contrib/llvm/lib/IR/Instructions.cpp

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