SMPFunction.cpp

#if SMP_DEBUG_TYPE_INFERENCE
		if (DebugFlag) SMP_msg("Finished type inference steps 1 and 2.\n");
#endif
		// 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;
		this->TypedPhiDefs = 0;
		this->UntypedPhiDefs = 0;
		// This step of the type inference might converge faster if we used a reverse iterator
		//  to go through the instructions, because we could infer a DEF, propagate it to
		//  the right hand side by making SMPInstr::InferOperatorType() public and calling it
		//  on the SMP_ASSIGN operator after we set the type of the left hand side (DEF). Any
		//  additional DEF inferences would be triggered mostly in the upwards direction by
		//  setting the type of one or more USEs in the current instruction. How much time gain
		//  could be achieved by doing this sequence is questionable.  !!!!****!!!!****
		for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
			CurrInst = (*InstIter);
			InstAddr = CurrInst->GetAddr();
			// 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;
				NewChange = false;
				if (UNINIT != CurrDef->GetType()) {
					++(this->TypedDefs);
				}
				else {
					op_t DefOp = CurrDef->GetOp();
					bool MemDef = (DefOp.type != o_reg);
					bool AliasedMemWrite = (MemDef && CurrDef->HasIndirectWrite());
					++(this->UntypedDefs);
					if (MDIsIndirectMemoryOpnd(DefOp, this->UseFP)  // relax this?
#if 0
						|| (o_mem == DefOp.type)
#endif
						|| AliasedMemWrite) {
						// Don't want to infer along DEF-USE chains for indirect
						//  memory accesses until we have alias analysis.
						++CurrDef;
						continue;
					}
					ea_t DefAddr = InstAddr;
					// Call inference method based on whether it is a block-local
					//  name or a global name.
					CurrBlock = CurrInst->GetBlock();
					if (CurrBlock->IsLocalName(DefOp)) {
						set<op_t, LessOp>::iterator NameIter;
						NameIter = CurrBlock->FindLocalName(DefOp);
						assert(CurrBlock->GetLastLocalName() != NameIter);
						unsigned int LocIndex = ExtractGlobalIndex(*NameIter);
						NewChange = CurrBlock->InferLocalDefType(DefOp, LocIndex, DefAddr);
						if (NewChange) {
							--(this->UntypedDefs);
							++(this->TypedDefs);
						}
						changed = (changed || NewChange);
					}
					else {
						// global name
						bool CallInst = ((CALL == CurrInst->GetDataFlowType())
							|| (INDIR_CALL == CurrInst->GetDataFlowType()));
						int DefSSANum = CurrDef->GetSSANum();
						SMPOperandType DefType = UNINIT;
						DefType = this->InferGlobalDefType(DefOp,
							DefSSANum, CurrBlock, CallInst, DefAddr);
						if (IsNotEqType(UNINIT, DefType)) {
							CurrDef = CurrInst->SetDefType(DefOp, DefType);
							--(this->UntypedDefs);
							++(this->TypedDefs);
							NewChange = true;
							// If we have one or more USEs of type POINTER and the
							//  other USEs are UNINIT, then InferGlobalDefType() will
							//  infer that it is a POINTER. We want to propagate POINTER
							//  to all the USEs now.
							if (IsDataPtr(DefType)) {
								this->ResetProcessedBlocks();
								CurrInst->GetBlock()->PropagateGlobalDefType(DefOp, DefType, DefSSANum, IsMemOperand(DefOp));
							}
						}
						changed = (changed || NewChange);
					} // end if local name ... else ...
				} // end if (UNINIT != CurrDef->GetType()) .. else ...
				CurrDef = NextDef;
			} // end while all DEFs in the DEF set
		} // end for all instructions
#if SMP_DEBUG_TYPE_INFERENCE
		if (DebugFlag) SMP_msg("Finished type inference step 3.\n");
#endif

		for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
			CurrBlock = (*BlockIter);
			changed |= CurrBlock->InferAllPhiDefTypes();
		}

#if SMP_DEBUG_TYPE_INFERENCE
		if (DebugFlag) SMP_msg("Finished unconditional phi type inference.\n");
#endif

#if SMP_CONDITIONAL_TYPE_PROPAGATION
		if (!changed) { // Try conditional type propagation
			changed |= this->ConditionalTypePropagation();
#if SMP_DEBUG_TYPE_INFERENCE
			if (DebugFlag) {
				SMP_msg("changed = %d after conditional type propagation.\n", changed);
			}
#endif
		}
#endif

	} while (changed);

	// With type inference finished, infer signedness from the types, e.g.
	//  POINTER and CODEPOINTER types must be UNSIGNED.
	if (FirstIter) { // Don't want profiler-dependent signedness in the system yet.
		for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
			(*InstIter)->InferSignednessFromSMPTypes(this->UsesFramePointer());
		}
	}

	// Record the meet of all register types that reach RETURN instructions.
	this->MDFindReturnTypes();
	return;
} // end of SMPFunction::InferTypes()

// determine signedness and width info for all operands
void SMPFunction::InferFGInfo(void) {
	bool changed, NewChange;
	unsigned short IterCount = 0;
	list<SMPInstr *>::iterator InstIter;
	list<SMPBasicBlock *>::iterator BlockIter;
	SMPBasicBlock *CurrBlock;

	do {
		changed = false;
		++IterCount;
		for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
			SMPInstr *CurrInst = (*InstIter);
			NewChange = CurrInst->InferFGInfo(IterCount);
			changed = (changed || NewChange);
		}
		if (changed) {
			for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
				CurrBlock = (*BlockIter);
				CurrBlock->PropagatePhiFGInfo();
			}
		}
