SMPFunction.cpp

// part of SCCP processing; propagate const DEFs into Phi USEs and Phi DEFs
void SMPFunction::EvaluateAllPhiConstants(int BlockNum, vector<STARSBitSet> ExecutedEdgeBitSet, list<pair<int, int> > &SSAWorkList) {
	// For all Phi DEFs of the type we are tracking for const values:
	//   If Phi DEF const value is not already the lattice bottom value:
	//     Accumulate const DEF values only for Phi USEs that correspond to incoming
	//      edges that are executed.
	//     If we have a consistent const value, set Phi DEF const value to it; if
	//      we have conflicting const values, set Phi DEF const value to type lattice bottom.
	//     If we set the Phi DEF const value to a new value, then propagate along SSA edges.

	// For all Phi DEFs of the type we are tracking for const values:
	SMPBasicBlock *CurrBlock = this->GetBlockByNum(BlockNum);
	set<SMPPhiFunction, LessPhi>::iterator PhiIter;
	for (PhiIter = CurrBlock->GetFirstPhi(); PhiIter != CurrBlock->GetLastPhi(); ++PhiIter) {
		op_t PhiOp = PhiIter->GetAnyOp();
		if (!(o_reg == PhiOp.type))   // !!!!****!!!! Add stack locations also in safe functions
			continue;
		int DefSSANum = PhiIter->GetDefSSANum();
		int DefHashValue = HashGlobalNameAndSSA(PhiOp, DefSSANum);
	//   If Phi DEF const value is not already the lattice bottom value:
		map<int, struct STARS_SCCP_Const_Struct>::iterator ConstIter = this->FindConstValue(DefHashValue);
		STARSConstantValueType DefConstValType = STARS_CONST_TOP; // default; no entry in map
		if (ConstIter != this->GetLastConstValueIter()) { // found entry in map
			DefConstValType = ConstIter->second.ConstType;
		}
		if (DefConstValType != STARS_CONST_BOTTOM) {
	//     Accumulate const DEF values only for Phi USEs that correspond to incoming
	//      edges that are executed.
			uval_t ConstUseVal;
			bool ConstUseValueSeen = false;
			list<SMPBasicBlock *>::iterator PredIter;
			size_t PredIndex = 0;
			STARSConstantValueType DefFinalConstValType = DefConstValType;
			for (PredIter = CurrBlock->GetFirstPred(); PredIter != CurrBlock->GetLastPred(); ++PredIter) {
				int IncomingBlockNum = (*PredIter)->GetNumber();
				bool ExecutedIncomingEdge = ExecutedEdgeBitSet.at(BlockNum).GetBit(IncomingBlockNum);
				if (ExecutedIncomingEdge) {
					int UseSSANum = PhiIter->GetUseSSANum(PredIndex);
					int UseHashValue = HashGlobalNameAndSSA(PhiOp, UseSSANum);
	//     If we have a consistent const value, set Phi DEF const value to it; if
	//      we have conflicting const values, set Phi DEF const value to type lattice bottom.
					ConstIter = this->FindConstValue(UseHashValue);
					STARSConstantValueType UseConstValType = STARS_CONST_TOP; // default; no entry in map
					if (ConstIter != this->GetLastConstValueIter()) { // found entry in map
						UseConstValType = ConstIter->second.ConstType;
					}
					if (UseConstValType == STARS_CONST_HAS_VALUE) {
						if (ConstUseValueSeen) { // check for consistency of values
							if (ConstUseVal != ConstIter->second.ConstValue) { // inconsistent const values
								DefFinalConstValType = STARS_CONST_BOTTOM;
								break; // no need to see more Phi USEs
							}
						}
						else { // this is the first const value we have seen
							DefFinalConstValType = STARS_CONST_HAS_VALUE; // so far, anyway
							ConstUseValueSeen = true;
							ConstUseVal = ConstIter->second.ConstValue; // only value seen so far
						}
					}
					else if (UseConstValType == STARS_CONST_BOTTOM) {
						// Any BOTTOM value in a USE makes the DEF also become BOTTOM.
						DefFinalConstValType =  STARS_CONST_BOTTOM;
						break; // no need to see more Phi USEs
					}
					// else must be STARS_CONST_TOP, which is a don't-care case
				} // end if (ExecutedIncomingEdge)
				++PredIndex; // keep index in sync with PredIter
			} // end for PredIter iteration through predecessor blocks

	//     If we set the Phi DEF const value to a new value, then propagate along SSA edges.
			if (DefFinalConstValType != DefConstValType) { // const entry is changing
				struct STARS_SCCP_Const_Struct NewConstEntry;
				NewConstEntry.ConstType = DefFinalConstValType;
				NewConstEntry.ConstValue = ConstUseVal;
				if (DefConstValType == STARS_CONST_TOP) { // there was no old map entry; insert new one
					pair<int, struct STARS_SCCP_Const_Struct> NewMapEntry(DefHashValue, NewConstEntry);
					pair<map<int, struct STARS_SCCP_Const_Struct>::iterator, bool> InsertResult = this->ConstantDefs.insert(NewMapEntry);
					assert(InsertResult.second);
				}
				else { // old map entry needs to be changed
					this->ConstantDefs[DefHashValue] = NewConstEntry;
				}
				// Propagate along SSA edges.
				pair<int, int> SSAEdge(BlockNum, DefHashValue);
				SSAWorkList.push_back(SSAEdge);
			} // end if entry is changing
		} // end if previous DEF value was not already BOTTOM
	} // end for all Phi functions
	return;
} // end of SMPFunction::EvaluateAllPhiConstants()

