[Scummvm-cvs-logs] SF.net SVN: scummvm:[42353] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Fri Jul 10 22:36:35 CEST 2009
Revision: 42353
http://scummvm.svn.sourceforge.net/scummvm/?rev=42353&view=rev
Author: kjdf
Date: 2009-07-10 20:36:35 +0000 (Fri, 10 Jul 2009)
Log Message:
-----------
decompiler: all while loops recursively detected and printed in graph output
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
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/decompiler.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-10 19:56:59 UTC (rev 42352)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-10 20:36:35 UTC (rev 42353)
@@ -22,6 +22,7 @@
("check-reducibility", "check if the graph is reducible")
("disasm", "print disassembly")
("blocks", "print basic blocks")
+ ("graph", "print graph")
// ("graph-intervals", value<unsigned>(), "print arg-th graph intervals")
("graph-struct", "print graph with marked structure information")
// ("decompile", "print decompiled program and exit")
@@ -67,6 +68,10 @@
cfg.orderNodes();
cfg.removeUnreachableNodes();
cfg.assignDominators();
+ if (vars.count("graph")) {
+ cout << cfg.graphvizToString(vars["fontname"].as<string>());
+ exit(0);
+ }
if (vars.count("check-reducibility")) {
if (cfg.isReducible())
exit(0);
@@ -75,7 +80,7 @@
exit(1);
}
if (vars.count("graph-struct")) {
- cfg.structureLoops();
+ cfg.structureLoops(cfg.stronglyConnectedComponents());
cout << cfg.graphvizToString(vars["fontname"].as<string>());
exit(0);
}
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-10 19:56:59 UTC (rev 42352)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-10 20:36:35 UTC (rev 42353)
@@ -57,22 +57,32 @@
}
+string graphvizPrintBox(Node *u, const string &fontname, int fontsize) {
+ ostringstream ret;
+ ret << '"' << u << "\"[";
+ if (fontname != "")
+ 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 << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << endl;
+ return ret.str();
+}
+
string graphvizPrintSubgraph(ControlFlowGraph *graph, const string &fontname, int fontsize) {
ostringstream ret;
ret << "subgraph \"cluster_" << graph << "\" {" << endl;
ret << "style=dotted" << endl;
foreach (Node *u, graph->_nodes) {
- ret << '"' << u << "\"[";
- if (fontname != "")
- 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 << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << endl;
+ 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;
+ // }
}
ret << "}" << endl;
@@ -80,7 +90,7 @@
ret << graphvizPrintSubgraph(subgraph, fontname, fontsize);
foreach (Node *u, graph->_nodes) {
- WhileLoop *loop = dynamic_cast<WhileLoop*>(u);
+ Loop *loop = dynamic_cast<Loop*>(u);
if (loop && loop->_body->_entry)
ret << '"' << u << "\" -> \"" << loop->_body->_entry << "\"[color=blue,style=dashed]" << endl;
}
@@ -261,8 +271,7 @@
void ControlFlowGraph::orderNodes() {
- assert(_entry);
- if (!_entry->_number)
+ if (_entry && !_entry->_number)
orderVisit(_entry, 0);
}
@@ -295,7 +304,7 @@
if ((*it)->_number)
it++;
else {
- delete *it;
+ // delete *it;
it = _nodes.erase(it);
}
}
@@ -320,6 +329,18 @@
list< list<Node*> > ControlFlowGraph::stronglyConnectedComponents() {
list< list<Node*> > ret;
+ foreach (Node *u, _nodes) {
+ u->_component = 0;
+ u->_number = 0;
+ }
+
+ int n = 0;
+ if (_entry && !_entry->_number)
+ n = orderVisit(_entry, n);
+ foreach (Node *u, _nodes)
+ if (!u->_number)
+ n = orderVisit(u, n);
+
list<Node*> nodes = inPostOrder(_nodes);
nodes.reverse();
foreach (Node *u, nodes)
@@ -362,18 +383,17 @@
}
-void ControlFlowGraph::structureLoops() {
+void ControlFlowGraph::structureLoops(const list< list<Node*> > &components) {
if (!_entry)
return;
foreach (Node *u, _nodes) {
- u->_component = 0;
u->_dominator = 0;
- u->_interval = 0;
u->_number = 0;
}
orderNodes();
+ removeUnreachableNodes();
assignDominators();
- foreach (list<Node*> component, stronglyConnectedComponents()) {
+ foreach (list<Node*> component, components) {
list<Node*> entries = componentEntryPoints(component);
if (entries.size() == 1) {
Node *entry = entries.front();
@@ -382,12 +402,16 @@
foreach (Node *v, u->_out)
if (v == entry && (!latch || latch->_number > u->_number))
latch = u;
- if (latch && entry->edgeOutsideComponent()) { // while loop
- _nodes.push_back(new WhileLoop(this, entry));
- } else if (latch && latch->edgeOutsideComponent()) {
- // TODO do-while loop
- } else {
- // TODO infinite loop
+ if (0) {
+ } else 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));
+ cerr << "done while loop at " << phex(entry->address()) << endl;
+ } else if (latch) {
+ _nodes.push_back(new EndlessLoop(this, entry));
+ cerr << "done infinite loop at " << phex(entry->address()) << endl;
}
} else {
// TODO: unreducible graph, lots of heuristics
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-10 19:56:59 UTC (rev 42352)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-10 20:36:35 UTC (rev 42353)
@@ -35,7 +35,7 @@
std::list< std::list<Node*> > stronglyConnectedComponents();
ControlFlowGraph *yank(std::set<Node*> &body);
- void structureLoops();
+ void structureLoops(const std::list< std::list<Node*> > &components);
// to be removed
void assignIntervals();
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-10 19:56:59 UTC (rev 42352)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-10 20:36:35 UTC (rev 42353)
@@ -83,10 +83,9 @@
}
-WhileLoop::WhileLoop(ControlFlowGraph *graph, Node *entry) : Node(), _condition(entry) {
+WhileLoop::WhileLoop(ControlFlowGraph *graph, Node *entry) : Loop(), _condition(entry) {
Node *exit = entry->edgeOutsideComponent();
_negate = exit != entry->_out.front();
- _condition = entry;
_component = entry->_component;
_dominator = entry->_dominator;
_interval = entry->_interval;
@@ -103,9 +102,9 @@
foreach (Node *u, entry->_out) {
u->_in.remove(entry);
- if (u != exit) {
+ if (u != exit && u != entry) { // proxy node
graph->_nodes.remove(u);
- delete u;
+ // delete u;
}
}
entry->_out.clear();
@@ -114,7 +113,12 @@
graph->addEdge(this, exit);
graph->_nodes.remove(entry);
- _body->structureLoops();
+ _body->structureLoops(_body->stronglyConnectedComponents());
+
+ foreach (Node *u, _body->_nodes)
+ u->_number = 0;
+ _body->orderNodes();
+ _body->removeUnreachableNodes();
}
@@ -140,3 +144,140 @@
ret << ") { }" << endl;
return ret.str();
}
+
+
+DoWhileLoop::DoWhileLoop(ControlFlowGraph *graph, Node *entry, Node *latch) : Loop(), _condition(latch) {
+ Node *exit = latch->edgeOutsideComponent();
+ _negate = exit == latch->_out.front();
+ _component = entry->_component;
+ _dominator = entry->_dominator;
+ _interval = entry->_interval;
+ _number = entry->_number;
+
+ set<Node*> body;
+ foreach (Node *u, graph->_nodes)
+ if (entry == u || (u != latch && entry->dominates(u) && u != exit && !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();
+ foreach (Node *u, graph->_nodes)
+ foreach (Node *&v, u->_out)
+ if (v->address() == entry->address()) { // proxy node
+ // delete v;
+ v = this;
+ _in.push_back(u);
+ }
+ graph->addEdge(this, exit);
+ graph->_nodes.remove(latch);
+
+ _body->structureLoops(_body->stronglyConnectedComponents());
+
+ foreach (Node *u, _body->_nodes)
+ u->_number = 0;
+ _body->orderNodes();
+ _body->removeUnreachableNodes();
+}
+
+
+DoWhileLoop::~DoWhileLoop() {
+}
+
+
+uint32 DoWhileLoop::address() {
+ return _body->_entry->address();
+}
+
+
+string DoWhileLoop::toString() {
+ ostringstream ret;
+ ret << "do { [" << phex(_body->_entry->address()) << "] } while ";
+ if (_negate)
+ ret << "not ";
+ ret << "(" << endl;
+ ret << _condition->toString();
+ ret << ")" << endl;
+ 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;
+ _number = entry->_number;
+ 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))
+ exit = v;
+ }
+
+ set<Node*> body;
+ foreach (Node *u, graph->_nodes)
+ if (entry->dominates(u) && (!exit || (u != exit && !exit->dominates(u))))
+ body.insert(u);
+ _body = graph->yank(body);
+ 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
+ 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;
+ }
+ }
+ if (exit)
+ graph->addEdge(this, exit);
+ graph->_nodes.remove(entry);
+ _body->_nodes.push_back(entry);
+
+ _body->setEntry(entry->address());
+ _body->structureLoops(components);
+ foreach (Node *u, _body->_nodes)
+ u->_number = 0;
+ _body->orderNodes();
+ _body->removeUnreachableNodes();
+}
+
+
+EndlessLoop::~EndlessLoop() {
+}
+
+
+uint32 EndlessLoop::address() {
+ return _body->_entry->address();
+}
+
+
+string EndlessLoop::toString() {
+ ostringstream ret;
+ ret << "for (;;) { ";
+ if (_body->_entry)
+ ret << "[" << phex(_body->_entry->address()) << "] ";
+ ret << "}" << endl;
+ return ret.str();
+}
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-10 19:56:59 UTC (rev 42352)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-10 20:36:35 UTC (rev 42353)
@@ -54,10 +54,19 @@
};
-struct WhileLoop : public Node {
+struct Loop : public Node {
+ ControlFlowGraph *_body;
+
+ Loop() : Node(), _body() {
+ }
+
+};
+
+
+struct WhileLoop : public Loop {
+
Node *_condition;
- ControlFlowGraph *_body;
bool _negate;
WhileLoop(ControlFlowGraph *graph, Node *entry);
@@ -67,4 +76,27 @@
std::string toString();
};
+
+struct DoWhileLoop : public Loop {
+
+ Node *_condition;
+ bool _negate;
+
+ DoWhileLoop(ControlFlowGraph *graph, Node *entry, Node *latch);
+ ~DoWhileLoop();
+
+ uint32 address();
+ std::string toString();
+};
+
+
+struct EndlessLoop : public Loop {
+
+ EndlessLoop(ControlFlowGraph *graph, Node *entry);
+ ~EndlessLoop();
+
+ uint32 address();
+ std::string toString();
+};
+
#endif
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