SMPFunction.cpp

/*
 * SMPFunction.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/
 *
 * Additional copyrights 2010, 2011, 2012, 2013 by Zephyr Software LLC
 * e-mail: {clc,jwd}@zephyr-software.com
 * URL   : http://www.zephyr-software.com/
 *
 */

//
// SMPFunction.cpp
//
// This module performs the fundamental data flow analyses needed for the
//   SMP project (Software Memory Protection) at the function level.
//

using namespace std;

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

#include <cstring>
#include <cstdlib>

#include <pro.h>
#include <assert.h>
#include <ida.hpp>
#include <ua.hpp>
#include <idp.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <intel.hpp>
#include <name.hpp>
#include <struct.hpp>

#include "SMPDBInterface.h"
#include "SMPDataFlowAnalysis.h"
#include "SMPStaticAnalyzer.h"
#include "SMPFunction.h"
#include "SMPBasicBlock.h"
#include "SMPInstr.h"
#include "SMPProgram.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 1
#define SMP_DEBUG_FRAMEFIXUP_VERBOSE 0
#define SMP_DEBUG_DATAFLOW 0
#define SMP_DEBUG_DATAFLOW_VERBOSE 0
#define SMP_DEBUG_TYPE_INFERENCE 0
#define SMP_DEBUG_PROFILED_TYPE_INFERENCE 0
#define SMP_DEBUG_STACK_GRANULARITY 0
#define SMP_DEBUG_FUNC 0
#define SMP_DEBUG_FUNC_SAFETY 1
#define SMP_VERBOSE_DEBUG_FUNC 0
#define SMP_DEBUG_BUILD_RTL 1   // leave this on; serious errors reported
#define SMP_DEBUG_UNINITIALIZED_SSA_NAMES 1
#define SMP_WARN_UNUSED_DEFS 0
#define SMP_DEBUG_SWITCH_TABLE_INFO 0
#define SMP_OPTIMIZE_BLOCK_PROFILING 0
#define SMP_DECLARE_INDIRECT_TARGETS_UNSAFE 1
#define SMP_AUDIT_STACK_POINTER_DELTAS 0
#define SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS 1
#define STARS_AGGRESSIVE_SIGNEDNESS_PROPAGATION 1
#define STARS_BUILD_LOOP_BITSET 1  // Build bitset in this->FuncLoopsByBlock
#define STARS_DEBUG_MEMORY_CORRUPTION 0

// Compute LVA/SSA or not? Turn it off for NICECAP demo on 31-JAN-2008
#define SMP_COMPUTE_LVA_SSA 1

// Compute fine-grained stack boundaries?
#define SMP_COMPUTE_STACK_GRANULARITY 1

// Use conditional type propagation on phi functions
#define SMP_CONDITIONAL_TYPE_PROPAGATION 1

// Kludges to fix IDA Pro 5.2 errors in cc1.ncexe
#define SMP_IDAPRO52_WORKAROUND 0

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

// Set SharedTailChunks to TRUE for entire printf family
//  After we restructure the parent/tail structure of the database, this
//  will go away.
#define KLUDGE_VFPRINTF_FAMILY 1

// Used for binary search by function number in SMPStaticAnalyzer.cpp
//  to trigger debugging output and find which instruction in which
//  function is causing a crash.
bool SMPBinaryDebug = false;

using namespace std;


// helper function to determine if an object is in a vector
template <class T>	
bool vector_exists(const T &item, const vector<T> &vec) {
	for (size_t i = 0; i < vec.size(); ++i) {
		if (vec[i] == item)
			return true;
	}
	return false;
}

// Comparison function for sorting.
bool LocalVarCompare(const LocalVar &LV1, const LocalVar &LV2) {
	return (LV1.offset < LV2.offset);
}

// *****************************************************************
// Class SMPFunction
// *****************************************************************

