I added a few fixes/improvements to depGraphAPI:
[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 // DDG
49 #include "Absloc.h"
50 #include "Graph.h"
51 #include "Node.h"
52
53 // Dyninst
54 #include "BPatch_basicBlock.h"
55 #include "BPatch_edge.h"
56 #include "BPatch_flowGraph.h"
57 #include "BPatch_function.h"
58
59 // InstructionAPI
60 #include "Instruction.h"
61
62 // Annotation interface
63 #include "Annotatable.h"
64
65 using namespace std;
66 using namespace Dyninst;
67 using namespace Dyninst::DepGraphAPI;
68 using namespace Dyninst::InstructionAPI;
69
70 static AnnotationClass <Graph::Ptr> FDGAnno(std::string("FDGAnno"));
71
72 FDGAnalyzer::~FDGAnalyzer() {
73   for (InstWithAddrList::iterator iter = lastInstInBlock.begin();
74       iter != lastInstInBlock.end();
75       iter++) {
76     InstWithAddr* item = *iter;
77     if (item) {
78       delete item;
79     }
80   }
81 }
82
83 Graph::Ptr FDGAnalyzer::analyze() {
84     if (fdg) return fdg;
85
86     if (func_ == NULL) return Graph::Ptr();
87
88     Graph::Ptr *ret;
89     func_->getAnnotation(ret, FDGAnno);
90     if (ret) {
91         fdg = *ret;
92         return fdg;
93     }
94
95     // What we really want to hand into this is a CFG... for
96     // now, the set of blocks and entry block will suffice.
97     BlockSet blocks;
98     func_->getCFG()->getAllBasicBlocks(blocks);
99
100     // Create a graph
101     fdg = Graph::createGraph();
102     
103     // create an array of <instruction, address> pairs indexed by block number.
104     lastInstInBlock.resize(blocks.size());
105     
106     // mark blocks that end with a jump/return/branch instruction.
107     markBlocksWithJump(blocks);
108     // find the dependencies between blocks.
109     findDependencies(blocks);
110     
111     // finally, create instruction level nodes.
112     createNodes(blocks);
113
114     return fdg;
115 }
116
117 /**
118  * Finds all blocks that end with a jump/return/branch instruction and puts them in
119  * markedBlocks member list. It also stores the last instruction of marked blocks.
120  */
121 void FDGAnalyzer::markBlocksWithJump(BlockSet &blocks) {
122   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
123     Block* block = *blockIter;
124     vector<Instruction> instructions;
125     block->getInstructions(instructions);
126
127     assert(instructions.size() > 0);
128
129     Instruction& lastInst = instructions[ instructions.size() - 1 ];
130     const Operation& opType = lastInst.getOperation();
131     
132     if (isReturnOp(opType) || isBranchOp(opType)) {
133       markedBlocks.insert(block);
134       lastInstInBlock[ block->getBlockNumber() ] =
135           new InstWithAddr(lastInst, (Address) (block->getEndAddress() - lastInst.size()));
136     }
137     else {
138       lastInstInBlock[ block->getBlockNumber() ] = NULL;
139     }
140     
141     Address address = (Address) block->getStartAddress();
142     for (unsigned i = 0; i < instructions.size(); i++) {
143       addrToBlock[address] = block;
144       address += instructions[i].size();
145     }
146   }
147 }
148
149 void FDGAnalyzer::findDependencies(BlockSet &blocks) {
150   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
151     Block* block = *blockIter;
152     BlockSet blocksWithJumps;
153     BlockSet visited;
154     findBlocksOnWay(blocksWithJumps, visited, block);
155     blockToJumps[block] = blocksWithJumps;
156   }
157 }
158
159 void FDGAnalyzer::findBlocksOnWay(BlockSet& needThese, 
160                                   BlockSet& visited, 
161                                   Block* givenBlock) {
162   if (markedBlocks.find(givenBlock) != markedBlocks.end()) {
163     needThese.insert(givenBlock);
164   }
165   findBlocksRecursive(needThese, visited, givenBlock);
166 }
167
168 void FDGAnalyzer::findBlocksRecursive(BlockSet& needThese, 
169                                       BlockSet& visited,
170                                       Block* givenBlock) {
171   if ((visited.find(givenBlock) != visited.end())) {
172     return;
173   }
174   visited.insert(givenBlock);
175   
176   vector<BPatch_edge*> outEdges;
177   givenBlock->getOutgoingEdges(outEdges);
178   for (unsigned i = 0; i < outEdges.size(); i++) {
179     Block* target = outEdges[i]->getTarget();
180     // if the target terminates anything other than a call, it is added to the list, and we don't
181     // search on this branch anymore. If not, keep looking!
182     if (markedBlocks.find(target) != markedBlocks.end()) {
183       needThese.insert(target);
184     }
185     else {
186       findBlocksRecursive(needThese, visited, target);
187     }
188   }
189 }
190
191 void FDGAnalyzer::createDepToOtherBlocks(NodeSet& nodes, 
192                                          NodePtr target) {
193   if (nodes.find(target) != nodes.end()) {
194     return;
195   }
196   nodes.insert(target);
197   Block* curBlock = addrToBlock[ target->addr() ];
198   assert(curBlock);
199   BlockSet& targets = blockToJumps[curBlock];
200   for (BlockSet::iterator blIter = targets.begin(); blIter != targets.end(); blIter++) {
201     InstWithAddr* targetInst = lastInstInBlock[ (*blIter)->getBlockNumber() ];
202     assert (targetInst);
203     if (targetInst->second == target->addr()) {
204       continue;
205     }
206     NodePtr source = PhysicalNode::createNode(targetInst->second);
207     fdg->insertPair(source, target);
208     
209     createDepToOtherBlocks(nodes, source);
210   }
211 }
212
213 bool FDGAnalyzer::createDepWithinBlock(NodeSet& nodes, 
214                                        NodePtr target) {
215   if (nodes.find(target) != nodes.end()) {
216     return true;
217   }
218   Block* curBlock = addrToBlock[ target->addr() ];
219   assert(curBlock);
220   InstWithAddr* inst = lastInstInBlock[ curBlock->getBlockNumber() ];
221   if (inst && inst->second != target->addr()) {
222     nodes.insert(target);
223     NodePtr source = PhysicalNode::createNode(inst->second);
224     fdg->insertPair(source, target);
225     
226     // since I am doing it for every instruction, I don't need to go any further now.    
227     return true;
228   }
229   return false;
230 }
231
232 void FDGAnalyzer::createNodes(BlockSet &blocks) {
233   NodePtr virtNode = VirtualNode::createNode();
234   NodeSet processedNodes;
235   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
236     Block* block = *blockIter;
237     vector<Instruction> instructions;
238     block->getInstructions(instructions);
239     
240     Address address = (Address) block->getStartAddress();
241     for (unsigned i = 0; i < instructions.size(); i++) {
242       NodePtr node = PhysicalNode::createNode(address);
243       fdg->insertPair(virtNode, node);
244       address += instructions[i].size();
245       
246       bool success = createDepWithinBlock(processedNodes, node);
247       if (!success) {
248         createDepToOtherBlocks(processedNodes, node);
249       }
250     }
251   }
252 }
253 /**************************************************************************************************/
254 /****************************   static functions   ************************************************/
255 bool FDGAnalyzer::isReturnOp(const Operation& opType) {
256     return (entryToCategory(opType.getID()) == c_ReturnInsn);
257 }
258
259 bool FDGAnalyzer::isBranchOp(const Operation& opType) {
260     return (entryToCategory(opType.getID()) == c_BranchInsn);
261 }