SMPFunction.cpp

// Given block # and PhiDef op_t and SSANum, return the Phi iterator or assert.
set<SMPPhiFunction, LessPhi>::iterator SMPFunction::GetPhiIterForPhiDef(size_t BlockNumber, op_t DefOp, int SSANum) {
	SMPBasicBlock *DefBlock = this->RPOBlocks.at(BlockNumber);
	set<SMPPhiFunction, LessPhi>::iterator PhiIter = DefBlock->FindPhi(DefOp);
	assert(PhiIter != DefBlock->GetLastPhi());
	return PhiIter;
}

// Is DestOp within the outgoing args area? Assume it must be an ESP-relative
//  DEF operand in order to be a write to the outgoing args area.
bool SMPFunction::IsInOutgoingArgsRegion(op_t DestOp) {
	bool OutArgWrite = false;
	int BaseReg, IndexReg;
	ushort ScaleFactor;
	ea_t offset;

	if (this->IsLeaf())
		return false;

	MDExtractAddressFields(DestOp, BaseReg, IndexReg, ScaleFactor, offset);
	if ((BaseReg != R_sp) && (IndexReg != R_sp))
		return false;
	if (((BaseReg == R_sp) && (IndexReg != R_none))
		|| ((IndexReg == R_sp) && (BaseReg != R_none))
		|| (0 < ScaleFactor)) {

#if 0
		SMP_msg("WARNING: WritesToOutgoingArgs called with indexed write.");
		PrintOperand(DestOp);
#endif
		return false;
	}

	if (!this->OutgoingArgsComputed) {
		OutArgWrite = true; // be conservative
	}
	else {
		OutArgWrite = (offset < this->OutgoingArgsSize);
	}
	return OutArgWrite;
} // end of SMPFunction::IsInOutgoingArgsRegion()

// Is DestOp a direct memory access above the local vars frame?
bool SMPFunction::WritesAboveLocalFrame(op_t DestOp) {
	bool InArgWrite = false;
	int BaseReg, IndexReg;
	ushort ScaleFactor;
	ea_t offset;
	long SignedOffset;

	MDExtractAddressFields(DestOp, BaseReg, IndexReg, ScaleFactor, offset);
	SignedOffset = (long) offset;
	bool ESPrelative = (BaseReg == R_sp) || (IndexReg == R_sp);
	bool EBPrelative = this->UseFP && ((BaseReg == R_bp) || (IndexReg == R_bp));
	if (!(ESPrelative || EBPrelative))
		return false;
	if (((IndexReg != R_none) && (BaseReg != R_none))
		|| (0 < ScaleFactor)) {

		SMP_msg("WARNING: WritesAboveLocalFrame called with indexed write.");
		PrintOperand(DestOp);
		return false;
	}

	InArgWrite = (ESPrelative && (SignedOffset > ((long) this->LocalVarsSize)))
		|| (EBPrelative && (SignedOffset > 0));

	return InArgWrite;
}// end of SMPFunction::WritesAboveLocalFrame()

// Is DestOp an indexed write above the local vars frame?
bool SMPFunction::IndexedWritesAboveLocalFrame(op_t DestOp) {
	bool InArgWrite = false;
	int BaseReg, IndexReg;
	ushort ScaleFactor;
	ea_t offset;
	int SignedOffset;

	MDExtractAddressFields(DestOp, BaseReg, IndexReg, ScaleFactor, offset);
	bool ESPrelative = (BaseReg == R_sp) || (IndexReg == R_sp);
	bool EBPrelative = this->UseFP && ((BaseReg == R_bp) || (IndexReg == R_bp));
	if (!(ESPrelative || EBPrelative))
		return false;

	SignedOffset = (int) offset;
	InArgWrite = (ESPrelative && (SignedOffset > this->LocalVarsSize))
		|| (EBPrelative && (SignedOffset > 0));

	return InArgWrite;
}	 // end of SMPFunction::IndexedWritesAboveLocalFrame

// Find evidence of calls to alloca(), which appear as stack space allocations (i.e.
//  subtractions from the stack pointer) AFTER the local frame allocation instruction
//  for this function.
// Return true if such an allocation is found and false otherwise.
bool SMPFunction::FindAlloca(void) {
	list<SMPInstr *>::iterator CurrInst = this->Instrs.begin();
#if SMP_USE_SSA_FNOP_MARKER
	++CurrInst;  // skip marker instruction
#endif
	for ( ; CurrInst != this->Instrs.end(); ++CurrInst) {
		if (((*CurrInst)->GetAddr() > this->LocalVarsAllocInstr) && (*CurrInst)->MDIsFrameAllocInstr()) {
			return true;
		}
	}
	return false;
} // end of SMPFunction::FindAlloca()

