LLVM  15.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 
22  switch (Pred) {
23  // False -> 0
24  case ICmpInst::ICMP_UGT: return 1; // 001
25  case ICmpInst::ICMP_SGT: return 1; // 001
26  case ICmpInst::ICMP_EQ: return 2; // 010
27  case ICmpInst::ICMP_UGE: return 3; // 011
28  case ICmpInst::ICMP_SGE: return 3; // 011
29  case ICmpInst::ICMP_ULT: return 4; // 100
30  case ICmpInst::ICMP_SLT: return 4; // 100
31  case ICmpInst::ICMP_NE: return 5; // 101
32  case ICmpInst::ICMP_ULE: return 6; // 110
33  case ICmpInst::ICMP_SLE: return 6; // 110
34  // True -> 7
35  default:
36  llvm_unreachable("Invalid ICmp predicate!");
37  }
38 }
39 
40 Constant *llvm::getPredForICmpCode(unsigned Code, bool Sign, Type *OpTy,
41  CmpInst::Predicate &Pred) {
42  switch (Code) {
43  default: llvm_unreachable("Illegal ICmp code!");
44  case 0: // False.
46  case 1: Pred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break;
47  case 2: Pred = ICmpInst::ICMP_EQ; break;
48  case 3: Pred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break;
49  case 4: Pred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break;
50  case 5: Pred = ICmpInst::ICMP_NE; break;
51  case 6: Pred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break;
52  case 7: // True.
54  }
55  return nullptr;
56 }
57 
59  return (CmpInst::isSigned(P1) == CmpInst::isSigned(P2)) ||
62 }
63 
64 Constant *llvm::getPredForFCmpCode(unsigned Code, Type *OpTy,
65  CmpInst::Predicate &Pred) {
66  Pred = static_cast<FCmpInst::Predicate>(Code);
67  assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE &&
68  "Unexpected FCmp predicate!");
69  if (Pred == FCmpInst::FCMP_FALSE)
71  if (Pred == FCmpInst::FCMP_TRUE)
73  return nullptr;
74 }
75 
77  CmpInst::Predicate &Pred,
78  Value *&X, APInt &Mask, bool LookThruTrunc) {
79  using namespace PatternMatch;
80 
81  const APInt *C;
82  if (!match(RHS, m_APInt(C)))
83  return false;
84 
85  switch (Pred) {
86  default:
87  return false;
88  case ICmpInst::ICMP_SLT:
89  // X < 0 is equivalent to (X & SignMask) != 0.
90  if (!C->isZero())
91  return false;
92  Mask = APInt::getSignMask(C->getBitWidth());
93  Pred = ICmpInst::ICMP_NE;
94  break;
95  case ICmpInst::ICMP_SLE:
96  // X <= -1 is equivalent to (X & SignMask) != 0.
97  if (!C->isAllOnes())
98  return false;
99  Mask = APInt::getSignMask(C->getBitWidth());
100  Pred = ICmpInst::ICMP_NE;
101  break;
102  case ICmpInst::ICMP_SGT:
103  // X > -1 is equivalent to (X & SignMask) == 0.
104  if (!C->isAllOnes())
105  return false;
106  Mask = APInt::getSignMask(C->getBitWidth());
107  Pred = ICmpInst::ICMP_EQ;
108  break;
109  case ICmpInst::ICMP_SGE:
110  // X >= 0 is equivalent to (X & SignMask) == 0.
111  if (!C->isZero())
112  return false;
113  Mask = APInt::getSignMask(C->getBitWidth());
114  Pred = ICmpInst::ICMP_EQ;
115  break;
116  case ICmpInst::ICMP_ULT:
117  // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0.
118  if (!C->isPowerOf2())
119  return false;
120  Mask = -*C;
121  Pred = ICmpInst::ICMP_EQ;
122  break;
123  case ICmpInst::ICMP_ULE:
124  // X <=u 2^n-1 is equivalent to (X & ~(2^n-1)) == 0.
125  if (!(*C + 1).isPowerOf2())
126  return false;
127  Mask = ~*C;
128  Pred = ICmpInst::ICMP_EQ;
129  break;
130  case ICmpInst::ICMP_UGT:
131  // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0.
132  if (!(*C + 1).isPowerOf2())
133  return false;
134  Mask = ~*C;
135  Pred = ICmpInst::ICMP_NE;
136  break;
137  case ICmpInst::ICMP_UGE:
138  // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0.
139  if (!C->isPowerOf2())
140  return false;
141  Mask = -*C;
142  Pred = ICmpInst::ICMP_NE;
143  break;
144  }
145 
146  if (LookThruTrunc && match(LHS, m_Trunc(m_Value(X)))) {
147  Mask = Mask.zext(X->getType()->getScalarSizeInBits());
148  } else {
149  X = LHS;
150  }
151 
152  return true;
153 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:740
CmpInstAnalysis.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::CmpInst::makeCmpResultType
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:1044
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:741
llvm::CmpInst::ICMP_SGT
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:746
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:1281
llvm::CmpInst::ICMP_SLE
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:749
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::BitmaskEnumDetail::Mask
constexpr 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
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
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:58
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:745
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:919
PatternMatch.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::CmpInst::FCMP_FALSE
@ FCMP_FALSE
0 0 0 0 Always false (always folded)
Definition: InstrTypes.h:721
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::getPredForFCmpCode
Constant * getPredForFCmpCode(unsigned Code, Type *OpTy, CmpInst::Predicate &Pred)
This is the complement of getFCmpCode.
Definition: CmpInstAnalysis.cpp:64
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CmpInst::ICMP_UGE
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:743
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:748
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:744
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::getICmpCode
unsigned getICmpCode(CmpInst::Predicate Pred)
Encode a icmp predicate into a three bit mask.
Definition: CmpInstAnalysis.cpp:21
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:76
llvm::getPredForICmpCode
Constant * getPredForICmpCode(unsigned Code, bool Sign, Type *OpTy, CmpInst::Predicate &Pred)
This is the complement of getICmpCode.
Definition: CmpInstAnalysis.cpp:40
llvm::CmpInst::isSigned
bool isSigned() const
Definition: InstrTypes.h:947
llvm::CmpInst::ICMP_SGE
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:747
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:742
llvm::PatternMatch::m_Trunc
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:1621
llvm::CmpInst::FCMP_TRUE
@ FCMP_TRUE
1 1 1 1 Always true (always folded)
Definition: InstrTypes.h:736
llvm::Value
LLVM Value Representation.
Definition: Value.h:74