[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