1 /*
2 * Copyright (c) 2011, 2015, 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 org.graalvm.compiler.core.common.calc.Condition;
26 import org.graalvm.compiler.core.common.type.IntegerStamp;
27 import org.graalvm.compiler.core.common.type.Stamp;
28 import org.graalvm.compiler.core.common.type.StampFactory;
29 import org.graalvm.compiler.graph.NodeClass;
30 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
31 import org.graalvm.compiler.nodeinfo.NodeInfo;
32 import org.graalvm.compiler.nodes.LogicConstantNode;
33 import org.graalvm.compiler.nodes.LogicNegationNode;
34 import org.graalvm.compiler.nodes.LogicNode;
35 import org.graalvm.compiler.nodes.ValueNode;
36 import org.graalvm.compiler.nodes.util.GraphUtil;
37
38 import jdk.vm.ci.code.CodeUtil;
39 import jdk.vm.ci.meta.ConstantReflectionProvider;
40 import jdk.vm.ci.meta.TriState;
41
42 @NodeInfo(shortName = "|<|")
43 public final class IntegerBelowNode extends CompareNode {
44 public static final NodeClass<IntegerBelowNode> TYPE = NodeClass.create(IntegerBelowNode.class);
45
46 public IntegerBelowNode(ValueNode x, ValueNode y) {
47 super(TYPE, Condition.BT, false, x, y);
48 assert x.stamp() instanceof IntegerStamp;
49 assert y.stamp() instanceof IntegerStamp;
50 }
51
52 public static LogicNode create(ValueNode x, ValueNode y, ConstantReflectionProvider constantReflection) {
53 LogicNode result = CompareNode.tryConstantFold(Condition.BT, x, y, constantReflection, false);
54 if (result != null) {
55 return result;
56 } else {
57 result = findSynonym(x, y);
58 if (result != null) {
59 return result;
60 }
61 return new IntegerBelowNode(x, y);
62 }
63 }
64
65 @Override
66 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
67 ValueNode result = super.canonical(tool, forX, forY);
68 if (result != this) {
69 return result;
70 }
71 LogicNode synonym = findSynonym(forX, forY);
72 if (synonym != null) {
73 return synonym;
74 }
75 if (forX.isConstant() && forX.asJavaConstant().asLong() == 0) {
76 // 0 |<| y is the same as 0 != y
77 return LogicNegationNode.create(CompareNode.createCompareNode(Condition.EQ, forX, forY, tool.getConstantReflection()));
78 }
79 return this;
80 }
81
82 private static LogicNode findSynonym(ValueNode forX, ValueNode forY) {
83 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) {
84 return LogicConstantNode.contradiction();
85 } else if (forX.stamp() instanceof IntegerStamp && forY.stamp() instanceof IntegerStamp) {
86 IntegerStamp xStamp = (IntegerStamp) forX.stamp();
87 IntegerStamp yStamp = (IntegerStamp) forY.stamp();
88 if (yStamp.isPositive()) {
89 if (xStamp.isPositive() && xStamp.upperBound() < yStamp.lowerBound()) {
90 return LogicConstantNode.tautology();
91 } else if (xStamp.isStrictlyNegative() || xStamp.lowerBound() >= yStamp.upperBound()) {
92 return LogicConstantNode.contradiction();
93 }
94 }
95 }
96 return null;
97 }
98
99 @Override
100 protected CompareNode duplicateModified(ValueNode newX, ValueNode newY) {
101 return new IntegerBelowNode(newX, newY);
102 }
103
104 @Override
105 public Stamp getSucceedingStampForX(boolean negated) {
106 Stamp xStampGeneric = getX().stamp();
107 Stamp yStampGeneric = getY().stamp();
108 if (xStampGeneric instanceof IntegerStamp) {
109 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
110 int bits = xStamp.getBits();
111 if (yStampGeneric instanceof IntegerStamp) {
112 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
113 assert yStamp.getBits() == bits;
114 if (negated) {
115 // x >= y
116 if (xStamp.isPositive() && yStamp.isPositive()) {
117 long xLowerBound = xStamp.lowerBound();
118 long yLowerBound = yStamp.lowerBound();
119 if (yLowerBound > xLowerBound) {
120 return StampFactory.forIntegerWithMask(bits, yLowerBound, xStamp.upperBound(), xStamp);
121 }
122 }
123 } else {
124 // x < y
125 if (yStamp.isStrictlyPositive()) {
126 // x >= 0 && x < y
127 long xUpperBound = xStamp.upperBound();
128 long yUpperBound = yStamp.upperBound();
129 if (yUpperBound <= xUpperBound || !xStamp.isPositive()) {
130 return StampFactory.forIntegerWithMask(bits, Math.max(0, xStamp.lowerBound()), Math.min(xUpperBound, yUpperBound - 1), xStamp);
131 }
132 }
133 }
134 }
135 }
136 return null;
137 }
138
139 @Override
140 public Stamp getSucceedingStampForY(boolean negated) {
141 Stamp xStampGeneric = getX().stamp();
142 Stamp yStampGeneric = getY().stamp();
143 if (xStampGeneric instanceof IntegerStamp) {
144 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
145 int bits = xStamp.getBits();
146 if (yStampGeneric instanceof IntegerStamp) {
147 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
148 assert yStamp.getBits() == bits;
149 if (negated) {
150 // y <= x
151 if (xStamp.isPositive()) {
152 long xUpperBound = xStamp.upperBound();
153 long yUpperBound = yStamp.upperBound();
154 if (xUpperBound < yUpperBound || !yStamp.isPositive()) {
155 return StampFactory.forIntegerWithMask(bits, Math.max(0, yStamp.lowerBound()), Math.min(xUpperBound, yUpperBound), yStamp);
156 }
157 }
158 } else {
159 // y > x
160 if (xStamp.isPositive() && yStamp.isPositive()) {
161 long xLowerBound = xStamp.lowerBound();
162 long yLowerBound = yStamp.lowerBound();
163 if (xLowerBound == CodeUtil.maxValue(bits)) {
164 return null;
165 } else if (xLowerBound >= yLowerBound) {
166 assert xLowerBound != CodeUtil.maxValue(bits);
167 return StampFactory.forIntegerWithMask(bits, xLowerBound + 1, yStamp.upperBound(), yStamp);
168 }
169 }
170 }
171 }
172 }
173 return null;
174 }
175
176 @Override
177 public TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) {
178 if (xStampGeneric instanceof IntegerStamp) {
179 IntegerStamp xStamp = (IntegerStamp) xStampGeneric;
180 if (yStampGeneric instanceof IntegerStamp) {
181 IntegerStamp yStamp = (IntegerStamp) yStampGeneric;
182 if (yStamp.isPositive()) {
183 if (xStamp.isPositive() && xStamp.upperBound() < yStamp.lowerBound()) {
184 return TriState.TRUE;
185 } else if (xStamp.isStrictlyNegative() || xStamp.lowerBound() >= yStamp.upperBound()) {
186 return TriState.FALSE;
187 }
188 }
189 }
190 }
191 return TriState.UNKNOWN;
192 }
193 }