SMPFunction.cpp

			LastInBlock = this->Instrs.end();
			this->Blocks.push_back(NewBlock);
			this->BlockCount += 1;
		}
	} // end for (bool ChunkOK = ...)

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

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

	// Now that we have all instructions and basic blocks, link each instruction
	//  to its basic block. 
	list<SMPBasicBlock *>::iterator BlockIter;
	SMPBasicBlock *CurrBlock;
	vector<SMPInstr *>::iterator InstIter;
	SMPInstr *CurrInst;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		for (InstIter = CurrBlock->GetFirstInst(); InstIter != CurrBlock->GetLastInst(); ++InstIter) {
			CurrInst = (*InstIter);
			InstAddr = CurrInst->GetAddr();
			CurrInst->SetBlock(CurrBlock->GetThisBlock());

#if 0
			if (this->AnalyzedSP) {
				// Audit the IDA SP analysis.
				sval_t sp_delta = get_spd(this->GetFuncInfo(), InstAddr);
				// 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) {
#if 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", InstAddr, this->GetFuncName(),
							CurrInst->GetDisasm());
					}
#endif
					;
				}
				else if (CurrInst->IsBranchToFarChunk() && (!this->HasSharedChunks())) {
					SMP_msg("WARNING: Found tail call branch with negative stack delta at %x\n", InstAddr);
				}
			} // end if (this->AnalyzedSP)
#endif

		} // end for each inst
		CurrBlock->Analyze();
	} // end for each block

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

	FragmentWorkList.clear();
	return;
} // end of SMPFunction::Analyze()

// Perform analyses that might need some info from other functions in the call graph.
void SMPFunction::AdvancedAnalysis(void) {
	list<SMPInstr *>::iterator InstIter;
	SMPInstr *CurrInst;

	// IDA Pro has trouble with functions that do not have any local
	//  variables. Unfortunately, the C library has plenty of these
	//  functions. IDA usually claims that frregs is zero and frsize
	//  is N, when the values should have been reversed. We can attempt
	//  to detect this and fix it. IDA Pro also sometimes has trouble with
	//  functions that allocate the stack frame, and then push registers
	//  later before making a call, because it wants to include register
	//  pushes below the stack frame as being part of the stack frame,
	//  even when they are temporary saves and restores. __brk in the
	//  Gnu stdclib is an example as of November of 2012.
	bool FrameInfoFixed = this->MDFixFrameInfo();
#if SMP_DEBUG_CONTROLFLOW
	SMP_msg("Returned from MDFixFrameInfo()\n");
#endif

	this->FindAllAllocsAndDeallocs();
	this->CallsAlloca = this->FindAlloca();

#if 1
	InstIter = this->Instrs.begin();
	if ((*InstIter)->IsFloatNop()) {
		++InstIter; // skip marker inst
	}
	for ( ; InstIter != this->Instrs.end(); ++InstIter) {
		CurrInst = (*InstIter);
		// We can finally search for stack loads now that UseFP has been fixed by
		//  MDFixUseFP(). Otherwise, we would do this in SMPInstr::Analyze(),
		//  but the UseFP flag is not ready that early.
		CurrInst->MDFindLoadFromStack(this->UseFP);

		// Fix up machine dependent quirks in the def and use lists.
		//  This used to be called from within SMPInstr.Analyze(), but info such as UseFP
		//  is not available that early.
		CurrInst->MDFixupDefUseLists();
	}
#endif
	InstIter = this->Instrs.begin();
	if ((*InstIter)->IsFloatNop()) {
		++InstIter; // skip marker inst
	}
	for ( ; InstIter != this->Instrs.end(); ++InstIter) {
		CurrInst = (*InstIter);
		ea_t InstAddr = CurrInst->GetAddr(); // for debugging breakpoints
		if (CurrInst->HasGoodRTL())
			CurrInst->SyncAllRTs(this->UsesFramePointer(), this->GetFramePtrStackDelta());

		// Detect indirect memory references.
		CurrInst->AnalyzeIndirectRefs(this->UseFP);

#if 0
		// 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;
		}
#endif
	} // end for all instructions

	// Audit the call instructions and call targets.
	//  !!!!****!!!! NOTE: Not sure the address range checks in this code are valid
	//   for functions with scattered chunks.
	if ((!this->AllCallTargets.empty()) || this->UnresolvedIndirectCalls) {
		bool FoundInternalCallTarget = false;
		vector<ea_t>::iterator CurrTarget = this->AllCallTargets.begin();
		set<ea_t>::iterator CurrDirectTarget, CurrIndirectTarget;
		while (CurrTarget != this->AllCallTargets.end()) {
			if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
				// Found a call target that is within the function.
				FoundInternalCallTarget = true;
				if (this->FirstEA == *CurrTarget) { // Direct recursion, not a pseudo-jump
					this->DirectlyRecursive = true;
				}
				CurrTarget = this->AllCallTargets.erase(CurrTarget);
			}
			else {
				++CurrTarget;
			}
		}
		if (FoundInternalCallTarget) {
			// We have to mark the pseudo-call instructions and audit the direct and
			//  indirect call target vectors.

			// Audit direct call targets.
			CurrDirectTarget = this->DirectCallTargets.begin();
			set<ea_t>::iterator CopyOfIterator;
			while (CurrDirectTarget != this->DirectCallTargets.end()) {
				ea_t TargetAddr = (*CurrDirectTarget);
				if ((this->FirstEA <= TargetAddr) && (this->FuncInfo.endEA >= TargetAddr)) {
					// Found a call target that is within the function.
					CopyOfIterator = CurrDirectTarget;
					++CopyOfIterator; // point to element after element that will be erased
					this->DirectCallTargets.erase(CurrDirectTarget);
					CurrDirectTarget = CopyOfIterator;
				}
				else {
					++CurrDirectTarget;
				}
			}
			// Audit indirect call targets.
			CurrIndirectTarget = this->IndirectCallTargets.begin();
			while (CurrIndirectTarget != this->IndirectCallTargets.end()) {
				ea_t TargetAddr = (*CurrIndirectTarget);
				if ((this->FirstEA <= TargetAddr) && (this->FuncInfo.endEA >= TargetAddr)) {
					// Found a call target that is within the function.
					CopyOfIterator = CurrIndirectTarget;
					++CopyOfIterator; // point to element after element that will be erased
					this->IndirectCallTargets.erase(CurrIndirectTarget);
					CurrIndirectTarget = CopyOfIterator;
				}
				else {
					++CurrIndirectTarget;
				}
			}
#if 1
			// 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;
			}
