[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