SMPDataFlowAnalysis.cpp

void STARSConstantTypeMeet(struct STARS_SCCP_Const_Struct OldConstStruct, struct STARS_SCCP_Const_Struct &NewConstStruct) {
	if ((OldConstStruct.ConstType != STARS_CONST_BOTTOM) && (NewConstStruct.ConstType != STARS_CONST_TOP)) {
		// We have four possibilities. Three of them have NewConstStruct lower in the type lattice, which means the final
		//  result is simply the NewConstStruct (i.e. if Old == TOP, New == CONST or BOTTOM; or Old == CONST, New == BOTTOM).
		// The fourth possibility is that Old == CONST, New == CONST, and we have to check the const values for consistency,
		//  lowering NewConstStruct to BOTTOM if they are inconsistent.
		if ((OldConstStruct.ConstType == STARS_CONST_HAS_VALUE) && (NewConstStruct.ConstType == STARS_CONST_HAS_VALUE)) {
			if (OldConstStruct.ConstValue != NewConstStruct.ConstValue) { // inconsistent const values
				NewConstStruct.ConstType = STARS_CONST_BOTTOM;
			}
		}
	}
	else {
		NewConstStruct = OldConstStruct;
	}
	return;
} // end of STARSConstantTypeMeet()

// If one constant is greater width than another, trim it down.
void HandleConstStructWidths(size_t LeftByteWidth, size_t RightByteWidth, struct STARS_SCCP_Const_Struct &LeftValue, struct STARS_SCCP_Const_Struct &RightValue) {
	size_t LesserByteWidth = LeftByteWidth;
	if (LeftByteWidth > RightByteWidth) {
		LesserByteWidth = RightByteWidth;
		if (RightByteWidth == 4) {
			LeftValue.ConstValue &= 0xffffffff;
		}
		else if (RightByteWidth == 2) {
			LeftValue.ConstValue &= 0xffff;
		}
		else if (RightByteWidth == 1) {
			LeftValue.ConstValue &= 0xff;
		}
		else {
			SMP_msg("ERROR: Const struct width of %zu\n", RightByteWidth);
		}
	}
	else if (RightByteWidth > LeftByteWidth) {
		if (LeftByteWidth == 4) {
			RightValue.ConstValue &= 0xffffffff;
		}
		else if (LeftByteWidth == 2) {
			RightValue.ConstValue &= 0xffff;
		}
		else if (LeftByteWidth == 1) {
			RightValue.ConstValue &= 0xff;
		}
		else {
			SMP_msg("ERROR: Const struct width of %zu\n", LeftByteWidth);
		}
	}
	if (LesserByteWidth <= 4) {
		// Solve potential problem even if Left and Right widths are the same.
		STARS_uval_t LimitValue = 0xffffffff;
		if (LesserByteWidth == 2)
			LimitValue = 0xffff;
		else if (LesserByteWidth == 1)
			LimitValue = 0xff;
		if (LeftValue.ConstValue > LimitValue)
			LeftValue.ConstValue &= LimitValue;
		if (RightValue.ConstValue > LimitValue)
			RightValue.ConstValue &= LimitValue;
	}
	return;
} // end of HandleConstStructWidths()

// *****************************************************************
// Class DisAsmString
// *****************************************************************
DisAsmString::DisAsmString(void) {
	this->CurrAddr = STARS_BADADDR;
	this->StringLen = 0;
	this->CachedDisAsm[0] = '\0';
	return;
}

char *DisAsmString::GetDisAsm(STARS_ea_t InstAddr, bool MarkerInst) {
	if (InstAddr != this->CurrAddr) {
		this->CurrAddr = InstAddr;
		if (MarkerInst) {
			this->SetMarkerInstText(InstAddr);
		}
		else {
			bool IDAsuccess = SMP_generate_disasm_line(InstAddr, this->CachedDisAsm, sizeof(this->CachedDisAsm) - 1);
			if (IDAsuccess) {
				// Remove interactive color-coding tags.
				this->StringLen = SMP_tag_remove(this->CachedDisAsm, this->CachedDisAsm, sizeof(this->CachedDisAsm) - 1);
				if (-1 >= StringLen) {
					SMP_msg("ERROR: tag_remove failed at addr %lx \n", (unsigned long) InstAddr);
					this->CachedDisAsm[0] = '\0';
				}
			}
			else {
				SMP_msg("ERROR: generate_disasm_line failed at addr %lx \n", (unsigned long) InstAddr);
				this->CachedDisAsm[0] = '\0';
			}
		}
	}
	return (char *) this->CachedDisAsm;
} // end of DisAsmString::GetDisasm()

// Set the disasm text for the SSA marker instructions, which have no IDA Pro disasm because
//  they are pseudo-instructions that we add at the top of each function to hold LiveIn name info.
void DisAsmString::SetMarkerInstText(STARS_ea_t InstAddr) {
	if (InstAddr != this->CurrAddr) {
		this->CurrAddr = InstAddr;
		SMP_strncpy(this->CachedDisAsm, "\tfnop\t; Top of function SSA marker for SMP", 
			sizeof(this->CachedDisAsm) - 1);
		this->StringLen = (STARS_ssize_t) strlen(this->CachedDisAsm);
	}
	return;
} // end of DisAsmString::SetMarkerInstText()

DisAsmString DisAsmText;

// *****************************************************************
// Class DefOrUse
// *****************************************************************

// Default constructor to make the compilers happy.
DefOrUse::DefOrUse(void) {
	this->Operand = nullptr;
	this->SSANumber = -2;
	this->OpType = UNINIT;
	this->NonSpeculativeOpType = UNINIT;
	this->MetadataStatus = DEF_METADATA_UNANALYZED;
	this->booleans1 = 0;
	return;
}

// Constructor.
DefOrUse::DefOrUse(STARSOpndTypePtr Ref, SMPOperandType Type, int SSASub) {
	if (Ref->IsRegOp()) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		STARSOpndTypePtr Ref2 = CloneIfSubwordReg(Ref);
		CanonicalizeOpnd(Ref2);
		this->Operand = Ref2;
	}
	else {
		this->Operand = Ref;
	}
	this->SSANumber = SSASub;
	this->OpType = Type;

#if 0
	// Not true if we construct a reference for fptr shadowing late in our analyses.
	assert(!IsProfDerived(Type));
#endif
	this->NonSpeculativeOpType = Type;
	this->MetadataStatus = DEF_METADATA_UNANALYZED;
	this->booleans1 = 0;
	return;
}

// Copy constructor.
DefOrUse::DefOrUse(const DefOrUse &CopyIn) {
	*this = CopyIn;
	return;
}

// Assignment operator for copy constructor use.
DefOrUse &DefOrUse::operator=(const DefOrUse &rhs) {
	this->Operand = rhs.Operand;
	this->OpType = rhs.OpType;
	this->NonSpeculativeOpType = rhs.NonSpeculativeOpType;
	this->SSANumber = rhs.SSANumber;
	this->MetadataStatus = rhs.MetadataStatus;
	this->booleans1 = rhs.booleans1;
	return *this;
}

// Set the operand type for this DEF or USE - don't forget to take
//  into account the speculative (profiler) status.
void DefOrUse::SetType(SMPOperandType Type, const SMPInstr *Instr) {
	SMPOperandType OldType = this->OpType;

	SMPOperandType NewType = Type;
	if (Instr->GetBlock()->GetFunc()->GetIsSpeculative()) {
		NewType = (SMPOperandType)(((int)NewType) | PROF_BASE);
		if (!IsProfDerived(OldType))
			this->NonSpeculativeOpType = OldType;
	}

	this->OpType = NewType;
}

void DefOrUse::SetMetadataStatus(SMPMetadataType NewStatus) {
	// See if we are just updating explanation codes.
	bool OldUsed = ((this->MetadataStatus >= DEF_METADATA_USED) && (this->MetadataStatus < DEF_METADATA_REDUNDANT));
	if (OldUsed) {
		bool NewUsed = ((NewStatus >= DEF_METADATA_USED) && (NewStatus < DEF_METADATA_REDUNDANT));
		if (NewUsed) { 
			// Union the explanation codes.
			int TempInt = (int) this->GetMetadataStatus();
			TempInt |= (int) NewStatus; 
			this->MetadataStatus = (SMPMetadataType) TempInt; 
			return;
		}
	}
	this->MetadataStatus = NewStatus;
	return;
}

// Debug printing.
void DefOrUse::Dump(void) const {
	PrintListOperand(this->Operand, this->SSANumber);
	if (IsEqType(this->OpType , NUMERIC))
		SMP_msg("N ");
	else if (IsEqType(this->OpType , CODEPTR))
		SMP_msg("C ");
	else if (IsEqType(this->OpType , POINTER))
		SMP_msg("P ");
	else if (IsEqType(this->OpType , STACKPTR))
		SMP_msg("S ");
	else if (IsEqType(this->OpType , GLOBALPTR))
		SMP_msg("G ");
	else if (IsEqType(this->OpType , HEAPPTR))
		SMP_msg("H ");
	else if (IsEqType(this->OpType , PTROFFSET))
		SMP_msg("O ");
	else if (IsEqType(this->OpType , NEGATEDPTR))
		SMP_msg("NegP ");
	else if (IsEqType(this->OpType , UNKNOWN))
		SMP_msg("U ");

	/* emit the profile bit */
	if (IsProfDerived(this->OpType))
		SMP_msg("Pr ");

	// Don't write anything for UNINIT OpType

	// Emit the metadata status.
	if (DEF_METADATA_UNUSED == this->MetadataStatus)
		SMP_msg("Mn ");
	else if (DEF_METADATA_USED == this->MetadataStatus)
		SMP_msg("Mu ");
	else if (DEF_METADATA_REDUNDANT == this->MetadataStatus)
		SMP_msg("Mr ");
	// Is the DEF possibly aliased because of an indirect write in
	//  the DEF-USE chain?
	if (this->HasIndirectWrite())
		SMP_msg("Al* ");
	return;
} // end of DefOrUse::Dump()

// *****************************************************************
// Class DefOrUseSet
// *****************************************************************

// Default constructor.
DefOrUseSet::DefOrUseSet(void) {
	this->Refs.clear();
	return;
}

// Destructor.
DefOrUseSet::~DefOrUseSet() {
	this->Refs.clear();
	return;
}

// Find the reference for a given operand type.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::FindRef(const STARSOpndTypePtr &SearchOp) {
	set<DefOrUse, LessDefUse>::iterator CurrRef;
	DefOrUse DummyRef(SearchOp);
	CurrRef = this->Refs.find(DummyRef);
	return CurrRef;
}

std::set<DefOrUse, LessDefUse>::const_iterator DefOrUseSet::FindConstRef(const STARSOpndTypePtr &SearchOp) const {
	set<DefOrUse, LessDefUse>::const_iterator CurrRef;
	DefOrUse DummyRef(SearchOp);
	CurrRef = this->Refs.find(DummyRef);
	return CurrRef;

}

// Insert a new DEF or USE; must be new, insert must succeed else we assert.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::InsertRef(DefOrUse Ref) {
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(Ref);
	assert(InsertResult.second);
	return InsertResult.first;
}

// Set a Def or Use into the list, along with its type.
void DefOrUseSet::SetRef(STARSOpndTypePtr Ref, SMPOperandType Type, int SSASub) {
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	DefOrUse CurrRef(Ref, Type, SSASub);
	InsertResult = this->Refs.insert(CurrRef);
	if ((!(InsertResult.second)) && (! Ref->IsRegOp())) {
		SMP_msg("WARNING: Inserted duplicate DEF or USE: ");
		CurrRef.Dump(); SMP_msg("\n");
	}
	return;
}

// Change the indirect write status for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetOp(set<DefOrUse, LessDefUse>::iterator CurrRef, STARSOpndTypePtr NewOp) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	assert(CurrRef != this->Refs.end());
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetOp(NewOp);
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	return InsertResult.first;
} // end of DefOrUseSet::SetOp()

// Change the SSA subscript for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetSSANum(const STARSOpndTypePtr &CurrOp, int NewSSASub) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
	set<DefOrUse, LessDefUse>::iterator NextRef = CurrRef;
	++NextRef;
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetSSANum(NewSSASub);
	this->Refs.erase(CurrRef);
	CurrRef = this->Refs.insert(NextRef, NewCopy);
	return CurrRef;
} // end of DefOrUseSet::SetSSANum()

// Change the operand type for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetType(const STARSOpndTypePtr &CurrOp, SMPOperandType Type, const SMPInstr* Instr) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
#if 1
	if (CurrOp->IsImmedOp()) {
		if (UNINIT != CurrRef->GetType() && Type != CurrRef->GetType()) {
			SMP_msg("ERROR: Changing type of immediate from %d to %d at %llx: ", CurrRef->GetType(), Type, (uint64_t) Instr->GetAddr());
			CurrRef->Dump();
			SMP_msg("\n");
			Instr->Dump();
		}
	}
#endif
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetType(Type,Instr);
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
} // end of DefOrUseSet::SetType()

// Change the Metadata type for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetMetadata(const STARSOpndTypePtr &CurrOp, SMPMetadataType Status) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetMetadataStatus(Status);
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
} // end of DefOrUseSet::SetMetadata()

// Change the indirect write status for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetIndWrite(const STARSOpndTypePtr &CurrOp, bool IndWriteFlag) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetIndWrite(IndWriteFlag);
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
} // end of DefOrUseSet::SetIndWrite()

// Change the ignore apparent truncation flag for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetNoTruncation(const STARSOpndTypePtr &CurrOp, bool NoTruncFlag) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetNoTruncation(NoTruncFlag);
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
} // end of DefOrUseSet::SetNoTruncation()

// Change the ignore apparent overflow flag for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetNoOverflow(const STARSOpndTypePtr &CurrOp, bool NoOverflowFlag) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetNoOverflow(NoOverflowFlag);
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
} // end of DefOrUseSet::SetNoOverflow()

// Set a DEF as being invariant for all loops in the func.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetLoopInvariant(const STARSOpndTypePtr &CurrOp) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetInvariantForAllLoops();
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
} // end of DefOrUseSet::SetLoopInvariant()

// Set a DEF as being a safe memory write
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetSafeMemWrite(const STARSOpndTypePtr &CurrOp) {
	// To change a field within a set, we must grab a copy, change the copy,
	//  delete the old set member, and insert the updated copy as a new member.
	set<DefOrUse, LessDefUse>::iterator CurrRef = this->FindRef(CurrOp);
	assert(CurrRef != this->Refs.end());
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetSafeMemWriteDef();
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
} // end of DefOrUseSet::SetSafeMemWrite()

// Debug printing.
void DefOrUseSet::Dump(void) const {
	set<DefOrUse, LessDefUse>::iterator CurrRef;
	for (CurrRef = this->Refs.begin(); CurrRef != this->Refs.end(); ++CurrRef) {
		CurrRef->Dump();
	}
	SMP_msg("\n");
	return;
}

// Do all types agree, ignoring any flags registers in the set? This is used
//  for conditional move instructions; if all types agree, it does not matter
//  whether the move happens or not.
bool DefOrUseSet::TypesAgreeNoFlags(void) {
	bool FoundFirstUse = false;
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	SMPOperandType UseType = UNINIT;
	for (CurrUse = this->Refs.begin(); CurrUse != this->Refs.end(); ++CurrUse) {
		if (!(CurrUse->GetOp()->MatchesReg(X86_FLAGS_REG))) { // ignore flags
			if (!FoundFirstUse) {
				FoundFirstUse = true;
				UseType = CurrUse->GetType();
			}
			else {
				if (IsNotEqType(CurrUse->GetType(), UseType)) {
					return false; // inconsistent types
				}
			}
		}
	}
	return true;
} // end of DefOrUseSet::TypesAgreeNoFlags()


// *****************************************************************
// Class DefOrUseList
// *****************************************************************

// Default constructor.
DefOrUseList::DefOrUseList(void) {
	this->Refs.clear();
	return;
}

// Set a Def or Use into the list, along with its type.
void DefOrUseList::SetRef(STARSOpndTypePtr Ref, SMPOperandType Type, int SSASub) {
	DefOrUse CurrRef(Ref, Type, SSASub);
	this->Refs.push_back(CurrRef);
	return;
}

// Get a reference by index.
DefOrUse DefOrUseList::GetRef(size_t index) const {
	return Refs[index];
}

// Change the SSA subscript for a reference.
void DefOrUseList::SetSSANum(size_t index, int NewSSASub) {
	this->Refs[index].SetSSANum(NewSSASub);
	return;
}

// Change the operand type for a reference.
void DefOrUseList::SetType(size_t index, SMPOperandType Type, const SMPInstr* Instr) {
	this->Refs[index].SetType(Type,Instr);
	return;
}

void DefOrUseList::SetMaybeAliased(std::size_t index) {
	this->Refs[index].SetIndWrite(true);
	return;
}

// Debug printing.
void DefOrUseList::Dump(void) const {
	for (size_t index = 0; index < this->Refs.size(); ++index) {
		Refs[index].Dump();
	}
	SMP_msg("\n");
	return;
}

// Erase duplicate entries, in case SMPInstr::MDFixupDefUseLists() adds one.
void DefOrUseList::EraseDuplicates(void) {
	STARSOpndSet TempRefs; // Use STL set to find duplicates
	STARSOpndSet::iterator TempIter;
	vector<DefOrUse>::iterator RefIter;

	RefIter = this->Refs.begin();
	while (RefIter != this->Refs.end()) {
		TempIter = TempRefs.find(RefIter->GetOp());
		if (TempIter == TempRefs.end()) { // not already in set
			TempRefs.insert(RefIter->GetOp());
			++RefIter;
		}
		else { // found it in set already
			RefIter = this->Refs.erase(RefIter);
		}
	}
	return;
} // end of DefOrUseList::EraseDuplicates()

// *****************************************************************
// Class SMPPhiFunction
// *****************************************************************

// Constructor
SMPPhiFunction::SMPPhiFunction(int GlobIndex, const DefOrUse &Def) {
	this->index = GlobIndex;
	this->DefName = Def;
	this->SubscriptedOps.clear();
	return;
}

DefOrUse SMPPhiFunction::GetDefCopy(void) const {
	DefOrUse DefCopy(this->DefName);
	return DefCopy;
}

// Add a phi item to the list
void SMPPhiFunction::PushBack(DefOrUse Ref) {
	this->SubscriptedOps.SetRef(Ref.GetOp(), Ref.GetType(), Ref.GetSSANum());
	return;
}

// Set the SSA number of the defined variable.
void SMPPhiFunction::SetSSADef(int NewSSASub) {
	this->DefName.SetSSANum(NewSSASub);
	return;
}

// Set the SSA number of the input variable.
void SMPPhiFunction::SetSSARef(size_t index, int NewSSASub) {
	this->SubscriptedOps.SetSSANum(index, NewSSASub);
	return;
}

// Set the type of the defined variable.
void SMPPhiFunction::SetDefType(SMPOperandType Type, const SMPInstr* Instr) {
	this->DefName.SetType(Type, Instr);
	return;
}

// Set the type of the input variable.
void SMPPhiFunction::SetRefType(size_t index, SMPOperandType Type, const SMPInstr* Instr) {
	this->SubscriptedOps.SetType(index, Type, Instr);
	return;
}

// Record that the memory DEF might be aliased.
void SMPPhiFunction::SetDefMaybeAliased(void) {
	this->DefName.SetIndWrite(true);
	return;
}

// Record that the memory USE might be aliased.
void SMPPhiFunction::SetRefMaybeAliased(std::size_t index) {
	this->SubscriptedOps.SetMaybeAliased(index);
	return;
}

// Set the metadata status of the DEF variable.
void SMPPhiFunction::SetDefMetadata(SMPMetadataType Status) {
	this->DefName.SetMetadataStatus(Status);
	return;
} // end of SMPPhiFunction::SetDefMetadata()

// Does at least one USE have a type other than UNINIT?
bool SMPPhiFunction::HasTypedUses(void) {
	size_t index;
	for (index = 0; index < this->GetPhiListSize(); ++index) {
		if (UNINIT != this->GetUseType(index))
			return true;
	}
	return false;
} // end of SMPPhiFunction::HasTypedUses()

