Mercurial > hg > graal-compiler
changeset 22350:06a9e6737dcf
Drop initial version of the trace based register allocator.
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java Fri Jul 24 16:20:56 2015 +0200 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/BackendOptions.java Fri Jul 24 10:55:33 2015 +0200 @@ -25,7 +25,7 @@ import static com.oracle.graal.compiler.common.BackendOptions.UserOptions.*; import static com.oracle.graal.compiler.common.GraalOptions.*; import jdk.internal.jvmci.options.*; -import jdk.internal.jvmci.options.DerivedOptionValue.*; +import jdk.internal.jvmci.options.DerivedOptionValue.OptionSupplier; /** * Options to control the backend configuration. @@ -36,27 +36,44 @@ // @formatter:off @Option(help = "Destruct SSA LIR eagerly (before other LIR phases).", type = OptionType.Debug) public static final OptionValue<Boolean> LIREagerSSADestruction = new OptionValue<>(false); + @Option(help = "Enable Linear Scan on SSI form.", type = OptionType.Debug) + public static final OptionValue<Boolean> LIROptSSILinearScan = new OptionValue<>(false); + @Option(help = "Enable experimental Trace Register Allocation.", type = OptionType.Debug) + public static final OptionValue<Boolean> TraceRA = new OptionValue<>(false); // @formatter:on } + /* Enable SSI Construction. */ + public static final DerivedOptionValue<Boolean> EnableSSIConstruction = new DerivedOptionValue<>(new OptionSupplier<Boolean>() { + private static final long serialVersionUID = -7375589337502162545L; + + public Boolean get() { + return LIROptSSILinearScan.getValue() || TraceRA.getValue(); + } + }); + /* Create SSA LIR during LIR generation. */ public static final DerivedOptionValue<Boolean> ConstructionSSAlirDuringLirBuilding = new DerivedOptionValue<>(new OptionSupplier<Boolean>() { private static final long serialVersionUID = 7657622005438210681L; public Boolean get() { - return SSA_LIR.getValue(); + return SSA_LIR.getValue() || EnableSSIConstruction.getValue(); } }); public enum LSRAVariant { NONSSA_LSAR, - SSA_LSRA + SSA_LSRA, + SSI_LSRA } public static final DerivedOptionValue<LSRAVariant> LinearScanVariant = new DerivedOptionValue<>(new OptionSupplier<LSRAVariant>() { private static final long serialVersionUID = 364925071685235153L; public LSRAVariant get() { + if (LIROptSSILinearScan.getValue()) { + return LSRAVariant.SSI_LSRA; + } if (SSA_LIR.getValue() && !LIREagerSSADestruction.getValue()) { return LSRAVariant.SSA_LSRA; } @@ -71,9 +88,14 @@ public Boolean get() { switch (LinearScanVariant.getValue()) { case SSA_LSRA: + case SSI_LSRA: return true; } + if (TraceRA.getValue()) { + return true; + } return false; } }); + }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/alloc/TraceBuilder.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2015, 2015, 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.compiler.common.alloc; + +import java.util.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; + +public final class TraceBuilder<T extends AbstractBlockBase<T>> { + + public static final class TraceBuilderResult<T extends AbstractBlockBase<T>> { + private final List<List<T>> traces; + private final int[] blockToTrace; + + private TraceBuilderResult(List<List<T>> traces, int[] blockToTrace) { + this.traces = traces; + this.blockToTrace = blockToTrace; + } + + public int getTraceForBlock(AbstractBlockBase<?> block) { + return blockToTrace[block.getId()]; + } + + public List<List<T>> getTraces() { + return traces; + } + } + + /** + * Build traces of sequentially executed blocks + */ + public static <T extends AbstractBlockBase<T>> TraceBuilderResult<T> computeTraces(T startBlock, List<T> blocks) { + return new TraceBuilder<>(blocks).build(startBlock); + } + + private final PriorityQueue<T> worklist; + private final BitSet processed; + /** + * Contains the number of unprocessed predecessors for every {@link AbstractBlockBase#getId() + * block}. + */ + private final int[] blocked; + private final int[] blockToTrace; + + private TraceBuilder(List<T> blocks) { + processed = new BitSet(blocks.size()); + worklist = new PriorityQueue<T>(TraceBuilder::compare); + blocked = new int[blocks.size()]; + blockToTrace = new int[blocks.size()]; + for (T block : blocks) { + blocked[block.getId()] = block.getPredecessorCount(); + } + } + + private static <T extends AbstractBlockBase<T>> int compare(T a, T b) { + return Double.compare(b.probability(), a.probability()); + } + + private boolean processed(T b) { + return processed.get(b.getId()); + } + + private TraceBuilderResult<T> build(T startBlock) { + try (Scope s = Debug.scope("TraceBuilder"); Indent i = Debug.logAndIndent("start trace building: " + startBlock)) { + ArrayList<List<T>> traces = buildTraces(startBlock); + + assert verify(traces); + return new TraceBuilderResult<>(traces, blockToTrace); + } + } + + private boolean verify(ArrayList<List<T>> traces) { + assert traces.stream().flatMap(l -> l.stream()).distinct().count() == blocked.length : "Not all blocks assigned to traces!"; + for (List<T> trace : traces) { + T last = null; + for (T current : trace) { + assert last == null || current.getPredecessors().contains(last); + last = current; + } + } + return true; + } + + protected ArrayList<List<T>> buildTraces(T startBlock) { + ArrayList<List<T>> traces = new ArrayList<>(); + // add start block + worklist.add(startBlock); + // process worklist + while (!worklist.isEmpty()) { + T block = worklist.poll(); + assert block != null; + traces.add(startTrace(block, traces.size())); + } + return traces; + } + + /** + * Build a new trace starting at {@code block}. + */ + private List<T> startTrace(T block, int traceNumber) { + assert block.getPredecessors().stream().allMatch(this::processed) : "Predecessor unscheduled: " + block.getPredecessors().stream().filter(this::processed).findFirst().get(); + ArrayList<T> trace = new ArrayList<>(); + int blockNumber = 0; + try (Indent i = Debug.logAndIndent("StartTrace: " + block)) { + for (T currentBlock = block; currentBlock != null; currentBlock = selectNext(currentBlock)) { + Debug.log("add %s (prob: %f)", currentBlock, currentBlock.probability()); + processed.set(currentBlock.getId()); + worklist.remove(currentBlock); + trace.add(currentBlock); + unblock(currentBlock); + currentBlock.setLinearScanNumber(blockNumber++); + blockToTrace[currentBlock.getId()] = traceNumber; + } + } + return trace; + } + + /** + * Decrease the {@link #blocked} count for all predecessors and add them to the worklist once + * the count reaches 0. + */ + private void unblock(T currentBlock) { + for (T successor : currentBlock.getSuccessors()) { + if (!processed(successor)) { + int blockCount = --blocked[successor.getId()]; + assert blockCount >= 0; + if (blockCount == 0) { + worklist.add(successor); + } + } + } + } + + /** + * @return The unprocessed predecessor with the highest probability, or {@code null}. + */ + private T selectNext(T currentBlock) { + T next = null; + for (T succ : currentBlock.getSuccessors()) { + if (!processed(succ) && (next == null || succ.probability() > next.probability())) { + next = succ; + } + } + return next; + } +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Fri Jul 24 16:20:56 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/LinearScanPhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -42,6 +42,9 @@ RegisterAllocationConfig registerAllocationConfig) { final LinearScan allocator; switch (LinearScanVariant.getValue()) { + case SSI_LSRA: + allocator = new SSILinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, linearScanOrder); + break; case SSA_LSRA: allocator = new SSALinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, linearScanOrder); break;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScan.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,70 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.ssi.*; + +public final class SSILinearScan extends LinearScan { + + public SSILinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + } + + @Override + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { + assert SSIVerifier.verify(lirGenRes.getLIR()) : "LIR not in SSI form."; + super.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new SSILinearScanLifetimeAnalysisPhase(this); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new SSILinearScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSILinearScanEliminateSpillMovePhase(this); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScanEliminateSpillMovePhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.StandardOp.MoveOp; + +public class SSILinearScanEliminateSpillMovePhase extends LinearScanEliminateSpillMovePhase { + + public SSILinearScanEliminateSpillMovePhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected int firstInstructionOfInterest() { + // also look at Labels as they define PHI values + return 0; + } + + @Override + protected boolean canEliminateSpillMove(AbstractBlockBase<?> block, MoveOp move) { + // TODO (je) do not eliminate spill moves yet! + return false; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScanLifetimeAnalysisPhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,122 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import static com.oracle.graal.lir.alloc.lsra.SSALinearScanLifetimeAnalysisPhase.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; +import com.oracle.graal.lir.ssi.*; + +public class SSILinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + public SSILinearScanLifetimeAnalysisPhase(LinearScan linearScan) { + super(linearScan); + } + + @Override + protected void addRegisterHint(final LIRInstruction op, final Value targetValue, OperandMode mode, EnumSet<OperandFlag> flags, final boolean hintAtDef) { + super.addRegisterHint(op, targetValue, mode, flags, hintAtDef); + + if (hintAtDef && op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + + Interval to = allocator.getOrCreateInterval((AllocatableValue) targetValue); + + SSIUtils.forEachRegisterHint(allocator.ir, allocator.blockForId(label.id()), label, targetValue, mode, (ValueConsumer) (registerHint, valueMode, valueFlags) -> { + if (LinearScan.isVariableOrRegister(registerHint)) { + Interval from = allocator.getOrCreateInterval((AllocatableValue) registerHint); + + setHint(op, to, from); + setHint(op, from, to); + } + }); + } + } + + @Override + protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { + assert interval.isSplitParent() : "can only be called for split parents"; + + switch (interval.spillState()) { + case NoDefinitionFound: + // assert interval.spillDefinitionPos() == -1 : "must no be set before"; + interval.setSpillDefinitionPos(defPos); + if (!(op instanceof LabelOp)) { + // Do not update state for labels. This will be done afterwards. + interval.setSpillState(SpillState.NoSpillStore); + } + break; + + case NoSpillStore: + assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; + if (defPos < interval.spillDefinitionPos() - 2) { + // second definition found, so no spill optimization possible for this interval + interval.setSpillState(SpillState.NoOptimization); + } else { + // two consecutive definitions (because of two-operand LIR form) + assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; + } + break; + + case NoOptimization: + // nothing to do + break; + + default: + throw new BailoutException("other states not allowed at this time"); + } + } + + @Override + protected void buildIntervals() { + super.buildIntervals(); + for (Interval interval : allocator.intervals()) { + if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { + // there was a definition in a phi/sigma + interval.setSpillState(SpillState.NoSpillStore); + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + LabelOp label = (LabelOp) op; + if (label.id() != 0) { + // skip method header + return RegisterPriority.None; + } + } + return super.registerPriorityOfOutputOperand(op); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/SSILinearScanResolveDataFlowPhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,127 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class SSILinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + + public SSILinearScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void resolveDataFlow() { + super.resolveDataFlow(); + /* + * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out + * and In value matches (ie. there is no resolution move) are falsely detected as errors. + */ + for (AbstractBlockBase<?> toBlock : allocator.sortedBlocks) { + if (toBlock.getPredecessorCount() != 0) { + SSIUtils.removeIncoming(allocator.ir, toBlock); + } else { + assert allocator.ir.getControlFlowGraph().getStartBlock().equals(toBlock); + } + SSIUtils.removeOutgoing(allocator.ir, toBlock); + } + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + + if (midBlock != null) { + HashMap<Value, Value> map = CollectionsFactory.newMap(); + SSIUtils.forEachValuePair(allocator.ir, midBlock, fromBlock, (to, from) -> map.put(to, from)); + + MyPhiValueVisitor visitor = new MyPhiValueVisitor(moveResolver, toBlock, fromBlock); + SSIUtils.forEachValuePair(allocator.ir, toBlock, midBlock, (to, from) -> { + Value phiOut = isConstant(from) ? from : map.get(from); + assert phiOut != null : "No entry for " + from; + visitor.visit(to, phiOut); + }); + } else { + // default case + SSIUtils.forEachValuePair(allocator.ir, toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); + } + + } + + private class MyPhiValueVisitor implements PhiValueVisitor { + final MoveResolver moveResolver; + final int toId; + final int fromId; + + public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { + this.moveResolver = moveResolver; + toId = allocator.getFirstLirInstructionId(toBlock); + fromId = allocator.getLastLirInstructionId(fromBlock); + assert fromId >= 0; + } + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "Out is a register: " + phiOut; + assert !isRegister(phiIn) : "In is a register: " + phiIn; + if (Value.ILLEGAL.equals(phiIn)) { + // The value not needed in this branch. + return; + } + if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { + // no need to handle virtual stack slots + return; + } + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numSSIResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval) { + numSSIResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceGlobalMoveResolver.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,407 @@ +/* + * Copyright (c) 2009, 2014, 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.lir.alloc.lsra; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.framemap.*; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; + +/** + */ +class TraceGlobalMoveResolver { + + private int insertIdx; + private LIRInsertionBuffer insertionBuffer; // buffer where moves are inserted + + private final List<Value> mappingFrom; + private final List<AllocatableValue> mappingTo; + private final int[] registerBlocked; + private static final int STACK_SLOT_IN_CALLER_FRAME_IDX = -1; + private int[] stackBlocked; + private final int firstVirtualStackIndex; + private final SpillMoveFactory spillMoveFactory; + private final FrameMapBuilder frameMapBuilder; + + private void setValueBlocked(Value location, int direction) { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments can be ignored + return; + } + if (stackIdx >= stackBlocked.length) { + stackBlocked = Arrays.copyOf(stackBlocked, stackIdx + 1); + } + stackBlocked[stackIdx] += direction; + } else { + assert direction == 1 || direction == -1 : "out of bounds"; + if (isRegister(location)) { + registerBlocked[asRegister(location).number] += direction; + } else { + throw JVMCIError.shouldNotReachHere("unhandled value " + location); + } + } + } + + private int valueBlocked(Value location) { + if (isStackSlotValue(location)) { + int stackIdx = getStackArrayIndex(asStackSlotValue(location)); + if (stackIdx == STACK_SLOT_IN_CALLER_FRAME_IDX) { + // incoming stack arguments are always blocked (aka they can not be written) + return 1; + } + if (stackIdx >= stackBlocked.length) { + return 0; + } + return stackBlocked[stackIdx]; + } + if (isRegister(location)) { + return registerBlocked[asRegister(location).number]; + } + throw JVMCIError.shouldNotReachHere("unhandled value " + location); + } + + private static boolean areMultipleReadsAllowed() { + return true; + } + + private boolean hasMappings() { + return mappingFrom.size() > 0; + } + + private SpillMoveFactory getSpillMoveFactory() { + return spillMoveFactory; + } + + private Register[] getRegisters() { + return frameMapBuilder.getRegisterConfig().getAllocatableRegisters(); + } + + public TraceGlobalMoveResolver(LIRGenerationResult res, SpillMoveFactory spillMoveFactory, Architecture arch) { + + this.mappingFrom = new ArrayList<>(8); + this.mappingTo = new ArrayList<>(8); + this.insertIdx = -1; + this.insertionBuffer = new LIRInsertionBuffer(); + + this.frameMapBuilder = res.getFrameMapBuilder(); + this.spillMoveFactory = spillMoveFactory; + this.registerBlocked = new int[arch.getRegisters().length]; + + FrameMapBuilderTool frameMapBuilderTool = (FrameMapBuilderTool) frameMapBuilder; + this.stackBlocked = new int[frameMapBuilderTool.getNumberOfStackSlots()]; + + FrameMap frameMap = frameMapBuilderTool.getFrameMap(); + this.firstVirtualStackIndex = !frameMap.frameNeedsAllocating() ? 0 : frameMap.currentFrameSize() + 1; + } + + private boolean checkEmpty() { + for (int i = 0; i < stackBlocked.length; i++) { + assert stackBlocked[i] == 0 : "stack map must be empty before and after processing"; + } + assert mappingFrom.size() == 0 && mappingTo.size() == 0 : "list must be empty before and after processing"; + for (int i = 0; i < getRegisters().length; i++) { + assert registerBlocked[i] == 0 : "register map must be empty before and after processing"; + } + return true; + } + + private boolean verifyBeforeResolve() { + assert mappingFrom.size() == mappingTo.size() : "length must be equal"; + assert insertIdx != -1 : "insert position not set"; + + int i; + int j; + if (!areMultipleReadsAllowed()) { + for (i = 0; i < mappingFrom.size(); i++) { + for (j = i + 1; j < mappingFrom.size(); j++) { + assert mappingFrom.get(i) == null || mappingFrom.get(i) != mappingFrom.get(j) : "cannot read from same interval twice"; + } + } + } + + for (i = 0; i < mappingTo.size(); i++) { + for (j = i + 1; j < mappingTo.size(); j++) { + assert mappingTo.get(i) != mappingTo.get(j) : "cannot write to same interval twice"; + } + } + + for (i = 0; i < mappingTo.size(); i++) { + Value to = mappingTo.get(i); + assert !isStackSlotValue(to) || getStackArrayIndex(asStackSlotValue(to)) != STACK_SLOT_IN_CALLER_FRAME_IDX : "Cannot move to in argument: " + to; + } + + HashSet<Value> usedRegs = new HashSet<>(); + if (!areMultipleReadsAllowed()) { + for (i = 0; i < mappingFrom.size(); i++) { + Value from = mappingFrom.get(i); + if (from != null && !isIllegal(from)) { + boolean unique = usedRegs.add(from); + assert unique : "cannot read from same register twice"; + } + } + } + + usedRegs.clear(); + for (i = 0; i < mappingTo.size(); i++) { + Value to = mappingTo.get(i); + if (isIllegal(to)) { + // After insertion the location may become illegal, so don't check it since multiple + // intervals might be illegal. + continue; + } + boolean unique = usedRegs.add(to); + assert unique : "cannot write to same register twice"; + } + + return true; + } + + // mark assignedReg and assignedRegHi of the interval as blocked + private void block(Value location) { + if (mightBeBlocked(location)) { + assert areMultipleReadsAllowed() || valueBlocked(location) == 0 : "location already marked as used: " + location; + setValueBlocked(location, 1); + Debug.log("block %s", location); + } + } + + // mark assignedReg and assignedRegHi of the interval as unblocked + private void unblock(Value location) { + if (mightBeBlocked(location)) { + assert valueBlocked(location) > 0 : "location already marked as unused: " + location; + setValueBlocked(location, -1); + Debug.log("unblock %s", location); + } + } + + /** + * Checks if the {@linkplain Interval#location() location} of {@code to} is not blocked or is + * only blocked by {@code from}. + */ + private boolean safeToProcessMove(Value fromLocation, Value toLocation) { + if (mightBeBlocked(toLocation)) { + if ((valueBlocked(toLocation) > 1 || (valueBlocked(toLocation) == 1 && !isMoveToSelf(fromLocation, toLocation)))) { + return false; + } + } + + return true; + } + + public static boolean isMoveToSelf(Value from, Value to) { + assert to != null; + if (to.equals(from)) { + return true; + } + if (from != null && isRegister(from) && isRegister(to) && asRegister(from).equals(asRegister(to))) { + assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Same register but Kind mismatch %s <- %s", to, from); + return true; + } + return false; + } + + private static boolean mightBeBlocked(Value location) { + return isRegister(location) || isStackSlotValue(location); + } + + private void createInsertionBuffer(List<LIRInstruction> list) { + assert !insertionBuffer.initialized() : "overwriting existing buffer"; + insertionBuffer.init(list); + } + + private void appendInsertionBuffer() { + if (insertionBuffer.initialized()) { + insertionBuffer.finish(); + } + assert !insertionBuffer.initialized() : "must be uninitialized now"; + + insertIdx = -1; + } + + private void insertMove(Value fromOperand, AllocatableValue toOperand) { + assert !fromOperand.equals(toOperand) : "from and to are equal: " + fromOperand + " vs. " + toOperand; + assert LIRKind.verifyMoveKinds(fromOperand.getLIRKind(), fromOperand.getLIRKind()) : "move between different types"; + assert insertIdx != -1 : "must setup insert position first"; + + insertionBuffer.append(insertIdx, createMove(fromOperand, toOperand)); + + if (Debug.isLogEnabled()) { + Debug.log("insert move from %s to %s at %d", fromOperand, toOperand, insertIdx); + } + } + + /** + * @param fromOpr {@link Interval#operand operand} of the {@code from} interval + * @param toOpr {@link Interval#operand operand} of the {@code to} interval + */ + private LIRInstruction createMove(Value fromOpr, AllocatableValue toOpr) { + if (isStackSlotValue(toOpr) && isStackSlotValue(fromOpr)) { + return getSpillMoveFactory().createStackMove(toOpr, fromOpr); + } + return getSpillMoveFactory().createMove(toOpr, fromOpr); + } + + private void resolveMappings() { + try (Indent indent = Debug.logAndIndent("resolveMapping")) { + assert verifyBeforeResolve(); + if (Debug.isLogEnabled()) { + printMapping(); + } + + // Block all registers that are used as input operands of a move. + // When a register is blocked, no move to this register is emitted. + // This is necessary for detecting cycles in moves. + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Value from = mappingFrom.get(i); + block(from); + } + + int spillCandidate = -1; + while (mappingFrom.size() > 0) { + boolean processedInterval = false; + + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Value fromInterval = mappingFrom.get(i); + AllocatableValue toInterval = mappingTo.get(i); + + Value fromLocation = fromInterval; + AllocatableValue toLocation = toInterval; + if (safeToProcessMove(fromLocation, toLocation)) { + // this interval can be processed because target is free + insertMove(fromLocation, toLocation); + unblock(fromLocation); + mappingFrom.remove(i); + mappingTo.remove(i); + + processedInterval = true; + } else if (fromInterval != null && isRegister(fromLocation)) { + // this interval cannot be processed now because target is not free + // it starts in a register, so it is a possible candidate for spilling + spillCandidate = i; + } + } + + if (!processedInterval) { + breakCycle(spillCandidate); + } + } + } + + // check that all intervals have been processed + assert checkEmpty(); + } + + private void breakCycle(int spillCandidate) { + // no move could be processed because there is a cycle in the move list + // (e.g. r1 . r2, r2 . r1), so one interval must be spilled to memory + assert spillCandidate != -1 : "no interval in register for spilling found"; + + // create a new spill interval and assign a stack slot to it + Value from = mappingFrom.get(spillCandidate); + try (Indent indent = Debug.logAndIndent("BreakCycle: %s", from)) { + StackSlotValue spillSlot = frameMapBuilder.allocateSpillSlot(from.getLIRKind()); + if (Debug.isLogEnabled()) { + Debug.log("created new slot for spilling: %s", spillSlot); + } + // insert a move from register to stack and update the mapping + insertMove(from, spillSlot); + block(spillSlot); + mappingFrom.set(spillCandidate, spillSlot); + unblock(from); + } + } + + private void printMapping() { + try (Indent indent = Debug.logAndIndent("Mapping")) { + for (int i = mappingFrom.size() - 1; i >= 0; i--) { + Debug.log("move %s <- %s", mappingTo.get(i), mappingFrom.get(i)); + } + } + } + + public void setInsertPosition(List<LIRInstruction> insertList, int insertIdx) { + assert this.insertIdx == -1 : "use moveInsertPosition instead of setInsertPosition when data already set"; + + createInsertionBuffer(insertList); + this.insertIdx = insertIdx; + } + + public void addMapping(Value from, AllocatableValue to) { + if (Debug.isLogEnabled()) { + Debug.log("add move mapping from %s to %s", from, to); + } + + assert !from.equals(to) : "from and to interval equal: " + from; + assert LIRKind.verifyMoveKinds(to.getLIRKind(), from.getLIRKind()) : String.format("Kind mismatch: %s vs. %s, from=%s, to=%s", from.getLIRKind(), to.getLIRKind(), from, to); + mappingFrom.add(from); + mappingTo.add(to); + } + + public void resolveAndAppendMoves() { + if (hasMappings()) { + resolveMappings(); + } + appendInsertionBuffer(); + } + + private int getStackArrayIndex(StackSlotValue stackSlotValue) { + if (isStackSlot(stackSlotValue)) { + return getStackArrayIndex(asStackSlot(stackSlotValue)); + } + if (isVirtualStackSlot(stackSlotValue)) { + return getStackArrayIndex(asVirtualStackSlot(stackSlotValue)); + } + throw JVMCIError.shouldNotReachHere("Unhandled StackSlotValue: " + stackSlotValue); + } + + private int getStackArrayIndex(StackSlot stackSlot) { + int stackIdx; + if (stackSlot.isInCallerFrame()) { + // incoming stack arguments can be ignored + stackIdx = STACK_SLOT_IN_CALLER_FRAME_IDX; + } else { + assert stackSlot.getRawAddFrameSize() : "Unexpected stack slot: " + stackSlot; + int offset = -stackSlot.getRawOffset(); + assert 0 <= offset && offset < firstVirtualStackIndex : String.format("Wrong stack slot offset: %d (first virtual stack slot index: %d", offset, firstVirtualStackIndex); + stackIdx = offset; + } + return stackIdx; + } + + private int getStackArrayIndex(VirtualStackSlot virtualStackSlot) { + return firstVirtualStackIndex + virtualStackSlot.getId(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScan.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import static com.oracle.graal.compiler.common.GraalOptions.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; + +public final class TraceLinearScan extends LinearScan { + + private final TraceBuilderResult<?> traceBuilderResult; + + public TraceLinearScan(TargetDescription target, LIRGenerationResult res, SpillMoveFactory spillMoveFactory, RegisterAllocationConfig regAllocConfig, + List<? extends AbstractBlockBase<?>> sortedBlocks, TraceBuilderResult<?> traceBuilderResult) { + super(target, res, spillMoveFactory, regAllocConfig, sortedBlocks); + this.traceBuilderResult = traceBuilderResult; + } + + @Override + protected <B extends AbstractBlockBase<B>> void allocate(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, + SpillMoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig) { + + /* + * This is the point to enable debug logging for the whole register allocation. + */ + try (Indent indent = Debug.logAndIndent("LinearScan allocate")) { + AllocationContext context = new AllocationContext(spillMoveFactory, registerAllocationConfig); + + createLifetimeAnalysisPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + try (Scope s = Debug.scope("AfterLifetimeAnalysis", (Object) intervals)) { + sortIntervalsBeforeAllocation(); + + createRegisterAllocationPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + if (LinearScan.Options.LSRAOptimizeSpillPosition.getValue()) { + createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + } + // resolve intra-trace data-flow + LinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase(); + dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks, "%s", dataFlowPhase.getName()); + + LinearScanAssignLocationsPhase assignPhase = createAssignLocationsPhase(); + assignPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); + + if (DetailedAsserts.getValue()) { + verifyIntervals(); + } + } catch (Throwable e) { + throw Debug.handle(e); + } + } + } + + @Override + protected MoveResolver createMoveResolver() { + SSAMoveResolver moveResolver = new SSAMoveResolver(this); + assert moveResolver.checkEmpty(); + return moveResolver; + } + + @Override + protected LinearScanLifetimeAnalysisPhase createLifetimeAnalysisPhase() { + return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult); + } + + @Override + protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + return new TraceLinearScanResolveDataFlowPhase(this); + } + + @Override + protected LinearScanEliminateSpillMovePhase createSpillMoveEliminationPhase() { + return new SSILinearScanEliminateSpillMovePhase(this); + } + + @Override + void printIntervals(String label) { + if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { + super.printIntervals(label); + } + } + + @Override + void printLir(String label, boolean hirValid) { + if (Debug.isDumpEnabled(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL)) { + Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks, label); + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanLifetimeAnalysisPhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,288 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.lir.LIRValueUtil.*; +import static com.oracle.graal.lir.alloc.lsra.TraceRegisterAllocationPhase.Options.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.common.*; +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.alloc.lsra.Interval.RegisterPriority; +import com.oracle.graal.lir.alloc.lsra.Interval.SpillState; +import com.oracle.graal.lir.alloc.lsra.LinearScan.BlockData; +import com.oracle.graal.lir.ssi.*; + +public class TraceLinearScanLifetimeAnalysisPhase extends LinearScanLifetimeAnalysisPhase { + + private final TraceBuilderResult<?> traceBuilderResult; + + public TraceLinearScanLifetimeAnalysisPhase(LinearScan linearScan, TraceBuilderResult<?> traceBuilderResult) { + super(linearScan); + this.traceBuilderResult = traceBuilderResult; + } + + private boolean sameTrace(AbstractBlockBase<?> a, AbstractBlockBase<?> b) { + return traceBuilderResult.getTraceForBlock(b) == traceBuilderResult.getTraceForBlock(a); + } + + private boolean isAllocatedOrCurrent(AbstractBlockBase<?> currentBlock, AbstractBlockBase<?> other) { + return traceBuilderResult.getTraceForBlock(other) <= traceBuilderResult.getTraceForBlock(currentBlock); + } + + static void setHint(final LIRInstruction op, Interval target, Interval source) { + Interval currentHint = target.locationHint(false); + if (currentHint == null || currentHint.from() > target.from()) { + /* + * Update hint if there was none or if the hint interval starts after the hinted + * interval. + */ + target.setLocationHint(source); + if (Debug.isLogEnabled()) { + Debug.log("operation at opId %d: added hint from interval %d (%s) to %d (%s)", op.id(), source.operandNumber, source, target.operandNumber, target); + } + } + } + + @Override + protected void changeSpillDefinitionPos(LIRInstruction op, AllocatableValue operand, Interval interval, int defPos) { + assert interval.isSplitParent() : "can only be called for split parents"; + + switch (interval.spillState()) { + case NoDefinitionFound: + // assert interval.spillDefinitionPos() == -1 : "must no be set before"; + interval.setSpillDefinitionPos(defPos); + if (!(op instanceof LabelOp)) { + // Do not update state for labels. This will be done afterwards. + interval.setSpillState(SpillState.NoSpillStore); + } + break; + + case NoSpillStore: + assert defPos <= interval.spillDefinitionPos() : "positions are processed in reverse order when intervals are created"; + if (defPos < interval.spillDefinitionPos() - 2) { + // second definition found, so no spill optimization possible for this interval + interval.setSpillState(SpillState.NoOptimization); + } else { + // two consecutive definitions (because of two-operand LIR form) + assert allocator.blockForId(defPos) == allocator.blockForId(interval.spillDefinitionPos()) : "block must be equal"; + } + break; + + case NoOptimization: + // nothing to do + break; + + default: + throw new BailoutException("other states not allowed at this time"); + } + } + + @Override + protected void buildIntervals() { + super.buildIntervals(); + // fix spill state for phi/sigma intervals + for (Interval interval : allocator.intervals()) { + if (interval != null && interval.spillState().equals(SpillState.NoDefinitionFound) && interval.spillDefinitionPos() != -1) { + // there was a definition in a phi/sigma + interval.setSpillState(SpillState.NoSpillStore); + } + } + if (TraceRAuseInterTraceHints.getValue()) { + addInterTraceHints(); + } + } + + private void addInterTraceHints() { + // set hints for phi/sigma intervals + LIR lir = allocator.ir; + for (AbstractBlockBase<?> block : allocator.sortedBlocks) { + LabelOp label = SSIUtils.incoming(lir, block); + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + if (isAllocatedOrCurrent(block, pred)) { + BlockEndOp outgoing = SSIUtils.outgoing(lir, pred); + for (int i = 0; i < outgoing.getOutgoingSize(); i++) { + Value toValue = label.getIncomingValue(i); + if (!isIllegal(toValue)) { + Value fromValue = outgoing.getOutgoingValue(i); + assert sameTrace(block, pred) || !isVariable(fromValue) : "Unallocated variable: " + fromValue; + + if (isStackSlotValue(fromValue)) { + + } else if (isConstant(fromValue)) { + } else { + Interval from = allocator.getOrCreateInterval((AllocatableValue) fromValue); + Interval to = allocator.getOrCreateInterval((AllocatableValue) toValue); + setHint(label, to, from); + } + } + } + } + } + } + /* + * Set the first range for fixed intervals to [-1, 0] to avoid intersection with incoming + * values. + */ + for (Interval interval : allocator.intervals()) { + if (interval != null && isRegister(interval.operand)) { + Range range = interval.first(); + if (range == Range.EndMarker) { + interval.addRange(-1, 0); + } else if (range.from == 0 && range.to == 1) { + range.from = -1; + range.to = 0; + } + } + } + } + + @Override + protected RegisterPriority registerPriorityOfOutputOperand(LIRInstruction op) { + if (op instanceof LabelOp) { + // skip method header + return RegisterPriority.None; + } + return super.registerPriorityOfOutputOperand(op); + } + + @Override + void handleMethodArguments(LIRInstruction op) { + if (op instanceof MoveOp) { + // do not optimize method arguments + return; + } + super.handleMethodArguments(op); + } + + /** + * Performs a backward dataflow analysis to compute global live sets (i.e. + * {@link BlockData#liveIn} and {@link BlockData#liveOut}) for each block. + */ + @Override + protected void computeGlobalLiveSets() { + try (Indent indent = Debug.logAndIndent("compute global live sets")) { + int numBlocks = allocator.blockCount(); + boolean changeOccurred; + boolean changeOccurredInBlock; + int iterationCount = 0; + BitSet liveOut = new BitSet(allocator.liveSetSize()); // scratch set for calculations + + /* + * Perform a backward dataflow analysis to compute liveOut and liveIn for each block. + * The loop is executed until a fixpoint is reached (no changes in an iteration). + */ + do { + changeOccurred = false; + + try (Indent indent2 = Debug.logAndIndent("new iteration %d", iterationCount)) { + + // iterate all blocks in reverse order + for (int i = numBlocks - 1; i >= 0; i--) { + AbstractBlockBase<?> block = allocator.blockAt(i); + BlockData blockSets = allocator.getBlockData(block); + + changeOccurredInBlock = false; + + /* liveOut(block) is the union of liveIn(sux), for successors sux of block. */ + int n = block.getSuccessorCount(); + if (n > 0) { + liveOut.clear(); + // block has successors + if (n > 0) { + for (AbstractBlockBase<?> successor : block.getSuccessors()) { + if (allocator.sortedBlocks.contains(successor)) { + liveOut.or(allocator.getBlockData(successor).liveIn); + } + } + } + + if (!blockSets.liveOut.equals(liveOut)) { + /* + * A change occurred. Swap the old and new live out sets to avoid + * copying. + */ + BitSet temp = blockSets.liveOut; + blockSets.liveOut = liveOut; + liveOut = temp; + + changeOccurred = true; + changeOccurredInBlock = true; + } + } + + if (iterationCount == 0 || changeOccurredInBlock) { + /* + * liveIn(block) is the union of liveGen(block) with (liveOut(block) & + * !liveKill(block)). + * + * Note: liveIn has to be computed only in first iteration or if liveOut + * has changed! + */ + BitSet liveIn = blockSets.liveIn; + liveIn.clear(); + liveIn.or(blockSets.liveOut); + liveIn.andNot(blockSets.liveKill); + liveIn.or(blockSets.liveGen); + + if (Debug.isLogEnabled()) { + Debug.log("block %d: livein = %s, liveout = %s", block.getId(), liveIn, blockSets.liveOut); + } + } + } + iterationCount++; + + if (changeOccurred && iterationCount > 50) { + throw new BailoutException("too many iterations in computeGlobalLiveSets"); + } + } + } while (changeOccurred); + + if (DetailedAsserts.getValue()) { + verifyLiveness(); + } + + // check that the liveIn set of the first block is empty + AbstractBlockBase<?> startBlock = allocator.blockAt(0); + if (allocator.getBlockData(startBlock).liveIn.cardinality() != 0) { + if (DetailedAsserts.getValue()) { + reportFailure(numBlocks); + } + // bailout if this occurs in product mode. + throw new JVMCIError("liveIn set of first block must be empty: " + allocator.getBlockData(startBlock).liveIn); + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceLinearScanResolveDataFlowPhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,107 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class TraceLinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { + + private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + + public TraceLinearScanResolveDataFlowPhase(LinearScan allocator) { + super(allocator); + } + + @Override + protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { + // do not optimize + } + + @Override + protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + assert midBlock == null; + if (containedInTrace(fromBlock) && containedInTrace(toBlock)) { + super.resolveCollectMappings(fromBlock, toBlock, midBlock, moveResolver); + SSIUtils.forEachValuePair(allocator.ir, toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); + } + + } + + private boolean containedInTrace(AbstractBlockBase<?> block) { + return allocator.sortedBlocks.contains(block); + } + + private class MyPhiValueVisitor implements PhiValueVisitor { + final MoveResolver moveResolver; + final int toId; + final int fromId; + + public MyPhiValueVisitor(MoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { + this.moveResolver = moveResolver; + toId = allocator.getFirstLirInstructionId(toBlock); + fromId = allocator.getLastLirInstructionId(fromBlock); + assert fromId >= 0; + } + + public void visit(Value phiIn, Value phiOut) { + assert !isRegister(phiOut) : "Out is a register: " + phiOut; + assert !isRegister(phiIn) : "In is a register: " + phiIn; + if (Value.ILLEGAL.equals(phiIn)) { + // The value not needed in this branch. + return; + } + if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { + // no need to handle virtual stack slots + return; + } + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); + if (isConstant(phiOut)) { + numSSIResolutionMoves.increment(); + moveResolver.addMapping(phiOut, toInterval); + } else { + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); + if (fromInterval != toInterval) { + numSSIResolutionMoves.increment(); + if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { + moveResolver.addMapping(fromInterval, toInterval); + } else { + numStackToStackMoves.increment(); + moveResolver.addMapping(fromInterval, toInterval); + } + } + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/lsra/TraceRegisterAllocationPhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.alloc.lsra; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.code.*; +import jdk.internal.jvmci.meta.*; +import jdk.internal.jvmci.options.*; + +import com.oracle.graal.compiler.common.alloc.*; +import com.oracle.graal.compiler.common.alloc.TraceBuilder.TraceBuilderResult; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; +import com.oracle.graal.lir.phases.*; +import com.oracle.graal.lir.ssa.SSAUtils.PhiValueVisitor; +import com.oracle.graal.lir.ssi.*; + +public class TraceRegisterAllocationPhase extends AllocationPhase { + public static class Options { + // @formatter:off + @Option(help = "Use inter-trace register hints.", type = OptionType.Debug) + public static final OptionValue<Boolean> TraceRAuseInterTraceHints = new OptionValue<>(true); + // @formatter:on + } + + static final int TRACE_DUMP_LEVEL = 3; + + @Override + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, + RegisterAllocationConfig registerAllocationConfig) { + LIR lir = lirGenRes.getLIR(); + assert SSIVerifier.verify(lir) : "LIR not in SSI form."; + B startBlock = linearScanOrder.get(0); + assert startBlock.equals(lir.getControlFlowGraph().getStartBlock()); + TraceBuilderResult<B> resultTraces = TraceBuilder.computeTraces(startBlock, linearScanOrder); + + Debug.dump(lir, "Before TraceRegisterAllocation"); + int traceNumber = 0; + for (List<B> trace : resultTraces.getTraces()) { + try (Indent i = Debug.logAndIndent("Allocating Trace%d: %s", traceNumber, trace); Scope s = Debug.scope("AllocateTrace", trace)) { + Debug.dump(TRACE_DUMP_LEVEL, trace, "Trace" + traceNumber + ": " + trace); + TraceLinearScan allocator = new TraceLinearScan(target, lirGenRes, spillMoveFactory, registerAllocationConfig, trace, resultTraces); + allocator.allocate(target, lirGenRes, codeEmittingOrder, linearScanOrder, spillMoveFactory, registerAllocationConfig); + Debug.dump(TRACE_DUMP_LEVEL, trace, "After Trace" + traceNumber + ": " + trace); + traceNumber++; + } catch (Throwable e) { + throw Debug.handle(e); + } + unnumberInstructions(trace, lir); + } + Debug.dump(lir, "After trace allocation"); + + resolveGlobalDataFlow(resultTraces, lirGenRes, spillMoveFactory, target.arch); + Debug.dump(lir, "After global dataflow resolution"); + + if (replaceStackToStackMoves(lir, spillMoveFactory)) { + Debug.dump(lir, "After fixing stack to stack moves"); + } + /* + * Incoming Values are needed for the RegisterVerifier, otherwise SIGMAs/PHIs where the Out + * and In value matches (ie. there is no resolution move) are falsely detected as errors. + */ + for (AbstractBlockBase<?> toBlock : lir.getControlFlowGraph().getBlocks()) { + if (toBlock.getPredecessorCount() != 0) { + SSIUtils.removeIncoming(lir, toBlock); + } else { + assert lir.getControlFlowGraph().getStartBlock().equals(toBlock); + } + SSIUtils.removeOutgoing(lir, toBlock); + } + } + + /** + * Fixup stack to stack moves introduced by stack arguments. + * + * TODO (je) find a better solution. + */ + private static boolean replaceStackToStackMoves(LIR lir, SpillMoveFactory spillMoveFactory) { + boolean changed = false; + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + for (int i = 0; i < instructions.size(); i++) { + LIRInstruction inst = instructions.get(i); + + if (inst instanceof MoveOp) { + MoveOp move = (MoveOp) inst; + if (isStackSlotValue(move.getInput()) && isStackSlotValue(move.getResult())) { + instructions.set(i, spillMoveFactory.createStackMove(move.getResult(), move.getInput())); + changed = true; + } + } + } + } + return changed; + } + + private static <B extends AbstractBlockBase<B>> void resolveGlobalDataFlow(TraceBuilderResult<B> resultTraces, LIRGenerationResult lirGenRes, SpillMoveFactory spillMoveFactory, Architecture arch) { + LIR lir = lirGenRes.getLIR(); + /* Resolve trace global data-flow mismatch. */ + TraceGlobalMoveResolver moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, arch); + PhiValueVisitor visitor = (Value phiIn, Value phiOut) -> { + if (!isIllegal(phiIn) && !TraceGlobalMoveResolver.isMoveToSelf(phiOut, phiIn)) { + moveResolver.addMapping(phiOut, (AllocatableValue) phiIn); + } + }; + + try (Indent indent = Debug.logAndIndent("Trace global move resolution")) { + for (List<B> trace : resultTraces.getTraces()) { + for (AbstractBlockBase<?> fromBlock : trace) { + for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { + if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) { + try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock), toBlock, + resultTraces.getTraceForBlock(toBlock))) { + + final List<LIRInstruction> instructions; + final int insertIdx; + if (fromBlock.getSuccessorCount() == 1) { + instructions = lir.getLIRforBlock(fromBlock); + insertIdx = instructions.size() - 1; + } else { + assert toBlock.getPredecessorCount() == 1; + instructions = lir.getLIRforBlock(toBlock); + insertIdx = 1; + } + + moveResolver.setInsertPosition(instructions, insertIdx); + SSIUtils.forEachValuePair(lir, toBlock, fromBlock, visitor); + moveResolver.resolveAndAppendMoves(); + } + } + } + } + } + } + } + + private static void unnumberInstructions(List<? extends AbstractBlockBase<?>> trace, LIR lir) { + trace.stream().flatMap(b -> lir.getLIRforBlock(b).stream()).forEach(op -> op.setId(-1)); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/BlockValueMap.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.gen; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; + +public interface BlockValueMap { + + void accessOperand(Value operand, AbstractBlockBase<?> block); + + void defineOperand(Value operand, AbstractBlockBase<?> block); + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/gen/SSIBlockValueMapImpl.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,246 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.gen; + +import static com.oracle.graal.lir.LIRValueUtil.*; +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.LabelOp; +import com.oracle.graal.lir.util.*; + +public class SSIBlockValueMapImpl implements BlockValueMap { + + private final class BlockData { + + /** Mapping from value to index into {@link #incoming} */ + private final ValueMap<Value, Integer> valueIndexMap; + private final ArrayList<Value> incoming; + private final ArrayList<Value> outgoing; + + private BlockData() { + valueIndexMap = new GenericValueMap<>(); + incoming = new ArrayList<>(); + outgoing = new ArrayList<>(); + } + + public Integer getIndex(Value operand) { + return valueIndexMap.get(operand); + } + + public Value getIncoming(int index) { + return incoming.get(index); + } + + public void setIncoming(int index, Value value) { + incoming.set(index, value); + } + + public int addIncoming(Value operand) { + int index = incoming.size(); + incoming.add(Value.ILLEGAL); + valueIndexMap.put(operand, index); + return index; + } + + public boolean contains(Value operand) { + return getIndex(operand) != null; + } + + public int addOutgoing(Value operand) { + int index = outgoing.size(); + outgoing.add(operand); + return index; + } + + } + + /** Mapping from value to definition block. */ + private final ValueMap<Value, AbstractBlockBase<?>> valueToDefBlock; + private final BlockMap<BlockData> blockData; + + public SSIBlockValueMapImpl(AbstractControlFlowGraph<?> cfg) { + valueToDefBlock = new GenericValueMap<>(); + blockData = new BlockMap<>(cfg); + } + + @Override + public void accessOperand(Value operand, AbstractBlockBase<?> block) { + assert block != null : "block is null"; + if (operand instanceof CompositeValue) { + ((CompositeValue) operand).forEachComponent(null, OperandMode.USE, (op, value, mode, flag) -> { + accessOperand(value, block); + return value; + }); + } else if (processValue(operand)) { + AbstractBlockBase<?> defBlock = getDefinitionBlock(operand); + assert defBlock != null : "Value is not defined: " + operand; + assert AbstractControlFlowGraph.dominates(defBlock, block) : "Block " + defBlock + " does not dominate " + block; + accessRecursive(operand, defBlock, block); + } + } + + @Override + public void defineOperand(Value operand, AbstractBlockBase<?> block) { + assert block != null : "block is null"; + if (processValue(operand)) { + AbstractBlockBase<?> defBlock = getDefinitionBlock(operand); + if (defBlock == null) { + setDefinitionBlock(operand, block); + } else { + /* + * Redefinition: this can happen for nodes that do not produce a new value but proxy + * another one (PiNode, reinterpret). + */ + assert AbstractControlFlowGraph.dominates(defBlock, block) : String.format("Definition of %s in %s does not dominate the redefinition %s", operand, defBlock, block); + } + } + } + + private static boolean processValue(Value operand) { + return isVariable(operand) || isVirtualStackSlot(operand); + } + + // setter getter for internal data structures + + private AbstractBlockBase<?> getDefinitionBlock(Value operand) { + return valueToDefBlock.get(operand); + } + + private void setDefinitionBlock(Value operand, AbstractBlockBase<?> block) { + valueToDefBlock.put(operand, block); + } + + private BlockData getOrInit(AbstractBlockBase<?> block) { + BlockData data = blockData.get(block); + if (data == null) { + data = new BlockData(); + blockData.put(block, data); + } + return data; + } + + // implementation + + private void accessRecursive(Value operand, AbstractBlockBase<?> defBlock, AbstractBlockBase<?> block) { + try (Indent indent = Debug.logAndIndent("get operand %s in block %s", operand, block)) { + if (block.equals(defBlock)) { + Debug.log("found definition!"); + return; + } + BlockData data = getOrInit(block); + Integer index = data.getIndex(operand); + if (index != null) { + // value is live at block begin but might not be initialized + Value in = data.getIncoming(index); + if (Value.ILLEGAL.equals(in)) { + data.setIncoming(index, operand); + Debug.log("uninitialized incoming value -> initialize!"); + } else { + Debug.log("incoming value already initialized!"); + } + return; + } + + // the value is not yet live a current block + int idx = addLiveValueToBlock(operand, block); + data.setIncoming(idx, operand); + + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + accessRecursive(operand, defBlock, pred); + } + } + } + + private int addLiveValueToBlock(Value operand, AbstractBlockBase<?> block) { + try (Indent indent = Debug.logAndIndent("add incoming value!")) { + int index = -1; + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + try (Indent indent1 = Debug.logAndIndent("Add outgoing operand to %s", pred)) { + BlockData predData = getOrInit(pred); + int predIndex = predData.addOutgoing(operand); + + if (index == -1) { + index = predIndex; + } else { + assert predIndex == index; + } + + for (AbstractBlockBase<?> succ : pred.getSuccessors()) { + Debug.log("Add incoming operand to %s", succ); + BlockData succData = getOrInit(succ); + if (!succData.contains(operand)) { + int succIndex = succData.addIncoming(operand); + assert succIndex == predIndex; + } + } + } + } + Debug.log("new index: %d", index); + return index; + } + } + + // finish + + public void finish(LIRGeneratorTool gen) { + Debug.dump(gen.getResult().getLIR(), "Before SSI operands"); + AbstractControlFlowGraph<?> cfg = gen.getResult().getLIR().getControlFlowGraph(); + for (AbstractBlockBase<?> block : cfg.getBlocks()) { + // set label + BlockData data = blockData.get(block); + if (data != null) { + if (data.incoming != null && data.incoming.size() > 0) { + LabelOp label = getLabel(gen, block); + label.addIncomingValues(data.incoming.toArray(new Value[data.incoming.size()])); + } + // set block end + if (data.outgoing != null && data.outgoing.size() > 0) { + BlockEndOp blockEndOp = getBlockEnd(gen, block); + blockEndOp.addOutgoingValues(data.outgoing.toArray(new Value[data.outgoing.size()])); + } + } + } + } + + private static List<LIRInstruction> getLIRforBlock(LIRGeneratorTool gen, AbstractBlockBase<?> block) { + return gen.getResult().getLIR().getLIRforBlock(block); + } + + private static LabelOp getLabel(LIRGeneratorTool gen, AbstractBlockBase<?> block) { + return (LabelOp) getLIRforBlock(gen, block).get(0); + } + + private static BlockEndOp getBlockEnd(LIRGeneratorTool gen, AbstractBlockBase<?> block) { + List<LIRInstruction> instructions = getLIRforBlock(gen, block); + return (BlockEndOp) instructions.get(instructions.size() - 1); + } +}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java Fri Jul 24 16:20:56 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/AllocationStage.java Fri Jul 24 10:55:33 2015 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.lir.phases; +import static com.oracle.graal.compiler.common.BackendOptions.UserOptions.*; import com.oracle.graal.lir.alloc.lsra.*; import com.oracle.graal.lir.dfa.*; import com.oracle.graal.lir.phases.AllocationPhase.AllocationContext; @@ -30,7 +31,11 @@ public class AllocationStage extends LIRPhaseSuite<AllocationContext> { public AllocationStage() { appendPhase(new MarkBasePointersPhase()); - appendPhase(new LinearScanPhase()); + if (TraceRA.getValue()) { + appendPhase(new TraceRegisterAllocationPhase()); + } else { + appendPhase(new LinearScanPhase()); + } // build frame map if (LSStackSlotAllocator.Options.LIROptLSStackSlotAllocator.getValue()) {
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java Fri Jul 24 16:20:56 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/phases/PreAllocationOptimizationStage.java Fri Jul 24 10:55:33 2015 +0200 @@ -23,11 +23,13 @@ package com.oracle.graal.lir.phases; import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.compiler.common.BackendOptions.*; import com.oracle.graal.compiler.common.*; import com.oracle.graal.lir.constopt.*; import com.oracle.graal.lir.phases.PreAllocationOptimizationPhase.PreAllocationOptimizationContext; import com.oracle.graal.lir.ssa.*; +import com.oracle.graal.lir.ssi.*; public class PreAllocationOptimizationStage extends LIRPhaseSuite<PreAllocationOptimizationContext> { public PreAllocationOptimizationStage() { @@ -37,5 +39,8 @@ if (ConstantLoadOptimization.Options.LIROptConstantLoadOptimization.getValue()) { appendPhase(new ConstantLoadOptimization()); } + if (EnableSSIConstruction.getValue()) { + appendPhase(new SSIConstructionPhase()); + } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIConstructionPhase.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,119 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.ssi; + +import java.util.*; + +import jdk.internal.jvmci.code.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.lir.phases.*; +import com.oracle.graal.lir.ssa.*; + +public final class SSIConstructionPhase extends PreAllocationOptimizationPhase { + + @Override + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, LIRGeneratorTool lirGen) { + assert SSAUtils.verifySSAForm(lirGenRes.getLIR()); + LIR lir = lirGenRes.getLIR(); + new SSIBuilder(lir).build(lirGen); + } + + private static class SSIBuilder { + private final SSIBlockValueMapImpl valueMap; + private final LIR lir; + private final BitSet processed; + + private SSIBuilder(LIR lir) { + this.lir = lir; + valueMap = new SSIBlockValueMapImpl(lir.getControlFlowGraph()); + processed = new BitSet(lir.getControlFlowGraph().getBlocks().size()); + } + + private void build(LIRGeneratorTool lirGen) { + Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(lir.getControlFlowGraph().getBlocks()); + while (!worklist.isEmpty()) { + AbstractBlockBase<?> block = worklist.poll(); + if (!processed.get(block.getId())) { + try (Indent indent = Debug.logAndIndent("Try processing Block %s", block)) { + // check predecessors + boolean reschedule = false; + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + if (!processed.get(pred.getId()) && !isLoopBackEdge(pred, block)) { + Debug.log("Schedule predecessor: %s", pred); + worklist.addLast(pred); + reschedule = true; + } + } + if (reschedule) { + Debug.log("Reschedule block %s", block); + worklist.addLast(block); + } else { + processBlock(block); + } + } + } + } + valueMap.finish(lirGen); + } + + public void processBlock(AbstractBlockBase<?> block) { + assert !processed.get(block.getId()) : "Block already processed " + block; + try (Indent indent = Debug.logAndIndent("Process Block %s", block)) { + // track values + ValueConsumer useConsumer = (value, mode, flags) -> { + if (flags.contains(OperandFlag.UNINITIALIZED)) { + AbstractBlockBase<?> startBlock = lir.getControlFlowGraph().getStartBlock(); + Debug.log("Set definition of %s in block %s", value, startBlock); + valueMap.defineOperand(value, startBlock); + } else { + Debug.log("Access %s in block %s", value, block); + valueMap.accessOperand(value, block); + } + }; + ValueConsumer defConsumer = (value, mode, flags) -> { + Debug.log("Set definition of %s in block %s", value, block); + valueMap.defineOperand(value, block); + }; + for (LIRInstruction op : lir.getLIRforBlock(block)) { + // use + op.visitEachInput(useConsumer); + op.visitEachAlive(useConsumer); + op.visitEachState(useConsumer); + // def + op.visitEachTemp(defConsumer); + op.visitEachOutput(defConsumer); + } + processed.set(block.getId()); + } + } + + private static boolean isLoopBackEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) { + return from.isLoopEnd() && to.isLoopHeader() && from.getLoop().equals(to.getLoop()); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIUtils.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,113 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.ssi; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.LIRInstruction.*; +import com.oracle.graal.lir.StandardOp.*; +import com.oracle.graal.lir.ssa.SSAUtils.*; + +public final class SSIUtils { + + public static BlockEndOp outgoing(LIR lir, AbstractBlockBase<?> block) { + return (BlockEndOp) outgoingInst(lir, block); + } + + public static LIRInstruction outgoingInst(LIR lir, AbstractBlockBase<?> block) { + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + int index = instructions.size() - 1; + LIRInstruction op = instructions.get(index); + return op; + } + + public static LabelOp incoming(LIR lir, AbstractBlockBase<?> block) { + return (LabelOp) incomingInst(lir, block); + } + + private static LIRInstruction incomingInst(LIR lir, AbstractBlockBase<?> block) { + return lir.getLIRforBlock(block).get(0); + } + + public static void removeIncoming(LIR lir, AbstractBlockBase<?> block) { + incoming(lir, block).clearIncomingValues(); + } + + public static void removeOutgoing(LIR lir, AbstractBlockBase<?> block) { + outgoing(lir, block).clearOutgoingValues(); + } + + /** + * Visits each SIGMA/PHI value pair of an edge, i.e. the outgoing value from the predecessor and + * the incoming value to the merge block. + */ + public static void forEachValuePair(LIR lir, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock, PhiValueVisitor visitor) { + assert toBlock.getPredecessors().contains(fromBlock) : String.format("%s not in predecessor list: %s", fromBlock, toBlock.getPredecessors()); + assert fromBlock.getSuccessorCount() == 1 || toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s has %d successors and %s has %d predecessors", fromBlock, + fromBlock.getSuccessors(), toBlock, toBlock.getPredecessorCount()); + assert fromBlock.getSuccessors().contains(toBlock) : String.format("Predecessor block %s has wrong successor: %s, should contain: %s", fromBlock, fromBlock.getSuccessors(), toBlock); + + BlockEndOp blockEnd = outgoing(lir, fromBlock); + LabelOp label = incoming(lir, toBlock); + + assert label.getIncomingSize() == blockEnd.getOutgoingSize() : String.format("In/Out size mismatch: in=%d vs. out=%d, blocks %s vs. %s", label.getIncomingSize(), blockEnd.getOutgoingSize(), + toBlock, fromBlock); + + for (int i = 0; i < label.getIncomingSize(); i++) { + visitor.visit(label.getIncomingValue(i), blockEnd.getOutgoingValue(i)); + } + } + + public static void forEachRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) { + assert mode == OperandMode.DEF : "Wrong operand mode: " + mode; + assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label); + + if (!label.isPhiIn()) { + return; + } + int idx = indexOfValue(label, targetValue); + assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label); + + for (AbstractBlockBase<?> pred : block.getPredecessors()) { + BlockEndOp blockEnd = outgoing(lir, pred); + Value sourceValue = blockEnd.getOutgoingValue(idx); + valueConsumer.visitValue((LIRInstruction) blockEnd, sourceValue, null, null); + } + + } + + private static int indexOfValue(LabelOp label, Value value) { + for (int i = 0; i < label.getIncomingSize(); i++) { + if (label.getIncomingValue(i).equals(value)) { + return i; + } + } + return -1; + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/ssi/SSIVerifier.java Fri Jul 24 10:55:33 2015 +0200 @@ -0,0 +1,158 @@ +/* + * Copyright (c) 2015, 2015, 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.lir.ssi; + +import static jdk.internal.jvmci.code.ValueUtil.*; + +import java.util.*; + +import jdk.internal.jvmci.meta.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.LIRInstruction.OperandFlag; +import com.oracle.graal.lir.LIRInstruction.OperandMode; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.StandardOp.LabelOp; + +public class SSIVerifier { + + public static boolean verify(LIR lir) { + return new SSIVerifier(lir).verify(); + } + + private final LIR lir; + + private SSIVerifier(LIR lir) { + this.lir = lir; + } + + private boolean verify() { + try (Scope s = Debug.scope("SSIVerifier", lir)) { + for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { + doBlock(block); + } + } catch (Throwable e) { + throw Debug.handle(e); + } + return true; + } + + private void doBlock(AbstractBlockBase<?> block) { + for (AbstractBlockBase<?> succ : block.getSuccessors()) { + verifyEdge(block, succ); + } + verifyInstructions(block); + } + + private void verifyEdge(AbstractBlockBase<?> from, AbstractBlockBase<?> to) { + BlockEndOp out = SSIUtils.outgoing(lir, from); + LabelOp in = SSIUtils.incoming(lir, to); + int outgoingSize = out.getOutgoingSize(); + int incomingSize = in.getIncomingSize(); + assert outgoingSize == incomingSize : String.format("Outgoing size %d and incoming size %d do not match", outgoingSize, incomingSize); + + for (int i = 0; i < outgoingSize; i++) { + Value incomingValue = in.getIncomingValue(i); + Value outgoingValue = out.getOutgoingValue(i); + LIRKind inLIRKind = incomingValue.getLIRKind(); + LIRKind outLIRKind = outgoingValue.getLIRKind(); + assert LIRKind.verifyMoveKinds(inLIRKind, outLIRKind) || incomingValue.equals(Value.ILLEGAL) : String.format("Outgoing LIRKind %s (%s) an and incoming LIRKind %s (%s) do not match", + outgoingValue, outLIRKind, incomingValue, inLIRKind); + } + } + + private void verifyInstructions(AbstractBlockBase<?> block) { + List<LIRInstruction> instructions = lir.getLIRforBlock(block); + HashMap<Value, LIRInstruction> defined = new HashMap<>(); + + InstructionValueConsumer useConsumer = new InstructionValueConsumer() { + public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) { + if (checkUsage(value)) { + assert defined.containsKey(value) || flags.contains(OperandFlag.UNINITIALIZED) : String.format("Value %s is used by instruction %s in block %s but not defined.", value, + instruction, block); + } + } + }; + InstructionValueConsumer stateConsumer = new InstructionValueConsumer() { + public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) { + if (checkUsage(value)) { + /* + * TODO (je): There are undefined stack values used for locks. Ignore them for + * the time being. + */ + assert defined.containsKey(value) || isVirtualStackSlot(value) : String.format("Value %s is used in state of instruction %s in block %s but not defined.", value, instruction, + block); + } + } + }; + + InstructionValueConsumer defConsumer = new InstructionValueConsumer() { + public void visitValue(LIRInstruction instruction, Value value, OperandMode mode, EnumSet<OperandFlag> flags) { + if (trackDefinition(value)) { + assert !defined.containsKey(value) : String.format("Value %s is redefined by instruction %s in block %s but already defined by %s.", value, instruction, block, defined.get(value)); + defined.put(value, instruction); + } + } + }; + + for (LIRInstruction op : instructions) { + op.visitEachAlive(useConsumer); + op.visitEachInput(useConsumer); + op.visitEachState(stateConsumer); + + op.visitEachTemp(defConsumer); + op.visitEachOutput(defConsumer); + } + } + + private static boolean trackDefinition(Value value) { + if (isRegister(value)) { + // registers can be redefined + return false; + } + if (value.equals(Value.ILLEGAL)) { + // Don't care about illegal values + return false; + } + return true; + } + + private static boolean checkUsage(Value value) { + if (value instanceof Constant) { + // Constants do not need to be defined + return false; + } + if (isRegister(value)) { + // Assume fixed registers are correct + return false; + } + if (value.equals(Value.ILLEGAL)) { + // Don't care about illegal values + return false; + } + return true; + } +}
--- a/mx.graal/suite.py Fri Jul 24 16:20:56 2015 +0200 +++ b/mx.graal/suite.py Fri Jul 24 10:55:33 2015 +0200 @@ -568,10 +568,8 @@ "subDir" : "graal", "sourceDirs" : ["src"], "dependencies" : [ - "com.oracle.graal.debug", "com.oracle.graal.nodeinfo", "com.oracle.graal.compiler.common", - "com.oracle.graal.debug", "com.oracle.graal.api.collections", "com.oracle.graal.api.runtime", ], @@ -665,7 +663,6 @@ "sourceDirs" : ["src"], "dependencies" : [ "com.oracle.graal.compiler.common", - "com.oracle.graal.debug", "com.oracle.graal.asm", ], "checkstyle" : "com.oracle.graal.graph", @@ -992,10 +989,8 @@ "subDir" : "graal", "sourceDirs" : ["src"], "dependencies" : [ - "jdk.internal.jvmci.debug", - "jdk.internal.jvmci.options", "jdk.internal.jvmci.common", - "jdk.internal.jvmci.code", + "com.oracle.graal.debug", ], "annotationProcessors" : ["jdk.internal.jvmci.options.processor"], "checkstyle" : "com.oracle.graal.graph",