// Emit the annotations describing the regions of the stack frame.
void SMPFunction::EmitStackFrameAnnotations(FILE *AnnotFile, SMPInstr *Instr) {
	ea_t addr = Instr->GetAddr();

#if 0
	if (0 < IncomingArgsSize) {
		SMP_fprintf(AnnotFile, "%10x %6d INARGS STACK esp + %d %s \n",
				addr, IncomingArgsSize,
				(LocalVarsSize + CalleeSavedRegsSize + RetAddrSize),
				Instr->GetDisasm());
	}
#endif
	if (0 < this->RetAddrSize) {
		SMP_fprintf(AnnotFile, "%10x %6d MEMORYHOLE STACK esp + %d ReturnAddress \n",
				addr, RetAddrSize, (this->LocalVarsSize + this->CalleeSavedRegsSize));
	}
	if (0 < this->CalleeSavedRegsSize) {
		SMP_fprintf(AnnotFile, "%10x %6u MEMORYHOLE STACK esp + %d CalleeSavedRegs \n",
				addr, this->CalleeSavedRegsSize, this->LocalVarsSize);
	}
	if ((0 < this->LocalVarsSize) && this->GoodLocalVarTable) {
		unsigned long ParentReferentID = DataReferentID++;
		SMP_fprintf(AnnotFile, "%10x %6u DATAREF STACK %ld esp + %d PARENT LocalFrame LOCALFRAME\n",
				addr, this->LocalVarsSize, ParentReferentID, 0);
#if SMP_COMPUTE_STACK_GRANULARITY
		if (this->AnalyzedSP && !this->CallsAlloca && (BADADDR != this->LocalVarsAllocInstr)) {
			// We can only fine-grain the stack frame if we were able to analyze the stack
			if (this->OutgoingArgsSize > 0) {
				SMP_fprintf(AnnotFile, "%10x %6u DATAREF STACK %ld esp + %d CHILDOF %ld OFFSET %d OutArgsRegion OUTARGS\n",
					addr, this->OutgoingArgsSize, DataReferentID, 0, ParentReferentID, 0);
				++DataReferentID;
			}
#if SMP_DEBUG_STACK_GRANULARITY
			SMP_msg("LocalVarTable of size %d for function %s\n", this->LocalVarTable.size(),
				this->GetFuncName());
#endif
			for (size_t i = 0; i < this->LocalVarTable.size(); ++i) {
#if SMP_DEBUG_STACK_GRANULARITY
				SMP_msg("Entry %d offset %ld size %d name %s\n", i, this->LocalVarTable[i].offset,
					this->LocalVarTable[i].size, this->LocalVarTable[i].VarName);
#endif
				// Don't emit annotations for incoming or outgoing args or anything else
				//  above or below the current local frame.
				if ((this->LocalVarTable[i].offset >= (long) this->FuncInfo.frsize)
					|| (this->LocalVarTable[i].offset < (long) this->OutgoingArgsSize))
					continue;
				SMP_fprintf(AnnotFile, "%10x %6u DATAREF STACK %ld esp + %ld CHILDOF %ld OFFSET %ld LOCALVAR %s \n",
					addr, this->LocalVarTable[i].size, DataReferentID,
					this->LocalVarTable[i].offset, ParentReferentID,
					this->LocalVarTable[i].offset, this->LocalVarTable[i].VarName);
				++DataReferentID;
			}
		} // end if (this->AnalyzedSP and not Alloca .... )
#endif
	} // end if (0 < LocalVarsSize)
	return;
} // end of SMPFunction::EmitStackFrameAnnotations() 