// Do we not care if DEF underflowed, due to how it is used?
bool SMPFunction::IsBenignUnderflowDEF(op_t DefOp, int DefSSANum, size_t DefAddr, int &IdiomCode) {
	bool benign = false;
	list<SMPInstr *>::iterator InstIter;
	set<DefOrUse, LessDefUse>::iterator DefIter, UseIter;
	int UseSSANum;
	SMPOperandType DefType;

	// We are looking to suppress overflow and underflow warnings on the following
	//  code sequence: PTR1-PTR2+1 gets a loop invariant code motion optimization
	//  that pulls  temp := 1-PTR2 out of the loop, and leaves temp2 := PTR1+temp
	//  inside the loop. The hoisted subtraction could underflow, and the addition
	//  that is not hoisted could overflow. The net effect of these two instructions
	//  is benign, however, so we want to suppress underflow and overflow checks on
	//  both of them, but only if we can match the pair of instructions.
	
	// We know that DefOp/DefAddr/DefSSANum refer to a subtraction instruction that
	//  produces a NEGATEDPTR result. We only need to find the paired addition instruction
	//  that USEs the same SSA name to produce a PTROFFSET result to prove that we have
	//  a case of benign underflow and overflow. If we find such a pair, we will mark
	//  both of their DEF results as benign overflows to suppress overflow checks.

	// PAINFUL: Linear search of instructions. Need to address this in the future.
	//  Perhaps we should have a map of UseHashValue to InstAddr, but that is more
	//  memory consumption. Sure would be useful, though.
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		UseIter = CurrInst->FindUse(DefOp);
		UseSSANum = UseIter->GetSSANum();
		if (UseSSANum == DefSSANum) {
			// Only remaining question: Do we produce a PTROFFSET in CurrInst? (If we do,
			//  that implies we had an addition, so we don't need to check that.)
			DefIter = CurrInst->GetFirstNonFlagsDef();
			DefType = DefIter->GetType();
			// NOTE: Make this more general. What if we just move the NEGATEDPTR into a register
			//  and then the next instruction, with different SSA name, produces the PTROFFSET?
			//  !!!!!*****!!!!!
			if (IsEqType(DefType, PTROFFSET)) {
				// Found a pair. Mark both DEFs as benign and return true.
				benign = true;
				IdiomCode = 4;
				// Note that we have two possibilities for the addition. The NEGATEDPTR could be
				//  both the DEF and a USE, e.g. add negptr,ptr1; or the NEGATEDPTR could be
				//  just a USE, e.g. add reg,negptr, so that reg is overwritten and becomes a
				//  PTROFFSET. It really does not matter. The point is that we want to ignore
				//  overflow on this addition, and also on the subtraction that produced the
				//  NEGATEDPTR, so we mark the DEF in each instruction as benignly overflowing.
				op_t UseInstDefOp = DefIter->GetOp();
				CurrInst->SetDefNoOverflow(UseInstDefOp, true);
				SMPInstr *DefInst = this->GetInstFromAddr(DefAddr);
				DefInst->SetDefNoOverflow(DefOp, true);
				break;
			}
		}
	}

	return benign;
} // end of SMPFunction::IsBenignUnderflowDEF()

bool SMPFunction::HasIntErrorCallSink(op_t DefOp, int DefSSANum, size_t DefAddr, std::string &SinkString) {
	bool FoundSink = false;

	this->ResetProcessedBlocks(); // prepare for recursion through blocks
	SinkString.clear();
	SMPBasicBlock *CurrBlock = this->GetBlockFromInstAddr(DefAddr);
	assert(CurrBlock != NULL);

	FoundSink = CurrBlock->IsCriticalSink(DefOp, DefSSANum, SinkString);

	return FoundSink;
} // end of SMPFunction::HasIntErrorCallSink()

