1/* 2 * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23package org.graalvm.compiler.lir.alloc.trace.lsra; 24 25import static jdk.vm.ci.code.ValueUtil.isRegister; 26import static org.graalvm.compiler.lir.LIRValueUtil.asConstant; 27import static org.graalvm.compiler.lir.LIRValueUtil.asVariable; 28import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue; 29import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 30import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot; 31 32import java.util.ArrayList; 33 34import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig; 35import org.graalvm.compiler.core.common.alloc.Trace; 36import org.graalvm.compiler.core.common.alloc.TraceBuilderResult; 37import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 38import org.graalvm.compiler.debug.Assertions; 39import org.graalvm.compiler.debug.CounterKey; 40import org.graalvm.compiler.debug.DebugContext; 41import org.graalvm.compiler.debug.Indent; 42import org.graalvm.compiler.lir.LIR; 43import org.graalvm.compiler.lir.LIRInstruction; 44import org.graalvm.compiler.lir.StandardOp; 45import org.graalvm.compiler.lir.StandardOp.JumpOp; 46import org.graalvm.compiler.lir.StandardOp.LabelOp; 47import org.graalvm.compiler.lir.alloc.trace.GlobalLivenessInfo; 48import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan; 49import org.graalvm.compiler.lir.gen.LIRGenerationResult; 50import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory; 51import org.graalvm.compiler.lir.ssa.SSAUtil; 52 53import jdk.vm.ci.code.TargetDescription; 54import jdk.vm.ci.meta.Value; 55 56/** 57 * Phase 6: resolve data flow 58 * 59 * Insert moves at edges between blocks if intervals have been split. 60 */ 61final class TraceLinearScanResolveDataFlowPhase extends TraceLinearScanAllocationPhase { 62 63 @Override 64 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, MoveFactory spillMoveFactory, RegisterAllocationConfig registerAllocationConfig, 65 TraceBuilderResult traceBuilderResult, TraceLinearScan allocator) { 66 new Resolver(allocator, traceBuilderResult).resolveDataFlow(trace, allocator.sortedBlocks()); 67 } 68 69 private static final class Resolver { 70 private final TraceLinearScan allocator; 71 private final TraceBuilderResult traceBuilderResult; 72 private final DebugContext debug; 73 74 private Resolver(TraceLinearScan allocator, TraceBuilderResult traceBuilderResult) { 75 this.allocator = allocator; 76 this.traceBuilderResult = traceBuilderResult; 77 this.debug = allocator.getDebug(); 78 } 79 80 private void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) { 81 if (fromBlock.getSuccessorCount() <= 1) { 82 if (debug.isLogEnabled()) { 83 debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); 84 } 85 86 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock); 87 LIRInstruction instr = instructions.get(instructions.size() - 1); 88 if (instr instanceof StandardOp.JumpOp) { 89 // insert moves before branch 90 moveResolver.setInsertPosition(instructions, instructions.size() - 1); 91 } else { 92 moveResolver.setInsertPosition(instructions, instructions.size()); 93 } 94 95 } else { 96 if (debug.isLogEnabled()) { 97 debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId()); 98 } 99 100 if (Assertions.detailedAssertionsEnabled(allocator.getOptions())) { 101 assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; 102 103 /* 104 * Because the number of predecessor edges matches the number of successor 105 * edges, blocks which are reached by switch statements may have be more than 106 * one predecessor but it will be guaranteed that all predecessors will be the 107 * same. 108 */ 109 for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) { 110 assert fromBlock == predecessor : "all critical edges must be broken"; 111 } 112 } 113 114 moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1); 115 } 116 } 117 118 /** 119 * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals 120 * that have been split. 121 */ 122 @SuppressWarnings("try") 123 private void resolveDataFlow(Trace currentTrace, AbstractBlockBase<?>[] blocks) { 124 if (blocks.length < 2) { 125 // no resolution necessary 126 return; 127 } 128 try (Indent indent = debug.logAndIndent("resolve data flow")) { 129 130 TraceLocalMoveResolver moveResolver = allocator.createMoveResolver(); 131 AbstractBlockBase<?> toBlock = null; 132 for (int i = 0; i < blocks.length - 1; i++) { 133 AbstractBlockBase<?> fromBlock = blocks[i]; 134 toBlock = blocks[i + 1]; 135 assert containedInTrace(currentTrace, fromBlock) : "Not in Trace: " + fromBlock; 136 assert containedInTrace(currentTrace, toBlock) : "Not in Trace: " + toBlock; 137 resolveCollectMappings(fromBlock, toBlock, moveResolver); 138 } 139 assert blocks[blocks.length - 1].equals(toBlock); 140 if (toBlock.isLoopEnd()) { 141 assert toBlock.getSuccessorCount() == 1; 142 AbstractBlockBase<?> loopHeader = toBlock.getSuccessors()[0]; 143 if (containedInTrace(currentTrace, loopHeader)) { 144 resolveCollectMappings(toBlock, loopHeader, moveResolver); 145 } 146 } 147 148 } 149 } 150 151 @SuppressWarnings("try") 152 private void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) { 153 try (Indent indent0 = debug.logAndIndent("Edge %s -> %s", fromBlock, toBlock)) { 154 // collect all intervals that have been split between 155 // fromBlock and toBlock 156 int toId = allocator.getFirstLirInstructionId(toBlock); 157 int fromId = allocator.getLastLirInstructionId(fromBlock); 158 assert fromId >= 0; 159 LIR lir = allocator.getLIR(); 160 if (SSAUtil.isMerge(toBlock)) { 161 JumpOp blockEnd = SSAUtil.phiOut(lir, fromBlock); 162 LabelOp label = SSAUtil.phiIn(lir, toBlock); 163 for (int i = 0; i < label.getPhiSize(); i++) { 164 addMapping(blockEnd.getOutgoingValue(i), label.getIncomingValue(i), fromId, toId, moveResolver); 165 } 166 } 167 GlobalLivenessInfo livenessInfo = allocator.getGlobalLivenessInfo(); 168 int[] locTo = livenessInfo.getBlockIn(toBlock); 169 for (int i = 0; i < locTo.length; i++) { 170 TraceInterval interval = allocator.intervalFor(locTo[i]); 171 addMapping(interval, interval, fromId, toId, moveResolver); 172 } 173 174 if (moveResolver.hasMappings()) { 175 resolveFindInsertPos(fromBlock, toBlock, moveResolver); 176 moveResolver.resolveAndAppendMoves(); 177 } 178 } 179 } 180 181 private boolean containedInTrace(Trace currentTrace, AbstractBlockBase<?> block) { 182 return currentTrace.getId() == traceBuilderResult.getTraceForBlock(block).getId(); 183 } 184 185 private static final CounterKey numResolutionMoves = DebugContext.counter("TraceRA[numTraceLSRAResolutionMoves]"); 186 private static final CounterKey numStackToStackMoves = DebugContext.counter("TraceRA[numTraceLSRAStackToStackMoves]"); 187 188 private void addMapping(Value phiFrom, Value phiTo, int fromId, int toId, TraceLocalMoveResolver moveResolver) { 189 assert !isRegister(phiFrom) : "Out is a register: " + phiFrom; 190 assert !isRegister(phiTo) : "In is a register: " + phiTo; 191 assert !Value.ILLEGAL.equals(phiTo) : "The value not needed in this branch? " + phiFrom; 192 if (isVirtualStackSlot(phiTo) && isVirtualStackSlot(phiFrom) && phiTo.equals(phiFrom)) { 193 // no need to handle virtual stack slots 194 return; 195 } 196 TraceInterval toParent = allocator.intervalFor(asVariable(phiTo)); 197 if (isConstantValue(phiFrom)) { 198 numResolutionMoves.increment(debug); 199 TraceInterval toInterval = allocator.splitChildAtOpId(toParent, toId, LIRInstruction.OperandMode.DEF); 200 moveResolver.addMapping(asConstant(phiFrom), toInterval); 201 } else { 202 addMapping(allocator.intervalFor(asVariable(phiFrom)), toParent, fromId, toId, moveResolver); 203 } 204 } 205 206 private void addMapping(TraceInterval fromParent, TraceInterval toParent, int fromId, int toId, TraceLocalMoveResolver moveResolver) { 207 TraceInterval fromInterval = allocator.splitChildAtOpId(fromParent, fromId, LIRInstruction.OperandMode.USE); 208 TraceInterval toInterval = toParent.getSplitChildAtOpIdOrNull(toId, LIRInstruction.OperandMode.DEF); 209 if (toInterval == null) { 210 // not alive 211 return; 212 } 213 if (fromInterval != toInterval) { 214 numResolutionMoves.increment(debug); 215 if (isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location())) { 216 numStackToStackMoves.increment(debug); 217 } 218 moveResolver.addMapping(fromInterval, toInterval); 219 } 220 } 221 } 222 223} 224