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: 377d8bc10488
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 675a56d4341d
Choose a head ref
  • 2 commits
  • 5 files changed
  • 1 contributor

Commits on Jun 7, 2016

  1. Address FIXMEs in LocalOptimizationPass 

    Removed some old conservative code. This should get rid
of more spurious copies (that were probably being handled
by OptimizeTempVarsPass that has been removed since).
    @subbuss
    subbuss committed Jun 7, 2016
    Copy the full SHA
    d41fac5 View commit details

  2. Replace EnsureTempsAssignedPass with AddMissingInitsPass 

    * Actually compute vars that might be undefined in a scope and
  add those initializers to the entry BB.
    @subbuss
    subbuss committed Jun 7, 2016
    Copy the full SHA
    675a56d View commit details
2 changes: 1 addition & 1 deletion core/src/main/java/org/jruby/ir/IRManager.java
View file
Original file line number Diff line number Diff line change
@@ -30,7 +30,7 @@
public class IRManager {
public static final String SAFE_COMPILER_PASSES = "";
public static final String DEFAULT_BUILD_PASSES = "";
public static final String DEFAULT_JIT_PASSES = "LocalOptimizationPass,DeadCodeElimination,OptimizeDynScopesPass,OptimizeDelegationPass,AddCallProtocolInstructions,EnsureTempsAssigned";
public static final String DEFAULT_JIT_PASSES = "LocalOptimizationPass,DeadCodeElimination,OptimizeDynScopesPass,OptimizeDelegationPass,AddCallProtocolInstructions,AddMissingInitsPass";
public static final String DEFAULT_INLINING_COMPILER_PASSES = "LocalOptimizationPass";

private final CompilerPass deadCodeEliminationPass = new DeadCodeElimination();
121 changes: 121 additions & 0 deletions core/src/main/java/org/jruby/ir/dataflow/analyses/DefinedVariableNode.java
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,121 @@
package org.jruby.ir.dataflow.analyses;

import org.jruby.dirgra.Edge;
import org.jruby.ir.dataflow.FlowGraphNode;
import org.jruby.ir.instructions.Instr;
import org.jruby.ir.instructions.ResultInstr;
import org.jruby.ir.operands.LocalVariable;
import org.jruby.ir.operands.Variable;
import org.jruby.ir.IRFlags;
import org.jruby.ir.representations.BasicBlock;

import java.util.*;

public class DefinedVariableNode extends FlowGraphNode<DefinedVariablesProblem, DefinedVariableNode> {
public DefinedVariableNode(DefinedVariablesProblem prob, BasicBlock n) {
super(prob, n);
}

@Override
public void init() {
setSize = problem.getDFVarsCount();
out = new BitSet(setSize);
computed = false;
}

private void addDFVar(Variable v) {
if (!problem.dfVarExists(v)) problem.addDFVar(v);
}

@Override
public void buildDataFlowVars(Instr i) {
if (i instanceof ResultInstr) addDFVar(((ResultInstr) i).getResult());
for (Variable x: i.getUsedVariables()) {
addDFVar(x);
}
}

@Override
public void applyPreMeetHandler() {
in = new BitSet(setSize);
// Init to all 1's so that when we 'and' with the
// first predecessor, we don't go to all 0's right away!
in.set(0, setSize);
}

@Override
public void compute_MEET(Edge e, DefinedVariableNode pred) {
// Only vars defined at the exit of all predecessors are considered defined on entry
if (pred.computed) {
in.and(pred.out);
}
}

@Override
public void initSolution() {
tmp = (BitSet) in.clone();
}

@Override
public void applyTransferFunction(Instr i) {
// v is defined
if (i instanceof ResultInstr) {
tmp.set(problem.getDFVar(((ResultInstr) i).getResult()));
}

// Variables that belong to outer scopes should always
// be considered defined.
for (Variable v: i.getUsedVariables()) {
if (v instanceof LocalVariable && ((LocalVariable)v).getScopeDepth() > 0) {
tmp.set(problem.getDFVar(v));
}
}
}

public void identifyInits(Set<Variable> undefinedVars) {
int parentScopeDepth = 1;
if (problem.getScope().getFlags().contains(IRFlags.REUSE_PARENT_DYNSCOPE)) {
parentScopeDepth = 0;
}

initSolution();
for (Instr i: basicBlock.getInstrs()) {
// Variables that belong to outer scopes should always
// be considered defined.
for (Variable v: i.getUsedVariables()) {
if (!v.isSelf()) {
if (v instanceof LocalVariable && ((LocalVariable)v).getScopeDepth() >= parentScopeDepth) {
tmp.set(problem.getDFVar(v));
}

if (!tmp.get(problem.getDFVar(v))) {
// System.out.println("Variable " + v + " in instr " + i + " isn't defined!");
undefinedVars.add(v);
}
}
}

// v is defined
if (i instanceof ResultInstr) {
tmp.set(problem.getDFVar(((ResultInstr) i).getResult()));
}
}
}

@Override
public boolean solutionChanged() {
return !tmp.equals(out);
}

@Override
public void finalizeSolution() {
out = tmp;
computed = true;
}

private boolean computed;
private BitSet in; // Variables defined at entry of this node
private BitSet out; // Variables defined at exit of node
private BitSet tmp; // Temporary state while applying transfer function
private int setSize; // Size of the "this.in" and "this.out" bit sets
}
63 changes: 63 additions & 0 deletions core/src/main/java/org/jruby/ir/dataflow/analyses/DefinedVariablesProblem.java
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,63 @@
package org.jruby.ir.dataflow.analyses;

import org.jruby.ir.IRScope;
import org.jruby.ir.dataflow.DataFlowProblem;
import org.jruby.ir.operands.Variable;
import org.jruby.ir.representations.BasicBlock;

import java.util.*;

public class DefinedVariablesProblem extends DataFlowProblem<DefinedVariablesProblem, DefinedVariableNode> {
public static final String NAME = "Defined Variables Analysis";

public DefinedVariablesProblem(IRScope scope) {
super(DataFlowProblem.DF_Direction.FORWARD);
setup(scope);
}

public Integer getDFVar(Variable v) {
return dfVarMap.get(v);
}

public boolean dfVarExists(Variable v) {
return getDFVar(v) != null;
}

public Variable getVariable(int id) {
return varDfVarMap.get(id);
}

@Override
public DefinedVariableNode buildFlowGraphNode(BasicBlock bb) {
return new DefinedVariableNode(this, bb);
}

public void addDFVar(Variable v) {
Integer dfv = addDataFlowVar();
dfVarMap.put(v, dfv);
varDfVarMap.put(dfv, v);
vars.add(v);
}

public Set<Variable> findUndefinedVars() {
Set<Variable> undefinedVars = new HashSet<Variable>();
for (DefinedVariableNode n : flowGraphNodes) {
n.identifyInits(undefinedVars);
}
return undefinedVars;
}

public Set<Variable> getAllVars() {
return dfVarMap.keySet();
}

@Override
public String getName() {
return NAME;
}

/* ----------- Private Interface ------------ */
private HashMap<Variable, Integer> dfVarMap = new HashMap<Variable, Integer>();
private HashMap<Integer, Variable> varDfVarMap = new HashMap<Integer, Variable>();
private HashSet<Variable> vars = new HashSet<Variable>();
}
45 changes: 45 additions & 0 deletions core/src/main/java/org/jruby/ir/passes/AddMissingInitsPass.java
View file
Original file line number Diff line number Diff line change
@@ -0,0 +1,45 @@
package org.jruby.ir.passes;

import java.util.Set;

import org.jruby.ir.IRScope;
import org.jruby.ir.operands.Nil;
import org.jruby.ir.operands.Variable;
import org.jruby.ir.representations.BasicBlock;
import org.jruby.ir.representations.CFG;
import org.jruby.ir.instructions.CopyInstr;
import org.jruby.ir.dataflow.analyses.DefinedVariablesProblem;

public class AddMissingInitsPass extends CompilerPass {
@Override
public String getLabel() {
return "AddMissingInitsPass";
}

@Override
public Object execute(IRScope scope, Object... data) {
// Make sure flags are computed
scope.computeScopeFlags();

// Find undefined vars
DefinedVariablesProblem p = new DefinedVariablesProblem(scope);
p.compute_MOP_Solution();
Set<Variable> undefinedVars = p.findUndefinedVars();

// Add inits to entry
BasicBlock bb = scope.getCFG().getEntryBB();
int i = 0;
Variable first = null;
for (Variable v : undefinedVars) {
// System.out.println("Adding missing init for " + v + " in " + scope);
if (first == null) {
bb.getInstrs().add(i++, new CopyInstr(v, new Nil()));
first = v;
} else {
bb.getInstrs().add(i++, new CopyInstr(v, first));
}
}

return null;
}
}
46 changes: 17 additions & 29 deletions core/src/main/java/org/jruby/ir/passes/LocalOptimizationPass.java
View file
Original file line number Diff line number Diff line change
@@ -8,6 +8,8 @@
import org.jruby.ir.operands.Operand;
import org.jruby.ir.operands.Variable;
import org.jruby.ir.representations.BasicBlock;
import org.jruby.ir.instructions.ClosureAcceptingInstr;
import org.jruby.ir.operands.WrappedIRClosure;

import java.util.*;

@@ -105,6 +107,16 @@ public static Instr optInstr(IRScope s, Instr instr, Map<Operand,Operand> valueM
return newInstr;
}

private static boolean isDataflowBarrier(Instr i, IRScope s) {
boolean reset = false;
if (!i.isDead() && i instanceof ClosureAcceptingInstr) {
Operand o = ((ClosureAcceptingInstr)i).getClosureArg();
reset = s.bindingHasEscaped() || (o != null && o instanceof WrappedIRClosure);
}

return reset;
}

public static void runLocalOptsOnInstrArray(IRScope s, Instr[] instrs) {
// Reset value map if this instruction is the start/end of a basic block
Map<Operand,Operand> valueMap = new HashMap<>();
@@ -116,21 +128,10 @@ public static void runLocalOptsOnInstrArray(IRScope s, Instr[] instrs) {
instrs[i] = newInstr;
}

// If the call has been optimized away in the previous step, it is no longer a hard boundary for opts!
//
// Right now, calls are considered hard boundaries for optimization and
// information cannot be propagated across them!
//
// SSS FIXME: Rather than treat all calls with a broad brush, what we need
// is to capture different attributes about a call :
// - uses closures
// - known call target
// - can modify scope,
// - etc.
//
// This information is present in instruction flags on CallBase. Use it!
// Reset simplification info if this starts/ends a basic block
// or if the instr is a dataflow barrier.
Operation iop = instr.getOperation();
if (iop.startsBasicBlock() || iop.endsBasicBlock() || (iop.isCall() && !instr.isDead())) {
if (iop.startsBasicBlock() || iop.endsBasicBlock() || isDataflowBarrier(instr, s)) {
valueMap = new HashMap<>();
simplificationMap = new HashMap<>();
}
@@ -151,21 +152,8 @@ public static void runLocalOptsOnBasicBlock(IRScope s, BasicBlock b) {
instrs.set(newInstr);
}

// If the call has been optimized away in the previous step, it is no longer a hard boundary for opts!
//
// Right now, calls are considered hard boundaries for optimization and
// information cannot be propagated across them!
//
// SSS FIXME: Rather than treat all calls with a broad brush, what we need
// is to capture different attributes about a call :
// - uses closures
// - known call target
// - can modify scope,
// - etc.
//
// This information is present in instruction flags on CallBase. Use it!
Operation iop = instr.getOperation();
if (iop.isCall() && !instr.isDead()) {
// Reset simplification info if this is a dataflow barrier.
if (isDataflowBarrier(instr, s)) {
valueMap = new HashMap<>();
simplificationMap = new HashMap<>();
}