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