SMPDataFlowAnalysis.cpp

//
// SMPDataFlowAnalysis.cpp
//
// This module contains common types an helper classes needed for the
//   SMP project (Software Memory Protection).
//

#include <list>
#include <set>
#include <vector>
#include <algorithm>

#include <cstring>

#include <pro.h>
#include <assert.h>
#include <ida.hpp>
#include <idp.hpp>
#include <allins.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <intel.hpp>
#include <loader.hpp>
#include <lines.hpp>
#include <name.hpp>

#include "SMPDataFlowAnalysis.h"
#include "SMPStaticAnalyzer.h"

// Set to 1 for debugging output
#define SMP_DEBUG 1
#define SMP_DEBUG2 0   // verbose
#define SMP_DEBUG3 0   // verbose
#define SMP_DEBUG_CONTROLFLOW 0  // tells what processing stage is entered
#define SMP_DEBUG_XOR 0
#define SMP_DEBUG_CHUNKS 1  // tracking down tail chunks for functions
#define SMP_DEBUG_FRAMEFIXUP 0
#define SMP_DEBUG_DATAFLOW 0
#define SMP_DEBUG_OPERAND_TYPES 1  // leave on; should never happen

char *RegNames[R_of + 1] =
	{ "EAX", "ECX", "EDX", "EBX", "ESP", "EBP", "ESI", "EDI",
	  "R8", "R9", "R10", "R11", "R12", "R13", "R14", "R15",
	  "AL", "CL", "DL", "BL", "AH", "CH", "DH", "BH",
	  "SPL", "BPL", "SIL", "DIL", "EIP", "ES", "CS", "SS",
	  "DS", "FS", "GS", "CF", "ZF", "SF", "OF" 
	};

// Define instruction categories for data flow analysis.
SMPitype DFACategory[NN_last+1];
// Define instruction categories for data type analysis.
int SMPTypeCategory[NN_last+1];

// Define which instructions define and use the CPU flags.
bool SMPDefsFlags[NN_last + 1];
bool SMPUsesFlags[NN_last + 1];

// Get the size in bytes of the data type of an operand.
size_t GetOpDataSize(op_t DataOp) {
	size_t DataSize;
	switch (DataOp.dtyp) {
		case dt_byte:
			DataSize = 1;
			break;
		case dt_word:
			DataSize = 2;
			break;
		case dt_dword:
		case dt_float:
		case dt_code:
		case dt_unicode:
		case dt_string:
			DataSize = 4;
			break;
		case dt_double:
		case dt_qword:
			DataSize = 8;
			break;
		case dt_packreal:
			DataSize = 12;
			break;
		case dt_byte16:
			DataSize = 16;
			break;
		case dt_fword:
			DataSize = 6;
			break;
		case dt_3byte:
			DataSize = 3;
			break;
		default:
			msg("WARNING: unexpected data type %d in GetOpDataSize() :", DataOp.dtyp);
			PrintOperand(DataOp);
			msg("\n");
			DataSize = 4;
			break;
	}
	return DataSize;
} // end of GetOpDataSize()

// We need to make subword registers equal to their containing registers when we
//  do comparisons, so that we will realize that register EAX is killed by a prior DEF
//  of register AL, for example, and vice versa. To keep sets ordered strictly,
//  we also have to make AL and AH be equal to each other as well as equal to EAX.
#define FIRST_x86_SUBWORD_REG R_al
#define LAST_x86_SUBWORD_REG R_bh
bool MDLessReg(const ushort Reg1, const ushort Reg2) {
	ushort SReg1 = MDCanonicalizeSubReg(Reg1);
	ushort SReg2 = MDCanonicalizeSubReg(Reg2);
	return (SReg1 < SReg2);
} // end of MDLessReg()

ushort MDCanonicalizeSubReg(const ushort Reg1) {
	bool Subword = ((Reg1 >= FIRST_x86_SUBWORD_REG) && (Reg1 <= LAST_x86_SUBWORD_REG));
	ushort SReg1 = Reg1;

	if (Subword) {
		// See enumeration RegNo in intel.hpp.
		if (SReg1 < 20)  // AL, CL, DL or BL
			SReg1 -= 16;
		else             // AH, CH, DH or BH
			SReg1 -= 20;
	}
	return SReg1;
} // end of MDCanonicalizeSubReg()

