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