#endif
		} // end if (FoundInternalCallTarget)
	}

	// Figure out the stack frame and related info.
#if SMP_ANALYZE_STACK_POINTER
	(void) this->AnalyzeStackPointerDeltas();
	InstIter = this->Instrs.begin();
	if ((*InstIter)->IsFloatNop()) {
		++InstIter; // skip marker inst
	}
	for ( ; InstIter != this->Instrs.end(); ++InstIter) {
		CurrInst = (*InstIter);
		CurrInst->MDFixupCallDefUseLists();
	}
#else
	(void) this->UseIDAStackPointerDeltas();
#endif

#if SMP_DEBUG_CONTROLFLOW
	SMP_msg("SMPFunction::Analyze: set stack frame info.\n");
#endif
	if (!(this->HasSharedChunks())) {

		this->SetStackFrameInfo();

	} // end if not shared chunks
	else { // has shared chunks; still want to compute stack frame info
#ifdef SMP_DEBUG_FUNC
		SMP_msg(" %s has shared chunks \n", this->GetFuncName());
#endif
		// Figure out the stack frame and related info.
		this->SetStackFrameInfo();
	}

	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::AdvancedAnalysis()

// Count call targets that have not been processed.
size_t SMPFunction::UnprocessedCalleesCount(void) {
	size_t UnprocessedTargetsCount = 0;

	size_t TargetIndex;
	for (TargetIndex = 0; TargetIndex < this->AllCallTargets.size(); ++TargetIndex) {
		SMPFunction *CurrTarget = this->GetProg()->FindFunction(this->AllCallTargets.at(TargetIndex));
		if (NULL == CurrTarget) {
#if 0
			// Bad call targets are removed in AdvancedAnalysis(), which comes later.
			SMP_msg("ERROR: NULL CallTarget in UnprocessedCalleesCount() at TargetIndex %zu \n", TargetIndex);
#endif
		}
		else if (!(CurrTarget->IsFuncProcessed())) {
			++UnprocessedTargetsCount;
		}
	}
	return UnprocessedTargetsCount;
} // end of SMPFunction::UnprocessedCalleesCount()

