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, 2014, 2015 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 <iterator>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <cstring>
#include <cstdint>
#include <cstdlib>
#include <cassert>

#include "interfaces/SMPDBInterface.h"
#include "base/SMPDataFlowAnalysis.h"
#include "base/SMPFunction.h"
#include "base/SMPBasicBlock.h"
#include "base/SMPInstr.h"
#include "base/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_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_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_FUNC_SCCP 0
#define STARS_DEBUG_FUNC_SCCP_VERBOSE 1
#define STARS_DEBUG_LOOP_INVARIANTS 0
#define STARS_DEBUG_FPTR_SHADOW_LIST 0
#define SPARK_EMIT_UNIV_QUANTIFIER_PRECONDITIONS 0  // Use for-all-i form of restrictions on memory ranges

// For debugging purposes, only emit SPARK Ada for main().
#define STARS_EMIT_ADA_FOR_MAIN_ONLY 0

// Compute LVA/SSA or not? Turn it off for NICECAP demo on 31-JAN-2008
#define SMP_COMPUTE_LVA_SSA 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.
#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 0

// C99 standard permits up to 127 arguments to a single function,
//  but FORTRAN has no limit. We have encountered 290 in practice.
#define STARS_MAX_ARGS_PER_FUNC 512


#if 0
// moved to idapro/STARSFunction.cpp 
// 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;
#endif

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

// Are the operands, SSA numbers, and SubtractAddend fields identical?
bool EqualInductionVars(const InductionVarTriple &IV1, const InductionVarTriple &IV2) {
	bool success = (IV1.InductionVar.GetSSANum() == IV2.InductionVar.GetSSANum())
		&& (IV1.SubtractAddend == IV2.SubtractAddend);
	if (success) {
		success = IsEqOp(IV1.InductionVar.GetOp(), IV2.InductionVar.GetOp());
		if (success) {
			success = (IsEqOp(IV1.Addend.GetOp(), IV2.Addend.GetOp())
				&& (IsEqOp(IV1.Multiplier.GetOp(), IV2.Multiplier.GetOp())));
		}
	}
	return success;
} // end of EqualInductionVars()

// Debug dump of induction variable.
void DumpInductionVar(const struct InductionVarTriple IndVar) {
	SMP_msg("InductionVar: Multiplier: ");
	IndVar.Multiplier.Dump();
	SMP_msg(" Induction Ref: ");
	IndVar.InductionVar.Dump();
	if (IndVar.SubtractAddend) {
		SMP_msg(" AddSubOperator: - ");
	}
	else {
		SMP_msg(" AddSubOperator: + ");
	}
	SMP_msg(" Induction Addend: ");
	IndVar.Addend.Dump();
	SMP_msg("\n");
	return;
} // end of DumpInductionVar()

// Debug dump of InductionVarFamily.
void DumpInductionVarFamily(const struct InductionVarFamily IVFamily) {
	SMP_msg(" BIVIncomingSSA: %d BIVIncomingDefAddr: %llx BIVInsideLoopDefAddrs:", 
		IVFamily.BIVIncomingSSANum, (uint64_t) IVFamily.BIVIncomingDefAddr);
	for (vector<STARS_ea_t>::const_iterator AddrIter = IVFamily.BIVInsideLoopDefAddrs.cbegin();
		AddrIter != IVFamily.BIVInsideLoopDefAddrs.cend();
		++AddrIter) {
		SMP_msg(" %llx", (uint64_t) (*AddrIter));
	}
	SMP_msg(" BIV: ");
	DumpInductionVar(IVFamily.BasicInductionVar);
	for (size_t index = 0; index < IVFamily.DependentInductionVars.size(); ++index) {
		struct DependentInductionVar DIV = IVFamily.DependentInductionVars[index];
		SMP_msg("DIVDefAddr: %llx DIVRef: ", (uint64_t) DIV.DIVDefAddr);
		DIV.DIV.Dump();
		SMP_msg(" DIV equation: ");
		DumpInductionVar(DIV.IVExpr);
	}
} // end of DumpInductionVarFamily()

// Determine whether we have an incrementing or decrementing loop based on
//  the BasicInductionVar.
bool IsPositiveIncrementBIV(const struct InductionVarTriple BIV) {
	bool PositiveIncrement = true; // default
	STARSOpndTypePtr AddendOp = BIV.Addend.GetOp();
	if (AddendOp->IsImmedOp()) {
		STARS_uval_t ImmedValue = AddendOp->GetImmedValue();
		int SignedValue = (int) ImmedValue;
		if (SignedValue < 0) {
			PositiveIncrement = BIV.SubtractAddend;
		}
		else {
			PositiveIncrement = (!BIV.SubtractAddend);
		}
	}

	return PositiveIncrement;
} // end of IsPositiveIncrementBIV()

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

