llvm/lib/IR/Instructions.cpp

   1 //===- Instructions.cpp - Implement the LLVM instructions -----------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements all of the non-inline methods for the LLVM instruction
  10 // classes.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/IR/Instructions.h"
  15 #include "LLVMContextImpl.h"
  16 #include "llvm/ADT/SmallBitVector.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/ADT/Twine.h"
  19 #include "llvm/IR/Attributes.h"
  20 #include "llvm/IR/BasicBlock.h"
  21 #include "llvm/IR/Constant.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DataLayout.h"
  24 #include "llvm/IR/DerivedTypes.h"
  25 #include "llvm/IR/Function.h"
  26 #include "llvm/IR/InstrTypes.h"
  27 #include "llvm/IR/Instruction.h"
  28 #include "llvm/IR/Intrinsics.h"
  29 #include "llvm/IR/LLVMContext.h"
  30 #include "llvm/IR/MDBuilder.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/Module.h"
  33 #include "llvm/IR/Operator.h"
  34 #include "llvm/IR/ProfDataUtils.h"
  35 #include "llvm/IR/Type.h"
  36 #include "llvm/IR/Value.h"
  37 #include "llvm/Support/AtomicOrdering.h"
  38 #include "llvm/Support/Casting.h"
  39 #include "llvm/Support/ErrorHandling.h"
  40 #include "llvm/Support/MathExtras.h"
  41 #include "llvm/Support/ModRef.h"
  42 #include "llvm/Support/TypeSize.h"
  43 #include <algorithm>
  44 #include <cassert>
  45 #include <cstdint>
  46 #include <optional>
  47 #include <vector>
  48
  49 using namespace llvm;
  50
  51 static cl::opt<bool> DisableI2pP2iOpt(
  52     "disable-i2p-p2i-opt", cl::init(false),
  53     cl::desc("Disables inttoptr/ptrtoint roundtrip optimization"));
  54
  55 //===----------------------------------------------------------------------===//
  56 //                            AllocaInst Class
  57 //===----------------------------------------------------------------------===//
  58
  59 std::optional<TypeSize>
  60 AllocaInst::getAllocationSize(const DataLayout &DL) const {
  61   TypeSize Size = DL.getTypeAllocSize(getAllocatedType());
  62   if (isArrayAllocation()) {
  63     auto *C = dyn_cast<ConstantInt>(getArraySize());
  64     if (!C)
  65       return std::nullopt;
  66     assert(!Size.isScalable() && "Array elements cannot have a scalable size");
  67     Size *= C->getZExtValue();
  68   }
  69   return Size;
  70 }
  71
  72 std::optional<TypeSize>
  73 AllocaInst::getAllocationSizeInBits(const DataLayout &DL) const {
  74   std::optional<TypeSize> Size = getAllocationSize(DL);
  75   if (Size)
  76     return *Size * 8;
  77   return std::nullopt;
  78 }
  79
  80 //===----------------------------------------------------------------------===//
  81 //                              SelectInst Class
  82 //===----------------------------------------------------------------------===//
  83
  84 /// areInvalidOperands - Return a string if the specified operands are invalid
  85 /// for a select operation, otherwise return null.
  86 const char *SelectInst::areInvalidOperands(Value *Op0, Value *Op1, Value *Op2) {
  87   if (Op1->getType() != Op2->getType())
  88     return "both values to select must have same type";
  89
  90   if (Op1->getType()->isTokenTy())
  91     return "select values cannot have token type";
  92
  93   if (VectorType *VT = dyn_cast<VectorType>(Op0->getType())) {
  94     // Vector select.
  95     if (VT->getElementType() != Type::getInt1Ty(Op0->getContext()))
  96       return "vector select condition element type must be i1";
  97     VectorType *ET = dyn_cast<VectorType>(Op1->getType());
  98     if (!ET)
  99       return "selected values for vector select must be vectors";
 100     if (ET->getElementCount() != VT->getElementCount())
 101       return "vector select requires selected vectors to have "
 102                    "the same vector length as select condition";
 103   } else if (Op0->getType() != Type::getInt1Ty(Op0->getContext())) {
 104     return "select condition must be i1 or <n x i1>";
 105   }
 106   return nullptr;
 107 }
 108
 109 //===----------------------------------------------------------------------===//
 110 //                               PHINode Class
 111 //===----------------------------------------------------------------------===//
 112
 113 PHINode::PHINode(const PHINode &PN)
 114     : Instruction(PN.getType(), Instruction::PHI, nullptr, PN.getNumOperands()),
 115       ReservedSpace(PN.getNumOperands()) {
 116   allocHungoffUses(PN.getNumOperands());
 117   std::copy(PN.op_begin(), PN.op_end(), op_begin());
 118   copyIncomingBlocks(make_range(PN.block_begin(), PN.block_end()));
 119   SubclassOptionalData = PN.SubclassOptionalData;
 120 }
 121
 122 // removeIncomingValue - Remove an incoming value.  This is useful if a
 123 // predecessor basic block is deleted.
 124 Value *PHINode::removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty) {
 125   Value *Removed = getIncomingValue(Idx);
 126
 127   // Move everything after this operand down.
 128   //
 129   // FIXME: we could just swap with the end of the list, then erase.  However,
 130   // clients might not expect this to happen.  The code as it is thrashes the
 131   // use/def lists, which is kinda lame.
 132   std::copy(op_begin() + Idx + 1, op_end(), op_begin() + Idx);
 133   copyIncomingBlocks(drop_begin(blocks(), Idx + 1), Idx);
 134
 135   // Nuke the last value.
 136   Op<-1>().set(nullptr);
 137   setNumHungOffUseOperands(getNumOperands() - 1);
 138
 139   // If the PHI node is dead, because it has zero entries, nuke it now.
 140   if (getNumOperands() == 0 && DeletePHIIfEmpty) {
 141     // If anyone is using this PHI, make them use a dummy value instead...
 142     replaceAllUsesWith(PoisonValue::get(getType()));
 143     eraseFromParent();
 144   }
 145   return Removed;
 146 }
 147
 148 void PHINode::removeIncomingValueIf(function_ref<bool(unsigned)> Predicate,
 149                                     bool DeletePHIIfEmpty) {
 150   SmallDenseSet<unsigned> RemoveIndices;
 151   for (unsigned Idx = 0; Idx < getNumIncomingValues(); ++Idx)
 152     if (Predicate(Idx))
 153       RemoveIndices.insert(Idx);
 154
 155   if (RemoveIndices.empty())
 156     return;
 157
 158   // Remove operands.
 159   auto NewOpEnd = remove_if(operands(), [&](Use &U) {
 160     return RemoveIndices.contains(U.getOperandNo());
 161   });
 162   for (Use &U : make_range(NewOpEnd, op_end()))
 163     U.set(nullptr);
 164
 165   // Remove incoming blocks.
 166   (void)std::remove_if(const_cast<block_iterator>(block_begin()),
 167                  const_cast<block_iterator>(block_end()), [&](BasicBlock *&BB) {
 168                    return RemoveIndices.contains(&BB - block_begin());
 169                  });
 170
 171   setNumHungOffUseOperands(getNumOperands() - RemoveIndices.size());
 172
 173   // If the PHI node is dead, because it has zero entries, nuke it now.
 174   if (getNumOperands() == 0 && DeletePHIIfEmpty) {
 175     // If anyone is using this PHI, make them use a dummy value instead...
 176     replaceAllUsesWith(PoisonValue::get(getType()));
 177     eraseFromParent();
 178   }
 179 }
 180
 181 /// growOperands - grow operands - This grows the operand list in response
 182 /// to a push_back style of operation.  This grows the number of ops by 1.5
 183 /// times.
 184 ///
 185 void PHINode::growOperands() {
 186   unsigned e = getNumOperands();
 187   unsigned NumOps = e + e / 2;
 188   if (NumOps < 2) NumOps = 2;      // 2 op PHI nodes are VERY common.
 189
 190   ReservedSpace = NumOps;
 191   growHungoffUses(ReservedSpace, /* IsPhi */ true);
 192 }
 193
 194 /// hasConstantValue - If the specified PHI node always merges together the same
 195 /// value, return the value, otherwise return null.
 196 Value *PHINode::hasConstantValue() const {
 197   // Exploit the fact that phi nodes always have at least one entry.
 198   Value *ConstantValue = getIncomingValue(0);
 199   for (unsigned i = 1, e = getNumIncomingValues(); i != e; ++i)
 200     if (getIncomingValue(i) != ConstantValue && getIncomingValue(i) != this) {
 201       if (ConstantValue != this)
 202         return nullptr; // Incoming values not all the same.
 203        // The case where the first value is this PHI.
 204       ConstantValue = getIncomingValue(i);
 205     }
 206   if (ConstantValue == this)
 207     return UndefValue::get(getType());
 208   return ConstantValue;
 209 }
 210
 211 /// hasConstantOrUndefValue - Whether the specified PHI node always merges
 212 /// together the same value, assuming that undefs result in the same value as
 213 /// non-undefs.
 214 /// Unlike \ref hasConstantValue, this does not return a value because the
 215 /// unique non-undef incoming value need not dominate the PHI node.
 216 bool PHINode::hasConstantOrUndefValue() const {
 217   Value *ConstantValue = nullptr;
 218   for (unsigned i = 0, e = getNumIncomingValues(); i != e; ++i) {
 219     Value *Incoming = getIncomingValue(i);
 220     if (Incoming != this && !isa<UndefValue>(Incoming)) {
 221       if (ConstantValue && ConstantValue != Incoming)
 222         return false;
 223       ConstantValue = Incoming;
 224     }
 225   }
 226   return true;
 227 }
 228
 229 //===----------------------------------------------------------------------===//
 230 //                       LandingPadInst Implementation
 231 //===----------------------------------------------------------------------===//
 232
 233 LandingPadInst::LandingPadInst(Type *RetTy, unsigned NumReservedValues,
 234                                const Twine &NameStr, Instruction *InsertBefore)
 235     : Instruction(RetTy, Instruction::LandingPad, nullptr, 0, InsertBefore) {
 236   init(NumReservedValues, NameStr);
 237 }
 238
 239 LandingPadInst::LandingPadInst(Type *RetTy, unsigned NumReservedValues,
 240                                const Twine &NameStr, BasicBlock *InsertAtEnd)
 241     : Instruction(RetTy, Instruction::LandingPad, nullptr, 0, InsertAtEnd) {
 242   init(NumReservedValues, NameStr);
 243 }
 244
 245 LandingPadInst::LandingPadInst(const LandingPadInst &LP)
 246     : Instruction(LP.getType(), Instruction::LandingPad, nullptr,
 247                   LP.getNumOperands()),
 248       ReservedSpace(LP.getNumOperands()) {
 249   allocHungoffUses(LP.getNumOperands());
 250   Use *OL = getOperandList();
 251   const Use *InOL = LP.getOperandList();
 252   for (unsigned I = 0, E = ReservedSpace; I != E; ++I)
 253     OL[I] = InOL[I];
 254
 255   setCleanup(LP.isCleanup());
 256 }
 257
 258 LandingPadInst *LandingPadInst::Create(Type *RetTy, unsigned NumReservedClauses,
 259                                        const Twine &NameStr,
 260                                        Instruction *InsertBefore) {
 261   return new LandingPadInst(RetTy, NumReservedClauses, NameStr, InsertBefore);
 262 }
 263
 264 LandingPadInst *LandingPadInst::Create(Type *RetTy, unsigned NumReservedClauses,
 265                                        const Twine &NameStr,
 266                                        BasicBlock *InsertAtEnd) {
 267   return new LandingPadInst(RetTy, NumReservedClauses, NameStr, InsertAtEnd);
 268 }
 269
 270 void LandingPadInst::init(unsigned NumReservedValues, const Twine &NameStr) {
 271   ReservedSpace = NumReservedValues;
 272   setNumHungOffUseOperands(0);
 273   allocHungoffUses(ReservedSpace);
 274   setName(NameStr);
 275   setCleanup(false);
 276 }
 277
 278 /// growOperands - grow operands - This grows the operand list in response to a
 279 /// push_back style of operation. This grows the number of ops by 2 times.
 280 void LandingPadInst::growOperands(unsigned Size) {
 281   unsigned e = getNumOperands();
 282   if (ReservedSpace >= e + Size) return;
 283   ReservedSpace = (std::max(e, 1U) + Size / 2) * 2;
 284   growHungoffUses(ReservedSpace);
 285 }
 286
 287 void LandingPadInst::addClause(Constant *Val) {
 288   unsigned OpNo = getNumOperands();
 289   growOperands(1);
 290   assert(OpNo < ReservedSpace && "Growing didn't work!");
 291   setNumHungOffUseOperands(getNumOperands() + 1);
 292   getOperandList()[OpNo] = Val;
 293 }
 294
 295 //===----------------------------------------------------------------------===//
 296 //                        CallBase Implementation
 297 //===----------------------------------------------------------------------===//
 298
 299 CallBase *CallBase::Create(CallBase *CB, ArrayRef<OperandBundleDef> Bundles,
 300                            Instruction *InsertPt) {
 301   switch (CB->getOpcode()) {
 302   case Instruction::Call:
 303     return CallInst::Create(cast<CallInst>(CB), Bundles, InsertPt);
 304   case Instruction::Invoke:
 305     return InvokeInst::Create(cast<InvokeInst>(CB), Bundles, InsertPt);
 306   case Instruction::CallBr:
 307     return CallBrInst::Create(cast<CallBrInst>(CB), Bundles, InsertPt);
 308   default:
 309     llvm_unreachable("Unknown CallBase sub-class!");
 310   }
 311 }
 312
 313 CallBase *CallBase::Create(CallBase *CI, OperandBundleDef OpB,
 314                            Instruction *InsertPt) {
 315   SmallVector<OperandBundleDef, 2> OpDefs;
 316   for (unsigned i = 0, e = CI->getNumOperandBundles(); i < e; ++i) {
 317     auto ChildOB = CI->getOperandBundleAt(i);
 318     if (ChildOB.getTagName() != OpB.getTag())
 319       OpDefs.emplace_back(ChildOB);
 320   }
 321   OpDefs.emplace_back(OpB);
 322   return CallBase::Create(CI, OpDefs, InsertPt);
 323 }
 324
 325
 326 Function *CallBase::getCaller() { return getParent()->getParent(); }
 327
 328 unsigned CallBase::getNumSubclassExtraOperandsDynamic() const {
 329   assert(getOpcode() == Instruction::CallBr && "Unexpected opcode!");
 330   return cast<CallBrInst>(this)->getNumIndirectDests() + 1;
 331 }
 332
 333 bool CallBase::isIndirectCall() const {
 334   const Value *V = getCalledOperand();
 335   if (isa<Function>(V) || isa<Constant>(V))
 336     return false;
 337   return !isInlineAsm();
 338 }
 339
 340 /// Tests if this call site must be tail call optimized. Only a CallInst can
 341 /// be tail call optimized.
 342 bool CallBase::isMustTailCall() const {
 343   if (auto *CI = dyn_cast<CallInst>(this))
 344     return CI->isMustTailCall();
 345   return false;
 346 }
 347
 348 /// Tests if this call site is marked as a tail call.
 349 bool CallBase::isTailCall() const {
 350   if (auto *CI = dyn_cast<CallInst>(this))
 351     return CI->isTailCall();
 352   return false;
 353 }
 354
 355 Intrinsic::ID CallBase::getIntrinsicID() const {
 356   if (auto *F = getCalledFunction())
 357     return F->getIntrinsicID();
 358   return Intrinsic::not_intrinsic;
 359 }
 360
 361 FPClassTest CallBase::getRetNoFPClass() const {
 362   FPClassTest Mask = Attrs.getRetNoFPClass();
 363
 364   if (const Function *F = getCalledFunction())
 365     Mask |= F->getAttributes().getRetNoFPClass();
 366   return Mask;
 367 }
 368
 369 FPClassTest CallBase::getParamNoFPClass(unsigned i) const {
 370   FPClassTest Mask = Attrs.getParamNoFPClass(i);
 371
 372   if (const Function *F = getCalledFunction())
 373     Mask |= F->getAttributes().getParamNoFPClass(i);
 374   return Mask;
 375 }
 376
 377 bool CallBase::isReturnNonNull() const {
 378   if (hasRetAttr(Attribute::NonNull))
 379     return true;
 380
 381   if (getRetDereferenceableBytes() > 0 &&
 382       !NullPointerIsDefined(getCaller(), getType()->getPointerAddressSpace()))
 383     return true;
 384
 385   return false;
 386 }
 387
 388 Value *CallBase::getArgOperandWithAttribute(Attribute::AttrKind Kind) const {
 389   unsigned Index;
 390
 391   if (Attrs.hasAttrSomewhere(Kind, &Index))
 392     return getArgOperand(Index - AttributeList::FirstArgIndex);
 393   if (const Function *F = getCalledFunction())
 394     if (F->getAttributes().hasAttrSomewhere(Kind, &Index))
 395       return getArgOperand(Index - AttributeList::FirstArgIndex);
 396
 397   return nullptr;
 398 }
 399
 400 /// Determine whether the argument or parameter has the given attribute.
 401 bool CallBase::paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const {
 402   assert(ArgNo < arg_size() && "Param index out of bounds!");
 403
 404   if (Attrs.hasParamAttr(ArgNo, Kind))
 405     return true;
 406
 407   const Function *F = getCalledFunction();
 408   if (!F)
 409     return false;
 410
 411   if (!F->getAttributes().hasParamAttr(ArgNo, Kind))
 412     return false;
 413
 414   // Take into account mod/ref by operand bundles.
 415   switch (Kind) {
 416   case Attribute::ReadNone:
 417     return !hasReadingOperandBundles() && !hasClobberingOperandBundles();
 418   case Attribute::ReadOnly:
 419     return !hasClobberingOperandBundles();
 420   case Attribute::WriteOnly:
 421     return !hasReadingOperandBundles();
 422   default:
 423     return true;
 424   }
 425 }
 426
 427 bool CallBase::hasFnAttrOnCalledFunction(Attribute::AttrKind Kind) const {
 428   Value *V = getCalledOperand();
 429   if (auto *CE = dyn_cast<ConstantExpr>(V))
 430     if (CE->getOpcode() == BitCast)
 431       V = CE->getOperand(0);
 432
 433   if (auto *F = dyn_cast<Function>(V))
 434     return F->getAttributes().hasFnAttr(Kind);
 435
 436   return false;
 437 }
 438
 439 bool CallBase::hasFnAttrOnCalledFunction(StringRef Kind) const {
 440   Value *V = getCalledOperand();
 441   if (auto *CE = dyn_cast<ConstantExpr>(V))
 442     if (CE->getOpcode() == BitCast)
 443       V = CE->getOperand(0);
 444
 445   if (auto *F = dyn_cast<Function>(V))
 446     return F->getAttributes().hasFnAttr(Kind);
 447
 448   return false;
 449 }
 450
 451 template <typename AK>
 452 Attribute CallBase::getFnAttrOnCalledFunction(AK Kind) const {
 453   if constexpr (std::is_same_v<AK, Attribute::AttrKind>) {
 454     // getMemoryEffects() correctly combines memory effects from the call-site,
 455     // operand bundles and function.
 456     assert(Kind != Attribute::Memory && "Use getMemoryEffects() instead");
 457   }
 458
 459   Value *V = getCalledOperand();
 460   if (auto *CE = dyn_cast<ConstantExpr>(V))
 461     if (CE->getOpcode() == BitCast)
 462       V = CE->getOperand(0);
 463
 464   if (auto *F = dyn_cast<Function>(V))
 465     return F->getAttributes().getFnAttr(Kind);
 466
 467   return Attribute();
 468 }
 469
 470 template Attribute
 471 CallBase::getFnAttrOnCalledFunction(Attribute::AttrKind Kind) const;
 472 template Attribute CallBase::getFnAttrOnCalledFunction(StringRef Kind) const;
 473
 474 void CallBase::getOperandBundlesAsDefs(
 475     SmallVectorImpl<OperandBundleDef> &Defs) const {
 476   for (unsigned i = 0, e = getNumOperandBundles(); i != e; ++i)
 477     Defs.emplace_back(getOperandBundleAt(i));
 478 }
 479
 480 CallBase::op_iterator
 481 CallBase::populateBundleOperandInfos(ArrayRef<OperandBundleDef> Bundles,
 482                                      const unsigned BeginIndex) {
 483   auto It = op_begin() + BeginIndex;
 484   for (auto &B : Bundles)
 485     It = std::copy(B.input_begin(), B.input_end(), It);
 486
 487   auto *ContextImpl = getContext().pImpl;
 488   auto BI = Bundles.begin();
 489   unsigned CurrentIndex = BeginIndex;
 490
 491   for (auto &BOI : bundle_op_infos()) {
 492     assert(BI != Bundles.end() && "Incorrect allocation?");
 493
 494     BOI.Tag = ContextImpl->getOrInsertBundleTag(BI->getTag());
 495     BOI.Begin = CurrentIndex;
 496     BOI.End = CurrentIndex + BI->input_size();
 497     CurrentIndex = BOI.End;
 498     BI++;
 499   }
 500
 501   assert(BI == Bundles.end() && "Incorrect allocation?");
 502
 503   return It;
 504 }
 505
 506 CallBase::BundleOpInfo &CallBase::getBundleOpInfoForOperand(unsigned OpIdx) {
 507   /// When there isn't many bundles, we do a simple linear search.
 508   /// Else fallback to a binary-search that use the fact that bundles usually
 509   /// have similar number of argument to get faster convergence.
 510   if (bundle_op_info_end() - bundle_op_info_begin() < 8) {
 511     for (auto &BOI : bundle_op_infos())
 512       if (BOI.Begin <= OpIdx && OpIdx < BOI.End)
 513         return BOI;
 514
 515     llvm_unreachable("Did not find operand bundle for operand!");
 516   }
 517
 518   assert(OpIdx >= arg_size() && "the Idx is not in the operand bundles");
 519   assert(bundle_op_info_end() - bundle_op_info_begin() > 0 &&
 520          OpIdx < std::prev(bundle_op_info_end())->End &&
 521          "The Idx isn't in the operand bundle");
 522
 523   /// We need a decimal number below and to prevent using floating point numbers
 524   /// we use an intergal value multiplied by this constant.
 525   constexpr unsigned NumberScaling = 1024;
 526
 527   bundle_op_iterator Begin = bundle_op_info_begin();
 528   bundle_op_iterator End = bundle_op_info_end();
 529   bundle_op_iterator Current = Begin;
 530
 531   while (Begin != End) {
 532     unsigned ScaledOperandPerBundle =
 533         NumberScaling * (std::prev(End)->End - Begin->Begin) / (End - Begin);
 534     Current = Begin + (((OpIdx - Begin->Begin) * NumberScaling) /
 535                        ScaledOperandPerBundle);
 536     if (Current >= End)
 537       Current = std::prev(End);
 538     assert(Current < End && Current >= Begin &&
 539            "the operand bundle doesn't cover every value in the range");
 540     if (OpIdx >= Current->Begin && OpIdx < Current->End)
 541       break;
 542     if (OpIdx >= Current->End)
 543       Begin = Current + 1;
 544     else
 545       End = Current;
 546   }
 547
 548   assert(OpIdx >= Current->Begin && OpIdx < Current->End &&
 549          "the operand bundle doesn't cover every value in the range");
 550   return *Current;
 551 }
 552
 553 CallBase *CallBase::addOperandBundle(CallBase *CB, uint32_t ID,
 554                                      OperandBundleDef OB,
 555                                      Instruction *InsertPt) {
 556   if (CB->getOperandBundle(ID))
 557     return CB;
 558
 559   SmallVector<OperandBundleDef, 1> Bundles;
 560   CB->getOperandBundlesAsDefs(Bundles);
 561   Bundles.push_back(OB);
 562   return Create(CB, Bundles, InsertPt);
 563 }
 564
 565 CallBase *CallBase::removeOperandBundle(CallBase *CB, uint32_t ID,
 566                                         Instruction *InsertPt) {
 567   SmallVector<OperandBundleDef, 1> Bundles;
 568   bool CreateNew = false;
 569
 570   for (unsigned I = 0, E = CB->getNumOperandBundles(); I != E; ++I) {
 571     auto Bundle = CB->getOperandBundleAt(I);
 572     if (Bundle.getTagID() == ID) {
 573       CreateNew = true;
 574       continue;
 575     }
 576     Bundles.emplace_back(Bundle);
 577   }
 578
 579   return CreateNew ? Create(CB, Bundles, InsertPt) : CB;
 580 }
 581
 582 bool CallBase::hasReadingOperandBundles() const {
 583   // Implementation note: this is a conservative implementation of operand
 584   // bundle semantics, where *any* non-assume operand bundle (other than
 585   // ptrauth) forces a callsite to be at least readonly.
 586   return hasOperandBundlesOtherThan(
 587              {LLVMContext::OB_ptrauth, LLVMContext::OB_kcfi}) &&
 588          getIntrinsicID() != Intrinsic::assume;
 589 }
 590
 591 bool CallBase::hasClobberingOperandBundles() const {
 592   return hasOperandBundlesOtherThan(
 593              {LLVMContext::OB_deopt, LLVMContext::OB_funclet,
 594               LLVMContext::OB_ptrauth, LLVMContext::OB_kcfi}) &&
 595          getIntrinsicID() != Intrinsic::assume;
 596 }
 597
 598 MemoryEffects CallBase::getMemoryEffects() const {
 599   MemoryEffects ME = getAttributes().getMemoryEffects();
 600   if (auto *Fn = dyn_cast<Function>(getCalledOperand())) {
 601     MemoryEffects FnME = Fn->getMemoryEffects();
 602     if (hasOperandBundles()) {
 603       // TODO: Add a method to get memory effects for operand bundles instead.
 604       if (hasReadingOperandBundles())
 605         FnME |= MemoryEffects::readOnly();
 606       if (hasClobberingOperandBundles())
 607         FnME |= MemoryEffects::writeOnly();
 608     }
 609     ME &= FnME;
 610   }
 611   return ME;
 612 }
 613 void CallBase::setMemoryEffects(MemoryEffects ME) {
 614   addFnAttr(Attribute::getWithMemoryEffects(getContext(), ME));
 615 }
 616
 617 /// Determine if the function does not access memory.
 618 bool CallBase::doesNotAccessMemory() const {
 619   return getMemoryEffects().doesNotAccessMemory();
 620 }
 621 void CallBase::setDoesNotAccessMemory() {
 622   setMemoryEffects(MemoryEffects::none());
 623 }
 624
 625 /// Determine if the function does not access or only reads memory.
 626 bool CallBase::onlyReadsMemory() const {
 627   return getMemoryEffects().onlyReadsMemory();
 628 }
 629 void CallBase::setOnlyReadsMemory() {
 630   setMemoryEffects(getMemoryEffects() & MemoryEffects::readOnly());
 631 }
 632
 633 /// Determine if the function does not access or only writes memory.
 634 bool CallBase::onlyWritesMemory() const {
 635   return getMemoryEffects().onlyWritesMemory();
 636 }
 637 void CallBase::setOnlyWritesMemory() {
 638   setMemoryEffects(getMemoryEffects() & MemoryEffects::writeOnly());
 639 }
 640
 641 /// Determine if the call can access memmory only using pointers based
 642 /// on its arguments.
 643 bool CallBase::onlyAccessesArgMemory() const {
 644   return getMemoryEffects().onlyAccessesArgPointees();
 645 }
 646 void CallBase::setOnlyAccessesArgMemory() {
 647   setMemoryEffects(getMemoryEffects() & MemoryEffects::argMemOnly());
 648 }
 649
 650 /// Determine if the function may only access memory that is
 651 ///  inaccessible from the IR.
 652 bool CallBase::onlyAccessesInaccessibleMemory() const {
 653   return getMemoryEffects().onlyAccessesInaccessibleMem();
 654 }
 655 void CallBase::setOnlyAccessesInaccessibleMemory() {
 656   setMemoryEffects(getMemoryEffects() & MemoryEffects::inaccessibleMemOnly());
 657 }
 658
 659 /// Determine if the function may only access memory that is
 660 ///  either inaccessible from the IR or pointed to by its arguments.
 661 bool CallBase::onlyAccessesInaccessibleMemOrArgMem() const {
 662   return getMemoryEffects().onlyAccessesInaccessibleOrArgMem();
 663 }
 664 void CallBase::setOnlyAccessesInaccessibleMemOrArgMem() {
 665   setMemoryEffects(getMemoryEffects() &
 666                    MemoryEffects::inaccessibleOrArgMemOnly());
 667 }
 668
 669 //===----------------------------------------------------------------------===//
 670 //                        CallInst Implementation
 671 //===----------------------------------------------------------------------===//
 672
 673 void CallInst::init(FunctionType *FTy, Value *Func, ArrayRef<Value *> Args,
 674                     ArrayRef<OperandBundleDef> Bundles, const Twine &NameStr) {
 675   this->FTy = FTy;
 676   assert(getNumOperands() == Args.size() + CountBundleInputs(Bundles) + 1 &&
 677          "NumOperands not set up?");
 678
 679 #ifndef NDEBUG
 680   assert((Args.size() == FTy->getNumParams() ||
 681           (FTy->isVarArg() && Args.size() > FTy->getNumParams())) &&
 682          "Calling a function with bad signature!");
 683
 684   for (unsigned i = 0; i != Args.size(); ++i)
 685     assert((i >= FTy->getNumParams() ||
 686             FTy->getParamType(i) == Args[i]->getType()) &&
 687            "Calling a function with a bad signature!");
 688 #endif
 689
 690   // Set operands in order of their index to match use-list-order
 691   // prediction.
 692   llvm::copy(Args, op_begin());
 693   setCalledOperand(Func);
 694
 695   auto It = populateBundleOperandInfos(Bundles, Args.size());
 696   (void)It;
 697   assert(It + 1 == op_end() && "Should add up!");
 698
 699   setName(NameStr);
 700 }
 701
 702 void CallInst::init(FunctionType *FTy, Value *Func, const Twine &NameStr) {
 703   this->FTy = FTy;
 704   assert(getNumOperands() == 1 && "NumOperands not set up?");
 705   setCalledOperand(Func);
 706
 707   assert(FTy->getNumParams() == 0 && "Calling a function with bad signature");
 708
 709   setName(NameStr);
 710 }
 711
 712 CallInst::CallInst(FunctionType *Ty, Value *Func, const Twine &Name,
 713                    Instruction *InsertBefore)
 714     : CallBase(Ty->getReturnType(), Instruction::Call,
 715                OperandTraits<CallBase>::op_end(this) - 1, 1, InsertBefore) {
 716   init(Ty, Func, Name);
 717 }
 718
 719 CallInst::CallInst(FunctionType *Ty, Value *Func, const Twine &Name,
 720                    BasicBlock *InsertAtEnd)
 721     : CallBase(Ty->getReturnType(), Instruction::Call,
 722                OperandTraits<CallBase>::op_end(this) - 1, 1, InsertAtEnd) {
 723   init(Ty, Func, Name);
 724 }
 725
 726 CallInst::CallInst(const CallInst &CI)
 727     : CallBase(CI.Attrs, CI.FTy, CI.getType(), Instruction::Call,
 728                OperandTraits<CallBase>::op_end(this) - CI.getNumOperands(),
 729                CI.getNumOperands()) {
 730   setTailCallKind(CI.getTailCallKind());
 731   setCallingConv(CI.getCallingConv());
 732
 733   std::copy(CI.op_begin(), CI.op_end(), op_begin());
 734   std::copy(CI.bundle_op_info_begin(), CI.bundle_op_info_end(),
 735             bundle_op_info_begin());
 736   SubclassOptionalData = CI.SubclassOptionalData;
 737 }
 738
 739 CallInst *CallInst::Create(CallInst *CI, ArrayRef<OperandBundleDef> OpB,
 740                            Instruction *InsertPt) {
 741   std::vector<Value *> Args(CI->arg_begin(), CI->arg_end());
 742
 743   auto *NewCI = CallInst::Create(CI->getFunctionType(), CI->getCalledOperand(),
 744                                  Args, OpB, CI->getName(), InsertPt);
 745   NewCI->setTailCallKind(CI->getTailCallKind());
 746   NewCI->setCallingConv(CI->getCallingConv());
 747   NewCI->SubclassOptionalData = CI->SubclassOptionalData;
 748   NewCI->setAttributes(CI->getAttributes());
 749   NewCI->setDebugLoc(CI->getDebugLoc());
 750   return NewCI;
 751 }
 752
 753 // Update profile weight for call instruction by scaling it using the ratio
 754 // of S/T. The meaning of "branch_weights" meta data for call instruction is
 755 // transfered to represent call count.
 756 void CallInst::updateProfWeight(uint64_t S, uint64_t T) {
 757   auto *ProfileData = getMetadata(LLVMContext::MD_prof);
 758   if (ProfileData == nullptr)
 759     return;
 760
 761   auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
 762   if (!ProfDataName || (!ProfDataName->getString().equals("branch_weights") &&
 763                         !ProfDataName->getString().equals("VP")))
 764     return;
 765
 766   if (T == 0) {
 767     LLVM_DEBUG(dbgs() << "Attempting to update profile weights will result in "
 768                          "div by 0. Ignoring. Likely the function "
 769                       << getParent()->getParent()->getName()
 770                       << " has 0 entry count, and contains call instructions "
 771                          "with non-zero prof info.");
 772     return;
 773   }
 774
 775   MDBuilder MDB(getContext());
 776   SmallVector<Metadata *, 3> Vals;
 777   Vals.push_back(ProfileData->getOperand(0));
 778   APInt APS(128, S), APT(128, T);
 779   if (ProfDataName->getString().equals("branch_weights") &&
 780       ProfileData->getNumOperands() > 0) {
 781     // Using APInt::div may be expensive, but most cases should fit 64 bits.
 782     APInt Val(128, mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1))
 783                        ->getValue()
 784                        .getZExtValue());
 785     Val *= APS;
 786     Vals.push_back(MDB.createConstant(
 787         ConstantInt::get(Type::getInt32Ty(getContext()),
 788                          Val.udiv(APT).getLimitedValue(UINT32_MAX))));
 789   } else if (ProfDataName->getString().equals("VP"))
 790     for (unsigned i = 1; i < ProfileData->getNumOperands(); i += 2) {
 791       // The first value is the key of the value profile, which will not change.
 792       Vals.push_back(ProfileData->getOperand(i));
 793       uint64_t Count =
 794           mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(i + 1))
 795               ->getValue()
 796               .getZExtValue();
 797       // Don't scale the magic number.
 798       if (Count == NOMORE_ICP_MAGICNUM) {
 799         Vals.push_back(ProfileData->getOperand(i + 1));
 800         continue;
 801       }
 802       // Using APInt::div may be expensive, but most cases should fit 64 bits.
 803       APInt Val(128, Count);
 804       Val *= APS;
 805       Vals.push_back(MDB.createConstant(
 806           ConstantInt::get(Type::getInt64Ty(getContext()),
 807                            Val.udiv(APT).getLimitedValue())));
 808     }
 809   setMetadata(LLVMContext::MD_prof, MDNode::get(getContext(), Vals));
 810 }
 811
 812 //===----------------------------------------------------------------------===//
 813 //                        InvokeInst Implementation
 814 //===----------------------------------------------------------------------===//
 815
 816 void InvokeInst::init(FunctionType *FTy, Value *Fn, BasicBlock *IfNormal,
 817                       BasicBlock *IfException, ArrayRef<Value *> Args,
 818                       ArrayRef<OperandBundleDef> Bundles,
 819                       const Twine &NameStr) {
 820   this->FTy = FTy;
 821
 822   assert((int)getNumOperands() ==
 823              ComputeNumOperands(Args.size(), CountBundleInputs(Bundles)) &&
 824          "NumOperands not set up?");
 825
 826 #ifndef NDEBUG
 827   assert(((Args.size() == FTy->getNumParams()) ||
 828           (FTy->isVarArg() && Args.size() > FTy->getNumParams())) &&
 829          "Invoking a function with bad signature");
 830
 831   for (unsigned i = 0, e = Args.size(); i != e; i++)
 832     assert((i >= FTy->getNumParams() ||
 833             FTy->getParamType(i) == Args[i]->getType()) &&
 834            "Invoking a function with a bad signature!");
 835 #endif
 836
 837   // Set operands in order of their index to match use-list-order
 838   // prediction.
 839   llvm::copy(Args, op_begin());
 840   setNormalDest(IfNormal);
 841   setUnwindDest(IfException);
 842   setCalledOperand(Fn);
 843
 844   auto It = populateBundleOperandInfos(Bundles, Args.size());
 845   (void)It;
 846   assert(It + 3 == op_end() && "Should add up!");
 847
 848   setName(NameStr);
 849 }
 850
 851 InvokeInst::InvokeInst(const InvokeInst &II)
 852     : CallBase(II.Attrs, II.FTy, II.getType(), Instruction::Invoke,
 853                OperandTraits<CallBase>::op_end(this) - II.getNumOperands(),
 854                II.getNumOperands()) {
 855   setCallingConv(II.getCallingConv());
 856   std::copy(II.op_begin(), II.op_end(), op_begin());
 857   std::copy(II.bundle_op_info_begin(), II.bundle_op_info_end(),
 858             bundle_op_info_begin());
 859   SubclassOptionalData = II.SubclassOptionalData;
 860 }
 861
 862 InvokeInst *InvokeInst::Create(InvokeInst *II, ArrayRef<OperandBundleDef> OpB,
 863                                Instruction *InsertPt) {
 864   std::vector<Value *> Args(II->arg_begin(), II->arg_end());
 865
 866   auto *NewII = InvokeInst::Create(
 867       II->getFunctionType(), II->getCalledOperand(), II->getNormalDest(),
 868       II->getUnwindDest(), Args, OpB, II->getName(), InsertPt);
 869   NewII->setCallingConv(II->getCallingConv());
 870   NewII->SubclassOptionalData = II->SubclassOptionalData;
 871   NewII->setAttributes(II->getAttributes());
 872   NewII->setDebugLoc(II->getDebugLoc());
 873   return NewII;
 874 }
 875
 876 LandingPadInst *InvokeInst::getLandingPadInst() const {
 877   return cast<LandingPadInst>(getUnwindDest()->getFirstNonPHI());
 878 }
 879
 880 //===----------------------------------------------------------------------===//
 881 //                        CallBrInst Implementation
 882 //===----------------------------------------------------------------------===//
 883
 884 void CallBrInst::init(FunctionType *FTy, Value *Fn, BasicBlock *Fallthrough,
 885                       ArrayRef<BasicBlock *> IndirectDests,
 886                       ArrayRef<Value *> Args,
 887                       ArrayRef<OperandBundleDef> Bundles,
 888                       const Twine &NameStr) {
 889   this->FTy = FTy;
 890
 891   assert((int)getNumOperands() ==
 892              ComputeNumOperands(Args.size(), IndirectDests.size(),
 893                                 CountBundleInputs(Bundles)) &&
 894          "NumOperands not set up?");
 895
 896 #ifndef NDEBUG
 897   assert(((Args.size() == FTy->getNumParams()) ||
 898           (FTy->isVarArg() && Args.size() > FTy->getNumParams())) &&
 899          "Calling a function with bad signature");
 900
 901   for (unsigned i = 0, e = Args.size(); i != e; i++)
 902     assert((i >= FTy->getNumParams() ||
 903             FTy->getParamType(i) == Args[i]->getType()) &&
 904            "Calling a function with a bad signature!");
 905 #endif
 906
 907   // Set operands in order of their index to match use-list-order
 908   // prediction.
 909   std::copy(Args.begin(), Args.end(), op_begin());
 910   NumIndirectDests = IndirectDests.size();
 911   setDefaultDest(Fallthrough);
 912   for (unsigned i = 0; i != NumIndirectDests; ++i)
 913     setIndirectDest(i, IndirectDests[i]);
 914   setCalledOperand(Fn);
 915
 916   auto It = populateBundleOperandInfos(Bundles, Args.size());
 917   (void)It;
 918   assert(It + 2 + IndirectDests.size() == op_end() && "Should add up!");
 919
 920   setName(NameStr);
 921 }
 922
 923 CallBrInst::CallBrInst(const CallBrInst &CBI)
 924     : CallBase(CBI.Attrs, CBI.FTy, CBI.getType(), Instruction::CallBr,
 925                OperandTraits<CallBase>::op_end(this) - CBI.getNumOperands(),
 926                CBI.getNumOperands()) {
 927   setCallingConv(CBI.getCallingConv());
 928   std::copy(CBI.op_begin(), CBI.op_end(), op_begin());
 929   std::copy(CBI.bundle_op_info_begin(), CBI.bundle_op_info_end(),
 930             bundle_op_info_begin());
 931   SubclassOptionalData = CBI.SubclassOptionalData;
 932   NumIndirectDests = CBI.NumIndirectDests;
 933 }
 934
 935 CallBrInst *CallBrInst::Create(CallBrInst *CBI, ArrayRef<OperandBundleDef> OpB,
 936                                Instruction *InsertPt) {
 937   std::vector<Value *> Args(CBI->arg_begin(), CBI->arg_end());
 938
 939   auto *NewCBI = CallBrInst::Create(
 940       CBI->getFunctionType(), CBI->getCalledOperand(), CBI->getDefaultDest(),
 941       CBI->getIndirectDests(), Args, OpB, CBI->getName(), InsertPt);
 942   NewCBI->setCallingConv(CBI->getCallingConv());
 943   NewCBI->SubclassOptionalData = CBI->SubclassOptionalData;
 944   NewCBI->setAttributes(CBI->getAttributes());
 945   NewCBI->setDebugLoc(CBI->getDebugLoc());
 946   NewCBI->NumIndirectDests = CBI->NumIndirectDests;
 947   return NewCBI;
 948 }
 949
 950 //===----------------------------------------------------------------------===//
 951 //                        ReturnInst Implementation
 952 //===----------------------------------------------------------------------===//
 953
 954 ReturnInst::ReturnInst(const ReturnInst &RI)
 955     : Instruction(Type::getVoidTy(RI.getContext()), Instruction::Ret,
 956                   OperandTraits<ReturnInst>::op_end(this) - RI.getNumOperands(),
 957                   RI.getNumOperands()) {
 958   if (RI.getNumOperands())
 959     Op<0>() = RI.Op<0>();
 960   SubclassOptionalData = RI.SubclassOptionalData;
 961 }
 962
 963 ReturnInst::ReturnInst(LLVMContext &C, Value *retVal, Instruction *InsertBefore)
 964     : Instruction(Type::getVoidTy(C), Instruction::Ret,
 965                   OperandTraits<ReturnInst>::op_end(this) - !!retVal, !!retVal,
 966                   InsertBefore) {
 967   if (retVal)
 968     Op<0>() = retVal;
 969 }
 970
 971 ReturnInst::ReturnInst(LLVMContext &C, Value *retVal, BasicBlock *InsertAtEnd)
 972     : Instruction(Type::getVoidTy(C), Instruction::Ret,
 973                   OperandTraits<ReturnInst>::op_end(this) - !!retVal, !!retVal,
 974                   InsertAtEnd) {
 975   if (retVal)
 976     Op<0>() = retVal;
 977 }
 978
 979 ReturnInst::ReturnInst(LLVMContext &Context, BasicBlock *InsertAtEnd)
 980     : Instruction(Type::getVoidTy(Context), Instruction::Ret,
 981                   OperandTraits<ReturnInst>::op_end(this), 0, InsertAtEnd) {}
 982
 983 //===----------------------------------------------------------------------===//
 984 //                        ResumeInst Implementation
 985 //===----------------------------------------------------------------------===//
 986
 987 ResumeInst::ResumeInst(const ResumeInst &RI)
 988     : Instruction(Type::getVoidTy(RI.getContext()), Instruction::Resume,
 989                   OperandTraits<ResumeInst>::op_begin(this), 1) {
 990   Op<0>() = RI.Op<0>();
 991 }
 992
 993 ResumeInst::ResumeInst(Value *Exn, Instruction *InsertBefore)
 994     : Instruction(Type::getVoidTy(Exn->getContext()), Instruction::Resume,
 995                   OperandTraits<ResumeInst>::op_begin(this), 1, InsertBefore) {
 996   Op<0>() = Exn;
 997 }
 998
 999 ResumeInst::ResumeInst(Value *Exn, BasicBlock *InsertAtEnd)
