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 */ 23 package org.graalvm.compiler.lir.alloc.trace.lsra; 24 25 import static org.graalvm.compiler.core.common.GraalOptions.DetailedAsserts; 26 import static org.graalvm.compiler.lir.LIRValueUtil.asConstant; 27 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue; 28 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue; 29 import static org.graalvm.compiler.lir.LIRValueUtil.isVirtualStackSlot; 30 import static jdk.vm.ci.code.ValueUtil.isRegister; 31 32 import java.util.List; 33 34 import org.graalvm.compiler.core.common.alloc.Trace; 35 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult; 36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 37 import org.graalvm.compiler.debug.Debug; 38 import org.graalvm.compiler.debug.DebugCounter; 39 import org.graalvm.compiler.debug.Indent; 40 import org.graalvm.compiler.lir.LIRInstruction; 41 import org.graalvm.compiler.lir.StandardOp; 42 import org.graalvm.compiler.lir.alloc.trace.lsra.TraceLinearScanPhase.TraceLinearScan; 43 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 44 import org.graalvm.compiler.lir.ssa.SSAUtil.PhiValueVisitor; 45 import org.graalvm.compiler.lir.ssi.SSIUtil; 46 47 import jdk.vm.ci.code.TargetDescription; 48 import jdk.vm.ci.meta.Value; 49 50 /** 51 * Phase 6: resolve data flow 52 * 53 * Insert moves at edges between blocks if intervals have been split. 54 */ 55 final class TraceLinearScanResolveDataFlowPhase extends TraceLinearScanAllocationPhase { 56 57 @Override 58 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, Trace trace, TraceLinearScanAllocationContext context) { 59 TraceBuilderResult traceBuilderResult = context.resultTraces; 60 TraceLinearScan allocator = context.allocator; 61 new Resolver(allocator, traceBuilderResult).resolveDataFlow(trace, allocator.sortedBlocks()); 62 } 63 64 private static final class Resolver { 65 private final TraceLinearScan allocator; 66 private final TraceBuilderResult traceBuilderResult; 67 68 private Resolver(TraceLinearScan allocator, TraceBuilderResult traceBuilderResult) { 69 this.allocator = allocator; 70 this.traceBuilderResult = traceBuilderResult; 71 } 72 73 private void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) { 74 if (fromBlock.getSuccessorCount() <= 1) { 75 if (Debug.isLogEnabled()) { 76 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); 77 } 78 79 List<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock); 80 LIRInstruction instr = instructions.get(instructions.size() - 1); 81 if (instr instanceof StandardOp.JumpOp) { 82 // insert moves before branch 83 moveResolver.setInsertPosition(instructions, instructions.size() - 1); 84 } else { 85 moveResolver.setInsertPosition(instructions, instructions.size()); 86 } 87 88 } else { 89 if (Debug.isLogEnabled()) { 90 Debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId()); 91 } 92 93 if (DetailedAsserts.getValue()) { 94 assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; 95 96 /* 97 * Because the number of predecessor edges matches the number of successor 98 * edges, blocks which are reached by switch statements may have be more than 99 * one predecessor but it will be guaranteed that all predecessors will be the 100 * same. 101 */ 102 for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) { 103 assert fromBlock == predecessor : "all critical edges must be broken"; 104 } 105 } 106 107 moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1); 108 } 109 } 110 111 /** 112 * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals 113 * that have been split. 114 */ 115 @SuppressWarnings("try") 116 private void resolveDataFlow(Trace currentTrace, AbstractBlockBase<?>[] blocks) { 117 if (blocks.length < 2) { 118 // no resolution necessary 119 return; 120 } 121 try (Indent indent = Debug.logAndIndent("resolve data flow")) { 122 123 TraceLocalMoveResolver moveResolver = allocator.createMoveResolver(); 124 AbstractBlockBase<?> toBlock = null; 125 for (int i = 0; i < blocks.length - 1; i++) { 126 AbstractBlockBase<?> fromBlock = blocks[i]; 127 toBlock = blocks[i + 1]; 128 assert containedInTrace(currentTrace, fromBlock) : "Not in Trace: " + fromBlock; 129 assert containedInTrace(currentTrace, toBlock) : "Not in Trace: " + toBlock; 130 resolveCollectMappings(fromBlock, toBlock, moveResolver); 131 } 132 assert blocks[blocks.length - 1].equals(toBlock); 133 if (toBlock.isLoopEnd()) { 134 assert toBlock.getSuccessorCount() == 1; 135 AbstractBlockBase<?> loopHeader = toBlock.getSuccessors()[0]; 136 if (containedInTrace(currentTrace, loopHeader)) { 137 resolveCollectMappings(toBlock, loopHeader, moveResolver); 138 } 139 } 140 141 } 142 } 143 144 @SuppressWarnings("try") 145 private void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, TraceLocalMoveResolver moveResolver) { 146 try (Indent indent0 = Debug.logAndIndent("Edge %s -> %s", fromBlock, toBlock)) { 147 // collect all intervals that have been split between 148 // fromBlock and toBlock 149 SSIUtil.forEachValuePair(allocator.getLIR(), toBlock, fromBlock, new MappingCollector(moveResolver, toBlock, fromBlock)); 150 if (moveResolver.hasMappings()) { 151 resolveFindInsertPos(fromBlock, toBlock, moveResolver); 152 moveResolver.resolveAndAppendMoves(); 153 } 154 } 155 } 156 157 private boolean containedInTrace(Trace currentTrace, AbstractBlockBase<?> block) { 158 return currentTrace.getId() == traceBuilderResult.getTraceForBlock(block).getId(); 159 } 160 161 private static final DebugCounter numSSIResolutionMoves = Debug.counter("SSI LSRA[numSSIResolutionMoves]"); 162 private static final DebugCounter numStackToStackMoves = Debug.counter("SSI LSRA[numStackToStackMoves]"); 163 164 private class MappingCollector implements PhiValueVisitor { 165 final TraceLocalMoveResolver moveResolver; 166 final int toId; 167 final int fromId; 168 169 MappingCollector(TraceLocalMoveResolver moveResolver, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> fromBlock) { 170 this.moveResolver = moveResolver; 171 toId = allocator.getFirstLirInstructionId(toBlock); 172 fromId = allocator.getLastLirInstructionId(fromBlock); 173 assert fromId >= 0; 174 } 175 176 @Override 177 public void visit(Value phiIn, Value phiOut) { 178 assert !isRegister(phiOut) : "Out is a register: " + phiOut; 179 assert !isRegister(phiIn) : "In is a register: " + phiIn; 180 if (Value.ILLEGAL.equals(phiIn)) { 181 // The value not needed in this branch. 182 return; 183 } 184 if (isVirtualStackSlot(phiIn) && isVirtualStackSlot(phiOut) && phiIn.equals(phiOut)) { 185 // no need to handle virtual stack slots 186 return; 187 } 188 TraceInterval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiIn), toId, LIRInstruction.OperandMode.DEF); 189 if (isConstantValue(phiOut)) { 190 numSSIResolutionMoves.increment(); 191 moveResolver.addMapping(asConstant(phiOut), toInterval); 192 } else { 193 TraceInterval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(phiOut), fromId, LIRInstruction.OperandMode.DEF); 194 if (fromInterval != toInterval) { 195 numSSIResolutionMoves.increment(); 196 if (!(isStackSlotValue(toInterval.location()) && isStackSlotValue(fromInterval.location()))) { 197 moveResolver.addMapping(fromInterval, toInterval); 198 } else { 199 numStackToStackMoves.increment(); 200 moveResolver.addMapping(fromInterval, toInterval); 201 } 202 } 203 } 204 } 205 } 206 } 207 208 }