SMPBasicBlock.cpp

/*
 * SMPBasicBlock.cpp - Class file for basic block analysis.
 *
 * 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/
 *
 * Additional copyrights 2010, 2011 by Zephyr Software LLC
 * e-mail: {clc,jwd}@zephyr-software.com
 * URL   : http://www.zephyr-software.com/
 *
 */

//
// SMPBasicBlock.cpp
//
// This module performs the fundamental basic block level analyses 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 <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <name.hpp>
#include <intel.hpp>

#include "SMPDBInterface.h"
#include "SMPStaticAnalyzer.h"
#include "SMPDataFlowAnalysis.h"
#include "SMPBasicBlock.h"
#include "SMPInstr.h"
#include "SMPFunction.h"

#define SMP_DEBUG_DATAFLOW 0   // verbose output for setting up SSA/LVA data structures
#define SMP_DEBUG_OPTIMIZATIONS 0    // verbose output for type propagation
#define SMP_VERBOSE_POINTER_REFINEMENT 0 // refining POINTER to HEAPPTR, STACKPTR, etc.
#define SMP_VERBOSE_ALIAS_DETECTION 0  // log message every time alias in DU chain is seen
#define STARS_DETECT_OPTIMIZED_RANGE_CHECK 1 // Detect misleading signedness case
#define STARS_MINIMIZE_UNSIGNED_BRANCH_PROPAGATION 1 // stop propagation at possible mixed-mode arithmetic
#define STARS_AGGRESSIVE_BENIGN_POINTER_ARITHMETIC 1 // subtract then add to POINTER can underflow then overflow benignly

// Basic block number 0 is the top of the CFG lattice.
#define SMP_TOP_BLOCK 0 

// *****************************************************************
// Class SMPBasicBlock
// *****************************************************************

// Constructor
SMPBasicBlock::SMPBasicBlock(SMPFunction *Func, list<SMPInstr *>::iterator First, list<SMPInstr *>::iterator Last) {
	this->FirstAddr = (*First)->GetAddr();
	this->BlockNum = SMP_BLOCKNUM_UNINIT;
	this->LoopHeaderNumber = SMP_BLOCKNUM_UNINIT;
	this->MyFunc = Func;
	this->SetOutgoingStackDelta(0);
#if 0
	this->IncomingStackPtrDelta = 0;
#endif
#if 1
	this->SetProcessed(false);
	this->SetIndirectJump(false);
	this->SetReturns(false);
	this->ResetShared();
	this->SetLiveInStale(true);
	this->SetUnreachableBlock(false);
	this->SetFlagsDeadBeforeFirstKill(false);
	this->SetMaybeAliased(false);
#else
	this->booleans1 = 0;
	this->SetLiveInStale(true);
#endif
	this->booleans2 = 0;

	this->InstVec.clear();
	this->AddrInstMap.clear();
	this->Predecessors.clear();
	this->Successors.clear();
	this->KillSet.clear();
	this->UpExposedSet.clear();
	this->LiveOutSet.clear();
	this->LiveInSet.clear();
	this->DomFrontier.clear();
	this->PhiFunctions.clear();
	this->LocalNames.clear();

	ea_t InstAddr;

	list<SMPInstr *>::iterator InstIter = First;
	SMPInstr *CurrInst;
	size_t VecIndex = this->InstVec.size() - 1;
	while (InstIter != Last) {
		CurrInst = (*InstIter);
		this->InstVec.push_back(CurrInst);
		VecIndex = this->InstVec.size() - 1;
		InstAddr = CurrInst->GetAddr();
		pair<ea_t, size_t> MapItem(InstAddr, VecIndex);
		this->AddrInstMap.insert(MapItem);
		++InstIter;
	}

	// Now process the last instruction.
	CurrInst = (*Last);
	this->InstVec.push_back(CurrInst); // Add last instruction
	InstAddr = CurrInst->GetAddr();
	VecIndex = this->InstVec.size() - 1;
	pair<ea_t, size_t> MapItem2(InstAddr, VecIndex);
	this->AddrInstMap.insert(MapItem2);
	CurrInst->SetTerminatesBlock();

	// Mark first true (non-marker) instruction. Marker is a floating point
	//  no-op at an odd address, 1 byte before actual first address of block.
	InstIter = First;
	CurrInst = (*InstIter);
	if ((CurrInst->IsFloatNop()) && (0 != (0x1 & CurrInst->GetAddr()))) {
		// Floating point no-op at odd address; this is SSA marker instruction.
		++InstIter; // skip to first real instruction
		CurrInst = (*InstIter);
	}
	CurrInst->SetFirstInBlock();
}

// Get address of first instruction in the block.
ea_t SMPBasicBlock::GetFirstAddr(void) const {
	return this->FirstAddr;
}

// Six methods to get values from the maps of global reg/SSA to FG info.
//  For global names, see corresponding methods in SMPFunction.
unsigned short SMPBasicBlock::GetDefSignMiscInfo(int DefHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
	if (MapIter != this->LocalDefFGInfoBySSA.end())
		return MapIter->second.SignMiscInfo;
	else
		return 0;
} // end of SMPBasicBlock::GetDefSignMiscInfo()

