Update copyright to LGPL on all files
[dyninst.git] / depGraphAPI / src / analyzeXPDG.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 "analyzeXPDG.h"
33
34 #include <map>
35
36 #include "Graph.h"
37 #include "FDG.h"
38 #include "PDG.h"
39 #include "analyzeFDG.h"
40 #include "analyzePDG.h"
41 #include "DepGraphNode.h" // for BlockNode
42
43 #include "BPatch_function.h"
44 #include "Annotatable.h"
45
46 #include "dyn_detail/boost/shared_ptr.hpp"
47
48 using namespace std;
49 using namespace Dyninst;
50 using namespace Dyninst::InstructionAPI;
51 using namespace Dyninst::DepGraphAPI;
52 using namespace dyn_detail::boost;
53
54 // Annotation type for storing xPDGs.
55 AnnotationClass<xPDG::Ptr> xPDGAnno(std::string("xPDGAnno"));
56
57 // Constructor. Copies given function into internal structure.
58 xPDGAnalyzer::xPDGAnalyzer(Function *f) : func_(f) {}
59
60 // Creates and returns an xPDG for the given function.
61 xPDG::Ptr xPDGAnalyzer::analyze() {
62     // No function, no xPDG!
63     if (func_ == NULL) return xPDG::Ptr();
64
65     // Check the annotations. Did we compute the graph before?
66     xPDG::Ptr *ret;
67     func_->getAnnotation(ret, xPDGAnno);
68     if (ret) {
69         // yes, we did. Return it.
70         xpdg = *ret;
71         return xpdg;
72     }
73
74     // Create a graph
75     xpdg = xPDG::createGraph();
76
77     // merge with the PDG of this function.
78     mergeWithPDG();
79     // and with the FDG of this function.
80     mergeWithFDG();
81
82     // Store as an annotation and return
83     xPDG::Ptr *ptr = new xPDG::Ptr(xpdg);
84     func_->addAnnotation(ptr, xPDGAnno);
85
86     return xpdg;
87 }
88
89 void xPDGAnalyzer::mergeWithPDG() {
90     // find the entry node first
91     NodePtr virtEntryNode = xpdg->virtualEntryNode();
92
93     // node map so that we can find the nodes created in the first pass during the second pass.
94     NodeMap nodeMap;
95
96     // Create the PDG and get the nodes.
97     PDG::Ptr pdg = PDG::analyze(func_);
98     NodeIterator pdgBegin, pdgEnd;
99     pdg->allNodes(pdgBegin, pdgEnd);
100
101     // Pass 1: create all PDG nodes in xPDG
102     for (NodeIterator pdgIter = pdgBegin; pdgIter != pdgEnd; pdgIter++) {
103         Node::Ptr node = *pdgIter;
104         // skip the virtual node
105         VirtualNode::Ptr virtNode = dynamic_pointer_cast<VirtualNode>(node);
106         if (virtNode) {
107             continue;
108         }
109
110         // copy the node and add to the graph
111         NodePtr nodeCopy = node->copy();
112         nodeMap[node.get()] = nodeCopy;
113         xpdg->addNode(nodeCopy);
114         xpdg->insertPair(virtEntryNode, nodeCopy);
115     }
116
117     // Pass 2: create the edges!
118     pdg->allNodes(pdgBegin, pdgEnd);
119     for (NodeIterator pdgIter = pdgBegin; pdgIter != pdgEnd; pdgIter++) {
120         Node::Ptr node = *pdgIter;
121         // skip the virtual node
122         VirtualNode::Ptr virtNode = dynamic_pointer_cast<VirtualNode>(node);
123         if (virtNode) {
124             continue;
125         }
126         // get the copy of the pdg node
127         NodePtr sourceCopy = nodeMap[node.get()];
128         assert(sourceCopy);
129
130         // get list of targets of this node
131         NodeIterator outsBegin, outsEnd;
132         node->outs(outsBegin, outsEnd);
133         for (NodeIterator outsIter = outsBegin; outsIter != outsEnd; outsIter++) {
134             // get the copy of the pdg node
135             Node::Ptr target = *outsIter;
136             NodePtr targetCopy = nodeMap[target.get()];
137             assert(target.get());
138             assert(targetCopy);
139
140             // now add an edge between these two copy nodes
141             xpdg->insertPair(sourceCopy, targetCopy);
142         }
143     }
144 }
145
146 // Merge current xPDG with the FDG of this function.
147 void xPDGAnalyzer::mergeWithFDG() {
148     // Create FDG and get the nodes. These nodes are basic-block-level nodes.
149     FDG::Ptr fdg = FDG::analyze(func_);
150     NodeIterator fdgBegin, fdgEnd;
151     fdg->allNodes(fdgBegin, fdgEnd);
152     // Iterate over nodes in FDG (Basic Blocks).
153     // For each block, find the outgoing edges of this block. If there is an outgoing edge,
154     // the last instruction of this block *must* be a jump/branch/return instruction (writes
155     // to PC). Create edges from this branch instruction to:
156     // 1) *all* instructions in this block.
157     // 2a) the jump/branch instruction (last instruction) of blocks that are in the outgoing
158     //     blocks list of the source block.
159     // 2b) to *all* instructions in a block that is in the outgoing blocks list of the source
160     //     block, provided that the last instruction is not   jump/return instruction.
161     for (NodeIterator fdgIter = fdgBegin; fdgIter != fdgEnd; fdgIter++) {
162         // skip the virtual node
163         VirtualNode::Ptr virtNode = dynamic_pointer_cast<VirtualNode>(*fdgIter);
164         if (virtNode) {
165             continue;
166         }
167         // This node has to be a block node if not virtual
168         BlockNode::Ptr node = dynamic_pointer_cast<BlockNode>(*fdgIter);
169         assert(node);
170
171         // Get the blocks that are in the out list.
172         NodeIterator depBegin, depEnd;
173         node->outs(depBegin, depEnd);
174         // if no dependencies, then skip this node!
175         if (depBegin == depEnd) {
176             continue;
177         }
178
179         Block* block = node->block();
180
181         // Find the last instruction.
182         vector<Instruction::Ptr> insns;
183         block->getInstructions(insns);
184         Instruction::Ptr lastInst = insns.back();
185         Address lastInstAddr = (Address) (block->getEndAddress() - lastInst->size());
186         const Operation& opType = lastInst->getOperation();
187         NodePtr source;
188         // Process the node if the last instruction is a jump/branch/return instruction.
189         if (FDGAnalyzer::isReturnOp(opType) || FDGAnalyzer::isBranchOp(opType)) {
190             // Find the node that is related to the EIP register.
191             NodeIterator sBegin, sEnd;
192             xpdg->Graph::find(lastInstAddr, sBegin, sEnd);
193             for (NodeIterator sIter = sBegin; sIter != sEnd; sIter++) {
194                 OperationNode::Ptr opNode = dynamic_pointer_cast<OperationNode>(*sIter);
195                 if (opNode) {
196                     RegisterLoc::Ptr regLoc = dynamic_pointer_cast<RegisterLoc>(opNode->absloc());
197                     if (regLoc) {
198                         RegisterAST::Ptr regAst = regLoc->getReg();
199                         if (regAst->getID() == r_EIP) {
200                             source = *sIter;
201                         }
202                     }
203                 }
204             }
205             // The source has to be set. If not, there is a problem!
206             assert(source);
207
208             // add intra-block dependencies first!
209             // add an edge from source to all nodes in this block.
210             Address targetAddr = (Address) block->getStartAddress();
211             for (unsigned i = 0; i < (insns.size() - 1); i++) {
212                 NodeIterator tBegin, tEnd;
213                 xpdg->Graph::find(targetAddr, tBegin, tEnd);
214                 PDGAnalyzer::createEdges(xpdg, source, tBegin, tEnd);
215                 targetAddr += insns[i]->size();
216             }
217
218             // now add inter-block dependencies!
219             // for each target block:
220             for (NodeIterator nodeIter = depBegin; nodeIter != depEnd; nodeIter++) {
221                 BlockNode::Ptr targetNode = dynamic_pointer_cast<BlockNode>(*nodeIter);
222                 assert(targetNode);
223
224                 Block* targetBlock = targetNode->block();
225                 vector<Instruction::Ptr> targetIns;
226                 targetBlock->getInstructions(targetIns);
227
228                 // check if the last instruction is jump/branch/return (It can't be return, can it?)
229                 Instruction::Ptr lastTargetInst = targetIns.back();
230                 const Operation& targetOpType = lastTargetInst->getOperation();
231                 if (FDGAnalyzer::isReturnOp(targetOpType) || FDGAnalyzer::isBranchOp(targetOpType)) {
232                     // add an edge only to the last instruction of this block.
233                     Address lastTargetAddr =
234                         (Address) (targetBlock->getEndAddress() - lastTargetInst->size());
235                     NodeIterator tBegin, tEnd;
236                     xpdg->Graph::find(lastTargetAddr, tBegin, tEnd);
237                     PDGAnalyzer::createEdges(xpdg, source, tBegin, tEnd);
238                 }
239                 // otherwise
240                 else {
241                     // add an edge to all instructions in this block.
242                     Address targetAddr = (Address) targetBlock->getStartAddress();
243                     for (unsigned j = 0; j < targetIns.size(); j++) {
244                         NodeIterator tBegin, tEnd;
245                         xpdg->Graph::find(targetAddr, tBegin, tEnd);
246                         PDGAnalyzer::createEdges(xpdg, source, tBegin, tEnd);
247                         targetAddr += targetIns[j]->size();
248                     }
249                 }
250             }
251         }
252         else {
253             // there can be out edges only if the last instruction is a return, jump or branch.
254             NodeIterator depBegin, depEnd;
255             node->outs(depBegin, depEnd);
256             assert(depBegin == depEnd);
257         }
258     }
259 }