SMPDataFlowAnalysis.cpp

	// Cycle through all chunks that belong to the function.
	func_tail_iterator_t FuncTail(&(this->FuncInfo));
	size_t ChunkCounter = 0;
	for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
		const area_t &CurrChunk = FuncTail.chunk();
		++ChunkCounter;
		if (1 < ChunkCounter) {
			this->SharedChunks = true;
#if SMP_DEBUG_CHUNKS
			msg("Found tail chunk for %s at %x\n", this->FuncName, CurrChunk.startEA);
#endif
		}
		// Build the instruction and block lists for the function.
		for (ea_t addr = CurrChunk.startEA; addr < CurrChunk.endEA;
			addr = get_item_end(addr)) {
			flags_t InstrFlags = getFlags(addr);
			if (isHead(InstrFlags) && isCode(InstrFlags)) {
				SMPInstr CurrInst = SMPInstr(addr);
				// Fill in the instruction data members.
#if SMP_DEBUG_CONTROLFLOW
				msg("SMPFunction::Analyze: calling CurrInst::Analyze.\n");
#endif
				CurrInst.Analyze();
				if (SMPBinaryDebug) {
					msg("Disasm:  %s \n", CurrInst.GetDisasm());
				}
				if (CurrInst.GetDataFlowType() == INDIR_CALL)
					this->IndirectCalls = true;

				// Before we insert the instruction into the instruction
				//  list, determine if it is a jump target that does not
				//  follow a basic block terminator. This is the special case
				//  of a CASE in a SWITCH that falls through into another
				//  CASE, for example. The first sequence of statements
				//  was not terminated by a C "break;" statement, so it
				//  looks like straight line code, but there is an entry
				//  point at the beginning of the second CASE sequence and
				//  we have to split basic blocks at the entry point.
				if ((FirstInBlock != this->Instrs.end())
					&& CurrInst.IsJumpTarget()) {
#if SMP_DEBUG_CONTROLFLOW
					msg("SMPFunction::Analyze: hit special jump target case.\n");
#endif
					LastInBlock = --(this->Instrs.end());
					SMPBasicBlock CurrBlock = SMPBasicBlock(FirstInBlock,
						LastInBlock);
					CurrBlock.Analyze();
					// If not the first chunk in the function, it is a shared
					//  tail chunk.
					if (ChunkCounter > 1) {
						CurrBlock.SetShared();
					}
					FirstInBlock = this->Instrs.end();
					LastInBlock = this->Instrs.end();
					this->Blocks.push_back(CurrBlock);
					this->BlockCount += 1;
				}

#if SMP_DEBUG_CONTROLFLOW
		msg("SMPFunction::Analyze: putting CurrInst on list.\n");
#endif
				// Insert instruction at end of list.
				this->Instrs.push_back(CurrInst);

				// Find basic block leaders and terminators.
				if (FirstInBlock == this->Instrs.end()) {
#if SMP_DEBUG_CONTROLFLOW
		msg("SMPFunction::Analyze: setting FirstInBlock.\n");
#endif
					FirstInBlock = --(this->Instrs.end());
				}
				if (CurrInst.IsBasicBlockTerminator()) {
#if SMP_DEBUG_CONTROLFLOW
		msg("SMPFunction::Analyze: found block terminator.\n");
#endif
					LastInBlock = --(this->Instrs.end());
					SMPBasicBlock CurrBlock = SMPBasicBlock(FirstInBlock, LastInBlock);
					CurrBlock.Analyze();
					// If not the first chunk in the function, it is a shared
					//  tail chunk.
					if (ChunkCounter > 1) {
						CurrBlock.SetShared();
					}
					FirstInBlock = this->Instrs.end();
					LastInBlock = this->Instrs.end();
					this->Blocks.push_back(CurrBlock);
					this->BlockCount += 1;

					// Is the instruction a branch to a target outside the function? If
					//  so, this function has shared tail chunks.
					if (CurrInst.IsBranchToFarChunk()) {
						this->SharedChunks = true;
					}
				}
			} // end if (isHead(InstrFlags) && isCode(InstrFlags)
		} // end for (ea_t addr = FuncInfo.startEA; ... )

		// Handle the special case in which a function does not terminate
		//  with a return instruction or any other basic block terminator.
		//  Sometimes IDA Pro sees a call to a NORET function and decides
		//  to not include the dead code after it in the function. That
		//  dead code includes the return instruction, so the function no
		//  longer includes a return instruction and terminates with a CALL.
		if (FirstInBlock != this->Instrs.end()) {
			LastInBlock = --(this->Instrs.end());
			SMPBasicBlock CurrBlock = SMPBasicBlock(FirstInBlock, LastInBlock);
			CurrBlock.Analyze();
			// If not the first chunk in the function, it is a shared
			//  tail chunk.
			if (ChunkCounter > 1) {
				CurrBlock.SetShared();
			}
			FirstInBlock = this->Instrs.end();
			LastInBlock = this->Instrs.end();
			this->Blocks.push_back(CurrBlock);
			this->BlockCount += 1;
		}
	} // end for (bool ChunkOK = ...)

