1234285Sdim//===- CmpInstAnalysis.cpp - Utils to help fold compares ---------------===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file holds routines to help analyse compare instructions 11234285Sdim// and fold them into constants or other compare instructions 12234285Sdim// 13234285Sdim//===----------------------------------------------------------------------===// 14234285Sdim 15234285Sdim#include "llvm/Transforms/Utils/CmpInstAnalysis.h" 16252723Sdim#include "llvm/IR/Constants.h" 17252723Sdim#include "llvm/IR/Instructions.h" 18234285Sdim 19234285Sdimusing namespace llvm; 20234285Sdim 21234285Sdim/// getICmpCode - Encode a icmp predicate into a three bit mask. These bits 22234285Sdim/// are carefully arranged to allow folding of expressions such as: 23234285Sdim/// 24234285Sdim/// (A < B) | (A > B) --> (A != B) 25234285Sdim/// 26234285Sdim/// Note that this is only valid if the first and second predicates have the 27234285Sdim/// same sign. Is illegal to do: (A u< B) | (A s> B) 28234285Sdim/// 29234285Sdim/// Three bits are used to represent the condition, as follows: 30234285Sdim/// 0 A > B 31234285Sdim/// 1 A == B 32234285Sdim/// 2 A < B 33234285Sdim/// 34234285Sdim/// <=> Value Definition 35234285Sdim/// 000 0 Always false 36234285Sdim/// 001 1 A > B 37234285Sdim/// 010 2 A == B 38234285Sdim/// 011 3 A >= B 39234285Sdim/// 100 4 A < B 40234285Sdim/// 101 5 A != B 41234285Sdim/// 110 6 A <= B 42234285Sdim/// 111 7 Always true 43234285Sdim/// 44234285Sdimunsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) { 45234285Sdim ICmpInst::Predicate Pred = InvertPred ? ICI->getInversePredicate() 46234285Sdim : ICI->getPredicate(); 47234285Sdim switch (Pred) { 48234285Sdim // False -> 0 49234285Sdim case ICmpInst::ICMP_UGT: return 1; // 001 50234285Sdim case ICmpInst::ICMP_SGT: return 1; // 001 51234285Sdim case ICmpInst::ICMP_EQ: return 2; // 010 52234285Sdim case ICmpInst::ICMP_UGE: return 3; // 011 53234285Sdim case ICmpInst::ICMP_SGE: return 3; // 011 54234285Sdim case ICmpInst::ICMP_ULT: return 4; // 100 55234285Sdim case ICmpInst::ICMP_SLT: return 4; // 100 56234285Sdim case ICmpInst::ICMP_NE: return 5; // 101 57234285Sdim case ICmpInst::ICMP_ULE: return 6; // 110 58234285Sdim case ICmpInst::ICMP_SLE: return 6; // 110 59234285Sdim // True -> 7 60234285Sdim default: 61234285Sdim llvm_unreachable("Invalid ICmp predicate!"); 62234285Sdim } 63234285Sdim} 64234285Sdim 65234285Sdim/// getICmpValue - This is the complement of getICmpCode, which turns an 66234285Sdim/// opcode and two operands into either a constant true or false, or the 67234285Sdim/// predicate for a new ICmp instruction. The sign is passed in to determine 68234285Sdim/// which kind of predicate to use in the new icmp instruction. 69234285Sdim/// Non-NULL return value will be a true or false constant. 70234285Sdim/// NULL return means a new ICmp is needed. The predicate for which is 71234285Sdim/// output in NewICmpPred. 72234285SdimValue *llvm::getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, 73234285Sdim CmpInst::Predicate &NewICmpPred) { 74234285Sdim switch (Code) { 75234285Sdim default: llvm_unreachable("Illegal ICmp code!"); 76234285Sdim case 0: // False. 77234285Sdim return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 78234285Sdim case 1: NewICmpPred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break; 79234285Sdim case 2: NewICmpPred = ICmpInst::ICMP_EQ; break; 80234285Sdim case 3: NewICmpPred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break; 81234285Sdim case 4: NewICmpPred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break; 82234285Sdim case 5: NewICmpPred = ICmpInst::ICMP_NE; break; 83234285Sdim case 6: NewICmpPred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break; 84234285Sdim case 7: // True. 85234285Sdim return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1); 86234285Sdim } 87234285Sdim return NULL; 88234285Sdim} 89234285Sdim 90234285Sdim/// PredicatesFoldable - Return true if both predicates match sign or if at 91234285Sdim/// least one of them is an equality comparison (which is signless). 92234285Sdimbool llvm::PredicatesFoldable(ICmpInst::Predicate p1, ICmpInst::Predicate p2) { 93234285Sdim return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) || 94234285Sdim (CmpInst::isSigned(p1) && ICmpInst::isEquality(p2)) || 95234285Sdim (CmpInst::isSigned(p2) && ICmpInst::isEquality(p1)); 96234285Sdim} 97