1 /* 2 * Copyright (c) 2015, 2015, 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.lsra; 24 25 import java.util.ArrayList; 26 import java.util.BitSet; 27 28 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 29 import org.graalvm.compiler.debug.Debug; 30 import org.graalvm.compiler.debug.Indent; 31 import org.graalvm.compiler.lir.LIRInstruction; 32 import org.graalvm.compiler.lir.StandardOp; 33 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 34 import org.graalvm.compiler.lir.phases.AllocationPhase; 35 36 import jdk.vm.ci.code.TargetDescription; 37 38 /** 39 * Phase 6: resolve data flow 40 * 41 * Insert moves at edges between blocks if intervals have been split. 42 */ 43 public class LinearScanResolveDataFlowPhase extends AllocationPhase { 44 45 protected final LinearScan allocator; 46 47 protected LinearScanResolveDataFlowPhase(LinearScan allocator) { 48 this.allocator = allocator; 49 } 50 51 @Override 52 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { 53 resolveDataFlow(); 54 allocator.printIntervals("After resolve data flow"); 55 } 56 57 protected void resolveCollectMappings(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, AbstractBlockBase<?> midBlock, MoveResolver moveResolver) { 58 assert moveResolver.checkEmpty(); 59 assert midBlock == null || 60 (midBlock.getPredecessorCount() == 1 && midBlock.getSuccessorCount() == 1 && midBlock.getPredecessors()[0].equals(fromBlock) && midBlock.getSuccessors()[0].equals( 61 toBlock)); 62 63 int toBlockFirstInstructionId = allocator.getFirstLirInstructionId(toBlock); 64 int fromBlockLastInstructionId = allocator.getLastLirInstructionId(fromBlock) + 1; 65 int numOperands = allocator.operandSize(); 66 BitSet liveAtEdge = allocator.getBlockData(toBlock).liveIn; 67 68 // visit all variables for which the liveAtEdge bit is set 69 for (int operandNum = liveAtEdge.nextSetBit(0); operandNum >= 0; operandNum = liveAtEdge.nextSetBit(operandNum + 1)) { 70 assert operandNum < numOperands : "live information set for not exisiting interval"; 71 assert allocator.getBlockData(fromBlock).liveOut.get(operandNum) && allocator.getBlockData(toBlock).liveIn.get(operandNum) : "interval not live at this edge"; 72 73 Interval fromInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), fromBlockLastInstructionId, LIRInstruction.OperandMode.DEF); 74 Interval toInterval = allocator.splitChildAtOpId(allocator.intervalFor(operandNum), toBlockFirstInstructionId, LIRInstruction.OperandMode.DEF); 75 76 if (fromInterval != toInterval && !fromInterval.location().equals(toInterval.location())) { 77 // need to insert move instruction 78 moveResolver.addMapping(fromInterval, toInterval); 79 } 80 } 81 } 82 83 void resolveFindInsertPos(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock, MoveResolver moveResolver) { 84 if (fromBlock.getSuccessorCount() <= 1) { 85 if (Debug.isLogEnabled()) { 86 Debug.log("inserting moves at end of fromBlock B%d", fromBlock.getId()); 87 } 88 89 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(fromBlock); 90 LIRInstruction instr = instructions.get(instructions.size() - 1); 91 if (instr instanceof StandardOp.JumpOp) { 92 // insert moves before branch 93 moveResolver.setInsertPosition(instructions, instructions.size() - 1); 94 } else { 95 moveResolver.setInsertPosition(instructions, instructions.size()); 96 } 97 98 } else { 99 if (Debug.isLogEnabled()) { 100 Debug.log("inserting moves at beginning of toBlock B%d", toBlock.getId()); 101 } 102 103 if (allocator.detailedAsserts) { 104 assert allocator.getLIR().getLIRforBlock(fromBlock).get(0) instanceof StandardOp.LabelOp : "block does not start with a label"; 105 106 /* 107 * Because the number of predecessor edges matches the number of successor edges, 108 * blocks which are reached by switch statements may have be more than one 109 * predecessor but it will be guaranteed that all predecessors will be the same. 110 */ 111 for (AbstractBlockBase<?> predecessor : toBlock.getPredecessors()) { 112 assert fromBlock == predecessor : "all critical edges must be broken"; 113 } 114 } 115 116 moveResolver.setInsertPosition(allocator.getLIR().getLIRforBlock(toBlock), 1); 117 } 118 } 119 120 /** 121 * Inserts necessary moves (spilling or reloading) at edges between blocks for intervals that 122 * have been split. 123 */ 124 @SuppressWarnings("try") 125 protected void resolveDataFlow() { 126 try (Indent indent = Debug.logAndIndent("resolve data flow")) { 127 128 MoveResolver moveResolver = allocator.createMoveResolver(); 129 BitSet blockCompleted = new BitSet(allocator.blockCount()); 130 131 optimizeEmptyBlocks(moveResolver, blockCompleted); 132 133 resolveDataFlow0(moveResolver, blockCompleted); 134 135 } 136 } 137 138 protected void optimizeEmptyBlocks(MoveResolver moveResolver, BitSet blockCompleted) { 139 for (AbstractBlockBase<?> block : allocator.sortedBlocks()) { 140 141 // check if block has only one predecessor and only one successor 142 if (block.getPredecessorCount() == 1 && block.getSuccessorCount() == 1) { 143 ArrayList<LIRInstruction> instructions = allocator.getLIR().getLIRforBlock(block); 144 assert instructions.get(0) instanceof StandardOp.LabelOp : "block must start with label"; 145 assert instructions.get(instructions.size() - 1) instanceof StandardOp.JumpOp : "block with successor must end with unconditional jump"; 146 147 // check if block is empty (only label and branch) 148 if (instructions.size() == 2) { 149 AbstractBlockBase<?> pred = block.getPredecessors()[0]; 150 AbstractBlockBase<?> sux = block.getSuccessors()[0]; 151 152 // prevent optimization of two consecutive blocks 153 if (!blockCompleted.get(pred.getLinearScanNumber()) && !blockCompleted.get(sux.getLinearScanNumber())) { 154 if (Debug.isLogEnabled()) { 155 Debug.log(" optimizing empty block B%d (pred: B%d, sux: B%d)", block.getId(), pred.getId(), sux.getId()); 156 } 157 158 blockCompleted.set(block.getLinearScanNumber()); 159 160 /* 161 * Directly resolve between pred and sux (without looking at the empty block 162 * between). 163 */ 164 resolveCollectMappings(pred, sux, block, moveResolver); 165 if (moveResolver.hasMappings()) { 166 moveResolver.setInsertPosition(instructions, 1); 167 moveResolver.resolveAndAppendMoves(); 168 } 169 } 170 } 171 } 172 } 173 } 174 175 protected void resolveDataFlow0(MoveResolver moveResolver, BitSet blockCompleted) { 176 BitSet alreadyResolved = new BitSet(allocator.blockCount()); 177 for (AbstractBlockBase<?> fromBlock : allocator.sortedBlocks()) { 178 if (!blockCompleted.get(fromBlock.getLinearScanNumber())) { 179 alreadyResolved.clear(); 180 alreadyResolved.or(blockCompleted); 181 182 for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) { 183 184 /* 185 * Check for duplicate edges between the same blocks (can happen with switch 186 * blocks). 187 */ 188 if (!alreadyResolved.get(toBlock.getLinearScanNumber())) { 189 if (Debug.isLogEnabled()) { 190 Debug.log("processing edge between B%d and B%d", fromBlock.getId(), toBlock.getId()); 191 } 192 193 alreadyResolved.set(toBlock.getLinearScanNumber()); 194 195 // collect all intervals that have been split between 196 // fromBlock and toBlock 197 resolveCollectMappings(fromBlock, toBlock, null, moveResolver); 198 if (moveResolver.hasMappings()) { 199 resolveFindInsertPos(fromBlock, toBlock, moveResolver); 200 moveResolver.resolveAndAppendMoves(); 201 } 202 } 203 } 204 } 205 } 206 } 207 208 }