SUBDIRS = handbook
-dist_noinst_DATA = annotations.tex jsr.bib
+dist_noinst_DATA = assertions.tex annotations.tex jsr.bib
EXTRA_DIST = inlining_stacktrace.txt native_threads.txt stack.txt
annotations.toc \
annotations.idx \
annotations.out \
- annotations.tex~
+ annotations.tex~ \
+ assertions.aux \
+ assertions.dvi \
+ assertions.log \
+ assertions.toc
annotations:
latex annotations
latex annotations
latex annotations
+assertions:
+ latex assertions
+ latex assertions
+
## Local variables:
## mode: Makefile
## indent-tabs-mode: t
--- /dev/null
+\documentclass{article}%
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{graphicx}
+\usepackage{listings}
+\lstloadlanguages{Java,C}
+\lstset{basicstyle=\scriptsize, numbers=left, tabsize=4, frame=none, breaklines=true}
+%-------------------------------------------
+\newtheorem{theorem}{Theorem}
+\newtheorem{acknowledgement}[theorem]{Acknowledgement}
+\newtheorem{algorithm}[theorem]{Algorithm}
+\newtheorem{axiom}[theorem]{Axiom}
+\newtheorem{case}[theorem]{Case}
+\newtheorem{claim}[theorem]{Claim}
+\newtheorem{conclusion}[theorem]{Conclusion}
+\newtheorem{condition}[theorem]{Condition}
+\newtheorem{conjecture}[theorem]{Conjecture}
+\newtheorem{corollary}[theorem]{Corollary}
+\newtheorem{criterion}[theorem]{Criterion}
+\newtheorem{definition}[theorem]{Definition}
+\newtheorem{example}[theorem]{Example}
+\newtheorem{exercise}[theorem]{Exercise}
+\newtheorem{lemma}[theorem]{Lemma}
+\newtheorem{notation}[theorem]{Notation}
+\newtheorem{problem}[theorem]{Problem}
+\newtheorem{proposition}[theorem]{Proposition}
+\newtheorem{remark}[theorem]{Remark}
+\newtheorem{solution}[theorem]{Solution}
+\newtheorem{summary}[theorem]{Summary}
+\newenvironment{proof}[1][Proof]{\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
+
+\begin{document}
+
+\title{Assertion support \\for the CACAO Virtual Machine}
+\author{{Gregor Kaufmann}
+\\0247381 033 534
+\\gregor@complang.tuwien.ac.at}
+\date{January 1, 2008}
+\maketitle
+\pagebreak
+
+\tableofcontents
+\pagebreak
+
+
+\section{Introduction to assertions in Java}
+\subsection{General Introduction}
+The assertion keyword in Java allows to assert the correctness of assumptions made in a program. It was first introdcuded in JDK 1.2 (see JSR41\footnote{http://jcp.org/aboutJava/communityprocess/review/jsr041/publicDraft.html}). An assertion works on an expression, evaluating to a boolean type, that must be true during the execution of a program (or else the execution halts and an exception gets thrown). Short example: a function that calculates from celsius to kelvin. This function might use an assertion to assure that the calculated value is not below 0.
+
+An assertion statement comes in two forms:
+\begin{itemize}
+\item \verb'assert BooleanExpression ;'
+\item \verb'assert BooleanExpression : ValueExpression ;'
+\end{itemize}
+The "BooleanExpression" can be any java expression resulting in a boolean value. If this "BoolenExpression" evalutes to false an (unnamed) AssertionError gets thrown. The second form of the assertion statement is used to generate detailed error messages: the value of "ValueExpression" gets passed to the constructor of the thrown AssertionError exception, building a more detailed error message. An assertion statement is equal to: if (BooleanExpression == false) throw new AssertionError(ValueExpression); (without the possibility to easily turn on/off this code at runtime).
+Examples:
+\begin{itemize}
+\item \verb'assert val < 10;'
+\item \verb'assert val > 99: val;'
+\item \verb'assert isValid(val): val;'
+\item \verb'assert val.isEnabled(): val.getStatus();'
+\end{itemize}
+
+\pagebreak
+\subsection{Interpreter options}
+Assertions can be turned on or off at runtime (turned off by default). The following options for the interpreter are available (\verb'>'JDK1.2 and \verb'>'CACAO-0.98):
+\begin{itemize}
+\item \verb'-ea[:<packagename>...|:<classname>]'
+\item \verb'-enableassertions[:<packagename>...|:<classname>]'
+\item \verb'-da[:<packagename>...|:<classname>]'
+\item \verb'-disableassertions[:<packagename>...|:<classname>]'
+\item \verb'-esa | -enablesystemassertions'
+\item \verb'-dsa | -disablesystemassertions}'
+\end{itemize}
+Detailed explanation of the available options:
+\begin{itemize}
+\item{\verb'-enableassertions/-ea' -- \tiny{Turns on assertions for all non-system/user classes}}
+\item{\verb'-disableassertions/-da' -- \tiny{Turns off assertions for all non-system/user classes}}
+\item{\verb'-enablesystemassertions/-esa' -- \tiny{Turns on assertions for all system/non-user classes}}
+\item{\verb'-disablesystemassertions/-dsa' -- \tiny{Turns off assertions for all system/non-user classes}}
+\item{\verb'-enableassertions/-ea:my.package...' -- \tiny{Turns on assertions for all classes in the "my.package" package (and all subpackages)}}
+\item{\verb'-disableassertions/-da:my.package...' -- \tiny{Turns off assertions for all classes in the "my.package" package (and all subpackages)}}
+\item{\verb'-enableassertions/-ea:Myclass' -- \tiny{Turns on assertions a class named "Myclass"}}
+\item{\verb'-disableassertions/-da:Myclass' -- \tiny{Turns off assertions a class named "Myclass"}}
+\end{itemize}
+Note 1: Specifing multiple class/package names is possible.
+\\
+\\
+Note 2: The assertion switches -ea/-da/-esa/-dsa are currently not implemented correctly in cacao+classpath (use cacao+openjdk or a patched classpath [see section \ref{see1}]).
+\pagebreak
+\subsection{Bytecode of an assertion statement} \label{bytecode}
+The following example shows how an assertion statement is translated into bytecode.
+\\
+\\
+I've compiled the following class with JDK-6.0 (other compilers produce slightly different bytecode).
+\begin{lstlisting}[language=Java]
+public class Test {
+ public static void main(String[] args) {
+ int x = 1;
+ assert x == 2 : x;
+ }
+}
+\end{lstlisting}
+The following bytecode gets produced:
+\\
+\begin{lstlisting}[language=Java]
+static {};
+ Code:
+ 0: ldc\_w #5; //class Test
+ 3: invokevirtual #6; //Method java/lang/Class.desiredAssertionStatus:()Z
+ 6: ifne 13
+ 9: iconst\_1
+ 10: goto 14
+ 13: iconst\_0
+ 14: putstatic #2; //Field \$assertionsDisabled:Z
+ 17: return
+\end{lstlisting}
+A static block is used to iniatilizes the boolean variable describing the assertion status of the class "Test".
+The assertion status, as set by the user/vm for, gets loaded (lines 3,4), and saved into constant\_pool[2] (line 9).
+\\
+\begin{lstlisting}[language=Java]
+public static void main(java.lang.String[]);
+ Code:
+ 0: iconst\_1
+ 1: istore\_1
+ 2: getstatic #2; //Field \$assertionsDisabled:Z
+ 5: ifne 22
+ 8: iload\_1
+ 9: iconst\_2
+ 10: if\_icmpeq 22
+ 13: new #3; //class java/lang/AssertionError
+ 16: dup
+ 17: iload\_1
+ 18: invokespecial #4; //Method java/lang/AssertionError."<init>":(I)V
+ 21: athrow
+ 22: return
+\end{lstlisting}
+The assertion status gets loaded from constant\_pool[2] (line 5), if assertions are disabled the function returns immediatly (lines 6,15). Otherwise, the assertion statement gets evaluated and an AssertionError exception gets thrown (lines 6-15).
+
+\pagebreak
+\section{Implementation of java assertions in CACAO}
+
+When I started working on the assertion support for cacao, a basic functionality to toggle assertions on and off was already implemented. It was possible to toggle assertions on and off at a systemwide level, but this only worked when cacao was used together with the GNU classpath classes. Because at least something was already implemented, I decided to start my work on cacao+classpath.
+\\
+\\
+Each class implements a method called desiredAssertionStatus that returns the desired assertion status of a class, see section \ref{bytecode} on how this is used by an assertion statement.
+\\
+\\
+The desiredAssertionStatus method in java.lang.Class of classpath looks like this:
+\begin{lstlisting}[language=Java,firstnumber=1216]
+ public boolean desiredAssertionStatus()
+ {
+ ClassLoader c = getClassLoader();
+ Object status;
+ if (c == null)
+ return VMClassLoader.defaultAssertionStatus();
+ if (c.classAssertionStatus != null)
+ synchronized (c)
+ {
+ status = c.classAssertionStatus.get(getName());
+ if (status != null)
+ return status.equals(Boolean.TRUE);
+ }
+ else
+ {
+ status = ClassLoader.StaticData.
+ systemClassAssertionStatus.get(getName());
+ if (status != null)
+ return status.equals(Boolean.TRUE);
+ }
+ if (c.packageAssertionStatus != null)
+ synchronized (c)
+ {
+ String name = getPackagePortion(getName());
+ if ("".equals(name))
+ status = c.packageAssertionStatus.get(null);
+ else
+ do
+ {
+ status = c.packageAssertionStatus.get(name);
+ name = getPackagePortion(name);
+ }
+ while (! "".equals(name) && status == null);
+ if (status != null)
+ return status.equals(Boolean.TRUE);
+ }
+ else
+ {
+ String name = getPackagePortion(getName());
+ if ("".equals(name))
+ status = ClassLoader.StaticData.
+ systemPackageAssertionStatus.get(null);
+ else
+ do
+ {
+ status = ClassLoader.StaticData.
+ systemPackageAssertionStatus.get(name);
+ name = getPackagePortion(name);
+ }
+ while (! "".equals(name) && status == null);
+ if (status != null)
+ return status.equals(Boolean.TRUE);
+ }
+ return c.defaultAssertionStatus;
+ }
+\end{lstlisting}
+The ClassLoader class stores the global assertion status for user classes and the individual status for classes and packages:
+\begin{itemize}
+\item{\verb'boolean defaultAssertionStatus'}
+\item{\verb'Map<String, Boolean> systemPackageAssertionStatus'}
+\item{\verb'Map<String, Boolean> systemClassAssertionStatus'}
+\end{itemize}
+
+\noindent The VMClassLoader class is a special class that needs to implemented by virtual machines that use the classpath classes.
+The following methods are used by the ClassLoader to initialize the variables above (in the same order):
+\begin{itemize}
+\item{\verb'boolean defaultUserAssertionStatus()'}
+\item{\verb'Map<String, Boolean> packageAssertionStatus()'}
+\item{\verb'Map<String, Boolean> classAssertionStatus()'}
+\end{itemize}
+See: java.lang.Class\footnote{http://cvs.savannah.gnu.org/viewvc/classpath/java/lang/Class.java?revision=1.54\&root=classpath\&view=markup}, java.lang.ClassLoader\footnote{http://cvs.savannah.gnu.org/viewvc/classpath/java/lang/ClassLoader.java?revision=1.62\&root=classpath\&view=markup}, java.lang.VMClassLoader\footnote{http://cvs.savannah.gnu.org/viewvc/classpath/vm/reference/java/lang/VMClassLoader.java?revision=1.16.2.18\&root=classpath\&view=markup}
+\\
+\\
+What had to be done:
+\begin{itemize}
+\item{Implement the methods: defaultUserAssertionStatus, packageAssertionStatus, classAssertionStatus}
+\item{Write a function to parse the commandline options}
+\end{itemize}
+See: src/lib/gnu/java/lang/VMClassLoader.java (section \ref{see1}), src/native/vm/gnu/java\_lang\_VMClassLoader.c (section \ref{see2}), src/vm/assertion.c (section \ref{see3}) and src/vm/assertion.c (section \ref{see4})
+\\\\
+For cacao+openjdk I could reuse most of the code I wrote for cacao+classpath:
+\\\\
+The desiredAssertionStatus method in java.lang.Class of openjdk looks like this:
+\begin{lstlisting}[language=Java, firstnumber=2849]
+public boolean desiredAssertionStatus() {
+ ClassLoader loader = getClassLoader();
+ // If the loader is null this is a system class, so ask the VM
+ if (loader == null)
+ return desiredAssertionStatus0(this);
+
+ synchronized(loader) {
+ // If the classloader has been initialized with
+ // the assertion directives, ask it. Otherwise,
+ // ask the VM.
+ return (loader.classAssertionStatus == null ?
+ desiredAssertionStatus0(this) :
+ loader.desiredAssertionStatus(getName()));
+ }
+}
+
+\end{lstlisting}
+The native function called by desiredAssertionStatus0 is JVM\_DesiredAssertionStatus, and that's the only function that had to be implemented by me to make assertions work with cacao+openjdk. I've also corrected the implementation of the JVM\_AssertionStatusDirectives function, which is used by java.lang.ClassLoader.
+\\
+\\
+See: src/native/vm/sun/jvm.c (section \ref{see5})
+
+\pagebreak
+\section{Patch overview}
+\subsection{Changed/New files}
+\begin{itemize}
+\item{\verb'configure.ac'}
+\item{\verb'm4/assertion.m4'}
+\item{\verb'src/lib/gnu/java/lang/VMClassLoader.java'}
+\item{\verb'src/native/include/Makefile.am'}
+\item{\verb'src/native/jni.h'}
+\item{\verb'src/native/vm/gnu/java_lang_VMClassLoader.c'}
+\item{\verb'src/native/vm/sun/jvm.c'}
+\item{\verb'src/vm/Makefile.am'}
+\item{\verb'src/vm/assertion.c'}
+\item{\verb'src/vm/assertion.h'}
+\item{\verb'src/vm/vm.c'}
+\item{\verb'src/vmcore/class.c'}
+\item{\verb'src/vmcore/class.h'}
+\item{\verb'src/vmcore/linker.c'}
+\item{\verb'src/vmcore/loader.c'}
+\item{\verb'configure.ac'}
+\end{itemize}
+
+\subsection{configure.ac}
+Added configure option "--enable-assertion" (turned on by default).
+\\
+Most of the assertion code will be turned off if this switch is disabled.
+\\\\
+Actual configure logic is in m4/assertion.m4.
+
+\subsection{m4/assertion.m4}
+Added autoconf logic to enable/disable building of assertion support.
+
+\subsection{src/lib/gnu/java/lang/VMClassLoader.java}
+\label{see1}
+Replaced the dummy implementations of:
+\begin{itemize}
+\item{\verb'defaultAssertionStatus'}
+\item{\verb'packageAssertionStatus'}
+\item{\verb'classAssertionStatus'}
+\end{itemize}
+
+Added:
+\begin{itemize}
+\item{\verb'defaultUserAssertionStatus'}
+\end{itemize}
+
+\noindent This function returns the user assertion status. Due to incorrect handling of user/system assertion status in GNU classpath\footnote{http://www.gnu.org/software/classpath/}, enabling (default) system assertions will also enable assertions in all user classes (a patch\footnote{http://www.mail-archive.com/classpath-patches@gnu.org/msg10400/assertion\_cp.patch} to fix this behaviour was submitted in August 07).
+\\\\
+Actual implementations now call into native code to get status.
+
+\subsection{src/native/include/Makefile.am}
+Added:
+\begin{itemize}
+\item{\verb'java_util_HashMap.h'}
+\item{\verb'java_util_Map.h'}
+\end{itemize}
+\noindent Headers needed to allow construction of Map/HashMap in native code.
+
+\subsection{src/native/jni.h}
+Removed:
+\begin{itemize}
+\item{\verb'_Jv_JavaVM->Java_java_lang_VMClassLoader_defaultAssertionStatus'}
+\end{itemize}
+\noindent This variable was used to hold the system's assertion status and was replaced by assertion\_user\_enabled and assertion\_system\_enabled.
+
+\subsection{src/native/vm/gnu/java\_lang\_VMClassLoader.c}
+\label{see2}
+This file holds native implementations of the VMClassLoader for GNU classpath.
+\\\\
+The following functions were added/replaced:
+\begin{itemize}
+\item{\verb'Java_java_lang_VMClassLoader_defaultUserAssertionStatus'}
+\end{itemize}
+\noindent Native implementation of VMClassLoader.defaultUserAssertionStatus. This function returns the default user assertion status of the system (user\_assertion\_status). Returns false if ENABLE\_ASSERTION is not defined (--enable-assertions=no).
+\begin{itemize}
+\item{\verb'Java_java_lang_VMClassLoader_defaultAssertionStatus'}
+\end{itemize}
+\noindent Previous implemention was replaced. Native implementation of VMClassLoader.defaultAssertionStatus. This function returns the default assertion status of the system (system\_assertion\_status). Returns false if ENABLE\_ASSERTION is not defined (--enable-assertions=no).
+\begin{itemize}
+\item{\verb'Java_java_lang_VMClassLoader_packageAssertionStatus0'}
+\end{itemize}
+\noindent Native implementation of VMClassLoader.packageAssertionStatus. Builds and returns a HashMap containing key and value pairs of packagenames and their assertion status (as expected by the ClassLoader). Returns an empty HashMap if ENABLE\_ASSERTION is not defined (--enable-assertions=no).
+\begin{itemize}
+\item{\verb'Java_java_lang_VMClassLoader_classAssertionStatus0'}
+\end{itemize}
+\noindent Native implementation of VMClassLoader.classAssertionStatus. Builds and returns a HashMap containing key and value pairs of classnames and their assertion status (as expected by the ClassLoader). Returns an empty HashMap if ENABLE\_ASSERTION is not defined (--enable-assertions=no).
+
+\subsection{src/native/jni.h}
+Removed:
+\begin{itemize}
+\item{\verb'_Jv_JavaVM->Java_java_lang_VMClassLoader_defaultAssertionStatus'}
+\end{itemize}
+\noindent This variable was used to hold the system's assertion status and was replaced by assertion\_user\_enabled and assertion\_system\_enabled.
+
+\subsection{src/native/vm/sun/jvm.c}
+\label{see5}
+This file holds various native implementations needed by OpenJDK\footnote{http://openjdk.java.net/}.
+\\\\
+The following functions were added/replaced:
+\begin{itemize}
+\item{\verb'JVM_DesiredAssertionStatus'}
+\end{itemize}
+\noindent Dummy implementation was replaced. Returns the desired assertion status for a given class. Returns false if ENABLE\_ASSERTION is not defined (--enable-assertions=no).
+\begin{itemize}
+\item{\verb'JVM_AssertionStatusDirectives'}
+\end{itemize}
+\noindent Previous implementation was incomplete. Builds and returns an AssertionStatusDirectives object. This object contains the names of all packages and classes and their assertion status.
+
+\subsection{src/vm/Makefile.am}
+Added (optional) building of the assertion module (assertion.c/assertion.h). Will only be built if ENABLE\_ASSERTION is defined (--enable-assertions=yes).
+
+\subsection{src/vm/assertion.c}
+\label{see3}
+This file handles the various assertion commandline options (-ea/-da/-esa/-dsa).
+
+\subsection{src/vm/assertion.h}
+\label{see4}
+Defines the following global variables:
+\begin{lstlisting}[language=C,firstnumber=46]
+extern list\_t *list\_assertion\_names;
+\end{lstlisting}
+This variable stores class/package names and their assertion status.
+\begin{lstlisting}[language=C,firstnumber=47]
+extern int32\_t assertion\_class\_count;
+\end{lstlisting}
+This variable stores the amount of classnames specified on the commandline.
+\begin{lstlisting}[language=C,firstnumber=48]
+extern int32\_t assertion\_package\_count;
+\end{lstlisting}
+This variable stores the amount of packagenames specified on the commandline.
+\begin{lstlisting}[language=C,firstnumber=49]
+extern bool assertion\_user\_enabled;
+\end{lstlisting}
+This variable stores the systemwide user default assertion status.
+\begin{lstlisting}[language=C,firstnumber=50]
+extern bool assertion_system_enabled;
+\end{lstlisting}
+This variable stores the systemwide default assertion status.
+\\\\
+Defines the following functions:
+\begin{lstlisting}[language=C,firstnumber=54]
+void assertion\_ea\_da(const char *name, bool enabled);
+\end{lstlisting}
+This function is used to initialize the variables described aboved.
+
+\subsection{src/vm/vm.c}
+Handling of assertion commandline options was added/changed. Package and classname parsing is handled by src/vm/assertion.c (assertion\_ea\_da function).
+
+\subsection{src/vmcore/class.c}
+Added class\_java\_util\_HashMap
+
+\subsection{src/vmcore/class.h}
+Added class\_java\_util\_HashMap.
+
+\subsection{src/vmcore/linker.c}
+Added linking of class\_java\_util\_HashMap.
+
+\subsection{src/vmcore/loader.c}
+Added loading of class\_java\_util\_HashMap.
+
+\end{document}
/* src/native/vm/sun_misc_Unsafe.c - sun/misc/Unsafe
- Copyright (C) 2006, 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
- R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
- C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
- Institut f. Computersprachen - TU Wien
+ Copyright (C) 2006, 2007, 2008
+ CACAOVM - Verein zu Foerderung der freien virtuellen Machine CACAO
This file is part of CACAO.
{ "putByte", "(JB)V", (void *) (intptr_t) &Java_sun_misc_Unsafe_putByte__JB },
{ "getShort", "(J)S", (void *) (intptr_t) &Java_sun_misc_Unsafe_getShort__J },
{ "putShort", "(JS)V", (void *) (intptr_t) &Java_sun_misc_Unsafe_putShort__JS },
+ { "getChar", "(J)C", (void *) (intptr_t) &Java_sun_misc_Unsafe_getChar__J },
+ { "putChar", "(JC)V", (void *) (intptr_t) &Java_sun_misc_Unsafe_putChar__JC },
{ "getInt", "(J)I", (void *) (intptr_t) &Java_sun_misc_Unsafe_getInt__J },
{ "putInt", "(JI)V", (void *) (intptr_t) &Java_sun_misc_Unsafe_putInt__JI },
{ "getLong", "(J)J", (void *) (intptr_t) &Java_sun_misc_Unsafe_getLong__J },
{ "objectFieldOffset", "(Ljava/lang/reflect/Field;)J", (void *) (intptr_t) &Java_sun_misc_Unsafe_objectFieldOffset },
{ "allocateMemory", "(J)J", (void *) (intptr_t) &Java_sun_misc_Unsafe_allocateMemory },
{ "setMemory", "(Ljava/lang/Object;JJB)V", (void *) (intptr_t) &Java_sun_misc_Unsafe_setMemory },
+ { "copyMemory", "(Ljava/lang/Object;JLjava/lang/Object;JJ)V", (void *) (intptr_t) &Java_sun_misc_Unsafe_copyMemory },
{ "freeMemory", "(J)V", (void *) (intptr_t) &Java_sun_misc_Unsafe_freeMemory },
{ "staticFieldOffset", "(Ljava/lang/reflect/Field;)J", (void *) (intptr_t) &Java_sun_misc_Unsafe_staticFieldOffset },
{ "staticFieldBase", "(Ljava/lang/reflect/Field;)Ljava/lang/Object;", (void *) (intptr_t) &Java_sun_misc_Unsafe_staticFieldBase },
}
+/*
+ * Class: sun/misc/Unsafe
+ * Method: getChar
+ * Signature: (J)C
+ */
+JNIEXPORT int32_t JNICALL Java_sun_misc_Unsafe_getChar__J(JNIEnv *env, sun_misc_Unsafe *this, int64_t address)
+{
+ uint16_t *p;
+ uint16_t value;
+
+ p = (uint16_t *) (intptr_t) address;
+
+ value = *p;
+
+ return (int32_t) value;
+}
+
+
+/*
+ * Class: sun/misc/Unsafe
+ * Method: putChar
+ * Signature: (JC)V
+ */
+JNIEXPORT void JNICALL Java_sun_misc_Unsafe_putChar__JC(JNIEnv *env, sun_misc_Unsafe *this, int64_t address, int32_t value)
+{
+ uint16_t *p;
+
+ p = (uint16_t *) (intptr_t) address;
+
+ *p = (uint16_t) value;
+}
+
+
/*
* Class: sun/misc/Unsafe
* Method: getInt
}
+/*
+ * Class: sun/misc/Unsafe
+ * Method: copyMemory
+ * Signature: (Ljava/lang/Object;JLjava/lang/Object;JJ)V
+ */
+JNIEXPORT void JNICALL Java_sun_misc_Unsafe_copyMemory(JNIEnv *env, sun_misc_Unsafe *this, java_lang_Object *srcBase, int64_t srcOffset, java_lang_Object *destBase, int64_t destOffset, int64_t bytes)
+{
+ size_t length;
+ void *src;
+ void *dest;
+
+ if (bytes == 0)
+ return;
+
+ length = (size_t) bytes;
+
+ if ((length != (uint64_t) bytes) || (bytes < 0)) {
+ exceptions_throw_illegalargumentexception();
+ return;
+ }
+
+ /* XXX Missing LLNI: We need to unwrap these objects. */
+
+ src = (void *) (((uint8_t *) srcBase) + srcOffset);
+ dest = (void *) (((uint8_t *) destBase) + destOffset);
+
+ MCOPY(dest, src, uint8_t, length);
+}
+
+
/*
* Class: sun/misc/Unsafe
* Method: freeMemory
#include "vm/jit/replace.h"
#include "vm/jit/stacktrace.h"
-#if defined(ENABLE_LSRA)
+#if defined(ENABLE_SSA)
+# include "vm/jit/optimizing/lsra.h"
+# include "vm/jit/optimizing/ssa.h"
+#elif defined(ENABLE_LSRA)
# include "vm/jit/allocator/lsra.h"
#endif
if (compileverbose)
printf("...returning - phi lifetimes where joined\n");
#endif
- return;
+ continue;
}
if (s->type == -1) {
if (compileverbose)
printf("...returning - phi lifetimes where joined\n");
#endif
- return;
+ continue;
}
tmp_i.opc = 0;
#endif
#if defined(ENABLE_PYTHON)
- if (!pythonpass_run(jd, "langauer_tarjan", "langauer_tarjan")) {
+ if (!pythonpass_run(jd, "langauer_tarjan", "main")) {
/*return NULL;*/
}
#endif
/* allocate registers */
if ((opt_lsra) && (jd->exceptiontablelength == 0)) {
jd->ls = DNEW(lsradata);
+ ssa(jd);
lsra(jd);
STATISTICS(count_methods_allocated_by_lsra++);
lsra.h \
ssa.c \
ssa.h \
+ ssa_phi.c \
+ ssa_phi.h \
+ ssa_rename.c \
+ ssa_rename.h \
graph.c \
graph.h \
dominators.c \
Authors: Christian Ullrich
+ $Id: graph.c$
*/
int graph_get_first_(graph_element *ge, graphiterator *i);
void transform_CFG(jitdata *, graphdata *);
+void graph_phi_moves(jitdata *jd, basicblock *bptr, basicblock *dst_goto);
+
#ifdef GRAPH_DEBUG_VERBOSE
void graph_print(lsradata *ls, graphdata *gd);
#endif
/*********************************************************************+
After the "original" CFG has been created, it has to be adopted for
-SSA. (inluding insertion of new Basic Blocks)
+SSA. (inluding insertion of new Basic Blocks - edge splitting)
-TODO: Do not insert blocks right now - just adopt the call graph!
- After the phi moves are determined create only the needed Blocks
**********************************************************************/
void transform_CFG(jitdata *jd, graphdata *gd) {
int i, j, k, n, num_new_blocks;
/* copy Basic Block References to ls->basicblocks */
for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
-/* if (bptr->flags >= BBREACHED) { */
- _GRAPH_ASSERT(bptr->nr < jd->basicblockcount);
- ls->basicblocks[bptr->nr + 1] = bptr;
- bptr->nr = bptr->nr+1;
-/* } */
+ _GRAPH_ASSERT(bptr->nr < jd->basicblockcount);
+ ls->basicblocks[bptr->nr + 1] = bptr;
+ bptr->nr = bptr->nr+1;
}
/* Create new Basic Blocks:
- 0, [jd->new_basicblockcount..ls->basicblockcount[ */
+ 0, [jd->basicblockcount..ls->basicblockcount[ */
/* num_new_blocks have to be inserted*/
tmp = DMNEW( basicblock, num_new_blocks);
ls->basicblocks[0]->next = ls->basicblocks[1];
if (ls->basicblockcount > jd->basicblockcount + 1) {
+
/* new Blocks have to be inserted */
+
num_succ = DMNEW(int, ls->basicblockcount);
successor = DMNEW(graph_element *, ls->basicblockcount);
/* regard the + 1 for the already inserted new BB 0 */
/* So recreate ls->var_def */
+
var_def = DMNEW(int *, ls->basicblockcount);
for(i = 0; i < jd->basicblockcount + 1; i++) {
var_def[i] = ls->var_def[i];
}
/* Now Split the edges */
+
num_new_blocks = jd->basicblockcount + 1; /* first free new block index */
for(i = 0; i < jd->basicblockcount + 1; i++) {
if (graph_has_multiple_successors(gd, i)) {/* more than one successor */
/* splite the edge from BB i to j with the new BB */
/* num_new_blocks ( i->j --> i->nnb->j)*/
/* iter_succ shows the edge from i to j */
+
graph_split_edge(gd, i, &iter, num_new_blocks);
ls->basicblocks[num_new_blocks]->indepth =
_GRAPH_ASSERT(ls->basicblocks[num_new_blocks]->outdepth ==
ls->basicblocks[j]->indepth );
-#if 0
- /* !!!! There can't be inoutvar definitions in one of these */
- /* newly inserted basicblocks !!!! */
-
- /* Add Definition */
- /* decrease nr temporarly, because ssa_set_interface*/
- /* adds 1 since it is called from stack.c, where there is */
- /* no new BB 0 inserted like now */
-
- ls->basicblocks[num_new_blocks]->nr--;
- ssa_set_interface(jd, ls->basicblocks[num_new_blocks]);
- ls->basicblocks[num_new_blocks]->nr++;
-#endif
num_new_blocks++;
}
}
ls->basicblocks[pred]->next;
ls->basicblocks[pred]->next =
ls->basicblocks[n];
+#if 1
/* generate no instructions */
ls->basicblocks[n]->icount = 1;
ls->basicblocks[n]->iinstr = NEW(instruction);
ls->basicblocks[n]->iinstr[0].opc = ICMD_NOP;
+#else
+ graph_phi_moves(jd, ls->basicblocks[n], NULL);
+#endif
} else {
/* Block n is in the Branch path */
/* link Block at the end */
/* change the Branch Target to BB i */
-
-
switch(iptr->opc) {
case ICMD_LOOKUPSWITCH:
{
/* not handled by now -> fallback to regalloc */
exit(1);
}
-
+#if 1
/* Generate the ICMD_GOTO */
ls->basicblocks[n]->icount = 1;
ls->basicblocks[n]->iinstr =
ICMD_GOTO;
ls->basicblocks[n]->iinstr->dst.block =
ls->basicblocks[succ];
+#else
+ graph_phi_moves(jd, ls->basicblocks[n], ls->basicblocks[succ]);
+#endif
}
}
}
}
+/* graph_phi_moves *************************************************************
+
+generate the instruction array for Basicblock n (== ls->basicblocks[n])
+
+IN:
+basicblock *bptr Basicblock to change with ->iinstr == NULL
+basicblock *dst_goto Destination Block for ICMD_GOTO at end of Block, or
+ NULL for no ICMD_GOTO
+
+OUT:
+bptr->iinstr points to a newly allocated instruction array containing
+ the phi moves, the optional ICMD_GOTO at the end.
+bptr->icount Count of instructions in bptr->iinstr
+
+*******************************************************************************/
+
+void graph_phi_moves(jitdata *jd, basicblock *bptr, basicblock *dst_goto) {
+ int lt_d,lt_s,i;
+ lsradata *ls;
+ instruction *iptr;
+
+ ls = jd->ls;
+
+ _GRAPH_ASSERT(ls->num_phi_moves[bptr->nr] > 0);
+ bptr->icount = ls->num_phi_moves[bptr->nr];
+ if (dst_goto != NULL)
+ bptr->icount++;
+ bptr->iinstr = iptr = DMNEW(instruction, bptr->icount);
+
+ _GRAPH_ASSERT(iptr != NULL);
+
+ /* Moves from phi functions with highest indices have to be */
+ /* inserted first, since this is the order as is used for */
+ /* conflict resolution */
+
+ for(i = ls->num_phi_moves[bptr->nr] - 1; i >= 0 ; i--) {
+ lt_d = ls->phi_moves[bptr->nr][i][0];
+ lt_s = ls->phi_moves[bptr->nr][i][1];
+
+#if defined(GRAPH_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("graph_phi_moves: BB %3i Move %3i <- %3i\n", bptr->nr,
+ lt_d, lt_s);
+#endif
+ if (lt_s == UNUSED) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf(" ... not processed \n");
+#endif
+ continue;
+ }
+
+ _GRAPH_ASSERT(d->type != -1);
+ _GRAPH_ASSERT(s->type == -1);
+
+ iptr->opc = ICMD_MOVE;
+ iptr->s1.varindex = ls->lifetime[lt_s].v_index;
+ iptr->dst.varindex = ls->lifetime[lt_d].v_index;
+ iptr++;
+ }
+
+ if (dst_goto != NULL) {
+ iptr->opc = ICMD_GOTO;
+ iptr->dst.block = dst_goto;
+ }
+}
+
#ifdef GRAPH_DEBUG_VERBOSE
void graph_print(lsradata *ls, graphdata *gd) {
int i,j;
Authors: Christian Ullrich
+ $Id: lifetimes.c $
*/
continue;
i = ls->var_0[i];
/* _LT_ASSERT( i < jd->cd->maxlocals); */
-#ifdef LT_DEBUG_VERBOSE
- if (compileverbose)
- printf("param %3i -> L %3i/%3i",p,i,t);
-#endif
+/* printf("param %3i -> L %3i/%3i\n",p,i,t); */
_LT_ASSERT(t == VAR(i)->type);
/* Param to Local init happens before normal Code */
/* real ICMD, no phi-function, no param initialisation */
_LT_ASSERT(ls->basicblocks[b_index]->iinstr != NULL);
+
iptr = ls->basicblocks[b_index]->iinstr + iindex;
if (icmd_table[iptr->opc].flags & ICMDTABLE_CALLS)
lt->savedvar = SAVEDVAR;
lt_is_live(ls, lt, b_index, iindex);
- if (iindex == -ls->varcount-1) {
+ if (iindex == -ls->ssavarcount-1) {
#ifdef LT_DEBUG_VERBOSE
if ((compileverbose))
lt->v_index, b_index, iindex);
#endif
/* iindex is the first statement of b_index */
- /* Statements -ls->max_vars-1 .. -1 are possible phi functions*/
+ /* Statements -ls->ssavarcounts-1 .. -1 are possible phi functions*/
/* lt->v_index is live-in at b_index */
pred = graph_get_first_predecessor(gd, b_index, &pred_iter);
/* look through phi functions */
- for(; prev_iindex > -ls->varcount-1; prev_iindex--)
+ for(; prev_iindex > -ls->ssavarcount-1; prev_iindex--)
if (ls->phi[b_index][-prev_iindex-1] != NULL)
break;
void lt_move_use_sites(struct lifetime *from, struct lifetime *to) {
struct site *s;
+#if 0
+ /* not anymore true for copy propagated lifetimes */
_LT_ASSERT(from->use != NULL);
+#endif
if (from->use == NULL)
return;
for(s = from->use; s->next != NULL; s = s->next);
}
}
-
if (bptr->iinstr != NULL) {
/* set iptr to last instruction of BB */
iptr = bptr->iinstr + iindex;
/* src/vm/jit/optimizing/lsra.inc - linear scan register allocator
- Copyright (C) 2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
Institut f. Computersprachen - TU Wien
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
-*/
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+ $Id: lsra.c $
+*/
#include "config.h"
#include <stdio.h>
#include "vm/jit/reg.h"
#include "vm/jit/jit.h"
-
#include "vm/jit/optimizing/graph.h"
#include "vm/jit/optimizing/lifetimes.h"
#include "vm/jit/optimizing/ssa.h"
#include "vm/jit/optimizing/lsra.h"
-#ifdef LSRA_TESTLT
-# include "vm/resolve.h"
-#include "vm/builtin.h"
-#endif
-
-
#include "toolbox/logging.h"
extern const char *string_java_lang_InternalError;
/* function prototypes */
-void lsra_init(jitdata *);
-graphdata *lsra_setup(jitdata *);
+void lsra_setup(jitdata *);
void lsra_main(jitdata *);
#ifdef LSRA_DEBUG_VERBOSE
void lsra_dump_stack(stackptr );
codegendata *cd;
registerdata *rd;
lsradata *ls;
- graphdata *gd;
#if defined(ENABLE_STATISTICS)
int locals_start;
int i,j;
#if defined(LSRA_DEBUG_VERBOSE)
if (compileverbose) {
printf("%s %s ",m->class->name->text, m->name->text);
- if (code_is_leafmethod(code))
+ if (code_is_leafmethod(jd->code))
printf("**Leafmethod**");
printf("\n");
}
{ int dummy=1; dummy++; }
#endif
#endif
-
- lsra_init(jd);
- gd = lsra_setup(jd);
+
+ lsra_setup(jd);
#if defined(ENABLE_STATISTICS)
/* find conflicts between locals for statistics */
#endif
/* Run LSRA */
lsra_main(jd);
-#ifdef LSRA_TESTLT
- test_lifetimes( jd, gd );
-#endif
+
fflush(stdout);
}
-void lsra_init(jitdata *jd)
-{
- lsradata *ls = jd->ls;
-
- /* Init LSRA Data Structures */
- /* allocate lifetimes for all Basicblocks */
-
- ls->v_index = -1;
-}
-
-graphdata *lsra_setup(jitdata *jd)
+void lsra_setup(jitdata *jd)
{
methodinfo *m;
codegendata *cd;
registerdata *rd;
lsradata *ls;
- graphdata *gd;
#if defined(ENABLE_LOOPS)
/* Loop optimization "destroys" the basicblock array */
rd = jd->rd;
ls = jd->ls;
- ssa_init(jd);
-
- /* Setup LSRA Data structures */
-
- /* Generate the Control Flow Graph */
- /* Add one for a Basic Block 0 to be inserted, so lateron */
- /* with SSA Parameter initialization is handled right */
- gd = graph_init(jd->basicblockcount + 1);
- graph_make_cfg(jd, gd);
- ssa(jd, gd);
- lt_lifeness_analysis(jd, gd);
-
#ifdef LSRA_DEBUG_VERBOSE
if (compileverbose) {
printf("Lifetimes after LifenessAnalyse: \n");
printf("Basicblockcount: %4i\n",ls->basicblockcount);
}
#endif
- return gd;
}
void lsra_reg_setup(jitdata *jd,
int_reg->nregdesc = nregdescint;
flt_reg->nregdesc = nregdescfloat;
- if (code_is_leafmethod(code)) {
+ if (code_is_leafmethod(jd->code)) {
/* Temp and Argumentregister can be used as saved registers */
int_reg->sav_top = INT_ARG_CNT + INT_TMP_CNT + INT_SAV_CNT;
int param_count;
int i,j,tmp;
- /* count number of parameters ( .i_start == -1) */
+ /* count number of parameters ( .i_start == 0) */
for (param_count=0; (param_count < lifetime_count) &&
-/* (ls->lifetime[lifetime[param_count]].i_start == -1); param_count++); */
(ls->lifetime[lifetime[param_count]].i_start == 0); param_count++);
if (param_count > 0) {
for (p=fmem; (p->next!=NULL) && (p->next->end < fm->end); p=p->next);
fm->next=p->next;
p->next=fm;
- return fm->off;
+ /* HACK: stackslots are 8 bytes on all architectures for now, I hope.
+ * -- pm
+ */
+ return fm->off * 8;
}
struct freemem *lsra_getnewmem(int *mem_use)
#ifdef LSRA_SAVEDVAR
lt->savedvar = SAVEDVAR;
#endif
- if (lt->savedvar || code_is_leafmethod(code)) {
+ if (lt->savedvar || code_is_leafmethod(jd->code)) {
/* use Saved Reg (in case of leafmethod all regs are saved regs) */
if (reg->sav_top > regsneeded) {
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
if (active[i]->i_end > lt->i_start) break;
/* make active[i]->reg available again */
- if (code_is_leafmethod(code)) {
+ if (code_is_leafmethod(jd->code)) {
/* leafmethod -> don't care about type -> put all again into */
/* reg->sav_reg */
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
ls = jd->ls;
- if (lt->savedvar || code_is_leafmethod(code)) {
+ if (lt->savedvar || code_is_leafmethod(jd->code)) {
_spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
} else {
_spill_at_intervall(lt, ls->active_tmp, &(ls->active_tmp_top));
switch (lt->type) {
case TYPE_LNG:
-#if defined(HAS_4BYTE_STACKSLOT) && !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
+#if (defined(HAS_4BYTE_STACKSLOT) && !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)) || defined (__I386__)
flags = 0;
#else
flags = 1;
Authors: Christian Ullrich
+ $Id: lsra.h,v 1.17 2005/11/22 14:36:16 christian Exp $
*/
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)<(b)?(b):(a))
-struct _backedge {
- int start;
- int end;
- int nesting;
- struct _backedge *next;
-};
-
struct site {
int b_index;
int iindex;
int nesting;
};
-/*
-struct stackslot {
- stackptr s;
- int bb;
- struct stackslot *next;
-};
-*/
-
struct lsra_register {
int *sav_reg;
int *tmp_reg;
int use;
};
-struct igraph_lookup {
- int var;
- int igraph;
-};
-
-struct igraph_interference {
- int v1;
- int v2;
- struct igraph_interference *next;
-};
-
-struct igraph_vars {
- int v;
- struct igraph_vars *next;
-};
-
-struct igraph {
- struct igraph_interference *inter;
- struct igraph_vars *vars;
-};
-
-
struct lsradata {
- /* int *var; */ /* unused entries are set to UNUSED */
- /* maps to jd->vars array */
int varcount; /* size of vars array */
int ssavarcount; /* ls->vars[0..ssavarcount[ are all locals and iovars */
/* they are regarded for ssa renaming */
int *sorted; /* BB sorted in reverse post order */
int *sorted_rev; /* BB reverse lookup of sorted */
- struct _backedge **backedge; /* backedge data structure */
- int backedge_count; /* number of backedges */
-
long *nesting; /* Nesting level of BB*/
struct lifetime *lifetime; /* array of lifetimes */
int active_tmp_top, active_sav_top;
struct lsra_exceptiontable *ex;
- int v_index; /* next free index for stack slot lifetimes */
- /* decrements from -1 */
/* SSA fields */
bitvector *var_def; /* LocalVar Definition Bitvector [0..ls->bbcount] */
int **stack;
int *stack_top;
- /* structures for phi var interference graphs */
- struct igraph_lookup **igraph_lookup; /* var to igraph index */
- int igraph_lookup_top; /* number of entries in above table */
- struct igraph *igraph; /* interference graphs */
- int igraph_top;
};
/* src/vm/jit/optimizing/ssa.c - static single-assignment form
- Copyright (C) 2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
Institut f. Computersprachen - TU Wien
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.
-*/
+ Contact: cacao@complang.tuwien.ac.at
+ Authors: Christian Ullrich
-#include "config.h"
+ $Id: $
+*/
#include <stdio.h>
#include <stdlib.h>
#include "vm/jit/optimizing/lsra.h"
#include "vm/jit/optimizing/ssa.h"
+#include "vm/jit/optimizing/ssa_rename.h"
+#include "vm/jit/optimizing/ssa_phi.h"
#if defined(SSA_DEBUG_VERBOSE)
#include "vmcore/options.h" /* compileverbose */
void copy_propagation(jitdata *jd, graphdata *gd);
void ssa_replace_use_sites(jitdata *, graphdata *, struct lifetime *,
int , worklist *);
-void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd);
-void ssa_rename_init(jitdata *jd, graphdata *gd);
-void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd);
-void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n);
void ssa_set_def(lsradata *, int , int );
void ssa_set_local_def(lsradata *, int , int );
void ssa_set_iovar(lsradata *, s4 , int , s4 *);
void ssa_set_interface(jitdata *, basicblock *, s4 *);
-void ssa_generate_phi_moves(jitdata *, graphdata *);
-int ssa_rename_def_(lsradata *ls, int a);
#ifdef SSA_DEBUG_VERBOSE
void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd);
void ssa_print_lt(lsradata *ls);
+void _ssa_print_lt(struct lifetime *lt);
void ssa_show_variable(jitdata *jd, int index, varinfo *v, int stage);
void ssa_print_phi(lsradata *, graphdata *);
#endif
SSA main procedure:
-******************************************************************************/
+SSA Algorithms are based on "modern compiler implementation in C" from andrew
+w. appel, edition 2004
+
+Corrections:
+page 441 Algorithm 19.6. Inserting phi-functions:
+
+...
+ for each Y in DF[n]
+- if Y not element of A phi [n]
++ if a not element of A phi [n]
+ insert the statment a <- ...
+...
+...
+- A phi [n] <- A phi [n] join {Y}
++ A phi [n] <- A phi [n] join {a}
+- if Y not element of A orig [n]
++ if a not element of A orig [Y]
+ W <- W join {Y}
-void ssa(jitdata *jd, graphdata *gd) {
+******************************************************************************/
+void ssa(jitdata *jd) {
struct dominatordata *dd;
lsradata *ls;
+ graphdata *gd;
+
+#if defined(ENABLE_LOOPS)
+ /* Loop optimization "destroys" the basicblock array */
+ /* TODO: work with the basicblock list */
+ if (opt_loops) {
+ log_text("lsra not possible with loop optimization\n");
+ exit(1);
+ }
+#endif
ls = jd->ls;
+ ssa_init(jd);
+ /* Generate the Control Flow Graph */
+ /* Add one for a Basic Block 0 to be inserted, so lateron */
+ /* with SSA Parameter initialization is handled right */
+
+ gd = graph_init(jd->basicblockcount + 1);
+ graph_make_cfg(jd, gd);
+
dd = compute_Dominators(gd, ls->basicblockcount);
computeDF(gd, dd, ls->basicblockcount, 0);
ssa_print_lt(ls);
}
#endif
-/* dead_code_elimination(jd, gd); */
+ if (opt_ssa_dce) {
+ dead_code_elimination(jd, gd);
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Phi after dead code elemination\n");
- ssa_print_phi(ls, gd);
- ssa_print_lt(ls);
- }
+ if (compileverbose) {
+ printf("Phi after dead code elemination\n");
+ ssa_print_phi(ls, gd);
+ ssa_print_lt(ls);
+ }
#endif
-/* copy_propagation(jd, gd); */
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Phi after copy propagation\n");
- ssa_print_phi(ls, gd);
- ssa_print_lt(ls);
}
+ if (opt_ssa_cp) {
+ copy_propagation(jd, gd);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("Phi after copy propagation\n");
+ ssa_print_phi(ls, gd);
+ ssa_print_lt(ls);
+ }
#endif
+ }
ssa_generate_phi_moves(jd, gd);
transform_BB(jd, gd);
+ lt_lifeness_analysis(jd, gd);
#ifdef SSA_DEBUG_CHECK
{
#endif
-
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
ssa_print_trees(jd, gd, dd);
#endif
+
}
/* ssa_init *******************************************************************
# if defined(SSA_DEBUG_VERBOSE)
if (compileverbose) {
printf("%s %s ",m->class->name->text, m->name->text);
- if (code_is_leafmethod(code))
+ if (code_is_leafmethod(jd->code))
printf("**Leafmethod**");
printf("\n");
}
jd->basicblockcount, jd->localcount);
#endif
- /* As first step all definitions of local variables and in/out vars are */
- /* gathered. in/outvars are coalesced for same type and depth */
- /* "normal" tempvars (just living within one basicblock are) ignored */
-
- /* ls->var holds the index to jd->vars */
+ /* As first step all definitions of local variables and in/out vars are */
+ /* gathered. in/outvars are coalesced for same type and depth */
+ /* "normal" tempvars (just living within one basicblock are) ignored */
ls->num_defs = DMNEW(int, jd->varcount);
ls->new_varindex = DMNEW(int , jd->varcount);
ls->ssavarcount = 0;
- /* Add parameters first in right order, so the new local indices */
- /* 0..p will correspond to "their" parameters */
- /* They get defined at the artificial Block 0, the real method bbs will be*/
- /* moved to start at block 1 */
+ /* Add parameters first in right order, so the new local indices */
+ /* 0..p will correspond to "their" parameters */
+ /* They get defined at the artificial Block 0, the real method bbs will */
+ /* be ed to start at block 1 */
/* don't look at already eliminated (not used) parameters (locals) */
if (v != UNUSED) {
if (( v < jd->localcount) || ( VAR(v)->flags & INOUT )) {
+
/* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
-/* _SSA_ASSERT(ls->new_varindex[v] != UNUSED); */
ssa_set_local_def(ls, b_index, v);
}
}
}
}
_SSA_ASSERT(ls->ssavarcount < jd->varcount);
+
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose) {
-
printf("ssa_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
ls->ssavarcount);
for(i = 0; i < jd->varcount; i++) {
}
ssa_set_iovar(ls, out[out_d], o_map_index, interface_map);
if (in_d == out_d) {
- if (in[in_d] != out[out_d]) {
-
- /* out interface stackslot is defined in this basic block */
-
-/* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
- }
out_d--;
in_d--;
}
else {
-
- /* in_d < out_d */
- /* out interface stackslot is defined in this basic block */
-
-/* ssa_set_def(ls, bptr->nr + 1, ls->new_varindex[out[out_d]]); */
out_d--;
}
}
}
-/* ssa_place_phi_functions *****************************************************
-
-ls->phi[n][a][p] is created and populated.
-
-For each basicblock Y in the dominance frontier of a basicblock n (0 <= n <
-ls->basicblockcount)in which a variable (0 <= a < ls->ssavarcount) is defined an
-entry in ls->phi[Y][a] is created.
-This entry is an array with the number of predecessors of Y elements + 1 elements.
-This elements are all set to the variable a and represent the phi function which
-will get ai = phi(ai1, ai2, ..., aip) after ssa_rename.
-
-*******************************************************************************/
-
-
-void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
-{
- int a,i,j,n,Y;
- bitvector *def_sites;
- bitvector *A_phi; /* [0..ls->basicblockcount[ of ls->ssavarcount Bit */
- worklist *W;
- int num_pred;
-
- lsradata *ls;
-
- ls = jd->ls;
-
- W = wl_new(ls->basicblockcount);
-
- def_sites = DMNEW(bitvector, ls->ssavarcount);
- for(a = 0; a < ls->ssavarcount; a++)
- def_sites[a] = bv_new(ls->basicblockcount);
-
- ls->phi = DMNEW(int **, ls->basicblockcount);
- A_phi = DMNEW(bitvector, ls->basicblockcount);
- for(i = 0; i < ls->basicblockcount; i++) {
- ls->phi[i] = DMNEW(int *, ls->ssavarcount);
- for(j = 0; j < ls->ssavarcount; j++)
- ls->phi[i][j] = NULL;
- A_phi[i] = bv_new(ls->ssavarcount);
- }
-
- /* copy var_def to def_sites */
- /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
-
- for(n = 0; n <= jd->basicblockcount; n++)
- for(a = 0; a < ls->ssavarcount; a++)
- if (bv_get_bit(ls->var_def[n], a))
- bv_set_bit(def_sites[a], n);
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("var Definitions:\n");
- for(i = 0; i < ls->ssavarcount; i++) {
- printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
- for(j = 0; j < ls->basicblockcount; j++) {
- if ((j % 5) == 0) printf(" ");
- if (bv_get_bit(def_sites[i], j))
- printf("1");
- else
- printf("0");
- }
- printf(" (");
-
- printf("\n");
- }
- }
-#endif
-
- for(a = 0; a < ls->ssavarcount; a++) {
-
- /* W<-def_sites(a) */
-
- for(n = 0; n < ls->basicblockcount; n++)
- if (bv_get_bit(def_sites[a],n)) {
- wl_add(W, n);
- }
-
- while (!wl_is_empty(W)) { /* W not empty */
- n = wl_get(W);
-
- for(i = 0; i < dd->num_DF[n]; i++) {
- Y = dd->DF[n][i];
- /* Node Y is in Dominance Frontier of n -> */
- /* insert phi function for a at top of Y*/
- _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
- if (bv_get_bit( A_phi[Y], a) == 0) {
- /* a is not a Element of A_phi[Y] */
- /* a <- phi(a,a...,a) to be inserted at top of Block Y */
- /* phi has as many arguments, as Y has predecessors */
-#if 0
-#if 0
- /* do not add a phi function for interface stackslots */
- /* if a predecessor is not a def site of a <==> */
- /* the block does not have the corresponding inslot*/
-
-/* if ((ls->var_to_index[a] >= 0) || */
-/* (bv_get_bit(def_sites[a], */
-/* graph_get_first_predecessor(gd, Y, &iter)))) */
-
-#endif
- /* for interface stackslots add a phi function only */
- /* if the basicblock has the corresponding incoming */
- /* stackslot -> it could be, that the stackslot is */
- /* not live anymore at Y */
-
-#endif
- num_pred = graph_get_num_predecessor(gd, Y);
- ls->phi[Y][a] = DMNEW(int, num_pred + 1);
- for (j = 0; j < num_pred + 1; j++)
- ls->phi[Y][a][j] = a;
- /* increment the number of definitions of a by one */
- /* for this phi function */
- ls->num_defs[a]++;
-
- bv_set_bit(A_phi[Y], a);
- if (bv_get_bit(ls->var_def[Y],a)==0) {
- /* Iterated Dominance Frontier Criterion:*/
- /* if Y had no definition for a insert it*/
- /* into the Worklist, since now it */
- /* defines a through the phi function */
- wl_add(W, Y);
- }
- }
- }
- }
- }
-}
-
-/* ssa_rename ******************************************************************
-
-Rename the variables a (0 <= a < ls->ssavarcount) so that each new variable
-has only one definition (SSA form).
-
-ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
-ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
- definition of each old var.
-ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
- and IOVARS.
-
-All other vars (TEMPVAR and PREALLOC) will get a new unique index above
-ls->varcount_with_indices.
-
-jd->var and jd->varcount will be set for this renamed vars.
-
-*******************************************************************************/
-
-void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd)
-{
- int i, mi, l, j, p, t;
- int type, flags;
- methoddesc *md = jd->m->parseddesc;
-
- varinfo *new_vars;
- lsradata *ls;
-
- ls = jd->ls;
-
- ssa_rename_init(jd, gd);
-
- /* Consider definition of Local Vars initialized with Arguments */
- /* in Block 0 */
- /* init is regarded as use too-> ssa_rename_use ->bullshit!!*/
- for (p = 0, l= 0; p < md->paramcount; p++) {
- t = md->paramtypes[p].type;
- mi = l * 5 + t;
- i = jd->local_map[mi];
- l++;
- if (IS_2_WORD_TYPE(t))
- l++;
- if (i == UNUSED)
- continue;
- /* !!!!! locals are now numbered as the parameters !!!! */
- /* !!!!! no additional increment for 2 word types !!!!! */
- /* this happens later on! here we still need the increment */
- /* index of var can be in the range from 0 up to not including */
- /* CD->maxlocals */
-
- /* ignore return value, since first definition gives 0 -> */
- /* no rename necessary */
-
- i = ls->new_varindex[i];
- j = ssa_rename_def_(ls, i);
- _SSA_ASSERT(j == 0);
- jd->local_map[mi] = i;
- }
- ssa_rename_(jd, gd, dd, 0);
-
-#if 0
- /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens! */
- /* if there is no use of the defined Var itself by the phi function */
- /* for a loop path, in which this var is not used, it will not be life */
- /* in this path and overwritten! */
-
- /* Invalidate all xij from phi(xi0)=xi1,xi2,xi3,..,xin with xij == xi0 */
- /* this happens if the phi function is the first definition of x or in a */
- /* path with a backedge xi has no definition */
- /* a phi(xij) = ...,xij,... with the only use and definition of xij by */
- /* this phi function would otherwise "deadlock" the dead code elemination */
- /* invalidate means set it to ls->max_vars_with_indices */
- /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in */
- /* [1,n] can be removed */
-
- for(i = 0; i < ls->ssavarcount; i++) {
- for(t = 0; t < ls->basicblockcount; t++) {
- if (ls->phi[t][i] != 0) {
- remove_phi = true;
- for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
- if (ls->phi[t][i][0] == ls->phi[t][i][p])
- ls->phi[t][i][p] = ls->varcount_with_indices;
- else
- remove_phi = false;
- }
- }
- if (remove_phi)
- ls->phi[t][i] = NULL;
- }
- }
-#endif
-
-#if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
-# if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("%s %s ",jd->m->class->name->text, jd->m->name->text);
- if (code_is_leafmethod(code))
- printf("**Leafmethod**");
- printf("\n");
- }
-# endif
- if (strcmp(jd->m->class->name->text,"fp")==0)
- if (strcmp(jd->m->name->text,"testfloat")==0)
-# if defined(SSA_DEBUG_VERBOSE)
- if (compileverbose)
- printf("12-------------------12\n");
-# else
- { int dummy=1; dummy++; }
-# endif
-#endif
- /* recreate rd->locals[][] */
- /* now only one (local_index/type) pair exists anymore */
- /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
- /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
-
- new_vars = DMNEW(varinfo, ls->vartop);
- for(i = 0; i < ls->vartop ; i++)
- new_vars[i].type = UNUSED;
- for(i = 0; i < jd->varcount; i++) {
- p = ls->new_varindex[i];
- if (p != UNUSED) {
- if (p < ls->ssavarcount)
- p = ls->var_0[p];
- new_vars[p].type = VAR(i)->type;
- new_vars[p].flags = VAR(i)->flags;
- ls->lifetime[p].v_index = p;
- ls->lifetime[p].type = VAR(i)->type;
- }
- }
-
- /* take care of newly indexed local & in/out vars */
-
- for(i = 0; i < ls->ssavarcount; i++) {
- j = ls->var_0[i];
- type = new_vars[j].type;
- flags = new_vars[j].flags;
- j++;
- for (; j < ls->var_0[i + 1]; j++) {
- new_vars[j].type = type;
- new_vars[j].flags = flags;
- ls->lifetime[j].v_index = j;
- ls->lifetime[j].type = type;
- }
- }
-
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
-
- printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
- ls->ssavarcount);
- for(i = 0; i < jd->varcount; i++) {
- printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
- ssa_show_variable(jd, i, VAR(i),0);
- j = ls->new_varindex[i];
- if ((j != UNUSED) && (j < ls->ssavarcount))
- printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
- else
- printf(" -> %3i", j);
- printf("\n");
- }
- }
-#endif
-
- jd->var = new_vars;
- jd->varcount = ls->vartop;
- jd->vartop = ls->vartop;
-
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
- ls->ssavarcount);
- for(i = 0; i < jd->varcount; i++) {
- printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
- ssa_show_variable(jd, i, VAR(i),0);
- printf("\n");
- }
- }
-#endif
-}
-
-/* ssa_rename_init *************************************************************
-
-Setup the data structure for ssa_rename
-
-ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
-ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
- definition of each old var.
-ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
- and IOVARS.
-
-All other vars (TEMPVAR and PREALLOC) will get a new unique index above
-ls->varcount_with_indices.
-
-jd->var and jd->varcount will be set for this renamed vars.
-
-*******************************************************************************/
-
-void ssa_rename_init(jitdata *jd, graphdata *gd)
-{
- int a, i, p;
- lsradata *ls;
-
- ls = jd->ls;
-
- /* set up new locals */
- /* ls->new_varindex[0..jd->varcount[ holds the new unique index */
- /* for locals and iovars */
-
- /* ls->num_defs[index] gives the number of indizes which will be created */
- /* from SSA */
-
- /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j) ..*/
- /* ls->var_0[X] will point to each LX(0) */
- /* ls->var_0[ls->ssavarcount] will hold ls->varcount_with_indices */
-
- /* as first step cummulate the num_defs array for locals and iovars */
- /* last element is the maximum var count */
-
- ls->var_0 = DMNEW(int, max(1, ls->ssavarcount + 1));
- ls->var_0[0] = 0;
- ls->varcount_with_indices = 0;
- for(i = 0; i < ls->ssavarcount; i++) {
- ls->varcount_with_indices += ls->num_defs[i];
- ls->var_0[i+1] = ls->var_0[i] + ls->num_defs[i];
- }
-
-#if 0
- /* Change the var indices in phi from La to La(0) */
-
- for(i = 0; i < ls->basicblockcount; i++)
- for (a = 0; a < ls->ssavarcount; a++)
- if (ls->phi[i][a] != NULL)
- for(p = 0; p < graph_get_num_predecessor(gd, i) + 1; p++)
- ls->phi[i][a][p] = ls->var_0[a];
-#endif
-
- /* Initialization */
-
- ls->count = DMNEW(int, max(1, ls->ssavarcount));
- ls->stack = DMNEW(int *, max(1, ls->ssavarcount));
- ls->stack_top = DMNEW(int, max(1, ls->ssavarcount));
- for(a = 0; a < ls->ssavarcount; a++) {
- ls->count[a] = 0;
- ls->stack_top[a] = 0;
-
- /* stack a has to hold number of defs of a Elements + 1 */
-
- ls->stack[a] = DMNEW(int, ls->num_defs[a] + 1);
- ls->stack[a][ls->stack_top[a]++] = 0;
- }
-
- if (ls->ssavarcount > 0) {
-
- /* Create the num_var_use Array */
-
- ls->num_var_use = DMNEW(int *, ls->basicblockcount);
- for(i = 0; i < ls->basicblockcount; i++) {
- ls->num_var_use[i] =DMNEW(int, max(1, ls->varcount_with_indices));
- for(a = 0; a < ls->varcount_with_indices; a++)
- ls->num_var_use[i][a] = 0;
- }
-
- /* Create the use_sites Array of Bitvectors*/
- /* use max(1,..), to ensure that the array is created! */
-
- ls->use_sites = DMNEW(bitvector, max(1, ls->varcount_with_indices));
- for(a = 0; a < ls->varcount_with_indices; a++)
- ls->use_sites[a] = bv_new(ls->basicblockcount);
- }
-
- /* init lifetimes */
- /* count number of TEMPVARs */
-
- ls->lifetimecount = 0;
- for(i = 0; i < jd->varcount; i++)
- if ((i >= jd->localcount) || (!(jd->var[i].flags & (INOUT | PREALLOC))))
- ls->lifetimecount++;
-
- ls->varcount = ls->varcount_with_indices + ls->lifetimecount;
-
- ls->lifetimecount = ls->varcount;
- ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
- ls->lt_used = DMNEW(int, ls->lifetimecount);
- ls->lt_int = DMNEW(int, ls->lifetimecount);
- ls->lt_int_count = 0;
- ls->lt_flt = DMNEW(int, ls->lifetimecount);
- ls->lt_flt_count = 0;
- ls->lt_mem = DMNEW(int, ls->lifetimecount);
- ls->lt_mem_count = 0;
- for (i=0; i < ls->lifetimecount; i++) {
- ls->lifetime[i].type = UNUSED;
- ls->lifetime[i].savedvar = 0;
- ls->lifetime[i].flags = 0;
- ls->lifetime[i].usagecount = 0;
- ls->lifetime[i].bb_last_use = -1;
- ls->lifetime[i].bb_first_def = -1;
- ls->lifetime[i].use = NULL;
- ls->lifetime[i].def = NULL;
- ls->lifetime[i].last_use = NULL;
- }
-
- /* for giving TEMP and PREALLOC vars a new unique index */
-
- ls->vartop = ls->varcount_with_indices;
-
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("ssa_rename_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
- ls->ssavarcount);
- for(i = 0; i < jd->varcount; i++) {
- if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
- printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
- ssa_show_variable(jd, i, VAR(i),0);
- if ((i < ls->ssavarcount) || (VAR(i)->flags & INOUT)) {
- printf(" -> %3i", ls->new_varindex[i]);
- }
- printf("\n");
- }
- }
- ssa_print_phi(ls, gd);
- }
-#endif
-}
-
-int ssa_rename_def_(lsradata *ls, int a) {
- int i;
-
- _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
- ls->count[a]++;
- i = ls->count[a] - 1;
- /* push i on stack[a] */
- _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
- ls->stack[a][ls->stack_top[a]++] = i;
- return i;
-}
-
-int ssa_rename_def(jitdata *jd, int *def_count, int a) {
- int i, a1, ret;
- lsradata *ls;
-
- ls = jd->ls;
-
- a1 = ls->new_varindex[a];
- _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
- if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
- /* local or inoutvar -> normal ssa renaming */
- _SSA_ASSERT((a < jd->localcount) || (VAR(a)->flags & INOUT));
- /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
-
- def_count[a1]++;
- i = ssa_rename_def_(ls, a1);
- ret = ls->var_0[a1] + i;
- }
- else {
- /* TEMP or PREALLOC var */
- if (a1 == UNUSED) {
- ls->new_varindex[a] = ls->vartop;
- ret = ls->vartop;
- ls->vartop++;
- _SSA_ASSERT( ls->vartop < ls->varcount);
- }
- else
- ret = a1;
- }
- return ret;
-}
-
-void ssa_rename_use_(lsradata *ls, int n, int a) {
- _SSA_CHECK_BOUNDS(a, 0, ls->varcount_with_indices);
- if (ls->ssavarcount > 0) {
- bv_set_bit(ls->use_sites[a], n);
- ls->num_var_use[n][a]++;
- }
-}
-
-int ssa_rename_use(lsradata *ls, int n, int a) {
- int a1, i;
- int ret;
-
- a1 = ls->new_varindex[a];
- _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
- if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
- /* local or inoutvar -> normal ssa renaming */
- /* i <- top(stack[a]) */
-
- _SSA_CHECK_BOUNDS(ls->stack_top[a1]-1, 0, ls->num_defs[a1]+1);
- i = ls->stack[a1][ls->stack_top[a1] - 1];
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a1]);
-
- ret = ls->var_0[a1] + i;
- }
- else {
- /* TEMP or PREALLOC var */
- if (a1 == UNUSED) {
- ls->new_varindex[a] = ls->vartop;
- ret = ls->vartop;
- ls->vartop++;
- _SSA_ASSERT( ls->vartop < ls->varcount);
- }
- else
- ret = a1;
- }
-
- return ret;
-}
-
-#ifdef SSA_DEBUG_VERBOSE
-void ssa_rename_print(instruction *iptr, char *op, int from, int to) {
- if (compileverbose) {
- printf("ssa_rename_: ");
- if (iptr != NULL)
- printf("%s ", opcode_names[iptr->opc]);
- else
- printf(" ");
-
- printf("%s: %3i->%3i\n", op, from, to);
- }
-}
-#endif
-
-void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
- int a, i, j, k, iindex, Y, v;
- int in_d, out_d;
- int *def_count;
- /* [0..ls->varcount[ Number of Definitions of this var in this */
- /* Basic Block. Used to remove the entries off the stack at the */
- /* end of the function */
- instruction *iptr;
- s4 *in, *out, *argp;
- graphiterator iter_succ, iter_pred;
- struct lifetime *lt;
-
- methoddesc *md;
- methodinfo *m;
- builtintable_entry *bte;
- lsradata *ls;
-
- ls = jd->ls;
- m = jd->m;
-
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("ssa_rename_: BB %i\n",n);
-#endif
-
- _SSA_CHECK_BOUNDS(n, 0, ls->basicblockcount);
-
- def_count = DMNEW(int, max(1, ls->ssavarcount));
- for(i = 0; i < ls->ssavarcount; i++)
- def_count[i] = 0;
-
- /* change Store of possible phi functions from a to ai*/
-
- for(a = 0; a < ls->ssavarcount; a++)
- if (ls->phi[n][a] != NULL) {
- def_count[a]++;
- /* do not mark this store as use - maybee this phi function */
- /* can be removed for unused Vars*/
- j = ls->var_0[a] + ssa_rename_def_(ls, a);
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( NULL, "phi-st", ls->phi[n][a][0], j);
-#endif
- ls->phi[n][a][0] = j;
- }
-
- in = ls->basicblocks[n]->invars;
- in_d = ls->basicblocks[n]->indepth - 1;
-
- /* change use of instack Interface stackslots except top SBR and EXH */
- /* stackslots */
-
- if ((ls->basicblocks[n]->type == BBTYPE_EXH) ||
- (ls->basicblocks[n]->type == BBTYPE_SBR)) {
- in_d--;
- }
-/* out = ls->basicblocks[n]->outvars; */
-/* out_d = ls->basicblocks[n]->outdepth - 1; */
-
-/* for(; out_d > in_d; out_d--); */
-
- for (; in_d >= 0; in_d--) {
- /* Possible Use of ls->new_varindex[jd->var[in_d]] */
- _SSA_ASSERT(ls->new_varindex[in[in_d]] != UNUSED);
-
- a = ls->new_varindex[in[in_d]];
- _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
-
- /* i <- top(stack[a]) */
-
- _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
- i = ls->stack[a][ls->stack_top[a]-1];
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
-
- /* Replace use of x with xi */
-
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
-#endif
- in[in_d] = ls->var_0[a] + i;
- lt = ls->lifetime + in[in_d];
-
- lt->v_index = in[in_d];
- lt->bb_last_use = -1;
- }
-
- iptr = ls->basicblocks[n]->iinstr;
-
- for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
-
- /* check for use (s1, s2, s3 or special (argp) ) */
-
- switch (icmd_table[iptr->opc].dataflow) {
- case DF_3_TO_0:
- case DF_3_TO_1: /* icmd has s1, s2 and s3 */
- j = ssa_rename_use(ls, n, iptr->sx.s23.s3.varindex);
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( iptr, "s3 ", iptr->sx.s23.s3.varindex, j);
-#endif
- iptr->sx.s23.s3.varindex = j;
-
- /* now "fall through" for handling of s2 and s1 */
-
- case DF_2_TO_0:
- case DF_2_TO_1: /* icmd has s1 and s2 */
- j = ssa_rename_use(ls, n, iptr->sx.s23.s2.varindex);
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( iptr, "s2 ", iptr->sx.s23.s2.varindex, j);
-#endif
- iptr->sx.s23.s2.varindex = j;
-
- /* now "fall through" for handling of s1 */
-
- case DF_1_TO_0:
- case DF_1_TO_1:
- case DF_MOVE:
- case DF_COPY:
- j = ssa_rename_use(ls, n, iptr->s1.varindex);
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( iptr, "s1 ", iptr->s1.varindex, j);
-#endif
- iptr->s1.varindex = j;
- break;
-
- case DF_INVOKE:
- case DF_BUILTIN:
- case DF_N_TO_1:
- /* do not use md->paramcount, pass-through stackslots have */
- /* to be renamed, too */
- i = iptr->s1.argcount;
- argp = iptr->sx.s23.s2.args;
- while (--i >= 0) {
- j = ssa_rename_use(ls, n, *argp);
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( iptr, "arg", *argp, j);
-#endif
- *argp = j;
- argp++;
- }
- break;
- }
-
-
- /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
- /* an optional dst - so they to be checked first */
-
- v = UNUSED;
- if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
- INSTRUCTION_GET_METHODDESC(iptr,md);
- if (md->returntype.type != TYPE_VOID)
- v = iptr->dst.varindex;
- }
- else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
- bte = iptr->sx.s23.s3.bte;
- md = bte->md;
- if (md->returntype.type != TYPE_VOID)
- v = iptr->dst.varindex;
- }
- else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
- v = iptr->dst.varindex;
- }
-
- if (v != UNUSED) {
- j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
-#endif
- iptr->dst.varindex = j;
- }
-
- /* ?????????????????????????????????????????????????????????? */
- /* Mark Def as use, too. Since param initialisation is in */
- /* var_def and this would not remove this locals, if not used */
- /* elsewhere */
- /* ?????????????????????????????????????????????????????????? */
-
- }
-
- /* change outstack Interface stackslots */
- out = ls->basicblocks[n]->outvars;
- out_d = ls->basicblocks[n]->outdepth - 1;
-
- for (;out_d >= 0; out_d--) {
- /* Possible Use of ls->new_varindex[jd->var[out_d]] */
- _SSA_ASSERT(ls->new_varindex[out[out_d]] != UNUSED);
-
- a = ls->new_varindex[out[out_d]];
- _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
-
- /* i <- top(stack[a]) */
-
- _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
- i = ls->stack[a][ls->stack_top[a]-1];
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
-
- /* Replace use of x with xi */
-
-#ifdef SSA_DEBUG_VERBOSE
- ssa_rename_print( NULL, "outvar", out[out_d], ls->var_0[a]+i);
-#endif
- out[out_d] = ls->var_0[a] + i;
- lt = ls->lifetime + out[out_d];
-
- lt->v_index = out[out_d];
- lt->bb_last_use = -1;
- }
-
- /* change use in phi Functions of Successors */
-
- Y = graph_get_first_successor(gd, n, &iter_succ);
- for(; Y != -1; Y = graph_get_next(&iter_succ)) {
- _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
- k = graph_get_first_predecessor(gd, Y, &iter_pred);
- for (j = 0; (k != -1) && (k != n); j++)
- k = graph_get_next(&iter_pred);
- _SSA_ASSERT(k == n);
-
- /* n is jth Predecessor of Y */
-
- for(a = 0; a < ls->ssavarcount; a++)
- if (ls->phi[Y][a] != NULL) {
-
- /* i <- top(stack[a]) */
-
- if (ls->stack_top[a] == 1) {
- /* no definition till now in controll flow */
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Succ %3i Arg %3i \n", Y, j);
- ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
- }
-#endif
- ls->phi[Y][a][j+1] = UNUSED;
- }
- else {
- _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
- i = ls->stack[a][ls->stack_top[a]-1];
- _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
-
- /* change jth operand from a0 to ai */
-
- i = ls->var_0[a] + i;
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose) {
- printf("Succ %3i Arg %3i \n", Y, j);
- ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
- }
-#endif
- ls->phi[Y][a][j+1] = i;
- _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
- ls->varcount_with_indices);
-
- /* use by phi function has to be remembered, too */
-
- ssa_rename_use_(ls, n, ls->phi[Y][a][j+1]);
- }
-
- /* ????????????????????????????????????????????? */
- /* why was this only for local vars before ? */
- /* ????????????????????????????????????????????? */
-
- }
- }
-
- /* Call ssa_rename_ for all Childs of n of the Dominator Tree */
- for(i = 0; i < ls->basicblockcount; i++)
- if (dd->idom[i] == n)
- ssa_rename_(jd, gd, dd, i);
-
- /* pop Stack[a] for each definition of a var a in the original S */
- for(a = 0; a < ls->ssavarcount; a++) {
- ls->stack_top[a] -= def_count[a];
- _SSA_ASSERT(ls->stack_top[a] >= 0);
- }
-}
-
-
-
#ifdef SSA_DEBUG_VERBOSE
void ssa_print_trees(jitdata *jd, graphdata *gd, dominatordata *dd) {
int i,j;
printf(")\n");
}
}
-
-void ssa_print_phi(lsradata *ls, graphdata *gd) {
- int i,j,k;
-
- printf("phi Functions (varcount_with_indices: %3i):\n",
- ls->varcount_with_indices);
- for(i = 0; i < ls->basicblockcount; i++) {
- for(j = 0; j < ls->ssavarcount; j++) {
- if (ls->phi[i][j] != NULL) {
- printf("BB %3i %3i = phi(", i, ls->phi[i][j][0]);
- for(k = 1; k <= graph_get_num_predecessor(gd, i); k++)
- printf("%3i ",ls->phi[i][j][k]);
- printf(")\n");
- }
- }
- }
-
-}
-
#endif
-void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
- int a, i, j, pred;
- graphiterator iter;
- lsradata *ls;
-
- ls = jd->ls;
-
- /* count moves to be inserted at the end of each block in moves[] */
- ls->num_phi_moves = DMNEW(int, ls->basicblockcount);
- for(i = 0; i < ls->basicblockcount; i++)
- ls->num_phi_moves[i] = 0;
- for(i = 0; i < ls->basicblockcount; i++)
- for(a = 0; a < ls->ssavarcount; a++)
- if (ls->phi[i][a] != NULL) {
-#if 0
- if (ls->lifetime[ls->phi[i][a][0]].use == NULL) {
- /* Var defined (only <- SSA Form!) in this phi function */
- /* and not used anywhere -> delete phi function and set */
- /* var to unused */
-
- /* TODO: first delete use sites of arguments of phi */
- /* function */
- VAR(ls->lifetime[ls->phi[i][a][0]].v_index)->type = UNUSED;
- ls->lifetime[ls->phi[i][a][0]].def = NULL;
- ls->phi[i][a] = NULL;
- }
- else
-#endif
- {
- pred = graph_get_first_predecessor(gd, i, &iter);
- for(; pred != -1; pred = graph_get_next(&iter)) {
- ls->num_phi_moves[pred]++;
- }
- }
- }
-
- /* allocate ls->phi_moves */
- ls->phi_moves = DMNEW( int **, ls->basicblockcount);
- for(i = 0; i < ls->basicblockcount; i++) {
- ls->phi_moves[i] = DMNEW( int *, ls->num_phi_moves[i]);
- for(j = 0; j <ls->num_phi_moves[i]; j++)
- ls->phi_moves[i][j] = DMNEW(int, 2);
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
- i, ls->num_phi_moves[i]);
-#endif
- }
-
- /* populate ls->phi_moves */
- for(i = 0; i < ls->basicblockcount; i++)
- ls->num_phi_moves[i] = 0;
- for(i = 0; i < ls->basicblockcount; i++)
- for(a = 0; a < ls->ssavarcount; a++)
- if (ls->phi[i][a] != NULL) {
- pred = graph_get_first_predecessor(gd, i, &iter);
- for(j = 0; pred != -1; j++, pred = graph_get_next(&iter)) {
- /* target is phi[i][a][0] */
- /* source is phi[i][a][j+1] */
- if (ls->phi[i][a][j+1] != ls->varcount_with_indices) {
- /* valid move */
- if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
- ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
- ls->phi[i][a][0];
- ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
- ls->phi[i][a][j+1];
- }
- }
- }
- }
-}
/****************************************************************************
Optimizations
W = wl_new(ls->lifetimecount);
if (ls->lifetimecount > 0) {
- /* put all lifetimes on Worklist */
+
+ /* put all lifetimes into Worklist W */
+
for(a = 0; a < ls->lifetimecount; a++) {
- if (ls->lifetime[a].type != -1) {
+ if (ls->lifetime[a].type != UNUSED) {
wl_add(W, a);
}
}
}
/* Remove unused lifetimes */
+
while(!wl_is_empty(W)) {
+
/* take a var out of Worklist */
+
a = wl_get(W);
lt = &(ls->lifetime[a]);
- if ((lt->def == NULL) || (lt->type == -1))
+ if ((lt->def == NULL) || (lt->type == UNUSED))
+
/* lifetime was already removed -> no defs anymore */
+
continue;
- /* Remove lifetimes, which are only used in a phi function, which
- defines them! */
+ /* Remove lifetimes, which are only used in the phi function which */
+ /* defines them! */
+
remove_statement = (lt->use != NULL) && (lt->use->iindex < 0);
for(use = lt->use; (remove_statement && (use != NULL));
use = use->next)
(use->b_index == lt->def->b_index) &&
(use->iindex == lt->def->iindex);
}
+
if (remove_statement) {
#ifdef SSA_DEBUG_CHECK
+
/* def == use can only happen in phi functions */
+
if (remove_statement)
_SSA_ASSERT(lt->use->iindex < 0);
#endif
+
/* give it free for removal */
+
lt->use = NULL;
}
if (lt->use == NULL) {
+
/* Look at statement of definition of a and remove it, */
/* if the Statement has no sideeffects other than the assignemnt */
/* of a */
+
if (lt->def->iindex < 0 ) {
+
/* phi function */
/* delete use of sources , delete phi functions */
NULL);
for (i = 1;i <= graph_get_num_predecessor(gd, lt->def->b_index);
- i++)
- {
- source =
- ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
- if ((source != ls->varcount_with_indices) &&
- (source != lt->v_index)) {
+ i++) {
+ source =
+ ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
+ if ((source != ls->varcount_with_indices) &&
+ (source != lt->v_index) &&
+ (source != UNUSED)) {
- /* phi Argument was not already removed (already in
- because of selfdefinition) */
+ /* phi Argument was not already removed (already in
+ because of "selfdefinition") */
- s_lt = &(ls->lifetime[source]);
+ s_lt = &(ls->lifetime[source]);
- /* remove it */
+ /* remove it */
- lt_remove_use_site(s_lt,lt->def->b_index,
- lt->def->iindex);
+ lt_remove_use_site(s_lt,lt->def->b_index,
+ lt->def->iindex);
- /* put it on the Worklist */
+ /* put it on the Worklist */
- wl_add(W, source);
- }
+ wl_add(W, source);
}
+ }
+
/* now delete phi function itself */
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("dce: BB%3i phi for var %3i=%3i removed \n",
+ lt->def->b_index, -lt->def->iindex - 1,
+ lt->v_index);
+ }
+#endif
+
ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
- } else {
+ }
+ else {
+
/* "normal" Use by ICMD */
+
remove_statement = false;
if (lt->def->b_index != 0) {
iptr = ls->basicblocks[lt->def->b_index]->iinstr +
lt->def->iindex;
- if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI)
- remove_statement = false;
+ if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
- /* if ICMD could throw an exception do not remove it! */
+ /* if ICMD could throw an exception do not remove it! */
- else {
+ remove_statement = false;
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("dce: PEI: BB%3i II%3i %s not removed \n",
+ lt->def->b_index, lt->def->iindex,
+ opcode_names[iptr->opc]);
+ }
+#endif
- /* ICMD_INVOKE*, ICMD_BUILTIN and ICMD_MULTIANEWARRAY */
- /* have possible sideeffects -> do not remove them */
-
-/* remove_statement = !(ICMD_HAS_SPECIAL(iptr->opc)); */
-
- remove_statement = !(
- (icmd_table[iptr->opc].dataflow == DF_INVOKE) ||
- (icmd_table[iptr->opc].dataflow == DF_BUILTIN) ||
- (icmd_table[iptr->opc].dataflow == DF_N_TO_1));
-
- if (remove_statement) {
- switch (icmd_table[iptr->opc].dataflow) {
- case DF_3_TO_0:
- case DF_3_TO_1: /* icmd has s1, s2 and s3 */
- a = iptr->sx.s23.s3.varindex;
- s_lt = ls->lifetime + a;
- lt_remove_use_site(s_lt, lt->def->b_index,
- lt->def->iindex);
- wl_add(W, a);
-
- /* now "fall through" for handling of s2 and s1 */
-
- case DF_2_TO_0:
- case DF_2_TO_1: /* icmd has s1 and s2 */
- a = iptr->sx.s23.s2.varindex;
- s_lt = ls->lifetime + a;
- lt_remove_use_site(s_lt, lt->def->b_index,
- lt->def->iindex);
- wl_add(W, a);
-
- /* now "fall through" for handling of s1 */
-
- case DF_1_TO_0:
- case DF_1_TO_1:
- case DF_MOVE:
- case DF_COPY:
- a = iptr->s1.varindex;
- s_lt = ls->lifetime + a;
- lt_remove_use_site(s_lt, lt->def->b_index,
- lt->def->iindex);
- wl_add(W, a);
- }
+ }
+ else {
+ remove_statement = true;
+
+ switch (icmd_table[iptr->opc].dataflow) {
+ case DF_3_TO_0:
+ case DF_3_TO_1: /* icmd has s1, s2 and s3 */
+ a = iptr->sx.s23.s3.varindex;
+ s_lt = ls->lifetime + a;
+ lt_remove_use_site(s_lt, lt->def->b_index,
+ lt->def->iindex);
+ wl_add(W, a);
+
+ /* "fall through" for handling of s2 and s1 */
+
+ case DF_2_TO_0:
+ case DF_2_TO_1: /* icmd has s1 and s2 */
+ a = iptr->sx.s23.s2.varindex;
+ s_lt = ls->lifetime + a;
+ lt_remove_use_site(s_lt, lt->def->b_index,
+ lt->def->iindex);
+ wl_add(W, a);
+
+ /* "fall through" for handling of s1 */
+
+ /* DF_{IINC,STORE,LOAD} are DF_{1_TO_1,MOVE,COPY} */
+
+ case DF_1_TO_0:
+ case DF_1_TO_1:
+ case DF_MOVE:
+ case DF_COPY:
+ a = iptr->s1.varindex;
+ s_lt = ls->lifetime + a;
+ lt_remove_use_site(s_lt, lt->def->b_index,
+ lt->def->iindex);
+ wl_add(W, a);
+ }
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("dce: BB%3i II%3i %s removed \n",
+ lt->def->b_index, lt->def->iindex,
+ opcode_names[iptr->opc]);
}
+#endif
}
if (remove_statement) {
#ifdef SSA_DEBUG_VERBOSE
if (compileverbose)
- printf("INFO: %s %s:at BB %3i II %3i NOP-<%s\n",
+ printf("dce: %s %s:at BB %3i II %3i NOP-<%s\n",
m->class->name->text, m->name->text,
lt->def->b_index, lt->def->iindex,
icmd_table[iptr->opc].name);
/* remove definition of a */
- VAR(lt->v_index)->type = -1;
- lt->type = -1;
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("dce: var %3i removed\n", lt->v_index);
+#endif
+ VAR(lt->v_index)->type = UNUSED;
+ lt->type = UNUSED;
lt->def = NULL;
+/* jd->var */
} /* if (lt->use == NULL) */
} /* while(!wl_is_empty(W)) */
} /* dead_code_elimination */
instruction *iptr;
struct lifetime *lt, *s_lt;
- s4 *in;
lsradata *ls;
if (ls->lifetimecount > 0) {
/* put all lifetimes on Worklist */
for(a = 0; a < ls->lifetimecount; a++) {
- if (ls->lifetime[a].type != -1) {
+ if (ls->lifetime[a].type != UNUSED) {
wl_add(W, a);
}
}
a = wl_get(W);
lt = ls->lifetime + a;
- if (lt->type == -1)
+ if (lt->type == UNUSED)
continue;
_SSA_ASSERT(lt->def != NULL);
+#if 0
_SSA_ASSERT(lt->use != NULL);
+#endif
if (lt->def->iindex < 0 ) {
/* phi function */
for (i = 1; i <= graph_get_num_predecessor(gd, lt->def->b_index);
i++) {
source = ls->phi[lt->def->b_index][-lt->def->iindex-1][i];
- if (source != ls->varcount_with_indices) {
+ if ((source != ls->varcount_with_indices) &&
+ (source != UNUSED)) {
if (only_source == ls->varcount_with_indices) {
+
/* first valid source argument of phi function */
+
only_source = source;
} else {
+
/* second valid source argument of phi function */
/* exit for loop */
+
only_source = ls->varcount_with_indices;
break;
}
}
}
+
if (only_source != ls->varcount_with_indices) {
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf(
+ "-- copy propagation phi-func: BB %3i II %3i: %3i -> %3i\n",
+ lt->def->b_index, lt->def->iindex,
+ only_source, lt->v_index);
+#endif
+ s_lt = ls->lifetime + only_source;
+
/* replace all use sites of lt with the var_index only_source */
ssa_replace_use_sites( jd, gd, lt, only_source, W);
- /* delete def of lt and replace uses of lt with "only_source" */
+ /* delete def of lt */
ls->phi[lt->def->b_index][-lt->def->iindex-1] = NULL;
- s_lt = ls->lifetime + only_source;
+ /* remove this deleted use site of s_lt */
- VAR(lt->v_index)->type = -1;
lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
+
lt->def = NULL;
+
/* move use sites from lt to s_lt */
+
lt_move_use_sites(lt, s_lt);
- lt->type = -1;
+
+ /* invalidate lt */
+
+ lt->type = UNUSED;
+ VAR(lt->v_index)->type = UNUSED;
+
+ /* add s_lt again to Worklist W */
+
+ wl_add(W, s_lt->v_index);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ _ssa_print_lt(s_lt);
+#endif
} /* if (only_source != ls->varcount_with_indices) */
- } else { /* if (lt->def->iindex < 0 )*/
+ }
+ else { /* if (lt->def->iindex < 0 ) */
+
+ /* def in argument passing - no propagation possible */
+ /* (there is no ICMD for this... */
+
+ if (lt->def->b_index == 0)
+ continue;
+
/* def in "normal" ICMD */
-#if 0
+
iptr = ls->basicblocks[lt->def->b_index]->iinstr +
lt->def->iindex;
-
- if ( localvar ) {
- if (lt->def->b_index == 0)
- continue;
-
- switch(iptr->opc) {
- case ICMD_ISTORE:
- case ICMD_LSTORE:
- case ICMD_FSTORE:
- case ICMD_DSTORE:
+
+ switch(iptr->opc) {
+ case ICMD_ISTORE:
+ case ICMD_LSTORE:
+ case ICMD_FSTORE:
+ case ICMD_DSTORE:
case ICMD_ASTORE:
- if (lt->def->iindex == 0) {
- /* first instruction in bb -> instack==bb->instack */
- in = ls->basicblocks[lt->def->b_index]->instack;
- } else {
- /* instack is (iptr-1)->dst */
- in = (iptr-1)->dst;
- }
-
- if (in->varkind != LOCALVAR) {
+ case ICMD_ILOAD:
+ case ICMD_LLOAD:
+ case ICMD_FLOAD:
+ case ICMD_DLOAD:
+ case ICMD_ALOAD:
+ case ICMD_MOVE:
#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("copy propagation xstore: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, in->varnum);
+ if (compileverbose)
+ printf(
+ "-- copy propagation %3i %s: BB %3i II %3i: %3i -> %3i\n",
+ iptr->opc, opcode_names[iptr->opc], lt->def->b_index,
+ lt->def->iindex, iptr->s1.varindex,
+ iptr->dst.varindex);
#endif
- s_lt = &(ls->lifetime[-in->varnum-1]);
-
- for (ss = s_lt->local_ss; ss != NULL; ss = ss->next) {
- ss->s->varkind = LOCALVAR;
- ss->s->varnum = iptr->op1;
- }
-
- /* replace all use sites of s_lt with the var_index */
- /* iptr->op1 */
-
- ssa_replace_use_sites(jd, gd, s_lt, iptr->op1, W);
+ s_lt = ls->lifetime + iptr->s1.varindex;
- /* s_lt->def is the new def site of lt */
- /* the old ->def site will get a use site of def */
- /* only one def site */
- _SSA_ASSERT(lt->def->next == NULL);
- _SSA_ASSERT(s_lt->def != NULL);
- _SSA_ASSERT(s_lt->def->next == NULL);
-
- /* replace def of s_lt with iptr->op1 */
- if (s_lt->def->iindex < 0) {
- /* phi function */
- _SSA_ASSERT(ls->phi[s_lt->def->b_index]
- [-s_lt->def->iindex-1]
- != NULL);
- ls->phi[s_lt->def->b_index][-s_lt->def->iindex-1][0]
- = iptr->op1;
- } else
- if (in->varnum != iptr->op1)
- printf("copy propagation: LOCALVAR ss->ISTORE BB %i II %i\n",
- lt->def->b_index, lt->def->iindex);
-
+ _SSA_ASSERT( lt->v_index == iptr->dst.varindex);
+
+ /* replace all use sites of lt with the var_index */
+ /* iptr->s1.varindex (==lt->v_index) */
+
+ ssa_replace_use_sites(jd, gd, lt, iptr->s1.varindex, W);
+
+ _SSA_ASSERT(lt->def->next == NULL);
+ _SSA_ASSERT(s_lt->def != NULL);
+ _SSA_ASSERT(s_lt->def->next == NULL);
- /* move def to use sites of lt */
- lt->def->next = lt->use;
- lt->use = lt->def;
-
- lt->def = s_lt->def;
+ /* this ICMD is not a PEI -> so no danger in deleting it! */
+ /* delete def of lt (ICMD_NOP) */
- s_lt->def = NULL;
+ /* lt->def->iindex > 0 -> ICMD */
+ iptr->opc = ICMD_NOP;
- /* move use sites from s_lt to lt */
- move_use_sites(s_lt, lt);
- move_stackslots(s_lt, lt);
- s_lt->type = -1;
- }
- break;
- }
- } else {
- /* Def Interface Stackslot */
-
- switch(iptr->opc) {
- case ICMD_ILOAD:
- case ICMD_LLOAD:
- case ICMD_FLOAD:
- case ICMD_DLOAD:
- case ICMD_ALOAD:
- only_source = lt->local_ss->s->varnum;
- if (lt->local_ss->s->varkind != LOCALVAR) {
-#ifdef SSA_DEBUG_VERBOSE
- if (compileverbose)
- printf("copy propagation xload: BB %3i I %3i: %3i -> %3i\n", lt->def->b_index, lt->def->iindex, iptr->op1, lt->local_ss->s->varnum);
-#endif
- _SSA_ASSERT(iptr->dst->varnum == lt->local_ss->s->varnum);
- for (ss = lt->local_ss; ss != NULL; ss = ss->next) {
- ss->s->varkind = LOCALVAR;
- ss->s->varnum = iptr->op1;
- }
+ /* remove this deleted use site of s_lt */
- /* replace all use sites of lt with the var_index iptr->op1*/
+ lt_remove_use_site(s_lt, lt->def->b_index, lt->def->iindex);
- ssa_replace_use_sites(jd, gd, lt, iptr->op1, W);
+ /* invalidate def site of lt */
- lt->def = NULL;
-
- s_lt = &(ls->lifetime[ls->maxlifetimes + iptr->op1]);
-
- /* move use sites from lt to s_lt */
- move_use_sites(lt, s_lt);
- move_stackslots(lt, s_lt);
- lt->type = -1;
- } else
- if (lt->local_ss->s->varnum != iptr->op1)
- printf("copy propagation: ILOAD -> LOCALVAR ss BB %i II %i\n",
- lt->def->b_index, lt->def->iindex);
-
- break;
- }
- } /* localvar or interface stackslot */
+ lt->def = NULL;
+
+ /* move use sites from lt to s_lt */
+
+ lt_move_use_sites(lt, s_lt);
+
+ /* invalidate lt */
+
+ lt->type = UNUSED;
+ VAR(lt->v_index)->type = UNUSED;
+
+ /* add s_lt again to Worklist W */
+ wl_add(W, s_lt->v_index);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ _ssa_print_lt(s_lt);
#endif
- } /* i(lt->def->iindex < 0 ) */
-
+ break;
+ }
+ } /* if (lt->def->iindex < 0 ) */
} /* while(!wl_is_empty(W)) */
}
for (i = 1;i <= graph_get_num_predecessor(gd, s->b_index); i++) {
source = ls->phi[s->b_index][-s->iindex-1][i];
- if (source == lt->v_index) {
+ if (source == lt->v_index) {
+
+ /* check if this use in this phi function is a */
+ /* "selfdefinition" (x = phi(...,x,...)) */
+ /* if so replace the use with -1 (x=phi(...,-1,...)*/
+
+ if (new_v_index == ls->phi[s->b_index][-s->iindex-1][0]) {
#ifdef SSA_DEBUG_VERBOSE
- if (W != NULL) {
- if (compileverbose)
- printf("copy propagation phi: BB %3i I %3i: %3i -> \
- %3i\n", s->b_index, s->iindex,
- new_v_index, source);
+ if (W != NULL) {
+ if (compileverbose)
+ printf(
+ "copy propagation phi: BB %3i I %3i: %3i -> %3i\n",
+ s->b_index, s->iindex, -1, source);
+ }
+#endif
+ ls->phi[s->b_index][-s->iindex-1][i] = -1;
+
+ /* remove this use site of use site */
+ lt_remove_use_site(lt, s->b_index, s->iindex);
}
+ else {
+#ifdef SSA_DEBUG_VERBOSE
+ if (W != NULL) {
+ if (compileverbose)
+ printf(
+ "copy propagation phi: BB %3i I %3i: %3i -> %3i\n",
+ s->b_index, s->iindex, new_v_index, source);
+ }
#endif
- ls->phi[s->b_index][-s->iindex-1][i]
- = new_v_index;
+ ls->phi[s->b_index][-s->iindex-1][i] = new_v_index;
+ }
}
}
if (W != NULL) {
#ifdef SSA_DEBUG_VERBOSE
if (W != NULL) {
if (compileverbose)
- printf("copy propagation loc: BB %3i I %3i: %3i -> \
+ printf("copy propagation loc3: BB %3i I %3i: %3i -> \
%3i\n", s->b_index, s->iindex,
new_v_index, iptr->sx.s23.s3.varindex);
}
#ifdef SSA_DEBUG_VERBOSE
if (W != NULL) {
if (compileverbose)
- printf("copy propagation loc: BB %3i I %3i: %3i -> \
+ printf("copy propagation loc2: BB %3i I %3i: %3i -> \
%3i\n", s->b_index, s->iindex,
new_v_index, iptr->sx.s23.s2.varindex);
}
#ifdef SSA_DEBUG_VERBOSE
if (W != NULL) {
if (compileverbose)
- printf("copy propagation loc: BB %3i I %3i: %3i -> \
- %3i\n", s->b_index, s->iindex,
- new_v_index, iptr->s1.varindex);
+ printf(
+ "copy propagation loc1: BB %3i I %3i: %3i -> %3i\n",
+ s->b_index, s->iindex, new_v_index,
+ iptr->s1.varindex);
}
#endif
iptr->s1.varindex = new_v_index;
if (W != NULL) {
if (compileverbose)
printf(
- "copy propagation loc: BB %3i I %3i: %3i -> %3i\n"
+ "copy propagation locN: BB %3i I %3i: %3i -> %3i\n"
, s->b_index, s->iindex, new_v_index, *argp);
}
#endif
void ssa_print_lt(lsradata *ls) {
int i;
struct lifetime *lt;
- struct site *use;
printf("SSA LT Def/Use\n");
for(i = 0; i < ls->lifetimecount; i++) {
lt = ls->lifetime + i;
- if (lt->type != UNUSED) {
- printf("VI %3i Type %3i Def: ",lt->v_index, lt->type);
- if (lt->def != NULL)
- printf("%3i,%3i Use: ",lt->def->b_index, lt->def->iindex);
- else
- printf("%3i,%3i Use: ",0,0);
- for(use = lt->use; use != NULL; use = use->next)
- printf("%3i,%3i ",use->b_index, use->iindex);
- printf("\n");
- }
+ _ssa_print_lt(lt);
+ }
+}
+
+void _ssa_print_lt(struct lifetime *lt) {
+ struct site *use;
+
+ if (lt->type != UNUSED) {
+ printf("VI %3i Type %3i Def: ",lt->v_index, lt->type);
+ if (lt->def != NULL)
+ printf("%3i,%3i Use: ",lt->def->b_index, lt->def->iindex);
+ else
+ printf("%3i,%3i Use: ",0,0);
+ for(use = lt->use; use != NULL; use = use->next)
+ printf("%3i,%3i ",use->b_index, use->iindex);
+ printf("\n");
}
}
/* src/vm/jit/optimizing/ssa.h - static single assignment form header
- Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
Institut f. Computersprachen - TU Wien
Authors: Christian Ullrich
+ $Id: ssa.h$
*/
/* function prototypes */
void ssa_init(jitdata *);
-void ssa(jitdata *, graphdata *);
+void ssa(jitdata */* , graphdata **/);
#endif /* _SSA_H */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.c - static single-assignment form
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: $
+
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "mm/memory.h"
+
+#include "toolbox/bitvector.h"
+#include "toolbox/worklist.h"
+
+#include "vm/builtin.h"
+
+#include "vm/jit/jit.h" /* icmd_table */
+
+#include "vm/jit/optimizing/dominators.h"
+#include "vm/jit/optimizing/graph.h"
+#include "vm/jit/optimizing/lifetimes.h"
+#include "vm/jit/optimizing/lsra.h"
+#include "vm/jit/optimizing/ssa.h"
+#include "vm/jit/optimizing/ssa_phi.h"
+
+#if defined(SSA_DEBUG_VERBOSE)
+#include "vmcore/options.h" /* compileverbose */
+#endif
+
+/* ssa_place_phi_functions *****************************************************
+
+Algorithm is based on "modern compiler implementation in C" from andrew
+w. appel, edition 2004
+
+Corrections:
+page 441 Algorithm 19.6. Inserting phi-functions:
+
+...
+ for each Y in DF[n]
+- if Y not element of A phi [n]
++ if a not element of A phi [n]
+ insert the statment a <- ...
+...
+...
+- A phi [n] <- A phi [n] join {Y}
++ A phi [n] <- A phi [n] join {a}
+- if Y not element of A orig [n]
++ if a not element of A orig [Y]
+ W <- W join {Y}
+
+
+ls->phi[n][a][p] is created and populated.
+
+n in [0..ls->basicblockcount[
+a in [0..ls->ssavarcount[
+p in [1..Count of Predecessors of Basicblock n]
+
+For each basicblock Y in the dominance frontier of a basicblock n (0 <= n <
+ls->basicblockcount) in which a variable (0 <= a < ls->ssavarcount) is defined
+an entry in ls->phi[Y][a] is created.
+This entry is an array with the number of predecessors of Y elements + 1
+elements.
+This elements are all set to the variable a and represent the phi function which
+will get ai = phi(ai1, ai2, ..., aip) after ssa_rename.
+
+
+ls->phi[n][a] == NULL, if no phi function for Variable a for Basicblock n exists
+
+or
+
+ls->phi[n][a][0] == a, representing the result of the phi function and
+ls->phi[n][a][p] == a, representing the arguments of the phi function.
+
+*******************************************************************************/
+
+
+void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd)
+{
+ int a,i,j,n,Y;
+ bitvector *def_sites;
+ bitvector *A_phi; /* [0..ls->basicblockcount[ of */
+ /* ls->ssavarcount Bit */
+ worklist *W;
+ int num_pred;
+
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ W = wl_new(ls->basicblockcount);
+
+ def_sites = DMNEW(bitvector, ls->ssavarcount);
+ for(a = 0; a < ls->ssavarcount; a++)
+ def_sites[a] = bv_new(ls->basicblockcount);
+
+ ls->phi = DMNEW(int **, ls->basicblockcount);
+ A_phi = DMNEW(bitvector, ls->basicblockcount);
+ for(i = 0; i < ls->basicblockcount; i++) {
+ ls->phi[i] = DMNEW(int *, ls->ssavarcount);
+ for(j = 0; j < ls->ssavarcount; j++)
+ ls->phi[i][j] = NULL;
+ A_phi[i] = bv_new(ls->ssavarcount);
+ }
+
+ /* copy var_def to def_sites */
+ /* var_def is valid for 0.. jd->basicblockcount (bb 0 for param init) */
+
+ for(n = 0; n <= jd->basicblockcount; n++)
+ for(a = 0; a < ls->ssavarcount; a++)
+ if (bv_get_bit(ls->var_def[n], a))
+ bv_set_bit(def_sites[a], n);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("var Definitions:\n");
+ for(i = 0; i < ls->ssavarcount; i++) {
+ printf("def_sites[%3i]=%p:",i,(void *)def_sites[i]);
+ for(j = 0; j < ls->basicblockcount; j++) {
+ if ((j % 5) == 0) printf(" ");
+ if (bv_get_bit(def_sites[i], j))
+ printf("1");
+ else
+ printf("0");
+ }
+ printf(" (");
+
+ printf("\n");
+ }
+ }
+#endif
+
+ for(a = 0; a < ls->ssavarcount; a++) {
+
+ /* W<-def_sites(a) */
+
+ for(n = 0; n < ls->basicblockcount; n++)
+ if (bv_get_bit(def_sites[a],n)) {
+ wl_add(W, n);
+ }
+
+ while (!wl_is_empty(W)) { /* W not empty */
+ n = wl_get(W);
+
+ for(i = 0; i < dd->num_DF[n]; i++) {
+ Y = dd->DF[n][i];
+
+ /* Node Y is in Dominance Frontier of n -> */
+ /* insert phi function for a at top of Y*/
+
+ _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
+ if (bv_get_bit( A_phi[Y], a) == 0) {
+
+ /* a is not a Element of A_phi[Y] */
+ /* a <- phi(a,a...,a) to be inserted at top of Block Y */
+ /* phi has as many arguments, as Y has predecessors */
+
+ num_pred = graph_get_num_predecessor(gd, Y);
+ ls->phi[Y][a] = DMNEW(int, num_pred + 1);
+ for (j = 0; j < num_pred + 1; j++)
+ ls->phi[Y][a][j] = a;
+
+ /* increment the number of definitions of a by one */
+ /* for this phi function */
+
+ ls->num_defs[a]++;
+
+ bv_set_bit(A_phi[Y], a);
+ if (bv_get_bit(ls->var_def[Y],a)==0) {
+
+ /* Iterated Dominance Frontier Criterion: */
+ /* if Y had no definition for a, insert it */
+ /* into the Worklist, since now it */
+ /* defines a through the phi function */
+
+ wl_add(W, Y);
+ }
+ }
+ }
+ }
+ }
+}
+
+void ssa_generate_phi_moves(jitdata *jd, graphdata *gd) {
+ int a, i, j, pred;
+ graphiterator iter;
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ /* count moves to be inserted at the end of each block in moves[] */
+
+ ls->num_phi_moves = DMNEW(int, ls->basicblockcount);
+ for(i = 0; i < ls->basicblockcount; i++)
+ ls->num_phi_moves[i] = 0;
+ for(i = 0; i < ls->basicblockcount; i++)
+ for(a = 0; a < ls->ssavarcount; a++)
+ if (ls->phi[i][a] != NULL) {
+#if 0
+ if (ls->lifetime[ls->phi[i][a][0]].use == NULL) {
+ /* Var defined (only <- SSA Form!) in this phi function */
+ /* and not used anywhere -> delete phi function and set */
+ /* var to unused */
+
+ /* TODO: first delete use sites of arguments of phi */
+ /* function */
+ VAR(ls->lifetime[ls->phi[i][a][0]].v_index)->type = UNUSED;
+ ls->lifetime[ls->phi[i][a][0]].def = NULL;
+ ls->phi[i][a] = NULL;
+ }
+ else
+#endif
+ {
+ pred = graph_get_first_predecessor(gd, i, &iter);
+ for(; pred != -1; pred = graph_get_next(&iter)) {
+ ls->num_phi_moves[pred]++;
+ }
+ }
+ }
+
+ /* allocate ls->phi_moves */
+
+ ls->phi_moves = DMNEW( int **, ls->basicblockcount);
+ for(i = 0; i < ls->basicblockcount; i++) {
+ ls->phi_moves[i] = DMNEW( int *, ls->num_phi_moves[i]);
+ for(j = 0; j <ls->num_phi_moves[i]; j++)
+ ls->phi_moves[i][j] = DMNEW(int, 2);
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("ssa_generate_phi_moves: ls_num_phi_moves[%3i] = %3i\n",
+ i, ls->num_phi_moves[i]);
+#endif
+ }
+
+ /* populate ls->phi_moves */
+
+ for(i = 0; i < ls->basicblockcount; i++)
+ ls->num_phi_moves[i] = 0;
+ for(i = 0; i < ls->basicblockcount; i++)
+ for(a = 0; a < ls->ssavarcount; a++)
+ if (ls->phi[i][a] != NULL) {
+ pred = graph_get_first_predecessor(gd, i, &iter);
+ for(j = 0; pred != -1; j++, pred = graph_get_next(&iter)) {
+ /* target is phi[i][a][0] */
+ /* source is phi[i][a][j+1] */
+ if (ls->phi[i][a][j+1] != ls->varcount_with_indices) {
+ /* valid move */
+ if (ls->phi[i][a][0] != ls->phi[i][a][j+1]) {
+ ls->phi_moves[pred][ls->num_phi_moves[pred]][0] =
+ ls->phi[i][a][0];
+ ls->phi_moves[pred][(ls->num_phi_moves[pred])++][1]=
+ ls->phi[i][a][j+1];
+ }
+ }
+ }
+ }
+}
+
+#ifdef SSA_DEBUG_VERBOSE
+void ssa_print_phi(lsradata *ls, graphdata *gd) {
+ int i,j,k;
+
+ printf("phi Functions (varcount_with_indices: %3i):\n",
+ ls->varcount_with_indices);
+ for(i = 0; i < ls->basicblockcount; i++) {
+ for(j = 0; j < ls->ssavarcount; j++) {
+ if (ls->phi[i][j] != NULL) {
+ printf("BB %3i %3i = phi(", i, ls->phi[i][j][0]);
+ for(k = 1; k <= graph_get_num_predecessor(gd, i); k++)
+ printf("%3i ",ls->phi[i][j][k]);
+ printf(")\n");
+ }
+ }
+ }
+
+}
+#endif
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.h - static single assignment form header
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: ssa.h$
+
+*/
+
+
+#ifndef _SSA_PHI_H
+#define _SSA_PHI_H
+
+#include "vm/jit/optimizing/graph.h"
+
+#if !defined(NDEBUG)
+# include <assert.h>
+#endif
+
+/* function prototypes */
+void ssa_place_phi_functions(jitdata *jd, graphdata *gd, dominatordata *dd);
+void ssa_generate_phi_moves(jitdata *, graphdata *);
+#ifdef SSA_DEBUG_VERBOSE
+void ssa_print_phi(lsradata *ls, graphdata *gd);
+#endif
+
+#endif /* _SSA_PHI_H */
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset): 4
+ * tab-width): 4
+ * End:
+ * vim:noexpandtab:sw=4:ts=4:
+ */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.c - static single-assignment form
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: $
+
+*/
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "mm/memory.h"
+
+#include "toolbox/bitvector.h"
+#include "toolbox/worklist.h"
+
+#include "vm/builtin.h"
+
+#include "vm/jit/jit.h" /* icmd_table */
+
+#include "vm/jit/optimizing/dominators.h"
+#include "vm/jit/optimizing/graph.h"
+#include "vm/jit/optimizing/lifetimes.h"
+#include "vm/jit/optimizing/lsra.h"
+#include "vm/jit/optimizing/ssa.h"
+#include "vm/jit/optimizing/ssa_rename.h"
+
+#if defined(SSA_DEBUG_VERBOSE)
+#include "vmcore/options.h" /* compileverbose */
+#endif
+
+/* function prototypes */
+void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n);
+int ssa_rename_def_(lsradata *ls, int a);
+
+/* ssa_rename ******************************************************************
+
+Rename the variables a (0 <= a < ls->ssavarcount) so that each new variable
+has only one definition (SSA form).
+
+ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
+ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
+ definition of each old var.
+ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
+ and IOVARS.
+
+All other vars (TEMPVAR and PREALLOC) will get a new unique index above
+ls->varcount_with_indices.
+
+jd->var and jd->varcount will be set for this renamed vars.
+
+*******************************************************************************/
+
+void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd)
+{
+ int i, mi, l, j, p, t;
+ int type, flags;
+ methoddesc *md = jd->m->parseddesc;
+
+ varinfo *new_vars;
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ ssa_rename_init(jd, gd);
+
+ /* Consider definition of Local Vars initialized with Arguments */
+ /* in Block 0 */
+ /* init is regarded as use too-> ssa_rename_use ->bullshit!!*/
+
+ for (p = 0, l= 0; p < md->paramcount; p++) {
+ t = md->paramtypes[p].type;
+ mi = l * 5 + t;
+ i = jd->local_map[mi];
+ l++;
+ if (IS_2_WORD_TYPE(t))
+ l++;
+ if (i == UNUSED)
+ continue;
+
+ /* !!!!! locals are now numbered as the parameters !!!! */
+ /* !!!!! no additional increment for 2 word types !!!!! */
+ /* this happens later on! here we still need the increment */
+ /* index of var can be in the range from 0 up to not including*/
+ /* jd->varcount */
+
+
+ i = ls->new_varindex[i];
+
+ /* ignore return value, since first definition gives 0 -> */
+ /* no rename necessary */
+
+ j = ssa_rename_def_(ls, i);
+ _SSA_ASSERT(j == 0);
+ jd->local_map[mi] = i;
+ }
+ ssa_rename_(jd, gd, dd, 0);
+
+#if 0
+ /* DO _NOT_ DO THIS! Look at java.util.stringtokenizer.counttokens! */
+ /* if there is no use of the defined Var itself by the phi function */
+ /* for a loop path, in which this var is not used, it will not be life*/
+ /* in this path and overwritten! */
+
+ /* Invalidate all xij from xi0=phi(xi1,xi2,xi3,..,xin) with xij == xi0*/
+ /* this happens if the phi function is the first definition of x or in*/
+ /* a path with a backedge xi has no definition */
+ /* a phi(xij) = ...,xij,... with the only use and definition of xij by*/
+ /* this phi function would otherwise "deadlock" the dead code */
+ /* elemination (invalidate means set it to UNUSED) */
+ /* a phi function phi(xi0)=xi1,xi2,...xin wiht xij == xi0 for all j in*/
+ /* [1,n] can be removed */
+
+ for(i = 0; i < ls->ssavarcount; i++) {
+ for(t = 0; t < ls->basicblockcount; t++) {
+ if (ls->phi[t][i] != 0) {
+ remove_phi = true;
+ for(p = 1; p <= graph_get_num_predecessor(gd, t); p++) {
+ if (ls->phi[t][i][0] == ls->phi[t][i][p])
+ ls->phi[t][i][p] = UNUSED;
+ else
+ remove_phi = false;
+ }
+ }
+ if (remove_phi)
+ ls->phi[t][i] = NULL;
+ }
+ }
+#endif
+
+#if defined(SSA_DEBUG_CHECK) || defined(SSA_DEBUG_VERBOSE)
+# if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose) {
+ printf("%s %s ",jd->m->class->name->text, jd->m->name->text);
+ if (code_is_leafmethod(jd->code))
+ printf("**Leafmethod**");
+ printf("\n");
+ }
+# endif
+ if (strcmp(jd->m->class->name->text,"fp")==0)
+ if (strcmp(jd->m->name->text,"testfloat")==0)
+# if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("12-------------------12\n");
+# else
+ { int dummy=1; dummy++; }
+# endif
+#endif
+
+ /* recreate rd->locals[][] */
+ /* now only one (local_index/type) pair exists anymore */
+ /* all var[t][i] with var_to_index[var[t][i]] >= 0 are locals */
+ /* max local index after SSA indexing is in ls->local_0[ls->max_locals] */
+
+ new_vars = DMNEW(varinfo, ls->vartop);
+ for(i = 0; i < ls->vartop ; i++)
+ new_vars[i].type = UNUSED;
+ for(i = 0; i < jd->varcount; i++) {
+ p = ls->new_varindex[i];
+ if (p != UNUSED) {
+ if (p < ls->ssavarcount)
+ p = ls->var_0[p];
+ new_vars[p].type = VAR(i)->type;
+ new_vars[p].flags = VAR(i)->flags;
+ ls->lifetime[p].v_index = p;
+ ls->lifetime[p].type = VAR(i)->type;
+ }
+ }
+
+ /* take care of newly indexed local & in/out vars */
+
+ for(i = 0; i < ls->ssavarcount; i++) {
+ j = ls->var_0[i];
+ type = new_vars[j].type;
+ flags = new_vars[j].flags;
+ j++;
+ for (; j < ls->var_0[i + 1]; j++) {
+ new_vars[j].type = type;
+ new_vars[j].flags = flags;
+ ls->lifetime[j].v_index = j;
+ ls->lifetime[j].type = type;
+ }
+ }
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+
+ printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
+ ls->ssavarcount);
+ for(i = 0; i < jd->varcount; i++) {
+ printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
+ ssa_show_variable(jd, i, VAR(i),0);
+ j = ls->new_varindex[i];
+ if ((j != UNUSED) && (j < ls->ssavarcount))
+ printf(" -> %3i ... %3i", ls->var_0[j], ls->var_0[j + 1] - 1);
+ else
+ printf(" -> %3i", j);
+ printf("\n");
+ }
+ }
+#endif
+
+ jd->var = new_vars;
+ jd->varcount = ls->vartop;
+ jd->vartop = ls->vartop;
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("ssa_rename: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
+ ls->ssavarcount);
+ for(i = 0; i < jd->varcount; i++) {
+ printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
+ ssa_show_variable(jd, i, VAR(i),0);
+ printf("\n");
+ }
+ }
+#endif
+}
+
+/* ssa_rename_init *************************************************************
+
+Setup the data structure for ssa_rename
+
+ls->def_count[0..ls->ssavarcount[ holds the number of definitions of each var.
+ls->var_0[0..ls->ssavarcount[ will be set to the new index of the first
+ definition of each old var.
+ls->varcount_with_indices will be se to the new maximum varcount of LOCAL
+ and IOVARS.
+
+All other vars (TEMPVAR and PREALLOC) will get a new unique index above
+ls->varcount_with_indices.
+
+jd->var and jd->varcount will be set for this renamed vars.
+
+*******************************************************************************/
+
+void ssa_rename_init(jitdata *jd, graphdata *gd)
+{
+ int a, i;
+#if 0
+ int p;
+#endif
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ /* set up new locals */
+ /* ls->new_varindex[0..jd->varcount[ holds the new unique index */
+ /* for locals and iovars */
+
+ /* ls->num_defs[index] gives the number of indizes which will be created */
+ /* from SSA */
+
+ /* -> vars will be numbered in this sequence: L0(0)..L0(i) L1(0)..L1(j) ..*/
+ /* ls->var_0[X] will point to each LX(0) */
+ /* ls->var_0[ls->ssavarcount] will hold ls->varcount_with_indices */
+
+ /* as first step cummulate the num_defs array for locals and iovars */
+ /* last element is the maximum var count */
+
+ ls->var_0 = DMNEW(int, max(1, ls->ssavarcount + 1));
+ ls->var_0[0] = 0;
+ ls->varcount_with_indices = 0;
+ for(i = 0; i < ls->ssavarcount; i++) {
+ ls->varcount_with_indices += ls->num_defs[i];
+ ls->var_0[i+1] = ls->var_0[i] + ls->num_defs[i];
+ }
+
+#if 0
+ /* Change the var indices in phi from La to La(0) */
+
+ for(i = 0; i < ls->basicblockcount; i++)
+ for (a = 0; a < ls->ssavarcount; a++)
+ if (ls->phi[i][a] != NULL)
+ for(p = 0; p < graph_get_num_predecessor(gd, i) + 1; p++)
+ ls->phi[i][a][p] = ls->var_0[a];
+#endif
+
+ /* Initialization */
+
+ ls->count = DMNEW(int, max(1, ls->ssavarcount));
+ ls->stack = DMNEW(int *, max(1, ls->ssavarcount));
+ ls->stack_top = DMNEW(int, max(1, ls->ssavarcount));
+ for(a = 0; a < ls->ssavarcount; a++) {
+ ls->count[a] = 0;
+ ls->stack_top[a] = 0;
+
+ /* stack a has to hold number of defs of a Elements + 1 */
+
+ ls->stack[a] = DMNEW(int, ls->num_defs[a] + 1);
+ ls->stack[a][ls->stack_top[a]++] = 0;
+ }
+
+ if (ls->ssavarcount > 0) {
+
+ /* Create the num_var_use Array */
+
+ ls->num_var_use = DMNEW(int *, ls->basicblockcount);
+ for(i = 0; i < ls->basicblockcount; i++) {
+ ls->num_var_use[i] =DMNEW(int, max(1, ls->varcount_with_indices));
+ for(a = 0; a < ls->varcount_with_indices; a++)
+ ls->num_var_use[i][a] = 0;
+ }
+
+ /* Create the use_sites Array of Bitvectors*/
+ /* use max(1,..), to ensure that the array is created! */
+
+ ls->use_sites = DMNEW(bitvector, max(1, ls->varcount_with_indices));
+ for(a = 0; a < ls->varcount_with_indices; a++)
+ ls->use_sites[a] = bv_new(ls->basicblockcount);
+ }
+
+ /* init lifetimes */
+ /* count number of TEMPVARs */
+
+ ls->lifetimecount = 0;
+ for(i = 0; i < jd->varcount; i++)
+ if ((i >= jd->localcount) || (!(jd->var[i].flags & (INOUT | PREALLOC))))
+ ls->lifetimecount++;
+
+ ls->varcount = ls->varcount_with_indices + ls->lifetimecount;
+
+ ls->lifetimecount = ls->varcount;
+ ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
+ ls->lt_used = DMNEW(int, ls->lifetimecount);
+ ls->lt_int = DMNEW(int, ls->lifetimecount);
+ ls->lt_int_count = 0;
+ ls->lt_flt = DMNEW(int, ls->lifetimecount);
+ ls->lt_flt_count = 0;
+ ls->lt_mem = DMNEW(int, ls->lifetimecount);
+ ls->lt_mem_count = 0;
+ for (i=0; i < ls->lifetimecount; i++) {
+ ls->lifetime[i].type = UNUSED;
+ ls->lifetime[i].savedvar = 0;
+ ls->lifetime[i].flags = 0;
+ ls->lifetime[i].usagecount = 0;
+ ls->lifetime[i].bb_last_use = -1;
+ ls->lifetime[i].bb_first_def = -1;
+ ls->lifetime[i].use = NULL;
+ ls->lifetime[i].def = NULL;
+ ls->lifetime[i].last_use = NULL;
+ }
+
+ /* for giving TEMP and PREALLOC vars a new unique index */
+
+ ls->vartop = ls->varcount_with_indices;
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("ssa_rename_init: Vars: Orig:%3i SSAVar: %3i\n", jd->varcount,
+ ls->ssavarcount);
+ for(i = 0; i < jd->varcount; i++) {
+ if ((i < jd->localcount) || ( VAR(i)->flags & INOUT)) {
+ printf("%3i(%3i,%3x) ",i,VAR(i)->type, VAR(i)->flags);
+ ssa_show_variable(jd, i, VAR(i),0);
+ if ((i < ls->ssavarcount) || (VAR(i)->flags & INOUT)) {
+ printf(" -> %3i", ls->new_varindex[i]);
+ }
+ printf("\n");
+ }
+ }
+ ssa_print_phi(ls, gd);
+ }
+#endif
+}
+
+int ssa_rename_def_(lsradata *ls, int a) {
+ int i;
+
+ _SSA_CHECK_BOUNDS(a,0,ls->ssavarcount);
+ ls->count[a]++;
+ i = ls->count[a] - 1;
+ /* push i on stack[a] */
+ _SSA_CHECK_BOUNDS(ls->stack_top[a], 0, ls->num_defs[a] + 1);
+ ls->stack[a][ls->stack_top[a]++] = i;
+ return i;
+}
+
+int ssa_rename_def(jitdata *jd, int *def_count, int a) {
+ int i, a1, ret;
+ lsradata *ls;
+
+ ls = jd->ls;
+
+ a1 = ls->new_varindex[a];
+ _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
+ if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
+ /* local or inoutvar -> normal ssa renaming */
+ _SSA_ASSERT((a < jd->localcount) || (VAR(a)->flags & INOUT));
+ /* !IS_TEMPVAR && !IS_PREALLOC == (IS_LOCALVAR || IS_INOUT) */
+
+ def_count[a1]++;
+ i = ssa_rename_def_(ls, a1);
+ ret = ls->var_0[a1] + i;
+ }
+ else {
+ /* TEMP or PREALLOC var */
+ if (a1 == UNUSED) {
+ ls->new_varindex[a] = ls->vartop;
+ ret = ls->vartop;
+ ls->vartop++;
+ _SSA_ASSERT( ls->vartop < ls->varcount);
+ }
+ else
+ ret = a1;
+ }
+ return ret;
+}
+
+void ssa_rename_use_(lsradata *ls, int n, int a) {
+ _SSA_CHECK_BOUNDS(a, 0, ls->varcount_with_indices);
+ if (ls->ssavarcount > 0) {
+ bv_set_bit(ls->use_sites[a], n);
+ ls->num_var_use[n][a]++;
+ }
+}
+
+int ssa_rename_use(lsradata *ls, int n, int a) {
+ int a1, i;
+ int ret;
+
+ a1 = ls->new_varindex[a];
+ _SSA_CHECK_BOUNDS(a1, UNUSED, ls->varcount);
+ if ((a1 != UNUSED) && (a1 < ls->ssavarcount)) {
+ /* local or inoutvar -> normal ssa renaming */
+ /* i <- top(stack[a]) */
+
+ _SSA_CHECK_BOUNDS(ls->stack_top[a1]-1, 0, ls->num_defs[a1]+1);
+ i = ls->stack[a1][ls->stack_top[a1] - 1];
+ _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a1]);
+
+ ret = ls->var_0[a1] + i;
+ }
+ else {
+ /* TEMP or PREALLOC var */
+ if (a1 == UNUSED) {
+ ls->new_varindex[a] = ls->vartop;
+ ret = ls->vartop;
+ ls->vartop++;
+ _SSA_ASSERT( ls->vartop < ls->varcount);
+ }
+ else
+ ret = a1;
+ }
+
+ return ret;
+}
+
+#ifdef SSA_DEBUG_VERBOSE
+void ssa_rename_print(instruction *iptr, char *op, int from, int to) {
+ if (compileverbose) {
+ printf("ssa_rename_: ");
+ if (iptr != NULL)
+ printf("%s ", opcode_names[iptr->opc]);
+ else
+ printf(" ");
+
+ printf("%s: %3i->%3i\n", op, from, to);
+ }
+}
+#endif
+
+/* ssa_rename_ ****************************************************************
+
+Algorithm is based on "modern compiler implementation in C" from andrew
+w. appel, edition 2004
+
+page 443 Algorithm 19.7. Renaming Variables
+
+*******************************************************************************/
+
+void ssa_rename_(jitdata *jd, graphdata *gd, dominatordata *dd, int n) {
+ int a, i, j, k, iindex, Y, v;
+ int in_d, out_d;
+ int *def_count;
+ /* [0..ls->varcount[ Number of Definitions of this var in this */
+ /* Basic Block. Used to remove the entries off the stack at the */
+ /* end of the function */
+ instruction *iptr;
+ s4 *in, *out, *argp;
+ graphiterator iter_succ, iter_pred;
+ struct lifetime *lt;
+
+ methoddesc *md;
+ methodinfo *m;
+ builtintable_entry *bte;
+ lsradata *ls;
+
+ ls = jd->ls;
+ m = jd->m;
+
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("ssa_rename_: BB %i\n",n);
+#endif
+
+ _SSA_CHECK_BOUNDS(n, 0, ls->basicblockcount);
+
+ def_count = DMNEW(int, max(1, ls->ssavarcount));
+ for(i = 0; i < ls->ssavarcount; i++)
+ def_count[i] = 0;
+
+ /* change Store of possible phi functions from a to ai*/
+
+ for(a = 0; a < ls->ssavarcount; a++)
+ if (ls->phi[n][a] != NULL) {
+ def_count[a]++;
+
+ /* do not mark this store as use - maybe this phi function */
+ /* can be removed for unused Vars*/
+
+ j = ls->var_0[a] + ssa_rename_def_(ls, a);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( NULL, "phi-st", ls->phi[n][a][0], j);
+#endif
+ ls->phi[n][a][0] = j;
+ }
+
+ in = ls->basicblocks[n]->invars;
+ in_d = ls->basicblocks[n]->indepth - 1;
+
+ /* change use of instack Interface stackslots except top SBR and EXH */
+ /* stackslots */
+
+ if ((ls->basicblocks[n]->type == BBTYPE_EXH) ||
+ (ls->basicblocks[n]->type == BBTYPE_SBR)) {
+ in_d--;
+ }
+/* out = ls->basicblocks[n]->outvars; */
+/* out_d = ls->basicblocks[n]->outdepth - 1; */
+
+/* for(; out_d > in_d; out_d--); */
+
+ for (; in_d >= 0; in_d--) {
+ /* Possible Use of ls->new_varindex[jd->var[in_d]] */
+ _SSA_ASSERT(ls->new_varindex[in[in_d]] != UNUSED);
+
+ a = ls->new_varindex[in[in_d]];
+ _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
+
+ /* i <- top(stack[a]) */
+
+ _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
+ i = ls->stack[a][ls->stack_top[a]-1];
+ _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+
+ /* Replace use of x with xi */
+
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( NULL, "invar", in[in_d], ls->var_0[a]+i);
+#endif
+ in[in_d] = ls->var_0[a] + i;
+ lt = ls->lifetime + in[in_d];
+
+ lt->v_index = in[in_d];
+ lt->bb_last_use = -1;
+ }
+
+ iptr = ls->basicblocks[n]->iinstr;
+
+ for(iindex = 0; iindex < ls->basicblocks[n]->icount; iindex++, iptr++) {
+
+ /* check for use (s1, s2, s3 or special (argp) ) */
+
+ switch (icmd_table[iptr->opc].dataflow) {
+ case DF_3_TO_0:
+ case DF_3_TO_1: /* icmd has s1, s2 and s3 */
+ j = ssa_rename_use(ls, n, iptr->sx.s23.s3.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "s3 ", iptr->sx.s23.s3.varindex, j);
+#endif
+ iptr->sx.s23.s3.varindex = j;
+
+ /* now "fall through" for handling of s2 and s1 */
+
+ case DF_2_TO_0:
+ case DF_2_TO_1: /* icmd has s1 and s2 */
+ j = ssa_rename_use(ls, n, iptr->sx.s23.s2.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "s2 ", iptr->sx.s23.s2.varindex, j);
+#endif
+ iptr->sx.s23.s2.varindex = j;
+
+ /* now "fall through" for handling of s1 */
+
+ case DF_1_TO_0:
+ case DF_1_TO_1:
+ case DF_MOVE:
+ case DF_COPY:
+ j = ssa_rename_use(ls, n, iptr->s1.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "s1 ", iptr->s1.varindex, j);
+#endif
+ iptr->s1.varindex = j;
+ break;
+
+ case DF_INVOKE:
+ case DF_BUILTIN:
+ case DF_N_TO_1:
+ /* do not use md->paramcount, pass-through stackslots have */
+ /* to be renamed, too */
+ i = iptr->s1.argcount;
+ argp = iptr->sx.s23.s2.args;
+ while (--i >= 0) {
+ j = ssa_rename_use(ls, n, *argp);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "arg", *argp, j);
+#endif
+ *argp = j;
+ argp++;
+ }
+ break;
+ }
+
+
+ /* Look for definitions (iptr->dst). INVOKE and BUILTIN have */
+ /* an optional dst - so they to be checked first */
+
+ v = UNUSED;
+ if (icmd_table[iptr->opc].dataflow == DF_INVOKE) {
+ INSTRUCTION_GET_METHODDESC(iptr,md);
+ if (md->returntype.type != TYPE_VOID)
+ v = iptr->dst.varindex;
+ }
+ else if (icmd_table[iptr->opc].dataflow == DF_BUILTIN) {
+ bte = iptr->sx.s23.s3.bte;
+ md = bte->md;
+ if (md->returntype.type != TYPE_VOID)
+ v = iptr->dst.varindex;
+ }
+ else if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE) {
+ v = iptr->dst.varindex;
+ }
+
+ if (v != UNUSED) {
+ j = ssa_rename_def(jd, def_count, iptr->dst.varindex);
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( iptr, "dst", iptr->dst.varindex, j);
+#endif
+ iptr->dst.varindex = j;
+ }
+
+ /* ?????????????????????????????????????????????????????????? */
+ /* Mark Def as use, too. Since param initialisation is in */
+ /* var_def and this would not remove this locals, if not used */
+ /* elsewhere */
+ /* ?????????????????????????????????????????????????????????? */
+
+ }
+
+ /* change outstack Interface stackslots */
+ out = ls->basicblocks[n]->outvars;
+ out_d = ls->basicblocks[n]->outdepth - 1;
+
+ for (;out_d >= 0; out_d--) {
+ /* Possible Use of ls->new_varindex[jd->var[out_d]] */
+ _SSA_ASSERT(ls->new_varindex[out[out_d]] != UNUSED);
+
+ a = ls->new_varindex[out[out_d]];
+ _SSA_CHECK_BOUNDS(a, 0, ls->ssavarcount);
+
+ /* i <- top(stack[a]) */
+
+ _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
+ i = ls->stack[a][ls->stack_top[a]-1];
+ _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+
+ /* Replace use of x with xi */
+
+#ifdef SSA_DEBUG_VERBOSE
+ ssa_rename_print( NULL, "outvar", out[out_d], ls->var_0[a]+i);
+#endif
+ out[out_d] = ls->var_0[a] + i;
+ lt = ls->lifetime + out[out_d];
+
+ lt->v_index = out[out_d];
+ lt->bb_last_use = -1;
+ }
+
+ /* change use in phi Functions of Successors */
+
+ Y = graph_get_first_successor(gd, n, &iter_succ);
+ for(; Y != -1; Y = graph_get_next(&iter_succ)) {
+ _SSA_CHECK_BOUNDS(Y, 0, ls->basicblockcount);
+ k = graph_get_first_predecessor(gd, Y, &iter_pred);
+ for (j = 0; (k != -1) && (k != n); j++)
+ k = graph_get_next(&iter_pred);
+ _SSA_ASSERT(k == n);
+
+ /* n is jth Predecessor of Y */
+
+ for(a = 0; a < ls->ssavarcount; a++)
+ if (ls->phi[Y][a] != NULL) {
+
+ /* i <- top(stack[a]) */
+
+ if (ls->stack_top[a] == 1) {
+ /* no definition till now in controll flow */
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("Succ %3i Arg %3i \n", Y, j);
+ ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], UNUSED);
+ }
+#endif
+ ls->phi[Y][a][j+1] = UNUSED;
+ }
+ else {
+ _SSA_CHECK_BOUNDS(ls->stack_top[a]-1, 0, ls->num_defs[a]+1);
+ i = ls->stack[a][ls->stack_top[a]-1];
+ _SSA_CHECK_BOUNDS(i, 0, ls->num_defs[a]);
+
+ /* change jth operand from a0 to ai */
+
+ i = ls->var_0[a] + i;
+#ifdef SSA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("Succ %3i Arg %3i \n", Y, j);
+ ssa_rename_print( NULL, "phi-use", ls->phi[Y][a][j+1], i);
+ }
+#endif
+ ls->phi[Y][a][j+1] = i;
+ _SSA_CHECK_BOUNDS(ls->phi[Y][a][j+1], 0,
+ ls->varcount_with_indices);
+
+ /* use by phi function has to be remembered, too */
+
+ ssa_rename_use_(ls, n, ls->phi[Y][a][j+1]);
+ }
+
+ /* ????????????????????????????????????????????? */
+ /* why was this only for local vars before ? */
+ /* ????????????????????????????????????????????? */
+
+ }
+ }
+
+ /* Call ssa_rename_ for all Childs of n of the Dominator Tree */
+ for(i = 0; i < ls->basicblockcount; i++)
+ if (dd->idom[i] == n)
+ ssa_rename_(jd, gd, dd, i);
+
+ /* pop Stack[a] for each definition of a var a in the original S */
+ for(a = 0; a < ls->ssavarcount; a++) {
+ ls->stack_top[a] -= def_count[a];
+ _SSA_ASSERT(ls->stack_top[a] >= 0);
+ }
+}
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ */
--- /dev/null
+/* src/vm/jit/optimizing/ssa.h - static single assignment form header
+
+ Copyright (C) 2005 - 2007 R. Grafl, A. Krall, C. Kruegel, C. Oates,
+ R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
+ C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
+ Institut f. Computersprachen - TU Wien
+
+ This file is part of CACAO.
+
+ This program is free software; you can redistribute it and/or
+ modify it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 2, or (at
+ your option) any later version.
+
+ This program is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: ssa.h$
+
+*/
+
+
+#ifndef _SSA_RENAME_H
+#define _SSA_RENAME_H
+
+#include "vm/jit/optimizing/graph.h"
+
+#if !defined(NDEBUG)
+# include <assert.h>
+#endif
+
+/* function prototypes */
+void ssa_rename_init(jitdata *jd, graphdata *gd);
+void ssa_rename(jitdata *jd, graphdata *gd, dominatordata *dd);
+
+#endif /* _SSA_RENAME_H */
+
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset): 4
+ * tab-width): 4
+ * End:
+ * vim:noexpandtab:sw=4:ts=4:
+ */
* Good: instruction.is_unresolved
* Bad: for i in range(0, bb.icount): instr = bb.instructions[i]
* Good: for instr in bb.instructions
+
+ TODO:
+
+ * Everywhere we return a variable number, we should return a varinfo
+ (varinfo wrapper has an index member anyways)
*/
#include <Python.h>
+#include "vm/global.h"
#include "vm/jit/python.h"
#include "vm/jit/show.h"
+#if defined(ENABLE_THREADS)
+# include "threads/lock-common.h"
+#endif
+
+#if defined(ENABLE_THREADS)
+static java_object_t *python_global_lock;
+#endif
/*
* Defs
F_CLASS_CALL_RETURN_TYPE,
F_CLASS_CALL_ARGS,
F_CLASSREF,
- F_DST,
+ F_CONTROL_FLOW,
+ F_CONTROL_FLOW_EX,
+ F_DATA_FLOW,
+ F_DATA_FLOW_EX,
F_DESCRIPTOR,
+ F_DST,
F_EXCEPTION_HANDLER,
F_FIELD_TYPE,
F_FIELD,
+ F_INDEX,
F_INSTRUCTIONS,
F_IS_CLASS_CONSTANT,
+ F_IS_INOUT,
+ F_IS_LOCAL,
+ F_IS_PREALLOCATED,
+ F_IS_SAVED,
+ F_IS_TEMPORARY,
F_IS_UNRESOLVED,
F_LOCAL_METHODINFO,
F_KLASS,
F_OPCODE,
F_OPCODE_EX,
F_PARAM_TYPES,
+ F_PEI,
+ F_PEI_EX,
F_PREDECESSORS,
F_REACHED,
F_RETURN_TYPE,
{ "call_return_type", F_CLASS_CALL_RETURN_TYPE },
{ "call_args", F_CLASS_CALL_ARGS },
{ "classref", F_CLASSREF },
- { "dst", F_DST },
+ { "control_flow", F_CONTROL_FLOW },
+ { "control_flow_ex", F_CONTROL_FLOW_EX },
+ { "data_flow", F_DATA_FLOW },
+ { "data_flow_ex", F_DATA_FLOW_EX },
{ "descriptor", F_DESCRIPTOR },
+ { "dst", F_DST },
{ "exception_handler", F_EXCEPTION_HANDLER },
{ "field", F_FIELD },
{ "field_type", F_FIELD_TYPE },
+ { "index", F_INDEX },
{ "instructions", F_INSTRUCTIONS },
- { "is_unresolved", F_IS_UNRESOLVED },
{ "is_class_constant", F_IS_CLASS_CONSTANT },
+ { "is_inout", F_IS_INOUT },
+ { "is_local", F_IS_LOCAL },
+ { "is_preallocated", F_IS_PREALLOCATED },
+ { "is_saved", F_IS_SAVED },
+ { "is_temporary", F_IS_TEMPORARY },
+ { "is_unresolved", F_IS_UNRESOLVED },
{ "klass", F_KLASS },
{ "line", F_LINE },
{ "local_map", F_LOCAL_MAP },
{ "opcode", F_OPCODE },
{ "opcode_ex", F_OPCODE_EX },
{ "param_types", F_PARAM_TYPES },
+ { "pei", F_PEI },
+ { "pei_ex", F_PEI_EX },
{ "predecessors", F_PREDECESSORS },
{ "reached", F_REACHED },
{ "return_type", F_RETURN_TYPE },
}
}
+static inline int instruction_opcode_ex(instruction *iptr) {
+ if (iptr->opc == ICMD_BUILTIN) {
+ return iptr->sx.s23.s3.bte->opcode;
+ } else {
+ return iptr->opc;
+ }
+}
+
ITERATOR_FUNC(call_args_iter_func) {
instruction *iptr = (instruction *)state->data;
switch (op) {
case F_OPCODE:
return get_int(arg->get.result, iptr->opc);
case F_OPCODE_EX:
- if (iptr->opc == ICMD_BUILTIN) {
- return get_int(arg->get.result, iptr->sx.s23.s3.bte->opcode);
- } else {
- return get_int(arg->get.result, iptr->opc);
- }
+ return get_int(arg->get.result, instruction_opcode_ex(iptr));
case F_NAME:
return get_string(arg->get.result, icmd_table[iptr->opc].name);
case F_NAME_EX:
- if (iptr->opc == ICMD_BUILTIN) {
- return get_string(arg->get.result, icmd_table[iptr->sx.s23.s3.bte->opcode].name);
- } else {
- return get_string(arg->get.result, icmd_table[iptr->opc].name);
- }
+ return get_string(arg->get.result, icmd_table[instruction_opcode_ex(iptr)].name);
case F_S1:
return get_int(arg->get.result, iptr->s1.varindex);
case F_S2:
return get_int(arg->get.result, iptr->line);
case F_SHOW:
return get_obj(arg->get.result, instruction_show_func, state->jd, iptr);
+ case F_PEI:
+ return get_bool(arg->get.result, icmd_table[iptr->opc].flags & ICMDTABLE_PEI);
+ case F_PEI_EX:
+ return get_bool(arg->get.result, icmd_table[instruction_opcode_ex(iptr)].flags & ICMDTABLE_PEI);
+ case F_DATA_FLOW:
+ return get_int(arg->get.result, icmd_table[iptr->opc].dataflow);
+ case F_DATA_FLOW_EX:
+ return get_int(arg->get.result, icmd_table[instruction_opcode_ex(iptr)].dataflow);
+ case F_CONTROL_FLOW:
+ return get_int(arg->get.result, icmd_table[iptr->opc].controlflow);
+ case F_CONTROL_FLOW_EX:
+ return get_int(arg->get.result, icmd_table[instruction_opcode_ex(iptr)].controlflow);
}
}
CLASS_FUNC(varinfo_func) {
+ jitdata *jd = state->jd;
varinfo *var = (varinfo *)state->vp;
+ int index = var - jd->var;
switch (op) {
case CLASS_GET_FIELD:
switch (arg->get.field) {
case F_TYPE:
return get_int(arg->get.result, var->type);
+ case F_IS_LOCAL:
+ return get_bool(arg->get.result, index < jd->localcount);
+ case F_IS_PREALLOCATED:
+ return get_bool(
+ arg->get.result,
+ (index >= jd->localcount) && (var->flags & PREALLOC)
+ );
+ case F_IS_INOUT:
+ return get_bool(
+ arg->get.result,
+ (index >= jd->localcount) && !(var->flags && PREALLOC) && (var->flags & INOUT)
+ );
+ case F_IS_TEMPORARY:
+ return get_bool(
+ arg->get.result,
+ (index >= jd->localcount) && !(var->flags && PREALLOC) && !(var->flags & INOUT)
+ );
+ case F_IS_SAVED:
+ return get_bool(arg->get.result, var->flags & SAVEDVAR);
+ case F_INDEX:
+ return get_int(arg->get.result, index);
}
+
}
return -1;
}
c(TYPE_VOID);
c(UNUSED);
+ /* data flow */
+
+ c(DF_0_TO_0);
+ c(DF_1_TO_0);
+ c(DF_2_TO_0);
+ c(DF_3_TO_0);
+ c(DF_DST_BASE);
+ c(DF_0_TO_1);
+ c(DF_1_TO_1);
+ c(DF_2_TO_1);
+ c(DF_3_TO_1);
+ c(DF_N_TO_1);
+ c(DF_INVOKE);
+ c(DF_BUILTIN);
+ c(DF_COPY);
+ c(DF_MOVE);
+ c(DF_DUP);
+ c(DF_DUP_X1);
+ c(DF_DUP_X2);
+ c(DF_DUP2);
+ c(DF_DUP2_X1);
+ c(DF_DUP2_X2);
+ c(DF_SWAP);
+ c(DF_LOAD);
+ c(DF_STORE);
+ c(DF_IINC);
+ c(DF_POP);
+ c(DF_POP2);
+
+ /* control flow */
+
+ c(CF_NORMAL);
+ c(CF_IF);
+ c(CF_END_BASE);
+ c(CF_END);
+ c(CF_GOTO);
+ c(CF_TABLE);
+ c(CF_LOOKUP);
+ c(CF_JSR);
+ c(CF_RET);
+
# undef c
}
constants(m);
}
+#if defined(ENABLE_THREADS)
+ python_global_lock = NEW(java_object_t);
+ LOCK_INIT_OBJECT_LOCK(python_global_lock);
+#endif
+
}
void pythonpass_cleanup() {
PyObject *pyarg = NULL;
int success = 0;
+ LOCK_MONITOR_ENTER(python_global_lock);
+
pymodname = PyString_FromString(module);
pymod = PyImport_Import(pymodname);
Py_XDECREF(pyargs);
Py_XDECREF(pyret);
+ LOCK_MONITOR_EXIT(python_global_lock);
+
return (success == 1 ? 1 : 0);
}
printf("\n");
+ if (irstage >= SHOW_CFG) {
+ printf("succs: %d [ ", bptr->successorcount);
+
+ for (i = 0; i < bptr->successorcount; i++)
+ printf("%d ", bptr->successors[i]->nr);
+
+ printf("]\n");
+ }
+
if (irstage >= SHOW_STACK) {
printf("IN: ");
show_variable_array(jd, bptr->invars, bptr->indepth, irstage);
#if defined(ENABLE_IFCONV)
{ "ifconv", false, OPT_IFCONV },
#endif
-#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
+#if defined(ENABLE_LSRA)
{ "lsra", false, OPT_LSRA },
#endif
+#if defined(ENABLE_SSA)
+ { "lsra", true, OPT_LSRA },
+#endif
#if defined(ENABLE_INTRP)
/* interpreter options */
puts(" -lsra use linear scan register allocation");
#endif
#if defined(ENABLE_SSA)
- puts(" -lsra use linear scan register allocation (with SSA)");
+ puts(" -lsra:... use linear scan register allocation (with SSA)");
+ puts(" (d)ead code elimination");
+ puts(" (c)opy propagation");
#endif
#if defined(ENABLE_DEBUG_FILTER)
puts(" -XXfi <regex> begin of dynamic scope for verbosecall filter");
break;
#endif
-#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
+#if defined(ENABLE_LSRA)
+ case OPT_LSRA:
+ opt_lsra = true;
+ break;
+#endif
+#if defined(ENABLE_SSA)
case OPT_LSRA:
opt_lsra = true;
+ for (i = 0; i < strlen(opt_arg); i++) {
+ switch (opt_arg[i]) {
+ case 'c':
+ opt_ssa_cp = true;
+ break;
+
+ case 'd':
+ opt_ssa_dce = true;
+ break;
+
+ case ':':
+ break;
+
+ default:
+ usage();
+ }
+ }
break;
#endif
#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
bool opt_lsra = false;
#endif
+#if defined(ENABLE_SSA)
+bool opt_ssa_dce = false; /* enable dead code elemination */
+bool opt_ssa_cp = false; /* enable copy propagation */
+#endif
/* interpreter options ********************************************************/
#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
extern bool opt_lsra;
#endif
-
+#if defined(ENABLE_SSA)
+extern bool opt_ssa_dce; /* enable dead code elemination */
+extern bool opt_ssa_cp; /* enable copy propagation */
+#endif
/* interpreter options ********************************************************/
projects / cacao.git / commitdiff