Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / dominator.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 class BPatch_basicBlock;
33 class BPatch_flowGraph;
34 class dominatorCFG;
35 class dominatorBB;
36
37 #include "dyninstAPI/h/BPatch_Set.h"
38 #include "dyninstAPI/h/BPatch_Vector.h"
39 #include "common/h/Dictionary.h"
40
41 class dominatorBB {
42    friend class dominatorCFG;
43 protected:
44    int dfs_no;
45    int size;
46    dominatorBB *semiDom;
47    dominatorBB *immDom;
48    dominatorBB *label;
49    dominatorBB *ancestor;
50    dominatorBB *parent;
51    dominatorBB *child;
52
53    BPatch_basicBlock *bpatchBlock;
54    dominatorCFG *dom_cfg;
55
56    BPatch_Set<dominatorBB *> bucket;
57    BPatch_Vector<dominatorBB *> pred;
58    BPatch_Vector<dominatorBB *> succ;   
59  public:
60    dominatorBB(BPatch_basicBlock *bb, dominatorCFG *dc);
61    ~dominatorBB();
62    dominatorBB *eval();
63    void compress();
64    void dominatorPredAndSucc();
65    void postDominatorPredAndSucc();
66    int sdno();
67 };
68
69 class dominatorCFG {
70    friend class dominatorBB;
71  protected:
72    dictionary_hash<unsigned, dominatorBB *> map;
73    BPatch_flowGraph *fg;
74    BPatch_Vector<dominatorBB *> all_blocks;
75    BPatch_Vector<dominatorBB *> sorted_blocks;
76    int currentDepthNo;
77
78    dominatorBB *entryBlock;
79    dominatorBB *nullNode;
80
81    void performComputation();
82    void storeDominatorResults();
83    void depthFirstSearch(dominatorBB *v);
84    void eval(dominatorBB *v);
85    void link(dominatorBB *v, dominatorBB *w);
86    dominatorBB *bpatchToDomBB(BPatch_basicBlock *bb);
87
88  public:
89    dominatorCFG(BPatch_flowGraph *flowgraph);
90    ~dominatorCFG();
91
92    void calcDominators();
93    void calcPostDominators();
94 };
95