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/PostOrderIterator.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/Analysis/InstructionSimplify.h"
21#include "llvm/Analysis/TargetFolder.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/IRBuilder.h"
24#include "llvm/IR/InstVisitor.h"
25#include "llvm/IR/PatternMatch.h"
26#include "llvm/IR/Value.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/KnownBits.h"
29#include "llvm/Support/KnownFPClass.h"
30#include "llvm/Transforms/InstCombine/InstCombiner.h"
31#include "llvm/Transforms/Utils/Local.h"
32#include <cassert>
33
34#define DEBUG_TYPE "instcombine"
35#include "llvm/Transforms/Utils/InstructionWorklist.h"
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;
50class BlockFrequencyInfo;
51class DataLayout;
52class DominatorTree;
53class GEPOperator;
54class GlobalVariable;
55class OptimizationRemarkEmitter;
56class ProfileSummaryInfo;
57class TargetLibraryInfo;
58class User;
59
60class LLVM_LIBRARY_VISIBILITY InstCombinerImpl final
61 : public InstCombiner,
62 public InstVisitor<InstCombinerImpl, Instruction *> {
63public:
64 InstCombinerImpl(InstructionWorklist &Worklist, BuilderTy &Builder,
65 bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
66 TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
67 DominatorTree &DT, OptimizationRemarkEmitter &ORE,
68 BlockFrequencyInfo *BFI, BranchProbabilityInfo *BPI,
69 ProfileSummaryInfo *PSI, const DataLayout &DL,
70 ReversePostOrderTraversal<BasicBlock *> &RPOT)
71 : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
72 BFI, BPI, PSI, DL, RPOT) {}
73
74 virtual ~InstCombinerImpl() = default;
75
76 /// Perform early cleanup and prepare the InstCombine worklist.
77 bool prepareWorklist(Function &F);
78
79 /// Run the combiner over the entire worklist until it is empty.
80 ///
81 /// \returns true if the IR is changed.
82 bool run();
83
84 // Visitation implementation - Implement instruction combining for different
85 // instruction types. The semantics are as follows:
86 // Return Value:
87 // null - No change was made
88 // I - Change was made, I is still valid, I may be dead though
89 // otherwise - Change was made, replace I with returned instruction
90 //
91 Instruction *visitFNeg(UnaryOperator &I);
92 Instruction *visitAdd(BinaryOperator &I);
93 Instruction *visitFAdd(BinaryOperator &I);
94 Value *OptimizePointerDifference(
95 Value *LHS, Value *RHS, Type *Ty, bool isNUW);
96 Instruction *visitSub(BinaryOperator &I);
97 Instruction *visitFSub(BinaryOperator &I);
98 Instruction *visitMul(BinaryOperator &I);
99 Instruction *foldPowiReassoc(BinaryOperator &I);
100 Instruction *foldFMulReassoc(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 *commonIDivRemTransforms(BinaryOperator &I);
107 Instruction *commonIRemTransforms(BinaryOperator &I);
108 Instruction *commonIDivTransforms(BinaryOperator &I);
109 Instruction *visitUDiv(BinaryOperator &I);
110 Instruction *visitSDiv(BinaryOperator &I);
111 Instruction *visitFDiv(BinaryOperator &I);
112 Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
113 Instruction *visitAnd(BinaryOperator &I);
114 Instruction *visitOr(BinaryOperator &I);
115 bool sinkNotIntoLogicalOp(Instruction &I);
116 bool sinkNotIntoOtherHandOfLogicalOp(Instruction &I);
117 Instruction *visitXor(BinaryOperator &I);
118 Instruction *visitShl(BinaryOperator &I);
119 Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
120 BinaryOperator *Sh0, const SimplifyQuery &SQ,
121 bool AnalyzeForSignBitExtraction = false);
122 Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
123 BinaryOperator &I);
124 Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
125 BinaryOperator &OldAShr);
126 Instruction *visitAShr(BinaryOperator &I);
127 Instruction *visitLShr(BinaryOperator &I);
128 Instruction *commonShiftTransforms(BinaryOperator &I);
129 Instruction *visitFCmpInst(FCmpInst &I);
130 CmpInst *canonicalizeICmpPredicate(CmpInst &I);
131 Instruction *visitICmpInst(ICmpInst &I);
132 Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
133 BinaryOperator &I);
134 Instruction *commonCastTransforms(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);
149 Instruction *visitSelectInst(SelectInst &SI);
150 Instruction *foldShuffledIntrinsicOperands(IntrinsicInst *II);
151 Value *foldReversedIntrinsicOperands(IntrinsicInst *II);
152 Instruction *visitCallInst(CallInst &CI);
153 Instruction *visitInvokeInst(InvokeInst &II);
154 Instruction *visitCallBrInst(CallBrInst &CBI);
155
156 Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
157 Instruction *visitPHINode(PHINode &PN);
158 Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
159 Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
160 Instruction *visitAllocaInst(AllocaInst &AI);
161 Instruction *visitAllocSite(Instruction &FI);
162 Instruction *visitFree(CallInst &FI, Value *FreedOp);
163 Instruction *visitLoadInst(LoadInst &LI);
164 Instruction *visitStoreInst(StoreInst &SI);
165 Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
166 Instruction *visitUnconditionalBranchInst(BranchInst &BI);
167 Instruction *visitBranchInst(BranchInst &BI);
168 Instruction *visitFenceInst(FenceInst &FI);
169 Instruction *visitSwitchInst(SwitchInst &SI);
170 Instruction *visitReturnInst(ReturnInst &RI);
171 Instruction *visitUnreachableInst(UnreachableInst &I);
172 Instruction *
173 foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
174 Instruction *visitInsertValueInst(InsertValueInst &IV);
175 Instruction *visitInsertElementInst(InsertElementInst &IE);
176 Instruction *visitExtractElementInst(ExtractElementInst &EI);
177 Instruction *simplifyBinOpSplats(ShuffleVectorInst &SVI);
178 Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
179 Instruction *visitExtractValueInst(ExtractValueInst &EV);
180 Instruction *visitLandingPadInst(LandingPadInst &LI);
181 Instruction *visitVAEndInst(VAEndInst &I);
182 Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
183 bool freezeOtherUses(FreezeInst &FI);
184 Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
185 Instruction *visitFreeze(FreezeInst &I);
186
187 /// Specify what to return for unhandled instructions.
188 Instruction *visitInstruction(Instruction &I) { return nullptr; }
189
190 /// True when DB dominates all uses of DI except UI.
191 /// UI must be in the same block as DI.
192 /// The routine checks that the DI parent and DB are different.
193 bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
194 const BasicBlock *DB) const;
195
196 /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
197 bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
198 const unsigned SIOpd);
199
200 LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
201 const Twine &Suffix = "");
202
203 KnownFPClass computeKnownFPClass(Value *Val, FastMathFlags FMF,
204 FPClassTest Interested = fcAllFlags,
205 const Instruction *CtxI = nullptr,
206 unsigned Depth = 0) const {
207 return llvm::computeKnownFPClass(
208 V: Val, FMF, InterestedClasses: Interested, SQ: getSimplifyQuery().getWithInstruction(I: CtxI),
209 Depth);
210 }
211
212 KnownFPClass computeKnownFPClass(Value *Val,
213 FPClassTest Interested = fcAllFlags,
214 const Instruction *CtxI = nullptr,
215 unsigned Depth = 0) const {
216 return llvm::computeKnownFPClass(
217 V: Val, InterestedClasses: Interested, SQ: getSimplifyQuery().getWithInstruction(I: CtxI), Depth);
218 }
219
220 /// Check if fmul \p MulVal, +0.0 will yield +0.0 (or signed zero is
221 /// ignorable).
222 bool fmulByZeroIsZero(Value *MulVal, FastMathFlags FMF,
223 const Instruction *CtxI) const;
224
225 Constant *getLosslessTrunc(Constant *C, Type *TruncTy, unsigned ExtOp) {
226 Constant *TruncC = ConstantExpr::getTrunc(C, Ty: TruncTy);
227 Constant *ExtTruncC =
228 ConstantFoldCastOperand(Opcode: ExtOp, C: TruncC, DestTy: C->getType(), DL);
229 if (ExtTruncC && ExtTruncC == C)
230 return TruncC;
231 return nullptr;
232 }
233
234 Constant *getLosslessUnsignedTrunc(Constant *C, Type *TruncTy) {
235 return getLosslessTrunc(C, TruncTy, ExtOp: Instruction::ZExt);
236 }
237
238 Constant *getLosslessSignedTrunc(Constant *C, Type *TruncTy) {
239 return getLosslessTrunc(C, TruncTy, ExtOp: Instruction::SExt);
240 }
241
242 std::optional<std::pair<Intrinsic::ID, SmallVector<Value *, 3>>>
243 convertOrOfShiftsToFunnelShift(Instruction &Or);
244
245private:
246 bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
247 bool isDesirableIntType(unsigned BitWidth) const;
248 bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
249 bool shouldChangeType(Type *From, Type *To) const;
250 Value *dyn_castNegVal(Value *V) const;
251
252 /// Classify whether a cast is worth optimizing.
253 ///
254 /// This is a helper to decide whether the simplification of
255 /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
256 ///
257 /// \param CI The cast we are interested in.
258 ///
259 /// \return true if this cast actually results in any code being generated and
260 /// if it cannot already be eliminated by some other transformation.
261 bool shouldOptimizeCast(CastInst *CI);
262
263 /// Try to optimize a sequence of instructions checking if an operation
264 /// on LHS and RHS overflows.
265 ///
266 /// If this overflow check is done via one of the overflow check intrinsics,
267 /// then CtxI has to be the call instruction calling that intrinsic. If this
268 /// overflow check is done by arithmetic followed by a compare, then CtxI has
269 /// to be the arithmetic instruction.
270 ///
271 /// If a simplification is possible, stores the simplified result of the
272 /// operation in OperationResult and result of the overflow check in
273 /// OverflowResult, and return true. If no simplification is possible,
274 /// returns false.
275 bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
276 Value *LHS, Value *RHS,
277 Instruction &CtxI, Value *&OperationResult,
278 Constant *&OverflowResult);
279
280 Instruction *visitCallBase(CallBase &Call);
281 Instruction *tryOptimizeCall(CallInst *CI);
282 bool transformConstExprCastCall(CallBase &Call);
283 Instruction *transformCallThroughTrampoline(CallBase &Call,
284 IntrinsicInst &Tramp);
285
286 // Return (a, b) if (LHS, RHS) is known to be (a, b) or (b, a).
287 // Otherwise, return std::nullopt
288 // Currently it matches:
289 // - LHS = (select c, a, b), RHS = (select c, b, a)
290 // - LHS = (phi [a, BB0], [b, BB1]), RHS = (phi [b, BB0], [a, BB1])
291 // - LHS = min(a, b), RHS = max(a, b)
292 std::optional<std::pair<Value *, Value *>> matchSymmetricPair(Value *LHS,
293 Value *RHS);
294
295 Value *simplifyMaskedLoad(IntrinsicInst &II);
296 Instruction *simplifyMaskedStore(IntrinsicInst &II);
297 Instruction *simplifyMaskedGather(IntrinsicInst &II);
298 Instruction *simplifyMaskedScatter(IntrinsicInst &II);
299
300 /// Transform (zext icmp) to bitwise / integer operations in order to
301 /// eliminate it.
302 ///
303 /// \param ICI The icmp of the (zext icmp) pair we are interested in.
304 /// \parem CI The zext of the (zext icmp) pair we are interested in.
305 ///
306 /// \return null if the transformation cannot be performed. If the
307 /// transformation can be performed the new instruction that replaces the
308 /// (zext icmp) pair will be returned.
309 Instruction *transformZExtICmp(ICmpInst *Cmp, ZExtInst &Zext);
310
311 Instruction *transformSExtICmp(ICmpInst *Cmp, SExtInst &Sext);
312
313 bool willNotOverflowSignedAdd(const WithCache<const Value *> &LHS,
314 const WithCache<const Value *> &RHS,
315 const Instruction &CxtI) const {
316 return computeOverflowForSignedAdd(LHS, RHS, CxtI: &CxtI) ==
317 OverflowResult::NeverOverflows;
318 }
319
320 bool willNotOverflowUnsignedAdd(const WithCache<const Value *> &LHS,
321 const WithCache<const Value *> &RHS,
322 const Instruction &CxtI) const {
323 return computeOverflowForUnsignedAdd(LHS, RHS, CxtI: &CxtI) ==
324 OverflowResult::NeverOverflows;
325 }
326
327 bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
328 const Instruction &CxtI, bool IsSigned) const {
329 return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
330 : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
331 }
332
333 bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
334 const Instruction &CxtI) const {
335 return computeOverflowForSignedSub(LHS, RHS, CxtI: &CxtI) ==
336 OverflowResult::NeverOverflows;
337 }
338
339 bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
340 const Instruction &CxtI) const {
341 return computeOverflowForUnsignedSub(LHS, RHS, CxtI: &CxtI) ==
342 OverflowResult::NeverOverflows;
343 }
344
345 bool willNotOverflowSub(const Value *LHS, const Value *RHS,
346 const Instruction &CxtI, bool IsSigned) const {
347 return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
348 : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
349 }
350
351 bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
352 const Instruction &CxtI) const {
353 return computeOverflowForSignedMul(LHS, RHS, CxtI: &CxtI) ==
354 OverflowResult::NeverOverflows;
355 }
356
357 bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
358 const Instruction &CxtI,
359 bool IsNSW = false) const {
360 return computeOverflowForUnsignedMul(LHS, RHS, CxtI: &CxtI, IsNSW) ==
361 OverflowResult::NeverOverflows;
362 }
363
364 bool willNotOverflowMul(const Value *LHS, const Value *RHS,
365 const Instruction &CxtI, bool IsSigned) const {
366 return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
367 : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
368 }
369
370 bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
371 const Value *RHS, const Instruction &CxtI,
372 bool IsSigned) const {
373 switch (Opcode) {
374 case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
375 case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
376 case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
377 default: llvm_unreachable("Unexpected opcode for overflow query");
378 }
379 }
380
381 Value *EmitGEPOffset(GEPOperator *GEP, bool RewriteGEP = false);
382 /// Emit sum of multiple GEP offsets. The GEPs are processed in reverse
383 /// order.
384 Value *EmitGEPOffsets(ArrayRef<GEPOperator *> GEPs, GEPNoWrapFlags NW,
385 Type *IdxTy, bool RewriteGEPs);
386 Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
387 Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
388 Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
389 Instruction *foldFBinOpOfIntCasts(BinaryOperator &I);
390 // Should only be called by `foldFBinOpOfIntCasts`.
391 Instruction *foldFBinOpOfIntCastsFromSign(
392 BinaryOperator &BO, bool OpsFromSigned, std::array<Value *, 2> IntOps,
393 Constant *Op1FpC, SmallVectorImpl<WithCache<const Value *>> &OpsKnown);
394 Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
395 Instruction *narrowBinOp(TruncInst &Trunc);
396 Instruction *narrowMaskedBinOp(BinaryOperator &And);
397 Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
398 Instruction *narrowFunnelShift(TruncInst &Trunc);
399 Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
400 Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
401 Instruction *foldNot(BinaryOperator &I);
402 Instruction *foldBinOpOfDisplacedShifts(BinaryOperator &I);
403
404 /// Determine if a pair of casts can be replaced by a single cast.
405 ///
406 /// \param CI1 The first of a pair of casts.
407 /// \param CI2 The second of a pair of casts.
408 ///
409 /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
410 /// Instruction::CastOps value for a cast that can replace the pair, casting
411 /// CI1->getSrcTy() to CI2->getDstTy().
412 ///
413 /// \see CastInst::isEliminableCastPair
414 Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
415 const CastInst *CI2);
416 Value *simplifyIntToPtrRoundTripCast(Value *Val);
417
418 Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,
419 bool IsAnd, bool IsLogical = false);
420 Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
421
422 Value *foldEqOfParts(Value *Cmp0, Value *Cmp1, bool IsAnd);
423
424 Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
425 bool IsAnd);
426
427 /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
428 /// NOTE: Unlike most of instcombine, this returns a Value which should
429 /// already be inserted into the function.
430 Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
431 bool IsLogicalSelect = false);
432
433 Instruction *foldLogicOfIsFPClass(BinaryOperator &Operator, Value *LHS,
434 Value *RHS);
435
436 Value *foldBooleanAndOr(Value *LHS, Value *RHS, Instruction &I, bool IsAnd,
437 bool IsLogical);
438
439 Value *reassociateBooleanAndOr(Value *LHS, Value *X, Value *Y, Instruction &I,
440 bool IsAnd, bool RHSIsLogical);
441
442 Instruction *
443 canonicalizeConditionalNegationViaMathToSelect(BinaryOperator &i);
444
445 Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D,
446 bool InvertFalseVal = false);
447 Value *getSelectCondition(Value *A, Value *B, bool ABIsTheSame);
448
449 Instruction *foldLShrOverflowBit(BinaryOperator &I);
450 Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
451 Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
452 Instruction *foldIntrinsicIsFPClass(IntrinsicInst &II);
453 Instruction *foldFPSignBitOps(BinaryOperator &I);
454 Instruction *foldFDivConstantDivisor(BinaryOperator &I);
455
456 // Optimize one of these forms:
457 // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
458 // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
459 // into simplier select instruction using isImpliedCondition.
460 Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
461 bool IsAnd);
462
463 Instruction *hoistFNegAboveFMulFDiv(Value *FNegOp, Instruction &FMFSource);
464
465 /// Simplify \p V given that it is known to be non-null.
466 /// Returns the simplified value if possible, otherwise returns nullptr.
467 /// If \p HasDereferenceable is true, the simplification will not perform
468 /// same object checks.
469 Value *simplifyNonNullOperand(Value *V, bool HasDereferenceable,
470 unsigned Depth = 0);
471
472public:
473 /// Create and insert the idiom we use to indicate a block is unreachable
474 /// without having to rewrite the CFG from within InstCombine.
475 void CreateNonTerminatorUnreachable(Instruction *InsertAt) {
476 auto &Ctx = InsertAt->getContext();
477 auto *SI = new StoreInst(ConstantInt::getTrue(Context&: Ctx),
478 PoisonValue::get(T: PointerType::getUnqual(C&: Ctx)),
479 /*isVolatile*/ false, Align(1));
480 InsertNewInstWith(New: SI, Old: InsertAt->getIterator());
481 }
482
483 /// Combiner aware instruction erasure.
484 ///
485 /// When dealing with an instruction that has side effects or produces a void
486 /// value, we can't rely on DCE to delete the instruction. Instead, visit
487 /// methods should return the value returned by this function.
488 Instruction *eraseInstFromFunction(Instruction &I) override {
489 LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
490 assert(I.use_empty() && "Cannot erase instruction that is used!");
491 salvageDebugInfo(I);
492
493 // Make sure that we reprocess all operands now that we reduced their
494 // use counts.
495 SmallVector<Value *> Ops(I.operands());
496 Worklist.remove(I: &I);
497 DC.removeValue(V: &I);
498 I.eraseFromParent();
499 for (Value *Op : Ops)
500 Worklist.handleUseCountDecrement(V: Op);
501 MadeIRChange = true;
502 return nullptr; // Don't do anything with FI
503 }
504
505 OverflowResult computeOverflow(
506 Instruction::BinaryOps BinaryOp, bool IsSigned,
507 Value *LHS, Value *RHS, Instruction *CxtI) const;
508
509 /// Performs a few simplifications for operators which are associative
510 /// or commutative.
511 bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
512
513 /// Tries to simplify binary operations which some other binary
514 /// operation distributes over.
515 ///
516 /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
517 /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
518 /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
519 /// value, or null if it didn't simplify.
520 Value *foldUsingDistributiveLaws(BinaryOperator &I);
521
522 /// Tries to simplify add operations using the definition of remainder.
523 ///
524 /// The definition of remainder is X % C = X - (X / C ) * C. The add
525 /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
526 /// X % (C0 * C1)
527 Value *SimplifyAddWithRemainder(BinaryOperator &I);
528
529 // Binary Op helper for select operations where the expression can be
530 // efficiently reorganized.
531 Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
532 Value *RHS);
533
534 // If `I` has operand `(ctpop (not x))`, fold `I` with `(sub nuw nsw
535 // BitWidth(x), (ctpop x))`.
536 Instruction *tryFoldInstWithCtpopWithNot(Instruction *I);
537
538 // (Binop1 (Binop2 (logic_shift X, C), C1), (logic_shift Y, C))
539 // -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
540 // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))
541 // -> (BinOp (logic_shift (BinOp X, Y)), Mask)
542 Instruction *foldBinOpShiftWithShift(BinaryOperator &I);
543
544 /// Tries to simplify binops of select and cast of the select condition.
545 ///
546 /// (Binop (cast C), (select C, T, F))
547 /// -> (select C, C0, C1)
548 Instruction *foldBinOpOfSelectAndCastOfSelectCondition(BinaryOperator &I);
549
550 /// This tries to simplify binary operations by factorizing out common terms
551 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
552 Value *tryFactorizationFolds(BinaryOperator &I);
553
554 /// Match a select chain which produces one of three values based on whether
555 /// the LHS is less than, equal to, or greater than RHS respectively.
556 /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
557 /// Equal and Greater values are saved in the matching process and returned to
558 /// the caller.
559 bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
560 ConstantInt *&Less, ConstantInt *&Equal,
561 ConstantInt *&Greater);
562
563 /// Attempts to replace I with a simpler value based on the demanded
564 /// bits.
565 Value *SimplifyDemandedUseBits(Instruction *I, const APInt &DemandedMask,
566 KnownBits &Known, const SimplifyQuery &Q,
567 unsigned Depth = 0);
568 using InstCombiner::SimplifyDemandedBits;
569 bool SimplifyDemandedBits(Instruction *I, unsigned Op,
570 const APInt &DemandedMask, KnownBits &Known,
571 const SimplifyQuery &Q,
572 unsigned Depth = 0) override;
573
574 /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
575 /// bits. It also tries to handle simplifications that can be done based on
576 /// DemandedMask, but without modifying the Instruction.
577 Value *SimplifyMultipleUseDemandedBits(Instruction *I,
578 const APInt &DemandedMask,
579 KnownBits &Known,
580 const SimplifyQuery &Q,
581 unsigned Depth = 0);
582
583 /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
584 /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
585 Value *simplifyShrShlDemandedBits(
586 Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
587 const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
588
589 /// Tries to simplify operands to an integer instruction based on its
590 /// demanded bits.
591 bool SimplifyDemandedInstructionBits(Instruction &Inst);
592 bool SimplifyDemandedInstructionBits(Instruction &Inst, KnownBits &Known);
593
594 Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
595 APInt &PoisonElts, unsigned Depth = 0,
596 bool AllowMultipleUsers = false) override;
597
598 /// Attempts to replace V with a simpler value based on the demanded
599 /// floating-point classes
600 Value *SimplifyDemandedUseFPClass(Value *V, FPClassTest DemandedMask,
601 KnownFPClass &Known, Instruction *CxtI,
602 unsigned Depth = 0);
603 bool SimplifyDemandedFPClass(Instruction *I, unsigned Op,
604 FPClassTest DemandedMask, KnownFPClass &Known,
605 unsigned Depth = 0);
606
607 /// Common transforms for add / disjoint or
608 Instruction *foldAddLikeCommutative(Value *LHS, Value *RHS, bool NSW,
609 bool NUW);
610
611 /// Canonicalize the position of binops relative to shufflevector.
612 Instruction *foldVectorBinop(BinaryOperator &Inst);
613 Instruction *foldVectorSelect(SelectInst &Sel);
614 Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
615 Constant *unshuffleConstant(ArrayRef<int> ShMask, Constant *C,
616 VectorType *NewCTy);
617
618 /// Given a binary operator, cast instruction, or select which has a PHI node
619 /// as operand #0, see if we can fold the instruction into the PHI (which is
620 /// only possible if all operands to the PHI are constants).
621 Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN,
622 bool AllowMultipleUses = false);
623
624 /// Try to fold binary operators whose operands are simple interleaved
625 /// recurrences to a single recurrence. This is a common pattern in reduction
626 /// operations.
627 /// Example:
628 /// %phi1 = phi [init1, %BB1], [%op1, %BB2]
629 /// %phi2 = phi [init2, %BB1], [%op2, %BB2]
630 /// %op1 = binop %phi1, constant1
631 /// %op2 = binop %phi2, constant2
632 /// %rdx = binop %op1, %op2
633 /// -->
634 /// %phi_combined = phi [init_combined, %BB1], [%op_combined, %BB2]
635 /// %rdx_combined = binop %phi_combined, constant_combined
636 Instruction *foldBinopWithRecurrence(BinaryOperator &BO);
637
638 /// For a binary operator with 2 phi operands, try to hoist the binary
639 /// operation before the phi. This can result in fewer instructions in
640 /// patterns where at least one set of phi operands simplifies.
641 /// Example:
642 /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
643 /// -->
644 /// BB1: BO = binop X, Y
645 /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
646 Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
647
648 /// Given an instruction with a select as one operand and a constant as the
649 /// other operand, try to fold the binary operator into the select arguments.
650 /// This also works for Cast instructions, which obviously do not have a
651 /// second operand.
652 Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
653 bool FoldWithMultiUse = false);
654
655 /// This is a convenience wrapper function for the above two functions.
656 Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
657
658 Instruction *foldAddWithConstant(BinaryOperator &Add);
659
660 Instruction *foldSquareSumInt(BinaryOperator &I);
661 Instruction *foldSquareSumFP(BinaryOperator &I);
662
663 /// Try to rotate an operation below a PHI node, using PHI nodes for
664 /// its operands.
665 Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
666 Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
667 Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
668 Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
669 Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
670 Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
671 Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
672 Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
673
674 /// If the phi is within a phi web, which is formed by the def-use chain
675 /// of phis and all the phis in the web are only used in the other phis.
676 /// In this case, these phis are dead and we will remove all of them.
677 bool foldDeadPhiWeb(PHINode &PN);
678
679 /// If an integer typed PHI has only one use which is an IntToPtr operation,
680 /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
681 /// insert a new pointer typed PHI and replace the original one.
682 bool foldIntegerTypedPHI(PHINode &PN);
683
684 /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
685 /// folded operation.
686 void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
687
688 Value *foldPtrToIntOfGEP(Type *IntTy, Value *Ptr);
689 Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, CmpPredicate Cond,
690 Instruction &I);
691 Instruction *foldSelectICmp(CmpPredicate Pred, SelectInst *SI, Value *RHS,
692 const ICmpInst &I);
693 bool foldAllocaCmp(AllocaInst *Alloca);
694 Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI,
695 GetElementPtrInst *GEP,
696 GlobalVariable *GV, CmpInst &ICI,
697 ConstantInt *AndCst = nullptr);
698 Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
699 Constant *RHSC);
700 Instruction *foldICmpAddOpConst(Value *X, const APInt &C, CmpPredicate Pred);
701 Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
702 Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
703
704 Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
705 Instruction *foldICmpWithDominatingICmp(ICmpInst &Cmp);
706 Instruction *foldICmpWithConstant(ICmpInst &Cmp);
707 Instruction *foldICmpUsingBoolRange(ICmpInst &I);
708 Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
709 Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
710 Instruction *foldICmpInstWithConstantAllowPoison(ICmpInst &Cmp,
711 const APInt &C);
712 Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
713 Instruction *foldICmpWithMinMax(Instruction &I, MinMaxIntrinsic *MinMax,
714 Value *Z, CmpPredicate Pred);
715 Instruction *foldICmpEquality(ICmpInst &Cmp);
716 Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
717 Instruction *foldSignBitTest(ICmpInst &I);
718 Instruction *foldICmpWithZero(ICmpInst &Cmp);
719
720 Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
721
722 Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
723 const APInt &C);
724 Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
725 ConstantInt *C);
726 Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
727 const APInt &C);
728 Instruction *foldICmpTruncWithTruncOrExt(ICmpInst &Cmp,
729 const SimplifyQuery &Q);
730 Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
731 const APInt &C);
732 Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
733 const APInt &C);
734 Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
735 const APInt &C);
736 Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
737 const APInt &C);
738 Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
739 const APInt &C);
740 Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
741 const APInt &C);
742 Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
743 const APInt &C);
744 Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
745 const APInt &C);
746 Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
747 const APInt &C);
748 Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
749 const APInt &C);
750 Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
751 const APInt &C);
752 Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
753 const APInt &C1);
754 Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
755 const APInt &C1, const APInt &C2);
756 Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor,
757 const APInt &C);
758 Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
759 const APInt &C2);
760 Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
761 const APInt &C2);
762
763 Instruction *foldICmpBinOpWithConstantViaTruthTable(ICmpInst &Cmp,
764 BinaryOperator *BO,
765 const APInt &C);
766 Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
767 BinaryOperator *BO,
768 const APInt &C);
769 Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
770 const APInt &C);
771 Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
772 const APInt &C);
773 Instruction *foldICmpBitCast(ICmpInst &Cmp);
774 Instruction *foldICmpWithTrunc(ICmpInst &Cmp);
775 Instruction *foldICmpCommutative(CmpPredicate Pred, Value *Op0, Value *Op1,
776 ICmpInst &CxtI);
777
778 // Helpers of visitSelectInst().
779 Instruction *foldSelectOfBools(SelectInst &SI);
780 Instruction *foldSelectToCmp(SelectInst &SI);
781 Instruction *foldSelectExtConst(SelectInst &Sel);
782 Instruction *foldSelectEqualityTest(SelectInst &SI);
783 Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
784 Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
785 Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
786 Value *A, Value *B, Instruction &Outer,
787 SelectPatternFlavor SPF2, Value *C);
788 Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
789 Value *foldSelectWithConstOpToBinOp(ICmpInst *Cmp, Value *TrueVal,
790 Value *FalseVal);
791 Instruction *foldSelectValueEquivalence(SelectInst &SI, CmpInst &CI);
792 bool replaceInInstruction(Value *V, Value *Old, Value *New,
793 unsigned Depth = 0);
794
795 Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
796 bool isSigned, bool Inside);
797 bool mergeStoreIntoSuccessor(StoreInst &SI);
798
799 /// Given an initial instruction, check to see if it is the root of a
800 /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
801 /// intrinsic.
802 Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
803 bool MatchBitReversals);
804
805 Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
806 Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
807
808 Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
809
810 bool tryToSinkInstruction(Instruction *I, BasicBlock *DestBlock);
811 void tryToSinkInstructionDbgValues(
812 Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock,
813 BasicBlock *DestBlock, SmallVectorImpl<DbgVariableIntrinsic *> &DbgUsers);
814 void tryToSinkInstructionDbgVariableRecords(
815 Instruction *I, BasicBlock::iterator InsertPos, BasicBlock *SrcBlock,
816 BasicBlock *DestBlock, SmallVectorImpl<DbgVariableRecord *> &DPUsers);
817
818 bool removeInstructionsBeforeUnreachable(Instruction &I);
819 void addDeadEdge(BasicBlock *From, BasicBlock *To,
820 SmallVectorImpl<BasicBlock *> &Worklist);
821 void handleUnreachableFrom(Instruction *I,
822 SmallVectorImpl<BasicBlock *> &Worklist);
823 void handlePotentiallyDeadBlocks(SmallVectorImpl<BasicBlock *> &Worklist);
824 void handlePotentiallyDeadSuccessors(BasicBlock *BB, BasicBlock *LiveSucc);
825 void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser = nullptr);
826
827 /// Take the exact integer log2 of the value. If DoFold is true, create the
828 /// actual instructions, otherwise return a non-null dummy value. Return
829 /// nullptr on failure. Note, if DoFold is true the caller must ensure that
830 /// takeLog2 will succeed, otherwise it may create stray instructions.
831 Value *takeLog2(Value *Op, unsigned Depth, bool AssumeNonZero, bool DoFold);
832
833 Value *tryGetLog2(Value *Op, bool AssumeNonZero) {
834 if (takeLog2(Op, /*Depth=*/Depth: 0, AssumeNonZero, /*DoFold=*/DoFold: false))
835 return takeLog2(Op, /*Depth=*/Depth: 0, AssumeNonZero, /*DoFold=*/DoFold: true);
836 return nullptr;
837 }
838};
839
840class Negator final {
841 /// Top-to-bottom, def-to-use negated instruction tree we produced.
842 SmallVector<Instruction *, NegatorMaxNodesSSO> NewInstructions;
843
844 using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
845 BuilderTy Builder;
846
847 const DominatorTree &DT;
848
849 const bool IsTrulyNegation;
850
851 SmallDenseMap<Value *, Value *> NegationsCache;
852
853 Negator(LLVMContext &C, const DataLayout &DL, const DominatorTree &DT,
854 bool IsTrulyNegation);
855
856#if LLVM_ENABLE_STATS
857 unsigned NumValuesVisitedInThisNegator = 0;
858 ~Negator();
859#endif
860
861 using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
862 Value * /*NegatedRoot*/>;
863
864 std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
865
866 [[nodiscard]] Value *visitImpl(Value *V, bool IsNSW, unsigned Depth);
867
868 [[nodiscard]] Value *negate(Value *V, bool IsNSW, unsigned Depth);
869
870 /// Recurse depth-first and attempt to sink the negation.
871 /// FIXME: use worklist?
872 [[nodiscard]] std::optional<Result> run(Value *Root, bool IsNSW);
873
874 Negator(const Negator &) = delete;
875 Negator(Negator &&) = delete;
876 Negator &operator=(const Negator &) = delete;
877 Negator &operator=(Negator &&) = delete;
878
879public:
880 /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
881 /// otherwise returns negated value.
882 [[nodiscard]] static Value *Negate(bool LHSIsZero, bool IsNSW, Value *Root,
883 InstCombinerImpl &IC);
884};
885
886struct CommonPointerBase {
887 /// Common base pointer.
888 Value *Ptr = nullptr;
889 /// LHS GEPs until common base.
890 SmallVector<GEPOperator *> LHSGEPs;
891 /// RHS GEPs until common base.
892 SmallVector<GEPOperator *> RHSGEPs;
893 /// LHS GEP NoWrapFlags until common base.
894 GEPNoWrapFlags LHSNW = GEPNoWrapFlags::all();
895 /// RHS GEP NoWrapFlags until common base.
896 GEPNoWrapFlags RHSNW = GEPNoWrapFlags::all();
897
898 static CommonPointerBase compute(Value *LHS, Value *RHS);
899};
900
901} // end namespace llvm
902
903#undef DEBUG_TYPE
904
905#endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
906