1 /*
2 * Copyright (c) 2013, 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.replacements.nodes.arithmetic;
24
25 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_4;
26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
27
28 import org.graalvm.compiler.core.common.type.IntegerStamp;
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.AbstractBeginNode;
33 import org.graalvm.compiler.nodes.ConstantNode;
34 import org.graalvm.compiler.nodes.ValueNode;
35 import org.graalvm.compiler.nodes.calc.MulNode;
36 import org.graalvm.compiler.nodes.spi.LoweringTool;
37
38 import jdk.vm.ci.meta.JavaConstant;
39 import jdk.vm.ci.meta.JavaKind;
40
41 /**
42 * Node representing an exact integer multiplication that will throw an {@link ArithmeticException}
43 * in case the addition would overflow the 32 bit range.
44 */
45 @NodeInfo(cycles = CYCLES_4, cyclesRationale = "mul+cmp", size = SIZE_2)
46 public final class IntegerMulExactNode extends MulNode implements IntegerExactArithmeticNode {
47 public static final NodeClass<IntegerMulExactNode> TYPE = NodeClass.create(IntegerMulExactNode.class);
48
49 public IntegerMulExactNode(ValueNode x, ValueNode y) {
50 super(TYPE, x, y);
51 setStamp(x.stamp().unrestricted());
52 assert x.stamp().isCompatible(y.stamp()) && x.stamp() instanceof IntegerStamp;
53 }
54
55 @Override
56 public boolean inferStamp() {
57 /*
58 * Note: it is not allowed to use the foldStamp method of the regular mul node as we do not
59 * know the result stamp of this node if we do not know whether we may deopt. If we know we
60 * can never overflow we will replace this node with its non overflow checking counterpart
61 * anyway.
62 */
63 return false;
64 }
65
66 @Override
67 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
68 if (forX.isConstant() && !forY.isConstant()) {
69 return new IntegerMulExactNode(forY, forX);
70 }
71 if (forX.isConstant()) {
72 return canonicalXconstant(forX, forY);
73 } else if (forY.isConstant()) {
74 long c = forY.asJavaConstant().asLong();
75 if (c == 1) {
76 return forX;
77 }
78 if (c == 0) {
79 return ConstantNode.forIntegerStamp(stamp(), 0);
80 }
81 }
82 if (!mayOverFlow((IntegerStamp) x.stamp(), (IntegerStamp) y.stamp())) {
83 return new MulNode(x, y).canonical(tool);
84 }
85 return this;
86 }
87
88 private static boolean mayOverFlow(IntegerStamp a, IntegerStamp b) {
89 // see IntegerStamp#foldStamp for details
90 assert a.getBits() == b.getBits();
91 if (a.upMask() == 0) {
92 return false;
93 } else if (b.upMask() == 0) {
94 return false;
95 }
96 if (a.isUnrestricted()) {
97 return true;
98 }
99 if (b.isUnrestricted()) {
100 return true;
101 }
102 int bits = a.getBits();
103 // Checkstyle: stop
104 long minN_a = a.lowerBound();
105 long maxN_a = Math.min(0, a.upperBound());
106 long minP_a = Math.max(0, a.lowerBound());
107 long maxP_a = a.upperBound();
108
109 long minN_b = b.lowerBound();
110 long maxN_b = Math.min(0, b.upperBound());
111 long minP_b = Math.max(0, b.lowerBound());
112 long maxP_b = b.upperBound();
113 // Checkstyle: resume
114
115 boolean mayOverflow = false;
116 if (a.canBePositive()) {
117 if (b.canBePositive()) {
118 mayOverflow |= IntegerStamp.multiplicationOverflows(maxP_a, maxP_b, bits);
119 mayOverflow |= IntegerStamp.multiplicationOverflows(minP_a, minP_b, bits);
120 }
121 if (b.canBeNegative()) {
122 mayOverflow |= IntegerStamp.multiplicationOverflows(minP_a, maxN_b, bits);
123 mayOverflow |= IntegerStamp.multiplicationOverflows(maxP_a, minN_b, bits);
124
125 }
126 }
127 if (a.canBeNegative()) {
128 if (b.canBePositive()) {
129 mayOverflow |= IntegerStamp.multiplicationOverflows(maxN_a, minP_b, bits);
130 mayOverflow |= IntegerStamp.multiplicationOverflows(minN_a, maxP_b, bits);
131 }
132 if (b.canBeNegative()) {
133 mayOverflow |= IntegerStamp.multiplicationOverflows(minN_a, minN_b, bits);
134 mayOverflow |= IntegerStamp.multiplicationOverflows(maxN_a, maxN_b, bits);
135 }
136 }
137 return mayOverflow;
138 }
139
140 private ValueNode canonicalXconstant(ValueNode forX, ValueNode forY) {
141 JavaConstant xConst = forX.asJavaConstant();
142 JavaConstant yConst = forY.asJavaConstant();
143 assert xConst.getJavaKind() == yConst.getJavaKind();
144 try {
145 if (xConst.getJavaKind() == JavaKind.Int) {
146 return ConstantNode.forInt(Math.multiplyExact(xConst.asInt(), yConst.asInt()));
147 } else {
148 assert xConst.getJavaKind() == JavaKind.Long;
149 return ConstantNode.forLong(Math.multiplyExact(xConst.asLong(), yConst.asLong()));
150 }
151 } catch (ArithmeticException ex) {
152 // The operation will result in an overflow exception, so do not canonicalize.
153 }
154 return this;
155 }
156
157 @Override
158 public IntegerExactArithmeticSplitNode createSplit(AbstractBeginNode next, AbstractBeginNode deopt) {
159 return graph().add(new IntegerMulExactSplitNode(stamp(), getX(), getY(), next, deopt));
160 }
161
162 @Override
163 public void lower(LoweringTool tool) {
164 IntegerExactArithmeticSplitNode.lower(tool, this);
165 }
166 }