SMPFunction.cpp 168.03 KiB
/*
* SMPFunction.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/
*
*/
//
// SMPFunction.cpp
//
// This module performs the fundamental data flow analyses needed for the
// SMP project (Software Memory Protection) at the function level.
//
#include <utility>
#include <list>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <pro.h>
#include <assert.h>
#include <ida.hpp>
#include <idp.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <allins.hpp>
#include <intel.hpp>
#include <name.hpp>
#include "SMPDataFlowAnalysis.h"
#include "SMPStaticAnalyzer.h"
#include "SMPFunction.h"
#include "SMPBasicBlock.h"
#include "SMPInstr.h"
// Set to 1 for debugging output
#define SMP_DEBUG 1
#define SMP_DEBUG2 0 // verbose
#define SMP_DEBUG3 0 // verbose
#define SMP_DEBUG_CONTROLFLOW 0 // tells what processing stage is entered
#define SMP_DEBUG_XOR 0
#define SMP_DEBUG_CHUNKS 1 // tracking down tail chunks for functions
#define SMP_DEBUG_FRAMEFIXUP 0
#define SMP_DEBUG_DATAFLOW 0
#define SMP_DEBUG_DATAFLOW_VERBOSE 0#define SMP_DEBUG_TYPE_INFERENCE 0
#define SMP_DEBUG_PROFILED_TYPE_INFERENCE 0
#define SMP_DEBUG_STACK_GRANULARITY 0
#define SMP_DEBUG_FUNC 0
#define SMP_VERBOSE_DEBUG_FUNC 0
#define SMP_DEBUG_BUILD_RTL 1 // leave this on; serious errors reported
#define SMP_DEBUG_UNINITIALIZED_SSA_NAMES 1
#define SMP_WARN_UNUSED_DEFS 0
#define SMP_DEBUG_SWITCH_TABLE_INFO 0
#define SMP_OPTIMIZE_BLOCK_PROFILING 0
// Compute LVA/SSA or not? Turn it off for NICECAP demo on 31-JAN-2008
#define SMP_COMPUTE_LVA_SSA 1
// Compute fine-grained stack boundaries?
#define SMP_COMPUTE_STACK_GRANULARITY 1
// Insert a floating no-op instruction at top of each function to hold SSA DEFs
// of LiveIn names?
#define SMP_USE_SSA_FNOP_MARKER 1
// Use conditional type propagation on phi functions
#define SMP_CONDITIONAL_TYPE_PROPAGATION 0
// Kludges to fix IDA Pro 5.2 errors in cc1.ncexe
#define SMP_IDAPRO52_WORKAROUND 0
// Basic block number 0 is the top of the CFG lattice.
#define SMP_TOP_BLOCK 0
// Set SharedTailChunks to TRUE for entire printf family
// After we restructure the parent/tail structure of the database, this
// will go away.
#define KLUDGE_VFPRINTF_FAMILY 1
// Used for binary search by function number in SMPStaticAnalyzer.cpp
// to trigger debugging output and find which instruction in which
// function is causing a crash.
bool SMPBinaryDebug = false;
using namespace std;
// helper function to determine if an object is in a vector
template <class T>
bool vector_exists(const T &item, const vector<T> &vec) {
for (size_t i = 0; i < vec.size(); ++i) {
if (vec[i] == item)
return true;
}
return false;
}
// *****************************************************************
// Class SMPFunction
// *****************************************************************
// Constructor
SMPFunction::SMPFunction(func_t *Info, SMPProgram* pgm) {
this->Program = pgm;
this->FuncInfo = *Info;
this->FirstEA = this->FuncInfo.startEA;
this->FuncName[0] = '\0';
this->BlockCount = 0;
this->UseFP = false;
this->StaticFunc = false;
this->LibFunc = false;
this->IndirectCalls = false;
this->UnresolvedIndirectCalls = false;
this->IndirectJumps = false; this->UnresolvedIndirectJumps = false;
this->DirectlyRecursive = false;
this->SharedChunks = false;
this->CallsAlloca = false;
this->AnalyzedSP = false;
this->BuiltRTLs = false;
#if 1 // default to unsafe
this->SafeFunc = false;
this->SpecSafeFunc = false;
this->SafeCallee = false;
this->SpecSafeCallee = false;
#else // default to safe
this->SafeFunc = true;
this->SpecSafeFunc = true;
this->SafeCallee = true;
this->SpecSafeCallee = true;
#endif
this->WritesAboveRA = false;
this->NeedsStackReferent = true;
this->SpecNeedsStackReferent = true;
this->HasIndirectWrites = false;
this->OutgoingArgsComputed = false;
this->OutgoingArgsSize = 0;
this->TypedDefs = 0;
this->UntypedDefs = 0;
this->TypedPhiDefs = 0;
this->UntypedPhiDefs = 0;
this->SafeBlocks = 0;
this->UnsafeBlocks = 0;
this->Size = 0;
this->LocalVarsSize = 0;
this->CalleeSavedRegsSize = 0;
this->RetAddrSize = 0;
this->IncomingArgsSize = 0;
this->OutgoingArgsSize = 0;
this->LocalVarsAllocInstr = BADADDR;
this->LocalVarsDeallocInstr = BADADDR;
this->AllocPointDelta = 0;
this->MinStackDelta = 0;
this->LocalVarOffsetLimit = 0;
this->ReturnAddrStatus = FUNC_UNKNOWN;
this->SetIsSpeculative(false);
this->Instrs.clear();
this->Blocks.clear();
this->DirectCallTargets.clear();
this->IndirectCallTargets.clear();
this->AllCallTargets.clear();
this->AllCallSources.clear();
this->InstBlockMap.clear();
this->RPOBlocks.clear();
this->IDom.clear();
this->DomTree.clear();
this->GlobalNames.clear();
this->BlocksDefinedIn.clear();
this->SSACounter.clear();
this->SSAStack.clear();
this->LocalVarTable.clear();
this->StackFrameMap.clear();
this->SavedRegLoc.clear();
this->ReturnRegTypes.clear();
this->LiveInSet.clear();
this->LiveOutSet.clear();
this->KillSet.clear();
for (int RegIndex = R_ax; RegIndex <= R_di; ++RegIndex) {
this->SavedRegLoc.push_back(0); // zero offset means reg not saved
this->ReturnRegTypes.push_back(UNINIT);
}
return;
} // end of SMPFunction() constructor
// Get a non-stale pointer to the func_t info for the current function.
func_t *SMPFunction::GetFuncInfo(void) {
func_t *myPtr = get_func(this->FirstEA);
assert(NULL != myPtr);
return myPtr;
}
// Reset the Processed flags in all blocks to false.
void SMPFunction::ResetProcessedBlocks(void) {
list<SMPBasicBlock>::iterator CurrBlock;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
CurrBlock->SetProcessed(false);
}
return;
} // end of SMPFunction::ResetProcessedBlocks()
// Return an iterator for the beginning of the LiveInSet.
set<op_t, LessOp>::iterator SMPFunction::GetFirstLiveIn(void) {
return this->LiveInSet.begin();
} // end of SMPBasicBlock::GetFirstLiveIn()
// Get termination iterator marker for the LiveIn set, for use by predecessors.
set<op_t, LessOp>::iterator SMPFunction::GetLastLiveIn(void) {
return this->LiveInSet.end();
}
// Get iterator for the start of the LiveOut set.
set<op_t, LessOp>::iterator SMPFunction::GetFirstLiveOut(void) {
return this->LiveOutSet.begin();
}
// Get termination iterator marker for the LiveOut set.
set<op_t, LessOp>::iterator SMPFunction::GetLastLiveOut(void) {
return this->LiveOutSet.end();
}
// Get iterator for the start of the VarKill set.
set<op_t, LessOp>::iterator SMPFunction::GetFirstVarKill(void) {
return this->KillSet.begin();
}
// Get termination iterator marker for the VarKill set.
set<op_t, LessOp>::iterator SMPFunction::GetLastVarKill(void) {
return this->KillSet.end();
}
// Add a caller to the list of all callers of this function.
void SMPFunction::AddCallSource(ea_t addr) {
// Convert call instruction address to beginning address of the caller.
func_t *FuncInfo = get_func(addr);
if (NULL == FuncInfo) {
msg("SERIOUS WARNING: Call location %x not in a function.\n", addr);
return;
}
ea_t FirstAddr = FuncInfo->startEA;
assert(BADADDR != FirstAddr);
this->AllCallSources.insert(FirstAddr);
return;
} // end of SMPFunction::AddCallSource()
// Figure out the different regions of the stack frame, and find the
// instructions that allocate and deallocate the local variables space
// on the stack frame.
// The stack frame info will be used to emit stack
// annotations when Analyze() reaches the stack allocation
// instruction that sets aside space for local vars.// Set the address of the instruction at which these
// annotations should be emitted. This should normally
// be an instruction such as: sub esp,48
// However, for a function with no local variables at all,
// we will need to determine which instruction should be
// considered to be the final instruction of the function
// prologue and return its address.
// Likewise, we find the stack deallocating instruction in
// the function epilogue.
void SMPFunction::SetStackFrameInfo(void) {
bool FoundAllocInstr = false;
bool FoundDeallocInstr = false;
bool DebugFlag = false;
#if SMP_DEBUG_FRAMEFIXUP
DebugFlag |= (0 == strcmp(".init_proc", this->GetFuncName()));
#endif
// The sizes of the three regions of the stack frame other than the
// return address are stored in the function structure.
this->LocalVarsSize = this->FuncInfo.frsize;
this->CalleeSavedRegsSize = this->FuncInfo.frregs;
this->IncomingArgsSize = this->FuncInfo.argsize;
// The return address size can be obtained in a machine independent
// way by calling get_frame_retsize().
this->RetAddrSize = get_frame_retsize(this->GetFuncInfo());
// IDA Pro has trouble with functions that do not have any local
// variables. Unfortunately, the C library has plenty of these
// functions. IDA usually claims that frregs is zero and frsize
// is N, when the values should have been reversed. We can attempt
// to detect this and fix it.
bool FrameInfoFixed = this->MDFixFrameInfo();
#if SMP_DEBUG_CONTROLFLOW
msg("Returned from MDFixFrameInfo()\n");
#endif
#if SMP_DEBUG_FRAMEFIXUP
if (FrameInfoFixed) {
msg("Fixed stack frame size info: %s\n", this->FuncName);
SMPBasicBlock CurrBlock = this->Blocks.front();
msg("First basic block:\n");
for (list<list<SMPInstr>::iterator>::iterator CurrInstr = CurrBlock.GetFirstInstr();
CurrInstr != CurrBlock.GetLastInstr();
++CurrInstr) {
msg("%s\n", (*CurrInstr)->GetDisasm());
}
}
#endif
// Now, if LocalVarsSize is not zero, we need to find the instruction
// in the function prologue that allocates space on the stack for
// local vars. This code could be made more robust in the future
// by matching LocalVarsSize to the immediate value in the allocation
// instruction. However, IDA Pro is sometimes a little off on this
// number. **!!**
if (0 < this->LocalVarsSize) {
if (DebugFlag) msg("Searching for alloc and dealloc\n");
for (list<SMPInstr>::iterator CurrInstr = this->Instrs.begin();
CurrInstr != this->Instrs.end();
++CurrInstr) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInstr)
continue; // skip marker instruction
#endif
ea_t addr = CurrInstr->GetAddr();
// Keep the most recent instruction in the DeallocInstr
// in case we reach the return without seeing a dealloc. if (!FoundDeallocInstr) {
this->LocalVarsDeallocInstr = addr;
}
if (!FoundAllocInstr
&& CurrInstr->MDIsFrameAllocInstr()) {
#if SMP_DEBUG_CONTROLFLOW
msg("Returned from MDIsFrameAllocInstr()\n");
#endif
this->LocalVarsAllocInstr = addr;
FoundAllocInstr = true;
if (DebugFlag) msg("Found alloc: %s\n", CurrInstr->GetDisasm());
// As soon as we have found the local vars allocation,
// we can try to fix incorrect sets of UseFP by IDA.
// NOTE: We might want to extend this in the future to
// handle functions that have no locals. **!!**
bool FixedUseFP = MDFixUseFP();
#if SMP_DEBUG_CONTROLFLOW
msg("Returned from MDFixUseFP()\n");
#endif
#if SMP_DEBUG_FRAMEFIXUP
if (FixedUseFP) {
msg("Fixed UseFP in %s\n", this->FuncName);
}
#endif
}
else if (FoundAllocInstr) {
// We can now start searching for the DeallocInstr.
if (CurrInstr->MDIsFrameDeallocInstr(UseFP, this->LocalVarsSize)) {
// Keep saving the most recent addr that looks
// like the DeallocInstr until we reach the
// end of the function. Last one to look like
// it is used as the DeallocInstr.
#if SMP_DEBUG_CONTROLFLOW
msg("Returned from MDIsFrameDeallocInstr()\n");
#endif
this->LocalVarsDeallocInstr = addr;
FoundDeallocInstr = true;
}
else {
if (DebugFlag) msg("Not dealloc: %s\n", CurrInstr->GetDisasm());
}
}
} // end for (list<SMPInstr>::iterator CurrInstr ... )
if (!FoundAllocInstr) {
// Could not find the frame allocating instruction. Bad.
// See if we can find the point at which the stack allocation reaches
// a total of FuncInfo.frsize+frregs, regardless of whether it happened by push
// instructions or some other means.
this->LocalVarsAllocInstr = this->FindAllocPoint(this->FuncInfo.frsize + this->FuncInfo.frregs);
#if SMP_DEBUG_CONTROLFLOW
msg("Returned from FindAllocPoint()\n");
#endif
#if SMP_DEBUG_FRAMEFIXUP
if (BADADDR == this->LocalVarsAllocInstr) {
msg("ERROR: Could not find stack frame allocation in %s\n",
FuncName);
msg("LocalVarsSize: %d SavedRegsSize: %d ArgsSize: %d\n",
LocalVarsSize, CalleeSavedRegsSize, IncomingArgsSize);
}
else {
msg("FindAllocPoint found %x for function %s\n",
this->LocalVarsAllocInstr, this->GetFuncName());
}
#endif
}
#if SMP_DEBUG_FRAMEFIXUP
if (!FoundDeallocInstr) {
// Could not find the frame deallocating instruction. Bad.
// Emit diagnostic and use the last instruction in the // function.
msg("ERROR: Could not find stack frame deallocation in %s\n",
FuncName);
}
#endif
}
// else LocalVarsSize was zero, meaning that we need to search
// for the end of the function prologue code and emit stack frame
// annotations from that address (i.e. this method returns that
// address). We will approximate this by finding the end of the
// sequence of PUSH instructions at the beginning of the function.
// The last PUSH instruction should be the last callee-save-reg
// instruction. We can make this more robust in the future by
// making sure that we do not count a PUSH of anything other than
// a register. **!!**
// NOTE: 2nd prologue instr is usually mov ebp,esp
// THE ASSUMPTION THAT WE HAVE ONLY PUSH INSTRUCTIONS BEFORE
// THE ALLOCATING INSTR IS ONLY TRUE WHEN LOCALVARSSIZE == 0;
else {
ea_t SaveAddr = this->FuncInfo.startEA;
for (list<SMPInstr>::iterator CurrInstr = this->Instrs.begin();
CurrInstr != this->Instrs.end();
++CurrInstr) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInstr)
continue; // skip marker instruction
#endif
insn_t CurrCmd = CurrInstr->GetCmd();
ea_t addr = CurrInstr->GetAddr();
if (CurrCmd.itype == NN_push)
SaveAddr = addr;
else
break;
}
this->LocalVarsAllocInstr = SaveAddr;
this->LocalVarsDeallocInstr = 0;
} // end if (LocalVarsSize > 0) ... else ...
this->CallsAlloca = this->FindAlloca();
#if SMP_COMPUTE_STACK_GRANULARITY
// Now, find the boundaries between local variables.
this->BuildLocalVarTable();
#endif
// Get callee-saved regs info for remediation use.
if (FoundAllocInstr) {
this->MDFindSavedRegs();
}
return;
} // end of SMPFunction::SetStackFrameInfo()
// IDA Pro defines the sizes of regions in the stack frame in a way
// that suits its purposes but not ours. The frsize field of the func_info_t
// structure measures the distance between the stack pointer and the
// frame pointer (ESP and EBP in the x86). This region includes some
// of the callee-saved registers. So, the frregs field only includes
// the callee-saved registers that are above the frame pointer.
// x86 standard prologue on gcc/linux:
// push ebp ; save old frame pointer
// mov ebp,esp ; new frame pointer = current stack pointer
// push esi ; callee save reg
// push edi ; callee save reg
// sub esp,34h ; allocate 52 bytes for local variables
//
// Notice that EBP acquires its final frame pointer value AFTER the
// old EBP has been pushed. This means that, of the three callee saved
// registers, one is above where EBP points and two are below.// IDA Pro is concerned with generating readable addressing expressions
// for items on the stack. None of the callee-saved regs will ever
// be addressed in the function; they will be dormant until they are popped
// off the stack in the function epilogue. In order to create readable
// disassembled code, IDA defines named constant offsets for locals. These
// offsets are negative values (x86 stack grows downward from EBP toward
// ESP). When ESP_relative addressing occurs, IDA converts a statement:
// mov eax,[esp+12]
// into the statement:
// mov eax,[esp+3Ch+var_30]
// Here, 3Ch == 60 decimal is the distance between ESP and EBP, and
// var_30 is defined to have the value -30h == -48 decimal. So, the
// "frame size" in IDA Pro is 60 bytes, and a certain local can be
// addressed in ESP-relative manner as shown, or as [ebp+var_30] for
// EBP-relative addressing. The interactive IDA user can then edit
// the name var_30 to something mnemonic, such as "virus_size", and IDA
// will replace all occurrences with the new name, so that code references
// automatically become [ebp+virus_size]. As the user proceeds
// interactively, he eventually produces very understandable code.
// This all makes sense for producing readable assembly text. However,
// our analyses have a compiler perspective as well as a memory access
// defense perspective. SMP distinguishes between callee saved regs,
// which should not be overwritten in the function body, and local
// variables, which can be written. We view the stack frame in logical
// pieces: here are the saved regs, here are the locals, here is the
// return address, etc. We don't care which direction from EBP the
// callee-saved registers lie; we don't want to lump them in with the
// local variables. We also don't like the fact that IDA Pro will take
// the function prologue code shown above and declare frregs=4 and
// frsize=60, because frsize no longer matches the stack allocation
// statement sub esp,34h == sub esp,52. We prefer frsize=52 and frregs=12.
// So, the task of this function is to fix these stack sizes in our
// private data members for the function, while leaving the IDA database
// alone because IDA needs to maintain its own definitions of these
// variables.
// Fixing means we will update the data members LocalVarsSize and
// CalleeSavedRegsSize.
// NOTE: This function is both machine dependent and platform dependent.
// The prologue and epilogue code generated by gcc-linux is as discussed
// above, while on Visual Studio and other Windows x86 compilers, the
// saving of registers other than EBP happens AFTER local stack allocation.
// A Windows version of the function would expect to see the pushing
// of ESI and EDI AFTER the sub esp,34h statement.
bool SMPFunction::MDFixFrameInfo(void) {
int SavedRegsSize = 0;
int OtherPushesSize = 0; // besides callee-saved regs
int NewLocalsSize = 0;
int OldFrameTotal = this->CalleeSavedRegsSize + this->LocalVarsSize;
bool Changed = false;
bool DebugFlag = (0 == strcmp("__libc_csu_init", this->GetFuncName()));
// Iterate through the first basic block in the function. If we find
// a frame allocating Instr in it, then we have local vars. If not,
// we don't, and LocalVarsSize should have been zero. Count the callee
// register saves leading up to the local allocation. Set data members
// according to what we found if the values of the data members would
// change.
SMPBasicBlock CurrBlock = this->Blocks.front();
for (list<list<SMPInstr>::iterator>::iterator CurrIter = CurrBlock.GetFirstInstr();
CurrIter != CurrBlock.GetLastInstr();
++CurrIter) {
#if SMP_USE_SSA_FNOP_MARKER
if (CurrBlock.GetFirstInstr() == CurrIter)
continue; // skip marker instruction
#endif
list<SMPInstr>::iterator CurrInstr = *CurrIter;
if (CurrInstr->MDIsPushInstr()) {
// We will make the gcc-linux assumption that a PUSH in
// the first basic block, prior to the stack allocating // instruction, is a callee register save. To make this
// more robust, we ensure that the register is from
// the callee saved group of registers, and that it has
// not been defined thus far in the function (else it might
// be a push of an outgoing argument to a call that happens
// in the first block when there are no locals). **!!!!**
if (CurrInstr->MDUsesCalleeSavedReg()
&& !CurrInstr->HasSourceMemoryOperand()) {
SavedRegsSize += 4; // **!!** should check the size
if (DebugFlag) msg("libc_csu_init SavedRegsSize: %d %s\n", SavedRegsSize,
CurrInstr->GetDisasm());
}
else {
// Pushes of outgoing args can be scheduled so that
// they are mixed with the pushes of callee saved regs.
OtherPushesSize += 4;
if (DebugFlag) msg("libc_csu_init OtherPushesSize: %d %s\n", OtherPushesSize,
CurrInstr->GetDisasm());
}
}
else if (CurrInstr->MDIsFrameAllocInstr()) {
if (DebugFlag) msg("libc_csu_init allocinstr: %s\n", CurrInstr->GetDisasm());
SavedRegsSize += OtherPushesSize;
// Get the size being allocated.
set<DefOrUse, LessDefUse>::iterator CurrUse;
for (CurrUse = CurrInstr->GetFirstUse(); CurrUse != CurrInstr->GetLastUse(); ++CurrUse) {
// Find the immediate operand.
if (o_imm == CurrUse->GetOp().type) {
// Get its value into LocalVarsSize.
long AllocValue = (signed long) CurrUse->GetOp().value;
// One compiler might have sub esp,24 and another
// might have add esp,-24. Take the absolute value.
if (0 > AllocValue)
AllocValue = -AllocValue;
if (AllocValue != (long) this->LocalVarsSize) {
Changed = true;
#if SMP_DEBUG_FRAMEFIXUP
if (AllocValue + SavedRegsSize != OldFrameTotal)
msg("Total frame size changed: %s\n", this->FuncName);
#endif
this->LocalVarsSize = (asize_t) AllocValue;
this->CalleeSavedRegsSize = (ushort) SavedRegsSize;
NewLocalsSize = this->LocalVarsSize;
}
else { // Old value was correct; no change.
NewLocalsSize = this->LocalVarsSize;
if (SavedRegsSize != this->CalleeSavedRegsSize) {
this->CalleeSavedRegsSize = (ushort) SavedRegsSize;
Changed = true;
#if SMP_DEBUG_FRAMEFIXUP
msg("Only callee regs size changed: %s\n", this->FuncName);
#endif
}
}
} // end if (o_imm == ...)
} // end for all uses
break; // After frame allocation instr, we are done
} // end if (push) .. elsif frame allocating instr
} // end for all instructions in the first basic block
// If we did not find an allocating instruction, see if it would keep
// the total size the same to set LocalVarsSize to 0 and to set
// CalleeSavedRegsSize to SavedRegsSize. If so, do it. If not, we
// might be better off to leave the numbers alone.
if (!Changed && (NewLocalsSize == 0)) {
if (DebugFlag) msg("libc_csu_init OldFrameTotal: %d \n", OldFrameTotal);
if (OldFrameTotal == SavedRegsSize) {
this->CalleeSavedRegsSize = (ushort) SavedRegsSize;
this->LocalVarsSize = 0;
Changed = true; }
#if SMP_DEBUG_FRAMEFIXUP
else {
msg("Could not update frame sizes: %s\n", this->FuncName);
}
#endif
}
#if SMP_DEBUG_FRAMEFIXUP
if ((0 < OtherPushesSize) && (0 < NewLocalsSize))
msg("Extra pushes found of size %d in %s\n", OtherPushesSize,
this->FuncName);
#endif
return Changed;
} // end of SMPFunction::MDFixFrameInfo()
// Some functions have difficult to find stack allocations. For example, in some
// version of glibc, strpbrk() zeroes out register ECX and then pushes it more than
// 100 times in order to allocate zero-ed out local vars space for a character translation
// table. We will use the stack pointer analysis of IDA to find out if there is a point
// in the first basic block at which the stack pointer reaches the allocation total
// that IDA is expecting for the local vars region.
// If so, we return the address of the instruction at which ESP reaches its value, else
// we return BADADDR.
ea_t SMPFunction::FindAllocPoint(asize_t OriginalLocSize) {
sval_t TargetSize = - ((sval_t) OriginalLocSize); // negate; stack grows down
#if SMP_DEBUG_FRAMEFIXUP
bool DebugFlag = (0 == strcmp("_dl_runtime_resolve", this->GetFuncName()));
if (DebugFlag)
msg("%s OriginalLocSize: %d\n", this->GetFuncName(), OriginalLocSize);
#endif
if (this->AnalyzedSP) {
// Limit our analysis to the first basic block in the function.
list<SMPInstr>::iterator CurrInstr;
for (CurrInstr = this->Instrs.begin(); CurrInstr != this->Instrs.end(); ++CurrInstr) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInstr)
continue; // skip marker instruction
#endif
ea_t addr = CurrInstr->GetAddr();
// get_spd() returns a cumulative delta of ESP
sval_t sp_delta = get_spd(this->GetFuncInfo(), addr);
#if SMP_DEBUG_FRAMEFIXUP
if (DebugFlag)
msg("%s delta: %d at %x\n", this->GetFuncName(), sp_delta, addr);
#endif
if (sp_delta == TargetSize) { // <= instead of == here? **!!**
// Previous instruction hit the frame size.
if (CurrInstr == this->Instrs.begin()) {
return BADADDR; // cannot back up from first instruction
}
else {
ea_t PrevAddr = (--CurrInstr)->GetAddr();
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin()->GetAddr() == PrevAddr)
return BADADDR; // don't return marker instruction
else
return PrevAddr;
#else
return PrevAddr;
#endif
}
}
if (CurrInstr->IsLastInBlock()) {
// It could be that the current instruction will cause the stack pointer
// delta to reach the TargetSize. sp_delta is not updated until after the // current instruction, so we need to look ahead one instruction if the
// current block falls through. On the other hand, if the current block
// ends with a jump or return, we cannot hit TargetSize.
if (CurrInstr->IsBasicBlockTerminator())
return BADADDR;
list<SMPInstr>::iterator NextInstr = CurrInstr;
++NextInstr;
if (NextInstr == this->Instrs.end())
return BADADDR;
sp_delta = get_spd(this->GetFuncInfo(), NextInstr->GetAddr());
if (sp_delta == TargetSize) {
// CurrInstr will cause stack pointer delta to hit TargetSize.
return addr;
}
else {
return BADADDR;
}
} // end if LastInBlock
} // end for all instructions
} // end if (this->AnalyzedSP)
#if SMP_DEBUG_FRAMEFIXUP
else {
msg("AnalyzedSP is false for %s\n", this->GetFuncName());
}
#endif
return BADADDR;
} // end of SMPFunction::FindAllocPoint()
// IDA Pro is sometimes confused by a function that uses the frame pointer
// register for other purposes. For the x86, a function that uses EBP
// as a frame pointer would begin with: push ebp; mov ebp,esp to save
// the old value of EBP and give it a new value as a frame pointer. The
// allocation of local variable space would have to come AFTER the move
// instruction. A function that begins: push ebp; push esi; sub esp,24
// is obviously not using EBP as a frame pointer. IDA is apparently
// confused by the push ebp instruction being the first instruction
// in the function. We will reset UseFP to false in this case.
// The inverse problem happens with a function that begins with instructions
// other than push ebp; mov ebp,esp; ... etc. but eventually has those
// instructions in the first basic block. For example, a C compiler generates
// for the first block of main():
// lea ecx,[esp+arg0]
// and esp, 0xfffffff0
// push dword ptr [ecx-4]
// push ebp
// mov ebp,esp
// push ecx
// sub esp,<framesize>
//
// This function is obviously using EBP as a frame pointer, but IDA Pro marks
// the function as not using a frame pointer. We will reset UseFP to true in
// this case.
// NOTE: This logic should work for both Linux and Windows x86 prologues.
bool SMPFunction::MDFixUseFP(void) {
list<SMPInstr>::iterator CurrInstr = this->Instrs.begin();
ea_t addr = CurrInstr->GetAddr();
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInstr)
++CurrInstr; // skip marker instruction
#endif
if (!(this->UseFP)) {
// See if we can detect the instruction "push ebp" followed by the instruction
// "mov ebp,esp" in the first basic block. The instructions do not have to be
// consecutive. If we find them, we will reset UseFP to true.
bool FirstBlockProcessed = false;
bool EBPSaved = false;
bool ESPintoEBP = false;
do { FirstBlockProcessed = CurrInstr->IsLastInBlock();
if (!EBPSaved) { // still looking for "push ebp"
if (CurrInstr->MDIsPushInstr() && CurrInstr->GetCmd().Operands[0].is_reg(R_bp)) {
EBPSaved = true;
}
}
else if (!ESPintoEBP) { // found "push ebp", looking for "mov ebp,esp"
insn_t CurrCmd = CurrInstr->GetCmd();
if ((CurrCmd.itype == NN_mov)
&& (CurrInstr->GetFirstDef()->GetOp().is_reg(R_bp))
&& (CurrInstr->GetFirstUse()->GetOp().is_reg(R_sp))) {
ESPintoEBP = true;
FirstBlockProcessed = true; // exit loop
}
}
++CurrInstr;
addr = CurrInstr->GetAddr();
// We must get EBP set to its frame pointer value before we reach the
// local frame allocation instruction (i.e. the subtraction of locals space
// from the stack pointer).
FirstBlockProcessed |= (addr >= this->LocalVarsAllocInstr);
} while (!FirstBlockProcessed);
// If we found ESPintoEBP, we also found EBPSaved first, and we need to change
// this->UseFP to true and return true. Otherwise, return false.
this->UseFP = ESPintoEBP;
return ESPintoEBP;
} // end if (!(this->UseFP))
// At this point, this->UseFP must have been true on entry to this method and we will
// check whether it should be reset to false.
while (addr < this->LocalVarsAllocInstr) {
set<DefOrUse, LessDefUse>::iterator CurrDef = CurrInstr->GetFirstDef();
while (CurrDef != CurrInstr->GetLastDef()) {
if (CurrDef->GetOp().is_reg(R_bp))
return false; // EBP got set before locals were allocated
++CurrDef;
}
++CurrInstr;
addr = CurrInstr->GetAddr();
}
// If we found no defs of the frame pointer before the local vars
// allocation, then the frame pointer register is not being used
// as a frame pointer, just as a general callee-saved register.
this->UseFP = false;
msg("MDFixUseFP reset UseFP to false for %s\n", this->GetFuncName());
return true;
} // end of SMPFunction::MDFixUseFP()
// Find the callee-saved reg offsets (negative offset from return address)
// for all registers pushed onto the stack before the stack frame allocation
// instruction.
void SMPFunction::MDFindSavedRegs(void) {
list<SMPInstr>::iterator CurrInst;
int RegIndex;
func_t *CurrFunc = get_func(this->GetStartAddr());
assert(NULL != CurrFunc);
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
if (CurrInst->GetAddr() > this->LocalVarsAllocInstr)
break;
if (!(CurrInst->MDIsPushInstr()))
continue;
sval_t CurrOffset = get_spd(CurrFunc, CurrInst->GetAddr());
if (CurrInst->GetCmd().itype == NN_push) {
op_t PushedReg = CurrInst->GetPushedOpnd();
if (o_reg == PushedReg.type) {
RegIndex = (int) PushedReg.reg;
if (RegIndex > R_di) {
msg("WARNING: Skipping save of register %d\n", RegIndex); continue;
}
if (this->SavedRegLoc.at((size_t) RegIndex) == 0) {
this->SavedRegLoc[(size_t) RegIndex] = CurrOffset - 4;
}
else {
msg("WARNING: Multiple saves of register %d\n", RegIndex);
}
} // end if register push operand
} // end if PUSH instruction
else if (NN_pusha == CurrInst->GetCmd().itype) {
// **!!** Handle pushes of all regs.
this->SavedRegLoc[(size_t) R_ax] = CurrOffset - 4;
this->SavedRegLoc[(size_t) R_cx] = CurrOffset - 8;
this->SavedRegLoc[(size_t) R_dx] = CurrOffset - 12;
this->SavedRegLoc[(size_t) R_bx] = CurrOffset - 16;
this->SavedRegLoc[(size_t) R_sp] = CurrOffset - 20;
this->SavedRegLoc[(size_t) R_bp] = CurrOffset - 24;
this->SavedRegLoc[(size_t) R_si] = CurrOffset - 28;
this->SavedRegLoc[(size_t) R_di] = CurrOffset - 32;
break; // all regs accounted for
}
else if (CurrInst->MDIsEnterInstr()) {
this->SavedRegLoc[(size_t) R_bp] = CurrOffset - 4;
}
} // end for all instructions
return;
} // end of SMPFunction::MDFindSavedRegs()
// Compute the ReturnRegTypes[] as the meet over all register types
// at all return instructions.
void SMPFunction::MDFindReturnTypes(void) {
list<SMPBasicBlock>::iterator CurrBlock;
list<list<SMPInstr>::iterator>::iterator InstIter;
vector<SMPOperandType> RegTypes;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
if (CurrBlock->HasReturn()) {
// Get the types of all registers at the RETURN point.
// Calculate the meet function over them.
InstIter = CurrBlock->GetLastInstr();
--InstIter;
assert(RETURN == (*InstIter)->GetDataFlowType());
set<DefOrUse, LessDefUse>::iterator CurrUse;
for (CurrUse = (*InstIter)->GetFirstUse();
CurrUse != (*InstIter)->GetLastUse();
++CurrUse) {
op_t UseOp = CurrUse->GetOp();
if ((o_reg != UseOp.type) || (R_di < UseOp.reg))
continue;
this->ReturnRegTypes[UseOp.reg]
= SMPTypeMeet(this->ReturnRegTypes.at(UseOp.reg),
CurrUse->GetType());
} // for all USEs in the RETURN instruction
} // end if current block has a RETURN
} // end for all blocks
return;
} // end of SMPFunction::MDFindReturnTypes()
// Determine local variable boundaries in the stack frame.
void SMPFunction::BuildLocalVarTable(void) {
// Currently we just use the info that IDA Pro has inferred from the direct
// addressing of stack locations.
this->SemiNaiveLocalVarID();
return;
} // end of SMPFunction::BuildLocalVarTable()
// Use the local variable offset list from IDA's stack frame structure to compute// the table of local variable boundaries.
void SMPFunction::SemiNaiveLocalVarID(void) {
// NOTE: We use IDA Pro's offsets from this->FuncInfo (e.g. frsize) and NOT
// our own corrected values in our private data members. The offsets we
// read from the stack frame structure returned by get_frame() are consistent
// with other IDA Pro values, not with our corrected values.
bool DebugFlag = false;
#if SMP_DEBUG_STACK_GRANULARITY
DebugFlag |= (0 == strcmp("qSort3", this->GetFuncName()));
#endif
func_t *FuncPtr = get_func(this->FuncInfo.startEA);
if (NULL == FuncPtr) {
msg("ERROR in SMPFunction::SemiNaiveLocalVarID; no func ptr\n");
}
assert(NULL != FuncPtr);
struc_t *StackFrame = get_frame(FuncPtr);
if (NULL == StackFrame) {
msg("WARNING: No stack frame info from get_frame for %s\n", this->GetFuncName());
return;
}
member_t *Member = StackFrame->members;
for (size_t i = 0; i < StackFrame->memqty; ++i, ++Member) {
long offset;
char MemberName[MAXSMPVARSTR] = {'\0'};
if (NULL == Member) {
msg("NULL stack frame member pointer in %s\n", this->GetFuncName());
break;
}
get_member_name(Member->id, MemberName, MAXSMPVARSTR - 1);
if (MemberName == NULL) {
#if SMP_DEBUG_STACK_GRANULARITY
msg("NULL stack frame member in %s\n", this->GetFuncName());
#endif
continue;
}
offset = Member->soff;
if (MemberName[0] == ' ') {
#if SMP_DEBUG_STACK_GRANULARITY
msg("NULL stack frame name at offset %d in %s\n", offset, this->GetFuncName());
#endif
MemberName[1] = '\0';
}
if (DebugFlag) {
msg("%s local var %s at offset %ld\n", this->GetFuncName(), MemberName, offset);
}
if (offset >= (long) this->LocalVarsSize)
break; // Stop after processing locals and outgoing args
#if 0
// We want the offset from the stack pointer after local frame allocation.
// This subtraction would make it relative to the original stack pointer.
offset -= this->FuncInfo.frsize;
#endif
struct LocalVar TempLocal;
TempLocal.offset = offset;
TempLocal.size = (size_t) -1; // compute later
qstrncpy(TempLocal.VarName, MemberName, sizeof(TempLocal.VarName) - 1);
this->LocalVarTable.push_back(TempLocal);
} // end for all stack frame members
if (this->LocalVarTable.empty())
return;
#if SMP_DEBUG_STACK_GRANULARITY
msg("Computing %d local var sizes\n", this->LocalVarTable.size());
#endif
// Now we want to fill in the size field for each local
size_t VarLimit = this->LocalVarTable.size() - 1;
assert(this->LocalVarTable.size() > 0); for (size_t VarIndex = 0; VarIndex < VarLimit; ++VarIndex) {
this->LocalVarTable[VarIndex].size = this->LocalVarTable[VarIndex + 1].offset
- this->LocalVarTable[VarIndex].offset;
}
#if SMP_DEBUG_STACK_GRANULARITY
msg("Computing last local var size for frsize %d\n", this->FuncInfo.frsize);
#endif
// Size of last local is total frsize minus savedregs in frame minus offset of last local
size_t SavedRegsSpace = 0; // portion of frsize that is saved regs, not locals.
if (this->CalleeSavedRegsSize > this->FuncInfo.frregs) {
// IDA Pro counts the save of EBP in frregs, but then EBP gets its new
// value and callee saved regs other than the old EBP push get counted
// in frsize rather than frregs. CalleeSavedRegsSize includes all saved
// regs on the stack, both above and below the current EBP offset.
// NOTE: For windows, this has to be done differently, as callee saved regs
// happen at the bottom of the local frame, not the top.
#if 0
SavedRegsSpace = this->CalleeSavedRegsSize - this->FuncInfo.frregs;
#else
SavedRegsSpace = this->FuncInfo.frsize - this->LocalVarsSize;
#endif
}
this->LocalVarTable.back().size = this->FuncInfo.frsize
- SavedRegsSpace - this->LocalVarTable.back().offset;
this->LocalVarOffsetLimit = this->LocalVarTable.back().offset
+ (adiff_t) this->LocalVarTable.back().size;
// IDA Pro can have difficulty with some irregular functions such as are found
// in the C startup code. The frsize value might be bogus. Just punt on the
// local variable ID if that is the case.
if (this->LocalVarOffsetLimit > (adiff_t) this->FuncInfo.frsize) {
this->LocalVarTable.clear();
msg("WARNING: Bad frsize for %s ; abandoning SemiNaiveLocalVarID.\n", this->FuncName);
return;
}
assert(this->LocalVarOffsetLimit <= (adiff_t) this->FuncInfo.frsize);
// Find out how many of the locals are really outgoing args.
if (this->AnalyzedSP && !this->CallsAlloca && (BADADDR != this->LocalVarsAllocInstr)) {
this->FindOutgoingArgsSize();
}
else {
msg("FindOutgoingArgsSize not called for %s ", this->GetFuncName());
msg("AnalyzedSP: %d CallsAlloca: %d LocalVarsAllocInstr: %x \n",
this->AnalyzedSP, this->CallsAlloca, this->LocalVarsAllocInstr);
}
return;
} // end of SMPFunction::SemiNaiveLocalVarID()
// Determine how many bytes at the bottom of the stack frame (i.e. at bottom of
// this->LocalVarsSize) are used for outgoing args. This is the case when the cdecl
// calling convention is used, e.g. gcc/linux allocates local var space + out args space
// in a single allocation and then writes outarg values directly to ESP+0, ESP+4, etc.
void SMPFunction::FindOutgoingArgsSize(void) {
// Compute the lowest value reached by the stack pointer.
list<SMPInstr>::iterator CurrInst;
this->MinStackDelta = 20000; // Final value should be negative
bool DebugFlag = false;
#if SMP_DEBUG_STACK_GRANULARITY
DebugFlag = (0 == strcmp("error_for_asm", this->GetFuncName()));
#endif
this->OutgoingArgsComputed = true;
if (DebugFlag) {
msg("DEBUG: Entered FindOutgoingArgsSize for %s\n", this->GetFuncName());
#if SMP_IDAPRO52_WORKAROUND
this->OutgoingArgsSize = 16;
return;
#endif }
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInst)
continue; // skip marker instruction
#endif
ea_t addr = CurrInst->GetAddr();
sval_t sp_delta = get_spd(this->GetFuncInfo(), addr);
if (sp_delta < this->MinStackDelta)
this->MinStackDelta = sp_delta;
if (addr == this->LocalVarsAllocInstr) {
// Total stack pointer delta is sp_delta for the next instruction,
// because IDA updates the sp delta AFTER each instruction.
list<SMPInstr>::iterator NextInst = CurrInst;
++NextInst;
sp_delta = get_spd(this->GetFuncInfo(), NextInst->GetAddr());
this->AllocPointDelta = sp_delta;
}
}
#if SMP_DEBUG_STACK_GRANULARITY
msg("AllocPointDelta: %d MinStackDelta: %d\n", this->AllocPointDelta, this->MinStackDelta);
#endif
assert(0 > this->MinStackDelta);
// Allocate a vector of stack frame entries, one for each byte of the stack frame.
// This will be our memory map for analyzing stack usage.
int limit = 0;
#if 1
if (this->LocalVarOffsetLimit > 0)
limit = this->LocalVarOffsetLimit;
#endif
for (int i = this->MinStackDelta; i < limit; ++i) {
struct StackFrameEntry TempEntry;
TempEntry.VarPtr = NULL;
TempEntry.offset = (long) i;
TempEntry.Read = false;
TempEntry.Written = false;
TempEntry.AddressTaken = false;
TempEntry.ESPRelativeAccess = false;
TempEntry.EBPRelativeAccess = false;
this->StackFrameMap.push_back(TempEntry);
}
// Fill in the VarPtr fields for each StackFrameMap entry.
if (0 <= this->AllocPointDelta) {
msg("FATAL ERROR: AllocPointDelta = %d in %s\n", this->AllocPointDelta, this->GetFuncName());
}
assert(0 > this->AllocPointDelta);
for (size_t i = 0; i < this->LocalVarTable.size(); ++i) {
assert(this->LocalVarTable.at(i).offset >= 0);
// Picture that AllocPointDelta is -200, MinStackDelta is -210, and
// the LocalVarTable[i].offset is +8 (i.e. 8 bytes above alloc point).
// Then base = 8 + (-200 - -210) = 8 + 10 = 18, the proper offset into
// the StackFrameMap.
size_t base = (size_t) (this->LocalVarTable.at(i).offset
+ (this->AllocPointDelta - this->MinStackDelta));
size_t limit = base + this->LocalVarTable.at(i).size;
if (limit > this->StackFrameMap.size()) {
msg("ERROR: base = %d limit = %d StackFrameMap size = %d\n", base, limit,
this->StackFrameMap.size());
}
assert(limit <= this->StackFrameMap.size());
for (size_t MapIndex = base; MapIndex < limit; ++MapIndex) {
this->StackFrameMap[MapIndex].VarPtr = &(this->LocalVarTable.at(i));
}
}
// Iterate through all instructions and record stack frame accesses in the StackFrameMap. for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInst)
continue; // skip marker instruction
#endif
sval_t sp_delta = get_spd(this->GetFuncInfo(), CurrInst->GetAddr());
if (0 < sp_delta) {
// Stack underflow; about to assert
msg("Stack underflow at %x %s sp_delta: %d\n", CurrInst->GetAddr(),
CurrInst->GetDisasm(), sp_delta);
}
assert(0 >= sp_delta);
ea_t offset;
size_t DataSize;
bool UsedFramePointer;
if (CurrInst->HasDestMemoryOperand()) {
set<DefOrUse, LessDefUse>::iterator CurrDef;
for (CurrDef = CurrInst->GetFirstDef(); CurrDef != CurrInst->GetLastDef(); ++CurrDef) {
op_t TempOp = CurrDef->GetOp();
if (TempOp.type != o_phrase && TempOp.type != o_displ)
continue;
if (this->MDGetStackOffsetAndSize(TempOp, sp_delta, offset, DataSize, UsedFramePointer)) {
assert(0 <= offset);
if (offset >= this->FuncInfo.frsize)
continue; // limit processing to outgoing args and locals
if ((offset + DataSize) > this->StackFrameMap.size()) {
msg("ERROR: offset = %d DataSize = %d FrameMapSize = %d\n",
offset, DataSize, this->StackFrameMap.size());
}
assert((offset + DataSize) <= this->StackFrameMap.size());
for (int j = 0; j < (int) DataSize; ++j) {
this->StackFrameMap[offset + j].Written = true;
if (!UsedFramePointer)
this->StackFrameMap[offset + j].ESPRelativeAccess = true;
else
this->StackFrameMap[offset + j].EBPRelativeAccess = true;
}
}
} // end for all DEFs
} // end if DestMemoryOperand
if (CurrInst->HasSourceMemoryOperand()) {
set<DefOrUse, LessDefUse>::iterator CurrUse;
for (CurrUse = CurrInst->GetFirstUse(); CurrUse != CurrInst->GetLastUse(); ++CurrUse) {
op_t TempOp = CurrUse->GetOp();
if (TempOp.type != o_phrase && TempOp.type != o_displ)
continue;
if (this->MDGetStackOffsetAndSize(TempOp, sp_delta, offset, DataSize, UsedFramePointer)) {
assert(0 <= offset);
if (offset >= this->FuncInfo.frsize)
continue; // limit processing to outgoing args and locals
if ((offset + DataSize) > this->StackFrameMap.size()) {
msg("ERROR: offset = %d DataSize = %d FrameMapSize = %d\n",
offset, DataSize, this->StackFrameMap.size());
}
assert((offset + DataSize) <= this->StackFrameMap.size());
for (int j = 0; j < (int) DataSize; ++j) {
this->StackFrameMap[offset + j].Read = true;
if (!UsedFramePointer)
this->StackFrameMap[offset + j].ESPRelativeAccess = true;
else
this->StackFrameMap[offset + j].EBPRelativeAccess = true;
}
}
} // end for all USEs
} // end if SourceMemoryOperand
// NOTE: Detect taking the address of stack locations. **!!**
} // end for all instructions
// If function is a leaf function, set OutgoingArgsSize to zero and return.
if (this->IsLeaf()) {
this->OutgoingArgsSize = 0;
return;
}
// For non-leaf functions, set the OutgoingArgsSize to the write-only, ESP-relative
// region of the bottom of the StackFrameMap.
for (size_t MapIndex = 0; MapIndex < this->StackFrameMap.size(); ++MapIndex) {
// Some of the bottom of the stack frame might be below the local frame allocation.
// These are pushes that happened after allocation, etc. We skip over these
// locations and define the outgoing args region to start strictly at the bottom
// of the local frame allocation.
struct StackFrameEntry TempEntry = this->StackFrameMap.at(MapIndex);
if (DebugFlag) {
msg("StackFrameMap entry %d: offset: %ld Read: %d Written: %d ESP: %d EBP: %d\n",
MapIndex, TempEntry.offset, TempEntry.Read, TempEntry.Written,
TempEntry.ESPRelativeAccess, TempEntry.EBPRelativeAccess);
}
if (TempEntry.offset < this->AllocPointDelta)
continue;
if (TempEntry.Read || TempEntry.EBPRelativeAccess || !TempEntry.Written
|| !TempEntry.ESPRelativeAccess)
break;
this->OutgoingArgsSize++;
}
// Sometimes we encounter unused stack space above the outgoing args. Lump this space
// in with the outgoing args. We detect this by noting when the outgoing args space
// has only partially used the space assigned to a local var.
if ((0 < this->OutgoingArgsSize) && (this->OutgoingArgsSize < this->FuncInfo.frsize)) {
long MapIndex = (this->AllocPointDelta - this->MinStackDelta);
assert(0 <= MapIndex);
MapIndex += (((long) this->OutgoingArgsSize) - 1);
struct StackFrameEntry TempEntry = this->StackFrameMap.at((size_t) MapIndex);
if (NULL == TempEntry.VarPtr) { // Gap in stack frame; IDA 6.0
msg("Gap in stack frame: %s\n", this->FuncName);
}
else if (this->OutgoingArgsSize < (TempEntry.VarPtr->offset + TempEntry.VarPtr->size)) {
#if SMP_DEBUG_FRAMEFIXUP
msg("OutGoingArgsSize = %d", this->OutgoingArgsSize);
#endif
this->OutgoingArgsSize = TempEntry.VarPtr->offset + TempEntry.VarPtr->size;
#if SMP_DEBUG_FRAMEFIXUP
msg(" adjusted to %d\n", this->OutgoingArgsSize);
#endif
}
}
return;
} // end of SMPFunction::FindOutgoingArgsSize()
// If TempOp reads or writes to a stack location, return the offset (relative to the initial
// stack pointer value) and the size in bytes of the data access.
// NOTE: TempOp must be of type o_displ or o_phrase, as no other operand type could be a
// stack memory access.
// sp_delta is the stack pointer delta of the current instruction, relative to the initial
// stack pointer value for the function.
// Return true if a stack memory access was found in TempOp, false otherwise.
bool SMPFunction::MDGetStackOffsetAndSize(op_t TempOp, sval_t sp_delta, ea_t &offset, size_t &DataSize, bool &FP) {
int BaseReg;
int IndexReg;
ushort ScaleFactor;
assert((o_displ == TempOp.type) || (o_phrase == TempOp.type));
MDExtractAddressFields(TempOp, BaseReg, IndexReg, ScaleFactor, offset);
if (TempOp.type == o_phrase) {
assert(offset == 0); // implicit zero, as in [esp] ==> [esp+0]
}
if ((BaseReg == R_sp) || (IndexReg == R_sp)) {
// ESP-relative constant offset offset += sp_delta; // base offsets from entry ESP value
offset -= this->MinStackDelta; // convert to StackFrameMap index
// Get size of data written
DataSize = GetOpDataSize(TempOp);
FP = false;
return true;
}
else if (this->UseFP && ((BaseReg == R_bp) || (IndexReg == R_bp))) {
offset -= this->FuncInfo.frregs; // base offsets from entry ESP value
offset -= this->MinStackDelta; // convert to StackFrameMap index
DataSize = GetOpDataSize(TempOp);
FP = true;
return true;
}
else {
return false;
}
} // end of SMPFunction::MDGetStackOffsetAndSize()
// Is DestOp within the outgoing args area? Assume it must be an ESP-relative
// DEF operand in order to be a write to the outgoing args area.
bool SMPFunction::WritesToOutgoingArgs(op_t DestOp) {
bool OutArgWrite = false;
int BaseReg, IndexReg;
ushort ScaleFactor;
ea_t offset;
if (this->IsLeaf())
return false;
MDExtractAddressFields(DestOp, BaseReg, IndexReg, ScaleFactor, offset);
if ((BaseReg != R_sp) && (IndexReg != R_sp))
return false;
if (((BaseReg == R_sp) && (IndexReg != R_none))
|| ((IndexReg == R_sp) && (BaseReg != R_none))
|| (0 < ScaleFactor)) {
msg("WARNING: WritesToOutgoingArgs called with indexed write.");
PrintOperand(DestOp);
return false;
}
if (!this->OutgoingArgsComputed) {
OutArgWrite = true; // be conservative
}
else {
OutArgWrite = (offset < this->OutgoingArgsSize);
}
return OutArgWrite;
} // end of SMPFunction::WritesToOutgoingArgs()
// Is DestOp a direct memory access above the local vars frame?
bool SMPFunction::WritesAboveLocalFrame(op_t DestOp) {
bool InArgWrite = false;
int BaseReg, IndexReg;
ushort ScaleFactor;
ea_t offset;
long SignedOffset;
MDExtractAddressFields(DestOp, BaseReg, IndexReg, ScaleFactor, offset);
SignedOffset = (long) offset;
bool ESPrelative = (BaseReg == R_sp) || (IndexReg == R_sp);
bool EBPrelative = this->UseFP && ((BaseReg == R_bp) || (IndexReg == R_bp));
if (!(ESPrelative || EBPrelative))
return false;
if (((IndexReg != R_none) && (BaseReg != R_none))
|| (0 < ScaleFactor)) {
msg("WARNING: WritesAboveLocalFrame called with indexed write.");
PrintOperand(DestOp); return false;
}
InArgWrite = (ESPrelative && (SignedOffset > ((long) this->LocalVarsSize)))
|| (EBPrelative && (SignedOffset > 0));
return InArgWrite;
}// end of SMPFunction::WritesAboveLocalFrame()
// Is DestOp an indexed write above the local vars frame?
bool SMPFunction::IndexedWritesAboveLocalFrame(op_t DestOp)
{
bool InArgWrite = false;
int BaseReg, IndexReg;
ushort ScaleFactor;
ea_t offset;
MDExtractAddressFields(DestOp, BaseReg, IndexReg, ScaleFactor, offset);
bool ESPrelative = (BaseReg == R_sp) || (IndexReg == R_sp);
bool EBPrelative = this->UseFP && ((BaseReg == R_bp) || (IndexReg == R_bp));
if (!(ESPrelative || EBPrelative))
return false;
InArgWrite = (ESPrelative && (offset > this->LocalVarsSize))
|| (EBPrelative && (offset > 0));
return InArgWrite;
} // end of SMPFunction::IndexedWritesAboveLocalFrame
// Find evidence of calls to alloca(), which appear as stack space allocations (i.e.
// subtractions from the stack pointer) AFTER the local frame allocation instruction
// for this function.
// Return true if such an allocation is found and false otherwise.
bool SMPFunction::FindAlloca(void) {
list<SMPInstr>::iterator CurrInst;
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInst)
continue; // skip marker instruction
#endif
if ((CurrInst->GetAddr() > this->LocalVarsAllocInstr) && CurrInst->MDIsFrameAllocInstr()) {
return true;
}
}
return false;
} // end of SMPFunction::FindAlloca()
// Emit the annotations describing the regions of the stack frame.
void SMPFunction::EmitStackFrameAnnotations(FILE *AnnotFile, list<SMPInstr>::iterator Instr) {
ea_t addr = Instr->GetAddr();
#if 0
if (0 < IncomingArgsSize) {
qfprintf(AnnotFile, "%10x %6d INARGS STACK esp + %d %s \n",
addr, IncomingArgsSize,
(LocalVarsSize + CalleeSavedRegsSize + RetAddrSize),
Instr->GetDisasm());
}
#endif
if (0 < RetAddrSize) {
qfprintf(AnnotFile, "%10x %6d MEMORYHOLE STACK esp + %d ReturnAddress \n",
addr, RetAddrSize, (LocalVarsSize + CalleeSavedRegsSize));
}
if (0 < CalleeSavedRegsSize) {
qfprintf(AnnotFile, "%10x %6d MEMORYHOLE STACK esp + %d CalleeSavedRegs \n",
addr, CalleeSavedRegsSize, LocalVarsSize);
}
if (0 < LocalVarsSize) {
unsigned long ParentReferentID = DataReferentID++; qfprintf(AnnotFile, "%10x %6d DATAREF STACK %ld esp + %d PARENT LocalFrame LOCALFRAME\n",
addr, LocalVarsSize, ParentReferentID, 0);
#if SMP_COMPUTE_STACK_GRANULARITY
if (this->AnalyzedSP && !this->CallsAlloca && (BADADDR != this->LocalVarsAllocInstr)) {
// We can only fine-grain the stack frame if we were able to analyze the stack
if (this->OutgoingArgsSize > 0) {
qfprintf(AnnotFile, "%10x %6d DATAREF STACK %ld esp + %d CHILDOF %ld OFFSET %d OutArgsRegion OUTARGS\n",
addr, this->OutgoingArgsSize, DataReferentID, 0, ParentReferentID, 0);
++DataReferentID;
}
#if SMP_DEBUG_STACK_GRANULARITY
msg("LocalVarTable of size %d for function %s\n", this->LocalVarTable.size(),
this->GetFuncName());
#endif
for (size_t i = 0; i < this->LocalVarTable.size(); ++i) {
#if SMP_DEBUG_STACK_GRANULARITY
msg("Entry %d offset %d size %d name %s\n", i, this->LocalVarTable[i].offset,
this->LocalVarTable[i].size, this->LocalVarTable[i].VarName);
#endif
// Don't emit annotations for incoming or outgoing args or anything else
// above or below the current local frame.
if ((this->LocalVarTable[i].offset >= (long) this->FuncInfo.frsize)
|| (this->LocalVarTable[i].offset < (long) this->OutgoingArgsSize))
continue;
qfprintf(AnnotFile, "%10x %6d DATAREF STACK %ld esp + %ld CHILDOF %ld OFFSET %ld LOCALVAR %s \n",
addr, this->LocalVarTable[i].size, DataReferentID,
this->LocalVarTable[i].offset, ParentReferentID,
this->LocalVarTable[i].offset, this->LocalVarTable[i].VarName);
++DataReferentID;
}
} // end if (this->AnalyzedSP and not Alloca .... )
#endif
} // end if (0 < LocalVarsSize)
return;
} // end of SMPFunction::EmitStackFrameAnnotations()
// Main data flow analysis driver. Goes through the function and
// fills all objects for instructions, basic blocks, and the function
// itself.
void SMPFunction::Analyze(void) {
bool FoundAllCallers = false;
list<SMPInstr>::iterator FirstInBlock = this->Instrs.end();
// For starting a basic block
list<SMPInstr>::iterator LastInBlock = this->Instrs.end();
// Terminating a basic block
#if SMP_DEBUG_CONTROLFLOW
msg("Entering SMPFunction::Analyze.\n");
#endif
// Get some basic info from the FuncInfo structure.
this->Size = this->FuncInfo.endEA - this->FuncInfo.startEA;
this->UseFP = (0 != (this->FuncInfo.flags & (FUNC_FRAME | FUNC_BOTTOMBP)));
this->StaticFunc = (0 != (this->FuncInfo.flags & FUNC_STATIC));
this->LibFunc = (0 != (this->FuncInfo.flags & FUNC_LIB));
get_func_name(this->FuncInfo.startEA, this->FuncName,
sizeof(this->FuncName) - 1);
this->BlockCount = 0;
this->AnalyzedSP = this->FuncInfo.analyzed_sp();
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: got basic info.\n");
#endif
// Cycle through all chunks that belong to the function.
func_tail_iterator_t FuncTail(this->GetFuncInfo());
size_t ChunkCounter = 0;
for (bool ChunkOK = FuncTail.main(); ChunkOK; ChunkOK = FuncTail.next()) {
const area_t &CurrChunk = FuncTail.chunk();
++ChunkCounter; if (1 < ChunkCounter) {
this->SharedChunks = true;
#if SMP_DEBUG_CHUNKS
msg("Found tail chunk for %s at %x\n", this->FuncName, CurrChunk.startEA);
#endif
}
// Build the instruction and block lists for the function.
for (ea_t addr = CurrChunk.startEA; addr < CurrChunk.endEA;
addr = get_item_end(addr)) {
flags_t InstrFlags = getFlags(addr);
if (isHead(InstrFlags) && isCode(InstrFlags)) {
SMPInstr CurrInst = SMPInstr(addr);
// Fill in the instruction data members.
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: calling CurrInst::Analyze.\n");
#endif
CurrInst.Analyze();
if (SMPBinaryDebug) {
msg("Disasm: %s \n", CurrInst.GetDisasm());
}
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.empty()) {
// First instruction in function. We want to create a pseudo-instruction
// at the top of the function that can hold SSA DEFs for LiveIn names
// to the function. We use a floating point no-op as the pseudo-inst.
// The code address is one less than the start address of the function.
SMPInstr MarkerInst = SMPInstr(addr - 1);
MarkerInst.AnalyzeMarker();
assert(FirstInBlock == this->Instrs.end());
this->Instrs.push_back(MarkerInst);
}
#endif
if (this->AnalyzedSP) {
// Audit the IDA SP analysis.
sval_t sp_delta = get_spd(this->GetFuncInfo(), addr);
// sp_delta is difference between current value of stack pointer
// and value of the stack pointer coming into the function. It
// is updated AFTER each instruction. Thus, it should not get back
// above zero (e.g. to +4) until after a return instruction.
if (sp_delta > 0) {
// Stack pointer has underflowed, according to IDA's analysis,
// which is probably incorrect.
this->AnalyzedSP = false;
msg("Resetting AnalyzedSP to false for %s\n", this->GetFuncName());
msg("Underflowing instruction: %s sp_delta: %d\n", CurrInst.GetDisasm(),
sp_delta);
}
else if (sp_delta == 0) {
// Search for tail calls.
if (CurrInst.IsBranchToFarChunk()) {
// After the stack has been restored to the point at which
// we are ready to return, we instead find a jump to a
// far chunk. This is the classic tail call optimization:
// the return statement has been replaced with a jump to
// another function, which will return not to this function,
// but to the caller of this function.
CurrInst.SetTailCall();
msg("Found tail call at %x from %s: %s\n", addr, this->GetFuncName(),
CurrInst.GetDisasm());
// Just like a return instruction, we must make
// DEF-USE chains reach the tail call.
CurrInst.MDAddRegUse(R_ax, false);
CurrInst.MDAddRegUse(R_bx, false);
CurrInst.MDAddRegUse(R_cx, false);
CurrInst.MDAddRegUse(R_dx, false);
CurrInst.MDAddRegUse(R_bp, false);
CurrInst.MDAddRegUse(R_si, false);
CurrInst.MDAddRegUse(R_di, false);
}
} }
// Find all functions that call the current function.
xrefblk_t CurrXrefs;
if (!FoundAllCallers) {
for (bool ok = CurrXrefs.first_to(CurrInst.GetAddr(), XREF_ALL);
ok;
ok = CurrXrefs.next_to()) {
if ((CurrXrefs.from != 0) && (CurrXrefs.iscode)) {
// Make sure it is not a fall-through. Must be a
// control-flow instruction of some sort, including
// direct or indirect calls or tail calls.
SMPInstr CallInst(CurrXrefs.from);
CallInst.Analyze();
SMPitype CallType = CallInst.GetDataFlowType();
if ((COND_BRANCH <= CallType) && (RETURN >= CallType)) {
// Found a caller, with its call address in CurrXrefs.from
this->AddCallSource(CurrXrefs.from);
}
}
}
FoundAllCallers = true; // only do this for first inst
}
SMPitype DataFlowType = CurrInst.GetDataFlowType();
if ((DataFlowType == INDIR_CALL)|| (DataFlowType == CALL)) {
// See if IDA has determined the target of the call.
ea_t TargetAddr = CurrInst.GetCallTarget();
bool LinkedToTarget = (BADADDR != TargetAddr);
if (LinkedToTarget) {
if (0 == TargetAddr) {
msg("WARNING: Ignoring NULL call target (unreachable) at %x\n", CurrInst.GetAddr());
}
else {
this->AllCallTargets.push_back(TargetAddr);
if (INDIR_CALL == DataFlowType) {
this->IndirectCallTargets.push_back(TargetAddr);
}
else {
this->DirectCallTargets.push_back(TargetAddr);
}
}
}
if (DataFlowType == INDIR_CALL) {
this->IndirectCalls = true;
this->UnresolvedIndirectCalls = (!LinkedToTarget);
}
} // end if INDIR_CALL or CALL
else if (DataFlowType == INDIR_JUMP)
this->IndirectJumps = true;
// Before we insert the instruction into the instruction
// list, determine if it is a jump target that does not
// follow a basic block terminator. This is the special case
// of a CASE in a SWITCH that falls through into another
// CASE, for example. The first sequence of statements
// was not terminated by a C "break;" statement, so it
// looks like straight line code, but there is an entry
// point at the beginning of the second CASE sequence and
// we have to split basic blocks at the entry point.
if ((FirstInBlock != this->Instrs.end())
&& CurrInst.IsJumpTarget()) {
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: hit special jump target case.\n");
#endif
LastInBlock = --(this->Instrs.end());
SMPBasicBlock CurrBlock = SMPBasicBlock(this, FirstInBlock,
LastInBlock);
CurrBlock.Analyze();
// If not the first chunk in the function, it is a shared // tail chunk.
if (ChunkCounter > 1) {
CurrBlock.SetShared();
}
FirstInBlock = this->Instrs.end();
LastInBlock = this->Instrs.end();
this->Blocks.push_back(CurrBlock);
this->BlockCount += 1;
}
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: putting CurrInst on list.\n");
#endif
// Insert instruction at end of list.
this->Instrs.push_back(CurrInst);
// Find basic block leaders and terminators.
if (FirstInBlock == this->Instrs.end()) {
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: setting FirstInBlock.\n");
#endif
#if SMP_USE_SSA_FNOP_MARKER
if (2 == this->Instrs.size()) {
// Just pushed first real instruction, after the fnop marker.
FirstInBlock = this->Instrs.begin();
}
else {
FirstInBlock = --(this->Instrs.end());
}
#else
FirstInBlock = --(this->Instrs.end());
#endif
}
if (CurrInst.IsBasicBlockTerminator()) {
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: found block terminator.\n");
#endif
LastInBlock = --(this->Instrs.end());
SMPBasicBlock CurrBlock = SMPBasicBlock(this, FirstInBlock, LastInBlock);
CurrBlock.Analyze();
// If not the first chunk in the function, it is a shared
// tail chunk.
if (ChunkCounter > 1) {
CurrBlock.SetShared();
}
FirstInBlock = this->Instrs.end();
LastInBlock = this->Instrs.end();
this->Blocks.push_back(CurrBlock);
this->BlockCount += 1;
// Is the instruction a branch to a target outside the function? If
// so, this function has shared tail chunks.
if (CurrInst.IsBranchToFarChunk() && (!CurrInst.IsTailCall())) {
this->SharedChunks = true;
}
}
} // end if (isHead(InstrFlags) && isCode(InstrFlags)
} // end for (ea_t addr = CurrChunk.startEA; ... )
// Handle the special case in which a function does not terminate
// with a return instruction or any other basic block terminator.
// Sometimes IDA Pro sees a call to a NORET function and decides
// to not include the dead code after it in the function. That
// dead code includes the return instruction, so the function no
// longer includes a return instruction and terminates with a CALL.
if (FirstInBlock != this->Instrs.end()) {
LastInBlock = --(this->Instrs.end());
SMPBasicBlock CurrBlock = SMPBasicBlock(this, FirstInBlock, LastInBlock);
CurrBlock.Analyze();
// If not the first chunk in the function, it is a shared // tail chunk.
if (ChunkCounter > 1) {
CurrBlock.SetShared();
}
FirstInBlock = this->Instrs.end();
LastInBlock = this->Instrs.end();
this->Blocks.push_back(CurrBlock);
this->BlockCount += 1;
}
} // end for (bool ChunkOK = ...)
// Now that we have all instructions and basic blocks, link each instruction
// to its basic block. Note that the instruction has to be linked to the copy
// of the basic block in this->Blocks(), not to the original SMPBasicBlock
// object that was constructed and destructed on the stack above. (Ouch!
// Very painful memory corruption debugging lesson.)
list<SMPBasicBlock>::iterator CurrBlock;
list<list<SMPInstr>::iterator>::iterator InstIter;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
(*InstIter)->SetBlock(CurrBlock->GetThisBlock());
}
}
#if KLUDGE_VFPRINTF_FAMILY
if (0 != strstr(this->GetFuncName(), "printf")) {
this->SharedChunks = true;
msg("Kludging function %s\n", this->GetFuncName());
}
#endif
#if SMP_IDAPRO52_WORKAROUND
if (0 == strcmp(this->GetFuncName(), "error_for_asm")) {
this->SharedChunks = true;
msg("Kludging function %s\n", this->GetFuncName());
}
#endif
// Set up basic block links and map of instructions to blocks.
if (!(this->HasSharedChunks())) {
this->SetLinks();
this->RPONumberBlocks();
// Figure out the stack frame and related info.
this->SetStackFrameInfo();
list<SMPInstr>::iterator CurrInst;
bool GoodRTL;
this->BuiltRTLs = true;
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
// Build tree RTLs for the instruction.
GoodRTL = CurrInst->BuildRTL();
this->BuiltRTLs = (this->BuiltRTLs && GoodRTL);
#if SMP_DEBUG_BUILD_RTL
if (!GoodRTL) {
msg("ERROR: Cannot build RTL at %x for %s\n", CurrInst->GetAddr(),
CurrInst->GetDisasm());
}
#endif
if (GoodRTL)
CurrInst->SyncAllRTs();
// Detect indirect memory references.
CurrInst->AnalyzeIndirectRefs(this->UseFP);
} // end for all instructions
} // end if not shared chunks
else { // has shared chunks; still want to compute stack frame info
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: set stack frame info.\n");
#endif
#ifdef SMP_DEBUG_FUNC msg(" %s has shared chunks \n", this->GetFuncName());
#endif
// Figure out the stack frame and related info.
this->SetStackFrameInfo();
}
// Audit the call instructions and call targets.
if ((!this->AllCallTargets.empty()) || this->UnresolvedIndirectCalls) {
bool FoundBadCallTarget = false;
vector<ea_t>::iterator CurrTarget = this->AllCallTargets.begin();
while (CurrTarget != this->AllCallTargets.end()) {
if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
// Found a call target that is within the function.
FoundBadCallTarget = true;
if (this->FirstEA == *CurrTarget) { // Direct recursion, not a pseudo-jump
this->DirectlyRecursive = true;
}
CurrTarget = this->AllCallTargets.erase(CurrTarget);
}
else {
++CurrTarget;
}
}
if (FoundBadCallTarget) {
// We have to mark the pseudo-call instructions and audit the direct and
// indirect call target vectors.
// Audit direct call targets.
CurrTarget = this->DirectCallTargets.begin();
while (CurrTarget != this->DirectCallTargets.end()) {
if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
// Found a call target that is within the function.
CurrTarget = this->DirectCallTargets.erase(CurrTarget);
}
else {
++CurrTarget;
}
}
// Audit indirect call targets.
CurrTarget = this->IndirectCallTargets.begin();
while (CurrTarget != this->IndirectCallTargets.end()) {
if ((this->FirstEA <= *CurrTarget) && (this->FuncInfo.endEA >= *CurrTarget)) {
// Found a call target that is within the function.
CurrTarget = this->IndirectCallTargets.erase(CurrTarget);
}
else {
++CurrTarget;
}
}
// Find calls used as jumps.
list<SMPInstr>::iterator InstIter = this->Instrs.begin();
while (InstIter != this->Instrs.end()) {
SMPitype InstFlow = InstIter->GetDataFlowType();
if ((CALL == InstFlow) || (INDIR_CALL == InstFlow)) {
InstIter->AnalyzeCallInst(this->FirstEA, this->FuncInfo.endEA);
}
++InstIter;
}
} // end if (FoundBadCallTarget)
}
this->MarkFunctionSafe();
} // end of SMPFunction::Analyze()
// For each instruction, mark the non-flags-reg DEFs as having live
// metadata (mmStrata needs to fetch and track this metadata for this
// instruction) or dead metadata (won't be used as addressing reg, won't
// be stored to memory, won't be returned to caller).
void SMPFunction::AnalyzeMetadataLiveness(void) {
bool changed; int BaseReg;
int IndexReg;
ushort ScaleFactor;
ea_t offset;
op_t BaseOp, IndexOp, ReturnOp, DefOp, UseOp;
BaseOp.type = o_reg;
IndexOp.type = o_reg;
ReturnOp.type = o_reg;
list<SMPInstr>::iterator CurrInst;
set<DefOrUse, LessDefUse>::iterator CurrDef;
set<DefOrUse, LessDefUse>::iterator CurrUse;
set<DefOrUse, LessDefUse>::iterator NextUse;
bool DebugFlag = false;
int IterationCount = 0;
#if SMP_DEBUG_DATAFLOW
if (0 == strcmp("uw_frame_state_for", this->GetFuncName())) {
DebugFlag = true;
}
#endif
do {
changed = false;
++IterationCount;
bool SafeMemDest;
if (DebugFlag) {
msg("AnalyzeMetadataLiveness iteration count: %d \n", IterationCount);
}
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
SafeMemDest = false; // true for some SafeFunc instructions
// Skip the SSA marker instruction.
if (NN_fnop == CurrInst->GetCmd().itype)
continue;
if (DebugFlag) {
msg("Inst addr: %x \n", CurrInst->GetAddr());
}
CurrDef = CurrInst->GetFirstDef();
while (CurrDef != CurrInst->GetLastDef()) {
if (DEF_METADATA_UNANALYZED == CurrDef->GetMetadataStatus()) {
DefOp = CurrDef->GetOp();
// Handle special registers never used as address regs.
if (DefOp.is_reg(X86_FLAGS_REG)
|| ((o_trreg <= DefOp.type) && (o_xmmreg >= DefOp.type))) {
CurrDef = CurrInst->SetDefMetadata(DefOp,
DEF_METADATA_UNUSED);
changed = true;
}
else if (DefOp.is_reg(R_sp)
|| (this->UseFP && DefOp.is_reg(R_bp))) {
// Stack pointer register DEFs always have live
// metadata, but we don't need to propagate back
// through particular DEF-USE chains.
CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_USED);
changed = true;
}
else if ((o_mem <= DefOp.type) && (o_displ >= DefOp.type)) {
// DEF is a memory operand. The addressing registers
// therefore have live metadata, and the memory metadata is live.
// EXCEPTION: If the function is Safe, then direct stack writes
// to local variables (above the outgoing args area of the frame)
// are not live metadata, and there will be no indirect local frame
// writes, by definition of "safe." So, for safe funcs, only
// the o_mem (globals) and indirect writes are live metadata.
if (this->SafeFunc && MDIsStackAccessOpnd(DefOp, this->UseFP)
&& (!this->WritesAboveLocalFrame(DefOp))
&& (!this->WritesToOutgoingArgs(DefOp))) {
++CurrDef;
SafeMemDest = true;
continue;
} CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_USED);
changed = true;
MDExtractAddressFields(DefOp, BaseReg, IndexReg,
ScaleFactor, offset);
if (R_none != BaseReg) {
BaseOp.reg = MDCanonicalizeSubReg((ushort) BaseReg);
if (BaseOp.is_reg(R_sp)
|| (this->UseFP && BaseOp.is_reg(R_bp))) {
; // do nothing; DEF handled by case above
}
else {
CurrUse = CurrInst->FindUse(BaseOp);
if (CurrUse == CurrInst->GetLastUse()) {
msg("ERROR: BaseReg %d not in USE list at %x for %s\n",
BaseOp.reg, CurrInst->GetAddr(),
CurrInst->GetDisasm());
}
assert(CurrUse != CurrInst->GetLastUse());
if (this->IsGlobalName(BaseOp)) {
changed |= this->PropagateGlobalMetadata(BaseOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
else {
changed |= CurrInst->GetBlock()->PropagateLocalMetadata(BaseOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
}
} // end if R_none != BaseReg
if (R_none != IndexReg) {
IndexOp.reg = MDCanonicalizeSubReg((ushort) IndexReg);
if (IndexOp.is_reg(R_sp)
|| (this->UseFP && IndexOp.is_reg(R_bp))) {
; // do nothing; DEF handled by case above
}
else {
CurrUse = CurrInst->FindUse(IndexOp);
if (CurrUse == CurrInst->GetLastUse()) {
msg("ERROR: IndexReg %d not in USE list at %x for %s\n",
IndexOp.reg, CurrInst->GetAddr(),
CurrInst->GetDisasm());
}
assert(CurrUse != CurrInst->GetLastUse());
if (0 != ScaleFactor) {
; // mmStrata knows scaled reg is NUMERIC
// ... its metadata is not fetched
}
else if (this->IsGlobalName(IndexOp)) {
changed |= this->PropagateGlobalMetadata(IndexOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
else {
changed |= CurrInst->GetBlock()->PropagateLocalMetadata(IndexOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
}
} // end if R_none != IndexReg
} // end if X86_FLAGS_REG .. else if stack ptr ...
} // end if unanalyzed metadata usage
++CurrDef;
} // end while processing DEFs
if ((RETURN == CurrInst->GetDataFlowType())
|| (CurrInst->IsTailCall()) // quasi-return
|| (CALL == CurrInst->GetDataFlowType())
|| (INDIR_CALL == CurrInst->GetDataFlowType())) {
// The EAX and EDX registers can be returned to the caller,
// which might use their metadata. They show up as USEs
// of the return instruction. Some library functions
// pass return values in non-standard ways. e.g. through
// EBX or EDI, so we treat all return regs the same.
// For CALL instructions, values can be passed in caller-saved // registers, unfortunately, so the metadata is live-in.
CurrUse = CurrInst->GetFirstUse();
while (CurrUse != CurrInst->GetLastUse()) {
NextUse = CurrUse;
++NextUse;
ReturnOp = CurrUse->GetOp();
if (DebugFlag) {
msg("ReturnOp: ");
PrintOperand(ReturnOp);
msg("\n");
}
if ((o_reg == ReturnOp.type) &&
(!ReturnOp.is_reg(X86_FLAGS_REG))) {
if (this->IsGlobalName(ReturnOp)) {
changed |= this->PropagateGlobalMetadata(ReturnOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
else {
changed |= CurrInst->GetBlock()->PropagateLocalMetadata(ReturnOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
}
CurrUse = NextUse;
} // end while all USEs
} // end if return or call
else if (CurrInst->HasDestMemoryOperand()
|| CurrInst->MDIsPushInstr()) {
// Memory writes cause a lot of metadata usage.
// Addressing registers in the memory destination
// have live metadata used in bounds checking. The
// register being stored to memory could end up being
// used in some other bounds checking, unless we
// have precise memory tracking and know that it
// won't.
// We handled the addressing registers above, so we
// handle the register written to memory here.
// The same exception applies as above: If the destination
// memory operand is not a stack write, then safe functions
// do not need to track the metadata.
if (SafeMemDest) {
continue; // go to next instruction
}
CurrUse = CurrInst->GetFirstUse();
while (CurrUse != CurrInst->GetLastUse()) {
NextUse = CurrUse;
++NextUse;
UseOp = CurrUse->GetOp();
// NOTE: **!!** To be less conservative, we
// should propagate less for exchange category
// instructions.
if ((UseOp.type == o_reg) && (!UseOp.is_reg(R_sp))
&& (!(this->UseFP && UseOp.is_reg(R_bp)))
&& (!UseOp.is_reg(X86_FLAGS_REG))) {
if (this->IsGlobalName(UseOp)) {
changed |= this->PropagateGlobalMetadata(UseOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
else {
changed |= CurrInst->GetBlock()->PropagateLocalMetadata(UseOp,
DEF_METADATA_USED, CurrUse->GetSSANum());
}
} // end if register
CurrUse = NextUse;
} // end while all USEs
} // end if call or return else if memdest ...
} // end for all instructions
} while (changed);
// All DEFs that still have status DEF_METADATA_UNANALYZED can now // be marked as DEF_METADATA_UNUSED.
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
if (NN_fnop == CurrInst->GetCmd().itype)
continue;
CurrDef = CurrInst->GetFirstDef();
while (CurrDef != CurrInst->GetLastDef()) {
if (DEF_METADATA_UNANALYZED == CurrDef->GetMetadataStatus()) {
CurrDef = CurrInst->SetDefMetadata(CurrDef->GetOp(),
DEF_METADATA_UNUSED);
assert(CurrDef != CurrInst->GetLastDef());
}
++CurrDef;
}
}
return;
} // end of SMPFunction::AnalyzeMetadataLiveness()
// Propagate the metadata Status for UseOp/SSANum to its global DEF.
// Return true if successful.
bool SMPFunction::PropagateGlobalMetadata(op_t UseOp, SMPMetadataType Status, int SSANum) {
bool changed = false;
if ((0 > SSANum) || (o_void == UseOp.type))
return false;
// Find the DEF of UseOp with SSANum.
bool FoundDef = false;
list<SMPInstr>::iterator CurrInst;
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
set<DefOrUse, LessDefUse>::iterator CurrDef;
set<DefOrUse, LessDefUse>::iterator CurrUse;
CurrDef = CurrInst->FindDef(UseOp);
if (CurrDef != CurrInst->GetLastDef()) {
if (SSANum == CurrDef->GetSSANum()) {
FoundDef = true;
if (Status != CurrDef->GetMetadataStatus()) {
CurrDef = CurrInst->SetDefMetadata(UseOp, Status);
changed = (CurrDef != CurrInst->GetLastDef());
// If source operand was memory, we have two cases.
// (1) The instruction could be a load, in which
// case we should simply terminate the
// propagation, because the prior DEF of a memory
// location is always considered live metadata
// already, and we do not want to propagate liveness
// to the address regs in the USE list.
// EXCEPTION: For safe funcs, we propagate liveness
// for stack locations.
// (2) We could have an arithmetic operation such
// as reg := reg arithop memsrc. In this case, we
// still do not want to propagate through the memsrc,
// (with the same safe func EXCEPTION),
// but the register is both DEF and USE and we need
// to propagate through the register.
if (CurrInst->HasSourceMemoryOperand()) {
if (this->SafeFunc) {
op_t MemSrcOp = CurrInst->MDGetMemUseOp();
assert(o_void != MemSrcOp.type);
if (MDIsStackAccessOpnd(MemSrcOp, this->UseFP)) {
// We have a SafeFunc stack access. This is
// the EXCEPTION case where we want to
// propagate metadata liveness for a memory
// location.
CurrUse = CurrInst->FindUse(MemSrcOp);
assert(CurrUse != CurrInst->GetLastUse());
if (this->IsGlobalName(MemSrcOp)) {
changed |= this->PropagateGlobalMetadata(MemSrcOp,
Status, CurrUse->GetSSANum()); }
else {
changed |= CurrInst->GetBlock()->PropagateLocalMetadata(MemSrcOp,
Status, CurrUse->GetSSANum());
}
} // end if stack access operand
} // end if SafeFunc
if (3 == CurrInst->GetOptType()) { // move inst
break; // load address regs are not live metadata
}
else if ((5 == CurrInst->GetOptType())
|| (NN_and == CurrInst->GetCmd().itype)
|| (NN_or == CurrInst->GetCmd().itype)
|| (NN_xor == CurrInst->GetCmd().itype)) {
// add, subtract, and, or with memsrc
// Find the DEF reg in the USE list.
CurrUse = CurrInst->FindUse(UseOp);
assert(CurrUse != CurrInst->GetLastUse());
changed |= this->PropagateGlobalMetadata(UseOp,
Status, CurrUse->GetSSANum());
break;
}
} // end if memory source
// Now, propagate the metadata status to all the
// non-memory, non-flags-reg, non-special-reg
// (i.e. regular registers) USEs.
CurrUse = CurrInst->GetFirstUse();
while (CurrUse != CurrInst->GetLastUse()) {
op_t UseOp = CurrUse->GetOp();
// NOTE: **!!** To be less conservative, we
// should propagate less for exchange category
// instructions.
if ((UseOp.type == o_reg) && (!UseOp.is_reg(R_sp))
&& (!(this->UseFP && UseOp.is_reg(R_bp)))
&& (!UseOp.is_reg(X86_FLAGS_REG))) {
if (this->IsGlobalName(UseOp)) {
changed |= this->PropagateGlobalMetadata(UseOp,
Status, CurrUse->GetSSANum());
}
else {
changed |= CurrInst->GetBlock()->PropagateLocalMetadata(UseOp,
Status, CurrUse->GetSSANum());
}
}
++CurrUse;
} // end while all USEs
}
break;
}
}
}
if (!FoundDef) {
// Check the Phi functions
list<SMPBasicBlock>::iterator CurrBlock;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
set<SMPPhiFunction, LessPhi>::iterator DefPhi;
DefPhi = CurrBlock->FindPhi(UseOp);
if (DefPhi != CurrBlock->GetLastPhi()) {
if (SSANum == DefPhi->GetDefSSANum()) {
if (Status != DefPhi->GetDefMetadata()) {
DefPhi = CurrBlock->SetPhiDefMetadata(UseOp, Status);
changed = true;
// If the Phi DEF has live metadata, then the Phi
// USEs each have live metadata. Propagate.
int UseSSANum;
for (size_t index = 0; index < DefPhi->GetPhiListSize(); ++index) {
UseSSANum = DefPhi->GetUseSSANum(index); // UseSSANum can be -1 in some cases because
// we conservatively make EAX and EDX be USEs
// of all return instructions, when the function
// might have a void return type, making it
// appear as if an uninitialized EAX or EDX
// could make it to the return block.
if (0 <= UseSSANum) {
changed |= this->PropagateGlobalMetadata(UseOp,
Status, UseSSANum);
}
}
}
FoundDef = true;
break;
}
}
} // end for all blocks
} // end if !FoundDef
if (!FoundDef) {
msg("ERROR: Could not find DEF of SSANum %d for: ", SSANum);
PrintOperand(UseOp);
msg(" in function %s\n", this->GetFuncName());
}
return changed;
} // end of SMPFunction::PropagateGlobalMetadata()
// Find consecutive DEFs of the same type and mark the second one redundant.
void SMPFunction::FindRedundantMetadata(void) {
list<SMPBasicBlock>::iterator CurrBlock;
bool changed = false;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
changed |= CurrBlock->FindRedundantLocalMetadata(this->SafeFunc);
}
return;
} // end of SMPFunction::FindRedundantMetadata()
// Compute SSA form data structures across the function.
void SMPFunction::ComputeSSA(void) {
bool DebugFlag = false;
bool DumpFlag = false;
#if SMP_DEBUG_DATAFLOW
DumpFlag |= (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
DebugFlag |= (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
#endif
#if 1
if (DumpFlag)
this->Dump();
#endif
if (DebugFlag) msg("Computing IDoms.\n");
this->ComputeIDoms();
if (DebugFlag) msg("Computing Dom frontiers.\n");
this->ComputeDomFrontiers();
if (DebugFlag) msg("Computing global names.\n");
this->ComputeGlobalNames();
if (DebugFlag) msg("Computing blocks defined in.\n");
this->ComputeBlocksDefinedIn();
if (DebugFlag) msg("Inserting Phi functions.\n");
this->InsertPhiFunctions();
if (DebugFlag) msg("Building dominator tree.\n");
this->BuildDominatorTree();
if (DebugFlag) msg("Computing SSA renumbering.\n");
this->SSARenumber();
list<SMPBasicBlock>::iterator CurrBlock;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
if (DumpFlag) CurrBlock->Dump();
if (DebugFlag) msg("Computing local names.\n");
CurrBlock->SetLocalNames();
if (DebugFlag) msg("Computing local SSA renumbering.\n");
CurrBlock->SSALocalRenumber();
if (DumpFlag) CurrBlock->Dump();
#if SMP_FULL_LIVENESS_ANALYSIS
if (DebugFlag) msg("Computing global chains.\n");
CurrBlock->CreateGlobalChains();
#endif
#if 1
if (DebugFlag) msg("Marking dead registers.\n");
CurrBlock->MarkDeadRegs();
#endif
}
#if SMP_DEBUG_DATAFLOW
if (DumpFlag)
this->Dump();
#endif
return;
} // end of SMPFunction::ComputeSSA()
// Find memory writes (DEFs) with possible aliases
void SMPFunction::AliasAnalysis(void) {
// First task: Mark which memory DEFs MIGHT be aliased because an
// indirect memory write occurs somewhere in the DEF-USE chain.
// Memory DEF-USE chains with no possible aliasing can be subjected
// to type inference and type-based optimizing annotations, e.g. a
// register spill to memory followed by retrieval from spill memory
// followed by NUMERIC USEs should be typed as a continuous NUMERIC
// chain if there is no possibility of aliasing.
// Preparatory step: For each indirect write, mark all def-use chains
// (maintained at the basic block level) that include the indirect
// write instruction. If there are no indirect writes in the function,
// leave all DEFs marked as unaliased and exit.
if (!(this->HasIndirectWrites))
return;
list<SMPBasicBlock>::iterator CurrBlock;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
list<list<SMPInstr>::iterator>::iterator CurrInst;
for (CurrInst = CurrBlock->GetFirstInstr();
CurrInst != CurrBlock->GetLastInstr();
++CurrInst) {
if ((*CurrInst)->HasIndirectMemoryWrite()) {
CurrBlock->MarkIndWriteChains((*CurrInst)->GetAddr());
// Until we get true aliasing analysis, any indirect write
// is classified as may-be-aliased.
CurrBlock->SetMaybeAliased(true);
}
} // end for all insts in block
} // end for all blocks in function
// Step one: Find only the memory DEFs to start with.
list<SMPInstr>::iterator CurrInst;
bool FoundIndWrite = false;
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
if (CurrInst->HasDestMemoryOperand()) {
// Starting with the DEF instruction, traverse the control flow
// until we run into (A) the re-definition of the operand, including
// a re-definition of any of its addressing registers, or (B) an
// indirect write. Return false if condition A terminates the
// search, and true if condition B terminates the search.
this->ResetProcessedBlocks();
op_t MemDefOp = CurrInst->MDGetMemDefOp();
assert(o_void != MemDefOp.type);
set<DefOrUse, LessDefUse>::iterator CurrMemDef = CurrInst->FindDef(MemDefOp);
assert(CurrMemDef != CurrInst->GetLastDef()); int SSANum = CurrMemDef->GetSSANum();
FoundIndWrite = this->FindPossibleChainAlias(CurrInst, MemDefOp, SSANum);
if (FoundIndWrite) {
// Mark the DEF as aliased.
CurrMemDef = CurrInst->SetDefIndWrite(CurrMemDef->GetOp(), true);
break; // Don't waste time after first alias found
}
} // end if inst has dest memory operand
} // end for all instructions
return;
} // end of SMPFunction::AliasAnalysis()
// Does the DefOp DEF_USE chain have an indirect mem write starting at CurrInst?
bool SMPFunction::FindPossibleChainAlias(list<SMPInstr>::iterator CurrInst, op_t DefOp, int SSANum) {
bool DebugFlag = false;
if (0 == strcmp("sdissect", this->GetFuncName())) {
// Next line is just a good place to set a break point.
DebugFlag = true;
}
// Starting with the DEF instruction, traverse the control flow
// until we run into (A) the re-definition of the operand, including
// a re-definition of any of its addressing registers, or (B) an
// indirect write. Return false if condition A terminates the
// search, and true if condition B terminates the search.
SMPBasicBlock *CurrBlock = CurrInst->GetBlock();
if (!(CurrBlock->IsProcessed())) {
CurrBlock->SetProcessed(true);
}
else
return false; // block already processed
// Proceed by cases:
ea_t DefAddr = CurrInst->GetAddr();
// Case 1: Local name. Return the IndWrite flag for the local Def-Use
// chain begun by CurrInst.
if (CurrBlock->IsLocalName(DefOp)) {
return CurrBlock->GetLocalDUChainIndWrite(DefOp, SSANum);
}
// Case 2: Global name.
// Case 2A: If Def-Use chain within this block for this memory operand
// has its IndWrite flag set to true, then stop and return true.
else if (CurrBlock->GetGlobalDUChainIndWrite(DefOp, DefAddr)) {
return true;
}
// Case 2B: Else if Def-Use chain is not the last chain in this block
// for this operand, then there must be a later redefinition of the
// memory operand (with new SSA number assigned) later in this block.
// Because we did not fall into case 2A, we know there is no IndWrite
// within the current memory operand's chain, so we return false.
else if (CurrBlock->IsLastGlobalChain(DefOp, DefAddr)) {
return false;
}
// Case 2C: Else if current memory operand is NOT LiveOut, even though
// this is the last def-use chain in the block, then there is no more
// traversing of the control flow graph to be done. The chain has ended
// without encountering an IndWrite, so return false.
else if (!(CurrBlock->IsLiveOut(DefOp))) {
return false;
}
// Case 2D: We have passed all previous checks, so we must have a memory
// operand that reaches the end of the block without encountering an
// IndWrite and is LiveOut. Its may-alias status will be determined by
// following the control flow graph for all successor blocks and examining
// the def-use chains in those blocks. list<list<SMPBasicBlock>::iterator>::iterator SuccBlock;
SuccBlock = CurrBlock->GetFirstSucc();
bool FoundAliasedWrite = false;
do {
FoundAliasedWrite = this->FindChainAliasHelper((*SuccBlock), DefOp);
++SuccBlock;
} while (!FoundAliasedWrite && (SuccBlock != CurrBlock->GetLastSucc()));
return FoundAliasedWrite;
} // end of SMPFunction::FindPossibleChainAlias()
// recursive helper for global DU-chains that traverse CFG
bool SMPFunction::FindChainAliasHelper(list<SMPBasicBlock>::iterator CurrBlock, op_t DefOp) {
bool DebugFlag = false;
if (0 == strcmp("mem2chunk_check", this->GetFuncName())) {
// Next line is just a good place to set a break point.
DebugFlag = true;
}
if (!(CurrBlock->IsProcessed())) {
CurrBlock->SetProcessed(true);
}
else
return false; // block already processed
// The LVA sets can be used to decide whether it is possible that
// the incoming DU chain overlaps a may-alias write. We can express
// the decision making in a truth table:
//
// Case # LiveIn? Killed? AliasedWrite in block? Action to take
// ------- ------- ------- ---------------------- --------------
// 1 N N N return false
// 2 N N Y return false
// 3 N Y N return false
// 4 N Y Y return false
// 5 Y N N recurse into successors
// 6 Y N Y return true
// 7 Y Y N return false
// 8 Y Y Y check location of aliased write
//
// In the last case, if there is an aliased write before the
// incoming DEF is killed and after it is used, then the
// incoming DU chain overlaps an aliased write, otherwise
// it does not.
// If not LiveIn, incoming DU chain does not run through this block
// at all, so return false.
if (!(CurrBlock->IsLiveIn(DefOp)))
return false; // cases 1-4
bool killed = CurrBlock->IsVarKill(DefOp);
bool BlockHasAliasedWrite = CurrBlock->MaybeAliasedWrite();
if (BlockHasAliasedWrite) {
// If DefOp is LiveIn and is not killed, then any aliased
// write in the block overlaps the incoming DU chain.
if (!killed) {
return true; // case 6
}
// If DefOp is LiveIn and is killed, then the location
// of the aliased write is the determining factor.
else {
// Incoming global DU chains get a new global DU chain
// built within the block with a pseudo-DefAddr of
// one byte before the first address of the block.
ea_t PseudoDefAddr = CurrBlock->GetFirstAddr() - 1;
return CurrBlock->GetGlobalDUChainIndWrite(DefOp, PseudoDefAddr); // case 8
}
} else {
// If killed, no aliased write, then cannot overlap an aliased write.
if (killed)
return false; // case 7
else {
// Need to recurse into all successors, because we passed through
// the block without seeing an aliased write and without killing
// the DefOp.
list<list<SMPBasicBlock>::iterator>::iterator SuccBlock;
SuccBlock = CurrBlock->GetFirstSucc();
bool FoundAliasedWrite = false;
while (!FoundAliasedWrite && (SuccBlock != CurrBlock->GetLastSucc())) {
FoundAliasedWrite = this->FindChainAliasHelper((*SuccBlock), DefOp);
++SuccBlock;
};
if (DebugFlag) {
msg("FindChainAliasHelper is returning %d\n", FoundAliasedWrite);
}
return FoundAliasedWrite;
}
}
assert(false); // statement should be unreachable
return false;
} // end of SMPFunction::FindChainAliasHelper()
// Link basic blocks to their predecessors and successors, and build the map
// of instruction addresses to basic blocks.
void SMPFunction::SetLinks(void) {
list<SMPBasicBlock>::iterator CurrBlock;
#if SMP_DEBUG_DATAFLOW_VERBOSE
msg("SetLinks called for %s\n", this->GetFuncName());
#endif
// First, set up the map of instructions to basic blocks.
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
list<list<SMPInstr>::iterator>::iterator CurrInst;
for (CurrInst = CurrBlock->GetFirstInstr();
CurrInst != CurrBlock->GetLastInstr();
++CurrInst) {
pair<ea_t, list<SMPBasicBlock>::iterator> MapItem((*CurrInst)->GetAddr(),CurrBlock);
InstBlockMap.insert(MapItem);
}
}
#if SMP_DEBUG_DATAFLOW_VERBOSE
msg("SetLinks finished mapping: %s\n", this->GetFuncName());
#endif
// Next, set successors of each basic block, also setting up the predecessors in the
// process.
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
list<SMPInstr>::iterator CurrInst = *(--(CurrBlock->GetLastInstr()));
bool CondTailCall = false;
if (CurrBlock->HasReturn()) {
if (!(CurrInst->IsCondTailCall())) {
// We either have a return instruction or an unconditional
// tail call instruction. We don't want to link to the
// tail call target, and there is no link for a return
continue;
}
else {
// We have a conditional tail call. We don't want to
// link to the tail call target, but we do want fall
// through to the next instruction.
CondTailCall = true;
}
}
// Last instruction in block; set successors
bool CallFlag = (CALL == CurrInst->GetDataFlowType());
bool IndirCallFlag = (INDIR_CALL == CurrInst->GetDataFlowType()); bool TailCallFlag = CondTailCall && CurrInst->IsCondTailCall();
bool IndirJumpFlag = (INDIR_JUMP == CurrInst->GetDataFlowType());
xrefblk_t CurrXrefs;
bool LinkedToTarget = false;
for (bool ok = CurrXrefs.first_from(CurrInst->GetAddr(), XREF_ALL);
ok;
ok = CurrXrefs.next_from()) {
if ((CurrXrefs.to != 0) && (CurrXrefs.iscode)) {
// Found a code target, with its address in CurrXrefs.to
if ((CallFlag || IndirCallFlag || TailCallFlag)
&& (CurrXrefs.to != (CurrInst->GetAddr() + CurrInst->GetCmd().size))) {
// A call instruction will have two targets: the fall through to the
// next instruction, and the called function. We want to link to the
// fall-through instruction, but not to the called function.
// Some blocks end with a call just because the fall-through instruction
// is a jump target from elsewhere.
continue;
}
map<ea_t, list<SMPBasicBlock>::iterator>::iterator MapEntry;
MapEntry = this->InstBlockMap.find(CurrXrefs.to);
if (MapEntry == this->InstBlockMap.end()) {
msg("WARNING: addr %x not found in map for %s\n", CurrXrefs.to,
this->GetFuncName());
msg(" Referenced from %s\n", CurrInst->GetDisasm());
}
else {
list<SMPBasicBlock>::iterator Target = MapEntry->second;
// Make target block a successor of current block.
CurrBlock->LinkToSucc(Target);
// Make current block a predecessor of target block.
Target->LinkToPred(CurrBlock);
LinkedToTarget = true;
#if SMP_USE_SWITCH_TABLE_INFO
if (IndirJumpFlag) {
#if SMP_DEBUG_SWITCH_TABLE_INFO
msg("Switch table link: jump at %x target at %x\n",
CurrInst->GetAddr(), CurrXrefs.to);
#else
;
#endif
}
#endif
}
}
} // end for all xrefs
if (IndirJumpFlag && (!LinkedToTarget)) {
this->UnresolvedIndirectJumps = true;
msg("WARNING: Unresolved indirect jump at %x\n", CurrInst->GetAddr());
}
else if (IndirCallFlag && (!LinkedToTarget)) {
this->UnresolvedIndirectCalls = true;
msg("WARNING: Unresolved indirect call at %x\n", CurrInst->GetAddr());
}
} // end for all blocks
// If we have any blocks that are all no-ops and have no predecessors, remove those
// blocks. They are dead and make the CFG no longer a lattice. Any blocks that have
// no predecessors but are not all no-ops should also be removed with a different
// log message.
// NOTE: Prior to construction of hell nodes in functions with unresolved indirect jumps,
// we cannot conclude that a block with no predecessors is unreachable. Also, the block
// order might be such that removal of a block makes an already processed block
// unreachable, so we have to iterate until there are no more changes.
// NOTE: An odd new gcc recursion optimization uses indirect calls within the function, so
// they can behave like indirect jumps.
#if SMP_USE_SWITCH_TABLE_INFO
if (!(this->HasUnresolvedIndirectJumps() || this->HasUnresolvedIndirectCalls())) {
#else
if (!(this->HasIndirectJumps())) {
#endif bool changed;
bool NoPredecessors;
bool OnlyPredIsItself;
list<list<SMPBasicBlock>::iterator>::iterator CurrPred;
do {
changed = false;
CurrBlock = this->Blocks.begin();
++CurrBlock; // don't delete the top block, no matter what.
while (CurrBlock != this->Blocks.end()) {
OnlyPredIsItself = false;
CurrPred = CurrBlock->GetFirstPred();
NoPredecessors = (CurrPred == CurrBlock->GetLastPred());
if (!NoPredecessors) {
if ((*CurrPred)->GetFirstAddr() == CurrBlock->GetFirstAddr()) { // self-recursion
++CurrPred; // any more preds besides itself?
OnlyPredIsItself = (CurrPred == CurrBlock->GetLastPred());
// Only predecessor was the self-recursion if no more preds
}
}
if (NoPredecessors || OnlyPredIsItself) {
if (CurrBlock->AllNops())
msg("Removing all nops block at %x\n", CurrBlock->GetFirstAddr());
else
msg("Removing block with no predecessors at %x\n", CurrBlock->GetFirstAddr());
// Remove this block from the predecessors list of its successors.
list<list<SMPBasicBlock>::iterator>::iterator SuccIter;
ea_t TempAddr = CurrBlock->GetFirstAddr();
for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
(*SuccIter)->ErasePred(TempAddr);
}
// Remove the unreachable instructions from the function inst list.
list<list<SMPInstr>::iterator>::iterator InstIter;
for (InstIter = CurrBlock->GetFirstInstr(); InstIter != CurrBlock->GetLastInstr(); ++InstIter) {
list<SMPInstr>::iterator DummyIter = this->Instrs.erase(*InstIter);
}
// Finally, remove the block from the blocks list.
CurrBlock = this->Blocks.erase(CurrBlock);
this->BlockCount -= 1;
changed = true;
}
else
++CurrBlock;
} // end while all blocks after the first one
} while (changed);
} // end if not indirect jumps
return;
} // end of SMPFunction::SetLinks()
// Number all basic blocks in reverse postorder (RPO) and set RPOBlocks vector to
// access them.
void SMPFunction::RPONumberBlocks(void) {
#if SMP_DEBUG_DATAFLOW
bool DebugFlag = false;
DebugFlag = (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
if (DebugFlag) msg("Entered RPONumberBlocks\n");
#endif
int CurrNum = 0;
list<list<SMPBasicBlock>::iterator> WorkList;
// Number the first block with 0.
list<SMPBasicBlock>::iterator CurrBlock = this->Blocks.begin();
#if 0
if (this->RPOBlocks.capacity() <= (size_t) this->BlockCount) {
msg("Reserving %d RPOBlocks old value: %d\n", 2+this->BlockCount, this->RPOBlocks.capacity());
this->RPOBlocks.reserve(2 + this->BlockCount);
this->RPOBlocks.assign(2 + this->BlockCount, this->Blocks.end());
}
#endif
CurrBlock->SetNumber(CurrNum); this->RPOBlocks.push_back(CurrBlock);
++CurrNum;
// Push the first block's successors onto the work list.
list<list<SMPBasicBlock>::iterator>::iterator CurrSucc = CurrBlock->GetFirstSucc();
while (CurrSucc != CurrBlock->GetLastSucc()) {
WorkList.push_back(*CurrSucc);
++CurrSucc;
}
// Use the WorkList to iterate through all blocks in the function
list<list<SMPBasicBlock>::iterator>::iterator CurrListItem = WorkList.begin();
bool change;
while (!WorkList.empty()) {
change = false;
while (CurrListItem != WorkList.end()) {
if ((*CurrListItem)->GetNumber() != SMP_BLOCKNUM_UNINIT) {
// Duplicates get pushed onto the WorkList because a block
// can be the successor of multiple other blocks. If it is
// already numbered, it is a duplicate and can be removed
// from the list.
CurrListItem = WorkList.erase(CurrListItem);
change = true;
continue;
}
if ((*CurrListItem)->AllPredecessorsNumbered()) {
// Ready to be numbered.
(*CurrListItem)->SetNumber(CurrNum);
#if 0
msg("Set RPO number %d\n", CurrNum);
if (DebugFlag && (7 == CurrNum))
this->Dump();
#endif
this->RPOBlocks.push_back(*CurrListItem);
++CurrNum;
change = true;
// Push its unnumbered successors onto the work list.
CurrSucc = (*CurrListItem)->GetFirstSucc();
while (CurrSucc != (*CurrListItem)->GetLastSucc()) {
if ((*CurrSucc)->GetNumber() == SMP_BLOCKNUM_UNINIT)
WorkList.push_back(*CurrSucc);
++CurrSucc;
}
CurrListItem = WorkList.erase(CurrListItem);
}
else {
++CurrListItem;
}
} // end while (CurrListItem != WorkList.end())
if (change) {
// Reset CurrListItem to beginning of work list for next iteration.
CurrListItem = WorkList.begin();
}
else {
// Loops can cause us to not be able to find a WorkList item that has
// all predecessors numbered. Take the WorkList item with the lowest address
// and number it so we can proceed.
CurrListItem = WorkList.begin();
ea_t LowAddr = (*CurrListItem)->GetFirstAddr();
list<list<SMPBasicBlock>::iterator>::iterator SaveItem = CurrListItem;
++CurrListItem;
while (CurrListItem != WorkList.end()) {
if (LowAddr > (*CurrListItem)->GetFirstAddr()) {
SaveItem = CurrListItem;
LowAddr = (*CurrListItem)->GetFirstAddr();
}
++CurrListItem;
}
// SaveItem should now be numbered.
(*SaveItem)->SetNumber(CurrNum);
#if SMP_DEBUG_DATAFLOW msg("Picked LowAddr %x and set RPO number %d\n", LowAddr, CurrNum);
#endif
this->RPOBlocks.push_back(*SaveItem);
++CurrNum;
// Push its unnumbered successors onto the work list.
CurrSucc = (*SaveItem)->GetFirstSucc();
while (CurrSucc != (*SaveItem)->GetLastSucc()) {
if ((*CurrSucc)->GetNumber() == SMP_BLOCKNUM_UNINIT)
WorkList.push_back(*CurrSucc);
++CurrSucc;
}
CurrListItem = WorkList.erase(SaveItem);
CurrListItem = WorkList.begin();
} // end if (change) ... else ...
} // end while work list is nonempty
// Prior to construction of hell nodes for functions with indirect jumps, there
// could still be unnumbered blocks because they appear to be unreachable
// (no predecessors from SetLinks() because they are reached only via indirect
// jumps). We need to number these and push them on the RPOBlocks vector so
// that the vector contains all the blocks.
// NOTE: Odd new gcc recursion optimization seems to use indirect calls to reach
// some blocks within a recursive function, operating somewhat like an indirect
// jump.
if (this->HasIndirectJumps() || this->HasIndirectCalls()) {
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
if (SMP_BLOCKNUM_UNINIT == CurrBlock->GetNumber()) {
msg("WARNING: Numbering indirectly reachable block at %x\n", CurrBlock->GetFirstAddr());
CurrBlock->SetNumber(CurrNum);
this->RPOBlocks.push_back(CurrBlock);
++CurrNum;
}
}
}
return;
} // end of SMPFunction::RPONumberBlocks()
// Perform live variable analysis on all blocks in the function.
// See chapter 9 of Cooper/Torczon, Engineering a Compiler, for the algorithm.
void SMPFunction::LiveVariableAnalysis(void) {
list<SMPBasicBlock>::iterator CurrBlock;
#if SMP_DEBUG_DATAFLOW
bool DebugFlag = (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
#endif
#if SMP_DEBUG_DATAFLOW_VERBOSE
msg("LiveVariableAnalysis for %s\n", this->GetFuncName());
#endif
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
// Initialize the Killed and UpwardExposed sets for each block.
CurrBlock->InitKilledExposed();
}
bool changed;
// Iterate over each block, updating LiveOut sets until no more changes are made.
// NOTE: LVA is more efficient when computed over a reverse post-order list of blocks
// from the inverted CFG. We have an RPO list from the forward CFG, so it is just as
// good to simply iterate through the blocks in layout order.
#if 1
do {
changed = false;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
changed |= CurrBlock->UpdateLiveOut();
}
} while (changed);
#else // Use reverse postorder
do {
changed = false;
for (size_t index = 0; index < this->RPOBlocks.size(); ++index) {
CurrBlock = this->RPOBlocks[index]; changed |= CurrBlock->UpdateLiveOut();
}
} while (changed);
#endif
#if SMP_USE_SSA_FNOP_MARKER
// Create DEFs in the marker instruction for all names in the LiveInSet
// of the first block. These are the names for the function that
// would otherwise look like USEs of uninitialized variables later.
// Note that the LiveVariableAnalysis work does not actually populate
// a LiveInSet for the first block, so we simulate it with its
// dataflow equation, UpExposed union (LiveOut minus VarKill).
set<op_t, LessOp>::iterator UpExposedIter, LiveOutIter;
list<SMPInstr>::iterator MarkerInst = this->Instrs.begin();
for (UpExposedIter = this->Blocks.begin()->GetFirstUpExposed();
UpExposedIter != this->Blocks.begin()->GetLastUpExposed();
++UpExposedIter) {
// Add DEF with SSANum of 0.
MarkerInst->AddDef(*UpExposedIter, UNINIT, 0);
// Add to the VarKill and LiveIn sets.
this->Blocks.begin()->AddVarKill(*UpExposedIter);
this->Blocks.begin()->AddLiveIn(*UpExposedIter);
}
for (LiveOutIter = this->Blocks.begin()->GetFirstLiveOut();
LiveOutIter != this->Blocks.begin()->GetLastLiveOut();
++LiveOutIter) {
if (!(this->Blocks.begin()->IsVarKill(*LiveOutIter))) {
// Add DEF with SSANum of 0.
MarkerInst->AddDef(*LiveOutIter, UNINIT, 0);
// Add to the VarKill and LiveIn sets.
this->Blocks.begin()->AddVarKill(*LiveOutIter);
this->Blocks.begin()->AddLiveIn(*LiveOutIter);
}
}
#endif
#if SMP_DEBUG_DATAFLOW_VERBOSE
if (DebugFlag) msg("Exiting LiveVariableAnalysis\n");
#endif
return;
} // end of SMPFunction::LiveVariableAnalysis()
// Return the IDom index that is the end of the intersection prefix of the Dom sets of
// the two blocks designated by the RPO numbers passed in.
// See Cooper & Torczon, "Engineering a Compiler" 1st edition figure 9.8.
int SMPFunction::IntersectDoms(int block1, int block2) const {
int finger1 = block1;
int finger2 = block2;
while (finger1 != finger2) {
while (finger1 > finger2)
finger1 = this->IDom.at(finger1);
while (finger2 > finger1)
finger2 = this->IDom.at(finger2);
}
return finger1;
} // end of SMPFunction::IntersectDoms()
// Compute immediate dominators of all blocks into IDom[] vector.
void SMPFunction::ComputeIDoms(void) {
bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
DebugFlag = (0 == strcmp("_Z_St20__throw_system_errori", this->GetFuncName()));
if (DebugFlag) msg("Entered ComputeIDoms\n");
#endif
// Initialize the IDom[] vector to uninitialized values for all blocks.
this->IDom.reserve(this->BlockCount);
this->IDom.assign(this->BlockCount, SMP_BLOCKNUM_UNINIT);
if (DebugFlag) msg("BlockCount = %d\n", this->BlockCount);
this->IDom[0] = 0; // Start block dominated only by itself
bool changed; do {
changed = false;
for (size_t RPONum = 1; RPONum < (size_t) this->BlockCount; ++RPONum) {
if (DebugFlag) msg("RPONum %d\n", RPONum);
if (DebugFlag) {
msg("RPOBlocks vector size: %d\n", this->RPOBlocks.size());
for (size_t index = 0; index < this->RPOBlocks.size(); ++index) {
msg("RPOBlocks entry %d is %d\n", index, RPOBlocks[index]->GetNumber());
}
}
// To avoid infinite loops on blocks that dominate themselves but otherwise have no
// predecessors (probably reachable only through indirect jumps), we stop processing
// the blocks once the IDom becomes the top (entry) block. This probably saves time
// on other blocks as well.
if (0 == this->IDom[RPONum])
continue;
list<SMPBasicBlock>::iterator CurrBlock = this->RPOBlocks.at(RPONum);
// if (DebugFlag) msg("CurrBlock: %x\n", CurrBlock._Ptr);
list<list<SMPBasicBlock>::iterator>::iterator CurrPred;
// Initialize NewIdom to the first processed predecessor of block RPONum.
int NewIdom = SMP_BLOCKNUM_UNINIT;
for (CurrPred = CurrBlock->GetFirstPred(); CurrPred != CurrBlock->GetLastPred(); ++CurrPred) {
int PredNum = (*CurrPred)->GetNumber();
if (DebugFlag) msg("Pred: %d\n", PredNum);
// **!!** See comment below about unreachable blocks.
if (SMP_BLOCKNUM_UNINIT == PredNum)
continue;
int PredIDOM = this->IDom.at(PredNum);
if (DebugFlag) msg("Pred IDom: %d\n", PredIDOM);
if (SMP_BLOCKNUM_UNINIT != PredIDOM) {
NewIdom = PredNum;
break;
}
}
if (NewIdom == SMP_BLOCKNUM_UNINIT) {
msg("Failure on NewIdom in ComputeIDoms for %s\n", this->GetFuncName());
if (this->HasIndirectJumps() || this->HasIndirectCalls()) {
// Might be reachable only through indirect jumps.
NewIdom = 0; // make it dominated by entry block
}
}
assert(NewIdom != SMP_BLOCKNUM_UNINIT);
// Loop through all predecessors of block RPONum except block NewIdom.
// Set NewIdom to the intersection of its Dom set and the Doms set of
// each predecessor that has had its Doms set computed.
for (CurrPred = CurrBlock->GetFirstPred(); CurrPred != CurrBlock->GetLastPred(); ++CurrPred) {
int PredNum = (*CurrPred)->GetNumber();
if (DebugFlag) msg("PredNum: %d\n", PredNum);
// **!!** We can avoid failure on unreachable basic blocks
// by executing a continue statement if PredNum is -1. Long term solution
// is to prune out unreachable basic blocks.
if (PredNum == SMP_BLOCKNUM_UNINIT)
continue;
int PredIDOM = this->IDom.at(PredNum);
if (DebugFlag) msg("PredIDOM: %d\n", PredIDOM);
if ((SMP_BLOCKNUM_UNINIT == PredIDOM) || (NewIdom == PredIDOM)) {
// Skip predecessors that have uncomputed Dom sets, or are the
// current NewIdom.
continue;
}
if (DebugFlag) msg("Old NewIdom value: %d\n", NewIdom);
NewIdom = this->IntersectDoms(PredNum, NewIdom);
if (DebugFlag) msg("New NewIdom value: %d\n", NewIdom);
}
// If NewIdom is not the value currently in vector IDom[], update the
// vector entry and set changed to true.
if (NewIdom != this->IDom.at(RPONum)) {
if (DebugFlag) msg("IDOM changed from %d to %d\n", this->IDom.at(RPONum), NewIdom);
this->IDom[RPONum] = NewIdom; changed = true;
}
}
} while (changed);
return;
} // end of SMPFunction::ComputeIDoms()
// Compute dominance frontier sets for each block.
void SMPFunction::ComputeDomFrontiers(void) {
list<SMPBasicBlock>::iterator CurrBlock;
list<SMPBasicBlock>::iterator RunnerBlock;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
// We look only at join points in the CFG, as per Cooper/Torczon chapter 9.
if (1 < CurrBlock->GetNumPreds()) { // join point; more than 1 predecessor
int runner;
list<list<SMPBasicBlock>::iterator>::iterator CurrPred;
for (CurrPred = CurrBlock->GetFirstPred(); CurrPred != CurrBlock->GetLastPred(); ++CurrPred) {
// For each predecessor, we run up the IDom[] vector and add CurrBlock to the
// DomFrontier for all blocks that are between CurrPred and IDom[CurrBlock],
// not including IDom[CurrBlock] itself.
runner = (*CurrPred)->GetNumber();
while (runner != this->IDom.at(CurrBlock->GetNumber())) {
// Cooper/Harvey/Kennedy paper does not quite agree with the later
// text by Cooper/Torczon. Text says that the start node has no IDom
// in the example on pages 462-463, but it shows an IDOM for the
// root node in Figure 9.9 of value == itself. The first edition text
// on p.463 seems correct, as the start node dominates every node and
// thus should have no dominance frontier.
if (SMP_TOP_BLOCK == runner)
break;
RunnerBlock = this->RPOBlocks.at(runner);
RunnerBlock->AddToDomFrontier(CurrBlock->GetNumber());
runner = this->IDom.at(runner);
}
} // end for all predecessors
} // end if join point
} // end for all blocks
return;
} // end of SMPFunction::ComputeDomFrontiers()
// Compute the GlobalNames set, which includes all operands that are used in more than
// one basic block. It is the union of all UpExposedSets of all blocks.
void SMPFunction::ComputeGlobalNames(void) {
set<op_t, LessOp>::iterator SetIter;
list<SMPBasicBlock>::iterator CurrBlock;
unsigned int index = 0;
if (this->Blocks.size() < 2)
return; // cannot have global names if there is only one block
bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
DebugFlag = (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
#endif
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
for (SetIter = CurrBlock->GetFirstUpExposed(); SetIter != CurrBlock->GetLastUpExposed(); ++SetIter) {
op_t TempOp = *SetIter;
// The GlobalNames set will have the complete collection of operands that we are
// going to number in our SSA computations. We now assign an operand number
// within the op_t structure for each, so that we can index into the
// BlocksUsedIn[] vector, for example. This operand number is not to be
// confused with SSA numbers.
// We use the operand number field op_t.n for the lower 8 bits, and the offset
// fields op_t.offb:op_t.offo for the upper 16 bits. We are overwriting IDA
// values here, but operands in the data flow analysis sets should never be
// inserted back into the program anyway.
SetGlobalIndex(&TempOp, index);
#if SMP_DEBUG_DATAFLOW
if (DebugFlag) { msg("Global Name: ");
PrintListOperand(TempOp);
}
#endif
set<op_t, LessOp>::iterator AlreadyInSet;
pair<set<op_t, LessOp>::iterator, bool> InsertResult;
InsertResult = this->GlobalNames.insert(TempOp);
if (!InsertResult.second) {
// Already in GlobalNames, so don't assign an index number.
;
#if SMP_DEBUG_DATAFLOW
if (DebugFlag) {
msg(" already in GlobalNames.\n");
}
#endif
}
else {
++index;
#if SMP_DEBUG_DATAFLOW
if (DebugFlag) {
msg(" inserted as index %d\n", ExtractGlobalIndex(TempOp));
}
#endif
}
} // for each upward exposed item in the current block
} // for each basic block
assert(16777215 >= this->GlobalNames.size()); // index fits in 24 bits
return;
} // end of SMPFunction::ComputeGlobalNames()
// For each item in GlobalNames, record the blocks that DEF the item.
void SMPFunction::ComputeBlocksDefinedIn(void) {
// Loop through all basic blocks and examine all DEFs. For Global DEFs, record
// the block number in BlocksDefinedIn. The VarKillSet records DEFs without
// having to examine every instruction.
list<SMPBasicBlock>::iterator CurrBlock;
this->BlocksDefinedIn.clear();
for (size_t i = 0; i < this->GlobalNames.size(); ++i) {
list<int> TempList;
this->BlocksDefinedIn.push_back(TempList);
}
#if SMP_DEBUG_DATAFLOW_VERBOSE
msg("Number of GlobalNames: %d\n", this->GlobalNames.size());
msg("Size of BlocksDefinedIn: %d\n", this->BlocksDefinedIn.size());
#endif
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
set<op_t, LessOp>::iterator KillIter;
for (KillIter = CurrBlock->GetFirstVarKill(); KillIter != CurrBlock->GetLastVarKill(); ++KillIter) {
// If killed item is not a block-local item (it is global), record it.
set<op_t, LessOp>::iterator NameIter = this->GlobalNames.find(*KillIter);
if (NameIter != this->GlobalNames.end()) { // found in GlobalNames set
// We have a kill of a global name. Get index from three 8-bit fields.
unsigned int index = ExtractGlobalIndex(*NameIter);
if (index >= this->GlobalNames.size()) {
// We are about to assert false.
msg("ComputeBlocksDefinedIn: Bad index: %d limit: %d\n", index,
this->GlobalNames.size());
msg("Block number %d\n", CurrBlock->GetNumber());
msg("Killed item: ");
PrintListOperand(*KillIter);
msg("\n");
msg("This is a fatal error.\n");
}
assert(index < this->GlobalNames.size());
// index is a valid subscript for the BlocksDefinedIn vector. Push the
// current block number onto the list of blocks that define this global name.
this->BlocksDefinedIn[index].push_back(CurrBlock->GetNumber());
}
} }
return;
} // end of SMPFunction::ComputeBlocksDefinedIn()
// Compute the phi functions at the entry point of each basic block that is a join point.
void SMPFunction::InsertPhiFunctions(void) {
set<op_t, LessOp>::iterator NameIter;
list<int> WorkList; // list of block numbers
bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
DebugFlag = (0 == strcmp("uw_frame_state_for", this->GetFuncName()));
#endif
if (DebugFlag) msg("GlobalNames size: %d\n", this->GlobalNames.size());
for (NameIter = this->GlobalNames.begin(); NameIter != this->GlobalNames.end(); ++NameIter) {
int CurrNameIndex = (int) (ExtractGlobalIndex(*NameIter));
if (DebugFlag) msg("CurrNameIndex: %d\n", CurrNameIndex);
#if 0
DebugFlag = (DebugFlag && (6 == CurrNameIndex));
#endif
// Initialize the work list to all blocks that define the current name.
WorkList.clear();
list<int>::iterator WorkIter;
for (WorkIter = this->BlocksDefinedIn.at((size_t) CurrNameIndex).begin();
WorkIter != this->BlocksDefinedIn.at((size_t) CurrNameIndex).end();
++WorkIter) {
WorkList.push_back(*WorkIter);
}
// Iterate through the work list, inserting phi functions for the current name
// into all the blocks in the dominance frontier of each work list block.
// Insert into the work list each block that had a phi function added.
while (!WorkList.empty()) {
#if SMP_DEBUG_DATAFLOW_VERBOSE
if (DebugFlag) msg("WorkList size: %d\n", WorkList.size());
#endif
list<int>::iterator WorkIter = WorkList.begin();
while (WorkIter != WorkList.end()) {
set<int>::iterator DomFrontIter;
#if SMP_DEBUG_DATAFLOW_VERBOSE
if (DebugFlag) msg("WorkIter: %d\n", *WorkIter);
#endif
if (DebugFlag && (*WorkIter > this->BlockCount)) {
msg("ERROR: WorkList block # %d out of range.\n", *WorkIter);
}
list<SMPBasicBlock>::iterator WorkBlock = this->RPOBlocks[*WorkIter];
for (DomFrontIter = WorkBlock->GetFirstDomFrontier();
DomFrontIter != WorkBlock->GetLastDomFrontier();
++DomFrontIter) {
#if SMP_DEBUG_DATAFLOW_VERBOSE
if (DebugFlag) msg("DomFront: %d\n", *DomFrontIter);
#endif
if (DebugFlag && (*DomFrontIter > this->BlockCount)) {
msg("ERROR: DomFront block # %d out of range.\n", *DomFrontIter);
}
list<SMPBasicBlock>::iterator PhiBlock = this->RPOBlocks[*DomFrontIter];
// Before inserting a phi function for the current name in *PhiBlock,
// see if the current name is LiveIn for *PhiBlock. If not, there
// is no need for the phi function. This check is what makes the SSA
// a fully pruned SSA.
if (PhiBlock->IsLiveIn(*NameIter)) {
size_t NumPreds = PhiBlock->GetNumPreds();
DefOrUse CurrRef(*NameIter);
SMPPhiFunction CurrPhi(CurrNameIndex, CurrRef);
for (size_t NumCopies = 0; NumCopies < NumPreds; ++NumCopies) {
CurrPhi.PushBack(CurrRef); // inputs to phi
}
if (PhiBlock->AddPhi(CurrPhi)) {
// If not already in Phi set, new phi function was inserted.
WorkList.push_back(PhiBlock->GetNumber());
#if SMP_DEBUG_DATAFLOW_VERBOSE if (DebugFlag) msg("Added phi for name %d at top of block %d\n", CurrNameIndex, PhiBlock->GetNumber());
#endif
}
}
else {
if (DebugFlag) {
msg("Global %d not LiveIn for block %d\n", CurrNameIndex, PhiBlock->GetNumber());
}
}
} // end for all blocks in the dominance frontier
// Remove current block number from the work list
if (DebugFlag) {
msg("Removing block %d from work list.\n", *WorkIter);
}
WorkIter = WorkList.erase(WorkIter);
} // end for all block numbers in the work list
} // end while the work list is not empty
if (DebugFlag) msg("WorkList empty.\n");
} // end for all elements of the GlobalNames set
return;
} // end of SMPFunction::InsertPhiFunctions()
// Build the dominator tree.
void SMPFunction::BuildDominatorTree(void) {
size_t index;
// First, fill the DomTree vector with the parent numbers filled in and the child lists
// left empty.
for (index = 0; index < this->IDom.size(); ++index) {
pair<int, list<int> > DomTreeEntry;
DomTreeEntry.first = this->IDom.at(index);
DomTreeEntry.second.clear();
this->DomTree.push_back(DomTreeEntry);
}
// Now, push the children onto the appropriate lists.
for (index = 0; index < this->IDom.size(); ++index) {
// E.g. if block 5 has block 3 as a parent, then we fetch the number 3
// using the expression this->DomTree.at(index).first, which was just
// initialized in the previous loop. Then we go to DomTree entry 3 and push
// the number 5 on its child list.
int parent = this->DomTree.at(index).first;
if (parent != (int) index) // block can dominate itself, but not in DomTree!
this->DomTree.at(parent).second.push_back((int) index);
}
return;
} // end of SMPFunction::BuildDominatorTree()
// Helper for SSA subscript renumbering: return the next SSA number for the global name
// and increment the SSACounter to prepare the next number. Push the returned number onto
// the SSAStack for the global name.
int SMPFunction::SSANewNumber(size_t GlobNameIndex) {
int Subscript = this->SSACounter.at(GlobNameIndex);
++(this->SSACounter[GlobNameIndex]);
this->SSAStack[GlobNameIndex].push_back(Subscript);
return Subscript;
} // end of SMPFunction::SSANewNumber()
// Main helper for SSA subscript renumbering. Renumber within block throughout its phi
// functions, then its DEFs and USEs, then its phi successors. Recurse then on all
// successors in the dominator tree.
void SMPFunction::SSARename(int BlockNumber) {
assert(0 <= BlockNumber);
assert(BlockNumber < this->BlockCount);
list<SMPBasicBlock>::iterator CurrBlock = this->RPOBlocks.at((size_t) BlockNumber);
bool DumpFlag = false;
#if SMP_DEBUG_DATAFLOW_VERBOSE
DumpFlag |= (0 == strcmp("main", this->GetFuncName()));
DumpFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
DumpFlag |= (0 == strcmp("uw_frame_state_for", this->GetFuncName()));#endif
if (DumpFlag) msg("Entered SSARename for block number %d\n", BlockNumber);
// For each phi function at the top of the block, rename the DEF of the phi function
// using SSANewNumber() on the global name index.
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
list<SMPPhiFunction> TempPhiList;
int GlobalNameIndex;
for (CurrPhi = CurrBlock->GetFirstPhi(); CurrPhi != CurrBlock->GetLastPhi(); ++CurrPhi) {
GlobalNameIndex = CurrPhi->GetIndex();
assert(0 <= GlobalNameIndex);
int NewSSANum = this->SSANewNumber((size_t) GlobalNameIndex);
// Cannot change the C++ STL set item directly, as sets might become unordered.
SMPPhiFunction TempPhi = (*CurrPhi);
TempPhi.SetSSADef(NewSSANum);
TempPhiList.push_back(TempPhi);
}
// Go back through the Phi function set and replace the items that need to be updated.
// Thank you g++ for being a pain.
list<SMPPhiFunction>::iterator TempIter;
for (TempIter = TempPhiList.begin(); TempIter != TempPhiList.end(); ++TempIter) {
// Use the op_t from the first phi use, because they are all the same.
bool Erased = CurrBlock->ErasePhi(TempIter->GetPhiRef(0).GetOp());
assert(Erased);
// Now we can add back the phi function that had the DEF SSA number changed.
bool Added = CurrBlock->AddPhi(*TempIter);
assert(Added);
}
TempPhiList.clear();
if (DumpFlag) msg("Processed phi functions at top.\n");
// For each instruction in the block, rename all global USEs and then all global DEFs.
list<list<SMPInstr>::iterator>::iterator CurrInst;
for (CurrInst = CurrBlock->GetFirstInstr(); CurrInst != CurrBlock->GetLastInstr(); ++CurrInst) {
set<DefOrUse, LessDefUse>::iterator CurrUse = (*CurrInst)->GetFirstUse();
while (CurrUse != (*CurrInst)->GetLastUse()) {
// See if Use is a global name.
set<op_t, LessOp>::iterator GlobIter = this->GlobalNames.find(CurrUse->GetOp());
if (GlobIter != this->GlobalNames.end()) { // found it
unsigned int GlobIndex = ExtractGlobalIndex(*GlobIter);
if (GlobIndex > this->SSAStack.size()) {
// Get some debug info out to the log file before we crash.
msg("Bad GlobIndex: %d\n", GlobIndex);
msg("Error in function %s\n", this->GetFuncName());
exit(EXIT_FAILURE);
}
// Set the SSA number for this use to the top of stack SSA # (back())
int NewSSANum;
if (this->SSAStack.at(GlobIndex).empty()) {
// No top of stack entry to read.
#if SMP_DEBUG_UNINITIALIZED_SSA_NAMES
if (!(*CurrInst)->MDIsPopInstr() && (o_reg == GlobIter->type)) {
// POP uses the stack offset and generates spurious
// uninitialized variable messages for [esp+0].
msg("WARNING: function %s : Use of uninitialized variable: ",
this->GetFuncName());
msg(" Variable: ");
PrintListOperand(*GlobIter);
msg(" Block number: %d Address: %x Instruction: %s\n", BlockNumber,
(*CurrInst)->GetAddr(), (*CurrInst)->GetDisasm());
}
#endif
NewSSANum = SMP_SSA_UNINIT;
}
else {
NewSSANum = this->SSAStack.at(GlobIndex).back();
} CurrUse = (*CurrInst)->SetUseSSA(CurrUse->GetOp(), NewSSANum);
}
++CurrUse;
} // end for all USEs
set<DefOrUse, LessDefUse>::iterator CurrDef = (*CurrInst)->GetFirstDef();
while (CurrDef != (*CurrInst)->GetLastDef()) {
// See if Def is a global name.
set<op_t, LessOp>::iterator GlobIter = this->GlobalNames.find(CurrDef->GetOp());
if (GlobIter != this->GlobalNames.end()) { // found it
unsigned int GlobIndex = ExtractGlobalIndex(*GlobIter);
// Set the SSA number for this DEF to the SSANewNumber top of stack
CurrDef = (*CurrInst)->SetDefSSA(CurrDef->GetOp(), this->SSANewNumber(GlobIndex));
}
++CurrDef;
} // end for all DEFs
} // end for all instructions
if (DumpFlag) msg("Processed all instructions.\n");
// For all control flow graph (not dominator tree) successors, fill in the current
// (outgoing) SSA number in the corresponding USE slot in the phi function, for all
// global names appearing in phi functions.
list<list<SMPBasicBlock>::iterator>::iterator SuccIter;
for (SuccIter = CurrBlock->GetFirstSucc(); SuccIter != CurrBlock->GetLastSucc(); ++SuccIter) {
// What position in the Preds list of this successor is CurrBlock?
int ListPos = (*SuccIter)->GetPredPosition(BlockNumber);
assert(0 <= ListPos);
// Go through all phi functions in this successor. At ListPos position in the
// incoming arguments for that phi function, set the SSA number to the SSA number
// in the top of stack entry for the global name associated with that phi function.
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
for (CurrPhi = (*SuccIter)->GetFirstPhi(); CurrPhi != (*SuccIter)->GetLastPhi(); ++CurrPhi) {
int GlobIndex = CurrPhi->GetIndex();
int CurrSSA;
if (this->SSAStack.at(GlobIndex).empty()) {
// No top of stack entry to read.
#if SMP_DEBUG_UNINITIALIZED_SSA_NAMES
msg("WARNING: function %s : Path to use of uninitialized variable: ",
this->GetFuncName());
msg(" Variable: ");
PrintListOperand(CurrPhi->GetAnyOp());
msg(" Block number: %d Successor block number: %d\n", BlockNumber,
(*SuccIter)->GetNumber());
#endif
CurrSSA = SMP_SSA_UNINIT;
}
else {
CurrSSA = this->SSAStack.at(GlobIndex).back(); // fetch from top of stack
}
#if 0
// g++ is a pain in the neck and won't allow changes to the set item
// through CurrPhi, which it types as a const iterator, so this next line does
// not compile in g++. C++ does not know how to distinguish between changing
// the field that ordering is based on, and other fields, so g++ has to be
// strict, I guess.
CurrPhi->SetSSARef(ListPos, CurrSSA);
#else
SMPPhiFunction TempPhi = (*CurrPhi);
TempPhi.SetSSARef(ListPos, CurrSSA);
TempPhiList.push_back(TempPhi);
if (DumpFlag && (BlockNumber >= 3) && (BlockNumber <= 4)) {
msg("BlockNumber: %d ListPos: %d\n", BlockNumber, ListPos);
}
#endif
} // end for all phi functions in successor
// Go back through the Phi function set and replace the items that need to be updated.
// Thank you g++ for being a pain.
for (TempIter = TempPhiList.begin(); TempIter != TempPhiList.end(); ++TempIter) {
if (DumpFlag && (BlockNumber >= 3) && (BlockNumber <= 4)) {
msg("Special before phi dump:\n"); set<SMPPhiFunction, LessPhi>::iterator FoundPhi;
FoundPhi = (*SuccIter)->FindPhi(TempIter->GetAnyOp());
FoundPhi->Dump();
}
// Use the op_t from the first phi use, because they are all the same.
bool Erased = (*SuccIter)->ErasePhi(TempIter->GetPhiRef(0).GetOp());
assert(Erased);
// Now we can add back the phi function that had one SSA number changed.
bool Added = (*SuccIter)->AddPhi(*TempIter);
assert(Added);
if (DumpFlag && (BlockNumber >= 3) && (BlockNumber <= 4)) {
msg("Special after phi dump:\n");
set<SMPPhiFunction, LessPhi>::iterator FoundPhi;
FoundPhi = (*SuccIter)->FindPhi(TempIter->GetAnyOp());
FoundPhi->Dump();
}
}
TempPhiList.clear();
} // end for all successors of CurrBlock
if (DumpFlag) msg("Processed successor phi functions.\n");
// For each successor in the dominator tree, recurse.
list<int>::iterator ChildIter;
for (ChildIter = this->DomTree[BlockNumber].second.begin();
ChildIter != this->DomTree[BlockNumber].second.end();
++ChildIter) {
this->SSARename(*ChildIter);
}
if (DumpFlag) msg("Finished recursion.\n");
// Pop off all SSAStack entries pushed during this block. I.e. for each global name,
// pop its SSAStack once per DEF and once per phi function in this block.
for (CurrPhi = CurrBlock->GetFirstPhi(); CurrPhi != CurrBlock->GetLastPhi(); ++CurrPhi) {
GlobalNameIndex = CurrPhi->GetIndex();
this->SSAStack.at((size_t) GlobalNameIndex).pop_back();
}
if (DumpFlag) msg("Popped off entries due to phi functions.\n");
for (CurrInst = CurrBlock->GetFirstInstr(); CurrInst != CurrBlock->GetLastInstr(); ++CurrInst) {
set<DefOrUse, LessDefUse>::iterator CurrDef;
for (CurrDef = (*CurrInst)->GetFirstDef(); CurrDef !=(*CurrInst)->GetLastDef(); ++CurrDef) {
// See if DEF is a global name.
set<op_t, LessOp>::iterator GlobIter = this->GlobalNames.find(CurrDef->GetOp());
if (GlobIter != this->GlobalNames.end()) { // found it
unsigned int GlobIndex = ExtractGlobalIndex(*GlobIter);
this->SSAStack.at((size_t) GlobIndex).pop_back();
}
} // end for all DEFs
} // end for all instructions
if (DumpFlag) msg("Popped off entries due to instructions.\n");
return;
} // end of SMPFunction::SSARename()
// Main driver of SSA subscript renumbering.
void SMPFunction::SSARenumber(void) {
if (0 >= this->GlobalNames.size())
return; // no names to renumber
// Initialize stacks and counters of SSA numbers.
size_t GlobIndex;
assert(0 == this->SSACounter.size());
for (GlobIndex = 0; GlobIndex < this->GlobalNames.size(); ++GlobIndex) {
list<int> DummyList;
this->SSACounter.push_back(0);
this->SSAStack.push_back(DummyList);
}
// Recurse through the dominator tree starting with node 0.
this->SSARename(0);
return;} // end of SMPFunction::SSARenumber()
// Main driver for the type inference system.
void SMPFunction::InferTypes(bool FirstIter) {
// The type inference system is an iteration over four analysis steps, until
// a fixed point is reached:
// 1) Within an instruction, set types of operators based on the operator type,
// the operand types, and the instruction type category, and propagate the
// type of the SMP_ASSIGN operator to its DEF.
// 2) Propagate the type of a DEF along its SSA chain to all USEs of that SSA name.
// 3) If all USEs of an SSA name have the same type, but the DEF has no type,
// then infer that the DEF must have the same type.
// 4) If all references to a memory location have the same type, mark that memory
// location as having that type, if no aliasing occurs.
//
// The type inference system will mark DEFs and USEs in each instruction's DEF and USE
// sets with an inferred type. This inference on USEs is not conclusive for other USEs
// outside of that instruction. For example, a pointer could be read in from memory
// and used as a pointer, then hashed using an arithmetic operation. If the arithmetic
// operation always treats its source operands as NUMERIC and produces a NUMERIC
// result, e.g. SMP_BITWISE_XOR, then the USE of that pointer is NUMERIC within
// this xor instruction. If the DEF at the beginning of the SSA chain for the pointer
// is eventually marked as POINTER, then all USEs in the chain will be marked POINTER
// as well (see step 2 above). This inconsistency along the USE chain is perfectly
// acceptable in our type system. It is important to mark the USEs according to how
// we observe them being used, because consistent USEs will propagate back up to
// the DEF in step 3 above.
bool changed;
bool NewChange = false;
bool DebugFlag = false;
#if SMP_DEBUG_TYPE_INFERENCE
DebugFlag |= (0 == strcmp("InputMove", this->GetFuncName()));
#endif
list<SMPInstr>::iterator CurrInst;
set<DefOrUse, LessDefUse>::iterator CurrDef;
set<DefOrUse, LessDefUse>::iterator NextDef;
list<SMPBasicBlock>::iterator CurrBlock;
if (DebugFlag) {
this->Dump();
}
// One time only: Set the types of immediate values, flags register, stack and frame
// pointers, and floating point registers.
if (FirstIter) {
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
if (DebugFlag) {
msg("SetImmedTypes for inst at %x: %s\n", CurrInst->GetAddr(), CurrInst->GetDisasm());
}
CurrInst->SetImmedTypes(this->UseFP);
}
}
// Iterate until no more changes: set types in DEF and USE lists based on RTL
// operators and the instruction category, SSA DEF-USE chains, etc.
do {
do {
changed = false;
// Step one: Infer types within instructions, context free.
// Step two, propagating DEF types to all USEs, happens within step one
// whenever a DEF type is set for the first time.
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
if (DebugFlag) msg("Inferring types for %s\n", CurrInst->GetDisasm());
NewChange = CurrInst->InferTypes();
changed = (changed || NewChange);
}
} while (changed);
if (DebugFlag) msg("Finished type inference steps 1 and 2.\n");
// Step three: If all USEs of an SSA name have the same type, but the DEF has no
// type, then infer that the DEF must have the same type. this->TypedDefs = 0;
this->UntypedDefs = 0;
this->TypedPhiDefs = 0;
this->UntypedPhiDefs = 0;
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
// Find any DEF that still has type UNINIT.
CurrDef = CurrInst->GetFirstDef();
while (CurrDef != CurrInst->GetLastDef()) {
// Set erase() and insert() are needed to change types of DEFs, so
// get hold of the next iterator value now.
NextDef = CurrDef;
++NextDef;
NewChange = false;
if (UNINIT != CurrDef->GetType()) {
++(this->TypedDefs);
}
else {
op_t DefOp = CurrDef->GetOp();
bool MemDef = (DefOp.type != o_reg);
bool AliasedMemWrite = (MemDef && CurrDef->HasIndirectWrite());
++(this->UntypedDefs);
if (MDIsIndirectMemoryOpnd(DefOp, this->UseFP) // relax this?
#if 0
|| (o_mem == DefOp.type)
#endif
|| AliasedMemWrite) {
// Don't want to infer along DEF-USE chains for indirect
// memory accesses until we have alias analysis.
++CurrDef;
continue;
}
ea_t DefAddr = CurrInst->GetAddr();
// Call inference method based on whether it is a block-local
// name or a global name.
if (CurrInst->GetBlock()->IsLocalName(DefOp)) {
set<op_t, LessOp>::iterator NameIter;
NameIter = CurrInst->GetBlock()->FindLocalName(DefOp);
assert(CurrInst->GetBlock()->GetLastLocalName() != NameIter);
unsigned int LocIndex = ExtractGlobalIndex(*NameIter);
NewChange = CurrInst->GetBlock()->InferLocalDefType(DefOp, LocIndex, DefAddr);
if (NewChange) {
--(this->UntypedDefs);
++(this->TypedDefs);
}
changed = (changed || NewChange);
}
else {
// global name
bool CallInst = ((CALL == CurrInst->GetDataFlowType())
|| (INDIR_CALL == CurrInst->GetDataFlowType()));
SMPOperandType DefType = UNINIT;
DefType = this->InferGlobalDefType(DefOp,
CurrDef->GetSSANum(), CurrInst->GetBlock(), CallInst);
if (IsNotEqType(UNINIT, DefType)) {
CurrDef = CurrInst->SetDefType(DefOp, DefType);
--(this->UntypedDefs);
++(this->TypedDefs);
NewChange = true;
}
changed = (changed || NewChange);
} // end if local name ... else ...
} // end if (UNINIT != CurrDef->GetType()) .. else ...
CurrDef = NextDef;
} // end while all DEFs in the DEF set
} // end for all instructions
if (DebugFlag) msg("Finished type inference step 3.\n");
if (!changed) { // Check for Phi function DEFs that are still UNINIT
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
changed |= CurrBlock->InferAllPhiDefTypes();
} }
if (DebugFlag) msg("Finished unconditional phi type inference.\n");
#if SMP_CONDITIONAL_TYPE_PROPAGATION
if (!changed) { // Try conditional type propagation
changed |= this->ConditionalTypePropagation();
if (DebugFlag)
msg("changed = %d after conditional type propagation.\n", changed);
}
#endif
} while (changed);
// Record the meet of all register types that reach RETURN instructions.
this->MDFindReturnTypes();
return;
} // end of SMPFunction::InferTypes()
// Apply the profiler information to this function once we've inferred everything we can about it.
void SMPFunction::ApplyProfilerInformation(ProfilerInformation* pi)
{
assert(pi);
// If no profiler annotations are available, save time.
if (0 == pi->GetProfilerAnnotationCount())
return;
SetIsSpeculative(true);
list<SMPInstr>::iterator CurrInst;
set<DefOrUse, LessDefUse>::iterator CurrDef, NextDef;
bool DebugFlag = false;
#if SMP_DEBUG_PROFILED_TYPE_INFERENCE
DebugFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
#endif
// for each instruction in this function
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
// lookup whether a load at this instruction was profiled as always numeric
InstructionInformation* ii = pi->GetInfo( CurrInst->GetAddr());
if (ii && DebugFlag)
msg("Found instruction information for %x\n", CurrInst->GetAddr());
if (ii && ii->isNumeric()) {
#if SMP_DEBUG_PROFILED_TYPE_INFERENCE
msg("Found instruction information for %x and it's numeric!\n", CurrInst->GetAddr());
#endif
CurrInst->UpdateMemLoadTypes((SMPOperandType)(NUMERIC|PROF_BASE));
}
// lookup whether this instruction has been profiled as an indirect call
set<ea_t> indirect_call_targets = pi->GetIndirectCallTargets(CurrInst->GetAddr());
for (set<ea_t>::iterator ict_iter = indirect_call_targets.begin();
ict_iter != indirect_call_targets.end();
++ict_iter)
{
ea_t target = *ict_iter;
if (vector_exists(target, IndirectCallTargets))
IndirectCallTargets.push_back(target);
if (vector_exists(target, AllCallTargets))
AllCallTargets.push_back(target);
}
}
return;
} // end of SMPFunction::ApplyProfilerInformation
// For the UNINIT type DEF DefOp, see if all its USEs have// a single type. If so, set the DEF to that type and return type,
// else return UNINIT.
SMPOperandType SMPFunction::InferGlobalDefType(op_t DefOp, int SSANum, SMPBasicBlock *DefBlock, bool CallInst) {
bool DebugFlag = false;
bool FoundNumeric = false;
bool FoundPointer = false;
bool FoundUnknown = false;
bool FoundUninit = false;
#if SMP_DEBUG_TYPE_INFERENCE
DebugFlag |= (0 == strcmp("mem_init", this->GetFuncName()));
#endif
if (DebugFlag) {
msg("InferGlobalDefType for SSANum %d of ", SSANum);
PrintOperand(DefOp);
msg("\n");
}
list<SMPInstr>::iterator InstIter;
assert(0 <= SSANum);
set<DefOrUse, LessDefUse>::iterator CurrUse;
// Go through all instructions in the function and find the instructions
// that have USEs of DefOp with SSANum. If all USEs in the chain have
// a single type (other than UNINIT), change the DEF type to match the
// USE type and set changed to true.
bool FirstUseSeen = false;
SMPOperandType UseType = UNINIT;
SMPOperandType PtrType = UNINIT;
for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
CurrUse = InstIter->FindUse(DefOp);
if (CurrUse != InstIter->GetLastUse()) { // found a USE of DefOp
if (CurrUse->GetSSANum() == SSANum) { // matched SSA number
if (!FirstUseSeen) {
FirstUseSeen = true;
}
UseType = CurrUse->GetType();
FoundNumeric |= (IsNumeric(UseType));
FoundUnknown |= (IsUnknown(UseType));
FoundUninit |= (IsEqType(UNINIT, UseType));
if (IsDataPtr(UseType)) {
if (FoundPointer) {
if (IsNotEqType(PtrType, UseType)) {
#if SMP_DEBUG_TYPE_INFERENCE
msg("WARNING: Differing ptr types in global chain:");
msg(" Prev: %d Current: %d %s\n", PtrType, UseType,
InstIter->GetDisasm());
#endif
PtrType = POINTER;
}
}
else {
FoundPointer = true;
PtrType = UseType;
}
}
} // end if matched SSA #
} // end if found a USE of DefOp
} // end for all instructions
// Now, we need to check the phi functions and see if there are Phi USEs of the DefOp.
set<SMPPhiFunction, LessPhi>::iterator UsePhi;
size_t BlockNum;
for (BlockNum = 0; BlockNum < (size_t) this->BlockCount; ++BlockNum) {
UsePhi = this->RPOBlocks.at(BlockNum)->FindPhi(DefOp);
if (UsePhi != this->RPOBlocks.at(BlockNum)->GetLastPhi()) {
// Found phi function for DefOp. See if we can find a USE
// with USE SSANum corresponding to our DEF SSANum.
for (size_t PhiIndex = 0; PhiIndex < UsePhi->GetPhiListSize(); ++PhiIndex) { if (UsePhi->GetUseSSANum(PhiIndex) == SSANum) {
// We have a Phi USE that matches our DEF.
if (!FirstUseSeen) {
FirstUseSeen = true;
}
UseType = UsePhi->GetUseType(PhiIndex);
FoundNumeric |= (IsNumeric(UseType));
FoundUnknown |= (IsUnknown(UseType));
FoundUninit |= (IsEqType(UNINIT, UseType));
if (IsDataPtr(UseType)) {
if (FoundPointer) {
if (IsNotEqType(PtrType, UseType)) {
;
#if SMP_DEBUG_TYPE_INFERENCE
msg("WARNING: Differing ptr types in global chain at Phi:");
msg(" Prev: %d Current: %d BlockNum: %d\n",
PtrType, UseType, BlockNum);
#endif
}
PtrType = POINTER;
}
else {
FoundPointer = true;
PtrType = UseType;
}
}
} // end if matched SSA #
} // end for all Phi USEs
} // end if found matching Phi function for DefOp
} // end for all block numbers in the function
if (FirstUseSeen) {
// Do we have a consistent type?
// If we see any definite POINTER uses, we must set the DEF
// to type POINTER or a refinement of it.
if (FoundPointer)
UseType = PtrType;
else if (FoundNumeric && !FoundUninit && !FoundUnknown)
UseType = NUMERIC;
else
return UNINIT; // no POINTER, but no consistent type
assert(UNINIT != UseType);
if (DebugFlag) msg("Inferring global DEF of type %d\n", UseType);
return UseType;
}
else { // not FirstUseSeen
// If the block returns, then the DEFs could be used in the caller.
if (!(DefBlock->HasReturn())) {
UseType = UNINIT;
// We probably want to set the DEF type to NUMERIC if there are no uses.
// Have to check these cases out manually in the *.asm first. **!!**
// If they are memory DEFs, we cannot optimize, so we might want to see
// if we can find a reg DEF with no USEs here. We also want to exclude
// warning messages for the caller-saved reg DEFs generated for CALLs.
if ((o_reg == DefOp.type) && (!CallInst)) {
;
#if SMP_WARN_UNUSED_DEFS
msg("WARNING: global DEF with no USEs for SSANum %d DefOp: ",
SSANum);
PrintOperand(DefOp);
msg("\n");
#endif
}
}
}
return UseType;
} // end of SMPFunction::InferGlobalDefType()
#define SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION 1
#if SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION
// The simple form of conditional type propagation observes that we
// simply need to apply the meet operator over Phi function USEs and
// then propagate any DEF type changes using PropagateGlobalDefType().
// The outermost iteration over all type inference methods in InferTypes()
// will take care of all the propagation that is handled by the work list
// processing in the textbook algorithm.
// Iteration convergence might be slower in the simple approach, but the code
// is much simpler to debug.
bool SMPFunction::ConditionalTypePropagation(void) {
bool changed = false;
list<SMPBasicBlock>::iterator CurrBlock;
vector<list<SMPBasicBlock>::iterator>::iterator CurrRPO;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
for (CurrRPO = this->RPOBlocks.begin(); CurrRPO != this->RPOBlocks.end(); ++CurrRPO) {
CurrBlock = *CurrRPO;
SMPOperandType MeetType;
for (CurrPhi = CurrBlock->GetFirstPhi(); CurrPhi != CurrBlock->GetLastPhi(); ++CurrPhi) {
MeetType = CurrPhi->ConditionalMeetType();
// Here we use a straight equality test, not our macros,
// because we consider it a change if the MeetType is
// profiler derived and the DEFType is not.
if (MeetType == CurrPhi->GetDefType())
continue;
// Change the DEF type to the MeetType and propagate.
op_t DefOp = CurrPhi->GetAnyOp();
bool IsMemOp = (o_reg != DefOp.type);
CurrPhi = CurrBlock->SetPhiDefType(DefOp, MeetType);
changed = true;
this->ResetProcessedBlocks();
changed |= CurrBlock->PropagateGlobalDefType(DefOp,
MeetType, CurrPhi->GetDefSSANum(), IsMemOp);
} // end for all phi functions in the current block
} // end for all blocks
return changed;
} // end of SMPFunction::ConditionalTypePropagation()
#else // not SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION
// Apply the SCC (Sparse Conditional Constant) propagation algorithm to
// propagate types starting from unresolved Phi DEFs.
bool SMPFunction::ConditionalTypePropagation(void) {
bool changed = false;
// Collections of Phi functions and instructions that have a DEF
// with type UNINIT for the current global name.
map<int, set<SMPPhiFunction, LessPhi>::iterator> UninitDEFPhis;
vector<list<SMPInstr>::iterator> UninitDEFInsts;
// Work lists of Phi functions and instructions that need to be processed
// according to the SCC algorithm.
list<map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator> PhiWorkList;
list<vector<list<SMPInstr>::iterator>::iterator> InstWorkList;
// Iterate through all global names that are either (1) registers
// or (2) stack locations in SAFE functions.
set<op_t, LessOp>::iterator CurrGlob;
for (CurrGlob = this->GetFirstGlobalName(); CurrGlob != this->GetLastGlobalName(); ++CurrGlob) {
op_t GlobalOp = *CurrGlob;
list<SMPBasicBlock>::iterator CurrBlock;
vector<list<SMPBasicBlock>::iterator>::iterator CurrRPO;
if (MDIsIndirectMemoryOpnd(GlobalOp, this->UseFP))
continue; // need alias analysis to process indirect accesses
if ((GlobalOp.type != o_reg)
&& (!((this->ReturnAddrStatus == FUNC_SAFE) && MDIsStackAccessOpnd(GlobalOp, this->UseFP))))
continue; // not register, not safe stack access
// Set up a map (indexed by SSANum) of iterators to Phi functions
// for the current global name that have UNINIT as the Phi DEF type.
UninitDEFPhis.clear();
UninitDEFInsts.clear();
for (CurrRPO = this->RPOBlocks.begin(); CurrRPO != this->RPOBlocks.end(); ++CurrRPO) {
CurrBlock = *CurrRPO;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
CurrPhi = CurrBlock->FindPhi(GlobalOp);
if (CurrPhi != CurrBlock->GetLastPhi()) {
// Found Phi function for current global name.
if (IsEqType(CurrPhi->GetDefType(), UNINIT)) {
// Phi DEF is UNINIT; add Phi to the map.
pair<int, set<SMPPhiFunction, LessPhi>::iterator> TempPair(CurrPhi->GetDefSSANum(), CurrPhi);
bool Inserted = false;
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator WhereIns;
pair<map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator, bool> Result(WhereIns, Inserted);
Result = UninitDEFPhis.insert(TempPair);
assert(Result.second == true);
}
}
} // end for all blocks
// If any Phi DEF had UNINIT as its type, set up a vector of
// iterators to instructions that have UNINIT as the DEF type
// for the current global name.
if (UninitDEFPhis.empty())
continue;
list<SMPInstr>::iterator CurrInst;
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
set<DefOrUse, LessDefUse>::iterator CurrDef = CurrInst->FindDef(GlobalOp);
if (CurrDef != CurrInst->GetLastDef()) {
// Found DEF of current global name.
if (IsEqType(UNINIT, CurrDef->GetType())) {
UninitDEFInsts.push_back(CurrInst);
}
}
} // end for all instructions
// Put all UNINIT Phi DEFs that have at least one USE
// that is not UNINIT onto the PhiWorkList.
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator CurrUnPhi;
for (CurrUnPhi = UninitDEFPhis.begin(); CurrUnPhi != UninitDEFPhis.end(); ++CurrUnPhi) {
pair<int, set<SMPPhiFunction, LessPhi>::iterator> PhiDefPair(*CurrUnPhi);
if (PhiDefPair.second->HasTypedUses()) {
PhiWorkList.push_back(CurrUnPhi);
}
}
// Iterate until both work lists are empty:
while (!(PhiWorkList.empty() && InstWorkList.empty())) {
// Process Phi items first.
while (!PhiWorkList.empty()) {
// If applying the meet operator over the Phi USE types
// would produce a new DEF type, change the DEF type and
// propagate it, adding Phi functions and instructions that
// received the propagated type to their respective work lists.
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator MapIter;
MapIter = PhiWorkList.front();
PhiWorkList.pop_front(); // remove from work list
pair<int, set<SMPPhiFunction, LessPhi>::iterator> PhiDefPair;
PhiDefPair.first = MapIter->first;
PhiDefPair.second = MapIter->second;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi = PhiDefPair.second;
SMPOperandType MeetType = CurrPhi->ConditionalMeetType();
// Here we use a straight equality test, not our macros,
// because we consider it a change if the MeetType is
// profiler derived and the DEFType is not.
if (MeetType == CurrPhi->GetDefType())
continue;
// At this point, we need to set the DEFType to the MeetType // and propagate the change. We have a map of all the
// critical Phi functions for this global name, as well
// as a vector of the relevant instructions for this name.
CurrPhi->SetDefType(MeetType);
changed = true;
int DefSSANum = CurrPhi->GetDefSSANum();
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator PhiIter;
vector<list<SMPInstr>::iterator>::iterator InstIter;
// Propagate to Phi functions first.
for (PhiIter = UninitDEFPhis.begin(); PhiIter != UninitDEFPhis.end(); ++PhiIter) {
if (DefSSANum == PhiIter->first)
continue; // Skip the Phi that we just changed
for (size_t index = 0; index < PhiIter->second->GetPhiListSize(); ++index) {
if (DefSSANum == PhiIter->second->GetUseSSANum(index)) {
// Matched SSA # to USE. Propagate new type.
PhiIter->second->SetRefType(index, MeetType);
// Add this phi function to the work list.
PhiWorkList.push_back(PhiIter);
}
}
}
#define SMP_COND_TYPE_PROP_TO_INSTS 0
#if SMP_COND_TYPE_PROP_TO_INSTS
// Propagate to instructions with uninit DEFs of global name.
// The idea is that the instructions that hold up type propagation
// are the ones that USE and then DEF the same global name.
// For example, "increment EAX" has to know the type of
// the USE of EAX in order to set the type of the DEF.
#endif
} // end while the PhiWorkList is not empty
#if SMP_COND_TYPE_PROP_TO_INSTS
// The PhiWorkList is empty at this point, so process
// instructions on the InstWorkList.
#endif
} // end while both work lists are not empty
} // end for all global names
return changed;
} // end of SMPFunction::ConditionalTypePropagation()
#endif // end if SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION else ...
// Emit all annotations for the function, including all per-instruction
// annotations.
void SMPFunction::EmitAnnotations(FILE *AnnotFile) {
// Emit annotation for the function as a whole.
if (this->StaticFunc) {
qfprintf(AnnotFile, "%10x %6d FUNC LOCAL %s ", this->FuncInfo.startEA,
this->Size, this->FuncName);
}
else {
qfprintf(AnnotFile, "%10x %6d FUNC GLOBAL %s ", this->FuncInfo.startEA,
this->Size, this->FuncName);
}
switch (this->ReturnAddrStatus)
{
case FUNC_UNKNOWN:
{
qfprintf(AnnotFile, "FUNC_UNKNOWN ");
break;
}
case FUNC_SAFE:
{
qfprintf(AnnotFile, "FUNC_SAFE ");
break;
}
case FUNC_UNSAFE:
{
qfprintf(AnnotFile, "FUNC_UNSAFE ");
break;
} default:
assert(0);
}
if (this->UseFP) {
qfprintf(AnnotFile, "USEFP ");
}
else {
qfprintf(AnnotFile, "NOFP ");
}
if (this->FuncInfo.does_return()) {
qfprintf(AnnotFile, "RET ");
}
else {
qfprintf(AnnotFile, "NORET ");
}
if (this->IsLeaf())
qfprintf(AnnotFile, "FUNC_LEAF ");
// store the return address
qfprintf(AnnotFile,"%10x ", this->FuncInfo.endEA - 1);
if (this->IsLibFunc())
qfprintf(AnnotFile, "LIBRARY ");
qfprintf(AnnotFile, "\n");
// Emit annotations about how to restore register values
qfprintf(AnnotFile, "%10x %6d FUNC FRAMERESTORE ", this->FuncInfo.startEA, 0);
for(int i=R_ax; i<=R_di; i++)
{
qfprintf(AnnotFile, "%d %d %d ", i, this->SavedRegLoc[i], this->ReturnRegTypes[i]);
}
qfprintf(AnnotFile, "ZZ\n");
qfprintf(AnnotFile, "%10x %6d FUNC MMSAFENESS ", this->FuncInfo.startEA, 0);
if (!IsSpecSafe())
qfprintf(AnnotFile, "UNSAFE\n");
else if (!IsSafe())
qfprintf(AnnotFile, "SPECSAFE\n");
else {
assert(IsSafe());
qfprintf(AnnotFile, "SAFE\n");
}
// Loop through all instructions in the function.
// Output optimization annotations for those
// instructions that do not require full computation
// of their memory metadata by the Memory Monitor SDT.
list<SMPInstr>::iterator CurrInst;
bool AllocSeen = false; // Reached LocalVarsAllocInstr yet?
bool DeallocTrigger = false;
for (CurrInst = Instrs.begin(); CurrInst != Instrs.end(); ++CurrInst) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInst)
continue; // skip marker instruction
#endif
ea_t addr = CurrInst->GetAddr();
qfprintf(AnnotFile, "%10x %6d INSTR BELONGTO %x \n", addr, 0, GetStartAddr());
if (this->LocalVarsAllocInstr == addr) {
AllocSeen = true;
if (this->NeedsStackReferent)
this->EmitStackFrameAnnotations(AnnotFile, CurrInst);
else {
int OptType = CurrInst->GetOptType();
if (5 == OptType) { // ADD or SUB
// Prevent mmStrata from extending the caller's stack frame
// to include the new allocation. qfprintf(AnnotFile, "%10x %6d INSTR LOCAL SafeFrameAlloc %s \n",
addr, -1, CurrInst->GetDisasm());
}
else if (CurrInst->MDIsPushInstr()) {
qfprintf(AnnotFile, "%10x %6d INSTR LOCAL NoWarn %s \n",
addr, -3, CurrInst->GetDisasm());
}
}
}
// If this is the instruction which deallocated space
// for local variables, we set a flag to remind us to
// emit an annotation on the next instruction.
// mmStrata wants the instruction AFTER the
// deallocating instruction, so that it processes
// the deallocation after it happens. It inserts
// instrumentation before an instruction, not
// after, so it will insert the deallocating
// instrumentation before the first POP of callee-saved regs,
// if there are any, or before the return, otherwise.
if (addr == this->LocalVarsDeallocInstr) {
DeallocTrigger = true;
}
else if (DeallocTrigger) { // Time for annotation
qfprintf(AnnotFile, "%10x %6d DEALLOC STACK esp - %d %s\n", addr,
LocalVarsSize, LocalVarsSize, CurrInst->GetDisasm());
DeallocTrigger = false;
}
if (this->HasGoodRTLs()) {
CurrInst->EmitTypeAnnotations(this->UseFP, AllocSeen, this->NeedsStackReferent, AnnotFile);
}
else {
CurrInst->EmitAnnotations(this->UseFP, AllocSeen, this->NeedsStackReferent, AnnotFile);
}
if (CurrInst->MDIsReturnInstr() && this->GetReturnAddressStatus() == FUNC_SAFE )
CurrInst->EmitSafeReturn(AnnotFile);
} // end for all instructions
// Loop through all basic blocks and emit profiling request annotations
// for those blocks that have unsafe memory writes in them.
list<SMPBasicBlock>::iterator CurrBlock;
this->SafeBlocks = 0;
this->UnsafeBlocks = 0;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
if (CurrBlock->MaybeAliasedWrite()) {
++(this->UnsafeBlocks);
#if SMP_OPTIMIZE_BLOCK_PROFILING
list<list<SMPInstr>::iterator>::iterator CurrInst;
CurrInst = CurrBlock->GetFirstInstr();
ea_t addr = (*CurrInst)->GetAddr();
qfprintf(AnnotFile, "%10x %6d BLOCK PROFILECOUNT %s\n", addr,
(*CurrInst)->GetCmd().size, (*CurrInst)->GetDisasm());
#endif
}
else {
++(this->SafeBlocks);
}
}
return;
} // end of SMPFunction::EmitAnnotations()
// Debug output dump.
void SMPFunction::Dump(void) {
list<SMPBasicBlock>::iterator CurrBlock;
msg("Debug dump for function: %s\n", this->GetFuncName());
msg("UseFP: %d LocalVarsAllocInstr: %x\n", this->UseFP,
this->LocalVarsAllocInstr);
for (size_t index = 0; index < this->IDom.size(); ++index) {
msg("IDOM for %d: %d\n", index, this->IDom.at(index));
} for (size_t index = 0; index < this->DomTree.size(); ++index) {
msg("DomTree for %d: ", index);
list<int>::iterator DomIter;
for (DomIter = this->DomTree.at(index).second.begin();
DomIter != this->DomTree.at(index).second.end();
++DomIter) {
msg("%d ", *DomIter);
}
msg("\n");
}
msg("Global names: \n");
set<op_t, LessOp>::iterator NameIter;
for (NameIter = this->GlobalNames.begin(); NameIter != this->GlobalNames.end(); ++NameIter) {
msg("index: %d ", ExtractGlobalIndex(*NameIter));
PrintListOperand(*NameIter);
msg("\n");
}
msg("Blocks each name is defined in: \n");
for (size_t index = 0; index < this->BlocksDefinedIn.size(); ++index) {
msg("Name index: %d Blocks: ", index);
list<int>::iterator BlockIter;
for (BlockIter = this->BlocksDefinedIn.at(index).begin();
BlockIter != this->BlocksDefinedIn.at(index).end();
++BlockIter) {
msg("%d ", *BlockIter);
}
msg("\n");
}
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
// Dump out the function number and data flow sets before the instructions.
CurrBlock->Dump();
}
msg("End of debug dump for function: %s\n", this->GetFuncName());
return;
} // end of SMPFunction::Dump()
// Analyzes the function to see if the return address can be marked as safe
void SMPFunction::MarkFunctionSafe() {
#if SMP_DEBUG_FUNC
msg(" Analyzing function %s and isLeaf = %d \n ", this->GetFuncName(), this->IsLeaf());
#endif
bool HasCallTargets = false;
bool HasStackPointerCopy = false;
bool HasStackPointerPush = false;
bool HasIndirectGlobalWrite = false;
bool WritesAboveLocalFrame = false; // Direct writes above local frame
bool WritesAboveLocalFrameIndirect = false; // Indirect writes above local frame
bool HasIndexedStackWrite = false;
bool HasIndirectWrite = false;
this->ReturnAddrStatus = FUNC_SAFE;
this->SafeFunc = true;
if (!this->AllCallTargets.empty()) {
HasCallTargets = true;
}
#if SMP_USE_SWITCH_TABLE_INFO
if (this->UnresolvedIndirectJumps) {
#else
if (this->IndirectJumps) {
#endif
#if SMP_DEBUG_FUNC
msg("Function %s marked as unsafe due to indirect jumps\n", this->GetFuncName());
#endif
}
list<SMPInstr>::iterator Instructions;
// while processing the stack pointer writes the prologue code for // saving frame register and allcating local variables needs to be
// handled
bool SaveEBP = false;
bool XferESPtoEBP = false;
for (Instructions = Instrs.begin(); Instructions != Instrs.end(); ++Instructions) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == Instructions)
continue; // skip marker instruction
#endif
#if SMP_VERBOSE_DEBUG_FUNC
msg(" Total number of defs for this instruction %d\n", Instructions->NumDefs());
#endif
if (!SaveEBP) { // still looking for "push ebp"
if (Instructions->MDIsPushInstr() && Instructions->GetCmd().Operands[0].is_reg(R_bp)) {
SaveEBP = true;
continue;
}
}
else if (!XferESPtoEBP) { // found "push ebp", looking for "mov ebp,esp"
insn_t CurrCmd = Instructions->GetCmd();
if ((CurrCmd.itype == NN_mov)
&& (Instructions->GetFirstDef()->GetOp().is_reg(R_bp))
&& (Instructions->GetFirstUse()->GetOp().is_reg(R_sp))) {
XferESPtoEBP = true;
continue;
}
}
ea_t address = Instructions->GetAddr();
if (address == this->LocalVarsAllocInstr ||
address == this->LocalVarsDeallocInstr)
continue;
if (Instructions->MDIsStackPointerCopy(this->UseFP)) {
HasStackPointerCopy = true;
if (NN_lea == Instructions->GetCmd().itype) {
// If an lea instruction loads an address above
// the stack frame, we must assume that writes
// above the stack frame could occur.
if (this->WritesAboveLocalFrame(Instructions->GetCmd().Operands[1]))
WritesAboveLocalFrameIndirect = true;
}
#if SMP_DEBUG_FUNC
msg(" Function %s marked as unsafe due to stack pointer copy \n ", this->GetFuncName());
msg("%s %x \n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
}
if (Instructions->MDIsPushInstr()) {
// not exactly sure how to handle this instruction
// for the moment if its a push on a esp or usefp & ebp
// mark as unsafe
if (Instructions->GetCmd().Operands[0].is_reg(R_sp) ||
(this->UseFP && Instructions->GetCmd().Operands[0].is_reg(R_bp))) {
HasStackPointerPush = true;
#if SMP_DEBUG_FUNC
msg(" Function %s marked as unsafe due to push on ebp or esp outside of function header \n", this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
}
continue;
}
if (Instructions->MDIsPopInstr()) {
// ignore pops for the moment
continue;
}
set<DefOrUse, LessDefUse>::iterator setIterator;
for (setIterator = Instructions->GetFirstDef(); setIterator != Instructions->GetLastDef(); ++setIterator) {
op_t Operand = setIterator->GetOp();
int BaseReg; int IndexReg;
ushort ScaleFactor;
ea_t offset;
if (Operand.type == o_mem) {
// now o_mem can have sib byte as well, as
// reported by IDA. Check if the base reg is R_none
// and index reg is R_none. If they are, then this is
// a direct global write and can be marked safe.
MDExtractAddressFields(Operand, BaseReg, IndexReg, ScaleFactor, offset);
if ((BaseReg == R_none) && (IndexReg == R_none)) {
// go onto next def
continue;
}
else {
HasIndirectGlobalWrite = true;
}
}
else if (Operand.type == o_displ) {
MDExtractAddressFields(Operand, BaseReg, IndexReg, ScaleFactor, offset);
bool FramePointerRelative = (this->UseFP && (BaseReg == R_bp));
bool StackPointerRelative = (BaseReg == R_sp);
if (StackPointerRelative || FramePointerRelative) {
if (IndexReg == R_none) {
bool tempWritesAboveLocalFrame = this->WritesAboveLocalFrame(Operand);
WritesAboveLocalFrame |= tempWritesAboveLocalFrame;
#if SMP_DEBUG_FUNC
if (tempWritesAboveLocalFrame) {
msg(" Function %s marked as unsafe due to direct write above loc "
"variables offset=%x loc=%x\n ", this->GetFuncName(),
offset, this->LocalVarsSize);
msg("Write above local frame in %s : offset: %d ",
this->GetFuncName(), offset);
msg("LocalVarsSize: %d OutgoingArgsSize: %d frsize: %d frregs: %d",
this->LocalVarsSize, this->OutgoingArgsSize,
this->FuncInfo.frsize, this->FuncInfo.frregs);
Instructions->Dump();
}
#endif
}
else {
bool tempWritesAboveLocalFrameIndirect = this->IndexedWritesAboveLocalFrame(Operand);
/* seperate indirect writes to this frame from indirect writes to another frame */
if (tempWritesAboveLocalFrameIndirect) {
WritesAboveLocalFrameIndirect = true;
#if SMP_DEBUG_FUNC
msg(" Function %s marked as unsafe due to indexed stack write above "
"loc variable offset\n", this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
}
else {
HasIndexedStackWrite = true;
#if SMP_DEBUG_FUNC
msg(" Function %s marked as unsafe due to indexed stack write\n",
this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
}
}
}
else {
/* check whether there is profiler information for this indirect reference */
HasIndirectWrite = true;
}
}
else if (Operand.type == o_phrase) {
// so phrase is of the form [BASE_REG + IND ]
// if the index register is missing just make sure that
// the displacement is below stack frame top MDExtractAddressFields(Operand, BaseReg, IndexReg, ScaleFactor, offset);
// check the base reg
// if index reg is used mark as unsafe
if ((BaseReg == R_sp || (this->UseFP && BaseReg == R_bp))) {
if (IndexReg == R_none) {
/* addressing mode is *esp or *ebp */
continue;
}
else {
HasIndexedStackWrite = true;
#if SMP_DEBUG_FUNC
msg(" Function %s marked as unsafe due to indexed stack write\n", this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
}
}
else {
/* check whether there is profiler information for this indirect reference */
HasIndirectWrite = true;
}
}
// else not memory, and we don't care.
} // end for all DEFs in current instruction
} // end for all instructions
// For mmStrata bounds checking of the stack frame, we don't care
// about indirect writes unless they are to the stack.
bool Unsafe = (HasStackPointerCopy || HasStackPointerPush
|| HasIndexedStackWrite || this->SharedChunks
|| this->UnresolvedIndirectJumps || this->UnresolvedIndirectCalls);
this->SafeFunc = (!Unsafe);
bool SpecUnsafe = (HasStackPointerCopy || HasStackPointerPush
|| HasIndexedStackWrite || this->SharedChunks
|| this->UnresolvedIndirectJumps);
this->SpecSafeFunc = (!SpecUnsafe);
this->WritesAboveRA = WritesAboveLocalFrameIndirect;
this->SafeCallee = (!Unsafe) && (!WritesAboveLocalFrameIndirect) && this->AnalyzedSP;
this->SpecSafeCallee = (!SpecUnsafe) && (!WritesAboveLocalFrameIndirect) && this->AnalyzedSP;
this->NeedsStackReferent = Unsafe;
this->SpecNeedsStackReferent = SpecUnsafe;
this->HasIndirectWrites = (HasIndexedStackWrite || HasIndirectWrite
|| WritesAboveLocalFrameIndirect || HasIndirectGlobalWrite);
if (Unsafe || WritesAboveLocalFrame || WritesAboveLocalFrameIndirect || HasIndirectGlobalWrite
|| HasIndirectWrite || (!this->AnalyzedSP)) {
this->ReturnAddrStatus = FUNC_UNSAFE;
#if SMP_DEBUG_FUNC
msg("UNSAFE function %s ", this->GetFuncName());
msg("StackPtrCopy: %d StackPtrPush: %d IndirectGlobal: %d ",
HasStackPointerCopy, HasStackPointerPush, HasIndirectGlobalWrite);
msg("WritesAboveFrame: %d IndirectStack: %d IndirectWrite: %d ",
WritesAboveLocalFrame, HasIndexedStackWrite, HasIndirectWrite);
msg("AnalyzedSP: %d UnresolvedCalls: %d UnresolvedJumps: %d SharedChunks: %d IsLeaf: %d\n",
this->AnalyzedSP, this->UnresolvedIndirectCalls, this->UnresolvedIndirectJumps,
this->SharedChunks, this->IsLeaf());
#endif
}
else if (HasCallTargets) {
this->ReturnAddrStatus = FUNC_UNKNOWN;
}
#if SMP_DEBUG_FUNC
if (ReturnAddrStatus == FUNC_SAFE)
msg("Function %s is SAFE\n", GetFuncName());
else if (ReturnAddrStatus == FUNC_SAFE)
msg("Function %s is UNSAFE\n", GetFuncName());
else if (ReturnAddrStatus == FUNC_SAFE) msg("Function %s is UNKNOWN\n", GetFuncName());
if (!Unsafe)
msg("Function %s is mmSAFE\n", GetFuncName());
else
msg("Function %s is mmUNSAFE\n", GetFuncName());
if (!SpecUnsafe)
msg("Function %s is Speculatively mmSAFE\n", GetFuncName());
else
msg("Function %s is Speculatively mmUNSAFE\n", GetFuncName());
#endif
return;
} // end of SMPFunction::MarkFunctionSafe()