SMPInstr.cpp

// Is opcode a shift or rotate?
// NOTE: We omit MMX/SSE unit shifts that do not use a general purpose
//  register as a shift counter, because right now this method is only
//  used as a helper for IsSubRegUsedAsShiftCount().
bool SMPInstr::MDIsShiftOrRotate(void) const {
	return (((NN_rcl <= SMPcmd.itype) && (NN_ror >= SMPcmd.itype))
		|| ((NN_sal <= SMPcmd.itype) && (NN_shr >= SMPcmd.itype))
		|| (NN_shld == SMPcmd.itype) || (NN_shrd == SMPcmd.itype));
} // end of SMPInstr::MDIsShiftOrRotate()

// Does the shift or rotate RTL move the upper HalfBitWidth bits
//  into the lower half of the register?
bool SMPInstr::ShiftMakesUpperBitsLower(size_t HalfBitWidth) {
	bool FullCircle = false;

	if (MD_NORMAL_MACHINE_BITWIDTH == (HalfBitWidth * 2)) {
		SMPRegTransfer *CurrRT = this->RTL.GetRT(0);
		if ((NULL != CurrRT) && (CurrRT->HasRightSubTree())) {
			CurrRT = CurrRT->GetRightTree();
			SMPoperator CurrOper =  CurrRT->GetOperator();
			if ((SMP_U_RIGHT_SHIFT == CurrOper) || (SMP_S_RIGHT_SHIFT == CurrOper)
				|| (SMP_ROTATE_LEFT == CurrOper) || (SMP_ROTATE_RIGHT == CurrOper)) {
				if (CurrRT->HasRightSubTree()) { // double-word shift
					CurrRT = CurrRT->GetRightTree();
				}
				assert(!(CurrRT->HasRightSubTree()));
				op_t ShiftCount = CurrRT->GetRightOperand();
				if (o_imm == ShiftCount.type) {
					uval_t ImmVal = ShiftCount.value;
					if (ImmVal == HalfBitWidth) {
						FullCircle = true;
					}
				}
			}
		}
	}
	return FullCircle;
} // SMPInstr::ShiftMakesUpperBitsLower()

// Set the type of all immediate operands found in the USE set.
// Set all flags and floating point register USEs and DEFs to NUMERIC also.
void SMPInstr::SetImmedTypes(bool UseFP) {
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	op_t UseOp;
	op_t DefOp;
	uval_t ImmVal;
	bool DebugFlag = false;
#if SMP_VERBOSE_DEBUG_BUILD_RTL
	DebugFlag = DebugFlag || (this->address == 0x805cd52) || (this->address == 0x805cd56);
	DebugFlag |= (0 == strncmp("__libc_csu_fini", this->BasicBlock->GetFunc()->GetFuncName(), 15));
#endif

	CurrUse = this->GetFirstUse();
	while (CurrUse != this->GetLastUse()) {
		UseOp = CurrUse->GetOp();
		if (DebugFlag) {
			msg("SetImmedTypes USE: ");
			PrintOperand(UseOp);
			msg("\n");
		}
		if (o_imm == UseOp.type) {
			ImmVal = UseOp.value;
			if (IsImmedGlobalAddress((ea_t) ImmVal)) {
				if (DebugFlag) msg("Setting to GLOBALPTR\n");
				CurrUse = this->SetUseType(UseOp, GLOBALPTR);
			}
#if 0
			else if (IsDataAddress((ea_t) ImmVal)) {
				// NOTE: We must call IsDataAddress() before we call IsImmedCodeAddress()
				//  to catch the data addresses within the code address range.
				if (DebugFlag) msg("Setting to POINTER\n");
				CurrUse = this->SetUseType(UseOp, POINTER);
			}
#endif
			else if (this->MDIsInterruptCall() || IsImmedCodeAddress((ea_t) ImmVal)) {
				if (DebugFlag) msg("Setting to CODEPTR\n");
				CurrUse = this->SetUseType(UseOp, CODEPTR);
			}
			else { // NUMERIC
				if (DebugFlag) msg("Setting to NUMERIC\n");
				CurrUse = this->SetUseType(UseOp, NUMERIC);
			}
		}
		else if (o_reg == UseOp.type) {
			if (UseOp.is_reg(X86_FLAGS_REG)) {
				if (DebugFlag) msg("Setting flags reg to NUMERIC\n");
				CurrUse = this->SetUseType(UseOp, NUMERIC);
			}
#if 1
			else if (UseOp.is_reg(R_sp) || (UseFP && UseOp.is_reg(R_bp))) {
				if (DebugFlag) msg("Setting reg to STACKPTR\n");
				CurrUse = this->SetUseType(UseOp, STACKPTR);
			}
#endif
		}
#if 0  // could these registers have pointers in them?
		else if ((o_trreg == UseOp.type) ||(o_dbreg == UseOp.type) || (o_crreg == UseOp.type)) {
			if (DebugFlag) msg("Setting special reg to NUMERIC\n");
			CurrUse = this->SetUseType(UseOp, NUMERIC);
		}
#endif
		else if ((o_fpreg == UseOp.type) || (o_mmxreg == UseOp.type) || (o_xmmreg == UseOp.type)) {
			if (DebugFlag) msg("Setting floating point reg to NUMERIC\n");
			CurrUse = this->SetUseType(UseOp, NUMERIC);
		}
		else if ((o_mem == UseOp.type) || (o_phrase == UseOp.type) || (o_displ == UseOp.type)) {
			// For memory operands, we need to identify the POINTER value that
			//  is used in the addressing mode, if possible.
			(void) this->MDFindPointerUse(UseOp, UseFP);
		}
		++CurrUse;
	} // end while all USEs via CurrUse

	CurrDef = this->GetFirstDef();
	while (CurrDef != this->GetLastDef()) {
		DefOp = CurrDef->GetOp();
		if (DebugFlag) {
			msg("SetImmedTypes DEF: ");
			PrintOperand(DefOp);
			msg("\n");
		}
		if (DebugFlag) msg("FuncName: %s\n", this->BasicBlock->GetFunc()->GetFuncName());
		if (o_reg == DefOp.type) {
			if (DefOp.is_reg(X86_FLAGS_REG)) {
				if (DebugFlag) msg("Setting flags reg DEF to NUMERIC\n");
				CurrDef = this->SetDefType(DefOp, NUMERIC);
				// No need to propagate this DEF type, as all flags will become NUMERIC.
			}
#if 1
			else if (DefOp.is_reg(R_sp) || (DefOp.is_reg(R_bp) && UseFP)) {
				if (DebugFlag) msg("Setting reg DEF to STACKPTR\n");
				CurrDef = this->SetDefType(DefOp, STACKPTR);
				assert(CurrDef != this->Defs.GetLastRef());
				// No need to propagate; all stack and frame pointers will become STACKPTR.
			}
#endif
		}
		else if ((o_fpreg == DefOp.type) || (o_mmxreg == DefOp.type) || (o_xmmreg == DefOp.type)) {
			if (DebugFlag) msg("Setting floating point reg DEF to NUMERIC\n");
			CurrDef = this->SetDefType(DefOp, NUMERIC);
			// No need to propagate; all FP reg uses will become NUMERIC anyway.
		}
#if 0  // could these registers have pointers in them?
		else if ((o_trreg == DefOp.type) || (o_dbreg == DefOp.type) || (o_crreg == DefOp.type)) {
			if (DebugFlag) msg("Setting special reg DEF to NUMERIC\n");
			CurrDef = this->SetDefType(DefOp, NUMERIC);
		}
#endif	
		else if ((o_mem == DefOp.type) || (o_phrase == DefOp.type) || (o_displ == DefOp.type)) {
			// For memory operands, we need to identify the POINTER value that
			//  is used in the addressing mode, if possible.
			(void) this->MDFindPointerUse(DefOp, UseFP);
		}
		++CurrDef;
	} // end while all DEFs via CurrDef
	return;
} // end of SMPInstr::SetImmedTypes()

