SMPFunction.cpp

// Perform live variable analysis on all blocks in the function.
// See chapter 9 of Cooper/Torczon, Engineering a Compiler, for the algorithm.
void SMPFunction::LiveVariableAnalysis(void) {
	list<SMPBasicBlock>::iterator CurrBlock;
#if SMP_DEBUG_DATAFLOW
	msg("LiveVariableAnalysis for %s\n", this->GetFuncName());
	bool DebugFlag = (0 == strcmp("__ieee754_pow", this->GetFuncName()));
#endif

	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		// Initialize the Killed and UpwardExposed sets for each block.
		CurrBlock->InitKilledExposed();
	}

	bool changed;
	// Iterate over each block, updating LiveOut sets until no more changes are made.
	// NOTE: LVA is more efficient when computed over a reverse post-order list of blocks
	//  from the inverted CFG. We have an RPO list from the forward CFG, so it is just as
	//  good to simply iterate through the blocks in layout order.
#if 1
	do {
		changed = false;
		for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
			changed |= CurrBlock->UpdateLiveOut();
		}
	} while (changed);
#else // Use reverse postorder
	do {
		changed = false;
		for (size_t index = 0; index < this->RPOBlocks.size(); ++index) {
			CurrBlock = this->RPOBlocks[index];
			changed |= CurrBlock->UpdateLiveOut();
		}
	} while (changed);
#endif

#if SMP_USE_SSA_FNOP_MARKER
	// Create DEFs in the marker instruction for all names in the LiveInSet
	//  of the first block. These are the names for the function that
	//  would otherwise look like USEs of uninitialized variables later.
	// Note that the LiveVariableAnalysis work does not actually populate
	//  a LiveInSet for the first block, so we simulate it with its
	//  dataflow equation, UpExposed union (LiveOut minus VarKill).
	set<op_t, LessOp>::iterator UpExposedIter, LiveOutIter;
	list<SMPInstr>::iterator MarkerInst = this->Instrs.begin();
	for (UpExposedIter = this->Blocks.begin()->GetFirstUpExposed();
		UpExposedIter != this->Blocks.begin()->GetLastUpExposed();
		++UpExposedIter) {
			// Add DEF with SSANum of 0.
			MarkerInst->AddDef(*UpExposedIter, UNINIT, 0);
			// Add to the VarKill set.
			this->Blocks.begin()->AddVarKill(*UpExposedIter);
	}
	for (LiveOutIter = this->Blocks.begin()->GetFirstLiveOut();
		LiveOutIter != this->Blocks.begin()->GetLastLiveOut();
		++LiveOutIter) {
			if (!(this->Blocks.begin()->IsVarKill(*LiveOutIter))) {
				// Add DEF with SSANum of 0.
				MarkerInst->AddDef(*LiveOutIter, UNINIT, 0);
				// Add to the VarKill set.
				this->Blocks.begin()->AddVarKill(*LiveOutIter);
			}
	}
#endif

#if SMP_DEBUG_DATAFLOW
	if (DebugFlag) msg("Exiting LiveVariableAnalysis\n");
#endif
	return;
} // end of SMPFunction::LiveVariableAnalysis()

// Return the IDom index that is the end of the intersection prefix of the Dom sets of
//  the two blocks designated by the RPO numbers passed in.
// See Cooper & Torczon, "Engineering a Compiler" 1st edition figure 9.8.
int SMPFunction::IntersectDoms(int block1, int block2) const {
	int finger1 = block1;
	int finger2 = block2;
	while (finger1 != finger2) {
		while (finger1 > finger2)
			finger1 = this->IDom.at(finger1);
		while (finger2 > finger1)
			finger2 = this->IDom.at(finger2);
	}
	return finger1;
} // end of SMPFunction::IntersectDoms()

