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