Skip to content
Snippets Groups Projects
SMPInstr.h 81.2 KiB
Newer Older
jdh8d's avatar
jdh8d committed
/*
 * SMPInstr.h - <see below>.
 *
 * Copyright (c) 2000, 2001, 2010 - University of Virginia 
 *
 * This file is part of the Memory Error Detection System (MEDS) infrastructure.
 * This file may be used and modified for non-commercial purposes as long as 
 * all copyright, permission, and nonwarranty notices are preserved.  
 * Redistribution is prohibited without prior written consent from the University 
 * of Virginia.
 *
 * Please contact the authors for restrictions applying to commercial use.
 *
 * THIS SOURCE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author: University of Virginia
 * e-mail: jwd@virginia.com
 * URL   : http://www.cs.virginia.edu/
 *
 * Additional copyrights 2010, 2011, 2012, 2013, 2014, 2015 by Zephyr Software LLC
 * e-mail: {clc,jwd}@zephyr-software.com
 * URL   : http://www.zephyr-software.com/
 *
jdh8d's avatar
jdh8d committed
 */

#ifndef SMPINSTR_H
#define SMPINSTR_H 1

// SMPInstr.h
//
// This header defines the interfaces needed for analyzing instructions.

#include <cstddef>
#include <cstdint>
#include "interfaces/STARSTypes.h"
#include "interfaces/SMPDBInterface.h"

#include "base/SMPDataFlowAnalysis.h"
#include "interfaces/abstract/STARSInstruction.h"
// Should we emit 64-bit register manipulations for all SPARK Ada
//  translations? If not, we will emit procedure calls to read and write
//  sub-word registers.
#define STARS_EMIT_64BIT_SPARK_ADA 1

// Dump diagnostics on Sparse Conditional Constant Propagation analyses
#define STARS_DEBUG_SCCP 1

// Convert unreachable block detected by SCCP into NOPs in binary file.
#define STARS_SCCP_CONVERT_UNREACHABLE_BLOCKS 0

// Value to signal error in computing stack pointer alteration by instruction or RTL.
#define SMP_STACK_DELTA_ERROR_CODE  0xebfaf0fd
// Value to signal that stack pointer is bitwise ANDed to align it; unknown delta that can
//  probably be ignored.
#define SMP_STACK_POINTER_BITWISE_AND_CODE 0xebeae0ed

enum STARSBranchConst {
	STARS_BRANCH_UNKNOWN = 0,
	STARS_BRANCH_ALWAYS_TAKEN,
	STARS_BRANCH_NEVER_TAKEN
};

enum SMPoperator {
	SMP_NULL_OPERATOR = 0,
	SMP_CALL,  // CALL instruction
	SMP_INPUT,  // input from port
	SMP_OUTPUT, // output to port
	SMP_ADDRESS_OF, // take effective address
	SMP_U_LEFT_SHIFT, // unsigned left shift
	SMP_S_LEFT_SHIFT, // signed left shift
	SMP_U_RIGHT_SHIFT, // unsigned right shift
	SMP_S_RIGHT_SHIFT, // signed right shift
	SMP_ROTATE_LEFT,
	SMP_ROTATE_LEFT_CARRY, // rotate left through carry
	SMP_ROTATE_RIGHT,
	SMP_ROTATE_RIGHT_CARRY, // rotate right through carry
	SMP_DECREMENT,
	SMP_INCREMENT,
	SMP_ADD,
	SMP_ADD_CARRY,   // add with carry
	SMP_SUBTRACT,
	SMP_SUBTRACT_BORROW,  // subtract with borrow
	SMP_U_MULTIPLY,
	SMP_S_MULTIPLY,
	SMP_U_DIVIDE,
	SMP_S_DIVIDE,
	SMP_U_REMAINDER,
	SMP_SIGN_EXTEND,
	SMP_ZERO_EXTEND,
	SMP_ASSIGN,
	SMP_BITWISE_AND,
	SMP_BITWISE_OR,
	SMP_BITWISE_NOT, // unary operator
	SMP_BITWISE_XOR,
	SMP_NEGATE,    // unary negation
	SMP_S_COMPARE, // signed compare (subtraction-based)
	SMP_U_COMPARE, // unsigned compare (AND-based)
	SMP_GENERAL_COMPARE, // comparisons of packed data, strings, signed, unsigned depending on control words
	SMP_LESS_THAN, // boolean test operators
	SMP_GREATER_THAN,
	SMP_LESS_EQUAL,
	SMP_GREATER_EQUAL,
	SMP_EQUAL,
	SMP_NOT_EQUAL,
	SMP_BELOW,   // unsigned comparison operators BELOW, BELOW_EQUAL, ABOVE, ABOVE_EQUAL
	SMP_BELOW_EQUAL,
	SMP_ABOVE,
	SMP_ABOVE_EQUAL,
	SMP_CARRY,  // should only be used in Guard RTLs
	SMP_NOT_CARRY,  // should only be used in Guard RTLs
	SMP_PARITY,  // should only be used in Guard RTLs
	SMP_NOT_PARITY,  // should only be used in Guard RTLs
	SMP_OVERFLOW,  // should only be used in Guard RTLs
	SMP_NOT_OVERFLOW,  // should only be used in Guard RTLs
	SMP_SIGN_BIT_SET,  // should only be used in Guard RTLs
	SMP_NOT_SIGN_BIT_SET,  // should only be used in Guard RTLs
	SMP_LOGICAL_AND,
	SMP_LOGICAL_OR,
	SMP_UNARY_NUMERIC_OPERATION,  // miscellaneous; produces NUMERIC result
	SMP_BINARY_NUMERIC_OPERATION,  // miscellaneous; produces NUMERIC result
	SMP_SYSTEM_OPERATION,   // for instructions such as CPUID, RDTSC, etc.; NUMERIC
	SMP_UNARY_FLOATING_ARITHMETIC,  // all the same to our type system; all NUMERIC
	SMP_BINARY_FLOATING_ARITHMETIC,  // all the same to our type system; all NUMERIC
	SMP_FLOATING_ADD,        // floating-point addition of any precision; all NUMERIC
	SMP_FLOATING_SUBTRACT,   // floating-point subtraction of any precision; all NUMERIC
	SMP_FLOATING_MULTIPLY,   // floating-point multiplication of any precision; all NUMERIC
	SMP_FLOATING_DIVIDE,     // floating-point division of any precision; all NUMERIC
clc5q's avatar
clc5q committed
	SMP_FLOATING_NEGATE_AND_ADD, // floating negate left operand and add to right, any precision; NUMERIC
	SMP_REVERSE_SHIFT_U, // Shift right operand by bit count in left operand
	SMP_SHUFFLE, // Shuffle bytes, words, etc. within destination operation per source mask
	SMP_COMPARE_EQ_AND_SET, // Compare for equality and set fields to all 1's or all 0's
	SMP_COMPARE_NE_AND_SET, // Compare for not-equal and set fields to all 1's or all 0's
	SMP_COMPARE_GT_AND_SET, // Compare for greater-than and set fields to all 1's or all 0's
	SMP_COMPARE_GE_AND_SET, // Compare for greater-than-or-equal and set fields to all 1's or all 0's
	SMP_COMPARE_LT_AND_SET, // Compare for less-than and set fields to all 1's or all 0's
	SMP_COMPARE_LE_AND_SET, // Compare for less-than-or-equal and set fields to all 1's or all 0's
	SMP_PACK_S,  // Pack operands into extended-precision register, signed saturation for loss of precision
	SMP_PACK_U,  // Pack operands into extended-precision register, unsigned saturation for loss of precision
	SMP_AVERAGE_U, // Average of unsigned operands
	SMP_MULTIPLY_AND_ADD, // multiply and add (or multiply and accumulate)
	SMP_SUM_OF_DIFFS, // sum over two vectors of absolute values of differences of their elements
	SMP_MAX_S, // dest := signed_max(dest, src)
	SMP_MAX_U, // dest := unsigned_max(dest, src)
	SMP_MIN_S, // dest := signed_min(dest, src)
	SMP_MIN_U, // dest := unsigned_min(dest, src)
	SMP_ABSOLUTE_VALUE, // take absolute value
	SMP_CONVERT_INT_TO_FP, // convert integer to floating point
	SMP_CONVERT_FP_TO_INT, // convert floating point to integer
	SMP_CREATE_MASK, // Create AND-mask from operand and byte/word/dword position # in immediate
	SMP_INTERLEAVE, // extended-precision interleaving of bytes or words or dwords etc.; NUMERIC
	SMP_CONCATENATE,     // extended-precision concatenation; NUMERIC
	SMP_EXTRACT_ZERO_EXTEND, // Extract sub-reg and zero-extend to reg length
	SMP_ENCRYPTION_OPERATION, // encryption or decryption bit manipulation operation
	SMP_UNARY_POINTER_OPERATION, // increment or decrement a pointer (perhaps dependent on direction flag)
	SMP_SYMBOLIC_READ_MEMORY, // for symbolic analysis only, in STARSExpression exprs
}; // end enum SMPoperator
inline bool IsUnaryOperator(SMPoperator Oper) {
	return (Oper == SMP_DECREMENT) || (Oper == SMP_INCREMENT) || (Oper == SMP_BITWISE_NOT)
		|| (Oper == SMP_NEGATE) || (Oper == SMP_UNARY_NUMERIC_OPERATION) || (Oper == SMP_UNARY_FLOATING_ARITHMETIC) 
clc5q's avatar
clc5q committed
		|| (Oper == SMP_ABSOLUTE_VALUE) || (Oper == SMP_UNARY_POINTER_OPERATION); 
};

inline bool IsRelationalOperator(SMPoperator Oper) {
	return ((Oper >= SMP_LESS_THAN) && (Oper <= SMP_ABOVE_EQUAL));
};

inline bool IsIntegerAddOrSubOperator(SMPoperator Oper) {
	return ((Oper >= SMP_DECREMENT) && (Oper <= SMP_SUBTRACT_BORROW));
};

