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