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