SMPFunction.cpp

#endif
					if (DebugFlag && (*DomFrontIter > this->BlockCount)) {
						msg("ERROR: DomFront block # %d out of range.\n", *DomFrontIter);
					}
					list<SMPBasicBlock>::iterator PhiBlock = this->RPOBlocks[*DomFrontIter];
					// Before inserting a phi function for the current name in *PhiBlock,
					//  see if the current name is LiveIn for *PhiBlock. If not, there
					//  is no need for the phi function. This check is what makes the SSA
					//  a fully pruned SSA.
					if (PhiBlock->IsLiveIn(*NameIter)) {
						size_t NumPreds = PhiBlock->GetNumPreds();
						DefOrUse CurrRef(*NameIter);
						SMPPhiFunction CurrPhi(CurrNameIndex, CurrRef);
						for (size_t NumCopies = 0; NumCopies < NumPreds; ++NumCopies) {
							CurrPhi.PushBack(CurrRef); // inputs to phi
						}
						if (PhiBlock->AddPhi(CurrPhi)) {
							// If not already in Phi set, new phi function was inserted.
							WorkList.push_back(PhiBlock->GetNumber());
#if SMP_DEBUG_DATAFLOW
							msg("Added phi for name %d at top of block %d\n", CurrNameIndex, PhiBlock->GetNumber());
#endif
						}
					}
					else {
						if (DebugFlag) {
							msg("Global %d not LiveIn for block %d\n", CurrNameIndex, PhiBlock->GetNumber());
						}
					}
				} // end for all blocks in the dominance frontier
				// Remove current block number from the work list
				if (DebugFlag) {
					msg("Removing block %d from work list.\n", *WorkIter);
				}
				WorkIter = WorkList.erase(WorkIter);
			} // end for all block numbers in the work list
		} // end while the work list is not empty
		if (DebugFlag) msg("WorkList empty.\n");
	} // end for all elements of the GlobalNames set
	return;
} // end of SMPFunction::InsertPhiFunctions()

