SMPFunction.cpp

		struct StackFrameEntry TempEntry = this->StackFrameMap.at((size_t) MapIndex);
		if (this->OutgoingArgsSize < (TempEntry.VarPtr->offset + TempEntry.VarPtr->size)) {
#if SMP_DEBUG_FRAMEFIXUP
			msg("OutGoingArgsSize = %d", this->OutgoingArgsSize);
#endif
			this->OutgoingArgsSize = TempEntry.VarPtr->offset + TempEntry.VarPtr->size;
#if SMP_DEBUG_FRAMEFIXUP
			msg(" adjusted to %d\n", this->OutgoingArgsSize);
#endif
		}
	}
	return;
} // end of SMPFunction::FindOutgoingArgsSize()

// If TempOp reads or writes to a stack location, return the offset (relative to the initial
//  stack pointer value) and the size in bytes of the data access.
// NOTE: TempOp must be of type o_displ or o_phrase, as no other operand type could be a
//  stack memory access.
// sp_delta is the stack pointer delta of the current instruction, relative to the initial
//  stack pointer value for the function.
// Return true if a stack memory access was found in TempOp, false otherwise.
bool SMPFunction::MDGetStackOffsetAndSize(op_t TempOp, sval_t sp_delta, ea_t &offset, size_t &DataSize, bool &FP) {
	int BaseReg;
	int IndexReg;
	ushort ScaleFactor;

	assert((o_displ == TempOp.type) || (o_phrase == TempOp.type));
	MDExtractAddressFields(TempOp, BaseReg, IndexReg, ScaleFactor, offset);

	if (TempOp.type == o_phrase) {
		assert(offset == 0);  // implicit zero, as in [esp] ==> [esp+0]
	}
	if ((BaseReg == R_sp) || (IndexReg == R_sp)) {
		// ESP-relative constant offset
		offset += sp_delta; // base offsets from entry ESP value
		offset -= this->MinStackDelta; // convert to StackFrameMap index
		// Get size of data written
		DataSize = GetOpDataSize(TempOp);
		FP = false;
		return true;
	}
	else if (this->UseFP && ((BaseReg == R_bp) || (IndexReg == R_bp))) {
		offset -= this->FuncInfo.frregs; // base offsets from entry ESP value
		offset -= this->MinStackDelta; // convert to StackFrameMap index
		DataSize = GetOpDataSize(TempOp);
		FP = true;
		return true;
	}
	else {
		return false;
	}
} // end of SMPFunction::MDGetStackOffsetAndSize()

// 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;
	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
#if SMP_USE_SSA_FNOP_MARKER
		if (this->Instrs.begin() == CurrInst)
			continue;  // skip marker instruction