// In SSA computations, we are storing the GlobalNames index into the op_t fields
//  n, offb, and offo. This function extracts an unsigned int from these three 8-bit
//  fields.
unsigned int ExtractGlobalIndex(op_t GlobalOp) {
	unsigned int index = 0;
	index |= (((unsigned int) GlobalOp.offo) & 0x000000ff);
	index <<= 8;
	index |= (((unsigned int) GlobalOp.offb) & 0x000000ff);
	index <<= 8;
	index |= (((unsigned int) GlobalOp.n) & 0x000000ff);
	return index;
}

void SetGlobalIndex(op_t *TempOp, size_t index) {
	TempOp->n = (char) (index & 0x000000ff);
	TempOp->offb = (char) ((index & 0x0000ff00) >> 8);
	TempOp->offo = (char) ((index & 0x00ff0000) >> 16);
	return;
}

// Return true if CurrOp could be an indirect memory reference.
bool MDIsIndirectMemoryOpnd(op_t CurrOp, bool UseFP) {
	bool indirect = false;
	if ((CurrOp.type != o_mem) && (CurrOp.type != o_phrase) && (CurrOp.type != o_displ))
		return false;

	if (CurrOp.hasSIB) {
		int BaseReg = sib_base(CurrOp);
		short IndexReg = sib_index(CurrOp);
		if ((R_none != IndexReg) && (R_sp != IndexReg)) { 
			if ((R_bp == IndexReg) && UseFP)
				;
			else
				indirect = true;
		}
		if (0 != sib_scale(CurrOp))
			indirect = true;
		if (R_none != BaseReg) {
			if ((BaseReg == R_bp) && (CurrOp.type == o_mem)) {
				; // EBP ==> no base register for o_mem type
			}
			else if ((BaseReg == R_bp) && UseFP) 
				;  // EBP used as frame pointer for direct access
			else if (BaseReg == R_sp)
				;  // ESP used as stack pointer for direct access
			else
				indirect = true; // conservative; some register used for addressing
								// other than a stack or frame pointer
		}
	} // end if hasSIB
	else { // no SIB; can have base register only
		ushort BaseReg = CurrOp.reg;
		if (CurrOp.type == o_mem) { // no base register for o_mem
			if (!((0 == BaseReg) || (R_bp == BaseReg))) {
				msg("base reg %d ignored \n", BaseReg);
			}
		}
		else if ((BaseReg == R_bp) && UseFP) 
			;  // EBP used as frame pointer for direct access
		else if (BaseReg == R_sp)
			;  // ESP used as stack pointer for direct access
		else {
			indirect = true;
		}
	}

	return indirect;
} // end MDIsIndirectMemoryOpnd()

// Extract the base and index registers and scale factor and displacement from the
//  memory operand.
void MDExtractAddressFields(op_t MemOp, int &BaseReg, int &IndexReg, ushort &Scale, ea_t &Offset) {
	assert((MemOp.type == o_phrase) || (MemOp.type == o_displ) || (MemOp.type == o_mem));

	Scale = 0;
	BaseReg = R_none;
	IndexReg = R_none;
	Offset = MemOp.addr;

	if (MemOp.hasSIB) {
		BaseReg = sib_base(MemOp);
		IndexReg = (int) sib_index(MemOp);
		if (R_sp == IndexReg) // signifies no index register
			IndexReg = R_none;
		if (R_none != IndexReg) {
			Scale = sib_scale(MemOp);
		}
		if (R_none != BaseReg) {
			if ((BaseReg == R_bp) && (MemOp.type == o_mem)) {
				BaseReg = R_none;
			}
		}
	}
	else { // no SIB byte; can have base reg but no index reg or scale factor
		BaseReg = (int) MemOp.reg;  // cannot be R_none for no SIB case
		if (MemOp.type == o_mem) {
			BaseReg = R_none; // no Base register for o_mem operands
		}
	}

	return;
} // end of MDExtractAddressFields()

