[Scummvm-cvs-logs] SF.net SVN: scummvm:[42310] tools/branches/gsoc2009-decompiler/decompiler
kjdf at users.sourceforge.net
kjdf at users.sourceforge.net
Thu Jul 9 19:45:13 CEST 2009
Revision: 42310
http://scummvm.svn.sourceforge.net/scummvm/?rev=42310&view=rev
Author: kjdf
Date: 2009-07-09 17:45:12 +0000 (Thu, 09 Jul 2009)
Log Message:
-----------
decompiler: moved Block to a separate file
Modified Paths:
--------------
tools/branches/gsoc2009-decompiler/decompiler/Makefile
tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
tools/branches/gsoc2009-decompiler/decompiler/graph.h
tools/branches/gsoc2009-decompiler/decompiler/instruction.h
tools/branches/gsoc2009-decompiler/decompiler/misc.h
tools/branches/gsoc2009-decompiler/decompiler/syntax.h
Added Paths:
-----------
tools/branches/gsoc2009-decompiler/decompiler/block.cpp
tools/branches/gsoc2009-decompiler/decompiler/block.h
Modified: tools/branches/gsoc2009-decompiler/decompiler/Makefile
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/Makefile 2009-07-09 17:44:32 UTC (rev 42309)
+++ tools/branches/gsoc2009-decompiler/decompiler/Makefile 2009-07-09 17:45:12 UTC (rev 42310)
@@ -75,12 +75,12 @@
.PHONY: all clean test
-decompiler$(EXEEXT): decompiler.o graph.o misc.o
+decompiler$(EXEEXT): decompiler.o graph.o misc.o block.o
$(CXX) $(LDFLAGS) -o $@ $+ -lboost_program_options
-decompiler.o: graph.h instruction.h misc.h parser.h reader.h syntax.h
+decompiler.o: instruction.h misc.h parser.h reader.h syntax.h
+graph.o: graph.h
-
######################################################################
# The build rules follow - normally you should have no need to
# touch whatever comes after here.
Added: tools/branches/gsoc2009-decompiler/decompiler/block.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/block.cpp (rev 0)
+++ tools/branches/gsoc2009-decompiler/decompiler/block.cpp 2009-07-09 17:45:12 UTC (rev 42310)
@@ -0,0 +1,47 @@
+#include "block.h"
+
+#include <boost/foreach.hpp>
+
+using namespace boost;
+using namespace std;
+
+#ifndef foreach
+#define foreach BOOST_FOREACH
+#endif
+
+
+Block::Block() : _interval(), _number(), _loopHead(), _loopFollow(), _loopLatch(), _visited(), _dominator(), _ifFollow(), _component() {
+}
+
+
+Block::~Block() {
+}
+
+
+bool Block::inLoop(Block *head) {
+ return _interval == head && head->_loopLatch->_number <= _number && _number < head->_number;
+}
+
+
+Block *Block::nonFollowEdge() {
+ foreach (Block *u, _out)
+ if (u != _loopFollow)
+ return u;
+ return 0;
+}
+
+
+Block *Block::outEdgeOutsideLoop(Block *head) {
+ foreach (Block *u, _out)
+ if (!u->inLoop(head) && u != head)
+ return u;
+ return 0;
+}
+
+
+string Block::toString() {
+ ostringstream ret;
+ foreach (Instruction *instruction, _instructions)
+ ret << instruction->toString();
+ return ret.str();
+}
Property changes on: tools/branches/gsoc2009-decompiler/decompiler/block.cpp
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: svn:eol-style
+ native
Added: tools/branches/gsoc2009-decompiler/decompiler/block.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/block.h (rev 0)
+++ tools/branches/gsoc2009-decompiler/decompiler/block.h 2009-07-09 17:45:12 UTC (rev 42310)
@@ -0,0 +1,43 @@
+#ifndef BLOCK_H
+#define BLOCK_H
+
+#include "instruction.h"
+
+#include <list>
+
+#include <boost/utility.hpp>
+
+
+enum LoopType {
+ PRE_TESTED,
+ POST_TESTED,
+ ENDLESS
+};
+
+
+struct Block : boost::noncopyable {
+
+ bool _visited;
+ Block *_dominator; // immediate dominator
+ Block *_ifFollow; // block is header node for if, branches converge at _ifFollow
+ Block *_interval; // header node of the interval this block belongs to
+ Block *_loopFollow; // if not null, this block is a loop header, and follow is a first block after exit
+ Block *_loopHead; // if not null, this is a latching block
+ Block *_loopLatch; // if not null, this block is a loop header, and latch is the last block in the loop
+ Block *_primitive; // interval header of the graph from which this graph has been derived
+ Block *_component;
+ LoopType _loopType;
+ int _number; // number in post-order
+ std::list<Block*> _in;
+ std::list<Block*> _out;
+ std::list<Instruction*> _instructions;
+
+ Block();
+ ~Block();
+ bool inLoop(Block *head);
+ Block *nonFollowEdge();
+ Block *outEdgeOutsideLoop(Block *head);
+ std::string toString();
+};
+
+#endif
Property changes on: tools/branches/gsoc2009-decompiler/decompiler/block.h
___________________________________________________________________
Added: svn:mime-type
+ text/plain
Added: svn:eol-style
+ native
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.cpp
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-09 17:44:32 UTC (rev 42309)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.cpp 2009-07-09 17:45:12 UTC (rev 42310)
@@ -1,18 +1,60 @@
+#include "graph.h"
+
#include <algorithm>
-#include "graph.h"
+#include <boost/foreach.hpp>
+#include <boost/utility.hpp>
+using namespace boost;
using namespace std;
+#ifndef foreach
+#define foreach BOOST_FOREACH
+#endif
-void componentVisit(Block *u, Block *head);
-Block *dominatorIntersect(Block *u, Block *v);
-std::list<Block*> inPostOrder(std::list<Block*> &blocks);
-int orderVisit(Block *u, int number);
-bool postOrderCompare(Block *a, Block *b);
+void componentVisit(Block *u, Block *head) {
+ if (u->_component)
+ return;
+ u->_component = head;
+ foreach (Block *v, u->_in)
+ componentVisit(v, head);
+}
+Block *dominatorIntersect(Block *u, Block *v) {
+ while (u != v) {
+ while (u->_number < v->_number)
+ u = u->_dominator;
+ while (v->_number < u->_number)
+ v = v->_dominator;
+ }
+ return u;
+}
+
+
+bool postOrderCompare(Block *a, Block *b) {
+ return a->_number < b->_number;
+}
+
+list<Block*> inPostOrder(list<Block*> &blocks) {
+ list<Block*> ret(blocks);
+ ret.sort(postOrderCompare);
+ return ret;
+}
+
+
+int orderVisit(Block *u, int number) {
+ u->_number = -1;
+ foreach (Block *v, u->_out)
+ if (!v->_number)
+ number = orderVisit(v, number);
+ u->_number = ++number;
+ return number;
+}
+
+
+
ControlFlowGraph::ControlFlowGraph() : _entry() {
}
@@ -23,6 +65,39 @@
}
+Block *ControlFlowGraph::addBlock(list<Instruction*>::iterator first, list<Instruction*>::iterator last) {
+ Block* block = new Block;
+ _blocks.push_back(block);
+ copy(first, last, back_inserter(block->_instructions));
+ return block;
+}
+
+
+void ControlFlowGraph::addBlocksFromScript(list<Instruction*>::iterator scriptBegin, list<Instruction*>::iterator scriptEnd) {
+ Jump *jump;
+ for (list<Instruction*>::iterator it = scriptBegin; it != scriptEnd; it++)
+ if ((jump = dynamic_cast<Jump*>(*it))) {
+ _targets[jump->target()] = 0;
+ if (next(it) != scriptEnd)
+ _targets[(*next(it))->_addr] = 0;
+ }
+ list<Instruction*>::iterator first = scriptBegin;
+ for (list<Instruction*>::iterator last = scriptBegin; last != scriptEnd; last++) {
+ if (next(last) == scriptEnd || contains(_targets, (*next(last))->_addr)) {
+ _targets[(*first)->_addr] = addBlock(first, next(last));
+ first = next(last);
+ }
+ }
+ foreach (Block *block, _blocks) {
+ if ((jump = dynamic_cast<Jump*>(block->_instructions.back())))
+ addEdge(block, _targets[jump->target()]);
+ map<address_t, Block*>::iterator succ = next(_targets.find(block->_instructions.front()->_addr));
+ if (succ != _targets.end() && (!jump || dynamic_cast<CondJump*>(jump)))
+ addEdge(block, succ->second);
+ }
+}
+
+
void ControlFlowGraph::addEdge(Block *from, Block *to) {
from->_out.push_back(to);
to->_in.push_back(from);
@@ -31,7 +106,7 @@
void ControlFlowGraph::assignComponents() {
orderBlocks();
- std::list<Block*> blocks = inPostOrder(_blocks);
+ list<Block*> blocks = inPostOrder(_blocks);
blocks.reverse();
foreach (Block *u, blocks)
componentVisit(u, u);
@@ -39,14 +114,14 @@
void ControlFlowGraph::assignDominators() {
- std::list<Block*> blocks = inPostOrder(_blocks);
+ list<Block*> blocks = inPostOrder(_blocks);
blocks.reverse();
blocks.remove(_entry);
_entry->_dominator = _entry;
for (bool changed = true; changed; ) {
changed = false;
foreach (Block *u, blocks) {
- std::list<Block*>::iterator it = u->_in.begin();
+ list<Block*>::iterator it = u->_in.begin();
while (!(*it)->_dominator)
it++;
Block *dom = *it++; // first processed predecessor
@@ -67,7 +142,7 @@
// a node belongs to an interval, if all its immediate predecessors belong the given interval
// otherwise it is an interval header
void ControlFlowGraph::assignIntervals() {
- std::list<Block*> intervals;
+ list<Block*> intervals;
intervals.push_back(_entry);
foreach (Block *interval, intervals) {
interval->_interval = interval;
@@ -94,33 +169,13 @@
}
-void componentVisit(Block *u, Block *head) {
- if (u->_component)
- return;
- u->_component = head;
- foreach (Block *v, u->_in)
- componentVisit(v, head);
-}
-
-
-Block *dominatorIntersect(Block *u, Block *v) {
- while (u != v) {
- while (u->_number < v->_number)
- u = u->_dominator;
- while (v->_number < u->_number)
- v = v->_dominator;
- }
- return u;
-}
-
-
// a derived graph, given set of intervals, is a graph in which
// all intervals have been collapsed to a single node, and edge
// exists between nodes if there are edges crossing corresponding
// intervals in the original graph
void ControlFlowGraph::extendIntervals() {
ControlFlowGraph d;
- std::map<Block*, Block*> trans;
+ map<Block*, Block*> trans;
foreach (Block *interval, intervals()) {
trans[interval] = d.addBlock(interval->_instructions.begin(), interval->_instructions.end());
trans[interval]->_primitive = interval;
@@ -138,8 +193,8 @@
}
-string ControlFlowGraph::graphvizEscapeLabel(const std::string &s) {
- std::string ret;
+string graphvizEscapeLabel(const string &s) {
+ string ret;
foreach (char c, s) {
if (c == '\n' || c == '"' || c == '\\')
ret.push_back('\\');
@@ -148,8 +203,8 @@
return ret;
}
-std::list<Block*> ControlFlowGraph::components() {
- std::list<Block*> ret;
+list<Block*> ControlFlowGraph::components() {
+ list<Block*> ret;
assignComponents();
foreach (Block *u, _blocks)
if (u->_component == u)
@@ -157,12 +212,12 @@
return ret;
}
-string ControlFlowGraph::graphvizToString(const std::string &fontname, int fontsize) {
- std::stringstream ret;
- ret << "digraph G {" << std::endl;
+string ControlFlowGraph::graphvizToString(const string &fontname, int fontsize) {
+ stringstream ret;
+ ret << "digraph G {" << endl;
foreach (Block *interval, intervals()) {
- ret << "subgraph " << '"' << "cluster_" << interval << '"' << " {" << std::endl;
- ret << "style=dotted;" << std::endl;
+ ret << "subgraph " << '"' << "cluster_" << interval << '"' << " {" << endl;
+ ret << "style=dotted;" << endl;
foreach (Block *u, _blocks)
if (u->_interval == interval) {
ret << '"' << u << "\"[";
@@ -175,28 +230,28 @@
ret << ", dom=" << u->_dominator->_number;
if (u->_loopFollow)
ret << ", loop_type=" << (u->_loopType == PRE_TESTED ? "pre_tested" : u->_loopType == POST_TESTED ? "post_tested" : "endless");
- ret << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << std::endl;
+ ret << ">\\n" << graphvizEscapeLabel(u->toString()) << "\"];" << endl;
}
- ret << "}" << std::endl;
+ ret << "}" << endl;
}
foreach (Block *u, _blocks) {
bool hadFollow = false;
foreach (Block *v, u->_out) {
hadFollow |= v == u->_loopFollow;
- ret << '"' << u << "\" -> \"" << v << '"' << (v == u->_loopFollow ? "[color=blue]" : "") << ";" << std::endl;
+ ret << '"' << u << "\" -> \"" << v << '"' << (v == u->_loopFollow ? "[color=blue]" : "") << ";" << endl;
}
if (u->_loopFollow && !hadFollow)
- ret << '"' << u << "\" -> \"" << u->_loopFollow << '"' << "[color=blue,style=dashed];" << std::endl;
+ ret << '"' << u << "\" -> \"" << u->_loopFollow << '"' << "[color=blue,style=dashed];" << endl;
if (u->_ifFollow)
- ret << '"' << u << "\" -> \"" << u->_ifFollow << '"' << "[color=red,style=dashed];" << std::endl;
+ ret << '"' << u << "\" -> \"" << u->_ifFollow << '"' << "[color=red,style=dashed];" << endl;
}
- ret << "}" << std::endl;
+ ret << "}" << endl;
return ret.str();
}
void ControlFlowGraph::ifStruct() {
- std::list<Block*> unresolved;
+ list<Block*> unresolved;
foreach (Block *u, inPostOrder(_blocks))
// TODO how will this work with 2-way head and 2-way latch loops - on latch node? how are loops going to be structured anyway
if (u->_out.size() == 2 && !((u->_loopLatch && u->_loopType == PRE_TESTED) || u->_loopHead)) {
@@ -215,15 +270,8 @@
}
-std::list<Block*> inPostOrder(std::list<Block*> &blocks) {
- std::list<Block*> ret(blocks);
- ret.sort(postOrderCompare);
- return ret;
-}
-
-
list<Block*> ControlFlowGraph::intervals() {
- std::list<Block*> ret;
+ list<Block*> ret;
assignIntervals();
foreach (Block *u, _blocks)
if (u->_interval == u)
@@ -252,6 +300,7 @@
return ret;
}
+
// for each set of 'growing' intervals in derived sequence of graphs,
// every interval header is a potential loop header
// we check for back edges that don't belong to loops discovered earlier
@@ -292,21 +341,6 @@
}
-int orderVisit(Block *u, int number) {
- u->_number = -1;
- foreach (Block *v, u->_out)
- if (!v->_number)
- number = orderVisit(v, number);
- u->_number = ++number;
- return number;
-}
-
-
-bool postOrderCompare(Block *a, Block *b) {
- return a->_number < b->_number;
-}
-
-
void ControlFlowGraph::removeJumpsToJumps() {
for (bool changed = true; changed; ) {
changed = false;
@@ -323,14 +357,13 @@
}
-// there are no paths that lead from entries to an unreachable node
-// but unreachable node can still have outgoing edge to the main part
-// of the graph, and we need to remove it from predecessor lists
void ControlFlowGraph::removeUnreachableBlocks() {
foreach (Block *u, _blocks)
if (!u->_number) {
foreach (Block *v, u->_out)
v->_in.remove(u);
+ foreach (Block *v, u->_in)
+ v->_out.remove(u);
}
for (list<Block*>::iterator it = _blocks.begin(); it != _blocks.end(); )
if ((*it)->_number)
Modified: tools/branches/gsoc2009-decompiler/decompiler/graph.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-09 17:44:32 UTC (rev 42309)
+++ tools/branches/gsoc2009-decompiler/decompiler/graph.h 2009-07-09 17:45:12 UTC (rev 42310)
@@ -9,138 +9,41 @@
#include <sstream>
#include "instruction.h"
+#include "block.h"
#include "misc.h"
-enum LoopType {
- PRE_TESTED,
- POST_TESTED,
- ENDLESS
-};
-
-
-struct Block : boost::noncopyable {
-
- bool _visited;
- Block *_dominator; // immediate dominator
- Block *_ifFollow; // block is header node for if, branches converge at _ifFollow
- Block *_interval; // header node of the interval this block belongs to
- Block *_loopFollow; // if not null, this block is a loop header, and follow is a first block after exit
- Block *_loopHead; // if not null, this is a latching block
- Block *_loopLatch; // if not null, this block is a loop header, and latch is the last block in the loop
- Block *_primitive; // interval header of the graph from which this graph has been derived
- Block *_component;
- LoopType _loopType;
- int _number; // number in post-order
- std::list<Block*> _in;
- std::list<Block*> _out;
- std::list<Instruction*> _instructions;
-
- std::string toString() {
- std::ostringstream ret;
- foreach (Instruction *instruction, _instructions)
- ret << instruction->toString();
- return ret.str();
- }
-
- bool inLoop(Block *head) {
- return _interval == head && head->_loopLatch->_number <= _number && _number < head->_number;
- }
-
- Block *nonFollowEdge() {
- foreach (Block *u, _out)
- if (u != _loopFollow)
- return u;
- return 0;
- }
-
- Block *outEdgeOutsideLoop(Block *head) {
- foreach (Block *u, _out)
- if (!u->inLoop(head) && u != head)
- return u;
- return 0;
- }
-
- Block() : _interval(), _number(), _loopHead(), _loopFollow(), _loopLatch(), _visited(), _dominator(), _ifFollow(), _component() {
- }
-
- ~Block() {
- }
-};
-
-
struct ControlFlowGraph : boost::noncopyable {
Block *_entry;
std::list<Block*> _blocks;
- std::map<address_t, Block*> _targets; // helps partitioning code into basic blocks
+ std::map<address_t, Block*> _targets; // helps partitioning code into basic blocks
ControlFlowGraph();
~ControlFlowGraph();
- // create a basic block given a range of instructions
- template<typename Iterator>
- Block *addBlock(Iterator first, Iterator last) {
- Block* block = new Block;
- _blocks.push_back(block);
- copy(first, last, back_inserter(block->_instructions));
- return block;
- }
-
- // create graph from a range of instructions
- template<typename Iterator>
- void addBlocksFromScript(Iterator scriptBegin, Iterator scriptEnd) {
- Jump *jump;
- for (Iterator it = scriptBegin; it != scriptEnd; it++)
- if ((jump = dynamic_cast<Jump*>(*it))) {
- _targets[jump->target()] = 0;
- if (next(it) != scriptEnd)
- _targets[(*next(it))->_addr] = 0;
- }
- Iterator first = scriptBegin;
- for (Iterator last = scriptBegin; last != scriptEnd; last++) {
- if (next(last) == scriptEnd || contains(_targets, (*next(last))->_addr)) {
- _targets[(*first)->_addr] = addBlock(first, next(last));
- first = next(last);
- }
- }
- foreach (Block *block, _blocks) {
- if ((jump = dynamic_cast<Jump*>(block->_instructions.back())))
- addEdge(block, _targets[jump->target()]);
- std::map<address_t, Block*>::iterator succ = next(_targets.find(block->_instructions.front()->_addr));
- if (succ != _targets.end() && (!jump || dynamic_cast<CondJump*>(jump)))
- addEdge(block, succ->second);
- }
- }
-
- void setEntry(address_t entry);
-
- void loopStruct(); // fill in all information about loops
- std::list<Block*> intervals(); // partition graph into intervals and return list of header blocks
+ Block *addBlock(std::list<Instruction*>::iterator first, std::list<Instruction*>::iterator last);
+ void addBlocksFromScript(std::list<Instruction*>::iterator scriptBegin, std::list<Instruction*>::iterator scriptEnd);
+ void addEdge(Block *from, Block *to);
+ void assignComponents(); // after order
+ void assignDominators(); // after order
std::list<Block*> components();
- void ifStruct(); // fill in all information about if-then-else, must be called after loopStruct
-
- void orderBlocks(); // assign block numbers in post-order
+ std::string graphvizToString(const std::string &fontname="", int fontsize=0);
+ void orderBlocks();
void removeJumpsToJumps();
- void removeUnreachableBlocks(); // to be called after order blocks
+ void removeUnreachableBlocks(); // after order
+ void replaceEdges(Block *from, Block *oldTo, Block *newTo);
+ void setEntry(address_t entry);
- std::string graphvizToString(const std::string &fontname="", int fontsize=0);
-
- void assignIntervals(); // can be called multiple times
+ // to be removed
+ void assignIntervals();
void extendIntervals();
+ void ifStruct(); // after loopStruct
+ std::list<Block*> intervals();
bool isReducible();
- void assignDominators(); // after order
- void assignComponents(); // after order
-
-private:
+ Block *loopFollow(Block *head, Block *latch);
+ void loopStruct();
LoopType loopType(Block *head, Block *latch);
- Block *loopFollow(Block *head, Block *latch); // to be called after loopType
-
- void addEdge(Block *from, Block *to);
-
- static std::string graphvizEscapeLabel(const std::string &s);
-
- void replaceEdges(Block *from, Block *oldTo, Block *newTo);
};
#endif
Modified: tools/branches/gsoc2009-decompiler/decompiler/instruction.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/instruction.h 2009-07-09 17:44:32 UTC (rev 42309)
+++ tools/branches/gsoc2009-decompiler/decompiler/instruction.h 2009-07-09 17:45:12 UTC (rev 42310)
@@ -2,9 +2,9 @@
#define INSTRUCTION_H
#include <cstdio>
+#include <list>
#include <sstream>
#include <string>
-#include <vector>
#include "misc.h"
@@ -55,7 +55,7 @@
struct Script {
- std::vector<Instruction*> _instructions;
+ std::list<Instruction*> _instructions;
Script(Parser *parser, const char *filename) {
parser->parseFile(this, filename);
Modified: tools/branches/gsoc2009-decompiler/decompiler/misc.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/misc.h 2009-07-09 17:44:32 UTC (rev 42309)
+++ tools/branches/gsoc2009-decompiler/decompiler/misc.h 2009-07-09 17:45:12 UTC (rev 42310)
@@ -5,14 +5,7 @@
#include <sstream>
#include <iomanip>
-#include <boost/foreach.hpp>
-#include <boost/utility.hpp>
-#ifndef foreach
-#define foreach BOOST_FOREACH
-#endif
-using namespace boost;
-
typedef unsigned char uint8;
typedef short int16;
typedef unsigned short uint16;
Modified: tools/branches/gsoc2009-decompiler/decompiler/syntax.h
===================================================================
--- tools/branches/gsoc2009-decompiler/decompiler/syntax.h 2009-07-09 17:44:32 UTC (rev 42309)
+++ tools/branches/gsoc2009-decompiler/decompiler/syntax.h 2009-07-09 17:45:12 UTC (rev 42310)
@@ -10,6 +10,11 @@
#include "misc.h"
+#include <boost/foreach.hpp>
+#ifndef foreach
+#define foreach BOOST_FOREACH
+#endif
+
#include <iostream>
using namespace std;
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