Line data    Source code

       1             : //===- CmpInstAnalysis.cpp - Utils to help fold compares ---------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file holds routines to help analyse compare instructions
      11             : // and fold them into constants or other compare instructions
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "llvm/Analysis/CmpInstAnalysis.h"
      16             : #include "llvm/IR/Constants.h"
      17             : #include "llvm/IR/Instructions.h"
      18             : #include "llvm/IR/PatternMatch.h"
      19             : 
      20             : using namespace llvm;
      21             : 
      22          24 : unsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) {
      23          24 :   ICmpInst::Predicate Pred = InvertPred ? ICI->getInversePredicate()
      24             :                                         : ICI->getPredicate();
      25             :   switch (Pred) {
      26             :       // False -> 0
      27             :     case ICmpInst::ICMP_UGT: return 1;  // 001
      28             :     case ICmpInst::ICMP_SGT: return 1;  // 001
      29             :     case ICmpInst::ICMP_EQ:  return 2;  // 010
      30             :     case ICmpInst::ICMP_UGE: return 3;  // 011
      31             :     case ICmpInst::ICMP_SGE: return 3;  // 011
      32             :     case ICmpInst::ICMP_ULT: return 4;  // 100
      33             :     case ICmpInst::ICMP_SLT: return 4;  // 100
      34             :     case ICmpInst::ICMP_NE:  return 5;  // 101
      35             :     case ICmpInst::ICMP_ULE: return 6;  // 110
      36             :     case ICmpInst::ICMP_SLE: return 6;  // 110
      37             :       // True -> 7
      38           0 :     default:
      39           0 :       llvm_unreachable("Invalid ICmp predicate!");
      40             :   }
      41             : }
      42             : 
      43          12 : Value *llvm::getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
      44             :                           CmpInst::Predicate &NewICmpPred) {
      45          12 :   switch (Code) {
      46           0 :     default: llvm_unreachable("Illegal ICmp code!");
      47           0 :     case 0: // False.
      48           0 :       return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
      49           0 :     case 1: NewICmpPred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break;
      50           0 :     case 2: NewICmpPred = ICmpInst::ICMP_EQ; break;
      51           3 :     case 3: NewICmpPred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break;
      52           0 :     case 4: NewICmpPred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break;
      53           3 :     case 5: NewICmpPred = ICmpInst::ICMP_NE; break;
      54           6 :     case 6: NewICmpPred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break;
      55           1 :     case 7: // True.
      56           1 :       return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1);
      57             :   }
      58             :   return nullptr;
      59             : }
      60             : 
      61        8129 : bool llvm::PredicatesFoldable(ICmpInst::Predicate p1, ICmpInst::Predicate p2) {
      62        9143 :   return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) ||
      63        9282 :          (CmpInst::isSigned(p1) && ICmpInst::isEquality(p2)) ||
      64         533 :          (CmpInst::isSigned(p2) && ICmpInst::isEquality(p1));
      65             : }
      66             : 
      67      105268 : bool llvm::decomposeBitTestICmp(Value *LHS, Value *RHS,
      68             :                                 CmpInst::Predicate &Pred,
      69             :                                 Value *&X, APInt &Mask, bool LookThruTrunc) {
      70             :   using namespace PatternMatch;
      71             : 
      72             :   const APInt *C;
      73      105268 :   if (!match(RHS, m_APInt(C)))
      74             :     return false;
      75             : 
      76       77553 :   switch (Pred) {
      77             :   default:
      78             :     return false;
      79        2212 :   case ICmpInst::ICMP_SLT:
      80             :     // X < 0 is equivalent to (X & SignMask) != 0.
      81        4424 :     if (!C->isNullValue())
      82             :       return false;
      83        1359 :     Mask = APInt::getSignMask(C->getBitWidth());
      84        1359 :     Pred = ICmpInst::ICMP_NE;
      85        1359 :     break;
      86          18 :   case ICmpInst::ICMP_SLE:
      87             :     // X <= -1 is equivalent to (X & SignMask) != 0.
      88          36 :     if (!C->isAllOnesValue())
      89             :       return false;
      90           1 :     Mask = APInt::getSignMask(C->getBitWidth());
      91           1 :     Pred = ICmpInst::ICMP_NE;
      92           1 :     break;
      93        2276 :   case ICmpInst::ICMP_SGT:
      94             :     // X > -1 is equivalent to (X & SignMask) == 0.
      95        4552 :     if (!C->isAllOnesValue())
      96             :       return false;
      97         402 :     Mask = APInt::getSignMask(C->getBitWidth());
      98         402 :     Pred = ICmpInst::ICMP_EQ;
      99         402 :     break;
     100          34 :   case ICmpInst::ICMP_SGE:
     101             :     // X >= 0 is equivalent to (X & SignMask) == 0.
     102          68 :     if (!C->isNullValue())
     103             :       return false;
     104          28 :     Mask = APInt::getSignMask(C->getBitWidth());
     105          28 :     Pred = ICmpInst::ICMP_EQ;
     106          28 :     break;
     107        3067 :   case ICmpInst::ICMP_ULT:
     108             :     // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0.
     109        3067 :     if (!C->isPowerOf2())
     110             :       return false;
     111        1327 :     Mask = -*C;
     112        1327 :     Pred = ICmpInst::ICMP_EQ;
     113        1327 :     break;
     114          23 :   case ICmpInst::ICMP_ULE:
     115             :     // X <=u 2^n-1 is equivalent to (X & ~(2^n-1)) == 0.
     116          46 :     if (!(*C + 1).isPowerOf2())
     117             :       return false;
     118           2 :     Mask = ~*C;
     119           2 :     Pred = ICmpInst::ICMP_EQ;
     120           2 :     break;
     121        4492 :   case ICmpInst::ICMP_UGT:
     122             :     // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0.
     123        8984 :     if (!(*C + 1).isPowerOf2())
     124             :       return false;
     125        4116 :     Mask = ~*C;
     126        4116 :     Pred = ICmpInst::ICMP_NE;
     127        4116 :     break;
     128           1 :   case ICmpInst::ICMP_UGE:
     129             :     // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0.
     130           1 :     if (!C->isPowerOf2())
     131             :       return false;
     132           1 :     Mask = -*C;
     133           1 :     Pred = ICmpInst::ICMP_NE;
     134           1 :     break;
     135             :   }
     136             : 
     137        7236 :   if (LookThruTrunc && match(LHS, m_Trunc(m_Value(X)))) {
     138         206 :     Mask = Mask.zext(X->getType()->getScalarSizeInBits());
     139             :   } else {
     140        7133 :     X = LHS;
     141             :   }
     142             : 
     143             :   return true;
     144             : }