Improve handling of XOR.
[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 <list>
39 #include <map>
40 #include <set>
41 #include <string>
42
43 // To define StackAST
44 #include "DynAST.h"
45
46 #include "Absloc.h"
47 #include "dyntypes.h"
48 #include "dyn_regs.h"
49 #include "util.h"
50
51 // FreeBSD is missing a MINLONG and MAXLONG
52 #if defined(os_freebsd) 
53 #if defined(arch_64bit)
54 #define MINLONG INT64_MIN
55 #define MAXLONG INT64_MAX
56 #else
57 #define MINLONG INT32_MIN
58 #define MAXLONG INT32_MAX
59 #endif
60 #endif
61
62 // These are _NOT_ in the Dyninst namespace...
63 namespace Dyninst {
64   namespace ParseAPI {
65     class Function;
66     class Block;
67         class Edge;
68   };
69   namespace InstructionAPI {
70     class Instruction;
71     class Expression;
72   };
73
74  
75 class StackAnalysis {
76 public:
77    typedef boost::shared_ptr<InstructionAPI::Instruction> InstructionPtr;
78    typedef boost::shared_ptr<InstructionAPI::Expression> ExpressionPtr;
79
80    class DATAFLOW_EXPORT Height {
81    public:
82       typedef signed long Height_t;
83       typedef enum {TOP, BOTTOM, HEIGHT} Type;
84
85       static const Height_t uninitialized = MAXLONG;
86       static const Height_t notUnique = MINLONG;
87       static const Height bottom;
88       static const Height top;
89
90       Height(const Height_t h, const Type t = HEIGHT) : height_(h), type_(t) {}
91       Height() : height_(uninitialized), type_(TOP) {}
92         
93       Height_t height() const { return height_; }
94         
95       // FIXME if we stop using TOP == MAXINT and BOT == MININT...
96       bool operator<(const Height &rhs) const {
97          return (height_ < rhs.height_);
98       }
99
100       bool operator>(const Height &rhs) const {
101          return (height_ > rhs.height_);
102       }
103
104       bool operator<=(const Height &rhs) const {
105          return (height_ <= rhs.height_);
106       }
107
108       bool operator>=(const Height &rhs) const {
109          return (height_ >= rhs.height_);
110       }
111
112       Height &operator+= (const Height &other);
113       Height &operator+=(const signed long &rhs);
114       const Height operator+(const Height &rhs) const;
115       const Height operator+(const signed long &rhs) const;
116       const Height operator-(const Height &rhs) const;
117
118       bool operator==(const Height &rhs) const {
119          return type_ == rhs.type_ && height_ == rhs.height_;
120       }
121
122       bool operator!=(const Height &rhs) const {
123          return !(*this == rhs);
124       }
125         
126       std::string format() const {
127          if (isTop()) return "TOP";
128          if (isBottom()) return "BOTTOM";
129
130          std::stringstream retVal;
131          retVal << height_;
132          return retVal.str();
133       }
134
135       bool isBottom() const {
136          return type_ == BOTTOM && height_ == notUnique;
137       }
138
139       bool isTop() const {
140          return type_ == TOP && height_ == uninitialized;
141       }
142
143       static Height meet(const Height &lhs, const Height &rhs) {
144          if (rhs == lhs) return rhs;
145          if (rhs == top) return lhs;
146          if (lhs == top) return rhs;
147          return bottom;
148       }
149
150       static Height meet(std::set<Height> &ins) {
151          if (ins.empty()) {
152             return top;
153          }
154
155          // If there is a single element in the set return it.
156          if (ins.size() == 1) {
157             return *(ins.begin());
158          }
159
160          // MEET (bottom, ...) == bottom
161          // Since ins is sorted, if bottom is in the set it must
162          // be the start element...
163          if (*ins.begin() == bottom) return bottom;
164
165          // MEET (N, top) == N
166          if (ins.size() == 2 && *ins.rbegin() == top) {
167             return *(ins.begin());
168          }
169
170          // There are 2 or more elements; the last one is not top; therefore
171          // there is a conflict, and we return bottom.
172          return bottom;
173       }
174
175    private:
176       Height_t height_;
177       Type type_;
178    };
179
180
181    // We need to represent the effects of instructions. We do this in terms of
182    // transfer functions. We recognize the following effects on the stack.
183    //   * Offset by known amount: push/pop/etc.
184    //   * Set to known value: leave
185    //   * Copy the stack pointer to/from some Absloc.
186    //
187    // There are also:
188    //   * Offset by unknown amount expressible in a range [l, h]
189    //   * Set to unknown value expressible in a range [l, h]
190    // which we don't handle yet.
191    //
192    // This gives us the following transfer functions.
193    //   * Delta(RV, f, t, v) -> RV[f] += v;
194    //   * Abs(RV, f, t, v) -> RV[f] = v;
195    //   * Copy(RV, f, t, v) -> RV[t] = RV[f];
196    //
197    // In the implementations below, we provide f, t, v at construction time (as
198    // they are fixed) and RV as a parameter. Note that a transfer function is a
199    // function T : (RegisterVector, RegisterID, RegisterID, value) ->
200    // (RegisterVector).
201    typedef std::map<Absloc, Height> AbslocState;
202    class TransferFunc {
203    public:
204       typedef enum {TOP, BOTTOM, OTHER} Type;
205
206       static const long uninitialized = MAXLONG;
207       static const long notUnique = MINLONG;
208       static const TransferFunc top;
209       static const TransferFunc bottom;
210
211       TransferFunc() :
212          from(Absloc()), target(Absloc()), delta(0), abs(uninitialized),
213          retop(false), topBottom(false), type_(TOP) {}
214       TransferFunc(long a, long d, Absloc f, Absloc t, bool i = false,
215          bool rt = false, Type type = OTHER) : from(f), target(t), delta(d),
216          abs(a), retop(rt), topBottom(i), type_(type) {}
217       TransferFunc(std::map<Absloc,std::pair<long,bool> > f, long d, Absloc t) :
218          from(Absloc()), target(t), delta(d), abs(uninitialized), retop(false),
219          topBottom(false), fromRegs(f), type_(OTHER) {}
220
221       static TransferFunc identityFunc(Absloc r);
222       static TransferFunc deltaFunc(Absloc r, long d);
223       static TransferFunc absFunc(Absloc r, long a, bool i = false);
224       static TransferFunc copyFunc(Absloc f, Absloc t, bool i = false);
225       static TransferFunc bottomFunc(Absloc r);
226       static TransferFunc retopFunc(Absloc r);
227       static TransferFunc sibFunc(std::map<Absloc, std::pair<long,bool> > f,
228          long d, Absloc t);
229
230       static TransferFunc meet(const TransferFunc &lhs,
231          const TransferFunc &rhs);
232
233       bool isIdentity() const;
234       bool isBottom() const;
235       bool isTop() const;
236       bool isRetop() const;
237       bool isAbs() const;
238       bool isCopy() const;
239       bool isDelta() const;
240       bool isSIB() const;
241       bool isTopBottom() const {
242          return topBottom;
243       }
244
245       bool operator==(const TransferFunc &rhs) const {
246          return from == rhs.from && target == rhs.target &&
247             delta == rhs.delta && abs == rhs.abs && retop == rhs.retop &&
248             topBottom == rhs.topBottom && fromRegs == rhs.fromRegs;
249       }
250
251       bool operator!=(const TransferFunc &rhs) const {
252          return !(*this == rhs);
253       }
254
255       Height apply(const AbslocState &inputs) const;
256       void accumulate(std::map<Absloc, TransferFunc> &inputs);
257       TransferFunc summaryAccumulate(
258          const std::map<Absloc, TransferFunc> &inputs) const;
259
260       std::string format() const;
261       Type type() const;
262
263       Absloc from;
264       Absloc target;
265       long delta;
266       long abs;
267
268       // Distinguish between default-constructed transfer functions and
269       // explicitly-retopped transfer functions.
270       bool retop;
271
272       // Annotate transfer functions that have the following characteristic:
273       // if target is TOP, keep as TOP
274       // else, target must be set to BOTTOM
275       // E.g., sign-extending a register:
276       //   if the register had an uninitialized stack height (TOP),
277       //       the sign-extension has no effect
278       //   if the register had a valid or notunique (BOTTOM) stack height,
279       //       the sign-extension must result in a BOTTOM stack height
280       bool topBottom;
281
282       // Handle complex math from SIB functions
283       std::map<Absloc, std::pair<long, bool> > fromRegs;
284
285    private:
286       Type type_;
287    };
288
289    typedef std::list<TransferFunc> TransferFuncs;
290    typedef std::map<Absloc, TransferFunc> TransferSet;
291
292    // Summarize the effects of a series (list!) of transfer functions.
293    // Intended to summarize a block. We may want to do a better job of
294    // summarizing, but this works...
295    class SummaryFunc {
296    public:
297       static const long uninitialized = MAXLONG;
298       static const long notUnique = MINLONG;
299
300       SummaryFunc() {};
301
302       void apply(const AbslocState &in, AbslocState &out) const;
303       void accumulate(const TransferSet &in, TransferSet &out) const;
304
305       std::string format() const;
306       void validate() const;
307
308       void add(TransferFuncs &f);
309
310       TransferSet accumFuncs;
311    };
312
313    // The results of the stack analysis is a series of intervals. For each
314    // interval we have the following information:
315    //   a) Whether the function has a well-defined
316    //      stack frame. This is defined as follows:
317    //        * x86/AMD-64: a frame pointer
318    //        * POWER: an allocated frame pointed to by GPR1
319    //   b) The "depth" of the stack; the distance between
320    //      the stack pointer and the caller's stack pointer.
321    //   c) The "depth" of any copies of the stack pointer.
322
323    typedef std::map<Offset, AbslocState> StateIntervals;
324    typedef std::map<ParseAPI::Block *, StateIntervals> Intervals;
325
326    typedef std::map<ParseAPI::Function *, Height> FuncCleanAmounts;
327
328    typedef std::map<ParseAPI::Block *, SummaryFunc> BlockEffects;
329    typedef std::map<ParseAPI::Block *, AbslocState> BlockState;
330    typedef std::map<ParseAPI::Block *, TransferSet> BlockSummaryState;
331
332    // To build intervals, we must replay the effect of each instruction.
333    // To avoid sucking enormous time, we keep those transfer functions around...
334    typedef std::map<ParseAPI::Block *, std::map<Offset, TransferFuncs>>
335       InstructionEffects;
336
337    DATAFLOW_EXPORT StackAnalysis();
338    DATAFLOW_EXPORT StackAnalysis(ParseAPI::Function *f);
339
340    DATAFLOW_EXPORT Height find(ParseAPI::Block *, Address addr, Absloc loc);
341    DATAFLOW_EXPORT Height findSP(ParseAPI::Block *, Address addr);
342    DATAFLOW_EXPORT Height findFP(ParseAPI::Block *, Address addr);
343    DATAFLOW_EXPORT void findDefinedHeights(ParseAPI::Block* b, Address addr,
344       std::vector<std::pair<Absloc, Height> >& heights);
345
346    // TODO: Update DataflowAPI manual
347    DATAFLOW_EXPORT bool getFunctionSummary(TransferSet &summary);
348
349    DATAFLOW_EXPORT void debug();
350
351 private:
352    std::string format(const AbslocState &input) const;
353    std::string format(const TransferSet &input) const;
354
355    MachRegister sp();
356    MachRegister fp();
357
358    bool analyze();
359    bool genInsnEffects();
360    void summarizeBlocks();
361    void summarize();
362
363    void fixpoint();
364    void summaryFixpoint();
365
366    void createIntervals();
367
368    void createEntryInput(AbslocState &input);
369    void createSummaryEntryInput(TransferSet &input);
370    void meetInputs(ParseAPI::Block *b, AbslocState& blockInput,
371       AbslocState &input);
372    void meetSummaryInputs(ParseAPI::Block *b, TransferSet &blockInput,
373       TransferSet &input);
374    void meet(const AbslocState &source, AbslocState &accum);
375    void meetSummary(const TransferSet &source, TransferSet &accum);
376    AbslocState getSrcOutputLocs(ParseAPI::Edge* e);
377    TransferSet getSummarySrcOutputLocs(ParseAPI::Edge *e);
378    void computeInsnEffects(ParseAPI::Block *block, InstructionPtr insn,
379       const Offset off, TransferFuncs &xferFunc);
380
381    bool isCall(InstructionPtr insn);
382    bool handleNormalCall(InstructionPtr insn, ParseAPI::Block *block,
383       Offset off, TransferFuncs &xferFuncs);
384    bool handleThunkCall(InstructionPtr insn, TransferFuncs &xferFuncs);
385    void handlePushPop(InstructionPtr insn, ParseAPI::Block *block,
386       const Offset off, int sign, TransferFuncs &xferFuncs);
387    void handleReturn(InstructionPtr insn, TransferFuncs &xferFuncs);
388    void handleAddSub(InstructionPtr insn, ParseAPI::Block *block,
389       const Offset off, int sign, TransferFuncs &xferFuncs);
390    void handleLEA(InstructionPtr insn, TransferFuncs &xferFuncs);
391    void handleLeave(ParseAPI::Block *block, const Offset off,
392       TransferFuncs &xferFuncs);
393    void handlePushPopFlags(int sign, TransferFuncs &xferFuncs);
394    void handlePushPopRegs(int sign, TransferFuncs &xferFuncs);
395    void handlePowerAddSub(InstructionPtr insn, int sign,
396       TransferFuncs &xferFuncs);
397    void handlePowerStoreUpdate(InstructionPtr insn, TransferFuncs &xferFuncs);
398    void handleMov(InstructionPtr insn, ParseAPI::Block *block,
399       const Offset off, TransferFuncs &xferFuncs);
400    void handleZeroExtend(InstructionPtr insn, ParseAPI::Block *block,
401       const Offset off, TransferFuncs &xferFuncs);
402    void handleSignExtend(InstructionPtr insn, ParseAPI::Block *block,
403       const Offset off, TransferFuncs &xferFuncs);
404    void handleSpecialSignExtend(InstructionPtr insn, TransferFuncs &xferFuncs);
405    void handleXor(InstructionPtr insn, ParseAPI::Block *block, const Offset off,
406       TransferFuncs &xferFuncs);
407    void handleDiv(InstructionPtr insn, TransferFuncs &xferFuncs);
408    void handleMul(InstructionPtr insn, TransferFuncs &xferFuncs);
409    void handleDefault(InstructionPtr insn, TransferFuncs &xferFuncs);
410
411    long extractDelta(InstructionAPI::Result deltaRes);
412
413    Height getStackCleanAmount(ParseAPI::Function *func);
414
415
416    ParseAPI::Function *func;
417
418    // SP effect tracking
419    BlockEffects *blockEffects;  // Pointer so we can make it an annotation
420    InstructionEffects *insnEffects;  // Pointer so we can make it an annotation
421
422    BlockState blockInputs;
423    BlockState blockOutputs;
424
425    // Like blockInputs and blockOutputs, but used for function summaries.
426    // Instead of tracking Heights, we track transfer functions.
427    BlockSummaryState blockSummaryInputs;
428    BlockSummaryState blockSummaryOutputs;
429
430    Intervals *intervals_; // Pointer so we can make it an annotation
431
432    FuncCleanAmounts funcCleanAmounts;
433    int word_size;
434    ExpressionPtr theStackPtr;
435    ExpressionPtr thePC;
436 };
437
438 } // namespace Dyninst
439
440 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os,
441    const Dyninst::StackAnalysis::Height &h);
442
443 namespace Dyninst {
444    DEF_AST_LEAF_TYPE(StackAST, Dyninst::StackAnalysis::Height);
445 }
446 #endif