// DEBUG Print DEF and/or USE for an operand.
void PrintDefUse(ulong feature, int OpNum) {
	// CF_ macros number the operands from 1 to 6, while OpNum
	//  is a 0 to 5 index into the insn_t.Operands[] array.
	// OpNum == -1 is a signal that this is a DEF or USE or VarKillSet etc.
	//  operand and not an instruction operand.
	if (-1 == OpNum)
		return;
	switch (OpNum) {
		case 0:
			if (feature & CF_CHG1)
				msg(" DEF");
			if (feature & CF_USE1)
				msg(" USE");
			break;
		case 1:
			if (feature & CF_CHG2)
				msg(" DEF");
			if (feature & CF_USE2)
				msg(" USE");
			break;
		case 2:
			if (feature & CF_CHG3)
				msg(" DEF");
			if (feature & CF_USE3)
				msg(" USE");
			break;
		case 3:
			if (feature & CF_CHG4)
				msg(" DEF");
			if (feature & CF_USE4)
				msg(" USE");
			break;
		case 4:
			if (feature & CF_CHG5)
				msg(" DEF");
			if (feature & CF_USE5)
				msg(" USE");
			break;
		case 5:
			if (feature & CF_CHG6)
				msg(" DEF");
			if (feature & CF_USE6)
				msg(" USE");
			break;
	}
	return;
} // end PrintDefUse()

// DEBUG print SIB info for an operand.
void PrintSIB(op_t Opnd) {
	int BaseReg;
	int IndexReg;
	ushort ScaleFactor;
	ea_t offset;
#define NAME_LEN 5
	char BaseName[NAME_LEN] = {'N', 'o', 'n', 'e', '\0'};
	char IndexName[NAME_LEN] = {'N', 'o', 'n', 'e', '\0'};

	MDExtractAddressFields(Opnd, BaseReg, IndexReg, ScaleFactor, offset);

	if (BaseReg != R_none)
		qstrncpy(BaseName, RegNames[BaseReg], NAME_LEN - 1);

	if (IndexReg != R_none) {
		qstrncpy(IndexName, RegNames[IndexReg], NAME_LEN -1);
	}
	msg(" Base %s Index %s Scale %d", BaseName, IndexName, ScaleFactor);
} // end PrintSIB()

// Debug: print one operand from an instruction or DEF or USE list.
void PrintOneOperand(op_t Opnd, ulong features, int OpNum) { 
	if (Opnd.type != o_void) {
		PrintOperand(Opnd);
		PrintDefUse(features, OpNum);
	}
	return;
} // end of PrintOneOperand()

// Debug: print one operand.
void PrintOperand(op_t Opnd) { 
	if (Opnd.type == o_void)
		return;
	else if (Opnd.type == o_mem) {
		msg(" Operand: memory : addr: %x", Opnd.addr);
		if (Opnd.hasSIB) {
			PrintSIB(Opnd);
		}
	}
	else if (Opnd.type == o_phrase) {
		msg(" Operand: memory phrase :");
		if (Opnd.hasSIB) { // has SIB info
			PrintSIB(Opnd);
		}
		else { // no SIB info
			ushort BaseReg = Opnd.phrase;
			msg(" reg %s", RegNames[BaseReg]);
		}
		if (Opnd.addr != 0) {
			msg(" \n WARNING: addr for o_phrase type: %d\n", Opnd.addr);
		}
	}
	else if (Opnd.type == o_displ) {
		msg(" Operand: memory displ :");
		ea_t offset = Opnd.addr;
		if (Opnd.hasSIB) {
			PrintSIB(Opnd);
			msg(" displ %d", offset);
		}
		else {
			ushort BaseReg = Opnd.reg;
			msg(" reg %s displ %d", RegNames[BaseReg], offset);
		}
	}
	else if (Opnd.type == o_reg) {
		msg(" Operand: register %s", RegNames[Opnd.reg]);
	}
	else if (Opnd.type == o_imm) {
		msg(" Operand: immed %d", Opnd.value);
	}
	else if (Opnd.type == o_far) {
		msg(" Operand: FarPtrImmed addr: %x", Opnd.addr);
	}
	else if (Opnd.type == o_near) {
		msg(" Operand: NearPtrImmed addr: %x", Opnd.addr);
	}
	else if (Opnd.type == o_trreg) {
		msg(" Operand: TaskReg reg: %d", Opnd.reg);
	}
	else if (Opnd.type == o_dbreg) {
		msg(" Operand: DebugReg reg: %d", Opnd.reg);
	}
	else if (Opnd.type == o_crreg) {
		msg(" Operand: ControlReg reg: %d", Opnd.reg);
	}
	else if (Opnd.type == o_fpreg) {
		msg(" Operand: FloatReg reg: %d", Opnd.reg);
	}
	else if (Opnd.type == o_mmxreg) {
		msg(" Operand: MMXReg reg: %d", Opnd.reg);
	}
	else if (Opnd.type == o_xmmreg) {
		msg(" Operand: XMMReg reg: %d", Opnd.reg);
	}
	else {
		msg(" Operand: unknown");
	}
	if (!(Opnd.showed()))
		msg(" HIDDEN ");
	return;
} // end of PrintOperand()