// Build the dominator tree.
void SMPFunction::BuildDominatorTree(void) {
	size_t index;
	// First, fill the DomTree vector with the parent numbers filled in and the child lists
	//  left empty.
	for (index = 0; index < this->IDom.size(); ++index) {
		pair<int, list<int> > DomTreeEntry;
		DomTreeEntry.first = this->IDom.at(index);
		DomTreeEntry.second.clear();
		this->DomTree.push_back(DomTreeEntry);
	}
	// Now, push the children onto the appropriate lists.
	for (index = 0; index < this->IDom.size(); ++index) {
		// E.g. if block 5 has block 3 as a parent, then we fetch the number 3
		//  using the expression this->DomTree.at(index).first, which was just
		//  initialized in the previous loop. Then we go to DomTree entry 3 and push
		//  the number 5 on its child list.
		int parent = this->DomTree.at(index).first;
		if (parent != index) // block can dominate itself, but not in DomTree!
			this->DomTree.at(parent).second.push_back((int) index);
	}

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

// Helper for SSA subscript renumbering: return the next SSA number for the global name
//  and increment the SSACounter to prepare the next number. Push the returned number onto
//  the SSAStack for the global name.
int SMPFunction::SSANewNumber(size_t GlobNameIndex) {
	int Subscript = this->SSACounter.at(GlobNameIndex);
	++(this->SSACounter[GlobNameIndex]);
	this->SSAStack[GlobNameIndex].push_back(Subscript);
	return Subscript;
} // end of SMPFunction::SSANewNumber()

// Main helper for SSA subscript renumbering. Renumber within block throughout its phi
//  functions, then its DEFs and USEs, then its phi successors. Recurse then on all
//  successors in the dominator tree.
void SMPFunction::SSARename(int BlockNumber) {
	assert(0 <= BlockNumber);
	assert(BlockNumber < this->BlockCount);
	list<SMPBasicBlock>::iterator CurrBlock = this->RPOBlocks.at((size_t) BlockNumber);

	bool DumpFlag = false;
#if SMP_DEBUG_DATAFLOW
	DumpFlag |=	(0 == strcmp("main", this->GetFuncName()));
	DumpFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
	DumpFlag |= (0 == strcmp("image_to_texture", this->GetFuncName()));
#endif

	if (DumpFlag) msg("Entered SSARename for block number %d\n", BlockNumber);

	// For each phi function at the top of the block, rename the DEF of the phi function
	//  using SSANewNumber() on the global name index.
	set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
	list<SMPPhiFunction> TempPhiList;
	int GlobalNameIndex;
	for (CurrPhi = CurrBlock->GetFirstPhi(); CurrPhi != CurrBlock->GetLastPhi(); ++CurrPhi) {
		GlobalNameIndex = CurrPhi->GetIndex();
		assert(0 <= GlobalNameIndex);
		int NewSSANum = this->SSANewNumber((size_t) GlobalNameIndex);
#if 0
			// g++ is a pain in the neck and won't allow changes to the set item
			//  through CurrPhi, which it types as a const iterator, so this next line does
			//  not compile in g++.
		CurrPhi->SetSSADef(NewSSANum);
#else
		SMPPhiFunction TempPhi = (*CurrPhi);
		TempPhi.SetSSADef(NewSSANum);
		TempPhiList.push_back(TempPhi);
#endif
	}
	// Go back through the Phi function set and replace the items that need to be updated.
	//  Thank you g++ for being a pain.
	list<SMPPhiFunction>::iterator TempIter;
	for (TempIter = TempPhiList.begin(); TempIter != TempPhiList.end(); ++TempIter) {
		// Use the op_t from the first phi use, because they are all the same.
		bool Erased = CurrBlock->ErasePhi(TempIter->GetPhiRef(0).GetOp());
		assert(Erased);
		// Now we can add back the phi function that had the DEF SSA number changed.
		bool Added = CurrBlock->AddPhi(*TempIter);
		assert(Added);
	}
	TempPhiList.clear();
	if (DumpFlag) msg("Processed phi functions at top.\n");

	// For each instruction in the block, rename all global USEs and then all global DEFs.
	list<list<SMPInstr>::iterator>::iterator CurrInst;
	for (CurrInst = CurrBlock->GetFirstInstr(); CurrInst != CurrBlock->GetLastInstr(); ++CurrInst) {
		set<DefOrUse, LessDefUse>::iterator CurrUse = (*CurrInst)->GetFirstUse();
		while (CurrUse != (*CurrInst)->GetLastUse()) {
			// See if Use is a global name.
			set<op_t, LessOp>::iterator GlobIter = this->GlobalNames.find(CurrUse->GetOp());
			if (GlobIter != this->GlobalNames.end()) { // found it
				unsigned int GlobIndex = ExtractGlobalIndex(*GlobIter);
				if (GlobIndex > this->SSAStack.size()) {
					// Get some debug info out to the log file before we crash.
					msg("Bad GlobIndex: %d\n", GlobIndex);
					msg("Error in function %s\n", this->GetFuncName());
					exit(EXIT_FAILURE);
				}
				// Set the SSA number for this use to the top of stack SSA # (back())
				int NewSSANum;
				if (this->SSAStack.at(GlobIndex).empty()) {
					// No top of stack entry to read.
#if SMP_DEBUG_UNINITIALIZED_SSA_NAMES
					if (!(*CurrInst)->MDIsPopInstr()) {
						// POP uses the stack offset and generates spurious
						//  uninitialized variable messages for [esp+0].
						msg("WARNING: function %s : Use of uninitialized variable: ",
							this->GetFuncName());
						msg(" Variable: ");
						PrintListOperand(*GlobIter);
						msg(" Block number: %d Address: %x Instruction: %s\n", BlockNumber,
							(*CurrInst)->GetAddr(), (*CurrInst)->GetDisasm());
					}
#endif
					NewSSANum = SMP_SSA_UNINIT;
				}
				else {
					NewSSANum = this->SSAStack.at(GlobIndex).back();
				}
				CurrUse = (*CurrInst)->SetUseSSA(CurrUse->GetOp(), NewSSANum);
			}
			++CurrUse;
		} // end for all USEs
		set<DefOrUse, LessDefUse>::iterator CurrDef = (*CurrInst)->GetFirstDef();
		while (CurrDef != (*CurrInst)->GetLastDef()) {
			// See if Def is a global name.
			set<op_t, LessOp>::iterator GlobIter = this->GlobalNames.find(CurrDef->GetOp());
			if (GlobIter != this->GlobalNames.end()) { // found it
				unsigned int GlobIndex = ExtractGlobalIndex(*GlobIter);
				// Set the SSA number for this DEF to the SSANewNumber top of stack
				CurrDef = (*CurrInst)->SetDefSSA(CurrDef->GetOp(), this->SSANewNumber(GlobIndex));
			}
			++CurrDef;
		} //  end for all DEFs
	} // end for all instructions
	if (DumpFlag) msg("Processed all instructions.\n");

	// For all control flow graph (not dominator tree) successors, fill in the current
	//  (outgoing) SSA number in the corresponding USE slot in the phi function, for all
	//  global names appearing in phi functions.
	list<list<SMPBasicBlock>::iterator>::iterator SuccIter;
	for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
		// What position in the Preds list of this successor is CurrBlock?
		int ListPos = (*SuccIter)->GetPredPosition(BlockNumber);
		assert(0 <= ListPos);

		// Go through all phi functions in this successor. At ListPos position in the
		//  incoming arguments for that phi function, set the SSA number to the SSA number
		//  in the top of stack entry for the global name associated with that phi function.
		set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
		for (CurrPhi = (*SuccIter)->GetFirstPhi(); CurrPhi != (*SuccIter)->GetLastPhi(); ++CurrPhi) {
			int GlobIndex = CurrPhi->GetIndex();
			int CurrSSA;
			if (this->SSAStack.at(GlobIndex).empty()) {
				// No top of stack entry to read.
#if SMP_DEBUG_UNINITIALIZED_SSA_NAMES
				msg("WARNING: function %s : Path to use of uninitialized variable: ",
					this->GetFuncName());
				msg(" Variable: ");
				PrintListOperand(CurrPhi->GetAnyOp());
				msg(" Block number: %d Successor block number: %d\n", BlockNumber,
					(*SuccIter)->GetNumber());
#endif
				CurrSSA = SMP_SSA_UNINIT;
			}
			else {
				CurrSSA = this->SSAStack.at(GlobIndex).back();  // fetch from top of stack
			}
#if 0
			// g++ is a pain in the neck and won't allow changes to the set item
			//  through CurrPhi, which it types as a const iterator, so this next line does
			//  not compile in g++. C++ does not know how to distinguish between changing
			//  the field that ordering is based on, and other fields, so g++ has to be
			//  strict, I guess.
			CurrPhi->SetSSARef(ListPos, CurrSSA);
#else
			SMPPhiFunction TempPhi = (*CurrPhi);
			TempPhi.SetSSARef(ListPos, CurrSSA);
			TempPhiList.push_back(TempPhi);
			if (DumpFlag && (BlockNumber >= 3) && (BlockNumber <= 4)) {
				msg("BlockNumber: %d  ListPos: %d\n", BlockNumber, ListPos);
			}
#endif
		} // end for all phi functions in successor
		// Go back through the Phi function set and replace the items that need to be updated.
		//  Thank you g++ for being a pain.
		for (TempIter = TempPhiList.begin(); TempIter != TempPhiList.end(); ++TempIter) {
			if (DumpFlag && (BlockNumber >= 3) && (BlockNumber <= 4)) {
				msg("Special before phi dump:\n");
				set<SMPPhiFunction, LessPhi>::iterator FoundPhi;
				FoundPhi = (*SuccIter)->FindPhi(TempIter->GetAnyOp());
				FoundPhi->Dump();
			}
			// Use the op_t from the first phi use, because they are all the same.
			bool Erased = (*SuccIter)->ErasePhi(TempIter->GetPhiRef(0).GetOp());
			assert(Erased);
			// Now we can add back the phi function that had one SSA number changed.
			bool Added = (*SuccIter)->AddPhi(*TempIter);
			assert(Added);
			if (DumpFlag && (BlockNumber >= 3) && (BlockNumber <= 4)) {
				msg("Special after phi dump:\n");
				set<SMPPhiFunction, LessPhi>::iterator FoundPhi;
				FoundPhi = (*SuccIter)->FindPhi(TempIter->GetAnyOp());
				FoundPhi->Dump();
			}
		}
		TempPhiList.clear();
	} // end for all successors of CurrBlock
	if (DumpFlag) msg("Processed successor phi functions.\n");

	// For each successor in the dominator tree, recurse.
	list<int>::iterator ChildIter;
	for (ChildIter = this->DomTree[BlockNumber].second.begin();
		ChildIter != this->DomTree[BlockNumber].second.end();
		++ChildIter) {
			this->SSARename(*ChildIter);
	}
	if (DumpFlag) msg("Finished recursion.\n");

	// Pop off all SSAStack entries pushed during this block. I.e. for each global name,
	//  pop its SSAStack once per DEF and once per phi function in this block.
	for (CurrPhi = CurrBlock->GetFirstPhi(); CurrPhi != CurrBlock->GetLastPhi(); ++CurrPhi) {
		GlobalNameIndex = CurrPhi->GetIndex();
		this->SSAStack.at((size_t) GlobalNameIndex).pop_back();
	}
	if (DumpFlag) msg("Popped off entries due to phi functions.\n");
	for (CurrInst = CurrBlock->GetFirstInstr(); CurrInst != CurrBlock->GetLastInstr(); ++CurrInst) {
		set<DefOrUse, LessDefUse>::iterator CurrDef;
		for (CurrDef = (*CurrInst)->GetFirstDef(); CurrDef !=(*CurrInst)->GetLastDef(); ++CurrDef) {
			// See if DEF is a global name.
			set<op_t, LessOp>::iterator GlobIter = this->GlobalNames.find(CurrDef->GetOp());
			if (GlobIter != this->GlobalNames.end()) { // found it
				unsigned int GlobIndex = ExtractGlobalIndex(*GlobIter);
				this->SSAStack.at((size_t) GlobIndex).pop_back();
			}
		} //  end for all DEFs
	} // end for all instructions
	if (DumpFlag) msg("Popped off entries due to instructions.\n");

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

// Main driver of SSA subscript renumbering.
void SMPFunction::SSARenumber(void) {
	if (0 >= this->GlobalNames.size())
		return;  // no names to renumber

	// Initialize stacks and counters of SSA numbers.
	size_t GlobIndex;
	for (GlobIndex = 0; GlobIndex < this->GlobalNames.size(); ++GlobIndex) {
		list<int> DummyList;
		this->SSACounter.push_back(0);
		this->SSAStack.push_back(DummyList);
	}

	// Recurse through the dominator tree starting with node 0.
	this->SSARename(0);
	return;
} // end of SMPFunction::SSARenumber()

// Main driver for the type inference system.
void SMPFunction::InferTypes(void) {
	// The type inference system is an iteration over four analysis steps, until
	//  a fixed point is reached:
	// 1) Within an instruction, set types of operators based on the operator type,
	//     the operand types, and the instruction type category, and propagate the
	//     type of the SMP_ASSIGN operator to its DEF.
	// 2) Propagate the type of a DEF along its SSA chain to all USEs of that SSA name.
	// 3) If all USEs of an SSA name have the same type, but the DEF has no type,
	//     then infer that the DEF must have the same type.
	// 4) If all references to a memory location have the same type, mark that memory
	//     location as having that type.
	//
	// The type inference system will mark DEFs and USEs in each instruction's DEF and USE
	//  sets with an inferred type. This inference USEs is not conclusive for other USEs
	//  outside of that instruction. For example, a pointer could be read in from memory
	//  and used as a pointer, then hashed using an arithmetic operation. If the arithmetic
	//  operation always treats its source operands as NUMERIC and produces a NUMERIC
	//  result, e.g. SMP_BITWISE_XOR, then the USE of that pointer is NUMERIC within
	//  this xor instruction. If the DEF at the beginning of the SSA chain for the pointer
	//  is eventually marked as POINTER, then all USEs in the chain will be marked POINTER
	//  as well (see step 2 above). This inconsistency along the USE chain is perfectly
	//  acceptable in our type system. It is immportant to mark the USEs according to how
	//  we observe them being used, because consistent USEs will propagate back up to
	//  the DEF in step 3 above.

	bool changed;
	bool NewChange;
	bool DebugFlag = (0 == strcmp("weightadj", this->GetFuncName()));
	list<SMPInstr>::iterator CurrInst;
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	set<DefOrUse, LessDefUse>::iterator NextDef;
	list<SMPBasicBlock>::iterator CurrBlock;
#if 1
	DebugFlag = false;
	if (DebugFlag) {
		this->Dump();
	}
	// One time only: Set the types of immediate values, flags register, stack and frame
	//  pointers, and floating point registers.
	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
		if (DebugFlag) {
			msg("SetImmedTypes for inst at %x: %s\n", CurrInst->GetAddr(), CurrInst->GetDisasm());
		}
		CurrInst->SetImmedTypes(this->UseFP);
	}
#endif

	// Iterate until no more changes: set types in DEF and USE lists based on RTL
	//  operators and the instruction category, SSA DEF-USE chains, etc.
	do {
		changed = false;
		// Step one: Infer types within instructions, context free.
		// Step two, propagating DEF types to all USEs, happens within step one
		//  whenever a DEF type is set for the first time.
		for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
			if (DebugFlag) msg("Inferring types for %s\n", CurrInst->GetDisasm());
			NewChange = CurrInst->InferTypes();
			changed = (changed || NewChange);
		}
		if (DebugFlag) msg("Finished type inference steps 1 and 2.\n");
		// Step three: If all USEs of an SSA name have the same type, but the DEF has no
		//  type, then infer that the DEF must have the same type.
		this->TypedDefs = 0;
		this->UntypedDefs = 0;
		for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
			// Find any DEF that still has type UNINIT.
			CurrDef = CurrInst->GetFirstDef();
			while (CurrDef != CurrInst->GetLastDef()) {
				// Set erase() and insert() are needed to change types of DEFs, so
				//  get hold of the next iterator value now.
				NextDef = CurrDef;
				++NextDef;
				if (UNINIT != CurrDef->GetType()) {
					++(this->TypedDefs);
				}
				else {
					++(this->UntypedDefs);
					op_t DefOp = CurrDef->GetOp();
					ea_t DefAddr = CurrInst->GetAddr();
					// Call inference method based on whether it is a block-local
					//  name or a global name.
					if (CurrInst->GetBlock()->IsLocalName(DefOp)) {
						set<op_t, LessOp>::iterator NameIter;
						NameIter = CurrInst->GetBlock()->FindLocalName(DefOp);
						assert(CurrInst->GetBlock()->GetLastLocalName() != NameIter);
						unsigned int LocIndex = ExtractGlobalIndex(*NameIter);
						NewChange = CurrInst->GetBlock()->InferLocalDefType(DefOp, LocIndex, DefAddr);
						if (NewChange) {
							--(this->UntypedDefs);
							++(this->TypedDefs);
						}
						changed = (changed || NewChange);
					}
					else {
#if 1
						// global name
						int SSANum = CurrDef->GetSSANum();
						NewChange = this->InferGlobalDefType(DefOp, SSANum);
						if (NewChange) {
							--(this->UntypedDefs);
							++(this->TypedDefs);
						}
						changed = (changed || NewChange);
#endif
					}
				}
				CurrDef = NextDef;
			} // end while all DEFs in the DEF set
		} // end for all instructions
		if (DebugFlag) msg("Finished type inference step 3.\n");
		if (!changed) { // Check for Phi function DEFs that are still UNINIT
			for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
				changed |= CurrBlock->InferAllPhiDefTypes();
			}
		}
	} while (changed);
	return;
} // end of SMPFunction::InferTypes()