#if STARS_AGGRESSIVE_SIGNEDNESS_PROPAGATION
		if (!changed) {
			changed = this->PropagateSignedness();
		}
#endif
	} while (changed);

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

// Apply the profiler information to this function once we've inferred everything we can about it.
void SMPFunction::ApplyProfilerInformation(ProfilerInformation* pi)
{
	assert(pi);

	// If no profiler annotations are available, save time.
	if (0 == pi->GetProfilerAnnotationCount())
		return;

	SetIsSpeculative(true);	

	list<SMPInstr *>::iterator InstIter;
	
	bool DebugFlag = false;
#if SMP_DEBUG_PROFILED_TYPE_INFERENCE
	DebugFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
#endif

	// for each instruction in this function 
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		// lookup whether a load at this instruction was profiled as always numeric 
		InstructionInformation* ii = pi->GetInfo(CurrInst->GetAddr());
		if (ii && DebugFlag)
			SMP_msg("Found instruction information for %lx\n", (unsigned long) CurrInst->GetAddr());
		if (ii && ii->isNumeric()) {
#if SMP_DEBUG_PROFILED_TYPE_INFERENCE
			SMP_msg("Found instruction information for %lx and it's numeric!\n", (unsigned long) CurrInst->GetAddr());
#endif
			CurrInst->UpdateMemLoadTypes((SMPOperandType)(NUMERIC|PROF_BASE));
		}

		// lookup whether this instruction has been profiled as an indirect call
		set<ea_t> indirect_call_targets = pi->GetIndirectCallTargets(CurrInst->GetAddr());

		for (set<ea_t>::iterator ict_iter = indirect_call_targets.begin();
			ict_iter != indirect_call_targets.end();
			++ict_iter)
		{
			ea_t target = *ict_iter;
			pair<set<ea_t>::iterator, bool> InsertResult;
			InsertResult = this->IndirectCallTargets.insert(target);
			if (InsertResult.second && (!vector_exists(target, AllCallTargets)))
				AllCallTargets.push_back(target);

		}

	}
	return;
}	// end of SMPFunction::ApplyProfilerInformation