// Constructor
SMPFunction::SMPFunction(func_t *Info, SMPProgram* pgm) {
	this->Program = pgm;
	this->FuncInfo = *Info;
	this->FirstEA = this->FuncInfo.startEA;
#if 0
	this->FuncName[0] = '\0';
#endif
	this->BlockCount = 0;
	this->LoopCount = 0;
	this->FuncProcessed = false;
	this->UseFP = false;
	this->StaticFunc = false;
	this->LibFunc = false;
	this->HasReturnInst = false;
	this->IndirectCalls = false;
	this->UnresolvedIndirectCalls = false;
	this->IndirectJumps = false;
	this->UnresolvedIndirectJumps = false;
	this->DirectlyRecursive = false;
	this->SharedChunks = false;
	this->UnsharedChunks = false;
	this->CallsAlloca = false;
	this->PushAfterLocalVarAlloc = false;
	this->AnalyzedSP = false;
	this->STARSStackPtrAnalysisPerformed = false;
	this->StackAdjustmentComputed = false;
	this->BuiltRTLs = false;
	this->HasReducibleCFG = true;
#if 1  // default to unsafe
	this->SetFuncSafe(false);
	this->SetSpecFuncSafe(false);
	this->SafeCallee = false;
	this->SpecSafeCallee = false;
#else // default to safe
	this->SafeFunc = true;
	this->SpecSafeFunc = true;
	this->SafeCallee = true;
	this->SpecSafeCallee = true;
#endif
	this->WritesAboveRA = false;
	this->NeedsStackReferent = true;
	this->SpecNeedsStackReferent = true;
	this->HasIndirectWrites = false;
	this->PossibleIndirectCallTarget = false;
	this->PossibleTailCallTarget = false;
	this->OutgoingArgsComputed = false;
	this->GoodLocalVarTable = false;
	this->StackFrameExtendsPastStackTop = false;
	this->SetIsSpeculative(false);
	this->HasHashingCode = false;
	this->TypedDefs = 0;
	this->UntypedDefs = 0;
	this->TypedPhiDefs = 0;
	this->UntypedPhiDefs = 0;
	this->SafeBlocks = 0;
	this->UnsafeBlocks = 0;
	this->Size = 0;

	// The sizes of the three regions of the stack frame other than the
	//  return address are stored in the function structure.
	this->LocalVarsSize = this->FuncInfo.frsize;
	this->CalleeSavedRegsSize = this->FuncInfo.frregs;
	this->IncomingArgsSize = this->FuncInfo.argsize;

	// The return address size can be obtained in a machine independent
	//  way by calling get_frame_retsize(). 
	this->RetAddrSize = get_frame_retsize(this->GetFuncInfo());

	this->OutgoingArgsSize = 0;
	this->LocalVarsAllocInstr = BADADDR;
	this->LocalVarsDeallocInstr = BADADDR;
	this->AllocPointDelta = 0;
	this->MinStackDelta = 0;
	this->MaxStackDelta = 0;
	this->MinStackAccessOffset = 0;
	this->MaxStackAccessLimit = 0;
	this->NetStackDelta = CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA;
	this->PreAllocStackDelta = CALLING_CONVENTION_DEFAULT_PREFRAMEALLOC_STACK_DELTA;
	this->FramePointerStackDelta = 0;
	this->GlobalStackAdjustment = 0;
	this->LocalVarOffsetLimit = 0;
	this->IDAReturnAddressOffset = 0;

	this->ReturnAddrStatus = FUNC_UNKNOWN;

	this->Instrs.clear();
	this->Blocks.clear();
	this->DirectCallTargets.clear();
	this->IndirectCallTargets.clear();
	this->AllCallTargets.clear();
	this->AllCallSources.clear();
	this->InstBlockMap.clear();
	this->RPOBlocks.clear();
	this->IDom.clear();
	this->DomTree.clear();
	this->GlobalNames.clear();
	this->BlocksDefinedIn.clear();
	this->SSACounter.clear();
	this->SSAStack.clear();
	this->LocalVarTable.clear();
	this->StackFrameMap.clear();
	this->FineGrainedStackTable.clear();
	this->SavedRegLoc.clear();
	this->ReturnRegTypes.clear();
	this->LiveOutSet.clear();
	this->KillSet.clear();
	this->GlobalDefAddrBySSA.clear();

	struct FineGrainedInfo TempFG;
	TempFG.SignMiscInfo = 0;
	TempFG.SizeInfo = 0;
	for (int RegIndex = R_ax; RegIndex <= STARS_MD_LAST_SAVED_REG_NUM; ++RegIndex) {
		this->SavedRegLoc.push_back(0); // zero offset means reg not saved
		this->ReturnRegTypes.push_back(UNINIT);
		this->ReturnRegFGInfo.push_back(TempFG);
	}

	return;
} // end of SMPFunction() constructor

SMPFunction::~SMPFunction() {
	list<SMPInstr *>::iterator InstIter;
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		if (NULL != CurrInst) delete CurrInst;
	}

	list<SMPBasicBlock *>::iterator BlockIter;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		SMPBasicBlock *CurrBlock = (*BlockIter);
		if (NULL != CurrBlock) delete CurrBlock;
	}
}

// Get a non-stale pointer to the func_t info for the current function.
func_t *SMPFunction::GetFuncInfo(void) {
	func_t *myPtr = SMP_get_func(this->FirstEA);
	assert(NULL != myPtr);
	return myPtr;
}

// Reset the Processed flags in all blocks to false.
void SMPFunction::ResetProcessedBlocks(void) {
	list<SMPBasicBlock *>::iterator CurrBlock;
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		(*CurrBlock)->SetProcessed(false);
	}
	return;
} // end of SMPFunction::ResetProcessedBlocks()

// Set SCCPVisited flag to false in all blocks
void SMPFunction::ResetSCCPVisitedBlocks(void) {
	list<SMPBasicBlock *>::iterator CurrBlock;
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		(*CurrBlock)->SetSCCPVisited(false);
	}
	return;
} // end of SMPFunction::ResetSCCPVisitedBlocks()

// Return an iterator for the beginning of the LiveInSet. 
set<op_t, LessOp>::iterator SMPFunction::GetFirstLiveIn(void) {
	return this->Blocks.front()->GetFirstLiveIn();
} // end of SMPBasicBlock::GetFirstLiveIn()