// Is the instruction a load from the stack?
void SMPInstr::MDFindLoadFromStack(bool UseFP) {
	set<DefOrUse, LessDefUse>::iterator UseIter;
	op_t UseOp;

	if ((3 == this->OptType) && (this->HasSourceMemoryOperand())) {
		// Loads and stores are OptCategory 3. We want only loads from the stack.
		for (UseIter = this->GetFirstUse(); UseIter != this->GetLastUse(); ++UseIter) {
			UseOp = UseIter->GetOp();
			if (MDIsStackAccessOpnd(UseOp, UseFP)) {
				this->SetLoadFromStack();
				break;
			}
		}
	}
	return;
} // end of SMPInstr::MDFindLoadFromStack()

// Determine if instr is inherently signed load instruction.
//  True if sign or zero-extended; pass out mask bits if true.
bool SMPInstr::MDIsSignedLoad(unsigned short &SignMask) {
	unsigned short opcode = this->SMPcmd.itype;
	if (NN_movzx == opcode) {
		SignMask = FG_MASK_UNSIGNED;
	}
	else if (NN_movsx == opcode) {
		SignMask = FG_MASK_SIGNED;
	}
	else {
		return false;
	}
	return true;
}

// Infer sign, bit width, other type info for simple cases where all the info needed is
//  within the instruction or can be read from the FineGrainedStackTable in the SMPFunction.
// NOTE: Must be called after SSA analysis is complete.
void SMPInstr::MDSetWidthSignInfo(bool UseFP) {
	set<DefOrUse, LessDefUse>::iterator UseIter;
	set<DefOrUse, LessDefUse>::iterator DefIter;
	op_t UseOp, DefOp;
	struct FineGrainedInfo FGEntry;
	bool ValueWillChange;
	unsigned short SignMask, TempSign, WidthMask;
	int DefHashValue, UseHashValue;
	ea_t DefAddr;  // for flags USE in conditional set
	int SSANum;    // for flags USE in conditional set
	bool LocalFlags;  // is flags register a local name?
	bool case1, case2, case3, case4, case5, case6;
	bool SignedSetOpcode = this->MDIsSignedSetValue();
	bool UnsignedSetOpcode = this->MDIsUnsignedSetValue();

	case1 = this->IsLoadFromStack();
	case2 = this->MDIsSignedLoad(SignMask); // sets value of SignMask if it returns true
	case3 = (7 == this->OptType);  // Multiplies and divides
	case4 = ((CALL == this->GetDataFlowType()) || (INDIR_CALL == this->GetDataFlowType()));
	case5 = (SignedSetOpcode || UnsignedSetOpcode); // set boolean based on flag condition
	case6 = this->MDDoublesWidth(); // convert byte to word, word to dword, etc.

	// Case 1: Load from stack location.
	if (case1) {
		bool success = false;
		for (UseIter = this->GetFirstUse(); UseIter != this->GetLastUse(); ++UseIter) {
			UseOp = UseIter->GetOp();
			if (MDIsStackAccessOpnd(UseOp, UseFP)) {
				// Found the stack location being loaded into a register. Now we need
				//  to get the sign and width info from the fine grained stack frame
				//  analysis.
				success = this->GetBlock()->GetFunc()->MDGetFGStackLocInfo(this->address, UseOp, FGEntry);
				assert(success);
				// Now we have signedness info in FGEntry. We need to OR it into the register target of the load.
				if (FGEntry.SignMiscInfo == 0) 
					break; // nothing to OR in; save time
				for (DefIter = this->GetFirstDef(); DefIter != this->GetLastDef(); ++DefIter) {
					DefOp = DefIter->GetOp();
					if (o_reg == DefOp.type) {
						DefOp.reg = MDCanonicalizeSubReg(DefOp.reg);
						TempSign = FGEntry.SignMiscInfo & FG_MASK_SIGNEDNESS_BITS; // Get both sign bit flags
						DefHashValue = HashGlobalNameAndSSA(DefOp, DefIter->GetSSANum());
						if (this->BasicBlock->IsLocalName(DefOp)) {
							this->BasicBlock->UpdateDefSignMiscInfo(DefHashValue, TempSign);
						}
						else {
							this->BasicBlock->GetFunc()->UpdateDefSignMiscInfo(DefHashValue, TempSign);
						}
						break;  // Should be only one register target for stack load, and no flags are set.
					}
				}
				break; // Only concerned with the stack operand
			}
		}
		assert(success);
	} // end if this->IsLoadFromStack()

	// Case 2: Loads that are sign-extended or zero-extended imply signed and unsigned, respectively.
	//  NOTE: If from the stack, they were handled in Case 1, and the signedness of the stack location
	//  was recorded a long time ago in SMPFunction::FindOutgoingArgsSize();
	else if (case2) {
		DefIter = this->GetFirstDef();
		while (DefIter != this->GetLastDef()) {
			// All non-memory DEFs besides the flags register should get the new SignMask ORed in.
			// On x86, there should only be one DEF for this move, and no flags, but we will generalize
			//  in case other architectures are odd.
			DefOp = DefIter->GetOp();
			if (!(IsMemOperand(DefOp) || MDIsFlagsReg(DefOp))) {
				DefOp.reg = MDCanonicalizeSubReg(DefOp.reg);
				DefHashValue = HashGlobalNameAndSSA(DefOp, DefIter->GetSSANum());
				if (this->BasicBlock->IsLocalName(DefOp)) {
					this->BasicBlock->UpdateDefSignMiscInfo(DefHashValue, SignMask);
				}
				else {
					this->BasicBlock->GetFunc()->UpdateDefSignMiscInfo(DefHashValue, SignMask);
				}
			}
			++DefIter;
		}

		// If the signed load is from memory, the only USEs are the memory
		//  operand and addressing registers. We do not want to claim that
		//  EBX is signed in the instruction movsx eax,[ebx]. Only the DEF
		//  register EAX and the memory location [EBX] are signed, and we
		//  have no idea where [EBX] is, so we punt on all USEs if we have
		//  a memory source operand.
		if (!(this->HasSourceMemoryOperand())) {
			UseIter = this->GetFirstUse();
			while (UseIter != this->GetLastUse()) {
				// All non-memory USEs besides the flags register should get the new SignMask ORed in.
				UseOp = UseIter->GetOp();
				if (!(IsMemOperand(UseOp) || MDIsFlagsReg(UseOp))) {
					UseOp.reg = MDCanonicalizeSubReg(UseOp.reg);
					UseHashValue = HashGlobalNameAndSSA(UseOp, UseIter->GetSSANum());
					if (this->BasicBlock->IsLocalName(UseOp)) {
						this->BasicBlock->UpdateUseSignMiscInfo(UseHashValue, SignMask);
					}
					else {
						this->BasicBlock->GetFunc()->UpdateUseSignMiscInfo(UseHashValue, SignMask);
					}
				}
				++UseIter;
			}
		}
	} // end of case 2

	// Case 3: multiplies and divides can be signed or unsigned.
	else if (case3) { // Multiplies and divides are type 7.
		if (this->MDIsSignedArithmetic()) {
			SignMask = FG_MASK_SIGNED;
		}
		else if (this->MDIsUnsignedArithmetic()) {
			SignMask = FG_MASK_UNSIGNED;
		}
		else {
			SignMask = 0; // unknown, uninitialized
		}
		if (0 != SignMask) {
			DefIter = this->GetFirstDef();
			while (DefIter != this->GetLastDef()) {
				// All DEFs besides the flags register should get the new SignMask ORed in.
				DefOp = DefIter->GetOp();
				if ((DefOp.type == o_reg) && (!(DefOp.is_reg(X86_FLAGS_REG)))) {
					DefOp.reg = MDCanonicalizeSubReg(DefOp.reg);
					DefHashValue = HashGlobalNameAndSSA(DefOp, DefIter->GetSSANum());
					if (this->BasicBlock->IsLocalName(DefOp)) {
						this->BasicBlock->UpdateDefSignMiscInfo(DefHashValue, SignMask);
					}
					else {
						this->BasicBlock->GetFunc()->UpdateDefSignMiscInfo(DefHashValue, SignMask);
					}
				}
				++DefIter;
			}

			UseIter = this->GetFirstUse();
			while (UseIter != this->GetLastUse()) {
				// All USEs besides the flags register should get the new SignMask ORed in.
				UseOp = UseIter->GetOp();
				if ((UseOp.type == o_reg) && (!(UseOp.is_reg(X86_FLAGS_REG)))) {
					UseOp.reg = MDCanonicalizeSubReg(UseOp.reg);
					UseHashValue = HashGlobalNameAndSSA(UseOp, UseIter->GetSSANum());
					if (this->BasicBlock->IsLocalName(UseOp)) {
						this->BasicBlock->UpdateUseSignMiscInfo(UseHashValue, SignMask);
					}
					else {
						this->BasicBlock->GetFunc()->UpdateUseSignMiscInfo(UseHashValue, SignMask);
					}
				}
				++UseIter;
			}
		} // end if (0 != SignMask)
	} // end of case 3 (multiplies and divides)

	// Case 4: Calls to library functions can reveal the type of the return register.
	else if (case4) {
		// Get name of function called.
		string FuncName = this->GetTrimmedCalledFunctionName();

		// Get FG info, if any, for called function.
		GetLibFuncFGInfo(FuncName, FGEntry);

		// See if anything was returned in FGEntry.
		if ((FGEntry.SignMiscInfo != 0) || (FGEntry.SizeInfo != 0)) {
			// Need to update the FG info for the DEF of the return register.
			DefOp = InitOp;
			DefOp.type = o_reg;
			DefOp.reg = MD_RETURN_VALUE_REG;
			DefIter = this->FindDef(DefOp);
			assert(DefIter != this->GetLastDef());
			DefHashValue = HashGlobalNameAndSSA(DefOp, DefIter->GetSSANum());
			if (this->BasicBlock->IsLocalName(DefOp)) {
				this->BasicBlock->UpdateDefFGInfo(DefHashValue, FGEntry);
			}
			else {
				this->BasicBlock->GetFunc()->UpdateDefFGInfo(DefHashValue, FGEntry);
			}
		}
	} // end of case4 (function calls)
	else if (case5) { // signed or unsigned conditional set opcode
		if (UnsignedSetOpcode) {
			SignMask = FG_MASK_UNSIGNED;
		}
		else {
			assert(SignedSetOpcode);
			SignMask = FG_MASK_SIGNED;
		}
		// Find the flags USE.
		UseOp.type = o_reg; // set up a dummy op for searching
		UseOp.reg = X86_FLAGS_REG;
		UseIter = this->FindUse(UseOp);
		assert(UseIter != this->GetLastUse());
		UseOp = UseIter->GetOp(); // get full info in all fields of UseOp
		SSANum = UseIter->GetSSANum();
		LocalFlags = this->GetBlock()->IsLocalName(UseOp);

		DefAddr = this->GetBlock()->GetDefAddrFromUseAddr(UseOp, this->GetAddr(), SSANum, LocalFlags);
		// Pass DefAddr to recursive helper function to propagate signedness of the set opcode.
		this->GetBlock()->PropagateBranchSignedness(DefAddr, UseOp, SignMask);
	}
	else if (case6) { // sign extend to double the width of USE operand into DEF operand
		DefIter = this->GetFirstNonFlagsDef();
		assert(DefIter != this->GetLastDef());
		DefOp = DefIter->GetOp();
		assert(o_reg == DefOp.type);
		DefOp.reg = MDCanonicalizeSubReg(DefOp.reg);
		SSANum =  DefIter->GetSSANum();
		DefHashValue = HashGlobalNameAndSSA(DefOp, SSANum);
		UseIter = this->GetFirstUse();
		assert(UseIter != this->GetLastUse());
		UseOp = UseIter->GetOp();
		assert(o_reg == UseOp.type);
		UseOp.reg = MDCanonicalizeSubReg(UseOp.reg);
		assert(UseOp.reg == DefOp.reg);
		UseHashValue = HashGlobalNameAndSSA(UseOp, UseIter->GetSSANum()); 
		SignMask = FG_MASK_SIGNED;  // opcodes do sign extension => signed
		// Mark DEF and USE as signed.
		if (this->GetBlock()->IsLocalName(DefOp)) {
			this->GetBlock()->UpdateDefSignMiscInfo(DefHashValue, SignMask);
			this->GetBlock()->UpdateUseSignMiscInfo(UseHashValue, SignMask);
		}
		else {
			this->GetBlock()->GetFunc()->UpdateDefSignMiscInfo(DefHashValue, SignMask);
			this->GetBlock()->GetFunc()->UpdateUseSignMiscInfo(UseHashValue, SignMask);
		}
	}

	// For all register DEFs and USEs, we should get the obvious register width info
	//  updated. Need to use the RTL operands to get accurate widths.
	SMPRegTransfer *CurrRT;
	for (size_t index = 0; index < this->RTL.GetCount(); ++index) {
		CurrRT = this->RTL.GetRT(index);
		DefOp = CurrRT->GetLeftOperand();
		// Avoid setting def width for case 2; we leave it as zero so that
		//  later uses can determine whether the zero-extension or sign-extension
		//  bits ever got used. See more discussion in EmitIntegerErrorAnnotations()
		//  for the CHECK TRUNCATION case.
		// NOTE: case2 can be set to true even in the case1/case2 overlap case that
		//  only passes through the case1 code above. This is intentional. We want
		//  to leave the DEF width set to 0 for all of case2 including the case1 overlap.
		if (!case2) {
			if (MDIsGeneralPurposeReg(DefOp)) {
				WidthMask = ComputeOperandBitWidthMask(DefOp, 0);
				DefOp.reg = MDCanonicalizeSubReg(DefOp.reg);
				DefIter = this->FindDef(DefOp);
				assert(DefIter != this->GetLastDef());
				DefHashValue = HashGlobalNameAndSSA(DefOp, DefIter->GetSSANum());
				if (this->BasicBlock->IsLocalName(DefOp)) {
					this->BasicBlock->UpdateDefWidthTypeInfo(DefHashValue, WidthMask);
				}
				else {
					this->BasicBlock->GetFunc()->UpdateDefWidthTypeInfo(DefHashValue, WidthMask);
				}
			}
		}
		if (CurrRT->HasRightSubTree()) {
			this->MDSetRTLRegWidthInfo(CurrRT->GetRightTree());
		}
		else {
			UseOp = CurrRT->GetRightOperand();
			this->SetRTLUseOpRegWidthInfo(UseOp);
		}
	}  // end for all RTLs 

	return;
} // end of SMPInstr::MDSetWidthSignInfo()

