Fixes for non-returning functions and tail calls:
[dyninst.git] / parseAPI / src / ParserDetails.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30 #ifndef _PARSER_DETAILS_H_
31 #define _PARSER_DETAILS_H_
32
33 #include "IA_IAPI.h"
34
35 namespace Dyninst {
36 namespace ParseAPI {
37
38 namespace {
39 /*
40  * The isCode queries into CodeSource objects with
41  * disjoint regions involve expensive range lookups.
42  * Because most often isCode is called on addresses
43  * within the current function's region, this code
44  * short circuits the expensive case.
45  *
46  * NB for overlapping region CodeSources, the two
47  * cases in this function are identical. We'll pay
48  * extra in this (uncommon) case.
49  */
50 static inline bool is_code(Function * f, Address addr)
51 {
52     return f->region()->isCode(addr) ||
53            f->isrc()->isCode(addr);
54 }
55
56 }
57
58 class ParseWorkBundle;
59
60 // Seems to be an edge whose target (?) needs parsing
61
62 class ParseWorkElem
63 {
64  public:
65     /*
66      * NOTE: The order of elements in this enum is critical to parsing order.
67      * The earier an element appear in the enum, the sooner the corresponding 
68      * edges are going to be parsed.
69      *
70      * 1. Our current implementation of non-returning function analysis 
71      * WORK IFF call is prioritized over call_fallthrough.
72      *
73      * 2. We have a tail call heuristics that a jump to its own block is not a tail call.
74      * For this heuristics to be more effective, we want to traverse 
75      * certain intraprocedural edges such as call_fallthrough and cond_not_taken
76      * over potential tail call edges such as cond_taken, br_direct, and br_indirect.
77      *
78      * 3. Jump table analysis would like to have as much intraprocedural control flow
79      * as possible to resolve an indirect jump. So resolve_jump_table is delayed.
80      *
81      * Please make sure to update this comment 
82      * if you change the order of the things appearing in the enum
83      *
84      */
85     enum parse_work_order {
86         seed_addr = 0,
87         cond_not_taken,
88         ret_fallthrough, /* conditional returns */
89         call,
90         call_fallthrough,
91         cond_taken,
92         br_direct,
93         br_indirect,
94         catch_block,
95         checked_call_ft,
96         resolve_jump_table, // We want to finish all possible parsing work before parsing jump tables
97         __parse_work_end__
98     };
99
100     // allow direct access to setting order/frame type..
101     ParseWorkElem(
102             ParseWorkBundle *b, 
103             parse_work_order o,
104             Edge *e, 
105             Address target, 
106             bool resolvable,
107             bool tailcall)
108         : _bundle(b),
109           _edge(e),
110           _targ(target),
111           _can_resolve(resolvable),
112           _tailcall(tailcall),
113           _order(o),
114           _call_processed(false) { }
115
116     ParseWorkElem(
117             ParseWorkBundle *b, 
118             Edge *e, 
119             Address target, 
120             bool resolvable,
121             bool tailcall)
122         : _bundle(b),
123           _edge(e),
124           _targ(target),
125           _can_resolve(resolvable),
126           _tailcall(tailcall),
127           _order(__parse_work_end__),
128           _call_processed(false),
129           _cur(NULL),
130           _ah(NULL)
131
132     { 
133       if(e) {
134         switch(e->type()) {
135             case CALL:
136                 _order = call; break;
137             case COND_TAKEN:
138                 _order = cond_taken; break;
139             case COND_NOT_TAKEN:
140                 _order = cond_not_taken; break;
141             case INDIRECT:
142                 _order = br_indirect; break;
143             case DIRECT:
144                 {
145                     if (tailcall) {
146                         _order = call;
147                     } else {
148                         _order = br_direct; 
149                     }
150                     break;
151                 }
152             case FALLTHROUGH:
153                 _order = ret_fallthrough; break;
154             case CATCH:
155                 _order = catch_block; break;
156             case CALL_FT:
157                 _order = call_fallthrough; break;
158             default:
159                 fprintf(stderr,"[%s:%d] FATAL: bad edge type %d\n",
160                     FILE__,__LINE__,e->type());
161                 assert(0);
162         } 
163       } else 
164         _order = seed_addr;
165     }
166
167     ParseWorkElem()
168         : _bundle(NULL),
169           _edge(NULL),
170           _targ((Address)-1),
171           _can_resolve(false),
172           _tailcall(false),
173           _order(__parse_work_end__),
174           _call_processed(false),
175           _cur(NULL),
176           _ah(NULL)
177     { } 
178
179     // This work element is a continuation of
180     // parsing jump tables
181     ParseWorkElem(ParseWorkBundle *bundle, Block *b, const InsnAdapter::IA_IAPI& ah)
182          : _bundle(bundle),
183           _edge(NULL),
184           _targ((Address)-1),
185           _can_resolve(false),
186           _tailcall(false),
187           _order(resolve_jump_table),
188           _call_processed(false),
189           _cur(b) {           
190               _ah = new InsnAdapter::IA_IAPI(ah);
191           }
192
193     ~ParseWorkElem() {
194         if (_ah != NULL) delete _ah;
195     }
196
197       
198
199     ParseWorkBundle *   bundle()        const { return _bundle; }
200     Edge *              edge()          const { return _edge; }
201     Address             target()        const { return _targ; }
202     bool                resolvable()    const { return _can_resolve; }
203     parse_work_order    order()         const { return _order; }
204     void                setTarget(Address t)  { _targ = t; }
205
206     bool                tailcall()      const { return _tailcall; }
207     bool                callproc()      const { return _call_processed; }
208     void                mark_call()     { _call_processed = true; }
209
210     Block *             cur()           const { return _cur; }
211     InsnAdapter::IA_IAPI *  ah()        const { return _ah; }
212
213     /* 
214      * Note that compare treats the parse_work_order as `lowest is
215      * highest priority'.
216      *
217      * Sorts by parse_work_order, then bundle, then address
218     */
219     struct compare {
220         bool operator()(const ParseWorkElem * e1, const ParseWorkElem * e2)
221         {
222             parse_work_order o1 = e1->order();
223             parse_work_order o2 = e2->order();   
224
225             if(o1 > o2)
226                 return true;
227             else if(o1 < o2)
228                 return false;
229             else {
230                 if(e1->bundle() == e2->bundle()) 
231                     return e1->target() > e2->target();
232                 else
233                     return e1->bundle() > e2->bundle();
234             }
235         }
236     };
237
238  private:
239     ParseWorkBundle * _bundle;
240     Edge * _edge;
241     Address _targ;
242     bool _can_resolve;
243     bool _tailcall;
244     parse_work_order _order;
245     bool _call_processed;
246
247     // Data for continuing parsing jump tables
248     Block * _cur;
249     InsnAdapter::IA_IAPI * _ah;
250 };
251
252 // ParseWorkElem container
253
254 class ParseWorkBundle
255 {
256  public:
257     ParseWorkBundle() {}
258     ~ParseWorkBundle()
259     {
260         for(unsigned i=0;i<_elems.size();++i)
261             delete _elems[i];
262     }
263
264     ParseWorkElem* add(ParseWorkElem * e) 
265     { 
266         _elems.push_back(e);
267         return e;
268     }
269     vector<ParseWorkElem*> const& elems() { return _elems; }
270  private:
271     vector<ParseWorkElem*> _elems;
272 };
273
274 } // ParseAPI
275 } // Dyninst
276
277 #endif