1 /*
   2  * Copyright (c) 2009, 2014, 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.calc;
  24 
  25 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_1;
  26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
  27 import static org.graalvm.compiler.nodes.calc.CompareNode.createCompareNode;
  28 
  29 import org.graalvm.compiler.core.common.calc.Condition;
  30 import org.graalvm.compiler.core.common.type.IntegerStamp;
  31 import org.graalvm.compiler.core.common.type.Stamp;
  32 import org.graalvm.compiler.core.common.type.StampFactory;
  33 import org.graalvm.compiler.graph.NodeClass;
  34 import org.graalvm.compiler.graph.spi.Canonicalizable;
  35 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
  36 import org.graalvm.compiler.nodeinfo.InputType;
  37 import org.graalvm.compiler.nodeinfo.NodeInfo;
  38 import org.graalvm.compiler.nodes.ConstantNode;
  39 import org.graalvm.compiler.nodes.LogicConstantNode;
  40 import org.graalvm.compiler.nodes.LogicNegationNode;
  41 import org.graalvm.compiler.nodes.LogicNode;
  42 import org.graalvm.compiler.nodes.StructuredGraph;
  43 import org.graalvm.compiler.nodes.ValueNode;
  44 import org.graalvm.compiler.nodes.spi.LIRLowerable;
  45 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
  46 
  47 import jdk.vm.ci.meta.JavaConstant;
  48 
  49 /**
  50  * The {@code ConditionalNode} class represents a comparison that yields one of two (eagerly
  51  * evaluated) values.
  52  */
  53 @NodeInfo(cycles = CYCLES_1, size = SIZE_2)
  54 public final class ConditionalNode extends FloatingNode implements Canonicalizable, LIRLowerable {
  55 
  56     public static final NodeClass<ConditionalNode> TYPE = NodeClass.create(ConditionalNode.class);
  57     @Input(InputType.Condition) LogicNode condition;
  58     @Input ValueNode trueValue;
  59     @Input ValueNode falseValue;
  60 
  61     public LogicNode condition() {
  62         return condition;
  63     }
  64 
  65     public ConditionalNode(LogicNode condition) {
  66         this(condition, ConstantNode.forInt(1, condition.graph()), ConstantNode.forInt(0, condition.graph()));
  67     }
  68 
  69     public ConditionalNode(LogicNode condition, ValueNode trueValue, ValueNode falseValue) {
  70         super(TYPE, trueValue.stamp().meet(falseValue.stamp()));
  71         assert trueValue.stamp().isCompatible(falseValue.stamp());
  72         this.condition = condition;
  73         this.trueValue = trueValue;
  74         this.falseValue = falseValue;
  75     }
  76 
  77     public static ValueNode create(LogicNode condition) {
  78         return create(condition, ConstantNode.forInt(1, condition.graph()), ConstantNode.forInt(0, condition.graph()));
  79     }
  80 
  81     public static ValueNode create(LogicNode condition, ValueNode trueValue, ValueNode falseValue) {
  82         ValueNode synonym = findSynonym(condition, trueValue, falseValue);
  83         if (synonym != null) {
  84             return synonym;
  85         }
  86         ValueNode result = canonicalizeConditional(condition, trueValue, falseValue, trueValue.stamp().meet(falseValue.stamp()));
  87         if (result != null) {
  88             return result;
  89         }
  90         return new ConditionalNode(condition, trueValue, falseValue);
  91     }
  92 
  93     @Override
  94     public boolean inferStamp() {
  95         Stamp valueStamp = trueValue.stamp().meet(falseValue.stamp());
  96         if (condition instanceof IntegerLessThanNode) {
  97             IntegerLessThanNode lessThan = (IntegerLessThanNode) condition;
  98             if (lessThan.getX() == trueValue && lessThan.getY() == falseValue) {
  99                 // this encodes a min operation
 100                 JavaConstant constant = lessThan.getX().asJavaConstant();
 101                 if (constant == null) {
 102                     constant = lessThan.getY().asJavaConstant();
 103                 }
 104                 if (constant != null) {
 105                     IntegerStamp bounds = StampFactory.forInteger(constant.getJavaKind(), constant.getJavaKind().getMinValue(), constant.asLong());
 106                     valueStamp = valueStamp.join(bounds);
 107                 }
 108             } else if (lessThan.getX() == falseValue && lessThan.getY() == trueValue) {
 109                 // this encodes a max operation
 110                 JavaConstant constant = lessThan.getX().asJavaConstant();
 111                 if (constant == null) {
 112                     constant = lessThan.getY().asJavaConstant();
 113                 }
 114                 if (constant != null) {
 115                     IntegerStamp bounds = StampFactory.forInteger(constant.getJavaKind(), constant.asLong(), constant.getJavaKind().getMaxValue());
 116                     valueStamp = valueStamp.join(bounds);
 117                 }
 118             }
 119         }
 120         return updateStamp(valueStamp);
 121     }
 122 
 123     public ValueNode trueValue() {
 124         return trueValue;
 125     }
 126 
 127     public ValueNode falseValue() {
 128         return falseValue;
 129     }
 130 
 131     @Override
 132     public ValueNode canonical(CanonicalizerTool tool) {
 133         ValueNode synonym = findSynonym(condition, trueValue(), falseValue());
 134         if (synonym != null) {
 135             return synonym;
 136         }
 137 
 138         ValueNode result = canonicalizeConditional(condition, trueValue(), falseValue(), stamp);
 139         if (result != null) {
 140             return result;
 141         }
 142 
 143         return this;
 144     }
 145 
 146     public static ValueNode canonicalizeConditional(LogicNode condition, ValueNode trueValue, ValueNode falseValue, Stamp stamp) {
 147         if (trueValue == falseValue) {
 148             return trueValue;
 149         }
 150 
 151         if (condition instanceof CompareNode && ((CompareNode) condition).isIdentityComparison()) {
 152             // optimize the pattern (x == y) ? x : y
 153             CompareNode compare = (CompareNode) condition;
 154             if ((compare.getX() == trueValue && compare.getY() == falseValue) || (compare.getX() == falseValue && compare.getY() == trueValue)) {
 155                 return falseValue;
 156             }
 157         }
 158 
 159         if (trueValue.stamp() instanceof IntegerStamp) {
 160             // check if the conditional is redundant
 161             if (condition instanceof IntegerLessThanNode) {
 162                 IntegerLessThanNode lessThan = (IntegerLessThanNode) condition;
 163                 IntegerStamp falseValueStamp = (IntegerStamp) falseValue.stamp();
 164                 IntegerStamp trueValueStamp = (IntegerStamp) trueValue.stamp();
 165                 if (lessThan.getX() == trueValue && lessThan.getY() == falseValue) {
 166                     // return "x" for "x < y ? x : y" in case that we know "x <= y"
 167                     if (trueValueStamp.upperBound() <= falseValueStamp.lowerBound()) {
 168                         return trueValue;
 169                     }
 170                 } else if (lessThan.getX() == falseValue && lessThan.getY() == trueValue) {
 171                     // return "x" for "x < y ? y : x" in case that we know "x <= y"
 172                     if (falseValueStamp.upperBound() <= trueValueStamp.lowerBound()) {
 173                         return falseValue;
 174                     }
 175                 }
 176             }
 177 
 178             // this optimizes the case where a value from the range 0 - 1 is mapped to the
 179             // range 0 - 1
 180             if (trueValue.isConstant() && falseValue.isConstant()) {
 181                 long constTrueValue = trueValue.asJavaConstant().asLong();
 182                 long constFalseValue = falseValue.asJavaConstant().asLong();
 183                 if (condition instanceof IntegerEqualsNode) {
 184                     IntegerEqualsNode equals = (IntegerEqualsNode) condition;
 185                     if (equals.getY().isConstant() && equals.getX().stamp() instanceof IntegerStamp) {
 186                         IntegerStamp equalsXStamp = (IntegerStamp) equals.getX().stamp();
 187                         if (equalsXStamp.upMask() == 1) {
 188                             long equalsY = equals.getY().asJavaConstant().asLong();
 189                             if (equalsY == 0) {
 190                                 if (constTrueValue == 0 && constFalseValue == 1) {
 191                                     // return x when: x == 0 ? 0 : 1;
 192                                     return IntegerConvertNode.convertUnsigned(equals.getX(), stamp);
 193                                 } else if (constTrueValue == 1 && constFalseValue == 0) {
 194                                     // negate a boolean value via xor
 195                                     return IntegerConvertNode.convertUnsigned(XorNode.create(equals.getX(), ConstantNode.forIntegerStamp(equals.getX().stamp(), 1)), stamp);
 196                                 }
 197                             } else if (equalsY == 1) {
 198                                 if (constTrueValue == 1 && constFalseValue == 0) {
 199                                     // return x when: x == 1 ? 1 : 0;
 200                                     return IntegerConvertNode.convertUnsigned(equals.getX(), stamp);
 201                                 } else if (constTrueValue == 0 && constFalseValue == 1) {
 202                                     // negate a boolean value via xor
 203                                     return IntegerConvertNode.convertUnsigned(XorNode.create(equals.getX(), ConstantNode.forIntegerStamp(equals.getX().stamp(), 1)), stamp);
 204                                 }
 205                             }
 206                         }
 207                     }
 208                 } else if (condition instanceof IntegerTestNode) {
 209                     // replace IntegerTestNode with AndNode for the following patterns:
 210                     // (value & 1) == 0 ? 0 : 1
 211                     // (value & 1) == 1 ? 1 : 0
 212                     IntegerTestNode integerTestNode = (IntegerTestNode) condition;
 213                     if (integerTestNode.getY().isConstant()) {
 214                         assert integerTestNode.getX().stamp() instanceof IntegerStamp;
 215                         long testY = integerTestNode.getY().asJavaConstant().asLong();
 216                         if (testY == 1 && constTrueValue == 0 && constFalseValue == 1) {
 217                             return IntegerConvertNode.convertUnsigned(AndNode.create(integerTestNode.getX(), integerTestNode.getY()), stamp);
 218                         }
 219                     }
 220                 }
 221             }
 222 
 223             if (condition instanceof IntegerLessThanNode) {
 224                 /*
 225                  * Convert a conditional add ((x < 0) ? (x + y) : x) into (x + (y & (x >> (bits -
 226                  * 1)))) to avoid the test.
 227                  */
 228                 IntegerLessThanNode lt = (IntegerLessThanNode) condition;
 229                 if (lt.getY().isConstant() && lt.getY().asConstant().isDefaultForKind()) {
 230                     if (falseValue == lt.getX()) {
 231                         if (trueValue instanceof AddNode) {
 232                             AddNode add = (AddNode) trueValue;
 233                             if (add.getX() == falseValue) {
 234                                 int bits = ((IntegerStamp) trueValue.stamp()).getBits();
 235                                 ValueNode shift = new RightShiftNode(lt.getX(), ConstantNode.forIntegerBits(32, bits - 1));
 236                                 ValueNode and = new AndNode(shift, add.getY());
 237                                 return new AddNode(add.getX(), and);
 238                             }
 239                         }
 240                     }
 241                 }
 242             }
 243         }
 244 
 245         return null;
 246     }
 247 
 248     private static ValueNode findSynonym(ValueNode condition, ValueNode trueValue, ValueNode falseValue) {
 249         if (condition instanceof LogicNegationNode) {
 250             LogicNegationNode negated = (LogicNegationNode) condition;
 251             return ConditionalNode.create(negated.getValue(), falseValue, trueValue);
 252         }
 253         if (condition instanceof LogicConstantNode) {
 254             LogicConstantNode c = (LogicConstantNode) condition;
 255             if (c.getValue()) {
 256                 return trueValue;
 257             } else {
 258                 return falseValue;
 259             }
 260         }
 261         return null;
 262     }
 263 
 264     @Override
 265     public void generate(NodeLIRBuilderTool generator) {
 266         generator.emitConditional(this);
 267     }
 268 
 269     public ConditionalNode(StructuredGraph graph, Condition condition, ValueNode x, ValueNode y) {
 270         this(createCompareNode(graph, condition, x, y, null));
 271     }
 272 }