SMPInstr.cpp

/*
 * SMPInstr.cpp - <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 by Zephyr Software LLC
 * e-mail: {clc,jwd}@zephyr-software.com
 * URL   : http://www.zephyr-software.com/
 *
 */

//
// SMPInstr.cpp
//
// This module performs the instruction level analyses needed for the
//   SMP project (Software Memory Protection).
//

using namespace std;

#include <string>
#include <cstring>

#include <pro.h>
#include <assert.h>
#include <ua.hpp>
#include <ida.hpp>
#include <idp.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <intel.hpp>
#include <loader.hpp>
#include <lines.hpp>
#include <name.hpp>

#include "SMPDBInterface.h"
#include "SMPStaticAnalyzer.h"
#include "SMPDataFlowAnalysis.h"
#include "SMPInstr.h"
#include "SMPProgram.h"
#include "ProfilerInformation.h"

// Set to 1 for debugging output
#define SMP_DEBUG 1
#define SMP_DEBUG2 0   // verbose
#define SMP_DEBUG_XOR 0
#define SMP_DEBUG_BUILD_RTL  1   // should be left on, serious errors!
#define SMP_VERBOSE_DEBUG_BUILD_RTL  0
#define SMP_VERBOSE_DEBUG_BUILD_RTL_DEF_USE 0
#define SMP_VERBOSE_DEBUG_INFER_TYPES 0
#define SMP_VERBOSE_DUMP 0
#define SMP_VERBOSE_FIND_POINTERS 0
#define STARS_DUMP_FG_INFO 1  // show signedness of DEFs and USEs in dump

#define SMP_BASEREG_POINTER_TYPE 1  // Initialize Base Register USEs to type POINTER?
#define SMP_OPTIMIZE_ADD_TO_NUMERIC 0 // optimizing annotation type -5
#define SMP_IDENTIFY_POINTER_ADDRESS_REG 0 // optimizing annotation POINTER
#define SMP_CHILDACCESS_ALL_CODE 0 // CHILDACCESS annotations for all funcs, or just analyzed funcs?
#define SPECIAL_CASE_CARRY_BORROW 0 // Treat sbb/adc different from sub/add annotations?
#define SMP_BUILD_SPECIAL_ADC_SBB_RTL 0 // Explicit RTL subtree for carry flag?
#define SMP_AGGRESSIVE_TYPE_INFERENCE 1  // Shorten iterations by quick propagation in InferOperatorType()
#define SMP_ANNOTATE_ALL_MEMORY_OPERANDS 0 // Info annotation for all memory read and write operands?
#define SMP_AGGRESSIVE_SIGN_TRANSFER 1  // More transfer of signedness across instructions
#define STARS_NO_SHIFT_SIGNEDNESS_IN_SCALEFACTOR 1  // unsigned left shift for scale factors is really unknownsign multiply

// Make the CF_CHG1 .. CF_CHG6 and CF_USE1..CF_USE6 macros more usable
//  by allowing us to pick them up with an array index.
static ulong DefMacros[UA_MAXOP] = {CF_CHG1, CF_CHG2, CF_CHG3, CF_CHG4, CF_CHG5, CF_CHG6};
static ulong UseMacros[UA_MAXOP] = {CF_USE1, CF_USE2, CF_USE3, CF_USE4, CF_USE5, CF_USE6};

// Text to be printed in each optimizing annotation explaining why
//  the annotation was emitted.
static const char *OptExplanation[LAST_TYPE_CATEGORY + 1] =
	{ "NoOpt", "NoMetaUpdate", "AlwaysNUM", "NUMVia2ndSrcIMMEDNUM",
	  "Always1stSrc", "1stSrcVia2ndSrcIMMEDNUM", "AlwaysPtr",
	  "AlwaysNUM", "AlwaysNUM", "NUMViaFPRegDest", "NumericSources",
	  "StackMemoryTracking", "NumericSources", "NumericMemDest",
	  "NeverMemDest", "SafeIfNoIndexing"
	};

static const char *OperatorText[LAST_SMP_OPERATOR + 1] = 
{ 	"SMP_NULL_OPERATOR", "SMP_CALL", "SMP_INPUT", "SMP_OUTPUT", "SMP_ADDRESS_OF",
	"SMP_U_LEFT_SHIFT", "SMP_S_LEFT_SHIFT", "SMP_U_RIGHT_SHIFT", "SMP_S_RIGHT_SHIFT",
	"SMP_ROTATE_LEFT", "SMP_ROTATE_LEFT_CARRY", "SMP_ROTATE_RIGHT", "SMP_ROTATE_RIGHT_CARRY",
	"SMP_DECREMENT", "SMP_INCREMENT",
	"SMP_ADD", "SMP_ADD_CARRY", "SMP_SUBTRACT", "SMP_SUBTRACT_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", "SMP_BITWISE_XOR", "SMP_BITWISE_AND_NOT", "SMP_NEGATE", 
	"SMP_S_COMPARE", "SMP_U_COMPARE", "SMP_GENERAL_COMPARE", "SMP_LESS_THAN", "SMP_GREATER_THAN",
	"SMP_LESS_EQUAL", "SMP_GREATER_EQUAL", "SMP_EQUAL", "SMP_NOT_EQUAL",
	"SMP_LOGICAL_AND", "SMP_LOGICAL_OR", "SMP_UNARY_NUMERIC_OPERATION",
	"SMP_BINARY_NUMERIC_OPERATION", "SMP_SYSTEM_OPERATION",
	"SMP_UNARY_FLOATING_ARITHMETIC", "SMP_BINARY_FLOATING_ARITHMETIC",
	"SMP_REVERSE_SHIFT_U", "SMP_SHUFFLE", "SMP_COMPARE_EQ_AND_SET",
	"SMP_COMPARE_NE_AND_SET", "SMP_COMPARE_GT_AND_SET", 
	"SMP_COMPARE_GE_AND_SET", "SMP_COMPARE_LT_AND_SET", "SMP_COMPARE_LE_AND_SET",
	"SMP_PACK_SIGNED", "SMP_PACK_UNSIGNED",
	"SMP_AVERAGE_UNSIGNED", "SMP_MULTIPLY_AND_ADD", "SMP_SUM_OF_DIFFS",
	"SMP_MAX_S", "SMP_MAX_U", "SMP_MIN_S", "SMP_MIN_U", "SMP_ABS_VALUE",
	"SMP_CONVERT_INT_TO_FP", "SMP_CONVERT_FP_TO_INT", "SMP_CREATE_MASK",
	"SMP_INTERLEAVE", "SMP_CONCATENATE", "SMP_EXTRACT_ZERO_EXTEND", 
	"SMP_ENCRYPTION_OPERATION", "SMP_SIGNAL"
};

