LLVM  9.0.0svn
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->isNullValue())
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->isAllOnesValue())
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->isAllOnesValue())
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->isNullValue())
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 }
uint64_t CallInst * C
Constant * getPredForICmpCode(unsigned Code, bool Sign, Type *OpTy, CmpInst::Predicate &Pred)
This is the complement of getICmpCode.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Definition: InstrTypes.h:889
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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.
unsigned getICmpCode(const ICmpInst *ICI, bool InvertPred=false)
Encode a icmp predicate into a three bit mask.
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:857
unsigned less or equal
Definition: InstrTypes.h:672
unsigned less than
Definition: InstrTypes.h:671
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1508
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
bool isSigned() const
Definition: InstrTypes.h:816
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:745
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:395
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:175
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:646
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
signed greater than
Definition: InstrTypes.h:673
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:554
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:129
signed less than
Definition: InstrTypes.h:675
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:631
signed less or equal
Definition: InstrTypes.h:676
Class for arbitrary precision integers.
Definition: APInt.h:69
bool isPowerOf2() const
Check if this APInt&#39;s value is a power of two greater than zero.
Definition: APInt.h:463
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:721
unsigned greater or equal
Definition: InstrTypes.h:670
bool isEquality() const
Return true if this predicate is either EQ or NE.
LLVM Value Representation.
Definition: Value.h:72
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
unsigned greater than
Definition: InstrTypes.h:669
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...
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
signed greater or equal
Definition: InstrTypes.h:674