unsigned short SMPBasicBlock::GetUseSignMiscInfo(int UseHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
	if (MapIter != this->LocalUseFGInfoBySSA.end())
		return MapIter->second.SignMiscInfo;
	else
		return 0;
} // end of SMPBasicBlock::GetUseSignMiscInfo()

unsigned short SMPBasicBlock::GetDefWidthTypeInfo(int DefHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
	if (MapIter != this->LocalDefFGInfoBySSA.end())
		return MapIter->second.SizeInfo;
	else
		return 0;
} // end of SMPBasicBlock::GetDefWidthTypeInfo()

unsigned short SMPBasicBlock::GetUseWidthTypeInfo(int UseHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
	if (MapIter != this->LocalUseFGInfoBySSA.end())
		return MapIter->second.SizeInfo;
	else
		return 0;
} // end of SMPBasicBlock::GetUseWidthTypeInfo()

struct FineGrainedInfo SMPBasicBlock::GetDefFGInfo(int DefHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
	if (MapIter != this->LocalDefFGInfoBySSA.end())
		return MapIter->second;
	else {
		struct FineGrainedInfo EmptyFG;
		EmptyFG.SignMiscInfo = 0;
		EmptyFG.SizeInfo = 0;
		return EmptyFG;
	}
} // end of SMPBasicBlock::GetDefFGInfo()

struct FineGrainedInfo SMPBasicBlock::GetUseFGInfo(int UseHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
	if (MapIter != this->LocalUseFGInfoBySSA.end())
		return MapIter->second;
	else {
		struct FineGrainedInfo EmptyFG;
		EmptyFG.SignMiscInfo = 0;
		EmptyFG.SizeInfo = 0;
		return EmptyFG;
	}
} // end of SMPBasicBlock::GetUseFGInfo()

bool SMPBasicBlock::IsLocalName(op_t CurrOp) const {
	return (!this->LocalNames.empty()
		&& (this->LocalNames.end() != this->LocalNames.find(CurrOp)));
}

set<op_t, LessOp>::iterator SMPBasicBlock::FindLocalName(op_t FindOp) {
	return this->LocalNames.find(FindOp);
}

// Equality operator for SMPBasicBlock. Key field is address of first instruction.
int SMPBasicBlock::operator==(const SMPBasicBlock &rhs) const {
	if (rhs.GetFirstAddr() != this->FirstAddr)
		return 0;
	else
		return 1;
}

// Link to predecessor block.
void SMPBasicBlock::LinkToPred(SMPBasicBlock *Predecessor) {
	this->Predecessors.push_back(Predecessor);
	return;
}

// Link to successor block.
void SMPBasicBlock::LinkToSucc(SMPBasicBlock *Successor) {
	this->Successors.push_back(Successor);
	return;
}

// See if all predecessors have set their ordering number.
bool SMPBasicBlock::AllPredecessorsNumbered(void) {
	list<SMPBasicBlock *>::iterator CurrPred;
	for (CurrPred = this->Predecessors.begin(); CurrPred != this->Predecessors.end(); ++CurrPred) {
		// Don't count current block, in case we have a one-block loop with this block
		//  as its own predecessor.
		if (**CurrPred == *this)
			continue;
		if ((*CurrPred)->GetNumber() == SMP_BLOCKNUM_UNINIT)
			return false;
	}
	return true;
} // end of SMPBasicBlock::AllPredecessorsNumbered()

// Mark as processed, recurse into successors depth-first.
void SMPBasicBlock::DepthFirstMark(void) {
	if (this->IsProcessed()) {
		return;
	}
	this->SetProcessed(true);
	list<SMPBasicBlock *>::iterator CurrSucc;
	for (CurrSucc = this->Successors.begin(); CurrSucc != this->Successors.end(); ++CurrSucc) {
		(*CurrSucc)->DepthFirstMark();
	}
	return;
} // end of SMPBasicBlock::DepthFirstMark()

// Are all instructions in the block no-ops?
bool SMPBasicBlock::AllNops(void) {
	size_t NopCount = 0;
	size_t GoodCount = 0;  // non-nop instructions
	vector<SMPInstr *>::iterator InstIter;
	for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		if (CurrInst->IsNop()) {
			++NopCount;
		}
		else {
			++GoodCount;
			break;
		}
	}
	return ((0 == GoodCount) && (0 < NopCount));
} // end of SMPBasicBlock::AllNops()

// Analyze basic block and fill data members.
void SMPBasicBlock::Analyze() {
	vector<SMPInstr *>::reverse_iterator RevInstIter = this->GetRevInstBegin();
	SMPInstr *BackInst = (*RevInstIter);
	if (BackInst->GetDataFlowType() == INDIR_JUMP) {
		this->SetIndirectJump(true);
	}
	else if (BackInst->GetDataFlowType() == RETURN) {
		this->SetReturns(true);
	}
} // end of SMPBasicBlock::Analyze()