// Compute immediate dominators of all blocks into IDom[] vector.
void SMPFunction::ComputeIDoms(void) {
	bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
	DebugFlag = (0 == strcmp("__ieee754_pow", this->GetFuncName()));
	if (DebugFlag) msg("Entered ComputeIDoms\n");
#endif
	// Initialize the IDom[] vector to uninitialized values for all blocks.
	this->IDom.reserve(this->BlockCount);
	this->IDom.assign(this->BlockCount, SMP_BLOCKNUM_UNINIT);
	if (DebugFlag) msg("BlockCount = %d\n", this->BlockCount);
	this->IDom[0] = 0; // Start block dominated only by itself
	bool changed;
	do {
		changed = false;
		for (size_t RPONum = 1; RPONum < (size_t) this->BlockCount; ++RPONum) {
			if (DebugFlag) msg("RPONum %d\n", RPONum);
			if (DebugFlag) {
				msg("RPOBlocks vector size: %d\n", this->RPOBlocks.size());
				for (size_t index = 0; index < this->RPOBlocks.size(); ++index) {
					msg("RPOBlocks entry %d is %d\n", index, RPOBlocks[index]->GetNumber());
				}
			}
			list<SMPBasicBlock>::iterator CurrBlock = this->RPOBlocks.at(RPONum);
			// if (DebugFlag) msg("CurrBlock: %x\n", CurrBlock._Ptr);
			list<list<SMPBasicBlock>::iterator>::iterator CurrPred;
			// Initialize NewIdom to the first processed predecessor of block RPONum.
			int NewIdom = SMP_BLOCKNUM_UNINIT;
			for (CurrPred = CurrBlock->GetFirstPred(); CurrPred != CurrBlock->GetLastPred(); ++CurrPred) {
				int PredNum = (*CurrPred)->GetNumber();
				if (DebugFlag) msg("Pred: %d\n", PredNum);
				// **!!** See comment below about unreachable blocks.
				if (SMP_BLOCKNUM_UNINIT == PredNum)
					continue;
				int PredIDOM = this->IDom.at(PredNum);
				if (DebugFlag) msg("Pred IDom: %d\n", PredIDOM);
				if (SMP_BLOCKNUM_UNINIT != PredIDOM) {
					NewIdom = PredNum;
					break;
				}
			}
			if (NewIdom == SMP_BLOCKNUM_UNINIT) {
				msg("Failure on NewIdom in ComputeIDoms for %s\n", this->GetFuncName());
				if (this->HasIndirectJumps()) {
					// Might be reachable only through indirect jumps.
					NewIdom = 0; // make it dominated by entry block
				}
			}
			assert(NewIdom != SMP_BLOCKNUM_UNINIT);
			// Loop through all predecessors of block RPONum except block NewIdom.
			//  Set NewIdom to the intersection of its Dom set and the Doms set of
			//  each predecessor that has had its Doms set computed.
			for (CurrPred = CurrBlock->GetFirstPred(); CurrPred != CurrBlock->GetLastPred(); ++CurrPred) {
				int PredNum = (*CurrPred)->GetNumber();
				if (DebugFlag) msg("PredNum: %d\n", PredNum);
				// **!!** We could avoid failure on unreachable basic blocks
				//  by executing a continue statement if PredNum is -1. Long term solution
				//  is to prune out unreachable basic blocks.
				if (PredNum == SMP_BLOCKNUM_UNINIT)
					continue;
				int PredIDOM = this->IDom.at(PredNum);
				if (DebugFlag) msg("PredIDOM: %d\n", PredIDOM);
				if ((SMP_BLOCKNUM_UNINIT == PredIDOM) || (NewIdom == PredIDOM)) {
					// Skip predecessors that have uncomputed Dom sets, or are the
					//  current NewIdom.
					continue;
				}
				if (DebugFlag) msg("Old NewIdom value: %d\n", NewIdom);
				NewIdom = this->IntersectDoms(PredNum, NewIdom);
				if (DebugFlag) msg("New NewIdom value: %d\n", NewIdom);
			}
			// If NewIdom is not the value currently in vector IDom[], update the
			//  vector entry and set changed to true.
			if (NewIdom != this->IDom.at(RPONum)) {
				if (DebugFlag) msg("IDOM changed from %d to %d\n", this->IDom.at(RPONum), NewIdom);
				this->IDom[RPONum] = NewIdom;
				changed = true;
			}
		}
	} while (changed);
	return;
} // end of SMPFunction::ComputeIDoms()

