//
// 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_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
// 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
// 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;
// *****************************************************************
// Class SMPFunction
// *****************************************************************
// Constructor
SMPFunction::SMPFunction(func_t *Info) {
this->FuncInfo = *Info;
this->IndirectCalls = false;
this->IndirectJumps = false;
this->SharedChunks = false;
this->CallsAlloca = false;
this->BuiltRTLs = false;
this->OutgoingArgsSize = 0;
this->BlockCount = 0;
this->LocalVarTable.clear();
this->StackFrameMap.clear();
this->DirectCallTargets.clear();
this->ReturnAddrStatus = FUNC_UNKNOWN;
this->Blocks.clear();
this->Instrs.clear();
this->GlobalNames.clear();
return;
}
// 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()
// 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->FuncInfo));
// 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 ...
#if 0
// Now we need to do the corresponding operations from the
// end of the function to find the DeallocInstr in the
// function epilogue. Because there is no addition to the
// stack pointer to deallocate the local vars region, the
// function epilogue will consist of (optional) pops of
// callee-saved regs, followed by the return instruction.
// Working backwards, we should find a return and then
// stop when we do not find any more pops.
if (0 >= LocalVarsSize) {
this->LocalVarsDeallocInstr = NULL;
}
else {
SaveAddr = this->FuncInfo.endEA - 1;
bool FoundRet = false;
do {
ea_t addr = get_item_head(SaveAddr);
flags_t InstrFlags = getFlags(addr);
if (isCode(addr) && isHead(addr)) {
ua_ana0(addr);
if (!FoundRet) { // Just starting out.
if (MDIsReturnInstr(cmd)) {
FoundRet = true;
SaveAddr = addr - 1;
}
else {
msg("ERROR: Last instruction not a return.\n");
}
}
else { // Should be 0 or more POPs before the return.
if (MDIsPopInstr(cmd)) {
SaveAddr = addr - 1;
}
else if (FrameAllocInstr(cmd, this->LocalVarsSize)) {
this->LocalVarsDeallocInstr = addr;
}
else {
msg("ERROR: Frame deallocation not prior to POPs.\n");
this->LocalVarsDeallocInstr = SaveAddr + 1;
}
} // end if (!FoundRet) ... else ...
}
else {
--SaveAddr;
} // end if (isCode(addr) && isHead(addr))
} while (NULL == this->LocalVarsDeallocInstr);
} // end if (0 >= this->LocalVarsSize)
#endif // 0
this->CallsAlloca = this->FindAlloca();
#if SMP_COMPUTE_STACK_GRANULARITY
// Now, find the boundaries between local variables.
this->BuildLocalVarTable();
#endif
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 ahve 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 %s\n", OldFrameTotal);
if (OldFrameTotal == SavedRegsSize) {
this->CalleeSavedRegsSize = 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) {
bool DebugFlag = (0 == strcmp("_dl_runtime_resolve", this->GetFuncName()));
sval_t TargetSize = - ((sval_t) OriginalLocSize); // negate; stack grows down
#if SMP_DEBUG_FRAMEFIXUP
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->FuncInfo), 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->FuncInfo), 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;
return true;
} // end of SMPFunction::MDFixUseFP()
// 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[MAXSTR] = {'\0'};
if (NULL == Member) {
msg("NULL stack frame member pointer in %s\n", this->GetFuncName());
break;
}
get_member_name(Member->id, MemberName, MAXSTR - 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 %d\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 = -1; // compute later
qstrncpy(TempLocal.VarName, MemberName, MAXSTR - 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
for (size_t VarIndex = 0; VarIndex < (this->LocalVarTable.size() - 1); ++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
if (this->LocalVarTable.size() > 0) {
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[this->LocalVarTable.size() - 1].size = this->FuncInfo.frsize
- SavedRegsSpace - this->LocalVarTable[this->LocalVarTable.size() - 1].offset;
}
this->LocalVarOffsetLimit = this->LocalVarTable.back().offset
+ (adiff_t) this->LocalVarTable.back().size;
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("simtest", this->GetFuncName()));
#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->FuncInfo), 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->FuncInfo), 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->FuncInfo), 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: %d 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 (this->OutgoingArgsSize < (TempEntry.VarPtr->offset + TempEntry.VarPtr->size)) {
msg("OutGoingArgsSize = %d", this->OutgoingArgsSize);
this->OutgoingArgsSize = TempEntry.VarPtr->offset + TempEntry.VarPtr->size;
msg(" adjusted to %d\n", this->OutgoingArgsSize);
}
}
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) {
ushort BaseReg;
ushort IndexReg;
assert((o_displ == TempOp.type) || (o_phrase == TempOp.type));
if (TempOp.type == o_displ) {
offset = TempOp.addr;
}
else { // o_phrase
offset = 0; // implicit zero, as in [esp] ==> [esp+0]
}
if (TempOp.hasSIB) {
BaseReg = sib_base(TempOp);
IndexReg = sib_index(TempOp);
}
else { // no SIB
BaseReg = TempOp.reg;
IndexReg = R_none;
}
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()
// 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 %d 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 %d esp + %d CHILDOF %d 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 %d esp + %d CHILDOF %d OFFSET %d 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) {
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));
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->FuncInfo));
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->FuncInfo), 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);
}
}
if (CurrInst.GetDataFlowType() == INDIR_CALL)
this->IndirectCalls = true;
else if (CurrInst.GetDataFlowType() == INDIR_JUMP)
this->IndirectJumps = true;
else if (CurrInst.GetDataFlowType() == CALL) {
set<DefOrUse, LessDefUse>::iterator CurrUse;
for (CurrUse = CurrInst.GetFirstUse(); CurrUse != CurrInst.GetLastUse(); ++CurrUse) {
optype_t OpType = CurrUse->GetOp().type;
if ((OpType == o_near) || (OpType == o_far)) {
ea_t CallTarget = CurrUse->GetOp().addr;
this->DirectCallTargets.push_back(CallTarget);
}
}
}
// 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()) {
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
// Set up basic block links and map of instructions to blocks.
if (!(this->HasSharedChunks())) {
bool DumpFlag = false;
#if SMP_DEBUG_DATAFLOW
DumpFlag |= (0 == strcmp("__do_global_dtors_aux", this->GetFuncName()));
DumpFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
DumpFlag |= (0 == strcmp("weightadj", this->GetFuncName()));
#endif
this->SetLinks();
this->RPONumberBlocks();
#if SMP_DEBUG_CONTROLFLOW
msg("SMPFunction::Analyze: set stack frame info.\n");
#endif
// Figure out the stack frame and related info.
this->SetStackFrameInfo();
#if SMP_COMPUTE_LVA_SSA
if (!(this->HasIndirectJumps())) {
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();
} // end for all instructions
this->LiveVariableAnalysis();
this->ComputeSSA();
if (DumpFlag)
this->Dump();
} // end if not indirect jumps
#endif // SMP_COMPUTE_LVA_SSA
} // 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();
}
this->MarkFunctionSafe();
} // end of SMPFunction::Analyze()
// Compute SSA form data structures across the function.
void SMPFunction::ComputeSSA(void) {
bool DumpFlag = false;
bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
DumpFlag |= (0 == strcmp("main", this->GetFuncName()));
DumpFlag |= (0 == strcmp("call_gmon_start", this->GetFuncName()));
DumpFlag |= (0 == strcmp("_init_proc", this->GetFuncName()));
#endif
#if 0
DebugFlag |= (0 == strcmp("call_gmon_start", this->GetFuncName()));
#endif
#if 0
DumpFlag |= (0 == strcmp("_nl_find_msg", this->GetFuncName()));
if (DumpFlag)
this->Dump();
#endif
this->ComputeIDoms();
this->ComputeDomFrontiers();
this->ComputeGlobalNames();
this->ComputeBlocksDefinedIn();
this->InsertPhiFunctions();
this->BuildDominatorTree();
this->SSARenumber();
list<SMPBasicBlock>::iterator CurrBlock;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
CurrBlock->SetLocalNames();
CurrBlock->SSALocalRenumber();
if (DebugFlag) CurrBlock->Dump();
#if SMP_FULL_LIVENESS_ANALYSIS
CurrBlock->CreateGlobalChains();
#endif
#if 1
CurrBlock->MarkDeadRegs();
#endif
}
#if SMP_DEBUG_DATAFLOW
if (DumpFlag)
this->Dump();
#endif
return;
} // end of SMPFunction::ComputeSSA()
// 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
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
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()));
// Last instruction in block; set successors
bool CallFlag = (CALL == CurrInst->GetDataFlowType());
xrefblk_t CurrXrefs;
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 && (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);
}
}
} // end for all xrefs
} // 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 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.
if (!(this->HasIndirectJumps())) {
bool changed;
do {
changed = false;
CurrBlock = this->Blocks.begin();
++CurrBlock; // don't delete the top block, no matter what.
while (CurrBlock != this->Blocks.end()) {
if (CurrBlock->GetFirstPred() == CurrBlock->GetLastPred()) {
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) {
bool DebugFlag = false;
#if SMP_DEBUG_DATAFLOW
DebugFlag = (0 == strcmp("__ieee754_pow", 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.
if (this->HasIndirectJumps()) {
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
if (SMP_BLOCKNUM_UNINIT == CurrBlock->GetNumber()) {
msg("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
msg("LiveVariableAnalysis for %s\n", this->GetFuncName());
bool DebugFlag = (0 == strcmp("__ieee754_pow", 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 UpExposedSet
// of the first block. These are the LiveIn names for the function that
// would otherwise look like USEs of uninitialized variables later.
set<op_t, LessOp>::iterator UpExposedIter;
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);
}
#endif
#if SMP_DEBUG_DATAFLOW
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("__ieee754_pow", 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());
}
}
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()) {
// 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 could 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("__ieee754_pow", 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
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
msg(" already in GlobalNames.\n");
#endif
}
else {
++index;
#if SMP_DEBUG_DATAFLOW
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
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("__ieee754_pow", 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
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
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
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
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 != 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
DumpFlag |= (0 == strcmp("main", this->GetFuncName()));
DumpFlag |= (0 == strcmp("dohanoi", this->GetFuncName()));
DumpFlag |= (0 == strcmp("image_to_texture", 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);
#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++.
CurrPhi->SetSSADef(NewSSANum);
#else
SMPPhiFunction TempPhi = (*CurrPhi);
TempPhi.SetSSADef(NewSSANum);
TempPhiList.push_back(TempPhi);
#endif
}
// 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;
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(void) {
// 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.
//
// The type inference system will mark DEFs and USEs in each instruction's DEF and USE
// sets with an inferred type. This inference 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 immportant 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;
bool DebugFlag = (0 == strcmp("weightadj", this->GetFuncName()));
list<SMPInstr>::iterator CurrInst;
set<DefOrUse, LessDefUse>::iterator CurrDef;
set<DefOrUse, LessDefUse>::iterator NextDef;
list<SMPBasicBlock>::iterator CurrBlock;
#if 1
DebugFlag = false;
if (DebugFlag) {
this->Dump();
}
// One time only: Set the types of immediate values, flags register, stack and frame
// pointers, and floating point registers.
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);
}
#endif
// 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 {
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);
}
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;
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;
if (UNINIT != CurrDef->GetType()) {
++(this->TypedDefs);
}
else {
++(this->UntypedDefs);
op_t DefOp = CurrDef->GetOp();
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 {
#if 1
// global name
int SSANum = CurrDef->GetSSANum();
NewChange = this->InferGlobalDefType(DefOp, SSANum);
if (NewChange) {
--(this->UntypedDefs);
++(this->TypedDefs);
}
changed = (changed || NewChange);
#endif
}
}
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();
}
}
} while (changed);
return;
} // end of SMPFunction::InferTypes()
// 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 true, else return false.
bool SMPFunction::InferGlobalDefType(op_t DefOp, int SSANum) {
bool changed = false;
bool DebugFlag = (0 == strcmp("hash_string", this->GetFuncName()));
#if 1
if (DebugFlag) {
msg("InferGlobalDefType for SSANum %d of ", SSANum);
PrintOperand(DefOp);
msg("\n");
}
list<SMPInstr>::iterator InstIter;
list<SMPInstr>::iterator DefInstIter;
bool DefFound = false;
set<DefOrUse, LessDefUse>::iterator CurrDef;
assert(0 <= SSANum);
set<DefOrUse, LessDefUse>::iterator CurrUse;
// Go through all instructions in the block and find the DEF and 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;
for (InstIter = this->Instrs.begin(); InstIter != this->Instrs.end(); ++InstIter) {
if (!DefFound) {
CurrDef = InstIter->FindDef(DefOp);
if (CurrDef != InstIter->GetLastDef()) { // found DEF of DefOp
if (CurrDef->GetSSANum() == SSANum) { // matched SSA number
DefFound = true;
DefInstIter = InstIter;
assert(UNINIT == CurrDef->GetType());
}
}
}
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();
if (UNINIT == UseType)
return false;
}
else {
if (CurrUse->GetType() != UseType)
return false; // no consistent type
}
}
}
} // end for all instructions
if (DefFound && FirstUseSeen) {
// We have a consistent type, else we would have returned false above.
assert(UNINIT != UseType);
if (DebugFlag) msg("Inferring global DEF of type %d\n", UseType);
CurrDef = DefInstIter->SetDefType(DefOp, UseType);
changed = true;
}
else if (!DefFound) {
// It could be that the DEF is provided by a Phi function.
list<SMPBasicBlock>::iterator CurrBlock;
set<SMPPhiFunction, LessPhi>::iterator DefPhi;
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
DefPhi = CurrBlock->FindPhi(DefOp);
if (CurrBlock->GetLastPhi() != DefPhi) { // block has Phi for DefOp
// See if the SSA subscripts match
if (DefPhi->GetDefSSANum() == SSANum) {
// Found a match. Set this Phi DEF type to UseType.
if (DebugFlag) msg("Inferring Phi DEF of type %d\n", UseType);
DefPhi = CurrBlock->SetPhiDefType(DefOp, UseType);
changed = true;
DefFound = true;
break;
}
}
}
if (!DefFound) { // not an instruction DEF or a Phi DEF
msg("ERROR: Could not find global DEF with SSANum %d for: ", SSANum);
PrintOperand(DefOp);
msg("\n");
}
}
else { // DefFound but not FirstUseSeen
// If the DefOp is is the LiveOut set, then the USEs could be in successor
// blocks, including in their Phi functions. If the block returns, then
// the DEFs could be used in the caller.
if (!(DefInstIter->GetBlock()->IsLiveOut(DefOp) || DefInstIter->GetBlock()->HasReturn())) {
// 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) && (CALL != DefInstIter->GetDataFlowType())
&& (INDIR_CALL != DefInstIter->GetDataFlowType())) {
msg("WARNING: global DEF with no USEs at %x for SSANum %d DefOp: ",
DefInstIter->GetAddr(), SSANum);
PrintOperand(DefOp);
msg("\n");
}
}
}
#endif
return changed;
} // end of SMPFunction::InferGlobalDefType()
// 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 ");
}
#ifdef SMP_DEBUG_FUNC
if (this->IsLeaf())
qfprintf(AnnotFile, "FUNC_LEAF ");
// store the return address
qfprintf(AnnotFile,"%10x ", this->FuncInfo.endEA - 1);
#endif
qfprintf(AnnotFile, "\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();
if (this->LocalVarsAllocInstr == addr) {
AllocSeen = true;
this->EmitStackFrameAnnotations(AnnotFile, CurrInst);
}
// 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, AnnotFile);
}
else {
CurrInst->EmitAnnotations(this->UseFP, AllocSeen, AnnotFile);
}
if (CurrInst->MDIsReturnInstr() && this->GetReturnAddressStatus() == FUNC_SAFE )
CurrInst->EmitSafeReturn(AnnotFile);
} // end for all instructions
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());
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();
}
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 name %s and isLeaf=%d ", this->GetFuncName(), this->IsLeaf());
#endif
ReturnAddrStatus = FUNC_SAFE;
if (!AnalyzedSP || this->IndirectCalls) {
#if SMP_DEBUG_FUNC
if (!AnalyzedSP)
msg(" Function marked as unsafe %s coz AnalyzedSP = false\n", this->GetFuncName());
else
msg(" Function marked as unsafe %s coz function has indirect calls\n", this->GetFuncName());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
if (!this->DirectCallTargets.empty()) {
#if SMP_DEBUG_FUNC
msg(" Function marked as unknown %s \n", this->GetFuncName());
#endif
ReturnAddrStatus = FUNC_UNKNOWN;
}
if (this->IndirectJumps) {
#if SMP_DEBUG_FUNC
msg(" Function marked as unsafe due to indirect jumps %s\n", this->GetFuncName());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return ;
}
if (this->HasSharedChunks()) {
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
list<SMPInstr>::iterator Instructions;
// while processing the stack pointer write the prolog containing 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)) {
#if SMP_DEBUG_FUNC
msg(" Function marked as unsafe %s due to stack pointer copy \n ", this->GetFuncName());
msg("%s %x \n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
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))) {
#if SMP_DEBUG_FUNC
msg(" Function marked as unsafe %s due to push on ebp or esp outside of function header \n", this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
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();
if (Operand.type == o_mem) {
// now o_mem can have sib byte as well, as
// reported by IDA. check if the base reg is bp
// and index reg is sp. If it is, then this is
// probably a global write and can be marked
// safe
if (Operand.hasSIB) {
int BaseReg = sib_base(Operand);
short IndexReg = sib_index(Operand);
if ((BaseReg == R_none || BaseReg == R_bp) &&
(IndexReg == R_none || IndexReg == R_sp)) {
// go onto next def
continue;
}
}
else {
// o_mem should never have a base register (field should be zero)
if ((Operand.reg == 0) || (Operand.reg == R_bp)) // ignore
continue;
}
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
if (Operand.type == o_displ) {
if (Operand.hasSIB) {
int BaseReg = sib_base(Operand);
short IndexReg = sib_index(Operand);
if (((BaseReg==R_sp || (this->UseFP && BaseReg == R_bp)))) {
if (IndexReg == R_sp || IndexReg == R_none) {
ea_t offset = Operand.addr;
if (offset > this->LocalVarsSize ) {
#if SMP_DEBUG_FUNC
msg(" Function marked as unsafe %s due to write above loc variables offset=%x loc=%x\n ", this->GetFuncName(), offset, this->LocalVarsSize);
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
else {
#if SMP_DEBUG_FUNC
msg(" Function marked as unsafe %s due to index write above loc variables \n", this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
else {
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
else {
// no index
ushort BaseReg = Operand.reg;
if (BaseReg == R_sp || (UseFP && BaseReg == R_bp)) {
ea_t offset = Operand.addr;
if (offset > this->LocalVarsSize ) {
#if SMP_DEBUG_FUNC
msg(" Function marked as unsafe %s due to write above loc variables in no sib offset=%x loc=%x \n", this->GetFuncName(), offset, this->LocalVarsSize);
msg("%s %x \n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
else {
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
}
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
if (Operand.hasSIB) {
// check the base reg
int BaseReg = sib_base(Operand);
short IndexReg = sib_index(Operand);
// if index reg is used mark as unsafe
if ((BaseReg == R_sp || (this->UseFP && BaseReg == R_bp))
&& (IndexReg != R_sp) && (IndexReg != R_none)) {
// index=sp implies there is no index register
#if SMP_DEBUG_FUNC
msg(" Does function with phrase have displ %s %x ", this->GetFuncName(), Operand.addr);
#endif
continue;
}
else {
ReturnAddrStatus = FUNC_UNSAFE;
return ;
}
}
else {
ushort BaseReg = Operand.reg;
if (BaseReg == R_sp || (this->UseFP && BaseReg == R_bp))
continue;
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
}
}
} // end of SMPFunction::MarkFunctionSafe()