// Constructor
SMPFunction::SMPFunction(STARS_Function_t *Info, SMPProgram* pgm) {
	this->Program = pgm;
	this->FuncInfo = Info;
	this->FirstEA = this->FuncInfo->get_startEA();
	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->SystemCalls = false;
	this->DirectlyRecursive = false;
	this->MutuallyRecursive = false;
//	this->SetSharedChunks(false);
	this->UnsharedChunks = false;
	this->MultipleEntryPoints = false;
	this->CalledFromOrphanCode = false;
	this->TailCallChainFromOrphanCode = false;
	this->CallsNonReturningFunc = false;
	this->CalleeChainCallsNonReturningFunc = false;
	this->CallsAlloca = false;
	this->PushAfterLocalVarAlloc = false;
	this->LinkerStub = false;
	this->ThunkFunc = false;
	this->AnalyzedSP = false;
	this->STARSStackPtrAnalysisPerformed = false;
	this->StackAdjustmentComputed = false;
	this->BuiltRTLs = false;
	this->HasReducibleCFG = false;
	this->HasStructuredCFG = false;
	this->HasGoodSSA = false;
#if 1  // default to unsafe
	this->SetFuncSafe(false);
	this->SetSpecFuncSafe(false);
	this->SafeCallee = false;
	this->SpecSafeCallee = false;
	this->UnsafeForFastReturns = true;
#else // default to safe
	this->SetFuncSafe(true);
	this->SpecSafeFunc = true;
	this->SafeCallee = true;
	this->SpecSafeCallee = true;
	this->UnsafeForFastReturns = false;
#endif
	this->WritesAboveRA = false;
	this->NeedsStackReferent = true;
	this->SpecNeedsStackReferent = true;
	this->HasIndirectWrites = false;
	this->HasUnsafeIndirectWrites = false;
	this->AltersMemory = false;
	this->HasLoopInArgMemWrites = false;
	this->HasMemExprsFromCalleeLoops = false;
	this->PossibleIndirectCallTarget = false;
	this->PossibleTailCallTarget = false;
	this->ReturnTargetsComputed = false;
	this->OutgoingArgsComputed = false;
	this->GoodLocalVarTable = false;
	this->StackFrameExtendsPastStackTop = false;
	this->SetIsSpeculative(false);
	this->HasHashingCode = false;
	this->HasInArgCodePointer = false;
	this->HasInArgDataPointer = false;
	this->HasMallocCall = false;
	this->TranslatingSPARKLoop = false;
	this->TypedDefs = 0;
	this->UntypedDefs = 0;
	this->TypedPhiDefs = 0;
	this->UntypedPhiDefs = 0;
	this->SafeBlocks = 0;
	this->UnsafeBlocks = 0;
	this->Size = 0;

#if 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->GetFrameSize();
	this->CalleeSavedRegsSize = this->FuncInfo->GetSavedRegSize();
	this->IncomingArgsSize = (STARS_asize_t) this->FuncInfo->GetIncomingArgumentSize();

	// 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->GetFuncInfo()->GetFrameReturnAddressSize();
#else  // compute values in MDFixFrameInfo() before their first use; avoid IDA Pro calls
	this->LocalVarsSize = 0;
	this->CalleeSavedRegsSize = 0;
	this->IncomingArgsSize = 0; // unused
	this->RetAddrSize = global_STARS_program->GetSTARS_ISA_Bytewidth();
#endif
	this->AllocSizeAfterFrameAlloc = 0;
	this->OutgoingArgsSize = 0;
	this->LocalVarsAllocInstr = STARS_BADADDR;
	this->LocalVarsDeallocInstr = STARS_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->SetLocalVarOffsetLimit(0);
	this->MaxDirectStackAccessDelta = 0;
	this->IDAReturnAddressOffset = 0;

	this->ReturnAddrStatus = FUNC_UNKNOWN;
	this->FastReturnStatus = SAFE_FAST_RETURN;

	this->InArgCount = 0;
	this->MaxInArgIndex = 0;
	this->TaintInArgPosBits = 0;
	this->MaxDirectStackAccessSSANum = 0;
	this->MaxRegSSANum = 0;
	this->InArgTypes.clear();
	this->InArgTypes.resize(STARS_MAX_ARGS_PER_FUNC);

	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->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 = STARS_x86_R_ax; RegIndex <= global_STARS_program->GetSTARS_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);
		this->IncomingRegTypes.push_back(UNINIT);
	}
	this->InArgTypes.assign(STARS_MAX_ARGS_PER_FUNC, (unsigned short) UNINIT);

	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 STARS_Function_t info for the current function.
STARS_Function_t *SMPFunction::GetFuncInfo(void)  const {
	STARS_Function_t *myPtr = SMP_get_func(this->GetFirstFuncAddr());
	assert(NULL != myPtr);
	return myPtr;
}

uint16_t SMPFunction::GetJumpToFollowNodeCounter(STARS_ea_t InstAddr) const {
	uint16_t Counter = 0;
	map<STARS_ea_t, uint16_t>::const_iterator MapIter = this->JumpToFollowNodeCounterMap.find(InstAddr);
	if (MapIter != this->JumpToFollowNodeCounterMap.end()) {
		Counter = MapIter->second;
	}
	return Counter;
} // end of SMPFunction::GetJumpToFollowNodeCounter()

// 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. 
STARSOpndSetIter SMPFunction::GetFirstLiveIn(void) {
	return this->Blocks.front()->GetFirstLiveIn();
} // end of SMPBasicBlock::GetFirstLiveIn()

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

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

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

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

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

// Compute InRegs, OutRegs, 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);
		STARSOpndSetIter LVASetIter;
		pair<STARSOpndSetIter, bool> InsertResult;
		for (LVASetIter = CurrBlock->GetFirstVarKill(); LVASetIter != CurrBlock->GetLastVarKill(); ++LVASetIter) {
			STARSOpndTypePtr 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) {
				STARSOpndTypePtr LiveOutOp = (*LVASetIter);
				InsertResult = this->LiveOutSet.insert(LiveOutOp); // insert will often fail due to duplication, which is expected
			}
		}
	}
	return;
} // end of SMPFunction::ComputeGlobalSets()

