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 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 <allins.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_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_ANALYZE_STACK_POINTER 0
#define SMP_AUDIT_STACK_POINTER_DELTAS 0
#define SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS 1

// 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 0

// 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->FuncProcessed = false;
	this->UseFP = false;
	this->StaticFunc = false;
	this->LibFunc = 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->AnalyzedSP = false;
	this->STARSStackPtrAnalysisPerformed = false;
	this->BuiltRTLs = false;
#if 1  // default to unsafe
	this->SafeFunc = false;
	this->SpecSafeFunc = 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->OutgoingArgsSize = 0;
	this->TypedDefs = 0;
	this->UntypedDefs = 0;
	this->TypedPhiDefs = 0;
	this->UntypedPhiDefs = 0;
	this->SafeBlocks = 0;
	this->UnsafeBlocks = 0;
	this->Size = 0;
	this->LocalVarsSize = 0;
	this->CalleeSavedRegsSize = 0;
	this->RetAddrSize = 0;
	this->IncomingArgsSize = 0;
	this->OutgoingArgsSize = 0;
	this->LocalVarsAllocInstr = BADADDR;
	this->LocalVarsDeallocInstr = BADADDR;
	this->AllocPointDelta = 0;
	this->MinStackDelta = 0;
	this->MaxStackDelta = 0;
	this->NetStackDelta = CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA;
	this->PreAllocStackDelta = CALLING_CONVENTION_DEFAULT_PREFRAMEALLOC_STACK_DELTA;
	this->FramePointerStackDelta = 0;
	this->LocalVarOffsetLimit = 0;

	this->ReturnAddrStatus = FUNC_UNKNOWN;
	this->SetIsSpeculative(false);

	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->LiveInSet.clear();
	this->LiveOutSet.clear();
	this->KillSet.clear();
	this->GlobalDefAddrBySSA.clear();

	for (int RegIndex = R_ax; RegIndex <= R_di; ++RegIndex) {
		this->SavedRegLoc.push_back(0); // zero offset means reg not saved
		this->ReturnRegTypes.push_back(UNINIT);
	}

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

	return;
} // end of SMPFunction() constructor

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

	list<SMPBasicBlock *>::iterator BlockIter;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		SMPBasicBlock *CurrBlock = (*BlockIter);
		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()

// Return an iterator for the beginning of the LiveInSet. 
set<op_t, LessOp>::iterator SMPFunction::GetFirstLiveIn(void) {
	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 SMPFunction::GetLastLiveIn(void) {
	return this->LiveInSet.end();
}

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

// 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;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

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

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

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

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

	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;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	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;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	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;
	pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;

	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 %x not in a function.\n", addr);
		return;
	}
	ea_t FirstAddr = FuncInfo->startEA;
	assert(BADADDR != FirstAddr);
	this->AllCallSources.insert(FirstAddr);
	return;
} // end of SMPFunction::AddCallSource()

// Six methods to set values into the maps of global reg/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::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::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()

// 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.
	list<SMPInstr *>::iterator InstIter;
	for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++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);
		}
	}
	if (this->TempReachingDefs.empty() && (o_reg == TempOp.type)) {
		SMP_msg("WARNING: Use of uninitialized variable at %x ", UseAddr);
		PrintOperand(TempOp);
		SMP_msg(" \n");
	}
	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()

// 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.
sval_t SMPFunction::GetStackDeltaForCallee(ea_t CallAddr) {
	bool success = false;
	sval_t CalleeDelta = CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA;

#if 0
#ifdef STARS_IDA_INTERFACE
	if (this->FuncInfo.flags & (FUNC_SP_READY | FUNC_PURGED_OK)) {
		// FUNC_SP_READY => AnalyzedSP; FUNC_PURGED_OK => analysis of effect on stack succeeded.
		if (this->FuncInfo.argsize != 0) {
		}
	}
#endif // STARS_IDA_INTERFACE
#endif

	SMPBasicBlock *CallBlock = this->GetBlockFromInstAddr(CallAddr);
	sval_t BlockAnalysisDelta = CallBlock->ComputeStackAdjustmentAfterCall(CallAddr);
	if (0 != BlockAnalysisDelta) {
		CalleeDelta -= BlockAnalysisDelta;
		SMP_msg("INFO: Block analysis produced callee delta of %d bytes after %x\n", CalleeDelta, CallAddr);
	}

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

// 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: %d at %x\n", IDAProDelta, CurrInst->GetAddr());
		}
	}
	return true;
} // end of SMPFunction::UseIDAStackPointerDeltas()

