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