Prototype of DataflowAPI liveness analysis
[dyninst.git] / patchAPI / src / PatchBlock.C
1 /* Public Interface */
2
3 #include "common.h"
4 #include "PatchCFG.h"
5 #include "AddrSpace.h"
6 #include "PatchObject.h"
7 #include "PatchMgr.h"
8 #include "PatchCallback.h"
9
10 using namespace Dyninst;
11 using namespace PatchAPI;
12 using namespace InstructionAPI;
13
14 PatchBlock*
15 PatchBlock::create(ParseAPI::Block *ib, PatchFunction *f) {
16   return f->object()->getBlock(ib);
17 }
18
19 PatchBlock::PatchBlock(ParseAPI::Block *blk, PatchObject *obj)
20   : block_(blk),   obj_(obj) {
21   ParseAPI::CodeObject::funclist& all = obj->co()->funcs();
22   for (ParseAPI::CodeObject::funclist::iterator fit = all.begin();
23        fit != all.end(); ++fit) {
24     if ((*fit)->contains(blk)) {
25       function_ = obj->getFunc(*fit);
26       break;
27     }
28   }
29 }
30
31 PatchBlock::PatchBlock(const PatchBlock *parent, PatchObject *child)
32   : block_(parent->block_), obj_(child) {
33   ParseAPI::CodeObject::funclist& all = child->co()->funcs();
34   for (ParseAPI::CodeObject::funclist::iterator fit = all.begin();
35        fit != all.end(); ++fit) {
36     if ((*fit)->contains(block_)) {
37       function_ = child->getFunc(*fit);
38       break;
39     }
40   }
41 }
42
43 void
44 PatchBlock::getInsns(Insns &insns) const {
45   // Pass through to ParseAPI. They don't have a native interface, so add one.
46   Offset off = block_->start();
47   const unsigned char *ptr =
48     (const unsigned char *)block_->region()->getPtrToInstruction(off);
49   if (ptr == NULL) return;
50   InstructionDecoder d(ptr, size(), block_->obj()->cs()->getArch());
51   while (off < block_->end()) {
52     Instruction::Ptr insn = d.decode();
53     insns[off + obj_->codeBase()] = insn;
54     off += insn->size();
55   }
56 }
57
58 const PatchBlock::edgelist&
59 PatchBlock::getSources() {
60   if (srclist_.empty()) {
61     for (ParseAPI::Block::edgelist::iterator iter = block_->sources().begin();
62          iter != block_->sources().end(); ++iter) {
63       PatchEdge *newEdge = obj_->getEdge(*iter, NULL, this);
64       srclist_.push_back(newEdge);
65     }
66   }
67   return srclist_;
68 }
69
70 const PatchBlock::edgelist&
71 PatchBlock::getTargets() {
72   if (trglist_.empty()) {
73     for (ParseAPI::Block::edgelist::iterator iter = block_->targets().begin();
74          iter != block_->targets().end(); ++iter) {
75       PatchEdge *newEdge = obj_->getEdge(*iter, this, NULL);
76       trglist_.push_back(newEdge);
77     }
78   }
79   return trglist_;
80 }
81
82 void PatchBlock::addSourceEdge(PatchEdge *e, bool addIfEmpty) {
83    if (!addIfEmpty && srclist_.empty()) return;
84
85    srclist_.push_back(e);
86
87   cb()->add_edge(this, e, PatchCallback::source);
88 }
89
90 void PatchBlock::addTargetEdge(PatchEdge *e, bool addIfEmpty) {
91    if (!addIfEmpty && trglist_.empty()) return;
92
93    trglist_.push_back(e);
94    
95    cb()->add_edge(this, e, PatchCallback::target);
96 }
97
98
99 void
100 PatchBlock::removeSourceEdge(PatchEdge *e) {
101    if (srclist_.empty()) return;
102
103   std::vector<PatchEdge *>::iterator iter;
104   if ((iter = std::find(srclist_.begin(), srclist_.end(), e)) != srclist_.end()) {
105     srclist_.erase(iter);
106   }
107
108   cb()->remove_edge(this, e, PatchCallback::source);
109 }
110
111 void
112 PatchBlock::removeTargetEdge(PatchEdge *e) {
113    if (trglist_.empty()) return;
114
115   std::vector<PatchEdge *>::iterator iter;
116   if ((iter = std::find(trglist_.begin(), trglist_.end(), e)) != trglist_.end()) {
117     trglist_.erase(iter);
118   }
119   cb()->remove_edge(this, e, PatchCallback::target);
120 }
121
122
123 bool
124 PatchBlock::isShared() {
125   return containingFuncs() > 1;
126 }
127
128 PatchBlock::~PatchBlock() {
129 #if 0
130    // Our predecessor may be deleted...
131   for (std::vector<PatchEdge *>::iterator iter = srclist_.begin();
132        iter != srclist_.end(); ++iter) {
133     PatchBlock* blk = (*iter)->source();
134     blk->removeTargetEdge(*iter);
135   }
136   for (std::vector<PatchEdge *>::iterator iter = trglist_.begin();
137        iter != trglist_.end(); ++iter) {
138     PatchBlock* blk = (*iter)->target();
139     blk->removeSourceEdge(*iter);
140   }
141 #endif
142 }
143
144 Address
145 PatchBlock::start() const {
146   return object()->codeBase() + block_->start();
147 }
148
149 Address
150 PatchBlock::end() const {
151   return object()->codeBase() + block_->end();
152 }
153
154 Address
155 PatchBlock::last() const {
156   return object()->codeBase() + block_->lastInsnAddr();
157 }
158
159 Address
160 PatchBlock::size() const {
161   return block_->size();
162 }
163
164 int
165 PatchBlock::containingFuncs() const {
166   return block_->containingFuncs();
167 }
168
169 bool
170 PatchBlock::containsCall() {
171   ParseAPI::Block::edgelist & out_edges = block_->targets();
172   ParseAPI::Block::edgelist::iterator eit = out_edges.begin();
173   for( ; eit != out_edges.end(); ++eit) {
174     if ( ParseAPI::CALL == (*eit)->type() ) {
175       return true;
176     }
177   }
178   return false;
179 }
180
181 bool
182 PatchBlock::containsDynamicCall() {
183   ParseAPI::Block::edgelist & out_edges = block_->targets();
184   ParseAPI::Block::edgelist::iterator eit = out_edges.begin();
185    for( ; eit != out_edges.end(); ++eit) {
186      if ( ParseAPI::CALL == (*eit)->type() && ((*eit)->sinkEdge())) {
187          return true;
188       }
189    }
190    return false;
191 }
192
193 std::string
194 PatchBlock::disassemble() const {
195   stringstream ret;
196   Insns instances;
197   getInsns(instances);
198   for (Insns::iterator iter = instances.begin();
199        iter != instances.end(); ++iter) {
200     ret << "\t" << hex << iter->first << ": " << iter->second->format() << dec << endl;
201   }
202   return ret.str();
203 }
204
205 InstructionAPI::Instruction::Ptr
206 PatchBlock::getInsn(Address a) const {
207    Insns insns;
208    getInsns(insns);
209    return insns[a];
210 }
211
212 std::string
213 PatchBlock::long_format() const {
214   stringstream ret;
215   ret << format() << endl;
216   
217   Insns insns;
218   getInsns(insns);
219   
220   for (Insns::iterator iter = insns.begin(); iter != insns.end(); ++iter) {
221      ret << "\t" << hex << iter->first << " : " << iter->second->format() << dec << endl;
222   }
223   return ret.str();
224 }
225
226 std::string
227 PatchBlock::format() const {
228   stringstream ret;
229   ret << "B[" << hex << start() << "," << end() << "]" << dec;
230
231   return ret.str();
232 }
233
234 PatchFunction*
235 PatchBlock::getFunction(ParseAPI::Function* f) {
236   return function()->object()->getFunc(f);
237 }
238
239 PatchFunction*
240 PatchBlock::function() const { return function_; }
241
242 ParseAPI::Block*
243 PatchBlock::block() const { return block_; }
244
245 PatchObject*
246 PatchBlock::object() const { return obj_; }
247
248 PatchFunction*
249 PatchBlock::getCallee() {
250    PatchBlock::edgelist::const_iterator it = getTargets().begin();
251    for (; it != getTargets().end(); ++it) {
252       if ((*it)->type() == ParseAPI::CALL) {
253          PatchBlock* trg = (*it)->target();
254          return trg->function();
255       }
256    }
257   return NULL;
258 }
259
260 Point *PatchBlock::findPoint(PatchLocation loc, Point::Type type, bool create) {
261    PointMakerPtr maker = obj_->addrSpace()->mgr()->pointMaker();
262    PatchMgrPtr mgr = obj_->addrSpace()->mgr();
263    Point *ret = NULL;
264
265    switch (type) {
266       case Point::BlockEntry:
267          if (!points_.entry && create) {
268             points_.entry = maker->createPoint(loc, type);
269          }
270          return points_.entry;
271          break;
272       case Point::BlockExit:
273          if (!points_.exit && create) {
274             points_.exit = maker->createPoint(loc, type);
275          }
276          return points_.exit;
277          break;
278       case Point::BlockDuring:
279          if (!points_.during && create) {
280             points_.during = maker->createPoint(loc, type);
281          }
282          return points_.during;
283          break;
284       case Point::PreInsn: {
285          if (!loc.addr || !loc.insn) return NULL;
286          InsnPoints::iterator iter2 = points_.preInsn.find(loc.addr);
287          if (iter2 == points_.preInsn.end()) {
288             if (!create) return NULL;
289             ret = maker->createPoint(loc, type);
290             points_.preInsn[loc.addr] = ret;
291             return ret;
292          }
293          else {
294             return iter2->second;
295          }
296          break;
297       }
298       case Point::PostInsn: {
299          if (!loc.addr || !loc.insn) return NULL;
300          InsnPoints::iterator iter2 = points_.postInsn.find(loc.addr);
301          if (iter2 == points_.postInsn.end()) {
302             if (!create) return NULL;
303             ret = maker->createPoint(loc, type);
304             points_.preInsn[loc.addr] = ret;
305             return ret;
306          }
307          else return iter2->second;
308          break;
309       }
310       default:
311          return NULL;
312    }
313 }
314
315
316 void PatchBlock::destroy(Point *p) {
317    assert(p->getBlock() == this);
318
319    switch(p->type()) {
320       case Point::PreInsn:
321          delete points_.preInsn[p->address()];
322          break;
323       case Point::PostInsn:
324          delete points_.postInsn[p->address()];
325          break;
326       case Point::BlockEntry:
327          delete points_.entry;
328          break;
329       case Point::BlockExit:
330          delete points_.exit;
331          break;
332       case Point::BlockDuring:
333          delete points_.during;
334          break;
335       default:
336          break;
337    }
338 }
339
340 PatchCallback *PatchBlock::cb() const {
341    return obj_->cb();
342 }
343
344 void PatchBlock::splitPoints(PatchBlock *succ) {
345    // Check our points. 
346    // Entry stays here
347    // During stays here
348    if (points_.exit) {
349       succ->points_.exit = points_.exit;
350       points_.exit = NULL;
351       succ->points_.exit->changeBlock(succ);
352    }
353
354    InsnPoints::iterator pre = points_.preInsn.lower_bound(succ->start());
355    for (InsnPoints::iterator tmp = pre; tmp != points_.preInsn.end(); ++tmp) {
356       tmp->second->changeBlock(succ);
357       succ->points_.preInsn[tmp->first] = tmp->second;
358    }
359    points_.preInsn.erase(pre, points_.preInsn.end());
360
361    InsnPoints::iterator post = points_.postInsn.lower_bound(succ->start());
362    for (InsnPoints::iterator tmp = post; tmp != points_.postInsn.end(); ++tmp) {
363       tmp->second->changeBlock(succ);
364       succ->points_.postInsn[tmp->first] = tmp->second;
365    }
366    points_.postInsn.erase(post, points_.postInsn.end());
367
368    std::vector<PatchFunction *> funcs;
369    getFunctions(std::back_inserter(funcs));
370    for (unsigned i = 0; i < funcs.size(); ++i) {
371       funcs[i]->splitPoints(this, succ);
372    }
373 }
374
375