Mercurial > hg > truffle
changeset 3046:f9e045cd2c23
Merge, add some edge spliting around loopbegin when necessary
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Fri Jun 17 14:53:07 2011 +0200 @@ -217,7 +217,7 @@ if (t instanceof RuntimeException) { throw (RuntimeException) t; } else { - throw new RuntimeException(t); + throw new RuntimeException("Exception while compiling: " + method,t); } } } finally {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Fri Jun 17 14:53:07 2011 +0200 @@ -133,4 +133,5 @@ public static boolean PrintLIRWithAssembly = ____; public static boolean OptCanonicalizer = true; + public static boolean OptLoops = true; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java Fri Jun 17 14:53:07 2011 +0200 @@ -25,8 +25,10 @@ import java.util.*; import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.graph.*; /** * This class optimizes moves, particularly those that result from eliminating SSA form.
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Fri Jun 17 14:53:07 2011 +0200 @@ -835,10 +835,10 @@ if (instr instanceof Phi) { Phi phi = (Phi) instr; TTY.println("phi block begin: " + phi.merge()); - TTY.println("pred count on blockbegin: " + phi.merge().predecessors().size()); + TTY.println("pred count on blockbegin: " + phi.merge().phiPointPredecessorCount()); TTY.println("phi values: " + phi.valueCount()); TTY.println("phi block preds:"); - for (Node n : phi.merge().predecessors()) { + for (Node n : phi.merge().phiPointPredecessors()) { TTY.println(n.toString()); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Fri Jun 17 14:53:07 2011 +0200 @@ -130,14 +130,14 @@ } stream.println(" </edges>"); - stream.println(" <controlFlow>"); if (schedule != null) { + stream.println(" <controlFlow>"); for (Block block : schedule.getBlocks()) { printBlock(graph, block); } + printNoBlock(); + stream.println(" </controlFlow>"); } - printNoBlock(); - stream.println(" </controlFlow>"); stream.println(" </graph>"); flush(); @@ -209,19 +209,19 @@ stream.printf(" <block name='%d'>%n", block.blockID()); stream.printf(" <successors>%n"); for (Block sux : block.getSuccessors()) { - if (sux.firstNode() instanceof LoopBegin && block.lastNode() instanceof LoopEnd) { - // Skip back edges. - } else { +// if (sux.firstNode() instanceof LoopBegin && block.lastNode() instanceof LoopEnd) { //TODO gd +// // Skip back edges. +// } else { stream.printf(" <successor name='%d'/>%n", sux.blockID()); - } +// } } stream.printf(" </successors>%n"); stream.printf(" <nodes>%n"); - ArrayList<Node> nodes = new ArrayList<Node>(block.getInstructions()); + Set<Node> nodes = new HashSet<Node>(block.getInstructions()); if (nodes.size() > 0) { // if this is the first block: add all locals to this block - if (nodes.get(0) == graph.start()) { + if (block.getInstructions() == graph.start()) { for (Node node : graph.getNodes()) { if (node instanceof Local) { nodes.add(node); @@ -239,7 +239,9 @@ if (merge.stateAfter() != null) { nodes.add(merge.stateAfter()); } - for (Node usage : merge.usages()) { + } + if (node instanceof PhiPoint) { + for (Node usage : node.usages()) { if (usage instanceof Phi || usage instanceof LoopCounter) { nodes.add(usage); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Fri Jun 17 14:53:07 2011 +0200 @@ -33,7 +33,7 @@ import com.oracle.max.asm.*; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.alloc.*; -import com.oracle.max.graal.compiler.alloc.OperandPool.*; +import com.oracle.max.graal.compiler.alloc.OperandPool.VariableFlag; import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.globalstub.*; import com.oracle.max.graal.compiler.graph.*; @@ -43,11 +43,17 @@ import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.bytecode.Bytecodes.MemoryBarriers; import com.sun.cri.ci.*; import com.sun.cri.ri.*; -import com.sun.cri.ri.RiType.*; +import com.sun.cri.ri.RiType.Representation; +import com.sun.cri.xir.CiXirAssembler.XirConstant; +import com.sun.cri.xir.CiXirAssembler.XirInstruction; +import com.sun.cri.xir.CiXirAssembler.XirOperand; +import com.sun.cri.xir.CiXirAssembler.XirParameter; +import com.sun.cri.xir.CiXirAssembler.XirRegister; +import com.sun.cri.xir.CiXirAssembler.XirTemp; import com.sun.cri.xir.*; -import com.sun.cri.xir.CiXirAssembler.*; /** * This class traverses the HIR instructions and generates LIR instructions from them. @@ -254,6 +260,13 @@ } } } + if (block.blockSuccessors().size() == 1 && !(block.lastInstruction() instanceof LoopEnd)) { + Node firstInstruction = block.blockSuccessors().get(0).firstInstruction(); + //System.out.println("suxSz == 1, fst=" + firstInstruction); + if (firstInstruction instanceof LoopBegin) { + moveToPhi((LoopBegin) firstInstruction, block.lastInstruction()); + } + } if (block.blockSuccessors().size() >= 1 && !block.endsWithJump()) { block.lir().jump(getLIRBlock((FixedNode) block.lastInstruction().successors().get(0))); } @@ -269,7 +282,9 @@ @Override public void visitMerge(Merge x) { - // Nothing to do. + if (x.next() instanceof LoopBegin) { + moveToPhi((LoopBegin) x.next(), x); + } } @Override @@ -1020,7 +1035,7 @@ lastState = fs; } else if (block.blockPredecessors().size() == 1) { FrameState fs = block.blockPredecessors().get(0).lastState(); - assert fs != null; + assert fs != null; //TODO gd maybe this assert should be removed if (GraalOptions.TraceLIRGeneratorLevel >= 2) { TTY.println("STATE CHANGE (singlePred)"); if (GraalOptions.TraceLIRGeneratorLevel >= 3) { @@ -1371,7 +1386,7 @@ } } - void moveToPhi(PhiResolver resolver, Value curVal, Value suxVal, List<Phi> phis, int predIndex) { + /*void moveToPhi(PhiResolver resolver, Value curVal, Value suxVal, List<Phi> phis, int predIndex) { // move current value to referenced phi function if (suxVal instanceof Phi) { Phi phi = (Phi) suxVal; @@ -1397,30 +1412,12 @@ resolver.move(operand, operandForPhi(phi)); } } - } - - private List<Phi> getPhis(LIRBlock block) { - if (block.getInstructions().size() > 0) { - Node i = block.firstInstruction(); - if (i instanceof Merge) { - List<Phi> result = new ArrayList<Phi>(); - for (Node n : i.usages()) { - if (n instanceof Phi) { - result.add((Phi) n); - } - } - return result; - } - } - return null; - } + }*/ @Override public void visitEndNode(EndNode end) { setNoResult(end); - Merge merge = end.merge(); - assert merge != null; - moveToPhi(merge, merge.endIndex(end)); + moveToPhi(end.merge(), end); lir.jump(getLIRBlock(end.merge())); } @@ -1436,49 +1433,45 @@ @Override public void visitLoopEnd(LoopEnd x) { setNoResult(x); - moveToPhi(x.loopBegin(), x.loopBegin().endCount()); + moveToPhi(x.loopBegin(), x); lir.jump(getLIRBlock(x.loopBegin())); } - private void moveToPhi(Merge merge, int nextSuccIndex) { + private void moveToPhi(PhiPoint merge, Node pred) { + int nextSuccIndex = merge.phiPointPredecessorIndex(pred); PhiResolver resolver = new PhiResolver(this); - for (Node n : merge.usages()) { - if (n instanceof Phi) { - Phi phi = (Phi) n; - if (!phi.isDead()) { - Value curVal = phi.valueAt(nextSuccIndex); - if (curVal != null && curVal != phi) { - if (curVal instanceof Phi) { - operandForPhi((Phi) curVal); - } - CiValue operand = curVal.operand(); - if (operand.isIllegal()) { - assert curVal instanceof Constant || curVal instanceof Local : "these can be produced lazily" + curVal + "/" + phi; - operand = operandForInstruction(curVal); - } - resolver.move(operand, operandForPhi(phi)); + for (Phi phi : merge.phis()) { + if (!phi.isDead()) { + Value curVal = phi.valueAt(nextSuccIndex); + if (curVal != null && curVal != phi) { + if (curVal instanceof Phi) { + operandForPhi((Phi) curVal); } + CiValue operand = curVal.operand(); + if (operand.isIllegal()) { + assert curVal instanceof Constant || curVal instanceof Local : "these can be produced lazily" + curVal + "/" + phi; + operand = operandForInstruction(curVal); + } + resolver.move(operand, operandForPhi(phi)); } } } resolver.dispose(); - //TODO (gd) remove that later + //TODO (gd) remove that later ? if (merge instanceof LoopBegin) { - for (Node usage : merge.usages()) { - if (usage instanceof LoopCounter) { - LoopCounter counter = (LoopCounter) usage; - if (counter.operand().isIllegal()) { - createResultVariable(counter); - } - if (nextSuccIndex == 0) { // (gd) nasty - lir.move(operandForInstruction(counter.init()), counter.operand()); + LoopBegin loopBegin = (LoopBegin) merge; + for (LoopCounter counter : loopBegin.counters()) { + if (counter.operand().isIllegal()) { + createResultVariable(counter); + } + if (nextSuccIndex == 0) { + lir.move(operandForInstruction(counter.init()), counter.operand()); + } else { + if (counter.kind == CiKind.Int) { + this.arithmeticOpInt(IADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride()), CiValue.IllegalValue); } else { - if (counter.kind == CiKind.Int) { - this.arithmeticOpInt(IADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride()), CiValue.IllegalValue); - } else { - assert counter.kind == CiKind.Long; - this.arithmeticOpLong(LADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride())); - } + assert counter.kind == CiKind.Long; + this.arithmeticOpLong(LADD, counter.operand(), counter.operand(), operandForInstruction(counter.stride())); } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/BlockMap.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/BlockMap.java Fri Jun 17 14:53:07 2011 +0200 @@ -29,6 +29,7 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.value.*; import com.sun.cri.bytecode.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Fri Jun 17 14:53:07 2011 +0200 @@ -70,40 +70,36 @@ public void build() { new GraphBuilderPhase(compilation, compilation.method, false, false).apply(compilation.graph); - //printGraph("After GraphBuilding", compilation.graph); - if (GraalOptions.TestGraphDuplication) { new DuplicationPhase().apply(compilation.graph); - //printGraph("After Duplication", compilation.graph); } new DeadCodeEliminationPhase().apply(compilation.graph); - //printGraph("After DeadCodeElimination", compilation.graph); if (GraalOptions.Inline) { new InliningPhase(compilation, this, GraalOptions.TraceInlining).apply(compilation.graph); - //printGraph("After Ininling", compilation.graph); - } - - if (GraalOptions.Time) { - GraalTimers.COMPUTE_LINEAR_SCAN_ORDER.start(); } Graph graph = compilation.graph; if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase().apply(graph); - new DeadCodeEliminationPhase().apply(compilation.graph); - //printGraph("After Canonicalization", graph); + new DeadCodeEliminationPhase().apply(graph); } - new LoopPhase().apply(graph); + new LoopEdgeSplitingPhase().apply(graph); + if (GraalOptions.OptLoops) { + new LoopPhase().apply(graph); + } new LoweringPhase().apply(graph); IdentifyBlocksPhase schedule = new IdentifyBlocksPhase(true); schedule.apply(graph); + if (GraalOptions.Time) { + GraalTimers.COMPUTE_LINEAR_SCAN_ORDER.start(); + } List<Block> blocks = schedule.getBlocks(); List<LIRBlock> lirBlocks = new ArrayList<LIRBlock>();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Fri Jun 17 14:53:07 2011 +0200 @@ -22,16 +22,20 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; -public class LoopBegin extends Merge { +public class LoopBegin extends StateSplit implements PhiPoint{ private static final int INPUT_COUNT = 0; private static final int SUCCESSOR_COUNT = 0; public LoopBegin(Graph graph) { - super(INPUT_COUNT, SUCCESSOR_COUNT, graph); + super(CiKind.Illegal, INPUT_COUNT, SUCCESSOR_COUNT, graph); } public LoopEnd loopEnd() { @@ -67,4 +71,44 @@ LoopBegin x = new LoopBegin(into); return x; } + + @Override + public int phiPointPredecessorCount() { + return 2; + } + + @Override + public int phiPointPredecessorIndex(Node pred) { + Node singlePredecessor = this.singlePredecessor(); + if (pred == singlePredecessor) { + return 0; + } else if (pred == this.loopEnd()) { + return 1; + } else if (singlePredecessor instanceof Placeholder) { + singlePredecessor = singlePredecessor.singlePredecessor(); + if (pred == singlePredecessor) { + return 0; + } + } + throw Util.shouldNotReachHere("unknown pred : " + pred + "(sp=" + singlePredecessor + ", le=" + this.loopEnd() + ")"); + } + + @Override + public Node asNode() { + return this; + } + + @Override + public Collection<Phi> phis() { + return Util.filter(this.usages(), Phi.class); + } + + public Collection<LoopCounter> counters() { + return Util.filter(this.usages(), LoopCounter.class); + } + + @Override + public List<Node> phiPointPredecessors() { + return Arrays.asList(new Node[]{this.singlePredecessor(), this.loopEnd()}); + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Fri Jun 17 14:53:07 2011 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; @@ -33,7 +35,7 @@ * about the basic block, including the successor and * predecessor blocks, exception handlers, liveness information, etc. */ -public class Merge extends StateSplit { +public class Merge extends StateSplit implements PhiPoint{ private static final int INPUT_COUNT = 0; @@ -294,4 +296,30 @@ } } } + + @Override + public int phiPointPredecessorCount() { + return endCount(); + } + + @Override + public int phiPointPredecessorIndex(Node pred) { + EndNode end = (EndNode) pred; + return endIndex(end); + } + + @Override + public Node asNode() { + return this; + } + + @Override + public Collection<Phi> phis() { + return Util.filter(this.usages(), Phi.class); + } + + @Override + public List<Node> phiPointPredecessors() { + return Collections.unmodifiableList(inputs().variablePart()); + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Fri Jun 17 14:53:07 2011 +0200 @@ -54,17 +54,22 @@ /** * The merge node for this phi. */ - public Merge merge() { - return (Merge) inputs().get(super.inputCount() + INPUT_MERGE); + public PhiPoint merge() { + return (PhiPoint) inputs().get(super.inputCount() + INPUT_MERGE); } - public void setMerge(Value n) { + public void setMerge(Node n) { + assert n instanceof PhiPoint; inputs().set(super.inputCount() + INPUT_MERGE, n); } - public Phi(CiKind kind, Merge merge, Graph graph) { + public Phi(CiKind kind, PhiPoint merge, Graph graph) { super(kind, INPUT_COUNT, SUCCESSOR_COUNT, graph); - setMerge(merge); + setMerge(merge.asNode()); + } + + Phi(CiKind kind, Graph graph) { + super(kind, INPUT_COUNT, SUCCESSOR_COUNT, graph); } /** @@ -139,7 +144,7 @@ @Override public Node copy(Graph into) { - Phi x = new Phi(kind, null, into); + Phi x = new Phi(kind, into); x.isDead = isDead; return x; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/PhiPoint.java Fri Jun 17 14:53:07 2011 +0200 @@ -0,0 +1,38 @@ +/* + * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.compiler.ir; + +import java.util.*; + +import com.oracle.max.graal.graph.*; + +/** + * A marker interface for nodes from which Phi can hang. + */ +public interface PhiPoint { + int phiPointPredecessorCount(); + int phiPointPredecessorIndex(Node pred); + List<Node> phiPointPredecessors(); + Node asNode(); + Collection<Phi> phis(); +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Fri Jun 17 14:53:07 2011 +0200 @@ -45,7 +45,7 @@ // remove chained Merges for (Merge merge : graph.getNodes(Merge.class)) { - if (merge.endCount() == 1 && merge.usages().size() == 0 && !(merge instanceof LoopEnd) && !(merge instanceof LoopBegin)) { + if (merge.endCount() == 1 && merge.usages().size() == 0 && !(merge instanceof LoopEnd)) { merge.endAt(0).replace(merge.next()); merge.delete(); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Fri Jun 17 14:53:07 2011 +0200 @@ -264,28 +264,25 @@ } public void mergeOrClone(Block target, FrameStateAccess newState) { - Instruction first = target.firstInstruction; + StateSplit first = (StateSplit) target.firstInstruction; + if (target.isLoopHeader && isVisited(target)) { - first = ((LoopBegin) first).loopEnd(); + first = ((LoopBegin) target.firstInstruction.next()).loopEnd(); } - assert first instanceof StateSplit; - - int bci = target.startBci; - - FrameState existingState = ((StateSplit) first).stateAfter(); + FrameState existingState = first.stateAfter(); if (existingState == null) { // copy state because it is modified - FrameState duplicate = newState.duplicate(bci); + FrameState duplicate = newState.duplicate(target.startBci); // if the block is a loop header, insert all necessary phis - if (first instanceof LoopBegin && target.isLoopHeader) { - assert first instanceof Merge; - insertLoopPhis((Merge) first, duplicate); - ((Merge) first).setStateAfter(duplicate); - } else { - ((StateSplit) first).setStateAfter(duplicate); + if (target.isLoopHeader && !isVisited(target)) { + LoopBegin loopBegin = (LoopBegin) target.firstInstruction.next(); + assert target.firstInstruction instanceof Placeholder && loopBegin != null; + //System.out.println("insertLoopPhis with " + target.loopHeaderState); + insertLoopPhis(loopBegin, loopBegin.stateAfter()); } + first.setStateAfter(duplicate); } else { if (!GraalOptions.AssumeVerifiedBytecode && !existingState.isCompatibleWith(newState)) { // stacks or locks do not match--bytecodes would not verify @@ -298,14 +295,14 @@ if (first instanceof Placeholder) { Placeholder p = (Placeholder) first; - assert !target.isLoopHeader; if (p.predecessors().size() == 0) { - p.setStateAfter(newState.duplicate(bci)); + p.setStateAfter(newState.duplicate(target.startBci)); return; } else { Merge merge = new Merge(graph); assert p.predecessors().size() == 1 : "predecessors size: " + p.predecessors().size(); - assert p.next() == null; + merge.setNext(p.next()); + p.setNext(null); EndNode end = new EndNode(graph); p.replace(end); merge.addEnd(end); @@ -319,20 +316,20 @@ } } - private void insertLoopPhis(Merge merge, FrameState newState) { + private void insertLoopPhis(LoopBegin loopBegin, FrameState newState) { int stackSize = newState.stackSize(); for (int i = 0; i < stackSize; i++) { // always insert phis for the stack Value x = newState.stackAt(i); if (x != null) { - newState.setupPhiForStack(merge, i).addInput(x); + newState.setupPhiForStack(loopBegin, i).addInput(x); } } int localsSize = newState.localsSize(); for (int i = 0; i < localsSize; i++) { Value x = newState.localAt(i); if (x != null) { - newState.setupPhiForLocal(merge, i).addInput(x); + newState.setupPhiForLocal(loopBegin, i).addInput(x); } } } @@ -1129,7 +1126,10 @@ LoopBegin loopBegin = new LoopBegin(graph); LoopEnd loopEnd = new LoopEnd(graph); loopEnd.setLoopBegin(loopBegin); - block.firstInstruction = loopBegin; + Placeholder p = new Placeholder(graph); + p.setNext(loopBegin); + loopBegin.setStateAfter(stateAfter.duplicate(block.startBci)); + block.firstInstruction = p; } else { block.firstInstruction = new Placeholder(graph); } @@ -1138,8 +1138,8 @@ addToWorkList(block); FixedNode result = null; - if (block.firstInstruction instanceof LoopBegin && isVisited(block)) { - result = ((LoopBegin) block.firstInstruction).loopEnd(); + if (block.isLoopHeader && isVisited(block)) { + result = ((LoopBegin) block.firstInstruction.next()).loopEnd(); } else { result = block.firstInstruction; } @@ -1177,9 +1177,13 @@ if (!isVisited(block)) { markVisited(block); // now parse the block - frameState.initializeFrom(((StateSplit) block.firstInstruction).stateAfter()); - lastInstr = block.firstInstruction; - assert block.firstInstruction.next() == null : "instructions already appended at block " + block.blockID; + if (block.isLoopHeader) { + lastInstr = (LoopBegin) block.firstInstruction.next(); + } else { + lastInstr = block.firstInstruction; + } + frameState.initializeFrom(((StateSplit) lastInstr).stateAfter()); + assert lastInstr.next() == null : "instructions already appended at block " + block.blockID; if (block == returnBlock) { createReturnBlock(block); @@ -1196,8 +1200,9 @@ } for (Block b : blocksVisited) { if (b.isLoopHeader) { - LoopBegin begin = (LoopBegin) b.firstInstruction; - LoopEnd end = begin.loopEnd(); + Instruction loopHeaderInstr = b.firstInstruction; + LoopBegin begin = (LoopBegin) loopHeaderInstr.next(); + LoopEnd loopEnd = begin.loopEnd(); // This can happen with degenerated loops like this one: // for (;;) { @@ -1206,14 +1211,16 @@ // } catch (UnresolvedException iioe) { // } // } - if (end.stateAfter() != null) { - begin.stateAfter().merge(begin, end.stateAfter()); + if (loopEnd.stateAfter() != null) { + //loopHeaderMerge.stateBefore().merge(begin, end.stateBefore()); + //assert loopHeaderMerge.equals(end.stateBefore()); + begin.stateAfter().merge(begin, loopEnd.stateAfter()); } else { - end.delete(); + loopEnd.delete(); Merge merge = new Merge(graph); - for (int i = 0; i < begin.endCount(); ++i) { - merge.addEnd(begin.endAt(i)); - } + EndNode end = new EndNode(graph); + begin.singlePredecessor().successors().replace(begin, end); + merge.addEnd(end); merge.setNext(begin.next()); merge.setStateAfter(begin.stateAfter()); begin.replace(merge); @@ -1223,6 +1230,9 @@ } private void createDeoptBlock(DeoptBlock block) { +// Merge x = new Merge(graph); +// x.setStateBefore(((StateSplit) block.firstInstruction).stateBefore()); +// append(x); append(new Deoptimize(DeoptAction.InvalidateReprofile, graph)); } @@ -1281,6 +1291,7 @@ stream.setBCI(block.startBci); int endBCI = stream.endBCI(); + boolean blockStart = true; int bci = block.startBci; while (bci < endBCI) { @@ -1293,6 +1304,7 @@ } // read the opcode int opcode = stream.currentBC(); + traceState(); traceInstruction(bci, opcode, bci == block.startBci); processBytecode(bci, opcode); @@ -1309,6 +1321,7 @@ stateSplit.setStateAfter(frameState.create(bci)); } } + blockStart = false; } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopEdgeSplitingPhase.java Fri Jun 17 14:53:07 2011 +0200 @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.compiler.phases; + +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.graph.*; + +/** + * Does critical edge spliting on LoopBegin. + */ +public class LoopEdgeSplitingPhase extends Phase { + + @Override + protected void run(Graph graph) { + for (LoopBegin loopBegin : graph.getNodes(LoopBegin.class)) { + Node pred = loopBegin.singlePredecessor(); + if (IdentifyBlocksPhase.trueSuccessorCount(pred) > 1) { + Anchor anchor = new Anchor(graph); + anchor.setNext(loopBegin); + pred.successors().replace(loopBegin, anchor); + } + } + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Fri Jun 17 14:53:07 2011 +0200 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -50,6 +51,7 @@ private void mergeLoopCounters(List<LoopCounter> counters, LoopBegin loopBegin) { Graph graph = loopBegin.graph(); + FrameState stateAfter = loopBegin.stateAfter(); LoopCounter[] acounters = counters.toArray(new LoopCounter[counters.size()]); for (int i = 0; i < acounters.length; i++) { LoopCounter c1 = acounters[i]; @@ -59,16 +61,30 @@ for (int j = i + 1; j < acounters.length; j++) { LoopCounter c2 = acounters[j]; if (c2 != null && c1.stride().valueEqual(c2.stride())) { + boolean c1InCompare = Util.filter(c1.usages(), Compare.class).size() > 0; + boolean c2inCompare = Util.filter(c2.usages(), Compare.class).size() > 0; + if (c2inCompare && !c1InCompare) { + c1 = acounters[j]; + c2 = acounters[i]; + acounters[i] = c2; + acounters[j] = c1; + } + boolean c2InFramestate = stateAfter != null ? stateAfter.inputs().contains(c2) : false; acounters[j] = null; CiKind kind = c1.kind; - IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); - IntegerAdd addStride = new IntegerAdd(kind, sub, c1.stride(), graph); - IntegerAdd add = new IntegerAdd(kind, c1, addStride, graph); - Phi phi = new Phi(kind, loopBegin, graph); // TODO (gd) assumes order on loopBegin preds - phi.addInput(c2.init()); - phi.addInput(add); - c2.replace(phi); - //System.out.println("--> merged Loop Counters"); + if (c2InFramestate) { + IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); + IntegerAdd addStride = new IntegerAdd(kind, sub, c1.stride(), graph); + IntegerAdd add = new IntegerAdd(kind, c1, addStride, graph); + Phi phi = new Phi(kind, loopBegin, graph); // TODO (gd) assumes order on loopBegin preds + phi.addInput(c2.init()); + phi.addInput(add); + c2.replace(phi); + } else { + IntegerSub sub = new IntegerSub(kind, c2.init(), c1.init(), graph); + IntegerAdd add = new IntegerAdd(kind, c1, sub, graph); + c2.replace(add); + } } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Fri Jun 17 14:53:07 2011 +0200 @@ -93,6 +93,20 @@ return trueSuccessorCount(n) > 1 || n instanceof Return || n instanceof Unwind || n instanceof Deoptimize; } + private void print() { + System.out.println("nodeToBlock :"); + System.out.println(nodeToBlock); + System.out.println("Blocks :"); + for (Block b : blocks) { + System.out.println(b + " [S:" + b.getSuccessors() + ", P:" + b.getPredecessors() + ", D:" + b.getDominators()); + System.out.println(" f " + b.firstNode()); + for (Node n : b.getInstructions()) { + System.out.println(" - " + n); + } + System.out.println(" l " + b.lastNode()); + } + } + private void identifyBlocks() { // Identify blocks. @@ -111,17 +125,22 @@ // Either dead code or at a merge node => stop iteration. break; } - assert currentNode.predecessors().size() == 1 : "preds: " + currentNode; - currentNode = currentNode.predecessors().get(0); + if (currentNode instanceof LoopBegin) { + block = null; + } + currentNode = currentNode.singlePredecessor(); } } } } +// System.out.println("identify blocks"); +// print(); + // Connect blocks. for (Block block : blocks) { Node n = block.firstNode(); - if (n instanceof Merge) { + if (n instanceof Merge) { Merge m = (Merge) n; for (int i = 0; i < m.endCount(); ++i) { EndNode end = m.endAt(i); @@ -137,6 +156,8 @@ } } } +// System.out.println("connect"); +// print(); computeDominators(); @@ -145,16 +166,23 @@ // Add successors of loop end nodes. Makes the graph cyclic. for (Block block : blocks) { - Node n = block.firstNode(); - if (n instanceof LoopBegin) { - LoopBegin loopBegin = (LoopBegin) n; - assert loopBegin.loopEnd() != null; - nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block); + Node n = block.lastNode(); + if (n instanceof LoopEnd) { + LoopEnd loopEnd = (LoopEnd) n; + assert loopEnd.loopBegin() != null; + block.addSuccessor(nodeToBlock.get(loopEnd.loopBegin())); } } +// System.out.println("dom + cycles"); +// print(); + assignLatestPossibleBlockToNodes(); +// System.out.println("assign last"); +// print(); sortNodesWithinBlocks(); +// System.out.println("sort"); +// print(); } else { computeJavaBlocks(); } @@ -234,7 +262,7 @@ } if (n instanceof Phi) { - Block block = nodeToBlock.get(((Phi) n).merge()); + Block block = nodeToBlock.get(((Phi) n).merge().asNode()); nodeToBlock.set(n, block); } @@ -242,32 +270,42 @@ Block block = nodeToBlock.get(((LoopCounter) n).loopBegin()); nodeToBlock.set(n, block); } - + if (n.id() == 142) { + System.out.println("computing common dom for " + n); + } Block block = null; for (Node succ : n.successors()) { + if (n.id() == 142) { + System.out.println("com(assignLatestPossibleBlockToNode(succ)) = com(" + assignLatestPossibleBlockToNode(succ) + ")"); + } block = getCommonDominator(block, assignLatestPossibleBlockToNode(succ)); } for (Node usage : n.usages()) { if (usage instanceof Phi) { Phi phi = (Phi) usage; - Merge merge = phi.merge(); - Block mergeBlock = nodeToBlock.get(merge); - assert mergeBlock != null : "no block for merge " + merge.id(); + PhiPoint merge = phi.merge(); + Block mergeBlock = nodeToBlock.get(merge.asNode()); + assert mergeBlock != null : "no block for merge " + merge.asNode().id(); for (int i = 0; i < phi.valueCount(); ++i) { if (phi.valueAt(i) == n) { if (mergeBlock.getPredecessors().size() == 0) { TTY.println(merge.toString()); TTY.println(phi.toString()); - TTY.println(merge.predecessors().toString()); + TTY.println(merge.phiPointPredecessors().toString()); TTY.println("value count: " + phi.valueCount()); } + if (n.id() == 142) { + System.out.println("com(phi-merge) = com(" + mergeBlock.getPredecessors().get(i) + ")"); + } block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); } } } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { - Merge merge = ((FrameState) usage).block(); - for (int i = 0; i < merge.endCount(); ++i) { - EndNode pred = merge.endAt(i); + PhiPoint merge = ((FrameState) usage).block(); + for (Node pred : merge.phiPointPredecessors()) { + if (n.id() == 142) { + System.out.println("com(FS pred) = com(" + nodeToBlock.get(pred) + ")"); + } block = getCommonDominator(block, nodeToBlock.get(pred)); } } else if (usage instanceof LoopCounter) { @@ -275,9 +313,15 @@ if (n == counter.init() || n == counter.stride()) { LoopBegin loopBegin = counter.loopBegin(); Block mergeBlock = nodeToBlock.get(loopBegin); + if (n.id() == 142) { + System.out.println("com(LC dom) = com(" + mergeBlock.dominator() + ")"); + } block = getCommonDominator(block, mergeBlock.dominator()); } } else { + if (n.id() == 142) { + System.out.println("com(usage) = com(" + assignLatestPossibleBlockToNode(usage) + ")"); + } block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); } } @@ -322,10 +366,24 @@ addToSorting(b, b.lastNode(), sortedInstructions, map); // Make sure that last node gets really last (i.e. when a frame state successor hangs off it). - sortedInstructions.remove(b.lastNode()); - sortedInstructions.add(b.lastNode()); - - assert sortedInstructions.get(sortedInstructions.size() - 1) == b.lastNode() : " lastNode=" + b.lastNode() + ", firstNode=" + b.firstNode() + ", sorted(sz-1)=" + sortedInstructions.get(sortedInstructions.size() - 1); + Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1); + if (lastSorted != b.lastNode()) { + int idx = sortedInstructions.indexOf(b.lastNode()); + boolean canNotMove = false; + for (int i = idx + 1; i < sortedInstructions.size(); i++) { + if (sortedInstructions.get(i).inputs().contains(b.lastNode())) { + canNotMove = true; + break; + } + } + if (canNotMove) { + assert !(b.lastNode() instanceof ControlSplit); + //b.setLastNode(lastSorted); + } else { + sortedInstructions.remove(b.lastNode()); + sortedInstructions.add(b.lastNode()); + } + } b.setInstructions(sortedInstructions); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java Fri Jun 17 14:53:07 2011 +0200 @@ -485,7 +485,7 @@ @Override public void visitLoopBegin(LoopBegin x) { - visitMerge(x); + } @Override
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/Util.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/Util.java Fri Jun 17 14:53:07 2011 +0200 @@ -27,6 +27,7 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -424,4 +425,15 @@ public static String valueString(Value value) { return (value == null) ? "-" : ("" + value.kind.typeChar + value.id()); } + + @SuppressWarnings("unchecked") + public static <T extends Node> Collection<T> filter(Collection<Node> nodes, Class<T> clazz) { + ArrayList<T> phis = new ArrayList<T>(); + for (Node node : nodes) { + if (clazz.isInstance(node)) { + phis.add((T) node); + } + } + return phis; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Fri Jun 17 14:53:07 2011 +0200 @@ -187,6 +187,28 @@ return true; } + public boolean equals(FrameStateAccess other) { + if (stackSize() != other.stackSize() || localsSize() != other.localsSize() || locksSize() != other.locksSize()) { + return false; + } + for (int i = 0; i < stackSize(); i++) { + Value x = stackAt(i); + Value y = other.stackAt(i); + if (x != y) { + return false; + } + } + for (int i = 0; i < locksSize(); i++) { + if (lockAt(i) != other.lockAt(i)) { + return false; + } + } + if (other.outerFrameState() != outerFrameState()) { + return false; + } + return true; + } + /** * Gets the size of the local variables. */ @@ -282,7 +304,7 @@ * @param block the block begin for which we are creating the phi * @param i the index into the stack for which to create a phi */ - public Phi setupPhiForStack(Merge block, int i) { + public Phi setupPhiForStack(PhiPoint block, int i) { Value p = stackAt(i); if (p != null) { if (p instanceof Phi) { @@ -303,7 +325,7 @@ * @param block the block begin for which we are creating the phi * @param i the index of the local variable for which to create the phi */ - public Phi setupPhiForLocal(Merge block, int i) { + public Phi setupPhiForLocal(PhiPoint block, int i) { Value p = localAt(i); if (p instanceof Phi) { Phi phi = (Phi) p; @@ -351,7 +373,7 @@ } } - public void merge(Merge block, FrameStateAccess other) { + public void merge(PhiPoint block, FrameStateAccess other) { checkSize(other); for (int i = 0; i < valuesSize(); i++) { Value x = valueAt(i); @@ -378,7 +400,7 @@ } if (phi.valueCount() == 0) { - int size = block.endCount(); + int size = block.phiPointPredecessorCount(); for (int j = 0; j < size; ++j) { phi.addInput(x); } @@ -387,20 +409,16 @@ phi.addInput((x == y) ? phi : y); } - if (block instanceof LoopBegin) { -// assert phi.valueCount() == ((LoopBegin) block).loopEnd().predecessors().size() + 1 : "loop, valueCount=" + phi.valueCount() + " predSize= " + ((LoopBegin) block).loopEnd().predecessors().size(); - } else { - assert phi.valueCount() == block.endCount() + 1 : "valueCount=" + phi.valueCount() + " predSize= " + block.endCount(); - } + assert phi.valueCount() == block.phiPointPredecessorCount() + (block instanceof LoopBegin ? 0 : 1) : "valueCount=" + phi.valueCount() + " predSize= " + block.phiPointPredecessorCount(); } } } } - public Merge block() { + public PhiPoint block() { for (Node n : usages()) { - if (n instanceof Merge) { - return (Merge) n; + if (n instanceof PhiPoint) { + return (PhiPoint) n; } } return null;
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Node.java Fri Jun 17 14:53:07 2011 +0200 @@ -53,6 +53,11 @@ public List<Node> predecessors() { return Collections.unmodifiableList(predecessors); } + + public Node singlePredecessor(){ + assert predecessors.size() == 1; + return predecessors.get(0); + } public List<Node> usages() { return Collections.unmodifiableList(usages);
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeMap.java Thu Jun 16 20:09:26 2011 +0200 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeMap.java Fri Jun 17 14:53:07 2011 +0200 @@ -53,4 +53,13 @@ assert node.graph == graph : "this node is not part of the graph"; assert node.id() < values.length : "this node was added to the graph after creating the node map"; } + + @Override + public String toString() { + StringBuilder sb = new StringBuilder(); + for (int i = 0; i < values.length; i++) { + sb.append("[").append(i).append(" -> ").append(values[i]).append("]").append('\n'); + } + return sb.toString(); + } }
--- a/rundacapo.sh Thu Jun 16 20:09:26 2011 +0200 +++ b/rundacapo.sh Fri Jun 17 14:53:07 2011 +0200 @@ -15,4 +15,4 @@ echo "DACAPO is not defined. It must point to a Dacapo benchmark directory." exit 1; fi -${JDK7}/bin/java -client -d64 -graal -XX:-GraalBailoutIsFatal -XX:+PrintCompilation -Xms1g -Xmx2g -esa -classpath ${DACAPO}/dacapo-9.12-bach.jar Harness --preserve $* +${JDK7}/bin/java -client -d64 -graal -G:PrintIdealGraphLevel=4 -G:PrintFilter=scanContent -XX:CompileCommand=compileonly,*.scanContent -XX:CompileCommand=exclude,com.oracle* -XX:-GraalBailoutIsFatal -XX:+PrintCompilation -Xms1g -Xmx2g -esa -classpath ${DACAPO}/dacapo-9.12-bach.jar Harness --preserve $*