// 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 type,
//  else return UNINIT.
// If DefAddr == BADADDR, then the DEF is in a Phi function, not an instruction.
SMPOperandType SMPFunction::InferGlobalDefType(op_t DefOp, int SSANum, SMPBasicBlock *DefBlock, bool CallInst, ea_t DefAddr) {
	bool DebugFlag = false;
	bool FoundNumeric = false;
	bool FoundPointer = false;
	bool FoundUnknown = false;
	bool FoundUninit = false;
	bool FoundDEF;
	bool DefEscapes = true;

#if SMP_DEBUG_TYPE_INFERENCE
	DebugFlag |= (0 == strcmp("mem_init", this->GetFuncName()));
#endif

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

	vector<SMPInstr *>::iterator InstIter;

	assert(0 <= SSANum);
	set<DefOrUse, LessDefUse>::iterator CurrUse, CurrDef;
	// Go through all instructions in the block and find 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.
	SMPOperandType UseType = UNINIT;
	SMPOperandType PtrType = UNINIT;

	if (BADADDR == DefAddr) { // DEF is in a Phi function
		FoundDEF = true;
	}
	else { // DEF is in an instruction
		FoundDEF = false; // need to see the DefAddr first
	}

	for (InstIter = DefBlock->GetFirstInst(); InstIter != DefBlock->GetLastInst(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		if ((!FoundDEF) && (DefAddr == CurrInst->GetAddr())) {
			FoundDEF = true;
		}
		else if (FoundDEF) {
			CurrDef = CurrInst->FindDef(DefOp);
			if (CurrDef != CurrInst->GetLastDef()) {
				// Found re-DEF of DefOp.
				DefEscapes = false;
			}
		}
		// NOTE: Following instructions should be inside if (FoundDEF) condition.
		CurrUse = CurrInst->FindUse(DefOp);
		if (CurrUse != CurrInst->GetLastUse()) { // found a USE of DefOp
			if (CurrUse->GetSSANum() == SSANum) { // matched SSA number
				UseType = CurrUse->GetType();
				FoundNumeric |= (IsNumeric(UseType));
				FoundUnknown |= (IsUnknown(UseType));
				FoundUninit |= (IsEqType(UNINIT, UseType));
				if (IsDataPtr(UseType)) {
					if (FoundPointer) {
						if (IsNotEqType(PtrType, UseType)) {
#if SMP_DEBUG_TYPE_INFERENCE
							SMP_msg("WARNING: Differing ptr types in global chain:");
							SMP_msg(" Prev: %d Current: %d %s\n", PtrType, UseType,
								CurrInst->GetDisasm());
#endif
							PtrType = POINTER;
						}
					}
					else {
						FoundPointer = true;
						PtrType = UseType;
					}
				}
			} // end if matched SSA #
		} // end if found a USE of DefOp
	} // end for all instructions

	if (DefEscapes) { // did not find re-def
		DefEscapes = DefBlock->IsLiveOut(DefOp);
	}


	if (DefEscapes) { // Need to recurse into successor blocks
		list<SMPBasicBlock *>::iterator SuccIter;
		ea_t TempAddr;
		this->ResetProcessedBlocks(); // set up recursion
		for (SuccIter = DefBlock->GetFirstSucc(); SuccIter != DefBlock->GetLastSucc(); ++SuccIter) {
			SMPBasicBlock *CurrBlock = (*SuccIter);
			set<SMPPhiFunction, LessPhi>::iterator PhiIter = CurrBlock->FindPhi(DefOp);
			TempAddr = DefAddr;
			if (PhiIter != CurrBlock->GetLastPhi()) {
				TempAddr = BADADDR;  // signals that DefOp will get re-DEFed in a Phi function.
			}
			else if (BADADDR == TempAddr) { // was BADADDR coming in to this function
				// We don't want to pass BADADDR down the recursion chain, because it will be interpreted
				//  by each successor block to mean that DefOp was a Phi USE that got re-DEFed in a Phi function
				//  within itself. Pass the dummy address that indicates LiveIn to the block.
				TempAddr = CurrBlock->GetFirstAddr() - 1;
			}
			// Should we screen the recursive call below using CurrBlock->IsLiveIn(DefOp) for speed?  !!!!****!!!!
			CurrBlock->InferGlobalDefType(DefOp, SSANum, TempAddr, FoundNumeric, FoundPointer, FoundUnknown, FoundUninit, PtrType);
		}
	}

	// Do we have a consistent type?
	// If we see any definite POINTER uses, we must set the DEF
	//  to type POINTER or a refinement of it.
	if (FoundPointer)
		UseType = PtrType;
	else if (FoundNumeric && !FoundUninit && !FoundUnknown)
		UseType = NUMERIC;
	else
		return UNINIT; // no POINTER, but no consistent type

	assert(UNINIT != UseType);
	if (DebugFlag) SMP_msg("Inferring global DEF of type %d\n", UseType);

	return UseType;
} // end of SMPFunction::InferGlobalDefType()

// Mark NUMERIC (and propagate) any DEF that starts at small immed. value and gets only small inc/dec operations.
void SMPFunction::FindCounterVariables(void) {
	// We define a counter variable as one that starts out as a small immediate value and then is only updated
	//  via small additions and subtractions. This cannot produce a POINTER, so it must be NUMERIC. This routine
	//  helps get the NUMERIC inference past the phi function barrier, e.g.:
	//
	//  mov eax,0    ; might be NULL POINTER or might be NUMERIC
	//  eax2 := phi(eax1, eax0)  ; still don't know type
	//  label1:    ; top of loop
	//   :
	//  add eax,4  ; increment induction variable; eax1 := eax0 + 4
	//  cmp eax,looplimit
	//  jl label1
	//
	//  Viewed in isolation, adding 4 to EAX could be a pointer operation or a numeric operation, and
	//   the same is true for initializing to zero. Viewed together, these statements obviously cannot be
	//   producing a POINTER value, as 0,4,8, etc. are not a sequence of POINTER values.

	list<SMPInstr *>::iterator InstIter;
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		bool ValueFound;
		uval_t ConstValue;
		if (CurrInst->MDIsSimpleAssignment(ValueFound, ConstValue)) {
			if (ValueFound && (0 == ConstValue)) {
				// Start small: Find init to zero, then track it. Init to small values after we test.
				set<DefOrUse, LessDefUse>::iterator DefIter = CurrInst->GetFirstNonFlagsDef();
				if (DefIter == CurrInst->GetLastDef()) {
					// Must have been a simple assignment to a flag, e.g. clc (clear the carry flag).
					continue;
				}
				op_t DefOp = DefIter->GetOp();
				if (o_reg == DefOp.type) {
					list<pair<int, ea_t> > CounterSSANums;  // SSA numbers that are definitely counters for DefOp
					int DefSSANum = DefIter->GetSSANum();
					ea_t DefAddr = CurrInst->GetAddr();
					pair<int, ea_t> ListItem(DefSSANum, DefAddr);
					CounterSSANums.push_back(ListItem);
					SMPBasicBlock *CurrBlock = CurrInst->GetBlock();
					int BlockNum = CurrBlock->GetNumber();
					bool LocalName = CurrBlock->IsLocalName(DefOp);
					if (this->CounterVarHelper(DefOp, DefSSANum, BlockNum, LocalName, CounterSSANums)) {
						while (!CounterSSANums.empty()) {
							int CurrSSANum = CounterSSANums.front().first;
							ea_t CurrDefAddr = CounterSSANums.front().second;
							bool Propagated;
							if (LocalName) {
								Propagated = CurrBlock->PropagateLocalDefType(DefOp, NUMERIC, CurrDefAddr, CurrSSANum, false);
							}
							else {
								this->ResetProcessedBlocks();
								Propagated = CurrBlock->PropagateGlobalDefType(DefOp, NUMERIC, CurrSSANum, false);
							}
							CounterSSANums.pop_front();
						}
					}
				} // end if o_reg type
			} // end if const value of 0
		} // end if simple assignment
	} // end for all instructions

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

// recursive helper for FindCounterVariables()
// Return true if we added to the DefSSANums list.
bool SMPFunction::CounterVarHelper(op_t DefOp, int DefSSANum, int BlockNum, bool LocalName, list<pair<int, ea_t> > CounterSSANums) {
	bool ListExpanded = false;
	size_t IncomingListSize = CounterSSANums.size();
	set<int> NonEscapingRegisterHashes;

	// First, examine the Phi list to find uses of DefOp/DefSSANum.
	// Next, examine instructions to find uses of DefOp/DefSSANum. They must be counter operations if DefOp is re-defed.

	// As a first cut, we will just find the following pattern:
	// 1. Counter-style DEF reaches the end of the current block.
	// 2. Successor block is a single-block loop with counter DEF appearing as a USE in a phi function.
	// 3. Within the single-block loop, Phi DEF is used in a counter-style operation, with new DEF becoming a Phi USE at top of block.
	// We will expand this to loops that are not in a single block later.
	SMPBasicBlock *CurrBlock = this->GetBlockByNum((size_t) BlockNum);
	assert(NULL != CurrBlock);
	ea_t DefAddr = CounterSSANums.front().second;
	if (CurrBlock->DoesDefReachBlockEnd(DefAddr, DefOp, DefSSANum, NonEscapingRegisterHashes)) {
		NonEscapingRegisterHashes.clear(); // Not memoizing for this use of DoesDefReachBlockEnd()
		bool LoopSuccFound = false;
		list<SMPBasicBlock *>::iterator SuccIter;
		SMPBasicBlock *SuccBlock;
		set<SMPPhiFunction, LessPhi>::iterator PhiIter;
		for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
			SuccBlock = (*SuccIter);
			if (SuccBlock->IsSelfLoop()) {
				PhiIter = SuccBlock->FindPhi(DefOp);
				if (PhiIter != SuccBlock->GetLastPhi()) { // Found a Phi function that could match
					size_t PhiSize = PhiIter->GetPhiListSize();
					for (size_t index = 0; index < PhiSize; ++index) {
						int PhiUseSSANum = PhiIter->GetUseSSANum(index);
						if (PhiUseSSANum == DefSSANum) {
							// Our DEF is a USE in the phi function at the top of SuccBlock. Success.
							int PhiDefSSANum = PhiIter->GetDefSSANum();
							LoopSuccFound = true;
							break;
						}
					}
				}
				if (LoopSuccFound) {
					break;
				}
			}
		}
		if (LoopSuccFound) {
			// SuccBlock points to a one-block loop with PhiIter pointing to a phi function that has
			//  DefOp/DefSSANum as a phi use, and DefOp/PhiDefSSANum as its phi def. Are the uses of
			//  DefOp/PhiDefSSANum within SuccBlock merely counter redefinitions?
			vector<SMPInstr *>::iterator InstIter;
			for (InstIter = SuccBlock->GetFirstInst(); InstIter != SuccBlock->GetLastInst(); ++InstIter) {
				set<DefOrUse, LessDefUse>::iterator DefIter, UseIter;
				SMPInstr *CurrInst = (*InstIter);
				DefIter = CurrInst->FindDef(DefOp);
				if (DefIter != CurrInst->GetLastDef()) {
					// Found a redefinition of DefOp. Is it just a counter operation that redefines DefOp?
					if (CurrInst->IsCounterOperation()) {
						// We will add the new DEF SSA # to the list of counter SSAs.
						pair<int, ea_t> CounterPair(DefIter->GetSSANum(), CurrInst->GetAddr());
						CounterSSANums.push_back(CounterPair);
						// We don't need to push the PhiDefSSANum discovered earlier, because if
						//  it follows the simple pattern of only using two counter DEFs as its USEs,
						//  one from before the loop and one from within the loop, then both of its USEs
						//  will get set to NUMERIC and propagation will occur naturally. If it does not
						//  fit this simple pattern, we don't want to force it to be NUMERIC yet.
					}
					else {
						// Problem: we redefined DefOp with a non-counter operation. We want to terminate
						//  the chain of detection of counter variables.
						break;
					}
				}
				else {
					UseIter = CurrInst->FindUse(DefOp);
					if (UseIter != CurrInst->GetLastUse()) {
						// Found USE of DefOp. See if it is a POINTER use, which would
						//  invalidate the hypothesis that DefOp is a counter.
						SMPOperandType UseType = UseIter->GetType();
						if (IsDataPtr(UseType) || IsEqType(UseType, CODEPTR)) {
							// Any apparent counter operations so far have really been pointer arithmetic.
							//  We need to restore the list to its incoming state.
							while (IncomingListSize < CounterSSANums.size()) {
								CounterSSANums.pop_back();
							}
							break; // terminate search
						}
					}
				}
			} // end for all insts in SuccBlock
		} // end if LoopSuccFound
	} // end if original pre-loop DEF reaches the end of its block

	ListExpanded = (CounterSSANums.size() > IncomingListSize);
	return ListExpanded;
} // end of SMPFunction::CounterVarHelper()