#endif

		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, list<SMPInstr>::iterator Instr) {
	ea_t addr = Instr->GetAddr();

#if 0
	if (0 < IncomingArgsSize) {
		qfprintf(AnnotFile, "%10x %6d INARGS STACK esp + %d %s \n",
				addr, IncomingArgsSize,
				(LocalVarsSize + CalleeSavedRegsSize + RetAddrSize),
				Instr->GetDisasm());
	}
#endif
	if (0 < RetAddrSize) {
		qfprintf(AnnotFile, "%10x %6d MEMORYHOLE STACK esp + %d ReturnAddress \n",
				addr, RetAddrSize, (LocalVarsSize + CalleeSavedRegsSize));
	}
	if (0 < CalleeSavedRegsSize) {
		qfprintf(AnnotFile, "%10x %6d MEMORYHOLE STACK esp + %d CalleeSavedRegs \n",
				addr, CalleeSavedRegsSize, LocalVarsSize);
	}
	if (0 < LocalVarsSize) {
		unsigned long ParentReferentID = DataReferentID++;
		qfprintf(AnnotFile, "%10x %6d DATAREF STACK %d esp + %d PARENT LocalFrame LOCALFRAME\n",
				addr, 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) {
				qfprintf(AnnotFile, "%10x %6d DATAREF STACK %d esp + %d CHILDOF %d OFFSET %d OutArgsRegion OUTARGS\n",
					addr, this->OutgoingArgsSize, DataReferentID, 0, ParentReferentID, 0);
				++DataReferentID;
			}
#if SMP_DEBUG_STACK_GRANULARITY
			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
				msg("Entry %d offset %d 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;
				qfprintf(AnnotFile, "%10x %6d DATAREF STACK %d esp + %d CHILDOF %d OFFSET %d 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) {
	list<SMPInstr>::iterator FirstInBlock = this->Instrs.end();
	   // For starting a basic block
	list<SMPInstr>::iterator LastInBlock = this->Instrs.end();
	   // Terminating a basic block

#if SMP_DEBUG_CONTROLFLOW
	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));
	get_func_name(this->FuncInfo.startEA, this->FuncName,
		sizeof(this->FuncName) - 1);
	this->BlockCount = 0;
	this->AnalyzedSP = this->FuncInfo.analyzed_sp();

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

	// Cycle through all chunks that belong to the function.
	func_tail_iterator_t FuncTail(&(this->FuncInfo));
	size_t ChunkCounter = 0;
	for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
		const area_t &CurrChunk = FuncTail.chunk();
		++ChunkCounter;
		if (1 < ChunkCounter) {
			this->SharedChunks = true;
#if SMP_DEBUG_CHUNKS
			msg("Found tail chunk for %s at %x\n", this->FuncName, CurrChunk.startEA);
#endif
		}
		// 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 = SMPInstr(addr);
				// Fill in the instruction data members.
#if SMP_DEBUG_CONTROLFLOW
				msg("SMPFunction::Analyze: calling CurrInst::Analyze.\n");
#endif
				CurrInst.Analyze();
				if (SMPBinaryDebug) {
					msg("Disasm:  %s \n", CurrInst.GetDisasm());
				}
#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 = SMPInstr(addr - 1);
					MarkerInst.AnalyzeMarker();
					assert(FirstInBlock == this->Instrs.end());
					this->Instrs.push_back(MarkerInst);
				}
#endif
				if (this->AnalyzedSP) {
					// Audit the IDA SP analysis.
					sval_t sp_delta = get_spd(&(this->FuncInfo), 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;
						msg("Resetting AnalyzedSP to false for %s\n", this->GetFuncName());
						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();
							msg("Found tail call at %x from %s: %s\n", addr, this->GetFuncName(),
								CurrInst.GetDisasm());
						}
					}
				}

				if (CurrInst.GetDataFlowType() == INDIR_CALL)
					this->IndirectCalls = true;
				else if (CurrInst.GetDataFlowType() == INDIR_JUMP)
					this->IndirectJumps = true;
				else if (CurrInst.GetDataFlowType() == CALL) {
					set<DefOrUse, LessDefUse>::iterator CurrUse;
					for (CurrUse = CurrInst.GetFirstUse(); CurrUse != CurrInst.GetLastUse(); ++CurrUse) {
						optype_t OpType = CurrUse->GetOp().type;
						if ((OpType == o_near) || (OpType == o_far)) {
							ea_t CallTarget = CurrUse->GetOp().addr;
							this->DirectCallTargets.push_back(CallTarget);
						}
					}
				}

				// 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
					msg("SMPFunction::Analyze: hit special jump target case.\n");
#endif
					LastInBlock = --(this->Instrs.end());
					SMPBasicBlock CurrBlock = SMPBasicBlock(this, FirstInBlock,
						LastInBlock);
					CurrBlock.Analyze();
					// If not the first chunk in the function, it is a shared
					//  tail chunk.
					if (ChunkCounter > 1) {
						CurrBlock.SetShared();
					}
					FirstInBlock = this->Instrs.end();
					LastInBlock = this->Instrs.end();
					this->Blocks.push_back(CurrBlock);
					this->BlockCount += 1;
				}

#if SMP_DEBUG_CONTROLFLOW
		msg("SMPFunction::Analyze: putting CurrInst on list.\n");
