Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: jruby/jruby
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 80d9f19c3e03
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 6568e11b7c7f
Choose a head ref
  • 3 commits
  • 7 files changed
  • 1 contributor

Commits on Jul 28, 2015

  1. More dead code in LVA from f48c871

    @subbuss
    subbuss committed Jul 28, 2015
    Copy the full SHA
    503edc8 View commit details

  2. Move liveness tests out of DCE transform into LVA computation 

    DCE used to do additional tests to decide if an instruction can be
deleted based on the scope's state. This is a no-no. DCE should
not do any additional tests about deletability based on scope
state (which was in reality liveness tests) -- it should simply use
whatever info is produced by LVA. Those tests should have been
part of LVA instead.

This really didn't affect correctness of DCE, but it would be
providing incorrect information about vars still live when the
scope was exited. Specifically, AddLocalVarLoadStoreInstructions pass
uses that LVA information to determine whether to add lvar stores
on exit. Without accurate LVA information, this can inadvertently
prevent lvar updates from being seen outside the scope.

This is part 1 of the fix for #3173.
    @subbuss
    subbuss committed Jul 28, 2015
    Copy the full SHA
    d59eeec View commit details

  3. Fixes to AddLocalVarLoadStoreInstructions pass 

    The following fixes were made:

1. Same kind of fix as in d59eeec but applied to this pass.
   The actual addition of binding stores shouldn't do additional
   analysis not already present in the dataflow analysis. It should
   simply use information from that analysis and add stores, where
   required.

2. A specific outcome of 1. above is: the addition should not look
   at scope type while adding stores on exit. If the analysis says:
   "add a store", add a store. No need to do it for closures only.

3. There was a subtle bug in the code. For exit BBs, we were
   intersecting lvars that were dirtied with lvars that were live
   at that point. However, we were looking for 'varsLiveOnExit'
   which was erroneous. LVA is a backwards propagation problem
   and we should be looking at 'varsLiveOnEntry' (since the exit
   of the scope corresponds to the dataflow entry for LVA).

Between these fixes and the fix in 8c48c3bc, #3173 should be solved.
    @subbuss
    subbuss committed Jul 28, 2015
    Copy the full SHA
    6568e11 View commit details
17 changes: 13 additions & 4 deletions core/src/main/java/org/jruby/ir/dataflow/analyses/LiveVariableNode.java
View file
Original file line number Diff line number Diff line change
@@ -57,6 +57,14 @@ public void applyPreMeetHandler() {
in.set(problem.getDFVar(v));
}
}

// If this scope's binding has escaped, all variables
// should be considered live on exit from the scope.
if (problem.getScope().bindingHasEscaped()) {
for (Variable x: problem.getNonSelfLocalVars()) {
in.set(problem.getDFVar(x));
}
}
}
// System.out.println("Init state for BB " + basicBlock.getID() + " is " + toString());
}
@@ -216,18 +224,19 @@ void markDeadInstructions() {
if (living.get(dv)) {
living.clear(dv);
// System.out.println("NO! LIVE result:" + v);
} else if (i.canBeDeleted(scope)) {
// System.out.println("YES!");
} else if (i.isDeletable()) {
// System.out.println("YES! (result)");
i.markDead();
it.remove();
} else {
// System.out.println("NO! has side effects! Op is: " + i.getOperation());
}
} else if (i.canBeDeleted(scope)) {
} else if (i.isDeletable()) {
// System.out.println("YES! (non-result)");
i.markDead();
it.remove();
} else {
// System.out.println("IGNORING! No result!");
// System.out.println("NO! has side effects! Op is: " + i.getOperation());
}

if (i instanceof ClosureAcceptingInstr) {
22 changes: 5 additions & 17 deletions core/src/main/java/org/jruby/ir/dataflow/analyses/LiveVariablesProblem.java
View file
Original file line number Diff line number Diff line change
@@ -59,20 +59,6 @@ public void addDFVar(Variable v) {
}
}

