[Scummvm-cvs-logs] SF.net SVN: scummvm:[42340] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Fri Jul 10 17:10:21 CEST 2009
Revision: 42340
http://scummvm.svn.sourceforge.net/scummvm/?rev=42340&view=rev
Author: kjdf
Date: 2009-07-10 15:10:21 +0000 (Fri, 10 Jul 2009)
Log Message:
-----------
decompiler: fixed while detection, graphical output for topmost while loops
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 15:04:41 UTC (rev 42339)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-10 15:10:21 UTC (rev 42340)
@@ -23,7 +23,7 @@
("disasm", "print disassembly")
("blocks", "print basic blocks")
("graph-intervals", value<unsigned>(), "print arg-th graph intervals")
- // ("graph-struct", "print graph with marked structure information")
+ ("graph-struct", "print graph with marked structure information")
// ("decompile", "print decompiled program and exit")
("no-remove-jumps", "don't remove jumps-to-jumps")
("fontname", value<string>()->default_value("Courier"), "font to use with dot output");
@@ -81,5 +81,10 @@
cout << cfg.graphvizToString(vars["fontname"].as<string>());
exit(0);
}
+ if (vars.count("graph-struct")) {
+ cfg.structureLoops();
+ cout << cfg.graphvizToString(vars["fontname"].as<string>());
+ exit(0);
+ }
return 0;
}
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-10 15:04:41 UTC (rev 42339)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-10 15:10:21 UTC (rev 42340)
@@ -57,6 +57,28 @@
}
+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;
+ foreach (Node *v, u->_out)
+ ret << '"' << u << "\" -> \"" << v << '"' << ";" << endl;
+ }
+ ret << "}" << endl;
+ return ret.str();
+}
+
+
bool postOrderCompare(Node *a, Node *b) {
return a->_number < b->_number;
}
@@ -184,9 +206,9 @@
// intervals in the original graph
void ControlFlowGraph::extendIntervals() {
ControlFlowGraph d;
- map<Node*, DerivedNode*> trans;
+ map<Node*, ProxyNode*> trans;
foreach (Node *interval, intervals()) {
- trans[interval] = new DerivedNode(interval);
+ trans[interval] = new ProxyNode(interval);
d._nodes.push_back(trans[interval]);
}
foreach (Node *interval, intervals())
@@ -197,34 +219,17 @@
d.assignIntervals();
foreach (Node *du, d._nodes)
foreach (Node *v, _nodes)
- if (v->_interval == dynamic_cast<DerivedNode*>(du)->_primitive)
- v->_interval = dynamic_cast<DerivedNode*>(du->_interval)->_primitive;
+ if (v->_interval == dynamic_cast<ProxyNode*>(du)->_node)
+ v->_interval = dynamic_cast<ProxyNode*>(du->_interval)->_node;
}
string ControlFlowGraph::graphvizToString(const string &fontname, int fontsize) {
stringstream ret;
ret << "digraph G {" << endl;
- foreach (Node *interval, intervals()) {
- ret << "subgraph " << '"' << "cluster_" << interval << '"' << " {" << endl;
- ret << "style=dotted;" << endl;
- foreach (Node *u, _nodes)
- if (u->_interval == interval) {
- 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 << "}" << endl;
- }
- foreach (Node *u, _nodes)
- foreach (Node *v, u->_out)
- ret << '"' << u << "\" -> \"" << v << '"' << ";" << endl;
+ ret << graphvizPrintSubgraph(this, fontname, fontsize);
+ foreach (ControlFlowGraph *graph, _subgraphs)
+ ret << graphvizPrintSubgraph(graph, fontname, fontsize);
ret << "}" << endl;
return ret.str();
}
@@ -320,17 +325,25 @@
}
-void ControlFlowGraph::yank(set<Node*> &nodes, ControlFlowGraph &subgraph) {
+ControlFlowGraph *ControlFlowGraph::yank(set<Node*> &nodes) {
+ 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(v);
+ }
+ ControlFlowGraph *subgraph = new ControlFlowGraph;
+ _subgraphs.push_back(subgraph);
foreach (Node *u, nodes) {
- subgraph._nodes.push_back(u);
+ subgraph->_nodes.push_back(u);
_nodes.remove(u);
- foreach (Node *&v, u->_out)
- if (!contains(nodes, v))
- v = new OutsideNode(v);
- foreach (Node *&v, u->_in)
- if (!contains(nodes, v))
- v = new OutsideNode(v);
}
+ return subgraph;
}
@@ -344,9 +357,9 @@
foreach (Node *v, u->_out)
if (v == entry && (!latch || latch->_number > u->_number))
latch = u;
- if (entry->edgeOutsideComponent()) { // while loop
- new WhileLoop(*this, entry);
- } else if (latch->edgeOutsideComponent()) {
+ 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
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-10 15:04:41 UTC (rev 42339)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-10 15:10:21 UTC (rev 42340)
@@ -17,6 +17,7 @@
Node *_entry;
std::list<Node*> _nodes;
+ std::list<ControlFlowGraph*> _subgraphs;
std::map<address_t, BasicBlock*> _targets; // helps partitioning code into basic nodes
ControlFlowGraph();
@@ -32,7 +33,7 @@
void replaceEdges(Node *from, Node *oldTo, Node *newTo);
void setEntry(address_t entry);
std::list< std::list<Node*> > stronglyConnectedComponents();
- void yank(std::set<Node*> &body, ControlFlowGraph &subgraph);
+ ControlFlowGraph *yank(std::set<Node*> &body);
void structureLoops();
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-10 15:04:41 UTC (rev 42339)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-10 15:10:21 UTC (rev 42340)
@@ -59,61 +59,55 @@
}
-DerivedNode::DerivedNode(Node *primitive) : Node(), _primitive(primitive) {
+ProxyNode::ProxyNode(Node *node) : Node(), _node(node) {
+ _component = node->_component;
+ _dominator = node->_dominator;
+ _interval = node->_interval;
+ _number = node->_number;
}
-DerivedNode::~DerivedNode() {
+ProxyNode::~ProxyNode() {
}
-uint32 DerivedNode::address() {
- return _primitive->address();
-}
-
-
-string DerivedNode::toString() {
- return _primitive->toString();
-}
-
-
-OutsideNode::OutsideNode(Node *node) : Node(), _node(node) {
-}
-
-
-OutsideNode::~OutsideNode() {
-}
-
-
-uint32 OutsideNode::address() {
+uint32 ProxyNode::address() {
return _node->address();
}
-string OutsideNode::toString() {
+string ProxyNode::toString() {
ostringstream ret;
ret << "goto " << _node->address() << endl;
return ret.str();
}
-WhileLoop::WhileLoop(ControlFlowGraph &graph, Node *entry) : Node(), _condition(entry) {
+WhileLoop::WhileLoop(ControlFlowGraph *graph, Node *entry) : Node(), _condition(entry) {
Node *exit = entry->edgeOutsideComponent();
- _out.push_back(exit);
- foreach (Node *u, entry->_out)
- u->_in.remove(entry); // remove dangling back-edges just in case
+ _negate = exit != entry->_out.front();
+ _condition = entry;
+ _component = entry->_component;
+ _dominator = entry->_dominator;
+ _interval = entry->_interval;
+ _number = entry->_number;
+
set<Node*> body;
- foreach (Node *u, graph._nodes)
+ foreach (Node *u, graph->_nodes)
if (entry->dominates(u) && u != exit && !exit->dominates(u))
body.insert(u);
- _body = new ControlFlowGraph;
- graph.yank(body, *_body);
- graph._nodes.remove(entry);
- foreach (Node *u, entry->_in)
- graph.replaceEdges(u, entry, this);
+ _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);
+ entry->_out.clear();
+ foreach (Node *u, list<Node*>(entry->_in))
+ graph->replaceEdges(u, entry, this);
+ graph->addEdge(this, exit);
+ graph->_nodes.remove(entry);
}
@@ -128,6 +122,14 @@
string WhileLoop::toString() {
ostringstream ret;
- ret << "while loop..." << endl;
+ ret << "while";
+ if (_negate)
+ ret << " not";
+ ret << " (" << endl;
+ ret << _condition->toString();
+ if (_body->_entry)
+ ret << ") { [" << phex(_body->_entry->address()) << "] }" << endl;
+ else
+ ret << ") { }" << endl;
return ret.str();
}
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-10 15:04:41 UTC (rev 42339)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-10 15:10:21 UTC (rev 42340)
@@ -42,24 +42,12 @@
};
-struct DerivedNode : public Node {
+struct ProxyNode : public Node {
- Node *_primitive; // interval header of the graph from which this graph has been derived
-
- DerivedNode(Node *primitive);
- ~DerivedNode();
-
- uint32 address();
- std::string toString();
-};
-
-
-struct OutsideNode : public Node {
-
Node *_node;
- OutsideNode(Node *node);
- ~OutsideNode();
+ ProxyNode(Node *node);
+ ~ProxyNode();
uint32 address();
std::string toString();
@@ -70,8 +58,9 @@
Node *_condition;
ControlFlowGraph *_body;
+ bool _negate;
- WhileLoop(ControlFlowGraph &graph, Node *entry);
+ WhileLoop(ControlFlowGraph *graph, Node *entry);
~WhileLoop();
uint32 address();
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