// For the UNINIT type DEF DefOp, see if all its USEs have
//  a single type. If so, set the DEF to that type and return true, else return false.
bool SMPFunction::InferGlobalDefType(op_t DefOp, int SSANum) {
	bool changed = false;
	bool DebugFlag = (0 == strcmp("hash_string", this->GetFuncName()));
#if 1

	if (DebugFlag) {
		msg("InferGlobalDefType for SSANum %d of ", SSANum);
		PrintOperand(DefOp);
		msg("\n");
	}

	list<SMPInstr>::iterator InstIter;
	list<SMPInstr>::iterator DefInstIter;
	bool DefFound = false;
	set<DefOrUse, LessDefUse>::iterator CurrDef;

	assert(0 <= SSANum);
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	// Go through all instructions in the block and find the DEF and the instructions
	//  that have USEs of DefOp with SSANum. If all USEs in the chain have
	//  a single type (other than UNINIT), change the DEF type to match the USE type
	//  and set changed to true.
	bool FirstUseSeen = false;
	SMPOperandType UseType;
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		if (!DefFound) {
			CurrDef = InstIter->FindDef(DefOp);
			if (CurrDef != InstIter->GetLastDef()) { // found DEF of DefOp
				if (CurrDef->GetSSANum() == SSANum) { // matched SSA number
					DefFound = true;
					DefInstIter = InstIter;
					assert(UNINIT == CurrDef->GetType());
				}
			}
		}
		CurrUse = InstIter->FindUse(DefOp);
		if (CurrUse != InstIter->GetLastUse()) { // found a USE of DefOp
			if (CurrUse->GetSSANum() == SSANum) { // matched SSA number
				if (!FirstUseSeen) {
					FirstUseSeen = true;
					UseType = CurrUse->GetType();
					if (UNINIT == UseType)
						return false;
				}
				else {
					if (CurrUse->GetType() != UseType)
						return false;  // no consistent type
				}
			}
		}
	} // end for all instructions

	if (DefFound && FirstUseSeen) {
		// We have a consistent type, else we would have returned false above.
		assert(UNINIT != UseType);
		if (DebugFlag) msg("Inferring global DEF of type %d\n", UseType);
		CurrDef = DefInstIter->SetDefType(DefOp, UseType);
		changed = true;
	}
	else if (!DefFound) {
		// It could be that the DEF is provided by a Phi function.
		list<SMPBasicBlock>::iterator CurrBlock;
		set<SMPPhiFunction, LessPhi>::iterator DefPhi;
		for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
			DefPhi = CurrBlock->FindPhi(DefOp);
			if (CurrBlock->GetLastPhi() != DefPhi) { // block has Phi for DefOp
				// See if the SSA subscripts match
				if (DefPhi->GetDefSSANum() == SSANum) {
					// Found a match. Set this Phi DEF type to UseType.
					if (DebugFlag) msg("Inferring Phi DEF of type %d\n", UseType);
					DefPhi = CurrBlock->SetPhiDefType(DefOp, UseType);
					changed = true;
					DefFound = true;
					break;
				}
			}
		}
		if (!DefFound) { // not an instruction DEF or a Phi DEF
			msg("ERROR: Could not find global DEF with SSANum %d for: ", SSANum);
			PrintOperand(DefOp);
			msg("\n");
		}
	}
	else { // DefFound but not FirstUseSeen
		// If the DefOp is is the LiveOut set, then the USEs could be in successor
		//  blocks, including in their Phi functions. If the block returns, then
		//  the DEFs could be used in the caller.
		if (!(DefInstIter->GetBlock()->IsLiveOut(DefOp)
			  || DefInstIter->GetBlock()->HasReturn())) {
			// We probably want to set the DEF type to NUMERIC if there are no uses.
			//  Have to check these cases out manually in the *.asm first.  **!!**
			msg("WARNING: global DEF with no USEs for SSANum %d DefOp: ", SSANum);
			PrintOperand(DefOp);
			msg("\n");
		}
	}
