Pete Cooper | 2e33944 | 2011-12-17 01:20:32 +0000 | [diff] [blame] | 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/Transforms/Utils/CmpInstAnalysis.h" |
| 16 | #include "llvm/Constants.h" |
| 17 | #include "llvm/Instructions.h" |
| 18 | |
| 19 | using namespace llvm; |
| 20 | |
| 21 | /// getICmpCode - Encode a icmp predicate into a three bit mask. These bits |
| 22 | /// are carefully arranged to allow folding of expressions such as: |
| 23 | /// |
| 24 | /// (A < B) | (A > B) --> (A != B) |
| 25 | /// |
| 26 | /// Note that this is only valid if the first and second predicates have the |
| 27 | /// same sign. Is illegal to do: (A u< B) | (A s> B) |
| 28 | /// |
| 29 | /// Three bits are used to represent the condition, as follows: |
| 30 | /// 0 A > B |
| 31 | /// 1 A == B |
| 32 | /// 2 A < B |
| 33 | /// |
| 34 | /// <=> Value Definition |
| 35 | /// 000 0 Always false |
| 36 | /// 001 1 A > B |
| 37 | /// 010 2 A == B |
| 38 | /// 011 3 A >= B |
| 39 | /// 100 4 A < B |
| 40 | /// 101 5 A != B |
| 41 | /// 110 6 A <= B |
| 42 | /// 111 7 Always true |
| 43 | /// |
| 44 | unsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) { |
| 45 | ICmpInst::Predicate Pred = InvertPred ? ICI->getInversePredicate() |
| 46 | : ICI->getPredicate(); |
| 47 | switch (Pred) { |
| 48 | // False -> 0 |
| 49 | case ICmpInst::ICMP_UGT: return 1; // 001 |
| 50 | case ICmpInst::ICMP_SGT: return 1; // 001 |
| 51 | case ICmpInst::ICMP_EQ: return 2; // 010 |
| 52 | case ICmpInst::ICMP_UGE: return 3; // 011 |
| 53 | case ICmpInst::ICMP_SGE: return 3; // 011 |
| 54 | case ICmpInst::ICMP_ULT: return 4; // 100 |
| 55 | case ICmpInst::ICMP_SLT: return 4; // 100 |
| 56 | case ICmpInst::ICMP_NE: return 5; // 101 |
| 57 | case ICmpInst::ICMP_ULE: return 6; // 110 |
| 58 | case ICmpInst::ICMP_SLE: return 6; // 110 |
| 59 | // True -> 7 |
| 60 | default: |
| 61 | llvm_unreachable("Invalid ICmp predicate!"); |
Pete Cooper | 2e33944 | 2011-12-17 01:20:32 +0000 | [diff] [blame] | 62 | } |
| 63 | } |
| 64 | |
| 65 | /// getICmpValue - This is the complement of getICmpCode, which turns an |
| 66 | /// opcode and two operands into either a constant true or false, or the |
| 67 | /// predicate for a new ICmp instruction. The sign is passed in to determine |
| 68 | /// which kind of predicate to use in the new icmp instruction. |
| 69 | /// Non-NULL return value will be a true or false constant. |
| 70 | /// NULL return means a new ICmp is needed. The predicate for which is |
| 71 | /// output in NewICmpPred. |
| 72 | Value *llvm::getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, |
| 73 | CmpInst::Predicate &NewICmpPred) { |
| 74 | switch (Code) { |
| 75 | default: assert(0 && "Illegal ICmp code!"); |
| 76 | case 0: // False. |
| 77 | return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); |
| 78 | case 1: NewICmpPred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break; |
| 79 | case 2: NewICmpPred = ICmpInst::ICMP_EQ; break; |
| 80 | case 3: NewICmpPred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break; |
| 81 | case 4: NewICmpPred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break; |
| 82 | case 5: NewICmpPred = ICmpInst::ICMP_NE; break; |
| 83 | case 6: NewICmpPred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break; |
| 84 | case 7: // True. |
| 85 | return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1); |
| 86 | } |
| 87 | return NULL; |
| 88 | } |
| 89 | |
| 90 | /// PredicatesFoldable - Return true if both predicates match sign or if at |
| 91 | /// least one of them is an equality comparison (which is signless). |
| 92 | bool llvm::PredicatesFoldable(ICmpInst::Predicate p1, ICmpInst::Predicate p2) { |
| 93 | return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) || |
| 94 | (CmpInst::isSigned(p1) && ICmpInst::isEquality(p2)) || |
| 95 | (CmpInst::isSigned(p2) && ICmpInst::isEquality(p1)); |
| 96 | } |