ea_t SMPFunction::GetFirstUnprocessedCallee(void) {
	ea_t CalleeAddr = BADADDR;
	size_t TargetIndex;
	for (TargetIndex = 0; TargetIndex < this->AllCallTargets.size(); ++TargetIndex) {
		ea_t TargetAddr = this->AllCallTargets.at(TargetIndex);
		SMPFunction *CurrTarget = this->GetProg()->FindFunction(TargetAddr);
		if ((NULL != CurrTarget) && (!(CurrTarget->IsFuncProcessed()))) {
			CalleeAddr = TargetAddr;
			break;
		}
	}
	return CalleeAddr;
} // end of SMPFunction::GetFirstUnprocessedCallee()

// Is the code starting at TargetAddr a non-shared chunk that jumps back into our function?
//  If so, it can be incorporated into our function rather than treated as a separate function.
//  This method is called only when we see a jump outside our function, and it is looking for
//  code fragments that are not really functions (i.e. don't have a stack frame, jump straight back
//  into our function after executing a few instructions, not a chunk shared among other functions).
//  These code fragments are found in the locking and unlocking code of the gcc stdlib, for example.
bool SMPFunction::FindDistantCodeFragment(ea_t TargetAddr) {
	bool PrivateFragment = false;
	func_t *TargetFunc = get_func(TargetAddr);
	if (TargetFunc) {
		// Determine if we are dealing with shared chunks.
		size_t ChunkCounter = 0;
		func_tail_iterator_t FuncTail(TargetFunc);
		for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
			++ChunkCounter;
		}
		if (1 < ChunkCounter) {
			SMP_msg("INFO: Code fragment at %lx is shared chunk.\n", (unsigned long) TargetAddr);
		}
		else {
			bool JumpsBackIntoCurrentFunc = false;
			bool HasReturnInstruction = false;
			bool AllocatesStackFrame = false;
		 	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.
						CurrInst->Analyze();
						// Search for two negative indicators (stack allocations and returns)
						//  and one positive indicator (jump back into this function).
						if (CurrInst->MDIsReturnInstr()) {
							HasReturnInstruction = true;
							break;
						}
						else if (CurrInst->MDIsFrameAllocInstr()) {
							AllocatesStackFrame = true;
							break;
						}
						else {
							SMPitype FlowType = CurrInst->GetDataFlowType();
							if ((JUMP == FlowType) || (INDIR_JUMP == FlowType)) {
								if (CurrInst->BuildRTL()) {
									ea_t FragmentJumpTarget = CurrInst->GetJumpTarget();
									if ((FragmentJumpTarget >= this->FirstEA) && (FragmentJumpTarget <= this->FuncInfo.endEA)) {
										JumpsBackIntoCurrentFunc = true;
									}
								}
							}
						}
					} // end if isHead() and isCode()
				} // end for all addrs in chunk
			} // end for all chunks (there will only be one)
			PrivateFragment = (JumpsBackIntoCurrentFunc && (!HasReturnInstruction) && (!AllocatesStackFrame));
		} // end if (1 < ChunkCounter) ... else ...
	} // end if (TargetFunc)

	return PrivateFragment;
} // end of SMPFunction::FindDistantCodeFragment()

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

#if 0
	// 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
	}
