Instructions.cpp revision a9203109f4ac95aa7e9624f2838e3d89623ec902 
1//===-- Instructions.cpp - Implement the LLVM instructions ----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements all of the non-inline methods for the LLVM instruction
11// classes.
12//
13//===----------------------------------------------------------------------===//
14
15#include "LLVMContextImpl.h"
16#include "llvm/Constants.h"
17#include "llvm/DerivedTypes.h"
18#include "llvm/Function.h"
19#include "llvm/Instructions.h"
20#include "llvm/Module.h"
21#include "llvm/Operator.h"
22#include "llvm/Support/ErrorHandling.h"
23#include "llvm/Support/CallSite.h"
24#include "llvm/Support/ConstantRange.h"
25#include "llvm/Support/MathExtras.h"
26using namespace llvm;
27
28//===----------------------------------------------------------------------===//
29//                            CallSite Class
30//===----------------------------------------------------------------------===//
31
32User::op_iterator CallSite::getCallee() const {
33  Instruction *II(getInstruction());
34  return isCall()
35    ? cast<CallInst>(II)->op_end() - 1 // Skip Callee
36    : cast<InvokeInst>(II)->op_end() - 3; // Skip BB, BB, Callee
37}
38
39//===----------------------------------------------------------------------===//
40//                            TerminatorInst Class
41//===----------------------------------------------------------------------===//
42
43// Out of line virtual method, so the vtable, etc has a home.
44TerminatorInst::~TerminatorInst() {
45}
46
47//===----------------------------------------------------------------------===//
48//                           UnaryInstruction Class
49//===----------------------------------------------------------------------===//
50
51// Out of line virtual method, so the vtable, etc has a home.
52UnaryInstruction::~UnaryInstruction() {
53}
54
55//===----------------------------------------------------------------------===//
56//                              SelectInst Class
57//===----------------------------------------------------------------------===//
58
59/// areInvalidOperands - Return a string if the specified operands are invalid
60/// for a select operation, otherwise return null.
61const char *SelectInst::areInvalidOperands(Value *Op0, Value *Op1, Value *Op2) {
62  if (Op1->getType() != Op2->getType())
63    return "both values to select must have same type";
64
65  if (VectorType *VT = dyn_cast<VectorType>(Op0->getType())) {
66    // Vector select.
67    if (VT->getElementType() != Type::getInt1Ty(Op0->getContext()))
68      return "vector select condition element type must be i1";
69    VectorType *ET = dyn_cast<VectorType>(Op1->getType());
70    if (ET == 0)
71      return "selected values for vector select must be vectors";
72    if (ET->getNumElements() != VT->getNumElements())
73      return "vector select requires selected vectors to have "
74                   "the same vector length as select condition";
75  } else if (Op0->getType() != Type::getInt1Ty(Op0->getContext())) {
76    return "select condition must be i1 or <n x i1>";
77  }
78  return 0;
79}
80
81
82//===----------------------------------------------------------------------===//
83//                               PHINode Class
84//===----------------------------------------------------------------------===//
85
86PHINode::PHINode(const PHINode &PN)
87  : Instruction(PN.getType(), Instruction::PHI,
88                allocHungoffUses(PN.getNumOperands()), PN.getNumOperands()),
89    ReservedSpace(PN.getNumOperands()) {
90  std::copy(PN.op_begin(), PN.op_end(), op_begin());
91  std::copy(PN.block_begin(), PN.block_end(), block_begin());
92  SubclassOptionalData = PN.SubclassOptionalData;
93}
94
95PHINode::~PHINode() {
96  dropHungoffUses();
97}
98
99Use *PHINode::allocHungoffUses(unsigned N) const {
100  // Allocate the array of Uses of the incoming values, followed by a pointer
101  // (with bottom bit set) to the User, followed by the array of pointers to
102  // the incoming basic blocks.
103  size_t size = N * sizeof(Use) + sizeof(Use::UserRef)
104    + N * sizeof(BasicBlock*);
105  Use *Begin = static_cast<Use*>(::operator new(size));
106  Use *End = Begin + N;
107  (void) new(End) Use::UserRef(const_cast<PHINode*>(this), 1);
108  return Use::initTags(Begin, End);
109}
110
111// removeIncomingValue - Remove an incoming value.  This is useful if a
112// predecessor basic block is deleted.
113Value *PHINode::removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty) {
114  Value *Removed = getIncomingValue(Idx);
115
116  // Move everything after this operand down.
117  //
118  // FIXME: we could just swap with the end of the list, then erase.  However,
119  // clients might not expect this to happen.  The code as it is thrashes the
120  // use/def lists, which is kinda lame.
121  std::copy(op_begin() + Idx + 1, op_end(), op_begin() + Idx);
122  std::copy(block_begin() + Idx + 1, block_end(), block_begin() + Idx);
123
124  // Nuke the last value.
125  Op<-1>().set(0);
126  --NumOperands;
127
128  // If the PHI node is dead, because it has zero entries, nuke it now.
129  if (getNumOperands() == 0 && DeletePHIIfEmpty) {
130    // If anyone is using this PHI, make them use a dummy value instead...
131    replaceAllUsesWith(UndefValue::get(getType()));
132    eraseFromParent();
133  }
134  return Removed;
135}
136
137/// growOperands - grow operands - This grows the operand list in response
138/// to a push_back style of operation.  This grows the number of ops by 1.5
139/// times.
140///
141void PHINode::growOperands() {
142  unsigned e = getNumOperands();
143  unsigned NumOps = e + e / 2;
144  if (NumOps < 2) NumOps = 2;      // 2 op PHI nodes are VERY common.
145
146  Use *OldOps = op_begin();
147  BasicBlock **OldBlocks = block_begin();
148
149  ReservedSpace = NumOps;
150  OperandList = allocHungoffUses(ReservedSpace);
151
152  std::copy(OldOps, OldOps + e, op_begin());
153  std::copy(OldBlocks, OldBlocks + e, block_begin());
154
155  Use::zap(OldOps, OldOps + e, true);
156}
157
158/// hasConstantValue - If the specified PHI node always merges together the same
159/// value, return the value, otherwise return null.
160Value *PHINode::hasConstantValue() const {
161  // Exploit the fact that phi nodes always have at least one entry.
162  Value *ConstantValue = getIncomingValue(0);
163  for (unsigned i = 1, e = getNumIncomingValues(); i != e; ++i)
164    if (getIncomingValue(i) != ConstantValue)
165      return 0; // Incoming values not all the same.
166  return ConstantValue;
167}
168
169
170//===----------------------------------------------------------------------===//
171//                        CallInst Implementation
172//===----------------------------------------------------------------------===//
173
174CallInst::~CallInst() {
175}
176
177void CallInst::init(Value *Func, ArrayRef<Value *> Args, const Twine &NameStr) {
178  assert(NumOperands == Args.size() + 1 && "NumOperands not set up?");
179  Op<-1>() = Func;
180
181#ifndef NDEBUG
182  FunctionType *FTy =
183    cast<FunctionType>(cast<PointerType>(Func->getType())->getElementType());
184
185  assert((Args.size() == FTy->getNumParams() ||
186          (FTy->isVarArg() && Args.size() > FTy->getNumParams())) &&
187         "Calling a function with bad signature!");
188
189  for (unsigned i = 0; i != Args.size(); ++i)
190    assert((i >= FTy->getNumParams() ||
191            FTy->getParamType(i) == Args[i]->getType()) &&
192           "Calling a function with a bad signature!");
193#endif
194
195  std::copy(Args.begin(), Args.end(), op_begin());
196  setName(NameStr);
197}
198
199void CallInst::init(Value *Func, const Twine &NameStr) {
200  assert(NumOperands == 1 && "NumOperands not set up?");
201  Op<-1>() = Func;
202
203#ifndef NDEBUG
204  FunctionType *FTy =
205    cast<FunctionType>(cast<PointerType>(Func->getType())->getElementType());
206
207  assert(FTy->getNumParams() == 0 && "Calling a function with bad signature");
208#endif
209
210  setName(NameStr);
211}
212
213CallInst::CallInst(Value *Func, const Twine &Name,
214                   Instruction *InsertBefore)
215  : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
216                                   ->getElementType())->getReturnType(),
217                Instruction::Call,
218                OperandTraits<CallInst>::op_end(this) - 1,
219                1, InsertBefore) {
220  init(Func, Name);
221}
222
223CallInst::CallInst(Value *Func, const Twine &Name,
224                   BasicBlock *InsertAtEnd)
225  : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
226                                   ->getElementType())->getReturnType(),
227                Instruction::Call,
228                OperandTraits<CallInst>::op_end(this) - 1,
229                1, InsertAtEnd) {
230  init(Func, Name);
231}
232
233CallInst::CallInst(const CallInst &CI)
234  : Instruction(CI.getType(), Instruction::Call,
235                OperandTraits<CallInst>::op_end(this) - CI.getNumOperands(),
236                CI.getNumOperands()) {
237  setAttributes(CI.getAttributes());
238  setTailCall(CI.isTailCall());
239  setCallingConv(CI.getCallingConv());
240
241  std::copy(CI.op_begin(), CI.op_end(), op_begin());
242  SubclassOptionalData = CI.SubclassOptionalData;
243}
244
245void CallInst::addAttribute(unsigned i, Attributes attr) {
246  AttrListPtr PAL = getAttributes();
247  PAL = PAL.addAttr(i, attr);
248  setAttributes(PAL);
249}
250
251void CallInst::removeAttribute(unsigned i, Attributes attr) {
252  AttrListPtr PAL = getAttributes();
253  PAL = PAL.removeAttr(i, attr);
254  setAttributes(PAL);
255}
256
257bool CallInst::paramHasAttr(unsigned i, Attributes attr) const {
258  if (AttributeList.paramHasAttr(i, attr))
259    return true;
260  if (const Function *F = getCalledFunction())
261    return F->paramHasAttr(i, attr);
262  return false;
263}
264
265/// IsConstantOne - Return true only if val is constant int 1
266static bool IsConstantOne(Value *val) {
267  assert(val && "IsConstantOne does not work with NULL val");
268  return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
269}
270
271static Instruction *createMalloc(Instruction *InsertBefore,
272                                 BasicBlock *InsertAtEnd, Type *IntPtrTy,
273                                 Type *AllocTy, Value *AllocSize,
274                                 Value *ArraySize, Function *MallocF,
275                                 const Twine &Name) {
276  assert(((!InsertBefore && InsertAtEnd) || (InsertBefore && !InsertAtEnd)) &&
277         "createMalloc needs either InsertBefore or InsertAtEnd");
278
279  // malloc(type) becomes:
280  //       bitcast (i8* malloc(typeSize)) to type*
281  // malloc(type, arraySize) becomes:
282  //       bitcast (i8 *malloc(typeSize*arraySize)) to type*
283  if (!ArraySize)
284    ArraySize = ConstantInt::get(IntPtrTy, 1);
285  else if (ArraySize->getType() != IntPtrTy) {
286    if (InsertBefore)
287      ArraySize = CastInst::CreateIntegerCast(ArraySize, IntPtrTy, false,
288                                              "", InsertBefore);
289    else
290      ArraySize = CastInst::CreateIntegerCast(ArraySize, IntPtrTy, false,
291                                              "", InsertAtEnd);
292  }
293
294  if (!IsConstantOne(ArraySize)) {
295    if (IsConstantOne(AllocSize)) {
296      AllocSize = ArraySize;         // Operand * 1 = Operand
297    } else if (Constant *CO = dyn_cast<Constant>(ArraySize)) {
298      Constant *Scale = ConstantExpr::getIntegerCast(CO, IntPtrTy,
299                                                     false /*ZExt*/);
300      // Malloc arg is constant product of type size and array size
301      AllocSize = ConstantExpr::getMul(Scale, cast<Constant>(AllocSize));
302    } else {
303      // Multiply type size by the array size...
304      if (InsertBefore)
305        AllocSize = BinaryOperator::CreateMul(ArraySize, AllocSize,
306                                              "mallocsize", InsertBefore);
307      else
308        AllocSize = BinaryOperator::CreateMul(ArraySize, AllocSize,
309                                              "mallocsize", InsertAtEnd);
310    }
311  }
312
313  assert(AllocSize->getType() == IntPtrTy && "malloc arg is wrong size");
314  // Create the call to Malloc.
315  BasicBlock* BB = InsertBefore ? InsertBefore->getParent() : InsertAtEnd;
316  Module* M = BB->getParent()->getParent();
317  Type *BPTy = Type::getInt8PtrTy(BB->getContext());
318  Value *MallocFunc = MallocF;
319  if (!MallocFunc)
320    // prototype malloc as "void *malloc(size_t)"
321    MallocFunc = M->getOrInsertFunction("malloc", BPTy, IntPtrTy, NULL);
322  PointerType *AllocPtrType = PointerType::getUnqual(AllocTy);
323  CallInst *MCall = NULL;
324  Instruction *Result = NULL;
325  if (InsertBefore) {
326    MCall = CallInst::Create(MallocFunc, AllocSize, "malloccall", InsertBefore);
327    Result = MCall;
328    if (Result->getType() != AllocPtrType)
329      // Create a cast instruction to convert to the right type...
330      Result = new BitCastInst(MCall, AllocPtrType, Name, InsertBefore);
331  } else {
332    MCall = CallInst::Create(MallocFunc, AllocSize, "malloccall");
333    Result = MCall;
334    if (Result->getType() != AllocPtrType) {
335      InsertAtEnd->getInstList().push_back(MCall);
336      // Create a cast instruction to convert to the right type...
337      Result = new BitCastInst(MCall, AllocPtrType, Name);
338    }
339  }
340  MCall->setTailCall();
341  if (Function *F = dyn_cast<Function>(MallocFunc)) {
342    MCall->setCallingConv(F->getCallingConv());
343    if (!F->doesNotAlias(0)) F->setDoesNotAlias(0);
344  }
345  assert(!MCall->getType()->isVoidTy() && "Malloc has void return type");
346
347  return Result;
348}
349
350/// CreateMalloc - Generate the IR for a call to malloc:
351/// 1. Compute the malloc call's argument as the specified type's size,
352///    possibly multiplied by the array size if the array size is not
353///    constant 1.
354/// 2. Call malloc with that argument.
355/// 3. Bitcast the result of the malloc call to the specified type.
356Instruction *CallInst::CreateMalloc(Instruction *InsertBefore,
357                                    Type *IntPtrTy, Type *AllocTy,
358                                    Value *AllocSize, Value *ArraySize,
359                                    Function * MallocF,
360                                    const Twine &Name) {
361  return createMalloc(InsertBefore, NULL, IntPtrTy, AllocTy, AllocSize,
362                      ArraySize, MallocF, Name);
363}
364
365/// CreateMalloc - Generate the IR for a call to malloc:
366/// 1. Compute the malloc call's argument as the specified type's size,
367///    possibly multiplied by the array size if the array size is not
368///    constant 1.
369/// 2. Call malloc with that argument.
370/// 3. Bitcast the result of the malloc call to the specified type.
371/// Note: This function does not add the bitcast to the basic block, that is the
372/// responsibility of the caller.
373Instruction *CallInst::CreateMalloc(BasicBlock *InsertAtEnd,
374                                    Type *IntPtrTy, Type *AllocTy,
375                                    Value *AllocSize, Value *ArraySize,
376                                    Function *MallocF, const Twine &Name) {
377  return createMalloc(NULL, InsertAtEnd, IntPtrTy, AllocTy, AllocSize,
378                      ArraySize, MallocF, Name);
379}
380
381static Instruction* createFree(Value* Source, Instruction *InsertBefore,
382                               BasicBlock *InsertAtEnd) {
383  assert(((!InsertBefore && InsertAtEnd) || (InsertBefore && !InsertAtEnd)) &&
384         "createFree needs either InsertBefore or InsertAtEnd");
385  assert(Source->getType()->isPointerTy() &&
386         "Can not free something of nonpointer type!");
387
388  BasicBlock* BB = InsertBefore ? InsertBefore->getParent() : InsertAtEnd;
389  Module* M = BB->getParent()->getParent();
390
391  Type *VoidTy = Type::getVoidTy(M->getContext());
392  Type *IntPtrTy = Type::getInt8PtrTy(M->getContext());
393  // prototype free as "void free(void*)"
394  Value *FreeFunc = M->getOrInsertFunction("free", VoidTy, IntPtrTy, NULL);
395  CallInst* Result = NULL;
396  Value *PtrCast = Source;
397  if (InsertBefore) {
398    if (Source->getType() != IntPtrTy)
399      PtrCast = new BitCastInst(Source, IntPtrTy, "", InsertBefore);
400    Result = CallInst::Create(FreeFunc, PtrCast, "", InsertBefore);
401  } else {
402    if (Source->getType() != IntPtrTy)
403      PtrCast = new BitCastInst(Source, IntPtrTy, "", InsertAtEnd);
404    Result = CallInst::Create(FreeFunc, PtrCast, "");
405  }
406  Result->setTailCall();
407  if (Function *F = dyn_cast<Function>(FreeFunc))
408    Result->setCallingConv(F->getCallingConv());
409
410  return Result;
411}
412
413/// CreateFree - Generate the IR for a call to the builtin free function.
414Instruction * CallInst::CreateFree(Value* Source, Instruction *InsertBefore) {
415  return createFree(Source, InsertBefore, NULL);
416}
417
418/// CreateFree - Generate the IR for a call to the builtin free function.
419/// Note: This function does not add the call to the basic block, that is the
420/// responsibility of the caller.
421Instruction* CallInst::CreateFree(Value* Source, BasicBlock *InsertAtEnd) {
422  Instruction* FreeCall = createFree(Source, NULL, InsertAtEnd);
423  assert(FreeCall && "CreateFree did not create a CallInst");
424  return FreeCall;
425}
426
427//===----------------------------------------------------------------------===//
428//                        InvokeInst Implementation
429//===----------------------------------------------------------------------===//
430
431void InvokeInst::init(Value *Fn, BasicBlock *IfNormal, BasicBlock *IfException,
432                      ArrayRef<Value *> Args, const Twine &NameStr) {
433  assert(NumOperands == 3 + Args.size() && "NumOperands not set up?");
434  Op<-3>() = Fn;
435  Op<-2>() = IfNormal;
436  Op<-1>() = IfException;
437
438#ifndef NDEBUG
439  FunctionType *FTy =
440    cast<FunctionType>(cast<PointerType>(Fn->getType())->getElementType());
441
442  assert(((Args.size() == FTy->getNumParams()) ||
443          (FTy->isVarArg() && Args.size() > FTy->getNumParams())) &&
444         "Invoking a function with bad signature");
445
446  for (unsigned i = 0, e = Args.size(); i != e; i++)
447    assert((i >= FTy->getNumParams() ||
448            FTy->getParamType(i) == Args[i]->getType()) &&
449           "Invoking a function with a bad signature!");
450#endif
451
452  std::copy(Args.begin(), Args.end(), op_begin());
453  setName(NameStr);
454}
455
456InvokeInst::InvokeInst(const InvokeInst &II)
457  : TerminatorInst(II.getType(), Instruction::Invoke,
458                   OperandTraits<InvokeInst>::op_end(this)
459                   - II.getNumOperands(),
460                   II.getNumOperands()) {
461  setAttributes(II.getAttributes());
462  setCallingConv(II.getCallingConv());
463  std::copy(II.op_begin(), II.op_end(), op_begin());
464  SubclassOptionalData = II.SubclassOptionalData;
465}
466
467BasicBlock *InvokeInst::getSuccessorV(unsigned idx) const {
468  return getSuccessor(idx);
469}
470unsigned InvokeInst::getNumSuccessorsV() const {
471  return getNumSuccessors();
472}
473void InvokeInst::setSuccessorV(unsigned idx, BasicBlock *B) {
474  return setSuccessor(idx, B);
475}
476
477bool InvokeInst::paramHasAttr(unsigned i, Attributes attr) const {
478  if (AttributeList.paramHasAttr(i, attr))
479    return true;
480  if (const Function *F = getCalledFunction())
481    return F->paramHasAttr(i, attr);
482  return false;
483}
484
485void InvokeInst::addAttribute(unsigned i, Attributes attr) {
486  AttrListPtr PAL = getAttributes();
487  PAL = PAL.addAttr(i, attr);
488  setAttributes(PAL);
489}
490
491void InvokeInst::removeAttribute(unsigned i, Attributes attr) {
492  AttrListPtr PAL = getAttributes();
493  PAL = PAL.removeAttr(i, attr);
494  setAttributes(PAL);
495}
496
497
498//===----------------------------------------------------------------------===//
499//                        ReturnInst Implementation
500//===----------------------------------------------------------------------===//
501
502ReturnInst::ReturnInst(const ReturnInst &RI)
503  : TerminatorInst(Type::getVoidTy(RI.getContext()), Instruction::Ret,
504                   OperandTraits<ReturnInst>::op_end(this) -
505                     RI.getNumOperands(),
506                   RI.getNumOperands()) {
507  if (RI.getNumOperands())
508    Op<0>() = RI.Op<0>();
509  SubclassOptionalData = RI.SubclassOptionalData;
510}
511
512ReturnInst::ReturnInst(LLVMContext &C, Value *retVal, Instruction *InsertBefore)
513  : TerminatorInst(Type::getVoidTy(C), Instruction::Ret,
514                   OperandTraits<ReturnInst>::op_end(this) - !!retVal, !!retVal,
515                   InsertBefore) {
516  if (retVal)
517    Op<0>() = retVal;
518}
519ReturnInst::ReturnInst(LLVMContext &C, Value *retVal, BasicBlock *InsertAtEnd)
520  : TerminatorInst(Type::getVoidTy(C), Instruction::Ret,
521                   OperandTraits<ReturnInst>::op_end(this) - !!retVal, !!retVal,
522                   InsertAtEnd) {
523  if (retVal)
524    Op<0>() = retVal;
525}
526ReturnInst::ReturnInst(LLVMContext &Context, BasicBlock *InsertAtEnd)
527  : TerminatorInst(Type::getVoidTy(Context), Instruction::Ret,
528                   OperandTraits<ReturnInst>::op_end(this), 0, InsertAtEnd) {
529}
530
531unsigned ReturnInst::getNumSuccessorsV() const {
532  return getNumSuccessors();
533}
534
535/// Out-of-line ReturnInst method, put here so the C++ compiler can choose to
536/// emit the vtable for the class in this translation unit.
537void ReturnInst::setSuccessorV(unsigned idx, BasicBlock *NewSucc) {
538  llvm_unreachable("ReturnInst has no successors!");
539}
540
541BasicBlock *ReturnInst::getSuccessorV(unsigned idx) const {
542  llvm_unreachable("ReturnInst has no successors!");
543  return 0;
544}
545
546ReturnInst::~ReturnInst() {
547}
548
549//===----------------------------------------------------------------------===//
550//                        UnwindInst Implementation
551//===----------------------------------------------------------------------===//
552
553UnwindInst::UnwindInst(LLVMContext &Context, Instruction *InsertBefore)
554  : TerminatorInst(Type::getVoidTy(Context), Instruction::Unwind,
555                   0, 0, InsertBefore) {
556}
557UnwindInst::UnwindInst(LLVMContext &Context, BasicBlock *InsertAtEnd)
558  : TerminatorInst(Type::getVoidTy(Context), Instruction::Unwind,
559                   0, 0, InsertAtEnd) {
560}
561
562
563unsigned UnwindInst::getNumSuccessorsV() const {
564  return getNumSuccessors();
565}
566
567void UnwindInst::setSuccessorV(unsigned idx, BasicBlock *NewSucc) {
568  llvm_unreachable("UnwindInst has no successors!");
569}
570
571BasicBlock *UnwindInst::getSuccessorV(unsigned idx) const {
572  llvm_unreachable("UnwindInst has no successors!");
573  return 0;
574}
575
576//===----------------------------------------------------------------------===//
577//                      UnreachableInst Implementation
578//===----------------------------------------------------------------------===//
579
580UnreachableInst::UnreachableInst(LLVMContext &Context,
581                                 Instruction *InsertBefore)
582  : TerminatorInst(Type::getVoidTy(Context), Instruction::Unreachable,
583                   0, 0, InsertBefore) {
584}
585UnreachableInst::UnreachableInst(LLVMContext &Context, BasicBlock *InsertAtEnd)
586  : TerminatorInst(Type::getVoidTy(Context), Instruction::Unreachable,
587                   0, 0, InsertAtEnd) {
588}
589
590unsigned UnreachableInst::getNumSuccessorsV() const {
591  return getNumSuccessors();
592}
593
594void UnreachableInst::setSuccessorV(unsigned idx, BasicBlock *NewSucc) {
595  llvm_unreachable("UnwindInst has no successors!");
596}
597
598BasicBlock *UnreachableInst::getSuccessorV(unsigned idx) const {
599  llvm_unreachable("UnwindInst has no successors!");
600  return 0;
601}
602
603//===----------------------------------------------------------------------===//
604//                        BranchInst Implementation
605//===----------------------------------------------------------------------===//
606
607void BranchInst::AssertOK() {
608  if (isConditional())
609    assert(getCondition()->getType()->isIntegerTy(1) &&
610           "May only branch on boolean predicates!");
611}
612
613BranchInst::BranchInst(BasicBlock *IfTrue, Instruction *InsertBefore)
614  : TerminatorInst(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
615                   OperandTraits<BranchInst>::op_end(this) - 1,
616                   1, InsertBefore) {
617  assert(IfTrue != 0 && "Branch destination may not be null!");
618  Op<-1>() = IfTrue;
619}
620BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
621                       Instruction *InsertBefore)
622  : TerminatorInst(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
623                   OperandTraits<BranchInst>::op_end(this) - 3,
624                   3, InsertBefore) {
625  Op<-1>() = IfTrue;
626  Op<-2>() = IfFalse;
627  Op<-3>() = Cond;
628#ifndef NDEBUG
629  AssertOK();
630#endif
631}
632
633BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *InsertAtEnd)
634  : TerminatorInst(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
635                   OperandTraits<BranchInst>::op_end(this) - 1,
636                   1, InsertAtEnd) {
637  assert(IfTrue != 0 && "Branch destination may not be null!");
638  Op<-1>() = IfTrue;
639}
640
641BranchInst::BranchInst(BasicBlock *IfTrue, BasicBlock *IfFalse, Value *Cond,
642           BasicBlock *InsertAtEnd)
643  : TerminatorInst(Type::getVoidTy(IfTrue->getContext()), Instruction::Br,
644                   OperandTraits<BranchInst>::op_end(this) - 3,
645                   3, InsertAtEnd) {
646  Op<-1>() = IfTrue;
647  Op<-2>() = IfFalse;
648  Op<-3>() = Cond;
649#ifndef NDEBUG
650  AssertOK();
651#endif
652}
653
654
655BranchInst::BranchInst(const BranchInst &BI) :
656  TerminatorInst(Type::getVoidTy(BI.getContext()), Instruction::Br,
657                 OperandTraits<BranchInst>::op_end(this) - BI.getNumOperands(),
658                 BI.getNumOperands()) {
659  Op<-1>() = BI.Op<-1>();
660  if (BI.getNumOperands() != 1) {
661    assert(BI.getNumOperands() == 3 && "BR can have 1 or 3 operands!");
662    Op<-3>() = BI.Op<-3>();
663    Op<-2>() = BI.Op<-2>();
664  }
665  SubclassOptionalData = BI.SubclassOptionalData;
666}
667
668BasicBlock *BranchInst::getSuccessorV(unsigned idx) const {
669  return getSuccessor(idx);
670}
671unsigned BranchInst::getNumSuccessorsV() const {
672  return getNumSuccessors();
673}
674void BranchInst::setSuccessorV(unsigned idx, BasicBlock *B) {
675  setSuccessor(idx, B);
676}
677
678
679//===----------------------------------------------------------------------===//
680//                        AllocaInst Implementation
681//===----------------------------------------------------------------------===//
682
683static Value *getAISize(LLVMContext &Context, Value *Amt) {
684  if (!Amt)
685    Amt = ConstantInt::get(Type::getInt32Ty(Context), 1);
686  else {
687    assert(!isa<BasicBlock>(Amt) &&
688           "Passed basic block into allocation size parameter! Use other ctor");
689    assert(Amt->getType()->isIntegerTy() &&
690           "Allocation array size is not an integer!");
691  }
692  return Amt;
693}
694
695AllocaInst::AllocaInst(Type *Ty, Value *ArraySize,
696                       const Twine &Name, Instruction *InsertBefore)
697  : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
698                     getAISize(Ty->getContext(), ArraySize), InsertBefore) {
699  setAlignment(0);
700  assert(!Ty->isVoidTy() && "Cannot allocate void!");
701  setName(Name);
702}
703
704AllocaInst::AllocaInst(Type *Ty, Value *ArraySize,
705                       const Twine &Name, BasicBlock *InsertAtEnd)
706  : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
707                     getAISize(Ty->getContext(), ArraySize), InsertAtEnd) {
708  setAlignment(0);
709  assert(!Ty->isVoidTy() && "Cannot allocate void!");
710  setName(Name);
711}
712
713AllocaInst::AllocaInst(Type *Ty, const Twine &Name,
714                       Instruction *InsertBefore)
715  : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
716                     getAISize(Ty->getContext(), 0), InsertBefore) {
717  setAlignment(0);
718  assert(!Ty->isVoidTy() && "Cannot allocate void!");
719  setName(Name);
720}
721
722AllocaInst::AllocaInst(Type *Ty, const Twine &Name,
723                       BasicBlock *InsertAtEnd)
724  : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
725                     getAISize(Ty->getContext(), 0), InsertAtEnd) {
726  setAlignment(0);
727  assert(!Ty->isVoidTy() && "Cannot allocate void!");
728  setName(Name);
729}
730
731AllocaInst::AllocaInst(Type *Ty, Value *ArraySize, unsigned Align,
732                       const Twine &Name, Instruction *InsertBefore)
733  : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
734                     getAISize(Ty->getContext(), ArraySize), InsertBefore) {
735  setAlignment(Align);
736  assert(!Ty->isVoidTy() && "Cannot allocate void!");
737  setName(Name);
738}
739
740AllocaInst::AllocaInst(Type *Ty, Value *ArraySize, unsigned Align,
741                       const Twine &Name, BasicBlock *InsertAtEnd)
742  : UnaryInstruction(PointerType::getUnqual(Ty), Alloca,
743                     getAISize(Ty->getContext(), ArraySize), InsertAtEnd) {
744  setAlignment(Align);
745  assert(!Ty->isVoidTy() && "Cannot allocate void!");
746  setName(Name);
747}
748
749// Out of line virtual method, so the vtable, etc has a home.
750AllocaInst::~AllocaInst() {
751}
752
753void AllocaInst::setAlignment(unsigned Align) {
754  assert((Align & (Align-1)) == 0 && "Alignment is not a power of 2!");
755  assert(Align <= MaximumAlignment &&
756         "Alignment is greater than MaximumAlignment!");
757  setInstructionSubclassData(Log2_32(Align) + 1);
758  assert(getAlignment() == Align && "Alignment representation error!");
759}
760
761bool AllocaInst::isArrayAllocation() const {
762  if (ConstantInt *CI = dyn_cast<ConstantInt>(getOperand(0)))
763    return !CI->isOne();
764  return true;
765}
766
767Type *AllocaInst::getAllocatedType() const {
768  return getType()->getElementType();
769}
770
771/// isStaticAlloca - Return true if this alloca is in the entry block of the
772/// function and is a constant size.  If so, the code generator will fold it
773/// into the prolog/epilog code, so it is basically free.
774bool AllocaInst::isStaticAlloca() const {
775  // Must be constant size.
776  if (!isa<ConstantInt>(getArraySize())) return false;
777
778  // Must be in the entry block.
779  const BasicBlock *Parent = getParent();
780  return Parent == &Parent->getParent()->front();
781}
782
783//===----------------------------------------------------------------------===//
784//                           LoadInst Implementation
785//===----------------------------------------------------------------------===//
786
787void LoadInst::AssertOK() {
788  assert(getOperand(0)->getType()->isPointerTy() &&
789         "Ptr must have pointer type.");
790}
791
792LoadInst::LoadInst(Value *Ptr, const Twine &Name, Instruction *InsertBef)
793  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
794                     Load, Ptr, InsertBef) {
795  setVolatile(false);
796  setAlignment(0);
797  AssertOK();
798  setName(Name);
799}
800
801LoadInst::LoadInst(Value *Ptr, const Twine &Name, BasicBlock *InsertAE)
802  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
803                     Load, Ptr, InsertAE) {
804  setVolatile(false);
805  setAlignment(0);
806  AssertOK();
807  setName(Name);
808}
809
810LoadInst::LoadInst(Value *Ptr, const Twine &Name, bool isVolatile,
811                   Instruction *InsertBef)
812  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
813                     Load, Ptr, InsertBef) {
814  setVolatile(isVolatile);
815  setAlignment(0);
816  AssertOK();
817  setName(Name);
818}
819
820LoadInst::LoadInst(Value *Ptr, const Twine &Name, bool isVolatile,
821                   unsigned Align, Instruction *InsertBef)
822  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
823                     Load, Ptr, InsertBef) {
824  setVolatile(isVolatile);
825  setAlignment(Align);
826  AssertOK();
827  setName(Name);
828}
829
830LoadInst::LoadInst(Value *Ptr, const Twine &Name, bool isVolatile,
831                   unsigned Align, BasicBlock *InsertAE)
832  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
833                     Load, Ptr, InsertAE) {
834  setVolatile(isVolatile);
835  setAlignment(Align);
836  AssertOK();
837  setName(Name);
838}
839
840LoadInst::LoadInst(Value *Ptr, const Twine &Name, bool isVolatile,
841                   BasicBlock *InsertAE)
842  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
843                     Load, Ptr, InsertAE) {
844  setVolatile(isVolatile);
845  setAlignment(0);
846  AssertOK();
847  setName(Name);
848}
849
850
851
852LoadInst::LoadInst(Value *Ptr, const char *Name, Instruction *InsertBef)
853  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
854                     Load, Ptr, InsertBef) {
855  setVolatile(false);
856  setAlignment(0);
857  AssertOK();
858  if (Name && Name[0]) setName(Name);
859}
860
861LoadInst::LoadInst(Value *Ptr, const char *Name, BasicBlock *InsertAE)
862  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
863                     Load, Ptr, InsertAE) {
864  setVolatile(false);
865  setAlignment(0);
866  AssertOK();
867  if (Name && Name[0]) setName(Name);
868}
869
870LoadInst::LoadInst(Value *Ptr, const char *Name, bool isVolatile,
871                   Instruction *InsertBef)
872: UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
873                   Load, Ptr, InsertBef) {
874  setVolatile(isVolatile);
875  setAlignment(0);
876  AssertOK();
877  if (Name && Name[0]) setName(Name);
878}
879
880LoadInst::LoadInst(Value *Ptr, const char *Name, bool isVolatile,
881                   BasicBlock *InsertAE)
882  : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
883                     Load, Ptr, InsertAE) {
884  setVolatile(isVolatile);
885  setAlignment(0);
886  AssertOK();
887  if (Name && Name[0]) setName(Name);
888}
889
890void LoadInst::setAlignment(unsigned Align) {
891  assert((Align & (Align-1)) == 0 && "Alignment is not a power of 2!");
892  assert(Align <= MaximumAlignment &&
893         "Alignment is greater than MaximumAlignment!");
894  setInstructionSubclassData((getSubclassDataFromInstruction() & 1) |
895                             ((Log2_32(Align)+1)<<1));
896  assert(getAlignment() == Align && "Alignment representation error!");
897}
898
899//===----------------------------------------------------------------------===//
900//                           StoreInst Implementation
901//===----------------------------------------------------------------------===//
902
903void StoreInst::AssertOK() {
904  assert(getOperand(0) && getOperand(1) && "Both operands must be non-null!");
905  assert(getOperand(1)->getType()->isPointerTy() &&
906         "Ptr must have pointer type!");
907  assert(getOperand(0)->getType() ==
908                 cast<PointerType>(getOperand(1)->getType())->getElementType()
909         && "Ptr must be a pointer to Val type!");
910}
911
912
913StoreInst::StoreInst(Value *val, Value *addr, Instruction *InsertBefore)
914  : Instruction(Type::getVoidTy(val->getContext()), Store,
915                OperandTraits<StoreInst>::op_begin(this),
916                OperandTraits<StoreInst>::operands(this),
917                InsertBefore) {
918  Op<0>() = val;
919  Op<1>() = addr;
920  setVolatile(false);
921  setAlignment(0);
922  AssertOK();
923}
924
925StoreInst::StoreInst(Value *val, Value *addr, BasicBlock *InsertAtEnd)
926  : Instruction(Type::getVoidTy(val->getContext()), Store,
927                OperandTraits<StoreInst>::op_begin(this),
928                OperandTraits<StoreInst>::operands(this),
929                InsertAtEnd) {
930  Op<0>() = val;
931  Op<1>() = addr;
932  setVolatile(false);
933  setAlignment(0);
934  AssertOK();
935}
936
937StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
938                     Instruction *InsertBefore)
939  : Instruction(Type::getVoidTy(val->getContext()), Store,
940                OperandTraits<StoreInst>::op_begin(this),
941                OperandTraits<StoreInst>::operands(this),
942                InsertBefore) {
943  Op<0>() = val;
944  Op<1>() = addr;
945  setVolatile(isVolatile);
946  setAlignment(0);
947  AssertOK();
948}
949
950StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
951                     unsigned Align, Instruction *InsertBefore)
952  : Instruction(Type::getVoidTy(val->getContext()), Store,
953                OperandTraits<StoreInst>::op_begin(this),
954                OperandTraits<StoreInst>::operands(this),
955                InsertBefore) {
956  Op<0>() = val;
957  Op<1>() = addr;
958  setVolatile(isVolatile);
959  setAlignment(Align);
960  AssertOK();
961}
962
963StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
964                     unsigned Align, BasicBlock *InsertAtEnd)
965  : Instruction(Type::getVoidTy(val->getContext()), Store,
966                OperandTraits<StoreInst>::op_begin(this),
967                OperandTraits<StoreInst>::operands(this),
968                InsertAtEnd) {
969  Op<0>() = val;
970  Op<1>() = addr;
971  setVolatile(isVolatile);
972  setAlignment(Align);
973  AssertOK();
974}
975
976StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
977                     BasicBlock *InsertAtEnd)
978  : Instruction(Type::getVoidTy(val->getContext()), Store,
979                OperandTraits<StoreInst>::op_begin(this),
980                OperandTraits<StoreInst>::operands(this),
981                InsertAtEnd) {
982  Op<0>() = val;
983  Op<1>() = addr;
984  setVolatile(isVolatile);
985  setAlignment(0);
986  AssertOK();
987}
988
989void StoreInst::setAlignment(unsigned Align) {
990  assert((Align & (Align-1)) == 0 && "Alignment is not a power of 2!");
991  assert(Align <= MaximumAlignment &&
992         "Alignment is greater than MaximumAlignment!");
993  setInstructionSubclassData((getSubclassDataFromInstruction() & 1) |
994                             ((Log2_32(Align)+1) << 1));
995  assert(getAlignment() == Align && "Alignment representation error!");
996}
997
998//===----------------------------------------------------------------------===//
999//                       GetElementPtrInst Implementation
1000//===----------------------------------------------------------------------===//
1001
1002void GetElementPtrInst::init(Value *Ptr, ArrayRef<Value *> IdxList,
1003                             const Twine &Name) {
1004  assert(NumOperands == 1 + IdxList.size() && "NumOperands not initialized?");
1005  OperandList[0] = Ptr;
1006  std::copy(IdxList.begin(), IdxList.end(), op_begin() + 1);
1007  setName(Name);
1008}
1009
1010GetElementPtrInst::GetElementPtrInst(const GetElementPtrInst &GEPI)
1011  : Instruction(GEPI.getType(), GetElementPtr,
1012                OperandTraits<GetElementPtrInst>::op_end(this)
1013                - GEPI.getNumOperands(),
1014                GEPI.getNumOperands()) {
1015  std::copy(GEPI.op_begin(), GEPI.op_end(), op_begin());
1016  SubclassOptionalData = GEPI.SubclassOptionalData;
1017}
1018
1019/// getIndexedType - Returns the type of the element that would be accessed with
1020/// a gep instruction with the specified parameters.
1021///
1022/// The Idxs pointer should point to a continuous piece of memory containing the
1023/// indices, either as Value* or uint64_t.
1024///
1025/// A null type is returned if the indices are invalid for the specified
1026/// pointer type.
1027///
1028template <typename IndexTy>
1029static Type *getIndexedTypeInternal(Type *Ptr, ArrayRef<IndexTy> IdxList) {
1030  PointerType *PTy = dyn_cast<PointerType>(Ptr);
1031  if (!PTy) return 0;   // Type isn't a pointer type!
1032  Type *Agg = PTy->getElementType();
1033
1034  // Handle the special case of the empty set index set, which is always valid.
1035  if (IdxList.empty())
1036    return Agg;
1037
1038  // If there is at least one index, the top level type must be sized, otherwise
1039  // it cannot be 'stepped over'.
1040  if (!Agg->isSized())
1041    return 0;
1042
1043  unsigned CurIdx = 1;
1044  for (; CurIdx != IdxList.size(); ++CurIdx) {
1045    CompositeType *CT = dyn_cast<CompositeType>(Agg);
1046    if (!CT || CT->isPointerTy()) return 0;
1047    IndexTy Index = IdxList[CurIdx];
1048    if (!CT->indexValid(Index)) return 0;
1049    Agg = CT->getTypeAtIndex(Index);
1050  }
1051  return CurIdx == IdxList.size() ? Agg : 0;
1052}
1053
1054Type *GetElementPtrInst::getIndexedType(Type *Ptr, ArrayRef<Value *> IdxList) {
1055  return getIndexedTypeInternal(Ptr, IdxList);
1056}
1057
1058Type *GetElementPtrInst::getIndexedType(Type *Ptr,
1059                                        ArrayRef<Constant *> IdxList) {
1060  return getIndexedTypeInternal(Ptr, IdxList);
1061}
1062
1063Type *GetElementPtrInst::getIndexedType(Type *Ptr, ArrayRef<uint64_t> IdxList) {
1064  return getIndexedTypeInternal(Ptr, IdxList);
1065}
1066
1067/// hasAllZeroIndices - Return true if all of the indices of this GEP are
1068/// zeros.  If so, the result pointer and the first operand have the same
1069/// value, just potentially different types.
1070bool GetElementPtrInst::hasAllZeroIndices() const {
1071  for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
1072    if (ConstantInt *CI = dyn_cast<ConstantInt>(getOperand(i))) {
1073      if (!CI->isZero()) return false;
1074    } else {
1075      return false;
1076    }
1077  }
1078  return true;
1079}
1080
1081/// hasAllConstantIndices - Return true if all of the indices of this GEP are
1082/// constant integers.  If so, the result pointer and the first operand have
1083/// a constant offset between them.
1084bool GetElementPtrInst::hasAllConstantIndices() const {
1085  for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
1086    if (!isa<ConstantInt>(getOperand(i)))
1087      return false;
1088  }
1089  return true;
1090}
1091
1092void GetElementPtrInst::setIsInBounds(bool B) {
1093  cast<GEPOperator>(this)->setIsInBounds(B);
1094}
1095
1096bool GetElementPtrInst::isInBounds() const {
1097  return cast<GEPOperator>(this)->isInBounds();
1098}
1099
1100//===----------------------------------------------------------------------===//
1101//                           ExtractElementInst Implementation
1102//===----------------------------------------------------------------------===//
1103
1104ExtractElementInst::ExtractElementInst(Value *Val, Value *Index,
1105                                       const Twine &Name,
1106                                       Instruction *InsertBef)
1107  : Instruction(cast<VectorType>(Val->getType())->getElementType(),
1108                ExtractElement,
1109                OperandTraits<ExtractElementInst>::op_begin(this),
1110                2, InsertBef) {
1111  assert(isValidOperands(Val, Index) &&
1112         "Invalid extractelement instruction operands!");
1113  Op<0>() = Val;
1114  Op<1>() = Index;
1115  setName(Name);
1116}
1117
1118ExtractElementInst::ExtractElementInst(Value *Val, Value *Index,
1119                                       const Twine &Name,
1120                                       BasicBlock *InsertAE)
1121  : Instruction(cast<VectorType>(Val->getType())->getElementType(),
1122                ExtractElement,
1123                OperandTraits<ExtractElementInst>::op_begin(this),
1124                2, InsertAE) {
1125  assert(isValidOperands(Val, Index) &&
1126         "Invalid extractelement instruction operands!");
1127
1128  Op<0>() = Val;
1129  Op<1>() = Index;
1130  setName(Name);
1131}
1132
1133
1134bool ExtractElementInst::isValidOperands(const Value *Val, const Value *Index) {
1135  if (!Val->getType()->isVectorTy() || !Index->getType()->isIntegerTy(32))
1136    return false;
1137  return true;
1138}
1139
1140
1141//===----------------------------------------------------------------------===//
1142//                           InsertElementInst Implementation
1143//===----------------------------------------------------------------------===//
1144
1145InsertElementInst::InsertElementInst(Value *Vec, Value *Elt, Value *Index,
1146                                     const Twine &Name,
1147                                     Instruction *InsertBef)
1148  : Instruction(Vec->getType(), InsertElement,
1149                OperandTraits<InsertElementInst>::op_begin(this),
1150                3, InsertBef) {
1151  assert(isValidOperands(Vec, Elt, Index) &&
1152         "Invalid insertelement instruction operands!");
1153  Op<0>() = Vec;
1154  Op<1>() = Elt;
1155  Op<2>() = Index;
1156  setName(Name);
1157}
1158
1159InsertElementInst::InsertElementInst(Value *Vec, Value *Elt, Value *Index,
1160                                     const Twine &Name,
1161                                     BasicBlock *InsertAE)
1162  : Instruction(Vec->getType(), InsertElement,
1163                OperandTraits<InsertElementInst>::op_begin(this),
1164                3, InsertAE) {
1165  assert(isValidOperands(Vec, Elt, Index) &&
1166         "Invalid insertelement instruction operands!");
1167
1168  Op<0>() = Vec;
1169  Op<1>() = Elt;
1170  Op<2>() = Index;
1171  setName(Name);
1172}
1173
1174bool InsertElementInst::isValidOperands(const Value *Vec, const Value *Elt,
1175                                        const Value *Index) {
1176  if (!Vec->getType()->isVectorTy())
1177    return false;   // First operand of insertelement must be vector type.
1178
1179  if (Elt->getType() != cast<VectorType>(Vec->getType())->getElementType())
1180    return false;// Second operand of insertelement must be vector element type.
1181
1182  if (!Index->getType()->isIntegerTy(32))
1183    return false;  // Third operand of insertelement must be i32.
1184  return true;
1185}
1186
1187
1188//===----------------------------------------------------------------------===//
1189//                      ShuffleVectorInst Implementation
1190//===----------------------------------------------------------------------===//
1191
1192ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *V2, Value *Mask,
1193                                     const Twine &Name,
1194                                     Instruction *InsertBefore)
1195: Instruction(VectorType::get(cast<VectorType>(V1->getType())->getElementType(),
1196                cast<VectorType>(Mask->getType())->getNumElements()),
1197              ShuffleVector,
1198              OperandTraits<ShuffleVectorInst>::op_begin(this),
1199              OperandTraits<ShuffleVectorInst>::operands(this),
1200              InsertBefore) {
1201  assert(isValidOperands(V1, V2, Mask) &&
1202         "Invalid shuffle vector instruction operands!");
1203  Op<0>() = V1;
1204  Op<1>() = V2;
1205  Op<2>() = Mask;
1206  setName(Name);
1207}
1208
1209ShuffleVectorInst::ShuffleVectorInst(Value *V1, Value *V2, Value *Mask,
1210                                     const Twine &Name,
1211                                     BasicBlock *InsertAtEnd)
1212: Instruction(VectorType::get(cast<VectorType>(V1->getType())->getElementType(),
1213                cast<VectorType>(Mask->getType())->getNumElements()),
1214              ShuffleVector,
1215              OperandTraits<ShuffleVectorInst>::op_begin(this),
1216              OperandTraits<ShuffleVectorInst>::operands(this),
1217              InsertAtEnd) {
1218  assert(isValidOperands(V1, V2, Mask) &&
1219         "Invalid shuffle vector instruction operands!");
1220
1221  Op<0>() = V1;
1222  Op<1>() = V2;
1223  Op<2>() = Mask;
1224  setName(Name);
1225}
1226
1227bool ShuffleVectorInst::isValidOperands(const Value *V1, const Value *V2,
1228                                        const Value *Mask) {
1229  if (!V1->getType()->isVectorTy() || V1->getType() != V2->getType())
1230    return false;
1231
1232  VectorType *MaskTy = dyn_cast<VectorType>(Mask->getType());
1233  if (MaskTy == 0 || !MaskTy->getElementType()->isIntegerTy(32))
1234    return false;
1235
1236  // Check to see if Mask is valid.
1237  if (const ConstantVector *MV = dyn_cast<ConstantVector>(Mask)) {
1238    VectorType *VTy = cast<VectorType>(V1->getType());
1239    for (unsigned i = 0, e = MV->getNumOperands(); i != e; ++i) {
1240      if (ConstantInt* CI = dyn_cast<ConstantInt>(MV->getOperand(i))) {
1241        if (CI->uge(VTy->getNumElements()*2))
1242          return false;
1243      } else if (!isa<UndefValue>(MV->getOperand(i))) {
1244        return false;
1245      }
1246    }
1247  }
1248  else if (!isa<UndefValue>(Mask) && !isa<ConstantAggregateZero>(Mask))
1249    return false;
1250
1251  return true;
1252}
1253
1254/// getMaskValue - Return the index from the shuffle mask for the specified
1255/// output result.  This is either -1 if the element is undef or a number less
1256/// than 2*numelements.
1257int ShuffleVectorInst::getMaskValue(unsigned i) const {
1258  const Constant *Mask = cast<Constant>(getOperand(2));
1259  if (isa<UndefValue>(Mask)) return -1;
1260  if (isa<ConstantAggregateZero>(Mask)) return 0;
1261  const ConstantVector *MaskCV = cast<ConstantVector>(Mask);
1262  assert(i < MaskCV->getNumOperands() && "Index out of range");
1263
1264  if (isa<UndefValue>(MaskCV->getOperand(i)))
1265    return -1;
1266  return cast<ConstantInt>(MaskCV->getOperand(i))->getZExtValue();
1267}
1268
1269//===----------------------------------------------------------------------===//
1270//                             InsertValueInst Class
1271//===----------------------------------------------------------------------===//
1272
1273void InsertValueInst::init(Value *Agg, Value *Val, ArrayRef<unsigned> Idxs,
1274                           const Twine &Name) {
1275  assert(NumOperands == 2 && "NumOperands not initialized?");
1276
1277  // There's no fundamental reason why we require at least one index
1278  // (other than weirdness with &*IdxBegin being invalid; see
1279  // getelementptr's init routine for example). But there's no
1280  // present need to support it.
1281  assert(Idxs.size() > 0 && "InsertValueInst must have at least one index");
1282
1283  assert(ExtractValueInst::getIndexedType(Agg->getType(), Idxs) ==
1284         Val->getType() && "Inserted value must match indexed type!");
1285  Op<0>() = Agg;
1286  Op<1>() = Val;
1287
1288  Indices.append(Idxs.begin(), Idxs.end());
1289  setName(Name);
1290}
1291
1292InsertValueInst::InsertValueInst(const InsertValueInst &IVI)
1293  : Instruction(IVI.getType(), InsertValue,
1294                OperandTraits<InsertValueInst>::op_begin(this), 2),
1295    Indices(IVI.Indices) {
1296  Op<0>() = IVI.getOperand(0);
1297  Op<1>() = IVI.getOperand(1);
1298  SubclassOptionalData = IVI.SubclassOptionalData;
1299}
1300
1301//===----------------------------------------------------------------------===//
1302//                             ExtractValueInst Class
1303//===----------------------------------------------------------------------===//
1304
1305void ExtractValueInst::init(ArrayRef<unsigned> Idxs, const Twine &Name) {
1306  assert(NumOperands == 1 && "NumOperands not initialized?");
1307
1308  // There's no fundamental reason why we require at least one index.
1309  // But there's no present need to support it.
1310  assert(Idxs.size() > 0 && "ExtractValueInst must have at least one index");
1311
1312  Indices.append(Idxs.begin(), Idxs.end());
1313  setName(Name);
1314}
1315
1316ExtractValueInst::ExtractValueInst(const ExtractValueInst &EVI)
1317  : UnaryInstruction(EVI.getType(), ExtractValue, EVI.getOperand(0)),
1318    Indices(EVI.Indices) {
1319  SubclassOptionalData = EVI.SubclassOptionalData;
1320}
1321
1322// getIndexedType - Returns the type of the element that would be extracted
1323// with an extractvalue instruction with the specified parameters.
1324//
1325// A null type is returned if the indices are invalid for the specified
1326// pointer type.
1327//
1328Type *ExtractValueInst::getIndexedType(Type *Agg,
1329                                       ArrayRef<unsigned> Idxs) {
1330  for (unsigned CurIdx = 0; CurIdx != Idxs.size(); ++CurIdx) {
1331    unsigned Index = Idxs[CurIdx];
1332    // We can't use CompositeType::indexValid(Index) here.
1333    // indexValid() always returns true for arrays because getelementptr allows
1334    // out-of-bounds indices. Since we don't allow those for extractvalue and
1335    // insertvalue we need to check array indexing manually.
1336    // Since the only other types we can index into are struct types it's just
1337    // as easy to check those manually as well.
1338    if (ArrayType *AT = dyn_cast<ArrayType>(Agg)) {
1339      if (Index >= AT->getNumElements())
1340        return 0;
1341    } else if (StructType *ST = dyn_cast<StructType>(Agg)) {
1342      if (Index >= ST->getNumElements())
1343        return 0;
1344    } else {
1345      // Not a valid type to index into.
1346      return 0;
1347    }
1348
1349    Agg = cast<CompositeType>(Agg)->getTypeAtIndex(Index);
1350  }
1351  return const_cast<Type*>(Agg);
1352}
1353
1354//===----------------------------------------------------------------------===//
1355//                             BinaryOperator Class
1356//===----------------------------------------------------------------------===//
1357
1358BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
1359                               Type *Ty, const Twine &Name,
1360                               Instruction *InsertBefore)
1361  : Instruction(Ty, iType,
1362                OperandTraits<BinaryOperator>::op_begin(this),
1363                OperandTraits<BinaryOperator>::operands(this),
1364                InsertBefore) {
1365  Op<0>() = S1;
1366  Op<1>() = S2;
1367  init(iType);
1368  setName(Name);
1369}
1370
1371BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
1372                               Type *Ty, const Twine &Name,
1373                               BasicBlock *InsertAtEnd)
1374  : Instruction(Ty, iType,
1375                OperandTraits<BinaryOperator>::op_begin(this),
1376                OperandTraits<BinaryOperator>::operands(this),
1377                InsertAtEnd) {
1378  Op<0>() = S1;
1379  Op<1>() = S2;
1380  init(iType);
1381  setName(Name);
1382}
1383
1384
1385void BinaryOperator::init(BinaryOps iType) {
1386  Value *LHS = getOperand(0), *RHS = getOperand(1);
1387  (void)LHS; (void)RHS; // Silence warnings.
1388  assert(LHS->getType() == RHS->getType() &&
1389         "Binary operator operand types must match!");
1390#ifndef NDEBUG
1391  switch (iType) {
1392  case Add: case Sub:
1393  case Mul:
1394    assert(getType() == LHS->getType() &&
1395           "Arithmetic operation should return same type as operands!");
1396    assert(getType()->isIntOrIntVectorTy() &&
1397           "Tried to create an integer operation on a non-integer type!");
1398    break;
1399  case FAdd: case FSub:
1400  case FMul:
1401    assert(getType() == LHS->getType() &&
1402           "Arithmetic operation should return same type as operands!");
1403    assert(getType()->isFPOrFPVectorTy() &&
1404           "Tried to create a floating-point operation on a "
1405           "non-floating-point type!");
1406    break;
1407  case UDiv:
1408  case SDiv:
1409    assert(getType() == LHS->getType() &&
1410           "Arithmetic operation should return same type as operands!");
1411    assert((getType()->isIntegerTy() || (getType()->isVectorTy() &&
1412            cast<VectorType>(getType())->getElementType()->isIntegerTy())) &&
1413           "Incorrect operand type (not integer) for S/UDIV");
1414    break;
1415  case FDiv:
1416    assert(getType() == LHS->getType() &&
1417           "Arithmetic operation should return same type as operands!");
1418    assert(getType()->isFPOrFPVectorTy() &&
1419           "Incorrect operand type (not floating point) for FDIV");
1420    break;
1421  case URem:
1422  case SRem:
1423    assert(getType() == LHS->getType() &&
1424           "Arithmetic operation should return same type as operands!");
1425    assert((getType()->isIntegerTy() || (getType()->isVectorTy() &&
1426            cast<VectorType>(getType())->getElementType()->isIntegerTy())) &&
1427           "Incorrect operand type (not integer) for S/UREM");
1428    break;
1429  case FRem:
1430    assert(getType() == LHS->getType() &&
1431           "Arithmetic operation should return same type as operands!");
1432    assert(getType()->isFPOrFPVectorTy() &&
1433           "Incorrect operand type (not floating point) for FREM");
1434    break;
1435  case Shl:
1436  case LShr:
1437  case AShr:
1438    assert(getType() == LHS->getType() &&
1439           "Shift operation should return same type as operands!");
1440    assert((getType()->isIntegerTy() ||
1441            (getType()->isVectorTy() &&
1442             cast<VectorType>(getType())->getElementType()->isIntegerTy())) &&
1443           "Tried to create a shift operation on a non-integral type!");
1444    break;
1445  case And: case Or:
1446  case Xor:
1447    assert(getType() == LHS->getType() &&
1448           "Logical operation should return same type as operands!");
1449    assert((getType()->isIntegerTy() ||
1450            (getType()->isVectorTy() &&
1451             cast<VectorType>(getType())->getElementType()->isIntegerTy())) &&
1452           "Tried to create a logical operation on a non-integral type!");
1453    break;
1454  default:
1455    break;
1456  }
1457#endif
1458}
1459
1460BinaryOperator *BinaryOperator::Create(BinaryOps Op, Value *S1, Value *S2,
1461                                       const Twine &Name,
1462                                       Instruction *InsertBefore) {
1463  assert(S1->getType() == S2->getType() &&
1464         "Cannot create binary operator with two operands of differing type!");
1465  return new BinaryOperator(Op, S1, S2, S1->getType(), Name, InsertBefore);
1466}
1467
1468BinaryOperator *BinaryOperator::Create(BinaryOps Op, Value *S1, Value *S2,
1469                                       const Twine &Name,
1470                                       BasicBlock *InsertAtEnd) {
1471  BinaryOperator *Res = Create(Op, S1, S2, Name);
1472  InsertAtEnd->getInstList().push_back(Res);
1473  return Res;
1474}
1475
1476BinaryOperator *BinaryOperator::CreateNeg(Value *Op, const Twine &Name,
1477                                          Instruction *InsertBefore) {
1478  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1479  return new BinaryOperator(Instruction::Sub,
1480                            zero, Op,
1481                            Op->getType(), Name, InsertBefore);
1482}
1483
1484BinaryOperator *BinaryOperator::CreateNeg(Value *Op, const Twine &Name,
1485                                          BasicBlock *InsertAtEnd) {
1486  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1487  return new BinaryOperator(Instruction::Sub,
1488                            zero, Op,
1489                            Op->getType(), Name, InsertAtEnd);
1490}
1491
1492BinaryOperator *BinaryOperator::CreateNSWNeg(Value *Op, const Twine &Name,
1493                                             Instruction *InsertBefore) {
1494  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1495  return BinaryOperator::CreateNSWSub(zero, Op, Name, InsertBefore);
1496}
1497
1498BinaryOperator *BinaryOperator::CreateNSWNeg(Value *Op, const Twine &Name,
1499                                             BasicBlock *InsertAtEnd) {
1500  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1501  return BinaryOperator::CreateNSWSub(zero, Op, Name, InsertAtEnd);
1502}
1503
1504BinaryOperator *BinaryOperator::CreateNUWNeg(Value *Op, const Twine &Name,
1505                                             Instruction *InsertBefore) {
1506  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1507  return BinaryOperator::CreateNUWSub(zero, Op, Name, InsertBefore);
1508}
1509
1510BinaryOperator *BinaryOperator::CreateNUWNeg(Value *Op, const Twine &Name,
1511                                             BasicBlock *InsertAtEnd) {
1512  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1513  return BinaryOperator::CreateNUWSub(zero, Op, Name, InsertAtEnd);
1514}
1515
1516BinaryOperator *BinaryOperator::CreateFNeg(Value *Op, const Twine &Name,
1517                                           Instruction *InsertBefore) {
1518  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1519  return new BinaryOperator(Instruction::FSub,
1520                            zero, Op,
1521                            Op->getType(), Name, InsertBefore);
1522}
1523
1524BinaryOperator *BinaryOperator::CreateFNeg(Value *Op, const Twine &Name,
1525                                           BasicBlock *InsertAtEnd) {
1526  Value *zero = ConstantFP::getZeroValueForNegation(Op->getType());
1527  return new BinaryOperator(Instruction::FSub,
1528                            zero, Op,
1529                            Op->getType(), Name, InsertAtEnd);
1530}
1531
1532BinaryOperator *BinaryOperator::CreateNot(Value *Op, const Twine &Name,
1533                                          Instruction *InsertBefore) {
1534  Constant *C;
1535  if (VectorType *PTy = dyn_cast<VectorType>(Op->getType())) {
1536    C = Constant::getAllOnesValue(PTy->getElementType());
1537    C = ConstantVector::get(
1538                              std::vector<Constant*>(PTy->getNumElements(), C));
1539  } else {
1540    C = Constant::getAllOnesValue(Op->getType());
1541  }
1542
1543  return new BinaryOperator(Instruction::Xor, Op, C,
1544                            Op->getType(), Name, InsertBefore);
1545}
1546
1547BinaryOperator *BinaryOperator::CreateNot(Value *Op, const Twine &Name,
1548                                          BasicBlock *InsertAtEnd) {
1549  Constant *AllOnes;
1550  if (VectorType *PTy = dyn_cast<VectorType>(Op->getType())) {
1551    // Create a vector of all ones values.
1552    Constant *Elt = Constant::getAllOnesValue(PTy->getElementType());
1553    AllOnes = ConstantVector::get(
1554                            std::vector<Constant*>(PTy->getNumElements(), Elt));
1555  } else {
1556    AllOnes = Constant::getAllOnesValue(Op->getType());
1557  }
1558
1559  return new BinaryOperator(Instruction::Xor, Op, AllOnes,
1560                            Op->getType(), Name, InsertAtEnd);
1561}
1562
1563
1564// isConstantAllOnes - Helper function for several functions below
1565static inline bool isConstantAllOnes(const Value *V) {
1566  if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
1567    return CI->isAllOnesValue();
1568  if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
1569    return CV->isAllOnesValue();
1570  return false;
1571}
1572
1573bool BinaryOperator::isNeg(const Value *V) {
1574  if (const BinaryOperator *Bop = dyn_cast<BinaryOperator>(V))
1575    if (Bop->getOpcode() == Instruction::Sub)
1576      if (Constant* C = dyn_cast<Constant>(Bop->getOperand(0)))
1577        return C->isNegativeZeroValue();
1578  return false;
1579}
1580
1581bool BinaryOperator::isFNeg(const Value *V) {
1582  if (const BinaryOperator *Bop = dyn_cast<BinaryOperator>(V))
1583    if (Bop->getOpcode() == Instruction::FSub)
1584      if (Constant* C = dyn_cast<Constant>(Bop->getOperand(0)))
1585        return C->isNegativeZeroValue();
1586  return false;
1587}
1588
1589bool BinaryOperator::isNot(const Value *V) {
1590  if (const BinaryOperator *Bop = dyn_cast<BinaryOperator>(V))
1591    return (Bop->getOpcode() == Instruction::Xor &&
1592            (isConstantAllOnes(Bop->getOperand(1)) ||
1593             isConstantAllOnes(Bop->getOperand(0))));
1594  return false;
1595}
1596
1597Value *BinaryOperator::getNegArgument(Value *BinOp) {
1598  return cast<BinaryOperator>(BinOp)->getOperand(1);
1599}
1600
1601const Value *BinaryOperator::getNegArgument(const Value *BinOp) {
1602  return getNegArgument(const_cast<Value*>(BinOp));
1603}
1604
1605Value *BinaryOperator::getFNegArgument(Value *BinOp) {
1606  return cast<BinaryOperator>(BinOp)->getOperand(1);
1607}
1608
1609const Value *BinaryOperator::getFNegArgument(const Value *BinOp) {
1610  return getFNegArgument(const_cast<Value*>(BinOp));
1611}
1612
1613Value *BinaryOperator::getNotArgument(Value *BinOp) {
1614  assert(isNot(BinOp) && "getNotArgument on non-'not' instruction!");
1615  BinaryOperator *BO = cast<BinaryOperator>(BinOp);
1616  Value *Op0 = BO->getOperand(0);
1617  Value *Op1 = BO->getOperand(1);
1618  if (isConstantAllOnes(Op0)) return Op1;
1619
1620  assert(isConstantAllOnes(Op1));
1621  return Op0;
1622}
1623
1624const Value *BinaryOperator::getNotArgument(const Value *BinOp) {
1625  return getNotArgument(const_cast<Value*>(BinOp));
1626}
1627
1628
1629// swapOperands - Exchange the two operands to this instruction.  This
1630// instruction is safe to use on any binary instruction and does not
1631// modify the semantics of the instruction.  If the instruction is
1632// order dependent (SetLT f.e.) the opcode is changed.
1633//
1634bool BinaryOperator::swapOperands() {
1635  if (!isCommutative())
1636    return true; // Can't commute operands
1637  Op<0>().swap(Op<1>());
1638  return false;
1639}
1640
1641void BinaryOperator::setHasNoUnsignedWrap(bool b) {
1642  cast<OverflowingBinaryOperator>(this)->setHasNoUnsignedWrap(b);
1643}
1644
1645void BinaryOperator::setHasNoSignedWrap(bool b) {
1646  cast<OverflowingBinaryOperator>(this)->setHasNoSignedWrap(b);
1647}
1648
1649void BinaryOperator::setIsExact(bool b) {
1650  cast<PossiblyExactOperator>(this)->setIsExact(b);
1651}
1652
1653bool BinaryOperator::hasNoUnsignedWrap() const {
1654  return cast<OverflowingBinaryOperator>(this)->hasNoUnsignedWrap();
1655}
1656
1657bool BinaryOperator::hasNoSignedWrap() const {
1658  return cast<OverflowingBinaryOperator>(this)->hasNoSignedWrap();
1659}
1660
1661bool BinaryOperator::isExact() const {
1662  return cast<PossiblyExactOperator>(this)->isExact();
1663}
1664
1665//===----------------------------------------------------------------------===//
1666//                                CastInst Class
1667//===----------------------------------------------------------------------===//
1668
1669// Just determine if this cast only deals with integral->integral conversion.
1670bool CastInst::isIntegerCast() const {
1671  switch (getOpcode()) {
1672    default: return false;
1673    case Instruction::ZExt:
1674    case Instruction::SExt:
1675    case Instruction::Trunc:
1676      return true;
1677    case Instruction::BitCast:
1678      return getOperand(0)->getType()->isIntegerTy() &&
1679        getType()->isIntegerTy();
1680  }
1681}
1682
1683bool CastInst::isLosslessCast() const {
1684  // Only BitCast can be lossless, exit fast if we're not BitCast
1685  if (getOpcode() != Instruction::BitCast)
1686    return false;
1687
1688  // Identity cast is always lossless
1689  Type* SrcTy = getOperand(0)->getType();
1690  Type* DstTy = getType();
1691  if (SrcTy == DstTy)
1692    return true;
1693
1694  // Pointer to pointer is always lossless.
1695  if (SrcTy->isPointerTy())
1696    return DstTy->isPointerTy();
1697  return false;  // Other types have no identity values
1698}
1699
1700/// This function determines if the CastInst does not require any bits to be
1701/// changed in order to effect the cast. Essentially, it identifies cases where
1702/// no code gen is necessary for the cast, hence the name no-op cast.  For
1703/// example, the following are all no-op casts:
1704/// # bitcast i32* %x to i8*
1705/// # bitcast <2 x i32> %x to <4 x i16>
1706/// # ptrtoint i32* %x to i32     ; on 32-bit plaforms only
1707/// @brief Determine if the described cast is a no-op.
1708bool CastInst::isNoopCast(Instruction::CastOps Opcode,
1709                          Type *SrcTy,
1710                          Type *DestTy,
1711                          Type *IntPtrTy) {
1712  switch (Opcode) {
1713    default:
1714      assert(!"Invalid CastOp");
1715    case Instruction::Trunc:
1716    case Instruction::ZExt:
1717    case Instruction::SExt:
1718    case Instruction::FPTrunc:
1719    case Instruction::FPExt:
1720    case Instruction::UIToFP:
1721    case Instruction::SIToFP:
1722    case Instruction::FPToUI:
1723    case Instruction::FPToSI:
1724      return false; // These always modify bits
1725    case Instruction::BitCast:
1726      return true;  // BitCast never modifies bits.
1727    case Instruction::PtrToInt:
1728      return IntPtrTy->getScalarSizeInBits() ==
1729             DestTy->getScalarSizeInBits();
1730    case Instruction::IntToPtr:
1731      return IntPtrTy->getScalarSizeInBits() ==
1732             SrcTy->getScalarSizeInBits();
1733  }
1734}
1735
1736/// @brief Determine if a cast is a no-op.
1737bool CastInst::isNoopCast(Type *IntPtrTy) const {
1738  return isNoopCast(getOpcode(), getOperand(0)->getType(), getType(), IntPtrTy);
1739}
1740
1741/// This function determines if a pair of casts can be eliminated and what
1742/// opcode should be used in the elimination. This assumes that there are two
1743/// instructions like this:
1744/// *  %F = firstOpcode SrcTy %x to MidTy
1745/// *  %S = secondOpcode MidTy %F to DstTy
1746/// The function returns a resultOpcode so these two casts can be replaced with:
1747/// *  %Replacement = resultOpcode %SrcTy %x to DstTy
1748/// If no such cast is permited, the function returns 0.
1749unsigned CastInst::isEliminableCastPair(
1750  Instruction::CastOps firstOp, Instruction::CastOps secondOp,
1751  Type *SrcTy, Type *MidTy, Type *DstTy, Type *IntPtrTy)
1752{
1753  // Define the 144 possibilities for these two cast instructions. The values
1754  // in this matrix determine what to do in a given situation and select the
1755  // case in the switch below.  The rows correspond to firstOp, the columns
1756  // correspond to secondOp.  In looking at the table below, keep in  mind
1757  // the following cast properties:
1758  //
1759  //          Size Compare       Source               Destination
1760  // Operator  Src ? Size   Type       Sign         Type       Sign
1761  // -------- ------------ -------------------   ---------------------
1762  // TRUNC         >       Integer      Any        Integral     Any
1763  // ZEXT          <       Integral   Unsigned     Integer      Any
1764  // SEXT          <       Integral    Signed      Integer      Any
1765  // FPTOUI       n/a      FloatPt      n/a        Integral   Unsigned
1766  // FPTOSI       n/a      FloatPt      n/a        Integral    Signed
1767  // UITOFP       n/a      Integral   Unsigned     FloatPt      n/a
1768  // SITOFP       n/a      Integral    Signed      FloatPt      n/a
1769  // FPTRUNC       >       FloatPt      n/a        FloatPt      n/a
1770  // FPEXT         <       FloatPt      n/a        FloatPt      n/a
1771  // PTRTOINT     n/a      Pointer      n/a        Integral   Unsigned
1772  // INTTOPTR     n/a      Integral   Unsigned     Pointer      n/a
1773  // BITCAST       =       FirstClass   n/a       FirstClass    n/a
1774  //
1775  // NOTE: some transforms are safe, but we consider them to be non-profitable.
1776  // For example, we could merge "fptoui double to i32" + "zext i32 to i64",
1777  // into "fptoui double to i64", but this loses information about the range
1778  // of the produced value (we no longer know the top-part is all zeros).
1779  // Further this conversion is often much more expensive for typical hardware,
1780  // and causes issues when building libgcc.  We disallow fptosi+sext for the
1781  // same reason.
1782  const unsigned numCastOps =
1783    Instruction::CastOpsEnd - Instruction::CastOpsBegin;
1784  static const uint8_t CastResults[numCastOps][numCastOps] = {
1785    // T        F  F  U  S  F  F  P  I  B   -+
1786    // R  Z  S  P  P  I  I  T  P  2  N  T    |
1787    // U  E  E  2  2  2  2  R  E  I  T  C    +- secondOp
1788    // N  X  X  U  S  F  F  N  X  N  2  V    |
1789    // C  T  T  I  I  P  P  C  T  T  P  T   -+
1790    {  1, 0, 0,99,99, 0, 0,99,99,99, 0, 3 }, // Trunc      -+
1791    {  8, 1, 9,99,99, 2, 0,99,99,99, 2, 3 }, // ZExt        |
1792    {  8, 0, 1,99,99, 0, 2,99,99,99, 0, 3 }, // SExt        |
1793    {  0, 0, 0,99,99, 0, 0,99,99,99, 0, 3 }, // FPToUI      |
1794    {  0, 0, 0,99,99, 0, 0,99,99,99, 0, 3 }, // FPToSI      |
1795    { 99,99,99, 0, 0,99,99, 0, 0,99,99, 4 }, // UIToFP      +- firstOp
1796    { 99,99,99, 0, 0,99,99, 0, 0,99,99, 4 }, // SIToFP      |
1797    { 99,99,99, 0, 0,99,99, 1, 0,99,99, 4 }, // FPTrunc     |
1798    { 99,99,99, 2, 2,99,99,10, 2,99,99, 4 }, // FPExt       |
1799    {  1, 0, 0,99,99, 0, 0,99,99,99, 7, 3 }, // PtrToInt    |
1800    { 99,99,99,99,99,99,99,99,99,13,99,12 }, // IntToPtr    |
1801    {  5, 5, 5, 6, 6, 5, 5, 6, 6,11, 5, 1 }, // BitCast    -+
1802  };
1803
1804  // If either of the casts are a bitcast from scalar to vector, disallow the
1805  // merging.
1806  if ((firstOp == Instruction::BitCast &&
1807       isa<VectorType>(SrcTy) != isa<VectorType>(MidTy)) ||
1808      (secondOp == Instruction::BitCast &&
1809       isa<VectorType>(MidTy) != isa<VectorType>(DstTy)))
1810    return 0; // Disallowed
1811
1812  int ElimCase = CastResults[firstOp-Instruction::CastOpsBegin]
1813                            [secondOp-Instruction::CastOpsBegin];
1814  switch (ElimCase) {
1815    case 0:
1816      // categorically disallowed
1817      return 0;
1818    case 1:
1819      // allowed, use first cast's opcode
1820      return firstOp;
1821    case 2:
1822      // allowed, use second cast's opcode
1823      return secondOp;
1824    case 3:
1825      // no-op cast in second op implies firstOp as long as the DestTy
1826      // is integer and we are not converting between a vector and a
1827      // non vector type.
1828      if (!SrcTy->isVectorTy() && DstTy->isIntegerTy())
1829        return firstOp;
1830      return 0;
1831    case 4:
1832      // no-op cast in second op implies firstOp as long as the DestTy
1833      // is floating point.
1834      if (DstTy->isFloatingPointTy())
1835        return firstOp;
1836      return 0;
1837    case 5:
1838      // no-op cast in first op implies secondOp as long as the SrcTy
1839      // is an integer.
1840      if (SrcTy->isIntegerTy())
1841        return secondOp;
1842      return 0;
1843    case 6:
1844      // no-op cast in first op implies secondOp as long as the SrcTy
1845      // is a floating point.
1846      if (SrcTy->isFloatingPointTy())
1847        return secondOp;
1848      return 0;
1849    case 7: {
1850      // ptrtoint, inttoptr -> bitcast (ptr -> ptr) if int size is >= ptr size
1851      if (!IntPtrTy)
1852        return 0;
1853      unsigned PtrSize = IntPtrTy->getScalarSizeInBits();
1854      unsigned MidSize = MidTy->getScalarSizeInBits();
1855      if (MidSize >= PtrSize)
1856        return Instruction::BitCast;
1857      return 0;
1858    }
1859    case 8: {
1860      // ext, trunc -> bitcast,    if the SrcTy and DstTy are same size
1861      // ext, trunc -> ext,        if sizeof(SrcTy) < sizeof(DstTy)
1862      // ext, trunc -> trunc,      if sizeof(SrcTy) > sizeof(DstTy)
1863      unsigned SrcSize = SrcTy->getScalarSizeInBits();
1864      unsigned DstSize = DstTy->getScalarSizeInBits();
1865      if (SrcSize == DstSize)
1866        return Instruction::BitCast;
1867      else if (SrcSize < DstSize)
1868        return firstOp;
1869      return secondOp;
1870    }
1871    case 9: // zext, sext -> zext, because sext can't sign extend after zext
1872      return Instruction::ZExt;
1873    case 10:
1874      // fpext followed by ftrunc is allowed if the bit size returned to is
1875      // the same as the original, in which case its just a bitcast
1876      if (SrcTy == DstTy)
1877        return Instruction::BitCast;
1878      return 0; // If the types are not the same we can't eliminate it.
1879    case 11:
1880      // bitcast followed by ptrtoint is allowed as long as the bitcast
1881      // is a pointer to pointer cast.
1882      if (SrcTy->isPointerTy() && MidTy->isPointerTy())
1883        return secondOp;
1884      return 0;
1885    case 12:
1886      // inttoptr, bitcast -> intptr  if bitcast is a ptr to ptr cast
1887      if (MidTy->isPointerTy() && DstTy->isPointerTy())
1888        return firstOp;
1889      return 0;
1890    case 13: {
1891      // inttoptr, ptrtoint -> bitcast if SrcSize<=PtrSize and SrcSize==DstSize
1892      if (!IntPtrTy)
1893        return 0;
1894      unsigned PtrSize = IntPtrTy->getScalarSizeInBits();
1895      unsigned SrcSize = SrcTy->getScalarSizeInBits();
1896      unsigned DstSize = DstTy->getScalarSizeInBits();
1897      if (SrcSize <= PtrSize && SrcSize == DstSize)
1898        return Instruction::BitCast;
1899      return 0;
1900    }
1901    case 99:
1902      // cast combination can't happen (error in input). This is for all cases
1903      // where the MidTy is not the same for the two cast instructions.
1904      assert(!"Invalid Cast Combination");
1905      return 0;
1906    default:
1907      assert(!"Error in CastResults table!!!");
1908      return 0;
1909  }
1910  return 0;
1911}
1912
1913CastInst *CastInst::Create(Instruction::CastOps op, Value *S, Type *Ty,
1914  const Twine &Name, Instruction *InsertBefore) {
1915  assert(castIsValid(op, S, Ty) && "Invalid cast!");
1916  // Construct and return the appropriate CastInst subclass
1917  switch (op) {
1918    case Trunc:    return new TruncInst    (S, Ty, Name, InsertBefore);
1919    case ZExt:     return new ZExtInst     (S, Ty, Name, InsertBefore);
1920    case SExt:     return new SExtInst     (S, Ty, Name, InsertBefore);
1921    case FPTrunc:  return new FPTruncInst  (S, Ty, Name, InsertBefore);
1922    case FPExt:    return new FPExtInst    (S, Ty, Name, InsertBefore);
1923    case UIToFP:   return new UIToFPInst   (S, Ty, Name, InsertBefore);
1924    case SIToFP:   return new SIToFPInst   (S, Ty, Name, InsertBefore);
1925    case FPToUI:   return new FPToUIInst   (S, Ty, Name, InsertBefore);
1926    case FPToSI:   return new FPToSIInst   (S, Ty, Name, InsertBefore);
1927    case PtrToInt: return new PtrToIntInst (S, Ty, Name, InsertBefore);
1928    case IntToPtr: return new IntToPtrInst (S, Ty, Name, InsertBefore);
1929    case BitCast:  return new BitCastInst  (S, Ty, Name, InsertBefore);
1930    default:
1931      assert(!"Invalid opcode provided");
1932  }
1933  return 0;
1934}
1935
1936CastInst *CastInst::Create(Instruction::CastOps op, Value *S, Type *Ty,
1937  const Twine &Name, BasicBlock *InsertAtEnd) {
1938  assert(castIsValid(op, S, Ty) && "Invalid cast!");
1939  // Construct and return the appropriate CastInst subclass
1940  switch (op) {
1941    case Trunc:    return new TruncInst    (S, Ty, Name, InsertAtEnd);
1942    case ZExt:     return new ZExtInst     (S, Ty, Name, InsertAtEnd);
1943    case SExt:     return new SExtInst     (S, Ty, Name, InsertAtEnd);
1944    case FPTrunc:  return new FPTruncInst  (S, Ty, Name, InsertAtEnd);
1945    case FPExt:    return new FPExtInst    (S, Ty, Name, InsertAtEnd);
1946    case UIToFP:   return new UIToFPInst   (S, Ty, Name, InsertAtEnd);
1947    case SIToFP:   return new SIToFPInst   (S, Ty, Name, InsertAtEnd);
1948    case FPToUI:   return new FPToUIInst   (S, Ty, Name, InsertAtEnd);
1949    case FPToSI:   return new FPToSIInst   (S, Ty, Name, InsertAtEnd);
1950    case PtrToInt: return new PtrToIntInst (S, Ty, Name, InsertAtEnd);
1951    case IntToPtr: return new IntToPtrInst (S, Ty, Name, InsertAtEnd);
1952    case BitCast:  return new BitCastInst  (S, Ty, Name, InsertAtEnd);
1953    default:
1954      assert(!"Invalid opcode provided");
1955  }
1956  return 0;
1957}
1958
1959CastInst *CastInst::CreateZExtOrBitCast(Value *S, Type *Ty,
1960                                        const Twine &Name,
1961                                        Instruction *InsertBefore) {
1962  if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1963    return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
1964  return Create(Instruction::ZExt, S, Ty, Name, InsertBefore);
1965}
1966
1967CastInst *CastInst::CreateZExtOrBitCast(Value *S, Type *Ty,
1968                                        const Twine &Name,
1969                                        BasicBlock *InsertAtEnd) {
1970  if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1971    return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
1972  return Create(Instruction::ZExt, S, Ty, Name, InsertAtEnd);
1973}
1974
1975CastInst *CastInst::CreateSExtOrBitCast(Value *S, Type *Ty,
1976                                        const Twine &Name,
1977                                        Instruction *InsertBefore) {
1978  if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1979    return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
1980  return Create(Instruction::SExt, S, Ty, Name, InsertBefore);
1981}
1982
1983CastInst *CastInst::CreateSExtOrBitCast(Value *S, Type *Ty,
1984                                        const Twine &Name,
1985                                        BasicBlock *InsertAtEnd) {
1986  if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1987    return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
1988  return Create(Instruction::SExt, S, Ty, Name, InsertAtEnd);
1989}
1990
1991CastInst *CastInst::CreateTruncOrBitCast(Value *S, Type *Ty,
1992                                         const Twine &Name,
1993                                         Instruction *InsertBefore) {
1994  if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
1995    return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
1996  return Create(Instruction::Trunc, S, Ty, Name, InsertBefore);
1997}
1998
1999CastInst *CastInst::CreateTruncOrBitCast(Value *S, Type *Ty,
2000                                         const Twine &Name,
2001                                         BasicBlock *InsertAtEnd) {
2002  if (S->getType()->getScalarSizeInBits() == Ty->getScalarSizeInBits())
2003    return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
2004  return Create(Instruction::Trunc, S, Ty, Name, InsertAtEnd);
2005}
2006
2007CastInst *CastInst::CreatePointerCast(Value *S, Type *Ty,
2008                                      const Twine &Name,
2009                                      BasicBlock *InsertAtEnd) {
2010  assert(S->getType()->isPointerTy() && "Invalid cast");
2011  assert((Ty->isIntegerTy() || Ty->isPointerTy()) &&
2012         "Invalid cast");
2013
2014  if (Ty->isIntegerTy())
2015    return Create(Instruction::PtrToInt, S, Ty, Name, InsertAtEnd);
2016  return Create(Instruction::BitCast, S, Ty, Name, InsertAtEnd);
2017}
2018
2019/// @brief Create a BitCast or a PtrToInt cast instruction
2020CastInst *CastInst::CreatePointerCast(Value *S, Type *Ty,
2021                                      const Twine &Name,
2022                                      Instruction *InsertBefore) {
2023  assert(S->getType()->isPointerTy() && "Invalid cast");
2024  assert((Ty->isIntegerTy() || Ty->isPointerTy()) &&
2025         "Invalid cast");
2026
2027  if (Ty->isIntegerTy())
2028    return Create(Instruction::PtrToInt, S, Ty, Name, InsertBefore);
2029  return Create(Instruction::BitCast, S, Ty, Name, InsertBefore);
2030}
2031
2032CastInst *CastInst::CreateIntegerCast(Value *C, Type *Ty,
2033                                      bool isSigned, const Twine &Name,
2034                                      Instruction *InsertBefore) {
2035  assert(C->getType()->isIntOrIntVectorTy() && Ty->isIntOrIntVectorTy() &&
2036         "Invalid integer cast");
2037  unsigned SrcBits = C->getType()->getScalarSizeInBits();
2038  unsigned DstBits = Ty->getScalarSizeInBits();
2039  Instruction::CastOps opcode =
2040    (SrcBits == DstBits ? Instruction::BitCast :
2041     (SrcBits > DstBits ? Instruction::Trunc :
2042      (isSigned ? Instruction::SExt : Instruction::ZExt)));
2043  return Create(opcode, C, Ty, Name, InsertBefore);
2044}
2045
2046CastInst *CastInst::CreateIntegerCast(Value *C, Type *Ty,
2047                                      bool isSigned, const Twine &Name,
2048                                      BasicBlock *InsertAtEnd) {
2049  assert(C->getType()->isIntOrIntVectorTy() && Ty->isIntOrIntVectorTy() &&
2050         "Invalid cast");
2051  unsigned SrcBits = C->getType()->getScalarSizeInBits();
2052  unsigned DstBits = Ty->getScalarSizeInBits();
2053  Instruction::CastOps opcode =
2054    (SrcBits == DstBits ? Instruction::BitCast :
2055     (SrcBits > DstBits ? Instruction::Trunc :
2056      (isSigned ? Instruction::SExt : Instruction::ZExt)));
2057  return Create(opcode, C, Ty, Name, InsertAtEnd);
2058}
2059
2060CastInst *CastInst::CreateFPCast(Value *C, Type *Ty,
2061                                 const Twine &Name,
2062                                 Instruction *InsertBefore) {
2063  assert(C->getType()->isFPOrFPVectorTy() && Ty->isFPOrFPVectorTy() &&
2064         "Invalid cast");
2065  unsigned SrcBits = C->getType()->getScalarSizeInBits();
2066  unsigned DstBits = Ty->getScalarSizeInBits();
2067  Instruction::CastOps opcode =
2068    (SrcBits == DstBits ? Instruction::BitCast :
2069     (SrcBits > DstBits ? Instruction::FPTrunc : Instruction::FPExt));
2070  return Create(opcode, C, Ty, Name, InsertBefore);
2071}
2072
2073CastInst *CastInst::CreateFPCast(Value *C, Type *Ty,
2074                                 const Twine &Name,
2075                                 BasicBlock *InsertAtEnd) {
2076  assert(C->getType()->isFPOrFPVectorTy() && Ty->isFPOrFPVectorTy() &&
2077         "Invalid cast");
2078  unsigned SrcBits = C->getType()->getScalarSizeInBits();
2079  unsigned DstBits = Ty->getScalarSizeInBits();
2080  Instruction::CastOps opcode =
2081    (SrcBits == DstBits ? Instruction::BitCast :
2082     (SrcBits > DstBits ? Instruction::FPTrunc : Instruction::FPExt));
2083  return Create(opcode, C, Ty, Name, InsertAtEnd);
2084}
2085
2086// Check whether it is valid to call getCastOpcode for these types.
2087// This routine must be kept in sync with getCastOpcode.
2088bool CastInst::isCastable(Type *SrcTy, Type *DestTy) {
2089  if (!SrcTy->isFirstClassType() || !DestTy->isFirstClassType())
2090    return false;
2091
2092  if (SrcTy == DestTy)
2093    return true;
2094
2095  if (VectorType *SrcVecTy = dyn_cast<VectorType>(SrcTy))
2096    if (VectorType *DestVecTy = dyn_cast<VectorType>(DestTy))
2097      if (SrcVecTy->getNumElements() == DestVecTy->getNumElements()) {
2098        // An element by element cast.  Valid if casting the elements is valid.
2099        SrcTy = SrcVecTy->getElementType();
2100        DestTy = DestVecTy->getElementType();
2101      }
2102
2103  // Get the bit sizes, we'll need these
2104  unsigned SrcBits = SrcTy->getPrimitiveSizeInBits();   // 0 for ptr
2105  unsigned DestBits = DestTy->getPrimitiveSizeInBits(); // 0 for ptr
2106
2107  // Run through the possibilities ...
2108  if (DestTy->isIntegerTy()) {               // Casting to integral
2109    if (SrcTy->isIntegerTy()) {                // Casting from integral
2110        return true;
2111    } else if (SrcTy->isFloatingPointTy()) {   // Casting from floating pt
2112      return true;
2113    } else if (SrcTy->isVectorTy()) {          // Casting from vector
2114      return DestBits == SrcBits;
2115    } else {                                   // Casting from something else
2116      return SrcTy->isPointerTy();
2117    }
2118  } else if (DestTy->isFloatingPointTy()) {  // Casting to floating pt
2119    if (SrcTy->isIntegerTy()) {                // Casting from integral
2120      return true;
2121    } else if (SrcTy->isFloatingPointTy()) {   // Casting from floating pt
2122      return true;
2123    } else if (SrcTy->isVectorTy()) {          // Casting from vector
2124      return DestBits == SrcBits;
2125    } else {                                   // Casting from something else
2126      return false;
2127    }
2128  } else if (DestTy->isVectorTy()) {         // Casting to vector
2129    return DestBits == SrcBits;
2130  } else if (DestTy->isPointerTy()) {        // Casting to pointer
2131    if (SrcTy->isPointerTy()) {                // Casting from pointer
2132      return true;
2133    } else if (SrcTy->isIntegerTy()) {         // Casting from integral
2134      return true;
2135    } else {                                   // Casting from something else
2136      return false;
2137    }
2138  } else if (DestTy->isX86_MMXTy()) {
2139    if (SrcTy->isVectorTy()) {
2140      return DestBits == SrcBits;       // 64-bit vector to MMX
2141    } else {
2142      return false;
2143    }
2144  } else {                                   // Casting to something else
2145    return false;
2146  }
2147}
2148
2149// Provide a way to get a "cast" where the cast opcode is inferred from the
2150// types and size of the operand. This, basically, is a parallel of the
2151// logic in the castIsValid function below.  This axiom should hold:
2152//   castIsValid( getCastOpcode(Val, Ty), Val, Ty)
2153// should not assert in castIsValid. In other words, this produces a "correct"
2154// casting opcode for the arguments passed to it.
2155// This routine must be kept in sync with isCastable.
2156Instruction::CastOps
2157CastInst::getCastOpcode(
2158  const Value *Src, bool SrcIsSigned, Type *DestTy, bool DestIsSigned) {
2159  Type *SrcTy = Src->getType();
2160
2161  assert(SrcTy->isFirstClassType() && DestTy->isFirstClassType() &&
2162         "Only first class types are castable!");
2163
2164  if (SrcTy == DestTy)
2165    return BitCast;
2166
2167  if (VectorType *SrcVecTy = dyn_cast<VectorType>(SrcTy))
2168    if (VectorType *DestVecTy = dyn_cast<VectorType>(DestTy))
2169      if (SrcVecTy->getNumElements() == DestVecTy->getNumElements()) {
2170        // An element by element cast.  Find the appropriate opcode based on the
2171        // element types.
2172        SrcTy = SrcVecTy->getElementType();
2173        DestTy = DestVecTy->getElementType();
2174      }
2175
2176  // Get the bit sizes, we'll need these
2177  unsigned SrcBits = SrcTy->getPrimitiveSizeInBits();   // 0 for ptr
2178  unsigned DestBits = DestTy->getPrimitiveSizeInBits(); // 0 for ptr
2179
2180  // Run through the possibilities ...
2181  if (DestTy->isIntegerTy()) {                      // Casting to integral
2182    if (SrcTy->isIntegerTy()) {                     // Casting from integral
2183      if (DestBits < SrcBits)
2184        return Trunc;                               // int -> smaller int
2185      else if (DestBits > SrcBits) {                // its an extension
2186        if (SrcIsSigned)
2187          return SExt;                              // signed -> SEXT
2188        else
2189          return ZExt;                              // unsigned -> ZEXT
2190      } else {
2191        return BitCast;                             // Same size, No-op cast
2192      }
2193    } else if (SrcTy->isFloatingPointTy()) {        // Casting from floating pt
2194      if (DestIsSigned)
2195        return FPToSI;                              // FP -> sint
2196      else
2197        return FPToUI;                              // FP -> uint
2198    } else if (SrcTy->isVectorTy()) {
2199      assert(DestBits == SrcBits &&
2200             "Casting vector to integer of different width");
2201      return BitCast;                             // Same size, no-op cast
2202    } else {
2203      assert(SrcTy->isPointerTy() &&
2204             "Casting from a value that is not first-class type");
2205      return PtrToInt;                              // ptr -> int
2206    }
2207  } else if (DestTy->isFloatingPointTy()) {         // Casting to floating pt
2208    if (SrcTy->isIntegerTy()) {                     // Casting from integral
2209      if (SrcIsSigned)
2210        return SIToFP;                              // sint -> FP
2211      else
2212        return UIToFP;                              // uint -> FP
2213    } else if (SrcTy->isFloatingPointTy()) {        // Casting from floating pt
2214      if (DestBits < SrcBits) {
2215        return FPTrunc;                             // FP -> smaller FP
2216      } else if (DestBits > SrcBits) {
2217        return FPExt;                               // FP -> larger FP
2218      } else  {
2219        return BitCast;                             // same size, no-op cast
2220      }
2221    } else if (SrcTy->isVectorTy()) {
2222      assert(DestBits == SrcBits &&
2223             "Casting vector to floating point of different width");
2224      return BitCast;                             // same size, no-op cast
2225    } else {
2226      llvm_unreachable("Casting pointer or non-first class to float");
2227    }
2228  } else if (DestTy->isVectorTy()) {
2229    assert(DestBits == SrcBits &&
2230           "Illegal cast to vector (wrong type or size)");
2231    return BitCast;
2232  } else if (DestTy->isPointerTy()) {
2233    if (SrcTy->isPointerTy()) {
2234      return BitCast;                               // ptr -> ptr
2235    } else if (SrcTy->isIntegerTy()) {
2236      return IntToPtr;                              // int -> ptr
2237    } else {
2238      assert(!"Casting pointer to other than pointer or int");
2239    }
2240  } else if (DestTy->isX86_MMXTy()) {
2241    if (SrcTy->isVectorTy()) {
2242      assert(DestBits == SrcBits && "Casting vector of wrong width to X86_MMX");
2243      return BitCast;                               // 64-bit vector to MMX
2244    } else {
2245      assert(!"Illegal cast to X86_MMX");
2246    }
2247  } else {
2248    assert(!"Casting to type that is not first-class");
2249  }
2250
2251  // If we fall through to here we probably hit an assertion cast above
2252  // and assertions are not turned on. Anything we return is an error, so
2253  // BitCast is as good a choice as any.
2254  return BitCast;
2255}
2256
2257//===----------------------------------------------------------------------===//
2258//                    CastInst SubClass Constructors
2259//===----------------------------------------------------------------------===//
2260
2261/// Check that the construction parameters for a CastInst are correct. This
2262/// could be broken out into the separate constructors but it is useful to have
2263/// it in one place and to eliminate the redundant code for getting the sizes
2264/// of the types involved.
2265bool
2266CastInst::castIsValid(Instruction::CastOps op, Value *S, Type *DstTy) {
2267
2268  // Check for type sanity on the arguments
2269  Type *SrcTy = S->getType();
2270  if (!SrcTy->isFirstClassType() || !DstTy->isFirstClassType() ||
2271      SrcTy->isAggregateType() || DstTy->isAggregateType())
2272    return false;
2273
2274  // Get the size of the types in bits, we'll need this later
2275  unsigned SrcBitSize = SrcTy->getScalarSizeInBits();
2276  unsigned DstBitSize = DstTy->getScalarSizeInBits();
2277
2278  // If these are vector types, get the lengths of the vectors (using zero for
2279  // scalar types means that checking that vector lengths match also checks that
2280  // scalars are not being converted to vectors or vectors to scalars).
2281  unsigned SrcLength = SrcTy->isVectorTy() ?
2282    cast<VectorType>(SrcTy)->getNumElements() : 0;
2283  unsigned DstLength = DstTy->isVectorTy() ?
2284    cast<VectorType>(DstTy)->getNumElements() : 0;
2285
2286  // Switch on the opcode provided
2287  switch (op) {
2288  default: return false; // This is an input error
2289  case Instruction::Trunc:
2290    return SrcTy->isIntOrIntVectorTy() && DstTy->isIntOrIntVectorTy() &&
2291      SrcLength == DstLength && SrcBitSize > DstBitSize;
2292  case Instruction::ZExt:
2293    return SrcTy->isIntOrIntVectorTy() && DstTy->isIntOrIntVectorTy() &&
2294      SrcLength == DstLength && SrcBitSize < DstBitSize;
2295  case Instruction::SExt:
2296    return SrcTy->isIntOrIntVectorTy() && DstTy->isIntOrIntVectorTy() &&
2297      SrcLength == DstLength && SrcBitSize < DstBitSize;
2298  case Instruction::FPTrunc:
2299    return SrcTy->isFPOrFPVectorTy() && DstTy->isFPOrFPVectorTy() &&
2300      SrcLength == DstLength && SrcBitSize > DstBitSize;
2301  case Instruction::FPExt:
2302    return SrcTy->isFPOrFPVectorTy() && DstTy->isFPOrFPVectorTy() &&
2303      SrcLength == DstLength && SrcBitSize < DstBitSize;
2304  case Instruction::UIToFP:
2305  case Instruction::SIToFP:
2306    return SrcTy->isIntOrIntVectorTy() && DstTy->isFPOrFPVectorTy() &&
2307      SrcLength == DstLength;
2308  case Instruction::FPToUI:
2309  case Instruction::FPToSI:
2310    return SrcTy->isFPOrFPVectorTy() && DstTy->isIntOrIntVectorTy() &&
2311      SrcLength == DstLength;
2312  case Instruction::PtrToInt:
2313    return SrcTy->isPointerTy() && DstTy->isIntegerTy();
2314  case Instruction::IntToPtr:
2315    return SrcTy->isIntegerTy() && DstTy->isPointerTy();
2316  case Instruction::BitCast:
2317    // BitCast implies a no-op cast of type only. No bits change.
2318    // However, you can't cast pointers to anything but pointers.
2319    if (SrcTy->isPointerTy() != DstTy->isPointerTy())
2320      return false;
2321
2322    // Now we know we're not dealing with a pointer/non-pointer mismatch. In all
2323    // these cases, the cast is okay if the source and destination bit widths
2324    // are identical.
2325    return SrcTy->getPrimitiveSizeInBits() == DstTy->getPrimitiveSizeInBits();
2326  }
2327}
2328
2329TruncInst::TruncInst(
2330  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2331) : CastInst(Ty, Trunc, S, Name, InsertBefore) {
2332  assert(castIsValid(getOpcode(), S, Ty) && "Illegal Trunc");
2333}
2334
2335TruncInst::TruncInst(
2336  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2337) : CastInst(Ty, Trunc, S, Name, InsertAtEnd) {
2338  assert(castIsValid(getOpcode(), S, Ty) && "Illegal Trunc");
2339}
2340
2341ZExtInst::ZExtInst(
2342  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2343)  : CastInst(Ty, ZExt, S, Name, InsertBefore) {
2344  assert(castIsValid(getOpcode(), S, Ty) && "Illegal ZExt");
2345}
2346
2347ZExtInst::ZExtInst(
2348  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2349)  : CastInst(Ty, ZExt, S, Name, InsertAtEnd) {
2350  assert(castIsValid(getOpcode(), S, Ty) && "Illegal ZExt");
2351}
2352SExtInst::SExtInst(
2353  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2354) : CastInst(Ty, SExt, S, Name, InsertBefore) {
2355  assert(castIsValid(getOpcode(), S, Ty) && "Illegal SExt");
2356}
2357
2358SExtInst::SExtInst(
2359  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2360)  : CastInst(Ty, SExt, S, Name, InsertAtEnd) {
2361  assert(castIsValid(getOpcode(), S, Ty) && "Illegal SExt");
2362}
2363
2364FPTruncInst::FPTruncInst(
2365  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2366) : CastInst(Ty, FPTrunc, S, Name, InsertBefore) {
2367  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPTrunc");
2368}
2369
2370FPTruncInst::FPTruncInst(
2371  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2372) : CastInst(Ty, FPTrunc, S, Name, InsertAtEnd) {
2373  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPTrunc");
2374}
2375
2376FPExtInst::FPExtInst(
2377  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2378) : CastInst(Ty, FPExt, S, Name, InsertBefore) {
2379  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPExt");
2380}
2381
2382FPExtInst::FPExtInst(
2383  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2384) : CastInst(Ty, FPExt, S, Name, InsertAtEnd) {
2385  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPExt");
2386}
2387
2388UIToFPInst::UIToFPInst(
2389  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2390) : CastInst(Ty, UIToFP, S, Name, InsertBefore) {
2391  assert(castIsValid(getOpcode(), S, Ty) && "Illegal UIToFP");
2392}
2393
2394UIToFPInst::UIToFPInst(
2395  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2396) : CastInst(Ty, UIToFP, S, Name, InsertAtEnd) {
2397  assert(castIsValid(getOpcode(), S, Ty) && "Illegal UIToFP");
2398}
2399
2400SIToFPInst::SIToFPInst(
2401  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2402) : CastInst(Ty, SIToFP, S, Name, InsertBefore) {
2403  assert(castIsValid(getOpcode(), S, Ty) && "Illegal SIToFP");
2404}
2405
2406SIToFPInst::SIToFPInst(
2407  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2408) : CastInst(Ty, SIToFP, S, Name, InsertAtEnd) {
2409  assert(castIsValid(getOpcode(), S, Ty) && "Illegal SIToFP");
2410}
2411
2412FPToUIInst::FPToUIInst(
2413  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2414) : CastInst(Ty, FPToUI, S, Name, InsertBefore) {
2415  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToUI");
2416}
2417
2418FPToUIInst::FPToUIInst(
2419  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2420) : CastInst(Ty, FPToUI, S, Name, InsertAtEnd) {
2421  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToUI");
2422}
2423
2424FPToSIInst::FPToSIInst(
2425  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2426) : CastInst(Ty, FPToSI, S, Name, InsertBefore) {
2427  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToSI");
2428}
2429
2430FPToSIInst::FPToSIInst(
2431  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2432) : CastInst(Ty, FPToSI, S, Name, InsertAtEnd) {
2433  assert(castIsValid(getOpcode(), S, Ty) && "Illegal FPToSI");
2434}
2435
2436PtrToIntInst::PtrToIntInst(
2437  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2438) : CastInst(Ty, PtrToInt, S, Name, InsertBefore) {
2439  assert(castIsValid(getOpcode(), S, Ty) && "Illegal PtrToInt");
2440}
2441
2442PtrToIntInst::PtrToIntInst(
2443  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2444) : CastInst(Ty, PtrToInt, S, Name, InsertAtEnd) {
2445  assert(castIsValid(getOpcode(), S, Ty) && "Illegal PtrToInt");
2446}
2447
2448IntToPtrInst::IntToPtrInst(
2449  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2450) : CastInst(Ty, IntToPtr, S, Name, InsertBefore) {
2451  assert(castIsValid(getOpcode(), S, Ty) && "Illegal IntToPtr");
2452}
2453
2454IntToPtrInst::IntToPtrInst(
2455  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2456) : CastInst(Ty, IntToPtr, S, Name, InsertAtEnd) {
2457  assert(castIsValid(getOpcode(), S, Ty) && "Illegal IntToPtr");
2458}
2459
2460BitCastInst::BitCastInst(
2461  Value *S, Type *Ty, const Twine &Name, Instruction *InsertBefore
2462) : CastInst(Ty, BitCast, S, Name, InsertBefore) {
2463  assert(castIsValid(getOpcode(), S, Ty) && "Illegal BitCast");
2464}
2465
2466BitCastInst::BitCastInst(
2467  Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd
2468) : CastInst(Ty, BitCast, S, Name, InsertAtEnd) {
2469  assert(castIsValid(getOpcode(), S, Ty) && "Illegal BitCast");
2470}
2471
2472//===----------------------------------------------------------------------===//
2473//                               CmpInst Classes
2474//===----------------------------------------------------------------------===//
2475
2476void CmpInst::Anchor() const {}
2477
2478CmpInst::CmpInst(Type *ty, OtherOps op, unsigned short predicate,
2479                 Value *LHS, Value *RHS, const Twine &Name,
2480                 Instruction *InsertBefore)
2481  : Instruction(ty, op,
2482                OperandTraits<CmpInst>::op_begin(this),
2483                OperandTraits<CmpInst>::operands(this),
2484                InsertBefore) {
2485    Op<0>() = LHS;
2486    Op<1>() = RHS;
2487  setPredicate((Predicate)predicate);
2488  setName(Name);
2489}
2490
2491CmpInst::CmpInst(Type *ty, OtherOps op, unsigned short predicate,
2492                 Value *LHS, Value *RHS, const Twine &Name,
2493                 BasicBlock *InsertAtEnd)
2494  : Instruction(ty, op,
2495                OperandTraits<CmpInst>::op_begin(this),
2496                OperandTraits<CmpInst>::operands(this),
2497                InsertAtEnd) {
2498  Op<0>() = LHS;
2499  Op<1>() = RHS;
2500  setPredicate((Predicate)predicate);
2501  setName(Name);
2502}
2503
2504CmpInst *
2505CmpInst::Create(OtherOps Op, unsigned short predicate,
2506                Value *S1, Value *S2,
2507                const Twine &Name, Instruction *InsertBefore) {
2508  if (Op == Instruction::ICmp) {
2509    if (InsertBefore)
2510      return new ICmpInst(InsertBefore, CmpInst::Predicate(predicate),
2511                          S1, S2, Name);
2512    else
2513      return new ICmpInst(CmpInst::Predicate(predicate),
2514                          S1, S2, Name);
2515  }
2516
2517  if (InsertBefore)
2518    return new FCmpInst(InsertBefore, CmpInst::Predicate(predicate),
2519                        S1, S2, Name);
2520  else
2521    return new FCmpInst(CmpInst::Predicate(predicate),
2522                        S1, S2, Name);
2523}
2524
2525CmpInst *
2526CmpInst::Create(OtherOps Op, unsigned short predicate, Value *S1, Value *S2,
2527                const Twine &Name, BasicBlock *InsertAtEnd) {
2528  if (Op == Instruction::ICmp) {
2529    return new ICmpInst(*InsertAtEnd, CmpInst::Predicate(predicate),
2530                        S1, S2, Name);
2531  }
2532  return new FCmpInst(*InsertAtEnd, CmpInst::Predicate(predicate),
2533                      S1, S2, Name);
2534}
2535
2536void CmpInst::swapOperands() {
2537  if (ICmpInst *IC = dyn_cast<ICmpInst>(this))
2538    IC->swapOperands();
2539  else
2540    cast<FCmpInst>(this)->swapOperands();
2541}
2542
2543bool CmpInst::isCommutative() const {
2544  if (const ICmpInst *IC = dyn_cast<ICmpInst>(this))
2545    return IC->isCommutative();
2546  return cast<FCmpInst>(this)->isCommutative();
2547}
2548
2549bool CmpInst::isEquality() const {
2550  if (const ICmpInst *IC = dyn_cast<ICmpInst>(this))
2551    return IC->isEquality();
2552  return cast<FCmpInst>(this)->isEquality();
2553}
2554
2555
2556CmpInst::Predicate CmpInst::getInversePredicate(Predicate pred) {
2557  switch (pred) {
2558    default: assert(!"Unknown cmp predicate!");
2559    case ICMP_EQ: return ICMP_NE;
2560    case ICMP_NE: return ICMP_EQ;
2561    case ICMP_UGT: return ICMP_ULE;
2562    case ICMP_ULT: return ICMP_UGE;
2563    case ICMP_UGE: return ICMP_ULT;
2564    case ICMP_ULE: return ICMP_UGT;
2565    case ICMP_SGT: return ICMP_SLE;
2566    case ICMP_SLT: return ICMP_SGE;
2567    case ICMP_SGE: return ICMP_SLT;
2568    case ICMP_SLE: return ICMP_SGT;
2569
2570    case FCMP_OEQ: return FCMP_UNE;
2571    case FCMP_ONE: return FCMP_UEQ;
2572    case FCMP_OGT: return FCMP_ULE;
2573    case FCMP_OLT: return FCMP_UGE;
2574    case FCMP_OGE: return FCMP_ULT;
2575    case FCMP_OLE: return FCMP_UGT;
2576    case FCMP_UEQ: return FCMP_ONE;
2577    case FCMP_UNE: return FCMP_OEQ;
2578    case FCMP_UGT: return FCMP_OLE;
2579    case FCMP_ULT: return FCMP_OGE;
2580    case FCMP_UGE: return FCMP_OLT;
2581    case FCMP_ULE: return FCMP_OGT;
2582    case FCMP_ORD: return FCMP_UNO;
2583    case FCMP_UNO: return FCMP_ORD;
2584    case FCMP_TRUE: return FCMP_FALSE;
2585    case FCMP_FALSE: return FCMP_TRUE;
2586  }
2587}
2588
2589ICmpInst::Predicate ICmpInst::getSignedPredicate(Predicate pred) {
2590  switch (pred) {
2591    default: assert(! "Unknown icmp predicate!");
2592    case ICMP_EQ: case ICMP_NE:
2593    case ICMP_SGT: case ICMP_SLT: case ICMP_SGE: case ICMP_SLE:
2594       return pred;
2595    case ICMP_UGT: return ICMP_SGT;
2596    case ICMP_ULT: return ICMP_SLT;
2597    case ICMP_UGE: return ICMP_SGE;
2598    case ICMP_ULE: return ICMP_SLE;
2599  }
2600}
2601
2602ICmpInst::Predicate ICmpInst::getUnsignedPredicate(Predicate pred) {
2603  switch (pred) {
2604    default: assert(! "Unknown icmp predicate!");
2605    case ICMP_EQ: case ICMP_NE:
2606    case ICMP_UGT: case ICMP_ULT: case ICMP_UGE: case ICMP_ULE:
2607       return pred;
2608    case ICMP_SGT: return ICMP_UGT;
2609    case ICMP_SLT: return ICMP_ULT;
2610    case ICMP_SGE: return ICMP_UGE;
2611    case ICMP_SLE: return ICMP_ULE;
2612  }
2613}
2614
2615/// Initialize a set of values that all satisfy the condition with C.
2616///
2617ConstantRange
2618ICmpInst::makeConstantRange(Predicate pred, const APInt &C) {
2619  APInt Lower(C);
2620  APInt Upper(C);
2621  uint32_t BitWidth = C.getBitWidth();
2622  switch (pred) {
2623  default: llvm_unreachable("Invalid ICmp opcode to ConstantRange ctor!");
2624  case ICmpInst::ICMP_EQ: Upper++; break;
2625  case ICmpInst::ICMP_NE: Lower++; break;
2626  case ICmpInst::ICMP_ULT:
2627    Lower = APInt::getMinValue(BitWidth);
2628    // Check for an empty-set condition.
2629    if (Lower == Upper)
2630      return ConstantRange(BitWidth, /*isFullSet=*/false);
2631    break;
2632  case ICmpInst::ICMP_SLT:
2633    Lower = APInt::getSignedMinValue(BitWidth);
2634    // Check for an empty-set condition.
2635    if (Lower == Upper)
2636      return ConstantRange(BitWidth, /*isFullSet=*/false);
2637    break;
2638  case ICmpInst::ICMP_UGT:
2639    Lower++; Upper = APInt::getMinValue(BitWidth);        // Min = Next(Max)
2640    // Check for an empty-set condition.
2641    if (Lower == Upper)
2642      return ConstantRange(BitWidth, /*isFullSet=*/false);
2643    break;
2644  case ICmpInst::ICMP_SGT:
2645    Lower++; Upper = APInt::getSignedMinValue(BitWidth);  // Min = Next(Max)
2646    // Check for an empty-set condition.
2647    if (Lower == Upper)
2648      return ConstantRange(BitWidth, /*isFullSet=*/false);
2649    break;
2650  case ICmpInst::ICMP_ULE:
2651    Lower = APInt::getMinValue(BitWidth); Upper++;
2652    // Check for a full-set condition.
2653    if (Lower == Upper)
2654      return ConstantRange(BitWidth, /*isFullSet=*/true);
2655    break;
2656  case ICmpInst::ICMP_SLE:
2657    Lower = APInt::getSignedMinValue(BitWidth); Upper++;
2658    // Check for a full-set condition.
2659    if (Lower == Upper)
2660      return ConstantRange(BitWidth, /*isFullSet=*/true);
2661    break;
2662  case ICmpInst::ICMP_UGE:
2663    Upper = APInt::getMinValue(BitWidth);        // Min = Next(Max)
2664    // Check for a full-set condition.
2665    if (Lower == Upper)
2666      return ConstantRange(BitWidth, /*isFullSet=*/true);
2667    break;
2668  case ICmpInst::ICMP_SGE:
2669    Upper = APInt::getSignedMinValue(BitWidth);  // Min = Next(Max)
2670    // Check for a full-set condition.
2671    if (Lower == Upper)
2672      return ConstantRange(BitWidth, /*isFullSet=*/true);
2673    break;
2674  }
2675  return ConstantRange(Lower, Upper);
2676}
2677
2678CmpInst::Predicate CmpInst::getSwappedPredicate(Predicate pred) {
2679  switch (pred) {
2680    default: assert(!"Unknown cmp predicate!");
2681    case ICMP_EQ: case ICMP_NE:
2682      return pred;
2683    case ICMP_SGT: return ICMP_SLT;
2684    case ICMP_SLT: return ICMP_SGT;
2685    case ICMP_SGE: return ICMP_SLE;
2686    case ICMP_SLE: return ICMP_SGE;
2687    case ICMP_UGT: return ICMP_ULT;
2688    case ICMP_ULT: return ICMP_UGT;
2689    case ICMP_UGE: return ICMP_ULE;
2690    case ICMP_ULE: return ICMP_UGE;
2691
2692    case FCMP_FALSE: case FCMP_TRUE:
2693    case FCMP_OEQ: case FCMP_ONE:
2694    case FCMP_UEQ: case FCMP_UNE:
2695    case FCMP_ORD: case FCMP_UNO:
2696      return pred;
2697    case FCMP_OGT: return FCMP_OLT;
2698    case FCMP_OLT: return FCMP_OGT;
2699    case FCMP_OGE: return FCMP_OLE;
2700    case FCMP_OLE: return FCMP_OGE;
2701    case FCMP_UGT: return FCMP_ULT;
2702    case FCMP_ULT: return FCMP_UGT;
2703    case FCMP_UGE: return FCMP_ULE;
2704    case FCMP_ULE: return FCMP_UGE;
2705  }
2706}
2707
2708bool CmpInst::isUnsigned(unsigned short predicate) {
2709  switch (predicate) {
2710    default: return false;
2711    case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_ULE: case ICmpInst::ICMP_UGT:
2712    case ICmpInst::ICMP_UGE: return true;
2713  }
2714}
2715
2716bool CmpInst::isSigned(unsigned short predicate) {
2717  switch (predicate) {
2718    default: return false;
2719    case ICmpInst::ICMP_SLT: case ICmpInst::ICMP_SLE: case ICmpInst::ICMP_SGT:
2720    case ICmpInst::ICMP_SGE: return true;
2721  }
2722}
2723
2724bool CmpInst::isOrdered(unsigned short predicate) {
2725  switch (predicate) {
2726    default: return false;
2727    case FCmpInst::FCMP_OEQ: case FCmpInst::FCMP_ONE: case FCmpInst::FCMP_OGT:
2728    case FCmpInst::FCMP_OLT: case FCmpInst::FCMP_OGE: case FCmpInst::FCMP_OLE:
2729    case FCmpInst::FCMP_ORD: return true;
2730  }
2731}
2732
2733bool CmpInst::isUnordered(unsigned short predicate) {
2734  switch (predicate) {
2735    default: return false;
2736    case FCmpInst::FCMP_UEQ: case FCmpInst::FCMP_UNE: case FCmpInst::FCMP_UGT:
2737    case FCmpInst::FCMP_ULT: case FCmpInst::FCMP_UGE: case FCmpInst::FCMP_ULE:
2738    case FCmpInst::FCMP_UNO: return true;
2739  }
2740}
2741
2742bool CmpInst::isTrueWhenEqual(unsigned short predicate) {
2743  switch(predicate) {
2744    default: return false;
2745    case ICMP_EQ:   case ICMP_UGE: case ICMP_ULE: case ICMP_SGE: case ICMP_SLE:
2746    case FCMP_TRUE: case FCMP_UEQ: case FCMP_UGE: case FCMP_ULE: return true;
2747  }
2748}
2749
2750bool CmpInst::isFalseWhenEqual(unsigned short predicate) {
2751  switch(predicate) {
2752  case ICMP_NE:    case ICMP_UGT: case ICMP_ULT: case ICMP_SGT: case ICMP_SLT:
2753  case FCMP_FALSE: case FCMP_ONE: case FCMP_OGT: case FCMP_OLT: return true;
2754  default: return false;
2755  }
2756}
2757
2758
2759//===----------------------------------------------------------------------===//
2760//                        SwitchInst Implementation
2761//===----------------------------------------------------------------------===//
2762
2763void SwitchInst::init(Value *Value, BasicBlock *Default, unsigned NumReserved) {
2764  assert(Value && Default && NumReserved);
2765  ReservedSpace = NumReserved;
2766  NumOperands = 2;
2767  OperandList = allocHungoffUses(ReservedSpace);
2768
2769  OperandList[0] = Value;
2770  OperandList[1] = Default;
2771}
2772
2773/// SwitchInst ctor - Create a new switch instruction, specifying a value to
2774/// switch on and a default destination.  The number of additional cases can
2775/// be specified here to make memory allocation more efficient.  This
2776/// constructor can also autoinsert before another instruction.
2777SwitchInst::SwitchInst(Value *Value, BasicBlock *Default, unsigned NumCases,
2778                       Instruction *InsertBefore)
2779  : TerminatorInst(Type::getVoidTy(Value->getContext()), Instruction::Switch,
2780                   0, 0, InsertBefore) {
2781  init(Value, Default, 2+NumCases*2);
2782}
2783
2784/// SwitchInst ctor - Create a new switch instruction, specifying a value to
2785/// switch on and a default destination.  The number of additional cases can
2786/// be specified here to make memory allocation more efficient.  This
2787/// constructor also autoinserts at the end of the specified BasicBlock.
2788SwitchInst::SwitchInst(Value *Value, BasicBlock *Default, unsigned NumCases,
2789                       BasicBlock *InsertAtEnd)
2790  : TerminatorInst(Type::getVoidTy(Value->getContext()), Instruction::Switch,
2791                   0, 0, InsertAtEnd) {
2792  init(Value, Default, 2+NumCases*2);
2793}
2794
2795SwitchInst::SwitchInst(const SwitchInst &SI)
2796  : TerminatorInst(SI.getType(), Instruction::Switch, 0, 0) {
2797  init(SI.getCondition(), SI.getDefaultDest(), SI.getNumOperands());
2798  NumOperands = SI.getNumOperands();
2799  Use *OL = OperandList, *InOL = SI.OperandList;
2800  for (unsigned i = 2, E = SI.getNumOperands(); i != E; i += 2) {
2801    OL[i] = InOL[i];
2802    OL[i+1] = InOL[i+1];
2803  }
2804  SubclassOptionalData = SI.SubclassOptionalData;
2805}
2806
2807SwitchInst::~SwitchInst() {
2808  dropHungoffUses();
2809}
2810
2811
2812/// addCase - Add an entry to the switch instruction...
2813///
2814void SwitchInst::addCase(ConstantInt *OnVal, BasicBlock *Dest) {
2815  unsigned OpNo = NumOperands;
2816  if (OpNo+2 > ReservedSpace)
2817    growOperands();  // Get more space!
2818  // Initialize some new operands.
2819  assert(OpNo+1 < ReservedSpace && "Growing didn't work!");
2820  NumOperands = OpNo+2;
2821  OperandList[OpNo] = OnVal;
2822  OperandList[OpNo+1] = Dest;
2823}
2824
2825/// removeCase - This method removes the specified successor from the switch
2826/// instruction.  Note that this cannot be used to remove the default
2827/// destination (successor #0).
2828///
2829void SwitchInst::removeCase(unsigned idx) {
2830  assert(idx != 0 && "Cannot remove the default case!");
2831  assert(idx*2 < getNumOperands() && "Successor index out of range!!!");
2832
2833  unsigned NumOps = getNumOperands();
2834  Use *OL = OperandList;
2835
2836  // Overwrite this case with the end of the list.
2837  if ((idx + 1) * 2 != NumOps) {
2838    OL[idx * 2] = OL[NumOps - 2];
2839    OL[idx * 2 + 1] = OL[NumOps - 1];
2840  }
2841
2842  // Nuke the last value.
2843  OL[NumOps-2].set(0);
2844  OL[NumOps-2+1].set(0);
2845  NumOperands = NumOps-2;
2846}
2847
2848/// growOperands - grow operands - This grows the operand list in response
2849/// to a push_back style of operation.  This grows the number of ops by 3 times.
2850///
2851void SwitchInst::growOperands() {
2852  unsigned e = getNumOperands();
2853  unsigned NumOps = e*3;
2854
2855  ReservedSpace = NumOps;
2856  Use *NewOps = allocHungoffUses(NumOps);
2857  Use *OldOps = OperandList;
2858  for (unsigned i = 0; i != e; ++i) {
2859      NewOps[i] = OldOps[i];
2860  }
2861  OperandList = NewOps;
2862  Use::zap(OldOps, OldOps + e, true);
2863}
2864
2865
2866BasicBlock *SwitchInst::getSuccessorV(unsigned idx) const {
2867  return getSuccessor(idx);
2868}
2869unsigned SwitchInst::getNumSuccessorsV() const {
2870  return getNumSuccessors();
2871}
2872void SwitchInst::setSuccessorV(unsigned idx, BasicBlock *B) {
2873  setSuccessor(idx, B);
2874}
2875
2876//===----------------------------------------------------------------------===//
2877//                        IndirectBrInst Implementation
2878//===----------------------------------------------------------------------===//
2879
2880void IndirectBrInst::init(Value *Address, unsigned NumDests) {
2881  assert(Address && Address->getType()->isPointerTy() &&
2882         "Address of indirectbr must be a pointer");
2883  ReservedSpace = 1+NumDests;
2884  NumOperands = 1;
2885  OperandList = allocHungoffUses(ReservedSpace);
2886
2887  OperandList[0] = Address;
2888}
2889
2890
2891/// growOperands - grow operands - This grows the operand list in response
2892/// to a push_back style of operation.  This grows the number of ops by 2 times.
2893///
2894void IndirectBrInst::growOperands() {
2895  unsigned e = getNumOperands();
2896  unsigned NumOps = e*2;
2897
2898  ReservedSpace = NumOps;
2899  Use *NewOps = allocHungoffUses(NumOps);
2900  Use *OldOps = OperandList;
2901  for (unsigned i = 0; i != e; ++i)
2902    NewOps[i] = OldOps[i];
2903  OperandList = NewOps;
2904  Use::zap(OldOps, OldOps + e, true);
2905}
2906
2907IndirectBrInst::IndirectBrInst(Value *Address, unsigned NumCases,
2908                               Instruction *InsertBefore)
2909: TerminatorInst(Type::getVoidTy(Address->getContext()),Instruction::IndirectBr,
2910                 0, 0, InsertBefore) {
2911  init(Address, NumCases);
2912}
2913
2914IndirectBrInst::IndirectBrInst(Value *Address, unsigned NumCases,
2915                               BasicBlock *InsertAtEnd)
2916: TerminatorInst(Type::getVoidTy(Address->getContext()),Instruction::IndirectBr,
2917                 0, 0, InsertAtEnd) {
2918  init(Address, NumCases);
2919}
2920
2921IndirectBrInst::IndirectBrInst(const IndirectBrInst &IBI)
2922  : TerminatorInst(Type::getVoidTy(IBI.getContext()), Instruction::IndirectBr,
2923                   allocHungoffUses(IBI.getNumOperands()),
2924                   IBI.getNumOperands()) {
2925  Use *OL = OperandList, *InOL = IBI.OperandList;
2926  for (unsigned i = 0, E = IBI.getNumOperands(); i != E; ++i)
2927    OL[i] = InOL[i];
2928  SubclassOptionalData = IBI.SubclassOptionalData;
2929}
2930
2931IndirectBrInst::~IndirectBrInst() {
2932  dropHungoffUses();
2933}
2934
2935/// addDestination - Add a destination.
2936///
2937void IndirectBrInst::addDestination(BasicBlock *DestBB) {
2938  unsigned OpNo = NumOperands;
2939  if (OpNo+1 > ReservedSpace)
2940    growOperands();  // Get more space!
2941  // Initialize some new operands.
2942  assert(OpNo < ReservedSpace && "Growing didn't work!");
2943  NumOperands = OpNo+1;
2944  OperandList[OpNo] = DestBB;
2945}
2946
2947/// removeDestination - This method removes the specified successor from the
2948/// indirectbr instruction.
2949void IndirectBrInst::removeDestination(unsigned idx) {
2950  assert(idx < getNumOperands()-1 && "Successor index out of range!");
2951
2952  unsigned NumOps = getNumOperands();
2953  Use *OL = OperandList;
2954
2955  // Replace this value with the last one.
2956  OL[idx+1] = OL[NumOps-1];
2957
2958  // Nuke the last value.
2959  OL[NumOps-1].set(0);
2960  NumOperands = NumOps-1;
2961}
2962
2963BasicBlock *IndirectBrInst::getSuccessorV(unsigned idx) const {
2964  return getSuccessor(idx);
2965}
2966unsigned IndirectBrInst::getNumSuccessorsV() const {
2967  return getNumSuccessors();
2968}
2969void IndirectBrInst::setSuccessorV(unsigned idx, BasicBlock *B) {
2970  setSuccessor(idx, B);
2971}
2972
2973//===----------------------------------------------------------------------===//
2974//                           clone_impl() implementations
2975//===----------------------------------------------------------------------===//
2976
2977// Define these methods here so vtables don't get emitted into every translation
2978// unit that uses these classes.
2979
2980GetElementPtrInst *GetElementPtrInst::clone_impl() const {
2981  return new (getNumOperands()) GetElementPtrInst(*this);
2982}
2983
2984BinaryOperator *BinaryOperator::clone_impl() const {
2985  return Create(getOpcode(), Op<0>(), Op<1>());
2986}
2987
2988FCmpInst* FCmpInst::clone_impl() const {
2989  return new FCmpInst(getPredicate(), Op<0>(), Op<1>());
2990}
2991
2992ICmpInst* ICmpInst::clone_impl() const {
2993  return new ICmpInst(getPredicate(), Op<0>(), Op<1>());
2994}
2995
2996ExtractValueInst *ExtractValueInst::clone_impl() const {
2997  return new ExtractValueInst(*this);
2998}
2999
3000InsertValueInst *InsertValueInst::clone_impl() const {
3001  return new InsertValueInst(*this);
3002}
3003
3004AllocaInst *AllocaInst::clone_impl() const {
3005  return new AllocaInst(getAllocatedType(),
3006                        (Value*)getOperand(0),
3007                        getAlignment());
3008}
3009
3010LoadInst *LoadInst::clone_impl() const {
3011  return new LoadInst(getOperand(0),
3012                      Twine(), isVolatile(),
3013                      getAlignment());
3014}
3015
3016StoreInst *StoreInst::clone_impl() const {
3017  return new StoreInst(getOperand(0), getOperand(1),
3018                       isVolatile(), getAlignment());
3019}
3020
3021TruncInst *TruncInst::clone_impl() const {
3022  return new TruncInst(getOperand(0), getType());
3023}
3024
3025ZExtInst *ZExtInst::clone_impl() const {
3026  return new ZExtInst(getOperand(0), getType());
3027}
3028
3029SExtInst *SExtInst::clone_impl() const {
3030  return new SExtInst(getOperand(0), getType());
3031}
3032
3033FPTruncInst *FPTruncInst::clone_impl() const {
3034  return new FPTruncInst(getOperand(0), getType());
3035}
3036
3037FPExtInst *FPExtInst::clone_impl() const {
3038  return new FPExtInst(getOperand(0), getType());
3039}
3040
3041UIToFPInst *UIToFPInst::clone_impl() const {
3042  return new UIToFPInst(getOperand(0), getType());
3043}
3044
3045SIToFPInst *SIToFPInst::clone_impl() const {
3046  return new SIToFPInst(getOperand(0), getType());
3047}
3048
3049FPToUIInst *FPToUIInst::clone_impl() const {
3050  return new FPToUIInst(getOperand(0), getType());
3051}
3052
3053FPToSIInst *FPToSIInst::clone_impl() const {
3054  return new FPToSIInst(getOperand(0), getType());
3055}
3056
3057PtrToIntInst *PtrToIntInst::clone_impl() const {
3058  return new PtrToIntInst(getOperand(0), getType());
3059}
3060
3061IntToPtrInst *IntToPtrInst::clone_impl() const {
3062  return new IntToPtrInst(getOperand(0), getType());
3063}
3064
3065BitCastInst *BitCastInst::clone_impl() const {
3066  return new BitCastInst(getOperand(0), getType());
3067}
3068
3069CallInst *CallInst::clone_impl() const {
3070  return  new(getNumOperands()) CallInst(*this);
3071}
3072
3073SelectInst *SelectInst::clone_impl() const {
3074  return SelectInst::Create(getOperand(0), getOperand(1), getOperand(2));
3075}
3076
3077VAArgInst *VAArgInst::clone_impl() const {
3078  return new VAArgInst(getOperand(0), getType());
3079}
3080
3081ExtractElementInst *ExtractElementInst::clone_impl() const {
3082  return ExtractElementInst::Create(getOperand(0), getOperand(1));
3083}
3084
3085InsertElementInst *InsertElementInst::clone_impl() const {
3086  return InsertElementInst::Create(getOperand(0),
3087                                   getOperand(1),
3088                                   getOperand(2));
3089}
3090
3091ShuffleVectorInst *ShuffleVectorInst::clone_impl() const {
3092  return new ShuffleVectorInst(getOperand(0),
3093                           getOperand(1),
3094                           getOperand(2));
3095}
3096
3097PHINode *PHINode::clone_impl() const {
3098  return new PHINode(*this);
3099}
3100
3101ReturnInst *ReturnInst::clone_impl() const {
3102  return new(getNumOperands()) ReturnInst(*this);
3103}
3104
3105BranchInst *BranchInst::clone_impl() const {
3106  return new(getNumOperands()) BranchInst(*this);
3107}
3108
3109SwitchInst *SwitchInst::clone_impl() const {
3110  return new SwitchInst(*this);
3111}
3112
3113IndirectBrInst *IndirectBrInst::clone_impl() const {
3114  return new IndirectBrInst(*this);
3115}
3116
3117
3118InvokeInst *InvokeInst::clone_impl() const {
3119  return new(getNumOperands()) InvokeInst(*this);
3120}
3121
3122UnwindInst *UnwindInst::clone_impl() const {
3123  LLVMContext &Context = getContext();
3124  return new UnwindInst(Context);
3125}
3126
3127UnreachableInst *UnreachableInst::clone_impl() const {
3128  LLVMContext &Context = getContext();
3129  return new UnreachableInst(Context);
3130}
3131