SMPFunction.cpp

#endif
#ifdef SMP_DEBUG_FUNC
		msg(" %s has shared chunks \n", this->GetFuncName());
#endif
		// Figure out the stack frame and related info.
		this->SetStackFrameInfo();
	}

	// We can finally search for stack loads now that UseFP has been fixed by
	//  GetStackFrameInfo(). Otherwise, we would do this in SMPInstr::Analyze(),
	//  but the UseFP flag is not ready that early.
	list<SMPInstr>::iterator StLoadInstIter = this->Instrs.begin();
	while (StLoadInstIter != this->Instrs.end()) {
		StLoadInstIter->MDFindLoadFromStack(this->UseFP);
		++StLoadInstIter;
	}

	// Audit the call instructions and call targets.
	if ((!this->AllCallTargets.empty()) || this->UnresolvedIndirectCalls) {
		bool FoundBadCallTarget = false;
		vector<ea_t>::iterator CurrTarget = this->AllCallTargets.begin();
		while (CurrTarget != this->AllCallTargets.end()) {
			if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
				// Found a call target that is within the function.
				FoundBadCallTarget = true;
				if (this->FirstEA == *CurrTarget) { // Direct recursion, not a pseudo-jump
					this->DirectlyRecursive = true;
				}
				CurrTarget = this->AllCallTargets.erase(CurrTarget);
			}
			else {
				++CurrTarget;
			}
		}
		if (FoundBadCallTarget) {
			// We have to mark the pseudo-call instructions and audit the direct and
			//  indirect call target vectors.

			// Audit direct call targets.
			CurrTarget = this->DirectCallTargets.begin();
			while (CurrTarget != this->DirectCallTargets.end()) {
				if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
					// Found a call target that is within the function.
					CurrTarget = this->DirectCallTargets.erase(CurrTarget);
				}
				else {
					++CurrTarget;
				}
			}
			// Audit indirect call targets.
			CurrTarget = this->IndirectCallTargets.begin();
			while (CurrTarget != this->IndirectCallTargets.end()) {
				if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
					// Found a call target that is within the function.
					CurrTarget = this->IndirectCallTargets.erase(CurrTarget);
				}
				else {
					++CurrTarget;
				}
			}
			// Find calls used as jumps.
			list<SMPInstr>::iterator InstIter = this->Instrs.begin();
			while (InstIter != this->Instrs.end()) {
				SMPitype InstFlow = InstIter->GetDataFlowType();
				if ((CALL == InstFlow) || (INDIR_CALL == InstFlow)) {
					InstIter->AnalyzeCallInst(this->FirstEA, this->FuncInfo.endEA);
				}
				++InstIter;
			}
		} // end if (FoundBadCallTarget)
	}

	this->MarkFunctionSafe();
} // end of SMPFunction::Analyze()

