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) { 70 const APInt *C; 71 if (!match(RHS, PatternMatch::m_APInt(C))) 72 return false; 73 74 switch (Pred) { 75 default: 76 return false; 77 case ICmpInst::ICMP_SLT: 78 // X < 0 is equivalent to (X & SignMask) != 0. 79 if (!C->isNullValue()) 80 return false; 81 Mask = APInt::getSignMask(C->getBitWidth()); 82 Pred = ICmpInst::ICMP_NE; 83 break; 84 case ICmpInst::ICMP_SLE: 85 // X <= -1 is equivalent to (X & SignMask) != 0. 86 if (!C->isAllOnesValue()) 87 return false; 88 Mask = APInt::getSignMask(C->getBitWidth()); 89 Pred = ICmpInst::ICMP_NE; 90 break; 91 case ICmpInst::ICMP_SGT: 92 // X > -1 is equivalent to (X & SignMask) == 0. 93 if (!C->isAllOnesValue()) 94 return false; 95 Mask = APInt::getSignMask(C->getBitWidth()); 96 Pred = ICmpInst::ICMP_EQ; 97 break; 98 case ICmpInst::ICMP_SGE: 99 // X >= 0 is equivalent to (X & SignMask) == 0. 100 if (!C->isNullValue()) 101 return false; 102 Mask = APInt::getSignMask(C->getBitWidth()); 103 Pred = ICmpInst::ICMP_EQ; 104 break; 105 case ICmpInst::ICMP_ULT: 106 // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0. 107 if (!C->isPowerOf2()) 108 return false; 109 Mask = -*C; 110 Pred = ICmpInst::ICMP_EQ; 111 break; 112 case ICmpInst::ICMP_ULE: 113 // X <=u 2^n-1 is equivalent to (X & ~(2^n-1)) == 0. 114 if (!(*C + 1).isPowerOf2()) 115 return false; 116 Mask = ~*C; 117 Pred = ICmpInst::ICMP_EQ; 118 break; 119 case ICmpInst::ICMP_UGT: 120 // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0. 121 if (!(*C + 1).isPowerOf2()) 122 return false; 123 Mask = ~*C; 124 Pred = ICmpInst::ICMP_NE; 125 break; 126 case ICmpInst::ICMP_UGE: 127 // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0. 128 if (!C->isPowerOf2()) 129 return false; 130 Mask = -*C; 131 Pred = ICmpInst::ICMP_NE; 132 break; 133 } 134 135 X = LHS; 136 return true; 137 } 138