1 /* 2 * Copyright (c) 2009, 2018, 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 24 25 package org.graalvm.compiler.lir.gen; 26 27 import static jdk.vm.ci.code.ValueUtil.isIllegal; 28 import static jdk.vm.ci.code.ValueUtil.isLegal; 29 import static jdk.vm.ci.meta.Value.ILLEGAL; 30 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable; 31 32 import java.util.ArrayList; 33 import java.util.List; 34 35 import jdk.internal.vm.compiler.collections.EconomicMap; 36 import jdk.internal.vm.compiler.collections.Equivalence; 37 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 38 import org.graalvm.compiler.lir.LIRInsertionBuffer; 39 import org.graalvm.compiler.lir.LIRInstruction; 40 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory; 41 42 import jdk.vm.ci.meta.AllocatableValue; 43 import jdk.vm.ci.meta.Value; 44 45 /** 46 * Converts phi instructions into moves. 47 * 48 * Resolves cycles: 49 * 50 * <pre> 51 * 52 * r1 := r2 becomes temp := r1 53 * r2 := r1 r1 := r2 54 * r2 := temp 55 * </pre> 56 * 57 * and orders moves: 58 * 59 * <pre> 60 * r2 := r3 becomes r1 := r2 61 * r1 := r2 r2 := r3 62 * </pre> 63 */ 64 public class PhiResolver { 65 66 /** 67 * Tracks a data flow dependency between a source operand and any number of the destination 68 * operands. 69 */ 70 static class PhiResolverNode { 71 72 /** 73 * A source operand whose value flows into the {@linkplain #destinations destination} 74 * operands. 75 */ 76 final Value operand; 77 78 /** 79 * The operands whose values are defined by the {@linkplain #operand source} operand. 80 */ 81 final ArrayList<PhiResolverNode> destinations; 82 83 /** 84 * Denotes if a move instruction has already been emitted to initialize the value of 85 * {@link #operand}. 86 */ 87 boolean assigned; 88 89 /** 90 * Specifies if this operand been visited for the purpose of emitting a move instruction. 91 */ 92 boolean visited; 93 94 /** 95 * Specifies if this is the initial definition in data flow path for a given value. 96 */ 97 boolean startNode; 98 PhiResolverNode(Value operand)99 PhiResolverNode(Value operand) { 100 this.operand = operand; 101 destinations = new ArrayList<>(4); 102 } 103 104 @Override toString()105 public String toString() { 106 StringBuilder buf = new StringBuilder(operand.toString()); 107 if (!destinations.isEmpty()) { 108 buf.append(" ->"); 109 for (PhiResolverNode node : destinations) { 110 buf.append(' ').append(node.operand); 111 } 112 } 113 return buf.toString(); 114 } 115 } 116 117 private final LIRGeneratorTool gen; 118 private final MoveFactory moveFactory; 119 private final LIRInsertionBuffer buffer; 120 private final int insertBefore; 121 122 /** 123 * The operand loop header phi for the operand currently being process in {@link #dispose()}. 124 */ 125 private PhiResolverNode loop; 126 127 private Value temp; 128 129 private final ArrayList<PhiResolverNode> variableOperands = new ArrayList<>(3); 130 private final ArrayList<PhiResolverNode> otherOperands = new ArrayList<>(3); 131 132 /** 133 * Maps operands to nodes. 134 */ 135 private final EconomicMap<Value, PhiResolverNode> operandToNodeMap = EconomicMap.create(Equivalence.DEFAULT); 136 create(LIRGeneratorTool gen)137 public static PhiResolver create(LIRGeneratorTool gen) { 138 AbstractBlockBase<?> block = gen.getCurrentBlock(); 139 assert block != null; 140 ArrayList<LIRInstruction> instructions = gen.getResult().getLIR().getLIRforBlock(block); 141 142 return new PhiResolver(gen, new LIRInsertionBuffer(), instructions, instructions.size()); 143 } 144 create(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore)145 public static PhiResolver create(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) { 146 return new PhiResolver(gen, buffer, instructions, insertBefore); 147 } 148 PhiResolver(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore)149 protected PhiResolver(LIRGeneratorTool gen, LIRInsertionBuffer buffer, List<LIRInstruction> instructions, int insertBefore) { 150 this.gen = gen; 151 moveFactory = gen.getSpillMoveFactory(); 152 temp = ILLEGAL; 153 154 this.buffer = buffer; 155 this.buffer.init(instructions); 156 this.insertBefore = insertBefore; 157 158 } 159 dispose()160 public void dispose() { 161 // resolve any cycles in moves from and to variables 162 for (int i = variableOperands.size() - 1; i >= 0; i--) { 163 PhiResolverNode node = variableOperands.get(i); 164 if (!node.visited) { 165 loop = null; 166 move(node, null); 167 node.startNode = true; 168 assert isIllegal(temp) : "moveTempTo() call missing"; 169 } 170 } 171 172 // generate move for move from non variable to arbitrary destination 173 for (int i = otherOperands.size() - 1; i >= 0; i--) { 174 PhiResolverNode node = otherOperands.get(i); 175 for (int j = node.destinations.size() - 1; j >= 0; j--) { 176 emitMove(node.destinations.get(j).operand, node.operand); 177 } 178 } 179 buffer.finish(); 180 } 181 move(Value dest, Value src)182 public void move(Value dest, Value src) { 183 assert isVariable(dest) : "destination must be virtual"; 184 // tty.print("move "); src.print(); tty.print(" to "); dest.print(); tty.cr(); 185 assert isLegal(src) : "source for phi move is illegal"; 186 assert isLegal(dest) : "destination for phi move is illegal"; 187 PhiResolverNode srcNode = sourceNode(src); 188 PhiResolverNode destNode = destinationNode(dest); 189 srcNode.destinations.add(destNode); 190 } 191 createNode(Value operand, boolean source)192 private PhiResolverNode createNode(Value operand, boolean source) { 193 PhiResolverNode node; 194 if (isVariable(operand)) { 195 node = operandToNodeMap.get(operand); 196 assert node == null || node.operand.equals(operand); 197 if (node == null) { 198 node = new PhiResolverNode(operand); 199 operandToNodeMap.put(operand, node); 200 } 201 // Make sure that all variables show up in the list when 202 // they are used as the source of a move. 203 if (source) { 204 if (!variableOperands.contains(node)) { 205 variableOperands.add(node); 206 } 207 } 208 } else { 209 assert source; 210 node = new PhiResolverNode(operand); 211 otherOperands.add(node); 212 } 213 return node; 214 } 215 destinationNode(Value opr)216 private PhiResolverNode destinationNode(Value opr) { 217 return createNode(opr, false); 218 } 219 emitMove(Value dest, Value src)220 private void emitMove(Value dest, Value src) { 221 assert isLegal(src); 222 assert isLegal(dest); 223 LIRInstruction move = moveFactory.createMove((AllocatableValue) dest, src); 224 buffer.append(insertBefore, move); 225 } 226 227 // Traverse assignment graph in depth first order and generate moves in post order 228 // ie. two assignments: b := c, a := b start with node c: 229 // Call graph: move(c, NULL) -> move(b, c) -> move(a, b) 230 // Generates moves in this order: move b to a and move c to b 231 // ie. cycle a := b, b := a start with node a 232 // Call graph: move(a, NULL) -> move(b, a) -> move(a, b) 233 // Generates moves in this order: move b to temp, move a to b, move temp to a move(PhiResolverNode dest, PhiResolverNode src)234 private void move(PhiResolverNode dest, PhiResolverNode src) { 235 if (!dest.visited) { 236 dest.visited = true; 237 for (int i = dest.destinations.size() - 1; i >= 0; i--) { 238 move(dest.destinations.get(i), dest); 239 } 240 } else if (!dest.startNode) { 241 // cycle in graph detected 242 assert loop == null : "only one loop valid!"; 243 loop = dest; 244 moveToTemp(src.operand); 245 return; 246 } // else dest is a start node 247 248 if (!dest.assigned) { 249 if (loop == dest) { 250 moveTempTo(dest.operand); 251 dest.assigned = true; 252 } else if (src != null) { 253 emitMove(dest.operand, src.operand); 254 dest.assigned = true; 255 } 256 } 257 } 258 moveTempTo(Value dest)259 private void moveTempTo(Value dest) { 260 assert isLegal(temp); 261 emitMove(dest, temp); 262 temp = ILLEGAL; 263 } 264 moveToTemp(Value src)265 private void moveToTemp(Value src) { 266 assert isIllegal(temp); 267 temp = gen.newVariable(src.getValueKind()); 268 emitMove(temp, src); 269 } 270 sourceNode(Value opr)271 private PhiResolverNode sourceNode(Value opr) { 272 return createNode(opr, true); 273 } 274 } 275