// Infer sign from the SMP types for USEs and DEFs.
void SMPInstr::InferSignednessFromSMPTypes(bool UseFP) {
	// Start with registers only, infer that all kids of pointers are UNSIGNED.
	set<DefOrUse, LessDefUse>::iterator DefIter, UseIter;
	op_t DefOp, UseOp;
	int SSANum;
	int DefHashValue, UseHashValue;
	SMPOperandType DefType, UseType;
	unsigned short DefSignMiscInfo = FG_MASK_UNSIGNED, UseSignMiscInfo = FG_MASK_UNSIGNED;
	bool GlobalName;

	for (DefIter = this->GetFirstDef(); DefIter != this->GetLastDef(); ++DefIter) {
		DefOp = DefIter->GetOp();
		if (MDIsGeneralPurposeReg(DefOp)) {
			DefType = DefIter->GetType();
			if (IsDataPtr(DefType) || (CODEPTR == DefType)) {
				GlobalName = this->BasicBlock->GetFunc()->IsGlobalName(DefOp);
				SSANum = DefIter->GetSSANum();
				DefHashValue = HashGlobalNameAndSSA(DefOp, SSANum);
				if (GlobalName) {
					this->BasicBlock->GetFunc()->UpdateDefSignMiscInfo(DefHashValue, DefSignMiscInfo);
				}
				else {
					this->BasicBlock->UpdateDefSignMiscInfo(DefHashValue, DefSignMiscInfo);
				}
			}
		}
	}

	for (UseIter = this->GetFirstUse(); UseIter != this->GetLastUse(); ++UseIter) {
		UseOp = UseIter->GetOp();
		if (MDIsGeneralPurposeReg(UseOp)) {
			UseType = UseIter->GetType();
			if (IsDataPtr(UseType) || (CODEPTR == UseType)) {
				GlobalName = this->BasicBlock->GetFunc()->IsGlobalName(UseOp);
				SSANum = UseIter->GetSSANum();
				UseHashValue = HashGlobalNameAndSSA(UseOp, SSANum);
				if (GlobalName) {
					this->BasicBlock->GetFunc()->UpdateUseSignMiscInfo(UseHashValue, UseSignMiscInfo);
				}
				else {
					this->BasicBlock->UpdateUseSignMiscInfo(UseHashValue, UseSignMiscInfo);
				}
			}
		}
	}

	return;
} // end of SMPInstr::InferSignednessFromSMPTypes()


