[Scummvm-cvs-logs] SF.net SVN: scummvm:[51748] tools/branches/gsoc2010-decompiler/decompiler
pidgeot at users.sourceforge.net
pidgeot at users.sourceforge.net
Thu Aug 5 03:14:32 CEST 2010
Revision: 51748
http://scummvm.svn.sourceforge.net/scummvm/?rev=51748&view=rev
Author: pidgeot
Date: 2010-08-05 01:14:31 +0000 (Thu, 05 Aug 2010)
Log Message:
-----------
Rewrite function detection
The KYRA-specific function detection has been replaced with a generic,
opt-in function detection which converts unreachable code into
functions.
A post-processing step will be required to fill in metadata for code
generation; this has not yet been implemented.
Modified Paths:
--------------
tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
tools/branches/gsoc2010-decompiler/decompiler/control_flow.h
tools/branches/gsoc2010-decompiler/decompiler/engine.h
tools/branches/gsoc2010-decompiler/decompiler/kyra/disassembler.cpp
tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.cpp
tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.h
Modified: tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp 2010-08-05 00:28:22 UTC (rev 51747)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.cpp 2010-08-05 01:14:31 UTC (rev 51748)
@@ -21,10 +21,11 @@
*/
#include "control_flow.h"
+#include "stack.h"
#include <algorithm>
#include <iostream>
-#include <stack>
+#include <set>
#include <boost/format.hpp>
@@ -157,9 +158,72 @@
}
}
+void ControlFlow::detectFunctions() {
+ uint32 nextFunc = 0;
+ for (ConstInstIterator it = _insts.begin(); it != _insts.end(); ++it) {
+ GraphVertex v = find(it);
+ GroupPtr gr = GET(v);
+
+ // If this is already a function, skip it
+ if (_engine->_functions.find(gr->_start->_address) != _engine->_functions.end()) {
+ nextFunc = _engine->_functions[gr->_start->_address]._endIt->_address;
+ continue;
+ }
+
+ // If a function has already been found here, skip it
+ if (gr->_start->_address < nextFunc)
+ continue;
+
+ InEdgeRange ier = boost::in_edges(v, _g);
+ bool isEntryPoint = true;
+ for (InEdgeIterator e = ier.first; e != ier.second; ++e) {
+ // If an ingoing edge exists from earlier in the code, this is not a function entry point
+ if (GET(boost::source(*e, _g))->_start->_address < gr->_start->_address)
+ isEntryPoint = false;
+ }
+
+ if (isEntryPoint) {
+ // Detect end point
+ Stack<GraphVertex> stack;
+ std::set<GraphVertex> seen;
+ stack.push(v);
+ GroupPtr endPoint = gr;
+ while (!stack.empty()) {
+ v = stack.pop();
+ GroupPtr tmp = GET(v);
+ if (tmp->_start->_address > endPoint->_start->_address)
+ endPoint = tmp;
+ OutEdgeRange r = boost::out_edges(v, _g);
+ for (OutEdgeIterator i = r.first; i != r.second; ++i) {
+ GraphVertex target = boost::target(*i, _g);
+ if (seen.find(target) == seen.end()) {
+ stack.push(target);
+ seen.insert(target);
+ }
+ }
+ }
+
+ ConstInstIterator endInst;
+ if (endPoint->_next)
+ endInst = endPoint->_next->_start;
+ else
+ endInst = _insts.end();
+ Function f(gr->_start, endInst);
+ f._v = find(it);
+ _engine->_functions[gr->_start->_address] = f;
+ nextFunc = endInst->_address;
+ }
+ }
+}
+
void ControlFlow::createGroups() {
if (GET(_engine->_functions.begin()->second._v)->_stackLevel != -1)
return;
+
+ // Detect more functions
+ if (_engine->detectMoreFuncs())
+ detectFunctions();
+
for (FuncMap::iterator fn = _engine->_functions.begin(); fn != _engine->_functions.end(); ++fn)
setStackLevel(fn->second._v, 0);
ConstInstIterator curInst, nextInst;
@@ -167,7 +231,7 @@
nextInst++;
int stackLevel = 0;
int expectedStackLevel = 0;
- std::stack<uint32> s;
+ //std::stack<uint32> s;
for (curInst = _insts.begin(); nextInst != _insts.end(); ++curInst, ++nextInst) {
GraphVertex cur = find(curInst);
GraphVertex next = find(nextInst);
Modified: tools/branches/gsoc2010-decompiler/decompiler/control_flow.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/control_flow.h 2010-08-05 00:28:22 UTC (rev 51747)
+++ tools/branches/gsoc2010-decompiler/decompiler/control_flow.h 2010-08-05 01:14:31 UTC (rev 51748)
@@ -156,6 +156,11 @@
void createGroups();
/**
+ * Auto-detects functions from unreachable code.
+ */
+ void detectFunctions();
+
+ /**
* Performs control flow analysis.
* The constructs are detected in the following order: do-while, while, break, continue, if/else.
*
Modified: tools/branches/gsoc2010-decompiler/decompiler/engine.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/engine.h 2010-08-05 00:28:22 UTC (rev 51747)
+++ tools/branches/gsoc2010-decompiler/decompiler/engine.h 2010-08-05 01:14:31 UTC (rev 51748)
@@ -107,6 +107,15 @@
*/
virtual bool supportsCodeGen() { return true; }
+ /**
+ * Whether or not additional functions should be looked for during CFG analysis.
+ * Code that was normally unreachable will be treated as starting a new function.
+ * Note: You will need a post-processing step to add the necessary metadata to the functions.
+ *
+ * @return True if yes, false if no.
+ */
+ virtual bool detectMoreFuncs() { return false; }
+
FuncMap _functions; ///< Map to functions in the current script, indexed by starting address.
};
Modified: tools/branches/gsoc2010-decompiler/decompiler/kyra/disassembler.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/kyra/disassembler.cpp 2010-08-05 00:28:22 UTC (rev 51747)
+++ tools/branches/gsoc2010-decompiler/decompiler/kyra/disassembler.cpp 2010-08-05 01:14:31 UTC (rev 51748)
@@ -555,36 +555,8 @@
for (InstIterator it = _insts.begin(); it != _insts.end(); ++it)
addrMap[it->_address] = it;
- // Function detection
- uint16 nextFunc = 0;
- // Process candidate entry points
-/* for (std::set<uint16>::iterator it = jumpTargets.begin(); it != jumpTargets.end(); ++it) {
- // If candidate was already placed inside a function, skip it
- if (_insts[*it]._address < nextFunc)
- continue;
-*/ // Determine function end point
- bool lastWasPop = false;
-
- for (int i = 0 ; _insts[i]._address < minFuncAddr; i++) {
-// if (_insts[i]._address < *it)
-// continue;
- // Kyra2 sometimes has an addSP instruction between the two popPos instrucitons, so we ignore those
- if (_insts[i]._name.compare("addSP") == 0)
- continue;
-
- if ((lastWasPop && _insts[i]._name.compare("popPos") == 0) || _insts[i+1]._address == minFuncAddr) {
- _engine->_functions[_insts[nextFunc]._address] = Function(addrMap[_insts[nextFunc]._address], addrMap[_insts[i+1]._address]);
- nextFunc = i+1;
-// break;
- }
-
- lastWasPop = (_insts[i]._name.compare("popPos") == 0);
- }
-// }
-
// Add metadata to newly found functions
for (FuncMap::iterator it = _engine->_functions.begin(); it != _engine->_functions.end(); ++it) {
- std::clog << boost::format("Processing function at 0x%08X\n") % it->first;
std::stringstream s;
s << boost::format("sub0x%X") % it->second._startIt->_address;
int maxArg = 0;
@@ -609,12 +581,13 @@
}
// Correct jumps to functions so they're treated as calls
+ bool lastWasPushPos = false;
for (InstIterator it = _insts.begin(); it != _insts.end(); ++it) {
if (it->_type == kJump || it->_type == kCondJump) {
- if (_engine->_functions.find(it->_params[0].getUnsigned()) != _engine->_functions.end()) {
+ if (lastWasPushPos || _engine->_functions.find(it->_params[0].getUnsigned()) != _engine->_functions.end()) {
it->_type = kCall;
- std::clog << boost::format("Changed instruction at 0x%08X to call\n") % it->_address;
}
}
+ lastWasPushPos = (it->_name.compare("pushPos") == 0);
}
}
Modified: tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.cpp
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.cpp 2010-08-05 00:28:22 UTC (rev 51747)
+++ tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.cpp 2010-08-05 01:14:31 UTC (rev 51748)
@@ -35,3 +35,7 @@
// TODO
return NULL;
}
+
+bool Kyra::Engine::detectMoreFuncs() {
+ return true;
+}
Modified: tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.h
===================================================================
--- tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.h 2010-08-05 00:28:22 UTC (rev 51747)
+++ tools/branches/gsoc2010-decompiler/decompiler/kyra/engine.h 2010-08-05 01:14:31 UTC (rev 51748)
@@ -39,6 +39,7 @@
uint32 getDestAddress(ConstInstIterator it) const;
::CodeGenerator *getCodeGenerator(std::ostream &output);
bool supportsCodeGen() { return false; }
+ bool detectMoreFuncs();
std::vector<std::string> _textStrings;
};
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