[Scummvm-cvs-logs] SF.net SVN: scummvm:[41923] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Sat Jun 27 23:34:13 CEST 2009
Revision: 41923
http://scummvm.svn.sourceforge.net/scummvm/?rev=41923&view=rev
Author: kjdf
Date: 2009-06-27 21:34:13 +0000 (Sat, 27 Jun 2009)
Log Message:
-----------
decompiler: all information about loops filled in
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.h
Modified: tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-06-27 16:48:47 UTC (rev 41922)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp 2009-06-27 21:34:13 UTC (rev 41923)
@@ -17,10 +17,10 @@
("disasm", "print disassembly and exit")
("blocks", "print basic blocks and exit")
("graph", "print graph and exit")
- ("derive", value<int>()->default_value(0), "find arg-th order intervals")
("fontname", value<string>()->default_value("Courier"), "font to use with graphical output");
options_description options("Allowed options");
options.add(visible).add_options()
+ ("derive", value<int>()->default_value(0), "find arg-th order intervals")
("inputfile", value<string>(), "input file");
positional_options_description pos;
pos.add("inputfile", 1);
@@ -52,12 +52,12 @@
cfg.printBasicBlocks(cout);
exit(0);
}
- // cfg.removeJumpsToJumps();
- // cfg.removeDeadBlocks();
+ cfg.removeJumpsToJumps();
cfg._graph.intervals();
if (vars.count("graph")) {
Graph<Block*> &g = cfg._graph;
- g.markReversePostOrder();
+ g.orderNodes();
+ cfg.removeDeadBlocks();
g.intervals();
for (int i = 0; i < vars["derive"].as<int>(); i++)
g.extendIntervals();
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-27 16:48:47 UTC (rev 41922)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-27 21:34:13 UTC (rev 41923)
@@ -18,6 +18,14 @@
#include <iostream>
+
+enum LoopType {
+ PRE_TESTED,
+ POST_TESTED,
+ ENDLESS
+};
+
+
template<typename Data>
struct Graph : boost::noncopyable {
@@ -38,14 +46,18 @@
friend class Graph;
- bool _visited;
Node *_interval;
std::list<Node*> _in;
std::list<Node*> _out;
- int _order;
- int _loop;
- Node(const Data &data) : _data(data), _interval(), _order(), _loop() {
+ int _number;
+
+ Node *_loopHead;
+ Node *_loopLatch;
+ Node *_loopFollow;
+ LoopType _loopType;
+
+ Node(const Data &data) : _data(data), _interval(), _number(), _loopHead(), _loopFollow() {
}
~Node() {
@@ -54,10 +66,9 @@
std::list<Node*> _nodes;
Node *_entry;
- int _currentOrder;
- int _currentLoop;
+ int _currentNumber;
- Graph() : _entry(), _currentOrder(), _currentLoop() {
+ Graph() : _entry(), _currentNumber() {
}
~Graph() {
@@ -91,13 +102,10 @@
node = newTo;
}
+ // to be called after order nodes
void removeUnreachableNodes() {
- foreach (Node *u, _nodes)
- u->_visited = false;
- assert(_entry);
- visit(_entry);
for (typename std::list<Node*>::iterator uit = _nodes.begin(); uit != _nodes.end(); )
- if ((*uit)->_visited)
+ if ((*uit)->_number)
uit++;
else {
foreach (Node *v, (*uit)->_out)
@@ -107,6 +115,21 @@
}
}
+ // assign node numbers in post-order
+ void orderNodes() {
+ assert(_entry);
+ orderVisit(_entry, 0);
+ }
+
+ int orderVisit(Node *u, int number) {
+ u->_number = -1;
+ foreach (Node *v, u->_out)
+ if (!v->_number)
+ number = orderVisit(v, number);
+ u->_number = ++number;
+ return number;
+ }
+
std::list<Node*> intervals() const {
std::list<Node*> ret;
assignIntervals();
@@ -116,28 +139,51 @@
return ret;
}
- // TODO: merge with removeUnreachableNodes?
- void markReversePostOrder() {
+ bool inLoop(Node *head, Node *latch, Node *u) {
+ return u->_interval == head && latch->_number <= u->_number && u->_number < head->_number;
+ }
+
+ LoopType loopType(Node *head, Node *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 (inLoop(head, latch, head->_out.front()))
+ return POST_TESTED;
+ else
+ return PRE_TESTED;
+ }
+
+ Node *loopFollow(Node *head, Node *latch) {
+ if (head->_loopType == PRE_TESTED)
+ return head->_out.front();
+ if (head->_loopType == POST_TESTED)
+ return latch->_out.back();
+ // ENDLESS
+ Node *ret = 0;
foreach (Node *u, _nodes)
- u->_visited = false;
- _currentOrder = _nodes.size();
- assert(_entry);
- visit(_entry);
+ if (inLoop(head, latch, u) && u->_out.size() == 2 && (!ret || ret->_number < u->_out.back()->_number))
+ ret = u->_out.back();
+ return ret;
}
void loopStruct() {
- foreach (Node *interval, intervals()) {
- foreach (Node *latch, interval->_in) {
- if (latch->_interval == interval) { // it *is* latching node not only by name :)
- if (!latch->_loop && !interval->_loop) {
- int curloop = ++_currentLoop;
+ for (size_t size = _nodes.size()+1; size > intervals().size(); size = intervals().size(), extendIntervals())
+ foreach (Node *interval, intervals()) {
+ foreach (Node *latch, interval->_in) {
+ if (latch->_interval == interval && !latch->_loopHead) {
foreach (Node *u, _nodes)
- if (interval->_order <= u->_order && u->_order <= latch->_order && u->_interval == interval)
- u->_loop = curloop;
+ if (inLoop(interval, latch, u))
+ u->_loopHead = interval;
+ interval->_loopLatch = latch; // TODO do we need this?
+ interval->_loopType = loopType(interval, latch);
+ interval->_loopFollow = loopFollow(interval, latch);
}
}
}
- }
}
void extendIntervals() {
@@ -173,34 +219,30 @@
<< "fontsize=" << fontsize << ",";
ret << "shape=box,"
<< "label=" << '"'
- << "<order: " << u->_order << ", "
- << "loop: " << u->_loop << ">\\n"
- << graphvizEscapeLabel(printer(u->_data))
- << '"'
+ << "<number: " << u->_number;
+ if (u->_loopFollow)
+ ret << ", loop_type=" << (u->_loopType == PRE_TESTED ? "pre_tested" : u->_loopType == POST_TESTED ? "post_tested" : "endless");
+ ret << ">\\n"
+ << graphvizEscapeLabel(printer(u->_data))
+ << '"'
<< "];" << std::endl;
}
ret << "}" << std::endl;
}
- foreach (Node *u, _nodes)
+ foreach (Node *u, _nodes) {
foreach (Node *v, u->_out)
- ret << '"' << u << '"'
- << " -> "
- << '"' << v << '"'
- << ";" << std::endl;
+ ret << '"' << u << '"'
+ << " -> "
+ << '"' << v << '"'
+ << (v == u->_loopFollow ? "[color=blue]" : "")
+ << ";" << std::endl;
+ }
ret << "}" << std::endl;
return ret.str();
}
private:
- void visit(Node *u) {
- u->_visited = true;
- foreach (Node *v, u->_out)
- if (!v->_visited)
- visit(v);
- u->_order = _currentOrder--;
- }
-
void assignIntervals() const {
std::list<Node*> intervals;
intervals.push_back(_entry);
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