[Scummvm-cvs-logs] SF.net SVN: scummvm:[42316] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Fri Jul 10 00:36:05 CEST 2009
Revision: 42316
http://scummvm.svn.sourceforge.net/scummvm/?rev=42316&view=rev
Author: kjdf
Date: 2009-07-09 22:36:04 +0000 (Thu, 09 Jul 2009)
Log Message:
-----------
decompiler: (untested) top-level 'while' structuring
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.h
tools/branches/gsoc2009-decompiler/decompiler/misc.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-09 21:46:03 UTC (rev 42315)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-09 22:36:04 UTC (rev 42316)
@@ -13,6 +13,19 @@
#endif
+
+std::list<Node*> componentEntryPoints(std::list<Node*> &component) {
+ std::list<Node*> ret;
+ foreach (Node *u, component)
+ foreach (Node *v, u->_in)
+ if (u->_component != v->_component) {
+ ret.push_back(u);
+ break;
+ }
+ return ret;
+}
+
+
void componentVisit(Node *u, Node *representative, list<Node*> &component) {
u->_component = representative;
component.push_back(u);
@@ -165,18 +178,6 @@
}
-std::list<Node*> ControlFlowGraph::componentEntryPoints(std::list<Node*> &component) {
- std::list<Node*> ret;
- foreach (Node *u, component)
- foreach (Node *v, u->_in)
- if (u->_component != v->_component) {
- ret.push_back(u);
- break;
- }
- return ret;
-}
-
-
// a derived graph, given set of intervals, is a graph in which
// all intervals have been collapsed to a single node, and edge
// exists between nodes if there are edges crossing corresponding
@@ -317,3 +318,41 @@
}
return ret;
}
+
+
+void ControlFlowGraph::yank(set<Node*> &nodes, ControlFlowGraph &subgraph) {
+ foreach (Node *u, nodes) {
+ 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);
+ }
+}
+
+
+void ControlFlowGraph::structureLoops() {
+ foreach (list<Node*> component, stronglyConnectedComponents()) {
+ list<Node*> entries = componentEntryPoints(component);
+ if (entries.size() == 1) {
+ Node *entry = entries.front();
+ 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))
+ latch = u;
+ if (entry->edgeOutsideComponent()) { // while loop
+ new WhileLoop(*this, entry);
+ } else if (latch->edgeOutsideComponent()) {
+ // TODO do-while loop
+ } else {
+ // TODO infinite loop
+ }
+ } else {
+ // TODO: unreducible graph, lots of heuristics
+ }
+ }
+}
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-09 21:46:03 UTC (rev 42315)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-09 22:36:04 UTC (rev 42316)
@@ -25,7 +25,6 @@
void addBasicBlocksFromScript(std::list<Instruction*>::iterator scriptBegin, std::list<Instruction*>::iterator scriptEnd);
void addEdge(Node *from, Node *to);
void assignDominators(); // after order
- static std::list<Node*> componentEntryPoints(std::list<Node*> &component);
std::string graphvizToString(const std::string &fontname="", int fontsize=0);
void orderNodes();
void removeJumpsToJumps();
@@ -33,7 +32,10 @@
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);
+ void structureLoops();
+
// to be removed
void assignIntervals();
void extendIntervals();
Modified: tools/branches/gsoc2009-decompiler/decompiler/misc.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/misc.h 2009-07-09 21:46:03 UTC (rev 42315)
+++ tools/branches/gsoc2009-decompiler/decompiler/misc.h 2009-07-09 22:36:04 UTC (rev 42316)
@@ -5,7 +5,9 @@
#include <sstream>
#include <iomanip>
+#include <boost/foreach.hpp>
+
typedef unsigned char uint8;
typedef short int16;
typedef unsigned short uint16;
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-09 21:46:03 UTC (rev 42315)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.cpp 2009-07-09 22:36:04 UTC (rev 42316)
@@ -1,5 +1,8 @@
#include "node.h"
+#include "graph.h"
+#include <set>
+
#include <boost/foreach.hpp>
using namespace boost;
@@ -18,6 +21,22 @@
}
+bool Node::dominates(Node *u) {
+ for (; u; u = u->_dominator)
+ if (u->_dominator == this)
+ return true;
+ return false;
+}
+
+
+Node *Node::edgeOutsideComponent() {
+ foreach (Node *u, _out)
+ if (u->_component != _component)
+ return u;
+ return 0;
+}
+
+
BasicBlock::BasicBlock(list<Instruction*>::iterator first, list<Instruction*>::iterator last) : Node() {
copy(first, last, back_inserter(_instructions));
}
@@ -56,3 +75,57 @@
string DerivedNode::toString() {
return _primitive->toString();
}
+
+
+OutsideNode::OutsideNode(Node *node) : Node(), _node(node) {
+}
+
+
+OutsideNode::~OutsideNode() {
+}
+
+
+uint32 OutsideNode::address() {
+ return _node->address();
+}
+
+
+string OutsideNode::toString() {
+ ostringstream ret;
+ ret << "goto " << _node->address() << endl;
+ return ret.str();
+}
+
+
+WhileLoop::WhileLoop(ControlFlowGraph &graph, Node *entry) : Node(), _condition(entry) {
+ Node *exit = entry->edgeOutsideComponent();
+ _out.push_back(exit);
+ set<Node*> body;
+ 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);
+ foreach (Node *u, entry->_out)
+ if (u != exit)
+ _body->setEntry(u->address());
+}
+
+
+WhileLoop::~WhileLoop() {
+}
+
+
+uint32 WhileLoop::address() {
+ return _condition->address();
+}
+
+
+string WhileLoop::toString() {
+ ostringstream ret;
+ ret << "while loop..." << endl;
+ return ret.str();
+}
Modified: tools/branches/gsoc2009-decompiler/decompiler/node.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-09 21:46:03 UTC (rev 42315)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.h 2009-07-09 22:36:04 UTC (rev 42316)
@@ -8,6 +8,9 @@
#include <boost/utility.hpp>
+struct ControlFlowGraph;
+
+
struct Node : boost::noncopyable {
Node *_component;
@@ -21,6 +24,8 @@
virtual ~Node();
virtual uint32 address() = 0;
+ bool dominates(Node *u);
+ Node *edgeOutsideComponent();
virtual std::string toString() = 0;
};
@@ -48,4 +53,29 @@
std::string toString();
};
+
+struct OutsideNode : public Node {
+
+ Node *_node;
+
+ OutsideNode(Node *node);
+ ~OutsideNode();
+
+ uint32 address();
+ std::string toString();
+};
+
+
+struct WhileLoop : public Node {
+
+ Node *_condition;
+ ControlFlowGraph *_body;
+
+ WhileLoop(ControlFlowGraph &graph, Node *entry);
+ ~WhileLoop();
+
+ 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