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