# HG changeset patch # User Lukas Stadler # Date 1309960889 -7200 # Node ID a5e5ef264dbfed16e82ae79bb715cf4cb3da6991 # Parent 94e903d0cf3b27c1c2c5005720cc614d4a2bbfef new escape analysis mechanism: don't use blocks during iteration, VirtualObjectFields merged with phis diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Wed Jul 06 16:01:29 2011 +0200 @@ -26,6 +26,7 @@ import static java.lang.reflect.Modifier.*; import java.util.*; +import java.util.Map.Entry; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.alloc.Interval.*; @@ -1837,117 +1838,162 @@ } } - CiValue toCiValue(int opId, Value value) { - if (value instanceof VirtualObject) { - return toCiVirtualObject(opId, (VirtualObject) value); - } else if (value != null && value.operand() != CiValue.IllegalValue) { - CiValue operand = value.operand(); - Constant con = null; - if (value instanceof Constant) { - con = (Constant) value; - } + private class DebugFrameBuilder { + + private final FrameState topState; + private final int opId; + private final BitMap frameRefMap; - assert con == null || operand.isVariable() || operand.isConstant() || operand.isIllegal() : "Constant instructions have only constant operands (or illegal if constant is optimized away)"; + private HashMap virtualObjects; + + public DebugFrameBuilder(FrameState topState, int opId, BitMap frameRefMap) { + this.topState = topState; + this.opId = opId; + this.frameRefMap = frameRefMap; + } - if (operand.isVariable()) { - OperandMode mode = OperandMode.Input; - LIRBlock block = blockForId(opId); - if (block.numberOfSux() == 1 && opId == block.lastLirInstructionId()) { - // generating debug information for the last instruction of a block. - // if this instruction is a branch, spill moves are inserted before this branch - // and so the wrong operand would be returned (spill moves at block boundaries are not - // considered in the live ranges of intervals) - // Solution: use the first opId of the branch target block instead. - final LIRInstruction instr = block.lir().instructionsList().get(block.lir().instructionsList().size() - 1); - if (instr instanceof LIRBranch) { - if (block.liveOut.get(operandNumber(operand))) { - opId = block.suxAt(0).firstLirInstructionId(); - mode = OperandMode.Output; - } - } + private CiValue toCiValue(Value value) { + if (value instanceof VirtualObject) { + if (virtualObjects == null) { + virtualObjects = new HashMap(); + } + VirtualObject obj = (VirtualObject) value; + CiVirtualObject ciObj = virtualObjects.get(value); + if (ciObj == null) { + ciObj = CiVirtualObject.get(obj.type(), null, value.id()); + virtualObjects.put(obj, ciObj); + } + return ciObj; + } else if (value != null && value.operand() != CiValue.IllegalValue) { + CiValue operand = value.operand(); + Constant con = null; + if (value instanceof Constant) { + con = (Constant) value; } - // Get current location of operand - // The operand must be live because debug information is considered when building the intervals - // if the interval is not live, colorLirOperand will cause an assert on failure - operand = colorLirOperand((CiVariable) operand, opId, mode); - assert !hasCall(opId) || operand.isStackSlot() || !isCallerSave(operand) : "cannot have caller-save register operands at calls"; - return operand; - } else if (operand.isRegister()) { - assert false : "must not reach here"; - return operand; + assert con == null || operand.isVariable() || operand.isConstant() || operand.isIllegal() : "Constant instructions have only constant operands (or illegal if constant is optimized away)"; + + int tempOpId = this.opId; + if (operand.isVariable()) { + OperandMode mode = OperandMode.Input; + LIRBlock block = blockForId(tempOpId); + if (block.numberOfSux() == 1 && tempOpId == block.lastLirInstructionId()) { + // generating debug information for the last instruction of a block. + // if this instruction is a branch, spill moves are inserted before this branch + // and so the wrong operand would be returned (spill moves at block boundaries are not + // considered in the live ranges of intervals) + // Solution: use the first opId of the branch target block instead. + final LIRInstruction instr = block.lir().instructionsList().get(block.lir().instructionsList().size() - 1); + if (instr instanceof LIRBranch) { + if (block.liveOut.get(operandNumber(operand))) { + tempOpId = block.suxAt(0).firstLirInstructionId(); + mode = OperandMode.Output; + } + } + } + + // Get current location of operand + // The operand must be live because debug information is considered when building the intervals + // if the interval is not live, colorLirOperand will cause an assert on failure + operand = colorLirOperand((CiVariable) operand, tempOpId, mode); + assert !hasCall(tempOpId) || operand.isStackSlot() || !isCallerSave(operand) : "cannot have caller-save register operands at calls"; + return operand; + } else if (operand.isRegister()) { + assert false : "must not reach here"; + return operand; + } else { + assert value instanceof Constant; + assert operand.isConstant() : "operand must be constant"; + return operand; + } } else { - assert value instanceof Constant; - assert operand.isConstant() : "operand must be constant"; - return operand; + // return a dummy value because real value not needed + return CiValue.IllegalValue; } - } else { - // return a dummy value because real value not needed - return CiValue.IllegalValue; } - } - private CiVirtualObject toCiVirtualObject(int opId, VirtualObject obj) { - RiType type = obj.type(); - EscapeField[] escapeFields = obj.fields(); - CiValue[] values = new CiValue[escapeFields.length]; - int valuesFilled = 0; + private CiFrame computeFrameForState(FrameState state) { + CiValue[] values = new CiValue[state.valuesSize() + state.locksSize()]; + int valueIndex = 0; + + for (int i = 0; i < state.valuesSize(); i++) { + values[valueIndex++] = toCiValue(state.valueAt(i)); + } - VirtualObject current = obj; - do { - boolean found = false; - for (int i = 0; i < escapeFields.length; i++) { - if (escapeFields[i].representation() == current.field().representation()) { - if (values[i] == null) { - values[i] = toCiValue(opId, current.input()); - valuesFilled++; + for (int i = 0; i < state.locksSize(); i++) { + if (compilation.runtime.sizeOfBasicObjectLock() != 0) { + CiStackSlot monitorAddress = frameMap.toMonitorBaseStackAddress(i); + values[valueIndex++] = monitorAddress; + CiStackSlot objectAddress = frameMap.toMonitorObjectStackAddress(i); + frameRefMap.set(objectAddress.index()); + } else { + Value lock = state.lockAt(i); + if (lock.isConstant() && compilation.runtime.asJavaClass(lock.asConstant()) != null) { + // lock on class for synchronized static method + values[valueIndex++] = lock.asConstant(); + } else { + values[valueIndex++] = toCiValue(lock); } - found = true; - break; } } - assert found : type + "." + current.field() + " not found"; - current = current.object(); - } while (current != null && valuesFilled < values.length); - - for (int i = 0; i < escapeFields.length; i++) { - assert values[i] != null : type + "." + escapeFields[i]; - } - - return CiVirtualObject.get(type, values, obj.id()); - } - - CiFrame computeFrameForState(FrameState state, int opId, BitMap frameRefMap) { - CiValue[] values = new CiValue[state.valuesSize() + state.locksSize()]; - int valueIndex = 0; - - for (int i = 0; i < state.valuesSize(); i++) { - values[valueIndex++] = toCiValue(opId, state.valueAt(i)); + CiFrame caller = null; + if (state.outerFrameState() != null) { + caller = computeFrameForState(state.outerFrameState()); + } + return new CiFrame(caller, state.method, state.bci, state.rethrowException(), values, state.localsSize(), state.stackSize(), state.locksSize()); } - for (int i = 0; i < state.locksSize(); i++) { - if (compilation.runtime.sizeOfBasicObjectLock() != 0) { - CiStackSlot monitorAddress = frameMap.toMonitorBaseStackAddress(i); - values[valueIndex++] = monitorAddress; - assert frameRefMap != null; - CiStackSlot objectAddress = frameMap.toMonitorObjectStackAddress(i); -// LIRDebugInfo.setBit(frameRefMap, objectAddress.index()); - frameRefMap.set(objectAddress.index()); - } else { - Value lock = state.lockAt(i); - if (lock.isConstant() && compilation.runtime.asJavaClass(lock.asConstant()) != null) { - // lock on class for synchronized static method - values[valueIndex++] = lock.asConstant(); - } else { - values[valueIndex++] = toCiValue(opId, lock); - } + public CiFrame build() { + CiFrame frame = computeFrameForState(topState); + + if (virtualObjects != null) { + // collect all VirtualObjectField instances: + HashMap objectStates = new HashMap(); + FrameState current = topState; + do { + for (Node n : current.inputs().variablePart()) { + VirtualObjectField field = (VirtualObjectField) n; + // null states occur for objects with 0 fields + if (field != null && !objectStates.containsKey(field.object())) { + objectStates.put(field.object(), field); + } + } + current = current.outerFrameState(); + } while (current != null); + // fill in the CiVirtualObject values: + // during this process new CiVirtualObjects might be discovered, so repeat until no more changes occur. + boolean changed; + do { + changed = false; + HashMap virtualObjectsCopy = new HashMap(virtualObjects); + for (Entry entry : virtualObjectsCopy.entrySet()) { + if (entry.getValue().values() == null) { + VirtualObject vobj = entry.getKey(); + CiValue[] values = new CiValue[vobj.fields().length]; + entry.getValue().setValues(values); + if (vobj.fields().length > 0) { + changed = true; + FloatingNode currentField = objectStates.get(vobj); + assert currentField != null; + do { + if (currentField instanceof VirtualObjectField) { + int index = ((VirtualObjectField) currentField).index(); + if (values[index] == null) { + values[index] = toCiValue(((VirtualObjectField) currentField).input()); + } + currentField = ((VirtualObjectField) currentField).lastState(); + } else { + assert currentField instanceof Phi : currentField; + currentField = (FloatingNode) ((Phi) currentField).valueAt(0); + } + } while (currentField != null); + } + } + } + } while (changed); } + return frame; } - CiFrame caller = null; - if (state.outerFrameState() != null) { - caller = computeFrameForState(state.outerFrameState(), opId, frameRefMap); - } - return new CiFrame(caller, state.method, state.bci, state.rethrowException(), values, state.localsSize(), state.stackSize(), state.locksSize()); } private void computeDebugInfo(IntervalWalker iw, LIRInstruction op) { @@ -1983,7 +2029,7 @@ if (GraalOptions.TraceLinearScanLevel >= 3) { TTY.println("creating debug information at opId %d", opId); } - return computeFrameForState(state, opId, frameRefMap); + return new DebugFrameBuilder(state, opId, frameRefMap).build(); } private void assignLocations(List instructions, IntervalWalker iw) { diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Wed Jul 06 16:01:29 2011 +0200 @@ -109,7 +109,7 @@ return; } - printer = new IdealGraphPrinter(stream); + printer = new IdealGraphPrinter(new BufferedOutputStream(stream)); if (GraalOptions.OmitDOTFrameStates) { printer.addOmittedClass(FrameState.class); } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Jul 06 16:01:29 2011 +0200 @@ -42,6 +42,7 @@ import com.oracle.max.graal.compiler.lir.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.value.*; +import com.oracle.max.graal.compiler.value.FrameState.ValueProcedure; import com.oracle.max.graal.graph.*; import com.sun.cri.bytecode.Bytecodes.MemoryBarriers; import com.sun.cri.ci.*; @@ -480,6 +481,13 @@ emitInstanceOf((TypeCheck) node, trueSuccessor, falseSuccessor, info); } else if (node instanceof NotInstanceOf) { emitInstanceOf((TypeCheck) node, falseSuccessor, trueSuccessor, info); + } else if (node instanceof Constant) { + CiConstant constant = ((Constant) node).asConstant(); + assert constant.kind == CiKind.Boolean; + LIRBlock target = constant.asBoolean() ? trueSuccessor : falseSuccessor; + if (target != null) { + lir.jump(target); + } } else { throw Util.unimplemented(node.toString()); } @@ -1609,57 +1617,25 @@ } } - protected void walkState(Node x, FrameState state) { + protected void walkState(final Node x, FrameState state) { if (state == null) { return; } - walkState(x, state.outerFrameState()); - - for (int index = 0; index < state.stackSize(); index++) { - Value value = state.stackAt(index); - if (value != x) { - walkStateValue(value); - } - } - for (int index = 0; index < state.localsSize(); index++) { - final Value value = state.localAt(index); - if (value != null) { - if (!(value instanceof Phi && ((Phi) value).isDead())) { - walkStateValue(value); + state.forEachLiveStateValue(new ValueProcedure() { + public void doValue(Value value) { + if (value == x) { + // nothing to do, will be visited shortly + } else if (value instanceof Phi && !((Phi) value).isDead()) { + // phi's are special + operandForPhi((Phi) value); + } else if (value.operand().isIllegal()) { + // instruction doesn't have an operand yet + CiValue operand = makeOperand(value); + assert operand.isLegal() : "must be evaluated now"; } } - } - } - - private void walkStateValue(Value value) { - if (value != null) { - 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()) { - // instruction doesn't have an operand yet - CiValue operand = makeOperand(value); - assert operand.isLegal() : "must be evaluated now"; - } - } - } - - private void walkVirtualObject(VirtualObject value) { - if (value.input() instanceof Phi) { - assert !((Phi) value.input()).isDead(); - } - HashSet fields = new HashSet(); - VirtualObject obj = value; - do { - if (!fields.contains(obj.field().representation())) { - fields.add(obj.field().representation()); - walkStateValue(obj.input()); - } - obj = obj.object(); - } while (obj != null); + }); } protected LIRDebugInfo stateFor(Value x) { diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IsNonNull.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IsNonNull.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IsNonNull.java Wed Jul 06 16:01:29 2011 +0200 @@ -68,7 +68,7 @@ */ public IsNonNull(Value object, Graph graph) { super(CiKind.Object, INPUT_COUNT, SUCCESSOR_COUNT, graph); - assert object == null || object.kind == CiKind.Object; + assert object == null || object.kind == CiKind.Object : object; setObject(object); } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewArray.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewArray.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewArray.java Wed Jul 06 16:01:29 2011 +0200 @@ -36,8 +36,6 @@ */ public abstract class NewArray extends FixedNodeWithNext { - private static final EscapeOp ESCAPE = new NewArrayEscapeOp(); - private static final int INPUT_COUNT = 1; private static final int INPUT_LENGTH = 0; @@ -109,7 +107,7 @@ return super.lookup(clazz); } - private static class NewArrayEscapeOp implements EscapeOp { + private static final EscapeOp ESCAPE = new EscapeOp() { @Override public boolean canAnalyze(Node node) { @@ -207,31 +205,27 @@ } @Override - public EscapeField updateState(Node node, Node current, Map fields, Map fieldState) { + public int updateState(Node node, Node current, Map fieldIndex, Value[] 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) { - x.replaceAtUsages(fieldState.get(field)); + x.replaceAtUsages(fieldState[index]); assert x.usages().size() == 0; x.replaceAndDelete(x.next()); } } else if (current instanceof StoreIndexed) { StoreIndexed x = (StoreIndexed) current; if (x.array() == node) { - fieldState.put(field, x.value()); + fieldState[index] = x.value(); assert x.usages().size() == 0; - WriteMemoryCheckpointNode checkpoint = new WriteMemoryCheckpointNode(x.graph()); - checkpoint.setStateAfter(x.stateAfter()); - checkpoint.setNext(x.next()); - x.replaceAndDelete(checkpoint); - return field; + x.replaceAndDelete(x.next()); + return index; } } } - return null; + return -1; } - } + }; } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java Wed Jul 06 16:01:29 2011 +0200 @@ -36,7 +36,6 @@ * The {@code NewInstance} instruction represents the allocation of an instance class object. */ public final class NewInstance extends FixedNodeWithNext { - private static final EscapeOp ESCAPE = new NewInstanceEscapeOp(); private static final int INPUT_COUNT = 0; private static final int SUCCESSOR_COUNT = 0; @@ -109,7 +108,7 @@ return super.lookup(clazz); } - private static class NewInstanceEscapeOp implements EscapeOp { + private static final EscapeOp ESCAPE = new EscapeOp() { @Override public boolean canAnalyze(Node node) { @@ -195,31 +194,27 @@ } @Override - public EscapeField updateState(Node node, Node current, Map fields, Map fieldState) { + public int updateState(Node node, Node current, Map fieldIndex, Value[] fieldState) { if (current instanceof AccessField) { - EscapeField field = fields.get(((AccessField) current).field()); - if (current instanceof LoadField) { - LoadField x = (LoadField) current; - if (x.object() == node) { - assert fieldState.get(field) != null : field + ", " + ((AccessField) current).field() + ((AccessField) current).field().hashCode(); - x.replaceAtUsages(fieldState.get(field)); + if (((AccessField) current).object() == node) { + Integer field = fieldIndex.get(((AccessField) current).field()); + assert field != null : ((AccessField) current).field() + " " + ((AccessField) current).field().hashCode(); + if (current instanceof LoadField) { + LoadField x = (LoadField) current; + assert fieldState[field] != null : field + ", " + ((AccessField) current).field() + ((AccessField) current).field().hashCode(); + x.replaceAtUsages(fieldState[field]); assert x.usages().size() == 0; x.replaceAndDelete(x.next()); - } - } else if (current instanceof StoreField) { - StoreField x = (StoreField) current; - if (x.object() == node) { - fieldState.put(field, x.value()); + } else if (current instanceof StoreField) { + StoreField x = (StoreField) current; + fieldState[field] = x.value(); assert x.usages().size() == 0; - WriteMemoryCheckpointNode checkpoint = new WriteMemoryCheckpointNode(x.graph()); - checkpoint.setStateAfter(x.stateAfter()); - checkpoint.setNext(x.next()); - x.replaceAndDelete(checkpoint); + x.replaceAndDelete(x.next()); return field; } } } - return null; + return -1; } - } + }; } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Wed Jul 06 16:01:29 2011 +0200 @@ -79,7 +79,7 @@ public boolean verify() { assertTrue(merge() != null); if (!isDead()) { - assertTrue(merge().phiPredecessorCount() == valueCount()); + assertTrue(merge().phiPredecessorCount() == valueCount(), merge().phiPredecessorCount() + "==" + valueCount()); } return true; } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/VirtualObject.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/VirtualObject.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/VirtualObject.java Wed Jul 06 16:01:29 2011 +0200 @@ -33,9 +33,7 @@ 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 INPUT_COUNT = 0; private static final int SUCCESSOR_COUNT = 0; @@ -49,48 +47,13 @@ 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); - } - - private 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 EscapeField[] fields; 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, Value input, EscapeField field, RiType type, EscapeField[] fields, Graph graph) { + public VirtualObject(RiType type, EscapeField[] fields, Graph graph) { super(CiKind.Int, INPUT_COUNT, SUCCESSOR_COUNT, graph); - this.field = field; this.type = type; this.fields = fields; - setObject(object); - setInput(input); - } - - public EscapeField field() { - return field; } public RiType type() { @@ -110,23 +73,22 @@ public Map getDebugProperties() { Map properties = super.getDebugProperties(); properties.put("type", type); - properties.put("field", field); return properties; } @Override public String shortName() { - return "VirtualObject " + field.name(); + return "VirtualObject " + type.name(); } @Override public void print(LogStream out) { - out.print(object()).print(".").print(field.name()).print("=").print(input()); + out.print("virtualobject ").print(type.name()); } @Override public Node copy(Graph into) { - VirtualObject x = new VirtualObject(null, null, field, type, fields, into); + VirtualObject x = new VirtualObject(type, fields, into); return x; } } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/VirtualObjectField.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/VirtualObjectField.java Wed Jul 06 16:01:29 2011 +0200 @@ -0,0 +1,130 @@ +/* + * 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.graph.*; +import com.sun.cri.ci.*; + + +public class VirtualObjectField extends FloatingNode { + + private static final int INPUT_COUNT = 3; + private static final int INPUT_OBJECT = 0; + private static final int INPUT_LAST_STATE = 1; + private static final int INPUT_INPUT = 2; + + 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 virtual object instance. + */ + public VirtualObject object() { + return (VirtualObject) inputs().get(super.inputCount() + INPUT_OBJECT); + } + + private VirtualObject setObject(VirtualObject n) { + return (VirtualObject) inputs().set(super.inputCount() + INPUT_OBJECT, n); + } + + /** + * The instruction that specifies the old state of the virtual object. + */ + public FloatingNode lastState() { + return (FloatingNode) inputs().get(super.inputCount() + INPUT_LAST_STATE); + } + + private FloatingNode setLastState(FloatingNode n) { + return (FloatingNode) inputs().set(super.inputCount() + INPUT_LAST_STATE, 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 int index; + + /** + * Constructs a new ArrayLength instruction. + * @param array the instruction producing the array + * @param newFrameState the state after executing this instruction + */ + public VirtualObjectField(VirtualObject object, FloatingNode lastState, Value input, int index, Graph graph) { + super(CiKind.Int, INPUT_COUNT, SUCCESSOR_COUNT, graph); + this.index = index; + setObject(object); + setLastState(lastState); + setInput(input); + } + + public int index() { + return index; + } + + @Override + public void accept(ValueVisitor v) { + // nothing to do... + } + + @Override + public Map getDebugProperties() { + Map properties = super.getDebugProperties(); + properties.put("index", index); + return properties; + } + + @Override + public String shortName() { + return "VirtualObjectField " + object().fields()[index].name(); + } + + @Override + public void print(LogStream out) { + out.print(object()).print(".").print(object().fields()[index].name()).print("=").print(input()); + } + + @Override + public Node copy(Graph into) { + VirtualObjectField x = new VirtualObjectField(null, null, null, index, into); + return x; + } +} diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Wed Jul 06 16:01:29 2011 +0200 @@ -99,29 +99,29 @@ endNode.replaceAndDelete(loop.next()); loop.delete(); } - } else if (node instanceof Merge) { - for (Node n : node.usages()) { - if (n instanceof Phi) { - Phi phi = (Phi) n; - if (phi.usages().size() == 1 && phi.usages().get(0) instanceof VirtualObject) { - // (tw) This VirtualObject instance is implicitely dead, because the CFG to it (i.e. the store that produced it) is dead! => fix this in escape analysis - VirtualObject virtualObject = (VirtualObject) phi.usages().get(0); - virtualObject.replaceAndDelete(virtualObject.object()); - } - } - } - } - - - if (IdentifyBlocksPhase.isFixed(node)) { - for (Node n : new ArrayList(node.usages())) { - if (n instanceof VirtualObject) { - // (tw) This VirtualObject instance is implicitely dead, because the CFG to it (i.e. the - // store that produced it) is dead! => fix this in Escape analysis - VirtualObject virtualObject = (VirtualObject) n; - virtualObject.replaceAndDelete(virtualObject.object()); - } - } +// } else if (node instanceof Merge) { +// for (Node n : node.usages()) { +// if (n instanceof Phi) { +// Phi phi = (Phi) n; +// if (phi.usages().size() == 1 && phi.usages().get(0) instanceof VirtualObject) { +// // (tw) This VirtualObject instance is implicitely dead, because the CFG to it (i.e. the store that produced it) is dead! => fix this in escape analysis +// VirtualObject virtualObject = (VirtualObject) phi.usages().get(0); +// virtualObject.replaceAndDelete(virtualObject.object()); +// } +// } +// } +// } +// +// +// if (IdentifyBlocksPhase.isFixed(node)) { +// for (Node n : new ArrayList(node.usages())) { +// if (n instanceof VirtualObject) { +// // (tw) This VirtualObject instance is implicitely dead, because the CFG to it (i.e. the +// // store that produced it) is dead! => fix this in Escape analysis +// VirtualObject virtualObject = (VirtualObject) n; +// virtualObject.replaceAndDelete(virtualObject.object()); +// } +// } } } } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Wed Jul 06 16:01:29 2011 +0200 @@ -23,7 +23,6 @@ package com.oracle.max.graal.compiler.phases; import java.util.*; -import java.util.Map.Entry; import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; @@ -40,24 +39,279 @@ public class EscapeAnalysisPhase extends Phase { + public interface MergeableState { + T clone(); + void merge(Merge merge, Collection withStates); + void loopBegin(LoopBegin loopBegin); + void loopEnd(LoopEnd loopEnd, T loopEndState); + } - public static class BlockExitState { - public final Map fieldState; - public VirtualObject obj; + public abstract static class PostOrderNodeIterator> { + + private final NodeBitMap visitedEnds; + private final Deque nodeQueue; + private final HashMap nodeStates; + private final FixedNode start; + + protected T state; + + public PostOrderNodeIterator(FixedNode start, T initialState) { + visitedEnds = start.graph().createNodeBitMap(); + nodeQueue = new ArrayDeque(); + nodeStates = new HashMap(); + this.start = start; + this.state = initialState; + } + + public void apply(FixedNode start) { + FixedNode current = start; + + do { + if (current instanceof Invoke) { + invoke((Invoke) current); + queueSuccessors(current); + current = nextQueuedNode(); + } else if (current instanceof LoopBegin) { + state.loopBegin((LoopBegin) current); + nodeStates.put(current, state.clone()); + loopBegin((LoopBegin) current); + current = ((LoopBegin) current).next(); + assert current != null; + } else if (current instanceof LoopEnd) { + T loopBeginState = nodeStates.get(((LoopEnd) current).loopBegin()); + if (loopBeginState != null) { + loopBeginState.loopEnd((LoopEnd) current, state); + } + loopEnd((LoopEnd) current); + current = nextQueuedNode(); + } else if (current instanceof Merge) { + merge((Merge) current); + current = ((Merge) current).next(); + assert current != null; + } else if (current instanceof FixedNodeWithNext) { + FixedNode next = ((FixedNodeWithNext) current).next(); + node(current); + current = next; + assert current != null; + } else if (current instanceof EndNode) { + end((EndNode) current); + queueMerge((EndNode) current); + current = nextQueuedNode(); + } else if (current instanceof Deoptimize) { + deoptimize((Deoptimize) current); + current = nextQueuedNode(); + } else if (current instanceof Return) { + returnNode((Return) current); + current = nextQueuedNode(); + } else if (current instanceof Unwind) { + unwind((Unwind) current); + current = nextQueuedNode(); + } else if (current instanceof ControlSplit) { + controlSplit((ControlSplit) current); + queueSuccessors(current); + current = nextQueuedNode(); + } else { + assert false : current.shortName(); + } + } while(current != null); + } + + private void queueSuccessors(FixedNode x) { + nodeStates.put(x, state); + for (Node node : x.successors()) { + if (node != null) { + nodeQueue.addFirst((FixedNode) node); + } + } + } - public BlockExitState() { - this.fieldState = new HashMap(); + private FixedNode nextQueuedNode() { + int maxIterations = nodeQueue.size(); + while (maxIterations-- > 0) { + FixedNode node = nodeQueue.removeFirst(); + if (node instanceof Merge) { + Merge merge = (Merge) node; + state = nodeStates.get(merge.endAt(0)).clone(); + ArrayList states = new ArrayList(merge.endCount() - 1); + for (int i = 1; i < merge.endCount(); i++) { + T other = nodeStates.get(merge.endAt(i)); + assert other != null; + states.add(other); + } + state.merge(merge, states); + return merge; + } else { + assert node.predecessors().size() == 1; + state = nodeStates.get(node.predecessors().get(0)).clone(); + return node; + } + } + return null; + } + + private void queueMerge(EndNode end) { + assert !visitedEnds.isMarked(end); + assert !nodeStates.containsKey(end); + nodeStates.put(end, state); + visitedEnds.mark(end); + Merge merge = end.merge(); + boolean endsVisited = true; + for (int i = 0; i < merge.endCount(); i++) { + if (!visitedEnds.isMarked(merge.endAt(i))) { + endsVisited = false; + break; + } + } + if (endsVisited) { + nodeQueue.add(merge); + } + } + + protected abstract void node(FixedNode node); + + protected void end(EndNode endNode) { + node(endNode); + } + + protected void merge(Merge merge) { + node(merge); + } + + protected void loopBegin(LoopBegin loopBegin) { + node(loopBegin); + } + + protected void loopEnd(LoopEnd loopEnd) { + node(loopEnd); + } + + protected void deoptimize(Deoptimize deoptimize) { + node(deoptimize); + } + + protected void controlSplit(ControlSplit controlSplit) { + node(controlSplit); + } + + protected void returnNode(Return returnNode) { + node(returnNode); + } + + protected void invoke(Invoke invoke) { + node(invoke); + } + + protected void unwind(Unwind unwind) { + node(unwind); } } + public static class BlockExitState implements MergeableState { + public final Value[] fieldState; + public final VirtualObject virtualObject; + public FloatingNode virtualObjectField; + + public BlockExitState(EscapeField[] fields, VirtualObject virtualObject) { + this.fieldState = new Value[fields.length]; + this.virtualObject = virtualObject; + this.virtualObjectField = null; + for (int i = 0; i < fields.length; i++) { + fieldState[i] = Constant.defaultForKind(fields[i].kind(), virtualObject.graph()); + virtualObjectField = new VirtualObjectField(virtualObject, virtualObjectField, fieldState[i], i, virtualObject.graph()); + } + } + + public BlockExitState(BlockExitState state) { + this.fieldState = state.fieldState.clone(); + this.virtualObject = state.virtualObject; + this.virtualObjectField = state.virtualObjectField; + } + + public void updateField(int fieldIndex) { + virtualObjectField = new VirtualObjectField(virtualObject, virtualObjectField, fieldState[fieldIndex], fieldIndex, virtualObject.graph()); + } + + @Override + public BlockExitState clone() { + return new BlockExitState(this); + } + + @Override + public void merge(Merge merge, Collection withStates) { + Phi vobjPhi = null; + Phi[] valuePhis = new Phi[fieldState.length]; + for (BlockExitState other : withStates) { + if (virtualObjectField != other.virtualObjectField && vobjPhi == null) { + vobjPhi = new Phi(CiKind.Illegal, merge, virtualObject.graph()); + vobjPhi.makeDead(); + vobjPhi.addInput(virtualObjectField); + virtualObjectField = vobjPhi; + } + for (int i2 = 0; i2 < fieldState.length; i2++) { + if (fieldState[i2] != other.fieldState[i2] && valuePhis[i2] == null) { + valuePhis[i2] = new Phi(fieldState[i2].kind, merge, virtualObject.graph()); + valuePhis[i2].addInput(fieldState[i2]); + fieldState[i2] = valuePhis[i2]; + } + } + } + for (BlockExitState other : withStates) { + if (vobjPhi != null) { + vobjPhi.addInput(other.virtualObjectField); + } + for (int i2 = 0; i2 < fieldState.length; i2++) { + if (valuePhis[i2] != null) { + valuePhis[i2].addInput(other.fieldState[i2]); + } + } + } + assert vobjPhi == null || vobjPhi.valueCount() == withStates.size() + 1; + for (int i2 = 0; i2 < fieldState.length; i2++) { + if (valuePhis[i2] != null) { + virtualObjectField = new VirtualObjectField(virtualObject, virtualObjectField, valuePhis[i2], i2, virtualObject.graph()); + assert valuePhis[i2].valueCount() == withStates.size() + 1; + } + } + } + + @Override + public void loopBegin(LoopBegin loopBegin) { + Phi vobjPhi = null; + vobjPhi = new Phi(CiKind.Illegal, loopBegin, virtualObject.graph()); + vobjPhi.makeDead(); + vobjPhi.addInput(virtualObjectField); + virtualObjectField = vobjPhi; + for (int i2 = 0; i2 < fieldState.length; i2++) { + Phi valuePhi = new Phi(fieldState[i2].kind, loopBegin, virtualObject.graph()); + valuePhi.addInput(fieldState[i2]); + fieldState[i2] = valuePhi; + updateField(i2); + } + } + + @Override + public void loopEnd(LoopEnd x, BlockExitState loopEndState) { + while (!(virtualObjectField instanceof Phi)) { + virtualObjectField = ((VirtualObjectField) virtualObjectField).lastState(); + } + ((Phi) virtualObjectField).addInput(loopEndState.virtualObjectField); + assert ((Phi) virtualObjectField).valueCount() == 2; + for (int i2 = 0; i2 < fieldState.length; i2++) { + ((Phi) fieldState[i2]).addInput(loopEndState.fieldState[i2]); + assert ((Phi) fieldState[i2]).valueCount() == 2; + } + } + } + + public class EscapementFixup { private List blocks; - private final Map fields = new HashMap(); + private final Map fields = new HashMap(); private final Map exitStates = new HashMap(); private final EscapeOp op; - private Graph graph; + private final Graph graph; private final Node node; private RiType type; private EscapeField[] escapeFields; @@ -74,217 +328,36 @@ } public void removeAllocation() { - final IdentifyBlocksPhase identifyBlocksPhase = new IdentifyBlocksPhase(true); - identifyBlocksPhase.apply(graph); - blocks = identifyBlocksPhase.getBlocks(); + assert node instanceof FixedNodeWithNext; - final HashMap phis = new HashMap(); - final Block startBlock = identifyBlocksPhase.getNodeToBlock().get(node); - assert startBlock != null; type = ((Value) node).exactType(); escapeFields = op.fields(node); - for (EscapeField field : escapeFields) { - fields.put(field.representation(), field); + for (int i = 0; i < escapeFields.length; i++) { + fields.put(escapeFields[i].representation(), i); } - - Block.iteratePostOrder(blocks, new BlockClosure() { - - public void apply(Block block) { - if (GraalOptions.TraceEscapeAnalysis) { - TTY.println("Block %d", block.blockID()); - } -// for (Node n : block.getInstructions()) { -// TTY.println(" %d %s", n.id(), n.shortName()); -// } -// for (Block b : block.getSuccessors()) { -// TTY.print(" %d", b.blockID()); -// } -// TTY.println(); - - BlockExitState state = new BlockExitState(); - if (/*block == startBlock ||*/ block.getPredecessors().size() == 0) { - state.obj = null; - } else { - List predecessors = block.getPredecessors(); - Set mergedFields = new HashSet(); - - BlockExitState predState = exitStates.get(predecessors.get(0)); - state.obj = predState == null ? null : predState.obj; - - for (int i = 0; i < predecessors.size(); i++) { - BlockExitState exitState = exitStates.get(predecessors.get(i)); - if (exitState == null) { - // (tw) What about an object that is allocated in a loop. We are merging in the values of the old allocation?; Now solved by "if" below. - mergedFields.addAll(fields.values()); - state.obj = null; - break; - } else { - for (EscapeField field : fields.values()) { - if (state.fieldState.get(field) == null) { - state.fieldState.put(field, exitState.fieldState.get(field)); - if (i != 0) { - // We need to merge this field too! - mergedFields.add(field); - } - } else if (state.fieldState.get(field) != exitState.fieldState.get(field)) { - mergedFields.add(field); - } - } - } - } - if (block.firstNode() instanceof LoopBegin) { - if (predState.obj == null) { - state.obj = null; - mergedFields.clear(); - } - } - - 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); - state.obj = new VirtualObject(state.obj, phi, field, type, escapeFields, graph); - } - } - } + final VirtualObject virtual = new VirtualObject(type, escapeFields, graph); + final BlockExitState startState = new BlockExitState(escapeFields, virtual); + if (GraalOptions.TraceEscapeAnalysis || GraalOptions.PrintEscapeAnalysis) { + TTY.println("new virtual object: " + virtual); + } + node.replaceAtUsages(virtual); + final FixedNode next = ((FixedNodeWithNext) node).next(); + node.replaceAndDelete(next); - Node current; - if (block.firstNode() instanceof StartNode) { - current = ((StartNode) block.firstNode()).start(); - } else { - current = block.firstNode(); - } - while (current != block.lastNode()) { - Node next = ((FixedNodeWithNext) current).next(); - FrameState stateAfter = null; - if (current instanceof StateSplit) { - stateAfter = ((StateSplit) current).stateAfter(); - } - if (current == node) { - for (EscapeField field : fields.values()) { - Constant value = Constant.defaultForKind(field.kind(), graph); - state.fieldState.put(field, value); - state.obj = new VirtualObject(state.obj, value, field, type, escapeFields, graph); - } - } else { - EscapeField changedField = op.updateState(node, current, fields, state.fieldState); - if (changedField != null) { - state.obj = new VirtualObject(state.obj, state.fieldState.get(changedField), changedField, type, escapeFields, graph); - } - } - if (stateAfter != null) { - updateFrameState(stateAfter, state.obj); - } - current = next; + new PostOrderNodeIterator(next, startState) { + @Override + protected void node(FixedNode node) { + int changedField = op.updateState(virtual, node, fields, state.fieldState); + if (changedField != -1) { + state.updateField(changedField); } - - if (GraalOptions.TraceEscapeAnalysis) { - TTY.print(" block end state: "); - for (Entry entry : state.fieldState.entrySet()) { - TTY.print("%s->%s ", entry.getKey().name(), entry.getValue()); - } - TTY.println(); - } - exitStates.put(block, state); - } - }); - - for (Entry entry : phis.entrySet()) { - Phi phi = entry.getKey(); - EscapeField field = entry.getValue(); - Block block = identifyBlocksPhase.getNodeToBlock().get(entry.getKey().merge()); - - List predecessors = block.getPredecessors(); - 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)); - if (exitState.fieldState.get(field) != simple) { - simple = null; - break; - } - } - if (simple != null) { - // (tw) Should never be reached, because Phi verification fails here.. - phi.replaceAndDelete(simple); - } 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); + if (!node.isDeleted() && node instanceof StateSplit && ((StateSplit) node).stateAfter() != null) { + if (state.virtualObjectField != null) { + ((StateSplit) node).stateAfter().addVirtualObjectMapping(state.virtualObjectField); } } } - } - // the rest of the usages should be dead frame states... - for (Node usage : new ArrayList(node.usages())) { - if (usage instanceof IsNonNull) { - usage.replaceAndDelete(Constant.forBoolean(true, graph)); - } else if (usage instanceof RegisterFinalizer) { - usage.replaceAndDelete(((RegisterFinalizer) usage).next()); - } else { - assert usage instanceof FrameState || usage instanceof VirtualObject : "usage: " + usage; - usage.inputs().replace(node, Node.Null); - } - } - - if (node instanceof FixedNodeWithNext) { - node.replaceAndDelete(((FixedNodeWithNext) node).next()); - } else { - node.delete(); - } - } - - private void updateFrameState(FrameState frameState, VirtualObject current) { - for (int i = 0; i < frameState.inputs().size(); i++) { - if (frameState.inputs().get(i) == node) { - frameState.inputs().set(i, current); - } else if (frameState.inputs().get(i) instanceof VirtualObject) { - VirtualObject obj = (VirtualObject) frameState.inputs().get(i); - do { - updateVirtualObject(obj, current); - obj = obj.object(); - } while (obj != null); - } - } - FrameState outer = frameState.outerFrameState(); - if (outer != null) { - boolean duplicate = false; - for (int i = 0; i < outer.inputs().size(); i++) { - if (outer.inputs().get(i) == node) { - duplicate = true; - } - } - // (tw) need to fully duplicate also if there is a reference to "node" in an outer framestate? - duplicate = true; - if (duplicate) { - outer = outer.duplicate(outer.bci); - frameState.setOuterFrameState(outer); - } - updateFrameState(outer, current); - } - } - - private void updateVirtualObject(VirtualObject obj, VirtualObject current) { - if (obj.input() == node) { - // (tw) don't we have similar issues here like in framestate dup? We are updating a shared data structure here.. - obj.setInput(current); - } else if (obj.input() instanceof VirtualObject) { - VirtualObject obj2 = (VirtualObject) obj.input(); - do { - updateVirtualObject(obj2, current); - obj2 = obj2.object(); - } while (obj2 != null); - } + }.apply(next); } private void process() { @@ -305,9 +378,6 @@ @Override protected void run(Graph graph) { - if (compilation.method.name().contains("removeEnd") || compilation.method.name().contains("emitCode")) { - return; - } for (Node node : graph.getNodes()) { EscapeOp op = node.lookup(EscapeOp.class); if (op != null && op.canAnalyze(node)) { @@ -344,10 +414,10 @@ TTY.println("%n!!!!!!!! non-escaping object: %d %s (%s) in %s", node.id(), node.shortName(), ((Value) node).exactType(), compilation.method); } new EscapementFixup(op, graph, node).apply(); + if (compilation.compiler.isObserved()) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After escape", graph, true, false)); + } new PhiSimplifier(graph); - if (compilation.compiler.isObserved()) { - compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After escape " + node.id(), graph, true, false)); - } break; } if (weight < minimumWeight) { @@ -364,6 +434,12 @@ } new InliningPhase(compilation, ir, invokes).apply(graph); new DeadCodeEliminationPhase().apply(graph); + if (node.isDeleted()) { + if (GraalOptions.TraceEscapeAnalysis || GraalOptions.PrintEscapeAnalysis) { + TTY.println("%n!!!!!!!! object died while performing escape analysis: %d %s (%s) in %s", node.id(), node.shortName(), ((Value) node).exactType(), compilation.method); + } + break; + } exits.clear(); invokes.clear(); } while (iterations++ < 3); @@ -433,7 +509,7 @@ void beforeUpdate(Node node, Node usage); - EscapeField updateState(Node node, Node current, Map fields, Map fieldState); + int updateState(Node node, Node current, Map fieldIndex, Value[] fieldState); } } diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Wed Jul 06 16:01:29 2011 +0200 @@ -267,10 +267,11 @@ 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) { + if (mergeBlock.getPredecessors().size() <= i) { TTY.println(merge.toString()); TTY.println(phi.toString()); TTY.println(merge.phiPredecessors().toString()); + TTY.println(phi.inputs().toString()); TTY.println("value count: " + phi.valueCount()); } block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64LIRGenerator.java Wed Jul 06 16:01:29 2011 +0200 @@ -367,7 +367,7 @@ return; } - assert Util.archKindsEqual(x.x().kind, x.kind) && Util.archKindsEqual(x.y().kind, x.kind) : "wrong parameter types: " + Bytecodes.nameOf(x.opcode); + assert Util.archKindsEqual(x.x().kind, x.kind) && Util.archKindsEqual(x.y().kind, x.kind) : "wrong parameter types: " + Bytecodes.nameOf(x.opcode) + ", x: " + x.x() + ", y: " + x.y() + ", kind: " + x.kind; switch (x.kind) { case Float: case Double: diff -r 94e903d0cf3b -r a5e5ef264dbf graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Mon Jul 04 18:04:44 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Wed Jul 06 16:01:29 2011 +0200 @@ -125,12 +125,27 @@ return method; } + public void addVirtualObjectMapping(Node virtualObject) { + assert virtualObject instanceof VirtualObjectField || virtualObject instanceof Phi : virtualObject; + inputs().variablePart().add(virtualObject); + } + + public int virtualObjectMappingCount() { + return inputs().variablePart().size(); + } + + public Node virtualObjectMappingAt(int i) { + return inputs().variablePart().get(i); + } + + /** * Gets a copy of this frame state. */ public FrameState duplicate(int bci) { FrameState other = new FrameState(method, bci, localsSize, stackSize, locksSize, rethrowException, graph()); other.inputs().setAll(inputs()); + other.inputs().variablePart().addAll(inputs().variablePart()); other.setOuterFrameState(outerFrameState()); return other; } @@ -162,6 +177,7 @@ for (int i = 0; i < locksSize; i++) { other.setValueAt(localsSize + other.stackSize + i, lockAt(i)); } + other.inputs().variablePart().addAll(inputs().variablePart()); other.setOuterFrameState(outerFrameState()); return other; } @@ -468,30 +484,83 @@ * @param proc the call back called to process each live value traversed */ public void forEachLiveStateValue(ValueProcedure proc) { - for (int i = 0; i < valuesSize(); i++) { - Value value = valueAt(i); - visitLiveStateValue(value, proc); - } - if (outerFrameState() != null) { - outerFrameState().forEachLiveStateValue(proc); - } - } + HashSet vobjs = null; + FrameState current = this; + do { + for (int i = 0; i < current.valuesSize(); i++) { + Value value = current.valueAt(i); + if (value instanceof VirtualObject) { + if (vobjs == null) { + vobjs = new HashSet(); + } + vobjs.add((VirtualObject) value); + } else if (value != null) { + proc.doValue(value); + } + } + current = current.outerFrameState(); + } while (current != null); + + if (vobjs != null) { + // collect all VirtualObjectField instances: + HashMap objectStates = new HashMap(); + current = this; + do { + for (int i = 0; i < current.virtualObjectMappingCount(); i++) { + VirtualObjectField field = (VirtualObjectField) current.virtualObjectMappingAt(i); + // null states occur for objects with 0 fields + if (field != null && !objectStates.containsKey(field.object())) { + objectStates.put(field.object(), field); + } + } + current = current.outerFrameState(); + } while (current != null); - private void visitLiveStateValue(Value value, ValueProcedure proc) { - if (value != null) { - if (value instanceof VirtualObject) { - HashSet fields = new HashSet(); - VirtualObject obj = (VirtualObject) value; - do { - if (!fields.contains(obj.field().representation())) { - fields.add(obj.field().representation()); - visitLiveStateValue(obj.input(), proc); + do { + HashSet vobjsCopy = new HashSet(vobjs); + for (VirtualObject vobj : vobjsCopy) { + if (vobj.fields().length > 0) { + boolean[] fieldState = new boolean[vobj.fields().length]; + FloatingNode currentField = objectStates.get(vobj); + assert currentField != null : this; + do { + if (currentField instanceof VirtualObjectField) { + int index = ((VirtualObjectField) currentField).index(); + Value value = ((VirtualObjectField) currentField).input(); + if (!fieldState[index]) { + fieldState[index] = true; + if (value instanceof VirtualObject) { + vobjs.add((VirtualObject) value); + } else { + proc.doValue(value); + } + } + currentField = ((VirtualObjectField) currentField).lastState(); + } else { + assert currentField instanceof Phi : currentField; + currentField = (FloatingNode) ((Phi) currentField).valueAt(0); + } + } while (currentField != null); } - obj = obj.object(); - } while (obj != null); - } else { - proc.doValue(value); + vobjs.remove(vobj); + } + } while (!vobjs.isEmpty()); + if (!vobjs.isEmpty()) { + for (VirtualObject obj : vobjs) { + TTY.println("+" + obj); + } + for (Node vobj : inputs().variablePart()) { + if (vobj instanceof VirtualObjectField) { + TTY.println("-" + ((VirtualObjectField) vobj).object()); + } else { + TTY.println("-" + vobj); + } + } + for (Node n : this.usages()) { + TTY.println("usage: " + n); + } } + assert vobjs.isEmpty() : "at FrameState " + this; } }