[Scummvm-cvs-logs] SF.net SVN: scummvm:[42395] tools/branches/gsoc2009-decompiler/decompiler

kjdf at users.sourceforge.net kjdf at users.sourceforge.net
Sat Jul 11 22:31:41 CEST 2009


Revision: 42395
          http://scummvm.svn.sourceforge.net/scummvm/?rev=42395&view=rev
Author:   kjdf
Date:     2009-07-11 20:31:41 +0000 (Sat, 11 Jul 2009)

Log Message:
-----------
decompiler: 'if' structuring

Modified Paths:
--------------
    tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
    tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
    tools/branches/gsoc2009-decompiler/decompiler/graph.h
    tools/branches/gsoc2009-decompiler/decompiler/node.cpp
    tools/branches/gsoc2009-decompiler/decompiler/node.h

Modified: tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp	2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/decompiler.cpp	2009-07-11 20:31:41 UTC (rev 42395)
@@ -80,6 +80,7 @@
 	}
 	if (vars.count("graph-struct")) {
 		cfg.structureLoops(cfg.stronglyConnectedComponents());
+		cfg.structureConditionals();
 		cout << cfg.graphvizToString(vars["fontname"].as<string>());
 		exit(0);
 	}

Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp	2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp	2009-07-11 20:31:41 UTC (rev 42395)
@@ -96,6 +96,14 @@
 			ret << '"' << u << "\" -> \"" << loop->_body->_entry << "\"[color=blue,style=dashed]" << endl;
 	}
 
+	foreach (Node *u, graph->_nodes) {
+		IfThenElse *ifte = dynamic_cast<IfThenElse*>(u);
+		if (ifte && ifte->_consequence->_entry)
+			ret << '"' << u << "\" -> \"" << ifte->_consequence->_entry << "\"[color=red]" << endl;
+		if (ifte && ifte->_alternative->_entry)
+			ret << '"' << u << "\" -> \"" << ifte->_alternative->_entry << "\"[color=red,style=dashed]" << endl;
+	}
+
 	return ret.str();
 }
 
@@ -404,7 +412,7 @@
 				foreach (Node *v, u->_out)
 					if (v == entry && (!latch || latch->_postOrder > u->_postOrder))
 						latch = u;
-			if (latch && latch != entry &&latch->edgeOutsideComponent()) {
+			if (latch && latch != entry && latch->edgeOutsideComponent()) {
 				_nodes.push_back(new DoWhileLoop(this, entry, latch));
 				cerr << "done do-while loop at " << phex(entry->address()) << endl;
 			} else if (latch && entry->edgeOutsideComponent()) {
@@ -419,3 +427,17 @@
 		}
 	}
 }
+
+
+void ControlFlowGraph::structureConditionals() {
+	assignDominators();
+	foreach (Node *u, inPostOrder(_nodes))
+		if (u->_out.size() == 2) {
+			_nodes.push_back(new IfThenElse(this, u));
+			cerr << "done if-then-else at " << phex(u->address()) << endl;
+			return structureConditionals();
+		}
+	foreach (ControlFlowGraph *subgraph, _subgraphs)
+		if (subgraph->_entry)
+			subgraph->structureConditionals();
+}

Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h	2009-07-11 20:31:41 UTC (rev 42395)
@@ -37,6 +37,7 @@
 	ControlFlowGraph *yank(std::set<Node*> &body);
 
 	void structureLoops(const std::list< std::list<Node*> > &components);
+	void structureConditionals();
 
 	// to be removed
 	void assignIntervals();

Modified: tools/branches/gsoc2009-decompiler/decompiler/node.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.cpp	2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.cpp	2009-07-11 20:31:41 UTC (rev 42395)
@@ -13,6 +13,20 @@
 #endif
 
 
+
+bool reaches(Node *u, Node *t, set<Node*> &visited) {
+	if (u == t)
+		return true;
+	if (contains(visited, u))
+		return false;
+	visited.insert(u);
+	foreach (Node *v, u->_out)
+		if (reaches(v, t, visited))
+			return true;
+	return false;
+}
+
+
 Node::Node() : _component(), _dominator(), _interval(), _postOrder() {
 }
 
@@ -45,6 +59,12 @@
 }
 
 
+bool Node::reaches(Node *t) {
+	set<Node*> visited;
+	return ::reaches(this, t, visited);
+}
+
+
 BasicBlock::BasicBlock(list<Instruction*>::iterator first, list<Instruction*>::iterator last) : Node() {
 	copy(first, last, back_inserter(_instructions));
 }
