LLVM  16.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, Value *FreedOp);
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 *simplifyBinOpSplats(ShuffleVectorInst &SVI);
171  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
172  Instruction *visitExtractValueInst(ExtractValueInst &EV);
173  Instruction *visitLandingPadInst(LandingPadInst &LI);
174  Instruction *visitVAEndInst(VAEndInst &I);
175  Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
176  bool freezeOtherUses(FreezeInst &FI);
177  Instruction *foldFreezeIntoRecurrence(FreezeInst &I, PHINode *PN);
178  Instruction *visitFreeze(FreezeInst &I);
179 
180  /// Specify what to return for unhandled instructions.
181  Instruction *visitInstruction(Instruction &I) { return nullptr; }
182 
183  /// True when DB dominates all uses of DI except UI.
184  /// UI must be in the same block as DI.
185  /// The routine checks that the DI parent and DB are different.
186  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
187  const BasicBlock *DB) const;
188 
189  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
190  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
191  const unsigned SIOpd);
192 
193  LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
194  const Twine &Suffix = "");
195 
196 private:
197  bool annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
198  bool isDesirableIntType(unsigned BitWidth) const;
199  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
200  bool shouldChangeType(Type *From, Type *To) const;
201  Value *dyn_castNegVal(Value *V) const;
202 
203  /// Classify whether a cast is worth optimizing.
204  ///
205  /// This is a helper to decide whether the simplification of
206  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
207  ///
208  /// \param CI The cast we are interested in.
209  ///
210  /// \return true if this cast actually results in any code being generated and
211  /// if it cannot already be eliminated by some other transformation.
212  bool shouldOptimizeCast(CastInst *CI);
213 
214  /// Try to optimize a sequence of instructions checking if an operation
215  /// on LHS and RHS overflows.
216  ///
217  /// If this overflow check is done via one of the overflow check intrinsics,
218  /// then CtxI has to be the call instruction calling that intrinsic. If this
219  /// overflow check is done by arithmetic followed by a compare, then CtxI has
220  /// to be the arithmetic instruction.
221  ///
222  /// If a simplification is possible, stores the simplified result of the
223  /// operation in OperationResult and result of the overflow check in
224  /// OverflowResult, and return true. If no simplification is possible,
225  /// returns false.
226  bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
227  Value *LHS, Value *RHS,
228  Instruction &CtxI, Value *&OperationResult,
230 
231  Instruction *visitCallBase(CallBase &Call);
232  Instruction *tryOptimizeCall(CallInst *CI);
233  bool transformConstExprCastCall(CallBase &Call);
234  Instruction *transformCallThroughTrampoline(CallBase &Call,
235  IntrinsicInst &Tramp);
236 
237  Value *simplifyMaskedLoad(IntrinsicInst &II);
238  Instruction *simplifyMaskedStore(IntrinsicInst &II);
239  Instruction *simplifyMaskedGather(IntrinsicInst &II);
240  Instruction *simplifyMaskedScatter(IntrinsicInst &II);
241 
242  /// Transform (zext icmp) to bitwise / integer operations in order to
243  /// eliminate it.
244  ///
245  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
246  /// \parem CI The zext of the (zext icmp) pair we are interested in.
247  ///
248  /// \return null if the transformation cannot be performed. If the
249  /// transformation can be performed the new instruction that replaces the
250  /// (zext icmp) pair will be returned.
251  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI);
252 
253  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
254 
255  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
256  const Instruction &CxtI) const {
257  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
259  }
260 
261  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
262  const Instruction &CxtI) const {
263  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
265  }
266 
267  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
268  const Instruction &CxtI, bool IsSigned) const {
269  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
270  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
271  }
272 
273  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
274  const Instruction &CxtI) const {
275  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
277  }
278 
279  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
280  const Instruction &CxtI) const {
281  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
283  }
284 
285  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
286  const Instruction &CxtI, bool IsSigned) const {
287  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
288  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
289  }
290 
291  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
292  const Instruction &CxtI) const {
293  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
295  }
296 
297  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
298  const Instruction &CxtI) const {
299  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
301  }
302 
303  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
304  const Instruction &CxtI, bool IsSigned) const {
305  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
306  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
307  }
308 
310  const Value *RHS, const Instruction &CxtI,
311  bool IsSigned) const {
312  switch (Opcode) {
313  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
314  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
315  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
316  default: llvm_unreachable("Unexpected opcode for overflow query");
317  }
318  }
319 
320  Value *EmitGEPOffset(User *GEP);
321  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
322  Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
323  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
324  Instruction *foldBinopOfSextBoolToSelect(BinaryOperator &I);
325  Instruction *narrowBinOp(TruncInst &Trunc);
326  Instruction *narrowMaskedBinOp(BinaryOperator &And);
327  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
328  Instruction *narrowFunnelShift(TruncInst &Trunc);
329  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
330  Instruction *matchSAddSubSat(IntrinsicInst &MinMax1);
331  Instruction *foldNot(BinaryOperator &I);
332 
333  void freelyInvertAllUsersOf(Value *V);
334 
335  /// Determine if a pair of casts can be replaced by a single cast.
336  ///
337  /// \param CI1 The first of a pair of casts.
338  /// \param CI2 The second of a pair of casts.
339  ///
340  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
341  /// Instruction::CastOps value for a cast that can replace the pair, casting
342  /// CI1->getSrcTy() to CI2->getDstTy().
343  ///
344  /// \see CastInst::isEliminableCastPair
345  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
346  const CastInst *CI2);
347  Value *simplifyIntToPtrRoundTripCast(Value *Val);
348 
349  Value *foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, Instruction &I,
350  bool IsAnd, bool IsLogical = false);
351  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
352 
353  Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
354 
355  Value *foldAndOrOfICmpsUsingRanges(ICmpInst *ICmp1, ICmpInst *ICmp2,
356  bool IsAnd);
357 
358  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
359  /// NOTE: Unlike most of instcombine, this returns a Value which should
360  /// already be inserted into the function.
361  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd,
362  bool IsLogicalSelect = false);
363 
364  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
365  Instruction *CxtI, bool IsAnd,
366  bool IsLogical = false);
367  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
368  Value *getSelectCondition(Value *A, Value *B);
369 
370  Instruction *foldExtractOfOverflowIntrinsic(ExtractValueInst &EV);
371  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
372  Instruction *foldFPSignBitOps(BinaryOperator &I);
373  Instruction *foldFDivConstantDivisor(BinaryOperator &I);
374 
375  // Optimize one of these forms:
376  // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
377  // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
378  // into simplier select instruction using isImpliedCondition.
379  Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
380  bool IsAnd);
381 
382 public:
383  /// Inserts an instruction \p New before instruction \p Old
384  ///
385  /// Also adds the new instruction to the worklist and returns \p New so that
386  /// it is suitable for use as the return from the visitation patterns.
388  assert(New && !New->getParent() &&
389  "New instruction already inserted into a basic block!");
390  BasicBlock *BB = Old.getParent();
391  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
392  Worklist.add(New);
393  return New;
394  }
395 
396  /// Same as InsertNewInstBefore, but also sets the debug loc.
398  New->setDebugLoc(Old.getDebugLoc());
399  return InsertNewInstBefore(New, Old);
400  }
401 
402  /// A combiner-aware RAUW-like routine.
403  ///
404  /// This method is to be used when an instruction is found to be dead,
405  /// replaceable with another preexisting expression. Here we add all uses of
406  /// I to the worklist, replace all uses of I with the new value, then return
407  /// I, so that the inst combiner will know that I was modified.
409  // If there are no uses to replace, then we return nullptr to indicate that
410  // no changes were made to the program.
411  if (I.use_empty()) return nullptr;
412 
413  Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
414 
415  // If we are replacing the instruction with itself, this must be in a
416  // segment of unreachable code, so just clobber the instruction.
417  if (&I == V)
418  V = PoisonValue::get(I.getType());
419 
420  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
421  << " with " << *V << '\n');
422 
423  I.replaceAllUsesWith(V);
424  MadeIRChange = true;
425  return &I;
426  }
427 
428  /// Replace operand of instruction and add old operand to the worklist.
429  Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
430  Worklist.addValue(I.getOperand(OpNum));
431  I.setOperand(OpNum, V);
432  return &I;
433  }
434 
435  /// Replace use and add the previously used value to the worklist.
436  void replaceUse(Use &U, Value *NewValue) {
437  Worklist.addValue(U);
438  U = NewValue;
439  }
440 
441  /// Create and insert the idiom we use to indicate a block is unreachable
442  /// without having to rewrite the CFG from within InstCombine.
444  auto &Ctx = InsertAt->getContext();
447  InsertAt);
448  }
449 
450 
451  /// Combiner aware instruction erasure.
452  ///
453  /// When dealing with an instruction that has side effects or produces a void
454  /// value, we can't rely on DCE to delete the instruction. Instead, visit
455  /// methods should return the value returned by this function.
457  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
458  assert(I.use_empty() && "Cannot erase instruction that is used!");
460 
461  // Make sure that we reprocess all operands now that we reduced their
462  // use counts.
463  for (Use &Operand : I.operands())
464  if (auto *Inst = dyn_cast<Instruction>(Operand))
465  Worklist.add(Inst);
466 
467  Worklist.remove(&I);
468  I.eraseFromParent();
469  MadeIRChange = true;
470  return nullptr; // Don't do anything with FI
471  }
472 
473  void computeKnownBits(const Value *V, KnownBits &Known,
474  unsigned Depth, const Instruction *CxtI) const {
475  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
476  }
477 
478  KnownBits computeKnownBits(const Value *V, unsigned Depth,
479  const Instruction *CxtI) const {
480  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
481  }
482 
483  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
484  unsigned Depth = 0,
485  const Instruction *CxtI = nullptr) {
486  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
487  }
488 
489  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
490  const Instruction *CxtI = nullptr) const {
491  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
492  }
493 
494  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
495  const Instruction *CxtI = nullptr) const {
496  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
497  }
498 
500  const Value *RHS,
501  const Instruction *CxtI) const {
502  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
503  }
504 
506  const Value *RHS,
507  const Instruction *CxtI) const {
508  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
509  }
510 
512  const Value *RHS,
513  const Instruction *CxtI) const {
514  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
515  }
516 
518  const Value *RHS,
519  const Instruction *CxtI) const {
520  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
521  }
522 
524  const Value *RHS,
525  const Instruction *CxtI) const {
526  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
527  }
528 
530  const Instruction *CxtI) const {
531  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
532  }
533 
534  OverflowResult computeOverflow(
535  Instruction::BinaryOps BinaryOp, bool IsSigned,
536  Value *LHS, Value *RHS, Instruction *CxtI) const;
537 
538  /// Performs a few simplifications for operators which are associative
539  /// or commutative.
540  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
541 
542  /// Tries to simplify binary operations which some other binary
543  /// operation distributes over.
544  ///
545  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
546  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
547  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
548  /// value, or null if it didn't simplify.
549  Value *foldUsingDistributiveLaws(BinaryOperator &I);
550 
551  /// Tries to simplify add operations using the definition of remainder.
552  ///
553  /// The definition of remainder is X % C = X - (X / C ) * C. The add
554  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
555  /// X % (C0 * C1)
556  Value *SimplifyAddWithRemainder(BinaryOperator &I);
557 
558  // Binary Op helper for select operations where the expression can be
559  // efficiently reorganized.
560  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
561  Value *RHS);
562 
563  /// This tries to simplify binary operations by factorizing out common terms
564  /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
565  Value *tryFactorizationFolds(BinaryOperator &I);
566 
567  /// Match a select chain which produces one of three values based on whether
568  /// the LHS is less than, equal to, or greater than RHS respectively.
569  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
570  /// Equal and Greater values are saved in the matching process and returned to
571  /// the caller.
572  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
574  ConstantInt *&Greater);
575 
576  /// Attempts to replace V with a simpler value based on the demanded
577  /// bits.
578  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
579  unsigned Depth, Instruction *CxtI);
580  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
581  const APInt &DemandedMask, KnownBits &Known,
582  unsigned Depth = 0) override;
583 
584  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
585  /// bits. It also tries to handle simplifications that can be done based on
586  /// DemandedMask, but without modifying the Instruction.
587  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
588  const APInt &DemandedMask,
589  KnownBits &Known,
590  unsigned Depth, Instruction *CxtI);
591 
592  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
593  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
594  Value *simplifyShrShlDemandedBits(
595  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
596  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
597 
598  /// Tries to simplify operands to an integer instruction based on its
599  /// demanded bits.
600  bool SimplifyDemandedInstructionBits(Instruction &Inst);
601 
602  Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
603  APInt &UndefElts, unsigned Depth = 0,
604  bool AllowMultipleUsers = false) override;
605 
606  /// Canonicalize the position of binops relative to shufflevector.
607  Instruction *foldVectorBinop(BinaryOperator &Inst);
608  Instruction *foldVectorSelect(SelectInst &Sel);
609  Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf);
610 
611  /// Given a binary operator, cast instruction, or select which has a PHI node
612  /// as operand #0, see if we can fold the instruction into the PHI (which is
613  /// only possible if all operands to the PHI are constants).
614  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
615 
616  /// For a binary operator with 2 phi operands, try to hoist the binary
617  /// operation before the phi. This can result in fewer instructions in
618  /// patterns where at least one set of phi operands simplifies.
619  /// Example:
620  /// BB3: binop (phi [X, BB1], [C1, BB2]), (phi [Y, BB1], [C2, BB2])
621  /// -->
622  /// BB1: BO = binop X, Y
623  /// BB3: phi [BO, BB1], [(binop C1, C2), BB2]
624  Instruction *foldBinopWithPhiOperands(BinaryOperator &BO);
625 
626  /// Given an instruction with a select as one operand and a constant as the
627  /// other operand, try to fold the binary operator into the select arguments.
628  /// This also works for Cast instructions, which obviously do not have a
629  /// second operand.
630  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
631  bool FoldWithMultiUse = false);
632 
633  /// This is a convenience wrapper function for the above two functions.
634  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
635 
636  Instruction *foldAddWithConstant(BinaryOperator &Add);
637 
638  /// Try to rotate an operation below a PHI node, using PHI nodes for
639  /// its operands.
640  Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
641  Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
642  Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
643  Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
644  Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
645  Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
646  Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
647  Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
648 
649  /// If an integer typed PHI has only one use which is an IntToPtr operation,
650  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
651  /// insert a new pointer typed PHI and replace the original one.
652  bool foldIntegerTypedPHI(PHINode &PN);
653 
654  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
655  /// folded operation.
656  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
657 
658  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
660  Instruction *foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI,
661  Value *RHS, const ICmpInst &I);
662  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca);
663  Instruction *foldCmpLoadFromIndexedGlobal(LoadInst *LI,
665  GlobalVariable *GV, CmpInst &ICI,
666  ConstantInt *AndCst = nullptr);
667  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
668  Constant *RHSC);
669  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
670  ICmpInst::Predicate Pred);
671  Instruction *foldICmpWithCastOp(ICmpInst &ICmp);
672  Instruction *foldICmpWithZextOrSext(ICmpInst &ICmp);
673 
674  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
676  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
677  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
678  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
679  Instruction *foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp,
680  const APInt &C);
681  Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
682  Instruction *foldICmpEquality(ICmpInst &Cmp);
683  Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
684  Instruction *foldSignBitTest(ICmpInst &I);
685  Instruction *foldICmpWithZero(ICmpInst &Cmp);
686 
687  Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
688 
689  Instruction *foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO,
690  const APInt &C);
691  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
692  ConstantInt *C);
693  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
694  const APInt &C);
695  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
696  const APInt &C);
697  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
698  const APInt &C);
699  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
700  const APInt &C);
701  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
702  const APInt &C);
703  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
704  const APInt &C);
705  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
706  const APInt &C);
707  Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
708  const APInt &C);
709  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
710  const APInt &C);
711  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
712  const APInt &C);
713  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
714  const APInt &C);
715  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
716  const APInt &C);
717  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
718  const APInt &C1);
719  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
720  const APInt &C1, const APInt &C2);
721  Instruction *foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor,
722  const APInt &C);
723  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
724  const APInt &C2);
725  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
726  const APInt &C2);
727 
728  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
729  BinaryOperator *BO,
730  const APInt &C);
731  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
732  const APInt &C);
733  Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
734  const APInt &C);
735  Instruction *foldICmpBitCast(ICmpInst &Cmp);
736 
737  // Helpers of visitSelectInst().
738  Instruction *foldSelectOfBools(SelectInst &SI);
739  Instruction *foldSelectExtConst(SelectInst &Sel);
740  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
741  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
742  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
743  Value *A, Value *B, Instruction &Outer,
744  SelectPatternFlavor SPF2, Value *C);
745  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
746  Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
747 
748  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
749  bool isSigned, bool Inside);
750  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
751  bool mergeStoreIntoSuccessor(StoreInst &SI);
752 
753  /// Given an initial instruction, check to see if it is the root of a
754  /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
755  /// intrinsic.
756  Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
757  bool MatchBitReversals);
758 
759  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
760  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
761 
762  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
763 
764  /// Returns a value X such that Val = X * Scale, or null if none.
765  ///
766  /// If the multiplication is known not to overflow then NoSignedWrap is set.
767  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
768 };
769 
770 class Negator final {
771  /// Top-to-bottom, def-to-use negated instruction tree we produced.
773 
776 
777  const DataLayout &DL;
778  AssumptionCache &AC;
779  const DominatorTree &DT;
780 
781  const bool IsTrulyNegation;
782 
783  SmallDenseMap<Value *, Value *> NegationsCache;
784 
786  const DominatorTree &DT, bool IsTrulyNegation);
787 
788 #if LLVM_ENABLE_STATS
789  unsigned NumValuesVisitedInThisNegator = 0;
790  ~Negator();
791 #endif
792 
793  using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
794  Value * /*NegatedRoot*/>;
795 
796  std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
797 
798  [[nodiscard]] Value *visitImpl(Value *V, unsigned Depth);
799 
800  [[nodiscard]] Value *negate(Value *V, unsigned Depth);
801 
802  /// Recurse depth-first and attempt to sink the negation.
803  /// FIXME: use worklist?
804  [[nodiscard]] Optional<Result> run(Value *Root);
805 
806  Negator(const Negator &) = delete;
807  Negator(Negator &&) = delete;
808  Negator &operator=(const Negator &) = delete;
809  Negator &operator=(Negator &&) = delete;
810 
811 public:
812  /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
813  /// otherwise returns negated value.
814  [[nodiscard]] static Value *Negate(bool LHSIsZero, Value *Root,
815  InstCombinerImpl &IC);
816 };
817 
818 } // end namespace llvm
819 
820 #undef DEBUG_TYPE
821 
822 #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:483
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:109
llvm::object::Equal
@ Equal
Definition: COFFModuleDefinition.cpp:36
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:3050
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:366
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:4893
llvm::SimplifyQuery
Definition: InstructionSimplify.h:93
llvm::ExtractElementInst
This instruction extracts a single (scalar) element from a VectorType value.
Definition: Instructions.h:1870
TargetFolder.h
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5253
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:1199
llvm::InstCombinerImpl::InsertNewInstBefore
Instruction * InsertNewInstBefore(Instruction *New, Instruction &Old)
Inserts an instruction New before instruction Old.
Definition: InstCombineInternal.h:387
Statistic.h
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2949
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::GlobalVariable
Definition: GlobalVariable.h:39
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:4949
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:478
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:408
llvm::Optional
Definition: APInt.h:33
llvm::FenceInst
An instruction for ordering other memory operations.
Definition: Instructions.h:433
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:385
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::UnaryOperator
Definition: InstrTypes.h:101
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:687
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::AArch64PACKey::DB
@ DB
Definition: AArch64BaseInfo.h:822
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:456
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:5064
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:5293
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:5487
llvm::AAResults
Definition: AliasAnalysis.h:294
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:1360
InstructionWorklist.h
SI
@ SI
Definition: SIInstrInfo.cpp:7966
llvm::InsertElementInst
This instruction inserts a single (scalar) element into a VectorType value.
Definition: Instructions.h:1934
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:807
llvm::Instruction
Definition: Instruction.h:42
llvm::InstCombinerImpl::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:499
llvm::salvageDebugInfo
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Definition: Utils.cpp:1361
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
PatternMatch.h
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:439
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:505
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:1222
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:501
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:40
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3809
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:298
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
llvm::SystemZII::IsLogical
@ IsLogical
Definition: SystemZInstrInfo.h:49
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1186
llvm::FPToSIInst
This class represents a cast from floating point to signed integer.
Definition: Instructions.h:5120
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:4808
llvm::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:5025
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:4018
llvm::LLVMContext
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
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:929
llvm::InstCombinerImpl::replaceUse
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombineInternal.h:436
llvm::InstCombinerImpl::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:517
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:197
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1735
llvm::FPToUIInst
This class represents a cast from floating point to unsigned integer.
Definition: Instructions.h:5081
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:4847
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:181
llvm::Negator
Definition: InstCombineInternal.h:770
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::VAEndInst
This represents the llvm.va_end intrinsic.
Definition: IntrinsicInst.h:1294
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:494
Mul
BinaryOperator * Mul
Definition: X86PartialReduction.cpp:70
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:138
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:994
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:5202
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:126
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:432
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4886
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:715
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:81
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:827
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:397
llvm::AnyMemSetInst
This class represents any memset intrinsic.
Definition: IntrinsicInst.h:1202
llvm::InstCombinerImpl::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:529
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:351
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2444
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
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:443
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
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:4907
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:185
llvm::IntToPtrInst
This class represents a cast from an integer to a pointer.
Definition: Instructions.h:5159
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:47
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:429
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:793
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2006
isSigned
static bool isSigned(unsigned int Opcode)
Definition: ExpandLargeDivRem.cpp:52
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:359
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5435
llvm::FPTruncInst
This class represents a truncation of floating point types.
Definition: Instructions.h:4925
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:511
llvm::InstCombinerImpl::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:523
llvm::PHINode
Definition: Instructions.h:2697
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:1474
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:4768
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:302
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3276
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:59
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3132
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:2555
foldICmpWithDominatingICmp
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
Definition: CodeGenPrepare.cpp:1760
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:489
llvm::InstCombinerImpl::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:473
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:1732