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