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::getAllOnes(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  Value *NewSrc =
2122  Builder.CreateGEP(GEPEltType, SO0, GO1, Src->getName());
2123  // Propagate 'inbounds' if the new source was not constant-folded.
2124  if (auto *NewSrcGEPI = dyn_cast<GetElementPtrInst>(NewSrc))
2125  NewSrcGEPI->setIsInBounds(Src->isInBounds());
2126  GetElementPtrInst *NewGEP =
2127  GetElementPtrInst::Create(GEPEltType, NewSrc, {SO1});
2128  NewGEP->setIsInBounds(GEP.isInBounds());
2129  return NewGEP;
2130  }
2131  }
2132  }
2133  }
2134  }
2135 
2136  // Note that if our source is a gep chain itself then we wait for that
2137  // chain to be resolved before we perform this transformation. This
2138  // avoids us creating a TON of code in some cases.
2139  if (auto *SrcGEP = dyn_cast<GEPOperator>(Src->getOperand(0)))
2140  if (SrcGEP->getNumOperands() == 2 && shouldMergeGEPs(*Src, *SrcGEP))
2141  return nullptr; // Wait until our source is folded to completion.
2142 
2143  SmallVector<Value*, 8> Indices;
2144 
2145  // Find out whether the last index in the source GEP is a sequential idx.
2146  bool EndsWithSequential = false;
2147  for (gep_type_iterator I = gep_type_begin(*Src), E = gep_type_end(*Src);
2148  I != E; ++I)
2149  EndsWithSequential = I.isSequential();
2150 
2151  // Can we combine the two pointer arithmetics offsets?
2152  if (EndsWithSequential) {
2153  // Replace: gep (gep %P, long B), long A, ...
2154  // With: T = long A+B; gep %P, T, ...
2155  Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
2156  Value *GO1 = GEP.getOperand(1);
2157 
2158  // If they aren't the same type, then the input hasn't been processed
2159  // by the loop above yet (which canonicalizes sequential index types to
2160  // intptr_t). Just avoid transforming this until the input has been
2161  // normalized.
2162  if (SO1->getType() != GO1->getType())
2163  return nullptr;
2164 
2165  Value *Sum =
2166  SimplifyAddInst(GO1, SO1, false, false, SQ.getWithInstruction(&GEP));
2167  // Only do the combine when we are sure the cost after the
2168  // merge is never more than that before the merge.
2169  if (Sum == nullptr)
2170  return nullptr;
2171 
2172  // Update the GEP in place if possible.
2173  if (Src->getNumOperands() == 2) {
2174  GEP.setIsInBounds(isMergedGEPInBounds(*Src, *cast<GEPOperator>(&GEP)));
2175  replaceOperand(GEP, 0, Src->getOperand(0));
2176  replaceOperand(GEP, 1, Sum);
2177  return &GEP;
2178  }
2179  Indices.append(Src->op_begin()+1, Src->op_end()-1);
2180  Indices.push_back(Sum);
2181  Indices.append(GEP.op_begin()+2, GEP.op_end());
2182  } else if (isa<Constant>(*GEP.idx_begin()) &&
2183  cast<Constant>(*GEP.idx_begin())->isNullValue() &&
2184  Src->getNumOperands() != 1) {
2185  // Otherwise we can do the fold if the first index of the GEP is a zero
2186  Indices.append(Src->op_begin()+1, Src->op_end());
2187  Indices.append(GEP.idx_begin()+1, GEP.idx_end());
2188  }
2189 
2190  if (!Indices.empty())
2191  return isMergedGEPInBounds(*Src, *cast<GEPOperator>(&GEP))
2193  Src->getSourceElementType(), Src->getOperand(0), Indices,
2194  GEP.getName())
2195  : GetElementPtrInst::Create(Src->getSourceElementType(),
2196  Src->getOperand(0), Indices,
2197  GEP.getName());
2198  }
2199 
2200  // Skip if GEP source element type is scalable. The type alloc size is unknown
2201  // at compile-time.
2202  if (GEP.getNumIndices() == 1 && !IsGEPSrcEleScalable) {
2203  unsigned AS = GEP.getPointerAddressSpace();
2204  if (GEP.getOperand(1)->getType()->getScalarSizeInBits() ==
2205  DL.getIndexSizeInBits(AS)) {
2206  uint64_t TyAllocSize = DL.getTypeAllocSize(GEPEltType).getFixedSize();
2207 
2208  bool Matched = false;
2209  uint64_t C;
2210  Value *V = nullptr;
2211  if (TyAllocSize == 1) {
2212  V = GEP.getOperand(1);
2213  Matched = true;
2214  } else if (match(GEP.getOperand(1),
2215  m_AShr(m_Value(V), m_ConstantInt(C)))) {
2216  if (TyAllocSize == 1ULL << C)
2217  Matched = true;
2218  } else if (match(GEP.getOperand(1),
2219  m_SDiv(m_Value(V), m_ConstantInt(C)))) {
2220  if (TyAllocSize == C)
2221  Matched = true;
2222  }
2223 
2224  // Canonicalize (gep i8* X, (ptrtoint Y)-(ptrtoint X)) to (bitcast Y), but
2225  // only if both point to the same underlying object (otherwise provenance
2226  // is not necessarily retained).
2227  Value *Y;
2228  Value *X = GEP.getOperand(0);
2229  if (Matched &&
2233  }
2234  }
2235 
2236  // We do not handle pointer-vector geps here.
2237  if (GEPType->isVectorTy())
2238  return nullptr;
2239 
2240  // Handle gep(bitcast x) and gep(gep x, 0, 0, 0).
2241  Value *StrippedPtr = PtrOp->stripPointerCasts();
2242  PointerType *StrippedPtrTy = cast<PointerType>(StrippedPtr->getType());
2243 
2244  if (StrippedPtr != PtrOp) {
2245  bool HasZeroPointerIndex = false;
2246  Type *StrippedPtrEltTy = StrippedPtrTy->getElementType();
2247 
2248  if (auto *C = dyn_cast<ConstantInt>(GEP.getOperand(1)))
2249  HasZeroPointerIndex = C->isZero();
2250 
2251  // Transform: GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ...
2252  // into : GEP [10 x i8]* X, i32 0, ...
2253  //
2254  // Likewise, transform: GEP (bitcast i8* X to [0 x i8]*), i32 0, ...
2255  // into : GEP i8* X, ...
2256  //
2257  // This occurs when the program declares an array extern like "int X[];"
2258  if (HasZeroPointerIndex) {
2259  if (auto *CATy = dyn_cast<ArrayType>(GEPEltType)) {
2260  // GEP (bitcast i8* X to [0 x i8]*), i32 0, ... ?
2261  if (CATy->getElementType() == StrippedPtrEltTy) {
2262  // -> GEP i8* X, ...
2263  SmallVector<Value *, 8> Idx(drop_begin(GEP.indices()));
2265  StrippedPtrEltTy, StrippedPtr, Idx, GEP.getName());
2266  Res->setIsInBounds(GEP.isInBounds());
2267  if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace())
2268  return Res;
2269  // Insert Res, and create an addrspacecast.
2270  // e.g.,
2271  // GEP (addrspacecast i8 addrspace(1)* X to [0 x i8]*), i32 0, ...
2272  // ->
2273  // %0 = GEP i8 addrspace(1)* X, ...
2274  // addrspacecast i8 addrspace(1)* %0 to i8*
2275  return new AddrSpaceCastInst(Builder.Insert(Res), GEPType);
2276  }
2277 
2278  if (auto *XATy = dyn_cast<ArrayType>(StrippedPtrEltTy)) {
2279  // GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ... ?
2280  if (CATy->getElementType() == XATy->getElementType()) {
2281  // -> GEP [10 x i8]* X, i32 0, ...
2282  // At this point, we know that the cast source type is a pointer
2283  // to an array of the same type as the destination pointer
2284  // array. Because the array type is never stepped over (there
2285  // is a leading zero) we can fold the cast into this GEP.
2286  if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace()) {
2287  GEP.setSourceElementType(XATy);
2288  return replaceOperand(GEP, 0, StrippedPtr);
2289  }
2290  // Cannot replace the base pointer directly because StrippedPtr's
2291  // address space is different. Instead, create a new GEP followed by
2292  // an addrspacecast.
2293  // e.g.,
2294  // GEP (addrspacecast [10 x i8] addrspace(1)* X to [0 x i8]*),
2295  // i32 0, ...
2296  // ->
2297  // %0 = GEP [10 x i8] addrspace(1)* X, ...
2298  // addrspacecast i8 addrspace(1)* %0 to i8*
2299  SmallVector<Value *, 8> Idx(GEP.indices());
2300  Value *NewGEP =
2301  GEP.isInBounds()
2302  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2303  Idx, GEP.getName())
2304  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2305  GEP.getName());
2306  return new AddrSpaceCastInst(NewGEP, GEPType);
2307  }
2308  }
2309  }
2310  } else if (GEP.getNumOperands() == 2 && !IsGEPSrcEleScalable) {
2311  // Skip if GEP source element type is scalable. The type alloc size is
2312  // unknown at compile-time.
2313  // Transform things like: %t = getelementptr i32*
2314  // bitcast ([2 x i32]* %str to i32*), i32 %V into: %t1 = getelementptr [2
2315  // x i32]* %str, i32 0, i32 %V; bitcast
2316  if (StrippedPtrEltTy->isArrayTy() &&
2317  DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType()) ==
2318  DL.getTypeAllocSize(GEPEltType)) {
2319  Type *IdxType = DL.getIndexType(GEPType);
2320  Value *Idx[2] = { Constant::getNullValue(IdxType), GEP.getOperand(1) };
2321  Value *NewGEP =
2322  GEP.isInBounds()
2323  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2324  GEP.getName())
2325  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2326  GEP.getName());
2327 
2328  // V and GEP are both pointer types --> BitCast
2329  return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, GEPType);
2330  }
2331 
2332  // Transform things like:
2333  // %V = mul i64 %N, 4
2334  // %t = getelementptr i8* bitcast (i32* %arr to i8*), i32 %V
2335  // into: %t1 = getelementptr i32* %arr, i32 %N; bitcast
2336  if (GEPEltType->isSized() && StrippedPtrEltTy->isSized()) {
2337  // Check that changing the type amounts to dividing the index by a scale
2338  // factor.
2339  uint64_t ResSize = DL.getTypeAllocSize(GEPEltType).getFixedSize();
2340  uint64_t SrcSize = DL.getTypeAllocSize(StrippedPtrEltTy).getFixedSize();
2341  if (ResSize && SrcSize % ResSize == 0) {
2342  Value *Idx = GEP.getOperand(1);
2343  unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
2344  uint64_t Scale = SrcSize / ResSize;
2345 
2346  // Earlier transforms ensure that the index has the right type
2347  // according to Data Layout, which considerably simplifies the
2348  // logic by eliminating implicit casts.
2349  assert(Idx->getType() == DL.getIndexType(GEPType) &&
2350  "Index type does not match the Data Layout preferences");
2351 
2352  bool NSW;
2353  if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
2354  // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
2355  // If the multiplication NewIdx * Scale may overflow then the new
2356  // GEP may not be "inbounds".
2357  Value *NewGEP =
2358  GEP.isInBounds() && NSW
2359  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2360  NewIdx, GEP.getName())
2361  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, NewIdx,
2362  GEP.getName());
2363 
2364  // The NewGEP must be pointer typed, so must the old one -> BitCast
2366  GEPType);
2367  }
2368  }
2369  }
2370 
2371  // Similarly, transform things like:
2372  // getelementptr i8* bitcast ([100 x double]* X to i8*), i32 %tmp
2373  // (where tmp = 8*tmp2) into:
2374  // getelementptr [100 x double]* %arr, i32 0, i32 %tmp2; bitcast
2375  if (GEPEltType->isSized() && StrippedPtrEltTy->isSized() &&
2376  StrippedPtrEltTy->isArrayTy()) {
2377  // Check that changing to the array element type amounts to dividing the
2378  // index by a scale factor.
2379  uint64_t ResSize = DL.getTypeAllocSize(GEPEltType).getFixedSize();
2380  uint64_t ArrayEltSize =
2381  DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType())
2382  .getFixedSize();
2383  if (ResSize && ArrayEltSize % ResSize == 0) {
2384  Value *Idx = GEP.getOperand(1);
2385  unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
2386  uint64_t Scale = ArrayEltSize / ResSize;
2387 
2388  // Earlier transforms ensure that the index has the right type
2389  // according to the Data Layout, which considerably simplifies
2390  // the logic by eliminating implicit casts.
2391  assert(Idx->getType() == DL.getIndexType(GEPType) &&
2392  "Index type does not match the Data Layout preferences");
2393 
2394  bool NSW;
2395  if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
2396  // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
2397  // If the multiplication NewIdx * Scale may overflow then the new
2398  // GEP may not be "inbounds".
2399  Type *IndTy = DL.getIndexType(GEPType);
2400  Value *Off[2] = {Constant::getNullValue(IndTy), NewIdx};
2401 
2402  Value *NewGEP =
2403  GEP.isInBounds() && NSW
2404  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2405  Off, GEP.getName())
2406  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Off,
2407  GEP.getName());
2408  // The NewGEP must be pointer typed, so must the old one -> BitCast
2410  GEPType);
2411  }
2412  }
2413  }
2414  }
2415  }
2416 
2417  // addrspacecast between types is canonicalized as a bitcast, then an
2418  // addrspacecast. To take advantage of the below bitcast + struct GEP, look
2419  // through the addrspacecast.
2420  Value *ASCStrippedPtrOp = PtrOp;
2421  if (auto *ASC = dyn_cast<AddrSpaceCastInst>(PtrOp)) {
2422  // X = bitcast A addrspace(1)* to B addrspace(1)*
2423  // Y = addrspacecast A addrspace(1)* to B addrspace(2)*
2424  // Z = gep Y, <...constant indices...>
2425  // Into an addrspacecasted GEP of the struct.
2426  if (auto *BC = dyn_cast<BitCastInst>(ASC->getOperand(0)))
2427  ASCStrippedPtrOp = BC;
2428  }
2429 
2430  if (auto *BCI = dyn_cast<BitCastInst>(ASCStrippedPtrOp)) {
2431  Value *SrcOp = BCI->getOperand(0);
2432  PointerType *SrcType = cast<PointerType>(BCI->getSrcTy());
2433  Type *SrcEltType = SrcType->getElementType();
2434 
2435  // GEP directly using the source operand if this GEP is accessing an element
2436  // of a bitcasted pointer to vector or array of the same dimensions:
2437  // gep (bitcast <c x ty>* X to [c x ty]*), Y, Z --> gep X, Y, Z
2438  // gep (bitcast [c x ty]* X to <c x ty>*), Y, Z --> gep X, Y, Z
2439  auto areMatchingArrayAndVecTypes = [](Type *ArrTy, Type *VecTy,
2440  const DataLayout &DL) {
2441  auto *VecVTy = cast<FixedVectorType>(VecTy);
2442  return ArrTy->getArrayElementType() == VecVTy->getElementType() &&
2443  ArrTy->getArrayNumElements() == VecVTy->getNumElements() &&
2444  DL.getTypeAllocSize(ArrTy) == DL.getTypeAllocSize(VecTy);
2445  };
2446  if (GEP.getNumOperands() == 3 &&
2447  ((GEPEltType->isArrayTy() && isa<FixedVectorType>(SrcEltType) &&
2448  areMatchingArrayAndVecTypes(GEPEltType, SrcEltType, DL)) ||
2449  (isa<FixedVectorType>(GEPEltType) && SrcEltType->isArrayTy() &&
2450  areMatchingArrayAndVecTypes(SrcEltType, GEPEltType, DL)))) {
2451 
2452  // Create a new GEP here, as using `setOperand()` followed by
2453  // `setSourceElementType()` won't actually update the type of the
2454  // existing GEP Value. Causing issues if this Value is accessed when
2455  // constructing an AddrSpaceCastInst
2456  Value *NGEP =
2457  GEP.isInBounds()
2458  ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]})
2459  : Builder.CreateGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]});
2460  NGEP->takeName(&GEP);
2461 
2462  // Preserve GEP address space to satisfy users
2463  if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace())
2464  return new AddrSpaceCastInst(NGEP, GEPType);
2465 
2466  return replaceInstUsesWith(GEP, NGEP);
2467  }
2468 
2469  // See if we can simplify:
2470  // X = bitcast A* to B*
2471  // Y = gep X, <...constant indices...>
2472  // into a gep of the original struct. This is important for SROA and alias
2473  // analysis of unions. If "A" is also a bitcast, wait for A/X to be merged.
2474  unsigned OffsetBits = DL.getIndexTypeSizeInBits(GEPType);
2475  APInt Offset(OffsetBits, 0);
2476 
2477  // If the bitcast argument is an allocation, The bitcast is for convertion
2478  // to actual type of allocation. Removing such bitcasts, results in having
2479  // GEPs with i8* base and pure byte offsets. That means GEP is not aware of
2480  // struct or array hierarchy.
2481  // By avoiding such GEPs, phi translation and MemoryDependencyAnalysis have
2482  // a better chance to succeed.
2483  if (!isa<BitCastInst>(SrcOp) && GEP.accumulateConstantOffset(DL, Offset) &&
2484  !isAllocationFn(SrcOp, &TLI)) {
2485  // If this GEP instruction doesn't move the pointer, just replace the GEP
2486  // with a bitcast of the real input to the dest type.
2487  if (!Offset) {
2488  // If the bitcast is of an allocation, and the allocation will be
2489  // converted to match the type of the cast, don't touch this.
2490  if (isa<AllocaInst>(SrcOp)) {
2491  // See if the bitcast simplifies, if so, don't nuke this GEP yet.
2492  if (Instruction *I = visitBitCast(*BCI)) {
2493  if (I != BCI) {
2494  I->takeName(BCI);
2495  BCI->getParent()->getInstList().insert(BCI->getIterator(), I);
2496  replaceInstUsesWith(*BCI, I);
2497  }
2498  return &GEP;
2499  }
2500  }
2501 
2502  if (SrcType->getPointerAddressSpace() != GEP.getAddressSpace())
2503  return new AddrSpaceCastInst(SrcOp, GEPType);
2504  return new BitCastInst(SrcOp, GEPType);
2505  }
2506 
2507  // Otherwise, if the offset is non-zero, we need to find out if there is a
2508  // field at Offset in 'A's type. If so, we can pull the cast through the
2509  // GEP.
2510  SmallVector<Value*, 8> NewIndices;
2511  if (FindElementAtOffset(SrcType, Offset.getSExtValue(), NewIndices)) {
2512  Value *NGEP =
2513  GEP.isInBounds()
2514  ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, NewIndices)
2515  : Builder.CreateGEP(SrcEltType, SrcOp, NewIndices);
2516 
2517  if (NGEP->getType() == GEPType)
2518  return replaceInstUsesWith(GEP, NGEP);
2519  NGEP->takeName(&GEP);
2520 
2521  if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace())
2522  return new AddrSpaceCastInst(NGEP, GEPType);
2523  return new BitCastInst(NGEP, GEPType);
2524  }
2525  }
2526  }
2527 
2528  if (!GEP.isInBounds()) {
2529  unsigned IdxWidth =
2530  DL.getIndexSizeInBits(PtrOp->getType()->getPointerAddressSpace());
2531  APInt BasePtrOffset(IdxWidth, 0);
2532  Value *UnderlyingPtrOp =
2534  BasePtrOffset);
2535  if (auto *AI = dyn_cast<AllocaInst>(UnderlyingPtrOp)) {
2536  if (GEP.accumulateConstantOffset(DL, BasePtrOffset) &&
2537  BasePtrOffset.isNonNegative()) {
2538  APInt AllocSize(
2539  IdxWidth,
2540  DL.getTypeAllocSize(AI->getAllocatedType()).getKnownMinSize());
2541  if (BasePtrOffset.ule(AllocSize)) {
2543  GEP.getSourceElementType(), PtrOp, makeArrayRef(Ops).slice(1),
2544  GEP.getName());
2545  }
2546  }
2547  }
2548  }
2549 
2550  if (Instruction *R = foldSelectGEP(GEP, Builder))
2551  return R;
2552 
2553  return nullptr;
2554 }
2555 
2557  Instruction *AI) {
2558  if (isa<ConstantPointerNull>(V))
2559  return true;
2560  if (auto *LI = dyn_cast<LoadInst>(V))
2561  return isa<GlobalVariable>(LI->getPointerOperand());
2562  // Two distinct allocations will never be equal.
2563  // We rely on LookThroughBitCast in isAllocLikeFn being false, since looking
2564  // through bitcasts of V can cause
2565  // the result statement below to be true, even when AI and V (ex:
2566  // i8* ->i32* ->i8* of AI) are the same allocations.
2567  return isAllocLikeFn(V, TLI) && V != AI;
2568 }
2569 
2572  const TargetLibraryInfo *TLI) {
2574  Worklist.push_back(AI);
2575 
2576  do {
2577  Instruction *PI = Worklist.pop_back_val();
2578  for (User *U : PI->users()) {
2579  Instruction *I = cast<Instruction>(U);
2580  switch (I->getOpcode()) {
2581  default:
2582  // Give up the moment we see something we can't handle.
2583  return false;
2584 
2585  case Instruction::AddrSpaceCast:
2586  case Instruction::BitCast:
2587  case Instruction::GetElementPtr:
2588  Users.emplace_back(I);
2589  Worklist.push_back(I);
2590  continue;
2591 
2592  case Instruction::ICmp: {
2593  ICmpInst *ICI = cast<ICmpInst>(I);
2594  // We can fold eq/ne comparisons with null to false/true, respectively.
2595  // We also fold comparisons in some conditions provided the alloc has
2596  // not escaped (see isNeverEqualToUnescapedAlloc).
2597  if (!ICI->isEquality())
2598  return false;
2599  unsigned OtherIndex = (ICI->getOperand(0) == PI) ? 1 : 0;
2600  if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex), TLI, AI))
2601  return false;
2602  Users.emplace_back(I);
2603  continue;
2604  }
2605 
2606  case Instruction::Call:
2607  // Ignore no-op and store intrinsics.
2608  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
2609  switch (II->getIntrinsicID()) {
2610  default:
2611  return false;
2612 
2613  case Intrinsic::memmove:
2614  case Intrinsic::memcpy:
2615  case Intrinsic::memset: {
2616  MemIntrinsic *MI = cast<MemIntrinsic>(II);
2617  if (MI->isVolatile() || MI->getRawDest() != PI)
2618  return false;
2620  }
2621  case Intrinsic::assume:
2622  case Intrinsic::invariant_start:
2623  case Intrinsic::invariant_end:
2624  case Intrinsic::lifetime_start:
2625  case Intrinsic::lifetime_end:
2626  case Intrinsic::objectsize:
2627  Users.emplace_back(I);
2628  continue;
2629  case Intrinsic::launder_invariant_group:
2630  case Intrinsic::strip_invariant_group:
2631  Users.emplace_back(I);
2632  Worklist.push_back(I);
2633  continue;
2634  }
2635  }
2636 
2637  if (isFreeCall(I, TLI)) {
2638  Users.emplace_back(I);
2639  continue;
2640  }
2641  return false;
2642 
2643  case Instruction::Store: {
2644  StoreInst *SI = cast<StoreInst>(I);
2645  if (SI->isVolatile() || SI->getPointerOperand() != PI)
2646  return false;
2647  Users.emplace_back(I);
2648  continue;
2649  }
2650  }
2651  llvm_unreachable("missing a return?");
2652  }
2653  } while (!Worklist.empty());
2654  return true;
2655 }
2656 
2658  // If we have a malloc call which is only used in any amount of comparisons to
2659  // null and free calls, delete the calls and replace the comparisons with true
2660  // or false as appropriate.
2661 
2662  // This is based on the principle that we can substitute our own allocation
2663  // function (which will never return null) rather than knowledge of the
2664  // specific function being called. In some sense this can change the permitted
2665  // outputs of a program (when we convert a malloc to an alloca, the fact that
2666  // the allocation is now on the stack is potentially visible, for example),
2667  // but we believe in a permissible manner.
2669 
2670  // If we are removing an alloca with a dbg.declare, insert dbg.value calls
2671  // before each store.
2673  std::unique_ptr<DIBuilder> DIB;
2674  if (isa<AllocaInst>(MI)) {
2675  findDbgUsers(DVIs, &MI);
2676  DIB.reset(new DIBuilder(*MI.getModule(), /*AllowUnresolved=*/false));
2677  }
2678 
2679  if (isAllocSiteRemovable(&MI, Users, &TLI)) {
2680  for (unsigned i = 0, e = Users.size(); i != e; ++i) {
2681  // Lowering all @llvm.objectsize calls first because they may
2682  // use a bitcast/GEP of the alloca we are removing.
2683  if (!Users[i])
2684  continue;
2685 
2686  Instruction *I = cast<Instruction>(&*Users[i]);
2687 
2688  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
2689  if (II->getIntrinsicID() == Intrinsic::objectsize) {
2690  Value *Result =
2691  lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true);
2692  replaceInstUsesWith(*I, Result);
2693  eraseInstFromFunction(*I);
2694  Users[i] = nullptr; // Skip examining in the next loop.
2695  }
2696  }
2697  }
2698  for (unsigned i = 0, e = Users.size(); i != e; ++i) {
2699  if (!Users[i])
2700  continue;
2701 
2702  Instruction *I = cast<Instruction>(&*Users[i]);
2703 
2704  if (ICmpInst *C = dyn_cast<ICmpInst>(I)) {
2705  replaceInstUsesWith(*C,
2706  ConstantInt::get(Type::getInt1Ty(C->getContext()),
2707  C->isFalseWhenEqual()));
2708  } else if (auto *SI = dyn_cast<StoreInst>(I)) {
2709  for (auto *DVI : DVIs)
2710  if (DVI->isAddressOfVariable())
2711  ConvertDebugDeclareToDebugValue(DVI, SI, *DIB);
2712  } else {
2713  // Casts, GEP, or anything else: we're about to delete this instruction,
2714  // so it can not have any valid uses.
2715  replaceInstUsesWith(*I, PoisonValue::get(I->getType()));
2716  }
2717  eraseInstFromFunction(*I);
2718  }
2719 
2720  if (InvokeInst *II = dyn_cast<InvokeInst>(&MI)) {
2721  // Replace invoke with a NOP intrinsic to maintain the original CFG
2722  Module *M = II->getModule();
2723  Function *F = Intrinsic::getDeclaration(M, Intrinsic::donothing);
2724  InvokeInst::Create(F, II->getNormalDest(), II->getUnwindDest(),
2725  None, "", II->getParent());
2726  }
2727 
2728  // Remove debug intrinsics which describe the value contained within the
2729  // alloca. In addition to removing dbg.{declare,addr} which simply point to
2730  // the alloca, remove dbg.value(<alloca>, ..., DW_OP_deref)'s as well, e.g.:
2731  //
2732  // ```
2733  // define void @foo(i32 %0) {
2734  // %a = alloca i32 ; Deleted.
2735  // store i32 %0, i32* %a
2736  // dbg.value(i32 %0, "arg0") ; Not deleted.
2737  // dbg.value(i32* %a, "arg0", DW_OP_deref) ; Deleted.
2738  // call void @trivially_inlinable_no_op(i32* %a)
2739  // ret void
2740  // }
2741  // ```
2742  //
2743  // This may not be required if we stop describing the contents of allocas
2744  // using dbg.value(<alloca>, ..., DW_OP_deref), but we currently do this in
2745  // the LowerDbgDeclare utility.
2746  //
2747  // If there is a dead store to `%a` in @trivially_inlinable_no_op, the
2748  // "arg0" dbg.value may be stale after the call. However, failing to remove
2749  // the DW_OP_deref dbg.value causes large gaps in location coverage.
2750  for (auto *DVI : DVIs)
2751  if (DVI->isAddressOfVariable() || DVI->getExpression()->startsWithDeref())
2752  DVI->eraseFromParent();
2753 
2754  return eraseInstFromFunction(MI);
2755  }
2756  return nullptr;
2757 }
2758 
2759 /// Move the call to free before a NULL test.
2760 ///
2761 /// Check if this free is accessed after its argument has been test
2762 /// against NULL (property 0).
2763 /// If yes, it is legal to move this call in its predecessor block.
2764 ///
2765 /// The move is performed only if the block containing the call to free
2766 /// will be removed, i.e.:
2767 /// 1. it has only one predecessor P, and P has two successors
2768 /// 2. it contains the call, noops, and an unconditional branch
2769 /// 3. its successor is the same as its predecessor's successor
2770 ///
2771 /// The profitability is out-of concern here and this function should
2772 /// be called only if the caller knows this transformation would be
2773 /// profitable (e.g., for code size).
2775  const DataLayout &DL) {
2776  Value *Op = FI.getArgOperand(0);
2777  BasicBlock *FreeInstrBB = FI.getParent();
2778  BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor();
2779 
2780  // Validate part of constraint #1: Only one predecessor
2781  // FIXME: We can extend the number of predecessor, but in that case, we
2782  // would duplicate the call to free in each predecessor and it may
2783  // not be profitable even for code size.
2784  if (!PredBB)
2785  return nullptr;
2786 
2787  // Validate constraint #2: Does this block contains only the call to
2788  // free, noops, and an unconditional branch?
2789  BasicBlock *SuccBB;
2790  Instruction *FreeInstrBBTerminator = FreeInstrBB->getTerminator();
2791  if (!match(FreeInstrBBTerminator, m_UnconditionalBr(SuccBB)))
2792  return nullptr;
2793 
2794  // If there are only 2 instructions in the block, at this point,
2795  // this is the call to free and unconditional.
2796  // If there are more than 2 instructions, check that they are noops
2797  // i.e., they won't hurt the performance of the generated code.
2798  if (FreeInstrBB->size() != 2) {
2799  for (const Instruction &Inst : FreeInstrBB->instructionsWithoutDebug()) {
2800  if (&Inst == &FI || &Inst == FreeInstrBBTerminator)
2801  continue;
2802  auto *Cast = dyn_cast<CastInst>(&Inst);
2803  if (!Cast || !Cast->isNoopCast(DL))
2804  return nullptr;
2805  }
2806  }
2807  // Validate the rest of constraint #1 by matching on the pred branch.
2808  Instruction *TI = PredBB->getTerminator();
2809  BasicBlock *TrueBB, *FalseBB;
2810  ICmpInst::Predicate Pred;
2811  if (!match(TI, m_Br(m_ICmp(Pred,
2813  m_Specific(Op->stripPointerCasts())),
2814  m_Zero()),
2815  TrueBB, FalseBB)))
2816  return nullptr;
2817  if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE)
2818  return nullptr;
2819 
2820  // Validate constraint #3: Ensure the null case just falls through.
2821  if (SuccBB != (Pred == ICmpInst::ICMP_EQ ? TrueBB : FalseBB))
2822  return nullptr;
2823  assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) &&
2824  "Broken CFG: missing edge from predecessor to successor");
2825 
2826  // At this point, we know that everything in FreeInstrBB can be moved
2827  // before TI.
2828  for (Instruction &Instr : llvm::make_early_inc_range(*FreeInstrBB)) {
2829  if (&Instr == FreeInstrBBTerminator)
2830  break;
2831  Instr.moveBefore(TI);
2832  }
2833  assert(FreeInstrBB->size() == 1 &&
2834  "Only the branch instruction should remain");
2835  return &FI;
2836 }
2837 
2839  Value *Op = FI.getArgOperand(0);
2840 
2841  // free undef -> unreachable.
2842  if (isa<UndefValue>(Op)) {
2843  // Leave a marker since we can't modify the CFG here.
2844  CreateNonTerminatorUnreachable(&FI);
2845  return eraseInstFromFunction(FI);
2846  }
2847 
2848  // If we have 'free null' delete the instruction. This can happen in stl code
2849  // when lots of inlining happens.
2850  if (isa<ConstantPointerNull>(Op))
2851  return eraseInstFromFunction(FI);
2852 
2853  // If we optimize for code size, try to move the call to free before the null
2854  // test so that simplify cfg can remove the empty block and dead code
2855  // elimination the branch. I.e., helps to turn something like:
2856  // if (foo) free(foo);
2857  // into
2858  // free(foo);
2859  //
2860  // Note that we can only do this for 'free' and not for any flavor of
2861  // 'operator delete'; there is no 'operator delete' symbol for which we are
2862  // permitted to invent a call, even if we're passing in a null pointer.
2863  if (MinimizeSize) {
2864  LibFunc Func;
2865  if (TLI.getLibFunc(FI, Func) && TLI.has(Func) && Func == LibFunc_free)
2867  return I;
2868  }
2869 
2870  return nullptr;
2871 }
2872 
2873 static bool isMustTailCall(Value *V) {
2874  if (auto *CI = dyn_cast<CallInst>(V))
2875  return CI->isMustTailCall();
2876  return false;
2877 }
2878 
2880  if (RI.getNumOperands() == 0) // ret void
2881  return nullptr;
2882 
2883  Value *ResultOp = RI.getOperand(0);
2884  Type *VTy = ResultOp->getType();
2885  if (!VTy->isIntegerTy() || isa<Constant>(ResultOp))
2886  return nullptr;
2887 
2888  // Don't replace result of musttail calls.
2889  if (isMustTailCall(ResultOp))
2890  return nullptr;
2891 
2892  // There might be assume intrinsics dominating this return that completely
2893  // determine the value. If so, constant fold it.
2894  KnownBits Known = computeKnownBits(ResultOp, 0, &RI);
2895  if (Known.isConstant())
2896  return replaceOperand(RI, 0,
2897  Constant::getIntegerValue(VTy, Known.getConstant()));
2898 
2899  return nullptr;
2900 }
2901 
2902 // WARNING: keep in sync with SimplifyCFGOpt::simplifyUnreachable()!
2904  // Try to remove the previous instruction if it must lead to unreachable.
2905  // This includes instructions like stores and "llvm.assume" that may not get
2906  // removed by simple dead code elimination.
2907  while (Instruction *Prev = I.getPrevNonDebugInstruction()) {
2908  // While we theoretically can erase EH, that would result in a block that
2909  // used to start with an EH no longer starting with EH, which is invalid.
2910  // To make it valid, we'd need to fixup predecessors to no longer refer to
2911  // this block, but that changes CFG, which is not allowed in InstCombine.
2912  if (Prev->isEHPad())
2913  return nullptr; // Can not drop any more instructions. We're done here.
2914 
2916  return nullptr; // Can not drop any more instructions. We're done here.
2917  // Otherwise, this instruction can be freely erased,
2918  // even if it is not side-effect free.
2919 
2920  // A value may still have uses before we process it here (for example, in
2921  // another unreachable block), so convert those to poison.
2922  replaceInstUsesWith(*Prev, PoisonValue::get(Prev->getType()));
2923  eraseInstFromFunction(*Prev);
2924  }
2925  assert(I.getParent()->sizeWithoutDebug() == 1 && "The block is now empty.");
2926  // FIXME: recurse into unconditional predecessors?
2927  return nullptr;
2928 }
2929 
2931  assert(BI.isUnconditional() && "Only for unconditional branches.");
2932 
2933  // If this store is the second-to-last instruction in the basic block
2934  // (excluding debug info and bitcasts of pointers) and if the block ends with
2935  // an unconditional branch, try to move the store to the successor block.
2936 
2937  auto GetLastSinkableStore = [](BasicBlock::iterator BBI) {
2938  auto IsNoopInstrForStoreMerging = [](BasicBlock::iterator BBI) {
2939  return isa<DbgInfoIntrinsic>(BBI) ||
2940  (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy());
2941  };
2942 
2943  BasicBlock::iterator FirstInstr = BBI->getParent()->begin();
2944  do {
2945  if (BBI != FirstInstr)
2946  --BBI;
2947  } while (BBI != FirstInstr && IsNoopInstrForStoreMerging(BBI));
2948 
2949  return dyn_cast<StoreInst>(BBI);
2950  };
2951 
2952  if (StoreInst *SI = GetLastSinkableStore(BasicBlock::iterator(BI)))
2953  if (mergeStoreIntoSuccessor(*SI))
2954  return &BI;
2955 
2956  return nullptr;
2957 }
2958 
2960  if (BI.isUnconditional())
2961  return visitUnconditionalBranchInst(BI);
2962 
2963  // Change br (not X), label True, label False to: br X, label False, True
2964  Value *X = nullptr;
2965  if (match(&BI, m_Br(m_Not(m_Value(X)), m_BasicBlock(), m_BasicBlock())) &&
2966  !isa<Constant>(X)) {
2967  // Swap Destinations and condition...
2968  BI.swapSuccessors();
2969  return replaceOperand(BI, 0, X);
2970  }
2971 
2972  // If the condition is irrelevant, remove the use so that other
2973  // transforms on the condition become more effective.
2974  if (!isa<ConstantInt>(BI.getCondition()) &&
2975  BI.getSuccessor(0) == BI.getSuccessor(1))
2976  return replaceOperand(
2977  BI, 0, ConstantInt::getFalse(BI.getCondition()->getType()));
2978 
2979  // Canonicalize, for example, fcmp_one -> fcmp_oeq.
2980  CmpInst::Predicate Pred;
2981  if (match(&BI, m_Br(m_OneUse(m_FCmp(Pred, m_Value(), m_Value())),
2982  m_BasicBlock(), m_BasicBlock())) &&
2983  !isCanonicalPredicate(Pred)) {
2984  // Swap destinations and condition.
2985  CmpInst *Cond = cast<CmpInst>(BI.getCondition());
2986  Cond->setPredicate(CmpInst::getInversePredicate(Pred));
2987  BI.swapSuccessors();
2988  Worklist.push(Cond);
2989  return &BI;
2990  }
2991 
2992  return nullptr;
2993 }
2994 
2996  Value *Cond = SI.getCondition();
2997  Value *Op0;
2998  ConstantInt *AddRHS;
2999  if (match(Cond, m_Add(m_Value(Op0), m_ConstantInt(AddRHS)))) {
3000  // Change 'switch (X+4) case 1:' into 'switch (X) case -3'.
3001  for (auto Case : SI.cases()) {
3002  Constant *NewCase = ConstantExpr::getSub(Case.getCaseValue(), AddRHS);
3003  assert(isa<ConstantInt>(NewCase) &&
3004  "Result of expression should be constant");
3005  Case.setValue(cast<ConstantInt>(NewCase));
3006  }
3007  return replaceOperand(SI, 0, Op0);
3008  }
3009 
3010  KnownBits Known = computeKnownBits(Cond, 0, &SI);
3011  unsigned LeadingKnownZeros = Known.countMinLeadingZeros();
3012  unsigned LeadingKnownOnes = Known.countMinLeadingOnes();
3013 
3014  // Compute the number of leading bits we can ignore.
3015  // TODO: A better way to determine this would use ComputeNumSignBits().
3016  for (auto &C : SI.cases()) {
3017  LeadingKnownZeros = std::min(
3018  LeadingKnownZeros, C.getCaseValue()->getValue().countLeadingZeros());
3019  LeadingKnownOnes = std::min(
3020  LeadingKnownOnes, C.getCaseValue()->getValue().countLeadingOnes());
3021  }
3022 
3023  unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);
3024 
3025  // Shrink the condition operand if the new type is smaller than the old type.
3026  // But do not shrink to a non-standard type, because backend can't generate
3027  // good code for that yet.
3028  // TODO: We can make it aggressive again after fixing PR39569.
3029  if (NewWidth > 0 && NewWidth < Known.getBitWidth() &&
3030  shouldChangeType(Known.getBitWidth(), NewWidth)) {
3031  IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);
3032  Builder.SetInsertPoint(&SI);
3033  Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc");
3034 
3035  for (auto Case : SI.cases()) {
3036  APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);
3037  Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));
3038  }
3039  return replaceOperand(SI, 0, NewCond);
3040  }
3041 
3042  return nullptr;
3043 }
3044 
3046  Value *Agg = EV.getAggregateOperand();
3047 
3048  if (!EV.hasIndices())
3049  return replaceInstUsesWith(EV, Agg);
3050 
3051  if (Value *V = SimplifyExtractValueInst(Agg, EV.getIndices(),
3052  SQ.getWithInstruction(&EV)))
3053  return replaceInstUsesWith(EV, V);
3054 
3055  if (InsertValueInst *IV = dyn_cast<InsertValueInst>(Agg)) {
3056  // We're extracting from an insertvalue instruction, compare the indices
3057  const unsigned *exti, *exte, *insi, *inse;
3058  for (exti = EV.idx_begin(), insi = IV->idx_begin(),
3059  exte = EV.idx_end(), inse = IV->idx_end();
3060  exti != exte && insi != inse;
3061  ++exti, ++insi) {
3062  if (*insi != *exti)
3063  // The insert and extract both reference distinctly different elements.
3064  // This means the extract is not influenced by the insert, and we can
3065  // replace the aggregate operand of the extract with the aggregate
3066  // operand of the insert. i.e., replace
3067  // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1
3068  // %E = extractvalue { i32, { i32 } } %I, 0
3069  // with
3070  // %E = extractvalue { i32, { i32 } } %A, 0
3071  return ExtractValueInst::Create(IV->getAggregateOperand(),
3072  EV.getIndices());
3073  }
3074  if (exti == exte && insi == inse)
3075  // Both iterators are at the end: Index lists are identical. Replace
3076  // %B = insertvalue { i32, { i32 } } %A, i32 42, 1, 0
3077  // %C = extractvalue { i32, { i32 } } %B, 1, 0
3078  // with "i32 42"
3079  return replaceInstUsesWith(EV, IV->getInsertedValueOperand());
3080  if (exti == exte) {
3081  // The extract list is a prefix of the insert list. i.e. replace
3082  // %I = insertvalue { i32, { i32 } } %A, i32 42, 1, 0
3083  // %E = extractvalue { i32, { i32 } } %I, 1
3084  // with
3085  // %X = extractvalue { i32, { i32 } } %A, 1
3086  // %E = insertvalue { i32 } %X, i32 42, 0
3087  // by switching the order of the insert and extract (though the
3088  // insertvalue should be left in, since it may have other uses).
3089  Value *NewEV = Builder.CreateExtractValue(IV->getAggregateOperand(),
3090  EV.getIndices());
3091  return InsertValueInst::Create(NewEV, IV->getInsertedValueOperand(),
3092  makeArrayRef(insi, inse));
3093  }
3094  if (insi == inse)
3095  // The insert list is a prefix of the extract list
3096  // We can simply remove the common indices from the extract and make it
3097  // operate on the inserted value instead of the insertvalue result.
3098  // i.e., replace
3099  // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1
3100  // %E = extractvalue { i32, { i32 } } %I, 1, 0
3101  // with
3102  // %E extractvalue { i32 } { i32 42 }, 0
3103  return ExtractValueInst::Create(IV->getInsertedValueOperand(),
3104  makeArrayRef(exti, exte));
3105  }
3106  if (WithOverflowInst *WO = dyn_cast<WithOverflowInst>(Agg)) {
3107  // We're extracting from an overflow intrinsic, see if we're the only user,
3108  // which allows us to simplify multiple result intrinsics to simpler
3109  // things that just get one value.
3110  if (WO->hasOneUse()) {
3111  // Check if we're grabbing only the result of a 'with overflow' intrinsic
3112  // and replace it with a traditional binary instruction.
3113  if (*EV.idx_begin() == 0) {
3114  Instruction::BinaryOps BinOp = WO->getBinaryOp();
3115  Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
3116  // Replace the old instruction's uses with poison.
3117  replaceInstUsesWith(*WO, PoisonValue::get(WO->getType()));
3118  eraseInstFromFunction(*WO);
3119  return BinaryOperator::Create(BinOp, LHS, RHS);
3120  }
3121 
3122  assert(*EV.idx_begin() == 1 &&
3123  "unexpected extract index for overflow inst");
3124 
3125  // If only the overflow result is used, and the right hand side is a
3126  // constant (or constant splat), we can remove the intrinsic by directly
3127  // checking for overflow.
3128  const APInt *C;
3129  if (match(WO->getRHS(), m_APInt(C))) {
3130  // Compute the no-wrap range [X,Y) for LHS given RHS=C, then
3131  // check for the inverted range using range offset trick (i.e.
3132  // use a subtract to shift the range to bottom of either the
3133  // signed or unsigned domain and then use a single compare to
3134  // check range membership).
3135  ConstantRange NWR =
3136  ConstantRange::makeExactNoWrapRegion(WO->getBinaryOp(), *C,
3137  WO->getNoWrapKind());
3138  APInt Min = WO->isSigned() ? NWR.getSignedMin() : NWR.getUnsignedMin();
3139  NWR = NWR.subtract(Min);
3140 
3141  CmpInst::Predicate Pred;
3142  APInt NewRHSC;
3143  if (NWR.getEquivalentICmp(Pred, NewRHSC)) {
3144  auto *OpTy = WO->getRHS()->getType();
3145  auto *NewLHS = Builder.CreateSub(WO->getLHS(),
3146  ConstantInt::get(OpTy, Min));
3147  return new ICmpInst(ICmpInst::getInversePredicate(Pred), NewLHS,
3148  ConstantInt::get(OpTy, NewRHSC));
3149  }
3150  }
3151  }
3152  }
3153  if (LoadInst *L = dyn_cast<LoadInst>(Agg))
3154  // If the (non-volatile) load only has one use, we can rewrite this to a
3155  // load from a GEP. This reduces the size of the load. If a load is used
3156  // only by extractvalue instructions then this either must have been
3157  // optimized before, or it is a struct with padding, in which case we
3158  // don't want to do the transformation as it loses padding knowledge.
3159  if (L->isSimple() && L->hasOneUse()) {
3160  // extractvalue has integer indices, getelementptr has Value*s. Convert.
3161  SmallVector<Value*, 4> Indices;
3162  // Prefix an i32 0 since we need the first element.
3163  Indices.push_back(Builder.getInt32(0));
3164  for (unsigned Idx : EV.indices())
3165  Indices.push_back(Builder.getInt32(Idx));
3166 
3167  // We need to insert these at the location of the old load, not at that of
3168  // the extractvalue.
3169  Builder.SetInsertPoint(L);
3170  Value *GEP = Builder.CreateInBoundsGEP(L->getType(),
3171  L->getPointerOperand(), Indices);
3172  Instruction *NL = Builder.CreateLoad(EV.getType(), GEP);
3173  // Whatever aliasing information we had for the orignal load must also
3174  // hold for the smaller load, so propagate the annotations.
3175  NL->setAAMetadata(L->getAAMetadata());
3176  // Returning the load directly will cause the main loop to insert it in
3177  // the wrong spot, so use replaceInstUsesWith().
3178  return replaceInstUsesWith(EV, NL);
3179  }
3180  // We could simplify extracts from other values. Note that nested extracts may
3181  // already be simplified implicitly by the above: extract (extract (insert) )
3182  // will be translated into extract ( insert ( extract ) ) first and then just
3183  // the value inserted, if appropriate. Similarly for extracts from single-use
3184  // loads: extract (extract (load)) will be translated to extract (load (gep))
3185  // and if again single-use then via load (gep (gep)) to load (gep).
3186  // However, double extracts from e.g. function arguments or return values
3187  // aren't handled yet.
3188  return nullptr;
3189 }
3190 
3191 /// Return 'true' if the given typeinfo will match anything.
3192 static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo) {
3193  switch (Personality) {
3194  case EHPersonality::GNU_C:
3196  case EHPersonality::Rust:
3197  // The GCC C EH and Rust personality only exists to support cleanups, so
3198  // it's not clear what the semantics of catch clauses are.
3199  return false;
3201  return false;
3203  // While __gnat_all_others_value will match any Ada exception, it doesn't
3204  // match foreign exceptions (or didn't, before gcc-4.7).
3205  return false;
3214  case EHPersonality::XL_CXX:
3215  return TypeInfo->isNullValue();
3216  }
3217  llvm_unreachable("invalid enum");
3218 }
3219 
3220 static bool shorter_filter(const Value *LHS, const Value *RHS) {
3221  return
3222  cast<ArrayType>(LHS->getType())->getNumElements()
3223  <
3224  cast<ArrayType>(RHS->getType())->getNumElements();
3225 }
3226 
3228  // The logic here should be correct for any real-world personality function.
3229  // However if that turns out not to be true, the offending logic can always
3230  // be conditioned on the personality function, like the catch-all logic is.
3231  EHPersonality Personality =
3233 
3234  // Simplify the list of clauses, eg by removing repeated catch clauses
3235  // (these are often created by inlining).
3236  bool MakeNewInstruction = false; // If true, recreate using the following:
3237  SmallVector<Constant *, 16> NewClauses; // - Clauses for the new instruction;
3238  bool CleanupFlag = LI.isCleanup(); // - The new instruction is a cleanup.
3239 
3240  SmallPtrSet<Value *, 16> AlreadyCaught; // Typeinfos known caught already.
3241  for (unsigned i = 0, e = LI.getNumClauses(); i != e; ++i) {
3242  bool isLastClause = i + 1 == e;
3243  if (LI.isCatch(i)) {
3244  // A catch clause.
3245  Constant *CatchClause = LI.getClause(i);
3246  Constant *TypeInfo = CatchClause->stripPointerCasts();
3247 
3248  // If we already saw this clause, there is no point in having a second
3249  // copy of it.
3250  if (AlreadyCaught.insert(TypeInfo).second) {
3251  // This catch clause was not already seen.
3252  NewClauses.push_back(CatchClause);
3253  } else {
3254  // Repeated catch clause - drop the redundant copy.
3255  MakeNewInstruction = true;
3256  }
3257 
3258  // If this is a catch-all then there is no point in keeping any following
3259  // clauses or marking the landingpad as having a cleanup.
3260  if (isCatchAll(Personality, TypeInfo)) {
3261  if (!isLastClause)
3262  MakeNewInstruction = true;
3263  CleanupFlag = false;
3264  break;
3265  }
3266  } else {
3267  // A filter clause. If any of the filter elements were already caught
3268  // then they can be dropped from the filter. It is tempting to try to
3269  // exploit the filter further by saying that any typeinfo that does not
3270  // occur in the filter can't be caught later (and thus can be dropped).
3271  // However this would be wrong, since typeinfos can match without being
3272  // equal (for example if one represents a C++ class, and the other some
3273  // class derived from it).
3274  assert(LI.isFilter(i) && "Unsupported landingpad clause!");
3275  Constant *FilterClause = LI.getClause(i);
3276  ArrayType *FilterType = cast<ArrayType>(FilterClause->getType());
3277  unsigned NumTypeInfos = FilterType->getNumElements();
3278 
3279  // An empty filter catches everything, so there is no point in keeping any
3280  // following clauses or marking the landingpad as having a cleanup. By
3281  // dealing with this case here the following code is made a bit simpler.
3282  if (!NumTypeInfos) {
3283  NewClauses.push_back(FilterClause);
3284  if (!isLastClause)
3285  MakeNewInstruction = true;
3286  CleanupFlag = false;
3287  break;
3288  }
3289 
3290  bool MakeNewFilter = false; // If true, make a new filter.
3291  SmallVector<Constant *, 16> NewFilterElts; // New elements.
3292  if (isa<ConstantAggregateZero>(FilterClause)) {
3293  // Not an empty filter - it contains at least one null typeinfo.
3294  assert(NumTypeInfos > 0 && "Should have handled empty filter already!");
3295  Constant *TypeInfo =
3296  Constant::getNullValue(FilterType->getElementType());
3297  // If this typeinfo is a catch-all then the filter can never match.
3298  if (isCatchAll(Personality, TypeInfo)) {
3299  // Throw the filter away.
3300  MakeNewInstruction = true;
3301  continue;
3302  }
3303 
3304  // There is no point in having multiple copies of this typeinfo, so
3305  // discard all but the first copy if there is more than one.
3306  NewFilterElts.push_back(TypeInfo);
3307  if (NumTypeInfos > 1)
3308  MakeNewFilter = true;
3309  } else {
3310  ConstantArray *Filter = cast<ConstantArray>(FilterClause);
3311  SmallPtrSet<Value *, 16> SeenInFilter; // For uniquing the elements.
3312  NewFilterElts.reserve(NumTypeInfos);
3313 
3314  // Remove any filter elements that were already caught or that already
3315  // occurred in the filter. While there, see if any of the elements are
3316  // catch-alls. If so, the filter can be discarded.
3317  bool SawCatchAll = false;
3318  for (unsigned j = 0; j != NumTypeInfos; ++j) {
3319  Constant *Elt = Filter->getOperand(j);
3320  Constant *TypeInfo = Elt->stripPointerCasts();
3321  if (isCatchAll(Personality, TypeInfo)) {
3322  // This element is a catch-all. Bail out, noting this fact.
3323  SawCatchAll = true;
3324  break;
3325  }
3326 
3327  // Even if we've seen a type in a catch clause, we don't want to
3328  // remove it from the filter. An unexpected type handler may be
3329  // set up for a call site which throws an exception of the same
3330  // type caught. In order for the exception thrown by the unexpected
3331  // handler to propagate correctly, the filter must be correctly
3332  // described for the call site.
3333  //
3334  // Example:
3335  //
3336  // void unexpected() { throw 1;}
3337  // void foo() throw (int) {
3338  // std::set_unexpected(unexpected);
3339  // try {
3340  // throw 2.0;
3341  // } catch (int i) {}
3342  // }
3343 
3344  // There is no point in having multiple copies of the same typeinfo in
3345  // a filter, so only add it if we didn't already.
3346  if (SeenInFilter.insert(TypeInfo).second)
3347  NewFilterElts.push_back(cast<Constant>(Elt));
3348  }
3349  // A filter containing a catch-all cannot match anything by definition.
3350  if (SawCatchAll) {
3351  // Throw the filter away.
3352  MakeNewInstruction = true;
3353  continue;
3354  }
3355 
3356  // If we dropped something from the filter, make a new one.
3357  if (NewFilterElts.size() < NumTypeInfos)
3358  MakeNewFilter = true;
3359  }
3360  if (MakeNewFilter) {
3361  FilterType = ArrayType::get(FilterType->getElementType(),
3362  NewFilterElts.size());
3363  FilterClause = ConstantArray::get(FilterType, NewFilterElts);
3364  MakeNewInstruction = true;
3365  }
3366 
3367  NewClauses.push_back(FilterClause);
3368 
3369  // If the new filter is empty then it will catch everything so there is
3370  // no point in keeping any following clauses or marking the landingpad
3371  // as having a cleanup. The case of the original filter being empty was
3372  // already handled above.
3373  if (MakeNewFilter && !NewFilterElts.size()) {
3374  assert(MakeNewInstruction && "New filter but not a new instruction!");
3375  CleanupFlag = false;
3376  break;
3377  }
3378  }
3379  }
3380 
3381  // If several filters occur in a row then reorder them so that the shortest
3382  // filters come first (those with the smallest number of elements). This is
3383  // advantageous because shorter filters are more likely to match, speeding up
3384  // unwinding, but mostly because it increases the effectiveness of the other
3385  // filter optimizations below.
3386  for (unsigned i = 0, e = NewClauses.size(); i + 1 < e; ) {
3387  unsigned j;
3388  // Find the maximal 'j' s.t. the range [i, j) consists entirely of filters.
3389  for (j = i; j != e; ++j)
3390  if (!isa<ArrayType>(NewClauses[j]->getType()))
3391  break;
3392 
3393  // Check whether the filters are already sorted by length. We need to know
3394  // if sorting them is actually going to do anything so that we only make a
3395  // new landingpad instruction if it does.
3396  for (unsigned k = i; k + 1 < j; ++k)
3397  if (shorter_filter(NewClauses[k+1], NewClauses[k])) {
3398  // Not sorted, so sort the filters now. Doing an unstable sort would be
3399  // correct too but reordering filters pointlessly might confuse users.
3400  std::stable_sort(NewClauses.begin() + i, NewClauses.begin() + j,
3401  shorter_filter);
3402  MakeNewInstruction = true;
3403  break;
3404  }
3405 
3406  // Look for the next batch of filters.
3407  i = j + 1;
3408  }
3409 
3410  // If typeinfos matched if and only if equal, then the elements of a filter L
3411  // that occurs later than a filter F could be replaced by the intersection of
3412  // the elements of F and L. In reality two typeinfos can match without being
3413  // equal (for example if one represents a C++ class, and the other some class
3414  // derived from it) so it would be wrong to perform this transform in general.
3415  // However the transform is correct and useful if F is a subset of L. In that
3416  // case L can be replaced by F, and thus removed altogether since repeating a
3417  // filter is pointless. So here we look at all pairs of filters F and L where
3418  // L follows F in the list of clauses, and remove L if every element of F is
3419  // an element of L. This can occur when inlining C++ functions with exception
3420  // specifications.
3421  for (unsigned i = 0; i + 1 < NewClauses.size(); ++i) {
3422  // Examine each filter in turn.
3423  Value *Filter = NewClauses[i];
3424  ArrayType *FTy = dyn_cast<ArrayType>(Filter->getType());
3425  if (!FTy)
3426  // Not a filter - skip it.
3427  continue;
3428  unsigned FElts = FTy->getNumElements();
3429  // Examine each filter following this one. Doing this backwards means that
3430  // we don't have to worry about filters disappearing under us when removed.
3431  for (unsigned j = NewClauses.size() - 1; j != i; --j) {
3432  Value *LFilter = NewClauses[j];
3433  ArrayType *LTy = dyn_cast<ArrayType>(LFilter->getType());
3434  if (!LTy)
3435  // Not a filter - skip it.
3436  continue;
3437  // If Filter is a subset of LFilter, i.e. every element of Filter is also
3438  // an element of LFilter, then discard LFilter.
3439  SmallVectorImpl<Constant *>::iterator J = NewClauses.begin() + j;
3440  // If Filter is empty then it is a subset of LFilter.
3441  if (!FElts) {
3442  // Discard LFilter.
3443  NewClauses.erase(J);
3444  MakeNewInstruction = true;
3445  // Move on to the next filter.
3446  continue;
3447  }
3448  unsigned LElts = LTy->getNumElements();
3449  // If Filter is longer than LFilter then it cannot be a subset of it.
3450  if (FElts > LElts)
3451  // Move on to the next filter.
3452  continue;
3453  // At this point we know that LFilter has at least one element.
3454  if (isa<ConstantAggregateZero>(LFilter)) { // LFilter only contains zeros.
3455  // Filter is a subset of LFilter iff Filter contains only zeros (as we
3456  // already know that Filter is not longer than LFilter).
3457  if (isa<ConstantAggregateZero>(Filter)) {
3458  assert(FElts <= LElts && "Should have handled this case earlier!");
3459  // Discard LFilter.
3460  NewClauses.erase(J);
3461  MakeNewInstruction = true;
3462  }
3463  // Move on to the next filter.
3464  continue;
3465  }
3466  ConstantArray *LArray = cast<ConstantArray>(LFilter);
3467  if (isa<ConstantAggregateZero>(Filter)) { // Filter only contains zeros.
3468  // Since Filter is non-empty and contains only zeros, it is a subset of
3469  // LFilter iff LFilter contains a zero.
3470  assert(FElts > 0 && "Should have eliminated the empty filter earlier!");
3471  for (unsigned l = 0; l != LElts; ++l)
3472  if (LArray->getOperand(l)->isNullValue()) {
3473  // LFilter contains a zero - discard it.
3474  NewClauses.erase(J);
3475  MakeNewInstruction = true;
3476  break;
3477  }
3478  // Move on to the next filter.
3479  continue;
3480  }
3481  // At this point we know that both filters are ConstantArrays. Loop over
3482  // operands to see whether every element of Filter is also an element of
3483  // LFilter. Since filters tend to be short this is probably faster than
3484  // using a method that scales nicely.
3485  ConstantArray *FArray = cast<ConstantArray>(Filter);
3486  bool AllFound = true;
3487  for (unsigned f = 0; f != FElts; ++f) {
3488  Value *FTypeInfo = FArray->getOperand(f)->stripPointerCasts();
3489  AllFound = false;
3490  for (unsigned l = 0; l != LElts; ++l) {
3491  Value *LTypeInfo = LArray->getOperand(l)->stripPointerCasts();
3492  if (LTypeInfo == FTypeInfo) {
3493  AllFound = true;
3494  break;
3495  }
3496  }
3497  if (!AllFound)
3498  break;
3499  }
3500  if (AllFound) {
3501  // Discard LFilter.
3502  NewClauses.erase(J);
3503  MakeNewInstruction = true;
3504  }
3505  // Move on to the next filter.
3506  }
3507  }
3508 
3509  // If we changed any of the clauses, replace the old landingpad instruction
3510  // with a new one.
3511  if (MakeNewInstruction) {
3513  NewClauses.size());
3514  for (unsigned i = 0, e = NewClauses.size(); i != e; ++i)
3515  NLI->addClause(NewClauses[i]);
3516  // A landing pad with no clauses must have the cleanup flag set. It is
3517  // theoretically possible, though highly unlikely, that we eliminated all
3518  // clauses. If so, force the cleanup flag to true.
3519  if (NewClauses.empty())
3520  CleanupFlag = true;
3521  NLI->setCleanup(CleanupFlag);
3522  return NLI;
3523  }
3524 
3525  // Even if none of the clauses changed, we may nonetheless have understood
3526  // that the cleanup flag is pointless. Clear it if so.
3527  if (LI.isCleanup() != CleanupFlag) {
3528  assert(!CleanupFlag && "Adding a cleanup, not removing one?!");
3529  LI.setCleanup(CleanupFlag);
3530  return &LI;
3531  }
3532 
3533  return nullptr;
3534 }
3535 
3536 Value *
3538  // Try to push freeze through instructions that propagate but don't produce
3539  // poison as far as possible. If an operand of freeze follows three
3540  // conditions 1) one-use, 2) does not produce poison, and 3) has all but one
3541  // guaranteed-non-poison operands then push the freeze through to the one
3542  // operand that is not guaranteed non-poison. The actual transform is as
3543  // follows.
3544  // Op1 = ... ; Op1 can be posion
3545  // Op0 = Inst(Op1, NonPoisonOps...) ; Op0 has only one use and only have
3546  // ; single guaranteed-non-poison operands
3547  // ... = Freeze(Op0)
3548  // =>
3549  // Op1 = ...
3550  // Op1.fr = Freeze(Op1)
3551  // ... = Inst(Op1.fr, NonPoisonOps...)
3552  auto *OrigOp = OrigFI.getOperand(0);
3553  auto *OrigOpInst = dyn_cast<Instruction>(OrigOp);
3554 
3555  // While we could change the other users of OrigOp to use freeze(OrigOp), that
3556  // potentially reduces their optimization potential, so let's only do this iff
3557  // the OrigOp is only used by the freeze.
3558  if (!OrigOpInst || !OrigOpInst->hasOneUse() || isa<PHINode>(OrigOp) ||
3559  canCreateUndefOrPoison(dyn_cast<Operator>(OrigOp)))
3560  return nullptr;
3561 
3562  // If operand is guaranteed not to be poison, there is no need to add freeze
3563  // to the operand. So we first find the operand that is not guaranteed to be
3564  // poison.
3565  Use *MaybePoisonOperand = nullptr;
3566  for (Use &U : OrigOpInst->operands()) {
3567  if (isGuaranteedNotToBeUndefOrPoison(U.get()))
3568  continue;
3569  if (!MaybePoisonOperand)
3570  MaybePoisonOperand = &U;
3571  else
3572  return nullptr;
3573  }
3574 
3575  // If all operands are guaranteed to be non-poison, we can drop freeze.
3576  if (!MaybePoisonOperand)
3577  return OrigOp;
3578 
3579  auto *FrozenMaybePoisonOperand = new FreezeInst(
3580  MaybePoisonOperand->get(), MaybePoisonOperand->get()->getName() + ".fr");
3581 
3582  replaceUse(*MaybePoisonOperand, FrozenMaybePoisonOperand);
3583  FrozenMaybePoisonOperand->insertBefore(OrigOpInst);
3584  return OrigOp;
3585 }
3586 
3588  Value *Op = FI.getOperand(0);
3589 
3590  if (isa<Constant>(Op))
3591  return false;
3592 
3593  bool Changed = false;
3594  Op->replaceUsesWithIf(&FI, [&](Use &U) -> bool {
3595  bool Dominates = DT.dominates(&FI, U);
3596  Changed |= Dominates;
3597  return Dominates;
3598  });
3599 
3600  return Changed;
3601 }
3602 
3604  Value *Op0 = I.getOperand(0);
3605 
3606  if (Value *V = SimplifyFreezeInst(Op0, SQ.getWithInstruction(&I)))
3607  return replaceInstUsesWith(I, V);
3608 
3609  // freeze (phi const, x) --> phi const, (freeze x)
3610  if (auto *PN = dyn_cast<PHINode>(Op0)) {
3611  if (Instruction *NV = foldOpIntoPhi(I, PN))
3612  return NV;
3613  }
3614 
3615  if (Value *NI = pushFreezeToPreventPoisonFromPropagating(I))
3616  return replaceInstUsesWith(I, NI);
3617 
3618  if (match(Op0, m_Undef())) {
3619  // If I is freeze(undef), see its uses and fold it to the best constant.
3620  // - or: pick -1
3621  // - select's condition: pick the value that leads to choosing a constant
3622  // - other ops: pick 0
3623  Constant *BestValue = nullptr;
3624  Constant *NullValue = Constant::getNullValue(I.getType());
3625  for (const auto *U : I.users()) {
3626  Constant *C = NullValue;
3627 
3628  if (match(U, m_Or(m_Value(), m_Value())))
3629  C = Constant::getAllOnesValue(I.getType());
3630  else if (const auto *SI = dyn_cast<SelectInst>(U)) {
3631  if (SI->getCondition() == &I) {
3632  APInt CondVal(1, isa<Constant>(SI->getFalseValue()) ? 0 : 1);
3633  C = Constant::getIntegerValue(I.getType(), CondVal);
3634  }
3635  }
3636 
3637  if (!BestValue)
3638  BestValue = C;
3639  else if (BestValue != C)
3640  BestValue = NullValue;
3641  }
3642 
3643  return replaceInstUsesWith(I, BestValue);
3644  }
3645 
3646  // Replace all dominated uses of Op to freeze(Op).
3647  if (freezeDominatedUses(I))
3648  return &I;
3649 
3650  return nullptr;
3651 }
3652 
3653 /// Try to move the specified instruction from its current block into the
3654 /// beginning of DestBlock, which can only happen if it's safe to move the
3655 /// instruction past all of the instructions between it and the end of its
3656 /// block.
3657 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
3658  assert(I->getSingleUndroppableUse() && "Invariants didn't hold!");
3659  BasicBlock *SrcBlock = I->getParent();
3660 
3661  // Cannot move control-flow-involving, volatile loads, vaarg, etc.
3662  if (isa<PHINode>(I) || I->isEHPad() || I->mayHaveSideEffects() ||
3663  I->isTerminator())
3664  return false;
3665 
3666  // Do not sink static or dynamic alloca instructions. Static allocas must
3667  // remain in the entry block, and dynamic allocas must not be sunk in between
3668  // a stacksave / stackrestore pair, which would incorrectly shorten its
3669  // lifetime.
3670  if (isa<AllocaInst>(I))
3671  return false;
3672 
3673  // Do not sink into catchswitch blocks.
3674  if (isa<CatchSwitchInst>(DestBlock->getTerminator()))
3675  return false;
3676 
3677  // Do not sink convergent call instructions.
3678  if (auto *CI = dyn_cast<CallInst>(I)) {
3679  if (CI->isConvergent())
3680  return false;
3681  }
3682  // We can only sink load instructions if there is nothing between the load and
3683  // the end of block that could change the value.
3684  if (I->mayReadFromMemory()) {
3685  // We don't want to do any sophisticated alias analysis, so we only check
3686  // the instructions after I in I's parent block if we try to sink to its
3687  // successor block.
3688  if (DestBlock->getUniquePredecessor() != I->getParent())
3689  return false;
3690  for (BasicBlock::iterator Scan = I->getIterator(),
3691  E = I->getParent()->end();
3692  Scan != E; ++Scan)
3693  if (Scan->mayWriteToMemory())
3694  return false;
3695  }
3696 
3697  I->dropDroppableUses([DestBlock](const Use *U) {
3698  if (auto *I = dyn_cast<Instruction>(U->getUser()))
3699  return I->getParent() != DestBlock;
3700  return true;
3701  });
3702  /// FIXME: We could remove droppable uses that are not dominated by
3703  /// the new position.
3704 
3705  BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();
3706  I->moveBefore(&*InsertPos);
3707  ++NumSunkInst;
3708 
3709  // Also sink all related debug uses from the source basic block. Otherwise we
3710  // get debug use before the def. Attempt to salvage debug uses first, to
3711  // maximise the range variables have location for. If we cannot salvage, then
3712  // mark the location undef: we know it was supposed to receive a new location
3713  // here, but that computation has been sunk.
3715  findDbgUsers(DbgUsers, I);
3716  // Process the sinking DbgUsers in reverse order, as we only want to clone the
3717  // last appearing debug intrinsic for each given variable.
3719  for (DbgVariableIntrinsic *DVI : DbgUsers)
3720  if (DVI->getParent() == SrcBlock)
3721  DbgUsersToSink.push_back(DVI);
3722  llvm::sort(DbgUsersToSink,
3723  [](auto *A, auto *B) { return B->comesBefore(A); });
3724 
3726  SmallSet<DebugVariable, 4> SunkVariables;
3727  for (auto User : DbgUsersToSink) {
3728  // A dbg.declare instruction should not be cloned, since there can only be
3729  // one per variable fragment. It should be left in the original place
3730  // because the sunk instruction is not an alloca (otherwise we could not be
3731  // here).
3732  if (isa<DbgDeclareInst>(User))
3733  continue;
3734 
3735  DebugVariable DbgUserVariable =
3736  DebugVariable(User->getVariable(), User->getExpression(),
3737  User->getDebugLoc()->getInlinedAt());
3738 
3739  if (!SunkVariables.insert(DbgUserVariable).second)
3740  continue;
3741 
3742  DIIClones.emplace_back(cast<DbgVariableIntrinsic>(User->clone()));
3743  if (isa<DbgDeclareInst>(User) && isa<CastInst>(I))
3744  DIIClones.back()->replaceVariableLocationOp(I, I->getOperand(0));
3745  LLVM_DEBUG(dbgs() << "CLONE: " << *DIIClones.back() << '\n');
3746  }
3747 
3748  // Perform salvaging without the clones, then sink the clones.
3749  if (!DIIClones.empty()) {
3750  salvageDebugInfoForDbgValues(*I, DbgUsers);
3751  // The clones are in reverse order of original appearance, reverse again to
3752  // maintain the original order.
3753  for (auto &DIIClone : llvm::reverse(DIIClones)) {
3754  DIIClone->insertBefore(&*InsertPos);
3755  LLVM_DEBUG(dbgs() << "SINK: " << *DIIClone << '\n');
3756  }
3757  }
3758 
3759  return true;
3760 }
3761 
3763  while (!Worklist.isEmpty()) {
3764  // Walk deferred instructions in reverse order, and push them to the
3765  // worklist, which means they'll end up popped from the worklist in-order.
3766  while (Instruction *I = Worklist.popDeferred()) {
3767  // Check to see if we can DCE the instruction. We do this already here to
3768  // reduce the number of uses and thus allow other folds to trigger.
3769  // Note that eraseInstFromFunction() may push additional instructions on
3770  // the deferred worklist, so this will DCE whole instruction chains.
3771  if (isInstructionTriviallyDead(I, &TLI)) {
3772  eraseInstFromFunction(*I);
3773  ++NumDeadInst;
3774  continue;
3775  }
3776 
3777  Worklist.push(I);
3778  }
3779 
3780  Instruction *I = Worklist.removeOne();
3781  if (I == nullptr) continue; // skip null values.
3782 
3783  // Check to see if we can DCE the instruction.
3784  if (isInstructionTriviallyDead(I, &TLI)) {
3785  eraseInstFromFunction(*I);
3786  ++NumDeadInst;
3787  continue;
3788  }
3789 
3790  if (!DebugCounter::shouldExecute(VisitCounter))
3791  continue;
3792 
3793  // Instruction isn't dead, see if we can constant propagate it.
3794  if (!I->use_empty() &&
3795  (I->getNumOperands() == 0 || isa<Constant>(I->getOperand(0)))) {
3796  if (Constant *C = ConstantFoldInstruction(I, DL, &TLI)) {
3797  LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I
3798  << '\n');
3799 
3800  // Add operands to the worklist.
3801  replaceInstUsesWith(*I, C);
3802  ++NumConstProp;
3803  if (isInstructionTriviallyDead(I, &TLI))
3804  eraseInstFromFunction(*I);
3805  MadeIRChange = true;
3806  continue;
3807  }
3808  }
3809 
3810  // See if we can trivially sink this instruction to its user if we can
3811  // prove that the successor is not executed more frequently than our block.
3812  // Return the UserBlock if successful.
3813  auto getOptionalSinkBlockForInst =
3814  [this](Instruction *I) -> Optional<BasicBlock *> {
3815  if (!EnableCodeSinking)
3816  return None;
3817  Use *SingleUse = I->getSingleUndroppableUse();
3818  if (!SingleUse)
3819  return None;
3820 
3821  BasicBlock *BB = I->getParent();
3822  Instruction *UserInst = cast<Instruction>(SingleUse->getUser());
3823  BasicBlock *UserParent;
3824 
3825  // Get the block the use occurs in.
3826  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
3827  UserParent = PN->getIncomingBlock(*SingleUse);
3828  else
3829  UserParent = UserInst->getParent();
3830 
3831  // Try sinking to another block. If that block is unreachable, then do
3832  // not bother. SimplifyCFG should handle it.
3833  if (UserParent == BB || !DT.isReachableFromEntry(UserParent))
3834  return None;
3835 
3836  auto *Term = UserParent->getTerminator();
3837  // See if the user is one of our successors that has only one
3838  // predecessor, so that we don't have to split the critical edge.
3839  // Another option where we can sink is a block that ends with a
3840  // terminator that does not pass control to other block (such as
3841  // return or unreachable). In this case:
3842  // - I dominates the User (by SSA form);
3843  // - the User will be executed at most once.
3844  // So sinking I down to User is always profitable or neutral.
3845  if (UserParent->getUniquePredecessor() == BB ||
3846  (isa<ReturnInst>(Term) || isa<UnreachableInst>(Term))) {
3847  assert(DT.dominates(BB, UserParent) && "Dominance relation broken?");
3848  return UserParent;
3849  }
3850  return None;
3851  };
3852 
3853  auto OptBB = getOptionalSinkBlockForInst(I);
3854  if (OptBB) {
3855  auto *UserParent = *OptBB;
3856  // Okay, the CFG is simple enough, try to sink this instruction.
3857  if (TryToSinkInstruction(I, UserParent)) {
3858  LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
3859  MadeIRChange = true;
3860  // We'll add uses of the sunk instruction below, but since
3861  // sinking can expose opportunities for it's *operands* add
3862  // them to the worklist
3863  for (Use &U : I->operands())
3864  if (Instruction *OpI = dyn_cast<Instruction>(U.get()))
3865  Worklist.push(OpI);
3866  }
3867  }
3868 
3869  // Now that we have an instruction, try combining it to simplify it.
3870  Builder.SetInsertPoint(I);
3871  Builder.CollectMetadataToCopy(
3872  I, {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
3873 
3874 #ifndef NDEBUG
3875  std::string OrigI;
3876 #endif
3877  LLVM_DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str(););
3878  LLVM_DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n');
3879 
3880  if (Instruction *Result = visit(*I)) {
3881  ++NumCombined;
3882  // Should we replace the old instruction with a new one?
3883  if (Result != I) {
3884  LLVM_DEBUG(dbgs() << "IC: Old = " << *I << '\n'
3885  << " New = " << *Result << '\n');
3886 
3887  Result->copyMetadata(*I,
3888  {LLVMContext::MD_dbg, LLVMContext::MD_annotation});
3889  // Everything uses the new instruction now.
3890  I->replaceAllUsesWith(Result);
3891 
3892  // Move the name to the new instruction first.
3893  Result->takeName(I);
3894 
3895  // Insert the new instruction into the basic block...
3896  BasicBlock *InstParent = I->getParent();
3897  BasicBlock::iterator InsertPos = I->getIterator();
3898 
3899  // Are we replace a PHI with something that isn't a PHI, or vice versa?
3900  if (isa<PHINode>(Result) != isa<PHINode>(I)) {
3901  // We need to fix up the insertion point.
3902  if (isa<PHINode>(I)) // PHI -> Non-PHI
3903  InsertPos = InstParent->getFirstInsertionPt();
3904  else // Non-PHI -> PHI
3905  InsertPos = InstParent->getFirstNonPHI()->getIterator();
3906  }
3907 
3908  InstParent->getInstList().insert(InsertPos, Result);
3909 
3910  // Push the new instruction and any users onto the worklist.
3911  Worklist.pushUsersToWorkList(*Result);
3912  Worklist.push(Result);
3913 
3914  eraseInstFromFunction(*I);
3915  } else {
3916  LLVM_DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n'
3917  << " New = " << *I << '\n');
3918 
3919  // If the instruction was modified, it's possible that it is now dead.
3920  // if so, remove it.
3921  if (isInstructionTriviallyDead(I, &TLI)) {
3922  eraseInstFromFunction(*I);
3923  } else {
3924  Worklist.pushUsersToWorkList(*I);
3925  Worklist.push(I);
3926  }
3927  }
3928  MadeIRChange = true;
3929  }
3930  }
3931 
3932  Worklist.zap();
3933  return MadeIRChange;
3934 }
3935 
3936 // Track the scopes used by !alias.scope and !noalias. In a function, a
3937 // @llvm.experimental.noalias.scope.decl is only useful if that scope is used
3938 // by both sets. If not, the declaration of the scope can be safely omitted.
3939 // The MDNode of the scope can be omitted as well for the instructions that are
3940 // part of this function. We do not do that at this point, as this might become
3941 // too time consuming to do.
3943  SmallPtrSet<const MDNode *, 8> UsedAliasScopesAndLists;
3944  SmallPtrSet<const MDNode *, 8> UsedNoAliasScopesAndLists;
3945 
3946 public:
3948  // This seems to be faster than checking 'mayReadOrWriteMemory()'.
3949  if (!I->hasMetadataOtherThanDebugLoc())
3950  return;
3951 
3952  auto Track = [](Metadata *ScopeList, auto &Container) {
3953  const auto *MDScopeList = dyn_cast_or_null<MDNode>(ScopeList);
3954  if (!MDScopeList || !Container.insert(MDScopeList).second)
3955  return;
3956  for (auto &MDOperand : MDScopeList->operands())
3957  if (auto *MDScope = dyn_cast<MDNode>(MDOperand))
3958  Container.insert(MDScope);
3959  };
3960 
3961  Track(I->getMetadata(LLVMContext::MD_alias_scope), UsedAliasScopesAndLists);
3962  Track(I->getMetadata(LLVMContext::MD_noalias), UsedNoAliasScopesAndLists);
3963  }
3964 
3966  NoAliasScopeDeclInst *Decl = dyn_cast<NoAliasScopeDeclInst>(Inst);
3967  if (!Decl)
3968  return false;
3969 
3970  assert(Decl->use_empty() &&
3971  "llvm.experimental.noalias.scope.decl in use ?");
3972  const MDNode *MDSL = Decl->getScopeList();
3973  assert(MDSL->getNumOperands() == 1 &&
3974  "llvm.experimental.noalias.scope should refer to a single scope");
3975  auto &MDOperand = MDSL->getOperand(0);
3976  if (auto *MD = dyn_cast<MDNode>(MDOperand))
3977  return !UsedAliasScopesAndLists.contains(MD) ||
3978  !UsedNoAliasScopesAndLists.contains(MD);
3979 
3980  // Not an MDNode ? throw away.
3981  return true;
3982  }
3983 };
3984 
3985 /// Populate the IC worklist from a function, by walking it in depth-first
3986 /// order and adding all reachable code to the worklist.
3987 ///
3988 /// This has a couple of tricks to make the code faster and more powerful. In
3989 /// particular, we constant fold and DCE instructions as we go, to avoid adding
3990 /// them to the worklist (this significantly speeds up instcombine on code where
3991 /// many instructions are dead or constant). Additionally, if we find a branch
3992 /// whose condition is a known constant, we only visit the reachable successors.
3994  const TargetLibraryInfo *TLI,
3995  InstCombineWorklist &ICWorklist) {
3996  bool MadeIRChange = false;
3999  Worklist.push_back(&F.front());
4000 
4001  SmallVector<Instruction*, 128> InstrsForInstCombineWorklist;
4002  DenseMap<Constant *, Constant *> FoldedConstants;
4003  AliasScopeTracker SeenAliasScopes;
4004 
4005  do {
4006  BasicBlock *BB = Worklist.pop_back_val();
4007 
4008  // We have now visited this block! If we've already been here, ignore it.
4009  if (!Visited.insert(BB).second)
4010  continue;
4011 
4012  for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
4013  // ConstantProp instruction if trivially constant.
4014  if (!Inst.use_empty() &&
4015  (Inst.getNumOperands() == 0 || isa<Constant>(Inst.getOperand(0))))
4016  if (Constant *C = ConstantFoldInstruction(&Inst, DL, TLI)) {
4017  LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << Inst
4018  << '\n');
4019  Inst.replaceAllUsesWith(C);
4020  ++NumConstProp;
4021  if (isInstructionTriviallyDead(&Inst, TLI))
4022  Inst.eraseFromParent();
4023  MadeIRChange = true;
4024  continue;
4025  }
4026 
4027  // See if we can constant fold its operands.
4028  for (Use &U : Inst.operands()) {
4029  if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))
4030  continue;
4031 
4032  auto *C = cast<Constant>(U);
4033  Constant *&FoldRes = FoldedConstants[C];
4034  if (!FoldRes)
4035  FoldRes = ConstantFoldConstant(C, DL, TLI);
4036 
4037  if (FoldRes != C) {
4038  LLVM_DEBUG(dbgs() << "IC: ConstFold operand of: " << Inst
4039  << "\n Old = " << *C
4040  << "\n New = " << *FoldRes << '\n');
4041  U = FoldRes;
4042  MadeIRChange = true;
4043  }
4044  }
4045 
4046  // Skip processing debug and pseudo intrinsics in InstCombine. Processing
4047  // these call instructions consumes non-trivial amount of time and
4048  // provides no value for the optimization.
4049  if (!Inst.isDebugOrPseudoInst()) {
4050  InstrsForInstCombineWorklist.push_back(&Inst);
4051  SeenAliasScopes.analyse(&Inst);
4052  }
4053  }
4054 
4055  // Recursively visit successors. If this is a branch or switch on a
4056  // constant, only visit the reachable successor.
4057  Instruction *TI = BB->getTerminator();
4058  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
4059  if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
4060  bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
4061  BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
4062  Worklist.push_back(ReachableBB);
4063  continue;
4064  }
4065  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
4066  if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
4067  Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor());
4068  continue;
4069  }
4070  }
4071 
4072  append_range(Worklist, successors(TI));
4073  } while (!Worklist.empty());
4074 
4075  // Remove instructions inside unreachable blocks. This prevents the
4076  // instcombine code from having to deal with some bad special cases, and
4077  // reduces use counts of instructions.
4078  for (BasicBlock &BB : F) {
4079  if (Visited.count(&BB))
4080  continue;
4081 
4082  unsigned NumDeadInstInBB;
4083  unsigned NumDeadDbgInstInBB;
4084  std::tie(NumDeadInstInBB, NumDeadDbgInstInBB) =
4086 
4087  MadeIRChange |= NumDeadInstInBB + NumDeadDbgInstInBB > 0;
4088  NumDeadInst += NumDeadInstInBB;
4089  }
4090 
4091  // Once we've found all of the instructions to add to instcombine's worklist,
4092  // add them in reverse order. This way instcombine will visit from the top
4093  // of the function down. This jives well with the way that it adds all uses
4094  // of instructions to the worklist after doing a transformation, thus avoiding
4095  // some N^2 behavior in pathological cases.
4096  ICWorklist.reserve(InstrsForInstCombineWorklist.size());
4097  for (Instruction *Inst : reverse(InstrsForInstCombineWorklist)) {
4098  // DCE instruction if trivially dead. As we iterate in reverse program
4099  // order here, we will clean up whole chains of dead instructions.
4100  if (isInstructionTriviallyDead(Inst, TLI) ||
4101  SeenAliasScopes.isNoAliasScopeDeclDead(Inst)) {
4102  ++NumDeadInst;
4103  LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
4104  salvageDebugInfo(*Inst);
4105  Inst->eraseFromParent();
4106  MadeIRChange = true;
4107  continue;
4108  }
4109 
4110  ICWorklist.push(Inst);
4111  }
4112 
4113  return MadeIRChange;
4114 }
4115 
4117  Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA,
4120  ProfileSummaryInfo *PSI, unsigned MaxIterations, LoopInfo *LI) {
4121  auto &DL = F.getParent()->getDataLayout();
4122  MaxIterations = std::min(MaxIterations, LimitMaxIterations.getValue());
4123 
4124  /// Builder - This is an IRBuilder that automatically inserts new
4125  /// instructions into the worklist when they are created.
4127  F.getContext(), TargetFolder(DL),
4128  IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {
4129  Worklist.add(I);
4130  if (auto *Assume = dyn_cast<AssumeInst>(I))
4131  AC.registerAssumption(Assume);
4132  }));
4133 
4134  // Lower dbg.declare intrinsics otherwise their value may be clobbered
4135  // by instcombiner.
4136  bool MadeIRChange = false;
4138  MadeIRChange = LowerDbgDeclare(F);
4139 
4140  // Iterate while there is work to do.
4141  unsigned Iteration = 0;
4142  while (true) {
4143  ++NumWorklistIterations;
4144  ++Iteration;
4145 
4146  if (Iteration > InfiniteLoopDetectionThreshold) {
4148  "Instruction Combining seems stuck in an infinite loop after " +
4149  Twine(InfiniteLoopDetectionThreshold) + " iterations.");
4150  }
4151 
4152  if (Iteration > MaxIterations) {
4153  LLVM_DEBUG(dbgs() << "\n\n[IC] Iteration limit #" << MaxIterations
4154  << " on " << F.getName()
4155  << " reached; stopping before reaching a fixpoint\n");
4156  break;
4157  }
4158 
4159  LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
4160  << F.getName() << "\n");
4161 
4162  MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
4163 
4164  InstCombinerImpl IC(Worklist, Builder, F.hasMinSize(), AA, AC, TLI, TTI, DT,
4165  ORE, BFI, PSI, DL, LI);
4167 
4168  if (!IC.run())
4169  break;
4170 
4171  MadeIRChange = true;
4172  }
4173 
4174  return MadeIRChange;
4175 }
4176 
4178 
4179 InstCombinePass::InstCombinePass(unsigned MaxIterations)
4180  : MaxIterations(MaxIterations) {}
4181 
4184  auto &AC = AM.getResult<AssumptionAnalysis>(F);
4185  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
4186  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
4188  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
4189 
4190  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
4191 
4192  auto *AA = &AM.getResult<AAManager>(F);
4193  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
4194  ProfileSummaryInfo *PSI =
4195  MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
4196  auto *BFI = (PSI && PSI->hasProfileSummary()) ?
4197  &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
4198 
4199  if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, TTI, DT, ORE,
4200  BFI, PSI, MaxIterations, LI))
4201  // No changes, all analyses are preserved.
4202  return PreservedAnalyses::all();
4203 
4204  // Mark all the analyses that instcombine updates as preserved.
4205  PreservedAnalyses PA;
4206  PA.preserveSet<CFGAnalyses>();
4207  return PA;
4208 }
4209 
4211  AU.setPreservesCFG();
4224 }
4225 
4227  if (skipFunction(F))
4228  return false;
4229 
4230  // Required analyses.
4231  auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
4232  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
4233  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
4234  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
4235  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
4236  auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
4237 
4238  // Optional analyses.
4239  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
4240  auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
4241  ProfileSummaryInfo *PSI =
4242  &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
4244  (PSI && PSI->hasProfileSummary()) ?
4245  &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
4246  nullptr;
4247 
4248  return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, TTI, DT, ORE,
4249  BFI, PSI, MaxIterations, LI);
4250 }
4251 
4253 
4255  : FunctionPass(ID), MaxIterations(InstCombineDefaultMaxIterations) {
4257 }
4258 
4260  : FunctionPass(ID), MaxIterations(MaxIterations) {
4262 }
4263 
4265  "Combine redundant instructions", false, false)
4277 
4278 // Initialization Routines
4281 }
4282 
4285 }
4286 
4288  return new InstructionCombiningPass();
4289 }
4290 
4292  return new InstructionCombiningPass(MaxIterations);
4293 }
4294 
4297 }
llvm::EHPersonality::MSVC_CXX
@ MSVC_CXX
llvm::NoAliasScopeDeclInst
Definition: IntrinsicInst.h:1227
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:2445
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1061
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::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:2331
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:1798
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:103
llvm::APInt::sadd_ov
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1918
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:2924
llvm::TargetTransformInfo::instCombineIntrinsic
Optional< Instruction * > instCombineIntrinsic(InstCombiner &IC, IntrinsicInst &II) const
Targets can implement their own combinations for target-specific intrinsics.
Definition: TargetTransformInfo.cpp:298
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:3785
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:3167
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:2978
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:2959
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:1379
Metadata.h
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
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:4589
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:4210
llvm::InstCombinerImpl::run
bool run()
Run the combiner over the entire worklist until it is empty.
Definition: InstructionCombining.cpp:3762
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:779
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:673
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:1075
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:625
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:5192
llvm::InstCombinerImpl::visitExtractValueInst
Instruction * visitExtractValueInst(ExtractValueInst &EV)
Definition: InstructionCombining.cpp:3045
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:5241
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:2877
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:734
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:2522
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:3038
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:687
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:1237
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::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:4254
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:1403
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:2657
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:2423
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:6053
llvm::MemIntrinsic
This is the common base class for memset/memcpy/memmove.
Definition: IntrinsicInst.h:874
llvm::Optional
Definition: APInt.h:33
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:2873
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:4283
llvm::ArrayType
Class to represent array types.
Definition: DerivedTypes.h:357
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:406
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
llvm::InstCombinePass::InstCombinePass
InstCombinePass()
Definition: InstructionCombining.cpp:4177
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:101
llvm::BranchInst::swapSuccessors
void swapSuccessors()
Swap the successors of this branch instruction.
Definition: Instructions.cpp:1295
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:4279
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:1113
llvm::InstCombinerImpl::visitUnreachableInst
Instruction * visitUnreachableInst(UnreachableInst &I)
Definition: InstructionCombining.cpp:2903
llvm::UndefMaskElem
constexpr int UndefMaskElem
Definition: Instructions.h:1997
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:2676
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:2838
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:1335
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:319
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:4116
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
AliasScopeTracker
Definition: InstructionCombining.cpp:3942
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:381
llvm::SelectInst::Create
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
Definition: Instructions.h:1769
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:3657
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:5232
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:369
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:2721
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:375
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:2949
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
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:3603
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
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:216
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:1474
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:2930
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:627
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:2077
llvm::IntegerType
Class to represent integer types.
Definition: DerivedTypes.h:40
llvm::Instruction::CastOps
CastOps
Definition: Instruction.h:799
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:409
llvm::Constant::getAllOnesValue
static Constant * getAllOnesValue(Type *Ty)
Definition: Constants.cpp:405
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:2422
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:287
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:310
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:1771
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:900
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:3537
LLVMAddInstructionCombiningPass
void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM)
See llvm::createInstructionCombiningPass function.
Definition: InstructionCombining.cpp:4295
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:416
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:4455
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:2717
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::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
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:5044
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::BranchInst::getCondition
Value * getCondition() const
Definition: Instructions.h:3141
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3741
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:1107
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:389
llvm::IRBuilderBase::FastMathFlagGuard
Definition: IRBuilder.h:389
llvm::Type::getArrayElementType
Type * getArrayElementType() const
Definition: Type.h:375
Combine
Hexagon Vector Combine
Definition: HexagonVectorCombine.cpp:1525
VectorUtils.h
llvm::ConstantExpr::getTrunc
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2070
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:2373
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:2556
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:2787
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:241
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:2398
llvm::StructLayout
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:604
uint64_t
ProfileSummaryInfo.h
llvm::ConstantRange::getSignedMin
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
Definition: ConstantRange.cpp:387
llvm::TargetTransformInfoWrapperPass
Wrapper pass for TargetTransformInfo.
Definition: TargetTransformInfo.h:2387
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:1880
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:5315
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2775
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:3947
isAllocSiteRemovable
static bool isAllocSiteRemovable(Instruction *AI, SmallVectorImpl< WeakTrackingVH > &Users, const TargetLibraryInfo *TLI)
Definition: InstructionCombining.cpp:2570
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:2242
llvm::ExtractValueInst::idx_begin
idx_iterator idx_begin() const
Definition: Instructions.h:2421
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:1348
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:2741
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:3659
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:632
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:2934
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:384
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:1963
llvm::generic_gep_type_iterator::getIndexedType
Type * getIndexedType() const
Definition: GetElementPtrTypeIterator.h:72
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::KnownBits::countMinLeadingZeros
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:236
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
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:602
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:3192
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:901
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:2995
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:650
llvm::BranchInst::isUnconditional
bool isUnconditional() const
Definition: Instructions.h:3138
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:75
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:1931
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
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:213
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:2774
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:421
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:4555
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
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::X86AS::SS
@ SS
Definition: X86.h:189
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
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: IRBuilder.h:367
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::LandingPadInst::isFilter
bool isFilter(unsigned Idx) const
Return 'true' if the clause and index Idx is a filter clause.
Definition: Instructions.h:2944
llvm::TargetTransformInfo::simplifyDemandedUseBitsIntrinsic
Optional< Value * > simplifyDemandedUseBitsIntrinsic(InstCombiner &IC, IntrinsicInst &II, APInt DemandedMask, KnownBits &Known, bool &KnownBitsComputed) const
Can be used to implement target-specific instruction combining.
Definition: TargetTransformInfo.cpp:303
llvm::Function::isTargetIntrinsic
static bool isTargetIntrinsic(Intrinsic::ID IID)
isTargetIntrinsic - Returns true if IID is an intrinsic specific to a certain target.
Definition: Function.cpp:741
llvm::ConstantVector::get
static Constant * get(ArrayRef< Constant * > V)
Definition: Constants.cpp:1369
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:430
llvm::WithOverflowInst
Represents an op.with.overflow intrinsic.
Definition: IntrinsicInst.h:589