SMPDataFlowAnalysis.cpp

/*
 * SMPDataFlowAnalysis.cpp - <see below>.
 *
 * Copyright (c) 2000, 2001, 2010 - University of Virginia 
 *
 * This file is part of the Memory Error Detection System (MEDS) infrastructure.
 * This file may be used and modified for non-commercial purposes as long as 
 * all copyright, permission, and nonwarranty notices are preserved.  
 * Redistribution is prohibited without prior written consent from the University 
 * of Virginia.
 *
 * Please contact the authors for restrictions applying to commercial use.
 *
 * THIS SOURCE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author: University of Virginia
 * e-mail: jwd@virginia.com
 * URL   : http://www.cs.virginia.edu/
 *
 */

//
// 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"
#include "SMPInstr.h"
#include "SMPBasicBlock.h"
#include "SMPFunction.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

const 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 = (ushort) sib_scale(MemOp);
		}
		if (R_none != BaseReg) {
			if ((BaseReg == R_bp) && (MemOp.type == o_mem)) {
				BaseReg = R_none;
				// **!!** BaseReg allowed for o_mem with SIB byte???
			}
		}
	}
	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()

// MACHINE DEPENDENT: Is operand a stack memory access?
bool MDIsStackAccessOpnd(op_t CurrOp, bool UseFP) {
	int BaseReg;
	int IndexReg;
	ushort ScaleFactor;
	ea_t offset;

	if ((o_displ != CurrOp.type) && (o_phrase != CurrOp.type)) {
		return false;
	}

	MDExtractAddressFields(CurrOp, BaseReg, IndexReg, ScaleFactor, offset);
	return ((BaseReg == R_sp) || (UseFP && (BaseReg == R_bp)));
} // end of MDIsStackAccessOpnd()

// MACHINE DEPENDENT: Is operand a caller-saved register?
bool MDIsCallerSavedReg(op_t CurrOp) {
	if (o_reg != CurrOp.type)
		return false;
	ushort CurrReg = MDCanonicalizeSubReg(CurrOp.reg);
	return ((R_ax == CurrReg) || (R_cx == CurrReg) || (R_dx == CurrReg));
} // end of MDIsCallerSavedReg()

// 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: %x\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;
}

// Meet function over any two types in the type lattice.
SMPOperandType SMPTypeMeet(SMPOperandType Type1, SMPOperandType Type2) {
	SMPOperandType MeetType = UNKNOWN;
	bool ProfDerived = IsProfDerived(Type1) || IsProfDerived(Type2);
	if (IsEqType(UNINIT, Type1))
		MeetType = Type2;
	else if (IsEqType(UNINIT, Type2) || IsEqType(Type1, Type2)
		|| IsUnknown(Type1))
		MeetType = Type1;
	else if (IsNumeric(Type1)) {
		if (IsNumeric(Type2))  // one is NUMERIC, one is CODEPTR
			MeetType = NUMERIC;
		else if (IsDataPtr(Type2) || IsUnknown(Type2))
			MeetType = UNKNOWN;
	}
	else if (IsDataPtr(Type1)) {
		if (IsDataPtr(Type2))  // two different POINTER subtypes
			MeetType = POINTER;
		else if (IsNumeric(Type2) || IsUnknown(Type2))
			MeetType = UNKNOWN;
	}
	if (ProfDerived && IsNotEqType(UNINIT, MeetType))
		MeetType = MakeProfDerived(MeetType);
	return MeetType;
} // end of SMPTypeMeet()

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

// Default constructor to make the compilers happy.
DefOrUse::DefOrUse(void) {
	this->Operand.type = o_void;
	this->OpType = UNINIT;
	this->NonSpeculativeOpType = UNINIT;
	this->SSANumber = -2;
	this->MetadataStatus = DEF_METADATA_UNANALYZED;
	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;

	assert(!IsProfDerived(Type));
	this->NonSpeculativeOpType = Type;
	this->SSANumber = SSASub;
	this->MetadataStatus = DEF_METADATA_UNANALYZED;
	this->IndWrite = false;
	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;
	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;
}

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

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

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

	// Don't write anything for UNINIT OpType

	// Emit the metadata status.
	if (DEF_METADATA_UNUSED == this->MetadataStatus)
		msg("Mn ");
	else if (DEF_METADATA_USED == this->MetadataStatus)
		msg("Mu ");
	else if (DEF_METADATA_REDUNDANT == this->MetadataStatus)
		msg("Mr ");
	// Is the DEF possibly aliased because of an indirect write in
	//  the DEF-USE chain?
	if (this->IndWrite)
		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(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;
} // 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()

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

// 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(BADADDR);
	this->IndWrite = false;
	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;
}

// 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()