[Scummvm-cvs-logs] SF.net SVN: scummvm:[49667] tools/branches/gsoc2010-decompiler/decompiler
pidgeot at users.sourceforge.net
pidgeot at users.sourceforge.net
Mon Jun 14 21:55:08 CEST 2010
Revision: 49667
http://scummvm.svn.sourceforge.net/scummvm/?rev=49667&view=rev
Author: pidgeot
Date: 2010-06-14 19:55:08 +0000 (Mon, 14 Jun 2010)
Log Message:
-----------
Add statement grouping to code flow graph
This completes Milestone 3: Generation of code flow graph.
Next milestone: Code flow analysis
Modified Paths:
--------------
tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
tools/branches/gsoc2010-decompiler/decompiler/control_flow.h
tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp
tools/branches/gsoc2010-decompiler/decompiler/graph.h
Modified: tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp 2010-06-14 19:37:19 UTC (rev 49666)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp 2010-06-14 19:55:08 UTC (rev 49667)
@@ -22,18 +22,26 @@
#include "control_flow.h"
-#include <cstdio>
+#include <iostream>
+#include <stack>
+#include <boost/format.hpp>
-ControlFlow::ControlFlow(std::vector<Instruction> &insts, Engine *engine) {
+#define PUT(vertex, group) boost::put(boost::vertex_name, _g, vertex, group);
+#define PUT_ID(vertex, id) boost::put(boost::vertex_index, _g, vertex, id);
+#define GET(vertex) (boost::get(boost::vertex_name, _g, vertex))
+
+ControlFlow::ControlFlow(std::vector<Instruction> &insts, Engine *engine) : _insts(insts) {
_engine = engine;
GraphVertex last;
bool addEdge = false;
+ int id = 0;
- std::map<uint32, GraphVertex> addrMap;
for (InstIterator it = insts.begin(); it != insts.end(); ++it) {
GraphVertex cur = boost::add_vertex(_g);
- addrMap[it->_address] = cur;
- boost::put(boost::vertex_name, _g, cur, Group(it, it));
+ _addrMap[it->_address] = cur;
+ PUT(cur, Group(it, it));
+ PUT_ID(cur, id);
+ id++;
if (addEdge)
boost::add_edge(last, cur, _g);
@@ -47,7 +55,7 @@
case kCondJump:
case kJumpRel:
case kCondJumpRel:
- boost::add_edge(addrMap[it->_address], addrMap[_engine->getDestAddress(it)], _g);
+ boost::add_edge(find(it), find(_engine->getDestAddress(it)), _g);
break;
default:
break;
@@ -55,7 +63,93 @@
}
}
+GraphVertex ControlFlow::find(Instruction inst) {
+ return _addrMap[inst._address];
+}
+
+GraphVertex ControlFlow::find(InstIterator it) {
+ return _addrMap[it->_address];
+}
+
+GraphVertex ControlFlow::find(uint32 address) {
+ std::map<uint32, GraphVertex>::iterator it = _addrMap.find(address);
+ if (it == _addrMap.end())
+ std::cerr << "Request for instruction at unknown address" << boost::format("0x%08x") % address;
+ return it->second;
+}
+
+void ControlFlow::merge(GraphVertex g1, GraphVertex g2) {
+ //Update property
+ Group gr1 = GET(g1);
+ Group gr2 = GET(g2);
+ gr1._end = gr2._end;
+ PUT(g1, gr1);
+
+ //Update address map
+ InstIterator it = gr2._start;
+ do {
+ _addrMap[it->_address] = g1;
+ ++it;
+ } while (gr2._start != gr2._end && it != gr2._end);
+
+ //Add outgoing edges from g2
+ EdgeRange r = boost::out_edges(g2, _g);
+ for (OutEdgeIterator e = r.first; e != r.second; e++) {
+ boost::add_edge(g1, boost::target(*e, _g), _g);
+ }
+
+ //Remove edges to/from g2
+ boost::clear_vertex(g2, _g);
+ //Remove vertex
+ boost::remove_vertex(g2, _g);
+}
+
void ControlFlow::createGroups() {
+ InstIterator curInst, nextInst;
+ nextInst = _insts.begin();
+ nextInst++;
+ int stackLevel = 0;
+ int expectedStackLevel = 0;
+ std::stack<uint32> s;
+ for (curInst = _insts.begin(); nextInst != _insts.end(); curInst++, nextInst++) {
+ GraphVertex cur = find(curInst);
+ GraphVertex next = find(nextInst);
+
+ if (in_degree(cur, _g) == 0 && out_degree(cur, _g) == 0)
+ continue;
+
+ //Check if we go below our expected stack level
+ if (stackLevel == expectedStackLevel && curInst->_stackChange < 0) {
+ expectedStackLevel = s.top();
+ s.pop();
+ }
+
+ stackLevel += curInst->_stackChange;
+
+ // Group ends after a jump
+ if (curInst->_type == kJump || curInst->_type == kJumpRel || curInst->_type == kCondJump || curInst->_type == kCondJumpRel) {
+ if (stackLevel != expectedStackLevel) {
+ s.push(expectedStackLevel);
+ expectedStackLevel = stackLevel;
+ }
+ continue;
+ }
+
+ // Group ends before target of a jump
+ if (in_degree(next, _g) != 1) {
+ if (stackLevel != expectedStackLevel) {
+ s.push(expectedStackLevel);
+ expectedStackLevel = stackLevel;
+ }
+ continue;
+ }
+
+ // Group ends when stack is balanced, unless just before conditional jump
+ if (stackLevel == expectedStackLevel && nextInst->_type != kCondJump && nextInst->_type != kCondJumpRel) {
+ continue;
+ }
+ merge(cur, next);
+ }
}
const Graph &ControlFlow::analyze() {
Modified: tools/branches/gsoc2010-decompiler/decompiler/control_flow.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.h 2010-06-14 19:37:19 UTC (rev 49666)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.h 2010-06-14 19:55:08 UTC (rev 49667)
@@ -31,9 +31,36 @@
*/
class ControlFlow {
private:
- Graph _g; ///< The control flow graph.
- Engine *_engine; ///< Pointer to the Engine used for the script.
+ Graph _g; ///< The control flow graph.
+ Engine *_engine; ///< Pointer to the Engine used for the script.
+ std::vector<Instruction> &_insts; ///< The instructions being analyzed
+ std::map<uint32, GraphVertex> _addrMap; ///< Map between addresses and vertices.
+ /**
+ * Find a graph vertex through an instruction.
+ * @param inst The instruction to find the vertex for.
+ */
+ GraphVertex find(Instruction inst);
+
+ /**
+ * Find a graph vertex through an instruction iterator.
+ * @param it The iterator to find the vertex for.
+ */
+ GraphVertex find(InstIterator it);
+
+ /**
+ * Find a graph vertex through an address.
+ * @param address The address to find the vertex for.
+ */
+ GraphVertex find(uint32 address);
+
+ /**
+ * Merge two graph vertices. g2 will be merged into g1.
+ * @param g1 The first vertex to merge.
+ * @param g2 The second vertex to merge.
+ */
+ void merge(GraphVertex g1, GraphVertex g2);
+
public:
/**
* Constructor for the control flow graph.
Modified: tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp 2010-06-14 19:37:19 UTC (rev 49666)
+++ tools/branches/gsoc2010-decompiler/decompiler/decompiler.cpp 2010-06-14 19:55:08 UTC (rev 49667)
@@ -120,6 +120,7 @@
//Control flow analysis
ControlFlow *cf = new ControlFlow(insts, engine);
+ cf->createGroups();
Graph g = cf->analyze();
if (vm.count("dump-graph")) {
Modified: tools/branches/gsoc2010-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/graph.h 2010-06-14 19:37:19 UTC (rev 49666)
+++ tools/branches/gsoc2010-decompiler/decompiler/graph.h 2010-06-14 19:55:08 UTC (rev 49667)
@@ -26,6 +26,7 @@
#include "instruction.h"
#include <ostream>
+#include <utility>
#include <boost/format.hpp>
@@ -83,12 +84,15 @@
}
};
-typedef boost::property<boost::vertex_name_t, Group> GroupProperty; ///< Type representing properties containing a Group
+typedef boost::property<boost::vertex_name_t, Group> GroupProperty; ///< Type representing properties containing a Group.
+typedef boost::property<boost::vertex_index_t, int, GroupProperty> GraphProperty; ///< Type representing properties containing an index, followed by a GroupProperty.
+typedef boost::adjacency_list<boost::vecS, boost::listS, boost::bidirectionalS, GraphProperty> 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.
+typedef Graph::out_edge_iterator OutEdgeIterator; ///< Type representing an iterator for outgoing edges.
+typedef Graph::in_edge_iterator InEdgeIterator; ///< Type representing an iterator for ingoing edges.
+typedef std::pair<OutEdgeIterator, OutEdgeIterator> EdgeRange; ///< Type representing a range of edges from boost::out_edges.
-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
-
/**
* Type used to set properties for dot output.
*/
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