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 OptimizationRemarkEmitter;
38class ProfileSummaryInfo;
39class TargetLibraryInfo;
40class TargetTransformInfo;
41
42/// The core instruction combiner logic.
43///
44/// This class provides both the logic to recursively visit instructions and
45/// combine them.
47 /// Only used to call target specific intrinsic combining.
48 /// It must **NOT** be used for any other purpose, as InstCombine is a
49 /// target-independent canonicalization transform.
51
52public:
53 /// Maximum size of array considered when transforming.
54 uint64_t MaxArraySizeForCombine = 0;
55
56 /// An IRBuilder that automatically inserts new instructions into the
57 /// worklist.
60
61protected:
62 /// A worklist of the instructions that need to be simplified.
64
65 // Mode in which we are running the combiner.
66 const bool MinimizeSize;
67
69
70 // Required analyses.
74 const DataLayout &DL;
79
80 // Optional analyses. When non-null, these can both be used to do better
81 // combining and will be updated to reflect any changes.
83
84 bool MadeIRChange = false;
85
86public:
88 bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
92 const DataLayout &DL, LoopInfo *LI)
93 : TTI(TTI), Builder(Builder), Worklist(Worklist),
94 MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL),
95 SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}
96
97 virtual ~InstCombiner() = default;
98
99 /// Return the source operand of a potentially bitcasted value while
100 /// optionally checking if it has one use. If there is no bitcast or the one
101 /// use check is not met, return the input value itself.
102 static Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
103 if (auto *BitCast = dyn_cast<BitCastInst>(V))
104 if (!OneUseOnly || BitCast->hasOneUse())
105 return BitCast->getOperand(0);
106
107 // V is not a bitcast or V has more than one use and OneUseOnly is true.
108 return V;
109 }
110
111 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
112 /// the amount of pattern matching needed for compares and commutative
113 /// instructions. For example, if we have:
114 /// icmp ugt X, Constant
115 /// or
116 /// xor (add X, Constant), cast Z
117 ///
118 /// We do not have to consider the commuted variants of these patterns because
119 /// canonicalization based on complexity guarantees the above ordering.
120 ///
121 /// This routine maps IR values to various complexity ranks:
122 /// 0 -> undef
123 /// 1 -> Constants
124 /// 2 -> Other non-instructions
125 /// 3 -> Arguments
126 /// 4 -> Cast and (f)neg/not instructions
127 /// 5 -> Other instructions
128 static unsigned getComplexity(Value *V) {
129 if (isa<Instruction>(V)) {
130 if (isa<CastInst>(V) || match(V, m_Neg(PatternMatch::m_Value())) ||
133 return 4;
134 return 5;
135 }
136 if (isa<Argument>(V))
137 return 3;
138 return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
139 }
140
141 /// Predicate canonicalization reduces the number of patterns that need to be
142 /// matched by other transforms. For example, we may swap the operands of a
143 /// conditional branch or select to create a compare with a canonical
144 /// (inverted) predicate which is then more likely to be matched with other
145 /// values.
147 switch (Pred) {
148 case CmpInst::ICMP_NE:
153 // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
157 return false;
158 default:
159 return true;
160 }
161 }
162
163 /// Given an exploded icmp instruction, return true if the comparison only
164 /// checks the sign bit. If it only checks the sign bit, set TrueIfSigned if
165 /// the result of the comparison is true when the input value is signed.
166 static bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS,
167 bool &TrueIfSigned) {
168 switch (Pred) {
169 case ICmpInst::ICMP_SLT: // True if LHS s< 0
170 TrueIfSigned = true;
171 return RHS.isZero();
172 case ICmpInst::ICMP_SLE: // True if LHS s<= -1
173 TrueIfSigned = true;
174 return RHS.isAllOnes();
175 case ICmpInst::ICMP_SGT: // True if LHS s> -1
176 TrueIfSigned = false;
177 return RHS.isAllOnes();
178 case ICmpInst::ICMP_SGE: // True if LHS s>= 0
179 TrueIfSigned = false;
180 return RHS.isZero();
182 // True if LHS u> RHS and RHS == sign-bit-mask - 1
183 TrueIfSigned = true;
184 return RHS.isMaxSignedValue();
186 // True if LHS u>= RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
187 TrueIfSigned = true;
188 return RHS.isMinSignedValue();
190 // True if LHS u< RHS and RHS == sign-bit-mask (2^7, 2^15, 2^31, etc)
191 TrueIfSigned = false;
192 return RHS.isMinSignedValue();
194 // True if LHS u<= RHS and RHS == sign-bit-mask - 1
195 TrueIfSigned = false;
196 return RHS.isMaxSignedValue();
197 default:
198 return false;
199 }
200 }
201
202 /// Add one to a Constant
204 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
205 }
206
207 /// Subtract one from a Constant
209 return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
210 }
211
212 std::optional<std::pair<
214 Constant *>> static getFlippedStrictnessPredicateAndConstant(CmpInst::
215 Predicate
216 Pred,
217 Constant *C);
218
220 // a ? b : false and a ? true : b are the canonical form of logical and/or.
221 // This includes !a ? b : false and !a ? true : b. Absorbing the not into
222 // the select by swapping operands would break recognition of this pattern
223 // in other analyses, so don't do that.
228 }
229
230 /// Return true if the specified value is free to invert (apply ~ to).
231 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
232 /// is true, work under the assumption that the caller intends to remove all
233 /// uses of V and only keep uses of ~V.
234 ///
235 /// See also: canFreelyInvertAllUsersOf()
236 static bool isFreeToInvert(Value *V, bool WillInvertAllUses) {
237 // ~(~(X)) -> X.
239 return true;
240
241 // Constants can be considered to be not'ed values.
243 return true;
244
245 // Compares can be inverted if all of their uses are being modified to use
246 // the ~V.
247 if (isa<CmpInst>(V))
248 return WillInvertAllUses;
249
250 // If `V` is of the form `A + Constant` then `-1 - V` can be folded into
251 // `(-1 - Constant) - A` if we are willing to invert all of the uses.
253 return WillInvertAllUses;
254
255 // If `V` is of the form `Constant - A` then `-1 - V` can be folded into
256 // `A + (-1 - Constant)` if we are willing to invert all of the uses.
258 return WillInvertAllUses;
259
260 // Selects with invertible operands are freely invertible
261 if (match(V,
264 return WillInvertAllUses;
265
266 // Min/max may be in the form of intrinsics, so handle those identically
267 // to select patterns.
270 return WillInvertAllUses;
271
272 return false;
273 }
274
275 /// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
276 /// InstCombine's freelyInvertAllUsersOf() must be kept in sync with this fn.
277 /// NOTE: for Instructions only!
278 ///
279 /// See also: isFreeToInvert()
280 static bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser) {
281 // Look at every user of V.
282 for (Use &U : V->uses()) {
283 if (U.getUser() == IgnoredUser)
284 continue; // Don't consider this user.
285
286 auto *I = cast<Instruction>(U.getUser());
287 switch (I->getOpcode()) {
288 case Instruction::Select:
289 if (U.getOperandNo() != 0) // Only if the value is used as select cond.
290 return false;
291 if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(I)))
292 return false;
293 break;
294 case Instruction::Br:
295 assert(U.getOperandNo() == 0 && "Must be branching on that value.");
296 break; // Free to invert by swapping true/false values/destinations.
297 case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring
298 // it.
300 return false; // Not a 'not'.
301 break;
302 default:
303 return false; // Don't know, likely not freely invertible.
304 }
305 // So far all users were free to invert...
306 }
307 return true; // Can freely invert all users!
308 }
309
310 /// Some binary operators require special handling to avoid poison and
311 /// undefined behavior. If a constant vector has undef elements, replace those
312 /// undefs with identity constants if possible because those are always safe
313 /// to execute. If no identity constant exists, replace undef with some other
314 /// safe constant.
315 static Constant *
317 bool IsRHSConstant) {
318 auto *InVTy = cast<FixedVectorType>(In->getType());
319
320 Type *EltTy = InVTy->getElementType();
321 auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
322 if (!SafeC) {
323 // TODO: Should this be available as a constant utility function? It is
324 // similar to getBinOpAbsorber().
325 if (IsRHSConstant) {
326 switch (Opcode) {
327 case Instruction::SRem: // X % 1 = 0
328 case Instruction::URem: // X %u 1 = 0
329 SafeC = ConstantInt::get(EltTy, 1);
330 break;
331 case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
332 SafeC = ConstantFP::get(EltTy, 1.0);
333 break;
334 default:
336 "Only rem opcodes have no identity constant for RHS");
337 }
338 } else {
339 switch (Opcode) {
340 case Instruction::Shl: // 0 << X = 0
341 case Instruction::LShr: // 0 >>u X = 0
342 case Instruction::AShr: // 0 >> X = 0
343 case Instruction::SDiv: // 0 / X = 0
344 case Instruction::UDiv: // 0 /u X = 0
345 case Instruction::SRem: // 0 % X = 0
346 case Instruction::URem: // 0 %u X = 0
347 case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
348 case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
349 case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
350 case Instruction::FRem: // 0.0 % X = 0
351 SafeC = Constant::getNullValue(EltTy);
352 break;
353 default:
354 llvm_unreachable("Expected to find identity constant for opcode");
355 }
356 }
357 }
358 assert(SafeC && "Must have safe constant for binop");
359 unsigned NumElts = InVTy->getNumElements();
360 SmallVector<Constant *, 16> Out(NumElts);
361 for (unsigned i = 0; i != NumElts; ++i) {
362 Constant *C = In->getAggregateElement(i);
363 Out[i] = isa<UndefValue>(C) ? SafeC : C;
364 }
365 return ConstantVector::get(Out);
366 }
367
368 void addToWorklist(Instruction *I) { Worklist.push(I); }
369
370 AssumptionCache &getAssumptionCache() const { return AC; }
372 DominatorTree &getDominatorTree() const { return DT; }
373 const DataLayout &getDataLayout() const { return DL; }
374 const SimplifyQuery &getSimplifyQuery() const { return SQ; }
376 return ORE;
377 }
380 LoopInfo *getLoopInfo() const { return LI; }
381
382 // Call target specific combiners
383 std::optional<Instruction *> targetInstCombineIntrinsic(IntrinsicInst &II);
384 std::optional<Value *>
385 targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask,
386 KnownBits &Known,
387 bool &KnownBitsComputed);
388 std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
389 IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts,
390 APInt &UndefElts2, APInt &UndefElts3,
391 std::function<void(Instruction *, unsigned, APInt, APInt &)>
392 SimplifyAndSetOp);
393
394 /// Inserts an instruction \p New before instruction \p Old
395 ///
396 /// Also adds the new instruction to the worklist and returns \p New so that
397 /// it is suitable for use as the return from the visitation patterns.
399 assert(New && !New->getParent() &&
400 "New instruction already inserted into a basic block!");
401 BasicBlock *BB = Old.getParent();
402 New->insertInto(BB, Old.getIterator()); // Insert inst
403 Worklist.add(New);
404 return New;
405 }
406
407 /// Same as InsertNewInstBefore, but also sets the debug loc.
409 New->setDebugLoc(Old.getDebugLoc());
410 return InsertNewInstBefore(New, Old);
411 }
412
413 /// A combiner-aware RAUW-like routine.
414 ///
415 /// This method is to be used when an instruction is found to be dead,
416 /// replaceable with another preexisting expression. Here we add all uses of
417 /// I to the worklist, replace all uses of I with the new value, then return
418 /// I, so that the inst combiner will know that I was modified.
420 // If there are no uses to replace, then we return nullptr to indicate that
421 // no changes were made to the program.
422 if (I.use_empty()) return nullptr;
423
424 Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
425
426 // If we are replacing the instruction with itself, this must be in a
427 // segment of unreachable code, so just clobber the instruction.
428 if (&I == V)
429 V = PoisonValue::get(I.getType());
430
431 LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
432 << " with " << *V << '\n');
433
434 // If V is a new unnamed instruction, take the name from the old one.
435 if (V->use_empty() && isa<Instruction>(V) && !V->hasName() && I.hasName())
436 V->takeName(&I);
437
438 I.replaceAllUsesWith(V);
439 return &I;
440 }
441
442 /// Replace operand of instruction and add old operand to the worklist.
444 Worklist.addValue(I.getOperand(OpNum));
445 I.setOperand(OpNum, V);
446 return &I;
447 }
448
449 /// Replace use and add the previously used value to the worklist.
450 void replaceUse(Use &U, Value *NewValue) {
451 Worklist.addValue(U);
452 U = NewValue;
453 }
454
455 /// Combiner aware instruction erasure.
456 ///
457 /// When dealing with an instruction that has side effects or produces a void
458 /// value, we can't rely on DCE to delete the instruction. Instead, visit
459 /// methods should return the value returned by this function.
461
462 void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
463 const Instruction *CxtI) const {
464 llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
465 }
466
468 const Instruction *CxtI) const {
469 return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
470 }
471
472 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
473 unsigned Depth = 0,
474 const Instruction *CxtI = nullptr) {
475 return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
476 }
477
478 bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
479 const Instruction *CxtI = nullptr) const {
480 return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
481 }
482
483 unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
484 const Instruction *CxtI = nullptr) const {
485 return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
486 }
487
488 unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth = 0,
489 const Instruction *CxtI = nullptr) const {
490 return llvm::ComputeMaxSignificantBits(Op, DL, Depth, &AC, CxtI, &DT);
491 }
492
494 const Value *RHS,
495 const Instruction *CxtI) const {
496 return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
497 }
498
500 const Instruction *CxtI) const {
501 return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
502 }
503
505 const Value *RHS,
506 const Instruction *CxtI) const {
507 return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
508 }
509
511 const Instruction *CxtI) const {
512 return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
513 }
514
516 const Value *RHS,
517 const Instruction *CxtI) const {
518 return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
519 }
520
522 const Instruction *CxtI) const {
523 return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
524 }
525
526 virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo,
527 const APInt &DemandedMask, KnownBits &Known,
528 unsigned Depth = 0) = 0;
529 virtual Value *
530 SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
531 unsigned Depth = 0,
532 bool AllowMultipleUsers = false) = 0;
533
534 bool isValidAddrSpaceCast(unsigned FromAS, unsigned ToAS) const;
535};
536
537} // namespace llvm
538
539#undef DEBUG_TYPE
540
541#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:701
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
@ ICMP_SLT
signed less than
Definition: InstrTypes.h:740
@ ICMP_SLE
signed less or equal
Definition: InstrTypes.h:741
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:716
@ ICMP_UGE
unsigned greater or equal
Definition: InstrTypes.h:735
@ ICMP_UGT
unsigned greater than
Definition: InstrTypes.h:734
@ ICMP_SGT
signed greater than
Definition: InstrTypes.h:738
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
Definition: InstrTypes.h:719
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:736
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:718
@ ICMP_NE
not equal
Definition: InstrTypes.h:733
@ ICMP_SGE
signed greater or equal
Definition: InstrTypes.h:739
@ ICMP_ULE
unsigned less or equal
Definition: InstrTypes.h:737
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2600
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2593
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false, bool NSZ=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2672
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:927
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:888
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1342
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:110
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:46
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:521
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:280
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:373
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:146
virtual Instruction * eraseInstFromFunction(Instruction &I)=0
Combiner aware instruction erasure.
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:372
virtual ~InstCombiner()=default
LoopInfo * getLoopInfo() const
Definition: InstCombiner.h:380
BlockFrequencyInfo * BFI
Definition: InstCombiner.h:77
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
Definition: InstCombiner.h:408
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:128
TargetLibraryInfo & TLI
Definition: InstCombiner.h:72
TargetLibraryInfo & getTargetLibraryInfo() const
Definition: InstCombiner.h:371
BlockFrequencyInfo * getBlockFrequencyInfo() const
Definition: InstCombiner.h:378
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombiner.h:472
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:493
AAResults * AA
Definition: InstCombiner.h:68
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:419
static bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Return true if the specified value is free to invert (apply ~ to).
Definition: InstCombiner.h:236
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:219
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:510
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
Definition: InstCombiner.h:208
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:467
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombiner.h:450
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:87
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:515
const SimplifyQuery SQ
Definition: InstCombiner.h:75
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:63
const DataLayout & DL
Definition: InstCombiner.h:74
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:483
const bool MinimizeSize
Definition: InstCombiner.h:66
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:504
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:102
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombiner.h:398
AssumptionCache & AC
Definition: InstCombiner.h:71
void addToWorklist(Instruction *I)
Definition: InstCombiner.h:368
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombiner.h:443
DominatorTree & DT
Definition: InstCombiner.h:73
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:316
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:499
ProfileSummaryInfo * getProfileSummaryInfo() const
Definition: InstCombiner.h:379
OptimizationRemarkEmitter & getOptimizationRemarkEmitter() const
Definition: InstCombiner.h:375
ProfileSummaryInfo * PSI
Definition: InstCombiner.h:78
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:166
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:462
BuilderTy & Builder
Definition: InstCombiner.h:59
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:370
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:478
OptimizationRemarkEmitter & ORE
Definition: InstCombiner.h:76
const SimplifyQuery & getSimplifyQuery() const
Definition: InstCombiner.h:374
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:203
unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:488
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:365
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:1743
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
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, 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)