// DEBUG dump of block
void SMPBasicBlock::Dump(void) {
	SMP_msg("Dump of basic block %d\n", this->BlockNum);
	// Dump dataflow analysis sets and links before dumping instructions.
	list<SMPBasicBlock *>::iterator CurrLink;
	SMP_msg("Predecessors: ");
	if (!this->Predecessors.empty()) {
		for (CurrLink = this->Predecessors.begin(); CurrLink != this->Predecessors.end(); ++CurrLink) {
			SMP_msg("%d ", (*CurrLink)->GetNumber());
		}
	}
	SMP_msg("\n");
	SMP_msg("Successors: ");
	if (!this->Successors.empty()) {
		for (CurrLink = this->Successors.begin(); CurrLink != this->Successors.end(); ++CurrLink) {
			SMP_msg("%d ", (*CurrLink)->GetNumber());
		}
	}
	SMP_msg("\n");
	set<op_t, LessOp>::iterator SetItem;
	SMP_msg("VarKill set: ");
	if (!this->KillSet.empty()) {
		SMP_msg("size: %zu ", this->KillSet.size());
		for (SetItem = this->KillSet.begin(); SetItem != this->KillSet.end(); ++SetItem) {
			PrintListOperand(*SetItem);
		}
	}
	SMP_msg("\n\n");
	SMP_msg("UpExposed set: ");
	if (!this->UpExposedSet.empty()) {
		for (SetItem = this->GetFirstUpExposed(); SetItem != this->GetLastUpExposed(); ++SetItem) {
			PrintListOperand(*SetItem);
		}
	}
	SMP_msg("\n\n");
	SMP_msg("LiveIn set: ");
	if (!this->LiveInSet.empty()) {
		for (SetItem = this->LiveInSet.begin(); SetItem != this->LiveInSet.end(); ++SetItem) {
			PrintListOperand(*SetItem);
		}
	}
	SMP_msg("\n\n");
	SMP_msg("LiveOut set: ");
	if (!this->LiveOutSet.empty()) {
		for (SetItem = this->LiveOutSet.begin(); SetItem != this->LiveOutSet.end(); ++SetItem) {
			PrintListOperand(*SetItem);
		}
	}
	SMP_msg("\n\n");
	SMP_msg("Dominance frontier: ");
	set<int>::iterator DomIter;
	if (!this->DomFrontier.empty()) {
		for (DomIter = this->DomFrontier.begin(); DomIter != this->DomFrontier.end(); ++DomIter) {
			SMP_msg("%d ", *DomIter);
		}
	}
	SMP_msg("\n\n");
	set<SMPPhiFunction, LessPhi>::iterator PhiIter;
	if (!this->PhiFunctions.empty()) {
		for (PhiIter = this->PhiFunctions.begin(); PhiIter != this->PhiFunctions.end(); ++PhiIter) {
			SMP_msg("Phi function for %d : ", PhiIter->GetIndex());
			// Dump out all phi operands
			PhiIter->Dump();
		}
	}
	SMP_msg("\n");

#if STARS_BUILD_DEF_USE_CHAINS
	SMP_msg("DEF-USE chains for block-local names: \n");
	this->LocalDUChains.Dump();

	SMP_msg("\n");
	SMP_msg("DEF-USE chains for block-local use of global names: \n");
	this->GlobalDUChains.Dump();
#endif

	SMP_msg("\n");
	if (this->HasIndirectJump())
		SMP_msg("Has indirect jump. ");
	if (this->HasReturn())
		SMP_msg("Has return. ");
	if (this->IsShared())
		SMP_msg("Is shared tail chunk block. ");
	SMP_msg("\n");

	// Now, dump all the instructions.
	vector<SMPInstr *>::iterator CurrInst;
	for (CurrInst = this->GetFirstInst(); CurrInst != this->GetLastInst(); ++CurrInst) {
		(*CurrInst)->Dump();
	}
	SMP_msg("\n");
	return;
} // end of SMPBasicBlock::Dump()

// Search successors for fall-through block, if any
list<SMPBasicBlock *>::iterator SMPBasicBlock::GetFallThroughSucc(void) {
	list<SMPBasicBlock *>::iterator FallThroughSuccIter = this->GetLastSucc();
	list<SMPBasicBlock *>::iterator SuccIter;
	vector<SMPInstr *>::reverse_iterator LastInstIter = this->GetRevInstBegin();
	SMPInstr *LastInst = (*LastInstIter);
	ea_t LastAddr = LastInst->GetAddr(), AddrDiff = 1000, FirstAddr;
	SMPitype LastDataFlow = LastInst->GetDataFlowType();

	if ((JUMP != LastDataFlow) && (RETURN != LastDataFlow) && (HALT != LastDataFlow)) {
		// Block has fall-through.
		for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
			FirstAddr = (*SuccIter)->GetFirstAddr();
			if (FirstAddr > LastAddr) { // block comes after this block; candidate for fall-through
				ea_t NewAddrDiff = FirstAddr - LastAddr;
				if (NewAddrDiff < AddrDiff) { // better candidate than previous successors
					AddrDiff = NewAddrDiff;
					FallThroughSuccIter = SuccIter;
				}
			}
		}
	}

	return FallThroughSuccIter;
} // end of SMPBasicBlock::GetFallThroughSucc()