// For each instruction, mark the non-flags-reg DEFs as having live
//  metadata (mmStrata needs to fetch and track this metadata for this
//  instruction) or dead metadata (won't be used as addressing reg, won't
//  be stored to memory, won't be returned to caller).
void SMPFunction::AnalyzeMetadataLiveness(void) {
	bool changed;
	int BaseReg;
	int IndexReg;
	ushort ScaleFactor;
	ea_t offset;
	op_t BaseOp, IndexOp, ReturnOp, DefOp, UseOp;
	BaseOp.type = o_reg;
	IndexOp.type = o_reg;
	ReturnOp.type = o_reg;
	list<SMPInstr>::iterator CurrInst;
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	set<DefOrUse, LessDefUse>::iterator NextUse;
	bool DebugFlag = false;
	int IterationCount = 0;
#if SMP_DEBUG_DATAFLOW
	if (0 == strcmp("uw_frame_state_for", this->GetFuncName())) {
		DebugFlag = true;
	}
#endif

	do {
		changed = false;
		++IterationCount;
		bool SafeMemDest;
		if (DebugFlag) {
			msg("AnalyzeMetadataLiveness iteration count: %d \n", IterationCount);
		}
		for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
			SafeMemDest = false;  // true for some SafeFunc instructions
			// Skip the SSA marker instruction.
			if (NN_fnop == CurrInst->GetCmd().itype)
				continue;

			if (DebugFlag) {
				msg("Inst addr: %x \n", CurrInst->GetAddr());
			}
			CurrDef = CurrInst->GetFirstDef();
			while (CurrDef != CurrInst->GetLastDef()) {
				if (DEF_METADATA_UNANALYZED == CurrDef->GetMetadataStatus()) {
					DefOp = CurrDef->GetOp();
					// Handle special registers never used as address regs.
					if (DefOp.is_reg(X86_FLAGS_REG)
						|| ((o_trreg <= DefOp.type) && (o_xmmreg >= DefOp.type))) {
						CurrDef = CurrInst->SetDefMetadata(DefOp,
							DEF_METADATA_UNUSED);
						changed = true;
					}
					else if (DefOp.is_reg(R_sp) 
						|| (this->UseFP && DefOp.is_reg(R_bp))) {
						// Stack pointer register DEFs always have live
						//  metadata, but we don't need to propagate back
						//  through particular DEF-USE chains.
						CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_USED);
						changed = true;
					}
					else if ((o_mem <= DefOp.type) && (o_displ >= DefOp.type)) {
						// DEF is a memory operand. The addressing registers
						//  therefore have live metadata, and the memory metadata is live.
						// EXCEPTION: If the function is Safe, then direct stack writes
						//  to local variables (above the outgoing args area of the frame)
						//  are not live metadata, and there will be no indirect local frame
						//  writes, by definition of "safe." So, for safe funcs, only
						//  the o_mem (globals) and indirect writes are live metadata.
						if (this->SafeFunc && MDIsStackAccessOpnd(DefOp, this->UseFP)
							&& (!this->WritesAboveLocalFrame(DefOp))
							&& (!this->WritesToOutgoingArgs(DefOp))) {
							++CurrDef;
							SafeMemDest = true;
							continue;
						}
						CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_USED);
						changed = true;
						MDExtractAddressFields(DefOp, BaseReg, IndexReg,
							ScaleFactor, offset);
						if (R_none != BaseReg) {
							BaseOp.reg = MDCanonicalizeSubReg((ushort) BaseReg);
							if (BaseOp.is_reg(R_sp) 
								|| (this->UseFP && BaseOp.is_reg(R_bp))) {
								; // do nothing; DEF handled by case above
							}
							else {
								CurrUse = CurrInst->FindUse(BaseOp);
								if (CurrUse == CurrInst->GetLastUse()) {
									msg("ERROR: BaseReg %d not in USE list at %x for %s\n",
										BaseOp.reg, CurrInst->GetAddr(),
										CurrInst->GetDisasm());
								}
								assert(CurrUse != CurrInst->GetLastUse());
								if (this->IsGlobalName(BaseOp)) {
									changed |= this->PropagateGlobalMetadata(BaseOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
								else {
									changed |= CurrInst->GetBlock()->PropagateLocalMetadata(BaseOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
							}
						} // end if R_none != BaseReg
						if (R_none != IndexReg) {
							IndexOp.reg = MDCanonicalizeSubReg((ushort) IndexReg);
							if (IndexOp.is_reg(R_sp) 
								|| (this->UseFP && IndexOp.is_reg(R_bp))) {
								; // do nothing; DEF handled by case above
							}
							else {
								CurrUse = CurrInst->FindUse(IndexOp);
								if (CurrUse == CurrInst->GetLastUse()) {
									msg("ERROR: IndexReg %d not in USE list at %x for %s\n",
										IndexOp.reg, CurrInst->GetAddr(),
										CurrInst->GetDisasm());
								}
								assert(CurrUse != CurrInst->GetLastUse());
								if (0 != ScaleFactor) {
									; // mmStrata knows scaled reg is NUMERIC
									// ... its metadata is not fetched
								}
								else if (this->IsGlobalName(IndexOp)) {
									changed |= this->PropagateGlobalMetadata(IndexOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
								else {
									changed |= CurrInst->GetBlock()->PropagateLocalMetadata(IndexOp,
										DEF_METADATA_USED, CurrUse->GetSSANum());
								}
							}
						} // end if R_none != IndexReg
					} // end if X86_FLAGS_REG .. else if stack ptr ... 
				} // end if unanalyzed metadata usage
				++CurrDef;
			} // end while processing DEFs
			if ((RETURN == CurrInst->GetDataFlowType())
				|| (CurrInst->IsTailCall())   // quasi-return
				|| (CALL == CurrInst->GetDataFlowType())
				|| (INDIR_CALL == CurrInst->GetDataFlowType())) {
				// The EAX and EDX registers can be returned to the caller,
				//  which might use their metadata. They show up as USEs
				//  of the return instruction. Some library functions
				//  pass return values in non-standard ways. e.g. through
				//  EBX or EDI, so we treat all return regs the same.
				// For CALL instructions, values can be passed in caller-saved
				//  registers, unfortunately, so the metadata is live-in.
				CurrUse = CurrInst->GetFirstUse();
				while (CurrUse != CurrInst->GetLastUse()) {
					NextUse = CurrUse;
					++NextUse;
					ReturnOp = CurrUse->GetOp();
					if (DebugFlag) {
						msg("ReturnOp: ");
						PrintOperand(ReturnOp);
						msg("\n");
					}
					if ((o_reg == ReturnOp.type) &&
						(!ReturnOp.is_reg(X86_FLAGS_REG))) {
						if (this->IsGlobalName(ReturnOp)) {
							changed |= this->PropagateGlobalMetadata(ReturnOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(ReturnOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
					}
					CurrUse = NextUse;
				} // end while all USEs
			} // end if return or call
			else if (CurrInst->HasDestMemoryOperand() 
				|| CurrInst->MDIsPushInstr()) {
				// Memory writes cause a lot of metadata usage.
				//  Addressing registers in the memory destination
				//  have live metadata used in bounds checking. The
				//  register being stored to memory could end up being
				//  used in some other bounds checking, unless we 
				//  have precise memory tracking and know that it
				//  won't.
				// We handled the addressing registers above, so we
				//  handle the register written to memory here.
				// The same exception applies as above: If the destination
				//  memory operand is not a stack write, then safe functions
				//  do not need to track the metadata.
				if (SafeMemDest) {
					continue;  // go to next instruction
				}
				CurrUse = CurrInst->GetFirstUse();
				while (CurrUse != CurrInst->GetLastUse()) {
					NextUse = CurrUse;
					++NextUse;
					UseOp = CurrUse->GetOp();
					// NOTE: **!!** To be less conservative, we
					//  should propagate less for exchange category
					//  instructions.
					if ((UseOp.type == o_reg) && (!UseOp.is_reg(R_sp))
						&& (!(this->UseFP && UseOp.is_reg(R_bp)))
						&& (!UseOp.is_reg(X86_FLAGS_REG))) {

						if (this->IsGlobalName(UseOp)) {
							changed |= this->PropagateGlobalMetadata(UseOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
						else {
							changed |= CurrInst->GetBlock()->PropagateLocalMetadata(UseOp,
									DEF_METADATA_USED, CurrUse->GetSSANum());
						}
					} // end if register
					CurrUse = NextUse;
				} // end while all USEs
			} // end if call or return else if memdest ...
		} // end for all instructions
	} while (changed);

	// All DEFs that still have status DEF_METADATA_UNANALYZED can now
	//  be marked as DEF_METADATA_UNUSED.
	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
		if (NN_fnop == CurrInst->GetCmd().itype)
			continue;
		CurrDef = CurrInst->GetFirstDef();
		while (CurrDef != CurrInst->GetLastDef()) {
			if (DEF_METADATA_UNANALYZED == CurrDef->GetMetadataStatus()) {
				CurrDef = CurrInst->SetDefMetadata(CurrDef->GetOp(),
					DEF_METADATA_UNUSED);
				assert(CurrDef != CurrInst->GetLastDef());
			}
			++CurrDef;
		}
	}

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

// Propagate the metadata Status for UseOp/SSANum to its global DEF.
// Return true if successful.
bool SMPFunction::PropagateGlobalMetadata(op_t UseOp, SMPMetadataType Status, int SSANum) {
	bool changed = false;

	if ((0 > SSANum) || (o_void == UseOp.type))
		return false;

	// Find the DEF of UseOp with SSANum.
	bool FoundDef = false;
	list<SMPInstr>::iterator CurrInst;

	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
		set<DefOrUse, LessDefUse>::iterator CurrDef;
		set<DefOrUse, LessDefUse>::iterator CurrUse;
		CurrDef = CurrInst->FindDef(UseOp);
		if (CurrDef != CurrInst->GetLastDef()) {
			if (SSANum == CurrDef->GetSSANum()) {
				FoundDef = true;
				if (Status != CurrDef->GetMetadataStatus()) {
					CurrDef = CurrInst->SetDefMetadata(UseOp, Status);
					changed = (CurrDef != CurrInst->GetLastDef());

					// If source operand was memory, we have two cases.
					//  (1) The instruction could be a load, in which
					//  case we should simply terminate the
					//  propagation, because the prior DEF of a memory
					//  location is always considered live metadata
					//  already, and we do not want to propagate liveness
					//  to the address regs in the USE list.
					//  EXCEPTION: For safe funcs, we propagate liveness
					//   for stack locations.
					//  (2) We could have an arithmetic operation such
					//  as reg := reg arithop memsrc. In this case, we
					//  still do not want to propagate through the memsrc,
					//  (with the same safe func EXCEPTION),
					//  but the register is both DEF and USE and we need
					//  to propagate through the register.
					if (CurrInst->HasSourceMemoryOperand()) {
						if (this->SafeFunc) {
							op_t MemSrcOp = CurrInst->MDGetMemUseOp();
							assert(o_void != MemSrcOp.type);
							if (MDIsStackAccessOpnd(MemSrcOp, this->UseFP)) {
								// We have a SafeFunc stack access. This is
								//  the EXCEPTION case where we want to
								//  propagate metadata liveness for a memory
								//  location.
								CurrUse = CurrInst->FindUse(MemSrcOp);
								assert(CurrUse != CurrInst->GetLastUse());
								if (this->IsGlobalName(MemSrcOp)) {
									changed |= this->PropagateGlobalMetadata(MemSrcOp,
										Status, CurrUse->GetSSANum());
								}
								else {
									changed |= CurrInst->GetBlock()->PropagateLocalMetadata(MemSrcOp,
										Status, CurrUse->GetSSANum());
								}
							} // end if stack access operand
						} // end if SafeFunc
						if (3 == CurrInst->GetOptType()) { // move inst
							break; // load address regs are not live metadata
						}
						else if ((5 == CurrInst->GetOptType())
							|| (NN_and == CurrInst->GetCmd().itype)
							|| (NN_or == CurrInst->GetCmd().itype)
							|| (NN_xor == CurrInst->GetCmd().itype)) {
							// add, subtract, and, or with memsrc
							// Find the DEF reg in the USE list.
							CurrUse = CurrInst->FindUse(UseOp);
							assert(CurrUse != CurrInst->GetLastUse());
							changed |= this->PropagateGlobalMetadata(UseOp,
								Status, CurrUse->GetSSANum());
							break;
						}
					} // end if memory source

					// Now, propagate the metadata status to all the
					//  non-memory, non-flags-reg, non-special-reg 
					//  (i.e. regular registers) USEs.
					CurrUse = CurrInst->GetFirstUse();
					while (CurrUse != CurrInst->GetLastUse()) {
						op_t UseOp = CurrUse->GetOp();
						// NOTE: **!!** To be less conservative, we
						//  should propagate less for exchange category
						//  instructions.
						if ((UseOp.type == o_reg) && (!UseOp.is_reg(R_sp))
							&& (!(this->UseFP && UseOp.is_reg(R_bp)))
							&& (!UseOp.is_reg(X86_FLAGS_REG))) {

							if (this->IsGlobalName(UseOp)) {
								changed |= this->PropagateGlobalMetadata(UseOp,
									Status, CurrUse->GetSSANum());
							}
							else {
								changed |= CurrInst->GetBlock()->PropagateLocalMetadata(UseOp,
									Status, CurrUse->GetSSANum());
							}
						}
						++CurrUse;
					} // end while all USEs
				}
				break;
			}
		}
	}

	if (!FoundDef) {
		// Check the Phi functions
		list<SMPBasicBlock>::iterator CurrBlock;
		for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
			set<SMPPhiFunction, LessPhi>::iterator DefPhi;
			DefPhi = CurrBlock->FindPhi(UseOp);
			if (DefPhi != CurrBlock->GetLastPhi()) {
				if (SSANum == DefPhi->GetDefSSANum()) {
					if (Status != DefPhi->GetDefMetadata()) {
						DefPhi = CurrBlock->SetPhiDefMetadata(UseOp, Status);
						changed = true;
						// If the Phi DEF has live metadata, then the Phi
						//  USEs each have live metadata. Propagate.
						int UseSSANum;
						for (size_t index = 0; index < DefPhi->GetPhiListSize(); ++index) {
							UseSSANum = DefPhi->GetUseSSANum(index);
							// UseSSANum can be -1 in some cases because
							//  we conservatively make EAX and EDX be USEs
							//  of all return instructions, when the function
							//  might have a void return type, making it
							//  appear as if an uninitialized EAX or EDX
							//  could make it to the return block.
							if (0 <= UseSSANum) {
								changed |= this->PropagateGlobalMetadata(UseOp,
									Status, UseSSANum);
							}
						}
					}
					FoundDef = true;
					break;
				}
			}
		} // end for all blocks
	} // end if !FoundDef

	if (!FoundDef) {
		msg("ERROR: Could not find DEF of SSANum %d for: ", SSANum);
		PrintOperand(UseOp);
		msg(" in function %s\n", this->GetFuncName());
	}

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

// Find consecutive DEFs of the same type and mark the second one redundant.
void SMPFunction::FindRedundantMetadata(void) {
	list<SMPBasicBlock>::iterator CurrBlock;
	bool changed = false;

	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		changed |= CurrBlock->FindRedundantLocalMetadata(this->SafeFunc);
	}
	return;
} // end of SMPFunction::FindRedundantMetadata()

// 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) msg("Computing IDoms.\n");
	this->ComputeIDoms();
	if (DebugFlag) msg("Computing Dom frontiers.\n");
	this->ComputeDomFrontiers();
	if (DebugFlag) msg("Computing global names.\n");
	this->ComputeGlobalNames();
	if (DebugFlag) msg("Computing blocks defined in.\n");
	this->ComputeBlocksDefinedIn();

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

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

		if (DebugFlag) msg("Computing global chains.\n");
		CurrBlock->CreateGlobalChains();

#if 1
		if (DebugFlag) msg("Marking dead registers.\n");
		CurrBlock->MarkDeadRegs();
#endif
	}
#if SMP_DEBUG_DATAFLOW
	if (DumpFlag)
		this->Dump();
#endif
	return;
} // end of SMPFunction::ComputeSSA()

// 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 CurrBlock;
	for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
		list<list<SMPInstr>::iterator>::iterator CurrInst;
		for (CurrInst = CurrBlock->GetFirstInstr();
			CurrInst != CurrBlock->GetLastInstr();
			++CurrInst) {
			if ((*CurrInst)->HasIndirectMemoryWrite()) {
				CurrBlock->MarkIndWriteChains((*CurrInst)->GetAddr());
				// 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.
	list<SMPInstr>::iterator CurrInst;
	bool FoundIndWrite = false;
	for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
		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);
				break; // Don't waste time after first alias found
			}
		} // 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(list<SMPInstr>::iterator CurrInst, op_t DefOp, int SSANum) {
	bool DebugFlag = false;
	if (0 == strcmp("sdissect", this->GetFuncName())) {
		// Next line is just a good place to set a break point.
		DebugFlag = true;
	}

	// 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();
	// Case 1: Local name. Return the IndWrite flag for the local Def-Use
	//  chain begun by CurrInst.
	if (CurrBlock->IsLocalName(DefOp)) {
		return CurrBlock->GetLocalDUChainIndWrite(DefOp, SSANum);
	}

	// Case 2: Global name.
	// 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;
	}

	// 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<list<SMPBasicBlock>::iterator>::iterator SuccBlock;
	SuccBlock = CurrBlock->GetFirstSucc();
	bool FoundAliasedWrite = false;
	do {
		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 CurrBlock, op_t DefOp) {
	bool DebugFlag = false;
	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 {
			// 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<list<SMPBasicBlock>::iterator>::iterator SuccBlock;
			SuccBlock = CurrBlock->GetFirstSucc();
			bool FoundAliasedWrite = false;
			while (!FoundAliasedWrite && (SuccBlock != CurrBlock->GetLastSucc())) {
				FoundAliasedWrite = this->FindChainAliasHelper((*SuccBlock), DefOp);
				++SuccBlock;
			};

			if (DebugFlag) {
				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 CurrBlock;
#if SMP_DEBUG_DATAFLOW_VERBOSE
	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_VERBOSE
	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()));
		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 IndirCallFlag = (INDIR_CALL == CurrInst->GetDataFlowType());
		bool TailCallFlag = CondTailCall && CurrInst->IsCondTailCall();
		bool IndirJumpFlag = (INDIR_JUMP == CurrInst->GetDataFlowType());
		xrefblk_t CurrXrefs;
		bool LinkedToTarget = false;
		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 || IndirCallFlag || TailCallFlag) 
						&& (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);
						LinkedToTarget = true;
#if SMP_USE_SWITCH_TABLE_INFO
						if (IndirJumpFlag) {
#if SMP_DEBUG_SWITCH_TABLE_INFO
							msg("Switch table link: jump at %x target at %x\n",
								CurrInst->GetAddr(), CurrXrefs.to);
#else
							;
#endif
						}
#endif
					}
				}
		} // end for all xrefs
		if (IndirJumpFlag && (!LinkedToTarget)) {
			this->UnresolvedIndirectJumps = true;
			msg("WARNING: Unresolved indirect jump at %x\n", CurrInst->GetAddr());
		}
		else if (IndirCallFlag && (!LinkedToTarget)) {
			this->UnresolvedIndirectCalls = true;
			msg("WARNING: Unresolved indirect call at %x\n", CurrInst->GetAddr());
		}
	} // 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. 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.
	// NOTE: An odd new gcc recursion optimization uses indirect calls within the function, so
	//  they can behave like indirect jumps.