// Compute SSA form data structures across the function.
void SMPFunction::ComputeSSA(void) {
	bool DebugFlag = false;
	bool DumpFlag = false;
#if SMP_DEBUG_DATAFLOW
	DumpFlag |= (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
	DebugFlag |= (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
#endif

#if 1
	if (DumpFlag)
		this->Dump();
#endif
	if (DebugFlag) SMP_msg("Computing IDoms.\n");
	this->ComputeIDoms();
	if (DebugFlag) SMP_msg("Computing Dom frontiers.\n");
	this->ComputeDomFrontiers();
	if (DebugFlag) SMP_msg("Computing global names.\n");
	this->ComputeGlobalNames();
	if (DebugFlag) SMP_msg("Computing blocks defined in.\n");
	this->ComputeBlocksDefinedIn();

	if (DebugFlag) SMP_msg("Inserting Phi functions.\n");
	this->InsertPhiFunctions();
	if (DebugFlag) SMP_msg("Building dominator tree.\n");
	this->BuildDominatorTree();
	if (DebugFlag) SMP_msg("Computing SSA renumbering.\n");
	this->SSARenumber();
	list<SMPBasicBlock *>::iterator BlockIter;
	SMPBasicBlock *CurrBlock;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		if (CurrBlock->FindLoopHeadsAndTails()) {
			++this->LoopCount;
		}

		if (DumpFlag) CurrBlock->Dump();

		if (DebugFlag) SMP_msg("Computing local names.\n");
		CurrBlock->SetLocalNames();
		if (DebugFlag) SMP_msg("Computing local SSA renumbering.\n");
		CurrBlock->SSALocalRenumber();
		if (DumpFlag) CurrBlock->Dump();

#if STARS_BUILD_DEF_USE_CHAINS
		if (DebugFlag) SMP_msg("Computing global chains.\n");
		CurrBlock->CreateGlobalChains();
#endif

#if 1
		if (DebugFlag) SMP_msg("Marking dead registers.\n");
		CurrBlock->MarkDeadRegs();
#endif
	}
#if SMP_DEBUG_DATAFLOW
	if (DumpFlag)
		this->Dump();
#endif

	// Once SSA numbers have been set into all DEFs, USES, and DU-chains, then
	//  the SSA numbering data structures will no longer be used and can be
	//  de-allocated.
	this->FreeSSAMemory();
	return;
} // end of SMPFunction::ComputeSSA()

// Detect which blocks are in which loops and populate FuncLoopsByBlock data structure.
void SMPFunction::DetectLoops(void) {
	list<SMPBasicBlock *>::iterator BlockIter;
	size_t LoopNumber = 0;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		SMPBasicBlock *CurrBlock = (*BlockIter);
		if (CurrBlock->IsLoopTailBlock()) {
			// For each loop tail block, get its loop header block number (the target
			//  block for its back edge). Then traverse the CFG upwards, recording all
			//  of the basic block numbers that lie between the loop tail and loop head,
			//  along with the tail and head.
			this->ResetProcessedBlocks();
			int TailBlockNum = CurrBlock->GetNumber();
			int HeadBlockNum = CurrBlock->GetLoopHeaderNumber();
			assert((TailBlockNum != SMP_BLOCKNUM_UNINIT) && (HeadBlockNum != SMP_BLOCKNUM_UNINIT));
			list<list<SMPBasicBlock *>::iterator> BlockWorkList;
			BlockWorkList.push_back(BlockIter);
			SMPBasicBlock *WorkBlock;
			SMPBasicBlock *PredBlock;
			list<SMPBasicBlock *>::iterator WorkIter;
			list<SMPBasicBlock *>::iterator PredIter;
			do {
				WorkIter = BlockWorkList.front();
				BlockWorkList.pop_front();
				WorkBlock = (*WorkIter);
				int WorkBlockNum = WorkBlock->GetNumber();
				assert(WorkBlockNum != SMP_BLOCKNUM_UNINIT);
				if (!(WorkBlock->IsProcessed())) {
					this->FuncLoopsByBlock[(size_t) WorkBlockNum].SetBit(LoopNumber);
					WorkBlock->SetProcessed(true);
					// Add unprocessed predecessors to the work list until we reach the loop head.
					if (WorkBlockNum != HeadBlockNum) {
						for (PredIter = WorkBlock->GetFirstPred(); PredIter != WorkBlock->GetLastPred(); ++PredIter) {
							PredBlock = (*PredIter);
							bool AlreadyProcessed = PredBlock->IsProcessed();
							if (!AlreadyProcessed) {
								BlockWorkList.push_back(PredIter);
							}
						}
					}
				}
			} while (!BlockWorkList.empty());
			++LoopNumber;
		}
	}

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

// Find memory writes (DEFs) with possible aliases
void SMPFunction::AliasAnalysis(void) {
	// First task: Mark which memory DEFs MIGHT be aliased because an
	//  indirect memory write occurs somewhere in the DEF-USE chain.
	//  Memory DEF-USE chains with no possible aliasing can be subjected
	//  to type inference and type-based optimizing annotations, e.g. a
	//  register spill to memory followed by retrieval from spill memory
	//  followed by NUMERIC USEs should be typed as a continuous NUMERIC
	//  chain if there is no possibility of aliasing.

	// Preparatory step: For each indirect write, mark all def-use chains
	//  (maintained at the basic block level) that include the indirect
	//  write instruction. If there are no indirect writes in the function,
	//  leave all DEFs marked as unaliased and exit.
	if (!(this->HasIndirectWrites))
		return;

	list<SMPBasicBlock *>::iterator BlockIter;
	SMPBasicBlock *CurrBlock;
	vector<SMPInstr *>::iterator BlkInstIter;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		for (BlkInstIter = CurrBlock->GetFirstInst(); BlkInstIter != CurrBlock->GetLastInst(); ++BlkInstIter) {
			SMPInstr *CurrInst = (*BlkInstIter);
			if (CurrInst->HasIndirectMemoryWrite()) {
#if STARS_BUILD_DEF_USE_CHAINS
				CurrBlock->MarkIndWriteChains(CurrInst->GetAddr());
#endif
				// Until we get true aliasing analysis, any indirect write
				//  is classified as may-be-aliased.
				CurrBlock->SetMaybeAliased(true);
			}
		} // end for all insts in block
	} // end for all blocks in function

	// Step one: Find only the memory DEFs to start with.
	bool FoundIndWrite = false;
	list<SMPInstr *>::iterator InstIter;
	for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
		SMPInstr *CurrInst = (*InstIter);
		ea_t InstAddr = CurrInst->GetAddr();
		if (CurrInst->HasDestMemoryOperand()) {
			// Starting with the DEF instruction, traverse the control flow
			//  until we run into (A) the re-definition of the operand, including
			//  a re-definition of any of its addressing registers, or (B) an
			//  indirect write. Return false if condition A terminates the
			//  search, and true if condition B terminates the search.
			this->ResetProcessedBlocks();
			op_t MemDefOp = CurrInst->MDGetMemDefOp();
			assert(o_void != MemDefOp.type);
			set<DefOrUse, LessDefUse>::iterator CurrMemDef = CurrInst->FindDef(MemDefOp);
			assert(CurrMemDef != CurrInst->GetLastDef());
			int SSANum = CurrMemDef->GetSSANum();
			FoundIndWrite = this->FindPossibleChainAlias(CurrInst, MemDefOp, SSANum);
			if (FoundIndWrite) {
				// Mark the DEF as aliased.
				CurrMemDef = CurrInst->SetDefIndWrite(CurrMemDef->GetOp(), true);
			}
		} // end if inst has dest memory operand
	} // end for all instructions

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