#endif
	return changed;
} // end of SMPFunction::InferGlobalDefType()

// Emit all annotations for the function, including all per-instruction
//  annotations.
void SMPFunction::EmitAnnotations(FILE *AnnotFile) {
	// Emit annotation for the function as a whole.
	if (this->StaticFunc) {
		qfprintf(AnnotFile,	"%10x %6d FUNC LOCAL  %s ", this->FuncInfo.startEA,
			this->Size, this->FuncName);
	}
	else {
		qfprintf(AnnotFile,	"%10x %6d FUNC GLOBAL %s ", this->FuncInfo.startEA,
			this->Size, this->FuncName);
	}
	switch (this->ReturnAddrStatus)
	{
		case FUNC_UNKNOWN:
		{
			qfprintf(AnnotFile, "FUNC_UNKNOWN ");
			break;
		}
		case FUNC_SAFE:
		{
			qfprintf(AnnotFile, "FUNC_SAFE ");
			break;
		}
		case FUNC_UNSAFE:
		{
			qfprintf(AnnotFile, "FUNC_UNSAFE ");
			break;
		}
		default:
			assert(0);	
	}
	if (this->UseFP) {
		qfprintf(AnnotFile, "USEFP ");
	}
	else {
		qfprintf(AnnotFile, "NOFP ");
	}
	if (this->FuncInfo.does_return()) {
		qfprintf(AnnotFile, "RET ");
	}
	else {
		qfprintf(AnnotFile, "NORET ");
	}
#ifdef SMP_DEBUG_FUNC
	if (this->IsLeaf())
		qfprintf(AnnotFile, "FUNC_LEAF ");
	// store the return address
	qfprintf(AnnotFile,"%10x ", this->FuncInfo.endEA - 1);
#endif
	qfprintf(AnnotFile, "\n");

	// Loop through all instructions in the function.
	// Output optimization annotations for those
	//  instructions that do not require full computation
	//  of their memory metadata by the Memory Monitor SDT.
	list<SMPInstr>::iterator CurrInst;
	bool AllocSeen = false; // Reached LocalVarsAllocInstr yet?
	bool DeallocTrigger = false;
	for (CurrInst = Instrs.begin(); CurrInst != Instrs.end(); ++CurrInst) {

#if SMP_USE_SSA_FNOP_MARKER
		if (this->Instrs.begin() == CurrInst)
			continue;  // skip marker instruction
#endif

		ea_t addr = CurrInst->GetAddr();
		if (this->LocalVarsAllocInstr == addr) {
			AllocSeen = true;
			this->EmitStackFrameAnnotations(AnnotFile, CurrInst);
		}
		// If this is the instruction which deallocated space
		//  for local variables, we set a flag to remind us to 
		//  emit an annotation on the next instruction.
		// mmStrata wants the instruction AFTER the
		//  deallocating instruction, so that it processes
		//  the deallocation after it happens. It inserts
		//  instrumentation before an instruction, not
		//  after, so it will insert the deallocating
		//  instrumentation before the first POP of callee-saved regs,
		//  if there are any, or before the return, otherwise.
		if (addr == this->LocalVarsDeallocInstr) {
			DeallocTrigger = true;
		}
		else if (DeallocTrigger) { // Time for annotation
			qfprintf(AnnotFile,	"%10x %6d DEALLOC STACK esp - %d %s\n", addr,
				LocalVarsSize, LocalVarsSize, CurrInst->GetDisasm());
			DeallocTrigger = false;
		}

		if (this->HasGoodRTLs()) {
			CurrInst->EmitTypeAnnotations(this->UseFP, AllocSeen, AnnotFile);
		}
		else {
			CurrInst->EmitAnnotations(this->UseFP, AllocSeen, AnnotFile);
		}
		if (CurrInst->MDIsReturnInstr() && this->GetReturnAddressStatus() == FUNC_SAFE )
			CurrInst->EmitSafeReturn(AnnotFile);
	}  // end for all instructions
	return;
} // end of SMPFunction::EmitAnnotations()