// Take RelationalOperator from a comparison instruction, as determined by its matching jump,
//  and convert it to the operator needed if the comparison operands are swapped.
//  E.g.: cmp rax,rbx followed by ja label1 produces SMP_GREATER_THAN operator.
//  If we did cmp rbx,rax then the operator would logically be SMP_LESS_THAN.
//  Used in STARSExpression tree flips.
SMPoperator InvertRelationalOperator(SMPoperator RelationalOperator);
// Does the CurrOperator definitely indicate a signed or unsigned operation?
bool OperatorHasSignedness(SMPoperator CurrOperator);
// Should we keep track of what the operator type was before profiler
//  information was applied? (Memory usage is affected)
#define SMP_TRACK_NONSPEC_OPER_TYPE 0

extern const char *OperatorText[]; // for printing operators in Dump() methods and error messages

// Print the SPARK Ada procedure suffix for the operand, e.g. reg32 or mem16 or const32
void PrintOperandSPARKAdaSuffix(const STARSOpndTypePtr &Opnd, FILE *OutFile);

// Print an operator in SPARK-Ada form.
void PrintSPARKAdaOperator(SMPoperator Oper, std::string &OutString, bool &PrefixProcCall, bool &PrefixUnary, bool ConstFollows = false);
clc5q's avatar
clc5q committed
// Print current indentation level using tabs.
void PrintSPARKIndentTabs(FILE *OutFile);

	SMPoperator oper;
	SMPOperandType type;
#if SMP_TRACK_NONSPEC_OPER_TYPE
	SMPOperandType NonSpeculativeType;
#endif
// Class for a guard expression in an RTL
class SMPGuard {
public:
	// Constructors
	SMPGuard(void);
	// Get methods
	inline SMPoperator GetOperator(void) { return GuardOp; };
	inline STARSOpndTypePtr GetLeftOperand(void) { return LeftOperand; };
	inline STARSOpndTypePtr GetRightOperand(void) { return RightOperand; };
	inline const STARSOpndTypePtr &GetConstLeftOperand(void) { return LeftOperand; };
	inline const STARSOpndTypePtr &GetConstRightOperand(void) { return RightOperand; };
	// Set methods
	inline void SetOperator(SMPoperator op) { GuardOp = op; };
	inline void SetLeftOperand(STARSOpndTypePtr Left) { LeftOperand = Left; };
	inline void SetRightOperand(STARSOpndTypePtr Right) { RightOperand = Right; };
	// Printing methods
	STARSOpndTypePtr LeftOperand;
	STARSOpndTypePtr RightOperand;
	SMPoperator GuardOp;
}; // end class SMPGuard

// Masks to set bits to use as booleans1 in SMPRegTransfer.
clc5q's avatar
clc5q committed
#define RTL_SET_RIGHT_SUBTREE 0x01
#define RTL_SET_TYPE_INFERENCE_COMPLETE 0x02
#define RTL_SET_UNUSED1 0x04
#define RTL_SET_UNUSED2 0x08
#define RTL_SET_UNUSED3 0x10
#define RTL_SET_UNUSED4 0x20
#define RTL_SET_UNUSED5 0x40
#define RTL_SET_UNUSED6 0x80
#define RTL_RESET_RIGHT_SUBTREE 0xfe
#define RTL_RESET_TYPE_INFERENCE_COMPLETE 0xfd
#define RTL_RESET_UNUSED1 0xfb
#define RTL_RESET_UNUSED2 0xf7
#define RTL_RESET_UNUSED3 0xef
#define RTL_RESET_UNUSED4 0xdf
#define RTL_RESET_UNUSED5 0xbf
#define RTL_RESET_UNUSED6 0x7f

// Classes for register transfers and register transfer lists (RTLs)
class SMPRegTransfer {
public:
	// Constructors and destructors
	SMPRegTransfer(void);
	~SMPRegTransfer();
	inline SMPoperator GetOperator(void) const { return RTop.oper; };
	inline SMPOperandType GetOperatorType(void) const { return RTop.type; };
	STARSOpndTypePtr GetLeftOperand(void) const;
	STARSOpndTypePtr GetRightOperand(void) const;
	STARSOpndTypePtr GetLeftOperandNoNorm(void) const { return LeftOperand; }; // don't normalize stack ops; for SPARK translation
	STARSOpndTypePtr GetRightOperandNoNorm(void) const { return RightOperand; }; // don't normalize stack ops; for SPARK translation
	inline const STARSOpndTypePtr &GetConstLeftOperandNoNorm(void) const { return LeftOperand; };
	inline const STARSOpndTypePtr &GetConstRightOperandNoNorm(void) const { return RightOperand; };
	inline SMPRegTransfer *GetRightTree(void) const { return RightRT; };
	inline SMPGuard *GetGuard(void) const { return Guard; };
	inline SMPInstr *GetParentInst(void) const { return ParentInst; };

	inline void SetOperator(SMPoperator op) { RTop.oper = op; };
	void SetOperatorType(SMPOperandType OpType, const SMPInstr* instr);
	inline void SetLeftOperand(STARSOpndTypePtr Left) { LeftOperand = Left; };
	inline void SetRightOperand(STARSOpndTypePtr Right) { RightOperand = Right; booleans1 &= RTL_RESET_RIGHT_SUBTREE; };
clc5q's avatar
clc5q committed
	inline void SetRightTree(SMPRegTransfer *RightTree) { RightRT = RightTree; booleans1 |= RTL_SET_RIGHT_SUBTREE; };
	inline void SetGuard(SMPGuard *NewGuard) { Guard = NewGuard; };
clc5q's avatar
clc5q committed
	inline void SetTypeInferenceComplete(void) { booleans1 |= RTL_SET_TYPE_INFERENCE_COMPLETE; };
	inline void SetParentInst(SMPInstr *Parent) { ParentInst = Parent; };
	// Query methods
clc5q's avatar
clc5q committed
	inline bool HasRightSubTree(void) const { return (booleans1 & RTL_SET_RIGHT_SUBTREE); };
	inline bool IsTypeInferenceComplete(void) const { return (booleans1 & RTL_SET_TYPE_INFERENCE_COMPLETE); };
	bool OperandTransfersValueToDef(const STARSOpndTypePtr &UseOp) const; // Does UseOp arithmetically affect the value of the NonFlagsDef for this RTL?
	bool IsTruncatedWidthRTL(std::size_t &LeftBitWidth, std::size_t &RightBitWidth) const; // Does RTL show LeftOp has smaller bitwidth than the right hand side operands?
	bool IsExpandedWidthRTL(std::size_t &LeftBitWidth, std::size_t &RightBitWidth) const; // Does RTL show LeftOp has larger bitwidth than the right hand side operands?
	bool IsSPARKAdaNop(void) const; // Is RT irrelevant for SPARK, e.g. floating-point operations that the SPARK provers will not model

	// Printing methods
	void EmitSPARKAdaProcSuffix(FILE *OutFile) const; // emit SPARK-Ada procedure suffix, e.g. _reg32_reg32( for the add_reg32_reg32() case
	void EmitSPARKAdaForRHS(FILE *OutFile, bool RecursiveCall) const; // Helper for right hand side of RTs (i.e. RightOperand or RightTree)
	void EmitSPARKAda(FILE *OutFile); // Emit SPARK-Ada translation of RT
	// Analysis methods
	bool IsAllocaRTL(void); // subtracts unknown value from stack pointer
	void MDFixFloatingPointRTL(void); // fix machine-specific FP reg encodings
	STARS_sval_t ComputeStackPointerAlteration(bool IsLeaveInstr, STARS_sval_t IncomingDelta, STARS_sval_t FramePtrDelta);  // For instruction with operand-dependent effects on stack pointer.
	struct STARS_SCCP_Const_Struct SCCPEvaluateRTLConsts(std::list<std::pair<int, int> > &SSAWorkList); // Evaluate constant expressions for SCCP algorithm
	bool IsBasicInductionVariableOperation(void) const;
	bool IsDerivedInductionVariableOperation(void) const;
	bool IsStackPtrUsedInRT(bool UseFP) const; // Is stack ptr (or frame ptr) reg in RT?
	bool IsSubregMove(void) const;  // Is RT a move of a const or subreg into a subreg?
	std::size_t MDSignExtend64RightOpIfNeeded(void);  // sign-extend RightOperand if it needs to become 64 bit operand
	bool RightTreeNeedsWidthCast(FILE *OutFile, std::size_t LeftBitWidth, std::size_t &RightBitWidth) const; // for SPARK Ada translation
private:
	SMPGuard *Guard;   // guard expression
	RTLoperator RTop;  // operator for the reg transfer
	STARSOpndTypePtr LeftOperand;  // operand to the left of the operator in the expression
	STARSOpndTypePtr RightOperand; // valid only if RightSubTree is false
	SMPRegTransfer *RightRT; // right subtree, valid only if RightSubTree is true
	SMPInstr *ParentInst; // SMPInstr that contains this RegTransfer
clc5q's avatar
clc5q committed
	unsigned char booleans1; // hold boolean flags as bits
#if 0 // now part of booleans1
	bool RightSubTree; // Is right operand another tree (true) or an operand (false)?
clc5q's avatar
clc5q committed
	bool TypeInferenceComplete; // RTL tree at this root has all operands and operators typed
#endif
	bool OperandTransfersHelper(const STARSOpndTypePtr &UseOp) const; // recursive helper for OperandTransfersValueToDef()
}; // end class SMPRegTransfer

#define SMP_RT_LIMIT  9    // how many register transfers could be in an RTL?
clc5q's avatar
clc5q committed
	// the x86 PUSHA and POPA opcodes need 9 RTs each
