1 /*
2 * Copyright (c) 2011, 2018, 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.nodes.calc;
26
27 import org.graalvm.compiler.core.common.type.ArithmeticOpTable;
28 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
29 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Add;
30 import org.graalvm.compiler.core.common.type.IntegerStamp;
31 import org.graalvm.compiler.core.common.type.Stamp;
32 import org.graalvm.compiler.graph.NodeClass;
33 import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative;
34 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
35 import org.graalvm.compiler.lir.gen.ArithmeticLIRGeneratorTool;
36 import org.graalvm.compiler.nodeinfo.NodeInfo;
37 import org.graalvm.compiler.nodes.ConstantNode;
38 import org.graalvm.compiler.nodes.NodeView;
39 import org.graalvm.compiler.nodes.ValueNode;
40 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
41
42 import jdk.vm.ci.code.CodeUtil;
43 import jdk.vm.ci.meta.Constant;
44 import jdk.vm.ci.meta.JavaConstant;
45 import jdk.vm.ci.meta.Value;
46
47 @NodeInfo(shortName = "+")
48 public class AddNode extends BinaryArithmeticNode<Add> implements NarrowableArithmeticNode, BinaryCommutative<ValueNode> {
49
50 public static final NodeClass<AddNode> TYPE = NodeClass.create(AddNode.class);
51
52 public AddNode(ValueNode x, ValueNode y) {
53 this(TYPE, x, y);
54 }
55
56 protected AddNode(NodeClass<? extends AddNode> c, ValueNode x, ValueNode y) {
57 super(c, ArithmeticOpTable::getAdd, x, y);
58 }
59
60 public static ValueNode create(ValueNode x, ValueNode y, NodeView view) {
61 BinaryOp<Add> op = ArithmeticOpTable.forStamp(x.stamp(view)).getAdd();
62 Stamp stamp = op.foldStamp(x.stamp(view), y.stamp(view));
63 ConstantNode tryConstantFold = tryConstantFold(op, x, y, stamp, view);
64 if (tryConstantFold != null) {
65 return tryConstantFold;
66 }
67 if (x.isConstant() && !y.isConstant()) {
68 return canonical(null, op, y, x, view);
69 } else {
70 return canonical(null, op, x, y, view);
71 }
72 }
73
74 private static ValueNode canonical(AddNode addNode, BinaryOp<Add> op, ValueNode forX, ValueNode forY, NodeView view) {
75 AddNode self = addNode;
76 boolean associative = op.isAssociative();
77 if (associative) {
78 if (forX instanceof SubNode) {
79 SubNode sub = (SubNode) forX;
80 if (sub.getY() == forY) {
81 // (a - b) + b
82 return sub.getX();
83 }
84 }
85 if (forY instanceof SubNode) {
86 SubNode sub = (SubNode) forY;
87 if (sub.getY() == forX) {
88 // b + (a - b)
89 return sub.getX();
90 }
91 }
92 }
93 if (forY.isConstant()) {
94 Constant c = forY.asConstant();
95 if (op.isNeutral(c)) {
96 return forX;
97 }
98 if (associative && self != null) {
99 // canonicalize expressions like "(a + 1) + 2"
100 ValueNode reassociated = reassociate(self, ValueNode.isConstantPredicate(), forX, forY, view);
101 if (reassociated != self) {
102 return reassociated;
103 }
104 }
105
106 // Attempt to optimize the pattern of an extend node between two add nodes.
107 if (c instanceof JavaConstant && (forX instanceof SignExtendNode || forX instanceof ZeroExtendNode)) {
108 IntegerConvertNode<?, ?> integerConvertNode = (IntegerConvertNode<?, ?>) forX;
109 ValueNode valueNode = integerConvertNode.getValue();
110 long constant = ((JavaConstant) c).asLong();
111 if (valueNode instanceof AddNode) {
112 AddNode addBeforeExtend = (AddNode) valueNode;
113 if (addBeforeExtend.getY().isConstant()) {
114 // There is a second add before the extend node that also has a constant as
115 // second operand. Therefore there will be canonicalizations triggered if we
116 // can move the add above the extension. For this we need to check whether
117 // the result of the addition is the same before the extension (which can be
118 // either zero extend or sign extend).
119 IntegerStamp beforeExtendStamp = (IntegerStamp) addBeforeExtend.stamp(view);
120 int bits = beforeExtendStamp.getBits();
121 if (constant >= CodeUtil.minValue(bits) && constant <= CodeUtil.maxValue(bits)) {
122 IntegerStamp narrowConstantStamp = IntegerStamp.create(bits, constant, constant);
123
124 if (!IntegerStamp.addCanOverflow(narrowConstantStamp, beforeExtendStamp)) {
125 ConstantNode constantNode = ConstantNode.forIntegerStamp(narrowConstantStamp, constant);
126 if (forX instanceof SignExtendNode) {
127 return SignExtendNode.create(AddNode.create(addBeforeExtend, constantNode, view), integerConvertNode.getResultBits(), view);
128 } else {
129 assert forX instanceof ZeroExtendNode;
130
131 // Must check to not cross zero with the new add.
132 boolean crossesZeroPoint = true;
133 if (constant > 0) {
134 if (beforeExtendStamp.lowerBound() >= 0 || beforeExtendStamp.upperBound() < -constant) {
135 // We are good here.
136 crossesZeroPoint = false;
137 }
138 } else {
139 if (beforeExtendStamp.lowerBound() >= -constant || beforeExtendStamp.upperBound() < 0) {
140 // We are good here as well.
141 crossesZeroPoint = false;
142 }
143 }
144 if (!crossesZeroPoint) {
145 return ZeroExtendNode.create(AddNode.create(addBeforeExtend, constantNode, view), integerConvertNode.getResultBits(), view);
146 }
147 }
148 }
149 }
150 }
151 }
152 }
153 }
154 if (forX instanceof NegateNode) {
155 return BinaryArithmeticNode.sub(forY, ((NegateNode) forX).getValue(), view);
156 } else if (forY instanceof NegateNode) {
157 return BinaryArithmeticNode.sub(forX, ((NegateNode) forY).getValue(), view);
158 }
159 if (self == null) {
160 self = (AddNode) new AddNode(forX, forY).maybeCommuteInputs();
161 }
162 return self;
163 }
164
165 @Override
166 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
167 ValueNode ret = super.canonical(tool, forX, forY);
168 if (ret != this) {
169 return ret;
170 }
171
172 if (forX.isConstant() && !forY.isConstant()) {
173 // we try to swap and canonicalize
174 ValueNode improvement = canonical(tool, forY, forX);
175 if (improvement != this) {
176 return improvement;
177 }
178 // if this fails we only swap
179 return new AddNode(forY, forX);
180 }
181 BinaryOp<Add> op = getOp(forX, forY);
182 NodeView view = NodeView.from(tool);
183 return canonical(this, op, forX, forY, view);
184 }
185
186 @Override
187 public void generate(NodeLIRBuilderTool nodeValueMap, ArithmeticLIRGeneratorTool gen) {
188 Value op1 = nodeValueMap.operand(getX());
189 assert op1 != null : getX() + ", this=" + this;
190 Value op2 = nodeValueMap.operand(getY());
191 if (shouldSwapInputs(nodeValueMap)) {
192 Value tmp = op1;
193 op1 = op2;
194 op2 = tmp;
195 }
196 nodeValueMap.setResult(this, gen.emitAdd(op1, op2, false));
197 }
198 }