1 /*
   2  * Copyright (c) 2015, 2019, 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.StandardOp.BlockEndOp;
  35 import org.graalvm.compiler.lir.StandardOp.JumpOp;
  36 import org.graalvm.compiler.lir.StandardOp.LabelOp;
  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
  71  *   [v3|i, v4|i] = LABEL
  72  *   ...
  73  * </pre>
  74  */
  75 public final class SSAUtil {
  76 
  77     public interface PhiValueVisitor {
  78         /**
  79          * @param phiIn the incoming value at the merge block
  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 void verifyPhi(LIR lir, AbstractBlockBase<?> merge) {
 144         assert merge.getPredecessorCount() > 1;
 145         for (AbstractBlockBase<?> pred : merge.getPredecessors()) {
 146             forEachPhiValuePair(lir, merge, pred, (phiIn, phiOut) -> {
 147                 assert phiIn.getValueKind().equals(phiOut.getValueKind()) ||
 148                                 (phiIn.getPlatformKind().equals(phiOut.getPlatformKind()) && LIRKind.isUnknownReference(phiIn) && LIRKind.isValue(phiOut));
 149             });
 150         }
 151     }
 152 
 153     public static int indexOfValue(LabelOp label, Value value) {
 154         for (int i = 0; i < label.getIncomingSize(); i++) {
 155             if (label.getIncomingValue(i).equals(value)) {
 156                 return i;
 157             }
 158         }
 159         return -1;
 160     }
 161 }