1 /*
2 * Copyright (c) 2009, 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
24
25 package org.graalvm.compiler.core.common.calc;
26
27 import org.graalvm.compiler.debug.GraalError;
28
29 import jdk.vm.ci.meta.Constant;
30 import jdk.vm.ci.meta.ConstantReflectionProvider;
31 import jdk.vm.ci.meta.JavaConstant;
32 import jdk.vm.ci.meta.PrimitiveConstant;
33
34 /**
35 * Condition codes used in conditionals.
36 */
37 public enum Condition {
38 /**
39 * Equal.
40 */
41 EQ("=="),
42
43 /**
44 * Not equal.
45 */
46 NE("!="),
47
48 /**
49 * Signed less than.
50 */
51 LT("<"),
52
53 /**
54 * Signed less than or equal.
55 */
56 LE("<="),
57
58 /**
59 * Signed greater than.
60 */
61 GT(">"),
62
63 /**
64 * Signed greater than or equal.
65 */
66 GE(">="),
67
68 /**
69 * Unsigned greater than or equal ("above than or equal").
70 */
71 AE("|>=|"),
72
73 /**
74 * Unsigned less than or equal ("below than or equal").
75 */
76 BE("|<=|"),
77
78 /**
79 * Unsigned greater than ("above than").
80 */
81 AT("|>|"),
82
83 /**
84 * Unsigned less than ("below than").
85 */
86 BT("|<|");
87
88 public final String operator;
89
90 Condition(String operator) {
91 this.operator = operator;
92 }
93
94 public boolean check(int left, int right) {
95 switch (this) {
96 case EQ:
97 return left == right;
98 case NE:
99 return left != right;
100 case LT:
101 return left < right;
102 case LE:
103 return left <= right;
104 case GT:
105 return left > right;
106 case GE:
107 return left >= right;
108 case AE:
109 return UnsignedMath.aboveOrEqual(left, right);
110 case BE:
111 return UnsignedMath.belowOrEqual(left, right);
112 case AT:
113 return UnsignedMath.aboveThan(left, right);
114 case BT:
115 return UnsignedMath.belowThan(left, right);
116 }
117 throw new IllegalArgumentException(this.toString());
118 }
119
120 public static final class CanonicalizedCondition {
121 private final CanonicalCondition canonicalCondition;
122 private final boolean mirror;
123 private final boolean negate;
124
125 private CanonicalizedCondition(CanonicalCondition canonicalCondition, boolean mirror, boolean negate) {
126 this.canonicalCondition = canonicalCondition;
127 this.mirror = mirror;
128 this.negate = negate;
129 }
130
131 public CanonicalCondition getCanonicalCondition() {
132 return canonicalCondition;
133 }
134
135 public boolean mustMirror() {
136 return mirror;
137 }
138
139 public boolean mustNegate() {
140 return negate;
141 }
142 }
143
144 public CanonicalizedCondition canonicalize() {
145 CanonicalCondition canonicalCondition;
146 switch (this) {
147 case EQ:
148 case NE:
149 canonicalCondition = CanonicalCondition.EQ;
150 break;
151 case LT:
152 case LE:
153 case GT:
154 case GE:
155 canonicalCondition = CanonicalCondition.LT;
156 break;
157 case BT:
158 case BE:
159 case AT:
160 case AE:
161 canonicalCondition = CanonicalCondition.BT;
162 break;
163 default:
164 throw new IllegalArgumentException(this.toString());
165 }
166 return new CanonicalizedCondition(canonicalCondition, canonicalMirror(), canonicalNegate());
167 }
168
169 /**
170 * Given a condition and its negation, this method returns true for one of the two and false for
171 * the other one. This can be used to keep comparisons in a canonical form.
172 *
173 * @return true if this condition is considered to be the canonical form, false otherwise.
174 */
175 public boolean isCanonical() {
176 switch (this) {
177 case EQ:
178 return true;
179 case NE:
180 return false;
181 case LT:
182 return true;
183 case LE:
184 return false;
185 case GT:
186 return false;
187 case GE:
188 return false;
189 case BT:
190 return true;
191 case BE:
192 return false;
193 case AT:
194 return false;
195 case AE:
196 return false;
197 }
198 throw new IllegalArgumentException(this.toString());
199 }
200
201 /**
202 * Returns true if the condition needs to be mirrored to get to a canonical condition. The
203 * result of the mirroring operation might still need to be negated to achieve a canonical form.
204 */
205 private boolean canonicalMirror() {
206 switch (this) {
207 case EQ:
208 return false;
209 case NE:
210 return false;
211 case LT:
212 return false;
213 case LE:
214 return true;
215 case GT:
216 return true;
217 case GE:
218 return false;
219 case BT:
220 return false;
221 case BE:
222 return true;
223 case AT:
224 return true;
225 case AE:
226 return false;
227 }
228 throw new IllegalArgumentException(this.toString());
229 }
230
231 /**
232 * Returns true if the condition needs to be negated to get to a canonical condition. The result
233 * of the negation might still need to be mirrored to achieve a canonical form.
234 */
235 private boolean canonicalNegate() {
236 switch (this) {
237 case EQ:
238 return false;
239 case NE:
240 return true;
241 case LT:
242 return false;
243 case LE:
244 return true;
245 case GT:
246 return false;
247 case GE:
248 return true;
249 case BT:
250 return false;
251 case BE:
252 return true;
253 case AT:
254 return false;
255 case AE:
256 return true;
257 }
258 throw new IllegalArgumentException(this.toString());
259 }
260
261 /**
262 * Negate this conditional.
263 *
264 * @return the condition that represents the negation
265 */
266 public final Condition negate() {
267 switch (this) {
268 case EQ:
269 return NE;
270 case NE:
271 return EQ;
272 case LT:
273 return GE;
274 case LE:
275 return GT;
276 case GT:
277 return LE;
278 case GE:
279 return LT;
280 case BT:
281 return AE;
282 case BE:
283 return AT;
284 case AT:
285 return BE;
286 case AE:
287 return BT;
288 }
289 throw new IllegalArgumentException(this.toString());
290 }
291
292 public boolean implies(Condition other) {
293 if (other == this) {
294 return true;
295 }
296 switch (this) {
297 case EQ:
298 return other == LE || other == GE || other == BE || other == AE;
299 case NE:
300 return false;
301 case LT:
302 return other == LE || other == NE;
303 case LE:
304 return false;
305 case GT:
306 return other == GE || other == NE;
307 case GE:
308 return false;
309 case BT:
310 return other == BE || other == NE;
311 case BE:
312 return false;
313 case AT:
314 return other == AE || other == NE;
315 case AE:
316 return false;
317 }
318 throw new IllegalArgumentException(this.toString());
319 }
320
321 /**
322 * Mirror this conditional (i.e. commute "a op b" to "b op' a")
323 *
324 * @return the condition representing the equivalent commuted operation
325 */
326 public final Condition mirror() {
327 switch (this) {
328 case EQ:
329 return EQ;
330 case NE:
331 return NE;
332 case LT:
333 return GT;
334 case LE:
335 return GE;
336 case GT:
337 return LT;
338 case GE:
339 return LE;
340 case BT:
341 return AT;
342 case BE:
343 return AE;
344 case AT:
345 return BT;
346 case AE:
347 return BE;
348 }
349 throw new IllegalArgumentException();
350 }
351
352 /**
353 * Returns true if this condition represents an unsigned comparison. EQ and NE are not
354 * considered to be unsigned.
355 */
356 public final boolean isUnsigned() {
357 return this == Condition.BT || this == Condition.BE || this == Condition.AT || this == Condition.AE;
358 }
359
360 /**
361 * Checks if this conditional operation is commutative.
362 *
363 * @return {@code true} if this operation is commutative
364 */
365 public final boolean isCommutative() {
366 return this == EQ || this == NE;
367 }
368
369 /**
370 * Attempts to fold a comparison between two constants and return the result.
371 *
372 * @param lt the constant on the left side of the comparison
373 * @param rt the constant on the right side of the comparison
374 * @param constantReflection needed to compare constants
375 * @return {@link Boolean#TRUE} if the comparison is known to be true, {@link Boolean#FALSE} if
376 * the comparison is known to be false
377 */
378 public boolean foldCondition(JavaConstant lt, JavaConstant rt, ConstantReflectionProvider constantReflection) {
379 assert !lt.getJavaKind().isNumericFloat() && !rt.getJavaKind().isNumericFloat();
380 return foldCondition(lt, rt, constantReflection, false);
381 }
382
383 /**
384 * Attempts to fold a comparison between two constants and return the result.
385 *
386 * @param lt the constant on the left side of the comparison
387 * @param rt the constant on the right side of the comparison
388 * @param constantReflection needed to compare constants
389 * @param unorderedIsTrue true if an undecided float comparison should result in "true"
390 * @return true if the comparison is known to be true, false if the comparison is known to be
391 * false
392 */
393 public boolean foldCondition(Constant lt, Constant rt, ConstantReflectionProvider constantReflection, boolean unorderedIsTrue) {
394 if (lt instanceof PrimitiveConstant) {
395 PrimitiveConstant lp = (PrimitiveConstant) lt;
396 PrimitiveConstant rp = (PrimitiveConstant) rt;
397 return foldCondition(lp, rp, unorderedIsTrue);
398 } else {
399 Boolean equal = constantReflection.constantEquals(lt, rt);
400 if (equal == null) {
401 throw new GraalError("could not fold %s %s %s", lt, this, rt);
402 }
403 switch (this) {
404 case EQ:
405 return equal.booleanValue();
406 case NE:
407 return !equal.booleanValue();
408 default:
409 throw new GraalError("expected condition: %s", this);
410 }
411 }
412 }
413
414 /**
415 * Attempts to fold a comparison between two primitive constants and return the result.
416 *
417 * @param lp the constant on the left side of the comparison
418 * @param rp the constant on the right side of the comparison
419 * @param unorderedIsTrue true if an undecided float comparison should result in "true"
420 * @return true if the comparison is known to be true, false if the comparison is known to be
421 * false
422 */
423 public boolean foldCondition(PrimitiveConstant lp, PrimitiveConstant rp, boolean unorderedIsTrue) {
424 switch (lp.getJavaKind()) {
425 case Boolean:
426 case Byte:
427 case Char:
428 case Short:
429 case Int: {
430 int x = lp.asInt();
431 int y = rp.asInt();
432 switch (this) {
433 case EQ:
434 return x == y;
435 case NE:
436 return x != y;
437 case LT:
438 return x < y;
439 case LE:
440 return x <= y;
441 case GT:
442 return x > y;
443 case GE:
444 return x >= y;
445 case AE:
446 return UnsignedMath.aboveOrEqual(x, y);
447 case BE:
448 return UnsignedMath.belowOrEqual(x, y);
449 case AT:
450 return UnsignedMath.aboveThan(x, y);
451 case BT:
452 return UnsignedMath.belowThan(x, y);
453 default:
454 throw new GraalError("expected condition: %s", this);
455 }
456 }
457 case Long: {
458 long x = lp.asLong();
459 long y = rp.asLong();
460 switch (this) {
461 case EQ:
462 return x == y;
463 case NE:
464 return x != y;
465 case LT:
466 return x < y;
467 case LE:
468 return x <= y;
469 case GT:
470 return x > y;
471 case GE:
472 return x >= y;
473 case AE:
474 return UnsignedMath.aboveOrEqual(x, y);
475 case BE:
476 return UnsignedMath.belowOrEqual(x, y);
477 case AT:
478 return UnsignedMath.aboveThan(x, y);
479 case BT:
480 return UnsignedMath.belowThan(x, y);
481 default:
482 throw new GraalError("expected condition: %s", this);
483 }
484 }
485 case Float: {
486 float x = lp.asFloat();
487 float y = rp.asFloat();
488 if (Float.isNaN(x) || Float.isNaN(y)) {
489 return unorderedIsTrue;
490 }
491 switch (this) {
492 case EQ:
493 return x == y;
494 case NE:
495 return x != y;
496 case LT:
497 return x < y;
498 case LE:
499 return x <= y;
500 case GT:
501 return x > y;
502 case GE:
503 return x >= y;
504 default:
505 throw new GraalError("expected condition: %s", this);
506 }
507 }
508 case Double: {
509 double x = lp.asDouble();
510 double y = rp.asDouble();
511 if (Double.isNaN(x) || Double.isNaN(y)) {
512 return unorderedIsTrue;
513 }
514 switch (this) {
515 case EQ:
516 return x == y;
517 case NE:
518 return x != y;
519 case LT:
520 return x < y;
521 case LE:
522 return x <= y;
523 case GT:
524 return x > y;
525 case GE:
526 return x >= y;
527 default:
528 throw new GraalError("expected condition: %s", this);
529 }
530 }
531 default:
532 throw new GraalError("expected value kind %s while folding condition: %s", lp.getJavaKind(), this);
533 }
534 }
535
536 public Condition join(Condition other) {
537 if (other == this) {
538 return this;
539 }
540 switch (this) {
541 case EQ:
542 if (other == LE || other == GE || other == BE || other == AE) {
543 return EQ;
544 } else {
545 return null;
546 }
547 case NE:
548 if (other == LT || other == GT || other == BT || other == AT) {
549 return other;
550 } else if (other == LE) {
551 return LT;
552 } else if (other == GE) {
553 return GT;
554 } else if (other == BE) {
555 return BT;
556 } else if (other == AE) {
557 return AT;
558 } else {
559 return null;
560 }
561 case LE:
562 if (other == GE || other == EQ) {
563 return EQ;
564 } else if (other == NE || other == LT) {
565 return LT;
566 } else {
567 return null;
568 }
569 case LT:
570 if (other == NE || other == LE) {
571 return LT;
572 } else {
573 return null;
574 }
575 case GE:
576 if (other == LE || other == EQ) {
577 return EQ;
578 } else if (other == NE || other == GT) {
579 return GT;
580 } else {
581 return null;
582 }
583 case GT:
584 if (other == NE || other == GE) {
585 return GT;
586 } else {
587 return null;
588 }
589 case BE:
590 if (other == AE || other == EQ) {
591 return EQ;
592 } else if (other == NE || other == BT) {
593 return BT;
594 } else {
595 return null;
596 }
597 case BT:
598 if (other == NE || other == BE) {
599 return BT;
600 } else {
601 return null;
602 }
603 case AE:
604 if (other == BE || other == EQ) {
605 return EQ;
606 } else if (other == NE || other == AT) {
607 return AT;
608 } else {
609 return null;
610 }
611 case AT:
612 if (other == NE || other == AE) {
613 return AT;
614 } else {
615 return null;
616 }
617 }
618 throw new IllegalArgumentException(this.toString());
619 }
620
621 public Condition meet(Condition other) {
622 if (other == this) {
623 return this;
624 }
625 switch (this) {
626 case EQ:
627 if (other == LE || other == GE || other == BE || other == AE) {
628 return other;
629 } else if (other == LT) {
630 return LE;
631 } else if (other == GT) {
632 return GE;
633 } else if (other == BT) {
634 return BE;
635 } else if (other == AT) {
636 return AE;
637 } else {
638 return null;
639 }
640 case NE:
641 if (other == LT || other == GT || other == BT || other == AT) {
642 return NE;
643 } else {
644 return null;
645 }
646 case LE:
647 if (other == EQ || other == LT) {
648 return LE;
649 } else {
650 return null;
651 }
652 case LT:
653 if (other == EQ || other == LE) {
654 return LE;
655 } else if (other == NE || other == GT) {
656 return NE;
657 } else {
658 return null;
659 }
660 case GE:
661 if (other == EQ || other == GT) {
662 return GE;
663 } else {
664 return null;
665 }
666 case GT:
667 if (other == EQ || other == GE) {
668 return GE;
669 } else if (other == NE || other == LT) {
670 return NE;
671 } else {
672 return null;
673 }
674 case BE:
675 if (other == EQ || other == BT) {
676 return BE;
677 } else {
678 return null;
679 }
680 case BT:
681 if (other == EQ || other == BE) {
682 return BE;
683 } else if (other == NE || other == AT) {
684 return NE;
685 } else {
686 return null;
687 }
688 case AE:
689 if (other == EQ || other == AT) {
690 return AE;
691 } else {
692 return null;
693 }
694 case AT:
695 if (other == EQ || other == AE) {
696 return AE;
697 } else if (other == NE || other == BT) {
698 return NE;
699 } else {
700 return null;
701 }
702 }
703 throw new IllegalArgumentException(this.toString());
704 }
705 }