// compute InputRegs (USEs) and OutputRegs (DEFs), only inherit from callees on InheritPass
bool SMPFunction::ComputeInOutRegs(bool InheritPass, bool &WritesMem, bool &CallChainNonReturning) {
	bool Changed = false;
	bool MemoryInput = false;
	bool MemoryOutput = false;
	CallChainNonReturning = false;

	if (InheritPass) {
		SMP_msg("INFO: InheritPass for ComputeInOutRegs(), function %s at %llx\n", this->GetFuncName(), (uint64_t) this->GetFirstFuncAddr());
		// Look at all callees and union their bitsets in.
		size_t OldInputBitCount = this->InputRegs.count();
		size_t OldOutputBitCount = this->OutputRegs.count();
		size_t OldCalleePreservedRegsBitCount = this->CalleePreservedRegs.count();
		size_t NumCallees = this->GetNumCallTargets();
		for (size_t CalleeIndex = 0; CalleeIndex < NumCallees; ++CalleeIndex) {
			STARS_ea_t CalleeAddr = this->GetCallTargetAddr(CalleeIndex);
			if (STARS_BADADDR != CalleeAddr) {
				SMPFunction *CalleeFunc = this->GetProg()->FindFunction(CalleeAddr);
				if (nullptr != CalleeFunc) {
					this->InputRegs |= CalleeFunc->GetInputRegs();
					MemoryOutput |= CalleeFunc->AltersSPARKMemory();
					this->CalleeHasLoopInArgMemWrites |= CalleeFunc->UsesInArgsForLoopMemWrites();
					CallChainNonReturning |= (CalleeFunc->HasCallToNonReturningFunc() || CalleeFunc->HasCalleeChainWithNonReturningFunc());

					// Examine whether the callee preserves a reg before deciding how to record the OutputRegs info.
					std::bitset<1 + MD_LAST_REG_NO> TempCalleeOutputRegs = CalleeFunc->GetOutputRegs();
					std::bitset<1 + MD_LAST_REG_NO> TempCalleePreservedRegs = CalleeFunc->GetPreservedRegs();
					std::bitset<1 + MD_LAST_REG_NO> TempCalleeChainPreservedRegs = CalleeFunc->GetCalleePreservedRegs();
					for (size_t RegNo = 0; RegNo < TempCalleeOutputRegs.size(); ++RegNo) {
						if (TempCalleeOutputRegs[RegNo]) {
							// If RegNo is Preserved, record in CalleePreservedRegs.
							if (TempCalleePreservedRegs[RegNo]) {
								this->CalleePreservedRegs.set(RegNo);
							}
							else {
								// Altered, not preserved
								this->OutputRegs.set(RegNo);
							}
						}
						else if (TempCalleePreservedRegs[RegNo]) { // preserved in callee, not explicitly altered
							this->CalleePreservedRegs.set(RegNo);
						}
						else if (TempCalleeChainPreservedRegs[RegNo]) { // preserved in callee chain, not explicitly altered
							this->CalleePreservedRegs.set(RegNo);
						}
					}
				}
			}
		} // end for all callees
		Changed = ((OldInputBitCount < this->InputRegs.count()) || (OldOutputBitCount < this->OutputRegs.count()) || (OldCalleePreservedRegsBitCount < this->CalleePreservedRegs.count()));
	}

	// We need to record registers read and written in instructions, excluding calls with their
	//  conservative DEF and USE lists, and excluding the SSA Marker inst with its pseudo-DEFs.
	for (size_t BlockNum = 0; BlockNum < this->RPOBlocks.size(); ++BlockNum) {
		SMPBasicBlock *CurrBlock = this->RPOBlocks[BlockNum];
		if (!InheritPass) {
			Changed = true;
			for (vector<SMPInstr *>::iterator InstIter = CurrBlock->GetFirstInst(); InstIter != CurrBlock->GetLastInst(); ++InstIter) {
				SMPInstr *CurrInst = (*InstIter);
				STARS_ea_t InstAddr = CurrInst->GetAddr();
				if (STARS_IsSSAMarkerPseudoID(InstAddr))
					continue;

				SMPitype FlowType = CurrInst->GetDataFlowType();
				if ((DEFAULT != FlowType) && (JUMP != FlowType) && (INDIR_JUMP != FlowType)) {
					if ((CALL == FlowType) || (INDIR_CALL == FlowType) || (RETURN == FlowType)) {
						// Calls and returns change the stack pointer.
						this->OutputRegs.set((size_t) MD_STACK_POINTER_REG, true);
						this->InputRegs.set((size_t) MD_STACK_POINTER_REG, true);
					}
					continue;  // exclude CALL, INDIR_CALL, RETURN with their conservative USE and DEF lists
				}
				for (STARSDefUseIter UseIter = CurrInst->GetFirstUse(); UseIter != CurrInst->GetLastUse(); ++UseIter) {
					STARSOpndTypePtr UseOp = UseIter->GetOp();
					if (UseOp->IsRegOp() || UseOp->IsFloatingPointRegOp()) {
						STARS_regnum_t RegNo = UseOp->GetReg();
						this->InputRegs.set((size_t) RegNo, true);
					}
					else if (UseOp->IsMemOp()) {
						MemoryInput = true;
					}
				} // end for all USEs

				for (STARSDefUseIter DefIter = CurrInst->GetFirstDef(); DefIter != CurrInst->GetLastDef(); ++DefIter) {
					STARSOpndTypePtr DefOp = DefIter->GetOp();
					if (DefOp->IsRegOp() || DefOp->IsFloatingPointRegOp()) {
						STARS_regnum_t RegNo = DefOp->GetReg();
						this->OutputRegs.set((size_t) RegNo, true);
					}
					else if (DefOp->IsMemOp()) {
						MemoryOutput = true;
					}
				} // end for all DEFs
			} // end for all insts in block
			if (!MemoryOutput && CurrBlock->HasMemoryWrite()) {
				SMP_msg("INFO: SPARK: Found new MemoryOutput using HasMemoryWrite\n");
				MemoryOutput = true;  // could be non-stack mem, not in DEFs
			}
		}
		else if (CurrBlock->HasCallInstruction()) { // InheritPass
			int LoopNum = this->GetInnermostLoopNum(CurrBlock->GetNumber());
			size_t LoopNumOffsetByOne = (size_t)(LoopNum + 1);
			// Note: LoopNum could be -1 if we are outside of any loop.
			list<size_t> LoopList;
			if (LoopNum >= 0) {
				this->BuildLoopList((int) BlockNum, LoopList);
			}
			string CurrFuncName(this->GetFuncName());

			for (vector<SMPInstr *>::iterator InstIter = CurrBlock->GetFirstInst(); InstIter != CurrBlock->GetLastInst(); ++InstIter) {
				// Find call instruction and determine callee.
				SMPInstr *CurrInst = (*InstIter);
				STARS_ea_t InstAddr = CurrInst->GetAddr();
				SMPitype FlowType = CurrInst->GetDataFlowType();
				if ((CALL == FlowType) || (INDIR_CALL == FlowType) || ((RETURN == FlowType) && CurrInst->IsTailCall())) {
					STARS_ea_t CalleeAddr = CurrInst->GetCallTarget();
					if (STARS_BADADDR != CalleeAddr) {
						SMPFunction *CalleeFunc = this->GetProg()->FindFunction(CalleeAddr);
						if ((nullptr != CalleeFunc) && CalleeFunc->StackPtrAnalysisSucceeded() && CalleeFunc->HasStructuredControlFlow()) {
							SMP_msg("INFO: SPARK: Function %s inheriting mem exprs from callee %s\n", CurrFuncName.c_str(), CalleeFunc->GetFuncName());
							size_t NumCalleeLoops = CalleeFunc->GetNumLoops();
							for (size_t CalleeLoopIndexPlusOne = 0; CalleeLoopIndexPlusOne <= NumCalleeLoops; ++CalleeLoopIndexPlusOne) {
								// Get non-loop mem write exprs that trace back to InArgs, trace them back from actual arg in this function.
								size_t NumCalleeInArgMemAddrs = CalleeFunc->GetNumInArgsUsedInMemWrites(CalleeLoopIndexPlusOne);
								pair<STARSExprSetIter, bool> InsertResult;
								for (size_t InArgIndex = 0; InArgIndex < NumCalleeInArgMemAddrs; ++InArgIndex) {
									size_t MemExprWidth = CalleeFunc->GetInArgMemWriteWidth(CalleeLoopIndexPlusOne, InArgIndex);
									STARSExprSetIter CurrentMemExprIter = CalleeFunc->GetInArgExprUsedInMemWrite(CalleeLoopIndexPlusOne, InArgIndex);
									STARSExpression *CurrentMemAddrExpr = (*CurrentMemExprIter)->Clone();
									Changed |= this->InheritCalleeMemExpr(MemExprWidth, CurrentMemAddrExpr, CurrInst, LoopNum, LoopList);
								} // end for ( ... InArgIndex < NumCalleeInArgMemAddrs ...)
							}

							// Inherit all of the callee's inherited MemExprs that traced back to InArgs.
							for (size_t CalleeLoopIndexPlusOne = 0; CalleeLoopIndexPlusOne <= NumCalleeLoops; ++CalleeLoopIndexPlusOne) {
								size_t NumCalleeInheritedExprs = CalleeFunc->GetNumInheritedMemWriteExprs(CalleeLoopIndexPlusOne);
								for (size_t ExprIndex = 0; ExprIndex < NumCalleeInheritedExprs; ++ExprIndex) {
									size_t MemExprWidth = CalleeFunc->GetInheritedMemWriteWidth(CalleeLoopIndexPlusOne, ExprIndex);
									STARSExprSetIter ExprIter = CalleeFunc->GetInheritedMemWriteExpr(CalleeLoopIndexPlusOne, ExprIndex);
									STARSExpression *CurrentMemAddrExpr = (*ExprIter)->Clone();
									Changed |= this->InheritCalleeMemExpr(MemExprWidth, CurrentMemAddrExpr, CurrInst, LoopNum, LoopList);
								}
							}

							// Do the same for callee loop mem write range exprs.
							for (size_t LoopIndex = 0; LoopIndex < NumCalleeLoops; ++LoopIndex) {

								STARSExprBoundsIter ExprIter;
								for (ExprIter = CalleeFunc->GetFirstLoopMemWriteExpandedExprBoundsIter(LoopIndex); ExprIter != CalleeFunc->GetLastLoopMemWriteExpandedExprBoundsIter(LoopIndex); ++ExprIter) {
									STARSExpression *LowerExpr = ExprIter->first;
									STARSExpression *UpperExpr = ExprIter->second;
									
									if ((nullptr != LowerExpr) && (nullptr != UpperExpr)) {
										// Set up a range expr so we can re-use this->InheritCalleeMemRangeExpr()
										STARSExpression *TempMemRangeExpr = new STARSExpression();
										TempMemRangeExpr->SetLeftTree(LowerExpr->Clone());
										TempMemRangeExpr->SetRightTree(UpperExpr->Clone());
										TempMemRangeExpr->SetParentFunc(TempMemRangeExpr->GetLeftTree()->GetParentFunc());
										TempMemRangeExpr->SetParentInst(TempMemRangeExpr->GetLeftTree()->GetParentInst());
										TempMemRangeExpr->SetOriginalParentInst(TempMemRangeExpr->GetLeftTree()->GetOriginalParentInst());
										TempMemRangeExpr->SetOperator(SMP_LESS_THAN); // LowerBound < UpperBound is range expr
										size_t MemWriteByteWidth = LowerExpr->FindOrigMemOpByteWidth();
										if (0 == MemWriteByteWidth) {
											MemWriteByteWidth = UpperExpr->FindOrigMemOpByteWidth();
										}
										if (0 == MemWriteByteWidth) {
											SMP_msg("ERROR: expr Inherited byte width of 0 from CalleeFunc %s ; expr dump follows.\n",
												CalleeFunc->GetFuncName());
											LowerExpr->Dump(0);
											MemWriteByteWidth = global_STARS_program->GetSTARS_ISA_Bytewidth(); // default
										}

										Changed |= this->InheritCalleeMemRangeExpr(TempMemRangeExpr, CurrInst, MemWriteByteWidth, LoopNumOffsetByOne, LoopList);
									}
								} // end for all expanded expr pairs in callee func for current LoopIndex
							} // end for all loops in CalleeFunc

							// Do the same for callee looping string mem write range exprs.
							for (size_t LoopIndexPlusOne = 0; LoopIndexPlusOne <= CalleeFunc->GetNumLoops(); ++LoopIndexPlusOne) {
								size_t ExprIndexLimit = CalleeFunc->GetNumStringMemWriteRangeExprs(LoopIndexPlusOne);
								for (size_t i = 0; i < ExprIndexLimit; ++i) {
									STARSExprSetIter StringExprIter = CalleeFunc->GetStringMemWriteRangeExpr(LoopIndexPlusOne, i);
									STARSExpression *TempStringRangeExpr = (*StringExprIter);
									assert(nullptr != TempStringRangeExpr);
									STARSExpression *CalleeStringRangeExpr = TempStringRangeExpr->Clone();
									size_t MemWriteByteWidth = CalleeFunc->GetStringMemWriteRangeWidth(LoopIndexPlusOne, i);
									SMP_msg("INFO: SPARK: Inheriting CalleeStringRangeExpr from CalleeAddr %llx at CallAddr %llx\n",
										(uint64_t) CalleeAddr, (uint64_t) InstAddr);
									Changed |= this->InheritCalleeMemRangeExpr(CalleeStringRangeExpr, CurrInst, MemWriteByteWidth, LoopNumOffsetByOne, LoopList);
								}
							} // end for all loops in CalleeFunc
						}
					}
				}
			}
		}
	} // end for all blocks

	WritesMem = MemoryOutput;

	return Changed;
} // end of SMPFunction::ComputeInOutRegs()