#if 0
// Does the CurrOperator definitely indicate a signed or unsigned operation?
bool OperatorHasSignedness(SMPoperator CurrOperator) {
	bool DetectedSignedness;

	switch (CurrOperator) {
		case SMP_NULL_OPERATOR:
			DetectedSignedness = false;
			break;

		case SMP_CALL:  // CALL instruction
			DetectedSignedness = true;
			break;

		case SMP_INPUT:  // input from port
		case SMP_OUTPUT: // output to port
		case SMP_ADDRESS_OF: // take effective address
		case SMP_GENERAL_COMPARE:
			DetectedSignedness = false;
			break;

		case SMP_U_LEFT_SHIFT: // unsigned left shift
		case SMP_U_RIGHT_SHIFT: // unsigned right shift
		case SMP_ROTATE_LEFT:
		case SMP_ROTATE_LEFT_CARRY: // rotate left through carry
		case SMP_ROTATE_RIGHT:
		case SMP_ROTATE_RIGHT_CARRY: // rotate right through carry
		case SMP_U_MULTIPLY:
		case SMP_U_DIVIDE:
		case SMP_U_REMAINDER:
		case SMP_ZERO_EXTEND:
		case SMP_BITWISE_NOT: // unary operator
		case SMP_BITWISE_XOR:
		case SMP_BITWISE_AND_NOT:
		case SMP_U_COMPARE: // unsigned compare (AND-based)
			DetectedSignedness = true;
			break;

		case SMP_S_LEFT_SHIFT: // signed left shift
		case SMP_S_RIGHT_SHIFT: // signed right shift
		case SMP_S_MULTIPLY:
		case SMP_S_DIVIDE:
		case SMP_SIGN_EXTEND:
		case SMP_NEGATE:    // unary negation
		case SMP_S_COMPARE: // signed compare (subtraction-based)
		case SMP_LESS_THAN: // boolean test operators
		case SMP_GREATER_THAN:
		case SMP_LESS_EQUAL:
		case SMP_GREATER_EQUAL:
			DetectedSignedness = true;
			break;

		case SMP_DECREMENT:
		case SMP_INCREMENT:
		case SMP_ADD:
		case SMP_ADD_CARRY:   // add with carry
		case SMP_SUBTRACT:
		case SMP_SUBTRACT_BORROW:  // subtract with borrow
		case SMP_ASSIGN:
		case SMP_BITWISE_AND:
		case SMP_BITWISE_OR:
		case SMP_EQUAL:
		case SMP_NOT_EQUAL:
		case SMP_LOGICAL_AND:
		case SMP_LOGICAL_OR:
		case SMP_UNARY_NUMERIC_OPERATION:  // miscellaneous; produces NUMERIC result
		case SMP_BINARY_NUMERIC_OPERATION:  // miscellaneous; produces NUMERIC result
		case SMP_SYSTEM_OPERATION:   // for instructions such as CPUID, RDTSC, etc.; NUMERIC
		case SMP_SHUFFLE: // Shuffle bytes, words, etc. within destination operation per source mask
		case SMP_SIGNAL: // signal or raise exception
			DetectedSignedness = false;
			break;

		case SMP_UNARY_FLOATING_ARITHMETIC:  // all the same to our type system; all NUMERIC
		case SMP_BINARY_FLOATING_ARITHMETIC:  // all the same to our type system; all NUMERIC
			DetectedSignedness = true;
			break;

		case SMP_REVERSE_SHIFT_U: // Shift right operand by bit count in left operand
		case SMP_COMPARE_EQ_AND_SET: // Compare for equality and set fields to all 1's or all 0's
		case SMP_COMPARE_NE_AND_SET: // Compare for inequality and set fields to all 1's or all 0's
		case SMP_COMPARE_GT_AND_SET: // Compare for greater-than and set fields to all 1's or all 0's
		case SMP_COMPARE_GE_AND_SET: // Compare for greater-than-or-equal and set fields to all 1's or all 0's
		case SMP_COMPARE_LT_AND_SET: // Compare for less-than and set fields to all 1's or all 0's
		case SMP_COMPARE_LE_AND_SET: // Compare for less-than-or-equal and set fields to all 1's or all 0's
		case SMP_PACK_S:  // Pack operands into extended-precision register, signed saturation for loss of precision
		case SMP_PACK_U:  // Pack operands into extended-precision register, unsigned saturation for loss of precision
		case SMP_AVERAGE_U: // Average of unsigned operands
		case SMP_MULTIPLY_AND_ADD: // multiply and add (or multiply and accumulate)
		case SMP_SUM_OF_DIFFS: // sum over two vectors of absolute values of differences of their elements
		case SMP_MAX_S: // dest := signed_max(dest, src)
		case SMP_MAX_U: // dest := unsigned_max(dest, src)
		case SMP_MIN_S: // dest := signed_min(dest, src)
		case SMP_MIN_U: // dest := unsigned_min(dest, src)
		case SMP_ABSOLUTE_VALUE: // take absolute value
		case SMP_CONVERT_INT_TO_FP: // convert integer to floating point
		case SMP_CONVERT_FP_TO_INT: // convert floating point to integer
		case SMP_INTERLEAVE: // extended-precision interleaving of bytes or words or dwords etc.; NUMERIC
		case SMP_CONCATENATE:     // extended-precision concatenation; NUMERIC
			DetectedSignedness = true;
			break;

		default:
			DetectedSignedness = false;
			SMP_msg("ERROR: Unknown operator in OperatorHasSignedness: %d\n", CurrOperator);
			break;
	} // end switch on operator

	return DetectedSignedness;
} // end of OperatorHasSignedness()
#endif

