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