#if KLUDGE_VFPRINTF_FAMILY
	if (0 != strstr(this->GetFuncName(), "printf")) {
		this->SharedChunks = true;
		msg("Kludging function %s\n", this->GetFuncName());
	}
#endif

	// Set up basic block links and map of instructions to blocks.
	if (!(this->HasSharedChunks())) {
		this->SetLinks();
#if SMP_COMPUTE_LVA_SSA
		this->RPONumberBlocks();
		this->LiveVariableAnalysis();
		this->ComputeSSA();
		bool DumpFlag = (0 == strcmp("main", this->GetFuncName()));
		DumpFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
		DumpFlag |= (0 == strcmp(".init_proc", this->GetFuncName()));
#if 0
		DumpFlag = true;
#endif
		if (DumpFlag) 
			this->Dump();
#endif
	}

#if SMP_DEBUG_CONTROLFLOW
	msg("SMPFunction::Analyze: set stack frame info.\n");
#endif
	// Figure out the stack frame and related info.
	this->SetStackFrameInfo();

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

// Compute SSA form data structures across the function.
void SMPFunction::ComputeSSA(void) {
#if 1
	this->ComputeIDoms();
	this->ComputeDomFrontiers();
	this->ComputeGlobalNames();
	this->ComputeBlocksDefinedIn();
	this->InsertPhiFunctions();
	this->SSARenumber();
#endif
	return;
} // end of SMPFunction::ComputeSSA()

// Link basic blocks to their predecessors and successors, and build the map
//  of instruction addresses to basic blocks.
void SMPFunction::SetLinks(void) {
	list<SMPBasicBlock>::iterator CurrBlock;
#if SMP_DEBUG_DATAFLOW
	msg("SetLinks called for %s\n", this->GetFuncName());
#endif
	// First, set up the map of instructions to basic blocks.
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		list<list<SMPInstr>::iterator>::iterator CurrInst;
		for (CurrInst = CurrBlock->GetFirstInstr();
			CurrInst != CurrBlock->GetLastInstr();
			++CurrInst) {
				pair<ea_t, list<SMPBasicBlock>::iterator> MapItem((*CurrInst)->GetAddr(),CurrBlock);
				InstBlockMap.insert(MapItem);
		}
	}

#if SMP_DEBUG_DATAFLOW
	msg("SetLinks finished mapping: %s\n", this->GetFuncName());
#endif
	// Next, set successors of each basic block, also setting up the predecessors in the
	//  process.
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		list<SMPInstr>::iterator CurrInst = *(--(CurrBlock->GetLastInstr()));
		// Last instruction in block; set successors
		bool CallFlag = (CALL == CurrInst->GetDataFlowType());
		xrefblk_t CurrXrefs;
		for (bool ok = CurrXrefs.first_from(CurrInst->GetAddr(), XREF_ALL);
			ok;
			ok = CurrXrefs.next_from()) {
				if ((CurrXrefs.to != 0) && (CurrXrefs.iscode)) {
					// Found a code target, with its address in CurrXrefs.to
					if (CallFlag && (CurrXrefs.to != (CurrInst->GetAddr() + CurrInst->GetCmd().size))) {
						// A call instruction will have two targets: the fall through to the
						//  next instruction, and the called function. We want to link to the
						//  fall-through instruction, but not to the called function.
						// Some blocks end with a call just because the fall-through instruction
						//  is a jump target from elsewhere.
						continue;
					}
					map<ea_t, list<SMPBasicBlock>::iterator>::iterator MapEntry;
					MapEntry = this->InstBlockMap.find(CurrXrefs.to);
					if (MapEntry == this->InstBlockMap.end()) {
						msg("WARNING: addr %x not found in map for %s\n", CurrXrefs.to,
							this->GetFuncName());
						msg(" Referenced from %s\n", CurrInst->GetDisasm());
					}
					else {
						list<SMPBasicBlock>::iterator Target = MapEntry->second;
						// Make target block a successor of current block.
						CurrBlock->LinkToSucc(Target);
						// Make current block a predecessor of target block.
						Target->LinkToPred(CurrBlock);
					}
				}
		} // end for all xrefs
	} // end for all blocks

	// If we have any blocks that are all no-ops and have no predecessors, remove those
	//  blocks. They are dead and make the CFG no longer a lattice.
	CurrBlock = this->Blocks.begin();
	while (CurrBlock != this->Blocks.end()) {
		if (CurrBlock->AllNops() && (CurrBlock->GetFirstPred() == CurrBlock->GetLastPred())) {
			msg("Removing all nops block at %x\n", CurrBlock->GetFirstAddr());
			CurrBlock = this->Blocks.erase(CurrBlock);
			this->BlockCount -= 1;
		}
		else
			++CurrBlock;
	}

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

