[Scummvm-cvs-logs] SF.net SVN: scummvm:[41831] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Wed Jun 24 20:28:00 CEST 2009
Revision: 41831
http://scummvm.svn.sourceforge.net/scummvm/?rev=41831&view=rev
Author: kjdf
Date: 2009-06-24 18:28:00 +0000 (Wed, 24 Jun 2009)
Log Message:
-----------
decompiler: replace derive() with extendIntervals which preserves more information
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.h
tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h
Modified: tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-06-24 18:27:43 UTC (rev 41830)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-06-24 18:28:00 UTC (rev 41831)
@@ -17,7 +17,7 @@
("disasm", "print disassembly and exit")
("blocks", "print basic blocks and exit")
("graph", "print graph and exit")
- ("derive", value<int>(), "find nth derivative");
+ ("derive", value<int>()->default_value(0), "find arg-th order intervals");
options_description options("Allowed options");
options.add(visible).add_options()
("inputfile", value<string>(), "input file");
@@ -55,17 +55,10 @@
// cfg.removeDeadBlocks();
cfg._graph.intervals();
if (vars.count("graph")) {
- Graph<Block*> g = cfg._graph;
- cfg._graph = g;
- cfg.printDot(cout);
- exit(0);
- }
- if (vars.count("derive")) {
- Graph<Block*> g = cfg._graph;
- for (int i = 0; i < vars["derive"].as<int>(); i++)
- g = g.derive();
- cfg._graph = g; // FIXME: evil
+ Graph<Block*> &g = cfg._graph;
g.intervals();
+ for (int i = 0; i < vars["derive"].as<int>(); i++)
+ g.extendIntervals();
cfg.printDot(cout);
exit(0);
}
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-24 18:27:43 UTC (rev 41830)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-24 18:28:00 UTC (rev 41831)
@@ -29,17 +29,21 @@
return _out;
}
+ // wouldn't be needed if Graph<X> and Graph<Y> weren't totally alien classes
+ Node *interval() const {
+ return _interval;
+ }
+
private:
friend class Graph;
bool _visited;
Node *_interval;
- Node *_primitive;
std::list<Node*> _in;
std::list<Node*> _out;
- Node(const Data &data) : _data(data), _interval(), _primitive() {
+ Node(const Data &data) : _data(data), _interval() {
}
~Node() {
@@ -143,35 +147,23 @@
return ret;
}
- Graph derive() {
- assignIntervals();
- Graph g;
- std::map<Node*, Node*> trans;
+ void extendIntervals() {
+ Graph<Node*> d;
+ std::map<Node*, typename Graph<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;
+ if (u->_interval == u)
+ trans[u] = d.addNode(u->_interval);
+ foreach (Node *interval, intervals())
foreach (Node *u, interval->_in)
- if (u->_interval != interval && !contains(pred, u->_interval)) {
- pred.insert(u->_interval);
- g.addEdge(trans[u->_interval], trans[interval]);
- }
- }
- g.setEntry(trans[_entry]);
- return g;
+ if (u->_interval != interval)
+ d.addEdge(trans[u->_interval], trans[interval]);
+ d.intervals();
+ foreach (typename Graph<Node*>::Node *du, d._nodes)
+ foreach (Node *v, _nodes)
+ if (v->_interval == du->_data)
+ v->_interval = du->interval()->_data;
}
- // std::list<Graph> derivedSequence() {
- // std::list<Graph> ret;
- // ret.push_back(*this);
- // while (ret.back().derive().nodes().size() < ret.back().nodes().size())
- // ret.push_back(ret.back().derive());
- // return ret;
- // }
-
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 {
std::stringstream ret;
Modified: tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h 2009-06-24 18:27:43 UTC (rev 41830)
+++ tools/branches/gsoc2009-decompiler/decompiler/test/test_graph.h 2009-06-24 18:28:00 UTC (rev 41831)
@@ -20,7 +20,7 @@
class GraphTestSuite : public CxxTest::TestSuite {
- IntGraph g1, g2, g3;
+ IntGraph g1, g2, g3, g4;
public:
@@ -28,76 +28,56 @@
g1 = makeGraph1();
g2 = makeGraph2();
g3 = makeGraph3();
+ g4 = makeGraph4();
}
// this tests internal, intermediate results, not part of the api
void test_intervals() {
g1.intervals();
- TS_ASSERT_EQUALS(findNode(g1, 1)->_interval->_data, findNode(g1, 1)->_data);
- TS_ASSERT_EQUALS(findNode(g1, 2)->_interval->_data, findNode(g1, 2)->_data);
- TS_ASSERT_EQUALS(findNode(g1, 3)->_interval->_data, findNode(g1, 2)->_data);
- TS_ASSERT_EQUALS(findNode(g1, 4)->_interval->_data, findNode(g1, 2)->_data);
- TS_ASSERT_EQUALS(findNode(g1, 5)->_interval->_data, findNode(g1, 2)->_data);
- TS_ASSERT_EQUALS(findNode(g1, 6)->_interval->_data, findNode(g1, 2)->_data);
+ TS_ASSERT_EQUALS(findNode(g1, 1)->interval()->_data, findNode(g1, 1)->_data);
+ for (int i = 2; i <= 6; i++)
+ TS_ASSERT_EQUALS(findNode(g1, i)->interval()->_data, findNode(g1, 2)->_data);
g2.intervals();
- TS_ASSERT_EQUALS(findNode(g2, 1)->_interval->_data, findNode(g2, 1)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 2)->_interval->_data, findNode(g2, 1)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 3)->_interval->_data, findNode(g2, 1)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 4)->_interval->_data, findNode(g2, 1)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 5)->_interval->_data, findNode(g2, 1)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 6)->_interval->_data, findNode(g2, 6)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 7)->_interval->_data, findNode(g2, 6)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 8)->_interval->_data, findNode(g2, 6)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 9)->_interval->_data, findNode(g2, 6)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 10)->_interval->_data, findNode(g2, 6)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 11)->_interval->_data, findNode(g2, 6)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 12)->_interval->_data, findNode(g2, 6)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 13)->_interval->_data, findNode(g2, 13)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 14)->_interval->_data, findNode(g2, 13)->_data);
- TS_ASSERT_EQUALS(findNode(g2, 15)->_interval->_data, findNode(g2, 13)->_data);
+ for (int i = 1; i <= 5; i++)
+ TS_ASSERT_EQUALS(findNode(g2, i)->interval()->_data, findNode(g2, 1)->_data);
+ for (int i = 6; i <= 12; i++)
+ TS_ASSERT_EQUALS(findNode(g2, i)->interval()->_data, findNode(g2, 6)->_data);
+ for (int i = 13; i <= 15; i++)
+ TS_ASSERT_EQUALS(findNode(g2, i)->interval()->_data, findNode(g2, 13)->_data);
g3.intervals();
- TS_ASSERT_EQUALS(findNode(g3, 1)->_interval->_data, findNode(g3, 1)->_data);
- TS_ASSERT_EQUALS(findNode(g3, 2)->_interval->_data, findNode(g3, 2)->_data);
- TS_ASSERT_EQUALS(findNode(g3, 3)->_interval->_data, findNode(g3, 3)->_data);
+ TS_ASSERT_EQUALS(findNode(g3, 1)->interval()->_data, findNode(g3, 1)->_data);
+ TS_ASSERT_EQUALS(findNode(g3, 2)->interval()->_data, findNode(g3, 2)->_data);
+ TS_ASSERT_EQUALS(findNode(g3, 3)->interval()->_data, findNode(g3, 3)->_data);
+ g4.intervals();
+ TS_ASSERT_EQUALS(findNode(g4, 1)->interval()->_data, findNode(g4, 1)->_data);
+ TS_ASSERT_EQUALS(findNode(g4, 2)->interval()->_data, findNode(g4, 2)->_data);
+ TS_ASSERT_EQUALS(findNode(g4, 3)->interval()->_data, findNode(g4, 2)->_data);
}
- // this tests internal, intermediate results, not part of the api
- void test_derive() {
- IntGraph g1d = g1.derive();
- TS_ASSERT_EQUALS(g1d._nodes.size(), 2);
- TS_ASSERT(findNode(g1d, 1));
- TS_ASSERT(findNode(g1d, 2));
- TS_ASSERT_EQUALS(outEdgesCount(g1d, 1), 1);
- TS_ASSERT_EQUALS(outEdgesCount(g1d, 2), 1);
- TS_ASSERT(pointsTo(g1d, 1, 2));
- TS_ASSERT(pointsTo(g1d, 1, 2));
- IntGraph g1dd = g1d.derive();
- TS_ASSERT_EQUALS(g1dd._nodes.size(), 1);
- TS_ASSERT(findNode(g1d, 1));
- TS_ASSERT_EQUALS(outEdgesCount(g1dd, 1), 0);
- IntGraph g2d = g2.derive();
- TS_ASSERT_EQUALS(g2d._nodes.size(), 3);
- TS_ASSERT(findNode(g2d, 1));
- TS_ASSERT(findNode(g2d, 6));
- TS_ASSERT(findNode(g2d, 13));
- TS_ASSERT_EQUALS(outEdgesCount(g2d, 1), 1);
- TS_ASSERT_EQUALS(outEdgesCount(g2d, 6), 1);
- TS_ASSERT_EQUALS(outEdgesCount(g2d, 13), 1);
- TS_ASSERT(pointsTo(g2d, 1, 6));
- TS_ASSERT(pointsTo(g2d, 6, 13));
- TS_ASSERT(pointsTo(g2d, 13, 6));
- IntGraph g3d = g3.derive();
- TS_ASSERT_EQUALS(g3d._nodes.size(), 3);
- TS_ASSERT(findNode(g3d, 1));
- TS_ASSERT(findNode(g3d, 2));
- TS_ASSERT(findNode(g3d, 3));
- TS_ASSERT_EQUALS(outEdgesCount(g3d, 1), 2);
- TS_ASSERT_EQUALS(outEdgesCount(g3d, 2), 1);
- TS_ASSERT_EQUALS(outEdgesCount(g3d, 3), 1);
- TS_ASSERT(pointsTo(g3d, 1, 2));
- TS_ASSERT(pointsTo(g3d, 1, 3));
- TS_ASSERT(pointsTo(g3d, 2, 3));
- TS_ASSERT(pointsTo(g3d, 3, 2));
+ void test_extendIntervals() {
+ g1.intervals();
+ g1.extendIntervals();
+ for (int i = 1; i <= 6; i++)
+ TS_ASSERT_EQUALS(findNode(g1, i)->interval()->_data, findNode(g1, 1)->_data);
+ g2.intervals();
+ g2.extendIntervals();
+ for (int i = 1; i <= 5; i++)
+ TS_ASSERT_EQUALS(findNode(g2, i)->interval()->_data, findNode(g2, 1)->_data);
+ for (int i = 6; i <= 15; i++)
+ TS_ASSERT_EQUALS(findNode(g2, i)->interval()->_data, findNode(g2, 6)->_data);
+ g2.extendIntervals();
+ for (int i = 1; i <= 15; i++)
+ TS_ASSERT_EQUALS(findNode(g2, i)->interval()->_data, findNode(g2, 1)->_data);
+ g3.intervals();
+ g3.extendIntervals();
+ TS_ASSERT_EQUALS(findNode(g3, 1)->interval()->_data, findNode(g3, 1)->_data);
+ TS_ASSERT_EQUALS(findNode(g3, 2)->interval()->_data, findNode(g3, 2)->_data);
+ TS_ASSERT_EQUALS(findNode(g3, 3)->interval()->_data, findNode(g3, 3)->_data);
+ g4.intervals();
+ g4.extendIntervals();
+ TS_ASSERT_EQUALS(findNode(g4, 1)->interval()->_data, findNode(g4, 1)->_data);
+ TS_ASSERT_EQUALS(findNode(g4, 2)->interval()->_data, findNode(g4, 1)->_data);
+ TS_ASSERT_EQUALS(findNode(g4, 3)->interval()->_data, findNode(g4, 1)->_data);
}
private:
@@ -189,4 +169,16 @@
g.addEdge(findNode(g, 3), findNode(g, 2));
return g;
}
+
+ IntGraph makeGraph4() {
+ IntGraph g;
+ g.addNode(1);
+ g.addNode(2);
+ g.addNode(3);
+ g.addEdge(findNode(g, 1), findNode(g, 2));
+ g.addEdge(findNode(g, 2), findNode(g, 2));
+ g.addEdge(findNode(g, 2), findNode(g, 3));
+ g.addEdge(findNode(g, 3), findNode(g, 1));
+ return g;
+ }
};
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