[Scummvm-cvs-logs] SF.net SVN: scummvm:[55832] tools/trunk/decompiler

pidgeot at users.sourceforge.net pidgeot at users.sourceforge.net
Tue Feb 8 23:17:39 CET 2011


Revision: 55832
          http://scummvm.svn.sourceforge.net/scummvm/?rev=55832&view=rev
Author:   pidgeot
Date:     2011-02-08 22:17:39 +0000 (Tue, 08 Feb 2011)

Log Message:
-----------
DECOMPILER: Pure grouping option

The existing grouping algorithm doesn't work with non-stack-based
engines. Because dot is unable the large amount of vertices you get as a
result, this prevents visualization of the code flow. To get around
that, pure grouping provides an alternative which only considers
branches. This creates the minimal amount of vertices in the graph,
making it much easier for dot to layout the graph.

Modified Paths:
--------------
    tools/trunk/decompiler/control_flow.cpp
    tools/trunk/decompiler/doc/cfg.tex
    tools/trunk/decompiler/doc/engine.tex
    tools/trunk/decompiler/engine.h

Modified: tools/trunk/decompiler/control_flow.cpp
===================================================================
--- tools/trunk/decompiler/control_flow.cpp	2011-02-08 20:52:26 UTC (rev 55831)
+++ tools/trunk/decompiler/control_flow.cpp	2011-02-08 22:17:39 UTC (rev 55832)
@@ -311,18 +311,21 @@
 			continue;
 		}
 