// Number all basic blocks in reverse postorder (RPO) and set RPOBlocks vector to
//  access them.
void SMPFunction::RPONumberBlocks(void) {
	bool DebugFlag = (0 == strcmp("vfprintf", this->GetFuncName()));
	int CurrNum = 0;
	list<list<SMPBasicBlock>::iterator> WorkList;

	// Number the first block with 0.
	list<SMPBasicBlock>::iterator CurrBlock = this->Blocks.begin();
#if 0
	if (this->RPOBlocks.capacity() <= (size_t) this->BlockCount) {
		msg("Reserving %d RPOBlocks old value: %d\n", 2+this->BlockCount, this->RPOBlocks.capacity());
		this->RPOBlocks.reserve(2 + this->BlockCount);
		this->RPOBlocks.assign(2 + this->BlockCount, this->Blocks.end());
	}
#endif
	CurrBlock->SetNumber(CurrNum);
	this->RPOBlocks.push_back(CurrBlock);
	++CurrNum;
	// Push the first block's successors onto the work list.
	list<list<SMPBasicBlock>::iterator>::iterator CurrSucc = CurrBlock->GetFirstSucc();
	while (CurrSucc != CurrBlock->GetLastSucc()) {
		WorkList.push_back(*CurrSucc);
		++CurrSucc;
	}

	// Use the WorkList to iterate through all blocks in the function
	list<list<SMPBasicBlock>::iterator>::iterator CurrListItem = WorkList.begin();
	bool change;
	while (!WorkList.empty()) {
		change = false;
		while (CurrListItem != WorkList.end()) {
			if ((*CurrListItem)->GetNumber() != SMP_BLOCKNUM_UNINIT) {
				// Duplicates get pushed onto the WorkList because a block
				//  can be the successor of multiple other blocks. If it is
				//  already numbered, it is a duplicate and can be removed
				//  from the list.
				CurrListItem = WorkList.erase(CurrListItem);
				change = true;
				continue;
			}
			if ((*CurrListItem)->AllPredecessorsNumbered()) {
				// Ready to be numbered.
				(*CurrListItem)->SetNumber(CurrNum);
#if 0
				msg("Set RPO number %d\n", CurrNum);
				if (DebugFlag && (7 == CurrNum))
					this->Dump();
#endif
				this->RPOBlocks.push_back(*CurrListItem);
				++CurrNum;
				change = true;
				// Push its unnumbered successors onto the work list.
				CurrSucc = (*CurrListItem)->GetFirstSucc();
				while (CurrSucc != (*CurrListItem)->GetLastSucc()) {
					if ((*CurrSucc)->GetNumber() == SMP_BLOCKNUM_UNINIT)
						WorkList.push_back(*CurrSucc);
					++CurrSucc;
				}
				CurrListItem = WorkList.erase(CurrListItem);
			}
			else {
				++CurrListItem;
			}
		} // end while (CurrListItem != WorkList.end())
		if (change) {
			// Reset CurrListItem to beginning of work list for next iteration.
			CurrListItem = WorkList.begin();
		}
		else {
			// Loops can cause us to not be able to find a WorkList item that has
			//  all predecessors numbered. Take the WorkList item with the lowest address
			//  and number it so we can proceed.
			CurrListItem = WorkList.begin();
			ea_t LowAddr = (*CurrListItem)->GetFirstAddr();
			list<list<SMPBasicBlock>::iterator>::iterator SaveItem = CurrListItem;
			++CurrListItem;
			while (CurrListItem != WorkList.end()) {
				if (LowAddr > (*CurrListItem)->GetFirstAddr()) {
					SaveItem = CurrListItem;
					LowAddr = (*CurrListItem)->GetFirstAddr();
				}
				++CurrListItem;
			}
			// SaveItem should now be numbered.
			(*SaveItem)->SetNumber(CurrNum);
			msg("Picked LowAddr %x and set RPO number %d\n", LowAddr, CurrNum);
			this->RPOBlocks.push_back(*SaveItem);
			++CurrNum;
			// Push its unnumbered successors onto the work list.
			CurrSucc = (*SaveItem)->GetFirstSucc();
			while (CurrSucc != (*SaveItem)->GetLastSucc()) {
				if ((*CurrSucc)->GetNumber() == SMP_BLOCKNUM_UNINIT)
					WorkList.push_back(*CurrSucc);
				++CurrSucc;
			}
			CurrListItem = WorkList.erase(SaveItem);
			CurrListItem = WorkList.begin();
		} // end if (change) ... else ...
	} // end while work list is nonempty
	return;
} // end of SMPFunction::RPONumberBlocks()