// Return true if mem expr inherited and added to MemAddrExprWidthsFromCallees
bool SMPFunction::InheritCalleeMemExpr(size_t MemExprWidth, STARSExpression *CurrentMemAddrExpr, SMPInstr *CallInst, int LoopNum, const list<size_t> &LoopList) {
	// Trace actual arg register back, substitute source into clone of callee mem addr expr to produce
	//  the mem addr expr for this function.
	STARSOpndTypePtr InArgOp = CurrentMemAddrExpr->GetLeftOperand();
	STARS_ea_t InstAddr = CallInst->GetAddr();
	size_t LoopNumOffsetByOne = (size_t) (LoopNum + 1);
	bool changed = false;
	bool VerboseOutput = global_stars_interface->VerboseLoopsMode();
	if (!CurrentMemAddrExpr->HasLeftSubTree() && InArgOp->IsRegOp() && (!InArgOp->MatchesReg(MD_STACK_POINTER_REG))) { // simple LeftOperand == InArg case
		STARSDefUseIter UseIter = CallInst->FindUse(InArgOp);
		assert(UseIter != CallInst->GetLastUse());
		// Start changing values in our cloned expr to match this function.
		CurrentMemAddrExpr->SetParentFunc(this);
		CurrentMemAddrExpr->SetParentInst(CallInst);
		CurrentMemAddrExpr->SetLeftUseAddr(InstAddr);
		CurrentMemAddrExpr->SetLeftSSANum(UseIter->GetSSANum());
		CurrentMemAddrExpr->SetLeftPreLoopDefAddr(STARS_BADADDR);
		if (VerboseOutput) {
			SMP_msg("INFO: MemAddrExprFromCallee before expansion: Width: %zu", MemExprWidth);
			CurrentMemAddrExpr->Dump(0);
		}
		bool StoppedOnIV = false;
		bool changed = false;
		set<int> DummyLoopRegHashes;
		set<STARS_ea_t> StackPtrCopySet;
		int DepthCounter = 0;
		if (CurrentMemAddrExpr->ExpandExpr(InstAddr, (size_t) LoopNum, false, true, true, false, false, DummyLoopRegHashes, StoppedOnIV, changed, StackPtrCopySet, DepthCounter)) {
			if (!StoppedOnIV) {
				// CurrentMemAddrExpr has been expanded successfully to an InArg or constant.
				CurrentMemAddrExpr->EvaluateConsts();
				bool Simplified = CurrentMemAddrExpr->SimplifyDriver();
				pair<STARSExprSetIter, bool> InsertResult = this->MemAddrExprsFromCallees[LoopNumOffsetByOne].insert(CurrentMemAddrExpr);
				if (InsertResult.second) { // new mem expr
					pair<STARSExprSetIter, size_t> InsertValue(InsertResult.first, MemExprWidth);
					this->MemAddrExprWidthsFromCallees[LoopNumOffsetByOne].push_back(InsertValue);
					if (VerboseOutput) {
						SMP_msg("INFO: MemAddExprFromCallee after expansion: Width: %zu", MemExprWidth);
						CurrentMemAddrExpr->Dump(0);
					}
					std::bitset<1 + MD_LAST_REG_NO> InArgRegNums;
					CurrentMemAddrExpr->ListInArgRegsUsed(InArgRegNums);
					// Mark all loops containing this block as having callee mem writes.
					for (list<size_t>::const_iterator LoopIter = LoopList.cbegin(); LoopIter != LoopList.cend(); ++LoopIter) {
						this->LoopHasCalleeMemWrites[*LoopIter] = true;
					}
					changed = true;
					this->MemRangeRegsBitmap |= InArgRegNums;

					if (LoopNum >= 0) {
						// If CurrentMemAddrExpr expands to a stack frame write in the loop's containing procedure,
						//  update the stack frame written maps.
						STARS_sval_t FinalStackPtrOffset;
						// CurrentMemAddrExpr has already expanded to the incoming stack pointer reg, so the
						//  expression is already normalized to a negative offset from the return address location.
						//  We pass in zero as the CurrentStackPtrOffset to avoid double-normalization.
						if (CurrentMemAddrExpr->IsStackPtrOffset(0, FinalStackPtrOffset)) {
							// Update for all loops that contain CallInst.
							int CallBlockNum = CallInst->GetBlock()->GetNumber();
							list<size_t> LoopList;
							this->BuildLoopList(CallBlockNum, LoopList);
							for (list<size_t>::const_iterator LoopIter = LoopList.cbegin(); LoopIter != LoopList.cend(); ++LoopIter) {
								size_t CurrLoopNum = (*LoopIter);
								this->UpdateStackBytesWrittenByLoop(FinalStackPtrOffset, MemExprWidth, CurrLoopNum);
								for (size_t RegNum = 0; RegNum < InArgRegNums.size(); ++RegNum) {
									if (InArgRegNums[RegNum]) {
										this->LoopMemRangeInArgRegsBitmap[CurrLoopNum].set(RegNum);
									}
								}
							}
						}
					}
				}
				else {
					SMP_msg("INFO: Expr insert collision at CallAddr %llx\n", (uint64_t)InstAddr);
				}
			}
			else { // StoppedOnIV
				SMP_msg("INFO: SPARK: Expr Expand() StoppedOnIV in InheritCalleeMemExpr() at %llx\n",
					(uint64_t) InstAddr);
				pair<STARSExprSetIter, bool> InsertResult = this->StoppedOnIVNonRangeExprs[LoopNumOffsetByOne].insert(CurrentMemAddrExpr);
				if (InsertResult.second) { // new Expr
					pair<STARSExprSetIter, size_t> InsertValue(InsertResult.first, MemExprWidth);
					this->StoppedOnIVNonRangeIterWidths[LoopNumOffsetByOne].push_back(InsertValue);
				}
			}
		}
		else {
			SMP_msg("ERROR: ExpandExpr() failure in InheritCalleeMemExpr() at CallAddr %llx\n", (uint64_t) InstAddr);
		}
	}
	return changed;
} // end of SMPFunction::InheritCalleeMemExpr()