#define SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION 1
#if SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION
// The simple form of conditional type propagation observes that we
//  simply need to apply the meet operator over Phi function USEs and
//  then propagate any DEF type changes using PropagateGlobalDefType().
//  The outermost iteration over all type inference methods in InferTypes()
//  will take care of all the propagation that is handled by the work list
//  processing in the textbook algorithm.
// Iteration convergence might be slower in the simple approach, but the code
//  is much simpler to debug.
bool SMPFunction::ConditionalTypePropagation(void) {
	bool changed = false;
	SMPBasicBlock *CurrBlock;
	vector<SMPBasicBlock *>::iterator CurrRPO;
	set<SMPPhiFunction, LessPhi>::iterator CurrPhi;

	for (CurrRPO = this->RPOBlocks.begin(); CurrRPO != this->RPOBlocks.end(); ++CurrRPO) {
		CurrBlock = *CurrRPO;
		SMPOperandType MeetType;
		CurrPhi = CurrBlock->GetFirstPhi();
		while (CurrPhi != CurrBlock->GetLastPhi()) {
			op_t DefOp = CurrPhi->GetAnyOp();
			bool IsMemOp = (o_reg != DefOp.type);
			MeetType = CurrPhi->ConditionalMeetType(CurrBlock);
			CurrPhi = CurrBlock->FindPhi(DefOp); // maybe stale, so re-find; could be changed by propagation in ConditionalMeetType()

			// Here we use a straight equality test, not our macros,
			//  because we consider it a change if the MeetType is
			//  profiler derived and the DEFType is not.
			if (MeetType != CurrPhi->GetDefType()) {
				// Change the DEF type to the MeetType and propagate.
				CurrPhi = CurrBlock->SetPhiDefType(DefOp, MeetType);
				changed = true;
				this->ResetProcessedBlocks();
				changed |= CurrBlock->PropagateGlobalDefType(DefOp,
					MeetType, CurrPhi->GetDefSSANum(), IsMemOp);
			}
			++CurrPhi;
		} // end for all phi functions in the current block
	} // end for all blocks

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

#else  // not SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION

// Apply the SCC (Sparse Conditional Constant) propagation algorithm to
//  propagate types starting from unresolved Phi DEFs.
bool SMPFunction::ConditionalTypePropagation(void) {
	bool changed = false;

	// Collections of Phi functions and instructions that have a DEF
	//  with type UNINIT for the current global name.
	map<int, set<SMPPhiFunction, LessPhi>::iterator> UninitDEFPhis;
	vector<list<SMPInstr>::iterator> UninitDEFInsts;

	// Work lists of Phi functions and instructions that need to be processed
	//  according to the SCC algorithm.
	list<map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator> PhiWorkList;
	list<vector<list<SMPInstr>::iterator>::iterator> InstWorkList;

	// Iterate through all global names that are either (1) registers
	//  or (2) stack locations in SAFE functions.
	set<op_t, LessOp>::iterator CurrGlob;
	for (CurrGlob = this->GetFirstGlobalName(); CurrGlob != this->GetLastGlobalName(); ++CurrGlob) {
		op_t GlobalOp = *CurrGlob;
		list<SMPBasicBlock>::iterator CurrBlock;
		vector<list<SMPBasicBlock>::iterator>::iterator CurrRPO;
		if (MDIsIndirectMemoryOpnd(GlobalOp, this->UseFP))
			continue; // need alias analysis to process indirect accesses
		if ((GlobalOp.type != o_reg)
			&& (!((this->GetReturnAddressStatus() == FUNC_SAFE) && MDIsStackAccessOpnd(GlobalOp, this->UseFP))))
			continue; // not register, not safe stack access

		// Set up a map (indexed by SSANum) of iterators to Phi functions
		//  for the current global name that have UNINIT as the Phi DEF type.
		UninitDEFPhis.clear();
		UninitDEFInsts.clear();
		for (CurrRPO = this->RPOBlocks.begin(); CurrRPO != this->RPOBlocks.end(); ++CurrRPO) {
			CurrBlock = *CurrRPO;
			set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
			CurrPhi = CurrBlock->FindPhi(GlobalOp);
			if (CurrPhi != CurrBlock->GetLastPhi()) {
				// Found Phi function for current global name.
				if (IsEqType(CurrPhi->GetDefType(), UNINIT)) {
					// Phi DEF is UNINIT; add Phi to the map.
					pair<int, set<SMPPhiFunction, LessPhi>::iterator> TempPair(CurrPhi->GetDefSSANum(), CurrPhi);
					bool Inserted = false;
					map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator WhereIns;
					pair<map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator, bool> Result(WhereIns, Inserted);
					Result = UninitDEFPhis.insert(TempPair);
					assert(Result.second == true);
				}
			}
		} // end for all blocks

		// If any Phi DEF had UNINIT as its type, set up a vector of
		//  iterators to instructions that have UNINIT as the DEF type
		//  for the current global name.
		if (UninitDEFPhis.empty())
			continue;
		list<SMPInstr *>::iterator InstIter;
		for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
			SMPInstr *CurrInst = (*InstIter);
			set<DefOrUse, LessDefUse>::iterator CurrDef = CurrInst->FindDef(GlobalOp);
			if (CurrDef != CurrInst->GetLastDef()) {
				// Found DEF of current global name.
				if (IsEqType(UNINIT, CurrDef->GetType())) {
					UninitDEFInsts.push_back(CurrInst);
				}
			}
		} // end for all instructions

		// Put all UNINIT Phi DEFs that have at least one USE
		//  that is not UNINIT onto the PhiWorkList.
		map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator CurrUnPhi;
		for (CurrUnPhi = UninitDEFPhis.begin(); CurrUnPhi != UninitDEFPhis.end(); ++CurrUnPhi) {
			pair<int, set<SMPPhiFunction, LessPhi>::iterator> PhiDefPair(*CurrUnPhi);
			if (PhiDefPair.second->HasTypedUses()) {
				PhiWorkList.push_back(CurrUnPhi);
			}
		}

		// Iterate until both work lists are empty:
		while (!(PhiWorkList.empty() && InstWorkList.empty())) {
			// Process Phi items first.
			while (!PhiWorkList.empty()) {
				// If applying the meet operator over the Phi USE types
				//  would produce a new DEF type, change the DEF type and
				//  propagate it, adding Phi functions and instructions that
				//  received the propagated type to their respective work lists.
				map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator MapIter;
				MapIter = PhiWorkList.front();
				PhiWorkList.pop_front();  // remove from work list
				pair<int, set<SMPPhiFunction, LessPhi>::iterator> PhiDefPair;
				PhiDefPair.first = MapIter->first;
				PhiDefPair.second = MapIter->second;
				set<SMPPhiFunction, LessPhi>::iterator CurrPhi = PhiDefPair.second;
				SMPOperandType MeetType = CurrPhi->ConditionalMeetType();
				// Here we use a straight equality test, not our macros,
				//  because we consider it a change if the MeetType is
				//  profiler derived and the DEFType is not.
				if (MeetType == CurrPhi->GetDefType())
					continue;
				// At this point, we need to set the DEFType to the MeetType
				//  and propagate the change. We have a map of all the
				//  critical Phi functions for this global name, as well
				//  as a vector of the relevant instructions for this name.
				CurrPhi->SetDefType(MeetType);
				changed = true;
				int DefSSANum = CurrPhi->GetDefSSANum();
				map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator PhiIter;
				vector<list<SMPInstr>::iterator>::iterator InstIter;
				// Propagate to Phi functions first.
				for (PhiIter = UninitDEFPhis.begin(); PhiIter != UninitDEFPhis.end(); ++PhiIter) {
					if (DefSSANum == PhiIter->first)
						continue;  // Skip the Phi that we just changed
					for (size_t index = 0; index < PhiIter->second->GetPhiListSize(); ++index) {
						if (DefSSANum == PhiIter->second->GetUseSSANum(index)) {
							// Matched SSA # to USE. Propagate new type.
							PhiIter->second->SetRefType(index, MeetType);
							// Add this phi function to the work list.
							PhiWorkList.push_back(PhiIter);
						}
					}
				}
#define SMP_COND_TYPE_PROP_TO_INSTS 0
#if SMP_COND_TYPE_PROP_TO_INSTS
				// Propagate to instructions with uninit DEFs of global name.
				//  The idea is that the instructions that hold up type propagation
				//  are the ones that USE and then DEF the same global name.
				//  For example, "increment EAX" has to know the type of
				//  the USE of EAX in order to set the type of the DEF.
#endif
			} // end while the PhiWorkList is not empty
#if SMP_COND_TYPE_PROP_TO_INSTS
			// The PhiWorkList is empty at this point, so process
			//  instructions on the InstWorkList.
#endif
		} // end while both work lists are not empty

	} // end for all global names
	return changed;
} // end of SMPFunction::ConditionalTypePropagation()
#endif  // end if SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION else ...