// Main data flow analysis driver. Goes through the function and
//  fills all objects for instructions, basic blocks, and the function
//  itself.
void SMPFunction::Analyze(void) {
	bool FoundAllCallers = false;
	list<SMPInstr *>::iterator FirstInBlock = this->Instrs.end();
	   // For starting a basic block
	list<SMPInstr *>::iterator LastInBlock = this->Instrs.end();
	   // Terminating a basic block
	sval_t CurrStackPointerOffset = 0;
	ea_t InstAddr; // grab address to help in debugging, conditional breakpoints, etc.

#if SMP_DEBUG_CONTROLFLOW
	SMP_msg("Entering SMPFunction::Analyze.\n");
#endif

	// Get some basic info from the FuncInfo structure.
	this->Size = this->FuncInfo.endEA - this->FuncInfo.startEA;
	this->UseFP = (0 != (this->FuncInfo.flags & (FUNC_FRAME | FUNC_BOTTOMBP)));
	this->StaticFunc = (0 != (this->FuncInfo.flags & FUNC_STATIC));
	this->LibFunc = (0 != (this->FuncInfo.flags & FUNC_LIB));
	this->BlockCount = 0;
	this->AnalyzedSP = this->FuncInfo.analyzed_sp();

#if SMP_DEBUG_CONTROLFLOW
	SMP_msg("SMPFunction::Analyze: got basic info.\n");
#endif

	// Determine if we are dealing with shared chunks.
	size_t ChunkCounter = 0;
	func_tail_iterator_t FuncTail(this->GetFuncInfo());
	for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
		++ChunkCounter;
		if (1 < ChunkCounter) {
			this->SharedChunks = true;
#if SMP_DEBUG_CHUNKS
			const area_t &CurrChunk = FuncTail.chunk();
			SMP_msg("Found tail chunk for %s at %x\n", this->GetFuncName(), CurrChunk.startEA);
#endif
		}
	}

	// Cycle through all chunks that belong to the function.
	ChunkCounter = 0;
	bool GoodRTL;
	this->BuiltRTLs = (!this->SharedChunks);
 	for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
		const area_t &CurrChunk = FuncTail.chunk();
		++ChunkCounter;
		// Build the instruction and block lists for the function.
		for (ea_t addr = CurrChunk.startEA; addr < CurrChunk.endEA;
			addr = get_item_end(addr)) {
			flags_t InstrFlags = getFlags(addr);
			if (isHead(InstrFlags) && isCode(InstrFlags)) {
				SMPInstr *CurrInst = new SMPInstr(addr);
				// Fill in the instruction data members.
#if SMP_DEBUG_CONTROLFLOW
				SMP_msg("SMPFunction::Analyze: calling CurrInst::Analyze.\n");
#endif
				CurrInst->Analyze();
				if (SMPBinaryDebug) {
					SMP_msg("Disasm:  %s \n", CurrInst->GetDisasm());
				}
#if SMP_COUNT_MEMORY_ALLOCATIONS
				SMPInstBytes += sizeof(*CurrInst);
#endif

#if SMP_USE_SSA_FNOP_MARKER
				if (this->Instrs.empty()) {
					// First instruction in function. We want to create a pseudo-instruction
					//  at the top of the function that can hold SSA DEFs for LiveIn names
					//  to the function. We use a floating point no-op as the pseudo-inst.
					//  The code address is one less than the start address of the function.
					SMPInstr *MarkerInst = new SMPInstr(addr - 1);
					MarkerInst->AnalyzeMarker();
					GoodRTL = MarkerInst->BuildRTL();
					this->BuiltRTLs = (this->BuiltRTLs && GoodRTL);
					if (GoodRTL) {
						MarkerInst->SetGoodRTL();
					}
					assert(FirstInBlock == this->Instrs.end());
					this->Instrs.push_back(MarkerInst);
#if SMP_COUNT_MEMORY_ALLOCATIONS
					SMPInstBytes += sizeof(*MarkerInst);
#endif
				}
#endif
				if (this->AnalyzedSP) {
					// Audit the IDA SP analysis.
					sval_t sp_delta = get_spd(this->GetFuncInfo(), addr);
					// sp_delta is difference between current value of stack pointer
					//  and value of the stack pointer coming into the function. It
					//  is updated AFTER each instruction. Thus, it should not get back
					//  above zero (e.g. to +4) until after a return instruction.
					if (sp_delta > 0) {
						// Stack pointer has underflowed, according to IDA's analysis,
						//  which is probably incorrect.
						this->AnalyzedSP = false;
						SMP_msg("WARNING: Resetting AnalyzedSP to false for %s\n", this->GetFuncName());
						SMP_msg("Underflowing instruction: %s sp_delta: %d\n", CurrInst->GetDisasm(),
							sp_delta);
					}
					else if (sp_delta == 0) {
						// Search for tail calls.
						if (CurrInst->IsBranchToFarChunk()) {
							// After the stack has been restored to the point at which
							//  we are ready to return, we instead find a jump to a
							//  far chunk. This is the classic tail call optimization:
							//  the return statement has been replaced with a jump to
							//  another function, which will return not to this function,
							//  but to the caller of this function.
							CurrInst->SetTailCall();
							SMP_msg("Found tail call at %x from %s: %s\n", addr, this->GetFuncName(),
								CurrInst->GetDisasm());
						}
					}
				}

				// Find all functions that call the current function.
				SMP_xref_t CurrXrefs;
				if (!FoundAllCallers) {
					for (bool ok = CurrXrefs.SMP_first_to(CurrInst->GetAddr(), XREF_ALL);
						ok;
						ok = CurrXrefs.SMP_next_to()) {
						if ((CurrXrefs.GetFrom() != 0) && (CurrXrefs.GetIscode())) {
							// Make sure it is not a fall-through. Must be a
							//  control-flow instruction of some sort, including
							//  direct or indirect calls or tail calls.
							SMPInstr CallInst(CurrXrefs.GetFrom());
							CallInst.Analyze();
							SMPitype CallType = CallInst.GetDataFlowType();
							if ((COND_BRANCH <= CallType) && (RETURN >= CallType)) {
								// Found a caller, with its call address in CurrXrefs.from
								this->AddCallSource(CurrXrefs.GetFrom());
							}
						}
					}
					FoundAllCallers = true; // only do this for first inst
				}

				SMPitype DataFlowType = CurrInst->GetDataFlowType();
				if ((DataFlowType == INDIR_CALL) || (DataFlowType == CALL)) {
					// See if IDA has determined the target of the call.
					ea_t TargetAddr = CurrInst->GetCallTarget();
					bool LinkedToTarget = (BADADDR != TargetAddr);
					if (LinkedToTarget) {
						if (0 == TargetAddr) {
							SMP_msg("WARNING: Ignoring NULL call target (unreachable) at %x\n", CurrInst->GetAddr());
						}
						else {
							this->AllCallTargets.push_back(TargetAddr);
							if (INDIR_CALL == DataFlowType) {
								this->IndirectCallTargets.push_back(TargetAddr);
							}
							else {
								this->DirectCallTargets.push_back(TargetAddr);
							}
						}
					}
					if (DataFlowType == INDIR_CALL) {
						this->IndirectCalls = true;
						this->UnresolvedIndirectCalls = (!LinkedToTarget);
					}
				} // end if INDIR_CALL or CALL
				else if (DataFlowType == INDIR_JUMP)
					this->IndirectJumps = true;

				// Before we insert the instruction into the instruction
				//  list, determine if it is a jump target that does not
				//  follow a basic block terminator. This is the special case
				//  of a CASE in a SWITCH that falls through into another
				//  CASE, for example. The first sequence of statements
				//  was not terminated by a C "break;" statement, so it
				//  looks like straight line code, but there is an entry
				//  point at the beginning of the second CASE sequence and
				//  we have to split basic blocks at the entry point.
				if ((FirstInBlock != this->Instrs.end())
					&& CurrInst->IsJumpTarget()) {
#if SMP_DEBUG_CONTROLFLOW
					SMP_msg("SMPFunction::Analyze: hit special jump target case.\n");
#endif
					LastInBlock = --(this->Instrs.end());
					SMPBasicBlock *NewBlock = new SMPBasicBlock(this, FirstInBlock,
						LastInBlock);
					// If not the first chunk in the function, it is a shared
					//  tail chunk.
					if (ChunkCounter > 1) {
						NewBlock->SetShared();
					}
					FirstInBlock = this->Instrs.end();
					LastInBlock = this->Instrs.end();
					this->Blocks.push_back(NewBlock);
					this->BlockCount += 1;
				}

#if SMP_DEBUG_CONTROLFLOW
		SMP_msg("SMPFunction::Analyze: putting CurrInst on list.\n");
#endif
				if (!this->SharedChunks) {
					// Build tree RTLs for the instruction.
					GoodRTL = CurrInst->BuildRTL();
					this->BuiltRTLs = (this->BuiltRTLs && GoodRTL);
					if (GoodRTL) {
						CurrInst->SetGoodRTL();
					}
#if SMP_DEBUG_BUILD_RTL
					if (!GoodRTL) {
						SMP_msg("ERROR: Cannot build RTL at %x for %s\n", CurrInst->GetAddr(), 
							CurrInst->GetDisasm());
					}
#endif
				}

				// Insert instruction at end of list.
				this->Instrs.push_back(CurrInst);

				// Find basic block leaders and terminators.
				if (FirstInBlock == this->Instrs.end()) {
#if SMP_DEBUG_CONTROLFLOW
					SMP_msg("SMPFunction::Analyze: setting FirstInBlock.\n");
#endif
#if SMP_USE_SSA_FNOP_MARKER
					if (2 == this->Instrs.size()) {
						// Just pushed first real instruction, after the fnop marker.
						FirstInBlock = this->Instrs.begin();
					}
					else {
						FirstInBlock = --(this->Instrs.end());
					}
#else
					FirstInBlock = --(this->Instrs.end());
#endif
				}
				if (CurrInst->IsBasicBlockTerminator()) {
#if SMP_DEBUG_CONTROLFLOW
		SMP_msg("SMPFunction::Analyze: found block terminator.\n");
#endif
					LastInBlock = --(this->Instrs.end());
					SMPBasicBlock *NewBlock = new SMPBasicBlock(this, FirstInBlock, LastInBlock);
					// If not the first chunk in the function, it is a shared
					//  tail chunk.
					if (ChunkCounter > 1) {
						NewBlock->SetShared();
					}
					FirstInBlock = this->Instrs.end();
					LastInBlock = this->Instrs.end();
					this->Blocks.push_back(NewBlock);
					this->BlockCount += 1;

					// Is the instruction a branch to a target outside the function? If
					//  so, this function has shared tail chunks.
					if (CurrInst->IsBranchToFarChunk() && (!CurrInst->IsTailCall())) {
						this->SharedChunks = true;
					}
				}
			} // end if (isHead(InstrFlags) && isCode(InstrFlags)
		} // end for (ea_t addr = CurrChunk.startEA; ... )

		// Handle the special case in which a function does not terminate
		//  with a return instruction or any other basic block terminator.
		//  Sometimes IDA Pro sees a call to a NORET function and decides
		//  to not include the dead code after it in the function. That
		//  dead code includes the return instruction, so the function no
		//  longer includes a return instruction and terminates with a CALL.
		if (FirstInBlock != this->Instrs.end()) {
			LastInBlock = --(this->Instrs.end());
			SMPBasicBlock *NewBlock = new SMPBasicBlock(this, FirstInBlock, LastInBlock);
			// If not the first chunk in the function, it is a shared
			//  tail chunk.
			if (ChunkCounter > 1) {
				NewBlock->SetShared();
			}
			FirstInBlock = this->Instrs.end();
			LastInBlock = this->Instrs.end();
			this->Blocks.push_back(NewBlock);
			this->BlockCount += 1;
		}
	} // end for (bool ChunkOK = ...)

	// Now that we have all instructions and basic blocks, link each instruction
	//  to its basic block. Note that the instruction has to be linked to the copy
	//  of the basic block in this->Blocks(), not to the original SMPBasicBlock
	//  object that was constructed and destructed on the stack above. (Ouch!
	//  Very painful memory corruption debugging lesson.)
	list<SMPBasicBlock *>::iterator BlockIter;
	SMPBasicBlock *CurrBlock;
	list<SMPInstr *>::iterator InstIter;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
			SMPInstr *CurrInst = (*InstIter);
			CurrInst->SetBlock(CurrBlock->GetThisBlock());
		}
	}