#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
					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
		msg("SMPFunction::Analyze: found block terminator.\n");
#endif
					LastInBlock = --(this->Instrs.end());
					SMPBasicBlock CurrBlock = SMPBasicBlock(this, FirstInBlock, LastInBlock);
					CurrBlock.Analyze();
					// If not the first chunk in the function, it is a shared
					//  tail chunk.
					if (ChunkCounter > 1) {
						CurrBlock.SetShared();
					}
					FirstInBlock = this->Instrs.end();
					LastInBlock = this->Instrs.end();
					this->Blocks.push_back(CurrBlock);
					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 CurrBlock = SMPBasicBlock(this, FirstInBlock, LastInBlock);
			CurrBlock.Analyze();
			// If not the first chunk in the function, it is a shared
			//  tail chunk.
			if (ChunkCounter > 1) {
				CurrBlock.SetShared();
			}
			FirstInBlock = this->Instrs.end();
			LastInBlock = this->Instrs.end();
			this->Blocks.push_back(CurrBlock);
			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 CurrBlock;
	list<list<SMPInstr>::iterator>::iterator InstIter;
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
			(*InstIter)->SetBlock(CurrBlock->GetThisBlock());
		}
	}

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

	// Set up basic block links and map of instructions to blocks.
	if (!(this->HasSharedChunks())) {
		bool DumpFlag = false;
#if SMP_DEBUG_DATAFLOW
		DumpFlag |= (0 == strcmp("__do_global_dtors_aux", this->GetFuncName()));
		DumpFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
		DumpFlag |= (0 == strcmp("weightadj", this->GetFuncName()));
#endif
		this->SetLinks();
		this->RPONumberBlocks();

#if SMP_DEBUG_CONTROLFLOW
		msg("SMPFunction::Analyze: set stack frame info.\n");
#endif
		// Figure out the stack frame and related info.
		this->SetStackFrameInfo();

#if SMP_COMPUTE_LVA_SSA
#if SMP_USE_SWITCH_TABLE_INFO
		if (!(this->HasUnresolvedIndirectJumps())) {
#else
		if (!(this->HasIndirectJumps())) {
#endif
			list<SMPInstr>::iterator CurrInst;
			bool GoodRTL;
			this->BuiltRTLs = true;
			for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
				// Build tree RTLs for the instruction.
				GoodRTL = CurrInst->BuildRTL();
				this->BuiltRTLs = (this->BuiltRTLs && GoodRTL);
#if SMP_DEBUG_BUILD_RTL
				if (!GoodRTL) {
					msg("ERROR: Cannot build RTL at %x for %s\n", CurrInst->GetAddr(), 
						CurrInst->GetDisasm());
				}
#endif
				if (GoodRTL)
					CurrInst->SyncAllRTs();
			} // end for all instructions
			this->LiveVariableAnalysis();
			this->ComputeSSA();
			if (DumpFlag) 
				this->Dump();
		} // end if not indirect jumps
#endif // SMP_COMPUTE_LVA_SSA
	} // end if not shared chunks
	else { // has shared chunks; still want to compute stack frame info
#if SMP_DEBUG_CONTROLFLOW
		msg("SMPFunction::Analyze: set stack frame info.\n");
#endif
#ifdef SMP_DEBUG_FUNC
		msg(" %s has shared chunks \n", this->GetFuncName());
#endif
	// Figure out the stack frame and related info.
		this->SetStackFrameInfo();
	}
	this->MarkFunctionSafe();
} // end of SMPFunction::Analyze()

