[Scummvm-cvs-logs] SF.net SVN: scummvm:[42312] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Thu Jul 9 20:03:09 CEST 2009
Revision: 42312
http://scummvm.svn.sourceforge.net/scummvm/?rev=42312&view=rev
Author: kjdf
Date: 2009-07-09 18:03:09 +0000 (Thu, 09 Jul 2009)
Log Message:
-----------
decompiler: removed dysfunctional if-then-else detection
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/Makefile
tools/branches/gsoc2009-decompiler/decompiler/block.cpp
tools/branches/gsoc2009-decompiler/decompiler/block.h
tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.h
Modified: tools/branches/gsoc2009-decompiler/decompiler/Makefile
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/Makefile 2009-07-09 17:45:36 UTC (rev 42311)
+++ tools/branches/gsoc2009-decompiler/decompiler/Makefile 2009-07-09 18:03:09 UTC (rev 42312)
@@ -68,7 +68,8 @@
test:
cxxtest/cxxtestgen.pl --error-printer --abort-on-fail --have-eh -o test_runner.cpp test/test_*.h
- g++ -g $(DEFINES) $(INCLUDES) -Icxxtest -o test_runner test_runner.cpp graph.cpp misc.cpp
+ g++ -g $(DEFINES) $(INCLUDES) -Icxxtest -o test_runner test_runner.cpp graph.cpp misc.cpp block.cpp
+ rm test_runner.cpp
./test_runner
Modified: tools/branches/gsoc2009-decompiler/decompiler/block.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/block.cpp 2009-07-09 17:45:36 UTC (rev 42311)
+++ tools/branches/gsoc2009-decompiler/decompiler/block.cpp 2009-07-09 18:03:09 UTC (rev 42312)
@@ -10,35 +10,13 @@
#endif
-Block::Block() : _interval(), _number(), _loopHead(), _loopFollow(), _loopLatch(), _visited(), _dominator(), _ifFollow(), _component() {
+Block::Block() : _interval(), _number(), _dominator(), _component() {
}
Block::~Block() {
}
-
-bool Block::inLoop(Block *head) {
- return _interval == head && head->_loopLatch->_number <= _number && _number < head->_number;
-}
-
-
-Block *Block::nonFollowEdge() {
- foreach (Block *u, _out)
- if (u != _loopFollow)
- return u;
- return 0;
-}
-
-
-Block *Block::outEdgeOutsideLoop(Block *head) {
- foreach (Block *u, _out)
- if (!u->inLoop(head) && u != head)
- return u;
- return 0;
-}
-
-
string Block::toString() {
ostringstream ret;
foreach (Instruction *instruction, _instructions)
Modified: tools/branches/gsoc2009-decompiler/decompiler/block.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/block.h 2009-07-09 17:45:36 UTC (rev 42311)
+++ tools/branches/gsoc2009-decompiler/decompiler/block.h 2009-07-09 18:03:09 UTC (rev 42312)
@@ -8,25 +8,13 @@
#include <boost/utility.hpp>
-enum LoopType {
- PRE_TESTED,
- POST_TESTED,
- ENDLESS
-};
-
-
struct Block : boost::noncopyable {
bool _visited;
Block *_dominator; // immediate dominator
- Block *_ifFollow; // block is header node for if, branches converge at _ifFollow
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 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;
std::list<Block*> _out;
@@ -34,9 +22,6 @@
Block();
~Block();
- bool inLoop(Block *head);
- Block *nonFollowEdge();
- Block *outEdgeOutsideLoop(Block *head);
std::string toString();
};
Modified: tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-09 17:45:36 UTC (rev 42311)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-07-09 18:03:09 UTC (rev 42312)
@@ -23,7 +23,7 @@
("disasm", "print disassembly")
("blocks", "print basic blocks")
("graph-intervals", value<unsigned>(), "print arg-th graph intervals")
- ("graph-struct", "print graph with marked structure information")
+ // ("graph-struct", "print graph with marked structure information")
// ("decompile", "print decompiled program and exit")
("no-remove-jumps", "don't remove jumps-to-jumps")
("fontname", value<string>()->default_value("Courier"), "font to use with dot output");
@@ -81,11 +81,5 @@
cout << cfg.graphvizToString(vars["fontname"].as<string>());
exit(0);
}
- cfg.loopStruct();
- cfg.ifStruct();
- if (vars.count("graph-struct")) {
- cout << cfg.graphvizToString(vars["fontname"].as<string>());
- exit(0);
- }
return 0;
}
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-09 17:45:36 UTC (rev 42311)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-09 18:03:09 UTC (rev 42312)
@@ -228,48 +228,18 @@
ret << "shape=box,label=\"<number=" << u->_number;
if (u->_dominator)
ret << ", dom=" << u->_dominator->_number;
- if (u->_loopFollow)
- ret << ", loop_type=" << (u->_loopType == PRE_TESTED ? "pre_tested" : u->_loopType == POST_TESTED ? "post_tested" : "endless");
ret << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << endl;
}
ret << "}" << endl;
}
- foreach (Block *u, _blocks) {
- bool hadFollow = false;
- foreach (Block *v, u->_out) {
- hadFollow |= v == u->_loopFollow;
- ret << '"' << u << "\" -> \"" << v << '"' << (v == u->_loopFollow ? "[color=blue]" : "") << ";" << endl;
- }
- if (u->_loopFollow && !hadFollow)
- ret << '"' << u << "\" -> \"" << u->_loopFollow << '"' << "[color=blue,style=dashed];" << endl;
- if (u->_ifFollow)
- ret << '"' << u << "\" -> \"" << u->_ifFollow << '"' << "[color=red,style=dashed];" << endl;
- }
+ foreach (Block *u, _blocks)
+ foreach (Block *v, u->_out)
+ ret << '"' << u << "\" -> \"" << v << '"' << ";" << endl;
ret << "}" << endl;
return ret.str();
}
-void ControlFlowGraph::ifStruct() {
- list<Block*> unresolved;
- foreach (Block *u, inPostOrder(_blocks))
- // TODO how will this work with 2-way head and 2-way latch loops - on latch node? how are loops going to be structured anyway
- if (u->_out.size() == 2 && !((u->_loopLatch && u->_loopType == PRE_TESTED) || u->_loopHead)) {
- Block *follow = 0;
- // find the deepest node with immediate dominator u
- foreach (Block *v, _blocks)
- if (v->_dominator == u && v->_in.size() >= 2 && (!follow || v->_number < follow->_number))
- follow = v;
- unresolved.push_back(u);
- if (follow) {
- foreach (Block *v, unresolved)
- v->_ifFollow = follow;
- unresolved.clear();
- }
- }
-}
-
-
list<Block*> ControlFlowGraph::intervals() {
list<Block*> ret;
assignIntervals();
@@ -287,53 +257,6 @@
}
-Block *ControlFlowGraph::loopFollow(Block *head, Block *latch) {
- if (head->_loopType == PRE_TESTED)
- return head->outEdgeOutsideLoop(head);
- if (head->_loopType == POST_TESTED)
- return latch->outEdgeOutsideLoop(head);
- // ENDLESS
- Block *ret = 0;
- foreach (Block *u, _blocks)
- 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
-// (inner loops)
-void ControlFlowGraph::loopStruct() {
- for (size_t size = _blocks.size()+1; size > intervals().size(); size = intervals().size(), extendIntervals())
- foreach (Block *interval, intervals()) {
- foreach (Block *latch, interval->_in) {
- if (latch->_interval == interval && !latch->_loopHead) {
- 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;
- if (head->_out.size() == 1 && latch->_out.size() == 2)
- return POST_TESTED;
- if (head->_out.size() == 2 && latch->_out.size() == 1)
- return PRE_TESTED;
- // head->_out.size() == 2 && latch->_out.size() == 2
- if (!head->outEdgeOutsideLoop(head))
- return POST_TESTED;
- else
- return PRE_TESTED;
-}
-
-
void ControlFlowGraph::orderBlocks() {
assert(_entry);
if (!_entry->_number)
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-09 17:45:36 UTC (rev 42311)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-09 18:03:09 UTC (rev 42312)
@@ -38,12 +38,8 @@
// to be removed
void assignIntervals();
void extendIntervals();
- void ifStruct(); // after loopStruct
std::list<Block*> intervals();
bool isReducible();
- Block *loopFollow(Block *head, Block *latch);
- void loopStruct();
- LoopType loopType(Block *head, Block *latch);
};
#endif
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