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