SMPFunction.cpp

// Return true if we update fine grained stack entry for stack op TempOp from instruction at InstAddr
bool SMPFunction::MDUpdateFGStackLocInfo(ea_t InstAddr, op_t TempOp, struct FineGrainedInfo NewFG) {
	int BaseReg;
	int IndexReg;
	ushort ScaleFactor;
	ea_t offset;
	int SignedOffset;
	struct FineGrainedInfo OldFG, UnionFG;

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

	SignedOffset = (int) offset;

	if (TempOp.type == o_phrase) {
		assert(SignedOffset == 0);  // implicit zero, as in [esp] ==> [esp+0]
	}
	if ((BaseReg == R_sp) || (IndexReg == R_sp)) {
		// ESP-relative constant offset
		SignedOffset -= this->MinStackAccessOffset; // convert to StackFrameMap index
	}
	else if (this->UseFP && ((BaseReg == R_bp) || (IndexReg == R_bp))) {
		assert(false); // should never get here with unnormalized stack operands
		SignedOffset -= this->FuncInfo.frregs; // base offsets from entry ESP value
		SignedOffset -= this->MinStackAccessOffset; // convert to StackFrameMap index
	}
	else {
		return false;
	}
	// We did not return false, so we should have a good offset. Use it to
	//  retrieve the fine grained stack table entry for that offset.
	if ((0 > SignedOffset) || (SignedOffset >= (int) this->FineGrainedStackTable.size())) {
		if (this->OutgoingArgsComputed) {
			SMP_msg("ERROR: FG stack table index out of range in MDGetFGStackLocInfo at %x\n", InstAddr);
		}
		return false;
	}
	else if (this->OutgoingArgsComputed && (((size_t)SignedOffset) < this->OutgoingArgsSize)) {
		// We don't want to update the outgoing args region, as it will not be consistent
		//  over multiple function calls. NOTE: We could fine tune this by seeing if we
		//  call mutliple target functions or not; if only one, then outgoing args region
		//  would be consistent in the absence of varargs targets.
		return false;
	}
	else {
		OldFG = this->FineGrainedStackTable.at((size_t) SignedOffset);
		UnionFG.SignMiscInfo = OldFG.SignMiscInfo | NewFG.SignMiscInfo;
		UnionFG.SizeInfo = OldFG.SizeInfo | NewFG.SizeInfo;
		if ((OldFG.SignMiscInfo != UnionFG.SignMiscInfo) || (OldFG.SizeInfo != UnionFG.SizeInfo)) {
			// The signs they are a-changin'. Or maybe the sizes.
			this->FineGrainedStackTable.at(SignedOffset).SignMiscInfo |= NewFG.SignMiscInfo;
			this->FineGrainedStackTable.at(SignedOffset).SizeInfo |= NewFG.SizeInfo;
		}
	}
	return true;
} // end of SMPFunction::MDUpdateFGStackLocInfo()

// retrieve DEF addr from GlobalDefAddrBySSA or return BADADDR
ea_t SMPFunction::GetGlobalDefAddr(op_t DefOp, int SSANum) {
	map<int, ea_t>::iterator DefAddrMapIter;
	map<int, ea_t>::iterator MapResult;
	ea_t DefAddr = BADADDR; // BADADDR means we did not find it
	bool RegDef = (o_reg == DefOp.type);

	if (RegDef) {
		int HashedName = HashGlobalNameAndSSA(DefOp, SSANum);
		MapResult = this->GlobalDefAddrBySSA.find(HashedName);
		if (MapResult != this->GlobalDefAddrBySSA.end()) { // Found it.
			DefAddr = (ea_t) MapResult->second;
		}
	}
	else if (MDIsStackAccessOpnd(DefOp, this->UsesFramePointer())) {
		// Until we get stack operands into the GlobalDefAddrBySSA map,
		//  do a linear search.
		list<SMPInstr *>::iterator InstIter;
		set<DefOrUse, LessDefUse>::iterator DefIter;
		for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
			SMPInstr *CurrInst = (*InstIter);
			if (CurrInst->HasDestMemoryOperand()) {
				op_t MemDefOp = CurrInst->GetMemDef();
				if (IsEqOp(DefOp, MemDefOp)) {
					DefIter = CurrInst->FindDef(MemDefOp);
					assert(DefIter != CurrInst->GetLastDef());
					int DefSSANum = DefIter->GetSSANum();
					if (DefSSANum == SSANum) { // found it
						DefAddr = CurrInst->GetAddr();
						break;
					}
				}
			}
		}
	}
	return DefAddr;
} // end of SMPFunction::GetGlobalDefAddr()