// Return true if anything already in the KillSet would kill the operand value.
bool SMPBasicBlock::MDAlreadyKilled(op_t Opnd1) const {
	// We have assembly language operands that can be complex, such as
	//  [ebx + esi*4 + 04h]. If ebx or esi have been killed, then this memory
	//  phrase should be considered killed. We could be even more conservative
	//  with base addresses, declaring an entire array killed whenever its base
	//  address appears in a definition, for example. We will do that if it proves
	//  to be necessary.
	bool FoundInKillSet = (KillSet.end() != KillSet.find(Opnd1));
	bool DirectAccess = false;
	bool StackAccess = false;
	bool UseFP = this->MyFunc->UsesFramePointer();

	switch (Opnd1.type) {
		// Some types are simple to test for equality.
		case o_void:
		case o_reg:
		case o_mem:
		case o_imm:
		case o_far:
		case o_near:
		case o_trreg:
		case o_dbreg:
		case o_crreg:
		case o_fpreg:
		case o_mmxreg:
		case o_xmmreg:
			// Look in KillSet. These simple types should be found there with
			//  no complicated comparisons needed.
			return FoundInKillSet;

		case o_phrase:
		case o_displ:
			StackAccess = MDIsStackAccessOpnd(Opnd1, UseFP);
			if (StackAccess) {
				DirectAccess = !MDIsIndirectMemoryOpnd(Opnd1, UseFP);
			}
			// If found directly in KillSet, return true. Otherwise, see if any registers
			//  used in the memory addressing expression were killed.
			if (FoundInKillSet)
				return true;
			else if (!(DirectAccess && StackAccess)) {
				// Should we add Opnd1 to the KillSet every time we return true below? **!!**
				op_t TempOp = InitOp;
				TempOp.type = o_reg;
				int BaseReg;
				int IndexReg;
				ushort ScaleFactor;
				ea_t displacement;

				MDExtractAddressFields(Opnd1, BaseReg, IndexReg, ScaleFactor, displacement);
			
				if (R_none != BaseReg) {
					TempOp.reg = (ushort) BaseReg;
					if (this->KillSet.end() != this->KillSet.find(TempOp))
						return true;
				}
				if (R_none != IndexReg) { // Cannot have ESP index reg in SIB
					TempOp.reg = (ushort) IndexReg;
					if (this->KillSet.end() != this->KillSet.find(TempOp))
						return true;
				}
			} // end if (FoundInKillSet) ... else ...
			break;
		default:
			SMP_msg("Unknown operand type %d in MDAlreadyKilled, block %d\n", Opnd1.type, this->BlockNum);
	} // end of switch on Opnd1.type

	return false;
} // end of SMPBasicBlock::MDAlreadyKilled()

// Initialize the KilledSet and UpExposedSet for live variable analysis.
void SMPBasicBlock::InitKilledExposed(bool UseFP) {
	// Find all upwardly exposed operands and killed operands in this block.
	vector<SMPInstr *>::iterator CurrIter;
	set<DefOrUse, LessDefUse>::iterator CurrUse, CurrDef;
	for (CurrIter = this->GetFirstInst(); CurrIter != this->GetLastInst(); ++CurrIter) {
		SMPInstr *CurrInst = (*CurrIter);

		// Dataflow equation for upward exposed variables: If a variable has not been
		//  killed yet in this block, starting from the top of the block, and it is used
		//  in the current instruction, then it is upwardly exposed.
		for (CurrUse = CurrInst->GetFirstUse(); CurrUse != CurrInst->GetLastUse(); ++CurrUse) {
			op_t UseOp = CurrUse->GetOp();
			// Only add non-immediate operands that are not already killed in this block.
			//  o_near and o_far operands are code addresses in immediate form, e.g.
			//  call _printf might be call 0x8048040, with o_near = 0x8048040.
			if ((!(this->MDAlreadyKilled(UseOp))) && (MDIsDataFlowOpnd(UseOp, UseFP))) {
				this->AddUpExposed(UseOp);
			}
		}
		// Dataflow equation for killed variables: If a variable is defined in any
		//  instruction in the block, it is killed by this block (i.e. prior definitions
		//  of that variable will not make it through the block).
		for (CurrDef = CurrInst->GetFirstDef(); CurrDef != CurrInst->GetLastDef(); ++CurrDef) {
			op_t DefOp = CurrDef->GetOp();
			if (MDIsDataFlowOpnd(DefOp, UseFP)) {
				this->KillSet.insert(DefOp);
			}
		}
	} // end for all instrs in block
	this->SetLiveInStale(true);  // Would need to compute LiveInSet for first time
	return;
} // end of SMPBasicBlock::InitKilledExposed()

// returns size in bytes
size_t SMPBasicBlock::GetBlockSize(void) {
	vector<SMPInstr *>::reverse_iterator LastInstIter = this->GetRevInstBegin();
	SMPInstr *LastInst = (*LastInstIter);
	size_t BlockSize = LastInst->GetSize() + (size_t)(LastInst->GetAddr() - this->FirstAddr);
	return BlockSize;
} // end of SMPBasicBlock::GetBlockSize()


// Return an iterator for the beginning of the LiveInSet. If the set is stale,
//  recompute it first.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstLiveIn(void) {
	if (this->IsLiveInStale()) {
		// Dataflow equation: A variable is live-in to this block if it
		//  is upwardly exposed from this block, or if it passes through
		//  the block unchanged (i.e. it is not killed and is live out).
		this->LiveInSet.clear();
		set<op_t, LessOp>::iterator OutIter;
		for (OutIter = this->GetFirstUpExposed(); OutIter != this->GetLastUpExposed(); ++OutIter) {
			this->LiveInSet.insert(*OutIter);
		}
		for (OutIter = this->LiveOutSet.begin(); OutIter != this->LiveOutSet.end(); ++OutIter) {
			if (KillSet.end() == this->KillSet.find(*OutIter)) // Found live out but not killed
				this->LiveInSet.insert(*OutIter);
		}
		this->SetLiveInStale(false);
	}
	return this->LiveInSet.begin();
} // end of SMPBasicBlock::GetFirstLiveIn()

// Get termination iterator marker for the LiveIn set, for use by predecessors.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastLiveIn(void) {
	// Does not matter if it is stale or not; end marker is the same
	return this->LiveInSet.end();
}

// Get iterator for the start of the LiveOut set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstLiveOut(void) {
	return this->LiveOutSet.begin();
}

// Get termination iterator marker for the LiveOut set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastLiveOut(void) {
	return this->LiveOutSet.end();
}

// Get iterator for the start of the VarKill set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstVarKill(void) {
	return this->KillSet.begin();
}

// Get termination iterator marker for the VarKill set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastVarKill(void) {
	return this->KillSet.end();
}

// Get iterator for the start of the UpExposed set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstUpExposed(void) {
	return this->UpExposedSet.begin();
}

// Get termination iterator marker for the UpExposed set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastUpExposed(void) {
	return this->UpExposedSet.end();
}

// Get iterator for the start of the LocalNames set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstLocalName(void) {
	return this->LocalNames.begin();
}

// Get termination iterator marker for the LocalNames set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastLocalName(void) {
	return this->LocalNames.end();
}

// Get iterator for the start of the DomFrontier set.
set<int>::iterator SMPBasicBlock::GetFirstDomFrontier(void) {
	return this->DomFrontier.begin();
}

// Get termination iterator marker for the DomFrontier set.
set<int>::iterator SMPBasicBlock::GetLastDomFrontier(void) {
	return this->DomFrontier.end();
}

// Get iterator for first Phi function.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::GetFirstPhi(void) {
	return this->PhiFunctions.begin();
}

// Get termination iterator marker for Phi functions set.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::GetLastPhi(void) {
	return this->PhiFunctions.end();
}

// Find the Phi function that matches the given op_t.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::FindPhi(op_t FindOp) {
	set<SMPPhiFunction, LessPhi>::iterator PhiIter;
	set<op_t, LessOp>::value_compare OpComp = this->LiveOutSet.value_comp(); // LessOp()
	for (PhiIter = this->GetFirstPhi(); PhiIter != this->GetLastPhi(); ++PhiIter) {
		op_t PhiOp = PhiIter->GetPhiRef(0).GetOp();
		if (OpComp(FindOp, PhiOp) || OpComp(PhiOp, FindOp)) {
			// One is less than the other.
			; // do nothing
		}
		else {
			// They are equal.
			return PhiIter;
		}
	}
	// If we exit the loop, we did not find it.
	return this->PhiFunctions.end();
} // end of SMPBasicBlock::FindPhi()

// Get a pointer to the instruction at address InstAddr.
//  Will assert if it does not find the instruction.
SMPInstr *SMPBasicBlock::FindInstr(ea_t InstAddr) {
	SMPInstr *CurrInst;
	map<ea_t, size_t>::iterator MapEntry;

	MapEntry = this->AddrInstMap.find(InstAddr);
	if (MapEntry == this->AddrInstMap.end()) {
		SMP_msg("FATAL ERROR: Failure on AddrInstMap. Size: %zu Addr: %lx \n",
			this->AddrInstMap.size(), (unsigned long) InstAddr);
		SMP_msg("First addr in block: %lx \n", (unsigned long) this->FirstAddr);
	}
	assert(MapEntry != this->AddrInstMap.end());
	CurrInst = this->GetInstFromIndex(MapEntry->second);

	return CurrInst;
} // end of SMPBasicBlock::FindInstr()

// Get an iterator to the instruction at address InstAddr.
//  Will assert if it does not find the instruction.
vector<SMPInstr *>::iterator SMPBasicBlock::GetInstIterFromAddr(ea_t InstAddr) {
#if 1
	size_t VecIndex = this->GetIndexFromInstAddr(InstAddr);
	vector<SMPInstr *>::iterator InstIter(this->InstVec.begin() + VecIndex);
#else

	vector<SMPInstr *>::iterator InstIter;
	for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
		if (InstAddr == (*InstIter)->GetAddr()) {
			break;
		}
	}
	if (InstIter == this->GetLastInst()) {
		SMP_msg("FATAL ERROR: Failure to find Instr. Addr: %x \n", InstAddr);
		SMP_msg("First addr in block: %x \n", this->FirstAddr);
	}
#endif
	assert(InstIter != this->GetLastInst());

	return InstIter;
} // end of SMPBasicBlock::GetInstIterFromAddr()

// Get the InstVec index for the instruction at InstAddr. Assert if not found.
size_t SMPBasicBlock::GetIndexFromInstAddr(ea_t InstAddr) const {
	SMPInstr *CurrInst;
	ea_t CurrAddr;
	size_t VecIndex;
	size_t UpperLimit = this->InstVec.size();
	if (UpperLimit > 10) { // big enough for binary search
		size_t LowerLimit = 0;
		do {
			VecIndex = (LowerLimit + UpperLimit) / 2;
			CurrInst = this->InstVec[VecIndex];
			CurrAddr = CurrInst->GetAddr();
			if (CurrAddr > InstAddr) { // search lower half
				UpperLimit = VecIndex - 1;
			}
			else if (CurrAddr < InstAddr) { // search upper half
				LowerLimit = VecIndex + 1;
			}
		} while ((CurrAddr != InstAddr) && (LowerLimit <= UpperLimit));
	}
	else { // small enough for linear search
		for (VecIndex = 0; VecIndex < UpperLimit; ++VecIndex) {
			CurrInst = this->InstVec[VecIndex];
			CurrAddr = CurrInst->GetAddr();
			if (CurrAddr == InstAddr) {
				break;
			}
		}
	}
	assert((CurrAddr == InstAddr) && (VecIndex < this->InstVec.size()));
	return VecIndex;
} // end of SMPBasicBlock::GetIndexFromInstAddr()

// The predecessor order is used in SSA phi functions. Get the ordinal number
//  of a given block number in the predecessor list.
int SMPBasicBlock::GetPredPosition(int BlockNum) {
	int counter = 0;
	list<SMPBasicBlock *>::iterator PredIter;
	for (PredIter = this->GetFirstPred(); PredIter != this->GetLastPred(); ++PredIter) {
		if (BlockNum == (*PredIter)->GetNumber()) {
			return counter;
		}
		++counter;
	}
	return -1;
}

// Set the DEF iterator from the DefAddr and DefOp. Assert if not found.
set<DefOrUse, LessDefUse>::iterator SMPBasicBlock::GetGlobalDefIterFromDefAddr(op_t DefOp, ea_t DefAddr) {
	map<ea_t, size_t>::iterator MapIter = this->AddrInstMap.find(DefAddr);
	assert(MapIter != this->AddrInstMap.end());
	SMPInstr *DefInst = this->GetInstFromIndex(MapIter->second);
	set<DefOrUse, LessDefUse>::iterator DefIter = DefInst->FindDef(DefOp);
	assert(DefIter != DefInst->GetLastDef());
	return DefIter;
} // end of SMPBasicBlock::GetGlobalDefIterFromDefAddr()

#if 0 // never used
// Given a USE operand and the address of its instr, return DEF using DU chains or Phi func.
set<DefOrUse, LessDefUse>::iterator SMPBasicBlock::GetDefFromOpAddr(op_t UseOp, ea_t InstAddr, int SSANum) {
	ea_t DefAddr;
	SMPInstr *DefInstr;
	set<DefOrUse, LessDefUse>::iterator DefIter;

	if (this->IsLocalName(UseOp)) {
		// Search in the local DU chains.
		unsigned int LocalDUIndex = this->GetLocalDUIndex(UseOp, SSANum);
		DefAddr = this->LocalDUChains.ChainsByName.at(LocalDUIndex).GetDef(SSANum);
		DefInstr = this->FindInstr(DefAddr);
		DefIter = DefInstr->FindDef(UseOp);
		assert(DefIter != DefInstr->GetLastDef());
	}
	else {
		// Global DEF for this SSANum must be in the Phi functions or within a block.
		DefAddr = this->MyFunc->GetGlobalDefAddr(UseOp, SSANum);
		if (DefAddr == BADADDR) { // Could not find it anywhere.
			SMP_msg("ERROR: Failure in GetDefFromOpAddr(): InstAddr %x SSANum %d\n",
					InstAddr, SSANum);
			assert(DefAddr != BADADDR); // kablooey!
		}
		else if (DefAddr < this->MyFunc->GetNumBlocks()) {
			// A block number was returned, not an instruction address.
			//  The DEF for this SSANum is only in a Phi function for that
			//  block number.
			size_t BlockNumber = (size_t) DefAddr;
			set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->MyFunc->GetPhiIterForPhiDef(BlockNumber, UseOp, SSANum);
				// PhiIter is guaranteed to be good, else we assert in GetPhiIterForPhiDef().
			assert(SSANum == PhiIter->GetDefSSANum());
			DefOrUse DefCopy = PhiIter->GetDefCopy();
			DefOrUseSet DummySet;
			DefIter = DummySet.InsertRef(DefCopy);
		}
		else { // Must be a DEF within a block, not in a Phi function.
			// NOTE: We might be looking within the current block with this code; perfectly OK.
			SMPBasicBlock *DefBlock = this->MyFunc->GetBlockFromInstAddr(DefAddr);
			DefIter = DefBlock->GetGlobalDefIterFromDefAddr(UseOp, DefAddr);
		}
	}

	return DefIter;
} // end of SMPBasicBlock::GetDefFromOpAddr()
#endif

