1 /*
   2  * Copyright (c) 2009, 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.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 }