#if KLUDGE_VFPRINTF_FAMILY
	if (0 != strstr(this->GetFuncName(), "printf")) {
		this->SharedChunks = true;
		SMP_msg("Kludging function %s\n", this->GetFuncName());
	}
#endif

#if SMP_IDAPRO52_WORKAROUND
	if (0 == strcmp(this->GetFuncName(), "error_for_asm")) {
		this->SharedChunks = true;
		SMP_msg("Kludging function %s\n", this->GetFuncName());
	}
#endif

	// Set up basic block links and map of instructions to blocks.
	if (!(this->HasSharedChunks())) {
		this->SetLinks();
		this->RPONumberBlocks();

		// Figure out the stack frame and related info.
		this->SetStackFrameInfo();

		list<SMPInstr *>::iterator InstIter;
		SMPInstr *CurrInst;
		for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
			CurrInst = (*InstIter);
			InstAddr = CurrInst->GetAddr(); // for debugging
			if (CurrInst->HasGoodRTL())
				CurrInst->SyncAllRTs();
			// Detect indirect memory references.
			CurrInst->AnalyzeIndirectRefs(this->UseFP);
		} // end for all instructions
	} // end if not shared chunks
	else { // has shared chunks; still want to compute stack frame info
#if SMP_DEBUG_CONTROLFLOW
		SMP_msg("SMPFunction::Analyze: set stack frame info.\n");
#endif
#ifdef SMP_DEBUG_FUNC
		SMP_msg(" %s has shared chunks \n", this->GetFuncName());
#endif
		// Figure out the stack frame and related info.
		this->SetStackFrameInfo();
	}

	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		(*BlockIter)->Analyze();
	}

	// Audit the call instructions and call targets.
	if ((!this->AllCallTargets.empty()) || this->UnresolvedIndirectCalls) {
		bool FoundBadCallTarget = false;
		vector<ea_t>::iterator CurrTarget = this->AllCallTargets.begin();
		while (CurrTarget != this->AllCallTargets.end()) {
			if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
				// Found a call target that is within the function.
				FoundBadCallTarget = true;
				if (this->FirstEA == *CurrTarget) { // Direct recursion, not a pseudo-jump
					this->DirectlyRecursive = true;
				}
				CurrTarget = this->AllCallTargets.erase(CurrTarget);
			}
			else {
				++CurrTarget;
			}
		}
		if (FoundBadCallTarget) {
			// We have to mark the pseudo-call instructions and audit the direct and
			//  indirect call target vectors.

			// Audit direct call targets.
			CurrTarget = this->DirectCallTargets.begin();
			while (CurrTarget != this->DirectCallTargets.end()) {
				if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
					// Found a call target that is within the function.
					CurrTarget = this->DirectCallTargets.erase(CurrTarget);
				}
				else {
					++CurrTarget;
				}
			}
			// Audit indirect call targets.
			CurrTarget = this->IndirectCallTargets.begin();
			while (CurrTarget != this->IndirectCallTargets.end()) {
				if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
					// Found a call target that is within the function.
					CurrTarget = this->IndirectCallTargets.erase(CurrTarget);
				}
				else {
					++CurrTarget;
				}
			}
			// Find calls used as jumps.
			list<SMPInstr *>::iterator InstIter = this->Instrs.begin();
			while (InstIter != this->Instrs.end()) {
				SMPInstr *CurrInst = (*InstIter);
				SMPitype InstFlow = CurrInst->GetDataFlowType();
				if ((CALL == InstFlow) || (INDIR_CALL == InstFlow)) {
					CurrInst->AnalyzeCallInst(this->FirstEA, this->FuncInfo.endEA);
				}
				++InstIter;
			}
		} // end if (FoundBadCallTarget)
	}

	this->MarkFunctionSafe();

