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             return super.toString(Verbosity.Name) + "(" + str + ")";
 136         } else {
 137             return super.toString(verbosity);
 138         }








 139     }
 140 
 141     public void addInput(ValueNode x) {
 142         assert !(x instanceof ValuePhiNode) || ((ValuePhiNode) x).merge() instanceof LoopBeginNode || ((ValuePhiNode) x).merge() != this.merge();
 143         assert !(this instanceof ValuePhiNode) || x.stamp().isCompatible(stamp());
 144         values().add(x);
 145     }
 146 
 147     public void removeInput(int index) {
 148         values().remove(index);
 149     }
 150 
 151     public NodeIterable<ValueNode> backValues() {
 152         return values().subList(merge().forwardEndCount());
 153     }
 154 
 155     /**
 156      * If all inputs are the same value, this value is returned, otherwise {@code this}. Note that
 157      * {@code null} is a valid return value, since {@link GuardPhiNode}s can have {@code null}
 158      * inputs.
 159      */
 160     public ValueNode singleValueOrThis() {
 161         ValueNode singleValue = valueAt(0);
 162         int count = valueCount();
 163         for (int i = 1; i < count; ++i) {
 164             ValueNode value = valueAt(i);
 165             if (value != this) {
 166                 if (value != singleValue) {
 167                     return this;
 168                 }
 169             }
 170         }
 171         return singleValue;
 172     }
 173 
 174     /**
 175      * If all inputs (but the first one) are the same value, the value is returned, otherwise
 176      * {@code this}. Note that {@code null} is a valid return value, since {@link GuardPhiNode}s can
 177      * have {@code null} inputs.
 178      */
 179     public ValueNode singleBackValueOrThis() {
 180         int valueCount = valueCount();
 181         assert merge() instanceof LoopBeginNode && valueCount >= 2;
 182         // Skip first value, assume second value as single value.
 183         ValueNode singleValue = valueAt(1);
 184         for (int i = 2; i < valueCount; ++i) {
 185             ValueNode value = valueAt(i);
 186             if (value != singleValue) {
 187                 return this;
 188             }
 189         }
 190         return singleValue;
 191     }
 192 
 193     @Override
 194     public ValueNode canonical(CanonicalizerTool tool) {
 195 
 196         if (isLoopPhi()) {
 197 
 198             int valueCount = valueCount();
 199             assert valueCount >= 2;
 200             int i;
 201             for (i = 1; i < valueCount; ++i) {
 202                 ValueNode value = valueAt(i);
 203                 if (value != this) {
 204                     break;
 205                 }
 206             }
 207 
 208             // All back edges are self-references => return forward edge input value.
 209             if (i == valueCount) {
 210                 return firstValue();
 211             }
 212 
 213             boolean onlySelfUsage = true;
 214             for (Node n : this.usages()) {
 215                 if (n != this) {
 216                     onlySelfUsage = false;
 217                     break;
 218                 }
 219             }
 220 
 221             if (onlySelfUsage) {
 222                 return null;
 223             }
 224         }
 225 
 226         return singleValueOrThis();
 227     }
 228 
 229     public ValueNode firstValue() {
 230         return valueAt(0);
 231     }
 232 
 233     public boolean isLoopPhi() {
 234         return merge() instanceof LoopBeginNode;
 235     }
 236 }
--- EOF ---