// Propagate signedness FG info from DEFs to USEs whenever there is no USE sign info.
bool SMPFunction::PropagateSignedness(void) {
	bool changed = false;
#if STARS_AGGRESSIVE_SIGNEDNESS_PROPAGATION
	map<int, struct FineGrainedInfo>::iterator UseFGIter, DefFGIter;
	list<SMPBasicBlock *>::iterator BlockIter;
	for (UseFGIter = this->GlobalUseFGInfoBySSA.begin(); UseFGIter != this->GlobalUseFGInfoBySSA.end(); ++UseFGIter) {
		struct FineGrainedInfo UseFG = UseFGIter->second;
		if (0 == (UseFG.SignMiscInfo & FG_MASK_SIGNEDNESS_BITS)) {
			// No signedness info. Propagate any signedness info from DEF.
			int UseHashValue = UseFGIter->first;
			unsigned short DefSignMask = this->GetDefSignMiscInfo(UseHashValue);
			DefSignMask &= FG_MASK_SIGNEDNESS_BITS;
			if (0 != DefSignMask) {
				// DEF has signedness info.
				UseFGIter->second.SignMiscInfo |= DefSignMask;
				changed = true;
			}
		}
	}
	// See if we have DEF signedness info for DEFs with no corresponding USE map entries.
	for (DefFGIter = this->GlobalDefFGInfoBySSA.begin(); DefFGIter != this->GlobalDefFGInfoBySSA.end(); ++DefFGIter) {
		struct FineGrainedInfo DefFG = DefFGIter->second;
		unsigned short DefSignMask = (DefFG.SignMiscInfo & FG_MASK_SIGNEDNESS_BITS);
		if (0 != DefSignMask) {
			// Has signedness info. See if USE has no entry.
			int DefHashValue = DefFGIter->first;
			UseFGIter = this->GlobalUseFGInfoBySSA.find(DefHashValue);
			if (UseFGIter == this->GlobalUseFGInfoBySSA.end()) {
				this->UpdateUseSignMiscInfo(DefHashValue, DefSignMask);
				changed = true;
			}
		}
	}
	// Do the same processsing for block-local registers.
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		bool NewChange = (*BlockIter)->PropagateDEFSignedness();
		changed = changed || NewChange;
	}
