[Scummvm-cvs-logs] SF.net SVN: scummvm:[42064] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Fri Jul 3 18:31:25 CEST 2009
Revision: 42064
http://scummvm.svn.sourceforge.net/scummvm/?rev=42064&view=rev
Author: kjdf
Date: 2009-07-03 16:31:25 +0000 (Fri, 03 Jul 2009)
Log Message:
-----------
decompiler: dominator tree algorithm
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/test/test_graph_internal.h
Modified: tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-03 16:29:56 UTC (rev 42063)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-03 16:31:25 UTC (rev 42064)
@@ -61,6 +61,7 @@
cfg.removeJumpsToJumps();
cfg.orderBlocks();
cfg.removeUnreachableBlocks();
+ cfg.assignDominators();
if (vars.count("graph-intervals")) {
cfg.assignIntervals();
for (unsigned i = 0; i < vars["graph-intervals"].as<unsigned>(); i++)
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-03 16:29:56 UTC (rev 42063)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-03 16:31:25 UTC (rev 42064)
@@ -5,7 +5,13 @@
using namespace std;
+Block *dominatorIntersect(Block *u, Block *v);
+std::list<Block*> inPostOrder(std::list<Block*> &blocks);
+int orderVisit(Block *u, int number);
+bool postOrderCompare(Block *a, Block *b);
+
+
ControlFlowGraph::ControlFlowGraph() : _entry() {
}
@@ -22,6 +28,29 @@
}
+void ControlFlowGraph::assignDominators() {
+ std::list<Block*> blocks = inPostOrder(_blocks);
+ blocks.reverse();
+ blocks.remove(_entry);
+ _entry->_dominator = _entry;
+ for (bool changed = true; changed; ) {
+ changed = false;
+ foreach (Block *u, blocks) {
+ std::list<Block*>::iterator it = u->_in.begin();
+ Block *dom = *it++;
+ for (; it != u->_in.end(); it++)
+ if ((*it)->_dominator)
+ dom = dominatorIntersect(*it, dom);
+ if (u->_dominator != dom) {
+ changed = true;
+ u->_dominator = dom;
+ }
+ }
+ }
+ _entry->_dominator = 0;
+}
+
+
// entry node is an interval header
// a node belongs to an interval, if all its immediate predecessors belong the given interval
// otherwise it is an interval header
@@ -53,6 +82,17 @@
}
+Block *dominatorIntersect(Block *u, Block *v) {
+ while (u != v) {
+ while (u->_number < v->_number)
+ u = u->_dominator;
+ while (v->_number < u->_number)
+ v = v->_dominator;
+ }
+ return u;
+}
+
+
// 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
@@ -101,7 +141,9 @@
ret << "fontname=" << '"' << fontname << "\",";
if (fontsize != 0)
ret << "fontsize=" << fontsize << ",";
- ret << "shape=box,label=\"<number: " << u->_number;
+ ret << "shape=box,label=\"<number=" << u->_number;
+ if (u->_dominator)
+ ret << ", dom=" << u->_dominator->_number;
if (u->_loopFollow)
ret << ", loop_type=" << (u->_loopType == PRE_TESTED ? "pre_tested" : u->_loopType == POST_TESTED ? "post_tested" : "endless");
ret << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << std::endl;
@@ -122,6 +164,13 @@
}
+std::list<Block*> inPostOrder(std::list<Block*> &blocks) {
+ std::list<Block*> ret(blocks);
+ ret.sort(postOrderCompare);
+ return ret;
+}
+
+
list<Block*> ControlFlowGraph::intervals() {
std::list<Block*> ret;
assignIntervals();
@@ -184,7 +233,7 @@
}
-int ControlFlowGraph::orderVisit(Block *u, int number) {
+int orderVisit(Block *u, int number) {
u->_number = -1;
foreach (Block *v, u->_out)
if (!v->_number)
@@ -194,6 +243,11 @@
}
+bool postOrderCompare(Block *a, Block *b) {
+ return a->_number < b->_number;
+}
+
+
void ControlFlowGraph::removeJumpsToJumps() {
for (bool changed = true; changed; ) {
changed = false;
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-03 16:29:56 UTC (rev 42063)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-03 16:31:25 UTC (rev 42064)
@@ -22,13 +22,14 @@
struct Block : boost::noncopyable {
bool _visited;
+ Block *_dominator; // immediate dominator
Block *_interval; // header node of the interval this block belongs to
Block *_loopFollow; // if not null, this block is a loop header, and follow is a first block after exit
Block *_loopHead; // if not null, this is a latching block
Block *_loopLatch; // if not null, this block is a loop header, and latch is the last block in the loop
Block *_primitive; // interval header of the graph from which this graph has been derived
LoopType _loopType;
- int _number; // number in reverse post-order
+ int _number; // number in post-order
std::list<Block*> _in;
std::list<Block*> _out;
std::list<Instruction*> _instructions;
@@ -58,7 +59,7 @@
return 0;
}
- Block() : _interval(), _number(), _loopHead(), _loopFollow(), _loopLatch(), _visited() {
+ Block() : _interval(), _number(), _loopHead(), _loopFollow(), _loopLatch(), _visited(), _dominator() {
}
~Block() {
@@ -123,6 +124,7 @@
void assignIntervals(); // can be called multiple times
void extendIntervals();
+ void assignDominators();
private:
LoopType loopType(Block *head, Block *latch);
@@ -131,7 +133,6 @@
void addEdge(Block *from, Block *to);
static std::string graphvizEscapeLabel(const std::string &s);
- int orderVisit(Block *u, int number); // visit blocks recursively, depth first, helper for orderBlocks
void replaceEdges(Block *from, Block *oldTo, Block *newTo);
};
Modified: tools/branches/gsoc2009-decompiler/decompiler/test/test_graph_internal.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/test/test_graph_internal.h 2009-07-03 16:29:56 UTC (rev 42063)
+++ tools/branches/gsoc2009-decompiler/decompiler/test/test_graph_internal.h 2009-07-03 16:31:25 UTC (rev 42064)
@@ -80,6 +80,48 @@
TS_ASSERT_EQUALS(addr(node(gd,2)->_interval), 1);
TS_ASSERT_EQUALS(addr(node(gd,3)->_interval), 1);
}
+
+
+ void test_assignDominators() {
+ ga->orderBlocks();
+ ga->assignDominators();
+ TS_ASSERT(!node(ga,1)->_dominator);
+ TS_ASSERT_EQUALS(addr(node(ga,2)->_dominator), 1);
+ TS_ASSERT_EQUALS(addr(node(ga,3)->_dominator), 2);
+ TS_ASSERT_EQUALS(addr(node(ga,4)->_dominator), 3);
+ TS_ASSERT_EQUALS(addr(node(ga,5)->_dominator), 2);
+ TS_ASSERT_EQUALS(addr(node(ga,6)->_dominator), 5);
+
+ gb->orderBlocks();
+ gb->assignDominators();
+ TS_ASSERT(!node(gb,1)->_dominator);
+ TS_ASSERT_EQUALS(addr(node(gb,2)->_dominator), 1);
+ TS_ASSERT_EQUALS(addr(node(gb,3)->_dominator), 2);
+ TS_ASSERT_EQUALS(addr(node(gb,4)->_dominator), 2);
+ TS_ASSERT_EQUALS(addr(node(gb,5)->_dominator), 1);
+ TS_ASSERT_EQUALS(addr(node(gb,6)->_dominator), 5);
+ TS_ASSERT_EQUALS(addr(node(gb,7)->_dominator), 6);
+ TS_ASSERT_EQUALS(addr(node(gb,8)->_dominator), 7);
+ TS_ASSERT_EQUALS(addr(node(gb,9)->_dominator), 8);
+ TS_ASSERT_EQUALS(addr(node(gb,10)->_dominator), 9);
+ TS_ASSERT_EQUALS(addr(node(gb,11)->_dominator), 6);
+ TS_ASSERT_EQUALS(addr(node(gb,12)->_dominator), 11);
+ TS_ASSERT_EQUALS(addr(node(gb,13)->_dominator), 11);
+ TS_ASSERT_EQUALS(addr(node(gb,14)->_dominator), 11);
+ TS_ASSERT_EQUALS(addr(node(gb,15)->_dominator), 14);
+
+ gc->orderBlocks();
+ gc->assignDominators();
+ TS_ASSERT(!node(gc,1)->_dominator);
+ TS_ASSERT_EQUALS(addr(node(gc,2)->_dominator), 1);
+ TS_ASSERT_EQUALS(addr(node(gc,3)->_dominator), 1);
+
+ gd->orderBlocks();
+ gd->assignDominators();
+ TS_ASSERT(!node(gd,1)->_dominator);
+ TS_ASSERT_EQUALS(addr(node(gd,2)->_dominator), 1);
+ TS_ASSERT_EQUALS(addr(node(gd,3)->_dominator), 2);
+ }
};
#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