// Print an operand in SPARK-Ada form.
void PrintSPARKAdaOperand(op_t Opnd, FILE *OutFile) {
	op_t BaseOp = InitOp;
	op_t IndexOp = InitOp;
	BaseOp.type = o_reg;
	IndexOp.type = o_reg;

	if (Opnd.type == o_mem) {
		if (Opnd.hasSIB) {
			SMP_fprintf(OutFile, " Memory[%lx + ", (unsigned long) Opnd.addr);
			AnnotPrintSIB(Opnd, false, OutFile);
			SMP_fprintf(OutFile, "] ");
		}
		else {
			SMP_fprintf(OutFile, " Memory[%lx] ", (unsigned long) Opnd.addr);
		}
	}
	else if (Opnd.type == o_phrase) {
		if (Opnd.hasSIB) { // has SIB info
			SMP_fprintf(OutFile, " Memory[");
			AnnotPrintSIB(Opnd, false, OutFile);
			SMP_fprintf(OutFile, "] ");
		}
		else { // no SIB info
			ushort BaseReg = Opnd.phrase;
			BaseOp.reg = BaseReg;
			if (RegSizes[BaseReg] == 1)
				BaseOp.dtyp = dt_byte;
			SMP_fprintf(OutFile, " Memory[%s] ", MDGetRegName(BaseOp));
		}
		if (Opnd.addr != 0) {
			SMP_msg(" \n WARNING: addr for o_phrase type: %lx\n", (unsigned long) Opnd.addr);
		}
	}
	else if (Opnd.type == o_displ) {
		ea_t offset = Opnd.addr;
		int SignedOffset = (int) offset;
		if (Opnd.hasSIB) {
			SMP_fprintf(OutFile, " Memory[");
			AnnotPrintSIB(Opnd, (SignedOffset != 0), OutFile);
			if (SignedOffset > 0) // print plus sign
				SMP_fprintf(OutFile, "+%d] ", SignedOffset);
			else if (SignedOffset < 0) // minus sign will print automatically
				SMP_fprintf(OutFile, "%d] ", SignedOffset);

		}
		else {
			ushort BaseReg = Opnd.reg;
			BaseOp.reg = BaseReg;
			if (RegSizes[BaseReg] == 1)
				BaseOp.dtyp = dt_byte;
			if (SignedOffset >= 0) // print plus sign
				SMP_fprintf(OutFile, " Memory[%s+%d] ", MDGetRegName(BaseOp), SignedOffset);
			else // minus sign will print automatically
				SMP_fprintf(OutFile, " Memory[%s%d] ", MDGetRegName(BaseOp), SignedOffset);
		}
	}
	else if (Opnd.type == o_reg) {
		SMP_fprintf(OutFile, " %s ", MDGetRegName(Opnd));
	}
	else if (Opnd.type == o_imm) {
		SMP_fprintf(OutFile, " %ld ", (long) Opnd.value);
	}
	else if ((Opnd.type == o_far) || (Opnd.type == o_near)) {
		SMP_fprintf(OutFile, " %lx ", (unsigned long) Opnd.addr);
	}
	else {
		SMP_fprintf(OutFile, " ERROROP");
	}
	return;
} // end of PrintSPARKAdaOperand()

