Mercurial > hg > truffle
changeset 6316:2e25b9c14b84
Temporarily remove experimental register allocators.
| author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
|---|---|
| date | Thu, 06 Sep 2012 15:32:08 +0200 |
| parents | 3aaf213e730e |
| children | 3ee3eb48e683 |
| files | graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/AssignRegisters.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/DataFlowAnalysis.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/LinearScanAllocator.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/ResolveDataFlow.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/SpillAllAllocator.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/IntervalPrinter.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/Location.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/LocationMap.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/LocationUtil.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/MoveResolver.java graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/RegisterVerifier.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/Interval.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java |
| diffstat | 18 files changed, 17 insertions(+), 2726 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/AssignRegisters.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,117 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.simple; - -import static com.oracle.graal.alloc.util.LocationUtil.*; - -import java.util.*; - -import com.oracle.graal.alloc.util.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; - -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 BitSet curRegisterRefMap; - private BitSet curFrameRefMap; - - public void execute() { - ValueProcedure useProc = new ValueProcedure() { @Override public Value doValue(Value value) { return use(value); } }; - ValueProcedure defProc = new ValueProcedure() { @Override public Value doValue(Value value) { return def(value); } }; - ValueProcedure setReferenceProc = new ValueProcedure() { @Override public Value doValue(Value value) { return setReference(value); } }; - StateProcedure finishProc = new StateProcedure() { @Override public void doState(LIRFrameState state) { state.finish((BitSet) (curRegisterRefMap.clone()), (BitSet) (curFrameRefMap.clone()), frameMap); } }; - - Debug.log("==== start assign registers ===="); - for (int i = lir.linearScanOrder().size() - 1; i >= 0; i--) { - Block block = lir.linearScanOrder().get(i); - Debug.log("start block %s", block); - - 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); - Debug.log(" op %d %s", op.id(), op); - - op.forEachOutput(defProc); - op.forEachTemp(defProc); - op.forEachState(useProc); - op.forEachAlive(useProc); - - // Build the reference map for the GC. - op.forEachState(finishProc); - - // 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); - } - Debug.log("end block %s", block); - } - Debug.log("==== end assign registers ===="); - } - - private Value use(Value value) { - Debug.log(" use %s", value); - if (isLocation(value)) { - Value location = asLocation(value).location; - frameMap.setReference(location, curRegisterRefMap, curFrameRefMap); - return location; - } else { - frameMap.setReference(value, curRegisterRefMap, curFrameRefMap); - return value; - } - } - - private Value def(Value value) { - Debug.log(" def %s", value); - if (isLocation(value)) { - Value location = asLocation(value).location; - frameMap.clearReference(location, curRegisterRefMap, curFrameRefMap); - return location; - } else { - frameMap.clearReference(value, curRegisterRefMap, curFrameRefMap); - return value; - } - } - - private Value setReference(Value value) { - Debug.log(" setReference %s", value); - frameMap.setReference(asLocation(value).location, curRegisterRefMap, curFrameRefMap); - return value; - } - - protected abstract LocationMap locationsForBlockEnd(Block block); -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/DataFlowAnalysis.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,303 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.simple; - -import static com.oracle.graal.api.code.ValueUtil.*; -import static com.oracle.graal.lir.LIRValueUtil.*; - -import java.util.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; - -public class DataFlowAnalysis { - private final LIR lir; - private final RegisterConfig registerConfig; - - public DataFlowAnalysis(LIR lir, RegisterConfig registerConfig) { - this.lir = lir; - this.registerConfig = registerConfig; - } - - public void execute() { - numberInstructions(); - backwardDataFlow(); - } - - - private List<Block> blocks() { - return lir.linearScanOrder(); - } - - private int numVariables() { - return lir.numVariables(); - } - - private boolean isAllocatableRegister(Value value) { - return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable(); - } - - - private int[] definitions; - private BitSet[] blockLiveIn; - private Block[] opIdBlock; - private Object[] opIdKilledValues; - - - public BitSet liveIn(Block block) { - return blockLiveIn[block.getId()]; - } - private void setLiveIn(Block block, BitSet liveIn) { - blockLiveIn[block.getId()] = liveIn; - } - - private Block blockOf(int opId) { - return opIdBlock[opId >> 1]; - } - private void setBlockOf(int opId, Block 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 Value) { - Value newValue = proc.doValue((Value) entry, null, null); - assert newValue == entry : "procedure does not allow to change values"; - } else { - Value[] values = (Value[]) entry; - for (int i = 0; i < values.length; i++) { - if (values[i] != null) { - Value newValue = proc.doValue(values[i], null, null); - assert newValue == values[i] : "procedure does not allow to change values"; - } - } - } - } - - public int definition(Variable value) { - return definitions[value.index]; - } - - /** - * Numbers all instructions in all blocks. The numbering follows the linear scan order. - */ - private void numberInstructions() { - ValueProcedure defProc = new ValueProcedure() { @Override public Value doValue(Value value) { return setDef(value); } }; - - int numInstructions = 0; - for (Block block : blocks()) { - numInstructions += block.lir.size(); - } - opIdBlock = new Block[numInstructions]; - opIdKilledValues = new Object[numInstructions << 1]; - definitions = new int[numVariables()]; - - curOpId = 0; - for (Block block : blocks()) { - for (LIRInstruction op : block.lir) { - op.setId(curOpId); - setBlockOf(curOpId, block); - - op.forEachTemp(defProc); - op.forEachOutput(defProc); - - curOpId += 2; // numbering of lirOps by two - } - } - assert curOpId == numInstructions << 1; - } - - private Value setDef(Value 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 Value doValue(Value value) { return use(value, curOpId); } }; - ValueProcedure aliveProc = new ValueProcedure() { @Override public Value doValue(Value value) { return use(value, curOpId + 1); } }; - ValueProcedure tempProc = new ValueProcedure() { @Override public Value doValue(Value value) { return def(value, true); } }; - ValueProcedure outputProc = new ValueProcedure() { @Override public Value doValue(Value value) { return def(value, false); } }; - - blockLiveIn = new BitSet[blocks().size()]; - registerLive = new BitSet(); - - Debug.log("==== start backward data flow analysis ===="); - for (int i = blocks().size() - 1; i >= 0; i--) { - Block block = blocks().get(i); - Debug.log("start block %s loop %s", block, block.getLoop()); - - variableLive = new BitSet(); - for (Block sux : block.getSuccessors()) { - BitSet suxLive = liveIn(sux); - if (suxLive != null) { - Debug.log(" sux %s suxLive: %s", sux, suxLive); - variableLive.or(suxLive); - } - } - - 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(); - Debug.log(" 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); - } - - assert registerLive.isEmpty() : "no fixed register must be alive after processing a block"; - assert liveIn(block) == null; - setLiveIn(block, variableLive); - - if (block.isLoopHeader()) { - Debug.log(" 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.getLoop().blocks) { - BitSet loopLiveIn = liveIn(loop); - assert loopLiveIn != null : "All loop blocks must have been processed before the loop header"; - loopLiveIn.or(variableLive); - Debug.log(" block %s loopLiveIn %s", loop, loopLiveIn); - } - } - - Debug.log("end block %s variableLive: %s", block, variableLive); - } - Debug.log("==== end backward data flow analysis ===="); - } - - private Value use(Value value, int killOpId) { - Debug.log(" use %s", value); - if (isVariable(value)) { - int variableIdx = asVariable(value).index; - assert definitions[variableIdx] < curOpId; - if (!variableLive.get(variableIdx)) { - Debug.log(" set live variable %d", variableIdx); - variableLive.set(variableIdx); - kill(value, killOpId); - } - - } else if (isAllocatableRegister(value)) { - int regNum = asRegister(value).number; - if (!registerLive.get(regNum)) { - Debug.log(" set live register %d", regNum); - registerLive.set(regNum); - kill(value, killOpId); - } - } - return value; - } - - private Value def(Value value, boolean isTemp) { - Debug.log(" def %s", value); - if (isVariable(value)) { - int variableIdx = asVariable(value).index; - assert definitions[variableIdx] == curOpId; - if (variableLive.get(variableIdx)) { - Debug.log(" 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)) { - Debug.log(" 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(Value value, int opId) { - if (opId < 0) { - return; - } - if (isVariable(value)) { - int defOpId = definitions[asVariable(value).index]; - assert defOpId > 0 && defOpId <= opId; - - Block defBlock = blockOf(defOpId); - Block useBlock = blockOf(opId); - - if (useBlock.getLoop() != null && useBlock.getLoop() != defBlock.getLoop()) { - // 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. - Debug.log(" no kill because use in %s, definition in %s", useBlock.getLoop(), defBlock.getLoop()); - return; - } - } - Debug.log(" kill %s at %d", value, opId); - - Object entry = killedValues(opId); - if (entry == null) { - setKilledValues(opId, value); - } else if (entry instanceof Value) { - setKilledValues(opId, new Value[] {(Value) entry, value}); - } else { - Value[] killed = (Value[]) 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; - } - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/LinearScanAllocator.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,613 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.simple; - -import static com.oracle.graal.alloc.util.LocationUtil.*; -import java.util.*; - -import com.oracle.graal.alloc.util.*; -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.code.Register.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; - -public class LinearScanAllocator { - private final LIR lir; - private final FrameMap frameMap; - - private final DataFlowAnalysis dataFlow; - - public LinearScanAllocator(LIR lir, FrameMap frameMap) { - this.lir = lir; - this.frameMap = frameMap; - - this.dataFlow = new DataFlowAnalysis(lir, frameMap.registerConfig); - this.blockBeginLocations = new LocationMap[lir.linearScanOrder().size()]; - this.blockEndLocations = new LocationMap[lir.linearScanOrder().size()]; - this.moveResolver = new MoveResolverImpl(lir, frameMap); - - this.variableLastUse = new int[lir.numVariables()]; - } - - private class MoveResolverImpl extends MoveResolver { - public MoveResolverImpl(LIR lir, FrameMap frameMap) { - super(lir, frameMap); - } - - @Override - protected Value scratchRegister(Variable spilled) { - GraalInternalError.shouldNotReachHere("needs working implementation"); - - EnumMap<RegisterFlag, Register[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters(); - Register[] availableRegs = categorizedRegs.get(spilled.flag); - for (Register reg : availableRegs) { - if (curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null) { - return reg.asValue(spilled.kind); - } - } - throw new BailoutException("No register found"); - } - } - - private class ResolveDataFlowImpl extends ResolveDataFlow { - public ResolveDataFlowImpl(LIR lir, MoveResolver moveResolver, DataFlowAnalysis dataFlow) { - super(lir, moveResolver, dataFlow); - } - - @Override - protected LocationMap locationsForBlockBegin(Block block) { - return beginLocationsFor(block); - } - - @Override - protected LocationMap locationsForBlockEnd(Block block) { - return endLocationsFor(block); - } - } - - private class AssignRegistersImpl extends AssignRegisters { - public AssignRegistersImpl(LIR lir, FrameMap frameMap) { - super(lir, frameMap); - } - - @Override - protected LocationMap locationsForBlockEnd(Block block) { - return endLocationsFor(block); - } - } - - - private int maxRegisterNum() { - return frameMap.target.arch.registers.length; - } - - private boolean isAllocatableRegister(Value value) { - return isRegister(value) && frameMap.registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable(); - } - - - private final LocationMap[] blockBeginLocations; - - private LocationMap beginLocationsFor(Block block) { - return blockBeginLocations[block.getId()]; - } - private void setBeginLocationsFor(Block block, LocationMap locations) { - blockBeginLocations[block.getId()] = locations; - } - - private final LocationMap[] blockEndLocations; - - private LocationMap endLocationsFor(Block block) { - return blockEndLocations[block.getId()]; - } - private void setEndLocationsFor(Block block, LocationMap locations) { - blockEndLocations[block.getId()] = locations; - } - - private final int[] variableLastUse; - - private int lastUseFor(Variable variable) { - return variableLastUse[variable.index]; - } - - private void setLastUseFor(Variable variable, int lastUse) { - variableLastUse[variable.index] = lastUse; - } - - private MoveResolver moveResolver; - private LocationMap curLocations; - private Value[] curInRegisterState; - private Value[] curOutRegisterState; - private BitSet curLiveIn; - private LIRInstruction curOp; - - /** - * The spill slot for a variable, if the variable has ever been spilled. - */ - private LocationMap canonicalSpillLocations; - - /** - * The register that a variable got assigned at its definition, and so it should get that register when reloading after spilling. - */ - private LocationMap hintRegisterLocations; - - public void execute() { - assert LIRVerifier.verify(true, lir, frameMap); - - dataFlow.execute(); - IntervalPrinter.printBeforeAllocation("Before register allocation", lir, frameMap.registerConfig, dataFlow); - - allocate(); - - IntervalPrinter.printAfterAllocation("After linear scan allocation", lir, frameMap.registerConfig, dataFlow, blockEndLocations); - - ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver, dataFlow); - resolveDataFlow.execute(); - frameMap.finish(); - - IntervalPrinter.printAfterAllocation("After resolve data flow", lir, frameMap.registerConfig, dataFlow, blockEndLocations); - assert RegisterVerifier.verify(lir, frameMap); - - AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap); - assignRegisters.execute(); - - Debug.dump(lir, "After register asignment"); - assert LIRVerifier.verify(false, lir, frameMap); - } - - private void allocate() { - ValueProcedure recordUseProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return recordUse(value); } }; - ValueProcedure killNonLiveProc = new ValueProcedure() { @Override public Value doValue(Value value) { return killNonLive(value); } }; - ValueProcedure unblockProc = new ValueProcedure() { @Override public Value doValue(Value value) { return unblock(value); } }; - ValueProcedure killProc = new ValueProcedure() { @Override public Value doValue(Value value) { return kill(value); } }; - ValueProcedure blockProc = new ValueProcedure() { @Override public Value doValue(Value value) { return block(value); } }; - ValueProcedure useProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return use(value, mode, flags); } }; - ValueProcedure defProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return def(value, mode, flags); } }; - - Debug.log("==== start linear scan allocation ===="); - canonicalSpillLocations = new LocationMap(lir.numVariables()); - hintRegisterLocations = new LocationMap(lir.numVariables()); - curInRegisterState = new Value[maxRegisterNum()]; - curOutRegisterState = new Value[maxRegisterNum()]; - for (Block block : lir.linearScanOrder()) { - Debug.log("start block %s %s", block, block.getLoop()); - - Arrays.fill(curOutRegisterState, null); - if (block.getDominator() != null) { - LocationMap dominatorState = endLocationsFor(block.getDominator()); - curLocations = new LocationMap(dominatorState); - // Clear out all variables that are not live at the begin of this block - curLiveIn = dataFlow.liveIn(block); - curLocations.forEachLocation(killNonLiveProc); - assert checkInputState(block); - } else { - curLocations = new LocationMap(lir.numVariables()); - } - Debug.log(logCurrentState()); - - for (int opIdx = 0; opIdx < block.lir.size(); opIdx++) { - LIRInstruction op = block.lir.get(opIdx); - curOp = op; - - Debug.log(" op %d %s", op.id(), op); - - System.arraycopy(curOutRegisterState, 0, curInRegisterState, 0, curOutRegisterState.length); - - // Unblock fixed registers that are only used for inputs in curOutRegisterState. - dataFlow.forEachKilled(op, false, unblockProc); - // Block fixed registers defined by this instruction in curOutRegisterState. - op.forEachTemp(blockProc); - op.forEachOutput(blockProc); - - op.forEachInput(recordUseProc); - op.forEachAlive(recordUseProc); - - 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(useProc); - op.forEachInput(useProc); - - dataFlow.forEachKilled(op, false, killProc); - - if (op.hasCall()) { - spillCallerSaveRegisters(); - } - if (op instanceof StandardOp.PhiLabelOp) { - assert opIdx == 0; - phiRegisterHints(block); - } - - op.forEachOutput(defProc); - op.forEachTemp(defProc); - - // Fixed temp and output registers can evict variables from their assigned register, allocate new location for them. - fixupEvicted(); - // State values are the least critical and can get the leftover registers (or stack slots if no more register available). - op.forEachState(useProc); - - if (opIdx == 0) { - assert !moveResolver.hasMappings() : "cannot insert spill moves before label"; - setBeginLocationsFor(block, new LocationMap(curLocations)); - } - moveResolver.resolve(); - - dataFlow.forEachKilled(op, true, unblockProc); - dataFlow.forEachKilled(op, true, killProc); - - curOp = null; - } - - assert endLocationsFor(block) == null; - setEndLocationsFor(block, curLocations); - - logCurrentState(); - Debug.log("end block %s", block); - } - - moveResolver.finish(); - Debug.log("==== end linear scan allocation ===="); - } - - private Value killNonLive(Value value) { - assert isLocation(value); - if (!curLiveIn.get(asLocation(value).variable.index)) { - return null; - - } else if (isAllocatableRegister(asLocation(value).location)) { - int regNum = asRegister(asLocation(value).location).number; - assert curOutRegisterState[regNum] == null; - curOutRegisterState[regNum] = value; - } - return value; - } - - private Value unblock(Value value) { - if (isAllocatableRegister(value)) { - Debug.log(" unblock register %s", value); - int regNum = asRegister(value).number; - assert curOutRegisterState[regNum] == value; - curOutRegisterState[regNum] = null; - } - return value; - } - - private Value kill(Value value) { - if (isVariable(value)) { - Location location = curLocations.get(asVariable(value)); - Debug.log(" kill location %s", location); - if (isRegister(location.location)) { - int regNum = asRegister(location.location).number; - if (curOutRegisterState[regNum] == location) { - curOutRegisterState[regNum] = null; - } - } - curLocations.clear(asVariable(value)); - } - return value; - } - - - private Value block(Value value) { - if (isAllocatableRegister(value)) { - Debug.log(" block %s", value); - int regNum = asRegister(value).number; - assert curOutRegisterState[regNum] == null || curOutRegisterState[regNum] instanceof Location; - curOutRegisterState[regNum] = value; - } - return value; - } - - private void spillCallerSaveRegisters() { - Debug.log(" spill caller save registers in curInRegisterState %s", Arrays.toString(curInRegisterState)); - for (Register reg : frameMap.registerConfig.getCallerSaveRegisters()) { - Value in = curInRegisterState[reg.number]; - if (in != null && isLocation(in)) { - spill(asLocation(in)); - } - } - } - - private Value recordUse(Value value) { - if (isVariable(value)) { - assert lastUseFor(asVariable(value)) <= curOp.id(); - setLastUseFor(asVariable(value), curOp.id()); - - } - return value; - } - - private Value use(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { - assert mode == OperandMode.USE || mode == OperandMode.ALIVE; - if (isVariable(value)) { - // State values are not recorded beforehand because it does not matter if they are spilled. Still, it is necessary to record them as used now. - recordUse(value); - - Location curLoc = curLocations.get(asVariable(value)); - if (isStackSlot(curLoc.location) && flags.contains(OperandFlag.STACK)) { - Debug.log(" use %s %s: use current stack slot %s", mode, value, curLoc.location); - return curLoc; - } - if (isRegister(curLoc.location)) { - int regNum = asRegister(curLoc.location).number; - assert curInRegisterState[regNum] == curLoc; - if (mode == OperandMode.USE || curOutRegisterState[regNum] == curLoc) { - Debug.log(" use %s %s: use current register %s", mode, value, curLoc.location); - return curLoc; - } - } - - Debug.log(" use %s %s", mode, value); - - Location newLoc = allocateRegister(asVariable(value), mode, flags); - if (newLoc != curLoc) { - moveResolver.add(curLoc, newLoc); - } - return newLoc; - } else { - assert !isAllocatableRegister(value) || curInRegisterState[asRegister(value).number] == value; - } - return value; - } - - private static final EnumSet<OperandFlag> SPILL_FLAGS = EnumSet.of(OperandFlag.REG, OperandFlag.STACK); - - private Value def(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { - assert mode == OperandMode.TEMP || mode == OperandMode.DEF; - if (isVariable(value)) { - Debug.log(" def %s %s", mode, value); - assert curLocations.get(asVariable(value)) == null; - - Location newLoc = allocateRegister(asVariable(value), mode, flags); - return newLoc; - } - return value; - } - - - private void fixupEvicted() { - for (int i = 0; i < curInRegisterState.length; i++) { - Value in = curInRegisterState[i]; - Value out = curOutRegisterState[i]; - - if (in != null && in != out && isLocation(in) && curLocations.get(asLocation(in).variable) == in) { - Debug.log(" %s was evicted by %s, need to allocate new location", in, out); - Location oldLoc = asLocation(in); - Location newLoc = allocateRegister(oldLoc.variable, OperandMode.ALIVE, SPILL_FLAGS); - assert oldLoc != newLoc; - moveResolver.add(oldLoc, newLoc); - } - - - } - } - - - private void phiRegisterHints(Block block) { - Debug.log(" phi register hints for %s", block); - Value[] phiDefinitions = ((StandardOp.PhiLabelOp) block.lir.get(0)).getPhiDefinitions(); - for (Block pred : block.getPredecessors()) { - Value[] phiInputs = ((StandardOp.PhiJumpOp) pred.lir.get(pred.lir.size() - 1)).getPhiInputs(); - - for (int i = 0; i < phiDefinitions.length; i++) { - Value phiDefinition = phiDefinitions[i]; - Value phiInput = phiInputs[i]; - - if (isVariable(phiDefinition)) { - Location hintResult = processRegisterHint(asVariable(phiDefinition), OperandMode.DEF, phiInput); - if (hintResult != null) { - phiDefinitions[i] = hintResult; - } - } - } - } - } - - private Location processRegisterHint(Variable variable, OperandMode mode, Value registerHint) { - if (registerHint == null) { - return null; - } - Debug.log(" try registerHint for %s %s: %s", mode, variable, registerHint); - Register hint = null; - if (isRegister(registerHint)) { - hint = asRegister(registerHint); - } else if (isLocation(registerHint) && isRegister(asLocation(registerHint).location)) { - hint = asRegister(asLocation(registerHint).location); - } - if (hint != null && hint.isSet(variable.flag) && isFree(hint, mode)) { - return selectRegister(hint, variable, mode); - } - return null; - } - - private Location allocateRegister(final Variable variable, final OperandMode mode, EnumSet<OperandFlag> flags) { - if (flags.contains(OperandFlag.HINT)) { - Value hintResult = curOp.forEachRegisterHint(variable, mode, new ValueProcedure() { - @Override - public Value doValue(Value registerHint) { - return processRegisterHint(variable, mode, registerHint); - } - }); - if (hintResult != null) { - return asLocation(hintResult); - } - } - - Value hintResult = processRegisterHint(variable, mode, hintRegisterLocations.get(variable)); - if (hintResult != null) { - return asLocation(hintResult); - } - - EnumMap<RegisterFlag, Register[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters(); - Register[] availableRegs = categorizedRegs.get(variable.flag); - - Location bestSpillCandidate = null; - for (Register reg : availableRegs) { - if (isFree(reg, mode)) { - return selectRegister(reg, variable, mode); - } else { - Location spillCandidate = spillCandidate(reg); - if (betterSpillCandidate(spillCandidate, bestSpillCandidate)) { - bestSpillCandidate = spillCandidate; - } - } - } - - if (flags.contains(OperandFlag.STACK) && betterSpillCandidate(curLocations.get(variable), bestSpillCandidate)) { - return selectSpillSlot(variable); - } - - if (bestSpillCandidate == null) { - // This should not happen as long as all LIR instructions have fulfillable register constraints. But be safe in product mode and bail out. - assert false; - throw new GraalInternalError("No register available"); - } - - spill(bestSpillCandidate); - - return selectRegister(asRegister(bestSpillCandidate.location), variable, mode); - } - - private void spill(Location value) { - Location newLoc = spillLocation(value.variable); - Debug.log(" spill %s to %s", value, newLoc); - if (!(curOp instanceof StandardOp.PhiLabelOp)) { - moveResolver.add(value, newLoc); - } - curLocations.put(newLoc); - - Register reg = asRegister(value.location); - assert curInRegisterState[reg.number] == value; - curInRegisterState[reg.number] = null; - if (curOutRegisterState[reg.number] == value) { - curOutRegisterState[reg.number] = null; - } - } - - private boolean isFree(Register reg, OperandMode mode) { - switch (mode) { - case USE: return curInRegisterState[reg.number] == null; - case ALIVE: return curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null; - case TEMP: return curOutRegisterState[reg.number] == null; - case DEF: return curOutRegisterState[reg.number] == null; - default: throw GraalInternalError.shouldNotReachHere(); - } - } - - private Location spillCandidate(Register reg) { - Value in = curInRegisterState[reg.number]; - Value out = curOutRegisterState[reg.number]; - if (in == out && in != null && isLocation(in) && lastUseFor(asLocation(in).variable) < curOp.id()) { - return asLocation(in); - } - return null; - } - - private boolean betterSpillCandidate(Location loc, Location compare) { - if (loc == null) { - return false; - } - if (compare == null) { - return true; - } - if (canonicalSpillLocations.get(loc.variable) != null && canonicalSpillLocations.get(compare.variable) == null) { - return true; - } - return dataFlow.definition(loc.variable) < dataFlow.definition(compare.variable); - } - - private Location spillLocation(Variable variable) { - Location result = canonicalSpillLocations.get(variable); - if (result == null) { - result = new Location(variable, frameMap.allocateSpillSlot(variable.kind)); - canonicalSpillLocations.put(result); - } - return result; - } - - private Location selectRegister(Register reg, Variable variable, OperandMode mode) { - assert isFree(reg, mode); - - Location loc = new Location(variable, reg.asValue(variable.kind)); - if (mode == OperandMode.USE || mode == OperandMode.ALIVE) { - curInRegisterState[reg.number] = loc; - } - curOutRegisterState[reg.number] = loc; - curLocations.put(loc); - recordUse(variable); - if (hintRegisterLocations.get(variable) == null) { - hintRegisterLocations.put(loc); - } - - Debug.log(" selected register %s", loc); - return loc; - } - - private Location selectSpillSlot(Variable variable) { - Location loc = spillLocation(variable); - curLocations.put(loc); - recordUse(variable); - - Debug.log(" selected spill slot %s", loc); - return loc; - } - - private boolean checkInputState(final Block block) { - final BitSet liveState = new BitSet(); - curLocations.forEachLocation(new ValueProcedure() { - @Override - public Value doValue(Value value) { - liveState.set(asLocation(value).variable.index); - - for (Block pred : block.getPredecessors()) { - LocationMap predState = endLocationsFor(pred); - if (predState != null) { - assert predState.get(asLocation(value).variable) != null; - } else { - assert block.isLoopHeader(); - } - } - return value; - } - }); - assert liveState.equals(curLiveIn); - return true; - } - - - private String logCurrentState() { - final StringBuilder sb = new StringBuilder(); - sb.append(" current lcoations: "); - curLocations.forEachLocation(new ValueProcedure() { - @Override - public Value doValue(Value value) { - sb.append(value).append(" "); - return value; - } - }); - return sb.toString(); - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/ResolveDataFlow.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,129 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.simple; - -import static com.oracle.graal.alloc.util.LocationUtil.*; - -import java.util.*; - -import com.oracle.graal.alloc.util.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.StandardOp.*; -import com.oracle.graal.lir.cfg.*; - -public abstract class ResolveDataFlow { - public final LIR lir; - public final MoveResolver moveResolver; - public final DataFlowAnalysis dataFlow; - - public ResolveDataFlow(LIR lir, MoveResolver moveResolver, DataFlowAnalysis dataFlow) { - this.lir = lir; - this.moveResolver = moveResolver; - this.dataFlow = dataFlow; - } - - private LocationMap curFromLocations; - - public void execute() { - ValueProcedure locMappingProc = new ValueProcedure() { @Override public Value doValue(Value value) { return locMapping(value); } }; - - Debug.log("==== start resolve data flow ===="); - for (Block toBlock : lir.linearScanOrder()) { - PhiLabelOp phiDefs = null; - if (toBlock.lir.get(0) instanceof PhiLabelOp) { - phiDefs = (PhiLabelOp) toBlock.lir.get(0); - } - - for (Block fromBlock : toBlock.getPredecessors()) { - Debug.log("start edge %s -> %s", fromBlock, toBlock); - findInsertPos(fromBlock, toBlock); - - LocationMap toLocations = locationsForBlockBegin(toBlock); - curFromLocations = locationsForBlockEnd(fromBlock); - if (toLocations != curFromLocations) { - toLocations.forEachLocation(locMappingProc); - } - - if (phiDefs != null) { - PhiJumpOp phiInputs = (PhiJumpOp) fromBlock.lir.get(fromBlock.lir.size() - 1); - phiMapping(phiInputs.getPhiInputs(), phiDefs.getPhiDefinitions()); - phiInputs.markResolved(); - } - - moveResolver.resolve(); - Debug.log("end edge %s -> %s", fromBlock, toBlock); - } - - if (phiDefs != null) { - // Phi functions are resolved with moves now, so delete them. - phiDefs.markResolved(); - } - } - moveResolver.finish(); - Debug.log("==== end resolve data flow ===="); - } - - private Value locMapping(Value value) { - Location to = asLocation(value); - Location from = curFromLocations.get(to.variable); - if (value != from && from != null) { - moveResolver.add(from, to); - } - return value; - } - - private void phiMapping(Value[] inputs, Value[] outputs) { - assert inputs.length == outputs.length; - for (int i = 0; i < inputs.length; i++) { - if (inputs[i] != outputs[i]) { - moveResolver.add(inputs[i], asLocation(outputs[i])); - } - } - } - - private void findInsertPos(Block fromBlock, Block 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 StandardOp.JumpOp : "block does not end with an unconditional jump"; - moveResolver.init(instructions, instructions.size() - 1); - Debug.log(" insert at end of %s before %d", fromBlock, instructions.size() - 1); - - } else if (toBlock.numberOfPreds() == 1) { - moveResolver.init(toBlock.lir, 1); - Debug.log(" insert at beginning of %s before %d", toBlock, 1); - - } else { - GraalInternalError.shouldNotReachHere("Critical edge not split"); - } - } - - protected abstract LocationMap locationsForBlockBegin(Block block); - protected abstract LocationMap locationsForBlockEnd(Block block); -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/simple/SpillAllAllocator.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,465 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.simple; - -import static com.oracle.graal.alloc.util.LocationUtil.*; -import java.util.*; - -import com.oracle.graal.alloc.util.*; -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.code.Register.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; - -public class SpillAllAllocator { - private final LIR lir; - private final FrameMap frameMap; - - private final DataFlowAnalysis dataFlow; - - public SpillAllAllocator(LIR lir, FrameMap frameMap) { - this.lir = lir; - this.frameMap = frameMap; - - this.dataFlow = new DataFlowAnalysis(lir, frameMap.registerConfig); - this.blockLocations = new LocationMap[lir.linearScanOrder().size()]; - this.moveResolver = new MoveResolverImpl(lir, frameMap); - } - - private class MoveResolverImpl extends MoveResolver { - public MoveResolverImpl(LIR lir, FrameMap frameMap) { - super(lir, frameMap); - } - - @Override - protected Value scratchRegister(Variable spilled) { - EnumMap<RegisterFlag, Register[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters(); - Register[] availableRegs = categorizedRegs.get(spilled.flag); - for (Register reg : availableRegs) { - if (curInRegisterState[reg.number] == null && curOutRegisterState[reg.number] == null) { - return reg.asValue(spilled.kind); - } - } - throw new BailoutException("No register found"); - } - } - - private class ResolveDataFlowImpl extends ResolveDataFlow { - public ResolveDataFlowImpl(LIR lir, MoveResolver moveResolver, DataFlowAnalysis dataFlow) { - super(lir, moveResolver, dataFlow); - } - - @Override - protected LocationMap locationsForBlockBegin(Block block) { - assert block.numberOfPreds() > 0 && block.getDominator() != null; - return locationsFor(block.getDominator()); - } - - @Override - protected LocationMap locationsForBlockEnd(Block block) { - return locationsFor(block); - } - } - - private class AssignRegistersImpl extends AssignRegisters { - public AssignRegistersImpl(LIR lir, FrameMap frameMap) { - super(lir, frameMap); - } - - @Override - protected LocationMap locationsForBlockEnd(Block block) { - return locationsFor(block); - } - } - - - private int maxRegisterNum() { - return frameMap.target.arch.registers.length; - } - - private boolean isAllocatableRegister(Value value) { - return isRegister(value) && frameMap.registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable(); - } - - - private final LocationMap[] blockLocations; - - private LocationMap locationsFor(Block block) { - return blockLocations[block.getId()]; - } - private void setLocationsFor(Block block, LocationMap locations) { - blockLocations[block.getId()] = 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); - - dataFlow.execute(); - IntervalPrinter.printBeforeAllocation("Before register allocation", lir, frameMap.registerConfig, dataFlow); - - allocate(); - - IntervalPrinter.printAfterAllocation("After spill all allocation", lir, frameMap.registerConfig, dataFlow, blockLocations); - - ResolveDataFlow resolveDataFlow = new ResolveDataFlowImpl(lir, moveResolver, dataFlow); - resolveDataFlow.execute(); - frameMap.finish(); - - IntervalPrinter.printAfterAllocation("After resolve data flow", lir, frameMap.registerConfig, dataFlow, blockLocations); - assert RegisterVerifier.verify(lir, frameMap); - - AssignRegisters assignRegisters = new AssignRegistersImpl(lir, frameMap); - assignRegisters.execute(); - - Debug.dump(lir, "After register asignment"); - assert LIRVerifier.verify(false, lir, frameMap); - } - - private void allocate() { - ValueProcedure killNonLiveProc = new ValueProcedure() { @Override public Value doValue(Value value) { return killNonLive(value); } }; - ValueProcedure killBeginProc = new ValueProcedure() { @Override public Value doValue(Value value) { return kill(value, false); } }; - ValueProcedure killEndProc = new ValueProcedure() { @Override public Value doValue(Value value) { return kill(value, true); } }; - ValueProcedure killLocationProc = new ValueProcedure() { @Override public Value doValue(Value value) { return killLocation(value); } }; - ValueProcedure blockProc = new ValueProcedure() { @Override public Value doValue(Value value) { return block(value); } }; - ValueProcedure loadProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return load(value, mode, flags); } }; - ValueProcedure spillProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return spill(value, mode, flags); } }; - ValueProcedure useSlotProc = new ValueProcedure() { @Override public Value doValue(Value value) { return useSlot(value); } }; - - Debug.log("==== start spill all allocation ===="); - curInRegisterState = new Object[maxRegisterNum()]; - curOutRegisterState = new Object[maxRegisterNum()]; - curRegisterLocations = new LocationMap(lir.numVariables()); - for (Block block : lir.linearScanOrder()) { - Debug.log("start block %s %s", block, block.getLoop()); - assert checkEmpty(curOutRegisterState); - - if (block.getDominator() != null) { - LocationMap dominatorState = locationsFor(block.getDominator()); - 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); - } else { - curStackLocations = new LocationMap(lir.numVariables()); - } - Debug.log(logCurrentState()); - - for (int opIdx = 0; opIdx < block.lir.size(); opIdx++) { - LIRInstruction op = block.lir.get(opIdx); - curInstruction = op; - Debug.log(" 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(loadProc); - op.forEachInput(loadProc); - 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(spillProc); - op.forEachOutput(spillProc); - moveResolver.resolve(); - - dataFlow.forEachKilled(op, true, killEndProc); - curRegisterLocations.forEachLocation(killLocationProc); - - assert curRegisterLocations.checkEmpty(); - curInstruction = null; - } - assert checkEmpty(curOutRegisterState); - assert locationsFor(block) == null; - setLocationsFor(block, curStackLocations); - - logCurrentState(); - Debug.log("end block %s", block); - } - - moveResolver.finish(); - Debug.log("==== end spill all allocation ===="); - } - - private Value killNonLive(Value value) { - assert isLocation(value); - if (!curLiveIn.get(asLocation(value).variable.index)) { - return null; - } - return value; - } - - private Value kill(Value value, boolean end) { - if (isVariable(value)) { - Debug.log(" kill variable %s", value); - - Variable variable = asVariable(value); - curStackLocations.clear(variable); - - Location loc = curRegisterLocations.get(variable); - if (loc != null) { - killLocation(loc); - curRegisterLocations.clear(variable); - - Debug.log(" location %s", loc); - assert isAllocatableRegister(loc.location); - - int regNum = asRegister(loc.location).number; - if (curOutRegisterState[regNum] == loc) { - curOutRegisterState[regNum] = null; - } - } - - } else if (isAllocatableRegister(value)) { - Debug.log(" 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 GraalInternalError.shouldNotReachHere(); - } - return value; - } - - private Value killLocation(Value value) { - Debug.log(" 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 Value block(Value value) { - if (isAllocatableRegister(value)) { - Debug.log(" 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 Value load(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { - assert mode == OperandMode.USE || mode == OperandMode.ALIVE; - if (flags.contains(OperandFlag.STACK)) { - return useSlot(value); - } - if (isVariable(value)) { - Debug.log(" load %s", value); - Location regLoc = curRegisterLocations.get(asVariable(value)); - if (regLoc != null) { - // This variable has already been processed before. - Debug.log(" found location %s", regLoc); - } else { - regLoc = allocateRegister(asVariable(value), curInRegisterState, mode == OperandMode.ALIVE ? curOutRegisterState : null, mode, flags); - 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 Value spill(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { - assert mode == OperandMode.TEMP || mode == OperandMode.DEF; - if (flags.contains(OperandFlag.STACK)) { - return defSlot(value); - } - if (isVariable(value)) { - Debug.log(" spill %s", value); - assert curStackLocations.get(asVariable(value)) == null; - Location regLoc = allocateRegister(asVariable(value), null, curOutRegisterState, mode, flags); - if (mode == OperandMode.DEF) { - Location stackLoc = new Location(asVariable(value), frameMap.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 Value useSlot(Value value) { - if (isVariable(value)) { - Debug.log(" useSlot %s", value); - Location stackLoc = curStackLocations.get(asVariable(value)); - assert stackLoc != null; - Debug.log(" slot %s", stackLoc); - return stackLoc; - } else { - return value; - } - } - - private Value defSlot(Value value) { - if (isVariable(value)) { - Debug.log(" assignSlot %s", value); - Location stackLoc = new Location(asVariable(value), frameMap.allocateSpillSlot(value.kind)); - assert curStackLocations.get(asVariable(value)) == null; - curStackLocations.put(stackLoc); - Debug.log(" slot %s", stackLoc); - return stackLoc; - } else { - return value; - } - } - - private Location allocateRegister(final Variable variable, final Object[] inRegisterState, final Object[] outRegisterState, OperandMode mode, EnumSet<OperandFlag> flags) { - if (flags.contains(OperandFlag.HINT)) { - Value result = curInstruction.forEachRegisterHint(variable, mode, new ValueProcedure() { - @Override - public Value doValue(Value registerHint) { - Debug.log(" registerHint %s", registerHint); - Register hint = null; - if (isRegister(registerHint)) { - hint = asRegister(registerHint); - } else if (isLocation(registerHint) && isRegister(asLocation(registerHint).location)) { - hint = asRegister(asLocation(registerHint).location); - } - if (hint != null && hint.isSet(variable.flag) && isFree(hint, inRegisterState, outRegisterState)) { - return selectRegister(hint, variable, inRegisterState, outRegisterState); - } - return null; - } - }); - - if (result != null) { - return asLocation(result); - } - } - - EnumMap<RegisterFlag, Register[]> categorizedRegs = frameMap.registerConfig.getCategorizedAllocatableRegisters(); - Register[] availableRegs = categorizedRegs.get(variable.flag); - - for (Register reg : availableRegs) { - if (isFree(reg, inRegisterState, outRegisterState)) { - return selectRegister(reg, variable, inRegisterState, outRegisterState); - } - - } - throw new BailoutException("No register found"); - } - - private static boolean isFree(Register reg, Object[] inRegisterState, Object[] outRegisterState) { - return (inRegisterState == null || inRegisterState[reg.number] == null) && (outRegisterState == null || outRegisterState[reg.number] == null); - } - - private Location selectRegister(Register reg, Variable variable, Object[] inRegisterState, Object[] outRegisterState) { - 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); - Debug.log(" selected register %s", loc); - return loc; - } - - private boolean checkInputState(final Block block) { - final BitSet liveState = new BitSet(); - curStackLocations.forEachLocation(new ValueProcedure() { - @Override - public Value doValue(Value 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 checkNoCallerSavedRegister() { - for (Register reg : frameMap.registerConfig.getCallerSaveRegisters()) { - assert curOutRegisterState[reg.number] == null || curOutRegisterState[reg.number] == curInstruction : "caller saved register in use accross call site"; - } - return true; - } - - private static boolean checkEmpty(Object[] array) { - for (Object o : array) { - assert o == null; - } - return true; - } - - - private String logCurrentState() { - final StringBuilder sb = new StringBuilder(); - sb.append(" curVariableLocations: "); - curStackLocations.forEachLocation(new ValueProcedure() { - @Override - public Value doValue(Value value) { - sb.append(value).append(" "); - return value; - } - }); - return sb.toString(); - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/IntervalPrinter.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,272 +0,0 @@ -/* - * Copyright (c) 2012, 2012, 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.graal.alloc.util; - -import static com.oracle.graal.alloc.util.LocationUtil.*; -import java.util.*; - -import com.oracle.graal.alloc.simple.*; -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; - -public final class IntervalPrinter { - - public static void printBeforeAllocation(String label, LIR lir, RegisterConfig registerConfig, DataFlowAnalysis dataFlow) { - if (Debug.isDumpEnabled()) { - IntervalPrinter printer = new IntervalPrinter(lir, registerConfig, dataFlow, null); - Debug.dump(lir, label); - Debug.dump(printer.execute(), label); - } - } - - public static void printAfterAllocation(String label, LIR lir, RegisterConfig registerConfig, DataFlowAnalysis dataFlow, LocationMap[] blockEndLocations) { - if (Debug.isDumpEnabled()) { - IntervalPrinter printer = new IntervalPrinter(lir, registerConfig, dataFlow, blockEndLocations); - Debug.dump(lir, label); - Debug.dump(printer.execute(), label); - } - } - - - public static class Range { - public final int from; - public final int to; - - public Range(int from, int to) { - this.from = from; - this.to = to; - } - } - - public static class UsePosition { - public final int pos; - public final String kind; - - public UsePosition(int pos, String kind) { - this.pos = pos; - this.kind = kind; - } - } - - public static class Interval { - public final String name; - public final String description; - public final String variable; - public final String type; - public final List<Range> ranges; - public final List<UsePosition> uses; - - protected final int orderNum; - protected int lastTo; - - public Interval(int orderNum, String name, String description, String variable, String type) { - this.orderNum = orderNum; - this.name = name; - this.description = description; - this.variable = variable; - this.type = type; - this.ranges = new ArrayList<>(); - this.uses = new ArrayList<>(); - } - } - - - private final LIR lir; - private final RegisterConfig registerConfig; - private final DataFlowAnalysis dataFlow; - private final LocationMap[] blockEndLocations; - private final Variable[] variables; - private final Map<String, Interval> intervals; - - private IntervalPrinter(LIR lir, RegisterConfig registerConfig, DataFlowAnalysis dataFlow, LocationMap[] blockEndLocations) { - this.lir = lir; - this.registerConfig = registerConfig; - this.dataFlow = dataFlow; - this.blockEndLocations = blockEndLocations; - this.variables = new Variable[lir.numVariables()]; - this.intervals = new HashMap<>(); - } - - private boolean isAllocatableRegister(Value value) { - return isRegister(value) && registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable(); - } - - private int curOpId; - private String curUseKind; - - public Interval[] execute() { - ValueProcedure varProc = new ValueProcedure() { @Override public Value doValue(Value value) { return var(value); } }; - - for (Block block : lir.linearScanOrder()) { - for (LIRInstruction op : block.lir) { - op.forEachOutput(varProc); - } - } - - ValueProcedure useProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return use(value, mode, flags); } }; - ValueProcedure defProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return def(value, flags); } }; - - intervals.put("call", new Interval(-2, "call", "", "call", "hasCall")); - intervals.put("st", new Interval(-1, "st", "", "st", "hasState")); - - for (int i = lir.linearScanOrder().size() - 1; i >= 0; i--) { - Block block = lir.linearScanOrder().get(i); - - curOpId = block.getLastLirInstructionId() + 2; - for (Block sux : block.getSuccessors()) { - BitSet suxIn = dataFlow.liveIn(sux); - for (int idx = suxIn.nextSetBit(0); idx >= 0; idx = suxIn.nextSetBit(idx + 1)) { - if (blockEndLocations != null) { - out(blockEndLocations[block.getId()].get(variables[idx])); - } else { - out(variables[idx]); - } - } - } - - for (int j = block.lir.size() - 1; j >= 0; j--) { - LIRInstruction op = block.lir.get(j); - if (op.id() >= 0) { - curOpId = op.id(); - } else { - curOpId = (curOpId - 1) | 1; - } - - op.forEachOutput(defProc); - op.forEachTemp(defProc); - op.forEachInput(useProc); - op.forEachAlive(useProc); - curUseKind = "L"; - op.forEachState(useProc); - curUseKind = null; - - if (op.hasCall()) { - intervals.get("call").ranges.add(new Range(curOpId, curOpId + 1)); - } - if (op.hasState()) { - intervals.get("st").ranges.add(new Range(curOpId, curOpId + 1)); - } - } - - for (Interval interval : intervals.values()) { - if (interval.lastTo != 0) { - interval.ranges.add(new Range(block.getFirstLirInstructionId(), interval.lastTo)); - interval.lastTo = 0; - } - } - } - - Interval[] intervalsArray = intervals.values().toArray(new Interval[0]); - Arrays.sort(intervalsArray, new Comparator<Interval>() { - @Override - public int compare(Interval o1, Interval o2) { - return o1.orderNum - o2.orderNum; - } - }); - return intervalsArray; - } - - public Value var(Value value) { - if (isLocation(value)) { - variables[asLocation(value).variable.index] = asLocation(value).variable; - } else if (isVariable(value)) { - variables[asVariable(value).index] = asVariable(value); - } - return value; - } - - private Interval findInterval(Value value) { - Interval interval; - if (isLocation(value)) { - Interval parent = findInterval(asLocation(value).variable); - String name = "v" + asLocation(value).variable.index + ":" + asLocation(value).location; - String description = isStackSlot(asLocation(value).location) ? "stack" : ""; - interval = new Interval(asLocation(value).variable.index * 2 + 1001, name, description, parent.name, value.kind.javaName); - - } else if (isVariable(value)) { - interval = new Interval(asVariable(value).index * 2 + 1000, value.toString(), "", value.toString(), value.kind.javaName); - - } else if (isAllocatableRegister(value)) { - interval = new Interval(asRegister(value).number, asRegister(value).toString(), "", asRegister(value).toString(), "fixed"); - - } else { - return null; - } - - Interval existing = intervals.get(interval.name); - if (existing != null) { - return existing; - } - intervals.put(interval.name, interval); - return interval; - } - - private String useKind(EnumSet<OperandFlag> flags) { - if (curUseKind != null) { - return curUseKind; - } else if (flags.contains(OperandFlag.STACK)) { - return "S"; - } else { - return "M"; - } - } - - private Value use(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { - Interval interval = findInterval(value); - if (interval != null) { - if (interval.uses.size() == 0 || interval.uses.get(interval.uses.size() - 1).pos != curOpId) { - interval.uses.add(new UsePosition(curOpId, useKind(flags))); - } - if (interval.lastTo == 0) { - interval.lastTo = curOpId + (mode == OperandMode.ALIVE ? 1 : 0); - } - } - return value; - } - - private Value def(Value value, EnumSet<OperandFlag> flags) { - Interval interval = findInterval(value); - if (interval != null) { - interval.uses.add(new UsePosition(curOpId, useKind(flags))); - if (interval.lastTo == 0) { - interval.ranges.add(new Range(curOpId, curOpId + 1)); - } else { - interval.ranges.add(new Range(curOpId, interval.lastTo)); - } - interval.lastTo = 0; - } - return value; - } - - private Value out(Value value) { - Interval interval = findInterval(value); - if (interval != null) { - interval.lastTo = curOpId; - } - return value; - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/Location.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.util; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.lir.*; - -public class Location extends Value { - private static final long serialVersionUID = -1786677729152726126L; - - public final Variable variable; - public final Value location; - - public Location(Variable variable, Value location) { - super(variable.kind); - this.variable = variable; - this.location = location; - - assert variable.kind == location.kind; - } - - @Override - public String toString() { - return variable + "[" + location + "]"; - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/LocationMap.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,73 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.util; - -import static com.oracle.graal.alloc.util.LocationUtil.*; - -import java.util.*; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; - -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(Variable 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(Variable variable) { - locations[variable.index] = null; - } - - public void forEachLocation(ValueProcedure proc) { - for (int i = 0; i < locations.length; i++) { - if (locations[i] != null) { - Value newValue = proc.doValue(locations[i], null, null); - 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; - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/LocationUtil.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,39 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.graal.alloc.util; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.lir.*; - -public class LocationUtil extends LIRValueUtil { - - public static boolean isLocation(Value value) { - assert value != null; - return value instanceof Location; - } - - public static Location asLocation(Value value) { - assert value != null; - return (Location) value; - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/MoveResolver.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,341 +0,0 @@ -/* - * Copyright (c) 2009, 2012, 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.graal.alloc.util; - -import static com.oracle.graal.alloc.util.LocationUtil.*; -import java.util.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.*; - -public abstract class MoveResolver { - private final LIR lir; - private final FrameMap frameMap; - private final int[] registersBlocked; - private final Map<Value, Integer> valuesBlocked; - private final List<Value> mappingFrom; - private final List<Location> mappingTo; - private final LIRInsertionBuffer insertionBuffer; - private int insertPos; - - public MoveResolver(LIR lir, FrameMap frameMap) { - this.lir = lir; - this.frameMap = frameMap; - - registersBlocked = new int[frameMap.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(Value from, Location to) { - assert checkValid(); - assert isLocation(from) || isConstant(from); - assert from != to; - - Debug.log("mr add mapping from %s to %s", from, to); - mappingFrom.add(from); - mappingTo.add(to); - - assert checkValid(); - } - - public boolean hasMappings() { - return mappingFrom.size() > 0; - } - - 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. - Debug.log("mr resolve mappings: %d", mappingFrom.size()); - insertMove(mappingFrom.get(0), mappingTo.get(0)); - mappingFrom.remove(0); - mappingTo.remove(0); - } else if (mappingFrom.size() > 1) { - Debug.log("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 (Value from : mappingFrom) { - block(from); - } - - while (mappingFrom.size() > 0) { - boolean processed = false; - for (int i = mappingFrom.size() - 1; i >= 0; i--) { - Value 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() - 1; i >= 0; i--) { - Value from = mappingFrom.get(i); - Location to = mappingTo.get(i); - assert !safeToProcessMove(from, to) : "would not be in this code otherwise"; - - if (isConstant(from)) { - continue; - } - Value 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--) { - Value 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, frameMap.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(Value value) { - if (isLocation(value)) { - Value 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(Value value) { - if (isLocation(value)) { - assert blockedCount(asLocation(value)) > 0; - Value 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) { - Value 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(Value 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) { - Debug.log("mr XCHG %s, %s", from, to); - // TODO (cwimmer) create XCHG instruction and use it here - insertionBuffer.append(insertPos, null); - throw GraalInternalError.unimplemented(); - } - - private void insertMove(Value src, Location dst) { - if (isStackSlot(dst.location) && isLocation(src) && isStackSlot(asLocation(src).location)) { - // Move between two stack slots. We need a temporary registers. If the allocator can give - // us a free register, we need two moves: src->scratch, scratch->dst - // If the allocator cannot give us a free register (it returns a Location in this case), - // we need to spill the scratch register first, so we need four moves in total. - - Value scratch = scratchRegister(dst.variable); - - Location scratchSaved = null; - Value scratchRegister = scratch; - if (isLocation(scratch)) { - scratchSaved = new Location(asLocation(scratch).variable, frameMap.allocateSpillSlot(scratch.kind)); - insertMove(scratch, scratchSaved); - scratchRegister = asLocation(scratch).location; - } - assert isRegister(scratchRegister); - - Location scratchLocation = new Location(dst.variable, scratchRegister); - insertMove(src, scratchLocation); - insertMove(scratchLocation, dst); - - if (scratchSaved != null) { - insertMove(scratchSaved, asLocation(scratch)); - } - - } else { - Debug.log("mr MOV %s -> %s", src, dst); - insertionBuffer.append(insertPos, lir.spillMoveFactory.createMove(dst, src)); - } - } - - /** - * Provides a register that can be used by the move resolver. If the returned value is a - * {@link RegisterValue}, the register can be overwritten without precautions. If the - * returned value is a {@link Location}, it needs to be spilled and rescued itself. - */ - protected abstract Value scratchRegister(Variable spilled); - - 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++) { - Value from = mappingFrom.get(i); - Location to = mappingTo.get(i); - - assert from.kind.stackKind() == to.kind; - - 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; - } -}
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/util/RegisterVerifier.java Thu Sep 06 13:40:04 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,247 +0,0 @@ -/* - * Copyright (c) 2009, 2012, 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.graal.alloc.util; - -import static com.oracle.graal.alloc.util.LocationUtil.*; -import java.util.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.LIRInstruction.*; -import com.oracle.graal.lir.cfg.*; - -public final class RegisterVerifier { - private final FrameMap frameMap; - - /** - * All blocks that must be processed. - */ - private final List<Block> workList; - - /** - * Saved information of previous check. - * <br> - * State mapping: mapping from registers and stack slots ({@link Register} and {@link Integer} stack slot offsets) to the - * value that is currently contained in there ({@link Location} for operands that were variables; {@link RegisterValue} or - * {@link StackSlot} for operands that used fixed registers or stack slots). - */ - private final Map<Object, Value>[] blockStates; - - private void addToWorkList(Block block) { - if (!workList.contains(block)) { - workList.add(block); - } - } - - private Map<Object, Value> stateFor(Block block) { - return blockStates[block.getId()]; - } - - private void setStateFor(Block block, Map<Object, Value> savedState) { - blockStates[block.getId()] = savedState; - } - - private static Map<Object, Value> copy(Map<Object, Value> inputState) { - return new HashMap<>(inputState); - } - - public static boolean verify(LIR lir, FrameMap frameMap) { - RegisterVerifier verifier = new RegisterVerifier(lir, frameMap); - verifier.verify(lir.cfg.getStartBlock()); - return true; - } - - @SuppressWarnings("unchecked") - private RegisterVerifier(LIR lir, FrameMap frameMap) { - this.frameMap = frameMap; - this.workList = new LinkedList<>(); - this.blockStates = new Map[lir.linearScanOrder().size()]; - } - - private Map<Object, Value> curInputState; - - private void verify(Block startBlock) { - ValueProcedure useProc = new ValueProcedure() { @Override public Value doValue(Value value, OperandMode mode, EnumSet<OperandFlag> flags) { return use(value, flags); } }; - ValueProcedure tempProc = new ValueProcedure() { @Override public Value doValue(Value value) { return temp(value); } }; - ValueProcedure outputProc = new ValueProcedure() { @Override public Value doValue(Value value) { return output(value); } }; - - curInputState = new HashMap<>(); - setStateFor(startBlock, curInputState); - addToWorkList(startBlock); - - Debug.log("==== start verify register allocation ===="); - do { - Block block = workList.remove(0); - - // Must copy state because it is modified. - curInputState = copy(stateFor(block)); - Debug.log("start block %s %s", block, block.getLoop()); - Debug.log(logCurrentState()); - - for (LIRInstruction op : block.lir) { - Debug.log(" 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 (Block succ : block.getSuccessors()) { - processSuccessor(succ); - } - - Debug.log("end block %s", block); - } while (!workList.isEmpty()); - Debug.log("==== end verify register allocation ===="); - } - - private void processSuccessor(Block succ) { - Map<Object, Value> savedState = stateFor(succ); - if (savedState == null) { - // Block was not processed before, so set initial inputState. - Debug.log(" 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. - Debug.log(" successor %s: state present", succ); - Iterator<Map.Entry<Object, Value>> iter = savedState.entrySet().iterator(); - while (iter.hasNext()) { - Map.Entry<Object, Value> entry = iter.next(); - Value savedValue = entry.getValue(); - Value 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. - Debug.log(" invalidating %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 Register && frameMap.registerConfig.getAttributesMap()[((Register) value1).number].isCallerSave()) { - Debug.log(" 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(Value 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 GraalInternalError.shouldNotReachHere(); - } - } - - private boolean isIgnoredRegister(Value value) { - return isRegister(value) && !frameMap.registerConfig.getAttributesMap()[asRegister(value).number].isAllocatable(); - } - - private Value use(Value value, EnumSet<OperandFlag> flags) { - if (!isConstant(value) && value != Value.IllegalValue && !isIgnoredRegister(value)) { - Value actual = curInputState.get(key(value)); - if (actual == null && flags.contains(OperandFlag.UNINITIALIZED)) { - // OK, since uninitialized values are allowed explicitly. - } else if (value != actual) { - Debug.log("Error in register allocation: %s != %s for key %s", value, actual, key(value)); - Debug.log(logCurrentState()); - throw GraalInternalError.shouldNotReachHere(); - } - } - return value; - } - - private Value temp(Value value) { - if (!isConstant(value) && value != Value.IllegalValue && !isIgnoredRegister(value)) { - Debug.log(" temp %s -> remove key %s", value, key(value)); - curInputState.remove(key(value)); - } - return value; - } - - private Value output(Value value) { - if (value != Value.IllegalValue && !isIgnoredRegister(value)) { - Debug.log(" output %s -> set key %s", value, key(value)); - curInputState.put(key(value), value); - } - return value; - } - - - private String logCurrentState() { - ArrayList<Object> keys = new ArrayList<>(curInputState.keySet()); - Collections.sort(keys, new Comparator<Object>() { - @Override - public int compare(Object o1, Object o2) { - if (o1 instanceof Register) { - if (o2 instanceof Register) { - return ((Register) o1).number - ((Register) o2).number; - } else { - return -1; - } - } else { - if (o2 instanceof Register) { - return 1; - } else { - return ((Integer) o1).intValue() - ((Integer) o2).intValue(); - } - } - } - }); - - StringBuilder sb = new StringBuilder(" state: "); - for (Object key : keys) { - sb.append(key).append("=").append(curInputState.get(key)).append(" "); - } - return sb.toString(); - } -}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Sep 06 13:40:04 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Sep 06 15:32:08 2012 +0200 @@ -26,7 +26,6 @@ import java.util.*; import java.util.concurrent.*; -import com.oracle.graal.alloc.simple.*; import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.alloc.*; @@ -72,26 +71,31 @@ this.backend = backend; } - public CompilationResult compileMethod(final ResolvedJavaMethod method, final StructuredGraph graph, int osrBCI, final GraphCache cache, final PhasePlan plan, final OptimisticOptimizations optimisticOpts) { + public CompilationResult compileMethod(final ResolvedJavaMethod method, final StructuredGraph graph, int osrBCI, final GraphCache cache, final PhasePlan plan, + final OptimisticOptimizations optimisticOpts) { assert (method.accessFlags() & Modifier.NATIVE) == 0 : "compiling native methods is not supported"; if (osrBCI != -1) { throw new BailoutException("No OSR supported"); } - return Debug.scope("GraalCompiler", new Object[] {graph, method, this}, new Callable<CompilationResult>() { + return Debug.scope("GraalCompiler", new Object[]{graph, method, this}, new Callable<CompilationResult>() { + public CompilationResult call() { final Assumptions assumptions = GraalOptions.OptAssumptions ? new Assumptions() : null; final LIR lir = Debug.scope("FrontEnd", new Callable<LIR>() { + public LIR call() { return emitHIR(graph, assumptions, cache, plan, optimisticOpts); } }); final FrameMap frameMap = Debug.scope("BackEnd", lir, new Callable<FrameMap>() { + public FrameMap call() { return emitLIR(lir, graph, method, assumptions); } }); return Debug.scope("CodeGen", frameMap, new Callable<CompilationResult>() { + public CompilationResult call() { return emitCode(assumptions, method, lir, frameMap); } @@ -136,7 +140,7 @@ } } - //new ConvertUnreachedToGuardPhase(optimisticOpts).apply(graph); + // new ConvertUnreachedToGuardPhase(optimisticOpts).apply(graph); plan.runPhases(PhasePosition.HIGH_LEVEL, graph); @@ -236,6 +240,7 @@ final LIRGenerator lirGenerator = backend.newLIRGenerator(graph, frameMap, method, lir, xir, assumptions); Debug.scope("LIRGen", lirGenerator, new Runnable() { + public void run() { for (Block b : lir.linearScanOrder()) { lirGenerator.doBlock(b); @@ -246,13 +251,9 @@ }); Debug.scope("Allocator", new Runnable() { + public void run() { - if (GraalOptions.AllocSSA) { - new LinearScanAllocator(lir, frameMap).execute(); - // new SpillAllAllocator(context, lir, frameMap).execute(); - } else { - new LinearScan(target, method, lir, lirGenerator, frameMap).allocate(); - } + new LinearScan(target, method, lir, lirGenerator, frameMap).allocate(); } }); return frameMap;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Thu Sep 06 13:40:04 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Thu Sep 06 15:32:08 2012 +0200 @@ -230,11 +230,6 @@ public static int MethodEntryCountersCallers = 20; /** - * Flag to turn on SSA-based register allocation, which is currently under development. - */ - public static boolean AllocSSA = false; - - /** * Prints all the available GraalOptions. */ public static boolean PrintFlags = false;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/Interval.java Thu Sep 06 13:40:04 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/Interval.java Thu Sep 06 15:32:08 2012 +0200 @@ -22,17 +22,18 @@ */ package com.oracle.graal.compiler.alloc; -import static com.oracle.graal.alloc.util.LocationUtil.*; import java.util.*; -import com.oracle.max.criutils.*; import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.*; import com.oracle.graal.compiler.util.*; import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; +import com.oracle.max.criutils.*; +import static com.oracle.graal.api.code.ValueUtil.*; +import static com.oracle.graal.lir.LIRValueUtil.*; /** * Represents an interval in the {@linkplain LinearScan linear scan register allocator}.
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Thu Sep 06 13:40:04 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Thu Sep 06 15:32:08 2012 +0200 @@ -22,8 +22,9 @@ */ package com.oracle.graal.compiler.alloc; -import static com.oracle.graal.alloc.util.LocationUtil.*; import static com.oracle.graal.api.code.CodeUtil.*; +import static com.oracle.graal.api.code.ValueUtil.*; +import static com.oracle.graal.lir.LIRValueUtil.*; import java.util.*;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Thu Sep 06 13:40:04 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Thu Sep 06 15:32:08 2012 +0200 @@ -42,8 +42,6 @@ import com.oracle.graal.lir.StandardOp.JumpOp; import com.oracle.graal.lir.StandardOp.LabelOp; import com.oracle.graal.lir.StandardOp.ParametersOp; -import com.oracle.graal.lir.StandardOp.PhiJumpOp; -import com.oracle.graal.lir.StandardOp.PhiLabelOp; import com.oracle.graal.lir.asm.*; import com.oracle.graal.lir.asm.TargetMethodAssembler.CallPositionListener; import com.oracle.graal.lir.cfg.*; @@ -319,21 +317,7 @@ assert block.lir == null : "LIR list already computed for this block"; block.lir = new ArrayList<>(); - if (GraalOptions.AllocSSA && block.getBeginNode() instanceof MergeNode) { - assert phiValues.isEmpty(); - MergeNode merge = (MergeNode) block.getBeginNode(); - for (PhiNode phi : merge.phis()) { - if (phi.type() == PhiType.Value) { - Value phiValue = newVariable(phi.kind()); - setResult(phi, phiValue); - phiValues.add(phiValue); - } - } - append(new PhiLabelOp(new Label(), block.align, phiValues.toArray(new Value[phiValues.size()]))); - phiValues.clear(); - } else { - append(new LabelOp(new Label(), block.align)); - } + append(new LabelOp(new Label(), block.align)); if (GraalOptions.TraceLIRGeneratorLevel >= 1) { TTY.println("BEGIN Generating LIR for block B" + block.getId()); @@ -644,21 +628,7 @@ public void visitLoopEnd(LoopEndNode x) { } - private ArrayList<Value> phiValues = new ArrayList<>(); - private void moveToPhi(MergeNode merge, EndNode pred) { - if (GraalOptions.AllocSSA) { - assert phiValues.isEmpty(); - for (PhiNode phi : merge.phis()) { - if (phi.type() == PhiType.Value) { - phiValues.add(operand(phi.valueAt(pred))); - } - } - append(new PhiJumpOp(getLIRBlock(merge), phiValues.toArray(new Value[phiValues.size()]))); - phiValues.clear(); - return; - } - if (GraalOptions.TraceLIRGeneratorLevel >= 1) { TTY.println("MOVE TO PHI from " + pred + " to " + merge); }
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Thu Sep 06 13:40:04 2012 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinter.java Thu Sep 06 15:32:08 2012 +0200 @@ -27,7 +27,6 @@ import java.io.*; import java.util.*; -import com.oracle.graal.alloc.util.*; import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.alloc.*; @@ -534,33 +533,5 @@ out.printf(" \"%s\"", interval.spillState()); out.println(); } - - public void printIntervals(String label, IntervalPrinter.Interval[] intervals) { - begin("intervals"); - out.println(String.format("name \"%s\"", label)); - - for (IntervalPrinter.Interval interval : intervals) { - printInterval(interval); - } - - end("intervals"); - } - - private void printInterval(IntervalPrinter.Interval interval) { - out.printf("%s %s \"%s\" %s %s ", interval.name, interval.type, interval.description, interval.variable, "no"); - if (interval.ranges.size() == 0) { - // One range is required in the spec, so output a dummy range. - out.printf("[0, 0[ "); - } else { - for (IntervalPrinter.Range range : interval.ranges) { - out.printf("[%d, %d[ ", range.from, range.to); - } - } - for (IntervalPrinter.UsePosition usePos : interval.uses) { - out.printf("%d %s ", usePos.pos, usePos.kind); - } - out.printf("\"%s\"", "no"); - out.println(); - } }
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Thu Sep 06 13:40:04 2012 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Thu Sep 06 15:32:08 2012 +0200 @@ -26,7 +26,6 @@ import java.util.*; import java.util.concurrent.atomic.*; -import com.oracle.graal.alloc.util.*; import com.oracle.graal.api.code.*; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.*; @@ -172,8 +171,6 @@ } else if (object instanceof Interval[]) { cfgPrinter.printIntervals(message, (Interval[]) object); - } else if (object instanceof IntervalPrinter.Interval[]) { - cfgPrinter.printIntervals(message, (IntervalPrinter.Interval[]) object); } cfgPrinter.target = null;