// 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;
	msg("LiveVariableAnalysis for %s\n", this->GetFuncName());

	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.
#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
	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 = (0 == strcmp("vfprintf", this->GetFuncName()));
	// 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) {
				if (DebugFlag) msg("Pred: %d\n", (*CurrPred)->GetNumber());
				int PredIDOM = this->IDom.at((*CurrPred)->GetNumber());
				if (DebugFlag) msg("Pred IDom: %d\n", PredIDOM);
				if (SMP_BLOCKNUM_UNINIT != PredIDOM) {
					NewIdom = (*CurrPred)->GetNumber();
					break;
				}
			}
			if (NewIdom == SMP_BLOCKNUM_UNINIT)
				msg("Failure on NewIdom in ComputeIDoms for %s\n", this->GetFuncName());
			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);
				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;
	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;
					(*CurrPred)->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

	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		for (SetIter = CurrBlock->GetFirstUpExposed(); SetIter != CurrBlock->GetLastUpExposed(); ++SetIter) {
			op_t TempOp = *SetIter;
			msg("Global Name: ");
			PrintOneOperand(TempOp, 0, -1);
			set<op_t, LessOp>::iterator AlreadyInSet = this->GlobalNames.find(TempOp);
			if (AlreadyInSet != this->GlobalNames.end()) {
				// Already in GlobalNames, so don't assign an index number or call insert.
				msg(" already in GlobalNames.\n");
				continue;
			}
			
			// 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.
			TempOp.n = (char) (index & 0x000000ff);
			TempOp.offb = (char) ((index & 0x0000ff00) >> 8);
			TempOp.offo = (char) ((index & 0x00ff0000) >> 16);
			++index;
			this->GlobalNames.insert(TempOp);
			msg(" inserted as index %d\n", ExtractGlobalIndex(TempOp));
		}
	}

	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);
	}
	msg("Number of GlobalNames: %d\n", this->GlobalNames.size());
	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 0
				msg("VarKill item offo: %d offb: %d n: %d index: %d\n", NameIter->offo, NameIter->offb, NameIter->n, index);
#endif
				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
	for (NameIter = this->GlobalNames.begin(); NameIter != this->GlobalNames.end(); ++NameIter) {
		int CurrNameIndex = (int) (ExtractGlobalIndex(*NameIter));
		// 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()) {
			msg("WorkList size: %d\n", WorkList.size());
			list<int>::iterator WorkIter = WorkList.begin();
			while (WorkIter != WorkList.end()) {
				set<int>::iterator DomFrontIter;
				list<SMPBasicBlock>::iterator WorkBlock = this->RPOBlocks[*WorkIter];
				for (DomFrontIter = WorkBlock->GetFirstDomFrontier();
					DomFrontIter != WorkBlock->GetLastDomFrontier();
					++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();
						SMPPhiFunction CurrPhi(CurrNameIndex);
						DefOrUse CurrRef(*NameIter);
						for (size_t NumCopies = 0; NumCopies < NumPreds; ++NumCopies) {
							CurrPhi.PushBack(CurrRef);
						}
						if (PhiBlock->AddPhi(CurrPhi)) {
							// If not already in Phi set, new phi function was inserted.
							WorkList.push_back(PhiBlock->GetNumber());
							msg("Added phi for name %d at top of block %d\n", CurrNameIndex, PhiBlock->GetNumber());
						}
					}
				} // end for all blocks in the dominance frontier
				// Remove current block number from the work list
				WorkIter = WorkList.erase(WorkIter);
			} // end for all block numbers in the work list
		} // end while the work list is not empty
	} // end for all elements of the GlobalNames set
	return;
} // end of SMPFunction::InsertPhiFunctions()

