SMPFunction.cpp

					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_DATAFLOW
				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,
	//     and no USEs escape into other SSA names of a different 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 DebugFlag = (0 == strcmp("hash_string", this->GetFuncName()));
	list<SMPInstr>::iterator CurrInst;
#if 1
	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.
	do {
		changed = false;
		// Step one: Infer types within instructions, context free.
		for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
			if (DebugFlag) msg("Inferring types for %s\n", CurrInst->GetDisasm());
			changed = (changed || CurrInst->InferTypes());
		}
	} while (changed);
	return;
} // end of SMPFunction::InferTypes()

// 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);
	}
	if (this->UseFP) {
		qfprintf(AnnotFile, "USEFP ");
	}
	else {
		qfprintf(AnnotFile, "NOFP ");
	}
	if (this->FuncInfo.does_return()) {
		qfprintf(AnnotFile, "\n");
	}
	else {
		qfprintf(AnnotFile, "NORET \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) {
		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);
		}
	}  // end for (ea_t addr = FuncInfo.startEA; ...)
	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()