SMPFunction.h

/*
 * SMPFunction.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/
 *
 */

#ifndef SMPFUNCTION_H
#define SMPFUNCTION_H 1

// SMPFunction.h
//
// This header defines the interfaces needed for analyzing functions, performing live variable analysis,
//  putting code into SSA form, etc.

#include <utility>
#include <list>
#include <vector>
#include <map>
#include <set>

#include <cstddef>
#include <stdio.h>

class SMPProgram;	// forward declaration so we can declare a pointer to an SMPProgram
class STARS_IDA_Function_t;
class STARS_IRDB_Function_t;

#include "interfaces/STARSTypes.h"
#include "interfaces/SMPDBInterface.h"

#include "base/SMPDataFlowAnalysis.h"
#include "base/SMPInstr.h"
#include "base/SMPBasicBlock.h"
#include "base/ProfilerInformation.h"


#define SMP_DEBUG_STACK_GRANULARITY 0

// What is the default change to the stack pointer for a function?
//  NOTE: When we start handling different calling conventions beyond
//  the gcc model, we will have to make this a variable that gets
//  initialized.
#define CALLING_CONVENTION_DEFAULT_FUNCTION_STACK_DELTA global_STARS_program->GetSTARS_ISA_Bytewidth()

// What is the default stack delta from function entry to stack frame allocation?
//  This would only be used in resolving phase-ordering problems, and should be 
//  eliminated if possible.
#define CALLING_CONVENTION_DEFAULT_PREFRAMEALLOC_STACK_DELTA (-(global_STARS_program->GetSTARS_ISA_Bytewidth()))

// What default value should we assign to alloca stack frame allocations?
#define STARS_DEFAULT_ALLOCA_SIZE -32

// Use IDA info for switch tables to link indirect jumps to successor blocks?
#define SMP_USE_SWITCH_TABLE_INFO 1

// Detect function code fragments that are not shared with another function.
#define STARS_FIND_UNSHARED_CHUNKS 1

// Find and fix missing IDA Pro code xrefs.
#define STARS_AUDIT_JUMP_XREFS 0
#define STARS_AUDIT_INDIR_JUMP_XREFS 1

// We can decide if conservative analysis of memory writes will cause us to avoid fast returns,
//  or merely shadow the return address.
#define STARS_CONSERVATIVE_FAST_RETURNS 0

// Emit CS: or FS: or GS: etc. segment reg prefix if found in operand
#define STARS_SPARK_EMIT_SEGMENT_REGS 0   

struct LocalVar {
	char VarName[MAXSMPVARSTR];
	long offset;
	std::size_t size;
};

// Comparison function for sorting.
bool LocalVarCompare(const LocalVar &LV1, const LocalVar &LV2);

enum StackAccessType {
	STARS_STACK_UNKNOWN = 0,
	STARS_STACK_INARG = 1,
	STARS_STACK_RETURN_ADDRESS = 2,
	STARS_STACK_CALLEE_SAVED_REG = 3,
	STARS_STACK_LOCAL_FRAME = 4,
	STARS_STACK_OUTARG = 5    // could be part of LOCAL_FRAME initially, then changed when we detect usage as OUTARG
};

// Entry for each byte address in the stack frame
struct StackFrameEntry {
	struct LocalVar *VarPtr;  // LocalVar that includes this offset
	long offset;  // offset relative to incoming stack pointer
	bool Read;    // was this entry ever read by an instruction?
	bool Written; // was this entry ever written by an instruction?
	bool AddressTaken; // did this entry have its address taken?
	bool ESPRelativeAccess; // ever accessed by ESP+const?
	bool EBPRelativeAccess; // ever accessed by EBP-const? (only if UseFP)
	bool IndexedAccess;  // index reg of unknown value added to the base address
	StackAccessType EntryType; // inference based on location and accessing instructions
};

enum FuncType { 
	FUNC_UNKNOWN = 0,
	FUNC_SAFE = 1,
	FUNC_UNSAFE = 2,
	FUNC_SAFE_IF_CALLEES_ARE_SAFE = 3
};

enum UnsafeFastReturnReason {
	SAFE_FAST_RETURN = 0,
	UNSAFE_RETURN_ADDRESS = 1,
	RETURN_ADDRESS_WRITE = 2,
	RETURN_ADDRESS_READ = 4,
	INDIRECTLY_CALLED = 8,
	NO_CALLERS = 16,
	TAIL_CALL_TARGET = 32,
	RAUNSAFE_CALLEES = 64,
	MAKES_TAIL_CALL = 128,
	MULTIPLE_ENTRY_POINTS = 256,
	UNRESOLVED_INDIR_JUMP = 512,
	EH_FRAME_ENTRY = 1024
};

// For queries about the type of sink that a DEF eventually flows into.
enum SinkSearchType {
	STARS_SINK_NONE = 0,
	STARS_SINK_MEMWRITE = 1,
	STARS_SINK_LOOP_CONDITION = 2,
	STARS_SINK_CALL = 4,
	STARS_SINK_RETURN = 8
};

// SPARK Ada recursive descent translation stack type; what we are currently translating
//  is on top.
enum SPARKTranslationCFType {
	SPARK_INITIAL_BLOCK = 0,
	SPARK_THEN_CLAUSE = 1,
	SPARK_ELSE_CLAUSE = 2,
	SPARK_SWITCH = 3,
	SPARK_LOOP = 4
};

// Loop types for structuring and decompilation
#define STARS_LOOP_TYPE_UNKNOWN 0
#define STARS_TOP_TESTING_LOOP 1
#define STARS_BOTTOM_TESTING_LOOP 2
#define STARS_INFINITE_OR_MIDDLE_TESTING_LOOP 3
#define STARS_CONSTANT_ITERATIONS_TOP_TESTING_LOOP 4

// A struct used to describe the comparison used to exit a loop or loop back.
//  For loops that could not be analyzed, CompareOperator is SMP_NULL_OPERATOR.
struct LoopComparison {
	DefOrUse Operand1;
	DefOrUse Operand2;
	STARS_ea_t CompareAddr;  // could be address of a decrement inst, for the decrement+COND_BRANCH type of loop
	SMPoperator CompareOperator;
	bool ExitsLoop;  // comparison could be used to loop back, in which case invert to exit loop.
};

// A struct to describe the triple (Multiplier * BasicInductionVar + Addend) that can be
//  used to define any induction variable. The basic induction variable of a family can
//  be represented with a Multiplier of one and an Addend of zero.
struct InductionVarTriple {
	DefOrUse InductionVar;
	DefOrUse Multiplier;
	DefOrUse Addend;
	bool SubtractAddend;  // Multiplier * BasicInductionVar - Addend
};

// Are the operands, SSA numbers, and SubtractAddend fields identical?
bool EqualInductionVars(const InductionVarTriple &IV1, const InductionVarTriple &IV2);

// Dependent induction variable: At DIVDefAddr, DIV is defined by an operation IVExpr performed upon an earlier IV in the family.
struct DependentInductionVar {
	struct InductionVarTriple IVExpr;
	DefOrUse DIV;
	STARS_ea_t DIVDefAddr;
	STARSExpression *DIVInitExpr;
	STARSExpression *DIVLimitExpr;
};