void SMPFunction::SSARenumber(void) {

	// **!!** Get this into CVS and patch in the code later after final debugging
	return;
}

// 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,	"%x %d FUNC LOCAL  %s ", this->FuncInfo.startEA,
			this->Size, this->FuncName);
	}
	else {
		qfprintf(AnnotFile,	"%x %d 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 == LocalVarsDeallocInstr) {
			DeallocTrigger = true;
		}
		else if (DeallocTrigger) { // Time for annotation
			qfprintf(AnnotFile,	"%x %d DEALLOC STACK esp - %d %s\n", addr,
				LocalVarsSize, LocalVarsSize, CurrInst->GetDisasm());
			DeallocTrigger = false;
		}

		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));
	}
	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));
		PrintOneOperand(*NameIter, 0, -1);
		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()

// Initialize the DFACategory[] array to define instruction classes
//   for the purposes of data flow analysis.
void InitDFACategory(void) {
	// Default category is 0, not the start or end of a basic block.
	(void) memset(DFACategory, 0, sizeof(DFACategory));

DFACategory[NN_call] = CALL;                // Call Procedure
DFACategory[NN_callfi] = INDIR_CALL;              // Indirect Call Far Procedure
DFACategory[NN_callni] = INDIR_CALL;              // Indirect Call Near Procedure

DFACategory[NN_hlt] = HALT;                 // Halt

DFACategory[NN_int] = CALL;                 // Call to Interrupt Procedure
DFACategory[NN_into] = CALL;                // Call to Interrupt Procedure if Overflow Flag = 1
DFACategory[NN_int3] = CALL;                // Trap to Debugger
DFACategory[NN_iretw] = RETURN;               // Interrupt Return
DFACategory[NN_iret] = RETURN;                // Interrupt Return
DFACategory[NN_iretd] = RETURN;               // Interrupt Return (use32)
DFACategory[NN_iretq] = RETURN;               // Interrupt Return (use64)
DFACategory[NN_ja] = COND_BRANCH;                  // Jump if Above (CF=0 & ZF=0)
DFACategory[NN_jae] = COND_BRANCH;                 // Jump if Above or Equal (CF=0)
DFACategory[NN_jb] = COND_BRANCH;                  // Jump if Below (CF=1)
DFACategory[NN_jbe] = COND_BRANCH;                 // Jump if Below or Equal (CF=1 | ZF=1)
DFACategory[NN_jc] = COND_BRANCH;                  // Jump if Carry (CF=1)
DFACategory[NN_jcxz] = COND_BRANCH;                // Jump if CX is 0
DFACategory[NN_jecxz] = COND_BRANCH;               // Jump if ECX is 0
DFACategory[NN_jrcxz] = COND_BRANCH;               // Jump if RCX is 0
DFACategory[NN_je] = COND_BRANCH;                  // Jump if Equal (ZF=1)
DFACategory[NN_jg] = COND_BRANCH;                  // Jump if Greater (ZF=0 & SF=OF)
DFACategory[NN_jge] = COND_BRANCH;                 // Jump if Greater or Equal (SF=OF)
DFACategory[NN_jl] = COND_BRANCH;                  // Jump if Less (SF!=OF)
DFACategory[NN_jle] = COND_BRANCH;                 // Jump if Less or Equal (ZF=1 | SF!=OF)
DFACategory[NN_jna] = COND_BRANCH;                 // Jump if Not Above (CF=1 | ZF=1)
DFACategory[NN_jnae] = COND_BRANCH;                // Jump if Not Above or Equal (CF=1)
DFACategory[NN_jnb] = COND_BRANCH;                 // Jump if Not Below (CF=0)
DFACategory[NN_jnbe] = COND_BRANCH;                // Jump if Not Below or Equal (CF=0 & ZF=0)
DFACategory[NN_jnc] = COND_BRANCH;                 // Jump if Not Carry (CF=0)
DFACategory[NN_jne] = COND_BRANCH;                 // Jump if Not Equal (ZF=0)
DFACategory[NN_jng] = COND_BRANCH;                 // Jump if Not Greater (ZF=1 | SF!=OF)
DFACategory[NN_jnge] = COND_BRANCH;                // Jump if Not Greater or Equal (ZF=1)
DFACategory[NN_jnl] = COND_BRANCH;                 // Jump if Not Less (SF=OF)
DFACategory[NN_jnle] = COND_BRANCH;                // Jump if Not Less or Equal (ZF=0 & SF=OF)
DFACategory[NN_jno] = COND_BRANCH;                 // Jump if Not Overflow (OF=0)
DFACategory[NN_jnp] = COND_BRANCH;                 // Jump if Not Parity (PF=0)
DFACategory[NN_jns] = COND_BRANCH;                 // Jump if Not Sign (SF=0)
DFACategory[NN_jnz] = COND_BRANCH;                 // Jump if Not Zero (ZF=0)
DFACategory[NN_jo] = COND_BRANCH;                  // Jump if Overflow (OF=1)
DFACategory[NN_jp] = COND_BRANCH;                  // Jump if Parity (PF=1)
DFACategory[NN_jpe] = COND_BRANCH;                 // Jump if Parity Even (PF=1)
DFACategory[NN_jpo] = COND_BRANCH;                 // Jump if Parity Odd  (PF=0)
DFACategory[NN_js] = COND_BRANCH;                  // Jump if Sign (SF=1)
DFACategory[NN_jz] = COND_BRANCH;                  // Jump if Zero (ZF=1)
DFACategory[NN_jmp] = JUMP;                 // Jump
DFACategory[NN_jmpfi] = INDIR_JUMP;               // Indirect Far Jump
DFACategory[NN_jmpni] = INDIR_JUMP;               // Indirect Near Jump
DFACategory[NN_jmpshort] = JUMP;            // Jump Short (only in 64-bit mode)

DFACategory[NN_loopw] = COND_BRANCH;               // Loop while ECX != 0
DFACategory[NN_loop] = COND_BRANCH;                // Loop while CX != 0
DFACategory[NN_loopd] = COND_BRANCH;               // Loop while ECX != 0
DFACategory[NN_loopq] = COND_BRANCH;               // Loop while RCX != 0
DFACategory[NN_loopwe] = COND_BRANCH;              // Loop while CX != 0 and ZF=1
DFACategory[NN_loope] = COND_BRANCH;               // Loop while rCX != 0 and ZF=1
DFACategory[NN_loopde] = COND_BRANCH;              // Loop while ECX != 0 and ZF=1
DFACategory[NN_loopqe] = COND_BRANCH;              // Loop while RCX != 0 and ZF=1
DFACategory[NN_loopwne] = COND_BRANCH;             // Loop while CX != 0 and ZF=0
DFACategory[NN_loopne] = COND_BRANCH;              // Loop while rCX != 0 and ZF=0
DFACategory[NN_loopdne] = COND_BRANCH;             // Loop while ECX != 0 and ZF=0
DFACategory[NN_loopqne] = COND_BRANCH;             // Loop while RCX != 0 and ZF=0

DFACategory[NN_retn] = RETURN;                // Return Near from Procedure
DFACategory[NN_retf] = RETURN;                // Return Far from Procedure

//
//      Pentium instructions
//

DFACategory[NN_rsm] = HALT;                 // Resume from System Management Mode

//      Pentium II instructions

DFACategory[NN_sysenter] = CALL;            // Fast Transition to System Call Entry Point
DFACategory[NN_sysexit] = CALL;             // Fast Transition from System Call Entry Point

// AMD syscall/sysret instructions  NOTE: not AMD, found in Intel manual

DFACategory[NN_syscall] = CALL;             // Low latency system call
DFACategory[NN_sysret] = CALL;              // Return from system call

// VMX instructions

DFACategory[NN_vmcall] = INDIR_CALL;              // Call to VM Monitor

  return;

} // end InitDFACategory()