Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / h / BPatch_flowGraph.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #ifndef _BPatch_flowGraph_h_
33 #define _BPatch_flowGraph_h_
34
35 #include <string>
36 #include <set>
37 #include "Annotatable.h"
38 #include "BPatch_dll.h"
39 #include "BPatch_Vector.h"
40 #include "BPatch_Set.h"
41 #include "BPatch_basicBlock.h"
42 #include "BPatch_basicBlockLoop.h"
43 #include "BPatch_eventLock.h"
44 #include "BPatch_loopTreeNode.h"
45
46 class int_function;
47 class process;
48 class AddressSpace;
49 class BPatch_edge;
50
51 typedef BPatch_basicBlockLoop BPatch_loop;
52
53 /** class which represents the control flow graph of a function
54   * in a executable code. 
55   *
56   * @see BPatch_basicBlock
57   * @see BPatch_basicBlockLoop
58   */
59 #ifdef DYNINST_CLASS_NAME
60 #undef DYNINST_CLASS_NAME
61 #endif
62 #define DYNINST_CLASS_NAME BPatch_flowGraph
63
64 class BPATCH_DLL_EXPORT BPatch_flowGraph : 
65       public BPatch_eventLock, 
66       public Dyninst::AnnotatableSparse 
67 {
68   friend class BPatch_basicBlock;
69   friend class BPatch_function;
70   friend class dominatorCFG;
71   friend class int_function; // This is illegal here... keeps us from having to
72                             // have a public constructor...  PDSEP
73   friend std::ostream& operator<<(std::ostream&,BPatch_flowGraph&);
74   friend void dfsCreateLoopHierarchy(BPatch_loopTreeNode * parent,
75                                      BPatch_Vector<BPatch_basicBlockLoop *> &loops,
76                                      std::string level);
77  
78   BPatch_flowGraph (BPatch_function *func, bool &valid); 
79
80   int_function *ll_func() const;
81 public:
82
83   //BPatch_process *getBProcess() const { return bproc; }
84   BPatch_addressSpace *getAddSpace() const { return addSpace; }
85   AddressSpace *getllAddSpace() const;
86   BPatch_function *getBFunction() const { return func_; }
87   BPatch_module *getModule() const { return mod; }
88   //  End of deprecated function
89
90   //  Functions for use by Dyninst users
91
92   API_EXPORT_DTOR(_dtor, (),
93   ~,BPatch_flowGraph,());
94
95   /** returns the set of all basic blocks in the CFG */
96   API_EXPORT(Int, (blocks),
97   bool,getAllBasicBlocks,(BPatch_Set<BPatch_basicBlock*> &blocks)); 
98
99   API_EXPORT(STL, (blocks),
100   bool, getAllBasicBlocks,(std::set<BPatch_basicBlock *> &blocks));
101   
102   /** returns the vector of entry basic blocks to CFG */
103   API_EXPORT(Int, (blocks),
104   bool,getEntryBasicBlock,(BPatch_Vector<BPatch_basicBlock*> &blocks));
105   
106   /** returns the vector of exit basic blocks to CFG */
107   API_EXPORT(Int, (blocks),
108   bool,getExitBasicBlock,(BPatch_Vector<BPatch_basicBlock*> &blocks));
109   
110   /** returns the vector of loops in CFG */
111   API_EXPORT(Int, (loops),
112   bool,getLoops,(BPatch_Vector<BPatch_basicBlockLoop*> &loops));
113
114   /** returns a vector of outer loops in the CFG */
115   API_EXPORT(Int, (loops),
116   bool,getOuterLoops,(BPatch_Vector<BPatch_basicBlockLoop*> &loops));
117
118   /** creates the source line blocks of all blocks in CFG.
119    * without calling this method line info is not available
120    */
121   API_EXPORT(Int, (),
122   bool,createSourceBlocks,());
123   
124   /** fills the dominator and immediate-dom information of basic blocks.
125    * without calling this method dominator info is not available
126    */
127   API_EXPORT_V(Int, (),
128   void,fillDominatorInfo,());
129
130   /** same as above, but for postdominator/immediate-postdom info 
131    */
132   API_EXPORT_V(Int, (),
133   void,fillPostDominatorInfo,());
134
135   /** return root of loop hierarchy  */
136   API_EXPORT(Int, (),
137   BPatch_loopTreeNode *,getLoopTree,());
138
139   /** returns true if the cfg contains dynamic callsites */
140   API_EXPORT(Int, (),
141   bool,containsDynamicCallsites,());
142
143   // for debugging, print loops with line numbers to stderr
144   API_EXPORT_V(Int, (),
145   void,printLoops,());
146
147   API_EXPORT(Int, (name),
148   BPatch_basicBlockLoop *,findLoop,(const char *name));
149
150   // Deprecated - this should not be an API method
151   //API_EXPORT_V(Int, (),
152   //void, initLivenessInfo,());
153
154   /*
155   API_EXPORT(Int, (edge),
156   BPatch_point *,createInstPointAtEdge,(BPatch_edge *edge));
157   */
158   // Deprecated... use BPatch_edge->point() instead
159   
160   /** find instrumentation points specified by loc, add to points*/
161   API_EXPORT(Int, (loc, loop),
162   BPatch_Vector<BPatch_point*> *,
163       findLoopInstPoints,(CONST_EXPORT BPatch_procedureLocation loc, 
164                           BPatch_basicBlockLoop *loop));
165
166  private:
167
168   BPatch_function *func_;
169   BPatch_addressSpace *addSpace;
170   //  BPatch_process *bproc;
171   BPatch_module *mod;
172
173   /** set of loops contained in control flow graph */
174   BPatch_Set<BPatch_basicBlockLoop*> *loops;
175   
176   /** set of all basic blocks that control flow graph has */
177   BPatch_Set<BPatch_basicBlock*, BPatch_basicBlock::compare> allBlocks;
178
179   /** root of the tree of loops */
180   BPatch_loopTreeNode *loopRoot;
181
182   /** set of back edges */
183   BPatch_Set<BPatch_edge*> backEdges;
184   
185   /** flag that keeps whether dominator info is initialized*/
186   bool isDominatorInfoReady;
187
188   /** flag that keeps whether postdominator info is initialized*/
189   bool isPostDominatorInfoReady;
190   
191   /** flag that keeps whether source block info is initialized*/
192   bool isSourceBlockInfoReady;
193   
194   bool createBasicBlocks();
195   
196   /** create the tree of loops/callees for this flow graph */
197   void createLoopHierarchy();
198   
199   void dfsVisitWithTargets(BPatch_basicBlock*,int*); 
200
201   void dfsVisitWithSources(BPatch_basicBlock*,int*); 
202   
203   void findAndDeleteUnreachable();
204   
205   static void findBBForBackEdge(BPatch_edge*,
206                                 BPatch_Set<BPatch_basicBlock*>&);
207
208
209   void getLoopsByNestingLevel(BPatch_Vector<BPatch_basicBlockLoop*>&, 
210                               bool outerMostOnly);
211   
212   bool dfsInsertCalleeIntoLoopHierarchy(BPatch_loopTreeNode *node, 
213                                         int_function *func,
214                                         unsigned long addr);
215
216   void insertCalleeIntoLoopHierarchy(int_function * func, unsigned long addr);
217
218   void dfsPrintLoops(BPatch_loopTreeNode *n);
219
220   void createBackEdges();
221   void createLoops();
222
223   void dump();
224
225
226   void findLoopExitInstPoints(BPatch_basicBlockLoop *loop,
227                               BPatch_Vector<BPatch_point*> *points);
228
229 };
230
231
232 #endif /* _BPatch_flowGraph_h_ */