[Scummvm-cvs-logs] SF.net SVN: scummvm:[41816] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Tue Jun 23 20:37:12 CEST 2009
Revision: 41816
http://scummvm.svn.sourceforge.net/scummvm/?rev=41816&view=rev
Author: kjdf
Date: 2009-06-23 18:37:10 +0000 (Tue, 23 Jun 2009)
Log Message:
-----------
decompiler: graph collapsing
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/cfg.h
tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.h
tools/branches/gsoc2009-decompiler/decompiler/misc.h
tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h
Modified: tools/branches/gsoc2009-decompiler/decompiler/cfg.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/cfg.h 2009-06-23 18:36:24 UTC (rev 41815)
+++ tools/branches/gsoc2009-decompiler/decompiler/cfg.h 2009-06-23 18:37:10 UTC (rev 41816)
@@ -81,7 +81,7 @@
}
void removeDeadBlocks() {
- _graph.removeUnreachableNodes(_nodes[0]);
+ _graph.removeUnreachableNodes();
}
typedef Graph<Block*>::Node Node;
@@ -91,11 +91,6 @@
Graph<Block*> _graph;
- template<typename Container, typename Element>
- static bool contains(const Container &c, const Element &e) {
- return c.find(e) != c.end();
- }
-
CFG(Script &script) : _script(script) {
_nodes[script.size()] = 0;
Jump *jump;
Modified: tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-06-23 18:36:24 UTC (rev 41815)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-06-23 18:37:10 UTC (rev 41816)
@@ -51,7 +51,7 @@
}
// cfg.removeJumpsToJumps();
// cfg.removeDeadBlocks();
- cfg._graph.assignIntervals(cfg._nodes[0]);
+ cfg._graph.intervals();
if (vars.count("graph")) {
cfg.printDot(cout);
exit(0);
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-23 18:36:24 UTC (rev 41815)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-23 18:37:10 UTC (rev 41816)
@@ -1,6 +1,10 @@
#ifndef GRAPH_H
#define GRAPH_H
+#include "misc.h"
+
+#include <cassert>
+
#include <list>
#include <map>
#include <set>
@@ -46,13 +50,15 @@
};
mutable std::list<Node*> _nodes;
+ Node *_entry;
- Graph() {
+ Graph() : _entry() {
}
Graph(const Graph &g) {
+ g.removeHiddenNodes();
std::map<Node*, Node*> trans;
- g.removeHiddenNodes();
+ trans[0] = 0;
foreach (Node *u, g._nodes)
trans[u] = addNode(u->_data);
foreach (Node *u, g._nodes) {
@@ -60,10 +66,10 @@
trans[u]->_in.push_back(trans[v]);
foreach (Node *v, u->_out)
trans[u]->_in.push_back(trans[v]);
- if (u->_interval)
- trans[u]->_interval = trans[u->_interval];
- trans[u]->_primary = u->_primary;
+ trans[u]->_interval = trans[u->_interval];
+ trans[u]->_primitive = u->_primitive;
}
+ _entry = trans[g._entry];
}
~Graph() {
@@ -71,9 +77,15 @@
delete u;
}
+ void setEntry(Node *entry) {
+ _entry = entry;
+ }
+
Node *addNode(const Data &data) {
Node* node = new Node(data);
_nodes.push_back(node);
+ if (!_entry)
+ _entry = node;
return node;
}
@@ -99,58 +111,53 @@
node = newTo;
}
- void removeUnreachableNodes(Node *start) {
+ void removeUnreachableNodes() {
foreach (Node *u, _nodes)
u->_visited = false;
- visit(start);
+ assert(_entry);
+ visit(_entry);
foreach (Node *u, _nodes)
if (!u->_visited)
removeNode(u);
}
- Graph derive() {
- return Graph();
+ std::list<Node*> intervals() const {
+ std::list<Node*> ret;
+ assignIntervals();
+ foreach (Node *u, _nodes)
+ if (u->_interval == u)
+ ret.push_back(u);
+ return ret;
}
- void test(int level=0) {
- }
-
- void assignIntervals(Node *start) {
- std::list<Node*> intervals;
- intervals.push_back(start);
- foreach (Node *interval, intervals) {
- interval->_interval = interval;
- for (bool added = true; added; ) {
- added = false;
- foreach (Node *m, _nodes) {
- bool allPredInInterval = true;
- foreach (Node *p, m->_in)
- allPredInInterval &= p->_interval == interval;
- if (!m->_interval && allPredInInterval) {
- added = true;
- m->_interval = interval;
- }
+ Graph derive() {
+ removeHiddenNodes();
+ assignIntervals();
+ Graph g;
+ std::map<Node*, Node*> trans;
+ foreach (Node *u, _nodes)
+ if (u->_interval == u) {
+ trans[u] = g.addNode(u->_data);
+ trans[u]->_primitive = u;
+ }
+ foreach (Node *interval, intervals()) {
+ std::set<Node*> pred;
+ foreach (Node *u, interval->_in)
+ if (u->_interval != interval && !contains(pred, u->_interval)) {
+ pred.insert(u->_interval);
+ g.addEdge(trans[u->_interval], trans[interval]);
}
- }
- foreach (Node *m, _nodes) {
- bool anyPredInInterval = false;
- foreach (Node *p, m->_in)
- anyPredInInterval |= p->_interval == interval;
- if (!m->_interval && anyPredInInterval)
- intervals.push_back(m);
- }
}
+ g.setEntry(trans[_entry]);
+ return g;
}
template<typename Printer> // printer is a functor taking Data and returning a string
std::string graphvizPrint(Printer printer, const std::string &fontname="Courier", int fontsize=14) const {
+ removeHiddenNodes();
std::stringstream ret;
ret << "digraph G {" << std::endl;
- removeHiddenNodes();
- std::set<Node*> intervals;
- foreach (Node *u, _nodes)
- intervals.insert(u->_interval);
- foreach (Node *interval, intervals) {
+ foreach (Node *interval, intervals()) {
ret << "subgraph " << '"' << "cluster_" << interval << '"' << " {" << std::endl;
ret << "style=dotted;" << std::endl;
foreach (Node *u, _nodes)
@@ -182,6 +189,33 @@
visit(v);
}
+ void assignIntervals() const {
+ std::list<Node*> intervals;
+ intervals.push_back(_entry);
+ foreach (Node *interval, intervals) {
+ interval->_interval = interval;
+ for (bool added = true; added; ) {
+ added = false;
+ foreach (Node *m, _nodes) {
+ bool allPredInInterval = true;
+ foreach (Node *p, m->_in)
+ allPredInInterval &= p->_interval == interval;
+ if (!m->_interval && allPredInInterval) {
+ added = true;
+ m->_interval = interval;
+ }
+ }
+ }
+ foreach (Node *m, _nodes) {
+ bool anyPredInInterval = false;
+ foreach (Node *p, m->_in)
+ anyPredInInterval |= p->_interval == interval;
+ if (!m->_interval && anyPredInInterval)
+ intervals.push_back(m);
+ }
+ }
+ }
+
void removeHiddenNodes() const {
for (typename std::list<Node*>::iterator it = _nodes.begin(); it != _nodes.end(); )
if ((*it)->_hidden) {
Modified: tools/branches/gsoc2009-decompiler/decompiler/misc.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/misc.h 2009-06-23 18:36:24 UTC (rev 41815)
+++ tools/branches/gsoc2009-decompiler/decompiler/misc.h 2009-06-23 18:37:10 UTC (rev 41816)
@@ -10,8 +10,6 @@
#define foreach BOOST_FOREACH
#endif
-using namespace std;
-
typedef unsigned char uint8;
typedef short int16;
typedef unsigned short uint16;
@@ -20,13 +18,18 @@
typedef uint32 address_t; // bytecode address
typedef uint32 index_t; // instruction number in intermediate script
-string phex(int i, int width=4) {
- ostringstream ret;
- ret << hex << setfill('0') << setw(width) << i;
+template<typename Container, typename Element>
+bool contains(const Container &c, const Element &e) {
+ return c.find(e) != c.end();
+}
+
+std::string phex(int i, int width=4) {
+ std::ostringstream ret;
+ ret << std::hex << std::setfill('0') << std::setw(width) << i;
return ret.str();
}
-uint32 read_be_uint32(ifstream &f) {
+uint32 read_be_uint32(std::ifstream &f) {
uint32 ret = 0;
ret |= f.get() << 24;
ret |= f.get() << 16;
@@ -35,7 +38,7 @@
return ret;
}
-uint32 read_le_uint32(ifstream &f) {
+uint32 read_le_uint32(std::ifstream &f) {
uint32 ret = 0;
ret |= f.get();
ret |= f.get() << 8;
@@ -44,14 +47,14 @@
return ret;
}
-uint16 read_le_uint16(ifstream &f) {
+uint16 read_le_uint16(std::ifstream &f) {
int ret = 0;
ret |= f.get();
ret |= f.get() << 8;
return (uint16) ret;
}
-int16 read_le_int16(ifstream &f) {
+int16 read_le_int16(std::ifstream &f) {
int ret = 0;
ret |= f.get();
ret |= f.get() << 8;
Modified: tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h 2009-06-23 18:36:24 UTC (rev 41815)
+++ tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h 2009-06-23 18:37:10 UTC (rev 41816)
@@ -13,10 +13,10 @@
public:
- void test_assignIntervals() {
+ void test_intervals() {
vector<IntNode*> nodes1;
IntGraph *g1 = makeGraph1(nodes1);
- g1->assignIntervals(nodes1[0]);
+ g1->intervals();
TS_ASSERT_EQUALS(nodes1[0]->interval()->_data, nodes1[0]->_data);
TS_ASSERT_EQUALS(nodes1[1]->interval()->_data, nodes1[1]->_data);
TS_ASSERT_EQUALS(nodes1[2]->interval()->_data, nodes1[1]->_data);
@@ -25,7 +25,7 @@
TS_ASSERT_EQUALS(nodes1[5]->interval()->_data, nodes1[1]->_data);
vector<IntNode*> nodes2;
IntGraph *g2 = makeGraph2(nodes2);
- g2->assignIntervals(nodes2[0]);
+ g2->intervals();
TS_ASSERT_EQUALS(nodes2[0]->interval()->_data, nodes2[0]->_data);
TS_ASSERT_EQUALS(nodes2[1]->interval()->_data, nodes2[0]->_data);
TS_ASSERT_EQUALS(nodes2[2]->interval()->_data, nodes2[0]->_data);
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