// Retrieve block iterator for InstAddr from InstBlockMap; assert if failure
SMPBasicBlock *SMPFunction::GetBlockFromInstAddr(ea_t InstAddr) {
	map<ea_t, SMPBasicBlock *>::iterator MapEntry;
	MapEntry = this->InstBlockMap.find(InstAddr);
	assert(MapEntry != this->InstBlockMap.end());
	return MapEntry->second;
}

// Retrieve inst pointer for InstAddr; assert if failure on block find.
SMPInstr *SMPFunction::GetInstFromAddr(ea_t InstAddr) {
	SMPBasicBlock *CurrBlock = this->GetBlockFromInstAddr(InstAddr);
	SMPInstr *CurrInst = CurrBlock->FindInstr(InstAddr);
	return CurrInst;
}

// 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.
// NOTE: DestOp should be already normalized to the entry stack delta.
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 {
		int SignedOffset = (int) offset;
		SignedOffset -= this->MinStackDelta; // convert to zero-based from bottom of stack frame
		OutArgWrite = (((size_t) SignedOffset) < 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 OpNormalized) {
	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));
	assert(!EBPrelative || !OpNormalized); // stack operands should be normalized by now
	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;
	}

	// The next statement omits a complication: The possibility that OpNormalized is false,
	//  and an ESPRelative access is above the stack frame. For the purposes of determining
	//  whether a function is safe, this is irrelevant, because !OpNormalized would indicate
	//  that AnalyzedSP is false, which will make the function unsafe anyway. Future uses for
	//  other purposes need to fix this.
	InArgWrite = (ESPrelative && OpNormalized && (SignedOffset >= 0))
		|| (EBPrelative && (SignedOffset > 0));

	if (InArgWrite && OpNormalized && (0 == SignedOffset)) {
		SMP_msg("DANGER: Write to saved return address detected in function that begins at %x\n",
			this->FirstEA);
	}

	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));
	assert(!EBPrelative || !this->StackPtrAnalysisSucceeded() || !this->HasSTARSStackPtrAnalysisCompleted()); // stack operands should be normalized by now
	if (!(ESPrelative || EBPrelative))
		return false;

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

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

// Is CurrOp found anywhere in the StackPtrCopySet, regardless of which address and stack delta
//  values are associated with it?
bool SMPFunction::IsInStackPtrCopySet(op_t CurrOp) {
	bool found = false;
	// Set is composed of triples, so we have to iterate through it and compare operands.
	set<pair<op_t, pair<ea_t, sval_t> >, LessStackDeltaCopy>::iterator CopyIter;
	for (CopyIter = this->StackPtrCopySet.begin(); CopyIter != this->StackPtrCopySet.end(); ++CopyIter) {
		pair<op_t, pair<ea_t, sval_t> > CurrCopy = *CopyIter;
		op_t CopyOp = CurrCopy.first;
		if (IsEqOp(CopyOp, CurrOp)) {
			// Found it.
			found = true;
			break;
		}
		else if (CopyOp.type > CurrOp.type) {
			// already moved past its spot; not found
			break;
		}
	}

	return found;
} // end of SMPFunction::IsInStackPtrCopySet()

// Find evidence of calls to alloca(), which appear as stack space allocations (i.e.
//  subtractions [of unknown values(?)] 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) {
	bool FoundAlloca = false;
	list<SMPInstr *>::iterator InstIter = this->Instrs.begin();
	SMPInstr *CurrInst;
	ea_t InstAddr;
#if SMP_USE_SSA_FNOP_MARKER
	++InstIter;  // skip marker instruction
#endif
	for ( ; InstIter != this->Instrs.end(); ++InstIter) {
		CurrInst = (*InstIter);
		InstAddr = CurrInst->GetAddr();
		if (InstAddr > this->LocalVarsAllocInstr) {
			if (CurrInst->MDIsFrameAllocInstr()) {
				FoundAlloca = true;
				if (CurrInst->HasAllocaRTL()) {
					CurrInst->SetAllocaCall();
				}
			}
			else if (CurrInst->MDIsPushInstr()) {
				this->PushAfterLocalVarAlloc = true;
			}
		}
	}
	return FoundAlloca;
} // 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 %6zu 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 %6zu 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;
	set<ea_t> FragmentWorkList;  // Distant code fragments that belong to this function and need processing
	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->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());
	ea_t FuncHeadLastAddr = 0;
	for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
		const area_t &CurrChunk = FuncTail.chunk();
		++ChunkCounter;
		if (1 == ChunkCounter) { // head chunk
			FuncHeadLastAddr = CurrChunk.endEA;
		}
		else { // a tail chunk
#if STARS_FIND_UNSHARED_CHUNKS
			if (this->GetProg()->IsChunkUnshared(CurrChunk.startEA, this->FirstEA, FuncHeadLastAddr)) {
				this->UnsharedChunks = true;
#if SMP_DEBUG_CHUNKS
				SMP_msg("INFO: Found unshared tail chunk for %s at %x\n", this->GetFuncName(), CurrChunk.startEA);
#endif
			}
			else {
#endif // STARS_FIND_UNSHARED_CHUNKS
				this->SharedChunks = true;
#if SMP_DEBUG_CHUNKS
				SMP_msg("INFO: Found tail chunk for %s at %x\n", this->GetFuncName(), CurrChunk.startEA);
#endif
#if STARS_FIND_UNSHARED_CHUNKS 
			}
#endif // STARS_FIND_UNSHARED_CHUNKS
		}
	}

	// Cycle through all chunks that belong to the function.
	ChunkCounter = 0;
	bool GoodRTL;
	this->BuiltRTLs = true;
 	for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
		const area_t &CurrChunk = FuncTail.chunk();
		++ChunkCounter;
