DepGraphAPI fixes
[dyninst.git] / depGraphAPI / src / analyzeFDG.C
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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  *
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  *
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  *
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  *
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 #include "analyzeFDG.h"
43
44 // std
45 #include <set>
46 #include <vector>
47
48 // depGraphAPI
49 #include "Node.h"
50 #include "DepGraphNode.h" // for BlockNode
51
52 // Dyninst
53 #include "BPatch_basicBlock.h"
54 #include "BPatch_edge.h"
55 #include "BPatch_flowGraph.h"
56 #include "BPatch_function.h"
57
58 // Annotation interface
59 #include "Annotatable.h"
60
61 using namespace std;
62 using namespace Dyninst;
63 using namespace Dyninst::DepGraphAPI;
64 using namespace Dyninst::InstructionAPI;
65
66 static AnnotationClass <FDG::Ptr> FDGAnno(std::string("FDGAnno"));
67
68 FDGAnalyzer::~FDGAnalyzer() {}
69
70 FDG::Ptr FDGAnalyzer::analyze() {
71     if (fdg) return fdg;
72
73     if (func_ == NULL) return FDG::Ptr();
74
75     FDG::Ptr *ret;
76     func_->getAnnotation(ret, FDGAnno);
77     if (ret) {
78         fdg = *ret;
79         return fdg;
80     }
81
82     // What we really want to hand into this is a CFG... for
83     // now, the set of blocks and entry block will suffice.
84     BlockSet blocks;
85     func_->getCFG()->getAllBasicBlocks(blocks);
86
87     // Create a graph
88     fdg = FDG::createGraph();
89     
90     // mark blocks that end with a jump/return/branch instruction.
91     markBlocksWithJump(blocks);
92     // find the dependencies between blocks.
93     findDependencies(blocks);
94     
95     // finally, create block level nodes.
96     createNodes(blocks);
97     
98     // Store as an annotation and return
99     FDG::Ptr *ptr = new FDG::Ptr(fdg);
100     func_->addAnnotation(ptr, FDGAnno);
101
102     return fdg;
103 }
104
105 /**
106  * Finds all blocks that end with a jump/return/branch instruction and puts them in
107  * markedBlocks member list. It also stores the last instruction of marked blocks.
108  */
109 void FDGAnalyzer::markBlocksWithJump(BlockSet &blocks) {
110   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
111     Block* block = *blockIter;
112     vector<Instruction::Ptr> instructions;
113     block->getInstructions(instructions);
114
115     assert(instructions.size() > 0);
116
117     Instruction::Ptr lastInst = instructions.back();
118     const Operation& opType = lastInst->getOperation();
119     
120     if (isReturnOp(opType) || isBranchOp(opType)) {
121       markedBlocks.insert(block);
122     }
123   }
124 }
125
126 void FDGAnalyzer::findDependencies(BlockSet &blocks) {
127   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
128     Block* block = *blockIter;
129     BlockSet blocksWithJumps;
130     BlockSet visited;
131     findBlocksRecursive(blocksWithJumps, visited, block);
132     blockToJumps[block] = blocksWithJumps;
133   }
134 }
135
136 void FDGAnalyzer::findBlocksRecursive(BlockSet& needThese, 
137                                       BlockSet& visited,
138                                       Block* givenBlock) {
139   if ((visited.find(givenBlock) != visited.end())) {
140     return;
141   }
142   visited.insert(givenBlock);
143   
144   vector<BPatch_edge*> outEdges;
145   givenBlock->getOutgoingEdges(outEdges);
146   for (unsigned i = 0; i < outEdges.size(); i++) {
147     Block* target = outEdges[i]->getTarget();
148     // if the target terminates anything other than a call, it is added to the list, and we don't
149     // search on this branch anymore. If not, keep looking!
150     if (markedBlocks.find(target) != markedBlocks.end()) {
151       needThese.insert(target);
152     }
153     else {
154       findBlocksRecursive(needThese, visited, target);
155     }
156   }
157 }
158
159 Node::Ptr FDGAnalyzer::makeNode(NodeMap& nodeMap, Block* block) {
160     if (nodeMap[block]) {
161         return nodeMap[block];
162     }
163     Node::Ptr blockNode = BlockNode::createNode(block);
164     nodeMap[block] = blockNode;
165     return blockNode;
166 }
167
168 void FDGAnalyzer::createNodes(BlockSet &blocks) {
169     NodePtr virtNode = fdg->virtualEntryNode();
170     NodeMap nodeMap;
171     for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
172         Block* block = *blockIter;
173         
174         Node::Ptr blockNode = makeNode(nodeMap, block);
175         fdg->addNode(blockNode);
176         fdg->insertPair(virtNode, blockNode);
177         
178         BlockSet& targets = blockToJumps[block];
179         for (BlockSet::iterator blIter = targets.begin(); blIter != targets.end(); blIter++) {
180             Node::Ptr source = makeNode(nodeMap, *blIter);
181             fdg->addNode(source);
182             fdg->insertPair(source, blockNode);
183         }
184     }
185 }
186 /**************************************************************************************************/
187 /****************************   static functions   ************************************************/
188 bool FDGAnalyzer::isReturnOp(const Operation& opType) {
189     return (entryToCategory(opType.getID()) == c_ReturnInsn);
190 }
191
192 bool FDGAnalyzer::isBranchOp(const Operation& opType) {
193     return (entryToCategory(opType.getID()) == c_BranchInsn);
194 }