1 /*
2 * Copyright (c) 2014, 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_4;
27
28 import java.util.function.BiFunction;
29
30 import org.graalvm.compiler.core.common.type.IntegerStamp;
31 import org.graalvm.compiler.core.common.type.Stamp;
32 import org.graalvm.compiler.core.common.type.StampFactory;
33 import org.graalvm.compiler.graph.NodeClass;
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.ValueNode;
39 import org.graalvm.compiler.nodes.calc.BinaryNode;
40 import org.graalvm.compiler.nodes.spi.ArithmeticLIRLowerable;
41 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool;
42
43 import jdk.vm.ci.meta.JavaKind;
44 import jdk.vm.ci.meta.Value;
45
46 @NodeInfo(shortName = "|*H|", cycles = CYCLES_4, cyclesRationale = "mul + mov", size = SIZE_4)
47 public final class UnsignedMulHighNode extends BinaryNode implements ArithmeticLIRLowerable {
48
49 public static final NodeClass<UnsignedMulHighNode> TYPE = NodeClass.create(UnsignedMulHighNode.class);
50
51 public UnsignedMulHighNode(ValueNode x, ValueNode y) {
52 this((IntegerStamp) x.stamp().unrestricted(), x, y);
53 }
54
55 public UnsignedMulHighNode(IntegerStamp stamp, ValueNode x, ValueNode y) {
56 super(TYPE, stamp, x, y);
57 }
58
59 private static long[] getUnsignedExtremes(IntegerStamp stamp) {
60 if (stamp.lowerBound() < 0 && stamp.upperBound() >= 0) {
61 /*
62 * If -1 and 0 are both in the signed range, then we can't say anything about the
63 * unsigned range, so we have to return [0, MAX_UNSIGNED].
64 */
65 return new long[]{0, -1L};
66 } else {
67 return new long[]{stamp.lowerBound(), stamp.upperBound()};
68 }
69 }
70
71 /**
72 * Determines the minimum and maximum result of this node for the given inputs and returns the
73 * result of the given BiFunction on the minimum and maximum values. Note that the minima and
74 * maxima are calculated using signed min/max functions, while the values themselves are
75 * unsigned.
76 */
77 private <T> T processExtremes(Stamp forX, Stamp forY, BiFunction<Long, Long, T> op) {
78 IntegerStamp xStamp = (IntegerStamp) forX;
79 IntegerStamp yStamp = (IntegerStamp) forY;
80
81 JavaKind kind = getStackKind();
82 assert kind == JavaKind.Int || kind == JavaKind.Long;
83 long[] xExtremes = getUnsignedExtremes(xStamp);
84 long[] yExtremes = getUnsignedExtremes(yStamp);
85 long min = Long.MAX_VALUE;
86 long max = Long.MIN_VALUE;
87 for (long a : xExtremes) {
88 for (long b : yExtremes) {
89 long result = kind == JavaKind.Int ? multiplyHighUnsigned((int) a, (int) b) : multiplyHighUnsigned(a, b);
90 min = Math.min(min, result);
91 max = Math.max(max, result);
92 }
93 }
94 return op.apply(min, max);
95 }
96
97 @SuppressWarnings("cast")
98 @Override
99 public Stamp foldStamp(Stamp stampX, Stamp stampY) {
100 // if min is negative, then the value can reach into the unsigned range
101 return processExtremes(stampX, stampY, (min, max) -> (min == (long) max || min >= 0) ? StampFactory.forInteger(getStackKind(), min, max) : StampFactory.forKind(getStackKind()));
102 }
103
104 @SuppressWarnings("cast")
105 @Override
106 public ValueNode canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) {
107 return processExtremes(forX.stamp(), forY.stamp(), (min, max) -> min == (long) max ? ConstantNode.forIntegerKind(getStackKind(), min) : this);
108 }
109
110 @Override
111 public void generate(NodeLIRBuilderTool nodeValueMap, ArithmeticLIRGeneratorTool gen) {
112 Value a = nodeValueMap.operand(getX());
113 Value b = nodeValueMap.operand(getY());
114 nodeValueMap.setResult(this, gen.emitUMulHigh(a, b));
115 }
116
117 public static int multiplyHighUnsigned(int x, int y) {
118 long xl = x & 0xFFFFFFFFL;
119 long yl = y & 0xFFFFFFFFL;
120 long r = xl * yl;
121 return (int) (r >> 32);
122 }
123
124 public static long multiplyHighUnsigned(long x, long y) {
125 // Checkstyle: stop
126 long x0, y0, z0;
127 long x1, y1, z1, z2, t;
128 // Checkstyle: resume
129
130 x0 = x & 0xFFFFFFFFL;
131 x1 = x >>> 32;
132
133 y0 = y & 0xFFFFFFFFL;
134 y1 = y >>> 32;
135
136 z0 = x0 * y0;
137 t = x1 * y0 + (z0 >>> 32);
138 z1 = t & 0xFFFFFFFFL;
139 z2 = t >>> 32;
140 z1 += x0 * y1;
141
142 return x1 * y1 + z2 + (z1 >>> 32);
143 }
144 }