// Get termination iterator marker for the LiveIn set.
set<op_t, LessOp>::iterator SMPFunction::GetLastLiveIn(void) {
	return this->Blocks.front()->GetLastLiveIn();
}

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

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

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

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

// Compute LiveOut, Kill sets for function
void SMPFunction::ComputeGlobalSets(void) {
	list<SMPBasicBlock *>::iterator BlockIter;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		SMPBasicBlock *CurrBlock = (*BlockIter);
		set<op_t, LessOp>::iterator LVASetIter;
		pair<set<op_t, LessOp>::iterator, bool> InsertResult;
		for (LVASetIter = CurrBlock->GetFirstVarKill(); LVASetIter != CurrBlock->GetLastVarKill(); ++LVASetIter) {
			op_t KilledOp = (*LVASetIter);
			InsertResult = this->KillSet.insert(KilledOp); // insert will often fail due to duplication, which is expected
		}
		if (CurrBlock->HasReturn()) {
			// LiveOut for return blocks are unioned to make the LiveOut for the function.
			for (LVASetIter = CurrBlock->GetFirstLiveOut(); LVASetIter != CurrBlock->GetLastLiveOut(); ++LVASetIter) {
				op_t LiveOutOp = (*LVASetIter);
				InsertResult = this->LiveOutSet.insert(LiveOutOp); // insert will often fail due to duplication, which is expected
			}
		}
	}
	return;
} // end of SMPFunction::ComputeGlobalSets()

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

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

unsigned short SMPFunction::GetStackDefSignMiscInfo(ea_t InstAddr) {
	map<ea_t, struct FineGrainedInfo>::iterator MapIter;

	MapIter = this->StackDefFGInfo.find(InstAddr);
	assert(MapIter != this->StackDefFGInfo.end());

	return MapIter->second.SignMiscInfo;
}