// Helper to set width info for a UseOp from an RTL
void SMPInstr::SetRTLUseOpRegWidthInfo(op_t UseOp) {
	unsigned short WidthMask;
	set<DefOrUse, LessDefUse>::iterator UseIter;
	unsigned int UseHashValue;

	if (MDIsGeneralPurposeReg(UseOp)) {
		WidthMask = ComputeOperandBitWidthMask(UseOp, 0);
		UseOp.reg = MDCanonicalizeSubReg(UseOp.reg);
		UseIter = this->FindUse(UseOp);
		assert(UseIter != this->GetLastUse());
		UseHashValue = HashGlobalNameAndSSA(UseOp, UseIter->GetSSANum());
		if (this->BasicBlock->IsLocalName(UseOp)) {
			this->BasicBlock->UpdateUseWidthTypeInfo(UseHashValue, WidthMask);
		}
		else {
			this->BasicBlock->GetFunc()->UpdateUseWidthTypeInfo(UseHashValue, WidthMask);
		}
	}

	return;
} // end of SMPInstr::SetRTLUseOpRegWidthInfo()

// Walk the RTL and update the register USE operands' width info.
void SMPInstr::MDSetRTLRegWidthInfo(SMPRegTransfer *CurrRT) {
	op_t UseOp;

	UseOp = CurrRT->GetLeftOperand();
	this->SetRTLUseOpRegWidthInfo(UseOp);
	if (CurrRT->HasRightSubTree()) {
		this->MDSetRTLRegWidthInfo(CurrRT->GetRightTree());
	}
	else {
		UseOp = CurrRT->GetRightOperand();
		this->SetRTLUseOpRegWidthInfo(UseOp);
	}

	return;
} // end of SMPInstr::MDSetRTLRegWidthInfo()