// Print an operator in SPARK-Ada form.
void PrintSPARKAdaOperator(SMPoperator Oper, FILE *OutFile) {
	switch (Oper) {
		case SMP_NULL_OPERATOR: 
		case SMP_INPUT:  // input from port
		case SMP_OUTPUT: // output to port
		case SMP_ADDRESS_OF: // take effective address
		case SMP_S_LEFT_SHIFT: // signed left shift
		case SMP_ROTATE_LEFT_CARRY: // rotate left through carry
		case SMP_ROTATE_RIGHT_CARRY: // rotate right through carry
		case SMP_ADD_CARRY:   // add with carry
		case SMP_SUBTRACT_BORROW:  // subtract with borrow
			SMP_msg("ERROR: SPARK: Cannot translate operator: ");
			SMP_msg(" %s \n", OperatorText[Oper]);
			break;

		case SMP_CALL:  // CALL instruction
			break;

		case SMP_U_LEFT_SHIFT: // unsigned left shift
		case SMP_REVERSE_SHIFT_U: // Shift right operand by bit count in left operand
			SMP_fprintf(OutFile, " Interfaces.Shift_Left");
			break;

		case SMP_U_RIGHT_SHIFT: // unsigned right shift
			SMP_fprintf(OutFile, " Interfaces.Shift_Right");
			break;

		case SMP_S_RIGHT_SHIFT: // signed right shift
			SMP_fprintf(OutFile, " Interfaces.Shift_Right_Arithmetic");
			break;

		case SMP_ROTATE_LEFT:
			SMP_fprintf(OutFile, " Interfaces.Rotate_Left");
			break;

		case SMP_ROTATE_RIGHT:
			SMP_fprintf(OutFile, " Interfaces.Rotate_Right");
			break;

		case SMP_DECREMENT:
			SMP_fprintf(OutFile, " - 1");
			break;

		case SMP_INCREMENT:
			SMP_fprintf(OutFile, " + 1");
			break;

		case SMP_ADD:
			SMP_fprintf(OutFile, " + ");
			break;

		case SMP_SUBTRACT:
			SMP_fprintf(OutFile, " - ");
			break;

		case SMP_U_MULTIPLY:
		case SMP_S_MULTIPLY:
			SMP_fprintf(OutFile, " * ");
			break;

		case SMP_U_DIVIDE:
		case SMP_S_DIVIDE:
		case SMP_U_REMAINDER:
			break;

		case SMP_SIGN_EXTEND:
		case SMP_ZERO_EXTEND:
			break;

		case SMP_ASSIGN:
			SMP_fprintf(OutFile, ":= ");
			break;

		case SMP_BITWISE_AND:
			SMP_fprintf(OutFile, " and ");
			break;

		case SMP_BITWISE_OR:
			SMP_fprintf(OutFile, " or ");
			break;

		case SMP_BITWISE_NOT: // unary operator
			SMP_fprintf(OutFile, " not ");
			break;

		case SMP_BITWISE_XOR:
			SMP_fprintf(OutFile, " xor ");
			break;

		case SMP_BITWISE_AND_NOT:
			SMP_fprintf(OutFile, " and (not ");
			break;

		case SMP_NEGATE:    // unary negation
			SMP_fprintf(OutFile, " - ");
			break;

		case SMP_S_COMPARE: // signed compare (subtraction-based)
		case SMP_U_COMPARE: // unsigned compare (AND-based)
		case SMP_GENERAL_COMPARE: // comparisons of packed data, strings, signed, unsigned depending on control words
			break;

		case SMP_LESS_THAN: // boolean test operators
			SMP_fprintf(OutFile, " < ");
			break;

		case SMP_GREATER_THAN:
			SMP_fprintf(OutFile, " > ");
			break;

		case SMP_LESS_EQUAL:
			SMP_fprintf(OutFile, " <= ");
			break;

		case SMP_GREATER_EQUAL:
			SMP_fprintf(OutFile, " >= ");
			break;

		case SMP_EQUAL:
			SMP_fprintf(OutFile, " = ");
			break;

		case SMP_NOT_EQUAL:
			SMP_fprintf(OutFile, " /= ");
			break;

		case SMP_LOGICAL_AND:
			SMP_fprintf(OutFile, " and then "); // short circuit operator
			break;

		case SMP_LOGICAL_OR:
			SMP_fprintf(OutFile, " or else "); // short circuit operator
			break;

		case SMP_UNARY_NUMERIC_OPERATION:  // miscellaneous; produces NUMERIC result
		case SMP_BINARY_NUMERIC_OPERATION:  // miscellaneous; produces NUMERIC result
		case SMP_SYSTEM_OPERATION:   // for instructions such as CPUID, RDTSC, etc.; NUMERIC
		case SMP_UNARY_FLOATING_ARITHMETIC:  // all the same to our type system; all NUMERIC
		case SMP_BINARY_FLOATING_ARITHMETIC:  // all the same to our type system; all NUMERIC
			break;

		case SMP_SHUFFLE: // Shuffle bytes, words, etc. within destination operation per source mask
		case SMP_COMPARE_EQ_AND_SET: // Compare for equality and set fields to all 1's or all 0's
		case SMP_COMPARE_NE_AND_SET: // Compare for not-equal and set fields to all 1's or all 0's
		case SMP_COMPARE_GT_AND_SET: // Compare for greater-than and set fields to all 1's or all 0's
		case SMP_COMPARE_GE_AND_SET: // Compare for greater-than-or-equal and set fields to all 1's or all 0's
		case SMP_COMPARE_LT_AND_SET: // Compare for less-than and set fields to all 1's or all 0's
		case SMP_COMPARE_LE_AND_SET: // Compare for less-than-or-equal and set fields to all 1's or all 0's
		case SMP_PACK_S:  // Pack operands into extended-precision register, signed saturation for loss of precision
		case SMP_PACK_U:  // Pack operands into extended-precision register, unsigned saturation for loss of precision
		case SMP_AVERAGE_U: // Average of unsigned operands
		case SMP_MULTIPLY_AND_ADD: // multiply and add (or multiply and accumulate)
		case SMP_SUM_OF_DIFFS: // sum over two vectors of absolute values of differences of their elements
		case SMP_MAX_S: // dest := signed_max(dest, src)
		case SMP_MAX_U: // dest := unsigned_max(dest, src)
		case SMP_MIN_S: // dest := signed_min(dest, src)
		case SMP_MIN_U: // dest := unsigned_min(dest, src)
		case SMP_ABSOLUTE_VALUE: // take absolute value
		case SMP_CONVERT_INT_TO_FP: // convert integer to floating point
		case SMP_CONVERT_FP_TO_INT: // convert floating point to integer
		case SMP_CREATE_MASK: // Create AND-mask from operand and byte/word/dword position # in immediate
		case SMP_INTERLEAVE: // extended-precision interleaving of bytes or words or dwords etc.; NUMERIC
		case SMP_CONCATENATE:     // extended-precision concatenation; NUMERIC
		case SMP_EXTRACT_ZERO_EXTEND: // Extract sub-reg and zero-extend to reg length
		case SMP_ENCRYPTION_OPERATION: // encryption or decryption bit manipulation operation
		case SMP_SIGNAL:   // signal or raise exception
			break;

		default:
			SMP_msg("ERROR: SPARK: Cannot translate unknown operator: ");
			SMP_msg(" %s \n", OperatorText[Oper]);
			break;
	}
} // end of PrintSPARKAdaOperator()

// *****************************************************************
// Class SMPGuard
// *****************************************************************
// Constructor
SMPGuard::SMPGuard(void) {
	this->LeftOperand.type = o_void;
	this->RightOperand.type = o_void;
	this->GuardOp = SMP_NULL_OPERATOR;
	return;
}