unsigned short SMPFunction::GetUseSignMiscInfo(int UseHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;

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

unsigned short SMPFunction::GetStackUseSignMiscInfo(ea_t InstAddr) {
	map<ea_t, struct FineGrainedInfo>::iterator MapIter;

	MapIter = this->StackUseFGInfo.find(InstAddr);
	assert(MapIter != this->StackUseFGInfo.end());

	return MapIter->second.SignMiscInfo;
}

unsigned short SMPFunction::GetDefWidthTypeInfo(int DefHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;

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

unsigned short SMPFunction::GetUseWidthTypeInfo(int UseHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;

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

struct FineGrainedInfo SMPFunction::GetDefFGInfo(int DefHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;

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

struct FineGrainedInfo SMPFunction::GetUseFGInfo(int UseHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;

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

// Add a caller to the list of all callers of this function.
void SMPFunction::AddCallSource(ea_t addr) {
	// Convert call instruction address to beginning address of the caller.
	func_t *FuncInfo = SMP_get_func(addr);
	if (NULL == FuncInfo) {
		SMP_msg("SERIOUS WARNING: Call location %lx not in a function.\n", (unsigned long) addr);
		return;
	}
	ea_t FirstAddr = FuncInfo->startEA;
	assert(BADADDR != FirstAddr);
	this->AllCallSources.insert(FirstAddr);
	this->AllCallSites.insert(addr);
	return;
} // end of SMPFunction::AddCallSource()

// add map entry to LeaInstOpMap
void SMPFunction::AddLeaOperand(ea_t addr, op_t LeaOperand) {
	pair<ea_t, op_t> InsertValue(addr, LeaOperand);
	pair<map<ea_t, op_t>::iterator, bool> InsertResult;
	InsertResult = this->LeaInstOpMap.insert(InsertValue);
	if (!(InsertResult.second)) { // already existed; replace
		map<ea_t, op_t>::iterator FindIter = this->LeaInstOpMap.find(addr);
		assert(FindIter != this->LeaInstOpMap.end());
		FindIter->second = LeaOperand;
	}
	return;
}

// Add input arguments to the NormalizedStackOpsMap.
void SMPFunction::AddNormalizedStackOperand(op_t OldOp, ea_t InstAddr, op_t NormalizedOp) {
	bool DuplicateCase = false; // e.g. inc [esp+8] will have [esp+8] as a DEF and a USE and maps will see [esp+8] twice
	bool DebugFlag = (InstAddr == 0xb79b);
	pair<map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator, bool> InsertResult;
	pair<map<pair<op_t, ea_t>, map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator, LessDefinition>::iterator, bool> InverseInsertResult;
	pair<op_t, ea_t> OldValue(OldOp, InstAddr);
	pair<op_t, ea_t> InverseValue(OldOp, InstAddr); // OldOp was NormalizedOp when it was inserted previously
	pair<pair<op_t, ea_t>, op_t> InsertValue(OldValue, NormalizedOp);
	pair<op_t, ea_t> InverseInsertValue(NormalizedOp, InstAddr);
	map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator OldIter = this->NormalizedStackOpsMap.begin();
	pair<pair<op_t, ea_t>, map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator> InverseInsertTriple(InverseInsertValue, OldIter);
	map<pair<op_t, ea_t>, map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator>::iterator InverseIter;

	// If this function calls alloca(), stack operands could be normalized more than once.
	//  Before we proceed, we update an old entry instead of inserting a new entry.
	if (this->CallsAlloca || this->HasPushAfterFrameAlloc()) {
		InverseIter = this->InverseNormalizedStackOpsMap.find(InverseValue);
		if (InverseIter != this->InverseNormalizedStackOpsMap.end()) {
			// We have our alloca() update case. We formerly mapped <A, InstAddr> to B.
			//  Now B is being normalized to C. All we want to do is change the original
			//  map entry so that we map <A, InstAddr> to C. In this manner, A is always the
			//  original un-normalized stack op, available for lookup from an RTL.
			OldIter = InverseIter->second; // OldIter points at map of <A, InstAddr> to B.
			OldIter->second = NormalizedOp; // Change B to C
			// Now we want to erase the Inverse map entry and insert a new one that maps
			//  <C, InstAddr> to OldIter instead of mapping <B, InstAddr> to OldIter.
			(void) this->InverseNormalizedStackOpsMap.erase(InverseIter);
			InverseInsertTriple.second = OldIter;
			InverseInsertResult = this->InverseNormalizedStackOpsMap.insert(InverseInsertTriple);
			assert(InverseInsertResult.second);
			return;
		}
		else {
			// We might have the final difficult case: We have a combination of CallsAlloca and the
			//  DuplicateCase described below (e.g. an increment of a stack location produces a DEF
			//  and a USE of the same location, causing duplicate mappings to be attempted). We need
			//  to detect the duplicate case here. What will happen is that, on the first call to this
			//  method, we will map <A, InstAddr> to B, and reverse-map <B, InstAddr> to A. On the second
			//  call to this method, we will detect the duplicate case and exit. On the third call, caused
			//  by CallsAlloca, we are asked to map <B, InstAddr> to C, and we will correctly hit the code
			//  just above, in the if-clause, to fix the A->B mapping to be an A->C mapping, and we will
			//  erase the reverse mapping of B->A and replace it with the C->A reverse mapping. On the
			//  fourth call to this method, we will not find a reverse mapping B->A any more, so the if-clause
			//  does not execute. We can only detect this case by finding an existing C->A reverse mapping
			//  and an existing A->C mapping to confirm our inference.
			pair<op_t, ea_t> TestInverseValue(NormalizedOp, InstAddr);
			InverseIter = this->InverseNormalizedStackOpsMap.find(TestInverseValue);
			if (InverseIter != this->InverseNormalizedStackOpsMap.end()) {
				// Found existing C->A inverse mapping. Is there an A->C mapping to confirm
				//  our interpretation of the situation?
				pair<op_t, ea_t> TestOldValue(InverseIter->second->first.first, InstAddr);
				map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator TestOldIter;
				TestOldIter = this->NormalizedStackOpsMap.find(TestOldValue);
				if (TestOldIter != this->NormalizedStackOpsMap.end()) {
					// We found a mapping from <A, InstAddr>.
					if (IsEqOp(NormalizedOp, TestOldIter->second)) {
						// The mapping is A->C as suspected.
						return; // duplication; nothing to do in either map.
					}
				}
			}
		}
	}
	// At this point, we have no inverse map entry to worry about, because we are
	//  normalizing this operand for the first time.
	InsertResult = this->NormalizedStackOpsMap.insert(InsertValue);
	OldIter = InsertResult.first;
	if (!(InsertResult.second)) {
		// Already had an entry. That should mean a rare case such as "inc [esp+8]" which
		//  produces a USE and a DEF of the same address. We can confirm that the map has
		//  the same normalized operand we were trying to insert. Otherwise, the collision
		//  is fatal.
		op_t OldOldOp = InsertResult.first->first.first;
		op_t OldNormalizedOp = InsertResult.first->second;
		assert(IsEqOp(OldOldOp, OldOp) && IsEqOp(OldNormalizedOp, NormalizedOp));
		DuplicateCase = true;
	}
	if (this->CallsAlloca || this->HasPushAfterFrameAlloc()) {
		// We need to add an entry to the inverse map.
		InverseInsertTriple.second = OldIter;
		InverseInsertResult = this->InverseNormalizedStackOpsMap.insert(InverseInsertTriple);
		assert(InverseInsertResult.second || DuplicateCase);
	}
	if (DebugFlag) {
		map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator StackMapIter;
		SMP_msg("DEBUG: NormalizedStackOpsMap size: %zd\n", this->NormalizedStackOpsMap.size());
		for (StackMapIter = this->NormalizedStackOpsMap.begin(); StackMapIter != this->NormalizedStackOpsMap.end(); ++ StackMapIter) {
			op_t OldOp = StackMapIter->first.first;
			ea_t InstAddr = StackMapIter->first.second;
			SMP_msg("DEBUG: NormalizedStackOps: ");
			PrintOperand(OldOp);
			SMP_msg(" addr: %lx\n", (unsigned long) InstAddr);
		}
	}
	return;
} // SMPFunction::AddNormalizedStackOperand()

// Insert SCCP value for global name; change old entry if already found.
map<int, struct STARS_SCCP_Const_Struct>::iterator SMPFunction::InsertGlobalConstValue(int DefHashValue, struct STARS_SCCP_Const_Struct NewConstEntry) {
	map<int, struct STARS_SCCP_Const_Struct>::iterator MapIter = this->FindConstValue(DefHashValue);
	if (MapIter == this->GetLastConstValueIter()) { // no old entry; insert
		pair<int, struct STARS_SCCP_Const_Struct> InsertPair(DefHashValue, NewConstEntry);
		pair<map<int, struct STARS_SCCP_Const_Struct>::iterator, bool> InsertResult = this->ConstantDefs.insert(InsertPair);
		assert(InsertResult.second);
		MapIter = InsertResult.first;
	}
	else { // old entry found; update
		MapIter->second = NewConstEntry;
	}
	return MapIter;
} // end of SMPFunction::InsertGlobalConstValue()


// Return RTLop if not stack opnd; return normalized RTLop otherwise.
op_t SMPFunction::GetNormalizedOperand(ea_t InstAddr, op_t RTLop) {
	op_t NormOp;
	bool DebugFlag = (0xb79b == InstAddr);
	if (DebugFlag) {
		map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator StackMapIter;
		SMP_msg("DEBUG: NormalizedStackOpsMap size: %zd\n", this->NormalizedStackOpsMap.size());
		for (StackMapIter = this->NormalizedStackOpsMap.begin(); StackMapIter != this->NormalizedStackOpsMap.end(); ++ StackMapIter) {
			op_t OldOp = StackMapIter->first.first;
			ea_t InstAddr = StackMapIter->first.second;
			SMP_msg("DEBUG: NormalizedStackOps: ");
			PrintOperand(OldOp);
			SMP_msg(" addr: %lx\n", (unsigned long) InstAddr);
		}
	}
	if (MDIsStackAccessOpnd(RTLop, this->UsesFramePointer())) {
		pair<op_t, ea_t> OldDefn(RTLop, InstAddr);
		map<pair<op_t, ea_t>, op_t, LessDefinition>::iterator FindIter = this->NormalizedStackOpsMap.find(OldDefn);
		assert(this->NormalizedStackOpsMap.end() != FindIter);
		NormOp = FindIter->second;
	}
	else {
		NormOp = RTLop;
	}
	return NormOp;
} // end of SMPFunction::GetNormalizedOperand()


// Eight methods to set values into the maps of global reg/stack/SSA to FG info.
//  For local names, see corresponding methods in SMPBasicBlock.
void SMPFunction::UpdateDefSignMiscInfo(int DefHashValue, unsigned short NewInfo) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
	if (MapIter == this->GlobalDefFGInfoBySSA.end()) {
		// Not found; insert first.
		struct FineGrainedInfo NewFGInfo;
		NewFGInfo.SignMiscInfo = NewInfo;
		NewFGInfo.SizeInfo = 0;
		pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFGInfo);
		MapResult = this->GlobalDefFGInfoBySSA.insert(MapItem);
		assert(MapResult.second); // Was not previously found, insertion must work.
	}
	else { // found; just OR in the new bits.
		MapIter->second.SignMiscInfo |= NewInfo;
	}

	return;
} // end of SMPFunction::UpdateDefSignMiscInfo()

void SMPFunction::UpdateStackDefSignMiscInfo(ea_t InstAddr, unsigned short NewInfo) {
	map<ea_t, struct FineGrainedInfo>::iterator MapIter;

	MapIter = this->StackDefFGInfo.find(InstAddr);
	assert(MapIter != this->StackDefFGInfo.end());
	// found; just OR in the new bits.
	MapIter->second.SignMiscInfo |= NewInfo;

	return;
} // end of SMPFunction::UpdateStackDefSignMiscInfo()

void SMPFunction::UpdateUseSignMiscInfo(int UseHashValue, unsigned short NewInfo) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
	if (MapIter == this->GlobalUseFGInfoBySSA.end()) {
		// Not found; insert first.
		struct FineGrainedInfo NewFGInfo;
		NewFGInfo.SignMiscInfo = NewInfo;
		NewFGInfo.SizeInfo = 0;
		pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFGInfo);
		MapResult = this->GlobalUseFGInfoBySSA.insert(MapItem);
		assert(MapResult.second); // Was not previously found, insertion must work.
	}
	else { // found; just OR in the new bits.
		MapIter->second.SignMiscInfo |= NewInfo;
	}

	return;
} // end of SMPFunction::UpdateUseSignMiscInfo()

void SMPFunction::UpdateStackUseSignMiscInfo(ea_t InstAddr, unsigned short NewInfo) {
	map<ea_t, struct FineGrainedInfo>::iterator MapIter;

	MapIter = this->StackUseFGInfo.find(InstAddr);
	assert(MapIter != this->StackUseFGInfo.end());
	// found; just OR in the new bits.
	MapIter->second.SignMiscInfo |= NewInfo;

	return;
} // end of SMPFunction::UpdateStackUseSignMiscInfo()

void SMPFunction::UpdateDefWidthTypeInfo(int DefHashValue, unsigned short NewInfo) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
	if (MapIter == this->GlobalDefFGInfoBySSA.end()) {
		// Not found; insert first.
		struct FineGrainedInfo NewFGInfo;
		NewFGInfo.SignMiscInfo = 0;
		NewFGInfo.SizeInfo = NewInfo;
		pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFGInfo);
		MapResult = this->GlobalDefFGInfoBySSA.insert(MapItem);
		assert(MapResult.second); // Was not previously found, insertion must work.
	}
	else { // found; just OR in the new bits.
		MapIter->second.SizeInfo |= NewInfo;
	}

	return;
} // end of SMPFunction::UpdateDefWidthTypeInfo()

