LLVM  9.0.0svn
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"
63 #include "llvm/IR/BasicBlock.h"
64 #include "llvm/IR/CFG.h"
65 #include "llvm/IR/Constant.h"
66 #include "llvm/IR/Constants.h"
67 #include "llvm/IR/DIBuilder.h"
68 #include "llvm/IR/DataLayout.h"
69 #include "llvm/IR/DerivedTypes.h"
70 #include "llvm/IR/Dominators.h"
71 #include "llvm/IR/Function.h"
73 #include "llvm/IR/IRBuilder.h"
74 #include "llvm/IR/InstrTypes.h"
75 #include "llvm/IR/Instruction.h"
76 #include "llvm/IR/Instructions.h"
77 #include "llvm/IR/IntrinsicInst.h"
78 #include "llvm/IR/Intrinsics.h"
80 #include "llvm/IR/Metadata.h"
81 #include "llvm/IR/Operator.h"
82 #include "llvm/IR/PassManager.h"
83 #include "llvm/IR/PatternMatch.h"
84 #include "llvm/IR/Type.h"
85 #include "llvm/IR/Use.h"
86 #include "llvm/IR/User.h"
87 #include "llvm/IR/Value.h"
88 #include "llvm/IR/ValueHandle.h"
89 #include "llvm/Pass.h"
91 #include "llvm/Support/Casting.h"
93 #include "llvm/Support/Compiler.h"
94 #include "llvm/Support/Debug.h"
97 #include "llvm/Support/KnownBits.h"
102 #include <algorithm>
103 #include <cassert>
104 #include <cstdint>
105 #include <memory>
106 #include <string>
107 #include <utility>
108 
109 using namespace llvm;
110 using namespace llvm::PatternMatch;
111 
112 #define DEBUG_TYPE "instcombine"
113 
114 STATISTIC(NumCombined , "Number of insts combined");
115 STATISTIC(NumConstProp, "Number of constant folds");
116 STATISTIC(NumDeadInst , "Number of dead inst eliminated");
117 STATISTIC(NumSunkInst , "Number of instructions sunk");
118 STATISTIC(NumExpand, "Number of expansions");
119 STATISTIC(NumFactor , "Number of factorizations");
120 STATISTIC(NumReassoc , "Number of reassociations");
121 DEBUG_COUNTER(VisitCounter, "instcombine-visit",
122  "Controls which instructions are visited");
123 
124 static cl::opt<bool>
125 EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"),
126  cl::init(true));
127 
128 static cl::opt<bool>
129 EnableExpensiveCombines("expensive-combines",
130  cl::desc("Enable expensive instruction combines"));
131 
132 static cl::opt<unsigned>
133 MaxArraySize("instcombine-maxarray-size", cl::init(1024),
134  cl::desc("Maximum array size considered when doing a combine"));
135 
136 // FIXME: Remove this flag when it is no longer necessary to convert
137 // llvm.dbg.declare to avoid inaccurate debug info. Setting this to false
138 // increases variable availability at the cost of accuracy. Variables that
139 // cannot be promoted by mem2reg or SROA will be described as living in memory
140 // for their entire lifetime. However, passes like DSE and instcombine can
141 // delete stores to the alloca, leading to misleading and inaccurate debug
142 // information. This flag can be removed when those passes are fixed.
143 static cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare",
144  cl::Hidden, cl::init(true));
145 
146 Value *InstCombiner::EmitGEPOffset(User *GEP) {
147  return llvm::EmitGEPOffset(&Builder, DL, GEP);
148 }
149 
150 /// Return true if it is desirable to convert an integer computation from a
151 /// given bit width to a new bit width.
152 /// We don't want to convert from a legal to an illegal type or from a smaller
153 /// to a larger illegal type. A width of '1' is always treated as a legal type
154 /// because i1 is a fundamental type in IR, and there are many specialized
155 /// optimizations for i1 types. Widths of 8, 16 or 32 are equally treated as
156 /// legal to convert to, in order to open up more combining opportunities.
157 /// NOTE: this treats i8, i16 and i32 specially, due to them being so common
158 /// from frontend languages.
159 bool InstCombiner::shouldChangeType(unsigned FromWidth,
160  unsigned ToWidth) const {
161  bool FromLegal = FromWidth == 1 || DL.isLegalInteger(FromWidth);
162  bool ToLegal = ToWidth == 1 || DL.isLegalInteger(ToWidth);
163 
164  // Convert to widths of 8, 16 or 32 even if they are not legal types. Only
165  // shrink types, to prevent infinite loops.
166  if (ToWidth < FromWidth && (ToWidth == 8 || ToWidth == 16 || ToWidth == 32))
167  return true;
168 
169  // If this is a legal integer from type, and the result would be an illegal
170  // type, don't do the transformation.
171  if (FromLegal && !ToLegal)
172  return false;
173 
174  // Otherwise, if both are illegal, do not increase the size of the result. We
175  // do allow things like i160 -> i64, but not i64 -> i160.
176  if (!FromLegal && !ToLegal && ToWidth > FromWidth)
177  return false;
178 
179  return true;
180 }
181 
182 /// Return true if it is desirable to convert a computation from 'From' to 'To'.
183 /// We don't want to convert from a legal to an illegal type or from a smaller
184 /// to a larger illegal type. i1 is always treated as a legal type because it is
185 /// a fundamental type in IR, and there are many specialized optimizations for
186 /// i1 types.
187 bool InstCombiner::shouldChangeType(Type *From, Type *To) const {
188  // TODO: This could be extended to allow vectors. Datalayout changes might be
189  // needed to properly support that.
190  if (!From->isIntegerTy() || !To->isIntegerTy())
191  return false;
192 
193  unsigned FromWidth = From->getPrimitiveSizeInBits();
194  unsigned ToWidth = To->getPrimitiveSizeInBits();
195  return shouldChangeType(FromWidth, ToWidth);
196 }
197 
198 // Return true, if No Signed Wrap should be maintained for I.
199 // The No Signed Wrap flag can be kept if the operation "B (I.getOpcode) C",
200 // where both B and C should be ConstantInts, results in a constant that does
201 // not overflow. This function only handles the Add and Sub opcodes. For
202 // all other opcodes, the function conservatively returns false.
205  if (!OBO || !OBO->hasNoSignedWrap())
206  return false;
207 
208  // We reason about Add and Sub Only.
209  Instruction::BinaryOps Opcode = I.getOpcode();
210  if (Opcode != Instruction::Add && Opcode != Instruction::Sub)
211  return false;
212 
213  const APInt *BVal, *CVal;
214  if (!match(B, m_APInt(BVal)) || !match(C, m_APInt(CVal)))
215  return false;
216 
217  bool Overflow = false;
218  if (Opcode == Instruction::Add)
219  (void)BVal->sadd_ov(*CVal, Overflow);
220  else
221  (void)BVal->ssub_ov(*CVal, Overflow);
222 
223  return !Overflow;
224 }
225 
228  return OBO && OBO->hasNoUnsignedWrap();
229 }
230 
231 /// Conservatively clears subclassOptionalData after a reassociation or
232 /// commutation. We preserve fast-math flags when applicable as they can be
233 /// preserved.
236  if (!FPMO) {
238  return;
239  }
240 
243  I.setFastMathFlags(FMF);
244 }
245 
246 /// Combine constant operands of associative operations either before or after a
247 /// cast to eliminate one of the associative operations:
248 /// (op (cast (op X, C2)), C1) --> (cast (op X, op (C1, C2)))
249 /// (op (cast (op X, C2)), C1) --> (op (cast X), op (C1, C2))
251  auto *Cast = dyn_cast<CastInst>(BinOp1->getOperand(0));
252  if (!Cast || !Cast->hasOneUse())
253  return false;
254 
255  // TODO: Enhance logic for other casts and remove this check.
256  auto CastOpcode = Cast->getOpcode();
257  if (CastOpcode != Instruction::ZExt)
258  return false;
259 
260  // TODO: Enhance logic for other BinOps and remove this check.
261  if (!BinOp1->isBitwiseLogicOp())
262  return false;
263 
264  auto AssocOpcode = BinOp1->getOpcode();
265  auto *BinOp2 = dyn_cast<BinaryOperator>(Cast->getOperand(0));
266  if (!BinOp2 || !BinOp2->hasOneUse() || BinOp2->getOpcode() != AssocOpcode)
267  return false;
268 
269  Constant *C1, *C2;
270  if (!match(BinOp1->getOperand(1), m_Constant(C1)) ||
271  !match(BinOp2->getOperand(1), m_Constant(C2)))
272  return false;
273 
274  // TODO: This assumes a zext cast.
275  // Eg, if it was a trunc, we'd cast C1 to the source type because casting C2
276  // to the destination type might lose bits.
277 
278  // Fold the constants together in the destination type:
279  // (op (cast (op X, C2)), C1) --> (op (cast X), FoldedC)
280  Type *DestTy = C1->getType();
281  Constant *CastC2 = ConstantExpr::getCast(CastOpcode, C2, DestTy);
282  Constant *FoldedC = ConstantExpr::get(AssocOpcode, C1, CastC2);
283  Cast->setOperand(0, BinOp2->getOperand(0));
284  BinOp1->setOperand(1, FoldedC);
285  return true;
286 }
287 
288 /// This performs a few simplifications for operators that are associative or
289 /// commutative:
290 ///
291 /// Commutative operators:
292 ///
293 /// 1. Order operands such that they are listed from right (least complex) to
294 /// left (most complex). This puts constants before unary operators before
295 /// binary operators.
296 ///
297 /// Associative operators:
298 ///
299 /// 2. Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.
300 /// 3. Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.
301 ///
302 /// Associative and commutative operators:
303 ///
304 /// 4. Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies.
305 /// 5. Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.
306 /// 6. Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"
307 /// if C1 and C2 are constants.
308 bool InstCombiner::SimplifyAssociativeOrCommutative(BinaryOperator &I) {
309  Instruction::BinaryOps Opcode = I.getOpcode();
310  bool Changed = false;
311 
312  do {
313  // Order operands such that they are listed from right (least complex) to
314  // left (most complex). This puts constants before unary operators before
315  // binary operators.
316  if (I.isCommutative() && getComplexity(I.getOperand(0)) <
318  Changed = !I.swapOperands();
319 
322 
323  if (I.isAssociative()) {
324  // Transform: "(A op B) op C" ==> "A op (B op C)" if "B op C" simplifies.
325  if (Op0 && Op0->getOpcode() == Opcode) {
326  Value *A = Op0->getOperand(0);
327  Value *B = Op0->getOperand(1);
328  Value *C = I.getOperand(1);
329 
330  // Does "B op C" simplify?
331  if (Value *V = SimplifyBinOp(Opcode, B, C, SQ.getWithInstruction(&I))) {
332  // It simplifies to V. Form "A op V".
333  I.setOperand(0, A);
334  I.setOperand(1, V);
335  // Conservatively clear the optional flags, since they may not be
336  // preserved by the reassociation.
337  bool IsNUW = hasNoUnsignedWrap(I) && hasNoUnsignedWrap(*Op0);
338  bool IsNSW = MaintainNoSignedWrap(I, B, C);
339 
341 
342  if (IsNUW)
343  I.setHasNoUnsignedWrap(true);
344 
345  if (IsNSW &&
346  (!Op0 || (isa<BinaryOperator>(Op0) && Op0->hasNoSignedWrap()))) {
347  // Note: this is only valid because SimplifyBinOp doesn't look at
348  // the operands to Op0.
349  I.setHasNoSignedWrap(true);
350  }
351 
352  Changed = true;
353  ++NumReassoc;
354  continue;
355  }
356  }
357 
358  // Transform: "A op (B op C)" ==> "(A op B) op C" if "A op B" simplifies.
359  if (Op1 && Op1->getOpcode() == Opcode) {
360  Value *A = I.getOperand(0);
361  Value *B = Op1->getOperand(0);
362  Value *C = Op1->getOperand(1);
363 
364  // Does "A op B" simplify?
365  if (Value *V = SimplifyBinOp(Opcode, A, B, SQ.getWithInstruction(&I))) {
366  // It simplifies to V. Form "V op C".
367  I.setOperand(0, V);
368  I.setOperand(1, C);
369  // Conservatively clear the optional flags, since they may not be
370  // preserved by the reassociation.
372  Changed = true;
373  ++NumReassoc;
374  continue;
375  }
376  }
377  }
378 
379  if (I.isAssociative() && I.isCommutative()) {
380  if (simplifyAssocCastAssoc(&I)) {
381  Changed = true;
382  ++NumReassoc;
383  continue;
384  }
385 
386  // Transform: "(A op B) op C" ==> "(C op A) op B" if "C op A" simplifies.
387  if (Op0 && Op0->getOpcode() == Opcode) {
388  Value *A = Op0->getOperand(0);
389  Value *B = Op0->getOperand(1);
390  Value *C = I.getOperand(1);
391 
392  // Does "C op A" simplify?
393  if (Value *V = SimplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) {
394  // It simplifies to V. Form "V op B".
395  I.setOperand(0, V);
396  I.setOperand(1, B);
397  // Conservatively clear the optional flags, since they may not be
398  // preserved by the reassociation.
400  Changed = true;
401  ++NumReassoc;
402  continue;
403  }
404  }
405 
406  // Transform: "A op (B op C)" ==> "B op (C op A)" if "C op A" simplifies.
407  if (Op1 && Op1->getOpcode() == Opcode) {
408  Value *A = I.getOperand(0);
409  Value *B = Op1->getOperand(0);
410  Value *C = Op1->getOperand(1);
411 
412  // Does "C op A" simplify?
413  if (Value *V = SimplifyBinOp(Opcode, C, A, SQ.getWithInstruction(&I))) {
414  // It simplifies to V. Form "B op V".
415  I.setOperand(0, B);
416  I.setOperand(1, V);
417  // Conservatively clear the optional flags, since they may not be
418  // preserved by the reassociation.
420  Changed = true;
421  ++NumReassoc;
422  continue;
423  }
424  }
425 
426  // Transform: "(A op C1) op (B op C2)" ==> "(A op B) op (C1 op C2)"
427  // if C1 and C2 are constants.
428  Value *A, *B;
429  Constant *C1, *C2;
430  if (Op0 && Op1 &&
431  Op0->getOpcode() == Opcode && Op1->getOpcode() == Opcode &&
432  match(Op0, m_OneUse(m_BinOp(m_Value(A), m_Constant(C1)))) &&
433  match(Op1, m_OneUse(m_BinOp(m_Value(B), m_Constant(C2))))) {
434  bool IsNUW = hasNoUnsignedWrap(I) &&
435  hasNoUnsignedWrap(*Op0) &&
436  hasNoUnsignedWrap(*Op1);
437  BinaryOperator *NewBO = (IsNUW && Opcode == Instruction::Add) ?
438  BinaryOperator::CreateNUW(Opcode, A, B) :
439  BinaryOperator::Create(Opcode, A, B);
440 
441  if (isa<FPMathOperator>(NewBO)) {
442  FastMathFlags Flags = I.getFastMathFlags();
443  Flags &= Op0->getFastMathFlags();
444  Flags &= Op1->getFastMathFlags();
445  NewBO->setFastMathFlags(Flags);
446  }
447  InsertNewInstWith(NewBO, I);
448  NewBO->takeName(Op1);
449  I.setOperand(0, NewBO);
450  I.setOperand(1, ConstantExpr::get(Opcode, C1, C2));
451  // Conservatively clear the optional flags, since they may not be
452  // preserved by the reassociation.
454  if (IsNUW)
455  I.setHasNoUnsignedWrap(true);
456 
457  Changed = true;
458  continue;
459  }
460  }
461 
462  // No further simplifications.
463  return Changed;
464  } while (true);
465 }
466 
467 /// Return whether "X LOp (Y ROp Z)" is always equal to
468 /// "(X LOp Y) ROp (X LOp Z)".
471  // X & (Y | Z) <--> (X & Y) | (X & Z)
472  // X & (Y ^ Z) <--> (X & Y) ^ (X & Z)
473  if (LOp == Instruction::And)
474  return ROp == Instruction::Or || ROp == Instruction::Xor;
475 
476  // X | (Y & Z) <--> (X | Y) & (X | Z)
477  if (LOp == Instruction::Or)
478  return ROp == Instruction::And;
479 
480  // X * (Y + Z) <--> (X * Y) + (X * Z)
481  // X * (Y - Z) <--> (X * Y) - (X * Z)
482  if (LOp == Instruction::Mul)
483  return ROp == Instruction::Add || ROp == Instruction::Sub;
484 
485  return false;
486 }
487 
488 /// Return whether "(X LOp Y) ROp Z" is always equal to
489 /// "(X ROp Z) LOp (Y ROp Z)".
493  return leftDistributesOverRight(ROp, LOp);
494 
495  // (X {&|^} Y) >> Z <--> (X >> Z) {&|^} (Y >> Z) for all shifts.
497 
498  // TODO: It would be nice to handle division, aka "(X + Y)/Z = X/Z + Y/Z",
499  // but this requires knowing that the addition does not overflow and other
500  // such subtleties.
501 }
502 
503 /// This function returns identity value for given opcode, which can be used to
504 /// factor patterns like (X * 2) + X ==> (X * 2) + (X * 1) ==> X * (2 + 1).
506  if (isa<Constant>(V))
507  return nullptr;
508 
509  return ConstantExpr::getBinOpIdentity(Opcode, V->getType());
510 }
511 
512 /// This function predicates factorization using distributive laws. By default,
513 /// it just returns the 'Op' inputs. But for special-cases like
514 /// 'add(shl(X, 5), ...)', this function will have TopOpcode == Instruction::Add
515 /// and Op = shl(X, 5). The 'shl' is treated as the more general 'mul X, 32' to
516 /// allow more factorization opportunities.
519  Value *&LHS, Value *&RHS) {
520  assert(Op && "Expected a binary operator");
521  LHS = Op->getOperand(0);
522  RHS = Op->getOperand(1);
523  if (TopOpcode == Instruction::Add || TopOpcode == Instruction::Sub) {
524  Constant *C;
525  if (match(Op, m_Shl(m_Value(), m_Constant(C)))) {
526  // X << C --> X * (1 << C)
527  RHS = ConstantExpr::getShl(ConstantInt::get(Op->getType(), 1), C);
528  return Instruction::Mul;
529  }
530  // TODO: We can add other conversions e.g. shr => div etc.
531  }
532  return Op->getOpcode();
533 }
534 
535 /// This tries to simplify binary operations by factorizing out common terms
536 /// (e. g. "(A*B)+(A*C)" -> "A*(B+C)").
537 Value *InstCombiner::tryFactorization(BinaryOperator &I,
538  Instruction::BinaryOps InnerOpcode,
539  Value *A, Value *B, Value *C, Value *D) {
540  assert(A && B && C && D && "All values must be provided");
541 
542  Value *V = nullptr;
543  Value *SimplifiedInst = nullptr;
544  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
545  Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
546 
547  // Does "X op' Y" always equal "Y op' X"?
548  bool InnerCommutative = Instruction::isCommutative(InnerOpcode);
549 
550  // Does "X op' (Y op Z)" always equal "(X op' Y) op (X op' Z)"?
551  if (leftDistributesOverRight(InnerOpcode, TopLevelOpcode))
552  // Does the instruction have the form "(A op' B) op (A op' D)" or, in the
553  // commutative case, "(A op' B) op (C op' A)"?
554  if (A == C || (InnerCommutative && A == D)) {
555  if (A != C)
556  std::swap(C, D);
557  // Consider forming "A op' (B op D)".
558  // If "B op D" simplifies then it can be formed with no cost.
559  V = SimplifyBinOp(TopLevelOpcode, B, D, SQ.getWithInstruction(&I));
560  // If "B op D" doesn't simplify then only go on if both of the existing
561  // operations "A op' B" and "C op' D" will be zapped as no longer used.
562  if (!V && LHS->hasOneUse() && RHS->hasOneUse())
563  V = Builder.CreateBinOp(TopLevelOpcode, B, D, RHS->getName());
564  if (V) {
565  SimplifiedInst = Builder.CreateBinOp(InnerOpcode, A, V);
566  }
567  }
568 
569  // Does "(X op Y) op' Z" always equal "(X op' Z) op (Y op' Z)"?
570  if (!SimplifiedInst && rightDistributesOverLeft(TopLevelOpcode, InnerOpcode))
571  // Does the instruction have the form "(A op' B) op (C op' B)" or, in the
572  // commutative case, "(A op' B) op (B op' D)"?
573  if (B == D || (InnerCommutative && B == C)) {
574  if (B != D)
575  std::swap(C, D);
576  // Consider forming "(A op C) op' B".
577  // If "A op C" simplifies then it can be formed with no cost.
578  V = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I));
579 
580  // If "A op C" doesn't simplify then only go on if both of the existing
581  // operations "A op' B" and "C op' D" will be zapped as no longer used.
582  if (!V && LHS->hasOneUse() && RHS->hasOneUse())
583  V = Builder.CreateBinOp(TopLevelOpcode, A, C, LHS->getName());
584  if (V) {
585  SimplifiedInst = Builder.CreateBinOp(InnerOpcode, V, B);
586  }
587  }
588 
589  if (SimplifiedInst) {
590  ++NumFactor;
591  SimplifiedInst->takeName(&I);
592 
593  // Check if we can add NSW/NUW flags to SimplifiedInst. If so, set them.
594  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SimplifiedInst)) {
595  if (isa<OverflowingBinaryOperator>(SimplifiedInst)) {
596  bool HasNSW = false;
597  bool HasNUW = false;
598  if (isa<OverflowingBinaryOperator>(&I)) {
599  HasNSW = I.hasNoSignedWrap();
600  HasNUW = I.hasNoUnsignedWrap();
601  }
602 
603  if (auto *LOBO = dyn_cast<OverflowingBinaryOperator>(LHS)) {
604  HasNSW &= LOBO->hasNoSignedWrap();
605  HasNUW &= LOBO->hasNoUnsignedWrap();
606  }
607 
608  if (auto *ROBO = dyn_cast<OverflowingBinaryOperator>(RHS)) {
609  HasNSW &= ROBO->hasNoSignedWrap();
610  HasNUW &= ROBO->hasNoUnsignedWrap();
611  }
612 
613  const APInt *CInt;
614  if (TopLevelOpcode == Instruction::Add &&
615  InnerOpcode == Instruction::Mul) {
616  // We can propagate 'nsw' if we know that
617  // %Y = mul nsw i16 %X, C
618  // %Z = add nsw i16 %Y, %X
619  // =>
620  // %Z = mul nsw i16 %X, C+1
621  //
622  // iff C+1 isn't INT_MIN
623  if (match(V, m_APInt(CInt))) {
624  if (!CInt->isMinSignedValue())
625  BO->setHasNoSignedWrap(HasNSW);
626  }
627 
628  // nuw can be propagated with any constant or nuw value.
629  BO->setHasNoUnsignedWrap(HasNUW);
630  }
631  }
632  }
633  }
634  return SimplifiedInst;
635 }
636 
637 /// This tries to simplify binary operations which some other binary operation
638 /// distributes over either by factorizing out common terms
639 /// (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this results in
640 /// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win).
641 /// Returns the simplified value, or null if it didn't simplify.
642 Value *InstCombiner::SimplifyUsingDistributiveLaws(BinaryOperator &I) {
643  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
646  Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
647 
648  {
649  // Factorization.
650  Value *A, *B, *C, *D;
651  Instruction::BinaryOps LHSOpcode, RHSOpcode;
652  if (Op0)
653  LHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op0, A, B);
654  if (Op1)
655  RHSOpcode = getBinOpsForFactorization(TopLevelOpcode, Op1, C, D);
656 
657  // The instruction has the form "(A op' B) op (C op' D)". Try to factorize
658  // a common term.
659  if (Op0 && Op1 && LHSOpcode == RHSOpcode)
660  if (Value *V = tryFactorization(I, LHSOpcode, A, B, C, D))
661  return V;
662 
663  // The instruction has the form "(A op' B) op (C)". Try to factorize common
664  // term.
665  if (Op0)
666  if (Value *Ident = getIdentityValue(LHSOpcode, RHS))
667  if (Value *V = tryFactorization(I, LHSOpcode, A, B, RHS, Ident))
668  return V;
669 
670  // The instruction has the form "(B) op (C op' D)". Try to factorize common
671  // term.
672  if (Op1)
673  if (Value *Ident = getIdentityValue(RHSOpcode, LHS))
674  if (Value *V = tryFactorization(I, RHSOpcode, LHS, Ident, C, D))
675  return V;
676  }
677 
678  // Expansion.
679  if (Op0 && rightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) {
680  // The instruction has the form "(A op' B) op C". See if expanding it out
681  // to "(A op C) op' (B op C)" results in simplifications.
682  Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
683  Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'
684 
685  Value *L = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I));
686  Value *R = SimplifyBinOp(TopLevelOpcode, B, C, SQ.getWithInstruction(&I));
687 
688  // Do "A op C" and "B op C" both simplify?
689  if (L && R) {
690  // They do! Return "L op' R".
691  ++NumExpand;
692  C = Builder.CreateBinOp(InnerOpcode, L, R);
693  C->takeName(&I);
694  return C;
695  }
696 
697  // Does "A op C" simplify to the identity value for the inner opcode?
698  if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {
699  // They do! Return "B op C".
700  ++NumExpand;
701  C = Builder.CreateBinOp(TopLevelOpcode, B, C);
702  C->takeName(&I);
703  return C;
704  }
705 
706  // Does "B op C" simplify to the identity value for the inner opcode?
707  if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
708  // They do! Return "A op C".
709  ++NumExpand;
710  C = Builder.CreateBinOp(TopLevelOpcode, A, C);
711  C->takeName(&I);
712  return C;
713  }
714  }
715 
716  if (Op1 && leftDistributesOverRight(TopLevelOpcode, Op1->getOpcode())) {
717  // The instruction has the form "A op (B op' C)". See if expanding it out
718  // to "(A op B) op' (A op C)" results in simplifications.
719  Value *A = LHS, *B = Op1->getOperand(0), *C = Op1->getOperand(1);
720  Instruction::BinaryOps InnerOpcode = Op1->getOpcode(); // op'
721 
722  Value *L = SimplifyBinOp(TopLevelOpcode, A, B, SQ.getWithInstruction(&I));
723  Value *R = SimplifyBinOp(TopLevelOpcode, A, C, SQ.getWithInstruction(&I));
724 
725  // Do "A op B" and "A op C" both simplify?
726  if (L && R) {
727  // They do! Return "L op' R".
728  ++NumExpand;
729  A = Builder.CreateBinOp(InnerOpcode, L, R);
730  A->takeName(&I);
731  return A;
732  }
733 
734  // Does "A op B" simplify to the identity value for the inner opcode?
735  if (L && L == ConstantExpr::getBinOpIdentity(InnerOpcode, L->getType())) {
736  // They do! Return "A op C".
737  ++NumExpand;
738  A = Builder.CreateBinOp(TopLevelOpcode, A, C);
739  A->takeName(&I);
740  return A;
741  }
742 
743  // Does "A op C" simplify to the identity value for the inner opcode?
744  if (R && R == ConstantExpr::getBinOpIdentity(InnerOpcode, R->getType())) {
745  // They do! Return "A op B".
746  ++NumExpand;
747  A = Builder.CreateBinOp(TopLevelOpcode, A, B);
748  A->takeName(&I);
749  return A;
750  }
751  }
752 
753  return SimplifySelectsFeedingBinaryOp(I, LHS, RHS);
754 }
755 
756 Value *InstCombiner::SimplifySelectsFeedingBinaryOp(BinaryOperator &I,
757  Value *LHS, Value *RHS) {
758  Instruction::BinaryOps Opcode = I.getOpcode();
759  // (op (select (a, b, c)), (select (a, d, e))) -> (select (a, (op b, d), (op
760  // c, e)))
761  Value *A, *B, *C, *D, *E;
762  Value *SI = nullptr;
763  if (match(LHS, m_Select(m_Value(A), m_Value(B), m_Value(C))) &&
764  match(RHS, m_Select(m_Specific(A), m_Value(D), m_Value(E)))) {
765  bool SelectsHaveOneUse = LHS->hasOneUse() && RHS->hasOneUse();
766  BuilderTy::FastMathFlagGuard Guard(Builder);
767  if (isa<FPMathOperator>(&I))
768  Builder.setFastMathFlags(I.getFastMathFlags());
769 
770  Value *V1 = SimplifyBinOp(Opcode, C, E, SQ.getWithInstruction(&I));
771  Value *V2 = SimplifyBinOp(Opcode, B, D, SQ.getWithInstruction(&I));
772  if (V1 && V2)
773  SI = Builder.CreateSelect(A, V2, V1);
774  else if (V2 && SelectsHaveOneUse)
775  SI = Builder.CreateSelect(A, V2, Builder.CreateBinOp(Opcode, C, E));
776  else if (V1 && SelectsHaveOneUse)
777  SI = Builder.CreateSelect(A, Builder.CreateBinOp(Opcode, B, D), V1);
778 
779  if (SI)
780  SI->takeName(&I);
781  }
782 
783  return SI;
784 }
785 
786 /// Given a 'sub' instruction, return the RHS of the instruction if the LHS is a
787 /// constant zero (which is the 'negate' form).
788 Value *InstCombiner::dyn_castNegVal(Value *V) const {
789  Value *NegV;
790  if (match(V, m_Neg(m_Value(NegV))))
791  return NegV;
792 
793  // Constants can be considered to be negated values if they can be folded.
794  if (ConstantInt *C = dyn_cast<ConstantInt>(V))
795  return ConstantExpr::getNeg(C);
796 
797  if (ConstantDataVector *C = dyn_cast<ConstantDataVector>(V))
798  if (C->getType()->getElementType()->isIntegerTy())
799  return ConstantExpr::getNeg(C);
800 
801  if (ConstantVector *CV = dyn_cast<ConstantVector>(V)) {
802  for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
803  Constant *Elt = CV->getAggregateElement(i);
804  if (!Elt)
805  return nullptr;
806 
807  if (isa<UndefValue>(Elt))
808  continue;
809 
810  if (!isa<ConstantInt>(Elt))
811  return nullptr;
812  }
813  return ConstantExpr::getNeg(CV);
814  }
815 
816  return nullptr;
817 }
818 
820  InstCombiner::BuilderTy &Builder) {
821  if (auto *Cast = dyn_cast<CastInst>(&I))
822  return Builder.CreateCast(Cast->getOpcode(), SO, I.getType());
823 
824  assert(I.isBinaryOp() && "Unexpected opcode for select folding");
825 
826  // Figure out if the constant is the left or the right argument.
827  bool ConstIsRHS = isa<Constant>(I.getOperand(1));
828  Constant *ConstOperand = cast<Constant>(I.getOperand(ConstIsRHS));
829 
830  if (auto *SOC = dyn_cast<Constant>(SO)) {
831  if (ConstIsRHS)
832  return ConstantExpr::get(I.getOpcode(), SOC, ConstOperand);
833  return ConstantExpr::get(I.getOpcode(), ConstOperand, SOC);
834  }
835 
836  Value *Op0 = SO, *Op1 = ConstOperand;
837  if (!ConstIsRHS)
838  std::swap(Op0, Op1);
839 
840  auto *BO = cast<BinaryOperator>(&I);
841  Value *RI = Builder.CreateBinOp(BO->getOpcode(), Op0, Op1,
842  SO->getName() + ".op");
843  auto *FPInst = dyn_cast<Instruction>(RI);
844  if (FPInst && isa<FPMathOperator>(FPInst))
845  FPInst->copyFastMathFlags(BO);
846  return RI;
847 }
848 
849 Instruction *InstCombiner::FoldOpIntoSelect(Instruction &Op, SelectInst *SI) {
850  // Don't modify shared select instructions.
851  if (!SI->hasOneUse())
852  return nullptr;
853 
854  Value *TV = SI->getTrueValue();
855  Value *FV = SI->getFalseValue();
856  if (!(isa<Constant>(TV) || isa<Constant>(FV)))
857  return nullptr;
858 
859  // Bool selects with constant operands can be folded to logical ops.
860  if (SI->getType()->isIntOrIntVectorTy(1))
861  return nullptr;
862 
863  // If it's a bitcast involving vectors, make sure it has the same number of
864  // elements on both sides.
865  if (auto *BC = dyn_cast<BitCastInst>(&Op)) {
866  VectorType *DestTy = dyn_cast<VectorType>(BC->getDestTy());
867  VectorType *SrcTy = dyn_cast<VectorType>(BC->getSrcTy());
868 
869  // Verify that either both or neither are vectors.
870  if ((SrcTy == nullptr) != (DestTy == nullptr))
871  return nullptr;
872 
873  // If vectors, verify that they have the same number of elements.
874  if (SrcTy && SrcTy->getNumElements() != DestTy->getNumElements())
875  return nullptr;
876  }
877 
878  // Test if a CmpInst instruction is used exclusively by a select as
879  // part of a minimum or maximum operation. If so, refrain from doing
880  // any other folding. This helps out other analyses which understand
881  // non-obfuscated minimum and maximum idioms, such as ScalarEvolution
882  // and CodeGen. And in this case, at least one of the comparison
883  // operands has at least one user besides the compare (the select),
884  // which would often largely negate the benefit of folding anyway.
885  if (auto *CI = dyn_cast<CmpInst>(SI->getCondition())) {
886  if (CI->hasOneUse()) {
887  Value *Op0 = CI->getOperand(0), *Op1 = CI->getOperand(1);
888  if ((SI->getOperand(1) == Op0 && SI->getOperand(2) == Op1) ||
889  (SI->getOperand(2) == Op0 && SI->getOperand(1) == Op1))
890  return nullptr;
891  }
892  }
893 
894  Value *NewTV = foldOperationIntoSelectOperand(Op, TV, Builder);
895  Value *NewFV = foldOperationIntoSelectOperand(Op, FV, Builder);
896  return SelectInst::Create(SI->getCondition(), NewTV, NewFV, "", nullptr, SI);
897 }
898 
900  InstCombiner::BuilderTy &Builder) {
901  bool ConstIsRHS = isa<Constant>(I->getOperand(1));
902  Constant *C = cast<Constant>(I->getOperand(ConstIsRHS));
903 
904  if (auto *InC = dyn_cast<Constant>(InV)) {
905  if (ConstIsRHS)
906  return ConstantExpr::get(I->getOpcode(), InC, C);
907  return ConstantExpr::get(I->getOpcode(), C, InC);
908  }
909 
910  Value *Op0 = InV, *Op1 = C;
911  if (!ConstIsRHS)
912  std::swap(Op0, Op1);
913 
914  Value *RI = Builder.CreateBinOp(I->getOpcode(), Op0, Op1, "phitmp");
915  auto *FPInst = dyn_cast<Instruction>(RI);
916  if (FPInst && isa<FPMathOperator>(FPInst))
917  FPInst->copyFastMathFlags(I);
918  return RI;
919 }
920 
921 Instruction *InstCombiner::foldOpIntoPhi(Instruction &I, PHINode *PN) {
922  unsigned NumPHIValues = PN->getNumIncomingValues();
923  if (NumPHIValues == 0)
924  return nullptr;
925 
926  // We normally only transform phis with a single use. However, if a PHI has
927  // multiple uses and they are all the same operation, we can fold *all* of the
928  // uses into the PHI.
929  if (!PN->hasOneUse()) {
930  // Walk the use list for the instruction, comparing them to I.
931  for (User *U : PN->users()) {
932  Instruction *UI = cast<Instruction>(U);
933  if (UI != &I && !I.isIdenticalTo(UI))
934  return nullptr;
935  }
936  // Otherwise, we can replace *all* users with the new PHI we form.
937  }
938 
939  // Check to see if all of the operands of the PHI are simple constants
940  // (constantint/constantfp/undef). If there is one non-constant value,
941  // remember the BB it is in. If there is more than one or if *it* is a PHI,
942  // bail out. We don't do arbitrary constant expressions here because moving
943  // their computation can be expensive without a cost model.
944  BasicBlock *NonConstBB = nullptr;
945  for (unsigned i = 0; i != NumPHIValues; ++i) {
946  Value *InVal = PN->getIncomingValue(i);
947  if (isa<Constant>(InVal) && !isa<ConstantExpr>(InVal))
948  continue;
949 
950  if (isa<PHINode>(InVal)) return nullptr; // Itself a phi.
951  if (NonConstBB) return nullptr; // More than one non-const value.
952 
953  NonConstBB = PN->getIncomingBlock(i);
954 
955  // If the InVal is an invoke at the end of the pred block, then we can't
956  // insert a computation after it without breaking the edge.
957  if (isa<InvokeInst>(InVal))
958  if (cast<Instruction>(InVal)->getParent() == NonConstBB)
959  return nullptr;
960 
961  // If the incoming non-constant value is in I's block, we will remove one
962  // instruction, but insert another equivalent one, leading to infinite
963  // instcombine.
964  if (isPotentiallyReachable(I.getParent(), NonConstBB, &DT, LI))
965  return nullptr;
966  }
967 
968  // If there is exactly one non-constant value, we can insert a copy of the
969  // operation in that block. However, if this is a critical edge, we would be
970  // inserting the computation on some other paths (e.g. inside a loop). Only
971  // do this if the pred block is unconditionally branching into the phi block.
972  if (NonConstBB != nullptr) {
973  BranchInst *BI = dyn_cast<BranchInst>(NonConstBB->getTerminator());
974  if (!BI || !BI->isUnconditional()) return nullptr;
975  }
976 
977  // Okay, we can do the transformation: create the new PHI node.
979  InsertNewInstBefore(NewPN, *PN);
980  NewPN->takeName(PN);
981 
982  // If we are going to have to insert a new computation, do so right before the
983  // predecessor's terminator.
984  if (NonConstBB)
985  Builder.SetInsertPoint(NonConstBB->getTerminator());
986 
987  // Next, add all of the operands to the PHI.
988  if (SelectInst *SI = dyn_cast<SelectInst>(&I)) {
989  // We only currently try to fold the condition of a select when it is a phi,
990  // not the true/false values.
991  Value *TrueV = SI->getTrueValue();
992  Value *FalseV = SI->getFalseValue();
993  BasicBlock *PhiTransBB = PN->getParent();
994  for (unsigned i = 0; i != NumPHIValues; ++i) {
995  BasicBlock *ThisBB = PN->getIncomingBlock(i);
996  Value *TrueVInPred = TrueV->DoPHITranslation(PhiTransBB, ThisBB);
997  Value *FalseVInPred = FalseV->DoPHITranslation(PhiTransBB, ThisBB);
998  Value *InV = nullptr;
999  // Beware of ConstantExpr: it may eventually evaluate to getNullValue,
1000  // even if currently isNullValue gives false.
1001  Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i));
1002  // For vector constants, we cannot use isNullValue to fold into
1003  // FalseVInPred versus TrueVInPred. When we have individual nonzero
1004  // elements in the vector, we will incorrectly fold InC to
1005  // `TrueVInPred`.
1006  if (InC && !isa<ConstantExpr>(InC) && isa<ConstantInt>(InC))
1007  InV = InC->isNullValue() ? FalseVInPred : TrueVInPred;
1008  else {
1009  // Generate the select in the same block as PN's current incoming block.
1010  // Note: ThisBB need not be the NonConstBB because vector constants
1011  // which are constants by definition are handled here.
1012  // FIXME: This can lead to an increase in IR generation because we might
1013  // generate selects for vector constant phi operand, that could not be
1014  // folded to TrueVInPred or FalseVInPred as done for ConstantInt. For
1015  // non-vector phis, this transformation was always profitable because
1016  // the select would be generated exactly once in the NonConstBB.
1017  Builder.SetInsertPoint(ThisBB->getTerminator());
1018  InV = Builder.CreateSelect(PN->getIncomingValue(i), TrueVInPred,
1019  FalseVInPred, "phitmp");
1020  }
1021  NewPN->addIncoming(InV, ThisBB);
1022  }
1023  } else if (CmpInst *CI = dyn_cast<CmpInst>(&I)) {
1024  Constant *C = cast<Constant>(I.getOperand(1));
1025  for (unsigned i = 0; i != NumPHIValues; ++i) {
1026  Value *InV = nullptr;
1027  if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))
1028  InV = ConstantExpr::getCompare(CI->getPredicate(), InC, C);
1029  else if (isa<ICmpInst>(CI))
1030  InV = Builder.CreateICmp(CI->getPredicate(), PN->getIncomingValue(i),
1031  C, "phitmp");
1032  else
1033  InV = Builder.CreateFCmp(CI->getPredicate(), PN->getIncomingValue(i),
1034  C, "phitmp");
1035  NewPN->addIncoming(InV, PN->getIncomingBlock(i));
1036  }
1037  } else if (auto *BO = dyn_cast<BinaryOperator>(&I)) {
1038  for (unsigned i = 0; i != NumPHIValues; ++i) {
1040  Builder);
1041  NewPN->addIncoming(InV, PN->getIncomingBlock(i));
1042  }
1043  } else {
1044  CastInst *CI = cast<CastInst>(&I);
1045  Type *RetTy = CI->getType();
1046  for (unsigned i = 0; i != NumPHIValues; ++i) {
1047  Value *InV;
1048  if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))
1049  InV = ConstantExpr::getCast(CI->getOpcode(), InC, RetTy);
1050  else
1051  InV = Builder.CreateCast(CI->getOpcode(), PN->getIncomingValue(i),
1052  I.getType(), "phitmp");
1053  NewPN->addIncoming(InV, PN->getIncomingBlock(i));
1054  }
1055  }
1056 
1057  for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) {
1058  Instruction *User = cast<Instruction>(*UI++);
1059  if (User == &I) continue;
1060  replaceInstUsesWith(*User, NewPN);
1061  eraseInstFromFunction(*User);
1062  }
1063  return replaceInstUsesWith(I, NewPN);
1064 }
1065 
1066 Instruction *InstCombiner::foldBinOpIntoSelectOrPhi(BinaryOperator &I) {
1067  if (!isa<Constant>(I.getOperand(1)))
1068  return nullptr;
1069 
1070  if (auto *Sel = dyn_cast<SelectInst>(I.getOperand(0))) {
1071  if (Instruction *NewSel = FoldOpIntoSelect(I, Sel))
1072  return NewSel;
1073  } else if (auto *PN = dyn_cast<PHINode>(I.getOperand(0))) {
1074  if (Instruction *NewPhi = foldOpIntoPhi(I, PN))
1075  return NewPhi;
1076  }
1077  return nullptr;
1078 }
1079 
1080 /// Given a pointer type and a constant offset, determine whether or not there
1081 /// is a sequence of GEP indices into the pointed type that will land us at the
1082 /// specified offset. If so, fill them into NewIndices and return the resultant
1083 /// element type, otherwise return null.
1084 Type *InstCombiner::FindElementAtOffset(PointerType *PtrTy, int64_t Offset,
1085  SmallVectorImpl<Value *> &NewIndices) {
1086  Type *Ty = PtrTy->getElementType();
1087  if (!Ty->isSized())
1088  return nullptr;
1089 
1090  // Start with the index over the outer type. Note that the type size
1091  // might be zero (even if the offset isn't zero) if the indexed type
1092  // is something like [0 x {int, int}]
1093  Type *IndexTy = DL.getIndexType(PtrTy);
1094  int64_t FirstIdx = 0;
1095  if (int64_t TySize = DL.getTypeAllocSize(Ty)) {
1096  FirstIdx = Offset/TySize;
1097  Offset -= FirstIdx*TySize;
1098 
1099  // Handle hosts where % returns negative instead of values [0..TySize).
1100  if (Offset < 0) {
1101  --FirstIdx;
1102  Offset += TySize;
1103  assert(Offset >= 0);
1104  }
1105  assert((uint64_t)Offset < (uint64_t)TySize && "Out of range offset");
1106  }
1107 
1108  NewIndices.push_back(ConstantInt::get(IndexTy, FirstIdx));
1109 
1110  // Index into the types. If we fail, set OrigBase to null.
1111  while (Offset) {
1112  // Indexing into tail padding between struct/array elements.
1113  if (uint64_t(Offset * 8) >= DL.getTypeSizeInBits(Ty))
1114  return nullptr;
1115 
1116  if (StructType *STy = dyn_cast<StructType>(Ty)) {
1117  const StructLayout *SL = DL.getStructLayout(STy);
1118  assert(Offset < (int64_t)SL->getSizeInBytes() &&
1119  "Offset must stay within the indexed type");
1120 
1121  unsigned Elt = SL->getElementContainingOffset(Offset);
1123  Elt));
1124 
1125  Offset -= SL->getElementOffset(Elt);
1126  Ty = STy->getElementType(Elt);
1127  } else if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) {
1128  uint64_t EltSize = DL.getTypeAllocSize(AT->getElementType());
1129  assert(EltSize && "Cannot index into a zero-sized array");
1130  NewIndices.push_back(ConstantInt::get(IndexTy,Offset/EltSize));
1131  Offset %= EltSize;
1132  Ty = AT->getElementType();
1133  } else {
1134  // Otherwise, we can't index into the middle of this atomic type, bail.
1135  return nullptr;
1136  }
1137  }
1138 
1139  return Ty;
1140 }
1141 
1143  // If this GEP has only 0 indices, it is the same pointer as
1144  // Src. If Src is not a trivial GEP too, don't combine
1145  // the indices.
1146  if (GEP.hasAllZeroIndices() && !Src.hasAllZeroIndices() &&
1147  !Src.hasOneUse())
1148  return false;
1149  return true;
1150 }
1151 
1152 /// Return a value X such that Val = X * Scale, or null if none.
1153 /// If the multiplication is known not to overflow, then NoSignedWrap is set.
1154 Value *InstCombiner::Descale(Value *Val, APInt Scale, bool &NoSignedWrap) {
1155  assert(isa<IntegerType>(Val->getType()) && "Can only descale integers!");
1156  assert(cast<IntegerType>(Val->getType())->getBitWidth() ==
1157  Scale.getBitWidth() && "Scale not compatible with value!");
1158 
1159  // If Val is zero or Scale is one then Val = Val * Scale.
1160  if (match(Val, m_Zero()) || Scale == 1) {
1161  NoSignedWrap = true;
1162  return Val;
1163  }
1164 
1165  // If Scale is zero then it does not divide Val.
1166  if (Scale.isMinValue())
1167  return nullptr;
1168 
1169  // Look through chains of multiplications, searching for a constant that is
1170  // divisible by Scale. For example, descaling X*(Y*(Z*4)) by a factor of 4
1171  // will find the constant factor 4 and produce X*(Y*Z). Descaling X*(Y*8) by
1172  // a factor of 4 will produce X*(Y*2). The principle of operation is to bore
1173  // down from Val:
1174  //
1175  // Val = M1 * X || Analysis starts here and works down
1176  // M1 = M2 * Y || Doesn't descend into terms with more
1177  // M2 = Z * 4 \/ than one use
1178  //
1179  // Then to modify a term at the bottom:
1180  //
1181  // Val = M1 * X
1182  // M1 = Z * Y || Replaced M2 with Z
1183  //
1184  // Then to work back up correcting nsw flags.
1185 
1186  // Op - the term we are currently analyzing. Starts at Val then drills down.
1187  // Replaced with its descaled value before exiting from the drill down loop.
1188  Value *Op = Val;
1189 
1190  // Parent - initially null, but after drilling down notes where Op came from.
1191  // In the example above, Parent is (Val, 0) when Op is M1, because M1 is the
1192  // 0'th operand of Val.
1193  std::pair<Instruction *, unsigned> Parent;
1194 
1195  // Set if the transform requires a descaling at deeper levels that doesn't
1196  // overflow.
1197  bool RequireNoSignedWrap = false;
1198 
1199  // Log base 2 of the scale. Negative if not a power of 2.
1200  int32_t logScale = Scale.exactLogBase2();
1201 
1202  for (;; Op = Parent.first->getOperand(Parent.second)) { // Drill down
1203  if (ConstantInt *CI = dyn_cast<ConstantInt>(Op)) {
1204  // If Op is a constant divisible by Scale then descale to the quotient.
1205  APInt Quotient(Scale), Remainder(Scale); // Init ensures right bitwidth.
1206  APInt::sdivrem(CI->getValue(), Scale, Quotient, Remainder);
1207  if (!Remainder.isMinValue())
1208  // Not divisible by Scale.
1209  return nullptr;
1210  // Replace with the quotient in the parent.
1211  Op = ConstantInt::get(CI->getType(), Quotient);
1212  NoSignedWrap = true;
1213  break;
1214  }
1215 
1216  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op)) {
1217  if (BO->getOpcode() == Instruction::Mul) {
1218  // Multiplication.
1219  NoSignedWrap = BO->hasNoSignedWrap();
1220  if (RequireNoSignedWrap && !NoSignedWrap)
1221  return nullptr;
1222 
1223  // There are three cases for multiplication: multiplication by exactly
1224  // the scale, multiplication by a constant different to the scale, and
1225  // multiplication by something else.
1226  Value *LHS = BO->getOperand(0);
1227  Value *RHS = BO->getOperand(1);
1228 
1229  if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS)) {
1230  // Multiplication by a constant.
1231  if (CI->getValue() == Scale) {
1232  // Multiplication by exactly the scale, replace the multiplication
1233  // by its left-hand side in the parent.
1234  Op = LHS;
1235  break;
1236  }
1237 
1238  // Otherwise drill down into the constant.
1239  if (!Op->hasOneUse())
1240  return nullptr;
1241 
1242  Parent = std::make_pair(BO, 1);
1243  continue;
1244  }
1245 
1246  // Multiplication by something else. Drill down into the left-hand side
1247  // since that's where the reassociate pass puts the good stuff.
1248  if (!Op->hasOneUse())
1249  return nullptr;
1250 
1251  Parent = std::make_pair(BO, 0);
1252  continue;
1253  }
1254 
1255  if (logScale > 0 && BO->getOpcode() == Instruction::Shl &&
1256  isa<ConstantInt>(BO->getOperand(1))) {
1257  // Multiplication by a power of 2.
1258  NoSignedWrap = BO->hasNoSignedWrap();
1259  if (RequireNoSignedWrap && !NoSignedWrap)
1260  return nullptr;
1261 
1262  Value *LHS = BO->getOperand(0);
1263  int32_t Amt = cast<ConstantInt>(BO->getOperand(1))->
1264  getLimitedValue(Scale.getBitWidth());
1265  // Op = LHS << Amt.
1266 
1267  if (Amt == logScale) {
1268  // Multiplication by exactly the scale, replace the multiplication
1269  // by its left-hand side in the parent.
1270  Op = LHS;
1271  break;
1272  }
1273  if (Amt < logScale || !Op->hasOneUse())
1274  return nullptr;
1275 
1276  // Multiplication by more than the scale. Reduce the multiplying amount
1277  // by the scale in the parent.
1278  Parent = std::make_pair(BO, 1);
1279  Op = ConstantInt::get(BO->getType(), Amt - logScale);
1280  break;
1281  }
1282  }
1283 
1284  if (!Op->hasOneUse())
1285  return nullptr;
1286 
1287  if (CastInst *Cast = dyn_cast<CastInst>(Op)) {
1288  if (Cast->getOpcode() == Instruction::SExt) {
1289  // Op is sign-extended from a smaller type, descale in the smaller type.
1290  unsigned SmallSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1291  APInt SmallScale = Scale.trunc(SmallSize);
1292  // Suppose Op = sext X, and we descale X as Y * SmallScale. We want to
1293  // descale Op as (sext Y) * Scale. In order to have
1294  // sext (Y * SmallScale) = (sext Y) * Scale
1295  // some conditions need to hold however: SmallScale must sign-extend to
1296  // Scale and the multiplication Y * SmallScale should not overflow.
1297  if (SmallScale.sext(Scale.getBitWidth()) != Scale)
1298  // SmallScale does not sign-extend to Scale.
1299  return nullptr;
1300  assert(SmallScale.exactLogBase2() == logScale);
1301  // Require that Y * SmallScale must not overflow.
1302  RequireNoSignedWrap = true;
1303 
1304  // Drill down through the cast.
1305  Parent = std::make_pair(Cast, 0);
1306  Scale = SmallScale;
1307  continue;
1308  }
1309 
1310  if (Cast->getOpcode() == Instruction::Trunc) {
1311  // Op is truncated from a larger type, descale in the larger type.
1312  // Suppose Op = trunc X, and we descale X as Y * sext Scale. Then
1313  // trunc (Y * sext Scale) = (trunc Y) * Scale
1314  // always holds. However (trunc Y) * Scale may overflow even if
1315  // trunc (Y * sext Scale) does not, so nsw flags need to be cleared
1316  // from this point up in the expression (see later).
1317  if (RequireNoSignedWrap)
1318  return nullptr;
1319 
1320  // Drill down through the cast.
1321  unsigned LargeSize = Cast->getSrcTy()->getPrimitiveSizeInBits();
1322  Parent = std::make_pair(Cast, 0);
1323  Scale = Scale.sext(LargeSize);
1324  if (logScale + 1 == (int32_t)Cast->getType()->getPrimitiveSizeInBits())
1325  logScale = -1;
1326  assert(Scale.exactLogBase2() == logScale);
1327  continue;
1328  }
1329  }
1330 
1331  // Unsupported expression, bail out.
1332  return nullptr;
1333  }
1334 
1335  // If Op is zero then Val = Op * Scale.
1336  if (match(Op, m_Zero())) {
1337  NoSignedWrap = true;
1338  return Op;
1339  }
1340 
1341  // We know that we can successfully descale, so from here on we can safely
1342  // modify the IR. Op holds the descaled version of the deepest term in the
1343  // expression. NoSignedWrap is 'true' if multiplying Op by Scale is known
1344  // not to overflow.
1345 
1346  if (!Parent.first)
1347  // The expression only had one term.
1348  return Op;
1349 
1350  // Rewrite the parent using the descaled version of its operand.
1351  assert(Parent.first->hasOneUse() && "Drilled down when more than one use!");
1352  assert(Op != Parent.first->getOperand(Parent.second) &&
1353  "Descaling was a no-op?");
1354  Parent.first->setOperand(Parent.second, Op);
1355  Worklist.Add(Parent.first);
1356 
1357  // Now work back up the expression correcting nsw flags. The logic is based
1358  // on the following observation: if X * Y is known not to overflow as a signed
1359  // multiplication, and Y is replaced by a value Z with smaller absolute value,
1360  // then X * Z will not overflow as a signed multiplication either. As we work
1361  // our way up, having NoSignedWrap 'true' means that the descaled value at the
1362  // current level has strictly smaller absolute value than the original.
1363  Instruction *Ancestor = Parent.first;
1364  do {
1365  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Ancestor)) {
1366  // If the multiplication wasn't nsw then we can't say anything about the
1367  // value of the descaled multiplication, and we have to clear nsw flags
1368  // from this point on up.
1369  bool OpNoSignedWrap = BO->hasNoSignedWrap();
1370  NoSignedWrap &= OpNoSignedWrap;
1371  if (NoSignedWrap != OpNoSignedWrap) {
1372  BO->setHasNoSignedWrap(NoSignedWrap);
1373  Worklist.Add(Ancestor);
1374  }
1375  } else if (Ancestor->getOpcode() == Instruction::Trunc) {
1376  // The fact that the descaled input to the trunc has smaller absolute
1377  // value than the original input doesn't tell us anything useful about
1378  // the absolute values of the truncations.
1379  NoSignedWrap = false;
1380  }
1381  assert((Ancestor->getOpcode() != Instruction::SExt || NoSignedWrap) &&
1382  "Failed to keep proper track of nsw flags while drilling down?");
1383 
1384  if (Ancestor == Val)
1385  // Got to the top, all done!
1386  return Val;
1387 
1388  // Move up one level in the expression.
1389  assert(Ancestor->hasOneUse() && "Drilled down when more than one use!");
1390  Ancestor = Ancestor->user_back();
1391  } while (true);
1392 }
1393 
1394 Instruction *InstCombiner::foldVectorBinop(BinaryOperator &Inst) {
1395  if (!Inst.getType()->isVectorTy()) return nullptr;
1396 
1397  BinaryOperator::BinaryOps Opcode = Inst.getOpcode();
1398  unsigned NumElts = cast<VectorType>(Inst.getType())->getNumElements();
1399  Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1);
1400  assert(cast<VectorType>(LHS->getType())->getNumElements() == NumElts);
1401  assert(cast<VectorType>(RHS->getType())->getNumElements() == NumElts);
1402 
1403  // If both operands of the binop are vector concatenations, then perform the
1404  // narrow binop on each pair of the source operands followed by concatenation
1405  // of the results.
1406  Value *L0, *L1, *R0, *R1;
1407  Constant *Mask;
1408  if (match(LHS, m_ShuffleVector(m_Value(L0), m_Value(L1), m_Constant(Mask))) &&
1409  match(RHS, m_ShuffleVector(m_Value(R0), m_Value(R1), m_Specific(Mask))) &&
1410  LHS->hasOneUse() && RHS->hasOneUse() &&
1411  cast<ShuffleVectorInst>(LHS)->isConcat() &&
1412  cast<ShuffleVectorInst>(RHS)->isConcat()) {
1413  // This transform does not have the speculative execution constraint as
1414  // below because the shuffle is a concatenation. The new binops are
1415  // operating on exactly the same elements as the existing binop.
1416  // TODO: We could ease the mask requirement to allow different undef lanes,
1417  // but that requires an analysis of the binop-with-undef output value.
1418  Value *NewBO0 = Builder.CreateBinOp(Opcode, L0, R0);
1419  if (auto *BO = dyn_cast<BinaryOperator>(NewBO0))
1420  BO->copyIRFlags(&Inst);
1421  Value *NewBO1 = Builder.CreateBinOp(Opcode, L1, R1);
1422  if (auto *BO = dyn_cast<BinaryOperator>(NewBO1))
1423  BO->copyIRFlags(&Inst);
1424  return new ShuffleVectorInst(NewBO0, NewBO1, Mask);
1425  }
1426 
1427  // It may not be safe to reorder shuffles and things like div, urem, etc.
1428  // because we may trap when executing those ops on unknown vector elements.
1429  // See PR20059.
1430  if (!isSafeToSpeculativelyExecute(&Inst))
1431  return nullptr;
1432 
1433  auto createBinOpShuffle = [&](Value *X, Value *Y, Constant *M) {
1434  Value *XY = Builder.CreateBinOp(Opcode, X, Y);
1435  if (auto *BO = dyn_cast<BinaryOperator>(XY))
1436  BO->copyIRFlags(&Inst);
1437  return new ShuffleVectorInst(XY, UndefValue::get(XY->getType()), M);
1438  };
1439 
1440  // If both arguments of the binary operation are shuffles that use the same
1441  // mask and shuffle within a single vector, move the shuffle after the binop.
1442  Value *V1, *V2;
1443  if (match(LHS, m_ShuffleVector(m_Value(V1), m_Undef(), m_Constant(Mask))) &&
1444  match(RHS, m_ShuffleVector(m_Value(V2), m_Undef(), m_Specific(Mask))) &&
1445  V1->getType() == V2->getType() &&
1446  (LHS->hasOneUse() || RHS->hasOneUse() || LHS == RHS)) {
1447  // Op(shuffle(V1, Mask), shuffle(V2, Mask)) -> shuffle(Op(V1, V2), Mask)
1448  return createBinOpShuffle(V1, V2, Mask);
1449  }
1450 
1451  // If both arguments of a commutative binop are select-shuffles that use the
1452  // same mask with commuted operands, the shuffles are unnecessary.
1453  if (Inst.isCommutative() &&
1454  match(LHS, m_ShuffleVector(m_Value(V1), m_Value(V2), m_Constant(Mask))) &&
1456  m_Specific(Mask)))) {
1457  auto *LShuf = cast<ShuffleVectorInst>(LHS);
1458  auto *RShuf = cast<ShuffleVectorInst>(RHS);
1459  // TODO: Allow shuffles that contain undefs in the mask?
1460  // That is legal, but it reduces undef knowledge.
1461  // TODO: Allow arbitrary shuffles by shuffling after binop?
1462  // That might be legal, but we have to deal with poison.
1463  if (LShuf->isSelect() && !LShuf->getMask()->containsUndefElement() &&
1464  RShuf->isSelect() && !RShuf->getMask()->containsUndefElement()) {
1465  // Example:
1466  // LHS = shuffle V1, V2, <0, 5, 6, 3>
1467  // RHS = shuffle V2, V1, <0, 5, 6, 3>
1468  // LHS + RHS --> (V10+V20, V21+V11, V22+V12, V13+V23) --> V1 + V2
1469  Instruction *NewBO = BinaryOperator::Create(Opcode, V1, V2);
1470  NewBO->copyIRFlags(&Inst);
1471  return NewBO;
1472  }
1473  }
1474 
1475  // If one argument is a shuffle within one vector and the other is a constant,
1476  // try moving the shuffle after the binary operation. This canonicalization
1477  // intends to move shuffles closer to other shuffles and binops closer to
1478  // other binops, so they can be folded. It may also enable demanded elements
1479  // transforms.
1480  Constant *C;
1481  if (match(&Inst, m_c_BinOp(
1483  m_Constant(C))) &&
1484  V1->getType()->getVectorNumElements() <= NumElts) {
1485  assert(Inst.getType()->getScalarType() == V1->getType()->getScalarType() &&
1486  "Shuffle should not change scalar type");
1487 
1488  // Find constant NewC that has property:
1489  // shuffle(NewC, ShMask) = C
1490  // If such constant does not exist (example: ShMask=<0,0> and C=<1,2>)
1491  // reorder is not possible. A 1-to-1 mapping is not required. Example:
1492  // ShMask = <1,1,2,2> and C = <5,5,6,6> --> NewC = <undef,5,6,undef>
1493  bool ConstOp1 = isa<Constant>(RHS);
1494  SmallVector<int, 16> ShMask;
1495  ShuffleVectorInst::getShuffleMask(Mask, ShMask);
1496  unsigned SrcVecNumElts = V1->getType()->getVectorNumElements();
1497  UndefValue *UndefScalar = UndefValue::get(C->getType()->getScalarType());
1498  SmallVector<Constant *, 16> NewVecC(SrcVecNumElts, UndefScalar);
1499  bool MayChange = true;
1500  for (unsigned I = 0; I < NumElts; ++I) {
1501  Constant *CElt = C->getAggregateElement(I);
1502  if (ShMask[I] >= 0) {
1503  assert(ShMask[I] < (int)NumElts && "Not expecting narrowing shuffle");
1504  Constant *NewCElt = NewVecC[ShMask[I]];
1505  // Bail out if:
1506  // 1. The constant vector contains a constant expression.
1507  // 2. The shuffle needs an element of the constant vector that can't
1508  // be mapped to a new constant vector.
1509  // 3. This is a widening shuffle that copies elements of V1 into the
1510  // extended elements (extending with undef is allowed).
1511  if (!CElt || (!isa<UndefValue>(NewCElt) && NewCElt != CElt) ||
1512  I >= SrcVecNumElts) {
1513  MayChange = false;
1514  break;
1515  }
1516  NewVecC[ShMask[I]] = CElt;
1517  }
1518  // If this is a widening shuffle, we must be able to extend with undef
1519  // elements. If the original binop does not produce an undef in the high
1520  // lanes, then this transform is not safe.
1521  // TODO: We could shuffle those non-undef constant values into the
1522  // result by using a constant vector (rather than an undef vector)
1523  // as operand 1 of the new binop, but that might be too aggressive
1524  // for target-independent shuffle creation.
1525  if (I >= SrcVecNumElts) {
1526  Constant *MaybeUndef =
1527  ConstOp1 ? ConstantExpr::get(Opcode, UndefScalar, CElt)
1528  : ConstantExpr::get(Opcode, CElt, UndefScalar);
1529  if (!isa<UndefValue>(MaybeUndef)) {
1530  MayChange = false;
1531  break;
1532  }
1533  }
1534  }
1535  if (MayChange) {
1536  Constant *NewC = ConstantVector::get(NewVecC);
1537  // It may not be safe to execute a binop on a vector with undef elements
1538  // because the entire instruction can be folded to undef or create poison
1539  // that did not exist in the original code.
1540  if (Inst.isIntDivRem() || (Inst.isShift() && ConstOp1))
1541  NewC = getSafeVectorConstantForBinop(Opcode, NewC, ConstOp1);
1542 
1543  // Op(shuffle(V1, Mask), C) -> shuffle(Op(V1, NewC), Mask)
1544  // Op(C, shuffle(V1, Mask)) -> shuffle(Op(NewC, V1), Mask)
1545  Value *NewLHS = ConstOp1 ? V1 : NewC;
1546  Value *NewRHS = ConstOp1 ? NewC : V1;
1547  return createBinOpShuffle(NewLHS, NewRHS, Mask);
1548  }
1549  }
1550 
1551  return nullptr;
1552 }
1553 
1554 /// Try to narrow the width of a binop if at least 1 operand is an extend of
1555 /// of a value. This requires a potentially expensive known bits check to make
1556 /// sure the narrow op does not overflow.
1557 Instruction *InstCombiner::narrowMathIfNoOverflow(BinaryOperator &BO) {
1558  // We need at least one extended operand.
1559  Value *Op0 = BO.getOperand(0), *Op1 = BO.getOperand(1);
1560 
1561  // If this is a sub, we swap the operands since we always want an extension
1562  // on the RHS. The LHS can be an extension or a constant.
1563  if (BO.getOpcode() == Instruction::Sub)
1564  std::swap(Op0, Op1);
1565 
1566  Value *X;
1567  bool IsSext = match(Op0, m_SExt(m_Value(X)));
1568  if (!IsSext && !match(Op0, m_ZExt(m_Value(X))))
1569  return nullptr;
1570 
1571  // If both operands are the same extension from the same source type and we
1572  // can eliminate at least one (hasOneUse), this might work.
1573  CastInst::CastOps CastOpc = IsSext ? Instruction::SExt : Instruction::ZExt;
1574  Value *Y;
1575  if (!(match(Op1, m_ZExtOrSExt(m_Value(Y))) && X->getType() == Y->getType() &&
1576  cast<Operator>(Op1)->getOpcode() == CastOpc &&
1577  (Op0->hasOneUse() || Op1->hasOneUse()))) {
1578  // If that did not match, see if we have a suitable constant operand.
1579  // Truncating and extending must produce the same constant.
1580  Constant *WideC;
1581  if (!Op0->hasOneUse() || !match(Op1, m_Constant(WideC)))
1582  return nullptr;
1583  Constant *NarrowC = ConstantExpr::getTrunc(WideC, X->getType());
1584  if (ConstantExpr::getCast(CastOpc, NarrowC, BO.getType()) != WideC)
1585  return nullptr;
1586  Y = NarrowC;
1587  }
1588 
1589  // Swap back now that we found our operands.
1590  if (BO.getOpcode() == Instruction::Sub)
1591  std::swap(X, Y);
1592 
1593  // Both operands have narrow versions. Last step: the math must not overflow
1594  // in the narrow width.
1595  if (!willNotOverflow(BO.getOpcode(), X, Y, BO, IsSext))
1596  return nullptr;
1597 
1598  // bo (ext X), (ext Y) --> ext (bo X, Y)
1599  // bo (ext X), C --> ext (bo X, C')
1600  Value *NarrowBO = Builder.CreateBinOp(BO.getOpcode(), X, Y, "narrow");
1601  if (auto *NewBinOp = dyn_cast<BinaryOperator>(NarrowBO)) {
1602  if (IsSext)
1603  NewBinOp->setHasNoSignedWrap();
1604  else
1605  NewBinOp->setHasNoUnsignedWrap();
1606  }
1607  return CastInst::Create(CastOpc, NarrowBO, BO.getType());
1608 }
1609 
1611  SmallVector<Value*, 8> Ops(GEP.op_begin(), GEP.op_end());
1612  Type *GEPType = GEP.getType();
1613  Type *GEPEltType = GEP.getSourceElementType();
1614  if (Value *V = SimplifyGEPInst(GEPEltType, Ops, SQ.getWithInstruction(&GEP)))
1615  return replaceInstUsesWith(GEP, V);
1616 
1617  // For vector geps, use the generic demanded vector support.
1618  if (GEP.getType()->isVectorTy()) {
1619  auto VWidth = GEP.getType()->getVectorNumElements();
1620  APInt UndefElts(VWidth, 0);
1621  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1622  if (Value *V = SimplifyDemandedVectorElts(&GEP, AllOnesEltMask,
1623  UndefElts)) {
1624  if (V != &GEP)
1625  return replaceInstUsesWith(GEP, V);
1626  return &GEP;
1627  }
1628 
1629  // TODO: 1) Scalarize splat operands, 2) scalarize entire instruction if
1630  // possible (decide on canonical form for pointer broadcast), 3) exploit
1631  // undef elements to decrease demanded bits
1632  }
1633 
1634  Value *PtrOp = GEP.getOperand(0);
1635 
1636  // Eliminate unneeded casts for indices, and replace indices which displace
1637  // by multiples of a zero size type with zero.
1638  bool MadeChange = false;
1639 
1640  // Index width may not be the same width as pointer width.
1641  // Data layout chooses the right type based on supported integer types.
1642  Type *NewScalarIndexTy =
1643  DL.getIndexType(GEP.getPointerOperandType()->getScalarType());
1644 
1645  gep_type_iterator GTI = gep_type_begin(GEP);
1646  for (User::op_iterator I = GEP.op_begin() + 1, E = GEP.op_end(); I != E;
1647  ++I, ++GTI) {
1648  // Skip indices into struct types.
1649  if (GTI.isStruct())
1650  continue;
1651 
1652  Type *IndexTy = (*I)->getType();
1653  Type *NewIndexType =
1654  IndexTy->isVectorTy()
1655  ? VectorType::get(NewScalarIndexTy, IndexTy->getVectorNumElements())
1656  : NewScalarIndexTy;
1657 
1658  // If the element type has zero size then any index over it is equivalent
1659  // to an index of zero, so replace it with zero if it is not zero already.
1660  Type *EltTy = GTI.getIndexedType();
1661  if (EltTy->isSized() && DL.getTypeAllocSize(EltTy) == 0)
1662  if (!isa<Constant>(*I) || !cast<Constant>(*I)->isNullValue()) {
1663  *I = Constant::getNullValue(NewIndexType);
1664  MadeChange = true;
1665  }
1666 
1667  if (IndexTy != NewIndexType) {
1668  // If we are using a wider index than needed for this platform, shrink
1669  // it to what we need. If narrower, sign-extend it to what we need.
1670  // This explicit cast can make subsequent optimizations more obvious.
1671  *I = Builder.CreateIntCast(*I, NewIndexType, true);
1672  MadeChange = true;
1673  }
1674  }
1675  if (MadeChange)
1676  return &GEP;
1677 
1678  // Check to see if the inputs to the PHI node are getelementptr instructions.
1679  if (auto *PN = dyn_cast<PHINode>(PtrOp)) {
1680  auto *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));
1681  if (!Op1)
1682  return nullptr;
1683 
1684  // Don't fold a GEP into itself through a PHI node. This can only happen
1685  // through the back-edge of a loop. Folding a GEP into itself means that
1686  // the value of the previous iteration needs to be stored in the meantime,
1687  // thus requiring an additional register variable to be live, but not
1688  // actually achieving anything (the GEP still needs to be executed once per
1689  // loop iteration).
1690  if (Op1 == &GEP)
1691  return nullptr;
1692 
1693  int DI = -1;
1694 
1695  for (auto I = PN->op_begin()+1, E = PN->op_end(); I !=E; ++I) {
1696  auto *Op2 = dyn_cast<GetElementPtrInst>(*I);
1697  if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands())
1698  return nullptr;
1699 
1700  // As for Op1 above, don't try to fold a GEP into itself.
1701  if (Op2 == &GEP)
1702  return nullptr;
1703 
1704  // Keep track of the type as we walk the GEP.
1705  Type *CurTy = nullptr;
1706 
1707  for (unsigned J = 0, F = Op1->getNumOperands(); J != F; ++J) {
1708  if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())
1709  return nullptr;
1710 
1711  if (Op1->getOperand(J) != Op2->getOperand(J)) {
1712  if (DI == -1) {
1713  // We have not seen any differences yet in the GEPs feeding the
1714  // PHI yet, so we record this one if it is allowed to be a
1715  // variable.
1716 
1717  // The first two arguments can vary for any GEP, the rest have to be
1718  // static for struct slots
1719  if (J > 1 && CurTy->isStructTy())
1720  return nullptr;
1721 
1722  DI = J;
1723  } else {
1724  // The GEP is different by more than one input. While this could be
1725  // extended to support GEPs that vary by more than one variable it
1726  // doesn't make sense since it greatly increases the complexity and
1727  // would result in an R+R+R addressing mode which no backend
1728  // directly supports and would need to be broken into several
1729  // simpler instructions anyway.
1730  return nullptr;
1731  }
1732  }
1733 
1734  // Sink down a layer of the type for the next iteration.
1735  if (J > 0) {
1736  if (J == 1) {
1737  CurTy = Op1->getSourceElementType();
1738  } else if (auto *CT = dyn_cast<CompositeType>(CurTy)) {
1739  CurTy = CT->getTypeAtIndex(Op1->getOperand(J));
1740  } else {
1741  CurTy = nullptr;
1742  }
1743  }
1744  }
1745  }
1746 
1747  // If not all GEPs are identical we'll have to create a new PHI node.
1748  // Check that the old PHI node has only one use so that it will get
1749  // removed.
1750  if (DI != -1 && !PN->hasOneUse())
1751  return nullptr;
1752 
1753  auto *NewGEP = cast<GetElementPtrInst>(Op1->clone());
1754  if (DI == -1) {
1755  // All the GEPs feeding the PHI are identical. Clone one down into our
1756  // BB so that it can be merged with the current GEP.
1757  GEP.getParent()->getInstList().insert(
1758  GEP.getParent()->getFirstInsertionPt(), NewGEP);
1759  } else {
1760  // All the GEPs feeding the PHI differ at a single offset. Clone a GEP
1761  // into the current block so it can be merged, and create a new PHI to
1762  // set that index.
1763  PHINode *NewPN;
1764  {
1765  IRBuilderBase::InsertPointGuard Guard(Builder);
1766  Builder.SetInsertPoint(PN);
1767  NewPN = Builder.CreatePHI(Op1->getOperand(DI)->getType(),
1768  PN->getNumOperands());
1769  }
1770 
1771  for (auto &I : PN->operands())
1772  NewPN->addIncoming(cast<GEPOperator>(I)->getOperand(DI),
1773  PN->getIncomingBlock(I));
1774 
1775  NewGEP->setOperand(DI, NewPN);
1776  GEP.getParent()->getInstList().insert(
1777  GEP.getParent()->getFirstInsertionPt(), NewGEP);
1778  NewGEP->setOperand(DI, NewPN);
1779  }
1780 
1781  GEP.setOperand(0, NewGEP);
1782  PtrOp = NewGEP;
1783  }
1784 
1785  // Combine Indices - If the source pointer to this getelementptr instruction
1786  // is a getelementptr instruction, combine the indices of the two
1787  // getelementptr instructions into a single instruction.
1788  if (auto *Src = dyn_cast<GEPOperator>(PtrOp)) {
1789  if (!shouldMergeGEPs(*cast<GEPOperator>(&GEP), *Src))
1790  return nullptr;
1791 
1792  // Try to reassociate loop invariant GEP chains to enable LICM.
1793  if (LI && Src->getNumOperands() == 2 && GEP.getNumOperands() == 2 &&
1794  Src->hasOneUse()) {
1795  if (Loop *L = LI->getLoopFor(GEP.getParent())) {
1796  Value *GO1 = GEP.getOperand(1);
1797  Value *SO1 = Src->getOperand(1);
1798  // Reassociate the two GEPs if SO1 is variant in the loop and GO1 is
1799  // invariant: this breaks the dependence between GEPs and allows LICM
1800  // to hoist the invariant part out of the loop.
1801  if (L->isLoopInvariant(GO1) && !L->isLoopInvariant(SO1)) {
1802  // We have to be careful here.
1803  // We have something like:
1804  // %src = getelementptr <ty>, <ty>* %base, <ty> %idx
1805  // %gep = getelementptr <ty>, <ty>* %src, <ty> %idx2
1806  // If we just swap idx & idx2 then we could inadvertantly
1807  // change %src from a vector to a scalar, or vice versa.
1808  // Cases:
1809  // 1) %base a scalar & idx a scalar & idx2 a vector
1810  // => Swapping idx & idx2 turns %src into a vector type.
1811  // 2) %base a scalar & idx a vector & idx2 a scalar
1812  // => Swapping idx & idx2 turns %src in a scalar type
1813  // 3) %base, %idx, and %idx2 are scalars
1814  // => %src & %gep are scalars
1815  // => swapping idx & idx2 is safe
1816  // 4) %base a vector
1817  // => %src is a vector
1818  // => swapping idx & idx2 is safe.
1819  auto *SO0 = Src->getOperand(0);
1820  auto *SO0Ty = SO0->getType();
1821  if (!isa<VectorType>(GEPType) || // case 3
1822  isa<VectorType>(SO0Ty)) { // case 4
1823  Src->setOperand(1, GO1);
1824  GEP.setOperand(1, SO1);
1825  return &GEP;
1826  } else {
1827  // Case 1 or 2
1828  // -- have to recreate %src & %gep
1829  // put NewSrc at same location as %src
1830  Builder.SetInsertPoint(cast<Instruction>(PtrOp));
1831  auto *NewSrc = cast<GetElementPtrInst>(
1832  Builder.CreateGEP(GEPEltType, SO0, GO1, Src->getName()));
1833  NewSrc->setIsInBounds(Src->isInBounds());
1834  auto *NewGEP = GetElementPtrInst::Create(GEPEltType, NewSrc, {SO1});
1835  NewGEP->setIsInBounds(GEP.isInBounds());
1836  return NewGEP;
1837  }
1838  }
1839  }
1840  }
1841 
1842  // Note that if our source is a gep chain itself then we wait for that
1843  // chain to be resolved before we perform this transformation. This
1844  // avoids us creating a TON of code in some cases.
1845  if (auto *SrcGEP = dyn_cast<GEPOperator>(Src->getOperand(0)))
1846  if (SrcGEP->getNumOperands() == 2 && shouldMergeGEPs(*Src, *SrcGEP))
1847  return nullptr; // Wait until our source is folded to completion.
1848 
1849  SmallVector<Value*, 8> Indices;
1850 
1851  // Find out whether the last index in the source GEP is a sequential idx.
1852  bool EndsWithSequential = false;
1853  for (gep_type_iterator I = gep_type_begin(*Src), E = gep_type_end(*Src);
1854  I != E; ++I)
1855  EndsWithSequential = I.isSequential();
1856 
1857  // Can we combine the two pointer arithmetics offsets?
1858  if (EndsWithSequential) {
1859  // Replace: gep (gep %P, long B), long A, ...
1860  // With: T = long A+B; gep %P, T, ...
1861  Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
1862  Value *GO1 = GEP.getOperand(1);
1863 
1864  // If they aren't the same type, then the input hasn't been processed
1865  // by the loop above yet (which canonicalizes sequential index types to
1866  // intptr_t). Just avoid transforming this until the input has been
1867  // normalized.
1868  if (SO1->getType() != GO1->getType())
1869  return nullptr;
1870 
1871  Value *Sum =
1872  SimplifyAddInst(GO1, SO1, false, false, SQ.getWithInstruction(&GEP));
1873  // Only do the combine when we are sure the cost after the
1874  // merge is never more than that before the merge.
1875  if (Sum == nullptr)
1876  return nullptr;
1877 
1878  // Update the GEP in place if possible.
1879  if (Src->getNumOperands() == 2) {
1880  GEP.setOperand(0, Src->getOperand(0));
1881  GEP.setOperand(1, Sum);
1882  return &GEP;
1883  }
1884  Indices.append(Src->op_begin()+1, Src->op_end()-1);
1885  Indices.push_back(Sum);
1886  Indices.append(GEP.op_begin()+2, GEP.op_end());
1887  } else if (isa<Constant>(*GEP.idx_begin()) &&
1888  cast<Constant>(*GEP.idx_begin())->isNullValue() &&
1889  Src->getNumOperands() != 1) {
1890  // Otherwise we can do the fold if the first index of the GEP is a zero
1891  Indices.append(Src->op_begin()+1, Src->op_end());
1892  Indices.append(GEP.idx_begin()+1, GEP.idx_end());
1893  }
1894 
1895  if (!Indices.empty())
1896  return GEP.isInBounds() && Src->isInBounds()
1898  Src->getSourceElementType(), Src->getOperand(0), Indices,
1899  GEP.getName())
1900  : GetElementPtrInst::Create(Src->getSourceElementType(),
1901  Src->getOperand(0), Indices,
1902  GEP.getName());
1903  }
1904 
1905  if (GEP.getNumIndices() == 1) {
1906  unsigned AS = GEP.getPointerAddressSpace();
1907  if (GEP.getOperand(1)->getType()->getScalarSizeInBits() ==
1908  DL.getIndexSizeInBits(AS)) {
1909  uint64_t TyAllocSize = DL.getTypeAllocSize(GEPEltType);
1910 
1911  bool Matched = false;
1912  uint64_t C;
1913  Value *V = nullptr;
1914  if (TyAllocSize == 1) {
1915  V = GEP.getOperand(1);
1916  Matched = true;
1917  } else if (match(GEP.getOperand(1),
1918  m_AShr(m_Value(V), m_ConstantInt(C)))) {
1919  if (TyAllocSize == 1ULL << C)
1920  Matched = true;
1921  } else if (match(GEP.getOperand(1),
1922  m_SDiv(m_Value(V), m_ConstantInt(C)))) {
1923  if (TyAllocSize == C)
1924  Matched = true;
1925  }
1926 
1927  if (Matched) {
1928  // Canonicalize (gep i8* X, -(ptrtoint Y))
1929  // to (inttoptr (sub (ptrtoint X), (ptrtoint Y)))
1930  // The GEP pattern is emitted by the SCEV expander for certain kinds of
1931  // pointer arithmetic.
1932  if (match(V, m_Neg(m_PtrToInt(m_Value())))) {
1933  Operator *Index = cast<Operator>(V);
1934  Value *PtrToInt = Builder.CreatePtrToInt(PtrOp, Index->getType());
1935  Value *NewSub = Builder.CreateSub(PtrToInt, Index->getOperand(1));
1936  return CastInst::Create(Instruction::IntToPtr, NewSub, GEPType);
1937  }
1938  // Canonicalize (gep i8* X, (ptrtoint Y)-(ptrtoint X))
1939  // to (bitcast Y)
1940  Value *Y;
1941  if (match(V, m_Sub(m_PtrToInt(m_Value(Y)),
1942  m_PtrToInt(m_Specific(GEP.getOperand(0))))))
1944  }
1945  }
1946  }
1947 
1948  // We do not handle pointer-vector geps here.
1949  if (GEPType->isVectorTy())
1950  return nullptr;
1951 
1952  // Handle gep(bitcast x) and gep(gep x, 0, 0, 0).
1953  Value *StrippedPtr = PtrOp->stripPointerCasts();
1954  PointerType *StrippedPtrTy = cast<PointerType>(StrippedPtr->getType());
1955 
1956  if (StrippedPtr != PtrOp) {
1957  bool HasZeroPointerIndex = false;
1958  Type *StrippedPtrEltTy = StrippedPtrTy->getElementType();
1959 
1960  if (auto *C = dyn_cast<ConstantInt>(GEP.getOperand(1)))
1961  HasZeroPointerIndex = C->isZero();
1962 
1963  // Transform: GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ...
1964  // into : GEP [10 x i8]* X, i32 0, ...
1965  //
1966  // Likewise, transform: GEP (bitcast i8* X to [0 x i8]*), i32 0, ...
1967  // into : GEP i8* X, ...
1968  //
1969  // This occurs when the program declares an array extern like "int X[];"
1970  if (HasZeroPointerIndex) {
1971  if (auto *CATy = dyn_cast<ArrayType>(GEPEltType)) {
1972  // GEP (bitcast i8* X to [0 x i8]*), i32 0, ... ?
1973  if (CATy->getElementType() == StrippedPtrEltTy) {
1974  // -> GEP i8* X, ...
1975  SmallVector<Value*, 8> Idx(GEP.idx_begin()+1, GEP.idx_end());
1977  StrippedPtrEltTy, StrippedPtr, Idx, GEP.getName());
1978  Res->setIsInBounds(GEP.isInBounds());
1979  if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace())
1980  return Res;
1981  // Insert Res, and create an addrspacecast.
1982  // e.g.,
1983  // GEP (addrspacecast i8 addrspace(1)* X to [0 x i8]*), i32 0, ...
1984  // ->
1985  // %0 = GEP i8 addrspace(1)* X, ...
1986  // addrspacecast i8 addrspace(1)* %0 to i8*
1987  return new AddrSpaceCastInst(Builder.Insert(Res), GEPType);
1988  }
1989 
1990  if (auto *XATy = dyn_cast<ArrayType>(StrippedPtrEltTy)) {
1991  // GEP (bitcast [10 x i8]* X to [0 x i8]*), i32 0, ... ?
1992  if (CATy->getElementType() == XATy->getElementType()) {
1993  // -> GEP [10 x i8]* X, i32 0, ...
1994  // At this point, we know that the cast source type is a pointer
1995  // to an array of the same type as the destination pointer
1996  // array. Because the array type is never stepped over (there
1997  // is a leading zero) we can fold the cast into this GEP.
1998  if (StrippedPtrTy->getAddressSpace() == GEP.getAddressSpace()) {
1999  GEP.setOperand(0, StrippedPtr);
2000  GEP.setSourceElementType(XATy);
2001  return &GEP;
2002  }
2003  // Cannot replace the base pointer directly because StrippedPtr's
2004  // address space is different. Instead, create a new GEP followed by
2005  // an addrspacecast.
2006  // e.g.,
2007  // GEP (addrspacecast [10 x i8] addrspace(1)* X to [0 x i8]*),
2008  // i32 0, ...
2009  // ->
2010  // %0 = GEP [10 x i8] addrspace(1)* X, ...
2011  // addrspacecast i8 addrspace(1)* %0 to i8*
2012  SmallVector<Value*, 8> Idx(GEP.idx_begin(), GEP.idx_end());
2013  Value *NewGEP =
2014  GEP.isInBounds()
2015  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2016  Idx, GEP.getName())
2017  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2018  GEP.getName());
2019  return new AddrSpaceCastInst(NewGEP, GEPType);
2020  }
2021  }
2022  }
2023  } else if (GEP.getNumOperands() == 2) {
2024  // Transform things like:
2025  // %t = getelementptr i32* bitcast ([2 x i32]* %str to i32*), i32 %V
2026  // into: %t1 = getelementptr [2 x i32]* %str, i32 0, i32 %V; bitcast
2027  if (StrippedPtrEltTy->isArrayTy() &&
2028  DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType()) ==
2029  DL.getTypeAllocSize(GEPEltType)) {
2030  Type *IdxType = DL.getIndexType(GEPType);
2031  Value *Idx[2] = { Constant::getNullValue(IdxType), GEP.getOperand(1) };
2032  Value *NewGEP =
2033  GEP.isInBounds()
2034  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2035  GEP.getName())
2036  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Idx,
2037  GEP.getName());
2038 
2039  // V and GEP are both pointer types --> BitCast
2040  return CastInst::CreatePointerBitCastOrAddrSpaceCast(NewGEP, GEPType);
2041  }
2042 
2043  // Transform things like:
2044  // %V = mul i64 %N, 4
2045  // %t = getelementptr i8* bitcast (i32* %arr to i8*), i32 %V
2046  // into: %t1 = getelementptr i32* %arr, i32 %N; bitcast
2047  if (GEPEltType->isSized() && StrippedPtrEltTy->isSized()) {
2048  // Check that changing the type amounts to dividing the index by a scale
2049  // factor.
2050  uint64_t ResSize = DL.getTypeAllocSize(GEPEltType);
2051  uint64_t SrcSize = DL.getTypeAllocSize(StrippedPtrEltTy);
2052  if (ResSize && SrcSize % ResSize == 0) {
2053  Value *Idx = GEP.getOperand(1);
2054  unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
2055  uint64_t Scale = SrcSize / ResSize;
2056 
2057  // Earlier transforms ensure that the index has the right type
2058  // according to Data Layout, which considerably simplifies the
2059  // logic by eliminating implicit casts.
2060  assert(Idx->getType() == DL.getIndexType(GEPType) &&
2061  "Index type does not match the Data Layout preferences");
2062 
2063  bool NSW;
2064  if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
2065  // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
2066  // If the multiplication NewIdx * Scale may overflow then the new
2067  // GEP may not be "inbounds".
2068  Value *NewGEP =
2069  GEP.isInBounds() && NSW
2070  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2071  NewIdx, GEP.getName())
2072  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, NewIdx,
2073  GEP.getName());
2074 
2075  // The NewGEP must be pointer typed, so must the old one -> BitCast
2077  GEPType);
2078  }
2079  }
2080  }
2081 
2082  // Similarly, transform things like:
2083  // getelementptr i8* bitcast ([100 x double]* X to i8*), i32 %tmp
2084  // (where tmp = 8*tmp2) into:
2085  // getelementptr [100 x double]* %arr, i32 0, i32 %tmp2; bitcast
2086  if (GEPEltType->isSized() && StrippedPtrEltTy->isSized() &&
2087  StrippedPtrEltTy->isArrayTy()) {
2088  // Check that changing to the array element type amounts to dividing the
2089  // index by a scale factor.
2090  uint64_t ResSize = DL.getTypeAllocSize(GEPEltType);
2091  uint64_t ArrayEltSize =
2092  DL.getTypeAllocSize(StrippedPtrEltTy->getArrayElementType());
2093  if (ResSize && ArrayEltSize % ResSize == 0) {
2094  Value *Idx = GEP.getOperand(1);
2095  unsigned BitWidth = Idx->getType()->getPrimitiveSizeInBits();
2096  uint64_t Scale = ArrayEltSize / ResSize;
2097 
2098  // Earlier transforms ensure that the index has the right type
2099  // according to the Data Layout, which considerably simplifies
2100  // the logic by eliminating implicit casts.
2101  assert(Idx->getType() == DL.getIndexType(GEPType) &&
2102  "Index type does not match the Data Layout preferences");
2103 
2104  bool NSW;
2105  if (Value *NewIdx = Descale(Idx, APInt(BitWidth, Scale), NSW)) {
2106  // Successfully decomposed Idx as NewIdx * Scale, form a new GEP.
2107  // If the multiplication NewIdx * Scale may overflow then the new
2108  // GEP may not be "inbounds".
2109  Type *IndTy = DL.getIndexType(GEPType);
2110  Value *Off[2] = {Constant::getNullValue(IndTy), NewIdx};
2111 
2112  Value *NewGEP =
2113  GEP.isInBounds() && NSW
2114  ? Builder.CreateInBoundsGEP(StrippedPtrEltTy, StrippedPtr,
2115  Off, GEP.getName())
2116  : Builder.CreateGEP(StrippedPtrEltTy, StrippedPtr, Off,
2117  GEP.getName());
2118  // The NewGEP must be pointer typed, so must the old one -> BitCast
2120  GEPType);
2121  }
2122  }
2123  }
2124  }
2125  }
2126 
2127  // addrspacecast between types is canonicalized as a bitcast, then an
2128  // addrspacecast. To take advantage of the below bitcast + struct GEP, look
2129  // through the addrspacecast.
2130  Value *ASCStrippedPtrOp = PtrOp;
2131  if (auto *ASC = dyn_cast<AddrSpaceCastInst>(PtrOp)) {
2132  // X = bitcast A addrspace(1)* to B addrspace(1)*
2133  // Y = addrspacecast A addrspace(1)* to B addrspace(2)*
2134  // Z = gep Y, <...constant indices...>
2135  // Into an addrspacecasted GEP of the struct.
2136  if (auto *BC = dyn_cast<BitCastInst>(ASC->getOperand(0)))
2137  ASCStrippedPtrOp = BC;
2138  }
2139 
2140  if (auto *BCI = dyn_cast<BitCastInst>(ASCStrippedPtrOp)) {
2141  Value *SrcOp = BCI->getOperand(0);
2142  PointerType *SrcType = cast<PointerType>(BCI->getSrcTy());
2143  Type *SrcEltType = SrcType->getElementType();
2144 
2145  // GEP directly using the source operand if this GEP is accessing an element
2146  // of a bitcasted pointer to vector or array of the same dimensions:
2147  // gep (bitcast <c x ty>* X to [c x ty]*), Y, Z --> gep X, Y, Z
2148  // gep (bitcast [c x ty]* X to <c x ty>*), Y, Z --> gep X, Y, Z
2149  auto areMatchingArrayAndVecTypes = [](Type *ArrTy, Type *VecTy) {
2150  return ArrTy->getArrayElementType() == VecTy->getVectorElementType() &&
2151  ArrTy->getArrayNumElements() == VecTy->getVectorNumElements();
2152  };
2153  if (GEP.getNumOperands() == 3 &&
2154  ((GEPEltType->isArrayTy() && SrcEltType->isVectorTy() &&
2155  areMatchingArrayAndVecTypes(GEPEltType, SrcEltType)) ||
2156  (GEPEltType->isVectorTy() && SrcEltType->isArrayTy() &&
2157  areMatchingArrayAndVecTypes(SrcEltType, GEPEltType)))) {
2158 
2159  // Create a new GEP here, as using `setOperand()` followed by
2160  // `setSourceElementType()` won't actually update the type of the
2161  // existing GEP Value. Causing issues if this Value is accessed when
2162  // constructing an AddrSpaceCastInst
2163  Value *NGEP =
2164  GEP.isInBounds()
2165  ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]})
2166  : Builder.CreateGEP(SrcEltType, SrcOp, {Ops[1], Ops[2]});
2167  NGEP->takeName(&GEP);
2168 
2169  // Preserve GEP address space to satisfy users
2170  if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace())
2171  return new AddrSpaceCastInst(NGEP, GEPType);
2172 
2173  return replaceInstUsesWith(GEP, NGEP);
2174  }
2175 
2176  // See if we can simplify:
2177  // X = bitcast A* to B*
2178  // Y = gep X, <...constant indices...>
2179  // into a gep of the original struct. This is important for SROA and alias
2180  // analysis of unions. If "A" is also a bitcast, wait for A/X to be merged.
2181  unsigned OffsetBits = DL.getIndexTypeSizeInBits(GEPType);
2182  APInt Offset(OffsetBits, 0);
2183  if (!isa<BitCastInst>(SrcOp) && GEP.accumulateConstantOffset(DL, Offset)) {
2184  // If this GEP instruction doesn't move the pointer, just replace the GEP
2185  // with a bitcast of the real input to the dest type.
2186  if (!Offset) {
2187  // If the bitcast is of an allocation, and the allocation will be
2188  // converted to match the type of the cast, don't touch this.
2189  if (isa<AllocaInst>(SrcOp) || isAllocationFn(SrcOp, &TLI)) {
2190  // See if the bitcast simplifies, if so, don't nuke this GEP yet.
2191  if (Instruction *I = visitBitCast(*BCI)) {
2192  if (I != BCI) {
2193  I->takeName(BCI);
2194  BCI->getParent()->getInstList().insert(BCI->getIterator(), I);
2195  replaceInstUsesWith(*BCI, I);
2196  }
2197  return &GEP;
2198  }
2199  }
2200 
2201  if (SrcType->getPointerAddressSpace() != GEP.getAddressSpace())
2202  return new AddrSpaceCastInst(SrcOp, GEPType);
2203  return new BitCastInst(SrcOp, GEPType);
2204  }
2205 
2206  // Otherwise, if the offset is non-zero, we need to find out if there is a
2207  // field at Offset in 'A's type. If so, we can pull the cast through the
2208  // GEP.
2209  SmallVector<Value*, 8> NewIndices;
2210  if (FindElementAtOffset(SrcType, Offset.getSExtValue(), NewIndices)) {
2211  Value *NGEP =
2212  GEP.isInBounds()
2213  ? Builder.CreateInBoundsGEP(SrcEltType, SrcOp, NewIndices)
2214  : Builder.CreateGEP(SrcEltType, SrcOp, NewIndices);
2215 
2216  if (NGEP->getType() == GEPType)
2217  return replaceInstUsesWith(GEP, NGEP);
2218  NGEP->takeName(&GEP);
2219 
2220  if (NGEP->getType()->getPointerAddressSpace() != GEP.getAddressSpace())
2221  return new AddrSpaceCastInst(NGEP, GEPType);
2222  return new BitCastInst(NGEP, GEPType);
2223  }
2224  }
2225  }
2226 
2227  if (!GEP.isInBounds()) {
2228  unsigned IdxWidth =
2229  DL.getIndexSizeInBits(PtrOp->getType()->getPointerAddressSpace());
2230  APInt BasePtrOffset(IdxWidth, 0);
2231  Value *UnderlyingPtrOp =
2233  BasePtrOffset);
2234  if (auto *AI = dyn_cast<AllocaInst>(UnderlyingPtrOp)) {
2235  if (GEP.accumulateConstantOffset(DL, BasePtrOffset) &&
2236  BasePtrOffset.isNonNegative()) {
2237  APInt AllocSize(IdxWidth, DL.getTypeAllocSize(AI->getAllocatedType()));
2238  if (BasePtrOffset.ule(AllocSize)) {
2240  GEP.getSourceElementType(), PtrOp, makeArrayRef(Ops).slice(1),
2241  GEP.getName());
2242  }
2243  }
2244  }
2245  }
2246 
2247  return nullptr;
2248 }
2249 
2251  Instruction *AI) {
2252  if (isa<ConstantPointerNull>(V))
2253  return true;
2254  if (auto *LI = dyn_cast<LoadInst>(V))
2255  return isa<GlobalVariable>(LI->getPointerOperand());
2256  // Two distinct allocations will never be equal.
2257  // We rely on LookThroughBitCast in isAllocLikeFn being false, since looking
2258  // through bitcasts of V can cause
2259  // the result statement below to be true, even when AI and V (ex:
2260  // i8* ->i32* ->i8* of AI) are the same allocations.
2261  return isAllocLikeFn(V, TLI) && V != AI;
2262 }
2263 
2266  const TargetLibraryInfo *TLI) {
2268  Worklist.push_back(AI);
2269 
2270  do {
2271  Instruction *PI = Worklist.pop_back_val();
2272  for (User *U : PI->users()) {
2273  Instruction *I = cast<Instruction>(U);
2274  switch (I->getOpcode()) {
2275  default:
2276  // Give up the moment we see something we can't handle.
2277  return false;
2278 
2279  case Instruction::AddrSpaceCast:
2280  case Instruction::BitCast:
2281  case Instruction::GetElementPtr:
2282  Users.emplace_back(I);
2283  Worklist.push_back(I);
2284  continue;
2285 
2286  case Instruction::ICmp: {
2287  ICmpInst *ICI = cast<ICmpInst>(I);
2288  // We can fold eq/ne comparisons with null to false/true, respectively.
2289  // We also fold comparisons in some conditions provided the alloc has
2290  // not escaped (see isNeverEqualToUnescapedAlloc).
2291  if (!ICI->isEquality())
2292  return false;
2293  unsigned OtherIndex = (ICI->getOperand(0) == PI) ? 1 : 0;
2294  if (!isNeverEqualToUnescapedAlloc(ICI->getOperand(OtherIndex), TLI, AI))
2295  return false;
2296  Users.emplace_back(I);
2297  continue;
2298  }
2299 
2300  case Instruction::Call:
2301  // Ignore no-op and store intrinsics.
2302  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
2303  switch (II->getIntrinsicID()) {
2304  default:
2305  return false;
2306 
2307  case Intrinsic::memmove:
2308  case Intrinsic::memcpy:
2309  case Intrinsic::memset: {
2310  MemIntrinsic *MI = cast<MemIntrinsic>(II);
2311  if (MI->isVolatile() || MI->getRawDest() != PI)
2312  return false;
2314  }
2315  case Intrinsic::invariant_start:
2316  case Intrinsic::invariant_end:
2317  case Intrinsic::lifetime_start:
2318  case Intrinsic::lifetime_end:
2319  case Intrinsic::objectsize:
2320  Users.emplace_back(I);
2321  continue;
2322  }
2323  }
2324 
2325  if (isFreeCall(I, TLI)) {
2326  Users.emplace_back(I);
2327  continue;
2328  }
2329  return false;
2330 
2331  case Instruction::Store: {
2332  StoreInst *SI = cast<StoreInst>(I);
2333  if (SI->isVolatile() || SI->getPointerOperand() != PI)
2334  return false;
2335  Users.emplace_back(I);
2336  continue;
2337  }
2338  }
2339  llvm_unreachable("missing a return?");
2340  }
2341  } while (!Worklist.empty());
2342  return true;
2343 }
2344 
2346  // If we have a malloc call which is only used in any amount of comparisons to
2347  // null and free calls, delete the calls and replace the comparisons with true
2348  // or false as appropriate.
2349 
2350  // This is based on the principle that we can substitute our own allocation
2351  // function (which will never return null) rather than knowledge of the
2352  // specific function being called. In some sense this can change the permitted
2353  // outputs of a program (when we convert a malloc to an alloca, the fact that
2354  // the allocation is now on the stack is potentially visible, for example),
2355  // but we believe in a permissible manner.
2357 
2358  // If we are removing an alloca with a dbg.declare, insert dbg.value calls
2359  // before each store.
2361  std::unique_ptr<DIBuilder> DIB;
2362  if (isa<AllocaInst>(MI)) {
2363  DIIs = FindDbgAddrUses(&MI);
2364  DIB.reset(new DIBuilder(*MI.getModule(), /*AllowUnresolved=*/false));
2365  }
2366 
2367  if (isAllocSiteRemovable(&MI, Users, &TLI)) {
2368  for (unsigned i = 0, e = Users.size(); i != e; ++i) {
2369  // Lowering all @llvm.objectsize calls first because they may
2370  // use a bitcast/GEP of the alloca we are removing.
2371  if (!Users[i])
2372  continue;
2373 
2374  Instruction *I = cast<Instruction>(&*Users[i]);
2375 
2376  if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
2377  if (II->getIntrinsicID() == Intrinsic::objectsize) {
2378  Value *Result =
2379  lowerObjectSizeCall(II, DL, &TLI, /*MustSucceed=*/true);
2380  replaceInstUsesWith(*I, Result);
2381  eraseInstFromFunction(*I);
2382  Users[i] = nullptr; // Skip examining in the next loop.
2383  }
2384  }
2385  }
2386  for (unsigned i = 0, e = Users.size(); i != e; ++i) {
2387  if (!Users[i])
2388  continue;
2389 
2390  Instruction *I = cast<Instruction>(&*Users[i]);
2391 
2392  if (ICmpInst *C = dyn_cast<ICmpInst>(I)) {
2393  replaceInstUsesWith(*C,
2395  C->isFalseWhenEqual()));
2396  } else if (isa<BitCastInst>(I) || isa<GetElementPtrInst>(I) ||
2397  isa<AddrSpaceCastInst>(I)) {
2398  replaceInstUsesWith(*I, UndefValue::get(I->getType()));
2399  } else if (auto *SI = dyn_cast<StoreInst>(I)) {
2400  for (auto *DII : DIIs)
2401  ConvertDebugDeclareToDebugValue(DII, SI, *DIB);
2402  }
2403  eraseInstFromFunction(*I);
2404  }
2405 
2406  if (InvokeInst *II = dyn_cast<InvokeInst>(&MI)) {
2407  // Replace invoke with a NOP intrinsic to maintain the original CFG
2408  Module *M = II->getModule();
2409  Function *F = Intrinsic::getDeclaration(M, Intrinsic::donothing);
2410  InvokeInst::Create(F, II->getNormalDest(), II->getUnwindDest(),
2411  None, "", II->getParent());
2412  }
2413 
2414  for (auto *DII : DIIs)
2415  eraseInstFromFunction(*DII);
2416 
2417  return eraseInstFromFunction(MI);
2418  }
2419  return nullptr;
2420 }
2421 
2422 /// Move the call to free before a NULL test.
2423 ///
2424 /// Check if this free is accessed after its argument has been test
2425 /// against NULL (property 0).
2426 /// If yes, it is legal to move this call in its predecessor block.
2427 ///
2428 /// The move is performed only if the block containing the call to free
2429 /// will be removed, i.e.:
2430 /// 1. it has only one predecessor P, and P has two successors
2431 /// 2. it contains the call, noops, and an unconditional branch
2432 /// 3. its successor is the same as its predecessor's successor
2433 ///
2434 /// The profitability is out-of concern here and this function should
2435 /// be called only if the caller knows this transformation would be
2436 /// profitable (e.g., for code size).
2438  const DataLayout &DL) {
2439  Value *Op = FI.getArgOperand(0);
2440  BasicBlock *FreeInstrBB = FI.getParent();
2441  BasicBlock *PredBB = FreeInstrBB->getSinglePredecessor();
2442 
2443  // Validate part of constraint #1: Only one predecessor
2444  // FIXME: We can extend the number of predecessor, but in that case, we
2445  // would duplicate the call to free in each predecessor and it may
2446  // not be profitable even for code size.
2447  if (!PredBB)
2448  return nullptr;
2449 
2450  // Validate constraint #2: Does this block contains only the call to
2451  // free, noops, and an unconditional branch?
2452  BasicBlock *SuccBB;
2453  Instruction *FreeInstrBBTerminator = FreeInstrBB->getTerminator();
2454  if (!match(FreeInstrBBTerminator, m_UnconditionalBr(SuccBB)))
2455  return nullptr;
2456 
2457  // If there are only 2 instructions in the block, at this point,
2458  // this is the call to free and unconditional.
2459  // If there are more than 2 instructions, check that they are noops
2460  // i.e., they won't hurt the performance of the generated code.
2461  if (FreeInstrBB->size() != 2) {
2462  for (const Instruction &Inst : *FreeInstrBB) {
2463  if (&Inst == &FI || &Inst == FreeInstrBBTerminator)
2464  continue;
2465  auto *Cast = dyn_cast<CastInst>(&Inst);
2466  if (!Cast || !Cast->isNoopCast(DL))
2467  return nullptr;
2468  }
2469  }
2470  // Validate the rest of constraint #1 by matching on the pred branch.
2471  Instruction *TI = PredBB->getTerminator();
2472  BasicBlock *TrueBB, *FalseBB;
2473  ICmpInst::Predicate Pred;
2474  if (!match(TI, m_Br(m_ICmp(Pred,
2475  m_CombineOr(m_Specific(Op),
2476  m_Specific(Op->stripPointerCasts())),
2477  m_Zero()),
2478  TrueBB, FalseBB)))
2479  return nullptr;
2480  if (Pred != ICmpInst::ICMP_EQ && Pred != ICmpInst::ICMP_NE)
2481  return nullptr;
2482 
2483  // Validate constraint #3: Ensure the null case just falls through.
2484  if (SuccBB != (Pred == ICmpInst::ICMP_EQ ? TrueBB : FalseBB))
2485  return nullptr;
2486  assert(FreeInstrBB == (Pred == ICmpInst::ICMP_EQ ? FalseBB : TrueBB) &&
2487  "Broken CFG: missing edge from predecessor to successor");
2488 
2489  // At this point, we know that everything in FreeInstrBB can be moved
2490  // before TI.
2491  for (BasicBlock::iterator It = FreeInstrBB->begin(), End = FreeInstrBB->end();
2492  It != End;) {
2493  Instruction &Instr = *It++;
2494  if (&Instr == FreeInstrBBTerminator)
2495  break;
2496  Instr.moveBefore(TI);
2497  }
2498  assert(FreeInstrBB->size() == 1 &&
2499  "Only the branch instruction should remain");
2500  return &FI;
2501 }
2502 
2504  Value *Op = FI.getArgOperand(0);
2505 
2506  // free undef -> unreachable.
2507  if (isa<UndefValue>(Op)) {
2508  // Leave a marker since we can't modify the CFG here.
2509  CreateNonTerminatorUnreachable(&FI);
2510  return eraseInstFromFunction(FI);
2511  }
2512 
2513  // If we have 'free null' delete the instruction. This can happen in stl code
2514  // when lots of inlining happens.
2515  if (isa<ConstantPointerNull>(Op))
2516  return eraseInstFromFunction(FI);
2517 
2518  // If we optimize for code size, try to move the call to free before the null
2519  // test so that simplify cfg can remove the empty block and dead code
2520  // elimination the branch. I.e., helps to turn something like:
2521  // if (foo) free(foo);
2522  // into
2523  // free(foo);
2524  if (MinimizeSize)
2525  if (Instruction *I = tryToMoveFreeBeforeNullTest(FI, DL))
2526  return I;
2527 
2528  return nullptr;
2529 }
2530 
2532  if (RI.getNumOperands() == 0) // ret void
2533  return nullptr;
2534 
2535  Value *ResultOp = RI.getOperand(0);
2536  Type *VTy = ResultOp->getType();
2537  if (!VTy->isIntegerTy())
2538  return nullptr;
2539 
2540  // There might be assume intrinsics dominating this return that completely
2541  // determine the value. If so, constant fold it.
2542  KnownBits Known = computeKnownBits(ResultOp, 0, &RI);
2543  if (Known.isConstant())
2544  RI.setOperand(0, Constant::getIntegerValue(VTy, Known.getConstant()));
2545 
2546  return nullptr;
2547 }
2548 
2550  // Change br (not X), label True, label False to: br X, label False, True
2551  Value *X = nullptr;
2552  BasicBlock *TrueDest;
2553  BasicBlock *FalseDest;
2554  if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
2555  !isa<Constant>(X)) {
2556  // Swap Destinations and condition...
2557  BI.setCondition(X);
2558  BI.swapSuccessors();
2559  return &BI;
2560  }
2561 
2562  // If the condition is irrelevant, remove the use so that other
2563  // transforms on the condition become more effective.
2564  if (BI.isConditional() && !isa<ConstantInt>(BI.getCondition()) &&
2565  BI.getSuccessor(0) == BI.getSuccessor(1)) {
2567  return &BI;
2568  }
2569 
2570  // Canonicalize, for example, icmp_ne -> icmp_eq or fcmp_one -> fcmp_oeq.
2571  CmpInst::Predicate Pred;
2572  if (match(&BI, m_Br(m_OneUse(m_Cmp(Pred, m_Value(), m_Value())), TrueDest,
2573  FalseDest)) &&
2574  !isCanonicalPredicate(Pred)) {
2575  // Swap destinations and condition.
2576  CmpInst *Cond = cast<CmpInst>(BI.getCondition());
2578  BI.swapSuccessors();
2579  Worklist.Add(Cond);
2580  return &BI;
2581  }
2582 
2583  return nullptr;
2584 }
2585 
2587  Value *Cond = SI.getCondition();
2588  Value *Op0;
2589  ConstantInt *AddRHS;
2590  if (match(Cond, m_Add(m_Value(Op0), m_ConstantInt(AddRHS)))) {
2591  // Change 'switch (X+4) case 1:' into 'switch (X) case -3'.
2592  for (auto Case : SI.cases()) {
2593  Constant *NewCase = ConstantExpr::getSub(Case.getCaseValue(), AddRHS);
2594  assert(isa<ConstantInt>(NewCase) &&
2595  "Result of expression should be constant");
2596  Case.setValue(cast<ConstantInt>(NewCase));
2597  }
2598  SI.setCondition(Op0);
2599  return &SI;
2600  }
2601 
2602  KnownBits Known = computeKnownBits(Cond, 0, &SI);
2603  unsigned LeadingKnownZeros = Known.countMinLeadingZeros();
2604  unsigned LeadingKnownOnes = Known.countMinLeadingOnes();
2605 
2606  // Compute the number of leading bits we can ignore.
2607  // TODO: A better way to determine this would use ComputeNumSignBits().
2608  for (auto &C : SI.cases()) {
2609  LeadingKnownZeros = std::min(
2610  LeadingKnownZeros, C.getCaseValue()->getValue().countLeadingZeros());
2611  LeadingKnownOnes = std::min(
2612  LeadingKnownOnes, C.getCaseValue()->getValue().countLeadingOnes());
2613  }
2614 
2615  unsigned NewWidth = Known.getBitWidth() - std::max(LeadingKnownZeros, LeadingKnownOnes);
2616 
2617  // Shrink the condition operand if the new type is smaller than the old type.
2618  // But do not shrink to a non-standard type, because backend can't generate
2619  // good code for that yet.
2620  // TODO: We can make it aggressive again after fixing PR39569.
2621  if (NewWidth > 0 && NewWidth < Known.getBitWidth() &&
2622  shouldChangeType(Known.getBitWidth(), NewWidth)) {
2623  IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);
2624  Builder.SetInsertPoint(&SI);
2625  Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc");
2626  SI.setCondition(NewCond);
2627 
2628  for (auto Case : SI.cases()) {
2629  APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);
2630  Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));
2631  }
2632  return &SI;
2633  }
2634 
2635  return nullptr;
2636 }
2637 
2639  Value *Agg = EV.getAggregateOperand();
2640 
2641  if (!EV.hasIndices())
2642  return replaceInstUsesWith(EV, Agg);
2643 
2644  if (Value *V = SimplifyExtractValueInst(Agg, EV.getIndices(),
2645  SQ.getWithInstruction(&EV)))
2646  return replaceInstUsesWith(EV, V);
2647 
2648  if (InsertValueInst *IV = dyn_cast<InsertValueInst>(Agg)) {
2649  // We're extracting from an insertvalue instruction, compare the indices
2650  const unsigned *exti, *exte, *insi, *inse;
2651  for (exti = EV.idx_begin(), insi = IV->idx_begin(),
2652  exte = EV.idx_end(), inse = IV->idx_end();
2653  exti != exte && insi != inse;
2654  ++exti, ++insi) {
2655  if (*insi != *exti)
2656  // The insert and extract both reference distinctly different elements.
2657  // This means the extract is not influenced by the insert, and we can
2658  // replace the aggregate operand of the extract with the aggregate
2659  // operand of the insert. i.e., replace
2660  // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1
2661  // %E = extractvalue { i32, { i32 } } %I, 0
2662  // with
2663  // %E = extractvalue { i32, { i32 } } %A, 0
2664  return ExtractValueInst::Create(IV->getAggregateOperand(),
2665  EV.getIndices());
2666  }
2667  if (exti == exte && insi == inse)
2668  // Both iterators are at the end: Index lists are identical. Replace
2669  // %B = insertvalue { i32, { i32 } } %A, i32 42, 1, 0
2670  // %C = extractvalue { i32, { i32 } } %B, 1, 0
2671  // with "i32 42"
2672  return replaceInstUsesWith(EV, IV->getInsertedValueOperand());
2673  if (exti == exte) {
2674  // The extract list is a prefix of the insert list. i.e. replace
2675  // %I = insertvalue { i32, { i32 } } %A, i32 42, 1, 0
2676  // %E = extractvalue { i32, { i32 } } %I, 1
2677  // with
2678  // %X = extractvalue { i32, { i32 } } %A, 1
2679  // %E = insertvalue { i32 } %X, i32 42, 0
2680  // by switching the order of the insert and extract (though the
2681  // insertvalue should be left in, since it may have other uses).
2682  Value *NewEV = Builder.CreateExtractValue(IV->getAggregateOperand(),
2683  EV.getIndices());
2684  return InsertValueInst::Create(NewEV, IV->getInsertedValueOperand(),
2685  makeArrayRef(insi, inse));
2686  }
2687  if (insi == inse)
2688  // The insert list is a prefix of the extract list
2689  // We can simply remove the common indices from the extract and make it
2690  // operate on the inserted value instead of the insertvalue result.
2691  // i.e., replace
2692  // %I = insertvalue { i32, { i32 } } %A, { i32 } { i32 42 }, 1
2693  // %E = extractvalue { i32, { i32 } } %I, 1, 0
2694  // with
2695  // %E extractvalue { i32 } { i32 42 }, 0
2696  return ExtractValueInst::Create(IV->getInsertedValueOperand(),
2697  makeArrayRef(exti, exte));
2698  }
2699  if (WithOverflowInst *WO = dyn_cast<WithOverflowInst>(Agg)) {
2700  // We're extracting from an overflow intrinsic, see if we're the only user,
2701  // which allows us to simplify multiple result intrinsics to simpler
2702  // things that just get one value.
2703  if (WO->hasOneUse()) {
2704  // Check if we're grabbing only the result of a 'with overflow' intrinsic
2705  // and replace it with a traditional binary instruction.
2706  if (*EV.idx_begin() == 0) {
2707  Instruction::BinaryOps BinOp = WO->getBinaryOp();
2708  Value *LHS = WO->getLHS(), *RHS = WO->getRHS();
2709  replaceInstUsesWith(*WO, UndefValue::get(WO->getType()));
2710  eraseInstFromFunction(*WO);
2711  return BinaryOperator::Create(BinOp, LHS, RHS);
2712  }
2713 
2714  // If the normal result of the add is dead, and the RHS is a constant,
2715  // we can transform this into a range comparison.
2716  // overflow = uadd a, -4 --> overflow = icmp ugt a, 3
2717  if (WO->getIntrinsicID() == Intrinsic::uadd_with_overflow)
2718  if (ConstantInt *CI = dyn_cast<ConstantInt>(WO->getRHS()))
2719  return new ICmpInst(ICmpInst::ICMP_UGT, WO->getLHS(),
2720  ConstantExpr::getNot(CI));
2721  }
2722  }
2723  if (LoadInst *L = dyn_cast<LoadInst>(Agg))
2724  // If the (non-volatile) load only has one use, we can rewrite this to a
2725  // load from a GEP. This reduces the size of the load. If a load is used
2726  // only by extractvalue instructions then this either must have been
2727  // optimized before, or it is a struct with padding, in which case we
2728  // don't want to do the transformation as it loses padding knowledge.
2729  if (L->isSimple() && L->hasOneUse()) {
2730  // extractvalue has integer indices, getelementptr has Value*s. Convert.
2731  SmallVector<Value*, 4> Indices;
2732  // Prefix an i32 0 since we need the first element.
2733  Indices.push_back(Builder.getInt32(0));
2734  for (ExtractValueInst::idx_iterator I = EV.idx_begin(), E = EV.idx_end();
2735  I != E; ++I)
2736  Indices.push_back(Builder.getInt32(*I));
2737 
2738  // We need to insert these at the location of the old load, not at that of
2739  // the extractvalue.
2740  Builder.SetInsertPoint(L);
2741  Value *GEP = Builder.CreateInBoundsGEP(L->getType(),
2742  L->getPointerOperand(), Indices);
2743  Instruction *NL = Builder.CreateLoad(EV.getType(), GEP);
2744  // Whatever aliasing information we had for the orignal load must also
2745  // hold for the smaller load, so propagate the annotations.
2746  AAMDNodes Nodes;
2747  L->getAAMetadata(Nodes);
2748  NL->setAAMetadata(Nodes);
2749  // Returning the load directly will cause the main loop to insert it in
2750  // the wrong spot, so use replaceInstUsesWith().
2751  return replaceInstUsesWith(EV, NL);
2752  }
2753  // We could simplify extracts from other values. Note that nested extracts may
2754  // already be simplified implicitly by the above: extract (extract (insert) )
2755  // will be translated into extract ( insert ( extract ) ) first and then just
2756  // the value inserted, if appropriate. Similarly for extracts from single-use
2757  // loads: extract (extract (load)) will be translated to extract (load (gep))
2758  // and if again single-use then via load (gep (gep)) to load (gep).
2759  // However, double extracts from e.g. function arguments or return values
2760  // aren't handled yet.
2761  return nullptr;
2762 }
2763 
2764 /// Return 'true' if the given typeinfo will match anything.
2765 static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo) {
2766  switch (Personality) {
2767  case EHPersonality::GNU_C:
2769  case EHPersonality::Rust:
2770  // The GCC C EH and Rust personality only exists to support cleanups, so
2771  // it's not clear what the semantics of catch clauses are.
2772  return false;
2774  return false;
2776  // While __gnat_all_others_value will match any Ada exception, it doesn't
2777  // match foreign exceptions (or didn't, before gcc-4.7).
2778  return false;
2787  return TypeInfo->isNullValue();
2788  }
2789  llvm_unreachable("invalid enum");
2790 }
2791 
2792 static bool shorter_filter(const Value *LHS, const Value *RHS) {
2793  return
2794  cast<ArrayType>(LHS->getType())->getNumElements()
2795  <
2796  cast<ArrayType>(RHS->getType())->getNumElements();
2797 }
2798 
2800  // The logic here should be correct for any real-world personality function.
2801  // However if that turns out not to be true, the offending logic can always
2802  // be conditioned on the personality function, like the catch-all logic is.
2803  EHPersonality Personality =
2805 
2806  // Simplify the list of clauses, eg by removing repeated catch clauses
2807  // (these are often created by inlining).
2808  bool MakeNewInstruction = false; // If true, recreate using the following:
2809  SmallVector<Constant *, 16> NewClauses; // - Clauses for the new instruction;
2810  bool CleanupFlag = LI.isCleanup(); // - The new instruction is a cleanup.
2811 
2812  SmallPtrSet<Value *, 16> AlreadyCaught; // Typeinfos known caught already.
2813  for (unsigned i = 0, e = LI.getNumClauses(); i != e; ++i) {
2814  bool isLastClause = i + 1 == e;
2815  if (LI.isCatch(i)) {
2816  // A catch clause.
2817  Constant *CatchClause = LI.getClause(i);
2818  Constant *TypeInfo = CatchClause->stripPointerCasts();
2819 
2820  // If we already saw this clause, there is no point in having a second
2821  // copy of it.
2822  if (AlreadyCaught.insert(TypeInfo).second) {
2823  // This catch clause was not already seen.
2824  NewClauses.push_back(CatchClause);
2825  } else {
2826  // Repeated catch clause - drop the redundant copy.
2827  MakeNewInstruction = true;
2828  }
2829 
2830  // If this is a catch-all then there is no point in keeping any following
2831  // clauses or marking the landingpad as having a cleanup.
2832  if (isCatchAll(Personality, TypeInfo)) {
2833  if (!isLastClause)
2834  MakeNewInstruction = true;
2835  CleanupFlag = false;
2836  break;
2837  }
2838  } else {
2839  // A filter clause. If any of the filter elements were already caught
2840  // then they can be dropped from the filter. It is tempting to try to
2841  // exploit the filter further by saying that any typeinfo that does not
2842  // occur in the filter can't be caught later (and thus can be dropped).
2843  // However this would be wrong, since typeinfos can match without being
2844  // equal (for example if one represents a C++ class, and the other some
2845  // class derived from it).
2846  assert(LI.isFilter(i) && "Unsupported landingpad clause!");
2847  Constant *FilterClause = LI.getClause(i);
2848  ArrayType *FilterType = cast<ArrayType>(FilterClause->getType());
2849  unsigned NumTypeInfos = FilterType->getNumElements();
2850 
2851  // An empty filter catches everything, so there is no point in keeping any
2852  // following clauses or marking the landingpad as having a cleanup. By
2853  // dealing with this case here the following code is made a bit simpler.
2854  if (!NumTypeInfos) {
2855  NewClauses.push_back(FilterClause);
2856  if (!isLastClause)
2857  MakeNewInstruction = true;
2858  CleanupFlag = false;
2859  break;
2860  }
2861 
2862  bool MakeNewFilter = false; // If true, make a new filter.
2863  SmallVector<Constant *, 16> NewFilterElts; // New elements.
2864  if (isa<ConstantAggregateZero>(FilterClause)) {
2865  // Not an empty filter - it contains at least one null typeinfo.
2866  assert(NumTypeInfos > 0 && "Should have handled empty filter already!");
2867  Constant *TypeInfo =
2868  Constant::getNullValue(FilterType->getElementType());
2869  // If this typeinfo is a catch-all then the filter can never match.
2870  if (isCatchAll(Personality, TypeInfo)) {
2871  // Throw the filter away.
2872  MakeNewInstruction = true;
2873  continue;
2874  }
2875 
2876  // There is no point in having multiple copies of this typeinfo, so
2877  // discard all but the first copy if there is more than one.
2878  NewFilterElts.push_back(TypeInfo);
2879  if (NumTypeInfos > 1)
2880  MakeNewFilter = true;
2881  } else {
2882  ConstantArray *Filter = cast<ConstantArray>(FilterClause);
2883  SmallPtrSet<Value *, 16> SeenInFilter; // For uniquing the elements.
2884  NewFilterElts.reserve(NumTypeInfos);
2885 
2886  // Remove any filter elements that were already caught or that already
2887  // occurred in the filter. While there, see if any of the elements are
2888  // catch-alls. If so, the filter can be discarded.
2889  bool SawCatchAll = false;
2890  for (unsigned j = 0; j != NumTypeInfos; ++j) {
2891  Constant *Elt = Filter->getOperand(j);
2892  Constant *TypeInfo = Elt->stripPointerCasts();
2893  if (isCatchAll(Personality, TypeInfo)) {
2894  // This element is a catch-all. Bail out, noting this fact.
2895  SawCatchAll = true;
2896  break;
2897  }
2898 
2899  // Even if we've seen a type in a catch clause, we don't want to
2900  // remove it from the filter. An unexpected type handler may be
2901  // set up for a call site which throws an exception of the same
2902  // type caught. In order for the exception thrown by the unexpected
2903  // handler to propagate correctly, the filter must be correctly
2904  // described for the call site.
2905  //
2906  // Example:
2907  //
2908  // void unexpected() { throw 1;}
2909  // void foo() throw (int) {
2910  // std::set_unexpected(unexpected);
2911  // try {
2912  // throw 2.0;
2913  // } catch (int i) {}
2914  // }
2915 
2916  // There is no point in having multiple copies of the same typeinfo in
2917  // a filter, so only add it if we didn't already.
2918  if (SeenInFilter.insert(TypeInfo).second)
2919  NewFilterElts.push_back(cast<Constant>(Elt));
2920  }
2921  // A filter containing a catch-all cannot match anything by definition.
2922  if (SawCatchAll) {
2923  // Throw the filter away.
2924  MakeNewInstruction = true;
2925  continue;
2926  }
2927 
2928  // If we dropped something from the filter, make a new one.
2929  if (NewFilterElts.size() < NumTypeInfos)
2930  MakeNewFilter = true;
2931  }
2932  if (MakeNewFilter) {
2933  FilterType = ArrayType::get(FilterType->getElementType(),
2934  NewFilterElts.size());
2935  FilterClause = ConstantArray::get(FilterType, NewFilterElts);
2936  MakeNewInstruction = true;
2937  }
2938 
2939  NewClauses.push_back(FilterClause);
2940 
2941  // If the new filter is empty then it will catch everything so there is
2942  // no point in keeping any following clauses or marking the landingpad
2943  // as having a cleanup. The case of the original filter being empty was
2944  // already handled above.
2945  if (MakeNewFilter && !NewFilterElts.size()) {
2946  assert(MakeNewInstruction && "New filter but not a new instruction!");
2947  CleanupFlag = false;
2948  break;
2949  }
2950  }
2951  }
2952 
2953  // If several filters occur in a row then reorder them so that the shortest
2954  // filters come first (those with the smallest number of elements). This is
2955  // advantageous because shorter filters are more likely to match, speeding up
2956  // unwinding, but mostly because it increases the effectiveness of the other
2957  // filter optimizations below.
2958  for (unsigned i = 0, e = NewClauses.size(); i + 1 < e; ) {
2959  unsigned j;
2960  // Find the maximal 'j' s.t. the range [i, j) consists entirely of filters.
2961  for (j = i; j != e; ++j)
2962  if (!isa<ArrayType>(NewClauses[j]->getType()))
2963  break;
2964 
2965  // Check whether the filters are already sorted by length. We need to know
2966  // if sorting them is actually going to do anything so that we only make a
2967  // new landingpad instruction if it does.
2968  for (unsigned k = i; k + 1 < j; ++k)
2969  if (shorter_filter(NewClauses[k+1], NewClauses[k])) {
2970  // Not sorted, so sort the filters now. Doing an unstable sort would be
2971  // correct too but reordering filters pointlessly might confuse users.
2972  std::stable_sort(NewClauses.begin() + i, NewClauses.begin() + j,
2973  shorter_filter);
2974  MakeNewInstruction = true;
2975  break;
2976  }
2977 
2978  // Look for the next batch of filters.
2979  i = j + 1;
2980  }
2981 
2982  // If typeinfos matched if and only if equal, then the elements of a filter L
2983  // that occurs later than a filter F could be replaced by the intersection of
2984  // the elements of F and L. In reality two typeinfos can match without being
2985  // equal (for example if one represents a C++ class, and the other some class
2986  // derived from it) so it would be wrong to perform this transform in general.
2987  // However the transform is correct and useful if F is a subset of L. In that
2988  // case L can be replaced by F, and thus removed altogether since repeating a
2989  // filter is pointless. So here we look at all pairs of filters F and L where
2990  // L follows F in the list of clauses, and remove L if every element of F is
2991  // an element of L. This can occur when inlining C++ functions with exception
2992  // specifications.
2993  for (unsigned i = 0; i + 1 < NewClauses.size(); ++i) {
2994  // Examine each filter in turn.
2995  Value *Filter = NewClauses[i];
2996  ArrayType *FTy = dyn_cast<ArrayType>(Filter->getType());
2997  if (!FTy)
2998  // Not a filter - skip it.
2999  continue;
3000  unsigned FElts = FTy->getNumElements();
3001  // Examine each filter following this one. Doing this backwards means that
3002  // we don't have to worry about filters disappearing under us when removed.
3003  for (unsigned j = NewClauses.size() - 1; j != i; --j) {
3004  Value *LFilter = NewClauses[j];
3005  ArrayType *LTy = dyn_cast<ArrayType>(LFilter->getType());
3006  if (!LTy)
3007  // Not a filter - skip it.
3008  continue;
3009  // If Filter is a subset of LFilter, i.e. every element of Filter is also
3010  // an element of LFilter, then discard LFilter.
3011  SmallVectorImpl<Constant *>::iterator J = NewClauses.begin() + j;
3012  // If Filter is empty then it is a subset of LFilter.
3013  if (!FElts) {
3014  // Discard LFilter.
3015  NewClauses.erase(J);
3016  MakeNewInstruction = true;
3017  // Move on to the next filter.
3018  continue;
3019  }
3020  unsigned LElts = LTy->getNumElements();
3021  // If Filter is longer than LFilter then it cannot be a subset of it.
3022  if (FElts > LElts)
3023  // Move on to the next filter.
3024  continue;
3025  // At this point we know that LFilter has at least one element.
3026  if (isa<ConstantAggregateZero>(LFilter)) { // LFilter only contains zeros.
3027  // Filter is a subset of LFilter iff Filter contains only zeros (as we
3028  // already know that Filter is not longer than LFilter).
3029  if (isa<ConstantAggregateZero>(Filter)) {
3030  assert(FElts <= LElts && "Should have handled this case earlier!");
3031  // Discard LFilter.
3032  NewClauses.erase(J);
3033  MakeNewInstruction = true;
3034  }
3035  // Move on to the next filter.
3036  continue;
3037  }
3038  ConstantArray *LArray = cast<ConstantArray>(LFilter);
3039  if (isa<ConstantAggregateZero>(Filter)) { // Filter only contains zeros.
3040  // Since Filter is non-empty and contains only zeros, it is a subset of
3041  // LFilter iff LFilter contains a zero.
3042  assert(FElts > 0 && "Should have eliminated the empty filter earlier!");
3043  for (unsigned l = 0; l != LElts; ++l)
3044  if (LArray->getOperand(l)->isNullValue()) {
3045  // LFilter contains a zero - discard it.
3046  NewClauses.erase(J);
3047  MakeNewInstruction = true;
3048  break;
3049  }
3050  // Move on to the next filter.
3051  continue;
3052  }
3053  // At this point we know that both filters are ConstantArrays. Loop over
3054  // operands to see whether every element of Filter is also an element of
3055  // LFilter. Since filters tend to be short this is probably faster than
3056  // using a method that scales nicely.
3057  ConstantArray *FArray = cast<ConstantArray>(Filter);
3058  bool AllFound = true;
3059  for (unsigned f = 0; f != FElts; ++f) {
3060  Value *FTypeInfo = FArray->getOperand(f)->stripPointerCasts();
3061  AllFound = false;
3062  for (unsigned l = 0; l != LElts; ++l) {
3063  Value *LTypeInfo = LArray->getOperand(l)->stripPointerCasts();
3064  if (LTypeInfo == FTypeInfo) {
3065  AllFound = true;
3066  break;
3067  }
3068  }
3069  if (!AllFound)
3070  break;
3071  }
3072  if (AllFound) {
3073  // Discard LFilter.
3074  NewClauses.erase(J);
3075  MakeNewInstruction = true;
3076  }
3077  // Move on to the next filter.
3078  }
3079  }
3080 
3081  // If we changed any of the clauses, replace the old landingpad instruction
3082  // with a new one.
3083  if (MakeNewInstruction) {
3085  NewClauses.size());
3086  for (unsigned i = 0, e = NewClauses.size(); i != e; ++i)
3087  NLI->addClause(NewClauses[i]);
3088  // A landing pad with no clauses must have the cleanup flag set. It is
3089  // theoretically possible, though highly unlikely, that we eliminated all
3090  // clauses. If so, force the cleanup flag to true.
3091  if (NewClauses.empty())
3092  CleanupFlag = true;
3093  NLI->setCleanup(CleanupFlag);
3094  return NLI;
3095  }
3096 
3097  // Even if none of the clauses changed, we may nonetheless have understood
3098  // that the cleanup flag is pointless. Clear it if so.
3099  if (LI.isCleanup() != CleanupFlag) {
3100  assert(!CleanupFlag && "Adding a cleanup, not removing one?!");
3101  LI.setCleanup(CleanupFlag);
3102  return &LI;
3103  }
3104 
3105  return nullptr;
3106 }
3107 
3108 /// Try to move the specified instruction from its current block into the
3109 /// beginning of DestBlock, which can only happen if it's safe to move the
3110 /// instruction past all of the instructions between it and the end of its
3111 /// block.
3112 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
3113  assert(I->hasOneUse() && "Invariants didn't hold!");
3114  BasicBlock *SrcBlock = I->getParent();
3115 
3116  // Cannot move control-flow-involving, volatile loads, vaarg, etc.
3117  if (isa<PHINode>(I) || I->isEHPad() || I->mayHaveSideEffects() ||
3118  I->isTerminator())
3119  return false;
3120 
3121  // Do not sink static or dynamic alloca instructions. Static allocas must
3122  // remain in the entry block, and dynamic allocas must not be sunk in between
3123  // a stacksave / stackrestore pair, which would incorrectly shorten its
3124  // lifetime.
3125  if (isa<AllocaInst>(I))
3126  return false;
3127 
3128  // Do not sink into catchswitch blocks.
3129  if (isa<CatchSwitchInst>(DestBlock->getTerminator()))
3130  return false;
3131 
3132  // Do not sink convergent call instructions.
3133  if (auto *CI = dyn_cast<CallInst>(I)) {
3134  if (CI->isConvergent())
3135  return false;
3136  }
3137  // We can only sink load instructions if there is nothing between the load and
3138  // the end of block that could change the value.
3139  if (I->mayReadFromMemory()) {
3140  for (BasicBlock::iterator Scan = I->getIterator(),
3141  E = I->getParent()->end();
3142  Scan != E; ++Scan)
3143  if (Scan->mayWriteToMemory())
3144  return false;
3145  }
3146  BasicBlock::iterator InsertPos = DestBlock->getFirstInsertionPt();
3147  I->moveBefore(&*InsertPos);
3148  ++NumSunkInst;
3149 
3150  // Also sink all related debug uses from the source basic block. Otherwise we
3151  // get debug use before the def. Attempt to salvage debug uses first, to
3152  // maximise the range variables have location for. If we cannot salvage, then
3153  // mark the location undef: we know it was supposed to receive a new location
3154  // here, but that computation has been sunk.
3156  findDbgUsers(DbgUsers, I);
3157  for (auto *DII : reverse(DbgUsers)) {
3158  if (DII->getParent() == SrcBlock) {
3159  // dbg.value is in the same basic block as the sunk inst, see if we can
3160  // salvage it. Clone a new copy of the instruction: on success we need
3161  // both salvaged and unsalvaged copies.
3163  cast<DbgVariableIntrinsic>(DII->clone())};
3164 
3165  if (!salvageDebugInfoForDbgValues(*I, TmpUser)) {
3166  // We are unable to salvage: sink the cloned dbg.value, and mark the
3167  // original as undef, terminating any earlier variable location.
3168  LLVM_DEBUG(dbgs() << "SINK: " << *DII << '\n');
3169  TmpUser[0]->insertBefore(&*InsertPos);
3171  DII->setOperand(0, MetadataAsValue::get(DII->getContext(),
3172  ValueAsMetadata::get(Undef)));
3173  } else {
3174  // We successfully salvaged: place the salvaged dbg.value in the
3175  // original location, and move the unmodified dbg.value to sink with
3176  // the sunk inst.
3177  TmpUser[0]->insertBefore(DII);
3178  DII->moveBefore(&*InsertPos);
3179  }
3180  }
3181  }
3182  return true;
3183 }
3184 
3186  while (!Worklist.isEmpty()) {
3187  Instruction *I = Worklist.RemoveOne();
3188  if (I == nullptr) continue; // skip null values.
3189 
3190  // Check to see if we can DCE the instruction.
3191  if (isInstructionTriviallyDead(I, &TLI)) {
3192  LLVM_DEBUG(dbgs() << "IC: DCE: " << *I << '\n');
3193  eraseInstFromFunction(*I);
3194  ++NumDeadInst;
3195  MadeIRChange = true;
3196  continue;
3197  }
3198 
3199  if (!DebugCounter::shouldExecute(VisitCounter))
3200  continue;
3201 
3202  // Instruction isn't dead, see if we can constant propagate it.
3203  if (!I->use_empty() &&
3204  (I->getNumOperands() == 0 || isa<Constant>(I->getOperand(0)))) {
3205  if (Constant *C = ConstantFoldInstruction(I, DL, &TLI)) {
3206  LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *I
3207  << '\n');
3208 
3209  // Add operands to the worklist.
3210  replaceInstUsesWith(*I, C);
3211  ++NumConstProp;
3212  if (isInstructionTriviallyDead(I, &TLI))
3213  eraseInstFromFunction(*I);
3214  MadeIRChange = true;
3215  continue;
3216  }
3217  }
3218 
3219  // In general, it is possible for computeKnownBits to determine all bits in
3220  // a value even when the operands are not all constants.
3221  Type *Ty = I->getType();
3222  if (ExpensiveCombines && !I->use_empty() && Ty->isIntOrIntVectorTy()) {
3223  KnownBits Known = computeKnownBits(I, /*Depth*/0, I);
3224  if (Known.isConstant()) {
3225  Constant *C = ConstantInt::get(Ty, Known.getConstant());
3226  LLVM_DEBUG(dbgs() << "IC: ConstFold (all bits known) to: " << *C
3227  << " from: " << *I << '\n');
3228 
3229  // Add operands to the worklist.
3230  replaceInstUsesWith(*I, C);
3231  ++NumConstProp;
3232  if (isInstructionTriviallyDead(I, &TLI))
3233  eraseInstFromFunction(*I);
3234  MadeIRChange = true;
3235  continue;
3236  }
3237  }
3238 
3239  // See if we can trivially sink this instruction to a successor basic block.
3240  if (EnableCodeSinking && I->hasOneUse()) {
3241  BasicBlock *BB = I->getParent();
3242  Instruction *UserInst = cast<Instruction>(*I->user_begin());
3243  BasicBlock *UserParent;
3244 
3245  // Get the block the use occurs in.
3246  if (PHINode *PN = dyn_cast<PHINode>(UserInst))
3247  UserParent = PN->getIncomingBlock(*I->use_begin());
3248  else
3249  UserParent = UserInst->getParent();
3250 
3251  if (UserParent != BB) {
3252  bool UserIsSuccessor = false;
3253  // See if the user is one of our successors.
3254  for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
3255  if (*SI == UserParent) {
3256  UserIsSuccessor = true;
3257  break;
3258  }
3259 
3260  // If the user is one of our immediate successors, and if that successor
3261  // only has us as a predecessors (we'd have to split the critical edge
3262  // otherwise), we can keep going.
3263  if (UserIsSuccessor && UserParent->getUniquePredecessor()) {
3264  // Okay, the CFG is simple enough, try to sink this instruction.
3265  if (TryToSinkInstruction(I, UserParent)) {
3266  LLVM_DEBUG(dbgs() << "IC: Sink: " << *I << '\n');
3267  MadeIRChange = true;
3268  // We'll add uses of the sunk instruction below, but since sinking
3269  // can expose opportunities for it's *operands* add them to the
3270  // worklist
3271  for (Use &U : I->operands())
3272  if (Instruction *OpI = dyn_cast<Instruction>(U.get()))
3273  Worklist.Add(OpI);
3274  }
3275  }
3276  }
3277  }
3278 
3279  // Now that we have an instruction, try combining it to simplify it.
3280  Builder.SetInsertPoint(I);
3281  Builder.SetCurrentDebugLocation(I->getDebugLoc());
3282 
3283 #ifndef NDEBUG
3284  std::string OrigI;
3285 #endif
3286  LLVM_DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str(););
3287  LLVM_DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n');
3288 
3289  if (Instruction *Result = visit(*I)) {
3290  ++NumCombined;
3291  // Should we replace the old instruction with a new one?
3292  if (Result != I) {
3293  LLVM_DEBUG(dbgs() << "IC: Old = " << *I << '\n'
3294  << " New = " << *Result << '\n');
3295 
3296  if (I->getDebugLoc())
3297  Result->setDebugLoc(I->getDebugLoc());
3298  // Everything uses the new instruction now.
3299  I->replaceAllUsesWith(Result);
3300 
3301  // Move the name to the new instruction first.
3302  Result->takeName(I);
3303 
3304  // Push the new instruction and any users onto the worklist.
3305  Worklist.AddUsersToWorkList(*Result);
3306  Worklist.Add(Result);
3307 
3308  // Insert the new instruction into the basic block...
3309  BasicBlock *InstParent = I->getParent();
3310  BasicBlock::iterator InsertPos = I->getIterator();
3311 
3312  // If we replace a PHI with something that isn't a PHI, fix up the
3313  // insertion point.
3314  if (!isa<PHINode>(Result) && isa<PHINode>(InsertPos))
3315  InsertPos = InstParent->getFirstInsertionPt();
3316 
3317  InstParent->getInstList().insert(InsertPos, Result);
3318 
3319  eraseInstFromFunction(*I);
3320  } else {
3321  LLVM_DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n'
3322  << " New = " << *I << '\n');
3323 
3324  // If the instruction was modified, it's possible that it is now dead.
3325  // if so, remove it.
3326  if (isInstructionTriviallyDead(I, &TLI)) {
3327  eraseInstFromFunction(*I);
3328  } else {
3329  Worklist.AddUsersToWorkList(*I);
3330  Worklist.Add(I);
3331  }
3332  }
3333  MadeIRChange = true;
3334  }
3335  }
3336 
3337  Worklist.Zap();
3338  return MadeIRChange;
3339 }
3340 
3341 /// Walk the function in depth-first order, adding all reachable code to the
3342 /// worklist.
3343 ///
3344 /// This has a couple of tricks to make the code faster and more powerful. In
3345 /// particular, we constant fold and DCE instructions as we go, to avoid adding
3346 /// them to the worklist (this significantly speeds up instcombine on code where
3347 /// many instructions are dead or constant). Additionally, if we find a branch
3348 /// whose condition is a known constant, we only visit the reachable successors.
3351  InstCombineWorklist &ICWorklist,
3352  const TargetLibraryInfo *TLI) {
3353  bool MadeIRChange = false;
3355  Worklist.push_back(BB);
3356 
3357  SmallVector<Instruction*, 128> InstrsForInstCombineWorklist;
3358  DenseMap<Constant *, Constant *> FoldedConstants;
3359 
3360  do {
3361  BB = Worklist.pop_back_val();
3362 
3363  // We have now visited this block! If we've already been here, ignore it.
3364  if (!Visited.insert(BB).second)
3365  continue;
3366 
3367  for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
3368  Instruction *Inst = &*BBI++;
3369 
3370  // DCE instruction if trivially dead.
3371  if (isInstructionTriviallyDead(Inst, TLI)) {
3372  ++NumDeadInst;
3373  LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
3374  if (!salvageDebugInfo(*Inst))
3376  Inst->eraseFromParent();
3377  MadeIRChange = true;
3378  continue;
3379  }
3380 
3381  // ConstantProp instruction if trivially constant.
3382  if (!Inst->use_empty() &&
3383  (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
3384  if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI)) {
3385  LLVM_DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: " << *Inst
3386  << '\n');
3387  Inst->replaceAllUsesWith(C);
3388  ++NumConstProp;
3389  if (isInstructionTriviallyDead(Inst, TLI))
3390  Inst->eraseFromParent();
3391  MadeIRChange = true;
3392  continue;
3393  }
3394 
3395  // See if we can constant fold its operands.
3396  for (Use &U : Inst->operands()) {
3397  if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))
3398  continue;
3399 
3400  auto *C = cast<Constant>(U);
3401  Constant *&FoldRes = FoldedConstants[C];
3402  if (!FoldRes)
3403  FoldRes = ConstantFoldConstant(C, DL, TLI);
3404  if (!FoldRes)
3405  FoldRes = C;
3406 
3407  if (FoldRes != C) {
3408  LLVM_DEBUG(dbgs() << "IC: ConstFold operand of: " << *Inst
3409  << "\n Old = " << *C
3410  << "\n New = " << *FoldRes << '\n');
3411  U = FoldRes;
3412  MadeIRChange = true;
3413  }
3414  }
3415 
3416  // Skip processing debug intrinsics in InstCombine. Processing these call instructions
3417  // consumes non-trivial amount of time and provides no value for the optimization.
3418  if (!isa<DbgInfoIntrinsic>(Inst))
3419  InstrsForInstCombineWorklist.push_back(Inst);
3420  }
3421 
3422  // Recursively visit successors. If this is a branch or switch on a
3423  // constant, only visit the reachable successor.
3424  Instruction *TI = BB->getTerminator();
3425  if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
3426  if (BI->isConditional() && isa<ConstantInt>(BI->getCondition())) {
3427  bool CondVal = cast<ConstantInt>(BI->getCondition())->getZExtValue();
3428  BasicBlock *ReachableBB = BI->getSuccessor(!CondVal);
3429  Worklist.push_back(ReachableBB);
3430  continue;
3431  }
3432  } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
3433  if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
3434  Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor());
3435  continue;
3436  }
3437  }
3438 
3439  for (BasicBlock *SuccBB : successors(TI))
3440  Worklist.push_back(SuccBB);
3441  } while (!Worklist.empty());
3442 
3443  // Once we've found all of the instructions to add to instcombine's worklist,
3444  // add them in reverse order. This way instcombine will visit from the top
3445  // of the function down. This jives well with the way that it adds all uses
3446  // of instructions to the worklist after doing a transformation, thus avoiding
3447  // some N^2 behavior in pathological cases.
3448  ICWorklist.AddInitialGroup(InstrsForInstCombineWorklist);
3449 
3450  return MadeIRChange;
3451 }
3452 
3453 /// Populate the IC worklist from a function, and prune any dead basic
3454 /// blocks discovered in the process.
3455 ///
3456 /// This also does basic constant propagation and other forward fixing to make
3457 /// the combiner itself run much faster.
3459  TargetLibraryInfo *TLI,
3460  InstCombineWorklist &ICWorklist) {
3461  bool MadeIRChange = false;
3462 
3463  // Do a depth-first traversal of the function, populate the worklist with
3464  // the reachable instructions. Ignore blocks that are not reachable. Keep
3465  // track of which blocks we visit.
3467  MadeIRChange |=
3468  AddReachableCodeToWorklist(&F.front(), DL, Visited, ICWorklist, TLI);
3469 
3470  // Do a quick scan over the function. If we find any blocks that are
3471  // unreachable, remove any instructions inside of them. This prevents
3472  // the instcombine code from having to deal with some bad special cases.
3473  for (BasicBlock &BB : F) {
3474  if (Visited.count(&BB))
3475  continue;
3476 
3477  unsigned NumDeadInstInBB = removeAllNonTerminatorAndEHPadInstructions(&BB);
3478  MadeIRChange |= NumDeadInstInBB > 0;
3479  NumDeadInst += NumDeadInstInBB;
3480  }
3481 
3482  return MadeIRChange;
3483 }
3484 
3486  Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA,
3489  ProfileSummaryInfo *PSI, bool ExpensiveCombines = true,
3490  LoopInfo *LI = nullptr) {
3491  auto &DL = F.getParent()->getDataLayout();
3492  ExpensiveCombines |= EnableExpensiveCombines;
3493 
3494  /// Builder - This is an IRBuilder that automatically inserts new
3495  /// instructions into the worklist when they are created.
3497  F.getContext(), TargetFolder(DL),
3498  IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {
3499  Worklist.Add(I);
3500  if (match(I, m_Intrinsic<Intrinsic::assume>()))
3501  AC.registerAssumption(cast<CallInst>(I));
3502  }));
3503 
3504  // Lower dbg.declare intrinsics otherwise their value may be clobbered
3505  // by instcombiner.
3506  bool MadeIRChange = false;
3508  MadeIRChange = LowerDbgDeclare(F);
3509 
3510  // Iterate while there is work to do.
3511  int Iteration = 0;
3512  while (true) {
3513  ++Iteration;
3514  LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
3515  << F.getName() << "\n");
3516 
3517  MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
3518 
3519  InstCombiner IC(Worklist, Builder, F.hasMinSize(), ExpensiveCombines, AA,
3520  AC, TLI, DT, ORE, BFI, PSI, DL, LI);
3522 
3523  if (!IC.run())
3524  break;
3525  }
3526 
3527  return MadeIRChange || Iteration > 1;
3528 }
3529 
3532  auto &AC = AM.getResult<AssumptionAnalysis>(F);
3533  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
3534  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
3536 
3537  auto *LI = AM.getCachedResult<LoopAnalysis>(F);
3538 
3539  auto *AA = &AM.getResult<AAManager>(F);
3540  const ModuleAnalysisManager &MAM =
3542  ProfileSummaryInfo *PSI =
3543  MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
3544  auto *BFI = (PSI && PSI->hasProfileSummary()) ?
3545  &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
3546 
3547  if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE,
3548  BFI, PSI, ExpensiveCombines, LI))
3549  // No changes, all analyses are preserved.
3550  return PreservedAnalyses::all();
3551 
3552  // Mark all the analyses that instcombine updates as preserved.
3553  PreservedAnalyses PA;
3554  PA.preserveSet<CFGAnalyses>();
3555  PA.preserve<AAManager>();
3556  PA.preserve<BasicAA>();
3557  PA.preserve<GlobalsAA>();
3558  return PA;
3559 }
3560 
3562  AU.setPreservesCFG();
3574 }
3575 
3577  if (skipFunction(F))
3578  return false;
3579 
3580  // Required analyses.
3581  auto AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3582  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
3583  auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
3584  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
3585  auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
3586 
3587  // Optional analyses.
3588  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
3589  auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
3590  ProfileSummaryInfo *PSI =
3591  &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
3593  (PSI && PSI->hasProfileSummary()) ?
3594  &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
3595  nullptr;
3596 
3597  return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE,
3598  BFI, PSI, ExpensiveCombines, LI);
3599 }
3600 
3602 
3604  "Combine redundant instructions", false, false)
3614  "Combine redundant instructions", false, false)
3615 
3616 // Initialization Routines
3619 }
3620 
3623 }
3624 
3626  return new InstructionCombiningPass(ExpensiveCombines);
3627 }
3628 
3631 }
Legacy wrapper pass to provide the GlobalsAAResult object.
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Type * getVectorElementType() const
Definition: Type.h:371
const NoneType None
Definition: None.h:23
A vector constant whose element type is a simple 1/2/4/8-byte integer or float/double, and whose elements are just simple data values (i.e.
Definition: Constants.h:761
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:28
uint64_t CallInst * C
Return a value (possibly void), from a function.
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...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
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...
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL, TargetLibraryInfo *TLI, InstCombineWorklist &ICWorklist)
Populate the IC worklist from a function, and prune any dead basic blocks discovered in the process...
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:594
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
void copyFastMathFlags(FastMathFlags FMF)
Convenience function for transferring all fast-math flag values to this instruction, which must be an operator which supports these flags.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:722
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:86
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
void setFastMathFlags(FastMathFlags FMF)
Convenience function for setting multiple fast-math flags on this instruction, which must be an opera...
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:172
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:78
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
This instruction extracts a struct member or array element value from an aggregate value...
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:836
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Definition: IRBuilder.h:1458
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
iterator_range< CaseIt > cases()
Iteration adapter for range-for loops.
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:561
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:693
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:375
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
void LLVMInitializeInstCombine(LLVMPassRegistryRef R)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
void swapSuccessors()
Swap the successors of this branch instruction.
static bool isAllocSiteRemovable(Instruction *AI, SmallVectorImpl< WeakTrackingVH > &Users, const TargetLibraryInfo *TLI)
This is the interface for a simple mod/ref and alias analysis over globals.
Represents an op.with.overflow intrinsic.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:264
static Value * foldOperationIntoPhiValue(BinaryOperator *I, Value *InV, InstCombiner::BuilderTy &Builder)
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock *> *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction &#39;To&#39; is reachable from &#39;From&#39;, without passing through any blocks in Ex...
Definition: CFG.cpp:211
static void ClearSubclassDataAfterReassociation(BinaryOperator &I)
Conservatively clears subclassOptionalData after a reassociation or commutation.
void push_back(const T &Elt)
Definition: SmallVector.h:211
Analysis providing profile information.
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:901
br_match m_UnconditionalBr(BasicBlock *&Succ)
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
void findDbgUsers(SmallVectorImpl< DbgVariableIntrinsic *> &DbgInsts, Value *V)
Finds the debug info intrinsics describing a value.
Definition: Local.cpp:1540
This class represents a function call, abstracting a target machine&#39;s calling convention.
This file contains the declarations for metadata subclasses.
An immutable pass that tracks lazily created AssumptionCache objects.
Value * getCondition() const
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:89
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
gep_type_iterator gep_type_end(const User *GEP)
const Value * getTrueValue() const
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:826
A cache of @llvm.assume calls within a function.
bool salvageDebugInfo(Instruction &I)
Assuming the instruction I is going to be deleted, attempt to salvage debug users of I by writing the...
Definition: Local.cpp:1624
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Definition: APInt.cpp:1841
This instruction constructs a fixed permutation of two input vectors.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:732
bool isTerminator() const
Definition: Instruction.h:128
struct LLVMOpaquePassRegistry * LLVMPassRegistryRef
Definition: Types.h:131
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in .dbg intrinsics with undef.
Definition: Local.cpp:483
void Add(Instruction *I)
Add - Add the specified instruction to the worklist if it isn&#39;t already in it.
BasicBlock * getSuccessor(unsigned i) const
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:813
STATISTIC(NumFunctions, "Total number of functions")
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
ThreeOps_match< V1_t, V2_t, Mask_t, Instruction::ShuffleVector > m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m)
Matches ShuffleVectorInst.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:580
static bool willNotOverflow(BinaryOpIntrinsic *BO, LazyValueInfo *LVI)
An instruction for reading from memory.
Definition: Instructions.h:167
uint64_t MaxArraySizeForCombine
Maximum size of array considered when transforming.
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:1946
Hexagon Common GEP
Value * getCondition() const
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2239
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:229
iv Induction Variable Users
Definition: IVUsers.cpp:51
Constant * getClause(unsigned Idx) const
Get the value of the clause at index Idx.
This defines the Use class.
void reserve(size_type N)
Definition: SmallVector.h:369
idx_iterator idx_end() const
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
TinyPtrVector - This class is specialized for cases where there are normally 0 or 1 element in a vect...
Definition: TinyPtrVector.h:30
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:39
static bool MaintainNoSignedWrap(BinaryOperator &I, Value *B, Value *C)
const Value * DoPHITranslation(const BasicBlock *CurBB, const BasicBlock *PredBB) const
Translate PHI node to its predecessor from the given basic block.
Definition: Value.cpp:724
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static bool isBitwiseLogicOp(unsigned Opcode)
Determine if the Opcode is and/or/xor.
Definition: Instruction.h:175
op_iterator op_begin()
Definition: User.h:229
static Constant * get(ArrayType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:992
unsigned getElementContainingOffset(uint64_t Offset) const
Given a valid byte offset into the structure, returns the structure index that contains it...
Definition: DataLayout.cpp:83
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...
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1508
LLVMContext & getContext() const
Return the LLVMContext in which this type was uniqued.
Definition: Type.h:129
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:274
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
bool isIdenticalTo(const Instruction *I) const
Return true if the specified instruction is exactly identical to the current one. ...
bool swapOperands()
Exchange the two operands to this instruction.
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1241
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
static Instruction * tryToMoveFreeBeforeNullTest(CallInst &FI, const DataLayout &DL)
Move the call to free before a NULL test.
AnalysisUsage & addRequired()
ArrayRef< unsigned > getIndices() const
Value * SimplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:562
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:50
This class represents a conversion between pointers from one address space to another.
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
This class represents the LLVM &#39;select&#39; instruction.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE, etc.
Definition: InstrTypes.h:831
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Attribute unwrap(LLVMAttributeRef Attr)
Definition: Attributes.h:203
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:368
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:439
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
&#39;undef&#39; values are things that do not have specified contents.
Definition: Constants.h:1285
uint64_t getArrayNumElements() const
Definition: DerivedTypes.h:422
Class to represent struct types.
Definition: DerivedTypes.h:233
Value * SimplifyGEPInst(Type *SrcTy, ArrayRef< Value *> Ops, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:196
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
The core instruction combiner logic.
void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM)
See llvm::createInstructionCombiningPass function.
static cl::opt< bool > EnableExpensiveCombines("expensive-combines", cl::desc("Enable expensive instruction combines"))
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1152
This file provides an implementation of debug counters.
static bool shorter_filter(const Value *LHS, const Value *RHS)
uint64_t getNumElements() const
For scalable vectors, this will return the minimum number of elements in the vector.
Definition: DerivedTypes.h:393
Type * getSourceElementType() const
Definition: Instructions.h:972
unsigned getNumClauses() const
Get the number of clauses for this landing pad.
This file implements a class to represent arbitrary precision integral constant values and operations...
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:681
Instruction * visitReturnInst(ReturnInst &RI)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
Instruction * visitBranchInst(BranchInst &BI)
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.
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:273
bool isBitwiseLogicOp() const
Return true if this is and/or/xor.
Definition: Instruction.h:180
unsigned getNumIndices() const
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Attempt to fold the constant using the specified DataLayout.
static Value * getIdentityValue(Instruction::BinaryOps Opcode, Value *V)
This function returns identity value for given opcode, which can be used to factor patterns like (X *...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:84
int64_t getSExtValue() const
Get sign extended value.
Definition: APInt.h:1574
void setCleanup(bool V)
Indicate that this landingpad instruction is a cleanup.
FastMathFlags getFastMathFlags() const
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
Definition: InstrTypes.h:692
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
static bool isNeverEqualToUnescapedAlloc(Value *V, const TargetLibraryInfo *TLI, Instruction *AI)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:123
bool isInBounds() const
Determine whether the GEP has the inbounds flag.
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Class to represent array types.
Definition: DerivedTypes.h:403
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
int32_t exactLogBase2() const
Definition: APInt.h:1787
This class represents a no-op cast from one type to another.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:81
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
TargetFolder - Create constants with target dependent folding.
Definition: TargetFolder.h:31
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
Definition: Value.h:582
An instruction for storing to memory.
Definition: Instructions.h:320
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:202
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
FunctionPass * createInstructionCombiningPass(bool ExpensiveCombines=true)
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
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:1043
Value * getOperand(unsigned i) const
Definition: User.h:169
static Instruction::BinaryOps getBinOpsForFactorization(Instruction::BinaryOps TopOpcode, BinaryOperator *Op, Value *&LHS, Value *&RHS)
This function predicates factorization using distributive laws.
Class to represent pointers.
Definition: DerivedTypes.h:544
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
unsigned getAddressSpace() const
Returns the address space of this instruction&#39;s pointer type.
Definition: Instructions.h:984
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:344
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return &#39;this&#39;.
Definition: Type.h:303
static MetadataAsValue * get(LLVMContext &Context, Metadata *MD)
Definition: Metadata.cpp:105
bool hasProfileSummary()
Returns true if profile summary is available.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:875
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:61
bool hasAllZeroIndices() const
Return true if all of the indices of this GEP are zeros.
Definition: Operator.h:507
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
The landingpad instruction holds all of the information necessary to generate correct exception handl...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:175
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:216
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:766
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
Definition: BasicBlock.cpp:233
bool run()
Run the combiner over the entire worklist until it is empty.
void setAAMetadata(const AAMDNodes &N)
Sets the metadata on this instruction from the AAMDNodes structure.
Definition: Metadata.cpp:1261
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Conditional or Unconditional Branch instruction.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
static ExtractValueInst * Create(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static bool isCatchAll(EHPersonality Personality, Constant *TypeInfo)
Return &#39;true&#39; if the given typeinfo will match anything.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
const APInt & getConstant() const
Returns the value when all bits have a known value.
Definition: KnownBits.h:56
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file provides the primary interface to the instcombine pass.
static BinaryOperator * CreateNUW(BinaryOps Opc, Value *V1, Value *V2, const Twine &Name="")
Definition: InstrTypes.h:308
A manager for alias analyses.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:572
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1892
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
size_t size() const
Definition: BasicBlock.h:278
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:541
void AddInitialGroup(ArrayRef< Instruction *> List)
AddInitialGroup - Add the specified batch of stuff in reverse order.
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
Value * SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
brc_match< Cond_t > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
bool isAssociative() const LLVM_READONLY
Return true if the instruction is associative:
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:442
Represent the analysis usage information of a pass.
op_iterator op_end()
Definition: User.h:231
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:814
bool isConstant() const
Returns true if we know the value of all bits.
Definition: KnownBits.h:49
This instruction compares its operands according to the predicate given to the constructor.
Analysis pass providing a never-invalidated alias analysis result.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
bool isBinaryOp() const
Definition: Instruction.h:130
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl...
Definition: Operator.h:66
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
Definition: AsmWriter.cpp:4274
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2316
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
void addClause(Constant *ClauseVal)
Add a catch or filter clause to the landing pad.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
op_range operands()
Definition: User.h:237
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
static CastInst * CreatePointerBitCastOrAddrSpaceCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast or an AddrSpaceCast cast instruction.
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:572
self_iterator getIterator()
Definition: ilist_node.h:81
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:73
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:73
Class to represent integer types.
Definition: DerivedTypes.h:40
Constant Vector Declarations.
Definition: Constants.h:499
The legacy pass manager&#39;s instcombine pass.
Definition: InstCombine.h:42
static Constant * getNot(Constant *C)
Definition: Constants.cpp:2222
void setSourceElementType(Type *Ty)
Definition: Instructions.h:974
static cl::opt< unsigned > MaxArraySize("instcombine-maxarray-size", cl::init(1024), cl::desc("Maximum array size considered when doing a combine"))
const Value * getCondition() const
static bool hasNoUnsignedWrap(BinaryOperator &I)
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:205
Type * getPointerOperandType() const
Method to return the pointer operand as a PointerType.
InstCombineWorklist - This is the worklist management logic for InstCombine.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
const Constant * stripPointerCasts() const
Definition: Constant.h:177
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, address space casts, and aliases.
Definition: Value.cpp:535
iterator erase(const_iterator CI)
Definition: SmallVector.h:434
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass...
size_t size() const
Definition: SmallVector.h:52
static wasm::ValType getType(const TargetRegisterClass *RC)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool LowerDbgDeclare(Function &F)
Lowers llvm.dbg.declare intrinsics into appropriate set of llvm.dbg.value intrinsics.
Definition: Local.cpp:1405
bool isVolatile() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isFilter(unsigned Idx) const
Return &#39;true&#39; if the clause and index Idx is a filter clause.
static Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
Definition: Constants.cpp:311
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
A function analysis which provides an AssumptionCache.
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:333
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:239
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Analysis pass which computes BlockFrequencyInfo.
This is the common base class for memset/memcpy/memmove.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
static bool simplifyAssocCastAssoc(BinaryOperator *BinOp1)
Combine constant operands of associative operations either before or after a cast to eliminate one of...
TinyPtrVector< DbgVariableIntrinsic * > FindDbgAddrUses(Value *V)
Finds all intrinsics declaring local variables as living in the memory that &#39;V&#39; points to...
Definition: Local.cpp:1506
BlockVerifier::State From
static bool combineInstructionsOverFunction(Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, bool ExpensiveCombines=true, LoopInfo *LI=nullptr)
iterator end()
Definition: BasicBlock.h:270
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1160
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:129
static ValueAsMetadata * get(Value *V)
Definition: Metadata.cpp:348
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Utility class for floating point operations which can have information about relaxed accuracy require...
Definition: Operator.h:245
This is a utility class that provides an abstraction for the common functionality between Instruction...
Definition: Operator.h:30
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:63
Provides information about what library functions are available for the current target.
static cl::opt< bool > EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"), cl::init(true))
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:643
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
uint64_t getSizeInBytes() const
Definition: DataLayout.h:570
Instruction * visitFree(CallInst &FI)
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1646
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
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:631
bool isConditional() const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
void initializeInstCombine(PassRegistry &)
Initialize all passes linked into the InstCombine library.
unsigned removeAllNonTerminatorAndEHPadInstructions(BasicBlock *BB)
Remove all instructions from a basic block other than it&#39;s terminator and any present EH pad instruct...
Definition: Local.cpp:1896
unsigned getNumIncomingValues() const
Return the number of incoming edges.
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:488
static bool AddReachableCodeToWorklist(BasicBlock *BB, const DataLayout &DL, SmallPtrSetImpl< BasicBlock *> &Visited, InstCombineWorklist &ICWorklist, const TargetLibraryInfo *TLI)
Walk the function in depth-first order, adding all reachable code to the worklist.
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Definition: InstrTypes.h:812
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a &#39;Neg&#39; as &#39;sub 0, V&#39;.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:535
struct LLVMOpaquePassManager * LLVMPassManagerRef
Definition: Types.h:128
static Value * foldOperationIntoSelectOperand(Instruction &I, Value *SO, InstCombiner::BuilderTy &Builder)
Class to represent vector types.
Definition: DerivedTypes.h:427
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
ConstantArray - Constant Array Declarations.
Definition: Constants.h:413
Class for arbitrary precision integers.
Definition: APInt.h:69
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1222
bool isCleanup() const
Return &#39;true&#39; if this landingpad instruction is a cleanup.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
CastClass_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
typename SuperClass::iterator iterator
Definition: SmallVector.h:319
iterator_range< user_iterator > users()
Definition: Value.h:399
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property...
Definition: Operator.h:95
Instruction * visitSwitchInst(SwitchInst &SI)
static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock)
Try to move the specified instruction from its current block into the beginning of DestBlock...
Instruction * visitExtractValueInst(ExtractValueInst &EV)
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1539
Represents analyses that only rely on functions&#39; control flow.
Definition: PassManager.h:114
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
Definition: KnownBits.h:161
const Value * getFalseValue() const
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
Instruction * visitLandingPadInst(LandingPadInst &LI)
use_iterator use_begin()
Definition: Value.h:338
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2209
Analysis pass providing a never-invalidated alias analysis result.
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)".
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&#39;s ...
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Provides an &#39;InsertHelper&#39; that calls a user-provided callback after performing the default insertion...
Definition: IRBuilder.h:72
bool isVolatile() const
Return true if this is a store to a volatile memory location.
Definition: Instructions.h:353
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:321
void registerAssumption(CallInst *CI)
Add an @llvm.assume intrinsic to this function&#39;s cache.
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:584
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:175
void setCondition(Value *V)
bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset) const
Accumulate the constant address offset of this GEP if possible.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:506
static InvokeInst * Create(FunctionType *Ty, Value *Func, BasicBlock *IfNormal, BasicBlock *IfException, ArrayRef< Value *> Args, const Twine &NameStr, Instruction *InsertBefore=nullptr)
static bool hasOneUse(unsigned Reg, MachineInstr *Def, MachineRegisterInfo &MRI, MachineDominatorTree &MDT, LiveIntervals &LIS)
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:609
static InsertValueInst * Create(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:189
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
bool isCatch(unsigned Idx) const
Return &#39;true&#39; if the clause and index Idx is a catch clause.
bool mayReadFromMemory() const
Return true if this instruction may read memory.
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...
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
Definition: Function.h:619
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:795
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:582
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
idx_iterator idx_begin() const
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2299
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
DEBUG_COUNTER(VisitCounter, "instcombine-visit", "Controls which instructions are visited")
bool isUnconditional() const
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
void initializeInstructionCombiningPassPass(PassRegistry &)
static cl::opt< unsigned > ShouldLowerDbgDeclare("instcombine-lower-dbg-declare", cl::Hidden, cl::init(true))
bool isMinValue() const
Determine if this is the smallest unsigned value.
Definition: APInt.h:436
void setCondition(Value *V)
Analysis pass providing the TargetLibraryInfo.
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag...
Multiway switch.
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1988
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
static GetElementPtrInst * CreateInBounds(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Definition: Instructions.h:935
INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine", "Combine redundant instructions", false, false) INITIALIZE_PASS_END(InstructionCombiningPass
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:375
const BasicBlock & front() const
Definition: Function.h:687
SmallVector< int, 16 > getShuffleMask() const
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
void stable_sort(R &&Range)
Definition: STLExtras.h:1316
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:482
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1879
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:114
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:575
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:353
LLVM Value Representation.
Definition: Value.h:72
Constant * getPersonalityFn() const
Get the personality function associated with this function.
Definition: Function.cpp:1384
This file provides internal interfaces used to implement the InstCombine.
void clearSubclassOptionalData()
Clear the optional flags contained in this value.
Definition: Value.h:475
succ_range successors(Instruction *I)
Definition: CFG.h:259
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:250
OptimizationRemarkEmitter legacy analysis pass.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
static const Function * getParent(const Value *V)
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Definition: Instruction.cpp:86
void ConvertDebugDeclareToDebugValue(DbgVariableIntrinsic *DII, StoreInst *SI, DIBuilder &Builder)
===---------------------------------------------------------------——===// Dbg Intrinsic utilities ...
Definition: Local.cpp:1306
Invoke instruction.
Instruction * visitGetElementPtrInst(GetElementPtrInst &GEP)
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:156
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
Definition: Instruction.h:583
Type * getElementType() const
Definition: DerivedTypes.h:394
IRTranslator LLVM IR MI
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:159
unsigned greater than
Definition: InstrTypes.h:755
bool isIntDivRem() const
Definition: Instruction.h:131
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
inst_range instructions(Function *F)
Definition: InstIterator.h:133
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
A container for analyses that lazily runs them and caches their results.
Type * getArrayElementType() const
Definition: Type.h:364
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:259
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object...
This header defines various interfaces for pass management in LLVM.
static bool shouldMergeGEPs(GEPOperator &GEP, GEPOperator &Src)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Value * getPointerOperand()
Definition: Instructions.h:412
Instruction * visitAllocSite(Instruction &FI)
The optimization diagnostic interface.
Value * getRawDest() const
bool use_empty() const
Definition: Value.h:322
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1088
Type * getElementType() const
Definition: DerivedTypes.h:563
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)".
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a &#39;Not&#39; as &#39;xor V, -1&#39; or &#39;xor -1, V&#39;.
bool isStructTy() const
True if this is an instance of StructType.
Definition: Type.h:217
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:220
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:43
const BasicBlock * getParent() const
Definition: Instruction.h:66
This instruction inserts a struct field of array element value into an aggregate value.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Legacy wrapper pass to provide the BasicAAResult object.
gep_type_iterator gep_type_begin(const User *GEP)
bool salvageDebugInfoForDbgValues(Instruction &I, ArrayRef< DbgVariableIntrinsic *> Insns)
Implementation of salvageDebugInfo, applying only to instructions in Insns, rather than all debug use...
Definition: Local.cpp:1633
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:1815
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property...
Definition: Operator.h:89
user_iterator user_end()
Definition: Value.h:383