[Scummvm-cvs-logs] SF.net SVN: scummvm:[42389] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Sat Jul 11 19:33:18 CEST 2009
Revision: 42389
http://scummvm.svn.sourceforge.net/scummvm/?rev=42389&view=rev
Author: kjdf
Date: 2009-07-11 17:33:18 +0000 (Sat, 11 Jul 2009)
Log Message:
-----------
decompiler: cleaned up loop structuring
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.h
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:32:58 UTC (rev 42388)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-11 17:33:18 UTC (rev 42389)
@@ -65,12 +65,13 @@
if (fontsize != 0)
ret << "fontsize=" << fontsize << ",";
ret << "shape=box,label=\"<number=" << u->_postOrder;
- // if (u->_dominator)
- // ret << ", dom=" << u->_dominator->_postOrder;
+ if (u->_dominator)
+ ret << ", dom=" << u->_dominator->_postOrder;
ret << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << endl;
return ret.str();
}
+
string graphvizPrintSubgraph(ControlFlowGraph *graph, const string &fontname, int fontsize) {
ostringstream ret;
ret << "subgraph \"cluster_" << graph << "\" {" << endl;
@@ -79,10 +80,10 @@
ret << graphvizPrintBox(u, fontname, fontsize);
foreach (Node *v, u->_out)
ret << '"' << u << "\" -> \"" << v << "\";" << endl;
- // foreach (Node *v, u->_in) {
- // ret << graphvizPrintBox(v, fontname, fontsize);
- // ret << '"' << v << "\" -> \"" << u << "\"[style=dashed];" << endl;
- // }
+ foreach (Node *v, u->_in) {
+ ret << graphvizPrintBox(v, fontname, fontsize);
+ ret << '"' << v << "\" -> \"" << u << "\"[style=dashed];" << endl;
+ }
}
ret << "}" << endl;
@@ -124,14 +125,10 @@
foreach (Node *&node, u->_out)
if (node == v) {
node = new ProxyNode(v);
+ node->_in.push_back(u);
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());
- }
}
@@ -203,6 +200,7 @@
}
+// TODO hidden nodes
// entry node is an interval header
// a node belongs to an interval, if all its immediate predecessors belong the given interval
// otherwise it is an interval header
@@ -258,6 +256,19 @@
}
+void ControlFlowGraph::deleteNode(Node *node) {
+ forgetNode(node);
+ delete node;
+}
+
+
+void ControlFlowGraph::forgetNode(Node *node) {
+ _nodes.remove(node);
+ foreach (Node *u, node->_out)
+ u->_in.remove(node);
+}
+
+
string ControlFlowGraph::graphvizToString(const string &fontname, int fontsize) {
stringstream ret;
ret << "digraph G {" << endl;
@@ -314,7 +325,7 @@
foreach (Node *v, u->_in)
v->_out.remove(u);
}
- for (list<Node*>::iterator it = _nodes.begin(); it != _nodes.end(); )
+ for (std::list<Node*>::iterator it = _nodes.begin(); it != _nodes.end(); )
if ((*it)->_postOrder)
it++;
else {
@@ -334,6 +345,20 @@
}
+void ControlFlowGraph::replaceEdges(Node *from, uint32 oldTo, Node *newTo) {
+ size_t n = 0;
+ foreach (Node *node, from->_out)
+ if (node->address() == oldTo) {
+ n += count(node->_in.begin(), node->_in.end(), from);
+ node->_in.remove(from);
+ }
+ fill_n(back_inserter(newTo->_in), n, from);
+ foreach (Node *&node, from->_out)
+ if (node->address() == oldTo)
+ node = newTo;
+}
+
+
void ControlFlowGraph::setEntry(address_t entry) {
foreach (Node *node, _nodes)
if (node->address() == entry)
@@ -347,7 +372,6 @@
u->_component = 0;
u->_postOrder = 0;
}
-
int n = 0;
if (_entry && !_entry->_postOrder)
n = orderVisit(_entry, n);
@@ -391,7 +415,6 @@
u->_postOrder = 0;
}
orderNodes();
- removeUnreachableNodes();
assignDominators();
foreach (list<Node*> component, components) {
list<Node*> entries = componentEntryPoints(component);
@@ -402,12 +425,11 @@
foreach (Node *v, u->_out)
if (v == entry && (!latch || latch->_postOrder > u->_postOrder))
latch = u;
- if (0) {
- } else if (latch && latch != entry && latch->edgeOutsideComponent()) {
+ if (latch && latch != entry &&latch->edgeOutsideComponent()) {
_nodes.push_back(new DoWhileLoop(this, entry, latch));
cerr << "done do-while loop at " << phex(entry->address()) << endl;
- } else if (latch && entry->edgeOutsideComponent()) { // while loop
- _nodes.push_back(new WhileLoop(this, entry));
+ } else if (latch && entry->edgeOutsideComponent()) {
+ _nodes.push_back(new WhileLoop(this, entry));
cerr << "done while loop at " << phex(entry->address()) << endl;
} else if (latch) {
_nodes.push_back(new EndlessLoop(this, entry));
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-11 17:32:58 UTC (rev 42388)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-11 17:33:18 UTC (rev 42389)
@@ -26,11 +26,14 @@
void addBasicBlocksFromScript(std::list<Instruction*>::iterator scriptBegin, std::list<Instruction*>::iterator scriptEnd);
void addEdge(Node *from, Node *to);
void assignDominators(); // after order
+ void deleteNode(Node *node);
+ void forgetNode(Node *node);
std::string graphvizToString(const std::string &fontname="", int fontsize=0);
void orderNodes();
void removeJumpsToJumps();
void removeUnreachableNodes(); // after order
void replaceEdges(Node *from, Node *oldTo, Node *newTo);
+ void replaceEdges(Node *from, uint32 oldTo, Node *newTo);
void setEntry(address_t entry);
std::list< std::list<Node*> > stronglyConnectedComponents();
ControlFlowGraph *yank(std::set<Node*> &body);
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-11 17:32:58 UTC (rev 42388)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-11 17:33:18 UTC (rev 42389)
@@ -13,7 +13,7 @@
#endif
-Node::Node() : _interval(), _postOrder(), _dominator(), _component() {
+Node::Node() : _component(), _dominator(), _interval(), _postOrder() {
}
@@ -23,7 +23,7 @@
bool Node::dominates(Node *u) {
for (; u; u = u->_dominator)
- if (u->_dominator == this)
+ if (u == this)
return true;
return false;
}
@@ -37,6 +37,14 @@
}
+void Node::mimic(Node *node) {
+ _component = node->_component;
+ _dominator = node->_dominator;
+ _interval = node->_interval;
+ _postOrder = node->_postOrder;
+}
+
+
BasicBlock::BasicBlock(list<Instruction*>::iterator first, list<Instruction*>::iterator last) : Node() {
copy(first, last, back_inserter(_instructions));
}
@@ -60,10 +68,7 @@
ProxyNode::ProxyNode(Node *node) : Node(), _node(node) {
- _component = node->_component;
- _dominator = node->_dominator;
- _interval = node->_interval;
- _postOrder = node->_postOrder;
+ mimic(node);
}
@@ -84,41 +89,34 @@
WhileLoop::WhileLoop(ControlFlowGraph *graph, Node *entry) : Loop(), _condition(entry) {
+ mimic(entry);
Node *exit = entry->edgeOutsideComponent();
_negate = exit != entry->_out.front();
- _component = entry->_component;
- _dominator = entry->_dominator;
- _interval = entry->_interval;
- _postOrder = entry->_postOrder;
+ // yank out loop body
set<Node*> body;
foreach (Node *u, graph->_nodes)
- if (entry->dominates(u) && u != exit && !exit->dominates(u))
+ if (u != entry && entry->dominates(u) && !exit->dominates(u))
body.insert(u);
_body = graph->yank(body);
foreach (Node *u, entry->_out)
if (u != exit)
_body->setEntry(u->address());
- foreach (Node *u, entry->_out) {
- u->_in.remove(entry);
- if (u != exit && u != entry) { // proxy node
- graph->_nodes.remove(u);
- // delete u;
- }
- }
- entry->_out.clear();
+ // remove unneeded nodes in main graph
+ graph->forgetNode(entry);
+ foreach (Node *u, entry->_out)
+ if (dynamic_cast<ProxyNode*>(u))
+ graph->deleteNode(u);
+
+ // attach this while block in place of entry
foreach (Node *u, list<Node*>(entry->_in))
- graph->replaceEdges(u, entry, this);
+ if (!dynamic_cast<ProxyNode*>(u))
+ graph->replaceEdges(u, entry, this);
graph->addEdge(this, exit);
- graph->_nodes.remove(entry);
- _body->structureLoops(_body->stronglyConnectedComponents());
-
- foreach (Node *u, _body->_nodes)
- u->_postOrder = 0;
- _body->orderNodes();
- _body->removeUnreachableNodes();
+ if (_body->_entry)
+ _body->structureLoops(_body->stronglyConnectedComponents());
}
@@ -147,44 +145,30 @@
DoWhileLoop::DoWhileLoop(ControlFlowGraph *graph, Node *entry, Node *latch) : Loop(), _condition(latch) {
+ mimic(entry);
Node *exit = latch->edgeOutsideComponent();
_negate = exit == latch->_out.front();
- _component = entry->_component;
- _dominator = entry->_dominator;
- _interval = entry->_interval;
- _postOrder = entry->_postOrder;
+ // yank out loop body
set<Node*> body;
foreach (Node *u, graph->_nodes)
- if (entry == u || (u != latch && entry->dominates(u) && u != exit && !exit->dominates(u)))
+ if (u != latch && entry->dominates(u) && !exit->dominates(u))
body.insert(u);
_body = graph->yank(body);
_body->setEntry(entry->address());
- foreach (Node *u, latch->_out) {
- u->_in.remove(latch);
- if (u != exit) { // proxy node
- graph->_nodes.remove(u);
-// delete u;
- }
- }
- latch->_out.clear();
+ // remove unneeded nodes in main graph and attach this while block in place of entry
foreach (Node *u, graph->_nodes)
foreach (Node *&v, u->_out)
- if (v->address() == entry->address()) { // proxy node
- // delete v;
+ if (v->address() == entry->address()) {
+ graph->deleteNode(v);
v = this;
_in.push_back(u);
}
+ graph->forgetNode(latch);
graph->addEdge(this, exit);
- graph->_nodes.remove(latch);
_body->structureLoops(_body->stronglyConnectedComponents());
-
- foreach (Node *u, _body->_nodes)
- u->_postOrder = 0;
- _body->orderNodes();
- _body->removeUnreachableNodes();
}
@@ -208,59 +192,45 @@
return ret.str();
}
-#include <cstdlib>
-void panic() {
- exit(0);
-}
EndlessLoop::EndlessLoop(ControlFlowGraph *graph, Node *entry) : Loop() {
- _component = entry->_component;
- _dominator = entry->_dominator;
- _interval = entry->_interval;
- _postOrder = entry->_postOrder;
+ mimic(entry);
Node *exit = 0;
foreach (Node *u, graph->_nodes)
- if (u->_component == entry->_component) {
+ if (u->_component == _component) {
foreach (Node *v, u->_out)
- if (v->_component != entry->_component && (!exit || exit->_postOrder < v->_postOrder))
+ if (v->_component != _component && (!exit || exit->_postOrder < v->_postOrder))
exit = v;
}
+ // yank out body
set<Node*> body;
foreach (Node *u, graph->_nodes)
- if (entry->dominates(u) && (!exit || (u != exit && !exit->dominates(u))))
+ if (u != entry && entry->dominates(u) && (!exit || !exit->dominates(u)))
body.insert(u);
_body = graph->yank(body);
+
+ // compute strongly connected components with detached entry
list< list<Node*> > components = _body->stronglyConnectedComponents();
- foreach (Node *u, list<Node*>(entry->_in))
- graph->replaceEdges(u, entry, this);
- // we have broken down strongly connected components, now reattach entry
+
+ // reattach entry to the loop body
foreach (Node *&u, entry->_out) {
- u->_in.remove(entry);
- if (u != entry) { // proxy node
- graph->_nodes.remove(u);
- Node *uref = dynamic_cast<ProxyNode*>(u)->_node;
- foreach (Node *&v, uref->_in) {
- if (v->address() == entry->address()) {
- _body->_nodes.remove(v);
- v = entry;
- }
- }
- u = uref;
- // delete u;
- }
+ Node *uref = dynamic_cast<ProxyNode*>(u)->_node;
+ uref->_in.push_back(entry);
+ graph->deleteNode(u);
+ u = uref;
}
- if (exit)
- graph->addEdge(this, exit);
graph->_nodes.remove(entry);
_body->_nodes.push_back(entry);
+ // attach this while block in place of entry
+ foreach (Node *u, list<Node*>(entry->_in))
+ graph->replaceEdges(u, entry, this);
+ if (exit)
+ graph->addEdge(this, exit);
+
_body->setEntry(entry->address());
_body->structureLoops(components);
- foreach (Node *u, _body->_nodes)
- 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:32:58 UTC (rev 42388)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-11 17:33:18 UTC (rev 42389)
@@ -26,6 +26,7 @@
virtual uint32 address() = 0;
bool dominates(Node *u);
Node *edgeOutsideComponent();
+ void mimic(Node *node);
virtual std::string toString() = 0;
};
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