lib/VMCore/Instructions.cpp

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