// Debug output dump.
void SMPFunction::Dump(void) {
	list<SMPBasicBlock>::iterator CurrBlock;
	msg("Debug dump for function: %s\n", this->GetFuncName());
	for (size_t index = 0; index < this->IDom.size(); ++index) {
		msg("IDOM for %d: %d\n", index, this->IDom.at(index));
	}
	for (size_t index = 0; index < this->DomTree.size(); ++index) {
		msg("DomTree for %d: ", index);
		list<int>::iterator DomIter;
		for (DomIter = this->DomTree.at(index).second.begin();
			DomIter != this->DomTree.at(index).second.end();
			++DomIter) {
				msg("%d ", *DomIter);
		}
		msg("\n");
	}
	msg("Global names: \n");
	set<op_t, LessOp>::iterator NameIter;
	for (NameIter = this->GlobalNames.begin(); NameIter != this->GlobalNames.end(); ++NameIter) {
		msg("index: %d ", ExtractGlobalIndex(*NameIter));
		PrintListOperand(*NameIter);
		msg("\n");
	}
	msg("Blocks each name is defined in: \n");
	for (size_t index = 0; index < this->BlocksDefinedIn.size(); ++index) {
		msg("Name index: %d Blocks: ", index);
		list<int>::iterator BlockIter;
		for (BlockIter = this->BlocksDefinedIn.at(index).begin();
			BlockIter != this->BlocksDefinedIn.at(index).end();
			++BlockIter) {
			msg("%d ", *BlockIter);
		}
		msg("\n");
	}
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		// Dump out the function number and data flow sets before the instructions.
		CurrBlock->Dump();
	}
	return;
} // end of SMPFunction::Dump()


