llvm/lib/IR/ConstantFold.cpp

   1 //===- ConstantFold.cpp - LLVM constant folder ----------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements folding of constants for LLVM.  This implements the
  10 // (internal) ConstantFold.h interface, which is used by the
  11 // ConstantExpr::get* methods to automatically fold constants when possible.
  12 //
  13 // The current constant folding implementation is implemented in two pieces: the
  14 // pieces that don't need DataLayout, and the pieces that do. This is to avoid
  15 // a dependence in IR on Target.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/IR/ConstantFold.h"
  20 #include "llvm/ADT/APSInt.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DerivedTypes.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/IR/GlobalAlias.h"
  26 #include "llvm/IR/GlobalVariable.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/Module.h"
  29 #include "llvm/IR/Operator.h"
  30 #include "llvm/IR/PatternMatch.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 using namespace llvm;
  33 using namespace llvm::PatternMatch;
  34
  35 //===----------------------------------------------------------------------===//
  36 //                ConstantFold*Instruction Implementations
  37 //===----------------------------------------------------------------------===//
  38
  39 /// This function determines which opcode to use to fold two constant cast
  40 /// expressions together. It uses CastInst::isEliminableCastPair to determine
  41 /// the opcode. Consequently its just a wrapper around that function.
  42 /// Determine if it is valid to fold a cast of a cast
  43 static unsigned
  44 foldConstantCastPair(
  45   unsigned opc,          ///< opcode of the second cast constant expression
  46   ConstantExpr *Op,      ///< the first cast constant expression
  47   Type *DstTy            ///< destination type of the first cast
  48 ) {
  49   assert(Op && Op->isCast() && "Can't fold cast of cast without a cast!");
  50   assert(DstTy && DstTy->isFirstClassType() && "Invalid cast destination type");
  51   assert(CastInst::isCast(opc) && "Invalid cast opcode");
  52
  53   // The types and opcodes for the two Cast constant expressions
  54   Type *SrcTy = Op->getOperand(0)->getType();
  55   Type *MidTy = Op->getType();
  56   Instruction::CastOps firstOp = Instruction::CastOps(Op->getOpcode());
  57   Instruction::CastOps secondOp = Instruction::CastOps(opc);
  58
  59   // Assume that pointers are never more than 64 bits wide, and only use this
  60   // for the middle type. Otherwise we could end up folding away illegal
  61   // bitcasts between address spaces with different sizes.
  62   IntegerType *FakeIntPtrTy = Type::getInt64Ty(DstTy->getContext());
  63
  64   // Let CastInst::isEliminableCastPair do the heavy lifting.
  65   return CastInst::isEliminableCastPair(firstOp, secondOp, SrcTy, MidTy, DstTy,
  66                                         nullptr, FakeIntPtrTy, nullptr);
  67 }
  68
  69 static Constant *FoldBitCast(Constant *V, Type *DestTy) {
  70   Type *SrcTy = V->getType();
  71   if (SrcTy == DestTy)
  72     return V; // no-op cast
  73
  74   if (V->isAllOnesValue())
  75     return Constant::getAllOnesValue(DestTy);
  76
  77   // Handle ConstantInt -> ConstantFP
  78   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
  79     // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts
  80     // This allows for other simplifications (although some of them
  81     // can only be handled by Analysis/ConstantFolding.cpp).
  82     if (isa<VectorType>(DestTy) && !isa<VectorType>(SrcTy))
  83       return ConstantExpr::getBitCast(ConstantVector::get(V), DestTy);
  84
  85     // Make sure dest type is compatible with the folded fp constant.
  86     // See note below regarding the PPC_FP128 restriction.
  87     if (!DestTy->isFPOrFPVectorTy() || DestTy->isPPC_FP128Ty() ||
  88         DestTy->getScalarSizeInBits() != SrcTy->getScalarSizeInBits())
  89       return nullptr;
  90
  91     return ConstantFP::get(
  92         DestTy,
  93         APFloat(DestTy->getScalarType()->getFltSemantics(), CI->getValue()));
  94   }
  95
  96   // Handle ConstantFP -> ConstantInt
  97   if (ConstantFP *FP = dyn_cast<ConstantFP>(V)) {
  98     // Canonicalize scalar-to-vector bitcasts into vector-to-vector bitcasts
  99     // This allows for other simplifications (although some of them
 100     // can only be handled by Analysis/ConstantFolding.cpp).
 101     if (isa<VectorType>(DestTy) && !isa<VectorType>(SrcTy))
 102       return ConstantExpr::getBitCast(ConstantVector::get(V), DestTy);
 103
 104     // PPC_FP128 is really the sum of two consecutive doubles, where the first
 105     // double is always stored first in memory, regardless of the target
 106     // endianness. The memory layout of i128, however, depends on the target
 107     // endianness, and so we can't fold this without target endianness
 108     // information. This should instead be handled by
 109     // Analysis/ConstantFolding.cpp
 110     if (SrcTy->isPPC_FP128Ty())
 111       return nullptr;
 112
 113     // Make sure dest type is compatible with the folded integer constant.
 114     if (!DestTy->isIntOrIntVectorTy() ||
 115         DestTy->getScalarSizeInBits() != SrcTy->getScalarSizeInBits())
 116       return nullptr;
 117
 118     return ConstantInt::get(DestTy, FP->getValueAPF().bitcastToAPInt());
 119   }
 120
 121   return nullptr;
 122 }
 123
 124 static Constant *foldMaybeUndesirableCast(unsigned opc, Constant *V,
 125                                           Type *DestTy) {
 126   return ConstantExpr::isDesirableCastOp(opc)
 127              ? ConstantExpr::getCast(opc, V, DestTy)
 128              : ConstantFoldCastInstruction(opc, V, DestTy);
 129 }
 130
 131 Constant *llvm::ConstantFoldCastInstruction(unsigned opc, Constant *V,
 132                                             Type *DestTy) {
 133   if (isa<PoisonValue>(V))
 134     return PoisonValue::get(DestTy);
 135
 136   if (isa<UndefValue>(V)) {
 137     // zext(undef) = 0, because the top bits will be zero.
 138     // sext(undef) = 0, because the top bits will all be the same.
 139     // [us]itofp(undef) = 0, because the result value is bounded.
 140     if (opc == Instruction::ZExt || opc == Instruction::SExt ||
 141         opc == Instruction::UIToFP || opc == Instruction::SIToFP)
 142       return Constant::getNullValue(DestTy);
 143     return UndefValue::get(DestTy);
 144   }
 145
 146   if (V->isNullValue() && !DestTy->isX86_AMXTy() &&
 147       opc != Instruction::AddrSpaceCast)
 148     return Constant::getNullValue(DestTy);
 149
 150   // If the cast operand is a constant expression, there's a few things we can
 151   // do to try to simplify it.
 152   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 153     if (CE->isCast()) {
 154       // Try hard to fold cast of cast because they are often eliminable.
 155       if (unsigned newOpc = foldConstantCastPair(opc, CE, DestTy))
 156         return foldMaybeUndesirableCast(newOpc, CE->getOperand(0), DestTy);
 157     }
 158   }
 159
 160   // If the cast operand is a constant vector, perform the cast by
 161   // operating on each element. In the cast of bitcasts, the element
 162   // count may be mismatched; don't attempt to handle that here.
 163   if ((isa<ConstantVector>(V) || isa<ConstantDataVector>(V)) &&
 164       DestTy->isVectorTy() &&
 165       cast<FixedVectorType>(DestTy)->getNumElements() ==
 166           cast<FixedVectorType>(V->getType())->getNumElements()) {
 167     VectorType *DestVecTy = cast<VectorType>(DestTy);
 168     Type *DstEltTy = DestVecTy->getElementType();
 169     // Fast path for splatted constants.
 170     if (Constant *Splat = V->getSplatValue()) {
 171       Constant *Res = foldMaybeUndesirableCast(opc, Splat, DstEltTy);
 172       if (!Res)
 173         return nullptr;
 174       return ConstantVector::getSplat(
 175           cast<VectorType>(DestTy)->getElementCount(), Res);
 176     }
 177     SmallVector<Constant *, 16> res;
 178     Type *Ty = IntegerType::get(V->getContext(), 32);
 179     for (unsigned i = 0,
 180                   e = cast<FixedVectorType>(V->getType())->getNumElements();
 181          i != e; ++i) {
 182       Constant *C = ConstantExpr::getExtractElement(V, ConstantInt::get(Ty, i));
 183       Constant *Casted = foldMaybeUndesirableCast(opc, C, DstEltTy);
 184       if (!Casted)
 185         return nullptr;
 186       res.push_back(Casted);
 187     }
 188     return ConstantVector::get(res);
 189   }
 190
 191   // We actually have to do a cast now. Perform the cast according to the
 192   // opcode specified.
 193   switch (opc) {
 194   default:
 195     llvm_unreachable("Failed to cast constant expression");
 196   case Instruction::FPTrunc:
 197   case Instruction::FPExt:
 198     if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
 199       bool ignored;
 200       APFloat Val = FPC->getValueAPF();
 201       Val.convert(DestTy->getScalarType()->getFltSemantics(),
 202                   APFloat::rmNearestTiesToEven, &ignored);
 203       return ConstantFP::get(DestTy, Val);
 204     }
 205     return nullptr; // Can't fold.
 206   case Instruction::FPToUI:
 207   case Instruction::FPToSI:
 208     if (ConstantFP *FPC = dyn_cast<ConstantFP>(V)) {
 209       const APFloat &V = FPC->getValueAPF();
 210       bool ignored;
 211       APSInt IntVal(DestTy->getScalarSizeInBits(), opc == Instruction::FPToUI);
 212       if (APFloat::opInvalidOp ==
 213           V.convertToInteger(IntVal, APFloat::rmTowardZero, &ignored)) {
 214         // Undefined behavior invoked - the destination type can't represent
 215         // the input constant.
 216         return PoisonValue::get(DestTy);
 217       }
 218       return ConstantInt::get(DestTy, IntVal);
 219     }
 220     return nullptr; // Can't fold.
 221   case Instruction::UIToFP:
 222   case Instruction::SIToFP:
 223     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 224       const APInt &api = CI->getValue();
 225       APFloat apf(DestTy->getScalarType()->getFltSemantics(),
 226                   APInt::getZero(DestTy->getScalarSizeInBits()));
 227       apf.convertFromAPInt(api, opc==Instruction::SIToFP,
 228                            APFloat::rmNearestTiesToEven);
 229       return ConstantFP::get(DestTy, apf);
 230     }
 231     return nullptr;
 232   case Instruction::ZExt:
 233     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 234       uint32_t BitWidth = DestTy->getScalarSizeInBits();
 235       return ConstantInt::get(DestTy, CI->getValue().zext(BitWidth));
 236     }
 237     return nullptr;
 238   case Instruction::SExt:
 239     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 240       uint32_t BitWidth = DestTy->getScalarSizeInBits();
 241       return ConstantInt::get(DestTy, CI->getValue().sext(BitWidth));
 242     }
 243     return nullptr;
 244   case Instruction::Trunc: {
 245     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 246       uint32_t BitWidth = DestTy->getScalarSizeInBits();
 247       return ConstantInt::get(DestTy, CI->getValue().trunc(BitWidth));
 248     }
 249
 250     return nullptr;
 251   }
 252   case Instruction::BitCast:
 253     return FoldBitCast(V, DestTy);
 254   case Instruction::AddrSpaceCast:
 255   case Instruction::IntToPtr:
 256   case Instruction::PtrToInt:
 257     return nullptr;
 258   }
 259 }
 260
 261 Constant *llvm::ConstantFoldSelectInstruction(Constant *Cond,
 262                                               Constant *V1, Constant *V2) {
 263   // Check for i1 and vector true/false conditions.
 264   if (Cond->isNullValue()) return V2;
 265   if (Cond->isAllOnesValue()) return V1;
 266
 267   // If the condition is a vector constant, fold the result elementwise.
 268   if (ConstantVector *CondV = dyn_cast<ConstantVector>(Cond)) {
 269     auto *V1VTy = CondV->getType();
 270     SmallVector<Constant*, 16> Result;
 271     Type *Ty = IntegerType::get(CondV->getContext(), 32);
 272     for (unsigned i = 0, e = V1VTy->getNumElements(); i != e; ++i) {
 273       Constant *V;
 274       Constant *V1Element = ConstantExpr::getExtractElement(V1,
 275                                                     ConstantInt::get(Ty, i));
 276       Constant *V2Element = ConstantExpr::getExtractElement(V2,
 277                                                     ConstantInt::get(Ty, i));
 278       auto *Cond = cast<Constant>(CondV->getOperand(i));
 279       if (isa<PoisonValue>(Cond)) {
 280         V = PoisonValue::get(V1Element->getType());
 281       } else if (V1Element == V2Element) {
 282         V = V1Element;
 283       } else if (isa<UndefValue>(Cond)) {
 284         V = isa<UndefValue>(V1Element) ? V1Element : V2Element;
 285       } else {
 286         if (!isa<ConstantInt>(Cond)) break;
 287         V = Cond->isNullValue() ? V2Element : V1Element;
 288       }
 289       Result.push_back(V);
 290     }
 291
 292     // If we were able to build the vector, return it.
 293     if (Result.size() == V1VTy->getNumElements())
 294       return ConstantVector::get(Result);
 295   }
 296
 297   if (isa<PoisonValue>(Cond))
 298     return PoisonValue::get(V1->getType());
 299
 300   if (isa<UndefValue>(Cond)) {
 301     if (isa<UndefValue>(V1)) return V1;
 302     return V2;
 303   }
 304
 305   if (V1 == V2) return V1;
 306
 307   if (isa<PoisonValue>(V1))
 308     return V2;
 309   if (isa<PoisonValue>(V2))
 310     return V1;
 311
 312   // If the true or false value is undef, we can fold to the other value as
 313   // long as the other value isn't poison.
 314   auto NotPoison = [](Constant *C) {
 315     if (isa<PoisonValue>(C))
 316       return false;
 317
 318     // TODO: We can analyze ConstExpr by opcode to determine if there is any
 319     //       possibility of poison.
 320     if (isa<ConstantExpr>(C))
 321       return false;
 322
 323     if (isa<ConstantInt>(C) || isa<GlobalVariable>(C) || isa<ConstantFP>(C) ||
 324         isa<ConstantPointerNull>(C) || isa<Function>(C))
 325       return true;
 326
 327     if (C->getType()->isVectorTy())
 328       return !C->containsPoisonElement() && !C->containsConstantExpression();
 329
 330     // TODO: Recursively analyze aggregates or other constants.
 331     return false;
 332   };
 333   if (isa<UndefValue>(V1) && NotPoison(V2)) return V2;
 334   if (isa<UndefValue>(V2) && NotPoison(V1)) return V1;
 335
 336   return nullptr;
 337 }
 338
 339 Constant *llvm::ConstantFoldExtractElementInstruction(Constant *Val,
 340                                                       Constant *Idx) {
 341   auto *ValVTy = cast<VectorType>(Val->getType());
 342
 343   // extractelt poison, C -> poison
 344   // extractelt C, undef -> poison
 345   if (isa<PoisonValue>(Val) || isa<UndefValue>(Idx))
 346     return PoisonValue::get(ValVTy->getElementType());
 347
 348   // extractelt undef, C -> undef
 349   if (isa<UndefValue>(Val))
 350     return UndefValue::get(ValVTy->getElementType());
 351
 352   auto *CIdx = dyn_cast<ConstantInt>(Idx);
 353   if (!CIdx)
 354     return nullptr;
 355
 356   if (auto *ValFVTy = dyn_cast<FixedVectorType>(Val->getType())) {
 357     // ee({w,x,y,z}, wrong_value) -> poison
 358     if (CIdx->uge(ValFVTy->getNumElements()))
 359       return PoisonValue::get(ValFVTy->getElementType());
 360   }
 361
 362   // ee (gep (ptr, idx0, ...), idx) -> gep (ee (ptr, idx), ee (idx0, idx), ...)
 363   if (auto *CE = dyn_cast<ConstantExpr>(Val)) {
 364     if (auto *GEP = dyn_cast<GEPOperator>(CE)) {
 365       SmallVector<Constant *, 8> Ops;
 366       Ops.reserve(CE->getNumOperands());
 367       for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
 368         Constant *Op = CE->getOperand(i);
 369         if (Op->getType()->isVectorTy()) {
 370           Constant *ScalarOp = ConstantExpr::getExtractElement(Op, Idx);
 371           if (!ScalarOp)
 372             return nullptr;
 373           Ops.push_back(ScalarOp);
 374         } else
 375           Ops.push_back(Op);
 376       }
 377       return CE->getWithOperands(Ops, ValVTy->getElementType(), false,
 378                                  GEP->getSourceElementType());
 379     } else if (CE->getOpcode() == Instruction::InsertElement) {
 380       if (const auto *IEIdx = dyn_cast<ConstantInt>(CE->getOperand(2))) {
 381         if (APSInt::isSameValue(APSInt(IEIdx->getValue()),
 382                                 APSInt(CIdx->getValue()))) {
 383           return CE->getOperand(1);
 384         } else {
 385           return ConstantExpr::getExtractElement(CE->getOperand(0), CIdx);
 386         }
 387       }
 388     }
 389   }
 390
 391   if (Constant *C = Val->getAggregateElement(CIdx))
 392     return C;
 393
 394   // Lane < Splat minimum vector width => extractelt Splat(x), Lane -> x
 395   if (CIdx->getValue().ult(ValVTy->getElementCount().getKnownMinValue())) {
 396     if (Constant *SplatVal = Val->getSplatValue())
 397       return SplatVal;
 398   }
 399
 400   return nullptr;
 401 }
 402
 403 Constant *llvm::ConstantFoldInsertElementInstruction(Constant *Val,
 404                                                      Constant *Elt,
 405                                                      Constant *Idx) {
 406   if (isa<UndefValue>(Idx))
 407     return PoisonValue::get(Val->getType());
 408
 409   // Inserting null into all zeros is still all zeros.
 410   // TODO: This is true for undef and poison splats too.
 411   if (isa<ConstantAggregateZero>(Val) && Elt->isNullValue())
 412     return Val;
 413
 414   ConstantInt *CIdx = dyn_cast<ConstantInt>(Idx);
 415   if (!CIdx) return nullptr;
 416
 417   // Do not iterate on scalable vector. The num of elements is unknown at
 418   // compile-time.
 419   if (isa<ScalableVectorType>(Val->getType()))
 420     return nullptr;
 421
 422   auto *ValTy = cast<FixedVectorType>(Val->getType());
 423
 424   unsigned NumElts = ValTy->getNumElements();
 425   if (CIdx->uge(NumElts))
 426     return PoisonValue::get(Val->getType());
 427
 428   SmallVector<Constant*, 16> Result;
 429   Result.reserve(NumElts);
 430   auto *Ty = Type::getInt32Ty(Val->getContext());
 431   uint64_t IdxVal = CIdx->getZExtValue();
 432   for (unsigned i = 0; i != NumElts; ++i) {
 433     if (i == IdxVal) {
 434       Result.push_back(Elt);
 435       continue;
 436     }
 437
 438     Constant *C = ConstantExpr::getExtractElement(Val, ConstantInt::get(Ty, i));
 439     Result.push_back(C);
 440   }
 441
 442   return ConstantVector::get(Result);
 443 }
 444
 445 Constant *llvm::ConstantFoldShuffleVectorInstruction(Constant *V1, Constant *V2,
 446                                                      ArrayRef<int> Mask) {
 447   auto *V1VTy = cast<VectorType>(V1->getType());
 448   unsigned MaskNumElts = Mask.size();
 449   auto MaskEltCount =
 450       ElementCount::get(MaskNumElts, isa<ScalableVectorType>(V1VTy));
 451   Type *EltTy = V1VTy->getElementType();
 452
 453   // Poison shuffle mask -> poison value.
 454   if (all_of(Mask, [](int Elt) { return Elt == PoisonMaskElem; })) {
 455     return PoisonValue::get(VectorType::get(EltTy, MaskEltCount));
 456   }
 457
 458   // If the mask is all zeros this is a splat, no need to go through all
 459   // elements.
 460   if (all_of(Mask, [](int Elt) { return Elt == 0; })) {
 461     Type *Ty = IntegerType::get(V1->getContext(), 32);
 462     Constant *Elt =
 463         ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, 0));
 464
 465     if (Elt->isNullValue()) {
 466       auto *VTy = VectorType::get(EltTy, MaskEltCount);
 467       return ConstantAggregateZero::get(VTy);
 468     } else if (!MaskEltCount.isScalable())
 469       return ConstantVector::getSplat(MaskEltCount, Elt);
 470   }
 471
 472   // Do not iterate on scalable vector. The num of elements is unknown at
 473   // compile-time.
 474   if (isa<ScalableVectorType>(V1VTy))
 475     return nullptr;
 476
 477   unsigned SrcNumElts = V1VTy->getElementCount().getKnownMinValue();
 478
 479   // Loop over the shuffle mask, evaluating each element.
 480   SmallVector<Constant*, 32> Result;
 481   for (unsigned i = 0; i != MaskNumElts; ++i) {
 482     int Elt = Mask[i];
 483     if (Elt == -1) {
 484       Result.push_back(UndefValue::get(EltTy));
 485       continue;
 486     }
 487     Constant *InElt;
 488     if (unsigned(Elt) >= SrcNumElts*2)
 489       InElt = UndefValue::get(EltTy);
 490     else if (unsigned(Elt) >= SrcNumElts) {
 491       Type *Ty = IntegerType::get(V2->getContext(), 32);
 492       InElt =
 493         ConstantExpr::getExtractElement(V2,
 494                                         ConstantInt::get(Ty, Elt - SrcNumElts));
 495     } else {
 496       Type *Ty = IntegerType::get(V1->getContext(), 32);
 497       InElt = ConstantExpr::getExtractElement(V1, ConstantInt::get(Ty, Elt));
 498     }
 499     Result.push_back(InElt);
 500   }
 501
 502   return ConstantVector::get(Result);
 503 }
 504
 505 Constant *llvm::ConstantFoldExtractValueInstruction(Constant *Agg,
 506                                                     ArrayRef<unsigned> Idxs) {
 507   // Base case: no indices, so return the entire value.
 508   if (Idxs.empty())
 509     return Agg;
 510
 511   if (Constant *C = Agg->getAggregateElement(Idxs[0]))
 512     return ConstantFoldExtractValueInstruction(C, Idxs.slice(1));
 513
 514   return nullptr;
 515 }
 516
 517 Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg,
 518                                                    Constant *Val,
 519                                                    ArrayRef<unsigned> Idxs) {
 520   // Base case: no indices, so replace the entire value.
 521   if (Idxs.empty())
 522     return Val;
 523
 524   unsigned NumElts;
 525   if (StructType *ST = dyn_cast<StructType>(Agg->getType()))
 526     NumElts = ST->getNumElements();
 527   else
 528     NumElts = cast<ArrayType>(Agg->getType())->getNumElements();
 529
 530   SmallVector<Constant*, 32> Result;
 531   for (unsigned i = 0; i != NumElts; ++i) {
 532     Constant *C = Agg->getAggregateElement(i);
 533     if (!C) return nullptr;
 534
 535     if (Idxs[0] == i)
 536       C = ConstantFoldInsertValueInstruction(C, Val, Idxs.slice(1));
 537
 538     Result.push_back(C);
 539   }
 540
 541   if (StructType *ST = dyn_cast<StructType>(Agg->getType()))
 542     return ConstantStruct::get(ST, Result);
 543   return ConstantArray::get(cast<ArrayType>(Agg->getType()), Result);
 544 }
 545
 546 Constant *llvm::ConstantFoldUnaryInstruction(unsigned Opcode, Constant *C) {
 547   assert(Instruction::isUnaryOp(Opcode) && "Non-unary instruction detected");
 548
 549   // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
 550   // vectors are always evaluated per element.
 551   bool IsScalableVector = isa<ScalableVectorType>(C->getType());
 552   bool HasScalarUndefOrScalableVectorUndef =
 553       (!C->getType()->isVectorTy() || IsScalableVector) && isa<UndefValue>(C);
 554
 555   if (HasScalarUndefOrScalableVectorUndef) {
 556     switch (static_cast<Instruction::UnaryOps>(Opcode)) {
 557     case Instruction::FNeg:
 558       return C; // -undef -> undef
 559     case Instruction::UnaryOpsEnd:
 560       llvm_unreachable("Invalid UnaryOp");
 561     }
 562   }
 563
 564   // Constant should not be UndefValue, unless these are vector constants.
 565   assert(!HasScalarUndefOrScalableVectorUndef && "Unexpected UndefValue");
 566   // We only have FP UnaryOps right now.
 567   assert(!isa<ConstantInt>(C) && "Unexpected Integer UnaryOp");
 568
 569   if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 570     const APFloat &CV = CFP->getValueAPF();
 571     switch (Opcode) {
 572     default:
 573       break;
 574     case Instruction::FNeg:
 575       return ConstantFP::get(C->getType(), neg(CV));
 576     }
 577   } else if (auto *VTy = dyn_cast<VectorType>(C->getType())) {
 578     // Fast path for splatted constants.
 579     if (Constant *Splat = C->getSplatValue())
 580       if (Constant *Elt = ConstantFoldUnaryInstruction(Opcode, Splat))
 581         return ConstantVector::getSplat(VTy->getElementCount(), Elt);
 582
 583     if (auto *FVTy = dyn_cast<FixedVectorType>(VTy)) {
 584       // Fold each element and create a vector constant from those constants.
 585       Type *Ty = IntegerType::get(FVTy->getContext(), 32);
 586       SmallVector<Constant *, 16> Result;
 587       for (unsigned i = 0, e = FVTy->getNumElements(); i != e; ++i) {
 588         Constant *ExtractIdx = ConstantInt::get(Ty, i);
 589         Constant *Elt = ConstantExpr::getExtractElement(C, ExtractIdx);
 590         Constant *Res = ConstantFoldUnaryInstruction(Opcode, Elt);
 591         if (!Res)
 592           return nullptr;
 593         Result.push_back(Res);
 594       }
 595
 596       return ConstantVector::get(Result);
 597     }
 598   }
 599
 600   // We don't know how to fold this.
 601   return nullptr;
 602 }
 603
 604 Constant *llvm::ConstantFoldBinaryInstruction(unsigned Opcode, Constant *C1,
 605                                               Constant *C2) {
 606   assert(Instruction::isBinaryOp(Opcode) && "Non-binary instruction detected");
 607
 608   // Simplify BinOps with their identity values first. They are no-ops and we
 609   // can always return the other value, including undef or poison values.
 610   if (Constant *Identity = ConstantExpr::getBinOpIdentity(
 611           Opcode, C1->getType(), /*AllowRHSIdentity*/ false)) {
 612     if (C1 == Identity)
 613       return C2;
 614     if (C2 == Identity)
 615       return C1;
 616   } else if (Constant *Identity = ConstantExpr::getBinOpIdentity(
 617                  Opcode, C1->getType(), /*AllowRHSIdentity*/ true)) {
 618     if (C2 == Identity)
 619       return C1;
 620   }
 621
 622   // Binary operations propagate poison.
 623   if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))
 624     return PoisonValue::get(C1->getType());
 625
 626   // Handle scalar UndefValue and scalable vector UndefValue. Fixed-length
 627   // vectors are always evaluated per element.
 628   bool IsScalableVector = isa<ScalableVectorType>(C1->getType());
 629   bool HasScalarUndefOrScalableVectorUndef =
 630       (!C1->getType()->isVectorTy() || IsScalableVector) &&
 631       (isa<UndefValue>(C1) || isa<UndefValue>(C2));
 632   if (HasScalarUndefOrScalableVectorUndef) {
 633     switch (static_cast<Instruction::BinaryOps>(Opcode)) {
 634     case Instruction::Xor:
 635       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
 636         // Handle undef ^ undef -> 0 special case. This is a common
 637         // idiom (misuse).
 638         return Constant::getNullValue(C1->getType());
 639       [[fallthrough]];
 640     case Instruction::Add:
 641     case Instruction::Sub:
 642       return UndefValue::get(C1->getType());
 643     case Instruction::And:
 644       if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) // undef & undef -> undef
 645         return C1;
 646       return Constant::getNullValue(C1->getType());   // undef & X -> 0
 647     case Instruction::Mul: {
 648       // undef * undef -> undef
 649       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
 650         return C1;
 651       const APInt *CV;
 652       // X * undef -> undef   if X is odd
 653       if (match(C1, m_APInt(CV)) || match(C2, m_APInt(CV)))
 654         if ((*CV)[0])
 655           return UndefValue::get(C1->getType());
 656
 657       // X * undef -> 0       otherwise
 658       return Constant::getNullValue(C1->getType());
 659     }
 660     case Instruction::SDiv:
 661     case Instruction::UDiv:
 662       // X / undef -> poison
 663       // X / 0 -> poison
 664       if (match(C2, m_CombineOr(m_Undef(), m_Zero())))
 665         return PoisonValue::get(C2->getType());
 666       // undef / X -> 0       otherwise
 667       return Constant::getNullValue(C1->getType());
 668     case Instruction::URem:
 669     case Instruction::SRem:
 670       // X % undef -> poison
 671       // X % 0 -> poison
 672       if (match(C2, m_CombineOr(m_Undef(), m_Zero())))
 673         return PoisonValue::get(C2->getType());
 674       // undef % X -> 0       otherwise
 675       return Constant::getNullValue(C1->getType());
 676     case Instruction::Or:                          // X | undef -> -1
 677       if (isa<UndefValue>(C1) && isa<UndefValue>(C2)) // undef | undef -> undef
 678         return C1;
 679       return Constant::getAllOnesValue(C1->getType()); // undef | X -> ~0
 680     case Instruction::LShr:
 681       // X >>l undef -> poison
 682       if (isa<UndefValue>(C2))
 683         return PoisonValue::get(C2->getType());
 684       // undef >>l X -> 0
 685       return Constant::getNullValue(C1->getType());
 686     case Instruction::AShr:
 687       // X >>a undef -> poison
 688       if (isa<UndefValue>(C2))
 689         return PoisonValue::get(C2->getType());
 690       // TODO: undef >>a X -> poison if the shift is exact
 691       // undef >>a X -> 0
 692       return Constant::getNullValue(C1->getType());
 693     case Instruction::Shl:
 694       // X << undef -> undef
 695       if (isa<UndefValue>(C2))
 696         return PoisonValue::get(C2->getType());
 697       // undef << X -> 0
 698       return Constant::getNullValue(C1->getType());
 699     case Instruction::FSub:
 700       // -0.0 - undef --> undef (consistent with "fneg undef")
 701       if (match(C1, m_NegZeroFP()) && isa<UndefValue>(C2))
 702         return C2;
 703       [[fallthrough]];
 704     case Instruction::FAdd:
 705     case Instruction::FMul:
 706     case Instruction::FDiv:
 707     case Instruction::FRem:
 708       // [any flop] undef, undef -> undef
 709       if (isa<UndefValue>(C1) && isa<UndefValue>(C2))
 710         return C1;
 711       // [any flop] C, undef -> NaN
 712       // [any flop] undef, C -> NaN
 713       // We could potentially specialize NaN/Inf constants vs. 'normal'
 714       // constants (possibly differently depending on opcode and operand). This
 715       // would allow returning undef sometimes. But it is always safe to fold to
 716       // NaN because we can choose the undef operand as NaN, and any FP opcode
 717       // with a NaN operand will propagate NaN.
 718       return ConstantFP::getNaN(C1->getType());
 719     case Instruction::BinaryOpsEnd:
 720       llvm_unreachable("Invalid BinaryOp");
 721     }
 722   }
 723
 724   // Neither constant should be UndefValue, unless these are vector constants.
 725   assert((!HasScalarUndefOrScalableVectorUndef) && "Unexpected UndefValue");
 726
 727   // Handle simplifications when the RHS is a constant int.
 728   if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
 729     if (C2 == ConstantExpr::getBinOpAbsorber(Opcode, C2->getType(),
 730                                              /*AllowLHSConstant*/ false))
 731       return C2;
 732
 733     switch (Opcode) {
 734     case Instruction::UDiv:
 735     case Instruction::SDiv:
 736       if (CI2->isZero())
 737         return PoisonValue::get(CI2->getType());              // X / 0 == poison
 738       break;
 739     case Instruction::URem:
 740     case Instruction::SRem:
 741       if (CI2->isOne())
 742         return Constant::getNullValue(CI2->getType());        // X % 1 == 0
 743       if (CI2->isZero())
 744         return PoisonValue::get(CI2->getType());              // X % 0 == poison
 745       break;
 746     case Instruction::And:
 747       assert(!CI2->isZero() && "And zero handled above");
 748       if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
 749         // If and'ing the address of a global with a constant, fold it.
 750         if (CE1->getOpcode() == Instruction::PtrToInt &&
 751             isa<GlobalValue>(CE1->getOperand(0))) {
 752           GlobalValue *GV = cast<GlobalValue>(CE1->getOperand(0));
 753
 754           Align GVAlign; // defaults to 1
 755
 756           if (Module *TheModule = GV->getParent()) {
 757             const DataLayout &DL = TheModule->getDataLayout();
 758             GVAlign = GV->getPointerAlignment(DL);
 759
 760             // If the function alignment is not specified then assume that it
 761             // is 4.
 762             // This is dangerous; on x86, the alignment of the pointer
 763             // corresponds to the alignment of the function, but might be less
 764             // than 4 if it isn't explicitly specified.
 765             // However, a fix for this behaviour was reverted because it
 766             // increased code size (see https://reviews.llvm.org/D55115)
 767             // FIXME: This code should be deleted once existing targets have
 768             // appropriate defaults
 769             if (isa<Function>(GV) && !DL.getFunctionPtrAlign())
 770               GVAlign = Align(4);
 771           } else if (isa<GlobalVariable>(GV)) {
 772             GVAlign = cast<GlobalVariable>(GV)->getAlign().valueOrOne();
 773           }
 774
 775           if (GVAlign > 1) {
 776             unsigned DstWidth = CI2->getBitWidth();
 777             unsigned SrcWidth = std::min(DstWidth, Log2(GVAlign));
 778             APInt BitsNotSet(APInt::getLowBitsSet(DstWidth, SrcWidth));
 779
 780             // If checking bits we know are clear, return zero.
 781             if ((CI2->getValue() & BitsNotSet) == CI2->getValue())
 782               return Constant::getNullValue(CI2->getType());
 783           }
 784         }
 785       }
 786       break;
 787     }
 788   } else if (isa<ConstantInt>(C1)) {
 789     // If C1 is a ConstantInt and C2 is not, swap the operands.
 790     if (Instruction::isCommutative(Opcode))
 791       return ConstantExpr::isDesirableBinOp(Opcode)
 792                  ? ConstantExpr::get(Opcode, C2, C1)
 793                  : ConstantFoldBinaryInstruction(Opcode, C2, C1);
 794   }
 795
 796   if (ConstantInt *CI1 = dyn_cast<ConstantInt>(C1)) {
 797     if (ConstantInt *CI2 = dyn_cast<ConstantInt>(C2)) {
 798       const APInt &C1V = CI1->getValue();
 799       const APInt &C2V = CI2->getValue();
 800       switch (Opcode) {
 801       default:
 802         break;
 803       case Instruction::Add:
 804         return ConstantInt::get(C1->getType(), C1V + C2V);
 805       case Instruction::Sub:
 806         return ConstantInt::get(C1->getType(), C1V - C2V);
 807       case Instruction::Mul:
 808         return ConstantInt::get(C1->getType(), C1V * C2V);
 809       case Instruction::UDiv:
 810         assert(!CI2->isZero() && "Div by zero handled above");
 811         return ConstantInt::get(CI1->getType(), C1V.udiv(C2V));
 812       case Instruction::SDiv:
 813         assert(!CI2->isZero() && "Div by zero handled above");
 814         if (C2V.isAllOnes() && C1V.isMinSignedValue())
 815           return PoisonValue::get(CI1->getType());   // MIN_INT / -1 -> poison
 816         return ConstantInt::get(CI1->getType(), C1V.sdiv(C2V));
 817       case Instruction::URem:
 818         assert(!CI2->isZero() && "Div by zero handled above");
 819         return ConstantInt::get(C1->getType(), C1V.urem(C2V));
 820       case Instruction::SRem:
 821         assert(!CI2->isZero() && "Div by zero handled above");
 822         if (C2V.isAllOnes() && C1V.isMinSignedValue())
 823           return PoisonValue::get(C1->getType()); // MIN_INT % -1 -> poison
 824         return ConstantInt::get(C1->getType(), C1V.srem(C2V));
 825       case Instruction::And:
 826         return ConstantInt::get(C1->getType(), C1V & C2V);
 827       case Instruction::Or:
 828         return ConstantInt::get(C1->getType(), C1V | C2V);
 829       case Instruction::Xor:
 830         return ConstantInt::get(C1->getType(), C1V ^ C2V);
 831       case Instruction::Shl:
 832         if (C2V.ult(C1V.getBitWidth()))
 833           return ConstantInt::get(C1->getType(), C1V.shl(C2V));
 834         return PoisonValue::get(C1->getType()); // too big shift is poison
 835       case Instruction::LShr:
 836         if (C2V.ult(C1V.getBitWidth()))
 837           return ConstantInt::get(C1->getType(), C1V.lshr(C2V));
 838         return PoisonValue::get(C1->getType()); // too big shift is poison
 839       case Instruction::AShr:
 840         if (C2V.ult(C1V.getBitWidth()))
 841           return ConstantInt::get(C1->getType(), C1V.ashr(C2V));
 842         return PoisonValue::get(C1->getType()); // too big shift is poison
 843       }
 844     }
 845
 846     if (C1 == ConstantExpr::getBinOpAbsorber(Opcode, C1->getType(),
 847                                              /*AllowLHSConstant*/ true))
 848       return C1;
 849   } else if (ConstantFP *CFP1 = dyn_cast<ConstantFP>(C1)) {
 850     if (ConstantFP *CFP2 = dyn_cast<ConstantFP>(C2)) {
 851       const APFloat &C1V = CFP1->getValueAPF();
 852       const APFloat &C2V = CFP2->getValueAPF();
 853       APFloat C3V = C1V;  // copy for modification
 854       switch (Opcode) {
 855       default:
 856         break;
 857       case Instruction::FAdd:
 858         (void)C3V.add(C2V, APFloat::rmNearestTiesToEven);
 859         return ConstantFP::get(C1->getType(), C3V);
 860       case Instruction::FSub:
 861         (void)C3V.subtract(C2V, APFloat::rmNearestTiesToEven);
 862         return ConstantFP::get(C1->getType(), C3V);
 863       case Instruction::FMul:
 864         (void)C3V.multiply(C2V, APFloat::rmNearestTiesToEven);
 865         return ConstantFP::get(C1->getType(), C3V);
 866       case Instruction::FDiv:
 867         (void)C3V.divide(C2V, APFloat::rmNearestTiesToEven);
 868         return ConstantFP::get(C1->getType(), C3V);
 869       case Instruction::FRem:
 870         (void)C3V.mod(C2V);
 871         return ConstantFP::get(C1->getType(), C3V);
 872       }
 873     }
 874   }
 875
 876   if (auto *VTy = dyn_cast<VectorType>(C1->getType())) {
 877     // Fast path for splatted constants.
 878     if (Constant *C2Splat = C2->getSplatValue()) {
 879       if (Instruction::isIntDivRem(Opcode) && C2Splat->isNullValue())
 880         return PoisonValue::get(VTy);
 881       if (Constant *C1Splat = C1->getSplatValue()) {
 882         Constant *Res =
 883             ConstantExpr::isDesirableBinOp(Opcode)
 884                 ? ConstantExpr::get(Opcode, C1Splat, C2Splat)
 885                 : ConstantFoldBinaryInstruction(Opcode, C1Splat, C2Splat);
 886         if (!Res)
 887           return nullptr;
 888         return ConstantVector::getSplat(VTy->getElementCount(), Res);
 889       }
 890     }
 891
 892     if (auto *FVTy = dyn_cast<FixedVectorType>(VTy)) {
 893       // Fold each element and create a vector constant from those constants.
 894       SmallVector<Constant*, 16> Result;
 895       Type *Ty = IntegerType::get(FVTy->getContext(), 32);
 896       for (unsigned i = 0, e = FVTy->getNumElements(); i != e; ++i) {
 897         Constant *ExtractIdx = ConstantInt::get(Ty, i);
 898         Constant *LHS = ConstantExpr::getExtractElement(C1, ExtractIdx);
 899         Constant *RHS = ConstantExpr::getExtractElement(C2, ExtractIdx);
 900         Constant *Res = ConstantExpr::isDesirableBinOp(Opcode)
 901                             ? ConstantExpr::get(Opcode, LHS, RHS)
 902                             : ConstantFoldBinaryInstruction(Opcode, LHS, RHS);
 903         if (!Res)
 904           return nullptr;
 905         Result.push_back(Res);
 906       }
 907
 908       return ConstantVector::get(Result);
 909     }
 910   }
 911
 912   if (ConstantExpr *CE1 = dyn_cast<ConstantExpr>(C1)) {
 913     // There are many possible foldings we could do here.  We should probably
 914     // at least fold add of a pointer with an integer into the appropriate
 915     // getelementptr.  This will improve alias analysis a bit.
 916
 917     // Given ((a + b) + c), if (b + c) folds to something interesting, return
 918     // (a + (b + c)).
 919     if (Instruction::isAssociative(Opcode) && CE1->getOpcode() == Opcode) {
 920       Constant *T = ConstantExpr::get(Opcode, CE1->getOperand(1), C2);
 921       if (!isa<ConstantExpr>(T) || cast<ConstantExpr>(T)->getOpcode() != Opcode)
 922         return ConstantExpr::get(Opcode, CE1->getOperand(0), T);
 923     }
 924   } else if (isa<ConstantExpr>(C2)) {
 925     // If C2 is a constant expr and C1 isn't, flop them around and fold the
 926     // other way if possible.
 927     if (Instruction::isCommutative(Opcode))
 928       return ConstantFoldBinaryInstruction(Opcode, C2, C1);
 929   }
 930
 931   // i1 can be simplified in many cases.
 932   if (C1->getType()->isIntegerTy(1)) {
 933     switch (Opcode) {
 934     case Instruction::Add:
 935     case Instruction::Sub:
 936       return ConstantExpr::getXor(C1, C2);
 937     case Instruction::Shl:
 938     case Instruction::LShr:
 939     case Instruction::AShr:
 940       // We can assume that C2 == 0.  If it were one the result would be
 941       // undefined because the shift value is as large as the bitwidth.
 942       return C1;
 943     case Instruction::SDiv:
 944     case Instruction::UDiv:
 945       // We can assume that C2 == 1.  If it were zero the result would be
 946       // undefined through division by zero.
 947       return C1;
 948     case Instruction::URem:
 949     case Instruction::SRem:
 950       // We can assume that C2 == 1.  If it were zero the result would be
 951       // undefined through division by zero.
 952       return ConstantInt::getFalse(C1->getContext());
 953     default:
 954       break;
 955     }
 956   }
 957
 958   // We don't know how to fold this.
 959   return nullptr;
 960 }
 961
 962 static ICmpInst::Predicate areGlobalsPotentiallyEqual(const GlobalValue *GV1,
 963                                                       const GlobalValue *GV2) {
 964   auto isGlobalUnsafeForEquality = [](const GlobalValue *GV) {
 965     if (GV->isInterposable() || GV->hasGlobalUnnamedAddr())
 966       return true;
 967     if (const auto *GVar = dyn_cast<GlobalVariable>(GV)) {
 968       Type *Ty = GVar->getValueType();
 969       // A global with opaque type might end up being zero sized.
 970       if (!Ty->isSized())
 971         return true;
 972       // A global with an empty type might lie at the address of any other
 973       // global.
 974       if (Ty->isEmptyTy())
 975         return true;
 976     }
 977     return false;
 978   };
 979   // Don't try to decide equality of aliases.
 980   if (!isa<GlobalAlias>(GV1) && !isa<GlobalAlias>(GV2))
 981     if (!isGlobalUnsafeForEquality(GV1) && !isGlobalUnsafeForEquality(GV2))
 982       return ICmpInst::ICMP_NE;
 983   return ICmpInst::BAD_ICMP_PREDICATE;
 984 }
 985
 986 /// This function determines if there is anything we can decide about the two
 987 /// constants provided. This doesn't need to handle simple things like integer
 988 /// comparisons, but should instead handle ConstantExprs and GlobalValues.
 989 /// If we can determine that the two constants have a particular relation to
 990 /// each other, we should return the corresponding ICmp predicate, otherwise
 991 /// return ICmpInst::BAD_ICMP_PREDICATE.
 992 static ICmpInst::Predicate evaluateICmpRelation(Constant *V1, Constant *V2) {
 993   assert(V1->getType() == V2->getType() &&
 994          "Cannot compare different types of values!");
 995   if (V1 == V2) return ICmpInst::ICMP_EQ;
 996
 997   // The following folds only apply to pointers.
 998   if (!V1->getType()->isPointerTy())
 999     return ICmpInst::BAD_ICMP_PREDICATE;
1000
1001   // To simplify this code we canonicalize the relation so that the first
1002   // operand is always the most "complex" of the two.  We consider simple
1003   // constants (like ConstantPointerNull) to be the simplest, followed by
1004   // BlockAddress, GlobalValues, and ConstantExpr's (the most complex).
1005   auto GetComplexity = [](Constant *V) {
1006     if (isa<ConstantExpr>(V))
1007       return 3;
1008     if (isa<GlobalValue>(V))
1009       return 2;
1010     if (isa<BlockAddress>(V))
1011       return 1;
1012     return 0;
1013   };
1014   if (GetComplexity(V1) < GetComplexity(V2)) {
1015     ICmpInst::Predicate SwappedRelation = evaluateICmpRelation(V2, V1);
1016     if (SwappedRelation != ICmpInst::BAD_ICMP_PREDICATE)
1017       return ICmpInst::getSwappedPredicate(SwappedRelation);
1018     return ICmpInst::BAD_ICMP_PREDICATE;
1019   }
1020
1021   if (const BlockAddress *BA = dyn_cast<BlockAddress>(V1)) {
1022     // Now we know that the RHS is a BlockAddress or simple constant.
1023     if (const BlockAddress *BA2 = dyn_cast<BlockAddress>(V2)) {
1024       // Block address in another function can't equal this one, but block
1025       // addresses in the current function might be the same if blocks are
1026       // empty.
1027       if (BA2->getFunction() != BA->getFunction())
1028         return ICmpInst::ICMP_NE;
1029     } else if (isa<ConstantPointerNull>(V2)) {
1030       return ICmpInst::ICMP_NE;
1031     }
1032   } else if (const GlobalValue *GV = dyn_cast<GlobalValue>(V1)) {
1033     // Now we know that the RHS is a GlobalValue, BlockAddress or simple
1034     // constant.
1035     if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) {
1036       return areGlobalsPotentiallyEqual(GV, GV2);
1037     } else if (isa<BlockAddress>(V2)) {
1038       return ICmpInst::ICMP_NE; // Globals never equal labels.
1039     } else if (isa<ConstantPointerNull>(V2)) {
1040       // GlobalVals can never be null unless they have external weak linkage.
1041       // We don't try to evaluate aliases here.
1042       // NOTE: We should not be doing this constant folding if null pointer
1043       // is considered valid for the function. But currently there is no way to
1044       // query it from the Constant type.
1045       if (!GV->hasExternalWeakLinkage() && !isa<GlobalAlias>(GV) &&
1046           !NullPointerIsDefined(nullptr /* F */,
1047                                 GV->getType()->getAddressSpace()))
1048         return ICmpInst::ICMP_UGT;
1049     }
1050   } else if (auto *CE1 = dyn_cast<ConstantExpr>(V1)) {
1051     // Ok, the LHS is known to be a constantexpr.  The RHS can be any of a
1052     // constantexpr, a global, block address, or a simple constant.
1053     Constant *CE1Op0 = CE1->getOperand(0);
1054
1055     switch (CE1->getOpcode()) {
1056     case Instruction::GetElementPtr: {
1057       GEPOperator *CE1GEP = cast<GEPOperator>(CE1);
1058       // Ok, since this is a getelementptr, we know that the constant has a
1059       // pointer type.  Check the various cases.
1060       if (isa<ConstantPointerNull>(V2)) {
1061         // If we are comparing a GEP to a null pointer, check to see if the base
1062         // of the GEP equals the null pointer.
1063         if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
1064           // If its not weak linkage, the GVal must have a non-zero address
1065           // so the result is greater-than
1066           if (!GV->hasExternalWeakLinkage() && CE1GEP->isInBounds())
1067             return ICmpInst::ICMP_UGT;
1068         }
1069       } else if (const GlobalValue *GV2 = dyn_cast<GlobalValue>(V2)) {
1070         if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
1071           if (GV != GV2) {
1072             if (CE1GEP->hasAllZeroIndices())
1073               return areGlobalsPotentiallyEqual(GV, GV2);
1074             return ICmpInst::BAD_ICMP_PREDICATE;
1075           }
1076         }
1077       } else if (const auto *CE2GEP = dyn_cast<GEPOperator>(V2)) {
1078         // By far the most common case to handle is when the base pointers are
1079         // obviously to the same global.
1080         const Constant *CE2Op0 = cast<Constant>(CE2GEP->getPointerOperand());
1081         if (isa<GlobalValue>(CE1Op0) && isa<GlobalValue>(CE2Op0)) {
1082           // Don't know relative ordering, but check for inequality.
1083           if (CE1Op0 != CE2Op0) {
1084             if (CE1GEP->hasAllZeroIndices() && CE2GEP->hasAllZeroIndices())
1085               return areGlobalsPotentiallyEqual(cast<GlobalValue>(CE1Op0),
1086                                                 cast<GlobalValue>(CE2Op0));
1087             return ICmpInst::BAD_ICMP_PREDICATE;
1088           }
1089         }
1090       }
1091       break;
1092     }
1093     default:
1094       break;
1095     }
1096   }
1097
1098   return ICmpInst::BAD_ICMP_PREDICATE;
1099 }
1100
1101 Constant *llvm::ConstantFoldCompareInstruction(CmpInst::Predicate Predicate,
1102                                                Constant *C1, Constant *C2) {
1103   Type *ResultTy;
1104   if (VectorType *VT = dyn_cast<VectorType>(C1->getType()))
1105     ResultTy = VectorType::get(Type::getInt1Ty(C1->getContext()),
1106                                VT->getElementCount());
1107   else
1108     ResultTy = Type::getInt1Ty(C1->getContext());
1109
1110   // Fold FCMP_FALSE/FCMP_TRUE unconditionally.
1111   if (Predicate == FCmpInst::FCMP_FALSE)
1112     return Constant::getNullValue(ResultTy);
1113
1114   if (Predicate == FCmpInst::FCMP_TRUE)
1115     return Constant::getAllOnesValue(ResultTy);
1116
1117   // Handle some degenerate cases first
1118   if (isa<PoisonValue>(C1) || isa<PoisonValue>(C2))
1119     return PoisonValue::get(ResultTy);
1120
1121   if (isa<UndefValue>(C1) || isa<UndefValue>(C2)) {
1122     bool isIntegerPredicate = ICmpInst::isIntPredicate(Predicate);
1123     // For EQ and NE, we can always pick a value for the undef to make the
1124     // predicate pass or fail, so we can return undef.
1125     // Also, if both operands are undef, we can return undef for int comparison.
1126     if (ICmpInst::isEquality(Predicate) || (isIntegerPredicate && C1 == C2))
1127       return UndefValue::get(ResultTy);
1128
1129     // Otherwise, for integer compare, pick the same value as the non-undef
1130     // operand, and fold it to true or false.
1131     if (isIntegerPredicate)
1132       return ConstantInt::get(ResultTy, CmpInst::isTrueWhenEqual(Predicate));
1133
1134     // Choosing NaN for the undef will always make unordered comparison succeed
1135     // and ordered comparison fails.
1136     return ConstantInt::get(ResultTy, CmpInst::isUnordered(Predicate));
1137   }
1138
1139   if (C2->isNullValue()) {
1140     // The caller is expected to commute the operands if the constant expression
1141     // is C2.
1142     // C1 >= 0 --> true
1143     if (Predicate == ICmpInst::ICMP_UGE)
1144       return Constant::getAllOnesValue(ResultTy);
1145     // C1 < 0 --> false
1146     if (Predicate == ICmpInst::ICMP_ULT)
1147       return Constant::getNullValue(ResultTy);
1148   }
1149
1150   // If the comparison is a comparison between two i1's, simplify it.
1151   if (C1->getType()->isIntegerTy(1)) {
1152     switch (Predicate) {
1153     case ICmpInst::ICMP_EQ:
1154       if (isa<ConstantInt>(C2))
1155         return ConstantExpr::getXor(C1, ConstantExpr::getNot(C2));
1156       return ConstantExpr::getXor(ConstantExpr::getNot(C1), C2);
1157     case ICmpInst::ICMP_NE:
1158       return ConstantExpr::getXor(C1, C2);
1159     default:
1160       break;
1161     }
1162   }
1163
1164   if (isa<ConstantInt>(C1) && isa<ConstantInt>(C2)) {
1165     const APInt &V1 = cast<ConstantInt>(C1)->getValue();
1166     const APInt &V2 = cast<ConstantInt>(C2)->getValue();
1167     return ConstantInt::get(ResultTy, ICmpInst::compare(V1, V2, Predicate));
1168   } else if (isa<ConstantFP>(C1) && isa<ConstantFP>(C2)) {
1169     const APFloat &C1V = cast<ConstantFP>(C1)->getValueAPF();
1170     const APFloat &C2V = cast<ConstantFP>(C2)->getValueAPF();
1171     return ConstantInt::get(ResultTy, FCmpInst::compare(C1V, C2V, Predicate));
1172   } else if (auto *C1VTy = dyn_cast<VectorType>(C1->getType())) {
1173
1174     // Fast path for splatted constants.
1175     if (Constant *C1Splat = C1->getSplatValue())
1176       if (Constant *C2Splat = C2->getSplatValue())
1177         if (Constant *Elt =
1178                 ConstantFoldCompareInstruction(Predicate, C1Splat, C2Splat))
1179           return ConstantVector::getSplat(C1VTy->getElementCount(), Elt);
1180
1181     // Do not iterate on scalable vector. The number of elements is unknown at
1182     // compile-time.
1183     if (isa<ScalableVectorType>(C1VTy))
1184       return nullptr;
1185
1186     // If we can constant fold the comparison of each element, constant fold
1187     // the whole vector comparison.
1188     SmallVector<Constant*, 4> ResElts;
1189     Type *Ty = IntegerType::get(C1->getContext(), 32);
1190     // Compare the elements, producing an i1 result or constant expr.
1191     for (unsigned I = 0, E = C1VTy->getElementCount().getKnownMinValue();
1192          I != E; ++I) {
1193       Constant *C1E =
1194           ConstantExpr::getExtractElement(C1, ConstantInt::get(Ty, I));
1195       Constant *C2E =
1196           ConstantExpr::getExtractElement(C2, ConstantInt::get(Ty, I));
1197       Constant *Elt = ConstantFoldCompareInstruction(Predicate, C1E, C2E);
1198       if (!Elt)
1199         return nullptr;
1200
1201       ResElts.push_back(Elt);
1202     }
1203
1204     return ConstantVector::get(ResElts);
1205   }
1206
1207   if (C1->getType()->isFPOrFPVectorTy()) {
1208     if (C1 == C2) {
1209       // We know that C1 == C2 || isUnordered(C1, C2).
1210       if (Predicate == FCmpInst::FCMP_ONE)
1211         return ConstantInt::getFalse(ResultTy);
1212       else if (Predicate == FCmpInst::FCMP_UEQ)
1213         return ConstantInt::getTrue(ResultTy);
1214     }
1215   } else {
1216     // Evaluate the relation between the two constants, per the predicate.
1217     int Result = -1;  // -1 = unknown, 0 = known false, 1 = known true.
1218     switch (evaluateICmpRelation(C1, C2)) {
1219     default: llvm_unreachable("Unknown relational!");
1220     case ICmpInst::BAD_ICMP_PREDICATE:
1221       break;  // Couldn't determine anything about these constants.
1222     case ICmpInst::ICMP_EQ:   // We know the constants are equal!
1223       // If we know the constants are equal, we can decide the result of this
1224       // computation precisely.
1225       Result = ICmpInst::isTrueWhenEqual(Predicate);
1226       break;
1227     case ICmpInst::ICMP_ULT:
1228       switch (Predicate) {
1229       case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_ULE:
1230         Result = 1; break;
1231       case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_UGE:
1232         Result = 0; break;
1233       default:
1234         break;
1235       }
1236       break;
1237     case ICmpInst::ICMP_SLT:
1238       switch (Predicate) {
1239       case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SLE:
1240         Result = 1; break;
1241       case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SGE:
1242         Result = 0; break;
1243       default:
1244         break;
1245       }
1246       break;
1247     case ICmpInst::ICMP_UGT:
1248       switch (Predicate) {
1249       case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_UGE:
1250         Result = 1; break;
1251       case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_ULE:
1252         Result = 0; break;
1253       default:
1254         break;
1255       }
1256       break;
1257     case ICmpInst::ICMP_SGT:
1258       switch (Predicate) {
1259       case ICmpInst::ICMP_SGT: case ICmpInst::ICMP_NE: case ICmpInst::ICMP_SGE:
1260         Result = 1; break;
1261       case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_EQ: case ICmpInst::ICMP_SLE:
1262         Result = 0; break;
1263       default:
1264         break;
1265       }
1266       break;
1267     case ICmpInst::ICMP_ULE:
1268       if (Predicate == ICmpInst::ICMP_UGT)
1269         Result = 0;
1270       if (Predicate == ICmpInst::ICMP_ULT || Predicate == ICmpInst::ICMP_ULE)
1271         Result = 1;
1272       break;
1273     case ICmpInst::ICMP_SLE:
1274       if (Predicate == ICmpInst::ICMP_SGT)
1275         Result = 0;
1276       if (Predicate == ICmpInst::ICMP_SLT || Predicate == ICmpInst::ICMP_SLE)
1277         Result = 1;
1278       break;
1279     case ICmpInst::ICMP_UGE:
1280       if (Predicate == ICmpInst::ICMP_ULT)
1281         Result = 0;
1282       if (Predicate == ICmpInst::ICMP_UGT || Predicate == ICmpInst::ICMP_UGE)
1283         Result = 1;
1284       break;
1285     case ICmpInst::ICMP_SGE:
1286       if (Predicate == ICmpInst::ICMP_SLT)
1287         Result = 0;
1288       if (Predicate == ICmpInst::ICMP_SGT || Predicate == ICmpInst::ICMP_SGE)
1289         Result = 1;
1290       break;
1291     case ICmpInst::ICMP_NE:
1292       if (Predicate == ICmpInst::ICMP_EQ)
1293         Result = 0;
1294       if (Predicate == ICmpInst::ICMP_NE)
1295         Result = 1;
1296       break;
1297     }
1298
1299     // If we evaluated the result, return it now.
1300     if (Result != -1)
1301       return ConstantInt::get(ResultTy, Result);
1302
1303     if ((!isa<ConstantExpr>(C1) && isa<ConstantExpr>(C2)) ||
1304         (C1->isNullValue() && !C2->isNullValue())) {
1305       // If C2 is a constant expr and C1 isn't, flip them around and fold the
1306       // other way if possible.
1307       // Also, if C1 is null and C2 isn't, flip them around.
1308       Predicate = ICmpInst::getSwappedPredicate(Predicate);
1309       return ConstantFoldCompareInstruction(Predicate, C2, C1);
1310     }
1311   }
1312   return nullptr;
1313 }
1314
1315 Constant *llvm::ConstantFoldGetElementPtr(Type *PointeeTy, Constant *C,
1316                                           std::optional<ConstantRange> InRange,
1317                                           ArrayRef<Value *> Idxs) {
1318   if (Idxs.empty()) return C;
1319
1320   Type *GEPTy = GetElementPtrInst::getGEPReturnType(
1321       C, ArrayRef((Value *const *)Idxs.data(), Idxs.size()));
1322
1323   if (isa<PoisonValue>(C))
1324     return PoisonValue::get(GEPTy);
1325
1326   if (isa<UndefValue>(C))
1327     return UndefValue::get(GEPTy);
1328
1329   auto IsNoOp = [&]() {
1330     // Avoid losing inrange information.
1331     if (InRange)
1332       return false;
1333
1334     return all_of(Idxs, [](Value *Idx) {
1335       Constant *IdxC = cast<Constant>(Idx);
1336       return IdxC->isNullValue() || isa<UndefValue>(IdxC);
1337     });
1338   };
1339   if (IsNoOp())
1340     return GEPTy->isVectorTy() && !C->getType()->isVectorTy()
1341                ? ConstantVector::getSplat(
1342                      cast<VectorType>(GEPTy)->getElementCount(), C)
1343                : C;
1344
1345   return nullptr;
1346 }