// Do we not consider truncation on this type of instruction to be an error?
bool SMPInstr::IsBenignTruncation(void) {
	bool benign = false;
	unsigned short SignMask;
	op_t UseOp, SearchOp;

	if (3 == this->GetOptType()) { // Move instruction
		bool ExtendedLoad = this->MDIsSignedLoad(SignMask);
		if (ExtendedLoad) {
			if (SignMask & FG_MASK_UNSIGNED) {
				// We have a zero-extended load. Compilers zero-extend both
				//  signed (unfortunately) and unsigned sub-regs when they know
				//  from the source language types that only the lower bits matter,
				//  e.g. when a char has been stored in the lower bits and regardless
				//  of whether that char was sign-extended or zero-extended previously,
				//  only the char itself is useful info. Otherwise, the compiler could
				//  move the whole register, e.g. instead of edi := zero-extend(cx), the
				//  compiler could have generated edi := ecx. The zero-extension loads
				//  are therefore not good candidates for truncation checks, as they lead
				//  to lots of false positives.
				benign = true;
			}
		}
		else { // Move, and not extended load, which was handled above.
			// Next case: A move instruction whose USE falsely appears to be a truncation,
			//  but in fact the apparently unused portion of the register is used later, e.g.:
			//   mov [ebp-12],ax  ; looks like EAX is being truncated to AX and stored
			//   shr eax,16       ; gets upper 16 bits into lower 16 bits
			//   mov [ebp-14],ax  ; store what used to be the upper 16 bits of EAX
			// The first instruction will trigger a CHECK TRUNCATION annotation that
			//  causes false positives. We need to analyze the context of the instruction
			//  to see that the whole register EAX was used, so no truncation occurred.
			//  The context analysis in the basic block will mark the second move as
			//  a "truncation" that should be ignored, so we check the flag here to short
			//  circuit redundant analysis.
			UseOp = this->GetMoveSource();
			assert(o_void != UseOp.type);
			SearchOp = UseOp;
			if (o_reg == UseOp.type) {
				SearchOp.reg = MDCanonicalizeSubReg(UseOp.reg);
			}
			set<DefOrUse, LessDefUse>::iterator UseIter = this->FindUse(SearchOp);
			assert(UseIter != this->GetLastUse());
			if (UseIter->DoesNotTruncate()) {
				benign = true;
			}
			else {
				set<DefOrUse, LessDefUse>::iterator DefIter = this->GetFirstNonFlagsDef();
				assert(DefIter != this->GetLastDef());
				int DefSSANum = DefIter->GetSSANum();
				benign = this->GetBlock()->IsBenignTruncationDEF(DefIter->GetOp(), DefSSANum, this->GetAddr());
			}
		}
	}
	return benign;
} // end of SMPInstr::IsBenignTruncation()

