12e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper//===- CmpInstAnalysis.cpp - Utils to help fold compares ---------------===// 22e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// 32e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// The LLVM Compiler Infrastructure 42e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// 52e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// This file is distributed under the University of Illinois Open Source 62e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// License. See LICENSE.TXT for details. 72e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// 82e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper//===----------------------------------------------------------------------===// 92e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// 102e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// This file holds routines to help analyse compare instructions 112e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// and fold them into constants or other compare instructions 122e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper// 132e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper//===----------------------------------------------------------------------===// 142e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper 152e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper#include "llvm/Transforms/Utils/CmpInstAnalysis.h" 160b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 170b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 182e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper 192e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooperusing namespace llvm; 202e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper 212e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// getICmpCode - Encode a icmp predicate into a three bit mask. These bits 222e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// are carefully arranged to allow folding of expressions such as: 232e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 242e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// (A < B) | (A > B) --> (A != B) 252e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 262e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// Note that this is only valid if the first and second predicates have the 272e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// same sign. Is illegal to do: (A u< B) | (A s> B) 282e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 292e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// Three bits are used to represent the condition, as follows: 302e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 0 A > B 312e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 1 A == B 322e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 2 A < B 332e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 342e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// <=> Value Definition 352e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 000 0 Always false 362e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 001 1 A > B 372e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 010 2 A == B 382e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 011 3 A >= B 392e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 100 4 A < B 402e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 101 5 A != B 412e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 110 6 A <= B 422e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 111 7 Always true 432e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// 442e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooperunsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) { 452e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper ICmpInst::Predicate Pred = InvertPred ? ICI->getInversePredicate() 462e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper : ICI->getPredicate(); 472e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper switch (Pred) { 482e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper // False -> 0 492e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_UGT: return 1; // 001 502e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_SGT: return 1; // 001 512e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_EQ: return 2; // 010 522e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_UGE: return 3; // 011 532e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_SGE: return 3; // 011 542e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_ULT: return 4; // 100 552e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_SLT: return 4; // 100 562e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_NE: return 5; // 101 572e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_ULE: return 6; // 110 582e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case ICmpInst::ICMP_SLE: return 6; // 110 592e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper // True -> 7 602e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper default: 612e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper llvm_unreachable("Invalid ICmp predicate!"); 622e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper } 632e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper} 642e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper 652e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// getICmpValue - This is the complement of getICmpCode, which turns an 662e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// opcode and two operands into either a constant true or false, or the 672e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// predicate for a new ICmp instruction. The sign is passed in to determine 682e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// which kind of predicate to use in the new icmp instruction. 692e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// Non-NULL return value will be a true or false constant. 702e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// NULL return means a new ICmp is needed. The predicate for which is 712e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// output in NewICmpPred. 722e33944c101f2a08ed1d85e807830f2fc089dd06Pete CooperValue *llvm::getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, 732e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper CmpInst::Predicate &NewICmpPred) { 742e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper switch (Code) { 75858143816d43e58b17bfd11cb1b57afbd7f0f893Craig Topper default: llvm_unreachable("Illegal ICmp code!"); 762e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 0: // False. 772e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0); 782e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 1: NewICmpPred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break; 792e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 2: NewICmpPred = ICmpInst::ICMP_EQ; break; 802e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 3: NewICmpPred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break; 812e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 4: NewICmpPred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break; 822e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 5: NewICmpPred = ICmpInst::ICMP_NE; break; 832e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 6: NewICmpPred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break; 842e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper case 7: // True. 852e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1); 862e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper } 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 882e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper} 892e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper 902e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// PredicatesFoldable - Return true if both predicates match sign or if at 912e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper/// least one of them is an equality comparison (which is signless). 922e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooperbool llvm::PredicatesFoldable(ICmpInst::Predicate p1, ICmpInst::Predicate p2) { 932e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) || 942e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper (CmpInst::isSigned(p1) && ICmpInst::isEquality(p2)) || 952e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper (CmpInst::isSigned(p2) && ICmpInst::isEquality(p1)); 962e33944c101f2a08ed1d85e807830f2fc089dd06Pete Cooper} 97