LLVM  14.0.0git
InstructionCombining.cpp
Go to the documentation of this file.
1 //===- InstructionCombining.cpp - Combine multiple instructions -----------===//
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 // InstructionCombining - Combine instructions to form fewer, simple
10 // instructions. This pass does not modify the CFG. This pass is where
11 // algebraic simplification happens.
12 //
13 // This pass combines things like:
14 // %Y = add i32 %X, 1
15 // %Z = add i32 %Y, 1
16 // into:
17 // %Z = add i32 %X, 2
18 //
19 // This is a simple worklist driven algorithm.
20 //
21 // This pass guarantees that the following canonicalizations are performed on
22 // the program:
23 // 1. If a binary operator has a constant operand, it is moved to the RHS
24 // 2. Bitwise operators with constant operands are always grouped so that
25 // shifts are performed first, then or's, then and's, then xor's.
26 // 3. Compare instructions are converted from <,>,<=,>= to ==,!= if possible
27 // 4. All cmp instructions on boolean values are replaced with logical ops
28 // 5. add X, X is represented as (X*2) => (X << 1)
29 // 6. Multiplies with a power-of-two constant argument are transformed into
30 // shifts.
31 // ... etc.
32 //
33 //===----------------------------------------------------------------------===//
34 
35 #include "InstCombineInternal.h"
36 #include "llvm-c/Initialization.h"
38 #include "llvm/ADT/APInt.h"
39 #include "llvm/ADT/ArrayRef.h"
40 #include "llvm/ADT/DenseMap.h"
41 #include "llvm/ADT/None.h"
42 #include "llvm/ADT/SmallPtrSet.h"
43 #include "llvm/ADT/SmallVector.h"
44 #include "llvm/ADT/Statistic.h"
45 #include "llvm/ADT/TinyPtrVector.h"
50 #include "llvm/Analysis/CFG.h"
56 #include "llvm/Analysis/LoopInfo.h"
65 #include "llvm/IR/BasicBlock.h"
66 #include "llvm/IR/CFG.h"
67 #include "llvm/IR/Constant.h"
68 #include "llvm/IR/Constants.h"
69 #include "llvm/IR/DIBuilder.h"
70 #include "llvm/IR/DataLayout.h"
71 #include "llvm/IR/DerivedTypes.h"
72 #include "llvm/IR/Dominators.h"
73 #include "llvm/IR/Function.h"
75 #include "llvm/IR/IRBuilder.h"
76 #include "llvm/IR/InstrTypes.h"
77 #include "llvm/IR/Instruction.h"
78 #include "llvm/IR/Instructions.h"
79 #include "llvm/IR/IntrinsicInst.h"
80 #include "llvm/IR/Intrinsics.h"
82 #include "llvm/IR/Metadata.h"
83 #include "llvm/IR/Operator.h"
84 #include "llvm/IR/PassManager.h"
85 #include "llvm/IR/PatternMatch.h"
86 #include "llvm/IR/Type.h"
87 #include "llvm/IR/Use.h"
88 #include "llvm/IR/User.h"
89 #include "llvm/IR/Value.h"
90 #include "llvm/IR/ValueHandle.h"
91 #include "llvm/InitializePasses.h"
92 #include "llvm/Pass.h"
94 #include "llvm/Support/Casting.h"
96 #include "llvm/Support/Compiler.h"
97 #include "llvm/Support/Debug.h"
100 #include "llvm/Support/KnownBits.h"
105 #include <algorithm>
106 #include <cassert>
107 #include <cstdint>
108 #include <memory>
109 #include <string>
110 #include <utility>
111 
112 using namespace llvm;
113 using namespace llvm::PatternMatch;
114 
115 #define DEBUG_TYPE "instcombine"
116 
117 STATISTIC(NumWorklistIterations,
118  "Number of instruction combining iterations performed");
119 
120 STATISTIC(NumCombined , "Number of insts combined");
121 STATISTIC(NumConstProp, "Number of constant folds");
122 STATISTIC(NumDeadInst , "Number of dead inst eliminated");
123 STATISTIC(NumSunkInst , "Number of instructions sunk");
124 STATISTIC(NumExpand, "Number of expansions");
125 STATISTIC(NumFactor , "Number of factorizations");
126 STATISTIC(NumReassoc , "Number of reassociations");
127 DEBUG_COUNTER(VisitCounter, "instcombine-visit",
128  "Controls which instructions are visited");
129 
130 // FIXME: these limits eventually should be as low as 2.
131 static constexpr unsigned InstCombineDefaultMaxIterations = 1000;
132 #ifndef NDEBUG
133 static constexpr unsigned InstCombineDefaultInfiniteLoopThreshold = 100;
134 #else
135 static constexpr unsigned InstCombineDefaultInfiniteLoopThreshold = 1000;
136 #endif
137 
138 static cl::opt<bool>
139 EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"),
140  cl::init(true));
141 
143  "instcombine-max-iterations",
144  cl::desc("Limit the maximum number of instruction combining iterations"),
146 
148  "instcombine-infinite-loop-threshold",
149  cl::desc("Number of instruction combining iterations considered an "
150  "infinite loop"),
152 
153 static cl::opt<unsigned>
154 MaxArraySize("instcombine-maxarray-size", cl::init(1024),
155  cl::desc("Maximum array size considered when doing a combine"));
156 
157 // FIXME: Remove this flag when it is no longer necessary to convert
158 // llvm.dbg.declare to avoid inaccurate debug info. Setting this to false
159 // increases variable availability at the cost of accuracy. Variables that
160 // cannot be promoted by mem2reg or SROA will be described as living in memory
161 // for their entire lifetime. However, passes like DSE and instcombine can
162 // delete stores to the alloca, leading to misleading and inaccurate debug
163 // information. This flag can be removed when those passes are fixed.
164 static cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare",
165  cl::Hidden, cl::init(true));
166 
169  // Handle target specific intrinsics
170  if (II.getCalledFunction()->isTargetIntrinsic()) {
171  return TTI.instCombineIntrinsic(*this, II);
172  }
173  return None;
174 }
175 
177  IntrinsicInst &II, APInt DemandedMask, KnownBits &Known,
178  bool &KnownBitsComputed) {
179  // Handle target specific intrinsics
180  if (II.getCalledFunction()->isTargetIntrinsic()) {
181  return TTI.simplifyDemandedUseBitsIntrinsic(*this, II, DemandedMask, Known,
182  KnownBitsComputed);
183  }
184  return None;
185 }
186 
188  IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, APInt &UndefElts2,
189  APInt &UndefElts3,
190  std::function<void(Instruction *, unsigned, APInt, APInt &)>
191  SimplifyAndSetOp) {
192  // Handle target specific intrinsics
193  if (II.getCalledFunction()->isTargetIntrinsic()) {
195  *this, II, DemandedElts, UndefElts, UndefElts2, UndefElts3,
196  SimplifyAndSetOp);
197  }
198  return None;
199 }
200 
201 Value *InstCombinerImpl::EmitGEPOffset(User *GEP) {
202  return llvm::EmitGEPOffset(&Builder, DL, GEP);
203 }
204 
205 /// Return true if it is desirable to convert an integer computation from a
206 /// given bit width to a new bit width.
207 /// We don't want to convert from a legal to an illegal type or from a smaller
208 /// to a larger illegal type. A width of '1' is always treated as a legal type
209 /// because i1 is a fundamental type in IR, and there are many specialized
210 /// optimizations for i1 types. Widths of 8, 16 or 32 are equally treated as
211 /// legal to convert to, in order to open up more combining opportunities.
212 /// NOTE: this treats i8, i16 and i32 specially, due to them being so common
213 /// from frontend languages.
214 bool InstCombinerImpl::shouldChangeType(unsigned FromWidth,
215  unsigned ToWidth) const {
216  bool FromLegal = FromWidth == 1 || DL.isLegalInteger(FromWidth);
217  bool ToLegal = ToWidth == 1 || DL.isLegalInteger(ToWidth);
218 
219  // Convert to widths of 8, 16 or 32 even if they are not legal types. Only
220  // shrink types, to prevent infinite loops.
221  if (ToWidth < FromWidth && (ToWidth == 8 || ToWidth == 16 || ToWidth == 32))
222  return true;
223 
224  // If this is a legal integer from type, and the result would be an illegal
225  // type, don't do the transformation.
226  if (FromLegal && !ToLegal)
227  return false;
228 
229  // Otherwise, if both are illegal, do not increase the size of the result. We
230  // do allow things like i160 -> i64, but not i64 -> i160.
231  if (!FromLegal && !ToLegal && ToWidth > FromWidth)
232  return false;
233 
234  return true;
235 }
236 
237 /// Return true if it is desirable to convert a computation from 'From' to 'To'.
238 /// We don't want to convert from a legal to an illegal type or from a smaller
239 /// to a larger illegal type. i1 is always treated as a legal type because it is
240 /// a fundamental type in IR, and there are many specialized optimizations for
241 /// i1 types.
242 bool InstCombinerImpl::shouldChangeType(Type *From, Type *To) const {
243  // TODO: This could be extended to allow vectors. Datalayout changes might be
244  // needed to properly support that.
245  if (!From->isIntegerTy() || !To->isIntegerTy())
246  return false;
247 
248  unsigned FromWidth = From->getPrimitiveSizeInBits();
249  unsigned ToWidth = To->getPrimitiveSizeInBits();
250  return shouldChangeType(FromWidth, ToWidth);
251 }
252 
253 // Return true, if No Signed Wrap should be maintained for I.
254 // The No Signed Wrap flag can be kept if the operation "B (I.getOpcode) C",
255 // where both B and C should be ConstantInts, results in a constant that does
256 // not overflow. This function only handles the Add and Sub opcodes. For
257 // all other opcodes, the function conservatively returns false.
259  auto *OBO = dyn_cast<OverflowingBinaryOperator>(&I);
260  if (!OBO || !OBO->hasNoSignedWrap())
261  return false;
262 
263  // We reason about Add and Sub Only.
264  Instruction::BinaryOps Opcode = I.getOpcode();
265  if (Opcode != Instruction::Add && Opcode != Instruction::Sub)
266  return false;
267 
268  const APInt *BVal, *CVal;
269  if (!match(B, m_APInt(BVal)) || !match(C, m_APInt(CVal)))
270  return false;
271 
272  bool Overflow = false;
273  if (Opcode == Instruction::Add)
274  (void)BVal->sadd_ov(*CVal, Overflow);
275  else
276  (void)BVal->ssub_ov(*CVal, Overflow);
277 
278  return !Overflow;
279 }
280 
282  auto *OBO = dyn_cast<OverflowingBinaryOperator>(&I);
283  return OBO && OBO->hasNoUnsignedWrap();
284 }
285 
287  auto *OBO = dyn_cast<OverflowingBinaryOperator>(&I);
288  return OBO && OBO->hasNoSignedWrap();
289 }
290 
291 /// Conservatively clears subclassOptionalData after a reassociation or
292 /// commutation. We preserve fast-math flags when applicable as they can be
293 /// preserved.
295  FPMathOperator *FPMO = dyn_cast<FPMathOperator>(&I);
296  if (!FPMO) {
297  I.clearSubclassOptionalData();
298  return;
299  }
300 
301  FastMathFlags FMF = I.getFastMathFlags();
302  I.clearSubclassOptionalData();
303  I.setFastMathFlags(FMF);
304 }
305 
306 /// Combine constant operands of associative operations either before or after a
307 /// cast to eliminate one of the associative operations:
308 /// (op (cast (op X, C2)), C1) --> (cast (op X, op (C1, C2)))
309 /// (op (cast (op X, C2)), C1) --> (op (cast X), op (C1, C2))
311  InstCombinerImpl &IC) {
312  auto *Cast = dyn_cast<CastInst>(BinOp1->getOperand(0));
313  if (!Cast || !Cast->hasOneUse())
314  return false;
315 
316  // TODO: Enhance logic for other casts and remove this check.
317  auto CastOpcode = Cast->getOpcode();
318  if (CastOpcode != Instruction::ZExt)
319  return false;
320 
321  // TODO: Enhance logic for other BinOps and remove this check.
322  if (!BinOp1->isBitwiseLogicOp())
323  return false;
324 
325  auto AssocOpcode = BinOp1->getOpcode();
326  auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0));
327  if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode)
328  return false;
329 
330  Constant *C1, *C2;
331  if (!match(BinOp1->getOperand(1), m_Constant(C1)) ||
332  !match(BinOp2->getOperand(1), m_Constant(C2)))
333  return false;
334 
335  // TODO: This assumes a zext cast.
336  // Eg, if it was a trunc, we'd cast C1 to the source type because casting C2
337  // to the destination type might lose bits.
338 
339  // Fold the constants together in the destination type:
340  // (op (cast (op X, C2)), C1) --> (op (cast X), FoldedC)
341  Type *DestTy = C1->getType();
342  Constant *CastC2 = ConstantExpr::getCast(CastOpcode, C2, DestTy);
343  Constant *FoldedC = ConstantExpr::get(AssocOpcode, C1, CastC2);
344  IC.replaceOperand(*Cast, 0, BinOp2->getOperand(0));
345  IC.replaceOperand(*BinOp1, 1, FoldedC);
346  return true;
347 }
348 
349 // Simplifies IntToPtr/PtrToInt RoundTrip Cast To BitCast.
350 // inttoptr ( ptrtoint (x) ) --> x
351 Value *InstCombinerImpl::simplifyIntToPtrRoundTripCast(Value *Val) {
352  auto *IntToPtr = dyn_cast<IntToPtrInst>(Val);
353  if (IntToPtr && DL.getPointerTypeSizeInBits(IntToPtr->getDestTy()) ==
354  DL.getTypeSizeInBits(IntToPtr->getSrcTy())) {
355  auto *PtrToInt = dyn_cast<PtrToIntInst>(IntToPtr->getOperand(0));
356  Type *CastTy = IntToPtr->getDestTy();
357  if (PtrToInt &&
358  CastTy->getPointerAddressSpace() ==
359  PtrToInt->getSrcTy()->getPointerAddressSpace() &&
360  DL.getPointerTypeSizeInBits(PtrToInt->getSrcTy()) ==
361  DL.getTypeSizeInBits(PtrToInt->getDestTy())) {
362  return CastInst::CreateBitOrPointerCast(PtrToInt->getOperand(0), CastTy,
363  "", PtrToInt);
364  }
365  }
366  return nullptr;
367 }
368 
369 /// This performs a few simplifications for operators that are associative or
370 /// commutative:
371 ///
372 /// Commutative operators:
373 ///
374 /// 1. Order operands such that they are listed from right (least complex) to
375 /// left (most complex). This puts constants before unary operators before
376 /// binary operators.
377 ///
378 /// Associative operators:
379 ///
380 /// 2. Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.
381 /// 3. Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.
382 ///
383 /// Associative and commutative operators:
384 ///
385 /// 4. Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies.
386 /// 5. Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.
387 /// 6. Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"
388 /// if C1 and C2 are constants.
390  Instruction::BinaryOps Opcode = I.getOpcode();
391  bool Changed = false;
392 
393  do {
394  // Order operands such that they are listed from right (least complex) to
395  // left (most complex). This puts constants before unary operators before
396  // binary operators.
397  if (I.isCommutative() && getComplexity(I.getOperand(0)) <
398  getComplexity(I.getOperand(1)))
399  Changed = !I.swapOperands();
400 
401  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));
402  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));
403 
404  if (I.isAssociative()) {
405  // Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.
406  if (Op0 && Op0->getOpcode() == Opcode) {
407  Value *A = Op0->getOperand(0);
408  Value *B = Op0->getOperand(1);
409  Value *C = I.getOperand(1);
410 
411  // Does "B op C" simplify?
412  if (Value *V = SimplifyBinOp(Opcode, B, C, SQ.getWithInstruction(&I))) {
413  // It simplifies to V. Form "A op V".
414  replaceOperand(I, 0, A);
415  replaceOperand(I, 1, V);
416  bool IsNUW = hasNoUnsignedWrap(I) && hasNoUnsignedWrap(*Op0);
417  bool IsNSW = maintainNoSignedWrap(I, B, C) && hasNoSignedWrap(*Op0);
418 
419  // Conservatively clear all optional flags since they may not be
420  // preserved by the reassociation. Reset nsw/nuw based on the above
421  // analysis.
423 
424  // Note: this is only valid because SimplifyBinOp doesn't look at
425  // the operands to Op0.
426  if (IsNUW)
427  I.setHasNoUnsignedWrap(true);
428 
429  if (IsNSW)
430  I.setHasNoSignedWrap(true);
431 
432  Changed = true;
433  ++NumReassoc;
434  continue;
435  }
436  }
437 
438  // Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.
439  if (Op1 && Op1->getOpcode() == Opcode) {
440  Value *A = I.getOperand(0);
441  Value *B = Op1->getOperand(0);
442  Value *C = Op1->getOperand(1);
443 
444  // Does "A op B" simplify?
445  if (Value *V = SimplifyBinOp(Opcode, A, B, SQ.getWithInstruction(&I))) {
446  // It simplifies to V. Form "V op C".
447  replaceOperand(I, 0, V);
448  replaceOperand(I, 1, C);
449  // Conservatively clear the optional flags, since they may not be
450  // preserved by the reassociation.
452  Changed = true;
453  ++NumReassoc;
454  continue;
455  }
456  }
457  }
458 
459  if (I.isAssociative() && I.isCommutative()) {
460  if (simplifyAssocCastAssoc(&I, *this)) {
461  Changed = true;
462  ++NumReassoc;
463  continue;
464  }
465 
466  // Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies.
467  if (Op0 && Op0->getOpcode() == Opcode) {
468  Value *A = Op0->getOperand(0);
469  Value *B = Op0->getOperand(1);
470  Value *C = I.getOperand(1);
471 
472  // Does "C op A" simplify?
473  if (Value *V = SimplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) {
474  // It simplifies to V. Form "V op B".
475  replaceOperand(I, 0, V);
476  replaceOperand(I, 1, B);
477  // Conservatively clear the optional flags, since they may not be
478  // preserved by the reassociation.
480  Changed = true;
481  ++NumReassoc;
482  continue;
483  }
484  }
485 
486  // Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.
487  if (Op1 && Op1->getOpcode() == Opcode) {
488  Value *A = I.getOperand(0);
489  Value *B = Op1->getOperand(0);
490  Value *C = Op1->getOperand(1);
491 
492  // Does "C op A" simplify?
493  if (Value *V = SimplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) {
494  // It simplifies to V. Form "B op V".
495  replaceOperand(I, 0, B);
496  replaceOperand(I, 1, V);
497  // Conservatively clear the optional flags, since they may not be
498  // preserved by the reassociation.
500  Changed = true;
501  ++NumReassoc;
502  continue;
503  }
504  }
505 
506  // Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"
507  // if C1 and C2 are constants.
508  Value *A, *B;
509  Constant *C1, *C2;
510  if (Op0 && Op1 &&
511  Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode &&
512  match(Op0, m_OneUse(m_BinOp(m_Value(A), m_Constant(C1)))) &&
513  match(Op1, m_OneUse(m_BinOp(m_Value(B), m_Constant(C2))))) {
514  bool IsNUW = hasNoUnsignedWrap(I) &&
515  hasNoUnsignedWrap(*Op0) &&
516  hasNoUnsignedWrap(*Op1);
517  BinaryOperator *NewBO = (IsNUW && Opcode == Instruction::Add) ?
518  BinaryOperator::CreateNUW(Opcode, A, B) :
519  BinaryOperator::Create(Opcode, A, B);
520 
521  if (isa<FPMathOperator>(NewBO)) {
522  FastMathFlags Flags = I.getFastMathFlags();
523  Flags &= Op0->getFastMathFlags();
524  Flags &= Op1->getFastMathFlags();
525  NewBO->setFastMathFlags(Flags);
526  }
527  InsertNewInstWith(NewBO, I);
528  NewBO->takeName(Op1);
529  replaceOperand(I, 0, NewBO);
530  replaceOperand(I, 1, ConstantExpr::get(Opcode, C1, C2));
531  // Conservatively clear the optional flags, since they may not be
532  // preserved by the reassociation.
534  if (IsNUW)
535  I.setHasNoUnsignedWrap(true);
536 
537  Changed = true;
538  continue;
539  }
540  }
541 
542  // No further simplifications.
543  return Changed;
544  } while (true);
545 }
546 
547 /// Return whether "X LOp (Y ROp Z)" is always equal to
548 /// "(X LOp Y) ROp (X LOp Z)".
551  // X & (Y | Z) <--> (X & Y) | (X & Z)
552  // X & (Y ^ Z) <--> (X & Y) ^ (X & Z)
553  if (LOp == Instruction::And)
554  return ROp == Instruction::Or || ROp == Instruction::Xor;
555 
556  // X | (Y & Z) <--> (X | Y) & (X | Z)
557  if (LOp == Instruction::Or)
558  return ROp == Instruction::And;
559 
560  // X * (Y + Z) <--> (X * Y) + (X * Z)
561  // X * (Y - Z) <--> (X * Y) - (X * Z)
562  if (LOp == Instruction::Mul)
563  return ROp == Instruction::Add || ROp == Instruction::Sub;
564 
565  return false;
566 }
567 
568 /// Return whether "(X LOp Y) ROp Z" is always equal to
569 /// "(X ROp Z) LOp (Y ROp Z)".
573  return leftDistributesOverRight(ROp, LOp);
574 
575  // (X {&|^} Y) >> Z <--> (X >> Z) {&|^} (Y >> Z) for all shifts.
577 
578  // TODO: It would be nice to handle division, aka "(X + Y)/Z = X/Z + Y/Z",
579  // but this requires knowing that the addition does not overflow and other
580  // such subtleties.
581 }
582 
583 /// This function returns identity value for given opcode, which can be used to
584 /// factor patterns like (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1).
586  if (isa<Constant>(V))
587  return nullptr;
588 
589  return ConstantExpr::getBinOpIdentity(Opcode, V->getType());
590 }
591 
592 /// This function predicates factorization using distributive laws. By default,
593 /// it just returns the 'Op' inputs. But for special-cases like
594 /// 'add(shl(X, 5), ...)', this function will have TopOpcode == Instruction::Add
595 /// and Op = shl(X, 5). The 'shl' is treated as the more general 'mul X, 32' to
596 /// allow more factorization opportunities.
599  Value *&LHS, Value *&RHS) {
600  assert(Op && "Expected a binary operator");
601  LHS = Op->getOperand(0);
602  RHS = Op->getOperand(1);
603  if (TopOpcode == Instruction::Add || TopOpcode == Instruction::Sub) {
604  Constant *C;
605  if (match(Op, m_Shl(m_Value(), m_Constant(C)))) {
606  // X << C --> X * (1 << C)
607  RHS = ConstantExpr::getShl(ConstantInt::get(Op->getType(), 1), C);
608  return Instruction::Mul;
609  }
610  // TODO: We can add other conversions e.g. shr => div etc.
611  }
612  return Op->getOpcode();
613 }
614 
615 /// This tries to simplify binary operations by factorizing out common terms
616 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
618  Instruction::BinaryOps InnerOpcode,
619  Value *A, Value *B, Value *C,
620  Value *D) {
621  assert(A && B && C && D && "All values must be provided");
622 
623  Value *V = nullptr;
624  Value *SimplifiedInst = nullptr;
625  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
626  Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
627 
628  // Does "X op' Y" always equal "Y op' X"?
629  bool InnerCommutative = Instruction::isCommutative(InnerOpcode);
630 
631  // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"?
632  if (leftDistributesOverRight(InnerOpcode, TopLevelOpcode))
633  // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
634  // commutative case, "(A op' B) op (C op' A)"?
635  if (A == C || (InnerCommutative && A == D)) {
636  if (A != C)
637  std::swap(C, D);
638  // Consider forming "A op' (B op D)".
639  // If "B op D" simplifies then it can be formed with no cost.
640  V = SimplifyBinOp(TopLevelOpcode, B, D, SQ.getWithInstruction(&I));
641  // If "B op D" doesn't simplify then only go on if both of the existing
642  // operations "A op' B" and "C op' D" will be zapped as no longer used.
643  if (!V && LHS->hasOneUse() && RHS->hasOneUse())
644  V = Builder.CreateBinOp(TopLevelOpcode, B, D, RHS->getName());
645  if (V) {
646  SimplifiedInst = Builder.CreateBinOp(InnerOpcode, A, V);
647  }
648  }
649 
650  // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"?
651  if (!SimplifiedInst && rightDistributesOverLeft(TopLevelOpcode, InnerOpcode))
652  // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
653  // commutative case, "(A op' B) op (B op' D)"?
654  if (B == D || (InnerCommutative && B == C)) {
655  if (B != D)
656  std::swap(C, D);
657  // Consider forming "(A op C) op' B".
658  // If "A op C" simplifies then it can be formed with no cost.
659  V = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I));
660 
661  // If "A op C" doesn't simplify then only go on if both of the existing
662  // operations "A op' B" and "C op' D" will be zapped as no longer used.
663  if (!V && LHS->hasOneUse() && RHS->hasOneUse())
664  V = Builder.CreateBinOp(TopLevelOpcode, A, C, LHS->getName());
665  if (V) {
666  SimplifiedInst = Builder.CreateBinOp(InnerOpcode, V, B);
667  }
668  }
669 
670  if (SimplifiedInst) {
671  ++NumFactor;
672  SimplifiedInst->takeName(&I);
673 
674  // Check if we can add NSW/NUW flags to SimplifiedInst. If so, set them.
675  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SimplifiedInst)) {
676  if (isa<OverflowingBinaryOperator>(SimplifiedInst)) {
677  bool HasNSW = false;
678  bool HasNUW = false;
679  if (isa<OverflowingBinaryOperator>(&I)) {
680  HasNSW = I.hasNoSignedWrap();
681  HasNUW = I.hasNoUnsignedWrap();
682  }
683 
684  if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS)) {
685  HasNSW &= LOBO->hasNoSignedWrap();
686  HasNUW &= LOBO->hasNoUnsignedWrap();
687  }
688 
689  if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS)) {
690  HasNSW &= ROBO->hasNoSignedWrap();
691  HasNUW &= ROBO->hasNoUnsignedWrap();
692  }
693 
694  if (TopLevelOpcode == Instruction::Add &&
695  InnerOpcode == Instruction::Mul) {
696  // We can propagate 'nsw' if we know that
697  // %Y = mul nsw i16 %X, C
698  // %Z = add nsw i16 %Y, %X
699  // =>
700  // %Z = mul nsw i16 %X, C+1
701  //
702  // iff C+1 isn't INT_MIN
703  const APInt *CInt;
704  if (match(V, m_APInt(CInt))) {
705  if (!CInt->isMinSignedValue())
706  BO->setHasNoSignedWrap(HasNSW);
707  }
708 
709  // nuw can be propagated with any constant or nuw value.
710  BO->setHasNoUnsignedWrap(HasNUW);
711  }
712  }
713  }
714  }
715  return SimplifiedInst;
716 }
717 
718 /// This tries to simplify binary operations which some other binary operation
719 /// distributes over either by factorizing out common terms
720 /// (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this results in
721 /// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win).
722 /// Returns the simplified value, or null if it didn't simplify.
724  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
725  BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
726  BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
727  Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
728 
729  {
730  // Factorization.
731  Value *A, *B, *C, *D;
732  Instruction::BinaryOps LHSOpcode, RHSOpcode;
733  if (Op0)
734  LHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op0, A, B);
735  if (Op1)
736  RHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op1, C, D);
737 
738  // The instruction has the form "(A op' B) op (C op' D)". Try to factorize
739  // a common term.
740  if (Op0 && Op1 && LHSOpcode == RHSOpcode)
741  if (Value *V = tryFactorization(I, LHSOpcode, A, B, C, D))
742  return V;
743 
744  // The instruction has the form "(A op' B) op (C)". Try to factorize common
745  // term.
746  if (Op0)
747  if (Value *Ident = getIdentityValue(LHSOpcode, RHS))
748  if (Value *V = tryFactorization(I, LHSOpcode, A, B, RHS, Ident))
749  return V;
750 
751  // The instruction has the form "(B) op (C op' D)". Try to factorize common
752  // term.
753  if (Op1)
754  if (Value *Ident = getIdentityValue(RHSOpcode, LHS))
755  if (Value *V = tryFactorization(I, RHSOpcode, LHS, Ident, C, D))
756  return V;
757  }
758 
759  // Expansion.
760  if (Op0 && rightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) {
761  // The instruction has the form "(A op' B) op C". See if expanding it out
762  // to "(A op C) op' (B op C)" results in simplifications.
763  Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
764  Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'
765 
766  // Disable the use of undef because it's not safe to distribute undef.
767  auto SQDistributive = SQ.getWithInstruction(&I).getWithoutUndef();
768  Value *L = SimplifyBinOp(TopLevelOpcode, A, C, SQDistributive);
769  Value *R = SimplifyBinOp(TopLevelOpcode, B, C, SQDistributive);
770 
771  // Do "A op C" and "B op C" both simplify?
772  if (L && R) {
773  // They do! Return "L op' R".
774  ++NumExpand;
775  C = Builder.CreateBinOp(InnerOpcode, L, R);
776  C->takeName(&I);
777  return C;
778  }
779 
780  // Does "A op C" simplify to the identity value for the inner opcode?
781  if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {
782  // They do! Return "B op C".
783  ++NumExpand;
784  C = Builder.CreateBinOp(TopLevelOpcode, B, C);
785  C->takeName(&I);
786  return C;
787  }
788 
789  // Does "B op C" simplify to the identity value for the inner opcode?
790  if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
791  // They do! Return "A op C".
792  ++NumExpand;
793  C = Builder.CreateBinOp(TopLevelOpcode, A, C);
794  C->takeName(&I);
795  return C;
796  }
797  }
798 
799  if (Op1 && leftDistributesOverRight(TopLevelOpcode, Op1->getOpcode())) {
800  // The instruction has the form "A op (B op' C)". See if expanding it out
801  // to "(A op B) op' (A op C)" results in simplifications.
802  Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
803  Instruction::BinaryOps InnerOpcode = Op1->getOpcode(); // op'
804 
805  // Disable the use of undef because it's not safe to distribute undef.
806  auto SQDistributive = SQ.getWithInstruction(&I).getWithoutUndef();
807  Value *L = SimplifyBinOp(TopLevelOpcode, A, B, SQDistributive);
808  Value *R = SimplifyBinOp(TopLevelOpcode, A, C, SQDistributive);
809 
810  // Do "A op B" and "A op C" both simplify?
811  if (L && R) {
812  // They do! Return "L op' R".
813  ++NumExpand;
814  A = Builder.CreateBinOp(InnerOpcode, L, R);
815  A->takeName(&I);
816  return A;
817  }
818 
819  // Does "A op B" simplify to the identity value for the inner opcode?
820  if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {
821  // They do! Return "A op C".
822  ++NumExpand;
823  A = Builder.CreateBinOp(TopLevelOpcode, A, C);
824  A->takeName(&I);
825  return A;
826  }
827 
828  // Does "A op C" simplify to the identity value for the inner opcode?
829  if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
830  // They do! Return "A op B".
831  ++NumExpand;
832  A = Builder.CreateBinOp(TopLevelOpcode, A, B);
833  A->takeName(&I);
834  return A;
835  }
836  }
837 
838  return SimplifySelectsFeedingBinaryOp(I, LHS, RHS);
839 }
840 
842  Value *LHS,
843  Value *RHS) {
844  Value *A, *B, *C, *D, *E, *F;
845  bool LHSIsSelect = match(LHS, m_Select(m_Value(A), m_Value(B), m_Value(C)));
846  bool RHSIsSelect = match(RHS, m_Select(m_Value(D), m_Value(E), m_Value(F)));
847  if (!LHSIsSelect && !RHSIsSelect)
848  return nullptr;
849 
850  FastMathFlags FMF;
852  if (isa<FPMathOperator>(&I)) {
853  FMF = I.getFastMathFlags();
854  Builder.setFastMathFlags(FMF);
855  }
856 
857  Instruction::BinaryOps Opcode = I.getOpcode();
859 
860  Value *Cond, *True = nullptr, *False = nullptr;
861  if (LHSIsSelect && RHSIsSelect && A == D) {
862  // (A ? B : C) op (A ? E : F) -> A ? (B op E) : (C op F)
863  Cond = A;
864  True = SimplifyBinOp(Opcode, B, E, FMF, Q);
865  False = SimplifyBinOp(Opcode, C, F, FMF, Q);
866 
867  if (LHS->hasOneUse() && RHS->hasOneUse()) {
868  if (False && !True)
869  True = Builder.CreateBinOp(Opcode, B, E);
870  else if (True && !False)
871  False = Builder.CreateBinOp(Opcode, C, F);
872  }
873  } else if (LHSIsSelect && LHS->hasOneUse()) {
874  // (A ? B : C) op Y -> A ? (B op Y) : (C op Y)
875  Cond = A;
876  True = SimplifyBinOp(Opcode, B, RHS, FMF, Q);
877  False = SimplifyBinOp(Opcode, C, RHS, FMF, Q);
878  } else if (RHSIsSelect && RHS->hasOneUse()) {
879  // X op (D ? E : F) -> D ? (X op E) : (X op F)
880  Cond = D;
881  True = SimplifyBinOp(Opcode, LHS, E, FMF, Q);
882  False = SimplifyBinOp(Opcode, LHS, F, FMF, Q);
883  }
884 
885  if (!True || !False)
886  return nullptr;
887 
888  Value *SI = Builder.CreateSelect(Cond, True, False);
889  SI->takeName(&I);
890  return SI;
891 }
892 
893 /// Freely adapt every user of V as-if V was changed to !V.
894 /// WARNING: only if canFreelyInvertAllUsersOf() said this can be done.
895 void InstCombinerImpl::freelyInvertAllUsersOf(Value *I) {
896  for (User *U : I->users()) {
897  switch (cast<Instruction>(U)->getOpcode()) {
898  case Instruction::Select: {
899  auto *SI = cast<SelectInst>(U);
900  SI->swapValues();
901  SI->swapProfMetadata();
902  break;
903  }
904  case Instruction::Br:
905  cast<BranchInst>(U)->swapSuccessors(); // swaps prof metadata too
906  break;
907  case Instruction::Xor:
908  replaceInstUsesWith(cast<Instruction>(*U), I);
909  break;
910  default:
911  llvm_unreachable("Got unexpected user - out of sync with "
912  "canFreelyInvertAllUsersOf() ?");
913  }
914  }
915 }
916 
917 /// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a
918 /// constant zero (which is the 'negate' form).
919 Value *InstCombinerImpl::dyn_castNegVal(Value *V) const {
920  Value *NegV;
921  if (match(V, m_Neg(m_Value(NegV))))
922  return NegV;
923 
924  // Constants can be considered to be negated values if they can be folded.
925  if (ConstantInt *C = dyn_cast<ConstantInt>(V))
926  return ConstantExpr::getNeg(C);
927 
928  if (ConstantDataVector *C = dyn_cast<ConstantDataVector>(V))
929  if (C->getType()->getElementType()->isIntegerTy())
930  return ConstantExpr::getNeg(C);
931 
932  if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) {
933  for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
934  Constant *Elt = CV->getAggregateElement(i);
935  if (!Elt)
936  return nullptr;
937 
938  if (isa<UndefValue>(Elt))
939  continue;
940 
941  if (!isa<ConstantInt>(Elt))
942  return nullptr;
943  }
944  return ConstantExpr::getNeg(CV);
945  }
946 
947  // Negate integer vector splats.
948  if (auto *CV = dyn_cast<Constant>(V))
949  if (CV->getType()->isVectorTy() &&
950  CV->getType()->getScalarType()->isIntegerTy() && CV->getSplatValue())
951  return ConstantExpr::getNeg(CV);
952 
953  return nullptr;
954 }
955 
958  if (auto *Cast = dyn_cast<CastInst>(&I))
959  return Builder.CreateCast(Cast->getOpcode(), SO, I.getType());
960 
961  if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
962  assert(canConstantFoldCallTo(II, cast<Function>(II->getCalledOperand())) &&
963  "Expected constant-foldable intrinsic");
964  Intrinsic::ID IID = II->getIntrinsicID();
965  if (II->getNumArgOperands() == 1)
966  return Builder.CreateUnaryIntrinsic(IID, SO);
967 
968  // This works for real binary ops like min/max (where we always expect the
969  // constant operand to be canonicalized as op1) and unary ops with a bonus
970  // constant argument like ctlz/cttz.
971  // TODO: Handle non-commutative binary intrinsics as below for binops.
972  assert(II->getNumArgOperands() == 2 && "Expected binary intrinsic");
973  assert(isa<Constant>(II->getArgOperand(1)) && "Expected constant operand");
974  return Builder.CreateBinaryIntrinsic(IID, SO, II->getArgOperand(1));
975  }
976 
977  assert(I.isBinaryOp() && "Unexpected opcode for select folding");
978 
979  // Figure out if the constant is the left or the right argument.
980  bool ConstIsRHS = isa<Constant>(I.getOperand(1));
981  Constant *ConstOperand = cast<Constant>(I.getOperand(ConstIsRHS));
982 
983  if (auto *SOC = dyn_cast<Constant>(SO)) {
984  if (ConstIsRHS)
985  return ConstantExpr::get(I.getOpcode(), SOC, ConstOperand);
986  return ConstantExpr::get(I.getOpcode(), ConstOperand, SOC);
987  }
988 
989  Value *Op0 = SO, *Op1 = ConstOperand;
990  if (!ConstIsRHS)
991  std::swap(Op0, Op1);
992 
993  auto *BO = cast<BinaryOperator>(&I);
994  Value *RI = Builder.CreateBinOp(BO->getOpcode(), Op0, Op1,
995  SO->getName() + ".op");
996  auto *FPInst = dyn_cast<Instruction>(RI);
997  if (FPInst && isa<FPMathOperator>(FPInst))
998  FPInst->copyFastMathFlags(BO);
999  return RI;
1000 }
1001 
1003  SelectInst *SI) {
1004  // Don't modify shared select instructions.
1005  if (!SI->hasOneUse())
1006  return nullptr;
1007 
1008  Value *TV = SI->getTrueValue();
1009  Value *FV = SI->getFalseValue();
1010  if (!(isa<Constant>(TV) || isa<Constant>(FV)))
1011  return nullptr;
1012 
1013  // Bool selects with constant operands can be folded to logical ops.
1014  if (SI->getType()->isIntOrIntVectorTy(1))
1015  return nullptr;
1016 
1017  // If it's a bitcast involving vectors, make sure it has the same number of
1018  // elements on both sides.
1019  if (auto *BC = dyn_cast<BitCastInst>(&Op)) {
1020  VectorType *DestTy = dyn_cast<VectorType>(BC->getDestTy());
1021  VectorType *SrcTy = dyn_cast<VectorType>(BC->getSrcTy());
1022 
1023  // Verify that either both or neither are vectors.
1024  if ((SrcTy == nullptr) != (DestTy == nullptr))
1025  return nullptr;
1026 
1027  // If vectors, verify that they have the same number of elements.
1028  if (SrcTy && SrcTy->getElementCount() != DestTy->getElementCount())
1029  return nullptr;
1030  }
1031 
1032  // Test if a CmpInst instruction is used exclusively by a select as
1033  // part of a minimum or maximum operation. If so, refrain from doing
1034  // any other folding. This helps out other analyses which understand
1035  // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
1036  // and CodeGen. And in this case, at least one of the comparison
1037  // operands has at least one user besides the compare (the select),
1038  // which would often largely negate the benefit of folding anyway.
1039  if (auto *CI = dyn_cast<CmpInst>(SI->getCondition())) {
1040  if (CI->hasOneUse()) {
1041  Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
1042 
1043  // FIXME: This is a hack to avoid infinite looping with min/max patterns.
1044  // We have to ensure that vector constants that only differ with
1045  // undef elements are treated as equivalent.
1046  auto areLooselyEqual = [](Value *A, Value *B) {
1047  if (A == B)
1048  return true;
1049 
1050  // Test for vector constants.
1051  Constant *ConstA, *ConstB;
1052  if (!match(A, m_Constant(ConstA)) || !match(B, m_Constant(ConstB)))
1053  return false;
1054 
1055  // TODO: Deal with FP constants?
1056  if (!A->getType()->isIntOrIntVectorTy() || A->getType() != B->getType())
1057  return false;
1058 
1059  // Compare for equality including undefs as equal.
1060  auto *Cmp = ConstantExpr::getCompare(ICmpInst::ICMP_EQ, ConstA, ConstB);
1061  const APInt *C;
1062  return match(Cmp, m_APIntAllowUndef(C)) && C->isOneValue();
1063  };
1064 
1065  if ((areLooselyEqual(TV, Op0) && areLooselyEqual(FV, Op1)) ||
1066  (areLooselyEqual(FV, Op0) && areLooselyEqual(TV, Op1)))
1067  return nullptr;
1068  }
1069  }
1070 
1073  return SelectInst::Create(SI->getCondition(), NewTV, NewFV, "", nullptr, SI);
1074 }
1075 
1078  bool ConstIsRHS = isa<Constant>(I->getOperand(1));
1079  Constant *C = cast<Constant>(I->getOperand(ConstIsRHS));
1080 
1081  if (auto *InC = dyn_cast<Constant>(InV)) {
1082  if (ConstIsRHS)
1083  return ConstantExpr::get(I->getOpcode(), InC, C);
1084  return ConstantExpr::get(I->getOpcode(), C, InC);
1085  }
1086 
1087  Value *Op0 = InV, *Op1 = C;
1088  if (!ConstIsRHS)
1089  std::swap(Op0, Op1);
1090 
1091  Value *RI = Builder.CreateBinOp(I->getOpcode(), Op0, Op1, "phi.bo");
1092  auto *FPInst = dyn_cast<Instruction>(RI);
1093  if (FPInst && isa<FPMathOperator>(FPInst))
1094  FPInst->copyFastMathFlags(I);
1095  return RI;
1096 }
1097 
1099  unsigned NumPHIValues = PN->getNumIncomingValues();
1100  if (NumPHIValues == 0)
1101  return nullptr;
1102 
1103  // We normally only transform phis with a single use. However, if a PHI has
1104  // multiple uses and they are all the same operation, we can fold *all* of the
1105  // uses into the PHI.
1106  if (!PN->hasOneUse()) {
1107  // Walk the use list for the instruction, comparing them to I.
1108  for (User *U : PN->users()) {
1109  Instruction *UI = cast<Instruction>(U);
1110  if (UI != &I && !I.isIdenticalTo(UI))
1111  return nullptr;
1112  }
1113  // Otherwise, we can replace *all* users with the new PHI we form.
1114  }
1115 
1116  // Check to see if all of the operands of the PHI are simple constants
1117  // (constantint/constantfp/undef). If there is one non-constant value,
1118  // remember the BB it is in. If there is more than one or if *it* is a PHI,
1119  // bail out. We don't do arbitrary constant expressions here because moving
1120  // their computation can be expensive without a cost model.
1121  BasicBlock *NonConstBB = nullptr;
1122  for (unsigned i = 0; i != NumPHIValues; ++i) {
1123  Value *InVal = PN->getIncomingValue(i);
1124  // If I is a freeze instruction, count undef as a non-constant.
1125  if (match(InVal, m_ImmConstant()) &&
1126  (!isa<FreezeInst>(I) || isGuaranteedNotToBeUndefOrPoison(InVal)))
1127  continue;
1128 
1129  if (isa<PHINode>(InVal)) return nullptr; // Itself a phi.
1130  if (NonConstBB) return nullptr; // More than one non-const value.
1131 
1132  NonConstBB = PN->getIncomingBlock(i);
1133 
1134  // If the InVal is an invoke at the end of the pred block, then we can't
1135  // insert a computation after it without breaking the edge.
1136  if (isa<InvokeInst>(InVal))
1137  if (cast<Instruction>(InVal)->getParent() == NonConstBB)
1138  return nullptr;
1139 
1140  // If the incoming non-constant value is in I's block, we will remove one
1141  // instruction, but insert another equivalent one, leading to infinite
1142  // instcombine.
1143  if (isPotentiallyReachable(I.getParent(), NonConstBB, nullptr, &DT, LI))
1144  return nullptr;
1145  }
1146 
1147  // If there is exactly one non-constant value, we can insert a copy of the
1148  // operation in that block. However, if this is a critical edge, we would be
1149  // inserting the computation on some other paths (e.g. inside a loop). Only
1150  // do this if the pred block is unconditionally branching into the phi block.
1151  // Also, make sure that the pred block is not dead code.
1152  if (NonConstBB != nullptr) {
1153  BranchInst *BI = dyn_cast<BranchInst>(NonConstBB->getTerminator());
1154  if (!BI || !BI->isUnconditional() || !DT.isReachableFromEntry(NonConstBB))
1155  return nullptr;
1156  }
1157 
1158  // Okay, we can do the transformation: create the new PHI node.
1159  PHINode *NewPN = PHINode::Create(I.getType(), PN->getNumIncomingValues());
1160  InsertNewInstBefore(NewPN, *PN);
1161  NewPN->takeName(PN);
1162 
1163  // If we are going to have to insert a new computation, do so right before the
1164  // predecessor's terminator.
1165  if (NonConstBB)
1166  Builder.SetInsertPoint(NonConstBB->getTerminator());
1167 
1168  // Next, add all of the operands to the PHI.
1169  if (SelectInst *SI = dyn_cast<SelectInst>(&I)) {
1170  // We only currently try to fold the condition of a select when it is a phi,
1171  // not the true/false values.
1172  Value *TrueV = SI->getTrueValue();
1173  Value *FalseV = SI->getFalseValue();
1174  BasicBlock *PhiTransBB = PN->getParent();
1175  for (unsigned i = 0; i != NumPHIValues; ++i) {
1176  BasicBlock *ThisBB = PN->getIncomingBlock(i);
1177  Value *TrueVInPred = TrueV->DoPHITranslation(PhiTransBB, ThisBB);
1178  Value *FalseVInPred = FalseV->DoPHITranslation(PhiTransBB, ThisBB);
1179  Value *InV = nullptr;
1180  // Beware of ConstantExpr: it may eventually evaluate to getNullValue,
1181  // even if currently isNullValue gives false.
1182  Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i));
1183  // For vector constants, we cannot use isNullValue to fold into
1184  // FalseVInPred versus TrueVInPred. When we have individual nonzero
1185  // elements in the vector, we will incorrectly fold InC to
1186  // `TrueVInPred`.
1187  if (InC && isa<ConstantInt>(InC))
1188  InV = InC->isNullValue() ? FalseVInPred : TrueVInPred;
1189  else {
1190  // Generate the select in the same block as PN's current incoming block.
1191  // Note: ThisBB need not be the NonConstBB because vector constants
1192  // which are constants by definition are handled here.
1193  // FIXME: This can lead to an increase in IR generation because we might
1194  // generate selects for vector constant phi operand, that could not be
1195  // folded to TrueVInPred or FalseVInPred as done for ConstantInt. For
1196  // non-vector phis, this transformation was always profitable because
1197  // the select would be generated exactly once in the NonConstBB.
1198  Builder.SetInsertPoint(ThisBB->getTerminator());
1199  InV = Builder.CreateSelect(PN->getIncomingValue(i), TrueVInPred,
1200  FalseVInPred, "phi.sel");
1201  }
1202  NewPN->addIncoming(InV, ThisBB);
1203  }
1204  } else if (CmpInst *CI = dyn_cast<CmpInst>(&I)) {
1205  Constant *C = cast<Constant>(I.getOperand(1));
1206  for (unsigned i = 0; i != NumPHIValues; ++i) {
1207  Value *InV = nullptr;
1208  if (auto *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))
1209  InV = ConstantExpr::getCompare(CI->getPredicate(), InC, C);
1210  else
1211  InV = Builder.CreateCmp(CI->getPredicate(), PN->getIncomingValue(i),
1212  C, "phi.cmp");
1213  NewPN->addIncoming(InV, PN->getIncomingBlock(i));
1214  }
1215  } else if (auto *BO = dyn_cast<BinaryOperator>(&I)) {
1216  for (unsigned i = 0; i != NumPHIValues; ++i) {
1218  Builder);
1219  NewPN->addIncoming(InV, PN->getIncomingBlock(i));
1220  }
1221  } else if (isa<FreezeInst>(&I)) {
1222  for (unsigned i = 0; i != NumPHIValues; ++i) {
1223  Value *InV;
1224  if (NonConstBB == PN->getIncomingBlock(i))
1225  InV = Builder.CreateFreeze(PN->getIncomingValue(i), "phi.fr");
1226  else
1227  InV = PN->getIncomingValue(i);
1228  NewPN->addIncoming(InV, PN->getIncomingBlock(i));
1229  }
1230  } else {
1231  CastInst *CI = cast<CastInst>(&I);
1232  Type *RetTy = CI->getType();
1233  for (unsigned i = 0; i != NumPHIValues; ++i) {
1234  Value *InV;
1235  if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))
1236  InV = ConstantExpr::getCast(CI->getOpcode(), InC, RetTy);
1237  else
1238  InV = Builder.CreateCast(CI->getOpcode(), PN->getIncomingValue(i),
1239  I.getType(), "phi.cast");
1240  NewPN->addIncoming(InV, PN->getIncomingBlock(i));
1241  }
1242  }
1243 
1244  for (User *U : make_early_inc_range(PN->users())) {
1245  Instruction *User = cast<Instruction>(U);
1246  if (User == &I) continue;
1247  replaceInstUsesWith(*User, NewPN);
1248  eraseInstFromFunction(*User);
1249  }
1250  return replaceInstUsesWith(I, NewPN);
1251 }
1252 
1254  if (!isa<Constant>(I.getOperand(1)))
1255  return nullptr;
1256 
1257  if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {
1258  if (Instruction *NewSel = FoldOpIntoSelect(I, Sel))
1259  return NewSel;
1260  } else if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) {
1261  if (Instruction *NewPhi = foldOpIntoPhi(I, PN))
1262  return NewPhi;
1263  }
1264  return nullptr;
1265 }
1266 
1267 /// Given a pointer type and a constant offset, determine whether or not there
1268 /// is a sequence of GEP indices into the pointed type that will land us at the
1269 /// specified offset. If so, fill them into NewIndices and return the resultant
1270 /// element type, otherwise return null.
1271 Type *
1272 InstCombinerImpl::FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
1273  SmallVectorImpl<Value *> &NewIndices) {
1274  Type *Ty = PtrTy->getElementType();
1275  if (!Ty->isSized())
1276  return nullptr;
1277 
1278  // Start with the index over the outer type. Note that the type size
1279  // might be zero (even if the offset isn't zero) if the indexed type
1280  // is something like [0 x {int, int}]
1281  Type *IndexTy = DL.getIndexType(PtrTy);
1282  int64_t FirstIdx = 0;
1283  if (int64_t TySize = DL.getTypeAllocSize(Ty)) {
1284  FirstIdx = Offset/TySize;
1285  Offset -= FirstIdx*TySize;
1286 
1287  // Handle hosts where % returns negative instead of values [0..TySize).
1288  if (Offset < 0) {
1289  --FirstIdx;
1290  Offset += TySize;
1291  assert(Offset >= 0);
1292  }
1293  assert((uint64_t)Offset < (uint64_t)TySize && "Out of range offset");
1294  }
1295 
1296  NewIndices.push_back(ConstantInt::get(IndexTy, FirstIdx));
1297 
1298  // Index into the types. If we fail, set OrigBase to null.
1299  while (Offset) {
1300  // Indexing into tail padding between struct/array elements.
1301  if (uint64_t(Offset * 8) >= DL.getTypeSizeInBits(Ty))
1302  return nullptr;
1303 
1304  if (StructType *STy = dyn_cast<StructType>(Ty)) {
1305  const StructLayout *SL = DL.getStructLayout(STy);
1306  assert(Offset < (int64_t)SL->getSizeInBytes() &&
1307  "Offset must stay within the indexed type");
1308 
1309  unsigned Elt = SL->getElementContainingOffset(Offset);
1310  NewIndices.push_back(ConstantInt::get(Type::getInt32Ty(Ty->getContext()),
1311  Elt));
1312 
1313  Offset -= SL->getElementOffset(Elt);
1314  Ty = STy->getElementType(Elt);
1315  } else if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) {
1316  uint64_t EltSize = DL.getTypeAllocSize(AT->getElementType());
1317  assert(EltSize && "Cannot index into a zero-sized array");
1318  NewIndices.push_back(ConstantInt::get(IndexTy,Offset/EltSize));
1319  Offset %= EltSize;
1320  Ty = AT->getElementType();
1321  } else {
1322  // Otherwise, we can't index into the middle of this atomic type, bail.
1323  return nullptr;
1324  }
1325  }
1326 
1327  return Ty;
1328 }
1329 
1331  // If this GEP has only 0 indices, it is the same pointer as
1332  // Src. If Src is not a trivial GEP too, don't combine
1333  // the indices.
1334  if (GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&
1335  !Src.hasOneUse())
1336  return false;
1337  return true;
1338 }
1339 
1340 /// Return a value X such that Val = X * Scale, or null if none.
1341 /// If the multiplication is known not to overflow, then NoSignedWrap is set.
1342 Value *InstCombinerImpl::Descale(Value *Val, APInt Scale, bool &NoSignedWrap) {
1343  assert(isa<IntegerType>(Val->getType()) && "Can only descale integers!");
1344  assert(cast<IntegerType>(Val->getType())->getBitWidth() ==
1345  Scale.getBitWidth() && "Scale not compatible with value!");
1346 
1347  // If Val is zero or Scale is one then Val = Val * Scale.
1348  if (match(Val, m_Zero()) || Scale == 1) {
1349  NoSignedWrap = true;
1350  return Val;
1351  }
1352 
1353  // If Scale is zero then it does not divide Val.
1354  if (Scale.isMinValue())
1355  return nullptr;
1356 
1357  // Look through chains of multiplications, searching for a constant that is
1358  // divisible by Scale. For example, descaling X*(Y*(Z*4)) by a factor of 4
1359  // will find the constant factor 4 and produce X*(Y*Z). Descaling X*(Y*8) by
1360  // a factor of 4 will produce X*(Y*2). The principle of operation is to bore
1361  // down from Val:
1362  //
1363  // Val = M1 * X || Analysis starts here and works down
1364  // M1 = M2 * Y || Doesn't descend into terms with more
1365  // M2 = Z * 4 \/ than one use
1366  //
1367  // Then to modify a term at the bottom:
1368  //
1369  // Val = M1 * X
1370  // M1 = Z * Y || Replaced M2 with Z
1371  //
1372  // Then to work back up correcting nsw flags.
1373 
1374  // Op - the term we are currently analyzing. Starts at Val then drills down.
1375  // Replaced with its descaled value before exiting from the drill down loop.
1376  Value *Op = Val;
1377 
1378  // Parent - initially null, but after drilling down notes where Op came from.
1379  // In the example above, Parent is (Val, 0) when Op is M1, because M1 is the
1380  // 0'th operand of Val.
1381  std::pair<Instruction *, unsigned> Parent;
1382 
1383  // Set if the transform requires a descaling at deeper levels that doesn't
1384  // overflow.
1385  bool RequireNoSignedWrap = false;
1386 
1387  // Log base 2 of the scale. Negative if not a power of 2.
1388  int32_t logScale = Scale.exactLogBase2();
1389 
1390  for (;; Op = Parent.first->getOperand(Parent.second)) { // Drill down
1391  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1392  // If Op is a constant divisible by Scale then descale to the quotient.
1393  APInt Quotient(Scale), Remainder(Scale); // Init ensures right bitwidth.
1394  APInt::sdivrem(CI->getValue(), Scale, Quotient, Remainder);
1395  if (!Remainder.isMinValue())
1396  // Not divisible by Scale.
1397  return nullptr;
1398  // Replace with the quotient in the parent.
1399  Op = ConstantInt::get(CI->getType(), Quotient);
1400  NoSignedWrap = true;
1401  break;
1402  }
1403 
1404  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op)) {
1405  if (BO->getOpcode() == Instruction::Mul) {
1406  // Multiplication.
1407  NoSignedWrap = BO->hasNoSignedWrap();
1408  if (RequireNoSignedWrap && !NoSignedWrap)
1409  return nullptr;
1410 
1411  // There are three cases for multiplication: multiplication by exactly
1412  // the scale, multiplication by a constant different to the scale, and
1413  // multiplication by something else.
1414  Value *LHS = BO->getOperand(0);
1415  Value *RHS = BO->getOperand(1);
1416 
1417  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1418  // Multiplication by a constant.
1419  if (CI->getValue() == Scale) {
1420  // Multiplication by exactly the scale, replace the multiplication
1421  // by its left-hand side in the parent.
1422  Op = LHS;
1423  break;
1424  }
1425 
1426  // Otherwise drill down into the constant.
1427  if (!Op->hasOneUse())
1428  return nullptr;
1429 
1430  Parent = std::make_pair(BO, 1);
1431  continue;
1432  }
1433 
1434  // Multiplication by something else. Drill down into the left-hand side
1435  // since that's where the reassociate pass puts the good stuff.
1436  if (!Op->hasOneUse())
1437  return nullptr;
1438 
1439  Parent = std::make_pair(BO, 0);
1440  continue;
1441  }
1442 
1443  if (logScale > 0 && BO->getOpcode() == Instruction::Shl &&
1444  isa<ConstantInt>(BO->getOperand(1))) {
1445  // Multiplication by a power of 2.
1446  NoSignedWrap = BO->hasNoSignedWrap();
1447  if (RequireNoSignedWrap && !NoSignedWrap)
1448  return nullptr;
1449 
1450  Value *LHS = BO->getOperand(0);
1451  int32_t Amt = cast<ConstantInt>(BO->getOperand(1))->
1452  getLimitedValue(Scale.getBitWidth());
1453  // Op = LHS << Amt.
1454 
1455  if (Amt == logScale) {
1456  // Multiplication by exactly the scale, replace the multiplication
1457  // by its left-hand side in the parent.
1458  Op = LHS;
1459  break;
1460  }
1461  if (Amt < logScale || !Op->hasOneUse())
1462  return nullptr;
1463 
1464  // Multiplication by more than the scale. Reduce the multiplying amount
1465  // by the scale in the parent.
1466  Parent = std::make_pair(BO, 1);
1467  Op = ConstantInt::get(BO->getType(), Amt - logScale);
1468  break;
1469  }
1470  }
1471 
1472  if (!Op->hasOneUse())
1473  return nullptr;
1474 
1475  if (CastInst *Cast = dyn_cast<CastInst>(Op)) {
1476  if (Cast->getOpcode() == Instruction::SExt) {
1477  // Op is sign-extended from a smaller type, descale in the smaller type.
1478  unsigned SmallSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1479  APInt SmallScale = Scale.trunc(SmallSize);
1480  // Suppose Op = sext X, and we descale X as Y * SmallScale. We want to
1481  // descale Op as (sext Y) * Scale. In order to have
1482  // sext (Y * SmallScale) = (sext Y) * Scale
1483  // some conditions need to hold however: SmallScale must sign-extend to
1484  // Scale and the multiplication Y * SmallScale should not overflow.
1485  if (SmallScale.sext(Scale.getBitWidth()) != Scale)
1486  // SmallScale does not sign-extend to Scale.
1487  return nullptr;
1488  assert(SmallScale.exactLogBase2() == logScale);
1489  // Require that Y * SmallScale must not overflow.
1490  RequireNoSignedWrap = true;
1491 
1492  // Drill down through the cast.
1493  Parent = std::make_pair(Cast, 0);
1494  Scale = SmallScale;
1495  continue;
1496  }
1497 
1498  if (Cast->getOpcode() == Instruction::Trunc) {
1499  // Op is truncated from a larger type, descale in the larger type.
1500  // Suppose Op = trunc X, and we descale X as Y * sext Scale. Then
1501  // trunc (Y * sext Scale) = (trunc Y) * Scale
1502  // always holds. However (trunc Y) * Scale may overflow even if
1503  // trunc (Y * sext Scale) does not, so nsw flags need to be cleared
1504  // from this point up in the expression (see later).
1505  if (RequireNoSignedWrap)
1506  return nullptr;
1507 
1508  // Drill down through the cast.
1509  unsigned LargeSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1510  Parent = std::make_pair(Cast, 0);
1511  Scale = Scale.sext(LargeSize);
1512  if (logScale + 1 == (int32_t)Cast->getType()->getPrimitiveSizeInBits())
1513  logScale = -1;
1514  assert(Scale.exactLogBase2() == logScale);
1515  continue;
1516  }
1517  }
1518 
1519  // Unsupported expression, bail out.
1520  return nullptr;
1521  }
1522 
1523  // If Op is zero then Val = Op * Scale.
1524  if (match(Op, m_Zero())) {
1525  NoSignedWrap = true;
1526  return Op;
1527  }
1528 
1529  // We know that we can successfully descale, so from here on we can safely
1530  // modify the IR. Op holds the descaled version of the deepest term in the
1531  // expression. NoSignedWrap is 'true' if multiplying Op by Scale is known
1532  // not to overflow.
1533 
1534  if (!Parent.first)
1535  // The expression only had one term.
1536  return Op;
1537 
1538  // Rewrite the parent using the descaled version of its operand.
1539  assert(Parent.first->hasOneUse() && "Drilled down when more than one use!");
1540  assert(Op != Parent.first->getOperand(Parent.second) &&
1541  "Descaling was a no-op?");
1542  replaceOperand(*Parent.first, Parent.second, Op);
1543  Worklist.push(Parent.first);
1544 
1545  // Now work back up the expression correcting nsw flags. The logic is based
1546  // on the following observation: if X * Y is known not to overflow as a signed
1547  // multiplication, and Y is replaced by a value Z with smaller absolute value,
1548  // then X * Z will not overflow as a signed multiplication either. As we work
1549  // our way up, having NoSignedWrap 'true' means that the descaled value at the
1550  // current level has strictly smaller absolute value than the original.
1551  Instruction *Ancestor = Parent.first;
1552  do {
1553  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Ancestor)) {
1554  // If the multiplication wasn't nsw then we can't say anything about the
1555  // value of the descaled multiplication, and we have to clear nsw flags
1556  // from this point on up.
1557  bool OpNoSignedWrap = BO->hasNoSignedWrap();
1558  NoSignedWrap &= OpNoSignedWrap;
1559  if (NoSignedWrap != OpNoSignedWrap) {
1560  BO->setHasNoSignedWrap(NoSignedWrap);
1561  Worklist.push(Ancestor);
1562  }
1563  } else if (Ancestor->getOpcode() == Instruction::Trunc) {
1564  // The fact that the descaled input to the trunc has smaller absolute
1565  // value than the original input doesn't tell us anything useful about
1566  // the absolute values of the truncations.
1567  NoSignedWrap = false;
1568  }
1569  assert((Ancestor->getOpcode() != Instruction::SExt || NoSignedWrap) &&
1570  "Failed to keep proper track of nsw flags while drilling down?");
1571 
1572  if (Ancestor == Val)
1573  // Got to the top, all done!
1574  return Val;
1575 
1576  // Move up one level in the expression.
1577  assert(Ancestor->hasOneUse() && "Drilled down when more than one use!");
1578  Ancestor = Ancestor->user_back();
1579  } while (true);
1580 }
1581 
1583  if (!isa<VectorType>(Inst.getType()))
1584  return nullptr;
1585 
1586  BinaryOperator::BinaryOps Opcode = Inst.getOpcode();
1587  Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1);
1588  assert(cast<VectorType>(LHS->getType())->getElementCount() ==
1589  cast<VectorType>(Inst.getType())->getElementCount());
1590  assert(cast<VectorType>(RHS->getType())->getElementCount() ==
1591  cast<VectorType>(Inst.getType())->getElementCount());
1592 
1593  // If both operands of the binop are vector concatenations, then perform the
1594  // narrow binop on each pair of the source operands followed by concatenation
1595  // of the results.
1596  Value *L0, *L1, *R0, *R1;
1598  if (match(LHS, m_Shuffle(m_Value(L0), m_Value(L1), m_Mask(Mask))) &&
1599  match(RHS, m_Shuffle(m_Value(R0), m_Value(R1), m_SpecificMask(Mask))) &&
1600  LHS->hasOneUse() && RHS->hasOneUse() &&
1601  cast<ShuffleVectorInst>(LHS)->isConcat() &&
1602  cast<ShuffleVectorInst>(RHS)->isConcat()) {
1603  // This transform does not have the speculative execution constraint as
1604  // below because the shuffle is a concatenation. The new binops are
1605  // operating on exactly the same elements as the existing binop.
1606  // TODO: We could ease the mask requirement to allow different undef lanes,
1607  // but that requires an analysis of the binop-with-undef output value.
1608  Value *NewBO0 = Builder.CreateBinOp(Opcode, L0, R0);
1609  if (auto *BO = dyn_cast<BinaryOperator>(NewBO0))
1610  BO->copyIRFlags(&Inst);
1611  Value *NewBO1 = Builder.CreateBinOp(Opcode, L1, R1);
1612  if (auto *BO = dyn_cast<BinaryOperator>(NewBO1))
1613  BO->copyIRFlags(&Inst);
1614  return new ShuffleVectorInst(NewBO0, NewBO1, Mask);
1615  }
1616 
1617  // It may not be safe to reorder shuffles and things like div, urem, etc.
1618  // because we may trap when executing those ops on unknown vector elements.
1619  // See PR20059.
1620  if (!isSafeToSpeculativelyExecute(&Inst))
1621  return nullptr;
1622 
1623  auto createBinOpShuffle = [&](Value *X, Value *Y, ArrayRef<int> M) {
1624  Value *XY = Builder.CreateBinOp(Opcode, X, Y);
1625  if (auto *BO = dyn_cast<BinaryOperator>(XY))
1626  BO->copyIRFlags(&Inst);
1627  return new ShuffleVectorInst(XY, UndefValue::get(XY->getType()), M);
1628  };
1629 
1630  // If both arguments of the binary operation are shuffles that use the same
1631  // mask and shuffle within a single vector, move the shuffle after the binop.
1632  Value *V1, *V2;
1633  if (match(LHS, m_Shuffle(m_Value(V1), m_Undef(), m_Mask(Mask))) &&
1635  V1->getType() == V2->getType() &&
1636  (LHS->hasOneUse() || RHS->hasOneUse() || LHS == RHS)) {
1637  // Op(shuffle(V1, Mask), shuffle(V2, Mask)) -> shuffle(Op(V1, V2), Mask)
1638  return createBinOpShuffle(V1, V2, Mask);
1639  }
1640 
1641  // If both arguments of a commutative binop are select-shuffles that use the
1642  // same mask with commuted operands, the shuffles are unnecessary.
1643  if (Inst.isCommutative() &&
1644  match(LHS, m_Shuffle(m_Value(V1), m_Value(V2), m_Mask(Mask))) &&
1645  match(RHS,
1647  auto *LShuf = cast<ShuffleVectorInst>(LHS);
1648  auto *RShuf = cast<ShuffleVectorInst>(RHS);
1649  // TODO: Allow shuffles that contain undefs in the mask?
1650  // That is legal, but it reduces undef knowledge.
1651  // TODO: Allow arbitrary shuffles by shuffling after binop?
1652  // That might be legal, but we have to deal with poison.
1653  if (LShuf->isSelect() &&
1654  !is_contained(LShuf->getShuffleMask(), UndefMaskElem) &&
1655  RShuf->isSelect() &&
1656  !is_contained(RShuf->getShuffleMask(), UndefMaskElem)) {
1657  // Example:
1658  // LHS = shuffle V1, V2, <0, 5, 6, 3>
1659  // RHS = shuffle V2, V1, <0, 5, 6, 3>
1660  // LHS + RHS --> (V10+V20, V21+V11, V22+V12, V13+V23) --> V1 + V2
1661  Instruction *NewBO = BinaryOperator::Create(Opcode, V1, V2);
1662  NewBO->copyIRFlags(&Inst);
1663  return NewBO;
1664  }
1665  }
1666 
1667  // If one argument is a shuffle within one vector and the other is a constant,
1668  // try moving the shuffle after the binary operation. This canonicalization
1669  // intends to move shuffles closer to other shuffles and binops closer to
1670  // other binops, so they can be folded. It may also enable demanded elements
1671  // transforms.
1672  Constant *C;
1673  auto *InstVTy = dyn_cast<FixedVectorType>(Inst.getType());
1674  if (InstVTy &&
1675  match(&Inst,
1677  m_ImmConstant(C))) &&
1678  cast<FixedVectorType>(V1->getType())->getNumElements() <=
1679  InstVTy->getNumElements()) {
1680  assert(InstVTy->getScalarType() == V1->getType()->getScalarType() &&
1681  "Shuffle should not change scalar type");
1682 
1683  // Find constant NewC that has property:
1684  // shuffle(NewC, ShMask) = C
1685  // If such constant does not exist (example: ShMask=<0,0> and C=<1,2>)
1686  // reorder is not possible. A 1-to-1 mapping is not required. Example:
1687  // ShMask = <1,1,2,2> and C = <5,5,6,6> --> NewC = <undef,5,6,undef>
1688  bool ConstOp1 = isa<Constant>(RHS);
1689  ArrayRef<int> ShMask = Mask;
1690  unsigned SrcVecNumElts =
1691  cast<FixedVectorType>(V1->getType())->getNumElements();
1692  UndefValue *UndefScalar = UndefValue::get(C->getType()->getScalarType());
1693  SmallVector<Constant *, 16> NewVecC(SrcVecNumElts, UndefScalar);
1694  bool MayChange = true;
1695  unsigned NumElts = InstVTy->getNumElements();
1696  for (unsigned I = 0; I < NumElts; ++I) {
1697  Constant *CElt = C->getAggregateElement(I);
1698  if (ShMask[I] >= 0) {
1699  assert(ShMask[I] < (int)NumElts && "Not expecting narrowing shuffle");
1700  Constant *NewCElt = NewVecC[ShMask[I]];
1701  // Bail out if:
1702  // 1. The constant vector contains a constant expression.
1703  // 2. The shuffle needs an element of the constant vector that can't
1704  // be mapped to a new constant vector.
1705  // 3. This is a widening shuffle that copies elements of V1 into the
1706  // extended elements (extending with undef is allowed).
1707  if (!CElt || (!isa<UndefValue>(NewCElt) && NewCElt != CElt) ||
1708  I >= SrcVecNumElts) {
1709  MayChange = false;
1710  break;
1711  }
1712  NewVecC[ShMask[I]] = CElt;
1713  }
1714  // If this is a widening shuffle, we must be able to extend with undef
1715  // elements. If the original binop does not produce an undef in the high
1716  // lanes, then this transform is not safe.
1717  // Similarly for undef lanes due to the shuffle mask, we can only
1718  // transform binops that preserve undef.
1719  // TODO: We could shuffle those non-undef constant values into the
1720  // result by using a constant vector (rather than an undef vector)
1721  // as operand 1 of the new binop, but that might be too aggressive
1722  // for target-independent shuffle creation.
1723  if (I >= SrcVecNumElts || ShMask[I] < 0) {
1724  Constant *MaybeUndef =
1725  ConstOp1 ? ConstantExpr::get(Opcode, UndefScalar, CElt)
1726  : ConstantExpr::get(Opcode, CElt, UndefScalar);
1727  if (!match(MaybeUndef, m_Undef())) {
1728  MayChange = false;
1729  break;
1730  }
1731  }
1732  }
1733  if (MayChange) {
1734  Constant *NewC = ConstantVector::get(NewVecC);
1735  // It may not be safe to execute a binop on a vector with undef elements
1736  // because the entire instruction can be folded to undef or create poison
1737  // that did not exist in the original code.
1738  if (Inst.isIntDivRem() || (Inst.isShift() && ConstOp1))
1739  NewC = getSafeVectorConstantForBinop(Opcode, NewC, ConstOp1);
1740 
1741  // Op(shuffle(V1, Mask), C) -> shuffle(Op(V1, NewC), Mask)
1742  // Op(C, shuffle(V1, Mask)) -> shuffle(Op(NewC, V1), Mask)
1743  Value *NewLHS = ConstOp1 ? V1 : NewC;
1744  Value *NewRHS = ConstOp1 ? NewC : V1;
1745  return createBinOpShuffle(NewLHS, NewRHS, Mask);
1746  }
1747  }
1748 
1749  // Try to reassociate to sink a splat shuffle after a binary operation.
1750  if (Inst.isAssociative() && Inst.isCommutative()) {
1751  // Canonicalize shuffle operand as LHS.
1752  if (isa<ShuffleVectorInst>(RHS))
1753  std::swap(LHS, RHS);
1754 
1755  Value *X;
1756  ArrayRef<int> MaskC;
1757  int SplatIndex;
1758  BinaryOperator *BO;
1759  if (!match(LHS,
1760  m_OneUse(m_Shuffle(m_Value(X), m_Undef(), m_Mask(MaskC)))) ||
1761  !match(MaskC, m_SplatOrUndefMask(SplatIndex)) ||
1762  X->getType() != Inst.getType() || !match(RHS, m_OneUse(m_BinOp(BO))) ||
1763  BO->getOpcode() != Opcode)
1764  return nullptr;
1765 
1766  // FIXME: This may not be safe if the analysis allows undef elements. By
1767  // moving 'Y' before the splat shuffle, we are implicitly assuming
1768  // that it is not undef/poison at the splat index.
1769  Value *Y, *OtherOp;
1770  if (isSplatValue(BO->getOperand(0), SplatIndex)) {
1771  Y = BO->getOperand(0);
1772  OtherOp = BO->getOperand(1);
1773  } else if (isSplatValue(BO->getOperand(1), SplatIndex)) {
1774  Y = BO->getOperand(1);
1775  OtherOp = BO->getOperand(0);
1776  } else {
1777  return nullptr;
1778  }
1779 
1780  // X and Y are splatted values, so perform the binary operation on those
1781  // values followed by a splat followed by the 2nd binary operation:
1782  // bo (splat X), (bo Y, OtherOp) --> bo (splat (bo X, Y)), OtherOp
1783  Value *NewBO = Builder.CreateBinOp(Opcode, X, Y);
1784  SmallVector<int, 8> NewMask(MaskC.size(), SplatIndex);
1785  Value *NewSplat = Builder.CreateShuffleVector(NewBO, NewMask);
1786  Instruction *R = BinaryOperator::Create(Opcode, NewSplat, OtherOp);
1787 
1788  // Intersect FMF on both new binops. Other (poison-generating) flags are
1789  // dropped to be safe.
1790  if (isa<FPMathOperator>(R)) {
1791  R->copyFastMathFlags(&Inst);
1792  R->andIRFlags(BO);
1793  }
1794  if (auto *NewInstBO = dyn_cast<BinaryOperator>(NewBO))
1795  NewInstBO->copyIRFlags(R);
1796  return R;
1797  }
1798 
1799  return nullptr;
1800 }
1801 
1802 /// Try to narrow the width of a binop if at least 1 operand is an extend of
1803 /// of a value. This requires a potentially expensive known bits check to make
1804 /// sure the narrow op does not overflow.
1805 Instruction *InstCombinerImpl::narrowMathIfNoOverflow(BinaryOperator &BO) {
1806  // We need at least one extended operand.
1807  Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1);
1808 
1809  // If this is a sub, we swap the operands since we always want an extension
1810  // on the RHS. The LHS can be an extension or a constant.
1811  if (BO.getOpcode() == Instruction::Sub)
1812  std::swap(Op0, Op1);
1813 
1814  Value *X;
1815  bool IsSext = match(Op0, m_SExt(m_Value(X)));
1816  if (!IsSext && !match(Op0, m_ZExt(m_Value(X))))
1817  return nullptr;
1818 
1819  // If both operands are the same extension from the same source type and we
1820  // can eliminate at least one (hasOneUse), this might work.
1821  CastInst::CastOps CastOpc = IsSext ? Instruction::SExt : Instruction::ZExt;
1822  Value *Y;
1823  if (!(match(Op1, m_ZExtOrSExt(m_Value(Y))) && X->getType() == Y->getType() &&
1824  cast<Operator>(Op1)->getOpcode() == CastOpc &&
1825  (Op0->hasOneUse() || Op1->hasOneUse()))) {
1826  // If that did not match, see if we have a suitable constant operand.
1827  // Truncating and extending must produce the same constant.
1828  Constant *WideC;
1829  if (!Op0->hasOneUse() || !match(Op1, m_Constant(WideC)))
1830  return nullptr;
1831  Constant *NarrowC = ConstantExpr::getTrunc(WideC, X->getType());
1832  if (ConstantExpr::getCast(CastOpc, NarrowC, BO.getType()) != WideC)
1833  return nullptr;
1834  Y = NarrowC;
1835  }
1836 
1837  // Swap back now that we found our operands.
1838  if (BO.getOpcode() == Instruction::Sub)
1839  std::swap(X, Y);
1840 
1841  // Both operands have narrow versions. Last step: the math must not overflow
1842  // in the narrow width.
1843  if (!willNotOverflow(BO.getOpcode(), X, Y, BO, IsSext))
1844  return nullptr;
1845 
1846  // bo (ext X), (ext Y) --> ext (bo X, Y)
1847  // bo (ext X), C --> ext (bo X, C')
1848  Value *NarrowBO = Builder.CreateBinOp(BO.getOpcode(), X, Y, "narrow");
1849  if (auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) {
1850  if (IsSext)
1851  NewBinOp->setHasNoSignedWrap();
1852  else
1853  NewBinOp->setHasNoUnsignedWrap();
1854  }
1855  return CastInst::Create(CastOpc, NarrowBO, BO.getType());
1856 }
1857 
1858 static bool isMergedGEPInBounds(GEPOperator &GEP1, GEPOperator &GEP2) {
1859  // At least one GEP must be inbounds.
1860  if (!GEP1.isInBounds() && !GEP2.isInBounds())
1861  return false;
1862 
1863  return (GEP1.isInBounds() || GEP1.hasAllZeroIndices()) &&
1864  (GEP2.isInBounds() || GEP2.hasAllZeroIndices());
1865 }
1866 
1867 /// Thread a GEP operation with constant indices through the constant true/false
1868 /// arms of a select.
1871  if (!GEP.hasAllConstantIndices())
1872  return nullptr;
1873 
1874  Instruction *Sel;
1875  Value *Cond;
1876  Constant *TrueC, *FalseC;
1877  if (!match(GEP.getPointerOperand(), m_Instruction(Sel)) ||
1878  !match(Sel,
1879  m_Select(m_Value(Cond), m_Constant(TrueC), m_Constant(FalseC))))
1880  return nullptr;
1881 
1882  // gep (select Cond, TrueC, FalseC), IndexC --> select Cond, TrueC', FalseC'
1883  // Propagate 'inbounds' and metadata from existing instructions.
1884  // Note: using IRBuilder to create the constants for efficiency.
1885  SmallVector<Value *, 4> IndexC(GEP.indices());
1886  bool IsInBounds = GEP.isInBounds();
1887  Type *Ty = GEP.getSourceElementType();
1888  Value *NewTrueC = IsInBounds ? Builder.CreateInBoundsGEP(Ty, TrueC, IndexC)
1889  : Builder.CreateGEP(Ty, TrueC, IndexC);
1890  Value *NewFalseC = IsInBounds ? Builder.CreateInBoundsGEP(Ty, FalseC, IndexC)
1891  : Builder.CreateGEP(Ty, FalseC, IndexC);
1892  return SelectInst::Create(Cond, NewTrueC, NewFalseC, "", nullptr, Sel);
1893 }
1894 
1896  SmallVector<Value *, 8> Ops(GEP.operands());
1897  Type *GEPType = GEP.getType();
1898  Type *GEPEltType = GEP.getSourceElementType();
1899  bool IsGEPSrcEleScalable = isa<ScalableVectorType>(GEPEltType);
1900  if (Value *V = SimplifyGEPInst(GEPEltType, Ops, SQ.getWithInstruction(&GEP)))
1901  return replaceInstUsesWith(GEP, V);
1902 
1903  // For vector geps, use the generic demanded vector support.
1904  // Skip if GEP return type is scalable. The number of elements is unknown at
1905  // compile-time.
1906  if (auto *GEPFVTy = dyn_cast<FixedVectorType>(GEPType)) {
1907  auto VWidth = GEPFVTy->getNumElements();
1908  APInt UndefElts(VWidth, 0);
1909  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1910  if (Value *V = SimplifyDemandedVectorElts(&GEP, AllOnesEltMask,
1911  UndefElts)) {
1912  if (V != &GEP)
1913  return replaceInstUsesWith(GEP, V);
1914  return &GEP;
1915  }
1916 
1917  // TODO: 1) Scalarize splat operands, 2) scalarize entire instruction if
1918  // possible (decide on canonical form for pointer broadcast), 3) exploit
1919  // undef elements to decrease demanded bits
1920  }
1921 
1922  Value *PtrOp = GEP.getOperand(0);
1923 
1924  // Eliminate unneeded casts for indices, and replace indices which displace
1925  // by multiples of a zero size type with zero.
1926  bool MadeChange = false;
1927 
1928  // Index width may not be the same width as pointer width.
1929  // Data layout chooses the right type based on supported integer types.
1930  Type *NewScalarIndexTy =
1931  DL.getIndexType(GEP.getPointerOperandType()->getScalarType());
1932 
1934  for (User::op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E;
1935  ++I, ++GTI) {
1936  // Skip indices into struct types.
1937  if (GTI.isStruct())
1938  continue;
1939 
1940  Type *IndexTy = (*I)->getType();
1941  Type *NewIndexType =
1942  IndexTy->isVectorTy()
1943  ? VectorType::get(NewScalarIndexTy,
1944  cast<VectorType>(IndexTy)->getElementCount())
1945  : NewScalarIndexTy;
1946 
1947  // If the element type has zero size then any index over it is equivalent
1948  // to an index of zero, so replace it with zero if it is not zero already.
1949  Type *EltTy = GTI.getIndexedType();
1950  if (EltTy->isSized() && DL.getTypeAllocSize(EltTy).isZero())
1951  if (!isa<Constant>(*I) || !match(I->get(), m_Zero())) {
1952  *I = Constant::getNullValue(NewIndexType);
1953  MadeChange = true;
1954  }
1955 
1956  if (IndexTy != NewIndexType) {
1957  // If we are using a wider index than needed for this platform, shrink
1958  // it to what we need. If narrower, sign-extend it to what we need.
1959  // This explicit cast can make subsequent optimizations more obvious.
1960  *I = Builder.CreateIntCast(*I, NewIndexType, true);
1961  MadeChange = true;
1962  }
1963  }
1964  if (MadeChange)
1965  return &GEP;
1966 
1967  // Check to see if the inputs to the PHI node are getelementptr instructions.
1968  if (auto *PN = dyn_cast<PHINode>(PtrOp)) {
1969  auto *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));
1970  if (!Op1)
1971  return nullptr;
1972 
1973  // Don't fold a GEP into itself through a PHI node. This can only happen
1974  // through the back-edge of a loop. Folding a GEP into itself means that
1975  // the value of the previous iteration needs to be stored in the meantime,
1976  // thus requiring an additional register variable to be live, but not
1977  // actually achieving anything (the GEP still needs to be executed once per
1978  // loop iteration).
1979  if (Op1 == &GEP)
1980  return nullptr;
1981 
1982  int DI = -1;
1983 
1984  for (auto I = PN->op_begin()+1, E = PN->op_end(); I !=E; ++I) {
1985  auto *Op2 = dyn_cast<GetElementPtrInst>(*I);
1986  if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands())
1987  return nullptr;
1988 
1989  // As for Op1 above, don't try to fold a GEP into itself.
1990  if (Op2 == &GEP)
1991  return nullptr;
1992 
1993  // Keep track of the type as we walk the GEP.
1994  Type *CurTy = nullptr;
1995 
1996  for (unsigned J = 0, F = Op1->getNumOperands(); J != F; ++J) {
1997  if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())
1998  return nullptr;
1999 
2000  if (Op1->getOperand(J) != Op2->getOperand(J)) {
2001  if (DI == -1) {
2002  // We have not seen any differences yet in the GEPs feeding the
2003  // PHI yet, so we record this one if it is allowed to be a
2004  // variable.
2005 
2006  // The first two arguments can vary for any GEP, the rest have to be
2007  // static for struct slots
2008  if (J > 1) {
2009  assert(CurTy && "No current type?");
2010  if (CurTy->isStructTy())
2011  return nullptr;
2012  }
2013 
2014  DI = J;
2015  } else {
2016  // The GEP is different by more than one input. While this could be
2017  // extended to support GEPs that vary by more than one variable it
2018  // doesn't make sense since it greatly increases the complexity and
2019  // would result in an R+R+R addressing mode which no backend
2020  // directly supports and would need to be broken into several
2021  // simpler instructions anyway.
2022  return nullptr;
2023  }
2024  }
2025 
2026  // Sink down a layer of the type for the next iteration.
2027  if (J > 0) {
2028  if (J == 1) {
2029  CurTy = Op1->getSourceElementType();
2030  } else {
2031  CurTy =
2032  GetElementPtrInst::getTypeAtIndex(CurTy, Op1->getOperand(J));
2033  }
2034  }
2035  }
2036  }
2037 
2038  // If not all GEPs are identical we'll have to create a new PHI node.
2039  // Check that the old PHI node has only one use so that it will get
2040  // removed.
2041  if (DI != -1 && !PN->hasOneUse())
2042  return nullptr;
2043 
2044  auto *NewGEP = cast<GetElementPtrInst>(Op1->clone());
2045  if (DI == -1) {
2046  // All the GEPs feeding the PHI are identical. Clone one down into our
2047  // BB so that it can be merged with the current GEP.
2048  } else {
2049  // All the GEPs feeding the PHI differ at a single offset. Clone a GEP
2050  // into the current block so it can be merged, and create a new PHI to
2051  // set that index.
2052  PHINode *NewPN;
2053  {
2055  Builder.SetInsertPoint(PN);
2056  NewPN = Builder.CreatePHI(Op1->getOperand(DI)->getType(),
2057  PN->getNumOperands());
2058  }
2059 
2060  for (auto &I : PN->operands())
2061  NewPN->addIncoming(cast<GEPOperator>(I)->getOperand(DI),
2062  PN->getIncomingBlock(I));
2063 
2064  NewGEP->setOperand(DI, NewPN);
2065  }
2066 
2067  GEP.getParent()->getInstList().insert(
2068  GEP.getParent()->getFirstInsertionPt(), NewGEP);
2069  replaceOperand(GEP, 0, NewGEP);
2070  PtrOp = NewGEP;
2071  }
2072 
2073  // Combine Indices - If the source pointer to this getelementptr instruction
2074  // is a getelementptr instruction, combine the indices of the two
2075  // getelementptr instructions into a single instruction.
2076  if (auto *Src = dyn_cast<GEPOperator>(PtrOp)) {
2077  if (!shouldMergeGEPs(*cast<GEPOperator>(&GEP), *Src))
2078  return nullptr;
2079 
2080  if (Src->getNumOperands() == 2 && GEP.getNumOperands() == 2 &&
2081  Src->hasOneUse()) {
2082  Value *GO1 = GEP.getOperand(1);
2083  Value *SO1 = Src->getOperand(1);
2084 
2085  if (LI) {
2086  // Try to reassociate loop invariant GEP chains to enable LICM.
2087  if (Loop *L = LI->getLoopFor(GEP.getParent())) {
2088  // Reassociate the two GEPs if SO1 is variant in the loop and GO1 is
2089  // invariant: this breaks the dependence between GEPs and allows LICM
2090  // to hoist the invariant part out of the loop.
2091  if (L->isLoopInvariant(GO1) && !L->isLoopInvariant(SO1)) {
2092  // We have to be careful here.
2093  // We have something like:
2094  // %src = getelementptr <ty>, <ty>* %base, <ty> %idx
2095  // %gep = getelementptr <ty>, <ty>* %src, <ty> %idx2
2096  // If we just swap idx & idx2 then we could inadvertantly
2097  // change %src from a vector to a scalar, or vice versa.
2098  // Cases:
2099  // 1) %base a scalar & idx a scalar & idx2 a vector
2100  // => Swapping idx & idx2 turns %src into a vector type.
2101  // 2) %base a scalar & idx a vector & idx2 a scalar
2102  // => Swapping idx & idx2 turns %src in a scalar type
2103  // 3) %base, %idx, and %idx2 are scalars
2104  // => %src & %gep are scalars
2105  // => swapping idx & idx2 is safe
2106  // 4) %base a vector
2107  // => %src is a vector
2108  // => swapping idx & idx2 is safe.
2109  auto *SO0 = Src->getOperand(0);
2110  auto *SO0Ty = SO0->getType();
2111  if (!isa<VectorType>(GEPType) || // case 3
2112  isa<VectorType>(SO0Ty)) { // case 4
2113  Src->setOperand(1, GO1);
2114  GEP.setOperand(1, SO1);
2115  return &GEP;
2116  } else {
2117  // Case 1 or 2
2118  // -- have to recreate %src & %gep
2119  // put NewSrc at same location as %src
2120  Builder.SetInsertPoint(cast<Instruction>(PtrOp));
2121  auto *NewSrc = cast<GetElementPtrInst>(
2122  Builder.CreateGEP(GEPEltType, SO0, GO1, Src->getName()));
2123  NewSrc->setIsInBounds(Src->isInBounds());
2124  auto *NewGEP =
2125  GetElementPtrInst::Create(GEPEltType, NewSrc, {SO1});
2126  NewGEP->setIsInBounds(GEP.isInBounds());
2127  return NewGEP;
2128  }
2129  }
2130  }
2131  }
2132 
2133  // Fold (gep(gep(Ptr,Idx0),Idx1) -> gep(Ptr,add(Idx0,Idx1))
2134  if (GO1->getType() == SO1->getType()) {
2135  bool NewInBounds = GEP.isInBounds() && Src->isInBounds();
2136  auto *NewIdx =
2137  Builder.CreateAdd(GO1, SO1, GEP.getName() + ".idx",
2138  /*HasNUW*/ false, /*HasNSW*/ NewInBounds);
2139  auto *NewGEP = GetElementPtrInst::Create(
2140  GEPEltType, Src->getPointerOperand(), {NewIdx});
2141  NewGEP->setIsInBounds(NewInBounds);
2142  return NewGEP;
2143  }
2144  }
2145 
2146  // Note that if our source is a gep chain itself then we wait for that
2147  // chain to be resolved before we perform this transformation. This
2148  // avoids us creating a TON of code in some cases.
2149  if (auto *SrcGEP = dyn_cast<GEPOperator>(Src->getOperand(0)))
2150  if (SrcGEP->getNumOperands() == 2 && shouldMergeGEPs(*Src, *SrcGEP))
2151  return nullptr; // Wait until our source is folded to completion.
2152 
2153  SmallVector<Value*, 8> Indices;
2154 
2155  // Find out whether the last index in the source GEP is a sequential idx.
2156  bool EndsWithSequential = false;
2157  for (gep_type_iterator I = gep_type_begin(*Src), E = gep_type_end(*Src);
2158  I != E; ++I)
2159  EndsWithSequential = I.isSequential();
2160 
2161  // Can we combine the two pointer arithmetics offsets?
2162  if (EndsWithSequential) {
2163  // Replace: gep (gep %P, long B), long A, ...
2164  // With: T = long A+B; gep %P, T, ...
2165  Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
2166  Value *GO1 = GEP.getOperand(1);
2167 
2168  // If they aren't the same type, then the input hasn't been processed
2169  // by the loop above yet (which canonicalizes sequential index types to
2170  // intptr_t). Just avoid transforming this until the input has been
2171  // normalized.
2172  if (SO1->getType() != GO1->getType())
2173  return nullptr;
2174 
2175  Value *Sum =
2176  SimplifyAddInst(GO1, SO1, false, false, SQ.getWithInstruction(&GEP));
2177  // Only do the combine when we are sure the cost after the
2178  // merge is never more than that before the merge.
2179  if (Sum == nullptr)
2180  return nullptr;
2181 
2182  // Update the GEP in place if possible.
2183  if (Src->getNumOperands() == 2) {
2184  GEP.setIsInBounds(isMergedGEPInBounds(*Src, *cast<GEPOperator>(&GEP)));
2185  replaceOperand(GEP, 0, Src->getOperand(0));
2186  replaceOperand(GEP, 1, Sum);
2187  return &GEP;
2188  }
2189  Indices.append(Src->op_begin()+1, Src->op_end()-1);
2190  Indices.push_back(Sum);
2191  Indices.append(GEP.op_begin()+2, GEP.op_end());
2192  } else if (isa<Constant>(*GEP.idx_begin()) &&
2193  cast<Constant>(*GEP.idx_begin())->isNullValue() &&
2194  Src->getNumOperands() != 1) {
2195  // Otherwise we can do the fold if the first index of the GEP is a zero
2196  Indices.append(Src->op_begin()+1, Src->op_end());
2197  Indices.append(GEP.idx_begin()+1, GEP.idx_end());
2198  }
2199 
2200  if (!Indices.empty())
2201  return isMergedGEPInBounds(*Src, *cast<GEPOperator>(&GEP))
2203  Src->getSourceElementType(), Src->getOperand(0), Indices,
2204  GEP.getName())
2205  : GetElementPtrInst::Create(Src->getSourceElementType(),
2206  Src->getOperand(0), Indices,
2207  GEP.getName());
2208  }
2209 
2210  // Skip if GEP source element type is scalable. The type alloc size is unknown
2211  // at compile-time.
2212  if (GEP.getNumIndices() == 1 && !IsGEPSrcEleScalable) {
2213  unsigned AS = GEP.getPointerAddressSpace();
2214  if (GEP.getOperand(1)->getType()->getScalarSizeInBits() ==
2215  DL.getIndexSizeInBits(AS)) {
2216  uint64_t TyAllocSize = DL.getTypeAllocSize(GEPEltType).getFixedSize();
2217 
2218  bool Matched = false;
2219  uint64_t C;
2220  Value *V = nullptr;
2221  if (TyAllocSize == 1) {
2222  V = GEP.getOperand(1);
2223  Matched = true;
2224  } else if (match(GEP.getOperand(1),
2225  m_AShr(m_Value(V), m_ConstantInt(C)))) {
2226  if (TyAllocSize == 1ULL << C)
2227  Matched = true;
2228  } else if (match(GEP.getOperand(1),
2229  m_SDiv(m_Value(V), m_ConstantInt(C)))) {
2230  if (TyAllocSize == C)
2231  Matched = true;
2232  }
2233 
2234  // Canonicalize (gep i8* X, (ptrtoint Y)-(ptrtoint X)) to (bitcast Y), but
2235  // only if both point to the same underlying object (otherwise provenance
2236  // is not necessarily retained).
2237  Value *Y;
2238  Value *X = GEP.getOperand(0);
2239  if (Matched &&
2243  }
2244  }
2245 
2246  // We do not handle pointer-vector geps here.
2247  if (GEPType->isVectorTy())
2248  return nullptr;
2249 
2250  // Handle gep(bitcast x) and gep(gep x, 0, 0, 0).
2251  Value *StrippedPtr = PtrOp->stripPointerCasts();
2252  PointerType *StrippedPtrTy = cast<PointerType>(StrippedPtr->getType());
2253 
2254  if (StrippedPtr != PtrOp) {
2255  bool HasZeroPointerIndex = false;
2256  Type *StrippedPtrEltTy = StrippedPtrTy->getElementType();
2257 
2258  if (auto *C = dyn_cast<ConstantInt>(GEP.getOperand(1)))
2259  HasZeroPointerIndex = C->isZero();
2260 
2261  // Transform: GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ...
2262  // into : GEP [10 x i8]* X, i32 0, ...
2263  //
2264  // Likewise, transform: GEP (bitcast i8* X to [0 x i8]*), i32 0, ...
2265  // into : GEP i8* X, ...
2266  //
2267  // This occurs when the program declares an array extern like "int X[];"
2268  if (HasZeroPointerIndex) {
2269  if (auto *CATy = dyn_cast<ArrayType>(GEPEltType)) {
2270  // GEP (bitcast i8* X to [0 x i8]*), i32 0, ... ?
2271  if (CATy->getElementType() == StrippedPtrEltTy) {
2272  // -> GEP i8* X, ...
2273  SmallVector<Value *, 8> Idx(drop_begin(GEP.indices()));
2275  StrippedPtrEltTy, StrippedPtr, Idx, GEP.getName());
2276  Res->setIsInBounds(GEP.isInBounds());
2277  if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace())
2278  return Res;
2279  // Insert Res, and create an addrspacecast.
2280  // e.g.,
2281  // GEP (addrspacecast i8 addrspace(1)* X to [0 x i8]*), i32 0, ...
2282  // ->
2283  // %0 = GEP i8 addrspace(1)* X, ...
2284  // addrspacecast i8 addrspace(1)* %0 to i8*
2285  return new AddrSpaceCastInst(Builder.Insert(Res), GEPType);
2286  }
2287 
2288  if (auto *XATy = dyn_cast<ArrayType>(StrippedPtrEltTy)) {
2289  // GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ... ?
2290  if (CATy->getElementType() == XATy->getElementType()) {
2291  // -> GEP [10 x i8]* X, i32 0, ...
2292  // At this point, we know that the cast source type is a pointer
2293  // to an array of the same type as the destination pointer
2294  // array. Because the array type is never stepped over (there
2295  // is a leading zero) we can fold the cast into this GEP.
2296  if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace()) {
2297  GEP.setSourceElementType(XATy);
2298  return replaceOperand(GEP, 0, StrippedPtr);
2299  }
2300  // Cannot replace the base pointer directly because StrippedPtr's
2301  // address space is different. Instead, create a new GEP followed by
2302  // an addrspacecast.
2303  // e.g.,
2304  // GEP (addrspacecast [10 x i8] addrspace(1)* X to [0 x i8]*),
2305  // i32 0, ...
2306  // ->
2307  // %0 = GEP [10 x i8] addrspace(1)* X, ...
2308  // addrspacecast i8 addrspace(1)* %0 to i8*
2309  SmallVector<Value *, 8> Idx(GEP.indices());
2310  Value *NewGEP =
2311  GEP.isInBounds()
2312  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2313  Idx, GEP.getName())
2314  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2315  GEP.getName());
2316  return new AddrSpaceCastInst(NewGEP, GEPType);
2317  }
2318  }
2319  }
2320  } else if (GEP.getNumOperands() == 2 && !IsGEPSrcEleScalable) {
2321  // Skip if GEP source element type is scalable. The type alloc size is
2322  // unknown at compile-time.
2323  // Transform things like: %t = getelementptr i32*
2324  // bitcast ([2 x i32]* %str to i32*), i32 %V into: %t1 = getelementptr [2
2325  // x i32]* %str, i32 0, i32 %V; bitcast
2326  if (StrippedPtrEltTy->isArrayTy() &&
2327  DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType()) ==
2328  DL.getTypeAllocSize(GEPEltType)) {
2329  Type *IdxType = DL.getIndexType(GEPType);
2330  Value *Idx[2] = { Constant::getNullValue(IdxType), GEP.getOperand(1) };
2331  Value *NewGEP =
2332  GEP.isInBounds()
2333  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2334  GEP.getName())
2335  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2336  GEP.getName());
2337 
2338  // V and GEP are both pointer types --> BitCast
2339  return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, GEPType);
2340  }
2341 
2342  // Transform things like:
2343  // %V = mul i64 %N, 4
2344  // %t = getelementptr i8* bitcast (i32* %arr to i8*), i32 %V
2345  // into: %t1 = getelementptr i32* %arr, i32 %N; bitcast
2346  if (GEPEltType->isSized() && StrippedPtrEltTy->isSized()) {
2347  // Check that changing the type amounts to dividing the index by a scale
2348  // factor.
2349  uint64_t ResSize = DL.getTypeAllocSize(GEPEltType).getFixedSize();
2350  uint64_t SrcSize = DL.getTypeAllocSize(StrippedPtrEltTy).getFixedSize();
2351  if (ResSize && SrcSize % ResSize == 0) {
2352  Value *Idx = GEP.getOperand(1);
2353  unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
2354  uint64_t Scale = SrcSize / ResSize;
2355 
2356  // Earlier transforms ensure that the index has the right type
2357  // according to Data Layout, which considerably simplifies the
2358  // logic by eliminating implicit casts.
2359  assert(Idx->getType() == DL.getIndexType(GEPType) &&
2360  "Index type does not match the Data Layout preferences");
2361 
2362  bool NSW;
2363  if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
2364  // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
2365  // If the multiplication NewIdx * Scale may overflow then the new
2366  // GEP may not be "inbounds".
2367  Value *NewGEP =
2368  GEP.isInBounds() && NSW
2369  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2370  NewIdx, GEP.getName())
2371  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, NewIdx,
2372  GEP.getName());
2373 
2374  // The NewGEP must be pointer typed, so must the old one -> BitCast
2376  GEPType);
2377  }
2378  }
2379  }
2380 
2381  // Similarly, transform things like:
2382  // getelementptr i8* bitcast ([100 x double]* X to i8*), i32 %tmp
2383  // (where tmp = 8*tmp2) into:
2384  // getelementptr [100 x double]* %arr, i32 0, i32 %tmp2; bitcast
2385  if (GEPEltType->isSized() && StrippedPtrEltTy->isSized() &&
2386  StrippedPtrEltTy->isArrayTy()) {
2387  // Check that changing to the array element type amounts to dividing the
2388  // index by a scale factor.
2389  uint64_t ResSize = DL.getTypeAllocSize(GEPEltType).getFixedSize();
2390  uint64_t ArrayEltSize =
2391  DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType())
2392  .getFixedSize();
2393  if (ResSize && ArrayEltSize % ResSize == 0) {
2394  Value *Idx = GEP.getOperand(1);
2395  unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
2396  uint64_t Scale = ArrayEltSize / ResSize;
2397 
2398  // Earlier transforms ensure that the index has the right type
2399  // according to the Data Layout, which considerably simplifies
2400  // the logic by eliminating implicit casts.
2401  assert(Idx->getType() == DL.getIndexType(GEPType) &&
2402  "Index type does not match the Data Layout preferences");
2403 
2404  bool NSW;
2405  if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
2406  // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
2407  // If the multiplication NewIdx * Scale may overflow then the new
2408  // GEP may not be "inbounds".
2409  Type *IndTy = DL.getIndexType(GEPType);
2410  Value *Off[2] = {Constant::getNullValue(IndTy), NewIdx};
2411 
2412  Value *NewGEP =
2413  GEP.isInBounds() && NSW
2414  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2415  Off, GEP.getName())
2416  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Off,
2417  GEP.getName());
2418  // The NewGEP must be pointer typed, so must the old one -> BitCast
2420  GEPType);
2421  }
2422  }
2423  }
2424  }
2425  }
2426 
2427  // addrspacecast between types is canonicalized as a bitcast, then an
2428  // addrspacecast. To take advantage of the below bitcast + struct GEP, look
2429  // through the addrspacecast.
2430  Value *ASCStrippedPtrOp = PtrOp;
2431  if (auto *ASC = dyn_cast<AddrSpaceCastInst>(PtrOp)) {
2432  // X = bitcast A addrspace(1)* to B addrspace(1)*
2433  // Y = addrspacecast A addrspace(1)* to B addrspace(2)*
2434  // Z = gep Y, <...constant indices...>
2435  // Into an addrspacecasted GEP of the struct.
2436  if (auto *BC = dyn_cast<BitCastInst>(ASC->getOperand(0)))
2437  ASCStrippedPtrOp = BC;
2438  }
2439 
2440  if (auto *BCI = dyn_cast<BitCastInst>(ASCStrippedPtrOp)) {
2441  Value *SrcOp = BCI->getOperand(0);
2442  PointerType *SrcType = cast<PointerType>(BCI->getSrcTy());
2443  Type *SrcEltType = SrcType->getElementType();
2444 
2445  // GEP directly using the source operand if this GEP is accessing an element
2446  // of a bitcasted pointer to vector or array of the same dimensions:
2447  // gep (bitcast <c x ty>* X to [c x ty]*), Y, Z --> gep X, Y, Z
2448  // gep (bitcast [c x ty]* X to <c x ty>*), Y, Z --> gep X, Y, Z
2449  auto areMatchingArrayAndVecTypes = [](Type *ArrTy, Type *VecTy,
2450  const DataLayout &DL) {
2451  auto *VecVTy = cast<FixedVectorType>(VecTy);
2452  return ArrTy->getArrayElementType() == VecVTy->getElementType() &&
2453  ArrTy->getArrayNumElements() == VecVTy->getNumElements() &&
2454  DL.getTypeAllocSize(ArrTy) == DL.getTypeAllocSize(VecTy);
2455  };
2456  if (GEP.getNumOperands() == 3 &&
2457  ((GEPEltType->isArrayTy() && isa<FixedVectorType>(SrcEltType) &&
2458  areMatchingArrayAndVecTypes(GEPEltType, SrcEltType, DL)) ||
2459  (isa<FixedVectorType>(GEPEltType) && SrcEltType->isArrayTy() &&
2460  areMatchingArrayAndVecTypes(SrcEltType, GEPEltType, DL)))) {
2461 
2462  // Create a new GEP here, as using `setOperand()` followed by
2463  // `setSourceElementType()` won't actually update the type of the
2464  // existing GEP Value. Causing issues if this Value is accessed when
2465  // constructing an AddrSpaceCastInst
2466  Value *NGEP =
2467  GEP.isInBounds()
2468  ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]})
2469  : Builder.CreateGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]});
2470  NGEP->takeName(&GEP);
2471 
2472  // Preserve GEP address space to satisfy users
2473  if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace())
2474  return new AddrSpaceCastInst(NGEP, GEPType);
2475 
2476  return replaceInstUsesWith(GEP, NGEP);
2477  }
2478 
2479  // See if we can simplify:
2480  // X = bitcast A* to B*
2481  // Y = gep X, <...constant indices...>
2482  // into a gep of the original struct. This is important for SROA and alias
2483  // analysis of unions. If "A" is also a bitcast, wait for A/X to be merged.
2484  unsigned OffsetBits = DL.getIndexTypeSizeInBits(GEPType);
2485  APInt Offset(OffsetBits, 0);
2486 
2487  // If the bitcast argument is an allocation, The bitcast is for convertion
2488  // to actual type of allocation. Removing such bitcasts, results in having
2489  // GEPs with i8* base and pure byte offsets. That means GEP is not aware of
2490  // struct or array hierarchy.
2491  // By avoiding such GEPs, phi translation and MemoryDependencyAnalysis have
2492  // a better chance to succeed.
2493  if (!isa<BitCastInst>(SrcOp) && GEP.accumulateConstantOffset(DL, Offset) &&
2494  !isAllocationFn(SrcOp, &TLI)) {
2495  // If this GEP instruction doesn't move the pointer, just replace the GEP
2496  // with a bitcast of the real input to the dest type.
2497  if (!Offset) {
2498  // If the bitcast is of an allocation, and the allocation will be
2499  // converted to match the type of the cast, don't touch this.
2500  if (isa<AllocaInst>(SrcOp)) {
2501  // See if the bitcast simplifies, if so, don't nuke this GEP yet.
2502  if (Instruction *I = visitBitCast(*BCI)) {
2503  if (I != BCI) {
2504  I->takeName(BCI);
2505  BCI->getParent()->getInstList().insert(BCI->getIterator(), I);
2506  replaceInstUsesWith(*BCI, I);
2507  }
2508  return &GEP;
2509  }
2510  }
2511 
2512  if (SrcType->getPointerAddressSpace() != GEP.getAddressSpace())
2513  return new AddrSpaceCastInst(SrcOp, GEPType);
2514  return new BitCastInst(SrcOp, GEPType);
2515  }
2516 
2517  // Otherwise, if the offset is non-zero, we need to find out if there is a
2518  // field at Offset in 'A's type. If so, we can pull the cast through the
2519  // GEP.
2520  SmallVector<Value*, 8> NewIndices;
2521  if (FindElementAtOffset(SrcType, Offset.getSExtValue(), NewIndices)) {
2522  Value *NGEP =
2523  GEP.isInBounds()
2524  ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, NewIndices)
2525  : Builder.CreateGEP(SrcEltType, SrcOp, NewIndices);
2526 
2527  if (NGEP->getType() == GEPType)
2528  return replaceInstUsesWith(GEP, NGEP);
2529  NGEP->takeName(&GEP);
2530 
2531  if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace())
2532  return new AddrSpaceCastInst(NGEP, GEPType);
2533  return new BitCastInst(NGEP, GEPType);
2534  }
2535  }
2536  }
2537 
2538  if (!GEP.isInBounds()) {
2539  unsigned IdxWidth =
2540  DL.getIndexSizeInBits(PtrOp->getType()->getPointerAddressSpace());
2541  APInt BasePtrOffset(IdxWidth, 0);
2542  Value *UnderlyingPtrOp =
2544  BasePtrOffset);
2545  if (auto *AI = dyn_cast<AllocaInst>(UnderlyingPtrOp)) {
2546  if (GEP.accumulateConstantOffset(DL, BasePtrOffset) &&
2547  BasePtrOffset.isNonNegative()) {
2548  APInt AllocSize(
2549  IdxWidth,
2550  DL.getTypeAllocSize(AI->getAllocatedType()).getKnownMinSize());
2551  if (BasePtrOffset.ule(AllocSize)) {
2553  GEP.getSourceElementType(), PtrOp, makeArrayRef(Ops).slice(1),
2554  GEP.getName());
2555  }
2556  }
2557  }
2558  }
2559 
2560  if (Instruction *R = foldSelectGEP(GEP, Builder))
2561  return R;
2562 
2563  return nullptr;
2564 }
2565 
2567  Instruction *AI) {
2568  if (isa<ConstantPointerNull>(V))
2569  return true;
2570  if (auto *LI = dyn_cast<LoadInst>(V))
2571  return isa<GlobalVariable>(LI->getPointerOperand());
2572  // Two distinct allocations will never be equal.
2573  // We rely on LookThroughBitCast in isAllocLikeFn being false, since looking
2574  // through bitcasts of V can cause
2575  // the result statement below to be true, even when AI and V (ex:
2576  // i8* ->i32* ->i8* of AI) are the same allocations.
2577  return isAllocLikeFn(V, TLI) && V != AI;
2578 }
2579 
2582  const TargetLibraryInfo *TLI) {
2584  Worklist.push_back(AI);
2585 
2586  do {
2587  Instruction *PI = Worklist.pop_back_val();
2588  for (User *U : PI->users()) {
2589  Instruction *I = cast<Instruction>(U);
2590  switch (I->getOpcode()) {
2591  default:
2592  // Give up the moment we see something we can't handle.
2593  return false;
2594 
2595  case Instruction::AddrSpaceCast:
2596  case Instruction::BitCast:
2597  case Instruction::GetElementPtr:
2598  Users.emplace_back(I);
2599  Worklist.push_back(I);
2600  continue;
2601 
2602  case Instruction::ICmp: {
2603  ICmpInst *ICI = cast<ICmpInst>(I);
2604  // We can fold eq/ne comparisons with null to false/true, respectively.
2605  // We also fold comparisons in some conditions provided the alloc has
2606  // not escaped (see isNeverEqualToUnescapedAlloc).
2607  if (!ICI->isEquality())
2608  return false;
2609  unsigned OtherIndex = (ICI->getOperand(0) == PI) ? 1 : 0;
2610  if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex), TLI, AI))
2611  return false;
2612  Users.emplace_back(I);
2613  continue;
2614  }
2615 
2616  case Instruction::Call:
2617  // Ignore no-op and store intrinsics.
2618  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
2619  switch (II->getIntrinsicID()) {
2620  default:
2621  return false;
2622 
2623  case Intrinsic::memmove:
2624  case Intrinsic::memcpy:
2625  case Intrinsic::memset: {
2626  MemIntrinsic *MI = cast<MemIntrinsic>(II);
2627  if (MI->isVolatile() || MI->getRawDest() != PI)
2628  return false;
2630  }
2631  case Intrinsic::assume:
2632  case Intrinsic::invariant_start:
2633  case Intrinsic::invariant_end:
2634  case Intrinsic::lifetime_start:
2635  case Intrinsic::lifetime_end:
2636  case Intrinsic::objectsize:
2637  Users.emplace_back(I);
2638  continue;
2639  case Intrinsic::launder_invariant_group:
2640  case Intrinsic::strip_invariant_group:
2641  Users.emplace_back(I);
2642  Worklist.push_back(I);
2643  continue;
2644  }
2645  }
2646 
2647  if (isFreeCall(I, TLI)) {
2648  Users.emplace_back(I);
2649  continue;
2650  }
2651  return false;
2652 
2653  case Instruction::Store: {
2654  StoreInst *SI = cast<StoreInst>(I);
2655  if (SI->isVolatile() || SI->getPointerOperand() != PI)
2656  return false;
2657  Users.emplace_back(I);
2658  continue;
2659  }
2660  }
2661  llvm_unreachable("missing a return?");
2662  }
2663  } while (!Worklist.empty());
2664  return true;
2665 }
2666 
2668  // If we have a malloc call which is only used in any amount of comparisons to
2669  // null and free calls, delete the calls and replace the comparisons with true
2670  // or false as appropriate.
2671 
2672  // This is based on the principle that we can substitute our own allocation
2673  // function (which will never return null) rather than knowledge of the
2674  // specific function being called. In some sense this can change the permitted
2675  // outputs of a program (when we convert a malloc to an alloca, the fact that
2676  // the allocation is now on the stack is potentially visible, for example),
2677  // but we believe in a permissible manner.
2679 
2680  // If we are removing an alloca with a dbg.declare, insert dbg.value calls
2681  // before each store.
2683  std::unique_ptr<DIBuilder> DIB;
2684  if (isa<AllocaInst>(MI)) {
2685  findDbgUsers(DVIs, &MI);
2686  DIB.reset(new DIBuilder(*MI.getModule(), /*AllowUnresolved=*/false));
2687  }
2688 
2689  if (isAllocSiteRemovable(&MI, Users, &TLI)) {
2690  for (unsigned i = 0, e = Users.size(); i != e; ++i) {
2691  // Lowering all @llvm.objectsize calls first because they may
2692  // use a bitcast/GEP of the alloca we are removing.
2693  if (!Users[i])
2694  continue;
2695 
2696  Instruction *I = cast<Instruction>(&*Users[i]);
2697 
2698  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
2699  if (II->getIntrinsicID() == Intrinsic::objectsize) {
2700  Value *Result =
2701  lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true);
2702  replaceInstUsesWith(*I, Result);
2703  eraseInstFromFunction(*I);
2704  Users[i] = nullptr; // Skip examining in the next loop.
2705  }
2706  }
2707  }
2708  for (unsigned i = 0, e = Users.size(); i != e; ++i) {
2709  if (!Users[i])
2710  continue;
2711 
2712  Instruction *I = cast<Instruction>(&*Users[i]);
2713 
2714  if (ICmpInst *C = dyn_cast<ICmpInst>(I)) {
2715  replaceInstUsesWith(*C,
2716  ConstantInt::get(Type::getInt1Ty(C->getContext()),
2717  C->isFalseWhenEqual()));
2718  } else if (auto *SI = dyn_cast<StoreInst>(I)) {
2719  for (auto *DVI : DVIs)
2720  if (DVI->isAddressOfVariable())
2721  ConvertDebugDeclareToDebugValue(DVI, SI, *DIB);
2722  } else {
2723  // Casts, GEP, or anything else: we're about to delete this instruction,
2724  // so it can not have any valid uses.
2725  replaceInstUsesWith(*I, PoisonValue::get(I->getType()));
2726  }
2727  eraseInstFromFunction(*I);
2728  }
2729 
2730  if (InvokeInst *II = dyn_cast<InvokeInst>(&MI)) {
2731  // Replace invoke with a NOP intrinsic to maintain the original CFG
2732  Module *M = II->getModule();
2733  Function *F = Intrinsic::getDeclaration(M, Intrinsic::donothing);
2734  InvokeInst::Create(F, II->getNormalDest(), II->getUnwindDest(),
2735  None, "", II->getParent());
2736  }
2737 
2738  // Remove debug intrinsics which describe the value contained within the
2739  // alloca. In addition to removing dbg.{declare,addr} which simply point to
2740  // the alloca, remove dbg.value(<alloca>, ..., DW_OP_deref)'s as well, e.g.:
2741  //
2742  // ```
2743  // define void @foo(i32 %0) {
2744  // %a = alloca i32 ; Deleted.
2745  // store i32 %0, i32* %a
2746  // dbg.value(i32 %0, "arg0") ; Not deleted.
2747  // dbg.value(i32* %a, "arg0", DW_OP_deref) ; Deleted.
2748  // call void @trivially_inlinable_no_op(i32* %a)
2749  // ret void
2750  // }
2751  // ```
2752  //
2753  // This may not be required if we stop describing the contents of allocas
2754  // using dbg.value(<alloca>, ..., DW_OP_deref), but we currently do this in
2755  // the LowerDbgDeclare utility.
2756  //
2757  // If there is a dead store to `%a` in @trivially_inlinable_no_op, the
2758  // "arg0" dbg.value may be stale after the call. However, failing to remove
2759  // the DW_OP_deref dbg.value causes large gaps in location coverage.
2760  for (auto *DVI : DVIs)
2761  if (DVI->isAddressOfVariable() || DVI->getExpression()->startsWithDeref())
2762  DVI->eraseFromParent();
2763 
2764  return eraseInstFromFunction(MI);
2765  }
2766  return nullptr;
2767 }
2768 
2769 /// Move the call to free before a NULL test.
2770 ///
2771 /// Check if this free is accessed after its argument has been test
2772 /// against NULL (property 0).
2773 /// If yes, it is legal to move this call in its predecessor block.
2774 ///
2775 /// The move is performed only if the block containing the call to free
2776 /// will be removed, i.e.:
2777 /// 1. it has only one predecessor P, and P has two successors
2778 /// 2. it contains the call, noops, and an unconditional branch
2779 /// 3. its successor is the same as its predecessor's successor
2780 ///
2781 /// The profitability is out-of concern here and this function should
2782 /// be called only if the caller knows this transformation would be
2783 /// profitable (e.g., for code size).
2785  const DataLayout &DL) {
2786  Value *Op = FI.getArgOperand(0);
2787  BasicBlock *FreeInstrBB = FI.getParent();
2788  BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor();
2789 
2790  // Validate part of constraint #1: Only one predecessor
2791  // FIXME: We can extend the number of predecessor, but in that case, we
2792  // would duplicate the call to free in each predecessor and it may
2793  // not be profitable even for code size.
2794  if (!PredBB)
2795  return nullptr;
2796 
2797  // Validate constraint #2: Does this block contains only the call to
2798  // free, noops, and an unconditional branch?
2799  BasicBlock *SuccBB;
2800  Instruction *FreeInstrBBTerminator = FreeInstrBB->getTerminator();
2801  if (!match(FreeInstrBBTerminator, m_UnconditionalBr(SuccBB)))
2802  return nullptr;
2803 
2804  // If there are only 2 instructions in the block, at this point,
2805  // this is the call to free and unconditional.
2806  // If there are more than 2 instructions, check that they are noops
2807  // i.e., they won't hurt the performance of the generated code.
2808  if (FreeInstrBB->size() != 2) {
2809  for (const Instruction &Inst : FreeInstrBB->instructionsWithoutDebug()) {
2810  if (&Inst == &FI || &Inst == FreeInstrBBTerminator)
2811  continue;
2812  auto *Cast = dyn_cast<CastInst>(&Inst);
2813  if (!Cast || !Cast->isNoopCast(DL))
2814  return nullptr;
2815  }
2816  }
2817  // Validate the rest of constraint #1 by matching on the pred branch.
2818  Instruction *TI = PredBB->getTerminator();
2819  BasicBlock *TrueBB, *FalseBB;
2820  ICmpInst::Predicate Pred;
2821  if (!match(TI, m_Br(m_ICmp(Pred,
2823  m_Specific(Op->stripPointerCasts())),
2824  m_Zero()),
2825  TrueBB, FalseBB)))
2826  return nullptr;
2827  if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE)
2828  return nullptr;
2829 
2830  // Validate constraint #3: Ensure the null case just falls through.
2831  if (SuccBB != (Pred == ICmpInst::ICMP_EQ ? TrueBB : FalseBB))
2832  return nullptr;
2833  assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) &&
2834  "Broken CFG: missing edge from predecessor to successor");
2835 
2836  // At this point, we know that everything in FreeInstrBB can be moved
2837  // before TI.
2838  for (BasicBlock::iterator It = FreeInstrBB->begin(), End = FreeInstrBB->end();
2839  It != End;) {
2840  Instruction &Instr = *It++;
2841  if (&Instr == FreeInstrBBTerminator)
2842  break;
2843  Instr.moveBefore(TI);
2844  }
2845  assert(FreeInstrBB->size() == 1 &&
2846  "Only the branch instruction should remain");
2847  return &FI;
2848 }
2849 
2851  Value *Op = FI.getArgOperand(0);
2852 
2853  // free undef -> unreachable.
2854  if (isa<UndefValue>(Op)) {
2855  // Leave a marker since we can't modify the CFG here.
2856  CreateNonTerminatorUnreachable(&FI);
2857  return eraseInstFromFunction(FI);
2858  }
2859 
2860  // If we have 'free null' delete the instruction. This can happen in stl code
2861  // when lots of inlining happens.
2862  if (isa<ConstantPointerNull>(Op))
2863  return eraseInstFromFunction(FI);
2864 
2865  // If we optimize for code size, try to move the call to free before the null
2866  // test so that simplify cfg can remove the empty block and dead code
2867  // elimination the branch. I.e., helps to turn something like:
2868  // if (foo) free(foo);
2869  // into
2870  // free(foo);
2871  //
2872  // Note that we can only do this for 'free' and not for any flavor of
2873  // 'operator delete'; there is no 'operator delete' symbol for which we are
2874  // permitted to invent a call, even if we're passing in a null pointer.
2875  if (MinimizeSize) {
2876  LibFunc Func;
2877  if (TLI.getLibFunc(FI, Func) && TLI.has(Func) && Func == LibFunc_free)
2879  return I;
2880  }
2881 
2882  return nullptr;
2883 }
2884 
2885 static bool isMustTailCall(Value *V) {
2886  if (auto *CI = dyn_cast<CallInst>(V))
2887  return CI->isMustTailCall();
2888  return false;
2889 }
2890 
2892  if (RI.getNumOperands() == 0) // ret void
2893  return nullptr;
2894 
2895  Value *ResultOp = RI.getOperand(0);
2896  Type *VTy = ResultOp->getType();
2897  if (!VTy->isIntegerTy() || isa<Constant>(ResultOp))
2898  return nullptr;
2899 
2900  // Don't replace result of musttail calls.
2901  if (isMustTailCall(ResultOp))
2902  return nullptr;
2903 
2904  // There might be assume intrinsics dominating this return that completely
2905  // determine the value. If so, constant fold it.
2906  KnownBits Known = computeKnownBits(ResultOp, 0, &RI);
2907  if (Known.isConstant())
2908  return replaceOperand(RI, 0,
2909  Constant::getIntegerValue(VTy, Known.getConstant()));
2910 
2911  return nullptr;
2912 }
2913 
2914 // WARNING: keep in sync with SimplifyCFGOpt::simplifyUnreachable()!
2916  // Try to remove the previous instruction if it must lead to unreachable.
2917  // This includes instructions like stores and "llvm.assume" that may not get
2918  // removed by simple dead code elimination.
2919  while (Instruction *Prev = I.getPrevNonDebugInstruction()) {
2920  // While we theoretically can erase EH, that would result in a block that
2921  // used to start with an EH no longer starting with EH, which is invalid.
2922  // To make it valid, we'd need to fixup predecessors to no longer refer to
2923  // this block, but that changes CFG, which is not allowed in InstCombine.
2924  if (Prev->isEHPad())
2925  return nullptr; // Can not drop any more instructions. We're done here.
2926 
2928  return nullptr; // Can not drop any more instructions. We're done here.
2929  // Otherwise, this instruction can be freely erased,
2930  // even if it is not side-effect free.
2931 
2932  // A value may still have uses before we process it here (for example, in
2933  // another unreachable block), so convert those to poison.
2934  replaceInstUsesWith(*Prev, PoisonValue::get(Prev->getType()));
2935  eraseInstFromFunction(*Prev);
2936  }
2937  assert(I.getParent()->sizeWithoutDebug() == 1 && "The block is now empty.");
2938  // FIXME: recurse into unconditional predecessors?
2939  return nullptr;
2940 }
2941 
2943  assert(BI.isUnconditional() && "Only for unconditional branches.");
2944 
2945  // If this store is the second-to-last instruction in the basic block
2946  // (excluding debug info and bitcasts of pointers) and if the block ends with
2947  // an unconditional branch, try to move the store to the successor block.
2948 
2949  auto GetLastSinkableStore = [](BasicBlock::iterator BBI) {
2950  auto IsNoopInstrForStoreMerging = [](BasicBlock::iterator BBI) {
2951  return isa<DbgInfoIntrinsic>(BBI) ||
2952  (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy());
2953  };
2954 
2955  BasicBlock::iterator FirstInstr = BBI->getParent()->begin();
2956  do {
2957  if (BBI != FirstInstr)
2958  --BBI;
2959  } while (BBI != FirstInstr && IsNoopInstrForStoreMerging(BBI));
2960 
2961  return dyn_cast<StoreInst>(BBI);
2962  };
2963 
2964  if (StoreInst *SI = GetLastSinkableStore(BasicBlock::iterator(BI)))
2965  if (mergeStoreIntoSuccessor(*SI))
2966  return &BI;
2967 
2968  return nullptr;
2969 }
2970 
2972  if (BI.isUnconditional())
2973  return visitUnconditionalBranchInst(BI);
2974 
2975  // Change br (not X), label True, label False to: br X, label False, True
2976  Value *X = nullptr;
2977  if (match(&BI, m_Br(m_Not(m_Value(X)), m_BasicBlock(), m_BasicBlock())) &&
2978  !isa<Constant>(X)) {
2979  // Swap Destinations and condition...
2980  BI.swapSuccessors();
2981  return replaceOperand(BI, 0, X);
2982  }
2983 
2984  // If the condition is irrelevant, remove the use so that other
2985  // transforms on the condition become more effective.
2986  if (!isa<ConstantInt>(BI.getCondition()) &&
2987  BI.getSuccessor(0) == BI.getSuccessor(1))
2988  return replaceOperand(
2989  BI, 0, ConstantInt::getFalse(BI.getCondition()->getType()));
2990 
2991  // Canonicalize, for example, fcmp_one -> fcmp_oeq.
2992  CmpInst::Predicate Pred;
2993  if (match(&BI, m_Br(m_OneUse(m_FCmp(Pred, m_Value(), m_Value())),
2994  m_BasicBlock(), m_BasicBlock())) &&
2995  !isCanonicalPredicate(Pred)) {
2996  // Swap destinations and condition.
2997  CmpInst *Cond = cast<CmpInst>(BI.getCondition());
2998  Cond->setPredicate(CmpInst::getInversePredicate(Pred));
2999  BI.swapSuccessors();
3000  Worklist.push(Cond);
3001  return &BI;
3002  }
3003 
3004  return nullptr;
3005 }
3006 
3008  Value *Cond = SI.getCondition();
3009  Value *Op0;
3010  ConstantInt *AddRHS;
3011  if (match(Cond, m_Add(m_Value(Op0), m_ConstantInt(AddRHS)))) {
3012  // Change 'switch (X+4) case 1:' into 'switch (X) case -3'.
3013  for (auto Case : SI.cases()) {
3014  Constant *NewCase = ConstantExpr::getSub(Case.getCaseValue(), AddRHS);
3015  assert(isa<ConstantInt>(NewCase) &&
3016  "Result of expression should be constant");
3017  Case.setValue(cast<ConstantInt>(NewCase));
3018  }
3019  return replaceOperand(SI, 0, Op0);
3020  }
3021 
3022  KnownBits Known = computeKnownBits(Cond, 0, &SI);
3023  unsigned LeadingKnownZeros = Known.countMinLeadingZeros();
3024  unsigned LeadingKnownOnes = Known.countMinLeadingOnes();
3025 
3026  // Compute the number of leading bits we can ignore.
3027  // TODO: A better way to determine this would use ComputeNumSignBits().
3028  for (auto &C : SI.cases()) {
3029  LeadingKnownZeros = std::min(
3030  LeadingKnownZeros, C.getCaseValue()->getValue().countLeadingZeros());
3031  LeadingKnownOnes = std::min(
3032  LeadingKnownOnes, C.getCaseValue()->getValue().countLeadingOnes());
3033  }
3034 
3035  unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);
3036 
3037  // Shrink the condition operand if the new type is smaller than the old type.
3038  // But do not shrink to a non-standard type, because backend can't generate
3039  // good code for that yet.
3040  // TODO: We can make it aggressive again after fixing PR39569.
3041  if (NewWidth > 0 && NewWidth < Known.getBitWidth() &&
3042  shouldChangeType(Known.getBitWidth(), NewWidth)) {
3043  IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);
3044  Builder.SetInsertPoint(&SI);
3045  Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc");
3046 
3047  for (auto Case : SI.cases()) {
3048  APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);
3049  Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));
3050  }
3051  return replaceOperand(SI, 0, NewCond);
3052  }
3053 
3054  return nullptr;
3055 }
3056 
3058  Value *Agg = EV.getAggregateOperand();
3059 
3060  if (!EV.hasIndices())
3061  return replaceInstUsesWith(EV, Agg);
3062 
3063  if (Value *V = SimplifyExtractValueInst(Agg, EV.getIndices(),
3064  SQ.getWithInstruction(&EV)))
3065  return replaceInstUsesWith(EV, V);
3066 
3067  if (InsertValueInst *IV = dyn_cast<InsertValueInst>(Agg)) {
3068  // We're extracting from an insertvalue instruction, compare the indices
3069  const unsigned *exti, *exte, *insi, *inse;
3070  for (exti = EV.idx_begin(), insi = IV->idx_begin(),
3071  exte = EV.idx_end(), inse = IV->idx_end();
3072  exti != exte && insi != inse;
3073  ++exti, ++insi) {
3074  if (*insi != *exti)
3075  // The insert and extract both reference distinctly different elements.
3076  // This means the extract is not influenced by the insert, and we can
3077  // replace the aggregate operand of the extract with the aggregate
3078  // operand of the insert. i.e., replace
3079  // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1
3080  // %E = extractvalue { i32, { i32 } } %I, 0
3081  // with
3082  // %E = extractvalue { i32, { i32 } } %A, 0
3083  return ExtractValueInst::Create(IV->getAggregateOperand(),
3084  EV.getIndices());
3085  }
3086  if (exti == exte && insi == inse)
3087  // Both iterators are at the end: Index lists are identical. Replace
3088  // %B = insertvalue { i32, { i32 } } %A, i32 42, 1, 0
3089  // %C = extractvalue { i32, { i32 } } %B, 1, 0
3090  // with "i32 42"
3091  return replaceInstUsesWith(EV, IV->getInsertedValueOperand());
3092  if (exti == exte) {
3093  // The extract list is a prefix of the insert list. i.e. replace
3094  // %I = insertvalue { i32, { i32 } } %A, i32 42, 1, 0
3095  // %E = extractvalue { i32, { i32 } } %I, 1
3096  // with
3097  // %X = extractvalue { i32, { i32 } } %A, 1
3098  // %E = insertvalue { i32 } %X, i32 42, 0
3099  // by switching the order of the insert and extract (though the
3100  // insertvalue should be left in, since it may have other uses).
3101  Value *NewEV = Builder.CreateExtractValue(IV->getAggregateOperand(),
3102  EV.getIndices());
3103  return InsertValueInst::Create(NewEV, IV->getInsertedValueOperand(),
3104  makeArrayRef(insi, inse));
3105  }
3106  if (insi == inse)
3107  // The insert list is a prefix of the extract list
3108  // We can simply remove the common indices from the extract and make it
3109  // operate on the inserted value instead of the insertvalue result.
3110  // i.e., replace
3111  // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1
3112  // %E = extractvalue { i32, { i32 } } %I, 1, 0
3113  // with
3114  // %E extractvalue { i32 } { i32 42 }, 0
3115  return ExtractValueInst::Create(IV->getInsertedValueOperand(),
3116  makeArrayRef(exti, exte));
3117  }
3118  if (WithOverflowInst *WO = dyn_cast<WithOverflowInst>(Agg)) {
3119  // We're extracting from an overflow intrinsic, see if we're the only user,
3120  // which allows us to simplify multiple result intrinsics to simpler
3121  // things that just get one value.
3122  if (WO->hasOneUse()) {
3123  // Check if we're grabbing only the result of a 'with overflow' intrinsic
3124  // and replace it with a traditional binary instruction.
3125  if (*EV.idx_begin() == 0) {
3126  Instruction::BinaryOps BinOp = WO->getBinaryOp();
3127  Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
3128  // Replace the old instruction's uses with poison.
3129  replaceInstUsesWith(*WO, PoisonValue::get(WO->getType()));
3130  eraseInstFromFunction(*WO);
3131  return BinaryOperator::Create(BinOp, LHS, RHS);
3132  }
3133 
3134  assert(*EV.idx_begin() == 1 &&
3135  "unexpected extract index for overflow inst");
3136 
3137  // If only the overflow result is used, and the right hand side is a
3138  // constant (or constant splat), we can remove the intrinsic by directly
3139  // checking for overflow.
3140  const APInt *C;
3141  if (match(WO->getRHS(), m_APInt(C))) {
3142  // Compute the no-wrap range [X,Y) for LHS given RHS=C, then
3143  // check for the inverted range using range offset trick (i.e.
3144  // use a subtract to shift the range to bottom of either the
3145  // signed or unsigned domain and then use a single compare to
3146  // check range membership).
3147  ConstantRange NWR =
3148  ConstantRange::makeExactNoWrapRegion(WO->getBinaryOp(), *C,
3149  WO->getNoWrapKind());
3150  APInt Min = WO->isSigned() ? NWR.getSignedMin() : NWR.getUnsignedMin();
3151  NWR = NWR.subtract(Min);
3152 
3153  CmpInst::Predicate Pred;
3154  APInt NewRHSC;
3155  if (NWR.getEquivalentICmp(Pred, NewRHSC)) {
3156  auto *OpTy = WO->getRHS()->getType();
3157  auto *NewLHS = Builder.CreateSub(WO->getLHS(),
3158  ConstantInt::get(OpTy, Min));
3159  return new ICmpInst(ICmpInst::getInversePredicate(Pred), NewLHS,
3160  ConstantInt::get(OpTy, NewRHSC));
3161  }
3162  }
3163  }
3164  }
3165  if (LoadInst *L = dyn_cast<LoadInst>(Agg))
3166  // If the (non-volatile) load only has one use, we can rewrite this to a
3167  // load from a GEP. This reduces the size of the load. If a load is used
3168  // only by extractvalue instructions then this either must have been
3169  // optimized before, or it is a struct with padding, in which case we
3170  // don't want to do the transformation as it loses padding knowledge.
3171  if (L->isSimple() && L->hasOneUse()) {
3172  // extractvalue has integer indices, getelementptr has Value*s. Convert.
3173  SmallVector<Value*, 4> Indices;
3174  // Prefix an i32 0 since we need the first element.
3175  Indices.push_back(Builder.getInt32(0));
3176  for (unsigned Idx : EV.indices())
3177  Indices.push_back(Builder.getInt32(Idx));
3178 
3179  // We need to insert these at the location of the old load, not at that of
3180  // the extractvalue.
3181  Builder.SetInsertPoint(L);
3182  Value *GEP = Builder.CreateInBoundsGEP(L->getType(),
3183  L->getPointerOperand(), Indices);
3184  Instruction *NL = Builder.CreateLoad(EV.getType(), GEP);
3185  // Whatever aliasing information we had for the orignal load must also
3186  // hold for the smaller load, so propagate the annotations.
3187  AAMDNodes Nodes;
3188  L->getAAMetadata(Nodes);
3189  NL->setAAMetadata(Nodes);
3190  // Returning the load directly will cause the main loop to insert it in
3191  // the wrong spot, so use replaceInstUsesWith().
3192  return replaceInstUsesWith(EV, NL);
3193  }
3194  // We could simplify extracts from other values. Note that nested extracts may
3195  // already be simplified implicitly by the above: extract (extract (insert) )
3196  // will be translated into extract ( insert ( extract ) ) first and then just
3197  // the value inserted, if appropriate. Similarly for extracts from single-use
3198  // loads: extract (extract (load)) will be translated to extract (load (gep))
3199  // and if again single-use then via load (gep (gep)) to load (gep).
3200  // However, double extracts from e.g. function arguments or return values
3201  // aren't handled yet.
3202  return nullptr;
3203 }
3204 
3205 /// Return 'true' if the given typeinfo will match anything.
3206 static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo) {
3207  switch (Personality) {
3208  case EHPersonality::GNU_C:
3210  case EHPersonality::Rust:
3211  // The GCC C EH and Rust personality only exists to support cleanups, so
3212  // it's not clear what the semantics of catch clauses are.
3213  return false;
3215  return false;
3217  // While __gnat_all_others_value will match any Ada exception, it doesn't
3218  // match foreign exceptions (or didn't, before gcc-4.7).
3219  return false;
3228  case EHPersonality::XL_CXX:
3229  return TypeInfo->isNullValue();
3230  }
3231  llvm_unreachable("invalid enum");
3232 }
3233 
3234 static bool shorter_filter(const Value *LHS, const Value *RHS) {
3235  return
3236  cast<ArrayType>(LHS->getType())->getNumElements()
3237  <
3238  cast<ArrayType>(RHS->getType())->getNumElements();
3239 }
3240 
3242  // The logic here should be correct for any real-world personality function.
3243  // However if that turns out not to be true, the offending logic can always
3244  // be conditioned on the personality function, like the catch-all logic is.
3245  EHPersonality Personality =
3247 
3248  // Simplify the list of clauses, eg by removing repeated catch clauses
3249  // (these are often created by inlining).
3250  bool MakeNewInstruction = false; // If true, recreate using the following:
3251  SmallVector<Constant *, 16> NewClauses; // - Clauses for the new instruction;
3252  bool CleanupFlag = LI.isCleanup(); // - The new instruction is a cleanup.
3253 
3254  SmallPtrSet<Value *, 16> AlreadyCaught; // Typeinfos known caught already.
3255  for (unsigned i = 0, e = LI.getNumClauses(); i != e; ++i) {
3256  bool isLastClause = i + 1 == e;
3257  if (LI.isCatch(i)) {
3258  // A catch clause.
3259  Constant *CatchClause = LI.getClause(i);
3260  Constant *TypeInfo = CatchClause->stripPointerCasts();
3261 
3262  // If we already saw this clause, there is no point in having a second
3263  // copy of it.
3264  if (AlreadyCaught.insert(TypeInfo).second) {
3265  // This catch clause was not already seen.
3266  NewClauses.push_back(CatchClause);
3267  } else {
3268  // Repeated catch clause - drop the redundant copy.
3269  MakeNewInstruction = true;
3270  }
3271 
3272  // If this is a catch-all then there is no point in keeping any following
3273  // clauses or marking the landingpad as having a cleanup.
3274  if (isCatchAll(Personality, TypeInfo)) {
3275  if (!isLastClause)
3276  MakeNewInstruction = true;
3277  CleanupFlag = false;
3278  break;
3279  }
3280  } else {
3281  // A filter clause. If any of the filter elements were already caught
3282  // then they can be dropped from the filter. It is tempting to try to
3283  // exploit the filter further by saying that any typeinfo that does not
3284  // occur in the filter can't be caught later (and thus can be dropped).
3285  // However this would be wrong, since typeinfos can match without being
3286  // equal (for example if one represents a C++ class, and the other some
3287  // class derived from it).
3288  assert(LI.isFilter(i) && "Unsupported landingpad clause!");
3289  Constant *FilterClause = LI.getClause(i);
3290  ArrayType *FilterType = cast<ArrayType>(FilterClause->getType());
3291  unsigned NumTypeInfos = FilterType->getNumElements();
3292 
3293  // An empty filter catches everything, so there is no point in keeping any
3294  // following clauses or marking the landingpad as having a cleanup. By
3295  // dealing with this case here the following code is made a bit simpler.
3296  if (!NumTypeInfos) {
3297  NewClauses.push_back(FilterClause);
3298  if (!isLastClause)
3299  MakeNewInstruction = true;
3300  CleanupFlag = false;
3301  break;
3302  }
3303 
3304  bool MakeNewFilter = false; // If true, make a new filter.
3305  SmallVector<Constant *, 16> NewFilterElts; // New elements.
3306  if (isa<ConstantAggregateZero>(FilterClause)) {
3307  // Not an empty filter - it contains at least one null typeinfo.
3308  assert(NumTypeInfos > 0 && "Should have handled empty filter already!");
3309  Constant *TypeInfo =
3310  Constant::getNullValue(FilterType->getElementType());
3311  // If this typeinfo is a catch-all then the filter can never match.
3312  if (isCatchAll(Personality, TypeInfo)) {
3313  // Throw the filter away.
3314  MakeNewInstruction = true;
3315  continue;
3316  }
3317 
3318  // There is no point in having multiple copies of this typeinfo, so
3319  // discard all but the first copy if there is more than one.
3320  NewFilterElts.push_back(TypeInfo);
3321  if (NumTypeInfos > 1)
3322  MakeNewFilter = true;
3323  } else {
3324  ConstantArray *Filter = cast<ConstantArray>(FilterClause);
3325  SmallPtrSet<Value *, 16> SeenInFilter; // For uniquing the elements.
3326  NewFilterElts.reserve(NumTypeInfos);
3327 
3328  // Remove any filter elements that were already caught or that already
3329  // occurred in the filter. While there, see if any of the elements are
3330  // catch-alls. If so, the filter can be discarded.
3331  bool SawCatchAll = false;
3332  for (unsigned j = 0; j != NumTypeInfos; ++j) {
3333  Constant *Elt = Filter->getOperand(j);
3334  Constant *TypeInfo = Elt->stripPointerCasts();
3335  if (isCatchAll(Personality, TypeInfo)) {
3336  // This element is a catch-all. Bail out, noting this fact.
3337  SawCatchAll = true;
3338  break;
3339  }
3340 
3341  // Even if we've seen a type in a catch clause, we don't want to
3342  // remove it from the filter. An unexpected type handler may be
3343  // set up for a call site which throws an exception of the same
3344  // type caught. In order for the exception thrown by the unexpected
3345  // handler to propagate correctly, the filter must be correctly
3346  // described for the call site.
3347  //
3348  // Example:
3349  //
3350  // void unexpected() { throw 1;}
3351  // void foo() throw (int) {
3352  // std::set_unexpected(unexpected);
3353  // try {
3354  // throw 2.0;
3355  // } catch (int i) {}
3356  // }
3357 
3358  // There is no point in having multiple copies of the same typeinfo in
3359  // a filter, so only add it if we didn't already.
3360  if (SeenInFilter.insert(TypeInfo).second)
3361  NewFilterElts.push_back(cast<Constant>(Elt));
3362  }
3363  // A filter containing a catch-all cannot match anything by definition.
3364  if (SawCatchAll) {
3365  // Throw the filter away.
3366  MakeNewInstruction = true;
3367  continue;
3368  }
3369 
3370  // If we dropped something from the filter, make a new one.
3371  if (NewFilterElts.size() < NumTypeInfos)
3372  MakeNewFilter = true;
3373  }
3374  if (MakeNewFilter) {
3375  FilterType = ArrayType::get(FilterType->getElementType(),
3376  NewFilterElts.size());
3377  FilterClause = ConstantArray::get(FilterType, NewFilterElts);
3378  MakeNewInstruction = true;
3379  }
3380 
3381  NewClauses.push_back(FilterClause);
3382 
3383  // If the new filter is empty then it will catch everything so there is
3384  // no point in keeping any following clauses or marking the landingpad
3385  // as having a cleanup. The case of the original filter being empty was
3386  // already handled above.
3387  if (MakeNewFilter && !NewFilterElts.size()) {
3388  assert(MakeNewInstruction && "New filter but not a new instruction!");
3389  CleanupFlag = false;
3390  break;
3391  }
3392  }
3393  }
3394 
3395  // If several filters occur in a row then reorder them so that the shortest
3396  // filters come first (those with the smallest number of elements). This is
3397  // advantageous because shorter filters are more likely to match, speeding up
3398  // unwinding, but mostly because it increases the effectiveness of the other
3399  // filter optimizations below.
3400  for (unsigned i = 0, e = NewClauses.size(); i + 1 < e; ) {
3401  unsigned j;
3402  // Find the maximal 'j' s.t. the range [i, j) consists entirely of filters.
3403  for (j = i; j != e; ++j)
3404  if (!isa<ArrayType>(NewClauses[j]->getType()))
3405  break;
3406 
3407  // Check whether the filters are already sorted by length. We need to know
3408  // if sorting them is actually going to do anything so that we only make a
3409  // new landingpad instruction if it does.
3410  for (unsigned k = i; k + 1 < j; ++k)
3411  if (shorter_filter(NewClauses[k+1], NewClauses[k])) {
3412  // Not sorted, so sort the filters now. Doing an unstable sort would be
3413  // correct too but reordering filters pointlessly might confuse users.
3414  std::stable_sort(NewClauses.begin() + i, NewClauses.begin() + j,
3415  shorter_filter);
3416  MakeNewInstruction = true;
3417  break;
3418  }
3419 
3420  // Look for the next batch of filters.
3421  i = j + 1;
3422  }
3423 
3424  // If typeinfos matched if and only if equal, then the elements of a filter L
3425  // that occurs later than a filter F could be replaced by the intersection of
3426  // the elements of F and L. In reality two typeinfos can match without being
3427  // equal (for example if one represents a C++ class, and the other some class
3428  // derived from it) so it would be wrong to perform this transform in general.
3429  // However the transform is correct and useful if F is a subset of L. In that
3430  // case L can be replaced by F, and thus removed altogether since repeating a
3431  // filter is pointless. So here we look at all pairs of filters F and L where
3432  // L follows F in the list of clauses, and remove L if every element of F is
3433  // an element of L. This can occur when inlining C++ functions with exception
3434  // specifications.
3435  for (unsigned i = 0; i + 1 < NewClauses.size(); ++i) {
3436  // Examine each filter in turn.
3437  Value *Filter = NewClauses[i];
3438  ArrayType *FTy = dyn_cast<ArrayType>(Filter->getType());
3439  if (!FTy)
3440  // Not a filter - skip it.
3441  continue;
3442  unsigned FElts = FTy->getNumElements();
3443  // Examine each filter following this one. Doing this backwards means that
3444  // we don't have to worry about filters disappearing under us when removed.
3445  for (unsigned j = NewClauses.size() - 1; j != i; --j) {
3446  Value *LFilter = NewClauses[j];
3447  ArrayType *LTy = dyn_cast<ArrayType>(LFilter->getType());
3448  if (!LTy)
3449  // Not a filter - skip it.
3450  continue;
3451  // If Filter is a subset of LFilter, i.e. every element of Filter is also
3452  // an element of LFilter, then discard LFilter.
3453  SmallVectorImpl<Constant *>::iterator J = NewClauses.begin() + j;
3454  // If Filter is empty then it is a subset of LFilter.
3455  if (!FElts) {
3456  // Discard LFilter.
3457  NewClauses.erase(J);
3458  MakeNewInstruction = true;
3459  // Move on to the next filter.
3460  continue;
3461  }
3462  unsigned LElts = LTy->getNumElements();
3463  // If Filter is longer than LFilter then it cannot be a subset of it.
3464  if (FElts > LElts)
3465  // Move on to the next filter.
3466  continue;
3467  // At this point we know that LFilter has at least one element.
3468  if (isa<ConstantAggregateZero>(LFilter)) { // LFilter only contains zeros.
3469  // Filter is a subset of LFilter iff Filter contains only zeros (as we
3470  // already know that Filter is not longer than LFilter).
3471  if (isa<ConstantAggregateZero>(Filter)) {
3472  assert(FElts <= LElts && "Should have handled this case earlier!");
3473  // Discard LFilter.
3474  NewClauses.erase(J);
3475  MakeNewInstruction = true;
3476  }
3477  // Move on to the next filter.
3478  continue;
3479  }
3480  ConstantArray *LArray = cast<ConstantArray>(LFilter);
3481  if (isa<ConstantAggregateZero>(Filter)) { // Filter only contains zeros.
3482  // Since Filter is non-empty and contains only zeros, it is a subset of
3483  // LFilter iff LFilter contains a zero.
3484  assert(FElts > 0 && "Should have eliminated the empty filter earlier!");
3485  for (unsigned l = 0; l != LElts; ++l)
3486  if (LArray->getOperand(l)->isNullValue()) {
3487  // LFilter contains a zero - discard it.
3488  NewClauses.erase(J);
3489  MakeNewInstruction = true;
3490  break;
3491  }
3492  // Move on to the next filter.
3493  continue;
3494  }
3495  // At this point we know that both filters are ConstantArrays. Loop over
3496  // operands to see whether every element of Filter is also an element of
3497  // LFilter. Since filters tend to be short this is probably faster than
3498  // using a method that scales nicely.
3499  ConstantArray *FArray = cast<ConstantArray>(Filter);
3500  bool AllFound = true;
3501  for (unsigned f = 0; f != FElts; ++f) {
3502  Value *FTypeInfo = FArray->getOperand(f)->stripPointerCasts();
3503  AllFound = false;
3504  for (unsigned l = 0; l != LElts; ++l) {
3505  Value *LTypeInfo = LArray->getOperand(l)->stripPointerCasts();
3506  if (LTypeInfo == FTypeInfo) {
3507  AllFound = true;
3508  break;
3509  }
3510  }
3511  if (!AllFound)
3512  break;
3513  }
3514  if (AllFound) {
3515  // Discard LFilter.
3516  NewClauses.erase(J);
3517  MakeNewInstruction = true;
3518  }
3519  // Move on to the next filter.
3520  }
3521  }
3522 
3523  // If we changed any of the clauses, replace the old landingpad instruction
3524  // with a new one.
3525  if (MakeNewInstruction) {
3527  NewClauses.size());
3528  for (unsigned i = 0, e = NewClauses.size(); i != e; ++i)
3529  NLI->addClause(NewClauses[i]);
3530  // A landing pad with no clauses must have the cleanup flag set. It is
3531  // theoretically possible, though highly unlikely, that we eliminated all
3532  // clauses. If so, force the cleanup flag to true.
3533  if (NewClauses.empty())
3534  CleanupFlag = true;
3535  NLI->setCleanup(CleanupFlag);
3536  return NLI;
3537  }
3538 
3539  // Even if none of the clauses changed, we may nonetheless have understood
3540  // that the cleanup flag is pointless. Clear it if so.
3541  if (LI.isCleanup() != CleanupFlag) {
3542  assert(!CleanupFlag && "Adding a cleanup, not removing one?!");
3543  LI.setCleanup(CleanupFlag);
3544  return &LI;
3545  }
3546 
3547  return nullptr;
3548 }
3549 
3550 Value *
3552  // Try to push freeze through instructions that propagate but don't produce
3553  // poison as far as possible. If an operand of freeze follows three
3554  // conditions 1) one-use, 2) does not produce poison, and 3) has all but one
3555  // guaranteed-non-poison operands then push the freeze through to the one
3556  // operand that is not guaranteed non-poison. The actual transform is as
3557  // follows.
3558  // Op1 = ... ; Op1 can be posion
3559  // Op0 = Inst(Op1, NonPoisonOps...) ; Op0 has only one use and only have
3560  // ; single guaranteed-non-poison operands
3561  // ... = Freeze(Op0)
3562  // =>
3563  // Op1 = ...
3564  // Op1.fr = Freeze(Op1)
3565  // ... = Inst(Op1.fr, NonPoisonOps...)
3566  auto *OrigOp = OrigFI.getOperand(0);
3567  auto *OrigOpInst = dyn_cast<Instruction>(OrigOp);
3568 
3569  // While we could change the other users of OrigOp to use freeze(OrigOp), that
3570  // potentially reduces their optimization potential, so let's only do this iff
3571  // the OrigOp is only used by the freeze.
3572  if (!OrigOpInst || !OrigOpInst->hasOneUse() || isa<PHINode>(OrigOp) ||
3573  canCreateUndefOrPoison(dyn_cast<Operator>(OrigOp)))
3574  return nullptr;
3575 
3576  // If operand is guaranteed not to be poison, there is no need to add freeze
3577  // to the operand. So we first find the operand that is not guaranteed to be
3578  // poison.
3579  Use *MaybePoisonOperand = nullptr;
3580  for (Use &U : OrigOpInst->operands()) {
3581  if (isGuaranteedNotToBeUndefOrPoison(U.get()))
3582  continue;
3583  if (!MaybePoisonOperand)
3584  MaybePoisonOperand = &U;
3585  else
3586  return nullptr;
3587  }
3588 
3589  // If all operands are guaranteed to be non-poison, we can drop freeze.
3590  if (!MaybePoisonOperand)
3591  return OrigOp;
3592 
3593  auto *FrozenMaybePoisonOperand = new FreezeInst(
3594  MaybePoisonOperand->get(), MaybePoisonOperand->get()->getName() + ".fr");
3595 
3596  replaceUse(*MaybePoisonOperand, FrozenMaybePoisonOperand);
3597  FrozenMaybePoisonOperand->insertBefore(OrigOpInst);
3598  return OrigOp;
3599 }
3600 
3602  Value *Op = FI.getOperand(0);
3603 
3604  if (isa<Constant>(Op))
3605  return false;
3606 
3607  bool Changed = false;
3608  Op->replaceUsesWithIf(&FI, [&](Use &U) -> bool {
3609  bool Dominates = DT.dominates(&FI, U);
3610  Changed |= Dominates;
3611  return Dominates;
3612  });
3613 
3614  return Changed;
3615 }
3616 
3618  Value *Op0 = I.getOperand(0);
3619 
3620  if (Value *V = SimplifyFreezeInst(Op0, SQ.getWithInstruction(&I)))
3621  return replaceInstUsesWith(I, V);
3622 
3623  // freeze (phi const, x) --> phi const, (freeze x)
3624  if (auto *PN = dyn_cast<PHINode>(Op0)) {
3625  if (Instruction *NV = foldOpIntoPhi(I, PN))
3626  return NV;
3627  }
3628 
3629  if (Value *NI = pushFreezeToPreventPoisonFromPropagating(I))
3630  return replaceInstUsesWith(I, NI);
3631 
3632  if (match(Op0, m_Undef())) {
3633  // If I is freeze(undef), see its uses and fold it to the best constant.
3634  // - or: pick -1
3635  // - select's condition: pick the value that leads to choosing a constant
3636  // - other ops: pick 0
3637  Constant *BestValue = nullptr;
3638  Constant *NullValue = Constant::getNullValue(I.getType());
3639  for (const auto *U : I.users()) {
3640  Constant *C = NullValue;
3641 
3642  if (match(U, m_Or(m_Value(), m_Value())))
3643  C = Constant::getAllOnesValue(I.getType());
3644  else if (const auto *SI = dyn_cast<SelectInst>(U)) {
3645  if (SI->getCondition() == &I) {
3646  APInt CondVal(1, isa<Constant>(SI->getFalseValue()) ? 0 : 1);
3647  C = Constant::getIntegerValue(I.getType(), CondVal);
3648  }
3649  }
3650 
3651  if (!BestValue)
3652  BestValue = C;
3653  else if (BestValue != C)
3654  BestValue = NullValue;
3655  }
3656 
3657  return replaceInstUsesWith(I, BestValue);
3658  }
3659 
3660  // Replace all dominated uses of Op to freeze(Op).
3661  if (freezeDominatedUses(I))
3662  return &I;
3663 
3664  return nullptr;
3665 }
3666 
3667 /// Try to move the specified instruction from its current block into the
3668 /// beginning of DestBlock, which can only happen if it's safe to move the
3669 /// instruction past all of the instructions between it and the end of its
3670 /// block.
3671 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
3672  assert(I->getSingleUndroppableUse() && "Invariants didn't hold!");
3673  BasicBlock *SrcBlock = I->getParent();
3674 
3675  // Cannot move control-flow-involving, volatile loads, vaarg, etc.
3676  if (isa<PHINode>(I) || I->isEHPad() || I->mayHaveSideEffects() ||
3677  I->isTerminator())
3678  return false;
3679 
3680  // Do not sink static or dynamic alloca instructions. Static allocas must
3681  // remain in the entry block, and dynamic allocas must not be sunk in between
3682  // a stacksave / stackrestore pair, which would incorrectly shorten its
3683  // lifetime.
3684  if (isa<AllocaInst>(I))
3685  return false;
3686 
3687  // Do not sink into catchswitch blocks.
3688  if (isa<CatchSwitchInst>(DestBlock->getTerminator()))
3689  return false;
3690 
3691  // Do not sink convergent call instructions.
3692  if (auto *CI = dyn_cast<CallInst>(I)) {
3693  if (CI->isConvergent())
3694  return false;
3695  }
3696  // We can only sink load instructions if there is nothing between the load and
3697  // the end of block that could change the value.
3698  if (I->mayReadFromMemory()) {
3699  // We don't want to do any sophisticated alias analysis, so we only check
3700  // the instructions after I in I's parent block if we try to sink to its
3701  // successor block.
3702  if (DestBlock->getUniquePredecessor() != I->getParent())
3703  return false;
3704  for (BasicBlock::iterator Scan = I->getIterator(),
3705  E = I->getParent()->end();
3706  Scan != E; ++Scan)
3707  if (Scan->mayWriteToMemory())
3708  return false;
3709  }
3710 
3711  I->dropDroppableUses([DestBlock](const Use *U) {
3712  if (auto *I = dyn_cast<Instruction>(U->getUser()))
3713  return I->getParent() != DestBlock;
3714  return true;
3715  });
3716  /// FIXME: We could remove droppable uses that are not dominated by
3717  /// the new position.
3718 
3719  BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();
3720  I->moveBefore(&*InsertPos);
3721  ++NumSunkInst;
3722 
3723  // Also sink all related debug uses from the source basic block. Otherwise we
3724  // get debug use before the def. Attempt to salvage debug uses first, to
3725  // maximise the range variables have location for. If we cannot salvage, then
3726  // mark the location undef: we know it was supposed to receive a new location
3727  // here, but that computation has been sunk.
3729  findDbgUsers(DbgUsers, I);
3730  // Process the sinking DbgUsers in reverse order, as we only want to clone the
3731  // last appearing debug intrinsic for each given variable.
3733  for (DbgVariableIntrinsic *DVI : DbgUsers)
3734  if (DVI->getParent() == SrcBlock)
3735  DbgUsersToSink.push_back(DVI);
3736  llvm::sort(DbgUsersToSink,
3737  [](auto *A, auto *B) { return B->comesBefore(A); });
3738 
3740  SmallSet<DebugVariable, 4> SunkVariables;
3741  for (auto User : DbgUsersToSink) {
3742  // A dbg.declare instruction should not be cloned, since there can only be
3743  // one per variable fragment. It should be left in the original place
3744  // because the sunk instruction is not an alloca (otherwise we could not be
3745  // here).
3746  if (isa<DbgDeclareInst>(User))
3747  continue;
3748 
3749  DebugVariable DbgUserVariable =
3750  DebugVariable(User->getVariable(), User->getExpression(),
3751  User->getDebugLoc()->getInlinedAt());
3752 
3753  if (!SunkVariables.insert(DbgUserVariable).second)
3754  continue;
3755 
3756  DIIClones.emplace_back(cast<DbgVariableIntrinsic>(User->clone()));
3757  if (isa<DbgDeclareInst>(User) && isa<CastInst>(I))
3758  DIIClones.back()->replaceVariableLocationOp(I, I->getOperand(0));
3759  LLVM_DEBUG(dbgs() << "CLONE: " << *DIIClones.back() << '\n');
3760  }
3761 
3762  // Perform salvaging without the clones, then sink the clones.
3763  if (!DIIClones.empty()) {
3764  salvageDebugInfoForDbgValues(*I, DbgUsers);
3765  // The clones are in reverse order of original appearance, reverse again to
3766  // maintain the original order.
3767  for (auto &DIIClone : llvm::reverse(DIIClones)) {
3768  DIIClone->insertBefore(&*InsertPos);
3769  LLVM_DEBUG(dbgs() << "SINK: " << *DIIClone << '\n');
3770  }
3771  }
3772 
3773  return true;
3774 }
3775 
3777  while (!Worklist.isEmpty()) {
3778  // Walk deferred instructions in reverse order, and push them to the
3779  // worklist, which means they'll end up popped from the worklist in-order.
3780  while (Instruction *I = Worklist.popDeferred()) {
3781  // Check to see if we can DCE the instruction. We do this already here to
3782  // reduce the number of uses and thus allow other folds to trigger.
3783  // Note that eraseInstFromFunction() may push additional instructions on
3784  // the deferred worklist, so this will DCE whole instruction chains.
3785  if (isInstructionTriviallyDead(I, &TLI)) {
3786  eraseInstFromFunction(*I);
3787  ++NumDeadInst;
3788  continue;
3789  }
3790 
3791  Worklist.push(I);
3792  }
3793 
3794  Instruction *I = Worklist.removeOne();
3795  if (I == nullptr) continue; // skip null values.
3796 
3797  // Check to see if we can DCE the instruction.
3798  if (isInstructionTriviallyDead(I, &TLI)) {
3799  eraseInstFromFunction(*I);
3800  ++NumDeadInst;
3801  continue;
3802  }
3803 
3804  if (!DebugCounter::shouldExecute(VisitCounter))
3805  continue;
3806 
3807  // Instruction isn't dead, see if we can constant propagate it.
3808  if (!I->use_empty() &&
3809  (I->getNumOperands() == 0 || isa<Constant>(I->getOperand(0)))) {
3810  if (Constant *C = ConstantFoldInstruction(I, DL, &TLI)) {
3811  LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I
3812  << '\n');
3813 
3814  // Add operands to the worklist.
3815  replaceInstUsesWith(*I, C);
3816  ++NumConstProp;
3817  if (isInstructionTriviallyDead(I, &TLI))
3818  eraseInstFromFunction(*I);
3819  MadeIRChange = true;
3820  continue;
3821  }
3822  }
3823 
3824  // See if we can trivially sink this instruction to its user if we can
3825  // prove that the successor is not executed more frequently than our block.
3826  if (EnableCodeSinking)
3827  if (Use *SingleUse = I->getSingleUndroppableUse()) {
3828  BasicBlock *BB = I->getParent();
3829  Instruction *UserInst = cast<Instruction>(SingleUse->getUser());
3830  BasicBlock *UserParent;
3831 
3832  // Get the block the use occurs in.
3833  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
3834  UserParent = PN->getIncomingBlock(*SingleUse);
3835  else
3836  UserParent = UserInst->getParent();
3837 
3838  // Try sinking to another block. If that block is unreachable, then do
3839  // not bother. SimplifyCFG should handle it.
3840  if (UserParent != BB && DT.isReachableFromEntry(UserParent)) {
3841  // See if the user is one of our successors that has only one
3842  // predecessor, so that we don't have to split the critical edge.
3843  bool ShouldSink = UserParent->getUniquePredecessor() == BB;
3844  // Another option where we can sink is a block that ends with a
3845  // terminator that does not pass control to other block (such as
3846  // return or unreachable). In this case:
3847  // - I dominates the User (by SSA form);
3848  // - the User will be executed at most once.
3849  // So sinking I down to User is always profitable or neutral.
3850  if (!ShouldSink) {
3851  auto *Term = UserParent->getTerminator();
3852  ShouldSink = isa<ReturnInst>(Term) || isa<UnreachableInst>(Term);
3853  }
3854  if (ShouldSink) {
3855  assert(DT.dominates(BB, UserParent) &&
3856  "Dominance relation broken?");
3857  // Okay, the CFG is simple enough, try to sink this instruction.
3858  if (TryToSinkInstruction(I, UserParent)) {
3859  LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
3860  MadeIRChange = true;
3861  // We'll add uses of the sunk instruction below, but since sinking
3862  // can expose opportunities for it's *operands* add them to the
3863  // worklist
3864  for (Use &U : I->operands())
3865  if (Instruction *OpI = dyn_cast<Instruction>(U.get()))
3866  Worklist.push(OpI);
3867  }
3868  }
3869  }
3870  }
3871 
3872  // Now that we have an instruction, try combining it to simplify it.
3873  Builder.SetInsertPoint(I);
3874  Builder.CollectMetadataToCopy(
3875  I, {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
3876 
3877 #ifndef NDEBUG
3878  std::string OrigI;
3879 #endif
3880  LLVM_DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str(););
3881  LLVM_DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n');
3882 
3883  if (Instruction *Result = visit(*I)) {
3884  ++NumCombined;
3885  // Should we replace the old instruction with a new one?
3886  if (Result != I) {
3887  LLVM_DEBUG(dbgs() << "IC: Old = " << *I << '\n'
3888  << " New = " << *Result << '\n');
3889 
3890  Result->copyMetadata(*I,
3891  {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
3892  // Everything uses the new instruction now.
3893  I->replaceAllUsesWith(Result);
3894 
3895  // Move the name to the new instruction first.
3896  Result->takeName(I);
3897 
3898  // Insert the new instruction into the basic block...
3899  BasicBlock *InstParent = I->getParent();
3900  BasicBlock::iterator InsertPos = I->getIterator();
3901 
3902  // Are we replace a PHI with something that isn't a PHI, or vice versa?
3903  if (isa<PHINode>(Result) != isa<PHINode>(I)) {
3904  // We need to fix up the insertion point.
3905  if (isa<PHINode>(I)) // PHI -> Non-PHI
3906  InsertPos = InstParent->getFirstInsertionPt();
3907  else // Non-PHI -> PHI
3908  InsertPos = InstParent->getFirstNonPHI()->getIterator();
3909  }
3910 
3911  InstParent->getInstList().insert(InsertPos, Result);
3912 
3913  // Push the new instruction and any users onto the worklist.
3914  Worklist.pushUsersToWorkList(*Result);
3915  Worklist.push(Result);
3916 
3917  eraseInstFromFunction(*I);
3918  } else {
3919  LLVM_DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n'
3920  << " New = " << *I << '\n');
3921 
3922  // If the instruction was modified, it's possible that it is now dead.
3923  // if so, remove it.
3924  if (isInstructionTriviallyDead(I, &TLI)) {
3925  eraseInstFromFunction(*I);
3926  } else {
3927  Worklist.pushUsersToWorkList(*I);
3928  Worklist.push(I);
3929  }
3930  }
3931  MadeIRChange = true;
3932  }
3933  }
3934 
3935  Worklist.zap();
3936  return MadeIRChange;
3937 }
3938 
3939 // Track the scopes used by !alias.scope and !noalias. In a function, a
3940 // @llvm.experimental.noalias.scope.decl is only useful if that scope is used
3941 // by both sets. If not, the declaration of the scope can be safely omitted.
3942 // The MDNode of the scope can be omitted as well for the instructions that are
3943 // part of this function. We do not do that at this point, as this might become
3944 // too time consuming to do.
3946  SmallPtrSet<const MDNode *, 8> UsedAliasScopesAndLists;
3947  SmallPtrSet<const MDNode *, 8> UsedNoAliasScopesAndLists;
3948 
3949 public:
3951  // This seems to be faster than checking 'mayReadOrWriteMemory()'.
3952  if (!I->hasMetadataOtherThanDebugLoc())
3953  return;
3954 
3955  auto Track = [](Metadata *ScopeList, auto &Container) {
3956  const auto *MDScopeList = dyn_cast_or_null<MDNode>(ScopeList);
3957  if (!MDScopeList || !Container.insert(MDScopeList).second)
3958  return;
3959  for (auto &MDOperand : MDScopeList->operands())
3960  if (auto *MDScope = dyn_cast<MDNode>(MDOperand))
3961  Container.insert(MDScope);
3962  };
3963 
3964  Track(I->getMetadata(LLVMContext::MD_alias_scope), UsedAliasScopesAndLists);
3965  Track(I->getMetadata(LLVMContext::MD_noalias), UsedNoAliasScopesAndLists);
3966  }
3967 
3969  NoAliasScopeDeclInst *Decl = dyn_cast<NoAliasScopeDeclInst>(Inst);
3970  if (!Decl)
3971  return false;
3972 
3973  assert(Decl->use_empty() &&
3974  "llvm.experimental.noalias.scope.decl in use ?");
3975  const MDNode *MDSL = Decl->getScopeList();
3976  assert(MDSL->getNumOperands() == 1 &&
3977  "llvm.experimental.noalias.scope should refer to a single scope");
3978  auto &MDOperand = MDSL->getOperand(0);
3979  if (auto *MD = dyn_cast<MDNode>(MDOperand))
3980  return !UsedAliasScopesAndLists.contains(MD) ||
3981  !UsedNoAliasScopesAndLists.contains(MD);
3982 
3983  // Not an MDNode ? throw away.
3984  return true;
3985  }
3986 };
3987 
3988 /// Populate the IC worklist from a function, by walking it in depth-first
3989 /// order and adding all reachable code to the worklist.
3990 ///
3991 /// This has a couple of tricks to make the code faster and more powerful. In
3992 /// particular, we constant fold and DCE instructions as we go, to avoid adding
3993 /// them to the worklist (this significantly speeds up instcombine on code where
3994 /// many instructions are dead or constant). Additionally, if we find a branch
3995 /// whose condition is a known constant, we only visit the reachable successors.
3997  const TargetLibraryInfo *TLI,
3998  InstCombineWorklist &ICWorklist) {
3999  bool MadeIRChange = false;
4002  Worklist.push_back(&F.front());
4003 
4004  SmallVector<Instruction*, 128> InstrsForInstCombineWorklist;
4005  DenseMap<Constant *, Constant *> FoldedConstants;
4006  AliasScopeTracker SeenAliasScopes;
4007 
4008  do {
4009  BasicBlock *BB = Worklist.pop_back_val();
4010 
4011  // We have now visited this block! If we've already been here, ignore it.
4012  if (!Visited.insert(BB).second)
4013  continue;
4014 
4015  for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
4016  Instruction *Inst = &*BBI++;
4017 
4018  // ConstantProp instruction if trivially constant.
4019  if (!Inst->use_empty() &&
4020  (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
4021  if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI)) {
4022  LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *Inst
4023  << '\n');
4024  Inst->replaceAllUsesWith(C);
4025  ++NumConstProp;
4026  if (isInstructionTriviallyDead(Inst, TLI))
4027  Inst->eraseFromParent();
4028  MadeIRChange = true;
4029  continue;
4030  }
4031 
4032  // See if we can constant fold its operands.
4033  for (Use &U : Inst->operands()) {
4034  if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))
4035  continue;
4036 
4037  auto *C = cast<Constant>(U);
4038  Constant *&FoldRes = FoldedConstants[C];
4039  if (!FoldRes)
4040  FoldRes = ConstantFoldConstant(C, DL, TLI);
4041 
4042  if (FoldRes != C) {
4043  LLVM_DEBUG(dbgs() << "IC: ConstFold operand of: " << *Inst
4044  << "\n Old = " << *C
4045  << "\n New = " << *FoldRes << '\n');
4046  U = FoldRes;
4047  MadeIRChange = true;
4048  }
4049  }
4050 
4051  // Skip processing debug and pseudo intrinsics in InstCombine. Processing
4052  // these call instructions consumes non-trivial amount of time and
4053  // provides no value for the optimization.
4054  if (!Inst->isDebugOrPseudoInst()) {
4055  InstrsForInstCombineWorklist.push_back(Inst);
4056  SeenAliasScopes.analyse(Inst);
4057  }
4058  }
4059 
4060  // Recursively visit successors. If this is a branch or switch on a
4061  // constant, only visit the reachable successor.
4062  Instruction *TI = BB->getTerminator();
4063  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
4064  if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
4065  bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
4066  BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
4067  Worklist.push_back(ReachableBB);
4068  continue;
4069  }
4070  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
4071  if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
4072  Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor());
4073  continue;
4074  }
4075  }
4076 
4077  append_range(Worklist, successors(TI));
4078  } while (!Worklist.empty());
4079 
4080  // Remove instructions inside unreachable blocks. This prevents the
4081  // instcombine code from having to deal with some bad special cases, and
4082  // reduces use counts of instructions.
4083  for (BasicBlock &BB : F) {
4084  if (Visited.count(&BB))
4085  continue;
4086 
4087  unsigned NumDeadInstInBB;
4088  unsigned NumDeadDbgInstInBB;
4089  std::tie(NumDeadInstInBB, NumDeadDbgInstInBB) =
4091 
4092  MadeIRChange |= NumDeadInstInBB + NumDeadDbgInstInBB > 0;
4093  NumDeadInst += NumDeadInstInBB;
4094  }
4095 
4096  // Once we've found all of the instructions to add to instcombine's worklist,
4097  // add them in reverse order. This way instcombine will visit from the top
4098  // of the function down. This jives well with the way that it adds all uses
4099  // of instructions to the worklist after doing a transformation, thus avoiding
4100  // some N^2 behavior in pathological cases.
4101  ICWorklist.reserve(InstrsForInstCombineWorklist.size());
4102  for (Instruction *Inst : reverse(InstrsForInstCombineWorklist)) {
4103  // DCE instruction if trivially dead. As we iterate in reverse program
4104  // order here, we will clean up whole chains of dead instructions.
4105  if (isInstructionTriviallyDead(Inst, TLI) ||
4106  SeenAliasScopes.isNoAliasScopeDeclDead(Inst)) {
4107  ++NumDeadInst;
4108  LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
4109  salvageDebugInfo(*Inst);
4110  Inst->eraseFromParent();
4111  MadeIRChange = true;
4112  continue;
4113  }
4114 
4115  ICWorklist.push(Inst);
4116  }
4117 
4118  return MadeIRChange;
4119 }
4120 
4122  Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA,
4125  ProfileSummaryInfo *PSI, unsigned MaxIterations, LoopInfo *LI) {
4126  auto &DL = F.getParent()->getDataLayout();
4127  MaxIterations = std::min(MaxIterations, LimitMaxIterations.getValue());
4128 
4129  /// Builder - This is an IRBuilder that automatically inserts new
4130  /// instructions into the worklist when they are created.
4132  F.getContext(), TargetFolder(DL),
4133  IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {
4134  Worklist.add(I);
4135  if (auto *Assume = dyn_cast<AssumeInst>(I))
4136  AC.registerAssumption(Assume);
4137  }));
4138 
4139  // Lower dbg.declare intrinsics otherwise their value may be clobbered
4140  // by instcombiner.
4141  bool MadeIRChange = false;
4143  MadeIRChange = LowerDbgDeclare(F);
4144 
4145  // Iterate while there is work to do.
4146  unsigned Iteration = 0;
4147  while (true) {
4148  ++NumWorklistIterations;
4149  ++Iteration;
4150 
4151  if (Iteration > InfiniteLoopDetectionThreshold) {
4153  "Instruction Combining seems stuck in an infinite loop after " +
4154  Twine(InfiniteLoopDetectionThreshold) + " iterations.");
4155  }
4156 
4157  if (Iteration > MaxIterations) {
4158  LLVM_DEBUG(dbgs() << "\n\n[IC] Iteration limit #" << MaxIterations
4159  << " on " << F.getName()
4160  << " reached; stopping before reaching a fixpoint\n");
4161  break;
4162  }
4163 
4164  LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
4165  << F.getName() << "\n");
4166 
4167  MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
4168 
4169  InstCombinerImpl IC(Worklist, Builder, F.hasMinSize(), AA, AC, TLI, TTI, DT,
4170  ORE, BFI, PSI, DL, LI);
4172 
4173  if (!IC.run())
4174  break;
4175 
4176  MadeIRChange = true;
4177  }
4178 
4179  return MadeIRChange;
4180 }
4181 
4183 
4184 InstCombinePass::InstCombinePass(unsigned MaxIterations)
4185  : MaxIterations(MaxIterations) {}
4186 
4189  auto &AC = AM.getResult<AssumptionAnalysis>(F);
4190  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
4191  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
4193  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
4194 
4195  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
4196 
4197  auto *AA = &AM.getResult<AAManager>(F);
4198  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
4199  ProfileSummaryInfo *PSI =
4200  MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
4201  auto *BFI = (PSI && PSI->hasProfileSummary()) ?
4202  &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
4203 
4204  if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, TTI, DT, ORE,
4205  BFI, PSI, MaxIterations, LI))
4206  // No changes, all analyses are preserved.
4207  return PreservedAnalyses::all();
4208 
4209  // Mark all the analyses that instcombine updates as preserved.
4210  PreservedAnalyses PA;
4211  PA.preserveSet<CFGAnalyses>();
4212  return PA;
4213 }
4214 
4216  AU.setPreservesCFG();
4229 }
4230 
4232  if (skipFunction(F))
4233  return false;
4234 
4235  // Required analyses.
4236  auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4237  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
4238  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
4239  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
4240  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
4241  auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
4242 
4243  // Optional analyses.
4244  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
4245  auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
4246  ProfileSummaryInfo *PSI =
4247  &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
4249  (PSI && PSI->hasProfileSummary()) ?
4250  &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
4251  nullptr;
4252 
4253  return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, TTI, DT, ORE,
4254  BFI, PSI, MaxIterations, LI);
4255 }
4256 
4258 
4260  : FunctionPass(ID), MaxIterations(InstCombineDefaultMaxIterations) {
4262 }
4263 
4265  : FunctionPass(ID), MaxIterations(MaxIterations) {
4267 }
4268 
4270  "Combine redundant instructions", false, false)
4282 
4283 // Initialization Routines
4286 }
4287 
4290 }
4291 
4293  return new InstructionCombiningPass();
4294 }
4295 
4297  return new InstructionCombiningPass(MaxIterations);
4298 }
4299 
4302 }
llvm::EHPersonality::MSVC_CXX
@ MSVC_CXX
llvm::NoAliasScopeDeclInst
Definition: IntrinsicInst.h:1205
i
i
Definition: README.txt:29
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::ExtractValueInst::hasIndices
bool hasIndices() const
Definition: Instructions.h:2447
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1051
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1233
foldSelectGEP
static Instruction * foldSelectGEP(GetElementPtrInst &GEP, InstCombiner::BuilderTy &Builder)
Thread a GEP operation with constant indices through the constant true/false arms of a select.
Definition: InstructionCombining.cpp:1869
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:298
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:274
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2313
llvm::LandingPadInst::Create
static LandingPadInst * Create(Type *RetTy, unsigned NumReservedClauses, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedClauses is a hint for the number of incoming clauses that this landingpad w...
Definition: Instructions.cpp:214
llvm::InstCombineWorklist::reserve
void reserve(size_t Size)
Definition: InstCombineWorklist.h:81
llvm::Instruction::isAssociative
bool isAssociative() const LLVM_READONLY
Return true if the instruction is associative:
Definition: Instruction.cpp:743
llvm::GetElementPtrInst::setIsInBounds
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
Definition: Instructions.cpp:1800
llvm::InstCombinerImpl::tryFactorization
Value * tryFactorization(BinaryOperator &, Instruction::BinaryOps, Value *, Value *, Value *, Value *)
This tries to simplify binary operations by factorizing out common terms (e.
Definition: InstructionCombining.cpp:617
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:102
llvm::APInt::sadd_ov
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1959
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
llvm::LandingPadInst::isCleanup
bool isCleanup() const
Return 'true' if this landingpad instruction is a cleanup.
Definition: Instructions.h:2926
llvm::TargetTransformInfo::instCombineIntrinsic
Optional< Instruction * > instCombineIntrinsic(InstCombiner &IC, IntrinsicInst &II) const
Targets can implement their own combinations for target-specific intrinsics.
Definition: TargetTransformInfo.cpp:297
llvm::InvokeInst::Create
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value * > Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
Definition: Instructions.h:3787
llvm::Type::getInt1Ty
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:200
llvm::InstCombinerImpl::visitGetElementPtrInst
Instruction * visitGetElementPtrInst(GetElementPtrInst &GEP)
Definition: InstructionCombining.cpp:1895
foldOperationIntoSelectOperand
static Value * foldOperationIntoSelectOperand(Instruction &I, Value *SO, InstCombiner::BuilderTy &Builder)
Definition: InstructionCombining.cpp:956
llvm::CastInst::CreatePointerBitCastOrAddrSpaceCast
static CastInst * CreatePointerBitCastOrAddrSpaceCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast or an AddrSpaceCast cast instruction.
Definition: Instructions.cpp:3169
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::ConvertDebugDeclareToDebugValue
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===------------------------------------------------------------------—===// Dbg Intrinsic utilities
Definition: Local.cpp:1441
llvm::Instruction::getModule
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:66
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:217
llvm::ReturnInst
Return a value (possibly void), from a function.
Definition: Instructions.h:2980
llvm::PatternMatch::m_Mask
Definition: PatternMatch.h:1524
llvm::EHPersonality::GNU_C_SjLj
@ GNU_C_SjLj
leftDistributesOverRight
static bool leftDistributesOverRight(Instruction::BinaryOps LOp, Instruction::BinaryOps ROp)
Return whether "X LOp (Y ROp Z)" is always equal to "(X LOp Y) ROp (X LOp Z)".
Definition: InstructionCombining.cpp:549
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:112
llvm::Instruction::isBitwiseLogicOp
static bool isBitwiseLogicOp(unsigned Opcode)
Determine if the Opcode is and/or/xor.
Definition: Instruction.h:215
llvm::Value::hasOneUse
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:435
llvm::generic_gep_type_iterator
Definition: GetElementPtrTypeIterator.h:31
llvm::InstCombinerImpl::visitBranchInst
Instruction * visitBranchInst(BranchInst &BI)
Definition: InstructionCombining.cpp:2971
llvm::Intrinsic::getDeclaration
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=None)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1336
Metadata.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4583
llvm::InstructionCombiningPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: InstructionCombining.cpp:4215
llvm::InstCombinerImpl::run
bool run()
Run the combiner over the entire worklist until it is empty.
Definition: InstructionCombining.cpp:3776
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::EHPersonality::GNU_Ada
@ GNU_Ada
IntrinsicInst.h
llvm::SimplifyQuery
Definition: InstructionSimplify.h:94
llvm::DIBuilder
Definition: DIBuilder.h:41
LLVMPassRegistryRef
struct LLVMOpaquePassRegistry * LLVMPassRegistryRef
Definition: Types.h:130
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
llvm::InstCombiner::targetInstCombineIntrinsic
Optional< Instruction * > targetInstCombineIntrinsic(IntrinsicInst &II)
Definition: InstructionCombining.cpp:168
llvm::InstCombinerImpl::foldBinOpIntoSelectOrPhi
Instruction * foldBinOpIntoSelectOrPhi(BinaryOperator &I)
This is a convenience wrapper function for the above two functions.
Definition: InstructionCombining.cpp:1253
llvm::PointerType::getElementType
Type * getElementType() const
Definition: DerivedTypes.h:672
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::APInt::ule
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1243
TargetFolder.h
Pass.h
llvm::IntrinsicInst::getIntrinsicID
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:52
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:623
llvm::PatternMatch::m_SplatOrUndefMask
Definition: PatternMatch.h:1545
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5194
llvm::InstCombinerImpl::visitExtractValueInst
Instruction * visitExtractValueInst(ExtractValueInst &EV)
Definition: InstructionCombining.cpp:3057
C1
instcombine should handle this C2 when C1
Definition: README.txt:263
llvm::ProfileSummaryInfo::hasProfileSummary
bool hasProfileSummary() const
Returns true if profile summary is available.
Definition: ProfileSummaryInfo.h:68
GetElementPtrTypeIterator.h
llvm::isGuaranteedNotToBeUndefOrPoison
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
Definition: ValueTracking.cpp:5235
llvm::Type::getScalarType
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:319
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::PatternMatch::m_SpecificMask
Definition: PatternMatch.h:1539
llvm::LandingPadInst
The landingpad instruction holds all of the information necessary to generate correct exception handl...
Definition: Instructions.h:2879
llvm::InstCombiner::targetSimplifyDemandedVectorEltsIntrinsic
Optional< Value * > targetSimplifyDemandedVectorEltsIntrinsic(IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, APInt &UndefElts2, APInt &UndefElts3, std::function< void(Instruction *, unsigned, APInt, APInt &)> SimplifyAndSetOp)
Definition: InstructionCombining.cpp:187
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1008
llvm::FunctionPass::skipFunction
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:163
ErrorHandling.h
llvm::PatternMatch::m_CombineOr
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:210
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
LazyBlockFrequencyInfo.h
llvm::Type::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:733
llvm::IRBuilder< TargetFolder, IRBuilderCallbackInserter >
llvm::InsertValueInst::Create
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:2524
getBinOpsForFactorization
static Instruction::BinaryOps getBinOpsForFactorization(Instruction::BinaryOps TopOpcode, BinaryOperator *Op, Value *&LHS, Value *&RHS)
This function predicates factorization using distributive laws.
Definition: InstructionCombining.cpp:598
llvm::CastInst::Create
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Definition: Instructions.cpp:3040
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:686
llvm::CmpInst::ICMP_NE
@ ICMP_NE
not equal
Definition: InstrTypes.h:742
llvm::CmpInst::getInversePredicate
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Definition: InstrTypes.h:820
llvm::findDbgUsers
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic * > &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: DebugInfo.cpp:102
llvm::ConstantRange::getEquivalentICmp
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
Definition: ConstantRange.cpp:150
ValueTracking.h
Local.h
OptimizationRemarkEmitter.h
llvm::isAllocLikeFn
bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates memory (either malloc,...
Definition: MemoryBuiltins.cpp:306
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::NoAliasScopeDeclInst::getScopeList
MDNode * getScopeList() const
Definition: IntrinsicInst.h:1215
llvm::PatternMatch::m_Br
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
Definition: PatternMatch.h:1741
llvm::InstCombiner::MaxArraySizeForCombine
uint64_t MaxArraySizeForCombine
Maximum size of array considered when transforming.
Definition: InstCombiner.h:51
APInt.h
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
llvm::LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
Definition: LazyBlockFrequencyInfo.cpp:62
llvm::InstructionCombiningPass::InstructionCombiningPass
InstructionCombiningPass()
Definition: InstructionCombining.cpp:4259
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
NL
#define NL
Definition: DetailedRecordsBackend.cpp:30
DenseMap.h
llvm::KnownBits::getConstant
const APInt & getConstant() const
Returns the value when all bits have a known value.
Definition: KnownBits.h:57
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1581
llvm::InstCombinerImpl::FoldOpIntoSelect
Instruction * FoldOpIntoSelect(Instruction &Op, SelectInst *SI)
Given an instruction with a select as one operand and a constant as the other operand,...
Definition: InstructionCombining.cpp:1002
llvm::InstCombinerImpl::visitAllocSite
Instruction * visitAllocSite(Instruction &FI)
Definition: InstructionCombining.cpp:2667
MemoryBuiltins.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
llvm::Instruction::isShift
bool isShift() const
Definition: Instruction.h:167
EHPersonalities.h
InfiniteLoopDetectionThreshold
static cl::opt< unsigned > InfiniteLoopDetectionThreshold("instcombine-infinite-loop-threshold", cl::desc("Number of instruction combining iterations considered an " "infinite loop"), cl::init(InstCombineDefaultInfiniteLoopThreshold), cl::Hidden)
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:134
llvm::ExtractValueInst::indices
iterator_range< idx_iterator > indices() const
Definition: Instructions.h:2425
llvm::SimplifyFreezeInst
Value * SimplifyFreezeInst(Value *Op, const SimplifyQuery &Q)
Given an operand for a Freeze, see if we can fold the result.
Definition: InstructionSimplify.cpp:6008
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:852
llvm::Optional
Definition: APInt.h:33
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::PatternMatch::m_BinOp
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:84
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::SmallPtrSet< Value *, 16 >
CBindingWrapping.h
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
llvm::PatternMatch::m_AShr
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1153
isMustTailCall
static bool isMustTailCall(Value *V)
Definition: InstructionCombining.cpp:2885
Operator.h
llvm::InstCombinerImpl::Descale
Value * Descale(Value *Val, APInt Scale, bool &NoSignedWrap)
Returns a value X such that Val = X * Scale, or null if none.
Definition: InstructionCombining.cpp:1342
llvm::BasicBlock::getSinglePredecessor
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:264
llvm::CallBase::getNumArgOperands
unsigned getNumArgOperands() const
Definition: InstrTypes.h:1336
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
LLVMInitializeInstCombine
void LLVMInitializeInstCombine(LLVMPassRegistryRef R)
Definition: InstructionCombining.cpp:4288
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:356
llvm::successors
succ_range successors(Instruction *I)
Definition: CFG.h:262
llvm::gep_type_begin
gep_type_iterator gep_type_begin(const User *GEP)
Definition: GetElementPtrTypeIterator.h:139
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2280
llvm::FastMathFlags
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:161
BasicAliasAnalysis.h
LegacyPassManager.h
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
ConstantFolding.h
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
Use.h
llvm::EHPersonality::GNU_ObjC
@ GNU_ObjC
llvm::APInt::isMinValue
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:442
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
llvm::InstCombinePass::InstCombinePass
InstCombinePass()
Definition: InstructionCombining.cpp:4182
llvm::isAllocationFn
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
Definition: MemoryBuiltins.cpp:242
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
llvm::BranchInst::swapSuccessors
void swapSuccessors()
Swap the successors of this branch instruction.
Definition: Instructions.cpp:1297
llvm::InstCombinerImpl::SimplifySelectsFeedingBinaryOp
Value * SimplifySelectsFeedingBinaryOp(BinaryOperator &I, Value *LHS, Value *RHS)
Definition: InstructionCombining.cpp:841
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::initializeInstCombine
void initializeInstCombine(PassRegistry &)
Initialize all passes linked into the InstCombine library.
Definition: InstructionCombining.cpp:4284
KnownBits.h
llvm::LazyBlockFrequencyInfoPass
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
Definition: LazyBlockFrequencyInfo.h:100
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::gep_type_end
gep_type_iterator gep_type_end(const User *GEP)
Definition: GetElementPtrTypeIterator.h:146
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1108
llvm::InstCombinerImpl::visitUnreachableInst
Instruction * visitUnreachableInst(UnreachableInst &I)
Definition: InstructionCombining.cpp:2915
llvm::UndefMaskElem
constexpr int UndefMaskElem
Definition: Instructions.h:1999
AliasAnalysis.h
llvm::PatternMatch::m_OneUse
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:67
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::ConstantExpr::getSub
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2689
llvm::classifyEHPersonality
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Definition: EHPersonalities.cpp:21
llvm::InstCombinerImpl::visitFree
Instruction * visitFree(CallInst &FI)
Definition: InstructionCombining.cpp:2850
Instruction.h
llvm::PatternMatch::m_APInt
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:270
CommandLine.h
llvm::PatternMatch::m_c_BinOp
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
Definition: PatternMatch.h:2213
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Type::isArrayTy
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:225
llvm::Intrinsic::getType
FunctionType * getType(LLVMContext &Context, ID id, ArrayRef< Type * > Tys=None)
Return the function type for an intrinsic.
Definition: Function.cpp:1292
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:160
llvm::APInt::isNonNegative
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:369
combineInstructionsOverFunction
static bool combineInstructionsOverFunction(Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, unsigned MaxIterations, LoopInfo *LI)
Definition: InstructionCombining.cpp:4121
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
AliasScopeTracker
Definition: InstructionCombining.cpp:3945
llvm::isSplatValue
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
Definition: VectorUtils.cpp:375
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1771
TryToSinkInstruction
static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock)
Try to move the specified instruction from its current block into the beginning of DestBlock,...
Definition: InstructionCombining.cpp:3671
hasNoUnsignedWrap
static bool hasNoUnsignedWrap(BinaryOperator &I)
Definition: InstructionCombining.cpp:281
llvm::AddrSpaceCastInst
This class represents a conversion between pointers from one address space to another.
Definition: Instructions.h:5234
InstCombineInternal.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::m_Select
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
Definition: PatternMatch.h:1472
llvm::ArrayType::getNumElements
uint64_t getNumElements() const
Definition: DerivedTypes.h:368
llvm::PatternMatch::m_ZExtOrSExt
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
Definition: PatternMatch.h:1658
Constants.h
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::PHINode::getIncomingValue
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Definition: Instructions.h:2723
llvm::AAResults
Definition: AliasAnalysis.h:456
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine", "Combine redundant instructions", false, false) INITIALIZE_PASS_END(InstructionCombiningPass
llvm::Constant::isNullValue
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:74
f
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:648
llvm::User
Definition: User.h:44
llvm::ConstantRange::getUnsignedMin
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
Definition: ConstantRange.cpp:376
llvm::LibFunc
LibFunc
Definition: TargetLibraryInfo.h:34
Intrinsics.h
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::InstCombinerImpl::foldOpIntoPhi
Instruction * foldOpIntoPhi(Instruction &I, PHINode *PN)
Given a binary operator, cast instruction, or select which has a PHI node as operand #0,...
Definition: InstructionCombining.cpp:1098
llvm::LandingPadInst::getNumClauses
unsigned getNumClauses() const
Get the number of clauses for this landing pad.
Definition: Instructions.h:2951
InstrTypes.h
llvm::CallBase::getCalledFunction
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation.
Definition: InstrTypes.h:1393
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::InstCombinerImpl::visitFreeze
Instruction * visitFreeze(FreezeInst &I)
Definition: InstructionCombining.cpp:3617
getOpcode
static Optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:199
llvm::EHPersonality::GNU_C
@ GNU_C
DEBUG_COUNTER
DEBUG_COUNTER(VisitCounter, "instcombine-visit", "Controls which instructions are visited")
llvm::canConstantFoldCallTo
bool canConstantFoldCallTo(const CallBase *Call, const Function *F)
canConstantFoldCallTo - Return true if its even possible to fold a call to the specified function.
Definition: ConstantFolding.cpp:1466
TargetLibraryInfo.h
llvm::Type::isVectorTy
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:237
llvm::InstCombinerImpl::visitUnconditionalBranchInst
Instruction * visitUnconditionalBranchInst(BranchInst &BI)
Definition: InstructionCombining.cpp:2942
llvm::PatternMatch::m_Instruction
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:748
l
This requires reassociating to forms of expressions that are already something that reassoc doesn t think about yet These two functions should generate the same code on big endian int * l
Definition: README.txt:100
llvm::BasicBlock::getFirstInsertionPt
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:249
false
Definition: StackSlotColoring.cpp:142
llvm::VectorType::getElementCount
ElementCount getElementCount() const
Return an ElementCount instance to represent the (possibly scalable) number of elements in the vector...
Definition: DerivedTypes.h:626
llvm::PatternMatch::m_ZExt
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:1639
llvm::isPotentiallyReachable
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
Definition: CFG.cpp:236
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::removeAllNonTerminatorAndEHPadInstructions
std::pair< unsigned, unsigned > removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than its terminator and any present EH pad instructi...
Definition: Local.cpp:2089
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:801
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:409
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:404
llvm::PatternMatch::m_SDiv
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1093
llvm::BinaryOperator::getOpcode
BinaryOps getOpcode() const
Definition: InstrTypes.h:393
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:145
llvm::Instruction
Definition: Instruction.h:45
llvm::ExtractValueInst::idx_end
idx_iterator idx_end() const
Definition: Instructions.h:2424
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::PassRegistry
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
llvm::unwrap
Attribute unwrap(LLVMAttributeRef Attr)
Definition: Attributes.h:256
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
llvm::TargetTransformInfo::simplifyDemandedVectorEltsIntrinsic
Optional< Value * > simplifyDemandedVectorEltsIntrinsic(InstCombiner &IC, IntrinsicInst &II, APInt DemandedElts, APInt &UndefElts, APInt &UndefElts2, APInt &UndefElts3, std::function< void(Instruction *, unsigned, APInt, APInt &)> SimplifyAndSetOp) const
Can be used to implement target-specific instruction combining.
Definition: TargetTransformInfo.cpp:309
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::LandingPadInst::addClause
void addClause(Constant *ClauseVal)
Add a catch or filter clause to the landing pad.
Definition: Instructions.cpp:243
llvm::UndefValue::get
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1784
llvm::InstCombinerImpl
Definition: InstCombineInternal.h:61
llvm::ConstantInt::get
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:899
InstCombineWorklist.h
llvm::getUnderlyingObject
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Definition: ValueTracking.cpp:4356
SmallPtrSet.h
llvm::InstCombinerImpl::pushFreezeToPreventPoisonFromPropagating
Value * pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI)
Definition: InstructionCombining.cpp:3551
LLVMAddInstructionCombiningPass
void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM)
See llvm::createInstructionCombiningPass function.
Definition: InstructionCombining.cpp:4300
llvm::InstCombineWorklist
InstCombineWorklist - This is the worklist management logic for InstCombine.
Definition: InstCombineWorklist.h:27
PatternMatch.h
llvm::BasicBlock::getFirstNonPHI
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:212
willNotOverflow
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
Definition: CorrelatedValuePropagation.cpp:391
llvm::SimplifyGEPInst
Value * SimplifyGEPInst(Type *SrcTy, ArrayRef< Value * > Ops, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
Definition: InstructionSimplify.cpp:4422
llvm::MCID::Call
@ Call
Definition: MCInstrDesc.h:153
llvm::Metadata
Root of the metadata hierarchy.
Definition: Metadata.h:62
rightDistributesOverLeft
static bool rightDistributesOverLeft(Instruction::BinaryOps LOp, Instruction::BinaryOps ROp)
Return whether "(X LOp Y) ROp Z" is always equal to "(X ROp Z) LOp (Y ROp Z)".
Definition: InstructionCombining.cpp:570
llvm::PatternMatch::m_APIntAllowUndef
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
Definition: PatternMatch.h:276
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
llvm::Instruction::isIntDivRem
bool isIntDivRem() const
Definition: Instruction.h:166
llvm::PHINode::getNumIncomingValues
unsigned getNumIncomingValues() const
Return the number of incoming edges.
Definition: Instructions.h:2719
llvm::None
const NoneType None
Definition: None.h:23
llvm::EHPersonality::Wasm_CXX
@ Wasm_CXX
ClearSubclassDataAfterReassociation
static void ClearSubclassDataAfterReassociation(BinaryOperator &I)
Conservatively clears subclassOptionalData after a reassociation or commutation.
Definition: InstructionCombining.cpp:294
llvm::Value::use_empty
bool use_empty() const
Definition: Value.h:345
Type.h
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
llvm::InstCombinerImpl::SimplifyAssociativeOrCommutative
bool SimplifyAssociativeOrCommutative(BinaryOperator &I)
Performs a few simplifications for operators which are associative or commutative.
Definition: InstructionCombining.cpp:389
simplifyAssocCastAssoc
static bool simplifyAssocCastAssoc(BinaryOperator *BinOp1, InstCombinerImpl &IC)
Combine constant operands of associative operations either before or after a cast to eliminate one of...
Definition: InstructionCombining.cpp:310
llvm::Instruction::isCommutative
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
Definition: Instruction.cpp:758
CFG.h
LoopInfo.h
llvm::canCreateUndefOrPoison
bool canCreateUndefOrPoison(const Operator *Op)
canCreateUndefOrPoison returns true if Op can create undef or poison from non-undef & non-poison oper...
Definition: ValueTracking.cpp:5038
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3143
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3743
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:710
llvm::Type::isIntegerTy
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:201
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1102
llvm::InstCombineWorklist::push
void push(Instruction *I)
Push the instruction onto the worklist stack.
Definition: InstCombineWorklist.h:60
foldOperationIntoPhiValue
static Value * foldOperationIntoPhiValue(BinaryOperator *I, Value *InV, InstCombiner::BuilderTy &Builder)
Definition: InstructionCombining.cpp:1076
llvm::VectorType
Base class of all SIMD vector types.
Definition: DerivedTypes.h:388
llvm::IRBuilderBase::FastMathFlagGuard
Definition: IRBuilder.h:389
llvm::Type::getArrayElementType
Type * getArrayElementType() const
Definition: Type.h:375
Combine
Hexagon Vector Combine
Definition: HexagonVectorCombine.cpp:1520
VectorUtils.h
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2083
llvm::GEPOperator::hasAllZeroIndices
bool hasAllZeroIndices() const
Return true if all of the indices of this GEP are zeros.
Definition: Operator.h:533
InstCombineDefaultInfiniteLoopThreshold
static constexpr unsigned InstCombineDefaultInfiniteLoopThreshold
Definition: InstructionCombining.cpp:133
BasicBlock.h
llvm::cl::opt< bool >
llvm::ClrHandlerType::Filter
@ Filter
llvm::DbgVariableIntrinsic
This is the common base class for debug info intrinsics for variables.
Definition: IntrinsicInst.h:148
llvm::ConstantExpr::getCompare
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
Definition: Constants.cpp:2386
llvm::EHPersonality::GNU_CXX_SjLj
@ GNU_CXX_SjLj
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::PatternMatch::m_Zero
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:535
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
isNeverEqualToUnescapedAlloc
static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo *TLI, Instruction *AI)
Definition: InstructionCombining.cpp:2566
llvm::Instruction::eraseFromParent
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:78
llvm::PatternMatch::m_UnconditionalBr
br_match m_UnconditionalBr(BasicBlock *&Succ)
Definition: PatternMatch.h:1720
llvm::PatternMatch::m_ImmConstant
match_combine_and< class_match< Constant >, match_unless< class_match< ConstantExpr > > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
Definition: PatternMatch.h:781
llvm::ICmpInst
This instruction compares its operands according to the predicate given to the constructor.
Definition: Instructions.h:1203
llvm::ConstantExpr::getBinOpIdentity
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2800
EnableCodeSinking
static cl::opt< bool > EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"), cl::init(true))
llvm::KnownBits::countMinLeadingOnes
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
Definition: KnownBits.h:239
llvm::TargetLibraryInfoWrapperPass
Definition: TargetLibraryInfo.h:463
llvm::ExtractValueInst::Create
static ExtractValueInst * Create(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:2400
llvm::StructLayout
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:604
ProfileSummaryInfo.h
llvm::ConstantRange::getSignedMin
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:388
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2369
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
MaxArraySize
static cl::opt< unsigned > MaxArraySize("instcombine-maxarray-size", cl::init(1024), cl::desc("Maximum array size considered when doing a combine"))
llvm::Instruction::user_back
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:91
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
llvm::APInt::sdivrem
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1921
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::BasicAAWrapperPass
Legacy wrapper pass to provide the BasicAAResult object.
Definition: BasicAliasAnalysis.h:244
llvm::SimplifyBinOp
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
Definition: InstructionSimplify.cpp:5282
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2777
llvm::PatternMatch::m_Or
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1129
AliasScopeTracker::analyse
void analyse(Instruction *I)
Definition: InstructionCombining.cpp:3950
isAllocSiteRemovable
static bool isAllocSiteRemovable(Instruction *AI, SmallVectorImpl< WeakTrackingVH > &Users, const TargetLibraryInfo *TLI)
Definition: InstructionCombining.cpp:2580
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::DenseMap
Definition: DenseMap.h:714
llvm::ConstantExpr::get
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
Definition: Constants.cpp:2255
llvm::ExtractValueInst::idx_begin
idx_iterator idx_begin() const
Definition: Instructions.h:2423
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::ConstantDataVector
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double,...
Definition: Constants.h:752
llvm::UndefValue
'undef' values are things that do not have specified contents.
Definition: Constants.h:1352
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::ConstantExpr::getShl
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2754
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:572
llvm::lowerObjectSizeCall
Value * lowerObjectSizeCall(IntrinsicInst *ObjectSize, const DataLayout &DL, const TargetLibraryInfo *TLI, bool MustSucceed)
Try to turn a call to @llvm.objectsize into an integer value of the given Type.
Definition: MemoryBuiltins.cpp:526
llvm::DebugVariable
Identifies a unique instance of a variable.
Definition: DebugInfoMetadata.h:3601
DIBuilder.h
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:185
llvm::StructLayout::getElementContainingOffset
unsigned getElementContainingOffset(uint64_t Offset) const
Given a valid byte offset into the structure, returns the structure index that contains it.
Definition: DataLayout.cpp:82
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:631
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1612
ArrayRef.h
llvm::ICmpInst::isEquality
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Definition: Instructions.h:1292
llvm::LandingPadInst::getClause
Constant * getClause(unsigned Idx) const
Get the value of the clause at index Idx.
Definition: Instructions.h:2936
ShouldLowerDbgDeclare
static cl::opt< unsigned > ShouldLowerDbgDeclare("instcombine-lower-dbg-declare", cl::Hidden, cl::init(true))
llvm::GetElementPtrInst::CreateInBounds
static GetElementPtrInst * CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Definition: Instructions.h:990
llvm::ConstantVector
Constant Vector Declarations.
Definition: Constants.h:493
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())
llvm::FPMathOperator
Utility class for floating point operations which can have information about relaxed accuracy require...
Definition: Operator.h:250
llvm::PatternMatch::m_Sub
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1020
llvm::Type::getArrayNumElements
uint64_t getArrayNumElements() const
Definition: DerivedTypes.h:383
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::salvageDebugInfoForDbgValues
void salvageDebugInfoForDbgValues(Instruction &I, ArrayRef< DbgVariableIntrinsic * > Insns)
Implementation of salvageDebugInfo, applying only to instructions in Insns, rather than all debug use...
Definition: Local.cpp:1734
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::ConstantExpr::getCast
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1976
llvm::generic_gep_type_iterator::getIndexedType
Type * getIndexedType() const
Definition: GetElementPtrTypeIterator.h:72
llvm::KnownBits::countMinLeadingZeros
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:234
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1740
function
print Print MemDeps of function
Definition: MemDepPrinter.cpp:83
llvm::SimplifyQuery::getWithInstruction
SimplifyQuery getWithInstruction(Instruction *I) const
Definition: InstructionSimplify.h:121
llvm::ArrayType::get
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:604
llvm::InstructionCombiningPass::ID
static char ID
Definition: InstCombine.h:45
isCatchAll
static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo)
Return 'true' if the given typeinfo will match anything.
Definition: InstructionCombining.cpp:3206
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::MDNode
Metadata node.
Definition: Metadata.h:897
InstCombineDefaultMaxIterations
static constexpr unsigned InstCombineDefaultMaxIterations
Definition: InstructionCombining.cpp:131
llvm::PatternMatch::m_Constant
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:142
llvm::IRBuilderCallbackInserter
Provides an 'InsertHelper' that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:77
TinyPtrVector.h
llvm::InstCombinerImpl::SimplifyUsingDistributiveLaws
Value * SimplifyUsingDistributiveLaws(BinaryOperator &I)
Tries to simplify binary operations which some other binary operation distributes over.
Definition: InstructionCombining.cpp:723
llvm::EHPersonality::CoreCLR
@ CoreCLR
llvm::GEPOperator
Definition: Operator.h:458
llvm::InstCombinerImpl::visitSwitchInst
Instruction * visitSwitchInst(SwitchInst &SI)
Definition: InstructionCombining.cpp:3007
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3140
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
LLVMPassManagerRef
struct LLVMOpaquePassManager * LLVMPassManagerRef
Definition: Types.h:127
llvm::InstCombinerImpl::foldVectorBinop
Instruction * foldVectorBinop(BinaryOperator &Inst)
Canonicalize the position of binops relative to shufflevector.
Definition: InstructionCombining.cpp:1582
CFG.h
llvm::GetElementPtrInst::Create
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:954
llvm::ProfileSummaryAnalysis
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:203
llvm::PatternMatch::m_SExt
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:1633
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
llvm::ArrayRef< int >
llvm::isInstructionTriviallyDead
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:398
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::BasicBlock::instructionsWithoutDebug
iterator_range< filter_iterator< BasicBlock::const_iterator, std::function< bool(const Instruction &)> > > instructionsWithoutDebug(bool SkipPseudoOp=false) const
Return a const iterator range over the instructions in the block, skipping any debug instructions.
Definition: BasicBlock.cpp:100
llvm::Instruction::getFastMathFlags
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Definition: Instruction.cpp:280
llvm::BinaryOperator
Definition: InstrTypes.h:189
None.h
llvm::APInt::ssub_ov
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1972
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::APInt::getAllOnesValue
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:567
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:212
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::AnalysisUsage::setPreservesCFG
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:253
llvm::StructLayout::getSizeInBytes
uint64_t getSizeInBytes() const
Definition: DataLayout.h:611
llvm::PatternMatch::m_Undef
auto m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:136
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::EHPersonality::MSVC_TableSEH
@ MSVC_TableSEH
llvm::EHPersonality::GNU_CXX
@ GNU_CXX
tryToMoveFreeBeforeNullTest
static Instruction * tryToMoveFreeBeforeNullTest(CallInst &FI, const DataLayout &DL)
Move the call to free before a NULL test.
Definition: InstructionCombining.cpp:2784
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::Constant::getAggregateElement
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:420
llvm::SimplifyExtractValueInst
Value * SimplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
Definition: InstructionSimplify.cpp:4522
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::CFGAnalyses
Represents analyses that only rely on functions' control flow.
Definition: PassManager.h:116
llvm::EHPersonality::XL_CXX
@ XL_CXX
llvm::BasicBlock::getUniquePredecessor
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
Definition: BasicBlock.cpp:272
llvm::PatternMatch::m_Shuffle
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
Definition: PatternMatch.h:1561
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
llvm::Value::replaceAllUsesWith
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:520
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
Compiler.h
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1744
llvm::IRBuilderBase::InsertPointGuard
Definition: