SMPDataFlowAnalysis.cpp

// Change the SSA subscript for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetSSANum(op_t 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(op_t 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 (o_imm == CurrOp.type) {
		if (UNINIT != CurrRef->GetType() && Type != CurrRef->GetType()) {
			msg("ERROR: Changing type of immediate from %d to %d : ", CurrRef->GetType(), Type);
			CurrRef->Dump();
			msg("\n");
		}
	}
#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(op_t 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(op_t 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(op_t 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(op_t 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()

// Debug printing.
void DefOrUseSet::Dump(void) {
	set<DefOrUse, LessDefUse>::iterator CurrRef;
	for (CurrRef = this->Refs.begin(); CurrRef != this->Refs.end(); ++CurrRef) {
		CurrRef->Dump();
	}
	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().is_reg(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(op_t 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;
}

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

// Erase duplicate entries, in case SMPInstr::MDFixupDefUseLists() adds one.
void DefOrUseList::EraseDuplicates(void) {
	set<op_t, LessOp> TempRefs; // Use STL set to find duplicates
	set<op_t, LessOp>::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;
}

// 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(void) 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 FoundPOINTER = false; // includes all POINTER subtypes
	bool FoundUNKNOWN = false; // any USE type UNKNOWN?
	bool ProfilerDerived = false; // was any USE type Profiler-derived?

	for (size_t index = 0; index < this->GetPhiListSize(); ++index) {
		SMPOperandType UseType = this->GetUseType(index);
		if (IsEqType(UseType, UNINIT))
			FoundUNINIT = true;
		else if (IsNumeric(UseType)) {
			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 (IsUnknown(UseType))
			FoundUNKNOWN = true;

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

	// Use the boolean flags to compute the meet function.
	if (FoundUNKNOWN || (FoundNUMERIC && FoundPOINTER))
		MeetType = UNKNOWN;
	else if (FoundNUMERIC)
		MeetType = NumericType;
	else if (FoundPOINTER)
		MeetType = PtrType;
	else {
		assert(FoundUNINIT);
		MeetType = UNINIT;
	}
	if (ProfilerDerived)
		MeetType = MakeProfDerived(MeetType);
	return MeetType;
} // end of SMPPhiFunction::ConditionalMeetType()

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

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

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

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

// Set the variable name.
void SMPDefUseChain::SetName(op_t Name) {
	if (o_reg == Name.type) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		Name.reg = MDCanonicalizeSubReg(Name.reg);
	}
	this->SSAName = Name;
	return;
}

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

// Push a USE onto the list
void SMPDefUseChain::PushUse(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) {
	msg("DEF-USE chain for: ");
	PrintListOperand(this->SSAName, SSANum);
	if (this->RefInstrs.size() < 1) {
		msg(" no references.\n");
		return;
	}
	msg("\n DEF: %x USEs: ", this->RefInstrs.at(0));
	size_t index;
	for (index = 1; index < this->RefInstrs.size(); ++index)
		msg("%x ", this->RefInstrs.at(index));
	msg("\n");
	return;
} // end of SMPDefUseChain::Dump()

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

SMPDUChainArray::SMPDUChainArray(op_t Name, ea_t FirstAddrMinusOne) {
	if (o_reg == Name.type) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		Name.reg = MDCanonicalizeSubReg(Name.reg);
	}
	this->SSAName = Name;
	this->BaseAddr = FirstAddrMinusOne;
	this->DUChains.clear();
	return;
}

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

void SMPDUChainArray::SetName(op_t Name, ea_t FirstAddrMinusOne) {
	if (o_reg == Name.type) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		Name.reg = MDCanonicalizeSubReg(Name.reg);
	}
	this->SSAName = Name;
	this->BaseAddr = FirstAddrMinusOne;
	return;
}

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

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

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

// Map system or library call name to FG info about its return value.
static map<string, struct FineGrainedInfo> ReturnRegisterTypeMap;

// Map system or library call name to the annotation substring that
//  guides saturating arithmetic or other continuation policies in 
//  the case of integer error detection of a value passed to that call.
// If we don't care about a certain call, we return an empty string.
static map<string, string> IntegerErrorCallSinkMap;

void InitIntegerErrorCallSinkMap(void) {
	pair<string, string> MapEntry;
	pair<map<string, string>::iterator, bool> InsertResult;

	MapEntry.first = string("malloc");
	MapEntry.second = string("SINKMALLOC");
	InsertResult = IntegerErrorCallSinkMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = string("calloc");
	MapEntry.second = string("SINKMALLOC");
	InsertResult = IntegerErrorCallSinkMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = string("realloc");
	MapEntry.second = string("SINKMALLOC");
	InsertResult = IntegerErrorCallSinkMap.insert(MapEntry);
	assert(InsertResult.second);

	return;
}

// Return sink string for call name from the sink map.
// If we don't care find the call name, we return an empty string.
void GetSinkStringForCallName(string CalleeName, string &SinkString) {
	map<string, string>::iterator MapIter;

	SinkString.clear(); // empty string, append map string if found later
	MapIter = IntegerErrorCallSinkMap.find(CalleeName);

	if (MapIter != IntegerErrorCallSinkMap.end()) { // found it
		SinkString.append(MapIter->second);
	}
	return;
}

// Initialize the FG info for the return register from any library function
//  whose name implies that we know certain return values (e.g. atoi() returns
//  a signed integer, while strtoul() returns an unsigned long).
void GetLibFuncFGInfo(string FuncName, struct FineGrainedInfo &InitFGInfo) {
	map<string, struct FineGrainedInfo>::iterator FindIter;

	FindIter = ReturnRegisterTypeMap.find(FuncName);
	if (FindIter == ReturnRegisterTypeMap.end()) { // not found
		InitFGInfo.SignMiscInfo = 0;
		InitFGInfo.SizeInfo = 0;
	}
	else { // found
		InitFGInfo = FindIter->second;
	}
	return;
} // end of GetLibFuncFGInfo()

// Initialize the lookup maps that are used to define the FG info that can
//  be inferred from a library function name.
void InitLibFuncFGInfoMaps(void) {
	op_t DummyOp = InitOp;
	struct FineGrainedInfo FGEntry;
	pair<string, struct FineGrainedInfo> MapEntry;
	pair<map<string, struct FineGrainedInfo>::iterator, bool> InsertResult;

	// Add functions that return signed integers.
	FGEntry.SignMiscInfo = FG_MASK_SIGNED;
	FGEntry.SizeInfo = (FG_MASK_INTEGER | ComputeOperandBitWidthMask(DummyOp, sizeof(int)));
	MapEntry.second = FGEntry;

	MapEntry.first = "atoi";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strcmp";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strncmp";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "memcmp";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isalnum";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isalpha";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "islower";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isupper";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isdigit";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isxdigit";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "iscntrl";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isgraph";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isblank";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isspace";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "isprint";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "ispunct";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return signed longs.
	if (sizeof(long int) != sizeof(int)) {
		FGEntry.SizeInfo = (FG_MASK_INTEGER | ComputeOperandBitWidthMask(DummyOp, sizeof(long int)));
		MapEntry.second = FGEntry;
	}

	MapEntry.first = "atol";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strtol";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return signed long longs.
	if (sizeof(long long int) != sizeof(long int)) {
		FGEntry.SizeInfo = (FG_MASK_INTEGER | ComputeOperandBitWidthMask(DummyOp, sizeof(long long int)));
		MapEntry.second = FGEntry;
	}

	MapEntry.first = "atoll";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strtoll";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return unsigned long longs.
	FGEntry.SignMiscInfo = FG_MASK_UNSIGNED;
	MapEntry.second = FGEntry;

	MapEntry.first = "strtoull";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return unsigned longs.
	if (sizeof(long long int) != sizeof(long int)) {
		FGEntry.SizeInfo = (FG_MASK_INTEGER | ComputeOperandBitWidthMask(DummyOp, sizeof(long int)));
		MapEntry.second = FGEntry;
	}

	MapEntry.first = "strtoul";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return size_t.
	FGEntry.SizeInfo = (FG_MASK_INTEGER | ComputeOperandBitWidthMask(DummyOp, sizeof(size_t)));
	FGEntry.SignMiscInfo = FG_MASK_UNSIGNED;
	MapEntry.second = FGEntry;

	MapEntry.first = "strlen";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strxfrm";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strspn";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strcspn";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return (char *).
	FGEntry.SizeInfo = (FG_MASK_DATAPOINTER | ComputeOperandBitWidthMask(DummyOp, sizeof(char *)));
	FGEntry.SignMiscInfo = FG_MASK_UNSIGNED;
	MapEntry.second = FGEntry;

	MapEntry.first = "strcpy";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strncpy";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strcat";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strncat";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strcoll";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strchr";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strrchr";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strpbrk";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strstr";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strtok";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "strerror";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return (void *).
	if (sizeof(void *) != sizeof(char *)) {
		FGEntry.SizeInfo = (FG_MASK_DATAPOINTER | ComputeOperandBitWidthMask(DummyOp, sizeof(void *)));
		MapEntry.second = FGEntry;
	}

	MapEntry.first = "malloc";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "calloc";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "realloc";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "memchr";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "memcpy";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "mempcpy";  // non-standard, found in glibc
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "memmove";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	MapEntry.first = "memset";
	InsertResult = ReturnRegisterTypeMap.insert(MapEntry);
	assert(InsertResult.second);

	// Functions that return bool.
	FGEntry.SizeInfo = (FG_MASK_INTEGER | ComputeOperandBitWidthMask(DummyOp, sizeof(bool)));
	FGEntry.SignMiscInfo = FG_MASK_UNSIGNED;
	MapEntry.second = FGEntry;


	// NOTE: Add <math.h> functions later.

	return;
} // end of InitLibFuncFGInfoMaps()

// Initialize the DFACategory[] array to define instruction classes
//   for the purposes of data flow analysis.
void InitDFACategory(void) {
	// Default category is 0, not the start or end of a basic block.
	(void) memset(DFACategory, 0, sizeof(DFACategory));

DFACategory[NN_call] = CALL;                // Call Procedure
DFACategory[NN_callfi] = INDIR_CALL;              // Indirect Call Far Procedure
DFACategory[NN_callni] = INDIR_CALL;              // Indirect Call Near Procedure

DFACategory[NN_hlt] = HALT;                 // Halt

DFACategory[NN_int] = INDIR_CALL;                 // Call to Interrupt Procedure
DFACategory[NN_into] = INDIR_CALL;                // Call to Interrupt Procedure if Overflow Flag = 1
DFACategory[NN_int3] = INDIR_CALL;                // Trap to Debugger
DFACategory[NN_iretw] = RETURN;               // Interrupt Return
DFACategory[NN_iret] = RETURN;                // Interrupt Return
DFACategory[NN_iretd] = RETURN;               // Interrupt Return (use32)
DFACategory[NN_iretq] = RETURN;               // Interrupt Return (use64)
DFACategory[NN_ja] = COND_BRANCH;                  // Jump if Above (CF=0 & ZF=0)
DFACategory[NN_jae] = COND_BRANCH;                 // Jump if Above or Equal (CF=0)
DFACategory[NN_jb] = COND_BRANCH;                  // Jump if Below (CF=1)
DFACategory[NN_jbe] = COND_BRANCH;                 // Jump if Below or Equal (CF=1 | ZF=1)
DFACategory[NN_jc] = COND_BRANCH;                  // Jump if Carry (CF=1)
DFACategory[NN_jcxz] = COND_BRANCH;                // Jump if CX is 0
DFACategory[NN_jecxz] = COND_BRANCH;               // Jump if ECX is 0
DFACategory[NN_jrcxz] = COND_BRANCH;               // Jump if RCX is 0
DFACategory[NN_je] = COND_BRANCH;                  // Jump if Equal (ZF=1)
DFACategory[NN_jg] = COND_BRANCH;                  // Jump if Greater (ZF=0 & SF=OF)
DFACategory[NN_jge] = COND_BRANCH;                 // Jump if Greater or Equal (SF=OF)
DFACategory[NN_jl] = COND_BRANCH;                  // Jump if Less (SF!=OF)
DFACategory[NN_jle] = COND_BRANCH;                 // Jump if Less or Equal (ZF=1 | SF!=OF)
DFACategory[NN_jna] = COND_BRANCH;                 // Jump if Not Above (CF=1 | ZF=1)
DFACategory[NN_jnae] = COND_BRANCH;                // Jump if Not Above or Equal (CF=1)
DFACategory[NN_jnb] = COND_BRANCH;                 // Jump if Not Below (CF=0)
DFACategory[NN_jnbe] = COND_BRANCH;                // Jump if Not Below or Equal (CF=0 & ZF=0)
DFACategory[NN_jnc] = COND_BRANCH;                 // Jump if Not Carry (CF=0)
DFACategory[NN_jne] = COND_BRANCH;                 // Jump if Not Equal (ZF=0)
DFACategory[NN_jng] = COND_BRANCH;                 // Jump if Not Greater (ZF=1 | SF!=OF)
DFACategory[NN_jnge] = COND_BRANCH;                // Jump if Not Greater or Equal (ZF=1)
DFACategory[NN_jnl] = COND_BRANCH;                 // Jump if Not Less (SF=OF)
DFACategory[NN_jnle] = COND_BRANCH;                // Jump if Not Less or Equal (ZF=0 & SF=OF)
DFACategory[NN_jno] = COND_BRANCH;                 // Jump if Not Overflow (OF=0)
DFACategory[NN_jnp] = COND_BRANCH;                 // Jump if Not Parity (PF=0)
DFACategory[NN_jns] = COND_BRANCH;                 // Jump if Not Sign (SF=0)
DFACategory[NN_jnz] = COND_BRANCH;                 // Jump if Not Zero (ZF=0)
DFACategory[NN_jo] = COND_BRANCH;                  // Jump if Overflow (OF=1)
DFACategory[NN_jp] = COND_BRANCH;                  // Jump if Parity (PF=1)
DFACategory[NN_jpe] = COND_BRANCH;                 // Jump if Parity Even (PF=1)
DFACategory[NN_jpo] = COND_BRANCH;                 // Jump if Parity Odd  (PF=0)
DFACategory[NN_js] = COND_BRANCH;                  // Jump if Sign (SF=1)
DFACategory[NN_jz] = COND_BRANCH;                  // Jump if Zero (ZF=1)
DFACategory[NN_jmp] = JUMP;                 // Jump
DFACategory[NN_jmpfi] = INDIR_JUMP;               // Indirect Far Jump
DFACategory[NN_jmpni] = INDIR_JUMP;               // Indirect Near Jump
DFACategory[NN_jmpshort] = JUMP;            // Jump Short (only in 64-bit mode)

DFACategory[NN_loopw] = COND_BRANCH;               // Loop while ECX != 0
DFACategory[NN_loop] = COND_BRANCH;                // Loop while CX != 0
DFACategory[NN_loopd] = COND_BRANCH;               // Loop while ECX != 0
DFACategory[NN_loopq] = COND_BRANCH;               // Loop while RCX != 0
DFACategory[NN_loopwe] = COND_BRANCH;              // Loop while CX != 0 and ZF=1
DFACategory[NN_loope] = COND_BRANCH;               // Loop while rCX != 0 and ZF=1
DFACategory[NN_loopde] = COND_BRANCH;              // Loop while ECX != 0 and ZF=1
DFACategory[NN_loopqe] = COND_BRANCH;              // Loop while RCX != 0 and ZF=1
DFACategory[NN_loopwne] = COND_BRANCH;             // Loop while CX != 0 and ZF=0
DFACategory[NN_loopne] = COND_BRANCH;              // Loop while rCX != 0 and ZF=0
DFACategory[NN_loopdne] = COND_BRANCH;             // Loop while ECX != 0 and ZF=0
DFACategory[NN_loopqne] = COND_BRANCH;             // Loop while RCX != 0 and ZF=0

DFACategory[NN_retn] = RETURN;                // Return Near from Procedure
DFACategory[NN_retf] = RETURN;                // Return Far from Procedure

//
//      Pentium instructions
//

DFACategory[NN_rsm] = HALT;                 // Resume from System Management Mode

//      Pentium II instructions

DFACategory[NN_sysenter] = CALL;            // Fast Transition to System Call Entry Point
DFACategory[NN_sysexit] = CALL;             // Fast Transition from System Call Entry Point

// AMD syscall/sysret instructions  NOTE: not AMD, found in Intel manual

DFACategory[NN_syscall] = CALL;             // Low latency system call
DFACategory[NN_sysret] = CALL;              // Return from system call

// VMX instructions

DFACategory[NN_vmcall] = INDIR_CALL;              // Call to VM Monitor

  return;

} // end InitDFACategory()

// Initialize the SMPDefsFlags[] array to define how we emit
//   optimizing annotations.
void InitSMPDefsFlags(void) {
	// Default value is true. Many instructions set the flags.
	(void) memset(SMPDefsFlags, true, sizeof(SMPDefsFlags));

SMPDefsFlags[NN_null] = false;            // Unknown Operation
SMPDefsFlags[NN_bound] = false;               // Check Array Index Against Bounds
SMPDefsFlags[NN_call] = false;                // Call Procedure
SMPDefsFlags[NN_callfi] = false;              // Indirect Call Far Procedure
SMPDefsFlags[NN_callni] = false;              // Indirect Call Near Procedure
SMPDefsFlags[NN_cbw] = false;                 // AL -> AX (with sign)           
SMPDefsFlags[NN_cwde] = false;                // AX -> EAX (with sign)            
SMPDefsFlags[NN_cdqe] = false;                // EAX -> RAX (with sign)           
SMPDefsFlags[NN_clts] = false;                // Clear Task-Switched Flag in CR0
SMPDefsFlags[NN_cwd] = false;                 // AX -> DX:AX (with sign)
SMPDefsFlags[NN_cdq] = false;                 // EAX -> EDX:EAX (with sign)
SMPDefsFlags[NN_cqo] = false;                 // RAX -> RDX:RAX (with sign)
SMPDefsFlags[NN_enterw] = false;              // Make Stack Frame for Procedure Parameters   
SMPDefsFlags[NN_enter] = false;               // Make Stack Frame for Procedure Parameters   
SMPDefsFlags[NN_enterd] = false;              // Make Stack Frame for Procedure Parameters   
SMPDefsFlags[NN_enterq] = false;              // Make Stack Frame for Procedure Parameters   
SMPDefsFlags[NN_hlt] = false;                 // Halt
SMPDefsFlags[NN_in] = false;                  // Input from Port                          
SMPDefsFlags[NN_ins] = false;                 // Input Byte(s) from Port to String        
SMPDefsFlags[NN_iretw] = false;               // Interrupt Return
SMPDefsFlags[NN_iret] = false;                // Interrupt Return
SMPDefsFlags[NN_iretd] = false;               // Interrupt Return (use32)
SMPDefsFlags[NN_iretq] = false;               // Interrupt Return (use64)
SMPDefsFlags[NN_ja] = false;                  // Jump if Above (CF=0 & ZF=0)
SMPDefsFlags[NN_jae] = false;                 // Jump if Above or Equal (CF=0)
SMPDefsFlags[NN_jb] = false;                  // Jump if Below (CF=1)
SMPDefsFlags[NN_jbe] = false;                 // Jump if Below or Equal (CF=1 | ZF=1)
SMPDefsFlags[NN_jc] = false;                  // Jump if Carry (CF=1)
SMPDefsFlags[NN_jcxz] = false;                // Jump if CX is 0
SMPDefsFlags[NN_jecxz] = false;               // Jump if ECX is 0
SMPDefsFlags[NN_jrcxz] = false;               // Jump if RCX is 0
SMPDefsFlags[NN_je] = false;                  // Jump if Equal (ZF=1)
SMPDefsFlags[NN_jg] = false;                  // Jump if Greater (ZF=0 & SF=OF)
SMPDefsFlags[NN_jge] = false;                 // Jump if Greater or Equal (SF=OF)
SMPDefsFlags[NN_jl] = false;                  // Jump if Less (SF!=OF)
SMPDefsFlags[NN_jle] = false;                 // Jump if Less or Equal (ZF=1 | SF!=OF)
SMPDefsFlags[NN_jna] = false;                 // Jump if Not Above (CF=1 | ZF=1)
SMPDefsFlags[NN_jnae] = false;                // Jump if Not Above or Equal (CF=1)
SMPDefsFlags[NN_jnb] = false;                 // Jump if Not Below (CF=0)
SMPDefsFlags[NN_jnbe] = false;                // Jump if Not Below or Equal (CF=0 & ZF=0)
SMPDefsFlags[NN_jnc] = false;                 // Jump if Not Carry (CF=0)
SMPDefsFlags[NN_jne] = false;                 // Jump if Not Equal (ZF=0)
SMPDefsFlags[NN_jng] = false;                 // Jump if Not Greater (ZF=1 | SF!=OF)
SMPDefsFlags[NN_jnge] = false;                // Jump if Not Greater or Equal (ZF=1)
SMPDefsFlags[NN_jnl] = false;                 // Jump if Not Less (SF=OF)
SMPDefsFlags[NN_jnle] = false;                // Jump if Not Less or Equal (ZF=0 & SF=OF)
SMPDefsFlags[NN_jno] = false;                 // Jump if Not Overflow (OF=0)
SMPDefsFlags[NN_jnp] = false;                 // Jump if Not Parity (PF=0)
SMPDefsFlags[NN_jns] = false;                 // Jump if Not Sign (SF=0)
SMPDefsFlags[NN_jnz] = false;                 // Jump if Not Zero (ZF=0)
SMPDefsFlags[NN_jo] = false;                  // Jump if Overflow (OF=1)
SMPDefsFlags[NN_jp] = false;                  // Jump if Parity (PF=1)
SMPDefsFlags[NN_jpe] = false;                 // Jump if Parity Even (PF=1)
SMPDefsFlags[NN_jpo] = false;                 // Jump if Parity Odd  (PF=0)
SMPDefsFlags[NN_js] = false;                  // Jump if Sign (SF=1)
SMPDefsFlags[NN_jz] = false;                  // Jump if Zero (ZF=1)
SMPDefsFlags[NN_jmp] = false;                 // Jump
SMPDefsFlags[NN_jmpfi] = false;               // Indirect Far Jump
SMPDefsFlags[NN_jmpni] = false;               // Indirect Near Jump
SMPDefsFlags[NN_jmpshort] = false;            // Jump Short (not used)
SMPDefsFlags[NN_lahf] = false;                // Load Flags into AH Register
SMPDefsFlags[NN_lea] = false;                 // Load Effective Address            
SMPDefsFlags[NN_leavew] = false;              // High Level Procedure Exit         
SMPDefsFlags[NN_leave] = false;               // High Level Procedure Exit         
SMPDefsFlags[NN_leaved] = false;              // High Level Procedure Exit         
SMPDefsFlags[NN_leaveq] = false;              // High Level Procedure Exit         
SMPDefsFlags[NN_lgdt] = false;                // Load Global Descriptor Table Register
SMPDefsFlags[NN_lidt] = false;                // Load Interrupt Descriptor Table Register
SMPDefsFlags[NN_lgs] = false;                 // Load Full Pointer to GS:xx
SMPDefsFlags[NN_lss] = false;                 // Load Full Pointer to SS:xx
SMPDefsFlags[NN_lds] = false;                 // Load Full Pointer to DS:xx
SMPDefsFlags[NN_les] = false;                 // Load Full Pointer to ES:xx
SMPDefsFlags[NN_lfs] = false;                 // Load Full Pointer to FS:xx
SMPDefsFlags[NN_loopwe] = false;              // Loop while CX != 0 and ZF=1
SMPDefsFlags[NN_loope] = false;               // Loop while rCX != 0 and ZF=1
SMPDefsFlags[NN_loopde] = false;              // Loop while ECX != 0 and ZF=1
SMPDefsFlags[NN_loopqe] = false;              // Loop while RCX != 0 and ZF=1
SMPDefsFlags[NN_loopwne] = false;             // Loop while CX != 0 and ZF=0
SMPDefsFlags[NN_loopne] = false;              // Loop while rCX != 0 and ZF=0
SMPDefsFlags[NN_loopdne] = false;             // Loop while ECX != 0 and ZF=0
SMPDefsFlags[NN_loopqne] = false;             // Loop while RCX != 0 and ZF=0
SMPDefsFlags[NN_ltr] = false;                 // Load Task Register
SMPDefsFlags[NN_mov] = false;                 // Move Data
SMPDefsFlags[NN_movsp] = true;                // Move to/from Special Registers
SMPDefsFlags[NN_movs] = false;                // Move Byte(s) from String to String
SMPDefsFlags[NN_movsx] = false;               // Move with Sign-Extend
SMPDefsFlags[NN_movzx] = false;               // Move with Zero-Extend
SMPDefsFlags[NN_nop] = false;                 // No Operation
SMPDefsFlags[NN_not] = false;                 // One's Complement Negation
SMPDefsFlags[NN_out] = false;                 // Output to Port
SMPDefsFlags[NN_outs] = false;                // Output Byte(s) to Port
SMPDefsFlags[NN_pop] = false;                 // Pop a word from the Stack
SMPDefsFlags[NN_popaw] = false;               // Pop all General Registers
SMPDefsFlags[NN_popa] = false;                // Pop all General Registers
SMPDefsFlags[NN_popad] = false;               // Pop all General Registers (use32)
SMPDefsFlags[NN_popaq] = false;               // Pop all General Registers (use64)
SMPDefsFlags[NN_push] = false;                // Push Operand onto the Stack
SMPDefsFlags[NN_pushaw] = false;              // Push all General Registers
SMPDefsFlags[NN_pusha] = false;               // Push all General Registers
SMPDefsFlags[NN_pushad] = false;              // Push all General Registers (use32)
SMPDefsFlags[NN_pushaq] = false;              // Push all General Registers (use64)
SMPDefsFlags[NN_pushfw] = false;              // Push Flags Register onto the Stack
SMPDefsFlags[NN_pushf] = false;               // Push Flags Register onto the Stack
SMPDefsFlags[NN_pushfd] = false;              // Push Flags Register onto the Stack (use32)
SMPDefsFlags[NN_pushfq] = false;              // Push Flags Register onto the Stack (use64)
SMPDefsFlags[NN_rep] = false;                 // Repeat String Operation
SMPDefsFlags[NN_repe] = false;                // Repeat String Operation while ZF=1
SMPDefsFlags[NN_repne] = false;               // Repeat String Operation while ZF=0
SMPDefsFlags[NN_retn] = false;                // Return Near from Procedure
SMPDefsFlags[NN_retf] = false;                // Return Far from Procedure
SMPDefsFlags[NN_sahf] = true;                 // Store AH into flags
SMPDefsFlags[NN_shl] = true;                  // Shift Logical Left
SMPDefsFlags[NN_shr] = true;                  // Shift Logical Right
SMPDefsFlags[NN_seta] = false;                // Set Byte if Above (CF=0 & ZF=0)
SMPDefsFlags[NN_setae] = false;               // Set Byte if Above or Equal (CF=0)
SMPDefsFlags[NN_setb] = false;                // Set Byte if Below (CF=1)