Mercurial > hg > truffle
changeset 2980:a0b1b22e58cd
Merge
| author | Gilles Duboscq <gilles.duboscq@oracle.com> |
|---|---|
| date | Tue, 14 Jun 2011 10:32:29 +0200 |
| parents | 9dfbd92bb4b8 (current diff) 4db4e8cb6bd6 (diff) |
| children | 42681ed31c4d |
| files | graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ClipNode.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedNullCheck.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Schedule.java |
| diffstat | 34 files changed, 1043 insertions(+), 788 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Tue Jun 14 10:32:29 2011 +0200 @@ -55,6 +55,7 @@ public static boolean ZapStackOnMethodEntry = ____; public static boolean StressLinearScan = ____; public static boolean BailoutOnException = ____; + public static boolean DeoptALot = ____; /** * See {@link Filter#Filter(String, Object)}.
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Tue Jun 14 10:32:29 2011 +0200 @@ -112,9 +112,9 @@ public void print(Graph graph, String title, boolean shortNames) { stream.printf(" <graph name='%s'>%n", escape(title)); noBlockNodes.clear(); - Schedule schedule = null; + IdentifyBlocksPhase schedule = null; try { - schedule = new Schedule(); + schedule = new IdentifyBlocksPhase(true); schedule.apply(graph); } catch (Throwable t) { // nothing to do here...
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Tue Jun 14 10:32:29 2011 +0200 @@ -275,7 +275,7 @@ } private static boolean jumpsToNextBlock(Node node) { - return node instanceof BlockEnd; + return node instanceof BlockEnd || node instanceof Anchor; } @Override @@ -296,12 +296,22 @@ if (Modifier.isSynchronized(compilation.method.accessFlags())) { bci = Instruction.SYNCHRONIZATION_ENTRY_BCI; } + + boolean withReceiver = !Modifier.isStatic(compilation.method.accessFlags()); + CiKind[] arguments = Util.signatureToKinds(compilation.method.signature(), withReceiver ? CiKind.Object : null); + int[] argumentSlots = new int[arguments.length]; + int slot = 0; + for (int arg = 0; arg < arguments.length; arg++) { + argumentSlots[arg] = slot; + slot += arguments[arg].sizeInSlots(); + } + FrameState fs = new FrameState(compilation.method, bci, compilation.method.maxLocals(), 0, 0, compilation.graph); for (Node node : compilation.graph.start().usages()) { if (node instanceof Local) { Local local = (Local) node; int i = local.index(); - fs.storeLocal(i, local); + fs.storeLocal(argumentSlots[i], local); CiValue src = args.locations[i]; assert src.isLegal() : "check"; @@ -313,9 +323,21 @@ setResult(local, dest); } } + assert checkOperands(fs); return fs; } + private boolean checkOperands(FrameState fs) { + boolean withReceiver = !Modifier.isStatic(compilation.method.accessFlags()); + CiKind[] arguments = Util.signatureToKinds(compilation.method.signature(), withReceiver ? CiKind.Object : null); + int slot = 0; + for (CiKind kind : arguments) { + assert fs.localAt(slot) != null : "slot: " + slot; + slot += kind.sizeInSlots(); + } + return true; + } + @Override public void visitCheckCast(CheckCast x) { XirArgument obj = toXirArgument(x.object()); @@ -400,6 +422,9 @@ DeoptimizationStub stub = new DeoptimizationStub(DeoptAction.InvalidateReprofile, state); deoptimizationStubs.add(stub); + + emitCompare(x.node()); + //emitBranch(x.node(), stub.label) throw new RuntimeException(); //lir.branch(x.condition.negate(), stub.label, stub.info); } @@ -435,7 +460,7 @@ // describing the state at the safepoint. moveToPhi(); - lir.jump(getLIRBlock(x.defaultSuccessor())); + lir.jump(getLIRBlock(x.next())); } @Override @@ -684,10 +709,14 @@ } @Override - public void visitNullCheck(FixedNullCheck x) { - CiValue value = load(x.object()); - LIRDebugInfo info = stateFor(x); - lir.nullCheck(value, info); + public void visitFixedGuard(FixedGuard fixedGuard) { + Node comp = fixedGuard.node(); + if (comp instanceof IsNonNull) { + IsNonNull x = (IsNonNull) comp; + CiValue value = load(x.object()); + LIRDebugInfo info = stateFor(x); + lir.nullCheck(value, info); + } } @Override
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Tue Jun 14 10:32:29 2011 +0200 @@ -87,13 +87,15 @@ if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase().apply(graph); + new DeadCodeEliminationPhase().apply(compilation.graph); printGraph("After Canonicalization", graph); - new DeadCodeEliminationPhase().apply(compilation.graph); } + new LoweringPhase().apply(graph); + new SplitCriticalEdgesPhase().apply(graph); - Schedule schedule = new Schedule(); + IdentifyBlocksPhase schedule = new IdentifyBlocksPhase(true); schedule.apply(graph);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AccessField.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AccessField.java Tue Jun 14 10:32:29 2011 +0200 @@ -74,6 +74,8 @@ super(kind, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph); this.field = field; setObject(object); + assert field.isResolved(); + assert field.holder().isResolved(); } /** @@ -93,18 +95,10 @@ } /** - * Checks whether the class of the field of this access is loaded. - * @return {@code true} if the class is loaded - */ - public boolean isLoaded() { - return field.isResolved(); - } - - /** * Checks whether this field is declared volatile. * @return {@code true} if the field is resolved and declared volatile */ public boolean isVolatile() { - return isLoaded() && Modifier.isVolatile(field.accessFlags()); + return Modifier.isVolatile(field.accessFlags()); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Anchor.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Anchor.java Tue Jun 14 10:32:29 2011 +0200 @@ -29,7 +29,7 @@ /** * The {@code Anchor} instruction represents the end of a block with an unconditional jump to another block. */ -public final class Anchor extends BlockEnd { +public final class Anchor extends Instruction { private static final int INPUT_COUNT = 0; private static final int SUCCESSOR_COUNT = 0; @@ -39,7 +39,7 @@ * @param graph */ public Anchor(Graph graph) { - super(CiKind.Illegal, 1, INPUT_COUNT, SUCCESSOR_COUNT, graph); + super(CiKind.Illegal, INPUT_COUNT, SUCCESSOR_COUNT, graph); } @Override @@ -49,12 +49,11 @@ @Override public void print(LogStream out) { - out.print("anchor ").print(defaultSuccessor()); + out.print("anchor ").print(next()); } @Override public Node copy(Graph into) { - Anchor x = new Anchor(into); - return x; + return new Anchor(into); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ArrayLength.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ArrayLength.java Tue Jun 14 10:32:29 2011 +0200 @@ -126,9 +126,7 @@ return length; } CiConstant constantValue = null; - if (array instanceof LoadField) { - constantValue = ((LoadField) array).constantValue(); - } else if (array.isConstant()) { + if (array.isConstant()) { constantValue = array.asConstant(); } if (constantValue != null && constantValue.isNonNull()) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ClipNode.java Tue Jun 14 10:03:09 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,65 +0,0 @@ -/* - * 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 com.oracle.max.graal.compiler.debug.*; -import com.oracle.max.graal.graph.*; -import com.sun.cri.ci.*; - - -public final class ClipNode extends Instruction { - private static final int INPUT_COUNT = 1; - private static final int INPUT_NODE = 0; - - private static final int SUCCESSOR_COUNT = 0; - - /** - * The instruction that produces the object tested against null. - */ - public FloatingNode node() { - return (FloatingNode) inputs().get(super.inputCount() + INPUT_NODE); - } - - public FloatingNode setNode(FloatingNode n) { - return (FloatingNode) inputs().set(super.inputCount() + INPUT_NODE, n); - } - - public ClipNode(Graph graph) { - super(CiKind.Illegal, INPUT_COUNT, SUCCESSOR_COUNT, graph); - } - - @Override - public void accept(ValueVisitor v) { - // Do nothing. - } - - @Override - public void print(LogStream out) { - out.print("clip node ").print(node()); - } - - @Override - public Node copy(Graph into) { - return new ClipNode(into); - } -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedGuard.java Tue Jun 14 10:32:29 2011 +0200 @@ -0,0 +1,65 @@ +/* + * 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 com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + + +public final class FixedGuard extends Instruction { + private static final int INPUT_COUNT = 1; + private static final int INPUT_NODE = 0; + + private static final int SUCCESSOR_COUNT = 0; + + /** + * The instruction that produces the object tested against null. + */ + public FloatingNode node() { + return (FloatingNode) inputs().get(super.inputCount() + INPUT_NODE); + } + + public FloatingNode setNode(FloatingNode n) { + return (FloatingNode) inputs().set(super.inputCount() + INPUT_NODE, n); + } + + public FixedGuard(Graph graph) { + super(CiKind.Illegal, INPUT_COUNT, SUCCESSOR_COUNT, graph); + } + + @Override + public void accept(ValueVisitor v) { + v.visitFixedGuard(this); + } + + @Override + public void print(LogStream out) { + out.print("clip node ").print(node()); + } + + @Override + public Node copy(Graph into) { + return new FixedGuard(into); + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedNullCheck.java Tue Jun 14 10:03:09 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,115 +0,0 @@ -/* - * 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.ir; - -import com.oracle.max.graal.compiler.debug.*; -import com.oracle.max.graal.compiler.util.*; -import com.oracle.max.graal.graph.*; -import com.sun.cri.bytecode.*; -import com.sun.cri.ci.*; -import com.sun.cri.ri.*; - -/** - * The {@code NullCheck} class represents an explicit null check instruction. - */ -public final class FixedNullCheck extends Instruction { - - private static final int INPUT_COUNT = 1; - private static final int INPUT_OBJECT = 0; - - private static final int SUCCESSOR_COUNT = 0; - - @Override - protected int inputCount() { - return super.inputCount() + INPUT_COUNT; - } - - @Override - protected int successorCount() { - return super.successorCount() + SUCCESSOR_COUNT; - } - - /** - * The instruction that produces the object tested against null. - */ - public Value object() { - return (Value) inputs().get(super.inputCount() + INPUT_OBJECT); - } - - public Value setObject(Value n) { - return (Value) inputs().set(super.inputCount() + INPUT_OBJECT, n); - } - - /** - * Constructs a new NullCheck instruction. - * @param object the instruction producing the object to check against null - * @param stateBefore the state before executing the null check - * @param graph - */ - public FixedNullCheck(Value object, Graph graph) { - super(CiKind.Object, INPUT_COUNT, SUCCESSOR_COUNT, graph); - assert object == null || object.kind == CiKind.Object; - setObject(object); - } - - @Override - public void accept(ValueVisitor v) { - v.visitNullCheck(this); - } - - @Override - public int valueNumber() { - return Util.hash1(Bytecodes.IFNONNULL, object()); - } - - @Override - public boolean valueEqual(Node i) { - if (i instanceof FixedNullCheck) { - FixedNullCheck o = (FixedNullCheck) i; - return object() == o.object(); - } - return false; - } - - @Override - public RiType declaredType() { - // null check does not alter the type of the object - return object().declaredType(); - } - - @Override - public RiType exactType() { - // null check does not alter the type of the object - return object().exactType(); - } - - @Override - public void print(LogStream out) { - out.print("null_check(").print(object()).print(')'); - } - - @Override - public Node copy(Graph into) { - return new FixedNullCheck(null, into); - } -}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/GuardNode.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/GuardNode.java Tue Jun 14 10:32:29 2011 +0200 @@ -36,12 +36,12 @@ /** * The instruction that produces the object tested against null. */ - public FloatingNode node() { - return (FloatingNode) inputs().get(super.inputCount() + INPUT_NODE); + public Compare node() { + return (Compare) inputs().get(super.inputCount() + INPUT_NODE); } - public FloatingNode setNode(FloatingNode n) { - return (FloatingNode) inputs().set(super.inputCount() + INPUT_NODE, n); + public Compare setNode(Compare n) { + return (Compare) inputs().set(super.inputCount() + INPUT_NODE, n); } public GuardNode(Graph graph) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IsNonNull.java Tue Jun 14 10:32:29 2011 +0200 @@ -0,0 +1,115 @@ +/* + * 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.ir; + +import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.util.*; +import com.oracle.max.graal.graph.*; +import com.sun.cri.bytecode.*; +import com.sun.cri.ci.*; +import com.sun.cri.ri.*; + +/** + * The {@code NullCheck} class represents an explicit null check instruction. + */ +public final class IsNonNull extends FloatingNode { + + private static final int INPUT_COUNT = 1; + private static final int INPUT_OBJECT = 0; + + private static final int SUCCESSOR_COUNT = 0; + + @Override + protected int inputCount() { + return super.inputCount() + INPUT_COUNT; + } + + @Override + protected int successorCount() { + return super.successorCount() + SUCCESSOR_COUNT; + } + + /** + * The instruction that produces the object tested against null. + */ + public Value object() { + return (Value) inputs().get(super.inputCount() + INPUT_OBJECT); + } + + public Value setObject(Value n) { + return (Value) inputs().set(super.inputCount() + INPUT_OBJECT, n); + } + + /** + * Constructs a new NullCheck instruction. + * @param object the instruction producing the object to check against null + * @param stateBefore the state before executing the null check + * @param graph + */ + public IsNonNull(Value object, Graph graph) { + super(CiKind.Object, INPUT_COUNT, SUCCESSOR_COUNT, graph); + assert object == null || object.kind == CiKind.Object; + setObject(object); + } + + @Override + public void accept(ValueVisitor v) { + // Nothing to do. + } + + @Override + public int valueNumber() { + return Util.hash1(Bytecodes.IFNONNULL, object()); + } + + @Override + public boolean valueEqual(Node i) { + if (i instanceof IsNonNull) { + IsNonNull o = (IsNonNull) i; + return object() == o.object(); + } + return false; + } + + @Override + public RiType declaredType() { + // null check does not alter the type of the object + return object().declaredType(); + } + + @Override + public RiType exactType() { + // null check does not alter the type of the object + return object().exactType(); + } + + @Override + public void print(LogStream out) { + out.print("null_check(").print(object()).print(')'); + } + + @Override + public Node copy(Graph into) { + return new IsNonNull(null, into); + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoadField.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoadField.java Tue Jun 14 10:32:29 2011 +0200 @@ -25,6 +25,8 @@ import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.compiler.graph.*; import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.CanonicalizerOp; +import com.oracle.max.graal.compiler.phases.LoweringPhase.LoweringOp; +import com.oracle.max.graal.compiler.phases.LoweringPhase.LoweringTool; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -68,8 +70,8 @@ */ @Override public RiType exactType() { - RiType declaredType = declaredType(); - return declaredType.isResolved() ? declaredType.exactType() : null; + RiType declared = declaredType(); + return declared != null && declared.isResolved() ? declared.exactType() : null; } @Override @@ -97,7 +99,7 @@ * * @return {@code null} if this load cannot be reduced to a constant */ - public CiConstant constantValue() { + private CiConstant constantValue() { if (isStatic()) { return field.constantValue(null); } else if (object().isConstant()) { @@ -108,8 +110,7 @@ @Override public Node copy(Graph into) { - LoadField x = new LoadField(null, field, into); - return x; + return new LoadField(null, field, into); } @SuppressWarnings("unchecked") @@ -121,6 +122,16 @@ return super.lookup(clazz); } + private static class LoadFieldLoweringOp implements LoweringOp { + + @Override + public Node lower(Node n, LoweringTool tool) { + LoadField field = (LoadField) n; + return null;//field.field().createLoad(tool); + } + + } + private static class LoadFieldCanonicalizerOp implements CanonicalizerOp { @Override public Node canonical(Node node) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Local.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Local.java Tue Jun 14 10:32:29 2011 +0200 @@ -22,8 +22,11 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.bytecode.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -34,15 +37,38 @@ public final class Local extends FloatingNode { private static final int INPUT_COUNT = 1; + private static final int INPUT_START = 0; private static final int SUCCESSOR_COUNT = 0; + @Override + protected int inputCount() { + return super.inputCount() + INPUT_COUNT; + } + + @Override + protected int successorCount() { + return super.successorCount() + SUCCESSOR_COUNT; + } + + /** + * The start node of the graph that this local belongs to. This is used for correctly scheduling the locals. + */ + private StartNode start() { + return (StartNode) inputs().get(super.inputCount() + INPUT_START); + } + + private void setStart(StartNode n) { + inputs().set(super.inputCount() + INPUT_START, n); + } + private final int index; private RiType declaredType; - public Local(CiKind kind, int javaIndex, Graph graph) { + public Local(CiKind kind, int javaIndex, StartNode start, Graph graph) { super(kind, INPUT_COUNT, SUCCESSOR_COUNT, graph); this.index = javaIndex; + setStart(start); } /** @@ -81,18 +107,15 @@ } @Override - protected int inputCount() { - return super.inputCount() + INPUT_COUNT; - } - - @Override - protected int successorCount() { - return super.successorCount() + SUCCESSOR_COUNT; + public Map<Object, Object> getDebugProperties() { + Map<Object, Object> properties = super.getDebugProperties(); + properties.put("index", index()); + return properties; } @Override public Node copy(Graph into) { - Local x = new Local(kind, index, into); + Local x = new Local(kind, index, start(), into); x.setDeclaredType(declaredType()); return x; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Tue Jun 14 10:32:29 2011 +0200 @@ -30,7 +30,7 @@ * The {@code Phi} instruction represents the merging of dataflow * in the instruction graph. It refers to a join block and a variable. */ -public final class Phi extends FixedNode { +public final class Phi extends FloatingNode { private static final int DEFAULT_MAX_VALUES = 2;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ValueVisitor.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ValueVisitor.java Tue Jun 14 10:32:29 2011 +0200 @@ -58,7 +58,7 @@ public abstract void visitNewMultiArray(NewMultiArray i); public abstract void visitNewObjectArray(NewObjectArray i); public abstract void visitNewTypeArray(NewTypeArray i); - public abstract void visitNullCheck(FixedNullCheck i); + public abstract void visitFixedGuard(FixedGuard fixedGuard); public abstract void visitPhi(Phi i); public abstract void visitRegisterFinalizer(RegisterFinalizer i); public abstract void visitReturn(Return i);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Tue Jun 14 10:32:29 2011 +0200 @@ -38,6 +38,27 @@ this.graph = graph; this.flood = graph.createNodeFlood(); + // remove chained Merges +// for (Merge merge : graph.getNodes(Merge.class)) { +// if (merge.predecessors().size() == 1 && merge.usages().size() == 0) { +// if (merge.successors().get(0) instanceof Merge) { +// Node pred = merge.predecessors().get(0); +// int predIndex = merge.predecessorsIndex().get(0); +// pred.successors().setAndClear(predIndex, merge, 0); +// merge.delete(); +// } +// } +// } +// Node startSuccessor = graph.start().successors().get(0); +// if (startSuccessor instanceof Merge) { +// Merge startMerge = (Merge) startSuccessor; +// if (startMerge.predecessors().size() == 1 && startMerge.usages().size() == 0) { +// int predIndex = startMerge.predecessorsIndex().get(0); +// graph.start().successors().setAndClear(predIndex, startMerge, 0); +// startMerge.delete(); +// } +// } + flood.add(graph.start()); iterateSuccessors(); @@ -96,6 +117,9 @@ private void iterateInputs() { for (Node node : graph.getNodes()) { + if (node instanceof Local) { + flood.add(node); + } if (node != Node.Null && flood.isMarked(node)) { for (Node input : node.inputs()) { if (!isCFG(input)) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 14 10:32:29 2011 +0200 @@ -694,7 +694,9 @@ private void genThrow(int bci) { Value exception = frameState.apop(); - append(new FixedNullCheck(exception, graph)); + FixedGuard node = new FixedGuard(graph); + node.setNode(new IsNonNull(exception, graph)); + append(node); Instruction entry = handleException(exception, bci); if (entry != null) { @@ -920,10 +922,15 @@ private void appendInvoke(int opcode, RiMethod target, Value[] args, int cpi, RiConstantPool constantPool) { CiKind resultType = returnKind(target); - Invoke invoke = new Invoke(bci(), opcode, resultType.stackKind(), args, target, target.signature().returnType(method.holder()), method.typeProfile(bci()), graph); - Value result = appendWithBCI(invoke); - invoke.setExceptionEdge(handleException(null, bci())); - frameState.pushReturn(resultType, result); + if (GraalOptions.DeoptALot) { + append(new Deoptimize(DeoptAction.None, graph)); + frameState.pushReturn(resultType, Constant.defaultForKind(resultType, graph)); + } else { + Invoke invoke = new Invoke(bci(), opcode, resultType.stackKind(), args, target, target.signature().returnType(method.holder()), method.typeProfile(bci()), graph); + Value result = appendWithBCI(invoke); + invoke.setExceptionEdge(handleException(null, bci())); + frameState.pushReturn(resultType, result); + } } private RiType getExactType(RiType staticType, Value receiver) { @@ -1277,7 +1284,7 @@ traceInstruction(bci, opcode, blockStart); processBytecode(bci, opcode); - if (Schedule.isBlockEnd(lastInstr) || lastInstr.next() != null) { + if (IdentifyBlocksPhase.isBlockEnd(lastInstr) || lastInstr.next() != null) { break; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Tue Jun 14 10:32:29 2011 +0200 @@ -239,7 +239,9 @@ assert invoke.predecessors().size() == 1 : "size: " + invoke.predecessors().size(); Instruction pred; if (withReceiver) { - pred = new FixedNullCheck(parameters[0], compilation.graph); + FixedGuard clipNode = new FixedGuard(compilation.graph); + clipNode.setNode(new IsNonNull(parameters[0], compilation.graph)); + pred = clipNode; } else { pred = new Merge(compilation.graph); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoweringPhase.java Tue Jun 14 10:32:29 2011 +0200 @@ -0,0 +1,75 @@ +/* + * 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.phases; + +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.graph.*; + +public class LoweringPhase extends Phase { + @Override + protected void run(final Graph graph) { + final IdentifyBlocksPhase s = new IdentifyBlocksPhase(false); + s.apply(graph); + + for (Block b : s.getBlocks()) { + final Node firstNode = b.firstNode(); + + final LoweringTool loweringTool = new LoweringTool() { + @Override + public Node createStructuredBlockAnchor() { + if (!(firstNode instanceof Anchor) && !(firstNode instanceof Merge)) { + Anchor a = new Anchor(graph); + assert firstNode.predecessors().size() == 1; + Node pred = firstNode.predecessors().get(0); + int predIndex = firstNode.predecessorsIndex().get(0); + a.successors().setAndClear(Instruction.SUCCESSOR_NEXT, pred, predIndex); + pred.successors().set(predIndex, a); + return a; + } + return firstNode; + } + }; + + for (final Node n : b.getInstructions()) { + if (n instanceof FixedNode) { + LoweringOp op = n.lookup(LoweringOp.class); + if (op != null) { + Node newNode = op.lower(n, loweringTool); + if (newNode != null) { + n.replace(newNode); + } + } + } + } + } + } + + public interface LoweringTool { + Node createStructuredBlockAnchor(); + } + + public interface LoweringOp extends Op { + Node lower(Node n, LoweringTool tool); + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/SplitCriticalEdgesPhase.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/SplitCriticalEdgesPhase.java Tue Jun 14 10:32:29 2011 +0200 @@ -36,12 +36,12 @@ List<Node> nodes = graph.getNodes(); for (int i = 0; i < nodes.size(); ++i) { Node n = nodes.get(i); - if (Schedule.trueSuccessorCount(n) > 1) { + if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) { for (int j = 0; j < n.successors().size(); ++j) { Node succ = n.successors().get(j); - if (Schedule.truePredecessorCount(succ) > 1) { + if (IdentifyBlocksPhase.truePredecessorCount(succ) > 1) { Anchor a = new Anchor(graph); - a.successors().setAndClear(1, n, j); + a.successors().setAndClear(Instruction.SUCCESSOR_NEXT, n, j); n.successors().set(j, a); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Tue Jun 14 10:32:29 2011 +0200 @@ -35,6 +35,7 @@ private final List<Block> predecessors = new ArrayList<Block>(); private List<Node> instructions = new ArrayList<Node>(); private Block dominator; + private Block javaBlock; private final List<Block> dominators = new ArrayList<Block>(); private Node firstNode; @@ -48,6 +49,14 @@ this.firstNode = node; } + public Block javaBlock() { + return javaBlock; + } + + public void setJavaBlock(Block javaBlock) { + this.javaBlock = javaBlock; + } + public Node lastNode() { return lastNode; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Tue Jun 14 10:32:29 2011 +0200 @@ -0,0 +1,478 @@ +/* + * Copyright (c) 2011, 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.schedule; + +import java.util.*; + +import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.phases.*; +import com.oracle.max.graal.compiler.value.*; +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + + +public class IdentifyBlocksPhase extends Phase { + private final List<Block> blocks = new ArrayList<Block>(); + private NodeMap<Block> nodeToBlock; + private Graph graph; + private boolean scheduleAllNodes; + + public IdentifyBlocksPhase(boolean scheduleAllNodes) { + super(scheduleAllNodes ? "FullSchedule" : "PartSchedule"); + this.scheduleAllNodes = scheduleAllNodes; + } + + + @Override + protected void run(Graph graph) { + this.graph = graph; + nodeToBlock = graph.createNodeMap(); + identifyBlocks(); + } + + public List<Block> getBlocks() { + return Collections.unmodifiableList(blocks); + } + + public NodeMap<Block> getNodeToBlock() { + return nodeToBlock; + } + + private Block createBlock() { + Block b = new Block(blocks.size()); + blocks.add(b); + return b; + } + + private Block assignBlock(Node n) { + Block curBlock = nodeToBlock.get(n); + if (curBlock == null) { + curBlock = createBlock(); + return assignBlock(n, curBlock); + } + return curBlock; + } + + + private Block assignBlock(Node n, Block b) { + assert nodeToBlock.get(n) == null; + nodeToBlock.set(n, b); + if (b.firstNode() == null) { + b.setFirstNode(n); + b.setLastNode(n); + } else { + if (b.lastNode() != null) { + b.getInstructions().add(b.lastNode()); + } + b.setLastNode(n); + } + b.setLastNode(n); + return b; + } + + public static boolean isFixed(Node n) { + return n != null && ((n instanceof FixedNode) || n == n.graph().start()); + } + + public static boolean isBlockEnd(Node n) { + return trueSuccessorCount(n) > 1 || n instanceof Anchor || n instanceof Return || n instanceof Unwind; + } + + private void identifyBlocks() { + // Identify blocks. + final ArrayList<Node> blockBeginNodes = new ArrayList<Node>(); + NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, new NodeVisitor() { + @Override + public boolean visit(Node n) { + if (!isFixed(n)) { + return false; + } + + if (n instanceof LoopBegin) { + // a LoopBegin is always a merge + assignBlock(n); + blockBeginNodes.add(n); + return true; + } + + Node singlePred = null; + for (Node pred : n.predecessors()) { + if (isFixed(pred)) { + if (singlePred == null) { + singlePred = pred; + } else { + // We have more than one predecessor => we are a merge block. + assignBlock(n); + blockBeginNodes.add(n); + return true; + } + } + } + + if (singlePred == null) { + // We have no predecessor => we are the start block. + assignBlock(n); + blockBeginNodes.add(n); + } else { + // We have a single predecessor => check its successor count. + if (isBlockEnd(singlePred)) { + assignBlock(n); + blockBeginNodes.add(n); + } else { + assignBlock(n, nodeToBlock.get(singlePred)); + } + } + return true; + }} + ); + + // Connect blocks. + for (Node n : blockBeginNodes) { + Block block = nodeToBlock.get(n); + for (Node pred : n.predecessors()) { + if (isFixed(pred)) { + Block predBlock = nodeToBlock.get(pred); + predBlock.addSuccessor(block); + } + } + + if (n instanceof Merge) { + for (Node usage : n.usages()) { + if (usage instanceof Phi) { + nodeToBlock.set(usage, block); + } + } + } + } + + for (Node n : graph.getNodes()) { + if (n instanceof FrameState) { + FrameState f = (FrameState) n; + if (f.predecessors().size() == 1) { + Block predBlock = nodeToBlock.get(f.predecessors().get(0)); + assert predBlock != null; + nodeToBlock.set(f, predBlock); + predBlock.getInstructions().add(f); + } else { + assert f.predecessors().size() == 0; + } + } + } + + computeDominators(); + + + if (scheduleAllNodes) { + + // Add successors of loop end nodes. Makes the graph cyclic. + for (Node n : blockBeginNodes) { + Block block = nodeToBlock.get(n); + if (n instanceof LoopBegin) { + LoopBegin loopBegin = (LoopBegin) n; + nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block); + } + } + + assignLatestPossibleBlockToNodes(); + sortNodesWithinBlocks(); + } else { + computeJavaBlocks(); + } + } + + private void computeJavaBlocks() { + + for (Block b : blocks) { + computeJavaBlock(b); + } + } + + private Block computeJavaBlock(Block b) { + if (b.javaBlock() == null) { + if (b.getPredecessors().size() == 0) { + b.setJavaBlock(b); + } else if (b.getPredecessors().size() == 1) { + Block pred = b.getPredecessors().get(0); + if (pred.getSuccessors().size() > 1) { + b.setJavaBlock(b); + } else { + b.setJavaBlock(computeJavaBlock(pred)); + } + } else { + Block dominatorBlock = b.getPredecessors().get(0); + for (int i=1; i<b.getPredecessors().size(); ++i) { + dominatorBlock = getCommonDominator(dominatorBlock, b.getPredecessors().get(i)); + } + CiBitMap blockMap = new CiBitMap(blocks.size()); + markPredecessors(b, dominatorBlock, blockMap); + + Block result = dominatorBlock; + L1: for (Block curBlock : blocks) { + if (curBlock != b && blockMap.get(curBlock.blockID())) { + for (Block succ : curBlock.getSuccessors()) { + if (!blockMap.get(succ.blockID())) { + result = b; + break L1; + } + } + } + } + b.setJavaBlock(result); + } + } + return b.javaBlock(); + } + + private void markPredecessors(Block b, Block stopBlock, CiBitMap blockMap) { + if (blockMap.get(b.blockID())) { + return; + } + blockMap.set(b.blockID()); + if (b != stopBlock) { + for (Block pred : b.getPredecessors()) { + markPredecessors(pred, stopBlock, blockMap); + } + } + } + + private void assignLatestPossibleBlockToNodes() { + for (Node n : graph.getNodes()) { + assignLatestPossibleBlockToNode(n); + } + } + + private Block assignLatestPossibleBlockToNode(Node n) { + if (n == null) { + return null; + } + + Block prevBlock = nodeToBlock.get(n); + if (prevBlock != null) { + return prevBlock; + } + + Block block = null; + for (Node succ : n.successors()) { + 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(); + 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("value count: " + phi.valueCount()); + } + block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); + } + } + } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { + Merge merge = ((FrameState) usage).block(); + for (Node pred : merge.predecessors()) { + if (isFixed(pred)) { + block = getCommonDominator(block, nodeToBlock.get(pred)); + } + } + } else { + block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); + } + } + + nodeToBlock.set(n, block); + if (block != null) { + block.getInstructions().add(n); + } + return block; + } + + private Block getCommonDominator(Block a, Block b) { + if (a == null) { + return b; + } + if (b == null) { + return a; + } + return commonDominator(a, b); + } + + private void sortNodesWithinBlocks() { + NodeBitMap map = graph.createNodeBitMap(); + for (Block b : blocks) { + sortNodesWithinBlocks(b, map); + } + } + + private void sortNodesWithinBlocks(Block b, NodeBitMap map) { + List<Node> instructions = b.getInstructions(); + List<Node> sortedInstructions = new ArrayList<Node>(); + assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b; + + boolean scheduleFirst = true; + + if (b.firstNode() == b.lastNode()) { + Node node = b.firstNode(); + if (!(node instanceof Merge)) { + scheduleFirst = false; + } + } + if (scheduleFirst) { + addToSorting(b, b.firstNode(), sortedInstructions, map); + } + for (Node i : instructions) { + addToSorting(b, i, sortedInstructions, map); + } + addToSorting(b, b.lastNode(), sortedInstructions, map); + b.setInstructions(sortedInstructions); + } + + private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) { + if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local) { + return; + } + + for (Node input : i.inputs()) { + addToSorting(b, input, sortedInstructions, map); + } + + for (Node pred : i.predecessors()) { + addToSorting(b, pred, sortedInstructions, map); + } + + map.mark(i); + + for (Node succ : i.successors()) { + if (succ instanceof FrameState) { + addToSorting(b, succ, sortedInstructions, map); + } + } + + // Now predecessors and inputs are scheduled => we can add this node. + if (!(i instanceof FrameState)) { + sortedInstructions.add(i); + } + } + + private void computeDominators() { + Block dominatorRoot = nodeToBlock.get(graph.start()); + assert dominatorRoot.getPredecessors().size() == 0; + CiBitMap visited = new CiBitMap(blocks.size()); + visited.set(dominatorRoot.blockID()); + LinkedList<Block> workList = new LinkedList<Block>(); + workList.add(dominatorRoot); + + while (!workList.isEmpty()) { + Block b = workList.remove(); + + List<Block> predecessors = b.getPredecessors(); + if (predecessors.size() == 1) { + b.setDominator(predecessors.get(0)); + } else if (predecessors.size() > 0) { + boolean delay = false; + for (Block pred : predecessors) { + if (pred != dominatorRoot && pred.dominator() == null) { + delay = true; + break; + } + } + + if (delay) { + workList.add(b); + continue; + } + + Block dominator = null; + for (Block pred : predecessors) { + if (dominator == null) { + dominator = pred; + } else { + dominator = commonDominator(dominator, pred); + } + } + b.setDominator(dominator); + } + + for (Block succ : b.getSuccessors()) { + if (!visited.get(succ.blockID())) { + visited.set(succ.blockID()); + workList.add(succ); + } + } + } + } + + public Block commonDominator(Block a, Block b) { + CiBitMap bitMap = new CiBitMap(blocks.size()); + Block cur = a; + while (cur != null) { + bitMap.set(cur.blockID()); + cur = cur.dominator(); + } + + cur = b; + while (cur != null) { + if (bitMap.get(cur.blockID())) { + return cur; + } + cur = cur.dominator(); + } + + throw new IllegalStateException("no common dominator between " + a + " and " + b); + } + + public static int trueSuccessorCount(Node n) { + if (n == null) { + return 0; + } + int i = 0; + for (Node s : n.successors()) { + if (isFixed(s)) { + i++; + } + } + return i; + } + + public static int truePredecessorCount(Node n) { + if (n == null) { + return 0; + } + int i = 0; + for (Node s : n.predecessors()) { + if (isFixed(s)) { + i++; + } + } + + if (n instanceof LoopBegin) { + i++; + } + return i; + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Schedule.java Tue Jun 14 10:03:09 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,467 +0,0 @@ -/* - * Copyright (c) 2011, 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.schedule; - -import java.util.*; - -import com.oracle.max.graal.compiler.debug.*; -import com.oracle.max.graal.compiler.ir.*; -import com.oracle.max.graal.compiler.phases.*; -import com.oracle.max.graal.compiler.value.*; -import com.oracle.max.graal.graph.*; -import com.sun.cri.ci.*; - - -public class Schedule extends Phase { - private final List<Block> blocks = new ArrayList<Block>(); - private NodeMap<Block> nodeToBlock; - private Graph graph; - - - @Override - protected void run(Graph graph) { - this.graph = graph; - nodeToBlock = graph.createNodeMap(); - identifyBlocks(); - } - - public List<Block> getBlocks() { - return Collections.unmodifiableList(blocks); - } - - public NodeMap<Block> getNodeToBlock() { - return nodeToBlock; - } - - private Block createBlock() { - Block b = new Block(blocks.size()); - blocks.add(b); - return b; - } - - private Block assignBlock(Node n) { - Block curBlock = nodeToBlock.get(n); - if (curBlock == null) { - curBlock = createBlock(); - return assignBlock(n, curBlock); - } - return curBlock; - } - - - private Block assignBlock(Node n, Block b) { - assert nodeToBlock.get(n) == null; - nodeToBlock.set(n, b); - if (b.firstNode() == null) { - b.setFirstNode(n); - b.setLastNode(n); - } else { - if (b.lastNode() != null) { - b.getInstructions().add(b.lastNode()); - } - b.setLastNode(n); - } - b.setLastNode(n); - return b; - } - - public static boolean isFixed(Node n) { - return n != null && ((n instanceof FixedNode) || n == n.graph().start()); - } - - public static boolean isBlockEnd(Node n) { - return trueSuccessorCount(n) > 1 || n instanceof Anchor || n instanceof Return || n instanceof Unwind; - } - - private void identifyBlocks() { - // Identify blocks. - final ArrayList<Node> blockBeginNodes = new ArrayList<Node>(); - NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, new NodeVisitor() { - @Override - public boolean visit(Node n) { - if (!isFixed(n)) { - return false; - } - - if (n instanceof LoopBegin) { - // a LoopBegin is always a merge - assignBlock(n); - blockBeginNodes.add(n); - return true; - } - - Node singlePred = null; - for (Node pred : n.predecessors()) { - if (isFixed(pred)) { - if (singlePred == null) { - singlePred = pred; - } else { - // We have more than one predecessor => we are a merge block. - assignBlock(n); - blockBeginNodes.add(n); - return true; - } - } - } - - if (singlePred == null) { - // We have no predecessor => we are the start block. - assignBlock(n); - blockBeginNodes.add(n); - } else { - // We have a single predecessor => check its successor count. - if (isBlockEnd(singlePred)) { - assignBlock(n); - blockBeginNodes.add(n); - } else { - assignBlock(n, nodeToBlock.get(singlePred)); - } - } - return true; - }} - ); - - // Connect blocks. - for (Node n : blockBeginNodes) { - Block block = nodeToBlock.get(n); - for (Node pred : n.predecessors()) { - if (isFixed(pred)) { - Block predBlock = nodeToBlock.get(pred); - predBlock.addSuccessor(block); - } - } - - if (n instanceof Merge) { - for (Node usage : n.usages()) { - if (usage instanceof Phi) { - nodeToBlock.set(usage, block); - } - } - } - } - - for (Node n : graph.getNodes()) { - if (n instanceof FrameState) { - FrameState f = (FrameState) n; - if (f.predecessors().size() == 1) { - Block predBlock = nodeToBlock.get(f.predecessors().get(0)); - assert predBlock != null; - nodeToBlock.set(f, predBlock); - predBlock.getInstructions().add(f); - } else { - assert f.predecessors().size() == 0; - } - } - } - - computeDominators(); - - - - // Add successors of loop end nodes. Makes the graph cyclic. - for (Node n : blockBeginNodes) { - Block block = nodeToBlock.get(n); - if (n instanceof LoopBegin) { - LoopBegin loopBegin = (LoopBegin) n; - nodeToBlock.get(loopBegin.loopEnd()).addSuccessor(block); - } - } - - assignLatestPossibleBlockToNodes(); - sortNodesWithinBlocks(); - - //print(); - } - - private void assignLatestPossibleBlockToNodes() { - for (Node n : graph.getNodes()) { - assignLatestPossibleBlockToNode(n); - } - } - - private Block assignLatestPossibleBlockToNode(Node n) { - if (n == null) { - return null; - } - - Block prevBlock = nodeToBlock.get(n); - if (prevBlock != null) { - return prevBlock; - } - - Block block = null; - for (Node succ : n.successors()) { - 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(); - 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("value count: " + phi.valueCount()); - } - block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); - } - } - } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { - Merge merge = ((FrameState) usage).block(); - for (Node pred : merge.predecessors()) { - if (isFixed(pred)) { - block = getCommonDominator(block, nodeToBlock.get(pred)); - } - } - } else { - block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); - } - } - - nodeToBlock.set(n, block); - if (block != null) { - block.getInstructions().add(n); - } - return block; - } - - private Block getCommonDominator(Block a, Block b) { - if (a == null) { - return b; - } - if (b == null) { - return a; - } - return commonDominator(a, b); - } - - private void sortNodesWithinBlocks() { - NodeBitMap map = graph.createNodeBitMap(); - for (Block b : blocks) { - sortNodesWithinBlocks(b, map); - } - } - - private void sortNodesWithinBlocks(Block b, NodeBitMap map) { - List<Node> instructions = b.getInstructions(); - List<Node> sortedInstructions = new ArrayList<Node>(); - assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b; - - boolean scheduleFirst = true; - - if (b.firstNode() == b.lastNode()) { - Node node = b.firstNode(); - if (!(node instanceof Merge)) { - scheduleFirst = false; - } - } - if (scheduleFirst) { - addToSorting(b, b.firstNode(), sortedInstructions, map); - } - for (Node i : instructions) { - addToSorting(b, i, sortedInstructions, map); - } - addToSorting(b, b.lastNode(), sortedInstructions, map); - //assert b.firstNode() == sortedInstructions.get(0) : b.firstNode(); - // assert b.lastNode() == sortedInstructions.get(sortedInstructions.size() - 1); - b.setInstructions(sortedInstructions); -// TTY.println("Block " + b); -// for (Node n : sortedInstructions) { -// TTY.println("Node: " + n); -// } - } - - private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) { - if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof Phi || i instanceof Local) { - return; - } - - for (Node input : i.inputs()) { - addToSorting(b, input, sortedInstructions, map); - } - - for (Node pred : i.predecessors()) { - addToSorting(b, pred, sortedInstructions, map); - } - - map.mark(i); - - for (Node succ : i.successors()) { - if (succ instanceof FrameState) { - addToSorting(b, succ, sortedInstructions, map); - } - } - - // Now predecessors and inputs are scheduled => we can add this node. - if (!(i instanceof FrameState)) { - sortedInstructions.add(i); - } - } - - private void computeDominators() { - Block dominatorRoot = nodeToBlock.get(graph.start()); - assert dominatorRoot.getPredecessors().size() == 0; - CiBitMap visited = new CiBitMap(blocks.size()); - visited.set(dominatorRoot.blockID()); - LinkedList<Block> workList = new LinkedList<Block>(); - workList.add(dominatorRoot); - - while (!workList.isEmpty()) { - Block b = workList.remove(); - - List<Block> predecessors = b.getPredecessors(); - if (predecessors.size() == 1) { - b.setDominator(predecessors.get(0)); - } else if (predecessors.size() > 0) { - boolean delay = false; - for (Block pred : predecessors) { - if (pred != dominatorRoot && pred.dominator() == null) { - delay = true; - break; - } - } - - if (delay) { - workList.add(b); - continue; - } - - Block dominator = null; - for (Block pred : predecessors) { - if (dominator == null) { - dominator = pred; - } else { - dominator = commonDominator(dominator, pred); - } - } - b.setDominator(dominator); - } - - for (Block succ : b.getSuccessors()) { - if (!visited.get(succ.blockID())) { - visited.set(succ.blockID()); - workList.add(succ); - } - } - } - } - - public Block commonDominator(Block a, Block b) { - CiBitMap bitMap = new CiBitMap(blocks.size()); - Block cur = a; - while (cur != null) { - bitMap.set(cur.blockID()); - cur = cur.dominator(); - } - - cur = b; - while (cur != null) { - if (bitMap.get(cur.blockID())) { - return cur; - } - cur = cur.dominator(); - } - - print(); - assert false : "no common dominator between " + a + " and " + b; - return null; - } - - private void print() { - TTY.println("============================================"); - TTY.println("%d blocks", blocks.size()); - - for (Block b : blocks) { - TTY.println(); - TTY.print(b.toString()); - - TTY.print(" succs="); - for (Block succ : b.getSuccessors()) { - TTY.print(succ + ";"); - } - - TTY.print(" preds="); - for (Block pred : b.getPredecessors()) { - TTY.print(pred + ";"); - } - - if (b.dominator() != null) { - TTY.print(" dom=" + b.dominator()); - } - TTY.println(); - - if (b.getInstructions().size() > 0) { - TTY.print("first instr: " + b.getInstructions().get(0)); - TTY.print("last instr: " + b.getInstructions().get(b.getInstructions().size() - 1)); - } - } - -/* - TTY.println("============================================"); - TTY.println("%d nodes", nodeToBlock.size()); - for (Node n : graph.getNodes()) { - if (n != null) { - TTY.print("Node %d: %s", n.id(), n.getClass().toString()); - Block curBlock = nodeToBlock.get(n); - if (curBlock != null) { - TTY.print(" %s", curBlock); - } - TTY.println(); - } - }*/ - } - - public static int trueSuccessorCount(Node n) { - if (n == null) { - return 0; - } - int i = 0; - for (Node s : n.successors()) { - if (isFixed(s)) { - i++; - } - } - return i; - } - - public static int truePredecessorCount(Node n) { - if (n == null) { - return 0; - } - int i = 0; - for (Node s : n.predecessors()) { - if (isFixed(s)) { - i++; - } - } - - if (n instanceof LoopBegin) { - i++; - } - return i; - } -}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameStateBuilder.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameStateBuilder.java Tue Jun 14 10:32:29 2011 +0200 @@ -58,8 +58,7 @@ int index = 0; if (!isStatic(method.accessFlags())) { // add the receiver and assume it is non null - Local local = new Local(method.holder().kind(), javaIndex, graph); - local.inputs().set(0, graph.start()); + Local local = new Local(method.holder().kind(), javaIndex, graph.start(), graph); local.setDeclaredType(method.holder()); storeLocal(javaIndex, local); javaIndex = 1; @@ -71,8 +70,7 @@ for (int i = 0; i < max; i++) { RiType type = sig.argumentTypeAt(i, accessingClass); CiKind kind = type.kind().stackKind(); - Local local = new Local(kind, index, graph); - local.inputs().set(0, graph.start()); + Local local = new Local(kind, index, graph.start(), graph); if (type.isResolved()) { local.setDeclaredType(type); }
--- a/graal/com.oracle.max.graal.doc.initial/graal_compiler.tex Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.doc.initial/graal_compiler.tex Tue Jun 14 10:32:29 2011 +0200 @@ -74,8 +74,11 @@ \section{Goals} The compiler effort aims at rewriting the high-level intermediate representation of C1X with two main goals: \begin{description} -\item[Modularity:] A modular design of the compiler should simplify the implementation of new languages, new back-ends, and new optimizations. -\item[Peak Performance:] A more powerful intermediate representation should enable the implementation of aggressive optimizations that impact the peak performance of the resulting machine code. +\item[Modularity:] +A modular design of the compiler should simplify the implementation of new languages, new back-ends, and new optimizations. +\item[Peak Performance:] +A more powerful intermediate representation should enable the implementation of aggressive optimizations that impact the peak performance of the resulting machine code. +In terms of startup performance, we want to orientate ourselves to the HotSpot server compiler configuration. \end{description} \section{Design} @@ -103,6 +106,7 @@ This is achieved by having a graph as the starting point of the compilation and not a Java bytecode array. Building the graph from the Java bytecodes must happen before giving a method to the compiler. This enables front-ends for different languages (e.g., Ruby or JavaScript) to provide their own graph. +The support for different languages is constrained by the following two conditions: We only support structured control flow, and the dynamic type system of the language must be expressible using the RiType class. Also, there is no dependency on a specific back-end, but the output of the compiler is a graph that can then be converted to a different representation in a final compiler phase. \end{description} @@ -168,7 +172,8 @@ \end{itemize} \item Only inputs and successors can be changed, and changes to them will update the usages and predecessors. \item Every node must be able to support cloning and serialization. - \item The edges of a node also define \textit{happens-before} and \textit{happens-after} relationships as shown in Figure~\ref{fig:directions}. + \item The edges of a node also define \textit{emitted-before} and \textit{emitted-after} relationships as shown in Figure~\ref{fig:directions}. + They mean that the machine code for one node is emitted before or after the machine code of another node. \end{itemize} \begin{figure}[ht] @@ -184,8 +189,8 @@ \data{usages}{node1} \control{predecessors}{node1} \node{node2}{Node} -\textnode{before}{happens-before} -\textnode{after}{happens-after} +\textnode{before}{emitted-before} +\textnode{after}{emitted-after} \data{node2}{before} \control{node2}{after} \data{after}{node2} @@ -208,18 +213,18 @@ \section{Control Flow} -Control flow is managed in way where the predecessor node contains direct pointers to its successor nodes. -We reserve the term \textit{instruction} for nodes that are embedded in the control flow. +Control flow is managed in a way where the predecessor node contains direct pointers to its successor nodes. This is opposite to the approach taken in the server compiler, where control flow and data flow edges point in the same direction. The advantage that we see in our approach is that there is no need for projection nodes in case of control flow splits. -An \texttt{If} instruction can directly point to its true and false successors without any intermediate nodes. +An \texttt{If} node can directly point to its true and false successors without any intermediate nodes. This makes the graph more compact and simplifies graph traversal. +We distinguish between \textit{fixed nodes} that are directly embedded in the control flow and \textit{floating nodes} whose position in the control flow may vary. -Listing~\ref{lst:cfg2} shows an example Java program with an if statement where both paths do not contain any instruction with side effects. +Listing~\ref{lst:cfg2} shows an example Java program with an if statement where both paths do not contain any node with side effects. Figure~\ref{fig:loopexits} shows the corresponding compiler graph. -The \texttt{If} instruction can directly point its true and false successors to a \texttt{Merge} instruction. -A \texttt{Phi} node that selects the appropriate value is appended to the \texttt{Merge} instruction. -The \texttt{Return} instruction then has a data dependency on the \texttt{Phi} node. +The \texttt{If} node can directly point its true and false successors to a \texttt{Merge} node. +A \texttt{Phi} node that selects the appropriate value is appended to the \texttt{Merge} node. +The \texttt{Return} node then has a data dependency on the \texttt{Phi} node. \begin{lstlisting}[label=lst:cfg2, caption=Control flow in the graph., captionpos=b] if (condition) { return 0; } @@ -259,10 +264,10 @@ Additionally, this greatly reduces the number of exception handler edges in the compiled code. The main advantage of this technique is however, that we are free in moving around bounds checks, memory allocation, memory accesses with implicit null checks, etc. -There are only two kinds of instruction that need explicit exception edges, because they are the only instructions that can throw exceptions in compiled code: \texttt{Throw} instructions and \texttt{Invoke} instructions. -They are modelled as instructions with an additional control flow continuation that points to an \texttt{ExceptionDispatch} instruction. -The exception dispatch instruction decides based on the type of the exception object whether the control should flow to the catch handler or to another exception dispatch. -If there is no catch handler in the currently compiled method, then the control flows into the \texttt{Unwind} instruction that handles the exception by forwarding it to the caller. +There are only two kinds of nodes that need explicit exception edges, because they are the only nodes that can throw exceptions in compiled code: \texttt{Throw} nodes and \texttt{Invoke} nodes. +They are modelled as nodes with an additional control flow continuation that points to an \texttt{ExceptionDispatch} node. +The exception dispatch node decides based on the type of the exception object whether the control should flow to the catch handler or to another exception dispatch. +If there is no catch handler in the currently compiled method, then the control flows into the \texttt{Unwind} node that handles the exception by forwarding it to the caller. Listing~\ref{lst:exc1} shows an example Java program with nested try blocks and Figure \ref{fig:exc1} shows the corresponding compiler graph. \begin{lstlisting}[label=lst:exc1, caption=Exception dispatch in the compiler graph., captionpos=b] @@ -308,8 +313,8 @@ \label{sec:loops} Loops form a first-class construct in the IR that is expressed by specialized IR nodes during all optimization phases. We only compile methods with a control flow where every loop has a single entry point. -This entry point is a \nodename{LoopBegin} instruction. -This instruction is connected to a \nodename{LoopEnd} instruction that merges all control flow paths that do not exit the loop. +This entry point is a \nodename{LoopBegin} node. +This node is connected to a \nodename{LoopEnd} node that merges all control flow paths that do not exit the loop. The edge between the \nodename{LoopBegin} and the \nodename{LoopEnd} is the backedge of the loop. It goes from the beginning to the end in order to make the graph acyclic. An algorithm that traverses the control flow has to explicitely decide whether it wants to incorporate backedges (i.e., special case of the treatment of \nodename{LoopEnd}) or ignore them. @@ -321,14 +326,16 @@ \textnode{BeforeLoop}{Loop entry} \textnode{Exit1}{First loop exit} \textnode{Exit2}{Second loop exit} -\nodesplit{LoopBegin}{LoopBegin} +\node{LoopBegin}{LoopBegin} \node{LoopEnd}{LoopEnd} \nodesplit{If1}{If} \nodesplit{If2}{If} -\controllabel{LoopBegin:succ1}{LoopEnd} -\controllabel{LoopBegin:succ2}{If1} +\data{LoopEnd}{LoopBegin} +\control{LoopBegin}{If1} \controllabel{If1:succ1}{If2} -\controllabel{If2:succ1}{LoopEnd} +\controllabel{If2:succ1}{LoopBody} +\textnode{LoopBody}{Loop body} +\control{LoopBody}{LoopEnd} \controllabel{BeforeLoop}{LoopBegin} \controllabel{If1:succ2}{Exit1} \controllabel{If2:succ2}{Exit2} @@ -339,7 +346,7 @@ \subsection{Loop Phis} Data flow in loops is modeled with special phi nodes at the beginning and the end of the loop. -The \nodename{LoopEnd} instruction merges every value that flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes. +The \nodename{LoopEnd} node merges every value that flows into the next loop iteration in associated \nodename{LoopEndPhi} nodes. A corresponding \nodename{LoopBeginPhi} node that is associated with the loop header has a control flow dependency on the \nodename{LoopEndPhi} node. Listing~\ref{lst:loop} shows a simple counting loop that is used as an example in the rest of this section. Figure~\ref{fig:loop2} shows how the loop is modelled immediately after building the graph. @@ -356,11 +363,11 @@ \textnode{n}{n} \textnode{Constant0}{0} \textnode{Constant1}{1} -\nodesplit{LoopBegin}{LoopBegin} +\node{LoopBegin}{LoopBegin} \node{LoopEnd}{LoopEnd} \nodesplit{If1}{If} -\controllabel{LoopBegin:succ1}{LoopEnd} -\controllabel{LoopBegin:succ2}{If1} +\data{LoopEnd}{LoopBegin} +\control{LoopBegin}{If1} \nodebi{Compare}{<} \nodebi{LoopBeginPhi}{LoopBeginPhi} \nodebi{Add}{+} @@ -375,7 +382,9 @@ \datalabel{Compare:in1}{LoopBeginPhi} \datalabel{Compare:in2}{n} \data{If1}{Compare} -\controllabel{If1:succ1}{LoopEnd} +\controllabel{If1:succ1}{LoopBody} +\textnode{LoopBody}{Loop body} +\control{LoopBody}{LoopEnd} \controllabel{BeforeLoop}{LoopBegin} \controllabel{If1:succ2}{Exit} \end{digraphenv} @@ -397,11 +406,11 @@ \textnode{n}{n} \textnode{Constant0}{0} \textnode{Constant1}{1} -\nodesplit{LoopBegin}{LoopBegin} +\node{LoopBegin}{LoopBegin} \node{LoopEnd}{LoopEnd} \nodesplit{If1}{If} -\controllabel{LoopBegin:succ1}{LoopEnd} -\controllabel{LoopBegin:succ2}{If1} +\data{LoopEnd}{LoopBegin} +\control{LoopBegin}{If1} \nodebi{Compare}{<} \nodetri{LoopCounter}{LoopCounter} \datalabel{LoopCounter:in1}{LoopBegin} @@ -410,7 +419,9 @@ \datalabel{Compare:in1}{LoopCounter} \datalabel{Compare:in2}{n} \data{If1}{Compare} -\controllabel{If1:succ1}{LoopEnd} +\controllabel{If1:succ1}{LoopBody} +\textnode{LoopBody}{Loop body} +\control{LoopBody}{LoopEnd} \controllabel{BeforeLoop}{LoopBegin} \controllabel{If1:succ2}{Exit} \end{digraphenv} @@ -423,8 +434,12 @@ If the total maximum number of iterations of a loop is fixed, then the loop is converted into a bounded loop. The total number of iterations always denotes the number of full iterations of the loop with the control flowing from the loop begin to the loop end. If the total number of iterations is reached, the loop is exited directly from the loop header. +The representation of the bounded loop in the graph should support reasoning about the loop, but does not specify how the loop will later be converted to machine code. In the example, we can infer from the loop exit with the comparison on the loop counter that the total number of iterations of the loop is limited to n. Figure \ref{fig:loop4} shows the compiler graph of the example loop after the bounded loop transformation. +If there are no other exits out of the loop, then the number of iterations specified as the input to the bounded loop node is also the exact number of loop iterations. +Loops with the same number of iterations can be merged into a single loop. +We also want to support loop splitting in order to find simple loops that are candidates for vectorization. \begin{figure}[ht] \centering @@ -434,11 +449,13 @@ \textnode{n}{n} \textnode{Constant0}{0} \textnode{Constant1}{1} -\nodesplittri{LoopBegin}{BoundedLoopBegin} +\nodesplit{LoopBegin}{BoundedLoopBegin} \node{LoopEnd}{LoopEnd} -\controllabel{LoopBegin:succ1}{LoopEnd} -\controllabel{LoopBegin:succ2}{LoopEnd} -\controllabel{LoopBegin:succ3}{Exit} +\data{LoopEnd}{LoopBegin} +\controllabel{LoopBegin:succ1}{LoopBody} +\textnode{LoopBody}{Loop body} +\control{LoopBody}{LoopEnd} +\controllabel{LoopBegin:succ2}{Exit} \nodetri{LoopCounter}{LoopCounter} \datalabel{LoopCounter:in1}{LoopBegin} \datalabeltext{LoopCounter:in2}{Constant0}{init} @@ -453,7 +470,7 @@ \subsection{Vectorization} If we have now a bounded loop with no additional loop exit and no associated phi nodes (only associated loop counters), we can vectorize the loop. -We replace the loop header with a normal instruction that produces a vector of values from 0 to the number of loop iterations minus 1. +We replace the loop header with a normal node that produces a vector of values from 0 to the number of loop iterations minus 1. The loop counters are replaced with \texttt{VectorAdd} and \texttt{VectorMul} nodes. The vectorization is only possible if every node of the loop can be replaced with a corresponding vector node. Figure \ref{fig:loop5} shows the compiler graph of the example loop after vectorization. @@ -492,9 +509,9 @@ Frame states are necessary to support the deoptimization of the program, which is the precondition for performing aggressive optimizations that use optimistic assumptions. Therefore every point in the optimizing compiler that may revert execution back to the interpreter needs a valid frame state. -However, the point where the interpreter continues execution need not correspond exactly to the execution position of the compiled code, because many Java bytecode instructions can be safely reexecuted. -Thus, frame states need only be generated for the states after instructions that cannot be reexecuted, because they modify the state of the program. -Examples for such instructions are: +However, the point where the interpreter continues execution need not correspond exactly to the execution position of the compiled code, because many Java bytecode nodes can be safely reexecuted. +Thus, frame states need only be generated for the states after nodes that cannot be reexecuted, because they modify the state of the program. +Examples for such nodes are: \begin{itemize} \item Array stores (in Java bytecodes {\tt IASTORE, LASTORE, FASTORE, \\DASTORE, AASTORE, BASTORE, CASTORE, SASTORE}) @@ -503,7 +520,7 @@ \item Synchronization (in Java bytecodes {\tt MONITORENTER, MONITOREXIT}) \end{itemize} -Within the graph a frame state is represented as a node that is attached to the instruction that caused it to be generated using a control dependency (see Figure~\ref{fig:fs1}). +Within the graph a frame state is represented as a node that is attached to the node that caused it to be generated using a control dependency (see Figure~\ref{fig:fs1}). Frame states also have data dependencies on the contents of the state: the local variables and the expression stack. The frame state at the method beginning does not have to be explicitely in the graph, because it can always be reconstructed at a later stage. @@ -532,8 +549,8 @@ A deoptimization node needs a valid frame state that specifies the location and state where the interpreter should continue. -The algorithm for constructing frame states makes sure that every possible location in the graph has a well-defined frame state that can be used by a deoptimization instruction. -Therefore, there are no direct links between the deoptimization instruction and its frame state thus allowing the deoptimization instructions to move freely around. +The algorithm for constructing frame states makes sure that every possible location in the graph has a well-defined frame state that can be used by a deoptimization node. +Therefore, there are no direct links between the deoptimization node and its frame state thus allowing the deoptimization nodes to move freely around. \subsection{Partial Escape Analysis} @@ -565,15 +582,15 @@ A guard is a node that deoptimizes based on a conditional expression. Guards are not attached to a certain frame state, they can move around freely and will always use the correct frame state when the nodes are scheduled (i.e., the last emitted frame state). The node that is guarded by the deoptimization has a data dependency on the guard and the guard in turn has a data dependency on the condition. -A guard must not be moved above any \texttt{If} nodes. -Therefore, we use \texttt{Anchor} instructions after a control flow split and a data dependency from the guard to this anchor. -The anchor is the most distant instruction that is postdominated by the guarded instruction and the guard can be scheduled anywhere between those two nodes. -This ensures maximum flexibility for the guard instruction and guarantees that we only deoptimize if the control flow would have reached the guarded instruction (without taking exceptions into account). +A guard may only be executed if it is guaranteed that the guarded node is executed too (if no exceptions are thrown). +Therefore, we use \texttt{Anchor} nodes after a control flow split and a data dependency from the guard to this anchor. +The anchor is the most distant node that is postdominated by the guarded node and the guard can be scheduled anywhere between those two nodes. +This ensures maximum flexibility for the guard node and guarantees that we only deoptimize if the control flow would have reached the guarded node (without taking exceptions into account). To illustrate the strengths of this approach, we show the graph for the Java code snippet shown in \ref{lst:guard1}. The example looks artificial, but in case of method inlining, this is a pattern that is not unlikely to be present in a normal Java program. Figure \ref{fig:guard0} shows the compiler graph for the example method after graph building. -The field stores are both represented by a single instruction and the null check that is implicitely incorporated in the field store. +The field stores are both represented by a single node and the null check that is implicitely incorporated in the field store. \begin{lstlisting}[label=lst:guard1, caption=Example method that demonstrates the strengths of modelling the guards explicitely., captionpos=b] void init(Point p) { @@ -617,9 +634,9 @@ \label{fig:guard0} \end{figure} -Figure~\ref{fig:guard1} shows the example graph at a later compilation phase when the field store instructions are lowered to memory store instructions and explicitely modelled null check guards. -The guards are attached to anchor instructions that delimit their possible schedule. -The first guard must not be moved outside the \texttt{if} block; the second guard may be moved before the \texttt{If} instruction, because at this point it is already guaranteed that the second store is executed. +Figure~\ref{fig:guard1} shows the example graph at a later compilation phase when the field store nodes are lowered to memory store nodes and explicitely modelled null check guards. +The guards are attached to anchor nodes that delimit their possible schedule. +The first guard must not be moved outside the \texttt{if} block; the second guard may be moved before the \texttt{If} node, because at this point it is already guaranteed that the second store is executed. \begin{figure}[ht] \centering @@ -635,8 +652,8 @@ \textnode{const0}{0} \nodeguard{guard1}{Guard} \nodeguard{guard2}{Guard} - \nodetrisplit{store1}{MemStore 16 (int)} - \nodetrisplit{store2}{MemStore 20 (int)} + \nodetrisplit{store1}{MemStore 16 (4 bytes)} + \nodetrisplit{store2}{MemStore 20 (4 bytes)} \nodeframestate{fs1}{FrameState} \nodeframestate{fs2}{FrameState} \data{store1:in1}{p} @@ -666,10 +683,10 @@ \label{fig:guard1} \end{figure} -The first guard can be easily removed, because it is guarded by an \texttt{If} instruction that checks the same condition. +The first guard can be easily removed, because it is guarded by an \texttt{If} node that checks the same condition. Therefore we can remove the guard and the anchor from the graph and this gives us the graph shown in Figure \ref{fig:guard2}. -There is another optimization for guard instructions: If two guards that are anchored to the true and false branch of the same \texttt{If} instruction have the same condition, they can be merged, so that the resulting guard is anchored at the most distant node of which the \texttt{If} instruction is a postdominator. +There is another optimization for guard nodes: If two guards that are anchored to the true and false branch of the same \texttt{If} node have the same condition, they can be merged, so that the resulting guard is anchored at the most distant node of which the \texttt{If} node is a postdominator. \begin{figure}[ht] @@ -684,8 +701,8 @@ \textnode{p}{p} \textnode{const0}{0} \nodeguard{guard2}{Guard} - \nodetrisplit{store1}{MemStore 16 (int)} - \nodetrisplit{store2}{MemStore 20 (int)} + \nodetrisplit{store1}{MemStore 16 (4 bytes)} + \nodetrisplit{store2}{MemStore 20 (4 bytes)} \nodeframestate{fs1}{FrameState} \nodeframestate{fs2}{FrameState} \data{store1:in1}{p} @@ -714,7 +731,7 @@ The remaining guard can now be moved above the \texttt{If} condition and be used to eliminate the need for the \texttt{If} node. From this point on, the guard can however no longer be moved below the first memory store. We use a control dependency from the guard to the field store to express this condition. -The link between the second store and the guard and the control flow merge instruction is no longer necessary. +The link between the second store and the guard and the control flow merge node is no longer necessary. \begin{figure}[ht] \centering @@ -726,8 +743,8 @@ \textnode{p}{p} \textnode{const0}{0} \nodeguard{guard2}{Guard} - \nodetrisplit{store1}{MemStore 16 (int)} - \nodetrisplit{store2}{MemStore 20 (int)} + \nodetrisplit{store1}{MemStore 16 (4 bytes)} + \nodetrisplit{store2}{MemStore 20 (4 bytes)} \nodeframestate{fs1}{FrameState} \nodeframestate{fs2}{FrameState} \data{store1:in1}{p} @@ -766,8 +783,8 @@ \textnode{p}{p} \textnode{const0}{0} \nodeguard{guard2}{Guard} - \nodetrisplit{store1}{MemStore 16 (int)} - \nodetrisplit{store2}{MemStore 20 (int)} + \nodetrisplit{store1}{MemStore 16 (4 bytes)} + \nodetrisplit{store2}{MemStore 20 (4 bytes)} \data{store1:in1}{p} \data{store2:in1}{p} \data{store1:in2}{const0} @@ -801,7 +818,7 @@ \textnode{p}{p} \textnode{const0}{0} \nodeguard{guard2}{Guard} - \nodetrisplit{store1}{MemStore 16 (long)} + \nodetrisplit{store1}{MemStore 16 (8 bytes)} \data{store1:in1}{p} \data{store1:in2}{const0} \data{guard2:in1}{anchor1} @@ -816,18 +833,18 @@ \label{fig:guard5} \end{figure} -A memory store that immediately follows a null check guard instruction on the same object, can be combined into a store with an implicit null check (that deoptimizes instead of throwing the exception). +A memory store that immediately follows a null check guard node on the same object, can be combined into a store with an implicit null check (that deoptimizes instead of throwing the exception). Therefore, we can remove the guard again and also the anchor is no longer necessary. Figure~\ref{fig:guard6} shows now that fully optimized graph that is generated for Listing~\ref{lst:guard1}. \begin{figure}[ht] \centering -\begin{digraphenv}{scale=0.5}{guard6} +\begin{digraphenv}{scale=0.5}{guard6} \textnode{entry}{Entry} \node{return}{Return} \textnode{p}{p} \textnode{const0}{0} - \nodetrisplit{store1}{DeoptimizingMemStore 16 (long)} + \nodetrisplit{store1}{DeoptimizingMemStore 16 (8 bytes)} \data{store1:in1}{p} \data{store1:in2}{const0} \control{entry}{store1} @@ -841,8 +858,9 @@ \section{Conclusions} \label{sec:conclusions} This document sketched the strategy for the Graph compiler. -We already reached M1 (as defined in Section~\ref{sec:mile}) and have the following plans for M2 to M4: +We have the following plans for M1 to M4: \begin{description} +\item[M1:] May 15th, 2011 \item[M2:] June 30th, 2011 \item[M3:] August 15th, 2011 \item[M4:] September 30th, 2011
--- a/graal/com.oracle.max.graal.doc.initial/graphdrawing.tex Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.doc.initial/graphdrawing.tex Tue Jun 14 10:32:29 2011 +0200 @@ -23,8 +23,8 @@ \NewEnviron{digraphenv}[2]{\digraph[#1]{#2}{ nodesep="0.1"; ranksep="0.08 equally"; \BODY }} -\newcommand{\control}[2]{#1:successors:s -> #2:predecessors:n [color=red];} -\newcommand{\controllabel}[2]{#1:s -> #2:predecessors:n [color=red];} +\newcommand{\control}[2]{#1:successors:s -> #2:predecessors:n [color=red,style=solid];} +\newcommand{\controllabel}[2]{#1:s -> #2:predecessors:n [color=red,style=solid];} \newcommand{\data}[2]{#2:usages:s -> #1:inputs [color=black,dir=back];} \newcommand{\datalabel}[2]{#2:usages:s -> #1:n [color=black,dir=back];} \newcommand{\datalabeltext}[3]{#2:usages:s -> #1:n [color=black,dir=back,label="#3"];}
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Tue Jun 14 10:32:29 2011 +0200 @@ -65,6 +65,10 @@ check(node); bitMap.clear(node.id()); } + + public void clearAll() { + bitMap.clearAll(); + } public void grow(Node node) { bitMap.grow(node.id() + 1);
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotXirGenerator.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotXirGenerator.java Tue Jun 14 10:32:29 2011 +0200 @@ -998,8 +998,8 @@ asm.bindOutOfLine(slowStoreCheck); checkSubtype(asm, temp, valueHub, compHub); asm.jneq(store, temp, asm.w(0)); - XirOperand scratch = asm.createRegisterTemp("scratch", CiKind.Object, AMD64.r10); - asm.mov(scratch, valueHub); + XirOperand scratch = asm.createRegisterTemp("scratch", CiKind.Word, AMD64.r10); + asm.mov(scratch, asm.createConstant(CiConstant.forWord(0))); asm.callRuntime(CiRuntimeCall.Deoptimize, null); asm.shouldNotReachHere(); }
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMExitsNative.java Tue Jun 14 10:03:09 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMExitsNative.java Tue Jun 14 10:32:29 2011 +0200 @@ -77,7 +77,6 @@ public void startCompiler() { originalOut = System.out; originalErr = System.err; - //TTY.println("startCompiler: " + originalOut); } public void shutdownCompiler() throws Throwable {
--- a/runfop.sh Tue Jun 14 10:03:09 2011 +0200 +++ b/runfop.sh Tue Jun 14 10:32:29 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 fop +${JDK7}/bin/java -client -d64 -graal -Xms1g -Xmx2g -esa -classpath ${DACAPO}/dacapo-9.12-bach.jar $* Harness --preserve -n 5 fop
--- a/src/cpu/x86/vm/sharedRuntime_x86_64.cpp Tue Jun 14 10:03:09 2011 +0200 +++ b/src/cpu/x86/vm/sharedRuntime_x86_64.cpp Tue Jun 14 10:32:29 2011 +0200 @@ -2656,6 +2656,7 @@ int jmp_uncommon_trap_offset = __ pc() - start; __ pushptr(Address(r15_thread, in_bytes(JavaThread::ScratchA_offset()))); + __ movptr(rscratch1, 0); int uncommon_trap_offset = __ pc() - start; @@ -2752,7 +2753,7 @@ // or captured in the vframeArray. RegisterSaver::restore_result_registers(masm); - // All of the register save area has been popped of the stack. Only the + // All of the register save area has been poppeset_jmp_uncommon_trap_offsetd of the stack. Only the // return address remains. // Pop all the frames we must move/replace.
--- a/src/share/vm/graal/graalCodeInstaller.cpp Tue Jun 14 10:03:09 2011 +0200 +++ b/src/share/vm/graal/graalCodeInstaller.cpp Tue Jun 14 10:32:29 2011 +0200 @@ -106,7 +106,8 @@ } // TODO: finish this - graal doesn't provide any scope values at the moment -static ScopeValue* get_hotspot_value(oop value, int frame_size) { +static ScopeValue* get_hotspot_value(oop value, int frame_size, ScopeValue* &second) { + second = NULL; if (value == CiValue::IllegalValue()) { return new LocationValue(Location::new_stk_loc(Location::invalid, 0)); } @@ -114,27 +115,61 @@ BasicType type = GraalCompiler::kindToBasicType(CiKind::typeChar(CiValue::kind(value))); Location::Type locationType = Location::normal; if (type == T_OBJECT || type == T_ARRAY) locationType = Location::oop; + if (value->is_a(CiRegisterValue::klass())) { jint number = CiRegister::number(CiRegisterValue::reg(value)); if (number < 16) { - return new LocationValue(Location::new_reg_loc(locationType, as_Register(number)->as_VMReg())); + if (type == T_INT || type == T_FLOAT || type == T_SHORT || type == T_CHAR || type == T_BOOLEAN || type == T_BYTE) { + locationType = Location::int_in_long; + } else if (type == T_LONG) { + locationType = Location::lng; + } else { + assert(type == T_OBJECT || type == T_ARRAY, "unexpected type in cpu register"); + } + ScopeValue* value = new LocationValue(Location::new_reg_loc(locationType, as_Register(number)->as_VMReg())); + if (type == T_LONG) { + second = value; + } + return value; } else { - return new LocationValue(Location::new_reg_loc(locationType, as_XMMRegister(number - 16)->as_VMReg())); + assert(type == T_FLOAT || type == T_DOUBLE, "only float and double expected in xmm register"); + if (type == T_FLOAT) { + // this seems weird, but the same value is used in c1_LinearScan + locationType = Location::normal; + } else { + locationType = Location::dbl; + } + ScopeValue* value = new LocationValue(Location::new_reg_loc(locationType, as_XMMRegister(number - 16)->as_VMReg())); + if (type == T_DOUBLE) { + second = value; + } + return value; } } else if (value->is_a(CiStackSlot::klass())) { + if (type == T_DOUBLE) { + locationType = Location::dbl; + } else if (type == T_LONG) { + locationType = Location::lng; + } jint index = CiStackSlot::index(value); + ScopeValue* value; if (index >= 0) { - return new LocationValue(Location::new_stk_loc(locationType, index * HeapWordSize)); + value = new LocationValue(Location::new_stk_loc(locationType, index * HeapWordSize)); } else { int frame_size_bytes = frame_size + 2 * HeapWordSize; - return new LocationValue(Location::new_stk_loc(locationType, -(index * HeapWordSize) + frame_size_bytes)); + value = new LocationValue(Location::new_stk_loc(locationType, -(index * HeapWordSize) + frame_size_bytes)); } + if (type == T_DOUBLE || type == T_LONG) { + second = value; + } + return value; } else if (value->is_a(CiConstant::klass())){ oop obj = CiConstant::object(value); jlong prim = CiConstant::primitive(value); if (type == T_INT || type == T_FLOAT || type == T_SHORT || type == T_CHAR || type == T_BOOLEAN || type == T_BYTE) { return new ConstantIntValue(*(jint*)&prim); } else if (type == T_LONG || type == T_DOUBLE) { + second = new ConstantIntValue(0); return new ConstantLongValue(prim); } else if (type == T_OBJECT) { oop obj = CiConstant::object(value); @@ -433,19 +468,32 @@ } for (jint i = 0; i < values->length(); i++) { - ScopeValue* value = get_hotspot_value(((oop*) values->base(T_OBJECT))[i], _frame_size); + ScopeValue* second = NULL; + ScopeValue* value = get_hotspot_value(((oop*) values->base(T_OBJECT))[i], _frame_size, second); if (i < local_count) { + if (second != NULL) { + locals->append(second); + } locals->append(value); } else if (i < local_count + expression_count) { + if (second != NULL) { + expressions->append(value); + } expressions->append(value); } else { + assert(second == NULL, "monitor cannot occupy two stack slots"); assert(value->is_location(), "invalid monitor location"); LocationValue* loc = (LocationValue*)value; int monitor_offset = loc->location().stack_offset(); LocationValue* obj = new LocationValue(Location::new_stk_loc(Location::oop, monitor_offset + BasicObjectLock::obj_offset_in_bytes())); monitors->append(new MonitorValue(obj, Location::new_stk_loc(Location::normal, monitor_offset + BasicObjectLock::lock_offset_in_bytes()))); } + if (second != NULL) { + i++; + assert(i < values->length(), "double-slot value not followed by CiValue.IllegalValue"); + assert(((oop*) values->base(T_OBJECT))[i] == CiValue::IllegalValue(), "double-slot value not followed by CiValue.IllegalValue"); + } } DebugToken* locals_token = _debug_recorder->create_scope_values(locals); DebugToken* expressions_token = _debug_recorder->create_scope_values(expressions);
--- a/src/share/vm/runtime/deoptimization.cpp Tue Jun 14 10:03:09 2011 +0200 +++ b/src/share/vm/runtime/deoptimization.cpp Tue Jun 14 10:32:29 2011 +0200 @@ -1221,6 +1221,8 @@ DeoptAction action = trap_request_action(trap_request); jint unloaded_class_index = trap_request_index(trap_request); // CP idx or -1 +// tty->print_cr("trap_request: %08x, cpi: %i, pc: %016x", trap_request, unloaded_class_index, fr.pc()); + Events::log("Uncommon trap occurred @" INTPTR_FORMAT " unloaded_class_index = %d", fr.pc(), (int) trap_request); vframe* vf = vframe::new_vframe(&fr, ®_map, thread); compiledVFrame* cvf = compiledVFrame::cast(vf);