/**
* Add all local variables of interest from the provided bitset.
*/
public Set<LocalVariable> addLiveLocalVars(Set<LocalVariable> list, BitSet living) {
for (int j = 0; j < living.size(); j++) {
if (!living.get(j)) continue;

Variable v = getVariable(j);
if (v instanceof LocalVariable) list.add((LocalVariable) v);
}

return list;
}

/**
* Get variables that are live on entry to the cfg.
* This is the case for closures which access variables from the parent scope.
@@ -81,15 +67,17 @@ public Set<LocalVariable> addLiveLocalVars(Set<LocalVariable> list, BitSet livin
*
* In the code snippet above, 'sum' is live on entry to the closure
*/
public List<Variable> getVarsLiveOnScopeEntry() {
List<Variable> liveVars = new ArrayList<Variable>();
public Collection<LocalVariable> getLocalVarsLiveOnScopeEntry() {
List<LocalVariable> liveVars = new ArrayList<LocalVariable>();
BitSet liveIn = getFlowGraphNode(getScope().getCFG().getEntryBB()).getLiveOutBitSet();

for (int i = 0; i < liveIn.size(); i++) {
if (!liveIn.get(i)) continue;

Variable v = getVariable(i);
liveVars.add(v);
if (v instanceof LocalVariable) {
liveVars.add((LocalVariable)v);
}
// System.out.println("variable " + v + " is live on entry!");
}

84 changes: 52 additions & 32 deletions core/src/main/java/org/jruby/ir/dataflow/analyses/StoreLocalVarPlacementNode.java
View file
Original file line number Diff line number Diff line change
@@ -35,8 +35,29 @@ public void buildDataFlowVars(Instr i) {

@Override
public void applyPreMeetHandler() {
BasicBlock bb = getBB();

// For rescue entries, <in> is handled specially
if (!getBB().isRescueEntry()) inDirtyVars = new HashSet<LocalVariable>();
if (!bb.isRescueEntry()) {
inDirtyVars = new HashSet<LocalVariable>();

// If this is the exit BB, we need a binding store on exit only for vars that are both:
//
// (a) dirty,
// (b) live on exit from the closure
// condition reqd. because the variable could be dirty but not used outside.
// Ex: s=0; a.each { |i| j = i+1; sum += j; }; puts sum
// i,j are dirty inside the block, but not used outside
if (bb.isExitBB()) {
LiveVariablesProblem lvp = problem.getScope().getLiveVariablesProblem();
java.util.Collection<LocalVariable> liveVars = lvp.getLocalVarsLiveOnScopeEntry();
if (liveVars != null) {
inDirtyVars.retainAll(liveVars); // Intersection with variables live on exit from the scope
} else {
inDirtyVars.clear();
}
}
}
}

@Override
@@ -97,6 +118,27 @@ public void applyTransferFunction(Instr i) {
}
dirtyVars = newDirtyVars;
}
} else if (i instanceof ReturnBase || i instanceof BreakInstr) {
// Wherever control leaves the scope (returns, breaks)
// we need a binding store on exit only for vars that are both:
//
// (a) dirty,
// (b) live on exit.
// condition useful because the variable could be dirty but not used outside.
// Ex: s=0; a.each { |i| j = i+1; sum += j; return if j < 5; sum += 1; }; puts sum
// i,j are dirty inside the block, but not used outside
//
// If this also happens to be exit BB, we would have intersected already earlier -- so no need to do it again!

if (!getBB().isExitBB()) {
LiveVariablesProblem lvp = scope.getLiveVariablesProblem();
java.util.Collection<LocalVariable> liveVars = lvp.getLocalVarsLiveOnScopeEntry();
if (liveVars != null) {
dirtyVars.retainAll(liveVars); // Intersection with variables live on exit from the scope
} else {
dirtyVars.clear();
}
}
}

if (scopeBindingHasEscaped && (i.getOperation() == Operation.PUT_GLOBAL_VAR)) {
@@ -117,8 +159,6 @@ public void applyTransferFunction(Instr i) {
// %self is local to every scope and never crosses scope boundaries and need not be spilled/refilled
if (v instanceof LocalVariable && !v.isSelf()) dirtyVars.add((LocalVariable) v);
}

if (i.getOperation().isReturn()) dirtyVars.clear();
}

@Override
@@ -147,24 +187,6 @@ public boolean addStores(Map<Operand, Operand> varRenameMap, Set<LocalVariable>

initSolution();

// If this is the exit BB, we need a binding store on exit only for vars that are both:
//
// (a) dirty,
// (b) live on exit from the closure
// condition reqd. because the variable could be dirty but not used outside.
// Ex: s=0; a.each { |i| j = i+1; sum += j; }; puts sum
// i,j are dirty inside the block, but not used outside

if (basicBlock.isExitBB()) {
LiveVariablesProblem lvp = scope.getLiveVariablesProblem();
java.util.Collection<LocalVariable> liveVars = lvp.getVarsLiveOnScopeExit();
if (liveVars != null) {
dirtyVars.retainAll(liveVars); // Intersection with variables live on exit from the scope
} else {
dirtyVars.clear();
}
}

while (instrs.hasNext()) {
Instr i = instrs.next();

@@ -228,21 +250,21 @@ public boolean addStores(Map<Operand, Operand> varRenameMap, Set<LocalVariable>
dirtyVars = newDirtyVars;
instrs.next();
}
} else if ((isClosure && (i instanceof ReturnInstr)) || (i instanceof BreakInstr)) {
// At closure return and break instructions (both of which are exits from the closure),
} else if (i instanceof ReturnBase || i instanceof BreakInstr) {
// Wherever control leaves the scope (returns, breaks)
// we need a binding store on exit only for vars that are both:
//
// (a) dirty,
// (b) live on exit from the closure
// condition reqd. because the variable could be dirty but not used outside.
// (b) live on exit.
// condition useful because the variable could be dirty but not used outside.
// Ex: s=0; a.each { |i| j = i+1; sum += j; return if j < 5; sum += 1; }; puts sum
// i,j are dirty inside the block, but not used outside
//
// If this also happens to be exit BB, we would have intersected already earlier -- so no need to do it again!

if (!basicBlock.isExitBB()) {
LiveVariablesProblem lvp = scope.getLiveVariablesProblem();
java.util.Collection<LocalVariable> liveVars = lvp.getVarsLiveOnScopeExit();
java.util.Collection<LocalVariable> liveVars = lvp.getLocalVarsLiveOnScopeEntry();
if (liveVars != null) {
dirtyVars.retainAll(liveVars); // Intersection with variables live on exit from the scope
} else {
@@ -252,18 +274,16 @@ public boolean addStores(Map<Operand, Operand> varRenameMap, Set<LocalVariable>

// Add before call
instrs.previous();
boolean f = problem.addClosureExitStoreLocalVars(instrs, dirtyVars, varRenameMap);
boolean f = problem.addScopeExitStoreLocalVars(instrs, dirtyVars, varRenameMap);
addedStores = addedStores || f;
instrs.next();

// Nothing is dirty anymore -- everything that needs spilling has been spilt
dirtyVars.clear();
}

if (
(scopeBindingHasEscaped && i.getOperation() == Operation.PUT_GLOBAL_VAR)
|| i.getOperation() == Operation.THREAD_POLL
) {
if ((scopeBindingHasEscaped && i.getOperation() == Operation.PUT_GLOBAL_VAR)
|| i.getOperation() == Operation.THREAD_POLL) {
// 1. Global-var tracing can execute closures set up in previous trace-var calls
// in which case we would have the 'scopeBindingHasEscaped' flag set to true.
// 2. Threads can update bindings, so we treat thread poll boundaries the same way.
@@ -311,7 +331,7 @@ public boolean addStores(Map<Operand, Operand> varRenameMap, Set<LocalVariable>
if (basicBlock.isExitBB()) {
// Last instr could be a return -- so, move iterator one position back
if (instrs.hasPrevious()) instrs.previous();
boolean f = problem.addClosureExitStoreLocalVars(instrs, dirtyVars, varRenameMap);
boolean f = problem.addScopeExitStoreLocalVars(instrs, dirtyVars, varRenameMap);
addedStores = addedStores || f;
}

4 changes: 2 additions & 2 deletions core/src/main/java/org/jruby/ir/dataflow/analyses/StoreLocalVarPlacementProblem.java
View file
Original file line number Diff line number Diff line change
@@ -62,7 +62,7 @@ TemporaryLocalVariable getLocalVarReplacement(LocalVariable v, Map<Operand, Oper
return value;
}

boolean addClosureExitStoreLocalVars(ListIterator<Instr> instrs, Set<LocalVariable> dirtyVars, Map<Operand, Operand> varRenameMap) {
boolean addScopeExitStoreLocalVars(ListIterator<Instr> instrs, Set<LocalVariable> dirtyVars, Map<Operand, Operand> varRenameMap) {
IRScope scope = getScope();
boolean addedStores = false;
boolean isEvalScript = scope instanceof IREvalScript;
@@ -132,7 +132,7 @@ public void addStores(Map<Operand, Operand> varRenameMap) {
Instr i = instrs.previous();
// Assumption: Last instr should always be a control-transfer instruction
assert i.getOperation().transfersControl(): "Last instruction of GEB in scope: " + getScope() + " is " + i + ", not a control-xfer instruction";
addClosureExitStoreLocalVars(instrs, dirtyVars, varRenameMap);
addScopeExitStoreLocalVars(instrs, dirtyVars, varRenameMap);
}
}
}
19 changes: 13 additions & 6 deletions core/src/main/java/org/jruby/ir/instructions/Instr.java
View file
Original file line number Diff line number Diff line change
@@ -143,24 +143,31 @@ public boolean computeScopeFlags(IRScope scope) {
}

/**
* Can this instruction be deleted? LVA will preserve instructions based on whether operands (variables)
* Can this instruction be deleted? LVA will preserve instructions based on whether operands (variables)
* are living but even if there are no living variables then the instruction itself may not be able to be removed
* during DCE for other reasons (like if it unconditionally has a side-effect or it happens to be living in a
* scope where a binding can escape and one of its operands is a local variable).
* during DCE for other reasons (like if it unconditionally has a side-effect)
*/
public boolean canBeDeleted(IRScope s) {
if (hasSideEffects() || operation.isDebugOp() || canRaiseException() || transfersControl()) return false;
public boolean isDeletable() {
return !(hasSideEffects() || operation.isDebugOp() || canRaiseException() || transfersControl());
}

public boolean canBeDeletedFromScope(IRScope s) {
if (!isDeletable()) {
return false;
}

if (this instanceof ResultInstr) {
Variable r = ((ResultInstr) this).getResult();

// An escaped binding needs to preserve lvars since that consumers of that binding may access lvars.
// An escaped binding needs to preserve lvars since
// consumers of that binding may access lvars.
if (s.bindingHasEscaped()) return !(r instanceof LocalVariable);
}

return true;
}


public void markDead() {
isDead = true;
}
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/ir/instructions/ToAryInstr.java
View file
Original file line number Diff line number Diff line change
@@ -29,7 +29,7 @@ public Operand getArray() {
}

@Override
public boolean canBeDeleted(IRScope s) {
public boolean canBeDeletedFromScope(IRScope s) {
// This is an instruction that can be safely deleted
// since it is inserted by JRuby to facilitate other operations
// and has no real side effects. Currently, this has been marked
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/ir/passes/LocalOptimizationPass.java
View file
Original file line number Diff line number Diff line change
@@ -81,7 +81,7 @@ public static Instr optInstr(IRScope s, Instr instr, Map<Operand,Operand> valueM

if (!instr.hasSideEffects()) {
if (instr instanceof CopyInstr) {
if (res.equals(val) && instr.canBeDeleted(s)) {
if (res.equals(val) && instr.canBeDeletedFromScope(s)) {
System.out.println("DEAD: marking instr dead!!");
instr.markDead();
}