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 unsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) { 23 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 default: 39 llvm_unreachable("Invalid ICmp predicate!"); 40 } 41 } 42 43 Value *llvm::getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, 44 CmpInst::Predicate &NewICmpPred) { 45 switch (Code) { 46 default: llvm_unreachable("Illegal ICmp code!"); 47 case 0: // False. 48 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 49 case 1: NewICmpPred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break; 50 case 2: NewICmpPred = ICmpInst::ICMP_EQ; break; 51 case 3: NewICmpPred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break; 52 case 4: NewICmpPred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break; 53 case 5: NewICmpPred = ICmpInst::ICMP_NE; break; 54 case 6: NewICmpPred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break; 55 case 7: // True. 56 return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1); 57 } 58 return nullptr; 59 } 60 61 bool llvm::PredicatesFoldable(ICmpInst::Predicate p1, ICmpInst::Predicate p2) { 62 return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) || 63 (CmpInst::isSigned(p1) && ICmpInst::isEquality(p2)) || 64 (CmpInst::isSigned(p2) && ICmpInst::isEquality(p1)); 65 } 66 67 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 if (!match(RHS, m_APInt(C))) 74 return false; 75 76 switch (Pred) { 77 default: 78 return false; 79 case ICmpInst::ICMP_SLT: 80 // X < 0 is equivalent to (X & SignMask) != 0. 81 if (!C->isNullValue()) 82 return false; 83 Mask = APInt::getSignMask(C->getBitWidth()); 84 Pred = ICmpInst::ICMP_NE; 85 break; 86 case ICmpInst::ICMP_SLE: 87 // X <= -1 is equivalent to (X & SignMask) != 0. 88 if (!C->isAllOnesValue()) 89 return false; 90 Mask = APInt::getSignMask(C->getBitWidth()); 91 Pred = ICmpInst::ICMP_NE; 92 break; 93 case ICmpInst::ICMP_SGT: 94 // X > -1 is equivalent to (X & SignMask) == 0. 95 if (!C->isAllOnesValue()) 96 return false; 97 Mask = APInt::getSignMask(C->getBitWidth()); 98 Pred = ICmpInst::ICMP_EQ; 99 break; 100 case ICmpInst::ICMP_SGE: 101 // X >= 0 is equivalent to (X & SignMask) == 0. 102 if (!C->isNullValue()) 103 return false; 104 Mask = APInt::getSignMask(C->getBitWidth()); 105 Pred = ICmpInst::ICMP_EQ; 106 break; 107 case ICmpInst::ICMP_ULT: 108 // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0. 109 if (!C->isPowerOf2()) 110 return false; 111 Mask = -*C; 112 Pred = ICmpInst::ICMP_EQ; 113 break; 114 case ICmpInst::ICMP_ULE: 115 // X <=u 2^n-1 is equivalent to (X & ~(2^n-1)) == 0. 116 if (!(*C + 1).isPowerOf2()) 117 return false; 118 Mask = ~*C; 119 Pred = ICmpInst::ICMP_EQ; 120 break; 121 case ICmpInst::ICMP_UGT: 122 // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0. 123 if (!(*C + 1).isPowerOf2()) 124 return false; 125 Mask = ~*C; 126 Pred = ICmpInst::ICMP_NE; 127 break; 128 case ICmpInst::ICMP_UGE: 129 // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0. 130 if (!C->isPowerOf2()) 131 return false; 132 Mask = -*C; 133 Pred = ICmpInst::ICMP_NE; 134 break; 135 } 136 137 if (LookThruTrunc && match(LHS, m_Trunc(m_Value(X)))) { 138 Mask = Mask.zext(X->getType()->getScalarSizeInBits()); 139 } else { 140 X = LHS; 141 } 142 143 return true; 144 } 145