class SMPRTL { // register transfer list
public:
	// Constructors and destructors.
	SMPRTL();
	~SMPRTL();
	inline std::size_t GetCount(void) const { return RTCount; };
	SMPRegTransfer *GetRT(std::size_t index) const;
	// Set methods
	void push_back(SMPRegTransfer *NewEffect);
	// Printing methods
	// Analysis methods.
	STARS_sval_t TotalStackPointerAlteration(bool IsLeaveInstr, STARS_sval_t IncomingDelta, STARS_sval_t FramePtrDelta); // sum across all RTs in RTL
	// Public data for ease of use.
	std::vector<STARSOpndTypePtr> ExtraKills;    // kills other than left operands
	SMPRegTransfer *RTvector[SMP_RT_LIMIT];
}; // end class SMPRTL
// Masks to set bits to use as booleans1 in STARSExpression.
#define EXPR_SET_RIGHT_SUBTREE 0x01
#define EXPR_SET_LEFT_SUBTREE 0x02
#define EXPR_SET_UNUSED1 0x04
#define EXPR_SET_UNUSED2 0x08
#define EXPR_SET_UNUSED3 0x10
#define EXPR_SET_UNUSED4 0x20
#define EXPR_SET_UNUSED5 0x40
#define EXPR_SET_UNUSED6 0x80
#define EXPR_RESET_RIGHT_SUBTREE 0xfe
#define EXPR_RESET_LEFT_SUBTREE 0xfd
#define EXPR_RESET_UNUSED1 0xfb
#define EXPR_RESET_UNUSED2 0xf7
#define EXPR_RESET_UNUSED3 0xef
#define EXPR_RESET_UNUSED4 0xdf
#define EXPR_RESET_UNUSED5 0xbf
#define EXPR_RESET_UNUSED6 0x7f

// Classes for general expressions, such as are needed in loop iterations analysis, loop termination exprs, etc.
class STARSExpression {
public:
	// Constructors and destructors
	STARSExpression(void);
	STARSExpression(SMPRegTransfer *RTExpr); // build from an RTL subtree
	STARSExpression(const STARSDefUseIter Ref, SMPInstr *CurrInst); // build from a DEF or USE
	~STARSExpression();
	STARSExpression *Clone(void) const; // Allocate a new tree, recursively copy in subtrees
clc5q's avatar
clc5q committed
	STARSExpression *CloneLHS(void) const; // Allocate a new tree, make it a copy of left-hand-side of this tree.
	STARSExpression *CloneRHS(void) const; // Allocate a new tree, make it a copy of right-hand-side of this tree.

	// Operators.
	bool operator<(const STARSExpression &rExpr) const;

	// Get methods
	inline SMPoperator GetOperator(void) const { return ExprOperator; };
	inline STARSOpndTypePtr GetLeftOperand(void) const { return LeftOperand; };
	inline STARSOpndTypePtr GetRightOperand(void) const { return RightOperand; };
	inline const STARSOpndTypePtr &GetConstLeftOperand(void) const { return LeftOperand; };
	inline const STARSOpndTypePtr &GetConstRightOperand(void) const { return RightOperand; };
	inline STARSExpression *GetLeftTree(void) const { return LeftExpr; };
	inline STARSExpression *GetRightTree(void) const { return RightExpr; };
	inline SMPFunction *GetParentFunc(void) const { return ParentFunc; };
	inline SMPInstr *GetParentInst(void) const { return ParentInst; };
	inline SMPInstr *GetOriginalParentInst(void) const { return OriginalParentInst; };
	inline int GetLeftSSANum(void) const { return LeftSSANum; };
	inline int GetRightSSANum(void) const { return RightSSANum; };
	inline STARS_ea_t GetLeftPreLoopDefAddr(void) const { return LeftPreLoopDefAddr; };
	inline STARS_ea_t GetRightPreLoopDefAddr(void) const { return RightPreLoopDefAddr; };
	inline STARS_ea_t GetLeftUseAddr(void) const { return LeftUseAddr; };
	inline STARS_ea_t GetRightUseAddr(void) const { return RightUseAddr; };

	// Set methods
	inline void SetOperator(SMPoperator op) { ExprOperator = op; };
	inline void SetLeftOperand(STARSOpndTypePtr Left) { LeftOperand = Left; if (nullptr != Left) booleans1 &= EXPR_RESET_LEFT_SUBTREE; };
	inline void SetRightOperand(STARSOpndTypePtr Right) { RightOperand = Right;  if (nullptr != Right) booleans1 &= EXPR_RESET_RIGHT_SUBTREE; };
	inline void SetLeftTree(STARSExpression *LeftTree) { LeftExpr = LeftTree; if (nullptr != LeftTree) booleans1 |= EXPR_SET_LEFT_SUBTREE; else booleans1 &= EXPR_RESET_LEFT_SUBTREE; };
	inline void SetRightTree(STARSExpression *RightTree) { RightExpr = RightTree; if (nullptr != RightTree) booleans1 |= EXPR_SET_RIGHT_SUBTREE; else booleans1 &= EXPR_RESET_RIGHT_SUBTREE; };
	inline void SetParentInst(SMPInstr *Parent) { ParentInst = Parent; if (nullptr == OriginalParentInst) OriginalParentInst = Parent; };
	inline void SetOriginalParentInst(SMPInstr *Parent) { OriginalParentInst = Parent; };
	inline void SetParentFunc(SMPFunction *Parent) { ParentFunc = Parent; };
	inline void SetLeftSSANum(int SSANum) { LeftSSANum = SSANum; };
	inline void SetRightSSANum(int SSANum) { RightSSANum = SSANum; };
	inline void SetLeftPreLoopDefAddr(STARS_ea_t LiveInAddr) { LeftPreLoopDefAddr = LiveInAddr; };
	inline void SetRightPreLoopDefAddr(STARS_ea_t LiveInAddr) { RightPreLoopDefAddr = LiveInAddr; };
	inline void SetLeftUseAddr(STARS_ea_t UseAddr) { LeftUseAddr = UseAddr; };
	inline void SetRightUseAddr(STARS_ea_t UseAddr) { RightUseAddr = UseAddr; };

	// Query methods
	inline bool HasRightSubTree(void) const { return (booleans1 & EXPR_SET_RIGHT_SUBTREE); };
	inline bool HasLeftSubTree(void) const { return (booleans1 & EXPR_SET_LEFT_SUBTREE); };
	bool IsEqualExpr(const STARSExpression *OtherExpr) const; // are exprs identical in operands and operators?
	bool IsEqualExprExceptingImmedOpnds(const STARSExpression *OtherExpr) const; // are exprs identical except for ImmedOp values?
	bool IsStackPtrPlusOffset(void) const; // Is Expr just the stack pointer plus optional offset constant?
	bool IsStackPtrRegUsed(void) const; // Is stack pointer reg found in the expr?
clc5q's avatar
clc5q committed
	bool IsRelationalExpr(void) const; // Is top-level operator relational?
	bool IsConstExpr(void) const; // Is expr just a constant value?

	// Printing methods
	void AnnotPrintStackPtrPlusOffset(FILE *AnnotFile) const;
	void StringPrintStackPtrPlusOffset(std::string &AnnotString) const;
	void Dump(const std::size_t TabCount = 0) const;
	void EmitSPARKAda(FILE *OutputFile, bool ProcessingLoop, bool OldSuffix, bool OffByOne, bool HasLoopArgs, bool UseSavedStackPtr, bool NoLHSArgs = false) const;  // Emit SPARK Ada translation of expression to OutputFile, perhaps with Reg'Old suffix.
	void EmitSPARKAdaString(std::string &OutString, bool ProcessingLoop, bool OldSuffix, bool OffByOne, bool HasLoopArgs, bool UseSavedStackPtr, bool NoLHSArgs = false) const;  // Emit SPARK Ada translation of expression to OutString, perhaps with Reg'Old suffix.
clc5q's avatar
clc5q committed
	void EmitSPARKInSafeRegion64(FILE *OutputFile, size_t MemWidth) const; // Emit X86.InSafeRegion64(..., X86.RSP) for each byte in memory expr
	void PrintSPARKArgLocationStrings(FILE *OutputFile, bool LoopInvariant, std::size_t LoopIndex, std::size_t &OutputCount, std::bitset<1 + MD_LAST_REG_NO> &RegsPrinted); // create vector of strings matching loop-function parameters to their incoming locations

