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