SMPFunction.cpp

	}

	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 {
			// Incoming global DU chains get a new global DU chain
			//  built within the block with a pseudo-DefAddr of
			//  one byte before the first address of the block.
			ea_t PseudoDefAddr = CurrBlock->GetFirstAddr() - 1;
			return CurrBlock->GetGlobalDUChainIndWrite(DefOp, PseudoDefAddr); // case 8
		}
	}
	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);
		list<SMPInstr *>::iterator CurrInst;
		for (CurrInst = CurrBlock->GetFirstInstr();
			CurrInst != CurrBlock->GetLastInstr();
			++CurrInst) {
				InstAddr = (*CurrInst)->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);
		list<SMPInstr *>::iterator InstIter = (--(CurrBlock->GetLastInstr()));
		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 %x\n", CurrInst->GetAddr());
		}
		else if (IndirCallFlag && (!LinkedToTarget)) {
			this->UnresolvedIndirectCalls = true;
			SMP_msg("WARNING: Unresolved indirect call at %x\n", 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("Removing all nops block at %x\n", CurrBlock->GetFirstAddr());
					else
						SMP_msg("Removing unreachable block 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.
					list<SMPInstr *>::iterator InstIter;
					InstIter = CurrBlock->GetFirstInstr();
					ea_t FirstBadAddr = (*InstIter)->GetAddr();
					InstIter = CurrBlock->GetLastInstr();
					--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->GetFirstInstr();
					while (InstIter != CurrBlock->GetLastInstr()) {
						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 %x has unresolved indirect branches but no unreachable blocks.\n", 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.
					list<SMPInstr *>::iterator InstIter;
					InstIter = CurrBlock->GetFirstInstr();
					ea_t FirstBadAddr = (*InstIter)->GetAddr();
					InstIter = CurrBlock->GetLastInstr();
					--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 %x\n", 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 %x\n", 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);
			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.at(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();
	SMPBasicBlock *FirstBlock = this->Blocks.front();
	for (UpExposedIter = FirstBlock->GetFirstUpExposed();
		UpExposedIter != FirstBlock->GetLastUpExposed();
		++UpExposedIter) {
			// Add DEF with SSANum of 0.
			(*MarkerInst)->AddDef(*UpExposedIter, UNINIT, 0);
			// Add to the VarKill and LiveIn sets.
			FirstBlock->AddVarKill(*UpExposedIter); // "killed" by marker inst def
			FirstBlock->AddLiveIn(*UpExposedIter);
	}
	for (LiveOutIter = FirstBlock->GetFirstLiveOut();
		LiveOutIter != FirstBlock->GetLastLiveOut();
		++LiveOutIter) {
			if (!(FirstBlock->IsVarKill(*LiveOutIter))) {
				// Add DEF with SSANum of 0.
				(*MarkerInst)->AddDef(*LiveOutIter, UNINIT, 0);
				// Add to the VarKill and LiveIn sets.
				FirstBlock->AddVarKill(*LiveOutIter); // "killed" by marker inst def
				FirstBlock->AddLiveIn(*LiveOutIter);
			}
	}
#endif

#if SMP_DEBUG_DATAFLOW_VERBOSE
	if (DebugFlag) SMP_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("_ZN6soplex7NameSetC2Eiidd", this->GetFuncName()));
	if (DebugFlag) SMP_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) {
		SMP_msg("BlockCount = %d RPOBlocks size = %zu\n", this->BlockCount, this->RPOBlocks.size());
	}
	if (this->BlockCount != this->RPOBlocks.size()) {
		SMP_msg("SERIOUS WARNING: Function %s has BlockCount of %d and RPOBlocks size of %zu\n",
			this->GetFuncName(), this->BlockCount, this->RPOBlocks.size());
	}
	this->IDom[0] = 0; // First block is dominated only by itself
	bool changed;
	do {
		changed = false;
		for (size_t RPONum = 1; RPONum < (size_t) this->BlockCount; ++RPONum) {
			if (DebugFlag) SMP_msg("RPONum %zu\n", RPONum);
#if 0
			if (DebugFlag) {
				SMP_msg("RPOBlocks vector size: %d\n", this->RPOBlocks.size());
				for (size_t index = 0; index < this->RPOBlocks.size(); ++index) {
					SMP_msg("RPOBlocks entry %d is %d\n", index, RPOBlocks[index]->GetNumber());
				}
			}
#endif
			// To avoid infinite loops on blocks that dominate themselves but otherwise have no 
			//  predecessors (probably reachable only through indirect jumps), we stop processing
			//  the blocks once the IDom becomes the top (entry) block. This probably saves time
			//  on other blocks as well.
			if (0 == this->IDom[RPONum])
				continue;

			SMPBasicBlock *CurrBlock = this->RPOBlocks.at(RPONum);
			// if (DebugFlag) SMP_msg("CurrBlock: %x\n", CurrBlock._Ptr);
			list<SMPBasicBlock *>::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) SMP_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) SMP_msg("Pred IDom: %d\n", PredIDOM);
				if (SMP_BLOCKNUM_UNINIT != PredIDOM) {
					NewIdom = PredNum;
					break;
				}
			}
			if (NewIdom == SMP_BLOCKNUM_UNINIT) {
				SMP_msg("WARNING: Failure on NewIdom in ComputeIDoms for %s\n", this->GetFuncName());
				if (this->HasIndirectJumps() || this->HasIndirectCalls()) {
					// Might be reachable only through indirect jumps.
					NewIdom = 0; // make it dominated by entry block
					SMP_msg("WARNING: Assuming block %d at address %d is reachable indirectly.\n",
						CurrBlock->GetNumber(), CurrBlock->GetFirstAddr());
				}
				else {
					// Might be exception handling code, reachable only by call stack walking.
					NewIdom = 0; // make it be dominated by entry block
					SMP_msg("WARNING: Assuming block %d at address %d is reachable by exception handling.\n",
						CurrBlock->GetNumber(), CurrBlock->GetFirstAddr());
				}
			}
			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) SMP_msg("PredNum: %d\n", PredNum);
				// **!!** We can 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, or better yet, create hell nodes
				//  if the function has indirect jumps.
				if (PredNum == SMP_BLOCKNUM_UNINIT)
					continue;
				int PredIDOM = this->IDom.at(PredNum);
				if (DebugFlag) SMP_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) SMP_msg("Old NewIdom value: %d\n", NewIdom);
				NewIdom = this->IntersectDoms(PredNum, NewIdom);
				if (DebugFlag) SMP_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) SMP_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 BlockIter;
	SMPBasicBlock *RunnerBlock;
	SMPBasicBlock *CurrBlock;
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		// 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<SMPBasicBlock *>::iterator PredIter;
			SMPBasicBlock *CurrPred;
			for (PredIter = CurrBlock->GetFirstPred(); PredIter != CurrBlock->GetLastPred(); ++PredIter) {
				CurrPred = (*PredIter);
				// 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 BlockIter;
	SMPBasicBlock *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("uw_frame_state_for", this->GetFuncName()));
