1 /*
2 * Copyright (c) 2013, 2019, 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
24
25 package org.graalvm.compiler.replacements.nodes.arithmetic;
26
27 import static org.graalvm.compiler.core.common.type.IntegerStamp.addOverflowsNegatively;
28 import static org.graalvm.compiler.core.common.type.IntegerStamp.addOverflowsPositively;
29 import static org.graalvm.compiler.core.common.type.IntegerStamp.carryBits;
30 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_2;
31 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_2;
32
33 import org.graalvm.compiler.core.common.type.IntegerStamp;
34 import org.graalvm.compiler.core.common.type.Stamp;
35 import org.graalvm.compiler.core.common.type.StampFactory;
36 import org.graalvm.compiler.graph.IterableNodeType;
37 import org.graalvm.compiler.graph.NodeClass;
38 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
39 import org.graalvm.compiler.nodeinfo.InputType;
40 import org.graalvm.compiler.nodeinfo.NodeInfo;
41 import org.graalvm.compiler.nodes.ConstantNode;
42 import org.graalvm.compiler.nodes.NodeView;
43 import org.graalvm.compiler.nodes.ValueNode;
44 import org.graalvm.compiler.nodes.calc.AddNode;
45
46 import jdk.vm.ci.code.CodeUtil;
47 import jdk.vm.ci.meta.JavaConstant;
48 import jdk.vm.ci.meta.JavaKind;
49 import org.graalvm.compiler.nodes.extended.GuardedNode;
50 import org.graalvm.compiler.nodes.extended.GuardingNode;
51
52 /**
53 * Node representing an exact integer addition that will throw an {@link ArithmeticException} in
54 * case the addition would overflow the 32 bit range.
55 */
56 @NodeInfo(cycles = CYCLES_2, size = SIZE_2)
57 public final class IntegerAddExactNode extends AddNode implements GuardedNode, IntegerExactArithmeticNode, IterableNodeType {
58 public static final NodeClass<IntegerAddExactNode> TYPE = NodeClass.create(IntegerAddExactNode.class);
59
60 @Input(InputType.Guard) protected GuardingNode guard;
61
62 public IntegerAddExactNode(ValueNode x, ValueNode y, GuardingNode guard) {
63 super(TYPE, x, y);
64 setStamp(x.stamp(NodeView.DEFAULT).unrestricted());
65 assert x.stamp(NodeView.DEFAULT).isCompatible(y.stamp(NodeView.DEFAULT)) && x.stamp(NodeView.DEFAULT) instanceof IntegerStamp;
66 this.guard = guard;
67 }
68
69 @Override
70 public boolean inferStamp() {
71 /*
72 * Note: it is not allowed to use the foldStamp method of the regular add node as we do not
73 * know the result stamp of this node if we do not know whether we may deopt. If we know we
74 * can never overflow we will replace this node with its non overflow checking counterpart
75 * anyway.
76 */
77 return false;
78 }
79
80 @Override
81 public Stamp foldStamp(Stamp stampX, Stamp stampY) {
82 IntegerStamp a = (IntegerStamp) stampX;
83 IntegerStamp b = (IntegerStamp) stampY;
84
85 int bits = a.getBits();
86 assert bits == b.getBits();
87
88 long defaultMask = CodeUtil.mask(bits);
89 long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
90 long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask()));
91 long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry;
92 long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry;
93
94 newDownMask &= defaultMask;
95 newUpMask &= defaultMask;
96
97 long newLowerBound;
98 long newUpperBound;
99 boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits);
100 boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits);
101 boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits);
102 boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits);
103 if (lowerOverflowsPositively) {
104 newLowerBound = CodeUtil.maxValue(bits);
105 } else if (lowerOverflowsNegatively) {
106 newLowerBound = CodeUtil.minValue(bits);
107 } else {
108 newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits);
109 }
110
111 if (upperOverflowsPositively) {
112 newUpperBound = CodeUtil.maxValue(bits);
113 } else if (upperOverflowsNegatively) {
114 newUpperBound = CodeUtil.minValue(bits);
115 } else {
116 newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits);
117 }
118
119 IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound);
120 newUpMask &= limit.upMask();
121 newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits);
122 newDownMask |= limit.downMask();
123 newLowerBound |= newDownMask;
124 return IntegerStamp.create(bits, newLowerBound, newUpperBound, newDownMask, newUpMask);
125 }
126
127 @Override
128 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
129 if (forX.isConstant() && !forY.isConstant()) {
130 return new IntegerAddExactNode(forY, forX, guard).canonical(tool);
131 }
132 if (forX.isConstant() && forY.isConstant()) {
133 return canonicalXYconstant(forX, forY);
134 } else if (forY.isConstant()) {
135 long c = forY.asJavaConstant().asLong();
136 if (c == 0) {
137 return forX;
138 }
139 }
140 if (!IntegerStamp.addCanOverflow((IntegerStamp) forX.stamp(NodeView.DEFAULT), (IntegerStamp) forY.stamp(NodeView.DEFAULT))) {
141 return new AddNode(forX, forY).canonical(tool);
142 }
143 return this;
144 }
145
146 private ValueNode canonicalXYconstant(ValueNode forX, ValueNode forY) {
147 JavaConstant xConst = forX.asJavaConstant();
148 JavaConstant yConst = forY.asJavaConstant();
149 assert xConst.getJavaKind() == yConst.getJavaKind();
150 try {
151 if (xConst.getJavaKind() == JavaKind.Int) {
152 return ConstantNode.forInt(Math.addExact(xConst.asInt(), yConst.asInt()));
153 } else {
154 assert xConst.getJavaKind() == JavaKind.Long;
155 return ConstantNode.forLong(Math.addExact(xConst.asLong(), yConst.asLong()));
156 }
157 } catch (ArithmeticException ex) {
158 // The operation will result in an overflow exception, so do not canonicalize.
159 }
160 return this;
161 }
162
163 @Override
164 public GuardingNode getGuard() {
165 return guard;
166 }
167
168 @Override
169 public void setGuard(GuardingNode guard) {
170 updateUsagesInterface(this.guard, guard);
171 this.guard = guard;
172 }
173 }