[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