1000     : Instruction(Type::getVoidTy(Exn->getContext()), Instruction::Resume,
1001                   OperandTraits<ResumeInst>::op_begin(this), 1, InsertAtEnd) {
1002   Op<0>() = Exn;
1003 }
1004
1005 //===----------------------------------------------------------------------===//
1006 //                        CleanupReturnInst Implementation
1007 //===----------------------------------------------------------------------===//
1008
1009 CleanupReturnInst::CleanupReturnInst(const CleanupReturnInst &CRI)
1010     : Instruction(CRI.getType(), Instruction::CleanupRet,
1011                   OperandTraits<CleanupReturnInst>::op_end(this) -
1012                       CRI.getNumOperands(),
1013                   CRI.getNumOperands()) {
1014   setSubclassData<Instruction::OpaqueField>(
1015       CRI.getSubclassData<Instruction::OpaqueField>());
1016   Op<0>() = CRI.Op<0>();
1017   if (CRI.hasUnwindDest())
1018     Op<1>() = CRI.Op<1>();
1019 }
1020
1021 void CleanupReturnInst::init(Value *CleanupPad, BasicBlock *UnwindBB) {
1022   if (UnwindBB)
1023     setSubclassData<UnwindDestField>(true);
1024
1025   Op<0>() = CleanupPad;
1026   if (UnwindBB)
1027     Op<1>() = UnwindBB;
1028 }
1029
1030 CleanupReturnInst::CleanupReturnInst(Value *CleanupPad, BasicBlock *UnwindBB,
1031                                      unsigned Values, Instruction *InsertBefore)
1032     : Instruction(Type::getVoidTy(CleanupPad->getContext()),
1033                   Instruction::CleanupRet,
1034                   OperandTraits<CleanupReturnInst>::op_end(this) - Values,
1035                   Values, InsertBefore) {
1036   init(CleanupPad, UnwindBB);
1037 }
1038
1039 CleanupReturnInst::CleanupReturnInst(Value *CleanupPad, BasicBlock *UnwindBB,
1040                                      unsigned Values, BasicBlock *InsertAtEnd)
1041     : Instruction(Type::getVoidTy(CleanupPad->getContext()),
1042                   Instruction::CleanupRet,
1043                   OperandTraits<CleanupReturnInst>::op_end(this) - Values,
1044                   Values, InsertAtEnd) {
1045   init(CleanupPad, UnwindBB);
1046 }
1047
1048 //===----------------------------------------------------------------------===//
1049 //                        CatchReturnInst Implementation
1050 //===----------------------------------------------------------------------===//
1051 void CatchReturnInst::init(Value *CatchPad, BasicBlock *BB) {
1052   Op<0>() = CatchPad;
1053   Op<1>() = BB;
1054 }
1055
1056 CatchReturnInst::CatchReturnInst(const CatchReturnInst &CRI)
1057     : Instruction(Type::getVoidTy(CRI.getContext()), Instruction::CatchRet,
1058                   OperandTraits<CatchReturnInst>::op_begin(this), 2) {
1059   Op<0>() = CRI.Op<0>();
1060   Op<1>() = CRI.Op<1>();
1061 }
1062
1063 CatchReturnInst::CatchReturnInst(Value *CatchPad, BasicBlock *BB,
1064                                  Instruction *InsertBefore)
1065     : Instruction(Type::getVoidTy(BB->getContext()), Instruction::CatchRet,
1066                   OperandTraits<CatchReturnInst>::op_begin(this), 2,
1067                   InsertBefore) {
1068   init(CatchPad, BB);
1069 }
1070
1071 CatchReturnInst::CatchReturnInst(Value *CatchPad, BasicBlock *BB,
1072                                  BasicBlock *InsertAtEnd)
1073     : Instruction(Type::getVoidTy(BB->getContext()), Instruction::CatchRet,
1074                   OperandTraits<CatchReturnInst>::op_begin(this), 2,
1075                   InsertAtEnd) {
1076   init(CatchPad, BB);
1077 }
1078
1079 //===----------------------------------------------------------------------===//
1080 //                       CatchSwitchInst Implementation
1081 //===----------------------------------------------------------------------===//
1082
1083 CatchSwitchInst::CatchSwitchInst(Value *ParentPad, BasicBlock *UnwindDest,
1084                                  unsigned NumReservedValues,
1085                                  const Twine &NameStr,
1086                                  Instruction *InsertBefore)
1087     : Instruction(ParentPad->getType(), Instruction::CatchSwitch, nullptr, 0,
1088                   InsertBefore) {
1089   if (UnwindDest)
1090     ++NumReservedValues;
1091   init(ParentPad, UnwindDest, NumReservedValues + 1);
1092   setName(NameStr);
1093 }
1094
1095 CatchSwitchInst::CatchSwitchInst(Value *ParentPad, BasicBlock *UnwindDest,
1096                                  unsigned NumReservedValues,
1097                                  const Twine &NameStr, BasicBlock *InsertAtEnd)
1098     : Instruction(ParentPad->getType(), Instruction::CatchSwitch, nullptr, 0,
1099                   InsertAtEnd) {
1100   if (UnwindDest)
1101     ++NumReservedValues;
1102   init(ParentPad, UnwindDest, NumReservedValues + 1);
1103   setName(NameStr);
1104 }
1105
1106 CatchSwitchInst::CatchSwitchInst(const CatchSwitchInst &CSI)
1107     : Instruction(CSI.getType(), Instruction::CatchSwitch, nullptr,
1108                   CSI.getNumOperands()) {
1109   init(CSI.getParentPad(), CSI.getUnwindDest(), CSI.getNumOperands());
1110   setNumHungOffUseOperands(ReservedSpace);
1111   Use *OL = getOperandList();
1112   const Use *InOL = CSI.getOperandList();
1113   for (unsigned I = 1, E = ReservedSpace; I != E; ++I)
1114     OL[I] = InOL[I];
1115 }
1116
1117 void CatchSwitchInst::init(Value *ParentPad, BasicBlock *UnwindDest,
1118                            unsigned NumReservedValues) {
1119   assert(ParentPad && NumReservedValues);
1120
1121   ReservedSpace = NumReservedValues;
1122   setNumHungOffUseOperands(UnwindDest ? 2 : 1);
1123   allocHungoffUses(ReservedSpace);
1124
1125   Op<0>() = ParentPad;
1126   if (UnwindDest) {
1127     setSubclassData<UnwindDestField>(true);
1128     setUnwindDest(UnwindDest);
1129   }
1130 }
1131
1132 /// growOperands - grow operands - This grows the operand list in response to a
1133 /// push_back style of operation. This grows the number of ops by 2 times.
1134 void CatchSwitchInst::growOperands(unsigned Size) {
1135   unsigned NumOperands = getNumOperands();
1136   assert(NumOperands >= 1);
1137   if (ReservedSpace >= NumOperands + Size)
1138     return;
1139   ReservedSpace = (NumOperands + Size / 2) * 2;
1140   growHungoffUses(ReservedSpace);
1141 }
1142
1143 void CatchSwitchInst::addHandler(BasicBlock *Handler) {
1144   unsigned OpNo = getNumOperands();
1145   growOperands(1);
1146   assert(OpNo < ReservedSpace && "Growing didn't work!");
1147   setNumHungOffUseOperands(getNumOperands() + 1);
1148   getOperandList()[OpNo] = Handler;
1149 }
1150
1151 void CatchSwitchInst::removeHandler(handler_iterator HI) {
1152   // Move all subsequent handlers up one.
1153   Use *EndDst = op_end() - 1;
1154   for (Use *CurDst = HI.getCurrent(); CurDst != EndDst; ++CurDst)
1155     *CurDst = *(CurDst + 1);
1156   // Null out the last handler use.
1157   *EndDst = nullptr;
1158
1159   setNumHungOffUseOperands(getNumOperands() - 1);
1160 }
1161
1162 //===----------------------------------------------------------------------===//
1163 //                        FuncletPadInst Implementation
1164 //===----------------------------------------------------------------------===//
1165 void FuncletPadInst::init(Value *ParentPad, ArrayRef<Value *> Args,
1166                           const Twine &NameStr) {
1167   assert(getNumOperands() == 1 + Args.size() && "NumOperands not set up?");
1168   llvm::copy(Args, op_begin());
1169   setParentPad(ParentPad);
1170   setName(NameStr);
1171 }
1172
1173 FuncletPadInst::FuncletPadInst(const FuncletPadInst &FPI)
1174     : Instruction(FPI.getType(), FPI.getOpcode(),
1175                   OperandTraits<FuncletPadInst>::op_end(this) -
1176                       FPI.getNumOperands(),
1177                   FPI.getNumOperands()) {
1178   std::copy(FPI.op_begin(), FPI.op_end(), op_begin());
1179   setParentPad(FPI.getParentPad());
1180 }
1181
1182 FuncletPadInst::FuncletPadInst(Instruction::FuncletPadOps Op, Value *ParentPad,
1183                                ArrayRef<Value *> Args, unsigned Values,
1184                                const Twine &NameStr, Instruction *InsertBefore)
1185     : Instruction(ParentPad->getType(), Op,
1186                   OperandTraits<FuncletPadInst>::op_end(this) - Values, Values,
1187                   InsertBefore) {
1188   init(ParentPad, Args, NameStr);
1189 }
1190
1191 FuncletPadInst::FuncletPadInst(Instruction::FuncletPadOps Op, Value *ParentPad,
1192                                ArrayRef<Value *> Args, unsigned Values,
1193                                const Twine &NameStr, BasicBlock *InsertAtEnd)
1194     : Instruction(ParentPad->getType(), Op,
1195                   OperandTraits<FuncletPadInst>::op_end(this) - Values, Values,
1196                   InsertAtEnd) {
1197   init(ParentPad, Args, NameStr);
1198 }
1199
1200 //===----------------------------------------------------------------------===//
1201 //                      UnreachableInst Implementation
1202 //===----------------------------------------------------------------------===//
1203
1204 UnreachableInst::UnreachableInst(LLVMContext &Context,
1205                                  Instruction *InsertBefore)
1206     : Instruction(Type::getVoidTy(Context), Instruction::Unreachable, nullptr,
1207                   0, InsertBefore) {}
1208 UnreachableInst::UnreachableInst(LLVMContext &Context, BasicBlock *InsertAtEnd)
1209     : Instruction(Type::getVoidTy(Context), Instruction::Unreachable, nullptr,
1210                   0, InsertAtEnd) {}
1211
1212 //===----------------------------------------------------------------------===//
1213 //                        BranchInst Implementation
1214 //===----------------------------------------------------------------------===//
1215
1216 void BranchInst::AssertOK() {
1217   if (isConditional())
1218     assert(getCondition()->getType()->isIntegerTy(1) &&
1219            "May only branch on boolean predicates!");
1220 }
1221
1222 BranchInst::BranchInst(BasicBlock *IfTrue, Instruction *InsertBefore)
1223     : Instruction(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
1224                   OperandTraits<BranchInst>::op_end(this) - 1, 1,
1225                   InsertBefore) {
1226   assert(IfTrue && "Branch destination may not be null!");
1227   Op<-1>() = IfTrue;
1228 }
1229
1230 BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
1231                        Instruction *InsertBefore)
1232     : Instruction(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
1233                   OperandTraits<BranchInst>::op_end(this) - 3, 3,
1234                   InsertBefore) {
1235   // Assign in order of operand index to make use-list order predictable.
1236   Op<-3>() = Cond;
1237   Op<-2>() = IfFalse;
1238   Op<-1>() = IfTrue;
1239 #ifndef NDEBUG
1240   AssertOK();
1241 #endif
1242 }
1243
1244 BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *InsertAtEnd)
1245     : Instruction(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
1246                   OperandTraits<BranchInst>::op_end(this) - 1, 1, InsertAtEnd) {
1247   assert(IfTrue && "Branch destination may not be null!");
1248   Op<-1>() = IfTrue;
1249 }
1250
1251 BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
1252                        BasicBlock *InsertAtEnd)
1253     : Instruction(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
1254                   OperandTraits<BranchInst>::op_end(this) - 3, 3, InsertAtEnd) {
1255   // Assign in order of operand index to make use-list order predictable.
1256   Op<-3>() = Cond;
1257   Op<-2>() = IfFalse;
1258   Op<-1>() = IfTrue;
1259 #ifndef NDEBUG
1260   AssertOK();
1261 #endif
1262 }
1263
1264 BranchInst::BranchInst(const BranchInst &BI)
1265     : Instruction(Type::getVoidTy(BI.getContext()), Instruction::Br,
1266                   OperandTraits<BranchInst>::op_end(this) - BI.getNumOperands(),
1267                   BI.getNumOperands()) {
1268   // Assign in order of operand index to make use-list order predictable.
1269   if (BI.getNumOperands() != 1) {
1270     assert(BI.getNumOperands() == 3 && "BR can have 1 or 3 operands!");
1271     Op<-3>() = BI.Op<-3>();
1272     Op<-2>() = BI.Op<-2>();
1273   }
1274   Op<-1>() = BI.Op<-1>();
1275   SubclassOptionalData = BI.SubclassOptionalData;
1276 }
1277
1278 void BranchInst::swapSuccessors() {
1279   assert(isConditional() &&
1280          "Cannot swap successors of an unconditional branch");
1281   Op<-1>().swap(Op<-2>());
1282
1283   // Update profile metadata if present and it matches our structural
1284   // expectations.
1285   swapProfMetadata();
1286 }
1287
1288 //===----------------------------------------------------------------------===//
1289 //                        AllocaInst Implementation
1290 //===----------------------------------------------------------------------===//
1291
1292 static Value *getAISize(LLVMContext &Context, Value *Amt) {
1293   if (!Amt)
1294     Amt = ConstantInt::get(Type::getInt32Ty(Context), 1);
1295   else {
1296     assert(!isa<BasicBlock>(Amt) &&
1297            "Passed basic block into allocation size parameter! Use other ctor");
1298     assert(Amt->getType()->isIntegerTy() &&
1299            "Allocation array size is not an integer!");
1300   }
1301   return Amt;
1302 }
1303
1304 static Align computeAllocaDefaultAlign(Type *Ty, BasicBlock *BB) {
1305   assert(BB && "Insertion BB cannot be null when alignment not provided!");
1306   assert(BB->getParent() &&
1307          "BB must be in a Function when alignment not provided!");
1308   const DataLayout &DL = BB->getModule()->getDataLayout();
1309   return DL.getPrefTypeAlign(Ty);
1310 }
1311
1312 static Align computeAllocaDefaultAlign(Type *Ty, Instruction *I) {
1313   assert(I && "Insertion position cannot be null when alignment not provided!");
1314   return computeAllocaDefaultAlign(Ty, I->getParent());
1315 }
1316
1317 AllocaInst::AllocaInst(Type *Ty, unsigned AddrSpace, const Twine &Name,
1318                        Instruction *InsertBefore)
1319   : AllocaInst(Ty, AddrSpace, /*ArraySize=*/nullptr, Name, InsertBefore) {}
1320
1321 AllocaInst::AllocaInst(Type *Ty, unsigned AddrSpace, const Twine &Name,
1322                        BasicBlock *InsertAtEnd)
1323   : AllocaInst(Ty, AddrSpace, /*ArraySize=*/nullptr, Name, InsertAtEnd) {}
1324
1325 AllocaInst::AllocaInst(Type *Ty, unsigned AddrSpace, Value *ArraySize,
1326                        const Twine &Name, Instruction *InsertBefore)
1327     : AllocaInst(Ty, AddrSpace, ArraySize,
1328                  computeAllocaDefaultAlign(Ty, InsertBefore), Name,
1329                  InsertBefore) {}
1330
1331 AllocaInst::AllocaInst(Type *Ty, unsigned AddrSpace, Value *ArraySize,
1332                        const Twine &Name, BasicBlock *InsertAtEnd)
1333     : AllocaInst(Ty, AddrSpace, ArraySize,
1334                  computeAllocaDefaultAlign(Ty, InsertAtEnd), Name,
1335                  InsertAtEnd) {}
1336
1337 AllocaInst::AllocaInst(Type *Ty, unsigned AddrSpace, Value *ArraySize,
1338                        Align Align, const Twine &Name,
1339                        Instruction *InsertBefore)
1340     : UnaryInstruction(PointerType::get(Ty, AddrSpace), Alloca,
1341                        getAISize(Ty->getContext(), ArraySize), InsertBefore),
1342       AllocatedType(Ty) {
1343   setAlignment(Align);
1344   assert(!Ty->isVoidTy() && "Cannot allocate void!");
1345   setName(Name);
1346 }
1347
1348 AllocaInst::AllocaInst(Type *Ty, unsigned AddrSpace, Value *ArraySize,
1349                        Align Align, const Twine &Name, BasicBlock *InsertAtEnd)
1350     : UnaryInstruction(PointerType::get(Ty, AddrSpace), Alloca,
1351                        getAISize(Ty->getContext(), ArraySize), InsertAtEnd),
1352       AllocatedType(Ty) {
1353   setAlignment(Align);
1354   assert(!Ty->isVoidTy() && "Cannot allocate void!");
1355   setName(Name);
1356 }
1357
1358
1359 bool AllocaInst::isArrayAllocation() const {
1360   if (ConstantInt *CI = dyn_cast<ConstantInt>(getOperand(0)))
1361     return !CI->isOne();
1362   return true;
1363 }
1364
1365 /// isStaticAlloca - Return true if this alloca is in the entry block of the
1366 /// function and is a constant size.  If so, the code generator will fold it
1367 /// into the prolog/epilog code, so it is basically free.
1368 bool AllocaInst::isStaticAlloca() const {
1369   // Must be constant size.
1370   if (!isa<ConstantInt>(getArraySize())) return false;
1371
1372   // Must be in the entry block.
1373   const BasicBlock *Parent = getParent();
1374   return Parent->isEntryBlock() && !isUsedWithInAlloca();
1375 }
1376
1377 //===----------------------------------------------------------------------===//
1378 //                           LoadInst Implementation
1379 //===----------------------------------------------------------------------===//
1380
1381 void LoadInst::AssertOK() {
1382   assert(getOperand(0)->getType()->isPointerTy() &&
1383          "Ptr must have pointer type.");
1384 }
1385
1386 static Align computeLoadStoreDefaultAlign(Type *Ty, BasicBlock *BB) {
1387   assert(BB && "Insertion BB cannot be null when alignment not provided!");
1388   assert(BB->getParent() &&
1389          "BB must be in a Function when alignment not provided!");
1390   const DataLayout &DL = BB->getModule()->getDataLayout();
1391   return DL.getABITypeAlign(Ty);
1392 }
1393
1394 static Align computeLoadStoreDefaultAlign(Type *Ty, Instruction *I) {
1395   assert(I && "Insertion position cannot be null when alignment not provided!");
1396   return computeLoadStoreDefaultAlign(Ty, I->getParent());
1397 }
1398
1399 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name,
1400                    Instruction *InsertBef)
1401     : LoadInst(Ty, Ptr, Name, /*isVolatile=*/false, InsertBef) {}
1402
1403 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name,
1404                    BasicBlock *InsertAE)
1405     : LoadInst(Ty, Ptr, Name, /*isVolatile=*/false, InsertAE) {}
1406
1407 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
1408                    Instruction *InsertBef)
1409     : LoadInst(Ty, Ptr, Name, isVolatile,
1410                computeLoadStoreDefaultAlign(Ty, InsertBef), InsertBef) {}
1411
1412 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
1413                    BasicBlock *InsertAE)
1414     : LoadInst(Ty, Ptr, Name, isVolatile,
1415                computeLoadStoreDefaultAlign(Ty, InsertAE), InsertAE) {}
1416
1417 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
1418                    Align Align, Instruction *InsertBef)
1419     : LoadInst(Ty, Ptr, Name, isVolatile, Align, AtomicOrdering::NotAtomic,
1420                SyncScope::System, InsertBef) {}
1421
1422 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
1423                    Align Align, BasicBlock *InsertAE)
1424     : LoadInst(Ty, Ptr, Name, isVolatile, Align, AtomicOrdering::NotAtomic,
1425                SyncScope::System, InsertAE) {}
1426
1427 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
1428                    Align Align, AtomicOrdering Order, SyncScope::ID SSID,
1429                    Instruction *InsertBef)
1430     : UnaryInstruction(Ty, Load, Ptr, InsertBef) {
1431   setVolatile(isVolatile);
1432   setAlignment(Align);
1433   setAtomic(Order, SSID);
1434   AssertOK();
1435   setName(Name);
1436 }
1437
1438 LoadInst::LoadInst(Type *Ty, Value *Ptr, const Twine &Name, bool isVolatile,
1439                    Align Align, AtomicOrdering Order, SyncScope::ID SSID,
1440                    BasicBlock *InsertAE)
1441     : UnaryInstruction(Ty, Load, Ptr, InsertAE) {
1442   setVolatile(isVolatile);
1443   setAlignment(Align);
1444   setAtomic(Order, SSID);
1445   AssertOK();
1446   setName(Name);
1447 }
1448
1449 //===----------------------------------------------------------------------===//
1450 //                           StoreInst Implementation
1451 //===----------------------------------------------------------------------===//
1452
1453 void StoreInst::AssertOK() {
1454   assert(getOperand(0) && getOperand(1) && "Both operands must be non-null!");
1455   assert(getOperand(1)->getType()->isPointerTy() &&
1456          "Ptr must have pointer type!");
1457 }
1458
1459 StoreInst::StoreInst(Value *val, Value *addr, Instruction *InsertBefore)
1460     : StoreInst(val, addr, /*isVolatile=*/false, InsertBefore) {}
1461
1462 StoreInst::StoreInst(Value *val, Value *addr, BasicBlock *InsertAtEnd)
1463     : StoreInst(val, addr, /*isVolatile=*/false, InsertAtEnd) {}
1464
1465 StoreInst::StoreInst(Value *val, Value *addr, BasicBlock::iterator InsertBefore)
1466     : StoreInst(val, addr, /*isVolatile=*/false, InsertBefore) {}
1467
1468 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
1469                      Instruction *InsertBefore)
1470     : StoreInst(val, addr, isVolatile,
1471                 computeLoadStoreDefaultAlign(val->getType(), InsertBefore),
1472                 InsertBefore) {}
1473
1474 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
1475                      BasicBlock *InsertAtEnd)
1476     : StoreInst(val, addr, isVolatile,
1477                 computeLoadStoreDefaultAlign(val->getType(), InsertAtEnd),
1478                 InsertAtEnd) {}
1479
1480 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
1481                      BasicBlock::iterator InsertBefore)
1482     : StoreInst(val, addr, isVolatile,
1483                 computeLoadStoreDefaultAlign(val->getType(), &*InsertBefore),
1484                 InsertBefore) {}
1485
1486 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
1487                      Instruction *InsertBefore)
1488     : StoreInst(val, addr, isVolatile, Align, AtomicOrdering::NotAtomic,
1489                 SyncScope::System, InsertBefore) {}
1490
1491 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
1492                      BasicBlock *InsertAtEnd)
1493     : StoreInst(val, addr, isVolatile, Align, AtomicOrdering::NotAtomic,
1494                 SyncScope::System, InsertAtEnd) {}
1495
1496 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
1497                      BasicBlock::iterator InsertBefore)
1498     : StoreInst(val, addr, isVolatile, Align, AtomicOrdering::NotAtomic,
1499                 SyncScope::System, InsertBefore) {}
1500
1501 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
1502                      AtomicOrdering Order, SyncScope::ID SSID,
1503                      Instruction *InsertBefore)
1504     : Instruction(Type::getVoidTy(val->getContext()), Store,
1505                   OperandTraits<StoreInst>::op_begin(this),
1506                   OperandTraits<StoreInst>::operands(this), InsertBefore) {
1507   Op<0>() = val;
1508   Op<1>() = addr;
1509   setVolatile(isVolatile);
1510   setAlignment(Align);
1511   setAtomic(Order, SSID);
1512   AssertOK();
1513 }
1514
1515 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
1516                      AtomicOrdering Order, SyncScope::ID SSID,
1517                      BasicBlock *InsertAtEnd)
1518     : Instruction(Type::getVoidTy(val->getContext()), Store,
1519                   OperandTraits<StoreInst>::op_begin(this),
1520                   OperandTraits<StoreInst>::operands(this), InsertAtEnd) {
1521   Op<0>() = val;
1522   Op<1>() = addr;
1523   setVolatile(isVolatile);
1524   setAlignment(Align);
1525   setAtomic(Order, SSID);
1526   AssertOK();
1527 }
1528
1529 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile, Align Align,
1530                      AtomicOrdering Order, SyncScope::ID SSID,
1531                      BasicBlock::iterator InsertBefore)
1532     : Instruction(Type::getVoidTy(val->getContext()), Store,
1533                   OperandTraits<StoreInst>::op_begin(this),
1534                   OperandTraits<StoreInst>::operands(this)) {
1535   Op<0>() = val;
1536   Op<1>() = addr;
1537   setVolatile(isVolatile);
1538   setAlignment(Align);
1539   setAtomic(Order, SSID);
1540   insertBefore(*InsertBefore->getParent(), InsertBefore);
1541   AssertOK();
1542 }
1543
1544 //===----------------------------------------------------------------------===//
1545 //                       AtomicCmpXchgInst Implementation
1546 //===----------------------------------------------------------------------===//
1547
1548 void AtomicCmpXchgInst::Init(Value *Ptr, Value *Cmp, Value *NewVal,
1549                              Align Alignment, AtomicOrdering SuccessOrdering,
1550                              AtomicOrdering FailureOrdering,
1551                              SyncScope::ID SSID) {
1552   Op<0>() = Ptr;
1553   Op<1>() = Cmp;
1554   Op<2>() = NewVal;
1555   setSuccessOrdering(SuccessOrdering);
1556   setFailureOrdering(FailureOrdering);
1557   setSyncScopeID(SSID);
1558   setAlignment(Alignment);
1559
1560   assert(getOperand(0) && getOperand(1) && getOperand(2) &&
1561          "All operands must be non-null!");
1562   assert(getOperand(0)->getType()->isPointerTy() &&
1563          "Ptr must have pointer type!");
1564   assert(getOperand(1)->getType() == getOperand(2)->getType() &&
1565          "Cmp type and NewVal type must be same!");
1566 }
1567
1568 AtomicCmpXchgInst::AtomicCmpXchgInst(Value *Ptr, Value *Cmp, Value *NewVal,
1569                                      Align Alignment,
1570                                      AtomicOrdering SuccessOrdering,
1571                                      AtomicOrdering FailureOrdering,
1572                                      SyncScope::ID SSID,
1573                                      Instruction *InsertBefore)
1574     : Instruction(
1575           StructType::get(Cmp->getType(), Type::getInt1Ty(Cmp->getContext())),
1576           AtomicCmpXchg, OperandTraits<AtomicCmpXchgInst>::op_begin(this),
1577           OperandTraits<AtomicCmpXchgInst>::operands(this), InsertBefore) {
1578   Init(Ptr, Cmp, NewVal, Alignment, SuccessOrdering, FailureOrdering, SSID);
1579 }
1580
1581 AtomicCmpXchgInst::AtomicCmpXchgInst(Value *Ptr, Value *Cmp, Value *NewVal,
1582                                      Align Alignment,
1583                                      AtomicOrdering SuccessOrdering,
1584                                      AtomicOrdering FailureOrdering,
1585                                      SyncScope::ID SSID,
1586                                      BasicBlock *InsertAtEnd)
1587     : Instruction(
1588           StructType::get(Cmp->getType(), Type::getInt1Ty(Cmp->getContext())),
1589           AtomicCmpXchg, OperandTraits<AtomicCmpXchgInst>::op_begin(this),
1590           OperandTraits<AtomicCmpXchgInst>::operands(this), InsertAtEnd) {
1591   Init(Ptr, Cmp, NewVal, Alignment, SuccessOrdering, FailureOrdering, SSID);
1592 }
1593
1594 //===----------------------------------------------------------------------===//
1595 //                       AtomicRMWInst Implementation
1596 //===----------------------------------------------------------------------===//
1597
1598 void AtomicRMWInst::Init(BinOp Operation, Value *Ptr, Value *Val,
1599                          Align Alignment, AtomicOrdering Ordering,
1600                          SyncScope::ID SSID) {
1601   assert(Ordering != AtomicOrdering::NotAtomic &&
1602          "atomicrmw instructions can only be atomic.");
1603   assert(Ordering != AtomicOrdering::Unordered &&
1604          "atomicrmw instructions cannot be unordered.");
1605   Op<0>() = Ptr;
1606   Op<1>() = Val;
1607   setOperation(Operation);
1608   setOrdering(Ordering);
1609   setSyncScopeID(SSID);
1610   setAlignment(Alignment);
1611
1612   assert(getOperand(0) && getOperand(1) &&
1613          "All operands must be non-null!");
1614   assert(getOperand(0)->getType()->isPointerTy() &&
1615          "Ptr must have pointer type!");
1616   assert(Ordering != AtomicOrdering::NotAtomic &&
1617          "AtomicRMW instructions must be atomic!");
1618 }
1619
1620 AtomicRMWInst::AtomicRMWInst(BinOp Operation, Value *Ptr, Value *Val,
1621                              Align Alignment, AtomicOrdering Ordering,
1622                              SyncScope::ID SSID, Instruction *InsertBefore)
1623     : Instruction(Val->getType(), AtomicRMW,
1624                   OperandTraits<AtomicRMWInst>::op_begin(this),
1625                   OperandTraits<AtomicRMWInst>::operands(this), InsertBefore) {
1626   Init(Operation, Ptr, Val, Alignment, Ordering, SSID);
1627 }
1628
1629 AtomicRMWInst::AtomicRMWInst(BinOp Operation, Value *Ptr, Value *Val,
1630                              Align Alignment, AtomicOrdering Ordering,
1631                              SyncScope::ID SSID, BasicBlock *InsertAtEnd)
1632     : Instruction(Val->getType(), AtomicRMW,
1633                   OperandTraits<AtomicRMWInst>::op_begin(this),
1634                   OperandTraits<AtomicRMWInst>::operands(this), InsertAtEnd) {
1635   Init(Operation, Ptr, Val, Alignment, Ordering, SSID);
1636 }
1637
1638 StringRef AtomicRMWInst::getOperationName(BinOp Op) {
1639   switch (Op) {
1640   case AtomicRMWInst::Xchg:
1641     return "xchg";
1642   case AtomicRMWInst::Add:
1643     return "add";
1644   case AtomicRMWInst::Sub:
1645     return "sub";
1646   case AtomicRMWInst::And:
1647     return "and";
1648   case AtomicRMWInst::Nand:
1649     return "nand";
1650   case AtomicRMWInst::Or:
1651     return "or";
1652   case AtomicRMWInst::Xor:
1653     return "xor";
1654   case AtomicRMWInst::Max:
1655     return "max";
1656   case AtomicRMWInst::Min:
1657     return "min";
1658   case AtomicRMWInst::UMax:
1659     return "umax";
1660   case AtomicRMWInst::UMin:
1661     return "umin";
1662   case AtomicRMWInst::FAdd:
1663     return "fadd";
1664   case AtomicRMWInst::FSub:
1665     return "fsub";
1666   case AtomicRMWInst::FMax:
1667     return "fmax";
1668   case AtomicRMWInst::FMin:
1669     return "fmin";
1670   case AtomicRMWInst::UIncWrap:
1671     return "uinc_wrap";
1672   case AtomicRMWInst::UDecWrap:
1673     return "udec_wrap";
1674   case AtomicRMWInst::BAD_BINOP:
1675     return "<invalid operation>";
1676   }
1677
1678   llvm_unreachable("invalid atomicrmw operation");
1679 }
1680
1681 //===----------------------------------------------------------------------===//
1682 //                       FenceInst Implementation
1683 //===----------------------------------------------------------------------===//
1684
1685 FenceInst::FenceInst(LLVMContext &C, AtomicOrdering Ordering,
1686                      SyncScope::ID SSID,
1687                      Instruction *InsertBefore)
1688   : Instruction(Type::getVoidTy(C), Fence, nullptr, 0, InsertBefore) {
1689   setOrdering(Ordering);
1690   setSyncScopeID(SSID);
1691 }
1692
1693 FenceInst::FenceInst(LLVMContext &C, AtomicOrdering Ordering,
1694                      SyncScope::ID SSID,
1695                      BasicBlock *InsertAtEnd)
1696   : Instruction(Type::getVoidTy(C), Fence, nullptr, 0, InsertAtEnd) {
1697   setOrdering(Ordering);
1698   setSyncScopeID(SSID);
1699 }
1700
1701 //===----------------------------------------------------------------------===//
1702 //                       GetElementPtrInst Implementation
1703 //===----------------------------------------------------------------------===//
1704
1705 void GetElementPtrInst::init(Value *Ptr, ArrayRef<Value *> IdxList,
1706                              const Twine &Name) {
1707   assert(getNumOperands() == 1 + IdxList.size() &&
1708          "NumOperands not initialized?");
1709   Op<0>() = Ptr;
1710   llvm::copy(IdxList, op_begin() + 1);
1711   setName(Name);
1712 }
1713
1714 GetElementPtrInst::GetElementPtrInst(const GetElementPtrInst &GEPI)
1715     : Instruction(GEPI.getType(), GetElementPtr,
1716                   OperandTraits<GetElementPtrInst>::op_end(this) -
1717                       GEPI.getNumOperands(),
1718                   GEPI.getNumOperands()),
1719       SourceElementType(GEPI.SourceElementType),
1720       ResultElementType(GEPI.ResultElementType) {
1721   std::copy(GEPI.op_begin(), GEPI.op_end(), op_begin());
1722   SubclassOptionalData = GEPI.SubclassOptionalData;
1723 }
1724
1725 Type *GetElementPtrInst::getTypeAtIndex(Type *Ty, Value *Idx) {
1726   if (auto *Struct = dyn_cast<StructType>(Ty)) {
1727     if (!Struct->indexValid(Idx))
1728       return nullptr;
1729     return Struct->getTypeAtIndex(Idx);
1730   }
1731   if (!Idx->getType()->isIntOrIntVectorTy())
1732     return nullptr;
1733   if (auto *Array = dyn_cast<ArrayType>(Ty))
1734     return Array->getElementType();
1735   if (auto *Vector = dyn_cast<VectorType>(Ty))
1736     return Vector->getElementType();
1737   return nullptr;
1738 }
1739
1740 Type *GetElementPtrInst::getTypeAtIndex(Type *Ty, uint64_t Idx) {
1741   if (auto *Struct = dyn_cast<StructType>(Ty)) {
1742     if (Idx >= Struct->getNumElements())
1743       return nullptr;
1744     return Struct->getElementType(Idx);
1745   }
1746   if (auto *Array = dyn_cast<ArrayType>(Ty))
1747     return Array->getElementType();
1748   if (auto *Vector = dyn_cast<VectorType>(Ty))
1749     return Vector->getElementType();
1750   return nullptr;
1751 }
1752
1753 template <typename IndexTy>
1754 static Type *getIndexedTypeInternal(Type *Ty, ArrayRef<IndexTy> IdxList) {
1755   if (IdxList.empty())
1756     return Ty;
1757   for (IndexTy V : IdxList.slice(1)) {
1758     Ty = GetElementPtrInst::getTypeAtIndex(Ty, V);
1759     if (!Ty)
1760       return Ty;
1761   }
1762   return Ty;
1763 }
1764
1765 Type *GetElementPtrInst::getIndexedType(Type *Ty, ArrayRef<Value *> IdxList) {
1766   return getIndexedTypeInternal(Ty, IdxList);
1767 }
1768
1769 Type *GetElementPtrInst::getIndexedType(Type *Ty,
1770                                         ArrayRef<Constant *> IdxList) {
1771   return getIndexedTypeInternal(Ty, IdxList);
1772 }
1773
1774 Type *GetElementPtrInst::getIndexedType(Type *Ty, ArrayRef<uint64_t> IdxList) {
1775   return getIndexedTypeInternal(Ty, IdxList);
1776 }
1777
1778 /// hasAllZeroIndices - Return true if all of the indices of this GEP are
1779 /// zeros.  If so, the result pointer and the first operand have the same
1780 /// value, just potentially different types.
1781 bool GetElementPtrInst::hasAllZeroIndices() const {
1782   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
1783     if (ConstantInt *CI = dyn_cast<ConstantInt>(getOperand(i))) {
1784       if (!CI->isZero()) return false;
1785     } else {
1786       return false;
1787     }
1788   }
1789   return true;
1790 }
1791
1792 /// hasAllConstantIndices - Return true if all of the indices of this GEP are
1793 /// constant integers.  If so, the result pointer and the first operand have
1794 /// a constant offset between them.
1795 bool GetElementPtrInst::hasAllConstantIndices() const {
1796   for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
1797     if (!isa<ConstantInt>(getOperand(i)))
1798       return false;
1799   }
1800   return true;
1801 }
1802
1803 void GetElementPtrInst::setIsInBounds(bool B) {
1804   cast<GEPOperator>(this)->setIsInBounds(B);
1805 }
1806
1807 bool GetElementPtrInst::isInBounds() const {
1808   return cast<GEPOperator>(this)->isInBounds();
1809 }
1810
1811 bool GetElementPtrInst::accumulateConstantOffset(const DataLayout &DL,
1812                                                  APInt &Offset) const {
1813   // Delegate to the generic GEPOperator implementation.
1814   return cast<GEPOperator>(this)->accumulateConstantOffset(DL, Offset);
1815 }
1816
1817 bool GetElementPtrInst::collectOffset(
1818     const DataLayout &DL, unsigned BitWidth,
1819     MapVector<Value *, APInt> &VariableOffsets,
1820     APInt &ConstantOffset) const {
1821   // Delegate to the generic GEPOperator implementation.
1822   return cast<GEPOperator>(this)->collectOffset(DL, BitWidth, VariableOffsets,
1823                                                 ConstantOffset);
1824 }
1825
1826 //===----------------------------------------------------------------------===//
1827 //                           ExtractElementInst Implementation
1828 //===----------------------------------------------------------------------===//
1829
1830 ExtractElementInst::ExtractElementInst(Value *Val, Value *Index,
1831                                        const Twine &Name,
1832                                        Instruction *InsertBef)
1833   : Instruction(cast<VectorType>(Val->getType())->getElementType(),
1834                 ExtractElement,
1835                 OperandTraits<ExtractElementInst>::op_begin(this),
1836                 2, InsertBef) {
1837   assert(isValidOperands(Val, Index) &&
1838          "Invalid extractelement instruction operands!");
1839   Op<0>() = Val;
1840   Op<1>() = Index;
1841   setName(Name);
1842 }
1843
1844 ExtractElementInst::ExtractElementInst(Value *Val, Value *Index,
1845                                        const Twine &Name,
1846                                        BasicBlock *InsertAE)
1847   : Instruction(cast<VectorType>(Val->getType())->getElementType(),
1848                 ExtractElement,
1849                 OperandTraits<ExtractElementInst>::op_begin(this),
1850                 2, InsertAE) {
1851   assert(isValidOperands(Val, Index) &&
1852          "Invalid extractelement instruction operands!");
1853
1854   Op<0>() = Val;
1855   Op<1>() = Index;
1856   setName(Name);
1857 }
1858
1859 bool ExtractElementInst::isValidOperands(const Value *Val, const Value *Index) {
1860   if (!Val->getType()->isVectorTy() || !Index->getType()->isIntegerTy())
1861     return false;
1862   return true;
1863 }
1864
1865 //===----------------------------------------------------------------------===//
1866 //                           InsertElementInst Implementation
1867 //===----------------------------------------------------------------------===//
1868
1869 InsertElementInst::InsertElementInst(Value *Vec, Value *Elt, Value *Index,
1870                                      const Twine &Name,
1871                                      Instruction *InsertBef)
1872   : Instruction(Vec->getType(), InsertElement,
1873                 OperandTraits<InsertElementInst>::op_begin(this),
1874                 3, InsertBef) {
1875   assert(isValidOperands(Vec, Elt, Index) &&
1876          "Invalid insertelement instruction operands!");
1877   Op<0>() = Vec;
1878   Op<1>() = Elt;
1879   Op<2>() = Index;
1880   setName(Name);
1881 }
1882
1883 InsertElementInst::InsertElementInst(Value *Vec, Value *Elt, Value *Index,
1884                                      const Twine &Name,
1885                                      BasicBlock *InsertAE)
1886   : Instruction(Vec->getType(), InsertElement,
1887                 OperandTraits<InsertElementInst>::op_begin(this),
1888                 3, InsertAE) {
1889   assert(isValidOperands(Vec, Elt, Index) &&
1890          "Invalid insertelement instruction operands!");
1891
1892   Op<0>() = Vec;
1893   Op<1>() = Elt;
1894   Op<2>() = Index;
1895   setName(Name);
1896 }
1897
1898 bool InsertElementInst::isValidOperands(const Value *Vec, const Value *Elt,
1899                                         const Value *Index) {
1900   if (!Vec->getType()->isVectorTy())
1901     return false;   // First operand of insertelement must be vector type.
1902
1903   if (Elt->getType() != cast<VectorType>(Vec->getType())->getElementType())
1904     return false;// Second operand of insertelement must be vector element type.
1905
1906   if (!Index->getType()->isIntegerTy())
1907     return false;  // Third operand of insertelement must be i32.
1908   return true;
1909 }
1910
1911 //===----------------------------------------------------------------------===//
1912 //                      ShuffleVectorInst Implementation
1913 //===----------------------------------------------------------------------===//
1914
1915 static Value *createPlaceholderForShuffleVector(Value *V) {
1916   assert(V && "Cannot create placeholder of nullptr V");
1917   return PoisonValue::get(V->getType());
1918 }
1919
1920 ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *Mask, const Twine &Name,
1921                                      Instruction *InsertBefore)
1922     : ShuffleVectorInst(V1, createPlaceholderForShuffleVector(V1), Mask, Name,
1923                         InsertBefore) {}
1924
1925 ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *Mask, const Twine &Name,
1926                                      BasicBlock *InsertAtEnd)
1927     : ShuffleVectorInst(V1, createPlaceholderForShuffleVector(V1), Mask, Name,
1928                         InsertAtEnd) {}
1929
1930 ShuffleVectorInst::ShuffleVectorInst(Value *V1, ArrayRef<int> Mask,
1931                                      const Twine &Name,
1932                                      Instruction *InsertBefore)
1933     : ShuffleVectorInst(V1, createPlaceholderForShuffleVector(V1), Mask, Name,
1934                         InsertBefore) {}
1935
1936 ShuffleVectorInst::ShuffleVectorInst(Value *V1, ArrayRef<int> Mask,
1937                                      const Twine &Name, BasicBlock *InsertAtEnd)
1938     : ShuffleVectorInst(V1, createPlaceholderForShuffleVector(V1), Mask, Name,
1939                         InsertAtEnd) {}
1940
1941 ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *V2, Value *Mask,
1942                                      const Twine &Name,
1943                                      Instruction *InsertBefore)
1944     : Instruction(
1945           VectorType::get(cast<VectorType>(V1->getType())->getElementType(),
1946                           cast<VectorType>(Mask->getType())->getElementCount()),
1947           ShuffleVector, OperandTraits<ShuffleVectorInst>::op_begin(this),
1948           OperandTraits<ShuffleVectorInst>::operands(this), InsertBefore) {
1949   assert(isValidOperands(V1, V2, Mask) &&
1950          "Invalid shuffle vector instruction operands!");
1951
1952   Op<0>() = V1;
1953   Op<1>() = V2;
1954   SmallVector<int, 16> MaskArr;
1955   getShuffleMask(cast<Constant>(Mask), MaskArr);
1956   setShuffleMask(MaskArr);
1957   setName(Name);
1958 }
1959
1960 ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *V2, Value *Mask,
1961                                      const Twine &Name, BasicBlock *InsertAtEnd)
1962     : Instruction(
1963           VectorType::get(cast<VectorType>(V1->getType())->getElementType(),
1964                           cast<VectorType>(Mask->getType())->getElementCount()),
1965           ShuffleVector, OperandTraits<ShuffleVectorInst>::op_begin(this),
1966           OperandTraits<ShuffleVectorInst>::operands(this), InsertAtEnd) {
1967   assert(isValidOperands(V1, V2, Mask) &&
1968          "Invalid shuffle vector instruction operands!");
1969
1970   Op<0>() = V1;
1971   Op<1>() = V2;
1972   SmallVector<int, 16> MaskArr;
1973   getShuffleMask(cast<Constant>(Mask), MaskArr);
1974   setShuffleMask(MaskArr);
1975   setName(Name);
1976 }
1977
1978 ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *V2, ArrayRef<int> Mask,
1979                                      const Twine &Name,
1980                                      Instruction *InsertBefore)
1981     : Instruction(
1982           VectorType::get(cast<VectorType>(V1->getType())->getElementType(),
1983                           Mask.size(), isa<ScalableVectorType>(V1->getType())),
1984           ShuffleVector, OperandTraits<ShuffleVectorInst>::op_begin(this),
1985           OperandTraits<ShuffleVectorInst>::operands(this), InsertBefore) {
1986   assert(isValidOperands(V1, V2, Mask) &&
1987          "Invalid shuffle vector instruction operands!");
1988   Op<0>() = V1;
1989   Op<1>() = V2;
1990   setShuffleMask(Mask);
1991   setName(Name);
1992 }
1993
1994 ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *V2, ArrayRef<int> Mask,
1995                                      const Twine &Name, BasicBlock *InsertAtEnd)
1996     : Instruction(
1997           VectorType::get(cast<VectorType>(V1->getType())->getElementType(),
1998                           Mask.size(), isa<ScalableVectorType>(V1->getType())),
1999           ShuffleVector, OperandTraits<ShuffleVectorInst>::op_begin(this),
2000           OperandTraits<ShuffleVectorInst>::operands(this), InsertAtEnd) {
2001   assert(isValidOperands(V1, V2, Mask) &&
2002          "Invalid shuffle vector instruction operands!");
2003
2004   Op<0>() = V1;
2005   Op<1>() = V2;
2006   setShuffleMask(Mask);
2007   setName(Name);
2008 }
2009
2010 void ShuffleVectorInst::commute() {
2011   int NumOpElts = cast<FixedVectorType>(Op<0>()->getType())->getNumElements();
2012   int NumMaskElts = ShuffleMask.size();
2013   SmallVector<int, 16> NewMask(NumMaskElts);
2014   for (int i = 0; i != NumMaskElts; ++i) {
2015     int MaskElt = getMaskValue(i);
2016     if (MaskElt == PoisonMaskElem) {
2017       NewMask[i] = PoisonMaskElem;
2018       continue;
2019     }
2020     assert(MaskElt >= 0 && MaskElt < 2 * NumOpElts && "Out-of-range mask");
2021     MaskElt = (MaskElt < NumOpElts) ? MaskElt + NumOpElts : MaskElt - NumOpElts;
2022     NewMask[i] = MaskElt;
2023   }
2024   setShuffleMask(NewMask);
2025   Op<0>().swap(Op<1>());
2026 }
2027
2028 bool ShuffleVectorInst::isValidOperands(const Value *V1, const Value *V2,
2029                                         ArrayRef<int> Mask) {
2030   // V1 and V2 must be vectors of the same type.
2031   if (!isa<VectorType>(V1->getType()) || V1->getType() != V2->getType())
2032     return false;
2033
2034   // Make sure the mask elements make sense.
2035   int V1Size =
2036       cast<VectorType>(V1->getType())->getElementCount().getKnownMinValue();
2037   for (int Elem : Mask)
2038     if (Elem != PoisonMaskElem && Elem >= V1Size * 2)
2039       return false;
2040
2041   if (isa<ScalableVectorType>(V1->getType()))
2042     if ((Mask[0] != 0 && Mask[0] != PoisonMaskElem) || !all_equal(Mask))
2043       return false;
2044
2045   return true;
2046 }
2047
2048 bool ShuffleVectorInst::isValidOperands(const Value *V1, const Value *V2,
2049                                         const Value *Mask) {
2050   // V1 and V2 must be vectors of the same type.
2051   if (!V1->getType()->isVectorTy() || V1->getType() != V2->getType())
2052     return false;
2053
2054   // Mask must be vector of i32, and must be the same kind of vector as the
2055   // input vectors
2056   auto *MaskTy = dyn_cast<VectorType>(Mask->getType());
2057   if (!MaskTy || !MaskTy->getElementType()->isIntegerTy(32) ||
2058       isa<ScalableVectorType>(MaskTy) != isa<ScalableVectorType>(V1->getType()))
2059     return false;
2060
2061   // Check to see if Mask is valid.
2062   if (isa<UndefValue>(Mask) || isa<ConstantAggregateZero>(Mask))
2063     return true;
2064
2065   if (const auto *MV = dyn_cast<ConstantVector>(Mask)) {
2066     unsigned V1Size = cast<FixedVectorType>(V1->getType())->getNumElements();
2067     for (Value *Op : MV->operands()) {
2068       if (auto *CI = dyn_cast<ConstantInt>(Op)) {
2069         if (CI->uge(V1Size*2))
2070           return false;
2071       } else if (!isa<UndefValue>(Op)) {
2072         return false;
2073       }
2074     }
2075     return true;
2076   }
2077
2078   if (const auto *CDS = dyn_cast<ConstantDataSequential>(Mask)) {
2079     unsigned V1Size = cast<FixedVectorType>(V1->getType())->getNumElements();
2080     for (unsigned i = 0, e = cast<FixedVectorType>(MaskTy)->getNumElements();
2081          i != e; ++i)
2082       if (CDS->getElementAsInteger(i) >= V1Size*2)
2083         return false;
2084     return true;
2085   }
2086
2087   return false;
2088 }
2089
2090 void ShuffleVectorInst::getShuffleMask(const Constant *Mask,
2091                                        SmallVectorImpl<int> &Result) {
2092   ElementCount EC = cast<VectorType>(Mask->getType())->getElementCount();
2093
2094   if (isa<ConstantAggregateZero>(Mask)) {
2095     Result.resize(EC.getKnownMinValue(), 0);
2096     return;
2097   }
2098
2099   Result.reserve(EC.getKnownMinValue());
2100
2101   if (EC.isScalable()) {
2102     assert((isa<ConstantAggregateZero>(Mask) || isa<UndefValue>(Mask)) &&
2103            "Scalable vector shuffle mask must be undef or zeroinitializer");
2104     int MaskVal = isa<UndefValue>(Mask) ? -1 : 0;
2105     for (unsigned I = 0; I < EC.getKnownMinValue(); ++I)
2106       Result.emplace_back(MaskVal);
2107     return;
2108   }
2109
2110   unsigned NumElts = EC.getKnownMinValue();
2111
2112   if (auto *CDS = dyn_cast<ConstantDataSequential>(Mask)) {
2113     for (unsigned i = 0; i != NumElts; ++i)
2114       Result.push_back(CDS->getElementAsInteger(i));
2115     return;
2116   }
2117   for (unsigned i = 0; i != NumElts; ++i) {
2118     Constant *C = Mask->getAggregateElement(i);
2119     Result.push_back(isa<UndefValue>(C) ? -1 :
2120                      cast<ConstantInt>(C)->getZExtValue());
2121   }
2122 }
2123
2124 void ShuffleVectorInst::setShuffleMask(ArrayRef<int> Mask) {
2125   ShuffleMask.assign(Mask.begin(), Mask.end());
2126   ShuffleMaskForBitcode = convertShuffleMaskForBitcode(Mask, getType());
2127 }
2128
2129 Constant *ShuffleVectorInst::convertShuffleMaskForBitcode(ArrayRef<int> Mask,
2130                                                           Type *ResultTy) {
2131   Type *Int32Ty = Type::getInt32Ty(ResultTy->getContext());
2132   if (isa<ScalableVectorType>(ResultTy)) {
2133     assert(all_equal(Mask) && "Unexpected shuffle");
2134     Type *VecTy = VectorType::get(Int32Ty, Mask.size(), true);
2135     if (Mask[0] == 0)
2136       return Constant::getNullValue(VecTy);
2137     return UndefValue::get(VecTy);
2138   }
2139   SmallVector<Constant *, 16> MaskConst;
2140   for (int Elem : Mask) {
2141     if (Elem == PoisonMaskElem)
2142       MaskConst.push_back(PoisonValue::get(Int32Ty));
2143     else
2144       MaskConst.push_back(ConstantInt::get(Int32Ty, Elem));
2145   }
2146   return ConstantVector::get(MaskConst);
2147 }
2148
2149 static bool isSingleSourceMaskImpl(ArrayRef<int> Mask, int NumOpElts) {
2150   assert(!Mask.empty() && "Shuffle mask must contain elements");
2151   bool UsesLHS = false;
2152   bool UsesRHS = false;
2153   for (int I : Mask) {
2154     if (I == -1)
2155       continue;
2156     assert(I >= 0 && I < (NumOpElts * 2) &&
2157            "Out-of-bounds shuffle mask element");
2158     UsesLHS |= (I < NumOpElts);
2159     UsesRHS |= (I >= NumOpElts);
2160     if (UsesLHS && UsesRHS)
2161       return false;
2162   }
2163   // Allow for degenerate case: completely undef mask means neither source is used.
2164   return UsesLHS || UsesRHS;
2165 }
2166
2167 bool ShuffleVectorInst::isSingleSourceMask(ArrayRef<int> Mask, int NumSrcElts) {
2168   // We don't have vector operand size information, so assume operands are the
2169   // same size as the mask.
2170   return isSingleSourceMaskImpl(Mask, NumSrcElts);
2171 }
2172
2173 static bool isIdentityMaskImpl(ArrayRef<int> Mask, int NumOpElts) {
2174   if (!isSingleSourceMaskImpl(Mask, NumOpElts))
2175     return false;
2176   for (int i = 0, NumMaskElts = Mask.size(); i < NumMaskElts; ++i) {
2177     if (Mask[i] == -1)
2178       continue;
2179     if (Mask[i] != i && Mask[i] != (NumOpElts + i))
2180       return false;
2181   }
2182   return true;
2183 }
2184
2185 bool ShuffleVectorInst::isIdentityMask(ArrayRef<int> Mask, int NumSrcElts) {
2186   if (Mask.size() != static_cast<unsigned>(NumSrcElts))
2187     return false;
2188   // We don't have vector operand size information, so assume operands are the
2189   // same size as the mask.
2190   return isIdentityMaskImpl(Mask, NumSrcElts);
2191 }
2192
2193 bool ShuffleVectorInst::isReverseMask(ArrayRef<int> Mask, int NumSrcElts) {
2194   if (Mask.size() != static_cast<unsigned>(NumSrcElts))
2195     return false;
2196   if (!isSingleSourceMask(Mask, NumSrcElts))
2197     return false;
2198
2199   // The number of elements in the mask must be at least 2.
2200   if (NumSrcElts < 2)
2201     return false;
2202
2203   for (int I = 0, E = Mask.size(); I < E; ++I) {
2204     if (Mask[I] == -1)
2205       continue;
2206     if (Mask[I] != (NumSrcElts - 1 - I) &&
2207         Mask[I] != (NumSrcElts + NumSrcElts - 1 - I))
2208       return false;
2209   }
2210   return true;
2211 }
2212
2213 bool ShuffleVectorInst::isZeroEltSplatMask(ArrayRef<int> Mask, int NumSrcElts) {
2214   if (Mask.size() != static_cast<unsigned>(NumSrcElts))
2215     return false;
2216   if (!isSingleSourceMask(Mask, NumSrcElts))
2217     return false;
2218   for (int I = 0, E = Mask.size(); I < E; ++I) {
2219     if (Mask[I] == -1)
2220       continue;
2221     if (Mask[I] != 0 && Mask[I] != NumSrcElts)
2222       return false;
2223   }
2224   return true;
2225 }
2226
2227 bool ShuffleVectorInst::isSelectMask(ArrayRef<int> Mask, int NumSrcElts) {
2228   if (Mask.size() != static_cast<unsigned>(NumSrcElts))
2229     return false;
2230   // Select is differentiated from identity. It requires using both sources.
2231   if (isSingleSourceMask(Mask, NumSrcElts))
2232     return false;
2233   for (int I = 0, E = Mask.size(); I < E; ++I) {
2234     if (Mask[I] == -1)
2235       continue;
2236     if (Mask[I] != I && Mask[I] != (NumSrcElts + I))
2237       return false;
2238   }
2239   return true;
2240 }
2241
2242 bool ShuffleVectorInst::isTransposeMask(ArrayRef<int> Mask, int NumSrcElts) {
2243   // Example masks that will return true:
2244   // v1 = <a, b, c, d>
2245   // v2 = <e, f, g, h>
2246   // trn1 = shufflevector v1, v2 <0, 4, 2, 6> = <a, e, c, g>
2247   // trn2 = shufflevector v1, v2 <1, 5, 3, 7> = <b, f, d, h>
2248
2249   if (Mask.size() != static_cast<unsigned>(NumSrcElts))
2250     return false;
2251   // 1. The number of elements in the mask must be a power-of-2 and at least 2.
2252   int Sz = Mask.size();
2253   if (Sz < 2 || !isPowerOf2_32(Sz))
2254     return false;
2255
2256   // 2. The first element of the mask must be either a 0 or a 1.
2257   if (Mask[0] != 0 && Mask[0] != 1)
2258     return false;
2259
2260   // 3. The difference between the first 2 elements must be equal to the
2261   // number of elements in the mask.
2262   if ((Mask[1] - Mask[0]) != NumSrcElts)
2263     return false;
2264
2265   // 4. The difference between consecutive even-numbered and odd-numbered
2266   // elements must be equal to 2.
2267   for (int I = 2; I < Sz; ++I) {
2268     int MaskEltVal = Mask[I];
2269     if (MaskEltVal == -1)
2270       return false;
2271     int MaskEltPrevVal = Mask[I - 2];
2272     if (MaskEltVal - MaskEltPrevVal != 2)
2273       return false;
2274   }
2275   return true;
2276 }
2277
2278 bool ShuffleVectorInst::isSpliceMask(ArrayRef<int> Mask, int NumSrcElts,
2279                                      int &Index) {
2280   if (Mask.size() != static_cast<unsigned>(NumSrcElts))
2281     return false;
2282   // Example: shufflevector <4 x n> A, <4 x n> B, <1,2,3,4>
2283   int StartIndex = -1;
2284   for (int I = 0, E = Mask.size(); I != E; ++I) {
2285     int MaskEltVal = Mask[I];
2286     if (MaskEltVal == -1)
2287       continue;
2288
2289     if (StartIndex == -1) {
2290       // Don't support a StartIndex that begins in the second input, or if the
2291       // first non-undef index would access below the StartIndex.
2292       if (MaskEltVal < I || NumSrcElts <= (MaskEltVal - I))
2293         return false;
2294
2295       StartIndex = MaskEltVal - I;
2296       continue;
2297     }
2298
2299     // Splice is sequential starting from StartIndex.
2300     if (MaskEltVal != (StartIndex + I))
2301       return false;
2302   }
2303
2304   if (StartIndex == -1)
2305     return false;
2306
2307   // NOTE: This accepts StartIndex == 0 (COPY).
2308   Index = StartIndex;
2309   return true;
2310 }
2311
2312 bool ShuffleVectorInst::isExtractSubvectorMask(ArrayRef<int> Mask,
2313                                                int NumSrcElts, int &Index) {
2314   // Must extract from a single source.
2315   if (!isSingleSourceMaskImpl(Mask, NumSrcElts))
2316     return false;
2317
2318   // Must be smaller (else this is an Identity shuffle).
2319   if (NumSrcElts <= (int)Mask.size())
2320     return false;
2321
2322   // Find start of extraction, accounting that we may start with an UNDEF.
2323   int SubIndex = -1;
2324   for (int i = 0, e = Mask.size(); i != e; ++i) {
2325     int M = Mask[i];
2326     if (M < 0)
2327       continue;
2328     int Offset = (M % NumSrcElts) - i;
2329     if (0 <= SubIndex && SubIndex != Offset)
2330       return false;
2331     SubIndex = Offset;
2332   }
2333
2334   if (0 <= SubIndex && SubIndex + (int)Mask.size() <= NumSrcElts) {
2335     Index = SubIndex;
2336     return true;
2337   }
2338   return false;
2339 }
2340
2341 bool ShuffleVectorInst::isInsertSubvectorMask(ArrayRef<int> Mask,
2342                                               int NumSrcElts, int &NumSubElts,
2343                                               int &Index) {
2344   int NumMaskElts = Mask.size();
2345
2346   // Don't try to match if we're shuffling to a smaller size.
2347   if (NumMaskElts < NumSrcElts)
2348     return false;
2349
2350   // TODO: We don't recognize self-insertion/widening.
2351   if (isSingleSourceMaskImpl(Mask, NumSrcElts))
2352     return false;
2353
2354   // Determine which mask elements are attributed to which source.
2355   APInt UndefElts = APInt::getZero(NumMaskElts);
2356   APInt Src0Elts = APInt::getZero(NumMaskElts);
2357   APInt Src1Elts = APInt::getZero(NumMaskElts);
2358   bool Src0Identity = true;
2359   bool Src1Identity = true;
2360
2361   for (int i = 0; i != NumMaskElts; ++i) {
2362     int M = Mask[i];
2363     if (M < 0) {
2364       UndefElts.setBit(i);
2365       continue;
2366     }
2367     if (M < NumSrcElts) {
2368       Src0Elts.setBit(i);
2369       Src0Identity &= (M == i);
2370       continue;
2371     }
2372     Src1Elts.setBit(i);
2373     Src1Identity &= (M == (i + NumSrcElts));
2374   }
2375   assert((Src0Elts | Src1Elts | UndefElts).isAllOnes() &&
2376          "unknown shuffle elements");
2377   assert(!Src0Elts.isZero() && !Src1Elts.isZero() &&
2378          "2-source shuffle not found");
2379
2380   // Determine lo/hi span ranges.
2381   // TODO: How should we handle undefs at the start of subvector insertions?
2382   int Src0Lo = Src0Elts.countr_zero();
2383   int Src1Lo = Src1Elts.countr_zero();
2384   int Src0Hi = NumMaskElts - Src0Elts.countl_zero();
2385   int Src1Hi = NumMaskElts - Src1Elts.countl_zero();
2386
2387   // If src0 is in place, see if the src1 elements is inplace within its own
2388   // span.
2389   if (Src0Identity) {
2390     int NumSub1Elts = Src1Hi - Src1Lo;
2391     ArrayRef<int> Sub1Mask = Mask.slice(Src1Lo, NumSub1Elts);
2392     if (isIdentityMaskImpl(Sub1Mask, NumSrcElts)) {
2393       NumSubElts = NumSub1Elts;
2394       Index = Src1Lo;
2395       return true;
2396     }
2397   }
2398
2399   // If src1 is in place, see if the src0 elements is inplace within its own
2400   // span.
2401   if (Src1Identity) {
2402     int NumSub0Elts = Src0Hi - Src0Lo;
2403     ArrayRef<int> Sub0Mask = Mask.slice(Src0Lo, NumSub0Elts);
2404     if (isIdentityMaskImpl(Sub0Mask, NumSrcElts)) {
2405       NumSubElts = NumSub0Elts;
2406       Index = Src0Lo;
2407       return true;
2408     }
2409   }
2410
2411   return false;
2412 }
2413
2414 bool ShuffleVectorInst::isIdentityWithPadding() const {
2415   // FIXME: Not currently possible to express a shuffle mask for a scalable
2416   // vector for this case.
2417   if (isa<ScalableVectorType>(getType()))
2418     return false;
2419
2420   int NumOpElts = cast<FixedVectorType>(Op<0>()->getType())->getNumElements();
2421   int NumMaskElts = cast<FixedVectorType>(getType())->getNumElements();
2422   if (NumMaskElts <= NumOpElts)
2423     return false;
2424
2425   // The first part of the mask must choose elements from exactly 1 source op.
2426   ArrayRef<int> Mask = getShuffleMask();
2427   if (!isIdentityMaskImpl(Mask, NumOpElts))
2428     return false;
2429
2430   // All extending must be with undef elements.
2431   for (int i = NumOpElts; i < NumMaskElts; ++i)
2432     if (Mask[i] != -1)
2433       return false;
2434
2435   return true;
2436 }
2437
2438 bool ShuffleVectorInst::isIdentityWithExtract() const {
2439   // FIXME: Not currently possible to express a shuffle mask for a scalable
2440   // vector for this case.
2441   if (isa<ScalableVectorType>(getType()))
2442     return false;
2443
2444   int NumOpElts = cast<FixedVectorType>(Op<0>()->getType())->getNumElements();
2445   int NumMaskElts = cast<FixedVectorType>(getType())->getNumElements();
2446   if (NumMaskElts >= NumOpElts)
2447     return false;
2448
2449   return isIdentityMaskImpl(getShuffleMask(), NumOpElts);
2450 }
2451
2452 bool ShuffleVectorInst::isConcat() const {
2453   // Vector concatenation is differentiated from identity with padding.
2454   if (isa<UndefValue>(Op<0>()) || isa<UndefValue>(Op<1>()))
2455     return false;
2456
2457   // FIXME: Not currently possible to express a shuffle mask for a scalable
2458   // vector for this case.
2459   if (isa<ScalableVectorType>(getType()))
2460     return false;
2461
2462   int NumOpElts = cast<FixedVectorType>(Op<0>()->getType())->getNumElements();
2463   int NumMaskElts = cast<FixedVectorType>(getType())->getNumElements();
2464   if (NumMaskElts != NumOpElts * 2)
2465     return false;
2466
2467   // Use the mask length rather than the operands' vector lengths here. We
2468   // already know that the shuffle returns a vector twice as long as the inputs,
2469   // and neither of the inputs are undef vectors. If the mask picks consecutive
2470   // elements from both inputs, then this is a concatenation of the inputs.
2471   return isIdentityMaskImpl(getShuffleMask(), NumMaskElts);
2472 }
2473
2474 static bool isReplicationMaskWithParams(ArrayRef<int> Mask,
2475                                         int ReplicationFactor, int VF) {
2476   assert(Mask.size() == (unsigned)ReplicationFactor * VF &&
2477          "Unexpected mask size.");
2478
2479   for (int CurrElt : seq(VF)) {
2480     ArrayRef<int> CurrSubMask = Mask.take_front(ReplicationFactor);
2481     assert(CurrSubMask.size() == (unsigned)ReplicationFactor &&
2482            "Run out of mask?");
2483     Mask = Mask.drop_front(ReplicationFactor);
2484     if (!all_of(CurrSubMask, [CurrElt](int MaskElt) {
2485           return MaskElt == PoisonMaskElem || MaskElt == CurrElt;
2486         }))
2487       return false;
2488   }
2489   assert(Mask.empty() && "Did not consume the whole mask?");
2490
2491   return true;
2492 }
2493
2494 bool ShuffleVectorInst::isReplicationMask(ArrayRef<int> Mask,
2495                                           int &ReplicationFactor, int &VF) {
2496   // undef-less case is trivial.
2497   if (!llvm::is_contained(Mask, PoisonMaskElem)) {
2498     ReplicationFactor =
2499         Mask.take_while([](int MaskElt) { return MaskElt == 0; }).size();
2500     if (ReplicationFactor == 0 || Mask.size() % ReplicationFactor != 0)
2501       return false;
2502     VF = Mask.size() / ReplicationFactor;
2503     return isReplicationMaskWithParams(Mask, ReplicationFactor, VF);
2504   }
2505
2506   // However, if the mask contains undef's, we have to enumerate possible tuples
2507   // and pick one. There are bounds on replication factor: [1, mask size]
2508   // (where RF=1 is an identity shuffle, RF=mask size is a broadcast shuffle)
2509   // Additionally, mask size is a replication factor multiplied by vector size,
2510   // which further significantly reduces the search space.
2511
2512   // Before doing that, let's perform basic correctness checking first.
2513   int Largest = -1;
2514   for (int MaskElt : Mask) {
2515     if (MaskElt == PoisonMaskElem)
2516       continue;
2517     // Elements must be in non-decreasing order.
2518     if (MaskElt < Largest)
2519       return false;
2520     Largest = std::max(Largest, MaskElt);
2521   }
2522
2523   // Prefer larger replication factor if all else equal.
2524   for (int PossibleReplicationFactor :
2525        reverse(seq_inclusive<unsigned>(1, Mask.size()))) {
2526     if (Mask.size() % PossibleReplicationFactor != 0)
2527       continue;
2528     int PossibleVF = Mask.size() / PossibleReplicationFactor;
2529     if (!isReplicationMaskWithParams(Mask, PossibleReplicationFactor,
2530                                      PossibleVF))
2531       continue;
2532     ReplicationFactor = PossibleReplicationFactor;
2533     VF = PossibleVF;
2534     return true;
2535   }
2536
2537   return false;
2538 }
2539
2540 bool ShuffleVectorInst::isReplicationMask(int &ReplicationFactor,
2541                                           int &VF) const {
2542   // Not possible to express a shuffle mask for a scalable vector for this
2543   // case.
2544   if (isa<ScalableVectorType>(getType()))
2545     return false;
2546
2547   VF = cast<FixedVectorType>(Op<0>()->getType())->getNumElements();
2548   if (ShuffleMask.size() % VF != 0)
2549     return false;
2550   ReplicationFactor = ShuffleMask.size() / VF;
2551
2552   return isReplicationMaskWithParams(ShuffleMask, ReplicationFactor, VF);
2553 }
2554
2555 bool ShuffleVectorInst::isOneUseSingleSourceMask(ArrayRef<int> Mask, int VF) {
2556   if (VF <= 0 || Mask.size() < static_cast<unsigned>(VF) ||
2557       Mask.size() % VF != 0)
2558     return false;
2559   for (unsigned K = 0, Sz = Mask.size(); K < Sz; K += VF) {
2560     ArrayRef<int> SubMask = Mask.slice(K, VF);
2561     if (all_of(SubMask, [](int Idx) { return Idx == PoisonMaskElem; }))
2562       continue;
2563     SmallBitVector Used(VF, false);
2564     for (int Idx : SubMask) {
2565       if (Idx != PoisonMaskElem && Idx < VF)
2566         Used.set(Idx);
2567     }
2568     if (!Used.all())
2569       return false;
2570   }
2571   return true;
2572 }
2573
2574 /// Return true if this shuffle mask is a replication mask.
2575 bool ShuffleVectorInst::isOneUseSingleSourceMask(int VF) const {
2576   // Not possible to express a shuffle mask for a scalable vector for this
2577   // case.
2578   if (isa<ScalableVectorType>(getType()))
2579     return false;
2580   if (!isSingleSourceMask(ShuffleMask, VF))
2581     return false;
2582
2583   return isOneUseSingleSourceMask(ShuffleMask, VF);
2584 }
2585
2586 bool ShuffleVectorInst::isInterleave(unsigned Factor) {
2587   FixedVectorType *OpTy = dyn_cast<FixedVectorType>(getOperand(0)->getType());
2588   // shuffle_vector can only interleave fixed length vectors - for scalable
2589   // vectors, see the @llvm.experimental.vector.interleave2 intrinsic
2590   if (!OpTy)
2591     return false;
2592   unsigned OpNumElts = OpTy->getNumElements();
2593
2594   return isInterleaveMask(ShuffleMask, Factor, OpNumElts * 2);
2595 }
2596
2597 bool ShuffleVectorInst::isInterleaveMask(
2598     ArrayRef<int> Mask, unsigned Factor, unsigned NumInputElts,
2599     SmallVectorImpl<unsigned> &StartIndexes) {
2600   unsigned NumElts = Mask.size();
2601   if (NumElts % Factor)
2602     return false;
2603
2604   unsigned LaneLen = NumElts / Factor;
2605   if (!isPowerOf2_32(LaneLen))
2606     return false;
2607
2608   StartIndexes.resize(Factor);
2609
2610   // Check whether each element matches the general interleaved rule.
2611   // Ignore undef elements, as long as the defined elements match the rule.
2612   // Outer loop processes all factors (x, y, z in the above example)
2613   unsigned I = 0, J;
2614   for (; I < Factor; I++) {
2615     unsigned SavedLaneValue;
2616     unsigned SavedNoUndefs = 0;
2617
2618     // Inner loop processes consecutive accesses (x, x+1... in the example)
2619     for (J = 0; J < LaneLen - 1; J++) {
2620       // Lane computes x's position in the Mask
2621       unsigned Lane = J * Factor + I;
2622       unsigned NextLane = Lane + Factor;
2623       int LaneValue = Mask[Lane];
2624       int NextLaneValue = Mask[NextLane];
2625
2626       // If both are defined, values must be sequential
2627       if (LaneValue >= 0 && NextLaneValue >= 0 &&
2628           LaneValue + 1 != NextLaneValue)
2629         break;
2630
2631       // If the next value is undef, save the current one as reference
2632       if (LaneValue >= 0 && NextLaneValue < 0) {
2633         SavedLaneValue = LaneValue;
2634         SavedNoUndefs = 1;
2635       }
2636
2637       // Undefs are allowed, but defined elements must still be consecutive:
2638       // i.e.: x,..., undef,..., x + 2,..., undef,..., undef,..., x + 5, ....
2639       // Verify this by storing the last non-undef followed by an undef
2640       // Check that following non-undef masks are incremented with the
2641       // corresponding distance.
2642       if (SavedNoUndefs > 0 && LaneValue < 0) {
2643         SavedNoUndefs++;
2644         if (NextLaneValue >= 0 &&
2645             SavedLaneValue + SavedNoUndefs != (unsigned)NextLaneValue)
2646           break;
2647       }
2648     }
2649
2650     if (J < LaneLen - 1)
2651       return false;
2652
2653     int StartMask = 0;
2654     if (Mask[I] >= 0) {
2655       // Check that the start of the I range (J=0) is greater than 0
2656       StartMask = Mask[I];
2657     } else if (Mask[(LaneLen - 1) * Factor + I] >= 0) {
2658       // StartMask defined by the last value in lane
2659       StartMask = Mask[(LaneLen - 1) * Factor + I] - J;
2660     } else if (SavedNoUndefs > 0) {
2661       // StartMask defined by some non-zero value in the j loop
2662       StartMask = SavedLaneValue - (LaneLen - 1 - SavedNoUndefs);
2663     }
2664     // else StartMask remains set to 0, i.e. all elements are undefs
2665
2666     if (StartMask < 0)
2667       return false;
2668     // We must stay within the vectors; This case can happen with undefs.
2669     if (StartMask + LaneLen > NumInputElts)
2670       return false;
2671
2672     StartIndexes[I] = StartMask;
2673   }
2674
2675   return true;
2676 }
2677
2678 /// Try to lower a vector shuffle as a bit rotation.
2679 ///
2680 /// Look for a repeated rotation pattern in each sub group.
2681 /// Returns an element-wise left bit rotation amount or -1 if failed.
2682 static int matchShuffleAsBitRotate(ArrayRef<int> Mask, int NumSubElts) {
2683   int NumElts = Mask.size();
2684   assert((NumElts % NumSubElts) == 0 && "Illegal shuffle mask");
2685
2686   int RotateAmt = -1;
2687   for (int i = 0; i != NumElts; i += NumSubElts) {
2688     for (int j = 0; j != NumSubElts; ++j) {
2689       int M = Mask[i + j];
2690       if (M < 0)
2691         continue;
2692       if (M < i || M >= i + NumSubElts)
2693         return -1;
2694       int Offset = (NumSubElts - (M - (i + j))) % NumSubElts;
2695       if (0 <= RotateAmt && Offset != RotateAmt)
2696         return -1;
2697       RotateAmt = Offset;
2698     }
2699   }
2700   return RotateAmt;
2701 }
2702
2703 bool ShuffleVectorInst::isBitRotateMask(
2704     ArrayRef<int> Mask, unsigned EltSizeInBits, unsigned MinSubElts,
2705     unsigned MaxSubElts, unsigned &NumSubElts, unsigned &RotateAmt) {
2706   for (NumSubElts = MinSubElts; NumSubElts <= MaxSubElts; NumSubElts *= 2) {
2707     int EltRotateAmt = matchShuffleAsBitRotate(Mask, NumSubElts);
2708     if (EltRotateAmt < 0)
2709       continue;
2710     RotateAmt = EltRotateAmt * EltSizeInBits;
2711     return true;
2712   }
2713
2714   return false;
2715 }
2716
2717 //===----------------------------------------------------------------------===//
2718 //                             InsertValueInst Class
2719 //===----------------------------------------------------------------------===//
2720
2721 void InsertValueInst::init(Value *Agg, Value *Val, ArrayRef<unsigned> Idxs,
2722                            const Twine &Name) {
2723   assert(getNumOperands() == 2 && "NumOperands not initialized?");
2724
2725   // There's no fundamental reason why we require at least one index
2726   // (other than weirdness with &*IdxBegin being invalid; see
2727   // getelementptr's init routine for example). But there's no
2728   // present need to support it.
2729   assert(!Idxs.empty() && "InsertValueInst must have at least one index");
2730
2731   assert(ExtractValueInst::getIndexedType(Agg->getType(), Idxs) ==
2732          Val->getType() && "Inserted value must match indexed type!");
2733   Op<0>() = Agg;
2734   Op<1>() = Val;
2735
2736   Indices.append(Idxs.begin(), Idxs.end());
2737   setName(Name);
2738 }
2739
2740 InsertValueInst::InsertValueInst(const InsertValueInst &IVI)
2741   : Instruction(IVI.getType(), InsertValue,
2742                 OperandTraits<InsertValueInst>::op_begin(this), 2),
2743     Indices(IVI.Indices) {
2744   Op<0>() = IVI.getOperand(0);
2745   Op<1>() = IVI.getOperand(1);
2746   SubclassOptionalData = IVI.SubclassOptionalData;
2747 }
2748
2749 //===----------------------------------------------------------------------===//
2750 //                             ExtractValueInst Class
2751 //===----------------------------------------------------------------------===//
2752
2753 void ExtractValueInst::init(ArrayRef<unsigned> Idxs, const Twine &Name) {
2754   assert(getNumOperands() == 1 && "NumOperands not initialized?");
2755
2756   // There's no fundamental reason why we require at least one index.
2757   // But there's no present need to support it.
2758   assert(!Idxs.empty() && "ExtractValueInst must have at least one index");
2759
2760   Indices.append(Idxs.begin(), Idxs.end());
2761   setName(Name);
2762 }
2763
2764 ExtractValueInst::ExtractValueInst(const ExtractValueInst &EVI)
2765   : UnaryInstruction(EVI.getType(), ExtractValue, EVI.getOperand(0)),
2766     Indices(EVI.Indices) {
2767   SubclassOptionalData = EVI.SubclassOptionalData;
2768 }
2769
2770 // getIndexedType - Returns the type of the element that would be extracted
2771 // with an extractvalue instruction with the specified parameters.
2772 //
2773 // A null type is returned if the indices are invalid for the specified
2774 // pointer type.
2775 //
2776 Type *ExtractValueInst::getIndexedType(Type *Agg,
2777                                        ArrayRef<unsigned> Idxs) {
2778   for (unsigned Index : Idxs) {
2779     // We can't use CompositeType::indexValid(Index) here.
2780     // indexValid() always returns true for arrays because getelementptr allows
2781     // out-of-bounds indices. Since we don't allow those for extractvalue and
2782     // insertvalue we need to check array indexing manually.
2783     // Since the only other types we can index into are struct types it's just
2784     // as easy to check those manually as well.
2785     if (ArrayType *AT = dyn_cast<ArrayType>(Agg)) {
2786       if (Index >= AT->getNumElements())
2787         return nullptr;
2788       Agg = AT->getElementType();
2789     } else if (StructType *ST = dyn_cast<StructType>(Agg)) {
2790       if (Index >= ST->getNumElements())
2791         return nullptr;
2792       Agg = ST->getElementType(Index);
2793     } else {
2794       // Not a valid type to index into.
2795       return nullptr;
2796     }
2797   }
2798   return const_cast<Type*>(Agg);
2799 }
2800
2801 //===----------------------------------------------------------------------===//
2802 //                             UnaryOperator Class
2803 //===----------------------------------------------------------------------===//
2804
2805 UnaryOperator::UnaryOperator(UnaryOps iType, Value *S,
2806                              Type *Ty, const Twine &Name,
2807                              Instruction *InsertBefore)
2808   : UnaryInstruction(Ty, iType, S, InsertBefore) {
2809   Op<0>() = S;
2810   setName(Name);
2811   AssertOK();
2812 }
2813
2814 UnaryOperator::UnaryOperator(UnaryOps iType, Value *S,
2815                              Type *Ty, const Twine &Name,
2816                              BasicBlock *InsertAtEnd)
2817   : UnaryInstruction(Ty, iType, S, InsertAtEnd) {
2818   Op<0>() = S;
2819   setName(Name);
2820   AssertOK();
2821 }
2822
2823 UnaryOperator *UnaryOperator::Create(UnaryOps Op, Value *S,
2824                                      const Twine &Name,
2825                                      Instruction *InsertBefore) {
2826   return new UnaryOperator(Op, S, S->getType(), Name, InsertBefore);
2827 }
2828
2829 UnaryOperator *UnaryOperator::Create(UnaryOps Op, Value *S,
2830                                      const Twine &Name,
2831                                      BasicBlock *InsertAtEnd) {
2832   UnaryOperator *Res = Create(Op, S, Name);
2833   Res->insertInto(InsertAtEnd, InsertAtEnd->end());
2834   return Res;
2835 }
2836
2837 void UnaryOperator::AssertOK() {
2838   Value *LHS = getOperand(0);
2839   (void)LHS; // Silence warnings.
2840 #ifndef NDEBUG
2841   switch (getOpcode()) {
2842   case FNeg:
2843     assert(getType() == LHS->getType() &&
2844            "Unary operation should return same type as operand!");
2845     assert(getType()->isFPOrFPVectorTy() &&
2846            "Tried to create a floating-point operation on a "
2847            "non-floating-point type!");
2848     break;
2849   default: llvm_unreachable("Invalid opcode provided");
2850   }
2851 #endif
2852 }
2853
2854 //===----------------------------------------------------------------------===//
2855 //                             BinaryOperator Class
2856 //===----------------------------------------------------------------------===//
2857
2858 BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
2859                                Type *Ty, const Twine &Name,
2860                                Instruction *InsertBefore)
2861   : Instruction(Ty, iType,
2862                 OperandTraits<BinaryOperator>::op_begin(this),
2863                 OperandTraits<BinaryOperator>::operands(this),
2864                 InsertBefore) {
2865   Op<0>() = S1;
2866   Op<1>() = S2;
2867   setName(Name);
2868   AssertOK();
2869 }
2870
2871 BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
2872                                Type *Ty, const Twine &Name,
2873                                BasicBlock *InsertAtEnd)
2874   : Instruction(Ty, iType,
2875                 OperandTraits<BinaryOperator>::op_begin(this),
2876                 OperandTraits<BinaryOperator>::operands(this),
2877                 InsertAtEnd) {
2878   Op<0>() = S1;
2879   Op<1>() = S2;
2880   setName(Name);
2881   AssertOK();
2882 }
2883
2884 void BinaryOperator::AssertOK() {
2885   Value *LHS = getOperand(0), *RHS = getOperand(1);
2886   (void)LHS; (void)RHS; // Silence warnings.
2887   assert(LHS->getType() == RHS->getType() &&
2888          "Binary operator operand types must match!");
2889 #ifndef NDEBUG
2890   switch (getOpcode()) {
2891   case Add: case Sub:
2892   case Mul:
2893     assert(getType() == LHS->getType() &&
2894            "Arithmetic operation should return same type as operands!");
2895     assert(getType()->isIntOrIntVectorTy() &&
2896            "Tried to create an integer operation on a non-integer type!");
2897     break;
2898   case FAdd: case FSub:
2899   case FMul:
2900     assert(getType() == LHS->getType() &&
2901            "Arithmetic operation should return same type as operands!");
2902     assert(getType()->isFPOrFPVectorTy() &&
2903            "Tried to create a floating-point operation on a "
2904            "non-floating-point type!");
2905     break;
2906   case UDiv:
2907   case SDiv:
2908     assert(getType() == LHS->getType() &&
2909            "Arithmetic operation should return same type as operands!");
2910     assert(getType()->isIntOrIntVectorTy() &&
2911            "Incorrect operand type (not integer) for S/UDIV");
2912     break;
2913   case FDiv:
2914     assert(getType() == LHS->getType() &&
2915            "Arithmetic operation should return same type as operands!");
2916     assert(getType()->isFPOrFPVectorTy() &&
2917            "Incorrect operand type (not floating point) for FDIV");
2918     break;
2919   case URem:
2920   case SRem:
2921     assert(getType() == LHS->getType() &&
2922            "Arithmetic operation should return same type as operands!");
2923     assert(getType()->isIntOrIntVectorTy() &&
2924            "Incorrect operand type (not integer) for S/UREM");
2925     break;
2926   case FRem:
2927     assert(getType() == LHS->getType() &&
2928            "Arithmetic operation should return same type as operands!");
2929     assert(getType()->isFPOrFPVectorTy() &&
2930            "Incorrect operand type (not floating point) for FREM");
2931     break;
2932   case Shl:
2933   case LShr:
2934   case AShr:
2935     assert(getType() == LHS->getType() &&
2936            "Shift operation should return same type as operands!");
2937     assert(getType()->isIntOrIntVectorTy() &&
2938            "Tried to create a shift operation on a non-integral type!");
2939     break;
2940   case And: case Or:
2941   case Xor:
2942     assert(getType() == LHS->getType() &&
2943            "Logical operation should return same type as operands!");
2944     assert(getType()->isIntOrIntVectorTy() &&
2945            "Tried to create a logical operation on a non-integral type!");
2946     break;
2947   default: llvm_unreachable("Invalid opcode provided");
2948   }
2949 #endif
2950 }
2951
2952 BinaryOperator *BinaryOperator::Create(BinaryOps Op, Value *S1, Value *S2,
2953                                        const Twine &Name,
2954                                        Instruction *InsertBefore) {
2955   assert(S1->getType() == S2->getType() &&
2956          "Cannot create binary operator with two operands of differing type!");
2957   return new BinaryOperator(Op, S1, S2, S1->getType(), Name, InsertBefore);
2958 }
2959
2960 BinaryOperator *BinaryOperator::Create(BinaryOps Op, Value *S1, Value *S2,
2961                                        const Twine &Name,
2962                                        BasicBlock *InsertAtEnd) {
2963   BinaryOperator *Res = Create(Op, S1, S2, Name);
2964   Res->insertInto(InsertAtEnd, InsertAtEnd->end());
2965   return Res;
2966 }
2967
2968 BinaryOperator *BinaryOperator::CreateNeg(Value *Op, const Twine &Name,
2969                                           Instruction *InsertBefore) {
2970   Value *Zero = ConstantInt::get(Op->getType(), 0);
2971   return new BinaryOperator(Instruction::Sub,
2972                             Zero, Op,
2973                             Op->getType(), Name, InsertBefore);
2974 }
2975
2976 BinaryOperator *BinaryOperator::CreateNeg(Value *Op, const Twine &Name,
2977                                           BasicBlock *InsertAtEnd) {
2978   Value *Zero = ConstantInt::get(Op->getType(), 0);
2979   return new BinaryOperator(Instruction::Sub,
2980                             Zero, Op,
2981                             Op->getType(), Name, InsertAtEnd);
2982 }
2983
2984 BinaryOperator *BinaryOperator::CreateNSWNeg(Value *Op, const Twine &Name,
2985                                              Instruction *InsertBefore) {
2986   Value *Zero = ConstantInt::get(Op->getType(), 0);
2987   return BinaryOperator::CreateNSWSub(Zero, Op, Name, InsertBefore);
2988 }
2989
2990 BinaryOperator *BinaryOperator::CreateNSWNeg(Value *Op, const Twine &Name,
2991                                              BasicBlock *InsertAtEnd) {
2992   Value *Zero = ConstantInt::get(Op->getType(), 0);
2993   return BinaryOperator::CreateNSWSub(Zero, Op, Name, InsertAtEnd);
2994 }
2995
2996 BinaryOperator *BinaryOperator::CreateNUWNeg(Value *Op, const Twine &Name,
2997                                              Instruction *InsertBefore) {
2998   Value *Zero = ConstantInt::get(Op->getType(), 0);
2999   return BinaryOperator::CreateNUWSub(Zero, Op, Name, InsertBefore);
3000 }
3001
3002 BinaryOperator *BinaryOperator::CreateNUWNeg(Value *Op, const Twine &Name,
3003                                              BasicBlock *InsertAtEnd) {
3004   Value *Zero = ConstantInt::get(Op->getType(), 0);
3005   return BinaryOperator::CreateNUWSub(Zero, Op, Name, InsertAtEnd);
3006 }
3007
3008 BinaryOperator *BinaryOperator::CreateNot(Value *Op, const Twine &Name,
3009                                           Instruction *InsertBefore) {
3010   Constant *C = Constant::getAllOnesValue(Op->getType());
3011   return new BinaryOperator(Instruction::Xor, Op, C,
3012                             Op->getType(), Name, InsertBefore);
3013 }
3014
3015 BinaryOperator *BinaryOperator::CreateNot(Value *Op, const Twine &Name,
3016                                           BasicBlock *InsertAtEnd) {
3017   Constant *AllOnes = Constant::getAllOnesValue(Op->getType());
3018   return new BinaryOperator(Instruction::Xor, Op, AllOnes,
3019                             Op->getType(), Name, InsertAtEnd);
3020 }
3021
3022 // Exchange the two operands to this instruction. This instruction is safe to
3023 // use on any binary instruction and does not modify the semantics of the
3024 // instruction. If the instruction is order-dependent (SetLT f.e.), the opcode
3025 // is changed.
3026 bool BinaryOperator::swapOperands() {
3027   if (!isCommutative())
3028     return true; // Can't commute operands
3029   Op<0>().swap(Op<1>());
3030   return false;
3031 }
3032
3033 //===----------------------------------------------------------------------===//
3034 //                             FPMathOperator Class
3035 //===----------------------------------------------------------------------===//
3036
3037 float FPMathOperator::getFPAccuracy() const {
3038   const MDNode *MD =
3039       cast<Instruction>(this)->getMetadata(LLVMContext::MD_fpmath);
3040   if (!MD)
3041     return 0.0;
3042   ConstantFP *Accuracy = mdconst::extract<ConstantFP>(MD->getOperand(0));
3043   return Accuracy->getValueAPF().convertToFloat();
3044 }
3045
3046 //===----------------------------------------------------------------------===//
3047 //                                CastInst Class
3048 //===----------------------------------------------------------------------===//
3049
3050 // Just determine if this cast only deals with integral->integral conversion.
3051 bool CastInst::isIntegerCast() const {
3052   switch (getOpcode()) {
3053     default: return false;
3054     case Instruction::ZExt:
3055     case Instruction::SExt:
3056     case Instruction::Trunc:
3057       return true;
3058     case Instruction::BitCast:
3059       return getOperand(0)->getType()->isIntegerTy() &&
3060         getType()->isIntegerTy();
3061   }
3062 }
3063
3064 /// This function determines if the CastInst does not require any bits to be
3065 /// changed in order to effect the cast. Essentially, it identifies cases where
3066 /// no code gen is necessary for the cast, hence the name no-op cast.  For
3067 /// example, the following are all no-op casts:
3068 /// # bitcast i32* %x to i8*
3069 /// # bitcast <2 x i32> %x to <4 x i16>
3070 /// # ptrtoint i32* %x to i32     ; on 32-bit plaforms only
3071 /// Determine if the described cast is a no-op.
3072 bool CastInst::isNoopCast(Instruction::CastOps Opcode,
3073                           Type *SrcTy,
3074                           Type *DestTy,
3075                           const DataLayout &DL) {
3076   assert(castIsValid(Opcode, SrcTy, DestTy) && "method precondition");
3077   switch (Opcode) {
3078     default: llvm_unreachable("Invalid CastOp");
3079     case Instruction::Trunc:
3080     case Instruction::ZExt:
3081     case Instruction::SExt:
3082     case Instruction::FPTrunc:
3083     case Instruction::FPExt:
3084     case Instruction::UIToFP:
3085     case Instruction::SIToFP:
3086     case Instruction::FPToUI:
3087     case Instruction::FPToSI:
3088     case Instruction::AddrSpaceCast:
3089       // TODO: Target informations may give a more accurate answer here.
3090       return false;
3091     case Instruction::BitCast:
3092       return true;  // BitCast never modifies bits.
3093     case Instruction::PtrToInt:
3094       return DL.getIntPtrType(SrcTy)->getScalarSizeInBits() ==
3095              DestTy->getScalarSizeInBits();
3096     case Instruction::IntToPtr:
3097       return DL.getIntPtrType(DestTy)->getScalarSizeInBits() ==
3098              SrcTy->getScalarSizeInBits();
3099   }
3100 }
3101
3102 bool CastInst::isNoopCast(const DataLayout &DL) const {
3103   return isNoopCast(getOpcode(), getOperand(0)->getType(), getType(), DL);
3104 }
3105
3106 /// This function determines if a pair of casts can be eliminated and what
3107 /// opcode should be used in the elimination. This assumes that there are two
3108 /// instructions like this:
3109 /// *  %F = firstOpcode SrcTy %x to MidTy
3110 /// *  %S = secondOpcode MidTy %F to DstTy
3111 /// The function returns a resultOpcode so these two casts can be replaced with:
3112 /// *  %Replacement = resultOpcode %SrcTy %x to DstTy
3113 /// If no such cast is permitted, the function returns 0.
3114 unsigned CastInst::isEliminableCastPair(
3115   Instruction::CastOps firstOp, Instruction::CastOps secondOp,
3116   Type *SrcTy, Type *MidTy, Type *DstTy, Type *SrcIntPtrTy, Type *MidIntPtrTy,
3117   Type *DstIntPtrTy) {
3118   // Define the 144 possibilities for these two cast instructions. The values
3119   // in this matrix determine what to do in a given situation and select the
3120   // case in the switch below.  The rows correspond to firstOp, the columns
3121   // correspond to secondOp.  In looking at the table below, keep in mind
3122   // the following cast properties:
3123   //
3124   //          Size Compare       Source               Destination
3125   // Operator  Src ? Size   Type       Sign         Type       Sign
3126   // -------- ------------ -------------------   ---------------------
3127   // TRUNC         >       Integer      Any        Integral     Any
3128   // ZEXT          <       Integral   Unsigned     Integer      Any
3129   // SEXT          <       Integral    Signed      Integer      Any
3130   // FPTOUI       n/a      FloatPt      n/a        Integral   Unsigned
3131   // FPTOSI       n/a      FloatPt      n/a        Integral    Signed
3132   // UITOFP       n/a      Integral   Unsigned     FloatPt      n/a
3133   // SITOFP       n/a      Integral    Signed      FloatPt      n/a
3134   // FPTRUNC       >       FloatPt      n/a        FloatPt      n/a
3135   // FPEXT         <       FloatPt      n/a        FloatPt      n/a
3136   // PTRTOINT     n/a      Pointer      n/a        Integral   Unsigned
3137   // INTTOPTR     n/a      Integral   Unsigned     Pointer      n/a
3138   // BITCAST       =       FirstClass   n/a       FirstClass    n/a
3139   // ADDRSPCST    n/a      Pointer      n/a        Pointer      n/a
3140   //
3141   // NOTE: some transforms are safe, but we consider them to be non-profitable.
3142   // For example, we could merge "fptoui double to i32" + "zext i32 to i64",
3143   // into "fptoui double to i64", but this loses information about the range
3144   // of the produced value (we no longer know the top-part is all zeros).
3145   // Further this conversion is often much more expensive for typical hardware,
3146   // and causes issues when building libgcc.  We disallow fptosi+sext for the
3147   // same reason.
3148   const unsigned numCastOps =
3149     Instruction::CastOpsEnd - Instruction::CastOpsBegin;
3150   static const uint8_t CastResults[numCastOps][numCastOps] = {
3151     // T        F  F  U  S  F  F  P  I  B  A  -+
3152     // R  Z  S  P  P  I  I  T  P  2  N  T  S   |
3153     // U  E  E  2  2  2  2  R  E  I  T  C  C   +- secondOp
3154     // N  X  X  U  S  F  F  N  X  N  2  V  V   |
3155     // C  T  T  I  I  P  P  C  T  T  P  T  T  -+
3156     {  1, 0, 0,99,99, 0, 0,99,99,99, 0, 3, 0}, // Trunc         -+
3157     {  8, 1, 9,99,99, 2,17,99,99,99, 2, 3, 0}, // ZExt           |
3158     {  8, 0, 1,99,99, 0, 2,99,99,99, 0, 3, 0}, // SExt           |
3159     {  0, 0, 0,99,99, 0, 0,99,99,99, 0, 3, 0}, // FPToUI         |
3160     {  0, 0, 0,99,99, 0, 0,99,99,99, 0, 3, 0}, // FPToSI         |
3161     { 99,99,99, 0, 0,99,99, 0, 0,99,99, 4, 0}, // UIToFP         +- firstOp
3162     { 99,99,99, 0, 0,99,99, 0, 0,99,99, 4, 0}, // SIToFP         |
3163     { 99,99,99, 0, 0,99,99, 0, 0,99,99, 4, 0}, // FPTrunc        |
3164     { 99,99,99, 2, 2,99,99, 8, 2,99,99, 4, 0}, // FPExt          |
3165     {  1, 0, 0,99,99, 0, 0,99,99,99, 7, 3, 0}, // PtrToInt       |
3166     { 99,99,99,99,99,99,99,99,99,11,99,15, 0}, // IntToPtr       |
3167     {  5, 5, 5, 6, 6, 5, 5, 6, 6,16, 5, 1,14}, // BitCast        |
3168     {  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,13,12}, // AddrSpaceCast -+
3169   };
3170
3171   // TODO: This logic could be encoded into the table above and handled in the
3172   // switch below.
3173   // If either of the casts are a bitcast from scalar to vector, disallow the
3174   // merging. However, any pair of bitcasts are allowed.
3175   bool IsFirstBitcast  = (firstOp == Instruction::BitCast);
3176   bool IsSecondBitcast = (secondOp == Instruction::BitCast);
3177   bool AreBothBitcasts = IsFirstBitcast && IsSecondBitcast;
3178
3179   // Check if any of the casts convert scalars <-> vectors.
3180   if ((IsFirstBitcast  && isa<VectorType>(SrcTy) != isa<VectorType>(MidTy)) ||
3181       (IsSecondBitcast && isa<VectorType>(MidTy) != isa<VectorType>(DstTy)))
3182     if (!AreBothBitcasts)
3183       return 0;
3184
3185   int ElimCase = CastResults[firstOp-Instruction::CastOpsBegin]
3186                             [secondOp-Instruction::CastOpsBegin];
3187   switch (ElimCase) {
3188     case 0:
3189       // Categorically disallowed.
3190       return 0;
3191     case 1:
3192       // Allowed, use first cast's opcode.
3193       return firstOp;
3194     case 2:
3195       // Allowed, use second cast's opcode.
3196       return secondOp;
3197     case 3:
3198       // No-op cast in second op implies firstOp as long as the DestTy
3199       // is integer and we are not converting between a vector and a
3200       // non-vector type.
3201       if (!SrcTy->isVectorTy() && DstTy->isIntegerTy())
3202         return firstOp;
3203       return 0;
3204     case 4:
3205       // No-op cast in second op implies firstOp as long as the DestTy
3206       // matches MidTy.
3207       if (DstTy == MidTy)
3208         return firstOp;
3209       return 0;
3210     case 5:
3211       // No-op cast in first op implies secondOp as long as the SrcTy
3212       // is an integer.
3213       if (SrcTy->isIntegerTy())
3214         return secondOp;
3215       return 0;
3216     case 6:
3217       // No-op cast in first op implies secondOp as long as the SrcTy
3218       // is a floating point.
3219       if (SrcTy->isFloatingPointTy())
3220         return secondOp;
3221       return 0;
3222     case 7: {
3223       // Disable inttoptr/ptrtoint optimization if enabled.
3224       if (DisableI2pP2iOpt)
3225         return 0;
3226
3227       // Cannot simplify if address spaces are different!
3228       if (SrcTy->getPointerAddressSpace() != DstTy->getPointerAddressSpace())
3229         return 0;
3230
3231       unsigned MidSize = MidTy->getScalarSizeInBits();
3232       // We can still fold this without knowing the actual sizes as long we
3233       // know that the intermediate pointer is the largest possible
3234       // pointer size.
3235       // FIXME: Is this always true?
3236       if (MidSize == 64)
3237         return Instruction::BitCast;
3238
3239       // ptrtoint, inttoptr -> bitcast (ptr -> ptr) if int size is >= ptr size.
3240       if (!SrcIntPtrTy || DstIntPtrTy != SrcIntPtrTy)
3241         return 0;
3242       unsigned PtrSize = SrcIntPtrTy->getScalarSizeInBits();
3243       if (MidSize >= PtrSize)
3244         return Instruction::BitCast;
3245       return 0;
3246     }
3247     case 8: {
3248       // ext, trunc -> bitcast,    if the SrcTy and DstTy are the same
3249       // ext, trunc -> ext,        if sizeof(SrcTy) < sizeof(DstTy)
3250       // ext, trunc -> trunc,      if sizeof(SrcTy) > sizeof(DstTy)
3251       unsigned SrcSize = SrcTy->getScalarSizeInBits();
3252       unsigned DstSize = DstTy->getScalarSizeInBits();
3253       if (SrcTy == DstTy)
3254         return Instruction::BitCast;
3255       if (SrcSize < DstSize)
3256         return firstOp;
3257       if (SrcSize > DstSize)
3258         return secondOp;
3259       return 0;
3260     }
3261     case 9:
3262       // zext, sext -> zext, because sext can't sign extend after zext
3263       return Instruction::ZExt;
3264     case 11: {
3265       // inttoptr, ptrtoint -> bitcast if SrcSize<=PtrSize and SrcSize==DstSize
3266       if (!MidIntPtrTy)
3267         return 0;
3268       unsigned PtrSize = MidIntPtrTy->getScalarSizeInBits();
3269       unsigned SrcSize = SrcTy->getScalarSizeInBits();
3270       unsigned DstSize = DstTy->getScalarSizeInBits();
3271       if (SrcSize <= PtrSize && SrcSize == DstSize)
3272         return Instruction::BitCast;
3273       return 0;
3274     }
3275     case 12:
3276       // addrspacecast, addrspacecast -> bitcast,       if SrcAS == DstAS
3277       // addrspacecast, addrspacecast -> addrspacecast, if SrcAS != DstAS
3278       if (SrcTy->getPointerAddressSpace() != DstTy->getPointerAddressSpace())
3279         return Instruction::AddrSpaceCast;
3280       return Instruction::BitCast;
3281     case 13:
3282       // FIXME: this state can be merged with (1), but the following assert
3283       // is useful to check the correcteness of the sequence due to semantic
3284       // change of bitcast.
3285       assert(
3286         SrcTy->isPtrOrPtrVectorTy() &&
3287         MidTy->isPtrOrPtrVectorTy() &&
3288         DstTy->isPtrOrPtrVectorTy() &&
3289         SrcTy->getPointerAddressSpace() != MidTy->getPointerAddressSpace() &&
3290         MidTy->getPointerAddressSpace() == DstTy->getPointerAddressSpace() &&
3291         "Illegal addrspacecast, bitcast sequence!");
3292       // Allowed, use first cast's opcode
3293       return firstOp;
3294     case 14:
3295       // bitcast, addrspacecast -> addrspacecast
3296       return Instruction::AddrSpaceCast;
3297     case 15:
3298       // FIXME: this state can be merged with (1), but the following assert
3299       // is useful to check the correcteness of the sequence due to semantic
3300       // change of bitcast.
3301       assert(
3302         SrcTy->isIntOrIntVectorTy() &&
3303         MidTy->isPtrOrPtrVectorTy() &&
3304         DstTy->isPtrOrPtrVectorTy() &&
3305         MidTy->getPointerAddressSpace() == DstTy->getPointerAddressSpace() &&
3306         "Illegal inttoptr, bitcast sequence!");
3307       // Allowed, use first cast's opcode
3308       return firstOp;
3309     case 16:
3310       // FIXME: this state can be merged with (2), but the following assert
3311       // is useful to check the correcteness of the sequence due to semantic
3312       // change of bitcast.
3313       assert(
3314         SrcTy->isPtrOrPtrVectorTy() &&
3315         MidTy->isPtrOrPtrVectorTy() &&
3316         DstTy->isIntOrIntVectorTy() &&
3317         SrcTy->getPointerAddressSpace() == MidTy->getPointerAddressSpace() &&
3318         "Illegal bitcast, ptrtoint sequence!");
3319       // Allowed, use second cast's opcode
3320       return secondOp;
3321     case 17:
3322       // (sitofp (zext x)) -> (uitofp x)
3323       return Instruction::UIToFP;
3324     case 99:
3325       // Cast combination can't happen (error in input). This is for all cases
3326       // where the MidTy is not the same for the two cast instructions.
3327       llvm_unreachable("Invalid Cast Combination");
3328     default:
3329       llvm_unreachable("Error in CastResults table!!!");
3330   }
3331 }
3332
3333 CastInst *CastInst::Create(Instruction::CastOps op, Value *S, Type *Ty,
3334   const Twine &Name, Instruction *InsertBefore) {
3335   assert(castIsValid(op, S, Ty) && "Invalid cast!");
3336   // Construct and return the appropriate CastInst subclass
3337   switch (op) {
3338   case Trunc:         return new TruncInst         (S, Ty, Name, InsertBefore);
3339   case ZExt:          return new ZExtInst          (S, Ty, Name, InsertBefore);
3340   case SExt:          return new SExtInst          (S, Ty, Name, InsertBefore);
3341   case FPTrunc:       return new FPTruncInst       (S, Ty, Name, InsertBefore);
3342   case FPExt:         return new FPExtInst         (S, Ty, Name, InsertBefore);
3343   case UIToFP:        return new UIToFPInst        (S, Ty, Name, InsertBefore);
3344   case SIToFP:        return new SIToFPInst        (S, Ty, Name, InsertBefore);
3345   case FPToUI:        return new FPToUIInst        (S, Ty, Name, InsertBefore);
3346   case FPToSI:        return new FPToSIInst        (S, Ty, Name, InsertBefore);
3347   case PtrToInt:      return new PtrToIntInst      (S, Ty, Name, InsertBefore);
3348   case IntToPtr:      return new IntToPtrInst      (S, Ty, Name, InsertBefore);
3349   case BitCast:       return new BitCastInst       (S, Ty, Name, InsertBefore);
3350   case AddrSpaceCast: return new AddrSpaceCastInst (S, Ty, Name, InsertBefore);
3351   default: llvm_unreachable("Invalid opcode provided");
3352   }
3353 }
3354
3355 CastInst *CastInst::Create(Instruction::CastOps op, Value *S, Type *Ty,
3356   const Twine &Name, BasicBlock *InsertAtEnd) {
3357   assert(castIsValid(op, S, Ty) && "Invalid cast!");
3358   // Construct and return the appropriate CastInst subclass
3359   switch (op) {
3360   case Trunc:         return new TruncInst         (S, Ty, Name, InsertAtEnd);
3361   case ZExt:          return new ZExtInst          (S, Ty, Name, InsertAtEnd);
3362   case SExt:          return new SExtInst          (S, Ty, Name, InsertAtEnd);
3363   case FPTrunc:       return new FPTruncInst       (S, Ty, Name, InsertAtEnd);
3364   case FPExt:         return new FPExtInst         (S, Ty, Name, InsertAtEnd);
3365   case UIToFP:        return new UIToFPInst        (S, Ty, Name, InsertAtEnd);
3366   case SIToFP:        return new SIToFPInst        (S, Ty, Name, InsertAtEnd);
3367   case FPToUI:        return new FPToUIInst        (S, Ty, Name, InsertAtEnd);
3368   case FPToSI:        return new FPToSIInst        (S, Ty, Name, InsertAtEnd);
3369   case PtrToInt:      return new PtrToIntInst      (S, Ty, Name, InsertAtEnd);
3370   case IntToPtr:      return new IntToPtrInst      (S, Ty, Name, InsertAtEnd);
3371   case BitCast:       return new BitCastInst       (S, Ty, Name, InsertAtEnd);
3372   case AddrSpaceCast: return new AddrSpaceCastInst (S, Ty, Name, InsertAtEnd);
3373   default: llvm_unreachable("Invalid opcode provided");
3374   }
3375 }
3376
3377 CastInst *CastInst::CreateZExtOrBitCast(Value *S, Type *Ty,
3378                                         const Twine &Name,
3379                                         Instruction *InsertBefore) {
3380   if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
3381     return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
3382   return Create(Instruction::ZExt, S, Ty, Name, InsertBefore);
3383 }
3384
3385 CastInst *CastInst::CreateZExtOrBitCast(Value *S, Type *Ty,
3386                                         const Twine &Name,
3387                                         BasicBlock *InsertAtEnd) {
3388   if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
3389     return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
3390   return Create(Instruction::ZExt, S, Ty, Name, InsertAtEnd);
3391 }
3392
3393 CastInst *CastInst::CreateSExtOrBitCast(Value *S, Type *Ty,
3394                                         const Twine &Name,
3395                                         Instruction *InsertBefore) {
3396   if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
3397     return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
3398   return Create(Instruction::SExt, S, Ty, Name, InsertBefore);
3399 }
3400
3401 CastInst *CastInst::CreateSExtOrBitCast(Value *S, Type *Ty,
3402                                         const Twine &Name,
3403                                         BasicBlock *InsertAtEnd) {
3404   if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
3405     return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
3406   return Create(Instruction::SExt, S, Ty, Name, InsertAtEnd);
3407 }
3408
3409 CastInst *CastInst::CreateTruncOrBitCast(Value *S, Type *Ty,
3410                                          const Twine &Name,
3411                                          Instruction *InsertBefore) {
3412   if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
3413     return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
3414   return Create(Instruction::Trunc, S, Ty, Name, InsertBefore);
3415 }
3416
3417 CastInst *CastInst::CreateTruncOrBitCast(Value *S, Type *Ty,
3418                                          const Twine &Name,
3419                                          BasicBlock *InsertAtEnd) {
3420   if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
3421     return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
3422   return Create(Instruction::Trunc, S, Ty, Name, InsertAtEnd);
3423 }
3424
3425 CastInst *CastInst::CreatePointerCast(Value *S, Type *Ty,
3426                                       const Twine &Name,
3427                                       BasicBlock *InsertAtEnd) {
3428   assert(S->getType()->isPtrOrPtrVectorTy() && "Invalid cast");
3429   assert((Ty->isIntOrIntVectorTy() || Ty->isPtrOrPtrVectorTy()) &&
3430          "Invalid cast");
3431   assert(Ty->isVectorTy() == S->getType()->isVectorTy() && "Invalid cast");
3432   assert((!Ty->isVectorTy() ||
3433           cast<VectorType>(Ty)->getElementCount() ==
3434               cast<VectorType>(S->getType())->getElementCount()) &&
3435          "Invalid cast");
3436
3437   if (Ty->isIntOrIntVectorTy())
3438     return Create(Instruction::PtrToInt, S, Ty, Name, InsertAtEnd);
3439
3440   return CreatePointerBitCastOrAddrSpaceCast(S, Ty, Name, InsertAtEnd);
3441 }
3442
3443 /// Create a BitCast or a PtrToInt cast instruction
3444 CastInst *CastInst::CreatePointerCast(Value *S, Type *Ty,
3445                                       const Twine &Name,
3446                                       Instruction *InsertBefore) {
3447   assert(S->getType()->isPtrOrPtrVectorTy() && "Invalid cast");
3448   assert((Ty->isIntOrIntVectorTy() || Ty->isPtrOrPtrVectorTy()) &&
3449          "Invalid cast");
3450   assert(Ty->isVectorTy() == S->getType()->isVectorTy() && "Invalid cast");
3451   assert((!Ty->isVectorTy() ||
3452           cast<VectorType>(Ty)->getElementCount() ==
3453               cast<VectorType>(S->getType())->getElementCount()) &&
3454          "Invalid cast");
3455
3456   if (Ty->isIntOrIntVectorTy())
3457     return Create(Instruction::PtrToInt, S, Ty, Name, InsertBefore);
3458
3459   return CreatePointerBitCastOrAddrSpaceCast(S, Ty, Name, InsertBefore);
3460 }
3461
3462 CastInst *CastInst::CreatePointerBitCastOrAddrSpaceCast(
3463   Value *S, Type *Ty,
3464   const Twine &Name,
3465   BasicBlock *InsertAtEnd) {
3466   assert(S->getType()->isPtrOrPtrVectorTy() && "Invalid cast");
3467   assert(Ty->isPtrOrPtrVectorTy() && "Invalid cast");
3468
3469   if (S->getType()->getPointerAddressSpace() != Ty->getPointerAddressSpace())
3470     return Create(Instruction::AddrSpaceCast, S, Ty, Name, InsertAtEnd);
3471
3472   return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
3473 }
3474
3475 CastInst *CastInst::CreatePointerBitCastOrAddrSpaceCast(
3476   Value *S, Type *Ty,
3477   const Twine &Name,
3478   Instruction *InsertBefore) {
3479   assert(S->getType()->isPtrOrPtrVectorTy() && "Invalid cast");
3480   assert(Ty->isPtrOrPtrVectorTy() && "Invalid cast");
3481
3482   if (S->getType()->getPointerAddressSpace() != Ty->getPointerAddressSpace())
3483     return Create(Instruction::AddrSpaceCast, S, Ty, Name, InsertBefore);
3484
3485   return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
3486 }
3487
3488 CastInst *CastInst::CreateBitOrPointerCast(Value *S, Type *Ty,
3489                                            const Twine &Name,
3490                                            Instruction *InsertBefore) {
3491   if (S->getType()->isPointerTy() && Ty->isIntegerTy())
3492     return Create(Instruction::PtrToInt, S, Ty, Name, InsertBefore);
3493   if (S->getType()->isIntegerTy() && Ty->isPointerTy())
3494     return Create(Instruction::IntToPtr, S, Ty, Name, InsertBefore);
3495
3496   return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
3497 }
3498
3499 CastInst *CastInst::CreateIntegerCast(Value *C, Type *Ty,
3500                                       bool isSigned, const Twine &Name,
3501                                       Instruction *InsertBefore) {
3502   assert(C->getType()->isIntOrIntVectorTy() && Ty->isIntOrIntVectorTy() &&
3503          "Invalid integer cast");
3504   unsigned SrcBits = C->getType()->getScalarSizeInBits();
3505   unsigned DstBits = Ty->getScalarSizeInBits();
3506   Instruction::CastOps opcode =
3507     (SrcBits == DstBits ? Instruction::BitCast :
3508      (SrcBits > DstBits ? Instruction::Trunc :
3509       (isSigned ? Instruction::SExt : Instruction::ZExt)));
3510   return Create(opcode, C, Ty, Name, InsertBefore);
3511 }
3512
3513 CastInst *CastInst::CreateIntegerCast(Value *C, Type *Ty,
3514                                       bool isSigned, const Twine &Name,
3515                                       BasicBlock *InsertAtEnd) {
3516   assert(C->getType()->isIntOrIntVectorTy() && Ty->isIntOrIntVectorTy() &&
3517          "Invalid cast");
3518   unsigned SrcBits = C->getType()->getScalarSizeInBits();
3519   unsigned DstBits = Ty->getScalarSizeInBits();
3520   Instruction::CastOps opcode =
3521     (SrcBits == DstBits ? Instruction::BitCast :
3522      (SrcBits > DstBits ? Instruction::Trunc :
3523       (isSigned ? Instruction::SExt : Instruction::ZExt)));
3524   return Create(opcode, C, Ty, Name, InsertAtEnd);
3525 }
3526
3527 CastInst *CastInst::CreateFPCast(Value *C, Type *Ty,
3528                                  const Twine &Name,
3529                                  Instruction *InsertBefore) {
3530   assert(C->getType()->isFPOrFPVectorTy() && Ty->isFPOrFPVectorTy() &&
3531          "Invalid cast");
3532   unsigned SrcBits = C->getType()->getScalarSizeInBits();
3533   unsigned DstBits = Ty->getScalarSizeInBits();
3534   Instruction::CastOps opcode =
3535     (SrcBits == DstBits ? Instruction::BitCast :
3536      (SrcBits > DstBits ? Instruction::FPTrunc : Instruction::FPExt));
3537   return Create(opcode, C, Ty, Name, InsertBefore);
3538 }
3539
3540 CastInst *CastInst::CreateFPCast(Value *C, Type *Ty,
3541                                  const Twine &Name,
3542                                  BasicBlock *InsertAtEnd) {
3543   assert(C->getType()->isFPOrFPVectorTy() && Ty->isFPOrFPVectorTy() &&
3544          "Invalid cast");
3545   unsigned SrcBits = C->getType()->getScalarSizeInBits();
3546   unsigned DstBits = Ty->getScalarSizeInBits();
3547   Instruction::CastOps opcode =
3548     (SrcBits == DstBits ? Instruction::BitCast :
3549      (SrcBits > DstBits ? Instruction::FPTrunc : Instruction::FPExt));
3550   return Create(opcode, C, Ty, Name, InsertAtEnd);
3551 }
3552
3553 bool CastInst::isBitCastable(Type *SrcTy, Type *DestTy) {
3554   if (!SrcTy->isFirstClassType() || !DestTy->isFirstClassType())
3555     return false;
3556
3557   if (SrcTy == DestTy)
3558     return true;
3559
3560   if (VectorType *SrcVecTy = dyn_cast<VectorType>(SrcTy)) {
3561     if (VectorType *DestVecTy = dyn_cast<VectorType>(DestTy)) {
3562       if (SrcVecTy->getElementCount() == DestVecTy->getElementCount()) {
3563         // An element by element cast. Valid if casting the elements is valid.
3564         SrcTy = SrcVecTy->getElementType();
3565         DestTy = DestVecTy->getElementType();
3566       }
3567     }
3568   }
3569
3570   if (PointerType *DestPtrTy = dyn_cast<PointerType>(DestTy)) {
3571     if (PointerType *SrcPtrTy = dyn_cast<PointerType>(SrcTy)) {
3572       return SrcPtrTy->getAddressSpace() == DestPtrTy->getAddressSpace();
3573     }
3574   }
3575
3576   TypeSize SrcBits = SrcTy->getPrimitiveSizeInBits();   // 0 for ptr
3577   TypeSize DestBits = DestTy->getPrimitiveSizeInBits(); // 0 for ptr
3578
3579   // Could still have vectors of pointers if the number of elements doesn't
3580   // match
3581   if (SrcBits.getKnownMinValue() == 0 || DestBits.getKnownMinValue() == 0)
3582     return false;
3583
3584   if (SrcBits != DestBits)
3585     return false;
3586
3587   if (DestTy->isX86_MMXTy() || SrcTy->isX86_MMXTy())
3588     return false;
3589
3590   return true;
3591 }
3592
3593 bool CastInst::isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy,
3594                                           const DataLayout &DL) {
3595   // ptrtoint and inttoptr are not allowed on non-integral pointers
3596   if (auto *PtrTy = dyn_cast<PointerType>(SrcTy))
3597     if (auto *IntTy = dyn_cast<IntegerType>(DestTy))
3598       return (IntTy->getBitWidth() == DL.getPointerTypeSizeInBits(PtrTy) &&
3599               !DL.isNonIntegralPointerType(PtrTy));
3600   if (auto *PtrTy = dyn_cast<PointerType>(DestTy))
3601     if (auto *IntTy = dyn_cast<IntegerType>(SrcTy))
3602       return (IntTy->getBitWidth() == DL.getPointerTypeSizeInBits(PtrTy) &&
3603               !DL.isNonIntegralPointerType(PtrTy));
3604
3605   return isBitCastable(SrcTy, DestTy);
3606 }
3607
3608 // Provide a way to get a "cast" where the cast opcode is inferred from the
3609 // types and size of the operand. This, basically, is a parallel of the
3610 // logic in the castIsValid function below.  This axiom should hold:
3611 //   castIsValid( getCastOpcode(Val, Ty), Val, Ty)
3612 // should not assert in castIsValid. In other words, this produces a "correct"
3613 // casting opcode for the arguments passed to it.
3614 Instruction::CastOps
3615 CastInst::getCastOpcode(
3616   const Value *Src, bool SrcIsSigned, Type *DestTy, bool DestIsSigned) {
3617   Type *SrcTy = Src->getType();
3618
3619   assert(SrcTy->isFirstClassType() && DestTy->isFirstClassType() &&
3620          "Only first class types are castable!");
3621
3622   if (SrcTy == DestTy)
3623     return BitCast;
3624
3625   // FIXME: Check address space sizes here
3626   if (VectorType *SrcVecTy = dyn_cast<VectorType>(SrcTy))
3627     if (VectorType *DestVecTy = dyn_cast<VectorType>(DestTy))
3628       if (SrcVecTy->getElementCount() == DestVecTy->getElementCount()) {
3629         // An element by element cast.  Find the appropriate opcode based on the
3630         // element types.
3631         SrcTy = SrcVecTy->getElementType();
3632         DestTy = DestVecTy->getElementType();
3633       }
3634
3635   // Get the bit sizes, we'll need these
3636   unsigned SrcBits = SrcTy->getPrimitiveSizeInBits();   // 0 for ptr
3637   unsigned DestBits = DestTy->getPrimitiveSizeInBits(); // 0 for ptr
3638
3639   // Run through the possibilities ...
3640   if (DestTy->isIntegerTy()) {                      // Casting to integral
3641     if (SrcTy->isIntegerTy()) {                     // Casting from integral
3642       if (DestBits < SrcBits)
3643         return Trunc;                               // int -> smaller int
3644       else if (DestBits > SrcBits) {                // its an extension
3645         if (SrcIsSigned)
3646           return SExt;                              // signed -> SEXT
3647         else
3648           return ZExt;                              // unsigned -> ZEXT
3649       } else {
3650         return BitCast;                             // Same size, No-op cast
3651       }
3652     } else if (SrcTy->isFloatingPointTy()) {        // Casting from floating pt
3653       if (DestIsSigned)
3654         return FPToSI;                              // FP -> sint
3655       else
3656         return FPToUI;                              // FP -> uint
3657     } else if (SrcTy->isVectorTy()) {
3658       assert(DestBits == SrcBits &&
3659              "Casting vector to integer of different width");
3660       return BitCast;                             // Same size, no-op cast
3661     } else {
3662       assert(SrcTy->isPointerTy() &&
3663              "Casting from a value that is not first-class type");
3664       return PtrToInt;                              // ptr -> int
3665     }
3666   } else if (DestTy->isFloatingPointTy()) {         // Casting to floating pt
3667     if (SrcTy->isIntegerTy()) {                     // Casting from integral
3668       if (SrcIsSigned)
3669         return SIToFP;                              // sint -> FP
3670       else
3671         return UIToFP;                              // uint -> FP
3672     } else if (SrcTy->isFloatingPointTy()) {        // Casting from floating pt
3673       if (DestBits < SrcBits) {
3674         return FPTrunc;                             // FP -> smaller FP
3675       } else if (DestBits > SrcBits) {
3676         return FPExt;                               // FP -> larger FP
3677       } else  {
3678         return BitCast;                             // same size, no-op cast
3679       }
3680     } else if (SrcTy->isVectorTy()) {
3681       assert(DestBits == SrcBits &&
3682              "Casting vector to floating point of different width");
3683       return BitCast;                             // same size, no-op cast
3684     }
3685     llvm_unreachable("Casting pointer or non-first class to float");
3686   } else if (DestTy->isVectorTy()) {
3687     assert(DestBits == SrcBits &&
3688            "Illegal cast to vector (wrong type or size)");
3689     return BitCast;
3690   } else if (DestTy->isPointerTy()) {
3691     if (SrcTy->isPointerTy()) {
3692       if (DestTy->getPointerAddressSpace() != SrcTy->getPointerAddressSpace())
3693         return AddrSpaceCast;
3694       return BitCast;                               // ptr -> ptr
3695     } else if (SrcTy->isIntegerTy()) {
3696       return IntToPtr;                              // int -> ptr
3697     }
3698     llvm_unreachable("Casting pointer to other than pointer or int");
3699   } else if (DestTy->isX86_MMXTy()) {
3700     if (SrcTy->isVectorTy()) {
3701       assert(DestBits == SrcBits && "Casting vector of wrong width to X86_MMX");
3702       return BitCast;                               // 64-bit vector to MMX
3703     }
3704     llvm_unreachable("Illegal cast to X86_MMX");
3705   }
3706   llvm_unreachable("Casting to type that is not first-class");
3707 }
3708
3709 //===----------------------------------------------------------------------===//
3710 //                    CastInst SubClass Constructors
3711 //===----------------------------------------------------------------------===//
3712
3713 /// Check that the construction parameters for a CastInst are correct. This
3714 /// could be broken out into the separate constructors but it is useful to have
3715 /// it in one place and to eliminate the redundant code for getting the sizes
3716 /// of the types involved.
3717 bool
3718 CastInst::castIsValid(Instruction::CastOps op, Type *SrcTy, Type *DstTy) {
3719   if (!SrcTy->isFirstClassType() || !DstTy->isFirstClassType() ||
3720       SrcTy->isAggregateType() || DstTy->isAggregateType())
3721     return false;
3722
3723   // Get the size of the types in bits, and whether we are dealing
3724   // with vector types, we'll need this later.
3725   bool SrcIsVec = isa<VectorType>(SrcTy);
3726   bool DstIsVec = isa<VectorType>(DstTy);
3727   unsigned SrcScalarBitSize = SrcTy->getScalarSizeInBits();
3728   unsigned DstScalarBitSize = DstTy->getScalarSizeInBits();
3729
3730   // If these are vector types, get the lengths of the vectors (using zero for
3731   // scalar types means that checking that vector lengths match also checks that
3732   // scalars are not being converted to vectors or vectors to scalars).
3733   ElementCount SrcEC = SrcIsVec ? cast<VectorType>(SrcTy)->getElementCount()
3734                                 : ElementCount::getFixed(0);
3735   ElementCount DstEC = DstIsVec ? cast<VectorType>(DstTy)->getElementCount()
3736                                 : ElementCount::getFixed(0);
3737
3738   // Switch on the opcode provided
3739   switch (op) {
3740   default: return false; // This is an input error
3741   case Instruction::Trunc:
3742     return SrcTy->isIntOrIntVectorTy() && DstTy->isIntOrIntVectorTy() &&
3743            SrcEC == DstEC && SrcScalarBitSize > DstScalarBitSize;
3744   case Instruction::ZExt:
3745     return SrcTy->isIntOrIntVectorTy() && DstTy->isIntOrIntVectorTy() &&
3746            SrcEC == DstEC && SrcScalarBitSize < DstScalarBitSize;
3747   case Instruction::SExt:
3748     return SrcTy->isIntOrIntVectorTy() && DstTy->isIntOrIntVectorTy() &&
3749            SrcEC == DstEC && SrcScalarBitSize < DstScalarBitSize;
3750   case Instruction::FPTrunc:
3751     return SrcTy->isFPOrFPVectorTy() && DstTy->isFPOrFPVectorTy() &&
3752            SrcEC == DstEC && SrcScalarBitSize > DstScalarBitSize;
3753   case Instruction::FPExt:
3754     return SrcTy->isFPOrFPVectorTy() && DstTy->isFPOrFPVectorTy() &&
3755            SrcEC == DstEC && SrcScalarBitSize < DstScalarBitSize;
3756   case Instruction::UIToFP:
3757   case Instruction::SIToFP:
3758     return SrcTy->isIntOrIntVectorTy() && DstTy->isFPOrFPVectorTy() &&
3759            SrcEC == DstEC;
3760   case Instruction::FPToUI:
3761   case Instruction::FPToSI:
3762     return SrcTy->isFPOrFPVectorTy() && DstTy->isIntOrIntVectorTy() &&
3763            SrcEC == DstEC;
3764   case Instruction::PtrToInt:
3765     if (SrcEC != DstEC)
3766       return false;
3767     return SrcTy->isPtrOrPtrVectorTy() && DstTy->isIntOrIntVectorTy();
3768   case Instruction::IntToPtr:
3769     if (SrcEC != DstEC)
3770       return false;
3771     return SrcTy->isIntOrIntVectorTy() && DstTy->isPtrOrPtrVectorTy();
3772   case Instruction::BitCast: {
3773     PointerType *SrcPtrTy = dyn_cast<PointerType>(SrcTy->getScalarType());
3774     PointerType *DstPtrTy = dyn_cast<PointerType>(DstTy->getScalarType());
3775
3776     // BitCast implies a no-op cast of type only. No bits change.
3777     // However, you can't cast pointers to anything but pointers.
3778     if (!SrcPtrTy != !DstPtrTy)
3779       return false;
3780
3781     // For non-pointer cases, the cast is okay if the source and destination bit
3782     // widths are identical.
3783     if (!SrcPtrTy)
3784       return SrcTy->getPrimitiveSizeInBits() == DstTy->getPrimitiveSizeInBits();
3785
3786     // If both are pointers then the address spaces must match.
3787     if (SrcPtrTy->getAddressSpace() != DstPtrTy->getAddressSpace())
3788       return false;
3789
3790     // A vector of pointers must have the same number of elements.
3791     if (SrcIsVec && DstIsVec)
3792       return SrcEC == DstEC;
3793     if (SrcIsVec)
3794       return SrcEC == ElementCount::getFixed(1);
3795     if (DstIsVec)
3796       return DstEC == ElementCount::getFixed(1);
3797
3798     return true;
3799   }
3800   case Instruction::AddrSpaceCast: {
3801     PointerType *SrcPtrTy = dyn_cast<PointerType>(SrcTy->getScalarType());
3802     if (!SrcPtrTy)
3803       return false;
3804
3805     PointerType *DstPtrTy = dyn_cast<PointerType>(DstTy->getScalarType());
3806     if (!DstPtrTy)
3807       return false;
3808
3809     if (SrcPtrTy->getAddressSpace() == DstPtrTy->getAddressSpace())
3810       return false;
3811
3812     return SrcEC == DstEC;
3813   }
3814   }
3815 }
3816
3817 TruncInst::TruncInst(
3818   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3819 ) : CastInst(Ty, Trunc, S, Name, InsertBefore) {
3820   assert(castIsValid(getOpcode(), S, Ty) && "Illegal Trunc");
3821 }
3822
3823 TruncInst::TruncInst(
3824   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3825 ) : CastInst(Ty, Trunc, S, Name, InsertAtEnd) {
3826   assert(castIsValid(getOpcode(), S, Ty) && "Illegal Trunc");
3827 }
3828
3829 ZExtInst::ZExtInst(
3830   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3831 )  : CastInst(Ty, ZExt, S, Name, InsertBefore) {
3832   assert(castIsValid(getOpcode(), S, Ty) && "Illegal ZExt");
3833 }
3834
3835 ZExtInst::ZExtInst(
3836   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3837 )  : CastInst(Ty, ZExt, S, Name, InsertAtEnd) {
3838   assert(castIsValid(getOpcode(), S, Ty) && "Illegal ZExt");
3839 }
3840 SExtInst::SExtInst(
3841   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3842 ) : CastInst(Ty, SExt, S, Name, InsertBefore) {
3843   assert(castIsValid(getOpcode(), S, Ty) && "Illegal SExt");
3844 }
3845
3846 SExtInst::SExtInst(
3847   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3848 )  : CastInst(Ty, SExt, S, Name, InsertAtEnd) {
3849   assert(castIsValid(getOpcode(), S, Ty) && "Illegal SExt");
3850 }
3851
3852 FPTruncInst::FPTruncInst(
3853   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3854 ) : CastInst(Ty, FPTrunc, S, Name, InsertBefore) {
3855   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPTrunc");
3856 }
3857
3858 FPTruncInst::FPTruncInst(
3859   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3860 ) : CastInst(Ty, FPTrunc, S, Name, InsertAtEnd) {
3861   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPTrunc");
3862 }
3863
3864 FPExtInst::FPExtInst(
3865   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3866 ) : CastInst(Ty, FPExt, S, Name, InsertBefore) {
3867   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPExt");
3868 }
3869
3870 FPExtInst::FPExtInst(
3871   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3872 ) : CastInst(Ty, FPExt, S, Name, InsertAtEnd) {
3873   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPExt");
3874 }
3875
3876 UIToFPInst::UIToFPInst(
3877   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3878 ) : CastInst(Ty, UIToFP, S, Name, InsertBefore) {
3879   assert(castIsValid(getOpcode(), S, Ty) && "Illegal UIToFP");
3880 }
3881
3882 UIToFPInst::UIToFPInst(
3883   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3884 ) : CastInst(Ty, UIToFP, S, Name, InsertAtEnd) {
3885   assert(castIsValid(getOpcode(), S, Ty) && "Illegal UIToFP");
3886 }
3887
3888 SIToFPInst::SIToFPInst(
3889   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3890 ) : CastInst(Ty, SIToFP, S, Name, InsertBefore) {
3891   assert(castIsValid(getOpcode(), S, Ty) && "Illegal SIToFP");
3892 }
3893
3894 SIToFPInst::SIToFPInst(
3895   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3896 ) : CastInst(Ty, SIToFP, S, Name, InsertAtEnd) {
3897   assert(castIsValid(getOpcode(), S, Ty) && "Illegal SIToFP");
3898 }
3899
3900 FPToUIInst::FPToUIInst(
3901   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3902 ) : CastInst(Ty, FPToUI, S, Name, InsertBefore) {
3903   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToUI");
3904 }
3905
3906 FPToUIInst::FPToUIInst(
3907   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3908 ) : CastInst(Ty, FPToUI, S, Name, InsertAtEnd) {
3909   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToUI");
3910 }
3911
3912 FPToSIInst::FPToSIInst(
3913   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3914 ) : CastInst(Ty, FPToSI, S, Name, InsertBefore) {
3915   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToSI");
3916 }
3917
3918 FPToSIInst::FPToSIInst(
3919   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3920 ) : CastInst(Ty, FPToSI, S, Name, InsertAtEnd) {
3921   assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToSI");
3922 }
3923
3924 PtrToIntInst::PtrToIntInst(
3925   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3926 ) : CastInst(Ty, PtrToInt, S, Name, InsertBefore) {
3927   assert(castIsValid(getOpcode(), S, Ty) && "Illegal PtrToInt");
3928 }
3929
3930 PtrToIntInst::PtrToIntInst(
3931   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3932 ) : CastInst(Ty, PtrToInt, S, Name, InsertAtEnd) {
3933   assert(castIsValid(getOpcode(), S, Ty) && "Illegal PtrToInt");
3934 }
3935
3936 IntToPtrInst::IntToPtrInst(
3937   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3938 ) : CastInst(Ty, IntToPtr, S, Name, InsertBefore) {
3939   assert(castIsValid(getOpcode(), S, Ty) && "Illegal IntToPtr");
3940 }
3941
3942 IntToPtrInst::IntToPtrInst(
3943   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3944 ) : CastInst(Ty, IntToPtr, S, Name, InsertAtEnd) {
3945   assert(castIsValid(getOpcode(), S, Ty) && "Illegal IntToPtr");
3946 }
3947
3948 BitCastInst::BitCastInst(
3949   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3950 ) : CastInst(Ty, BitCast, S, Name, InsertBefore) {
3951   assert(castIsValid(getOpcode(), S, Ty) && "Illegal BitCast");
3952 }
3953
3954 BitCastInst::BitCastInst(
3955   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3956 ) : CastInst(Ty, BitCast, S, Name, InsertAtEnd) {
3957   assert(castIsValid(getOpcode(), S, Ty) && "Illegal BitCast");
3958 }
3959
3960 AddrSpaceCastInst::AddrSpaceCastInst(
3961   Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
3962 ) : CastInst(Ty, AddrSpaceCast, S, Name, InsertBefore) {
3963   assert(castIsValid(getOpcode(), S, Ty) && "Illegal AddrSpaceCast");
3964 }
3965
3966 AddrSpaceCastInst::AddrSpaceCastInst(
3967   Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
3968 ) : CastInst(Ty, AddrSpaceCast, S, Name, InsertAtEnd) {
3969   assert(castIsValid(getOpcode(), S, Ty) && "Illegal AddrSpaceCast");
3970 }
3971
3972 //===----------------------------------------------------------------------===//
3973 //                               CmpInst Classes
3974 //===----------------------------------------------------------------------===//
3975
3976 CmpInst::CmpInst(Type *ty, OtherOps op, Predicate predicate, Value *LHS,
3977                  Value *RHS, const Twine &Name, Instruction *InsertBefore,
3978                  Instruction *FlagsSource)
3979   : Instruction(ty, op,
3980                 OperandTraits<CmpInst>::op_begin(this),
3981                 OperandTraits<CmpInst>::operands(this),
3982                 InsertBefore) {
3983   Op<0>() = LHS;
3984   Op<1>() = RHS;
3985   setPredicate((Predicate)predicate);
3986   setName(Name);
3987   if (FlagsSource)
3988     copyIRFlags(FlagsSource);
3989 }
3990
3991 CmpInst::CmpInst(Type *ty, OtherOps op, Predicate predicate, Value *LHS,
3992                  Value *RHS, const Twine &Name, BasicBlock *InsertAtEnd)
3993   : Instruction(ty, op,
3994                 OperandTraits<CmpInst>::op_begin(this),
3995                 OperandTraits<CmpInst>::operands(this),
3996                 InsertAtEnd) {
3997   Op<0>() = LHS;
3998   Op<1>() = RHS;
3999   setPredicate((Predicate)predicate);
4000   setName(Name);
4001 }
4002
4003 CmpInst *
4004 CmpInst::Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2,
4005                 const Twine &Name, Instruction *InsertBefore) {
4006   if (Op == Instruction::ICmp) {
4007     if (InsertBefore)
4008       return new ICmpInst(InsertBefore, CmpInst::Predicate(predicate),
4009                           S1, S2, Name);
4010     else
4011       return new ICmpInst(CmpInst::Predicate(predicate),
4012                           S1, S2, Name);
4013   }
4014
4015   if (InsertBefore)
4016     return new FCmpInst(InsertBefore, CmpInst::Predicate(predicate),
4017                         S1, S2, Name);
4018   else
4019     return new FCmpInst(CmpInst::Predicate(predicate),
4020                         S1, S2, Name);
4021 }
4022
4023 CmpInst *
4024 CmpInst::Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2,
4025                 const Twine &Name, BasicBlock *InsertAtEnd) {
4026   if (Op == Instruction::ICmp) {
4027     return new ICmpInst(*InsertAtEnd, CmpInst::Predicate(predicate),
4028                         S1, S2, Name);
4029   }
4030   return new FCmpInst(*InsertAtEnd, CmpInst::Predicate(predicate),
4031                       S1, S2, Name);
4032 }
4033
4034 void CmpInst::swapOperands() {
4035   if (ICmpInst *IC = dyn_cast<ICmpInst>(this))
4036     IC->swapOperands();
4037   else
4038     cast<FCmpInst>(this)->swapOperands();
4039 }
4040
4041 bool CmpInst::isCommutative() const {
4042   if (const ICmpInst *IC = dyn_cast<ICmpInst>(this))
4043     return IC->isCommutative();
4044   return cast<FCmpInst>(this)->isCommutative();
4045 }
4046
4047 bool CmpInst::isEquality(Predicate P) {
4048   if (ICmpInst::isIntPredicate(P))
4049     return ICmpInst::isEquality(P);
4050   if (FCmpInst::isFPPredicate(P))
4051     return FCmpInst::isEquality(P);
4052   llvm_unreachable("Unsupported predicate kind");
4053 }
4054
4055 CmpInst::Predicate CmpInst::getInversePredicate(Predicate pred) {
4056   switch (pred) {
4057     default: llvm_unreachable("Unknown cmp predicate!");
4058     case ICMP_EQ: return ICMP_NE;
4059     case ICMP_NE: return ICMP_EQ;
4060     case ICMP_UGT: return ICMP_ULE;
4061     case ICMP_ULT: return ICMP_UGE;
4062     case ICMP_UGE: return ICMP_ULT;
4063     case ICMP_ULE: return ICMP_UGT;
4064     case ICMP_SGT: return ICMP_SLE;
4065     case ICMP_SLT: return ICMP_SGE;
4066     case ICMP_SGE: return ICMP_SLT;
4067     case ICMP_SLE: return ICMP_SGT;
4068
4069     case FCMP_OEQ: return FCMP_UNE;
4070     case FCMP_ONE: return FCMP_UEQ;
4071     case FCMP_OGT: return FCMP_ULE;
4072     case FCMP_OLT: return FCMP_UGE;
4073     case FCMP_OGE: return FCMP_ULT;
4074     case FCMP_OLE: return FCMP_UGT;
4075     case FCMP_UEQ: return FCMP_ONE;
4076     case FCMP_UNE: return FCMP_OEQ;
4077     case FCMP_UGT: return FCMP_OLE;
4078     case FCMP_ULT: return FCMP_OGE;
4079     case FCMP_UGE: return FCMP_OLT;
4080     case FCMP_ULE: return FCMP_OGT;
4081     case FCMP_ORD: return FCMP_UNO;
4082     case FCMP_UNO: return FCMP_ORD;
4083     case FCMP_TRUE: return FCMP_FALSE;
4084     case FCMP_FALSE: return FCMP_TRUE;
4085   }
4086 }
4087
4088 StringRef CmpInst::getPredicateName(Predicate Pred) {
4089   switch (Pred) {
4090   default:                   return "unknown";
4091   case FCmpInst::FCMP_FALSE: return "false";
4092   case FCmpInst::FCMP_OEQ:   return "oeq";
4093   case FCmpInst::FCMP_OGT:   return "ogt";
4094   case FCmpInst::FCMP_OGE:   return "oge";
4095   case FCmpInst::FCMP_OLT:   return "olt";
4096   case FCmpInst::FCMP_OLE:   return "ole";
4097   case FCmpInst::FCMP_ONE:   return "one";
4098   case FCmpInst::FCMP_ORD:   return "ord";
4099   case FCmpInst::FCMP_UNO:   return "uno";
4100   case FCmpInst::FCMP_UEQ:   return "ueq";
4101   case FCmpInst::FCMP_UGT:   return "ugt";
4102   case FCmpInst::FCMP_UGE:   return "uge";
4103   case FCmpInst::FCMP_ULT:   return "ult";
4104   case FCmpInst::FCMP_ULE:   return "ule";
4105   case FCmpInst::FCMP_UNE:   return "une";
4106   case FCmpInst::FCMP_TRUE:  return "true";
4107   case ICmpInst::ICMP_EQ:    return "eq";
4108   case ICmpInst::ICMP_NE:    return "ne";
4109   case ICmpInst::ICMP_SGT:   return "sgt";
4110   case ICmpInst::ICMP_SGE:   return "sge";
4111   case ICmpInst::ICMP_SLT:   return "slt";
4112   case ICmpInst::ICMP_SLE:   return "sle";
4113   case ICmpInst::ICMP_UGT:   return "ugt";
4114   case ICmpInst::ICMP_UGE:   return "uge";
4115   case ICmpInst::ICMP_ULT:   return "ult";
4116   case ICmpInst::ICMP_ULE:   return "ule";
4117   }
4118 }
4119
4120 raw_ostream &llvm::operator<<(raw_ostream &OS, CmpInst::Predicate Pred) {
4121   OS << CmpInst::getPredicateName(Pred);
4122   return OS;
4123 }
4124
4125 ICmpInst::Predicate ICmpInst::getSignedPredicate(Predicate pred) {
4126   switch (pred) {
4127     default: llvm_unreachable("Unknown icmp predicate!");
4128     case ICMP_EQ: case ICMP_NE:
4129     case ICMP_SGT: case ICMP_SLT: case ICMP_SGE: case ICMP_SLE:
4130        return pred;
4131     case ICMP_UGT: return ICMP_SGT;
4132     case ICMP_ULT: return ICMP_SLT;
4133     case ICMP_UGE: return ICMP_SGE;
4134     case ICMP_ULE: return ICMP_SLE;
4135   }
4136 }
4137
4138 ICmpInst::Predicate ICmpInst::getUnsignedPredicate(Predicate pred) {
4139   switch (pred) {
4140     default: llvm_unreachable("Unknown icmp predicate!");
4141     case ICMP_EQ: case ICMP_NE:
4142     case ICMP_UGT: case ICMP_ULT: case ICMP_UGE: case ICMP_ULE:
4143        return pred;
4144     case ICMP_SGT: return ICMP_UGT;
4145     case ICMP_SLT: return ICMP_ULT;
4146     case ICMP_SGE: return ICMP_UGE;
4147     case ICMP_SLE: return ICMP_ULE;
4148   }
4149 }
4150
4151 CmpInst::Predicate CmpInst::getSwappedPredicate(Predicate pred) {
4152   switch (pred) {
4153     default: llvm_unreachable("Unknown cmp predicate!");
4154     case ICMP_EQ: case ICMP_NE:
4155       return pred;
4156     case ICMP_SGT: return ICMP_SLT;
4157     case ICMP_SLT: return ICMP_SGT;
4158     case ICMP_SGE: return ICMP_SLE;
4159     case ICMP_SLE: return ICMP_SGE;
4160     case ICMP_UGT: return ICMP_ULT;
4161     case ICMP_ULT: return ICMP_UGT;
4162     case ICMP_UGE: return ICMP_ULE;
4163     case ICMP_ULE: return ICMP_UGE;
4164
4165     case FCMP_FALSE: case FCMP_TRUE:
4166     case FCMP_OEQ: case FCMP_ONE:
4167     case FCMP_UEQ: case FCMP_UNE:
4168     case FCMP_ORD: case FCMP_UNO:
4169       return pred;
4170     case FCMP_OGT: return FCMP_OLT;
4171     case FCMP_OLT: return FCMP_OGT;
4172     case FCMP_OGE: return FCMP_OLE;
4173     case FCMP_OLE: return FCMP_OGE;
4174     case FCMP_UGT: return FCMP_ULT;
4175     case FCMP_ULT: return FCMP_UGT;
4176     case FCMP_UGE: return FCMP_ULE;
4177     case FCMP_ULE: return FCMP_UGE;
4178   }
4179 }
4180
4181 bool CmpInst::isNonStrictPredicate(Predicate pred) {
4182   switch (pred) {
4183   case ICMP_SGE:
4184   case ICMP_SLE:
4185   case ICMP_UGE:
4186   case ICMP_ULE:
4187   case FCMP_OGE:
4188   case FCMP_OLE:
4189   case FCMP_UGE:
4190   case FCMP_ULE:
4191     return true;
4192   default:
4193     return false;
4194   }
4195 }
4196
4197 bool CmpInst::isStrictPredicate(Predicate pred) {
4198   switch (pred) {
4199   case ICMP_SGT:
4200   case ICMP_SLT:
4201   case ICMP_UGT:
4202   case ICMP_ULT:
4203   case FCMP_OGT:
4204   case FCMP_OLT:
4205   case FCMP_UGT:
4206   case FCMP_ULT:
4207     return true;
4208   default:
4209     return false;
4210   }
4211 }
4212
4213 CmpInst::Predicate CmpInst::getStrictPredicate(Predicate pred) {
4214   switch (pred) {
4215   case ICMP_SGE:
4216     return ICMP_SGT;
4217   case ICMP_SLE:
4218     return ICMP_SLT;
4219   case ICMP_UGE:
4220     return ICMP_UGT;
4221   case ICMP_ULE:
4222     return ICMP_ULT;
4223   case FCMP_OGE:
4224     return FCMP_OGT;
4225   case FCMP_OLE:
4226     return FCMP_OLT;
4227   case FCMP_UGE:
4228     return FCMP_UGT;
4229   case FCMP_ULE:
4230     return FCMP_ULT;
4231   default:
4232     return pred;
4233   }
4234 }
4235
4236 CmpInst::Predicate CmpInst::getNonStrictPredicate(Predicate pred) {
4237   switch (pred) {
4238   case ICMP_SGT:
4239     return ICMP_SGE;
4240   case ICMP_SLT:
4241     return ICMP_SLE;
4242   case ICMP_UGT:
4243     return ICMP_UGE;
4244   case ICMP_ULT:
4245     return ICMP_ULE;
4246   case FCMP_OGT:
4247     return FCMP_OGE;
4248   case FCMP_OLT:
4249     return FCMP_OLE;
4250   case FCMP_UGT:
4251     return FCMP_UGE;
4252   case FCMP_ULT:
4253     return FCMP_ULE;
4254   default:
4255     return pred;
4256   }
4257 }
4258
4259 CmpInst::Predicate CmpInst::getFlippedStrictnessPredicate(Predicate pred) {
4260   assert(CmpInst::isRelational(pred) && "Call only with relational predicate!");
4261
4262   if (isStrictPredicate(pred))
4263     return getNonStrictPredicate(pred);
4264   if (isNonStrictPredicate(pred))
4265     return getStrictPredicate(pred);
4266
4267   llvm_unreachable("Unknown predicate!");
4268 }
4269
4270 CmpInst::Predicate CmpInst::getSignedPredicate(Predicate pred) {
4271   assert(CmpInst::isUnsigned(pred) && "Call only with unsigned predicates!");
4272
4273   switch (pred) {
4274   default:
4275     llvm_unreachable("Unknown predicate!");
4276   case CmpInst::ICMP_ULT:
4277     return CmpInst::ICMP_SLT;
4278   case CmpInst::ICMP_ULE:
4279     return CmpInst::ICMP_SLE;
4280   case CmpInst::ICMP_UGT:
4281     return CmpInst::ICMP_SGT;
4282   case CmpInst::ICMP_UGE:
4283     return CmpInst::ICMP_SGE;
4284   }
4285 }
4286
4287 CmpInst::Predicate CmpInst::getUnsignedPredicate(Predicate pred) {
4288   assert(CmpInst::isSigned(pred) && "Call only with signed predicates!");
4289
4290   switch (pred) {
4291   default:
4292     llvm_unreachable("Unknown predicate!");
4293   case CmpInst::ICMP_SLT:
4294     return CmpInst::ICMP_ULT;
4295   case CmpInst::ICMP_SLE:
4296     return CmpInst::ICMP_ULE;
4297   case CmpInst::ICMP_SGT:
4298     return CmpInst::ICMP_UGT;
4299   case CmpInst::ICMP_SGE:
4300     return CmpInst::ICMP_UGE;
4301   }
4302 }
4303
4304 bool CmpInst::isUnsigned(Predicate predicate) {
4305   switch (predicate) {
4306     default: return false;
4307     case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: case ICmpInst::ICMP_UGT:
4308     case ICmpInst::ICMP_UGE: return true;
4309   }
4310 }
4311
4312 bool CmpInst::isSigned(Predicate predicate) {
4313   switch (predicate) {
4314     default: return false;
4315     case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: case ICmpInst::ICMP_SGT:
4316     case ICmpInst::ICMP_SGE: return true;
4317   }
4318 }
4319
4320 bool ICmpInst::compare(const APInt &LHS, const APInt &RHS,
4321                        ICmpInst::Predicate Pred) {
4322   assert(ICmpInst::isIntPredicate(Pred) && "Only for integer predicates!");
4323   switch (Pred) {
4324   case ICmpInst::Predicate::ICMP_EQ:
4325     return LHS.eq(RHS);
4326   case ICmpInst::Predicate::ICMP_NE:
4327     return LHS.ne(RHS);
4328   case ICmpInst::Predicate::ICMP_UGT:
4329     return LHS.ugt(RHS);
4330   case ICmpInst::Predicate::ICMP_UGE:
4331     return LHS.uge(RHS);
4332   case ICmpInst::Predicate::ICMP_ULT:
4333     return LHS.ult(RHS);
4334   case ICmpInst::Predicate::ICMP_ULE:
4335     return LHS.ule(RHS);
4336   case ICmpInst::Predicate::ICMP_SGT:
4337     return LHS.sgt(RHS);
4338   case ICmpInst::Predicate::ICMP_SGE:
4339     return LHS.sge(RHS);
4340   case ICmpInst::Predicate::ICMP_SLT:
4341     return LHS.slt(RHS);
4342   case ICmpInst::Predicate::ICMP_SLE:
4343     return LHS.sle(RHS);
4344   default:
4345     llvm_unreachable("Unexpected non-integer predicate.");
4346   };
4347 }
4348
4349 bool FCmpInst::compare(const APFloat &LHS, const APFloat &RHS,
4350                        FCmpInst::Predicate Pred) {
4351   APFloat::cmpResult R = LHS.compare(RHS);
4352   switch (Pred) {
4353   default:
4354     llvm_unreachable("Invalid FCmp Predicate");
4355   case FCmpInst::FCMP_FALSE:
4356     return false;
4357   case FCmpInst::FCMP_TRUE:
4358     return true;
4359   case FCmpInst::FCMP_UNO:
4360     return R == APFloat::cmpUnordered;
4361   case FCmpInst::FCMP_ORD:
4362     return R != APFloat::cmpUnordered;
4363   case FCmpInst::FCMP_UEQ:
4364     return R == APFloat::cmpUnordered || R == APFloat::cmpEqual;
4365   case FCmpInst::FCMP_OEQ:
4366     return R == APFloat::cmpEqual;
4367   case FCmpInst::FCMP_UNE:
4368     return R != APFloat::cmpEqual;
4369   case FCmpInst::FCMP_ONE:
4370     return R == APFloat::cmpLessThan || R == APFloat::cmpGreaterThan;
4371   case FCmpInst::FCMP_ULT:
4372     return R == APFloat::cmpUnordered || R == APFloat::cmpLessThan;
4373   case FCmpInst::FCMP_OLT:
4374     return R == APFloat::cmpLessThan;
4375   case FCmpInst::FCMP_UGT:
4376     return R == APFloat::cmpUnordered || R == APFloat::cmpGreaterThan;
4377   case FCmpInst::FCMP_OGT:
4378     return R == APFloat::cmpGreaterThan;
4379   case FCmpInst::FCMP_ULE:
4380     return R != APFloat::cmpGreaterThan;
4381   case FCmpInst::FCMP_OLE:
4382     return R == APFloat::cmpLessThan || R == APFloat::cmpEqual;
4383   case FCmpInst::FCMP_UGE:
4384     return R != APFloat::cmpLessThan;
4385   case FCmpInst::FCMP_OGE:
4386     return R == APFloat::cmpGreaterThan || R == APFloat::cmpEqual;
4387   }
4388 }
4389
4390 CmpInst::Predicate CmpInst::getFlippedSignednessPredicate(Predicate pred) {
4391   assert(CmpInst::isRelational(pred) &&
4392          "Call only with non-equality predicates!");
4393
4394   if (isSigned(pred))
4395     return getUnsignedPredicate(pred);
4396   if (isUnsigned(pred))
4397     return getSignedPredicate(pred);
4398
4399   llvm_unreachable("Unknown predicate!");
4400 }
4401
4402 bool CmpInst::isOrdered(Predicate predicate) {
4403   switch (predicate) {
4404     default: return false;
4405     case FCmpInst::FCMP_OEQ: case FCmpInst::FCMP_ONE: case FCmpInst::FCMP_OGT:
4406     case FCmpInst::FCMP_OLT: case FCmpInst::FCMP_OGE: case FCmpInst::FCMP_OLE:
4407     case FCmpInst::FCMP_ORD: return true;
4408   }
4409 }
4410
4411 bool CmpInst::isUnordered(Predicate predicate) {
4412   switch (predicate) {
4413     default: return false;
4414     case FCmpInst::FCMP_UEQ: case FCmpInst::FCMP_UNE: case FCmpInst::FCMP_UGT:
4415     case FCmpInst::FCMP_ULT: case FCmpInst::FCMP_UGE: case FCmpInst::FCMP_ULE:
4416     case FCmpInst::FCMP_UNO: return true;
4417   }
4418 }
4419
4420 bool CmpInst::isTrueWhenEqual(Predicate predicate) {
4421   switch(predicate) {
4422     default: return false;
4423     case ICMP_EQ:   case ICMP_UGE: case ICMP_ULE: case ICMP_SGE: case ICMP_SLE:
4424     case FCMP_TRUE: case FCMP_UEQ: case FCMP_UGE: case FCMP_ULE: return true;
4425   }
4426 }
4427
4428 bool CmpInst::isFalseWhenEqual(Predicate predicate) {
4429   switch(predicate) {
4430   case ICMP_NE:    case ICMP_UGT: case ICMP_ULT: case ICMP_SGT: case ICMP_SLT:
4431   case FCMP_FALSE: case FCMP_ONE: case FCMP_OGT: case FCMP_OLT: return true;
4432   default: return false;
4433   }
4434 }
4435
4436 bool CmpInst::isImpliedTrueByMatchingCmp(Predicate Pred1, Predicate Pred2) {
4437   // If the predicates match, then we know the first condition implies the
4438   // second is true.
4439   if (Pred1 == Pred2)
4440     return true;
4441
4442   switch (Pred1) {
4443   default:
4444     break;
4445   case ICMP_EQ:
4446     // A == B implies A >=u B, A <=u B, A >=s B, and A <=s B are true.
4447     return Pred2 == ICMP_UGE || Pred2 == ICMP_ULE || Pred2 == ICMP_SGE ||
4448            Pred2 == ICMP_SLE;
4449   case ICMP_UGT: // A >u B implies A != B and A >=u B are true.
4450     return Pred2 == ICMP_NE || Pred2 == ICMP_UGE;
4451   case ICMP_ULT: // A <u B implies A != B and A <=u B are true.
4452     return Pred2 == ICMP_NE || Pred2 == ICMP_ULE;
4453   case ICMP_SGT: // A >s B implies A != B and A >=s B are true.
4454     return Pred2 == ICMP_NE || Pred2 == ICMP_SGE;
4455   case ICMP_SLT: // A <s B implies A != B and A <=s B are true.
4456     return Pred2 == ICMP_NE || Pred2 == ICMP_SLE;
4457   }
4458   return false;
4459 }
4460
4461 bool CmpInst::isImpliedFalseByMatchingCmp(Predicate Pred1, Predicate Pred2) {
4462   return isImpliedTrueByMatchingCmp(Pred1, getInversePredicate(Pred2));
4463 }
4464
4465 //===----------------------------------------------------------------------===//
4466 //                        SwitchInst Implementation
4467 //===----------------------------------------------------------------------===//
4468
4469 void SwitchInst::init(Value *Value, BasicBlock *Default, unsigned NumReserved) {
4470   assert(Value && Default && NumReserved);
4471   ReservedSpace = NumReserved;
4472   setNumHungOffUseOperands(2);
4473   allocHungoffUses(ReservedSpace);
4474
4475   Op<0>() = Value;
4476   Op<1>() = Default;
4477 }
4478
4479 /// SwitchInst ctor - Create a new switch instruction, specifying a value to
4480 /// switch on and a default destination.  The number of additional cases can
4481 /// be specified here to make memory allocation more efficient.  This
4482 /// constructor can also autoinsert before another instruction.
4483 SwitchInst::SwitchInst(Value *Value, BasicBlock *Default, unsigned NumCases,
4484                        Instruction *InsertBefore)
4485     : Instruction(Type::getVoidTy(Value->getContext()), Instruction::Switch,
4486                   nullptr, 0, InsertBefore) {
4487   init(Value, Default, 2+NumCases*2);
4488 }
4489
4490 /// SwitchInst ctor - Create a new switch instruction, specifying a value to
4491 /// switch on and a default destination.  The number of additional cases can
4492 /// be specified here to make memory allocation more efficient.  This
4493 /// constructor also autoinserts at the end of the specified BasicBlock.
4494 SwitchInst::SwitchInst(Value *Value, BasicBlock *Default, unsigned NumCases,
4495                        BasicBlock *InsertAtEnd)
4496     : Instruction(Type::getVoidTy(Value->getContext()), Instruction::Switch,
4497                   nullptr, 0, InsertAtEnd) {
4498   init(Value, Default, 2+NumCases*2);
4499 }
4500
4501 SwitchInst::SwitchInst(const SwitchInst &SI)
4502     : Instruction(SI.getType(), Instruction::Switch, nullptr, 0) {
4503   init(SI.getCondition(), SI.getDefaultDest(), SI.getNumOperands());
4504   setNumHungOffUseOperands(SI.getNumOperands());
4505   Use *OL = getOperandList();
4506   const Use *InOL = SI.getOperandList();
4507   for (unsigned i = 2, E = SI.getNumOperands(); i != E; i += 2) {
4508     OL[i] = InOL[i];
4509     OL[i+1] = InOL[i+1];
4510   }
4511   SubclassOptionalData = SI.SubclassOptionalData;
4512 }
4513
4514 /// addCase - Add an entry to the switch instruction...
4515 ///
4516 void SwitchInst::addCase(ConstantInt *OnVal, BasicBlock *Dest) {
4517   unsigned NewCaseIdx = getNumCases();
4518   unsigned OpNo = getNumOperands();
4519   if (OpNo+2 > ReservedSpace)
4520     growOperands();  // Get more space!
4521   // Initialize some new operands.
4522   assert(OpNo+1 < ReservedSpace && "Growing didn't work!");
4523   setNumHungOffUseOperands(OpNo+2);
4524   CaseHandle Case(this, NewCaseIdx);
4525   Case.setValue(OnVal);
4526   Case.setSuccessor(Dest);
4527 }
4528
4529 /// removeCase - This method removes the specified case and its successor
4530 /// from the switch instruction.
4531 SwitchInst::CaseIt SwitchInst::removeCase(CaseIt I) {
4532   unsigned idx = I->getCaseIndex();
4533
4534   assert(2 + idx*2 < getNumOperands() && "Case index out of range!!!");
4535
4536   unsigned NumOps = getNumOperands();
4537   Use *OL = getOperandList();
4538
4539   // Overwrite this case with the end of the list.
4540   if (2 + (idx + 1) * 2 != NumOps) {
4541     OL[2 + idx * 2] = OL[NumOps - 2];
4542     OL[2 + idx * 2 + 1] = OL[NumOps - 1];
4543   }
4544
4545   // Nuke the last value.
4546   OL[NumOps-2].set(nullptr);
4547   OL[NumOps-2+1].set(nullptr);
4548   setNumHungOffUseOperands(NumOps-2);
4549
4550   return CaseIt(this, idx);
4551 }
4552
4553 /// growOperands - grow operands - This grows the operand list in response
4554 /// to a push_back style of operation.  This grows the number of ops by 3 times.
4555 ///
4556 void SwitchInst::growOperands() {
4557   unsigned e = getNumOperands();
4558   unsigned NumOps = e*3;
4559
4560   ReservedSpace = NumOps;
4561   growHungoffUses(ReservedSpace);
4562 }
4563
4564 MDNode *SwitchInstProfUpdateWrapper::buildProfBranchWeightsMD() {
4565   assert(Changed && "called only if metadata has changed");
4566
4567   if (!Weights)
4568     return nullptr;
4569
4570   assert(SI.getNumSuccessors() == Weights->size() &&
4571          "num of prof branch_weights must accord with num of successors");
4572
4573   bool AllZeroes = all_of(*Weights, [](uint32_t W) { return W == 0; });
4574
4575   if (AllZeroes || Weights->size() < 2)
4576     return nullptr;
4577
4578   return MDBuilder(SI.getParent()->getContext()).createBranchWeights(*Weights);
4579 }
4580
4581 void SwitchInstProfUpdateWrapper::init() {
4582   MDNode *ProfileData = getBranchWeightMDNode(SI);
4583   if (!ProfileData)
4584     return;
4585
4586   if (ProfileData->getNumOperands() != SI.getNumSuccessors() + 1) {
4587     llvm_unreachable("number of prof branch_weights metadata operands does "
4588                      "not correspond to number of succesors");
4589   }
4590
4591   SmallVector<uint32_t, 8> Weights;
4592   if (!extractBranchWeights(ProfileData, Weights))
4593     return;
4594   this->Weights = std::move(Weights);
4595 }
4596
4597 SwitchInst::CaseIt
4598 SwitchInstProfUpdateWrapper::removeCase(SwitchInst::CaseIt I) {
4599   if (Weights) {
4600     assert(SI.getNumSuccessors() == Weights->size() &&
4601            "num of prof branch_weights must accord with num of successors");
4602     Changed = true;
4603     // Copy the last case to the place of the removed one and shrink.
4604     // This is tightly coupled with the way SwitchInst::removeCase() removes
4605     // the cases in SwitchInst::removeCase(CaseIt).
4606     (*Weights)[I->getCaseIndex() + 1] = Weights->back();
4607     Weights->pop_back();
4608   }
4609   return SI.removeCase(I);
4610 }
4611
4612 void SwitchInstProfUpdateWrapper::addCase(
4613     ConstantInt *OnVal, BasicBlock *Dest,
4614     SwitchInstProfUpdateWrapper::CaseWeightOpt W) {
4615   SI.addCase(OnVal, Dest);
4616
4617   if (!Weights && W && *W) {
4618     Changed = true;
4619     Weights = SmallVector<uint32_t, 8>(SI.getNumSuccessors(), 0);
4620     (*Weights)[SI.getNumSuccessors() - 1] = *W;
4621   } else if (Weights) {
4622     Changed = true;
4623     Weights->push_back(W.value_or(0));
4624   }
4625   if (Weights)
4626     assert(SI.getNumSuccessors() == Weights->size() &&
4627            "num of prof branch_weights must accord with num of successors");
4628 }
4629
4630 Instruction::InstListType::iterator
4631 SwitchInstProfUpdateWrapper::eraseFromParent() {
4632   // Instruction is erased. Mark as unchanged to not touch it in the destructor.
4633   Changed = false;
4634   if (Weights)
4635     Weights->resize(0);
4636   return SI.eraseFromParent();
4637 }
4638
4639 SwitchInstProfUpdateWrapper::CaseWeightOpt
4640 SwitchInstProfUpdateWrapper::getSuccessorWeight(unsigned idx) {
4641   if (!Weights)
4642     return std::nullopt;
4643   return (*Weights)[idx];
4644 }
4645
4646 void SwitchInstProfUpdateWrapper::setSuccessorWeight(
4647     unsigned idx, SwitchInstProfUpdateWrapper::CaseWeightOpt W) {
4648   if (!W)
4649     return;
4650
4651   if (!Weights && *W)
4652     Weights = SmallVector<uint32_t, 8>(SI.getNumSuccessors(), 0);
4653
4654   if (Weights) {
4655     auto &OldW = (*Weights)[idx];
4656     if (*W != OldW) {
4657       Changed = true;
4658       OldW = *W;
4659     }
4660   }
4661 }
4662
4663 SwitchInstProfUpdateWrapper::CaseWeightOpt
4664 SwitchInstProfUpdateWrapper::getSuccessorWeight(const SwitchInst &SI,
4665                                                 unsigned idx) {
4666   if (MDNode *ProfileData = getBranchWeightMDNode(SI))
4667     if (ProfileData->getNumOperands() == SI.getNumSuccessors() + 1)
4668       return mdconst::extract<ConstantInt>(ProfileData->getOperand(idx + 1))
4669           ->getValue()
4670           .getZExtValue();
4671
4672   return std::nullopt;
4673 }
4674
4675 //===----------------------------------------------------------------------===//
4676 //                        IndirectBrInst Implementation
4677 //===----------------------------------------------------------------------===//
4678
4679 void IndirectBrInst::init(Value *Address, unsigned NumDests) {
4680   assert(Address && Address->getType()->isPointerTy() &&
4681          "Address of indirectbr must be a pointer");
4682   ReservedSpace = 1+NumDests;
4683   setNumHungOffUseOperands(1);
4684   allocHungoffUses(ReservedSpace);
4685
4686   Op<0>() = Address;
4687 }
4688
4689
4690 /// growOperands - grow operands - This grows the operand list in response
4691 /// to a push_back style of operation.  This grows the number of ops by 2 times.
4692 ///
4693 void IndirectBrInst::growOperands() {
4694   unsigned e = getNumOperands();
4695   unsigned NumOps = e*2;
4696
4697   ReservedSpace = NumOps;
4698   growHungoffUses(ReservedSpace);
4699 }
4700
4701 IndirectBrInst::IndirectBrInst(Value *Address, unsigned NumCases,
4702                                Instruction *InsertBefore)
4703     : Instruction(Type::getVoidTy(Address->getContext()),
4704                   Instruction::IndirectBr, nullptr, 0, InsertBefore) {
4705   init(Address, NumCases);
4706 }
4707
4708 IndirectBrInst::IndirectBrInst(Value *Address, unsigned NumCases,
4709                                BasicBlock *InsertAtEnd)
4710     : Instruction(Type::getVoidTy(Address->getContext()),
4711                   Instruction::IndirectBr, nullptr, 0, InsertAtEnd) {
4712   init(Address, NumCases);
4713 }
4714
4715 IndirectBrInst::IndirectBrInst(const IndirectBrInst &IBI)
4716     : Instruction(Type::getVoidTy(IBI.getContext()), Instruction::IndirectBr,
4717                   nullptr, IBI.getNumOperands()) {
4718   allocHungoffUses(IBI.getNumOperands());
4719   Use *OL = getOperandList();
4720   const Use *InOL = IBI.getOperandList();
4721   for (unsigned i = 0, E = IBI.getNumOperands(); i != E; ++i)
4722     OL[i] = InOL[i];
4723   SubclassOptionalData = IBI.SubclassOptionalData;
4724 }
4725
4726 /// addDestination - Add a destination.
4727 ///
4728 void IndirectBrInst::addDestination(BasicBlock *DestBB) {
4729   unsigned OpNo = getNumOperands();
4730   if (OpNo+1 > ReservedSpace)
4731     growOperands();  // Get more space!
4732   // Initialize some new operands.
4733   assert(OpNo < ReservedSpace && "Growing didn't work!");
4734   setNumHungOffUseOperands(OpNo+1);
4735   getOperandList()[OpNo] = DestBB;
4736 }
4737
4738 /// removeDestination - This method removes the specified successor from the
4739 /// indirectbr instruction.
4740 void IndirectBrInst::removeDestination(unsigned idx) {
4741   assert(idx < getNumOperands()-1 && "Successor index out of range!");
4742
4743   unsigned NumOps = getNumOperands();
4744   Use *OL = getOperandList();
4745
4746   // Replace this value with the last one.
4747   OL[idx+1] = OL[NumOps-1];
4748
4749   // Nuke the last value.
4750   OL[NumOps-1].set(nullptr);
4751   setNumHungOffUseOperands(NumOps-1);
4752 }
4753
4754 //===----------------------------------------------------------------------===//
4755 //                            FreezeInst Implementation
4756 //===----------------------------------------------------------------------===//
4757
4758 FreezeInst::FreezeInst(Value *S,
4759                        const Twine &Name, Instruction *InsertBefore)
4760     : UnaryInstruction(S->getType(), Freeze, S, InsertBefore) {
4761   setName(Name);
4762 }
4763
4764 FreezeInst::FreezeInst(Value *S,
4765                        const Twine &Name, BasicBlock *InsertAtEnd)
4766     : UnaryInstruction(S->getType(), Freeze, S, InsertAtEnd) {
4767   setName(Name);
4768 }
4769
4770 //===----------------------------------------------------------------------===//
4771 //                           cloneImpl() implementations
4772 //===----------------------------------------------------------------------===//
4773
4774 // Define these methods here so vtables don't get emitted into every translation
4775 // unit that uses these classes.
4776
4777 GetElementPtrInst *GetElementPtrInst::cloneImpl() const {
4778   return new (getNumOperands()) GetElementPtrInst(*this);
4779 }
4780
4781 UnaryOperator *UnaryOperator::cloneImpl() const {
4782   return Create(getOpcode(), Op<0>());
4783 }
4784
4785 BinaryOperator *BinaryOperator::cloneImpl() const {
4786   return Create(getOpcode(), Op<0>(), Op<1>());
4787 }
4788
4789 FCmpInst *FCmpInst::cloneImpl() const {
4790   return new FCmpInst(getPredicate(), Op<0>(), Op<1>());
4791 }
4792
4793 ICmpInst *ICmpInst::cloneImpl() const {
4794   return new ICmpInst(getPredicate(), Op<0>(), Op<1>());
4795 }
4796
4797 ExtractValueInst *ExtractValueInst::cloneImpl() const {
4798   return new ExtractValueInst(*this);
4799 }
4800
4801 InsertValueInst *InsertValueInst::cloneImpl() const {
4802   return new InsertValueInst(*this);
4803 }
4804
4805 AllocaInst *AllocaInst::cloneImpl() const {
4806   AllocaInst *Result = new AllocaInst(getAllocatedType(), getAddressSpace(),
4807                                       getOperand(0), getAlign());
4808   Result->setUsedWithInAlloca(isUsedWithInAlloca());
4809   Result->setSwiftError(isSwiftError());
4810   return Result;
4811 }
4812
4813 LoadInst *LoadInst::cloneImpl() const {
4814   return new LoadInst(getType(), getOperand(0), Twine(), isVolatile(),
4815                       getAlign(), getOrdering(), getSyncScopeID());
4816 }
4817
4818 StoreInst *StoreInst::cloneImpl() const {
4819   return new StoreInst(getOperand(0), getOperand(1), isVolatile(), getAlign(),
4820                        getOrdering(), getSyncScopeID());
4821 }
4822
4823 AtomicCmpXchgInst *AtomicCmpXchgInst::cloneImpl() const {
4824   AtomicCmpXchgInst *Result = new AtomicCmpXchgInst(
4825       getOperand(0), getOperand(1), getOperand(2), getAlign(),
4826       getSuccessOrdering(), getFailureOrdering(), getSyncScopeID());
4827   Result->setVolatile(isVolatile());
4828   Result->setWeak(isWeak());
4829   return Result;
4830 }
4831
4832 AtomicRMWInst *AtomicRMWInst::cloneImpl() const {
4833   AtomicRMWInst *Result =
4834       new AtomicRMWInst(getOperation(), getOperand(0), getOperand(1),
4835                         getAlign(), getOrdering(), getSyncScopeID());
4836   Result->setVolatile(isVolatile());
4837   return Result;
4838 }
4839
4840 FenceInst *FenceInst::cloneImpl() const {
4841   return new FenceInst(getContext(), getOrdering(), getSyncScopeID());
4842 }
4843
4844 TruncInst *TruncInst::cloneImpl() const {
4845   return new TruncInst(getOperand(0), getType());
4846 }
4847
4848 ZExtInst *ZExtInst::cloneImpl() const {
4849   return new ZExtInst(getOperand(0), getType());
4850 }
4851
4852 SExtInst *SExtInst::cloneImpl() const {
4853   return new SExtInst(getOperand(0), getType());
4854 }
4855
4856 FPTruncInst *FPTruncInst::cloneImpl() const {
4857   return new FPTruncInst(getOperand(0), getType());
4858 }
4859
4860 FPExtInst *FPExtInst::cloneImpl() const {
4861   return new FPExtInst(getOperand(0), getType());
4862 }
4863
4864 UIToFPInst *UIToFPInst::cloneImpl() const {
4865   return new UIToFPInst(getOperand(0), getType());
4866 }
4867
4868 SIToFPInst *SIToFPInst::cloneImpl() const {
4869   return new SIToFPInst(getOperand(0), getType());
4870 }
4871
4872 FPToUIInst *FPToUIInst::cloneImpl() const {
4873   return new FPToUIInst(getOperand(0), getType());
4874 }
4875
4876 FPToSIInst *FPToSIInst::cloneImpl() const {
4877   return new FPToSIInst(getOperand(0), getType());
4878 }
4879
4880 PtrToIntInst *PtrToIntInst::cloneImpl() const {
4881   return new PtrToIntInst(getOperand(0), getType());
4882 }
4883
4884 IntToPtrInst *IntToPtrInst::cloneImpl() const {
4885   return new IntToPtrInst(getOperand(0), getType());
4886 }
4887
4888 BitCastInst *BitCastInst::cloneImpl() const {
4889   return new BitCastInst(getOperand(0), getType());
4890 }
4891
4892 AddrSpaceCastInst *AddrSpaceCastInst::cloneImpl() const {
4893   return new AddrSpaceCastInst(getOperand(0), getType());
4894 }
4895
4896 CallInst *CallInst::cloneImpl() const {
4897   if (hasOperandBundles()) {
4898     unsigned DescriptorBytes = getNumOperandBundles() * sizeof(BundleOpInfo);
4899     return new(getNumOperands(), DescriptorBytes) CallInst(*this);
4900   }
4901   return  new(getNumOperands()) CallInst(*this);
4902 }
4903
4904 SelectInst *SelectInst::cloneImpl() const {
4905   return SelectInst::Create(getOperand(0), getOperand(1), getOperand(2));
4906 }
4907
4908 VAArgInst *VAArgInst::cloneImpl() const {
4909   return new VAArgInst(getOperand(0), getType());
4910 }
4911
4912 ExtractElementInst *ExtractElementInst::cloneImpl() const {
4913   return ExtractElementInst::Create(getOperand(0), getOperand(1));
4914 }
4915
4916 InsertElementInst *InsertElementInst::cloneImpl() const {
4917   return InsertElementInst::Create(getOperand(0), getOperand(1), getOperand(2));
4918 }
4919
4920 ShuffleVectorInst *ShuffleVectorInst::cloneImpl() const {
4921   return new ShuffleVectorInst(getOperand(0), getOperand(1), getShuffleMask());
4922 }
4923
4924 PHINode *PHINode::cloneImpl() const { return new PHINode(*this); }
4925
4926 LandingPadInst *LandingPadInst::cloneImpl() const {
4927   return new LandingPadInst(*this);
4928 }
4929
4930 ReturnInst *ReturnInst::cloneImpl() const {
4931   return new(getNumOperands()) ReturnInst(*this);
4932 }
4933
4934 BranchInst *BranchInst::cloneImpl() const {
4935   return new(getNumOperands()) BranchInst(*this);
4936 }
4937
4938 SwitchInst *SwitchInst::cloneImpl() const { return new SwitchInst(*this); }
4939
4940 IndirectBrInst *IndirectBrInst::cloneImpl() const {
4941   return new IndirectBrInst(*this);
4942 }
4943
4944 InvokeInst *InvokeInst::cloneImpl() const {
4945   if (hasOperandBundles()) {
4946     unsigned DescriptorBytes = getNumOperandBundles() * sizeof(BundleOpInfo);
4947     return new(getNumOperands(), DescriptorBytes) InvokeInst(*this);
4948   }
4949   return new(getNumOperands()) InvokeInst(*this);
4950 }
4951
4952 CallBrInst *CallBrInst::cloneImpl() const {
4953   if (hasOperandBundles()) {
4954     unsigned DescriptorBytes = getNumOperandBundles() * sizeof(BundleOpInfo);
4955     return new (getNumOperands(), DescriptorBytes) CallBrInst(*this);
4956   }
4957   return new (getNumOperands()) CallBrInst(*this);
4958 }
4959
4960 ResumeInst *ResumeInst::cloneImpl() const { return new (1) ResumeInst(*this); }
4961
4962 CleanupReturnInst *CleanupReturnInst::cloneImpl() const {
4963   return new (getNumOperands()) CleanupReturnInst(*this);
4964 }
4965
4966 CatchReturnInst *CatchReturnInst::cloneImpl() const {
4967   return new (getNumOperands()) CatchReturnInst(*this);
4968 }
4969
4970 CatchSwitchInst *CatchSwitchInst::cloneImpl() const {
4971   return new CatchSwitchInst(*this);
4972 }
4973
4974 FuncletPadInst *FuncletPadInst::cloneImpl() const {
4975   return new (getNumOperands()) FuncletPadInst(*this);
4976 }
4977
4978 UnreachableInst *UnreachableInst::cloneImpl() const {
4979   LLVMContext &Context = getContext();
4980   return new UnreachableInst(Context);
4981 }
4982
4983 FreezeInst *FreezeInst::cloneImpl() const {
4984   return new FreezeInst(getOperand(0));
4985 }