// Debug print
void SMPGuard::Dump(void) const {
	SMP_msg("GUARD: ");
	PrintOperand(this->LeftOperand);
	SMP_msg(" %s ", OperatorText[this->GuardOp]);
	PrintOperand(this->RightOperand);
	SMP_msg(":");
	return;
} // end of SMPGuard::Dump()

// *****************************************************************
// Class SMPRegTransfer
// *****************************************************************
// Constructors
SMPRegTransfer::SMPRegTransfer(void) {
	this->Guard = NULL;
	this->LeftOperand.type = o_void;
	this->RightOperand.type = o_void;
	this->RTop.oper = SMP_NULL_OPERATOR;
	this->RTop.type = UNINIT;
#if SMP_TRACK_NONSPEC_OPER_TYPE
	this->RTop.NonSpeculativeType = UNINIT;
#endif
	this->RightRT = NULL;
	this->ParentInst = NULL;
	this->booleans1 = 0;
	return;
}

// Destructor
SMPRegTransfer::~SMPRegTransfer() {
#if 0
	SMP_msg("Destroying SMPRegTransfer.\n");
#endif
	if (NULL != this->RightRT)
		delete this->RightRT;
	if (NULL != this->Guard)
		delete this->Guard;
	return;
}

// Get the left operand, and normalize it if it is a stack operand.
op_t SMPRegTransfer::GetLeftOperand(void) const {
	op_t TempOp = this->LeftOperand;
	// AreDefsNormalized and AreUsesNormalized should always agree, but we
	//  use Defs for left operands and Uses for right operands, which is not
	//  strictly true, but there is no difference in results.
	if (this->ParentInst->AreDefsNormalized()) {
		ea_t InstAddr = this->ParentInst->GetAddr();
		TempOp = this->ParentInst->GetBlock()->GetFunc()->GetNormalizedOperand(InstAddr, TempOp);
	}
	return TempOp;
} // end of SMPRegTransfer::GetLeftOperand()

// Get the right operand, and normalize it if it is a stack operand.
op_t SMPRegTransfer::GetRightOperand(void) const {
	op_t TempOp = this->RightOperand;
	if (this->ParentInst->AreDefsNormalized()) {
		ea_t InstAddr = this->ParentInst->GetAddr();
		TempOp = this->ParentInst->GetBlock()->GetFunc()->GetNormalizedOperand(InstAddr, TempOp);
	}
	return TempOp;
} // end of SMPRegTransfer::GetRightOperand()

// Does RTL subtract a non-immediate value from the stack pointer?
bool SMPRegTransfer::IsAllocaRTL(void) {
	bool AllocaFound = false;
	// Search for the pattern: stack_pointer := stack_pointer minus non-immediate
	if ((SMP_ASSIGN == this->GetOperator()) && (this->HasRightSubTree())) {
		op_t DefOp = this->GetLeftOperand();
		if (DefOp.is_reg(MD_STACK_POINTER_REG)) {
			// We have the code pattern stack_pointer := ...
			SMPRegTransfer *RightRT = this->GetRightTree();
			SMPoperator RightOperator = RightRT->GetOperator();
			op_t RightDefOp = RightRT->GetLeftOperand();
			if ((RightDefOp.is_reg(MD_STACK_POINTER_REG)) && (SMP_SUBTRACT == RightOperator)) {
				// We have the code pattern stack_pointer := stack_pointer minus ...
				if (RightRT->HasRightSubTree()) {
					AllocaFound = true; // not an immediate rightop, whatever it is
				}
				else {
					op_t RightUseOp = RightRT->GetRightOperand();
					if (o_imm != RightUseOp.type) {
						AllocaFound = true;
					}
				}
			}
		}
	}
	return AllocaFound;
} // end of SMPRegTransfer::IsAllocaRTL()

// If we see add esp,immediate and the immediate value is large, then
//  some stupid hand-coded ASM is probably counting on an overflow, and
//  this is actually a subtraction from the stack pointer (i.e. it is an
//  addition of a negative number). We have to detect the signedness error
//  because IDA Pro treats the immediate operands as unsigned at all times.
#define STARS_ESP_ADDITION_OVERFLOW_THRESHOLD 0xf0000000

