[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