// Analyze changes to the stack pointer over all instructions.
bool SMPFunction::AnalyzeStackPointerDeltas(void) {
	list<pair<SMPBasicBlock *, sval_t> > WorkList;
	list<SMPInstr *>::iterator InstIter;
	SMPInstr *CurrInst;
	sval_t CurrentDelta = 0;
	bool ConsistentNetDelta = true; // Net change to stack pointer is consistent at all RETURN locations
	bool ReturnSeen = false;
	bool IDAProSucceeded = this->AnalyzedSP;
	bool FirstBlockProcessed = false;
	bool FPSaved = false; // found save of frame pointer; prelude to initializing it
	bool SPintoFP = false; // found move of stack pointer into frame pointer (FP init)

#if SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS
	bool DebugFlag = (0 == strcmp("find_derivation", this->GetFuncName()));
	bool TraceFlag = (0 == strcmp("_dl_start_profile", this->GetFuncName()));
	bool IDATraceFlag = (0 == strcmp("do_length", this->GetFuncName()));
#endif

#if 1
	// Temporarily pull the functions that call alloca out of the stack pointer delta computations, so
	//  that we can focus on solving other problems.
	if (this->CallsAlloca) {
		if (!this->AnalyzedSP) {
			(void) this->UseIDAStackPointerDeltas();
			return false; // leave it unsolved
		}
		else {
			SMP_msg("INFO: Using IDA Pro stack pointer deltas for alloca-calling function %s .\n", this->GetFuncName());
			return this->UseIDAStackPointerDeltas();
		}
	}
#endif

	// In order to precisely track stack deltas, we need to deal with instruction sequences that save the stack pointer
	//  and then restore it later. This requires a reaching definitions data flow analysis that includes, at a minimum,
	//  all stack definitions (normalized by stack delta, so that we do not confuse [esp+20] and [esp+20] where the values
	//  of esp are not the same). We also need to keep track of stack pointer saves in both registers and in stack locations.
	// In order for the information about saved stack pointer copies to be available as soon as we need them in the stack
	//  delta analysis, we have to perform both stack delta analysis and reaching definitions analysis at the same time. Luckily,
	//  both analyses are well suited to being performed as forward analyses starting from the entry basic block.
	//
	// Data structures for the reaching definitions analysis include a ReachesIn and a ReachesOut set for each basic block, a
	//  VarKill set for each block, and a DownExposedDefs set for each block. The VarKill set is shared with the later Live Variable
	//  Analysis (LVA), so we compute the VarKill and the UpExposed sets (UpExposed is only used by LVA) on the first pass through
	//  each block. The VarKill and all other LVA sets are sets of operands. The ReachesIn, ReachesOut, and DownExposedDefs sets
	//  are sets of definitions, where a definition is a pair<operand, instruction address>. The StackPtrCopySet is a triple of
	//   <operand, instruction address, stack delta>, arranged as a pair of pairs <operand, <addr, delta> >
	//
	// Algorithm: We maintain a WorkList of pairs <basic block pointer, incoming stack delta to that block>
	//
	// All sets are empty at the beginning.
	// Add the entry basic block to the WorkList, with IncomingDelta of zero.
	// while (WorkList is not empty) do
	//    de-queue first block from WorkList, obtain IncomingDelta
	//    Compute ReachesIn as the union of the ReachesOut of all predecesssor blocks
	//    if (block has not already been processed) then
	//       mark block as processed
	//       for each inst in block (forward iteration) do
	//           for each USE in inst do
	//              if USE operand not in VarKill set for block then
	//                  add USE operand to UpExposed set for block
	//              endif
	//              if USE operand is a stack pointer value AND it will produce DEF that is a stack pointer value then
	//                  if DEF is stack pointer register then  { a stack pointer value that was saved is being restored }
	//                      retrieve new stack pointer delta from saved value in StackPtrCopySet, looking it up in
	//                          that set using the reaching definitions for the USE operand. If inconsistent  ******
	//                  else { stack pointer value is being saved somewhere besides the stack pointer register }
	//                      add stack delta to StackPtrCopySet for DEF that is receiving it in current inst
	//                  endif
	//               endif
	//            endfor { each USE }
	//            for each DEF in inst do
	//               if register or stack operand then 
	//                  add to VarKill set
	//                  update DownExposedDefs set (insert, or replace current def for this operand)
	//               endif
	//            endfor { each DEF }
	//            Store IncomingDelta for current instruction
	//            Get change in delta for current instruction
	//            Add current change to IncomingDelta
	//       endfor { each inst }
	//       At end of block, make ReachesOut set be (ReachesIn minus VarKill) union DownExposedDefs
	//       For each successor block, add pairs <block pointer, IncomingDelta> to end of WorkList
	//    else { block has already been processed at least once}
	//       if IncomingDelta from WorkList is inconsistent with old IncomingDelta then
	//          if function calls alloca() then
	//             if new IncomingDelta makes stack frame look larger than old IncomingDelta then
	//                ignore new IncomingDelta and just process reaching definitions sets below
	//             else
	//                use new IncomingDelta and re-process deltas in this block to converge to
	//                 smallest stack frame, which means we are basically ignoring alloca()'s as much as possible.
	//             endif
	//          else
	//             Set AnalyzedSP to false, emit error message, clear WorkList and bail out of this function.
	//          endif
	//       endif { inconsistent IncomingDelta values }
	//       Recompute ReachesIn as union of ReachesOut of all predecessor blocks
	//       if ReachesIn set changed then
	//          recompute ReachesOut without examining instructions unless alloca() case requires iterating through instructions
	//       endif
	//       if any change in deltas or reaching definitions sets, then add block to end of WorkList along with all successor blocks.
	//    endif
	// end while

	// Mark all blocks as unprocessed
	this->ResetProcessedBlocks();

	this->AnalyzedSP = true;

	// Put the entry block on the work list.
	assert(0 < this->Blocks.size());
	pair<SMPBasicBlock *, sval_t> WorkingPair (this->Blocks.front(), CurrentDelta);
	WorkList.push_back(WorkingPair);

	// While blocks exist on the work list
	//  if block already processed, confirm that we are re-entering
	//    the block with the same stack pointer delta as previously,
	//    and pop it off the work list
	//    otherwise declare the stack pointer to be un-analyzeable;
	//  else
	//     iterate through all instructions in the block, analyzing
	//     the stack pointer delta of each inst and accumulating current delta
	//     At the end of the block, put the successor blocks on the work list.
	// For both cases, maintain and update reaching definitions sets, and the
	//  UpExposed and VarKill sets that are used by LVA as well as reaching defs analysis.
	bool ReprocessingAllocaBlocks = false;
	bool ReachesInChanged;
	bool ReachesOutChanged = false;
	do {
		SMPBasicBlock *CurrBlock = WorkList.front().first;
		sval_t IncomingDelta = WorkList.front().second;

		if (CurrBlock->IsProcessed()) { // already processed
			ReachesInChanged = CurrBlock->ComputeReachesInSet();
			ReachesOutChanged = false;
			if (ReachesInChanged) {
				ReachesOutChanged = CurrBlock->ComputeReachesOutSet();
			}
			if (ReachesOutChanged) {
				// Push the successor blocks onto the work list
				sval_t SuccIncomingDelta = CurrBlock->GetOutgoingStackDelta();
				list<SMPBasicBlock *>::iterator SuccIter;
				for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
					pair<SMPBasicBlock *, sval_t> SuccPair (*SuccIter, SuccIncomingDelta);
					WorkList.push_back(SuccPair);
				}
			}
			InstIter = CurrBlock->GetFirstInstr();
			sval_t PrevIncomingDelta = (*InstIter)->GetStackPtrOffset();
			if (IncomingDelta == PrevIncomingDelta) {
				// No error, already processed.
				WorkList.pop_front(); // discard already processed block.
			}
			else if (this->CallsAlloca) {
				// Calls to alloca() become additional stack allocations, which can produce
				//  multiple possible stack deltas for an instruction if different paths
				//  to the instruction do not hit the same alloca() calls, so it is not
				//  an error to have conflicting deltas in the functions that call alloca().
				//  We want to converge to the smallest magnitude deltas, which are the greatest
				//  values because the deltas are negative. This is the opposite of IDA Pro, which
				//  seems to use the largest stack deltas it has seen.
				if (PrevIncomingDelta >= IncomingDelta) {
					// Old incoming delta should be retained.
					WorkList.pop_front(); // discard already processed block.
				}
				else {
					CurrBlock->SetProcessed(false);
					ReprocessingAllocaBlocks = true;
					continue;  // Make the loop come around and process this block again, using
							   //  the new incoming delta. Because we do this only when it decreases
							   //  the stack size as seen by this block, no infinite loop is possible.
				}
			}
			else {
				this->AnalyzedSP = false;
				SMP_msg("ERROR: Stack delta: PrevIncoming is %d NewIncoming is %d at %x\n",
					PrevIncomingDelta, IncomingDelta, (*InstIter)->GetAddr());
				WorkList.clear();
			}
		}
		else { // not already processed
			// ReprocessingAllocaBlocks => Reaching definitions sets have already been computed; just need to do stack delta analysis
			ReachesOutChanged = false;
			ReachesInChanged = CurrBlock->ComputeReachesInSet();
			if (ReachesInChanged && ReprocessingAllocaBlocks) {
				// Because block is not truly being processed for the first time, the ReachesOut set can be
				//  recomputed without processing instructions, as the DEDefs set and VarKill set will never
				//  change after the first pass through the block.
				ReachesOutChanged = CurrBlock->ComputeReachesOutSet();
			}
			CurrBlock->SetProcessed(true);
			WorkList.pop_front();
			for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
				CurrInst = (*InstIter);
				ea_t InstAddr = CurrInst->GetAddr();
				if (InstAddr == this->GetFirstFrameAllocInstAddr()) {
					// Record the reset point for frame deallocations
					this->PreAllocStackDelta = IncomingDelta;
				}
#if 0
				if (this->CallsAlloca) { // keep deltas in a set; paths can lead to multiple deltas per inst
					bool DeltaAlreadyFound = CurrInst->FindStackPtrDelta(IncomingDelta);
				}
				else {
#endif
					CurrInst->SetStackPtrOffset(IncomingDelta);
#if 0
				}
#endif
#if SMP_COMPARE_IDA_STARS_STACK_POINTER_DELTAS
				if (DebugFlag && IDAProSucceeded && !this->CallsAlloca) {
					sval_t IDAProDelta = get_spd(this->GetFuncInfo(), InstAddr);
					if ((IDAProDelta != IncomingDelta) && (!CurrInst->MDIsHaltInstr())) {
						// IDA Pro special-cases the HALT instruction to make it appear that the
						//  incoming stack delta is zero. We do no such special case delta adjudstment,
						//  so we suppress error messages, as our delta will be non-zero.
						SMP_msg("ERROR: At %x IDA Pro has stack pointer delta of %d and we compute %d\n", InstAddr,
							IDAProDelta, IncomingDelta);
					}
				}
				if (TraceFlag) {
					SMP_msg("INFO: Stack delta trace: %d at %x\n", IncomingDelta, InstAddr);
				}
#endif

				// As soon as the stack ptr offset has been set for the current instruction, we can normalize
				//  all of its stack DEFs and USEs.
				bool StackOpsChanged = CurrInst->MDNormalizeStackOps(UseFP, this->GetFramePtrStackDelta(), ReprocessingAllocaBlocks);
				if (!FirstBlockProcessed) { // Look for initialization of frame pointer, record its stack delta
					FirstBlockProcessed = CurrInst->IsLastInBlock();
					if (!FPSaved) { // still looking for "push <framepointerreg>"
						if (CurrInst->MDIsPushInstr() && CurrInst->GetCmd().Operands[0].is_reg(MD_FRAME_POINTER_REG)) {
							FPSaved = true;
						}
					}
					else if (!SPintoFP) { // found "push <framepointerreg>", looking for "fp := sp"
						insn_t CurrCmd = CurrInst->GetCmd();
						if ((CurrCmd.itype == MD_MOVE_INSTRUCTION) 
							&& (CurrInst->GetFirstDef()->GetOp().is_reg(MD_FRAME_POINTER_REG))
							&& (CurrInst->GetFirstUse()->GetOp().is_reg(MD_STACK_POINTER_REG))) {
							SPintoFP = true;
							this->FramePointerStackDelta = IncomingDelta;
							FirstBlockProcessed = true; // stop looking
							assert(this->UsesFramePointer());
						}
					}
				}

				// 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.
				set<DefOrUse, LessDefUse>::iterator CurrUse;
				if (!ReprocessingAllocaBlocks) { // Only compute on first pass through block
					for (CurrUse = CurrInst->GetFirstUse(); CurrUse != CurrInst->GetLastUse(); ++CurrUse) {
						op_t UseOp = CurrUse->GetOp();
						if (MDIsDataFlowOpnd(UseOp, this->UsesFramePointer())) {
							// We have a register or stack operand. If stack operand, it is normalized, i.e. EBP-4 might be ESP-8,
							//  where the ESP-8 refers to the value of ESP upon entry to the function, not its current value.
							//  This normalization makes each stack location uniquely named (no aliases at different code locations due
							//  to different values of ESP at different code locations).
							// We only track certain kinds of operands in our data flow analyses.
							// 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 (!(CurrBlock->MDAlreadyKilled(UseOp))) {
								CurrBlock->AddUpExposed(UseOp);
							}
						}
					}
				}

				// Find stack pointer saves and restores.
				bool StackPtrSaved;
				sval_t SavedDelta;
				op_t CopyOperand;
				bool SavedDeltaHasNewValue = false;
				bool ErrorFlag = false;
				if (CurrInst->MDIsStackPtrSaveOrRestore(this->UsesFramePointer(), StackPtrSaved, SavedDelta, CopyOperand, ErrorFlag)) {
					// NOTE: If CopyOperand is a stack location, it is normalized.
					if (StackPtrSaved) {
						// Insert new entry into the StackPtrCopySet. For the ReprocessingAllocaBlocks case, this might be
						//  just a tricky update of the delta for an existing item in the set.
						bool DeltaInserted = this->AddToStackPtrCopySet(CopyOperand, InstAddr, SavedDelta);
						if (TraceFlag) {
							SMP_msg("INFO: Stack delta saved: %d at %x\n", SavedDelta, InstAddr);
						}
					}
					else { // stack pointer or frame pointer was restored
						SavedDeltaHasNewValue = true; // no need to compute effect of restore instruction later
					}
				} // end if (CurrInst->MDIsStackPtrSaveOrRestore())
				else if (ErrorFlag) {
					this->AnalyzedSP = false;
					WorkList.clear();
					break;
				}

				// Update VarKill and DownExposedDefs sets for DEFs in current instruction.
				// 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).
				if (!ReprocessingAllocaBlocks) { // Only compute on first pass through block
					set<DefOrUse, LessDefUse>::iterator CurrDef;
					for (CurrDef = CurrInst->GetFirstDef(); CurrDef != CurrInst->GetLastDef(); ++CurrDef) {
						op_t DefOp = CurrDef->GetOp();
						if (MDIsDataFlowOpnd(DefOp, this->UsesFramePointer())) {
							// We have a register or stack operand. If stack operand, it is normalized, i.e. EBP-4 might be ESP-8,