Update copyright to LGPL on all files
[dyninst.git] / common / src / Node.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
33 // Node class implementation
34
35 #include "Graph.h"
36 #include "Edge.h"
37 #include "Node.h"
38 #include <assert.h>
39
40 #include "common/h/NodeIterator.h"
41
42 // Nodes are quite simple; they have an Insn, an Absloc, and a set of Edges.
43
44 using namespace Dyninst;
45
46 const Address Node::INVALID_ADDR = (Address) -1;
47
48 void Node::ins(NodeIterator &begin, NodeIterator &end) {
49     // Ins and outs are currently stored as sets of edges.
50     // We need an iterator that translates them...
51     begin = NodeIterator(new NodeFromEdgeSet(ins_.begin(), NodeFromEdgeSet::source));
52     end = NodeIterator(new NodeFromEdgeSet(ins_.end(), NodeFromEdgeSet::source));
53 }
54
55 void Node::outs(NodeIterator &begin, NodeIterator &end) {
56     begin = NodeIterator(new NodeFromEdgeSet(outs_.begin(), NodeFromEdgeSet::target));
57     end = NodeIterator(new NodeFromEdgeSet(outs_.end(), NodeFromEdgeSet::target));
58 }
59
60 void Node::ins(EdgeIterator &begin, EdgeIterator &end) {
61     // Iteration over a pre-existing set is easy...
62     begin = EdgeIterator(new EdgeIteratorSet(ins_.begin()));
63     end = EdgeIterator(new EdgeIteratorSet(ins_.end()));
64 }
65
66 void Node::outs(EdgeIterator &begin, EdgeIterator &end) {
67     // Iteration over a pre-existing set is easy...
68     begin = EdgeIterator(new EdgeIteratorSet(outs_.begin()));
69     end = EdgeIterator(new EdgeIteratorSet(outs_.end()));
70 }
71
72 bool Node::hasInEdges() {
73     return !ins_.empty();
74 }
75
76 bool Node::hasOutEdges() {
77     return !outs_.empty();
78 }
79
80 void Node::forwardClosure(NodeIterator &begin, NodeIterator &end) {
81     end = NodeIterator(new NodeSearchIterator());
82
83     if (!hasOutEdges()) {
84         begin = end;
85     }
86     else {
87         NodeIterator outBegin, outEnd;
88         outs(outBegin, outEnd);
89         begin = NodeIterator(new NodeSearchIterator(outBegin, outEnd, NodeSearchIterator::out, NodeSearchIterator::breadth));
90     }
91 }
92
93 void Node::backwardClosure(NodeIterator &begin, NodeIterator &end) {
94     end = NodeIterator(new NodeSearchIterator());
95
96     if (!hasInEdges()) {
97         begin = end;
98     }
99     else {
100         NodeIterator inBegin, inEnd;
101         ins(inBegin, inEnd);
102         begin = NodeIterator(new NodeSearchIterator(inBegin, inEnd, NodeSearchIterator::in, NodeSearchIterator::breadth));
103     }
104 }
105
106
107 Node::Ptr PhysicalNode::createNode(Address addr) {
108     return Node::Ptr(new PhysicalNode(addr));
109 }
110
111 Node::Ptr PhysicalNode::copy() {
112     return Node::Ptr(new PhysicalNode(addr()));
113 }
114
115 std::string PhysicalNode::format() const {
116     char buf[256];
117     sprintf(buf, "N_0x%lx", addr());
118     return std::string(buf);
119 }
120
121 std::string VirtualNode::defaultName("N_VIRTUAL");
122
123 Node::Ptr VirtualNode::createNode() {
124     return Node::Ptr(new VirtualNode());
125 }
126
127 Node::Ptr VirtualNode::createNode(std::string name) {
128     return Node::Ptr(new VirtualNode(name));
129 }
130
131 Node::Ptr VirtualNode::copy() {
132     return Node::Ptr(new VirtualNode(name_));
133 }
134
135 std::string VirtualNode::format() const {
136     return name_;
137 }
138
139 // Prefix...
140 NodeIterator &NodeIterator::operator++() {
141     if (!iter_) return *this;
142     
143     iter_->inc();
144     return *this;
145 }
146
147 // Postfix...
148 NodeIterator NodeIterator::operator++(int) {
149     NodeIterator ret = *this;
150     ++(*this);
151     return ret;    
152 }
153
154 // Prefix...
155 NodeIterator &NodeIterator::operator--() {
156     if (!iter_) return *this;
157     
158     iter_->dec();
159     return *this;
160 }
161
162 // Postfix...
163 NodeIterator NodeIterator::operator--(int) {
164     NodeIterator ret = *this;
165     --(*this);
166     return ret;    
167 }
168
169
170 Node::Ptr NodeIterator::operator*() const {
171     if (!iter_) return Node::Ptr();
172
173     return iter_->get();
174 }
175
176 bool NodeIterator::operator!=(const NodeIterator &rhs) const {
177     if (!iter_) {
178         return (rhs.iter_ != NULL);
179     }
180     return !iter_->equals(rhs.iter_);
181 }
182
183 bool NodeIterator::operator==(const NodeIterator &rhs) const {
184     if (!iter_) {
185         return (rhs.iter_ == NULL);
186     }
187     return iter_->equals(rhs.iter_);
188 }
189
190 NodeIterator &NodeIterator::operator=(const NodeIterator &rhs) {
191     if (iter_) delete iter_;
192     iter_ = rhs.copy();
193     return *this;
194 }
195
196 NodeIterator::NodeIterator() : iter_(NULL) {
197 }
198
199 NodeIterator::NodeIterator(NodeIteratorImpl *iter) :
200     iter_(iter) {
201 }
202
203 NodeIterator::NodeIterator(const NodeIterator &rhs) :
204     iter_(rhs.copy()) {
205 }
206
207 NodeIterator::~NodeIterator() { 
208     if (iter_) delete iter_;
209 }
210
211 NodeIteratorImpl *NodeIterator::copy() const {
212     if (iter_ == NULL) return NULL;
213     return iter_->copy();
214 }
215
216 Graph::Ptr Node::forwardSubgraph() {
217     // We want to copy this node and every node reachable from
218     // it along a forward direction. This node will become the
219     // entry for a new subgraph. 
220
221     // TODO: this is a generic graph by definition, as nodes
222     // have no idea what type of graph they belong to. Is that
223     // the right thing? 
224
225     Graph::Ptr ret = Graph::createGraph();
226     
227     Node::Ptr newEntry = copy();
228     ret->insertEntryNode(newEntry);
229     
230     std::set<Node::Ptr> visited;
231     std::queue<std::pair<Node::Ptr, Node::Ptr> > worklist;
232
233     // We don't have a shared pointer to the current node. 
234     // However, we do have an edge, which has a weak pointer. 
235
236     if (outs_.empty()) return ret;
237     Node::Ptr thisPtr = (*outs_.begin())->source();
238
239     worklist.push(std::make_pair(thisPtr, newEntry));
240
241     while (!worklist.empty()) {
242         // First is the original node, second the copy
243         std::pair<Node::Ptr, Node::Ptr> src = worklist.front(); 
244         worklist.pop();
245
246         if (visited.find(src.first) != visited.end()) continue;
247         visited.insert(src.first);
248
249         NodeIterator b, e;
250         src.first->outs(b, e);
251
252         if (b == e) {
253             ret->insertExitNode(src.second);
254         }
255
256         for (; b != e; ++b) {
257             std::pair<Node::Ptr, Node::Ptr> targ = std::make_pair(*b, (*b)->copy());
258             ret->insertPair(src.second, targ.second);
259             worklist.push(targ);
260         } 
261     }
262     return ret;
263 }
264
265 Graph::Ptr Node::backwardSubgraph() {
266     // We want to copy this node and every node reachable from
267     // it along a forward direction. This node will become the
268     // entry for a new subgraph. 
269
270     // TODO: this is a generic graph by definition, as nodes
271     // have no idea what type of graph they belong to. Is that
272     // the right thing? 
273
274     Graph::Ptr ret = Graph::createGraph();
275     
276     Node::Ptr newExit = copy();
277     ret->insertExitNode(newExit);
278     
279     std::set<Node::Ptr> visited;
280     std::queue<std::pair<Node::Ptr, Node::Ptr> > worklist;
281     
282     // See comment in nearly-identical code above...
283     if (ins_.empty()) return ret;
284     Node::Ptr thisPtr = (*ins_.begin())->target();
285
286     worklist.push(std::make_pair(thisPtr, newExit));
287
288     while (!worklist.empty()) {
289         // First is the original node, second the copy
290         std::pair<Node::Ptr, Node::Ptr> targ = worklist.front(); 
291         worklist.pop();
292
293         if (visited.find(targ.first) != visited.end()) continue;
294         visited.insert(targ.first);
295
296         NodeIterator b, e;
297
298         targ.first->ins(b, e);
299
300         if (b == e) {
301             ret->insertEntryNode(targ.second);
302         }
303
304         for (; b != e; ++b) {
305             std::pair<Node::Ptr, Node::Ptr> src = std::make_pair(*b, (*b)->copy());
306             ret->insertPair(src.second, targ.second);
307             worklist.push(src);
308         } 
309     }
310     return ret;
311 }