Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Browse files

Resolution to github issue #8.

Problem: In Frame.merge the operand stacks were being examined pointwise for differences, but due to an incorrect comparison, the analysis assumed that the stack had not changed.

TestYield/ExLoop are the relevant unit test and example code to exercise this functionality.

	modified:   .classpath
	modified:   src/kilim/analysis/Frame.java
	modified:   src/kilim/analysis/Usage.java
	modified:   src/kilim/tools/Asm.java
	modified:   src/kilim/tools/P.java
	modified:   test/kilim/test/TestYield.java
	new file:   test/kilim/test/ex/ExLoop.java
	modified:   test/kilim/test/ex/ExYieldStack.java
  • Loading branch information...
commit 1b54ce98dfac32bfccf20576af6b2a245cc85ac6 1 parent 4afe3bf
@kilim authored
View
2  .classpath
@@ -5,7 +5,7 @@
<classpathentry excluding="scala/" kind="src" path="bench"/>
<classpathentry kind="src" path="test"/>
<classpathentry kind="lib" path="libs/asm-all-2.2.3.jar" sourcepath="/Users/s/sw/asm-2.2.3/src"/>
- <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
<classpathentry kind="lib" path="libs/junit.jar"/>
+ <classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.launching.macosx.MacOSXType/1.6.0"/>
<classpathentry kind="output" path="classes"/>
</classpath>
View
4 src/kilim/analysis/Frame.java
@@ -66,8 +66,8 @@ public Frame merge(Frame inframe, boolean localsOnly, Usage usage) {
Value[] st = stack;
Value[] ist = inframe.stack;
for (int i = 0; i < slen; i++) {
- Value va = ist[i];
- Value vb = st[i];
+ Value va = st[i];
+ Value vb = ist[i];
if (va == vb || va.equals(vb)) continue;
Value newval = va.merge(vb);
if (newval != va) {
View
66 src/kilim/analysis/Usage.java
@@ -5,16 +5,20 @@
*/
package kilim.analysis;
+
import java.util.ArrayList;
import java.util.BitSet;
/**
- * Each BasicBlock owns one instance of Usage.
- * This class maintains, in essence, three vectors of booleans, indexed by the
- * local variable number. Since it is <i>very</i> rare for a method to
- * have more than 31 local variables, the vectors are represented by int
- * bitmaps. For more than this, the basic block creates an instance of BigUsage
- * that is functionally identical (TODO)
+ * Each BasicBlock owns one instance of Usage. This class maintains, in essence, three vectors of
+ * booleans, indexed by the local variable number. Since it is <i>very</i> rare for a method to have
+ * more than 31 local variables, the vectors are represented by int bitmaps. For more than this, the
+ * basic block creates an instance of BigUsage that is functionally identical (TODO)
+ *
+ * Note that we don't need to track usage of operand stack. All elements of the operand stack are
+ * always live, and always need to be stored and restored (during stack switching). This is not true
+ * of local vars; a var may have a valid value which may not be used downstream, so we track which
+ * vars must be taken seriously.
*
* @see BasicBlock
*/
@@ -30,24 +34,22 @@
private BitSet in;
/**
- * use.bit(i) == 1 (from LSB) if the ith var is read before it has been
- * written. The bit vector as a whole represents the set of vars that the
- * BB needs from its predecessors.
+ * use.bit(i) == 1 (from LSB) if the ith var is read before it has been written. The bit vector
+ * as a whole represents the set of vars that the BB needs from its predecessors.
*/
private BitSet use;
/**
- * def.bit(i) == 1 (from LSB) if the ith var is written into before it has
- * been read. It represents all the vars that this BB is capable of
- * supplying downstream on its own, hence those vars are not required to be
- * supplied by its predecessors (even if they do supply them, they will be
- * overwritten anyway).
+ * def.bit(i) == 1 (from LSB) if the ith var is written into before it has been read. It
+ * represents all the vars that this BB is capable of supplying downstream on its own, hence
+ * those vars are not required to be supplied by its predecessors (even if they do supply them,
+ * they will be overwritten anyway).
*/
private BitSet def;
public Usage(int numLocals) {
nLocals = numLocals;
- in = new BitSet(numLocals);
+ in = new BitSet(numLocals);
use = new BitSet(numLocals);
def = new BitSet(numLocals);
}
@@ -71,24 +73,24 @@ public void write(int var) {
public boolean isLiveIn(int var) {
return in.get(var);
}
-
+
/**
- * This is the standard liveness calculation (Dragon Book, section 10.6). At
- * each BB (and its corresponding usage), we evaluate "in" using use and
- * def. in = use U (out \ def) where out = U succ.in, for all successors
+ * This is the standard liveness calculation (Dragon Book, section 10.6). At each BB (and its
+ * corresponding usage), we evaluate "in" using use and def. in = use U (out \ def) where out =
+ * U succ.in, for all successors
*/
public boolean evalLiveIn(ArrayList<Usage> succUsage) {
BitSet out = new BitSet(nLocals);
- BitSet old_in = (BitSet)in.clone();
+ BitSet old_in = (BitSet) in.clone();
if (succUsage.size() == 0) {
in = use;
} else {
- // calculate out = U succ.in
+ // calculate out = U succ.in
out = (BitSet) succUsage.get(0).in.clone();
for (int i = 1; i < succUsage.size(); i++) {
out.or(succUsage.get(i).in);
}
- // calc out \ def == out & ~def == ~(out | def)
+ // calc out \ def == out & ~def == ~(out | def)
BitSet def1 = (BitSet) def.clone();
def1.flip(0, nLocals);
out.and(def1);
@@ -99,13 +101,12 @@ public boolean evalLiveIn(ArrayList<Usage> succUsage) {
}
/**
- * Called to coalesce a successor's usage into the current BB. Important: This
- * should be called before live variable analysis begins, because we don't
- * bother merging this.in.
+ * Called to coalesce a successor's usage into the current BB. Important: This should be called
+ * before live variable analysis begins, because we don't bother merging this.in.
*/
void absorb(Usage succ) {
- BitSet b = (BitSet)this.def.clone();
- b.flip(0,nLocals);
+ BitSet b = (BitSet) this.def.clone();
+ b.flip(0, nLocals);
b.and(succ.use);
this.use.or(b);
this.def.or(succ.def);
@@ -125,7 +126,8 @@ public String toString() {
private void printBits(StringBuffer sb, BitSet b) {
int numDefined = 0;
for (int i = 0; i < nLocals; i++) {
- if (b.get(i)) numDefined++;
+ if (b.get(i))
+ numDefined++;
}
sb.append('(').append(numDefined).append("): ");
for (int i = 0; i < nLocals; i++) {
@@ -136,13 +138,15 @@ private void printBits(StringBuffer sb, BitSet b) {
}
/**
- * This is purely for testing purposes.
- * @param var local var index
+ * This is purely for testing purposes.
+ *
+ * @param var
+ * local var index
*/
public void setLiveIn(int var) {
in.set(var);
}
-
+
Usage copy() {
Usage ret = new Usage(nLocals);
ret.use = use;
View
25 src/kilim/tools/Asm.java
@@ -113,8 +113,9 @@ public Asm(String afileName) throws IOException {
}
// .class public final Foo/Bar/Baz
- private static String classNamePatternStr = "[\\w/]+";
- private static Pattern classPattern = Pattern.compile("\\.(class|interface) (.*?)?(" + classNamePatternStr + ")$");
+ private static String classNamePatternStr = "[\\w/$]+";
+ private static String modifierPatternStr = "public|private|protected|static|final|synchronized|volatile|transient|native|abstract|strict| ";
+ private static Pattern classPattern = Pattern.compile("\\.(class|interface) ((" + modifierPatternStr + ")*)(" + classNamePatternStr + ")$");
private void parseClass() {
readLine();
// match class declaration
@@ -128,7 +129,7 @@ private void parseClass() {
}
acc |= parseModifiers(group(2));
- className = group(3);
+ className = group(4);
String superClassName = parseSuper();
String[] interfaces = parseInterfaces();
cv.visit(V1_5, acc, className, null, superClassName, interfaces);
@@ -197,15 +198,14 @@ private void parseClassBody() {
// The field declaration "public final String fileName = "foobar" is declared as
// .field public final fieldName [[Ljava/lang/String; = "foobar"
// .field (modifier)* name type (= constval)?
- private static String modifierPatternStr = "public|private|protected|static|final|synchronized|volatile|transient|native|abstract|strict| ";
private static String namePatternStr = "[$\\w]+";
private static String descPatternStr = "[$\\[\\w/;]+";
private static Pattern fieldPattern =
- Pattern.compile(".field +(" + modifierPatternStr + ")* +(" + namePatternStr + ") +(" + descPatternStr + ") *(= *(.*))?");
+ Pattern.compile(".field +((" + modifierPatternStr + ")*) +(" + namePatternStr + ") +(" + descPatternStr + ") *(= *(.*))?");
private void parseField() {
- String name = group(2);
- String desc = group(3);
- String valueStr = group(5);
+ String name = group(3);
+ String desc = group(4);
+ String valueStr = group(6);
Object value = valueStr == null ? null :
parseValue(valueStr,
(desc.equals(D_DOUBLE) || desc.equals(D_LONG)));
@@ -223,13 +223,13 @@ private void parseField() {
// .method private final static foobar(IJZ)[[Ljava/lang/Object;
// .method <init>(IJZ)
private static String methodNamePatternStr = "[<>\\w]+"; //
- private static Pattern methodPattern = Pattern.compile(".method +("+ modifierPatternStr + ")* ("+ methodNamePatternStr + ") *([(][^\\s]+)");
+ private static Pattern methodPattern = Pattern.compile(".method +(("+ modifierPatternStr + ")*) ("+ methodNamePatternStr + ") *([(][^\\s]+)");
private void parseMethod() {
eofOK = false;
- methodName = group(2);
+ methodName = group(3);
int acc = parseModifiers(group(1));
- String desc = group(3);
+ String desc = group(4);
String[] exceptions = parseMethodExceptions();
mv = cv.visitMethod(
@@ -744,7 +744,8 @@ boolean lineMatch(Pattern p) {
}
String group(int i) {
- return lastMatch.group(i);
+ String ret = lastMatch.group(i);
+ return ret;
}
int groupCount() {
View
15 src/kilim/tools/P.java
@@ -10,29 +10,34 @@
// than calling System.out.println.
public class P {
- // Call as /kilim/tools/P/pi(I)V
+ // Call as invokestatic kilim/tools/P/pi(I)V
public static void pi(int i) {
System.out.println(i);
}
- // Call as /kilim/tools/P/pn()V
+ // Call as invokestatic kilim/tools/P/pn()V
public static void pn() {
System.out.println();
}
- // Call as /kilim/tools/P/pn(Ljava/lang/Object;)V
+ // Call as invokestatic kilim/tools/P/pn(Ljava/lang/Object;)V
public static void pn(Object o) {
System.out.println(o);
}
- // Call as /kilim/tools/P/p(Ljava/lang/Object;)V
+ // Call as invokestatic kilim/tools/P/p(Ljava/lang/Object;)V
public static void p(Object o) {
System.out.print(o);
}
- // Call as /kilim/tools/P/ps(Ljava/lang/Object;)V
+ // Call as invokestatic kilim/tools/P/ps(Ljava/lang/Object;)V
public static void ps(Object o) {
System.out.print(o);
System.out.print(" ");
}
+ // Call as invokestatic kilim/tools/P/ptest()V
+ public static void ptest() {
+ System.out.println("test");
+ }
+
}
View
7 test/kilim/test/TestYield.java
@@ -46,6 +46,13 @@ public void testDupsInStack() throws Exception {
public void testConstantsInStack() throws Exception {
runTask(new kilim.test.ex.ExYieldConstants(0));
}
+
+ public void testLoop() throws Exception {
+ kilim.test.ex.ExLoop ex = new kilim.test.ex.ExLoop();
+ runTask(ex);
+ assertTrue(ex.verify());
+ }
+
public static void runTask(String taskClassName, int testCase) throws Exception {
ExYieldBase task;
View
30 test/kilim/test/ex/ExLoop.java
@@ -0,0 +1,30 @@
+package kilim.test.ex;
+
+import kilim.Pausable;
+import kilim.Task;
+
+public class ExLoop extends Task {
+ public String foo[] = new String[5];
+ String dummy() throws Pausable {
+ Task.yield();
+ return "dummy";
+ }
+ @Override
+ public void execute() throws Pausable, Exception {
+ for (int i = 0; i < foo.length; i++) {
+ // foo and i are on the operand stack before dummy gets called. This
+ // test checks that the operand stack is correctly restored.
+ foo[i] = dummy();
+ }
+ }
+
+ public boolean verify() {
+ // Call after ExLoop task has finished. foo[1..n] must have "dummy".
+ for (int i = 0; i < foo.length; i++) {
+ if (! "dummy".equals(foo[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
View
7 test/kilim/test/ex/ExYieldStack.java
@@ -55,6 +55,13 @@ void testFactorial_st() throws Pausable {
}
}
+ // Issue 8 on github
+ void testLoop() throws Pausable {
+ // The other tests don't test constant propagation, but not dynamic operands
+ // on stack.
+
+ }
+
static long fact_st(long n, boolean doPause) throws Pausable {
// System.out.println("n = " + n + ", doPause = " + doPause);
if (n == 1) {
Please sign in to comment.
Something went wrong with that request. Please try again.