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

kjdf at users.sourceforge.net kjdf at users.sourceforge.net
Thu Jul 2 18:04:45 CEST 2009


Revision: 42028
          http://scummvm.svn.sourceforge.net/scummvm/?rev=42028&view=rev
Author:   kjdf
Date:     2009-07-02 16:04:45 +0000 (Thu, 02 Jul 2009)

Log Message:
-----------
decompiler: loop detections are now insensitive to edge ordering (which may change after removal
of jumps to jumps)

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-02 16:04:32 UTC (rev 42027)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp	2009-07-02 16:04:45 UTC (rev 42028)
@@ -116,11 +116,6 @@
 }
 
 
-bool ControlFlowGraph::inLoop(Block *head, Block *latch, Block *u) {
-	return u->_interval == head && latch->_number <= u->_number && u->_number < head->_number;
-}
-
-
 list<Block*> ControlFlowGraph::intervals() {
 	std::list<Block*> ret;
 	assignIntervals();
@@ -133,18 +128,17 @@
 
 Block *ControlFlowGraph::loopFollow(Block *head, Block *latch) {
 	if (head->_loopType == PRE_TESTED)
-		return head->_out.front();
+		return head->outEdgeOutsideLoop(head);
 	if (head->_loopType == POST_TESTED)
-		return latch->_out.back();
+		return latch->outEdgeOutsideLoop(head);
 	// ENDLESS
 	Block *ret = 0;
 	foreach (Block *u, _blocks)
-		if (inLoop(head, latch, u) && u->_out.size() == 2 && (!ret || ret->_number < u->_out.back()->_number))
-			ret = u->_out.back();
+		if (u->inLoop(head) && u->outEdgeOutsideLoop(head) && (!ret || ret->_number < u->outEdgeOutsideLoop(head)->_number))
+			ret = u->outEdgeOutsideLoop(head);
 	return ret;
 }
 
-
 // for each set of 'growing' intervals in derived sequence of graphs,
 // every interval header is a potential loop header
 // we check for back edges that don't belong to loops discovered earlier
@@ -154,18 +148,15 @@
 		foreach (Block *interval, intervals()) {
 			foreach (Block *latch, interval->_in) {
 				if (latch->_interval == interval && !latch->_loopHead) {
-					foreach (Block *u, _blocks)
-						if (inLoop(interval, latch, u))
-							u->_loopHead = interval;
-					interval->_loopLatch = latch; // TODO do we need this?
+					interval->_loopLatch = latch;
 					interval->_loopType = loopType(interval, latch);
 					interval->_loopFollow = loopFollow(interval, latch);
+					latch->_loopHead = interval;
 				}
 			}
 		}
 }
 
-
 LoopType ControlFlowGraph::loopType(Block *head, Block *latch) {
 	if (head->_out.size() == 1 && latch->_out.size() == 1)
 		return ENDLESS;
@@ -174,7 +165,7 @@
 	if (head->_out.size() == 2 && latch->_out.size() == 1)
 		return PRE_TESTED;
 	// head->_out.size() == 2 && latch->_out.size() == 2
-	if (inLoop(head, latch, head->_out.front()))
+	if (!head->outEdgeOutsideLoop(head))
 		return POST_TESTED;
 	else
 		return PRE_TESTED;

Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-02 16:04:32 UTC (rev 42027)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-02 16:04:45 UTC (rev 42028)
@@ -11,6 +11,7 @@
 #include "instruction.h"
 #include "misc.h"
 
+
 enum LoopType {
 	PRE_TESTED,
 	POST_TESTED,
@@ -22,7 +23,7 @@
 
 	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 block belongs to a loop
+    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;
@@ -38,6 +39,17 @@
 		return ret.str();
 	}
 
+	bool inLoop(Block *head) {
+		return _interval == head && head->_loopLatch->_number <= _number && _number <= head->_number;
+	}
+
+	Block *outEdgeOutsideLoop(Block *head) {
+		foreach (Block *u, _out)
+			if (!u->inLoop(head))
+				return u;
+		return 0;
+	}
+
 	Block() : _interval(), _number(), _loopHead(), _loopFollow() {
 	}
 
@@ -105,7 +117,6 @@
 private:
 	LoopType loopType(Block *head, Block *latch);
 	Block *loopFollow(Block *head, Block *latch);     // to be called after loopType
-	bool inLoop(Block *head, Block *latch, Block *u);
 
 	void addEdge(Block *from, Block *to);
 


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