Move Graph, Node, Edge objects to common/dynutil; move all others to new 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     if (isReturnOp(opType) || isJumpOp(opType) || isBranchOp(opType)) {
132       markedBlocks.insert(block);
133       lastInstInBlock[ block->getBlockNumber() ] =
134           new InstWithAddr(lastInst, (Address) (block->getEndAddress() - lastInst.size()));
135     }
136     else {
137       lastInstInBlock[ block->getBlockNumber() ] = NULL;
138     }
139     
140     Address address = (Address) block->getStartAddress();
141     for (unsigned i = 0; i < instructions.size(); i++) {
142       addrToBlock[address] = block;
143       address += instructions[i].size();
144     }
145   }
146 }
147
148 void FDGAnalyzer::findDependencies(BlockSet &blocks) {
149   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
150     Block* block = *blockIter;
151     BlockSet blocksWithJumps;
152     BlockSet visited;
153     findBlocksOnWay(blocksWithJumps, visited, block);
154     blockToJumps[block] = blocksWithJumps;
155   }
156 }
157
158 void FDGAnalyzer::findBlocksOnWay(BlockSet& needThese, 
159                                   BlockSet& visited, 
160                                   Block* givenBlock) {
161   if (markedBlocks.find(givenBlock) != markedBlocks.end()) {
162     needThese.insert(givenBlock);
163   }
164   findBlocksRecursive(needThese, visited, givenBlock);
165 }
166
167 void FDGAnalyzer::findBlocksRecursive(BlockSet& needThese, 
168                                       BlockSet& visited,
169                                       Block* givenBlock) {
170   if ((visited.find(givenBlock) != visited.end())) {
171     return;
172   }
173   visited.insert(givenBlock);
174   
175   vector<BPatch_edge*> outEdges;
176   givenBlock->getOutgoingEdges(outEdges);
177   for (unsigned i = 0; i < outEdges.size(); i++) {
178     Block* target = outEdges[i]->getTarget();
179     // if the target terminates anything other than a call, it is added to the list, and we don't
180     // search on this branch anymore. If not, keep looking!
181     if (markedBlocks.find(target) != markedBlocks.end()) {
182       needThese.insert(target);
183     }
184     else {
185       findBlocksRecursive(needThese, visited, target);
186     }
187   }
188 }
189
190 void FDGAnalyzer::createDepToOtherBlocks(NodeSet& nodes, 
191                                          NodePtr source) {
192   if (nodes.find(source) != nodes.end()) {
193     return;
194   }
195   nodes.insert(source);
196   Block* curBlock = addrToBlock[ source->addr() ];
197   assert(curBlock);
198   BlockSet& targets = blockToJumps[curBlock];
199   for (BlockSet::iterator blIter = targets.begin(); blIter != targets.end(); blIter++) {
200     InstWithAddr* targetInst = lastInstInBlock[ (*blIter)->getBlockNumber() ];
201     assert (targetInst);
202     if (targetInst->second == source->addr()) {
203       continue;
204     }
205     NodePtr target = PhysicalNode::createNode(targetInst->second);
206     fdg->insertPair(source, target);
207     
208     createDepToOtherBlocks(nodes, target);
209   }
210 }
211
212 bool FDGAnalyzer::createDepWithinBlock(NodeSet& nodes, 
213                                        NodePtr source) {
214   if (nodes.find(source) != nodes.end()) {
215     return true;
216   }
217   Block* curBlock = addrToBlock[ source->addr() ];
218   assert(curBlock);
219   InstWithAddr* inst = lastInstInBlock[ curBlock->getBlockNumber() ];
220   if (inst && inst->second != source->addr()) {
221     nodes.insert(source);
222     NodePtr target = PhysicalNode::createNode(inst->second);
223     fdg->insertPair(source, target);
224     
225     // since I am doing it for every instruction, I don't need to go any further now.    
226     return true;
227   }
228   return false;
229 }
230
231 void FDGAnalyzer::createNodes(BlockSet &blocks) {
232   NodePtr virtNode = VirtualNode::createNode();
233   NodeSet processedNodes;
234   for (BlockSet::iterator blockIter = blocks.begin(); blockIter != blocks.end(); blockIter++) {
235     Block* block = *blockIter;
236     vector<Instruction> instructions;
237     block->getInstructions(instructions);
238     
239     Address address = (Address) block->getStartAddress();
240     for (unsigned i = 0; i < instructions.size(); i++) {
241       NodePtr node = PhysicalNode::createNode(address);
242       fdg->insertPair(virtNode, node);
243       address += instructions[i].size();
244       
245       bool success = createDepWithinBlock(processedNodes, node);
246       if (!success) {
247         createDepToOtherBlocks(processedNodes, node);
248       }
249     }
250   }
251 }
252 /**************************************************************************************************/
253 /****************************   static functions   ************************************************/
254 bool FDGAnalyzer::isReturnOp(const Operation& opType) {
255   entryID opId = opType.getID();
256   if ((opId == e_iret) ||
257       (opId == e_ret_far) ||
258       (opId == e_ret_near) ||
259       (opId == e_sysret) ||
260       (opId == e_sysexit)) {
261     return true;
262   }
263   return false;
264 }
265
266 bool FDGAnalyzer::isJumpOp(const Operation& opType) {
267   return (e_jmp == opType.getID());
268 }
269
270 bool FDGAnalyzer::isBranchOp(const Operation& opType) {
271   return ((e_jb <= opType.getID()) && (e_jz >= opType.getID()) && (e_jmp != opType.getID()));
272 }