bool SMPFunction::InheritCalleeMemRangeExpr(STARSExpression *CalleeMemRangeExpr, SMPInstr *CallInst, size_t MemWriteByteWidth, size_t LoopNumPlusOne, const list<size_t> &LoopList) {
	// Again, deal with the simple to analyze case in which we can find the InArg on the lhs easily.
	bool FoundInArg = false;
	bool Changed = false;
	bool VerboseOutput = global_stars_interface->VerboseLoopsMode();
	STARS_ea_t InstAddr = CallInst->GetAddr();

	// Start changing values in our cloned expr to match this function.
	CalleeMemRangeExpr->SetParentFunc(this);
	CalleeMemRangeExpr->SetParentInst(CallInst);
	bitset<1 + MD_LAST_REG_NO> InArgRegNums;
	CalleeMemRangeExpr->ListInArgRegsUsed(InArgRegNums);
	bool FoundInArgReg = InArgRegNums.any();

	if (FoundInArgReg) {
		bool ReplacedInArgSSANum = false;
		for (size_t RegNum = 0; RegNum < InArgRegNums.size(); ++RegNum) {
			bool StackPointerReg = (RegNum == MD_STACK_POINTER_REG);
			if (!StackPointerReg && InArgRegNums[RegNum]) {
				STARSOpndTypePtr CurrInArgOp = CallInst->MakeRegOpnd((STARS_regnum_t) RegNum);
				STARSDefUseIter UseIter = CallInst->FindUse(CurrInArgOp);
				if (UseIter != CallInst->GetLastUse()) {
					// Replace all SSANum == 0 instances of InArgOp with SSANum of InArg in this function.
					// NOTE: Might we need to do the same for multiple InArgs, used as limits, etc.?
					CalleeMemRangeExpr->SubstituteSSANum(CallInst, UseIter->GetSSANum(), CurrInArgOp);
					ReplacedInArgSSANum = true;
				}
				else {
					SMP_msg("ERROR: SPARK: Callee loop range does not trace to InArgUSE at call site %llx\n", (uint64_t) InstAddr);
				}
			}
		} // end for all InArgRegNums
		if (!ReplacedInArgSSANum) {
			SMP_msg("ERROR: SPARK: Callee loop range expr did not see InArgSSANums replaced at call site %llx\n", (uint64_t) InstAddr);
		}
		if (VerboseOutput) {
			SMP_msg("INFO: LoopCalleeMemRangeExpr before expansion:");
			CalleeMemRangeExpr->Dump(0);
		}
		bool StoppedOnIV = false;
		bool changed = false;
		set<int> DummyLoopRegHashes;
		set<STARS_ea_t> StackPtrCopySet;
		int DepthCounter = 0;
		if (CalleeMemRangeExpr->ExpandExpr(InstAddr, 0, false, true, true, false, false, DummyLoopRegHashes, StoppedOnIV, changed, StackPtrCopySet, DepthCounter)) {
			if (!StoppedOnIV) {
				// CalleeMemRangeExpr has been expanded successfully to an InArg or constant.
				CalleeMemRangeExpr->EvaluateConsts();
				bool Simplified = CalleeMemRangeExpr->SimplifyDriver();
				pair<STARSExprSetIter, bool> InsertResult = this->LoopMemAddrExprsFromCalleeLoops[LoopNumPlusOne].insert(CalleeMemRangeExpr);
				if (InsertResult.second) { // new mem expr
					InArgRegNums.reset();
					this->HasMemExprsFromCalleeLoops = true;
					Changed = true;
					CalleeMemRangeExpr->ListInArgRegsUsed(InArgRegNums);
					pair<STARSExprSetIter, size_t> InsertValue(InsertResult.first, MemWriteByteWidth);
					this->LoopMemAddrExprWidthsFromCalleeLoops[LoopNumPlusOne].push_back(InsertValue);
					if (VerboseOutput) {
						SMP_msg("INFO: LoopCalleeMemRangeExpr after expansion:");
						CalleeMemRangeExpr->Dump(0);
					}
					this->MemRangeRegsBitmap |= InArgRegNums;
					// Mark all loops containing this block as having callee mem writes.
					for (list<size_t>::const_iterator LoopIter = LoopList.cbegin(); LoopIter != LoopList.cend(); ++LoopIter) {
						size_t CurrLoopNum = *LoopIter;
						this->LoopHasCalleeMemWrites[CurrLoopNum] = true;
						// Mark the InArg regs reached in the Expand() operation.
						for (size_t RegNum = 0; RegNum < InArgRegNums.size(); ++RegNum) {
							if (InArgRegNums[RegNum]) {
								this->LoopMemRangeInArgRegsBitmap[CurrLoopNum].set(RegNum);
							}
						}
					}
				}
				else {
					SMP_msg("INFO: Expr insert collision at CallAddr %llx\n", (uint64_t) InstAddr);
				}
			}
			else { // StoppedOnIV
				SMP_msg("ERROR: SPARK: Expr Expand() StoppedOnIV in InheritCalleeMemRangeExpr() at %llx\n",
					(uint64_t) InstAddr);
				this->CalleeMemExprProblems[LoopNumPlusOne] = true;
				pair<STARSExprSetIter, bool> InsertResult = this->StoppedOnIVMemRangeExprs[LoopNumPlusOne].insert(CalleeMemRangeExpr);
				if (InsertResult.second) { // new Expr
					pair<STARSExprSetIter, size_t> InsertValue(InsertResult.first, MemWriteByteWidth);
					this->StoppedOnIVMemRangeIterWidths[LoopNumPlusOne].push_back(InsertValue);
				}
			}
		}
		else {
			SMP_msg("ERROR: SPARK: ExpandExpr() failure in InheritCalleeMemRangeExpr at CallAddr %llx\n", (uint64_t) InstAddr);
			this->CalleeMemExprProblems[LoopNumPlusOne] = true;
		}
	}
	else if (!FoundInArgReg) {
		pair<STARSExprSetIter, bool> InsertResult = this->LoopMemAddrExprsFromCalleeLoops[LoopNumPlusOne].insert(CalleeMemRangeExpr);
		if (InsertResult.second) { // new mem expr
			this->HasMemExprsFromCalleeLoops = true;
			Changed = true;
			pair<STARSExprSetIter, size_t> InsertValue(InsertResult.first, MemWriteByteWidth);
			this->LoopMemAddrExprWidthsFromCalleeLoops[LoopNumPlusOne].push_back(InsertValue);
			if (VerboseOutput) {
				SMP_msg("INFO: Global static inherited LoopCalleeMemRangeExpr:");
				CalleeMemRangeExpr->Dump(0);
			}
			// Mark all loops containing this block as having callee mem writes.
			for (list<size_t>::const_iterator LoopIter = LoopList.cbegin(); LoopIter != LoopList.cend(); ++LoopIter) {
				size_t CurrLoopNum = *LoopIter;
				this->LoopHasCalleeMemWrites[CurrLoopNum] = true;
			}
		}
		else {
			SMP_msg("INFO: Expr insert collision at CallAddr %llx\n", (uint64_t) InstAddr);
		}
	}
	return Changed;
} // end of SMPFunction::InheritCalleeMemRangeExpr()