#if SMP_COUNT_MEMORY_ALLOCATIONS
	SMPInstCount += ((unsigned long) this->Instrs.size());
	SMPBlockCount += ((unsigned long) this->Blocks.size());
	SMPLocalVarCount += ((unsigned long) this->LocalVarTable.size());
#endif

} // end of SMPFunction::Analyze()


// Free memory that is no longer needed after loop 2 of SMPProgram::Analyze().
void SMPFunction::FreeUnusedMemory2(void) {
	size_t UnusedElements;
	size_t CurrSize;

	// Go through vector containers and resize to current capacity, if the vector
	//  has been fully computed by the time SMPProgram:Analyze() loop 2 completes.
	CurrSize = this->DirectCallTargets.size();
	UnusedElements = this->DirectCallTargets.capacity() - CurrSize;
	if (0 < UnusedElements) {
		UnusedIntCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<ea_t>(this->DirectCallTargets).swap(this->DirectCallTargets);
#else
		this->DirectCallTargets.resize(CurrSize);
#endif
	}

	CurrSize = this->IndirectCallTargets.size();
	UnusedElements = this->IndirectCallTargets.capacity() - CurrSize;
	if (0 < UnusedElements) {
		UnusedIntCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<ea_t>(this->IndirectCallTargets).swap(this->IndirectCallTargets);
#else
		this->IndirectCallTargets.resize(CurrSize);
#endif
	}

	CurrSize = this->AllCallTargets.size();
	UnusedElements = this->AllCallTargets.capacity() - CurrSize;
	if (0 < UnusedElements) {
		UnusedIntCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<ea_t>(this->AllCallTargets).swap(this->AllCallTargets);
#else
		this->AllCallTargets.resize(CurrSize);
#endif
	}

	CurrSize = this->SavedRegLoc.size();
	UnusedElements = this->SavedRegLoc.capacity() - CurrSize;
	if (0 < UnusedElements) {
		UnusedIntCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<int>(this->SavedRegLoc).swap(this->SavedRegLoc);
#else
		this->SavedRegLoc.resize(CurrSize);
#endif
	}

	CurrSize = this->RPOBlocks.size();
	UnusedElements = this->RPOBlocks.capacity() - CurrSize;
	if (0 < UnusedElements) {
		list<SMPBasicBlock *>::iterator DummyIter = this->Blocks.end();
		UnusedIntCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<SMPBasicBlock *>(this->RPOBlocks).swap(this->RPOBlocks);
#else
		this->RPOBlocks.resize(CurrSize, DummyIter);
#endif
	}

	CurrSize = this->LocalVarTable.size();
	UnusedElements = this->LocalVarTable.capacity() - CurrSize;
	if (0 < UnusedElements) {
		struct LocalVar DummyVar;
		DummyVar.offset = 0;
		DummyVar.size = 0;
		UnusedStructCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<struct LocalVar>(this->LocalVarTable).swap(this->LocalVarTable);
#else
		this->LocalVarTable.resize(CurrSize, DummyVar);
#endif
	}

	CurrSize = this->StackFrameMap.size();
	UnusedElements = this->StackFrameMap.capacity() - CurrSize;
	if (0 < UnusedElements) {
		struct StackFrameEntry DummyEntry;
		DummyEntry.offset = 0;
		DummyEntry.VarPtr = NULL;
		UnusedStructCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<struct StackFrameEntry>(this->StackFrameMap).swap(this->StackFrameMap);
#else
		this->StackFrameMap.resize(CurrSize, DummyEntry);
#endif
	}

	CurrSize = this->FineGrainedStackTable.size();
	UnusedElements = this->FineGrainedStackTable.capacity() - CurrSize;
	if (0 < UnusedElements) {
		struct FineGrainedInfo DummyFG;
		DummyFG.SignMiscInfo = 0;
		DummyFG.SizeInfo = 0;
		UnusedStructCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<struct FineGrainedInfo>(this->FineGrainedStackTable).swap(this->FineGrainedStackTable);
#else
		this->FineGrainedStackTable.resize(CurrSize, DummyFG);
#endif
	}

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

// Free memory that is no longer needed after loop 3 of SMPProgram::Analyze().
void SMPFunction::FreeUnusedMemory3(void) {
	size_t UnusedElements;
	size_t CurrSize;

	// Go through vector containers and resize to current capacity, if the vector
	//  has been fully computed by the time SMPProgram:Analyze() loop 2 completes.
	CurrSize = this->ReturnRegTypes.size();
	UnusedElements = this->ReturnRegTypes.capacity() - CurrSize;
	if (0 < UnusedElements) {
		UnusedIntCount += (unsigned long) UnusedElements;
#if SMP_SHRINK_TO_FIT
		std::vector<SMPOperandType>(this->ReturnRegTypes).swap(this->ReturnRegTypes);
#else		
		this->ReturnRegTypes.resize(CurrSize);
#endif
	}

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

// Free memory that is no longer needed after type inference (loop 4 of SMPProgram::Analyze()).
void SMPFunction::FreeUnusedMemory4(void) {
	this->KillSet.clear();
	this->LiveOutSet.clear();
	this->LiveInSet.clear();
	this->StackFrameMap.clear();
	this->BlocksDefinedIn.clear();

#if SMP_SHRINK_TO_FIT
	std::set<op_t, LessOp>(this->KillSet).swap(this->KillSet);
	std::set<op_t, LessOp>(this->LiveOutSet).swap(this->LiveOutSet);
	std::set<op_t, LessOp>(this->LiveInSet).swap(this->LiveInSet);
#endif

	list<SMPBasicBlock *>::iterator BlockIter;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		(*BlockIter)->FreeUnusedMemory4();
	}
	return;
} // end of SMPFunction::FreeUnusedMemory4()

// Free SSA data structures that are no longer needed when all SSA numbers have
//  been recorded in DEFs and USEs.
void SMPFunction::FreeSSAMemory(void) {
	this->IDom.clear();
	this->DomTree.clear();
	this->BlocksDefinedIn.clear();
	this->SSACounter.clear();
	this->SSAStack.clear();

#if SMP_SHRINK_TO_FIT
	vector<int>(this->IDom).swap(this->IDom);
	vector<pair<int, list<int> > >(this->DomTree).swap(this->DomTree);
	vector<list<int> >(this->BlocksDefinedIn).swap(this->BlocksDefinedIn);
	vector<int>(this->SSACounter).swap(this->SSACounter);
	vector<list<int> >(this->SSAStack).swap(this->SSAStack);
#endif

	list<SMPBasicBlock *>::iterator BlockIter;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		(*BlockIter)->FreeSSAMemory();
	}
	return;
} // end of SMPFunction::FreeSSAMemory()