// 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 CurrInst;
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	set<DefOrUse, LessDefUse>::iterator NextUse;

	do {
		changed = false;
		for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
			// Skip the SSA marker instruction.
			if (NN_fnop == CurrInst->GetCmd().itype)
				continue;

			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.
						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()) {
									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()) {
									msg("ERROR: IndexReg %d not in USE list at %x for %s\n",
										IndexOp.reg, CurrInst->GetAddr(),
										CurrInst->GetDisasm());
								}
								assert(CurrUse != CurrInst->GetLastUse());
								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())
				|| (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 ((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
			else if (CurrInst->HasDestMemoryOperand()) {
				// 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.
				UseOp = CurrInst->GetSourceOnlyOperand();
				if ((UseOp.type != o_void) && (!UseOp.is_reg(R_sp))
					&& (!(this->UseFP && UseOp.is_reg(R_bp)))) {

					CurrUse = CurrInst->FindUse(UseOp);
					if (CurrUse == CurrInst->GetLastUse()) {
						msg("ERROR: UseReg %d not in USE list at %x for %s\n",
							UseOp.reg, CurrInst->GetAddr(),
							CurrInst->GetDisasm());
					}
					assert(CurrUse != CurrInst->GetLastUse());
					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 for all instructions
	} while (changed);

	// All DEFs that still have status DEF_METADATA_UNANALYZED can now
	//  be marked as DEF_METADATA_UNUSED.
	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
		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;

	// Find the DEF of UseOp with SSANum.
	bool FoundDef = false;
	list<SMPInstr>::iterator CurrInst;

	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
		set<DefOrUse, LessDefUse>::iterator CurrDef;
		set<DefOrUse, LessDefUse>::iterator CurrUse;
		CurrDef = CurrInst->FindDef(UseOp);
		if (CurrDef != CurrInst->GetLastDef()) {
			if (SSANum == CurrDef->GetSSANum()) {
				if (Status != CurrDef->GetMetadataStatus()) {
					CurrDef = CurrInst->SetDefMetadata(UseOp, Status);
					changed = (CurrDef != CurrInst->GetLastDef());
					// Now, propagate the metadata status to all the
					//  non-memory, non-flags-reg, non-special-reg 
					//  (i.e. regular registers) USEs.
					CurrUse = CurrInst->GetFirstUse();
					while (CurrUse != CurrInst->GetLastUse()) {
						op_t UseOp = CurrUse->GetOp();
						if ((o_reg == UseOp.type)
							&& (!UseOp.is_reg(X86_FLAGS_REG))) {
								changed |= this->PropagateGlobalMetadata(UseOp,
									Status, CurrUse->GetSSANum());
						}
						++CurrUse;
					}
				}
				FoundDef = true;
				break;
			}
		}
	}

	if (!FoundDef) {
		// Check the Phi functions
		list<SMPBasicBlock>::iterator CurrBlock;
		for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
			set<SMPPhiFunction, LessPhi>::iterator DefPhi;
			DefPhi = CurrBlock->FindPhi(UseOp);
			if (DefPhi != CurrBlock->GetLastPhi()) {
				if (SSANum == DefPhi->GetDefSSANum()) {
					if (Status != DefPhi->GetDefMetadata()) {
						DefPhi = CurrBlock->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);
							}
						}
					}
					FoundDef = true;
					break;
				}
			}
		} // end for all blocks
	} // end if !FoundDef

	if (!FoundDef) {
		msg("ERROR: Could not find DEF of SSANum %d for: ");
		PrintOperand(UseOp);
		msg(" in function %s\n", this->GetFuncName());
	}

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

// Compute SSA form data structures across the function.
void SMPFunction::ComputeSSA(void) {
	bool DumpFlag = false;
	bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
	DumpFlag |= (0 == strcmp("main", this->GetFuncName()));
	DumpFlag |= (0 == strcmp("call_gmon_start", this->GetFuncName()));
	DumpFlag |= (0 == strcmp("_init_proc", this->GetFuncName()));
#endif
#if 0
	DebugFlag |= (0 == strcmp("call_gmon_start", this->GetFuncName()));
#endif

#if 0
	DumpFlag |= (0 == strcmp("_nl_find_msg", this->GetFuncName()));
	if (DumpFlag)
		this->Dump();
#endif
	this->ComputeIDoms();
	this->ComputeDomFrontiers();
	this->ComputeGlobalNames();
	this->ComputeBlocksDefinedIn();

	this->InsertPhiFunctions();
	this->BuildDominatorTree();
	this->SSARenumber();
	list<SMPBasicBlock>::iterator CurrBlock;
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		CurrBlock->SetLocalNames();
		CurrBlock->SSALocalRenumber();
		if (DebugFlag) CurrBlock->Dump();

#if SMP_FULL_LIVENESS_ANALYSIS
		CurrBlock->CreateGlobalChains();
#endif
#if 1
		CurrBlock->MarkDeadRegs();
#endif
	}
