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