This is the mail archive of the
kawa@sourceware.org
mailing list for the Kawa project.
experimental unreachability analysys
- From: Per Bothner <per at bothner dot com>
- To: "kawa at sourceware dot org" <kawa at sourceware dot org>
- Date: Tue, 02 Oct 2012 12:24:14 -0700
- Subject: experimental unreachability analysys
I'd be interested in people could try out the attached patch.
This provides a new and more precise unreachability/termination analysis.
The main task is to figure out conservatively if an expression cannot
return normally. It does that if it throws an uncaught exception,
exits from a block, calls a continuation, or has infinite recursion
(which encompasses tail-recursion/loops). In that case the expression
has the special never-returns type. Any expression which is executed
*after* a never-returns expression is therefore unreachable.
The hard part of course is infinite recursion or non-termination of
functions. In general this is undecidable, so we make some simplifications.
To start: If function f always calls g then h, then f can only finish if g
and h can finish. The problem is conditionals: If f calls g in one branch
of an if form, but calls h in the other branch, the f can finish if
g can finish *or* h can finish. So the analysis (done during the PushApply
phase) built a set of dependencies: f can finish if
(or
(and f11-can-finish f12-can-finish ....)
(and f21-can-finish f22-can-finish ....)
...)
This is represented by a ArrayList<HashSet<LambdaExp>> for each LambdaExp.
If at the end of analyzing a function we determine that it definitely can
finish (because one of the and sets is empty), then we notify any
function that depends on this function, to see if their dependency lists
can be simplified. At the end, any function that has not be simplified
to a known can-finish state can be safely (I believe) treated as if
it never terminates. This is because for every set of mutually
recursive functions there has to be a base case: at least one function
with at least one path (and-clause) that does not call any of the functions
- otherwise none of the functions will terminate.
There are various simplifications and optimizations as you can see in
the code.
Still, the algorithm seems to slow down compilation noticeably. I'm mulling
an alternative data structure: Instead of ArrayList<HashSet<LambdaExp>>
we'd use a Map<LambdaExp,IntNum> where the IntNum is a bitmask of the
possible paths - specifically a mask of indexes of the ArrayList in the
current data structure. I haven't quite figures that out, though.
It does not handle separate compilation, in that any previously-compiled
function is assume to terminate. (The intention is to use an annotation
to mark if a function never-returns.)
I'd appreciate feedback: Are the error messages helpful? Do you see
false positions? False negatives - unreachable code it should catch
(within the limitations of the framework)? Do you have code where
compilation time is seriously impacted by this change?
It does pretty well in my limited testing. At this point my main concern
is that it slows down compilation quite a bit. (I don't have strong
numbers, but running make check in the main testsuite directory is
about 30% slower, which means compilation is *at least* that much slower.)
Unreachability analysis is not only helpful to catch user errors.
It is also helpful for compiler correctness, since Kawa currently
can get confused by unreachable code, and fail with an internal error
or generate unverifiable bytecode.
--
--Per Bothner
per@bothner.com http://per.bothner.com/
Index: gnu/expr/ReferenceExp.java
===================================================================
--- gnu/expr/ReferenceExp.java (revision 7298)
+++ gnu/expr/ReferenceExp.java (working copy)
@@ -195,6 +195,8 @@
Expression dval = decl.getValue();
if (dval != null)
return dval.validateApply(exp, visitor, required, decl);
+ if (decl.type == ClassType.make("kawa.lang.Continuation")) // FIXME
+ exp.setType(Type.neverReturnsType);
}
}
else if (getSymbol() instanceof Symbol)
Index: gnu/expr/ChainLambdas.java
===================================================================
--- gnu/expr/ChainLambdas.java (revision 7298)
+++ gnu/expr/ChainLambdas.java (working copy)
@@ -23,8 +23,9 @@
}
protected void maybeWarnUnreachable(Expression exp) {
- if (! unreachableCodeSeen && comp.warnUnreachable())
+ if (! unreachableCodeSeen && comp.warnUnreachable()) {
comp.error('w', "unreachable code", exp);
+ }
unreachableCodeSeen = true;
}
@@ -39,8 +40,9 @@
exp.exps[i] = e;
if (e.neverReturns() && neverReturnsIndex < 0) {
neverReturnsIndex = i;
- if (i < last)
+ if (i < last) {
maybeWarnUnreachable(exp.exps[i+1]);
+ }
}
}
if (neverReturnsIndex >= 0) {
@@ -65,7 +67,13 @@
Expression[] xargs = new Expression[i+2];
xargs[0] = exp.func;
System.arraycopy(args, 0, xargs, 1, i+1);
- maybeWarnUnreachable(i+1 < nargs ? args[i+1] : exp);
+ if (i+1 < nargs || ! exp.isAppendValues()) {
+ if (! unreachableCodeSeen && comp.warnUnreachable()) {
+ comp.error('w', "unreachable procedure call", exp);
+ comp.error('i', "this operand never finishes", args[i]);
+ }
+ unreachableCodeSeen = true;
+ }
BeginExp bexp = new BeginExp(xargs);
bexp.type = Type.neverReturnsType;
return bexp;
@@ -75,6 +83,18 @@
return exp;
}
+ protected Expression visitSetExp(SetExp sexp, ScopeExp scope) {
+ Expression r = super.visitSetExp(sexp, scope);
+ if (r == sexp) {
+ Expression rval = sexp.getNewValue();
+ if (rval.neverReturns()) {
+ maybeWarnUnreachable(sexp);
+ return rval;
+ }
+ }
+ return r;
+ }
+
protected Expression visitIfExp(IfExp exp, ScopeExp scope) {
Expression e = visit(exp.test, scope);
if (e.neverReturns()) {
Index: gnu/expr/ApplyExp.java
===================================================================
--- gnu/expr/ApplyExp.java (revision 7298)
+++ gnu/expr/ApplyExp.java (working copy)
@@ -57,6 +57,12 @@
return func instanceof QuoteExp ? ((QuoteExp) func).getValue() : null;
}
+ public boolean isAppendValues() {
+ return func instanceof QuoteExp
+ && (((QuoteExp) func).getValue()
+ == gnu.kawa.functions.AppendValues.appendValues);
+ }
+
public ApplyExp (Expression f, Expression... a) { func = f; args = a; }
public ApplyExp (Procedure p, Expression... a) { this(new QuoteExp(p), a); }
Index: gnu/expr/PushApply.java
===================================================================
--- gnu/expr/PushApply.java (revision 7298)
+++ gnu/expr/PushApply.java (working copy)
@@ -1,5 +1,8 @@
package gnu.expr;
+import gnu.bytecode.Type;
+import java.util.*;
+
/** Re-arranges ApplyExp where the function is a LetExp or BeginExp.
Optimizes ((let (...) body) . args) to (let (...) (body . args)).
Optimizes ((begin ... last) . args) to (begin ... (last . args)).
@@ -13,6 +16,8 @@
public class PushApply extends ExpVisitor<Expression,Void>
{
+ public static boolean checkReachable = true;
+
public static void pushApply (Expression exp, Compilation comp)
{
PushApply visitor = new PushApply();
@@ -45,6 +50,12 @@
if (fdecl != null && ! fdecl.hasUnknownValue()
&& ! fdecl.inExternalModule(comp))
fdecl.addCaller(exp);
+ Expression fval = fdecl == null ? null : fdecl.getValue(); // follow FIXME
+ if (checkReachable && fval != null
+ && fval.getClass() == LambdaExp.class
+ && ! canFinishTracker.ignoreThisFork) {
+ noteFinishDependency((LambdaExp) fval, currentLambda);
+ }
}
if (func instanceof LetExp
&& ! (func instanceof FluidLetExp)) // [APPLY-LET]
@@ -78,6 +89,22 @@
return exp;
}
+ void noteFinishDependency(LambdaExp callee, LambdaExp caller) {
+ if (callee == caller || callee.body.type == Type.neverReturnsType) {
+ canFinishTracker.dependencyAddedThisFork = true;
+ caller.canFinishCondition = LambdaExp.CANNOT_FINISH;
+ } else if (caller.canFinishCondition != LambdaExp.CAN_FINISH) {
+ ArrayList<HashSet<LambdaExp>> deps = canFinishDeps();
+ int ndeps = deps.size();
+ for (int i = 0; i < ndeps; i++) {
+ if (caller.canFinishCondition.get(i).add(callee))
+ canFinishTracker.dependencyAddedThisFork = true;
+ }
+ if (callee.canFinishListeners == null)
+ callee.canFinishListeners = new HashSet<LambdaExp>();
+ callee.canFinishListeners.add(caller);
+ }
+ }
protected Expression visitIfExp(IfExp exp, Void ignored) {
Expression test = exp.test;
if (test instanceof LetExp
@@ -100,8 +127,16 @@
stmts[last_index] = exp;
return visit(begin, ignored);
}
- else
- return super.visitIfExp(exp, ignored);
+ else {
+ exp.test = visitAndUpdate(exp.test, ignored);
+ forkPush();
+ exp.then_clause = visitAndUpdate(exp.then_clause, ignored);
+ forkNext();
+ if (exp.else_clause != null)
+ exp.else_clause = visitAndUpdate(exp.else_clause, ignored);
+ forkPop();
+ return exp;
+ }
}
protected Expression visitReferenceExp (ReferenceExp exp, Void ignored)
@@ -140,4 +175,101 @@
exp.declareParts(getCompilation());
return visitLambdaExp(exp, ignored);
}
+
+ protected Expression visitLambdaExp (LambdaExp exp, Void ignored) {
+ CanFinishTracker oldTracker = canFinishTracker;
+ CanFinishTracker newTracker = new CanFinishTracker();
+ canFinishTracker = newTracker;
+ newTracker.dependenciesAtForkStart = LambdaExp.CAN_FINISH;
+ LambdaExp saveLambda = currentLambda;
+ exp.setFlag(true, LambdaExp.IN_EXPWALKER);
+ currentLambda = exp;
+ try {
+ return super.visitLambdaExp(exp, ignored);
+ }
+ finally {
+ exp.setFlag(false, LambdaExp.IN_EXPWALKER);
+
+ if (exp.canFinishCondition == null)
+ exp.canFinishCondition = LambdaExp.CAN_FINISH;
+ exp.checkCanFinish();
+ currentLambda = saveLambda;
+ canFinishTracker = oldTracker;
+ }
+ }
+
+ class CanFinishTracker {
+ CanFinishTracker outer;
+
+ /** Don't need to update canFinishCondition in this fork of an If.
+ * The reason is that a prior fork did not add extra dependencies,
+ * or that we depend on something known not to return.
+ */
+ boolean ignoreThisFork;
+
+ boolean dependencyAddedThisFork;
+ ArrayList<HashSet<LambdaExp>> dependenciesAtForkStart;
+ ArrayList<HashSet<LambdaExp>> dependenciesPreviousForks;
+ }
+
+ CanFinishTracker canFinishTracker;
+
+ private static ArrayList<HashSet<LambdaExp>> cloneDeps(ArrayList<HashSet<LambdaExp>> deps) {
+ ArrayList<HashSet<LambdaExp>> result = new ArrayList<HashSet<LambdaExp>>();
+ for (HashSet<LambdaExp> x : deps)
+ result.add((HashSet<LambdaExp>) x.clone());
+ return result;
+ }
+
+ private static ArrayList<HashSet<LambdaExp>> canFinishDeps(CanFinishTracker outer) {
+ if (outer.dependenciesAtForkStart == null)
+ outer.dependenciesAtForkStart = cloneDeps(canFinishDeps(outer.outer));
+ return outer.dependenciesAtForkStart;
+ }
+
+ ArrayList<HashSet<LambdaExp>> canFinishDeps() {
+ if (currentLambda.canFinishCondition == null)
+ currentLambda.canFinishCondition = cloneDeps(canFinishDeps(canFinishTracker));
+ return currentLambda.canFinishCondition;
+ }
+
+ public void forkPush() {
+ LambdaExp curLambda = getCurrentLambda();
+ CanFinishTracker oldTracker = canFinishTracker;
+ CanFinishTracker newTracker = new CanFinishTracker();
+ newTracker.dependenciesAtForkStart = curLambda.canFinishCondition;
+ curLambda.canFinishCondition = null;
+ newTracker.ignoreThisFork = false;
+ newTracker.dependencyAddedThisFork = false;
+ newTracker.outer = oldTracker;
+ canFinishTracker = newTracker;
+ }
+
+ public void forkNext() {
+ LambdaExp curLambda = getCurrentLambda();
+ if (! canFinishTracker.dependencyAddedThisFork) {
+ canFinishTracker.ignoreThisFork = true;
+ canFinishTracker.dependenciesPreviousForks = null;
+ } else {
+ canFinishTracker.ignoreThisFork = false;
+ canFinishTracker.dependencyAddedThisFork = false;
+ if (canFinishTracker.dependenciesPreviousForks == null)
+ canFinishTracker.dependenciesPreviousForks = curLambda.canFinishCondition;
+ else {
+ canFinishTracker.dependenciesPreviousForks.addAll(curLambda.canFinishCondition);
+ }
+ curLambda.canFinishCondition = null;
+ }
+ }
+
+ public void forkPop() {
+ CanFinishTracker oldTracker = canFinishTracker;
+ forkNext();
+ LambdaExp curLambda = currentLambda;
+ if (canFinishTracker.ignoreThisFork)
+ curLambda.canFinishCondition = canFinishTracker.dependenciesAtForkStart;
+ else
+ curLambda.canFinishCondition = canFinishTracker.dependenciesPreviousForks;
+ canFinishTracker = oldTracker.outer;
+ }
}
Index: gnu/expr/FindTailCalls.java
===================================================================
--- gnu/expr/FindTailCalls.java (revision 7298)
+++ gnu/expr/FindTailCalls.java (working copy)
@@ -75,9 +75,7 @@
lexp = (LambdaExp) exp.func;
visitLambdaExp(lexp);
}
- else if (exp.func instanceof QuoteExp
- && (((QuoteExp) exp.func).getValue()
- == gnu.kawa.functions.AppendValues.appendValues))
+ else if (exp.isAppendValues())
isAppendValues = true;
else
{
Index: gnu/expr/LambdaExp.java
===================================================================
--- gnu/expr/LambdaExp.java (revision 7298)
+++ gnu/expr/LambdaExp.java (working copy)
@@ -5,7 +5,7 @@
import gnu.bytecode.*;
import gnu.mapping.*;
import gnu.lists.LList;
-import java.util.ArrayList;
+import java.util.*;
import gnu.kawa.functions.Convert;
/**
@@ -148,7 +148,8 @@
public static final int OVERLOADABLE_FIELD = 2048;
public static final int ATTEMPT_INLINE = 4096;
static final int INLINE_ONLY = 8192;
- protected static final int NEXT_AVAIL_FLAG = 16384;
+ public static final int IN_EXPWALKER = 0x4000;
+ protected static final int NEXT_AVAIL_FLAG = 0x8000;
/** True iff this lambda is only "called" inline. */
public final boolean getInlineOnly() { return (flags & INLINE_ONLY) != 0; }
@@ -283,6 +284,55 @@
public boolean usingCallContext()
{ return getCallConvention() >= Compilation.CALL_WITH_CONSUMER; }
+ /** This function can finish if specified functions can finish.
+ * I.e. call this function can complete normally is there is some i
+ * such that all members of canFinishDependencies.get(i) can finish.
+ * May be null if there is no dependency yet in the current execution
+ * path fork, in which case PsuhApply.canGinishDeps will realize it.
+ */
+ ArrayList<HashSet<LambdaExp>> canFinishCondition;
+
+ static ArrayList<HashSet<LambdaExp>> CAN_FINISH = new ArrayList();
+ static { CAN_FINISH.add(new HashSet<LambdaExp>()); }
+
+ static ArrayList<HashSet<LambdaExp>> CANNOT_FINISH = new ArrayList();
+
+ /** Set of functions whose canFinishCondition may depend on this. */
+ Set<LambdaExp> canFinishListeners;
+
+ void notifyCanFinish() {
+ Set<LambdaExp> listeners = canFinishListeners;
+ if (listeners != null) {
+ canFinishListeners = null;
+ for (LambdaExp f : listeners) {
+ f.checkCanFinish();
+ }
+ }
+ }
+
+ void checkCanFinish() {
+ ArrayList<HashSet<LambdaExp>> cond = canFinishCondition;
+ if (cond != null && ! getFlag(LambdaExp.IN_EXPWALKER)) {
+ // See if we can simplify exp.canFinishCondition.
+ // I.e. if any dependencies are now CAN_FINISH.
+ for (Set<LambdaExp> set : cond) {
+ Iterator<LambdaExp> callees = set.iterator();
+ while (callees.hasNext()) {
+ LambdaExp callee = callees.next();
+ if (callee.canFinishCondition == LambdaExp.CAN_FINISH)
+ callees.remove();
+ }
+ if (set.isEmpty()) {
+ canFinishCondition = LambdaExp.CAN_FINISH;
+ notifyCanFinish();
+ return;
+ }
+ }
+ }
+ }
+
+
+
public final boolean isHandlingTailCalls ()
{
return isModuleBody()
Index: gnu/expr/InlineCalls.java
===================================================================
--- gnu/expr/InlineCalls.java (revision 7300)
+++ gnu/expr/InlineCalls.java (working copy)
@@ -594,6 +594,10 @@
}
if (exp.getClass() == LambdaExp.class)
{
+ if (exp.canFinishCondition!=LambdaExp.CAN_FINISH
+ && exp.canFinishCondition!=null) {
+ exp.setReturnType(Type.neverReturnsType);
+ }
Declaration ldecl = exp.nameDecl;
boolean unknownCalls = true;
if (ldecl != null && ! exp.isClassMethod() && ldecl.isModuleLocal())
Index: testsuite/inlining.expected
===================================================================
--- testsuite/inlining.expected (revision 7298)
+++ testsuite/inlining.expected (working copy)
@@ -81,7 +81,7 @@
InliningTest.plusLambda1()int: 3 bytes
InliningTest.firstNegative(double[])double: 32 bytes
InliningTest.inlineTwoCalls(int)int: 27 bytes
-InliningTest.inlineTwoFunctions(java.lang.Object)java.lang.Object: 23 bytes
+InliningTest.inlineTwoFunctions(java.lang.Object)void: 23 bytes
InliningTest.checkEven(int)java.lang.Object: 34 bytes
InliningTest.constantPropagation1()int: 3 bytes
InliningTest.constantPropagation2()int: 3 bytes
@@ -89,8 +89,8 @@
InliningTest.factorialInfer1(int)java.lang.Object: 25 bytes
InliningTest.getFromVector1(gnu.lists.FVector,int)java.lang.Integer: 12 bytes
InliningTest.getFromVector2(gnu.lists.FVector,int)java.lang.Integer: 12 bytes
-InliningTest.topLevelRecurse1(gnu.lists.Pair)java.lang.Object: 10 bytes
-InliningTest.topLevelRecurse2(java.lang.Object,java.lang.Object)java.lang.Object: 7 bytes
+InliningTest.topLevelRecurse1(gnu.lists.Pair)void: 10 bytes
+InliningTest.topLevelRecurse2(java.lang.Object,java.lang.Object)void: 7 bytes
InliningTest.sum1(gnu.math.IntNum)java.lang.Object: 36 bytes
InliningTest.sum2(double)double: 30 bytes
cycle1.isIsEven(int)boolean: 17 bytes
Index: testsuite/unreach1.scm
===================================================================
--- testsuite/unreach1.scm (revision 7298)
+++ testsuite/unreach1.scm (working copy)
@@ -4,21 +4,23 @@
(define (bar2)
(list (primitive-throw java.lang.NullPointerException) 12 13))
-;; Diagnostic: unreach1.scm:6:58: warning - unreachable code
+;; Diagnostic: unreach1.scm:6:3: warning - unreachable procedure call
+;; Diagnostic: unreach1.scm:6:9: note - this operand never finishes
(define (bar3)
(list 12 (primitive-throw java.lang.NullPointerException) (sqrt 13)))
-;; Diagnostic: unreach1.scm:10:61: warning - unreachable code
+;; Diagnostic: unreach1.scm:11:3: warning - unreachable procedure call
+;; Diagnostic: unreach1.scm:11:12: note - this operand never finishes
(define (bar4)
(primitive-throw java.lang.NullPointerException)
13)
-;; Diagnostic: unreach1.scm:15:3: warning - unreachable code
+;; Diagnostic: unreach1.scm:17:3: warning - unreachable code
(define (bar5)
(begin (primitive-throw java.lang.NullPointerException)
13))
-;; Diagnostic: unreach1.scm:20:10: warning - unreachable code
+;; Diagnostic: unreach1.scm:22:10: warning - unreachable code
;;; Savannah bug #35524: Unreachable code is not an error
(define (foo)
@@ -27,4 +29,10 @@
(let l ()
(return #f)
(l)))))
-;; Diagnostic: unreach1.scm:29:8: warning - unreachable code
+;; Diagnostic: unreach1.scm:31:8: warning - unreachable code
+
+;;; Savannah bug #36560: eq? <endless-loop>
+(define (foo36560)
+ (eq? (let loop () (loop)) #t))
+;; Diagnostic: unreach1.scm:36:3: warning - unreachable procedure call
+;; Diagnostic: unreach1.scm:36:8: note - this operand never finishes
Index: testsuite/unreach3.scm
===================================================================
--- testsuite/unreach3.scm (revision 7298)
+++ testsuite/unreach3.scm (working copy)
@@ -1,5 +1,6 @@
(format #t "[~a]~%"
(* 10 (call/cc (lambda (k) (+ 2 (k 3))))))
-;; Diagnostic: unreach3.scm:2:15: warning - unreachable code
+;; Diagnostic: unreach3.scm:2:36: warning - unreachable procedure call
+;; Diagnostic: unreach3.scm:2:41: note - this operand never finishes
;30
;; Output: [30]