/*
* SMPBasicBlock.cpp - Class file for basic block analysis.
*
* Copyright (c) 2000, 2001, 2010 - University of Virginia
*
* This file is part of the Memory Error Detection System (MEDS) infrastructure.
* This file may be used and modified for non-commercial purposes as long as
* all copyright, permission, and nonwarranty notices are preserved.
* Redistribution is prohibited without prior written consent from the University
* of Virginia.
*
* Please contact the authors for restrictions applying to commercial use.
*
* THIS SOURCE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
* MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*
* Author: University of Virginia
* e-mail: jwd@virginia.com
* URL : http://www.cs.virginia.edu/
*
* Additional copyrights 2010, 2011 by Zephyr Software LLC
* e-mail: {clc,jwd}@zephyr-software.com
* URL : http://www.zephyr-software.com/
*
*/
//
// SMPBasicBlock.cpp
//
// This module performs the fundamental basic block level analyses needed for the
// SMP project (Software Memory Protection).
//
#include <list>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
#include <pro.h>
#include <assert.h>
#include <ida.hpp>
#include <idp.hpp>
#include <auto.hpp>
#include <bytes.hpp>
#include <funcs.hpp>
#include <name.hpp>
#include <intel.hpp>
#include "SMPDBInterface.h"
#include "SMPStaticAnalyzer.h"
#include "SMPDataFlowAnalysis.h"
#include "SMPBasicBlock.h"
#include "SMPInstr.h"
#include "SMPFunction.h"
#define SMP_DEBUG_DATAFLOW 0 // verbose output for setting up SSA/LVA data structures
#define SMP_DEBUG_OPTIMIZATIONS 0 // verbose output for type propagation
#define SMP_VERBOSE_POINTER_REFINEMENT 0 // refining POINTER to HEAPPTR, STACKPTR, etc.
#define SMP_VERBOSE_ALIAS_DETECTION 0 // log message every time alias in DU chain is seen
#define STARS_DETECT_OPTIMIZED_RANGE_CHECK 1 // Detect misleading signedness case
#define STARS_MINIMIZE_UNSIGNED_BRANCH_PROPAGATION 1 // stop propagation at possible mixed-mode arithmetic
#define STARS_AGGRESSIVE_BENIGN_POINTER_ARITHMETIC 1 // subtract then add to POINTER can underflow then overflow benignly
// Basic block number 0 is the top of the CFG lattice.
#define SMP_TOP_BLOCK 0
// *****************************************************************
// Class SMPBasicBlock
// *****************************************************************
// Constructor
SMPBasicBlock::SMPBasicBlock(SMPFunction *Func, list<SMPInstr *>::iterator First, list<SMPInstr *>::iterator Last) {
this->FirstAddr = (*First)->GetAddr();
this->BlockNum = SMP_BLOCKNUM_UNINIT;
this->LoopHeaderNumber = SMP_BLOCKNUM_UNINIT;
this->MyFunc = Func;
this->SetOutgoingStackDelta(0);
#if 0
this->IncomingStackPtrDelta = 0;
#endif
#if 1
this->SetProcessed(false);
this->SetIndirectJump(false);
this->SetReturns(false);
this->ResetShared();
this->SetLiveInStale(true);
this->SetUnreachableBlock(false);
this->SetFlagsDeadBeforeFirstKill(false);
this->SetMaybeAliased(false);
#else
this->booleans1 = 0;
this->SetLiveInStale(true);
#endif
this->booleans2 = 0;
this->InstVec.clear();
this->AddrInstMap.clear();
this->Predecessors.clear();
this->Successors.clear();
this->KillSet.clear();
this->UpExposedSet.clear();
this->LiveOutSet.clear();
this->LiveInSet.clear();
this->DomFrontier.clear();
this->PhiFunctions.clear();
this->LocalNames.clear();
ea_t InstAddr;
list<SMPInstr *>::iterator InstIter = First;
SMPInstr *CurrInst;
size_t VecIndex = this->InstVec.size() - 1;
while (InstIter != Last) {
CurrInst = (*InstIter);
this->InstVec.push_back(CurrInst);
VecIndex = this->InstVec.size() - 1;
InstAddr = CurrInst->GetAddr();
pair<ea_t, size_t> MapItem(InstAddr, VecIndex);
this->AddrInstMap.insert(MapItem);
++InstIter;
}
// Now process the last instruction.
CurrInst = (*Last);
this->InstVec.push_back(CurrInst); // Add last instruction
InstAddr = CurrInst->GetAddr();
VecIndex = this->InstVec.size() - 1;
pair<ea_t, size_t> MapItem2(InstAddr, VecIndex);
this->AddrInstMap.insert(MapItem2);
CurrInst->SetTerminatesBlock();
// Mark first true (non-marker) instruction. Marker is a floating point
// no-op at an odd address, 1 byte before actual first address of block.
InstIter = First;
CurrInst = (*InstIter);
if ((CurrInst->IsFloatNop()) && (0 != (0x1 & CurrInst->GetAddr()))) {
// Floating point no-op at odd address; this is SSA marker instruction.
++InstIter; // skip to first real instruction
CurrInst = (*InstIter);
}
CurrInst->SetFirstInBlock();
}
// Get address of first instruction in the block.
ea_t SMPBasicBlock::GetFirstAddr(void) const {
return this->FirstAddr;
}
// Six methods to get values from the maps of global reg/SSA to FG info.
// For global names, see corresponding methods in SMPFunction.
unsigned short SMPBasicBlock::GetDefSignMiscInfo(int DefHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
if (MapIter != this->LocalDefFGInfoBySSA.end())
return MapIter->second.SignMiscInfo;
else
return 0;
} // end of SMPBasicBlock::GetDefSignMiscInfo()
unsigned short SMPBasicBlock::GetUseSignMiscInfo(int UseHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
if (MapIter != this->LocalUseFGInfoBySSA.end())
return MapIter->second.SignMiscInfo;
else
return 0;
} // end of SMPBasicBlock::GetUseSignMiscInfo()
unsigned short SMPBasicBlock::GetDefWidthTypeInfo(int DefHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
if (MapIter != this->LocalDefFGInfoBySSA.end())
return MapIter->second.SizeInfo;
else
return 0;
} // end of SMPBasicBlock::GetDefWidthTypeInfo()
unsigned short SMPBasicBlock::GetUseWidthTypeInfo(int UseHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
if (MapIter != this->LocalUseFGInfoBySSA.end())
return MapIter->second.SizeInfo;
else
return 0;
} // end of SMPBasicBlock::GetUseWidthTypeInfo()
struct FineGrainedInfo SMPBasicBlock::GetDefFGInfo(int DefHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
if (MapIter != this->LocalDefFGInfoBySSA.end())
return MapIter->second;
else {
struct FineGrainedInfo EmptyFG;
EmptyFG.SignMiscInfo = 0;
EmptyFG.SizeInfo = 0;
return EmptyFG;
}
} // end of SMPBasicBlock::GetDefFGInfo()
struct FineGrainedInfo SMPBasicBlock::GetUseFGInfo(int UseHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
if (MapIter != this->LocalUseFGInfoBySSA.end())
return MapIter->second;
else {
struct FineGrainedInfo EmptyFG;
EmptyFG.SignMiscInfo = 0;
EmptyFG.SizeInfo = 0;
return EmptyFG;
}
} // end of SMPBasicBlock::GetUseFGInfo()
bool SMPBasicBlock::IsLocalName(op_t CurrOp) const {
return (!this->LocalNames.empty()
&& (this->LocalNames.end() != this->LocalNames.find(CurrOp)));
}
set<op_t, LessOp>::iterator SMPBasicBlock::FindLocalName(op_t FindOp) {
return this->LocalNames.find(FindOp);
}
// Equality operator for SMPBasicBlock. Key field is address of first instruction.
int SMPBasicBlock::operator==(const SMPBasicBlock &rhs) const {
if (rhs.GetFirstAddr() != this->FirstAddr)
return 0;
else
return 1;
}
// Link to predecessor block.
void SMPBasicBlock::LinkToPred(SMPBasicBlock *Predecessor) {
this->Predecessors.push_back(Predecessor);
return;
}
// Link to successor block.
void SMPBasicBlock::LinkToSucc(SMPBasicBlock *Successor) {
this->Successors.push_back(Successor);
return;
}
// See if all predecessors have set their ordering number.
bool SMPBasicBlock::AllPredecessorsNumbered(void) {
list<SMPBasicBlock *>::iterator CurrPred;
for (CurrPred = this->Predecessors.begin(); CurrPred != this->Predecessors.end(); ++CurrPred) {
// Don't count current block, in case we have a one-block loop with this block
// as its own predecessor.
if (**CurrPred == *this)
continue;
if ((*CurrPred)->GetNumber() == SMP_BLOCKNUM_UNINIT)
return false;
}
return true;
} // end of SMPBasicBlock::AllPredecessorsNumbered()
// Mark as processed, recurse into successors depth-first.
void SMPBasicBlock::DepthFirstMark(void) {
if (this->IsProcessed()) {
return;
}
this->SetProcessed(true);
list<SMPBasicBlock *>::iterator CurrSucc;
for (CurrSucc = this->Successors.begin(); CurrSucc != this->Successors.end(); ++CurrSucc) {
(*CurrSucc)->DepthFirstMark();
}
return;
} // end of SMPBasicBlock::DepthFirstMark()
// Are all instructions in the block no-ops?
bool SMPBasicBlock::AllNops(void) {
size_t NopCount = 0;
size_t GoodCount = 0; // non-nop instructions
vector<SMPInstr *>::iterator InstIter;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
if (CurrInst->IsNop()) {
++NopCount;
}
else {
++GoodCount;
break;
}
}
return ((0 == GoodCount) && (0 < NopCount));
} // end of SMPBasicBlock::AllNops()
// Analyze basic block and fill data members.
void SMPBasicBlock::Analyze() {
vector<SMPInstr *>::reverse_iterator RevInstIter = this->GetRevInstBegin();
SMPInstr *BackInst = (*RevInstIter);
if (BackInst->GetDataFlowType() == INDIR_JUMP) {
this->SetIndirectJump(true);
}
else if (BackInst->GetDataFlowType() == RETURN) {
this->SetReturns(true);
}
} // end of SMPBasicBlock::Analyze()
// DEBUG dump of block
void SMPBasicBlock::Dump(void) {
SMP_msg("Dump of basic block %d\n", this->BlockNum);
// Dump dataflow analysis sets and links before dumping instructions.
list<SMPBasicBlock *>::iterator CurrLink;
SMP_msg("Predecessors: ");
if (!this->Predecessors.empty()) {
for (CurrLink = this->Predecessors.begin(); CurrLink != this->Predecessors.end(); ++CurrLink) {
SMP_msg("%d ", (*CurrLink)->GetNumber());
}
}
SMP_msg("\n");
SMP_msg("Successors: ");
if (!this->Successors.empty()) {
for (CurrLink = this->Successors.begin(); CurrLink != this->Successors.end(); ++CurrLink) {
SMP_msg("%d ", (*CurrLink)->GetNumber());
}
}
SMP_msg("\n");
set<op_t, LessOp>::iterator SetItem;
SMP_msg("VarKill set: ");
if (!this->KillSet.empty()) {
SMP_msg("size: %zu ", this->KillSet.size());
for (SetItem = this->KillSet.begin(); SetItem != this->KillSet.end(); ++SetItem) {
PrintListOperand(*SetItem);
}
}
SMP_msg("\n\n");
SMP_msg("UpExposed set: ");
if (!this->UpExposedSet.empty()) {
for (SetItem = this->GetFirstUpExposed(); SetItem != this->GetLastUpExposed(); ++SetItem) {
PrintListOperand(*SetItem);
}
}
SMP_msg("\n\n");
SMP_msg("LiveIn set: ");
if (!this->LiveInSet.empty()) {
for (SetItem = this->LiveInSet.begin(); SetItem != this->LiveInSet.end(); ++SetItem) {
PrintListOperand(*SetItem);
}
}
SMP_msg("\n\n");
SMP_msg("LiveOut set: ");
if (!this->LiveOutSet.empty()) {
for (SetItem = this->LiveOutSet.begin(); SetItem != this->LiveOutSet.end(); ++SetItem) {
PrintListOperand(*SetItem);
}
}
SMP_msg("\n\n");
SMP_msg("Dominance frontier: ");
set<int>::iterator DomIter;
if (!this->DomFrontier.empty()) {
for (DomIter = this->DomFrontier.begin(); DomIter != this->DomFrontier.end(); ++DomIter) {
SMP_msg("%d ", *DomIter);
}
}
SMP_msg("\n\n");
set<SMPPhiFunction, LessPhi>::iterator PhiIter;
if (!this->PhiFunctions.empty()) {
for (PhiIter = this->PhiFunctions.begin(); PhiIter != this->PhiFunctions.end(); ++PhiIter) {
SMP_msg("Phi function for %d : ", PhiIter->GetIndex());
// Dump out all phi operands
PhiIter->Dump();
}
}
SMP_msg("\n");
#if STARS_BUILD_DEF_USE_CHAINS
SMP_msg("DEF-USE chains for block-local names: \n");
this->LocalDUChains.Dump();
SMP_msg("\n");
SMP_msg("DEF-USE chains for block-local use of global names: \n");
this->GlobalDUChains.Dump();
#endif
SMP_msg("\n");
if (this->HasIndirectJump())
SMP_msg("Has indirect jump. ");
if (this->HasReturn())
SMP_msg("Has return. ");
if (this->IsShared())
SMP_msg("Is shared tail chunk block. ");
SMP_msg("\n");
// Now, dump all the instructions.
vector<SMPInstr *>::iterator CurrInst;
for (CurrInst = this->GetFirstInst(); CurrInst != this->GetLastInst(); ++CurrInst) {
(*CurrInst)->Dump();
}
SMP_msg("\n");
return;
} // end of SMPBasicBlock::Dump()
// Search successors for fall-through block, if any
list<SMPBasicBlock *>::iterator SMPBasicBlock::GetFallThroughSucc(void) {
list<SMPBasicBlock *>::iterator FallThroughSuccIter = this->GetLastSucc();
list<SMPBasicBlock *>::iterator SuccIter;
vector<SMPInstr *>::reverse_iterator LastInstIter = this->GetRevInstBegin();
SMPInstr *LastInst = (*LastInstIter);
ea_t LastAddr = LastInst->GetAddr(), AddrDiff = 1000, FirstAddr;
SMPitype LastDataFlow = LastInst->GetDataFlowType();
if ((JUMP != LastDataFlow) && (RETURN != LastDataFlow) && (HALT != LastDataFlow)) {
// Block has fall-through.
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
FirstAddr = (*SuccIter)->GetFirstAddr();
if (FirstAddr > LastAddr) { // block comes after this block; candidate for fall-through
ea_t NewAddrDiff = FirstAddr - LastAddr;
if (NewAddrDiff < AddrDiff) { // better candidate than previous successors
AddrDiff = NewAddrDiff;
FallThroughSuccIter = SuccIter;
}
}
}
}
return FallThroughSuccIter;
} // end of SMPBasicBlock::GetFallThroughSucc()
// Return true if anything already in the KillSet would kill the operand value.
bool SMPBasicBlock::MDAlreadyKilled(op_t Opnd1) const {
// We have assembly language operands that can be complex, such as
// [ebx + esi*4 + 04h]. If ebx or esi have been killed, then this memory
// phrase should be considered killed. We could be even more conservative
// with base addresses, declaring an entire array killed whenever its base
// address appears in a definition, for example. We will do that if it proves
// to be necessary.
bool FoundInKillSet = (KillSet.end() != KillSet.find(Opnd1));
bool DirectAccess = false;
bool StackAccess = false;
bool UseFP = this->MyFunc->UsesFramePointer();
switch (Opnd1.type) {
// Some types are simple to test for equality.
case o_void:
case o_reg:
case o_mem:
case o_imm:
case o_far:
case o_near:
case o_trreg:
case o_dbreg:
case o_crreg:
case o_fpreg:
case o_mmxreg:
case o_xmmreg:
// Look in KillSet. These simple types should be found there with
// no complicated comparisons needed.
return FoundInKillSet;
case o_phrase:
case o_displ:
StackAccess = MDIsStackAccessOpnd(Opnd1, UseFP);
if (StackAccess) {
DirectAccess = !MDIsIndirectMemoryOpnd(Opnd1, UseFP);
}
// If found directly in KillSet, return true. Otherwise, see if any registers
// used in the memory addressing expression were killed.
if (FoundInKillSet)
return true;
else if (!(DirectAccess && StackAccess)) {
// Should we add Opnd1 to the KillSet every time we return true below? **!!**
op_t TempOp = InitOp;
TempOp.type = o_reg;
int BaseReg;
int IndexReg;
ushort ScaleFactor;
ea_t displacement;
MDExtractAddressFields(Opnd1, BaseReg, IndexReg, ScaleFactor, displacement);
if (R_none != BaseReg) {
TempOp.reg = (ushort) BaseReg;
if (this->KillSet.end() != this->KillSet.find(TempOp))
return true;
}
if (R_none != IndexReg) { // Cannot have ESP index reg in SIB
TempOp.reg = (ushort) IndexReg;
if (this->KillSet.end() != this->KillSet.find(TempOp))
return true;
}
} // end if (FoundInKillSet) ... else ...
break;
default:
SMP_msg("Unknown operand type %d in MDAlreadyKilled, block %d\n", Opnd1.type, this->BlockNum);
} // end of switch on Opnd1.type
return false;
} // end of SMPBasicBlock::MDAlreadyKilled()
// Initialize the KilledSet and UpExposedSet for live variable analysis.
void SMPBasicBlock::InitKilledExposed(bool UseFP) {
// Find all upwardly exposed operands and killed operands in this block.
vector<SMPInstr *>::iterator CurrIter;
set<DefOrUse, LessDefUse>::iterator CurrUse, CurrDef;
for (CurrIter = this->GetFirstInst(); CurrIter != this->GetLastInst(); ++CurrIter) {
SMPInstr *CurrInst = (*CurrIter);
// Dataflow equation for upward exposed variables: If a variable has not been
// killed yet in this block, starting from the top of the block, and it is used
// in the current instruction, then it is upwardly exposed.
for (CurrUse = CurrInst->GetFirstUse(); CurrUse != CurrInst->GetLastUse(); ++CurrUse) {
op_t UseOp = CurrUse->GetOp();
// Only add non-immediate operands that are not already killed in this block.
// o_near and o_far operands are code addresses in immediate form, e.g.
// call _printf might be call 0x8048040, with o_near = 0x8048040.
if ((!(this->MDAlreadyKilled(UseOp))) && (MDIsDataFlowOpnd(UseOp, UseFP))) {
this->AddUpExposed(UseOp);
}
}
// Dataflow equation for killed variables: If a variable is defined in any
// instruction in the block, it is killed by this block (i.e. prior definitions
// of that variable will not make it through the block).
for (CurrDef = CurrInst->GetFirstDef(); CurrDef != CurrInst->GetLastDef(); ++CurrDef) {
op_t DefOp = CurrDef->GetOp();
if (MDIsDataFlowOpnd(DefOp, UseFP)) {
this->KillSet.insert(DefOp);
}
}
} // end for all instrs in block
this->SetLiveInStale(true); // Would need to compute LiveInSet for first time
return;
} // end of SMPBasicBlock::InitKilledExposed()
// returns size in bytes
size_t SMPBasicBlock::GetBlockSize(void) {
vector<SMPInstr *>::reverse_iterator LastInstIter = this->GetRevInstBegin();
SMPInstr *LastInst = (*LastInstIter);
size_t BlockSize = LastInst->GetSize() + (size_t)(LastInst->GetAddr() - this->FirstAddr);
return BlockSize;
} // end of SMPBasicBlock::GetBlockSize()
// Return an iterator for the beginning of the LiveInSet. If the set is stale,
// recompute it first.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstLiveIn(void) {
if (this->IsLiveInStale()) {
// Dataflow equation: A variable is live-in to this block if it
// is upwardly exposed from this block, or if it passes through
// the block unchanged (i.e. it is not killed and is live out).
this->LiveInSet.clear();
set<op_t, LessOp>::iterator OutIter;
for (OutIter = this->GetFirstUpExposed(); OutIter != this->GetLastUpExposed(); ++OutIter) {
this->LiveInSet.insert(*OutIter);
}
for (OutIter = this->LiveOutSet.begin(); OutIter != this->LiveOutSet.end(); ++OutIter) {
if (KillSet.end() == this->KillSet.find(*OutIter)) // Found live out but not killed
this->LiveInSet.insert(*OutIter);
}
this->SetLiveInStale(false);
}
return this->LiveInSet.begin();
} // end of SMPBasicBlock::GetFirstLiveIn()
// Get termination iterator marker for the LiveIn set, for use by predecessors.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastLiveIn(void) {
// Does not matter if it is stale or not; end marker is the same
return this->LiveInSet.end();
}
// Get iterator for the start of the LiveOut set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstLiveOut(void) {
return this->LiveOutSet.begin();
}
// Get termination iterator marker for the LiveOut set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastLiveOut(void) {
return this->LiveOutSet.end();
}
// Get iterator for the start of the VarKill set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstVarKill(void) {
return this->KillSet.begin();
}
// Get termination iterator marker for the VarKill set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastVarKill(void) {
return this->KillSet.end();
}
// Get iterator for the start of the UpExposed set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstUpExposed(void) {
return this->UpExposedSet.begin();
}
// Get termination iterator marker for the UpExposed set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastUpExposed(void) {
return this->UpExposedSet.end();
}
// Get iterator for the start of the LocalNames set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetFirstLocalName(void) {
return this->LocalNames.begin();
}
// Get termination iterator marker for the LocalNames set.
set<op_t, LessOp>::iterator SMPBasicBlock::GetLastLocalName(void) {
return this->LocalNames.end();
}
// Get iterator for the start of the DomFrontier set.
set<int>::iterator SMPBasicBlock::GetFirstDomFrontier(void) {
return this->DomFrontier.begin();
}
// Get termination iterator marker for the DomFrontier set.
set<int>::iterator SMPBasicBlock::GetLastDomFrontier(void) {
return this->DomFrontier.end();
}
// Get iterator for first Phi function.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::GetFirstPhi(void) {
return this->PhiFunctions.begin();
}
// Get termination iterator marker for Phi functions set.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::GetLastPhi(void) {
return this->PhiFunctions.end();
}
// Find the Phi function that matches the given op_t.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::FindPhi(op_t FindOp) {
set<SMPPhiFunction, LessPhi>::iterator PhiIter;
set<op_t, LessOp>::value_compare OpComp = this->LiveOutSet.value_comp(); // LessOp()
for (PhiIter = this->GetFirstPhi(); PhiIter != this->GetLastPhi(); ++PhiIter) {
op_t PhiOp = PhiIter->GetPhiRef(0).GetOp();
if (OpComp(FindOp, PhiOp) || OpComp(PhiOp, FindOp)) {
// One is less than the other.
; // do nothing
}
else {
// They are equal.
return PhiIter;
}
}
// If we exit the loop, we did not find it.
return this->PhiFunctions.end();
} // end of SMPBasicBlock::FindPhi()
// Get a pointer to the instruction at address InstAddr.
// Will assert if it does not find the instruction.
SMPInstr *SMPBasicBlock::FindInstr(ea_t InstAddr) {
SMPInstr *CurrInst;
map<ea_t, size_t>::iterator MapEntry;
MapEntry = this->AddrInstMap.find(InstAddr);
if (MapEntry == this->AddrInstMap.end()) {
SMP_msg("FATAL ERROR: Failure on AddrInstMap. Size: %zu Addr: %lx \n",
this->AddrInstMap.size(), (unsigned long) InstAddr);
SMP_msg("First addr in block: %lx \n", (unsigned long) this->FirstAddr);
}
assert(MapEntry != this->AddrInstMap.end());
CurrInst = this->GetInstFromIndex(MapEntry->second);
return CurrInst;
} // end of SMPBasicBlock::FindInstr()
// Get an iterator to the instruction at address InstAddr.
// Will assert if it does not find the instruction.
vector<SMPInstr *>::iterator SMPBasicBlock::GetInstIterFromAddr(ea_t InstAddr) {
#if 1
size_t VecIndex = this->GetIndexFromInstAddr(InstAddr);
vector<SMPInstr *>::iterator InstIter(this->InstVec.begin() + VecIndex);
#else
vector<SMPInstr *>::iterator InstIter;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
if (InstAddr == (*InstIter)->GetAddr()) {
break;
}
}
if (InstIter == this->GetLastInst()) {
SMP_msg("FATAL ERROR: Failure to find Instr. Addr: %x \n", InstAddr);
SMP_msg("First addr in block: %x \n", this->FirstAddr);
}
#endif
assert(InstIter != this->GetLastInst());
return InstIter;
} // end of SMPBasicBlock::GetInstIterFromAddr()
// Get the InstVec index for the instruction at InstAddr. Assert if not found.
size_t SMPBasicBlock::GetIndexFromInstAddr(ea_t InstAddr) const {
SMPInstr *CurrInst;
ea_t CurrAddr;
size_t VecIndex;
size_t UpperLimit = this->InstVec.size();
if (UpperLimit > 10) { // big enough for binary search
size_t LowerLimit = 0;
do {
VecIndex = (LowerLimit + UpperLimit) / 2;
CurrInst = this->InstVec[VecIndex];
CurrAddr = CurrInst->GetAddr();
if (CurrAddr > InstAddr) { // search lower half
UpperLimit = VecIndex - 1;
}
else if (CurrAddr < InstAddr) { // search upper half
LowerLimit = VecIndex + 1;
}
} while ((CurrAddr != InstAddr) && (LowerLimit <= UpperLimit));
}
else { // small enough for linear search
for (VecIndex = 0; VecIndex < UpperLimit; ++VecIndex) {
CurrInst = this->InstVec[VecIndex];
CurrAddr = CurrInst->GetAddr();
if (CurrAddr == InstAddr) {
break;
}
}
}
assert((CurrAddr == InstAddr) && (VecIndex < this->InstVec.size()));
return VecIndex;
} // end of SMPBasicBlock::GetIndexFromInstAddr()
// The predecessor order is used in SSA phi functions. Get the ordinal number
// of a given block number in the predecessor list.
int SMPBasicBlock::GetPredPosition(int BlockNum) {
int counter = 0;
list<SMPBasicBlock *>::iterator PredIter;
for (PredIter = this->GetFirstPred(); PredIter != this->GetLastPred(); ++PredIter) {
if (BlockNum == (*PredIter)->GetNumber()) {
return counter;
}
++counter;
}
return -1;
}
// Set the DEF iterator from the DefAddr and DefOp. Assert if not found.
set<DefOrUse, LessDefUse>::iterator SMPBasicBlock::GetGlobalDefIterFromDefAddr(op_t DefOp, ea_t DefAddr) {
map<ea_t, size_t>::iterator MapIter = this->AddrInstMap.find(DefAddr);
assert(MapIter != this->AddrInstMap.end());
SMPInstr *DefInst = this->GetInstFromIndex(MapIter->second);
set<DefOrUse, LessDefUse>::iterator DefIter = DefInst->FindDef(DefOp);
assert(DefIter != DefInst->GetLastDef());
return DefIter;
} // end of SMPBasicBlock::GetGlobalDefIterFromDefAddr()
#if 0 // never used
// Given a USE operand and the address of its instr, return DEF using DU chains or Phi func.
set<DefOrUse, LessDefUse>::iterator SMPBasicBlock::GetDefFromOpAddr(op_t UseOp, ea_t InstAddr, int SSANum) {
ea_t DefAddr;
SMPInstr *DefInstr;
set<DefOrUse, LessDefUse>::iterator DefIter;
if (this->IsLocalName(UseOp)) {
// Search in the local DU chains.
unsigned int LocalDUIndex = this->GetLocalDUIndex(UseOp, SSANum);
DefAddr = this->LocalDUChains.ChainsByName.at(LocalDUIndex).GetDef(SSANum);
DefInstr = this->FindInstr(DefAddr);
DefIter = DefInstr->FindDef(UseOp);
assert(DefIter != DefInstr->GetLastDef());
}
else {
// Global DEF for this SSANum must be in the Phi functions or within a block.
DefAddr = this->MyFunc->GetGlobalDefAddr(UseOp, SSANum);
if (DefAddr == BADADDR) { // Could not find it anywhere.
SMP_msg("ERROR: Failure in GetDefFromOpAddr(): InstAddr %x SSANum %d\n",
InstAddr, SSANum);
assert(DefAddr != BADADDR); // kablooey!
}
else if (DefAddr < this->MyFunc->GetNumBlocks()) {
// A block number was returned, not an instruction address.
// The DEF for this SSANum is only in a Phi function for that
// block number.
size_t BlockNumber = (size_t) DefAddr;
set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->MyFunc->GetPhiIterForPhiDef(BlockNumber, UseOp, SSANum);
// PhiIter is guaranteed to be good, else we assert in GetPhiIterForPhiDef().
assert(SSANum == PhiIter->GetDefSSANum());
DefOrUse DefCopy = PhiIter->GetDefCopy();
DefOrUseSet DummySet;
DefIter = DummySet.InsertRef(DefCopy);
}
else { // Must be a DEF within a block, not in a Phi function.
// NOTE: We might be looking within the current block with this code; perfectly OK.
SMPBasicBlock *DefBlock = this->MyFunc->GetBlockFromInstAddr(DefAddr);
DefIter = DefBlock->GetGlobalDefIterFromDefAddr(UseOp, DefAddr);
}
}
return DefIter;
} // end of SMPBasicBlock::GetDefFromOpAddr()
#endif
#if STARS_BUILD_DEF_USE_CHAINS
// Given a USE operand and the address of its instr, return DEF addr using DU chains or Phi func.
// If DEF is in a Phi function, we return the block number, which never conflicts with instruction
// addresses.
ea_t SMPBasicBlock::GetDefAddrFromUseAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName) {
ea_t DefAddr = BADADDR;
set<DefOrUse, LessDefUse>::iterator DefIter;
bool RegisterOp = (o_reg == UseOp.type);
if (LocalName) {
// Search in the local DU chains.
unsigned int LocalDUIndex = this->GetLocalDUIndex(UseOp, SSANum);
DefAddr = this->GetFirstDefAddr(LocalDUIndex, SSANum, false);
}
else if (RegisterOp) {
// Global DEF for this SSANum must be in the Phi functions or within a block.
DefAddr = this->MyFunc->GetGlobalDefAddr(UseOp, SSANum);
if (DefAddr == BADADDR) { // Could not find it anywhere.
this->GetFunc()->Dump();
SMP_msg("ERROR: Failure in GetDefAddrFromUseAddr(): InstAddr %x SSANum %d\n",
InstAddr, SSANum);
SMP_msg(" LocalName: %d UseOp.reg: %d\n", LocalName, UseOp.reg);
assert(DefAddr != BADADDR); // kablooey!
}
}
else if (MDIsDirectStackAccessOpnd(UseOp, this->GetFunc()->UsesFramePointer())) {
// Func->GetGlobalDefAddr() only works on registers. Get stack DefAddr from
// Phi functions or DU chains.
set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->FindPhi(UseOp);
if (PhiIter != this->GetLastPhi()) {
// Found a Phi function for UseOp; does it DEF our SSANum?
int PhiDefSSANum = PhiIter->GetDefSSANum();
if (PhiDefSSANum == SSANum) {
return this->BlockNum; // BlockNum is signal that the Def has no real addr, is in Phi
}
}
unsigned int GlobalDUIndex = this->GetGlobalDUIndex(UseOp, BADADDR);
size_t chain;
size_t NumChains = this->GetNumLocalChains(GlobalDUIndex, true);
ea_t LastAddr;
for (chain = 0; chain < NumChains; ++chain) {
LastAddr = this->GetLastUseAddr(GlobalDUIndex, chain, true);
if (LastAddr >= InstAddr) {
// Found the chain with InstAddr within it.
DefAddr = this->GetFirstDefAddr(GlobalDUIndex, chain, true);
break;
}
}
}
return DefAddr;
} // end of SMPBasicBlock::GetDefAddrFromUseAddr()
#else
// Given a USE operand and the address of its instr, return DEF addr using SSA chains or Phi func.
// If DEF is in a Phi function, we return the block number, which (hopefully) never conflicts with instruction
// addresses.
ea_t SMPBasicBlock::GetDefAddrFromUseAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName) {
ea_t DefAddr = BADADDR;
set<DefOrUse, LessDefUse>::iterator DefIter;
bool RegisterOp = (o_reg == UseOp.type);
bool PhiUse = (InstAddr < this->GetFunc()->GetNumBlocks());
if (RegisterOp && (!LocalName)) {
// Global DEF for this SSANum must be in the Phi functions or within a block.
DefAddr = this->MyFunc->GetGlobalDefAddr(UseOp, SSANum); // only works on registers
if (DefAddr == BADADDR) { // Could not find it anywhere.
this->GetFunc()->Dump();
SMP_msg("ERROR: Failure in GetDefAddrFromUseAddr(): InstAddr %lx SSANum %d\n",
(unsigned long) InstAddr, SSANum);
SMP_msg(" LocalName: %d UseOp.reg: %d\n", LocalName, UseOp.reg);
assert(DefAddr != BADADDR); // kablooey!
}
}
else if (LocalName || MDIsDirectStackAccessOpnd(UseOp, this->GetFunc()->UsesFramePointer())) {
if (PhiUse) {
// Need to find DEF for a PhiUse. Temporarily, we will use the slow linear search method.
DefAddr = this->GetFunc()->GetGlobalDefAddr(UseOp, SSANum);
if (BADADDR == DefAddr) { // Need to search Phi functions.
// Rare case in which a Phi USE was traced only to a Phi DEF in an earlier block.
DefAddr = (ea_t) this->GetFunc()->GetBlockNumForPhiDef(UseOp, SSANum);
assert(BADADDR != DefAddr);
}
}
else {
vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(InstAddr);
if (this->IsVarKill(UseOp)) { // Cannot find a DEF in block if not in VarKill set for this block
vector<SMPInstr *>::reverse_iterator RevInstIter(InstIter);
while (RevInstIter != this->GetRevInstEnd()) {
SMPInstr *CurrInst = (*RevInstIter);
set<DefOrUse, LessDefUse>::iterator DefIter = CurrInst->FindDef(UseOp);
if (DefIter != CurrInst->GetLastDef()) {
DefAddr = CurrInst->GetAddr();
assert(SSANum == DefIter->GetSSANum());
break;
}
++RevInstIter;
}
}
if (DefAddr == BADADDR) { // not found yet
// Must be a global name defined in the Phi functions or LiveIn and UpExposed to the block, or a non-stack mem access.
bool UseFP = this->GetFunc()->UsesFramePointer();
assert(!LocalName || (!MDIsDataFlowOpnd(UseOp, UseFP)));
set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->FindPhi(UseOp);
if (PhiIter != this->GetLastPhi()) {
// Found a Phi function for UseOp; does it DEF our SSANum?
int PhiDefSSANum = PhiIter->GetDefSSANum();
if (PhiDefSSANum == SSANum) {
DefAddr = this->BlockNum; // BlockNum is signal that the Def has no real addr, is in Phi
}
}
else {
DefAddr = this->GetFirstAddr() - 1; // pseudo-def-addr for LiveIn, not in Phi, UpExposed
}
}
}
}
return DefAddr;
} // end of SMPBasicBlock::GetDefAddrFromUseAddr()
#endif
ea_t SMPBasicBlock::GetUltimateDefAddr(op_t UseOp, ea_t InstAddr, int SSANum, bool LocalName) {
ea_t DefAddr = BADADDR;
DefAddr = this->GetDefAddrFromUseAddr(UseOp, InstAddr, SSANum, LocalName);
bool LiveInAddr = (DefAddr == (this->GetFirstAddr() - 1));
if (LiveInAddr && this->IsLiveIn(UseOp)) { // UpExposed or pass-through case
// We need to find the predecessor block that DEFed the UseOp/SSANum.
assert(!LocalName); // also cannot be a register; it is a global name stack var
#if 1
size_t NumBlocks = this->GetFunc()->GetNumBlocks();
bool FoundDEF = false;
set<DefOrUse, LessDefUse>::iterator DefIter;
// Check special case of DEF in marker instruction at beginning of function.
if (SSANum == 0) {
SMPInstr *FirstInst = this->GetFunc()->GetInstFromAddr(this->GetFunc()->GetFirstFuncAddr() - 1);
if (FirstInst->IsFloatNop()) {
DefIter = FirstInst->FindDef(UseOp);
if (DefIter != FirstInst->GetLastDef()) {
assert(0 == DefIter->GetSSANum());
DefAddr = FirstInst->GetAddr();
FoundDEF = true;
}
}
}
for (size_t BlockIndex = 0; (BlockIndex < NumBlocks) && (!FoundDEF); ++BlockIndex) {
SMPBasicBlock *CurrBlock = this->GetFunc()->GetBlockByNum(BlockIndex);
// Don't bother to look inside block insts unless UseOp is killed and LiveOut
if (CurrBlock->IsLiveOut(UseOp)) {
// Can we match the SSANum in an inst DEF or a Phi DEF?
set<SMPPhiFunction, LessPhi>::iterator PhiIter = CurrBlock->FindPhi(UseOp);
if (PhiIter != CurrBlock->GetLastPhi()) {
if (SSANum == PhiIter->GetDefSSANum()) {
DefAddr = (ea_t) BlockIndex;
FoundDEF = true;
break;
}
}
if (CurrBlock->IsVarKill(UseOp)) {
vector<SMPInstr *>::reverse_iterator RevInstIter;
for (RevInstIter = CurrBlock->GetRevInstBegin(); RevInstIter != CurrBlock->GetRevInstEnd(); ++RevInstIter) {
SMPInstr *CurrInst = (*RevInstIter);
ea_t CurrAddr = CurrInst->GetAddr();
if (CurrInst->HasDestMemoryOperand() || CurrInst->MDIsPushInstr()) {
DefIter = CurrInst->FindDef(UseOp);
if (DefIter != CurrInst->GetLastDef()) {
// Because we are using a reverse iterator, the first DEF we encounter either
// matches the SSANum or else this block is irrelevant.
if (SSANum == DefIter->GetSSANum()) {
DefAddr = CurrAddr;
FoundDEF = true;
}
break; // found it or did not; break regardless
}
}
}
}
}
}
#else
list<SMPBasicBlock *>::iterator PredIter;
bool FoundDefiningBlock = false;
for (PredIter = this->GetFirstPred(); PredIter != this->GetLastPred(); ++PredIter) {
SMPBasicBlock *PredBlock = (*PredIter);
if (!PredBlock->IsProcessed() && PredBlock->IsLiveOut(UseOp)) {
// Found possible defining block. At least one predecessor should have UseOp LiveOut.
// We can recurse, but we need a pseudo UseAddr. We
// will use the last instruction in PredBlock as the pseudo UseAddr, but first
// we need to check to see if it is the DefAddr.
vector<SMPInstr *>::reverse_iterator RevInstIter = PredBlock->GetRevInstBegin();
SMPInstr *LastPredInst = (*RevInstIter);
ea_t LastPredAddr = LastPredInst->GetAddr();
if (LastPredInst->FindDef(UseOp) != LastPredInst->GetLastDef()) {
DefAddr = LastPredAddr;
PredBlock->SetProcessed(true);
FoundDefiningBlock = true;
}
else { // We can use LastPredInst addr as pseudo-UseAddr.
DefAddr = PredBlock->GetUltimateDefAddr(UseOp, LastPredAddr, SSANum, LocalName);
}
if (BADADDR != DefAddr) {
break;
}
}
}
#endif
} // end if LiveIn
#if 0
if (LiveInAddr) {
DefAddr = BADADDR;
}
#endif
assert(BADADDR != DefAddr);
return DefAddr;
} // end of SMPBasicBlock::GetUltimateDefAddr()
// STUB: Trace UseOp through move and Phi defs to some defining operation.
ea_t SMPBasicBlock::GetUltimateOperandSource(ea_t UseAddr, op_t UseOp, int UseSSANum) {
bool LocalName = this->IsLocalName(UseOp);
ea_t DefiningAddr = this->GetDefAddrFromUseAddr(UseOp, UseAddr, UseSSANum, LocalName);
SMPBasicBlock *CurrBlock;
// We have four possibilities for DefiningAddr:
// 1: BADADDR means we cannot trace the operand.
// 2: An instruction address, in which case we recurse if inst is a move.
// 3: Our block number, which means a Phi DEF, so we need to recurse into our predecessors.
// 4: OUr block's first addr minus one, indicating upexposed in this block, need to recurse into predecessors.s
return DefiningAddr;
} // end of SMPBasicBlock::GetUltimateOperandSource()
// Does DefOp get written out in truncated form (lower bits only)?
bool SMPBasicBlock::IsOpDestTruncatedWrite(op_t DefOp, int DefSSANum, ea_t DefAddr) {
vector<SMPInstr *>::iterator InstIter;
SMPInstr *LastUseInst = NULL;
set<DefOrUse, LessDefUse>::iterator DefIter;
bool RegisterOp = (o_reg == DefOp.type);
bool LocalName = this->IsLocalName(DefOp);
bool LastUseIsTruncatedWrite = false;
size_t chain;
size_t NumChains;
ea_t LastAddr = BADADDR;
if (!RegisterOp || (DefSSANum == SMP_SSA_UNINIT))
return false;
#if STARS_BUILD_DEF_USE_CHAINS
if (LocalName) {
// Search in the local DU chains.
unsigned int LocalDUIndex = this->GetLocalDUIndex(DefOp, DefSSANum);
NumChains = this->GetNumLocalChains(LocalDUIndex, false);
for (chain = 0; chain < NumChains; ++chain) {
if (this->GetFirstDefAddr(LocalDUIndex, chain, false) == DefAddr) {
// Found the chain with DefAddr within it.
LastAddr = this->GetLastUseAddr(LocalDUIndex, chain, false);
break;
}
}
}
else {
unsigned int GlobalDUIndex = this->GetGlobalDUIndex(DefOp, DefAddr);
NumChains = this->GetNumLocalChains(GlobalDUIndex, true);
for (chain = 0; chain < NumChains; ++chain) {
if (this->GetFirstDefAddr(GlobalDUIndex, chain, true) == DefAddr) {
// Found the chain with DefAddr within it.
LastAddr = this->GetLastUseAddr(GlobalDUIndex, chain, true);
break;
}
}
}
#endif
InstIter = this->GetInstIterFromAddr(DefAddr);
++InstIter;
while (InstIter != this->GetLastInst()) {
LastUseInst = (*InstIter);
if (LastUseInst->FindUse(DefOp) != LastUseInst->GetLastUse()) {
LastAddr = LastUseInst->GetAddr();
}
if (LastUseInst->FindDef(DefOp) != LastUseInst->GetLastDef()) {
// re-DEF
break;
}
++InstIter;
}
if (BADADDR != LastAddr) {
InstIter = this->GetInstIterFromAddr(LastAddr);
LastUseInst = (*InstIter);
if (LastUseInst->MDDoublesWidth()) {
LastUseIsTruncatedWrite = true;
}
else if (LastUseInst->MDIsReducedWidthMove()) {
// If DefOp is used as an address reg, it is not a truncated write of DefOp;
// otherwise, it is.
LastUseIsTruncatedWrite = LastUseInst->IsNonAddressReg(DefOp);
}
if (!LastUseIsTruncatedWrite && (NULL != LastUseInst)) {
// See if we can recurse through a regular move.
if (LastUseInst->MDIsMoveInstr()) {
DefIter = LastUseInst->GetFirstNonFlagsDef();
assert(DefIter != LastUseInst->GetLastDef());
op_t CopyDefOp = DefIter->GetOp();
bool UseFP = this->GetFunc()->UsesFramePointer();
if (MDIsDataFlowOpnd(CopyDefOp, UseFP)) {
int CopyDefSSANum = DefIter->GetSSANum();
LastUseIsTruncatedWrite = this->IsOpDestTruncatedWrite(CopyDefOp, CopyDefSSANum, LastAddr);
}
}
}
}
return LastUseIsTruncatedWrite;
} // end of SMPBasicBlock::IsOpDestTruncatedWrite()
// Update the LiveOut set for the block.
// Return true if it changed, false otherwise.
bool SMPBasicBlock::UpdateLiveOut(void) {
bool changed = false;
set<op_t, LessOp> OldLiveOut(this->LiveOutSet); // save copy of old LiveOutSet
this->LiveOutSet.clear(); // Clear it and rebuild it
// Dataflow equation for LiveOutSet: If a variable is live-in for any successor
// block, it is live out for this block.
list<SMPBasicBlock *>::iterator SuccIter;
set<op_t, LessOp>::iterator InSuccIter;
for (SuccIter = this->Successors.begin(); SuccIter != this->Successors.end(); ++SuccIter) {
for (InSuccIter = (*SuccIter)->GetFirstLiveIn(); InSuccIter != (*SuccIter)->GetLastLiveIn(); ++InSuccIter) {
this->LiveOutSet.insert(*InSuccIter);
}
}
// Only remaining question: Did the LiveOutSet change?
// Short cut: If the set cardinality changed, then the set changed.
if (this->LiveOutSet.size() != OldLiveOut.size()) {
changed = true;
}
else { // Same # of elements; move through in lockstep and compare.
set<op_t, LessOp>::iterator NewIter = this->LiveOutSet.begin();
set<op_t, LessOp>::iterator OldIter = OldLiveOut.begin();
set<op_t, LessOp>::value_compare OpComp = OldLiveOut.value_comp(); // LessOp()
while (OldIter != OldLiveOut.end()) { // both iters terminate simultaneously
if (OpComp(*OldIter, *NewIter) || OpComp(*NewIter, *OldIter)) {
changed = true;
break;
}
++OldIter;
++NewIter;
}
}
if (changed)
this->SetLiveInStale(true);
OldLiveOut.clear();
return changed;
} // end of SMPBasicBlock::UpdateLiveOut()
#if 0
// Set the SSA numbers for the DEFs in the LiveOut set.
void SMPBasicBlock::SetLiveOutSSANums(void) {
size_t LiveOutCount = this->LiveOutSet.size();
size_t LiveOutDefsMarked = 0;
vector<SMPInstr *>::reverse_iterator RevInstIter;
for (RevInstIter = this->GetRevInstBegin(); (RevInstIter != this->GetRevInstEnd()) && (LiveOutDefsMarked < LiveOutCount); ++RevInstIter) {
set<DefOrUse, LessDefUse>::iterator DefIter;
SMPInstr *CurrInst = (*RevInstIter);
for (DefIter = CurrInst->GetFirstDef(); DefIter != CurrInst->GetLastDef(); ++DefIter) {
op_t DefOp = DefIter->GetOp();
set<DefOp, LessOp>::iterator LiveOutIter = this->LiveOutSet.find(DefOp);
if (LiveOutIter != this->GetLastLiveOut()) { // found DefOp in LiveOut set
;
}
}
}
return;
} // end of SMPBasicBlock::SetLiveOutSSANums()
#endif
// Compute the ReachesIn set as the union of the ReachesOut sets of all predecessor blocks.
// Return TRUE if the ReachesIn set was updated, false if it gained no new elements.
bool SMPBasicBlock::ComputeReachesInSet(void) {
size_t OldSize = this->ReachesInSet.size();
size_t NewSize; // If NewSize becomes different from OldSize, then ReachesInSet changed.
list<SMPBasicBlock *>::iterator PredIter;
for (PredIter = this->GetFirstPred(); PredIter != this->GetLastPred(); ++PredIter) {
SMPBasicBlock *CurrPred = *PredIter;
this->ReachesInSet.insert(CurrPred->GetFirstReachesOut(), CurrPred->GetLastReachesOut());
}
NewSize = this->ReachesInSet.size();
return (NewSize != OldSize);
} // end of SMPBasicBlock::ComputeReachesInSet()
// Compute the ReachesOut set according to its dataflow formula: ReachesOut = ((ReachesIn minus VarKill) union DownExposedDefs).
bool SMPBasicBlock::ComputeReachesOutSet(void) {
size_t OldSize = this->ReachesOutSet.size();
size_t NewSize; // If NewSize becomes different from OldSize, then ReachesOutSet changed.
// First step: Add all ReachesIn defns that are not killed.
set<pair<op_t, ea_t>, LessDefinition>::iterator ReachesInIter;
for (ReachesInIter = this->GetFirstReachesIn(); ReachesInIter != this->GetLastReachesIn(); ++ReachesInIter) {
op_t InOp = ReachesInIter->first;
if (!(this->IsVarKill(InOp))) {
this->AddReachesOut(*ReachesInIter);
}
}
// Second step: Add DEDefns.
set<pair<op_t, ea_t>, LessDefinition>::iterator DEDefnIter;
for (DEDefnIter = this->GetFirstDownExposedDefn(); DEDefnIter != this->GetLastDownExposedDefn(); ++DEDefnIter) {
this->AddReachesOut(*DEDefnIter);
}
NewSize = this->ReachesOutSet.size();
this->ResetReachesOutStale();
return (NewSize != OldSize);
} // end of SMPBasicBlock::ComputeReachesOutSet()
// Add DefOp, remove previous defs of DefOp that now do not reach the end of the block.
void SMPBasicBlock::UpdateDownExposedDefs(op_t DefOp, ea_t InstAddr) {
// First, remove any definition of DefOp that precedes the current definition.
set<pair<op_t, ea_t>, LessDefinition>::iterator DEDefnIter = this->GetFirstDownExposedDefn();
while (DEDefnIter != this->GetLastDownExposedDefn()) {
op_t OldOp = DEDefnIter->first;
if (IsEqOpIgnoreBitwidth(OldOp, DefOp)) {
(void) this->DownExposedDefnSet.erase(DEDefnIter);
break; // save time; should never be more than one defn per DefOp in this set, unlike ReachesIn & ReachesOut
}
else {
++DEDefnIter;
}
}
// Next, insert the new definition.
pair<op_t, ea_t> NewDefn(DefOp, InstAddr);
pair<set<pair<op_t, ea_t>, LessDefinition>::iterator, bool> InsertResult;
InsertResult = this->DownExposedDefnSet.insert(NewDefn);
assert(InsertResult.second);
this->SetReachesOutStale();
return;
} // end of SMPBasicBlock::UpdateDownExposedDefs()
// Evaluate constants for all instructions as part of SCCP algorithm at SMPFunction level.
void SMPBasicBlock::SCCPEvaluateConstants(enum STARSBranchConst &BranchEval, list<pair<int, int> > &CFGWorkList, list<pair<int, int> > &SSAWorkList) {
// for (each instruction i in block) do
// if (i is an assignment) then
// EvaluateAssign(i)
// else if (i is a conditional branch) then
// EvaluateConditional(i)
// endif
// endfor
BranchEval = STARS_BRANCH_UNKNOWN;
// for (each instruction i in block) do
vector<SMPInstr *>::iterator InstIter;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
// if (i is an assignment) then
// EvaluateAssign(i)
SMPitype DataFlowType = CurrInst->GetDataFlowType();
if (DEFAULT == DataFlowType) {
CurrInst->SCCPEvaluateAssignment(SSAWorkList);
}
// else if (i is a conditional branch) then
// EvaluateConditional(i)
else if (COND_BRANCH == DataFlowType) {
CurrInst->SCCPEvaluateCondBranch(BranchEval);
}
// endif
// endfor
}
this->SetSCCPVisited(true);
// Handle successors, based on BranchEval.
this->SCCPHandleSuccessors(BranchEval, CFGWorkList);
return;
} // end of SMPBasicBlock::SCCPEvaluateConstants()
// Propagate GlobalOp/DefSSANum const value
void SMPBasicBlock::SCCPGlobalPropagationHelper(op_t GlobalOp, int DefSSANum, vector<STARSBitSet> ExecutedEdgeBitSet, list<pair<int, int> > &CFGWorkList, list<pair<int, int> > &SSAWorkList) {
// Three cases:
// (1) GlobalOp/DefSSANum is a Phi USE, in which case we re-eval the Phi Function and return.
// (2) GlobalOp/DefSSANum is upward exposed, in which case we find the UpExposed USEs and re-eval those statements and recurse if LiveOut.
// (3) GlobalOp/DefSSANum is the pass-through case, so it must be LiveOut and we recurse.
bool FoundReDEF = true;
enum STARSBranchConst BranchEval;
BranchEval = STARS_BRANCH_UNKNOWN;
this->SetProcessed(true); // prevent infinite recursion
set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->FindPhi(GlobalOp);
if (PhiIter != this->GetLastPhi()) { // Case 1.
int PhiDefSSANum = PhiIter->GetDefSSANum();
if (PhiDefSSANum != DefSSANum) { // DefSSANum should be found among the Phi USEs
this->GetFunc()->EvaluateAllPhiConstants(this->GetNumber(), ExecutedEdgeBitSet, SSAWorkList);
}
}
else if (this->IsUpExposed(GlobalOp)) { // case 2
FoundReDEF = false;
vector<SMPInstr *>::iterator InstIter;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
set<DefOrUse, LessDefUse>::iterator UseIter = CurrInst->FindUse(GlobalOp);
if (UseIter != CurrInst->GetLastUse()) { // operand is USEd; check SSANum
int UseSSANum = UseIter->GetSSANum();
if (UseSSANum == DefSSANum) {
SMPitype DataFlowType = CurrInst->GetDataFlowType();
if (DEFAULT == DataFlowType) {
CurrInst->SCCPEvaluateAssignment(SSAWorkList);
}
else if (COND_BRANCH == DataFlowType) {
CurrInst->SCCPEvaluateCondBranch(BranchEval);
this->SCCPHandleSuccessors(BranchEval, CFGWorkList);
}
}
}
set<DefOrUse, LessDefUse>::iterator DefIter = CurrInst->FindDef(GlobalOp);
if (DefIter != CurrInst->GetLastDef()) { // check for re-DEF
int NewDefSSANum = DefIter->GetSSANum();
if (NewDefSSANum > DefSSANum) { // re-DEF; we can stop searching for USEs of DefOp/DefSSANum in this block
FoundReDEF = true;
break;
}
}
} // end for all insts in block
}
else if (this->IsLiveOut(GlobalOp)) { // case 3
// Not UpExposed, but LiveOut; not re-DEF in block
FoundReDEF = false;
}
if (!FoundReDEF) { // common recursion for case 2 and case 3
list<SMPBasicBlock *>::iterator SuccIter;
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
SMPBasicBlock *SuccBlock = (*SuccIter);
if ((!SuccBlock->IsProcessed()) && SuccBlock->IsSCCPVisited() && SuccBlock->IsLiveIn(GlobalOp)) {
SuccBlock->SCCPGlobalPropagationHelper(GlobalOp, DefSSANum, ExecutedEdgeBitSet, CFGWorkList, SSAWorkList);
}
}
}
return;
} // end of SMPBasicBlock::SCCPGlobalPropagationHelper()
// Based on BranchEval, push successors onto CFGWorkList
void SMPBasicBlock::SCCPHandleSuccessors(enum STARSBranchConst &BranchEval, list<pair<int, int> > &CFGWorkList) {
// Put block successors on CFGWorkList, based on conditional branch evaluation if any
bool TakeDistantSucc = (BranchEval != STARS_BRANCH_NEVER_TAKEN);
bool TakeFallThroughSucc = (BranchEval != STARS_BRANCH_ALWAYS_TAKEN);
list<SMPBasicBlock *>::iterator SuccBlockIter = this->GetFirstSucc();
list<SMPBasicBlock *>::iterator FallThroughSuccIter = this->GetFallThroughSucc();
while (SuccBlockIter != this->GetLastSucc()) { // not the return block; has a successor
if (((SuccBlockIter == FallThroughSuccIter) && (TakeFallThroughSucc))
|| ((SuccBlockIter != FallThroughSuccIter) && (TakeDistantSucc))) {
int NextBlockNum = (*SuccBlockIter)->GetNumber();
pair<int, int> TempEdge(this->GetNumber(), NextBlockNum);
CFGWorkList.push_back(TempEdge);
}
++SuccBlockIter;
}
return;
} // end of SMPBasicBlock::SCCPHandleSuccessors()
// Patch binary to make this block into nops.
void SMPBasicBlock::SCCPNullifyUnreachableBlock(void) {
SMP_msg("INFO: SCCP: Removing unreachable block at %lx, patching in NOPs\n",
(unsigned long) this->GetFirstAddr());
// Remove this block from the predecessors list of its successors.
list<SMPBasicBlock *>::iterator SuccIter;
ea_t TempAddr = this->GetFirstAddr();
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
(*SuccIter)->ErasePred(TempAddr);
}
#if 1
// Remove this block from the successors list of its predecessors.
list<SMPBasicBlock *>::iterator PredIter;
for (PredIter = this->GetFirstPred(); PredIter != this->GetLastPred(); ++PredIter) {
(*PredIter)->EraseSucc(TempAddr);
}
#endif
// Patch all bytes in the database for this block into nops.
size_t NumBytes = this->GetBlockSize();
ea_t CurrAddr = this->GetFirstAddr();
for (size_t ByteIndex = 0; ByteIndex < NumBytes; ++ByteIndex) {
bool success = patch_byte(CurrAddr, MD_BINARY_NOP_INSTRUCTION);
// If success == false, that just means the byte already had that value in the
// database, so nothing was changed. Cannot assert that success should be true.
// assert(success);
++CurrAddr;
}
return;
} // end of SMPBasicBlock::SCCPNullifyUnreachableBlock()
// Gather statistics on SCCP effectiveness
void SMPBasicBlock::SCCPGatherStatistics(void) {
#if STARS_SCCP_GATHER_STATISTICS
vector<SMPInstr *>::iterator InstIter;
bool ConstArgFound = false;
bool ArgWriteFound = false;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
SMPitype DataFlowType = CurrInst->GetDataFlowType();
if (CurrInst->HasDestMemoryOperand()) { // NOTE: Use MDIsArgumentPass() instead?
op_t MoveSourceOp = CurrInst->GetMoveSource();
op_t DEFMemOp = CurrInst->GetMemDef();
if ((o_void != MoveSourceOp.type) && this->GetFunc()->IsInOutgoingArgsRegion(DEFMemOp)) {
++SCCPOutgoingArgWriteCount;
ArgWriteFound = true;
if (o_imm == MoveSourceOp.type) {
++SCCPConstantOutgoingArgWriteCount;
ConstArgFound = true;
}
else if (o_reg == MoveSourceOp.type) {
CanonicalizeOpnd(MoveSourceOp);
set<DefOrUse, LessDefUse>::iterator UseIter = CurrInst->FindUse(MoveSourceOp);
assert(UseIter != CurrInst->GetLastUse());
int UseSSANum = UseIter->GetSSANum();
int UseHashIndex = HashGlobalNameAndSSA(MoveSourceOp, UseSSANum);
map<int, struct STARS_SCCP_Const_Struct>::iterator ConstIter = this->GetFunc()->FindConstValue(UseHashIndex);
if (ConstIter != this->GetFunc()->GetLastConstValueIter()) { // found an SCCP const entry
++SCCPConstantOutgoingArgWriteCount;
ConstArgFound = true;
}
}
}
}
else if ((DataFlowType == CALL) || (DataFlowType == INDIR_CALL)) {
// Need to start gathering data for the next call; reset counters.
// Can have multiple calls in one basic block.
if (ArgWriteFound) {
++SCCPFuncsWithArgWriteCount;
if (ConstArgFound) {
++SCCPFuncsWithConstantArgWriteCount;
}
}
ArgWriteFound = false;
ConstArgFound = false;
}
} // end for all instructions
if (ArgWriteFound) {
++SCCPFuncsWithArgWriteCount;
if (ConstArgFound) {
++SCCPFuncsWithConstantArgWriteCount;
}
}
#endif
return;
} // end of SMPBasicBlock::SCCPGatherStatistics()
// Insert RPO number block into the dominance frontier set.
void SMPBasicBlock::AddToDomFrontier(int block) {
this->DomFrontier.insert(block);
return;
} // end of SMPBasicBlock::AddToDomFrontier()
// Fill the set of non-global names used in this block. Set local indices that can be
// used later to index into a vector of def-use chains.
void SMPBasicBlock::SetLocalNames(void) {
vector<SMPInstr *>::iterator InstIter;
size_t LocalIndex = 0;
#if SMP_DEBUG_DATAFLOW
SMP_msg("Entered SetLocalNames.\n");
#endif
set<DefOrUse, LessDefUse>::iterator CurrDef;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
for (CurrDef = CurrInst->GetFirstDef(); CurrDef != CurrInst->GetLastDef(); ++CurrDef) {
op_t DefOp = CurrDef->GetOp();
if (!(this->MyFunc->IsGlobalName(DefOp))) {
// Not in global names set
if (this->LocalNames.end() == this->LocalNames.find(DefOp)) {
// Not yet in LocalNames, so add it.
SetGlobalIndex(&DefOp, LocalIndex);
this->LocalNames.insert(DefOp);
++LocalIndex;
}
}
}
}
return;
} // end of SMPBasicBlock::SetLocalNames()
#if STARS_BUILD_DEF_USE_CHAINS
// Create local def-use chains for all global names
// Important to remember that a chain can start without a def because the variable is Live-In;
// in this case we give the chain a pseudo-def at address (first addr in block - 1) **!!**
// Variant on SSALocalRenumber
void SMPBasicBlock::CreateGlobalChains() {
bool DebugFlag = false;
#if 0
DebugFlag |= (0 == strcmp(".init_proc", this->MyFunc->GetFuncName()));
#endif
size_t NumGlobals = this->MyFunc->NumGlobalNames();
size_t LocalIndex;
vector<int> LocalUseIndex;
// Initialize LocalUseIndex and DUChain values for each local name.
set<op_t, LessOp>::iterator NameIter;
if (NumGlobals < 1)
return;
this->GlobalDUChains.ChainsByName.clear();
this->GlobalDUChains.ChainsByName.reserve(NumGlobals);
op_t TempOp = InitOp;
SMPDUChainArray Temp(TempOp, this->GetFirstAddr() - 1);
if (DebugFlag)
SMP_msg("Initializing GlobalChainsByName.\n");
this->GlobalDUChains.ChainsByName.assign(NumGlobals, Temp);
for (NameIter = this->MyFunc->GetFirstGlobalName(); NameIter != this->MyFunc->GetLastGlobalName(); ++NameIter) {
LocalIndex = (size_t) ExtractGlobalIndex(*NameIter);
LocalUseIndex.push_back(-1); // init LocalUse indices to -1; first DEF will make it 0
// Set the local name for each DU chain array.
if (LocalIndex > this->GlobalDUChains.ChainsByName.size())
SMP_msg("FATAL ERROR: LocalIndex %zu out of bounds in CreateGlobalChains.\n", LocalIndex);
if (DebugFlag)
SMP_msg("Setting name for LocalIndex = %zu\n", LocalIndex);
this->GlobalDUChains.ChainsByName.at(LocalIndex).SetName(*NameIter, this->GetFirstAddr() - 1);
}
// Iterate through all instructions in the block. For each DEF of a global name,
// set a new LocalUse index and start a new DU chain. For each USE of a global name,
// set the current LocalUse index for that name and add the instruction to the DU
// chain.
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator CurrUse, CurrDef;
set<op_t, LessOp>::iterator UseNameIter, DefNameIter;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
size_t NameIndex;
ea_t InstAddr = CurrInst->GetAddr();
// USEs get referenced logically before DEFs, so start with them.
CurrUse = CurrInst->GetFirstUse();
while (CurrUse != CurrInst->GetLastUse()) {
op_t UseOp = CurrUse->GetOp();
UseNameIter = this->MyFunc->FindGlobalName(UseOp);
if (UseNameIter != this->MyFunc->GetLastGlobalName()) {
// Found USE of a global name
NameIndex = ExtractGlobalIndex(*UseNameIter);
if (NameIndex > LocalUseIndex.size())
SMP_msg("NameIndex %zu out of range in CreateGlobalChains.\n", NameIndex);
int LocalUseNum = LocalUseIndex.at(NameIndex);
if (LocalUseNum == -1) { // LiveIn, use before def
LocalUseIndex.at(NameIndex)++;
LocalUseNum++;
// Make the DEF be just before the start of the block
SMPDefUseChain TempDefChain(UseOp, 0);
this->GlobalDUChains.ChainsByName.at(NameIndex).PushChain(TempDefChain);
#if SMP_COUNT_MEMORY_ALLOCATIONS
SMPDefUseChainBytes += sizeof(TempDefChain);
#endif
}
// Push address of USE instruction onto the DEF-USE chain for this LocalUseNum.
this->GlobalDUChains.ChainsByName.at(NameIndex).PushUse(LocalUseNum, CurrInst->GetAddr());
#if SMP_COUNT_MEMORY_ALLOCATIONS
SMPDefUseChainBytes += SMP_DU_ADDR_SIZE;
#endif
}
++CurrUse;
} // end for all USEs in the instruction.
// Now do the DEFs.
CurrDef = CurrInst->GetFirstDef();
while (CurrDef != CurrInst->GetLastDef()) {
op_t DefOp = CurrDef->GetOp();
DefNameIter = this->MyFunc->FindGlobalName(DefOp);
if (DefNameIter != this->MyFunc->GetLastGlobalName()) {
// Found DEF of a global name.
size_t NameIndex = ExtractGlobalIndex(*DefNameIter);
if (NameIndex > LocalUseIndex.size())
SMP_msg("DEF NameIndex %zu out of range in CreateGlobalChains.\n", NameIndex);
++LocalUseIndex[NameIndex]; // move up to next LocalUse subscript number
#if 0
// Before the push_back() call, we should have # chains equal to new LocalUseNum
int LocalUseNum = LocalUseIndex.at(NameIndex);
assert(LocalUseNum == this->GlobalDUChains.ChainsByName.at(NameIndex).GetSize());
#endif
// Set up a new DU chain and push it onto the vector of DU chains for this
// local name. Push the DEF onto the list (it will be the first reference
// on the list, because the list was newly created).
SMPDefUseChain TempDefChain(DefOp, CurrInst->GetAddr() - this->GetFirstAddr() + 1);
this->GlobalDUChains.ChainsByName.at(NameIndex).PushChain(TempDefChain);
#if SMP_COUNT_MEMORY_ALLOCATIONS
SMPDefUseChainBytes += sizeof(TempDefChain);
#endif
}
++CurrDef;
} // end for all DEFs in the instruction
} // end for all instructions in the block
#if SMP_COUNT_MEMORY_ALLOCATIONS
for (size_t ArrayIndex = 0; ArrayIndex < this->GlobalDUChains.ChainsByName.size(); ++ArrayIndex) {
SMPDefUseChainCount += this->GlobalDUChains.ChainsByName.at(ArrayIndex).GetSize();
}
#endif
if (DebugFlag)
SMP_msg("Exiting CreateGlobalChains()\n");
return;
} // end of SMPBasicBlock::CreateGlobalChains()
#endif
// Create local DEF-USE chains and renumber all references to all names in LocalNames.
void SMPBasicBlock::SSALocalRenumber(void) {
bool DebugFlag = false;
#if 0
DebugFlag |= (0 == strcmp(".init_proc", this->MyFunc->GetFuncName()));
#endif
size_t NumLocals = this->LocalNames.size();
size_t LocalIndex;
vector<int> SSAIndex;
// Initialize SSAIndex and DUChain values for each local name.
set<op_t, LessOp>::iterator NameIter;
if (DebugFlag)
SMP_msg("LocalNames size: %zu\n", NumLocals);
#if STARS_BUILD_DEF_USE_CHAINS
this->LocalDUChains.ChainsByName.clear();
this->LocalDUChains.ChainsByName.reserve(NumLocals);
#endif
op_t TempOp = InitOp;
#if STARS_BUILD_DEF_USE_CHAINS
SMPDUChainArray Temp(TempOp, this->GetFirstAddr() - 1);
if (DebugFlag)
SMP_msg("Initializing ChainsByName.\n");
this->LocalDUChains.ChainsByName.assign(NumLocals, Temp);
for (NameIter = this->LocalNames.begin(); NameIter != this->LocalNames.end(); ++NameIter) {
LocalIndex = (size_t) ExtractGlobalIndex(*NameIter);
SSAIndex.push_back(-1); // init SSA indices to -1; first DEF will make it 0
// Set the local name for each DU chain array.
if (LocalIndex > this->LocalDUChains.ChainsByName.size())
SMP_msg("FATAL ERROR: LocalIndex %zu out of bounds in SSALocalRenumber.\n", LocalIndex);
if (DebugFlag)
SMP_msg("Setting name for LocalIndex = %zu\n", LocalIndex);
this->LocalDUChains.ChainsByName.at(LocalIndex).SetName(*NameIter, this->GetFirstAddr() - 1);
}
#else
for (NameIter = this->LocalNames.begin(); NameIter != this->LocalNames.end(); ++NameIter) {
LocalIndex = (size_t) ExtractGlobalIndex(*NameIter);
SSAIndex.push_back(-1); // init SSA indices to -1; first DEF will make it 0
}
#endif
// Iterate through all instructions in the block. For each DEF of a local name,
// set a new SSA index and start a new DU chain. For each USE of a local name,
// set the current SSA index for that name and add the instruction to the DU
// chain.
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator CurrUse, CurrDef;
set<op_t, LessOp>::iterator UseNameIter, DefNameIter;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
size_t NameIndex;
// USEs get referenced logically before DEFs, so start with them.
CurrUse = CurrInst->GetFirstUse();
while (CurrUse != CurrInst->GetLastUse()) {
op_t UseOp = CurrUse->GetOp();
UseNameIter = this->LocalNames.find(UseOp);
if (UseNameIter != this->LocalNames.end()) {
// Found USE of a local name.
NameIndex = ExtractGlobalIndex(*UseNameIter);
if (NameIndex > SSAIndex.size())
SMP_msg("FATAL ERROR: NameIndex %zu out of range in SSALocalRenumber.\n", NameIndex);
int SSANum = SSAIndex.at(NameIndex);
// Update the SSA subscript in the DEF-USE list for the instruction.
#if SMP_DEBUG_DATAFLOW
if (DebugFlag) {
SMP_msg("Setting SSANum to %d for local NameIndex %d\n", SSANum, NameIndex);
SMP_msg("Addr %x USE operand: ", CurrInst->GetAddr());
PrintOneOperand(UseOp, 0, -1);
SMP_msg("\n");
}
#endif
CurrUse = CurrInst->SetUseSSA(UseOp, SSANum);
#if STARS_BUILD_DEF_USE_CHAINS
if (SSANum >= 0) { // skip USE before DEF names
if ((size_t) SSANum > this->LocalDUChains.ChainsByName.at(NameIndex).GetSize())
SMP_msg("FATAL ERROR: SSANum %d out of range in SSALocalRenumber.\n", SSANum);
// Push address of USE instruction onto the DEF-USE chain for this SSANum.
this->LocalDUChains.ChainsByName.at(NameIndex).PushUse(SSANum, CurrInst->GetAddr());
}
#endif
}
++CurrUse;
} // end for all USEs in the instruction.
// Now do the DEFs.
CurrDef = CurrInst->GetFirstDef();
while (CurrDef != CurrInst->GetLastDef()) {
op_t DefOp = CurrDef->GetOp();
DefNameIter = this->LocalNames.find(DefOp);
if (DefNameIter != this->LocalNames.end()) {
// Found DEF of a local name.
NameIndex = ExtractGlobalIndex(*DefNameIter);
if (NameIndex > SSAIndex.size())
SMP_msg("ERROR: DEF NameIndex %zu out of range in SSALocalRenumber.\n", NameIndex);
++SSAIndex[NameIndex]; // move up to next SSA subscript number
int SSANum = SSAIndex.at(NameIndex);
// Put new SSA number into DEF list entry in the instruction.
CurrDef = CurrInst->SetDefSSA(DefOp, SSANum);
#if STARS_BUILD_DEF_USE_CHAINS
// Before the push_back() call, we should have # chains equal to new SSANum
assert(SSANum == (int) this->LocalDUChains.ChainsByName.at(NameIndex).GetSize());
#endif
SetGlobalIndex(&DefOp, NameIndex);
#if STARS_BUILD_DEF_USE_CHAINS
// Set up a new DU chain and push it onto the vector of DU chains for this
// local name. Push the DEF onto the list (it will be the first reference
// on the list, because the list was newly created).
SMPDefUseChain TempDefChain(DefOp, CurrInst->GetAddr() - this->GetFirstAddr() + 1);
this->LocalDUChains.ChainsByName.at(NameIndex).PushChain(TempDefChain);
#endif
}
++CurrDef;
} // end for all DEFs in the instruction
} // end for all instructions in the block
#if STARS_BUILD_DEF_USE_CHAINS
#if SMP_COUNT_MEMORY_ALLOCATIONS
for (size_t ArrayIndex = 0; ArrayIndex < this->LocalDUChains.ChainsByName.size(); ++ArrayIndex) {
SMPDefUseChainCount += this->LocalDUChains.ChainsByName.at(ArrayIndex).GetSize();
}
#endif
#endif
if (DebugFlag)
SMP_msg("Exiting SSALocalRenumber()\n");
return;
} // end of SMPBasicBlock::SSALocalRenumber()
// Determine if block is loop tail, also set loop header flag for dominating back-edge successor.
bool SMPBasicBlock::FindLoopHeadsAndTails(void) {
bool LoopTail = false;
list<SMPBasicBlock *>::iterator SuccIter;
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
int SuccBlockNum = (*SuccIter)->GetNumber();
if (this->GetFunc()->DoesBlockDominateBlock(SuccBlockNum, this->GetNumber())) {
LoopTail = true;
this->SetLoopTailBlock();
(*SuccIter)->SetLoopHeaderBlock();
this->LoopHeaderNumber = (*SuccIter)->GetNumber();
break; // should only be able to have one back edge to a loop header
}
}
return LoopTail;
} // end of SMPBasicBlock::FindLoopHeadsAndTails()
// Free memory for reaching defs sets after they are no longer needed.
void SMPBasicBlock::FreeReachingDefsMemory(void) {
this->ReachesInSet.clear();
this->ReachesOutSet.clear();
this->DownExposedDefnSet.clear();
return;
} // end of SMPBasicBlock::FreeReachingDefsMemory()
// Free SSA data structures that are no longer needed when all SSA numbers have
// been recorded in DEFs and USEs.
void SMPBasicBlock::FreeSSAMemory(void) {
this->DomFrontier.clear();
#if SMP_SHRINK_TO_FIT
std::set<int>(this->DomFrontier).swap(this->DomFrontier);
#endif
return;
} // end of SMPBasicBlock::FreeSSAMemory()
// After type inference, before annotation emission, free memory that is no
// longer needed (i.e. after loop 4 in SMPProgram::Analyze()).
void SMPBasicBlock::FreeUnusedMemory4(void) {
this->LiveInSet.clear();
#if 0 // PhiFunctions, LiveOutSet, Successors and AddrInstMap are used in SMPInstr::EmitIntegerErrorAnnotations()
this->KillSet.clear();
this->LiveOutSet.clear();
this->Predecessors.clear();
this->Successors.clear();
this->PhiFunctions.clear();
this->AddrInstMap.clear();
#endif
this->UpExposedSet.clear();
#if SMP_SHRINK_TO_FIT
std::set<op_t, LessOp>(this->LiveInSet).swap(this->LiveInSet);
std::set<op_t, LessOp>(this->UpExposedSet).swap(this->UpExposedSet);
#if 0
std::set<op_t, LessOp>(this->KillSet).swap(this->KillSet);
std::set<op_t, LessOp>(this->LiveInSet).swap(this->LiveOutSet);
std::set<SMPPhiFunction, LessPhi>(this->PhiFunctions).swap(this->PhiFunctions);
std::map<ea_t, size_t>(this->AddrInstMap).swap(this->AddrInstMap);
std::list<SMPBasicBlock *>(this->Predecessors).swap(this->Predecessors);
std::list<SMPBasicBlock *>(this->Successors).swap(this->Successors);
#endif
#endif
return;
} // end of SMPBasicBlock::FreeUnusedMemory4()
// Find the local Def-Use chain index for the given DefOp with given SSA index.
unsigned int SMPBasicBlock::GetLocalDUIndex(op_t DefOp, int SSANum) {
unsigned int RegIndex = 0;
set<op_t, LessOp>::iterator NameIter;
NameIter = this->LocalNames.find(DefOp);
if (NameIter == this->LocalNames.end()) {
SMP_msg("ERROR: local DEF name not in LocalNames: ");
PrintOperand(DefOp);
SMP_msg("\n");
assert(NameIter != this->LocalNames.end()); // abort
}
else {
// DefOp is in the LocalNames, as expected
RegIndex = ExtractGlobalIndex(*NameIter);
assert(0 <= SSANum);
#if STARS_BUILD_DEF_USE_CHAINS
assert(SSANum < (int) this->GetNumLocalChains(RegIndex, false));
#endif
}
return RegIndex;
} // end of SMPBasicBlock::GetLocalDUIndex()
// Find the global Def-Use chain index for the given DefOp with given address.
unsigned int SMPBasicBlock::GetGlobalDUIndex(op_t DefOp, ea_t DefAddr) {
unsigned int RegIndex = 0;
set<op_t, LessOp>::iterator NameIter;
NameIter = this->MyFunc->FindGlobalName(DefOp);
if (NameIter == this->MyFunc->GetLastGlobalName()) {
SMP_msg("ERROR: global DEF name at %lx not in GlobalNames: ", (unsigned long) DefAddr);
PrintOperand(DefOp);
SMP_msg("\n");
assert(NameIter != this->MyFunc->GetLastGlobalName()); // abort
}
else {
// DefOp is in the GlobalNames, as expected
RegIndex = ExtractGlobalIndex(*NameIter);
}
return RegIndex;
} // end of SMPBasicBlock::GetGlobalDUIndex()
#if STARS_BUILD_DEF_USE_CHAINS
// Any global DU chains for DefOp?
bool SMPBasicBlock::HasGlobalDUChain(op_t DefOp, ea_t DefAddr) {
unsigned int DUIndex = this->GetGlobalDUIndex(DefOp, DefAddr);
size_t NumChains = this->GetNumLocalChains(DUIndex, true);
return (0 < NumChains);
}
// Any global DU chains for DUIndex?
bool SMPBasicBlock::IsGlobalReferenced(unsigned int DUIndex) {
size_t NumChains = this->GetNumLocalChains(DUIndex, true);
return (0 < NumChains);
}
#endif
#if STARS_BUILD_DEF_USE_CHAINS
// For the local Def-Use chain for DefOp/SSANum, return the IndWrite flag.
bool SMPBasicBlock::GetLocalDUChainIndWrite(op_t DefOp, int SSANum) {
unsigned int DUIndex = this->GetLocalDUIndex(DefOp, SSANum);
return this->LocalDUChains.ChainsByName.at(DUIndex).HasIndirectWrite(SSANum);
}
// For the global Def-Use chain for DefOp at DefAddr, return the IndWrite flag.
bool SMPBasicBlock::GetGlobalDUChainIndWrite(op_t DefOp, ea_t DefAddr) {
unsigned int DUIndex = this->GetGlobalDUIndex(DefOp, DefAddr);
size_t chain;
size_t NumChains = this->GetNumLocalChains(DUIndex, true);
for (chain = 0; chain < NumChains; ++chain) {
if (DefAddr == this->GetFirstDefAddr(DUIndex, chain, true)) {
// Found the chain with matching DefAddr.
return this->GlobalDUChains.ChainsByName.at(DUIndex).HasIndirectWrite(chain);
}
}
return false; // not found; pass-through case, global not def or use in block
} // end of SMPBasicBlock::GetGlobalDUChainIndWrite()
// Is DU-chain at DefAddr the last one for global DefOp?
bool SMPBasicBlock::IsLastGlobalChain(op_t DefOp, ea_t DefAddr) {
unsigned int DUIndex = this->GetGlobalDUIndex(DefOp, DefAddr);
size_t LastIndex = this->GetNumLocalChains(DUIndex, true) - 1;
ea_t LastDefAddr = this->GetFirstDefAddr(DUIndex, LastIndex, true);
return (DefAddr == LastDefAddr);
} // end of SMPBasicBlock::IsLastGlobalChain()
#endif
// MemDefOp starting at InstIter has DU chain overlapping an indirect mem write
bool SMPBasicBlock::HasUseAfterIndWrite(op_t MemDefOp, vector<SMPInstr *>::iterator InstIter, bool &IndWriteSeen, bool &ReDef) {
IndWriteSeen = false;
ReDef = false;
bool FoundIndirectWrite = false;
set<DefOrUse, LessDefUse>::iterator UseIter;
while (InstIter != this->GetLastInst()) {
SMPInstr *TempInst = (*InstIter);
if (TempInst->FindDef(MemDefOp) != TempInst->GetLastDef()) {
// Re-DEF before indirect write.
ReDef = true;
return false;
}
else if (FoundIndirectWrite) {
UseIter = TempInst->FindUse(MemDefOp);
if (UseIter != TempInst->GetLastUse()) {
// USEd after indirect write.
return true;
}
}
else if (TempInst->HasIndirectMemoryWrite()) {
// Indirect write before re-DEF.
FoundIndirectWrite = true;
IndWriteSeen = true;
}
++InstIter;
}
// No re-DEF, no use after indirect write.
return false;
} // end of SMPBasicBlock::HasUseAfterIndWrite()
// If branch at block end is signed/unsigned, propagate to operands that set flags before it.
void SMPBasicBlock::MarkBranchSignedness(void) {
unsigned short SignMask;
set<DefOrUse, LessDefUse>::iterator UseIter;
op_t UseOp = InitOp;
ea_t DefAddr; // for flags USE in branch
int SSANum; // for flags USE in branch
bool LocalFlags; // is flags register a local name?
vector<SMPInstr *>::reverse_iterator InstRevIter;
InstRevIter = this->GetRevInstBegin(); // Any conditional branch would be last instruction
SMPInstr *LastInst = (*InstRevIter);
if (LastInst->MDIsUnsignedBranch()) {
if (this->IsBranchSignednessUnreliable()) {
return;
}
SignMask = FG_MASK_UNSIGNED;
}
else if (LastInst->MDIsSignedBranch()) {
SignMask = FG_MASK_SIGNED;
}
else
return; // Last instruction is not a signed or unsigned branch.
// Find the flags USE.
UseOp.type = o_reg; // set up a dummy op for searching
UseOp.reg = X86_FLAGS_REG;
UseIter = LastInst->FindUse(UseOp);
assert(UseIter != LastInst->GetLastUse());
UseOp = UseIter->GetOp(); // get full info in all fields
SSANum = UseIter->GetSSANum();
LocalFlags = this->IsLocalName(UseOp);
DefAddr = this->GetDefAddrFromUseAddr(UseOp, LastInst->GetAddr(), SSANum, LocalFlags);
// Pass DefAddr to recursive helper function.
this->PropagateBranchSignedness(DefAddr, UseOp, SignMask);
return;
} // end of SMPBasicBlock::MarkBranchSignedness()
// For the DefAddr of the SearchOp, propagate SignMask to all DEFs and USEs in the
// instruction or Phi function indicated by DefAddr.
// Currently, the DefAddr initially will be an instruction that defined the flags that were used in a signed or
// unsigned branch instruction, and the SearchOp will be the flags register. Upon recursion, the DefAddr
// and SearchOp will change as we backtrack up the signedness propagation chain.
// We recurse on all USEs until we encounter memory operands, also terminating the recursion as
// soon as we see an instruction other than a move, compare, or test.
void SMPBasicBlock::PropagateBranchSignedness(ea_t DefAddr, op_t SearchOp, unsigned short SignMask) {
SMPInstr *DefInst;
SMPBasicBlock *DefBlock;
set<DefOrUse, LessDefUse>::iterator UseIter;
set<DefOrUse, LessDefUse>::iterator DefIter;
int DefHashValue, UseHashValue;
ea_t PhiUseDefAddr; // for a Phi USE, where was it DEFed?
ea_t UseDefAddr; // for an instruction USE, where was it DEFed?
bool LocalDef = this->IsLocalName(SearchOp);
if (SearchOp.type == o_reg)
CanonicalizeOpnd(SearchOp);
else
return; // Limit to registers for now
if (DefAddr < this->MyFunc->GetNumBlocks()) { // found in Phi DEF; DefAddr is block #
// We need to propagate the SignMask to the Phi DEF, and then to the Phi USEs, and
// then we need to propagate the SignMask to the DEF of each Phi USE. It is possible
// that a Phi USE has its DEF in another block's Phi function, so this might recurse.
size_t BlockNum = (size_t) DefAddr;
if (IsMemOperand(SearchOp))
return; // end recursion
DefBlock = this->MyFunc->GetBlockByNum(BlockNum);
set<SMPPhiFunction, LessPhi>::iterator PhiIter = DefBlock->FindPhi(SearchOp);
assert(PhiIter != DefBlock->GetLastPhi());
int SSANum = PhiIter->GetDefSSANum();
DefHashValue = HashGlobalNameAndSSA(SearchOp, SSANum);
this->MyFunc->UpdateDefSignMiscInfo(DefHashValue, SignMask);
size_t UseIndex, UseLimit;
UseLimit = PhiIter->GetPhiListSize();
for (UseIndex = 0; UseIndex < UseLimit; ++UseIndex) {
int UseSSANum = PhiIter->GetUseSSANum(UseIndex);
UseHashValue = HashGlobalNameAndSSA(SearchOp, UseSSANum);
// Avoid propagation and recursion if no change will be made.
unsigned short OldSignInfo = this->MyFunc->GetUseSignMiscInfo(UseHashValue);
if (OldSignInfo != (OldSignInfo | SignMask)) { // sign info will change
this->MyFunc->UpdateUseSignMiscInfo(UseHashValue, SignMask);
PhiUseDefAddr = this->MyFunc->GetGlobalDefAddr(SearchOp, UseSSANum);
assert(BADADDR != PhiUseDefAddr);
if (PhiUseDefAddr < this->MyFunc->GetNumBlocks()) {
// DEF of current Phi USE is in another Phi function.
DefBlock = this->MyFunc->GetBlockByNum((size_t) PhiUseDefAddr);
}
else { // DEF is in an instruction.
DefBlock = this->MyFunc->GetBlockFromInstAddr(PhiUseDefAddr);
}
if (PhiUseDefAddr != DefAddr) { // Don't recurse infinitely
DefBlock->PropagateBranchSignedness(PhiUseDefAddr, SearchOp, SignMask); // recurse
}
}
}
}
else { // DEF must be in an instruction
if (LocalDef) { // DEF must be in a local instruction
DefInst = this->FindInstr(DefAddr);
}
else { // DEF might be in any block in the function
DefBlock = this->MyFunc->GetBlockFromInstAddr(DefAddr);
// DefBlock must be good, else GetBlockFromInstAddr() would assert.
DefInst = DefBlock->FindInstr(DefAddr);
}
// We sometimes have a compiler idiom in which a comparison is made between a signed char and
// an ASCII value, and then an unsigned branch is taken. We don't want to propagate UNSIGNED
// in this case, and we are unsure what signedness is truly present, so we just return.
if ((FG_MASK_UNSIGNED == SignMask) && (DefInst->MDComparesImmedASCII())) {
return;
}
// If the DEF is from a call instruction, we only want to propagate the sign to the DEF
// itself and stop the recursion. The other register USEs and DEFs of the call are unrelated
// to the SearchOp DEF, unlike arithmetic instructions.
if (DefInst->GetDataFlowType() >= JUMP) {
DefIter = DefInst->FindDef(SearchOp);
assert(DefIter != DefInst->GetLastDef());
DefHashValue = HashGlobalNameAndSSA(SearchOp, DefIter->GetSSANum());
if (LocalDef) {
this->UpdateDefSignMiscInfo(DefHashValue, SignMask);
}
else {
this->MyFunc->UpdateDefSignMiscInfo(DefHashValue, SignMask);
}
return;
}
// Now we should have a good DefInst for the Inst that DEFs SearchOp.
// Loop through the DEFs and USEs in this Inst and OR in the SignMask for register operands.
for (DefIter = DefInst->GetFirstDef(); DefIter != DefInst->GetLastDef(); ++DefIter) {
op_t DefOp = DefIter->GetOp();
if (DefOp.type == o_reg) {
CanonicalizeOpnd(DefOp);
DefHashValue = HashGlobalNameAndSSA(DefOp, DefIter->GetSSANum());
if ((LocalDef && this->IsLocalName(DefOp))
|| (!LocalDef && DefBlock->IsLocalName(DefOp))) {
// DefOp is local to a block, must use block-local maps.
if (LocalDef) { // still within current block
this->UpdateDefSignMiscInfo(DefHashValue, SignMask);
}
else { // DEF in another block; use DefBlock
DefBlock->UpdateDefSignMiscInfo(DefHashValue, SignMask);
}
}
else { // DefOp is global, use SMPFunction global maps.
this->MyFunc->UpdateDefSignMiscInfo(DefHashValue, SignMask);
}
}
} // end for all DEFs
// We don't want to propagate to USEs of instructions that load from non-stack memory. All of the
// uses are either memory locations or just addressing registers.
bool ReadsMemory = DefInst->HasSourceMemoryOperand();
if (ReadsMemory) {
if (DefInst->HasIndirectMemoryRead()
|| (!(DefInst->IsLoadFromStack()) && (DefInst->GetOptType() == 3))) {
// Either a load that is not from the stack, or an indirect access to memory.
return; // No USEs we can propagate through
}
}
#if STARS_MINIMIZE_UNSIGNED_BRANCH_PROPAGATION
// Now we propagate to the USEs of the instruction. However, we need to beware of
// propagating too much UNSIGNEDNESS, as we sometimes have mixed-mode arithmetic
// and lea instructions can add SIGNED and UNSIGNED to produce UNSIGNED, e.g.:
// lea edi,[eax+ebx]
// Just because EDI is UNSIGNED does not mean that both EAX and EBX are UNSIGNED.
// Perhaps EAX is UNSIGNED and EBX is SIGNED, or vice versa.
if (DefInst->MDIsLoadEffectiveAddressInstr()) {
// Se if we have more than one non-flags register USE.
size_t RegUseCount = 0;
for (UseIter = DefInst->GetFirstUse(); UseIter != DefInst->GetLastUse(); ++UseIter) {
op_t UseOp = UseIter->GetOp();
if ((UseOp.type == o_reg) && ((!ReadsMemory) || (DefInst->IsNonAddressReg(UseOp)))) { // don't want addressing registers
if (!(UseOp.is_reg(X86_FLAGS_REG))) {
++RegUseCount;
}
}
}
if (RegUseCount > 1) {
return;
}
}
#endif
// A USE in the instruction that DEFed the flags used in our original condition branch
// could be local to the block containing the instruction, else it is a global name.
// We always want to update the sign info of the USE. Propagation to the DEF of that USE
// will happen only if the instruction is a simple move, compare, or test (for now).
// NOTE: We might try to propagate to DEFs of registers by arithmetic instructions later.
#if 1
bool PropagateThroughUses = DefInst->MDPropagateUseUpFromBranch();
#else
bool PropagateThroughUses = false;
#endif
ea_t UseDefAddr = BADADDR;
for (UseIter = DefInst->GetFirstUse(); UseIter != DefInst->GetLastUse(); ++UseIter) {
op_t UseOp = UseIter->GetOp();
if ((UseOp.type == o_reg) && ((!ReadsMemory) || (DefInst->IsNonAddressReg(UseOp)))) { // don't want addressing registers
#if 0 // USEs should already be canonicalized
CanonicalizeOpnd(UseOp);
#endif
if (UseOp.is_reg(X86_FLAGS_REG)) {
// don't need to propagate to flags after initial call to this method
continue; // save time
}
int UseSSANum = UseIter->GetSSANum();
bool LocalUseOp;
if (LocalDef) {
LocalUseOp = this->IsLocalName(UseOp);
}
else {
LocalUseOp = DefBlock->IsLocalName(UseOp);
}
UseHashValue = HashGlobalNameAndSSA(UseOp, UseSSANum);
if (LocalDef) {
if (LocalUseOp) {// USE must be in a local instruction
this->UpdateUseSignMiscInfo(UseHashValue, SignMask);
}
else { // USE is global name
this->MyFunc->UpdateUseSignMiscInfo(UseHashValue, SignMask);
}
}
else if (LocalUseOp) { // USE is local to DEF block
DefBlock->UpdateUseSignMiscInfo(UseHashValue, SignMask);
}
else { // USE is global name
this->MyFunc->UpdateUseSignMiscInfo(UseHashValue, SignMask);
}
if (PropagateThroughUses) {
// For this opcode, we propagate through register USEs to their DEFs.
if (LocalDef) {
UseDefAddr = this->GetDefAddrFromUseAddr(UseOp, DefInst->GetAddr(), UseSSANum, LocalUseOp);
this->PropagateBranchSignedness(UseDefAddr, UseOp, SignMask); // recurse
}
else { // recurse through the DEF block
UseDefAddr = DefBlock->GetDefAddrFromUseAddr(UseOp, DefInst->GetAddr(), UseSSANum, LocalUseOp);
DefBlock->PropagateBranchSignedness(UseDefAddr, UseOp, SignMask); // recurse
}
}
}
else if (MDIsDirectStackAccessOpnd(UseOp, this->MyFunc->UsesFramePointer())) {
// Arithmetic or load using the stack as a source operand. We need to update
// our stack frame FG info sign inferences, in case we have some
// code that never does signed/unsigned loads from this stack location but uses it
// as a source operand for arithmetic or regular loads.
if (PropagateThroughUses && this->GetFunc()->HasGoodFGStackTable()
&& (!this->GetFunc()->IsInOutgoingArgsRegion(UseOp))) {
struct FineGrainedInfo StackFG;
bool success = this->GetFunc()->MDGetFGStackLocInfo(DefInst->GetAddr(), UseOp, StackFG);
assert(success);
if (0 == (StackFG.SignMiscInfo & FG_MASK_SIGNEDNESS_BITS)) {
// Stack operand has no signedness info. Time to give it some.
StackFG.SignMiscInfo |= SignMask;
success = this->GetFunc()->MDUpdateFGStackLocInfo(DefInst->GetAddr(), UseOp, StackFG);
assert(success);
// success => an update occurred
}
}
}
} // end for all USEs
} // end if (Phi DEF) else ...
return;
} // end of SMPBasicBlock::PropagateBranchSignedness()
// propagate DEF signedness to USE if USE has no signedness info.
bool SMPBasicBlock::PropagateDEFSignedness(void) {
bool changed = false;
map<int, struct FineGrainedInfo>::iterator UseFGIter, DefFGIter;
for (UseFGIter = this->LocalUseFGInfoBySSA.begin(); UseFGIter != this->LocalUseFGInfoBySSA.end(); ++UseFGIter) {
struct FineGrainedInfo UseFG = UseFGIter->second;
if (0 == (UseFG.SignMiscInfo & FG_MASK_SIGNEDNESS_BITS)) {
// No signedness info. Propagate any signedness info from DEF.
int UseHashValue = UseFGIter->first;
unsigned short DefSignMask = this->GetDefSignMiscInfo(UseHashValue);
DefSignMask &= FG_MASK_SIGNEDNESS_BITS;
if (0 != DefSignMask) {
// DEF has signedness info.
UseFGIter->second.SignMiscInfo |= DefSignMask;
changed = true;
}
}
}
// See if we have DEF signedness info for DEFs with no corresponding USE map entries.
for (DefFGIter = this->LocalDefFGInfoBySSA.begin(); DefFGIter != this->LocalDefFGInfoBySSA.end(); ++DefFGIter) {
struct FineGrainedInfo DefFG = DefFGIter->second;
unsigned short DefSignMask = (DefFG.SignMiscInfo & FG_MASK_SIGNEDNESS_BITS);
if (0 != DefSignMask) {
// Has signedness info. See if USE has no entry.
int DefHashValue = DefFGIter->first;
UseFGIter = this->LocalUseFGInfoBySSA.find(DefHashValue);
if (UseFGIter == this->LocalUseFGInfoBySSA.end()) {
this->UpdateUseSignMiscInfo(DefHashValue, DefSignMask);
changed = true;
}
}
}
return changed;
} // end of SMPBasicBlock::PropagateDEFSignedness()
// backtrack from CallAddr and mark unsigned args based on bitset
void SMPBasicBlock::MarkUnsignedArgs(ea_t CallAddr, unsigned int ArgPosBits) {
vector<SMPInstr *>::reverse_iterator RevInstIter;
unsigned int UnsignedArgCount = CountBitsSet(ArgPosBits);
unsigned int UnsignedArgsFound = 0;
for (RevInstIter = this->GetRevInstBegin(); RevInstIter != this->GetRevInstEnd(); ++RevInstIter) {
SMPInstr *CurrInst = (*RevInstIter);
ea_t InstAddr = CurrInst->GetAddr();
if (InstAddr < CallAddr) {
SMPitype FlowType = CurrInst->GetDataFlowType();
if ((FlowType == CALL) || (FlowType == INDIR_CALL)) {
// We have reached a call before the one we care about. Done.
break;
}
size_t ArgumentNumber;
if (CurrInst->MDIsArgumentPass(ArgumentNumber)) {
if (0 != (ArgPosBits & (1 << ArgumentNumber))) {
// ArgumentNumber matches a bit set in ArgPosBits.
CurrInst->SetUnsignedArg();
++UnsignedArgsFound;
if (UnsignedArgsFound >= UnsignedArgCount) {
break; // found them all
}
}
}
}
}
return;
} // end of SMPBasicBlock::MarkUnsignedArgs()
// Find the stack target of a call to memset() and the size in bytes of the memset() region.
// If the memset() target is not on the stack, return false. If the
// size of the memset() region is not a constant, we also return false.
bool SMPBasicBlock::AnalyzeMemSet(ea_t MemSetAddr, op_t &MemSetTarget, size_t &MemSetSize, int &StackOffset, bool &FPRelativeTarget) {
set<DefOrUse, LessDefUse>::iterator UseIter;
op_t DefOp, UseOp, UltimateSourceOp;
ea_t InstAddr;
int UseSSANum;
bool FoundTarget = false, FoundSize = false;
bool UseFP = this->GetFunc()->UsesFramePointer();
bool DummyFPRelative = false; // don't care about this for the size argument to memset(), which is o_imm anyway
vector<SMPInstr *>::reverse_iterator InstRevIter;
sval_t CurrentDelta;
assert(MemSetAddr >= this->FirstAddr);
MemSetTarget = InitOp;
MemSetSize = 0;
// The MemSetTarget will be moved into [ESP+0] and the size will be moved
// into [ESP+8]. The value being copied into each byte will be moved into
// [ESP+4], which we do not care about. We will move backwards through the block until
// we find the MemSetAddr, then we will trace the def-use SSA chain back to its
// source for each argument to memset() that we care about.
// NOTE: [ESP+0], [ESP+4], etc., do not look like that any more, because stack ops have
// been normalized.
InstRevIter = this->GetRevInstBegin();
SMPInstr *CurrInst = (*InstRevIter);
InstAddr = CurrInst->GetAddr();
while ((InstAddr > MemSetAddr) && (InstRevIter != this->GetRevInstEnd())) {
++InstRevIter; // move backwards through block by incrementing the reverse iterator.
CurrInst = (*InstRevIter);
InstAddr = CurrInst->GetAddr();
}
if (InstAddr != MemSetAddr) {
SMP_msg("ERROR: Memset not found at MemSetAddr %lx\n", (unsigned long) MemSetAddr);
return false;
}
// Keep iterating backwards from MemSetAddr, searching for DEFs of [ESP] and [ESP+8].
++InstRevIter; // move backwards through block by incrementing the reverse iterator.
while (InstRevIter != this->GetRevInstEnd()) {
CurrInst = (*InstRevIter);
InstAddr = CurrInst->GetAddr();
if (CurrInst->HasDestMemoryOperand()) {
DefOp = CurrInst->MDGetMemDefOp();
// We want to know if DefOp is ESP-relative, so we do not want to find
// an EBP-relative DefOp, as arguments are not passed EBP-relative. So,
// regardless of whether we actually use EBP as a frame pointer in this
// function, we will pass FALSE as the second argument of this next query.
// NOTE: There are no more EBP-relative DEFs after normalization, anyway.
if (MDIsDirectStackAccessOpnd(DefOp, false)) {
// Found write to stack, ESP-relative. Determine if it is [ESP+0] or [ESP+8].
int BaseReg, IndexReg;
ushort ScaleFactor;
ea_t offset;
MDExtractAddressFields(DefOp, BaseReg, IndexReg, ScaleFactor, offset);
// We don't want scaled or indexed accesses to the stack; cannot analyze easily.
if ((R_none == IndexReg) && (0 == ScaleFactor)) {
assert(BaseReg == MD_STACK_POINTER_REG);
int SignedOffset = (int) offset; // IDA Pro has signedness problem to fix here.
CurrentDelta = CurrInst->GetStackPtrOffset();
SignedOffset -= (int) CurrentDelta; // undo normalization of stack offset
if (0 == SignedOffset) {
UseOp = CurrInst->GetMoveSource();
if (o_reg == UseOp.type) {
CanonicalizeOpnd(UseOp);
}
if (o_void == UseOp.type) {
SMP_msg("ERROR: No move source at %lx within AnalyzeMemSet().\n", (unsigned long) InstAddr);
break;
}
else {
UseIter = CurrInst->FindUse(UseOp);
assert(UseIter != CurrInst->GetLastUse());
UseSSANum = UseIter->GetSSANum();
if (CurrInst->TraceUltimateMoveSource(UseOp, UseSSANum, UltimateSourceOp, FPRelativeTarget)) {
if (MDIsDirectStackAccessOpnd(UltimateSourceOp, UseFP)) {
// memset() has a stack location as its target. Extract info from
// UltimateSourceOp.
MDExtractAddressFields(UltimateSourceOp, BaseReg, IndexReg, ScaleFactor, offset);
if ((R_none != IndexReg) || (0 != ScaleFactor)) {
break; // cannot make use of complex stack loc expression
}
else {
MemSetTarget = UltimateSourceOp;
StackOffset = (int) offset; // NOTE: this is a normalized offset
FoundTarget = true; // success on argument #1
if (FoundSize) break; // nothing left to find
}
}
else {
// Found ultimate source of argument #1, but not a stack operand.
break; // return false
}
}
else { // could not find ultimate source of argument #1
break; // time to return false
}
}
}
else if (8 == SignedOffset) {
UseOp = CurrInst->GetMoveSource();
if (o_reg == UseOp.type) {
CanonicalizeOpnd(UseOp);
}
if (o_void == UseOp.type) {
SMP_msg("ERROR: No move source at %lx within AnalyzeMemSet().\n",
(unsigned long) InstAddr);
break;
}
else {
UseIter = CurrInst->FindUse(UseOp);
assert(UseIter != CurrInst->GetLastUse());
UseSSANum = UseIter->GetSSANum();
if (CurrInst->TraceUltimateMoveSource(UseOp, UseSSANum, UltimateSourceOp, DummyFPRelative)) {
if (o_imm != UltimateSourceOp.type) {
break; // return false if cannot find an immediate value for argument #3
}
else {
uval_t ImmVal;
ImmVal = UseOp.value;
MemSetSize = (size_t) ImmVal;
FoundSize = true;
if (FoundTarget) break; // nothing left to find
}
}
}
} // end if ((0 == SignedOffset) || (8 == SignedOffset))
}
} // end if MDIsStackAccessOpnd(DefOp, false)
} // end if CurrInst->HasDestMemoryOperand()
++InstRevIter; // move backwards through block by incrementing the reverse iterator.
} // end while we have not reached the block Instrs.rend()
return (FoundTarget && FoundSize);
} // end of SMPBasicBlock::AnalyzeMemset()
#if STARS_BUILD_DEF_USE_CHAINS
// For the newly defined type DefType for DefOp at instruction DefAddr, propagate the
// type to all USEs in the local SSA chain for the DEF. If any USE types change,
// return true.
bool SMPBasicBlock::PropagateLocalDefType(op_t DefOp, SMPOperandType DefType, ea_t DefAddr, int SSANum, bool IsMemOp) {
bool changed = false;
bool SafeFunc = (this->MyFunc) && this->MyFunc->IsSafe();
bool DebugFlag = false;
#if SMP_DEBUG_OPTIMIZATIONS
DebugFlag |= (0 == strcmp("memset", this->MyFunc->GetFuncName()));
#endif
set<op_t, LessOp>::iterator NameIter;
if (DebugFlag) {
SMP_msg("PropagateLocalDefType for DefType %d at %x ", DefType, DefAddr);
PrintOperand(DefOp);
SMP_msg("\n");
}
unsigned int RegIndex = this->GetLocalDUIndex(DefOp, SSANum);
ea_t StartAddr = this->GetFirstDefAddr(RegIndex, SSANum, false);
assert(DefAddr == StartAddr);
ea_t LastAddr = this->GetLastUseAddr(RegIndex, SSANum, false);
if (BADADDR == LastAddr)
return false; // DEF had no USEs, so no propagation
set<DefOrUse, LessDefUse>::iterator CurrUse;
vector<SMPInstr *>::iterator InstIter;
// Go through the instructions in the block and find the instructions between StartAddr
// and LastAddr that have USEs of DefOp. These will all have SSANum, based on the
// local du-chain, so it does not have to be checked. If any USE in the chain has
// a type other than DefType, change it to DefType and set changed to true.
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
ea_t CurrAddr = CurrInst->GetAddr();
if (CurrAddr > LastAddr)
break;
if (CurrAddr > StartAddr) {
#if SMP_VERBOSE_ALIAS_DETECTION
if (IsMemOp && (CurrInst->HasIndirectMemoryWrite())) {
SMP_msg("CAUTION: Indirect memory write in MemOp chain.\n");
SMP_msg("CAUTION: at %x ChainStart: %x ChainEnd: %x \n",
CurrAddr, StartAddr, LastAddr);
#if 0
if (!SafeFunc) {
SMP_msg("Local type propagation terminated in unsafe func %s\n",
this->MyFunc->GetFuncName());
break;
}
#endif
}
#endif
CurrUse = CurrInst->FindUse(DefOp);
if (CurrUse != CurrInst->GetLastUse()) { // found a USE in the chain
ushort InstOpcode = CurrInst->GetCmd().itype;
SMPOperandType UseType = CurrUse->GetType();
if (UseType == UNINIT) {
assert(SSANum == CurrUse->GetSSANum());
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else if (DefType != UseType) {
// See lengthy explanation in PropagateGlobalDefType().
if (IsRefinedDataPtr(DefType) && (IsEqType(POINTER, UseType))) {
#if SMP_VERBOSE_POINTER_REFINEMENT
SMP_msg("Refining POINTER to %d at %x %s for USE:", DefType,
CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
#endif
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else if (IsDataPtr(DefType) && IsNumeric(UseType)
&& ((InstOpcode == NN_adc) || (InstOpcode == NN_sbb))) {
SMP_msg("ADC/SBB: Refining NUMERIC to %d at %x %s for USE:", DefType,
CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else {
;
#if SMP_DEBUG_OPTIMIZATIONS
SMP_msg("WARNING: Not overriding type %d to %d at %x %s for USE:", UseType,
DefType, CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
#endif
}
}
}
}
} // end for all instructions
return changed;
} // end of SMPBasicBlock::PropagateLocalDefType()
#else
// For the newly defined type DefType for DefOp at instruction DefAddr, propagate the
// type to all USEs in the local SSA chain for the DEF. If any USE types change,
// return true.
bool SMPBasicBlock::PropagateLocalDefType(op_t DefOp, SMPOperandType DefType, ea_t DefAddr, int SSANum, bool IsMemOp) {
bool changed = false;
bool SafeFunc = (this->MyFunc) && this->MyFunc->IsSafe();
bool DebugFlag = false;
#if SMP_DEBUG_OPTIMIZATIONS
DebugFlag |= (0 == strcmp("memset", this->MyFunc->GetFuncName()));
#endif
if (DebugFlag) {
SMP_msg("PropagateLocalDefType for DefType %d at %lx ",
DefType, (unsigned long) DefAddr);
PrintOperand(DefOp);
SMP_msg("\n");
}
set<DefOrUse, LessDefUse>::iterator CurrUse;
vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(DefAddr);
// Go through the instructions in the block and find the instructions that have USEs of DefOp/SSANum.
// If any USE in the chain has a type other than DefType, change it to DefType and set changed to true.
++InstIter;
while (InstIter != this->GetLastInst()) {
SMPInstr *CurrInst = (*InstIter);
++InstIter;
ea_t CurrAddr = CurrInst->GetAddr();
#if SMP_VERBOSE_ALIAS_DETECTION
if (IsMemOp && (CurrInst->HasIndirectMemoryWrite())) {
SMP_msg("CAUTION: Indirect memory write in MemOp chain.\n");
SMP_msg("CAUTION: at %lx ChainStart: %lx ChainEnd: %lx \n",
(unsigned long) CurrAddr, (unsigned long) StartAddr, (unsigned long) LastAddr);
#if 0
if (!SafeFunc) {
SMP_msg("Local type propagation terminated in unsafe func %s\n",
this->MyFunc->GetFuncName());
break;
}
#endif
}
#endif
CurrUse = CurrInst->FindUse(DefOp);
if (CurrUse != CurrInst->GetLastUse()) { // found a USE in the chain
ushort InstOpcode = CurrInst->GetCmd().itype;
SMPOperandType UseType = CurrUse->GetType();
if (UseType == UNINIT) {
assert(SSANum == CurrUse->GetSSANum());
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else if (DefType != UseType) {
// See lengthy explanation of propagation rules in PropagateGlobalDefType().
if (IsRefinedDataPtr(DefType) && (IsEqType(POINTER, UseType))) {
#if SMP_VERBOSE_POINTER_REFINEMENT
SMP_msg("Refining POINTER to %d at %lx %s for USE:", DefType,
(unsigned long) CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
#endif
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else if (IsDataPtr(DefType) && IsNumeric(UseType)
&& ((InstOpcode == NN_adc) || (InstOpcode == NN_sbb))) {
SMP_msg("ADC/SBB: Refining NUMERIC to %d at %lx %s for USE:", DefType,
(unsigned long) CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else {
;
#if SMP_DEBUG_OPTIMIZATIONS
SMP_msg("WARNING: Not overriding type %d to %d at %lx %s for USE:", UseType,
DefType, (unsigned long) CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
#endif
}
}
}
if (CurrInst->FindDef(DefOp) != CurrInst->GetLastDef()) {
// Instruction redefines DefOp. Terminate.
break;
}
} // end for all instructions
return changed;
} // end of SMPBasicBlock::PropagateLocalDefType()
#endif
// Propagate the DefType of the DEF in DefOp with SSANum to all USEs. DefOp is a global
// name, so the propagation will have to recurse into successor blocks, check their
// phi functions for occurrences of DefOp, etc.
// Return true if any USEs have their types changed.
bool SMPBasicBlock::PropagateGlobalDefType(op_t DefOp, SMPOperandType DefType, int SSANum, bool IsMemOp) {
bool changed = false;
bool FoundPhiDef = false;
bool SafeFunc = (this->MyFunc) && this->MyFunc->IsSafe();
bool DebugFlag = false;
#if SMP_DEBUG_OPTIMIZATIONS
DebugFlag |= (0 == strcmp("__strtod_internal", this->MyFunc->GetFuncName()));
#endif
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator CurrUse;
set<DefOrUse, LessDefUse>::iterator CurrDef;
SMPOperandType UseType;
// Use the Processed flag to avoid infinite recursion.
if (this->IsProcessed())
return false;
else
this->SetProcessed(true);
if (DebugFlag) {
SMP_msg("PropagateGlobalDefType: DefType %d SSANum %d ", DefType, SSANum);
PrintOperand(DefOp);
SMP_msg("\n");
}
// When we can traverse all paths of the global DEF-USE chains for this
// DefOp, we can be sure there is no aliasing. Until then, we must
// be more conservative on global MemOp propagation than for locals.
if (IsMemOp && (!SafeFunc))
return false;
// This might be a recursive invocation, so the DefOp might be in the Phi functions.
set<SMPPhiFunction, LessPhi>::iterator CurrPhi = this->FindPhi(DefOp);
if (CurrPhi != this->GetLastPhi()) { // Found a corresponding phi function
if (DebugFlag) SMP_msg("Found Phi for DefOp\n");
// If SSANum matches the DEF in the Phi function, then we are being
// called by InferPhiDefType() and we should proceed to process
// the instructions in the block.
if (SSANum != CurrPhi->GetDefSSANum()) { // not DEF, so find USE
if (DebugFlag) SMP_msg("Phi was a USE\n");
// Now, find the SSANum entry in the phi arguments (USEs)
bool FoundUse = false;
size_t PhiIndex;
for (PhiIndex = 0; PhiIndex < CurrPhi->GetPhiListSize(); ++PhiIndex) {
if (SSANum == CurrPhi->GetUseSSANum(PhiIndex)) {
FoundUse = true;
if (DebugFlag) SMP_msg("Found the phi USE at index %zu\n", PhiIndex);
if (UNINIT == CurrPhi->GetUseType(PhiIndex)) {
changed = this->SetPhiUseType(DefOp, PhiIndex, DefType);
assert(changed);
if (DebugFlag) SMP_msg("Changed the phi USE type\n");
}
#if 1
break; // **!!** COULD BE MULTIPLE USES HERE
#endif
}
}
if (!FoundUse) {
// Not actually a problem. E.g. if we find an inst: add eax,4 that
// uses eax SSA #7 and DEFs eax SSA #8, we will call this function
// to propagate the type of SSA #8. There could be a phi function
// at the top of this block that DEFs eax SSA #7 from earlier USEs
// of eax. We will not find eax SSA #8 in that phi function, so we
// pass down to the code below to process all instructions.
;
#if 0
SMP_msg("ERROR: Failed to find Phi use of SSA %d in block %d for: ", SSANum,
this->GetNumber());
PrintOperand(DefOp);
SMP_msg("\n");
#endif
}
else
return changed; // end the recursion; phi function does not permit DefOp
// with SSANum to be referenced on this path again
} // end if DefOp and SSANum are not the phi function DEF
else {
FoundPhiDef = true;
}
} // end if we found a phi function for DefOp
// If not in the Phi functions, it could be in the instructions for the block.
bool FoundUse = false;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
#if 0
if (IsMemOp && (CurrInst->HasIndirectMemoryWrite())) {
if (!SafeFunc) {
SMP_msg("Global type propagation terminated in unsafe func %s\n",
this->MyFunc->GetFuncName());
return changed;
}
}
#endif
CurrUse = CurrInst->FindUse(DefOp);
if ((CurrUse == CurrInst->GetLastUse()) || (SSANum != CurrUse->GetSSANum())) {
if (FoundUse) {
// If we have already gone past the DEF and at least one use,
// another DEF will indicate that the original DEF-USE chain is
// finished. In that case, we can save a lot of time by not processing
// any more instructions and recursing into successor blocks, because
// the original DEF is now dead.
CurrDef = CurrInst->FindDef(DefOp);
if ((CurrDef != CurrInst->GetLastDef()) && (SSANum != CurrDef->GetSSANum())) {
return changed;
}
else {
continue;
}
}
else {
continue;
}
}
// If we reach this point, we have found a use with the same SSA number.
FoundUse = true;
UseType = CurrUse->GetType();
ushort InstOpcode = CurrInst->GetCmd().itype;
if (DebugFlag) {
SMP_msg("Found USE with same SSANum at %lx : %s\n",
(unsigned long) CurrInst->GetAddr(), CurrInst->GetDisasm());
}
if (UNINIT == UseType) {
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else if (DefType != UseType) {
// Weird. USE already has a type, but it is not the DEF type.
// If we are refining a POINTER to a particular pointer type, fine.
// We don't want to change NUMERIC to something else, however,
// because it is possible to perform inherently NUMERIC operations
// on pointer types, e.g. def a pointer, use it as pointer, then
// perform hash function computations on it. Those computations
// (shift, xor, etc.) should truly remain NUMERIC.
//
// EXCEPTION: We need to propagate pointer types to USEs within
// subtract-with-borrow and add-with-carry instructions. This is
// because of phase ordering issues. E.g. sbb ecx,3 could have
// the DEF type inferred to be NUMERIC based on its later uses,
// but we still need to know if the USE of ecx was POINTER. This
// is a special case in which the sbb or adc instruction changes
// the type of the register. We need to observe this type change
// when we emit annotations, so that we emit an annotation to
// force the DEF metadata to NUMERIC rather than an annotation
// that squashes the instruction and leaves ecx with type POINTER.
// SMPInstr::InferOperatorType() will propagate NUMERIC from
// the SMP_SUBTRACT_BORROW operator to register ecx if ecx still
// had type UNINIT. We need to reset the USE of ecx to POINTER
// if we later discover that ecx came into the instruction with
// type POINTER.
if (IsRefinedDataPtr(DefType) && (IsEqType(POINTER, UseType))) {
#if SMP_VERBOSE_POINTER_REFINEMENT
SMP_msg("Refining POINTER to %d at %lx %s for USE:", DefType,
(unsigned long) CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
#endif
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else if (IsDataPtr(DefType) && IsNumeric(UseType)
&& ((InstOpcode == NN_adc) || (InstOpcode == NN_sbb))) {
SMP_msg("ADC/SBB: Refining NUMERIC to %d at %lx %s for USE:", DefType,
(unsigned long) CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
CurrUse = CurrInst->SetUseType(DefOp, DefType);
assert(CurrUse != CurrInst->GetLastUse()); // found USE
changed = true;
}
else {
;
#if SMP_DEBUG_OPTIMIZATIONS
SMP_msg("WARNING: Not overriding type %d to %d at %x %s for USE:", UseType,
DefType, CurrInst->GetAddr(), CurrInst->GetDisasm());
CurrUse->Dump();
SMP_msg("\n");
#endif
}
}
} // end for all instructions in the block
// We recurse into all successor blocks looking for more USEs. We know that there
// cannot be more USEs if the global name DefOp is not LiveOut from this block, so
// we can just return in that case.
if (this->LiveOutSet.end() == LiveOutSet.find(DefOp)) // not LiveOut
return changed;
// Only recurse into successors that have DefOp in their LiveIn set. The others
// will not have Phi functions for DefOp, because we constructed fully pruned SSA
// form, nor will they have USEs of this SSANum.
list<SMPBasicBlock *>::iterator SuccIter;
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
if ((*SuccIter)->IsLiveIn(DefOp)) {
changed |= (*SuccIter)->PropagateGlobalDefType(DefOp, DefType, SSANum, IsMemOp);
}
}
return changed;
} // end of SMPBasicBlock::PropagateGlobalDefType()
// Propagate the metadata Status for UseOp/SSANum to its local DEF.
// Return true if successful.
bool SMPBasicBlock::PropagateLocalMetadata(op_t UseOp, SMPMetadataType Status, int SSANum, ea_t UseAddr) {
bool changed = false;
set<op_t, LessOp>::iterator NameIter;
NameIter = this->FindLocalName(UseOp);
if (this->GetLastLocalName() == NameIter) {
return false;
}
assert(0 <= SSANum);
ea_t DefAddr = this->GetDefAddrFromUseAddr(UseOp, UseAddr, SSANum, true);
if ((DefAddr == BADADDR) || (DefAddr < this->GetFirstAddr())) {
return false;
}
// Find the instruction at DefAddr
vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(DefAddr);
SMPInstr *CurrInst = (*InstIter);
set<DefOrUse, LessDefUse>::iterator CurrDef, CurrUse, NextUse;
CurrDef = CurrInst->FindDef(UseOp);
assert(CurrDef != CurrInst->GetLastDef());
assert(SSANum == CurrDef->GetSSANum());
// Set the new metadata status.
if (Status != CurrDef->GetMetadataStatus()) {
CurrDef = CurrInst->SetDefMetadata(UseOp, Status);
changed = (CurrDef != CurrInst->GetLastDef());
// If source operand was memory, we have two cases.
// (1) The instruction could be a load, in which
// case we should simply terminate the
// propagation, because the prior DEF of a memory
// location is always considered live metadata
// already, and we do not want to propagate liveness
// to the address regs in the USE list.
// EXCEPTION: For safe funcs, we propagate liveness
// for stack locations.
// (2) We could have an arithmetic operation such
// as reg := reg arithop memsrc. In this case, we
// still do not want to propagate through the memsrc,
// but the register is both DEF and USE and we need
// to propagate through the register.
if (CurrInst->HasSourceMemoryOperand()) {
if (this->MyFunc->IsSafe()) {
bool UseFP = this->MyFunc->UsesFramePointer();
op_t MemSrcOp = CurrInst->MDGetMemUseOp();
assert(o_void != MemSrcOp.type);
if (MDIsStackAccessOpnd(MemSrcOp, UseFP)) {
// We have a SafeFunc stack access. This is
// the EXCEPTION case where we want to
// propagate metadata liveness for a memory
// location.
CurrUse = CurrInst->FindUse(MemSrcOp);
assert(CurrUse != CurrInst->GetLastUse());
if (this->MyFunc->IsGlobalName(MemSrcOp)) {
changed |= this->MyFunc->PropagateGlobalMetadata(MemSrcOp,
Status, CurrUse->GetSSANum(), DefAddr);
}
else {
changed |= this->PropagateLocalMetadata(MemSrcOp,
Status, CurrUse->GetSSANum(), DefAddr);
}
} // end if stack access operand
} // end if SafeFunc
if (3 == CurrInst->GetOptType()) { // move inst
return changed; // address regs are not live metadata
}
else if ((5 == CurrInst->GetOptType())
|| (NN_and == CurrInst->GetCmd().itype)
|| (NN_or == CurrInst->GetCmd().itype)
|| (NN_xor == CurrInst->GetCmd().itype)) {
// add, subtract, and, or with memsrc
// Find the DEF reg in the USE list.
CurrUse = CurrInst->FindUse(UseOp);
assert(CurrUse != CurrInst->GetLastUse());
changed |= this->PropagateLocalMetadata(UseOp,
Status, CurrUse->GetSSANum(), DefAddr);
return changed;
}
} // end if memory source
// Now, propagate the metadata status to all the
// non-memory, non-flags-reg, non-special-reg
// (i.e. regular registers) USEs.
CurrUse = CurrInst->GetFirstUse();
while (CurrUse != CurrInst->GetLastUse()) {
NextUse = CurrUse;
++NextUse;
op_t UseOp2 = CurrUse->GetOp();
// NOTE: **!!** To be less conservative, we
// should propagate less for exchange category
// instructions.
if ((UseOp2.type == o_reg) && (!MDIsStackOrFramePointerReg(UseOp2, this->MyFunc->UsesFramePointer()))
&& (!UseOp2.is_reg(X86_FLAGS_REG))) {
if (this->MyFunc->IsGlobalName(UseOp2)) {
changed |= this->MyFunc->PropagateGlobalMetadata(UseOp2,
Status, CurrUse->GetSSANum(), DefAddr);
}
else {
changed |= this->PropagateLocalMetadata(UseOp2,
Status, CurrUse->GetSSANum(), DefAddr);
}
}
CurrUse = NextUse;
} // end while all USEs
} // end if Status != CurrDef status
return changed;
} // end of SMPBasicBlock::PropagateLocalMetadata()
// For the UNINIT type DEF DefOp at instruction DefAddr, see if all its USEs have
// a single type. If so, set the DEF to that type and return true, else return false.
bool SMPBasicBlock::InferLocalDefType(op_t DefOp, unsigned int LocIndex, ea_t DefAddr) {
bool changed = false;
bool DebugFlag = false;
#if SMP_DEBUG_OPTIMIZATIONS
DebugFlag |= (0 == strcmp("weightadj", this->MyFunc->GetFuncName()));
#endif
if (DebugFlag) {
SMP_msg("InferLocalDefType at %lx ", (unsigned long) DefAddr);
PrintOperand(DefOp);
SMP_msg("\n");
}
vector<SMPInstr *>::iterator InstIter;
vector<SMPInstr *>::iterator DefInstIter = this->GetInstIterFromAddr(DefAddr);
set<DefOrUse, LessDefUse>::iterator CurrDef;
SMPInstr *DefInst = (*DefInstIter);
CurrDef = DefInst->FindDef(DefOp);
if (CurrDef == DefInst->GetLastDef()) {
SMP_msg("ERROR: DEF at %lx not found in DEF list by InferLocalDefType for DefOp: ", (unsigned long) DefAddr);
PrintOperand(DefOp);
SMP_msg("\n");
return false;
}
int SSANum = CurrDef->GetSSANum();
assert(0 <= SSANum);
set<DefOrUse, LessDefUse>::iterator CurrUse;
// Go through the instructions in the block and find the instructions between DefAddr
// and the last inst that have USEs of DefOp/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;
bool FoundUninit = false;
bool FoundNumeric = false;
bool FoundPointer = false;
bool FoundUnknown = false;
SMPOperandType DefType = CurrDef->GetType();
SMPOperandType PtrType = UNINIT;
SMPOperandType UseType = UNINIT;
InstIter = DefInstIter;
++InstIter;
for ( ; InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
ea_t CurrAddr = CurrInst->GetAddr();
CurrUse = CurrInst->FindUse(DefOp);
if (CurrUse != CurrInst->GetLastUse()) { // found a USE in the chain
if (!FirstUseSeen)
FirstUseSeen = true;
UseType = CurrUse->GetType();
if (UNINIT == UseType)
FoundUninit = true;
else if (IsNumeric(UseType))
FoundNumeric = true;
else if (IsUnknown(UseType))
FoundUnknown = true;
else if (IsDataPtr(UseType)) {
if (FoundPointer) {
if (IsNotEqType(PtrType, UseType)) {
;
#if SMP_DEBUG_OPTIMIZATIONS
SMP_msg("WARNING: Differing ptr types in local chain:");
SMP_msg(" Prev: %d Current: %d %s\n", PtrType, UseType,
CurrInst->GetDisasm());
#endif
}
PtrType = POINTER;
}
else {
FoundPointer = true;
PtrType = UseType;
}
}
}
if (CurrInst->FindDef(DefOp) != CurrInst->GetLastDef()) {
// Redefined. Chain is finished.
break;
}
} // end for all instructions
if (FirstUseSeen) {
// See if we have a consistent type.
// If we see any definite POINTER uses, we must set the DEF
// to type POINTER or a refinement of it.
if (FoundPointer)
UseType = PtrType;
else if (FoundNumeric && !FoundUninit && !FoundUnknown)
UseType = NUMERIC;
else
return false; // no POINTER, but no consistent type
if (!IsEqType(DefType, UseType)) {
if (DebugFlag) SMP_msg("Inferring local DEF of type %d\n", UseType);
CurrDef = DefInst->SetDefType(DefOp, UseType);
changed = true;
if (FoundPointer && FoundUninit) {
// We will propagate PtrType to the UNINIT elements of
// the DEF-USE chain.
bool IsMemOp = (o_reg != DefOp.type);
changed |= this->PropagateLocalDefType(DefOp, PtrType, DefAddr,
CurrDef->GetSSANum(), IsMemOp);
}
}
}
return changed;
} // end of SMPBasicBlock::InferLocalDefType()
void SMPBasicBlock::InferGlobalDefType(op_t DefOp, int SSANum, ea_t DefAddr, bool &FoundNumeric, bool &FoundPointer,
bool &FoundUnknown, bool &FoundUninit, SMPOperandType &PtrType) {
// Avoid infinite recursion
if (this->IsProcessed())
return;
else
this->SetProcessed(true);
bool DefEscapes = true;
vector<SMPInstr *>::iterator InstIter;
assert(0 <= SSANum);
set<DefOrUse, LessDefUse>::iterator CurrUse, CurrDef;
// Go through all instructions in the block and find the instructions
// that have USEs of DefOp with SSANum. Record the results in the
// boolean in-out arguments.
SMPOperandType UseType = UNINIT;
SMPOperandType DefType = UNINIT;
if (BADADDR == DefAddr) { // DEF is USEd (and thus re-DEFed) in a Phi function
DefEscapes = false;
set<SMPPhiFunction, LessPhi>::iterator UsePhi;
UsePhi = this->FindPhi(DefOp);
if (UsePhi != this->GetLastPhi()) {
// Found phi function for DefOp. See if we can find a USE
// with USE SSANum corresponding to our DEF SSANum.
DefType = UsePhi->GetDefType();
for (size_t PhiIndex = 0; PhiIndex < UsePhi->GetPhiListSize(); ++PhiIndex) {
if (UsePhi->GetUseSSANum(PhiIndex) == SSANum) {
// We have a Phi USE that matches our DEF.
UseType = UsePhi->GetUseType(PhiIndex);
FoundNumeric |= (IsNumeric(UseType));
FoundUnknown |= (IsUnknown(UseType));
FoundUninit |= (IsEqType(UNINIT, UseType));
if (IsDataPtr(UseType)) {
if (FoundPointer) {
if (IsNotEqType(PtrType, UseType)) {
PtrType = POINTER;
}
}
else {
FoundPointer = true;
PtrType = UseType;
}
}
} // end if matched SSA #
} // end for all Phi USEs
} // end if found matching Phi function for DefOp
}
else { // DEF is in an instruction in a previous block !!!!****!!!! Why not current block?
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
CurrDef = CurrInst->FindDef(DefOp);
if (CurrDef != CurrInst->GetLastDef()) {
// Found re-DEF of DefOp.
DefEscapes = false;
}
CurrUse = CurrInst->FindUse(DefOp);
if (CurrUse != CurrInst->GetLastUse()) { // found a USE of DefOp
if (CurrUse->GetSSANum() == SSANum) { // matched SSA number
UseType = CurrUse->GetType();
FoundNumeric |= (IsNumeric(UseType));
FoundUnknown |= (IsUnknown(UseType));
FoundUninit |= (IsEqType(UNINIT, UseType));
if (IsDataPtr(UseType)) {
if (FoundPointer) {
if (IsNotEqType(PtrType, UseType)) {
// Have seen two different pointer types/subtypes
PtrType = POINTER;
}
}
else {
FoundPointer = true;
PtrType = UseType;
}
}
} // end if matched SSA #
} // end if found a USE of DefOp
} // end for all instructions
}
if (DefEscapes) { // did not find re-def
DefEscapes = this->IsLiveOut(DefOp);
}
if (DefEscapes) { // Need to recurse into successor blocks
list<SMPBasicBlock *>::iterator SuccIter;
ea_t TempAddr;
set<SMPPhiFunction, LessPhi>::iterator PhiIter;
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
SMPBasicBlock *CurrBlock = (*SuccIter);
PhiIter = CurrBlock->FindPhi(DefOp);
TempAddr = DefAddr;
if (PhiIter != CurrBlock->GetLastPhi()) {
TempAddr = BADADDR; // signals that DefOp will get re-DEFed in a Phi function.
}
else if (BADADDR == TempAddr) { // was BADADDR coming in to this function
// We don't want to pass BADADDR down the recursion chain, because it will be interpreted
// by each successor block to mean that DefOp was a Phi USE that got re-DEFed in a Phi function
// within itself. Pass the dummy address that indicates LiveIn to the block.
TempAddr = CurrBlock->GetFirstAddr() - 1;
}
// Should we screen the recursive call below using CurrBlock->IsLiveIn(DefOp) for speed? !!!!****!!!!
CurrBlock->InferGlobalDefType(DefOp, SSANum, TempAddr, FoundNumeric, FoundPointer, FoundUnknown, FoundUninit, PtrType);
}
}
return;
} // end of SMPBasicBlock::InferGlobalDefType()
// Iterate over all phi functions, calling InferPhiDefType() for any Phi DEF whose
// type is still UNINIT.
// Return TRUE if any changes are made.
bool SMPBasicBlock::InferAllPhiDefTypes(void) {
bool changed = false;
bool NewChange;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi = this->GetFirstPhi();
while (CurrPhi != this->GetLastPhi()) {
if (UNINIT == CurrPhi->GetDefType()) {
CurrPhi = this->InferPhiDefType(CurrPhi, NewChange);
changed = (changed || NewChange);
if (NewChange) {
this->MyFunc->IncTypedPhiDefs();
}
else {
this->MyFunc->IncUntypedPhiDefs();
}
}
else {
this->MyFunc->IncTypedPhiDefs();
}
++CurrPhi;
}
return changed;
} // end of SMPBasicBlock::InferAllPhiDefTypes()
// If all USEs in a Phi function are set in agreement with each other, then infer
// the Phi DEF type is the same as the USEs type, set it, propagate it,
// and return true.
// Otherwise, if all USEs of the Phi DEF in the function have a common type,
// infer the Phi DEF type from them and return true.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::InferPhiDefType(set<SMPPhiFunction, LessPhi>::iterator DefPhi, bool &changed) {
changed = false;
bool SkipToBackInference = false;
bool PropagateChange = false;
set<SMPPhiFunction, LessPhi>::iterator UsePhi;
set<SMPPhiFunction, LessPhi>::iterator ReturnPhi = DefPhi;
SMPOperandType MeetType = UNINIT;
op_t DefOp = DefPhi->GetAnyOp();
int SSANum = DefPhi->GetDefSSANum();
bool SafeFunc = this->MyFunc->IsSafe();
bool IndirectOp = MDIsIndirectMemoryOpnd(DefOp, this->MyFunc->UsesFramePointer());
bool UnsafeOp = (IndirectOp || ((o_reg != DefOp.type) && (!SafeFunc)));
// Relax the UnsafeOp definition with alias analysis?
assert(UNINIT == DefPhi->GetDefType());
for (size_t index = 0; index < DefPhi->GetPhiListSize(); ++index) {
if (IsEqType(UNINIT, DefPhi->GetUseType(index))) {
SkipToBackInference = true;
break;
}
}
if (!SkipToBackInference) {
// Must have seen all non-UNINIT types if we reach this point.
MeetType = DefPhi->ConditionalMeetType();
if (IsNotEqType(UNKNOWN, MeetType)) {
// Don't infer UNKNOWN until conditional type propagation stage.
ReturnPhi = this->SetPhiDefType(DefOp, MeetType);
changed = true;
PropagateChange = true;
}
}
else if (!UnsafeOp) { // try back inference from USEs of Phi DEF
SMPOperandType DefType;
DefType = this->MyFunc->InferGlobalDefType(DefOp, SSANum, this, false, BADADDR);
if (IsNotEqType(UNINIT, DefType)) {
// Don't set changed, because there is no downward propagation
// to do. Instead, propagate only to UNINIT Phi USEs.
size_t limit = DefPhi->GetPhiListSize();
set<size_t> UseUpdates;
UseUpdates.clear();
for (size_t index = 0; index < limit; ++index) {
if (UNINIT == DefPhi->GetUseType(index)) {
UseUpdates.insert(index); // keep list needing update
}
}
set<size_t>::iterator UpIter;
for (UpIter = UseUpdates.begin(); UpIter != UseUpdates.end(); ++UpIter) {
this->SetPhiUseType(DefOp, *UpIter, DefType);
// NOTE: DefPhi iterator is stale after this update
}
ReturnPhi = this->SetPhiDefType(DefOp, DefType);
// We don't set PropagateChange to true for the back inference case,
// because there is no propagating to do.
changed = true;
}
}
// Propagate down to USEs of this DEF.
if (PropagateChange && !UnsafeOp) {
bool IsMemOp = (o_reg != DefOp.type);
this->MyFunc->ResetProcessedBlocks();
changed |= this->PropagateGlobalDefType(DefOp, MeetType, SSANum, IsMemOp);
}
return ReturnPhi;
} // end of SMPBasicBlock::InferPhiDefType()
#if STARS_BUILD_DEF_USE_CHAINS
size_t SMPBasicBlock::GetNumDUChains(bool GlobalName) const {
size_t NumChains;
if (GlobalName)
NumChains = this->GlobalDUChains.ChainsByName.size();
else
NumChains = this->LocalDUChains.ChainsByName.size();
return NumChains;
}
size_t SMPBasicBlock::GetNumLocalChains(unsigned int RegIndex, bool GlobalName) const {
size_t NumLocalChains;
if (GlobalName)
NumLocalChains = this->GlobalDUChains.ChainsByName.at(RegIndex).GetSize();
else
NumLocalChains = this->LocalDUChains.ChainsByName.at(RegIndex).GetSize();
return NumLocalChains;
}
// number of uses for RegIndex in ChainIndex in this block
size_t SMPBasicBlock::GetNumLocalUses(unsigned int RegIndex, size_t ChainIndex, bool GlobalName) const {
size_t NumLocalUses;
if (GlobalName)
NumLocalUses = this->GlobalDUChains.ChainsByName.at(RegIndex).GetNumUses(ChainIndex);
else
NumLocalUses = this->LocalDUChains.ChainsByName.at(RegIndex).GetNumUses(ChainIndex);
return NumLocalUses;
}
ea_t SMPBasicBlock::GetFirstDefAddr(unsigned int RegIndex, size_t ChainIndex, bool GlobalName) const {
size_t DefAddr;
if (GlobalName)
DefAddr = this->GlobalDUChains.ChainsByName.at(RegIndex).GetDef(ChainIndex);
else
DefAddr = this->LocalDUChains.ChainsByName.at(RegIndex).GetDef(ChainIndex);
return DefAddr;
}
ea_t SMPBasicBlock::GetLastUseAddr(unsigned int RegIndex, size_t ChainIndex, bool GlobalName) const {
size_t UseAddr;
if (GlobalName)
UseAddr = this->GlobalDUChains.ChainsByName.at(RegIndex).GetLastUse(ChainIndex);
else
UseAddr = this->LocalDUChains.ChainsByName.at(RegIndex).GetLastUse(ChainIndex);
return UseAddr;
}
//fetch USE addr #UseIndex from DU chain.
ea_t SMPBasicBlock::GetDUChainUse(unsigned int NameIndex, int SSANum, size_t UseIndex, bool GlobalName) const {
size_t UseAddr;
if (GlobalName)
UseAddr = this->GlobalDUChains.ChainsByName.at(NameIndex).GetUse(SSANum, UseIndex);
else
UseAddr = this->LocalDUChains.ChainsByName.at(NameIndex).GetUse(SSANum, UseIndex);
return UseAddr;
}
op_t SMPBasicBlock::GetDUName(unsigned int NameIndex, bool GlobalName) {
op_t ChainOp;
if (GlobalName)
ChainOp = this->GlobalDUChains.ChainsByName.at(NameIndex).GetName();
else
ChainOp = this->LocalDUChains.ChainsByName.at(NameIndex).GetName();
return ChainOp;
}
void SMPBasicBlock::SetIndWrite(unsigned int NameIndex, size_t ChainIndex, bool GlobalName, bool FlagValue) {
if (GlobalName)
this->GlobalDUChains.ChainsByName.at(NameIndex).SetIndWrite(ChainIndex, FlagValue);
else
this->LocalDUChains.ChainsByName.at(NameIndex).SetIndWrite(ChainIndex, FlagValue);
return;
}
#endif
// Is GlobalOp used anywhere in this block as a LiveIn value, including as a Phi USE?
bool SMPBasicBlock::IsGlobalNameUsedLiveIn(op_t GlobalOp) {
bool FoundInLiveInSet = (LiveInSet.end() != LiveInSet.find(GlobalOp));
bool OpUsed = FoundInLiveInSet;
if (FoundInLiveInSet) {
// exclude the pass-through case, in which the operand is LiveIn, LiveOut, but never killed or used.
bool FoundInUpExposedSet = (this->GetLastUpExposed() != this->UpExposedSet.find(GlobalOp));
OpUsed = FoundInUpExposedSet;
if (!OpUsed) {
// See if it is used as a Phi USE and is otherwise just passed through the block.
set<SMPPhiFunction, LessPhi>::iterator PhiIter = this->FindPhi(GlobalOp);
OpUsed = (PhiIter != this->GetLastPhi());
}
}
return OpUsed;
} // end of SMPBasicBlock::IsGlobalNameUsed()
// Extension of IsRegDead for Global names. Check and see if it overlaps with a DEF-USE chain
bool SMPBasicBlock::IsGlobalRegDead(ea_t InstAddr, op_t Operand, unsigned int RegIndex) {
bool FoundInLiveInSet = (LiveInSet.end() != LiveInSet.find(Operand));
bool FoundInLiveOutSet = (LiveOutSet.end() != LiveOutSet.find(Operand));
#if STARS_BUILD_DEF_USE_CHAINS
bool FoundInUpExposedSet = (this->GetLastUpExposed() != this->UpExposedSet.find(Operand));
size_t LocalChainIndex;
size_t LocalChainMax = this->GetNumLocalChains(RegIndex, true);
--LocalChainMax;
bool HasLocalChains = (0 < LocalChainMax);
#endif
bool FoundInKillSet = (KillSet.end() != KillSet.find(Operand));
bool DebugFlag = (0x804837b == InstAddr);
#if STARS_BUILD_DEF_USE_CHAINS
if (DebugFlag) {
SMP_msg("IsGlobalRegDead for %x : ", InstAddr);
PrintOperand(Operand);
SMP_msg("\nLiveIn: %d LiveOut: %d UpExposed: %d VarKilled: %d\n", FoundInLiveInSet,
FoundInLiveOutSet, FoundInUpExposedSet, FoundInKillSet);
}
if (DebugFlag) SMP_msg("A");
// If there are no local chains for this global name, then it is either the pass-through
// case (LiveIn, LiveOut, !UpExposed, !VarKilled) or it must be dead.
if (!HasLocalChains)
return (!FoundInLiveInSet);
#endif
if (DebugFlag) SMP_msg("A1");
// If it is Live-In and Live-Out and not in the kill set,
// it is live the whole time (either pass-through case or use-only case).
if (FoundInLiveInSet && FoundInLiveOutSet && !FoundInKillSet)
return false;
if (DebugFlag) SMP_msg("B");
// If it is not Live-In and not in the Kill set it is dead the whole time
if (!FoundInLiveInSet && !FoundInKillSet) {
// Must not have USEs, else it would be LiveIn. So, no DEFs, no USEs, not LiveIn: Dead.
assert(!FoundInLiveOutSet);
return true;
}
vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(InstAddr);
while (InstIter != this->GetLastInst()) {
SMPInstr *CurrInst = (*InstIter);
// Case 1: Not dead if reg is USE before it is a DEF.
if (CurrInst->FindUse(Operand) != CurrInst->GetLastUse()) {
return false;
}
// Case 2: Dead if DEF before USE.
if (CurrInst->FindDef(Operand) != CurrInst->GetLastDef()) {
return true;
}
++InstIter;
}
// Case 3: Reached end of block with no DEFs or USEs >=InstAddr. This is a global name,
// so it is dead if and only if it is not LiveOut. Does not really matter
// if it was DEFed or USEd before InstAddr.
return (!FoundInLiveOutSet);
#if STARS_BUILD_DEF_USE_CHAINS
if (DebugFlag) SMP_msg("C");
// If it is not in the UpExposed set and is in the Kill set, it is dead
// before the first def
if (!FoundInUpExposedSet && FoundInKillSet) {
ea_t StartAddr = this->GetFirstDefAddr(RegIndex, 0, true);
if ((BADADDR != StartAddr) && (InstAddr <= StartAddr))
return true;
}
if (DebugFlag) SMP_msg("D");
// If it is in the UpExposedSet, it is live until the last use of the first chain
if (FoundInUpExposedSet) {
ea_t LastAddr = this->GetLastUseAddr(RegIndex, 0, true);
if ((BADADDR != LastAddr) && (InstAddr <= LastAddr))
return false;
}
if (DebugFlag) SMP_msg("E");
// If it is not Live-Out, then it is dead after the last use
if (!FoundInLiveOutSet) {
ea_t LastAddr = this->GetLastUseAddr(RegIndex, LocalChainMax, true);
if ((BADADDR != LastAddr) && (InstAddr > LastAddr))
return true;
}
if (DebugFlag) SMP_msg("F");
//If it is LiveOut and it is in the Kill Set, it will be live after the last definition
if (FoundInLiveOutSet && FoundInKillSet) {
ea_t DefAddr = this->GetFirstDefAddr(RegIndex, LocalChainMax, true);
if ((BADADDR != DefAddr) && (DefAddr < InstAddr)) // **!!** <= or < ?
return false;
}
if (DebugFlag) SMP_msg("G");
// See if any DEF-USE chains overlap InstAddr's USE.
for (LocalChainIndex = 0; LocalChainIndex <= LocalChainMax; ++LocalChainIndex) {
// Need to check here to not break if this block does not have a def for this (LiveIn)
// Skip this check if it is UpExposed and this is the first chain
if (!FoundInUpExposedSet || LocalChainIndex > 0) {
ea_t StartAddr = this->GetFirstDefAddr(RegIndex, LocalChainIndex, true);
if (StartAddr >= InstAddr)
continue; // cannot overlap USE if DEF is after InstAddr
}
ea_t LastAddr = this->GetLastUseAddr(RegIndex, LocalChainIndex, true);
if (DebugFlag) SMP_msg(" LastAddr: %x\n", LastAddr);
if ((BADADDR != LastAddr) && (LastAddr >= InstAddr)) {
if (DebugFlag) SMP_msg("Ga");
return false;
}
}
if (DebugFlag) SMP_msg("H");
return true; // no DEF-USE chains overlapped the instrumentation point
#endif
} // end of SMPBasicBlock::IsGlobalRegDead()
// If no DEF-USE chains overlap the instrumentation point for InstAddr (which logically
// falls between the USEs of the instruction at InstAddr and its DEFs), for register RegIndex,
// then it is safe for the instrumentation to use that register without saving and
// restoring its value. Return true in this case, false if there is DEF-USE overlap.
bool SMPBasicBlock::IsRegDead(ea_t InstAddr, uint16 RegNo) {
// See if any DEF-USE chains overlap InstAddr's USEs.
vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(InstAddr);
op_t RegOp = InitOp;
RegOp.type = o_reg;
RegOp.reg = RegNo;
RegOp.dtyp = (*InstIter)->GetOperandDtypField();
while (InstIter != this->GetLastInst()) {
SMPInstr *CurrInst = (*InstIter);
// Case 1: Not dead if reg is USE before it is a DEF.
if (CurrInst->FindUse(RegOp) != CurrInst->GetLastUse()) {
return false;
}
// Case 2: Dead if DEF before USE.
if (CurrInst->FindDef(RegOp) != CurrInst->GetLastDef()) {
return true;
}
++InstIter;
}
// Case 3: Reached end of block with no DEFs or USEs. This is a local name,
// so it was dead at the original InstAddr.
return true;
} // end of SMPBasicBlock::IsRegDead()
// Mark the registers that are dead for each instruction in the block.
void SMPBasicBlock::MarkDeadRegs(void) {
bool DebugFlag = false;
#if 0
DebugFlag |= (0 == strcmp("_int_malloc", this->MyFunc->GetFuncName()));
#endif
set<op_t, LessOp>::iterator NameIter;
set<op_t, LessOp>::iterator FlagNameIter;
vector<SMPInstr *>::iterator InstIter;
op_t FlagsOp = InitOp;
FlagsOp.type = o_reg;
FlagsOp.reg = X86_FLAGS_REG;
FlagsOp.specflag1 = 0;
FlagsOp.specflag2 = 0;
bool GlobalFlags = this->MyFunc->IsGlobalName(FlagsOp);
if (GlobalFlags) {
#if 0
this->SetFlagsDeadAfterLastUse((this->LiveOutSet.find(FlagsOp) == this->LiveOutSet.end()));
#endif
this->SetFlagsDeadBeforeFirstKill(((this->UpExposedSet.find(FlagsOp) == this->GetLastUpExposed())
&& (this->KillSet.find(FlagsOp) != this->KillSet.end())));
FlagNameIter = this->MyFunc->FindGlobalName(FlagsOp);
}
else {
FlagNameIter = this->LocalNames.find(FlagsOp);
}
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
ea_t InstAddr = CurrInst->GetAddr();
DebugFlag = (0x804dafc == InstAddr);
if (DebugFlag) {
CurrInst->PrintOperands();
SMP_msg("\n");
}
// First, put EFLAGS at beginning of string if it is dead.
if (!GlobalFlags) {
if (FlagNameIter != this->LocalNames.end()) {
// EFLAGS is in the LocalNames
uint16 RegNo = FlagNameIter->reg;
unsigned int RegIndex = ExtractGlobalIndex(*FlagNameIter);
if (this->IsRegDead(InstAddr, RegNo)) {
CurrInst->SetRegDead((size_t) MD_FLAGS_REG);
}
}
else { // EFLAGS are not locally used, but not global either; they are dead here
CurrInst->SetRegDead((size_t) MD_FLAGS_REG);
}
}
else {
assert(FlagNameIter != this->MyFunc->GetLastGlobalName());
unsigned int RegIndex = ExtractGlobalIndex(*FlagNameIter);
bool newCatch = this->IsGlobalRegDead(InstAddr, FlagsOp, RegIndex);
if (newCatch)
CurrInst->SetRegDead((size_t) MD_FLAGS_REG);
}
// Now, process all other local regs and skip EFLAGS.
for (NameIter = this->LocalNames.begin(); NameIter != this->LocalNames.end(); ++NameIter) {
if (NameIter->type != o_reg)
continue;
// We never want to consider ESP to be available for instrumentation.
if (NameIter->is_reg(MD_STACK_POINTER_REG))
continue;
// Until we analyze interprocedural register use, it is safest to not
// use EBP for instrumentation. This could change with more analysis.
if (NameIter->is_reg(MD_FRAME_POINTER_REG))
continue;
unsigned int RegIndex = ExtractGlobalIndex(*NameIter);
uint16 RegNo = NameIter->reg;
if (RegNo == MD_FLAGS_REG) {
// We moved EFLAGS to the beginning, per annotations spec
continue;
}
if (this->IsRegDead(InstAddr, RegNo)) {
CurrInst->SetRegDead((size_t) RegNo);
}
} // end for all local names
// Now, process all other global regs and skip EFLAGS.
//SMP_msg(" Done. Analyzing global regs...");
size_t NumGlobals = this->MyFunc->NumGlobalNames();
if (NumGlobals > 0) {
for (NameIter = this->MyFunc->GetFirstGlobalName(); NameIter != this->MyFunc->GetLastGlobalName(); ++NameIter) {
op_t RegOp = InitOp;
RegOp.type = o_reg;
//SMP_msg(" i ");
//SMP_msg("%d", NameIter->type);
if (NameIter->type != o_reg)
continue;
//SMP_msg(" j ");
// We never want to consider ESP to be available for instrumentation.
if (NameIter->is_reg(MD_STACK_POINTER_REG))
continue;
//SMP_msg(" k ");
// Until we analyze interprocedural register use, it is safest to not
// use EBP for instrumentation. This could change with more analysis.
if (NameIter->is_reg(MD_FRAME_POINTER_REG))
continue;
//SMP_msg(" l ");
unsigned int RegIndex = ExtractGlobalIndex(*NameIter);
int RegNum = NameIter->reg;
if (RegNum == X86_FLAGS_REG) {
// We moved EFLAGS to the beginning, per annotations spec
continue;
}
//SMP_msg(" m ");
RegOp.reg = NameIter->reg;
RegOp.dtyp = CurrInst->GetOperandDtypField();
//SMP_msg("%i", RegOp.reg);
if (this->IsGlobalRegDead(InstAddr, RegOp, RegIndex)) {
CurrInst->SetRegDead((size_t) RegNum);
}
} // end for all global names
}
//SMP_msg("Done. Next instruction.\n");
} // end for all instructions
if (DebugFlag)
SMP_msg("Exiting MarkDeadRegs()\n");
return;
} // end of SMPBasicBlock::MarkDeadRegs()
#if STARS_BUILD_DEF_USE_CHAINS
// Does DefOp at DefAddr never get used?
bool SMPBasicBlock::IsDefDead(ea_t DefAddr, op_t DefOp) {
set<op_t, LessOp>::iterator LocalIter = this->LocalNames.find(DefOp);
bool LocalName = (LocalIter != this->LocalNames.end());
bool DefDead = false;
unsigned int DUIndex;
size_t NumChains;
if (LocalName) {
DUIndex = ExtractGlobalIndex(*LocalIter);
size_t SSAIndex;
assert(DUIndex < this->GetNumDUChains(false));
NumChains = this->GetNumLocalChains(DUIndex, false);
for (SSAIndex = 0; SSAIndex < NumChains; ++SSAIndex) {
if (DefAddr == this->GetFirstDefAddr(DUIndex, SSAIndex, false)) {
break;
}
}
assert(SSAIndex < NumChains); // found it
// If it has no uses, it is dead. Being a local name, there is no LiveOut possibility.
DefDead = (0 == this->GetNumLocalUses(DUIndex, SSAIndex, false));
}
else { // global name
DUIndex = this->GetGlobalDUIndex(DefOp, DefAddr);
NumChains = this->GetNumLocalChains(DUIndex, true);
assert(0 < NumChains);
bool FoundIndex = false;
size_t ChainIndex;
for (ChainIndex = 0; ChainIndex < NumChains; ++ChainIndex) {
if (DefAddr == this->GetFirstDefAddr(DUIndex, ChainIndex, true)) {
FoundIndex = true;
break;
}
}
assert(FoundIndex);
if (0 == this->GetNumLocalUses(DUIndex, ChainIndex, true)) {
// No uses in that chain. If it is not the last chain, then DefOp is redefined and this
// DEF is truly dead. If it is the last chain and DefOp is in the LiveOut set, then it
// is not dead.
if (ChainIndex == (NumChains - 1)) { // No uses, last chain
DefDead = (!(this->IsLiveOut(DefOp)));
}
else {
// No uses, not last chain.
DefDead = true;
}
}
}
return DefDead;
} // end of SMPBasicBlock::IsDefDead()
#else
// Does DefOp at DefAddr never get used?
bool SMPBasicBlock::IsDefDead(ea_t DefAddr, op_t DefOp) {
vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(DefAddr);
++InstIter; // start with next instruction
while (InstIter != this->GetLastInst()) {
SMPInstr *CurrInst = (*InstIter);
// Case 1: Not dead if reg is USE before it is a DEF.
if (CurrInst->FindUse(DefOp) != CurrInst->GetLastUse()) {
return false;
}
// Case 2: Dead if re-DEF before USE.
if (CurrInst->FindDef(DefOp) != CurrInst->GetLastDef()) {
return true;
}
++InstIter;
}
// Case 3: Reached end of block with no DEFs or USEs. If this is a local name,
// it was dead at the original DefAddr, else a global is dead if it is not LiveOut.
set<op_t, LessOp>::iterator LocalIter = this->LocalNames.find(DefOp);
bool LocalName = (LocalIter != this->LocalNames.end());
return (LocalName || (!(this->IsLiveOut(DefOp))));
} // end of SMPBasicBlock::IsDefDead()
#endif
// Return true if DefOp at DefAddr is used in or redefined by addition; pass back AdditionAddr
bool SMPBasicBlock::IsDefInvolvedInAddition(ea_t DefAddr, op_t DefOp, ea_t &AdditionAddr) {
set<op_t, LessOp>::iterator LocalIter = this->LocalNames.find(DefOp);
bool LocalName = (LocalIter != this->LocalNames.end());
unsigned int DUIndex;
size_t NumChains, NumUses, UseIndex;
bool LastChain = false;
bool UseFP = this->GetFunc()->UsesFramePointer();
vector<SMPInstr *>::iterator UseInstIter;
if (!MDIsDataFlowOpnd(DefOp, UseFP)) {
return false;
}
UseInstIter = this->GetInstIterFromAddr(DefAddr);
++UseInstIter;
while (UseInstIter != this->GetLastInst()) {
SMPInstr *UseInst = (*UseInstIter);
AdditionAddr = UseInst->GetAddr();
if (UseInst->FindUse(DefOp) != UseInst->GetLastUse()) {
if (UseInst->MDIsAddition()) {
// hash function value is accumulating in another DEF via addition.
return true;
}
else if (UseInst->MDIsMoveInstr() || UseInst->MDIsUnderflowingOpcode() || UseInst->MDIsLoadEffectiveAddressInstr()) {
// Copied to another location via move or subtraction; could reach addition in that location.
set<DefOrUse, LessDefUse>::iterator CopyDefIter = UseInst->GetFirstNonFlagsDef();
op_t CopyDefOp = CopyDefIter->GetOp();
ea_t CopyAdditionAddr;
if (this->IsDefInvolvedInAddition(UseInst->GetAddr(), CopyDefOp, CopyAdditionAddr)) {
AdditionAddr = CopyAdditionAddr;
return true;
}
}
}
if (UseInst->FindDef(DefOp) != UseInst->GetLastDef()) {
// re-DEF
return (UseInst->MDIsAddition());
}
++UseInstIter;
}
return false; // reached end of block without returning true or false above
#if STARS_BUILD_DEF_USE_CHAINS
if (LocalName) {
DUIndex = ExtractGlobalIndex(*LocalIter);
size_t SSAIndex;
assert(DUIndex < this->GetNumDUChains(false));
NumChains = this->GetNumLocalChains(DUIndex, false);
for (SSAIndex = 0; SSAIndex < NumChains; ++SSAIndex) {
if (DefAddr == this->GetFirstDefAddr(DUIndex, SSAIndex, false)) {
break;
}
}
assert(SSAIndex < NumChains); // found it
// If it has no uses, or is the last DEF, it is not part of an addition re-definition.
NumUses = this->GetNumLocalUses(DUIndex, SSAIndex, false);
LastChain = (SSAIndex == (NumChains - 1));
// Search for addition USEs.
for (UseIndex = 0; UseIndex < NumUses; ++UseIndex) {
AdditionAddr = this->GetDUChainUse(DUIndex, SSAIndex, UseIndex, false);
UseInstIter = this->GetInstIterFromAddr(AdditionAddr);
SMPInstr *UseInst = (*UseInstIter);
if (UseInst->MDIsAddition()) {
// hash function value is accumulating in another DEF via addition.
return true;
}
else if (UseInst->MDIsMoveInstr() || UseInst->MDIsUnderflowingOpcode() || UseInst->MDIsLoadEffectiveAddressInstr()) {
// Copied to another location via move or subtraction; could reach addition in that location.
set<DefOrUse, LessDefUse>::iterator CopyDefIter = UseInst->GetFirstNonFlagsDef();
op_t CopyDefOp = CopyDefIter->GetOp();
ea_t CopyAdditionAddr;
if (this->IsDefInvolvedInAddition(UseInst->GetAddr(), CopyDefOp, CopyAdditionAddr)) {
AdditionAddr = CopyAdditionAddr;
return true;
}
}
}
if ((0 == NumUses) || LastChain) {
return false;
}
// Get next DEF, see if it is an addition.
AdditionAddr = this->GetFirstDefAddr(DUIndex, SSAIndex + 1, false);
}
else {
DUIndex = this->GetGlobalDUIndex(DefOp, DefAddr);
NumChains = this->GetNumLocalChains(DUIndex, true);
assert(0 < NumChains);
bool FoundIndex = false;
size_t ChainIndex;
for (ChainIndex = 0; ChainIndex < NumChains; ++ChainIndex) {
if (DefAddr == this->GetFirstDefAddr(DUIndex, ChainIndex, true)) {
FoundIndex = true;
break;
}
}
assert(FoundIndex);
NumUses = this->GetNumLocalUses(DUIndex, ChainIndex, true);
LastChain = (ChainIndex == (NumChains - 1));
// Search for addition USEs.
for (UseIndex = 0; UseIndex < NumUses; ++UseIndex) {
AdditionAddr = this->GetDUChainUse(DUIndex, ChainIndex, UseIndex, true);
UseInstIter = this->GetInstIterFromAddr(AdditionAddr);
SMPInstr *UseInst = (*UseInstIter);
if (UseInst->MDIsAddition()) {
// hash function value is accumulating in another DEF via addition.
return true;
}
else if (UseInst->MDIsMoveInstr() || UseInst->MDIsUnderflowingOpcode() || UseInst->MDIsLoadEffectiveAddressInstr()) {
// Copied to another location iva move or subtraction; could reach addition in that location.
set<DefOrUse, LessDefUse>::iterator CopyDefIter = UseInst->GetFirstNonFlagsDef();
op_t CopyDefOp = CopyDefIter->GetOp();
ea_t CopyAdditionAddr;
if (this->IsDefInvolvedInAddition(UseInst->GetAddr(), CopyDefOp, CopyAdditionAddr)) {
AdditionAddr = CopyAdditionAddr;
return true;
}
}
}
if ((0 == NumUses) || LastChain) {
return false;
}
// Get next DEF, see if it is an addition.
AdditionAddr = this->GetFirstDefAddr(DUIndex, ChainIndex + 1, true);
}
vector<SMPInstr *>::iterator RedefInstIter = this->GetInstIterFromAddr(AdditionAddr);
return ((*RedefInstIter)->MDIsAddition());
#endif
} // end of SMPBasicBlock::IsDefInvolvedInAddition()
// Does value of DefOp/DefSSANum reach block end in any computation of any DEF at all?
bool SMPBasicBlock::DoesDefReachBlockEnd(ea_t DefAddr, op_t DefOp, int DefSSANum, set<int> &NonEscapingRegisterHashes) {
set<op_t, LessOp>::iterator LocalIter = this->LocalNames.find(DefOp);
bool LocalName = (LocalIter != this->LocalNames.end());
unsigned int DUIndex;
size_t NumChains, NumUses;
bool DoesEscape = false;
bool ReDEF = false;
bool UseFP = this->GetFunc()->UsesFramePointer();
// set<int> NonEscapingRegisterHashes; // memoization optimization: set of register/SSA# hashes that do not reach end of block
// If we encounter indirect memory operands of any kind, we cannot track them and must
// assume they are loop-variant and reach outside this block. Ditto for non-reg,
// non-stack operands.
if (MDIsIndirectMemoryOpnd(DefOp, UseFP) || (!MDIsDataFlowOpnd(DefOp, UseFP))) {
return true;
}
#if STARS_BUILD_DEF_USE_CHAINS
if (LocalName) {
DUIndex = ExtractGlobalIndex(*LocalIter);
size_t SSAIndex;
assert(DUIndex < this->GetNumDUChains(false));
NumChains = this->GetNumLocalChains(DUIndex, false);
for (SSAIndex = 0; SSAIndex < NumChains; ++SSAIndex) {
if (DefAddr == this->GetFirstDefAddr(DUIndex, SSAIndex, false)) {
break;
}
}
assert(SSAIndex < NumChains); // found it
// If it has no uses, it is dead. Being a local name, there is no LiveOut possibility.
NumUses = this->GetNumLocalUses(DUIndex, SSAIndex, false);
if (0 == NumUses) {
DoesEscape = false; // Local name with no uses; dead; cannot escape block.
}
else {
// For each use, we need to see if the value gets incorporated into a new DEF via
// arithmetic or assignment, and that new DEF reaches the end of the block.
for (size_t UseIndex = 0; UseIndex < NumUses; ++UseIndex) {
ea_t UseAddr = this->GetDUChainUse(DUIndex, SSAIndex, UseIndex, false);
SMPInstr *NextInst = this->FindInstr(UseAddr);
set<DefOrUse, LessDefUse>::iterator NextDefIter = NextInst->GetFirstNonFlagsDef();
if (NextDefIter != NextInst->GetLastDef()) {
// Instruction does something besides define the flags. That does not prove that
// our DefOp argument is transferred in any way to the next DEF, because our DefOp
// could just be used as an addressing register in NextInst.
if (NextInst->OperandTransfersValueToDef(DefOp)) {
op_t NextDefOp = NextDefIter->GetOp();
int NextDefSSANum = NextDefIter->GetSSANum();
bool RegNextDef = (o_reg == NextDefOp.type);
int NextDefHashValue;
if (RegNextDef) {
NextDefHashValue = HashGlobalNameAndSSA(NextDefOp, NextDefSSANum);
if (NonEscapingRegisterHashes.find(NextDefHashValue) != NonEscapingRegisterHashes.end()) {
// We have already determined that NextDef does not reach the end of the block.
continue;
}
}
ea_t NextDefAddr = UseAddr;
if (this->DoesDefReachBlockEnd(NextDefAddr, NextDefOp, NextDefSSANum, NonEscapingRegisterHashes)) {
DoesEscape = true;
break;
}
else if (RegNextDef) {
// Memoize this result to save time reanalyzing it for other def-use chains.
pair<set<int>::iterator, bool> InsertResult;
InsertResult = NonEscapingRegisterHashes.insert(NextDefHashValue);
assert(InsertResult.second);
}
}
}
} // end for all uses in DU-chain
}
}
else { // global name
DUIndex = this->GetGlobalDUIndex(DefOp, DefAddr);
NumChains = this->GetNumLocalChains(DUIndex, true);
assert(0 < NumChains);
bool FoundIndex = false;
size_t ChainIndex;
for (ChainIndex = 0; ChainIndex < NumChains; ++ChainIndex) {
if (DefAddr == this->GetFirstDefAddr(DUIndex, ChainIndex, true)) {
FoundIndex = true;
break;
}
}
assert(FoundIndex);
NumUses = this->GetNumLocalUses(DUIndex, ChainIndex, true);
bool LastChain = (ChainIndex == (NumChains - 1));
if (LastChain) { // Last chain
DoesEscape = this->IsLiveOut(DefOp);
}
else if (0 == NumUses) {
// No uses in that chain. If it is not the last chain, then DefOp is redefined and this
// DEF is truly dead. If it is the last chain and DefOp is in the LiveOut set, then it
// was caught above and DoesEscape would already be true and this statement would not be reached.
DoesEscape = false;
}
else {
// For each use, we need to see if the value gets incorporated into a new DEF via
// arithmetic or assignment, and that new DEF reaches the end of the block.
for (size_t UseIndex = 0; UseIndex < NumUses; ++UseIndex) {
ea_t UseAddr = this->GetDUChainUse(DUIndex, ChainIndex, UseIndex, true);
SMPInstr *NextInst = this->FindInstr(UseAddr);
set<DefOrUse, LessDefUse>::iterator NextDefIter = NextInst->GetFirstNonFlagsDef();
if (NextDefIter != NextInst->GetLastDef()) {
// Instruction does something besides define the flags. That does not prove that
// our DefOp argument is transferred in any way to the next DEF, because our DefOp
// could just be used as an addressing register in NextInst.
if (NextInst->OperandTransfersValueToDef(DefOp)) {
op_t NextDefOp = NextDefIter->GetOp();
int NextDefSSANum = NextDefIter->GetSSANum();
bool RegNextDef = (o_reg == NextDefOp.type);
int NextDefHashValue;
if (RegNextDef) {
NextDefHashValue = HashGlobalNameAndSSA(NextDefOp, NextDefSSANum);
if (NonEscapingRegisterHashes.find(NextDefHashValue) != NonEscapingRegisterHashes.end()) {
// We have already determined that NextDef does not reach the end of the block.
continue;
}
}
ea_t NextDefAddr = UseAddr;
if (this->DoesDefReachBlockEnd(NextDefAddr, NextDefOp, NextDefSSANum, NonEscapingRegisterHashes)) {
DoesEscape = true;
break;
}
else if (RegNextDef) {
// Memoize this result to save time reanalyzing it for other def-use chains.
pair<set<int>::iterator, bool> InsertResult = NonEscapingRegisterHashes.insert(NextDefHashValue);
assert(InsertResult.second);
}
}
}
} // end for all uses in DU-chain
}
}
#else
vector<SMPInstr *>::iterator InstIter = this->GetInstIterFromAddr(DefAddr);
++InstIter;
while (InstIter != this->GetLastInst()) {
SMPInstr *NextInst = (*InstIter);
if (NextInst->FindUse(DefOp) != NextInst->GetLastUse()) { // NextInst uses DefOp
set<DefOrUse, LessDefUse>::iterator NextDefIter = NextInst->GetFirstNonFlagsDef();
if (NextDefIter != NextInst->GetLastDef()) {
// Instruction does something besides define the flags. That does not prove that
// our DefOp argument is transferred in any way to the next DEF, because our DefOp
// could just be used as an addressing register in NextInst.
if (NextInst->OperandTransfersValueToDef(DefOp)) {
op_t NextDefOp = NextDefIter->GetOp();
int NextDefSSANum = NextDefIter->GetSSANum();
bool RegNextDef = (o_reg == NextDefOp.type);
int NextDefHashValue;
if (RegNextDef) {
NextDefHashValue = HashGlobalNameAndSSA(NextDefOp, NextDefSSANum);
if (NonEscapingRegisterHashes.find(NextDefHashValue) != NonEscapingRegisterHashes.end()) {
// We have already determined that NextDef does not reach the end of the block.
++InstIter;
continue;
}
}
ea_t NextDefAddr = NextInst->GetAddr();
if (this->DoesDefReachBlockEnd(NextDefAddr, NextDefOp, NextDefSSANum, NonEscapingRegisterHashes)) {
DoesEscape = true;
break;
}
else if (RegNextDef) {
// Memoize this result to save time reanalyzing it for other def-use chains.
pair<set<int>::iterator, bool> InsertResult;
InsertResult = NonEscapingRegisterHashes.insert(NextDefHashValue);
assert(InsertResult.second);
}
}
}
} // end if FindUse() succeeds
if (NextInst->FindDef(DefOp) != NextInst->GetLastDef()) {
// Re-DEF.
ReDEF = true;
break;
}
++InstIter;
}
if (!(DoesEscape || LocalName || ReDEF)) {
// Did not find an escape, but we have a global name that reaches the end of the block
// without being redefined. If it is LiveOut, it escapes.
DoesEscape = this->IsLiveOut(DefOp);
}
#endif
NonEscapingRegisterHashes.clear();
return DoesEscape;
} // end of SMPBasicBlock::DoesDefReachBlockEnd()
// DefOp/DefSSANum is only used in LoopNum (outside of DefAddr) as address reg or Phi USE
bool SMPBasicBlock::IsDefOnlyUsedAsAddressReg(ea_t DefAddr, op_t DefOp, size_t LoopNum, size_t &AddrUseCounter, SMPOperandType &MemType) {
bool OnlyAddressReg = false;
bool ReDefSeen = false;
if (this->IsProcessed() || (!this->GetFunc()->IsBlockInLoop(this->GetNumber(), LoopNum))) {
// Must have already passed the test, or is an irrelevant block outside the loop.
return true;
}
if (o_reg == DefOp.type) {
OnlyAddressReg = true;
vector<SMPInstr *>::iterator InstIter;
op_t SearchOp = DefOp;
CanonicalizeOpnd(SearchOp);
set<DefOrUse, LessDefUse>::iterator UseIter;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
ea_t InstAddr = CurrInst->GetAddr();
if (InstAddr != DefAddr) { // Skip induction variable re-definition.
UseIter = CurrInst->FindUse(SearchOp);
if (UseIter != CurrInst->GetLastUse()) {
// Found a USE of DefOp not at DefAddr.
if (CurrInst->HasDestMemoryOperand() || CurrInst->HasSourceMemoryOperand()) {
op_t MemOp = CurrInst->GetMemUse();
if (o_void == MemOp.type) {
MemOp = CurrInst->GetMemDef();
}
int BaseReg, IndexReg;
ushort ScaleFactor;
ea_t offset;
MDExtractAddressFields(MemOp, BaseReg, IndexReg, ScaleFactor, offset);
if ((BaseReg != DefOp.reg) && (IndexReg != DefOp.reg)) {
OnlyAddressReg = false; // USEd somehow, but not as an address reg.
}
else {
++AddrUseCounter;
}
}
else {
// Definitely not an addressing reg, as there are no memory operands.
OnlyAddressReg = false;
}
if (!OnlyAddressReg)
break;
}
#if 1
else if ((InstAddr > DefAddr) && (CurrInst->FindDef(SearchOp) != CurrInst->GetLastDef())) {
// SearchOp is DEFed but not USEd in CurrInst. That means some re-DEF
// that does not depend on the previous value, e.g. SearchOp := OtherOp,
// in a simple move. No need to search the rest of the block, as there
// will be no more USEs of the original SearchOp.
ReDefSeen = true;
break;
}
#endif
}
} // end for all insts
// If we passed all instructions in block with no problems, recurse into successors.
this->SetProcessed(true);
if (OnlyAddressReg && (!ReDefSeen)) {
list<SMPBasicBlock *>::iterator SuccIter;
ea_t PseudoDefAddr; // To identify re-DEF instructions in successor blocks.
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
PseudoDefAddr = (*SuccIter)->GetFirstAddr() - 1; // any DEF without USE will be seen as a re-DEF in successor.
if (!(*SuccIter)->IsDefOnlyUsedAsAddressReg(PseudoDefAddr, DefOp, LoopNum, AddrUseCounter, MemType)) {
OnlyAddressReg = false;
break;
}
}
}
}
if (OnlyAddressReg) {
if (0 < AddrUseCounter) {
// NOTE: Future work: extract pointer type of base register above.
MemType = POINTER;
}
}
return OnlyAddressReg;
} // end of SMPBasicBlock::IsDefOnlyUsedAsAddressReg()
// erase() block starting at FirstAddr from Preds list
void SMPBasicBlock::ErasePred(ea_t FirstAddr) {
list<SMPBasicBlock *>::iterator PredIter;
PredIter = this->Predecessors.begin();
while (PredIter != this->Predecessors.end()) {
if ((*PredIter)->GetFirstAddr() == FirstAddr) {
PredIter = this->Predecessors.erase(PredIter);
break; // can only appear once
}
else
++PredIter;
}
return;
} // end of SMPBasicBlock::ErasePred()
// erase() block starting at FirstAddr from Successors list
void SMPBasicBlock::EraseSucc(ea_t FirstAddr) {
list<SMPBasicBlock *>::iterator SuccIter;
SuccIter = this->Successors.begin();
while (SuccIter != this->Successors.end()) {
if ((*SuccIter)->GetFirstAddr() == FirstAddr) {
SuccIter = this->Successors.erase(SuccIter);
break; // can only appear once
}
else
++SuccIter;
}
return;
} // end of SMPBasicBlock::EraseSucc()
// Add ReachInDefn to the ReachesIn set. If it was not already present,
// then update the ReachesOutStale flag.
void SMPBasicBlock::AddReachesIn(pair<op_t, ea_t> ReachInDefn) {
pair<set<pair<op_t, ea_t>, LessDefinition>::iterator, bool> InsertResult;
InsertResult = ReachesInSet.insert(ReachInDefn);
if (InsertResult.second) {
// New element added; ReachesOut set might be stale.
this->SetReachesOutStale();
}
} // end of SMPBasicBlock::AddReachesIn()
// Add a new definition to the ReachesOut set. If it was not already
// present in the ReachesOut set, then propagate it to the ReachesIn sets
// of all successor blocks. NOTE: The policy here is to keep the ReachesIn
// sets up to date at all times.
void SMPBasicBlock::AddReachesOut(pair<op_t, ea_t> ReachOutDefn) {
pair<set<pair<op_t, ea_t>, LessDefinition>::iterator, bool> InsertResult;
InsertResult = ReachesOutSet.insert(ReachOutDefn);
if (InsertResult.second) {
// Insertion was of a new element; propagate to ReachesIn of all successors.
list<SMPBasicBlock *>::iterator SuccIter;
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
(*SuccIter)->AddReachesIn(ReachOutDefn);
}
}
return;
} // end of SMPBasicBlock::AddReachesOut()
// Erase a phi function from the list.
bool SMPBasicBlock::ErasePhi(op_t OldOp) {
set<SMPPhiFunction, LessPhi>::iterator PhiIter;
PhiIter = this->FindPhi(OldOp);
if (PhiIter == this->PhiFunctions.end())
return false; // did not find, cannot erase
this->PhiFunctions.erase(PhiIter);
return true;
} // end of SMPBasicBlock::ErasePhi()
// Add a phi function to the list of phi functions entering this block.
// If phi function for this global name already existed in the block,
// return false because no new phi function was added; else return true.
bool SMPBasicBlock::AddPhi(SMPPhiFunction NewPhi) {
if (this->PhiFunctions.end() == this->PhiFunctions.find(NewPhi)) {
this->PhiFunctions.insert(NewPhi);
return true;
}
else
return false;
} // end of SMPBasicBlock::AddPhi()
// Change the SSA number of the Phi function DEF corresponding to DefOp.
bool SMPBasicBlock::SetPhiDefSSA(op_t DefOp, int SSANum) {
bool updated = false;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
CurrPhi = this->FindPhi(DefOp);
if (CurrPhi == this->PhiFunctions.end()) { // did not find
SMP_msg("ERROR: SetPhiDefSSA for block %d did not find DefOp: ", this->GetNumber());
PrintOperand(DefOp);
SMP_msg("\n");
}
else { // found it
// To change a set item, we must change a copy, remove the original item
// from the set, and then insert the modified copy of the item.
SMPPhiFunction TempPhi = (*CurrPhi);
TempPhi.SetSSADef(SSANum);
bool erased = this->ErasePhi(DefOp);
assert(erased);
updated = this->AddPhi(TempPhi);
assert(updated);
}
return updated;
} // end of SMPBasicBlock::SetPhiDefSSA()
// Change the SSA number of the Phi function USE corresponding to DefOp and index.
bool SMPBasicBlock::SetPhiUseSSA(op_t DefOp, size_t index, int SSANum) {
bool updated = false;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
CurrPhi = this->FindPhi(DefOp);
if (CurrPhi == this->PhiFunctions.end()) { // did not find
SMP_msg("ERROR: SetPhiUseSSA for block %d did not find DefOp: ", this->GetNumber());
PrintOperand(DefOp);
SMP_msg("\n");
}
else { // found it
// To change a set item, we must change a copy, remove the original item
// from the set, and then insert the modified copy of the item.
SMPPhiFunction TempPhi = (*CurrPhi);
TempPhi.SetSSARef(index, SSANum);
bool erased = this->ErasePhi(DefOp);
assert(erased);
updated = this->AddPhi(TempPhi);
assert(updated);
}
return updated;
} // end of SMPBasicBlock::SetPhiUseSSA()
// Change the SMP type of the Phi function DEF corresponding to DefOp.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::SetPhiDefType(op_t DefOp, SMPOperandType Type) {
bool updated = false;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
CurrPhi = this->FindPhi(DefOp);
if (CurrPhi == this->PhiFunctions.end()) { // did not find
SMP_msg("ERROR: SetPhiDefType for block %d did not find DefOp: ", this->GetNumber());
PrintOperand(DefOp);
SMP_msg("\n");
}
else { // found it
// To change a set item, we must change a copy, remove the original item
// from the set, and then insert the modified copy of the item.
SMPPhiFunction TempPhi = (*CurrPhi);
const SMPInstr *FirstInst = (*(this->GetFirstInst()));
TempPhi.SetDefType(Type, FirstInst);
bool erased = this->ErasePhi(DefOp);
assert(erased);
pair<set<SMPPhiFunction, LessPhi>::iterator, bool> InsertResult;
InsertResult = this->PhiFunctions.insert(TempPhi);
CurrPhi = InsertResult.first;
updated = InsertResult.second;
assert(updated);
}
return CurrPhi;
} // end of SMPBasicBlock::SetPhiDefType()
// Change the SMP type of the Phi function USE corresponding to DefOp and index.
bool SMPBasicBlock::SetPhiUseType(op_t DefOp, size_t index, SMPOperandType Type) {
bool updated = false;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
CurrPhi = this->FindPhi(DefOp);
if (CurrPhi == this->PhiFunctions.end()) { // did not find
SMP_msg("ERROR: SetPhiUseType for block %d did not find DefOp: ", this->GetNumber());
PrintOperand(DefOp);
SMP_msg("\n");
}
else { // found it
// To change a set item, we must change a copy, remove the original item
// from the set, and then insert the modified copy of the item.
SMPPhiFunction TempPhi = (*CurrPhi);
const SMPInstr *FirstInst = (*(this->GetFirstInst()));
TempPhi.SetRefType(index, Type, FirstInst);
bool erased = this->ErasePhi(DefOp);
assert(erased);
updated = this->AddPhi(TempPhi);
assert(updated);
}
return updated;
} // end of SMPBasicBlock::SetPhiUseType()
// Change the metadata type of the Phi function DEF corresponding to DefOp.
set<SMPPhiFunction, LessPhi>::iterator SMPBasicBlock::SetPhiDefMetadata(op_t DefOp, SMPMetadataType Status) {
bool updated = false;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
CurrPhi = this->FindPhi(DefOp);
if (CurrPhi == this->PhiFunctions.end()) { // did not find
SMP_msg("ERROR: SetPhiDefMetadata for block %d did not find DefOp: ", this->GetNumber());
PrintOperand(DefOp);
SMP_msg("\n");
}
else { // found it
// To change a set item, we must change a copy, remove the original item
// from the set, and then insert the modified copy of the item.
SMPPhiFunction TempPhi = (*CurrPhi);
TempPhi.SetDefMetadata(Status);
bool erased = this->ErasePhi(DefOp);
assert(erased);
pair<set<SMPPhiFunction, LessPhi>::iterator, bool> InsertResult;
InsertResult = this->PhiFunctions.insert(TempPhi);
CurrPhi = InsertResult.first;
updated = InsertResult.second;
assert(updated);
}
return CurrPhi;
} // end of SMPBasicBlock::SetPhiDefMetadata()
// Insert SCCP value for local name; change if already found.
map<int, struct STARS_SCCP_Const_Struct>::iterator SMPBasicBlock::InsertLocalConstValue(int DefHashValue, struct STARS_SCCP_Const_Struct NewConstEntry) {
map<int, struct STARS_SCCP_Const_Struct>::iterator MapIter = this->FindLocalConstValue(DefHashValue);
if (MapIter == this->GetLastLocalConstValueIter()) { // no old entry; insert
pair<int, struct STARS_SCCP_Const_Struct> InsertPair(DefHashValue, NewConstEntry);
pair<map<int, struct STARS_SCCP_Const_Struct>::iterator, bool> InsertResult = this->ConstantLocalDefs.insert(InsertPair);
assert(InsertResult.second);
MapIter = InsertResult.first;
}
else { // old entry found; update
MapIter->second = NewConstEntry;
}
return MapIter;
} // end of SMPBasicBlock::InsertLocalConstValue()
// Six methods to get values into the maps of local reg/SSA to FG info.
// For global names, see corresponding methods in SMPFunction.
void SMPBasicBlock::UpdateDefSignMiscInfo(int DefHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair< map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
if (MapIter == this->LocalDefFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = NewInfo;
NewFGInfo.SizeInfo = 0;
pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFGInfo);
MapResult = this->LocalDefFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SignMiscInfo |= NewInfo;
}
return;
} // end of SMPBasicBlock::UpdateDefSignMiscInfo()
void SMPBasicBlock::UpdateUseSignMiscInfo(int UseHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
if (MapIter == this->LocalUseFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = NewInfo;
NewFGInfo.SizeInfo = 0;
pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFGInfo);
MapResult = this->LocalUseFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SignMiscInfo |= NewInfo;
}
return;
} // end of SMPBasicBlock::UpdateUseSignMiscInfo()
void SMPBasicBlock::UpdateDefWidthTypeInfo(int DefHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
if (MapIter == this->LocalDefFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = 0;
NewFGInfo.SizeInfo = NewInfo;
pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFGInfo);
MapResult = this->LocalDefFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SizeInfo |= NewInfo;
}
return;
} // end of SMPBasicBlock::UpdateDefWidthTypeInfo()
void SMPBasicBlock::UpdateUseWidthTypeInfo(int UseHashValue, unsigned short NewInfo) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
if (MapIter == this->LocalUseFGInfoBySSA.end()) {
// Not found; insert first.
struct FineGrainedInfo NewFGInfo;
NewFGInfo.SignMiscInfo = 0;
NewFGInfo.SizeInfo = NewInfo;
pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFGInfo);
MapResult = this->LocalUseFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just OR in the new bits.
MapIter->second.SizeInfo |= NewInfo;
}
return;
} // end of SMPBasicBlock::UpdateUseWidthTypeInfo()
void SMPBasicBlock::UpdateDefFGInfo(int DefHashValue, struct FineGrainedInfo NewFG) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
if (MapIter == this->LocalDefFGInfoBySSA.end()) {
// Not found; insert it.
pair<int, struct FineGrainedInfo> MapItem(DefHashValue, NewFG);
MapResult = this->LocalDefFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just put in the new bits.
MapIter->second.SignMiscInfo |= NewFG.SignMiscInfo;
MapIter->second.SizeInfo |= NewFG.SizeInfo;
}
return;
} // end of SMPBasicBlock::UpdateDefFGInfo()
void SMPBasicBlock::UpdateUseFGInfo(int UseHashValue, struct FineGrainedInfo NewFG) {
map<int, struct FineGrainedInfo>::iterator MapIter;
pair<map<int, struct FineGrainedInfo>::iterator, bool> MapResult;
MapIter = this->LocalUseFGInfoBySSA.find(UseHashValue);
if (MapIter == this->LocalUseFGInfoBySSA.end()) {
// Not found; insert it.
pair<int, struct FineGrainedInfo> MapItem(UseHashValue, NewFG);
MapResult = this->LocalUseFGInfoBySSA.insert(MapItem);
assert(MapResult.second); // Was not previously found, insertion must work.
}
else { // found; just put in the new bits.
MapIter->second.SignMiscInfo |= NewFG.SignMiscInfo;
MapIter->second.SizeInfo |= NewFG.SizeInfo;
}
return;
} // end of SMPBasicBlock::UpdateUseFGInfo()
// Reset the signedness bits to zero for DEF.
void SMPBasicBlock::ClearDefSignedness(int DefHashValue) {
map<int, struct FineGrainedInfo>::iterator MapIter;
MapIter = this->LocalDefFGInfoBySSA.find(DefHashValue);
if (MapIter != this->LocalDefFGInfoBySSA.end()) {
MapIter->second.SignMiscInfo &= (~FG_MASK_SIGNEDNESS_BITS);
}
return;
} // end of SMPBasicBlock::ClearDefSignedness()
// Ensure that the Phi DEFs have all the fine grained info from all Phi USEs.
void SMPBasicBlock::PropagatePhiFGInfo(void) {
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
size_t PhiUseIndex;
struct FineGrainedInfo UseFG;
for (CurrPhi = this->GetFirstPhi(); CurrPhi != this->GetLastPhi(); ++CurrPhi) {
op_t PhiOp = CurrPhi->GetAnyOp();
int DefSSANum = CurrPhi->GetDefSSANum();
if (!MDIsGeneralPurposeReg(PhiOp)) // !!!!****!!!! Add stack locations also
continue;
int DefHashValue = HashGlobalNameAndSSA(PhiOp, DefSSANum);
for (PhiUseIndex = 0; PhiUseIndex < CurrPhi->GetPhiListSize(); ++PhiUseIndex) {
int UseSSANum = CurrPhi->GetUseSSANum(PhiUseIndex);
int UseHashValue = HashGlobalNameAndSSA(PhiOp, UseSSANum);
UseFG = this->GetFunc()->GetUseFGInfo(UseHashValue);
#if 1
if ((UseFG.SignMiscInfo == 0) && (UseFG.SizeInfo == 0)) {
// If no info for USE, get info from DEF.
UseFG = this->GetFunc()->GetDefFGInfo(UseHashValue);
}
#endif
this->GetFunc()->UpdateDefFGInfo(DefHashValue, UseFG);
}
}
return;
} // end of SMPBasicBlock::PropagatePhiFGInfo()
// Find consecutive DEFs of the same name within the block, both having
// live metadata, that have the same type, making the second DEF
// redundant metadata.
bool SMPBasicBlock::FindRedundantLocalMetadata(bool SafeFunc) {
bool changed = false;
bool CallInst;
bool UseFP = this->GetFunc()->UsesFramePointer();
bool EligibleOperand;
bool LeafFunc = this->GetFunc()->IsLeaf();
set<op_t, LessOp>::iterator NameIter;
vector<SMPInstr *>::iterator InstIter;
SMPInstr *CurrInst;
set<DefOrUse, LessDefUse>::iterator CurrDef;
size_t LocalNameLimit = this->LocalNames.size();
size_t GlobalNameLimit = this->GetFunc()->NumGlobalNames();
vector<SMPOperandType> LocalTypes;
vector<SMPOperandType> GlobalTypes;
#if 0
bool DebugFlag = false;
if (0 == strcmp("__libc_start_main", this->GetFunc()->GetFuncName())) {
DebugFlag = true;
}
#endif
// Initialize the most recently seen type for each possible DEF.
for (size_t i = 0; i < LocalNameLimit; ++i)
LocalTypes.push_back(UNINIT);
for (size_t i = 0; i < GlobalNameLimit; ++i)
GlobalTypes.push_back(UNINIT);
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
CurrInst = (*InstIter);
if (NN_fnop == CurrInst->GetCmd().itype)
continue; // skip SSA marker instruction; has no normal DEFs
CallInst = ((CurrInst->GetDataFlowType() == CALL)
|| (CurrInst->GetDataFlowType() == INDIR_CALL));
for (CurrDef = CurrInst->GetFirstDef(); CurrDef != CurrInst->GetLastDef(); ++CurrDef) {
op_t DefOp = CurrDef->GetOp();
// We limit our analysis to register DEFs, or stack memory DEFs
// in SAFE functions. ***!!!*** Could add o_mem direct accesses
// in SAFE functions.
EligibleOperand = ((DefOp.type == o_reg)
&& !(MDIsStackOrFramePointerReg(DefOp, UseFP)));
if (!EligibleOperand && (DefOp.type != o_reg) && SafeFunc) {
// Make some exceptions for SAFE functions.
EligibleOperand = MDIsDirectStackAccessOpnd(DefOp, UseFP)
|| (LeafFunc && !MDIsIndirectMemoryOpnd(DefOp, UseFP));
}
if (!EligibleOperand)
continue;
// If the metadata is not live for the DEF it is irrelevant
// to redundancy analysis. We make an exception for the DEFs
// of caller-saved regs at a CALL instruction, because we have
// no idea what might have happened to the metadata in the callee.
if ((CurrDef->GetMetadataStatus() != DEF_METADATA_USED)
&& (!(CallInst && MDIsCallerSavedReg(DefOp))))
continue;
bool GlobalName = false;
NameIter = this->GetFunc()->FindGlobalName(DefOp);
unsigned int NameIndex;
SMPOperandType CurrType = CurrDef->GetType();
SMPOperandType OldType;
if (NameIter != this->GetFunc()->GetLastGlobalName()) {
// global name
GlobalName = true;
NameIndex = ExtractGlobalIndex(*NameIter);
OldType = GlobalTypes.at(NameIndex);
}
else { // local name
NameIter = this->FindLocalName(DefOp);
assert(NameIter != this->GetLastLocalName());
NameIndex = ExtractGlobalIndex(*NameIter);
OldType = LocalTypes.at(NameIndex);
}
if (IsEqType(CurrType, OldType)) {
// types agree; only redundant if NUMERIC or pointers with
// the same referent, which we cannot determine statically,
// so we stick to NUMERIC redundancy only.
if (IsNumeric(CurrType)) {
// Metadata is redundant; profiler-dependent or not?
bool ProfDerived = IsProfDerived(CurrType)
|| IsProfDerived(OldType);
if (ProfDerived) {
CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_PROF_REDUNDANT);
}
else {
CurrDef = CurrInst->SetDefMetadata(DefOp, DEF_METADATA_REDUNDANT);
}
changed = true;
}
} // end if current type same as old type
else {
// Update latest type seen.
if (GlobalName)
GlobalTypes[NameIndex] = CurrType;
else
LocalTypes[NameIndex] = CurrType;
}
} // end for all DEFs in current instruction
} // end for all instructions
LocalTypes.clear();
GlobalTypes.clear();
return changed;
} // end of SMPBasicBlock::FindRedundantLocalMetadata()
#if STARS_BUILD_DEF_USE_CHAINS
// Mark chains that include the indirect mem write addr
void SMPBasicBlock::MarkIndWriteChains(ea_t InstAddr) {
// Iterate through all local names that have DU chains.
size_t NameIndex, SSAIndex, SSALimit;
for (NameIndex = 0; NameIndex < this->GetNumDUChains(false); ++NameIndex) {
SSALimit = this->GetNumLocalChains(NameIndex, false);
for (SSAIndex = 0; SSAIndex < SSALimit; ++SSAIndex) {
ea_t LastAddr = this->GetLastUseAddr(NameIndex, SSAIndex, false);
if ((InstAddr > this->GetFirstDefAddr(NameIndex, SSAIndex, false))
&& (InstAddr < LastAddr)
&& (BADADDR != LastAddr)) {
this->SetIndWrite(NameIndex, SSAIndex, false, true);
}
}
}
// Iterate through all global names that have DU chains.
for (NameIndex = 0; NameIndex < this->GetNumDUChains(true); ++NameIndex) {
SSALimit = this->GetNumLocalChains(NameIndex, true);
for (SSAIndex = 0; SSAIndex < SSALimit; ++SSAIndex) {
bool AfterDef = (InstAddr > this->GetFirstDefAddr(NameIndex, SSAIndex, true));
bool BeforeLastUse = (InstAddr < this->GetLastUseAddr(NameIndex, SSAIndex, true));
if (AfterDef) {
if (BeforeLastUse) {
this->SetIndWrite(NameIndex, SSAIndex, true, true);
}
// If the chain is the last SSA index for this global name,
// and the global name is LiveOut, then the chain really
// extends to the end of the block.
else if (SSAIndex == (SSALimit - 1)) { // last chain for name
// Check for LiveOut
op_t GlobalOp = this->GetDUName(NameIndex, true);
if (this->IsLiveOut(GlobalOp)) {
// live out; indirect write inside chain
this->SetIndWrite(NameIndex, SSAIndex, true, true);
}
}
} // end if (AfterDef)
} // end for all SSA indices in each global name
} // end for all global names
return;
} // end of SMPBasicBlock::MarkIndWriteChains()
#endif
// Does block infinitely loop back to itself?
bool SMPBasicBlock::IsInfiniteSelfLoop(void) {
bool InfiniteLoop = false;
size_t NumSucc = this->GetNumSuccessors();
if (1 == NumSucc) {
// Is the only successor this block, and there are no function calls?
int MyNum = this->GetNumber();
list<SMPBasicBlock *>::iterator SuccIter = this->GetFirstSucc();
int SuccNum = (*SuccIter)->GetNumber();
if ((SuccNum == MyNum) && (!(this->HasCallInstruction() || this->HasIndirJumpInstruction()))) {
InfiniteLoop = true;
}
}
return InfiniteLoop;
} // end of SMPBasicBlock::IsInfiniteSelfLoop()
// Does block call a function?
bool SMPBasicBlock::HasCallInstruction(void) {
vector<SMPInstr *>::iterator InstIter;
bool HasCall = false;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPitype InstDataFlowType = (*InstIter)->GetDataFlowType();
if ((CALL == InstDataFlowType) || (INDIR_CALL == InstDataFlowType)) {
HasCall = true;
break;
}
}
return HasCall;
} // end of SMPBasicBlock::HasCallInstruction()
// Does block end with an indirect jump?
bool SMPBasicBlock::HasIndirJumpInstruction(void) {
vector<SMPInstr *>::reverse_iterator InstIter = this->GetRevInstBegin();
SMPInstr *LastInst = (*InstIter);
bool HasIndirJump = (LastInst->GetDataFlowType() == INDIR_JUMP);
return HasIndirJump;
} // end of SMPBasicBlock::HasIndirJumpInstruction()
// Does block end with a conditional branch?
bool SMPBasicBlock::HasConditionalBranch(void) {
vector<SMPInstr *>::reverse_iterator InstIter = this->GetRevInstBegin();
SMPInstr *LastInst = (*InstIter);
bool HasCondBranch = (LastInst->GetDataFlowType() == COND_BRANCH);
return HasCondBranch;
} // end of SMPBasicBlock::HasConditionalBranch()
// We don't care if we overflow computing some DEFs, because of how they are used.
// Return true when we detect one of these cases.
bool SMPBasicBlock::IsBenignOverflowDEF(op_t DefOp, int DefSSANum, size_t DefAddr, bool UnderflowOpcode, int &IdiomCode) {
bool benign = false;
op_t UseOp;
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator UseIter, DefIter;
bool RegDef = (o_reg == DefOp.type);
struct FineGrainedInfo DefFGInfo;
bool LocalDefName = this->IsLocalName(DefOp);
bool UseFP = this->GetFunc()->UsesFramePointer();
if (RegDef) {
unsigned int DefHashValue = HashGlobalNameAndSSA(DefOp, DefSSANum);
if (LocalDefName) {
// Local name, find in basic block maps.
DefFGInfo = this->GetDefFGInfo(DefHashValue);
}
else { // Global name, find in global maps.
DefFGInfo = this->GetFunc()->GetDefFGInfo(DefHashValue);
}
}
else if (MDIsDirectStackAccessOpnd(DefOp, UseFP)) {
bool success = this->GetFunc()->MDGetFGStackLocInfo(DefAddr, DefOp, DefFGInfo);
assert(success);
}
else {
return false; // we can only handle register and stack DefOp types.
}
bool DefIsUnsigned = (FG_MASK_UNSIGNED == (DefFGInfo.SignMiscInfo & FG_MASK_SIGNEDNESS_BITS));
// First, we find the USEs of the DEF.
if (RegDef) {
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
size_t InstAddr = CurrInst->GetAddr();
if (InstAddr > DefAddr) {
UseIter = CurrInst->FindUse(DefOp);
if (UseIter != CurrInst->GetLastUse()) {
if (UseIter->GetSSANum() == DefSSANum) {
// Found use of same SSA name.
if (CurrInst->IsSubRegUsedAsShiftCount(DefOp)) {
// A subreg of DefOp is used as a shift counter.
// We don't care if we overflowed DefOp, because
// we don't mind tossing upper bits anyway, as we
// need an 8-bit shift count for this USE.
benign = true;
IdiomCode = 1;
}
else if (INDIR_JUMP == CurrInst->GetDataFlowType()) {
// Lots of false positives on indirect jumps via switch tables, because if
// any switch index has a negative number, then the compiler makes the "base"
// address be the address of "case 0:" rather than the beginning address, and then
// uses negative offsets to reach the "case -1:" and "case -2:" etc. addresses.
// So, STARS infers CODEPOINTER type => UNSIGNED, but we have unsigned+negative offset
// which looks like an unsigned addition overflow. We need to change the signedness
// to UNKNOWNSIGN when the annotation is emitted. This is not a truly benign case,
// so we just use the IdiomCode to signal what is going on and leave benign set to false.
// In the cases that occur later, we will continue to process this code just in case
// a truly benign code pattern is detected that will override this IdiomCode.
// NOTE: We could make this case less likely to produce false negatives by getting info
// from IDA Pro to see if we have a switch table with negative offsets.
IdiomCode = 17;
}
break; // For now, stop at first USE.
}
}
}
}
}
if (benign) {
return benign;
}
SMPInstr *DefInst = this->GetFunc()->GetInstFromAddr(DefAddr);
ea_t SourceInstAddr = BADADDR;
SMPInstr *SourceInst = NULL;
int UseSSANum = SMP_SSA_UNINIT;
bool SpecialSourceFound = false;
bool LeaDef = DefInst->MDIsLoadEffectiveAddressInstr();
UseIter = DefInst->FindUse(DefOp); // DEF is also USE in addition, subtraction, etc.
if (MDIsDataFlowOpnd(DefOp, UseFP) && (UseIter != DefInst->GetLastUse())) {
UseSSANum = UseIter->GetSSANum();
this->GetFunc()->ResetProcessedBlocks();
SpecialSourceFound = DefInst->IsOpSourceSpecial(DefOp, UseSSANum, false, SourceInstAddr);
if (SpecialSourceFound) {
SourceInst = this->GetFunc()->GetInstFromAddr(SourceInstAddr);
}
}
// Second case: Subtraction of two values, each of which is just a condition code.
// This can happen in optimized code that tests for which of two condition codes
// has been set, e.g.:
// [arithmetic operation or comparison]
// seta al ; if "above" flag then al := 1 else al := 0
// setb bl ; if "below" flag then bl := 1 else bl := 0
// mov ecx,eax ; make copy of eax (including al) into ecx
// sub al,bl ; al := al - bl
// The resulting value in al will be 1 if the above flag was set, -1 if below, 0 if neither.
// We see the seta/setb as implying unsigned values, which is true, but if al becomes -1
// we do not want to consider this to be an underflow.
// If the source of the minuend and subtrahend are one condition code and one small immediate,
// then we also want to suppress underflow false positives.
// The same logic applies to overflow opcodes: lea edx,[eax+eax-1] is hard to classify as
// potential underflow or overflow. If eax comes from a condition code (seta eax), the values
// will be small and no overflow check is needed.
if (!benign) {
if (UnderflowOpcode && MDIsDataFlowOpnd(DefOp, UseFP)) {
// Prepare for possible recursive traversals through the function blocks.
this->GetFunc()->ResetProcessedBlocks();
if (SpecialSourceFound && DefInst->IsOpSourceConditionCode(DefOp, UseSSANum)) {
// If we had a decrement opcode, we are done, and underflow is benign.
if (DefInst->MDIsDecrement()) {
benign = true;
}
else { // For subtraction, need to see if BOTH operands came from condition codes (flags).
UseOp = DefInst->GetUseOnlyAddSubOp();
if (MDIsDataFlowOpnd(UseOp, UseFP)) {
CanonicalizeOpnd(UseOp);
UseIter = DefInst->FindUse(UseOp);
int SubtrahendSSANum = UseIter->GetSSANum();
this->GetFunc()->ResetProcessedBlocks();
benign = DefInst->IsOpSourceConditionCode(UseOp, SubtrahendSSANum);
}
else if (UseOp.type == o_imm) {
uval_t ImmVal = UseOp.value;
benign = (ImmVal <= 4); // small value is intentionally setting up bit pattern of mostly 1-bits
}
}
if (benign) {
IdiomCode = 3;
}
}
// Prepare for possible recursive traversals through the function blocks.
this->GetFunc()->ResetProcessedBlocks();
if (!benign && SpecialSourceFound && (DefInst->IsOpSourceZeroExtendedMove(DefOp, UseSSANum, false))) {
// If we had a decrement opcode, we are done, and underflow is not benign.
if (DefInst->MDIsDecrement()) {
benign = false;
}
else { // For subtraction, need to see if BOTH operands came from zero-extended moves.
UseOp = DefInst->GetUseOnlyAddSubOp();
if (MDIsDataFlowOpnd(UseOp, UseFP)) {
CanonicalizeOpnd(UseOp);
UseIter = DefInst->FindUse(UseOp);
UseSSANum = UseIter->GetSSANum();
this->GetFunc()->ResetProcessedBlocks();
benign = DefInst->IsOpSourceZeroExtendedMove(UseOp, UseSSANum, false);
}
}
if (benign) {
IdiomCode = 12;
}
}
// Third case: Subtract original value from shifted value, unsigned. If the shift reduced the original value,
// you will have an underflow. Right shifts always reduce the unsigned value, and left shifts reduce the unsigned
// value in many cases (but not for signed values).
else if (!benign) {
// Check for UNSIGNED.
if (DefIsUnsigned) {
// Does the subtraction use a value from a shift?
UseIter = DefInst->FindUse(DefOp);
if (UseIter != DefInst->GetLastUse()) {
int UseSSANum = UseIter->GetSSANum();
ea_t UseDefAddr = this->GetDefAddrFromUseAddr(DefOp, DefAddr, UseSSANum, LocalDefName);
if (UseDefAddr >= this->GetFirstAddr()) {
// Limit to the simple case in which UseDefAddr is in our block, not Phi function or function entry marker inst.
SMPInstr *UseDefInst = this->GetFunc()->GetInstFromAddr(UseDefAddr);
if (UseDefInst->MDIsShiftOrRotate()) {
// Find USE that got shifted.
UseIter = UseDefInst->FindUse(DefOp);
if (UseIter != UseDefInst->GetLastUse()) {
UseSSANum = UseIter->GetSSANum();
// At this point, we might still have sequence:
// mov edi,eax
// shl edi,5
// sub edi,eax
//
// We have backtracked from the subtraction to the USE of EDI in the shift. Now we need to
// find the move that is the DEF of this USE of EDI, i.e. we need to find EAX.
UseDefAddr = this->GetDefAddrFromUseAddr(DefOp, UseDefAddr, UseSSANum, LocalDefName);
if (UseDefAddr >= this->GetFirstAddr()) {
SMPInstr *MoveInst = this->GetFunc()->GetInstFromAddr(UseDefAddr);
if (MoveInst->MDIsMoveInstr()) {
op_t MoveSourceOp = MoveInst->GetMoveSource();
// Now for the $64,000 question: Is MoveSourceOp the same operand as
// is subtracted in DefInst?
// NOTE: We should probably limit this check to register or direct stack operands.
// We are currently matching MoveSourceOp to the subtrahend operand on immediate
// value cases, e.g. 0x80a7884 in sudoku.exe with immediate value 1.
UseIter = DefInst->FindUse(MoveSourceOp);
if (UseIter != DefInst->GetLastUse()) {
// Found it. The value that got shifted later had the unshifted
// original value subtracted from the shifted value, which will
// produce a benign unsigned underflow quite often.
benign = true;
IdiomCode = 16;
}
}
}
}
}
}
}
}
}
} // end if (UnderflowOpcode && MDIsDataFlowOpnd())
// Fourth case: lea reg, [basereg+indexreg*scalefactor+offset], where
// basereg and indexreg both got their values from condition codes, so the
// computational values are too small for non-benign overflow or underflow.
else if (DefInst->MDIsLoadEffectiveAddressInstr()) {
UseOp = DefInst->GetLeaMemUseOp();
int BaseReg, IndexReg;
ushort ScaleFactor;
ea_t offset;
MDExtractAddressFields(UseOp, BaseReg, IndexReg, ScaleFactor, offset);
bool SafeBaseReg = (BaseReg == R_none);
bool SafeIndexReg = (IndexReg == R_none);
op_t SearchOp = InitOp;
SearchOp.type = o_reg;
SearchOp.dtyp = DefInst->GetOperandDtypField();
if (!SafeBaseReg) {
SearchOp.reg = BaseReg;
UseIter = DefInst->FindUse(SearchOp);
assert(UseIter != DefInst->GetLastUse());
UseSSANum = UseIter->GetSSANum();
this->GetFunc()->ResetProcessedBlocks();
SafeBaseReg = DefInst->IsOpSourceConditionCode(SearchOp, UseSSANum);
}
if (SafeBaseReg && (!SafeIndexReg)) {
// We avoid redundant work when BaseReg == IndexReg.
if (IndexReg == BaseReg) {
SafeIndexReg = true;
}
else {
SearchOp.reg = IndexReg;
UseIter = DefInst->FindUse(SearchOp);
assert(UseIter != DefInst->GetLastUse());
UseSSANum = UseIter->GetSSANum();
this->GetFunc()->ResetProcessedBlocks();
SafeIndexReg = DefInst->IsOpSourceConditionCode(SearchOp, UseSSANum);
}
}
if (SafeBaseReg && SafeIndexReg) { // We could check for huge offset values here (corner case) !!!!****!!!!
benign = true;
IdiomCode = 8;
}
}
}
#if STARS_AGGRESSIVE_BENIGN_POINTER_ARITHMETIC
if (!benign && UnderflowOpcode && DefIsUnsigned) {
// Search for a sequence of SUB then ADD operations that
// are applied to a POINTER type.
InstIter = this->GetInstIterFromAddr(DefAddr);
assert(InstIter != this->GetLastInst());
DefIter = DefInst->FindDef(DefOp);
assert(DefIter != DefInst->GetLastDef());
SMPOperandType DefType = DefIter->GetType();
#if 0 // Make it apply to all UNSIGNED; POINTERs are already IDIOM 18
if (IsDataPtr(DefType)) {
#endif
// Restrict pattern to POINTER -= [operand1]; POINTER += [operand2]
// in consecutive instructions. Both instructions could overflow, while
// producing a valid result after canceling each other out.
++InstIter;
if (InstIter != this->GetLastInst()) {
SMPInstr *DefInst2 = (*InstIter);
if (DefInst2->MDIsAddition()) {
UseIter = DefInst2->FindUse(DefOp);
if (UseIter != DefInst2->GetLastUse()) {
// POINTER DefOp is USE (and also DEF, which we did not check explicitly)
// in addition after being re-DEFed by the original subtraction inst.
benign = true;
IdiomCode = 23;
DefInst2->SetSuppressNumericAnnotation();
}
}
}
#if 0
}
#endif
}
#endif
if (!benign) {
// Bitwise NOT is likely to produce an overflow/underflow for a subsequent add/subtract.
#if 0
if (RegDef) {
#endif
// DEF is also USE in addition or subtraction ...
if (UseIter != DefInst->GetLastUse()) { // ... but not always on lea opcode
if (SpecialSourceFound && SourceInst->MDIsBitwiseNotOpcode()) {
benign = true;
IdiomCode = 21;
}
}
#if 0
}
#endif
#if 0
else if (MDIsDirectStackAccessOpnd(DefOp, this->GetFunc()->UsesFramePointer())){
// We need the canonicalized stack operand as found in DEFs and USEs.
UseOp = DefInst->MDGetMemUseOp(); // DEF is also USE in addition or subtraction ...
UseIter = DefInst->FindUse(UseOp);
if (UseIter != DefInst->GetLastUse()) { // ... but not always on lea opcode
UseSSANum = UseIter->GetSSANum();
if (SourceInst->MDIsBitwiseNotOpcode()) {
benign = true;
IdiomCode = 21;
}
}
}
#endif
}
if (!benign) {
// Look for bitwise NOT idiom on USE-only addend or subtrahend.
UseOp = DefInst->GetUseOnlyAddSubOp();
if (UseOp.type == o_reg) {
CanonicalizeOpnd(UseOp);
UseIter = DefInst->FindUse(UseOp);
if (UseIter != DefInst->GetLastUse()) {
UseSSANum = UseIter->GetSSANum();
bool LocalName = this->IsLocalName(UseOp);
this->GetFunc()->ResetProcessedBlocks();
if (DefInst->IsOpSourceBitwiseNot(UseOp, UseSSANum)) {
benign = true;
IdiomCode = 21;
}
}
}
else if (MDIsDirectStackAccessOpnd(UseOp, this->GetFunc()->UsesFramePointer())) {
// We need the canonicalized stack operand as found in DEFs and USEs.
UseOp = DefInst->MDGetMemUseOp();
assert(o_void != UseOp.type);
UseIter = DefInst->FindUse(UseOp);
assert(UseIter != DefInst->GetLastUse());
UseSSANum = UseIter->GetSSANum();
this->GetFunc()->ResetProcessedBlocks();
if (DefInst->IsOpSourceBitwiseNot(UseOp, UseSSANum)) {
benign = true;
IdiomCode = 21;
}
}
}
if (!benign && !UnderflowOpcode && DefIsUnsigned) {
// Search for a sequence of ADD, OR, and AND operations that
// use constant operands that add up to an UNSIGNED OVERFLOW.
InstIter = this->GetInstIterFromAddr(DefAddr);
assert(InstIter != this->GetLastInst());
int32 ImmedValue = (int32) (*InstIter)->MDGetImmedUse();
// NOTE: If ImmedValue is very large, we catch this elsewhere as IDIOM 11.
if (ImmedValue > 0) {
vector<SMPInstr *>::reverse_iterator RevInstIter(InstIter);
int32 ConstLimit = 0x7fffffff - ImmedValue;
while (RevInstIter != this->GetRevInstEnd()) {
SMPInstr *SearchInst = (*RevInstIter);
DefIter = SearchInst->FindDef(DefOp);
if (DefIter != SearchInst->GetLastDef()) { // found previous DEF
if (SearchInst->MDIsBitwiseAndOpcode() || SearchInst->MDIsBitwiseOrOpcode() || SearchInst->MDIsAddition()) {
ImmedValue = (int32) SearchInst->MDGetImmedUse();
if (0 < ImmedValue) {
if (ImmedValue >= ConstLimit) {
benign = true;
IdiomCode = 22;
break; // no need to search further
}
else {
ConstLimit -= ImmedValue; // set new limiting value
}
}
else {
break; // not the pure chain we are searching for
}
}
else {
break; // not the pure chain we are searching for
}
}
++RevInstIter;
}
}
}
return benign;
} // end of SMPBasicBlock::IsBenignOverflowDEF()
// Is subword of DefOp written later, before TruncAddr?
bool SMPBasicBlock::IsDEFWrittenWithTruncation(op_t DefOp, int DefSSANum, ea_t DefAddr, ea_t TruncAddr, bool PhiDEF) {
assert(o_reg == DefOp.type);
op_t SearchOp = DefOp;
CanonicalizeOpnd(SearchOp);
vector<SMPInstr *>::iterator InstIter;
bool FoundSubwordWrite = false;
InstIter = this->GetInstIterFromAddr(DefAddr);
if (!PhiDEF) {
// DefAddr is just first addr in block with PhiDEF, else it is real DefAddr that should be skipped.
++InstIter;
}
while (InstIter != this->GetLastInst()) {
// Search for subword write of DefOp/DefSSANum.
SMPInstr *CurrInst = (*InstIter);
ea_t InstAddr = CurrInst->GetAddr();
if (InstAddr >= TruncAddr)
break; // else we will find the apparent truncation we started with!
// Re-DEF of DefOp terminates search unless it is a right shift.
// A right shift often precedes a subword write, e.g.:
// edx := ...
// ecx := edx; // need to recurse into ecx chain here
// ecx := ecx >> 8; // don't terminate ecx chain search yet
// mem := cl (subword of ecx) // found subword write
set<DefOrUse, LessDefUse>::iterator DefIter = CurrInst->FindDef(SearchOp);
if (DefIter != CurrInst->GetLastDef()) { // found re-DEF
if (CurrInst->MDIsShiftRight()) {
// Reset DefSSANum and DefAddr and recurse.
FoundSubwordWrite = this->IsDEFWrittenWithTruncation(DefOp, DefIter->GetSSANum(), InstAddr, TruncAddr, false);
}
break; // we always terminate after re-DEF; either we recursed or we failed our search.
}
set<DefOrUse, LessDefUse>::iterator UseIter = CurrInst->FindUse(SearchOp);
if (UseIter != CurrInst->GetLastUse()) { // Used, so instruction might be relevant.
if (CurrInst->MDIsMoveInstr()) { // register DefOp might be copied somewhere
op_t MoveSourceOp = CurrInst->GetMoveSource();
CanonicalizeOpnd(MoveSourceOp);
if (IsEqOp(MoveSourceOp, SearchOp)) { // SearchOp is being copied.
// Subword write of DefOp is successful detection.
if (CurrInst->MDIsReducedWidthMove()) { // Subword of SearchOp is being copied.
FoundSubwordWrite = true;
break;
}
else { // full-width move
DefIter = CurrInst->GetFirstNonFlagsDef();
op_t MoveDestOp = DefIter->GetOp();
if (o_reg == MoveDestOp.type) { // recurse into copy reg chain
int MoveDestSSANum = DefIter->GetSSANum();
FoundSubwordWrite = this->IsDEFWrittenWithTruncation(MoveDestOp, MoveDestSSANum, InstAddr, TruncAddr, false);
if (FoundSubwordWrite)
break; // success, else continue current chain
}
else { // copied to memory; do not recurse, but keep searching.
;
}
}
}
} // end if Move instr
} // end if USEd
++InstIter;
} // end while all insts
return FoundSubwordWrite;
} // end of SMPBasicBlock::IsDEFWrittenWithTruncation()
// We don't care if we truncate computing some DEFs, because of how they are used.
// Return true when we detect one of these cases.
bool SMPBasicBlock::IsBenignTruncationDEF(op_t DefOp, int DefSSANum, size_t DefAddr, int &IdiomCode) {
bool benign = false;
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator UseIter, UseIter2, DefIter;
op_t UseOp, SearchOp = InitOp, UseOp2;
unsigned short SignMask;
bool FoundTruncationDef = false; // Found apparent truncation move
SMPInstr *TruncationInst = NULL;
size_t UseBitWidth; // Bit width involved in truncation move
size_t BytesMasked;
bool FoundSubregUse = false; // Found next use of truncated DEF, which appears to make truncation benign
int UseSSANum = -1, UseSSANum2;
// First, we find the USEs of the DEF.
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
size_t InstAddr = CurrInst->GetAddr();
if (InstAddr == DefAddr) {
// In the truncating instruction, if we have a sub-register that was originally
// DEFed as its enclosing register, it appears to be a truncation. However, it
// could be that the rest of the register is used later, not discarded, e.g.:
// mov [ebp-12],ax ; looks like EAX is being truncated to AX and stored
// shr eax,16 ; gets upper 16 bits into lower 16 bits
// mov [ebp-14],ax ; store what used to be the upper 16 bits of EAX
// The first instruction will trigger a CHECK TRUNCATION annotation that
// causes false positives. We need to analyze the context of the instruction
// to see that the whole register EAX was used, so no truncation occurred.
// The context analysis in the basic block will mark the second move as
// a "truncation" that should be ignored, so we can later avoid performing
// redundant analysis.
if ((CurrInst->GetOptType() == 3) && (!CurrInst->MDIsSignedLoad(SignMask))) {
// We have a regular load, not a sign-extended or zero-extended load.
// This is the kind of load that could look like a truncation, if the
// USE has smaller width than the DEF. Precise analysis of the width of
// the USE and DEF occurs in SMPInstr::EmitIntegerErrorAnnotations(), but
// we need only a good first cut here.
UseOp = CurrInst->GetMoveSource();
SearchOp = UseOp;
if (UseOp.type == o_reg) {
SearchOp = UseOp;
CanonicalizeOpnd(SearchOp);
}
else {
break; // Not a sub-register, cannot fit the pattern
}
UseIter = CurrInst->FindUse(SearchOp);
assert(UseIter != CurrInst->GetLastUse());
UseSSANum = UseIter->GetSSANum();
if (UseIter->DoesNotTruncate()) {
benign = true; // already analyzed
IdiomCode = 2;
break;
}
FoundTruncationDef = true;
TruncationInst = CurrInst;
UseBitWidth = 8 * GetOpDataSize(UseOp);
if (MD_NORMAL_MACHINE_BITWIDTH <= UseBitWidth) {
// Cannot be truncation; exit.
break;
}
}
}
else if (FoundTruncationDef) {
if (!FoundSubregUse) {
// Find next USE of SearchOp.
UseIter2 = CurrInst->FindUse(SearchOp);
if (UseIter2 != CurrInst->GetLastUse()) {
int UseSSANum2 = UseIter2->GetSSANum();
if (UseSSANum != UseSSANum2) {
break; // have re-DEFed; stop following SearchOp
}
// Found use of SearchOp+DefSSANum. Must be shift or rotate to fit pattern.
if (CurrInst->MDIsShiftOrRotate()) {
// If we shift or rotate by UseBitWidth bits, even if we don't make
// an exact full circle, we can pattern match a simpler pattern, e.g.:
// mov <memory>,dl
// shr edx,8
// loop back to process next byte in edx
// If we see this pattern, we go ahead and mark the move as non-truncating.
// Passing false as the second argument makes the check less restrictive.
if (CurrInst->ShiftMakesUpperBitsLower(UseBitWidth, false)) {
// At least it matches the less restrictive two-inst sequence.
benign = true;
IdiomCode = 2;
// Set the NoTruncate flag in the first instruction for the sub-reg UseOp.
TruncationInst->SetUseNoTruncate(SearchOp, true);
if (CurrInst->ShiftMakesUpperBitsLower(UseBitWidth, true)) {
FoundSubregUse = true;
}
}
} // end if shift or rotate
else if (CurrInst->MDIsSubregMaskInst(BytesMasked)) {
// If we are masking off subreg regions, then we are operating on
// less than the full register after the truncation, so the truncation
// is almost certainly benign.
benign = true;
IdiomCode = 14;
break; // Masking inst is redefining SearchOp
}
} // end if found SearchOp in CurrInst
else {
DefIter = CurrInst->FindDef(SearchOp);
if (DefIter != CurrInst->GetLastDef()) {
// SearchOp is not used as subreg yet, but is re-DEFed. Failed to match.
break;
}
}
}
else {
// Found apparent truncation, found shift that seems to make it benign.
// Now we need to see the shifted bits (former upper bits) get stored
// so we can mark both store instructions as benign.
UseIter2 = CurrInst->FindUse(SearchOp);
if (UseIter2 != CurrInst->GetLastUse()) {
if ((CurrInst->GetOptType() == 3) && (!CurrInst->MDIsSignedLoad(SignMask))) {
UseOp2 = UseIter2->GetOp();
size_t UseBitWidth2 = 8 * GetOpDataSize(UseOp2);
if (UseBitWidth == UseBitWidth2) {
// Entire pattern matched. Moved lower bits, shifted or rotated by
// stored bit width, then moved new lower bits.
// Avoid redundant computation on sub-reg UseOp2 in 3rd instruction by setting its flag.
CurrInst->SetUseNoTruncate(SearchOp, true);
}
}
break; // Found whole pattern, or failed to find third inst in pattern.
}
else {
DefIter = CurrInst->FindDef(SearchOp);
if (DefIter != CurrInst->GetLastDef()) {
// SearchOp is not written as subreg yet, but is re-DEFed. Failed to match.
break;
}
}
} // end if (!FoundSubregUse) ... else ...
} // end if (InstAddr == DefAddr) ... else if (FoundTruncationDef) ...
} // end for all insts in block
if (benign)
return true;
SMPInstr *DefInst = this->GetFunc()->GetInstFromAddr(DefAddr);
ea_t SourceInstAddr = BADADDR;
SMPInstr *SourceInst = NULL;
int DefUseSSANum = SMP_SSA_UNINIT;
bool SpecialSourceFound = false;
bool LeaDef = DefInst->MDIsLoadEffectiveAddressInstr();
bool UseFP = this->GetFunc()->UsesFramePointer();
UseIter = DefInst->FindUse(DefOp); // DEF is also USE in addition, subtraction, etc.
if (MDIsDataFlowOpnd(DefOp, UseFP) && (UseIter != DefInst->GetLastUse())) {
DefUseSSANum = UseIter->GetSSANum();
this->GetFunc()->ResetProcessedBlocks();
SpecialSourceFound = DefInst->IsOpSourceSpecial(DefOp, DefUseSSANum, true, SourceInstAddr);
if (SpecialSourceFound) {
SourceInst = this->GetFunc()->GetInstFromAddr(SourceInstAddr);
if (SourceInst->IsReducedWidthDef()) {
benign = true;
IdiomCode = 24;
}
}
}
if (!benign && (o_reg == SearchOp.type) && (-1 != UseSSANum)) {
// See if truncation use is a copy of another register that gets subword masked, which
// is a sign that the truncation use is also only valid for the lower bits.
bool LocalName = this->IsLocalName(SearchOp);
ea_t UseDefAddr = this->GetDefAddrFromUseAddr(SearchOp, DefAddr, UseSSANum, LocalName);
if ((BADADDR != UseDefAddr) && (UseDefAddr > this->GetFunc()->GetNumBlocks())) {
// We have a valid inst addr (not Phi block number). See if it is a reg to reg copy.
SMPInstr *CopyInst = this->GetFunc()->GetInstFromAddr(UseDefAddr);
if (CopyInst->MDIsMoveInstr()) {
unsigned short SignMask;
if (CopyInst->MDIsSignedLoad(SignMask)) {
// Truncation use came from a zero-extended or sign-extended load. So,
// we know that the later truncation store is probably a benign truncation.
IdiomCode = 14;
benign = true;
}
else { // regular move. Is it reg to reg?
UseOp2 = CopyInst->GetMoveSource();
if (o_reg == UseOp2.type) {
// If UseOp2, the source of our truncation store USE operand,
// ever has a subreg masked off, then our truncation is probably
// benign.
CanonicalizeOpnd(UseOp2);
SMPBasicBlock *CopyBlock = CopyInst->GetBlock();
UseIter2 = CopyInst->FindUse(UseOp2);
assert(UseIter2 != CopyInst->GetLastUse());
int DefSSANum2 = UseIter2->GetSSANum();
// NOTE: UseDefAddr is not actually the DefAddr of UseOp2; it
// is the addr at which UseOp2 was moved into our truncation move
// USE, SearchOp. But we only want to see the USEs of UseOp2 that
// come after the reg to reg copy.
benign = CopyBlock->IsDefMasked(UseOp2, DefSSANum2, UseDefAddr);
if (benign)
IdiomCode = 14;
}
}
}
}
}
if (!benign && (o_reg == SearchOp.type) && (-1 != UseSSANum)) {
// Check for case in which a copy of the DEF corresponding to the subword USE
// gets written as a subword. This occurs in patterns that write in pieces such as:
// edx := ...
// ecx : = edx;
// write subword of ecx ; not a truncation
// ecx := edx; get original copy
// write different subword of ecx ; not a truncation
// etc.
// write subword of edx ; not really a truncation
bool LocalName = this->IsLocalName(SearchOp);
ea_t UseDefAddr = this->GetDefAddrFromUseAddr(SearchOp, DefAddr, UseSSANum, LocalName);
if (BADADDR != UseDefAddr) {
// Check for Phi DEF instead of inst DEF.
bool PhiDEF = false;
if (UseDefAddr <= this->GetFunc()->GetNumBlocks()) {
// For our purposes, we just want to search the block for subword writes, so we can pretend
// the DEF addr is right before the block.
PhiDEF = true;
SMPBasicBlock *DefBlock = this->GetFunc()->GetBlockByNum(UseDefAddr);
UseDefAddr = DefBlock->GetFirstAddr();
}
SMPInstr *UseDefInst = this->GetFunc()->GetInstFromAddr(UseDefAddr);
benign = UseDefInst->GetBlock()->IsDEFWrittenWithTruncation(SearchOp, UseSSANum, UseDefAddr, DefAddr, PhiDEF);
if (benign)
IdiomCode = 2;
}
}
#if SMP_MEASURE_NUMERIC_ANNOTATIONS
if (benign) {
++SuppressTruncationRegPiecesAllUsed;
}
#endif
return benign;
} // end of SMPBasicBlock::IsBenignTruncationDEF()
// Does DefOp+DefSSANum get subreg masked before it gets re-DEFined?
bool SMPBasicBlock::IsDefMasked(op_t DefOp, int DefSSANum, ea_t DefAddr) {
bool MaskingDetected = false;
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator UseIter, DefIter;
op_t UseOp, SearchOp = DefOp;
int UseSSANum;
ea_t InstAddr;
size_t BytesMasked;
if (o_reg == DefOp.type) {
CanonicalizeOpnd(SearchOp);
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
InstAddr = CurrInst->GetAddr();
if (InstAddr > DefAddr) {
UseIter = CurrInst->FindUse(SearchOp);
if (UseIter != CurrInst->GetLastUse()) {
UseSSANum = UseIter->GetSSANum();
if (UseSSANum == DefSSANum) {
if (CurrInst->MDIsSubregMaskInst(BytesMasked)) {
MaskingDetected = true;
break;
}
}
else {
// Must have been re-DEFed.
break;
}
}
DefIter = CurrInst->FindDef(SearchOp);
if (DefIter != CurrInst->GetLastDef()) {
// Re-DEF. Did not find masking inst.
break;
}
}
}
}
return MaskingDetected;
} // end of SMPBasicBlock::IsDefMasked()
// Is DEF later passed as an argument to a critical system or lib call? If so, return true and put
// the integer error info string in SinkString. If not, leave SinkString empty and return false.
// Recurse through successor blocks if needed to find all USEs of the DEF.
bool SMPBasicBlock::IsCriticalSink(op_t DefOp, int DefSSANum, std::string &SinkString) {
// Call recursive helper that finds argument-passing USEs of the DEF.
op_t AlternateDefOp = InitOp;
bool FoundSink = this->UseHasCriticalSink(DefOp, DefSSANum, AlternateDefOp, SMP_SSA_UNINIT, SinkString);
return FoundSink;
} // end of SMPBasicBlock::IsCriticalSink()
// Can we find USE being passed to a critical system or library call?
bool SMPBasicBlock::UseHasCriticalSink(op_t DefOp, int DefSSANum, op_t DefOp2, int DefSSANum2, std::string &SinkString) {
bool FoundSink = false;
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator UseIter, DefIter;
bool FoundArgPass = false;
int SearchSSANum = DefSSANum;
int SearchSSANum2 = DefSSANum2;
ea_t InstAddr; // for debugging, breakpoints, etc.
size_t ArgumentNumber = 7; // init to bad number
// avoid infinite recursion
if (this->IsProcessed()) {
return false;
}
this->SetProcessed(true);
// We need to make the recursion robust by finding DefOp in Phi functions
// and altering the DefSSANum we are searching for.
set<SMPPhiFunction, LessPhi>::iterator CurrPhi = this->FindPhi(DefOp);
if (CurrPhi != this->GetLastPhi()) {
// Found Phi function for DefOp. That means we will not be finding DefSSANum for
// DefOp in this block or its successors, because the Phi function will redefine
// to a new SSA number.
size_t PhiNumUses = CurrPhi->GetPhiListSize();
bool FoundPhiUse = false;
for (size_t i = 0; i < PhiNumUses; ++i) {
// Confirm that DefSSANum was actually a Phi USE in this block.
if (CurrPhi->GetUseSSANum(i) == DefSSANum) {
FoundPhiUse = true;
break;
}
}
if (FoundPhiUse) {
SearchSSANum = CurrPhi->GetDefSSANum(); // new SSA name to search for is Phi DEF
}
}
// Do the same for DefOp2/DefSSANum2.
if (o_void != DefOp2.type) {
CurrPhi = this->FindPhi(DefOp2);
if (CurrPhi != this->GetLastPhi()) {
// Found Phi function for DefOp2. That means we will not be finding DefSSANum2 for
// DefOp2 in this block or its successors, because the Phi function will redefine
// to a new SSA number.
size_t PhiNumUses = CurrPhi->GetPhiListSize();
bool FoundPhiUse = false;
for (size_t i = 0; i < PhiNumUses; ++i) {
// Confirm that DefSSANum2 was actually a Phi USE in this block.
if (CurrPhi->GetUseSSANum(i) == DefSSANum2) {
FoundPhiUse = true;
break;
}
}
if (FoundPhiUse) {
SearchSSANum2 = CurrPhi->GetDefSSANum(); // new SSA name to search for is Phi DEF
}
}
}
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
InstAddr = CurrInst->GetAddr();
// Two stage search: Find argument pass, then find next call instruction.
if (!FoundArgPass) {
UseIter = CurrInst->FindUse(DefOp);
if (UseIter != CurrInst->GetLastUse()) {
int UseSSANum = UseIter->GetSSANum();
if (UseSSANum == SearchSSANum) {
// Found a use that matches the DEF. Is it passed as an argument?
if (CurrInst->MDIsArgumentPass(ArgumentNumber)) {
FoundArgPass = true;
}
else if (CurrInst->MDIsMoveInstr() && (o_void == DefOp2.type)) {
// DefOp is getting stored, but not as an argument pass.
// Hard to say if we should keep following DefOp or follow
// the stored copy. Let's try following the stored copy also if
// it is a register or stack location.
DefIter = CurrInst->GetFirstNonFlagsDef();
assert(DefIter != CurrInst->GetLastDef());
op_t NewDefOp = DefIter->GetOp();
if (MDIsDataFlowOpnd(NewDefOp, this->GetFunc()->UsesFramePointer())) {
// Follow NewDefOp from now on in addition to DefOp.
CanonicalizeOpnd(NewDefOp);
DefOp2 = NewDefOp;
SearchSSANum2 = DefIter->GetSSANum();
}
}
else { // Stop searching for DefOp if it gets redefined.
DefIter = CurrInst->FindDef(DefOp);
if (DefIter != CurrInst->GetLastDef()) {
// DefOp was USE and DEF in CurrInst.
if (o_void != DefOp2.type) {
// We have an alternate DEF to search for. Make it primary.
DefOp = DefOp2;
SearchSSANum = SearchSSANum2;
DefOp2 = InitOp; // No more alternate.
SearchSSANum2 = SMP_SSA_UNINIT;
}
else { // No alternate to search for; search has failed.
DefOp = InitOp;
SearchSSANum = SMP_SSA_UNINIT;
break;
}
}
}
}
}
else if (o_void != DefOp2.type) { // DefOp is not used; search for DefOp2
UseIter = CurrInst->FindUse(DefOp2);
if (UseIter != CurrInst->GetLastUse()) {
int UseSSANum = UseIter->GetSSANum();
if (UseSSANum == SearchSSANum2) {
// Found a use that matches the DEF. Is it passed as an argument?
if (CurrInst->MDIsArgumentPass(ArgumentNumber)) {
FoundArgPass = true;
}
else if (CurrInst->MDIsMoveInstr()) { // DefOp2 is copied somewhere
// We cannot follow a third location currently, but we can see
// if DefOp2 is redefining DefOp in this move, and get a new
// SearchSSANum for DefOp in that case.
DefIter = CurrInst->FindDef(DefOp);
if (DefIter != CurrInst->GetLastDef()) {
// DefOp2 was copied to DefOp.
SearchSSANum = DefIter->GetSSANum(); // new DefOp/DefSSANum pair to search for.
}
}
else { // Stop searching for DefOp2 if it gets redefined.
DefIter = CurrInst->FindDef(DefOp2);
if (DefIter != CurrInst->GetLastDef()) {
// DefOp2 was USE and DEF in CurrInst.
DefOp2 = InitOp; // No more alternate.
SearchSSANum2 = SMP_SSA_UNINIT;
}
}
}
}
}
}
else { // found arg pass, need to find call
if (CurrInst->GetDataFlowType() == CALL) {
string CalleeName = CurrInst->GetTrimmedCalledFunctionName();
if (!(CalleeName.empty())) {
GetSinkStringForCallName(CalleeName, SinkString);
if (!(SinkString.empty())) {
// ArgumentNumber needs to be 0 for malloc(), 0 or 1 for calloc(),
// and 1 for realloc.
if (ArgumentNumber < 2) {
bool FoundMalloc = (0 == CalleeName.compare("malloc"));
bool FoundCalloc = (0 == CalleeName.compare("calloc"));
bool FoundRealloc = (0 == CalleeName.compare("realloc"));
if (((ArgumentNumber == 0) && (FoundMalloc || FoundCalloc))
|| ((ArgumentNumber == 1) && (FoundCalloc || FoundRealloc))) {
FoundSink = true;
}
}
}
}
break;
}
}
} // end for all instructions
if (!FoundArgPass) {
if (!this->IsLiveOut(DefOp2)) {
// Cannot search for DefOp2 if not LiveOut.
DefOp2 = InitOp;
SearchSSANum2 = SMP_SSA_UNINIT;
}
if (!this->IsLiveOut(DefOp)) {
// Search for DefOp2 instead of DefOp.
DefOp = DefOp2;
SearchSSANum = SearchSSANum2;
DefOp2 = InitOp; // No more alternate.
SearchSSANum2 = SMP_SSA_UNINIT;
}
if (o_void != DefOp.type) {
// Need to recurse through successor blocks to keep searching for arg pass.
list<SMPBasicBlock *>::iterator SuccIter;
for (SuccIter = this->GetFirstSucc(); SuccIter != this->GetLastSucc(); ++SuccIter) {
if ((*SuccIter)->UseHasCriticalSink(DefOp, SearchSSANum, DefOp2, SearchSSANum2, SinkString)) {
FoundSink = true;
break;
}
}
}
}
return FoundSink;
} // end of SMPBasicBlock::UseHasCriticalSink()
// It is safe to emit signedness checks when the very next use of a stack DEF is as
// a sign-extended or zero-extended load. Beyond a single basic block, we need to
// do more analysis. This catches a simple case that is valid across all programs.
bool SMPBasicBlock::IsStackOpNextUsedWithSignedness(op_t StackDefOp, ea_t DefAddr, int SSANum) {
bool SafeCheck = false;
vector<SMPInstr *>::iterator InstIter;
set<DefOrUse, LessDefUse>::iterator UseIter;
ea_t InstAddr; // for debugging, breakpoints, etc.
bool FoundDefInst = false;
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
InstAddr = CurrInst->GetAddr();
// Two stage search: Find DEF instruction, then find next USE;
if (!FoundDefInst) {
FoundDefInst = (InstAddr == DefAddr);
}
else {
UseIter = CurrInst->FindUse(StackDefOp);
if (UseIter != CurrInst->GetLastUse()) {
int UseSSANum = UseIter->GetSSANum();
if (UseSSANum == SSANum) {
// Found next USE of matching SSA name.
// Is it an extended load?
unsigned short DummySignMask;
SafeCheck = CurrInst->MDIsSignedLoad(DummySignMask);
break;
}
}
}
} // end for all instructions
return SafeCheck;
} // end of SMPBasicBlock::IsStackOpNextUsedWithSignedness()
// Find inc/add that makes small negative back into positive. e.g.:
// sbb edx,edx ; unsigned edx becomes 0 or -1; SMPInstr is suppressing underflow false positive.
// add edx,1 ; converts 0 or -1 to 1 or 0 (looks like unsigned overflow); catch this here.
// We also catch the case in which a "not edx" or "and edx,..." or "or edx,..." instruction
// is interposed between the sbb and the add.
void SMPBasicBlock::SuppressAnnotOnSignChangingAddition(op_t DefOp, int DefSSANum, size_t DefAddr) {
vector<SMPInstr *>::iterator DefInstIter = this->GetInstIterFromAddr(DefAddr);
op_t SearchOp = DefOp;
CanonicalizeOpnd(SearchOp);
int SearchSSANum = DefSSANum;
set<DefOrUse, LessDefUse>::iterator UseIter, DefIter;
++DefInstIter;
while (DefInstIter != this->GetLastInst()) {
SMPInstr *CurrInst = (*DefInstIter);
ea_t InstAddr = CurrInst->GetAddr();
if (CurrInst->MDIsSmallPositiveAddition()) {
UseIter = CurrInst->FindUse(SearchOp);
if (UseIter != CurrInst->GetLastUse()) {
if (SearchSSANum == UseIter->GetSSANum()) {
// Found the increment or small addition that will cause false positives.
CurrInst->SetSuppressNumericAnnotation();
break;
}
else {
// We must have moved on past the original def-use chain.
break;
}
}
}
else if (CurrInst->MDIsBitwiseNotOpcode() || CurrInst->MDIsBitwiseAndOpcode() || CurrInst->MDIsBitwiseOrOpcode()) {
UseIter = CurrInst->FindUse(SearchOp);
if (UseIter != CurrInst->GetLastUse()) {
// Bitwise operation is performed on SearchOp.
if (SearchSSANum == UseIter->GetSSANum()) {
// Reset the SearchSSANum that we expect to see in the small addition.
DefIter = CurrInst->GetFirstNonFlagsDef();
op_t NewDefOp = DefIter->GetOp();
if (IsEqOp(DefOp, NewDefOp)) {
SearchSSANum = DefIter->GetSSANum();
}
else {
// Must have an instruction such as "or dontcarereg,ourreg" which
// does not re-DEF ourreg and thus the chain is no longer the pattern
// we are looking for.
break;
}
}
else {
// We must have moved on past the original def-use chain.
break;
}
}
}
++DefInstIter;
}
return;
} // end of SMPBasicBlock::SuppressAnnotOnSignChangingAddition()
// Last-minute prep before emitting numeric annotations
void SMPBasicBlock::AnalyzePrepForNumericAnnotations(void) {
if (this->HasCallInstruction()) {
vector<SMPInstr *>::iterator InstIter;
bool FoundTrustedCall = false;
ea_t FirstTrustedCallAddr = 0xfffffff0;
SMPInstr *CurrInst;
ea_t InstAddr;
// See if we have any calls to system calls that produce trusted output.
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
CurrInst = (*InstIter);
InstAddr = CurrInst->GetAddr();
if (CurrInst->IsNumericTrustedSystemCall()) {
FoundTrustedCall = true;
if (InstAddr < FirstTrustedCallAddr) {
FirstTrustedCallAddr = InstAddr;
}
}
else if (FoundTrustedCall) {
// Already found a trusted call; suppress numeric annotations.
CurrInst->SetSuppressNumericAnnotation();
}
}
if (FoundTrustedCall && this->GetFunc()->IsBlockInAnyLoop(this->GetNumber())) {
// Overflows can occur as numeric values are used in next iteration of the
// loop, so we want to suppress annotations even for insts before the call.
// FUTURE: Make more thorough by following def-use chains. As a first cut, we
// will just deal with the block that has the trusted call in it.
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
CurrInst = (*InstIter);
InstAddr = CurrInst->GetAddr();
if (InstAddr <= FirstTrustedCallAddr) {
CurrInst->SetSuppressNumericAnnotation();
}
else {
break;
}
}
}
}
return;
} // end of SMPBasicBlock::AnalyzePrepForNumericAnnotations()
// Unsigned branch should be treated as unknown signedness because of code idiom?
bool SMPBasicBlock::IsBranchSignednessUnreliable(void) {
// There are two code patterns that make an unsigned branch an unreliable
// basis for inferring that the related operands were unsigned.
//
// First, we are looking for the pattern:
// ja addr1
// jb addr1
// This is a stupid, inefficient way of saying jne addr1. The unsigned
// nature of the operands that produced the flags when compared cannot
// be reliably inferred, because this sequence is the same as a jne even
// for signed operands.
//
// Second, a typical pattern for optimizing compilers:
// Source: if ((x >= 500) && (x <= 520)) where x is a signed int
// Instead of generating two compares and two branches, only
// one branch is needed:
// sub ebx,500
// cmp ebx,20
// ja not_in_range
// The jump-if-above is a trick to catch the less than 500 case (which
// is now a negative value in ebx) by pretending it is a large unsigned
// number, while also catching the greater than 520 case in the same
// conditional branch. One conditional branch is much faster than two
// in a pipelined machine, but it uses an unsigned conditional branch on
// signed data, which screws up our signedness inference.
// Another variation is a small addition to get a range that spans zero to
// be all non-negative:
// add eax,1
// cmp eax,2 ; if ((eax < -1) || (eax > 1)) ...
// ja not_in_range
//
// Third, we look for a pattern such as:
// cmp eax,0xfffffffc
// ja loopexit
// It is unlikely that an unsigned number is being compared to a value so
// close to the maximum unsigned value, with branching resulting. Instead,
// it is common for a decrementing counter to get cut off at a small negative
// value with this code pattern, giving a SIGNED var the false appearance of
// UNSIGNED.
bool JumpAbove = false;
bool JumpBelow = false;
ea_t TargetAddr = BADADDR, BranchAddr = BADADDR;
SMPInstr *BranchInst;
unsigned short opcode;
vector<SMPInstr *>::reverse_iterator InstRevIter;
vector<SMPInstr *>::iterator InstIter;
if (1 == this->InstVec.size()) {
// Might be the second instruction in the sequence.
InstIter = this->GetFirstInst();
BranchInst = (*InstIter);
BranchAddr = BranchInst->GetAddr();
opcode = BranchInst->GetCmd().itype;
JumpAbove = (opcode == NN_ja);
JumpBelow = (opcode == NN_jb);
if (JumpAbove || JumpBelow) {
// We look for the simple pattern of fall-through-only from first block
// to second block.
if (1 == this->Predecessors.size()) {
TargetAddr = BranchInst->GetJumpTarget();
list<SMPBasicBlock *>::iterator PredIter = this->GetFirstPred();
InstRevIter = (*PredIter)->GetRevInstBegin();
BranchInst = (*InstRevIter);
opcode = BranchInst->GetCmd().itype;
if (JumpBelow)
JumpAbove = (opcode == NN_ja);
else if (JumpAbove)
JumpBelow = (opcode == NN_jb);
}
}
}
else {
// Might be the first instruction in the sequence.
InstRevIter = this->GetRevInstBegin();
BranchInst = (*InstRevIter);
BranchAddr = BranchInst->GetAddr();
opcode = BranchInst->GetCmd().itype;
JumpAbove = (opcode == NN_ja);
JumpBelow = (opcode == NN_jb);
if (JumpAbove || JumpBelow) {
// We look for the simple pattern of fall-through-only from first block
// to second block, plus conditional branch target.
if (2 == this->Successors.size()) {
TargetAddr = BranchInst->GetJumpTarget();
list<SMPBasicBlock *>::iterator SuccIter = this->GetFallThroughSucc();
if (SuccIter != this->GetLastSucc()) {
InstIter = (*SuccIter)->GetFirstInst();
BranchInst = (*InstIter);
opcode = BranchInst->GetCmd().itype;
if (JumpBelow)
JumpAbove = (opcode == NN_ja);
else if (JumpAbove)
JumpBelow = (opcode == NN_jb);
}
}
}
}
if (JumpAbove && JumpBelow && (BranchInst->GetJumpTarget() == TargetAddr))
return true;
#if STARS_DETECT_OPTIMIZED_RANGE_CHECK
// Now, search for the second and third cases.
bool OptimizedRangeComparison = false;
bool TooLargeCompareConstant = false;
InstRevIter = this->GetRevInstBegin();
BranchInst = (*InstRevIter);
// Find the flags USE.
op_t UseOp;
UseOp.type = o_reg; // set up a dummy op for searching
UseOp.reg = X86_FLAGS_REG;
set<DefOrUse, LessDefUse>::iterator UseIter = BranchInst->FindUse(UseOp);
assert(UseIter != BranchInst->GetLastUse());
UseOp = UseIter->GetOp(); // get full info in all fields
int UseSSANum = UseIter->GetSSANum();
bool LocalFlags = this->IsLocalName(UseOp);
ea_t DefAddr = this->GetDefAddrFromUseAddr(UseOp, BranchInst->GetAddr(), UseSSANum, LocalFlags);
// Phi DEFs are rarely or never found as the source of the flags for a branch, so keep it simple.
if (DefAddr > this->GetFunc()->GetNumBlocks()) { // DefAddr is an inst, not a Phi DEF.
// In order to fit the pattern, we need to see a comparison to a positive immediate constant.
SMPInstr *CompareInst = this->GetFunc()->GetInstFromAddr(DefAddr);
op_t CompareOperand = InitOp;
uval_t CompareConstant, SubtractConstant;
if (CompareInst->MDIsCompareToPositiveConstant(CompareOperand, CompareConstant)) {
// For the third pattern, we just need to have a really large CompareConstant.
if (CompareConstant >= 0xfffffff0) {
TooLargeCompareConstant = true;
}
else {
// To complete the second pattern, we need CompareOperand to have been DEFed by a
// subtraction of a constant, or the addition of a small positive constant.
if (o_reg == CompareOperand.type) {
CanonicalizeOpnd(CompareOperand);
UseIter = CompareInst->FindUse(CompareOperand);
assert(UseIter != CompareInst->GetLastUse());
UseSSANum = UseIter->GetSSANum();
SMPBasicBlock *CompareBlock = CompareInst->GetBlock(); // just in case it's not this block
bool LocalCompName = CompareBlock->IsLocalName(CompareOperand);
ea_t SubtractAddr = CompareBlock->GetDefAddrFromUseAddr(CompareOperand, DefAddr, UseSSANum, LocalCompName);
if (SubtractAddr > this->GetFunc()->GetNumBlocks()) {
SMPInstr *SubtractInst = this->GetFunc()->GetInstFromAddr(SubtractAddr);
op_t MinuendOp = InitOp;
if (SubtractInst->MDIsSubtractionOfConstant(MinuendOp, SubtractConstant)) {
OptimizedRangeComparison = true;
}
else if (SubtractInst->MDIsSmallPositiveAddition()) {
OptimizedRangeComparison = true;
}
}
}
}
}
}
return (OptimizedRangeComparison || TooLargeCompareConstant);
#else
return false;
#endif
} // end of SMPBasicBlock::IsBranchSignednessUnreliable()
// Find stack adjustment code, if any, after CallAddr.
sval_t SMPBasicBlock::ComputeStackAdjustmentAfterCall(ea_t CallAddr) {
sval_t AdjustmentBytes = 0;
sval_t PriorAdjustmentBytes = 0; // stack deltas before the call
vector<SMPInstr *>::iterator InstIter;
ea_t InstAddr; // for debugging, breakpoints, etc.
bool FoundCallInst = false;
bool FirstBlock = (this->GetFirstAddr() == this->GetFunc()->GetFirstFuncAddr());
for (InstIter = this->GetFirstInst(); InstIter != this->GetLastInst(); ++InstIter) {
SMPInstr *CurrInst = (*InstIter);
InstAddr = CurrInst->GetAddr();
// Two stage search: Find CALL instruction, then find next stack adjustment.
sval_t CurrentDelta = CurrInst->FindStackAdjustment();
SMPitype DataFlowType = CurrInst->GetDataFlowType();
if (!FoundCallInst) {
FoundCallInst = (InstAddr == CallAddr);
if (!FoundCallInst && !FirstBlock) {
PriorAdjustmentBytes += CurrentDelta;
if (JUMP <= DataFlowType) {
// Reset PriorAdjustmentBytes and exit. Basic block is too confusing
// to analyze if multiple calls happen. We cannot tell if stack adjustments
// between the first call and the second call are related to the first call
// or the second call.
PriorAdjustmentBytes = 0;
break;
}
}
}
else {
if (JUMP > DataFlowType) {
if (SMP_STACK_DELTA_ERROR_CODE == CurrentDelta) {
// An error will soon occur, no need for further computations.
AdjustmentBytes = 0;
SMP_msg("INFO: Stack adjustment set to zero due to error code at %lx\n", (unsigned long) InstAddr);
break;
}
else if (SMP_STACK_POINTER_BITWISE_AND_CODE == CurrentDelta) {
; // Ignore AND with stack pointer for now
}
else if (0 != CurrentDelta) {
SMP_msg("INFO: Found stack adjustment of %ld bytes at %lx\n",
(long) CurrentDelta, (unsigned long) InstAddr);
AdjustmentBytes += CurrentDelta;
}
// NOTE: ****!!!!****!!!! We want to find changes in stack direction and terminate
// in the future, in case we see code such as:
//
// call foo
// pop eax ; adjust stack after call to foo, grab return arg and put in eax
// push ebx ; caller-save before call to bar
// call bar
}
else if ((RETURN == DataFlowType)
|| ((!this->GetFunc()->HasExplicitReturnInstruction()) && ((INDIR_JUMP == DataFlowType) || (JUMP == DataFlowType)))) {
// We have been counting up adjustment bytes that precede a RETURN. Those
// adjustments are expected before a RETURN and have nothing to do with
// the function call at CallAddr. If the function has no explicit return instructions, we will
// conservatively treat jumps as probable tail calls, which will later be given the RETURN
// data flow type but have not yet been analyzed and marked.
AdjustmentBytes = 0;
SMP_msg("INFO: Resetting stack adjustment to zero at return inst at %lx\n",
(unsigned long) InstAddr);
break;
}
else {
// We want to break at calls after CallAddr, and other instructions that
// hit this break would terminate the block anyway (e.g. jumps, branches).
break;
}
}
}
if (AdjustmentBytes != 0) {
// PriorAdjustmentBytes is usually negative (making stack space before the call)
// and AdjustmentBytes is usually positive (returning stack space after the call).
// Adding them gets the net adjustment after the call.
AdjustmentBytes += PriorAdjustmentBytes;
}
return AdjustmentBytes;
} // end of SMPBasicBlock::ComputeStackAdjustmentAfterCall()