Newer
Older
// Now, we need to check the phi functions and see if there are Phi USEs of the DefOp.
set<SMPPhiFunction, LessPhi>::iterator UsePhi;
size_t BlockNum;
for (BlockNum = 0; BlockNum < (size_t) this->BlockCount; ++BlockNum) {
UsePhi = this->RPOBlocks.at(BlockNum)->FindPhi(DefOp);
if (UsePhi != this->RPOBlocks.at(BlockNum)->GetLastPhi()) {
// Found phi function for DefOp. See if we can find a USE
// with USE SSANum corresponding to our DEF SSANum.
for (size_t PhiIndex = 0; PhiIndex < UsePhi->GetPhiListSize(); ++PhiIndex) {
if (UsePhi->GetUseSSANum(PhiIndex) == SSANum) {
// We have a Phi USE that matches our DEF.
if (!FirstUseSeen) {
FirstUseSeen = true;
UseType = UsePhi->GetUseType(PhiIndex);
FoundNumeric |= (IsNumeric(UseType));
FoundUnknown |= (IsUnknown(UseType));
FoundUninit |= (IsEqType(UNINIT, UseType));
if (IsDataPtr(UseType)) {
if (FoundPointer) {
if (IsNotEqType(PtrType, UseType)) {
msg("WARNING: Differing ptr types in global chain at Phi:");
msg(" Prev: %d Current: %d BlockNum: %d\n",
PtrType, UseType, BlockNum);
}
PtrType = POINTER;
}
else {
FoundPointer = true;
PtrType = UseType;
}
} // end if matched SSA #
} // end for all Phi USEs
} // end if found matching Phi function for DefOp
} // end for all block numbers in the function
if (FirstUseSeen) {
// Do we have a consistent type?
// If we see any definite POINTER uses, we must set the DEF
// to type POINTER or a refinement of it.
if (FoundPointer)
UseType = PtrType;
else if (FoundNumeric && !FoundUninit && !FoundUnknown)
UseType = NUMERIC;
else
return UNINIT; // no POINTER, but no consistent type
assert(UNINIT != UseType);
if (DebugFlag) msg("Inferring global DEF of type %d\n", UseType);
else { // not FirstUseSeen
// If the block returns, then the DEFs could be used in the caller.
if (!(DefBlock->HasReturn())) {
UseType = UNINIT;
// We probably want to set the DEF type to NUMERIC if there are no uses.
// Have to check these cases out manually in the *.asm first. **!!**
// If they are memory DEFs, we cannot optimize, so we might want to see
// if we can find a reg DEF with no USEs here. We also want to exclude
// warning messages for the caller-saved reg DEFs generated for CALLs.
if ((o_reg == DefOp.type) && (!CallInst)) {
;
#if SMP_WARN_UNUSED_DEFS
msg("WARNING: global DEF with no USEs for SSANum %d DefOp: ",
SSANum);
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
#define SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION 1
#if SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION
// The simple form of conditional type propagation observes that we
// simply need to apply the meet operator over Phi function USEs and
// then propagate any DEF type changes using PropagateGlobalDefType().
// The outermost iteration over all type inference methods in InferTypes()
// will take care of all the propagation that is handled by the work list
// processing in the textbook algorithm.
// Iteration convergence might be slower in the simple approach, but the code
// is much simpler to debug.
bool SMPFunction::ConditionalTypePropagation(void) {
bool changed = false;
list<SMPBasicBlock>::iterator CurrBlock;
vector<list<SMPBasicBlock>::iterator>::iterator CurrRPO;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
for (CurrRPO = this->RPOBlocks.begin(); CurrRPO != this->RPOBlocks.end(); ++CurrRPO) {
CurrBlock = *CurrRPO;
SMPOperandType MeetType;
for (CurrPhi = CurrBlock->GetFirstPhi(); CurrPhi != CurrBlock->GetLastPhi(); ++CurrPhi) {
MeetType = CurrPhi->ConditionalMeetType();
// Here we use a straight equality test, not our macros,
// because we consider it a change if the MeetType is
// profiler derived and the DEFType is not.
if (MeetType == CurrPhi->GetDefType())
continue;
// Change the DEF type to the MeetType and propagate.
op_t DefOp = CurrPhi->GetAnyOp();
CurrPhi = CurrBlock->SetPhiDefType(DefOp, MeetType);
changed = true;
this->ResetProcessedBlocks();
changed |= CurrBlock->PropagateGlobalDefType(DefOp,
MeetType, CurrPhi->GetDefSSANum());
} // end for all phi functions in the current block
} // end for all blocks
return changed;
} // end of SMPFunction::ConditionalTypePropagation()
#else // not SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION
// Apply the SCC (Sparse Conditional Constant) propagation algorithm to
// propagate types starting from unresolved Phi DEFs.
bool SMPFunction::ConditionalTypePropagation(void) {
bool changed = false;
// Collections of Phi functions and instructions that have a DEF
// with type UNINIT for the current global name.
map<int, set<SMPPhiFunction, LessPhi>::iterator> UninitDEFPhis;
vector<list<SMPInstr>::iterator> UninitDEFInsts;
// Work lists of Phi functions and instructions that need to be processed
// according to the SCC algorithm.
list<map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator> PhiWorkList;
list<vector<list<SMPInstr>::iterator>::iterator> InstWorkList;
// Iterate through all global names that are either (1) registers
// or (2) stack locations in SAFE functions.
set<op_t, LessOp>::iterator CurrGlob;
for (CurrGlob = this->GetFirstGlobalName(); CurrGlob != this->GetLastGlobalName(); ++CurrGlob) {
op_t GlobalOp = *CurrGlob;
list<SMPBasicBlock>::iterator CurrBlock;
vector<list<SMPBasicBlock>::iterator>::iterator CurrRPO;
if (MDIsIndirectMemoryOpnd(GlobalOp, this->UseFP))
continue; // need alias analysis to process indirect accesses
if ((GlobalOp.type != o_reg)
&& (!((this->ReturnAddrStatus == FUNC_SAFE) && MDIsStackAccessOpnd(GlobalOp, this->UseFP))))
continue; // not register, not safe stack access
// Set up a map (indexed by SSANum) of iterators to Phi functions
// for the current global name that have UNINIT as the Phi DEF type.
UninitDEFPhis.clear();
UninitDEFInsts.clear();
for (CurrRPO = this->RPOBlocks.begin(); CurrRPO != this->RPOBlocks.end(); ++CurrRPO) {
CurrBlock = *CurrRPO;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi;
CurrPhi = CurrBlock->FindPhi(GlobalOp);
if (CurrPhi != CurrBlock->GetLastPhi()) {
// Found Phi function for current global name.
if (IsEqType(CurrPhi->GetDefType(), UNINIT)) {
// Phi DEF is UNINIT; add Phi to the map.
pair<int, set<SMPPhiFunction, LessPhi>::iterator> TempPair(CurrPhi->GetDefSSANum(), CurrPhi);
bool Inserted = false;
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator WhereIns;
pair<map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator, bool> Result(WhereIns, Inserted);
Result = UninitDEFPhis.insert(TempPair);
assert(Result.second == true);
}
}
} // end for all blocks
// If any Phi DEF had UNINIT as its type, set up a vector of
// iterators to instructions that have UNINIT as the DEF type
// for the current global name.
if (UninitDEFPhis.empty())
continue;
list<SMPInstr>::iterator CurrInst;
for (CurrInst = this->Instrs.begin(); CurrInst != this->Instrs.end(); ++CurrInst) {
set<DefOrUse, LessDefUse>::iterator CurrDef = CurrInst->FindDef(GlobalOp);
if (CurrDef != CurrInst->GetLastDef()) {
// Found DEF of current global name.
if (IsEqType(UNINIT, CurrDef->GetType())) {
UninitDEFInsts.push_back(CurrInst);
}
}
} // end for all instructions
// Put all UNINIT Phi DEFs that have at least one USE
// that is not UNINIT onto the PhiWorkList.
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator CurrUnPhi;
for (CurrUnPhi = UninitDEFPhis.begin(); CurrUnPhi != UninitDEFPhis.end(); ++CurrUnPhi) {
pair<int, set<SMPPhiFunction, LessPhi>::iterator> PhiDefPair(*CurrUnPhi);
if (PhiDefPair.second->HasTypedUses()) {
PhiWorkList.push_back(CurrUnPhi);
}
}
// Iterate until both work lists are empty:
while (!(PhiWorkList.empty() && InstWorkList.empty())) {
// Process Phi items first.
while (!PhiWorkList.empty()) {
// If applying the meet operator over the Phi USE types
// would produce a new DEF type, change the DEF type and
// propagate it, adding Phi functions and instructions that
// received the propagated type to their respective work lists.
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator MapIter;
MapIter = PhiWorkList.front();
PhiWorkList.pop_front(); // remove from work list
pair<int, set<SMPPhiFunction, LessPhi>::iterator> PhiDefPair;
PhiDefPair.first = MapIter->first;
PhiDefPair.second = MapIter->second;
set<SMPPhiFunction, LessPhi>::iterator CurrPhi = PhiDefPair.second;
SMPOperandType MeetType = CurrPhi->ConditionalMeetType();
// Here we use a straight equality test, not our macros,
// because we consider it a change if the MeetType is
// profiler derived and the DEFType is not.
if (MeetType == CurrPhi->GetDefType())
continue;
// At this point, we need to set the DEFType to the MeetType
// and propagate the change. We have a map of all the
// critical Phi functions for this global name, as well
// as a vector of the relevant instructions for this name.
CurrPhi->SetDefType(MeetType);
changed = true;
int DefSSANum = CurrPhi->GetDefSSANum();
map<int, set<SMPPhiFunction, LessPhi>::iterator>::iterator PhiIter;
vector<list<SMPInstr>::iterator>::iterator InstIter;
// Propagate to Phi functions first.
for (PhiIter = UninitDEFPhis.begin(); PhiIter != UninitDEFPhis.end(); ++PhiIter) {
if (DefSSANum == PhiIter->first)
continue; // Skip the Phi that we just changed
for (size_t index = 0; index < PhiIter->second->GetPhiListSize(); ++index) {
if (DefSSANum == PhiIter->second->GetUseSSANum(index)) {
// Matched SSA # to USE. Propagate new type.
PhiIter->second->SetRefType(index, MeetType);
// Add this phi function to the work list.
PhiWorkList.push_back(PhiIter);
}
}
}
#define SMP_COND_TYPE_PROP_TO_INSTS 0
#if SMP_COND_TYPE_PROP_TO_INSTS
// Propagate to instructions with uninit DEFs of global name.
// The idea is that the instructions that hold up type propagation
// are the ones that USE and then DEF the same global name.
// For example, "increment EAX" has to know the type of
// the USE of EAX in order to set the type of the DEF.
#endif
} // end while the PhiWorkList is not empty
#if SMP_COND_TYPE_PROP_TO_INSTS
// The PhiWorkList is empty at this point, so process
// instructions on the InstWorkList.
#endif
} // end while both work lists are not empty
} // end for all global names
return changed;
} // end of SMPFunction::ConditionalTypePropagation()
#endif // end if SMP_SIMPLE_CONDITIONAL_TYPE_PROPAGATION else ...
// Emit all annotations for the function, including all per-instruction
// annotations.
void SMPFunction::EmitAnnotations(FILE *AnnotFile) {
// Emit annotation for the function as a whole.
if (this->StaticFunc) {
qfprintf(AnnotFile, "%10x %6d FUNC LOCAL %s ", this->FuncInfo.startEA,
this->Size, this->FuncName);
}
else {
qfprintf(AnnotFile, "%10x %6d FUNC GLOBAL %s ", this->FuncInfo.startEA,
this->Size, this->FuncName);
}
switch (this->ReturnAddrStatus)
{
case FUNC_UNKNOWN:
{
qfprintf(AnnotFile, "FUNC_UNKNOWN ");
break;
}
case FUNC_SAFE:
{
qfprintf(AnnotFile, "FUNC_SAFE ");
break;
}
case FUNC_UNSAFE:
{
qfprintf(AnnotFile, "FUNC_UNSAFE ");
break;
}
default:
assert(0);
}
if (this->UseFP) {
qfprintf(AnnotFile, "USEFP ");
}
else {
qfprintf(AnnotFile, "NOFP ");
}
if (this->FuncInfo.does_return()) {
#ifdef SMP_DEBUG_FUNC
if (this->IsLeaf())
qfprintf(AnnotFile, "FUNC_LEAF ");
// store the return address
qfprintf(AnnotFile,"%10x ", this->FuncInfo.endEA - 1);
#endif
// Loop through all instructions in the function.
// Output optimization annotations for those
// instructions that do not require full computation
// of their memory metadata by the Memory Monitor SDT.
list<SMPInstr>::iterator CurrInst;
bool AllocSeen = false; // Reached LocalVarsAllocInstr yet?
bool DeallocTrigger = false;
for (CurrInst = Instrs.begin(); CurrInst != Instrs.end(); ++CurrInst) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == CurrInst)
continue; // skip marker instruction
#endif
ea_t addr = CurrInst->GetAddr();
qfprintf(AnnotFile, "%10x %6d INSTR BELONGTO %x \n", addr, 0, GetStartAddr());
if (this->LocalVarsAllocInstr == addr) {
AllocSeen = true;
this->EmitStackFrameAnnotations(AnnotFile, CurrInst);
}
// If this is the instruction which deallocated space
// for local variables, we set a flag to remind us to
// emit an annotation on the next instruction.
// mmStrata wants the instruction AFTER the
// deallocating instruction, so that it processes
// the deallocation after it happens. It inserts
// instrumentation before an instruction, not
// after, so it will insert the deallocating
// instrumentation before the first POP of callee-saved regs,
// if there are any, or before the return, otherwise.
if (addr == this->LocalVarsDeallocInstr) {
DeallocTrigger = true;
}
else if (DeallocTrigger) { // Time for annotation
qfprintf(AnnotFile, "%10x %6d DEALLOC STACK esp - %d %s\n", addr,
LocalVarsSize, LocalVarsSize, CurrInst->GetDisasm());
DeallocTrigger = false;
}
if (this->HasGoodRTLs()) {
CurrInst->EmitTypeAnnotations(this->UseFP, AllocSeen, AnnotFile);
}
else {
CurrInst->EmitAnnotations(this->UseFP, AllocSeen, AnnotFile);
}
if (CurrInst->MDIsReturnInstr() && this->GetReturnAddressStatus() == FUNC_SAFE )
CurrInst->EmitSafeReturn(AnnotFile);
} // end for all instructions
return;
} // end of SMPFunction::EmitAnnotations()
// Debug output dump.
void SMPFunction::Dump(void) {
list<SMPBasicBlock>::iterator CurrBlock;
msg("Debug dump for function: %s\n", this->GetFuncName());
for (size_t index = 0; index < this->IDom.size(); ++index) {
msg("IDOM for %d: %d\n", index, this->IDom.at(index));
}
for (size_t index = 0; index < this->DomTree.size(); ++index) {
msg("DomTree for %d: ", index);
list<int>::iterator DomIter;
for (DomIter = this->DomTree.at(index).second.begin();
DomIter != this->DomTree.at(index).second.end();
++DomIter) {
msg("%d ", *DomIter);
}
msg("\n");
}
msg("Global names: \n");
set<op_t, LessOp>::iterator NameIter;
for (NameIter = this->GlobalNames.begin(); NameIter != this->GlobalNames.end(); ++NameIter) {
msg("index: %d ", ExtractGlobalIndex(*NameIter));
PrintListOperand(*NameIter);
msg("\n");
}
msg("Blocks each name is defined in: \n");
for (size_t index = 0; index < this->BlocksDefinedIn.size(); ++index) {
msg("Name index: %d Blocks: ", index);
list<int>::iterator BlockIter;
for (BlockIter = this->BlocksDefinedIn.at(index).begin();
BlockIter != this->BlocksDefinedIn.at(index).end();
++BlockIter) {
msg("%d ", *BlockIter);
}
msg("\n");
}
for (CurrBlock = this->Blocks.begin(); CurrBlock != this->Blocks.end(); ++CurrBlock) {
// Dump out the function number and data flow sets before the instructions.
CurrBlock->Dump();
}
msg("End of debug dump for function: %s\n", this->GetFuncName());
return;
} // end of SMPFunction::Dump()
// Analyzes the function to see if the return address can be marked as safe
void SMPFunction::MarkFunctionSafe() {
msg(" Analyzing function name %s and isLeaf=%d ", this->GetFuncName(), this->IsLeaf());
#endif
ReturnAddrStatus = FUNC_SAFE;
if (!AnalyzedSP || this->IndirectCalls) {
msg(" Function marked as unsafe %s coz AnalyzedSP = false\n", this->GetFuncName());
msg(" Function marked as unsafe %s coz function has indirect calls\n", this->GetFuncName());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
if (!this->DirectCallTargets.empty()) {
msg(" Function marked as unknown %s \n", this->GetFuncName());
#endif
ReturnAddrStatus = FUNC_UNKNOWN;
}
#if SMP_USE_SWITCH_TABLE_INFO
if (this->UnresolvedIndirectJumps) {
#else
msg(" Function marked as unsafe due to indirect jumps %s\n", this->GetFuncName());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return ;
}
if (this->HasSharedChunks()) {
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
list<SMPInstr>::iterator Instructions;
// while processing the stack pointer write the prolog containing for
// saving frame register and allcating local variables needs to be
// handled
bool SaveEBP = false;
bool XferESPtoEBP = false;
for (Instructions = Instrs.begin(); Instructions != Instrs.end(); Instructions++) {
#if SMP_USE_SSA_FNOP_MARKER
if (this->Instrs.begin() == Instructions)
continue; // skip marker instruction
#endif
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
msg(" Total number of defs for this instruction %d\n", Instructions->NumDefs());
#endif
if (!SaveEBP) { // still looking for "push ebp"
if (Instructions->MDIsPushInstr() && Instructions->GetCmd().Operands[0].is_reg(R_bp)) {
SaveEBP = true;
continue;
}
}
else if (!XferESPtoEBP) { // found "push ebp", looking for "mov ebp,esp"
insn_t CurrCmd = Instructions->GetCmd();
if ((CurrCmd.itype == NN_mov)
&& (Instructions->GetFirstDef()->GetOp().is_reg(R_bp))
&& (Instructions->GetFirstUse()->GetOp().is_reg(R_sp))) {
XferESPtoEBP = true;
continue;
}
}
ea_t address = Instructions->GetAddr();
if (address == this->LocalVarsAllocInstr ||
address == this->LocalVarsDeallocInstr)
continue;
if (Instructions->MDIsStackPointerCopy(this->UseFP)) {
msg(" Function marked as unsafe %s due to stack pointer copy \n ", this->GetFuncName());
msg("%s %x \n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
if (Instructions->MDIsPushInstr()) {
// not exactly sure how to handle this instruction
// for the moment if its a push on a esp or usefp & ebp
// mark as unsafe
if (Instructions->GetCmd().Operands[0].is_reg(R_sp) ||
( this->UseFP && Instructions->GetCmd().Operands[0].is_reg(R_bp))) {
msg(" Function marked as unsafe %s due to push on ebp or esp outside of function header \n", this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
continue;
}
if (Instructions->MDIsPopInstr()) {
// ignore pops for the moment
continue;
}
set<DefOrUse, LessDefUse>::iterator setIterator;
for (setIterator = Instructions->GetFirstDef(); setIterator != Instructions->GetLastDef(); setIterator++) {
op_t Operand = setIterator->GetOp();
clc5q
committed
int BaseReg;
int IndexReg;
ushort ScaleFactor;
ea_t offset;
if (Operand.type == o_mem) {
// now o_mem can have sib byte as well, as
clc5q
committed
// reported by IDA. Check if the base reg is R_none
// and index reg is R_none. If they are, then this is
// probably a global write and can be marked safe.
MDExtractAddressFields(Operand, BaseReg, IndexReg, ScaleFactor, offset);
if ((BaseReg == R_none) && (IndexReg == R_none)) {
// go onto next def
continue;
}
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
if (Operand.type == o_displ) {
clc5q
committed
MDExtractAddressFields(Operand, BaseReg, IndexReg, ScaleFactor, offset);
if ((BaseReg == R_sp) || (this->UseFP && (BaseReg == R_bp))) {
if (IndexReg == R_none) {
if (offset > this->LocalVarsSize ) {
clc5q
committed
msg(" Function marked as unsafe %s due to write above loc variables offset=%x loc=%x\n ", this->GetFuncName(), offset, this->LocalVarsSize);
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
#endif
clc5q
committed
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
else {
clc5q
committed
msg(" Function marked as unsafe %s due to index write above loc variables \n", this->GetFuncName());
msg("%s %x\n", (Instructions)->GetDisasm(), (Instructions)->GetAddr());
clc5q
committed
ReturnAddrStatus = FUNC_UNSAFE;
clc5q
committed
else {
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
if (Operand.type == o_phrase) {
// so phrase is of the form [BASE_REG + IND ]
// if the index register is missing just make sure that
// the displacement is below stack frame top
clc5q
committed
MDExtractAddressFields(Operand, BaseReg, IndexReg, ScaleFactor, offset);
// check the base reg
// if index reg is used mark as unsafe
if ((BaseReg == R_sp || (this->UseFP && BaseReg == R_bp))
&& (IndexReg == R_none)) {
clc5q
committed
msg(" Does function with phrase have displ %s %x ", this->GetFuncName(), Operand.addr);
clc5q
committed
continue;
}
else {
ReturnAddrStatus = FUNC_UNSAFE;
return;
}
}
}
}
} // end of SMPFunction::MarkFunctionSafe()