// Does the DefOp DEF_USE chain have an indirect mem write starting at CurrInst?
bool SMPFunction::FindPossibleChainAlias(SMPInstr *CurrInst, op_t DefOp, int SSANum) {
#if 0
	bool DebugFlag = false;
	if (0 == strcmp("sdissect", this->GetFuncName())) {
		// Next line is just a good place to set a break point.
		DebugFlag = true;
	}
#endif

	// Starting with the DEF instruction, traverse the control flow
	//  until we run into (A) the re-definition of the operand, including
	//  a re-definition of any of its addressing registers, or (B) an
	//  indirect write. Return false if condition A terminates the
	//  search, and true if condition B terminates the search.
	SMPBasicBlock *CurrBlock = CurrInst->GetBlock();
	if (!(CurrBlock->IsProcessed())) {
		CurrBlock->SetProcessed(true);
	}
	else
		return false; // block already processed

	// Proceed by cases:
	ea_t DefAddr = CurrInst->GetAddr();
	set<DefOrUse, LessDefUse>::iterator UseIter;
	vector<SMPInstr *>::iterator InstIter = CurrBlock->GetInstIterFromAddr(DefAddr);
	bool IndWriteFound, ReDef;
	++InstIter;
	// Case 1: Local name. Return the IndWrite flag for the local Def-Use
	//  chain begun by CurrInst.
	bool UseAfterIndirectWrite = CurrBlock->HasUseAfterIndWrite(DefOp, InstIter, IndWriteFound, ReDef);
	bool LiveOutFlag = CurrBlock->IsLiveOut(DefOp);
	if (CurrBlock->IsLocalName(DefOp)) {
#if STARS_BUILD_DEF_USE_CHAINS
		return CurrBlock->GetLocalDUChainIndWrite(DefOp, SSANum);
#else
		return (UseAfterIndirectWrite);
#endif
	}

	// Case 2: Global name.
#if 1
	if (UseAfterIndirectWrite) {
		return true;
	}
	else if (IndWriteFound) {
		// We found an indirect write, but no USE of DefOp after it.
		//  If DefOp is LiveOut, then there is a USE of DefOp in a
		//  successor block, so DefOp can be aliased.
		return (LiveOutFlag && !ReDef);
	}
#else
	// Case 2A: If Def-Use chain within this block for this memory operand
	//  has its IndWrite flag set to true, then stop and return true.
	else if (CurrBlock->GetGlobalDUChainIndWrite(DefOp, DefAddr)) {
		return true;
	}

	// Case 2B: Else if Def-Use chain is not the last chain in this block
	//  for this operand, then there must be a later redefinition of the
	//  memory operand (with new SSA number assigned) later in this block.
	//  Because we did not fall into case 2A, we know there is no IndWrite
	//  within the current memory operand's chain, so we return false.
	else if (!CurrBlock->IsLastGlobalChain(DefOp, DefAddr)) {
		return false;
	}

	// Case 2C: Else if current memory operand is NOT LiveOut, even though
	//  this is the last def-use chain in the block, then there is no more
	//  traversing of the control flow graph to be done. The chain has ended
	//  without encountering an IndWrite, so return false.
	else if (!(CurrBlock->IsLiveOut(DefOp))) {
		return false;
	}
#endif

	// Case 2D: We have passed all previous checks, so we must have a memory
	//  operand that reaches the end of the block without encountering an
	//  IndWrite and is LiveOut. Its may-alias status will be determined by
	//  following the control flow graph for all successor blocks and examining
	//  the def-use chains in those blocks.
	list<SMPBasicBlock *>::iterator SuccBlock;
	SuccBlock = CurrBlock->GetFirstSucc();
	bool FoundAliasedWrite = false;
	if (LiveOutFlag && !ReDef) {
		do {
			if ((*SuccBlock)->IsLiveIn(DefOp)) {
				FoundAliasedWrite = this->FindChainAliasHelper(SuccBlock, DefOp);
			}
			++SuccBlock;
		} while (!FoundAliasedWrite && (SuccBlock != CurrBlock->GetLastSucc()));
	}

	return FoundAliasedWrite;
} // end of SMPFunction::FindPossibleChainAlias()

