Update copyright to LGPL on all files
[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  * 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 "analyzeFDG.h"
33
34 // std
35 #include <set>
36 #include <vector>
37
38 // depGraphAPI
39 #include "Node.h"
40 #include "DepGraphNode.h" // for BlockNode
41
42 // Dyninst
43 #include "BPatch_basicBlock.h"
44 #include "BPatch_edge.h"
45 #include "BPatch_flowGraph.h"
46 #include "BPatch_function.h"
47
48 // Annotation interface
49 #include "Annotatable.h"
50
51 using namespace std;
52 using namespace Dyninst;
53 using namespace Dyninst::DepGraphAPI;
54 using namespace Dyninst::InstructionAPI;
55
56 static AnnotationClass <FDG::Ptr> FDGAnno(std::string("FDGAnno"));
57
58 FDGAnalyzer::~FDGAnalyzer() {}
59
60 FDG::Ptr FDGAnalyzer::analyze() {
61     if (fdg) return fdg;
62
63     if (func_ == NULL) return FDG::Ptr();
64
65     FDG::Ptr *ret;
66     func_->getAnnotation(ret, FDGAnno);
67     if (ret) {
68         fdg = *ret;
69         return fdg;
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     BlockSet blocks;
75     func_->getCFG()->getAllBasicBlocks(blocks);
76
77     // Create a graph
78     fdg = FDG::createGraph();
79     
80     // mark blocks that end with a jump/return/branch instruction.
81     markBlocksWithJump(blocks);
82     // find the dependencies between blocks.
83     findDependencies(blocks);
84     
85     // finally, create block level nodes.
86     createNodes(blocks);
87     
88     // Store as an annotation and return
89     FDG::Ptr *ptr = new FDG::Ptr(fdg);
90     func_->addAnnotation(ptr, FDGAnno);
91
92     return fdg;
93 }
94
95 /**
96  * Finds all blocks that end with a jump/return/branch instruction and puts them in
97  * markedBlocks member list. It also stores the last instruction of marked blocks.
98  */
99 void FDGAnalyzer::markBlocksWithJump(BlockSet &blocks) {
100   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
101     Block* block = *blockIter;
102     vector<Instruction::Ptr> instructions;
103     block->getInstructions(instructions);
104
105     assert(instructions.size() > 0);
106
107     Instruction::Ptr lastInst = instructions.back();
108     const Operation& opType = lastInst->getOperation();
109     
110     if (isReturnOp(opType) || isBranchOp(opType)) {
111       markedBlocks.insert(block);
112     }
113   }
114 }
115
116 void FDGAnalyzer::findDependencies(BlockSet &blocks) {
117   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
118     Block* block = *blockIter;
119     BlockSet blocksWithJumps;
120     BlockSet visited;
121     findBlocksRecursive(blocksWithJumps, visited, block);
122     blockToJumps[block] = blocksWithJumps;
123   }
124 }
125
126 void FDGAnalyzer::findBlocksRecursive(BlockSet& needThese, 
127                                       BlockSet& visited,
128                                       Block* givenBlock) {
129   if ((visited.find(givenBlock) != visited.end())) {
130     return;
131   }
132   visited.insert(givenBlock);
133   
134   vector<BPatch_edge*> outEdges;
135   givenBlock->getOutgoingEdges(outEdges);
136   for (unsigned i = 0; i < outEdges.size(); i++) {
137     Block* target = outEdges[i]->getTarget();
138     // if the target terminates anything other than a call, it is added to the list, and we don't
139     // search on this branch anymore. If not, keep looking!
140     if (markedBlocks.find(target) != markedBlocks.end()) {
141       needThese.insert(target);
142     }
143     else {
144       findBlocksRecursive(needThese, visited, target);
145     }
146   }
147 }
148
149 Node::Ptr FDGAnalyzer::makeNode(NodeMap& nodeMap, Block* block) {
150     if (nodeMap[block]) {
151         return nodeMap[block];
152     }
153     Node::Ptr blockNode = BlockNode::createNode(block);
154     nodeMap[block] = blockNode;
155     return blockNode;
156 }
157
158 void FDGAnalyzer::createNodes(BlockSet &blocks) {
159     NodePtr virtNode = fdg->virtualEntryNode();
160     NodeMap nodeMap;
161     for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
162         Block* block = *blockIter;
163         
164         Node::Ptr blockNode = makeNode(nodeMap, block);
165         fdg->addNode(blockNode);
166         fdg->insertPair(virtNode, blockNode);
167         
168         BlockSet& targets = blockToJumps[block];
169         for (BlockSet::iterator blIter = targets.begin(); blIter != targets.end(); blIter++) {
170             Node::Ptr source = makeNode(nodeMap, *blIter);
171             fdg->addNode(source);
172             fdg->insertPair(source, blockNode);
173         }
174     }
175 }
176 /**************************************************************************************************/
177 /****************************   static functions   ************************************************/
178 bool FDGAnalyzer::isReturnOp(const Operation& opType) {
179     return (entryToCategory(opType.getID()) == c_ReturnInsn);
180 }
181
182 bool FDGAnalyzer::isBranchOp(const Operation& opType) {
183     return (entryToCategory(opType.getID()) == c_BranchInsn);
184 }