#if SMP_USE_SWITCH_TABLE_INFO
	if (!(this->HasUnresolvedIndirectJumps() || this->HasUnresolvedIndirectCalls())) {
#else
	if (!(this->HasIndirectJumps() || this->HasIndirectCalls())) {
#endif
		bool changed;
		bool NoPredecessors;
		bool OnlyPredIsItself;
		list<list<SMPBasicBlock>::iterator>::iterator CurrPred;
		do {
			changed = false;
			CurrBlock = this->Blocks.begin();
			++CurrBlock; // don't delete the top block, no matter what.
			while (CurrBlock != this->Blocks.end()) {
				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())
						msg("Removing all nops block at %x\n", CurrBlock->GetFirstAddr());
					else
						msg("Removing block with no predecessors at %x\n", CurrBlock->GetFirstAddr());
					// Remove this block from the predecessors list of its successors.
					list<list<SMPBasicBlock>::iterator>::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<list<SMPInstr>::iterator>::iterator InstIter;
					for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
						list<SMPInstr>::iterator DummyIter = this->Instrs.erase(*InstIter);
					}
					// Finally, remove the block from the blocks list.
					CurrBlock = this->Blocks.erase(CurrBlock);
					this->BlockCount -= 1;
					changed = true;
				}
				else
					++CurrBlock;
			} // end while all blocks after the first one
		} while (changed);
	} // end if not indirect jumps

	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) msg("Entered RPONumberBlocks\n");
#endif
	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);
#if SMP_DEBUG_DATAFLOW
			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;