Prevent duplicate return edge creation in Function::blocks_int
[dyninst.git] / parseAPI / src / Function.C
1 #include <algorithm>
2
3 #include "dyntypes.h"
4
5 #include "CodeObject.h"
6 #include "CFG.h"
7
8 #include "Parser.h"
9 #include "debug_parse.h"
10 #include "util.h"
11
12 using namespace std;
13
14 using namespace Dyninst;
15 using namespace Dyninst::ParseAPI;
16
17 Function::Function() :
18         _start(0),
19         _obj(NULL),
20         _region(NULL),
21         _isrc(NULL),
22         _src(RT),
23         _rs(UNSET),
24         _entry(NULL),
25         _parsed(false),
26         _cache_valid(false),
27         _bl(_blocks),
28         _call_edge_list(_call_edges),
29         _retBL(_return_blocks),
30         _no_stack_frame(true),
31         _saves_fp(false),
32         _cleans_stack(false),
33         _tamper(TAMPER_UNSET),
34         _tamper_addr(0)
35 {
36     fprintf(stderr,"PROBABLE ERROR, default ParseAPI::Function constructor\n");
37 }
38
39 Function::Function(Address addr, string name, CodeObject * obj, 
40     CodeRegion * region, InstructionSource * isrc) :
41         _start(addr),
42         _obj(obj),
43         _region(region),
44         _isrc(isrc),
45         _src(RT),
46         _rs(UNSET),
47         _name(name),
48         _entry(NULL),
49         _parsed(false),
50         _cache_valid(false),
51         _bl(_blocks),
52         _call_edge_list(_call_edges),
53         _retBL(_return_blocks),
54         _no_stack_frame(true),
55         _saves_fp(false),
56         _cleans_stack(false),
57         _tamper(TAMPER_UNSET),
58         _tamper_addr(0)
59 {
60     
61 }
62
63
64 Function::~Function()
65 {
66     vector<FuncExtent *>::iterator eit = _extents.begin();
67     for( ; eit != _extents.end(); ++eit) {
68         delete *eit;
69     }
70 }
71
72 Function::blocklist &
73 Function::blocks()
74 {
75     if(!_cache_valid)
76         finalize();
77     return _bl;
78 }
79
80 Function::edgelist & 
81 Function::callEdges() {
82     if(!_cache_valid)
83         finalize();
84     return _call_edge_list; 
85 }
86
87 Function::blocklist &
88 Function::returnBlocks() {
89   if (!_cache_valid) 
90     finalize();
91   return _retBL;
92 }
93
94 vector<FuncExtent *> const&
95 Function::extents()
96 {
97     if(!_cache_valid)
98         finalize(); 
99     return _extents;
100 }
101
102 void
103 Function::finalize()
104 {
105     // The Parser knows how to finalize
106     // a Function's parse data
107     _obj->parser->finalize(this);
108 }
109
110 vector<Block *> const&
111 Function::blocks_int()
112 {
113     if(_cache_valid)
114         return _blocks;
115
116     // overloaded map warning:
117     // visited[addr] == 1 means visited
118     // visited[addr] == 2 means already on the return list
119     dyn_hash_map<Address,short> visited;
120     vector<Block *> worklist;
121
122     bool need_entry = true;
123     for(vector<Block*>::iterator bit=_blocks.begin();
124         bit!=_blocks.end();++bit) 
125     {
126         Block * b = *bit;
127         visited[b->start()] = 1;
128         need_entry = need_entry && (b != _entry);
129     }
130     worklist.insert(worklist.begin(),_blocks.begin(),_blocks.end());
131
132     if(need_entry) {
133         worklist.push_back(_entry);
134         visited[_entry->start()] = 1;
135         add_block(_entry);
136     }
137
138     // avoid duplicating return edges
139     for(vector<Block*>::iterator bit=_return_blocks.begin();
140         bit!=_return_blocks.end();++bit)
141     {
142         Block * b = *bit;
143         visited[b->start()] = 2;
144     }
145     
146     while(!worklist.empty()) {
147         Block * cur = worklist.back();
148         worklist.pop_back();
149
150         bool link_return = false;
151         const Block::edgelist & trgs = cur->targets();
152         for(Block::edgelist::iterator tit=trgs.begin();
153             tit!=trgs.end();++tit) {
154             Edge * e = *tit;
155             Block * t = e->trg();
156
157             if(e->type() == CALL) {
158                 _call_edges.push_back(e);
159                 continue;
160             }
161
162             if(e->type() == RET) {
163                 link_return = true;
164                 continue;
165             }
166
167             /* sink edges receive no further processing */
168             if(e->sinkEdge())
169                 continue;
170
171             if(!HASHDEF(visited,t->start())) {
172                 worklist.push_back(t);
173                 visited[t->start()] = true;
174                 add_block(t);
175             }
176         } 
177         if(link_return) {
178             delayed_link_return(_obj,cur);
179             if(visited[cur->start()] <= 1)
180                 _return_blocks.push_back(cur);
181         }
182     }
183
184     Block::compare comp;
185     sort(_blocks.begin(),_blocks.end(),comp);
186
187     return _blocks;
188 }
189
190 void
191 Function::delayed_link_return(CodeObject * o, Block * retblk)
192 {
193     bool link_entry = false;
194
195     dyn_hash_map<Address,bool> linked;
196     Block::edgelist::iterator eit = retblk->targets().begin();
197     for( ; eit != retblk->targets().end(); ++eit) {
198         Edge * e = *eit;
199         linked[e->trg()->start()] = true;
200     }
201
202     eit = _entry->sources().begin();
203     for( ; eit != _entry->sources().end(); ++eit) {
204         Edge * e = *eit;
205         if(e->type() == CALL) {
206             parsing_printf("[%s:%d] linking return edge %lx -> %lx\n",
207                 FILE__,__LINE__,retblk->lastInsnAddr(),e->src()->end());
208
209             // XXX opportunity here to be more conservative about delayed
210             //     determination of return status
211     
212             Block * call_ft = _obj->findBlockByEntry(region(),e->src()->end());
213             if(!call_ft) {
214                 parsing_printf("[%s:%d] no block found, error!\n",
215                     FILE__,__LINE__);
216             } 
217             else if(!HASHDEF(linked,call_ft->start())) {
218                 if(call_ft == _entry)
219                     link_entry = true;
220                 else 
221                     o->add_edge(retblk,call_ft,RET);
222                 linked[call_ft->start()] = true;
223             }
224         }
225     }
226     // can't do this during iteration
227     if(link_entry)
228         o->add_edge(retblk,_entry,RET);
229 }
230
231 void
232 Function::add_block(Block *b)
233 {
234     ++b->_func_cnt;            // block counts references
235     _blocks.push_back(b);
236     _bmap[b->start()] = b;
237 }
238
239 const string &
240 Function::name() 
241 {
242     return _name;
243 }
244
245 bool
246 Function::contains(Block *b)
247 {
248     if(!_cache_valid)
249         finalize();
250
251     return HASHDEF(_bmap,b->start());
252 }
253
254 void 
255 Function::deleteBlocks(vector<Block*> &dead_blocks, Block * new_entry)
256 {
257     _cache_valid = false;
258     if (new_entry) {
259         _start = new_entry->start();
260         _entry = new_entry;
261     }
262
263     for (unsigned didx=0; didx < dead_blocks.size(); didx++) {
264         bool found = false;
265         Block *dead = dead_blocks[didx];
266
267         // remove dead block from _blocks
268         std::vector<Block *>::iterator biter = _blocks.begin();
269         while ( !found && _blocks.end() != biter ) {
270             if (dead == *biter) {
271                 found = true;
272                 biter = _blocks.erase(biter);
273             }
274             else {
275                 biter++;
276             }
277         }
278         if (!found) {
279             fprintf(stderr,"Error, tried to remove block [%lx,%lx) from "
280                     "function at %lx that it does not belong to at %s[%d]\n",
281                     dead->start(),dead->end(), addr(), FILE__,__LINE__);
282             assert(0);
283         }
284
285         // remove dead block from _return_blocks and its call edges from vector
286         Block::edgelist & outs = dead->targets();
287         found = false;
288         
289         for (Block::edgelist::iterator oit = outs.begin();
290              !found && outs.end() != oit; 
291              oit++ ) 
292         {
293             switch((*oit)->type()) {
294                 case CALL:
295                     for (vector<Edge*>::iterator cit = _call_edges.begin(); 
296                          !found && _call_edges.end() != cit; 
297                          cit++) 
298                     {
299                         if (*oit == *cit) {
300                             found = true;
301                             _call_edges.erase(cit);
302                         }
303                     }
304                     assert(found);
305                     break;
306                 case RET:
307                     for (vector<Block*>::iterator rit = _return_blocks.begin();
308                          !found && _return_blocks.end() != rit; 
309                          rit++) 
310                     {
311                         if ((*oit)->trg() == *rit) {
312                             found = true;
313                             _return_blocks.erase(rit);
314                         }
315                     }
316                     break;
317                 default:
318                     break;
319             }
320         }
321         // remove dead block from block map
322         _bmap.erase(dead->start());
323
324         // disconnect dead block from CFG
325         if (1 < dead->containingFuncs()) {
326             for (unsigned sidx=0; sidx < dead->_sources.size(); sidx++) {
327                 Edge *edge = dead->_sources[sidx];
328                 edge->src()->removeTarget( edge );
329             }
330             for (unsigned tidx=0; tidx < dead->_targets.size(); tidx++) {
331                 Edge *edge = dead->_targets[tidx];
332                 edge->trg()->removeSource( edge );
333             }
334         }
335     }
336
337     // call finalize, fixes extents
338     obj()->parser->finalize(this);
339
340     // delete the blocks
341     for (unsigned didx=0; didx < dead_blocks.size(); didx++) {
342         Block *dead = dead_blocks[didx];
343         if (1 <= dead->containingFuncs()) {
344             dead->removeFunc(this);
345             mal_printf("WARNING: removing shared block [%lx %lx] rather "
346                        "than deleting it %s[%d]\n", dead->start(), 
347                        dead->end(), FILE__,__LINE__);
348         } else {
349             obj()->fact()->free_block(dead);
350         }
351     }
352 }
353