void SMPFunction::UpdateUseWidthTypeInfo(int UseHashValue, unsigned short NewInfo) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
	if (MapIter == this->GlobalUseFGInfoBySSA.end()) {
		// Not found; insert first.
		struct FineGrainedInfo NewFGInfo;
		NewFGInfo.SignMiscInfo = 0;
		NewFGInfo.SizeInfo = NewInfo;
		pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFGInfo);
		MapResult = this->GlobalUseFGInfoBySSA.insert(MapItem);
		assert(MapResult.second); // Was not previously found, insertion must work.
	}
	else { // found; just OR in the new bits.
		MapIter->second.SizeInfo |= NewInfo;
	}

	return;
} // end of SMPFunction::UpdateUseWidthTypeInfo()

void SMPFunction::UpdateDefFGInfo(int DefHashValue, struct FineGrainedInfo NewFG) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
	if (MapIter == this->GlobalDefFGInfoBySSA.end()) {
		// Not found; insert it.
		pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFG);
		MapResult = this->GlobalDefFGInfoBySSA.insert(MapItem);
		assert(MapResult.second); // Was not previously found, insertion must work.
	}
	else { // found; just put in the new bits.
		MapIter->second.SignMiscInfo |= NewFG.SignMiscInfo;
		MapIter->second.SizeInfo |= NewFG.SizeInfo;
	}

	return;
} // end of SMPFunction::UpdateDefFGInfo()