// Compute dominance frontier sets for each block.
void SMPFunction::ComputeDomFrontiers(void) {
	list<SMPBasicBlock>::iterator CurrBlock;
	list<SMPBasicBlock>::iterator RunnerBlock;
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		// We look only at join points in the CFG, as per Cooper/Torczon chapter 9.
		if (1 < CurrBlock->GetNumPreds()) { // join point; more than 1 predecessor
			int runner;
			list<list<SMPBasicBlock>::iterator>::iterator CurrPred;
			for (CurrPred = CurrBlock->GetFirstPred(); CurrPred != CurrBlock->GetLastPred(); ++CurrPred) {
				// For each predecessor, we run up the IDom[] vector and add CurrBlock to the
				//  DomFrontier for all blocks that are between CurrPred and IDom[CurrBlock],
				//  not including IDom[CurrBlock] itself.
				runner = (*CurrPred)->GetNumber();
				while (runner != this->IDom.at(CurrBlock->GetNumber())) {
					// Cooper/Harvey/Kennedy paper does not quite agree with the later
					//  text by Cooper/Torczon. Text says that the start node has no IDom
					//  in the example on pages 462-463, but it shows an IDOM for the
					//  root node in Figure 9.9 of value == itself. The first edition text
					//  on p.463 seems correct, as the start node dominates every node and
					//  thus should have no dominance frontier.
					if (SMP_TOP_BLOCK == runner)
						break;
					RunnerBlock = this->RPOBlocks.at(runner);
					RunnerBlock->AddToDomFrontier(CurrBlock->GetNumber());
					runner = this->IDom.at(runner);
				}
			} // end for all predecessors
		} // end if join point
	} // end for all blocks
	return;
} // end of SMPFunction::ComputeDomFrontiers()

// Compute the GlobalNames set, which includes all operands that are used in more than
//  one basic block. It is the union of all UpExposedSets of all blocks.
void SMPFunction::ComputeGlobalNames(void) {
	set<op_t, LessOp>::iterator SetIter;
	list<SMPBasicBlock>::iterator CurrBlock;
	unsigned int index = 0;
	if (this->Blocks.size() < 2)
		return; // cannot have global names if there is only one block

	bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
	DebugFlag = (0 == strcmp("__ieee754_pow", this->GetFuncName()));
#endif

	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		for (SetIter = CurrBlock->GetFirstUpExposed(); SetIter != CurrBlock->GetLastUpExposed(); ++SetIter) {
			op_t TempOp = *SetIter;
			// The GlobalNames set will have the complete collection of operands that we are
			//  going to number in our SSA computations. We now assign an operand number
			//  within the op_t structure for each, so that we can index into the
			//  BlocksUsedIn[] vector, for example. This operand number is not to be
			//  confused with SSA numbers.
			// We use the operand number field op_t.n for the lower 8 bits, and the offset
			//  fields op_t.offb:op_t.offo for the upper 16 bits. We are overwriting IDA
			//  values here, but operands in the data flow analysis sets should never be
			//  inserted back into the program anyway.
			SetGlobalIndex(&TempOp, index);

#if SMP_DEBUG_DATAFLOW
			msg("Global Name: ");
			PrintListOperand(TempOp);
#endif
			set<op_t, LessOp>::iterator AlreadyInSet;
			pair<set<op_t, LessOp>::iterator, bool> InsertResult;
			InsertResult = this->GlobalNames.insert(TempOp);
			if (!InsertResult.second) {
				// Already in GlobalNames, so don't assign an index number.
				;
#if SMP_DEBUG_DATAFLOW
				msg(" already in GlobalNames.\n");
#endif
			}
			else {
				++index;
#if SMP_DEBUG_DATAFLOW
				msg(" inserted as index %d\n", ExtractGlobalIndex(TempOp));
#endif
			}
		} // for each upward exposed item in the current block
	} // for each basic block

	assert(16777215 >= this->GlobalNames.size()); // index fits in 24 bits
	return;
} // end of SMPFunction::ComputeGlobalNames()