// Split relational RangeExpr into upper and lower bonds exprs and save them and their width
void SMPFunction::SplitAndSaveRelationalExpr(bool PositiveIncrement, std::size_t LoopNumPlusOne, size_t MemWidth, STARSExpression *RangeExpr) {
	assert(nullptr != RangeExpr);
	assert((0 <= LoopNumPlusOne) && (LoopNumPlusOne <= this->GetNumLoops()));
	bool VerboseOutput = global_stars_interface->VerboseLoopsMode();
	STARSExpression *LowerExpr;
	STARSExpression *UpperExpr;
	RangeExpr->SplitMemoryRangeExpr(PositiveIncrement, LowerExpr, UpperExpr);
	assert(nullptr != LowerExpr);
	assert(nullptr != UpperExpr);
	if (VerboseOutput) {
		SMP_msg("INFO: SPARK: RelationalExpr being split: \n");
		RangeExpr->Dump(0);
	}
	pair<STARSExprSetIter, bool> InsertResult = this->RelationalLowerBoundExprs[LoopNumPlusOne].insert(LowerExpr);
	pair<STARSExprSetIter, bool> InsertResult2 = this->RelationalUpperBoundExprs[LoopNumPlusOne].insert(UpperExpr);
	if (InsertResult.second || InsertResult2.second) { // new range if either one was new expr
		pair<STARSExprSetIter, STARSExprSetIter> BoundsIters(InsertResult.first, InsertResult2.first);
		pair<size_t, pair<STARSExprSetIter, STARSExprSetIter> > InsertValue(MemWidth, BoundsIters);
		this->RelationalMemWriteWidths[LoopNumPlusOne].push_back(InsertValue);
	}
	else {
		SMP_msg("INFO: SPARK: Duplicate RelationalExpr not saved.\n");
	}

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

// Build range expr for memory writes in looping string opcode
void SMPFunction::BuildLoopingStringMemExprs(SMPBasicBlock *CurrBlock, SMPInstr *CurrInst) {
	assert(CurrBlock->HasLoopingStringOpcode());
	unsigned short opcode = CurrInst->GetIDAOpcode();
	STARS_ea_t InstAddr = CurrInst->GetAddr();
	bool NonWritingLoopingStringOperation = ((opcode == STARS_NN_cmps) || (opcode == STARS_NN_scas) || (opcode == STARS_NN_outs));
	bool VerboseOutput = global_stars_interface->VerboseLoopsMode();
	if (!NonWritingLoopingStringOperation) {
		// Make Expr like: RDI < (RDI + (RCX*ByteWidth))
		int CurrBlockNum = CurrBlock->GetNumber();
		STARSOpndTypePtr FirstOpnd = CurrInst->GetOperand(0);
		uint16_t ByteWidth = FirstOpnd->GetByteWidth();
		STARSExpression *LowerBoundExpr = new STARSExpression();
		LowerBoundExpr->SetParentFunc(this);
		LowerBoundExpr->SetParentInst(CurrInst);
		LowerBoundExpr->SetOriginalParentInst(CurrInst);
		LowerBoundExpr->SetOperator(SMP_ASSIGN);
		STARSOpndTypePtr UseOp = CurrInst->MakeRegOpnd(STARS_x86_R_di);
		STARSDefUseIter UseIter = CurrInst->FindUse(UseOp);
		assert(UseIter != CurrInst->GetLastUse());
		LowerBoundExpr->SetLeftOperand(UseOp);
		LowerBoundExpr->SetLeftUseAddr(InstAddr);
		LowerBoundExpr->SetLeftSSANum(UseIter->GetSSANum());

		int LoopIndex = this->GetInnermostLoopNum(CurrBlockNum);
		size_t LoopNum = (size_t) LoopIndex;
		int LoopIndexPlusOne = LoopIndex + 1;
		bool InsideLoop = (0 <= LoopIndex);
		bool StoppedOnIV = false;
		bool changed = false;
		if (!InsideLoop) { // not in a loop
			LoopNum = 0;
		}
		set<int> LoopRegHashes;
		set<STARS_ea_t> StackPtrCopySet;
		int DepthCounter = 0;
		if (LowerBoundExpr->ExpandExpr(InstAddr, LoopNum, false, true, true, true, false, LoopRegHashes, StoppedOnIV, changed, StackPtrCopySet, DepthCounter)) {
			if (StoppedOnIV) {
				this->SymbolicAnalysisProblems[LoopIndexPlusOne] = true;
				SMP_msg("ERROR: SPARK: LowerBoundExpr Expand() StoppedOnIV in BuildLoopingStringMemExprs() at %llx\n",
					(uint64_t)InstAddr);
				pair<STARSExprSetIter, bool> InsertResult = this->StoppedOnIVMemRangeExprs[LoopIndexPlusOne].insert(LowerBoundExpr);
				if (InsertResult.second) { // new Expr
					pair<STARSExprSetIter, size_t> InsertValue(InsertResult.first, ByteWidth);
					this->StoppedOnIVMemRangeIterWidths[LoopIndexPlusOne].push_back(InsertValue);
				}
			}
			else {
				LowerBoundExpr->EvaluateConsts();
				LowerBoundExpr->SimplifyDriver();
				// The upper bound is RDI + RCX*ByteWidth. Optimize away ByteWidth == 1.
				//  Clone the expanded and simplified RDI from LowerBoundExpr to save time.
				STARSExpression *UpperBoundExpr = new STARSExpression();
				UpperBoundExpr->SetParentFunc(this);
				UpperBoundExpr->SetParentInst(CurrInst);
				UpperBoundExpr->SetOriginalParentInst(CurrInst);
				UpperBoundExpr->SetOperator(SMP_ADD);
				UpperBoundExpr->SetLeftTree(LowerBoundExpr->Clone());
				UpperBoundExpr->SetLeftPreLoopDefAddr(LowerBoundExpr->GetLeftPreLoopDefAddr());
				STARSOpndTypePtr CounterOp = CurrInst->MakeRegOpnd(STARS_x86_R_cx);
				STARSDefUseIter CounterUseIter = CurrInst->FindUse(CounterOp);
				assert(CounterUseIter != CurrInst->GetLastUse());
				if (1 == ByteWidth) { // Simplify RCX * 1 to RCX
					UpperBoundExpr->SetRightOperand(CounterOp);
					UpperBoundExpr->SetRightUseAddr(InstAddr);
					UpperBoundExpr->SetRightSSANum(CounterUseIter->GetSSANum());
				}
				else { // Create RCX*ByteWidth right tree.
					STARSExpression *RightTree = new STARSExpression();
					RightTree->SetParentFunc(this);
					RightTree->SetParentInst(CurrInst);
					RightTree->SetOriginalParentInst(CurrInst);
					RightTree->SetOperator(SMP_U_MULTIPLY);
					RightTree->SetLeftOperand(CounterOp);
					RightTree->SetLeftUseAddr(CurrInst->GetAddr());
					RightTree->SetLeftSSANum(CounterUseIter->GetSSANum());
					RightTree->SetRightOperand(CurrInst->MakeImmediateOpnd((STARS_uval_t)ByteWidth));
					UpperBoundExpr->SetRightTree(RightTree);
				}
				// Expand only the right side, as left side was expanded, simplified and cloned from lower bound.
				DepthCounter = 0;
				if (UpperBoundExpr->ExpandExpr(InstAddr, LoopNum, true, true, true, true, false, LoopRegHashes, StoppedOnIV, changed, StackPtrCopySet, DepthCounter)) {
					if (!StoppedOnIV) {