Mercurial > hg > graal-compiler
changeset 22555:72b2950d7e30
TraceRA: remove LinearScanResolveDataFlowPhase.
author | Josef Eisl <josef.eisl@jku.at> |
---|---|
date | Mon, 31 Aug 2015 13:55:03 +0200 |
parents | 05d3ecaa9d69 |
children | 576594eb9fb0 |
files | graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanResolveDataFlowPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java |
diffstat | 4 files changed, 156 insertions(+), 223 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/LinearScanResolveDataFlowPhase.java Mon Aug 31 13:50:09 2015 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,208 +0,0 @@ -/* - * 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.trace; - -import static com.oracle.graal.compiler.common.GraalOptions.*; - -import java.util.*; - -import jdk.internal.jvmci.code.*; -import com.oracle.graal.debug.*; - -import com.oracle.graal.compiler.common.alloc.*; -import com.oracle.graal.compiler.common.cfg.*; -import com.oracle.graal.lir.*; -import com.oracle.graal.lir.gen.*; -import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; -import com.oracle.graal.lir.phases.*; - -/** - * Phase 6: resolve data flow - * - * Insert moves at edges between blocks if intervals have been split. - */ -public class LinearScanResolveDataFlowPhase extends AllocationPhase { - - protected final TraceLinearScan allocator; - - protected LinearScanResolveDataFlowPhase(TraceLinearScan allocator) { - this.allocator = allocator; - } - - @Override - protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, - RegisterAllocationConfig registerAllocationConfig) { - resolveDataFlow(); - } - - protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { - assert moveResolver.checkEmpty(); - assert midBlock == null || - (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals( - toBlock)); - - int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); - int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; - int numOperands = allocator.operandSize(); - BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn; - - // visit all variables for which the liveAtEdge bit is set - for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { - assert operandNum < numOperands : "live information set for not exisiting interval"; - assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; - - Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); - Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); - - if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { - // need to insert move instruction - moveResolver.addMapping(fromInterval, toInterval); - } - } - } - - void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) { - if (fromBlock.getSuccessorCount() <= 1) { - if (Debug.isLogEnabled()) { - Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); - } - - List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock); - LIRInstruction instr = instructions.get(instructions.size() - 1); - if (instr instanceof StandardOp.JumpOp) { - // insert moves before branch - moveResolver.setInsertPosition(instructions, instructions.size() - 1); - } else { - moveResolver.setInsertPosition(instructions, instructions.size()); - } - - } else { - if (Debug.isLogEnabled()) { - Debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId()); - } - - if (DetailedAsserts.getValue()) { - assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; - - /* - * Because the number of predecessor edges matches the number of successor edges, - * blocks which are reached by switch statements may have be more than one - * predecessor but it will be guaranteed that all predecessors will be the same. - */ - for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) { - assert fromBlock == predecessor : "all critical edges must be broken"; - } - } - - moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1); - } - } - - /** - * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that - * have been split. - */ - protected void resolveDataFlow() { - try (Indent indent = Debug.logAndIndent("resolve data flow")) { - - MoveResolver moveResolver = allocator.createMoveResolver(); - BitSet blockCompleted = new BitSet(allocator.blockCount()); - - optimizeEmptyBlocks(moveResolver, blockCompleted); - - resolveDataFlow0(moveResolver, blockCompleted); - - } - } - - protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { - for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { - - // check if block has only one predecessor and only one successor - if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) { - List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); - assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label"; - assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump"; - - // check if block is empty (only label and branch) - if (instructions.size() == 2) { - AbstractBlockBase<?> pred = block.getPredecessors().iterator().next(); - AbstractBlockBase<?> sux = block.getSuccessors().iterator().next(); - - // prevent optimization of two consecutive blocks - if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) { - if (Debug.isLogEnabled()) { - Debug.log(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.getId(), pred.getId(), sux.getId()); - } - - blockCompleted.set(block.getLinearScanNumber()); - - /* - * Directly resolve between pred and sux (without looking at the empty block - * between). - */ - resolveCollectMappings(pred, sux, block, moveResolver); - if (moveResolver.hasMappings()) { - moveResolver.setInsertPosition(instructions, 1); - moveResolver.resolveAndAppendMoves(); - } - } - } - } - } - } - - protected void resolveDataFlow0(MoveResolver moveResolver, BitSet blockCompleted) { - BitSet alreadyResolved = new BitSet(allocator.blockCount()); - for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) { - if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { - alreadyResolved.clear(); - alreadyResolved.or(blockCompleted); - - for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { - - /* - * Check for duplicate edges between the same blocks (can happen with switch - * blocks). - */ - if (!alreadyResolved.get(toBlock.getLinearScanNumber())) { - if (Debug.isLogEnabled()) { - Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId()); - } - - alreadyResolved.set(toBlock.getLinearScanNumber()); - - // collect all intervals that have been split between - // fromBlock and toBlock - resolveCollectMappings(fromBlock, toBlock, null, moveResolver); - if (moveResolver.hasMappings()) { - resolveFindInsertPos(fromBlock, toBlock, moveResolver); - moveResolver.resolveAndAppendMoves(); - } - } - } - } - } - } - -}
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Mon Aug 31 13:50:09 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScan.java Mon Aug 31 13:55:03 2015 +0200 @@ -636,7 +636,7 @@ createOptimizeSpillPositionPhase().apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); } // resolve intra-trace data-flow - LinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase(); + TraceLinearScanResolveDataFlowPhase dataFlowPhase = createResolveDataFlowPhase(); dataFlowPhase.apply(target, lirGenRes, codeEmittingOrder, linearScanOrder, context, false); Debug.dump(TraceRegisterAllocationPhase.TRACE_DUMP_LEVEL, sortedBlocks(), "%s", dataFlowPhase.getName()); @@ -659,7 +659,7 @@ return new TraceLinearScanLifetimeAnalysisPhase(this, traceBuilderResult); } - protected LinearScanResolveDataFlowPhase createResolveDataFlowPhase() { + protected TraceLinearScanResolveDataFlowPhase createResolveDataFlowPhase() { return new TraceLinearScanResolveDataFlowPhase(this); }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java Mon Aug 31 13:50:09 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanAssignLocationsPhase.java Mon Aug 31 13:55:03 2015 +0200 @@ -42,7 +42,6 @@ import com.oracle.graal.lir.StandardOp.BlockEndOp; import com.oracle.graal.lir.StandardOp.MoveOp; import com.oracle.graal.lir.StandardOp.ValueMoveOp; -import com.oracle.graal.lir.alloc.lsra.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.lir.gen.LIRGeneratorTool.SpillMoveFactory; import com.oracle.graal.lir.phases.*; @@ -110,7 +109,7 @@ if (isIllegal(interval.location()) && interval.canMaterialize()) { assert mode != OperandMode.DEF; - return interval.getMaterializedValue(); + return new ConstantValue(interval.kind(), interval.getMaterializedValue()); } return interval.location(); } @@ -135,7 +134,7 @@ * is a branch, spill moves are inserted before this branch and so the wrong operand * would be returned (spill moves at block boundaries are not considered in the live * ranges of intervals). - * + * * Solution: use the first opId of the branch target block instead. */ final LIRInstruction instr = allocator.getLIR().getLIRforBlock(block).get(allocator.getLIR().getLIRforBlock(block).size() - 1); @@ -153,7 +152,7 @@ * cause an assert on failure. */ Value result = colorLirOperand(op, (Variable) operand, mode); - assert !allocator.hasCall(tempOpId) || isStackSlotValue(result) || isConstant(result) || !allocator.isCallerSave(result) : "cannot have caller-save register operands at calls"; + assert !allocator.hasCall(tempOpId) || isStackSlotValue(result) || isConstantValue(result) || !allocator.isCallerSave(result) : "cannot have caller-save register operands at calls"; return result; }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Mon Aug 31 13:50:09 2015 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/alloc/trace/TraceLinearScanResolveDataFlowPhase.java Mon Aug 31 13:55:03 2015 +0200 @@ -22,38 +22,177 @@ */ package com.oracle.graal.lir.alloc.trace; +import static com.oracle.graal.compiler.common.GraalOptions.*; import static com.oracle.graal.lir.LIRValueUtil.*; import static jdk.internal.jvmci.code.ValueUtil.*; import java.util.*; +import jdk.internal.jvmci.code.*; import jdk.internal.jvmci.meta.*; +import com.oracle.graal.compiler.common.alloc.*; import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.debug.*; import com.oracle.graal.lir.*; +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.SSAUtil.PhiValueVisitor; import com.oracle.graal.lir.ssi.*; -public class TraceLinearScanResolveDataFlowPhase extends LinearScanResolveDataFlowPhase { +/** + * Phase 6: resolve data flow + * + * Insert moves at edges between blocks if intervals have been split. + */ +public class TraceLinearScanResolveDataFlowPhase extends AllocationPhase { - private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); - private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + protected final TraceLinearScan allocator; - public TraceLinearScanResolveDataFlowPhase(TraceLinearScan allocator) { - super(allocator); + protected TraceLinearScanResolveDataFlowPhase(TraceLinearScan allocator) { + this.allocator = allocator; } @Override - protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { - // do not optimize + protected <B extends AbstractBlockBase<B>> void run(TargetDescription target, LIRGenerationResult lirGenRes, List<B> codeEmittingOrder, List<B> linearScanOrder, SpillMoveFactory spillMoveFactory, + RegisterAllocationConfig registerAllocationConfig) { + resolveDataFlow(); + } + + protected void resolveCollectMappings0(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { + assert moveResolver.checkEmpty(); + assert midBlock == null || + (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals( + toBlock)); + + int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); + int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; + int numOperands = allocator.operandSize(); + BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn; + + // visit all variables for which the liveAtEdge bit is set + for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { + assert operandNum < numOperands : "live information set for not exisiting interval"; + assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; + + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); + + if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { + // need to insert move instruction + moveResolver.addMapping(fromInterval, toInterval); + } + } } - @Override + void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) { + if (fromBlock.getSuccessorCount() <= 1) { + if (Debug.isLogEnabled()) { + Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); + } + + List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock); + LIRInstruction instr = instructions.get(instructions.size() - 1); + if (instr instanceof StandardOp.JumpOp) { + // insert moves before branch + moveResolver.setInsertPosition(instructions, instructions.size() - 1); + } else { + moveResolver.setInsertPosition(instructions, instructions.size()); + } + + } else { + if (Debug.isLogEnabled()) { + Debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId()); + } + + if (DetailedAsserts.getValue()) { + assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; + + /* + * Because the number of predecessor edges matches the number of successor edges, + * blocks which are reached by switch statements may have be more than one + * predecessor but it will be guaranteed that all predecessors will be the same. + */ + for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) { + assert fromBlock == predecessor : "all critical edges must be broken"; + } + } + + moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1); + } + } + + /** + * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that + * have been split. + */ + protected void resolveDataFlow() { + try (Indent indent = Debug.logAndIndent("resolve data flow")) { + + MoveResolver moveResolver = allocator.createMoveResolver(); + BitSet blockCompleted = new BitSet(allocator.blockCount()); + + BitSet alreadyResolved = new BitSet(allocator.blockCount()); + for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) { + if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { + alreadyResolved.clear(); + alreadyResolved.or(blockCompleted); + + for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { + + /* + * Check for duplicate edges between the same blocks (can happen with switch + * blocks). + */ + if (!alreadyResolved.get(toBlock.getLinearScanNumber())) { + if (Debug.isLogEnabled()) { + Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId()); + } + + alreadyResolved.set(toBlock.getLinearScanNumber()); + + // collect all intervals that have been split between + // fromBlock and toBlock + resolveCollectMappings(fromBlock, toBlock, null, moveResolver); + if (moveResolver.hasMappings()) { + resolveFindInsertPos(fromBlock, toBlock, moveResolver); + moveResolver.resolveAndAppendMoves(); + } + } + } + } + } + + } + } + 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); + assert moveResolver.checkEmpty(); + assert midBlock == null || + (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors().get(0).equals(fromBlock) && midBlock.getSuccessors().get(0).equals( + toBlock)); + + int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); + int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; + int numOperands = allocator.operandSize(); + BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn; + + // visit all variables for which the liveAtEdge bit is set + for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { + assert operandNum < numOperands : "live information set for not exisiting interval"; + assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; + + Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); + Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); + + if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { + // need to insert move instruction + moveResolver.addMapping(fromInterval, toInterval); + } + } SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MyPhiValueVisitor(moveResolver, toBlock, fromBlock)); } @@ -63,6 +202,9 @@ return allocator.sortedBlocks().contains(block); } + private static final DebugMetric numSSIResolutionMoves = Debug.metric("SSI LSRA[numSSIResolutionMoves]"); + private static final DebugMetric numStackToStackMoves = Debug.metric("SSI LSRA[numStackToStackMoves]"); + private class MyPhiValueVisitor implements PhiValueVisitor { final MoveResolver moveResolver; final int toId;