LLVM  14.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() {}
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 *visitAllocaInst(AllocaInst &AI);
152  Instruction *visitAllocSite(Instruction &FI);
153  Instruction *visitFree(CallInst &FI);
154  Instruction *visitLoadInst(LoadInst &LI);
155  Instruction *visitStoreInst(StoreInst &SI);
156  Instruction *visitAtomicRMWInst(AtomicRMWInst &SI);
157  Instruction *visitUnconditionalBranchInst(BranchInst &BI);
158  Instruction *visitBranchInst(BranchInst &BI);
159  Instruction *visitFenceInst(FenceInst &FI);
160  Instruction *visitSwitchInst(SwitchInst &SI);
161  Instruction *visitReturnInst(ReturnInst &RI);
162  Instruction *visitUnreachableInst(UnreachableInst &I);
163  Instruction *
164  foldAggregateConstructionIntoAggregateReuse(InsertValueInst &OrigIVI);
165  Instruction *visitInsertValueInst(InsertValueInst &IV);
166  Instruction *visitInsertElementInst(InsertElementInst &IE);
167  Instruction *visitExtractElementInst(ExtractElementInst &EI);
168  Instruction *visitShuffleVectorInst(ShuffleVectorInst &SVI);
169  Instruction *visitExtractValueInst(ExtractValueInst &EV);
170  Instruction *visitLandingPadInst(LandingPadInst &LI);
171  Instruction *visitVAEndInst(VAEndInst &I);
172  Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
173  bool freezeDominatedUses(FreezeInst &FI);
174  Instruction *visitFreeze(FreezeInst &I);
175 
176  /// Specify what to return for unhandled instructions.
177  Instruction *visitInstruction(Instruction &I) { return nullptr; }
178 
179  /// True when DB dominates all uses of DI except UI.
180  /// UI must be in the same block as DI.
181  /// The routine checks that the DI parent and DB are different.
182  bool dominatesAllUses(const Instruction *DI, const Instruction *UI,
183  const BasicBlock *DB) const;
184 
185  /// Try to replace select with select operand SIOpd in SI-ICmp sequence.
186  bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp,
187  const unsigned SIOpd);
188 
189  LoadInst *combineLoadToNewType(LoadInst &LI, Type *NewTy,
190  const Twine &Suffix = "");
191 
192 private:
193  void annotateAnyAllocSite(CallBase &Call, const TargetLibraryInfo *TLI);
194  bool isDesirableIntType(unsigned BitWidth) const;
195  bool shouldChangeType(unsigned FromBitWidth, unsigned ToBitWidth) const;
196  bool shouldChangeType(Type *From, Type *To) const;
197  Value *dyn_castNegVal(Value *V) const;
198  Type *FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
199  SmallVectorImpl<Value *> &NewIndices);
200 
201  /// Classify whether a cast is worth optimizing.
202  ///
203  /// This is a helper to decide whether the simplification of
204  /// logic(cast(A), cast(B)) to cast(logic(A, B)) should be performed.
205  ///
206  /// \param CI The cast we are interested in.
207  ///
208  /// \return true if this cast actually results in any code being generated and
209  /// if it cannot already be eliminated by some other transformation.
210  bool shouldOptimizeCast(CastInst *CI);
211 
212  /// Try to optimize a sequence of instructions checking if an operation
213  /// on LHS and RHS overflows.
214  ///
215  /// If this overflow check is done via one of the overflow check intrinsics,
216  /// then CtxI has to be the call instruction calling that intrinsic. If this
217  /// overflow check is done by arithmetic followed by a compare, then CtxI has
218  /// to be the arithmetic instruction.
219  ///
220  /// If a simplification is possible, stores the simplified result of the
221  /// operation in OperationResult and result of the overflow check in
222  /// OverflowResult, and return true. If no simplification is possible,
223  /// returns false.
224  bool OptimizeOverflowCheck(Instruction::BinaryOps BinaryOp, bool IsSigned,
225  Value *LHS, Value *RHS,
226  Instruction &CtxI, Value *&OperationResult,
228 
229  Instruction *visitCallBase(CallBase &Call);
230  Instruction *tryOptimizeCall(CallInst *CI);
231  bool transformConstExprCastCall(CallBase &Call);
232  Instruction *transformCallThroughTrampoline(CallBase &Call,
233  IntrinsicInst &Tramp);
234 
235  Value *simplifyMaskedLoad(IntrinsicInst &II);
236  Instruction *simplifyMaskedStore(IntrinsicInst &II);
237  Instruction *simplifyMaskedGather(IntrinsicInst &II);
238  Instruction *simplifyMaskedScatter(IntrinsicInst &II);
239 
240  /// Transform (zext icmp) to bitwise / integer operations in order to
241  /// eliminate it.
242  ///
243  /// \param ICI The icmp of the (zext icmp) pair we are interested in.
244  /// \parem CI The zext of the (zext icmp) pair we are interested in.
245  ///
246  /// \return null if the transformation cannot be performed. If the
247  /// transformation can be performed the new instruction that replaces the
248  /// (zext icmp) pair will be returned.
249  Instruction *transformZExtICmp(ICmpInst *ICI, ZExtInst &CI);
250 
251  Instruction *transformSExtICmp(ICmpInst *ICI, Instruction &CI);
252 
253  bool willNotOverflowSignedAdd(const Value *LHS, const Value *RHS,
254  const Instruction &CxtI) const {
255  return computeOverflowForSignedAdd(LHS, RHS, &CxtI) ==
257  }
258 
259  bool willNotOverflowUnsignedAdd(const Value *LHS, const Value *RHS,
260  const Instruction &CxtI) const {
261  return computeOverflowForUnsignedAdd(LHS, RHS, &CxtI) ==
263  }
264 
265  bool willNotOverflowAdd(const Value *LHS, const Value *RHS,
266  const Instruction &CxtI, bool IsSigned) const {
267  return IsSigned ? willNotOverflowSignedAdd(LHS, RHS, CxtI)
268  : willNotOverflowUnsignedAdd(LHS, RHS, CxtI);
269  }
270 
271  bool willNotOverflowSignedSub(const Value *LHS, const Value *RHS,
272  const Instruction &CxtI) const {
273  return computeOverflowForSignedSub(LHS, RHS, &CxtI) ==
275  }
276 
277  bool willNotOverflowUnsignedSub(const Value *LHS, const Value *RHS,
278  const Instruction &CxtI) const {
279  return computeOverflowForUnsignedSub(LHS, RHS, &CxtI) ==
281  }
282 
283  bool willNotOverflowSub(const Value *LHS, const Value *RHS,
284  const Instruction &CxtI, bool IsSigned) const {
285  return IsSigned ? willNotOverflowSignedSub(LHS, RHS, CxtI)
286  : willNotOverflowUnsignedSub(LHS, RHS, CxtI);
287  }
288 
289  bool willNotOverflowSignedMul(const Value *LHS, const Value *RHS,
290  const Instruction &CxtI) const {
291  return computeOverflowForSignedMul(LHS, RHS, &CxtI) ==
293  }
294 
295  bool willNotOverflowUnsignedMul(const Value *LHS, const Value *RHS,
296  const Instruction &CxtI) const {
297  return computeOverflowForUnsignedMul(LHS, RHS, &CxtI) ==
299  }
300 
301  bool willNotOverflowMul(const Value *LHS, const Value *RHS,
302  const Instruction &CxtI, bool IsSigned) const {
303  return IsSigned ? willNotOverflowSignedMul(LHS, RHS, CxtI)
304  : willNotOverflowUnsignedMul(LHS, RHS, CxtI);
305  }
306 
307  bool willNotOverflow(BinaryOperator::BinaryOps Opcode, const Value *LHS,
308  const Value *RHS, const Instruction &CxtI,
309  bool IsSigned) const {
310  switch (Opcode) {
311  case Instruction::Add: return willNotOverflowAdd(LHS, RHS, CxtI, IsSigned);
312  case Instruction::Sub: return willNotOverflowSub(LHS, RHS, CxtI, IsSigned);
313  case Instruction::Mul: return willNotOverflowMul(LHS, RHS, CxtI, IsSigned);
314  default: llvm_unreachable("Unexpected opcode for overflow query");
315  }
316  }
317 
318  Value *EmitGEPOffset(User *GEP);
319  Instruction *scalarizePHI(ExtractElementInst &EI, PHINode *PN);
320  Instruction *foldBitcastExtElt(ExtractElementInst &ExtElt);
321  Instruction *foldCastedBitwiseLogic(BinaryOperator &I);
322  Instruction *narrowBinOp(TruncInst &Trunc);
323  Instruction *narrowMaskedBinOp(BinaryOperator &And);
324  Instruction *narrowMathIfNoOverflow(BinaryOperator &I);
325  Instruction *narrowFunnelShift(TruncInst &Trunc);
326  Instruction *optimizeBitCastFromPhi(CastInst &CI, PHINode *PN);
327  Instruction *matchSAddSubSat(Instruction &MinMax1);
328  Instruction *foldNot(BinaryOperator &I);
329 
330  void freelyInvertAllUsersOf(Value *V);
331 
332  /// Determine if a pair of casts can be replaced by a single cast.
333  ///
334  /// \param CI1 The first of a pair of casts.
335  /// \param CI2 The second of a pair of casts.
336  ///
337  /// \return 0 if the cast pair cannot be eliminated, otherwise returns an
338  /// Instruction::CastOps value for a cast that can replace the pair, casting
339  /// CI1->getSrcTy() to CI2->getDstTy().
340  ///
341  /// \see CastInst::isEliminableCastPair
342  Instruction::CastOps isEliminableCastPair(const CastInst *CI1,
343  const CastInst *CI2);
344  Value *simplifyIntToPtrRoundTripCast(Value *Val);
345 
346  Value *foldAndOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &And);
347  Value *foldOrOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Or);
348  Value *foldXorOfICmps(ICmpInst *LHS, ICmpInst *RHS, BinaryOperator &Xor);
349 
350  Value *foldEqOfParts(ICmpInst *Cmp0, ICmpInst *Cmp1, bool IsAnd);
351 
352  /// Optimize (fcmp)&(fcmp) or (fcmp)|(fcmp).
353  /// NOTE: Unlike most of instcombine, this returns a Value which should
354  /// already be inserted into the function.
355  Value *foldLogicOfFCmps(FCmpInst *LHS, FCmpInst *RHS, bool IsAnd);
356 
357  Value *foldAndOrOfICmpsOfAndWithPow2(ICmpInst *LHS, ICmpInst *RHS,
358  Instruction *CxtI, bool IsAnd,
359  bool IsLogical = false);
360  Value *matchSelectFromAndOr(Value *A, Value *B, Value *C, Value *D);
361  Value *getSelectCondition(Value *A, Value *B);
362 
363  Instruction *foldIntrinsicWithOverflowCommon(IntrinsicInst *II);
364  Instruction *foldFPSignBitOps(BinaryOperator &I);
365 
366  // Optimize one of these forms:
367  // and i1 Op, SI / select i1 Op, i1 SI, i1 false (if IsAnd = true)
368  // or i1 Op, SI / select i1 Op, i1 true, i1 SI (if IsAnd = false)
369  // into simplier select instruction using isImpliedCondition.
370  Instruction *foldAndOrOfSelectUsingImpliedCond(Value *Op, SelectInst &SI,
371  bool IsAnd);
372 
373 public:
374  /// Inserts an instruction \p New before instruction \p Old
375  ///
376  /// Also adds the new instruction to the worklist and returns \p New so that
377  /// it is suitable for use as the return from the visitation patterns.
379  assert(New && !New->getParent() &&
380  "New instruction already inserted into a basic block!");
381  BasicBlock *BB = Old.getParent();
382  BB->getInstList().insert(Old.getIterator(), New); // Insert inst
383  Worklist.add(New);
384  return New;
385  }
386 
387  /// Same as InsertNewInstBefore, but also sets the debug loc.
389  New->setDebugLoc(Old.getDebugLoc());
390  return InsertNewInstBefore(New, Old);
391  }
392 
393  /// A combiner-aware RAUW-like routine.
394  ///
395  /// This method is to be used when an instruction is found to be dead,
396  /// replaceable with another preexisting expression. Here we add all uses of
397  /// I to the worklist, replace all uses of I with the new value, then return
398  /// I, so that the inst combiner will know that I was modified.
400  // If there are no uses to replace, then we return nullptr to indicate that
401  // no changes were made to the program.
402  if (I.use_empty()) return nullptr;
403 
404  Worklist.pushUsersToWorkList(I); // Add all modified instrs to worklist.
405 
406  // If we are replacing the instruction with itself, this must be in a
407  // segment of unreachable code, so just clobber the instruction.
408  if (&I == V)
409  V = UndefValue::get(I.getType());
410 
411  LLVM_DEBUG(dbgs() << "IC: Replacing " << I << "\n"
412  << " with " << *V << '\n');
413 
414  I.replaceAllUsesWith(V);
415  MadeIRChange = true;
416  return &I;
417  }
418 
419  /// Replace operand of instruction and add old operand to the worklist.
420  Instruction *replaceOperand(Instruction &I, unsigned OpNum, Value *V) {
421  Worklist.addValue(I.getOperand(OpNum));
422  I.setOperand(OpNum, V);
423  return &I;
424  }
425 
426  /// Replace use and add the previously used value to the worklist.
427  void replaceUse(Use &U, Value *NewValue) {
428  Worklist.addValue(U);
429  U = NewValue;
430  }
431 
432  /// Create and insert the idiom we use to indicate a block is unreachable
433  /// without having to rewrite the CFG from within InstCombine.
435  auto &Ctx = InsertAt->getContext();
438  InsertAt);
439  }
440 
441 
442  /// Combiner aware instruction erasure.
443  ///
444  /// When dealing with an instruction that has side effects or produces a void
445  /// value, we can't rely on DCE to delete the instruction. Instead, visit
446  /// methods should return the value returned by this function.
448  LLVM_DEBUG(dbgs() << "IC: ERASE " << I << '\n');
449  assert(I.use_empty() && "Cannot erase instruction that is used!");
451 
452  // Make sure that we reprocess all operands now that we reduced their
453  // use counts.
454  for (Use &Operand : I.operands())
455  if (auto *Inst = dyn_cast<Instruction>(Operand))
456  Worklist.add(Inst);
457 
458  Worklist.remove(&I);
459  I.eraseFromParent();
460  MadeIRChange = true;
461  return nullptr; // Don't do anything with FI
462  }
463 
464  void computeKnownBits(const Value *V, KnownBits &Known,
465  unsigned Depth, const Instruction *CxtI) const {
466  llvm::computeKnownBits(V, Known, DL, Depth, &AC, CxtI, &DT);
467  }
468 
469  KnownBits computeKnownBits(const Value *V, unsigned Depth,
470  const Instruction *CxtI) const {
471  return llvm::computeKnownBits(V, DL, Depth, &AC, CxtI, &DT);
472  }
473 
474  bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero = false,
475  unsigned Depth = 0,
476  const Instruction *CxtI = nullptr) {
477  return llvm::isKnownToBeAPowerOfTwo(V, DL, OrZero, Depth, &AC, CxtI, &DT);
478  }
479 
480  bool MaskedValueIsZero(const Value *V, const APInt &Mask, unsigned Depth = 0,
481  const Instruction *CxtI = nullptr) const {
482  return llvm::MaskedValueIsZero(V, Mask, DL, Depth, &AC, CxtI, &DT);
483  }
484 
485  unsigned ComputeNumSignBits(const Value *Op, unsigned Depth = 0,
486  const Instruction *CxtI = nullptr) const {
487  return llvm::ComputeNumSignBits(Op, DL, Depth, &AC, CxtI, &DT);
488  }
489 
491  const Value *RHS,
492  const Instruction *CxtI) const {
493  return llvm::computeOverflowForUnsignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
494  }
495 
497  const Value *RHS,
498  const Instruction *CxtI) const {
499  return llvm::computeOverflowForSignedMul(LHS, RHS, DL, &AC, CxtI, &DT);
500  }
501 
503  const Value *RHS,
504  const Instruction *CxtI) const {
505  return llvm::computeOverflowForUnsignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
506  }
507 
509  const Value *RHS,
510  const Instruction *CxtI) const {
511  return llvm::computeOverflowForSignedAdd(LHS, RHS, DL, &AC, CxtI, &DT);
512  }
513 
515  const Value *RHS,
516  const Instruction *CxtI) const {
517  return llvm::computeOverflowForUnsignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
518  }
519 
521  const Instruction *CxtI) const {
522  return llvm::computeOverflowForSignedSub(LHS, RHS, DL, &AC, CxtI, &DT);
523  }
524 
525  OverflowResult computeOverflow(
526  Instruction::BinaryOps BinaryOp, bool IsSigned,
527  Value *LHS, Value *RHS, Instruction *CxtI) const;
528 
529  /// Performs a few simplifications for operators which are associative
530  /// or commutative.
531  bool SimplifyAssociativeOrCommutative(BinaryOperator &I);
532 
533  /// Tries to simplify binary operations which some other binary
534  /// operation distributes over.
535  ///
536  /// It does this by either by factorizing out common terms (eg "(A*B)+(A*C)"
537  /// -> "A*(B+C)") or expanding out if this results in simplifications (eg: "A
538  /// & (B | C) -> (A&B) | (A&C)" if this is a win). Returns the simplified
539  /// value, or null if it didn't simplify.
540  Value *SimplifyUsingDistributiveLaws(BinaryOperator &I);
541 
542  /// Tries to simplify add operations using the definition of remainder.
543  ///
544  /// The definition of remainder is X % C = X - (X / C ) * C. The add
545  /// expression X % C0 + (( X / C0 ) % C1) * C0 can be simplified to
546  /// X % (C0 * C1)
547  Value *SimplifyAddWithRemainder(BinaryOperator &I);
548 
549  // Binary Op helper for select operations where the expression can be
550  // efficiently reorganized.
551  Value *SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS,
552  Value *RHS);
553 
554  /// This tries to simplify binary operations by factorizing out common terms
555  /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
556  Value *tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *,
557  Value *, Value *, Value *);
558 
559  /// Match a select chain which produces one of three values based on whether
560  /// the LHS is less than, equal to, or greater than RHS respectively.
561  /// Return true if we matched a three way compare idiom. The LHS, RHS, Less,
562  /// Equal and Greater values are saved in the matching process and returned to
563  /// the caller.
564  bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS,
566  ConstantInt *&Greater);
567 
568  /// Attempts to replace V with a simpler value based on the demanded
569  /// bits.
570  Value *SimplifyDemandedUseBits(Value *V, APInt DemandedMask, KnownBits &Known,
571  unsigned Depth, Instruction *CxtI);
572  bool SimplifyDemandedBits(Instruction *I, unsigned Op,
573  const APInt &DemandedMask, KnownBits &Known,
574  unsigned Depth = 0) override;
575 
576  /// Helper routine of SimplifyDemandedUseBits. It computes KnownZero/KnownOne
577  /// bits. It also tries to handle simplifications that can be done based on
578  /// DemandedMask, but without modifying the Instruction.
579  Value *SimplifyMultipleUseDemandedBits(Instruction *I,
580  const APInt &DemandedMask,
581  KnownBits &Known,
582  unsigned Depth, Instruction *CxtI);
583 
584  /// Helper routine of SimplifyDemandedUseBits. It tries to simplify demanded
585  /// bit for "r1 = shr x, c1; r2 = shl r1, c2" instruction sequence.
586  Value *simplifyShrShlDemandedBits(
587  Instruction *Shr, const APInt &ShrOp1, Instruction *Shl,
588  const APInt &ShlOp1, const APInt &DemandedMask, KnownBits &Known);
589 
590  /// Tries to simplify operands to an integer instruction based on its
591  /// demanded bits.
592  bool SimplifyDemandedInstructionBits(Instruction &Inst);
593 
594  virtual Value *
595  SimplifyDemandedVectorElts(Value *V, APInt DemandedElts, APInt &UndefElts,
596  unsigned Depth = 0,
597  bool AllowMultipleUsers = false) override;
598 
599  /// Canonicalize the position of binops relative to shufflevector.
600  Instruction *foldVectorBinop(BinaryOperator &Inst);
601  Instruction *foldVectorSelect(SelectInst &Sel);
602 
603  /// Given a binary operator, cast instruction, or select which has a PHI node
604  /// as operand #0, see if we can fold the instruction into the PHI (which is
605  /// only possible if all operands to the PHI are constants).
606  Instruction *foldOpIntoPhi(Instruction &I, PHINode *PN);
607 
608  /// Given an instruction with a select as one operand and a constant as the
609  /// other operand, try to fold the binary operator into the select arguments.
610  /// This also works for Cast instructions, which obviously do not have a
611  /// second operand.
612  Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI);
613 
614  /// This is a convenience wrapper function for the above two functions.
615  Instruction *foldBinOpIntoSelectOrPhi(BinaryOperator &I);
616 
617  Instruction *foldAddWithConstant(BinaryOperator &Add);
618 
619  /// Try to rotate an operation below a PHI node, using PHI nodes for
620  /// its operands.
621  Instruction *foldPHIArgOpIntoPHI(PHINode &PN);
622  Instruction *foldPHIArgBinOpIntoPHI(PHINode &PN);
623  Instruction *foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN);
624  Instruction *foldPHIArgExtractValueInstructionIntoPHI(PHINode &PN);
625  Instruction *foldPHIArgGEPIntoPHI(PHINode &PN);
626  Instruction *foldPHIArgLoadIntoPHI(PHINode &PN);
627  Instruction *foldPHIArgZextsIntoPHI(PHINode &PN);
628  Instruction *foldPHIArgIntToPtrToPHI(PHINode &PN);
629 
630  /// If an integer typed PHI has only one use which is an IntToPtr operation,
631  /// replace the PHI with an existing pointer typed PHI if it exists. Otherwise
632  /// insert a new pointer typed PHI and replace the original one.
633  Instruction *foldIntegerTypedPHI(PHINode &PN);
634 
635  /// Helper function for FoldPHIArgXIntoPHI() to set debug location for the
636  /// folded operation.
637  void PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN);
638 
639  Instruction *foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
641  Instruction *foldAllocaCmp(ICmpInst &ICI, const AllocaInst *Alloca,
642  const Value *Other);
643  Instruction *foldCmpLoadFromIndexedGlobal(GetElementPtrInst *GEP,
644  GlobalVariable *GV, CmpInst &ICI,
645  ConstantInt *AndCst = nullptr);
646  Instruction *foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI,
647  Constant *RHSC);
648  Instruction *foldICmpAddOpConst(Value *X, const APInt &C,
649  ICmpInst::Predicate Pred);
650  Instruction *foldICmpWithCastOp(ICmpInst &ICI);
651 
652  Instruction *foldICmpUsingKnownBits(ICmpInst &Cmp);
654  Instruction *foldICmpWithConstant(ICmpInst &Cmp);
655  Instruction *foldICmpInstWithConstant(ICmpInst &Cmp);
656  Instruction *foldICmpInstWithConstantNotInt(ICmpInst &Cmp);
657  Instruction *foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ);
658  Instruction *foldICmpEquality(ICmpInst &Cmp);
659  Instruction *foldIRemByPowerOfTwoToBitTest(ICmpInst &I);
660  Instruction *foldSignBitTest(ICmpInst &I);
661  Instruction *foldICmpWithZero(ICmpInst &Cmp);
662 
663  Value *foldMultiplicationOverflowCheck(ICmpInst &Cmp);
664 
665  Instruction *foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select,
666  ConstantInt *C);
667  Instruction *foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc,
668  const APInt &C);
669  Instruction *foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And,
670  const APInt &C);
671  Instruction *foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor,
672  const APInt &C);
673  Instruction *foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or,
674  const APInt &C);
675  Instruction *foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul,
676  const APInt &C);
677  Instruction *foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl,
678  const APInt &C);
679  Instruction *foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr,
680  const APInt &C);
681  Instruction *foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
682  const APInt &C);
683  Instruction *foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv,
684  const APInt &C);
685  Instruction *foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div,
686  const APInt &C);
687  Instruction *foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub,
688  const APInt &C);
689  Instruction *foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add,
690  const APInt &C);
691  Instruction *foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And,
692  const APInt &C1);
693  Instruction *foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And,
694  const APInt &C1, const APInt &C2);
695  Instruction *foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
696  const APInt &C2);
697  Instruction *foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1,
698  const APInt &C2);
699 
700  Instruction *foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp,
701  BinaryOperator *BO,
702  const APInt &C);
703  Instruction *foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
704  const APInt &C);
705  Instruction *foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II,
706  const APInt &C);
707  Instruction *foldICmpBitCast(ICmpInst &Cmp);
708 
709  // Helpers of visitSelectInst().
710  Instruction *foldSelectExtConst(SelectInst &Sel);
711  Instruction *foldSelectOpOp(SelectInst &SI, Instruction *TI, Instruction *FI);
712  Instruction *foldSelectIntoOp(SelectInst &SI, Value *, Value *);
713  Instruction *foldSPFofSPF(Instruction *Inner, SelectPatternFlavor SPF1,
714  Value *A, Value *B, Instruction &Outer,
715  SelectPatternFlavor SPF2, Value *C);
716  Instruction *foldSelectInstWithICmp(SelectInst &SI, ICmpInst *ICI);
717  Instruction *foldSelectValueEquivalence(SelectInst &SI, ICmpInst &ICI);
718 
719  Value *insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi,
720  bool isSigned, bool Inside);
721  Instruction *PromoteCastOfAllocation(BitCastInst &CI, AllocaInst &AI);
722  bool mergeStoreIntoSuccessor(StoreInst &SI);
723 
724  /// Given an initial instruction, check to see if it is the root of a
725  /// bswap/bitreverse idiom. If so, return the equivalent bswap/bitreverse
726  /// intrinsic.
727  Instruction *matchBSwapOrBitReverse(Instruction &I, bool MatchBSwaps,
728  bool MatchBitReversals);
729 
730  Instruction *SimplifyAnyMemTransfer(AnyMemTransferInst *MI);
731  Instruction *SimplifyAnyMemSet(AnyMemSetInst *MI);
732 
733  Value *EvaluateInDifferentType(Value *V, Type *Ty, bool isSigned);
734 
735  /// Returns a value X such that Val = X * Scale, or null if none.
736  ///
737  /// If the multiplication is known not to overflow then NoSignedWrap is set.
738  Value *Descale(Value *Val, APInt Scale, bool &NoSignedWrap);
739 };
740 
741 class Negator final {
742  /// Top-to-bottom, def-to-use negated instruction tree we produced.
744 
747 
748  const DataLayout &DL;
749  AssumptionCache &AC;
750  const DominatorTree &DT;
751 
752  const bool IsTrulyNegation;
753 
754  SmallDenseMap<Value *, Value *> NegationsCache;
755 
757  const DominatorTree &DT, bool IsTrulyNegation);
758 
759 #if LLVM_ENABLE_STATS
760  unsigned NumValuesVisitedInThisNegator = 0;
761  ~Negator();
762 #endif
763 
764  using Result = std::pair<ArrayRef<Instruction *> /*NewInstructions*/,
765  Value * /*NegatedRoot*/>;
766 
767  std::array<Value *, 2> getSortedOperandsOfBinOp(Instruction *I);
768 
769  LLVM_NODISCARD Value *visitImpl(Value *V, unsigned Depth);
770 
771  LLVM_NODISCARD Value *negate(Value *V, unsigned Depth);
772 
773  /// Recurse depth-first and attempt to sink the negation.
774  /// FIXME: use worklist?
776 
777  Negator(const Negator &) = delete;
778  Negator(Negator &&) = delete;
779  Negator &operator=(const Negator &) = delete;
780  Negator &operator=(Negator &&) = delete;
781 
782 public:
783  /// Attempt to negate \p Root. Retuns nullptr if negation can't be performed,
784  /// otherwise returns negated value.
785  LLVM_NODISCARD static Value *Negate(bool LHSIsZero, Value *Root,
786  InstCombinerImpl &IC);
787 };
788 
789 } // end namespace llvm
790 
791 #undef DEBUG_TYPE
792 
793 #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:474
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:105
llvm::object::Equal
@ Equal
Definition: COFFModuleDefinition.cpp:38
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::OverflowResult::NeverOverflows
@ NeverOverflows
Never overflows.
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2986
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:356
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:720
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:4727
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::ExtractElementInst
This instruction extracts a single (scalar) element from a VectorType value.
Definition: Instructions.h:1873
TargetFolder.h
llvm::SystemZII::IsLogical
@ IsLogical
Definition: SystemZInstrInfo.h:49
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5198
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:378
Statistic.h
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2885
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::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:4783
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:74
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:469
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:399
llvm::Optional
Definition: APInt.h:33
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:380
llvm::UnaryOperator
Definition: InstrTypes.h:102
llvm::SelectPatternFlavor
SelectPatternFlavor
Specific patterns of select instructions we can match.
Definition: ValueTracking.h:676
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:101
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:163
llvm::InstCombinerImpl::eraseInstFromFunction
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Definition: InstCombineInternal.h:447
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:4882
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:5238
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:5291
llvm::AAResults
Definition: AliasAnalysis.h:508
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:1369
InstructionWorklist.h
llvm::InsertElementInst
This instruction inserts a single (scalar) element into a VectorType value.
Definition: Instructions.h:1937
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:799
llvm::Instruction
Definition: Instruction.h:45
llvm::InstCombinerImpl::computeOverflowForUnsignedMul
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:490
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1796
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
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:289
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:496
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::AnyMemTransferInst
Definition: IntrinsicInst.h:1029
llvm::OverflowResult
OverflowResult
Definition: ValueTracking.h:487
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3749
llvm::ARM_PROC::IE
@ IE
Definition: ARMBaseInfo.h:27
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
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:1203
llvm::FPToSIInst
This class represents a cast from floating point to signed integer.
Definition: Instructions.h:5065
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:4753
llvm::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC, const Instruction *CxtI, const DominatorTree *DT)
Definition: ValueTracking.cpp:4859
llvm::CallBrInst
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
Definition: Instructions.h:3958
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:928
llvm::InstCombinerImpl::replaceUse
void replaceUse(Use &U, Value *NewValue)
Replace use and add the previously used value to the worklist.
Definition: InstCombineInternal.h:427
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
llvm::InstCombinerImpl::computeOverflowForSignedAdd
OverflowResult computeOverflowForSignedAdd(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:508
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:213
IRBuilder.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::FPToUIInst
This class represents a cast from floating point to unsigned integer.
Definition: Instructions.h:5026
llvm::GEPOperator
Definition: Operator.h:458
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:650
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::ZExtInst
This class represents zero extension of integer types.
Definition: Instructions.h:4792
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:177
llvm::Negator
Definition: InstCombineInternal.h:741
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::VAEndInst
This represents the llvm.va_end intrinsic.
Definition: IntrinsicInst.h:1101
llvm::BinaryOperator
Definition: InstrTypes.h:189
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:485
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
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:134
llvm::Value::getContext
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:990
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:5147
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:430
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:421
llvm::SExtInst
This class represents a sign extension of integer types.
Definition: Instructions.h:4831
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:726
llvm::MCID::Select
@ Select
Definition: MCInstrDesc.h:162
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:83
llvm::ConstantInt::getTrue
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:873
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:388
llvm::AnyMemSetInst
This class represents any memset intrinsic.
Definition: IntrinsicInst.h:1010
llvm::InstCombinerImpl::computeOverflowForSignedSub
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:520
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2380
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
LLVM_NODISCARD
#define LLVM_NODISCARD
LLVM_NODISCARD - Warn if a type or return value is discarded.
Definition: Compiler.h: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:434
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:1728
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:221
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:4741
llvm::MCID::Add
@ Add
Definition: MCInstrDesc.h:183
llvm::IntToPtrInst
This class represents a cast from an integer to a pointer.
Definition: Instructions.h:5104
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:420
llvm::Instruction::BinaryOps
BinaryOps
Definition: Instruction.h:785
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2009
llvm::Instruction::getDebugLoc
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:370
llvm::FreezeInst
This class represents a freeze function that returns random concrete value if an operand is either a ...
Definition: Instructions.h:5358
llvm::FPTruncInst
This class represents a truncation of floating point types.
Definition: Instructions.h:4870
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:502
llvm::InstCombinerImpl::computeOverflowForUnsignedSub
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Definition: InstCombineInternal.h:514
llvm::PHINode
Definition: Instructions.h:2633
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:1161
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
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:172
llvm::UnreachableInst
This function has undefined behavior.
Definition: Instructions.h:4713
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:292
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::SwitchInst
Multiway switch.
Definition: Instructions.h:3212
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition: Instructions.h:3068
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:2491
foldICmpWithDominatingICmp
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
Definition: CodeGenPrepare.cpp:1651
Value.h
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:480
llvm::InstCombinerImpl::computeKnownBits
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
Definition: InstCombineInternal.h:464
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44