#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->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);
#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 = InitOp, IndexOp = InitOp, ReturnOp = InitOp;
	BaseOp.type = o_reg;
	IndexOp.type = o_reg;
	ReturnOp.type = o_reg;
	list<SMPInstr *>::iterator InstIter;
	list<SMPInstr *>::reverse_iterator RevInstIter;
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	set<DefOrUse, LessDefUse>::iterator NextUse;
	bool DebugFlag = false;
	bool UseFP = this->UsesFramePointer();
	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 (RevInstIter = this->Instrs.rbegin(); RevInstIter != this->Instrs.rend(); ++RevInstIter) {
			SMPInstr *CurrInst = (*RevInstIter);
			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: %lx \n", (unsigned long) CurrInst->GetAddr());
			}
			CurrDef = CurrInst->GetFirstDef();
			while (CurrDef != CurrInst->GetLastDef()) {
				if (DEF_METADATA_UNANALYZED == CurrDef->GetMetadataStatus()) {
					op_t 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 (MDIsStackOrFramePointerReg(DefOp, UseFP)) {
						// 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, CurrInst->AreDefsNormalized()))
							&& (!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);
							BaseOp.dtyp = CurrInst->GetOperandDtypField(); // canonical reg width
							if (MDIsStackOrFramePointerReg(BaseOp, UseFP)) {
								; // do nothing; DEF handled by case above
							}
							else {
								CurrUse = CurrInst->FindUse(BaseOp);
								if (CurrUse == CurrInst->GetLastUse()) {
									SMP_msg("FATAL ERROR: BaseReg %d not in USE list at %lx for %s\n",
										BaseOp.reg, (unsigned long) CurrInst->GetAddr(),
										CurrInst->GetDisasm());
								}
								assert(CurrUse != CurrInst->GetLastUse());
								if (this->IsGlobalName(BaseOp)) {
									changed |= this->PropagateGlobalMetadata(BaseOp,
										DEF_METADATA_USED, CurrUse->GetSSANum(), InstAddr);
								}
								else {
									changed |= CurrInst->GetBlock()->PropagateLocalMetadata(BaseOp,
										DEF_METADATA_USED, CurrUse->GetSSANum(), InstAddr);
								}
							}
						} // end if R_none != BaseReg
						if (R_none != IndexReg) {
							IndexOp.reg = MDCanonicalizeSubReg((ushort) IndexReg);
							IndexOp.dtyp = CurrInst->GetOperandDtypField(); // canonical reg width
							if (MDIsStackOrFramePointerReg(IndexOp, UseFP)) {
								; // do nothing; DEF handled by case above
							}
							else {
								CurrUse = CurrInst->FindUse(IndexOp);
								if (CurrUse == CurrInst->GetLastUse()) {
									SMP_msg("FATAL ERROR: IndexReg %d not in USE list at %lx for %s\n",
										IndexOp.reg, (unsigned long) 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(), InstAddr);
								}
								else {
									changed |= CurrInst->GetBlock()->PropagateLocalMetadata(IndexOp,
										DEF_METADATA_USED, CurrUse->GetSSANum(), InstAddr);
								}
							}
						} // 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) &&
						(!MDIsStackOrFramePointerReg(ReturnOp, UseFP)) &&
						(!ReturnOp.is_reg(X86_FLAGS_REG))) {
						if (this->IsGlobalName(ReturnOp)) {
							changed |= this->PropagateGlobalMetadata(ReturnOp,
									DEF_METADATA_USED, CurrUse->GetSSANum(), InstAddr);
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(ReturnOp,
									DEF_METADATA_USED, CurrUse->GetSSANum(), InstAddr);
						}
					}
					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;
					op_t UseOp = CurrUse->GetOp();
					// NOTE: **!!** To be less conservative, we
					//  should propagate less for exchange category
					//  instructions.
					if ((UseOp.type == o_reg) && (!MDIsStackOrFramePointerReg(UseOp, UseFP)) && (!UseOp.is_reg(X86_FLAGS_REG))) {
						if (this->IsGlobalName(UseOp)) {
							changed |= this->PropagateGlobalMetadata(UseOp,
									DEF_METADATA_USED, CurrUse->GetSSANum(), InstAddr);
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(UseOp,
									DEF_METADATA_USED, CurrUse->GetSSANum(), InstAddr);
						}
					} // 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, ea_t UseAddr) {
	bool changed = false;
	bool UseFP = this->UsesFramePointer();

	if ((0 > SSANum) || (o_void == UseOp.type) || (!MDIsDataFlowOpnd(UseOp, UseFP)) || MDIsIndirectMemoryOpnd(UseOp, UseFP))
		return false;

	// Find the DEF of UseOp with SSANum.
	ea_t DefAddr;
	SMPBasicBlock *UseBlock;
	SMPBasicBlock *DefBlock;

	if (UseAddr > this->GetNumBlocks()) { // UseAddr is an inst addr
		UseBlock = this->GetBlockFromInstAddr(UseAddr);
	}
	else { // UseAddr is a block number
		UseBlock = this->GetBlockByNum((size_t) UseAddr);
	}

	DefAddr = UseBlock->GetUltimateDefAddr(UseOp, UseAddr, SSANum, false);

	if (BADADDR == DefAddr) {
		return changed;
	}

	if (DefAddr > this->GetNumBlocks()) { // found a DEF inst.
		SMPInstr *CurrInst = this->GetInstFromAddr(DefAddr);
		ea_t InstAddr = DefAddr;
		DefBlock = this->GetBlockFromInstAddr(DefAddr);
		set<DefOrUse, LessDefUse>::iterator CurrDef;
		set<DefOrUse, LessDefUse>::iterator CurrUse;
		CurrDef = CurrInst->FindDef(UseOp);
		assert(CurrDef != CurrInst->GetLastDef());
		assert(SSANum == CurrDef->GetSSANum());
		if (Status != CurrDef->GetMetadataStatus()) {
			CurrDef = CurrInst->SetDefMetadata(UseOp, Status);
			changed = (CurrDef != CurrInst->GetLastDef());
			bool PropThroughUses = changed;

			// If source operand was memory, we have two cases.
			//  (1) The instruction could be a load, in which
			//  case we should simply terminate the
			//  propagation, because the prior DEF of a memory
			//  location is always considered live metadata
			//  already, and we do not want to propagate liveness
			//  to the address regs in the USE list.
			//  EXCEPTION: For safe funcs, we propagate liveness
			//   for stack locations.
			//  (2) We could have an arithmetic operation such
			//  as reg := reg arithop memsrc. In this case, we
			//  still do not want to propagate through the memsrc,
			//  (with the same safe func EXCEPTION),
			//  but the register is both DEF and USE and we need
			//  to propagate through the register.
			if (CurrInst->HasSourceMemoryOperand()) {
				if (this->SafeFunc) {
					op_t MemSrcOp = CurrInst->MDGetMemUseOp();
					assert(o_void != MemSrcOp.type);
					if (MDIsDirectStackAccessOpnd(MemSrcOp, this->UseFP)) {
						// We have a SafeFunc stack access. This is
						//  the EXCEPTION case where we want to
						//  propagate metadata liveness for a memory
						//  location.
						CurrUse = CurrInst->FindUse(MemSrcOp);
						assert(CurrUse != CurrInst->GetLastUse());
						if (this->IsGlobalName(MemSrcOp)) {
							changed |= this->PropagateGlobalMetadata(MemSrcOp,
								Status, CurrUse->GetSSANum(), InstAddr);
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(MemSrcOp,
								Status, CurrUse->GetSSANum(), InstAddr);
						}
					} // end if stack access operand
				} // end if SafeFunc
				if (3 == CurrInst->GetOptType()) { // move inst
					PropThroughUses = false; // load address regs are not live metadata
				}
				else if ((5 == CurrInst->GetOptType())
					|| (NN_and == CurrInst->GetCmd().itype)
					|| (NN_or == CurrInst->GetCmd().itype)
					|| (NN_xor == CurrInst->GetCmd().itype)) {
					// add, subtract, and, or with memsrc
					// Find the DEF reg in the USE list.
					CurrUse = CurrInst->FindUse(UseOp);
					assert(CurrUse != CurrInst->GetLastUse());
					changed |= this->PropagateGlobalMetadata(UseOp,
						Status, CurrUse->GetSSANum(), InstAddr);
					PropThroughUses = false;
				}
			} // end if memory source

			// Now, propagate the metadata status to all the
			//  non-memory, non-flags-reg, non-special-reg 
			//  (i.e. regular registers) USEs.
			if (PropThroughUses) {
				CurrUse = CurrInst->GetFirstUse();
				while (CurrUse != CurrInst->GetLastUse()) {
					op_t CurrUseOp = CurrUse->GetOp();
					// NOTE: **!!** To be less conservative, we
					//  should propagate less for exchange category
					//  instructions.
					if ((CurrUseOp.type == o_reg) && (!MDIsStackOrFramePointerReg(CurrUseOp, UseFP))
						&& (!CurrUseOp.is_reg(X86_FLAGS_REG))) {

						if (this->IsGlobalName(CurrUseOp)) {
							changed |= this->PropagateGlobalMetadata(CurrUseOp,
								Status, CurrUse->GetSSANum(), InstAddr);
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(CurrUseOp,
								Status, CurrUse->GetSSANum(), InstAddr);
						}
					}
					++CurrUse;
				} // end while all USEs
			}
		}
	}

	else { // Found a DEF block number in DefAddr.
		// Check the Phi functions
		DefBlock = this->GetBlockByNum((size_t) DefAddr);
		set<SMPPhiFunction, LessPhi>::iterator DefPhi;
		DefPhi = DefBlock->FindPhi(UseOp);
		assert(DefPhi != DefBlock->GetLastPhi());
		assert(SSANum == DefPhi->GetDefSSANum());
		if (Status != DefPhi->GetDefMetadata()) {
			DefPhi = DefBlock->SetPhiDefMetadata(UseOp, Status);
			changed = true;
			// If the Phi DEF has live metadata, then the Phi
			//  USEs each have live metadata. Propagate.
			int UseSSANum;
			for (size_t index = 0; index < DefPhi->GetPhiListSize(); ++index) {
				UseSSANum = DefPhi->GetUseSSANum(index);
				// UseSSANum can be -1 in some cases because
				//  we conservatively make EAX and EDX be USEs
				//  of all return instructions, when the function
				//  might have a void return type, making it
				//  appear as if an uninitialized EAX or EDX
				//  could make it to the return block.
				if (0 <= UseSSANum) {
					changed |= this->PropagateGlobalMetadata(UseOp,	Status, UseSSANum, DefAddr);
				}
			}
		}

	} // end if (DefAddr is inst addr) else ... [DefAddr is block number]

	return changed;
} // end of SMPFunction::PropagateGlobalMetadata()

