[Scummvm-cvs-logs] SF.net SVN: scummvm:[42395] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Sat Jul 11 22:31:41 CEST 2009
Revision: 42395
http://scummvm.svn.sourceforge.net/scummvm/?rev=42395&view=rev
Author: kjdf
Date: 2009-07-11 20:31:41 +0000 (Sat, 11 Jul 2009)
Log Message:
-----------
decompiler: 'if' structuring
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-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-11 20:31:41 UTC (rev 42395)
@@ -80,6 +80,7 @@
}
if (vars.count("graph-struct")) {
cfg.structureLoops(cfg.stronglyConnectedComponents());
+ cfg.structureConditionals();
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-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-11 20:31:41 UTC (rev 42395)
@@ -96,6 +96,14 @@
ret << '"' << u << "\" -> \"" << loop->_body->_entry << "\"[color=blue,style=dashed]" << endl;
}
+ foreach (Node *u, graph->_nodes) {
+ IfThenElse *ifte = dynamic_cast<IfThenElse*>(u);
+ if (ifte && ifte->_consequence->_entry)
+ ret << '"' << u << "\" -> \"" << ifte->_consequence->_entry << "\"[color=red]" << endl;
+ if (ifte && ifte->_alternative->_entry)
+ ret << '"' << u << "\" -> \"" << ifte->_alternative->_entry << "\"[color=red,style=dashed]" << endl;
+ }
+
return ret.str();
}
@@ -404,7 +412,7 @@
foreach (Node *v, u->_out)
if (v == entry && (!latch || latch->_postOrder > u->_postOrder))
latch = u;
- 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()) {
@@ -419,3 +427,17 @@
}
}
}
+
+
+void ControlFlowGraph::structureConditionals() {
+ assignDominators();
+ foreach (Node *u, inPostOrder(_nodes))
+ if (u->_out.size() == 2) {
+ _nodes.push_back(new IfThenElse(this, u));
+ cerr << "done if-then-else at " << phex(u->address()) << endl;
+ return structureConditionals();
+ }
+ foreach (ControlFlowGraph *subgraph, _subgraphs)
+ if (subgraph->_entry)
+ subgraph->structureConditionals();
+}
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-11 20:31:41 UTC (rev 42395)
@@ -37,6 +37,7 @@
ControlFlowGraph *yank(std::set<Node*> &body);
void structureLoops(const std::list< std::list<Node*> > &components);
+ void structureConditionals();
// to be removed
void assignIntervals();
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-11 20:31:41 UTC (rev 42395)
@@ -13,6 +13,20 @@
#endif
+
+bool reaches(Node *u, Node *t, set<Node*> &visited) {
+ if (u == t)
+ return true;
+ if (contains(visited, u))
+ return false;
+ visited.insert(u);
+ foreach (Node *v, u->_out)
+ if (reaches(v, t, visited))
+ return true;
+ return false;
+}
+
+
Node::Node() : _component(), _dominator(), _interval(), _postOrder() {
}
@@ -45,6 +59,12 @@
}
+bool Node::reaches(Node *t) {
+ set<Node*> visited;
+ return ::reaches(this, t, visited);
+}
+
+
BasicBlock::BasicBlock(list<Instruction*>::iterator first, list<Instruction*>::iterator last) : Node() {
copy(first, last, back_inserter(_instructions));
}
@@ -109,7 +129,9 @@
if (dynamic_cast<ProxyNode*>(u))
graph->deleteNode(u);
- // attach this while block in place of entry
+ // attach this loop block in place of entry
+ if (graph->_entry == entry)
+ graph->_entry = this;
foreach (Node *u, list<Node*>(entry->_in))
if (!dynamic_cast<ProxyNode*>(u))
graph->replaceEdges(u, entry, this);
@@ -157,7 +179,9 @@
_body = graph->yank(body);
_body->setEntry(entry->address());
- // remove unneeded nodes in main graph and attach this while block in place of entry
+ // remove unneeded nodes in main graph and attach this loop block in place of entry
+ if (graph->_entry == entry)
+ graph->_entry = this;
foreach (Node *u, graph->_nodes)
foreach (Node *&v, u->_out)
if (v->address() == entry->address()) {
@@ -223,7 +247,9 @@
graph->_nodes.remove(entry);
_body->_nodes.push_back(entry);
- // attach this while block in place of entry
+ // attach this loop block in place of entry
+ if (graph->_entry == entry)
+ graph->_entry = this;
foreach (Node *u, list<Node*>(entry->_in))
graph->replaceEdges(u, entry, this);
if (exit)
@@ -251,3 +277,65 @@
ret << "}" << endl;
return ret.str();
}
+
+
+IfThenElse::IfThenElse(ControlFlowGraph *graph, Node *entry) : Node(), _condition(entry) {
+ mimic(entry);
+ Node *exit = 0;
+ foreach (Node *u, graph->_nodes)
+ if (u->_dominator == entry && u->_in.size() >= 2)
+ exit = u;
+
+ // yank out true and false branch
+ set<Node*> consequence, alternative;
+ foreach (Node *u, graph->_nodes)
+ if (u != entry && entry->dominates(u) && !entry->_out.front()->reaches(u))
+ consequence.insert(u);
+ foreach (Node *u, graph->_nodes)
+ if (u != entry && entry->dominates(u) && !entry->_out.back()->reaches(u))
+ alternative.insert(u);
+ _consequence = graph->yank(consequence);
+ if (!consequence.empty())
+ _consequence->setEntry(entry->_out.back()->address());
+ _alternative = graph->yank(alternative);
+ if (!alternative.empty())
+ _alternative->setEntry(entry->_out.front()->address());
+
+ // remove unneeded nodes in main graph
+ graph->forgetNode(entry);
+ foreach (Node *u, entry->_out)
+ if (dynamic_cast<ProxyNode*>(u))
+ graph->deleteNode(u);
+
+ // attach this conditional block in place of entry
+ if (graph->_entry == entry)
+ graph->_entry = this;
+ foreach (Node *u, list<Node*>(entry->_in))
+ graph->replaceEdges(u, entry, this);
+ if (exit)
+ graph->addEdge(this, exit);
+}
+
+
+IfThenElse::~IfThenElse() {
+}
+
+
+uint32 IfThenElse::address() {
+ return _condition->address();
+}
+
+
+string IfThenElse::toString() {
+ ostringstream ret;
+ ret << "if (" << endl;
+ ret << _condition->toString();
+ ret << ") { ";
+ if (_consequence->_entry)
+ ret << "[" << phex(_consequence->_entry->address()) << "] ";
+ ret << "} else { ";
+ if (_alternative->_entry)
+ ret << "[" << phex(_alternative->_entry->address()) << "] ";
+ ret << "}" << endl;
+ return ret.str();
+}
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-11 20:31:41 UTC (rev 42395)
@@ -27,6 +27,7 @@
bool dominates(Node *u);
Node *edgeOutsideComponent();
void mimic(Node *node);
+ bool reaches(Node *t);
virtual std::string toString() = 0;
};
@@ -61,7 +62,6 @@
Loop() : Node(), _body() {
}
-
};
@@ -100,4 +100,18 @@
std::string toString();
};
+
+struct IfThenElse : public Node {
+
+ Node *_condition;
+ ControlFlowGraph *_consequence;
+ ControlFlowGraph *_alternative;
+
+ IfThenElse(ControlFlowGraph *graph, Node *entry);
+ ~IfThenElse();
+
+ 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