Priorize existing call fallthrough edges over any jumps to increase the effectiveness...
[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     enum parse_work_order {
66         seed_addr = 0,
67         ret_fallthrough, /* conditional returns */
68         call_fallthrough,
69         cond_taken,
70         cond_not_taken,
71         br_direct,
72         br_indirect,
73         catch_block,
74         call,
75         checked_call_ft,
76         resolve_jump_table, // We want to finish all possible parsing work before parsing jump tables
77         __parse_work_end__
78     };
79
80     // allow direct access to setting order/frame type..
81     ParseWorkElem(
82             ParseWorkBundle *b, 
83             parse_work_order o,
84             Edge *e, 
85             Address target, 
86             bool resolvable,
87             bool tailcall)
88         : _bundle(b),
89           _edge(e),
90           _targ(target),
91           _can_resolve(resolvable),
92           _tailcall(tailcall),
93           _order(o),
94           _call_processed(false) { }
95
96     ParseWorkElem(
97             ParseWorkBundle *b, 
98             Edge *e, 
99             Address target, 
100             bool resolvable,
101             bool tailcall)
102         : _bundle(b),
103           _edge(e),
104           _targ(target),
105           _can_resolve(resolvable),
106           _tailcall(tailcall),
107           _order(__parse_work_end__),
108           _call_processed(false),
109           _cur(NULL),
110           _ah(NULL)
111
112     { 
113       if(e) {
114         switch(e->type()) {
115             case CALL:
116                 _order = call; break;
117             case COND_TAKEN:
118                 _order = cond_taken; break;
119             case COND_NOT_TAKEN:
120                 _order = cond_not_taken; break;
121             case INDIRECT:
122                 _order = br_indirect; break;
123             case DIRECT:
124                 {
125                     if (tailcall) {
126                         _order = call;
127                     } else {
128                         _order = br_direct; 
129                     }
130                     break;
131                 }
132             case FALLTHROUGH:
133                 _order = ret_fallthrough; break;
134             case CATCH:
135                 _order = catch_block; break;
136             case CALL_FT:
137                 _order = call_fallthrough; break;
138             default:
139                 fprintf(stderr,"[%s:%d] FATAL: bad edge type %d\n",
140                     FILE__,__LINE__,e->type());
141                 assert(0);
142         } 
143       } else 
144         _order = seed_addr;
145     }
146
147     ParseWorkElem()
148         : _bundle(NULL),
149           _edge(NULL),
150           _targ((Address)-1),
151           _can_resolve(false),
152           _tailcall(false),
153           _order(__parse_work_end__),
154           _call_processed(false),
155           _cur(NULL),
156           _ah(NULL)
157     { } 
158
159     // This work element is a continuation of
160     // parsing jump tables
161     ParseWorkElem(ParseWorkBundle *bundle, Block *b, const InsnAdapter::IA_IAPI& ah)
162          : _bundle(bundle),
163           _edge(NULL),
164           _targ((Address)-1),
165           _can_resolve(false),
166           _tailcall(false),
167           _order(resolve_jump_table),
168           _call_processed(false),
169           _cur(b) {           
170               _ah = new InsnAdapter::IA_IAPI(ah);
171           }
172
173     ~ParseWorkElem() {
174         if (_ah != NULL) delete _ah;
175     }
176
177       
178
179     ParseWorkBundle *   bundle()        const { return _bundle; }
180     Edge *              edge()          const { return _edge; }
181     Address             target()        const { return _targ; }
182     bool                resolvable()    const { return _can_resolve; }
183     parse_work_order    order()         const { return _order; }
184     void                setTarget(Address t)  { _targ = t; }
185
186     bool                tailcall()      const { return _tailcall; }
187     bool                callproc()      const { return _call_processed; }
188     void                mark_call()     { _call_processed = true; }
189
190     Block *             cur()           const { return _cur; }
191     InsnAdapter::IA_IAPI *  ah()        const { return _ah; }
192
193     /* 
194      * Note that compare treats the parse_work_order as `lowest is
195      * highest priority'.
196      *
197      * Sorts by parse_work_order, then bundle, then address
198     */
199     struct compare {
200         bool operator()(const ParseWorkElem * e1, const ParseWorkElem * e2)
201         {
202             parse_work_order o1 = e1->order();
203             parse_work_order o2 = e2->order();   
204
205             if(o1 > o2)
206                 return true;
207             else if(o1 < o2)
208                 return false;
209             else {
210                 if(e1->bundle() == e2->bundle()) 
211                     return e1->target() > e2->target();
212                 else
213                     return e1->bundle() > e2->bundle();
214             }
215         }
216     };
217
218  private:
219     ParseWorkBundle * _bundle;
220     Edge * _edge;
221     Address _targ;
222     bool _can_resolve;
223     bool _tailcall;
224     parse_work_order _order;
225     bool _call_processed;
226
227     // Data for continuing parsing jump tables
228     Block * _cur;
229     InsnAdapter::IA_IAPI * _ah;
230 };
231
232 // ParseWorkElem container
233
234 class ParseWorkBundle
235 {
236  public:
237     ParseWorkBundle() {}
238     ~ParseWorkBundle()
239     {
240         for(unsigned i=0;i<_elems.size();++i)
241             delete _elems[i];
242     }
243
244     ParseWorkElem* add(ParseWorkElem * e) 
245     { 
246         _elems.push_back(e);
247         return e;
248     }
249     vector<ParseWorkElem*> const& elems() { return _elems; }
250  private:
251     vector<ParseWorkElem*> _elems;
252 };
253
254 } // ParseAPI
255 } // Dyninst
256
257 #endif