// For each item in GlobalNames, record the blocks that DEF the item.
void SMPFunction::ComputeBlocksDefinedIn(void) {
	// Loop through all basic blocks and examine all DEFs. For Global DEFs, record
	//  the block number in BlocksDefinedIn. The VarKillSet records DEFs without
	//  having to examine every instruction.
	list<SMPBasicBlock>::iterator CurrBlock;
	this->BlocksDefinedIn.clear();
	for (size_t i = 0; i < this->GlobalNames.size(); ++i) {
		list<int> TempList;
		this->BlocksDefinedIn.push_back(TempList);
	}
#if SMP_DEBUG_DATAFLOW
	msg("Number of GlobalNames: %d\n", this->GlobalNames.size());
	msg("Size of BlocksDefinedIn: %d\n", this->BlocksDefinedIn.size());
#endif
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		set<op_t, LessOp>::iterator KillIter;
		for (KillIter = CurrBlock->GetFirstVarKill(); KillIter != CurrBlock->GetLastVarKill(); ++KillIter) {
			// If killed item is not a block-local item (it is global), record it.
			set<op_t, LessOp>::iterator NameIter = this->GlobalNames.find(*KillIter);
			if (NameIter != this->GlobalNames.end()) { // found in GlobalNames set
				// We have a kill of a global name. Get index from three 8-bit fields.
				unsigned int index = ExtractGlobalIndex(*NameIter);
				if (index >= this->GlobalNames.size()) {
					// We are about to assert false.
					msg("ComputeBlocksDefinedIn: Bad index: %d limit: %d\n", index,
						this->GlobalNames.size());
					msg("Block number %d\n", CurrBlock->GetNumber());
					msg("Killed item: ");
					PrintListOperand(*KillIter);
					msg("\n");
					msg("This is a fatal error.\n");
				}
				assert(index < this->GlobalNames.size());
				// index is a valid subscript for the BlocksDefinedIn vector. Push the
				//  current block number onto the list of blocks that define this global name.
				this->BlocksDefinedIn[index].push_back(CurrBlock->GetNumber());
			}			
		}
	}
	return;
} // end of SMPFunction::ComputeBlocksDefinedIn()

