1 /*
   2  * Copyright (c) 2009, 2017, 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.nodes;
  24 
  25 import static org.graalvm.compiler.nodeinfo.InputType.Association;
  26 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0;
  27 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_1;
  28 
  29 import org.graalvm.compiler.core.common.type.Stamp;
  30 import org.graalvm.compiler.graph.Node;
  31 import org.graalvm.compiler.graph.NodeClass;
  32 import org.graalvm.compiler.graph.NodeInputList;
  33 import org.graalvm.compiler.graph.iterators.NodeIterable;
  34 import org.graalvm.compiler.graph.spi.Canonicalizable;
  35 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
  36 import org.graalvm.compiler.nodeinfo.NodeInfo;
  37 import org.graalvm.compiler.nodeinfo.Verbosity;
  38 import org.graalvm.compiler.nodes.calc.FloatingNode;
  39 
  40 /**
  41  * {@code PhiNode}s represent the merging of edges at a control flow merges (
  42  * {@link AbstractMergeNode} or {@link LoopBeginNode}). For a {@link AbstractMergeNode}, the order
  43  * of the values corresponds to the order of the ends. For {@link LoopBeginNode}s, the first value
  44  * corresponds to the loop's predecessor, while the rest of the values correspond to the
  45  * {@link LoopEndNode}s.
  46  */
  47 @NodeInfo(cycles = CYCLES_0, size = SIZE_1)
  48 public abstract class PhiNode extends FloatingNode implements Canonicalizable {
  49 
  50     public static final NodeClass<PhiNode> TYPE = NodeClass.create(PhiNode.class);
  51     @Input(Association) protected AbstractMergeNode merge;
  52 
  53     protected PhiNode(NodeClass<? extends PhiNode> c, Stamp stamp, AbstractMergeNode merge) {
  54         super(c, stamp);
  55         this.merge = merge;
  56     }
  57 
  58     public abstract NodeInputList<ValueNode> values();
  59 
  60     public AbstractMergeNode merge() {
  61         return merge;
  62     }
  63 
  64     public void setMerge(AbstractMergeNode x) {
  65         updateUsages(merge, x);
  66         merge = x;
  67     }
  68 
  69     @Override
  70     public boolean verify() {
  71         assertTrue(merge() != null, "missing merge");
  72         assertTrue(merge().phiPredecessorCount() == valueCount(), "mismatch between merge predecessor count and phi value count: %d != %d", merge().phiPredecessorCount(), valueCount());
  73         return super.verify();
  74     }
  75 
  76     /**
  77      * Get the instruction that produces the value associated with the i'th predecessor of the
  78      * merge.
  79      *
  80      * @param i the index of the predecessor
  81      * @return the instruction that produced the value in the i'th predecessor
  82      */
  83     public ValueNode valueAt(int i) {
  84         return values().get(i);
  85     }
  86 
  87     /**
  88      * Sets the value at the given index and makes sure that the values list is large enough.
  89      *
  90      * @param i the index at which to set the value
  91      * @param x the new phi input value for the given location
  92      */
  93     public void initializeValueAt(int i, ValueNode x) {
  94         while (values().size() <= i) {
  95             values().add(null);
  96         }
  97         values().set(i, x);
  98     }
  99 
 100     public void setValueAt(int i, ValueNode x) {
 101         values().set(i, x);
 102     }
 103 
 104     public void setValueAt(AbstractEndNode end, ValueNode x) {
 105         setValueAt(merge().phiPredecessorIndex(end), x);
 106     }
 107 
 108     public ValueNode valueAt(AbstractEndNode pred) {
 109         return valueAt(merge().phiPredecessorIndex(pred));
 110     }
 111 
 112     /**
 113      * Get the number of inputs to this phi (i.e. the number of predecessors to the merge).
 114      *
 115      * @return the number of inputs in this phi
 116      */
 117     public int valueCount() {
 118         return values().size();
 119     }
 120 
 121     public void clearValues() {
 122         values().clear();
 123     }
 124 
 125     @Override
 126     public String toString(Verbosity verbosity) {
 127         if (verbosity == Verbosity.Name) {
 128             StringBuilder str = new StringBuilder();
 129             for (int i = 0; i < valueCount(); ++i) {
 130                 if (i != 0) {
 131                     str.append(' ');
 132                 }
 133                 str.append(valueAt(i) == null ? "-" : valueAt(i).toString(Verbosity.Id));
 134             }
 135             String description = valueDescription();
 136             if (description.length() > 0) {
 137                 str.append(", ").append(description);
 138             }
 139             return super.toString(Verbosity.Name) + "(" + str + ")";
 140         } else {
 141             return super.toString(verbosity);
 142         }
 143     }
 144 
 145     /**
 146      * String describing the kind of value this Phi merges. Used by {@link #toString(Verbosity)} and
 147      * dumping.
 148      */
 149     protected String valueDescription() {
 150         return "";
 151     }
 152 
 153     public void addInput(ValueNode x) {
 154         assert !(x instanceof ValuePhiNode) || ((ValuePhiNode) x).merge() instanceof LoopBeginNode || ((ValuePhiNode) x).merge() != this.merge();
 155         assert !(this instanceof ValuePhiNode) || x.stamp().isCompatible(stamp());
 156         values().add(x);
 157     }
 158 
 159     public void removeInput(int index) {
 160         values().remove(index);
 161     }
 162 
 163     public NodeIterable<ValueNode> backValues() {
 164         return values().subList(merge().forwardEndCount());
 165     }
 166 
 167     /**
 168      * If all inputs are the same value, this value is returned, otherwise {@code this}. Note that
 169      * {@code null} is a valid return value, since {@link GuardPhiNode}s can have {@code null}
 170      * inputs.
 171      */
 172     public ValueNode singleValueOrThis() {
 173         ValueNode singleValue = valueAt(0);
 174         int count = valueCount();
 175         for (int i = 1; i < count; ++i) {
 176             ValueNode value = valueAt(i);
 177             if (value != this) {
 178                 if (value != singleValue) {
 179                     return this;
 180                 }
 181             }
 182         }
 183         return singleValue;
 184     }
 185 
 186     /**
 187      * If all inputs (but the first one) are the same value, the value is returned, otherwise
 188      * {@code this}. Note that {@code null} is a valid return value, since {@link GuardPhiNode}s can
 189      * have {@code null} inputs.
 190      */
 191     public ValueNode singleBackValueOrThis() {
 192         int valueCount = valueCount();
 193         assert merge() instanceof LoopBeginNode && valueCount >= 2;
 194         // Skip first value, assume second value as single value.
 195         ValueNode singleValue = valueAt(1);
 196         for (int i = 2; i < valueCount; ++i) {
 197             ValueNode value = valueAt(i);
 198             if (value != singleValue) {
 199                 return this;
 200             }
 201         }
 202         return singleValue;
 203     }
 204 
 205     @Override
 206     public ValueNode canonical(CanonicalizerTool tool) {
 207 
 208         if (isLoopPhi()) {
 209 
 210             int valueCount = valueCount();
 211             assert valueCount >= 2;
 212             int i;
 213             for (i = 1; i < valueCount; ++i) {
 214                 ValueNode value = valueAt(i);
 215                 if (value != this) {
 216                     break;
 217                 }
 218             }
 219 
 220             // All back edges are self-references => return forward edge input value.
 221             if (i == valueCount) {
 222                 return firstValue();
 223             }
 224 
 225             boolean onlySelfUsage = true;
 226             for (Node n : this.usages()) {
 227                 if (n != this) {
 228                     onlySelfUsage = false;
 229                     break;
 230                 }
 231             }
 232 
 233             if (onlySelfUsage) {
 234                 return null;
 235             }
 236         }
 237 
 238         return singleValueOrThis();
 239     }
 240 
 241     public ValueNode firstValue() {
 242         return valueAt(0);
 243     }
 244 
 245     public boolean isLoopPhi() {
 246         return merge() instanceof LoopBeginNode;
 247     }
 248 }