LLVM  14.0.0git
CmpInstAnalysis.cpp
Go to the documentation of this file.
1 //===- CmpInstAnalysis.cpp - Utils to help fold compares ---------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file holds routines to help analyse compare instructions
10 // and fold them into constants or other compare instructions
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/IR/Constants.h"
16 #include "llvm/IR/Instructions.h"
17 #include "llvm/IR/PatternMatch.h"
18 
19 using namespace llvm;
20 
21 unsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) {
22  ICmpInst::Predicate Pred = InvertPred ? ICI->getInversePredicate()
23  : ICI->getPredicate();
24  switch (Pred) {
25  // False -> 0
26  case ICmpInst::ICMP_UGT: return 1; // 001
27  case ICmpInst::ICMP_SGT: return 1; // 001
28  case ICmpInst::ICMP_EQ: return 2; // 010
29  case ICmpInst::ICMP_UGE: return 3; // 011
30  case ICmpInst::ICMP_SGE: return 3; // 011
31  case ICmpInst::ICMP_ULT: return 4; // 100
32  case ICmpInst::ICMP_SLT: return 4; // 100
33  case ICmpInst::ICMP_NE: return 5; // 101
34  case ICmpInst::ICMP_ULE: return 6; // 110
35  case ICmpInst::ICMP_SLE: return 6; // 110
36  // True -> 7
37  default:
38  llvm_unreachable("Invalid ICmp predicate!");
39  }
40 }
41 
42 Constant *llvm::getPredForICmpCode(unsigned Code, bool Sign, Type *OpTy,
43  CmpInst::Predicate &Pred) {
44  switch (Code) {
45  default: llvm_unreachable("Illegal ICmp code!");
46  case 0: // False.
48  case 1: Pred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break;
49  case 2: Pred = ICmpInst::ICMP_EQ; break;
50  case 3: Pred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break;
51  case 4: Pred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break;
52  case 5: Pred = ICmpInst::ICMP_NE; break;
53  case 6: Pred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break;
54  case 7: // True.
56  }
57  return nullptr;
58 }
59 
61  return (CmpInst::isSigned(P1) == CmpInst::isSigned(P2)) ||
64 }
65 
67  CmpInst::Predicate &Pred,
68  Value *&X, APInt &Mask, bool LookThruTrunc) {
69  using namespace PatternMatch;
70 
71  const APInt *C;
72  if (!match(RHS, m_APInt(C)))
73  return false;
74 
75  switch (Pred) {
76  default:
77  return false;
78  case ICmpInst::ICMP_SLT:
79  // X < 0 is equivalent to (X & SignMask) != 0.
80  if (!C->isZero())
81  return false;
82  Mask = APInt::getSignMask(C->getBitWidth());
83  Pred = ICmpInst::ICMP_NE;
84  break;
85  case ICmpInst::ICMP_SLE:
86  // X <= -1 is equivalent to (X & SignMask) != 0.
87  if (!C->isAllOnes())
88  return false;
89  Mask = APInt::getSignMask(C->getBitWidth());
90  Pred = ICmpInst::ICMP_NE;
91  break;
92  case ICmpInst::ICMP_SGT:
93  // X > -1 is equivalent to (X & SignMask) == 0.
94  if (!C->isAllOnes())
95  return false;
96  Mask = APInt::getSignMask(C->getBitWidth());
97  Pred = ICmpInst::ICMP_EQ;
98  break;
99  case ICmpInst::ICMP_SGE:
100  // X >= 0 is equivalent to (X & SignMask) == 0.
101  if (!C->isZero())
102  return false;
103  Mask = APInt::getSignMask(C->getBitWidth());
104  Pred = ICmpInst::ICMP_EQ;
105  break;
106  case ICmpInst::ICMP_ULT:
107  // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0.
108  if (!C->isPowerOf2())
109  return false;
110  Mask = -*C;
111  Pred = ICmpInst::ICMP_EQ;
112  break;
113  case ICmpInst::ICMP_ULE:
114  // X <=u 2^n-1 is equivalent to (X & ~(2^n-1)) == 0.
115  if (!(*C + 1).isPowerOf2())
116  return false;
117  Mask = ~*C;
118  Pred = ICmpInst::ICMP_EQ;
119  break;
120  case ICmpInst::ICMP_UGT:
121  // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0.
122  if (!(*C + 1).isPowerOf2())
123  return false;
124  Mask = ~*C;
125  Pred = ICmpInst::ICMP_NE;
126  break;
127  case ICmpInst::ICMP_UGE:
128  // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0.
129  if (!C->isPowerOf2())
130  return false;
131  Mask = -*C;
132  Pred = ICmpInst::ICMP_NE;
133  break;
134  }
135 
136  if (LookThruTrunc && match(LHS, m_Trunc(m_Value(X)))) {
137  Mask = Mask.zext(X->getType()->getScalarSizeInBits());
138  } else {
139  X = LHS;
140  }
141 
142  return true;
143 }
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
CmpInstAnalysis.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1031
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:820
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:747
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::ICmpInst::isEquality
bool isEquality() const
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1298
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:750
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:270
llvm::predicatesFoldable
bool predicatesFoldable(CmpInst::Predicate P1, CmpInst::Predicate P2)
Return true if both predicates match sign or if at least one of them is an equality comparison (which...
Definition: CmpInstAnalysis.cpp:60
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
P2
This might compile to this xmm1 xorps xmm0 movss xmm0 ret Now consider if the code caused xmm1 to get spilled This might produce this xmm1 movaps xmm0 movaps xmm1 movss xmm0 ret since the reload is only used by these we could fold it into the producing something like xmm1 movaps xmm0 ret saving two instructions The basic idea is that a reload from a spill if only one byte chunk is bring in zeros the one element instead of elements This can be used to simplify a variety of shuffle where the elements are fixed zeros This code generates ugly probably due to costs being off or< 4 x float > * P2
Definition: README-SSE.txt:278
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::CmpInst::ICMP_ULE
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:746
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:925
PatternMatch.h
llvm::getICmpCode
unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred=false)
Encode a icmp predicate into a three bit mask.
Definition: CmpInstAnalysis.cpp:21
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:744
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::CmpInst::ICMP_SLT
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:749
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::decomposeBitTestICmp
bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, Value *&X, APInt &Mask, bool LookThroughTrunc=true)
Decompose an icmp into the form ((X & Mask) pred 0) if possible.
Definition: CmpInstAnalysis.cpp:66
llvm::getPredForICmpCode
Constant * getPredForICmpCode(unsigned Code, bool Sign, Type *OpTy, CmpInst::Predicate &Pred)
This is the complement of getICmpCode.
Definition: CmpInstAnalysis.cpp:42
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:934
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:748
llvm::APInt::getSignMask
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:209
Instructions.h
llvm::CmpInst::ICMP_UGT
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:743
llvm::CmpInst::getPredicate
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:796
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1621
llvm::Value
LLVM Value Representation.
Definition: Value.h:74