LLVM 17.0.0git
InstCombiner.h
Go to the documentation of this file.
1//===- InstCombiner.h - InstCombine implementation --------------*- C++ -*-===//
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/// \file
9///
10/// This file provides the interface for the instcombine pass implementation.
11/// The interface is used for generic transformations in this folder and
12/// target specific combinations in the targets.
13/// The visitor implementation is in \c InstCombinerImpl in
14/// \c InstCombineInternal.h.
15///
16//===----------------------------------------------------------------------===//
17
18#ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
19#define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINER_H
20
24#include "llvm/IR/IRBuilder.h"
26#include "llvm/Support/Debug.h"
28#include <cassert>
29
30#define DEBUG_TYPE "instcombine"
32
33namespace llvm {
34
35class AAResults;
36class AssumptionCache;
37class ProfileSummaryInfo;
38class TargetLibraryInfo;
39class TargetTransformInfo;
40
41/// The core instruction combiner logic.
42///
43/// This class provides both the logic to recursively visit instructions and
44/// combine them.
46 /// Only used to call target specific intrinsic combining.
47 /// It must **NOT** be used for any other purpose, as InstCombine is a
48 /// target-independent canonicalization transform.
50
51public:
52 /// Maximum size of array considered when transforming.
53 uint64_t MaxArraySizeForCombine = 0;
54
55 /// An IRBuilder that automatically inserts new instructions into the
56 /// worklist.
59
60protected:
61 /// A worklist of the instructions that need to be simplified.
63
64 // Mode in which we are running the combiner.
65 const bool MinimizeSize;
66
68
69 // Required analyses.
73 const DataLayout &DL;
78
79 // Optional analyses. When non-null, these can both be used to do better
80 // combining and will be updated to reflect any changes.
82
83 bool MadeIRChange = false;
84
85public:
87 bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
91 const DataLayout &DL, LoopInfo *LI)
92 : TTI(TTI), Builder(Builder), Worklist(Worklist),
93 MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL),
94 SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
95
96 virtual ~InstCombiner() = default;
97
98 /// Return the source operand of a potentially bitcasted value while
99 /// optionally checking if it has one use. If there is no bitcast or the one
100 /// use check is not met, return the input value itself.
101 static Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
102 if (auto *BitCast = dyn_cast<BitCastInst>(V))
103 if (!OneUseOnly || BitCast->hasOneUse())
104 return BitCast->getOperand(0);
105
106 // V is not a bitcast or V has more than one use and OneUseOnly is true.
107 return V;
108 }
109
110 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
111 /// the amount of pattern matching needed for compares and commutative
112 /// instructions. For example, if we have:
113 /// icmp ugt X, Constant
114 /// or
115 /// xor (add X, Constant), cast Z
116 ///
117 /// We do not have to consider the commuted variants of these patterns because
118 /// canonicalization based on complexity guarantees the above ordering.
119 ///
120 /// This routine maps IR values to various complexity ranks:
121 /// 0 -> undef
122 /// 1 -> Constants
123 /// 2 -> Other non-instructions
124 /// 3 -> Arguments
125 /// 4 -> Cast and (f)neg/not instructions
126 /// 5 -> Other instructions
127 static unsigned getComplexity(Value *V) {
128 if (isa<Instruction>(V)) {
129 if (isa<CastInst>(V) || match(V, m_Neg(PatternMatch::m_Value())) ||
132 return 4;
133 return 5;
134 }
135 if (isa<Argument>(V))
136 return 3;
137 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
138 }
139
140 /// Predicate canonicalization reduces the number of patterns that need to be
141 /// matched by other transforms. For example, we may swap the operands of a
142 /// conditional branch or select to create a compare with a canonical
143 /// (inverted) predicate which is then more likely to be matched with other
144 /// values.
146 switch (Pred) {
147 case CmpInst::ICMP_NE:
152 // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
156 return false;
157 default:
158 return true;
159 }
160 }
161
162 /// Given an exploded icmp instruction, return true if the comparison only
163 /// checks the sign bit. If it only checks the sign bit, set TrueIfSigned if
164 /// the result of the comparison is true when the input value is signed.
165 static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS,
166 bool &TrueIfSigned) {
167 switch (Pred) {
168 case ICmpInst::ICMP_SLT: // True if LHS s< 0
169 TrueIfSigned = true;
170 return RHS.isZero();
171 case ICmpInst::ICMP_SLE: // True if LHS s<= -1
172 TrueIfSigned = true;
173 return RHS.isAllOnes();
174 case ICmpInst::ICMP_SGT: // True if LHS s> -1
175 TrueIfSigned = false;
176 return RHS.isAllOnes();
177 case ICmpInst::ICMP_SGE: // True if LHS s>= 0
178 TrueIfSigned = false;
179 return RHS.isZero();
181 // True if LHS u> RHS and RHS == sign-bit-mask - 1
182 TrueIfSigned = true;
183 return RHS.isMaxSignedValue();
185 // True if LHS u>= RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
186 TrueIfSigned = true;
187 return RHS.isMinSignedValue();
189 // True if LHS u< RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
190 TrueIfSigned = false;
191 return RHS.isMinSignedValue();
193 // True if LHS u<= RHS and RHS == sign-bit-mask - 1
194 TrueIfSigned = false;
195 return RHS.isMaxSignedValue();
196 default:
197 return false;
198 }
199 }
200
201 /// Add one to a Constant
203 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
204 }
205
206 /// Subtract one from a Constant
208 return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
209 }
210
211 std::optional<std::pair<
213 Constant *>> static getFlippedStrictnessPredicateAndConstant(CmpInst::
214 Predicate
215 Pred,
216 Constant *C);
217
219 // a ? b : false and a ? true : b are the canonical form of logical and/or.
220 // This includes !a ? b : false and !a ? true : b. Absorbing the not into
221 // the select by swapping operands would break recognition of this pattern
222 // in other analyses, so don't do that.
227 }
228
229 /// Return true if the specified value is free to invert (apply ~ to).
230 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
231 /// is true, work under the assumption that the caller intends to remove all
232 /// uses of V and only keep uses of ~V.
233 ///
234 /// See also: canFreelyInvertAllUsersOf()
235 static bool isFreeToInvert(Value *V, bool WillInvertAllUses) {
236 // ~(~(X)) -> X.
238 return true;
239
240 // Constants can be considered to be not'ed values.
242 return true;
243
244 // Compares can be inverted if all of their uses are being modified to use
245 // the ~V.
246 if (isa<CmpInst>(V))
247 return WillInvertAllUses;
248
249 // If `V` is of the form `A + Constant` then `-1 - V` can be folded into
250 // `(-1 - Constant) - A` if we are willing to invert all of the uses.
252 return WillInvertAllUses;
253
254 // If `V` is of the form `Constant - A` then `-1 - V` can be folded into
255 // `A + (-1 - Constant)` if we are willing to invert all of the uses.
257 return WillInvertAllUses;
258
259 // Selects with invertible operands are freely invertible
260 if (match(V,
263 return WillInvertAllUses;
264
265 // Min/max may be in the form of intrinsics, so handle those identically
266 // to select patterns.
269 return WillInvertAllUses;
270
271 return false;
272 }
273
274 /// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
275 /// InstCombine's freelyInvertAllUsersOf() must be kept in sync with this fn.
276 /// NOTE: for Instructions only!
277 ///
278 /// See also: isFreeToInvert()
279 static bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser) {
280 // Look at every user of V.
281 for (Use &U : V->uses()) {
282 if (U.getUser() == IgnoredUser)
283 continue; // Don't consider this user.
284
285 auto *I = cast<Instruction>(U.getUser());
286 switch (I->getOpcode()) {
287 case Instruction::Select:
288 if (U.getOperandNo() != 0) // Only if the value is used as select cond.
289 return false;
290 if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(I)))
291 return false;
292 break;
293 case Instruction::Br:
294 assert(U.getOperandNo() == 0 && "Must be branching on that value.");
295 break; // Free to invert by swapping true/false values/destinations.
296 case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring
297 // it.
299 return false; // Not a 'not'.
300 break;
301 default:
302 return false; // Don't know, likely not freely invertible.
303 }
304 // So far all users were free to invert...
305 }
306 return true; // Can freely invert all users!
307 }
308
309 /// Some binary operators require special handling to avoid poison and
310 /// undefined behavior. If a constant vector has undef elements, replace those
311 /// undefs with identity constants if possible because those are always safe
312 /// to execute. If no identity constant exists, replace undef with some other
313 /// safe constant.
314 static Constant *
316 bool IsRHSConstant) {
317 auto *InVTy = cast<FixedVectorType>(In->getType());
318
319 Type *EltTy = InVTy->getElementType();
320 auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
321 if (!SafeC) {
322 // TODO: Should this be available as a constant utility function? It is
323 // similar to getBinOpAbsorber().
324 if (IsRHSConstant) {
325 switch (Opcode) {
326 case Instruction::SRem: // X % 1 = 0
327 case Instruction::URem: // X %u 1 = 0
328 SafeC = ConstantInt::get(EltTy, 1);
329 break;
330 case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
331 SafeC = ConstantFP::get(EltTy, 1.0);
332 break;
333 default:
335 "Only rem opcodes have no identity constant for RHS");
336 }
337 } else {
338 switch (Opcode) {
339 case Instruction::Shl: // 0 << X = 0
340 case Instruction::LShr: // 0 >>u X = 0
341 case Instruction::AShr: // 0 >> X = 0
342 case Instruction::SDiv: // 0 / X = 0
343 case Instruction::UDiv: // 0 /u X = 0
344 case Instruction::SRem: // 0 % X = 0
345 case Instruction::URem: // 0 %u X = 0
346 case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
347 case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
348 case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
349 case Instruction::FRem: // 0.0 % X = 0
350 SafeC = Constant::getNullValue(EltTy);
351 break;
352 default:
353 llvm_unreachable("Expected to find identity constant for opcode");
354 }
355 }
356 }
357 assert(SafeC && "Must have safe constant for binop");
358 unsigned NumElts = InVTy->getNumElements();
359 SmallVector<Constant *, 16> Out(NumElts);
360 for (unsigned i = 0; i != NumElts; ++i) {
361 Constant *C = In->getAggregateElement(i);
362 Out[i] = isa<UndefValue>(C) ? SafeC : C;
363 }
364 return ConstantVector::get(Out);
365 }
366
367 void addToWorklist(Instruction *I) { Worklist.push(I); }
368
369 AssumptionCache &getAssumptionCache() const { return AC; }
371 DominatorTree &getDominatorTree() const { return DT; }
372 const DataLayout &getDataLayout() const { return DL; }
373 const SimplifyQuery &getSimplifyQuery() const { return SQ; }
375 return ORE;
376 }
379 LoopInfo *getLoopInfo() const { return LI; }
380
381 // Call target specific combiners
382 std::optional<Instruction *> targetInstCombineIntrinsic(IntrinsicInst &II);
383 std::optional<Value *>
384 targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask,
385 KnownBits &Known,
386 bool &KnownBitsComputed);
387 std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
388 IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts,
389 APInt &UndefElts2, APInt &UndefElts3,
390 std::function<void(Instruction *, unsigned, APInt, APInt &)>
391 SimplifyAndSetOp);
392
393 /// Inserts an instruction \p New before instruction \p Old
394 ///
395 /// Also adds the new instruction to the worklist and returns \p New so that
396 /// it is suitable for use as the return from the visitation patterns.
398 assert(New && !New->getParent() &&
399 "New instruction already inserted into a basic block!");
400 BasicBlock *BB = Old.getParent();
401 New->insertInto(BB, Old.getIterator()); // Insert inst
402 Worklist.add(New);
403 return New;
404 }
405
406 /// Same as InsertNewInstBefore, but also sets the debug loc.
408 New->setDebugLoc(Old.getDebugLoc());
409 return InsertNewInstBefore(New, Old);
410 }
411
412 /// A combiner-aware RAUW-like routine.
413 ///
414 /// This method is to be used when an instruction is found to be dead,
415 /// replaceable with another preexisting expression. Here we add all uses of
416 /// I to the worklist, replace all uses of I with the new value, then return
417 /// I, so that the inst combiner will know that I was modified.
419 // If there are no uses to replace, then we return nullptr to indicate that
420 // no changes were made to the program.
421 if (I.use_empty()) return nullptr;
422
423 Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
424
425 // If we are replacing the instruction with itself, this must be in a
426 // segment of unreachable code, so just clobber the instruction.
427 if (&I == V)
428 V = PoisonValue::get(I.getType());
429
430 LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
431 << " with " << *V << '\n');
432
433 // If V is a new unnamed instruction, take the name from the old one.
434 if (V->use_empty() && isa<Instruction>(V) && !V->hasName() && I.hasName())
435 V->takeName(&I);
436
437 I.replaceAllUsesWith(V);
438 return &I;
439 }
440
441 /// Replace operand of instruction and add old operand to the worklist.
443 Worklist.addValue(I.getOperand(OpNum));
444 I.setOperand(OpNum, V);
445 return &I;
446 }
447
448 /// Replace use and add the previously used value to the worklist.
449 void replaceUse(Use &U, Value *NewValue) {
450 Worklist.addValue(U);
451 U = NewValue;
452 }
453
454 /// Combiner aware instruction erasure.
455 ///
456 /// When dealing with an instruction that has side effects or produces a void
457 /// value, we can't rely on DCE to delete the instruction. Instead, visit
458 /// methods should return the value returned by this function.
460
461 void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
462 const Instruction *CxtI) const {
463 llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
464 }
465
467 const Instruction *CxtI) const {
468 return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
469 }
470
471 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
472 unsigned Depth = 0,
473 const Instruction *CxtI = nullptr) {
474 return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
475 }
476
477 bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
478 const Instruction *CxtI = nullptr) const {
479 return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
480 }
481
482 unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
483 const Instruction *CxtI = nullptr) const {
484 return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
485 }
486
487 unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth = 0,
488 const Instruction *CxtI = nullptr) const {
489 return llvm::ComputeMaxSignificantBits(Op, DL, Depth, &AC, CxtI, &DT);
490 }
491
493 const Value *RHS,
494 const Instruction *CxtI) const {
495 return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
496 }
497
499 const Instruction *CxtI) const {
500 return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
501 }
502
504 const Value *RHS,
505 const Instruction *CxtI) const {
506 return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
507 }
508
510 const Instruction *CxtI) const {
511 return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
512 }
513
515 const Value *RHS,
516 const Instruction *CxtI) const {
517 return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
518 }
519
521 const Instruction *CxtI) const {
522 return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
523 }
524
525 virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo,
526 const APInt &DemandedMask, KnownBits &Known,
527 unsigned Depth = 0) = 0;
528 virtual Value *
529 SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
530 unsigned Depth = 0,
531 bool AllowMultipleUsers = false) = 0;
532};
533
534} // namespace llvm
535
536#undef DEBUG_TYPE
537
538#endif
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
assume Assume Builder
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:126
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define I(x, y, z)
Definition: MD5.cpp:58
@ SI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:75
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:708
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:747
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:748
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:723
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:742
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:741
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:745
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:726
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:725
@ ICMP_NE
not equal
Definition: InstrTypes.h:740
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:746
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:744
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2664
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2657
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2741
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:934
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:887
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1356
This is an important base class in LLVM.
Definition: Constant.h:41
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:114
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
The core instruction combiner logic.
Definition: InstCombiner.h:45
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:520
static bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ? InstCombine's freelyInvertA...
Definition: InstCombiner.h:279
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:372
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:145
virtual Instruction * eraseInstFromFunction(Instruction &I)=0
Combiner aware instruction erasure.
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:371
virtual ~InstCombiner()=default
LoopInfo * getLoopInfo() const
Definition: InstCombiner.h:379
BlockFrequencyInfo * BFI
Definition: InstCombiner.h:76
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
Definition: InstCombiner.h:407
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:127
TargetLibraryInfo & TLI
Definition: InstCombiner.h:71
TargetLibraryInfo & getTargetLibraryInfo() const
Definition: InstCombiner.h:370
BlockFrequencyInfo * getBlockFrequencyInfo() const
Definition: InstCombiner.h:377
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombiner.h:471
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:492
AAResults * AA
Definition: InstCombiner.h:67
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:418
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
Definition: InstCombiner.h:235
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:218
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:509
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
Definition: InstCombiner.h:207
virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known, unsigned Depth=0)=0
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:466
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombiner.h:449
InstCombiner(InstructionWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, const DataLayout &DL, LoopInfo *LI)
Definition: InstCombiner.h:86
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:514
const SimplifyQuery SQ
Definition: InstCombiner.h:74
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:62
const DataLayout & DL
Definition: InstCombiner.h:73
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:482
const bool MinimizeSize
Definition: InstCombiner.h:65
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:503
virtual Value * SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts, unsigned Depth=0, bool AllowMultipleUsers=false)=0
static Value * peekThroughBitcast(Value *V, bool OneUseOnly=false)
Return the source operand of a potentially bitcasted value while optionally checking if it has one us...
Definition: InstCombiner.h:101
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombiner.h:397
AssumptionCache & AC
Definition: InstCombiner.h:70
void addToWorklist(Instruction *I)
Definition: InstCombiner.h:367
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombiner.h:442
DominatorTree & DT
Definition: InstCombiner.h:72
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
Definition: InstCombiner.h:315
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:498
ProfileSummaryInfo * getProfileSummaryInfo() const
Definition: InstCombiner.h:378
OptimizationRemarkEmitter & getOptimizationRemarkEmitter() const
Definition: InstCombiner.h:374
ProfileSummaryInfo * PSI
Definition: InstCombiner.h:77
static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, bool &TrueIfSigned)
Given an exploded icmp instruction, return true if the comparison only checks the sign bit.
Definition: InstCombiner.h:165
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:461
BuilderTy & Builder
Definition: InstCombiner.h:58
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:369
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:477
OptimizationRemarkEmitter & ORE
Definition: InstCombiner.h:75
const SimplifyQuery & getSimplifyQuery() const
Definition: InstCombiner.h:373
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:202
unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:487
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
void pushUsersToWorkList(Instruction &I)
When an instruction is simplified, add all users of the instruction to the work lists because they mi...
void add(Instruction *I)
Add instruction to the worklist.
void push(Instruction *I)
Push the instruction onto the worklist stack.
void addValue(Value *V)
Add value to the worklist if it is an instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:358
const BasicBlock * getParent() const
Definition: Instruction.h:90
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
The optimization diagnostic interface.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1759
Analysis providing profile information.
This class represents the LLVM 'select' instruction.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Provides information about what library functions are available for the current target.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
bool use_empty() const
Definition: Value.h:344
iterator_range< use_iterator > uses()
Definition: Value.h:376
bool hasName() const
Definition: Value.h:261
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:381
self_iterator getIterator()
Definition: ilist_node.h:82
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:444
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:751
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > > > m_MaxOrMin(const LHS &L, const RHS &R)
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:991
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
OverflowResult
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
TargetTransformInfo TTI
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)