xref: /freebsd-src/contrib/llvm-project/llvm/lib/IR/ConstantFold.cpp (revision e8d8bef961a50d4dc22501cde4fb9fb0be1b2532)
1 //===- ConstantFold.cpp - LLVM constant folder ----------------------------===//
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 // This file implements folding of constants for LLVM.  This implements the
10 // (internal) ConstantFold.h interface, which is used by the
11 // ConstantExpr::get* methods to automatically fold constants when possible.
12 //
13 // The current constant folding implementation is implemented in two pieces: the
14 // pieces that don't need DataLayout, and the pieces that do. This is to avoid
15 // a dependence in IR on Target.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "ConstantFold.h"
20 #include "llvm/ADT/APSInt.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/IR/Constants.h"
23 #include "llvm/IR/DerivedTypes.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/GetElementPtrTypeIterator.h"
26 #include "llvm/IR/GlobalAlias.h"
27 #include "llvm/IR/GlobalVariable.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/Module.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/Support/ErrorHandling.h"
33 #include "llvm/Support/ManagedStatic.h"
34 #include "llvm/Support/MathExtras.h"
35 using namespace llvm;
36 using namespace llvm::PatternMatch;
37 
38 //===----------------------------------------------------------------------===//
39 //                ConstantFold*Instruction Implementations
40 //===----------------------------------------------------------------------===//
41 
42 /// Convert the specified vector Constant node to the specified vector type.
43 /// At this point, we know that the elements of the input vector constant are
44 /// all simple integer or FP values.
45 static Constant *BitCastConstantVector(Constant *CV, VectorType *DstTy) {
46 
47   if (CV->isAllOnesValue()) return Constant::getAllOnesValue(DstTy);
48   if (CV->isNullValue()) return Constant::getNullValue(DstTy);
49 
50   // Do not iterate on scalable vector. The num of elements is unknown at
51   // compile-time.
52   if (isa<ScalableVectorType>(DstTy))
53     return nullptr;
54 
55   // If this cast changes element count then we can't handle it here:
56   // doing so requires endianness information.  This should be handled by
57   // Analysis/ConstantFolding.cpp
58   unsigned NumElts = cast<FixedVectorType>(DstTy)->getNumElements();
59   if (NumElts != cast<FixedVectorType>(CV->getType())->getNumElements())
60     return nullptr;
61 
62   Type *DstEltTy = DstTy->getElementType();
63   // Fast path for splatted constants.
64   if (Constant *Splat = CV->getSplatValue()) {
65     return ConstantVector::getSplat(DstTy->getElementCount(),
66                                     ConstantExpr::getBitCast(Splat, DstEltTy));
67   }
68 
69   SmallVector<Constant*, 16> Result;
70   Type *Ty = IntegerType::get(CV->getContext(), 32);
71   for (unsigned i = 0; i != NumElts; ++i) {
72     Constant *C =
73       ConstantExpr::getExtractElement(CV, ConstantInt::get(Ty, i));
74     C = ConstantExpr::getBitCast(C, DstEltTy);
75     Result.push_back(C);
76   }
77 
78   return ConstantVector::get(Result);
79 }
80 
81 /// This function determines which opcode to use to fold two constant cast
82 /// expressions together. It uses CastInst::isEliminableCastPair to determine
83 /// the opcode. Consequently its just a wrapper around that function.
84 /// Determine if it is valid to fold a cast of a cast
85 static unsigned
86 foldConstantCastPair(
87   unsigned opc,          ///< opcode of the second cast constant expression
88   ConstantExpr *Op,      ///< the first cast constant expression
89   Type *DstTy            ///< destination type of the first cast
90 ) {
91   assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!");
92   assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type");
93   assert(CastInst::isCast(opc) && "Invalid cast opcode");
94 
95   // The types and opcodes for the two Cast constant expressions
96   Type *SrcTy = Op->getOperand(0)->getType();
97   Type *MidTy = Op->getType();
98   Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode());
99   Instruction::CastOps secondOp = Instruction::CastOps(opc);
100 
101   // Assume that pointers are never more than 64 bits wide, and only use this
102   // for the middle type. Otherwise we could end up folding away illegal
103   // bitcasts between address spaces with different sizes.
104   IntegerType *FakeIntPtrTy = Type::getInt64Ty(DstTy->getContext());
105 
106   // Let CastInst::isEliminableCastPair do the heavy lifting.
107   return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy,
108                                         nullptr, FakeIntPtrTy, nullptr);
109 }
110 
111 static Constant *FoldBitCast(Constant *V, Type *DestTy) {
112   Type *SrcTy = V->getType();
113   if (SrcTy == DestTy)
114     return V; // no-op cast
115 
116   // Check to see if we are casting a pointer to an aggregate to a pointer to
117   // the first element.  If so, return the appropriate GEP instruction.
118   if (PointerType *PTy = dyn_cast<PointerType>(V->getType()))
119     if (PointerType *DPTy = dyn_cast<PointerType>(DestTy))
120       if (PTy->getAddressSpace() == DPTy->getAddressSpace()
121           && PTy->getElementType()->isSized()) {
122         SmallVector<Value*, 8> IdxList;
123         Value *Zero =
124           Constant::getNullValue(Type::getInt32Ty(DPTy->getContext()));
125         IdxList.push_back(Zero);
126         Type *ElTy = PTy->getElementType();
127         while (ElTy && ElTy != DPTy->getElementType()) {
128           ElTy = GetElementPtrInst::getTypeAtIndex(ElTy, (uint64_t)0);
129           IdxList.push_back(Zero);
130         }
131 
132         if (ElTy == DPTy->getElementType())
133           // This GEP is inbounds because all indices are zero.
134           return ConstantExpr::getInBoundsGetElementPtr(PTy->getElementType(),
135                                                         V, IdxList);
136       }
137 
138   // Handle casts from one vector constant to another.  We know that the src
139   // and dest type have the same size (otherwise its an illegal cast).
140   if (VectorType *DestPTy = dyn_cast<VectorType>(DestTy)) {
141     if (VectorType *SrcTy = dyn_cast<VectorType>(V->getType())) {
142       assert(DestPTy->getPrimitiveSizeInBits() ==
143                  SrcTy->getPrimitiveSizeInBits() &&
144              "Not cast between same sized vectors!");
145       SrcTy = nullptr;
146       // First, check for null.  Undef is already handled.
147       if (isa<ConstantAggregateZero>(V))
148         return Constant::getNullValue(DestTy);
149 
150       // Handle ConstantVector and ConstantAggregateVector.
151       return BitCastConstantVector(V, DestPTy);
152     }
153 
154     // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts
155     // This allows for other simplifications (although some of them
156     // can only be handled by Analysis/ConstantFolding.cpp).
157     if (isa<ConstantInt>(V) || isa<ConstantFP>(V))
158       return ConstantExpr::getBitCast(ConstantVector::get(V), DestPTy);
159   }
160 
161   // Finally, implement bitcast folding now.   The code below doesn't handle
162   // bitcast right.
163   if (isa<ConstantPointerNull>(V))  // ptr->ptr cast.
164     return ConstantPointerNull::get(cast<PointerType>(DestTy));
165 
166   // Handle integral constant input.
167   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
168     if (DestTy->isIntegerTy())
169       // Integral -> Integral. This is a no-op because the bit widths must
170       // be the same. Consequently, we just fold to V.
171       return V;
172 
173     // See note below regarding the PPC_FP128 restriction.
174     if (DestTy->isFloatingPointTy() && !DestTy->isPPC_FP128Ty())
175       return ConstantFP::get(DestTy->getContext(),
176                              APFloat(DestTy->getFltSemantics(),
177                                      CI->getValue()));
178 
179     // Otherwise, can't fold this (vector?)
180     return nullptr;
181   }
182 
183   // Handle ConstantFP input: FP -> Integral.
184   if (ConstantFP *FP = dyn_cast<ConstantFP>(V)) {
185     // PPC_FP128 is really the sum of two consecutive doubles, where the first
186     // double is always stored first in memory, regardless of the target
187     // endianness. The memory layout of i128, however, depends on the target
188     // endianness, and so we can't fold this without target endianness
189     // information. This should instead be handled by
190     // Analysis/ConstantFolding.cpp
191     if (FP->getType()->isPPC_FP128Ty())
192       return nullptr;
193 
194     // Make sure dest type is compatible with the folded integer constant.
195     if (!DestTy->isIntegerTy())
196       return nullptr;
197 
198     return ConstantInt::get(FP->getContext(),
199                             FP->getValueAPF().bitcastToAPInt());
200   }
201 
202   return nullptr;
203 }
204 
205 
206 /// V is an integer constant which only has a subset of its bytes used.
207 /// The bytes used are indicated by ByteStart (which is the first byte used,
208 /// counting from the least significant byte) and ByteSize, which is the number
209 /// of bytes used.
210 ///
211 /// This function analyzes the specified constant to see if the specified byte
212 /// range can be returned as a simplified constant.  If so, the constant is
213 /// returned, otherwise null is returned.
214 static Constant *ExtractConstantBytes(Constant *C, unsigned ByteStart,
215                                       unsigned ByteSize) {
216   assert(C->getType()->isIntegerTy() &&
217          (cast<IntegerType>(C->getType())->getBitWidth() & 7) == 0 &&
218          "Non-byte sized integer input");
219   unsigned CSize = cast<IntegerType>(C->getType())->getBitWidth()/8;
220   assert(ByteSize && "Must be accessing some piece");
221   assert(ByteStart+ByteSize <= CSize && "Extracting invalid piece from input");
222   assert(ByteSize != CSize && "Should not extract everything");
223 
224   // Constant Integers are simple.
225   if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) {
226     APInt V = CI->getValue();
227     if (ByteStart)
228       V.lshrInPlace(ByteStart*8);
229     V = V.trunc(ByteSize*8);
230     return ConstantInt::get(CI->getContext(), V);
231   }
232 
233   // In the input is a constant expr, we might be able to recursively simplify.
234   // If not, we definitely can't do anything.
235   ConstantExpr *CE = dyn_cast<ConstantExpr>(C);
236   if (!CE) return nullptr;
237 
238   switch (CE->getOpcode()) {
239   default: return nullptr;
240   case Instruction::Or: {
241     Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize);
242     if (!RHS)
243       return nullptr;
244 
245     // X | -1 -> -1.
246     if (ConstantInt *RHSC = dyn_cast<ConstantInt>(RHS))
247       if (RHSC->isMinusOne())
248         return RHSC;
249 
250     Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize);
251     if (!LHS)
252       return nullptr;
253     return ConstantExpr::getOr(LHS, RHS);
254   }
255   case Instruction::And: {
256     Constant *RHS = ExtractConstantBytes(CE->getOperand(1), ByteStart,ByteSize);
257     if (!RHS)
258       return nullptr;
259 
260     // X & 0 -> 0.
261     if (RHS->isNullValue())
262       return RHS;
263 
264     Constant *LHS = ExtractConstantBytes(CE->getOperand(0), ByteStart,ByteSize);
265     if (!LHS)
266       return nullptr;
267     return ConstantExpr::getAnd(LHS, RHS);
268   }
269   case Instruction::LShr: {
270     ConstantInt *Amt = dyn_cast<ConstantInt>(CE->getOperand(1));
271     if (!Amt)
272       return nullptr;
273     APInt ShAmt = Amt->getValue();
274     // Cannot analyze non-byte shifts.
275     if ((ShAmt & 7) != 0)
276       return nullptr;
277     ShAmt.lshrInPlace(3);
278 
279     // If the extract is known to be all zeros, return zero.
280     if (ShAmt.uge(CSize - ByteStart))
281       return Constant::getNullValue(
282           IntegerType::get(CE->getContext(), ByteSize * 8));
283     // If the extract is known to be fully in the input, extract it.
284     if (ShAmt.ule(CSize - (ByteStart + ByteSize)))
285       return ExtractConstantBytes(CE->getOperand(0),
286                                   ByteStart + ShAmt.getZExtValue(), ByteSize);
287 
288     // TODO: Handle the 'partially zero' case.
289     return nullptr;
290   }
291 
292   case Instruction::Shl: {
293     ConstantInt *Amt = dyn_cast<ConstantInt>(CE->getOperand(1));
294     if (!Amt)
295       return nullptr;
296     APInt ShAmt = Amt->getValue();
297     // Cannot analyze non-byte shifts.
298     if ((ShAmt & 7) != 0)
299       return nullptr;
300     ShAmt.lshrInPlace(3);
301 
302     // If the extract is known to be all zeros, return zero.
303     if (ShAmt.uge(ByteStart + ByteSize))
304       return Constant::getNullValue(
305           IntegerType::get(CE->getContext(), ByteSize * 8));
306     // If the extract is known to be fully in the input, extract it.
307     if (ShAmt.ule(ByteStart))
308       return ExtractConstantBytes(CE->getOperand(0),
309                                   ByteStart - ShAmt.getZExtValue(), ByteSize);
310 
311     // TODO: Handle the 'partially zero' case.
312     return nullptr;
313   }
314 
315   case Instruction::ZExt: {
316     unsigned SrcBitSize =
317       cast<IntegerType>(CE->getOperand(0)->getType())->getBitWidth();
318 
319     // If extracting something that is completely zero, return 0.
320     if (ByteStart*8 >= SrcBitSize)
321       return Constant::getNullValue(IntegerType::get(CE->getContext(),
322                                                      ByteSize*8));
323 
324     // If exactly extracting the input, return it.
325     if (ByteStart == 0 && ByteSize*8 == SrcBitSize)
326       return CE->getOperand(0);
327 
328     // If extracting something completely in the input, if the input is a
329     // multiple of 8 bits, recurse.
330     if ((SrcBitSize&7) == 0 && (ByteStart+ByteSize)*8 <= SrcBitSize)
331       return ExtractConstantBytes(CE->getOperand(0), ByteStart, ByteSize);
332 
333     // Otherwise, if extracting a subset of the input, which is not multiple of
334     // 8 bits, do a shift and trunc to get the bits.
335     if ((ByteStart+ByteSize)*8 < SrcBitSize) {
336       assert((SrcBitSize&7) && "Shouldn't get byte sized case here");
337       Constant *Res = CE->getOperand(0);
338       if (ByteStart)
339         Res = ConstantExpr::getLShr(Res,
340                                  ConstantInt::get(Res->getType(), ByteStart*8));
341       return ConstantExpr::getTrunc(Res, IntegerType::get(C->getContext(),
342                                                           ByteSize*8));
343     }
344 
345     // TODO: Handle the 'partially zero' case.
346     return nullptr;
347   }
348   }
349 }
350 
351 /// Return a ConstantExpr with type DestTy for sizeof on Ty, with any known
352 /// factors factored out. If Folded is false, return null if no factoring was
353 /// possible, to avoid endlessly bouncing an unfoldable expression back into the
354 /// top-level folder.
355 static Constant *getFoldedSizeOf(Type *Ty, Type *DestTy, bool Folded) {
356   if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
357     Constant *N = ConstantInt::get(DestTy, ATy->getNumElements());
358     Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true);
359     return ConstantExpr::getNUWMul(E, N);
360   }
361 
362   if (StructType *STy = dyn_cast<StructType>(Ty))
363     if (!STy->isPacked()) {
364       unsigned NumElems = STy->getNumElements();
365       // An empty struct has size zero.
366       if (NumElems == 0)
367         return ConstantExpr::getNullValue(DestTy);
368       // Check for a struct with all members having the same size.
369       Constant *MemberSize =
370         getFoldedSizeOf(STy->getElementType(0), DestTy, true);
371       bool AllSame = true;
372       for (unsigned i = 1; i != NumElems; ++i)
373         if (MemberSize !=
374             getFoldedSizeOf(STy->getElementType(i), DestTy, true)) {
375           AllSame = false;
376           break;
377         }
378       if (AllSame) {
379         Constant *N = ConstantInt::get(DestTy, NumElems);
380         return ConstantExpr::getNUWMul(MemberSize, N);
381       }
382     }
383 
384   // Pointer size doesn't depend on the pointee type, so canonicalize them
385   // to an arbitrary pointee.
386   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
387     if (!PTy->getElementType()->isIntegerTy(1))
388       return
389         getFoldedSizeOf(PointerType::get(IntegerType::get(PTy->getContext(), 1),
390                                          PTy->getAddressSpace()),
391                         DestTy, true);
392 
393   // If there's no interesting folding happening, bail so that we don't create
394   // a constant that looks like it needs folding but really doesn't.
395   if (!Folded)
396     return nullptr;
397 
398   // Base case: Get a regular sizeof expression.
399   Constant *C = ConstantExpr::getSizeOf(Ty);
400   C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
401                                                     DestTy, false),
402                             C, DestTy);
403   return C;
404 }
405 
406 /// Return a ConstantExpr with type DestTy for alignof on Ty, with any known
407 /// factors factored out. If Folded is false, return null if no factoring was
408 /// possible, to avoid endlessly bouncing an unfoldable expression back into the
409 /// top-level folder.
410 static Constant *getFoldedAlignOf(Type *Ty, Type *DestTy, bool Folded) {
411   // The alignment of an array is equal to the alignment of the
412   // array element. Note that this is not always true for vectors.
413   if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
414     Constant *C = ConstantExpr::getAlignOf(ATy->getElementType());
415     C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
416                                                       DestTy,
417                                                       false),
418                               C, DestTy);
419     return C;
420   }
421 
422   if (StructType *STy = dyn_cast<StructType>(Ty)) {
423     // Packed structs always have an alignment of 1.
424     if (STy->isPacked())
425       return ConstantInt::get(DestTy, 1);
426 
427     // Otherwise, struct alignment is the maximum alignment of any member.
428     // Without target data, we can't compare much, but we can check to see
429     // if all the members have the same alignment.
430     unsigned NumElems = STy->getNumElements();
431     // An empty struct has minimal alignment.
432     if (NumElems == 0)
433       return ConstantInt::get(DestTy, 1);
434     // Check for a struct with all members having the same alignment.
435     Constant *MemberAlign =
436       getFoldedAlignOf(STy->getElementType(0), DestTy, true);
437     bool AllSame = true;
438     for (unsigned i = 1; i != NumElems; ++i)
439       if (MemberAlign != getFoldedAlignOf(STy->getElementType(i), DestTy, true)) {
440         AllSame = false;
441         break;
442       }
443     if (AllSame)
444       return MemberAlign;
445   }
446 
447   // Pointer alignment doesn't depend on the pointee type, so canonicalize them
448   // to an arbitrary pointee.
449   if (PointerType *PTy = dyn_cast<PointerType>(Ty))
450     if (!PTy->getElementType()->isIntegerTy(1))
451       return
452         getFoldedAlignOf(PointerType::get(IntegerType::get(PTy->getContext(),
453                                                            1),
454                                           PTy->getAddressSpace()),
455                          DestTy, true);
456 
457   // If there's no interesting folding happening, bail so that we don't create
458   // a constant that looks like it needs folding but really doesn't.
459   if (!Folded)
460     return nullptr;
461 
462   // Base case: Get a regular alignof expression.
463   Constant *C = ConstantExpr::getAlignOf(Ty);
464   C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
465                                                     DestTy, false),
466                             C, DestTy);
467   return C;
468 }
469 
470 /// Return a ConstantExpr with type DestTy for offsetof on Ty and FieldNo, with
471 /// any known factors factored out. If Folded is false, return null if no
472 /// factoring was possible, to avoid endlessly bouncing an unfoldable expression
473 /// back into the top-level folder.
474 static Constant *getFoldedOffsetOf(Type *Ty, Constant *FieldNo, Type *DestTy,
475                                    bool Folded) {
476   if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
477     Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo, false,
478                                                                 DestTy, false),
479                                         FieldNo, DestTy);
480     Constant *E = getFoldedSizeOf(ATy->getElementType(), DestTy, true);
481     return ConstantExpr::getNUWMul(E, N);
482   }
483 
484   if (StructType *STy = dyn_cast<StructType>(Ty))
485     if (!STy->isPacked()) {
486       unsigned NumElems = STy->getNumElements();
487       // An empty struct has no members.
488       if (NumElems == 0)
489         return nullptr;
490       // Check for a struct with all members having the same size.
491       Constant *MemberSize =
492         getFoldedSizeOf(STy->getElementType(0), DestTy, true);
493       bool AllSame = true;
494       for (unsigned i = 1; i != NumElems; ++i)
495         if (MemberSize !=
496             getFoldedSizeOf(STy->getElementType(i), DestTy, true)) {
497           AllSame = false;
498           break;
499         }
500       if (AllSame) {
501         Constant *N = ConstantExpr::getCast(CastInst::getCastOpcode(FieldNo,
502                                                                     false,
503                                                                     DestTy,
504                                                                     false),
505                                             FieldNo, DestTy);
506         return ConstantExpr::getNUWMul(MemberSize, N);
507       }
508     }
509 
510   // If there's no interesting folding happening, bail so that we don't create
511   // a constant that looks like it needs folding but really doesn't.
512   if (!Folded)
513     return nullptr;
514 
515   // Base case: Get a regular offsetof expression.
516   Constant *C = ConstantExpr::getOffsetOf(Ty, FieldNo);
517   C = ConstantExpr::getCast(CastInst::getCastOpcode(C, false,
518                                                     DestTy, false),
519                             C, DestTy);
520   return C;
521 }
522 
523 Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V,
524                                             Type *DestTy) {
525   if (isa<PoisonValue>(V))
526     return PoisonValue::get(DestTy);
527 
528   if (isa<UndefValue>(V)) {
529     // zext(undef) = 0, because the top bits will be zero.
530     // sext(undef) = 0, because the top bits will all be the same.
531     // [us]itofp(undef) = 0, because the result value is bounded.
532     if (opc == Instruction::ZExt || opc == Instruction::SExt ||
533         opc == Instruction::UIToFP || opc == Instruction::SIToFP)
534       return Constant::getNullValue(DestTy);
535     return UndefValue::get(DestTy);
536   }
537 
538   if (V->isNullValue() && !DestTy->isX86_MMXTy() && !DestTy->isX86_AMXTy() &&
539       opc != Instruction::AddrSpaceCast)
540     return Constant::getNullValue(DestTy);
541 
542   // If the cast operand is a constant expression, there's a few things we can
543   // do to try to simplify it.
544   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
545     if (CE->isCast()) {
546       // Try hard to fold cast of cast because they are often eliminable.
547       if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy))
548         return ConstantExpr::getCast(newOpc, CE->getOperand(0), DestTy);
549     } else if (CE->getOpcode() == Instruction::GetElementPtr &&
550                // Do not fold addrspacecast (gep 0, .., 0). It might make the
551                // addrspacecast uncanonicalized.
552                opc != Instruction::AddrSpaceCast &&
553                // Do not fold bitcast (gep) with inrange index, as this loses
554                // information.
555                !cast<GEPOperator>(CE)->getInRangeIndex().hasValue() &&
556                // Do not fold if the gep type is a vector, as bitcasting
557                // operand 0 of a vector gep will result in a bitcast between
558                // different sizes.
559                !CE->getType()->isVectorTy()) {
560       // If all of the indexes in the GEP are null values, there is no pointer
561       // adjustment going on.  We might as well cast the source pointer.
562       bool isAllNull = true;
563       for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
564         if (!CE->getOperand(i)->isNullValue()) {
565           isAllNull = false;
566           break;
567         }
568       if (isAllNull)
569         // This is casting one pointer type to another, always BitCast
570         return ConstantExpr::getPointerCast(CE->getOperand(0), DestTy);
571     }
572   }
573 
574   // If the cast operand is a constant vector, perform the cast by
575   // operating on each element. In the cast of bitcasts, the element
576   // count may be mismatched; don't attempt to handle that here.
577   if ((isa<ConstantVector>(V) || isa<ConstantDataVector>(V)) &&
578       DestTy->isVectorTy() &&
579       cast<FixedVectorType>(DestTy)->getNumElements() ==
580           cast<FixedVectorType>(V->getType())->getNumElements()) {
581     VectorType *DestVecTy = cast<VectorType>(DestTy);
582     Type *DstEltTy = DestVecTy->getElementType();
583     // Fast path for splatted constants.
584     if (Constant *Splat = V->getSplatValue()) {
585       return ConstantVector::getSplat(
586           cast<VectorType>(DestTy)->getElementCount(),
587           ConstantExpr::getCast(opc, Splat, DstEltTy));
588     }
589     SmallVector<Constant *, 16> res;
590     Type *Ty = IntegerType::get(V->getContext(), 32);
591     for (unsigned i = 0,
592                   e = cast<FixedVectorType>(V->getType())->getNumElements();
593          i != e; ++i) {
594       Constant *C =
595         ConstantExpr::getExtractElement(V, ConstantInt::get(Ty, i));
596       res.push_back(ConstantExpr::getCast(opc, C, DstEltTy));
597     }
598     return ConstantVector::get(res);
599   }
600 
601   // We actually have to do a cast now. Perform the cast according to the
602   // opcode specified.
603   switch (opc) {
604   default:
605     llvm_unreachable("Failed to cast constant expression");
606   case Instruction::FPTrunc:
607   case Instruction::FPExt:
608     if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
609       bool ignored;
610       APFloat Val = FPC->getValueAPF();
611       Val.convert(DestTy->isHalfTy() ? APFloat::IEEEhalf() :
612                   DestTy->isFloatTy() ? APFloat::IEEEsingle() :
613                   DestTy->isDoubleTy() ? APFloat::IEEEdouble() :
614                   DestTy->isX86_FP80Ty() ? APFloat::x87DoubleExtended() :
615                   DestTy->isFP128Ty() ? APFloat::IEEEquad() :
616                   DestTy->isPPC_FP128Ty() ? APFloat::PPCDoubleDouble() :
617                   APFloat::Bogus(),
618                   APFloat::rmNearestTiesToEven, &ignored);
619       return ConstantFP::get(V->getContext(), Val);
620     }
621     return nullptr; // Can't fold.
622   case Instruction::FPToUI:
623   case Instruction::FPToSI:
624     if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
625       const APFloat &V = FPC->getValueAPF();
626       bool ignored;
627       uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth();
628       APSInt IntVal(DestBitWidth, opc == Instruction::FPToUI);
629       if (APFloat::opInvalidOp ==
630           V.convertToInteger(IntVal, APFloat::rmTowardZero, &ignored)) {
631         // Undefined behavior invoked - the destination type can't represent
632         // the input constant.
633         return PoisonValue::get(DestTy);
634       }
635       return ConstantInt::get(FPC->getContext(), IntVal);
636     }
637     return nullptr; // Can't fold.
638   case Instruction::IntToPtr:   //always treated as unsigned
639     if (V->isNullValue())       // Is it an integral null value?
640       return ConstantPointerNull::get(cast<PointerType>(DestTy));
641     return nullptr;                   // Other pointer types cannot be casted
642   case Instruction::PtrToInt:   // always treated as unsigned
643     // Is it a null pointer value?
644     if (V->isNullValue())
645       return ConstantInt::get(DestTy, 0);
646     // If this is a sizeof-like expression, pull out multiplications by
647     // known factors to expose them to subsequent folding. If it's an
648     // alignof-like expression, factor out known factors.
649     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
650       if (CE->getOpcode() == Instruction::GetElementPtr &&
651           CE->getOperand(0)->isNullValue()) {
652         // FIXME: Looks like getFoldedSizeOf(), getFoldedOffsetOf() and
653         // getFoldedAlignOf() don't handle the case when DestTy is a vector of
654         // pointers yet. We end up in asserts in CastInst::getCastOpcode (see
655         // test/Analysis/ConstantFolding/cast-vector.ll). I've only seen this
656         // happen in one "real" C-code test case, so it does not seem to be an
657         // important optimization to handle vectors here. For now, simply bail
658         // out.
659         if (DestTy->isVectorTy())
660           return nullptr;
661         GEPOperator *GEPO = cast<GEPOperator>(CE);
662         Type *Ty = GEPO->getSourceElementType();
663         if (CE->getNumOperands() == 2) {
664           // Handle a sizeof-like expression.
665           Constant *Idx = CE->getOperand(1);
666           bool isOne = isa<ConstantInt>(Idx) && cast<ConstantInt>(Idx)->isOne();
667           if (Constant *C = getFoldedSizeOf(Ty, DestTy, !isOne)) {
668             Idx = ConstantExpr::getCast(CastInst::getCastOpcode(Idx, true,
669                                                                 DestTy, false),
670                                         Idx, DestTy);
671             return ConstantExpr::getMul(C, Idx);
672           }
673         } else if (CE->getNumOperands() == 3 &&
674                    CE->getOperand(1)->isNullValue()) {
675           // Handle an alignof-like expression.
676           if (StructType *STy = dyn_cast<StructType>(Ty))
677             if (!STy->isPacked()) {
678               ConstantInt *CI = cast<ConstantInt>(CE->getOperand(2));
679               if (CI->isOne() &&
680                   STy->getNumElements() == 2 &&
681                   STy->getElementType(0)->isIntegerTy(1)) {
682                 return getFoldedAlignOf(STy->getElementType(1), DestTy, false);
683               }
684             }
685           // Handle an offsetof-like expression.
686           if (Ty->isStructTy() || Ty->isArrayTy()) {
687             if (Constant *C = getFoldedOffsetOf(Ty, CE->getOperand(2),
688                                                 DestTy, false))
689               return C;
690           }
691         }
692       }
693     // Other pointer types cannot be casted
694     return nullptr;
695   case Instruction::UIToFP:
696   case Instruction::SIToFP:
697     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
698       const APInt &api = CI->getValue();
699       APFloat apf(DestTy->getFltSemantics(),
700                   APInt::getNullValue(DestTy->getPrimitiveSizeInBits()));
701       apf.convertFromAPInt(api, opc==Instruction::SIToFP,
702                            APFloat::rmNearestTiesToEven);
703       return ConstantFP::get(V->getContext(), apf);
704     }
705     return nullptr;
706   case Instruction::ZExt:
707     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
708       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
709       return ConstantInt::get(V->getContext(),
710                               CI->getValue().zext(BitWidth));
711     }
712     return nullptr;
713   case Instruction::SExt:
714     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
715       uint32_t BitWidth = cast<IntegerType>(DestTy)->getBitWidth();
716       return ConstantInt::get(V->getContext(),
717                               CI->getValue().sext(BitWidth));
718     }
719     return nullptr;
720   case Instruction::Trunc: {
721     if (V->getType()->isVectorTy())
722       return nullptr;
723 
724     uint32_t DestBitWidth = cast<IntegerType>(DestTy)->getBitWidth();
725     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
726       return ConstantInt::get(V->getContext(),
727                               CI->getValue().trunc(DestBitWidth));
728     }
729 
730     // The input must be a constantexpr.  See if we can simplify this based on
731     // the bytes we are demanding.  Only do this if the source and dest are an
732     // even multiple of a byte.
733     if ((DestBitWidth & 7) == 0 &&
734         (cast<IntegerType>(V->getType())->getBitWidth() & 7) == 0)
735       if (Constant *Res = ExtractConstantBytes(V, 0, DestBitWidth / 8))
736         return Res;
737 
738     return nullptr;
739   }
740   case Instruction::BitCast:
741     return FoldBitCast(V, DestTy);
742   case Instruction::AddrSpaceCast:
743     return nullptr;
744   }
745 }
746 
747 Constant *llvm::ConstantFoldSelectInstruction(Constant *Cond,
748                                               Constant *V1, Constant *V2) {
749   // Check for i1 and vector true/false conditions.
750   if (Cond->isNullValue()) return V2;
751   if (Cond->isAllOnesValue()) return V1;
752 
753   // If the condition is a vector constant, fold the result elementwise.
754   if (ConstantVector *CondV = dyn_cast<ConstantVector>(Cond)) {
755     auto *V1VTy = CondV->getType();
756     SmallVector<Constant*, 16> Result;
757     Type *Ty = IntegerType::get(CondV->getContext(), 32);
758     for (unsigned i = 0, e = V1VTy->getNumElements(); i != e; ++i) {
759       Constant *V;
760       Constant *V1Element = ConstantExpr::getExtractElement(V1,
761                                                     ConstantInt::get(Ty, i));
762       Constant *V2Element = ConstantExpr::getExtractElement(V2,
763                                                     ConstantInt::get(Ty, i));
764       auto *Cond = cast<Constant>(CondV->getOperand(i));
765       if (isa<PoisonValue>(Cond)) {
766         V = PoisonValue::get(V1Element->getType());
767       } else if (V1Element == V2Element) {
768         V = V1Element;
769       } else if (isa<UndefValue>(Cond)) {
770         V = isa<UndefValue>(V1Element) ? V1Element : V2Element;
771       } else {
772         if (!isa<ConstantInt>(Cond)) break;
773         V = Cond->isNullValue() ? V2Element : V1Element;
774       }
775       Result.push_back(V);
776     }
777 
778     // If we were able to build the vector, return it.
779     if (Result.size() == V1VTy->getNumElements())
780       return ConstantVector::get(Result);
781   }
782 
783   if (isa<PoisonValue>(Cond))
784     return PoisonValue::get(V1->getType());
785 
786   if (isa<UndefValue>(Cond)) {
787     if (isa<UndefValue>(V1)) return V1;
788     return V2;
789   }
790 
791   if (V1 == V2) return V1;
792 
793   if (isa<PoisonValue>(V1))
794     return V2;
795   if (isa<PoisonValue>(V2))
796     return V1;
797 
798   // If the true or false value is undef, we can fold to the other value as
799   // long as the other value isn't poison.
800   auto NotPoison = [](Constant *C) {
801     if (isa<PoisonValue>(C))
802       return false;
803 
804     // TODO: We can analyze ConstExpr by opcode to determine if there is any
805     //       possibility of poison.
806     if (isa<ConstantExpr>(C))
807       return false;
808 
809     if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(C) ||
810         isa<ConstantPointerNull>(C) || isa<Function>(C))
811       return true;
812 
813     if (C->getType()->isVectorTy())
814       return !C->containsPoisonElement() && !C->containsConstantExpression();
815 
816     // TODO: Recursively analyze aggregates or other constants.
817     return false;
818   };
819   if (isa<UndefValue>(V1) && NotPoison(V2)) return V2;
820   if (isa<UndefValue>(V2) && NotPoison(V1)) return V1;
821 
822   if (ConstantExpr *TrueVal = dyn_cast<ConstantExpr>(V1)) {
823     if (TrueVal->getOpcode() == Instruction::Select)
824       if (TrueVal->getOperand(0) == Cond)
825         return ConstantExpr::getSelect(Cond, TrueVal->getOperand(1), V2);
826   }
827   if (ConstantExpr *FalseVal = dyn_cast<ConstantExpr>(V2)) {
828     if (FalseVal->getOpcode() == Instruction::Select)
829       if (FalseVal->getOperand(0) == Cond)
830         return ConstantExpr::getSelect(Cond, V1, FalseVal->getOperand(2));
831   }
832 
833   return nullptr;
834 }
835 
836 Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val,
837                                                       Constant *Idx) {
838   auto *ValVTy = cast<VectorType>(Val->getType());
839 
840   // extractelt poison, C -> poison
841   // extractelt C, undef -> poison
842   if (isa<PoisonValue>(Val) || isa<UndefValue>(Idx))
843     return PoisonValue::get(ValVTy->getElementType());
844 
845   // extractelt undef, C -> undef
846   if (isa<UndefValue>(Val))
847     return UndefValue::get(ValVTy->getElementType());
848 
849   auto *CIdx = dyn_cast<ConstantInt>(Idx);
850   if (!CIdx)
851     return nullptr;
852 
853   if (auto *ValFVTy = dyn_cast<FixedVectorType>(Val->getType())) {
854     // ee({w,x,y,z}, wrong_value) -> poison
855     if (CIdx->uge(ValFVTy->getNumElements()))
856       return PoisonValue::get(ValFVTy->getElementType());
857   }
858 
859   // ee (gep (ptr, idx0, ...), idx) -> gep (ee (ptr, idx), ee (idx0, idx), ...)
860   if (auto *CE = dyn_cast<ConstantExpr>(Val)) {
861     if (CE->getOpcode() == Instruction::GetElementPtr) {
862       SmallVector<Constant *, 8> Ops;
863       Ops.reserve(CE->getNumOperands());
864       for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
865         Constant *Op = CE->getOperand(i);
866         if (Op->getType()->isVectorTy()) {
867           Constant *ScalarOp = ConstantExpr::getExtractElement(Op, Idx);
868           if (!ScalarOp)
869             return nullptr;
870           Ops.push_back(ScalarOp);
871         } else
872           Ops.push_back(Op);
873       }
874       return CE->getWithOperands(Ops, ValVTy->getElementType(), false,
875                                  Ops[0]->getType()->getPointerElementType());
876     } else if (CE->getOpcode() == Instruction::InsertElement) {
877       if (const auto *IEIdx = dyn_cast<ConstantInt>(CE->getOperand(2))) {
878         if (APSInt::isSameValue(APSInt(IEIdx->getValue()),
879                                 APSInt(CIdx->getValue()))) {
880           return CE->getOperand(1);
881         } else {
882           return ConstantExpr::getExtractElement(CE->getOperand(0), CIdx);
883         }
884       }
885     }
886   }
887 
888   // CAZ of type ScalableVectorType and n < CAZ->getMinNumElements() =>
889   //   extractelt CAZ, n -> 0
890   if (auto *ValSVTy = dyn_cast<ScalableVectorType>(Val->getType())) {
891     if (!CIdx->uge(ValSVTy->getMinNumElements())) {
892       if (auto *CAZ = dyn_cast<ConstantAggregateZero>(Val))
893         return CAZ->getElementValue(CIdx->getZExtValue());
894     }
895     return nullptr;
896   }
897 
898   return Val->getAggregateElement(CIdx);
899 }
900 
901 Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val,
902                                                      Constant *Elt,
903                                                      Constant *Idx) {
904   if (isa<UndefValue>(Idx))
905     return PoisonValue::get(Val->getType());
906 
907   ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
908   if (!CIdx) return nullptr;
909 
910   // Do not iterate on scalable vector. The num of elements is unknown at
911   // compile-time.
912   if (isa<ScalableVectorType>(Val->getType()))
913     return nullptr;
914 
915   auto *ValTy = cast<FixedVectorType>(Val->getType());
916 
917   unsigned NumElts = ValTy->getNumElements();
918   if (CIdx->uge(NumElts))
919     return PoisonValue::get(Val->getType());
920 
921   SmallVector<Constant*, 16> Result;
922   Result.reserve(NumElts);
923   auto *Ty = Type::getInt32Ty(Val->getContext());
924   uint64_t IdxVal = CIdx->getZExtValue();
925   for (unsigned i = 0; i != NumElts; ++i) {
926     if (i == IdxVal) {
927       Result.push_back(Elt);
928       continue;
929     }
930 
931     Constant *C = ConstantExpr::getExtractElement(Val, ConstantInt::get(Ty, i));
932     Result.push_back(C);
933   }
934 
935   return ConstantVector::get(Result);
936 }
937 
938 Constant *llvm::ConstantFoldShuffleVectorInstruction(Constant *V1, Constant *V2,
939                                                      ArrayRef<int> Mask) {
940   auto *V1VTy = cast<VectorType>(V1->getType());
941   unsigned MaskNumElts = Mask.size();
942   auto MaskEltCount =
943       ElementCount::get(MaskNumElts, isa<ScalableVectorType>(V1VTy));
944   Type *EltTy = V1VTy->getElementType();
945 
946   // Undefined shuffle mask -> undefined value.
947   if (all_of(Mask, [](int Elt) { return Elt == UndefMaskElem; })) {
948     return UndefValue::get(FixedVectorType::get(EltTy, MaskNumElts));
949   }
950 
951   // If the mask is all zeros this is a splat, no need to go through all
952   // elements.
953   if (all_of(Mask, [](int Elt) { return Elt == 0; }) &&
954       !MaskEltCount.isScalable()) {
955     Type *Ty = IntegerType::get(V1->getContext(), 32);
956     Constant *Elt =
957         ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, 0));
958     return ConstantVector::getSplat(MaskEltCount, Elt);
959   }
960   // Do not iterate on scalable vector. The num of elements is unknown at
961   // compile-time.
962   if (isa<ScalableVectorType>(V1VTy))
963     return nullptr;
964 
965   unsigned SrcNumElts = V1VTy->getElementCount().getKnownMinValue();
966 
967   // Loop over the shuffle mask, evaluating each element.
968   SmallVector<Constant*, 32> Result;
969   for (unsigned i = 0; i != MaskNumElts; ++i) {
970     int Elt = Mask[i];
971     if (Elt == -1) {
972       Result.push_back(UndefValue::get(EltTy));
973       continue;
974     }
975     Constant *InElt;
976     if (unsigned(Elt) >= SrcNumElts*2)
977       InElt = UndefValue::get(EltTy);
978     else if (unsigned(Elt) >= SrcNumElts) {
979       Type *Ty = IntegerType::get(V2->getContext(), 32);
980       InElt =
981         ConstantExpr::getExtractElement(V2,
982                                         ConstantInt::get(Ty, Elt - SrcNumElts));
983     } else {
984       Type *Ty = IntegerType::get(V1->getContext(), 32);
985       InElt = ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, Elt));
986     }
987     Result.push_back(InElt);
988   }
989 
990   return ConstantVector::get(Result);
991 }
992 
993 Constant *llvm::ConstantFoldExtractValueInstruction(Constant *Agg,
994                                                     ArrayRef<unsigned> Idxs) {
995   // Base case: no indices, so return the entire value.
996   if (Idxs.empty())
997     return Agg;
998 
999   if (Constant *C = Agg->getAggregateElement(Idxs[0]))
1000     return ConstantFoldExtractValueInstruction(C, Idxs.slice(1));
1001 
1002   return nullptr;
1003 }
1004 
1005 Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg,
1006                                                    Constant *Val,
1007                                                    ArrayRef<unsigned> Idxs) {
1008   // Base case: no indices, so replace the entire value.
1009   if (Idxs.empty())
1010     return Val;
1011 
1012   unsigned NumElts;
1013   if (StructType *ST = dyn_cast<StructType>(Agg->getType()))
1014     NumElts = ST->getNumElements();
1015   else
1016     NumElts = cast<ArrayType>(Agg->getType())->getNumElements();
1017 
1018   SmallVector<Constant*, 32> Result;
1019   for (unsigned i = 0; i != NumElts; ++i) {
1020     Constant *C = Agg->getAggregateElement(i);
1021     if (!C) return nullptr;
1022 
1023     if (Idxs[0] == i)
1024       C = ConstantFoldInsertValueInstruction(C, Val, Idxs.slice(1));
1025 
1026     Result.push_back(C);
1027   }
1028 
1029   if (StructType *ST = dyn_cast<StructType>(Agg->getType()))
1030     return ConstantStruct::get(ST, Result);
1031   return ConstantArray::get(cast<ArrayType>(Agg->getType()), Result);
1032 }
1033 
1034 Constant *llvm::ConstantFoldUnaryInstruction(unsigned Opcode, Constant *C) {
1035   assert(Instruction::isUnaryOp(Opcode) && "Non-unary instruction detected");
1036 
1037   // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
1038   // vectors are always evaluated per element.
1039   bool IsScalableVector = isa<ScalableVectorType>(C->getType());
1040   bool HasScalarUndefOrScalableVectorUndef =
1041       (!C->getType()->isVectorTy() || IsScalableVector) && isa<UndefValue>(C);
1042 
1043   if (HasScalarUndefOrScalableVectorUndef) {
1044     switch (static_cast<Instruction::UnaryOps>(Opcode)) {
1045     case Instruction::FNeg:
1046       return C; // -undef -> undef
1047     case Instruction::UnaryOpsEnd:
1048       llvm_unreachable("Invalid UnaryOp");
1049     }
1050   }
1051 
1052   // Constant should not be UndefValue, unless these are vector constants.
1053   assert(!HasScalarUndefOrScalableVectorUndef && "Unexpected UndefValue");
1054   // We only have FP UnaryOps right now.
1055   assert(!isa<ConstantInt>(C) && "Unexpected Integer UnaryOp");
1056 
1057   if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
1058     const APFloat &CV = CFP->getValueAPF();
1059     switch (Opcode) {
1060     default:
1061       break;
1062     case Instruction::FNeg:
1063       return ConstantFP::get(C->getContext(), neg(CV));
1064     }
1065   } else if (auto *VTy = dyn_cast<FixedVectorType>(C->getType())) {
1066 
1067     Type *Ty = IntegerType::get(VTy->getContext(), 32);
1068     // Fast path for splatted constants.
1069     if (Constant *Splat = C->getSplatValue()) {
1070       Constant *Elt = ConstantExpr::get(Opcode, Splat);
1071       return ConstantVector::getSplat(VTy->getElementCount(), Elt);
1072     }
1073 
1074     // Fold each element and create a vector constant from those constants.
1075     SmallVector<Constant *, 16> Result;
1076     for (unsigned i = 0, e = VTy->getNumElements(); i != e; ++i) {
1077       Constant *ExtractIdx = ConstantInt::get(Ty, i);
1078       Constant *Elt = ConstantExpr::getExtractElement(C, ExtractIdx);
1079 
1080       Result.push_back(ConstantExpr::get(Opcode, Elt));
1081     }
1082 
1083     return ConstantVector::get(Result);
1084   }
1085 
1086   // We don't know how to fold this.
1087   return nullptr;
1088 }
1089 
1090 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, Constant *C1,
1091                                               Constant *C2) {
1092   assert(Instruction::isBinaryOp(Opcode) && "Non-binary instruction detected");
1093 
1094   // Simplify BinOps with their identity values first. They are no-ops and we
1095   // can always return the other value, including undef or poison values.
1096   // FIXME: remove unnecessary duplicated identity patterns below.
1097   // FIXME: Use AllowRHSConstant with getBinOpIdentity to handle additional ops,
1098   //        like X << 0 = X.
1099   Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, C1->getType());
1100   if (Identity) {
1101     if (C1 == Identity)
1102       return C2;
1103     if (C2 == Identity)
1104       return C1;
1105   }
1106 
1107   // Binary operations propagate poison.
1108   // FIXME: Currently, or/and i1 poison aren't folded into poison because
1109   // it causes miscompilation when combined with another optimization in
1110   // InstCombine (select i1 -> and/or). The select fold is wrong, but
1111   // fixing it requires an effort, so temporarily disable this until it is
1112   // fixed.
1113   bool PoisonFold = !C1->getType()->isIntegerTy(1) ||
1114                     (Opcode != Instruction::Or && Opcode != Instruction::And);
1115   if (PoisonFold && (isa<PoisonValue>(C1) || isa<PoisonValue>(C2)))
1116     return PoisonValue::get(C1->getType());
1117 
1118   // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
1119   // vectors are always evaluated per element.
1120   bool IsScalableVector = isa<ScalableVectorType>(C1->getType());
1121   bool HasScalarUndefOrScalableVectorUndef =
1122       (!C1->getType()->isVectorTy() || IsScalableVector) &&
1123       (isa<UndefValue>(C1) || isa<UndefValue>(C2));
1124   if (HasScalarUndefOrScalableVectorUndef) {
1125     switch (static_cast<Instruction::BinaryOps>(Opcode)) {
1126     case Instruction::Xor:
1127       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
1128         // Handle undef ^ undef -> 0 special case. This is a common
1129         // idiom (misuse).
1130         return Constant::getNullValue(C1->getType());
1131       LLVM_FALLTHROUGH;
1132     case Instruction::Add:
1133     case Instruction::Sub:
1134       return UndefValue::get(C1->getType());
1135     case Instruction::And:
1136       if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) // undef & undef -> undef
1137         return C1;
1138       return Constant::getNullValue(C1->getType());   // undef & X -> 0
1139     case Instruction::Mul: {
1140       // undef * undef -> undef
1141       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
1142         return C1;
1143       const APInt *CV;
1144       // X * undef -> undef   if X is odd
1145       if (match(C1, m_APInt(CV)) || match(C2, m_APInt(CV)))
1146         if ((*CV)[0])
1147           return UndefValue::get(C1->getType());
1148 
1149       // X * undef -> 0       otherwise
1150       return Constant::getNullValue(C1->getType());
1151     }
1152     case Instruction::SDiv:
1153     case Instruction::UDiv:
1154       // X / undef -> poison
1155       // X / 0 -> poison
1156       if (match(C2, m_CombineOr(m_Undef(), m_Zero())))
1157         return PoisonValue::get(C2->getType());
1158       // undef / 1 -> undef
1159       if (match(C2, m_One()))
1160         return C1;
1161       // undef / X -> 0       otherwise
1162       return Constant::getNullValue(C1->getType());
1163     case Instruction::URem:
1164     case Instruction::SRem:
1165       // X % undef -> poison
1166       // X % 0 -> poison
1167       if (match(C2, m_CombineOr(m_Undef(), m_Zero())))
1168         return PoisonValue::get(C2->getType());
1169       // undef % X -> 0       otherwise
1170       return Constant::getNullValue(C1->getType());
1171     case Instruction::Or:                          // X | undef -> -1
1172       if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) // undef | undef -> undef
1173         return C1;
1174       return Constant::getAllOnesValue(C1->getType()); // undef | X -> ~0
1175     case Instruction::LShr:
1176       // X >>l undef -> poison
1177       if (isa<UndefValue>(C2))
1178         return PoisonValue::get(C2->getType());
1179       // undef >>l 0 -> undef
1180       if (match(C2, m_Zero()))
1181         return C1;
1182       // undef >>l X -> 0
1183       return Constant::getNullValue(C1->getType());
1184     case Instruction::AShr:
1185       // X >>a undef -> poison
1186       if (isa<UndefValue>(C2))
1187         return PoisonValue::get(C2->getType());
1188       // undef >>a 0 -> undef
1189       if (match(C2, m_Zero()))
1190         return C1;
1191       // TODO: undef >>a X -> poison if the shift is exact
1192       // undef >>a X -> 0
1193       return Constant::getNullValue(C1->getType());
1194     case Instruction::Shl:
1195       // X << undef -> undef
1196       if (isa<UndefValue>(C2))
1197         return PoisonValue::get(C2->getType());
1198       // undef << 0 -> undef
1199       if (match(C2, m_Zero()))
1200         return C1;
1201       // undef << X -> 0
1202       return Constant::getNullValue(C1->getType());
1203     case Instruction::FSub:
1204       // -0.0 - undef --> undef (consistent with "fneg undef")
1205       if (match(C1, m_NegZeroFP()) && isa<UndefValue>(C2))
1206         return C2;
1207       LLVM_FALLTHROUGH;
1208     case Instruction::FAdd:
1209     case Instruction::FMul:
1210     case Instruction::FDiv:
1211     case Instruction::FRem:
1212       // [any flop] undef, undef -> undef
1213       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
1214         return C1;
1215       // [any flop] C, undef -> NaN
1216       // [any flop] undef, C -> NaN
1217       // We could potentially specialize NaN/Inf constants vs. 'normal'
1218       // constants (possibly differently depending on opcode and operand). This
1219       // would allow returning undef sometimes. But it is always safe to fold to
1220       // NaN because we can choose the undef operand as NaN, and any FP opcode
1221       // with a NaN operand will propagate NaN.
1222       return ConstantFP::getNaN(C1->getType());
1223     case Instruction::BinaryOpsEnd:
1224       llvm_unreachable("Invalid BinaryOp");
1225     }
1226   }
1227 
1228   // Neither constant should be UndefValue, unless these are vector constants.
1229   assert((!HasScalarUndefOrScalableVectorUndef) && "Unexpected UndefValue");
1230 
1231   // Handle simplifications when the RHS is a constant int.
1232   if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
1233     switch (Opcode) {
1234     case Instruction::Add:
1235       if (CI2->isZero()) return C1;                             // X + 0 == X
1236       break;
1237     case Instruction::Sub:
1238       if (CI2->isZero()) return C1;                             // X - 0 == X
1239       break;
1240     case Instruction::Mul:
1241       if (CI2->isZero()) return C2;                             // X * 0 == 0
1242       if (CI2->isOne())
1243         return C1;                                              // X * 1 == X
1244       break;
1245     case Instruction::UDiv:
1246     case Instruction::SDiv:
1247       if (CI2->isOne())
1248         return C1;                                            // X / 1 == X
1249       if (CI2->isZero())
1250         return PoisonValue::get(CI2->getType());              // X / 0 == poison
1251       break;
1252     case Instruction::URem:
1253     case Instruction::SRem:
1254       if (CI2->isOne())
1255         return Constant::getNullValue(CI2->getType());        // X % 1 == 0
1256       if (CI2->isZero())
1257         return PoisonValue::get(CI2->getType());              // X % 0 == poison
1258       break;
1259     case Instruction::And:
1260       if (CI2->isZero()) return C2;                           // X & 0 == 0
1261       if (CI2->isMinusOne())
1262         return C1;                                            // X & -1 == X
1263 
1264       if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
1265         // (zext i32 to i64) & 4294967295 -> (zext i32 to i64)
1266         if (CE1->getOpcode() == Instruction::ZExt) {
1267           unsigned DstWidth = CI2->getType()->getBitWidth();
1268           unsigned SrcWidth =
1269             CE1->getOperand(0)->getType()->getPrimitiveSizeInBits();
1270           APInt PossiblySetBits(APInt::getLowBitsSet(DstWidth, SrcWidth));
1271           if ((PossiblySetBits & CI2->getValue()) == PossiblySetBits)
1272             return C1;
1273         }
1274 
1275         // If and'ing the address of a global with a constant, fold it.
1276         if (CE1->getOpcode() == Instruction::PtrToInt &&
1277             isa<GlobalValue>(CE1->getOperand(0))) {
1278           GlobalValue *GV = cast<GlobalValue>(CE1->getOperand(0));
1279 
1280           MaybeAlign GVAlign;
1281 
1282           if (Module *TheModule = GV->getParent()) {
1283             const DataLayout &DL = TheModule->getDataLayout();
1284             GVAlign = GV->getPointerAlignment(DL);
1285 
1286             // If the function alignment is not specified then assume that it
1287             // is 4.
1288             // This is dangerous; on x86, the alignment of the pointer
1289             // corresponds to the alignment of the function, but might be less
1290             // than 4 if it isn't explicitly specified.
1291             // However, a fix for this behaviour was reverted because it
1292             // increased code size (see https://reviews.llvm.org/D55115)
1293             // FIXME: This code should be deleted once existing targets have
1294             // appropriate defaults
1295             if (isa<Function>(GV) && !DL.getFunctionPtrAlign())
1296               GVAlign = Align(4);
1297           } else if (isa<Function>(GV)) {
1298             // Without a datalayout we have to assume the worst case: that the
1299             // function pointer isn't aligned at all.
1300             GVAlign = llvm::None;
1301           } else if (isa<GlobalVariable>(GV)) {
1302             GVAlign = cast<GlobalVariable>(GV)->getAlign();
1303           }
1304 
1305           if (GVAlign && *GVAlign > 1) {
1306             unsigned DstWidth = CI2->getType()->getBitWidth();
1307             unsigned SrcWidth = std::min(DstWidth, Log2(*GVAlign));
1308             APInt BitsNotSet(APInt::getLowBitsSet(DstWidth, SrcWidth));
1309 
1310             // If checking bits we know are clear, return zero.
1311             if ((CI2->getValue() & BitsNotSet) == CI2->getValue())
1312               return Constant::getNullValue(CI2->getType());
1313           }
1314         }
1315       }
1316       break;
1317     case Instruction::Or:
1318       if (CI2->isZero()) return C1;        // X | 0 == X
1319       if (CI2->isMinusOne())
1320         return C2;                         // X | -1 == -1
1321       break;
1322     case Instruction::Xor:
1323       if (CI2->isZero()) return C1;        // X ^ 0 == X
1324 
1325       if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
1326         switch (CE1->getOpcode()) {
1327         default: break;
1328         case Instruction::ICmp:
1329         case Instruction::FCmp:
1330           // cmp pred ^ true -> cmp !pred
1331           assert(CI2->isOne());
1332           CmpInst::Predicate pred = (CmpInst::Predicate)CE1->getPredicate();
1333           pred = CmpInst::getInversePredicate(pred);
1334           return ConstantExpr::getCompare(pred, CE1->getOperand(0),
1335                                           CE1->getOperand(1));
1336         }
1337       }
1338       break;
1339     case Instruction::AShr:
1340       // ashr (zext C to Ty), C2 -> lshr (zext C, CSA), C2
1341       if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1))
1342         if (CE1->getOpcode() == Instruction::ZExt)  // Top bits known zero.
1343           return ConstantExpr::getLShr(C1, C2);
1344       break;
1345     }
1346   } else if (isa<ConstantInt>(C1)) {
1347     // If C1 is a ConstantInt and C2 is not, swap the operands.
1348     if (Instruction::isCommutative(Opcode))
1349       return ConstantExpr::get(Opcode, C2, C1);
1350   }
1351 
1352   if (ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) {
1353     if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
1354       const APInt &C1V = CI1->getValue();
1355       const APInt &C2V = CI2->getValue();
1356       switch (Opcode) {
1357       default:
1358         break;
1359       case Instruction::Add:
1360         return ConstantInt::get(CI1->getContext(), C1V + C2V);
1361       case Instruction::Sub:
1362         return ConstantInt::get(CI1->getContext(), C1V - C2V);
1363       case Instruction::Mul:
1364         return ConstantInt::get(CI1->getContext(), C1V * C2V);
1365       case Instruction::UDiv:
1366         assert(!CI2->isZero() && "Div by zero handled above");
1367         return ConstantInt::get(CI1->getContext(), C1V.udiv(C2V));
1368       case Instruction::SDiv:
1369         assert(!CI2->isZero() && "Div by zero handled above");
1370         if (C2V.isAllOnesValue() && C1V.isMinSignedValue())
1371           return PoisonValue::get(CI1->getType());   // MIN_INT / -1 -> poison
1372         return ConstantInt::get(CI1->getContext(), C1V.sdiv(C2V));
1373       case Instruction::URem:
1374         assert(!CI2->isZero() && "Div by zero handled above");
1375         return ConstantInt::get(CI1->getContext(), C1V.urem(C2V));
1376       case Instruction::SRem:
1377         assert(!CI2->isZero() && "Div by zero handled above");
1378         if (C2V.isAllOnesValue() && C1V.isMinSignedValue())
1379           return PoisonValue::get(CI1->getType());   // MIN_INT % -1 -> poison
1380         return ConstantInt::get(CI1->getContext(), C1V.srem(C2V));
1381       case Instruction::And:
1382         return ConstantInt::get(CI1->getContext(), C1V & C2V);
1383       case Instruction::Or:
1384         return ConstantInt::get(CI1->getContext(), C1V | C2V);
1385       case Instruction::Xor:
1386         return ConstantInt::get(CI1->getContext(), C1V ^ C2V);
1387       case Instruction::Shl:
1388         if (C2V.ult(C1V.getBitWidth()))
1389           return ConstantInt::get(CI1->getContext(), C1V.shl(C2V));
1390         return PoisonValue::get(C1->getType()); // too big shift is poison
1391       case Instruction::LShr:
1392         if (C2V.ult(C1V.getBitWidth()))
1393           return ConstantInt::get(CI1->getContext(), C1V.lshr(C2V));
1394         return PoisonValue::get(C1->getType()); // too big shift is poison
1395       case Instruction::AShr:
1396         if (C2V.ult(C1V.getBitWidth()))
1397           return ConstantInt::get(CI1->getContext(), C1V.ashr(C2V));
1398         return PoisonValue::get(C1->getType()); // too big shift is poison
1399       }
1400     }
1401 
1402     switch (Opcode) {
1403     case Instruction::SDiv:
1404     case Instruction::UDiv:
1405     case Instruction::URem:
1406     case Instruction::SRem:
1407     case Instruction::LShr:
1408     case Instruction::AShr:
1409     case Instruction::Shl:
1410       if (CI1->isZero()) return C1;
1411       break;
1412     default:
1413       break;
1414     }
1415   } else if (ConstantFP *CFP1 = dyn_cast<ConstantFP>(C1)) {
1416     if (ConstantFP *CFP2 = dyn_cast<ConstantFP>(C2)) {
1417       const APFloat &C1V = CFP1->getValueAPF();
1418       const APFloat &C2V = CFP2->getValueAPF();
1419       APFloat C3V = C1V;  // copy for modification
1420       switch (Opcode) {
1421       default:
1422         break;
1423       case Instruction::FAdd:
1424         (void)C3V.add(C2V, APFloat::rmNearestTiesToEven);
1425         return ConstantFP::get(C1->getContext(), C3V);
1426       case Instruction::FSub:
1427         (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven);
1428         return ConstantFP::get(C1->getContext(), C3V);
1429       case Instruction::FMul:
1430         (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven);
1431         return ConstantFP::get(C1->getContext(), C3V);
1432       case Instruction::FDiv:
1433         (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven);
1434         return ConstantFP::get(C1->getContext(), C3V);
1435       case Instruction::FRem:
1436         (void)C3V.mod(C2V);
1437         return ConstantFP::get(C1->getContext(), C3V);
1438       }
1439     }
1440   } else if (auto *VTy = dyn_cast<VectorType>(C1->getType())) {
1441     // Fast path for splatted constants.
1442     if (Constant *C2Splat = C2->getSplatValue()) {
1443       if (Instruction::isIntDivRem(Opcode) && C2Splat->isNullValue())
1444         return PoisonValue::get(VTy);
1445       if (Constant *C1Splat = C1->getSplatValue()) {
1446         return ConstantVector::getSplat(
1447             VTy->getElementCount(),
1448             ConstantExpr::get(Opcode, C1Splat, C2Splat));
1449       }
1450     }
1451 
1452     if (auto *FVTy = dyn_cast<FixedVectorType>(VTy)) {
1453       // Fold each element and create a vector constant from those constants.
1454       SmallVector<Constant*, 16> Result;
1455       Type *Ty = IntegerType::get(FVTy->getContext(), 32);
1456       for (unsigned i = 0, e = FVTy->getNumElements(); i != e; ++i) {
1457         Constant *ExtractIdx = ConstantInt::get(Ty, i);
1458         Constant *LHS = ConstantExpr::getExtractElement(C1, ExtractIdx);
1459         Constant *RHS = ConstantExpr::getExtractElement(C2, ExtractIdx);
1460 
1461         // If any element of a divisor vector is zero, the whole op is poison.
1462         if (Instruction::isIntDivRem(Opcode) && RHS->isNullValue())
1463           return PoisonValue::get(VTy);
1464 
1465         Result.push_back(ConstantExpr::get(Opcode, LHS, RHS));
1466       }
1467 
1468       return ConstantVector::get(Result);
1469     }
1470   }
1471 
1472   if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
1473     // There are many possible foldings we could do here.  We should probably
1474     // at least fold add of a pointer with an integer into the appropriate
1475     // getelementptr.  This will improve alias analysis a bit.
1476 
1477     // Given ((a + b) + c), if (b + c) folds to something interesting, return
1478     // (a + (b + c)).
1479     if (Instruction::isAssociative(Opcode) && CE1->getOpcode() == Opcode) {
1480       Constant *T = ConstantExpr::get(Opcode, CE1->getOperand(1), C2);
1481       if (!isa<ConstantExpr>(T) || cast<ConstantExpr>(T)->getOpcode() != Opcode)
1482         return ConstantExpr::get(Opcode, CE1->getOperand(0), T);
1483     }
1484   } else if (isa<ConstantExpr>(C2)) {
1485     // If C2 is a constant expr and C1 isn't, flop them around and fold the
1486     // other way if possible.
1487     if (Instruction::isCommutative(Opcode))
1488       return ConstantFoldBinaryInstruction(Opcode, C2, C1);
1489   }
1490 
1491   // i1 can be simplified in many cases.
1492   if (C1->getType()->isIntegerTy(1)) {
1493     switch (Opcode) {
1494     case Instruction::Add:
1495     case Instruction::Sub:
1496       return ConstantExpr::getXor(C1, C2);
1497     case Instruction::Mul:
1498       return ConstantExpr::getAnd(C1, C2);
1499     case Instruction::Shl:
1500     case Instruction::LShr:
1501     case Instruction::AShr:
1502       // We can assume that C2 == 0.  If it were one the result would be
1503       // undefined because the shift value is as large as the bitwidth.
1504       return C1;
1505     case Instruction::SDiv:
1506     case Instruction::UDiv:
1507       // We can assume that C2 == 1.  If it were zero the result would be
1508       // undefined through division by zero.
1509       return C1;
1510     case Instruction::URem:
1511     case Instruction::SRem:
1512       // We can assume that C2 == 1.  If it were zero the result would be
1513       // undefined through division by zero.
1514       return ConstantInt::getFalse(C1->getContext());
1515     default:
1516       break;
1517     }
1518   }
1519 
1520   // We don't know how to fold this.
1521   return nullptr;
1522 }
1523 
1524 /// This type is zero-sized if it's an array or structure of zero-sized types.
1525 /// The only leaf zero-sized type is an empty structure.
1526 static bool isMaybeZeroSizedType(Type *Ty) {
1527   if (StructType *STy = dyn_cast<StructType>(Ty)) {
1528     if (STy->isOpaque()) return true;  // Can't say.
1529 
1530     // If all of elements have zero size, this does too.
1531     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
1532       if (!isMaybeZeroSizedType(STy->getElementType(i))) return false;
1533     return true;
1534 
1535   } else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
1536     return isMaybeZeroSizedType(ATy->getElementType());
1537   }
1538   return false;
1539 }
1540 
1541 /// Compare the two constants as though they were getelementptr indices.
1542 /// This allows coercion of the types to be the same thing.
1543 ///
1544 /// If the two constants are the "same" (after coercion), return 0.  If the
1545 /// first is less than the second, return -1, if the second is less than the
1546 /// first, return 1.  If the constants are not integral, return -2.
1547 ///
1548 static int IdxCompare(Constant *C1, Constant *C2, Type *ElTy) {
1549   if (C1 == C2) return 0;
1550 
1551   // Ok, we found a different index.  If they are not ConstantInt, we can't do
1552   // anything with them.
1553   if (!isa<ConstantInt>(C1) || !isa<ConstantInt>(C2))
1554     return -2; // don't know!
1555 
1556   // We cannot compare the indices if they don't fit in an int64_t.
1557   if (cast<ConstantInt>(C1)->getValue().getActiveBits() > 64 ||
1558       cast<ConstantInt>(C2)->getValue().getActiveBits() > 64)
1559     return -2; // don't know!
1560 
1561   // Ok, we have two differing integer indices.  Sign extend them to be the same
1562   // type.
1563   int64_t C1Val = cast<ConstantInt>(C1)->getSExtValue();
1564   int64_t C2Val = cast<ConstantInt>(C2)->getSExtValue();
1565 
1566   if (C1Val == C2Val) return 0;  // They are equal
1567 
1568   // If the type being indexed over is really just a zero sized type, there is
1569   // no pointer difference being made here.
1570   if (isMaybeZeroSizedType(ElTy))
1571     return -2; // dunno.
1572 
1573   // If they are really different, now that they are the same type, then we
1574   // found a difference!
1575   if (C1Val < C2Val)
1576     return -1;
1577   else
1578     return 1;
1579 }
1580 
1581 /// This function determines if there is anything we can decide about the two
1582 /// constants provided. This doesn't need to handle simple things like
1583 /// ConstantFP comparisons, but should instead handle ConstantExprs.
1584 /// If we can determine that the two constants have a particular relation to
1585 /// each other, we should return the corresponding FCmpInst predicate,
1586 /// otherwise return FCmpInst::BAD_FCMP_PREDICATE. This is used below in
1587 /// ConstantFoldCompareInstruction.
1588 ///
1589 /// To simplify this code we canonicalize the relation so that the first
1590 /// operand is always the most "complex" of the two.  We consider ConstantFP
1591 /// to be the simplest, and ConstantExprs to be the most complex.
1592 static FCmpInst::Predicate evaluateFCmpRelation(Constant *V1, Constant *V2) {
1593   assert(V1->getType() == V2->getType() &&
1594          "Cannot compare values of different types!");
1595 
1596   // We do not know if a constant expression will evaluate to a number or NaN.
1597   // Therefore, we can only say that the relation is unordered or equal.
1598   if (V1 == V2) return FCmpInst::FCMP_UEQ;
1599 
1600   if (!isa<ConstantExpr>(V1)) {
1601     if (!isa<ConstantExpr>(V2)) {
1602       // Simple case, use the standard constant folder.
1603       ConstantInt *R = nullptr;
1604       R = dyn_cast<ConstantInt>(
1605                       ConstantExpr::getFCmp(FCmpInst::FCMP_OEQ, V1, V2));
1606       if (R && !R->isZero())
1607         return FCmpInst::FCMP_OEQ;
1608       R = dyn_cast<ConstantInt>(
1609                       ConstantExpr::getFCmp(FCmpInst::FCMP_OLT, V1, V2));
1610       if (R && !R->isZero())
1611         return FCmpInst::FCMP_OLT;
1612       R = dyn_cast<ConstantInt>(
1613                       ConstantExpr::getFCmp(FCmpInst::FCMP_OGT, V1, V2));
1614       if (R && !R->isZero())
1615         return FCmpInst::FCMP_OGT;
1616 
1617       // Nothing more we can do
1618       return FCmpInst::BAD_FCMP_PREDICATE;
1619     }
1620 
1621     // If the first operand is simple and second is ConstantExpr, swap operands.
1622     FCmpInst::Predicate SwappedRelation = evaluateFCmpRelation(V2, V1);
1623     if (SwappedRelation != FCmpInst::BAD_FCMP_PREDICATE)
1624       return FCmpInst::getSwappedPredicate(SwappedRelation);
1625   } else {
1626     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
1627     // constantexpr or a simple constant.
1628     ConstantExpr *CE1 = cast<ConstantExpr>(V1);
1629     switch (CE1->getOpcode()) {
1630     case Instruction::FPTrunc:
1631     case Instruction::FPExt:
1632     case Instruction::UIToFP:
1633     case Instruction::SIToFP:
1634       // We might be able to do something with these but we don't right now.
1635       break;
1636     default:
1637       break;
1638     }
1639   }
1640   // There are MANY other foldings that we could perform here.  They will
1641   // probably be added on demand, as they seem needed.
1642   return FCmpInst::BAD_FCMP_PREDICATE;
1643 }
1644 
1645 static ICmpInst::Predicate areGlobalsPotentiallyEqual(const GlobalValue *GV1,
1646                                                       const GlobalValue *GV2) {
1647   auto isGlobalUnsafeForEquality = [](const GlobalValue *GV) {
1648     if (GV->isInterposable() || GV->hasGlobalUnnamedAddr())
1649       return true;
1650     if (const auto *GVar = dyn_cast<GlobalVariable>(GV)) {
1651       Type *Ty = GVar->getValueType();
1652       // A global with opaque type might end up being zero sized.
1653       if (!Ty->isSized())
1654         return true;
1655       // A global with an empty type might lie at the address of any other
1656       // global.
1657       if (Ty->isEmptyTy())
1658         return true;
1659     }
1660     return false;
1661   };
1662   // Don't try to decide equality of aliases.
1663   if (!isa<GlobalAlias>(GV1) && !isa<GlobalAlias>(GV2))
1664     if (!isGlobalUnsafeForEquality(GV1) && !isGlobalUnsafeForEquality(GV2))
1665       return ICmpInst::ICMP_NE;
1666   return ICmpInst::BAD_ICMP_PREDICATE;
1667 }
1668 
1669 /// This function determines if there is anything we can decide about the two
1670 /// constants provided. This doesn't need to handle simple things like integer
1671 /// comparisons, but should instead handle ConstantExprs and GlobalValues.
1672 /// If we can determine that the two constants have a particular relation to
1673 /// each other, we should return the corresponding ICmp predicate, otherwise
1674 /// return ICmpInst::BAD_ICMP_PREDICATE.
1675 ///
1676 /// To simplify this code we canonicalize the relation so that the first
1677 /// operand is always the most "complex" of the two.  We consider simple
1678 /// constants (like ConstantInt) to be the simplest, followed by
1679 /// GlobalValues, followed by ConstantExpr's (the most complex).
1680 ///
1681 static ICmpInst::Predicate evaluateICmpRelation(Constant *V1, Constant *V2,
1682                                                 bool isSigned) {
1683   assert(V1->getType() == V2->getType() &&
1684          "Cannot compare different types of values!");
1685   if (V1 == V2) return ICmpInst::ICMP_EQ;
1686 
1687   if (!isa<ConstantExpr>(V1) && !isa<GlobalValue>(V1) &&
1688       !isa<BlockAddress>(V1)) {
1689     if (!isa<GlobalValue>(V2) && !isa<ConstantExpr>(V2) &&
1690         !isa<BlockAddress>(V2)) {
1691       // We distilled this down to a simple case, use the standard constant
1692       // folder.
1693       ConstantInt *R = nullptr;
1694       ICmpInst::Predicate pred = ICmpInst::ICMP_EQ;
1695       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2));
1696       if (R && !R->isZero())
1697         return pred;
1698       pred = isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1699       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2));
1700       if (R && !R->isZero())
1701         return pred;
1702       pred = isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1703       R = dyn_cast<ConstantInt>(ConstantExpr::getICmp(pred, V1, V2));
1704       if (R && !R->isZero())
1705         return pred;
1706 
1707       // If we couldn't figure it out, bail.
1708       return ICmpInst::BAD_ICMP_PREDICATE;
1709     }
1710 
1711     // If the first operand is simple, swap operands.
1712     ICmpInst::Predicate SwappedRelation =
1713       evaluateICmpRelation(V2, V1, isSigned);
1714     if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
1715       return ICmpInst::getSwappedPredicate(SwappedRelation);
1716 
1717   } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1)) {
1718     if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
1719       ICmpInst::Predicate SwappedRelation =
1720         evaluateICmpRelation(V2, V1, isSigned);
1721       if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
1722         return ICmpInst::getSwappedPredicate(SwappedRelation);
1723       return ICmpInst::BAD_ICMP_PREDICATE;
1724     }
1725 
1726     // Now we know that the RHS is a GlobalValue, BlockAddress or simple
1727     // constant (which, since the types must match, means that it's a
1728     // ConstantPointerNull).
1729     if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) {
1730       return areGlobalsPotentiallyEqual(GV, GV2);
1731     } else if (isa<BlockAddress>(V2)) {
1732       return ICmpInst::ICMP_NE; // Globals never equal labels.
1733     } else {
1734       assert(isa<ConstantPointerNull>(V2) && "Canonicalization guarantee!");
1735       // GlobalVals can never be null unless they have external weak linkage.
1736       // We don't try to evaluate aliases here.
1737       // NOTE: We should not be doing this constant folding if null pointer
1738       // is considered valid for the function. But currently there is no way to
1739       // query it from the Constant type.
1740       if (!GV->hasExternalWeakLinkage() && !isa<GlobalAlias>(GV) &&
1741           !NullPointerIsDefined(nullptr /* F */,
1742                                 GV->getType()->getAddressSpace()))
1743         return ICmpInst::ICMP_NE;
1744     }
1745   } else if (const BlockAddress *BA = dyn_cast<BlockAddress>(V1)) {
1746     if (isa<ConstantExpr>(V2)) {  // Swap as necessary.
1747       ICmpInst::Predicate SwappedRelation =
1748         evaluateICmpRelation(V2, V1, isSigned);
1749       if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
1750         return ICmpInst::getSwappedPredicate(SwappedRelation);
1751       return ICmpInst::BAD_ICMP_PREDICATE;
1752     }
1753 
1754     // Now we know that the RHS is a GlobalValue, BlockAddress or simple
1755     // constant (which, since the types must match, means that it is a
1756     // ConstantPointerNull).
1757     if (const BlockAddress *BA2 = dyn_cast<BlockAddress>(V2)) {
1758       // Block address in another function can't equal this one, but block
1759       // addresses in the current function might be the same if blocks are
1760       // empty.
1761       if (BA2->getFunction() != BA->getFunction())
1762         return ICmpInst::ICMP_NE;
1763     } else {
1764       // Block addresses aren't null, don't equal the address of globals.
1765       assert((isa<ConstantPointerNull>(V2) || isa<GlobalValue>(V2)) &&
1766              "Canonicalization guarantee!");
1767       return ICmpInst::ICMP_NE;
1768     }
1769   } else {
1770     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
1771     // constantexpr, a global, block address, or a simple constant.
1772     ConstantExpr *CE1 = cast<ConstantExpr>(V1);
1773     Constant *CE1Op0 = CE1->getOperand(0);
1774 
1775     switch (CE1->getOpcode()) {
1776     case Instruction::Trunc:
1777     case Instruction::FPTrunc:
1778     case Instruction::FPExt:
1779     case Instruction::FPToUI:
1780     case Instruction::FPToSI:
1781       break; // We can't evaluate floating point casts or truncations.
1782 
1783     case Instruction::BitCast:
1784       // If this is a global value cast, check to see if the RHS is also a
1785       // GlobalValue.
1786       if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0))
1787         if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2))
1788           return areGlobalsPotentiallyEqual(GV, GV2);
1789       LLVM_FALLTHROUGH;
1790     case Instruction::UIToFP:
1791     case Instruction::SIToFP:
1792     case Instruction::ZExt:
1793     case Instruction::SExt:
1794       // We can't evaluate floating point casts or truncations.
1795       if (CE1Op0->getType()->isFPOrFPVectorTy())
1796         break;
1797 
1798       // If the cast is not actually changing bits, and the second operand is a
1799       // null pointer, do the comparison with the pre-casted value.
1800       if (V2->isNullValue() && CE1->getType()->isIntOrPtrTy()) {
1801         if (CE1->getOpcode() == Instruction::ZExt) isSigned = false;
1802         if (CE1->getOpcode() == Instruction::SExt) isSigned = true;
1803         return evaluateICmpRelation(CE1Op0,
1804                                     Constant::getNullValue(CE1Op0->getType()),
1805                                     isSigned);
1806       }
1807       break;
1808 
1809     case Instruction::GetElementPtr: {
1810       GEPOperator *CE1GEP = cast<GEPOperator>(CE1);
1811       // Ok, since this is a getelementptr, we know that the constant has a
1812       // pointer type.  Check the various cases.
1813       if (isa<ConstantPointerNull>(V2)) {
1814         // If we are comparing a GEP to a null pointer, check to see if the base
1815         // of the GEP equals the null pointer.
1816         if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
1817           if (GV->hasExternalWeakLinkage())
1818             // Weak linkage GVals could be zero or not. We're comparing that
1819             // to null pointer so its greater-or-equal
1820             return isSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
1821           else
1822             // If its not weak linkage, the GVal must have a non-zero address
1823             // so the result is greater-than
1824             return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1825         } else if (isa<ConstantPointerNull>(CE1Op0)) {
1826           // If we are indexing from a null pointer, check to see if we have any
1827           // non-zero indices.
1828           for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
1829             if (!CE1->getOperand(i)->isNullValue())
1830               // Offsetting from null, must not be equal.
1831               return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1832           // Only zero indexes from null, must still be zero.
1833           return ICmpInst::ICMP_EQ;
1834         }
1835         // Otherwise, we can't really say if the first operand is null or not.
1836       } else if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) {
1837         if (isa<ConstantPointerNull>(CE1Op0)) {
1838           if (GV2->hasExternalWeakLinkage())
1839             // Weak linkage GVals could be zero or not. We're comparing it to
1840             // a null pointer, so its less-or-equal
1841             return isSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
1842           else
1843             // If its not weak linkage, the GVal must have a non-zero address
1844             // so the result is less-than
1845             return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1846         } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
1847           if (GV == GV2) {
1848             // If this is a getelementptr of the same global, then it must be
1849             // different.  Because the types must match, the getelementptr could
1850             // only have at most one index, and because we fold getelementptr's
1851             // with a single zero index, it must be nonzero.
1852             assert(CE1->getNumOperands() == 2 &&
1853                    !CE1->getOperand(1)->isNullValue() &&
1854                    "Surprising getelementptr!");
1855             return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1856           } else {
1857             if (CE1GEP->hasAllZeroIndices())
1858               return areGlobalsPotentiallyEqual(GV, GV2);
1859             return ICmpInst::BAD_ICMP_PREDICATE;
1860           }
1861         }
1862       } else {
1863         ConstantExpr *CE2 = cast<ConstantExpr>(V2);
1864         Constant *CE2Op0 = CE2->getOperand(0);
1865 
1866         // There are MANY other foldings that we could perform here.  They will
1867         // probably be added on demand, as they seem needed.
1868         switch (CE2->getOpcode()) {
1869         default: break;
1870         case Instruction::GetElementPtr:
1871           // By far the most common case to handle is when the base pointers are
1872           // obviously to the same global.
1873           if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1874             // Don't know relative ordering, but check for inequality.
1875             if (CE1Op0 != CE2Op0) {
1876               GEPOperator *CE2GEP = cast<GEPOperator>(CE2);
1877               if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices())
1878                 return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0),
1879                                                   cast<GlobalValue>(CE2Op0));
1880               return ICmpInst::BAD_ICMP_PREDICATE;
1881             }
1882             // Ok, we know that both getelementptr instructions are based on the
1883             // same global.  From this, we can precisely determine the relative
1884             // ordering of the resultant pointers.
1885             unsigned i = 1;
1886 
1887             // The logic below assumes that the result of the comparison
1888             // can be determined by finding the first index that differs.
1889             // This doesn't work if there is over-indexing in any
1890             // subsequent indices, so check for that case first.
1891             if (!CE1->isGEPWithNoNotionalOverIndexing() ||
1892                 !CE2->isGEPWithNoNotionalOverIndexing())
1893                return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
1894 
1895             // Compare all of the operands the GEP's have in common.
1896             gep_type_iterator GTI = gep_type_begin(CE1);
1897             for (;i != CE1->getNumOperands() && i != CE2->getNumOperands();
1898                  ++i, ++GTI)
1899               switch (IdxCompare(CE1->getOperand(i),
1900                                  CE2->getOperand(i), GTI.getIndexedType())) {
1901               case -1: return isSigned ? ICmpInst::ICMP_SLT:ICmpInst::ICMP_ULT;
1902               case 1:  return isSigned ? ICmpInst::ICMP_SGT:ICmpInst::ICMP_UGT;
1903               case -2: return ICmpInst::BAD_ICMP_PREDICATE;
1904               }
1905 
1906             // Ok, we ran out of things they have in common.  If any leftovers
1907             // are non-zero then we have a difference, otherwise we are equal.
1908             for (; i < CE1->getNumOperands(); ++i)
1909               if (!CE1->getOperand(i)->isNullValue()) {
1910                 if (isa<ConstantInt>(CE1->getOperand(i)))
1911                   return isSigned ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
1912                 else
1913                   return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
1914               }
1915 
1916             for (; i < CE2->getNumOperands(); ++i)
1917               if (!CE2->getOperand(i)->isNullValue()) {
1918                 if (isa<ConstantInt>(CE2->getOperand(i)))
1919                   return isSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
1920                 else
1921                   return ICmpInst::BAD_ICMP_PREDICATE; // Might be equal.
1922               }
1923             return ICmpInst::ICMP_EQ;
1924           }
1925         }
1926       }
1927       break;
1928     }
1929     default:
1930       break;
1931     }
1932   }
1933 
1934   return ICmpInst::BAD_ICMP_PREDICATE;
1935 }
1936 
1937 Constant *llvm::ConstantFoldCompareInstruction(unsigned short pred,
1938                                                Constant *C1, Constant *C2) {
1939   Type *ResultTy;
1940   if (VectorType *VT = dyn_cast<VectorType>(C1->getType()))
1941     ResultTy = VectorType::get(Type::getInt1Ty(C1->getContext()),
1942                                VT->getElementCount());
1943   else
1944     ResultTy = Type::getInt1Ty(C1->getContext());
1945 
1946   // Fold FCMP_FALSE/FCMP_TRUE unconditionally.
1947   if (pred == FCmpInst::FCMP_FALSE)
1948     return Constant::getNullValue(ResultTy);
1949 
1950   if (pred == FCmpInst::FCMP_TRUE)
1951     return Constant::getAllOnesValue(ResultTy);
1952 
1953   // Handle some degenerate cases first
1954   if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))
1955     return PoisonValue::get(ResultTy);
1956 
1957   if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) {
1958     CmpInst::Predicate Predicate = CmpInst::Predicate(pred);
1959     bool isIntegerPredicate = ICmpInst::isIntPredicate(Predicate);
1960     // For EQ and NE, we can always pick a value for the undef to make the
1961     // predicate pass or fail, so we can return undef.
1962     // Also, if both operands are undef, we can return undef for int comparison.
1963     if (ICmpInst::isEquality(Predicate) || (isIntegerPredicate && C1 == C2))
1964       return UndefValue::get(ResultTy);
1965 
1966     // Otherwise, for integer compare, pick the same value as the non-undef
1967     // operand, and fold it to true or false.
1968     if (isIntegerPredicate)
1969       return ConstantInt::get(ResultTy, CmpInst::isTrueWhenEqual(Predicate));
1970 
1971     // Choosing NaN for the undef will always make unordered comparison succeed
1972     // and ordered comparison fails.
1973     return ConstantInt::get(ResultTy, CmpInst::isUnordered(Predicate));
1974   }
1975 
1976   // icmp eq/ne(null,GV) -> false/true
1977   if (C1->isNullValue()) {
1978     if (const GlobalValue *GV = dyn_cast<GlobalValue>(C2))
1979       // Don't try to evaluate aliases.  External weak GV can be null.
1980       if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage() &&
1981           !NullPointerIsDefined(nullptr /* F */,
1982                                 GV->getType()->getAddressSpace())) {
1983         if (pred == ICmpInst::ICMP_EQ)
1984           return ConstantInt::getFalse(C1->getContext());
1985         else if (pred == ICmpInst::ICMP_NE)
1986           return ConstantInt::getTrue(C1->getContext());
1987       }
1988   // icmp eq/ne(GV,null) -> false/true
1989   } else if (C2->isNullValue()) {
1990     if (const GlobalValue *GV = dyn_cast<GlobalValue>(C1))
1991       // Don't try to evaluate aliases.  External weak GV can be null.
1992       if (!isa<GlobalAlias>(GV) && !GV->hasExternalWeakLinkage() &&
1993           !NullPointerIsDefined(nullptr /* F */,
1994                                 GV->getType()->getAddressSpace())) {
1995         if (pred == ICmpInst::ICMP_EQ)
1996           return ConstantInt::getFalse(C1->getContext());
1997         else if (pred == ICmpInst::ICMP_NE)
1998           return ConstantInt::getTrue(C1->getContext());
1999       }
2000   }
2001 
2002   // If the comparison is a comparison between two i1's, simplify it.
2003   if (C1->getType()->isIntegerTy(1)) {
2004     switch(pred) {
2005     case ICmpInst::ICMP_EQ:
2006       if (isa<ConstantInt>(C2))
2007         return ConstantExpr::getXor(C1, ConstantExpr::getNot(C2));
2008       return ConstantExpr::getXor(ConstantExpr::getNot(C1), C2);
2009     case ICmpInst::ICMP_NE:
2010       return ConstantExpr::getXor(C1, C2);
2011     default:
2012       break;
2013     }
2014   }
2015 
2016   if (isa<ConstantInt>(C1) && isa<ConstantInt>(C2)) {
2017     const APInt &V1 = cast<ConstantInt>(C1)->getValue();
2018     const APInt &V2 = cast<ConstantInt>(C2)->getValue();
2019     switch (pred) {
2020     default: llvm_unreachable("Invalid ICmp Predicate");
2021     case ICmpInst::ICMP_EQ:  return ConstantInt::get(ResultTy, V1 == V2);
2022     case ICmpInst::ICMP_NE:  return ConstantInt::get(ResultTy, V1 != V2);
2023     case ICmpInst::ICMP_SLT: return ConstantInt::get(ResultTy, V1.slt(V2));
2024     case ICmpInst::ICMP_SGT: return ConstantInt::get(ResultTy, V1.sgt(V2));
2025     case ICmpInst::ICMP_SLE: return ConstantInt::get(ResultTy, V1.sle(V2));
2026     case ICmpInst::ICMP_SGE: return ConstantInt::get(ResultTy, V1.sge(V2));
2027     case ICmpInst::ICMP_ULT: return ConstantInt::get(ResultTy, V1.ult(V2));
2028     case ICmpInst::ICMP_UGT: return ConstantInt::get(ResultTy, V1.ugt(V2));
2029     case ICmpInst::ICMP_ULE: return ConstantInt::get(ResultTy, V1.ule(V2));
2030     case ICmpInst::ICMP_UGE: return ConstantInt::get(ResultTy, V1.uge(V2));
2031     }
2032   } else if (isa<ConstantFP>(C1) && isa<ConstantFP>(C2)) {
2033     const APFloat &C1V = cast<ConstantFP>(C1)->getValueAPF();
2034     const APFloat &C2V = cast<ConstantFP>(C2)->getValueAPF();
2035     APFloat::cmpResult R = C1V.compare(C2V);
2036     switch (pred) {
2037     default: llvm_unreachable("Invalid FCmp Predicate");
2038     case FCmpInst::FCMP_FALSE: return Constant::getNullValue(ResultTy);
2039     case FCmpInst::FCMP_TRUE:  return Constant::getAllOnesValue(ResultTy);
2040     case FCmpInst::FCMP_UNO:
2041       return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered);
2042     case FCmpInst::FCMP_ORD:
2043       return ConstantInt::get(ResultTy, R!=APFloat::cmpUnordered);
2044     case FCmpInst::FCMP_UEQ:
2045       return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered ||
2046                                         R==APFloat::cmpEqual);
2047     case FCmpInst::FCMP_OEQ:
2048       return ConstantInt::get(ResultTy, R==APFloat::cmpEqual);
2049     case FCmpInst::FCMP_UNE:
2050       return ConstantInt::get(ResultTy, R!=APFloat::cmpEqual);
2051     case FCmpInst::FCMP_ONE:
2052       return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan ||
2053                                         R==APFloat::cmpGreaterThan);
2054     case FCmpInst::FCMP_ULT:
2055       return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered ||
2056                                         R==APFloat::cmpLessThan);
2057     case FCmpInst::FCMP_OLT:
2058       return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan);
2059     case FCmpInst::FCMP_UGT:
2060       return ConstantInt::get(ResultTy, R==APFloat::cmpUnordered ||
2061                                         R==APFloat::cmpGreaterThan);
2062     case FCmpInst::FCMP_OGT:
2063       return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan);
2064     case FCmpInst::FCMP_ULE:
2065       return ConstantInt::get(ResultTy, R!=APFloat::cmpGreaterThan);
2066     case FCmpInst::FCMP_OLE:
2067       return ConstantInt::get(ResultTy, R==APFloat::cmpLessThan ||
2068                                         R==APFloat::cmpEqual);
2069     case FCmpInst::FCMP_UGE:
2070       return ConstantInt::get(ResultTy, R!=APFloat::cmpLessThan);
2071     case FCmpInst::FCMP_OGE:
2072       return ConstantInt::get(ResultTy, R==APFloat::cmpGreaterThan ||
2073                                         R==APFloat::cmpEqual);
2074     }
2075   } else if (auto *C1VTy = dyn_cast<VectorType>(C1->getType())) {
2076 
2077     // Fast path for splatted constants.
2078     if (Constant *C1Splat = C1->getSplatValue())
2079       if (Constant *C2Splat = C2->getSplatValue())
2080         return ConstantVector::getSplat(
2081             C1VTy->getElementCount(),
2082             ConstantExpr::getCompare(pred, C1Splat, C2Splat));
2083 
2084     // Do not iterate on scalable vector. The number of elements is unknown at
2085     // compile-time.
2086     if (isa<ScalableVectorType>(C1VTy))
2087       return nullptr;
2088 
2089     // If we can constant fold the comparison of each element, constant fold
2090     // the whole vector comparison.
2091     SmallVector<Constant*, 4> ResElts;
2092     Type *Ty = IntegerType::get(C1->getContext(), 32);
2093     // Compare the elements, producing an i1 result or constant expr.
2094     for (unsigned I = 0, E = C1VTy->getElementCount().getKnownMinValue();
2095          I != E; ++I) {
2096       Constant *C1E =
2097           ConstantExpr::getExtractElement(C1, ConstantInt::get(Ty, I));
2098       Constant *C2E =
2099           ConstantExpr::getExtractElement(C2, ConstantInt::get(Ty, I));
2100 
2101       ResElts.push_back(ConstantExpr::getCompare(pred, C1E, C2E));
2102     }
2103 
2104     return ConstantVector::get(ResElts);
2105   }
2106 
2107   if (C1->getType()->isFloatingPointTy() &&
2108       // Only call evaluateFCmpRelation if we have a constant expr to avoid
2109       // infinite recursive loop
2110       (isa<ConstantExpr>(C1) || isa<ConstantExpr>(C2))) {
2111     int Result = -1;  // -1 = unknown, 0 = known false, 1 = known true.
2112     switch (evaluateFCmpRelation(C1, C2)) {
2113     default: llvm_unreachable("Unknown relation!");
2114     case FCmpInst::FCMP_UNO:
2115     case FCmpInst::FCMP_ORD:
2116     case FCmpInst::FCMP_UNE:
2117     case FCmpInst::FCMP_ULT:
2118     case FCmpInst::FCMP_UGT:
2119     case FCmpInst::FCMP_ULE:
2120     case FCmpInst::FCMP_UGE:
2121     case FCmpInst::FCMP_TRUE:
2122     case FCmpInst::FCMP_FALSE:
2123     case FCmpInst::BAD_FCMP_PREDICATE:
2124       break; // Couldn't determine anything about these constants.
2125     case FCmpInst::FCMP_OEQ: // We know that C1 == C2
2126       Result = (pred == FCmpInst::FCMP_UEQ || pred == FCmpInst::FCMP_OEQ ||
2127                 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE ||
2128                 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE);
2129       break;
2130     case FCmpInst::FCMP_OLT: // We know that C1 < C2
2131       Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE ||
2132                 pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT ||
2133                 pred == FCmpInst::FCMP_ULE || pred == FCmpInst::FCMP_OLE);
2134       break;
2135     case FCmpInst::FCMP_OGT: // We know that C1 > C2
2136       Result = (pred == FCmpInst::FCMP_UNE || pred == FCmpInst::FCMP_ONE ||
2137                 pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT ||
2138                 pred == FCmpInst::FCMP_UGE || pred == FCmpInst::FCMP_OGE);
2139       break;
2140     case FCmpInst::FCMP_OLE: // We know that C1 <= C2
2141       // We can only partially decide this relation.
2142       if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT)
2143         Result = 0;
2144       else if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT)
2145         Result = 1;
2146       break;
2147     case FCmpInst::FCMP_OGE: // We known that C1 >= C2
2148       // We can only partially decide this relation.
2149       if (pred == FCmpInst::FCMP_ULT || pred == FCmpInst::FCMP_OLT)
2150         Result = 0;
2151       else if (pred == FCmpInst::FCMP_UGT || pred == FCmpInst::FCMP_OGT)
2152         Result = 1;
2153       break;
2154     case FCmpInst::FCMP_ONE: // We know that C1 != C2
2155       // We can only partially decide this relation.
2156       if (pred == FCmpInst::FCMP_OEQ || pred == FCmpInst::FCMP_UEQ)
2157         Result = 0;
2158       else if (pred == FCmpInst::FCMP_ONE || pred == FCmpInst::FCMP_UNE)
2159         Result = 1;
2160       break;
2161     case FCmpInst::FCMP_UEQ: // We know that C1 == C2 || isUnordered(C1, C2).
2162       // We can only partially decide this relation.
2163       if (pred == FCmpInst::FCMP_ONE)
2164         Result = 0;
2165       else if (pred == FCmpInst::FCMP_UEQ)
2166         Result = 1;
2167       break;
2168     }
2169 
2170     // If we evaluated the result, return it now.
2171     if (Result != -1)
2172       return ConstantInt::get(ResultTy, Result);
2173 
2174   } else {
2175     // Evaluate the relation between the two constants, per the predicate.
2176     int Result = -1;  // -1 = unknown, 0 = known false, 1 = known true.
2177     switch (evaluateICmpRelation(C1, C2,
2178                                  CmpInst::isSigned((CmpInst::Predicate)pred))) {
2179     default: llvm_unreachable("Unknown relational!");
2180     case ICmpInst::BAD_ICMP_PREDICATE:
2181       break;  // Couldn't determine anything about these constants.
2182     case ICmpInst::ICMP_EQ:   // We know the constants are equal!
2183       // If we know the constants are equal, we can decide the result of this
2184       // computation precisely.
2185       Result = ICmpInst::isTrueWhenEqual((ICmpInst::Predicate)pred);
2186       break;
2187     case ICmpInst::ICMP_ULT:
2188       switch (pred) {
2189       case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULE:
2190         Result = 1; break;
2191       case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_UGE:
2192         Result = 0; break;
2193       }
2194       break;
2195     case ICmpInst::ICMP_SLT:
2196       switch (pred) {
2197       case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SLE:
2198         Result = 1; break;
2199       case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SGE:
2200         Result = 0; break;
2201       }
2202       break;
2203     case ICmpInst::ICMP_UGT:
2204       switch (pred) {
2205       case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGE:
2206         Result = 1; break;
2207       case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULE:
2208         Result = 0; break;
2209       }
2210       break;
2211     case ICmpInst::ICMP_SGT:
2212       switch (pred) {
2213       case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SGE:
2214         Result = 1; break;
2215       case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SLE:
2216         Result = 0; break;
2217       }
2218       break;
2219     case ICmpInst::ICMP_ULE:
2220       if (pred == ICmpInst::ICMP_UGT) Result = 0;
2221       if (pred == ICmpInst::ICMP_ULT || pred == ICmpInst::ICMP_ULE) Result = 1;
2222       break;
2223     case ICmpInst::ICMP_SLE:
2224       if (pred == ICmpInst::ICMP_SGT) Result = 0;
2225       if (pred == ICmpInst::ICMP_SLT || pred == ICmpInst::ICMP_SLE) Result = 1;
2226       break;
2227     case ICmpInst::ICMP_UGE:
2228       if (pred == ICmpInst::ICMP_ULT) Result = 0;
2229       if (pred == ICmpInst::ICMP_UGT || pred == ICmpInst::ICMP_UGE) Result = 1;
2230       break;
2231     case ICmpInst::ICMP_SGE:
2232       if (pred == ICmpInst::ICMP_SLT) Result = 0;
2233       if (pred == ICmpInst::ICMP_SGT || pred == ICmpInst::ICMP_SGE) Result = 1;
2234       break;
2235     case ICmpInst::ICMP_NE:
2236       if (pred == ICmpInst::ICMP_EQ) Result = 0;
2237       if (pred == ICmpInst::ICMP_NE) Result = 1;
2238       break;
2239     }
2240 
2241     // If we evaluated the result, return it now.
2242     if (Result != -1)
2243       return ConstantInt::get(ResultTy, Result);
2244 
2245     // If the right hand side is a bitcast, try using its inverse to simplify
2246     // it by moving it to the left hand side.  We can't do this if it would turn
2247     // a vector compare into a scalar compare or visa versa, or if it would turn
2248     // the operands into FP values.
2249     if (ConstantExpr *CE2 = dyn_cast<ConstantExpr>(C2)) {
2250       Constant *CE2Op0 = CE2->getOperand(0);
2251       if (CE2->getOpcode() == Instruction::BitCast &&
2252           CE2->getType()->isVectorTy() == CE2Op0->getType()->isVectorTy() &&
2253           !CE2Op0->getType()->isFPOrFPVectorTy()) {
2254         Constant *Inverse = ConstantExpr::getBitCast(C1, CE2Op0->getType());
2255         return ConstantExpr::getICmp(pred, Inverse, CE2Op0);
2256       }
2257     }
2258 
2259     // If the left hand side is an extension, try eliminating it.
2260     if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
2261       if ((CE1->getOpcode() == Instruction::SExt &&
2262            ICmpInst::isSigned((ICmpInst::Predicate)pred)) ||
2263           (CE1->getOpcode() == Instruction::ZExt &&
2264            !ICmpInst::isSigned((ICmpInst::Predicate)pred))){
2265         Constant *CE1Op0 = CE1->getOperand(0);
2266         Constant *CE1Inverse = ConstantExpr::getTrunc(CE1, CE1Op0->getType());
2267         if (CE1Inverse == CE1Op0) {
2268           // Check whether we can safely truncate the right hand side.
2269           Constant *C2Inverse = ConstantExpr::getTrunc(C2, CE1Op0->getType());
2270           if (ConstantExpr::getCast(CE1->getOpcode(), C2Inverse,
2271                                     C2->getType()) == C2)
2272             return ConstantExpr::getICmp(pred, CE1Inverse, C2Inverse);
2273         }
2274       }
2275     }
2276 
2277     if ((!isa<ConstantExpr>(C1) && isa<ConstantExpr>(C2)) ||
2278         (C1->isNullValue() && !C2->isNullValue())) {
2279       // If C2 is a constant expr and C1 isn't, flip them around and fold the
2280       // other way if possible.
2281       // Also, if C1 is null and C2 isn't, flip them around.
2282       pred = ICmpInst::getSwappedPredicate((ICmpInst::Predicate)pred);
2283       return ConstantExpr::getICmp(pred, C2, C1);
2284     }
2285   }
2286   return nullptr;
2287 }
2288 
2289 /// Test whether the given sequence of *normalized* indices is "inbounds".
2290 template<typename IndexTy>
2291 static bool isInBoundsIndices(ArrayRef<IndexTy> Idxs) {
2292   // No indices means nothing that could be out of bounds.
2293   if (Idxs.empty()) return true;
2294 
2295   // If the first index is zero, it's in bounds.
2296   if (cast<Constant>(Idxs[0])->isNullValue()) return true;
2297 
2298   // If the first index is one and all the rest are zero, it's in bounds,
2299   // by the one-past-the-end rule.
2300   if (auto *CI = dyn_cast<ConstantInt>(Idxs[0])) {
2301     if (!CI->isOne())
2302       return false;
2303   } else {
2304     auto *CV = cast<ConstantDataVector>(Idxs[0]);
2305     CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue());
2306     if (!CI || !CI->isOne())
2307       return false;
2308   }
2309 
2310   for (unsigned i = 1, e = Idxs.size(); i != e; ++i)
2311     if (!cast<Constant>(Idxs[i])->isNullValue())
2312       return false;
2313   return true;
2314 }
2315 
2316 /// Test whether a given ConstantInt is in-range for a SequentialType.
2317 static bool isIndexInRangeOfArrayType(uint64_t NumElements,
2318                                       const ConstantInt *CI) {
2319   // We cannot bounds check the index if it doesn't fit in an int64_t.
2320   if (CI->getValue().getMinSignedBits() > 64)
2321     return false;
2322 
2323   // A negative index or an index past the end of our sequential type is
2324   // considered out-of-range.
2325   int64_t IndexVal = CI->getSExtValue();
2326   if (IndexVal < 0 || (NumElements > 0 && (uint64_t)IndexVal >= NumElements))
2327     return false;
2328 
2329   // Otherwise, it is in-range.
2330   return true;
2331 }
2332 
2333 Constant *llvm::ConstantFoldGetElementPtr(Type *PointeeTy, Constant *C,
2334                                           bool InBounds,
2335                                           Optional<unsigned> InRangeIndex,
2336                                           ArrayRef<Value *> Idxs) {
2337   if (Idxs.empty()) return C;
2338 
2339   Type *GEPTy = GetElementPtrInst::getGEPReturnType(
2340       PointeeTy, C, makeArrayRef((Value *const *)Idxs.data(), Idxs.size()));
2341 
2342   if (isa<PoisonValue>(C))
2343     return PoisonValue::get(GEPTy);
2344 
2345   if (isa<UndefValue>(C))
2346     // If inbounds, we can choose an out-of-bounds pointer as a base pointer.
2347     return InBounds ? PoisonValue::get(GEPTy) : UndefValue::get(GEPTy);
2348 
2349   Constant *Idx0 = cast<Constant>(Idxs[0]);
2350   if (Idxs.size() == 1 && (Idx0->isNullValue() || isa<UndefValue>(Idx0)))
2351     return GEPTy->isVectorTy() && !C->getType()->isVectorTy()
2352                ? ConstantVector::getSplat(
2353                      cast<VectorType>(GEPTy)->getElementCount(), C)
2354                : C;
2355 
2356   if (C->isNullValue()) {
2357     bool isNull = true;
2358     for (unsigned i = 0, e = Idxs.size(); i != e; ++i)
2359       if (!isa<UndefValue>(Idxs[i]) &&
2360           !cast<Constant>(Idxs[i])->isNullValue()) {
2361         isNull = false;
2362         break;
2363       }
2364     if (isNull) {
2365       PointerType *PtrTy = cast<PointerType>(C->getType()->getScalarType());
2366       Type *Ty = GetElementPtrInst::getIndexedType(PointeeTy, Idxs);
2367 
2368       assert(Ty && "Invalid indices for GEP!");
2369       Type *OrigGEPTy = PointerType::get(Ty, PtrTy->getAddressSpace());
2370       Type *GEPTy = PointerType::get(Ty, PtrTy->getAddressSpace());
2371       if (VectorType *VT = dyn_cast<VectorType>(C->getType()))
2372         GEPTy = VectorType::get(OrigGEPTy, VT->getElementCount());
2373 
2374       // The GEP returns a vector of pointers when one of more of
2375       // its arguments is a vector.
2376       for (unsigned i = 0, e = Idxs.size(); i != e; ++i) {
2377         if (auto *VT = dyn_cast<VectorType>(Idxs[i]->getType())) {
2378           assert((!isa<VectorType>(GEPTy) || isa<ScalableVectorType>(GEPTy) ==
2379                                                  isa<ScalableVectorType>(VT)) &&
2380                  "Mismatched GEPTy vector types");
2381           GEPTy = VectorType::get(OrigGEPTy, VT->getElementCount());
2382           break;
2383         }
2384       }
2385 
2386       return Constant::getNullValue(GEPTy);
2387     }
2388   }
2389 
2390   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
2391     // Combine Indices - If the source pointer to this getelementptr instruction
2392     // is a getelementptr instruction, combine the indices of the two
2393     // getelementptr instructions into a single instruction.
2394     //
2395     if (CE->getOpcode() == Instruction::GetElementPtr) {
2396       gep_type_iterator LastI = gep_type_end(CE);
2397       for (gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
2398            I != E; ++I)
2399         LastI = I;
2400 
2401       // We cannot combine indices if doing so would take us outside of an
2402       // array or vector.  Doing otherwise could trick us if we evaluated such a
2403       // GEP as part of a load.
2404       //
2405       // e.g. Consider if the original GEP was:
2406       // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c,
2407       //                    i32 0, i32 0, i64 0)
2408       //
2409       // If we then tried to offset it by '8' to get to the third element,
2410       // an i8, we should *not* get:
2411       // i8* getelementptr ({ [2 x i8], i32, i8, [3 x i8] }* @main.c,
2412       //                    i32 0, i32 0, i64 8)
2413       //
2414       // This GEP tries to index array element '8  which runs out-of-bounds.
2415       // Subsequent evaluation would get confused and produce erroneous results.
2416       //
2417       // The following prohibits such a GEP from being formed by checking to see
2418       // if the index is in-range with respect to an array.
2419       // TODO: This code may be extended to handle vectors as well.
2420       bool PerformFold = false;
2421       if (Idx0->isNullValue())
2422         PerformFold = true;
2423       else if (LastI.isSequential())
2424         if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx0))
2425           PerformFold = (!LastI.isBoundedSequential() ||
2426                          isIndexInRangeOfArrayType(
2427                              LastI.getSequentialNumElements(), CI)) &&
2428                         !CE->getOperand(CE->getNumOperands() - 1)
2429                              ->getType()
2430                              ->isVectorTy();
2431 
2432       if (PerformFold) {
2433         SmallVector<Value*, 16> NewIndices;
2434         NewIndices.reserve(Idxs.size() + CE->getNumOperands());
2435         NewIndices.append(CE->op_begin() + 1, CE->op_end() - 1);
2436 
2437         // Add the last index of the source with the first index of the new GEP.
2438         // Make sure to handle the case when they are actually different types.
2439         Constant *Combined = CE->getOperand(CE->getNumOperands()-1);
2440         // Otherwise it must be an array.
2441         if (!Idx0->isNullValue()) {
2442           Type *IdxTy = Combined->getType();
2443           if (IdxTy != Idx0->getType()) {
2444             unsigned CommonExtendedWidth =
2445                 std::max(IdxTy->getIntegerBitWidth(),
2446                          Idx0->getType()->getIntegerBitWidth());
2447             CommonExtendedWidth = std::max(CommonExtendedWidth, 64U);
2448 
2449             Type *CommonTy =
2450                 Type::getIntNTy(IdxTy->getContext(), CommonExtendedWidth);
2451             Constant *C1 = ConstantExpr::getSExtOrBitCast(Idx0, CommonTy);
2452             Constant *C2 = ConstantExpr::getSExtOrBitCast(Combined, CommonTy);
2453             Combined = ConstantExpr::get(Instruction::Add, C1, C2);
2454           } else {
2455             Combined =
2456               ConstantExpr::get(Instruction::Add, Idx0, Combined);
2457           }
2458         }
2459 
2460         NewIndices.push_back(Combined);
2461         NewIndices.append(Idxs.begin() + 1, Idxs.end());
2462 
2463         // The combined GEP normally inherits its index inrange attribute from
2464         // the inner GEP, but if the inner GEP's last index was adjusted by the
2465         // outer GEP, any inbounds attribute on that index is invalidated.
2466         Optional<unsigned> IRIndex = cast<GEPOperator>(CE)->getInRangeIndex();
2467         if (IRIndex && *IRIndex == CE->getNumOperands() - 2 && !Idx0->isNullValue())
2468           IRIndex = None;
2469 
2470         return ConstantExpr::getGetElementPtr(
2471             cast<GEPOperator>(CE)->getSourceElementType(), CE->getOperand(0),
2472             NewIndices, InBounds && cast<GEPOperator>(CE)->isInBounds(),
2473             IRIndex);
2474       }
2475     }
2476 
2477     // Attempt to fold casts to the same type away.  For example, folding:
2478     //
2479     //   i32* getelementptr ([2 x i32]* bitcast ([3 x i32]* %X to [2 x i32]*),
2480     //                       i64 0, i64 0)
2481     // into:
2482     //
2483     //   i32* getelementptr ([3 x i32]* %X, i64 0, i64 0)
2484     //
2485     // Don't fold if the cast is changing address spaces.
2486     if (CE->isCast() && Idxs.size() > 1 && Idx0->isNullValue()) {
2487       PointerType *SrcPtrTy =
2488         dyn_cast<PointerType>(CE->getOperand(0)->getType());
2489       PointerType *DstPtrTy = dyn_cast<PointerType>(CE->getType());
2490       if (SrcPtrTy && DstPtrTy) {
2491         ArrayType *SrcArrayTy =
2492           dyn_cast<ArrayType>(SrcPtrTy->getElementType());
2493         ArrayType *DstArrayTy =
2494           dyn_cast<ArrayType>(DstPtrTy->getElementType());
2495         if (SrcArrayTy && DstArrayTy
2496             && SrcArrayTy->getElementType() == DstArrayTy->getElementType()
2497             && SrcPtrTy->getAddressSpace() == DstPtrTy->getAddressSpace())
2498           return ConstantExpr::getGetElementPtr(SrcArrayTy,
2499                                                 (Constant *)CE->getOperand(0),
2500                                                 Idxs, InBounds, InRangeIndex);
2501       }
2502     }
2503   }
2504 
2505   // Check to see if any array indices are not within the corresponding
2506   // notional array or vector bounds. If so, try to determine if they can be
2507   // factored out into preceding dimensions.
2508   SmallVector<Constant *, 8> NewIdxs;
2509   Type *Ty = PointeeTy;
2510   Type *Prev = C->getType();
2511   auto GEPIter = gep_type_begin(PointeeTy, Idxs);
2512   bool Unknown =
2513       !isa<ConstantInt>(Idxs[0]) && !isa<ConstantDataVector>(Idxs[0]);
2514   for (unsigned i = 1, e = Idxs.size(); i != e;
2515        Prev = Ty, Ty = (++GEPIter).getIndexedType(), ++i) {
2516     if (!isa<ConstantInt>(Idxs[i]) && !isa<ConstantDataVector>(Idxs[i])) {
2517       // We don't know if it's in range or not.
2518       Unknown = true;
2519       continue;
2520     }
2521     if (!isa<ConstantInt>(Idxs[i - 1]) && !isa<ConstantDataVector>(Idxs[i - 1]))
2522       // Skip if the type of the previous index is not supported.
2523       continue;
2524     if (InRangeIndex && i == *InRangeIndex + 1) {
2525       // If an index is marked inrange, we cannot apply this canonicalization to
2526       // the following index, as that will cause the inrange index to point to
2527       // the wrong element.
2528       continue;
2529     }
2530     if (isa<StructType>(Ty)) {
2531       // The verify makes sure that GEPs into a struct are in range.
2532       continue;
2533     }
2534     if (isa<VectorType>(Ty)) {
2535       // There can be awkward padding in after a non-power of two vector.
2536       Unknown = true;
2537       continue;
2538     }
2539     auto *STy = cast<ArrayType>(Ty);
2540     if (ConstantInt *CI = dyn_cast<ConstantInt>(Idxs[i])) {
2541       if (isIndexInRangeOfArrayType(STy->getNumElements(), CI))
2542         // It's in range, skip to the next index.
2543         continue;
2544       if (CI->getSExtValue() < 0) {
2545         // It's out of range and negative, don't try to factor it.
2546         Unknown = true;
2547         continue;
2548       }
2549     } else {
2550       auto *CV = cast<ConstantDataVector>(Idxs[i]);
2551       bool InRange = true;
2552       for (unsigned I = 0, E = CV->getNumElements(); I != E; ++I) {
2553         auto *CI = cast<ConstantInt>(CV->getElementAsConstant(I));
2554         InRange &= isIndexInRangeOfArrayType(STy->getNumElements(), CI);
2555         if (CI->getSExtValue() < 0) {
2556           Unknown = true;
2557           break;
2558         }
2559       }
2560       if (InRange || Unknown)
2561         // It's in range, skip to the next index.
2562         // It's out of range and negative, don't try to factor it.
2563         continue;
2564     }
2565     if (isa<StructType>(Prev)) {
2566       // It's out of range, but the prior dimension is a struct
2567       // so we can't do anything about it.
2568       Unknown = true;
2569       continue;
2570     }
2571     // It's out of range, but we can factor it into the prior
2572     // dimension.
2573     NewIdxs.resize(Idxs.size());
2574     // Determine the number of elements in our sequential type.
2575     uint64_t NumElements = STy->getArrayNumElements();
2576 
2577     // Expand the current index or the previous index to a vector from a scalar
2578     // if necessary.
2579     Constant *CurrIdx = cast<Constant>(Idxs[i]);
2580     auto *PrevIdx =
2581         NewIdxs[i - 1] ? NewIdxs[i - 1] : cast<Constant>(Idxs[i - 1]);
2582     bool IsCurrIdxVector = CurrIdx->getType()->isVectorTy();
2583     bool IsPrevIdxVector = PrevIdx->getType()->isVectorTy();
2584     bool UseVector = IsCurrIdxVector || IsPrevIdxVector;
2585 
2586     if (!IsCurrIdxVector && IsPrevIdxVector)
2587       CurrIdx = ConstantDataVector::getSplat(
2588           cast<FixedVectorType>(PrevIdx->getType())->getNumElements(), CurrIdx);
2589 
2590     if (!IsPrevIdxVector && IsCurrIdxVector)
2591       PrevIdx = ConstantDataVector::getSplat(
2592           cast<FixedVectorType>(CurrIdx->getType())->getNumElements(), PrevIdx);
2593 
2594     Constant *Factor =
2595         ConstantInt::get(CurrIdx->getType()->getScalarType(), NumElements);
2596     if (UseVector)
2597       Factor = ConstantDataVector::getSplat(
2598           IsPrevIdxVector
2599               ? cast<FixedVectorType>(PrevIdx->getType())->getNumElements()
2600               : cast<FixedVectorType>(CurrIdx->getType())->getNumElements(),
2601           Factor);
2602 
2603     NewIdxs[i] = ConstantExpr::getSRem(CurrIdx, Factor);
2604 
2605     Constant *Div = ConstantExpr::getSDiv(CurrIdx, Factor);
2606 
2607     unsigned CommonExtendedWidth =
2608         std::max(PrevIdx->getType()->getScalarSizeInBits(),
2609                  Div->getType()->getScalarSizeInBits());
2610     CommonExtendedWidth = std::max(CommonExtendedWidth, 64U);
2611 
2612     // Before adding, extend both operands to i64 to avoid
2613     // overflow trouble.
2614     Type *ExtendedTy = Type::getIntNTy(Div->getContext(), CommonExtendedWidth);
2615     if (UseVector)
2616       ExtendedTy = FixedVectorType::get(
2617           ExtendedTy,
2618           IsPrevIdxVector
2619               ? cast<FixedVectorType>(PrevIdx->getType())->getNumElements()
2620               : cast<FixedVectorType>(CurrIdx->getType())->getNumElements());
2621 
2622     if (!PrevIdx->getType()->isIntOrIntVectorTy(CommonExtendedWidth))
2623       PrevIdx = ConstantExpr::getSExt(PrevIdx, ExtendedTy);
2624 
2625     if (!Div->getType()->isIntOrIntVectorTy(CommonExtendedWidth))
2626       Div = ConstantExpr::getSExt(Div, ExtendedTy);
2627 
2628     NewIdxs[i - 1] = ConstantExpr::getAdd(PrevIdx, Div);
2629   }
2630 
2631   // If we did any factoring, start over with the adjusted indices.
2632   if (!NewIdxs.empty()) {
2633     for (unsigned i = 0, e = Idxs.size(); i != e; ++i)
2634       if (!NewIdxs[i]) NewIdxs[i] = cast<Constant>(Idxs[i]);
2635     return ConstantExpr::getGetElementPtr(PointeeTy, C, NewIdxs, InBounds,
2636                                           InRangeIndex);
2637   }
2638 
2639   // If all indices are known integers and normalized, we can do a simple
2640   // check for the "inbounds" property.
2641   if (!Unknown && !InBounds)
2642     if (auto *GV = dyn_cast<GlobalVariable>(C))
2643       if (!GV->hasExternalWeakLinkage() && isInBoundsIndices(Idxs))
2644         return ConstantExpr::getGetElementPtr(PointeeTy, C, Idxs,
2645                                               /*InBounds=*/true, InRangeIndex);
2646 
2647   return nullptr;
2648 }
2649