#if SMP_DEBUG_DATAFLOW
	if (DumpFlag)
		this->Dump();
#endif
	return;
} // end of SMPFunction::ComputeSSA()

// Link basic blocks to their predecessors and successors, and build the map
//  of instruction addresses to basic blocks.
void SMPFunction::SetLinks(void) {
	list<SMPBasicBlock>::iterator CurrBlock;
#if SMP_DEBUG_DATAFLOW
	msg("SetLinks called for %s\n", this->GetFuncName());
#endif
	// First, set up the map of instructions to basic blocks.
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		list<list<SMPInstr>::iterator>::iterator CurrInst;
		for (CurrInst = CurrBlock->GetFirstInstr();
			CurrInst != CurrBlock->GetLastInstr();
			++CurrInst) {
				pair<ea_t, list<SMPBasicBlock>::iterator> MapItem((*CurrInst)->GetAddr(),CurrBlock);
				InstBlockMap.insert(MapItem);
		}
	}

#if SMP_DEBUG_DATAFLOW
	msg("SetLinks finished mapping: %s\n", this->GetFuncName());
#endif
	// Next, set successors of each basic block, also setting up the predecessors in the
	//  process.
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		list<SMPInstr>::iterator CurrInst = *(--(CurrBlock->GetLastInstr()));
		bool CondTailCall = false;
		if (CurrBlock->HasReturn()) {
			if (!(CurrInst->IsCondTailCall())) {
				// We either have a return instruction or an unconditional
				//  tail call instruction. We don't want to link to the
				//  tail call target, and there is no link for a return
				continue;
			}
			else {
				// We have a conditional tail call. We don't want to
				//  link to the tail call target, but we do want fall
				//  through to the next instruction.
				CondTailCall = true;
			}
		}

		// Last instruction in block; set successors
		bool CallFlag = (CALL == CurrInst->GetDataFlowType());
		bool TailCallFlag = CondTailCall && CurrInst->IsCondTailCall();
		bool IndirJumpFlag = (INDIR_JUMP == CurrInst->GetDataFlowType());
		xrefblk_t CurrXrefs;
		bool LinkedToTarget = false;
		for (bool ok = CurrXrefs.first_from(CurrInst->GetAddr(), XREF_ALL);
			ok;
			ok = CurrXrefs.next_from()) {
				if ((CurrXrefs.to != 0) && (CurrXrefs.iscode)) {
					// Found a code target, with its address in CurrXrefs.to
					if ((CallFlag || TailCallFlag) 
						&& (CurrXrefs.to != (CurrInst->GetAddr() + CurrInst->GetCmd().size))) {
						// A call instruction will have two targets: the fall through to the
						//  next instruction, and the called function. We want to link to the
						//  fall-through instruction, but not to the called function.
						// Some blocks end with a call just because the fall-through instruction
						//  is a jump target from elsewhere.
						continue;
					}
					map<ea_t, list<SMPBasicBlock>::iterator>::iterator MapEntry;
					MapEntry = this->InstBlockMap.find(CurrXrefs.to);
					if (MapEntry == this->InstBlockMap.end()) {
						msg("WARNING: addr %x not found in map for %s\n", CurrXrefs.to,
							this->GetFuncName());
						msg(" Referenced from %s\n", CurrInst->GetDisasm());
					}
					else {
						list<SMPBasicBlock>::iterator Target = MapEntry->second;
						// Make target block a successor of current block.
						CurrBlock->LinkToSucc(Target);
						// Make current block a predecessor of target block.
						Target->LinkToPred(CurrBlock);
						LinkedToTarget = true;
#if SMP_USE_SWITCH_TABLE_INFO
						if (IndirJumpFlag) {
							msg("Switch table link: jump at %x target at %x\n",
								CurrInst->GetAddr(), CurrXrefs.to);
						}
#endif
					}
				}
		} // end for all xrefs
		if (IndirJumpFlag && (!LinkedToTarget)) {
			this->UnresolvedIndirectJumps = true;
			msg("WARNING: Unresolved indirect jump at %x\n",	CurrInst->GetAddr());
		}
	} // end for all blocks

	// If we have any blocks that are all no-ops and have no predecessors, remove those
	//  blocks. They are dead and make the CFG no longer a lattice. Any blocks that have
	//  no predecessors but are not all no-ops should also be removed with a different
	//  log message.
	// NOTE: Prior to construction of hell nodes in functions with unresolved indirect jumps,
	//  we cannot conclude that a block with no predecessors is unreachable. Also, the block
	//  order might be such that removal of a block makes an already processed block
	//  unreachable, so we have to iterate until there are no more changes.