@@ -109,7 +129,9 @@
 		if (dynamic_cast<ProxyNode*>(u))
 			graph->deleteNode(u);
 
-	// attach this while block in place of entry
+	// attach this loop block in place of entry
+	if (graph->_entry == entry)
+		graph->_entry = this;
 	foreach (Node *u, list<Node*>(entry->_in))
 		if (!dynamic_cast<ProxyNode*>(u))
 			graph->replaceEdges(u, entry, this);
@@ -157,7 +179,9 @@
 	_body = graph->yank(body);
 	_body->setEntry(entry->address());
 
-	// remove unneeded nodes in main graph and attach this while block in place of entry
+	// remove unneeded nodes in main graph and attach this loop block in place of entry
+	if (graph->_entry == entry)
+		graph->_entry = this;
 	foreach (Node *u, graph->_nodes)
 		foreach (Node *&v, u->_out)
 			if (v->address() == entry->address()) {
@@ -223,7 +247,9 @@
 	graph->_nodes.remove(entry);
 	_body->_nodes.push_back(entry);
 
-	// attach this while block in place of entry
+	// attach this loop block in place of entry
+	if (graph->_entry == entry)
+		graph->_entry = this;
 	foreach (Node *u, list<Node*>(entry->_in))
 		graph->replaceEdges(u, entry, this);
 	if (exit)
@@ -251,3 +277,65 @@
 	ret << "}" << endl;
 	return ret.str();
 }
+
+
+IfThenElse::IfThenElse(ControlFlowGraph *graph, Node *entry) : Node(), _condition(entry) {
+	mimic(entry);
+	Node *exit = 0;
+	foreach (Node *u, graph->_nodes)
+		if (u->_dominator == entry && u->_in.size() >= 2)
+			exit = u;
+
+	// yank out true and false branch
+	set<Node*> consequence, alternative;
+	foreach (Node *u, graph->_nodes)
+		if (u != entry && entry->dominates(u) && !entry->_out.front()->reaches(u))
+			consequence.insert(u);
+	foreach (Node *u, graph->_nodes)
+		if (u != entry && entry->dominates(u) && !entry->_out.back()->reaches(u))
+			alternative.insert(u);
+	_consequence = graph->yank(consequence);
+	if (!consequence.empty())
+		_consequence->setEntry(entry->_out.back()->address());
+	_alternative = graph->yank(alternative);
+	if (!alternative.empty())
+		_alternative->setEntry(entry->_out.front()->address());
+
+	// remove unneeded nodes in main graph
+	graph->forgetNode(entry);
+	foreach (Node *u, entry->_out)
+		if (dynamic_cast<ProxyNode*>(u))
+			graph->deleteNode(u);
+
+	// attach this conditional block in place of entry
+	if (graph->_entry == entry)
+		graph->_entry = this;
+	foreach (Node *u, list<Node*>(entry->_in))
+		graph->replaceEdges(u, entry, this);
+	if (exit)
+		graph->addEdge(this, exit);
+}
+
+
+IfThenElse::~IfThenElse() {
+}
+
+
+uint32 IfThenElse::address() {
+	return _condition->address();
+}
+
+
+string IfThenElse::toString() {
+	ostringstream ret;
+	ret << "if (" << endl;
+	ret << _condition->toString();
+	ret << ") { ";
+	if (_consequence->_entry)
+		ret << "[" << phex(_consequence->_entry->address()) << "] ";
+	ret << "} else { ";
+	if (_alternative->_entry)
+		ret << "[" << phex(_alternative->_entry->address()) << "] ";
+	ret << "}" << endl;
+	return ret.str();
+}

Modified: tools/branches/gsoc2009-decompiler/decompiler/node.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/node.h	2009-07-11 19:38:41 UTC (rev 42394)
+++ tools/branches/gsoc2009-decompiler/decompiler/node.h	2009-07-11 20:31:41 UTC (rev 42395)
@@ -27,6 +27,7 @@
 	bool dominates(Node *u);
 	Node *edgeOutsideComponent();
 	void mimic(Node *node);
+	bool reaches(Node *t);
 	virtual std::string toString() = 0;
 };
 
@@ -61,7 +62,6 @@
 
 	Loop() : Node(), _body() {
 	}
-
 };
 
 
@@ -100,4 +100,18 @@
 	std::string toString();
 };
 
+
+struct IfThenElse : public Node {
+
+	Node *_condition;
+	ControlFlowGraph *_consequence;
+	ControlFlowGraph *_alternative;
+
+	IfThenElse(ControlFlowGraph *graph, Node *entry);
+	~IfThenElse();
+
+	uint32 address();
+	std::string toString();
+};
+
 #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