// Do we not consider overflow or underflow on this type of instruction to be an error?
bool SMPInstr::IsBenignOverflow(void) {
	bool benign = false;
	set<DefOrUse, LessDefUse>::iterator DefIter;
	SMPOperandType DefType;
	int DefSSANum;
	ea_t DefAddr;
	op_t DefOp;

	// 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.
	if (this->MDIsMaybeBenignUnderflowOpcode()) { // might have the subtract instruction
		DefIter = this->GetFirstNonFlagsDef();
		assert(DefIter != this->GetLastDef());
		if (DefIter->DoesNotOverflow()) {
			benign = true; // short circuit; already analyzed
		}
		else {
			DefType = DefIter->GetType();
			if (IsEqType(DefType, NEGATEDPTR)) { // We have candidate subtract instruction
				DefSSANum = DefIter->GetSSANum();
				DefAddr = this->GetAddr();
				DefOp = DefIter->GetOp();
				benign = this->GetBlock()->GetFunc()->IsBenignUnderflowDEF(DefOp, DefSSANum, DefAddr);
			}
		}
	}
	else if (this->MDIsMaybeBenignOverflowOpcode()) { // might have the add instruction
		DefIter = this->GetFirstNonFlagsDef();
		assert(DefIter != this->GetLastDef());
		if (DefIter->DoesNotOverflow()) {
			benign = true; // short circuit; already analyzed
		}
		else { // Bad luck to encounter addition first. See what types tell us.
			if (this->HasNegatedPtrUSE()) { // We have candidate for addition.
				DefType = DefIter->GetType();
				if (IsEqType(DefType, PTROFFSET)) {
					// Current instruction is definitely the addition instruction of some
					//  benignly underflowing and overflowing pair of instructions. It does
					//  not really matter that we have not found the subtraction yet; we will
					//  get to it eventually. We should suppress overflow checks on this inst.
					DefOp = DefIter->GetOp();
					this->Defs.SetNoOverflow(DefOp, true);
					benign = true;
				}
				else {
					// A bit of a quandary. Ideally, we would have successful SMP type inference
					//  and always have PTROFFSET := POINTER + NEGATEDPTR. However, sometimes we
					//  might have ?? := ?? + NEGATEDPTR. The instruction could be of the type
					//  NEGATEDPTR := NUMERIC + NEGATEDPTR, so we cannot just assume here that 
					//  we have detected the benign case. We will be safe and do nothing.
					;
				}
			}
		}
	}

	return benign;
} // end of SMPInstr::IsBenignOverflow()

// Do we detect a situation in which it is safe to check for signedness errors on
//  the stack write (return false), or not (return true to be safe).
bool SMPInstr::SkipSignednessCheckOnStackWrite(int DefSSANum) {
	bool SkipCheck = true;
	op_t StackDefOp = this->DEFMemOp;
	size_t DefBitWidth = 8 * GetOpDataSize(StackDefOp);
	if (DefBitWidth < MD_NORMAL_MACHINE_BITWIDTH) {
		// If we are not dealing with a shortened bit width, then
		//  the next load from the stack will not be sign-extended
		//  or zero-extended.
		if (this->GetBlock()->IsStackOpNextUsedWithSignedness(StackDefOp, this->GetAddr(), DefSSANum)) {
			SkipCheck = false;
		}
	}
	return SkipCheck;
} // end of SMPInstr::SkipSignednessCheckOnStackWrite()

// Does inst pass an outgoing argument?
bool SMPInstr::MDIsArgumentPass(void) {
	bool OutArgPass = false;

	// Current model is writing outargs to stack. For other compiler targets in the
	//  future, we would also include pushes onto the stack.
	if (this->HasDestMemoryOperand() && (this->GetOptType() == 3)) { // move to memory
		if (this->GetBlock()->GetFunc()->OutArgsRegionComputed()) {
			op_t DefOp = this->DEFMemOp;
			OutArgPass = this->GetBlock()->GetFunc()->IsInOutgoingArgsRegion(DefOp);
		}
	}
	return OutArgPass;
}

