LLVM  13.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/Support/Debug.h"
26 #include "llvm/Support/KnownBits.h"
30 #include <cassert>
31 
32 #define DEBUG_TYPE "instcombine"
33 
34 using namespace llvm::PatternMatch;
35 
36 // As a default, let's assume that we want to be aggressive,
37 // and attempt to traverse with no limits in attempt to sink negation.
38 static constexpr unsigned NegatorDefaultMaxDepth = ~0U;
39 
40 // Let's guesstimate that most often we will end up visiting/producing
41 // fairly small number of new instructions.
42 static constexpr unsigned NegatorMaxNodesSSO = 16;
43 
44 namespace llvm {
45 
46 class AAResults;
47 class APInt;
48 class AssumptionCache;
49 class BlockFrequencyInfo;
50 class DataLayout;
51 class DominatorTree;
52 class GEPOperator;
53 class GlobalVariable;
54 class LoopInfo;
55 class OptimizationRemarkEmitter;
56 class ProfileSummaryInfo;
57 class TargetLibraryInfo;
58 class User;
59 
61  : public InstCombiner,
62  public InstVisitor<InstCombinerImpl, Instruction *> {
63 public:
65  bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
69  const DataLayout &DL, LoopInfo *LI)
70  : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
71  BFI, PSI, DL, LI) {}
72 
73  virtual ~InstCombinerImpl() {}
74 
75  /// Run the combiner over the entire worklist until it is empty.
76  ///
77  /// \returns true if the IR is changed.
78  bool run();
79 
80  // Visitation implementation - Implement instruction combining for different
81  // instruction types. The semantics are as follows:
82  // Return Value:
83  // null - No change was made
84  // I - Change was made, I is still valid, I may be dead though
85  // otherwise - Change was made, replace I with returned instruction
86  //
87  Instruction *visitFNeg(UnaryOperator &I);
88  Instruction *visitAdd(BinaryOperator &I);
89  Instruction *visitFAdd(BinaryOperator &I);
90  Value *OptimizePointerDifference(
91  Value *LHS, Value *RHS, Type *Ty, bool isNUW);
92  Instruction *visitSub(BinaryOperator &I);
93  Instruction *visitFSub(BinaryOperator &I);
94  Instruction *visitMul(BinaryOperator &I);
95  Instruction *visitFMul(BinaryOperator &I);
96  Instruction *visitURem(BinaryOperator &I);
97  Instruction *visitSRem(BinaryOperator &I);
98  Instruction *visitFRem(BinaryOperator &I);
99  bool simplifyDivRemOfSelectWithZeroOp(BinaryOperator &I);
100  Instruction *commonIRemTransforms(BinaryOperator &I);
101  Instruction *commonIDivTransforms(BinaryOperator &I);
102  Instruction *visitUDiv(BinaryOperator &I);
103  Instruction *visitSDiv(BinaryOperator &I);
104  Instruction *visitFDiv(BinaryOperator &I);
105  Value *simplifyRangeCheck(ICmpInst *Cmp0, ICmpInst *Cmp1, bool Inverted);
106  Instruction *visitAnd(BinaryOperator &I);
107  Instruction *visitOr(BinaryOperator &I);
108  bool sinkNotIntoOtherHandOfAndOrOr(BinaryOperator &I);
109  Instruction *visitXor(BinaryOperator &I);
110  Instruction *visitShl(BinaryOperator &I);
111  Value *reassociateShiftAmtsOfTwoSameDirectionShifts(
112  BinaryOperator *Sh0, const SimplifyQuery &SQ,
113  bool AnalyzeForSignBitExtraction = false);
114  Instruction *canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(
115  BinaryOperator &I);
116  Instruction *foldVariableSignZeroExtensionOfVariableHighBitExtract(
117  BinaryOperator &OldAShr);
118  Instruction *visitAShr(BinaryOperator &I);
119  Instruction *visitLShr(BinaryOperator &I);
120  Instruction *commonShiftTransforms(BinaryOperator &I);
121  Instruction *visitFCmpInst(FCmpInst &I);
122  CmpInst *canonicalizeICmpPredicate(CmpInst &I);
123  Instruction *visitICmpInst(ICmpInst &I);
124  Instruction *FoldShiftByConstant(Value *Op0, Constant *Op1,
125  BinaryOperator &I);
126  Instruction *commonCastTransforms(CastInst &CI);
127  Instruction *commonPointerCastTransforms(CastInst &CI);
128  Instruction *visitTrunc(TruncInst &CI);
129  Instruction *visitZExt(ZExtInst &CI);
130  Instruction *visitSExt(SExtInst &CI);
131  Instruction *visitFPTrunc(FPTruncInst &CI);
132  Instruction *visitFPExt(CastInst &CI);
133  Instruction *visitFPToUI(FPToUIInst &FI);
134  Instruction *visitFPToSI(FPToSIInst &FI);
135  Instruction *visitUIToFP(CastInst &CI);
136  Instruction *visitSIToFP(CastInst &CI);
137  Instruction *visitPtrToInt(PtrToIntInst &CI);
138  Instruction *visitIntToPtr(IntToPtrInst &CI);
139  Instruction *visitBitCast(BitCastInst &CI);
140  Instruction *visitAddrSpaceCast(AddrSpaceCastInst &CI);
141  Instruction *foldItoFPtoI(CastInst &FI);
142  Instruction *visitSelectInst(SelectInst &SI);
143  Instruction *visitCallInst(CallInst &CI);
144  Instruction *visitInvokeInst(InvokeInst &II);
145  Instruction *visitCallBrInst(CallBrInst &CBI);
146 
147  Instruction *SliceUpIllegalIntegerPHI(PHINode &PN);
148  Instruction *visitPHINode(PHINode &PN);
149  Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
150  Instruction *visitAllocaInst(AllocaInst &AI);
151  Instruction *visitAllocSite(Instruction &FI);
152  Instruction *visitFree(CallInst &FI);
153  Instruction *visitLoadInst(LoadInst &LI);
154  Instruction *visitStoreInst(StoreInst &SI);
155  Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
156  Instruction *visitUnconditionalBranchInst(BranchInst &BI);
157  Instruction *visitBranchInst(BranchInst &BI);
158  Instruction *visitFenceInst(FenceInst &FI);
159  Instruction *visitSwitchInst(SwitchInst &SI);
160  Instruction *visitReturnInst(ReturnInst &RI);
161  Instruction *visitUnreachableInst(UnreachableInst &I);
162  Instruction *
163  foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
164  Instruction *visitInsertValueInst(InsertValueInst &IV);
165  Instruction *visitInsertElementInst(InsertElementInst &IE);
166  Instruction *visitExtractElementInst(ExtractElementInst &EI);
167  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
168  Instruction *visitExtractValueInst(ExtractValueInst &EV);
169  Instruction *visitLandingPadInst(LandingPadInst &LI);
170  Instruction *visitVAEndInst(VAEndInst &I);
171  Instruction *visitFreeze(FreezeInst &I);
172 
173  /// Specify what to return for unhandled instructions.
174  Instruction *visitInstruction(Instruction &I) { return nullptr; }
175 
176  /// True when DB dominates all uses of DI except UI.
177  /// UI must be in the same block as DI.
178  /// The routine checks that the DI parent and DB are different.
179  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
180  const BasicBlock *DB) const;
181 
182  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
183  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
184  const unsigned SIOpd);
185 
186  LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
187  const Twine &Suffix = "");
188 
189 private:
190  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
191  bool shouldChangeType(Type *From, Type *To) const;
192  Value *dyn_castNegVal(Value *V) const;
193  Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
194  SmallVectorImpl<Value *> &NewIndices);
195 
196  /// Classify whether a cast is worth optimizing.
197  ///
198  /// This is a helper to decide whether the simplification of
199  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
200  ///
201  /// \param CI The cast we are interested in.
202  ///
203  /// \return true if this cast actually results in any code being generated and
204  /// if it cannot already be eliminated by some other transformation.
205  bool shouldOptimizeCast(CastInst *CI);
206 
207  /// Try to optimize a sequence of instructions checking if an operation
208  /// on LHS and RHS overflows.
209  ///
210  /// If this overflow check is done via one of the overflow check intrinsics,
211  /// then CtxI has to be the call instruction calling that intrinsic. If this
212  /// overflow check is done by arithmetic followed by a compare, then CtxI has
213  /// to be the arithmetic instruction.
214  ///
215  /// If a simplification is possible, stores the simplified result of the
216  /// operation in OperationResult and result of the overflow check in
217  /// OverflowResult, and return true. If no simplification is possible,
218  /// returns false.
219  bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
220  Value *LHS, Value *RHS,
221  Instruction &CtxI, Value *&OperationResult,
223 
224  Instruction *visitCallBase(CallBase &Call);
225  Instruction *tryOptimizeCall(CallInst *CI);
226  bool transformConstExprCastCall(CallBase &Call);
227  Instruction *transformCallThroughTrampoline(CallBase &Call,
228  IntrinsicInst &Tramp);
229 
230  Value *simplifyMaskedLoad(IntrinsicInst &II);
231  Instruction *simplifyMaskedStore(IntrinsicInst &II);
232  Instruction *simplifyMaskedGather(IntrinsicInst &II);
233  Instruction *simplifyMaskedScatter(IntrinsicInst &II);
234 
235  /// Transform (zext icmp) to bitwise / integer operations in order to
236  /// eliminate it.
237  ///
238  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
239  /// \parem CI The zext of the (zext icmp) pair we are interested in.
240  /// \param DoTransform Pass false to just test whether the given (zext icmp)
241  /// would be transformed. Pass true to actually perform the transformation.
242  ///
243  /// \return null if the transformation cannot be performed. If the
244  /// transformation can be performed the new instruction that replaces the
245  /// (zext icmp) pair will be returned (if \p DoTransform is false the
246  /// unmodified \p ICI will be returned in this case).
247  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI,
248  bool DoTransform = true);
249 
250  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
251 
252  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
253  const Instruction &CxtI) const {
254  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
256  }
257 
258  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
259  const Instruction &CxtI) const {
260  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
262  }
263 
264  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
265  const Instruction &CxtI, bool IsSigned) const {
266  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
267  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
268  }
269 
270  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
271  const Instruction &CxtI) const {
272  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
274  }
275 
276  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
277  const Instruction &CxtI) const {
278  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
280  }
281 
282  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
283  const Instruction &CxtI, bool IsSigned) const {
284  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
285  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
286  }
287 
288  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
289  const Instruction &CxtI) const {
290  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
292  }
293 
294  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
295  const Instruction &CxtI) const {
296  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
298  }
299 
300  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
301  const Instruction &CxtI, bool IsSigned) const {
302  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
303  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
304  }
305 
306  bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
307  const Value *RHS, const Instruction &CxtI,
308  bool IsSigned) const {
309  switch (Opcode) {
310  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
311  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
312  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
313  default: llvm_unreachable("Unexpected opcode for overflow query");
314  }
315  }
316 
317  Value *EmitGEPOffset(User *GEP);
318  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
319  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
320  Instruction *narrowBinOp(TruncInst &Trunc);
321  Instruction *narrowMaskedBinOp(BinaryOperator &And);
322  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
323  Instruction *narrowFunnelShift(TruncInst &Trunc);
324  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
325  Instruction *matchSAddSubSat(SelectInst &MinMax1);
326 
327  void freelyInvertAllUsersOf(Value *V);
328 
329  /// Determine if a pair of casts can be replaced by a single cast.
330  ///
331  /// \param CI1 The first of a pair of casts.
332  /// \param CI2 The second of a pair of casts.
333  ///
334  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
335  /// Instruction::CastOps value for a cast that can replace the pair, casting
336  /// CI1->getSrcTy() to CI2->getDstTy().
337  ///
338  /// \see CastInst::isEliminableCastPair
339  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
340  const CastInst *CI2);
341 
342  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &And);
343  Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Or);
344  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
345 
346  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
347  /// NOTE: Unlike most of instcombine, this returns a Value which should
348  /// already be inserted into the function.
349  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
350 
351  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
352  BinaryOperator &Logic);
353  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
354  Value *getSelectCondition(Value *A, Value *B);
355 
356  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
357  Instruction *foldFPSignBitOps(BinaryOperator &I);
358 
359 public:
360  /// Inserts an instruction \p New before instruction \p Old
361  ///
362  /// Also adds the new instruction to the worklist and returns \p New so that
363  /// it is suitable for use as the return from the visitation patterns.
365  assert(New && !New->getParent() &&
366  "New instruction already inserted into a basic block!");
367  BasicBlock *BB = Old.getParent();
368  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
369  Worklist.add(New);
370  return New;
371  }
372 
373  /// Same as InsertNewInstBefore, but also sets the debug loc.
375  New->setDebugLoc(Old.getDebugLoc());
376  return InsertNewInstBefore(New, Old);
377  }
378 
379  /// A combiner-aware RAUW-like routine.
380  ///
381  /// This method is to be used when an instruction is found to be dead,
382  /// replaceable with another preexisting expression. Here we add all uses of
383  /// I to the worklist, replace all uses of I with the new value, then return
384  /// I, so that the inst combiner will know that I was modified.
386  // If there are no uses to replace, then we return nullptr to indicate that
387  // no changes were made to the program.
388  if (I.use_empty()) return nullptr;
389 
390  Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
391 
392  // If we are replacing the instruction with itself, this must be in a
393  // segment of unreachable code, so just clobber the instruction.
394  if (&I == V)
395  V = UndefValue::get(I.getType());
396 
397  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
398  << " with " << *V << '\n');
399 
400  I.replaceAllUsesWith(V);
401  MadeIRChange = true;
402  return &I;
403  }
404 
405  /// Replace operand of instruction and add old operand to the worklist.
406  Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
407  Worklist.addValue(I.getOperand(OpNum));
408  I.setOperand(OpNum, V);
409  return &I;
410  }
411 
412  /// Replace use and add the previously used value to the worklist.
413  void replaceUse(Use &U, Value *NewValue) {
414  Worklist.addValue(U);
415  U = NewValue;
416  }
417 
418  /// Creates a result tuple for an overflow intrinsic \p II with a given
419  /// \p Result and a constant \p Overflow value.
421  Constant *Overflow) {
422  Constant *V[] = {UndefValue::get(Result->getType()), Overflow};
423  StructType *ST = cast<StructType>(II->getType());
424  Constant *Struct = ConstantStruct::get(ST, V);
425  return InsertValueInst::Create(Struct, Result, 0);
426  }
427 
428  /// Create and insert the idiom we use to indicate a block is unreachable
429  /// without having to rewrite the CFG from within InstCombine.
431  auto &Ctx = InsertAt->getContext();
434  InsertAt);
435  }
436 
437 
438  /// Combiner aware instruction erasure.
439  ///
440  /// When dealing with an instruction that has side effects or produces a void
441  /// value, we can't rely on DCE to delete the instruction. Instead, visit
442  /// methods should return the value returned by this function.
444  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
445  assert(I.use_empty() && "Cannot erase instruction that is used!");
447 
448  // Make sure that we reprocess all operands now that we reduced their
449  // use counts.
450  for (Use &Operand : I.operands())
451  if (auto *Inst = dyn_cast<Instruction>(Operand))
452  Worklist.add(Inst);
453 
454  Worklist.remove(&I);
455  I.eraseFromParent();
456  MadeIRChange = true;
457  return nullptr; // Don't do anything with FI
458  }
459 
460  void computeKnownBits(const Value *V, KnownBits &Known,
461  unsigned Depth, const Instruction *CxtI) const {
462  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
463  }
464 
465  KnownBits computeKnownBits(const Value *V, unsigned Depth,
466  const Instruction *CxtI) const {
467  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
468  }
469 
470  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
471  unsigned Depth = 0,
472  const Instruction *CxtI = nullptr) {
473  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
474  }
475 
476  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
477  const Instruction *CxtI = nullptr) const {
478  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
479  }
480 
481  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
482  const Instruction *CxtI = nullptr) const {
483  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
484  }
485 
487  const Value *RHS,
488  const Instruction *CxtI) const {
489  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
490  }
491 
493  const Value *RHS,
494  const Instruction *CxtI) const {
495  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
496  }
497 
499  const Value *RHS,
500  const Instruction *CxtI) const {
501  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
502  }
503 
505  const Value *RHS,
506  const Instruction *CxtI) const {
507  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
508  }
509 
511  const Value *RHS,
512  const Instruction *CxtI) const {
513  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
514  }
515 
517  const Instruction *CxtI) const {
518  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
519  }
520 
521  OverflowResult computeOverflow(
522  Instruction::BinaryOps BinaryOp, bool IsSigned,
523  Value *LHS, Value *RHS, Instruction *CxtI) const;
524 
525  /// Performs a few simplifications for operators which are associative
526  /// or commutative.
527  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
528 
529  /// Tries to simplify binary operations which some other binary
530  /// operation distributes over.
531  ///
532  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
533  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
534  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
535  /// value, or null if it didn't simplify.
536  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
537 
538  /// Tries to simplify add operations using the definition of remainder.
539  ///
540  /// The definition of remainder is X % C = X - (X / C ) * C. The add
541  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
542  /// X % (C0 * C1)
543  Value *SimplifyAddWithRemainder(BinaryOperator &I);
544 
545  // Binary Op helper for select operations where the expression can be
546  // efficiently reorganized.
547  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
548  Value *RHS);
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 *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
553  Value *, Value *, Value *);
554 
555  /// Match a select chain which produces one of three values based on whether
556  /// the LHS is less than, equal to, or greater than RHS respectively.
557  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
558  /// Equal and Greater values are saved in the matching process and returned to
559  /// the caller.
560  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
562  ConstantInt *&Greater);
563 
564  /// Attempts to replace V with a simpler value based on the demanded
565  /// bits.
566  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
567  unsigned Depth, Instruction *CxtI);
568  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
569  const APInt &DemandedMask, KnownBits &Known,
570  unsigned Depth = 0) override;
571 
572  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
573  /// bits. It also tries to handle simplifications that can be done based on
574  /// DemandedMask, but without modifying the Instruction.
575  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
576  const APInt &DemandedMask,
577  KnownBits &Known,
578  unsigned Depth, Instruction *CxtI);
579 
580  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
581  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
582  Value *simplifyShrShlDemandedBits(
583  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
584  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
585 
586  /// Tries to simplify operands to an integer instruction based on its
587  /// demanded bits.
588  bool SimplifyDemandedInstructionBits(Instruction &Inst);
589 
590  virtual Value *
591  SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
592  unsigned Depth = 0,
593  bool AllowMultipleUsers = false) override;
594 
595  /// Canonicalize the position of binops relative to shufflevector.
596  Instruction *foldVectorBinop(BinaryOperator &Inst);
597  Instruction *foldVectorSelect(SelectInst &Sel);
598 
599  /// Given a binary operator, cast instruction, or select which has a PHI node
600  /// as operand #0, see if we can fold the instruction into the PHI (which is
601  /// only possible if all operands to the PHI are constants).
602  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
603 
604  /// Given an instruction with a select as one operand and a constant as the
605  /// other operand, try to fold the binary operator into the select arguments.
606  /// This also works for Cast instructions, which obviously do not have a
607  /// second operand.
608  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
609 
610  /// This is a convenience wrapper function for the above two functions.
611  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
612 
613  Instruction *foldAddWithConstant(BinaryOperator &Add);
614 
615  /// Try to rotate an operation below a PHI node, using PHI nodes for
616  /// its operands.
617  Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
618  Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
619  Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
620  Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
621  Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
622  Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
623  Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
624 
625  /// If an integer typed PHI has only one use which is an IntToPtr operation,
626  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
627  /// insert a new pointer typed PHI and replace the original one.
628  Instruction *foldIntegerTypedPHI(PHINode &PN);
629 
630  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
631  /// folded operation.
632  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
633 
634  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
636  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
637  const Value *Other);
638  Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
639  GlobalVariable *GV, CmpInst &ICI,
640  ConstantInt *AndCst = nullptr);
641  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
642  Constant *RHSC);
643  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
644  ICmpInst::Predicate Pred);
645  Instruction *foldICmpWithCastOp(ICmpInst &ICI);
646 
647  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
649  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
650  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
651  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
652  Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
653  Instruction *foldICmpEquality(ICmpInst &Cmp);
654  Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
655  Instruction *foldSignBitTest(ICmpInst &I);
656  Instruction *foldICmpWithZero(ICmpInst &Cmp);
657 
658  Value *foldUnsignedMultiplicationOverflowCheck(ICmpInst &Cmp);
659 
660  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
661  ConstantInt *C);
662  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
663  const APInt &C);
664  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
665  const APInt &C);
666  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
667  const APInt &C);
668  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
669  const APInt &C);
670  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
671  const APInt &C);
672  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
673  const APInt &C);
674  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
675  const APInt &C);
676  Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
677  const APInt &C);
678  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
679  const APInt &C);
680  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
681  const APInt &C);
682  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
683  const APInt &C);
684  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
685  const APInt &C);
686  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
687  const APInt &C1);
688  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
689  const APInt &C1, const APInt &C2);
690  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
691  const APInt &C2);
692  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
693  const APInt &C2);
694 
695  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
696  BinaryOperator *BO,
697  const APInt &C);
698  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
699  const APInt &C);
700  Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
701  const APInt &C);
702 
703  // Helpers of visitSelectInst().
704  Instruction *foldSelectExtConst(SelectInst &Sel);
705  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
706  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
707  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
708  Value *A, Value *B, Instruction &Outer,
709  SelectPatternFlavor SPF2, Value *C);
710  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
711  Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
712 
713  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
714  bool isSigned, bool Inside);
715  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
716  bool mergeStoreIntoSuccessor(StoreInst &SI);
717 
718  /// Given an initial instruction, check to see if it is the root of a
719  /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
720  /// intrinsic.
721  Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
722  bool MatchBitReversals);
723 
724  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
725  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
726 
727  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
728 
729  /// Returns a value X such that Val = X * Scale, or null if none.
730  ///
731  /// If the multiplication is known not to overflow then NoSignedWrap is set.
732  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
733 };
734 
735 class Negator final {
736  /// Top-to-bottom, def-to-use negated instruction tree we produced.
738 
741 
742  const DataLayout &DL;
743  AssumptionCache &AC;
744  const DominatorTree &DT;
745 
746  const bool IsTrulyNegation;
747 
748  SmallDenseMap<Value *, Value *> NegationsCache;
749 
751  const DominatorTree &DT, bool IsTrulyNegation);
752 
753 #if LLVM_ENABLE_STATS
754  unsigned NumValuesVisitedInThisNegator = 0;
755  ~Negator();
756 #endif
757 
758  using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
759  Value * /*NegatedRoot*/>;
760 
761  std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
762 
763  LLVM_NODISCARD Value *visitImpl(Value *V, unsigned Depth);
764 
765  LLVM_NODISCARD Value *negate(Value *V, unsigned Depth);
766 
767  /// Recurse depth-first and attempt to sink the negation.
768  /// FIXME: use worklist?
770 
771  Negator(const Negator &) = delete;
772  Negator(Negator &&) = delete;
773  Negator &operator=(const Negator &) = delete;
774  Negator &operator=(Negator &&) = delete;
775 
776 public:
777  /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
778  /// otherwise returns negated value.
779  LLVM_NODISCARD static Value *Negate(bool LHSIsZero, Value *Root,
780  InstCombinerImpl &IC);
781 };
782 
783 } // end namespace llvm
784 
785 #undef DEBUG_TYPE
786 
787 #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:470
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:100
llvm::object::Equal
@ Equal
Definition: COFFModuleDefinition.cpp:38
llvm
Definition: AllocatorList.h:23
llvm::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2923
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:359
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
InstCombiner.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:722
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:4617
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::ExtractElementInst
This instruction extracts a single (scalar) element from a VectorType value.
Definition: Instructions.h:1850
TargetFolder.h
llvm::ConstantStruct::get
static Constant * get(StructType *T, ArrayRef< Constant * > V)
Definition: Constants.cpp:1312
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5136
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:1168
llvm::InstCombinerImpl::InsertNewInstBefore
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombineInternal.h:364
Statistic.h
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2822
llvm::MipsISD::Lo
@ Lo
Definition: MipsISelLowering.h:79
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::InsertValueInst::Create
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:2469
llvm::GlobalVariable
Definition: GlobalVariable.h:40
llvm::SmallDenseMap
Definition: DenseMap.h:880
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:4673
ValueTracking.h
Local.h
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::InstCombinerImpl::~InstCombinerImpl
virtual ~InstCombinerImpl()
Definition: InstCombineInternal.h:73
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:34
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
llvm::InstCombinerImpl::computeKnownBits
KnownBits computeKnownBits(const Value *V, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:465
llvm::InstCombinerImpl::replaceInstUsesWith
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
Definition: InstCombineInternal.h:385
llvm::Optional
Definition: APInt.h:34
llvm::FenceInst
An instruction for ordering other memory operations.
Definition: Instructions.h:444
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
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:383
llvm::UnaryOperator
Definition: InstrTypes.h:103
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:657
llvm::BitmaskEnumDetail::Mask
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
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:122
KnownBits.h
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::MipsISD::Hi
@ Hi
Definition: MipsISelLowering.h:75
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::InstCombinerImpl::eraseInstFromFunction
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Definition: InstCombineInternal.h:443
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:77
llvm::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4772
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:5176
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:5172
llvm::AAResults
Definition: AliasAnalysis.h:456
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::InstCombinerImpl::CreateOverflowTuple
Instruction * CreateOverflowTuple(IntrinsicInst *II, Value *Result, Constant *Overflow)
Creates a result tuple for an overflow intrinsic II with a given Result and a constant Overflow value...
Definition: InstCombineInternal.h:420
llvm::FCmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1344
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::InsertElementInst
This instruction inserts a single (scalar) element into a VectorType value.
Definition: Instructions.h:1914
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:782
llvm::Instruction
Definition: Instruction.h:45
llvm::InstCombinerImpl::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:486
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1770
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:60
InstCombineWorklist.h
llvm::InstCombineWorklist
InstCombineWorklist - This is the worklist management logic for InstCombine.
Definition: InstCombineWorklist.h:27
PatternMatch.h
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:391
llvm::Type::getInt1PtrTy
static PointerType * getInt1PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:252
NegatorDefaultMaxDepth
static constexpr unsigned NegatorDefaultMaxDepth
Definition: InstCombineInternal.h:38
llvm::InstCombinerImpl::computeOverflowForSignedMul
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:492
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::InstCombinerImpl::InstCombinerImpl
InstCombinerImpl(InstCombineWorklist &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:64
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:980
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:487
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3686
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:712
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
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:1178
llvm::FPToSIInst
This class represents a cast from floating point to signed integer.
Definition: Instructions.h:5003
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::ARM_MB::ST
@ ST
Definition: ARMBaseInfo.h:73
llvm::TruncInst
This class represents a truncation of integer types.
Definition: Instructions.h:4691
llvm::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4749
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:3895
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:59
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:905
llvm::InstCombinerImpl::replaceUse
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombineInternal.h:413
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:634
llvm::InstCombinerImpl::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:504
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:211
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1715
llvm::FPToUIInst
This class represents a cast from floating point to unsigned integer.
Definition: Instructions.h:4964
llvm::GEPOperator
Definition: Operator.h:457
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:649
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:71
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4730
NegatorMaxNodesSSO
static constexpr unsigned NegatorMaxNodesSSO
Definition: InstCombineInternal.h:42
llvm::InstCombinerImpl::visitInstruction
Instruction * visitInstruction(Instruction &I)
Specify what to return for unhandled instructions.
Definition: InstCombineInternal.h:174
llvm::Negator
Definition: InstCombineInternal.h:735
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::VAEndInst
This represents the llvm.va_end intrinsic.
Definition: IntrinsicInst.h:1052
llvm::BinaryOperator
Definition: InstrTypes.h:190
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:481
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:167
InstVisitor.h
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:940
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
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:5085
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:131
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:79
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:432
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:419
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4769
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:702
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:163
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
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:374
llvm::AnyMemSetInst
This class represents any memset intrinsic.
Definition: IntrinsicInst.h:961
llvm::InstCombinerImpl::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:516
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2318
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h:161
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:430
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:1799
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:207
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:4631
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:184
llvm::IntToPtrInst
This class represents a cast from an integer to a pointer.
Definition: Instructions.h:5042
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:45
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:406
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:768
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:1986
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:365
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5287
llvm::FPTruncInst
This class represents a truncation of floating point types.
Definition: Instructions.h:4808
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
InstructionSimplify.h
llvm::InstCombinerImpl::computeOverflowForUnsignedAdd
OverflowResult computeOverflowForUnsignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:498
llvm::InstCombinerImpl::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:510
llvm::PHINode
Definition: Instructions.h:2572
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::SmallVectorImpl< Value * >
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1164
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1450
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:4650
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:295
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3149
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:61
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3005
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:2429
foldICmpWithDominatingICmp
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
Definition: CodeGenPrepare.cpp:1651
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::InstCombinerImpl::MaskedValueIsZero
bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth=0, const Instruction *CxtI=nullptr) const
Definition: InstCombineInternal.h:476
llvm::InstCombinerImpl::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:460
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44