void SMPFunction::UpdateUseFGInfo(int UseHashValue, struct FineGrainedInfo NewFG) {
	map<int, struct FineGrainedInfo>::iterator MapIter;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	MapIter = this->GlobalUseFGInfoBySSA.find(UseHashValue);
	if (MapIter == this->GlobalUseFGInfoBySSA.end()) {
		// Not found; insert it.
		pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFG);
		MapResult = this->GlobalUseFGInfoBySSA.insert(MapItem);
		assert(MapResult.second); // Was not previously found, insertion must work.
	}
	else { // found; just put in the new bits.
		MapIter->second.SignMiscInfo |= NewFG.SignMiscInfo;
		MapIter->second.SizeInfo |= NewFG.SizeInfo;
	}

	return;
} // end of SMPFunction::UpdateUseFGInfo()

// Reset the signedness bits to zero for DEF.
void SMPFunction::ClearDefSignedness(int DefHashValue) {
	map<int, struct FineGrainedInfo>::iterator MapIter;

	MapIter = this->GlobalDefFGInfoBySSA.find(DefHashValue);
	if (MapIter != this->GlobalDefFGInfoBySSA.end()) {
		MapIter->second.SignMiscInfo &= (~FG_MASK_SIGNEDNESS_BITS);
	}
	return;
} // end of SMPFunction::ClearDefSignedness()

// Erase a range of instructions from the Instrs list, usually corresponding
//  the the range of a basic block.
void SMPFunction::EraseInstRange(ea_t FirstAddr, ea_t LastAddr) {
	list<SMPInstr *>::iterator InstIter = this->Instrs.begin();
	SMPInstr *CurrInst;
	ea_t InstAddr;

	while (InstIter != this->Instrs.end()) {
		CurrInst = (*InstIter);
		InstAddr = CurrInst->GetAddr();
		if ((InstAddr >= FirstAddr) && (InstAddr <= LastAddr)) {
			InstIter = this->Instrs.erase(InstIter);
		}
		else {
			++InstIter;
		}
	}
} // end of SMPFunction::EraseInstRange()

