Improved LEA handling and added mul/div handling.
[dyninst.git] / dataflowAPI / h / stackanalysis.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #if !defined(STACK_ANALYSIS_H)
32 #define STACK_ANALYSIS_H
33
34 #if !defined(_MSC_VER) && !defined(os_freebsd)
35 #include <values.h>
36 #endif
37
38 #include "dyntypes.h"
39 #include <set>
40 #include <map>
41 #include <string>
42 #include <list>
43 #include "util.h"
44 #include "dyn_regs.h"
45 #include "Absloc.h"
46
47 // To define StackAST
48 #include "DynAST.h"
49
50 // FreeBSD is missing a MINLONG and MAXLONG
51 #if defined(os_freebsd) 
52 #if defined(arch_64bit)
53 #define MINLONG INT64_MIN
54 #define MAXLONG INT64_MAX
55 #else
56 #define MINLONG INT32_MIN
57 #define MAXLONG INT32_MAX
58 #endif
59 #endif
60
61 // These are _NOT_ in the Dyninst namespace...
62 namespace Dyninst {
63
64   namespace ParseAPI {
65     class Function;
66     class Block;
67         class Edge;
68   };
69
70   namespace InstructionAPI {
71     class Instruction;
72     class Expression;
73   };
74
75  
76 class StackAnalysis {
77   typedef boost::shared_ptr<InstructionAPI::Instruction> InstructionPtr;
78   typedef boost::shared_ptr<InstructionAPI::Expression> ExpressionPtr;
79
80  public:
81
82     class DATAFLOW_EXPORT Height {
83     public:
84         typedef signed long Height_t;
85         
86         static const Height_t uninitialized = MAXLONG;
87         static const Height_t notUnique = MINLONG;
88         
89         static const Height bottom;
90         static const Height top;
91         
92       Height(const Height_t h) : height_(h) {};
93       Height() : height_(uninitialized) {};
94         
95         Height_t height() const { return height_; }
96         
97         // FIX THIS!!! if we stop using TOP == MAXINT and
98         // BOT == MININT...
99         bool operator<(const Height &rhs) const {
100             return (height_ < rhs.height_);
101         }
102
103         bool operator>(const Height &rhs) const {
104             return (height_ > rhs.height_);
105         }
106
107         bool operator<=(const Height &rhs) const {
108             return (height_ <= rhs.height_);
109         }
110
111         bool operator>=(const Height &rhs) const {
112             return (height_ >= rhs.height_);
113         }
114         
115         Height &operator+= (const Height &other) {
116             if (isBottom()) return *this;
117             if (other.isBottom()) {
118                 *this = bottom;
119                 return *this;
120             }
121             if (isTop() && other.isTop()) {
122                 // TOP + TOP = TOP
123                 *this = top;
124                 return *this;
125             }
126             if (isTop() || other.isTop()) {
127                 // TOP + height = BOTTOM
128                 *this = bottom;
129                 return *this;
130             }
131             
132             height_ += other.height_;
133             return *this;
134         }
135
136         const Height operator+(const Height &rhs) const {
137             if (isBottom()) return bottom;
138             if (rhs.isBottom()) return rhs;
139             if (isTop() && rhs.isTop()) return top;
140             if (isTop() || rhs.isTop()) return bottom;
141
142             return Height(height_ + rhs.height_);
143         }
144
145         const Height operator-(const Height &rhs) const {
146             if (isBottom()) return bottom;
147             if (rhs.isBottom()) return rhs;
148             if (isTop() && rhs.isTop()) return top;
149             if (isTop() || rhs.isTop()) return bottom;
150
151             return Height(height_ - rhs.height_);
152         }
153
154         Height &operator+=(const signed long &rhs) {
155             if (isBottom()) return *this;
156             if (isTop()) return *this;
157
158             height_ += rhs;
159             return *this;
160         }
161
162         const Height operator+(const signed long &rhs) const {
163           if (isBottom()) return bottom;
164       if (isTop()) return top;
165
166           return Height(height_ + rhs);
167         }
168
169         bool operator==(const Height &rhs) const {
170            return height_ == rhs.height_;
171         }
172         bool operator!=(const Height &rhs) const {
173             return !(*this == rhs);
174         }
175         
176         std::string format() const {
177             if (isTop()) return "TOP";
178             if (isBottom()) return "BOTTOM";
179             
180             std::stringstream retVal;
181             retVal << height_;
182             return retVal.str();
183         }                                        
184         
185         bool isBottom() const {
186             return height_ == notUnique;
187         }
188         
189         bool isTop() const {
190             return height_ == uninitialized; 
191         }
192
193         static Height meet(const Height &lhs, const Height &rhs) {
194            if (rhs == lhs) return rhs;
195            if (rhs == top) return lhs;
196            if (lhs == top) return rhs;
197            return bottom;
198         }
199
200         static Height meet (std::set<Height> &ins) {
201            if (ins.empty()) {
202               return top;
203            }
204            
205            // If there is a single element in the set return it.
206            if (ins.size() == 1) {
207               return *(ins.begin());
208            }
209            
210            // MEET (bottom, ...) == bottom
211            // Since ins is sorted, if bottom is in the set it must
212            // be the start element...
213            
214            if ((*(ins.begin())) == bottom)  {
215               return bottom;
216            }
217            
218            // MEET (N, top) == N
219            if ((ins.size() == 2) &&
220                ((*(ins.rbegin())) == top)) {
221               return *(ins.begin());
222            }
223            
224            // There are 2 or more elements; the last one is not
225            // top; therefore there is a conflict, and we return
226            // bottom.
227            return bottom;
228         }
229         
230     private:
231         Height_t height_;
232     };
233
234
235     // We need to represent the effects of instructions. We do this
236     // in terms of transfer functions. We recognize the following 
237     // effects on the stack.
238     //
239     // Offset by known amount: push/pop/etc. 
240     // Set to known value: leave
241     // Assign the stack pointer to/from an alias
242     //
243     // There are also: 
244     // Offset by unknown amount expressible in a range [l, h]
245     // Set to unknown value expressible in a range [l, h]
246     // which we don't handle yet. 
247     //
248     // This gives us the following transfer functions. A transfer function
249     // is a function T : (RegisterVector, RegisterID, RegisterID, value) -> (RegisterVector)
250     //
251     // Delta(RV, f, t, v) -> RV[f] += v;
252     // Abs(RV, f, t, v) -> RV[f] = v;
253     // Alias(RV, f, t, v) -> RV[t] = RV[f];
254     // In the implementations below, we provide f, t, v at construction time (as they are
255     // fixed) and RV as a parameter.
256
257     
258     typedef std::map<Absloc, Height> AbslocState;
259
260     struct TransferFunc {
261        static const long uninitialized = MAXLONG;
262        static const long notUnique = MINLONG;
263
264        static const TransferFunc top;
265        static const TransferFunc bottom;
266
267        typedef enum {
268           Bottom,
269           Delta,
270           Abs,
271           Alias } Type;
272        
273        static TransferFunc deltaFunc(Absloc r, long d);
274        static TransferFunc absFunc(Absloc r, long a, bool i = false);
275        static TransferFunc aliasFunc(Absloc f, Absloc t, bool i = false);
276        static TransferFunc bottomFunc(Absloc r);
277        static TransferFunc retopFunc(Absloc r);
278        static TransferFunc sibFunc(std::map<Absloc, std::pair<long,bool> > f,
279           long d, Absloc t);
280
281        bool isBottom() const;
282        bool isTop() const;
283        bool isRetop() const;
284        bool isAbs() const;
285        bool isAlias() const;
286        bool isDelta() const;
287        bool isSIB() const;
288
289        bool isTopBottom() const {
290            return topBottom;
291        }
292
293     TransferFunc() :
294        from(Absloc()), target(Absloc()), delta(0), abs(uninitialized),
295        retop(false), topBottom(false) {};
296     TransferFunc(long a, long d, Absloc f, Absloc t, bool i = false,
297        bool rt = false) :
298        from(f), target(t), delta(d), abs(a), retop(rt), topBottom(i) {};
299     TransferFunc(std::map<Absloc,std::pair<long,bool> > f, long d, Absloc t) :
300        from(Absloc()), target(t),
301        delta(d), abs(uninitialized),
302        retop(false),
303        topBottom(false),
304        fromRegs(f) {}
305
306        Height apply(const AbslocState &inputs) const;
307        void accumulate(std::map<Absloc, TransferFunc> &inputs);
308
309        std::string format() const;
310        Type type() const;
311
312        Absloc from;
313        Absloc target;
314        long delta;
315        long abs;
316
317        // Distinguish between default-constructed transfer functions and
318        // explicitly-retopped transfer functions.
319        bool retop;
320
321        // Annotate transfer functions that have the following characteristic:
322        // if target is TOP, keep as TOP
323        // else, target must be set to BOTTOM
324        // E.g., sign-extending a register:
325        //   if the register had an uninitialized stack height (TOP),
326        //       the sign-extension has no effect
327        //   if the register had a valid or notunique (BOTTOM) stack height,
328        //       the sign-extension must result in a BOTTOM stack height
329        bool topBottom;
330
331        // Handle complex math from SIB functions
332        std::map<Absloc, std::pair<long, bool> > fromRegs;
333     };
334
335     typedef std::list<TransferFunc> TransferFuncs;
336     typedef std::map<Absloc, TransferFunc> TransferSet;
337
338     // Summarize the effects of a series (list!) of transfer functions.
339     // Intended to summarize a block. We may want to do a better job of
340     // summarizing, but this works...
341     struct SummaryFunc {
342        static const long uninitialized = MAXLONG;
343        static const long notUnique = MINLONG;
344
345        SummaryFunc() {};
346
347        void apply(const AbslocState &in, AbslocState &out) const;
348        std::string format() const;
349            void validate() const;
350
351        void add(TransferFuncs &f);
352
353        TransferSet accumFuncs;
354     };
355
356     // The results of the stack analysis is a series of 
357     // intervals. For each interval we have the following
358     // information: 
359     //   a) Whether the function has a well-defined
360     //      stack frame. This is defined as follows:
361     //        x86/AMD-64: a frame pointer
362     //        POWER: an allocated frame pointed to by GPR1
363     //   b) The "depth" of the stack; the distance between
364     //      the stack pointer and the caller's stack pointer.
365     //   c) The "depth" of any aliases of the stack pointer. 
366     
367     typedef std::map<Offset, AbslocState> StateIntervals;
368     typedef std::map<ParseAPI::Block *, StateIntervals> Intervals;
369     
370     typedef std::map<ParseAPI::Function *, Height> FuncCleanAmounts;
371     
372     typedef std::map<ParseAPI::Block *, SummaryFunc> BlockEffects;
373     typedef std::map<ParseAPI::Block *, AbslocState> BlockState;
374
375     // To build intervals, we must replay the effect of each instruction.
376     // To avoid sucking enormous time, we keep those transfer functions around...
377     typedef std::map<ParseAPI::Block *, std::map<Offset, TransferFuncs> > InstructionEffects;
378
379     DATAFLOW_EXPORT StackAnalysis();
380     DATAFLOW_EXPORT StackAnalysis(ParseAPI::Function *f);
381     
382     DATAFLOW_EXPORT Height find(ParseAPI::Block *, Address addr, Absloc loc);
383     // And a commonly used shortcut
384     DATAFLOW_EXPORT Height findSP(ParseAPI::Block *, Address addr);
385     DATAFLOW_EXPORT Height findFP(ParseAPI::Block *, Address addr);
386     DATAFLOW_EXPORT void findDefinedHeights(ParseAPI::Block* b, Address addr, std::vector<std::pair<Absloc, Height> >& heights);
387     
388     
389     DATAFLOW_EXPORT void debug();
390     
391  private:
392     
393     std::string format(const AbslocState &input) const;
394
395     MachRegister sp();
396     MachRegister fp();
397
398     bool analyze();
399     void summarizeBlocks();
400     void summarize();
401
402     void fixpoint();
403     
404     void createIntervals();
405
406     void createEntryInput(AbslocState &input);
407     void meetInputs(ParseAPI::Block *b, AbslocState& blockInput, AbslocState &input);
408     void meet(const AbslocState &source, AbslocState &accum);
409     AbslocState getSrcOutputLocs(ParseAPI::Edge* e);
410     void computeInsnEffects(ParseAPI::Block *block,
411                             InstructionPtr insn,
412                             const Offset off,
413                             TransferFuncs &xferFunc);
414
415     bool isCall(InstructionPtr insn);
416     bool handleNormalCall(InstructionPtr insn, ParseAPI::Block *block, Offset off, TransferFuncs &xferFuncs);
417     bool handleThunkCall(InstructionPtr insn, TransferFuncs &xferFuncs);
418     void handlePushPop(InstructionPtr insn, int sign, TransferFuncs &xferFuncs);
419     void handleReturn(InstructionPtr insn, TransferFuncs &xferFuncs);
420     void handleAddSub(InstructionPtr insn, int sign, TransferFuncs &xferFuncs);
421     void handleLEA(InstructionPtr insn, TransferFuncs &xferFuncs);
422     void handleLeave(TransferFuncs &xferFuncs);
423     void handlePushPopFlags(int sign, TransferFuncs &xferFuncs);
424     void handlePushPopRegs(int sign, TransferFuncs &xferFuncs);
425     void handlePowerAddSub(InstructionPtr insn, int sign, TransferFuncs &xferFuncs);
426     void handlePowerStoreUpdate(InstructionPtr insn, TransferFuncs &xferFuncs);
427     void handleMov(InstructionPtr insn, const Offset off, TransferFuncs &xferFuncs);
428     void handleZeroExtend(InstructionPtr insn, TransferFuncs &xferFuncs);
429     void handleSignExtend(InstructionPtr insn, TransferFuncs &xferFuncs);
430     void handleXor(InstructionPtr insn, TransferFuncs &xferFuncs);
431     void handleDiv(InstructionPtr insn, TransferFuncs &xferFuncs);
432     void handleMul(InstructionPtr insn, TransferFuncs &xferFuncs);
433     void handleDefault(InstructionPtr insn, TransferFuncs &xferFuncs);
434
435     long extractDelta(InstructionAPI::Result deltaRes);
436
437     Height getStackCleanAmount(ParseAPI::Function *func);
438
439     ParseAPI::Function *func;
440
441     
442
443     // SP effect tracking
444     BlockEffects blockEffects;
445     InstructionEffects insnEffects;
446
447     BlockState blockInputs;
448     BlockState blockOutputs;
449
450
451
452     Intervals *intervals_; // Pointer so we can make it an annotation
453     
454     FuncCleanAmounts funcCleanAmounts;
455     int word_size;
456     ExpressionPtr theStackPtr;
457     ExpressionPtr thePC;
458
459 };
460
461 };
462
463 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os, const Dyninst::StackAnalysis::Height &h);
464
465 namespace Dyninst {
466   DEF_AST_LEAF_TYPE(StackAST, Dyninst::StackAnalysis::Height);
467
468 };
469
470
471 #endif
472