1 /* 2 * Copyright (c) 2015, 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.ssa; 26 27 import java.util.ArrayList; 28 import java.util.Arrays; 29 30 import org.graalvm.compiler.core.common.LIRKind; 31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 32 import org.graalvm.compiler.lir.LIR; 33 import org.graalvm.compiler.lir.LIRInstruction; 34 import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 35 import org.graalvm.compiler.lir.StandardOp.BlockEndOp; 36 import org.graalvm.compiler.lir.StandardOp.JumpOp; 37 import org.graalvm.compiler.lir.StandardOp.LabelOp; 38 import org.graalvm.compiler.lir.ValueConsumer; 39 40 import jdk.vm.ci.meta.Value; 41 42 /** 43 * Utilities for working with Static-Single-Assignment LIR form. 44 * 45 * <h2>Representation of <code>PHI</code>s</h2> 46 * 47 * There is no explicit <code>PHI</code> {@linkplain LIRInstruction}. Instead, they are implemented 48 * as parallel copy that span across a control-flow edge. 49 * 50 * The variables introduced by <code>PHI</code>s of a specific {@linkplain AbstractBlockBase merge 51 * block} are {@linkplain LabelOp#setIncomingValues attached} to the {@linkplain LabelOp} of the 52 * block. The outgoing values from the predecessor are {@link JumpOp#getOutgoingValue input} to the 53 * {@linkplain BlockEndOp} of the predecessor. Because there are no critical edges we know that the 54 * {@link BlockEndOp} of the predecessor has to be a {@link JumpOp}. 55 * 56 * <h3>Example:</h3> 57 * 58 * <pre> 59 * B0 -> B1 60 * ... 61 * v0|i = ... 62 * JUMP ~[v0|i, int[0|0x0]] destination: B0 -> B1 63 * ________________________________________________ 64 * 65 * B2 -> B1 66 * ... 67 * v1|i = ... 68 * v2|i = ... 69 * JUMP ~[v1|i, v2|i] destination: B2 -> B1 70 * ________________________________________________ 71 * 72 * B1 <- B0,B2 73 * [v3|i, v4|i] = LABEL 74 * ... 75 * </pre> 76 */ 77 public final class SSAUtil { 78 79 public interface PhiValueVisitor { 80 /** 81 * @param phiIn the incoming value at the merge block 82 * @param phiOut the outgoing value from the predecessor block 83 */ 84 void visit(Value phiIn, Value phiOut); 85 } 86 87 /** 88 * Visits each phi value pair of an edge, i.e. the outgoing value from the predecessor and the 89 * incoming value to the merge block. 90 */ 91 public static void forEachPhiValuePair(LIR lir, AbstractBlockBase<?> merge, AbstractBlockBase<?> pred, PhiValueVisitor visitor) { 92 if (merge.getPredecessorCount() < 2) { 93 return; 94 } 95 assert Arrays.asList(merge.getPredecessors()).contains(pred) : String.format("%s not in predecessor list: %s", pred, Arrays.toString(merge.getPredecessors())); 96 assert pred.getSuccessorCount() == 1 : String.format("Merge predecessor block %s has more than one successor? %s", pred, Arrays.toString(pred.getSuccessors())); 97 assert pred.getSuccessors()[0] == merge : String.format("Predecessor block %s has wrong successor: %s, should be: %s", pred, pred.getSuccessors()[0], merge); 98 99 JumpOp jump = phiOut(lir, pred); 100 LabelOp label = phiIn(lir, merge); 101 102 assert label.getPhiSize() == jump.getPhiSize() : String.format("Phi In/Out size mismatch: in=%d vs. out=%d", label.getPhiSize(), jump.getPhiSize()); 103 104 for (int i = 0; i < label.getPhiSize(); i++) { 105 visitor.visit(label.getIncomingValue(i), jump.getOutgoingValue(i)); 106 } 107 } 108 109 public static JumpOp phiOut(LIR lir, AbstractBlockBase<?> block) { 110 assert block.getSuccessorCount() == 1; 111 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 112 int index = instructions.size() - 1; 113 LIRInstruction op = instructions.get(index); 114 return (JumpOp) op; 115 } 116 117 public static JumpOp phiOutOrNull(LIR lir, AbstractBlockBase<?> block) { 118 if (block.getSuccessorCount() != 1) { 119 return null; 120 } 121 return phiOut(lir, block); 122 } 123 124 public static int phiOutIndex(LIR lir, AbstractBlockBase<?> block) { 125 assert block.getSuccessorCount() == 1; 126 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 127 int index = instructions.size() - 1; 128 assert instructions.get(index) instanceof JumpOp; 129 return index; 130 } 131 132 public static LabelOp phiIn(LIR lir, AbstractBlockBase<?> block) { 133 assert block.getPredecessorCount() > 1; 134 LabelOp label = (LabelOp) lir.getLIRforBlock(block).get(0); 135 return label; 136 } 137 138 public static void removePhiOut(LIR lir, AbstractBlockBase<?> block) { 139 JumpOp jump = phiOut(lir, block); 140 jump.clearOutgoingValues(); 141 } 142 143 public static void removePhiIn(LIR lir, AbstractBlockBase<?> block) { 144 LabelOp label = phiIn(lir, block); 145 label.clearIncomingValues(); 146 } 147 148 public static boolean verifySSAForm(LIR lir) { 149 return new SSAVerifier(lir).verify(); 150 } 151 152 public static boolean isMerge(AbstractBlockBase<?> block) { 153 return block.getPredecessorCount() > 1; 154 } 155 156 public static void verifyPhi(LIR lir, AbstractBlockBase<?> merge) { 157 assert merge.getPredecessorCount() > 1; 158 for (AbstractBlockBase<?> pred : merge.getPredecessors()) { 159 forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> { 160 assert phiIn.getValueKind().equals(phiOut.getValueKind()) || 161 (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && LIRKind.isUnknownReference(phiIn) && LIRKind.isValue(phiOut)); 162 }); 163 } 164 } 165 166 public static void forEachPhiRegisterHint(LIR lir, AbstractBlockBase<?> block, LabelOp label, Value targetValue, OperandMode mode, ValueConsumer valueConsumer) { 167 assert mode == OperandMode.DEF : "Wrong operand mode: " + mode; 168 assert lir.getLIRforBlock(block).get(0).equals(label) : String.format("Block %s and Label %s do not match!", block, label); 169 170 if (!label.isPhiIn()) { 171 return; 172 } 173 int idx = indexOfValue(label, targetValue); 174 assert idx >= 0 : String.format("Value %s not in label %s", targetValue, label); 175 176 for (AbstractBlockBase<?> pred : block.getPredecessors()) { 177 JumpOp jump = phiOut(lir, pred); 178 Value sourceValue = jump.getOutgoingValue(idx); 179 valueConsumer.visitValue(jump, sourceValue, null, null); 180 } 181 182 } 183 184 private static int indexOfValue(LabelOp label, Value value) { 185 for (int i = 0; i < label.getIncomingSize(); i++) { 186 if (label.getIncomingValue(i).equals(value)) { 187 return i; 188 } 189 } 190 return -1; 191 } 192 193 public static int numPhiOut(LIR lir, AbstractBlockBase<?> block) { 194 if (block.getSuccessorCount() != 1) { 195 // cannot be a phi_out block 196 return 0; 197 } 198 return numPhiIn(lir, block.getSuccessors()[0]); 199 } 200 201 private static int numPhiIn(LIR lir, AbstractBlockBase<?> block) { 202 if (!isMerge(block)) { 203 return 0; 204 } 205 return phiIn(lir, block).getPhiSize(); 206 } 207 208 }