// Compute the phi functions at the entry point of each basic block that is a join point.
void SMPFunction::InsertPhiFunctions(void) {
	set<op_t, LessOp>::iterator NameIter;
	list<int> WorkList;  // list of block numbers
	bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
	DebugFlag = (0 == strcmp("__ieee754_pow", this->GetFuncName()));
#endif
	if (DebugFlag) msg("GlobalNames size: %d\n", this->GlobalNames.size());
	for (NameIter = this->GlobalNames.begin(); NameIter != this->GlobalNames.end(); ++NameIter) {
		int CurrNameIndex = (int) (ExtractGlobalIndex(*NameIter));
		if (DebugFlag) msg("CurrNameIndex: %d\n", CurrNameIndex);
#if 0
		DebugFlag = (DebugFlag && (6 == CurrNameIndex));
#endif
		// Initialize the work list to all blocks that define the current name.
		WorkList.clear();
		list<int>::iterator WorkIter;
		for (WorkIter = this->BlocksDefinedIn.at((size_t) CurrNameIndex).begin();
			WorkIter != this->BlocksDefinedIn.at((size_t) CurrNameIndex).end();
			++WorkIter) {
			WorkList.push_back(*WorkIter);
		}

		// Iterate through the work list, inserting phi functions for the current name
		//  into all the blocks in the dominance frontier of each work list block.
		//  Insert into the work list each block that had a phi function added.
		while (!WorkList.empty()) {
#if SMP_DEBUG_DATAFLOW
			msg("WorkList size: %d\n", WorkList.size());
#endif
			list<int>::iterator WorkIter = WorkList.begin();
			while (WorkIter != WorkList.end()) {
				set<int>::iterator DomFrontIter;
#if SMP_DEBUG_DATAFLOW
				msg("WorkIter: %d\n", *WorkIter);
#endif
				if (DebugFlag && (*WorkIter > this->BlockCount)) {
					msg("ERROR: WorkList block # %d out of range.\n", *WorkIter);
				}
				list<SMPBasicBlock>::iterator WorkBlock = this->RPOBlocks[*WorkIter];
				for (DomFrontIter = WorkBlock->GetFirstDomFrontier();
					DomFrontIter != WorkBlock->GetLastDomFrontier();
					++DomFrontIter) {
#if SMP_DEBUG_DATAFLOW
					msg("DomFront: %d\n", *DomFrontIter);
#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() && (o_reg == GlobIter->type)) {
						// 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 UnsafeFunc = (FUNC_SAFE != this->ReturnAddrStatus);
	bool DebugFlag = false;
#if SMP_DEBUG_TYPE_INFERENCE
	DebugFlag |= (0 == strcmp("weightadj", this->GetFuncName()));
#endif
	list<SMPInstr>::iterator CurrInst;
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	set<DefOrUse, LessDefUse>::iterator NextDef;
	list<SMPBasicBlock>::iterator CurrBlock;

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

	// 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 {
		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);
			}
		} while (changed);
		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;
		this->TypedPhiDefs = 0;
		this->UntypedPhiDefs = 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();
					if (MDIsIndirectMemoryOpnd(DefOp, this->UseFP)
						|| (o_mem == DefOp.type)
						|| ((o_reg != DefOp.type) && UnsafeFunc)) {
						// Don't want to infer along DEF-USE chains for indirect
						//  memory accesses until we have alias analysis.
						++CurrDef;
						continue;
					}
					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 {
						// global name
						bool CallInst = ((CALL == CurrInst->GetDataFlowType())
							|| (INDIR_CALL == CurrInst->GetDataFlowType()));
						SMPOperandType DefType = UNINIT;
						DefType = this->InferGlobalDefType(DefOp,
							CurrDef->GetSSANum(), CurrInst->GetBlock(), CallInst);
						if (IsNotEqType(UNINIT, DefType)) {
							CurrDef = CurrInst->SetDefType(DefOp, DefType);
							--(this->UntypedDefs);
							++(this->TypedDefs);
							NewChange = true;
						}
						changed = (changed || NewChange);
					}
				}
				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();
			}
		}
		if (DebugFlag) msg("Finished unconditional phi type inference.\n");

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

	} while (changed);
	return;
} // end of SMPFunction::InferTypes()

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

	list<SMPInstr>::iterator CurrInst;
	set<DefOrUse, LessDefUse>::iterator CurrDef, NextDef;
	
	bool DebugFlag = false;
#if SMP_DEBUG_TYPE_INFERENCE
	DebugFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
