[Scummvm-cvs-logs] SF.net SVN: scummvm:[50546] tools/branches/gsoc2010-decompiler/decompiler
pidgeot at users.sourceforge.net
pidgeot at users.sourceforge.net
Thu Jul 1 16:44:09 CEST 2010
Revision: 50546
http://scummvm.svn.sourceforge.net/scummvm/?rev=50546&view=rev
Author: pidgeot
Date: 2010-07-01 14:44:08 +0000 (Thu, 01 Jul 2010)
Log Message:
-----------
Change Groups to be stored as a pointer
Add additional information to Group for short-circuit detection
Modified Paths:
--------------
tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
tools/branches/gsoc2010-decompiler/decompiler/graph.h
tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h
Modified: tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp 2010-07-01 12:30:56 UTC (rev 50545)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp 2010-07-01 14:44:08 UTC (rev 50546)
@@ -35,11 +35,12 @@
GraphVertex last;
bool addEdge = false;
int id = 0;
+ Group *prev = NULL;
for (InstIterator it = insts.begin(); it != insts.end(); ++it) {
GraphVertex cur = boost::add_vertex(_g);
_addrMap[it->_address] = cur;
- PUT(cur, Group(it, it));
+ PUT(cur, new Group(it, it, prev));
PUT_ID(cur, id);
id++;
@@ -47,6 +48,7 @@
boost::add_edge(last, cur, _g);
last = cur;
addEdge = (it->_type != kJump && it->_type != kJumpRel);
+ prev = GET(cur);
}
for (InstIterator it = insts.begin(); it != insts.end(); ++it) {
@@ -80,17 +82,17 @@
void ControlFlow::merge(GraphVertex g1, GraphVertex g2) {
// Update property
- Group gr1 = GET(g1);
- Group gr2 = GET(g2);
- gr1._end = gr2._end;
+ Group *gr1 = GET(g1);
+ Group *gr2 = GET(g2);
+ gr1->_end = gr2->_end;
PUT(g1, gr1);
// Update address map
- InstIterator it = gr2._start;
+ InstIterator it = gr2->_start;
do {
_addrMap[it->_address] = g1;
++it;
- } while (gr2._start != gr2._end && it != gr2._end);
+ } while (gr2->_start != gr2->_end && it != gr2->_end);
// Add outgoing edges from g2
EdgeRange r = boost::out_edges(g2, _g);
@@ -105,13 +107,13 @@
}
void ControlFlow::setStackLevel(GraphVertex g, int level) {
- Group gr = GET(g);
- if (gr._stackLevel != -1) {
- if (gr._stackLevel != level)
- std::cerr << boost::format("WARNING: Inconsistency in expected stack level for instruction at address 0x%08x (current: %d, requested: %d)\n") % gr._start->_address % gr._stackLevel % level;
+ Group *gr = GET(g);
+ if (gr->_stackLevel != -1) {
+ if (gr->_stackLevel != level)
+ std::cerr << boost::format("WARNING: Inconsistency in expected stack level for instruction at address 0x%08x (current: %d, requested: %d)\n") % gr->_start->_address % gr->_stackLevel % level;
return;
}
- gr._stackLevel = level;
+ gr->_stackLevel = level;
PUT(g, gr)
if (boost::out_degree(g, _g) == 0)
@@ -119,7 +121,7 @@
EdgeRange r = boost::out_edges(g, _g);
for (OutEdgeIterator e = r.first; e != r.second; e++) {
- setStackLevel(boost::target(*e, _g), level + gr._start->_stackChange);
+ setStackLevel(boost::target(*e, _g), level + gr->_start->_stackChange);
}
}
@@ -137,12 +139,12 @@
if (in_degree(cur, _g) == 0 && out_degree(cur, _g) == 0)
continue;
- Group grCur = GET(cur);
- Group grNext = GET(next);
- expectedStackLevel = grCur._stackLevel;
+ Group *grCur = GET(cur);
+ Group *grNext = GET(next);
+ expectedStackLevel = grCur->_stackLevel;
- if (expectedStackLevel > grNext._stackLevel)
- expectedStackLevel = grNext._stackLevel;
+ if (expectedStackLevel > grNext->_stackLevel)
+ expectedStackLevel = grNext->_stackLevel;
stackLevel += curInst->_stackChange;
@@ -152,7 +154,7 @@
s.push(expectedStackLevel);
expectedStackLevel = stackLevel;
}*/
- stackLevel = grNext._stackLevel;
+ stackLevel = grNext->_stackLevel;
continue;
}
@@ -162,7 +164,7 @@
s.push(expectedStackLevel);
expectedStackLevel = stackLevel;
}*/
- stackLevel = grNext._stackLevel;
+ stackLevel = grNext->_stackLevel;
continue;
}
@@ -177,5 +179,6 @@
}
const Graph &ControlFlow::analyze() {
+
return _g;
}
Modified: tools/branches/gsoc2010-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/graph.h 2010-07-01 12:30:56 UTC (rev 50545)
+++ tools/branches/gsoc2010-decompiler/decompiler/graph.h 2010-07-01 14:44:08 UTC (rev 50546)
@@ -34,29 +34,47 @@
#include <boost/graph/adjacency_list.hpp>
/**
+ * Enumeration representing the different kinds of groups.
+ */
+enum GroupType {
+ kNormal, ///< Normal group.
+ kWhileCond, ///< Group is the condition check for a while-loop.
+ kDoWhileCond, ///< Group is the condition check for a do-while-loop.
+ kIfCond, ///< Group is the condition check for an if.
+ kBreak, ///< Group is a break.
+ kContinue ///< Group is a continue.
+};
+
+/**
* Structure representing a group of instructions.
*/
struct Group {
InstIterator _start; ///< First instruction in the group.
InstIterator _end; ///< Last instruction in the group.
int _stackLevel; ///< Level of the stack upon entry.
-
+ GroupType _type; ///< Type of the group.
+ Group *_prev; ///< Pointer to the previous group, when ordered by address. Used for short-circuit analysis.
+
/**
- * Parameterless constructor for Group. Required for use with STL and Boost.
- * Should not be called manually.
+ * Parameterless constructor for Group. Required for use with STL and Boost, should not be called manually.
*/
- Group() { _stackLevel = -1; }
+ Group() {
+ _stackLevel = -1;
+ _type = kNormal;
+ }
/**
* Constructor for Group.
*
* @param start First instruction in the group.
* @param end Last instruction in the group.
+ * @param prev Pointer to the previous group, when ordered by address.
*/
- Group(InstIterator start, InstIterator end) {
+ Group(InstIterator start, InstIterator end, Group *prev) {
_start = start;
_end = end;
_stackLevel = -1;
+ _type = kNormal;
}
/**
@@ -93,9 +111,9 @@
};
/**
- * Type representing properties containing a Group.
+ * Type representing properties containing a pointer to a Group.
*/
-typedef boost::property<boost::vertex_name_t, Group> GroupProperty;
+typedef boost::property<boost::vertex_name_t, Group*> GroupProperty;
/**
* Type representing properties containing an index, followed by a GroupProperty.
Modified: tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h 2010-07-01 12:30:56 UTC (rev 50545)
+++ tools/branches/gsoc2010-decompiler/decompiler/test/cfg_test.h 2010-07-01 14:44:08 UTC (rev 50546)
@@ -43,20 +43,20 @@
TS_ASSERT(boost::num_vertices(g) == 4);
std::pair<VertexIterator, VertexIterator> range = boost::vertices(g);
VertexIterator it = range.first;
- Group gr = GET(*it);
- TS_ASSERT(gr._start->_address == 0);
+ Group *gr = GET(*it);
+ TS_ASSERT(gr->_start->_address == 0);
TS_ASSERT(boost::in_degree(*it, g) == 0 && boost::out_degree(*it, g) == 1);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 2);
+ TS_ASSERT(gr->_start->_address == 2);
TS_ASSERT(boost::in_degree(*it, g) == 1 && boost::out_degree(*it, g) == 1);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 5);
+ TS_ASSERT(gr->_start->_address == 5);
TS_ASSERT(boost::in_degree(*it, g) == 0 && boost::out_degree(*it, g) == 1);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 6);
+ TS_ASSERT(gr->_start->_address == 6);
TS_ASSERT(boost::in_degree(*it, g) == 2 && boost::out_degree(*it, g) == 0);
};
@@ -71,20 +71,20 @@
TS_ASSERT(boost::num_vertices(g) == 4);
std::pair<VertexIterator, VertexIterator> range = boost::vertices(g);
VertexIterator it = range.first;
- Group gr = GET(*it);
- TS_ASSERT(gr._start->_address == 0);
+ Group *gr = GET(*it);
+ TS_ASSERT(gr->_start->_address == 0);
TS_ASSERT(boost::in_degree(*it, g) == 0 && boost::out_degree(*it, g) == 1);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 2);
+ TS_ASSERT(gr->_start->_address == 2);
TS_ASSERT(boost::in_degree(*it, g) == 1 && boost::out_degree(*it, g) == 2);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 5);
+ TS_ASSERT(gr->_start->_address == 5);
TS_ASSERT(boost::in_degree(*it, g) == 1 && boost::out_degree(*it, g) == 1);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 6);
+ TS_ASSERT(gr->_start->_address == 6);
TS_ASSERT(boost::in_degree(*it, g) == 2 && boost::out_degree(*it, g) == 0);
}
@@ -100,17 +100,17 @@
TS_ASSERT(boost::num_vertices(g) == 3);
std::pair<VertexIterator, VertexIterator> range = boost::vertices(g);
VertexIterator it = range.first;
- Group gr = GET(*it);
- TS_ASSERT(gr._start->_address == 0);
- TS_ASSERT(gr._end->_address == 2);
+ Group *gr = GET(*it);
+ TS_ASSERT(gr->_start->_address == 0);
+ TS_ASSERT(gr->_end->_address == 2);
TS_ASSERT(boost::in_degree(*it, g) == 0 && boost::out_degree(*it, g) == 2);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 5);
+ TS_ASSERT(gr->_start->_address == 5);
TS_ASSERT(boost::in_degree(*it, g) == 1 && boost::out_degree(*it, g) == 1);
++it;
gr = GET(*it);
- TS_ASSERT(gr._start->_address == 6);
+ TS_ASSERT(gr->_start->_address == 6);
TS_ASSERT(boost::in_degree(*it, g) == 2 && boost::out_degree(*it, g) == 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