LLVM  15.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"
24 #include "llvm/IR/PatternMatch.h"
25 #include "llvm/IR/Value.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/KnownBits.h"
30 #include <cassert>
31 
32 #define DEBUG_TYPE "instcombine"
34 
35 using 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.
39 static 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.
43 static constexpr unsigned NegatorMaxNodesSSO = 16;
44 
45 namespace llvm {
46 
47 class AAResults;
48 class APInt;
49 class AssumptionCache;
50 class BlockFrequencyInfo;
51 class DataLayout;
52 class DominatorTree;
53 class GEPOperator;
54 class GlobalVariable;
55 class LoopInfo;
56 class OptimizationRemarkEmitter;
57 class ProfileSummaryInfo;
58 class TargetLibraryInfo;
59 class User;
60 
62  : public InstCombiner,
63  public InstVisitor<InstCombinerImpl, Instruction *> {
64 public:
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 sinkNotIntoOtherHandOfAndOrOr(BinaryOperator &I);
110  Instruction *visitXor(BinaryOperator &I);
111  Instruction *visitShl(BinaryOperator &I);
112  Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
113  BinaryOperator *Sh0, const SimplifyQuery &SQ,
114  bool AnalyzeForSignBitExtraction = false);
115  Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
116  BinaryOperator &I);
117  Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
118  BinaryOperator &OldAShr);
119  Instruction *visitAShr(BinaryOperator &I);
120  Instruction *visitLShr(BinaryOperator &I);
121  Instruction *commonShiftTransforms(BinaryOperator &I);
122  Instruction *visitFCmpInst(FCmpInst &I);
123  CmpInst *canonicalizeICmpPredicate(CmpInst &I);
124  Instruction *visitICmpInst(ICmpInst &I);
125  Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
126  BinaryOperator &I);
127  Instruction *commonCastTransforms(CastInst &CI);
128  Instruction *commonPointerCastTransforms(CastInst &CI);
129  Instruction *visitTrunc(TruncInst &CI);
130  Instruction *visitZExt(ZExtInst &CI);
131  Instruction *visitSExt(SExtInst &CI);
132  Instruction *visitFPTrunc(FPTruncInst &CI);
133  Instruction *visitFPExt(CastInst &CI);
134  Instruction *visitFPToUI(FPToUIInst &FI);
135  Instruction *visitFPToSI(FPToSIInst &FI);
136  Instruction *visitUIToFP(CastInst &CI);
137  Instruction *visitSIToFP(CastInst &CI);
138  Instruction *visitPtrToInt(PtrToIntInst &CI);
139  Instruction *visitIntToPtr(IntToPtrInst &CI);
140  Instruction *visitBitCast(BitCastInst &CI);
141  Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
142  Instruction *foldItoFPtoI(CastInst &FI);
143  Instruction *visitSelectInst(SelectInst &SI);
144  Instruction *visitCallInst(CallInst &CI);
145  Instruction *visitInvokeInst(InvokeInst &II);
146  Instruction *visitCallBrInst(CallBrInst &CBI);
147 
148  Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
149  Instruction *visitPHINode(PHINode &PN);
150  Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
151  Instruction *visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src);
152  Instruction *visitGEPOfBitcast(BitCastInst *BCI, GetElementPtrInst &GEP);
153  Instruction *visitAllocaInst(AllocaInst &AI);
154  Instruction *visitAllocSite(Instruction &FI);
155  Instruction *visitFree(CallInst &FI);
156  Instruction *visitLoadInst(LoadInst &LI);
157  Instruction *visitStoreInst(StoreInst &SI);
158  Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
159  Instruction *visitUnconditionalBranchInst(BranchInst &BI);
160  Instruction *visitBranchInst(BranchInst &BI);
161  Instruction *visitFenceInst(FenceInst &FI);
162  Instruction *visitSwitchInst(SwitchInst &SI);
163  Instruction *visitReturnInst(ReturnInst &RI);
164  Instruction *visitUnreachableInst(UnreachableInst &I);
165  Instruction *
166  foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
167  Instruction *visitInsertValueInst(InsertValueInst &IV);
168  Instruction *visitInsertElementInst(InsertElementInst &IE);
169  Instruction *visitExtractElementInst(ExtractElementInst &EI);
170  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
171  Instruction *visitExtractValueInst(ExtractValueInst &EV);
172  Instruction *visitLandingPadInst(LandingPadInst &LI);
173  Instruction *visitVAEndInst(VAEndInst &I);
174  Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
175  bool freezeOtherUses(FreezeInst &FI);
176  Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
177  Instruction *visitFreeze(FreezeInst &I);
178 
179  /// Specify what to return for unhandled instructions.
180  Instruction *visitInstruction(Instruction &I) { return nullptr; }
181 
182  /// True when DB dominates all uses of DI except UI.
183  /// UI must be in the same block as DI.
184  /// The routine checks that the DI parent and DB are different.
185  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
186  const BasicBlock *DB) const;
187 
188  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
189  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
190  const unsigned SIOpd);
191 
192  LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
193  const Twine &Suffix = "");
194 
195 private:
196  bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
197  bool isDesirableIntType(unsigned BitWidth) const;
198  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
199  bool shouldChangeType(Type *From, Type *To) const;
200  Value *dyn_castNegVal(Value *V) const;
201 
202  /// Classify whether a cast is worth optimizing.
203  ///
204  /// This is a helper to decide whether the simplification of
205  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
206  ///
207  /// \param CI The cast we are interested in.
208  ///
209  /// \return true if this cast actually results in any code being generated and
210  /// if it cannot already be eliminated by some other transformation.
211  bool shouldOptimizeCast(CastInst *CI);
212 
213  /// Try to optimize a sequence of instructions checking if an operation
214  /// on LHS and RHS overflows.
215  ///
216  /// If this overflow check is done via one of the overflow check intrinsics,
217  /// then CtxI has to be the call instruction calling that intrinsic. If this
218  /// overflow check is done by arithmetic followed by a compare, then CtxI has
219  /// to be the arithmetic instruction.
220  ///
221  /// If a simplification is possible, stores the simplified result of the
222  /// operation in OperationResult and result of the overflow check in
223  /// OverflowResult, and return true. If no simplification is possible,
224  /// returns false.
225  bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
226  Value *LHS, Value *RHS,
227  Instruction &CtxI, Value *&OperationResult,
229 
230  Instruction *visitCallBase(CallBase &Call);
231  Instruction *tryOptimizeCall(CallInst *CI);
232  bool transformConstExprCastCall(CallBase &Call);
233  Instruction *transformCallThroughTrampoline(CallBase &Call,
234  IntrinsicInst &Tramp);
235 
236  Value *simplifyMaskedLoad(IntrinsicInst &II);
237  Instruction *simplifyMaskedStore(IntrinsicInst &II);
238  Instruction *simplifyMaskedGather(IntrinsicInst &II);
239  Instruction *simplifyMaskedScatter(IntrinsicInst &II);
240 
241  /// Transform (zext icmp) to bitwise / integer operations in order to
242  /// eliminate it.
243  ///
244  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
245  /// \parem CI The zext of the (zext icmp) pair we are interested in.
246  ///
247  /// \return null if the transformation cannot be performed. If the
248  /// transformation can be performed the new instruction that replaces the
249  /// (zext icmp) pair will be returned.
250  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI);
251 
252  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
253 
254  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
255  const Instruction &CxtI) const {
256  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
258  }
259 
260  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
261  const Instruction &CxtI) const {
262  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
264  }
265 
266  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
267  const Instruction &CxtI, bool IsSigned) const {
268  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
269  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
270  }
271 
272  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
273  const Instruction &CxtI) const {
274  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
276  }
277 
278  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
279  const Instruction &CxtI) const {
280  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
282  }
283 
284  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
285  const Instruction &CxtI, bool IsSigned) const {
286  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
287  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
288  }
289 
290  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
291  const Instruction &CxtI) const {
292  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
294  }
295 
296  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
297  const Instruction &CxtI) const {
298  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
300  }
301 
302  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
303  const Instruction &CxtI, bool IsSigned) const {
304  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
305  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
306  }
307 
309  const Value *RHS, const Instruction &CxtI,
310  bool IsSigned) const {
311  switch (Opcode) {
312  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
313  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
314  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
315  default: llvm_unreachable("Unexpected opcode for overflow query");
316  }
317  }
318 
319  Value *EmitGEPOffset(User *GEP);
320  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
321  Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
322  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
323  Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
324  Instruction *narrowBinOp(TruncInst &Trunc);
325  Instruction *narrowMaskedBinOp(BinaryOperator &And);
326  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
327  Instruction *narrowFunnelShift(TruncInst &Trunc);
328  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
329  Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
330  Instruction *foldNot(BinaryOperator &I);
331 
332  void freelyInvertAllUsersOf(Value *V);
333 
334  /// Determine if a pair of casts can be replaced by a single cast.
335  ///
336  /// \param CI1 The first of a pair of casts.
337  /// \param CI2 The second of a pair of casts.
338  ///
339  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
340  /// Instruction::CastOps value for a cast that can replace the pair, casting
341  /// CI1->getSrcTy() to CI2->getDstTy().
342  ///
343  /// \see CastInst::isEliminableCastPair
344  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
345  const CastInst *CI2);
346  Value *simplifyIntToPtrRoundTripCast(Value *Val);
347 
348  Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,
349  bool IsAnd, bool IsLogical = false);
350  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
351 
352  Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
353 
354  Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
355  bool IsAnd);
356 
357  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
358  /// NOTE: Unlike most of instcombine, this returns a Value which should
359  /// already be inserted into the function.
360  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
361  bool IsLogicalSelect = false);
362 
363  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
364  Instruction *CxtI, bool IsAnd,
365  bool IsLogical = false);
366  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
367  Value *getSelectCondition(Value *A, Value *B);
368 
369  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
370  Instruction *foldFPSignBitOps(BinaryOperator &I);
371 
372  // Optimize one of these forms:
373  // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
374  // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
375  // into simplier select instruction using isImpliedCondition.
376  Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
377  bool IsAnd);
378 
379 public:
380  /// Inserts an instruction \p New before instruction \p Old
381  ///
382  /// Also adds the new instruction to the worklist and returns \p New so that
383  /// it is suitable for use as the return from the visitation patterns.
385  assert(New && !New->getParent() &&
386  "New instruction already inserted into a basic block!");
387  BasicBlock *BB = Old.getParent();
388  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
389  Worklist.add(New);
390  return New;
391  }
392 
393  /// Same as InsertNewInstBefore, but also sets the debug loc.
395  New->setDebugLoc(Old.getDebugLoc());
396  return InsertNewInstBefore(New, Old);
397  }
398 
399  /// A combiner-aware RAUW-like routine.
400  ///
401  /// This method is to be used when an instruction is found to be dead,
402  /// replaceable with another preexisting expression. Here we add all uses of
403  /// I to the worklist, replace all uses of I with the new value, then return
404  /// I, so that the inst combiner will know that I was modified.
406  // If there are no uses to replace, then we return nullptr to indicate that
407  // no changes were made to the program.
408  if (I.use_empty()) return nullptr;
409 
410  Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
411 
412  // If we are replacing the instruction with itself, this must be in a
413  // segment of unreachable code, so just clobber the instruction.
414  if (&I == V)
415  V = PoisonValue::get(I.getType());
416 
417  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
418  << " with " << *V << '\n');
419 
420  I.replaceAllUsesWith(V);
421  MadeIRChange = true;
422  return &I;
423  }
424 
425  /// Replace operand of instruction and add old operand to the worklist.
426  Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
427  Worklist.addValue(I.getOperand(OpNum));
428  I.setOperand(OpNum, V);
429  return &I;
430  }
431 
432  /// Replace use and add the previously used value to the worklist.
433  void replaceUse(Use &U, Value *NewValue) {
434  Worklist.addValue(U);
435  U = NewValue;
436  }
437 
438  /// Create and insert the idiom we use to indicate a block is unreachable
439  /// without having to rewrite the CFG from within InstCombine.
441  auto &Ctx = InsertAt->getContext();
444  InsertAt);
445  }
446 
447 
448  /// Combiner aware instruction erasure.
449  ///
450  /// When dealing with an instruction that has side effects or produces a void
451  /// value, we can't rely on DCE to delete the instruction. Instead, visit
452  /// methods should return the value returned by this function.
454  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
455  assert(I.use_empty() && "Cannot erase instruction that is used!");
457 
458  // Make sure that we reprocess all operands now that we reduced their
459  // use counts.
460  for (Use &Operand : I.operands())
461  if (auto *Inst = dyn_cast<Instruction>(Operand))
462  Worklist.add(Inst);
463 
464  Worklist.remove(&I);
465  I.eraseFromParent();
466  MadeIRChange = true;
467  return nullptr; // Don't do anything with FI
468  }
469 
470  void computeKnownBits(const Value *V, KnownBits &Known,
471  unsigned Depth, const Instruction *CxtI) const {
472  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
473  }
474 
475  KnownBits computeKnownBits(const Value *V, unsigned Depth,
476  const Instruction *CxtI) const {
477  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
478  }
479 
480  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
481  unsigned Depth = 0,
482  const Instruction *CxtI = nullptr) {
483  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
484  }
485 
486  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
487  const Instruction *CxtI = nullptr) const {
488  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
489  }
490 
491  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
492  const Instruction *CxtI = nullptr) const {
493  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
494  }
495 
497  const Value *RHS,
498  const Instruction *CxtI) const {
499  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
500  }
501 
503  const Value *RHS,
504  const Instruction *CxtI) const {
505  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
506  }
507 
509  const Value *RHS,
510  const Instruction *CxtI) const {
511  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
512  }
513 
515  const Value *RHS,
516  const Instruction *CxtI) const {
517  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
518  }
519 
521  const Value *RHS,
522  const Instruction *CxtI) const {
523  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
524  }
525 
527  const Instruction *CxtI) const {
528  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
529  }
530 
531  OverflowResult computeOverflow(
532  Instruction::BinaryOps BinaryOp, bool IsSigned,
533  Value *LHS, Value *RHS, Instruction *CxtI) const;
534 
535  /// Performs a few simplifications for operators which are associative
536  /// or commutative.
537  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
538 
539  /// Tries to simplify binary operations which some other binary
540  /// operation distributes over.
541  ///
542  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
543  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
544  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
545  /// value, or null if it didn't simplify.
546  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
547 
548  /// Tries to simplify add operations using the definition of remainder.
549  ///
550  /// The definition of remainder is X % C = X - (X / C ) * C. The add
551  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
552  /// X % (C0 * C1)
553  Value *SimplifyAddWithRemainder(BinaryOperator &I);
554 
555  // Binary Op helper for select operations where the expression can be
556  // efficiently reorganized.
557  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
558  Value *RHS);
559 
560  /// This tries to simplify binary operations by factorizing out common terms
561  /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
562  Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
563  Value *, Value *, Value *);
564 
565  /// Match a select chain which produces one of three values based on whether
566  /// the LHS is less than, equal to, or greater than RHS respectively.
567  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
568  /// Equal and Greater values are saved in the matching process and returned to
569  /// the caller.
570  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
572  ConstantInt *&Greater);
573 
574  /// Attempts to replace V with a simpler value based on the demanded
575  /// bits.
576  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
577  unsigned Depth, Instruction *CxtI);
578  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
579  const APInt &DemandedMask, KnownBits &Known,
580  unsigned Depth = 0) override;
581 
582  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
583  /// bits. It also tries to handle simplifications that can be done based on
584  /// DemandedMask, but without modifying the Instruction.
585  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
586  const APInt &DemandedMask,
587  KnownBits &Known,
588  unsigned Depth, Instruction *CxtI);
589 
590  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
591  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
592  Value *simplifyShrShlDemandedBits(
593  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
594  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
595 
596  /// Tries to simplify operands to an integer instruction based on its
597  /// demanded bits.
598  bool SimplifyDemandedInstructionBits(Instruction &Inst);
599 
600  virtual Value *
601  SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
602  unsigned Depth = 0,
603  bool AllowMultipleUsers = false) override;
604 
605  /// Canonicalize the position of binops relative to shufflevector.
606  Instruction *foldVectorBinop(BinaryOperator &Inst);
607  Instruction *foldVectorSelect(SelectInst &Sel);
608  Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
609 
610  /// Given a binary operator, cast instruction, or select which has a PHI node
611  /// as operand #0, see if we can fold the instruction into the PHI (which is
612  /// only possible if all operands to the PHI are constants).
613  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
614 
615  /// For a binary operator with 2 phi operands, try to hoist the binary
616  /// operation before the phi. This can result in fewer instructions in
617  /// patterns where at least one set of phi operands simplifies.
618  /// Example:
619  /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
620  /// -->
621  /// BB1: BO = binop X, Y
622  /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
623  Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
624 
625  /// Given an instruction with a select as one operand and a constant as the
626  /// other operand, try to fold the binary operator into the select arguments.
627  /// This also works for Cast instructions, which obviously do not have a
628  /// second operand.
629  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
630  bool FoldWithMultiUse = false);
631 
632  /// This is a convenience wrapper function for the above two functions.
633  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
634 
635  Instruction *foldAddWithConstant(BinaryOperator &Add);
636 
637  /// Try to rotate an operation below a PHI node, using PHI nodes for
638  /// its operands.
639  Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
640  Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
641  Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
642  Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
643  Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
644  Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
645  Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
646  Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
647 
648  /// If an integer typed PHI has only one use which is an IntToPtr operation,
649  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
650  /// insert a new pointer typed PHI and replace the original one.
651  Instruction *foldIntegerTypedPHI(PHINode &PN);
652 
653  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
654  /// folded operation.
655  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
656 
657  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
659  Instruction *foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI,
660  Value *RHS, const ICmpInst &I);
661  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca);
662  Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI,
664  GlobalVariable *GV, CmpInst &ICI,
665  ConstantInt *AndCst = nullptr);
666  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
667  Constant *RHSC);
668  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
669  ICmpInst::Predicate Pred);
670  Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
671  Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
672 
673  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
675  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
676  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
677  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
678  Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
679  const APInt &C);
680  Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
681  Instruction *foldICmpEquality(ICmpInst &Cmp);
682  Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
683  Instruction *foldSignBitTest(ICmpInst &I);
684  Instruction *foldICmpWithZero(ICmpInst &Cmp);
685 
686  Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
687 
688  Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
689  const APInt &C);
690  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
691  ConstantInt *C);
692  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
693  const APInt &C);
694  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
695  const APInt &C);
696  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
697  const APInt &C);
698  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
699  const APInt &C);
700  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
701  const APInt &C);
702  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
703  const APInt &C);
704  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
705  const APInt &C);
706  Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
707  const APInt &C);
708  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
709  const APInt &C);
710  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
711  const APInt &C);
712  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
713  const APInt &C);
714  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
715  const APInt &C);
716  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
717  const APInt &C1);
718  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
719  const APInt &C1, const APInt &C2);
720  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
721  const APInt &C2);
722  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
723  const APInt &C2);
724 
725  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
726  BinaryOperator *BO,
727  const APInt &C);
728  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
729  const APInt &C);
730  Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
731  const APInt &C);
732  Instruction *foldICmpBitCast(ICmpInst &Cmp);
733 
734  // Helpers of visitSelectInst().
735  Instruction *foldSelectExtConst(SelectInst &Sel);
736  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
737  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
738  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
739  Value *A, Value *B, Instruction &Outer,
740  SelectPatternFlavor SPF2, Value *C);
741  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
742  Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
743 
744  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
745  bool isSigned, bool Inside);
746  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
747  bool mergeStoreIntoSuccessor(StoreInst &SI);
748 
749  /// Given an initial instruction, check to see if it is the root of a
750  /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
751  /// intrinsic.
752  Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
753  bool MatchBitReversals);
754 
755  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
756  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
757 
758  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
759 
760  /// Returns a value X such that Val = X * Scale, or null if none.
761  ///
762  /// If the multiplication is known not to overflow then NoSignedWrap is set.
763  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
764 };
765 
766 class Negator final {
767  /// Top-to-bottom, def-to-use negated instruction tree we produced.
769 
772 
773  const DataLayout &DL;
774  AssumptionCache &AC;
775  const DominatorTree &DT;
776 
777  const bool IsTrulyNegation;
778 
779  SmallDenseMap<Value *, Value *> NegationsCache;
780 
782  const DominatorTree &DT, bool IsTrulyNegation);
783 
784 #if LLVM_ENABLE_STATS
785  unsigned NumValuesVisitedInThisNegator = 0;
786  ~Negator();
787 #endif
788 
789  using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
790  Value * /*NegatedRoot*/>;
791 
792  std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
793 
794  LLVM_NODISCARD Value *visitImpl(Value *V, unsigned Depth);
795 
796  LLVM_NODISCARD Value *negate(Value *V, unsigned Depth);
797 
798  /// Recurse depth-first and attempt to sink the negation.
799  /// FIXME: use worklist?
801 
802  Negator(const Negator &) = delete;
803  Negator(Negator &&) = delete;
804  Negator &operator=(const Negator &) = delete;
805  Negator &operator=(Negator &&) = delete;
806 
807 public:
808  /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
809  /// otherwise returns negated value.
810  LLVM_NODISCARD static Value *Negate(bool LHSIsZero, Value *Root,
811  InstCombinerImpl &IC);
812 };
813 
814 } // end namespace llvm
815 
816 #undef DEBUG_TYPE
817 
818 #endif // LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
llvm::InstCombinerImpl::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
Definition: InstCombineInternal.h:480
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm::object::Equal
@ Equal
Definition: COFFModuleDefinition.cpp:36
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3004
llvm::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if 'V & Mask' is known to be zero.
Definition: ValueTracking.cpp:391
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
InstCombiner.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:719
llvm::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4844
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
llvm::ExtractElementInst
This instruction extracts a single (scalar) element from a VectorType value.
Definition: Instructions.h:1859
TargetFolder.h
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5212
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::InstCombinerImpl::InsertNewInstBefore
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombineInternal.h:384
Statistic.h
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2903
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::GlobalVariable
Definition: GlobalVariable.h:39
llvm::SmallDenseMap
Definition: DenseMap.h:882
llvm::computeOverflowForUnsignedAdd
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4900
ValueTracking.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::InstCombinerImpl::computeKnownBits
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:475
llvm::InstCombinerImpl::InstCombinerImpl
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)
Definition: InstCombineInternal.h:65
llvm::InstCombinerImpl::replaceInstUsesWith
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombineInternal.h:405
llvm::Optional
Definition: APInt.h:33
llvm::FenceInst
An instruction for ordering other memory operations.
Definition: Instructions.h:432
llvm::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return the number of times the sign bit of the register is replicated into the other bits.
Definition: ValueTracking.cpp:415
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::UnaryOperator
Definition: InstrTypes.h:101
llvm::SystemZII::IsLogical
@ IsLogical
Definition: SystemZInstrInfo.h:49
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:698
llvm::EmitGEPOffset
Value * EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
Definition: Local.h:29
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
KnownBits.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::InstCombinerImpl::eraseInstFromFunction
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Definition: InstCombineInternal.h:453
llvm::BitmaskEnumDetail::Mask
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:5015
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::AddrSpaceCastInst
This class represents a conversion between pointers from one address space to another.
Definition: Instructions.h:5252
llvm::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Definition: ValueTracking.cpp:5421
llvm::AAResults
Definition: AliasAnalysis.h:511
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::FCmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1347
InstructionWorklist.h
llvm::InsertElementInst
This instruction inserts a single (scalar) element into a VectorType value.
Definition: Instructions.h:1923
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:800
llvm::Instruction
Definition: Instruction.h:42
llvm::InstCombinerImpl::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:496
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
PatternMatch.h
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:441
llvm::Type::getInt1PtrTy
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:287
NegatorDefaultMaxDepth
static constexpr unsigned NegatorDefaultMaxDepth
Definition: InstCombineInternal.h:39
llvm::InstCombinerImpl::computeOverflowForSignedMul
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:502
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:1136
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:508
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3763
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:297
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1173
llvm::FPToSIInst
This class represents a cast from floating point to signed integer.
Definition: Instructions.h:5079
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4767
llvm::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4976
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:3972
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:68
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:916
llvm::InstCombinerImpl::replaceUse
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombineInternal.h:433
llvm::InstCombinerImpl::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:514
llvm::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Definition: ValueTracking.cpp:222
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1724
llvm::FPToUIInst
This class represents a cast from floating point to unsigned integer.
Definition: Instructions.h:5040
llvm::GEPOperator
Definition: Operator.h:375
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4806
NegatorMaxNodesSSO
static constexpr unsigned NegatorMaxNodesSSO
Definition: InstCombineInternal.h:43
llvm::InstCombinerImpl::visitInstruction
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
Definition: InstCombineInternal.h:180
llvm::Negator
Definition: InstCombineInternal.h:766
llvm::LoopInfo
Definition: LoopInfo.h:1102
llvm::VAEndInst
This represents the llvm.va_end intrinsic.
Definition: IntrinsicInst.h:1208
llvm::BinaryOperator
Definition: InstrTypes.h:188
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::InstCombinerImpl::ComputeNumSignBits
unsigned ComputeNumSignBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombineInternal.h:491
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:137
InstVisitor.h
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:991
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:82
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::PtrToIntInst
This class represents a cast from a pointer to an integer.
Definition: Instructions.h:5161
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:125
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:78
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:429
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:429
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4845
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:173
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:714
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:164
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:872
llvm::KnownBits
Definition: KnownBits.h:23
llvm::InstCombinerImpl::InsertNewInstWith
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
Definition: InstCombineInternal.h:394
llvm::AnyMemSetInst
This class represents any memset intrinsic.
Definition: IntrinsicInst.h:1116
llvm::InstCombinerImpl::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:526
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2398
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:155
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::InstCombinerImpl::CreateNonTerminatorUnreachable
void CreateNonTerminatorUnreachable(Instruction *InsertAt)
Create and insert the idiom we use to indicate a block is unreachable without having to rewrite the C...
Definition: InstCombineInternal.h:440
llvm::salvageDebugInfo
void salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1739
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:222
llvm::InstructionWorklist
InstructionWorklist - This is the worklist management logic for InstCombine and other simplification ...
Definition: InstructionWorklist.h:25
llvm::computeOverflowForSignedMul
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT, bool UseInstrInfo=true)
Definition: ValueTracking.cpp:4858
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::IntToPtrInst
This class represents a cast from an integer to a pointer.
Definition: Instructions.h:5118
llvm::InstCombiner
The core instruction combiner logic.
Definition: InstCombiner.h:45
llvm::IntrinsicInst
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:46
AA
llvm::InstCombinerImpl::replaceOperand
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
Definition: InstCombineInternal.h:426
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:786
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:1995
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:367
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5394
llvm::FPTruncInst
This class represents a truncation of floating point types.
Definition: Instructions.h:4884
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
InstructionSimplify.h
llvm::InstCombinerImpl::computeOverflowForUnsignedAdd
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:508
llvm::InstCombinerImpl::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:520
llvm::PHINode
Definition: Instructions.h:2651
llvm::PatternMatch
Definition: PatternMatch.h:47
IV
static const uint32_t IV[8]
Definition: blake3_impl.h:85
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:171
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4727
llvm::isKnownToBeAPowerOfTwo
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
Definition: ValueTracking.cpp:327
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3230
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3086
llvm::CodeGenOpt::Less
@ Less
Definition: CodeGen.h:54
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2509
foldICmpWithDominatingICmp
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
Definition: CodeGenPrepare.cpp:1666
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::InstCombinerImpl::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombineInternal.h:486
llvm::InstCombinerImpl::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:470
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
llvm::PoisonValue::get
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Definition: Constants.cpp:1774