#endif

	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) 
	{
		InstructionInformation* ii=pi->GetInfo( CurrInst->GetAddr());
		if(ii && DebugFlag)
			msg("Found instruction information for %x\n", CurrInst->GetAddr());
		if(ii && ii->isNumeric())
		{
			msg("Found instruction information for %x and it's numeric!\n", CurrInst->GetAddr());
			CurrInst->UpdateMemLoadTypes((SMPOperandType)(NUMERIC|PROF_BASE));
		}
	}


}	// 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.
SMPOperandType SMPFunction::InferGlobalDefType(op_t DefOp, int SSANum, SMPBasicBlock *DefBlock, bool CallInst) {
	bool changed = false;
	bool DebugFlag = false;
	bool FoundNumeric = false;
	bool FoundPointer = false;
	bool FoundUnknown = false;
	bool FoundUninit = false;

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

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

	list<SMPInstr>::iterator InstIter;

	assert(0 <= SSANum);
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	// Go through all instructions in the function 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.
	bool FirstUseSeen = false;
	bool ProfDerived = false;
	SMPOperandType UseType = UNINIT;
	SMPOperandType PtrType = UNINIT;
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		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();
				FoundNumeric |= (IsNumeric(UseType));
				FoundUnknown |= (IsUnknown(UseType));
				FoundUninit |= (IsEqType(UNINIT, UseType));
				if (IsDataPtr(UseType)) {
					if (FoundPointer) {
						if (IsNotEqType(PtrType, UseType)) {
							msg("WARNING: Differing ptr types in global chain:");
							msg(" Prev: %d Current: %d %s\n", PtrType, UseType,
								InstIter->GetDisasm());
						}
						PtrType = POINTER;
					}
					else {
						FoundPointer = true;
						PtrType = UseType;
					}
				}
			} // end if matched SSA #
		} // end if found a USE of DefOp
	} // end for all instructions

	// Now, we need to check the phi functions and see if there are Phi USEs of the DefOp.
	set<SMPPhiFunction, LessPhi>::iterator UsePhi;
	size_t BlockNum;
	for (BlockNum = 0; BlockNum < (size_t) this->BlockCount; ++BlockNum) {
		UsePhi = this->RPOBlocks.at(BlockNum)->FindPhi(DefOp);
		if (UsePhi != this->RPOBlocks.at(BlockNum)->GetLastPhi()) {
			// Found phi function for DefOp. See if we can find a USE
			//  with USE SSANum corresponding to our DEF SSANum.
			for (size_t PhiIndex = 0; PhiIndex < UsePhi->GetPhiListSize(); ++PhiIndex) {
				if (UsePhi->GetUseSSANum(PhiIndex) == SSANum) {
					// We have a Phi USE that matches our DEF.
					if (!FirstUseSeen) {
						FirstUseSeen = true;
					}
					UseType = UsePhi->GetUseType(PhiIndex);
					FoundNumeric |= (IsNumeric(UseType));
					FoundUnknown |= (IsUnknown(UseType));
					FoundUninit |= (IsEqType(UNINIT, UseType));
					if (IsDataPtr(UseType)) {
						if (FoundPointer) {
							if (IsNotEqType(PtrType, UseType)) {
								msg("WARNING: Differing ptr types in global chain at Phi:");
								msg(" Prev: %d Current: %d BlockNum: %d\n",
									PtrType, UseType, BlockNum);
							}
							PtrType = POINTER;
						}
						else {
							FoundPointer = true;
							PtrType = UseType;
						}
					}
				} // end if matched SSA #
			} // end for all Phi USEs
		} // end if found matching Phi function for DefOp
	} // end for all block numbers in the function

	if (FirstUseSeen) {
		// 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) msg("Inferring global DEF of type %d\n", UseType);
		return UseType;
	}
	else { // not FirstUseSeen
		// If the block returns, then the DEFs could be used in the caller.
		if (!(DefBlock->HasReturn())) {
			UseType = UNINIT;
			// 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.  **!!**
			//  If they are memory DEFs, we cannot optimize, so we might want to see
			//  if we can find a reg DEF with no USEs here. We also want to exclude
			//  warning messages for the caller-saved reg DEFs generated for CALLs.
			if ((o_reg == DefOp.type) && (!CallInst)) {
				;
#if SMP_WARN_UNUSED_DEFS
				msg("WARNING: global DEF with no USEs for SSANum %d DefOp: ",
					SSANum);
				PrintOperand(DefOp);
				msg("\n");
#endif
			}
		}
	}

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

#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;
	list<SMPBasicBlock>::iterator CurrBlock;
	vector<list<SMPBasicBlock>::iterator>::iterator CurrRPO;
	set<SMPPhiFunction, LessPhi>::iterator CurrPhi;

	for (CurrRPO = this->RPOBlocks.begin(); CurrRPO != this->RPOBlocks.end(); ++CurrRPO) {
		CurrBlock = *CurrRPO;
		SMPOperandType MeetType;
		for (CurrPhi = CurrBlock->GetFirstPhi(); CurrPhi != CurrBlock->GetLastPhi(); ++CurrPhi) {
			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;
			// Change the DEF type to the MeetType and propagate.
			op_t DefOp = CurrPhi->GetAnyOp();
			CurrPhi = CurrBlock->SetPhiDefType(DefOp, MeetType);
			changed = true;
			this->ResetProcessedBlocks();
			changed |= CurrBlock->PropagateGlobalDefType(DefOp,
				MeetType, CurrPhi->GetDefSSANum());