Update copyright to LGPL on all files
[dyninst.git] / depGraphAPI / src / analyzePDG.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 "analyzePDG.h"
33
34 #include <set>
35 #include <map>
36
37 #include "dyn_detail/boost/shared_ptr.hpp"
38
39 #include "Graph.h"
40 #include "analyzeDDG.h"
41 #include "analyzeCDG.h"
42
43 #include "BPatch_function.h"
44 #include "Annotatable.h"
45
46 #include "instructionAPI/h/Register.h"
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 PDGs.
55 AnnotationClass<PDG::Ptr> PDGAnno(std::string("PDGAnno"));
56
57 // Constructor. Copies given function into internal structure.
58 PDGAnalyzer::PDGAnalyzer(Function *f) : func_(f) {}
59
60 // Creates a PDG for the given function.
61 PDG::Ptr PDGAnalyzer::analyze() {
62     // No function, no PDG!
63     if (func_ == NULL) return PDG::Ptr();
64
65     // Check the annotations. Did we compute the graph before?
66     PDG::Ptr *ret;
67     func_->getAnnotation(ret, PDGAnno);
68     if (ret) {
69         // yes, we did. Return it.
70         pdg = *ret;
71         return pdg;
72     }
73
74     // What we really want to hand into this is a CFG... for
75     // now, the set of blocks will suffice.
76     BlockSet blocks;
77     func_->getCFG()->getAllBasicBlocks(blocks);
78
79     // Create an empty graph
80     pdg = PDG::createGraph();
81
82     // merge with the DDG of this function.
83     mergeWithDDG();
84     // and with the CDG of this function.
85     mergeWithCDG();
86
87     // Store as an annotation and return
88     PDG::Ptr *ptr = new PDG::Ptr(pdg);
89     func_->addAnnotation(ptr, PDGAnno);
90
91     return pdg;
92 }
93
94 void PDGAnalyzer::mergeWithDDG() {
95     // find the entry node first
96     NodePtr virtEntryNode = pdg->virtualEntryNode();
97
98     // node map so that we can find the nodes created in the first pass during the second pass.
99     NodeMap nodeMap;
100
101     // get the DDG and its nodes.
102     Graph::Ptr ddg = DDG::analyze(func_);
103     NodeIterator ddgBegin, ddgEnd;
104     ddg->allNodes(ddgBegin, ddgEnd);
105
106     // Pass 1: create all DDG nodes in PDG
107     for (NodeIterator ddgIter = ddgBegin; ddgIter != ddgEnd; ddgIter++) {
108         Node::Ptr node = *ddgIter;
109         // skip the virtual node
110         VirtualNode::Ptr virtNode = dynamic_pointer_cast<VirtualNode>(node);
111         if (virtNode) {
112             continue;
113         }
114
115         // copy the node and add to the graph
116         NodePtr nodeCopy = node->copy();
117         nodeMap[node.get()] = nodeCopy;
118         pdg->addNode(nodeCopy);
119         pdg->insertPair(virtEntryNode, nodeCopy);
120     }
121
122     // Pass 2: create the edges!
123     for (NodeIterator ddgIter = ddgBegin; ddgIter != ddgEnd; ddgIter++) {
124         Node::Ptr node = *ddgIter;
125         // skip the virtual node
126         VirtualNode::Ptr virtNode = dynamic_pointer_cast<VirtualNode>(node);
127         if (virtNode) {
128             continue;
129         }
130         // get the copy of the ddg node
131         NodePtr sourceCopy = nodeMap[node.get()];
132         assert(sourceCopy);
133
134         // get list of targets of this node
135         NodeIterator outsBegin, outsEnd;
136         node->outs(outsBegin, outsEnd);
137         for (NodeIterator outsIter = outsBegin; outsIter != outsEnd; outsIter++) {
138             // get the copy of the ddg node
139             Node::Ptr target = *outsIter;
140             NodePtr targetCopy = nodeMap[target.get()];
141             assert(targetCopy);
142
143             // now add an edge between these two copy nodes
144             pdg->insertPair(sourceCopy, targetCopy);
145         }
146     }
147 }
148
149 /**
150  * Helper Method:
151  * Creates an edge from source to each target and puts them in PDG.
152  */
153 void PDGAnalyzer::createEdges(Graph::Ptr graph, Node::Ptr source,
154         NodeIterator targetsBegin, NodeIterator targetsEnd) {
155     for (NodeIterator targetIter = targetsBegin; targetIter != targetsEnd; targetIter++) {
156         Node::Ptr target = *targetIter;
157         graph->insertPair(source, target);
158     }
159 }
160
161 void PDGAnalyzer::mergeWithCDG() {
162     typedef vector<Instruction::Ptr>::iterator InsIter;
163
164     // get the CDG and all of its nodes.
165     Graph::Ptr cdg = CDG::analyze(func_);
166     NodeIterator cdgBegin, cdgEnd;
167     cdg->allNodes(cdgBegin, cdgEnd);
168     // Iterate over nodes in CDG (Basic Blocks).
169     // For each block, find the outgoing edges of this block. If there is an outgoing edge,
170     // the last instruction of this block *must* be a branch instruction with more than one
171     // targets. Create edges from this branch instruction to *all* instructions in all
172     // blocks that are in the outgoing blocks list.
173     for (NodeIterator cdgIter = cdgBegin; cdgIter != cdgEnd; cdgIter++) {
174         // skip the virtual node in CDG.
175         VirtualNode::Ptr virtNode = dynamic_pointer_cast<VirtualNode>(*cdgIter);
176         if (virtNode) {
177             continue;
178         }
179         // This node has to be a block node if not virtual
180         BlockNode::Ptr node = dynamic_pointer_cast<BlockNode>(*cdgIter);
181         assert(node);
182
183         // skip if there are no dependencies!
184         NodeIterator targetsBegin, targetsEnd;
185         node->outs(targetsBegin, targetsEnd);
186         if (targetsBegin == targetsEnd) {
187             continue;
188         }
189
190         Block* block = node->block();
191
192         // find last instruction in block
193         vector<Instruction::Ptr> insns;
194         block->getInstructions(insns);
195         Address lastInstAddr = (Address) (block->getEndAddress() - insns.back()->size());
196
197         // Find the node that is related to the EIP register.
198         NodeIterator sourcesBegin, sourcesEnd;
199         pdg->Graph::find(lastInstAddr, sourcesBegin, sourcesEnd);
200         NodePtr source;
201         assert(sourcesBegin != sourcesEnd);
202         for (NodeIterator sIter = sourcesBegin; sIter != sourcesEnd; sIter++) {
203             OperationNode::Ptr opNode = dynamic_pointer_cast<OperationNode>(*sIter);
204             if (opNode) {
205                 RegisterLoc::Ptr regLoc = dynamic_pointer_cast<RegisterLoc>(opNode->absloc());
206                 if (regLoc) {
207                     RegisterAST::Ptr regAst = regLoc->getReg();
208                     if (regAst->getID() == r_EIP) {
209                         source = *sIter;
210                     }
211                 }
212             }
213         }
214         // The source has to be set. If not, there is a problem!
215         assert(source);
216
217         // Now create an edge from the source to *all* instructions in all
218         // blocks that are in the outgoing blocks list.
219         for (NodeIterator targetIter = targetsBegin; targetIter != targetsEnd; targetIter++) {
220             BlockNode::Ptr targetNode = dynamic_pointer_cast<BlockNode>(*targetIter);
221             assert(targetNode);
222
223             Block* targetBlock = targetNode->block();
224             // for each instruction in block
225             vector<Instruction::Ptr> targetInsns;
226             targetBlock->getInstructions(targetInsns);
227             Address targetAddr = (Address) targetBlock->getStartAddress();
228             for (InsIter insIter = targetInsns.begin(); insIter != targetInsns.end(); insIter++) {
229                 // find all versions -> one set of targets
230                 NodeIterator targetsBegin, targetsEnd;
231                 pdg->Graph::find(targetAddr, targetsBegin, targetsEnd);
232
233                 // create edges from source to targets
234                 createEdges(pdg, source, targetsBegin, targetsEnd);
235
236                 // increment the address by the size of this instruction
237                 targetAddr += (*insIter)->size();
238             }
239         }
240     }
241 }