// Trace UseOp through register moves back to its stack location or immediate value source.
//  Return true if we are passing an immediate or stack location back in UltSource.
bool SMPInstr::TraceUltimateMoveSource(op_t UseOp, int UseSSANum, op_t &UltSource) {
	// If we hit an immediate value or a stack location, we are done.
	bool UseFP = this->GetBlock()->GetFunc()->UsesFramePointer();
	op_t NewUseOp; // next UseOp up the move chain
	op_t DefOp, ImmOp;
	int NewUseSSANum;
	set<DefOrUse,LessDefUse>::iterator UseIter;
	bool LocalName;
	ea_t DefAddr;
	SMPInstr *DefInst;

	UltSource = InitOp;
	bool StackOp = MDIsStackAccessOpnd(UseOp, UseFP);
	bool RegisterOp = (UseOp.type == o_reg);

	if (this->GetOptType() == 3) { // move instruction
		if (UseOp.type == o_imm) {
			UltSource = UseOp;
			return true;
		}
		else if ((!RegisterOp) && (!StackOp)) {
			// We only trace the move chain through registers or stack locations to an ultimate 
			//  load-effective-address of a stack location, or a move of an immediate value.
			return false;
		}
	} 
	else if (!this->MDIsLoadEffectiveAddressInstr()) {
		return false;
	}
	else { // Load effective address instruction.
		// If it is a stack location being loaded, trace succeeded, else it failed.
		if (StackOp) {
			UltSource = UseOp;
			return true;
		}
		else {
			return false;
		}
	}

	// If we reach this point, we have a move instruction but did not return true or false above.

	// Recursion case. Going back up the move chain has just produced a register or
	//  a stack location, and we still need to find the stack address or immediate value
	//  that was stored in the register or stack location. The stack location could hold
	//  a pointer to a stack object, produced by an earlier LEA instruction, or it
	//  could hold an immediate value (e.g. constant size argument passed to memset() or
	//  similar function).
	LocalName = this->GetBlock()->IsLocalName(UseOp);
	DefAddr = this->GetBlock()->GetDefAddrFromUseAddr(UseOp, this->GetAddr(), UseSSANum, LocalName);
	if ((BADADDR == DefAddr) || (DefAddr < (this->GetBlock()->GetFunc()->GetStartAddr() - 1))) {
		// Def was not found, or was found in Phi function (DefAddr was block number, not instruction addr).
		return false;
	}

	// Everything is OK so far; time to recurse up the move chain.
	DefInst = this->GetBlock()->GetFunc()->GetInstFromAddr(DefAddr);
	if (DefInst->GetOptType() == 3) {
		NewUseOp = DefInst->GetMoveSource();
	}
	else if (DefInst->MDIsLoadEffectiveAddressInstr()) {
		NewUseOp = DefInst->GetLeaMemUseOp();
		if (MDIsStackAccessOpnd(NewUseOp, UseFP)) {
			UltSource = NewUseOp;
			return true;
		}
		else {
			return false;
		}
	}
	// We don't have a move instruction or a load effective address instruction, which
	//  can be used to move a stack address into a register. We don't try to trace through
	//  arithmetic except for two easy cases.
	// Case 1: A register is cleared. Same as assigning immediate value zero to the reg.
	else if (DefInst->IsRegClearIdiom()) {
		UltSource.type = o_imm;
		UltSource.value = 0;  // why would we memset a zero byte region?
		return true;
	}
	// Easy arithmetic Case 2: we have reg += ImmediateValue, and reg was DEFed by reg := LEA(StackLoc).
	else if (DefInst->MDIsAddImmediateToReg(DefOp, ImmOp)) {
		SMPInstr *NewDefInst;
		UseIter = DefInst->FindUse(DefOp);
		assert(UseIter != DefInst->GetLastUse());
		NewUseSSANum = UseIter->GetSSANum();
		LocalName = DefInst->GetBlock()->IsLocalName(DefOp);
		DefAddr = DefInst->GetBlock()->GetDefAddrFromUseAddr(DefOp, DefInst->GetAddr(), NewUseSSANum, LocalName);
		if ((BADADDR == DefAddr) || (DefAddr < (DefInst->GetBlock()->GetFunc()->GetStartAddr() - 1))) {
			// Def was not found, or was found in Phi function (DefAddr was block number, not instruction addr).
			return false;
		}
		NewDefInst = DefInst->GetBlock()->GetFunc()->GetInstFromAddr(DefAddr);
		if (NewDefInst->MDIsLoadEffectiveAddressInstr()) {
			NewUseOp = NewDefInst->GetLeaMemUseOp();
			if (MDIsStackAccessOpnd(NewUseOp, UseFP)) {
				// We have the code sequence we were searching for when we first saw the
				//  addition of an immediate value to a register, e.g.:
				//   lea ebx,[ebp-2000]
				//   add ebx,1000
				//
				// We are essentially making this sequence into a single instruction:
				//   lea ebx,[ebp-1000]
				//  by adding the immediate value to the address offset. With a stack that grows
				//  downward, it does not matter if we add 1000 to [esp+500] to produce [esp+1500],
				//  or we add 1000 to [ebp-2000] to make [ebp-1000]. Either way, we are simulating the
				//  addition of 1000 as we move up in the stack frame.
				NewUseOp.addr += ImmOp.value; // perform the address arithmetic addition
				UltSource = NewUseOp;
				return true;
			}
			else {
				return false;
			}
		}
		else {
			return false;
		}
	}
	else {
		// Not the kind of instruction we need; cut short the recursion.
		return false;
	}

	// NewUseOp is the move source operand that we seek.
	UseIter = DefInst->FindUse(NewUseOp);
	assert(UseIter != DefInst->GetLastUse());
	NewUseSSANum = UseIter->GetSSANum();  // unused for immediates, used for regs and stack
	// Recurse
	return DefInst->TraceUltimateMoveSource(NewUseOp, NewUseSSANum, UltSource);

} // end of SMPInstr::TraceUltimateMoveSource()

