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