	// Analysis methods
	void SwapSides(void);  // swap left and right sides
	uint16_t FindOrigMemOpByteWidth(void) const; // Search OrigParentInst for MemOp and return its byte width
	void EvaluateConsts(void); // Substitute SCCP constants for operands
clc5q's avatar
clc5q committed
	bool WidenRegOperands(std::size_t ByteWidth); // Widen register operands that are narrower than ByteWidth
	bool SimplifyExtensions(STARSExpression *ParentExpr); // Remove sign-extension and zero-extension operators after widening
	bool SimplifyAssigns(STARSExpression *ParentExpr); // Remove SMP_ASSIGN operators below the root level
	bool SimplifyDriver(void); // Call WidenRegOperands, SimplifyExtensions, and SimplifyExpr
	bool SimplifyExpr(STARSExpression *ParentExpr);  // Simplify operations with operands of zero or one, etc. Return true if expr was raised to parent.
	bool ExpandExpr(STARS_ea_t UseAddr, std::size_t LoopIndex, bool RightSideOnly, bool StopOnIV, bool StopOnLoopBoundary, bool RecordLoopRegs, bool InitCase, 
		std::set<int> &LoopRegHashes, bool &StoppedOnIV, bool &changed, std::set<STARS_ea_t> &StackPtrCopySet, int &DepthCounter); // Replace operands with their definitions, which might be sub-expressions
	// NOTE: StopOnLoopBoundary does not apply to the stack pointer register. We expand it to its func-entry value if possible.
	// DepthCounter is used to limit the call chain depth as ExpandExpr(), ExpandOperand(), and ExpandOperandHelper() recurse.
	//  Beyond a certain depth, we will never simplify the expression to a nice annotation output, anyway.
	//  The initial caller should pass a zero.
clc5q's avatar
clc5q committed
	bool UsesInArgReg(void) const; // Is any incoming argument register encountered? (SSA #0 in an InArg reg)
clc5q's avatar
clc5q committed
	void ListInArgRegsUsed(std::bitset<1 + MD_LAST_REG_NO> &RegNums); // list incoming argument register numbers encountered (SSA #0 in an InArg reg)
clc5q's avatar
clc5q committed
	bool IsStackPtrOffset(const STARS_sval_t CurrentStackPtrOffset, STARS_sval_t &FinalStackPtrOffset) const; // If expr is SP+offset, add offset to Current to get Final
clc5q's avatar
clc5q committed
	void SubstituteSSANum(SMPInstr *CallInst, const int NewSSANum, const STARSOpndTypePtr &InArgOp); // Find all uses of InArgOp, SSANum == 0, and give it NewSSANum; replace all ParentInsts with CallInst
	STARSOpndTypePtr FindLeftPreLoopDefOp(void) const; // For loop exprs, find the DefOp at LeftPreLoopDefAddr
	bool AreAllRegsLoopInvariant(void) const; // Detect loop-invariant exprs, which can occur inside loops.
clc5q's avatar
clc5q committed
	void SplitMemoryRangeExpr(bool PositiveIncrement, STARSExpression *&InitExpr, STARSExpression *&LimitExpr); // If this is a relational range expr, produce the lower and limit exprs
	bool ExtractImmedValue(STARS_uval_t &Value) const; // Assuming simple address regs +/- immediate, extract the immediate operand value & return true.
	bool UpdateImmedValue(STARS_uval_t OldValue, STARS_uval_t NewValue); // Find same Immed operand as ExtractImmedValue() (OldValue) and change its value to NewValue.

private:
	SMPoperator ExprOperator;  // operator for the reg transfer
	STARSOpndTypePtr LeftOperand;  // operand to the left of the operator in the expression; valid if LeftSubTree is false
	int LeftSSANum;   // valid only if LeftSubTree is false
	STARSOpndTypePtr RightOperand; // valid only if RightSubTree is false
	int RightSSANum;  // valid only if RightSubTree is false
	STARSExpression *LeftExpr; // left subtree, valid only if LeftSubTree is true
	STARSExpression *RightExpr; // right subtree, valid only if RightSubTree is true
	SMPFunction *ParentFunc; // SMPFunction that contains this expression
	SMPInstr *ParentInst; // SMPInstr that contains the DEF that uses the root expression, before ExpandExpr finds prior DEFs of its USEs.
	SMPInstr *OriginalParentInst; // Original ParentInst that does not change as ExpandExpr() proceeds.
	STARS_ea_t LeftPreLoopDefAddr; // DefAddr in backwards ExpandExpr() chain lhs that is just before loop, LiveIn to loop
	STARS_ea_t RightPreLoopDefAddr; // DefAddr in backwards ExpandExpr() chain rhs that is just before loop, LiveIn to loop
	STARS_ea_t LeftUseAddr; // InstAddr where we first saw a USE of the left operand
	STARS_ea_t RightUseAddr; // InstAddr where we first saw a USE of the right operand
	unsigned char booleans1; // hold boolean flags as bits
#if 0 // now part of booleans1
	bool RightSubTree; // Is right operand another tree (true) or an operand (false)?
	bool LeftSubTree; // Is left operand another tree (true) or an operand (false)?
#endif

	// Methods
	bool FindConstForOperand(bool Left, STARS_uval_t &ConstValue, STARS_ea_t &ConstDefAddr); // search for SCCP constant value for LeftOperand or RightOperand
	bool ElevateRightSide(STARSExpression *ParentExpr); // Expr simplifies to RightExpr or RightOperand, so raise it into ParentExpr; return true if RightOperand
	bool ElevateLeftSide(STARSExpression *ParentExpr); // Expr simplifies to LeftExpr or LeftOperand, so raise it into ParentExpr; return true if LeftOperand
	bool ExpandOperand(std::size_t LoopIndex, bool Left, bool StopOnIV, STARS_ea_t UseAddr, bool StopOnLoopBoundary, bool RecordLoopRegs, bool InitCase, 
		std::set<int> &LoopRegHashes, bool &StoppedOnIV, bool &changed, std::set<STARS_ea_t> &StackPtrCopySet, int &DepthCounter); // return false if expansion is forced to stop before constant DEF or InArg DEF or IndVAr.
	bool ExpandOperandHelper(STARS_ea_t DefAddr, const STARSOpndTypePtr &SearchOp, std::size_t LoopIndex, bool Left, bool StopOnIV, bool StopOnLoopBoundary, bool RecordLoopRegs, bool InitCase, 
		std::set<int> &LoopRegHashes, bool &StoppedOnIV, bool &changed, std::set<STARS_ea_t> &StackPtrCopySet, int &DepthCounter); // recursive helper for ExpandOperand()
	void PrintSPARKArgLocationStringsHelper(FILE *OutputFile, bool LoopInvariant, std::size_t &OutputCount, const STARSOpndTypePtr &LeafOp, STARS_ea_t PreLoopDefAddr);

}; // end class STARSExpression

// Is the given memory range just a local frame write?
bool IsLocalStackFrameExprPair(const STARSExpression *LowerExpr, const STARSExpression *UpperExpr);

// STL ordered container less-than operator for STARSExpression objects.
class STARSLessExpression {
public:
	bool operator() (const STARSExpression *Expr1, const STARSExpression *Expr2) const {
		if (nullptr == Expr1) {
			return (nullptr != Expr2); // nullptr is less than any ptr
		}
		else if (nullptr == Expr2) {
			return false;
		}
		else {
			return ((*Expr1) < (*Expr2)); // use < operator from STARSExpression
		}
	}
}; // end class STARSLessExpression
typedef std::set<STARSExpression *, STARSLessExpression> STARSExprSet;
typedef STARSExprSet::iterator STARSExprSetIter;

// Pair together the <lower-bound-expr, upper-bound-expr> of a memory writing range.
typedef std::pair<STARSExpression *, STARSExpression *> STARSExprBoundsPair;

class STARSLessExprPair {
public:
	bool operator() (const STARSExprBoundsPair Pair1, const STARSExprBoundsPair Pair2) const {
		STARSExprSet::value_compare ExprComp = this->DummyExprSet.value_comp(); // < operator
		if (ExprComp(Pair1.first, Pair2.first))
			return true;
		else if (ExprComp(Pair2.first, Pair1.first))
			return false;
		else // first expr in each pair are the same
			return ExprComp(Pair1.second, Pair2.second);
	}
private:
	STARSExprSet DummyExprSet;
}; // end class STARSLessExprPair
typedef std::set<STARSExprBoundsPair, STARSLessExprPair> STARSExprBoundsSet;
typedef STARSExprBoundsSet::const_iterator STARSExprBoundsIter;
typedef std::vector<STARSExprBoundsSet>::const_iterator STARSExprBoundsVecIter;

// Masks to set bits to use as booleans1 in SMPInstr.
#define INSTR_SET_GOODRTL 0x01
#define INSTR_SET_JUMP_TARGET 0x02
#define INSTR_SET_BLOCK_TERM 0x04
#define INSTR_SET_TAIL_CALL 0x08
#define INSTR_SET_COND_TAIL_CALL 0x10
#define INSTR_SET_CALL_USED_AS_JUMP 0x20
#define INSTR_SET_DIRECT_RECURSIVE_CALL 0x40
#define INSTR_SET_INTERRUPT 0x80
#define INSTR_RESET_GOODRTL 0xfe
#define INSTR_RESET_JUMP_TARGET 0xfd
#define INSTR_RESET_BLOCK_TERM 0xfb
#define INSTR_RESET_TAIL_CALL 0xf7
#define INSTR_RESET_COND_TAIL_CALL 0xef
#define INSTR_RESET_CALL_USED_AS_JUMP 0xdf
#define INSTR_RESET_DIRECT_RECURSIVE_CALL 0xbf
#define INSTR_RESET_INTERRUPT 0x7f

// Masks to set bits to use as booleans2 in SMPInstr.
#define INSTR_SET_NOP 0x01
#define INSTR_SET_REG_CLEAR_IDIOM 0x02
#define INSTR_SET_DEFS_FLAGS 0x04
#define INSTR_SET_USES_FLAGS 0x08
#define INSTR_SET_FAR_BRANCH_COMPUTED 0x10
#define INSTR_SET_BRANCHES_TO_FAR_CHUNK 0x20
#define INSTR_SET_INDIRECT_MEM_WRITE 0x40
#define INSTR_SET_INDIRECT_MEM_READ 0x80
#define INSTR_RESET_NOP 0xfe
#define INSTR_RESET_REG_CLEAR_IDIOM 0xfd
#define INSTR_RESET_DEFS_FLAGS 0xfb
#define INSTR_RESET_USES_FLAGS 0xf7
#define INSTR_RESET_FAR_BRANCH_COMPUTED 0xef
#define INSTR_RESET_BRANCHES_TO_FAR_CHUNK 0xdf
#define INSTR_RESET_INDIRECT_MEM_WRITE 0xbf
#define INSTR_RESET_INDIRECT_MEM_READ 0x7f

