[Scummvm-cvs-logs] SF.net SVN: scummvm:[42309] tools/branches/gsoc2009-decompiler/decompiler

kjdf at users.sourceforge.net kjdf at users.sourceforge.net
Thu Jul 9 19:44:34 CEST 2009


Revision: 42309
          http://scummvm.svn.sourceforge.net/scummvm/?rev=42309&view=rev
Author:   kjdf
Date:     2009-07-09 17:44:32 +0000 (Thu, 09 Jul 2009)

Log Message:
-----------
decompiler: strongly connected components algorithm

Modified Paths:
--------------
    tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
    tools/branches/gsoc2009-decompiler/decompiler/graph.h

Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp	2009-07-09 17:25:06 UTC (rev 42308)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp	2009-07-09 17:44:32 UTC (rev 42309)
@@ -5,6 +5,7 @@
 using namespace std;
 
 
+void componentVisit(Block *u, Block *head);
 Block *dominatorIntersect(Block *u, Block *v);
 std::list<Block*> inPostOrder(std::list<Block*> &blocks);
 int orderVisit(Block *u, int number);
@@ -28,6 +29,15 @@
 }
 
 
+void ControlFlowGraph::assignComponents() {
+	orderBlocks();
+	std::list<Block*> blocks = inPostOrder(_blocks);
+	blocks.reverse();
+	foreach (Block *u, blocks)
+		componentVisit(u, u);
+}
+
+
 void ControlFlowGraph::assignDominators() {
 	std::list<Block*> blocks = inPostOrder(_blocks);
 	blocks.reverse();
@@ -84,6 +94,15 @@
 }
 
 
+void componentVisit(Block *u, Block *head) {
+	if (u->_component)
+		return;
+	u->_component = head;
+	foreach (Block *v, u->_in)
+		componentVisit(v, head);
+}
+
+
 Block *dominatorIntersect(Block *u, Block *v) {
 	while (u != v) {
 		while (u->_number < v->_number)
@@ -129,6 +148,14 @@
 	return ret;
 }
 
+std::list<Block*> ControlFlowGraph::components() {
+	std::list<Block*> ret;
+	assignComponents();
+	foreach (Block *u, _blocks)
+		if (u->_component == u)
+			ret.push_back(u);
+	return ret;
+}
 
 string ControlFlowGraph::graphvizToString(const std::string &fontname, int fontsize) {
 	std::stringstream ret;
@@ -260,6 +287,7 @@
 
 void ControlFlowGraph::orderBlocks() {
 	assert(_entry);
+	if (!_entry->_number)
 		orderVisit(_entry, 0);
 }
 

Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-09 17:25:06 UTC (rev 42308)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-09 17:44:32 UTC (rev 42309)
@@ -29,6 +29,7 @@
     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
+	Block *_component;
 	LoopType _loopType;
 	int _number;             // number in post-order
 	std::list<Block*> _in;
@@ -60,7 +61,7 @@
 		return 0;
 	}
 
-	Block() : _interval(), _number(), _loopHead(), _loopFollow(), _loopLatch(), _visited(), _dominator(), _ifFollow() {
+	Block() : _interval(), _number(), _loopHead(), _loopFollow(), _loopLatch(), _visited(), _dominator(), _ifFollow(), _component() {
 	}
 
 	~Block() {
@@ -116,6 +117,7 @@
 
 	void loopStruct();               // fill in all information about loops
 	std::list<Block*> intervals();   // partition graph into intervals and return list of header blocks
+	std::list<Block*> components();
 	void ifStruct();                 // fill in all information about if-then-else, must be called after loopStruct
 
 	void orderBlocks();              // assign block numbers in post-order
@@ -127,7 +129,8 @@
 	void assignIntervals();  // can be called multiple times
 	void extendIntervals();
 	bool isReducible();
-	void assignDominators();
+	void assignDominators(); // after order
+	void assignComponents(); // after order
 
 private:
 	LoopType loopType(Block *head, Block *latch);


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