// Return the result of applying the conditional type propagation meet operator
//  over all the USE types.
SMPOperandType SMPPhiFunction::ConditionalMeetType(SMPBasicBlock *CurrBlock) const {
	SMPOperandType MeetType;
	SMPOperandType PtrType = UNINIT;
	SMPOperandType NumericType = UNINIT; // can end up NUMERIC or CODEPTR
	bool FoundUNINIT  = false; // any USE type UNINIT?
	bool FoundNUMERIC = false; // any USE type NUMERIC?
	bool FoundZero = false; // was DEF to zero? (could be POINTER or NUMERIC
	bool FoundPOINTER = false; // includes all POINTER subtypes
	bool FoundUNKNOWN = false; // any USE type UNKNOWN?
	bool FoundPTROFFSET = false; // any USE type PTROFFSET?
	bool FoundNEGATEDPTR = false; // any USE type NEGATEDPTR?
	bool ProfilerDerived = false; // was any USE type Profiler-derived?
	list<size_t> ZeroConstIndices;
	STARS_ea_t BlockStartAddr = CurrBlock->GetFirstAddr(); // for debugging
	STARSOpndTypePtr PhiOp = this->GetAnyOp();

	for (size_t index = 0; index < this->GetPhiListSize(); ++index) {
		SMPOperandType UseType = this->GetUseType(index);
		if (IsEqType(UseType, UNINIT))
			FoundUNINIT = true;
		else if (IsNumeric(UseType)) {
			// Check for possibility that we aggressively declared NUMERIC when register was set to zero.
			int UseSSANum = this->GetUseSSANum(index);
			bool CurrentUseZeroCase = false;
			if (MDIsDataFlowOpnd(PhiOp, false)) {
				STARS_ea_t DefAddr = CurrBlock->GetFunc()->GetGlobalDefAddr(PhiOp, UseSSANum);
				// Handle simple case: DEF is in an instruction.
				if ((STARS_BADADDR != DefAddr) && (DefAddr < STARS_PSEUDO_ID_MIN)) {
					SMPInstr *DefInst = CurrBlock->GetFunc()->GetInstFromAddr(DefAddr);
					CurrentUseZeroCase = DefInst->IsSetToZero();
				}
			}
			if (CurrentUseZeroCase) {
				FoundZero = true;
				ZeroConstIndices.push_back(index);
			}
			else {
				FoundNUMERIC = true;
				if (IsEqType(NumericType, CODEPTR)) {
					// Already refined. If current type agrees, leave it
					//  alone, else revert to generic type NUMERIC.
					if (IsNotEqType(UseType, NumericType))
						NumericType = NUMERIC;
				}
				else {
					// Have not yet refined NumericType; might still be UNINIT.
					if (IsEqType(UNINIT, NumericType))
						NumericType = UseType;
					else { // NumericType is NUMERIC; leave it as NUMERIC.
						assert(IsEqType(NUMERIC, NumericType));
					}
				}
			}
		}
		else if (IsDataPtr(UseType)) {
			FoundPOINTER = true;
			// Perform a meet over the pointer types.
			if (IsRefinedDataPtr(PtrType)) {
				// Already refined. If current type agrees, leave it
				//  alone, else revert to generic type POINTER.
				if (IsNotEqType(UseType, PtrType))
					PtrType = POINTER;
			}
			else {
				// Have not yet refined PtrType; might still be UNINIT.
				if (IsEqType(UNINIT, PtrType))
					PtrType = UseType;
				else { // PtrType is POINTER because we saw POINTER or
					// had a conflict between pointer refinements; leave
					// it as POINTER.
					assert(IsEqType(POINTER, PtrType));
				}
			}
		}
		else if (IsEqType(PTROFFSET, UseType)) 
			FoundPTROFFSET = true;
		else if (IsEqType(NEGATEDPTR, UseType)) 
			FoundNEGATEDPTR = true;
		else if (IsUnknown(UseType))
			FoundUNKNOWN = true;

		if (IsProfDerived(UseType))
			ProfilerDerived = true;
	}

	// Use the boolean flags to compute the meet function.
	if (FoundUNKNOWN || (FoundNUMERIC && FoundPOINTER) 
		|| ((FoundNUMERIC || FoundPOINTER || FoundNEGATEDPTR) && FoundPTROFFSET)
		|| ((FoundNUMERIC || FoundPOINTER || FoundPTROFFSET) && FoundNEGATEDPTR))
		MeetType = UNKNOWN;
	else if (FoundNUMERIC)
		MeetType = NumericType;
	else if (FoundPOINTER) {
		MeetType = PtrType;
		if (FoundZero) { // mixture of POINTER and const zero DEFs, i.e. ptr := NULL;
			// Undo the aggressive NUMERIC inference when registers are set to zero.
			//  NOTE: There cannot be any alterations to the reg between the zero DEF and
			//  the current block on at least one path, or it would not show up in the Phi function with the
			//  current SSA number.
			do {
				size_t ZeroConstIndex = ZeroConstIndices.front();
				int UseSSANum = this->GetUseSSANum(ZeroConstIndex);
				STARS_ea_t DefAddr = CurrBlock->GetFunc()->GetGlobalDefAddr(PhiOp, UseSSANum);
				// Handle simple case: DEF is in an instruction.
				if ((STARS_BADADDR != DefAddr) && (DefAddr < STARS_PSEUDO_ID_MIN)) {
					SMPInstr *DefInst = CurrBlock->GetFunc()->GetInstFromAddr(DefAddr);
					set<DefOrUse, LessDefUse>::iterator DefIter = DefInst->SetDefType(PhiOp, PtrType);
#if 0
					SMP_msg("INFO: Converting zeroed reg from NUMERIC to POINTER at %lx for Block at %lx\n",
						(unsigned long) DefAddr, (unsigned long) BlockStartAddr);
#endif
					CurrBlock->GetFunc()->ResetProcessedBlocks();
					SMPBasicBlock *DefBlock = CurrBlock->GetFunc()->GetBlockFromInstAddr(DefAddr);
#if 0 // Causes infinite loops, crashes; need to debug !!!!****!!!!
					DefBlock->PropagateGlobalDefType(PhiOp, PtrType, UseSSANum, false, true);
#else
					DefBlock->PropagateGlobalDefType(PhiOp, PtrType, UseSSANum, false, false);
#endif
				}
				ZeroConstIndices.pop_front();
			} while (!ZeroConstIndices.empty());
		}
	}
	else if (FoundPTROFFSET)
		MeetType = PTROFFSET;
	else if (FoundNEGATEDPTR)
		MeetType = NEGATEDPTR;
	else if (FoundZero && (!FoundUNINIT)) // nothing but zeroes
		MeetType = NUMERIC;
	else {
		assert(FoundUNINIT);
		MeetType = UNINIT;
	}
	if (ProfilerDerived)
		MeetType = MakeProfDerived(MeetType);
	return MeetType;
} // end of SMPPhiFunction::ConditionalMeetType()

