Mercurial > hg > truffle
changeset 4169:f5328dda9714
Initial commit of SSA-based spill-all register assignment
line wrap: on
line diff
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiAddress.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiAddress.java Wed Dec 28 18:13:25 2011 -0800 @@ -230,13 +230,13 @@ } @Override - public String name() { + public String toString() { // Checkstyle: stop switch (format()) { - case BASE : return "[" + s(base) + "]"; - case BASE_DISP : return "[" + s(base) + signed(displacement) + "]"; - case BASE_INDEX : return "[" + s(base) + "+" + s(index) + "]"; - case BASE_INDEX_DISP : return "[" + s(base) + "+(" + s(index) + "*" + scale.value + ")" + signed(displacement) + "]"; + case BASE : return "[" + s(base) + kindSuffix() + "]"; + case BASE_DISP : return "[" + s(base) + signed(displacement) + kindSuffix() + "]"; + case BASE_INDEX : return "[" + s(base) + "+" + s(index) + kindSuffix() + "]"; + case BASE_INDEX_DISP : return "[" + s(base) + "+(" + s(index) + "*" + scale.value + ")" + signed(displacement) + kindSuffix() + "]"; case PLACEHOLDER : return "[<placeholder>]"; default : throw new IllegalArgumentException("unknown format: " + format()); }
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiBitMap.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiBitMap.java Wed Dec 28 18:13:25 2011 -0800 @@ -62,6 +62,19 @@ } /** + * Constructs a copy of the given bit map. + * + * @param bitmap the bit map to copy. + */ + public CiBitMap(CiBitMap bitmap) { + this.size = bitmap.size; + this.low = bitmap.low; + if (bitmap.extra != null) { + this.extra = Arrays.copyOf(bitmap.extra, bitmap.extra.length); + } + } + + /** * Constructs a new bit map from a byte array encoded bit map. * * @param arr the byte array containing the bit map to convert
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiConstant.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiConstant.java Wed Dec 28 18:13:25 2011 -0800 @@ -30,7 +30,7 @@ public final class CiConstant extends CiValue { /** - * + * */ private static final long serialVersionUID = -6355452536852663986L; private static final CiConstant[] INT_CONSTANT_CACHE = new CiConstant[100]; @@ -129,8 +129,8 @@ } @Override - public String name() { - return "const[" + kind.format(boxedValue()) + (kind != CiKind.Object ? "|0x" + Long.toHexString(primitive) : "") + "]"; + public String toString() { + return kind.javaName + "[" + kind.format(boxedValue()) + (kind != CiKind.Object ? "|0x" + Long.toHexString(primitive) : "") + "]"; } /**
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiMonitorValue.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiMonitorValue.java Wed Dec 28 18:13:25 2011 -0800 @@ -23,13 +23,11 @@ package com.sun.cri.ci; public final class CiMonitorValue extends CiValue { - /** - * - */ private static final long serialVersionUID = 8241681800464483691L; - public final CiValue owner; - public final CiValue lockData; - public final boolean eliminated; + + public CiValue owner; + public CiValue lockData; + public boolean eliminated; public CiMonitorValue(CiValue owner, CiValue lockData, boolean eliminated) { super(CiKind.Illegal); @@ -40,22 +38,7 @@ } @Override - public String name() { - return "monitor"; - } - - @Override - public boolean equals(Object obj) { - return this == obj; - } - - @Override - public boolean equalsIgnoringKind(CiValue other) { - return this == other; - } - - @Override - public int hashCode() { - return 0; + public String toString() { + return "monitor[" + owner + (lockData != null ? ", " + lockData : "") + (eliminated ? ", eliminated" : "") + "]"; } }
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiRegisterValue.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiRegisterValue.java Wed Dec 28 18:13:25 2011 -0800 @@ -28,12 +28,9 @@ * retrieve the canonical {@link CiRegisterValue} instance for a given (register,kind) pair. */ public final class CiRegisterValue extends CiValue { + private static final long serialVersionUID = 7999341472196897163L; /** - * - */ - private static final long serialVersionUID = 7999341472196897163L; - /** * The register. */ public final CiRegister reg; @@ -41,14 +38,14 @@ /** * Should only be called from {@link CiRegister#CiRegister} to ensure canonicalization. */ - CiRegisterValue(CiKind kind, CiRegister register) { + protected CiRegisterValue(CiKind kind, CiRegister register) { super(kind); this.reg = register; } @Override public int hashCode() { - return kind.ordinal() ^ reg.number; + return (reg.number << 4) ^ kind.ordinal(); } @Override @@ -65,8 +62,8 @@ } @Override - public String name() { - return reg.name; + public String toString() { + return reg.name + kindSuffix(); } @Override
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiStackSlot.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiStackSlot.java Wed Dec 28 18:13:25 2011 -0800 @@ -29,7 +29,7 @@ public final class CiStackSlot extends CiValue { /** - * + * */ private static final long serialVersionUID = -7725071921307318433L; @@ -122,8 +122,8 @@ } @Override - public String name() { - return (inCallerFrame() ? "caller-stack" : "stack:") + index(); + public String toString() { + return (inCallerFrame() ? "caller-stack" : "stack:") + index() + kindSuffix(); } /**
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiValue.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiValue.java Wed Dec 28 18:13:25 2011 -0800 @@ -24,8 +24,6 @@ import java.io.*; - - /** * Abstract base class for values manipulated by the compiler. All values have a {@linkplain CiKind kind} and are immutable. */ @@ -35,25 +33,13 @@ @SuppressWarnings("serial") public static CiValue IllegalValue = new CiValue(CiKind.Illegal) { @Override - public String name() { - return "<illegal>"; + public String toString() { + return "-"; } @Override public CiRegister asRegister() { return CiRegister.None; } - @Override - public int hashCode() { - return -1; - } - @Override - public boolean equals(Object obj) { - return obj == this; - } - @Override - public boolean equalsIgnoringKind(CiValue other) { - return other == this; - } }; /** @@ -110,52 +96,19 @@ return this instanceof CiConstant; } - /** - * Gets a string name for this value without indicating its {@linkplain #kind kind}. - */ - public abstract String name(); - - @Override - public abstract boolean equals(Object obj); - - public abstract boolean equalsIgnoringKind(CiValue other); + public boolean equalsIgnoringKind(CiValue other) { + // This is a suitable default implementation for several subclasses + return equals(other); + } @Override - public abstract int hashCode(); + public abstract String toString(); - @Override - public final String toString() { - return name() + kindSuffix(); - } - - public final String kindSuffix() { - if (kind == CiKind.Illegal) { - return ""; - } - return ":" + kind.typeChar; + protected final String kindSuffix() { + return "|" + kind.typeChar; } public final boolean isConstant0() { return isConstant() && ((CiConstant) this).asInt() == 0; } - - /** - * Utility for specializing how a {@linkplain CiValue LIR operand} is formatted to a string. - * The {@linkplain Formatter#DEFAULT default formatter} returns the value of - * {@link CiValue#toString()}. - */ - public static class Formatter { - public static final Formatter DEFAULT = new Formatter(); - - /** - * Formats a given operand as a string. - * - * @param operand the operand to format - * @return {@code operand} as a string - */ - public String format(CiValue operand) { - return operand.toString(); - } - } - }
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVariable.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVariable.java Wed Dec 28 18:13:25 2011 -0800 @@ -30,7 +30,7 @@ public final class CiVariable extends CiValue { /** - * + * */ private static final long serialVersionUID = 4507578431686109809L; @@ -116,7 +116,7 @@ } @Override - public String name() { - return "v" + index; + public String toString() { + return "v" + index + kindSuffix(); } }
--- a/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVirtualObject.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.cri/src/com/sun/cri/ci/CiVirtualObject.java Wed Dec 28 18:13:25 2011 -0800 @@ -29,11 +29,8 @@ * deoptimization to recreate the object. */ public final class CiVirtualObject extends CiValue { + private static final long serialVersionUID = -2907197776426346021L; - /** - * - */ - private static final long serialVersionUID = -2907197776426346021L; private final RiType type; private CiValue[] values; private final int id; @@ -58,8 +55,8 @@ } @Override - public String name() { - return "vobject"; + public String toString() { + return "vobject:" + id; } /**
--- a/graal/com.oracle.max.criutils/src/com/oracle/max/criutils/CompilationPrinter.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.criutils/src/com/oracle/max/criutils/CompilationPrinter.java Wed Dec 28 18:13:25 2011 -0800 @@ -25,8 +25,6 @@ import java.io.*; import com.sun.cri.ci.*; -import com.sun.cri.ci.CiAddress.Scale; -import com.sun.cri.ci.CiValue.Formatter; import com.sun.cri.ri.*; /** @@ -105,7 +103,7 @@ /** * Formats a given {@linkplain FrameState JVM frame state} as a multi line string. */ - protected String debugInfoToString(CiCodePos codePos, CiBitMap registerRefMap, CiBitMap frameRefMap, OperandFormatter fmt, CiArchitecture arch) { + protected String debugInfoToString(CiCodePos codePos, CiBitMap registerRefMap, CiBitMap frameRefMap, CiArchitecture arch) { StringBuilder sb = new StringBuilder(); if (registerRefMap != null) { @@ -134,7 +132,7 @@ if (frame.numStack > 0) { sb.append("stack: "); for (int i = 0; i < frame.numStack; i++) { - sb.append(valueToString(frame.getStackValue(i), fmt)).append(' '); + sb.append(valueToString(frame.getStackValue(i))).append(' '); } sb.append("\n"); } @@ -142,14 +140,14 @@ if (frame.numLocks > 0) { sb.append("locks: "); for (int i = 0; i < frame.numLocks; ++i) { - sb.append(valueToString(frame.getLockValue(i), fmt)).append(' '); + sb.append(valueToString(frame.getLockValue(i))).append(' '); } sb.append("\n"); } sb.append("locals: "); for (int i = 0; i < frame.numLocals; i++) { - sb.append(valueToString(frame.getLocalValue(i), fmt)).append(' '); + sb.append(valueToString(frame.getLocalValue(i))).append(' '); } sb.append("\n"); } @@ -159,63 +157,11 @@ return sb.toString(); } - - protected String valueToString(CiValue value, Formatter operandFmt) { + protected String valueToString(CiValue value) { if (value == null) { return "-"; } - return operandFmt.format(value); - } - - - /** - * Formats LIR operands as expected by the C1 Visualizer. - */ - public static class OperandFormatter extends Formatter { - /** - * The textual delimiters used for an operand depend on the context in which it is being - * printed. When printed as part of a frame state or as the result operand in a HIR node listing, - * it is enclosed in double-quotes (i.e. {@code "}'s). - */ - public final boolean asStateOrHIROperandResult; - - public OperandFormatter(boolean asStateOrHIROperandResult) { - this.asStateOrHIROperandResult = asStateOrHIROperandResult; - } - - @Override - public String format(CiValue operand) { - if (operand.isLegal()) { - String op; - if (operand.isVariableOrRegister() || operand.isStackSlot()) { - op = operand.name(); - } else if (operand.isConstant()) { - CiConstant constant = (CiConstant) operand; - op = operand.kind.javaName + ":" + operand.kind.format(constant.boxedValue()); - } else if (operand.isAddress()) { - CiAddress address = (CiAddress) operand; - op = "Base:" + format(address.base); - if (!address.index.isIllegal()) { - op += " Index:" + format(address.index); - } - if (address.scale != Scale.Times1) { - op += " * " + address.scale.value; - } - op += " Disp:" + address.displacement; - } else { - assert operand.isIllegal(); - op = "-"; - } - if (operand.kind != CiKind.Illegal) { - op += "|" + operand.kind.typeChar; - } - if (asStateOrHIROperandResult) { - op = " \"" + op.replace('"', '\'') + "\" "; - } - return op; - } - return ""; - } + return value.toString(); } public void printMachineCode(String code, String label) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/AssignRegisters.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,130 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.simple; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import com.oracle.max.criutils.*; +import com.oracle.max.graal.alloc.util.*; +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.sun.cri.ci.*; + +public abstract class AssignRegisters { + public final LIR lir; + public final FrameMap frameMap; + + public AssignRegisters(LIR lir, FrameMap frameMap) { + this.lir = lir; + this.frameMap = frameMap; + } + + private CiBitMap curRegisterRefMap; + private CiBitMap curFrameRefMap; + + public void execute() { + ValueProcedure useProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value); } }; + ValueProcedure defProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value); } }; + ValueProcedure setReferenceProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return setReference(value); } }; + + trace(1, "==== start assign registers ===="); + for (int i = lir.linearScanOrder().size() - 1; i >= 0; i--) { + LIRBlock block = lir.linearScanOrder().get(i); + trace(1, "start block %s", block); + assert block.phis == null : "Register assignment must run after phi functions have been replaced by moves"; + + curRegisterRefMap = frameMap.initRegisterRefMap(); + curFrameRefMap = frameMap.initFrameRefMap(); + + // Put all values live at the end of the block into the reference map. + locationsForBlockEnd(block).forEachLocation(setReferenceProc); + + for (int j = block.lir().size() - 1; j >= 0; j--) { + LIRInstruction op = block.lir().get(j); + trace(1, " op %d %s", op.id(), op); + + op.forEachOutput(defProc); + op.forEachTemp(defProc); + op.forEachState(useProc); + op.forEachAlive(useProc); + + if (op.info != null) { + trace(3, " registerRefMap: %s frameRefMap: %s", curRegisterRefMap, curFrameRefMap); + op.info.finish(new CiBitMap(curRegisterRefMap), new CiBitMap(curFrameRefMap), frameMap); + + if (op instanceof LIRXirInstruction) { + LIRXirInstruction xir = (LIRXirInstruction) op; + if (xir.infoAfter != null) { + xir.infoAfter.finish(op.hasCall() ? null : new CiBitMap(curRegisterRefMap), new CiBitMap(curFrameRefMap), frameMap); + } + } + } + + // Process input operands after assigning the reference map, so that input operands that are used + // for the last time at this instruction are not part of the reference map. + op.forEachInput(useProc); + } + trace(1, "end block %s", block); + } + trace(1, "==== end assign registers ===="); + } + + private CiValue use(CiValue value) { + trace(3, " use %s", value); + if (isLocation(value)) { + CiValue location = asLocation(value).location; + frameMap.setReference(location, curRegisterRefMap, curFrameRefMap); + return location; + } else { + frameMap.setReference(value, curRegisterRefMap, curFrameRefMap); + return value; + } + } + + private CiValue def(CiValue value) { + trace(3, " def %s", value); + if (isLocation(value)) { + CiValue location = asLocation(value).location; + frameMap.clearReference(location, curRegisterRefMap, curFrameRefMap); + return location; + } else { + frameMap.clearReference(value, curRegisterRefMap, curFrameRefMap); + return value; + } + } + + private CiValue setReference(CiValue value) { + trace(3, " setReference %s", value); + frameMap.setReference(asLocation(value).location, curRegisterRefMap, curFrameRefMap); + return value; + } + + protected abstract LocationMap locationsForBlockEnd(LIRBlock block); + + private static void trace(int level, String format, Object...args) { + if (GraalOptions.TraceRegisterAllocationLevel >= level) { + TTY.println(format, args); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/DataFlowAnalysis.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,342 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.simple; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.criutils.*; +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.alloc.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.oracle.max.graal.compiler.schedule.*; +import com.sun.cri.ci.*; +import com.sun.cri.ri.*; + +public class DataFlowAnalysis { + private final GraalContext context; + private final LIR lir; + private final OperandPool operands; + private final RiRegisterConfig registerConfig; + private final CiCallingConvention incomingArguments; + + public DataFlowAnalysis(GraalContext context, LIR lir, OperandPool operands, RiRegisterConfig registerConfig, CiCallingConvention incomingArguments) { + this.context = context; + this.lir = lir; + this.operands = operands; + this.registerConfig = registerConfig; + this.incomingArguments = incomingArguments; + } + + public void execute() { + numberInstructions(); + context.observable.fireCompilationEvent("After instruction numbering", lir); + backwardDataFlow(); + } + + + private List<LIRBlock> blocks() { + return lir.linearScanOrder(); + } + + private int numVariables() { + return operands.numVariables(); + } + + private boolean isAllocatableRegister(CiValue value) { + return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable; + } + + + private int[] definitions; + private BitSet[] blockLiveIn; + private LIRBlock[] opIdBlock; + private Object[] opIdKilledValues; + + + public BitSet liveIn(Block block) { + return blockLiveIn[block.blockID()]; + } + private void setLiveIn(Block block, BitSet liveIn) { + blockLiveIn[block.blockID()] = liveIn; + } + + private LIRBlock blockOf(int opId) { + return opIdBlock[opId >> 1]; + } + private void setBlockOf(int opId, LIRBlock block) { + opIdBlock[opId >> 1] = block; + } + + private Object killedValues(int opId) { + return opIdKilledValues[opId]; + } + private void setKilledValues(int opId, Object killedValues) { + opIdKilledValues[opId] = killedValues; + } + + public void forEachKilled(LIRInstruction op, boolean end, ValueProcedure proc) { + Object entry = killedValues(op.id() + (end ? 1 : 0)); + if (entry == null) { + // Nothing to do + } else if (entry instanceof CiValue) { + CiValue newValue = proc.doValue((CiValue) entry); + assert newValue == entry : "procedure does not allow to change values"; + } else { + CiValue[] values = (CiValue[]) entry; + for (int i = 0; i < values.length; i++) { + if (values[i] != null) { + CiValue newValue = proc.doValue(values[i]); + assert newValue == values[i] : "procedure does not allow to change values"; + } + } + } + } + + /** + * Numbers all instructions in all blocks. The numbering follows the {@linkplain ComputeLinearScanOrder linear scan order}. + */ + private void numberInstructions() { + ValueProcedure defProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return setDef(value); } }; + + int numInstructions = 0; + for (LIRBlock block : blocks()) { + numInstructions += block.lir().size(); + } + opIdBlock = new LIRBlock[numInstructions]; + opIdKilledValues = new Object[numInstructions << 1]; + definitions = new int[numVariables()]; + + curOpId = 0; + for (LIRBlock block : blocks()) { + block.setFirstLirInstructionId(curOpId); + + if (block.phis != null) { + block.phis.forEachOutput(defProc); + } + + for (LIRInstruction op : block.lir()) { + op.setId(curOpId); + setBlockOf(curOpId, block); + + op.forEachTemp(defProc); + op.forEachOutput(defProc); + + curOpId += 2; // numbering of lirOps by two + } + block.setLastLirInstructionId(curOpId - 2); + } + assert curOpId == numInstructions << 1; + } + + private CiValue setDef(CiValue value) { + if (isVariable(value)) { + assert definitions[asVariable(value).index] == 0 : "Variable defined twice"; + definitions[asVariable(value).index] = curOpId; + } + return value; + } + + + private BitSet variableLive; + private BitSet registerLive; + private int curOpId; + + private void backwardDataFlow() { + ValueProcedure inputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value, curOpId); } }; + ValueProcedure aliveProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value, curOpId + 1); } }; + ValueProcedure phiInputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value, -1); } }; + ValueProcedure tempProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, true); } }; + ValueProcedure outputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, false); } }; + + blockLiveIn = new BitSet[blocks().size()]; + registerLive = new BitSet(); + + trace(1, "==== start backward data flow analysis ===="); + for (int i = blocks().size() - 1; i >= 0; i--) { + LIRBlock block = blocks().get(i); + trace(1, "start block %s loop %d depth %d", block, block.loopIndex(), block.loopDepth()); + + variableLive = new BitSet(); + for (LIRBlock sux : block.getLIRSuccessors()) { + BitSet suxLive = liveIn(sux); + if (suxLive != null) { + trace(1, " sux %s suxLive: %s", sux, suxLive); + variableLive.or(suxLive); + } + + if (sux.phis != null) { + curOpId = block.lastLirInstructionId(); + trace(1, " phis %d variableLive: %s", curOpId, variableLive); + sux.phis.forEachInput(block, phiInputProc); + } + } + + assert registerLive.isEmpty() : "no fixed register must be alive before processing a block"; + + for (int j = block.lir().size() - 1; j >= 0; j--) { + LIRInstruction op = block.lir().get(j); + curOpId = op.id(); + trace(1, " op %d %s variableLive: %s registerLive: %s", curOpId, op, variableLive, registerLive); + + op.forEachOutput(outputProc); + op.forEachTemp(tempProc); + op.forEachState(aliveProc); + op.forEachAlive(aliveProc); + op.forEachInput(inputProc); + } + + if (block.phis != null) { + curOpId = block.firstLirInstructionId(); + trace(1, " phis %d variableLive: %s registerLive: %s", curOpId, variableLive, registerLive); + block.phis.forEachOutput(outputProc); + } + + if (block.numberOfPreds() == 0) { + curOpId = block.firstLirInstructionId(); + trace(1, " arguments %d variableLive: %s registerLive: %s", curOpId, variableLive, registerLive); + for (CiValue value : incomingArguments.locations) { + def(value, false); + } + assert variableLive.isEmpty() : "no variables must be live at method entry"; + } + + assert registerLive.isEmpty() : "no fixed register must be alive after processing a block"; + assert liveIn(block) == null; + setLiveIn(block, variableLive); + + if (block.isLoopHeader()) { + trace(1, " loop header, propagating live set to loop blocks variableLive: %s", variableLive); + // All variables that are live at the beginning of a loop are also live the whole loop. + // This is guaranteed by the SSA form. + for (Block loop : block.loopBlocks) { + BitSet loopLiveIn = liveIn(loop); + assert loopLiveIn != null : "All loop blocks must have been processed before the loop header"; + loopLiveIn.or(variableLive); + trace(3, " block %s loopLiveIn %s", loop, loopLiveIn); + } + } + + trace(1, "end block %s variableLive: %s", block, variableLive); + } + trace(1, "==== end backward data flow analysis ===="); + } + + private CiValue use(CiValue value, int killOpId) { + trace(3, " use %s", value); + if (isVariable(value)) { + int variableIdx = asVariable(value).index; + assert definitions[variableIdx] < curOpId; + if (!variableLive.get(variableIdx)) { + trace(3, " set live variable %d", variableIdx); + variableLive.set(variableIdx); + kill(value, killOpId); + } + + } else if (isAllocatableRegister(value)) { + int regNum = asRegister(value).number; + if (!registerLive.get(regNum)) { + trace(3, " set live register %d", regNum); + registerLive.set(regNum); + kill(value, killOpId); + } + } + return value; + } + + private CiValue def(CiValue value, boolean isTemp) { + trace(3, " def %s", value); + if (isVariable(value)) { + int variableIdx = asVariable(value).index; + assert definitions[variableIdx] == curOpId; + if (variableLive.get(variableIdx)) { + trace(3, " clear live variable %d", variableIdx); + assert !isTemp : "temp variable cannot be used after the operation"; + variableLive.clear(variableIdx); + } else { + // Variable has never been used, so kill it immediately after the definition. + kill(value, curOpId + 1); + } + + } else if (isAllocatableRegister(value)) { + int regNum = asRegister(value).number; + if (registerLive.get(regNum)) { + trace(3, " clear live register %d", regNum); + assert !isTemp : "temp variable cannot be used after the operation"; + registerLive.clear(regNum); + } else { + // Register has never been used, so kill it immediately after the definition. + kill(value, curOpId + 1); + } + } + return value; + } + + private void kill(CiValue value, int opId) { + if (opId < 0) { + return; + } + if (isVariable(value)) { + int defOpId = definitions[asVariable(value).index]; + assert defOpId > 0 && defOpId <= opId; + + LIRBlock defBlock = blockOf(defOpId); + LIRBlock useBlock = blockOf(opId); + + if (useBlock.loopDepth() > 0 && useBlock.loopIndex() != defBlock.loopIndex()) { + // This is a value defined outside of the loop it is currently used in. Therefore, it is live the whole loop + // and is not killed by the current instruction. + trace(3, " no kill because use in loop %d, definition in loop %d", useBlock.loopIndex(), defBlock.loopIndex()); + return; + } + } + trace(3, " kill %s at %d", value, opId); + + Object entry = killedValues(opId); + if (entry == null) { + setKilledValues(opId, value); + } else if (entry instanceof CiValue) { + setKilledValues(opId, new CiValue[] {(CiValue) entry, value}); + } else { + CiValue[] killed = (CiValue[]) entry; + for (int i = 0; i < killed.length; i++) { + if (killed[i] == null) { + killed[i] = value; + return; + } + } + int oldLen = killed.length; + killed = Arrays.copyOf(killed, oldLen * 2); + setKilledValues(opId, killed); + killed[oldLen] = value; + } + } + + private static void trace(int level, String format, Object...args) { + if (GraalOptions.TraceRegisterAllocationLevel >= level) { + TTY.println(format, args); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/ResolveDataFlow.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,124 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.simple; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.criutils.*; +import com.oracle.max.graal.alloc.util.*; +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.oracle.max.graal.compiler.lir.LIRPhiMapping.PhiValueProcedure; +import com.oracle.max.graal.compiler.util.*; +import com.sun.cri.ci.*; + +public abstract class ResolveDataFlow { + public final LIR lir; + public final MoveResolver moveResolver; + + public ResolveDataFlow(LIR lir, MoveResolver moveResolver) { + this.lir = lir; + this.moveResolver = moveResolver; + } + + private LocationMap curFromLocations; + + public void execute() { + ValueProcedure locMappingProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return locMapping(value); } }; + PhiValueProcedure phiMappingProc = new PhiValueProcedure() { @Override public void doValue(CiValue input, CiValue output) { phiMapping(input, output); } }; + + trace(1, "==== start resolve data flow ===="); + for (LIRBlock toBlock : lir.linearScanOrder()) { + + for (LIRBlock fromBlock : toBlock.getLIRPredecessors()) { + trace(1, "start edge %s -> %s", fromBlock, toBlock); + findInsertPos(fromBlock, toBlock); + + LocationMap toLocations = locationsForBlockBegin(toBlock); + curFromLocations = locationsForBlockEnd(fromBlock); + if (toLocations != curFromLocations) { + toLocations.forEachLocation(locMappingProc); + } + + if (toBlock.phis != null) { + toBlock.phis.forEachInput(fromBlock, phiMappingProc); + } + + moveResolver.resolve(); + trace(1, "end edge %s -> %s", fromBlock, toBlock); + } + + // Phi functions are resolved with moves now, so delete them. + toBlock.phis = null; + } + moveResolver.finish(); + trace(1, "==== end resolve data flow ===="); + } + + private CiValue locMapping(CiValue value) { + Location to = curFromLocations.get(asLocation(value).variable); + if (value != to && to != null) { + moveResolver.add(value, to); + } + return value; + } + + private void phiMapping(CiValue input, CiValue output) { + Location to = asLocation(output); + if (input != to) { + moveResolver.add(input, to); + } + } + + private void findInsertPos(LIRBlock fromBlock, LIRBlock toBlock) { + assert fromBlock.getSuccessors().contains(toBlock) && toBlock.getPredecessors().contains(fromBlock); + + if (fromBlock.numberOfSux() == 1) { + List<LIRInstruction> instructions = fromBlock.lir(); + LIRInstruction instr = instructions.get(instructions.size() - 1); + assert instr instanceof LIRBranch && instr.code == StandardOpcode.JUMP : "block does not end with an unconditional jump"; + moveResolver.init(instructions, instructions.size() - 1); + trace(1, " insert at end of %s before %d", fromBlock, instructions.size() - 1); + + } else if (toBlock.numberOfPreds() == 1) { + moveResolver.init(toBlock.lir(), 1); + trace(1, " insert at beginning of %s before %d", toBlock, 1); + + } else { + Util.shouldNotReachHere("Critical edge not split"); + } + } + + protected abstract LocationMap locationsForBlockBegin(LIRBlock block); + protected abstract LocationMap locationsForBlockEnd(LIRBlock block); + + + private static void trace(int level, String format, Object...args) { + if (GraalOptions.TraceRegisterAllocationLevel >= level) { + TTY.println(format, args); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/simple/SpillAllAllocator.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,472 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.simple; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.criutils.*; +import com.oracle.max.graal.alloc.util.*; +import com.oracle.max.graal.alloc.util.MoveResolver; +import com.oracle.max.graal.alloc.util.RegisterVerifier; +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.alloc.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.compiler.util.*; +import com.sun.cri.ci.*; +import com.sun.cri.ci.CiRegister.RegisterFlag; +import com.sun.cri.ri.*; + +public class SpillAllAllocator { + private final GraalContext context; + private final LIR lir; + private final FrameMap frameMap; + private final OperandPool operands; + private final RiRegisterConfig registerConfig; + + private final DataFlowAnalysis dataFlow; + + private final SpillSlots spillSlots; + + public SpillAllAllocator(GraalContext context, LIR lir, GraalCompilation compilation, OperandPool pool, RiRegisterConfig registerConfig) { + this.context = context; + this.lir = lir; + this.operands = pool; + this.registerConfig = registerConfig; + this.frameMap = compilation.frameMap(); + + this.spillSlots = new SpillSlots(compilation.compiler.context, frameMap); + this.dataFlow = new DataFlowAnalysis(context, lir, pool, registerConfig, frameMap.incomingArguments()); + this.blockLocations = new LocationMap[lir.linearScanOrder().size()]; + this.moveResolver = new MoveResolver(frameMap.target, spillSlots); + } + + + private class ResolveDataFlowImpl extends ResolveDataFlow { + public ResolveDataFlowImpl(LIR lir, MoveResolver moveResolver) { + super(lir, moveResolver); + } + + @Override + protected LocationMap locationsForBlockBegin(LIRBlock block) { + assert block.numberOfPreds() > 0 && block.dominator() != null; + return locationsFor(block.dominator()); + } + + @Override + protected LocationMap locationsForBlockEnd(LIRBlock block) { + return locationsFor(block); + } + } + + private class AssignRegistersImpl extends AssignRegisters { + public AssignRegistersImpl(LIR lir, FrameMap frameMap) { + super(lir, frameMap); + } + + @Override + protected LocationMap locationsForBlockEnd(LIRBlock block) { + return locationsFor(block); + } + } + + + private int maxRegisterNum() { + return frameMap.target.arch.registers.length; + } + + private boolean isAllocatableRegister(CiValue value) { + return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable; + } + + + private final LocationMap[] blockLocations; + + private LocationMap locationsFor(Block block) { + return blockLocations[block.blockID()]; + } + private void setLocationsFor(Block block, LocationMap locations) { + blockLocations[block.blockID()] = locations; + } + + private MoveResolver moveResolver; + private LocationMap curStackLocations; + private LocationMap curRegisterLocations; + private Object[] curInRegisterState; + private Object[] curOutRegisterState; + private BitSet curLiveIn; + private LIRInstruction curInstruction; + + public void execute() { + assert LIRVerifier.verify(true, lir, frameMap.incomingArguments(), frameMap, registerConfig, operands); + + dataFlow.execute(); + + allocate(); + + context.observable.fireCompilationEvent("After spill all allocation", lir); + + spillSlots.finish(); + + ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver); + resolveDataFlow.execute(); + + context.observable.fireCompilationEvent("After resolve data flow", lir); + + assert RegisterVerifier.verify(lir, frameMap.incomingArguments(), frameMap, registerConfig); + + AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap); + assignRegisters.execute(); + + context.observable.fireCompilationEvent("After register asignment", lir); + + assert LIRVerifier.verify(true, lir, frameMap.incomingArguments(), frameMap, registerConfig, operands); + } + + private void allocate() { + ValueProcedure killNonLiveProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return killNonLive(value); } }; + ValueProcedure killBeginProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return kill(value, false); } }; + ValueProcedure killEndProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return kill(value, true); } }; + ValueProcedure killLocationProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return killLocation(value); } }; + ValueProcedure blockProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return block(value); } }; + ValueProcedure inputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return load(value, false); } }; + ValueProcedure aliveProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return load(value, true); } }; + ValueProcedure tempProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return spill(value, true); } }; + ValueProcedure outputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return spill(value, false); } }; + ValueProcedure useSlotProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return useSlot(value); } }; + ValueProcedure defSlotProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return defSlot(value); } }; + + trace(1, "==== start spill all allocation ===="); + curInRegisterState = new Object[maxRegisterNum()]; + curOutRegisterState = new Object[maxRegisterNum()]; + curRegisterLocations = new LocationMap(operands.numVariables()); + for (LIRBlock block : lir.linearScanOrder()) { + trace(1, "start block %s loop %d depth %d", block, block.loopIndex(), block.loopDepth()); + assert checkEmpty(curOutRegisterState); + + if (block.numberOfPreds() == 0) { + curStackLocations = new LocationMap(operands.numVariables()); + trace(1, " arguments"); + curInstruction = lir.startBlock().lir().get(0); + for (CiValue value : frameMap.incomingArguments().locations) { + block(value); + } + } else { + LocationMap dominatorState = locationsFor(block.dominator()); + curStackLocations = new LocationMap(dominatorState); + // Clear out all variables that are not live at the begin of this block + curLiveIn = dataFlow.liveIn(block); + curStackLocations.forEachLocation(killNonLiveProc); + assert checkInputState(block); + } + traceState(); + + if (block.phis != null) { + trace(1, " phis"); + block.phis.forEachOutput(defSlotProc); + } + + for (int opIdx = 0; opIdx < block.lir().size(); opIdx++) { + LIRInstruction op = block.lir().get(opIdx); + curInstruction = op; + trace(1, " op %d %s", op.id(), op); + + assert curRegisterLocations.checkEmpty(); + + System.arraycopy(curOutRegisterState, 0, curInRegisterState, 0, curOutRegisterState.length); + + // Block fixed registers that are defined by this instruction, so that they are no longer available for normal allocation. + op.forEachTemp(blockProc); + op.forEachOutput(blockProc); + + moveResolver.init(block.lir(), opIdx); + // Process Alive before Input because they are more restricted and the same variable can be Alive and Input. + op.forEachAlive(aliveProc); + op.forEachInput(inputProc); + moveResolver.resolve(); + op.forEachState(useSlotProc); + + dataFlow.forEachKilled(op, false, killBeginProc); + assert !op.hasCall() || checkNoCallerSavedRegister() : "caller saved register in use accross call site"; + + moveResolver.init(block.lir(), opIdx + 1); + op.forEachTemp(tempProc); + op.forEachOutput(outputProc); + moveResolver.resolve(); + + dataFlow.forEachKilled(op, true, killEndProc); + curRegisterLocations.forEachLocation(killLocationProc); + + assert curRegisterLocations.checkEmpty(); + curInstruction = null; + } + assert checkEmpty(curOutRegisterState); + + for (LIRBlock sux : block.getLIRSuccessors()) { + if (sux.phis != null) { + trace(1, " phis of successor %s", sux); + sux.phis.forEachInput(block, useSlotProc); + } + } + + assert checkEmpty(curOutRegisterState); + assert locationsFor(block) == null; + setLocationsFor(block, curStackLocations); + + traceState(); + trace(1, "end block %s", block); + } + + moveResolver.finish(); + trace(1, "==== end spill all allocation ===="); + } + + private CiValue killNonLive(CiValue value) { + assert isLocation(value); + if (!curLiveIn.get(asLocation(value).variable.index)) { + return null; + } + return value; + } + + private CiValue kill(CiValue value, boolean end) { + if (isVariable(value)) { + trace(3, " kill variable %s", value); + + CiVariable variable = asVariable(value); + curStackLocations.clear(variable); + + Location loc = curRegisterLocations.get(variable); + if (loc != null) { + killLocation(loc); + curRegisterLocations.clear(variable); + + trace(3, " location %s", loc); + assert isAllocatableRegister(loc.location); + + int regNum = asRegister(loc.location).number; + if (curOutRegisterState[regNum] == loc) { + curOutRegisterState[regNum] = null; + } + } + + } else if (isAllocatableRegister(value)) { + trace(3, " kill register %s", value); + int regNum = asRegister(value).number; + assert curOutRegisterState[regNum] == null || curOutRegisterState[regNum] instanceof LIRInstruction && curInstruction != null; + + if (end || curOutRegisterState[regNum] != curInstruction) { + curOutRegisterState[regNum] = null; + } + + } else { + throw Util.shouldNotReachHere(); + } + return value; + } + + private CiValue killLocation(CiValue value) { + trace(3, " kill location %s", value); + assert isAllocatableRegister(asLocation(value).location); + + int regNum = asRegister(asLocation(value).location).number; + if (curOutRegisterState[regNum] == value) { + curOutRegisterState[regNum] = null; + } + return null; + } + + private CiValue block(CiValue value) { + if (isAllocatableRegister(value)) { + trace(3, " block %s", value); + int regNum = asRegister(value).number; + assert curInstruction != null; + assert curOutRegisterState[regNum] == null || curOutRegisterState[regNum] instanceof LIRInstruction; + curOutRegisterState[regNum] = curInstruction; + } + return value; + } + + private CiValue load(CiValue value, boolean isAlive) { + if (isVariable(value)) { + trace(3, " load %s", value); + Location regLoc = curRegisterLocations.get(asVariable(value)); + if (regLoc != null) { + // This variable has already been processed before. + trace(3, " found location %s", regLoc); + } else { + regLoc = allocateRegister(asVariable(value), curInRegisterState, isAlive ? curOutRegisterState : null); + Location stackLoc = curStackLocations.get(asVariable(value)); + assert stackLoc != null; + moveResolver.add(stackLoc, regLoc); + } + return regLoc; + } else { + assert !isAllocatableRegister(value) || curInRegisterState[asRegister(value).number] instanceof LIRInstruction; + return value; + } + } + + private CiValue spill(CiValue value, boolean isTemp) { + if (isVariable(value)) { + trace(3, " spill %s", value); + assert curStackLocations.get(asVariable(value)) == null; + Location regLoc = allocateRegister(asVariable(value), null, curOutRegisterState); + if (!isTemp) { + Location stackLoc = new Location(asVariable(value), spillSlots.allocateSpillSlot(value.kind)); + curStackLocations.put(stackLoc); + moveResolver.add(regLoc, stackLoc); + } + return regLoc; + } else { + assert !isAllocatableRegister(value) || curOutRegisterState[asRegister(value).number] == curInstruction && curInstruction != null; + return value; + } + } + + private CiValue useSlot(CiValue value) { + if (isVariable(value)) { + trace(3, " useSlot %s", value); + Location stackLoc = curStackLocations.get(asVariable(value)); + assert stackLoc != null; + trace(3, " slot %s", stackLoc); + return stackLoc; + } else { + return value; + } + } + + private CiValue defSlot(CiValue value) { + if (isVariable(value)) { + trace(3, " assignSlot %s", value); + Location stackLoc = new Location(asVariable(value), spillSlots.allocateSpillSlot(value.kind)); + assert curStackLocations.get(asVariable(value)) == null; + curStackLocations.put(stackLoc); + trace(3, " slot %s", stackLoc); + return stackLoc; + } else { + return value; + } + } + + private Location allocateRegister(CiVariable variable, Object[] inRegisterState, Object[] outRegisterState) { + EnumMap<RegisterFlag, CiRegister[]> categorizedRegs = registerConfig.getCategorizedAllocatableRegisters(); + CiRegister[] availableRegs; + if (operands.mustBeByteRegister(variable)) { + assert variable.kind != CiKind.Float && variable.kind != CiKind.Double : "cpu regs only"; + availableRegs = categorizedRegs.get(RegisterFlag.Byte); + } else if (variable.kind == CiKind.Float || variable.kind == CiKind.Double) { + availableRegs = categorizedRegs.get(RegisterFlag.FPU); + } else { + availableRegs = categorizedRegs.get(RegisterFlag.CPU); + } + + for (CiRegister reg : availableRegs) { + if ((inRegisterState == null || inRegisterState[reg.number] == null) && (outRegisterState == null || outRegisterState[reg.number] == null)) { + Location loc = new Location(variable, reg.asValue(variable.kind)); + if (inRegisterState != null) { + inRegisterState[reg.number] = loc; + } + if (outRegisterState != null) { + outRegisterState[reg.number] = loc; + } + assert curRegisterLocations.get(variable) == null; + curRegisterLocations.put(loc); + trace(3, " selected register %s", loc); + return loc; + } + } + throw new CiBailout("No register found"); + } + + + private boolean checkInputState(final LIRBlock block) { + final BitSet liveState = new BitSet(); + curStackLocations.forEachLocation(new ValueProcedure() { + @Override + public CiValue doValue(CiValue value) { + liveState.set(asLocation(value).variable.index); + + for (Block pred : block.getPredecessors()) { + LocationMap predState = locationsFor(pred); + if (predState != null) { + assert predState.get(asLocation(value).variable) == value; + } else { + assert block.isLoopHeader(); + } + } + return value; + } + }); + assert liveState.equals(curLiveIn); + return true; + } + +// private boolean checkBlocked(CiValue value, Object[] inRegisterState, Object[] outRegisterState) { +// if (isAllocatableRegister(value)) { +// int regNum = asRegister(value).number; +// assert inRegisterState == null || inRegisterState[regNum] instanceof LIRInstruction; +// } +// return !isAllocatableRegister(value) || asRegister(curRegisterState[asRegister(value).number]) == asRegister(value); +// } +// + private boolean checkNoCallerSavedRegister() { + for (CiRegister reg : registerConfig.getCallerSaveRegisters()) { + assert curOutRegisterState[reg.number] == null || curOutRegisterState[reg.number] == curInstruction : "caller saved register in use accross call site"; + // TODO check if that assertion holds, otherwise the code below is necessary (outside of an assertion!) + // curRegisterState[reg.number] = null; + } + return true; + } + + private static boolean checkEmpty(Object[] array) { + for (Object o : array) { + assert o == null; + } + return true; + } + + + private void traceState() { + if (GraalOptions.TraceRegisterAllocationLevel >= 3) { + TTY.print(" curVariableLocations: "); + curStackLocations.forEachLocation(new ValueProcedure() { + @Override + public CiValue doValue(CiValue value) { + TTY.print("%s ", value); + return value; + } + }); + TTY.println(); + } + } + + private static void trace(int level, String format, Object...args) { + if (GraalOptions.TraceRegisterAllocationLevel >= level) { + TTY.println(format, args); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/LIRVerifier.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,206 @@ +/* + * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.util; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.criutils.*; +import com.oracle.max.graal.compiler.alloc.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.compiler.util.*; +import com.sun.cri.ci.*; +import com.sun.cri.ri.*; + +public final class LIRVerifier { + private final LIR lir; + private final FrameMap frameMap; + private final RiRegisterConfig registerConfig; + + private final boolean beforeRegisterAllocation; + + private final BitSet[] blockLiveOut; + private final Object[] variableDefinitions; + + private BitSet liveOutFor(Block block) { + return blockLiveOut[block.blockID()]; + } + private void setLiveOutFor(Block block, BitSet liveOut) { + blockLiveOut[block.blockID()] = liveOut; + } + + private int maxRegisterNum() { + return frameMap.target.arch.registers.length; + } + + private boolean isAllocatableRegister(CiValue value) { + return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable; + } + + + public static boolean verify(boolean beforeRegisterAllocation, LIR lir, CiCallingConvention incomingArguments, FrameMap frameMap, RiRegisterConfig registerConfig, OperandPool operands) { + LIRVerifier verifier = new LIRVerifier(beforeRegisterAllocation, lir, frameMap, registerConfig, operands); + verifier.verify(incomingArguments); + return true; + } + + private LIRVerifier(boolean beforeRegisterAllocation, LIR lir, FrameMap frameMap, RiRegisterConfig registerConfig, OperandPool operands) { + this.beforeRegisterAllocation = beforeRegisterAllocation; + this.lir = lir; + this.frameMap = frameMap; + this.registerConfig = registerConfig; + this.blockLiveOut = new BitSet[lir.linearScanOrder().size()]; + this.variableDefinitions = new Object[operands.numVariables()]; + } + + private BitSet curVariablesLive; + private CiValue[] curRegistersLive; + + private LIRBlock curBlock; + private Object curInstruction; + + private void verify(CiCallingConvention incomingArguments) { + ValueProcedure useProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value); } }; + ValueProcedure tempProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, true); } }; + ValueProcedure outputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return def(value, false); } }; + + for (LIRBlock block : lir.linearScanOrder()) { + curBlock = block; + curVariablesLive = new BitSet(); + curRegistersLive = new CiValue[maxRegisterNum()]; + + if (block.numberOfPreds() == 0) { + curInstruction = "Argument"; + for (CiValue value : incomingArguments.locations) { + def(value, false); + } + } else { + curVariablesLive.or(liveOutFor(block.dominator())); + } + + if (beforeRegisterAllocation) { + if (block.phis != null) { + curInstruction = block.phis; + block.phis.forEachOutput(outputProc); + } + } else { + assert block.phis == null; + } + + for (LIRInstruction op : block.lir()) { + curInstruction = op; + + op.forEachInput(useProc); + if (op.hasCall()) { + for (CiRegister register : registerConfig.getCallerSaveRegisters()) { + curRegistersLive[register.number] = null; + } + } + op.forEachAlive(useProc); + op.forEachState(useProc); + op.forEachTemp(tempProc); + op.forEachOutput(outputProc); + + curInstruction = null; + } + + setLiveOutFor(block, curVariablesLive); + } + } + + private CiValue use(CiValue value) { + if (beforeRegisterAllocation && isVariable(value)) { + int variableIdx = asVariable(value).index; + if (!curVariablesLive.get(variableIdx)) { + TTY.println("block %s instruction %s", curBlock, curInstruction); + TTY.println("live variables: %s", curVariablesLive); + if (variableDefinitions[variableIdx] != null) { + TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]); + } + TTY.println("ERROR: Use of variable %s that is not defined in dominator", value); + throw Util.shouldNotReachHere(); + } + + } else if (beforeRegisterAllocation && isAllocatableRegister(value)) { + int regNum = asRegister(value).number; + if (curRegistersLive[regNum] != value) { + TTY.println("block %s instruction %s", curBlock, curInstruction); + TTY.println("live registers: %s", Arrays.toString(curRegistersLive)); + TTY.println("ERROR: Use of fixed register %s that is not defined in this block", value); + throw Util.shouldNotReachHere(); + } + } else if (isRegister(value)) { + // Register usage cannot be checked. + } else if (isStackSlot(value)) { + // TODO check if stack slot is allowed for this operand. + } else if (isConstant(value)) { + // TODO check if constant is allowed for this operand. + } else if (value == CiValue.IllegalValue) { + // TODO check if illegal is allowed for this operand. + } else { + TTY.println("block %s instruction %s", curBlock, curInstruction); + TTY.println("Unexpected value: %s %s", value.getClass().getSimpleName(), value); + throw Util.shouldNotReachHere(); + } + return value; + } + + private CiValue def(CiValue value, boolean isTemp) { + if (beforeRegisterAllocation && isVariable(value)) { + int variableIdx = asVariable(value).index; + if (variableDefinitions[variableIdx] != null) { + TTY.println("block %s instruction %s", curBlock, curInstruction); + TTY.println("live variables: %s", curVariablesLive); + TTY.println("definition of %s: %s", value, variableDefinitions[variableIdx]); + TTY.println("ERROR: Variable %s defined multiple times", value); + throw Util.shouldNotReachHere(); + } + assert curInstruction != null; + variableDefinitions[variableIdx] = curInstruction; + assert !curVariablesLive.get(variableIdx); + if (!isTemp) { + curVariablesLive.set(variableIdx); + } + + } else if (beforeRegisterAllocation && isAllocatableRegister(value)) { + int regNum = asRegister(value).number; + if (isTemp) { + curRegistersLive[regNum] = null; + } else { + curRegistersLive[regNum] = value; + } + } else if (isRegister(value)) { + // Register definition cannot be checked. + } else if (isStackSlot(value)) { + // TODO check if stack slot is allowed for this operand. + } else { + TTY.println("block %s instruction %s", curBlock, curInstruction); + TTY.println("Unexpected value: %s %s", value.getClass().getSimpleName(), value); + throw Util.shouldNotReachHere(); + } + return value; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/Location.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.util; + +import com.sun.cri.ci.*; + +public class Location extends CiValue { + private static final long serialVersionUID = -1786677729152726126L; + + public final CiVariable variable; + public final CiValue location; + + public Location(CiVariable variable, CiValue location) { + super(variable.kind); + this.variable = variable; + this.location = location; + + assert variable.kind == location.kind; + } + + @Override + public String toString() { + return variable + "[" + location + "]"; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/LocationMap.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.util; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.sun.cri.ci.*; + +public class LocationMap { + private final Location[] locations; + + public LocationMap(int numVariables) { + locations = new Location[numVariables]; + } + + public LocationMap(LocationMap template) { + locations = Arrays.copyOf(template.locations, template.locations.length); + } + + public Location get(CiVariable variable) { + assert locations[variable.index] == null || locations[variable.index].variable == variable; + return locations[variable.index]; + } + + public void put(Location location) { + locations[location.variable.index] = location; + } + + public void clear(CiVariable variable) { + locations[variable.index] = null; + } + + public void forEachLocation(ValueProcedure proc) { + for (int i = 0; i < locations.length; i++) { + if (locations[i] != null) { + CiValue newValue = proc.doValue(locations[i]); + assert newValue == null || asLocation(newValue).variable == locations[i].variable; + locations[i] = (Location) newValue; + } + } + } + + public boolean checkEmpty() { + for (int i = 0; i < locations.length; i++) { + assert locations[i] == null; + } + return true; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/MoveResolver.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,312 @@ +/* + * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.util; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.criutils.*; +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.alloc.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.util.*; +import com.sun.cri.ci.*; + +public final class MoveResolver { + private final SpillSlots spillSlots; + private final int[] registersBlocked; + private final Map<CiValue, Integer> valuesBlocked; + private final List<CiValue> mappingFrom; + private final List<Location> mappingTo; + private final LIRInsertionBuffer insertionBuffer; + private int insertPos; + + public MoveResolver(CiTarget target, SpillSlots spillSlots) { + this.spillSlots = spillSlots; + + registersBlocked = new int[target.arch.registers.length]; + valuesBlocked = new HashMap<>(); + + mappingFrom = new ArrayList<>(); + mappingTo = new ArrayList<>(); + insertionBuffer = new LIRInsertionBuffer(); + insertPos = -1; + + assert checkEmpty(); + } + + public void init(List<LIRInstruction> newInsertList, int newInsertPos) { + assert checkEmpty(); + + if (insertionBuffer.lirList() != newInsertList) { + // Block changed, so append insertionBuffer because it is bound to a specific block + finish(); + insertionBuffer.init(newInsertList); + } + insertPos = newInsertPos; + + assert checkValid(); + } + + public void add(CiValue from, Location to) { + assert checkValid(); + assert isLocation(from) || isConstant(from); + assert from != to; + + trace(3, "mr add mapping from %s to %s", from, to); + mappingFrom.add(from); + mappingTo.add(to); + + assert checkValid(); + } + + public void resolve() { + assert checkValid(); + + if (mappingFrom.size() == 1) { + // If there is only one mapping, it is trivial that this mapping is safe to resolve. + trace(3, "mr resolve mappings: %d", mappingFrom.size()); + insertMove(mappingFrom.get(0), mappingTo.get(0)); + mappingFrom.remove(0); + mappingTo.remove(0); + } else if (mappingFrom.size() > 1) { + trace(3, "mr resolve mappings: %d", mappingFrom.size()); + doResolve(); + } + insertPos = -1; + + assert checkEmpty(); + } + + public void finish() { + assert checkEmpty(); + + if (insertionBuffer.initialized()) { + insertionBuffer.finish(); + } + + assert !insertionBuffer.initialized() : "must be uninitialized now"; + assert checkEmpty(); + } + + + private void doResolve() { + // Block all registers and stack slots that are used as inputs of a move. + // When a register is blocked, no move to this register is emitted. + // This is necessary for detecting cycles in moves. + for (CiValue from : mappingFrom) { + block(from); + } + + while (mappingFrom.size() > 0) { + boolean processed = false; + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + CiValue from = mappingFrom.get(i); + Location to = mappingTo.get(i); + + if (safeToProcessMove(from, to)) { + insertMove(from, to); + unblock(from); + mappingFrom.remove(i); + mappingTo.remove(i); + processed = true; + } + } + + if (!processed) { + // No move could be processed because there is a cycle in the move list + // (e.g., r1 -> r2, r2 -> r1), so one location must be spilled. + spill(); + } + } + } + + private void spill() { + Location spillCandidate = null; + int exchangeCandidate = -1; + int exchangeOther = -1; + + for (int i = mappingFrom.size(); i >= 0; i--) { + CiValue from = mappingFrom.get(i); + Location to = mappingTo.get(i); + assert !safeToProcessMove(from, to) : "would not be in this code otherwise"; + + if (isConstant(from)) { + continue; + } + CiValue fromLoc = asLocation(from).location; + + // Check if we can insert an exchange to save us from spilling. + if (isRegister(fromLoc) && isRegister(to) && asRegister(fromLoc) != asRegister(to) && blockedCount(to) == 1) { + for (int j = mappingFrom.size() - 1; j >= 0; j--) { + CiValue possibleOther = mappingFrom.get(j); + if (isLocation(possibleOther)) { + if (asLocation(possibleOther).location == to.location) { + assert exchangeCandidate == -1 : "must not find twice because of blocked check above"; + exchangeCandidate = i; + exchangeOther = j; + } else if (i != j && asLocation(possibleOther).location == fromLoc) { + // From is read multiple times, so exchange would be too complicated. + exchangeCandidate = -1; + break; + } + } + } + } + + if (exchangeCandidate != -1) { + // Already found a result, no need to search further + break; + } + if (spillCandidate == null || isStackSlot(spillCandidate.location)) { + // this interval cannot be processed now because target is not free + spillCandidate = asLocation(from); + } + } + + if (exchangeCandidate != -1) { + Location from = asLocation(mappingFrom.get(exchangeCandidate)); + Location to = mappingTo.get(exchangeCandidate); + Location other = asLocation(mappingFrom.get(exchangeOther)); + + Location newOther = new Location(other.variable, from.variable); + mappingFrom.set(exchangeOther, newOther); + + insertExchange(newOther, to); + unblock(to); + mappingFrom.remove(exchangeCandidate); + mappingTo.remove(exchangeCandidate); + + } else { + assert spillCandidate != null : "no location for spilling found"; + + Location spillLocation = new Location(spillCandidate.variable, spillSlots.allocateSpillSlot(spillCandidate.kind)); + insertMove(spillCandidate, spillLocation); + + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + if (mappingFrom.get(i) == spillCandidate) { + mappingFrom.set(i, spillLocation); + unblock(spillCandidate); + block(spillLocation); + } + } + assert blockedCount(spillCandidate) == 0 : "register must be unblocked after spilling"; + } + } + + private void block(CiValue value) { + if (isLocation(value)) { + CiValue location = asLocation(value).location; + if (isRegister(location)) { + registersBlocked[asRegister(location).number]++; + } else { + Integer count = valuesBlocked.get(location); + valuesBlocked.put(location, count == null ? 1 : count + 1); + } + } + } + + private void unblock(CiValue value) { + if (isLocation(value)) { + assert blockedCount(asLocation(value)) > 0; + CiValue location = asLocation(value).location; + if (isRegister(location)) { + registersBlocked[asRegister(location).number]--; + } else { + Integer count = valuesBlocked.remove(location); + if (count > 1) { + valuesBlocked.put(location, count - 1); + } + } + } + } + + private int blockedCount(Location value) { + CiValue location = asLocation(value).location; + if (isRegister(location)) { + return registersBlocked[asRegister(location).number]; + } else { + Integer count = valuesBlocked.get(location); + return count == null ? 0 : count; + } + } + + private boolean safeToProcessMove(CiValue from, Location to) { + int count = blockedCount(to); + return count == 0 || (count == 1 && isLocation(from) && asLocation(from).location == to.location); + } + + private void insertExchange(Location from, Location to) { + trace(3, "mr XCHG %s, %s", from, to); + throw Util.unimplemented(); + // TODO create XCHG instruction and use it here + // insertionBuffer.append(StandardOp.XCHG.create(from, to)); + } + + private void insertMove(CiValue src, Location dst) { + trace(3, "mr MOV %s -> %s", src, dst); + insertionBuffer.append(insertPos, StandardOpcode.MOVE.create(dst, src)); + } + + + private boolean checkEmpty() { + assert insertPos == -1; + assert mappingFrom.size() == 0 && mappingTo.size() == 0; + for (int registerBlocked : registersBlocked) { + assert registerBlocked == 0; + } + assert valuesBlocked.size() == 0; + return true; + } + + private boolean checkValid() { + assert insertPos != -1; + for (int registerBlocked : registersBlocked) { + assert registerBlocked == 0; + } + assert mappingFrom.size() == mappingTo.size(); + assert insertionBuffer.initialized() && insertPos != -1; + + for (int i = 0; i < mappingTo.size(); i++) { + CiValue from = mappingFrom.get(i); + Location to = mappingTo.get(i); + + assert from.kind.stackKind() == to.kind; + assert !isLocation(from) || asLocation(from).location != to.location; + + for (int j = i + 1; j < mappingTo.size(); j++) { + Location otherTo = mappingTo.get(j); + assert to != otherTo && to.variable != otherTo.variable && to.location != otherTo.location : "Cannot write to same location twice"; + } + } + return true; + } + + + private static void trace(int level, String format, Object...args) { + if (GraalOptions.TraceRegisterAllocationLevel >= level) { + TTY.println(format, args); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/RegisterVerifier.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,256 @@ +/* + * Copyright (c) 2009, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.util; + +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + +import java.util.*; + +import com.oracle.max.criutils.*; +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.lir.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; +import com.oracle.max.graal.compiler.util.*; +import com.sun.cri.ci.*; +import com.sun.cri.ri.*; + +public final class RegisterVerifier { + private final FrameMap frameMap; + private final RiRegisterConfig registerConfig; + + /** + * All blocks that must be processed. + */ + private final List<LIRBlock> workList; + + /** + * Saved information of previous check. + * <br> + * State mapping: mapping from registers and stack slots ({@link CiRegister} and {@link Integer} stack slot offsets) to the + * value that is currently contained in there ({@link Location} for operands that were variables; {@link CiRegisterValue} or + * {@link CiStackSlot} for operands that used fixed registers or stack slots). + */ + private final Map<Object, CiValue>[] blockStates; + + private void addToWorkList(LIRBlock block) { + if (!workList.contains(block)) { + workList.add(block); + } + } + + private Map<Object, CiValue> stateFor(LIRBlock block) { + return blockStates[block.blockID()]; + } + + private void setStateFor(LIRBlock block, Map<Object, CiValue> savedState) { + blockStates[block.blockID()] = savedState; + } + + private static Map<Object, CiValue> copy(Map<Object, CiValue> inputState) { + return new HashMap<>(inputState); + } + + public static boolean verify(LIR lir, CiCallingConvention incomingArguments, FrameMap frameMap, RiRegisterConfig registerConfig) { + RegisterVerifier verifier = new RegisterVerifier(lir, frameMap, registerConfig); + verifier.verify(lir.startBlock(), incomingArguments); + return true; + } + + @SuppressWarnings("unchecked") + private RegisterVerifier(LIR lir, FrameMap frameMap, RiRegisterConfig registerConfig) { + this.frameMap = frameMap; + this.registerConfig = registerConfig; + this.workList = new LinkedList<>(); + this.blockStates = new Map[lir.linearScanOrder().size()]; + } + + private Map<Object, CiValue> curInputState; + + private void verify(LIRBlock startBlock, CiCallingConvention incomingArguments) { + ValueProcedure useProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return use(value); } }; + ValueProcedure tempProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return temp(value); } }; + ValueProcedure outputProc = new ValueProcedure() { @Override public CiValue doValue(CiValue value) { return output(value); } }; + + curInputState = new HashMap<>(); + for (CiValue value : incomingArguments.locations) { + curInputState.put(key(value), value); + } + setStateFor(startBlock, curInputState); + addToWorkList(startBlock); + + trace(1, "==== start verify register allocation ===="); + do { + LIRBlock block = workList.remove(0); + assert block.phis == null : "phi functions must have been resolved with moves"; + + // Must copy state because it is modified. + curInputState = copy(stateFor(block)); + trace(1, "start block %s loop %d depth %d", block, block.loopIndex(), block.loopDepth()); + traceState(); + + for (LIRInstruction op : block.lir()) { + trace(2, " op %d %s", op.id(), op); + + op.forEachInput(useProc); + if (op.hasCall()) { + invalidateRegisters(); + } + op.forEachAlive(useProc); + op.forEachState(useProc); + op.forEachTemp(tempProc); + op.forEachOutput(outputProc); + } + + for (LIRBlock succ : block.getLIRSuccessors()) { + processSuccessor(succ); + } + + trace(1, "end block %s", block); + } while (!workList.isEmpty()); + trace(1, "==== end verify register allocation ===="); + } + + private void processSuccessor(LIRBlock succ) { + Map<Object, CiValue> savedState = stateFor(succ); + if (savedState == null) { + // Block was not processed before, so set initial inputState. + trace(2, " successor %s: initial visit", succ); + setStateFor(succ, copy(curInputState)); + addToWorkList(succ); + + } else { + // This block was already processed before. + // Check if new inputState is consistent with savedState. + trace(2, " successor %s: state present", succ); + Iterator<Map.Entry<Object, CiValue>> iter = savedState.entrySet().iterator(); + while (iter.hasNext()) { + Map.Entry<Object, CiValue> entry = iter.next(); + CiValue savedValue = entry.getValue(); + CiValue inputValue = curInputState.get(entry.getKey()); + + if (savedValue != inputValue) { + // Current inputState and previous savedState assume a different value in this register. + // Assume that this register is invalid and remove it from the saved state. + trace(2, " invalididating %s because it is inconsistent with %s", savedValue, inputValue); + iter.remove(); + // Must re-visit this block. + addToWorkList(succ); + } + } + } + } + + private void invalidateRegisters() { + // Invalidate all caller save registers at calls. + Iterator<Object> iter = curInputState.keySet().iterator(); + while (iter.hasNext()) { + Object value1 = iter.next(); + if (value1 instanceof CiRegister && registerConfig.getAttributesMap()[((CiRegister) value1).number].isCallerSave) { + trace(2, " remove caller save register %s", value1); + iter.remove(); + } + } + } + + /** + * Gets the mapping key for a value. The key should be as narrow as possible, e.g., it should not + * include the kind of the value because we do not want to distinguish between the same register with + * different kinds. + */ + private Object key(CiValue value) { + if (isLocation(value)) { + return key(asLocation(value).location); + } else if (isRegister(value)) { + return asRegister(value); + } else if (isStackSlot(value)) { + return Integer.valueOf(frameMap.offsetForStackSlot(asStackSlot(value))); + } else { + throw Util.shouldNotReachHere(); + } + } + + private boolean isIgnoredRegister(CiValue value) { + return isRegister(value) && !registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable; + } + + private CiValue use(CiValue value) { + if (!isConstant(value) && value != CiValue.IllegalValue && !isIgnoredRegister(value)) { + CiValue actual = curInputState.get(key(value)); + if (value != actual) { + TTY.println("!! Error in register allocation: %s != %s for key %s", value, actual, key(value)); + traceState(); + throw Util.shouldNotReachHere(); + } + } + return value; + } + + private CiValue temp(CiValue value) { + trace(2, " temp %s -> remove key %s", value, key(value)); + curInputState.remove(key(value)); + return value; + } + + private CiValue output(CiValue value) { + trace(2, " output %s -> set key %s", value, key(value)); + curInputState.put(key(value), value); + return value; + } + + + private void traceState() { + if (GraalOptions.TraceRegisterAllocationLevel >= 2) { + ArrayList<Object> keys = new ArrayList<>(curInputState.keySet()); + Collections.sort(keys, new Comparator<Object>() { + @Override + public int compare(Object o1, Object o2) { + if (o1 instanceof CiRegister) { + if (o2 instanceof CiRegister) { + return ((CiRegister) o1).number - ((CiRegister) o2).number; + } else { + return -1; + } + } else { + if (o2 instanceof CiRegister) { + return 1; + } else { + return ((Integer) o1).intValue() - ((Integer) o2).intValue(); + } + } + } + }); + + TTY.print(" state: "); + for (Object key : keys) { + TTY.print("%s=%s ", key, curInputState.get(key)); + } + TTY.println(); + } + } + + private static void trace(int level, String format, Object...args) { + if (GraalOptions.TraceRegisterAllocationLevel >= level) { + TTY.println(format, args); + } + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/SpillSlots.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/SpillSlots.java Wed Dec 28 18:13:25 2011 -0800 @@ -61,6 +61,7 @@ */ public CiStackSlot allocateSpillSlot(CiKind kind) { assert maxSpills >= 0 : "cannot allocate new spill slots after finish() has been called"; + assert numberOfSpillSlots(kind) <= 2 : "larger values not supported yet"; CiStackSlot spillSlot; if (numberOfSpillSlots(kind) == 2) {
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/alloc/util/ValueUtil.java Wed Dec 28 18:13:25 2011 -0800 @@ -0,0 +1,114 @@ +/* + * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.max.graal.alloc.util; + +import com.sun.cri.ci.*; + + +public class ValueUtil { + + public static boolean isIllegal(CiValue value) { + assert value != null; + assert (value == CiValue.IllegalValue) == (value.kind == CiKind.Illegal); + return value == CiValue.IllegalValue; + } + + public static boolean isVirtualObject(CiValue value) { + assert value != null; + return value instanceof CiVirtualObject; + } + + public static boolean isLocation(CiValue value) { + assert value != null; + return value instanceof Location; + } + + public static Location asLocation(CiValue value) { + assert value != null; + return (Location) value; + } + + + public static boolean isVariable(CiValue value) { + assert value != null; + return value instanceof CiVariable; + } + + public static CiVariable asVariable(CiValue value) { + assert value != null; + return (CiVariable) value; + } + + public static boolean isConstant(CiValue value) { + assert value != null; + return value instanceof CiConstant; + } + + public static boolean isStackSlot(CiValue value) { + assert value != null; + return value instanceof CiStackSlot; + } + + public static CiStackSlot asStackSlot(CiValue value) { + assert value != null; + return (CiStackSlot) value; + } + + + + public static boolean isRegister(CiValue value) { + assert value != null; + return value instanceof CiRegisterValue; + } + + public static CiRegister asRegister(CiValue value) { + assert value != null; + return ((CiRegisterValue) value).reg; + } + + + public static CiRegister asIntReg(CiValue value) { + assert value.kind == CiKind.Int || value.kind == CiKind.Jsr; + return asRegister(value); + } + + public static CiRegister asLongReg(CiValue value) { + assert value.kind == CiKind.Long : value.kind; + return asRegister(value); + } + + public static CiRegister asObjectReg(CiValue value) { + assert value.kind == CiKind.Object; + return asRegister(value); + } + + public static CiRegister asFloatReg(CiValue value) { + assert value.kind == CiKind.Float; + return asRegister(value); + } + + public static CiRegister asDoubleReg(CiValue value) { + assert value.kind == CiKind.Double; + return asRegister(value); + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalCompilation.java Wed Dec 28 18:13:25 2011 -0800 @@ -27,6 +27,7 @@ import com.oracle.max.asm.*; import com.oracle.max.criutils.*; +import com.oracle.max.graal.alloc.simple.*; import com.oracle.max.graal.compiler.alloc.*; import com.oracle.max.graal.compiler.asm.*; import com.oracle.max.graal.compiler.gen.*; @@ -299,7 +300,7 @@ lir = new LIR(startBlock, linearScanOrder, codeEmittingOrder, valueToBlock); if (context().isObserved()) { - context().observable.fireCompilationEvent("After linear scan order", this, graph); + context().observable.fireCompilationEvent("After linear scan order", this, graph, lir); } } catch (AssertionError t) { context().observable.fireCompilationEvent("AssertionError in ComputeLinearScanOrder", CompilationEvent.ERROR, this, graph); @@ -334,15 +335,28 @@ for (LIRBlock b : lir.linearScanOrder()) { lirGenerator.doBlock(b); } + + for (LIRBlock b : lir.linearScanOrder()) { + if (b.phis != null) { + b.phis.fillInputs(lirGenerator); + } + } } finally { context().timers.endScope(); } + if (context().isObserved()) { + context().observable.fireCompilationEvent("After LIR generation", this, graph, lir); + } if (GraalOptions.PrintLIR && !TTY.isSuppressed()) { LIR.printLIR(lir.linearScanOrder()); } - new LinearScan(this, lir, lirGenerator, frameMap()).allocate(); + if (GraalOptions.AllocSSA) { + new SpillAllAllocator(context(), lir, this, lirGenerator.operands, registerConfig).execute(); + } else { + new LinearScan(this, lir, lirGenerator, frameMap()).allocate(); + } } } catch (Error e) { if (context().isObserved() && GraalOptions.PlotOnError) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Wed Dec 28 18:13:25 2011 -0800 @@ -105,6 +105,7 @@ public static boolean PrintCodeBytes = ____; public static int PrintAssemblyBytesPerLine = 16; public static int TraceLinearScanLevel = 0; + public static int TraceRegisterAllocationLevel = 0; public static int TraceLIRGeneratorLevel = 0; public static boolean TraceRelocation = ____; public static boolean TraceLIRVisit = ____;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/Interval.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/Interval.java Wed Dec 28 18:13:25 2011 -0800 @@ -1113,7 +1113,7 @@ from = String.valueOf(from()); to = String.valueOf(to()); } - String locationString = this.location == null ? "" : "@" + this.location.name(); + String locationString = this.location == null ? "" : "@" + this.location; return operandNumber + ":" + operand + (operand.isRegister() ? "" : locationString) + "[" + from + "," + to + "]"; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/LinearScan.java Wed Dec 28 18:13:25 2011 -0800 @@ -35,7 +35,7 @@ import com.oracle.max.graal.compiler.alloc.Interval.SpillState; import com.oracle.max.graal.compiler.gen.*; import com.oracle.max.graal.compiler.lir.*; -import com.oracle.max.graal.compiler.lir.LIRDebugInfo.ValueProcedure; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; import com.oracle.max.graal.compiler.lir.LIRInstruction.OperandMode; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; @@ -613,7 +613,7 @@ // Add uses of live locals from interpreter's point of view for proper debug information generation LIRDebugInfo info = op.info; if (info != null) { - info.forEachLiveStateValue(new ValueProcedure() { + info.forEachState(new ValueProcedure() { @Override public CiValue doValue(CiValue operand) { int operandNum = operandNumber(operand); @@ -623,7 +623,7 @@ TTY.println(" Setting liveGen for LIR opId %d, operand %d because of state for %s", op.id(), operandNum, op); } } - return null; + return operand; } }); } @@ -824,10 +824,10 @@ TTY.println(ins.id() + ": " + ins.result() + " " + ins.toString()); LIRDebugInfo info = ins.info; if (info != null) { - info.forEachLiveStateValue(new ValueProcedure() { + info.forEachState(new ValueProcedure() { public CiValue doValue(CiValue liveStateOperand) { TTY.println(" operand=" + liveStateOperand); - return null; + return liveStateOperand; } }); } @@ -1178,10 +1178,10 @@ // to a call site, the value would be in a register at the call otherwise) LIRDebugInfo info = op.info; if (info != null) { - info.forEachLiveStateValue(new ValueProcedure() { + info.forEachState(new ValueProcedure() { public CiValue doValue(CiValue operand) { addUse(operand, blockFrom, (opId + 1), RegisterPriority.None, operand.kind.stackKind()); - return null; + return operand; } }); } @@ -1638,7 +1638,7 @@ return new IntervalWalker(this, oopIntervals, nonOopIntervals); } - void computeOopMap(IntervalWalker iw, LIRInstruction op, LIRDebugInfo info) { + void computeOopMap(IntervalWalker iw, LIRInstruction op, CiBitMap registerRefMap, CiBitMap frameRefMap) { if (GraalOptions.TraceLinearScanLevel >= 3) { TTY.println("creating oop map at opId %d", op.id()); } @@ -1665,7 +1665,7 @@ // caller-save registers must not be included into oop-maps at calls assert !op.hasCall() || !operand.isRegister() || !isCallerSave(operand) : "interval is in a caller-save register at a call . register will be overwritten"; - info.setReference(interval.location(), frameMap); + frameMap.setReference(interval.location(), registerRefMap, frameRefMap); // Spill optimization: when the stack value is guaranteed to be always correct, // then it must be added to the oop map even if the interval is currently in a register @@ -1673,7 +1673,7 @@ assert interval.spillDefinitionPos() > 0 : "position not set correctly"; assert interval.spillSlot() != null : "no spill slot assigned"; assert !interval.operand.isRegister() : "interval is on stack : so stack slot is registered twice"; - info.setReference(interval.spillSlot(), frameMap); + frameMap.setReference(interval.spillSlot(), registerRefMap, frameRefMap); } } } @@ -1698,10 +1698,11 @@ private void computeDebugInfo(IntervalWalker iw, final LIRInstruction op, LIRDebugInfo info) { - info.initDebugInfo(op, frameMap); - computeOopMap(iw, op, info); + CiBitMap registerRefMap = op.hasCall() ? null : frameMap.initRegisterRefMap(); + CiBitMap frameRefMap = frameMap.initFrameRefMap(); + computeOopMap(iw, op, registerRefMap, frameRefMap); - info.forEachLiveStateValue(new ValueProcedure() { + info.forEachState(new ValueProcedure() { @Override public CiValue doValue(CiValue operand) { int tempOpId = op.id(); @@ -1730,6 +1731,8 @@ return result; } }); + + info.finish(registerRefMap, frameRefMap, frameMap); } private void assignLocations(List<LIRInstruction> instructions, IntervalWalker iw) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/CFGPrinter.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/CFGPrinter.java Wed Dec 28 18:13:25 2011 -0800 @@ -231,7 +231,7 @@ if (compilation.nodeOperands != null && node instanceof ValueNode) { CiValue operand = compilation.operand((ValueNode) node); if (operand != null) { - out.print("result ").print(new OperandFormatter(false).format(operand)).println(COLUMN_END); + out.print("result ").print(operand.toString()).println(COLUMN_END); } } out.print("tid ").print(nodeToString(node)).println(COLUMN_END); @@ -239,7 +239,7 @@ if (node instanceof StateSplit) { StateSplit stateSplit = (StateSplit) node; if (stateSplit.stateAfter() != null) { - String state = stateToString(stateSplit.stateAfter(), null); + String state = stateToString(stateSplit.stateAfter()); out.print("st ").print(HOVER_START).print("st").print(HOVER_SEP).print(state).print(HOVER_END).println(COLUMN_END); } } @@ -300,7 +300,7 @@ } } - private String stateToString(FrameState state, OperandFormatter operandFmt) { + private String stateToString(FrameState state) { StringBuilder buf = new StringBuilder(); FrameState curState = state; do { @@ -309,7 +309,7 @@ if (curState.stackSize() > 0) { buf.append("stack: "); for (int i = 0; i < curState.stackSize(); i++) { - buf.append(stateValueToString(curState.stackAt(i), operandFmt)).append(' '); + buf.append(stateValueToString(curState.stackAt(i))).append(' '); } buf.append("\n"); } @@ -317,14 +317,14 @@ if (curState.locksSize() > 0) { buf.append("locks: "); for (int i = 0; i < curState.locksSize(); ++i) { - buf.append(stateValueToString(curState.lockAt(i), operandFmt)).append(' '); + buf.append(stateValueToString(curState.lockAt(i))).append(' '); } buf.append("\n"); } buf.append("locals: "); for (int i = 0; i < curState.localsSize(); i++) { - buf.append(stateValueToString(curState.localAt(i), operandFmt)).append(' '); + buf.append(stateValueToString(curState.localAt(i))).append(' '); } buf.append("\n"); @@ -334,14 +334,15 @@ return buf.toString(); } - private String stateValueToString(ValueNode value, OperandFormatter operandFmt) { - if (operandFmt == null) { - return nodeToString(value); + private String stateValueToString(ValueNode value) { + String result = nodeToString(value); + if (value != null) { + CiValue operand = compilation.operand(value); + if (operand != null) { + result += ": " + operand; + } } - if (value == null) { - return "-"; - } - return operandFmt.format(compilation.operand(value)); + return result; } /** @@ -357,6 +358,20 @@ begin("IR"); out.println("LIR"); + + if (block.phis != null) { + CiValue[] results = block.phis.results(); + for (int i = 0; i < results.length; i++) { + out.print("instruction PHI ").print(results[i].toString()).print(" = ("); + String sep = ""; + for (LIRBlock pred : block.getLIRPredecessors()) { + out.print(sep).print(block.phis.inputs(pred)[i].toString()); + sep = ", "; + } + out.print(")").print(COLUMN_END).println(COLUMN_END); + } + } + for (int i = 0; i < lir.size(); i++) { LIRInstruction inst = lir.get(i); out.printf("nr %4d ", inst.id()).print(COLUMN_END); @@ -366,9 +381,9 @@ out.adjustIndentation(-level); String state; if (inst.info.hasDebugInfo()) { - state = debugInfoToString(inst.info.debugInfo().codePos, inst.info.debugInfo().registerRefMap, inst.info.debugInfo().frameRefMap, new OperandFormatter(false), target.arch); + state = debugInfoToString(inst.info.debugInfo().codePos, inst.info.debugInfo().registerRefMap, inst.info.debugInfo().frameRefMap, target.arch); } else { - state = debugInfoToString(inst.info.topFrame, null, null, new OperandFormatter(false), target.arch); + state = debugInfoToString(inst.info.topFrame, null, null, target.arch); } if (state != null) { out.print(" st ").print(HOVER_START).print("st").print(HOVER_SEP).print(state).print(HOVER_END).print(COLUMN_END); @@ -376,7 +391,7 @@ out.adjustIndentation(level); } - out.print(" instruction ").print(inst.toString(new OperandFormatter(false))).print(COLUMN_END); + out.print(" instruction ").print(inst.toString()).print(COLUMN_END); out.println(COLUMN_END); } end("IR"); @@ -428,17 +443,17 @@ } private void printInterval(Interval interval) { - out.printf("%s %s ", interval.operand.name(), (interval.operand.isRegister() ? "fixed" : interval.kind().name())); + out.printf("%s %s ", interval.operand, (interval.operand.isRegister() ? "fixed" : interval.kind().name())); if (interval.operand.isRegister()) { - out.printf("\"[%s|%c]\"", interval.operand.name(), interval.operand.kind.typeChar); + out.printf("\"[%s|%c]\"", interval.operand, interval.operand.kind.typeChar); } else { if (interval.location() != null) { - out.printf("\"[%s|%c]\"", interval.location().name(), interval.location().kind.typeChar); + out.printf("\"[%s|%c]\"", interval.location(), interval.location().kind.typeChar); } } Interval hint = interval.locationHint(false); - out.printf("%s %s ", interval.splitParent().operand.name(), hint != null ? hint.operand.name() : -1); + out.printf("%s %s ", interval.splitParent().operand, hint != null ? hint.operand : -1); // print ranges Range cur = interval.first();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Wed Dec 28 18:13:25 2011 -0800 @@ -22,6 +22,7 @@ */ package com.oracle.max.graal.compiler.gen; +import static com.oracle.max.graal.alloc.util.ValueUtil.*; import static com.oracle.max.cri.intrinsics.MemoryBarriers.*; import static com.sun.cri.ci.CiCallingConvention.Type.*; import static com.sun.cri.ci.CiValue.*; @@ -384,6 +385,8 @@ public void visitCheckCast(CheckCastNode x) { XirSnippet snippet = xir.genCheckCast(site(x), toXirArgument(x.object()), toXirArgument(x.targetClassInstruction()), x.targetClass()); emitXir(snippet, x, state(), null, true); + // The result of a checkcast is the unmodified object, so no need to allocate a new variable for it. + setResult(x, operand(x.object())); } @Override @@ -780,19 +783,31 @@ for (ValueNode arg : arguments) { if (arg != null) { CiValue operand = cc.locations[j++]; - if (operand.isRegister()) { - emitMove(operand(arg), operand.asRegister().asValue(operand.kind.stackKind())); - } else { - assert !((CiStackSlot) operand).inCallerFrame(); - CiValue param = loadForStore(operand(arg), operand.kind); - emitMove(param, operand); + if (isRegister(operand)) { + if (operand.kind.stackKind() != operand.kind) { + // We only have stack-kinds in the LIR, so convert the operand kind. + operand = asRegister(operand).asValue(operand.kind.stackKind()); + } - if (arg.kind() == CiKind.Object && pointerSlots != null) { + } else if (isStackSlot(operand)) { + assert !asStackSlot(operand).inCallerFrame(); + if (operand.kind == CiKind.Object && pointerSlots != null) { // This slot must be marked explicitly in the pointer map. - pointerSlots.add((CiStackSlot) operand); + pointerSlots.add(asStackSlot(operand)); + } + if (operand.kind.stackKind() != operand.kind) { + // We only have stack-kinds in the LIR, so convert the operand kind. + operand = CiStackSlot.get(operand.kind.stackKind(), asStackSlot(operand).index()); } + } else { + throw Util.shouldNotReachHere(); } + + emitMove(operand(arg), operand); argList.add(operand); + + } else { + throw Util.shouldNotReachHere("I thought we no longer have null entries for two-slot types..."); } } return argList;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/FrameMap.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/FrameMap.java Wed Dec 28 18:13:25 2011 -0800 @@ -22,6 +22,7 @@ */ package com.oracle.max.graal.compiler.lir; +import static com.oracle.max.graal.alloc.util.ValueUtil.*; import static com.sun.cri.ci.CiCallingConvention.Type.*; import com.oracle.max.graal.compiler.*; @@ -275,9 +276,6 @@ * Encapsulates the details of a stack block reserved by a call to {@link FrameMap#reserveStackBlock(int, boolean)}. */ public static final class StackBlock extends CiValue { - /** - * - */ private static final long serialVersionUID = -5260976274149772987L; /** @@ -300,22 +298,9 @@ } @Override - public String name() { + public String toString() { return "StackBlock " + offset; } - - @Override - public boolean equals(Object obj) { - return this == obj; - } - @Override - public boolean equalsIgnoringKind(CiValue other) { - return this == other; - } - @Override - public int hashCode() { - return offset; - } } /** @@ -391,12 +376,39 @@ return (outgoingSize + customAreaSize()) / target.spillSlotSize; } + + + + private int registerRefMapSize() { + return target.arch.registerReferenceMapBitCount; + } + + private int frameRefMapSize() { + if (incomingArguments.stackSize > 0) { + return (frameSize() + target.arch.returnAddressSize + customAreaSize() + incomingArguments.stackSize) / target.wordSize; + } else { + return frameSize() / target.wordSize; + } + } + + private int frameRefMapIndex(CiStackSlot slot) { + int offset = offsetForStackSlot(slot); + assert offset % target.wordSize == 0 && offset / target.wordSize < frameRefMapSize(); + return offset / target.wordSize; + } + /** - * Initializes a ref map that covers all the slots in the frame. + * Initializes a reference map that covers all registers of the target architecture. + */ + public CiBitMap initRegisterRefMap() { + return new CiBitMap(registerRefMapSize()); + } + + /** + * Initializes a reference map that covers all the slots in the frame. */ public CiBitMap initFrameRefMap() { - int frameWords = frameSize() / target.spillSlotSize; - CiBitMap frameRefMap = new CiBitMap(frameWords); + CiBitMap frameRefMap = new CiBitMap(frameRefMapSize()); for (StackBlock sb = stackBlocks; sb != null; sb = sb.next) { if (sb.kind == CiKind.Object) { int firstSlot = offsetForStackBlock(sb) / target.wordSize; @@ -408,4 +420,48 @@ } return frameRefMap; } + + /** + * Marks the specified location as a reference in the reference map of the debug information. + * The tracked location can be a {@link CiRegisterValue} or a {@link CiStackSlot}. Note that a + * {@link CiConstant} is automatically tracked. + * + * @param location The location to be added to the reference map. + * @param registerRefMap A register reference map, as created by {@link #initRegisterRefMap()}. + * @param frameRefMap A frame reference map, as created by {@link #initFrameRefMap()}. + */ + public void setReference(CiValue location, CiBitMap registerRefMap, CiBitMap frameRefMap) { +// assert registerRefMap.size() == registerRefMapSize() && frameRefMap.size() == frameRefMapSize(); + if (location.kind == CiKind.Object) { + if (isRegister(location)) { + registerRefMap.set(asRegister(location).number); + } else if (isStackSlot(location)) { + frameRefMap.set(frameRefMapIndex(asStackSlot(location))); + } else { + assert isConstant(location); + } + } + } + + /** + * Clears the specified location as a reference in the reference map of the debug information. + * The tracked location can be a {@link CiRegisterValue} or a {@link CiStackSlot}. Note that a + * {@link CiConstant} is automatically tracked. + * + * @param location The location to be removed from the reference map. + * @param registerRefMap A register reference map, as created by {@link #initRegisterRefMap()}. + * @param frameRefMap A frame reference map, as created by {@link #initFrameRefMap()}. + */ + public void clearReference(CiValue location, CiBitMap registerRefMap, CiBitMap frameRefMap) { +// assert registerRefMap.size() == registerRefMapSize() && frameRefMap.size() == frameRefMapSize(); + if (location.kind == CiKind.Object) { + if (location instanceof CiRegisterValue) { + registerRefMap.clear(asRegister(location).number); + } else if (isStackSlot(location)) { + frameRefMap.clear(frameRefMapIndex(asStackSlot(location))); + } else { + assert isConstant(location); + } + } + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRBlock.java Wed Dec 28 18:13:25 2011 -0800 @@ -149,6 +149,17 @@ return (LIRBlock) successors.get(i); } + @SuppressWarnings({"unchecked", "cast"}) + public List<LIRBlock> getLIRSuccessors() { + return (List<LIRBlock>) (List) super.getSuccessors(); + } + + @SuppressWarnings({"unchecked", "cast"}) + public List<LIRBlock> getLIRPredecessors() { + return (List<LIRBlock>) (List) super.getPredecessors(); + } + + @Override public String toString() { return "B" + blockID();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRCall.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRCall.java Wed Dec 28 18:13:25 2011 -0800 @@ -26,7 +26,6 @@ import com.sun.cri.ci.*; import com.sun.cri.ci.CiTargetMethod.Mark; -import com.sun.cri.ci.CiValue.Formatter; import com.sun.cri.ri.*; import com.sun.cri.xir.CiXirAssembler.XirMark; @@ -92,13 +91,13 @@ } @Override - public String operationString(Formatter operandFmt) { + public String operationString() { StringBuilder buf = new StringBuilder(); if (result.isLegal()) { - buf.append(operandFmt.format(result)).append(" = "); + buf.append(result).append(" = "); } if (targetAddressIndex >= 0) { - buf.append(operandFmt.format(targetAddress())); + buf.append(targetAddress()); } if (inputs.length + alives.length > 1) { buf.append("("); @@ -106,13 +105,13 @@ String sep = ""; for (CiValue input : inputs) { if (input != targetAddress()) { - buf.append(sep).append(operandFmt.format(input)); + buf.append(sep).append(input); sep = ", "; } } for (CiValue input : alives) { if (input != targetAddress()) { - buf.append(sep).append(operandFmt.format(input)).append(" ~"); + buf.append(sep).append(input).append(" ~"); sep = ", "; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRDebugInfo.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRDebugInfo.java Wed Dec 28 18:13:25 2011 -0800 @@ -22,14 +22,16 @@ */ package com.oracle.max.graal.compiler.lir; +import static com.oracle.max.graal.alloc.util.ValueUtil.*; + import java.util.*; import com.oracle.max.graal.compiler.lir.FrameMap.StackBlock; -import com.oracle.max.graal.compiler.util.*; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; import com.sun.cri.ci.*; /** - * This class represents debugging and deoptimization information attached to a LIR instruction. + * This class represents garbage collection and deoptimization information attached to a LIR instruction. */ public class LIRDebugInfo { public final CiFrame topFrame; @@ -45,36 +47,21 @@ this.exceptionEdge = exceptionEdge; } - public CiDebugInfo debugInfo() { - assert debugInfo != null : "debug info not allocated yet"; - return debugInfo; - } - public boolean hasDebugInfo() { return debugInfo != null; } - - /** - * Iterator interface for iterating all variables of a frame state. - */ - public interface ValueProcedure { - /** - * The iterator method. - * - * @param value The variable that is iterated. - * @return The new value that should replace variable, or {@code null} if the variable should remain unchanged. - */ - CiValue doValue(CiValue value); + public CiDebugInfo debugInfo() { + assert debugInfo != null : "debug info not allocated yet"; + return debugInfo; } - /** * Iterates the frame state and calls the {@link ValueProcedure} for every variable. * * @param proc The procedure called for variables. */ - public void forEachLiveStateValue(ValueProcedure proc) { + public void forEachState(ValueProcedure proc) { for (CiFrame cur = topFrame; cur != null; cur = cur.caller()) { processValues(cur.values, proc); } @@ -90,48 +77,41 @@ CiValue value = values[i]; if (value instanceof CiMonitorValue) { CiMonitorValue monitor = (CiMonitorValue) value; - - if (monitor.owner instanceof CiVariable) { - CiValue newValue = proc.doValue(monitor.owner); - if (newValue != null) { - values[i] = new CiMonitorValue(newValue, monitor.lockData, monitor.eliminated); - } + if (processed(monitor.owner)) { + monitor.owner = proc.doValue(monitor.owner); } - } else { - if (value instanceof CiVariable) { - CiValue newValue = proc.doValue(value); - if (newValue != null) { - values[i] = newValue; - } - } else { - // Nothing to do for these types. - assert value == CiValue.IllegalValue || value instanceof CiConstant || value instanceof CiStackSlot || (value instanceof CiVirtualObject && Arrays.asList(virtualObjects).contains(value)); - } + } else if (processed(value)) { + values[i] = proc.doValue(value); } } } - /** - * Create the initial {@link CiDebugInfo} object. This initializes the reference maps. - * This method requires the size of the stack frame to be known, i.e., this method must be called - * after the register allocator has allocated all spill slots and finalized the frame. - * - * @param op The instruction that contains this debug info. - * @param frameMap The frame map used for the compilation. - */ - public void initDebugInfo(LIRInstruction op, FrameMap frameMap) { - CiBitMap frameRefMap = frameMap.initFrameRefMap(); - CiBitMap regRefMap = op.hasCall() ? null : new CiBitMap(frameMap.target.arch.registerReferenceMapBitCount); + private boolean processed(CiValue value) { + if (isIllegal(value)) { + // Ignore dead local variables. + return false; + } else if (isConstant(value)) { + // Ignore constants, the register allocator does not need to see them. + return false; + } else if (isVirtualObject(value)) { + assert Arrays.asList(virtualObjects).contains(value); + return false; + } else { + return true; + } + } - debugInfo = new CiDebugInfo(topFrame, regRefMap, frameRefMap); + + public void finish(CiBitMap registerRefMap, CiBitMap frameRefMap, FrameMap frameMap) { + debugInfo = new CiDebugInfo(topFrame, registerRefMap, frameRefMap); // Add locks that are in the designated frame area. for (CiFrame cur = topFrame; cur != null; cur = cur.caller()) { for (int i = 0; i < cur.numLocks; i++) { - CiMonitorValue lock = (CiMonitorValue) cur.values[i + cur.numLocals + cur.numStack]; + CiMonitorValue lock = (CiMonitorValue) cur.getLockValue(i); if (lock.lockData != null) { - cur.values[i + cur.numLocals + cur.numStack] = new CiMonitorValue(lock.owner, frameMap.toStackSlot((StackBlock) lock.lockData), lock.eliminated); + lock.lockData = frameMap.toStackSlot((StackBlock) lock.lockData); } } } @@ -139,41 +119,11 @@ // Add additional stack slots for outgoing method parameters. if (pointerSlots != null) { for (CiStackSlot v : pointerSlots) { - setReference(v, frameMap); + frameMap.setReference(v, registerRefMap, frameRefMap); } } } - /** - * Marks the specified location as a reference in the reference map of the debug information. - * The location must be a {@link CiRegisterValue} or a {@link CiStackSlot}. Note that a {@link CiAddress} - * cannot be tracked by reference maps, and that a {@link CiConstant} does not have to be added - * manually because it is automatically tracked. - * - * @param location The stack slot or register to be added to the reference map. - * @param frameMap The frame map used for the compilation. - */ - public void setReference(CiValue location, FrameMap frameMap) { - if (location instanceof CiStackSlot) { - CiStackSlot stackSlot = (CiStackSlot) location; - int offset = frameMap.offsetForStackSlot(stackSlot); - assert offset % frameMap.target.wordSize == 0 : "must be aligned"; - setBit(debugInfo.frameRefMap, offset / frameMap.target.wordSize); - - } else if (location instanceof CiRegisterValue) { - CiRegister register = ((CiRegisterValue) location).reg; - setBit(debugInfo.registerRefMap, register.number); - - } else { - throw Util.shouldNotReachHere(); - } - } - - private static void setBit(CiBitMap refMap, int bit) { - assert bit >= 0 && bit < refMap.size() : "register out of range"; - assert !refMap.get(bit) : "Ref map entry already set"; - refMap.set(bit); - } @Override public String toString() {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRInstruction.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRInstruction.java Wed Dec 28 18:13:25 2011 -0800 @@ -23,10 +23,8 @@ package com.oracle.max.graal.compiler.lir; import com.oracle.max.graal.compiler.asm.*; -import com.oracle.max.graal.compiler.lir.LIRDebugInfo.ValueProcedure; import com.oracle.max.graal.compiler.util.*; import com.sun.cri.ci.*; -import com.sun.cri.ci.CiValue.Formatter; /** * The {@code LIRInstruction} class definition. @@ -38,6 +36,20 @@ public static final OperandMode[] OPERAND_MODES = OperandMode.values(); /** + * Iterator interface for iterating over a list of values. + */ + public interface ValueProcedure { + /** + * The iterator method. + * + * @param value The value that is iterated. + * @return The new value to replace the value that was passed in. + */ + CiValue doValue(CiValue value); + } + + + /** * Constants denoting how a LIR instruction uses an operand. */ public enum OperandMode { @@ -209,7 +221,7 @@ public final void setOperandAt(OperandMode mode, int index, CiValue location) { assert index < operandCount(mode); assert location.kind != CiKind.Illegal; - assert operandAt(mode, index).isVariable() && operandAt(mode, index).kind == location.kind; + assert operandAt(mode, index).kind == location.kind; switch (mode) { case Output: result = location; break; case Input: inputs[index] = location; break; @@ -219,11 +231,39 @@ } } - public final void forEachOperand(OperandMode mode, ValueProcedure proc) { - for (int i = 0; i < operandCount(mode); i++) { - CiValue newValue = proc.doValue(operandAt(mode, i)); - if (newValue != null) { - setOperandAt(mode, i, newValue); + public final void forEachInput(ValueProcedure proc) { + for (int i = 0; i < inputs.length; i++) { + inputs[i] = proc.doValue(inputs[i]); + } + } + + public final void forEachAlive(ValueProcedure proc) { + for (int i = 0; i < alives.length; i++) { + alives[i] = proc.doValue(alives[i]); + } + } + + public final void forEachTemp(ValueProcedure proc) { + for (int i = 0; i < temps.length; i++) { + temps[i] = proc.doValue(temps[i]); + } + } + + public final void forEachOutput(ValueProcedure proc) { + if (result != CiValue.IllegalValue) { + result = proc.doValue(result); + } + } + + public final void forEachState(ValueProcedure proc) { + if (info != null) { + info.forEachState(proc); + + if (this instanceof LIRXirInstruction) { + LIRXirInstruction xir = (LIRXirInstruction) this; + if (xir.infoAfter != null) { + xir.infoAfter.forEachState(proc); + } } } } @@ -255,11 +295,6 @@ } - @Override - public String toString() { - return toString(Formatter.DEFAULT); - } - public final String toStringWithIdPrefix() { if (id != -1) { return String.format("%4d %s", id, toString()); @@ -270,21 +305,21 @@ /** * Gets the operation performed by this instruction in terms of its operands as a string. */ - public String operationString(Formatter operandFmt) { + public String operationString() { StringBuilder buf = new StringBuilder(); if (result.isLegal()) { - buf.append(operandFmt.format(result)).append(" = "); + buf.append(result).append(" = "); } if (inputs.length + alives.length > 1) { buf.append("("); } String sep = ""; for (CiValue input : inputs) { - buf.append(sep).append(operandFmt.format(input)); + buf.append(sep).append(input); sep = ", "; } for (CiValue input : alives) { - buf.append(sep).append(operandFmt.format(input)).append(" ~"); + buf.append(sep).append(input).append(" ~"); sep = ", "; } if (inputs.length + alives.length > 1) { @@ -296,7 +331,7 @@ } sep = ""; for (CiValue temp : temps) { - buf.append(sep).append(operandFmt.format(temp)); + buf.append(sep).append(temp); sep = ", "; } if (temps.length > 0) { @@ -305,7 +340,7 @@ return buf.toString(); } - protected static String refMapToString(CiDebugInfo debugInfo, Formatter operandFmt) { + protected static String refMapToString(CiDebugInfo debugInfo) { StringBuilder buf = new StringBuilder(); if (debugInfo.hasStackRefMap()) { CiBitMap bm = debugInfo.frameRefMap; @@ -313,7 +348,7 @@ if (buf.length() != 0) { buf.append(", "); } - buf.append(operandFmt.format(CiStackSlot.get(CiKind.Object, slot))); + buf.append(CiStackSlot.get(CiKind.Object, slot)); } } if (debugInfo.hasRegisterRefMap()) { @@ -328,12 +363,12 @@ return buf.toString(); } - protected void appendDebugInfo(StringBuilder buf, Formatter operandFmt) { + protected void appendDebugInfo(StringBuilder buf) { if (info != null) { buf.append(" [bci:").append(info.topFrame.bci); if (info.hasDebugInfo()) { CiDebugInfo debugInfo = info.debugInfo(); - String refmap = refMapToString(debugInfo, operandFmt); + String refmap = refMapToString(debugInfo); if (refmap.length() != 0) { buf.append(", refmap(").append(refmap.trim()).append(')'); } @@ -342,9 +377,10 @@ } } - public String toString(Formatter operandFmt) { - StringBuilder buf = new StringBuilder(name()).append(' ').append(operationString(operandFmt)); - appendDebugInfo(buf, operandFmt); + @Override + public String toString() { + StringBuilder buf = new StringBuilder(name()).append(' ').append(operationString()); + appendDebugInfo(buf); return buf.toString(); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRPhiMapping.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRPhiMapping.java Wed Dec 28 18:13:25 2011 -0800 @@ -25,15 +25,16 @@ import java.util.*; import com.oracle.max.graal.compiler.gen.*; -import com.oracle.max.graal.compiler.lir.LIRDebugInfo.ValueProcedure; +import com.oracle.max.graal.compiler.lir.LIRInstruction.ValueProcedure; import com.oracle.max.graal.nodes.*; +import com.oracle.max.graal.nodes.PhiNode.*; import com.sun.cri.ci.*; public class LIRPhiMapping { private final LIRBlock block; - private final CiValue[][] inputs; - private final CiValue[] results; + private CiValue[][] inputs; + private CiValue[] results; public LIRPhiMapping(LIRBlock block, LIRGenerator gen) { this.block = block; @@ -42,23 +43,43 @@ MergeNode mergeNode = (MergeNode) block.firstNode(); List<PhiNode> phis = mergeNode.phis().snapshot(); - int numPhis = phis.size(); + for (int i = 0; i < phis.size(); i++) { + PhiNode phi = phis.get(i); + if (phi.type() == PhiType.Value) { + gen.setResult(phi, gen.newVariable(phi.kind())); + } + } + } + + public void fillInputs(LIRGenerator gen) { + assert block.firstNode() instanceof MergeNode : "phi functions are only present at control flow merges"; + MergeNode mergeNode = (MergeNode) block.firstNode(); + List<PhiNode> phis = mergeNode.phis().snapshot(); + + int numPhis = 0; + for (int i = 0; i < phis.size(); i++) { + if (phis.get(i).type() == PhiType.Value) { + numPhis++; + } + } int numPreds = block.numberOfPreds(); results = new CiValue[numPhis]; - for (int i = 0; i < numPhis; i++) { - CiVariable opd = gen.newVariable(phis.get(i).kind()); - gen.setResult(phis.get(i), opd); - results[i] = opd; - } + inputs = new CiValue[numPreds][numPhis]; - inputs = new CiValue[numPreds][numPhis]; - for (int i = 0; i < numPreds; i++) { - assert i == mergeNode.phiPredecessorIndex((FixedNode) block.predAt(i).lastNode()) : "block predecessors and node predecessors must have same order"; - for (int j = 0; j < numPhis; j++) { - inputs[i][j] = gen.operand(phis.get(j).valueAt(i)); + int phiIdx = 0; + for (int i = 0; i < phis.size(); i++) { + PhiNode phi = phis.get(i); + if (phi.type() == PhiType.Value) { + results[phiIdx] = gen.operand(phi); + for (int j = 0; j < numPreds; j++) { + assert j == mergeNode.phiPredecessorIndex((FixedNode) block.predAt(j).lastNode()) : "block predecessors and node predecessors must have same order"; + inputs[j][phiIdx] = gen.operand(phi.valueAt(j)); + } + phiIdx++; } } + assert phiIdx == numPhis; } public CiValue[] results() { @@ -73,19 +94,29 @@ public void forEachInput(LIRBlock pred, ValueProcedure proc) { CiValue[] predInputs = inputs(pred); for (int i = 0; i < predInputs.length; i++) { - CiValue newValue = proc.doValue(predInputs[i]); - if (newValue != null) { - predInputs[i] = newValue; - } + predInputs[i] = proc.doValue(predInputs[i]); } } public void forEachOutput(ValueProcedure proc) { for (int i = 0; i < results.length; i++) { - CiValue newValue = proc.doValue(results[i]); - if (newValue != null) { - results[i] = newValue; - } + results[i] = proc.doValue(results[i]); + } + } + + public void forEachInput(LIRBlock pred, PhiValueProcedure proc) { + CiValue[] predInputs = inputs(pred); + for (int i = 0; i < predInputs.length; i++) { + proc.doValue(predInputs[i], results[i]); } } + + public interface PhiValueProcedure { + void doValue(CiValue input, CiValue output); + } + + @Override + public String toString() { + return "PhiMapping for " + block + ": " + Arrays.toString(results); + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRXirInstruction.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/lir/LIRXirInstruction.java Wed Dec 28 18:13:25 2011 -0800 @@ -25,7 +25,6 @@ import java.util.*; import com.sun.cri.ci.*; -import com.sun.cri.ci.CiValue.Formatter; import com.sun.cri.ri.*; import com.sun.cri.xir.*; @@ -98,17 +97,17 @@ * Prints this instruction. */ @Override - public String operationString(Formatter operandFmt) { - return toString(operandFmt); + public String operationString() { + return toString(); } @Override - public String toString(Formatter operandFmt) { + public String toString() { StringBuilder sb = new StringBuilder(); sb.append("XIR: "); if (result().isLegal()) { - sb.append(operandFmt.format(result()) + " = "); + sb.append(result() + " = "); } sb.append(snippet.template); @@ -119,14 +118,9 @@ sb.append(", "); } if (a.constant != null) { - sb.append(operandFmt.format(a.constant)); + sb.append(a.constant); } else { - Object o = a.object; - if (o instanceof CiValue) { - sb.append(operandFmt.format((CiValue) o)); - } else { - sb.append(o); - } + sb.append(a.object); } } sb.append(')'); @@ -147,7 +141,7 @@ sb.append(' ').append(mode.name().toLowerCase()).append("=("); HashSet<String> operands = new HashSet<>(); for (int i = 0; i < n; i++) { - String operand = operandFmt.format(operandAt(mode, i)); + String operand = operandAt(mode, i).toString(); if (!operands.contains(operand)) { if (!operands.isEmpty()) { sb.append(", "); @@ -160,7 +154,7 @@ } } - appendDebugInfo(sb, operandFmt); + appendDebugInfo(sb); return sb.toString(); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java Wed Dec 28 18:13:25 2011 -0800 @@ -43,6 +43,11 @@ private int loopIndex = -1; private double probability; + /** + * For loop headers only: The list of all blocks in this loop. + */ + public List<Block> loopBlocks; + private Node firstNode; private Node lastNode;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Wed Dec 28 18:13:25 2011 -0800 @@ -283,34 +283,36 @@ Block loopBeginBlock = nodeToBlock.get(loopEnd.loopBegin()); block.addSuccessor(loopBeginBlock); BitMap map = new BitMap(blocks.size()); + loopBeginBlock.loopBlocks = new ArrayList<>(); markBlocks(block, loopBeginBlock, map, loopCount++, block.loopDepth()); assert loopBeginBlock.loopDepth() == block.loopDepth() && loopBeginBlock.loopIndex() == block.loopIndex(); } } } - private void markBlocks(Block block, Block endBlock, BitMap map, int loopIndex, int initialDepth) { + private void markBlocks(Block block, Block loopBeginBlock, BitMap map, int loopIndex, int initialDepth) { if (map.get(block.blockID())) { return; } map.set(block.blockID()); + loopBeginBlock.loopBlocks.add(block); if (block.loopDepth() <= initialDepth) { assert block.loopDepth() == initialDepth; block.setLoopIndex(loopIndex); } block.setLoopDepth(block.loopDepth() + 1); - if (block == endBlock) { + if (block == loopBeginBlock) { return; } for (Block pred : block.getPredecessors()) { - markBlocks(pred, endBlock, map, loopIndex, initialDepth); + markBlocks(pred, loopBeginBlock, map, loopIndex, initialDepth); } if (block.isLoopHeader()) { - markBlocks(nodeToBlock.get(((LoopBeginNode) block.firstNode()).loopEnd()), endBlock, map, loopIndex, initialDepth); + markBlocks(nodeToBlock.get(((LoopBeginNode) block.firstNode()).loopEnd()), loopBeginBlock, map, loopIndex, initialDepth); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ControlFlowOpcode.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64ControlFlowOpcode.java Wed Dec 28 18:13:25 2011 -0800 @@ -32,7 +32,6 @@ import com.sun.cri.ci.*; import com.sun.cri.ci.CiAddress.Scale; import com.sun.cri.ci.CiTargetMethod.JumpTable; -import com.sun.cri.ci.CiValue.Formatter; public class AMD64ControlFlowOpcode { @@ -50,7 +49,7 @@ } @Override - public String operationString(Formatter operandFmt) { + public String operationString() { return label.toString(); } }; @@ -86,7 +85,7 @@ } @Override - public String operationString(Formatter operandFmt) { + public String operationString() { return "[" + destination + "]"; } }; @@ -106,7 +105,7 @@ } @Override - public String operationString(Formatter operandFmt) { + public String operationString() { return cond.operator + " [" + destination + "]"; } }; @@ -125,7 +124,7 @@ } @Override - public String operationString(Formatter operandFmt) { + public String operationString() { return cond.operator + " [" + destination + "]" + (unorderedIsTrue ? " unorderedIsTrue" : " unorderedIsFalse"); } }; @@ -147,8 +146,8 @@ } @Override - public String operationString(Formatter operandFmt) { - StringBuilder buf = new StringBuilder(super.operationString(operandFmt)); + public String operationString() { + StringBuilder buf = new StringBuilder(super.operationString()); buf.append("\ndefault: [").append(defaultTarget).append(']'); int key = lowKey; for (LabelRef l : targets) { @@ -181,8 +180,8 @@ } @Override - public String operationString(Formatter operandFmt) { - return condition.toString() + " " + super.operationString(operandFmt); + public String operationString() { + return condition.toString() + " " + super.operationString(); } }; } @@ -202,8 +201,8 @@ } @Override - public String operationString(Formatter operandFmt) { - return condition.toString() + " unordered=" + unorderedIsTrue + " " + super.operationString(operandFmt); + public String operationString() { + return condition.toString() + " unordered=" + unorderedIsTrue + " " + super.operationString(); } }; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64DivOpcode.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/target/amd64/AMD64DivOpcode.java Wed Dec 28 18:13:25 2011 -0800 @@ -37,7 +37,7 @@ public LIRInstruction create(CiRegisterValue result, LIRDebugInfo info, CiRegisterValue left, CiVariable right) { CiValue[] inputs = new CiValue[] {left}; CiValue[] alives = new CiValue[] {right}; - CiValue[] temps = new CiValue[] {AMD64.rdx.asValue()}; + CiValue[] temps = new CiValue[] {result.reg == AMD64.rax ? AMD64.rdx.asValue(result.kind) : AMD64.rax.asValue(result.kind)}; return new AMD64LIRInstruction(this, result, info, inputs, alives, temps) { @Override
--- a/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/HotSpotXirGenerator.java Wed Dec 28 18:12:08 2011 -0800 +++ b/graal/com.oracle.max.graal.hotspot/src/com/oracle/max/graal/hotspot/HotSpotXirGenerator.java Wed Dec 28 18:13:25 2011 -0800 @@ -119,7 +119,7 @@ XirOperand cache = asm.createRegisterTemp("cache (rax)", target.wordKind, AMD64.rax); CiCallingConvention conventions = registerConfig.getCallingConvention(JavaCallee, new CiKind[] {CiKind.Object}, target, false); - XirOperand receiver = asm.createRegisterTemp("receiver", target.wordKind, conventions.locations[0].asRegister()); + XirOperand receiver = asm.createRegister("receiver", target.wordKind, conventions.locations[0].asRegister()); asm.pload(target.wordKind, temp, receiver, asm.i(config.hubOffset), false); asm.jneq(unverifiedStub, cache, temp); @@ -639,7 +639,7 @@ @Override protected XirTemplate create(CiXirAssembler asm, long flags) { - asm.restart(); + asm.restart(CiKind.Void); XirParameter object = asm.createInputParameter("object", CiKind.Object); final XirOperand hub; hub = asm.createConstantInputParameter("hub", CiKind.Object); @@ -669,7 +669,7 @@ asm.callRuntime(CiRuntimeCall.Deoptimize, null); asm.shouldNotReachHere(); - return asm.finishTemplate(object, "checkcast"); + return asm.finishTemplate("checkcast"); } };