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