// Debug printing.
void SMPPhiFunction::Dump(void) const {
	SMP_msg(" DEF: ");
	this->DefName.Dump();
	SMP_msg(" USEs: ");
	this->SubscriptedOps.Dump();
	return;
}

// *****************************************************************
// Class SMPDefUseChain
// *****************************************************************

// Constructors
SMPDefUseChain::SMPDefUseChain(void) {
	this->SSAName = nullptr;
	this->RefInstrs.clear();
	this->RefInstrs.push_back((unsigned short) STARS_BADADDR);
	this->IndWrite = false;
	return;
}

SMPDefUseChain::SMPDefUseChain(STARSOpndTypePtr Name, STARS_ea_t Def) {
	this->SetName(Name);
	this->RefInstrs.push_back(Def);
	this->IndWrite = false;
	return;
}

// Set the variable name.
void SMPDefUseChain::SetName(STARSOpndTypePtr Name) {
	STARSOpndTypePtr Name2 = nullptr;
	if (Name->IsRegOp()) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		Name2 = CloneIfSubwordReg(Name);
		CanonicalizeOpnd(Name2);
	}
	else {
		Name2 = Name;
	}
	this->SSAName = Name2;
	return;
}

// Set the DEF instruction.
void SMPDefUseChain::SetDef(STARS_ea_t Def) {
	this->RefInstrs[0] = (unsigned short) Def;
	return;
}

// Push a USE onto the list
void SMPDefUseChain::PushUse(STARS_ea_t Use) {
	this->RefInstrs.push_back((unsigned short) Use);
	return;
}

// Set the indirect memory write flag.
void SMPDefUseChain::SetIndWrite(bool IndMemWrite) {
	this->IndWrite = IndMemWrite;
	return;
}

// DEBUG dump.
void SMPDefUseChain::Dump(int SSANum) const {
	SMP_msg("DEF-USE chain for: ");
	PrintListOperand(this->SSAName, SSANum);
	if (this->RefInstrs.size() < 1) {
		SMP_msg(" no references.\n");
		return;
	}
	SMP_msg("\n DEF: %x USEs: ", this->RefInstrs[0]);
	size_t index;
	for (index = 1; index < this->RefInstrs.size(); ++index)
		SMP_msg("%x ", this->RefInstrs[index]);
	SMP_msg("\n");
	return;
} // end of SMPDefUseChain::Dump()

// *****************************************************************
// Class SMPDUChainArray
// *****************************************************************
SMPDUChainArray::SMPDUChainArray(void) {
	this->SSAName = nullptr;
	this->DUChains.clear();
	return;
}

SMPDUChainArray::SMPDUChainArray(STARSOpndTypePtr Name, STARS_ea_t FirstAddrMinusOne) {
	STARSOpndTypePtr Name2 = nullptr;
	if (Name->IsRegOp()) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		Name2 = CloneIfSubwordReg(Name);
		CanonicalizeOpnd(Name2);
	}
	else {
		Name2 = Name;
	}
	this->SSAName = Name2;
	this->BaseAddr = FirstAddrMinusOne;
	this->DUChains.clear();
	return;
}

