Skip to content

Commit

Permalink
Fix bug in LVA + simplify it
Browse files Browse the repository at this point in the history 
* LVA was attempting to analyze closures in the context of their
  parent scope's LVA context. The code was general enough that if
  we knew more information about specific call sites, it would have
  done better.

  However, in reality, given that we don't know too much about
  call sites, (a) all that code was extra complexity (b) it was
  really doing anything in terms of not being conservative (because
  all calls are being treated as dataflow barriers right now)
  (c) in the only case where it would not have been conservative,
  it was actually making an incorrect assumption that the closure
  will execute at the call site where it is defined and hence
  incorrectly marking a variable dead when it wasn't.

* The fix was to simply eliminate the analysis of closures in the
  context of the parent's scope. We already had support for
  independent LVA of closures which takes care of scenario (c) above
  by marking all dirtied vars live on "entry" (which in the case of
  LVA, which is a backwards pass, is the control flow exit).

  This now fixes the failing snippet (see below) and should also
  eliminate the remaining test:mri:jit failures.
[subbu@earth ir] jruby -Xjit.threshold=0 -e "z = 5; x = Hash.new {|h,kk| z = kk }; z=0; x[22]; p z"
22
  • Loading branch information
@subbuss
subbuss committed Mar 5, 2015
1 parent 8534d9f commit ed58d73
Show file tree
Hide file tree
Showing 2 changed files with 5 additions and 93 deletions.
87 changes: 2 additions & 85 deletions core/src/main/java/org/jruby/ir/dataflow/analyses/LiveVariableNode.java
View file
Expand Up @@ -103,86 +103,8 @@ public void applyTransferFunction(Instr i) {
// If so, we need to process the closure for live variable info.
if (i instanceof ClosureAcceptingInstr) {
Operand o = ((ClosureAcceptingInstr)i).getClosureArg();
// System.out.println("Processing closure: " + o + "-------");
if (o != null && o instanceof WrappedIRClosure) {
IRClosure cl = ((WrappedIRClosure)o).getClosure();
LiveVariablesProblem cl_lvp = (LiveVariablesProblem) cl.getDataFlowSolution(DataFlowConstants.LVP_NAME);
boolean needsInit = false;
if (cl_lvp == null) {
cl_lvp = new LiveVariablesProblem(cl, problem.getNonSelfLocalVars());
cl.setDataFlowSolution(cl_lvp.getName(), cl_lvp);
cl.computeScopeFlags();
needsInit = true;
}

// Add all living local variables.
Set<LocalVariable> liveVars = problem.addLiveLocalVars(new HashSet<LocalVariable>(), living);

// Collect variables live on entry of the closure -- they could all be live on exit as well (conservative, but safe).
//
// def foo
// i = 0;
// loop { i += 1; break if i > n }
// end
//
// Here, i is not live outside the closure, but it is clearly live on exit of the closure because
// it is reused on the next iteration. In the absence of information about the call accepting the closure,
// we have to assume that all vars live on exit from the closure will be live on entry into the closure as well
// because of looping.
List<Variable> liveOnEntryBefore = cl_lvp.getVarsLiveOnScopeEntry();
for (Variable y: liveOnEntryBefore) {
if (y instanceof LocalVariable) liveVars.add((LocalVariable)y);
}

// Collect variables live out of the exception target node. Since this call can directly jump to
// the rescue block (or scope exit) without executing the rest of the instructions in this bb, we
// have a control-flow edge from this call to that block. Since we dont want to add a
// control-flow edge from pretty much every call to the rescuer/exit BB, we are handling it
// implicitly here.
if (i.canRaiseException()) problem.addLiveLocalVars(liveVars, getExceptionTargetNode().out);

// Run LVA on the closure to propagate current LVA state through the closure
// SSS FIXME: Think through this .. Is there any way out of having
// to recompute the entire lva for the closure each time through?
cl_lvp.setVarsLiveOnScopeExit(liveVars);
if (needsInit) {
// Init DF vars from this set
for (Variable v: liveVars) {
cl_lvp.addDFVar(v);
}
}
cl_lvp.compute_MOP_Solution();

// Check if liveOnScopeEntry added new vars -- if so, rerun.
// NOTE: This is conservative since we are not checking if some vars got deleted.
// But, this conservativeness guarantees forward progress of the analysis.
boolean changed;
List<Variable> liveOnEntryAfter;
do {
changed = false;
liveOnEntryAfter = cl_lvp.getVarsLiveOnScopeEntry();
for (Variable y: liveOnEntryAfter) {
if (y instanceof LocalVariable) {
LocalVariable ly = (LocalVariable)y;
if (!liveVars.contains(ly)) {
changed = true;
liveVars.add(ly);
}
}
}

if (changed) {
cl_lvp.setVarsLiveOnScopeExit(liveVars);
cl_lvp.compute_MOP_Solution();
}
} while (changed);

// Merge live on closure entry info into the current problem.
markAllVariablesLive(problem, liveOnEntryAfter);
}

// If this is a dataflow barrier -- mark all local vars but %self and %block live
if (scopeBindingHasEscaped) {
if ((o != null && o instanceof WrappedIRClosure) || scopeBindingHasEscaped) {
// System.out.println(".. call is a data flow barrier ..");
// Mark all non-self, non-block local variables live if 'c' is a dataflow barrier!
for (Variable x: problem.getNonSelfLocalVars()) {
Expand Down Expand Up @@ -303,12 +225,7 @@ void markDeadInstructions() {

if (i instanceof ClosureAcceptingInstr) {
Operand o = ((ClosureAcceptingInstr)i).getClosureArg();
if (o != null && o instanceof WrappedIRClosure) {
IRClosure cl = ((WrappedIRClosure)o).getClosure();
LiveVariablesProblem cl_lvp = (LiveVariablesProblem)cl.getDataFlowSolution(problem.getName());
// Collect variables live on entry and merge that info into the current problem.
markAllVariablesLive(problem, cl_lvp.getVarsLiveOnScopeEntry());
} else if (scopeBindingHasEscaped) {
if ((o != null && o instanceof WrappedIRClosure) || scopeBindingHasEscaped) {
// Mark all non-self, non-block local variables live if 'c' is a dataflow barrier!
for (Variable x: problem.getNonSelfLocalVars()) {
living.set(problem.getDFVar(x));
Expand Down
11 changes: 3 additions & 8 deletions core/src/main/java/org/jruby/ir/passes/LiveVariableAnalysis.java
View file
Expand Up @@ -19,7 +19,7 @@
import java.util.List;

public class LiveVariableAnalysis extends CompilerPass {
public static List<Class<? extends CompilerPass>> DEPENDENCIES = Arrays.<Class<? extends CompilerPass>>asList(CFGBuilder.class);
public static List<Class<? extends CompilerPass>> DEPENDENCIES = Arrays.<Class<? extends CompilerPass>>asList(CFGBuilder.class, OptimizeDynScopesPass.class);

@Override
public String getLabel() {
Expand Down Expand Up @@ -72,13 +72,8 @@ public Object execute(IRScope scope, Object... data) {
LiveVariablesProblem lvp = new LiveVariablesProblem(scope);

if (scope instanceof IRClosure) {
// Go conservative! Normally, closure scopes are analyzed
// in the context of their outermost method scopes where we
// have better knowledge of aliveness in that global context.
//
// But, if we are analyzing closures standalone, we have to
// conservatively assume that any dirtied variables that
// belong to an outer scope are live on exit.
// We have to conservatively assume that any dirtied variables
// that belong to an outer scope are live on exit.
Set<LocalVariable> nlVars = new HashSet<LocalVariable>();
collectNonLocalDirtyVars((IRClosure)scope, nlVars, scope.getFlags().contains(IRFlags.DYNSCOPE_ELIMINATED) ? -1 : 0);

Expand Down

0 comments on commit ed58d73

Please sign in to comment.