[Scummvm-cvs-logs] SF.net SVN: scummvm:[41674] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Fri Jun 19 15:30:03 CEST 2009
Revision: 41674
http://scummvm.svn.sourceforge.net/scummvm/?rev=41674&view=rev
Author: kjdf
Date: 2009-06-19 13:30:00 +0000 (Fri, 19 Jun 2009)
Log Message:
-----------
decompiler: graph intervals
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/decompiler.cc
tools/branches/gsoc2009-decompiler/decompiler/graph.h
Added Paths:
-----------
tools/branches/gsoc2009-decompiler/decompiler/intv.cc
Removed Paths:
-------------
tools/branches/gsoc2009-decompiler/decompiler/decompiler.rb
tools/branches/gsoc2009-decompiler/decompiler/test.cc
Modified: tools/branches/gsoc2009-decompiler/decompiler/decompiler.cc
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cc 2009-06-19 11:56:00 UTC (rev 41673)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cc 2009-06-19 13:30:00 UTC (rev 41674)
@@ -49,8 +49,9 @@
cfg.printBasicBlocks(cout);
exit(0);
}
- cfg.removeJumpsToJumps();
- cfg.removeDeadBlocks();
+ // cfg.removeJumpsToJumps();
+ // cfg.removeDeadBlocks();
+ cfg._graph.assignIntervals(cfg._nodes[0]);
if (vars.count("graph")) {
cfg.printDot(cout);
exit(0);
Deleted: tools/branches/gsoc2009-decompiler/decompiler/decompiler.rb
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.rb 2009-06-19 11:56:00 UTC (rev 41673)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.rb 2009-06-19 13:30:00 UTC (rev 41674)
@@ -1,43 +0,0 @@
-#! /usr/bin/env ruby
-
-require 'getoptlong'
-require 'tempfile'
-
-$image_viewer = 'eog -n'
-
-def usage
- puts "decompiler.rb [--graph] file.dmp"
-end
-
-def graph filename
- tmpfile = Tempfile.new 'decompiler'
- system "./decompiler -graph #{filename} | dot -T svg -o #{tmpfile.path}"
- system `#{$image_viewer} #{tmpfile.path}`
-end
-
-
-opts = GetoptLong.new(['--disasm', '-d', GetoptLong::NO_ARGUMENT],
- ['--blocks', '-b', GetoptLong::NO_ARGUMENT],
- ['--graph', '-g', GetoptLong::NO_ARGUMENT])
-
-if ARGV.size < 1
- usage
- exit
-end
-
-for opt, arg in opts
- case opt
- when '--help'
- usage
- exit
- when '--disasm'
- system "./decompiler -disasm #{ARGV[0]}"
- exit
- when '--blocks'
- system "./decompiler -blocks #{ARGV[0]}"
- exit
- when '--graph'
- graph ARGV[0]
- exit
- end
-end
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-19 11:56:00 UTC (rev 41673)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-06-19 13:30:00 UTC (rev 41674)
@@ -2,6 +2,7 @@
#define GRAPH_H
#include <list>
+#include <set>
#include <sstream>
#include <boost/foreach.hpp>
@@ -29,15 +30,16 @@
std::list<Node*> _out;
bool _hidden;
bool _visited;
+ Node *_interval;
- Node(const Data &data) : _data(data), _hidden(false) {
+ Node(const Data &data) : _data(data), _hidden(false), _interval(0) {
}
~Node() {
}
};
- std::list<Node*> _nodes;
+ mutable std::list<Node*> _nodes;
Graph() {
}
@@ -53,7 +55,7 @@
return node;
}
- void hideNode(Node *u) {
+ void removeNode(Node *u) {
foreach (Node *v, u->_in)
v->_out.remove(u);
foreach (Node *v, u->_out)
@@ -75,46 +77,91 @@
node = newTo;
}
- void visit(Node *u) {
- u->_visited = true;
- foreach (Node *v, u->_out)
- if (!v->_visited)
- visit(v);
- }
-
void removeUnreachableNodes(Node *start) {
foreach (Node *u, _nodes)
u->_visited = false;
visit(start);
foreach (Node *u, _nodes)
if (!u->_visited)
- hideNode(u);
+ removeNode(u);
}
+ void assignIntervals(Node *start) {
+ std::list<Node*> intervals;
+ intervals.push_back(start);
+ foreach (Node *interval, intervals) {
+ interval->_interval = interval;
+ for (bool added = true; added; ) {
+ added = false;
+ foreach (Node *m, _nodes) {
+ bool allPredInInterval = true;
+ foreach (Node *p, m->_in)
+ allPredInInterval &= p->_interval == interval;
+ if (!m->_interval && allPredInInterval) {
+ added = true;
+ m->_interval = interval;
+ }
+ }
+ }
+ foreach (Node *m, _nodes) {
+ bool hasPredInInterval = false;
+ foreach (Node *p, m->_in)
+ hasPredInInterval |= p->_interval == interval;
+ if (!m->_interval && hasPredInInterval)
+ intervals.push_back(m);
+ }
+ }
+ }
+
template<typename Printer> // printer is a functor taking Data and returning a string
std::string graphvizPrint(Printer printer, const std::string &fontname="Courier", int fontsize=14) const {
std::stringstream ret;
ret << "digraph G {" << std::endl;
+ removeHiddenNodes();
+ std::set<Node*> intervals;
foreach (Node *u, _nodes)
- if (!u->_hidden) {
- ret << '"' << u << '"'
- << "[fontname=" << '"' << fontname << '"'
- << ",fontsize=" << fontsize
- << ",shape=box"
- << ",label=" << '"' << graphvizEscapeLabel(printer(u->_data)) << '"'
- << "];" << std::endl;
- foreach (Node *v, u->_out)
+ intervals.insert(u->_interval);
+ foreach (Node *interval, intervals) {
+ ret << "subgraph " << '"' << "cluster_" << interval << '"' << " {" << std::endl;
+ ret << "style=dotted;" << std::endl;
+ foreach (Node *u, _nodes)
+ if (u->_interval == interval)
ret << '"' << u << '"'
- << " -> "
- << '"' << v << '"'
- << ";" << std::endl;
- }
+ << "[fontname=" << '"' << fontname << '"'
+ << ",fontsize=" << fontsize
+ << ",shape=box"
+ << ",label=" << '"' << graphvizEscapeLabel(printer(u->_data)) << '"'
+ << "];" << std::endl;
+ ret << "}" << std::endl;
+ }
+ foreach (Node *u, _nodes)
+ foreach (Node *v, u->_out)
+ ret << '"' << u << '"'
+ << " -> "
+ << '"' << v << '"'
+ << ";" << 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);
+ }
+
+ void removeHiddenNodes() const {
+ for (typename std::list<Node*>::iterator it = _nodes.begin(); it != _nodes.end(); )
+ if ((*it)->_hidden) {
+ delete *it;
+ it = _nodes.erase(it);
+ } else
+ it++;
+ }
+
static std::string graphvizEscapeLabel(const std::string &s) {
std::string ret;
foreach (char c, s) {
Added: tools/branches/gsoc2009-decompiler/decompiler/intv.cc
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/intv.cc (rev 0)
+++ tools/branches/gsoc2009-decompiler/decompiler/intv.cc 2009-06-19 13:30:00 UTC (rev 41674)
@@ -0,0 +1,76 @@
+#include <iostream>
+using namespace std;
+
+#include "graph.h"
+
+typedef Graph<int> graph;
+typedef graph::Node *node;
+
+
+string printer(int i) {
+ ostringstream ret;
+ ret << i;
+ return ret.str();
+}
+
+int main1() {
+ graph g;
+ node n1 = g.addNode(1);
+ node n2 = g.addNode(2);
+ node n3 = g.addNode(3);
+ node n4 = g.addNode(4);
+ node n5 = g.addNode(5);
+ node n6 = g.addNode(6);
+ g.addEdge(n1, n2);
+ g.addEdge(n2, n3);
+ g.addEdge(n2, n5);
+ g.addEdge(n3, n4);
+ g.addEdge(n4, n2);
+ g.addEdge(n5, n1);
+ g.addEdge(n5, n6);
+ g.assignIntervals(n1);
+ cout << g.graphvizPrint(printer);
+ return 0;
+}
+
+int main() {
+ graph g;
+ node n1 = g.addNode(1);
+ node n2 = g.addNode(2);
+ node n3 = g.addNode(3);
+ node n4 = g.addNode(4);
+ node n5 = g.addNode(5);
+ node n6 = g.addNode(6);
+ node n7 = g.addNode(7);
+ node n8 = g.addNode(8);
+ node n9 = g.addNode(9);
+ node n10 = g.addNode(10);
+ node n11 = g.addNode(11);
+ node n12 = g.addNode(12);
+ node n13 = g.addNode(13);
+ node n14 = g.addNode(14);
+ node n15 = g.addNode(15);
+ g.addEdge(n1, n2);
+ g.addEdge(n1, n5);
+ g.addEdge(n2, n3);
+ g.addEdge(n2, n4);
+ g.addEdge(n3, n5);
+ g.addEdge(n4, n5);
+ g.addEdge(n5, n6);
+ g.addEdge(n6, n7);
+ g.addEdge(n6, n12);
+ g.addEdge(n7, n8);
+ g.addEdge(n7, n9);
+ g.addEdge(n8, n9);
+ g.addEdge(n8, n10);
+ g.addEdge(n9, n10);
+ g.addEdge(n10, n11);
+ g.addEdge(n12, n13);
+ g.addEdge(n13, n14);
+ g.addEdge(n14, n13);
+ g.addEdge(n14, n15);
+ g.addEdge(n15, n6);
+ g.assignIntervals(n1);
+ cout << g.graphvizPrint(printer);
+ return 0;
+}
Property changes on: tools/branches/gsoc2009-decompiler/decompiler/intv.cc
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: svn:eol-style
+ native
Deleted: tools/branches/gsoc2009-decompiler/decompiler/test.cc
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/test.cc 2009-06-19 11:56:00 UTC (rev 41673)
+++ tools/branches/gsoc2009-decompiler/decompiler/test.cc 2009-06-19 13:30:00 UTC (rev 41674)
@@ -1,46 +0,0 @@
-#include <cstdio>
-
-#include "graph.h"
-
-#include <string>
-#include <sstream>
-#include <iostream>
-
-#include <functional>
-
-using namespace std;
-
-#include <boost/shared_ptr.hpp>
-
-
-struct BBlock {
- int a, b;
- virtual string print() {
- return string("something");
- }
-};
-
-struct BBlock2 : public BBlock {
- int c;
- virtual string print() {
- return string("[0000] push(1);\n[0003] not();\n if ()\n goto 0;");
- }
-};
-
-typedef boost::shared_ptr<BBlock> block_t;
-typedef Graph<block_t> graph_t;
-typedef graph_t::Node *node_t;
-
-string printer(block_t b) {
- return b->print();
-};
-
-int main() {
- graph_t g;
- node_t a = g.addNode(block_t(new BBlock()));
- g.addEdge(a, g.addNode(block_t(new BBlock2())));
- cout << g.graphvizPrint(printer) << endl;
- // cout << "===" << endl;
- // cout << a->_data->print() << endl;
- return 0;
-}
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