#if STARS_BUILD_DEF_USE_CHAINS
// Given a USE operand and the address of its instr, return DEF addr using DU chains or Phi func.
//  If DEF is in a Phi function, we return the block number, which never conflicts with instruction
//   addresses.
ea_t SMPBasicBlock::GetDefAddrFromUseAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName) {
	ea_t DefAddr = BADADDR;
	set<DefOrUse, LessDefUse>::iterator DefIter;
	bool RegisterOp = (o_reg == UseOp.type);

	if (LocalName) {
		// Search in the local DU chains.
		unsigned int LocalDUIndex = this->GetLocalDUIndex(UseOp, SSANum);
		DefAddr = this->GetFirstDefAddr(LocalDUIndex, SSANum, false);
	}
	else if (RegisterOp) {
		// Global DEF for this SSANum must be in the Phi functions or within a block.
		DefAddr = this->MyFunc->GetGlobalDefAddr(UseOp, SSANum);
		if (DefAddr == BADADDR) { // Could not find it anywhere.
			this->GetFunc()->Dump();
			SMP_msg("ERROR: Failure in GetDefAddrFromUseAddr(): InstAddr %x SSANum %d\n",
					InstAddr, SSANum);
			SMP_msg(" LocalName: %d UseOp.reg: %d\n", LocalName, UseOp.reg);
			assert(DefAddr != BADADDR); // kablooey!
		}
	}
	else if (MDIsDirectStackAccessOpnd(UseOp, this->GetFunc()->UsesFramePointer())) {
		// Func->GetGlobalDefAddr() only works on registers. Get stack DefAddr from
		//  Phi functions or DU chains.
		set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->FindPhi(UseOp);
		if (PhiIter != this->GetLastPhi()) {
			// Found a Phi function for UseOp; does it DEF our SSANum?
			int PhiDefSSANum = PhiIter->GetDefSSANum();
			if (PhiDefSSANum == SSANum) {
				return this->BlockNum;  // BlockNum is signal that the Def has no real addr, is in Phi
			}
		}
		unsigned int GlobalDUIndex = this->GetGlobalDUIndex(UseOp, BADADDR);
		size_t chain;
		size_t NumChains = this->GetNumLocalChains(GlobalDUIndex, true);
		ea_t LastAddr;
		for (chain = 0; chain < NumChains; ++chain) {
			LastAddr = this->GetLastUseAddr(GlobalDUIndex, chain, true);
			if (LastAddr >= InstAddr) {
				// Found the chain with InstAddr within it.
				DefAddr = this->GetFirstDefAddr(GlobalDUIndex, chain, true);
				break;
			}
		}
	}

	return DefAddr;
} // end of SMPBasicBlock::GetDefAddrFromUseAddr()

#else

// Given a USE operand and the address of its instr, return DEF addr using SSA chains or Phi func.
//  If DEF is in a Phi function, we return the block number, which (hopefully) never conflicts with instruction
//   addresses.
ea_t SMPBasicBlock::GetDefAddrFromUseAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName) {
	ea_t DefAddr = BADADDR;
	set<DefOrUse, LessDefUse>::iterator DefIter;
	bool RegisterOp = (o_reg == UseOp.type);
	bool PhiUse = (InstAddr < this->GetFunc()->GetNumBlocks());

	if (RegisterOp && (!LocalName)) {
		// Global DEF for this SSANum must be in the Phi functions or within a block.
		DefAddr = this->MyFunc->GetGlobalDefAddr(UseOp, SSANum); // only works on registers
		if (DefAddr == BADADDR) { // Could not find it anywhere.
			this->GetFunc()->Dump();
			SMP_msg("ERROR: Failure in GetDefAddrFromUseAddr(): InstAddr %lx SSANum %d\n",
					(unsigned long) InstAddr, SSANum);
			SMP_msg(" LocalName: %d UseOp.reg: %d\n", LocalName, UseOp.reg);
			assert(DefAddr != BADADDR); // kablooey!
		}
	}
	else if (LocalName || MDIsDirectStackAccessOpnd(UseOp, this->GetFunc()->UsesFramePointer())) {
		if (PhiUse) {
			// Need to find DEF for a PhiUse. Temporarily, we will use the slow linear search method.
			DefAddr = this->GetFunc()->GetGlobalDefAddr(UseOp, SSANum);
			if (BADADDR == DefAddr) { // Need to search Phi functions.
				// Rare case in which a Phi USE was traced only to a Phi DEF in an earlier block.
				DefAddr = (ea_t) this->GetFunc()->GetBlockNumForPhiDef(UseOp, SSANum);
				assert(BADADDR != DefAddr);
			}
		}
		else {
			vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(InstAddr);
			if (this->IsVarKill(UseOp)) { // Cannot find a DEF in block if not in VarKill set for this block
				vector<SMPInstr *>::reverse_iterator RevInstIter(InstIter);
				while (RevInstIter != this->GetRevInstEnd()) {
					SMPInstr *CurrInst = (*RevInstIter);
					set<DefOrUse, LessDefUse>::iterator DefIter = CurrInst->FindDef(UseOp);
					if (DefIter != CurrInst->GetLastDef()) {
						DefAddr = CurrInst->GetAddr();
						assert(SSANum == DefIter->GetSSANum());
						break;
					}
					++RevInstIter;
				}
			}
			if (DefAddr == BADADDR) { // not found yet
				// Must be a global name defined in the Phi functions or LiveIn and UpExposed to the block, or a non-stack mem access.
				bool UseFP = this->GetFunc()->UsesFramePointer();
				assert(!LocalName || (!MDIsDataFlowOpnd(UseOp, UseFP)));
				set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->FindPhi(UseOp);
				if (PhiIter != this->GetLastPhi()) {
					// Found a Phi function for UseOp; does it DEF our SSANum?
					int PhiDefSSANum = PhiIter->GetDefSSANum();
					if (PhiDefSSANum == SSANum) {
						DefAddr = this->BlockNum;  // BlockNum is signal that the Def has no real addr, is in Phi
					}
				}
				else {
					DefAddr = this->GetFirstAddr() - 1; // pseudo-def-addr for LiveIn, not in Phi, UpExposed
				}
			}
		}
	}

	return DefAddr;
} // end of SMPBasicBlock::GetDefAddrFromUseAddr()