#endif
	return changed;
} // end of SMPFunction::PropagateSignedness()

// Detect and mark special cases before emitting numeric error annotations.
void SMPFunction::MarkSpecialNumericErrorCases(void) {
	list<SMPBasicBlock *>::iterator BlockIter;
	vector<SMPInstr *>::reverse_iterator InstIter;
	SMPBasicBlock *CurrBlock;
	SMPInstr *CurrInst;
	bool DebugFlag = (0 == strcmp("sub_8063BE0", this->GetFuncName()));

	set<int> NonEscapingRegisterHashes; // memoization optimization: set of register/SSA# hashes that do not reach end of block

#if STARS_BUILD_LOOP_BITSET
	// Now that we know how many loops we have, we can allocate the loops data structure.
	this->FuncLoopsByBlock.resize(this->BlockCount);
	for (size_t BlockIndex = 0; BlockIndex < this->BlockCount; ++BlockIndex) {
		this->FuncLoopsByBlock.at(BlockIndex).AllocateBits(this->LoopCount);
	}

	if (this->LoopCount > 0) {
		this->DetectLoops();
	}
#endif

	// Special-case preparatory analyses.
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		CurrBlock->AnalyzePrepForNumericAnnotations();
	}

	if (this->LoopCount == 0) {
		return;
	}

	// Loop through blocks and detect tight loops of hashing arithmetic.
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		int BlockNum = CurrBlock->GetNumber();
#if 0
		if (CurrBlock->IsLoopTailBlock() && CurrBlock->IsLoopHeaderBlock()) {
#else
		if (this->IsBlockInAnyLoop(BlockNum)) {
#endif
			// We have a one-block loop to itself. This is the simple case we want
			//  to start with, as hash functions we have observed are tight loops of arithmetic computations.
			//  The next question is whether we can find the kind of shift/rotate that is common to hashing, plus
			//  at least one addition.
			bool ShiftFound = false;
			bool AddFound = false;
			op_t DefOp = InitOp, AddDefOp = InitOp;
			set<DefOrUse, LessDefUse>::iterator DefIter;
			NonEscapingRegisterHashes.clear();

			for (InstIter = CurrBlock->GetRevInstBegin(); InstIter != CurrBlock->GetRevInstEnd(); ++InstIter) {
				CurrInst = (*InstIter);
				if ((!ShiftFound) && CurrInst->MDIsHashingArithmetic()) {
					// If the operand being shifted is never used in any assignment or arithmetic
					//  except as an address register computation within a memory operand, then the
					//  shifted value does not reach the top of the loop and get shifts accumulated.
					//  In that case, we are not dealing with a shift-and-add type of hash function.
					//  So, do not claim success unless the later addition DEF reaches the end
					//  of the block.
					DefIter = CurrInst->GetFirstNonFlagsDef();
					ea_t DefAddr = CurrInst->GetAddr();
					DefOp = DefIter->GetOp();
					ea_t AdditionAddr = BADADDR;
					ShiftFound = CurrBlock->IsDefInvolvedInAddition(DefAddr, DefOp, AdditionAddr);
					if (ShiftFound) {
						SMPInstr *AdditionInst = this->GetInstFromAddr(AdditionAddr);
						DefIter = AdditionInst->GetFirstNonFlagsDef();
						AddDefOp = DefIter->GetOp();
						AddFound = CurrBlock->DoesDefReachBlockEnd(AdditionAddr, AddDefOp, DefIter->GetSSANum(), NonEscapingRegisterHashes);
						if (AddFound) {
							break;
						}
						else {
							// Reset ShiftFound and look for a different shift.
							ShiftFound = false;
						}
					}
				}
			}
			if (ShiftFound && AddFound) {
				// We found a tight hashing loop. Mark all the overflowing and underflowing opcodes as benign.
				//  NOTE: We could do loop-variant analysis to ensure that the shifted and added values are actually
				//  changing within the loop, but if they are not, they are probably not exploitable overflows anyway,
				//  and the loop-invariant overflow would happen on every loop iteration based on initial values, which
				//  is a pattern we have never seen for this kind of code.
				vector<SMPInstr *>::iterator ForwardInstIter;
				for (ForwardInstIter = CurrBlock->GetFirstInst(); ForwardInstIter != CurrBlock->GetLastInst(); ++ForwardInstIter) {
					CurrInst = (*ForwardInstIter);
					if (CurrInst->MDIsOverflowingOpcode() || CurrInst->MDIsUnderflowingOpcode() || CurrInst->MDIsLoadEffectiveAddressInstr()) {
						CurrInst->SetHashOperation();
					}
				}
			}
		} // end if loop header and loop tail
	} // end for all blocks

	NonEscapingRegisterHashes.clear();
	return;
} // end of SMPFunction::MarkSpecialNumericErrorCases()

