[Scummvm-cvs-logs] SF.net SVN: scummvm:[42388] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Sat Jul 11 19:32:58 CEST 2009
Revision: 42388
http://scummvm.svn.sourceforge.net/scummvm/?rev=42388&view=rev
Author: kjdf
Date: 2009-07-11 17:32:58 +0000 (Sat, 11 Jul 2009)
Log Message:
-----------
decompiler: cleaned up graph::yank
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
tools/branches/gsoc2009-decompiler/decompiler/node.cpp
tools/branches/gsoc2009-decompiler/decompiler/node.h
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-11 17:25:49 UTC (rev 42387)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-11 17:32:58 UTC (rev 42388)
@@ -37,9 +37,9 @@
Node *dominatorIntersect(Node *u, Node *v) {
while (u != v) {
- while (u->_number < v->_number)
+ while (u->_postOrder < v->_postOrder)
u = u->_dominator;
- while (v->_number < u->_number)
+ while (v->_postOrder < u->_postOrder)
v = v->_dominator;
}
return u;
@@ -64,9 +64,9 @@
ret << "fontname=" << '"' << fontname << "\",";
if (fontsize != 0)
ret << "fontsize=" << fontsize << ",";
- ret << "shape=box,label=\"<number=" << u->_number;
- if (u->_dominator)
- ret << ", dom=" << u->_dominator->_number;
+ ret << "shape=box,label=\"<number=" << u->_postOrder;
+ // if (u->_dominator)
+ // ret << ", dom=" << u->_dominator->_postOrder;
ret << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << endl;
return ret.str();
}
@@ -100,7 +100,7 @@
bool postOrderCompare(Node *a, Node *b) {
- return a->_number < b->_number;
+ return a->_postOrder < b->_postOrder;
}
list<Node*> inPostOrder(list<Node*> &nodes) {
@@ -111,16 +111,30 @@
int orderVisit(Node *u, int number) {
- u->_number = -1;
+ u->_postOrder = -1;
foreach (Node *v, u->_out)
- if (!v->_number)
+ if (!v->_postOrder)
number = orderVisit(v, number);
- u->_number = ++number;
+ u->_postOrder = ++number;
return number;
}
+void replaceCrossEdgesWithProxies(ControlFlowGraph *gu, Node *u, ControlFlowGraph *gv, Node *v) {
+ foreach (Node *&node, u->_out)
+ if (node == v) {
+ node = new ProxyNode(v);
+ gu->_nodes.push_back(node);
+ }
+ size_t n = count(v->_in.begin(), v->_in.end(), u);
+ v->_in.remove(u);
+ while (n--) {
+ v->_in.push_back(new ProxyNode(u));
+ gv->_nodes.push_back(v->_in.back());
+ }
+}
+
ControlFlowGraph::ControlFlowGraph() : _entry() {
}
@@ -271,7 +285,7 @@
void ControlFlowGraph::orderNodes() {
- if (_entry && !_entry->_number)
+ if (_entry && !_entry->_postOrder)
orderVisit(_entry, 0);
}
@@ -294,14 +308,14 @@
void ControlFlowGraph::removeUnreachableNodes() {
foreach (Node *u, _nodes)
- if (!u->_number) {
+ if (!u->_postOrder) {
foreach (Node *v, u->_out)
v->_in.remove(u);
foreach (Node *v, u->_in)
v->_out.remove(u);
}
for (list<Node*>::iterator it = _nodes.begin(); it != _nodes.end(); )
- if ((*it)->_number)
+ if ((*it)->_postOrder)
it++;
else {
// delete *it;
@@ -331,14 +345,14 @@
list< list<Node*> > ret;
foreach (Node *u, _nodes) {
u->_component = 0;
- u->_number = 0;
+ u->_postOrder = 0;
}
int n = 0;
- if (_entry && !_entry->_number)
+ if (_entry && !_entry->_postOrder)
n = orderVisit(_entry, n);
foreach (Node *u, _nodes)
- if (!u->_number)
+ if (!u->_postOrder)
n = orderVisit(u, n);
list<Node*> nodes = inPostOrder(_nodes);
@@ -353,32 +367,18 @@
}
-// TODO force same proxy nodes for all nodes?
ControlFlowGraph *ControlFlowGraph::yank(set<Node*> &nodes) {
ControlFlowGraph *subgraph = new ControlFlowGraph;
- _subgraphs.push_back(subgraph);
- list<Node*> newNodes;
- foreach (Node *u, _nodes)
- foreach (Node *v, _nodes)
- if (contains(nodes, u) != contains(nodes, v)) { // replace all cross-graph edges with proxies
- size_t n = count(v->_in.begin(), v->_in.end(), u);
- v->_in.remove(u);
- while (n--)
- v->_in.push_back(new ProxyNode(u));
- foreach (Node *&node, u->_out)
- if (node == v) {
- node = new ProxyNode(node);
- if (contains(nodes, u))
- subgraph->_nodes.push_back(node);
- else
- newNodes.push_back(node);
- }
- }
- copy(newNodes.begin(), newNodes.end(), back_inserter(_nodes));
foreach (Node *u, nodes) {
subgraph->_nodes.push_back(u);
_nodes.remove(u);
}
+ foreach (Node *u, nodes)
+ foreach (Node *v, list<Node*>(_nodes)) {
+ replaceCrossEdgesWithProxies(subgraph, u, this, v);
+ replaceCrossEdgesWithProxies(this, v, subgraph, u);
+ }
+ _subgraphs.push_back(subgraph);
return subgraph;
}
@@ -388,7 +388,7 @@
return;
foreach (Node *u, _nodes) {
u->_dominator = 0;
- u->_number = 0;
+ u->_postOrder = 0;
}
orderNodes();
removeUnreachableNodes();
@@ -400,7 +400,7 @@
Node *latch = 0;
foreach (Node *u, component) // find the deepest latching node
foreach (Node *v, u->_out)
- if (v == entry && (!latch || latch->_number > u->_number))
+ if (v == entry && (!latch || latch->_postOrder > u->_postOrder))
latch = u;
if (0) {
} else if (latch && latch != entry && latch->edgeOutsideComponent()) {
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-11 17:25:49 UTC (rev 42387)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-11 17:32:58 UTC (rev 42388)
@@ -13,7 +13,7 @@
#endif
-Node::Node() : _interval(), _number(), _dominator(), _component() {
+Node::Node() : _interval(), _postOrder(), _dominator(), _component() {
}
@@ -63,7 +63,7 @@
_component = node->_component;
_dominator = node->_dominator;
_interval = node->_interval;
- _number = node->_number;
+ _postOrder = node->_postOrder;
}
@@ -89,7 +89,7 @@
_component = entry->_component;
_dominator = entry->_dominator;
_interval = entry->_interval;
- _number = entry->_number;
+ _postOrder = entry->_postOrder;
set<Node*> body;
foreach (Node *u, graph->_nodes)
@@ -116,7 +116,7 @@
_body->structureLoops(_body->stronglyConnectedComponents());
foreach (Node *u, _body->_nodes)
- u->_number = 0;
+ u->_postOrder = 0;
_body->orderNodes();
_body->removeUnreachableNodes();
}
@@ -152,7 +152,7 @@
_component = entry->_component;
_dominator = entry->_dominator;
_interval = entry->_interval;
- _number = entry->_number;
+ _postOrder = entry->_postOrder;
set<Node*> body;
foreach (Node *u, graph->_nodes)
@@ -182,7 +182,7 @@
_body->structureLoops(_body->stronglyConnectedComponents());
foreach (Node *u, _body->_nodes)
- u->_number = 0;
+ u->_postOrder = 0;
_body->orderNodes();
_body->removeUnreachableNodes();
}
@@ -217,12 +217,12 @@
_component = entry->_component;
_dominator = entry->_dominator;
_interval = entry->_interval;
- _number = entry->_number;
+ _postOrder = entry->_postOrder;
Node *exit = 0;
foreach (Node *u, graph->_nodes)
if (u->_component == entry->_component) {
foreach (Node *v, u->_out)
- if (v->_component != entry->_component && (!exit || exit->_number < v->_number))
+ if (v->_component != entry->_component && (!exit || exit->_postOrder < v->_postOrder))
exit = v;
}
@@ -258,7 +258,7 @@
_body->setEntry(entry->address());
_body->structureLoops(components);
foreach (Node *u, _body->_nodes)
- u->_number = 0;
+ u->_postOrder = 0;
_body->orderNodes();
_body->removeUnreachableNodes();
}
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-11 17:25:49 UTC (rev 42387)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-11 17:32:58 UTC (rev 42388)
@@ -14,9 +14,9 @@
struct Node : boost::noncopyable {
Node *_component;
- Node *_dominator; // immediate dominator
- Node *_interval; // header node of the interval this node belongs to
- int _number; // number in post-order
+ Node *_dominator;
+ Node *_interval;
+ int _postOrder;
std::list<Node*> _in;
std::list<Node*> _out;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
More information about the Scummvm-git-logs
mailing list