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. 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 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 committed Jul 28, 2015
    Copy the full SHA
    6568e11 View commit details
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) {
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!");
}

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;
}

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
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;
}
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
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();
}