// Infer DEF, USE, and RTL SMPoperator types within the instruction based on the type
//  of operator, the type category of the instruction, and the previously known types 
//  of the operands.
bool SMPInstr::InferTypes(void) {
	bool changed = false;  // return value
	int SSANum;
	int TypeCategory = SMPTypeCategory[this->SMPcmd.itype];
	set<DefOrUse, LessDefUse>::iterator CurrDef;
	set<DefOrUse, LessDefUse>::iterator CurrUse;
	op_t DefOp = InitOp, UseOp = InitOp;
	bool DebugFlag = false;
	bool UseFP = this->BasicBlock->GetFunc()->UsesFramePointer();
	bool SafeFunc = this->BasicBlock->GetFunc()->IsSafe();
	bool IsMemOp;
#if SMP_VERBOSE_DEBUG_INFER_TYPES
	DebugFlag |= (0 == strcmp("InputMove", this->BasicBlock->GetFunc()->GetFuncName()));
#endif

	if (DebugFlag) {
		msg("opcode: %d TypeCategory: %d\n", this->SMPcmd.itype, TypeCategory);
	}

	// If we are already finished with all types, return false.
	if (this->IsTypeInferenceComplete())
		return false;

	if (this->AllDEFsTyped() && this->AllUSEsTyped()) {
		this->SetTypeInferenceComplete();
		return false;
	}

	if (this->HasDestMemoryOperand()) {
		changed |= this->MDFindPointerUse(this->MDGetMemDefOp(), UseFP);
	}
	if (this->HasSourceMemoryOperand()) {
		changed |= this->MDFindPointerUse(this->MDGetMemUseOp(), UseFP);
	}

	// The control flow instructions can be handled simply based on their type
	//  and do not need an RTL walk.
	SMPitype DFAType = this->GetDataFlowType();
	bool CallInst = ((DFAType == CALL) || (DFAType == INDIR_CALL));
	ushort IndirCallReg = R_none;
	if (DebugFlag) {
		msg("DFAType: %d  CategoryInferenceComplete: %d\n",
			DFAType, this->IsCategoryInferenceComplete());
	}

	if (DFAType == INDIR_CALL) {
		op_t TargetOp = this->SMPcmd.Operands[0];
		if (TargetOp.type == o_reg)
			IndirCallReg = TargetOp.reg;
	}

	if ((DFAType >= JUMP) && (DFAType <= INDIR_CALL)) {
		// All USEs are either the flags (NUMERIC) or the target address (CODEPTR).
		//  The exceptions are the USE list for interrupt calls, which includes
		//  the caller-saved regs, and indirect calls through a memory
		//  operand, such as call [ebx+esi+20h], where the memory operand
		//  is a CODEPTR but the addressing registers are a BaseReg and
		//  IndexReg as in any other memory addressing, and the caller-saved
		//  regs on any call.
		CurrUse = this->GetFirstUse();
		while (CurrUse != this->GetLastUse()) {
			UseOp = CurrUse->GetOp();
			if (UseOp.is_reg(X86_FLAGS_REG))
				CurrUse = this->SetUseType(UseOp, NUMERIC);
			else if ((CurrUse->GetType() != CODEPTR)
				&& (!(this->MDIsInterruptCall() && (o_reg == UseOp.type)))
				&& (!(CallInst && MDIsCallerSavedReg(UseOp)))
				&& (!(this->HasSourceMemoryOperand() 
					&& (INDIR_CALL == this->GetDataFlowType())
					&& (o_reg == UseOp.type)))) {
				CurrUse = this->SetUseType(UseOp, CODEPTR);
				if (DFAType == CALL) {
					// If the call is to malloc(), then the DEF of the return
					//  register is of type HEAPPTR.
					changed |= this->MDFindMallocCall(UseOp);
				}
			}
			else if ((CurrUse->GetType() != CODEPTR) && CallInst
				&& UseOp.is_reg(IndirCallReg)) {

				CurrUse = this->SetUseType(UseOp, CODEPTR);
			}
			++CurrUse;
		}
		this->SetTypeInferenceComplete();
		return true;
	}

	// First, see if we can infer something about DEFs and USEs just from the 
	//  type category of the instruction.
	if (!this->IsCategoryInferenceComplete()) {
		bool MemPropagate = false;
		switch (TypeCategory) {
			case 0: // no inference possible just from type category
			case 1: // no inference possible just from type category
			case 3:  // MOV instructions; inference will come from source to dest in RTL walk.
			case 5:  // binary arithmetic; inference will come in RTL walk.
			case 10:  // binary arithmetic; inference will come in RTL walk.
			case 11:  // push and pop instructions; inference will come in RTL walk.
			case 12:  // exchange instructions; inference will come in RTL walk.
				this->SetCategoryInferenceComplete();
				break;

			case 2: // Result type is always NUMERIC.
			case 7: // Result type is always NUMERIC.
			case 8: // Result type is always NUMERIC.
			case 9: // Result type is always NUMERIC.
			case 13: // Result type is always NUMERIC.
			case 14: // Result type is always NUMERIC.
			case 15: // Result type is always NUMERIC.
				CurrDef = this->GetFirstDef();
				while (CurrDef != this->GetLastDef()) {
					if (!IsEqType(NUMERIC, CurrDef->GetType())) {
						DefOp = CurrDef->GetOp();
						SSANum = CurrDef->GetSSANum();
						CurrDef = this->SetDefType(DefOp, NUMERIC);
						changed = true;
						// Be conservative and only propagate register DEFs and SAFE stack locs. We
						//  can improve this in the future. **!!**
						bool IsMemOp = (o_reg != DefOp.type);
						bool MemPropagate = MDIsStackAccessOpnd(DefOp, UseFP);
#if SMP_PROPAGATE_MEM_TYPES
						;
#else
						// Be conservative and only propagate register DEFs and SAFE stack locs.
						//  We can improve this in the future. **!!**
						MemPropagate = MemPropagate && SafeFunc;
#endif
						if ((o_reg == DefOp.type) || MemPropagate) {
							if (this->BasicBlock->IsLocalName(DefOp)) {
								(void) this->BasicBlock->PropagateLocalDefType(DefOp, NUMERIC,
									this->GetAddr(), SSANum, IsMemOp);
							}
							else { // global name
								this->BasicBlock->GetFunc()->ResetProcessedBlocks(); // set Processed to false
								(void) this->BasicBlock->PropagateGlobalDefType(DefOp, NUMERIC,
									SSANum, IsMemOp);
							}
						}
					}
					++CurrDef;
				}
				this->SetCategoryInferenceComplete();
				break;

			case 4: // Unary INC, DEC, etc.: dest=source, so type remains the same
				assert(1 == this->RTL.GetCount());
				assert(this->RTL.GetRT(0)->HasRightSubTree());
				UseOp = this->RTL.GetRT(0)->GetLeftOperand(); // USE == DEF
				CurrUse = this->Uses.FindRef(UseOp);
				assert(CurrUse != this->GetLastUse());
				if (UNINIT != CurrUse->GetType()) {
					// Only one USE, and it has a type assigned, so assign that type
					// to the DEF.