#endif

ea_t SMPBasicBlock::GetUltimateDefAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName) {
	ea_t DefAddr = BADADDR;
	DefAddr = this->GetDefAddrFromUseAddr(UseOp, InstAddr, SSANum, LocalName);
	bool LiveInAddr = (DefAddr == (this->GetFirstAddr() - 1));
	if (LiveInAddr && this->IsLiveIn(UseOp)) { // UpExposed or pass-through case
		// We need to find the predecessor block that DEFed the UseOp/SSANum.
		assert(!LocalName); // also cannot be a register; it is a global name stack var

#if 1
		size_t NumBlocks = this->GetFunc()->GetNumBlocks();
		bool FoundDEF = false;
		set<DefOrUse, LessDefUse>::iterator DefIter;
		// Check special case of DEF in marker instruction at beginning of function.
		if (SSANum == 0) {
			SMPInstr *FirstInst = this->GetFunc()->GetInstFromAddr(this->GetFunc()->GetFirstFuncAddr() - 1);
			if (FirstInst->IsFloatNop()) {
				DefIter = FirstInst->FindDef(UseOp);
				if (DefIter != FirstInst->GetLastDef()) {
					assert(0 == DefIter->GetSSANum());
					DefAddr = FirstInst->GetAddr();
					FoundDEF = true;
				}
			}
		}

		for (size_t BlockIndex = 0; (BlockIndex < NumBlocks) && (!FoundDEF); ++BlockIndex) {
			SMPBasicBlock *CurrBlock = this->GetFunc()->GetBlockByNum(BlockIndex);
			// Don't bother to look inside block insts unless UseOp is killed and LiveOut
			if (CurrBlock->IsLiveOut(UseOp)) {
				// Can we match the SSANum in an inst DEF or a Phi DEF?
				set<SMPPhiFunction, LessPhi>::iterator PhiIter = CurrBlock->FindPhi(UseOp);
				if (PhiIter != CurrBlock->GetLastPhi()) {
					if (SSANum == PhiIter->GetDefSSANum()) {
						DefAddr = (ea_t) BlockIndex;
						FoundDEF = true;
						break;
					}
				}
				if (CurrBlock->IsVarKill(UseOp)) {
					vector<SMPInstr *>::reverse_iterator RevInstIter;
					for (RevInstIter = CurrBlock->GetRevInstBegin(); RevInstIter != CurrBlock->GetRevInstEnd(); ++RevInstIter) {
						SMPInstr *CurrInst = (*RevInstIter);
						ea_t CurrAddr = CurrInst->GetAddr();
						if (CurrInst->HasDestMemoryOperand() || CurrInst->MDIsPushInstr()) {
							DefIter = CurrInst->FindDef(UseOp);
							if (DefIter != CurrInst->GetLastDef()) {
								// Because we are using a reverse iterator, the first DEF we encounter either
								//  matches the SSANum or else this block is irrelevant.
								if (SSANum == DefIter->GetSSANum()) {
									DefAddr = CurrAddr;
									FoundDEF = true;
								}
								break; // found it or did not; break regardless
							}
						}
					}
				}
			}
		}
#else
		list<SMPBasicBlock *>::iterator PredIter;
		bool FoundDefiningBlock = false;
		for (PredIter = this->GetFirstPred(); PredIter != this->GetLastPred(); ++PredIter) {
			SMPBasicBlock *PredBlock = (*PredIter);
			if (!PredBlock->IsProcessed() && PredBlock->IsLiveOut(UseOp)) {
				// Found possible defining block. At least one predecessor should have UseOp LiveOut.
				// We can recurse, but we need a pseudo UseAddr. We
				//  will use the last instruction in PredBlock as the pseudo UseAddr, but first
				//  we need to check to see if it is the DefAddr.
				vector<SMPInstr *>::reverse_iterator RevInstIter = PredBlock->GetRevInstBegin();
				SMPInstr *LastPredInst = (*RevInstIter);
				ea_t LastPredAddr = LastPredInst->GetAddr();
				if (LastPredInst->FindDef(UseOp) != LastPredInst->GetLastDef()) {
					DefAddr = LastPredAddr;
					PredBlock->SetProcessed(true);
					FoundDefiningBlock = true;
				}