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