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_CALL_TRASHES_REGS 1  // Add DEFs of caller-saved regs to CALL instructions
#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;