STARS_ea_t SMPDUChainArray::GetLastUse(int SSANum) const {
	STARS_ea_t TempAddr = DUChains[(size_t)SSANum].GetLastUse();
	if (STARS_BADADDR != TempAddr) {
		// If STARS_BADADDR, leave it as STARS_BADADDR. Otherwise, add in BaseAddr.
		TempAddr += this->BaseAddr;
	}
	return TempAddr;
}

void SMPDUChainArray::SetName(STARSOpndTypePtr Name, STARS_ea_t FirstAddrMinusOne) {
	STARSOpndTypePtr Name2 = nullptr;
	if (Name->IsRegOp()) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		Name2 = CloneIfSubwordReg(Name);
		CanonicalizeOpnd(Name2);
	}
	else {
		Name2 = Name;
	}
	this->SSAName = Name2;
	this->BaseAddr = FirstAddrMinusOne;
	return;
}

// DEBUG dump.
void SMPDUChainArray::Dump(void) const {
	for (size_t index = 0; index < this->GetSize(); ++index) {
		this->DUChains[index].Dump((int) index);
	}
	return;
}

// *****************************************************************
// Class SMPCompleteDUChains
// *****************************************************************

// DEBUG dump.
void SMPCompleteDUChains::Dump(void) const {
	for (size_t index = 0; index < this->ChainsByName.size(); ++index) {
		this->ChainsByName[index].Dump();
	}
	return;
} // end of SMPCompleteDUChains::Dump()

// *****************************************************************
// Class STARSBitSet
// *****************************************************************

// Constructors.
STARSBitSet::STARSBitSet() {
	this->BitLimit = 0;
}

// Get methods
bool STARSBitSet::GetBit(size_t BitIndex) const {
	size_t ByteIndex = BitIndex / 8;
	size_t BitNumber = BitIndex % 8;
	assert(BitIndex <= this->BitLimit);
	return (0 != (this->STARSBits[ByteIndex] & STARSBitMasks[BitNumber]));
}

uint8_t STARSBitSet::GetByte(std::size_t ByteIndex) const {
	assert(ByteIndex < this->STARSBits.size());
	return this->STARSBits[ByteIndex];
}

// Set methods
void STARSBitSet::AllocateBits(size_t Size) {
	size_t Bytes = Size / 8;
	size_t ExtraBits = Size % 8;
	this->BitLimit = Size;
	if (0 != ExtraBits) {
		this->STARSBits.resize(1 + Bytes);
	}
	else {
		this->STARSBits.resize(Bytes);
	}
	for (Bytes = 0; Bytes < this->STARSBits.size(); ++Bytes) {
		this->STARSBits[Bytes] = 0;
	}
}

void STARSBitSet::SetBit(size_t BitIndex) {
	size_t ByteIndex = BitIndex / 8;
	size_t BitNumber = BitIndex % 8;
	assert(BitIndex <= this->BitLimit);
	this->STARSBits[ByteIndex] |= STARSBitMasks[BitNumber];
	return;
}

void STARSBitSet::ResetBit(size_t BitIndex) {
	size_t ByteIndex = BitIndex / 8;
	size_t BitNumber = BitIndex % 8;
	assert(BitIndex <= this->BitLimit);
	this->STARSBits[ByteIndex] &= (~STARSBitMasks[BitNumber]);
	return;
}

void STARSBitSet::ResetAllBits(void) {
	size_t NumBytes = this->STARSBits.size();
	for (size_t ByteIndex = 0; ByteIndex < NumBytes; ++ByteIndex) {
		this->STARSBits[ByteIndex] = 0;
	}
	return;
} // end of STARSBitSet::ResetAllBits()

// Query methods

// Returns false if all bits are zero, true otherwise.
bool STARSBitSet::IsAnyBitSet(void) const {
	bool FoundSetBit = false;
	size_t ByteIndex;
	for (ByteIndex = 0; ByteIndex < this->STARSBits.size(); ++ByteIndex) {
		if (0 != this->STARSBits[ByteIndex]) {
			FoundSetBit = true;
			break;
		}
	}

	return FoundSetBit;
}

// Return highest index set; -1 if no bits set.
int STARSBitSet::FindHighestBitSet(void) const {
	bool FoundSetBit = false;
	size_t ByteIndex, BitIndex, BitSetSize = this->STARSBits.size();
	assert(0 < BitSetSize);
	for (ByteIndex = BitSetSize; ByteIndex > 0; --ByteIndex) {
		if (0 != this->STARSBits[ByteIndex - 1]) {