// Compute operand-dependent change in stack pointer value.
sval_t SMPRegTransfer::ComputeStackPointerAlteration(bool IsLeaveInstr, sval_t IncomingDelta, sval_t FramePtrDelta) {
	sval_t delta = 0;

	// Search for the pattern: stack_pointer := ...
	if (SMP_ASSIGN == this->GetOperator()) {
		op_t DefOp = this->GetLeftOperand();
		if (DefOp.is_reg(MD_STACK_POINTER_REG)) {
			// We have the code pattern stack_pointer := ...
			// We expect to find an overall RT structure of:
			//   stack_pointer := stack_pointer binaryoperator constant
			//  If the binaryoperator is addition or subtraction, then
			//   we use the constant to determine our return value.
			//  If the binaryoperator is a bitwise AND, then we return
			//   a special code. Delta is unknown but can probably be treated
			//   as zero, assuming that no stack-pointer-relative accesses to
			//   the stack region above the current stack pointer occur later.
			//  If we have a non-constant operand, we return an error code
			//   to indicate that we cannot compute the delta.
			//  If we don't have a binary operator, we return an error code,
			//   unless we find a stack frame deallocation:  esp := ebp
			if (!this->HasRightSubTree()) {
				op_t UseOp = this->GetRightOperand();
				if (UseOp.is_reg(MD_FRAME_POINTER_REG)) { // !!!!****!!!! Should validate that frame pointer reg is used as frame pointer
					// Found esp := ebp (deallocation of stack frame)
					delta = FramePtrDelta - IncomingDelta;
					assert(delta >= 0); // e.g. -4 - -12 => +8 for an 8-byte frame
				}
				else {
					// !!!!****!!!!**** Need to look up deltas for registers that
					//  were used to hold a copy of the stack pointer.
					// For now, just consider it an error.
					delta = (sval_t) SMP_STACK_DELTA_ERROR_CODE;
				}
			}
			else {
				SMPRegTransfer *RightRT = this->GetRightTree();
				SMPoperator RightOperator = RightRT->GetOperator();
				op_t RightDefOp = RightRT->GetLeftOperand();
				if (IsLeaveInstr) {
					// Found the RT esp := ebp + wordsize that adjusts the stack pointer
					//  for an x86 LEAVE instruction. esp := ebp is equivalent
					//  to esp := <esp when frame ptr was set up>, so delta becomes
					//  <esp delta when frame ptr was set up> - IncomingDelta + wordsize.
					assert(SMP_ADD == RightOperator);
					assert(!RightRT->HasRightSubTree());
					assert(RightDefOp.is_reg(X86_FRAME_POINTER_REG));
					delta = STARS_ISA_Bytewidth + FramePtrDelta - IncomingDelta;
				}
				else if (RightRT->HasRightSubTree()) {
					// Not the right code pattern; unknown effect on stack pointer.
					delta = (sval_t) SMP_STACK_DELTA_ERROR_CODE;
				}
				else if (!RightDefOp.is_reg(MD_STACK_POINTER_REG)) {
					// We have stack_pointer := something1 operator something2
					//  where something1 is not the stack_pointer. It might be
					//  the frame pointer, e.g. SP := FP-12. We can compute this
					//  stack delta because we know the delta when the FP was set up.
					op_t RightUseOp = RightRT->GetRightOperand();
					if (RightDefOp.is_reg(MD_FRAME_POINTER_REG) && (o_imm == RightUseOp.type)) {
						// We have SP := FP operator immediate
						delta = FramePtrDelta - IncomingDelta; // partial computation: SP := BP
						assert(delta >= 0); // e.g. -4 - -12 => +8 for an 8-byte frame
						if (SMP_ADD == RightOperator) {
							delta += RightUseOp.value;
						}
						else if (SMP_SUBTRACT == RightOperator) {
							delta -= RightUseOp.value;
						}
						else {
							// Not the right code pattern; unknown effect on stack pointer.
							delta = (sval_t) SMP_STACK_DELTA_ERROR_CODE;
						}
					}
					else {
						// !!!!****!!!!**** Need to look up deltas for registers that
						//  were used to hold a copy of the stack pointer.
						// For now, just consider it an error.
						delta = (sval_t) SMP_STACK_DELTA_ERROR_CODE;
					}
				}
				else {
					// We have stack_pointer := stack_pointer operator ...
					op_t RightUseOp = RightRT->GetRightOperand();
					// Check the operator
					if (SMP_BITWISE_AND == RightOperator) {
						delta = (sval_t) SMP_STACK_POINTER_BITWISE_AND_CODE;
					}
					else {
						if (o_imm != RightUseOp.type) {
							// Don't know how to deal with adding non-constant to stack pointer
							delta = (sval_t) SMP_STACK_DELTA_ERROR_CODE;
						}
						else if (SMP_ADD == RightOperator) {
							delta = (sval_t) RightUseOp.value;
							if (delta > STARS_ESP_ADDITION_OVERFLOW_THRESHOLD) {
								// Really a subtraction via addition of a negative.
								//  E.g. add esp, 0xfffffff0 is sub esp,16
								int32 TempDelta = (int32) (delta & 0xffffffff);
								delta = (sval_t) TempDelta;
							}
						}
						else if (SMP_SUBTRACT == RightOperator) {
							if (RightUseOp.value > STARS_ESP_ADDITION_OVERFLOW_THRESHOLD) {
								// Really a subtraction via addition of a negative.
								//  E.g. add esp, 0xfffffff0 is sub esp,16
								int32 TempDelta = (int32) (RightUseOp.value & 0xffffffff);
								delta = (0 - ((sval_t) TempDelta));
							}
							else {
								delta = (0 - ((sval_t) RightUseOp.value));
							}
						}
						else {
							delta = (sval_t) SMP_STACK_DELTA_ERROR_CODE;
						}
					}
				}
			}
		}
	}
	return delta;
} // end of SMPRegTransfer::ComputeStackPointerAlteration()

// Evaluate constant expressions for SCCP algorithm
struct STARS_SCCP_Const_Struct SMPRegTransfer::SCCPEvaluateRTLConsts(list<pair<int, int> > &SSAWorkList) {
	struct STARS_SCCP_Const_Struct ReturnConstStruct;
	ReturnConstStruct.ConstType = STARS_CONST_TOP; // default value

