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

[pidgeot at users.sourceforge.net]

Revision: 49614
          http://scummvm.svn.sourceforge.net/scummvm/?rev=49614&view=rev
Author:   pidgeot
Date:     2010-06-12 23:57:50 +0000 (Sat, 12 Jun 2010)

Log Message:
-----------
*Very* basic prototype for code flow graph

No grouping is performed yet; each instruction gets its own vertex and
jumps are not considered at all when creating the edges.
Basic dot output is implemented and appears to work well.

Modified Paths:
--------------
    tools/branches/gsoc2010-decompiler/Makefile.common
    tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp
    tools/branches/gsoc2010-decompiler/decompiler/disassembler.h
    tools/branches/gsoc2010-decompiler/decompiler/instruction.h

Added Paths:
-----------
    tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
    tools/branches/gsoc2010-decompiler/decompiler/control_flow.h
    tools/branches/gsoc2010-decompiler/decompiler/graph.h

Modified: tools/branches/gsoc2010-decompiler/Makefile.common
===================================================================
--- tools/branches/gsoc2010-decompiler/Makefile.common	2010-06-12 23:53:26 UTC (rev 49613)
+++ tools/branches/gsoc2010-decompiler/Makefile.common	2010-06-12 23:57:50 UTC (rev 49614)
@@ -267,6 +267,7 @@
 	decompiler/disassembler.o \
 	decompiler/simple_disassembler.o \
 	decompiler/unknown_opcode.o \
+	decompiler/control_flow.o \
 	decompiler/scummv6/disassembler.o \
 	decompiler/scummv6/engine.o
 

Added: tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp	                        (rev 0)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp	2010-06-12 23:57:50 UTC (rev 49614)
@@ -0,0 +1,45 @@
+/* ScummVM Tools
+ * Copyright (C) 2010 The ScummVM project
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ *
+ */
+
+#include "control_flow.h"
+
+ControlFlow::ControlFlow(std::vector<Instruction> &insts) {
+	GraphVertex last;
+
+	std::map<uint32, GraphVertex> addrMap;
+	for (InstIterator it = insts.begin(); it != insts.end(); ++it)
+	{
+		GraphVertex cur = boost::add_vertex(g);
+		boost::put(boost::vertex_name, g, cur, Group(it, it));
+
+		if (it != insts.begin())
+			boost::add_edge(last, cur, g);
+		last = cur;
+	}
+}
+
+void ControlFlow::createGroups() {
+}
+
+const Graph &ControlFlow::analyze() {
+	return g;
+}


Property changes on: tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
___________________________________________________________________
Added: svn:mime-type
   + text/plain
Added: svn:keywords
   + Date Rev Author URL Id
Added: svn:eol-style
   + native

Added: tools/branches/gsoc2010-decompiler/decompiler/control_flow.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.h	                        (rev 0)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.h	2010-06-12 23:57:50 UTC (rev 49614)
@@ -0,0 +1,49 @@
+/* ScummVM Tools
+ * Copyright (C) 2010 The ScummVM project
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ *
+ */
+
+#ifndef DEC_CONTROL_FLOW_H
+#define DEC_CONTROL_FLOW_H
+
+#include "graph.h"
+
+class ControlFlow {
+private:
+	Graph g; ///< The control flow graph.
+public:
+	/**
+	 * Constructor for the control flow graph.
+	 * @param insts std::vector containing the instructions to analyze control flow for.
+	 */
+	ControlFlow(std::vector<Instruction> &insts);
+
+	/**
+	 * Creates groups suitable for a stack-based machine.
+	 */
+	void createGroups();
+
+	/**
+	 * Performs control flow analysis.
+	 */
+	const Graph &analyze();
+};
+
+#endif


Property changes on: tools/branches/gsoc2010-decompiler/decompiler/control_flow.h
___________________________________________________________________
Added: svn:mime-type
   + text/plain
Added: svn:keywords
   + Date Rev Author URL Id
Added: svn:eol-style
   + native

Modified: tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp	2010-06-12 23:53:26 UTC (rev 49613)
+++ tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp	2010-06-12 23:57:50 UTC (rev 49614)
@@ -20,17 +20,20 @@
  *
  */
 
-#include <fstream>
-#include <iostream>
-#include <boost/program_options.hpp>
-
 #include "objectFactory.h"
 
 #include "disassembler.h"
 #include "engine.h"
 
+#include "control_flow.h"
+
 #include "scummv6/engine.h"
 
+#include <fstream>
+#include <iostream>
+#include <boost/program_options.hpp>
+#include <boost/graph/graphviz.hpp>
+
 namespace po = boost::program_options;
 
 #define ENGINE(id, description, engineClass) engines[std::string(id)] = description; engineFactory.addEntry<engineClass>(std::string(id));
@@ -47,7 +50,8 @@
 			("help,?", "Produce this help message.")
 			("engine,e", po::value<std::string>(), "Engine the script originates from.")
 			("list,l", "List the supported engines.")
-			("dump-disassembly,d", po::value<std::string>()->implicit_value(""), "Dump the disassembly to a file. Leave out filename to output to stdout.");
+			("dump-disassembly,d", po::value<std::string>()->implicit_value(""), "Dump the disassembly to a file. Leave out filename to output to stdout.")
+			("dump-graph,g", po::value<std::string>()->implicit_value(""), "Output the control flow graph in dot format to a file. Leave out filename to output to stdout.");
 
 		po::options_description args("");
 		args.add(visible).add_options()
