LLVM 18.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"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/InstVisitor.h"
26#include "llvm/IR/Value.h"
27#include "llvm/Support/Debug.h"
31#include <cassert>
32
33#define DEBUG_TYPE "instcombine"
35
36using namespace llvm::PatternMatch;
37
38// As a default, let's assume that we want to be aggressive,
39// and attempt to traverse with no limits in attempt to sink negation.
40static constexpr unsigned NegatorDefaultMaxDepth = ~0U;
41
42// Let's guesstimate that most often we will end up visiting/producing
43// fairly small number of new instructions.
44static constexpr unsigned NegatorMaxNodesSSO = 16;
45
46namespace llvm {
47
48class AAResults;
49class APInt;
50class AssumptionCache;
52class DataLayout;
53class DominatorTree;
54class GEPOperator;
55class GlobalVariable;
56class LoopInfo;
60class User;
61
63 : public InstCombiner,
64 public InstVisitor<InstCombinerImpl, Instruction *> {
65public:
67 bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
71 const DataLayout &DL, LoopInfo *LI)
72 : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
73 BFI, PSI, DL, LI) {}
74
75 virtual ~InstCombinerImpl() = default;
76
77 /// Perform early cleanup and prepare the InstCombine worklist.
78 bool prepareWorklist(Function &F,
80
81 /// Run the combiner over the entire worklist until it is empty.
82 ///
83 /// \returns true if the IR is changed.
84 bool run();
85
86 // Visitation implementation - Implement instruction combining for different
87 // instruction types. The semantics are as follows:
88 // Return Value:
89 // null - No change was made
90 // I - Change was made, I is still valid, I may be dead though
91 // otherwise - Change was made, replace I with returned instruction
92 //
93 Instruction *visitFNeg(UnaryOperator &I);
94 Instruction *visitAdd(BinaryOperator &I);
95 Instruction *visitFAdd(BinaryOperator &I);
96 Value *OptimizePointerDifference(
97 Value *LHS, Value *RHS, Type *Ty, bool isNUW);
98 Instruction *visitSub(BinaryOperator &I);
99 Instruction *visitFSub(BinaryOperator &I);
100 Instruction *visitMul(BinaryOperator &I);
101 Instruction *visitFMul(BinaryOperator &I);
102 Instruction *visitURem(BinaryOperator &I);
103 Instruction *visitSRem(BinaryOperator &I);
104 Instruction *visitFRem(BinaryOperator &I);
105 bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
106 Instruction *commonIRemTransforms(BinaryOperator &I);
107 Instruction *commonIDivTransforms(BinaryOperator &I);
108 Instruction *visitUDiv(BinaryOperator &I);
109 Instruction *visitSDiv(BinaryOperator &I);
110 Instruction *visitFDiv(BinaryOperator &I);
111 Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
112 Instruction *visitAnd(BinaryOperator &I);
113 Instruction *visitOr(BinaryOperator &I);
114 bool sinkNotIntoLogicalOp(Instruction &I);
115 bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I);
116 Instruction *visitXor(BinaryOperator &I);
117 Instruction *visitShl(BinaryOperator &I);
118 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
119 BinaryOperator *Sh0, const SimplifyQuery &SQ,
120 bool AnalyzeForSignBitExtraction = false);
121 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
123 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
124 BinaryOperator &OldAShr);
125 Instruction *visitAShr(BinaryOperator &I);
126 Instruction *visitLShr(BinaryOperator &I);
127 Instruction *commonShiftTransforms(BinaryOperator &I);
128 Instruction *visitFCmpInst(FCmpInst &I);
129 CmpInst *canonicalizeICmpPredicate(CmpInst &I);
130 Instruction *visitICmpInst(ICmpInst &I);
131 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
133 Instruction *commonCastTransforms(CastInst &CI);
134 Instruction *commonPointerCastTransforms(CastInst &CI);
135 Instruction *visitTrunc(TruncInst &CI);
136 Instruction *visitZExt(ZExtInst &Zext);
137 Instruction *visitSExt(SExtInst &Sext);
138 Instruction *visitFPTrunc(FPTruncInst &CI);
139 Instruction *visitFPExt(CastInst &CI);
140 Instruction *visitFPToUI(FPToUIInst &FI);
141 Instruction *visitFPToSI(FPToSIInst &FI);
142 Instruction *visitUIToFP(CastInst &CI);
143 Instruction *visitSIToFP(CastInst &CI);
144 Instruction *visitPtrToInt(PtrToIntInst &CI);
145 Instruction *visitIntToPtr(IntToPtrInst &CI);
146 Instruction *visitBitCast(BitCastInst &CI);
147 Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
148 Instruction *foldItoFPtoI(CastInst &FI);
150 Instruction *visitCallInst(CallInst &CI);
151 Instruction *visitInvokeInst(InvokeInst &II);
152 Instruction *visitCallBrInst(CallBrInst &CBI);
153
154 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
155 Instruction *visitPHINode(PHINode &PN);
156 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
157 Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
158 Instruction *visitAllocaInst(AllocaInst &AI);
159 Instruction *visitAllocSite(Instruction &FI);
160 Instruction *visitFree(CallInst &FI, Value *FreedOp);
161 Instruction *visitLoadInst(LoadInst &LI);
162 Instruction *visitStoreInst(StoreInst &SI);
163 Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
164 Instruction *visitUnconditionalBranchInst(BranchInst &BI);
165 Instruction *visitBranchInst(BranchInst &BI);
166 Instruction *visitFenceInst(FenceInst &FI);
167 Instruction *visitSwitchInst(SwitchInst &SI);
168 Instruction *visitReturnInst(ReturnInst &RI);
169 Instruction *visitUnreachableInst(UnreachableInst &I);
171 foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
172 Instruction *visitInsertValueInst(InsertValueInst &IV);
173 Instruction *visitInsertElementInst(InsertElementInst &IE);
174 Instruction *visitExtractElementInst(ExtractElementInst &EI);
175 Instruction *simplifyBinOpSplats(ShuffleVectorInst &SVI);
176 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
177 Instruction *visitExtractValueInst(ExtractValueInst &EV);
178 Instruction *visitLandingPadInst(LandingPadInst &LI);
179 Instruction *visitVAEndInst(VAEndInst &I);
180 Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
181 bool freezeOtherUses(FreezeInst &FI);
182 Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
183 Instruction *visitFreeze(FreezeInst &I);
184
185 /// Specify what to return for unhandled instructions.
187
188 /// True when DB dominates all uses of DI except UI.
189 /// UI must be in the same block as DI.
190 /// The routine checks that the DI parent and DB are different.
191 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
192 const BasicBlock *DB) const;
193
194 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
195 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
196 const unsigned SIOpd);
197
198 LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
199 const Twine &Suffix = "");
200
202 FPClassTest Interested = fcAllFlags,
203 const Instruction *CtxI = nullptr,
204 unsigned Depth = 0) const {
205 return llvm::computeKnownFPClass(Val, FMF, DL, Interested, Depth, &TLI, &AC,
206 CtxI, &DT);
207 }
208
210 FPClassTest Interested = fcAllFlags,
211 const Instruction *CtxI = nullptr,
212 unsigned Depth = 0) const {
213 return llvm::computeKnownFPClass(Val, DL, Interested, Depth, &TLI, &AC,
214 CtxI, &DT);
215 }
216
217 /// Check if fmul \p MulVal, +0.0 will yield +0.0 (or signed zero is
218 /// ignorable).
220 const Instruction *CtxI) const;
221
222 Constant *getLosslessTrunc(Constant *C, Type *TruncTy, unsigned ExtOp) {
223 Constant *TruncC = ConstantExpr::getTrunc(C, TruncTy);
224 Constant *ExtTruncC =
225 ConstantFoldCastOperand(ExtOp, TruncC, C->getType(), DL);
226 if (ExtTruncC && ExtTruncC == C)
227 return TruncC;
228 return nullptr;
229 }
230
232 return getLosslessTrunc(C, TruncTy, Instruction::ZExt);
233 }
234
236 return getLosslessTrunc(C, TruncTy, Instruction::SExt);
237 }
238
239private:
240 bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
241 bool isDesirableIntType(unsigned BitWidth) const;
242 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
243 bool shouldChangeType(Type *From, Type *To) const;
244 Value *dyn_castNegVal(Value *V) const;
245
246 /// Classify whether a cast is worth optimizing.
247 ///
248 /// This is a helper to decide whether the simplification of
249 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
250 ///
251 /// \param CI The cast we are interested in.
252 ///
253 /// \return true if this cast actually results in any code being generated and
254 /// if it cannot already be eliminated by some other transformation.
255 bool shouldOptimizeCast(CastInst *CI);
256
257 /// Try to optimize a sequence of instructions checking if an operation
258 /// on LHS and RHS overflows.
259 ///
260 /// If this overflow check is done via one of the overflow check intrinsics,
261 /// then CtxI has to be the call instruction calling that intrinsic. If this
262 /// overflow check is done by arithmetic followed by a compare, then CtxI has
263 /// to be the arithmetic instruction.
264 ///
265 /// If a simplification is possible, stores the simplified result of the
266 /// operation in OperationResult and result of the overflow check in
267 /// OverflowResult, and return true. If no simplification is possible,
268 /// returns false.
269 bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
270 Value *LHS, Value *RHS,
271 Instruction &CtxI, Value *&OperationResult,
273
274 Instruction *visitCallBase(CallBase &Call);
275 Instruction *tryOptimizeCall(CallInst *CI);
276 bool transformConstExprCastCall(CallBase &Call);
277 Instruction *transformCallThroughTrampoline(CallBase &Call,
278 IntrinsicInst &Tramp);
279
280 Value *simplifyMaskedLoad(IntrinsicInst &II);
281 Instruction *simplifyMaskedStore(IntrinsicInst &II);
282 Instruction *simplifyMaskedGather(IntrinsicInst &II);
283 Instruction *simplifyMaskedScatter(IntrinsicInst &II);
284
285 /// Transform (zext icmp) to bitwise / integer operations in order to
286 /// eliminate it.
287 ///
288 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
289 /// \parem CI The zext of the (zext icmp) pair we are interested in.
290 ///
291 /// \return null if the transformation cannot be performed. If the
292 /// transformation can be performed the new instruction that replaces the
293 /// (zext icmp) pair will be returned.
294 Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext);
295
296 Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext);
297
298 bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
299 const Instruction &CxtI) const {
300 return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
301 OverflowResult::NeverOverflows;
302 }
303
304 bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
305 const Instruction &CxtI) const {
306 return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
307 OverflowResult::NeverOverflows;
308 }
309
310 bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
311 const Instruction &CxtI, bool IsSigned) const {
312 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
313 : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
314 }
315
316 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
317 const Instruction &CxtI) const {
318 return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
319 OverflowResult::NeverOverflows;
320 }
321
322 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
323 const Instruction &CxtI) const {
324 return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
325 OverflowResult::NeverOverflows;
326 }
327
328 bool willNotOverflowSub(const Value *LHS, const Value *RHS,
329 const Instruction &CxtI, bool IsSigned) const {
330 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
331 : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
332 }
333
334 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
335 const Instruction &CxtI) const {
336 return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
337 OverflowResult::NeverOverflows;
338 }
339
340 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
341 const Instruction &CxtI) const {
342 return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
343 OverflowResult::NeverOverflows;
344 }
345
346 bool willNotOverflowMul(const Value *LHS, const Value *RHS,
347 const Instruction &CxtI, bool IsSigned) const {
348 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
349 : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
350 }
351
353 const Value *RHS, const Instruction &CxtI,
354 bool IsSigned) const {
355 switch (Opcode) {
356 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
357 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
358 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
359 default: llvm_unreachable("Unexpected opcode for overflow query");
360 }
361 }
362
363 Value *EmitGEPOffset(User *GEP);
364 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
365 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
366 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
367 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
368 Instruction *narrowBinOp(TruncInst &Trunc);
369 Instruction *narrowMaskedBinOp(BinaryOperator &And);
370 Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
371 Instruction *narrowFunnelShift(TruncInst &Trunc);
372 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
373 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
374 Instruction *foldNot(BinaryOperator &I);
375 Instruction *foldBinOpOfDisplacedShifts(BinaryOperator &I);
376
377 /// Determine if a pair of casts can be replaced by a single cast.
378 ///
379 /// \param CI1 The first of a pair of casts.
380 /// \param CI2 The second of a pair of casts.
381 ///
382 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
383 /// Instruction::CastOps value for a cast that can replace the pair, casting
384 /// CI1->getSrcTy() to CI2->getDstTy().
385 ///
386 /// \see CastInst::isEliminableCastPair
387 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
388 const CastInst *CI2);
389 Value *simplifyIntToPtrRoundTripCast(Value *Val);
390
391 Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,
392 bool IsAnd, bool IsLogical = false);
393 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
394
395 Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
396
397 Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
398 bool IsAnd);
399
400 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
401 /// NOTE: Unlike most of instcombine, this returns a Value which should
402 /// already be inserted into the function.
403 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
404 bool IsLogicalSelect = false);
405
406 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,
407 Value *RHS);
408
410 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);
411
412 Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
413 Instruction *CxtI, bool IsAnd,
414 bool IsLogical = false);
415 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
416 bool InvertFalseVal = false);
417 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
418
419 Instruction *foldLShrOverflowBit(BinaryOperator &I);
420 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
421 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
422 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II);
423 Instruction *foldFPSignBitOps(BinaryOperator &I);
424 Instruction *foldFDivConstantDivisor(BinaryOperator &I);
425
426 // Optimize one of these forms:
427 // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
428 // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
429 // into simplier select instruction using isImpliedCondition.
430 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
431 bool IsAnd);
432
433 Instruction *hoistFNegAboveFMulFDiv(Value *FNegOp, Instruction &FMFSource);
434
435public:
436 /// Create and insert the idiom we use to indicate a block is unreachable
437 /// without having to rewrite the CFG from within InstCombine.
439 auto &Ctx = InsertAt->getContext();
440 auto *SI = new StoreInst(ConstantInt::getTrue(Ctx),
441 PoisonValue::get(PointerType::getUnqual(Ctx)),
442 /*isVolatile*/ false, Align(1));
443 InsertNewInstBefore(SI, InsertAt->getIterator());
444 }
445
446 /// Combiner aware instruction erasure.
447 ///
448 /// When dealing with an instruction that has side effects or produces a void
449 /// value, we can't rely on DCE to delete the instruction. Instead, visit
450 /// methods should return the value returned by this function.
452 LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
453 assert(I.use_empty() && "Cannot erase instruction that is used!");
455
456 // Make sure that we reprocess all operands now that we reduced their
457 // use counts.
458 SmallVector<Value *> Ops(I.operands());
459 Worklist.remove(&I);
460 I.eraseFromParent();
461 for (Value *Op : Ops)
462 Worklist.handleUseCountDecrement(Op);
463 MadeIRChange = true;
464 return nullptr; // Don't do anything with FI
465 }
466
467 OverflowResult computeOverflow(
468 Instruction::BinaryOps BinaryOp, bool IsSigned,
469 Value *LHS, Value *RHS, Instruction *CxtI) const;
470
471 /// Performs a few simplifications for operators which are associative
472 /// or commutative.
473 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
474
475 /// Tries to simplify binary operations which some other binary
476 /// operation distributes over.
477 ///
478 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
479 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
480 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
481 /// value, or null if it didn't simplify.
482 Value *foldUsingDistributiveLaws(BinaryOperator &I);
483
484 /// Tries to simplify add operations using the definition of remainder.
485 ///
486 /// The definition of remainder is X % C = X - (X / C ) * C. The add
487 /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
488 /// X % (C0 * C1)
489 Value *SimplifyAddWithRemainder(BinaryOperator &I);
490
491 // Binary Op helper for select operations where the expression can be
492 // efficiently reorganized.
493 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
494 Value *RHS);
495
496 // (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C))
497 // -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
498 // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))
499 // -> (BinOp (logic_shift (BinOp X, Y)), Mask)
500 Instruction *foldBinOpShiftWithShift(BinaryOperator &I);
501
502 /// Tries to simplify binops of select and cast of the select condition.
503 ///
504 /// (Binop (cast C), (select C, T, F))
505 /// -> (select C, C0, C1)
506 Instruction *foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I);
507
508 /// This tries to simplify binary operations by factorizing out common terms
509 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
510 Value *tryFactorizationFolds(BinaryOperator &I);
511
512 /// Match a select chain which produces one of three values based on whether
513 /// the LHS is less than, equal to, or greater than RHS respectively.
514 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
515 /// Equal and Greater values are saved in the matching process and returned to
516 /// the caller.
517 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
518 ConstantInt *&Less, ConstantInt *&Equal,
519 ConstantInt *&Greater);
520
521 /// Attempts to replace V with a simpler value based on the demanded
522 /// bits.
523 Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
524 unsigned Depth, Instruction *CxtI);
525 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
526 const APInt &DemandedMask, KnownBits &Known,
527 unsigned Depth = 0) override;
528
529 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
530 /// bits. It also tries to handle simplifications that can be done based on
531 /// DemandedMask, but without modifying the Instruction.
532 Value *SimplifyMultipleUseDemandedBits(Instruction *I,
533 const APInt &DemandedMask,
534 KnownBits &Known,
535 unsigned Depth, Instruction *CxtI);
536
537 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
538 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
539 Value *simplifyShrShlDemandedBits(
540 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
541 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
542
543 /// Tries to simplify operands to an integer instruction based on its
544 /// demanded bits.
545 bool SimplifyDemandedInstructionBits(Instruction &Inst);
546
547 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
548 APInt &UndefElts, unsigned Depth = 0,
549 bool AllowMultipleUsers = false) override;
550
551 /// Canonicalize the position of binops relative to shufflevector.
552 Instruction *foldVectorBinop(BinaryOperator &Inst);
554 Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
555
556 /// Given a binary operator, cast instruction, or select which has a PHI node
557 /// as operand #0, see if we can fold the instruction into the PHI (which is
558 /// only possible if all operands to the PHI are constants).
559 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
560
561 /// For a binary operator with 2 phi operands, try to hoist the binary
562 /// operation before the phi. This can result in fewer instructions in
563 /// patterns where at least one set of phi operands simplifies.
564 /// Example:
565 /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
566 /// -->
567 /// BB1: BO = binop X, Y
568 /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
569 Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
570
571 /// Given an instruction with a select as one operand and a constant as the
572 /// other operand, try to fold the binary operator into the select arguments.
573 /// This also works for Cast instructions, which obviously do not have a
574 /// second operand.
575 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
576 bool FoldWithMultiUse = false);
577
578 /// This is a convenience wrapper function for the above two functions.
579 Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
580
581 Instruction *foldAddWithConstant(BinaryOperator &Add);
582
583 Instruction *foldSquareSumInt(BinaryOperator &I);
584 Instruction *foldSquareSumFP(BinaryOperator &I);
585
586 /// Try to rotate an operation below a PHI node, using PHI nodes for
587 /// its operands.
588 Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
589 Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
590 Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
591 Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
592 Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
593 Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
594 Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
595 Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
596
597 /// If an integer typed PHI has only one use which is an IntToPtr operation,
598 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
599 /// insert a new pointer typed PHI and replace the original one.
600 bool foldIntegerTypedPHI(PHINode &PN);
601
602 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
603 /// folded operation.
604 void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
605
606 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
608 Instruction *foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI,
609 Value *RHS, const ICmpInst &I);
610 bool foldAllocaCmp(AllocaInst *Alloca);
611 Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI,
613 GlobalVariable *GV, CmpInst &ICI,
614 ConstantInt *AndCst = nullptr);
615 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
616 Constant *RHSC);
617 Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
619 Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
620 Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
621
622 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
624 Instruction *foldICmpWithConstant(ICmpInst &Cmp);
625 Instruction *foldICmpUsingBoolRange(ICmpInst &I);
626 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
627 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
628 Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
629 const APInt &C);
630 Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
631 Instruction *foldICmpWithMinMaxImpl(Instruction &I, MinMaxIntrinsic *MinMax,
632 Value *Z, ICmpInst::Predicate Pred);
633 Instruction *foldICmpWithMinMax(ICmpInst &Cmp);
634 Instruction *foldICmpEquality(ICmpInst &Cmp);
635 Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
636 Instruction *foldSignBitTest(ICmpInst &I);
637 Instruction *foldICmpWithZero(ICmpInst &Cmp);
638
639 Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
640
641 Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
642 const APInt &C);
643 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
644 ConstantInt *C);
645 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
646 const APInt &C);
647 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
648 const APInt &C);
649 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
650 const APInt &C);
651 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
652 const APInt &C);
653 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
654 const APInt &C);
655 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
656 const APInt &C);
657 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
658 const APInt &C);
659 Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
660 const APInt &C);
661 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
662 const APInt &C);
663 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
664 const APInt &C);
665 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
666 const APInt &C);
667 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
668 const APInt &C);
669 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
670 const APInt &C1);
671 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
672 const APInt &C1, const APInt &C2);
673 Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor,
674 const APInt &C);
675 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
676 const APInt &C2);
677 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
678 const APInt &C2);
679
680 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
681 BinaryOperator *BO,
682 const APInt &C);
683 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
684 const APInt &C);
685 Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
686 const APInt &C);
687 Instruction *foldICmpBitCast(ICmpInst &Cmp);
688 Instruction *foldICmpWithTrunc(ICmpInst &Cmp);
689
690 // Helpers of visitSelectInst().
693 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
694 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
696 Value *A, Value *B, Instruction &Outer,
701 unsigned Depth = 0);
702
703 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
704 bool isSigned, bool Inside);
705 bool mergeStoreIntoSuccessor(StoreInst &SI);
706
707 /// Given an initial instruction, check to see if it is the root of a
708 /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
709 /// intrinsic.
710 Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
711 bool MatchBitReversals);
712
713 Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
714 Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
715
716 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
717
718 bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock);
719
720 bool removeInstructionsBeforeUnreachable(Instruction &I);
721 void addDeadEdge(BasicBlock *From, BasicBlock *To,
723 void handleUnreachableFrom(Instruction *I,
725 void handlePotentiallyDeadBlocks(SmallVectorImpl<BasicBlock *> &Worklist);
726 void handlePotentiallyDeadSuccessors(BasicBlock *BB, BasicBlock *LiveSucc);
727 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);
728};
729
730class Negator final {
731 /// Top-to-bottom, def-to-use negated instruction tree we produced.
733
735 BuilderTy Builder;
736
737 const DataLayout &DL;
738 AssumptionCache &AC;
739 const DominatorTree &DT;
740
741 const bool IsTrulyNegation;
742
743 SmallDenseMap<Value *, Value *> NegationsCache;
744
746 const DominatorTree &DT, bool IsTrulyNegation);
747
748#if LLVM_ENABLE_STATS
749 unsigned NumValuesVisitedInThisNegator = 0;
750 ~Negator();
751#endif
752
753 using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
754 Value * /*NegatedRoot*/>;
755
756 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
757
758 [[nodiscard]] Value *visitImpl(Value *V, bool IsNSW, unsigned Depth);
759
760 [[nodiscard]] Value *negate(Value *V, bool IsNSW, unsigned Depth);
761
762 /// Recurse depth-first and attempt to sink the negation.
763 /// FIXME: use worklist?
764 [[nodiscard]] std::optional<Result> run(Value *Root, bool IsNSW);
765
766 Negator(const Negator &) = delete;
767 Negator(Negator &&) = delete;
768 Negator &operator=(const Negator &) = delete;
769 Negator &operator=(Negator &&) = delete;
770
771public:
772 /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
773 /// otherwise returns negated value.
774 [[nodiscard]] static Value *Negate(bool LHSIsZero, bool IsNSW, Value *Root,
775 InstCombinerImpl &IC);
776};
777
778} // end namespace llvm
779
780#undef DEBUG_TYPE
781
782#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
assume Assume Builder
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< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
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
Definition: Compiler.h:131
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
#define LLVM_DEBUG(X)
Definition: Debug.h:101
uint64_t Align
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 F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
StandardInstrumentations SI(Mod->getContext(), Debug, VerifyEach)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
const SmallVectorImpl< MachineOperand > & Cond
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...
static OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const AddOperator *Add, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Value * RHS
Value * LHS
BinaryOperator * Mul
static const uint32_t IV[8]
Definition: blake3_impl.h:78
Class for arbitrary precision integers.
Definition: APInt.h:76
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:1190
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:701
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:711
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
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
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.
Convenience struct for specifying and reasoning about fast-math flags.
Definition: FMF.h:20
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.
bool fmulByZeroIsZero(Value *MulVal, FastMathFlags FMF, const Instruction *CtxI) const
Check if fmul MulVal, +0.0 will yield +0.0 (or signed zero is ignorable).
virtual ~InstCombinerImpl()=default
KnownFPClass computeKnownFPClass(Value *Val, FastMathFlags FMF, FPClassTest Interested=fcAllFlags, const Instruction *CtxI=nullptr, unsigned Depth=0) const
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)
Constant * getLosslessUnsignedTrunc(Constant *C, Type *TruncTy)
bool replaceInInstruction(Value *V, Value *Old, Value *New, unsigned Depth=0)
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Instruction * foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI)
Constant * getLosslessTrunc(Constant *C, Type *TruncTy, unsigned ExtOp)
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
KnownFPClass computeKnownFPClass(Value *Val, FPClassTest Interested=fcAllFlags, const Instruction *CtxI=nullptr, unsigned Depth=0) const
Constant * getLosslessSignedTrunc(Constant *C, Type *TruncTy)
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:46
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
This class represents min/max intrinsics.
static Value * Negate(bool LHSIsZero, bool IsNSW, 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.
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 class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
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
This function has undefined behavior.
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:1069
This class represents zero extension of integer types.
self_iterator getIterator()
Definition: ilist_node.h:82
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
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 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:1394
SelectPatternFlavor
Specific patterns of select instructions we can match.
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
KnownFPClass computeKnownFPClass(const Value *V, const APInt &DemandedElts, const DataLayout &DL, FPClassTest InterestedClasses=fcAllFlags, unsigned Depth=0, const TargetLibraryInfo *TLI=nullptr, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which floating-point classes are valid for V, and return them in KnownFPClass bit sets.