	SMPoperator CurrOper = this->GetOperator();
	switch (CurrOper) {
		case SMP_ASSIGN:
		{
			op_t LeftOp = this->GetLeftOperand();
			if (o_reg != LeftOp.type) {
				break; // Only looking to update registers now
			}
			bool NewValueAvailable;
			if (this->HasRightSubTree()) {
				ReturnConstStruct = this->GetRightTree()->SCCPEvaluateRTLConsts(SSAWorkList); // recurse into right subtree
			}
			else {
				op_t RightOp = this->GetRightOperand();
				this->ParentInst->SCCPFetchConstUseValue(RightOp, ReturnConstStruct);
			}
			NewValueAvailable = (STARS_CONST_TOP != ReturnConstStruct.ConstType);
			// Update const map entry for DEF
			if (NewValueAvailable) {
				CanonicalizeOpnd(LeftOp);
				struct STARS_SCCP_Const_Struct OldConstStruct;
				OldConstStruct.ConstType = STARS_CONST_TOP;
				set<DefOrUse, LessDefUse>::iterator DefIter = this->ParentInst->FindDef(LeftOp);
				if (DefIter != this->ParentInst->GetLastDef()) {
					int DefSSANum = DefIter->GetSSANum();
					int DefHashValue = HashGlobalNameAndSSA(LeftOp, DefSSANum);
					bool LocalName = this->ParentInst->GetBlock()->IsLocalName(LeftOp);
					this->ParentInst->SCCPFetchConstDefValue(LeftOp, OldConstStruct);
					bool HasOldValue = (STARS_CONST_TOP != OldConstStruct.ConstType);

					if (HasOldValue) { // must perform type lattice meet operation to update ReturnConstStruct
						STARSConstantTypeMeet(OldConstStruct, ReturnConstStruct);
					}
					if (ReturnConstStruct.ConstType != OldConstStruct.ConstType) { // type change
						map<int, struct STARS_SCCP_Const_Struct>::iterator NewConstIter;
						if (LocalName) {
							NewConstIter = this->ParentInst->GetBlock()->InsertLocalConstValue(DefHashValue, ReturnConstStruct);
						}
						else {
							NewConstIter = this->ParentInst->GetBlock()->GetFunc()->InsertGlobalConstValue(DefHashValue, ReturnConstStruct);
						}
						// Propagate along SSA edges.
						int BlockNum = this->ParentInst->GetBlock()->GetNumber();
						pair<int, int> SSAEdge(BlockNum, DefHashValue);
						SSAWorkList.push_back(SSAEdge);
					}
				}
			}
			break; // end case for SMP_ASSIGN
		}

		case SMP_ADD:
		case SMP_SUBTRACT:
		case SMP_U_MULTIPLY:
		case SMP_S_MULTIPLY:
		case SMP_BITWISE_AND:
		case SMP_BITWISE_OR:
		case SMP_BITWISE_XOR:
		case SMP_BITWISE_AND_NOT:
		case SMP_S_COMPARE:
		case SMP_U_COMPARE:
			// binary arithmetic operators
			// We will initially deal with the simple case: The comparison is of a LeftOp register to a RightOp register or immediate.
			//  If the result is definitely zero, we return zero as the const value (presumably to be put into the zero flag).
			if (!(this->HasRightSubTree())) { // simple compare of two operands should always be the case
				op_t LeftOp = this->GetLeftOperand();
				op_t RightOp = this->GetRightOperand();
				if ((LeftOp.type == o_reg) && ((RightOp.type == o_reg) || (RightOp.type == o_imm))) {
					CanonicalizeOpnd(LeftOp);
					CanonicalizeOpnd(RightOp);
					struct STARS_SCCP_Const_Struct LeftValue, RightValue;

					this->ParentInst->SCCPFetchConstUseValue(LeftOp, LeftValue);
					bool LeftValueAvailable = (STARS_CONST_TOP != LeftValue.ConstType);
					if (STARS_CONST_BOTTOM == LeftValue.ConstType) {
						ReturnConstStruct = LeftValue;
						break; // right operand is irrelevant if left is BOTTOM
					}

					bool RightValueAvailable = false;
					if (o_imm == RightOp.type) {
						RightValueAvailable = true;
						RightValue.ConstType = STARS_CONST_HAS_VALUE;
						RightValue.ConstValue = RightOp.value;
					}
					else {
						this->ParentInst->SCCPFetchConstUseValue(RightOp, RightValue);
						RightValueAvailable = (STARS_CONST_TOP != RightValue.ConstType);
						if (STARS_CONST_BOTTOM == RightValue.ConstType) {
							ReturnConstStruct = RightValue;
							break; // left operand is irrelevant if right is BOTTOM
						}
					}

					if (LeftValueAvailable && RightValueAvailable) {
						// Apply the operator to the values.
						ReturnConstStruct.ConstType = STARS_CONST_HAS_VALUE;
						uval_t TestValue;
						bool CompareFlag = ((CurrOper == SMP_S_COMPARE) || (CurrOper == SMP_U_COMPARE));
						if (CurrOper == SMP_ADD) {
							TestValue = (LeftValue.ConstValue + RightValue.ConstValue);
						}
						else if ((CurrOper == SMP_U_MULTIPLY) || (CurrOper == SMP_S_MULTIPLY)) {
							TestValue = (LeftValue.ConstValue * RightValue.ConstValue);
						}
						else if ((CurrOper == SMP_SUBTRACT) || (CurrOper == SMP_S_COMPARE)) {
							// Signed compare is a subtraction operation
							TestValue = (LeftValue.ConstValue - RightValue.ConstValue);
						}
						else if ((CurrOper == SMP_U_COMPARE) || (CurrOper == SMP_BITWISE_AND)) {
							// Unsigned compare is a bitwise AND operation
							TestValue = (LeftValue.ConstValue & RightValue.ConstValue);
						}
						else if (CurrOper == SMP_BITWISE_OR) {
							TestValue = (LeftValue.ConstValue | RightValue.ConstValue);
						}
						else if (CurrOper == SMP_BITWISE_XOR) {
							TestValue = (LeftValue.ConstValue ^ RightValue.ConstValue);
						}
						else if (CurrOper == SMP_BITWISE_AND_NOT) {
							TestValue = (LeftValue.ConstValue & (~(RightValue.ConstValue)));
						}
						else {
							break; // should be unreachable
						}
						if ((0 != TestValue) && CompareFlag) {
							TestValue = 1; // i.e. zero flag will be set to false
						}
						ReturnConstStruct.ConstValue = TestValue;
					}
				} // end if two regs, or one reg and one immediate
			} // end if no right subtree
			break; // end of signed and unsigned compare operators case

		default:
			break; // ignore
	} // end switch(CurrOper)

	return ReturnConstStruct;
} // end of SMPRegTransfer::SCCPEvaluateRTLConsts()

// Debug print
void SMPRegTransfer::Dump(void) const {
	if (NULL != this->Guard)
		this->Guard->Dump();
	// Left operand
	if (o_void != this->LeftOperand.type)
		PrintOperand(this->LeftOperand);
	// Then the operator
	SMP_msg(" %s ", OperatorText[this->GetOperator()]);
	// then the right operand or subtree
	if (this->HasRightSubTree())
		this->GetRightTree()->Dump();
	else if (o_void != this->RightOperand.type)
		PrintOperand(this->RightOperand);
	return;
} // end of SMPRegTransfer::Dump()