// Find consecutive DEFs of the same type and mark the second one redundant.
void SMPFunction::FindRedundantMetadata(void) {
	list<SMPBasicBlock *>::iterator BlockIter;
	SMPBasicBlock *CurrBlock;
	bool changed = false;

	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		changed |= CurrBlock->FindRedundantLocalMetadata(this->SafeFunc);
	}
	return;
} // end of SMPFunction::FindRedundantMetadata()

// Perform SCCP to find constant values for DEFs, store in this->ConstantDefs
void SMPFunction::SparseConditionalConstantPropagation(void) {
	// We perform the SCCP (Sparse Conditional Constant Propagation) algorithm
	//  as found in Cooper & Torczon, "Engineering a Compiler."

	// CFGWorkList := { all edges from pseudo-entry block to entry blocks }
	//  We do not have a pseudo-entry block, so we special case by starting processing at
	//  the first basic block, block number 0, which is our entry block.
	list<pair<int, int> > CFGWorkList; // edges from pair.first = source block number to pair.second = dest block number
	pair<int, int> InitEdge(-1, 0); // -1 is pseudo-block-number
	CFGWorkList.push_back(InitEdge);
	size_t BlockNumLimit = this->Blocks.size();
	vector<STARSBitSet> ExecutedEdgeBitSet(BlockNumLimit); // records which edges have been executed in SCCP; row = DestBlockNum, col (bit) = SrcBlockNum

	// for each edge e in the CFG
	//  mark e as unexecuted
	for (size_t EdgeIndex = 0; EdgeIndex < BlockNumLimit; ++EdgeIndex) {
		ExecutedEdgeBitSet[EdgeIndex].AllocateBits(BlockNumLimit); // allocate and zero all bits
	}
	this->ResetSCCPVisitedBlocks();  // records which blocks have been visited in SCCP algorithm

	// SSAWorkList := { empty set }
	list<pair<int, int> > SSAWorkList; // pair.first = block number, pair.second = name+SSA hash
	SSAWorkList.clear();

	// for each ref def x in the procedure
	//   Value(x) = TOP
	//  We currently implement this by having this->ConstantDefs contain no entry for defs with value TOP

	// while ((CFGWorkList is not empty) or (SSAWorkList is not empty))
	while (!(CFGWorkList.empty() && SSAWorkList.empty())) {

	//   if (CFGWorkList is not empty) then
	//       remove an edge e = (m, n) from the CFGWorkList
	//       if (e is marked as unexecuted) then
	//          mark e as executed
	//          EvaluateAllPhisInBlock(n)
	//          if (e is only edge into n marked as executed) then
	//              for (each instruction i in block n) do
	//                  if (i is an assignment) then
	//                      EvaluateAssign(i)
	//                  else if (i is a conditional branch) then
	//                      EvaluateConditional(i)
	//                  endif
	//              endfor
	//              Put block successors on CFGWorkList, based on conditional branch evaluation if any
	//          endif
	//       endif
	//   endif

	//   if (CFGWorkList is not empty) then
		if (!(CFGWorkList.empty())) {
	//       remove an edge e = (m, n) from the CFGWorkList
			pair<int, int> CurrentEdge = CFGWorkList.front();
			CFGWorkList.pop_front();
	//       if (e is marked as unexecuted) then
			int SrcBlockNum = CurrentEdge.first;
			int DestBlockNum = CurrentEdge.second;
			bool UnexecutedEdge = (0 > CurrentEdge.first);
			if (!UnexecutedEdge) {
				UnexecutedEdge = (!ExecutedEdgeBitSet.at((size_t) DestBlockNum).GetBit((size_t) SrcBlockNum));
			}
			if (UnexecutedEdge) {