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