// Emit all annotations for the function, including all per-instruction
//  annotations.
void SMPFunction::EmitAnnotations(FILE *AnnotFile, FILE *InfoAnnotFile) {
	// Emit annotation for the function as a whole.
	list<SMPBasicBlock *>::iterator BlockIter;
	SMPBasicBlock *CurrBlock;
	bool FuncHasProblems = ((!this->AnalyzedSP) || (!this->HasGoodRTLs()) || (this->HasUnresolvedIndirectCalls())
		|| (this->HasUnresolvedIndirectJumps()) || (this->HasSharedChunks()));

	if (this->StaticFunc) {
		SMP_fprintf(AnnotFile,	"%10lx %6zu FUNC LOCAL  %s ", (unsigned long) this->FuncInfo.startEA,
			this->Size, this->GetFuncName());
	}
	else {
		SMP_fprintf(AnnotFile,	"%10lx %6zu FUNC GLOBAL %s ", (unsigned long) this->FuncInfo.startEA,
			this->Size, this->GetFuncName());
	}
	switch (this->GetReturnAddressStatus())
	{
		case FUNC_UNKNOWN:
		{
			SMP_fprintf(AnnotFile, "FUNC_UNKNOWN ");
			break;
		}
		case FUNC_SAFE:
		{
			SMP_fprintf(AnnotFile, "FUNC_SAFE ");
			break;
		}
		case FUNC_UNSAFE:
		{
			SMP_fprintf(AnnotFile, "FUNC_UNSAFE ");
			break;
		}
		default:
			assert(0);	
	}
	if (this->UseFP) {
		SMP_fprintf(AnnotFile, "USEFP ");
	}
	else {
		SMP_fprintf(AnnotFile, "NOFP ");
	}
	if (this->FuncInfo.does_return()) {
		SMP_fprintf(AnnotFile, "RET ");
	}
	else {
		SMP_fprintf(AnnotFile, "NORET ");
	}

	if (this->IsLeaf())
		SMP_fprintf(AnnotFile, "FUNC_LEAF ");
	// Store the first return instruction's address
	SMP_fprintf(AnnotFile,"%10lx ", (unsigned long) (this->FuncInfo.endEA - 1));

	if (this->IsLibFunc())
		SMP_fprintf(AnnotFile, "LIBRARY ");
	SMP_fprintf(AnnotFile, "\n");

	// Emit annotations about how to restore register values
	SMP_fprintf(AnnotFile, "%10lx %6d FUNC FRAMERESTORE ", (unsigned long) this->FuncInfo.startEA, 0);
	for(int i = R_ax; i <= R_di; i++)
	{
		SMP_fprintf(AnnotFile, "%d %d %d ", i, this->SavedRegLoc[i], this->ReturnRegTypes[i]);
	}
	SMP_fprintf(AnnotFile, "ZZ\n");

	SMP_fprintf(AnnotFile, "%10lx %6d FUNC MMSAFENESS ", (unsigned long) this->FuncInfo.startEA, 0);
	if (!IsSpecSafe())
		SMP_fprintf(AnnotFile, "UNSAFE\n");
	else if (!IsSafe())
		SMP_fprintf(AnnotFile, "SPECSAFE\n");
	else {
		assert(IsSafe());
		SMP_fprintf(AnnotFile, "SAFE\n");
	}

	// If function has problems that limited our analyses, emit an information annotation so that
	//  other tools can be aware of which analyses will be sound.
	if (FuncHasProblems) {
		SMP_fprintf(InfoAnnotFile,	"%10lx %6zu FUNC PROBLEM %s ", (unsigned long) this->FuncInfo.startEA,
			this->Size, this->GetFuncName());
		if (!this->AnalyzedSP) {
			SMP_fprintf(InfoAnnotFile, "STACKANALYSIS ");
		}
		if (this->HasSharedChunks()) {
			SMP_fprintf(InfoAnnotFile, "CHUNKS ");
		}
		if (this->HasUnresolvedIndirectJumps()) {
			SMP_fprintf(InfoAnnotFile, "JUMPUNRESOLVED ");
		}
		if (this->HasUnresolvedIndirectCalls()) {
			SMP_fprintf(InfoAnnotFile, "CALLUNRESOLVED ");
		}
		if (!this->HasGoodRTLs()) {
			SMP_fprintf(InfoAnnotFile, "BADRTLS ");
		}
		SMP_fprintf(InfoAnnotFile, "\n");
	}

	// Find and mark special cases that will affect the integer error annotations.
	this->MarkSpecialNumericErrorCases();

	// 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<size_t> LoopList; // for current block
	int CurrBlockNum = SMP_BLOCKNUM_UNINIT;
	list<SMPInstr *>::iterator InstIter = Instrs.begin();
#if SMP_USE_SSA_FNOP_MARKER
	++InstIter;  // skip marker instruction
#endif
	bool AllocSeen = false; // Reached LocalVarsAllocInstr yet?
	bool DeallocTrigger = false;
	for ( ; InstIter != Instrs.end(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		ea_t addr = CurrInst->GetAddr();
		CurrBlock = CurrInst->GetBlock();
		int BlockNum = CurrBlock->GetNumber();
		if (BlockNum != CurrBlockNum) {
			CurrBlockNum = BlockNum;
			if (0 < this->LoopCount) {
				LoopList.clear();
				this->BuildLoopList(BlockNum, LoopList);
			}
		}

		SMP_fprintf(AnnotFile, "%10lx %6zu INSTR BELONGTO %lx \n",
			(unsigned long) addr, CurrInst->GetSize(), (unsigned long) GetStartAddr());
		SMPitype CurrDataFlow = CurrInst->GetDataFlowType();
		if ((CurrDataFlow == INDIR_JUMP) || (CurrDataFlow == INDIR_CALL)) {
			SMP_xref_t xrefs;
			for (bool ok = xrefs.SMP_first_from(addr, XREF_ALL); ok; ok = xrefs.SMP_next_from()) {
				if (xrefs.GetTo() != 0) {
					if (xrefs.GetIscode() && (xrefs.GetType() != fl_F)) {
						// Found a code target, with its address in xrefs.to
						PrintCodeToCodeXref(addr, xrefs.GetTo(), CurrInst->GetSize());
					}
				}
			}
		}

		if (this->LocalVarsAllocInstr == addr) {
			AllocSeen = true;
			if (this->NeedsStackReferent)
				this->EmitStackFrameAnnotations(AnnotFile, CurrInst);
			else {
				int OptType = CurrInst->GetOptType(); 
				if (5 == OptType) { // ADD or SUB
					// Prevent mmStrata from extending the caller's stack frame
					//  to include the new allocation.
					SMP_fprintf(AnnotFile, "%10lx %6d INSTR LOCAL SafeFrameAlloc %s \n",
						(unsigned long) addr, -1, CurrInst->GetDisasm());
				}
				else if (CurrInst->MDIsPushInstr()) {
					SMP_fprintf(AnnotFile, "%10lx %6d INSTR LOCAL NoWarn %s \n",
						(unsigned long) addr, -3, CurrInst->GetDisasm());
				}
				// mmStrata ignores the DATAREF annotations anyway, so even though
				//  they are not needed, emit them for use by Strata and other tools
				//  in other projects besides MEDS.
				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.