void SMPRegTransfer::EmitSPARKAda(void) const {
	SMPoperator CurrOper = this->GetOperator();
	switch (CurrOper) {
		case SMP_NULL_OPERATOR: 
		case SMP_INPUT:  // input from port
		case SMP_OUTPUT: // output to port
		case SMP_ROTATE_LEFT_CARRY: // rotate left through carry
		case SMP_ROTATE_RIGHT_CARRY: // rotate right through carry
			SMP_msg("ERROR: SPARK: Cannot translate operator: ");
			SMP_msg(" %s \n", OperatorText[this->GetOperator()]);
			break;

		case SMP_CALL:  // CALL instruction
			break;

		case SMP_ADDRESS_OF: // take effective address
			break;

		case SMP_U_LEFT_SHIFT: // unsigned left shift
			// Ada: result := Interfaces.Shift_Left(Value => LeftOperand, Amount => RightOperand);
		case SMP_U_RIGHT_SHIFT: // unsigned right shift
			// Ada: result := Interfaces.Shift_Right(Value => LeftOperand, Amount => RightOperand);
		case SMP_S_RIGHT_SHIFT: // signed right shift
			// Ada: result := Interfaces.Shift_Right_Arithmetic(Value => LeftOperand, Amount => RightOperand);
		case SMP_ROTATE_LEFT:
			// Ada: result := Interfaces.Rotate_Left(Value => LeftOperand, Amount => RightOperand);
		case SMP_ROTATE_RIGHT:
			// Ada: result := Interfaces.Rotate_Right(Value => LeftOperand, Amount => RightOperand);
			PrintSPARKAdaOperator(CurrOper, ZST_SPARKSourceFile);
			SMP_fprintf(ZST_SPARKSourceFile, "(Value => ");
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			SMP_fprintf(ZST_SPARKSourceFile, ", Amount => ");
			this->EmitSPARKAdaForRHS();
			SMP_fprintf(ZST_SPARKSourceFile, ")\n");
			break;

		case SMP_S_LEFT_SHIFT: // signed left shift
			// Need to convert to multiplication, using exponentiation base 2 for multiplier
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			SMP_fprintf(ZST_SPARKSourceFile, " * (2 ** ");
			this->EmitSPARKAdaForRHS();
			SMP_fprintf(ZST_SPARKSourceFile, ")");
			break;

		case SMP_DECREMENT:
		case SMP_INCREMENT:
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			PrintSPARKAdaOperator(CurrOper, ZST_SPARKSourceFile); // + 1 or - 1
			break;

		case SMP_ADD:
		case SMP_SUBTRACT:
		case SMP_BITWISE_AND:
		case SMP_BITWISE_OR:
		case SMP_BITWISE_XOR:
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			PrintSPARKAdaOperator(CurrOper, ZST_SPARKSourceFile); // +
			this->EmitSPARKAdaForRHS();
			break;

		case SMP_ADD_CARRY:   // add with carry
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			SMP_fprintf(ZST_SPARKSourceFile, " + ");
			this->EmitSPARKAdaForRHS();
			SMP_fprintf(ZST_SPARKSourceFile, " + CarryFlag");
			break;

		case SMP_SUBTRACT_BORROW:  // subtract with borrow
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			SMP_fprintf(ZST_SPARKSourceFile, " - ");
			this->EmitSPARKAdaForRHS();
			SMP_fprintf(ZST_SPARKSourceFile, " - CarryFlag");
			break;

		case SMP_U_MULTIPLY:
		case SMP_S_MULTIPLY:
		case SMP_U_DIVIDE:
		case SMP_S_DIVIDE:
		case SMP_U_REMAINDER:
			break;

		case SMP_SIGN_EXTEND:
		case SMP_ZERO_EXTEND:
			break;

		case SMP_ASSIGN:
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			SMP_fprintf(ZST_SPARKSourceFile, ":= ");
			this->EmitSPARKAdaForRHS();
			SMP_fprintf(ZST_SPARKSourceFile, ";\n");
			break;

		case SMP_BITWISE_NOT: // unary operator
		case SMP_NEGATE:    // unary negation
			PrintSPARKAdaOperator(CurrOper, ZST_SPARKSourceFile); // not
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			break;

		case SMP_BITWISE_AND_NOT:
			PrintSPARKAdaOperand(this->GetLeftOperand(), ZST_SPARKSourceFile);
			PrintSPARKAdaOperator(CurrOper, ZST_SPARKSourceFile); // "and (not"
			this->EmitSPARKAdaForRHS();
			SMP_fprintf(ZST_SPARKSourceFile, ")");
			break;

		case SMP_S_COMPARE: // signed compare (subtraction-based)
		case SMP_U_COMPARE: // unsigned compare (AND-based)
		case SMP_GENERAL_COMPARE: // comparisons of packed data, strings, signed, unsigned depending on control words
		case SMP_LESS_THAN: // boolean test operators
		case SMP_GREATER_THAN:
		case SMP_LESS_EQUAL:
		case SMP_GREATER_EQUAL:
		case SMP_EQUAL:
		case SMP_NOT_EQUAL:
		case SMP_LOGICAL_AND:
		case SMP_LOGICAL_OR:
		case SMP_UNARY_NUMERIC_OPERATION:  // miscellaneous; produces NUMERIC result
		case SMP_BINARY_NUMERIC_OPERATION:  // miscellaneous; produces NUMERIC result
		case SMP_SYSTEM_OPERATION:   // for instructions such as CPUID, RDTSC, etc.; NUMERIC
		case SMP_UNARY_FLOATING_ARITHMETIC:  // all the same to our type system; all NUMERIC
		case SMP_BINARY_FLOATING_ARITHMETIC:  // all the same to our type system; all NUMERIC