-		// If group has no instructions with stack effect >= 0, don't merge on balanced stack
-		bool forceMerge = true;
-		ConstInstIterator it = grCur->_start;
-		do {
-			if ((*it)->_stackChange >= 0)
-				forceMerge = false;
-			++it;
-		} while (grCur->_start != grCur->_end && it != grCur->_end);
+		// This part is only relevant if we use the stack level.
+		if (!_engine->usePureGrouping()) {
+			// If group has no instructions with stack effect >= 0, don't merge on balanced stack
+			bool forceMerge = true;
+			ConstInstIterator it = grCur->_start;
+			do {
+				if ((*it)->_stackChange >= 0)
+					forceMerge = false;
+				++it;
+			} while (grCur->_start != grCur->_end && it != grCur->_end);
 
-		// Group ends when stack is balanced, unless just before conditional jump
-		if (stackLevel == expectedStackLevel && !forceMerge && !(*nextInst)->isCondJump()) {
-			continue;
+			// Group ends when stack is balanced, unless just before conditional jump
+			if (stackLevel == expectedStackLevel && !forceMerge && !(*nextInst)->isCondJump()) {
+				continue;
+			}
 		}
 
 		// All checks passed, merge groups

Modified: tools/trunk/decompiler/doc/cfg.tex
===================================================================
--- tools/trunk/decompiler/doc/cfg.tex	2011-02-08 20:52:26 UTC (rev 55831)
+++ tools/trunk/decompiler/doc/cfg.tex	2011-02-08 22:17:39 UTC (rev 55832)
@@ -29,6 +29,7 @@
 If this step is not enabled, and no functions have been defined before the control flow analysis is started, there will still be added a single function covering the entire script. This is done to avoid having a special case in the code, and it will not affect the output of your script in any way.
 
 \subsection{Group generation}
+\label{sec:groupgen}
 Groups are initially formed according to these rules:
 \begin{itemize}
 \item If the next instruction is a jump or a return, end the group here.
@@ -37,10 +38,14 @@
 \item If the current instruction brings the stack level to the same as the start of the current group, and at least one instruction with a non-negative stack effect exists in the group, end the group here.
 \end{itemize}
 
-Unreachable code will not be processed in the group generation, but will remain as individual instructions.
+The final two rules are based on a property of stack-based engines: when the stack becomes balanced, as defined by these two rules, this indicates that the current group corresponds to a single line of code. This property of the groups can be helpful when performing code generation, since it adds some context -- e.g., conditions are placed in a group of their own.
 
+However, this only works for stack-based engines; for a non-stack-based engine, each instruction ends up in a group of its own, which is particularly bad for visualization of the code flow, since dot tends to choke on the large amount of vertices resulting from this. For this reason, engines are able to request \emph{pure grouping} via the virtual \code{usePureGrouping} method, mentioned in Section~\vref{sec:addingengine}. In pure grouping, only the first two rules are applied, creating the minimum number of groups for any grouping algorithm.
+
 Prior to applying these rules, a depth-first search is performed to calculate the expected stack level at each instruction. If multiple paths are found to the same instruction, a warning will be output if the expected stack level from each path differs.
 
+Unreachable code will not be processed during the group generation, but will remain as individual instructions.
+
 \subsection{Short-circuit detection}
 \emph{NOTE: This feature is currently disabled.}
 
@@ -49,7 +54,7 @@
 The rules used to detect if two consecutive groups $A$ and $B$ are oart of the same short-circuited check are as follows:
 \begin{itemize}
 \item Both group $A$ and $B$ end with a conditional jump (they have two possible successors each)
-\item For each outgoing edge from A, the edge must either go to B, or to a successor of B - in other words, merging may not add any new successors. More formally, $\text{succ}(A) \subseteq \{B\} \cup \text{succ}(B)$ , where $\text{succ}(X)$ is the set of possible successors for the group $X$.
+\item For each outgoing edge from A, the edge must either go to B, or to a successor of B -- in other words, merging may not add any new successors. More formally, $\text{succ}(A) \subseteq \{B\} \cup \text{succ}(B)$, where $\text{succ}(X)$ is the set of possible successors for the group $X$.
 \end{itemize}
 
 \subsection{Construct detection}

Modified: tools/trunk/decompiler/doc/engine.tex
===================================================================
--- tools/trunk/decompiler/doc/engine.tex	2011-02-08 20:52:26 UTC (rev 55831)
+++ tools/trunk/decompiler/doc/engine.tex	2011-02-08 22:17:39 UTC (rev 55832)
@@ -6,6 +6,7 @@
 If you need to store metadata about the script, you can add the necessary fields to your engine class and store the information there, as the same instance will be used throughout the decompilation process.
 
 \subsection{Adding a new engine}
+\label{sec:addingengine}
 In order to make the decompiler use the code you write to decompile code for some engine, it must be registered in the program. To do so, include the header file for your engine in \code{decompiler.cpp}, and use the \code{ENGINE} macro defined there to register your engine with the program.
 
 This macro takes 3 parameters: the engine ID, a description of the engine, and the name of the \code{Engine} subclass used to create the classes used for the various steps of the process. The ID is entered by the user to signify the engine where the script originates from, and the description is a descriptive text which will be shown when the user requests a list of the supported engines. In general, you should place the files for your engine in a folder with the same name as the engine ID you use.
@@ -21,11 +22,12 @@
 \item \code{supportsCodeFlow} and \code{supportsCodeGen}, which can be used to stop the decompiler from going any further after disassembly or code flow analysis, respectively. This is helpful when working on a brand new engine, so you can take one step at a time without having to remember to use the right command-line switch. If you do not override these methods, the decompiler will go through all steps.
 \item \code{detectMoreFuncs} allows you to tell the control flow analysis to automatically detect functions based on reachability. See Section~\vref{sec:autofunc} for details. By default, this is turned off; engines must opt-in to this feature.
 \item \code{postCFG}, which is a post-processing step called after control flow analysis. If you override \code{detectMoreFuncs} to return true, you must also override this function to process any newly found functions. A default implementation which does nothing is already provided in case you do not need to do any post-processing.
+\item \code{usePureGrouping} is used to toggle ``pure'' grouping. In pure grouping, stack levels are ignored during group generation in the control flow analysis. By default, this is turned off. See Section~\vref{sec:groupgen} for details.
 \end{itemize}
 
 Additionally, if your engine is not stack-based, you may not wish to see the stack effect when reviewing the disassembly or code flow graph. You can disable this by calling \code{setOutputStackEffect(false)} from e.g. your Engine constructor. The method is defined in instruction.h, which you will have to include.
 
-It is important to realize that you do not necessarily need to implement a completely new code generator and disassembler for every engine; for variations on the same engine, you can reuse the existing classes and simply send in any extra information required. In particular, code generators are likely to be reusable without change for different versions of the same engine - e.g., the Kyra2 code generator will likely work for all Kyra games.
+It is important to realize that you do not necessarily need to implement a completely new code generator and disassembler for every engine; for variations on the same engine, you can reuse the existing classes and simply send in any extra information required. In particular, code generators are likely to be reusable without change for different versions of the same engine -- e.g., the Kyra2 code generator will likely work for all Kyra games.
 
 For this purpose, the user may optionally specify an \emph{engine variant}, which is a string that will be passed to your Engine. If you make use of this feature, you should also override \code{getVariants} to specify which variants your engine supports. This list will be displayed to the user if they specify an engine while using the \code{-h} option.
 

Modified: tools/trunk/decompiler/engine.h
===================================================================
--- tools/trunk/decompiler/engine.h	2011-02-08 20:52:26 UTC (rev 55831)
+++ tools/trunk/decompiler/engine.h	2011-02-08 22:17:39 UTC (rev 55832)
@@ -128,6 +128,15 @@
 	virtual void getVariants(std::vector<std::string> &variants) const { };
 
 	std::string _variant; ///< Engine variant to use for the script.
+
+	/**
+	 * Whether or not to use "pure" grouping during code flow analysis.
+	 * With pure grouping, code flow analysis only looks at branches when merging.
+	 * This method may be more appropriate for non-stack-based engines.
+	 *
+	 * @return True if pure grouping should be used, false if not.
+	 */
+	virtual bool usePureGrouping() const { return false; }
 };
 
 #endif


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