Merge branch 'master' into devel
[dyninst.git] / symEval / src / Absloc.C
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 #include "Absloc.h"
33 #include <assert.h>
34
35 #include "instructionAPI/h/Register.h"
36 #include "instructionAPI/h/InstructionAST.h"
37 #include "instructionAPI/h/Instruction.h"
38 #include "instructionAPI/h/Expression.h"
39
40 #include "symEval/h/stackanalysis.h"
41
42 #include <sstream>
43
44 using namespace Dyninst;
45 // using namespace Dyninst::DepGraphAPI;
46 using namespace Dyninst::InstructionAPI;
47 using namespace dyn_detail::boost;
48 using namespace std;
49 //////////////// Replace with generic version ////////////
50
51 ////////////////
52 // FIXME architecture...
53 ///////////////
54 bool Absloc::isPC() const { 
55   if (type_ != Register) return false;
56   return (reg_ == MachRegister::getPC(reg_.getArchitecture()));
57 }
58
59 bool Absloc::isSP() const {
60   if (type_ != Register) return false;
61   return (reg_ == MachRegister::getStackPointer(reg_.getArchitecture()));
62 }
63
64 bool Absloc::isFP() const {
65   if (type_ != Register) return false;
66   return (reg_ == MachRegister::getFramePointer(reg_.getArchitecture()));
67 }
68
69 Absloc Absloc::makePC(Architecture arch) {
70   return Absloc(MachRegister::getPC(arch));
71 }
72
73 Absloc Absloc::makeSP(Architecture arch) {
74   return Absloc(MachRegister::getStackPointer(arch));
75 }
76
77 Absloc Absloc::makeFP(Architecture arch) {
78   return Absloc(MachRegister::getFramePointer(arch));
79 }
80
81 std::string Absloc::format() const {
82   std::stringstream ret;
83   
84   switch(type_) {
85   case Register:
86     // TODO: I'd like a "current architecture" global
87     // and a int->register converter...
88     ret << reg_.name();
89     break;
90   case Stack: {
91     ret << "S[" << func_ << "," << off_ << "," << region_ << "]";
92     break;
93   }
94   case Heap:
95     ret << "_" << std::hex << addr_ << std::dec;
96     break;
97   default:
98     ret << "(UNKNOWN)";
99     break;
100   }
101
102   return ret.str();
103 }
104
105 bool AbsRegion::contains(const Absloc::Type t) const {
106   // Abslocs, if they exist, must be specific.
107   // So just check our type
108   return (type_ == t);
109 }
110
111 bool AbsRegion::contains(const Absloc &loc) const {
112   if (type_ != Absloc::Unknown) {
113     // If we're a typed region we contain any absloc
114     // with our type
115     return (type_ == loc.type());
116   }
117   //if (loc.type() != Absloc::Unknown) {
118   //return (type() == loc.type());
119   //}
120
121   // See if any of our abslocs matches
122   if (absloc_ == loc) return true;
123
124   if (loc.type() == Absloc::Unknown) {
125     cerr << "Weird case: comp " << format() << " /w/ " << loc.format() << endl;
126   }
127
128   return false;
129 }  
130
131
132 bool AbsRegion::contains(const AbsRegion &rhs) const {
133   if (type_ != Absloc::Unknown) {
134     // We're a typed region, so we contain rhs
135     // if either it has the same type as us or if all
136     // of its abslocs are the same type
137     if (rhs.type_ == type_) return true;
138     if (rhs.absloc_.type() == type_) return true;
139     return false;
140   }
141
142   if (rhs.type() != Absloc::Unknown) {
143     if (absloc_.type() == rhs.type()) return true;
144   }
145
146   // Stack slots operate kinda... odd...
147   if ((absloc_.type() == Absloc::Stack) &&
148       (rhs.absloc_.type() == Absloc::Stack)) {
149     // Return true if we're in the same function but different
150     // regions
151     if ((absloc_.func() == rhs.absloc_.func()) &&
152         (absloc_.region() != rhs.absloc_.region())) return true;
153   }
154
155   if (absloc_ == rhs.absloc_) return true;
156   return false;
157 }
158 /*
159 bool AbsRegion::overlaps(const AbsRegion &rhs) const {
160   if (type_ != Absloc::Unknown) {
161     // We're a typed region, so we contain rhs
162     // if either it has the same type as us or if all
163     // of its abslocs are the same type
164     if (rhs.type_ == type_) return true;
165     for (std::set<Absloc>::const_iterator iter = rhs.abslocs_.begin();
166          iter != rhs.abslocs_.end(); ++iter) {
167       if ((*iter).type() == type_) return true;
168     }
169     return false;
170   }
171
172   // We don't have a type, therefore we are a set. 
173   // If they are a type...
174   if (rhs.type_ != Absloc::Unknown) {
175     return containsOfType(rhs.type_);
176   }
177
178   // Neither a type, so see if there is any overlap in our sets.
179
180   for (std::set<Absloc>::const_iterator iter = rhs.abslocs_.begin();
181        iter != rhs.abslocs_.end(); ++iter) {
182     if (abslocs_.find(*iter) != abslocs_.end()) {
183       return true;
184     }
185   }
186   return false;
187 }
188 */
189
190 bool AbsRegion::containsOfType(Absloc::Type t) const {
191   if (type_ == t) return true;
192
193   if (absloc_.type() == t) return true;
194   return false;
195 }
196
197 bool AbsRegion::operator==(const AbsRegion &rhs) const {
198   // return contains(rhs) && rhs.contains(*this));
199   return ((type_ == rhs.type_) &&
200           (absloc_ == rhs.absloc_));
201 }
202
203 bool AbsRegion::operator!=(const AbsRegion &rhs) const { 
204   return ((type_ != rhs.type_) ||
205           (absloc_ != rhs.absloc_));
206 }
207
208
209 bool AbsRegion::operator<(const AbsRegion &rhs) const {
210   if (absloc_ < rhs.absloc_) return true;
211   if (rhs.absloc_ < absloc_) return false;
212
213   return type() < rhs.type();
214 }
215
216 /*
217 void AbsRegion::insert(const Absloc &abs) {
218   assert(a
219   if (type_ != Absloc::Unknown) 
220     assert(0 && "Unimplemented");
221   abslocs_.insert(abs);
222 }
223
224 void AbsRegion::insert(const AbsRegion &rhs) {
225   if (type_ != Absloc::Unknown)
226     assert(0 && "Unimplemented");
227   if (rhs.type_ != Absloc::Unknown)
228     assert(0 && "Unimplemented");
229
230   abslocs_.insert(rhs.abslocs_.begin(),
231                   rhs.abslocs_.end());
232 }
233
234 void AbsRegion::erase(const Absloc &rhs) {
235   if (type_ != Absloc::Unknown)
236     assert(0 && "Unimplemented");
237   abslocs_.erase(rhs);
238 }
239
240 void AbsRegion::erase(const AbsRegion &rhs) {
241   if (type_ != Absloc::Unknown)
242     assert(0 && "Unimplemented");
243   if (rhs.type_ != Absloc::Unknown)
244     assert(0 && "Unimplemented");
245
246   abslocs_.erase(rhs.abslocs_.begin(),
247                  rhs.abslocs_.end());
248 }
249 */
250
251 void Assignment::addInput(const AbsRegion &reg) {
252   inputs_.push_back(reg);
253 }
254
255 void Assignment::addInputs(const std::vector<AbsRegion> &region) {
256   for (unsigned i = 0; i < region.size(); ++i) {
257     inputs_.push_back(region[i]);
258   }
259 }
260
261 const std::string AbsRegion::format() const {
262   std::stringstream ret;
263
264   if (absloc_ != Absloc()) {
265     ret << "[" << absloc_.format();
266     if (size_) ret << ":" << size_;
267     ret << "]";
268   }
269   else {
270     switch(type_) {
271     case Absloc::Register:
272       ret << "R[]";
273       break;
274     case Absloc::Stack:
275       ret << "S[]";
276       break;
277     case Absloc::Heap:
278       ret << "H[]";
279       break;
280     default:
281       ret << "?[];";
282       break;
283     }
284   }
285   return ret.str();
286 }
287
288 const std::string Assignment::format() const {
289   // Err....
290   std::stringstream ret;
291   ret << "(@"<< std::hex << addr_ << std::dec
292       << "<" << out_.format();
293   for (unsigned i = 0; i < inputs_.size(); i++) {
294     ret << ">" << inputs_[i].format();
295   }
296   ret << ")";
297
298   return ret.str();
299 }
300
301 std::ostream &operator<<(std::ostream &os, const Absloc &a) {
302   os << a.format();
303   return os;
304 }
305
306 std::ostream &operator<<(std::ostream &os, const AbsRegion &a) {
307   os << a.format();
308   return os;
309 }
310
311 std::ostream &operator<<(std::ostream &os, const Assignment::Ptr &a) {
312   os << a->format();
313   return os;
314 }
315
316 #if 0
317 bool AbsRegion::equivalent(const AbsRegion &lhs,
318                            const AbsRegion &rhs,
319                            Address addr,
320                            ParseAPI::Function *caller,
321                            ParseAPI::Function *callee) {
322   // Check equivalence given a particular location (and thus
323   // possible stack overlap)
324   if (lhs == rhs) return true;
325   if (lhs.abslocs().empty() || rhs.abslocs().empty()) return false;
326
327   if (lhs.abslocs().size() > 1) return false;
328   if (rhs.abslocs().size() > 1) return false;
329
330   // Only stack slots can overlap (for now)
331   const Absloc &lLoc = *(lhs.abslocs().begin());
332   const Absloc &rLoc = *(rhs.abslocs().begin());
333   if (lLoc.type() != Absloc::Stack) return false;
334   if (rLoc.type() != Absloc::Stack) return false;
335
336   int caller_offset = -1;
337   int callee_offset = -1;
338
339   if (lLoc.func() == caller->name()) {
340     if (rLoc.func() != callee->name()) return false;
341     caller_offset = lLoc.off();
342     callee_offset = rLoc.off();
343   }
344   else if (rLoc.func() == caller->name()) {
345     if (lLoc.func() != callee->name()) return false;
346     caller_offset = rLoc.off();
347     callee_offset = lLoc.off();
348   }
349   else {
350     return false;
351   }
352
353   StackAnalysis sA(caller);
354
355   StackAnalysis::Height heightSA = sA.findSP(addr);
356
357   // Ensure that analysis has been performed.
358   assert(!heightSA.isTop());
359   
360   if (heightSA.isBottom()) {
361     return false;
362   }
363
364   if ((caller_offset - heightSA.height()) == callee_offset)
365     return true;
366   else
367     return false;
368 }
369 #endif