@@ -78,7 +82,7 @@
 		if (vm.count("help") || !vm.count("input-file")) {
 			std::cout << "Usage: " << argv[0] << " [option...] file" << "\n";
 			std::cout << visible << "\n";
-			std::cout << "Note: If outputting to stdout, -d must NOT be specified immediately before the input file.\n";
+			std::cout << "Note: If outputting to stdout, -d or -g must NOT be specified immediately before the input file.\n";
 			return 1;
 		}
 	
@@ -93,7 +97,7 @@
 		Engine *engine = engineFactory.create(vm["engine"].as<std::string>());
 		std::string inputFile = vm["input-file"].as<std::string>();
 
-		//TODO: Process file
+		//Disassembly
 		Disassembler *disassembler = engine->getDisassembler();
 		disassembler->open(inputFile.c_str());
 
@@ -113,6 +117,28 @@
 		}
 
 		delete disassembler;
+
+		//Control flow analysis
+		ControlFlow* cf = new ControlFlow(insts);
+		Graph g = cf->analyze();
+
+		if (vm.count("dump-graph")) {
+			std::streambuf *buf; 
+			std::ofstream of; 
+ 
+			if (vm["dump-graph"].as<std::string>() != "") { 
+				of.open(vm["dump-graph"].as<std::string>().c_str()); 
+				buf = of.rdbuf(); 
+			} else { 
+				buf = std::cout.rdbuf(); 
+			} 
+ 			std::ostream out(buf); 
+			boost::write_graphviz(out, g, boost::make_label_writer(get(boost::vertex_name, g)));
+		}
+
+		delete cf;
+
+		//TODO: Code generation
 	} catch (std::exception& e) {
 		std::cerr << "ERROR: " << e.what() << "\n";
 		return 3;

Modified: tools/branches/gsoc2010-decompiler/decompiler/disassembler.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/disassembler.h	2010-06-12 23:53:26 UTC (rev 49613)
+++ tools/branches/gsoc2010-decompiler/decompiler/disassembler.h	2010-06-12 23:57:50 UTC (rev 49614)
@@ -30,8 +30,6 @@
 #include "common/file.h"
 #include "unknown_opcode.h"
 
-typedef std::vector<Instruction>::iterator InstIterator;
-
 /**
  * Base class for disassemblers.
  */

Added: tools/branches/gsoc2010-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/graph.h	                        (rev 0)
+++ tools/branches/gsoc2010-decompiler/decompiler/graph.h	2010-06-12 23:57:50 UTC (rev 49614)
@@ -0,0 +1,82 @@
+/* ScummVM Tools
+ * Copyright (C) 2010 The ScummVM project
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * $URL$
+ * $Id$
+ *
+ */
+
+#ifndef DEC_GRAPH_H
+#define DEC_GRAPH_H
+
+#include "instruction.h"
+
+#include <ostream>
+
+#include <boost/format.hpp>
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/adjacency_list.hpp>
+
+/**
+ * Structure representing a group of instructions.
+ */
+struct Group {
+	InstIterator _start; ///< First instruction in the group.
+	InstIterator _end;   ///< Last instruction in the group.
+
+	Group() {}
+
+	/**
+	 * Constructor for Group.
+	 * @param start First instruction in the group.
+	 * @param end Last instruction in the group.
+	 */
+	Group(InstIterator start, InstIterator end) {
+		_start = start;
+		_end = end;
+	}
+
+	/**
+	 * Output a group to an std::ostream as a graphviz label.
+	 * @param output The std::ostream to output to.
+	 * @param group The Group to output.
+	 * @return The std::ostream used for output.
+	 */
+	friend std::ostream& operator<< (std::ostream &output, Group &group) {
+		InstIterator inst = group._start;
+		do {
+			output << boost::format("%08x: %s") % inst->_address % inst->_name;
+			std::vector<Parameter>::iterator param;
+			for (param = inst->_params.begin(); param != inst->_params.end(); ++param) {
+				if (param != inst->_params.begin())
+					output << ",";
+				output << " " << param->_value;
+			}
+			output << "\\n";			
+		} while (inst++ != group._end);
+		return output;
+	}
+};
+
+typedef boost::property<boost::vertex_name_t, Group> GroupProperty; ///< Type representing properties containing a Group
+
+typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, GroupProperty> Graph; ///< Type used for the code flow graph
+typedef Graph::vertex_descriptor GraphVertex; ///< Type representing a vertex in the graph
+typedef Graph::edge_descriptor GraphEdge; ///< Type representing an edge in the graph
+
+#endif


Property changes on: tools/branches/gsoc2010-decompiler/decompiler/graph.h
___________________________________________________________________
Added: svn:mime-type
   + text/plain
Added: svn:keywords
   + Date Rev Author URL Id
Added: svn:eol-style
   + native

Modified: tools/branches/gsoc2010-decompiler/decompiler/instruction.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/instruction.h	2010-06-12 23:53:26 UTC (rev 49613)
+++ tools/branches/gsoc2010-decompiler/decompiler/instruction.h	2010-06-12 23:57:50 UTC (rev 49614)
@@ -101,4 +101,6 @@
 	std::vector<Parameter> _params; ///< Array of parameters used for the instruction.
 };
 
+typedef std::vector<Instruction>::iterator InstIterator;
+
 #endif


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.