#if SMP_USE_SWITCH_TABLE_INFO
	if (!(this->HasUnresolvedIndirectJumps())) {
#else
	if (!(this->HasIndirectJumps())) {
#endif
		bool changed;
		do {
			changed = false;
			CurrBlock = this->Blocks.begin();
			++CurrBlock; // don't delete the top block, no matter what.
			while (CurrBlock != this->Blocks.end()) {
				if (CurrBlock->GetFirstPred() == CurrBlock->GetLastPred()) {
					if (CurrBlock->AllNops())
						msg("Removing all nops block at %x\n", CurrBlock->GetFirstAddr());
					else
						msg("Removing block with no predecessors at %x\n", CurrBlock->GetFirstAddr());
					// Remove this block from the predecessors list of its successors.
					list<list<SMPBasicBlock>::iterator>::iterator SuccIter;
					ea_t TempAddr = CurrBlock->GetFirstAddr();
					for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
						(*SuccIter)->ErasePred(TempAddr);
					}
					// Remove the unreachable instructions from the function inst list.
					list<list<SMPInstr>::iterator>::iterator InstIter;
					for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
						list<SMPInstr>::iterator DummyIter = this->Instrs.erase(*InstIter);
					}
					// Finally, remove the block from the blocks list.
					CurrBlock = this->Blocks.erase(CurrBlock);
					this->BlockCount -= 1;
					changed = true;
				}
				else
					++CurrBlock;
			} // end while all blocks after the first one
		} while (changed);
	} // end if not indirect jumps

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

