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