// For each instruction, mark the non-flags-reg DEFs as having live
//  metadata (mmStrata needs to fetch and track this metadata for this
//  instruction) or dead metadata (won't be used as addressing reg, won't
//  be stored to memory, won't be returned to caller).
void SMPFunction::AnalyzeMetadataLiveness(void) {
	bool changed;
	int BaseReg;
	int IndexReg;
	ushort ScaleFactor;
	ea_t offset;
	op_t BaseOp, IndexOp, ReturnOp, DefOp, UseOp;
	BaseOp.type = o_reg;
	IndexOp.type = o_reg;
	ReturnOp.type = o_reg;
	list<SMPInstr *>::iterator InstIter;
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	set<DefOrUse, LessDefUse>::iterator NextUse;
	bool DebugFlag = false;
	int IterationCount = 0;

#if SMP_DEBUG_DATAFLOW
	if (0 == strcmp("uw_frame_state_for", this->GetFuncName())) {
		DebugFlag = true;
	}
#endif

	do {
		changed = false;
		++IterationCount;
		bool SafeMemDest;
		if (DebugFlag) {
			SMP_msg("AnalyzeMetadataLiveness iteration count: %d \n", IterationCount);
		}
		for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
			SMPInstr *CurrInst = (*InstIter);
			ea_t InstAddr = CurrInst->GetAddr();
			SafeMemDest = false;  // true for some SafeFunc instructions
			// Skip the SSA marker instruction.
			if (NN_fnop == CurrInst->GetCmd().itype)
				continue;

			if (DebugFlag) {
				SMP_msg("Inst addr: %x \n", CurrInst->GetAddr());
			}
			CurrDef = CurrInst->GetFirstDef();
			while (CurrDef != CurrInst->GetLastDef()) {
				if (DEF_METADATA_UNANALYZED == CurrDef->GetMetadataStatus()) {
					DefOp = CurrDef->GetOp();
					// Handle special registers never used as address regs.
					if (DefOp.is_reg(X86_FLAGS_REG)
						|| ((o_trreg <= DefOp.type) && (o_xmmreg >= DefOp.type))) {
						CurrDef = CurrInst->SetDefMetadata(DefOp,
							DEF_METADATA_UNUSED);
						changed = true;
					}
					else if (DefOp.is_reg(R_sp) 
						|| (this->UseFP && DefOp.is_reg(R_bp))) {
						// Stack pointer register DEFs always have live
						//  metadata, but we don't need to propagate back
						//  through particular DEF-USE chains.
						CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_USED);
						changed = true;
					}
					else if ((o_mem <= DefOp.type) && (o_displ >= DefOp.type)) {
						// DEF is a memory operand. The addressing registers
						//  therefore have live metadata, and the memory metadata is live.
						// EXCEPTION: If the function is Safe, then direct stack writes
						//  to local variables (above the outgoing args area of the frame)
						//  are not live metadata, and there will be no indirect local frame
						//  writes, by definition of "safe." So, for safe funcs, only
						//  the o_mem (globals) and indirect writes are live metadata.
						if (this->SafeFunc && MDIsStackAccessOpnd(DefOp, this->UseFP)
							&& (!this->WritesAboveLocalFrame(DefOp))
							&& (!this->IsInOutgoingArgsRegion(DefOp))) {
							++CurrDef;
							SafeMemDest = true;
							continue;
						}
						CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_USED);
						changed = true;
						MDExtractAddressFields(DefOp, BaseReg, IndexReg,
							ScaleFactor, offset);
						if (R_none != BaseReg) {
							BaseOp.reg = MDCanonicalizeSubReg((ushort) BaseReg);
							if (BaseOp.is_reg(R_sp) 
								|| (this->UseFP && BaseOp.is_reg(R_bp))) {
								; // do nothing; DEF handled by case above
							}
							else {
								CurrUse = CurrInst->FindUse(BaseOp);
								if (CurrUse == CurrInst->GetLastUse()) {
									SMP_msg("ERROR: BaseReg %d not in USE list at %x for %s\n",
										BaseOp.reg, CurrInst->GetAddr(),
										CurrInst->GetDisasm());
								}
								assert(CurrUse != CurrInst->GetLastUse());
								if (this->IsGlobalName(BaseOp)) {
									changed |= this->PropagateGlobalMetadata(BaseOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
								else {
									changed |= CurrInst->GetBlock()->PropagateLocalMetadata(BaseOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
							}
						} // end if R_none != BaseReg
						if (R_none != IndexReg) {
							IndexOp.reg = MDCanonicalizeSubReg((ushort) IndexReg);
							if (IndexOp.is_reg(R_sp) 
								|| (this->UseFP && IndexOp.is_reg(R_bp))) {
								; // do nothing; DEF handled by case above
							}
							else {
								CurrUse = CurrInst->FindUse(IndexOp);
								if (CurrUse == CurrInst->GetLastUse()) {
									SMP_msg("ERROR: IndexReg %d not in USE list at %x for %s\n",
										IndexOp.reg, CurrInst->GetAddr(),
										CurrInst->GetDisasm());
								}
								assert(CurrUse != CurrInst->GetLastUse());
								if (0 != ScaleFactor) {
									; // mmStrata knows scaled reg is NUMERIC
									// ... its metadata is not fetched
								}
								else if (this->IsGlobalName(IndexOp)) {
									changed |= this->PropagateGlobalMetadata(IndexOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
								else {
									changed |= CurrInst->GetBlock()->PropagateLocalMetadata(IndexOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
							}
						} // end if R_none != IndexReg
					} // end if X86_FLAGS_REG .. else if stack ptr ... 
				} // end if unanalyzed metadata usage
				++CurrDef;
			} // end while processing DEFs
			if ((RETURN == CurrInst->GetDataFlowType())
				|| (CurrInst->IsTailCall())   // quasi-return
				|| (CALL == CurrInst->GetDataFlowType())
				|| (INDIR_CALL == CurrInst->GetDataFlowType())) {
				// The EAX and EDX registers can be returned to the caller,
				//  which might use their metadata. They show up as USEs
				//  of the return instruction. Some library functions
				//  pass return values in non-standard ways. e.g. through
				//  EBX or EDI, so we treat all return regs the same.
				// For CALL instructions, values can be passed in caller-saved
				//  registers, unfortunately, so the metadata is live-in.
				CurrUse = CurrInst->GetFirstUse();
				while (CurrUse != CurrInst->GetLastUse()) {
					NextUse = CurrUse;
					++NextUse;
					ReturnOp = CurrUse->GetOp();
					if (DebugFlag) {
						SMP_msg("ReturnOp: ");
						PrintOperand(ReturnOp);
						SMP_msg("\n");
					}
					if ((o_reg == ReturnOp.type) &&
						(!ReturnOp.is_reg(X86_FLAGS_REG))) {
						if (this->IsGlobalName(ReturnOp)) {
							changed |= this->PropagateGlobalMetadata(ReturnOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(ReturnOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
					}
					CurrUse = NextUse;
				} // end while all USEs
			} // end if return or call
			else if (CurrInst->HasDestMemoryOperand() 
				|| CurrInst->MDIsPushInstr()) {
				// Memory writes cause a lot of metadata usage.
				//  Addressing registers in the memory destination
				//  have live metadata used in bounds checking. The
				//  register being stored to memory could end up being
				//  used in some other bounds checking, unless we 
				//  have precise memory tracking and know that it
				//  won't.
				// We handled the addressing registers above, so we
				//  handle the register written to memory here.
				// The same exception applies as above: If the destination
				//  memory operand is not a stack write, then safe functions
				//  do not need to track the metadata.
				// If we push a register and have callees, the metadata could
				//  be live, if the callee gets its incoming args from our push
				//  instructions.
				if (SafeMemDest && !(CurrInst->MDIsPushInstr() && !this->IsLeaf())) {
					continue;  // go to next instruction
				}
				CurrUse = CurrInst->GetFirstUse();
				while (CurrUse != CurrInst->GetLastUse()) {
					NextUse = CurrUse;
					++NextUse;
					UseOp = CurrUse->GetOp();
					// NOTE: **!!** To be less conservative, we
					//  should propagate less for exchange category
					//  instructions.
					if ((UseOp.type == o_reg) && (!UseOp.is_reg(R_sp))
						&& (!(this->UseFP && UseOp.is_reg(R_bp)))
						&& (!UseOp.is_reg(X86_FLAGS_REG))) {

						if (this->IsGlobalName(UseOp)) {
							changed |= this->PropagateGlobalMetadata(UseOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(UseOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
					} // end if register
					CurrUse = NextUse;
				} // end while all USEs
			} // end if call or return else if memdest ...
		} // end for all instructions
	} while (changed);

	// All DEFs that still have status DEF_METADATA_UNANALYZED can now
	//  be marked as DEF_METADATA_UNUSED.
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		if (NN_fnop == CurrInst->GetCmd().itype)
			continue;
		CurrDef = CurrInst->GetFirstDef();
		while (CurrDef != CurrInst->GetLastDef()) {
			if (DEF_METADATA_UNANALYZED == CurrDef->GetMetadataStatus()) {
				CurrDef = CurrInst->SetDefMetadata(CurrDef->GetOp(),
					DEF_METADATA_UNUSED);
				assert(CurrDef != CurrInst->GetLastDef());
			}
			++CurrDef;
		}
	}

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

// Propagate the metadata Status for UseOp/SSANum to its global DEF.
// Return true if successful.
bool SMPFunction::PropagateGlobalMetadata(op_t UseOp, SMPMetadataType Status, int SSANum) {
	bool changed = false;

	if ((0 > SSANum) || (o_void == UseOp.type))
		return false;