Use fixpoint analysis correctly.
[dyninst.git] / dyninstAPI / src / stackanalysis.C
1 /*
2  * Copyright (c) 1996-2004 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 #include "dyninstAPI/src/function.h"
43 #include "dyninstAPI/src/symtab.h"
44 #include "instPoint.h"
45
46 #include "instructionAPI/h/InstructionDecoder.h"
47 #include "instructionAPI/h/Result.h"
48 #include "instructionAPI/h/Instruction.h"
49
50 #include <queue>
51 #include <vector>
52
53 #include "stackanalysis.h"
54
55 #include "Annotatable.h"
56
57 #include "debug.h"
58
59 using namespace Dyninst;
60 using namespace InstructionAPI;
61
62 const StackAnalysis::StackHeight StackAnalysis::StackHeight::bottom(StackAnalysis::StackHeight::notUnique);
63 const StackAnalysis::StackHeight StackAnalysis::StackHeight::top(StackAnalysis::StackHeight::uninitialized);
64
65 AnnotationClass <StackAnalysis::HeightTree> StackHeightAnno(std::string("StackHeightAnno"));
66 AnnotationClass <StackAnalysis::PresenceTree> StackPresenceAnno(std::string("StackPresenceAnno"));
67
68
69 //
70 //
71 // Concepts:
72 //
73 // There are three terms we throw around:
74 // 
75 // Stack height: the size of the stack; (cur_stack_ptr - func_start_stack_ptr)
76 // Stack delta: the difference in the size of the stack over the execution of
77 //   a region of code (basic block here). (block_end_stack_ptr - block_start_stack_ptr)
78 // Stack clean: the amount the callee function shifts the stack. This is an x86 idiom.
79 //   On x86 the caller pushes arguments onto the stack (and thus shifts the stack).
80 //   Normally the caller also cleans the stack (that is, removes arguments). However, 
81 //   some callee functions perform this cleaning themselves. We need to account for this
82 //   in our analysis, which otherwise assumes that callee functions don't alter the stack.
83 // 
84
85 bool StackAnalysis::analyze()
86 {
87     stanalysis_printf("Beginning stack analysis for function %s\n",
88                       func->symTabName().c_str());
89     blocks = func->blocks();
90     if (blocks.empty()) return false;
91     
92     blocks = func->blocks();
93     
94     stanalysis_printf("\tSummarizing block effects\n");
95     summarizeBlockDeltas();
96     
97     stanalysis_printf("\tPerforming fixpoint analysis\n");
98     calculateInterBlockDepth();
99
100     stanalysis_printf("\tCreating interval trees\n");
101     createIntervals();
102
103     func->addAnnotation(heightIntervals_, StackHeightAnno);
104     func->addAnnotation(presenceIntervals_, StackPresenceAnno);
105
106     if (dyn_debug_stackanalysis) {
107         debugStackHeights();
108         debugStackPresences();
109     }
110
111     stanalysis_printf("Finished stack analysis for function %s\n",
112                       func->symTabName().c_str());
113
114     return true;
115 }
116    
117 void StackAnalysis::summarizeBlockDeltas() {
118     // STACK HEIGHT:
119     // Foreach block B:
120     //   Let acc = 0;
121     //   Foreach (insn i, offset o) in B:
122     //     Let d = change in stack height at i;
123     //     Let acc += d;
124     //     blockToInsnDeltas[B][o] = d;
125     //   blockHeightDeltas[B] = acc;
126
127     // STACK PRESENCE:
128     // Foreach block B:
129     //   Let d = uninitialized;
130     //   Foreach (insn i, offset o) in B:
131     //     d = change in stack presence at d;
132     //     blockToInsnDeltas[B][o] = d;
133     //   blockHeightDeltas[B] = d;
134
135     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
136         Block *block = *iter;
137         stanalysis_printf("\t Block starting at 0x%lx\n", block->firstInsnOffset());
138
139         StackHeight heightChange(0);
140         StackPresence stackPresence;
141
142         std::vector<std::pair<InstructionAPI::Instruction, Offset> > instances;
143         block->getInsnInstances(instances);
144
145         for (unsigned j = 0; j < instances.size(); j++) {
146             InstructionAPI::Instruction insn = instances[j].first;
147             Offset off = instances[j].second;
148
149             // Can go top...
150             StackHeight delta;
151             computeInsnEffects(block, insn, off, delta, stackPresence);
152             blockToInsnDeltas[block][off] = delta;
153             blockToInsnPresence[block][off] = stackPresence;
154
155             heightChange += delta;
156         }
157         blockHeightDeltas[block] = heightChange;
158         blockPresenceDeltas[block] = stackPresence;
159     }
160 }
161
162 void StackAnalysis::calculateInterBlockDepth() {
163
164     std::queue<Block *> worklist;
165
166     worklist.push(func->entryBlock());
167
168     //BlockHeight_t blockHeights; // This by default initializes all entries to "bottom". 
169
170     while (!worklist.empty()) {
171         Block *block = worklist.front();
172         stanalysis_printf("\t Fixpoint analysis: visiting block at 0x%lx\n", block->firstInsnOffset());
173
174         worklist.pop();
175
176         // Step 1: calculate the meet over the heights of all incoming
177         // intraprocedural blocks.
178
179         std::set<StackHeight> inHeights;
180         std::set<StackPresence> inPresences;
181
182         if (block->isEntryBlock(func)) {
183             // The in height is 0
184             inHeights.insert(StackHeight(0));
185             inPresences.insert(StackPresence(StackPresence::noFrame));
186         }
187         else {
188             std::vector<Edge *> inEdges; block->getSources(inEdges);
189             for (unsigned i = 0; i < inEdges.size(); i++) {
190                 Edge *edge = inEdges[i];
191                 if (edge->getType() == ET_CALL) continue;
192                 inHeights.insert(outBlockHeights[edge->getSource()]);
193                 inPresences.insert(outBlockPresences[edge->getSource()]);
194             }
195         }
196         
197         StackHeight newInHeight = StackHeight::meet(inHeights);
198         StackPresence newInPresence = StackPresence::meet(inPresences);
199
200         // Step 2: see if the input has changed
201
202         if ((newInHeight == inBlockHeights[block]) &&
203             (newInPresence == inBlockPresences[block])) {
204             // No new work here
205             continue;
206         }
207         
208         // Step 3: calculate our new out height
209
210         inBlockHeights[block] = newInHeight;
211         outBlockHeights[block] = newInHeight + blockHeightDeltas[block];
212
213         inBlockPresences[block] = newInPresence;
214         // If there was no change in the block then use the in presence; otherwise
215         // use the change in the block. Effectively a 2-part meet.
216         outBlockPresences[block] = (blockPresenceDeltas[block].isTop()) ? (newInPresence) : (blockPresenceDeltas[block]);
217
218         // Step 4: push all children on the worklist.
219
220         std::vector<Edge *> outEdges; block->getTargets(outEdges);
221
222         for (unsigned i = 0; i < outEdges.size(); i++) {
223             if (outEdges[i]->getType() == ET_CALL) continue;
224             worklist.push(outEdges[i]->getTarget());
225         }
226     }
227 }
228
229 void StackAnalysis::createIntervals() {
230     // Use the results summaries to calculate the 
231     // stack heights. We expect that heights will
232     // change infrequently and so summarize them at 
233     // the function level. 
234
235     heightIntervals_ = new HeightTree();
236     presenceIntervals_ = new PresenceTree();
237
238     StackHeight curHeight;
239     Offset curLB = 0;
240     Offset curUB = 0;
241
242     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
243         Block *block = *iter;
244
245         stanalysis_printf("\t Interval creation: visiting block at 0x%lx\n", block->firstInsnOffset());
246         
247         curLB = block->firstInsnOffset();
248         curUB = 0;
249         curHeight = inBlockHeights[block];
250         
251         // Now create extents for instructions within this block.
252         
253         for (InsnDeltas::iterator iter = blockToInsnDeltas[block].begin();
254              iter != blockToInsnDeltas[block].end(); 
255              iter++) {
256             // Now create extents for instructions within this block.
257             if ((*iter).second == StackHeight(0)) {
258                 continue;
259             }
260             
261             // We've changed the height of the stack. End this interval
262             // and start a new one. 
263             //
264             // We need to determine UB. It's defined as the end of the 
265             // current instruction. Therefore there are two cases:
266             // if we're the last insn (take the block end) or not
267             // the last insn (take the start of the next insn)
268             InsnDeltas::iterator iter2 = iter;
269             iter2++;
270             if (iter2 == blockToInsnDeltas[block].end()) {
271                 curUB = block->endOffset();
272             }
273             else {
274                 curUB = (*iter2).first;
275             }
276             heightIntervals_->insert(curLB, curUB, curHeight);
277             
278             // Start a new one
279             curLB = curUB;
280             curUB = 0;
281             curHeight += (*iter).second;
282
283         }
284         
285         if (curLB != block->endOffset()) {
286             // Cap off the extent for the current block
287             curUB = block->endOffset();
288             if (curHeight != outBlockHeights[block]) {
289                 fprintf(stderr, "ERROR: inconsistency in stack analysis, %s != %s\n",
290                         curHeight.getString().c_str(), outBlockHeights[block].getString().c_str());
291             }
292             assert(curHeight == outBlockHeights[block]);
293             heightIntervals_->insert(curLB, curUB, curHeight);
294         }
295     }
296
297     StackPresence curPres;
298     curUB = 0;
299     curLB = 0;
300     
301     for (Block::blockSet::iterator iter = blocks.begin(); iter != blocks.end(); iter++) {
302         Block *block = *iter;
303         
304         curLB = block->firstInsnOffset();
305         curUB = 0;
306         curPres = inBlockPresences[block];
307         
308         for (InsnPresence::iterator iter = blockToInsnPresence[block].begin();
309              iter != blockToInsnPresence[block].end(); 
310              iter++) {
311             
312             if ((*iter).second.isTop())
313                 continue;
314             
315             // We've changed the state of the stack pointer. End this interval
316             // and start a new one. 
317             //
318             // We need to determine UB. It's defined as the end of the 
319             // current instruction. Therefore there are two cases:
320             // if we're the last insn (take the block end) or not
321             // the last insn (take the start of the next insn)
322             InsnPresence::iterator iter2 = iter;
323             iter2++;
324             if (iter2 == blockToInsnPresence[block].end()) {
325                 curUB = block->endOffset();
326             }
327             else {
328                 curUB = (*iter2).first;
329             }
330             presenceIntervals_->insert(curLB, curUB, curPres);
331             
332             // Start a new one
333             curLB = curUB;
334             curUB = 0;
335             curPres = (*iter).second;
336         }            
337
338         if (curLB != block->endOffset()) {
339             // Cap off the extent for the current block
340             curUB = block->endOffset();
341             assert(curPres == outBlockPresences[block]);
342             presenceIntervals_->insert(curLB, curUB, curPres);
343         }
344     }
345 }
346
347
348 void StackAnalysis::computeInsnEffects(const Block *block,
349                                        const Instruction &insn,
350                                        Offset off,
351                                        StackHeight &height,
352                                        StackPresence &pres) 
353 {
354     stanalysis_printf("\t\tInsn at 0x%lx\n", off); 
355     Expression::Ptr theStackPtr(new RegisterAST(r_eSP));
356     Expression::Ptr stackPtr32(new RegisterAST(r_ESP));
357     Expression::Ptr stackPtr64(new RegisterAST(r_RSP));
358     
359     Expression::Ptr theFramePtr(new RegisterAST(r_eBP));
360     Expression::Ptr framePtr32(new RegisterAST(r_EBP));
361     Expression::Ptr framePtr64(new RegisterAST(r_RBP));
362     
363     //TODO: Integrate entire test into analysis lattice
364     entryID what = insn.getOperation().getID();
365
366     if (insn.isWritten(theFramePtr) || insn.isWritten(framePtr32) || insn.isWritten(framePtr64)) {
367         stanalysis_printf("\t\t\t FP written\n");
368         if (what == e_mov &&
369             (insn.isRead(theStackPtr) || insn.isRead(stackPtr32) || insn.isRead(stackPtr64))) {
370             pres = StackPresence::frame;
371             stanalysis_printf("\t\t\t Frame created\n");
372         }
373         else {
374             pres = StackPresence::noFrame;
375             stanalysis_printf("\t\t\t Frame destroyed\n");
376         }
377     }
378     
379
380    if (what == e_call)
381    {
382       pdvector<image_edge *> outs;
383       block->getTargets(outs);
384       for (unsigned i=0; i<outs.size(); i++) {
385          image_edge *cur_edge = outs[i];
386          if (cur_edge->getType() != ET_CALL) 
387              continue;
388          
389          image_basicBlock *target_bbl = cur_edge->getTarget();
390          image_func *target_func = target_bbl->getEntryFunc();
391          if (!target_func)
392              continue;
393          height = getStackCleanAmount(target_func);
394          stanalysis_printf("\t\t\t Stack height changed by self-cleaning function: %s\n", height.getString().c_str());
395          return;
396       }
397       height = StackHeight(0);
398       stanalysis_printf("\t\t\t Stack height assumed unchanged by call\n");
399       return;
400    }
401
402    int word_size = func->img()->getAddressWidth();
403    
404    if(!insn.isWritten(theStackPtr) && !insn.isWritten(stackPtr32)) {
405        height = StackHeight(0);
406        return;
407    }
408    int sign = 1;
409    switch(what)
410    {
411    case e_push:
412        sign = -1;
413    case e_pop: {
414        Operand arg = insn.getOperand(0);
415        if (arg.getValue()->eval().defined) {
416            height = StackHeight(sign * word_size); 
417            stanalysis_printf("\t\t\t Stack height changed by evaluated push/pop: %s\n", height.getString().c_str());
418            return;
419        }
420        height = StackHeight(sign * arg.getValue()->size());
421        stanalysis_printf("\t\t\t Stack height changed by unevalled push/pop: %s\n", height.getString().c_str());
422        return;
423    }
424    case e_sub:
425        sign = -1;
426    case e_add: {
427        // Add/subtract are op0 += (or -=) op1
428        Operand arg = insn.getOperand(1);
429        Result delta = arg.getValue()->eval();
430        if(delta.defined) {
431            switch(delta.type) {
432            case u8:
433                height = StackHeight(sign * delta.val.u8val);
434                break;
435            case u16:
436                height = StackHeight(sign * delta.val.u16val);
437                break;
438            case u32:
439                height = StackHeight(sign * delta.val.u32val);
440                break;
441            case u64:
442                height = StackHeight(sign * delta.val.u64val);
443                break;
444            case s8:
445                height = StackHeight(sign * delta.val.s8val);
446                break;
447            case s16:
448                height = StackHeight(sign * delta.val.s16val);
449                break;
450            case s32:
451                height = StackHeight(sign * delta.val.s32val);
452                break;
453            case s64:
454                height = StackHeight(sign * delta.val.s64val);
455                break;
456            default:
457                // Add of anything that's not a "normal" integral type
458                // means we don't know what happened
459                height = StackHeight(StackHeight::bottom);
460                break;
461            }
462            stanalysis_printf("\t\t\t Stack height changed by evalled add/sub: %s\n", height.getString().c_str());
463            return;
464        }
465    }
466        height = StackHeight(StackHeight::bottom);
467        stanalysis_printf("\t\t\t Stack height changed by unevalled add/sub: %s\n", height.getString().c_str());
468        return;
469        // We treat return as zero-modification right now
470    case e_ret_near:
471    case e_ret_far:
472        height = StackHeight(0);
473        stanalysis_printf("\t\t\t Stack height changed by ret_near/ret_far %s\n", height.getString().c_str());
474        return;
475    default:
476        stanalysis_printf("\t\t\t Stack height changed by unhandled insn %s: %s\n", 
477                          insn.format().c_str(), height.getString().c_str());
478        height = StackHeight(StackHeight::bottom);
479        return;
480    }
481    assert(0);
482    return;
483 }
484
485
486 StackAnalysis::StackHeight StackAnalysis::getStackCleanAmount(image_func *func) {
487     // Cache previous work...
488     if (funcCleanAmounts.find(func) != funcCleanAmounts.end()) {
489         return funcCleanAmounts[func];
490     }
491
492     if (!func->cleansOwnStack()) {
493         funcCleanAmounts[func] = StackHeight(0);
494         return StackHeight(0);
495     }
496
497     InstructionDecoder decoder;   
498     unsigned char *cur;
499
500     std::set<StackHeight> returnCleanVals;
501     
502     for (unsigned i=0; i < func->funcExits().size(); i++) {
503         cur = (unsigned char *) func->getPtrToInstruction(func->funcExits()[i]->offset());
504         size_t size = 0;
505         Instruction insn = decoder.decode(cur, size);
506         
507         entryID what = insn.getOperation().getID();
508         if (what != e_ret_near)
509             continue;
510         
511         int val;
512         std::vector<Operand> ops;
513         insn.getOperands(ops);
514         if (ops.size() == 0) {
515             val = 0;
516         }
517         else {      
518             Result imm = ops[0].getValue()->eval();
519             assert(imm.defined);
520             val = (int) imm.val.s16val;
521         }
522         returnCleanVals.insert(StackHeight(val));
523     }
524
525     funcCleanAmounts[func] = StackHeight::meet(returnCleanVals);
526     return funcCleanAmounts[func];
527 }
528
529 StackAnalysis::StackAnalysis(Function *f) : func(f) {
530     blocks = func->blocks();
531     heightIntervals_ = NULL;
532     presenceIntervals_ = NULL;
533 }
534
535 const StackAnalysis::HeightTree *StackAnalysis::heightIntervals() {
536     if (func == NULL) return NULL;
537
538     // Check the annotation
539     HeightTree *ret;
540     func->getAnnotation(ret, StackHeightAnno);
541     if (ret) return ret;
542     if (heightIntervals_ == NULL) {
543         if (!analyze()) return NULL;
544         ret = heightIntervals_;
545     }
546
547     return ret;
548 }
549
550
551 const StackAnalysis::PresenceTree *StackAnalysis::presenceIntervals() {
552     if (func == NULL) return NULL;
553
554     // Check the annotation
555     PresenceTree *ret;
556     func->getAnnotation(ret, StackPresenceAnno);
557     if (ret) return ret;
558
559     if (presenceIntervals_ == NULL) {
560         if (!analyze()) return NULL;
561         ret = presenceIntervals_;
562     }
563
564     return ret;
565 }
566
567 void StackAnalysis::debugStackHeights() {
568     if (!heightIntervals_) return;
569     std::vector<std::pair<std::pair<Offset, Offset>, StackHeight> > elements;
570     heightIntervals_->elements(elements);
571
572     for (unsigned i = 0; i < elements.size(); i++) {
573         fprintf(stderr, "0x%lx - 0x%lx: %s\n",
574                 elements[i].first.first,
575                 elements[i].first.second,
576                 elements[i].second.getString().c_str());
577     }
578 }
579
580 void StackAnalysis::debugStackPresences() {
581     if (!presenceIntervals_) return;
582
583     std::vector<std::pair<std::pair<Offset, Offset>, StackPresence> > elements;
584     presenceIntervals_->elements(elements);
585
586     for (unsigned i = 0; i < elements.size(); i++) {
587         fprintf(stderr, "0x%lx - 0x%lx: %s\n",
588                 elements[i].first.first,
589                 elements[i].first.second,
590                 elements[i].second.getString().c_str());
591     }
592 }
593