// Analyzes the function to see if the return address can be marked as safe 
void SMPFunction::MarkFunctionSafe() {
#ifdef SMP_DEBUG_FUNC
	msg(" Analyzing function name %s and isLeaf=%d ", this->GetFuncName(), this->IsLeaf());
#endif

	ReturnAddrStatus = FUNC_SAFE;
	if (!AnalyzedSP || this->IndirectCalls) {
#ifdef SMP_DEBUG_FUNC 
		if (!AnalyzedSP)
			msg(" Function marked as unsafe %s coz AnalyzedSP = false\n", this->GetFuncName());	
		else
			msg(" Function marked as unsafe %s coz function has indirect calls\n", this->GetFuncName());
#endif

		ReturnAddrStatus = FUNC_UNSAFE;
		return;
	}

	if (!this->DirectCallTargets.empty()) {
#ifdef SMP_DEBUG_FUNC 
		msg(" Function marked as unknown %s \n", this->GetFuncName());
#endif
		ReturnAddrStatus = FUNC_UNKNOWN;
	}
	if (this->IndirectJumps) {
#ifdef SMP_DEBUG_FUNC
		msg(" Function marked as unsafe due to indirect jumps %s\n", this->GetFuncName());
#endif
		ReturnAddrStatus = FUNC_UNSAFE;
		return ;
	}
	if (this->HasSharedChunks()) {
		ReturnAddrStatus = FUNC_UNSAFE;
		return;
	}
	list<SMPInstr>::iterator Instructions;

	// while processing the stack pointer write the prolog  containing for
	// saving frame register and allcating local variables needs to be
	// handled
	bool SaveEBP = false;
	bool XferESPtoEBP = false;
	for (Instructions = Instrs.begin(); Instructions != Instrs.end();	Instructions++) {

#if SMP_USE_SSA_FNOP_MARKER
		if (this->Instrs.begin() == Instructions)
			continue;  // skip marker instruction
#endif

#ifdef SMP_DEBUG_FUNC 
		msg(" Total number of defs for this instruction %d\n", Instructions->NumDefs());
#endif
		if (!SaveEBP) { // still looking for "push ebp"
			if (Instructions->MDIsPushInstr() && Instructions->GetCmd().Operands[0].is_reg(R_bp)) {
				SaveEBP = true;
				continue;
			}
		}
		else if (!XferESPtoEBP) { // found "push ebp", looking for "mov ebp,esp"
			insn_t CurrCmd = Instructions->GetCmd();
			if ((CurrCmd.itype == NN_mov)
					&& (Instructions->GetFirstDef()->GetOp().is_reg(R_bp))
					&& (Instructions->GetFirstUse()->GetOp().is_reg(R_sp))) {
				XferESPtoEBP = true;
				continue;
			}
		}
		ea_t address = Instructions->GetAddr();
		if (address == this->LocalVarsAllocInstr ||
		    address == this->LocalVarsDeallocInstr)
			continue;

		if (Instructions->MDIsStackPointerCopy(this->UseFP)) {
#ifdef SMP_DEBUG_FUNC 
			msg(" Function marked as unsafe %s due to stack pointer copy \n ", this->GetFuncName());
			msg("%s %x \n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
			ReturnAddrStatus = FUNC_UNSAFE;
			return;
		}
		if (Instructions->MDIsPushInstr()) {
			// not exactly sure how to handle this instruction
			// for the moment if its a push on a esp or usefp & ebp
			// mark as unsafe
			if (Instructions->GetCmd().Operands[0].is_reg(R_sp) || 	 
					( this->UseFP && Instructions->GetCmd().Operands[0].is_reg(R_bp))) {
#ifdef SMP_DEBUG_FUNC 
				msg(" Function marked as unsafe %s due to push on ebp or esp outside of function header \n", this->GetFuncName());	
				msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
				ReturnAddrStatus = FUNC_UNSAFE;
				return;
			}
			continue;
		}
		if (Instructions->MDIsPopInstr()) {
			// ignore pops for the moment
			 continue;
		}
		set<DefOrUse, LessDefUse>::iterator setIterator;
		for (setIterator = Instructions->GetFirstDef(); setIterator != Instructions->GetLastDef(); setIterator++) {
			op_t Operand = setIterator->GetOp();
			if (Operand.type == o_mem)	{
				// now o_mem can have sib byte as well, as
				// reported by IDA. check if the base reg is bp
				// and index reg is sp. If it is, then this is
				// probably a global write and can be marked
				// safe
				if (Operand.hasSIB) {
					int BaseReg = sib_base(Operand);
					short IndexReg = sib_index(Operand);
					if ((BaseReg == R_none || BaseReg == R_bp) &&
							(IndexReg == R_none || IndexReg == R_sp))					 {
						// go onto next def
						continue;
					}	
				}
				else {
					// o_mem should never have a base register (field should be zero)
					if ((Operand.reg == 0) || (Operand.reg == R_bp)) // ignore 
						continue;
				}
				ReturnAddrStatus = FUNC_UNSAFE;
				return;
			}
			if (Operand.type == o_displ) {
				if (Operand.hasSIB) {
					int BaseReg = sib_base(Operand);
					short IndexReg = sib_index(Operand);
					if (((BaseReg==R_sp || (this->UseFP && BaseReg == R_bp)))) {
						if (IndexReg == R_sp || IndexReg == R_none) {
							ea_t offset = Operand.addr;
							if (offset > this->LocalVarsSize ) {
#ifdef SMP_DEBUG_FUNC 
								msg(" Function marked as unsafe %s due to write above loc variables offset=%x  loc=%x\n ", this->GetFuncName(), offset, this->LocalVarsSize);	
								msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
								ReturnAddrStatus = FUNC_UNSAFE;
								return;
							}
						}
						else {
#ifdef SMP_DEBUG_FUNC 
							msg(" Function marked as unsafe %s due to index write above loc variables \n", this->GetFuncName());	
							msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
							ReturnAddrStatus = FUNC_UNSAFE;  
							return;
						}
					}
					else {
						 ReturnAddrStatus = FUNC_UNSAFE;
						 return;
					} 

				}
				else {
					// no index
					ushort BaseReg = Operand.reg;
					if (BaseReg == R_sp || (UseFP &&	BaseReg == R_bp)) {
						ea_t offset = Operand.addr;
						if (offset > this->LocalVarsSize ) {
#ifdef SMP_DEBUG_FUNC 
							msg(" Function marked as unsafe %s due to write above loc variables in no sib offset=%x loc=%x \n", this->GetFuncName(), offset, this->LocalVarsSize);
							msg("%s %x \n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
							ReturnAddrStatus = FUNC_UNSAFE;
							return;
						}
					}
					else {
						ReturnAddrStatus = FUNC_UNSAFE;
						return;
					}
				}
			}
			if (Operand.type == o_phrase)	{
				// so phrase is of the form [BASE_REG + IND ]
				// if the index register is missing just make sure that
				// the displacement is below stack frame top
				if (Operand.hasSIB) {
					// check the base reg
					int BaseReg = sib_base(Operand);
					short IndexReg = sib_index(Operand);
					// if index reg is used mark as unsafe 
					if ((BaseReg == R_sp || (this->UseFP && BaseReg == R_bp))
                   && (IndexReg != R_sp) && (IndexReg != R_none)) {
                 // index=sp implies there is no index register
#ifdef SMP_DEBUG_FUNC 
						msg(" Does function with phrase have displ %s %x  ", this->GetFuncName(), Operand.addr);	
#endif
						continue;
					}
					else {
						ReturnAddrStatus = FUNC_UNSAFE;
						return ;
					}
				}
				else {
					ushort BaseReg = Operand.reg;
					if (BaseReg == R_sp || (this->UseFP && BaseReg == R_bp))
						continue;
					ReturnAddrStatus = FUNC_UNSAFE;
					return;
				}
			}
		}
	}
} // end of SMPFunction::MarkFunctionSafe()