Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / stackanalysis.h
1 /*
2  * Copyright (c) 1996-2009 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  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #if !defined(STACK_ANALYSIS_H)
33 #define STACK_ANALYSIS_H
34
35 #include <values.h>
36 #include "dyntypes.h"
37 #include <set>
38 #include <string>
39
40 #include "common/h/IntervalTree.h"
41
42 // for blockSet...
43 #include "dyninstAPI/src/image-func.h"
44
45 #include "dyn_detail/boost/shared_ptr.hpp"
46
47 // These are _NOT_ in the Dyninst namespace...
48 class image_func;
49 class image_basicBlock;
50 class image_edge;
51
52 namespace Dyninst {
53 class InstructionAPI::Instruction; 
54
55  
56 class StackAnalysis {
57  public:
58     
59     // The height of a stack is actually a value from a lattice:
60     // 
61     // <int>: height of the stack at this point
62     // BOT/uninitialized: the height of the stack at this point is unknown (uninitialized)
63     // TOP/notUnique: the height of the stack at this point is unknown (non-unique)
64     
65     template <class T> 
66         T join(std::set<T> &ins) {
67         if (ins.empty()) 
68             return T::bottom;
69         
70         // If there is a single element in the set return it.
71         if (ins.size() == 1) 
72             return *(ins.begin());
73         
74         // JOIN (..., top) == top
75         // Since ins is sorted, if top is in the set it must
76         // be the end element...
77         const T &last = *(ins.rbegin());
78         if (last == T::top) return T::top;
79         
80         // U (bot, N) == N
81         const T &first = *(ins.begin());
82         if ((ins.size() == 2) &&
83             (first == T::bottom))
84             return *(ins.rbegin());
85         
86         // There are 2 or more elements; the first one is not
87         // bottom; therefore there is a conflict, and we return
88         // top.
89         return T::top;
90     }
91     
92     
93     template <class T> 
94         T meet (std::set<T> &ins) {
95         // Another useful default.
96         if (ins.empty()) {
97             return T::top;
98         }
99         
100         // If there is a single element in the set return it.
101         if (ins.size() == 1) {
102             return *(ins.begin());
103         }
104         
105         // MEET (bottom, ...) == bottom
106         // Since ins is sorted, if bottom is in the set it must
107         // be the start element...
108         
109         if ((*(ins.begin())) == T::bottom)  {
110             return T::bottom;
111         }
112         
113         // MEET (N, top) == N
114         if ((ins.size() == 2) &&
115             ((*(ins.rbegin())) == T::top)) {
116             return *(ins.begin());
117         }
118         
119         // There are 2 or more elements; the last one is not
120         // top; therefore there is a conflict, and we return
121         // bottom.
122         return T::bottom;
123     }
124
125     // A Range represents a single unknown
126     // operation on the stack pointer. It
127     // consists of an <int, int> pair that
128     // represents the upper and lower bounds of
129     // the operation on the stack pointer and 
130     // an Offset that represents the instruction
131     // performing the operation.
132
133     class Range {
134     public:
135         typedef std::pair<long, long> range_t;
136         
137         static const range_t infinite;
138
139         Range(range_t range,
140               long delta,
141               Offset off) : 
142             range_(range), delta_(delta), off_(off) {};
143
144         Range(const Range &r, 
145               long delta) :
146             range_(r.range_),
147             delta_(delta),
148             off_(r.off_) {};
149
150         Range() : 
151             delta_(0), off_(0) {
152             
153             range_.first = 0;
154             range_.second = 0;
155         }
156
157         range_t &range() { return range_; }
158         Offset &off() { return off_; }
159
160         bool operator== (const Range &rhs) const {
161             return ((range_ == rhs.range_) &&
162                     (off_ == rhs.off_));
163         }
164
165         bool operator< (const Range &rhs) const {
166             return (off_ < rhs.off_);
167         }
168
169         bool operator> (const Range &rhs) const {
170             return (off_ > rhs.off_);
171         }
172
173         bool operator!= (const Range &rhs) const { 
174             return !((*this) == rhs);
175         }
176         
177         std::string format() const;
178     private:
179         range_t range_;
180         long delta_;
181         Offset off_;
182         // Value of the stack when the range was applied
183     };
184
185     typedef std::vector<Range> Ranges;
186     static const Range defaultRange;
187
188     class Region {
189     public:
190         typedef dyn_detail::boost::shared_ptr<Region> Ptr;
191
192         Region(int n, 
193                Range &r,
194                Region::Ptr p) : 
195             name_(n),
196             range_(r),
197             prev_(p)
198             {};
199
200         Region(int n) : name_(n) {};
201         Region() : name_(0) {};
202        
203         int &name() { return name_; };
204         Range &range() { return range_; };
205         Ptr prev() { return prev_; };
206
207         std::string format() const;
208
209         bool operator< (const Region &rhs) const {
210             return name_ < rhs.name_; 
211         }
212
213         bool operator==(const Region &rhs) const {
214             return name_ == rhs.name_;
215         }
216         
217         bool operator!= (const Region &rhs) const {
218             return !(*this == rhs);
219         }
220
221     private:
222         int name_;
223         Range range_;
224         Ptr prev_;
225     };
226
227     class Height {
228     public:
229         typedef signed long Height_t;
230         
231         static const Height_t uninitialized = MAXLONG;           
232         static const Height_t notUnique = MINLONG;           
233         
234         static const Height bottom;
235         static const Height top;
236         
237         Height(const Height_t h, Region::Ptr r) :
238             height_(h), region_(r) {};
239         Height(const Height_t h) : height_(h) {};
240         Height() : height_(uninitialized) {};
241
242         Height_t height() const { return height_; }
243         Region::Ptr region() const { return region_; }
244         
245         
246         // FIX THIS!!! if we stop using TOP == MAXINT and
247         // BOT == MININT...
248         bool operator<(const Height &rhs) const {
249             if (height_ == rhs.height_) 
250                 return region_ < rhs.region_;
251             return (height_ < rhs.height_);
252         }
253         
254         Height &operator+= (const Height &other) {
255             if (isBottom()) return *this;
256             if (other.isBottom()) {
257                 *this = bottom;
258                 return *this;
259             }
260             if (other.isTop()) {
261                 return *this;
262             }
263
264             if (region_ != other.region_) {
265                 *this = bottom;
266                 return *this;
267             }
268
269             height_ += other.height_;
270             return *this;
271         }
272
273         const Height operator+(const Height &rhs) const {
274             if (isBottom()) return bottom;
275             if (rhs.isBottom()) return rhs;
276             if (isTop()) return rhs;
277             if (rhs.isTop()) return *this;
278             if (region_ != rhs.region_) return bottom;
279
280             return Height(height_ + rhs.height_, region_);
281         }
282
283         bool operator==(const Height &rhs) const {
284             return ((height_ == rhs.height_) &&
285                     (region_ == rhs.region_));
286         }
287         bool operator!=(const Height &rhs) const {
288             return !(*this == rhs);
289         }
290         
291         std::string format() const {
292             if (isTop()) return "TOP";
293             if (isBottom()) return "BOTTOM";
294             
295             std::stringstream retVal;
296             retVal << height_ << region_->format();
297             return retVal.str();
298         }                                        
299         
300         bool isBottom() const {
301             return height_ == notUnique;
302         }
303         
304         bool isTop() const {
305             return height_ == uninitialized; 
306         }
307         
308     private:
309         Height_t height_;
310         
311         Region::Ptr region_;
312     };
313     
314     class Presence {
315     public:
316         typedef enum {
317             bottom_t,
318             noFrame_t,
319             frame_t,
320             top_t} Presence_t;
321
322         static const Presence bottom;
323         static const Presence top;
324         
325         Presence() : presence_(top_t) {};
326         Presence(Presence_t d) : presence_(d) {};
327         Presence presence() const { return presence_; };
328         
329         // This is arbitrary and strictly for ordering
330         // in set insertion. The only requirement is that 
331         // bottom < (ANY) and (ANY) < top
332         bool operator<(const Presence &rhs) const {
333             return (presence_ < rhs.presence_); 
334         }
335         bool operator==(const Presence &other) const {
336             return presence_ == other.presence_;
337         }
338         bool operator!=(const Presence &rhs) const {
339             return presence_ != rhs.presence_;
340         }
341         
342         std::string format() const {
343             switch(presence_) {
344             case bottom_t:
345                 return "BOTTOM";
346             case noFrame_t:
347                 return "NOFRAME";
348             case frame_t:
349                 return "FRAME";
350             case top_t:
351                 return "TOP";
352             default:
353                 assert(0);
354                 return "UNKNOWN";
355             }
356         }
357
358         void apply(const Presence &in,
359                    Presence &out) const;
360         void apply(Presence &out) const;
361
362         bool isBottom() const {
363             return presence_ == bottom_t;
364         }
365         
366         bool isTop() const {
367             return presence_ == top_t;
368         }
369         
370     private:
371         Presence_t presence_;
372     };    
373
374     // We need to represent the effects of instructions. We do this
375     // in terms of transfer functions. We recognize the following 
376     // effects on the stack.
377     //
378     // Offset by known amount: push/pop/etc. 
379     // Set to known value: leave
380     // Offset by unknown amount expressible in a range [l, h]
381     // Set to unknown value expressible in a range [l, h]
382     //
383     // These map as follows:
384     // Offset by known amount: delta transfer function
385     // Set to known value: set transfer function
386     // Offset by unknown amount: new_region transfer function
387     // Set to unknown value: new_region transfer function
388
389     // This gives us three transfer functions. A transfer
390     // function is a function T : (height, region, value) -> (height, region)
391     // described as follows:
392     // Delta (h, r, v) : (h+v, r)
393     // Set (h, r, v) : (v, r)
394     // New (h, r, vl, vh) : (0, new region(vl, vh))
395     // 
396     // where 'new region' represents a previously unallocated region, 
397     // and (vl,vh) represent the range [l, h]
398
399     typedef std::pair<Ranges, Height> Status;
400
401     class InsnTransferFunc;
402     class BlockTransferFunc;
403
404     class InsnTransferFunc {
405     public:
406         static const InsnTransferFunc top;
407         static const InsnTransferFunc bottom;
408
409         static const long uninitialized = MAXLONG;
410         static const long notUnique = MINLONG;
411
412         InsnTransferFunc() : delta_(uninitialized), abs_(false), range_(defaultRange) {};
413         InsnTransferFunc(long delta, bool reset) :
414             delta_(delta), abs_(reset), range_(defaultRange) {};
415         InsnTransferFunc(Range &r) :
416             delta_(0), abs_(false), range_(r) {};
417
418         void apply(const BlockTransferFunc &in,
419                    BlockTransferFunc &out) const;
420
421         void apply(BlockTransferFunc &update) const;
422
423         std::string format() const;
424
425         bool operator==(const InsnTransferFunc &rhs) const {
426             return ((delta_ == rhs.delta_) &&
427                     (abs_ == rhs.abs_) &&
428                     (range_ == rhs.range_));
429         }
430         
431         bool operator!=(const InsnTransferFunc &rhs) const {
432             return !(*this == rhs);
433         }
434
435         long &delta() { return delta_; }
436         bool &abs() { return abs_; }
437         Range &range() { return range_; }
438
439     private:
440         long delta_;
441         bool abs_;
442         Range range_;
443     };
444
445     // This is a bit of an odd beast. It's a block-level
446     // summary of what we've done to the stack, either
447     // from the beginning of the block or the beginning
448     // of the function. As such, it's a transfer function. 
449     // It also needs to satisfy the join/meet requirements 
450     // of operator <, operator ==, top, bottom. 
451
452     class BlockTransferFunc {
453     public:
454         static const BlockTransferFunc bottom;
455         static const BlockTransferFunc top;
456         static const BlockTransferFunc initial;
457
458         static const long uninitialized = MAXLONG;
459         static const long notUnique = MINLONG;
460
461         // From meet/join requirements: default constructor
462         // is TOP. Represented by uninitialized delta.
463
464         // Members:
465         // delta (int) : the height difference from the start
466         //               to the finish
467         // reset (int) : if true, the stack is reset to 0 and
468         //               delta measures from there. 
469         // ranges (int, int) : represent unknown modifications
470         //                     of the stack (e.g., rounding, adding
471         //                     a variable, etc.)
472
473         BlockTransferFunc() : 
474             delta_(uninitialized), 
475             reset_(false),
476             abs_(false)
477             {};
478         BlockTransferFunc(long d, 
479                           bool r,
480                           bool a) : 
481             delta_(d), 
482             reset_(r),
483             abs_(a) 
484             {};
485         
486         bool operator <(const BlockTransferFunc &rhs) const {
487             if ((*this) == rhs) return false;
488
489             if (rhs == top) return true;
490             else if (*this == bottom) return true;
491             // Arbitrary unique ordering
492             else if (delta_ < rhs.delta_) return true;
493             else if (delta_ > rhs.delta_) return false;
494             else if (reset_ < rhs.reset_) return true;
495             else if (reset_ > rhs.reset_) return false;
496             else if (abs_ < rhs.abs_) return true;
497             else if (abs_ > rhs.abs_) return false;
498             else if (ranges_.size() < rhs.ranges_.size()) return true;
499             else if (ranges_.size() > rhs.ranges_.size()) return false;
500             // Errr...
501             for (unsigned i = 0; i < ranges_.size(); i++) {
502                 if (ranges_[i] < rhs.ranges_[i]) return true;
503                 else if (ranges_[i] > rhs.ranges_[i]) return false;
504             }
505             return false;
506         }
507         bool operator==(const BlockTransferFunc &rhs) const {
508             if ((delta_ == uninitialized) && 
509                 (rhs.delta_ == uninitialized)) return true;
510             if ((delta_ == notUnique) && 
511                 (rhs.delta_ == notUnique)) return true;
512
513             if (delta_ != rhs.delta_) return false;
514             if (reset_ != rhs.reset_) return false;
515             if (abs_ != rhs.abs_) return false;
516             if (ranges_.size() != rhs.ranges_.size()) return false;
517             for (unsigned i = 0; i < ranges_.size(); i++) {
518                 if (ranges_[i] != rhs.ranges_[i]) return false;
519             }
520             return true;
521         }
522         bool operator!=(const BlockTransferFunc &rhs) const {
523             return !(*this == rhs);
524         }        
525
526
527         void apply(const BlockTransferFunc &in, BlockTransferFunc &out) const;
528         void apply(BlockTransferFunc &out) const;
529
530         std::string format() const;
531
532         long &delta() { return delta_; }
533         bool &reset() { return reset_; }
534         bool &abs() { return abs_; }
535         Ranges &ranges() { return ranges_; }
536
537     private:
538         long delta_;
539         bool reset_;
540         bool abs_;
541         Ranges ranges_;
542     };
543
544     // We map sets of Ranges to Regions using a prefix tree.
545     // Each node in the tree represents a particular Range.
546     
547     class RangeTree {
548     public:
549         struct Node {
550             Node() {};
551             Node(Region::Ptr re) :
552                 region(re) {};
553             ~Node() {
554                 for (std::map<Range, Node *>::iterator i = children.begin(); 
555                      i != children.end(); i++) {
556                     if (i->second)
557                         delete i->second;
558                 }
559             }
560
561             std::map<Range, Node *> children;
562             Region::Ptr region;
563         };
564
565         // May expand the tree
566         Region::Ptr find(Ranges &str);
567
568         RangeTree(Region::Ptr initial) : curRegion(0) {
569             root = new Node(initial);
570         };
571         ~RangeTree() { 
572             delete root; 
573         }
574         
575         int getNewRegionID() { return ++curRegion; }
576
577     private:
578         int curRegion;
579         Node *root;
580     };
581         
582     // The results of the stack analysis is a series of 
583     // intervals. For each interval we have the following
584     // information: 
585     //   a) Whether the function has a well-defined
586     //      stack frame. This is defined as follows:
587     //        x86/AMD-64: a frame pointer
588     //        POWER: an allocated frame pointed to by GPR1
589     //   b) The "depth" of the stack; the distance between
590     //      the stack pointer and the caller's stack pointer.
591     
592     typedef class IntervalTree<Offset, Height> HeightTree;
593     
594     typedef class IntervalTree<Offset, Presence> PresenceTree;
595     
596     typedef image_basicBlock Block;
597     typedef image_edge Edge;
598     typedef image_func Function;
599     
600     typedef std::map<Offset, InsnTransferFunc> InsnFuncs;
601     typedef std::map<Block *, InsnFuncs> BlockToInsnFuncs;
602
603     typedef std::map<Function *, Height> FuncCleanAmounts;
604     
605     typedef std::map<Block *, Presence> BlockPresence;
606     typedef std::map<Offset, Presence> InsnPresence;
607     typedef std::map<Block *, InsnPresence> BlockToInsnPresence;
608     
609     typedef std::map<Block *, BlockTransferFunc> BlockEffects;
610
611     StackAnalysis();
612     StackAnalysis(Function *f);
613     
614     const HeightTree *heightIntervals();
615     const PresenceTree *presenceIntervals();
616     
617     void debugHeights();
618     void debugPresences();
619     
620  private:
621     
622     bool analyze();
623     void summarizeBlocks();
624     void fixpoint();
625
626     void createPresenceIntervals();
627     void createHeightIntervals();
628
629     void computeInsnEffects(const Block *block,
630                             const InstructionAPI::Instruction::Ptr &insn,
631                             const Offset off,
632                             InsnTransferFunc &iFunc,
633                             Presence &pres);
634
635     Height getStackCleanAmount(Function *func);
636
637     Region::Ptr getRegion(Ranges &ranges);
638     
639     Block::blockSet blocks;
640     Function *func;
641     
642     BlockToInsnFuncs blockToInsnFuncs;
643     BlockEffects blockEffects;
644     BlockEffects inBlockEffects;
645     BlockEffects outBlockEffects;
646         
647     BlockToInsnPresence blockToInsnPresences;
648     BlockPresence blockPresences;
649     BlockPresence inBlockPresences;
650     BlockPresence outBlockPresences;
651     
652     HeightTree *heightIntervals_; // Pointer so we can make it an annotation
653     PresenceTree *presenceIntervals_;
654     
655     FuncCleanAmounts funcCleanAmounts;
656     
657     RangeTree rt;
658 };
659 };
660
661 #endif
662