Update DepGraphAPI source files to conform with published API.
[dyninst.git] / depGraphAPI / src / analyzeCDG.C
1 /*
2  * Copyright (c) 2007-2008 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 #include <set>
33 #include <vector>
34
35 #include "analyzeCDG.h"
36
37 #include "Absloc.h"
38 #include "Graph.h"
39 #include "CDG.h"
40
41 // Dyninst
42 #include "BPatch_basicBlock.h"
43 #include "BPatch_flowGraph.h"
44 #include "BPatch_function.h"
45
46 // InstructionAPI
47 #include "Instruction.h"
48
49 // Annotation interface
50 #include "Annotatable.h"
51
52
53 using namespace std;
54 using namespace Dyninst;
55 using namespace Dyninst::DepGraphAPI;
56 using namespace Dyninst::InstructionAPI;
57
58 AnnotationClass <CDG::Ptr> CDGAnno(std::string("CDGAnno"));
59
60 CDGAnalyzer::CDGAnalyzer(Function *f) : func_(f) {};
61
62 CDG::Ptr CDGAnalyzer::analyze() {
63     if (func_ == NULL) return CDG::Ptr();
64
65     CDG::Ptr *ret;
66     func_->getAnnotation(ret, CDGAnno);
67     if (ret) {
68         cdg = *ret;
69         return cdg;
70     }
71
72     // What we really want to hand into this is a CFG... for
73     // now, the set of blocks and entry block will suffice.
74     CDGAnalyzer::BlockSet blocks;
75     func_->getCFG()->getAllBasicBlocks(blocks);
76
77     // Create a graph
78     cdg = CDG::createGraph();
79     
80     // create the dependencies between blocks
81     createInterBlockDeps(blocks);
82     
83     // create instruction-level nodes and insert them into the graph
84     createNodeDeps(blocks);
85
86     // Store as an annotation and return
87     CDG::Ptr *ptr = new CDG::Ptr(cdg);
88     func_->addAnnotation(ptr, CDGAnno);
89     
90     return cdg;
91 }
92
93 /**
94  * Creates control flow dependencies between blocks. For more info, see Ferrante et. al.'s
95  * "The program dependence graph and its use in optimization".
96  */
97 void CDGAnalyzer::createInterBlockDeps(BlockSet &blocks) {
98     for (BlockSet::iterator blockIter = blocks.begin(); 
99          blockIter != blocks.end(); blockIter++) {
100     Block* block = *blockIter;
101     vector<Block*> out;
102     block->getTargets(out);
103     for (unsigned i = 0; i < out.size(); i++) {
104       if (out[i]->postdominates(block)) {
105         continue;
106       }
107
108       // Work on this edge right now: mark all parents of 'block'
109       // According to Ferrante et al. page 325, marking only this node and its parent is enough
110       Block* parent = block->getImmediatePostDominator();
111
112       // traverse from out[i] to one of the parents marked in the previous step
113       for (Block* temp = out[i]; 
114            (temp != NULL) && (temp != block) && (temp != parent);
115            temp = temp->getImmediatePostDominator()) {
116         // mark them as control dependent to 'block'
117         dependencies[ temp ].insert(block);
118       }
119     }
120   }
121 }
122
123 void CDGAnalyzer::createNodeDeps(BlockSet &) {
124     //createNodes();
125     createDependencies();
126 }
127
128 /**
129  * Creates individual nodes for each instruction and insert an edge from a virtual node to all
130  * the nodes to avoid garbage collection by boost.
131  */
132 void CDGAnalyzer::createNodes(BlockSet &blocks) {
133
134     for (BlockSet::iterator blockIter = blocks.begin(); 
135          blockIter != blocks.end(); blockIter++) {
136
137         NodePtr node = BlockNode::createNode(*blockIter);
138         nodeMap[*blockIter] = node;
139     }
140 }
141
142 /**
143  * Creates dependencies at the instruction level using the dependencies at the Block level.
144  */
145 void CDGAnalyzer::createDependencies() {
146     for (BlockMap::iterator iter = dependencies.begin(); 
147          iter != dependencies.end(); iter++) {
148         // Everything in iter->second depends on iter->first...
149         Node::Ptr source = makeNode(iter->first);
150
151         for (BlockSet::iterator blockIter = iter->second.begin();
152              blockIter != iter->second.end();
153              blockIter++) {
154             Node::Ptr target = makeNode(*blockIter);
155
156             cdg->insertPair(source, target);
157         }
158     }
159 }
160
161 Node::Ptr CDGAnalyzer::makeNode(Block *b) {
162     if (nodeMap.find(b) == nodeMap.end()) {
163         Node::Ptr newNode = BlockNode::createNode(b);
164         nodeMap[b] = newNode;
165     }
166     
167     return nodeMap[b];
168 }