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.core.common.type;
24
25 import static jdk.vm.ci.meta.MetaUtil.getSimpleName;
26
27 import java.util.Arrays;
28 import java.util.Objects;
29 import java.util.function.Function;
30
31 import org.graalvm.compiler.core.common.calc.FloatConvert;
32 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Add;
33 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.And;
34 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Div;
35 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Mul;
36 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Or;
37 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Rem;
38 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Sub;
39 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp.Xor;
40 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp.Narrow;
41 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp.SignExtend;
42 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp.ZeroExtend;
43 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp.Shl;
44 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp.Shr;
45 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp.UShr;
46 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp.Abs;
47 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp.Neg;
48 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp.Not;
49 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp.Sqrt;
50 import org.graalvm.util.CollectionsUtil;
51
52 import jdk.vm.ci.meta.Constant;
53 import jdk.vm.ci.meta.JavaKind;
54
55 /**
56 * Information about arithmetic operations.
57 */
58 public final class ArithmeticOpTable {
59
60 private final UnaryOp<Neg> neg;
61 private final BinaryOp<Add> add;
62 private final BinaryOp<Sub> sub;
63
64 private final BinaryOp<Mul> mul;
65 private final BinaryOp<Div> div;
66 private final BinaryOp<Rem> rem;
67
68 private final UnaryOp<Not> not;
69 private final BinaryOp<And> and;
70 private final BinaryOp<Or> or;
71 private final BinaryOp<Xor> xor;
72
73 private final ShiftOp<Shl> shl;
74 private final ShiftOp<Shr> shr;
75 private final ShiftOp<UShr> ushr;
76
77 private final UnaryOp<Abs> abs;
78 private final UnaryOp<Sqrt> sqrt;
79
80 private final IntegerConvertOp<ZeroExtend> zeroExtend;
81 private final IntegerConvertOp<SignExtend> signExtend;
82 private final IntegerConvertOp<Narrow> narrow;
83
84 private final FloatConvertOp[] floatConvert;
85 private final int hash;
86
87 public static ArithmeticOpTable forStamp(Stamp s) {
88 if (s instanceof ArithmeticStamp) {
89 return ((ArithmeticStamp) s).getOps();
90 } else {
91 return EMPTY;
92 }
93 }
94
95 public static final ArithmeticOpTable EMPTY = new ArithmeticOpTable(null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null);
96
97 public interface ArithmeticOpWrapper {
98
99 <OP> UnaryOp<OP> wrapUnaryOp(UnaryOp<OP> op);
100
101 <OP> BinaryOp<OP> wrapBinaryOp(BinaryOp<OP> op);
102
103 <OP> ShiftOp<OP> wrapShiftOp(ShiftOp<OP> op);
104
105 <OP> IntegerConvertOp<OP> wrapIntegerConvertOp(IntegerConvertOp<OP> op);
106
107 FloatConvertOp wrapFloatConvertOp(FloatConvertOp op);
108 }
109
110 private static <T> T wrapIfNonNull(Function<T, T> wrapper, T obj) {
111 if (obj == null) {
112 return null;
113 } else {
114 return wrapper.apply(obj);
115 }
116 }
117
118 public static ArithmeticOpTable wrap(ArithmeticOpWrapper wrapper, ArithmeticOpTable inner) {
119 UnaryOp<Neg> neg = wrapIfNonNull(wrapper::wrapUnaryOp, inner.getNeg());
120 BinaryOp<Add> add = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getAdd());
121 BinaryOp<Sub> sub = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getSub());
122
123 BinaryOp<Mul> mul = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getMul());
124 BinaryOp<Div> div = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getDiv());
125 BinaryOp<Rem> rem = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getRem());
126
127 UnaryOp<Not> not = wrapIfNonNull(wrapper::wrapUnaryOp, inner.getNot());
128 BinaryOp<And> and = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getAnd());
129 BinaryOp<Or> or = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getOr());
130 BinaryOp<Xor> xor = wrapIfNonNull(wrapper::wrapBinaryOp, inner.getXor());
131
132 ShiftOp<Shl> shl = wrapIfNonNull(wrapper::wrapShiftOp, inner.getShl());
133 ShiftOp<Shr> shr = wrapIfNonNull(wrapper::wrapShiftOp, inner.getShr());
134 ShiftOp<UShr> ushr = wrapIfNonNull(wrapper::wrapShiftOp, inner.getUShr());
135
136 UnaryOp<Abs> abs = wrapIfNonNull(wrapper::wrapUnaryOp, inner.getAbs());
137 UnaryOp<Sqrt> sqrt = wrapIfNonNull(wrapper::wrapUnaryOp, inner.getSqrt());
138
139 IntegerConvertOp<ZeroExtend> zeroExtend = wrapIfNonNull(wrapper::wrapIntegerConvertOp, inner.getZeroExtend());
140 IntegerConvertOp<SignExtend> signExtend = wrapIfNonNull(wrapper::wrapIntegerConvertOp, inner.getSignExtend());
141 IntegerConvertOp<Narrow> narrow = wrapIfNonNull(wrapper::wrapIntegerConvertOp, inner.getNarrow());
142
143 FloatConvertOp[] floatConvert = CollectionsUtil.filterAndMapToArray(inner.floatConvert, Objects::nonNull, wrapper::wrapFloatConvertOp, FloatConvertOp[]::new);
144 return new ArithmeticOpTable(neg, add, sub, mul, div, rem, not, and, or, xor, shl, shr, ushr, abs, sqrt, zeroExtend, signExtend, narrow, floatConvert);
145 }
146
147 protected ArithmeticOpTable(UnaryOp<Neg> neg, BinaryOp<Add> add, BinaryOp<Sub> sub, BinaryOp<Mul> mul, BinaryOp<Div> div, BinaryOp<Rem> rem, UnaryOp<Not> not, BinaryOp<And> and, BinaryOp<Or> or,
148 BinaryOp<Xor> xor, ShiftOp<Shl> shl, ShiftOp<Shr> shr, ShiftOp<UShr> ushr, UnaryOp<Abs> abs, UnaryOp<Sqrt> sqrt, IntegerConvertOp<ZeroExtend> zeroExtend,
149 IntegerConvertOp<SignExtend> signExtend, IntegerConvertOp<Narrow> narrow, FloatConvertOp... floatConvert) {
150 this.neg = neg;
151 this.add = add;
152 this.sub = sub;
153 this.mul = mul;
154 this.div = div;
155 this.rem = rem;
156 this.not = not;
157 this.and = and;
158 this.or = or;
159 this.xor = xor;
160 this.shl = shl;
161 this.shr = shr;
162 this.ushr = ushr;
163 this.abs = abs;
164 this.sqrt = sqrt;
165 this.zeroExtend = zeroExtend;
166 this.signExtend = signExtend;
167 this.narrow = narrow;
168 this.floatConvert = new FloatConvertOp[FloatConvert.values().length];
169 for (FloatConvertOp op : floatConvert) {
170 this.floatConvert[op.getFloatConvert().ordinal()] = op;
171 }
172
173 this.hash = Objects.hash(neg, add, sub, mul, div, rem, not, and, or, xor, shl, shr, ushr, abs, sqrt, zeroExtend, signExtend, narrow);
174 }
175
176 @Override
177 public int hashCode() {
178 return hash;
179 }
180
181 /**
182 * Describes the unary negation operation.
183 */
184 public UnaryOp<Neg> getNeg() {
185 return neg;
186 }
187
188 /**
189 * Describes the addition operation.
190 */
191 public BinaryOp<Add> getAdd() {
192 return add;
193 }
194
195 /**
196 * Describes the subtraction operation.
197 */
198 public BinaryOp<Sub> getSub() {
199 return sub;
200 }
201
202 /**
203 * Describes the multiplication operation.
204 */
205 public BinaryOp<Mul> getMul() {
206 return mul;
207 }
208
209 /**
210 * Describes the division operation.
211 */
212 public BinaryOp<Div> getDiv() {
213 return div;
214 }
215
216 /**
217 * Describes the remainder operation.
218 */
219 public BinaryOp<Rem> getRem() {
220 return rem;
221 }
222
223 /**
224 * Describes the bitwise not operation.
225 */
226 public UnaryOp<Not> getNot() {
227 return not;
228 }
229
230 /**
231 * Describes the bitwise and operation.
232 */
233 public BinaryOp<And> getAnd() {
234 return and;
235 }
236
237 /**
238 * Describes the bitwise or operation.
239 */
240 public BinaryOp<Or> getOr() {
241 return or;
242 }
243
244 /**
245 * Describes the bitwise xor operation.
246 */
247 public BinaryOp<Xor> getXor() {
248 return xor;
249 }
250
251 /**
252 * Describes the shift left operation.
253 */
254 public ShiftOp<Shl> getShl() {
255 return shl;
256 }
257
258 /**
259 * Describes the signed shift right operation.
260 */
261 public ShiftOp<Shr> getShr() {
262 return shr;
263 }
264
265 /**
266 * Describes the unsigned shift right operation.
267 */
268 public ShiftOp<UShr> getUShr() {
269 return ushr;
270 }
271
272 /**
273 * Describes the absolute value operation.
274 */
275 public UnaryOp<Abs> getAbs() {
276 return abs;
277 }
278
279 /**
280 * Describes the square root operation.
281 */
282 public UnaryOp<Sqrt> getSqrt() {
283 return sqrt;
284 }
285
286 /**
287 * Describes the zero extend conversion.
288 */
289 public IntegerConvertOp<ZeroExtend> getZeroExtend() {
290 return zeroExtend;
291 }
292
293 /**
294 * Describes the sign extend conversion.
295 */
296 public IntegerConvertOp<SignExtend> getSignExtend() {
297 return signExtend;
298 }
299
300 /**
301 * Describes the narrowing conversion.
302 */
303 public IntegerConvertOp<Narrow> getNarrow() {
304 return narrow;
305 }
306
307 /**
308 * Describes integer/float/double conversions.
309 */
310 public FloatConvertOp getFloatConvert(FloatConvert op) {
311 return floatConvert[op.ordinal()];
312 }
313
314 public static String toString(Op... ops) {
315 return CollectionsUtil.mapAndJoin(ops, o -> o == null ? "null" : o.operator + "{" + getSimpleName(o.getClass(), false) + "}", ",");
316 }
317
318 private boolean opsEquals(ArithmeticOpTable that) {
319 // @formatter:off
320 return Objects.equals(neg, that.neg) &&
321 Objects.equals(add, that.add) &&
322 Objects.equals(sub, that.sub) &&
323 Objects.equals(mul, that.mul) &&
324 Objects.equals(div, that.div) &&
325 Objects.equals(rem, that.rem) &&
326 Objects.equals(not, that.not) &&
327 Objects.equals(and, that.and) &&
328 Objects.equals(or, that.or) &&
329 Objects.equals(xor, that.xor) &&
330 Objects.equals(shl, that.shl) &&
331 Objects.equals(shr, that.shr) &&
332 Objects.equals(ushr, that.ushr) &&
333 Objects.equals(abs, that.abs) &&
334 Objects.equals(sqrt, that.sqrt) &&
335 Objects.equals(zeroExtend, that.zeroExtend) &&
336 Objects.equals(signExtend, that.signExtend) &&
337 Objects.equals(narrow, that.narrow);
338 // @formatter:on
339 }
340
341 @Override
342 public boolean equals(Object obj) {
343 if (this == obj) {
344 return true;
345 }
346 if (obj == null) {
347 return false;
348 }
349 if (getClass() != obj.getClass()) {
350 return false;
351 }
352 ArithmeticOpTable that = (ArithmeticOpTable) obj;
353 if (opsEquals(that)) {
354 if (Arrays.equals(this.floatConvert, that.floatConvert)) {
355 return true;
356 }
357 }
358 return false;
359 }
360
361 @Override
362 public String toString() {
363 return getClass().getSimpleName() + "[" + toString(neg, add, sub, mul, div, rem, not, and, or, xor, shl, shr, ushr, abs, sqrt, zeroExtend, signExtend, narrow) + ",floatConvert[" +
364 toString(floatConvert) + "]]";
365 }
366
367 public abstract static class Op {
368
369 private final String operator;
370
371 protected Op(String operator) {
372 this.operator = operator;
373 }
374
375 @Override
376 public String toString() {
377 return operator;
378 }
379
380 @Override
381 public int hashCode() {
382 return operator.hashCode();
383 }
384
385 @Override
386 public boolean equals(Object obj) {
387 if (this == obj) {
388 return true;
389 }
390 if (obj == null) {
391 return false;
392 }
393 if (getClass() != obj.getClass()) {
394 return false;
395 }
396 Op that = (Op) obj;
397 if (operator.equals(that.operator)) {
398 return true;
399 }
400 return true;
401 }
402 }
403
404 /**
405 * Describes a unary arithmetic operation.
406 */
407 public abstract static class UnaryOp<T> extends Op {
408
409 public abstract static class Neg extends UnaryOp<Neg> {
410
411 protected Neg() {
412 super("-");
413 }
414 }
415
416 public abstract static class Not extends UnaryOp<Not> {
417
418 protected Not() {
419 super("~");
420 }
421 }
422
423 public abstract static class Abs extends UnaryOp<Abs> {
424
425 protected Abs() {
426 super("ABS");
427 }
428 }
429
430 public abstract static class Sqrt extends UnaryOp<Sqrt> {
431
432 protected Sqrt() {
433 super("SQRT");
434 }
435 }
436
437 protected UnaryOp(String operation) {
438 super(operation);
439 }
440
441 /**
442 * Apply the operation to a {@link Constant}.
443 */
444 public abstract Constant foldConstant(Constant value);
445
446 /**
447 * Apply the operation to a {@link Stamp}.
448 */
449 public abstract Stamp foldStamp(Stamp stamp);
450
451 public UnaryOp<T> unwrap() {
452 return this;
453 }
454 }
455
456 /**
457 * Describes a binary arithmetic operation.
458 */
459 public abstract static class BinaryOp<T> extends Op {
460
461 public abstract static class Add extends BinaryOp<Add> {
462
463 protected Add(boolean associative, boolean commutative) {
464 super("+", associative, commutative);
465 }
466 }
467
468 public abstract static class Sub extends BinaryOp<Sub> {
469
470 protected Sub(boolean associative, boolean commutative) {
471 super("-", associative, commutative);
472 }
473 }
474
475 public abstract static class Mul extends BinaryOp<Mul> {
476
477 protected Mul(boolean associative, boolean commutative) {
478 super("*", associative, commutative);
479 }
480 }
481
482 public abstract static class Div extends BinaryOp<Div> {
483
484 protected Div(boolean associative, boolean commutative) {
485 super("/", associative, commutative);
486 }
487 }
488
489 public abstract static class Rem extends BinaryOp<Rem> {
490
491 protected Rem(boolean associative, boolean commutative) {
492 super("%", associative, commutative);
493 }
494 }
495
496 public abstract static class And extends BinaryOp<And> {
497
498 protected And(boolean associative, boolean commutative) {
499 super("&", associative, commutative);
500 }
501 }
502
503 public abstract static class Or extends BinaryOp<Or> {
504
505 protected Or(boolean associative, boolean commutative) {
506 super("|", associative, commutative);
507 }
508 }
509
510 public abstract static class Xor extends BinaryOp<Xor> {
511
512 protected Xor(boolean associative, boolean commutative) {
513 super("^", associative, commutative);
514 }
515 }
516
517 private final boolean associative;
518 private final boolean commutative;
519
520 protected BinaryOp(String operation, boolean associative, boolean commutative) {
521 super(operation);
522 this.associative = associative;
523 this.commutative = commutative;
524 }
525
526 /**
527 * Apply the operation to two {@linkplain Constant Constants}.
528 */
529 public abstract Constant foldConstant(Constant a, Constant b);
530
531 /**
532 * Apply the operation to two {@linkplain Stamp Stamps}.
533 */
534 public abstract Stamp foldStamp(Stamp a, Stamp b);
535
536 /**
537 * Checks whether this operation is associative. An operation is associative when
538 * {@code (a . b) . c == a . (b . c)} for all a, b, c. Note that you still have to be
539 * careful with inverses. For example the integer subtraction operation will report
540 * {@code true} here, since you can still reassociate as long as the correct negations are
541 * inserted.
542 */
543 public final boolean isAssociative() {
544 return associative;
545 }
546
547 /**
548 * Checks whether this operation is commutative. An operation is commutative when
549 * {@code a . b == b . a} for all a, b.
550 */
551 public final boolean isCommutative() {
552 return commutative;
553 }
554
555 /**
556 * Check whether a {@link Constant} is a neutral element for this operation. A neutral
557 * element is any element {@code n} where {@code a . n == a} for all a.
558 *
559 * @param n the {@link Constant} that should be tested
560 * @return true iff for all {@code a}: {@code a . n == a}
561 */
562 public boolean isNeutral(Constant n) {
563 return false;
564 }
565
566 /**
567 * Check whether this operation has a zero {@code z == a . a} for each a. Examples of
568 * operations having such an element are subtraction and exclusive-or. Note that this may be
569 * different from the numbers tested by {@link #isNeutral}.
570 *
571 * @param stamp a {@link Stamp}
572 * @return a unique {@code z} such that {@code z == a . a} for each {@code a} in
573 * {@code stamp} if it exists, otherwise {@code null}
574 */
575 public Constant getZero(Stamp stamp) {
576 return null;
577 }
578
579 public BinaryOp<T> unwrap() {
580 return this;
581 }
582
583 @Override
584 public int hashCode() {
585 final int prime = 31;
586 int result = super.hashCode();
587 result = prime * result + (associative ? 1231 : 1237);
588 result = prime * result + (commutative ? 1231 : 1237);
589 return result;
590 }
591
592 @Override
593 public boolean equals(Object obj) {
594 if (this == obj) {
595 return true;
596 }
597 if (!super.equals(obj)) {
598 return false;
599 }
600 if (getClass() != obj.getClass()) {
601 return false;
602 }
603 BinaryOp<?> that = (BinaryOp<?>) obj;
604 if (associative != that.associative) {
605 return false;
606 }
607 if (commutative != that.commutative) {
608 return false;
609 }
610 return true;
611 }
612
613 @Override
614 public String toString() {
615 if (associative) {
616 if (commutative) {
617 return super.toString() + "[AC]";
618 } else {
619 return super.toString() + "[A]";
620 }
621 } else if (commutative) {
622 return super.toString() + "[C]";
623 }
624 return super.toString();
625 }
626 }
627
628 /**
629 * Describes a shift operation. The right argument of a shift operation always has kind
630 * {@link JavaKind#Int}.
631 */
632 public abstract static class ShiftOp<OP> extends Op {
633
634 public abstract static class Shl extends ShiftOp<Shl> {
635
636 public Shl() {
637 super("<<");
638 }
639 }
640
641 public abstract static class Shr extends ShiftOp<Shr> {
642
643 public Shr() {
644 super(">>");
645 }
646 }
647
648 public abstract static class UShr extends ShiftOp<UShr> {
649
650 public UShr() {
651 super(">>>");
652 }
653 }
654
655 protected ShiftOp(String operation) {
656 super(operation);
657 }
658
659 /**
660 * Apply the shift to a constant.
661 */
662 public abstract Constant foldConstant(Constant c, int amount);
663
664 /**
665 * Apply the shift to a stamp.
666 */
667 public abstract Stamp foldStamp(Stamp s, IntegerStamp amount);
668
669 /**
670 * Get the shift amount mask for a given result stamp.
671 */
672 public abstract int getShiftAmountMask(Stamp s);
673 }
674
675 public abstract static class FloatConvertOp extends UnaryOp<FloatConvertOp> {
676
677 private final FloatConvert op;
678
679 protected FloatConvertOp(FloatConvert op) {
680 super(op.name());
681 this.op = op;
682 }
683
684 public FloatConvert getFloatConvert() {
685 return op;
686 }
687
688 @Override
689 public FloatConvertOp unwrap() {
690 return this;
691 }
692
693 @Override
694 public int hashCode() {
695 final int prime = 31;
696 return prime * super.hashCode() + op.hashCode();
697 }
698
699 @Override
700 public boolean equals(Object obj) {
701 if (this == obj) {
702 return true;
703 }
704 if (!super.equals(obj)) {
705 return false;
706 }
707 if (getClass() != obj.getClass()) {
708 return false;
709 }
710 FloatConvertOp that = (FloatConvertOp) obj;
711 if (op != that.op) {
712 return false;
713 }
714 return true;
715 }
716 }
717
718 public abstract static class IntegerConvertOp<T> extends Op {
719
720 public abstract static class ZeroExtend extends IntegerConvertOp<ZeroExtend> {
721
722 protected ZeroExtend() {
723 super("ZeroExtend");
724 }
725 }
726
727 public abstract static class SignExtend extends IntegerConvertOp<SignExtend> {
728
729 protected SignExtend() {
730 super("SignExtend");
731 }
732 }
733
734 public abstract static class Narrow extends IntegerConvertOp<Narrow> {
735
736 protected Narrow() {
737 super("Narrow");
738 }
739
740 @Override
741 public Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp) {
742 return null;
743 }
744 }
745
746 protected IntegerConvertOp(String op) {
747 super(op);
748 }
749
750 public abstract Constant foldConstant(int inputBits, int resultBits, Constant value);
751
752 public abstract Stamp foldStamp(int inputBits, int resultBits, Stamp stamp);
753
754 public IntegerConvertOp<T> unwrap() {
755 return this;
756 }
757
758 /**
759 * Computes the stamp of the input for the given output stamp.
760 */
761 public abstract Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp);
762 }
763 }