// For instruction address UseAddr, compute the reaching defs for operand TempOp,
//  placing them into the TempReachingDefs list.
void SMPFunction::ComputeTempReachingDefs(op_t TempOp, ea_t UseAddr) {
	this->TempReachingDefs.clear();
	SMPBasicBlock *CurrBlock = this->GetBlockFromInstAddr(UseAddr);
	assert(NULL != CurrBlock);
	set<pair<op_t, ea_t>, LessDefinition>::iterator ReachesInIter;
	pair<set<ea_t, LessAddr>::iterator, bool> InsertResult;

	// Start with the matching members of the ReachesIn set for the current basic block.
	for (ReachesInIter = CurrBlock->GetFirstReachesIn(); ReachesInIter != CurrBlock->GetLastReachesIn(); ++ReachesInIter) {
		pair<op_t, ea_t> ReachesInDef = *ReachesInIter;
		if (IsEqOp(TempOp, ReachesInDef.first)) {
			InsertResult = this->TempReachingDefs.insert(ReachesInDef.second);
			assert(InsertResult.second);
		}
	}

	// Now, see if any def in the block hides the ReachesIn defs before we get to UseAddr.
	vector<SMPInstr *>::iterator InstIter;
	for (InstIter = CurrBlock->GetFirstInst(); InstIter != CurrBlock->GetLastInst(); ++InstIter) {
		SMPInstr *CurrInst = *InstIter;
		ea_t InstAddr = CurrInst->GetAddr();
		if (InstAddr >= UseAddr)
			break;
		set<DefOrUse, LessDefUse>::iterator DefIter = CurrInst->FindDef(TempOp);
		if (DefIter != CurrInst->GetLastDef()) {
			// Found a def. All previous defs are hidden from UseAddr by this def.
			this->TempReachingDefs.clear();
			InsertResult = this->TempReachingDefs.insert(InstAddr);
			assert(InsertResult.second);
		}
	}
	return;
} // end of SMPFunction::ComputeTempReachingDefs()

// Find all the saved stack deltas (if any) for the def addrs in the TempReachesDefs list for TempOp.
//  Put the entries matching TempOp into TempStackDeltaReachesList.
void SMPFunction::ComputeTempStackDeltaReachesList(op_t TempOp) {
	bool FoundOperand = false;
	set<pair<op_t, pair<ea_t, sval_t> >, LessStackDeltaCopy>::iterator CopyIter;
	this->TempStackDeltaReachesList.clear();
	for (CopyIter = this->StackPtrCopySet.begin(); CopyIter != this->StackPtrCopySet.end(); ++CopyIter) {
		pair<op_t, pair<ea_t, sval_t> > CopyEntry = *CopyIter;
		if (IsEqOp(TempOp, CopyEntry.first)) {
			set<ea_t, LessAddr>::iterator FindReachDefIter;
			FoundOperand = true; // help us save time later by exiting loop
			// Match address at which stack ptr copy was made to a reaching def address for TempOp.
			FindReachDefIter = this->TempReachingDefs.find(CopyEntry.second.first);
			if (FindReachDefIter != this->TempReachingDefs.end()) {
				// Found a StackPtrCopySet entry for TempOp, AND we found the DefAddr
				//  in the TempReachingDefs set. 
				this->TempStackDeltaReachesList.push_back(CopyEntry.second); // push back a pair<ea_t, sval_t>
			}
		}
		else if (FoundOperand) {
			// We have found the operand, but have now moved past it in the iteration of StackPtrCopySet.
			//  Save time by exiting the loop.
			break;
		}
	}
	return;
} // end of SMPFunction::ComputeTempStackDeltaReachesList()

// Find the largest stack delta in the TempStackDeltaReachesList.
// Return true if only one value was found in the list.
bool SMPFunction::FindReachingStackDelta(sval_t &StackDelta) {
	bool UniqueDelta = true;

	if (this->TempStackDeltaReachesList.empty()) {
		StackDelta = 0;
		return false;
	}
	else {
		StackDelta = this->TempStackDeltaReachesList.front().second;
	}

	list<pair<ea_t, sval_t> >::iterator DeltaIter;
	for (DeltaIter = this->TempStackDeltaReachesList.begin(); DeltaIter != this->TempStackDeltaReachesList.end(); ++DeltaIter) {
		sval_t NewDelta = DeltaIter->second;
		if (NewDelta != StackDelta) {
			UniqueDelta = false;
			if (NewDelta > StackDelta) {
				StackDelta = NewDelta;
			}
		}
	}
	return UniqueDelta;
} // end of SMPFunction::FindReachingStackDelta()

// Find any apparent stack adjustment after the call instruction at CallAddr,
//  confining our search to the basic block containing CallAddr.
sval_t SMPFunction::GetStackAdjustmentForCallee(ea_t CallAddr) {
	sval_t CalleeAdjustment = 0;

	SMPBasicBlock *CallBlock = this->GetBlockFromInstAddr(CallAddr);
	assert(NULL != CallBlock);
	sval_t BlockAnalysisDelta = CallBlock->ComputeStackAdjustmentAfterCall(CallAddr);
	if (0 != BlockAnalysisDelta) {
		CalleeAdjustment = BlockAnalysisDelta;
		SMP_msg("INFO: Block analysis produced callee adjustment of %ld bytes after %lx\n", 
			(long) CalleeAdjustment, (unsigned long) CallAddr);
	}

	return CalleeAdjustment;
} // end of SMPFunction::GetStackAdjustmentForCallee()