// recursive helper for global DU-chains that traverse CFG
bool SMPFunction::FindChainAliasHelper(list<SMPBasicBlock *>::iterator BlockIter, op_t DefOp) {
	bool DebugFlag = false;
	SMPBasicBlock *CurrBlock = (*BlockIter);
	if (0 == strcmp("mem2chunk_check", this->GetFuncName())) {
		// Next line is just a good place to set a break point.
		DebugFlag = true;
	}

	if (!(CurrBlock->IsProcessed())) {
		CurrBlock->SetProcessed(true);
	}
	else
		return false; // block already processed

	// The LVA sets can be used to decide whether it is possible that
	//  the incoming DU chain overlaps a may-alias write. We can express
	//  the decision making in a truth table:
	//
	//  Case #    LiveIn?   Killed?   AliasedWrite in block?  Action to take
	//  -------   -------   -------   ----------------------  --------------
	//    1          N          N                N             return false
	//    2          N          N                Y             return false
	//    3          N          Y                N             return false
	//    4          N          Y                Y             return false
	//    5          Y          N                N             recurse into successors
	//    6          Y          N                Y             return true
	//    7          Y          Y                N             return false
	//    8          Y          Y                Y             check location of aliased write
	//
	// In the last case, if there is an aliased write before the
	// incoming DEF is killed and after it is used, then the
	// incoming DU chain overlaps an aliased write, otherwise
	// it does not.


	// If not LiveIn, incoming DU chain does not run through this block
	//  at all, so return false.
	if (!(CurrBlock->IsLiveIn(DefOp)))
		return false;  // cases 1-4

	bool killed = CurrBlock->IsVarKill(DefOp);
	bool BlockHasAliasedWrite = CurrBlock->MaybeAliasedWrite();

	if (BlockHasAliasedWrite) {
		// If DefOp is LiveIn and is not killed, then any aliased
		//  write in the block overlaps the incoming DU chain.
		if (!killed) {
			return true;  // case 6
		}
		// If DefOp is LiveIn and is killed, then the location
		//  of the aliased write is the determining factor.
		else { // case 8; depends on finding indirect write, then USE, before re-DEF.
			vector<SMPInstr *>::iterator InstIter = CurrBlock->GetFirstInst();
			bool IndWriteFound, ReDef;
			return CurrBlock->HasUseAfterIndWrite(DefOp, InstIter, IndWriteFound, ReDef);
		}
	}
	else {
		// If killed, no aliased write, then cannot overlap an aliased write.
		if (killed)
			return false; // case 7
		else {
			// Need to recurse into all successors, because we passed through
			//  the block without seeing an aliased write and without killing
			//  the DefOp.
			list<SMPBasicBlock *>::iterator SuccBlock;
			SuccBlock = CurrBlock->GetFirstSucc();
			bool FoundAliasedWrite = false;
			while (!FoundAliasedWrite && (SuccBlock != CurrBlock->GetLastSucc())) {
				FoundAliasedWrite = this->FindChainAliasHelper(SuccBlock, DefOp);
				++SuccBlock;
			};

			if (DebugFlag) {
				SMP_msg("FindChainAliasHelper is returning %d\n", FoundAliasedWrite);
			}
			return FoundAliasedWrite;
		}
	}
	assert(false); // statement should be unreachable
	return false;
} // end of SMPFunction::FindChainAliasHelper()

// 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 BlockIter;
	SMPBasicBlock *CurrBlock;
	list<SMPBasicBlock *> UnresolvedBranchWorkList;
	ea_t InstAddr;
#if SMP_DEBUG_DATAFLOW_VERBOSE
	SMP_msg("SetLinks called for %s\n", this->GetFuncName());
#endif
	// First, set up the map of instructions to basic blocks.
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		vector<SMPInstr *>::iterator InstIter;
		for (InstIter = CurrBlock->GetFirstInst(); InstIter != CurrBlock->GetLastInst(); ++InstIter) {
			InstAddr = (*InstIter)->GetAddr();
			pair<ea_t, SMPBasicBlock *> MapItem(InstAddr, CurrBlock);
			InstBlockMap.insert(MapItem);
		}
	}

