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