// Get stack delta from a callee function that is unable to provide the info from
//  its own analyses (e.g. analyses failed or have not been performed yet, due to
//  a mutually recursive clique in the call graph). We have three approaches in
//  this case: Use a default value, consult IDA Pro's analyses, or see if we can
//  detect a stack adjustment after the call instruction, from which we could infer
//  the stack delta of the callee. We choose the latter approach, and find the smallest
//  adjustment among all call sites for the callee.
sval_t SMPFunction::GetStackDeltaForCallee(ea_t CallTargetAddr) {
	sval_t CalleeDelta = CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA;

	SMPFunction *CalleeFunc = this->GetProg()->FindFunction(CallTargetAddr);
	if (NULL != CalleeFunc) {
		sval_t GlobalAdjustment = CalleeFunc->ComputeGlobalStackAdjustment();
		if (0 != GlobalAdjustment) {
			CalleeDelta -= GlobalAdjustment;
			SMP_msg("INFO: Global stack adjustment analysis produced callee delta of %ld bytes after %lx\n",
				(long) CalleeDelta, (unsigned long) CallTargetAddr);
		}
	}

	return CalleeDelta;
} // end of SMPFunction::GetStackDeltaForCallee()

// Compute a consistent (or smallest) stack adjustment seen program-wide after all calls to the current function.
//  Do not return a non-zero value unless more than one call site can be used as evidence.
sval_t SMPFunction::ComputeGlobalStackAdjustment(void) {
	bool FoundZeroAdjustment = false;
	sval_t GlobalAdjustment = 0;
	sval_t NegativeAdjustment = -10000; // record negative adjustments detected
	sval_t PositiveAdjustment = 10000; // record positive adjustments detected
	size_t NumCallSites = this->AllCallSites.size();

	// Use cached value if already computed.
	if (this->StackAdjustmentComputed) {
		return this->GlobalStackAdjustment;
	}

	if (1 < NumCallSites) { // if only one call site, it is dangerous to draw conclusions about seeming "adjustments."
		set<ea_t>::iterator CallSiteIter;
		for (CallSiteIter = this->AllCallSites.begin(); CallSiteIter != this->AllCallSites.end(); ++CallSiteIter) {
			ea_t CallSiteAddr = (*CallSiteIter);
			func_t *CurrFunc = SMP_get_func(CallSiteAddr);
			assert(NULL != CurrFunc);
			ea_t CallerFirstAddr = CurrFunc->startEA;
			SMPFunction *CallerFunc = this->GetProg()->FindFunction(CallerFirstAddr);
			assert(NULL != CallerFunc);
			sval_t CurrentAdjustment = CallerFunc->GetStackAdjustmentForCallee(CallSiteAddr);
			// See if CurrentAdjustment is a new, lowest positive value for GlobalAdjustment.
			if ((0 < CurrentAdjustment) && (CurrentAdjustment < PositiveAdjustment)) {
				PositiveAdjustment = CurrentAdjustment;
			}
			else if ((0 > CurrentAdjustment) && (CurrentAdjustment > NegativeAdjustment)) {
				NegativeAdjustment = CurrentAdjustment;
			}
			else if (0 == CurrentAdjustment) {
				FoundZeroAdjustment = true;
				break; // Any zero adjustment found invalidates non-zero inferences
			}
		}
	}

	// See if we consistently had positive or negative adjustments
	if (FoundZeroAdjustment) {
		GlobalAdjustment = 0; // cannot be a clear non-zero indication if we found any zeroes
	}
	else if (PositiveAdjustment < 10000) { // found at least one positive adjustment
		if (NegativeAdjustment > -10000) { // found at least one negative adjustment; bad
			GlobalAdjustment = 0; // inconsistent; reset to zero
		}
		else {
			GlobalAdjustment = PositiveAdjustment;
		}
	}
	else if (NegativeAdjustment > -10000) { // found negative but no positive adjustments
		GlobalAdjustment = NegativeAdjustment;
	}
	else { // did not find negative or positive adjustments
		GlobalAdjustment = 0;
	}

	this->StackAdjustmentComputed = true; // signal caching of the value for future speed
	this->GlobalStackAdjustment = GlobalAdjustment; // cache the value
	return GlobalAdjustment;
} // end of SMPFunction::ComputeGlobalStackAdjustment()

// Use IDA Pro stack pointer deltas instead of doing our own analysis.
bool SMPFunction::UseIDAStackPointerDeltas(void) {
	list<SMPInstr *>::iterator InstIter;
	SMPInstr *CurrInst;
#if SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS
	bool IDATraceFlag = (0 == strcmp("do_length", this->GetFuncName()));
#endif

	InstIter = this->Instrs.begin();
#if SMP_USE_SSA_FNOP_MARKER
	++InstIter; // skip marker pseudo-instruction
#endif
	while (InstIter != this->Instrs.end()) {
		CurrInst = *InstIter;
		sval_t IDAProDelta = get_spd(this->GetFuncInfo(), CurrInst->GetAddr());
		CurrInst->SetStackPtrOffset(IDAProDelta);
		++InstIter;
		if (IDATraceFlag) {
			SMP_msg("INFO: IDA Pro stack delta trace: %ld at %lx\n", (long) IDAProDelta, (unsigned long) CurrInst->GetAddr());
		}
	}