This commit enables arbitrary instrumentation points at the last instruction
[dyninst.git] / dyninstAPI / h / BPatch_flowGraph.h
1 #ifndef _BPatch_flowGraph_h_
2 #define _BPatch_flowGraph_h_
3
4 #include "BPatch_dll.h"
5 #include "BPatch_Vector.h"
6 #include "BPatch_Set.h"
7 #include "BPatch_basicBlock.h"
8 #include "BPatch_basicBlockLoop.h"
9
10 class BPatch_image;
11
12 /** class which represents the control flow graph of a function
13   * in a executable code. 
14   *
15   * @see BPatch_basicBlock
16   * @see BPatch_basicBlockLoop
17   */
18 class BPATCH_DLL_EXPORT BPatch_flowGraph {
19         friend class BPatch_function;
20         friend class BPatch_basicBlock;
21         friend ostream& operator<<(ostream&,BPatch_flowGraph&);
22
23 private:
24         /** bpatch function for which the CFG is generated */
25         BPatch_function* bpFunction;
26
27         /** set of basic blocks that are entry to the control flow graph*/
28         BPatch_Set<BPatch_basicBlock*> entryBlock;
29
30         /** set of basic blocks that are exit from the control flow graph */
31         BPatch_Set<BPatch_basicBlock*> exitBlock;
32
33         /** set of loops contained in control flow graph */
34         BPatch_Set<BPatch_basicBlockLoop*>* loops;
35         
36         /** set of all basic blocks that control flow graph has */
37         BPatch_Set<BPatch_basicBlock*> allBlocks;
38
39 public:
40         /** destructor for the class */
41         ~BPatch_flowGraph();
42
43         /** returns the set of all basic blocks in the CFG */
44         void getAllBasicBlocks(BPatch_Set<BPatch_basicBlock*>&);
45
46         /** returns the vector of entry basic blocks to CFG */
47         void getEntryBasicBlock(BPatch_Vector<BPatch_basicBlock*>&);
48
49         /** returns the vector of exit basic blocks to CFG */
50         void getExitBasicBlock(BPatch_Vector<BPatch_basicBlock*>&);
51
52         /** returns the vector of loops in CFG */
53         void getLoops(BPatch_Vector<BPatch_basicBlockLoop*>&);
54
55         /** creates the source line blocks of all blocks in CFG.
56           * without calling this method line info is not available
57           */
58         void createSourceBlocks();
59
60         /** fills the dominator and immediate-dom information of basic blocks.
61           * without calling this method dominator info is not available
62           */
63         void fillDominatorInfo();
64 private:
65         /** three colors used in depth first search algorithm */
66         static const int WHITE;
67         static const int GRAY;
68         static const int BLACK;
69
70         /** flag that keeps whether dominator info is initialized*/
71         bool isDominatorInfoReady;
72
73         /** flag that keeps whether source block info is initialized*/
74         bool isSourceBlockInfoReady;
75
76         /** constructor of the class */
77         BPatch_flowGraph(BPatch_function*);
78
79         /** constructor for the class */
80         BPatch_flowGraph(BPatch_image*,char*);
81
82         void createBasicBlocks();
83
84         void fillLoopInfo(BPatch_Set<BPatch_basicBlock*>**,BPatch_basicBlock**);
85
86         void dfsVisit(BPatch_basicBlock*,int*,
87                       BPatch_Set<BPatch_basicBlock*>**,
88                       int* which=NULL,BPatch_basicBlock** order=NULL); 
89
90         void findBackEdges(BPatch_Set<BPatch_basicBlock*>**);
91
92         void findAndDeleteUnreachable();
93
94         static void findBBForBackEdge(BPatch_basicBlock*,BPatch_basicBlock*,
95                                       BPatch_Set<BPatch_basicBlock*>&);
96 };
97
98 #endif /* _BPatch_flowGraph_h_ */