// Number all basic blocks in reverse postorder (RPO) and set RPOBlocks vector to
//  access them.
void SMPFunction::RPONumberBlocks(void) {
	bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
	DebugFlag = (0 == strcmp("__ieee754_pow", this->GetFuncName()));
	if (DebugFlag) msg("Entered RPONumberBlocks\n");
#endif
	int CurrNum = 0;
	list<list<SMPBasicBlock>::iterator> WorkList;

	// Number the first block with 0.
	list<SMPBasicBlock>::iterator CurrBlock = this->Blocks.begin();
#if 0
	if (this->RPOBlocks.capacity() <= (size_t) this->BlockCount) {
		msg("Reserving %d RPOBlocks old value: %d\n", 2+this->BlockCount, this->RPOBlocks.capacity());
		this->RPOBlocks.reserve(2 + this->BlockCount);
		this->RPOBlocks.assign(2 + this->BlockCount, this->Blocks.end());
	}
#endif
	CurrBlock->SetNumber(CurrNum);
	this->RPOBlocks.push_back(CurrBlock);
	++CurrNum;
	// Push the first block's successors onto the work list.
	list<list<SMPBasicBlock>::iterator>::iterator CurrSucc = CurrBlock->GetFirstSucc();
	while (CurrSucc != CurrBlock->GetLastSucc()) {
		WorkList.push_back(*CurrSucc);
		++CurrSucc;
	}

	// Use the WorkList to iterate through all blocks in the function
	list<list<SMPBasicBlock>::iterator>::iterator CurrListItem = WorkList.begin();
	bool change;
	while (!WorkList.empty()) {
		change = false;
		while (CurrListItem != WorkList.end()) {
			if ((*CurrListItem)->GetNumber() != SMP_BLOCKNUM_UNINIT) {
				// Duplicates get pushed onto the WorkList because a block
				//  can be the successor of multiple other blocks. If it is
				//  already numbered, it is a duplicate and can be removed
				//  from the list.
				CurrListItem = WorkList.erase(CurrListItem);
				change = true;
				continue;
			}
			if ((*CurrListItem)->AllPredecessorsNumbered()) {
				// Ready to be numbered.
				(*CurrListItem)->SetNumber(CurrNum);
#if 0
				msg("Set RPO number %d\n", CurrNum);
				if (DebugFlag && (7 == CurrNum))
					this->Dump();
#endif
				this->RPOBlocks.push_back(*CurrListItem);
				++CurrNum;
				change = true;
				// Push its unnumbered successors onto the work list.
				CurrSucc = (*CurrListItem)->GetFirstSucc();
				while (CurrSucc != (*CurrListItem)->GetLastSucc()) {
					if ((*CurrSucc)->GetNumber() == SMP_BLOCKNUM_UNINIT)
						WorkList.push_back(*CurrSucc);
					++CurrSucc;
				}
				CurrListItem = WorkList.erase(CurrListItem);
			}
			else {
				++CurrListItem;
			}
		} // end while (CurrListItem != WorkList.end())
		if (change) {
			// Reset CurrListItem to beginning of work list for next iteration.
			CurrListItem = WorkList.begin();
		}
		else {
			// Loops can cause us to not be able to find a WorkList item that has
			//  all predecessors numbered. Take the WorkList item with the lowest address
			//  and number it so we can proceed.
			CurrListItem = WorkList.begin();
			ea_t LowAddr = (*CurrListItem)->GetFirstAddr();
			list<list<SMPBasicBlock>::iterator>::iterator SaveItem = CurrListItem;
			++CurrListItem;
			while (CurrListItem != WorkList.end()) {
				if (LowAddr > (*CurrListItem)->GetFirstAddr()) {
					SaveItem = CurrListItem;
					LowAddr = (*CurrListItem)->GetFirstAddr();
				}
				++CurrListItem;
			}
			// SaveItem should now be numbered.
			(*SaveItem)->SetNumber(CurrNum);
#if SMP_DEBUG_DATAFLOW
			msg("Picked LowAddr %x and set RPO number %d\n", LowAddr, CurrNum);
#endif
			this->RPOBlocks.push_back(*SaveItem);
			++CurrNum;
			// Push its unnumbered successors onto the work list.
			CurrSucc = (*SaveItem)->GetFirstSucc();
			while (CurrSucc != (*SaveItem)->GetLastSucc()) {
				if ((*CurrSucc)->GetNumber() == SMP_BLOCKNUM_UNINIT)
					WorkList.push_back(*CurrSucc);
				++CurrSucc;
			}
			CurrListItem = WorkList.erase(SaveItem);
			CurrListItem = WorkList.begin();
		} // end if (change) ... else ...
	} // end while work list is nonempty

	// Prior to construction of hell nodes for functions with indirect jumps, there
	//  could still be unnumbered blocks because they appear to be unreachable
	//  (no predecessors from SetLinks() because they are reached only via indirect
	//  jumps). We need to number these and push them on the RPOBlocks vector so
	//  that the vector contains all the blocks.
	if (this->HasIndirectJumps()) {
		for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
			if (SMP_BLOCKNUM_UNINIT == CurrBlock->GetNumber()) {
				msg("Numbering indirectly reachable block at %x\n", CurrBlock->GetFirstAddr());
				CurrBlock->SetNumber(CurrNum);
				this->RPOBlocks.push_back(CurrBlock);
				++CurrNum;
			}
		}
	}
	return;
} // end of SMPFunction::RPONumberBlocks()