#endif

	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		CurrBlock = (*BlockIter);
		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
			if (DebugFlag) {
				SMP_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
				if (DebugFlag) {
					SMP_msg(" already in GlobalNames.\n");
				}
#endif
			}
			else {
				++index;
#if SMP_DEBUG_DATAFLOW
				if (DebugFlag) {
					SMP_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 BlockIter;
	SMPBasicBlock *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_VERBOSE
	SMP_msg("Number of GlobalNames: %d\n", this->GlobalNames.size());
	SMP_msg("Size of BlocksDefinedIn: %d\n", this->BlocksDefinedIn.size());
#endif
	for (BlockIter = this->Blocks.begin(); BlockIter != this->Blocks.end(); ++BlockIter) {
		set<op_t, LessOp>::iterator KillIter;
		CurrBlock = (*BlockIter);
		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.
					SMP_msg("ComputeBlocksDefinedIn: Bad index: %d limit: %zu\n", index,
						this->GlobalNames.size());
					SMP_msg("Block number %d\n", CurrBlock->GetNumber());
					SMP_msg("Killed item: ");
					PrintListOperand(*KillIter);
					SMP_msg("\n");
					SMP_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("uw_frame_state_for", this->GetFuncName()));
#endif
	if (DebugFlag) SMP_msg("GlobalNames size: %zu\n", this->GlobalNames.size());
	for (NameIter = this->GlobalNames.begin(); NameIter != this->GlobalNames.end(); ++NameIter) {
		int CurrNameIndex = (int) (ExtractGlobalIndex(*NameIter));
		if (DebugFlag) SMP_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_VERBOSE
			if (DebugFlag) SMP_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_VERBOSE
				if (DebugFlag) SMP_msg("WorkIter: %d\n", *WorkIter);
#endif
				if (DebugFlag && (*WorkIter > this->BlockCount)) {
					SMP_msg("ERROR: WorkList block # %d out of range.\n", *WorkIter);
				}
				SMPBasicBlock *WorkBlock = this->RPOBlocks[*WorkIter];
				for (DomFrontIter = WorkBlock->GetFirstDomFrontier();
					DomFrontIter != WorkBlock->GetLastDomFrontier();
					++DomFrontIter) {
#if SMP_DEBUG_DATAFLOW_VERBOSE
					if (DebugFlag) SMP_msg("DomFront: %d\n", *DomFrontIter);
#endif
					if (DebugFlag && (*DomFrontIter > this->BlockCount)) {
						SMP_msg("ERROR: DomFront block # %d out of range.\n", *DomFrontIter);
					}
					SMPBasicBlock *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_VERBOSE
							if (DebugFlag) SMP_msg("Added phi for name %d at top of block %d\n", CurrNameIndex, PhiBlock->GetNumber());
#endif
						}
					}
					else {
						if (DebugFlag) {
							SMP_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) {
					SMP_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) SMP_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 != (int) index) // block can dominate itself, but not in DomTree!
			this->DomTree.at(parent).second.push_back((int) index);
	}

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

// Does basic block HeadBlockNum dominate basic block TailBlockNum?
bool SMPFunction::DoesBlockDominateBlock(int HeadBlockNum, int TailBlockNum) {
	if (HeadBlockNum == TailBlockNum)
		return true;
	else if ((HeadBlockNum == SMP_BLOCKNUM_UNINIT) || (TailBlockNum == SMP_BLOCKNUM_UNINIT)) {
		return false;
	}
	else {
		// Recurse downward from HeadBlockNum in the dominator tree until we find TailBlockNum
		//  or return false if we never find it.
		bool FoundIt = false;