#if SMP_DEBUG_DATAFLOW_VERBOSE
	SMP_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 (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		vector<SMPInstr *>::iterator InstIter = (--(CurrBlock->GetLastInst()));
		SMPInstr *CurrInst = (*InstIter);
		InstAddr = CurrInst->GetAddr();
		bool CondTailCall = false;
		if (CurrBlock->HasReturn()) {
			if (!(CurrInst->IsCondTailCall())) {
				// We either have a return instruction or an unconditional
				//  tail call instruction. We don't want to link to the
				//  tail call target, and there is no link for a return
				continue;
			}
			else {
				// We have a conditional tail call. We don't want to
				//  link to the tail call target, but we do want fall
				//  through to the next instruction.
				CondTailCall = true;
			}
		}

		// Last instruction in block; set successors
		bool CallFlag = (CALL == CurrInst->GetDataFlowType());
		bool IndirJumpFlag = (INDIR_JUMP == CurrInst->GetDataFlowType());
		bool IndirCallFlag = (INDIR_CALL == CurrInst->GetDataFlowType());
		// NOTE: Dues to phase re-ordering, we cannot yet identify tail calls,
		//  so CondTailCall and TailCallFlag will always be false, which is harmless.
		//  SMPInstr::SetTailCall() will do a little cleanup later.
		bool TailCallFlag = CondTailCall && CurrInst->IsCondTailCall();
		SMP_xref_t CurrXrefs;
		bool LinkedToTarget = false;
		for (bool ok = CurrXrefs.SMP_first_from(CurrInst->GetAddr(), XREF_ALL);
			ok;
			ok = CurrXrefs.SMP_next_from()) {
				ea_t TargetAddr = CurrXrefs.GetTo();
				if ((TargetAddr != 0) && (CurrXrefs.GetIscode())) {
					// Found a code target, with its address in CurrXrefs.to
					if ((CallFlag || IndirCallFlag || TailCallFlag) 
						&& (TargetAddr != (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, SMPBasicBlock *>::iterator MapEntry;
					MapEntry = this->InstBlockMap.find(TargetAddr);
					if (MapEntry == this->InstBlockMap.end()) {
						; // do nothing; probably a tail call (not yet identified)
#if 0
						SMP_msg("WARNING: addr %x not found in map for %s\n", TargetAddr,
							this->GetFuncName());
						SMP_msg(" Referenced from %s\n", CurrInst->GetDisasm());
#endif
					}
					else {
						SMPBasicBlock *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);
						LinkedToTarget = true;
#if SMP_USE_SWITCH_TABLE_INFO
						if (IndirJumpFlag) {
#if SMP_DEBUG_SWITCH_TABLE_INFO
							SMP_msg("Switch table link: jump at %x target at %x\n",
								CurrInst->GetAddr(), TargetAddr);
#else
							;
#endif
						}
#endif
					}
				}
		} // end for all xrefs
		if (IndirJumpFlag && (!LinkedToTarget)) {
			this->UnresolvedIndirectJumps = true;
			UnresolvedBranchWorkList.push_back(CurrBlock);
			SMP_msg("WARNING: Unresolved indirect jump at %lx\n", (unsigned long) CurrInst->GetAddr());
		}
		else if (IndirCallFlag && (!LinkedToTarget)) {
			this->UnresolvedIndirectCalls = true;
			SMP_msg("WARNING: Unresolved indirect call at %lx\n", (unsigned long) CurrInst->GetAddr());
		}
	} // end for all blocks

	// Mark all blocks that can be reached from the entry block, so we can find the unreachable ones.
	this->ResetProcessedBlocks();
	this->Blocks.front()->DepthFirstMark();
	// We have two cases: (1) Unresolved indirect branches could be targeting the unmarked blocks, making
	//  these blocks reachable, in which case we should link the unresolved branches to the unmarked blocks;
	//  or (2) there are no unresolved branches, in which case the unmarked blocks are unreachable within
	//  the function. They might be reachable from outside the function using exception handling jumps, but
	//  that still would not allow us to link them into the CFG of this function properly, so in any case we
	//  are deleting those unreachable blocks and not emitting annotations for them.
	// NOTE: An odd new gcc recursion optimization uses indirect calls within the function, so
	//  they can behave like indirect jumps. However, we don't want to link unresolved calls to unmarked blocks
	//  at this time.
	bool HellNodeCase = (!UnresolvedBranchWorkList.empty() && (this->HasUnresolvedIndirectCalls() || this->HasUnresolvedIndirectJumps()));
	bool AddedMissingLinks = false;
	bool changed;
	do {
		changed = false;
		list<SMPBasicBlock *>::iterator BlockIter = this->Blocks.begin();
		while (BlockIter != this->Blocks.end()) {
			CurrBlock = (*BlockIter);
			if (CurrBlock->IsProcessed()) {
				++BlockIter;
			}
			else {
				// Block cannot be reached from entry node, even after we have added links
				//  on previous loop iterations.
				if (!HellNodeCase) {
					if (CurrBlock->AllNops())
						SMP_msg("INFO: Removing all nops block at %lx\n", (unsigned long) CurrBlock->GetFirstAddr());
					else
						SMP_msg("INFO: Removing unreachable block at %lx\n", (unsigned long) CurrBlock->GetFirstAddr());
					// Remove this block from the predecessors list of its successors.
					list<SMPBasicBlock *>::iterator SuccIter;
					ea_t TempAddr = CurrBlock->GetFirstAddr();
					for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
						(*SuccIter)->ErasePred(TempAddr);
					}
					// Remove the unreachable instructions from the function inst list.
					vector<SMPInstr *>::iterator InstIter;
					InstIter = CurrBlock->GetFirstInst();
					ea_t FirstBadAddr = (*InstIter)->GetAddr();
					InstIter = CurrBlock->GetLastInst();
					--InstIter; // get last real instruction
					ea_t LastBadAddr = (*InstIter)->GetAddr();
					this->EraseInstRange(FirstBadAddr, LastBadAddr);

					// Remove the block from the blocks list.
					BlockIter = this->Blocks.erase(BlockIter);
					this->BlockCount -= 1;

#if 0  // Exception handling code requires something more delicate than this. Later checks for stack adjustment etc. can look at these blocks.
					// Finally, call destructors on the block and insts removed.
					InstIter = CurrBlock->GetFirstInst();
					while (InstIter != CurrBlock->GetLastInst()) {
						SMPInstr *DeadInst = (*InstIter);
						++InstIter;
						if (NULL != DeadInst) delete DeadInst;
					}
					delete CurrBlock;
#endif
				}
				else { // HellNodeCase
					// Block must be reachable only through an unresolved indirect branch.
					// Make each unresolved indirect branch link to the block so it is reachable.
					list<SMPBasicBlock *>::iterator WorkIter;
					AddedMissingLinks = true;
					for (WorkIter = UnresolvedBranchWorkList.begin(); WorkIter != UnresolvedBranchWorkList.end(); ++ WorkIter) {
						SMPBasicBlock *WorkBlock = (*WorkIter);
						WorkBlock->LinkToSucc(CurrBlock);
					}
					// Mark CurrBlock as now being reachable, along with the blocks it dominates.
					CurrBlock->DepthFirstMark();
					++BlockIter;
				}
				changed = true;
			} // end if (processed) ... else ...
		} // end loop through blocks
	} while (changed);
	if (HellNodeCase && (!AddedMissingLinks)) {
		SMP_msg("SERIOUS WARNING: Function at %lx has unresolved indirect branches but no unreachable blocks.\n",
			(unsigned long) this->FirstEA);
	}

#if 0
	// 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. Any blocks that have
	//  no predecessors but are not all no-ops should also be removed with a different
	//  log message.
	// NOTE: Prior to construction of hell nodes in functions with unresolved indirect jumps,
	//  we cannot conclude that a block with no predecessors is unreachable. Also, the block
	//  order might be such that removal of a block makes an already processed block
	//  unreachable, so we have to iterate until there are no more changes.
	bool NoPredecessors;
	bool OnlyPredIsItself;
	list<SMPBasicBlock *>::iterator CurrPred;
#if SMP_USE_SWITCH_TABLE_INFO
	if (!(this->HasUnresolvedIndirectJumps() || this->HasUnresolvedIndirectCalls())) {
#else
	if (!(this->HasIndirectJumps() || this->HasIndirectCalls())) {
#endif
		bool changed;
		do {
			changed = false;
			BlockIter = this->Blocks.begin();
			++BlockIter; // don't delete the top block, no matter what.
			while (BlockIter != this->Blocks.end()) {
				CurrBlock = (*BlockIter);
				OnlyPredIsItself = false;
				CurrPred = CurrBlock->GetFirstPred();
				NoPredecessors = (CurrPred == CurrBlock->GetLastPred());
				if (!NoPredecessors) {
					if ((*CurrPred)->GetFirstAddr() == CurrBlock->GetFirstAddr()) { // self-recursion
						++CurrPred; // any more preds besides itself?
						OnlyPredIsItself = (CurrPred == CurrBlock->GetLastPred());
							// Only predecessor was the self-recursion if no more preds
					}
				}
				if (NoPredecessors || OnlyPredIsItself) {
					if (CurrBlock->AllNops())
						SMP_msg("Removing all nops block at %x\n", CurrBlock->GetFirstAddr());
					else
						SMP_msg("Removing block with no predecessors at %x\n", CurrBlock->GetFirstAddr());
					// Remove this block from the predecessors list of its successors.
					list<SMPBasicBlock *>::iterator SuccIter;
					ea_t TempAddr = CurrBlock->GetFirstAddr();
					for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
						(*SuccIter)->ErasePred(TempAddr);
					}
					// Remove the unreachable instructions from the function inst list.
					vector<SMPInstr *>::iterator InstIter;
					InstIter = CurrBlock->GetFirstInst();
					ea_t FirstBadAddr = (*InstIter)->GetAddr();
					InstIter = CurrBlock->GetLastInst();
					--InstIter; // get last real instruction
					ea_t LastBadAddr = (*InstIter)->GetAddr();
					this->EraseInstRange(FirstBadAddr, LastBadAddr);

					// Finally, remove the block from the blocks list.
					BlockIter = this->Blocks.erase(BlockIter);
					this->BlockCount -= 1;
					changed = true;
				}
				else {
					++BlockIter;
				}
			} // end while all blocks after the first one
		} while (changed);
	} // end if not unresolved indirect jumps or indirect calls
	else if (this->UnresolvedIndirectJumps) {
		// Make each unresolved indirect branch have each block with no predecessor as a target,
		//  so that the resulting CFG has a proper structure.
		BlockIter = this->Blocks.begin();
		++BlockIter; // The top block is expected to have no predecessors, which is not a CFG problem.
		bool AddedMissingLinks = false;
		while (BlockIter != this->Blocks.end()) {
			CurrBlock = (*BlockIter);
			OnlyPredIsItself = false;
			CurrPred = CurrBlock->GetFirstPred();
			NoPredecessors = (CurrPred == CurrBlock->GetLastPred());
			if (!NoPredecessors) {
				if ((*CurrPred)->GetFirstAddr() == CurrBlock->GetFirstAddr()) { // self-recursion
					++CurrPred; // any more preds besides itself?
					OnlyPredIsItself = (CurrPred == CurrBlock->GetLastPred());
						// Only predecessor was the self-recursion if no more preds
				}
			}
			if (NoPredecessors || OnlyPredIsItself) {
				// Block must be reachable only through an unresolved indirect branch.
				// Make each unresolved indirect branch link to the block so it is reachable.
				list<SMPBasicBlock *>::iterator WorkIter;
				AddedMissingLinks = true;
				for (WorkIter = UnresolvedBranchWorkList.begin(); WorkIter != UnresolvedBranchWorkList.end(); ++ WorkIter) {
					SMPBasicBlock *WorkBlock = (*WorkIter);
					WorkBlock->LinkToSucc(CurrBlock);
				}
			}
			++BlockIter;
		} // end for all blocks
		if (!AddedMissingLinks) {
			SMP_msg("SERIOUS WARNING: Function at %x has unresolved indirect branches but no unreachable blocks.\n", this->FirstEA);
		}
	}
#endif

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

// Number all basic blocks in reverse postorder (RPO) and set RPOBlocks vector to
//  access them.
void SMPFunction::RPONumberBlocks(void) {
#if SMP_DEBUG_DATAFLOW
	bool DebugFlag = false;
	DebugFlag = (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
	if (DebugFlag) SMP_msg("Entered RPONumberBlocks\n");
#endif
	int CurrNum = 0;
	list<SMPBasicBlock *> WorkList;

	// Number the first block with 0.
	list<SMPBasicBlock *>::iterator BlockIter = this->Blocks.begin();
	SMPBasicBlock *CurrBlock = (*BlockIter);
#if 0
	if (this->RPOBlocks.capacity() <= (size_t) this->BlockCount) {
		SMP_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<SMPBasicBlock *>::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<SMPBasicBlock *>::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
				SMP_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<SMPBasicBlock *>::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);
#if SMP_DEBUG_DATAFLOW
			SMP_msg("Picked LowAddr %x and set RPO number %d\n", LowAddr, CurrNum);
#endif
			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

	// Prior to construction of hell nodes for functions with indirect jumps, there
	//  could still be unnumbered blocks because they appear to be unreachable
	//  (no predecessors from SetLinks() because they are reached only via indirect
	//  jumps). We need to number these and push them on the RPOBlocks vector so
	//  that the vector contains all the blocks.
	// NOTE: Odd new gcc recursion optimization seems to use indirect calls to reach
	//  some blocks within a recursive function, operating somewhat like an indirect
	//  jump.
	if (this->HasIndirectJumps() || this->HasIndirectCalls()) {
		for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
			CurrBlock = (*BlockIter);
			if (SMP_BLOCKNUM_UNINIT == CurrBlock->GetNumber()) {
				SMP_msg("WARNING: Numbering indirectly reachable block at %lx\n", (unsigned long) CurrBlock->GetFirstAddr());
				CurrBlock->SetNumber(CurrNum);
				this->RPOBlocks.push_back(CurrBlock);
				++CurrNum;
			}
		}
	}
	// If we still have unnumbered blocks, it is not because of indirect jumps or calls.
	//  We have some mysterious dead code.
	if (this->BlockCount > this->RPOBlocks.size()) {
		SMP_msg("SERIOUS WARNING: RPONumberBlocks method: Function %s has BlockCount %d and RPOBlocks size %zu\n",
			this->GetFuncName(), this->BlockCount, this->RPOBlocks.size());
		for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
			CurrBlock = (*BlockIter);
			if (SMP_BLOCKNUM_UNINIT == CurrBlock->GetNumber()) {
				SMP_msg("WARNING: Numbering apparently unreachable block at %lx\n", (unsigned long) CurrBlock->GetFirstAddr());
				CurrBlock->SetNumber(CurrNum);
				this->RPOBlocks.push_back(CurrBlock);
				++CurrNum;
			}
		}
	}
	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 BlockIter;
	SMPBasicBlock *CurrBlock;
#if SMP_DEBUG_DATAFLOW
	bool DebugFlag = (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
#endif
#if SMP_DEBUG_DATAFLOW_VERBOSE
	SMP_msg("LiveVariableAnalysis for %s\n", this->GetFuncName());
#endif

#if SMP_ANALYZE_STACK_POINTER
	;
#else
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		// Initialize the Killed and UpwardExposed sets for each block.
		CurrBlock->InitKilledExposed(this->UsesFramePointer());
	}
#endif

	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 (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
			CurrBlock = (*BlockIter);