LLVM  6.0.0svn
CmpInstAnalysis.cpp
Go to the documentation of this file.
1 //===- CmpInstAnalysis.cpp - Utils to help fold compares ---------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file holds routines to help analyse compare instructions
11 // and fold them into constants or other compare instructions
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/IR/Constants.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/PatternMatch.h"
19 
20 using namespace llvm;
21 
22 unsigned llvm::getICmpCode(const ICmpInst *ICI, bool InvertPred) {
23  ICmpInst::Predicate Pred = InvertPred ? ICI->getInversePredicate()
24  : ICI->getPredicate();
25  switch (Pred) {
26  // False -> 0
27  case ICmpInst::ICMP_UGT: return 1; // 001
28  case ICmpInst::ICMP_SGT: return 1; // 001
29  case ICmpInst::ICMP_EQ: return 2; // 010
30  case ICmpInst::ICMP_UGE: return 3; // 011
31  case ICmpInst::ICMP_SGE: return 3; // 011
32  case ICmpInst::ICMP_ULT: return 4; // 100
33  case ICmpInst::ICMP_SLT: return 4; // 100
34  case ICmpInst::ICMP_NE: return 5; // 101
35  case ICmpInst::ICMP_ULE: return 6; // 110
36  case ICmpInst::ICMP_SLE: return 6; // 110
37  // True -> 7
38  default:
39  llvm_unreachable("Invalid ICmp predicate!");
40  }
41 }
42 
43 Value *llvm::getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
44  CmpInst::Predicate &NewICmpPred) {
45  switch (Code) {
46  default: llvm_unreachable("Illegal ICmp code!");
47  case 0: // False.
49  case 1: NewICmpPred = Sign ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT; break;
50  case 2: NewICmpPred = ICmpInst::ICMP_EQ; break;
51  case 3: NewICmpPred = Sign ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE; break;
52  case 4: NewICmpPred = Sign ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT; break;
53  case 5: NewICmpPred = ICmpInst::ICMP_NE; break;
54  case 6: NewICmpPred = Sign ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; break;
55  case 7: // True.
57  }
58  return nullptr;
59 }
60 
62  return (CmpInst::isSigned(p1) == CmpInst::isSigned(p2)) ||
65 }
66 
68  CmpInst::Predicate &Pred,
69  Value *&X, APInt &Mask, bool LookThruTrunc) {
70  using namespace PatternMatch;
71 
72  const APInt *C;
73  if (!match(RHS, m_APInt(C)))
74  return false;
75 
76  switch (Pred) {
77  default:
78  return false;
79  case ICmpInst::ICMP_SLT:
80  // X < 0 is equivalent to (X & SignMask) != 0.
81  if (!C->isNullValue())
82  return false;
83  Mask = APInt::getSignMask(C->getBitWidth());
84  Pred = ICmpInst::ICMP_NE;
85  break;
86  case ICmpInst::ICMP_SLE:
87  // X <= -1 is equivalent to (X & SignMask) != 0.
88  if (!C->isAllOnesValue())
89  return false;
90  Mask = APInt::getSignMask(C->getBitWidth());
91  Pred = ICmpInst::ICMP_NE;
92  break;
93  case ICmpInst::ICMP_SGT:
94  // X > -1 is equivalent to (X & SignMask) == 0.
95  if (!C->isAllOnesValue())
96  return false;
97  Mask = APInt::getSignMask(C->getBitWidth());
98  Pred = ICmpInst::ICMP_EQ;
99  break;
100  case ICmpInst::ICMP_SGE:
101  // X >= 0 is equivalent to (X & SignMask) == 0.
102  if (!C->isNullValue())
103  return false;
104  Mask = APInt::getSignMask(C->getBitWidth());
105  Pred = ICmpInst::ICMP_EQ;
106  break;
107  case ICmpInst::ICMP_ULT:
108  // X <u 2^n is equivalent to (X & ~(2^n-1)) == 0.
109  if (!C->isPowerOf2())
110  return false;
111  Mask = -*C;
112  Pred = ICmpInst::ICMP_EQ;
113  break;
114  case ICmpInst::ICMP_ULE:
115  // X <=u 2^n-1 is equivalent to (X & ~(2^n-1)) == 0.
116  if (!(*C + 1).isPowerOf2())
117  return false;
118  Mask = ~*C;
119  Pred = ICmpInst::ICMP_EQ;
120  break;
121  case ICmpInst::ICMP_UGT:
122  // X >u 2^n-1 is equivalent to (X & ~(2^n-1)) != 0.
123  if (!(*C + 1).isPowerOf2())
124  return false;
125  Mask = ~*C;
126  Pred = ICmpInst::ICMP_NE;
127  break;
128  case ICmpInst::ICMP_UGE:
129  // X >=u 2^n is equivalent to (X & ~(2^n-1)) != 0.
130  if (!C->isPowerOf2())
131  return false;
132  Mask = -*C;
133  Pred = ICmpInst::ICMP_NE;
134  break;
135  }
136 
137  if (LookThruTrunc && match(LHS, m_Trunc(m_Value(X)))) {
138  Mask = Mask.zext(X->getType()->getScalarSizeInBits());
139  } else {
140  X = LHS;
141  }
142 
143  return true;
144 }
uint64_t CallInst * C
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
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:1067
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:865
unsigned less or equal
Definition: InstrTypes.h:879
unsigned less than
Definition: InstrTypes.h:878
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1488
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
bool isSigned() const
Determine if this instruction is using a signed comparison.
Definition: InstrTypes.h:994
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:951
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:912
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:389
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:260
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:853
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
signed greater than
Definition: InstrTypes.h:880
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:548
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
signed less than
Definition: InstrTypes.h:882
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:560
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...
signed less or equal
Definition: InstrTypes.h:883
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:457
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:927
Value * getICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS, CmpInst::Predicate &NewICmpPred)
This is the complement of getICmpCode, which turns an opcode and two operands into either a constant ...
unsigned greater or equal
Definition: InstrTypes.h:877
bool isEquality() const
Return true if this predicate is either EQ or NE.
LLVM Value Representation.
Definition: Value.h:73
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:81
unsigned greater than
Definition: InstrTypes.h:876
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:399
signed greater or equal
Definition: InstrTypes.h:881