LLVM 17.0.0git
InstCombineInternal.h
Go to the documentation of this file.
1//===- InstCombineInternal.h - InstCombine pass internals -------*- 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//
9/// \file
10///
11/// This file provides internal interfaces used to implement the InstCombine.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
16#define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
17
18#include "llvm/ADT/Statistic.h"
22#include "llvm/IR/IRBuilder.h"
23#include "llvm/IR/InstVisitor.h"
25#include "llvm/IR/Value.h"
26#include "llvm/Support/Debug.h"
30#include <cassert>
31
32#define DEBUG_TYPE "instcombine"
34
35using namespace llvm::PatternMatch;
36
37// As a default, let's assume that we want to be aggressive,
38// and attempt to traverse with no limits in attempt to sink negation.
39static constexpr unsigned NegatorDefaultMaxDepth = ~0U;
40
41// Let's guesstimate that most often we will end up visiting/producing
42// fairly small number of new instructions.
43static constexpr unsigned NegatorMaxNodesSSO = 16;
44
45namespace llvm {
46
47class AAResults;
48class APInt;
49class AssumptionCache;
51class DataLayout;
52class DominatorTree;
53class GEPOperator;
54class GlobalVariable;
55class LoopInfo;
59class User;
60
62 : public InstCombiner,
63 public InstVisitor<InstCombinerImpl, Instruction *> {
64public:
66 bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
70 const DataLayout &DL, LoopInfo *LI)
71 : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
72 BFI, PSI, DL, LI) {}
73
74 virtual ~InstCombinerImpl() = default;
75
76 /// Run the combiner over the entire worklist until it is empty.
77 ///
78 /// \returns true if the IR is changed.
79 bool run();
80
81 // Visitation implementation - Implement instruction combining for different
82 // instruction types. The semantics are as follows:
83 // Return Value:
84 // null - No change was made
85 // I - Change was made, I is still valid, I may be dead though
86 // otherwise - Change was made, replace I with returned instruction
87 //
88 Instruction *visitFNeg(UnaryOperator &I);
89 Instruction *visitAdd(BinaryOperator &I);
90 Instruction *visitFAdd(BinaryOperator &I);
91 Value *OptimizePointerDifference(
92 Value *LHS, Value *RHS, Type *Ty, bool isNUW);
93 Instruction *visitSub(BinaryOperator &I);
94 Instruction *visitFSub(BinaryOperator &I);
95 Instruction *visitMul(BinaryOperator &I);
96 Instruction *visitFMul(BinaryOperator &I);
97 Instruction *visitURem(BinaryOperator &I);
98 Instruction *visitSRem(BinaryOperator &I);
99 Instruction *visitFRem(BinaryOperator &I);
100 bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
101 Instruction *commonIRemTransforms(BinaryOperator &I);
102 Instruction *commonIDivTransforms(BinaryOperator &I);
103 Instruction *visitUDiv(BinaryOperator &I);
104 Instruction *visitSDiv(BinaryOperator &I);
105 Instruction *visitFDiv(BinaryOperator &I);
106 Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
107 Instruction *visitAnd(BinaryOperator &I);
108 Instruction *visitOr(BinaryOperator &I);
109 bool sinkNotIntoLogicalOp(Instruction &I);
110 bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I);
111 Instruction *visitXor(BinaryOperator &I);
112 Instruction *visitShl(BinaryOperator &I);
113 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
114 BinaryOperator *Sh0, const SimplifyQuery &SQ,
115 bool AnalyzeForSignBitExtraction = false);
116 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
118 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
119 BinaryOperator &OldAShr);
120 Instruction *visitAShr(BinaryOperator &I);
121 Instruction *visitLShr(BinaryOperator &I);
122 Instruction *commonShiftTransforms(BinaryOperator &I);
123 Instruction *visitFCmpInst(FCmpInst &I);
124 CmpInst *canonicalizeICmpPredicate(CmpInst &I);
125 Instruction *visitICmpInst(ICmpInst &I);
126 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
128 Instruction *commonCastTransforms(CastInst &CI);
129 Instruction *commonPointerCastTransforms(CastInst &CI);
130 Instruction *visitTrunc(TruncInst &CI);
131 Instruction *visitZExt(ZExtInst &Zext);
132 Instruction *visitSExt(SExtInst &Sext);
133 Instruction *visitFPTrunc(FPTruncInst &CI);
134 Instruction *visitFPExt(CastInst &CI);
135 Instruction *visitFPToUI(FPToUIInst &FI);
136 Instruction *visitFPToSI(FPToSIInst &FI);
137 Instruction *visitUIToFP(CastInst &CI);
138 Instruction *visitSIToFP(CastInst &CI);
139 Instruction *visitPtrToInt(PtrToIntInst &CI);
140 Instruction *visitIntToPtr(IntToPtrInst &CI);
141 Instruction *visitBitCast(BitCastInst &CI);
142 Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
143 Instruction *foldItoFPtoI(CastInst &FI);
145 Instruction *visitCallInst(CallInst &CI);
146 Instruction *visitInvokeInst(InvokeInst &II);
147 Instruction *visitCallBrInst(CallBrInst &CBI);
148
149 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
150 Instruction *visitPHINode(PHINode &PN);
151 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
152 Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
153 Instruction *visitGEPOfBitcast(BitCastInst *BCI, GetElementPtrInst &GEP);
154 Instruction *visitAllocaInst(AllocaInst &AI);
155 Instruction *visitAllocSite(Instruction &FI);
156 Instruction *visitFree(CallInst &FI, Value *FreedOp);
157 Instruction *visitLoadInst(LoadInst &LI);
158 Instruction *visitStoreInst(StoreInst &SI);
159 Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
160 Instruction *visitUnconditionalBranchInst(BranchInst &BI);
161 Instruction *visitBranchInst(BranchInst &BI);
162 Instruction *visitFenceInst(FenceInst &FI);
163 Instruction *visitSwitchInst(SwitchInst &SI);
164 Instruction *visitReturnInst(ReturnInst &RI);
165 Instruction *visitUnreachableInst(UnreachableInst &I);
167 foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
168 Instruction *visitInsertValueInst(InsertValueInst &IV);
169 Instruction *visitInsertElementInst(InsertElementInst &IE);
170 Instruction *visitExtractElementInst(ExtractElementInst &EI);
171 Instruction *simplifyBinOpSplats(ShuffleVectorInst &SVI);
172 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
173 Instruction *visitExtractValueInst(ExtractValueInst &EV);
174 Instruction *visitLandingPadInst(LandingPadInst &LI);
175 Instruction *visitVAEndInst(VAEndInst &I);
176 Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
177 bool freezeOtherUses(FreezeInst &FI);
178 Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
179 Instruction *visitFreeze(FreezeInst &I);
180
181 /// Specify what to return for unhandled instructions.
183
184 /// True when DB dominates all uses of DI except UI.
185 /// UI must be in the same block as DI.
186 /// The routine checks that the DI parent and DB are different.
187 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
188 const BasicBlock *DB) const;
189
190 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
191 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
192 const unsigned SIOpd);
193
194 LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
195 const Twine &Suffix = "");
196
197private:
198 bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
199 bool isDesirableIntType(unsigned BitWidth) const;
200 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
201 bool shouldChangeType(Type *From, Type *To) const;
202 Value *dyn_castNegVal(Value *V) const;
203
204 /// Classify whether a cast is worth optimizing.
205 ///
206 /// This is a helper to decide whether the simplification of
207 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
208 ///
209 /// \param CI The cast we are interested in.
210 ///
211 /// \return true if this cast actually results in any code being generated and
212 /// if it cannot already be eliminated by some other transformation.
213 bool shouldOptimizeCast(CastInst *CI);
214
215 /// Try to optimize a sequence of instructions checking if an operation
216 /// on LHS and RHS overflows.
217 ///
218 /// If this overflow check is done via one of the overflow check intrinsics,
219 /// then CtxI has to be the call instruction calling that intrinsic. If this
220 /// overflow check is done by arithmetic followed by a compare, then CtxI has
221 /// to be the arithmetic instruction.
222 ///
223 /// If a simplification is possible, stores the simplified result of the
224 /// operation in OperationResult and result of the overflow check in
225 /// OverflowResult, and return true. If no simplification is possible,
226 /// returns false.
227 bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
228 Value *LHS, Value *RHS,
229 Instruction &CtxI, Value *&OperationResult,
231
232 Instruction *visitCallBase(CallBase &Call);
233 Instruction *tryOptimizeCall(CallInst *CI);
234 bool transformConstExprCastCall(CallBase &Call);
235 Instruction *transformCallThroughTrampoline(CallBase &Call,
236 IntrinsicInst &Tramp);
237
238 Value *simplifyMaskedLoad(IntrinsicInst &II);
239 Instruction *simplifyMaskedStore(IntrinsicInst &II);
240 Instruction *simplifyMaskedGather(IntrinsicInst &II);
241 Instruction *simplifyMaskedScatter(IntrinsicInst &II);
242
243 /// Transform (zext icmp) to bitwise / integer operations in order to
244 /// eliminate it.
245 ///
246 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
247 /// \parem CI The zext of the (zext icmp) pair we are interested in.
248 ///
249 /// \return null if the transformation cannot be performed. If the
250 /// transformation can be performed the new instruction that replaces the
251 /// (zext icmp) pair will be returned.
252 Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext);
253
254 Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext);
255
256 bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
257 const Instruction &CxtI) const {
258 return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
260 }
261
262 bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
263 const Instruction &CxtI) const {
264 return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
266 }
267
268 bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
269 const Instruction &CxtI, bool IsSigned) const {
270 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
271 : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
272 }
273
274 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
275 const Instruction &CxtI) const {
276 return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
278 }
279
280 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
281 const Instruction &CxtI) const {
282 return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
284 }
285
286 bool willNotOverflowSub(const Value *LHS, const Value *RHS,
287 const Instruction &CxtI, bool IsSigned) const {
288 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
289 : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
290 }
291
292 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
293 const Instruction &CxtI) const {
294 return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
296 }
297
298 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
299 const Instruction &CxtI) const {
300 return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
302 }
303
304 bool willNotOverflowMul(const Value *LHS, const Value *RHS,
305 const Instruction &CxtI, bool IsSigned) const {
306 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
307 : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
308 }
309
310 bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
311 const Value *RHS, const Instruction &CxtI,
312 bool IsSigned) const {
313 switch (Opcode) {
314 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
315 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
316 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
317 default: llvm_unreachable("Unexpected opcode for overflow query");
318 }
319 }
320
321 Value *EmitGEPOffset(User *GEP);
322 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
323 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
324 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
325 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
326 Instruction *narrowBinOp(TruncInst &Trunc);
327 Instruction *narrowMaskedBinOp(BinaryOperator &And);
328 Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
329 Instruction *narrowFunnelShift(TruncInst &Trunc);
330 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
331 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
332 Instruction *foldNot(BinaryOperator &I);
333
334 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);
335
336 /// Determine if a pair of casts can be replaced by a single cast.
337 ///
338 /// \param CI1 The first of a pair of casts.
339 /// \param CI2 The second of a pair of casts.
340 ///
341 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
342 /// Instruction::CastOps value for a cast that can replace the pair, casting
343 /// CI1->getSrcTy() to CI2->getDstTy().
344 ///
345 /// \see CastInst::isEliminableCastPair
346 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
347 const CastInst *CI2);
348 Value *simplifyIntToPtrRoundTripCast(Value *Val);
349
350 Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,
351 bool IsAnd, bool IsLogical = false);
352 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
353
354 Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
355
356 Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
357 bool IsAnd);
358
359 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
360 /// NOTE: Unlike most of instcombine, this returns a Value which should
361 /// already be inserted into the function.
362 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
363 bool IsLogicalSelect = false);
364
365 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,
366 Value *RHS);
367
369 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);
370
371 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
372 Instruction *CxtI, bool IsAnd,
373 bool IsLogical = false);
374 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
375 bool InvertFalseVal = false);
376 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
377
378 Instruction *foldLShrOverflowBit(BinaryOperator &I);
379 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
380 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
381 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II);
382 Instruction *foldFPSignBitOps(BinaryOperator &I);
383 Instruction *foldFDivConstantDivisor(BinaryOperator &I);
384
385 // Optimize one of these forms:
386 // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
387 // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
388 // into simplier select instruction using isImpliedCondition.
389 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
390 bool IsAnd);
391
392public:
393 /// Create and insert the idiom we use to indicate a block is unreachable
394 /// without having to rewrite the CFG from within InstCombine.
396 auto &Ctx = InsertAt->getContext();
399 InsertAt);
400 }
401
402
403 /// Combiner aware instruction erasure.
404 ///
405 /// When dealing with an instruction that has side effects or produces a void
406 /// value, we can't rely on DCE to delete the instruction. Instead, visit
407 /// methods should return the value returned by this function.
409 LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
410 assert(I.use_empty() && "Cannot erase instruction that is used!");
412
413 // Make sure that we reprocess all operands now that we reduced their
414 // use counts.
415 for (Use &Operand : I.operands())
416 if (auto *Inst = dyn_cast<Instruction>(Operand))
417 Worklist.add(Inst);
418
419 Worklist.remove(&I);
420 I.eraseFromParent();
421 MadeIRChange = true;
422 return nullptr; // Don't do anything with FI
423 }
424
425 OverflowResult computeOverflow(
426 Instruction::BinaryOps BinaryOp, bool IsSigned,
427 Value *LHS, Value *RHS, Instruction *CxtI) const;
428
429 /// Performs a few simplifications for operators which are associative
430 /// or commutative.
431 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
432
433 /// Tries to simplify binary operations which some other binary
434 /// operation distributes over.
435 ///
436 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
437 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
438 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
439 /// value, or null if it didn't simplify.
440 Value *foldUsingDistributiveLaws(BinaryOperator &I);
441
442 /// Tries to simplify add operations using the definition of remainder.
443 ///
444 /// The definition of remainder is X % C = X - (X / C ) * C. The add
445 /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
446 /// X % (C0 * C1)
447 Value *SimplifyAddWithRemainder(BinaryOperator &I);
448
449 // Binary Op helper for select operations where the expression can be
450 // efficiently reorganized.
451 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
452 Value *RHS);
453
454 /// This tries to simplify binary operations by factorizing out common terms
455 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
456 Value *tryFactorizationFolds(BinaryOperator &I);
457
458 /// Match a select chain which produces one of three values based on whether
459 /// the LHS is less than, equal to, or greater than RHS respectively.
460 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
461 /// Equal and Greater values are saved in the matching process and returned to
462 /// the caller.
463 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
464 ConstantInt *&Less, ConstantInt *&Equal,
465 ConstantInt *&Greater);
466
467 /// Attempts to replace V with a simpler value based on the demanded
468 /// bits.
469 Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
470 unsigned Depth, Instruction *CxtI);
471 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
472 const APInt &DemandedMask, KnownBits &Known,
473 unsigned Depth = 0) override;
474
475 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
476 /// bits. It also tries to handle simplifications that can be done based on
477 /// DemandedMask, but without modifying the Instruction.
478 Value *SimplifyMultipleUseDemandedBits(Instruction *I,
479 const APInt &DemandedMask,
480 KnownBits &Known,
481 unsigned Depth, Instruction *CxtI);
482
483 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
484 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
485 Value *simplifyShrShlDemandedBits(
486 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
487 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
488
489 /// Tries to simplify operands to an integer instruction based on its
490 /// demanded bits.
491 bool SimplifyDemandedInstructionBits(Instruction &Inst);
492
493 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
494 APInt &UndefElts, unsigned Depth = 0,
495 bool AllowMultipleUsers = false) override;
496
497 /// Canonicalize the position of binops relative to shufflevector.
498 Instruction *foldVectorBinop(BinaryOperator &Inst);
500 Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
501
502 /// Given a binary operator, cast instruction, or select which has a PHI node
503 /// as operand #0, see if we can fold the instruction into the PHI (which is
504 /// only possible if all operands to the PHI are constants).
505 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
506
507 /// For a binary operator with 2 phi operands, try to hoist the binary
508 /// operation before the phi. This can result in fewer instructions in
509 /// patterns where at least one set of phi operands simplifies.
510 /// Example:
511 /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
512 /// -->
513 /// BB1: BO = binop X, Y
514 /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
515 Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
516
517 /// Given an instruction with a select as one operand and a constant as the
518 /// other operand, try to fold the binary operator into the select arguments.
519 /// This also works for Cast instructions, which obviously do not have a
520 /// second operand.
521 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
522 bool FoldWithMultiUse = false);
523
524 /// This is a convenience wrapper function for the above two functions.
525 Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
526
527 Instruction *foldAddWithConstant(BinaryOperator &Add);
528
529 /// Try to rotate an operation below a PHI node, using PHI nodes for
530 /// its operands.
531 Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
532 Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
533 Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
534 Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
535 Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
536 Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
537 Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
538 Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
539
540 /// If an integer typed PHI has only one use which is an IntToPtr operation,
541 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
542 /// insert a new pointer typed PHI and replace the original one.
543 bool foldIntegerTypedPHI(PHINode &PN);
544
545 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
546 /// folded operation.
547 void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
548
549 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
551 Instruction *foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI,
552 Value *RHS, const ICmpInst &I);
553 Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca);
554 Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI,
556 GlobalVariable *GV, CmpInst &ICI,
557 ConstantInt *AndCst = nullptr);
558 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
559 Constant *RHSC);
560 Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
562 Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
563 Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
564
565 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
567 Instruction *foldICmpWithConstant(ICmpInst &Cmp);
568 Instruction *foldICmpUsingBoolRange(ICmpInst &I);
569 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
570 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
571 Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
572 const APInt &C);
573 Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
574 Instruction *foldICmpEquality(ICmpInst &Cmp);
575 Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
576 Instruction *foldSignBitTest(ICmpInst &I);
577 Instruction *foldICmpWithZero(ICmpInst &Cmp);
578
579 Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
580
581 Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
582 const APInt &C);
583 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
584 ConstantInt *C);
585 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
586 const APInt &C);
587 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
588 const APInt &C);
589 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
590 const APInt &C);
591 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
592 const APInt &C);
593 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
594 const APInt &C);
595 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
596 const APInt &C);
597 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
598 const APInt &C);
599 Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
600 const APInt &C);
601 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
602 const APInt &C);
603 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
604 const APInt &C);
605 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
606 const APInt &C);
607 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
608 const APInt &C);
609 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
610 const APInt &C1);
611 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
612 const APInt &C1, const APInt &C2);
613 Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor,
614 const APInt &C);
615 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
616 const APInt &C2);
617 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
618 const APInt &C2);
619
620 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
621 BinaryOperator *BO,
622 const APInt &C);
623 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
624 const APInt &C);
625 Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
626 const APInt &C);
627 Instruction *foldICmpBitCast(ICmpInst &Cmp);
628 Instruction *foldICmpWithTrunc(ICmpInst &Cmp);
629
630 // Helpers of visitSelectInst().
633 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
634 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
636 Value *A, Value *B, Instruction &Outer,
640
641 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
642 bool isSigned, bool Inside);
643 Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
644 bool mergeStoreIntoSuccessor(StoreInst &SI);
645
646 /// Given an initial instruction, check to see if it is the root of a
647 /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
648 /// intrinsic.
649 Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
650 bool MatchBitReversals);
651
652 Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
653 Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
654
655 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
656
657 /// Returns a value X such that Val = X * Scale, or null if none.
658 ///
659 /// If the multiplication is known not to overflow then NoSignedWrap is set.
660 Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
661};
662
663class Negator final {
664 /// Top-to-bottom, def-to-use negated instruction tree we produced.
666
668 BuilderTy Builder;
669
670 const DataLayout &DL;
671 AssumptionCache &AC;
672 const DominatorTree &DT;
673
674 const bool IsTrulyNegation;
675
676 SmallDenseMap<Value *, Value *> NegationsCache;
677
679 const DominatorTree &DT, bool IsTrulyNegation);
680
681#if LLVM_ENABLE_STATS
682 unsigned NumValuesVisitedInThisNegator = 0;
683 ~Negator();
684#endif
685
686 using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
687 Value * /*NegatedRoot*/>;
688
689 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
690
691 [[nodiscard]] Value *visitImpl(Value *V, unsigned Depth);
692
693 [[nodiscard]] Value *negate(Value *V, unsigned Depth);
694
695 /// Recurse depth-first and attempt to sink the negation.
696 /// FIXME: use worklist?
697 [[nodiscard]] std::optional<Result> run(Value *Root);
698
699 Negator(const Negator &) = delete;
700 Negator(Negator &&) = delete;
701 Negator &operator=(const Negator &) = delete;
702 Negator &operator=(Negator &&) = delete;
703
704public:
705 /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
706 /// otherwise returns negated value.
707 [[nodiscard]] static Value *Negate(bool LHSIsZero, Value *Root,
708 InstCombinerImpl &IC);
709};
710
711} // end namespace llvm
712
713#undef DEBUG_TYPE
714
715#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
assume Assume Builder
SmallVector< MachineOperand, 4 > Cond
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:126
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
Hexagon Common GEP
IRTranslator LLVM IR MI
static constexpr unsigned NegatorMaxNodesSSO
static constexpr unsigned NegatorDefaultMaxDepth
This file provides the interface for the instcombine pass implementation.
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
Value * RHS
Value * LHS
static const uint32_t IV[8]
Definition: blake3_impl.h:77
Class for arbitrary precision integers.
Definition: APInt.h:75
This class represents a conversion between pointers from one address space to another.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
This class represents any memset intrinsic.
A cache of @llvm.assume calls within a function.
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:718
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
This class represents a no-op cast from one type to another.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1186
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:428
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:708
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:718
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
This is an important base class in LLVM.
Definition: Constant.h:41
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
This instruction extracts a single (scalar) element from a VectorType value.
This instruction extracts a struct member or array element value from an aggregate value.
This instruction compares its operands according to the predicate given to the constructor.
This class represents a cast from floating point to signed integer.
This class represents a cast from floating point to unsigned integer.
This class represents a truncation of floating point types.
An instruction for ordering other memory operations.
Definition: Instructions.h:436
This class represents a freeze function that returns random concrete value if an operand is either a ...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:940
This instruction compares its operands according to the predicate given to the constructor.
This instruction inserts a single (scalar) element into a VectorType value.
This instruction inserts a struct field of array element value into an aggregate value.
virtual ~InstCombinerImpl()=default
Instruction * foldVectorSelect(SelectInst &Sel)
Instruction * foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI)
Instruction * foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1, Value *A, Value *B, Instruction &Outer, SelectPatternFlavor SPF2, Value *C)
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Instruction * foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI)
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
InstCombinerImpl(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)
void CreateNonTerminatorUnreachable(Instruction *InsertAt)
Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...
Instruction * visitSelectInst(SelectInst &SI)
Instruction * foldSelectOfBools(SelectInst &SI)
Instruction * foldSelectExtConst(SelectInst &Sel)
The core instruction combiner logic.
Definition: InstCombiner.h:45
Base class for instruction visitors.
Definition: InstVisitor.h:78
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
This class represents a cast from an integer to a pointer.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:47
Invoke instruction.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
The landingpad instruction holds all of the information necessary to generate correct exception handl...
An instruction for reading from memory.
Definition: Instructions.h:177
static Value * Negate(bool LHSIsZero, Value *Root, InstCombinerImpl &IC)
Attempt to negate Root.
This is a utility class that provides an abstraction for the common functionality between Instruction...
Definition: Operator.h:31
The optimization diagnostic interface.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1758
Analysis providing profile information.
This class represents a cast from a pointer to an integer.
Return a value (possibly void), from a function.
This class represents a sign extension of integer types.
This class represents the LLVM 'select' instruction.
This instruction constructs a fixed permutation of two input vectors.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Multiway switch.
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.
This class represents a truncation of integer types.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
This function has undefined behavior.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
This represents the llvm.va_end intrinsic.
LLVM Value Representation.
Definition: Value.h:74
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:994
This class represents zero extension of integer types.
#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
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
OverflowResult
@ NeverOverflows
Never overflows.
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)
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1367
SelectPatternFlavor
Specific patterns of select instructions we can match.
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)
@ Or
Bitwise or logical OR of integers.
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
@ Add
Sum of integers.
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:184
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)