#if 0
		if (CurrChunk.startEA < this->FirstEA) {
			this->FirstEA = CurrChunk.startEA;
		}
#endif
#if STARS_DEBUG_MEMORY_CORRUPTION
	bool DebugFlag = (0 == strcmp("sub_8063BE0", this->GetFuncName()));
#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 = 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

				// 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()) {
						ea_t FromAddr = CurrXrefs.GetFrom();
						if ((FromAddr != 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(FromAddr);
							CallInst.Analyze();
							SMPitype CallType = CallInst.GetDataFlowType();
							if ((COND_BRANCH <= CallType) && (RETURN >= CallType)) {
								// Found a caller, with its call address in CurrXrefs.from
								this->AddCallSource(FromAddr);
							}
						}
					}
					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.
#if 0
					CurrInst->AnalyzeCallInst(this->FirstEA, this->FuncInfo.endEA);
#endif
					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;
				}
				else if (DataFlowType == RETURN) {
					this->HasReturnInst = true;
				}
				// Add call targets for tail call jumps.
				else if (CurrInst->IsBranchToFarChunk()) {
					ea_t FarTargetAddr = CurrInst->GetFarBranchTarget();
					if (BADADDR != FarTargetAddr) {
						assert((RETURN == DataFlowType) || (JUMP == DataFlowType) || (COND_BRANCH == DataFlowType));
						// Optimized tail calls, where the stack frame is down to zero at the call point,
						//  get RETURN as their DataFlowType. Might have to revisit that idea at some point. !!!!****!!!!
						if (this->FindDistantCodeFragment(FarTargetAddr)) {
							if (this->GetProg()->InsertUnsharedFragment(FarTargetAddr)) {
								// Fragment address was inserted in SMPProgram set, was not already there.
								pair<set<ea_t>::iterator, bool> InsertResult;
								InsertResult = FragmentWorkList.insert(FarTargetAddr);
								if (InsertResult.second) {
									SMP_msg("INFO: Found distant code fragment at %x that can be added to func, reached from %x\n",
										FarTargetAddr, addr);
#if 0
									if (FarTargetAddr < this->FirstEA) {
										this->FirstEA = FarTargetAddr;
									}
#endif
								}
								else {
									// These kind of fragments are generally only jumped to from one place,
									//  and jump back into the function that jumped into them. Very suspicious
									//  to encounter such a fragment more than once, and even if it happens,
									//  the insertion into the SMPProgram set should have failed due to already
									//  being present. This message and assertion should never be reached.
									SMP_msg("FATAL ERROR: Distant fragment at %x reached from %x already reached from same function.\n",
										FarTargetAddr, addr);
									assert(InsertResult.second); // sanity lost; shut down
								}
							}
							else { // Fragment address was already in SMPProgram set
								; // Probably added in loop at beginning that found unshared fragments.
#if 0
								// These kind of fragments are generally only jumped to from one place,
								//  and jump back into the function that jumped into them. Very suspicious
								//  to encounter such a fragment more than once.
								SMP_msg("WARNING: Distant fragment at %x reached from %x has already been processed.\n",
									FarTargetAddr, addr);
#endif
							}
						}
						else if (!this->GetProg()->IsUnsharedFragment(FarTargetAddr)) {
							this->AllCallTargets.push_back(FarTargetAddr);
							this->DirectCallTargets.push_back(FarTargetAddr);
						}
					}
				}

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

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

#if SMP_DEBUG_CONTROLFLOW
		SMP_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
					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;

				}
			} // 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 = ...)

#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;
	list<SMPInstr *>::iterator InstIter;
	SMPInstr *CurrInst;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++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
	for (InstIter = this->Instrs.begin(); 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

	for (InstIter = this->Instrs.begin(); 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();
		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.
			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;
				}
			}
#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();
#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 %x is shared chunk.\n", 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;

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