// Print an operand that has no features flags or operand position number, such
//  as the op_t types found in lists and sets throughout the blocks, phi functions, etc.
void PrintListOperand(op_t Opnd, int SSANum) {
	if (Opnd.type != o_void) {
		PrintOperand(Opnd);
		msg(" SSANum: %d ", SSANum);
	}
	return;
} // end of PrintListOperand()

// MACHINE DEPENDENT: Is operand type a known type that we want to analyze?
bool MDKnownOperandType(op_t TempOp) {
	bool GoodOpType = ((TempOp.type >= o_reg) && (TempOp.type <= o_xmmreg));
#if SMP_DEBUG_OPERAND_TYPES
	if (!GoodOpType && (o_void != TempOp.type)) {
		msg("WARNING: Operand type %d \n", TempOp.type);
	}
#endif 
	return GoodOpType;
}

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

// Default constructor to make the compilers happy.
DefOrUse::DefOrUse(void) {
	this->OpType = UNINIT;
	this->SSANumber = -2;
	return;
}

// Constructor.
DefOrUse::DefOrUse(op_t Ref, SMPOperandType Type, int SSASub) {
	if (o_reg == Ref.type) {
		// We want to map AH, AL, and AX to EAX, etc. throughout our data flow analysis
		//  and type inference systems.
		Ref.reg = MDCanonicalizeSubReg(Ref.reg);
	}
	this->Operand = Ref;
	this->OpType = Type;
	this->SSANumber = SSASub;
	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->SSANumber = rhs.SSANumber;
	return *this;
}

// Debug printing.
void DefOrUse::Dump(void) const {
	PrintListOperand(this->Operand, this->SSANumber);
	if (this->OpType == NUMERIC)
		msg("N ");
	else if (this->OpType == CODEPTR)
		msg("C ");
	else if (this->OpType == POINTER)
		msg("P ");
	else if (this->OpType == STACKPTR)
		msg("S ");
	else if (this->OpType == GLOBALPTR)
		msg("G ");
	else if (this->OpType == HEAPPTR)
		msg("H ");
	else if (this->OpType == PTROFFSET)
		msg("O ");
	else if (this->OpType == UNKNOWN)
		msg("U ");
	// Don't write anything for UNINIT OpType
	return;
} // end of DefOrUse::Dump()

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

// Default constructor.
DefOrUseSet::DefOrUseSet(void) {
	return;
}

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

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

// 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;
}

// Change the operand type for a reference.
set<DefOrUse, LessDefUse>::iterator DefOrUseSet::SetType(op_t CurrOp, SMPOperandType Type) {
	// 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()) {
			msg("ERROR: Changing type of immediate from %d to %d : ", CurrRef->GetType(), Type);
			CurrRef->Dump();
			msg("\n");
		}
	}
#endif
	DefOrUse NewCopy = (*CurrRef);
	NewCopy.SetType(Type);
	this->Refs.erase(CurrRef);
	pair<set<DefOrUse, LessDefUse>::iterator, bool> InsertResult;
	InsertResult = this->Refs.insert(NewCopy);
	assert(InsertResult.second);
	CurrRef = InsertResult.first;
	return CurrRef;
}

// 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?
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) {
	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) {
	this->Refs[index].SetType(Type);
	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;
	return;
}

// 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) {
	this->DefName.SetType(Type);
	return;
}

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

// 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.push_back(BADADDR);
	return;
}

SMPDefUseChain::SMPDefUseChain(op_t Name, ea_t Def) {
	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->RefInstrs.push_back(Def);
	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] = Def;
	return;
}

// Push a USE onto the list
void SMPDefUseChain::PushUse(ea_t Use) {
	this->RefInstrs.push_back(Use);
	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;
	return;
}

SMPDUChainArray::SMPDUChainArray(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;
}

void SMPDUChainArray::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;
}

// DEBUG dump.
void SMPDUChainArray::Dump(void) {
	size_t index;
	for (index = 0; index < this->DUChains.size(); ++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()

// 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] = false;               // 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_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_shl] = false;                 // Shift Logical Left
SMPDefsFlags[NN_shr] = false;                 // 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)