Merge branch 'master' of git.dyninst.org:/pub/dyninst
[dyninst.git] / symEval / h / Absloc.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 // Base representations for locations in program memory and registers
33 // We use a two-layered model consisting of AbsLocs (abstract locations)
34 // and AbsRegions (abstract regions). 
35 //
36 // An Absloc defines a unique location in memory or a register. We 
37 // consider the stack to be a separate, indexed-from-zero memory location.
38 //
39 // An AbsRegion is a set of Abslocs. In essence it is a set, though we
40 // may be able to use a more efficient internal representation than a
41 // set. As a TODO, we wish to provide shortcuts for comparing one type
42 // of AbsRegion to another type more efficiently than the fallback
43 // point-wise comparison.
44
45 #if !defined(ABSLOC_H)
46 #define ABSLOC_H
47
48 #include <values.h>
49
50 #include "Instruction.h"
51 #include "AST.h"
52
53 class image_func;
54
55 namespace Dyninst {
56
57 class Absloc {
58  public:
59   typedef enum {
60     Register,
61     Stack,
62     Heap,
63     Unknown } Type;
64
65   static Absloc makePC(Dyninst::Architecture arch);
66   static Absloc makeSP(Dyninst::Architecture arch);
67   static Absloc makeFP(Dyninst::Architecture arch);
68   
69   // Some static functions for "well-known" Abslocs
70   bool isPC() const;
71   bool isSPR() const;
72   
73   bool isSP() const;
74   bool isFP() const;
75
76  Absloc() :
77   type_(Unknown),
78     reg_(),
79     off_(-1),
80     region_(-1),
81     addr_(-1) {};
82  Absloc(MachRegister reg) :
83   type_(Register),
84     reg_(reg) {};
85     
86  Absloc(Address addr) :
87   type_(Heap),
88     addr_(addr) {};
89  Absloc(int o,
90         int r,
91         const std::string &f) :
92     type_(Stack),
93       off_(o),
94       region_(r),
95       func_(f) {};
96     
97   std::string format() const;
98
99   const Type &type() const { return type_; };
100
101   const MachRegister &reg() const { assert(type_ == Register); return reg_; };
102
103   int off() const { assert(type_ == Stack); return off_; };
104   int region() const { assert(type_ == Stack); return region_; };
105   const std::string &func() const { assert(type_ == Stack); return func_; };
106   
107   bool operator<(const Absloc &rhs) const {
108     if (type_ != rhs.type_) 
109       return type_ < rhs.type_;
110     switch(type_) {
111     case Register:
112       return reg_ < rhs.reg_;
113     case Stack:
114       if (off_ != rhs.off_)
115         return off_ < rhs.off_;
116       // Now we get arbitrary
117       if (region_ != rhs.region_)
118         return region_ < rhs.region_;
119       return func_ < rhs.func_;
120     case Heap:
121       return addr_ < rhs.addr_;
122     default:
123       return true;
124     }
125   }
126
127   bool operator==(const Absloc &rhs) const {
128     if (type_ != rhs.type_) return false;
129     switch(type_) {
130     case Register:
131       return reg_ == rhs.reg_;
132     case Stack:
133       return ((off_ == rhs.off_) &&
134               (region_ == rhs.region_) &&
135               (func_ == rhs.func_));
136     case Heap:
137       return addr_ == rhs.addr_;
138     default:
139       return true;
140     }
141   }
142
143   bool operator!=(const Absloc &rhs) const {
144     return !(*this == rhs);
145   }
146
147   static char typeToChar(const Type t) {
148     switch(t) {
149     case Register:
150       return 'r';
151     case Stack:
152       return 's';
153     case Heap:
154       return 'h';
155     default:
156       return 'u';
157     }
158   };
159
160  private:
161   Type type_;
162
163   MachRegister reg_;
164
165   int off_;
166   int region_;  
167   std::string func_;
168
169   Address addr_;
170 };
171
172 class AbsRegion {
173  public:
174   // Set operations get included here? Or third-party
175   // functions?
176   
177   bool contains(const Absloc::Type t) const;
178   bool contains(const Absloc &abs) const;
179   bool contains(const AbsRegion &rhs) const;
180   // Logically, "intersect(rhs) != 0"
181   //bool overlaps(const AbsRegion &rhs) const;
182
183   bool containsOfType(Absloc::Type t) const;
184
185   //iterator &begin();
186   //iterator &end();
187
188   bool operator==(const AbsRegion &rhs) const;
189   bool operator<(const AbsRegion &rhs) const;
190
191   const std::string format() const;
192
193   void insert(const Absloc &abs);
194   void insert(const AbsRegion &reg);
195
196   void erase(const Absloc &abs);
197   void erase(const AbsRegion &reg);
198
199   AbsRegion() :
200     type_(Absloc::Unknown) {};
201
202   AbsRegion(Absloc::Type t) :
203     type_(t) {};
204
205   AbsRegion(Absloc a) :
206     type_(Absloc::Unknown),
207       absloc_(a) {};
208
209
210   void setGenerator(AST::Ptr generator) {
211       generator_ = generator;
212   }
213
214   static bool equivalent(const AbsRegion &lhs,
215                          const AbsRegion &rhs,
216                          Address addr,
217                          image_func *caller,
218                          image_func *callee);
219
220   const Absloc absloc() const { return absloc_; }
221   const Absloc::Type type() const { return type_; }
222
223  private:
224   // Type is for "we're on the stack but we don't know where".
225   // Effectively, it's a wildcard.
226   Absloc::Type type_;
227
228   // For specific knowledge.
229   Absloc absloc_;
230
231   // And the AST that gave rise to this Absloc. We use this
232   // as a generating function (if present and not overridden)
233   AST::Ptr generator_;
234 };
235
236
237 class Assignment {
238  public:
239   typedef dyn_detail::boost::shared_ptr<Assignment> Ptr;
240   typedef std::set<AbsRegion> Aliases;
241
242   const std::vector<AbsRegion> &inputs() const { return inputs_; }
243   std::vector<AbsRegion> &inputs() { return inputs_; }
244
245   const InstructionAPI::Instruction::Ptr insn() const { return insn_; }
246   const Address addr() const { return addr_; }
247
248   const AbsRegion &out() const { return out_; }
249   AbsRegion &out() { return out_; }
250
251   const std::string format() const;
252
253   // FIXME
254   Aliases aliases;
255
256   // Factory functions. 
257   static std::set<Assignment::Ptr> create(InstructionAPI::Instruction::Ptr insn,
258                                           Address addr);
259
260   Assignment(const InstructionAPI::Instruction::Ptr i,
261              const Address a,
262              image_func *f,
263              const std::vector<AbsRegion> &ins,
264              const AbsRegion &o) : 
265     insn_(i),
266     addr_(a),
267       func_(f),
268     inputs_(ins),
269     out_(o) {};
270
271   Assignment(const InstructionAPI::Instruction::Ptr i,
272              const Address a,
273              image_func *f,
274              const AbsRegion &o) : 
275     insn_(i),
276     addr_(a),
277       func_(f),
278     out_(o) {};
279
280   // Internally used method; add a dependence on 
281   // a new abstract region. If this is a new region
282   // we'll add it to the dependence list. Otherwise 
283   // we'll join the provided input set to the known
284   // inputs.
285   void addInput(const AbsRegion &reg);
286   void addInputs(const std::vector<AbsRegion> &regions);
287
288   image_func *func() const { return func_; }
289
290  private:
291   InstructionAPI::Instruction::Ptr insn_;
292   Address addr_;
293
294   image_func *func_;
295
296   std::vector<AbsRegion> inputs_;
297   AbsRegion out_;
298 };
299
300 // Dyninst namespace
301 };
302
303
304 std::ostream &operator<<(std::ostream &os, const Dyninst::Absloc &a);
305 std::ostream &operator<<(std::ostream &os, const Dyninst::AbsRegion &a);
306 std::ostream &operator<<(std::ostream &os, const Dyninst::Assignment::Ptr &a);
307
308 #endif
309