// Masks to set bits to use as booleans3 in SMPInstr.
#define INSTR_SET_LOAD_FROM_STACK 0x01
#define INSTR_SET_MULTIPLICATION_BITS_DISCARDED 0x02
#define INSTR_SET_TYPE_INFERENCE_COMPLETE 0x04
#define INSTR_SET_CATEGORY_INFERENCE_COMPLETE 0x08
#define INSTR_SET_DEFS_TYPED 0x10
#define INSTR_SET_USES_TYPED 0x20
#define INSTR_SET_MEM_DEF_USE_COMPUTED 0x40
#define INSTR_SET_FIRST_IN_BLOCK 0x80
#define INSTR_RESET_LOAD_FROM_STACK 0xfe
#define INSTR_RESET_MULTIPLICATION_BITS_DISCARDED 0xfd
#define INSTR_RESET_TYPE_INFERENCE_COMPLETE 0xfb
#define INSTR_RESET_CATEGORY_INFERENCE_COMPLETE 0xf7
#define INSTR_RESET_DEFS_TYPED 0xef
#define INSTR_RESET_USES_TYPED 0xdf
#define INSTR_RESET_MEM_DEF_USE_COMPUTED 0xbf
#define INSTR_RESET_FIRST_IN_BLOCK 0x7f
// Masks to set bits to use as booleans4 in SMPInstr.
#define INSTR_SET_DEFS_NORMALIZED 0x01
#define INSTR_SET_INST_REMOVED 0x02
#define INSTR_SET_STACK_ALIGNMENT 0x04
#define INSTR_SET_FP_NORMALIZED_TO_SP 0x08
#define INSTR_SET_ALLOCA 0x10
#define INSTR_SET_SUPPRESS_NUMERIC_ANNOTATION 0x20
#define INSTR_SET_HASH_OPERATION 0x40
#define INSTR_SET_UNSIGNED_ARG 0x80
#define INSTR_RESET_DEFS_NORMALIZED 0xfe
#define INSTR_RESET_INST_REMOVED 0xfd
#define INSTR_RESET_STACK_ALIGNMENT 0xfb
#define INSTR_RESET_FP_NORMALIZED_TO_SP 0xf7
#define INSTR_RESET_ALLOCA 0xef
#define INSTR_RESET_SUPPRESS_NUMERIC_ANNOTATION 0xdf
#define INSTR_RESET_HASH_OPERATION 0xbf
#define INSTR_RESET_UNSIGNED_ARG 0x7f
// Masks to set bits to use as booleans5 in SMPInstr.
#define INSTR_SET_UNSAFE_MEM_WRITE 0x01
#define INSTR_SET_FIXED_CALL_PUSH 0x02
#define INSTR_SET_FIXED_CALL_JUMP 0x04
#define INSTR_SET_COPY_OF_INARG 0x08
#define INSTR_SET_ANALYZED_WRITE_SAFETY 0x10
#define INSTR_SET_UPPER_BITS_CLEAR_IDIOM 0x20
#define INSTR_SET_SPARK_TRANSLATED 0x40
#define INSTR_SET_RETURN_OPCODE 0x80
#define INSTR_RESET_FIXED_CALL_PUSH 0xfd
#define INSTR_RESET_FIXED_CALL_JUMP 0xfb
#define INSTR_RESET_COPY_OF_INARG 0xf7
#define INSTR_RESET_ANALYZED_WRITE_SAFETY 0xef
#define INSTR_RESET_UPPER_BITS_CLEAR_IDIOM 0xdf
#define INSTR_RESET_SPARK_TRANSLATED 0xbf
#define INSTR_RESET_RETURN_OPCODE 0x7f
class SMPInstr {
public: 
	// Constructors and destructors
	// Operators
	int operator==(const SMPInstr &rhs) const;
	int operator<(const SMPInstr &rhs) const;
	int operator<=(const SMPInstr &rhs) const;
	int operator!=(const SMPInstr &rhs) const;
	inline STARS_ea_t GetAddr(void) const { return STARS_ID.GetIDWithinFile(); };
	inline std::size_t GetSize(void) const { return (std::size_t) STARSInstPtr->GetSize(); };
	inline STARS_InstructionID_t GetInstID(void) const { return STARS_ID; };
	inline uint16_t GetIDAOpcode(void) const { return STARSInstPtr->GetIDAOpcode(); };
	inline STARS_ea_t GetCallTarget(void) const { return IsFixedCallJump() ? GetJumpTarget() : CallTarget; };
	inline const STARSOpndTypePtr &GetControlFlowTarget(void) const { return RTL.GetRT(0)->GetConstRightOperandNoNorm(); };
clc5q's avatar
clc5q committed
	inline SMPBasicBlock *GetBlock(void) const { return BasicBlock; };
	inline std::set<DefOrUse, LessDefUse>::iterator GetFirstUse(void) { return Uses.GetFirstRef(); };
	inline std::set<DefOrUse, LessDefUse>::iterator GetFirstDef(void) { return Defs.GetFirstRef(); };
	inline std::set<DefOrUse, LessDefUse>::iterator GetLastUse(void)  { return Uses.GetLastRef(); };
	inline std::set<DefOrUse, LessDefUse>::iterator GetLastDef(void)  { return Defs.GetLastRef(); };
	inline std::set<DefOrUse, LessDefUse>::const_iterator GetFirstConstUse(void) const { return Uses.GetFirstConstRef(); };
	inline std::set<DefOrUse, LessDefUse>::const_iterator GetFirstConstDef(void) const { return Defs.GetFirstConstRef(); };
	inline std::set<DefOrUse, LessDefUse>::const_iterator GetLastConstUse(void) const { return Uses.GetLastConstRef(); };
	inline std::set<DefOrUse, LessDefUse>::const_iterator GetLastConstDef(void) const { return Defs.GetLastConstRef(); };
	inline std::set<DefOrUse, LessDefUse>::iterator GetLastSymbolicMemUse(void)  { return IndirectMemUses.GetLastRef(); };
	inline std::set<DefOrUse, LessDefUse>::iterator FindUse(const STARSOpndTypePtr &SearchOp) { return Uses.FindRef(SearchOp); };
	inline std::set<DefOrUse, LessDefUse>::iterator FindDef(const STARSOpndTypePtr &SearchOp) { return Defs.FindRef(SearchOp); };
	inline std::set<DefOrUse, LessDefUse>::iterator FindSymbolicMemUse(const STARSOpndTypePtr &SearchOp) { return IndirectMemUses.FindRef(SearchOp); };
	std::set<DefOrUse, LessDefUse>::iterator GetFirstNonFlagsDef(void);
	void GetShiftOperands(STARSOpndTypePtr &ShiftedOp, STARSOpndTypePtr &ShiftCounterOp);
	inline STARSOpndTypePtr GetMemDef(void) const { return DEFMemOp; };
	inline STARSOpndTypePtr GetMemUse(void) const { return USEMemOp; };
	void GetMemDEFAddressRegs(std::set<STARS_regnum_t> &AddressRegs) const;
	void GetDEFRegs(std::set<int> &DefRegs);
	inline std::set<STARS_sval_t>::iterator GetFirstStackDelta(void) { return StackDeltaSet.begin(); };
	inline std::set<STARS_sval_t>::iterator GetLastStackDelta(void) { return StackDeltaSet.end(); };
	inline std::size_t NumUses(void) const { return Uses.GetSize(); };
	inline std::size_t NumDefs(void) const { return Defs.GetSize(); };
	inline STARSOpndTypePtr GetOperand(std::size_t OpNum) const { return STARSInstPtr->GetOpnd(OpNum); };
clc5q's avatar
clc5q committed
	int GetOptType(void) const;
	inline SMPitype GetDataFlowType(void) const { return type; };
	STARSOpndTypePtr MDGetMemUseOp(void) const;
	STARSOpndTypePtr MDGetMemDefOp(void) const;
	STARSOpndTypePtr GetLeaMemUseOp(void) const; // return original Lea instruction [pseudo-]memory operand.
	STARSOpndTypePtr GetMoveSource(void);
clc5q's avatar
clc5q committed
#if 0
	inline STARSOpndTypePtr GetUseOnlyAddSubOp(void) const { return AddSubSourceOp; };
	inline STARSOpndTypePtr GetDefUseAddSubOp(void) const { return AddSubDefUseOp; };
clc5q's avatar
clc5q committed
#else
	STARSOpndTypePtr GetUseOnlyAddSubOp(void) const;
	STARSOpndTypePtr GetDefUseAddSubOp(void) const;
clc5q's avatar
clc5q committed
#endif
	STARSOpndTypePtr GetFirstRightOperand(void) const;
	STARSOpndTypePtr GetFirstRightOperandNoNorm(void) const;
	STARSOpndTypePtr GetFirstLeftOperandNoNorm(void) const;
	SMPRegTransfer *GetDefRT(STARSOpndTypePtr DefOp) const;
	std::size_t GetNumRTs(void) const { return RTL.GetCount(); };
	SMPRegTransfer *GetRT(std::size_t RTindex) const { return RTL.GetRT(RTindex); };
	std::size_t GetPushedOpndByteSize(void) const; // return # bytes width of first pushed operand
	inline STARS_sval_t GetStackPtrOffset(void) const { return StackPtrOffset; };
	STARS_ea_t GetJumpTarget(void) const; // return BADADDR if not jump, target addr otherwise.
	bool GetAddressRegs(STARSDefUseSet &AddressRegs); // Build set of address reg USEs, return true if any found
	SMPoperator GetCondBranchOperator(void) const; // get COND_BRANCH operator that guards the control flow, e.g. SMP_LESS_THAN
	inline STARS_InstructionID_Set_t GetReferencedIDs(bool &success) const { return STARSInstPtr->GetReferencedInstructionIDs(success); };
	inline STARS_InstructionID_Set_t GetTargetedIDs(bool &success) { return STARSInstPtr->GetTargetedInstructionIDs(success); };
	inline STARS_ea_t GetFallThroughAddr(void) { return STARSInstPtr->GetFallThroughInstID(); };
	inline std::bitset<1 + MD_LAST_REG_NO> GetDeadRegsSet(void) const { return DeadRegsBitmap; };
	inline void SetGoodRTL(void) { booleans1 |= INSTR_SET_GOODRTL; };
	inline void ResetCondTailCall(void) { booleans1 &= INSTR_RESET_COND_TAIL_CALL; };
	inline void SetCondTailCall(void) { booleans1 |= INSTR_SET_COND_TAIL_CALL; };
	inline void SetBlock(SMPBasicBlock *Block) { BasicBlock = Block; };
	inline void SetTerminatesBlock(void) { booleans1 |= INSTR_SET_BLOCK_TERM; };
	inline void SetJumpTarget(void) { booleans1 |= INSTR_SET_JUMP_TARGET; };
	void SetTailCall(void);
	void SetLeaMemUseOp(STARSOpndTypePtr NewLeaOperand); // record original Lea instruction [pseudo-]memory operand.
	inline void SetFirstInBlock(void) { 
		booleans3 |= INSTR_SET_FIRST_IN_BLOCK;
	};
	inline void ResetTypeInferenceComplete(void) { booleans3 &= INSTR_RESET_TYPE_INFERENCE_COMPLETE; };
	inline void SetInstRemove(void) { booleans4 |= INSTR_SET_INST_REMOVED; };
	inline void SetAllocaCall(void) { booleans4 |= INSTR_SET_ALLOCA; };
	inline void SetSuppressNumericAnnotation(void) { booleans4 |= INSTR_SET_SUPPRESS_NUMERIC_ANNOTATION; };
	inline void SetHashOperation(void) { booleans4 |= INSTR_SET_HASH_OPERATION; };
	inline void SetUnsignedArg(void) { booleans4 |= INSTR_SET_UNSIGNED_ARG; };
	inline void SetUnsafeMemWrite(void) { booleans5 |= INSTR_SET_UNSAFE_MEM_WRITE; };
	inline void SetAnalyzedWriteSafety(void) { booleans5 |= INSTR_SET_ANALYZED_WRITE_SAFETY; };
	inline void SetFixedCallPush(void) { booleans5 |= INSTR_SET_FIXED_CALL_PUSH; };
	inline void SetCopyOfIncomingArg(void) { booleans5 |= INSTR_SET_COPY_OF_INARG; };
	inline void SetSPARKTranslated(void) { booleans5 |= INSTR_SET_SPARK_TRANSLATED; };
	inline void SetHasReturnOpcode(void) { booleans5 |= INSTR_SET_RETURN_OPCODE; };
	void SetFixedCallJump(void);
	inline void AddDef(STARSOpndTypePtr DefOp, SMPOperandType DefType, int DefSSANum) {
		Defs.SetRef(DefOp, DefType, DefSSANum);
	}
	inline void AddUse(STARSOpndTypePtr UseOp, SMPOperandType UseType, int UseSSANum) {
		Uses.SetRef(UseOp, UseType, UseSSANum);
	}
	inline void AddSymbolicMemUse(STARSOpndTypePtr UseOp, SMPOperandType UseType, int UseSSANum) {
		IndirectMemUses.SetRef(UseOp, UseType, UseSSANum);
	}
	void MDAddRegDef(STARS_regnum_t DefReg, bool Shown, SMPOperandType Type = UNINIT);
clc5q's avatar
clc5q committed
		// Add DEF of register if not already a DEF
	void MDAddRegUse(STARS_regnum_t UseReg, bool Shown, SMPOperandType Type = UNINIT);
clc5q's avatar
clc5q committed
		// Add USE of register if not already a USE
	std::set<DefOrUse, LessDefUse>::iterator SetUseSSA(const STARSOpndTypePtr &CurrOp, int SSASub);
	std::set<DefOrUse, LessDefUse>::iterator SetDefSSA(const STARSOpndTypePtr &CurrOp, int SSASub);
	std::set<DefOrUse, LessDefUse>::iterator SetUseType(const STARSOpndTypePtr &CurrOp, SMPOperandType CurrType);
	std::set<DefOrUse, LessDefUse>::iterator SetDefType(const STARSOpndTypePtr &CurrOp, SMPOperandType CurrType);
	std::set<DefOrUse, LessDefUse>::iterator SetDefMetadata(const STARSOpndTypePtr &CurrOp, SMPMetadataType Status);
	std::set<DefOrUse, LessDefUse>::iterator SetDefIndWrite(const STARSOpndTypePtr &CurrOp, bool IndWriteFlag);
clc5q's avatar
clc5q committed
	std::set<DefOrUse, LessDefUse>::iterator SetDefLoopInvariant(const STARSOpndTypePtr &CurrOp); // invariant for all loops
	STARSDefUseIter SetDefSafeMemWrite(const STARSOpndTypePtr &CurrOp);
	std::set<DefOrUse, LessDefUse>::iterator SetUseNoTruncate(const STARSOpndTypePtr &CurrOp, bool NoTruncFlag);
	std::set<DefOrUse, LessDefUse>::iterator SetDefNoOverflow(const STARSOpndTypePtr &DefOp, bool NoOverflowFlag);
	inline void EraseDef(std::set<DefOrUse, LessDefUse>::iterator DefIter)  { Defs.EraseRef(DefIter); };
	inline void EraseUse(std::set<DefOrUse, LessDefUse>::iterator UseIter)  { Uses.EraseRef(UseIter); };
	void SetRegDead(std::size_t RegNum); // Set the DeadRegsBitmap entry for Regnum.
	inline void SetStackPtrOffset(STARS_sval_t Delta) { StackPtrOffset = Delta; };
	bool UpdateUseOpFGInfo(const STARSOpndTypePtr &UseOp, struct FineGrainedInfo NewFG);
		// helper for InferOperatorFGInfo() to update USE maps, return true if changed maps
	bool UpdateDefOpFGInfo(const STARSOpndTypePtr &DefOp, struct FineGrainedInfo NewFG);
		// helper for InferOperatorFGInfo() to update DEF maps, return true if changed maps
	void SetDeadRegsSet(std::bitset<1 + MD_LAST_REG_NO> NewBitSet) { DeadRegsBitmap = NewBitSet; };
	STARSOpndTypePtr MakeRegOpnd(STARS_regnum_t RegNum) const; // pass-through to STARS_Instruction_t::MakeRegOpnd()
	STARSOpndTypePtr MakeFloatingPointRegOpnd(STARS_regnum_t RegNum) const; // pass-through to STARS_Instruction_t::MakeFloatingPointRegOpnd()
	STARSOpndTypePtr MakeVoidOpnd(void) const; // pass-through to STARS_Instruction_t::MakeVoidOpnd()
	STARSOpndTypePtr MakeImmediateOpnd(STARS_uval_t value) const; // pass-through to STARS_Instruction_t::MakeImmediateOpnd()
	inline bool RegOpndMatches(std::size_t OpndNum, STARS_regnum_t RegNum) const { return STARSInstPtr->RegOpndMatches(OpndNum, RegNum); };
	bool HasDestMemoryOperand(void) const; // Does instruction write to memory?
	bool HasSourceMemoryOperand(void) const; // Does instruction read from memory?
	inline bool HasIndirectMemoryWrite(void) const { return (booleans2 & INSTR_SET_INDIRECT_MEM_WRITE); };
	inline bool HasIndirectMemoryRead(void) const { return (booleans2 & INSTR_SET_INDIRECT_MEM_READ); };
	bool HasStaticMemRead(void) const;
	bool HasNegatedPtrUSE(void); // Does a USE have type NEGATEDPTR?
	bool IsSecondSrcOperandNumeric(void) const;
	bool IsBasicBlockTerminator(void) const;  // kind of inst that ALWAYS terminates a block
	inline bool IsLastInBlock(void) const { return (booleans1 & INSTR_SET_BLOCK_TERM); }; // does terminate its block
	inline bool IsJumpTarget(void) { return (booleans1 & INSTR_SET_JUMP_TARGET); };
	bool IsBranchToFarChunk(void);  // instr jumps outside current chunk
	bool IsBranchToOtherFunc(void); // instr branches or jumps to another function
	inline bool IsTailCall(void) const { return (booleans1 & INSTR_SET_TAIL_CALL); };
	inline bool IsCondTailCall(void) const { return (booleans1 & INSTR_SET_COND_TAIL_CALL); };
	inline bool IsCallUsedAsJump(void) const { return (booleans1 & INSTR_SET_CALL_USED_AS_JUMP); };
	inline bool IsRecursiveCall(void) const { return (booleans1 & INSTR_SET_DIRECT_RECURSIVE_CALL); };
	inline bool IsInterruptCall(void) const { return (booleans1 & INSTR_SET_INTERRUPT); };
	bool IsOddIfThenCase(void) const; // is poorly-optimized if-then COND_BRANCH with extra jumps
	inline bool IsNop(void) const { return (booleans2 & INSTR_SET_NOP); }; // instruction is simple or complex no-op
	inline bool MDIsFloatNop(void) const { return (GetIDAOpcode() == STARS_NN_fnop); };
	bool IsMarkerInst(void) const;
	bool MDIsPushInstr(void) const;
	bool MDIsPopInstr(void) const;
	bool MDIsEnterInstr(void) const;
	bool MDIsLeaveInstr(void) const;
	bool MDIsHaltInstr(void) const;
	bool IsJumpOrBranchInstr(void) const;
	bool MDIsLoopInstr(void) const;
	bool MDIsConditionalMoveInstr(void) const;
	bool MDIsLoadEffectiveAddressInstr(void) const { return ((GetIDAOpcode() == STARS_NN_lea) && (!IsNop()) && (!IsRegClearIdiom())); };
	bool MDIsStackPointerCopy(bool UseFP);  // copies ESP or EBP to register
	bool IsStackBasedLoadEffectiveAddress(bool UseFP) const;
	bool IsGlobalStaticLoadEffectiveAddress(void) const;
	bool MDIsFrameAllocInstr(void);
	bool MDIsFrameDeallocInstr(bool UseFP, STARS_asize_t LocSize);
	bool MDUsesCalleeSavedReg(void);
	inline bool MDIsUnsignedArithmetic(void) const { return ((STARS_NN_mul == GetIDAOpcode()) || (STARS_NN_div == GetIDAOpcode())); };
	bool MDIsSignedArithmetic(void) const;
	bool MDIsUnsignedBranch(void) const;
	bool MDIsSignedBranch(void) const;
	bool MDIsUnsignedSetValue(void) const;
	bool MDIsSignedSetValue(void) const;
	bool MDIsHashingArithmetic(void) const; // Is kind of shift or rotate that is used in hash functions
	bool MDIsCompareToPositiveConstant(STARSOpndTypePtr &NonConstOperand, STARS_uval_t &ConstValue) const;
	bool MDIsCompareOrTest(void) const; // Opcode is compare or test
	bool MDIsFloatingStackCompare(void) const; // Opcode is comparison of FP stack regs, setting EFLAGS as result
	bool IsSubtractionOfConstant(STARSOpndTypePtr &NonConstOperand, STARS_uval_t &ConstValue) const;
	bool IsLoadGlobalStaticDataAddress(STARS_uval_t &GlobalAddr); // RTL is reg := global_var_addr
	bool IsBasicInductionVarArithmetic(STARSOpndTypePtr &RhsOperand, SMPoperator &RhsOperator) const; // RTL is simple x := x op y where op is +, -, or *
	// RTL is linear function Add1 + Mult1*Mult2 + Add2 or some portion of it, with nullptr returned for missing operands.
	bool IsDependentInductionVarArithmetic(STARSOpndTypePtr &Mult1, STARSOpndTypePtr &Mult2, STARSOpndTypePtr &Add1, STARSOpndTypePtr &Add2, SMPoperator &RhsOperator);
	bool MDIsSubregMaskInst(std::size_t &BytesMasked); // is AND operation that masks off lower BytesMasked bytes
	inline bool MDIsBitwiseNotOpcode(void) const { return (STARS_NN_not == GetIDAOpcode()); };
	inline bool MDIsBitwiseAndOpcode(void) const { return (STARS_NN_and == GetIDAOpcode()); };
	inline bool MDIsBitwiseOrOpcode(void) const { return (STARS_NN_or == GetIDAOpcode()); };
	inline bool MDIsSignBitFill(void) const { return ((STARS_NN_sar == GetIDAOpcode()) && ((MD_NORMAL_MACHINE_BITWIDTH - 1) == MDGetShiftCount())); };
	inline bool MDDoublesWidth(void) const { 
		return ((STARS_NN_cbw == GetIDAOpcode()) || (STARS_NN_cwde == GetIDAOpcode()) || (STARS_NN_cdqe == GetIDAOpcode()));
	}
	inline bool MDPropagateUseUpFromBranch(void) const { 
		// Do we propagate branch signedness through the register USEs of this opcode to their DEFs?
		return ((STARS_NN_cmp == GetIDAOpcode()) || (STARS_NN_test == GetIDAOpcode()) || (STARS_NN_mov == GetIDAOpcode())
			|| ((STARS_NN_bt <= GetIDAOpcode()) && (STARS_NN_bts >= GetIDAOpcode()))
	inline bool IsLoadFromStack(void) const { return (booleans3 & INSTR_SET_LOAD_FROM_STACK); };
	inline bool IsFirstInBlock(void) const { return (booleans3 & INSTR_SET_FIRST_IN_BLOCK); };
	inline bool HasFlagsDef(void) const { return (booleans2 & INSTR_SET_DEFS_FLAGS); };
	inline bool HasFlagsUse(void) const { return (booleans2 & INSTR_SET_USES_FLAGS); };
	inline bool IsRegClearIdiom(void) const { return (booleans2 & INSTR_SET_REG_CLEAR_IDIOM); };
	bool AllDEFsTyped(void); // No DEF is UNINIT
	bool AllUSEsTyped(void); // No USE is UNINIT
	bool IsNonAddressReg(const STARSOpndTypePtr &UseOp) const; // UseOp is a USE reg, not just an address reg in a memory USE
clc5q's avatar
clc5q committed
	bool IsReducedWidthDef(void) const; // RTL shows DEF operand is subreg.
	bool IsSubRegUsedAsShiftCount(const STARSOpndTypePtr &UseOp); // Is a subreg of UseOp used as a shift counter?
	bool IsOpSourceSmallPositiveConstant(const STARSOpndTypePtr &UseOp, int UseSSANum); // Does UseOp ultimately come from a small positive constant?
	bool IsOpSourceBitwiseNot(const STARSOpndTypePtr &UseOp, int UseSSANum); // Does UseOp ultimately come from a bitwise not instruction?
	bool IsOpSourceConditionCode(const STARSOpndTypePtr &UseOp, int UseSSANum); // Does UseOp ultimately come from a set-condition-code instruction?
	bool IsOpSourceLeftShift(const STARSOpndTypePtr &UseOp, int UseSSANum, STARSOpndTypePtr &ShiftCounterOp, STARSOpndTypePtr &ShiftedOp, STARS_ea_t &ShiftInstAddr); // Does UseOp ultimately come from a left shift?
	bool IsOpSourceZeroExtendedMove(const STARSOpndTypePtr &UseOp, int UseSSANum, bool TruncationCheck); // Does UseOp ultimately come from a move-with-zero-extension instruction?
	bool IsOpSourceZeroExtendedMoveShiftRightOrConditionCode(const STARSOpndTypePtr &UseOp, int UseSSANum, bool TruncationCheck); // Union of two earlier methods plus right shifts
	bool IsOpSourceSpecial(const STARSOpndTypePtr &UseOp, int UseSSANum, bool TruncationCheck, STARS_ea_t &SourceInstAddr); // Trace through moves to any of the above cases, return source addr
	bool IsOpSourceByteSwap(const STARSOpndTypePtr &UseOp, int UseSSANum, STARS_ea_t &ByteSwapAddr); // Does UseOp ultimately come from a byte swap?
	bool MDIsOverflowingOpcode(void) const; // Is non-multiply arithmetic instruction that can possibly overflow?
	bool MDIsUnderflowingOpcode(void) const; // Is non-multiply arithmetic instruction that can possibly underflow?
	bool MDIsPrefetchOpcode(void) const; // Is prefetch instruction of any sort
	bool MDIsUndefinedOpcode(void) const; // undefined opcode; control flow should never reach it
	bool MDIsAddition(void) const;
clc5q's avatar
clc5q committed
	bool MDIsDivision(void) const;
	bool MDIsShiftOrRotate(void) const; // Is opcode a shift or rotate?
	bool MDIsShiftRight(void) const; // Is opcode a shift to the right?
	bool MDIsDoubleRegShift(void) const; // Shift of two regs concatenated together?
	bool ShiftMakesUpperBitsLower(std::size_t HalfBitWidth, bool MustBeHalfRegWidth); // Do upper HalfBitWidth bits end up lower HalfBitWidth bits?
	bool MDComparesImmedASCII(void); // Inst compares a location to an apparent ASCII immediate value.
	bool MDDestroysSignBit(void) const; // Inst destroys original sign bit, e.g. shift left overwrites sign bit.
	bool MDIsZeroFlagCondBranch(void) const; // Inst is cond branch depending only on zero/non-zero status, i.e. uses only the zero flag 
clc5q's avatar
clc5q committed
	bool MDIsPossibleStringLoopingOpcode(void) const; // Inst is x86 string opcode that can have a repeat prefix to make it loop.
	bool MDHasAnyRepeatPrefix(void) const { return STARSInstPtr->HasAnyRepeatPrefix(); };
	bool MDDefaultsTo64BitOperands(void) const;
	bool MDHas64BitOperands(void) const; // Inst has 64-bit operands
	bool MDIsAddressing32bit(void) const; // is current addressing 32-bit?
	bool MDIsAddressing64bit(void) const; // is current addressing 64-bit?
	bool HasStackPointerDEF(void); // stack pointer reg is in the DEFs set
	inline bool HasGoodRTL(void) const { return (booleans1 & INSTR_SET_GOODRTL); };
	inline bool IsDefsFlags(void) const { return (booleans2 & INSTR_SET_DEFS_FLAGS); };
	inline bool IsUsesFlags(void) const { return (booleans2 & INSTR_SET_USES_FLAGS); };
	inline bool AreDefsNormalized(void) const { return (booleans4 & INSTR_SET_DEFS_NORMALIZED); };
	inline bool IsInstRemoved(void) const { return (booleans4 & INSTR_SET_INST_REMOVED); }; // e.g. inst is unreachable or other optimization removed it
	inline bool IsStackAlignmentInst(void) const { return (booleans4 & INSTR_SET_STACK_ALIGNMENT); };
	inline bool HasFPNormalizedToSP(void) const { return (booleans4 & INSTR_SET_FP_NORMALIZED_TO_SP); };
	inline bool IsAllocaCall(void) const { return (booleans4 & INSTR_SET_ALLOCA); };
	inline bool IsNumericAnnotationSuppressed(void) const { return (booleans4 & INSTR_SET_SUPPRESS_NUMERIC_ANNOTATION); };
	inline bool IsHashOperation(void) const { return (booleans4 & INSTR_SET_HASH_OPERATION); };
	inline bool IsUnsignedArg(void) const { return (booleans4 & INSTR_SET_UNSIGNED_ARG); };
	inline bool IsUnsafeMemWrite(void) const { return (booleans5 & INSTR_SET_UNSAFE_MEM_WRITE); };
	inline bool IsFixedCallPush(void) const { return (booleans5 & INSTR_SET_FIXED_CALL_PUSH); };
	inline bool IsFixedCallJump(void) const { return (booleans5 & INSTR_SET_FIXED_CALL_JUMP); };
	inline bool IsCopyOfIncomingArg(void) const { return (booleans5 & INSTR_SET_COPY_OF_INARG); };
	inline bool IsWriteSafetyAnalyzed(void) const { return (booleans5 & INSTR_SET_ANALYZED_WRITE_SAFETY); };
	inline bool HasBeenTranslatedToSPARK(void) const { return (booleans5 & INSTR_SET_SPARK_TRANSLATED); };
	inline bool HasReturnOpcode(void) const { return (booleans5 & INSTR_SET_RETURN_OPCODE); };
	inline bool MDIsReducedWidthMove(void) { return ((nullptr != GetMoveSource()) && (MoveSource->GetByteWidth() < 4)); };
	inline bool IsAnalyzeable(void) const { return (!(IsNop() || IsMarkerInst() || MDIsHaltInstr())); };
	bool IsLastInstInOptimizedLoop(bool &DoubleTailBlock);  // last inst in optimized top-testing loop will fall through to relocated loop header block
	// Are numeric values from a system call trusted input, so that all numeric errors
	//  derived from the returned values should be treated as benign?
	bool IsNumericTrustedSystemCall(void);
	bool IsIncomingRegDead(int RegNum); // Is register RegNum dead coming into this function, based on the DeadRegsBitmap?
	bool FindStackPtrDelta(STARS_sval_t SearchDelta) const; // Is SearchDelta in the set of possible stack pointer deltas for this inst?
	// Printing methods
	void PrintOperands(void) const;
	char *DestString(int OptType);
	void PrintDeadRegs(FILE *OutputFile); // print the registers that are dead right before this instruction.
	void Dump(void) const; // Complete debug print, with DEF/USE list, SSA #s, RTL
	// Print an operand in SPARK-Ada form.
	void PrintSPARKAdaOperand(const STARSOpndTypePtr &Opnd, FILE *OutFile, bool LeftHandSide, bool UseFP, bool UseMachinePrefix, bool OmitTrailingSpace, bool UseSavedStackPtr = false);
	void SPARKAdaOperandToString(const STARSOpndTypePtr &Opnd, std::string &OutString, bool LeftHandSide, bool UseFP, bool UseMachinePrefix, bool OmitTrailingSpace, bool UseSavedStackPtr);
	void PrintSPARKAdaAddressExpr(const STARSOpndTypePtr &Opnd, FILE *OutFile, bool UseFP, bool UseSavedStackPtr);  // e.g. for [RBP-8] print RBP-8 only
	bool MDEmitSPARKAdaStringOperation(FILE *OutFile); // emit SPARK Ada for string operation, perhaps with repeat prefix that makes it a loop; return true if it writes memory.
clc5q's avatar
clc5q committed
	void MDEmitSPARKAdaCompareOrTest(FILE *OutFile); // emit SPARK Ada for setting flags only (compare or test opcodes)
	void MDEmitSPARKAdaArithmeticSetsCondCodes(FILE *OutFile); // emit SPARK Ada for ops that set flags (add, sub, etc.)
clc5q's avatar
clc5q committed
	void MDEmitSPARKAdaSetCondCodeIntoReg(FILE *OutFile); // emit SPARK Ada for moving a condition code value or expr into a register
clc5q's avatar
clc5q committed
	void MDEmitSPARKAdaCondition(FILE *OutFile); // emit SPARK Ada for the current conditional branch
clc5q's avatar
clc5q committed
	void MDEmitSPARKAdaInvertedCondition(FILE *OutFile); // Invert the condition of the current conditional branch and emit SPARK Ada equivalent.
	void MDEmitSPARKAdaExprCompare(FILE *OutFile); // emit SPARK Ada comparison expr for current signed-compare conditional branch
	void MDEmitSPARKAdaExprTest(FILE *OutFile); // emit SPARK Ada comparison expr for current unsigned-compare conditional branch
	SMPoperator MDConvertJumpToOperator(void) const;  // return SMP_GREATER_THAN for ja and jg opcodes, etc.
clc5q's avatar
clc5q committed
	void EmitSPARKAdaLoopInvariants(FILE *BodyFile) const;
	void EmitSPARKAda(FILE *OutFile); // Emit SPARK-Ada translation of instruction
	// Analysis methods
	STARSOpndTypePtr GetSourceOnlyOperand(void) const; // return non-flags-reg non-dest source operand
	std::set<DefOrUse, LessDefUse>::iterator GetPointerAddressReg(const STARSOpndTypePtr &MemOp);
	bool FillCmd(void); // Fetch "cmd" instruction description from disassembler.
	void Analyze(void); // Fill in basic data for instruction.
	void AnalyzeMarker(void); // Fill in basic data for top of function pseudo-instruction.
	void MDFixFloatingPointRTL(void); // fix machine-specific FP reg encodings
	void AnalyzeCallInst(STARS_ea_t FirstFuncAddr); // Detect pseudo-calls
	void AnalyzeIndirectRefs(bool UseFP); // Detect indirect memory operands
	STARS_sval_t AnalyzeStackPointerDelta(STARS_sval_t IncomingDelta, STARS_sval_t FramePtrDelta);
	STARS_sval_t FindStackAdjustment(void); // Find amount of stack adjustment, e.g. if this inst is after a call
	bool MDComputeNormalizedDataFlowOp(bool UseFP, STARS_sval_t FPDelta, STARSOpndTypePtr &DefOp); // Normalize stack operands to use incoming stack delta; leave others as is
		// return true if register or stack memory operand, false otherwise
	bool MDNormalizeStackOps(bool UseFP, STARS_sval_t FPDelta, bool Recomputing, STARS_sval_t DeltaIncrement = 0);
		// Iterate through Defs and Uses, calling MDComputeNormalizedDataFlowOp(); true if changed DEFs or USEs
	void MDGetUnnormalizedOp(STARSOpndTypePtr &NormOp); // If NormOp is a normalized stack memory operand, unnormalize it.
	bool HasAllocaRTL(void); // RTL shows alloca pattern, i.e. subtracts non-const value from stack pointer
	bool MDIsStackPtrSaveOrRestore(bool UseFP, STARS_sval_t FPDelta, bool &Save, STARS_sval_t &StackDelta, STARSOpndTypePtr &CopyOp, bool &Error); // is stack/frame pointer saved to/restored from CopyOp
	bool DetectUnsafeMemWrite(void); // return true if current inst mem write is unsafe, false otherwise
	bool GetPushedRegsList(std::map<uint32_t, STARS_sval_t> &PushedRegs); // Make list of regs and their stack offsets in RTLs for any push instruction
	bool GetPoppedRegsList(bool FirstReturnBlock, std::map<uint32_t, STARS_sval_t> &PoppedRegs); // Make list of regs and their stack offsets in RTLs for any pop instruction
	void MDFixupDefUseLists(void); // Machine-dependent ad hoc fixes
	bool MDFixupCallDefUseLists(void); // Machine-dependent ad hoc fixes for call instructions; return true if changes made
	void MDFindLoadFromStack(bool UseFP); // determine if instruction is load from stack loc
	bool MDIsSystemCall(void); // return true if instruction is a system call
	bool MDIsSignedLoad(unsigned short &SignMask) const; // true if sign or zero-extended; pass out mask bits
clc5q's avatar
clc5q committed
	bool MDIsArithmeticUsingCarryFlag(void) const; // e.g. add-with-carry or subtract-with-borrow
	bool MDIsSmallPositiveAddition(void); // true if increment or addition of small positive immediate value
	bool MDIsSmallAdditionOrSubtraction(void); // true if increment, decrement, or addition or subtraction of small immediate value
	bool MDIsSimpleAssignment(bool &ValueFound, STARS_uval_t &ConstValue); // Inst is move or register clear.
	bool IsSimpleCopy(STARSOpndTypePtr &rhs) const; // RTL is just lhs := rhs;
	bool IsSimpleCopyNoNorm(STARSOpndTypePtr &rhs) const; // RTL is just lhs := rhs; don't normalize rhs operand
	bool IsCounterOperation(void); // Inst clears register or adds or subtracts small immediate value, as is done with counter variables.
clc5q's avatar
clc5q committed
	bool MDIsNonOverflowingBitManipulation(void) const; // Inst does an AND, OR, XOR operation, does not do add, subtract, etc.
	bool FindConstantValue(std::set<DefOrUse, LessDefUse>::iterator UseIter, STARS_uval_t &ConstValue); // return true if traced USE to a constant value
	void SyncAllRTs(bool UseFP, STARS_sval_t FPDelta); // calls SyncRTLDefUse() for all RTs in RTL
	STARSOpndTypePtr GetPushedOpnd(void) const; // Extract source operand from PUSH RTL
	int MDGetImmedUse(void); // Get immed value from USE list of inst
	void MDGetFlagsUsed(std::set<int> &UsedFlags); // See which particular SCCP flags (carry flag, zero flag, etc.) are USEd
	bool MDIsArgumentPass(std::size_t &ArgumentNumber); // Does inst pass an outgoing argument?
	void GetCompareOrTestExpr(struct LoopComparison &LoopExpr); // Get comparison expr; valid only for signed or unsigned comparison insts
	STARSExpression *CreateDefExpr(const STARSOpndTypePtr &DefOp); // create Expr for DefOp from right-hand-side of first RT
	STARSExpression *CreateMemDefAddrExpr(void); // create Expr from left-hand-side of first RT, e.g. [RAX+8] => SMP_ADD(RAX, 8)
	bool OperandTransfersValueToDef(const STARSOpndTypePtr &UseOp); // Does UseOp arithmetically affect the value of the NonFlagsDef for this inst?
	void SCCPEvaluateAssignment(std::list<std::pair<int, int> > &SSAWorkList); // Evaluate constants in assignment statement for SCCP algorithm
	void SCCPEvaluateCondBranch(enum STARSBranchConst &BranchEval); // Evaluate conditional branch using constant values from SCCP
	void SCCPFetchConstUseValue(const STARSOpndTypePtr &UseOp, STARS_SCCP_Const_Struct &ConstStruct); // fetch const value, if any for a USE operand
	void SCCPFetchConstDefValue(const STARSOpndTypePtr &DefOp, STARS_SCCP_Const_Struct &ConstStruct); // fetch const value, if any for a DEF operand
	std::string GetTrimmedCalledFunctionName(void); // Get funcname from call inst and remove "." and "_" prefices
	void SetImmedTypes(bool UseFP); // type all immediate operands as NUMERIC, CODEPTR, GLOBALPTR
									//  and set other context-free types (ESP == STACKPTR, etc.)
	void MDSetWidthSignInfo(bool UseFP); // Infer sign, bit width, etc. in simple cases within one instr
	void InferSignednessFromSMPTypes(bool UseFP); // Infer sign from the SMP types for USEs and DEFs.
	bool InferMarkerInstTypes(void); // Get incoming types for marker inst DEFs from all call sites.
	bool InferTypes(void); // return true if any DEF-USE or RTL operator types were updated.
	bool InferFGInfo(unsigned short IterCount); // infer width on first pass, signedness on all passes
	void AnnotateStackConstants(bool UseFP, FILE *AnnotFile);