LLVM 20.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
26#include "llvm/IR/IRBuilder.h"
28#include "llvm/Support/Debug.h"
30#include <cassert>
31
32#define DEBUG_TYPE "instcombine"
34
35namespace llvm {
36
37class AAResults;
38class AssumptionCache;
39class OptimizationRemarkEmitter;
40class ProfileSummaryInfo;
41class TargetLibraryInfo;
42class TargetTransformInfo;
43
44/// The core instruction combiner logic.
45///
46/// This class provides both the logic to recursively visit instructions and
47/// combine them.
49 /// Only used to call target specific intrinsic combining.
50 /// It must **NOT** be used for any other purpose, as InstCombine is a
51 /// target-independent canonicalization transform.
52 TargetTransformInfo &TTIForTargetIntrinsicsOnly;
53
54public:
55 /// Maximum size of array considered when transforming.
56 uint64_t MaxArraySizeForCombine = 0;
57
58 /// An IRBuilder that automatically inserts new instructions into the
59 /// worklist.
62
63protected:
64 /// A worklist of the instructions that need to be simplified.
66
67 // Mode in which we are running the combiner.
68 const bool MinimizeSize;
69
71
72 // Required analyses.
76 const DataLayout &DL;
83
85
86 bool MadeIRChange = false;
87
88 /// Edges that are known to never be taken.
90
91 /// Order of predecessors to canonicalize phi nodes towards.
93
94 /// Backedges, used to avoid pushing instructions across backedges in cases
95 /// where this may result in infinite combine loops. For irreducible loops
96 /// this picks an arbitrary backedge.
98 bool ComputedBackEdges = false;
99
100public:
102 bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
106 ProfileSummaryInfo *PSI, const DataLayout &DL,
108 : TTIForTargetIntrinsicsOnly(TTI), Builder(Builder), Worklist(Worklist),
109 MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL),
110 SQ(DL, &TLI, &DT, &AC, nullptr, /*UseInstrInfo*/ true,
111 /*CanUseUndef*/ true, &DC),
112 ORE(ORE), BFI(BFI), BPI(BPI), PSI(PSI), RPOT(RPOT) {}
113
114 virtual ~InstCombiner() = default;
115
116 /// Return the source operand of a potentially bitcasted value while
117 /// optionally checking if it has one use. If there is no bitcast or the one
118 /// use check is not met, return the input value itself.
119 static Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
120 if (auto *BitCast = dyn_cast<BitCastInst>(V))
121 if (!OneUseOnly || BitCast->hasOneUse())
122 return BitCast->getOperand(0);
123
124 // V is not a bitcast or V has more than one use and OneUseOnly is true.
125 return V;
126 }
127
128 /// Assign a complexity or rank value to LLVM Values. This is used to reduce
129 /// the amount of pattern matching needed for compares and commutative
130 /// instructions. For example, if we have:
131 /// icmp ugt X, Constant
132 /// or
133 /// xor (add X, Constant), cast Z
134 ///
135 /// We do not have to consider the commuted variants of these patterns because
136 /// canonicalization based on complexity guarantees the above ordering.
137 ///
138 /// This routine maps IR values to various complexity ranks:
139 /// 0 -> undef
140 /// 1 -> Constants
141 /// 2 -> Cast and (f)neg/not instructions
142 /// 3 -> Other instructions and arguments
143 static unsigned getComplexity(Value *V) {
144 if (isa<Constant>(V))
145 return isa<UndefValue>(V) ? 0 : 1;
146
147 if (isa<CastInst>(V) || match(V, m_Neg(PatternMatch::m_Value())) ||
148 match(V, m_Not(PatternMatch::m_Value())) ||
149 match(V, m_FNeg(PatternMatch::m_Value())))
150 return 2;
151
152 return 3;
153 }
154
155 /// Predicate canonicalization reduces the number of patterns that need to be
156 /// matched by other transforms. For example, we may swap the operands of a
157 /// conditional branch or select to create a compare with a canonical
158 /// (inverted) predicate which is then more likely to be matched with other
159 /// values.
161 switch (Pred) {
162 case CmpInst::ICMP_NE:
163 case CmpInst::ICMP_ULE:
164 case CmpInst::ICMP_SLE:
165 case CmpInst::ICMP_UGE:
166 case CmpInst::ICMP_SGE:
167 // TODO: There are 16 FCMP predicates. Should others be (not) canonical?
168 case CmpInst::FCMP_ONE:
169 case CmpInst::FCMP_OLE:
170 case CmpInst::FCMP_OGE:
171 return false;
172 default:
173 return true;
174 }
175 }
176
177 /// Add one to a Constant
179 return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
180 }
181
182 /// Subtract one from a Constant
184 return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
185 }
186
187 std::optional<std::pair<
189 Constant *>> static getFlippedStrictnessPredicateAndConstant(CmpPredicate
190 Pred,
191 Constant *C);
192
194 // a ? b : false and a ? true : b are the canonical form of logical and/or.
195 // This includes !a ? b : false and !a ? true : b. Absorbing the not into
196 // the select by swapping operands would break recognition of this pattern
197 // in other analyses, so don't do that.
198 return match(&SI, PatternMatch::m_LogicalAnd(PatternMatch::m_Value(),
199 PatternMatch::m_Value())) ||
200 match(&SI, PatternMatch::m_LogicalOr(PatternMatch::m_Value(),
201 PatternMatch::m_Value()));
202 }
203
204 /// Return nonnull value if V is free to invert under the condition of
205 /// WillInvertAllUses.
206 /// If Builder is nonnull, it will return a simplified ~V.
207 /// If Builder is null, it will return an arbitrary nonnull value (not
208 /// dereferenceable).
209 /// If the inversion will consume instructions, `DoesConsume` will be set to
210 /// true. Otherwise it will be false.
211 Value *getFreelyInvertedImpl(Value *V, bool WillInvertAllUses,
212 BuilderTy *Builder, bool &DoesConsume,
213 unsigned Depth);
214
215 Value *getFreelyInverted(Value *V, bool WillInvertAllUses,
216 BuilderTy *Builder, bool &DoesConsume) {
217 DoesConsume = false;
218 return getFreelyInvertedImpl(V, WillInvertAllUses, Builder, DoesConsume,
219 /*Depth*/ 0);
220 }
221
222 Value *getFreelyInverted(Value *V, bool WillInvertAllUses,
223 BuilderTy *Builder) {
224 bool Unused;
225 return getFreelyInverted(V, WillInvertAllUses, Builder, Unused);
226 }
227
228 /// Return true if the specified value is free to invert (apply ~ to).
229 /// This happens in cases where the ~ can be eliminated. If WillInvertAllUses
230 /// is true, work under the assumption that the caller intends to remove all
231 /// uses of V and only keep uses of ~V.
232 ///
233 /// See also: canFreelyInvertAllUsersOf()
234 bool isFreeToInvert(Value *V, bool WillInvertAllUses,
235 bool &DoesConsume) {
236 return getFreelyInverted(V, WillInvertAllUses, /*Builder*/ nullptr,
237 DoesConsume) != nullptr;
238 }
239
240 bool isFreeToInvert(Value *V, bool WillInvertAllUses) {
241 bool Unused;
242 return isFreeToInvert(V, WillInvertAllUses, Unused);
243 }
244
245 /// Given i1 V, can every user of V be freely adapted if V is changed to !V ?
246 /// InstCombine's freelyInvertAllUsersOf() must be kept in sync with this fn.
247 /// NOTE: for Instructions only!
248 ///
249 /// See also: isFreeToInvert()
251 // Look at every user of V.
252 for (Use &U : V->uses()) {
253 if (U.getUser() == IgnoredUser)
254 continue; // Don't consider this user.
255
256 auto *I = cast<Instruction>(U.getUser());
257 switch (I->getOpcode()) {
258 case Instruction::Select:
259 if (U.getOperandNo() != 0) // Only if the value is used as select cond.
260 return false;
261 if (shouldAvoidAbsorbingNotIntoSelect(*cast<SelectInst>(I)))
262 return false;
263 break;
264 case Instruction::Br:
265 assert(U.getOperandNo() == 0 && "Must be branching on that value.");
266 break; // Free to invert by swapping true/false values/destinations.
267 case Instruction::Xor: // Can invert 'xor' if it's a 'not', by ignoring
268 // it.
269 if (!match(I, m_Not(PatternMatch::m_Value())))
270 return false; // Not a 'not'.
271 break;
272 default:
273 return false; // Don't know, likely not freely invertible.
274 }
275 // So far all users were free to invert...
276 }
277 return true; // Can freely invert all users!
278 }
279
280 /// Some binary operators require special handling to avoid poison and
281 /// undefined behavior. If a constant vector has undef elements, replace those
282 /// undefs with identity constants if possible because those are always safe
283 /// to execute. If no identity constant exists, replace undef with some other
284 /// safe constant.
285 static Constant *
287 bool IsRHSConstant) {
288 auto *InVTy = cast<FixedVectorType>(In->getType());
289
290 Type *EltTy = InVTy->getElementType();
291 auto *SafeC = ConstantExpr::getBinOpIdentity(Opcode, EltTy, IsRHSConstant);
292 if (!SafeC) {
293 // TODO: Should this be available as a constant utility function? It is
294 // similar to getBinOpAbsorber().
295 if (IsRHSConstant) {
296 switch (Opcode) {
297 case Instruction::SRem: // X % 1 = 0
298 case Instruction::URem: // X %u 1 = 0
299 SafeC = ConstantInt::get(EltTy, 1);
300 break;
301 case Instruction::FRem: // X % 1.0 (doesn't simplify, but it is safe)
302 SafeC = ConstantFP::get(EltTy, 1.0);
303 break;
304 default:
306 "Only rem opcodes have no identity constant for RHS");
307 }
308 } else {
309 switch (Opcode) {
310 case Instruction::Shl: // 0 << X = 0
311 case Instruction::LShr: // 0 >>u X = 0
312 case Instruction::AShr: // 0 >> X = 0
313 case Instruction::SDiv: // 0 / X = 0
314 case Instruction::UDiv: // 0 /u X = 0
315 case Instruction::SRem: // 0 % X = 0
316 case Instruction::URem: // 0 %u X = 0
317 case Instruction::Sub: // 0 - X (doesn't simplify, but it is safe)
318 case Instruction::FSub: // 0.0 - X (doesn't simplify, but it is safe)
319 case Instruction::FDiv: // 0.0 / X (doesn't simplify, but it is safe)
320 case Instruction::FRem: // 0.0 % X = 0
321 SafeC = Constant::getNullValue(EltTy);
322 break;
323 default:
324 llvm_unreachable("Expected to find identity constant for opcode");
325 }
326 }
327 }
328 assert(SafeC && "Must have safe constant for binop");
329 unsigned NumElts = InVTy->getNumElements();
330 SmallVector<Constant *, 16> Out(NumElts);
331 for (unsigned i = 0; i != NumElts; ++i) {
332 Constant *C = In->getAggregateElement(i);
333 Out[i] = isa<UndefValue>(C) ? SafeC : C;
334 }
335 return ConstantVector::get(Out);
336 }
337
338 void addToWorklist(Instruction *I) { Worklist.push(I); }
339
340 AssumptionCache &getAssumptionCache() const { return AC; }
342 DominatorTree &getDominatorTree() const { return DT; }
343 const DataLayout &getDataLayout() const { return DL; }
344 const SimplifyQuery &getSimplifyQuery() const { return SQ; }
346 return ORE;
347 }
350
351 // Call target specific combiners
352 std::optional<Instruction *> targetInstCombineIntrinsic(IntrinsicInst &II);
353 std::optional<Value *>
354 targetSimplifyDemandedUseBitsIntrinsic(IntrinsicInst &II, APInt DemandedMask,
355 KnownBits &Known,
356 bool &KnownBitsComputed);
357 std::optional<Value *> targetSimplifyDemandedVectorEltsIntrinsic(
358 IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts,
359 APInt &UndefElts2, APInt &UndefElts3,
360 std::function<void(Instruction *, unsigned, APInt, APInt &)>
361 SimplifyAndSetOp);
362
363 void computeBackEdges();
364 bool isBackEdge(const BasicBlock *From, const BasicBlock *To) {
365 if (!ComputedBackEdges)
366 computeBackEdges();
367 return BackEdges.contains({From, To});
368 }
369
370 /// Inserts an instruction \p New before instruction \p Old
371 ///
372 /// Also adds the new instruction to the worklist and returns \p New so that
373 /// it is suitable for use as the return from the visitation patterns.
375 assert(New && !New->getParent() &&
376 "New instruction already inserted into a basic block!");
377 New->insertBefore(Old); // Insert inst
378 Worklist.add(New);
379 return New;
380 }
381
382 /// Same as InsertNewInstBefore, but also sets the debug loc.
384 New->setDebugLoc(Old->getDebugLoc());
385 return InsertNewInstBefore(New, Old);
386 }
387
388 /// A combiner-aware RAUW-like routine.
389 ///
390 /// This method is to be used when an instruction is found to be dead,
391 /// replaceable with another preexisting expression. Here we add all uses of
392 /// I to the worklist, replace all uses of I with the new value, then return
393 /// I, so that the inst combiner will know that I was modified.
395 // If there are no uses to replace, then we return nullptr to indicate that
396 // no changes were made to the program.
397 if (I.use_empty()) return nullptr;
398
399 Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
400
401 // If we are replacing the instruction with itself, this must be in a
402 // segment of unreachable code, so just clobber the instruction.
403 if (&I == V)
404 V = PoisonValue::get(I.getType());
405
406 LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
407 << " with " << *V << '\n');
408
409 // If V is a new unnamed instruction, take the name from the old one.
410 if (V->use_empty() && isa<Instruction>(V) && !V->hasName() && I.hasName())
411 V->takeName(&I);
412
413 I.replaceAllUsesWith(V);
414 return &I;
415 }
416
417 /// Replace operand of instruction and add old operand to the worklist.
419 Value *OldOp = I.getOperand(OpNum);
420 I.setOperand(OpNum, V);
421 Worklist.handleUseCountDecrement(OldOp);
422 return &I;
423 }
424
425 /// Replace use and add the previously used value to the worklist.
426 void replaceUse(Use &U, Value *NewValue) {
427 Value *OldOp = U;
428 U = NewValue;
429 Worklist.handleUseCountDecrement(OldOp);
430 }
431
432 /// Combiner aware instruction erasure.
433 ///
434 /// When dealing with an instruction that has side effects or produces a void
435 /// value, we can't rely on DCE to delete the instruction. Instead, visit
436 /// methods should return the value returned by this function.
438
439 void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
440 const Instruction *CxtI) const {
442 }
443
444 KnownBits computeKnownBits(const Value *V, unsigned Depth,
445 const Instruction *CxtI) const {
447 }
448
449 bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
450 unsigned Depth = 0,
451 const Instruction *CxtI = nullptr) {
452 return llvm::isKnownToBeAPowerOfTwo(V, OrZero, Depth,
453 SQ.getWithInstruction(CxtI));
454 }
455
456 bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
457 const Instruction *CxtI = nullptr) const {
458 return llvm::MaskedValueIsZero(V, Mask, SQ.getWithInstruction(CxtI), Depth);
459 }
460
461 unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
462 const Instruction *CxtI = nullptr) const {
463 return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
464 }
465
466 unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth = 0,
467 const Instruction *CxtI = nullptr) const {
468 return llvm::ComputeMaxSignificantBits(Op, DL, Depth, &AC, CxtI, &DT);
469 }
470
472 const Value *RHS,
473 const Instruction *CxtI,
474 bool IsNSW = false) const {
476 LHS, RHS, SQ.getWithInstruction(CxtI), IsNSW);
477 }
478
480 const Instruction *CxtI) const {
482 SQ.getWithInstruction(CxtI));
483 }
484
488 const Instruction *CxtI) const {
490 SQ.getWithInstruction(CxtI));
491 }
492
496 const Instruction *CxtI) const {
498 SQ.getWithInstruction(CxtI));
499 }
500
502 const Value *RHS,
503 const Instruction *CxtI) const {
505 SQ.getWithInstruction(CxtI));
506 }
507
509 const Instruction *CxtI) const {
511 SQ.getWithInstruction(CxtI));
512 }
513
514 virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo,
515 const APInt &DemandedMask, KnownBits &Known,
516 unsigned Depth, const SimplifyQuery &Q) = 0;
517
518 bool SimplifyDemandedBits(Instruction *I, unsigned OpNo,
519 const APInt &DemandedMask, KnownBits &Known) {
520 return SimplifyDemandedBits(I, OpNo, DemandedMask, Known,
521 /*Depth=*/0, SQ.getWithInstruction(I));
522 }
523
524 virtual Value *
525 SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
526 unsigned Depth = 0,
527 bool AllowMultipleUsers = false) = 0;
528
529 bool isValidAddrSpaceCast(unsigned FromAS, unsigned ToAS) const;
530};
531
532} // namespace llvm
533
534#undef DEBUG_TYPE
535
536#endif
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
basic Basic Alias true
BlockVerifier::State From
IRBuilder< TargetFolder > BuilderTy
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
#define LLVM_LIBRARY_VISIBILITY
Definition: Compiler.h:133
#define LLVM_DEBUG(...)
Definition: Debug.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t IntrinsicInst * II
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:78
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Analysis providing branch probability information.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
Definition: CmpPredicate.h:22
This is an important base class in LLVM.
Definition: Constant.h:42
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:63
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
The core instruction combiner logic.
Definition: InstCombiner.h:48
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:508
SimplifyQuery SQ
Definition: InstCombiner.h:77
const DataLayout & getDataLayout() const
Definition: InstCombiner.h:343
bool isFreeToInvert(Value *V, bool WillInvertAllUses)
Definition: InstCombiner.h:240
virtual Instruction * eraseInstFromFunction(Instruction &I)=0
Combiner aware instruction erasure.
bool isFreeToInvert(Value *V, bool WillInvertAllUses, bool &DoesConsume)
Return true if the specified value is free to invert (apply ~ to).
Definition: InstCombiner.h:234
DominatorTree & getDominatorTree() const
Definition: InstCombiner.h:342
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI, bool IsNSW=false) const
Definition: InstCombiner.h:471
virtual ~InstCombiner()=default
BlockFrequencyInfo * BFI
Definition: InstCombiner.h:79
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
Definition: InstCombiner.h:143
SmallDenseMap< BasicBlock *, SmallVector< BasicBlock * >, 8 > PredOrder
Order of predecessors to canonicalize phi nodes towards.
Definition: InstCombiner.h:92
TargetLibraryInfo & TLI
Definition: InstCombiner.h:74
TargetLibraryInfo & getTargetLibraryInfo() const
Definition: InstCombiner.h:341
BlockFrequencyInfo * getBlockFrequencyInfo() const
Definition: InstCombiner.h:348
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombiner.h:449
Instruction * InsertNewInstBefore(Instruction *New, BasicBlock::iterator Old)
Inserts an instruction New before instruction Old.
Definition: InstCombiner.h:374
AAResults * AA
Definition: InstCombiner.h:70
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombiner.h:394
static bool shouldAvoidAbsorbingNotIntoSelect(const SelectInst &SI)
Definition: InstCombiner.h:193
OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:494
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
Definition: InstCombiner.h:183
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:444
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombiner.h:426
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:501
static bool isCanonicalPredicate(CmpPredicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
Definition: InstCombiner.h:160
InstructionWorklist & Worklist
A worklist of the instructions that need to be simplified.
Definition: InstCombiner.h:65
Instruction * InsertNewInstWith(Instruction *New, BasicBlock::iterator Old)
Same as InsertNewInstBefore, but also sets the debug loc.
Definition: InstCombiner.h:383
BranchProbabilityInfo * BPI
Definition: InstCombiner.h:80
bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known)
Definition: InstCombiner.h:518
ReversePostOrderTraversal< BasicBlock * > & RPOT
Definition: InstCombiner.h:84
const DataLayout & DL
Definition: InstCombiner.h:76
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:461
DomConditionCache DC
Definition: InstCombiner.h:82
const bool MinimizeSize
Definition: InstCombiner.h:68
virtual bool SimplifyDemandedBits(Instruction *I, unsigned OpNo, const APInt &DemandedMask, KnownBits &Known, unsigned Depth, const SimplifyQuery &Q)=0
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:119
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:250
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder)
Definition: InstCombiner.h:222
AssumptionCache & AC
Definition: InstCombiner.h:73
void addToWorklist(Instruction *I)
Definition: InstCombiner.h:338
SmallDenseSet< std::pair< const BasicBlock *, const BasicBlock * >, 8 > BackEdges
Backedges, used to avoid pushing instructions across backedges in cases where this may result in infi...
Definition: InstCombiner.h:97
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombiner.h:418
DominatorTree & DT
Definition: InstCombiner.h:75
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:286
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:479
ProfileSummaryInfo * getProfileSummaryInfo() const
Definition: InstCombiner.h:349
OptimizationRemarkEmitter & getOptimizationRemarkEmitter() const
Definition: InstCombiner.h:345
ProfileSummaryInfo * PSI
Definition: InstCombiner.h:81
SmallDenseSet< std::pair< BasicBlock *, BasicBlock * >, 8 > DeadEdges
Edges that are known to never be taken.
Definition: InstCombiner.h:89
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombiner.h:439
BuilderTy & Builder
Definition: InstCombiner.h:61
AssumptionCache & getAssumptionCache() const
Definition: InstCombiner.h:340
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:456
OptimizationRemarkEmitter & ORE
Definition: InstCombiner.h:78
OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const Instruction *CxtI) const
Definition: InstCombiner.h:486
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume)
Definition: InstCombiner.h:215
const SimplifyQuery & getSimplifyQuery() const
Definition: InstCombiner.h:344
bool isBackEdge(const BasicBlock *From, const BasicBlock *To)
Definition: InstCombiner.h:364
InstCombiner(InstructionWorklist &Worklist, BuilderTy &Builder, bool MinimizeSize, AAResults *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI, ProfileSummaryInfo *PSI, const DataLayout &DL, ReversePostOrderTraversal< BasicBlock * > &RPOT)
Definition: InstCombiner.h:101
static Constant * AddOne(Constant *C)
Add one to a Constant.
Definition: InstCombiner.h:178
unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombiner.h:466
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:48
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:298
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
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 contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:193
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
OverflowResult
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.
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const SimplifyQuery &SQ, unsigned Depth=0)
Return true if 'V & Mask' is known to be zero.
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ, bool IsNSW=false)
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)
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...
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const SimplifyQuery &SQ)
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.
OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const SimplifyQuery &SQ)
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.
SimplifyQuery getWithInstruction(const Instruction *I) const