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

[kjdf at users.sourceforge.net]

Revision: 42315
          http://scummvm.svn.sourceforge.net/scummvm/?rev=42315&view=rev
Author:   kjdf
Date:     2009-07-09 21:46:03 +0000 (Thu, 09 Jul 2009)

Log Message:
-----------
decompiler: stronglyConnectedComponents, componentEntryPoints

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 19:25:09 UTC (rev 42314)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp	2009-07-09 21:46:03 UTC (rev 42315)
@@ -13,12 +13,12 @@
 #endif
 
 
-void componentVisit(Node *u, Node *head) {
-	if (u->_component)
-		return;
-	u->_component = head;
+void componentVisit(Node *u, Node *representative, list<Node*> &component) {
+	u->_component = representative;
+	component.push_back(u);
 	foreach (Node *v, u->_in)
-		componentVisit(v, head);
+		if (!v->_component)
+			componentVisit(v, representative, component);
 }
 
 
@@ -33,6 +33,17 @@
 }
 
 
+string graphvizEscapeLabel(const string &s) {
+	string ret;
+	foreach (char c, s) {
+		if (c == '\n' || c == '"' || c == '\\')
+			ret.push_back('\\');
+		ret.push_back(c == '\n' ? 'l' : c);   // align lines to the left
+	}
+	return ret;
+}
+
+
 bool postOrderCompare(Node *a, Node *b) {
 	return a->_number < b->_number;
 }
@@ -98,15 +109,6 @@
 }
 
 
-void ControlFlowGraph::assignComponents() {
-	orderNodes();
-	list<Node*> nodes = inPostOrder(_nodes);
-	nodes.reverse();
-	foreach (Node *u, nodes)
-		componentVisit(u, u);
-}
-
-
 void ControlFlowGraph::assignDominators() {
 	list<Node*> nodes = inPostOrder(_nodes);
 	nodes.reverse();
@@ -163,6 +165,18 @@
 }
 
 
+std::list<Node*> ControlFlowGraph::componentEntryPoints(std::list<Node*> &component) {
+	std::list<Node*> ret;
+	foreach (Node *u, component)
+		foreach (Node *v, u->_in)
+			if (u->_component != v->_component) {
+				ret.push_back(u);
+				break;
+			}
+	return ret;
+}
+
+
 // 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
@@ -187,25 +201,6 @@
 }
 
 
-string graphvizEscapeLabel(const string &s) {
-	string ret;
-	foreach (char c, s) {
-		if (c == '\n' || c == '"' || c == '\\')
-			ret.push_back('\\');
-		ret.push_back(c == '\n' ? 'l' : c);   // align lines to the left
-	}
-	return ret;
-}
-
-list<Node*> ControlFlowGraph::components() {
-	list<Node*> ret;
-	assignComponents();
-	foreach (Node *u, _nodes)
-		if (u->_component == u)
-			ret.push_back(u);
-	return ret;
-}
-
 string ControlFlowGraph::graphvizToString(const string &fontname, int fontsize) {
 	stringstream ret;
 	ret << "digraph G {" << endl;
@@ -307,3 +302,18 @@
 		if (node->address() == entry)
 			_entry = node;
 }
+
+
+list< list<Node*> > ControlFlowGraph::stronglyConnectedComponents() {
+	list< list<Node*> > ret;
+	orderNodes();
+	list<Node*> nodes = inPostOrder(_nodes);
+	nodes.reverse();
+	foreach (Node *u, nodes)
+		if (!u->_component) {
+			list<Node*> component;
+			componentVisit(u, u, component);
+			ret.push_back(component);
+		}
+	return ret;
+}

Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-09 19:25:09 UTC (rev 42314)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-09 21:46:03 UTC (rev 42315)
@@ -24,15 +24,15 @@
 
 	void addBasicBlocksFromScript(std::list<Instruction*>::iterator scriptBegin, std::list<Instruction*>::iterator scriptEnd);
 	void addEdge(Node *from, Node *to);
-	void assignComponents(); // after order
 	void assignDominators(); // after order
-	std::list<Node*> components();
+	static std::list<Node*> componentEntryPoints(std::list<Node*> &component);
 	std::string graphvizToString(const std::string &fontname="", int fontsize=0);
 	void orderNodes();
 	void removeJumpsToJumps();
 	void removeUnreachableNodes(); // after order
 	void replaceEdges(Node *from, Node *oldTo, Node *newTo);
 	void setEntry(address_t entry);
+	std::list< std::list<Node*> > stronglyConnectedComponents();
 
 	// to be removed
 	void assignIntervals();


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.