Mercurial > hg > graal-compiler
changeset 3088:be5deef7c7a0
more escape analysis changes
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Mon Jun 27 17:13:33 2011 +0200 @@ -56,6 +56,7 @@ // escape analysis settings public static int ForcedInlineEscapeWeight = 0; + public static int MaximumEscapeAnalysisArrayLength = 32; // debugging settings public static boolean VerifyPointerMaps = ____; @@ -103,6 +104,7 @@ public static boolean TraceAssembler = ____; public static boolean TraceInlining = ____; public static boolean TraceDeadCodeElimination = ____; + public static boolean TraceEscapeAnalysis = ____; public static int TraceBytecodeParserLevel = 0; public static boolean QuietBailout = ____;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Mon Jun 27 17:13:33 2011 +0200 @@ -398,7 +398,7 @@ @Override public void visitNewObjectArray(NewObjectArray x) { XirArgument length = toXirArgument(x.length()); - XirSnippet snippet = xir.genNewArray(site(x), length, CiKind.Object, x.elementClass(), x.exactType()); + XirSnippet snippet = xir.genNewArray(site(x), length, CiKind.Object, x.elementType(), x.exactType()); emitXir(snippet, x, stateFor(x), null, true); } @@ -1598,7 +1598,9 @@ private void walkStateValue(Value value) { if (value != null) { - if (value instanceof Phi && !((Phi) value).isDead()) { + if (value instanceof VirtualObject) { + walkVirtualObject((VirtualObject) value); + } else if (value instanceof Phi && !((Phi) value).isDead()) { // phi's are special operandForPhi((Phi) value); } else if (value.operand().isIllegal()) { @@ -1609,6 +1611,13 @@ } } + private void walkVirtualObject(VirtualObject value) { + walkStateValue(value.input()); + if (value.object() != null) { + walkVirtualObject(value.object()); + } + } + protected LIRDebugInfo stateFor(Value x) { assert lastState != null : "must have state before instruction for " + x; return stateFor(x, lastState);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MemoryWrite.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MemoryWrite.java Mon Jun 27 17:13:33 2011 +0200 @@ -30,7 +30,6 @@ public final class MemoryWrite extends MemoryAccess { - private static final EscapeOp ESCAPE = new NewInstanceEscapeOp(); private static final int INPUT_COUNT = 1; private static final int INPUT_VALUE = 0; @@ -63,20 +62,4 @@ public Node copy(Graph into) { return new MemoryWrite(super.kind, null, displacement(), into); } - - @SuppressWarnings("unchecked") - @Override - public <T extends Op> T lookup(Class<T> clazz) { - if (clazz == EscapeOp.class) { - return (T) ESCAPE; - } - return super.lookup(clazz); - } - - private static class NewInstanceEscapeOp implements EscapeOp { - @Override - public Escape escape(Node node, Node value) { - return Escape.NewValue; - } - } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewArray.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewArray.java Mon Jun 27 17:13:33 2011 +0200 @@ -22,13 +22,21 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.EscapeField; +import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.EscapeOp; +import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; +import com.sun.cri.ri.*; /** * The {@code NewArray} class is the base of all instructions that allocate arrays. */ public abstract class NewArray extends Instruction { + private static final EscapeOp ESCAPE = new NewArrayEscapeOp(); private static final int INPUT_COUNT = 1; private static final int INPUT_LENGTH = 0; @@ -67,4 +75,158 @@ super(CiKind.Object, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph); setLength(length); } + + /** + * The list of instructions which produce input for this instruction. + */ + public Value dimension(int index) { + assert index == 0; + return length(); + } + + /** + * The rank of the array allocated by this instruction, i.e. how many array dimensions. + */ + public int dimensionCount() { + return 1; + } + + public abstract CiKind elementKind(); + + @SuppressWarnings("unchecked") + @Override + public <T extends Op> T lookup(Class<T> clazz) { + if (clazz == EscapeOp.class) { + return (T) ESCAPE; + } + return super.lookup(clazz); + } + + private static class NewArrayEscapeOp implements EscapeOp { + + @Override + public boolean canAnalyze(Node node) { + NewArray x = (NewArray) node; + CiConstant length = x.dimension(0).asConstant(); + return length != null && length.asInt() >= 0 && length.asInt() < GraalOptions.MaximumEscapeAnalysisArrayLength; + } + + @Override + public boolean escape(Node node, Node usage) { + if (usage instanceof IsNonNull) { + IsNonNull x = (IsNonNull) usage; + assert x.object() == node; + return false; + } else if (usage instanceof IsType) { + IsType x = (IsType) usage; + assert x.object() == node; + return false; + } else if (usage instanceof FrameState) { + FrameState x = (FrameState) usage; + assert x.inputs().contains(node); + return true; + } else if (usage instanceof LoadIndexed) { + LoadIndexed x = (LoadIndexed) usage; + assert x.array() == node; + CiConstant index = x.index().asConstant(); + CiConstant length = ((NewArray) node).dimension(0).asConstant(); + if (index == null || length == null || index.asInt() < 0 || index.asInt() >= length.asInt()) { + return true; + } + return false; + } else if (usage instanceof StoreField) { + StoreField x = (StoreField) usage; + assert x.value() == node; + return true; + } else if (usage instanceof StoreIndexed) { + StoreIndexed x = (StoreIndexed) usage; + CiConstant index = x.index().asConstant(); + CiConstant length = ((NewArray) node).dimension(0).asConstant(); + if (index == null || length == null || index.asInt() < 0 || index.asInt() >= length.asInt()) { + return true; + } + return x.value() == node; + } else if (usage instanceof AccessMonitor) { + AccessMonitor x = (AccessMonitor) usage; + assert x.object() == node; + return false; + } else if (usage instanceof ArrayLength) { + ArrayLength x = (ArrayLength) usage; + assert x.array() == node; + return false; + } else if (usage instanceof VirtualObject) { + VirtualObject x = (VirtualObject) usage; + return false; + } else { + return true; + } + } + + @Override + public void beforeUpdate(Node node, Node usage) { + if (usage instanceof IsNonNull) { + IsNonNull x = (IsNonNull) usage; + if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) { + FixedGuard guard = (FixedGuard) x.usages().get(0); + guard.replace(guard.next()); + } + x.delete(); + } else if (usage instanceof IsType) { + IsType x = (IsType) usage; + assert x.type() == ((NewArray) node).exactType(); + if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) { + FixedGuard guard = (FixedGuard) x.usages().get(0); + guard.replace(guard.next()); + } + x.delete(); + } else if (usage instanceof AccessMonitor) { + AccessMonitor x = (AccessMonitor) usage; + x.replace(x.next()); + } else if (usage instanceof ArrayLength) { + ArrayLength x = (ArrayLength) usage; + x.replace(((NewArray) node).dimension(0)); + } + } + + @Override + public void collectField(Node node, Node usage, Map<Object, EscapeField> fields) { + if (usage instanceof AccessIndexed) { + AccessIndexed x = (AccessIndexed) usage; + CiConstant index = x.index().asConstant(); + CiConstant length = ((NewArray) node).dimension(0).asConstant(); + assert index != null && length != null && index.asInt() >= 0 && index.asInt() < length.asInt(); + + Integer representation = index.asInt(); + if (!fields.containsKey(representation)) { + fields.put(representation, new EscapeField("[" + representation + "]", representation, ((NewArray) node).elementKind())); + } + } + } + + @Override + public void updateState(Node node, Node current, Map<Object, EscapeField> fields, Map<EscapeField, Node> fieldState) { + if (current instanceof AccessIndexed) { + int index = ((AccessIndexed) current).index().asConstant().asInt(); + EscapeField field = fields.get(index); + if (current instanceof LoadIndexed) { + LoadIndexed x = (LoadIndexed) current; + if (x.array() == node) { + for (Node usage : new ArrayList<Node>(x.usages())) { + assert fieldState.get(field) != null; + usage.inputs().replace(x, fieldState.get(field)); + } + assert x.usages().size() == 0; + x.replace(x.next()); + } + } else if (current instanceof StoreIndexed) { + StoreIndexed x = (StoreIndexed) current; + if (x.array() == node) { + fieldState.put(field, x.value()); + assert x.usages().size() == 0; + x.replace(x.next()); + } + } + } + } + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java Mon Jun 27 17:13:33 2011 +0200 @@ -22,9 +22,12 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; -import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.Escape; +import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.EscapeField; import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.EscapeOp; +import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -99,9 +102,113 @@ } private static class NewInstanceEscapeOp implements EscapeOp { + @Override - public Escape escape(Node node, Node value) { - return Escape.NewValue; + public boolean canAnalyze(Node node) { + return ((NewInstance) node).instanceClass().isResolved(); + } + + @Override + public boolean escape(Node node, Node usage) { + if (usage instanceof IsNonNull) { + IsNonNull x = (IsNonNull) usage; + assert x.object() == node; + return false; + } else if (usage instanceof IsType) { + IsType x = (IsType) usage; + assert x.object() == node; + return false; + } else if (usage instanceof FrameState) { + FrameState x = (FrameState) usage; + assert x.inputs().contains(node); + return true; + } else if (usage instanceof LoadField) { + LoadField x = (LoadField) usage; + assert x.object() == node; + return false; + } else if (usage instanceof StoreField) { + StoreField x = (StoreField) usage; + return x.value() == node; + } else if (usage instanceof StoreIndexed) { + StoreIndexed x = (StoreIndexed) usage; + assert x.value() == node; + return true; + } else if (usage instanceof AccessMonitor) { + AccessMonitor x = (AccessMonitor) usage; + assert x.object() == node; + return false; + } else if (usage instanceof VirtualObject) { + VirtualObject x = (VirtualObject) usage; + return false; + } else if (usage instanceof RegisterFinalizer) { + RegisterFinalizer x = (RegisterFinalizer) usage; + assert x.object() == node; + return false; + } else { + return true; + } + } + + @Override + public void beforeUpdate(Node node, Node usage) { + if (usage instanceof IsNonNull) { + IsNonNull x = (IsNonNull) usage; + if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) { + FixedGuard guard = (FixedGuard) x.usages().get(0); + guard.replace(guard.next()); + } + x.delete(); + } else if (usage instanceof IsType) { + IsType x = (IsType) usage; + assert x.type() == ((NewInstance) node).instanceClass(); + if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) { + FixedGuard guard = (FixedGuard) x.usages().get(0); + guard.replace(guard.next()); + } + x.delete(); + } else if (usage instanceof AccessMonitor) { + AccessMonitor x = (AccessMonitor) usage; + x.replace(x.next()); + } else if (usage instanceof RegisterFinalizer) { + RegisterFinalizer x = (RegisterFinalizer) usage; + x.replace(x.next()); + } + } + + @Override + public void collectField(Node node, Node usage, Map<Object, EscapeField> fields) { + if (usage instanceof AccessField) { + AccessField x = (AccessField) usage; + assert x.object() == node; + if (!fields.containsKey(x.field())) { + fields.put(x.field(), new EscapeField(x.field().name(), x.field(), x.field.kind().stackKind())); + } + } + } + + @Override + public void updateState(Node node, Node current, Map<Object, EscapeField> fields, Map<EscapeField, Node> fieldState) { + if (current instanceof AccessField) { + EscapeField field = fields.get(((AccessField) current).field()); + if (current instanceof LoadField) { + LoadField x = (LoadField) current; + if (x.object() == node) { + for (Node usage : new ArrayList<Node>(x.usages())) { + assert fieldState.get(field) != null; + usage.inputs().replace(x, fieldState.get(field)); + } + assert x.usages().size() == 0; + x.replace(x.next()); + } + } else if (current instanceof StoreField) { + StoreField x = (StoreField) current; + if (x.object() == node) { + fieldState.put(field, x.value()); + assert x.usages().size() == 0; + x.replace(x.next()); + } + } + } } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewMultiArray.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewMultiArray.java Mon Jun 27 17:13:33 2011 +0200 @@ -50,6 +50,7 @@ /** * The list of instructions which produce input for this instruction. */ + @Override public Value dimension(int index) { assert index >= 0 && index < dimensionCount; return (Value) inputs().get(super.inputCount() + index); @@ -63,6 +64,7 @@ /** * The rank of the array allocated by this instruction, i.e. how many array dimensions. */ + @Override public int dimensionCount() { return dimensionCount; } @@ -105,6 +107,21 @@ } @Override + public CiKind elementKind() { + return elementType.kind(); + } + + @Override + public RiType exactType() { + return elementType.arrayOf(); + } + + @Override + public RiType declaredType() { + return exactType(); + } + + @Override public void print(LogStream out) { out.print("new multi array ["); for (int i = 0; i < dimensionCount; i++) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewObjectArray.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewObjectArray.java Mon Jun 27 17:13:33 2011 +0200 @@ -52,11 +52,16 @@ * Gets the type of the elements of the array. * @return the element type of the array */ - public RiType elementClass() { + public RiType elementType() { return elementClass; } @Override + public CiKind elementKind() { + return elementClass.kind(); + } + + @Override public RiType exactType() { return elementClass.arrayOf(); } @@ -73,7 +78,7 @@ @Override public void print(LogStream out) { - out.print("new object array [").print(length()).print("] ").print(CiUtil.toJavaName(elementClass())); + out.print("new object array [").print(length()).print("] ").print(CiUtil.toJavaName(elementType())); } @Override
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewTypeArray.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewTypeArray.java Mon Jun 27 17:13:33 2011 +0200 @@ -42,6 +42,7 @@ this.elementType = elementType; } + @Override public CiKind elementKind() { return elementType.kind(); }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/VirtualObject.java Mon Jun 27 17:13:33 2011 +0200 @@ -0,0 +1,125 @@ +/* + * 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.compiler.debug.*; +import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.EscapeField; +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; +import com.sun.cri.ri.*; + + +public class VirtualObject extends FloatingNode { + + private static final int INPUT_COUNT = 2; + private static final int INPUT_OBJECT = 0; + private static final int INPUT_INPUT = 1; + + 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 specifies the old state of the virtual object. + */ + public VirtualObject object() { + return (VirtualObject) inputs().get(super.inputCount() + INPUT_OBJECT); + } + + public VirtualObject setObject(VirtualObject n) { + return (VirtualObject) inputs().set(super.inputCount() + INPUT_OBJECT, n); + } + + /** + * The instruction that contains the new state of the specified field. + */ + public Value input() { + return (Value) inputs().get(super.inputCount() + INPUT_INPUT); + } + + public Value setInput(Value n) { + return (Value) inputs().set(super.inputCount() + INPUT_INPUT, n); + } + + private EscapeField field; + private RiType type; + + /** + * Constructs a new ArrayLength instruction. + * @param array the instruction producing the array + * @param newFrameState the state after executing this instruction + */ + public VirtualObject(VirtualObject object, EscapeField field, RiType type, Graph graph) { + super(CiKind.Int, INPUT_COUNT, SUCCESSOR_COUNT, graph); + this.field = field; + this.type = type; + setObject(object); + } + + public EscapeField field() { + return field; + } + + public RiType type() { + return type; + } + + @Override + public void accept(ValueVisitor v) { + // nothing to do... + } + + @Override + public Map<Object, Object> getDebugProperties() { + Map<Object, Object> properties = super.getDebugProperties(); + properties.put("type", type); + properties.put("field", field); + return properties; + } + + @Override + public String shortName() { + return "VirtualObject " + field.name(); + } + + @Override + public void print(LogStream out) { + out.print(object()).print(".").print(field.name()).print("=").print(input()); + } + + @Override + public Node copy(Graph into) { + VirtualObject x = new VirtualObject(null, field, type, into); + return x; + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Mon Jun 27 17:13:33 2011 +0200 @@ -27,11 +27,13 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.gen.*; import com.oracle.max.graal.compiler.graph.*; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.schedule.*; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; import com.sun.cri.ri.*; @@ -39,37 +41,50 @@ public static class BlockExitState { - public final HashMap<RiField, Node> fieldState; + public final Map<EscapeField, Node> fieldState; public BlockExitState() { - this.fieldState = new HashMap<RiField, Node>(); + this.fieldState = new HashMap<EscapeField, Node>(); } } public class EscapementFixup { private List<Block> blocks; - private final HashMap<String, RiField> fields = new HashMap<String, RiField>(); - - private final HashMap<Block, BlockExitState> exitStates = new HashMap<Block, BlockExitState>(); + private final Map<Object, EscapeField> fields = new HashMap<Object, EscapeField>(); + private final Map<Block, BlockExitState> exitStates = new HashMap<Block, BlockExitState>(); + private final EscapeOp op; + private Graph graph; + private final Node node; - public void apply(final Graph graph, final Node node) { - process(node); - removeAllocation(graph, node); + public EscapementFixup(EscapeOp op, Graph graph, Node node) { + this.op = op; + this.graph = graph; + this.node = node; } - public void removeAllocation(final Graph graph, final Node node) { + public void apply() { + process(); + removeAllocation(); + } + + public void removeAllocation() { final IdentifyBlocksPhase identifyBlocksPhase = new IdentifyBlocksPhase(true); identifyBlocksPhase.apply(graph); blocks = identifyBlocksPhase.getBlocks(); - final HashMap<Phi, RiField> phis = new HashMap<Phi, RiField>(); + final HashMap<Phi, EscapeField> phis = new HashMap<Phi, EscapeField>(); + final Block startBlock = identifyBlocksPhase.getNodeToBlock().get(node); + assert startBlock != null; + final RiType type = ((Value) node).exactType(); Block.iteratePostOrder(blocks, new BlockClosure() { public void apply(Block block) { -// TTY.println("Block %d", block.blockID()); + if (GraalOptions.TraceEscapeAnalysis) { + TTY.println("Block %d", block.blockID()); + } // for (Node n : block.getInstructions()) { // TTY.println(" %d %s", n.id(), n.shortName()); // } @@ -78,37 +93,39 @@ // } // TTY.println(); - BlockExitState state; - List<Block> predecessors = block.getPredecessors(); - Set<RiField> mergedFields = new HashSet<RiField>(); - state = new BlockExitState(); - for (int i = 0; i < predecessors.size(); i++) { - BlockExitState exitState = exitStates.get(predecessors.get(i)); - if (exitState == null) { - mergedFields.addAll(fields.values()); - } else { - for (RiField field : fields.values()) { - if (state.fieldState.get(field) == null) { - state.fieldState.put(field, exitState.fieldState.get(field)); - } else if (state.fieldState.get(field) != exitState.fieldState.get(field)) { - mergedFields.add(field); + BlockExitState state = new BlockExitState(); + if (block == startBlock) { + for (EscapeField field : fields.values()) { + state.fieldState.put(field, Constant.defaultForKind(field.kind(), graph)); + } + } else { + List<Block> predecessors = block.getPredecessors(); + Set<EscapeField> mergedFields = new HashSet<EscapeField>(); + for (int i = 0; i < predecessors.size(); i++) { + BlockExitState exitState = exitStates.get(predecessors.get(i)); + if (exitState == null) { + mergedFields.addAll(fields.values()); + break; + } else { + for (EscapeField field : fields.values()) { + if (state.fieldState.get(field) == null) { + state.fieldState.put(field, exitState.fieldState.get(field)); + } else if (state.fieldState.get(field) != exitState.fieldState.get(field)) { + mergedFields.add(field); + } } } } - } - if (!mergedFields.isEmpty()) { - assert block.firstNode() instanceof Merge : "unexpected: " + block.firstNode().shortName() + " " + block.firstNode().id(); - for (RiField field : mergedFields) { - Phi phi = new Phi(field.kind().stackKind(), (Merge) block.firstNode(), graph); - state.fieldState.put(field, phi); - phis.put(phi, field); + if (!mergedFields.isEmpty()) { + assert block.firstNode() instanceof Merge : "unexpected: " + block.firstNode().shortName() + " " + block.firstNode().id(); + for (EscapeField field : mergedFields) { + Phi phi = new Phi(field.kind().stackKind(), (Merge) block.firstNode(), graph); + state.fieldState.put(field, phi); + phis.put(phi, field); + } } } - if (identifyBlocksPhase.getNodeToBlock().get(node) == block) { - state = new BlockExitState(); - } - Node current; if (block.firstNode() instanceof StartNode) { current = ((StartNode) block.firstNode()).start(); @@ -116,99 +133,124 @@ current = block.firstNode(); } while (current != block.lastNode()) { - if (current instanceof LoadField) { - LoadField x = (LoadField) current; - if (x.object() == node) { - for (Node usage : new ArrayList<Node>(x.usages())) { - assert state.fieldState.get(x.field()) != null; - usage.inputs().replace(x, state.fieldState.get(x.field())); - } - current = ((Instruction) current).next(); - x.replace(x.next()); - } else { - current = ((Instruction) current).next(); + Node next = ((Instruction) current).next(); + op.updateState(node, current, fields, state.fieldState); + if (!current.isDeleted() && current instanceof Instruction) { + FrameState stateAfter = ((Instruction) current).stateAfter(); + if (stateAfter != null) { + updateFrameState(stateAfter, state, type, null); } - } else if (current instanceof StoreField) { - StoreField x = (StoreField) current; - if (x.object() == node) { - state.fieldState.put(x.field(), x.value()); - current = ((Instruction) current).next(); - x.replace(x.next()); - } else { - current = ((Instruction) current).next(); - } - } else { - current = ((Instruction) current).next(); } + current = next; } + if (GraalOptions.TraceEscapeAnalysis) { + TTY.print(" block end state: "); + for (Entry<EscapeField, Node> entry : state.fieldState.entrySet()) { + TTY.print("%s->%s ", entry.getKey().name(), entry.getValue()); + } + TTY.println(); + } exitStates.put(block, state); } - }); + }, startBlock); - for (Entry<Phi, RiField> entry : phis.entrySet()) { + for (Entry<Phi, EscapeField> entry : phis.entrySet()) { Phi phi = entry.getKey(); - RiField field = entry.getValue(); + EscapeField field = entry.getValue(); Block block = identifyBlocksPhase.getNodeToBlock().get(entry.getKey().merge()); List<Block> predecessors = block.getPredecessors(); - for (int i = 0; i < predecessors.size(); i++) { + assert predecessors.size() > 0; + Node simple = exitStates.get(predecessors.get(0)).fieldState.get(field); + for (int i = 1; i < predecessors.size(); i++) { BlockExitState exitState = exitStates.get(predecessors.get(i)); - assert exitState != null; - Node value = exitState.fieldState.get(field); - TTY.println("fixing phi %d with %s", phi.id(), value); - if (value == null) { - phi.addInput(Constant.defaultForKind(field.kind(), graph)); - } else { - phi.addInput(value); + if (exitState.fieldState.get(field) != simple) { + simple = null; } } - + if (simple != null) { + for (Node usage : new ArrayList<Node>(phi.usages())) { + usage.inputs().replace(phi, simple); + } + phi.delete(); + } else { + for (int i = 0; i < predecessors.size(); i++) { + BlockExitState exitState = exitStates.get(predecessors.get(i)); + assert exitState != null; + Node value = exitState.fieldState.get(field); + if (GraalOptions.TraceEscapeAnalysis) { + TTY.println("fixing phi %d with %s", phi.id(), value); + } + if (value == null) { + phi.addInput(Constant.defaultForKind(field.kind(), graph)); + } else { + phi.addInput(value); + } + } + } + } + // the rest of the usages should be dead frame states... + for (Node usage : new ArrayList<Node>(node.usages())) { + assert usage instanceof FrameState || usage instanceof VirtualObject; + usage.inputs().replace(node, Node.Null); } - node.delete(); + if (node instanceof Instruction) { + node.replace(((Instruction) node).next()); + } else { + node.delete(); + } } - - private void process(Node node) { - for (Node usage : new ArrayList<Node>(node.usages())) { - if (usage instanceof IsNonNull) { - IsNonNull x = (IsNonNull) usage; - if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) { - FixedGuard guard = (FixedGuard) x.usages().get(0); - guard.replace(guard.next()); - } - x.delete(); - } else if (usage instanceof IsType) { - IsType x = (IsType) usage; - assert x.type() == ((NewInstance) node).instanceClass(); - if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) { - FixedGuard guard = (FixedGuard) x.usages().get(0); - guard.replace(guard.next()); + private VirtualObject updateFrameState(FrameState frameState, BlockExitState currentState, RiType type, VirtualObject current) { + for (int i = 0; i < frameState.inputs().size(); i++) { + if (frameState.inputs().get(i) == node) { + if (current == null) { + for (EscapeField field : fields.values()) { + current = new VirtualObject(current, field, type, graph); + current.setInput((Value) currentState.fieldState.get(field)); + } } - x.delete(); - } else if (usage instanceof FrameState) { - FrameState x = (FrameState) usage; - x.inputs().replace(node, Node.Null); - } else if (usage instanceof StoreField) { - StoreField x = (StoreField) usage; - assert x.object() == node; - assert fields.get(x.field().name()) == null || fields.get(x.field().name()) == x.field(); - fields.put(x.field().name(), x.field()); - } else if (usage instanceof AccessMonitor) { - AccessMonitor x = (AccessMonitor) usage; - TTY.println("replacing %d with %d (%s)", x.id(), x.next().id(), x.shortName()); - x.replace(x.next()); - } else if (usage instanceof LoadField) { - LoadField x = (LoadField) usage; - assert x.object() == node; - assert fields.get(x.field().name()) == null || fields.get(x.field().name()) == x.field(); - fields.put(x.field().name(), x.field()); - } else if (usage instanceof RegisterFinalizer) { - RegisterFinalizer x = (RegisterFinalizer) usage; - x.replace(x.next()); - } else { - assert false; + frameState.inputs().set(i, current); + } else if (frameState.inputs().get(i) instanceof VirtualObject) { + VirtualObject obj = (VirtualObject) frameState.inputs().get(i); + do { + current = updateVirtualObject(obj, currentState, type, current); + obj = obj.object(); + } while (obj != null); + } + } + if (frameState.outerFrameState() != null) { + current = updateFrameState(frameState.outerFrameState(), currentState, type, current); + } + return current; + } + + private VirtualObject updateVirtualObject(VirtualObject obj, BlockExitState currentState, RiType type, VirtualObject current) { + if (obj.input() == node) { + if (current == null) { + for (EscapeField field : fields.values()) { + current = new VirtualObject(current, field, type, graph); + current.setInput((Value) currentState.fieldState.get(field)); + } + } + obj.setInput(current); + } else if (obj.input() instanceof VirtualObject) { + VirtualObject obj2 = (VirtualObject) obj.input(); + do { + current = updateVirtualObject(obj2, currentState, type, current); + obj2 = obj2.object(); + } while (obj2 != null); + } + return current; + } + + private void process() { + for (Node usage : new ArrayList<Node>(node.usages())) { + op.beforeUpdate(node, usage); + if (!usage.isDeleted()) { + op.collectField(node, usage, fields); } } } @@ -224,89 +266,120 @@ @Override protected void run(Graph graph) { -// if (compilation.method.holder().name().contains("jnt")) { - for (Node node : graph.getNodes()) { - if (node instanceof NewInstance && ((NewInstance) node).instanceClass().isResolved()) { - Set<Node> exits = new HashSet<Node>(); - Set<Invoke> invokes = new HashSet<Invoke>(); - int iterations = 0; +// if (!compilation.method.holder().name().contains("jnt")) { +// return; +// } +// if (true) return; + for (Node node : graph.getNodes()) { + EscapeOp op = node.lookup(EscapeOp.class); + if (op != null && op.canAnalyze(node)) { + Set<Node> exits = new HashSet<Node>(); + Set<Invoke> invokes = new HashSet<Invoke>(); + int iterations = 0; - int weight; - do { - weight = analyse(node, exits, invokes); -// TTY.print("%d: new value: %d %s, weight %d, escapes at ", iterations, node.id(), node.shortName(), weight); -// for (Node n : exits) { -// TTY.print("%d %s, ", n.id(), n.shortName()); -// } -// for (Node n : invokes) { -// TTY.print("%d %s, ", n.id(), n.shortName()); -// } -// TTY.println(); - if (exits.size() != 0) { - TTY.println("####### escaping object: %d in %s", node.id(), compilation.method); - break; + int weight; + int minimumWeight = GraalOptions.ForcedInlineEscapeWeight; + do { + weight = analyze(op, node, exits, invokes); + if (exits.size() != 0) { + if (GraalOptions.TraceEscapeAnalysis) { + TTY.println("####### escaping object: %d %s in %s", node.id(), node.shortName(), compilation.method); + TTY.print("%d: new value: %d %s, weight %d, escapes at ", iterations, node.id(), node.shortName(), weight); + for (Node n : exits) { + TTY.print("%d %s, ", n.id(), n.shortName()); + } + for (Node n : invokes) { + TTY.print("%d %s, ", n.id(), n.shortName()); + } + TTY.println(); } - if (invokes.size() == 0) { - TTY.println("!!!!!!!! non-escaping object: %d in %s", node.id(), compilation.method); - new EscapementFixup().apply(graph, node); - break; + break; + } + if (invokes.size() == 0) { + if (GraalOptions.TraceEscapeAnalysis) { + TTY.println("!!!!!!!! non-escaping object: %d %s in %s", node.id(), node.shortName(), compilation.method); } - for (Invoke invoke : invokes) { - new InliningPhase(compilation, ir, invoke, GraalOptions.TraceInlining).apply(graph); + new EscapementFixup(op, graph, node).apply(); + new PhiSimplifier(graph); + break; + } + if (weight < minimumWeight) { + if (GraalOptions.TraceEscapeAnalysis) { + TTY.println("####### possibly escaping object: %d in %s (insufficient weight for inlining)", node.id(), compilation.method); } - exits.clear(); - invokes.clear(); - } while (weight >= GraalOptions.ForcedInlineEscapeWeight && iterations++ < 15); - } + break; + } + new InliningPhase(compilation, ir, invokes, GraalOptions.TraceInlining).apply(graph); + exits.clear(); + invokes.clear(); + } while (iterations++ < 3); } -// } + } } - private int analyse(Node node, Collection<Node> exits, Collection<Invoke> invokes) { + private int analyze(EscapeOp op, Node node, Collection<Node> exits, Collection<Invoke> invokes) { int weight = 0; for (Node usage : node.usages()) { - if (usage instanceof IsNonNull) { - IsNonNull x = (IsNonNull) usage; - weight++; - } else if (usage instanceof IsType) { - IsType x = (IsType) usage; - weight++; - } else if (usage instanceof FrameState) { - FrameState x = (FrameState) usage; - } else if (usage instanceof StoreField) { - StoreField x = (StoreField) usage; - if (x.value() == node) { - exits.add(x); + boolean escapes = op.escape(node, usage); + if (escapes) { + if (usage instanceof FrameState) { + // nothing to do... + } else if (usage instanceof Invoke) { + invokes.add((Invoke) usage); } else { - weight++; + exits.add(usage); + if (!GraalOptions.TraceEscapeAnalysis) { + break; + } } - } else if (usage instanceof AccessMonitor) { - AccessMonitor x = (AccessMonitor) usage; - weight++; - } else if (usage instanceof LoadField) { - LoadField x = (LoadField) usage; + } else { weight++; - } else if (usage instanceof RegisterFinalizer) { - RegisterFinalizer x = (RegisterFinalizer) usage; - weight++; - } else if (usage instanceof Invoke) { - Invoke x = (Invoke) usage; - invokes.add(x); - } else { - exits.add(usage); } } return weight; } + public static class EscapeField { - public static enum Escape { - NewValue, - DoesNotEscape, - DoesEscape + private String name; + private Object representation; + private CiKind kind; + + public EscapeField(String name, Object representation, CiKind kind) { + this.name = name; + this.representation = representation; + this.kind = kind; + } + + public String name() { + return name; + } + + public Object representation() { + return representation; + } + + public CiKind kind() { + return kind; + } + + @Override + public String toString() { + return name(); + } } public static interface EscapeOp extends Op { - Escape escape(Node node, Node value); + + boolean canAnalyze(Node node); + + boolean escape(Node node, Node usage); + + void beforeUpdate(Node node, Node usage); + + void collectField(Node node, Node usage, Map<Object, EscapeField> fields); + + void updateState(Node node, Node current, Map<Object, EscapeField> fields, Map<EscapeField, Node> fieldState); + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Mon Jun 27 17:13:33 2011 +0200 @@ -49,12 +49,12 @@ private int inliningSize; private final boolean trace; - private final Invoke hint; + private final Collection<Invoke> hints; - public InliningPhase(GraalCompilation compilation, IR ir, Invoke hint, boolean trace) { + public InliningPhase(GraalCompilation compilation, IR ir, Collection<Invoke> hints, boolean trace) { this.compilation = compilation; this.ir = ir; - this.hint = hint; + this.hints = hints; this.trace = trace; } @@ -74,8 +74,8 @@ float ratio = GraalOptions.MaximumInlineRatio; inliningSize = compilation.method.codeSize(); - if (hint != null) { - newInvokes.add(hint); + if (hints != null) { + newInvokes.addAll(hints); } else { for (Invoke invoke : graph.getNodes(Invoke.class)) { newInvokes.add(invoke); @@ -269,7 +269,7 @@ private boolean checkStaticSizeConditions(RiMethod method, Invoke invoke) { int maximumSize = GraalOptions.MaximumInlineSize; - if (invoke == hint) { + if (hints != null && hints.contains(invoke)) { maximumSize = GraalOptions.MaximumFreqInlineSize; } if (method.codeSize() > maximumSize) { @@ -293,7 +293,7 @@ maximumSize = GraalOptions.MaximumInlineSize; } } - if (invoke == hint) { + if (hints != null && hints.contains(invoke)) { maximumSize = GraalOptions.MaximumFreqInlineSize; } if (method.codeSize() > maximumSize) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Wed Jun 22 11:56:15 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Mon Jun 27 17:13:33 2011 +0200 @@ -140,15 +140,22 @@ this.instructions = instructions; } + public static void iteratePostOrder(List<Block> blocks, BlockClosure closure) { + ArrayList<Block> startBlocks = new ArrayList<Block>(); + for (Block block : blocks) { + if (block.getPredecessors().size() == 0) { + startBlocks.add(block); + } + } + iteratePostOrder(blocks, closure, startBlocks.toArray(new Block[startBlocks.size()])); + } - public static void iteratePostOrder(List<Block> blocks, BlockClosure closure) { + public static void iteratePostOrder(List<Block> blocks, BlockClosure closure, Block... startBlocks) { BitMap visited = new BitMap(blocks.size()); LinkedList<Block> workList = new LinkedList<Block>(); - for (Block block : blocks) { - if (block.getPredecessors().size() == 0) { - workList.add(block); - visited.set(block.blockID()); - } + for (Block block : startBlocks) { + workList.add(block); + visited.set(block.blockID()); } while (!workList.isEmpty()) { @@ -161,7 +168,6 @@ boolean delay = false; for (Block pred : succ.getPredecessors()) { if (!visited.get(pred.blockID()) && !(pred.lastNode instanceof LoopEnd)) { - TTY.println("missing pred: %d", pred.blockID()); delay = true; break; }