1 /* 2 * Copyright (c) 2009, 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.nodes.calc; 26 27 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_1; 28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_1; 29 30 import org.graalvm.compiler.core.common.type.ArithmeticOpTable; 31 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp; 32 import org.graalvm.compiler.core.common.type.IntegerStamp; 33 import org.graalvm.compiler.core.common.type.Stamp; 34 import org.graalvm.compiler.debug.GraalError; 35 import org.graalvm.compiler.graph.Graph; 36 import org.graalvm.compiler.graph.Node; 37 import org.graalvm.compiler.graph.NodeClass; 38 import org.graalvm.compiler.graph.iterators.NodePredicate; 39 import org.graalvm.compiler.graph.spi.Canonicalizable; 40 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 41 import org.graalvm.compiler.nodeinfo.NodeInfo; 42 import org.graalvm.compiler.nodes.ArithmeticOperation; 43 import org.graalvm.compiler.nodes.ConstantNode; 44 import org.graalvm.compiler.nodes.NodeView; 45 import org.graalvm.compiler.nodes.StructuredGraph; 46 import org.graalvm.compiler.nodes.ValueNode; 47 import org.graalvm.compiler.nodes.ValuePhiNode; 48 import org.graalvm.compiler.nodes.spi.ArithmeticLIRLowerable; 49 import org.graalvm.compiler.nodes.spi.NodeValueMap; 50 51 import jdk.vm.ci.meta.Constant; 52 53 @NodeInfo(cycles = CYCLES_1, size = SIZE_1) 54 public abstract class BinaryArithmeticNode<OP> extends BinaryNode implements ArithmeticOperation, ArithmeticLIRLowerable, Canonicalizable.Binary<ValueNode> { 55 56 @SuppressWarnings("rawtypes") public static final NodeClass<BinaryArithmeticNode> TYPE = NodeClass.create(BinaryArithmeticNode.class); 57 BinaryArithmeticNode(NodeClass<? extends BinaryArithmeticNode<OP>> c, BinaryOp<OP> opForStampComputation, ValueNode x, ValueNode y)58 protected BinaryArithmeticNode(NodeClass<? extends BinaryArithmeticNode<OP>> c, BinaryOp<OP> opForStampComputation, ValueNode x, ValueNode y) { 59 super(c, opForStampComputation.foldStamp(x.stamp(NodeView.DEFAULT), y.stamp(NodeView.DEFAULT)), x, y); 60 } 61 BinaryArithmeticNode(NodeClass<? extends BinaryArithmeticNode<OP>> c, Stamp stamp, ValueNode x, ValueNode y)62 protected BinaryArithmeticNode(NodeClass<? extends BinaryArithmeticNode<OP>> c, Stamp stamp, ValueNode x, ValueNode y) { 63 super(c, stamp, x, y); 64 } 65 getArithmeticOpTable(ValueNode forValue)66 public static ArithmeticOpTable getArithmeticOpTable(ValueNode forValue) { 67 return ArithmeticOpTable.forStamp(forValue.stamp(NodeView.DEFAULT)); 68 } 69 getOp(ArithmeticOpTable table)70 protected abstract BinaryOp<OP> getOp(ArithmeticOpTable table); 71 getOp(ValueNode forX, ValueNode forY)72 protected final BinaryOp<OP> getOp(ValueNode forX, ValueNode forY) { 73 ArithmeticOpTable table = getArithmeticOpTable(forX); 74 assert table.equals(getArithmeticOpTable(forY)); 75 return getOp(table); 76 } 77 78 @Override getArithmeticOp()79 public final BinaryOp<OP> getArithmeticOp() { 80 return getOp(getX(), getY()); 81 } 82 isAssociative()83 public boolean isAssociative() { 84 return getArithmeticOp().isAssociative(); 85 } 86 87 @Override canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY)88 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) { 89 NodeView view = NodeView.from(tool); 90 ValueNode result = tryConstantFold(getOp(forX, forY), forX, forY, stamp(view), view); 91 if (result != null) { 92 return result; 93 } 94 if (forX instanceof ConditionalNode && forY.isConstant() && forX.hasExactlyOneUsage()) { 95 ConditionalNode conditionalNode = (ConditionalNode) forX; 96 BinaryOp<OP> arithmeticOp = getArithmeticOp(); 97 ConstantNode trueConstant = tryConstantFold(arithmeticOp, conditionalNode.trueValue(), forY, this.stamp(view), view); 98 if (trueConstant != null) { 99 ConstantNode falseConstant = tryConstantFold(arithmeticOp, conditionalNode.falseValue(), forY, this.stamp(view), view); 100 if (falseConstant != null) { 101 // @formatter:off 102 /* The arithmetic is folded into a constant on both sides of the conditional. 103 * Example: 104 * (cond ? -5 : 5) + 100 105 * canonicalizes to: 106 * (cond ? 95 : 105) 107 */ 108 // @formatter:on 109 return ConditionalNode.create(conditionalNode.condition, trueConstant, 110 falseConstant, view); 111 } 112 } 113 } 114 return this; 115 } 116 117 @SuppressWarnings("unused") tryConstantFold(BinaryOp<OP> op, ValueNode forX, ValueNode forY, Stamp stamp, NodeView view)118 public static <OP> ConstantNode tryConstantFold(BinaryOp<OP> op, ValueNode forX, ValueNode forY, Stamp stamp, NodeView view) { 119 if (forX.isConstant() && forY.isConstant()) { 120 Constant ret = op.foldConstant(forX.asConstant(), forY.asConstant()); 121 if (ret != null) { 122 return ConstantNode.forPrimitive(stamp, ret); 123 } 124 } 125 return null; 126 } 127 128 @Override foldStamp(Stamp stampX, Stamp stampY)129 public Stamp foldStamp(Stamp stampX, Stamp stampY) { 130 assert stampX.isCompatible(x.stamp(NodeView.DEFAULT)) && stampY.isCompatible(y.stamp(NodeView.DEFAULT)); 131 return getArithmeticOp().foldStamp(stampX, stampY); 132 } 133 add(StructuredGraph graph, ValueNode v1, ValueNode v2, NodeView view)134 public static ValueNode add(StructuredGraph graph, ValueNode v1, ValueNode v2, NodeView view) { 135 return graph.addOrUniqueWithInputs(AddNode.create(v1, v2, view)); 136 } 137 add(ValueNode v1, ValueNode v2, NodeView view)138 public static ValueNode add(ValueNode v1, ValueNode v2, NodeView view) { 139 return AddNode.create(v1, v2, view); 140 } 141 add(ValueNode v1, ValueNode v2)142 public static ValueNode add(ValueNode v1, ValueNode v2) { 143 return add(v1, v2, NodeView.DEFAULT); 144 } 145 mul(StructuredGraph graph, ValueNode v1, ValueNode v2, NodeView view)146 public static ValueNode mul(StructuredGraph graph, ValueNode v1, ValueNode v2, NodeView view) { 147 return graph.addOrUniqueWithInputs(MulNode.create(v1, v2, view)); 148 } 149 mul(ValueNode v1, ValueNode v2, NodeView view)150 public static ValueNode mul(ValueNode v1, ValueNode v2, NodeView view) { 151 return MulNode.create(v1, v2, view); 152 } 153 mul(ValueNode v1, ValueNode v2)154 public static ValueNode mul(ValueNode v1, ValueNode v2) { 155 return mul(v1, v2, NodeView.DEFAULT); 156 } 157 sub(StructuredGraph graph, ValueNode v1, ValueNode v2, NodeView view)158 public static ValueNode sub(StructuredGraph graph, ValueNode v1, ValueNode v2, NodeView view) { 159 return graph.addOrUniqueWithInputs(SubNode.create(v1, v2, view)); 160 } 161 sub(ValueNode v1, ValueNode v2, NodeView view)162 public static ValueNode sub(ValueNode v1, ValueNode v2, NodeView view) { 163 return SubNode.create(v1, v2, view); 164 } 165 sub(ValueNode v1, ValueNode v2)166 public static ValueNode sub(ValueNode v1, ValueNode v2) { 167 return sub(v1, v2, NodeView.DEFAULT); 168 } 169 branchlessMin(ValueNode v1, ValueNode v2, NodeView view)170 public static ValueNode branchlessMin(ValueNode v1, ValueNode v2, NodeView view) { 171 if (v1.isDefaultConstant() && !v2.isDefaultConstant()) { 172 return branchlessMin(v2, v1, view); 173 } 174 int bits = ((IntegerStamp) v1.stamp(view)).getBits(); 175 assert ((IntegerStamp) v2.stamp(view)).getBits() == bits; 176 ValueNode t1 = sub(v1, v2, view); 177 ValueNode t2 = RightShiftNode.create(t1, bits - 1, view); 178 ValueNode t3 = AndNode.create(t1, t2, view); 179 return add(v2, t3, view); 180 } 181 branchlessMax(ValueNode v1, ValueNode v2, NodeView view)182 public static ValueNode branchlessMax(ValueNode v1, ValueNode v2, NodeView view) { 183 if (v1.isDefaultConstant() && !v2.isDefaultConstant()) { 184 return branchlessMax(v2, v1, view); 185 } 186 int bits = ((IntegerStamp) v1.stamp(view)).getBits(); 187 assert ((IntegerStamp) v2.stamp(view)).getBits() == bits; 188 if (v2.isDefaultConstant()) { 189 // prefer a & ~(a>>31) to a - (a & (a>>31)) 190 return AndNode.create(v1, NotNode.create(RightShiftNode.create(v1, bits - 1, view)), view); 191 } else { 192 ValueNode t1 = sub(v1, v2, view); 193 ValueNode t2 = RightShiftNode.create(t1, bits - 1, view); 194 ValueNode t3 = AndNode.create(t1, t2, view); 195 return sub(v1, t3, view); 196 } 197 } 198 199 private enum ReassociateMatch { 200 x, 201 y; 202 getValue(BinaryNode binary)203 public ValueNode getValue(BinaryNode binary) { 204 switch (this) { 205 case x: 206 return binary.getX(); 207 case y: 208 return binary.getY(); 209 default: 210 throw GraalError.shouldNotReachHere(); 211 } 212 } 213 getOtherValue(BinaryNode binary)214 public ValueNode getOtherValue(BinaryNode binary) { 215 switch (this) { 216 case x: 217 return binary.getY(); 218 case y: 219 return binary.getX(); 220 default: 221 throw GraalError.shouldNotReachHere(); 222 } 223 } 224 } 225 findReassociate(BinaryNode binary, NodePredicate criterion)226 private static ReassociateMatch findReassociate(BinaryNode binary, NodePredicate criterion) { 227 boolean resultX = criterion.apply(binary.getX()); 228 boolean resultY = criterion.apply(binary.getY()); 229 if (resultX && !resultY) { 230 return ReassociateMatch.x; 231 } 232 if (!resultX && resultY) { 233 return ReassociateMatch.y; 234 } 235 return null; 236 } 237 238 //@formatter:off 239 /* 240 * In reassociate, complexity comes from the handling of IntegerSub (non commutative) which can 241 * be mixed with IntegerAdd. It first tries to find m1, m2 which match the criterion : 242 * (a o m2) o m1 243 * (m2 o a) o m1 244 * m1 o (a o m2) 245 * m1 o (m2 o a) 246 * It then produces 4 boolean for the -/+ cases: 247 * invertA : should the final expression be like *-a (rather than a+*) 248 * aSub : should the final expression be like a-* (rather than a+*) 249 * invertM1 : should the final expression contain -m1 250 * invertM2 : should the final expression contain -m2 251 * 252 */ 253 //@formatter:on 254 /** 255 * Tries to re-associate values which satisfy the criterion. For example with a constantness 256 * criterion: {@code (a + 2) + 1 => a + (1 + 2)} 257 * <p> 258 * This method accepts only {@linkplain BinaryOp#isAssociative() associative} operations such as 259 * +, -, *, &, | and ^ 260 * 261 * @param forY 262 * @param forX 263 */ reassociate(BinaryArithmeticNode<?> node, NodePredicate criterion, ValueNode forX, ValueNode forY, NodeView view)264 public static ValueNode reassociate(BinaryArithmeticNode<?> node, NodePredicate criterion, ValueNode forX, ValueNode forY, NodeView view) { 265 assert node.getOp(forX, forY).isAssociative(); 266 ReassociateMatch match1 = findReassociate(node, criterion); 267 if (match1 == null) { 268 return node; 269 } 270 ValueNode otherValue = match1.getOtherValue(node); 271 boolean addSub = false; 272 boolean subAdd = false; 273 if (otherValue.getClass() != node.getClass()) { 274 if (node instanceof AddNode && otherValue instanceof SubNode) { 275 addSub = true; 276 } else if (node instanceof SubNode && otherValue instanceof AddNode) { 277 subAdd = true; 278 } else { 279 return node; 280 } 281 } 282 BinaryNode other = (BinaryNode) otherValue; 283 ReassociateMatch match2 = findReassociate(other, criterion); 284 if (match2 == null) { 285 return node; 286 } 287 boolean invertA = false; 288 boolean aSub = false; 289 boolean invertM1 = false; 290 boolean invertM2 = false; 291 if (addSub) { 292 invertM2 = match2 == ReassociateMatch.y; 293 invertA = !invertM2; 294 } else if (subAdd) { 295 invertA = invertM2 = match1 == ReassociateMatch.x; 296 invertM1 = !invertM2; 297 } else if (node instanceof SubNode && other instanceof SubNode) { 298 invertA = match1 == ReassociateMatch.x ^ match2 == ReassociateMatch.x; 299 aSub = match1 == ReassociateMatch.y && match2 == ReassociateMatch.y; 300 invertM1 = match1 == ReassociateMatch.y && match2 == ReassociateMatch.x; 301 invertM2 = match1 == ReassociateMatch.x && match2 == ReassociateMatch.x; 302 } 303 assert !(invertM1 && invertM2) && !(invertA && aSub); 304 ValueNode m1 = match1.getValue(node); 305 ValueNode m2 = match2.getValue(other); 306 ValueNode a = match2.getOtherValue(other); 307 if (node instanceof AddNode || node instanceof SubNode) { 308 ValueNode associated; 309 if (invertM1) { 310 associated = BinaryArithmeticNode.sub(m2, m1, view); 311 } else if (invertM2) { 312 associated = BinaryArithmeticNode.sub(m1, m2, view); 313 } else { 314 associated = BinaryArithmeticNode.add(m1, m2, view); 315 } 316 if (invertA) { 317 return BinaryArithmeticNode.sub(associated, a, view); 318 } 319 if (aSub) { 320 return BinaryArithmeticNode.sub(a, associated, view); 321 } 322 return BinaryArithmeticNode.add(a, associated, view); 323 } else if (node instanceof MulNode) { 324 return BinaryArithmeticNode.mul(a, AddNode.mul(m1, m2, view), view); 325 } else if (node instanceof AndNode) { 326 return new AndNode(a, new AndNode(m1, m2)); 327 } else if (node instanceof OrNode) { 328 return new OrNode(a, new OrNode(m1, m2)); 329 } else if (node instanceof XorNode) { 330 return new XorNode(a, new XorNode(m1, m2)); 331 } else { 332 throw GraalError.shouldNotReachHere(); 333 } 334 } 335 336 /** 337 * Ensure a canonical ordering of inputs for commutative nodes to improve GVN results. Order the 338 * inputs by increasing {@link Node#id} and call {@link Graph#findDuplicate(Node)} on the node 339 * if it's currently in a graph. It's assumed that if there was a constant on the left it's been 340 * moved to the right by other code and that ordering is left alone. 341 * 342 * @return the original node or another node with the same input ordering 343 */ 344 @SuppressWarnings("deprecation") maybeCommuteInputs()345 public BinaryNode maybeCommuteInputs() { 346 assert this instanceof BinaryCommutative; 347 if (!y.isConstant() && (x.isConstant() || x.getId() > y.getId())) { 348 ValueNode tmp = x; 349 x = y; 350 y = tmp; 351 if (graph() != null) { 352 // See if this node already exists 353 BinaryNode duplicate = graph().findDuplicate(this); 354 if (duplicate != null) { 355 return duplicate; 356 } 357 } 358 } 359 return this; 360 } 361 362 /** 363 * Determines if it would be better to swap the inputs in order to produce better assembly code. 364 * First we try to pick a value which is dead after this use. If both values are dead at this 365 * use then we try pick an induction variable phi to encourage the phi to live in a single 366 * register. 367 * 368 * @param nodeValueMap 369 * @return true if inputs should be swapped, false otherwise 370 */ shouldSwapInputs(NodeValueMap nodeValueMap)371 protected boolean shouldSwapInputs(NodeValueMap nodeValueMap) { 372 final boolean xHasOtherUsages = getX().hasUsagesOtherThan(this, nodeValueMap); 373 final boolean yHasOtherUsages = getY().hasUsagesOtherThan(this, nodeValueMap); 374 375 if (!getY().isConstant() && !yHasOtherUsages) { 376 if (xHasOtherUsages == yHasOtherUsages) { 377 return getY() instanceof ValuePhiNode && getY().inputs().contains(this); 378 } else { 379 return true; 380 } 381 } 382 return false; 383 } 384 385 } 386