lib/VMCore/Instructions.cpp

   1 //===-- Instructions.cpp - Implement the LLVM instructions ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements all of the non-inline methods for the LLVM instruction
  11 // classes.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/BasicBlock.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Support/CallSite.h"
  21 using namespace llvm;
  22
  23 //===----------------------------------------------------------------------===//
  24 //                            TerminatorInst Class
  25 //===----------------------------------------------------------------------===//
  26
  27 TerminatorInst::TerminatorInst(Instruction::TermOps iType,
  28                                Use *Ops, unsigned NumOps, Instruction *IB)
  29   : Instruction(Type::VoidTy, iType, Ops, NumOps, "", IB) {
  30 }
  31
  32 TerminatorInst::TerminatorInst(Instruction::TermOps iType,
  33                                Use *Ops, unsigned NumOps, BasicBlock *IAE)
  34   : Instruction(Type::VoidTy, iType, Ops, NumOps, "", IAE) {
  35 }
  36
  37
  38
  39 //===----------------------------------------------------------------------===//
  40 //                               PHINode Class
  41 //===----------------------------------------------------------------------===//
  42
  43 PHINode::PHINode(const PHINode &PN)
  44   : Instruction(PN.getType(), Instruction::PHI,
  45                 new Use[PN.getNumOperands()], PN.getNumOperands()),
  46     ReservedSpace(PN.getNumOperands()) {
  47   Use *OL = OperandList;
  48   for (unsigned i = 0, e = PN.getNumOperands(); i != e; i+=2) {
  49     OL[i].init(PN.getOperand(i), this);
  50     OL[i+1].init(PN.getOperand(i+1), this);
  51   }
  52 }
  53
  54 PHINode::~PHINode() {
  55   delete [] OperandList;
  56 }
  57
  58 // removeIncomingValue - Remove an incoming value.  This is useful if a
  59 // predecessor basic block is deleted.
  60 Value *PHINode::removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty) {
  61   unsigned NumOps = getNumOperands();
  62   Use *OL = OperandList;
  63   assert(Idx*2 < NumOps && "BB not in PHI node!");
  64   Value *Removed = OL[Idx*2];
  65
  66   // Move everything after this operand down.
  67   //
  68   // FIXME: we could just swap with the end of the list, then erase.  However,
  69   // client might not expect this to happen.  The code as it is thrashes the
  70   // use/def lists, which is kinda lame.
  71   for (unsigned i = (Idx+1)*2; i != NumOps; i += 2) {
  72     OL[i-2] = OL[i];
  73     OL[i-2+1] = OL[i+1];
  74   }
  75
  76   // Nuke the last value.
  77   OL[NumOps-2].set(0);
  78   OL[NumOps-2+1].set(0);
  79   NumOperands = NumOps-2;
  80
  81   // If the PHI node is dead, because it has zero entries, nuke it now.
  82   if (NumOps == 2 && DeletePHIIfEmpty) {
  83     // If anyone is using this PHI, make them use a dummy value instead...
  84     replaceAllUsesWith(UndefValue::get(getType()));
  85     eraseFromParent();
  86   }
  87   return Removed;
  88 }
  89
  90 /// resizeOperands - resize operands - This adjusts the length of the operands
  91 /// list according to the following behavior:
  92 ///   1. If NumOps == 0, grow the operand list in response to a push_back style
  93 ///      of operation.  This grows the number of ops by 1.5 times.
  94 ///   2. If NumOps > NumOperands, reserve space for NumOps operands.
  95 ///   3. If NumOps == NumOperands, trim the reserved space.
  96 ///
  97 void PHINode::resizeOperands(unsigned NumOps) {
  98   if (NumOps == 0) {
  99     NumOps = (getNumOperands())*3/2;
 100     if (NumOps < 4) NumOps = 4;      // 4 op PHI nodes are VERY common.
 101   } else if (NumOps*2 > NumOperands) {
 102     // No resize needed.
 103     if (ReservedSpace >= NumOps) return;
 104   } else if (NumOps == NumOperands) {
 105     if (ReservedSpace == NumOps) return;
 106   } else {
 107     return;
 108   }
 109
 110   ReservedSpace = NumOps;
 111   Use *NewOps = new Use[NumOps];
 112   Use *OldOps = OperandList;
 113   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
 114       NewOps[i].init(OldOps[i], this);
 115       OldOps[i].set(0);
 116   }
 117   delete [] OldOps;
 118   OperandList = NewOps;
 119 }
 120
 121
 122 //===----------------------------------------------------------------------===//
 123 //                        CallInst Implementation
 124 //===----------------------------------------------------------------------===//
 125
 126 CallInst::~CallInst() {
 127   delete [] OperandList;
 128 }
 129
 130 void CallInst::init(Value *Func, const std::vector<Value*> &Params) {
 131   NumOperands = Params.size()+1;
 132   Use *OL = OperandList = new Use[Params.size()+1];
 133   OL[0].init(Func, this);
 134
 135   const FunctionType *FTy =
 136     cast<FunctionType>(cast<PointerType>(Func->getType())->getElementType());
 137
 138   assert((Params.size() == FTy->getNumParams() ||
 139           (FTy->isVarArg() && Params.size() > FTy->getNumParams())) &&
 140          "Calling a function with bad signature");
 141   for (unsigned i = 0, e = Params.size(); i != e; ++i)
 142     OL[i+1].init(Params[i], this);
 143 }
 144
 145 void CallInst::init(Value *Func, Value *Actual1, Value *Actual2) {
 146   NumOperands = 3;
 147   Use *OL = OperandList = new Use[3];
 148   OL[0].init(Func, this);
 149   OL[1].init(Actual1, this);
 150   OL[2].init(Actual2, this);
 151
 152   const FunctionType *FTy =
 153     cast<FunctionType>(cast<PointerType>(Func->getType())->getElementType());
 154
 155   assert((FTy->getNumParams() == 2 ||
 156           (FTy->isVarArg() && FTy->getNumParams() == 0)) &&
 157          "Calling a function with bad signature");
 158 }
 159
 160 void CallInst::init(Value *Func, Value *Actual) {
 161   NumOperands = 2;
 162   Use *OL = OperandList = new Use[2];
 163   OL[0].init(Func, this);
 164   OL[1].init(Actual, this);
 165
 166   const FunctionType *FTy =
 167     cast<FunctionType>(cast<PointerType>(Func->getType())->getElementType());
 168
 169   assert((FTy->getNumParams() == 1 ||
 170           (FTy->isVarArg() && FTy->getNumParams() == 0)) &&
 171          "Calling a function with bad signature");
 172 }
 173
 174 void CallInst::init(Value *Func) {
 175   NumOperands = 1;
 176   Use *OL = OperandList = new Use[1];
 177   OL[0].init(Func, this);
 178
 179   const FunctionType *MTy =
 180     cast<FunctionType>(cast<PointerType>(Func->getType())->getElementType());
 181
 182   assert(MTy->getNumParams() == 0 && "Calling a function with bad signature");
 183 }
 184
 185 CallInst::CallInst(Value *Func, const std::vector<Value*> &Params,
 186                    const std::string &Name, Instruction *InsertBefore)
 187   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 188                                  ->getElementType())->getReturnType(),
 189                 Instruction::Call, 0, 0, Name, InsertBefore) {
 190   init(Func, Params);
 191 }
 192
 193 CallInst::CallInst(Value *Func, const std::vector<Value*> &Params,
 194                    const std::string &Name, BasicBlock *InsertAtEnd)
 195   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 196                                  ->getElementType())->getReturnType(),
 197                 Instruction::Call, 0, 0, Name, InsertAtEnd) {
 198   init(Func, Params);
 199 }
 200
 201 CallInst::CallInst(Value *Func, Value *Actual1, Value *Actual2,
 202                    const std::string &Name, Instruction  *InsertBefore)
 203   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 204                                    ->getElementType())->getReturnType(),
 205                 Instruction::Call, 0, 0, Name, InsertBefore) {
 206   init(Func, Actual1, Actual2);
 207 }
 208
 209 CallInst::CallInst(Value *Func, Value *Actual1, Value *Actual2,
 210                    const std::string &Name, BasicBlock  *InsertAtEnd)
 211   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 212                                    ->getElementType())->getReturnType(),
 213                 Instruction::Call, 0, 0, Name, InsertAtEnd) {
 214   init(Func, Actual1, Actual2);
 215 }
 216
 217 CallInst::CallInst(Value *Func, Value* Actual, const std::string &Name,
 218                    Instruction  *InsertBefore)
 219   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 220                                    ->getElementType())->getReturnType(),
 221                 Instruction::Call, 0, 0, Name, InsertBefore) {
 222   init(Func, Actual);
 223 }
 224
 225 CallInst::CallInst(Value *Func, Value* Actual, const std::string &Name,
 226                    BasicBlock  *InsertAtEnd)
 227   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 228                                    ->getElementType())->getReturnType(),
 229                 Instruction::Call, 0, 0, Name, InsertAtEnd) {
 230   init(Func, Actual);
 231 }
 232
 233 CallInst::CallInst(Value *Func, const std::string &Name,
 234                    Instruction *InsertBefore)
 235   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 236                                    ->getElementType())->getReturnType(),
 237                 Instruction::Call, 0, 0, Name, InsertBefore) {
 238   init(Func);
 239 }
 240
 241 CallInst::CallInst(Value *Func, const std::string &Name,
 242                    BasicBlock *InsertAtEnd)
 243   : Instruction(cast<FunctionType>(cast<PointerType>(Func->getType())
 244                                    ->getElementType())->getReturnType(),
 245                 Instruction::Call, 0, 0, Name, InsertAtEnd) {
 246   init(Func);
 247 }
 248
 249 CallInst::CallInst(const CallInst &CI)
 250   : Instruction(CI.getType(), Instruction::Call, new Use[CI.getNumOperands()],
 251                 CI.getNumOperands()) {
 252   setTailCall(CI.isTailCall());
 253   Use *OL = OperandList;
 254   Use *InOL = CI.OperandList;
 255   for (unsigned i = 0, e = CI.getNumOperands(); i != e; ++i)
 256     OL[i].init(InOL[i], this);
 257 }
 258
 259
 260 //===----------------------------------------------------------------------===//
 261 //                        InvokeInst Implementation
 262 //===----------------------------------------------------------------------===//
 263
 264 InvokeInst::~InvokeInst() {
 265   delete [] OperandList;
 266 }
 267
 268 void InvokeInst::init(Value *Fn, BasicBlock *IfNormal, BasicBlock *IfException,
 269                       const std::vector<Value*> &Params) {
 270   NumOperands = 3+Params.size();
 271   Use *OL = OperandList = new Use[3+Params.size()];
 272   OL[0].init(Fn, this);
 273   OL[1].init(IfNormal, this);
 274   OL[2].init(IfException, this);
 275   const FunctionType *FTy =
 276     cast<FunctionType>(cast<PointerType>(Fn->getType())->getElementType());
 277
 278   assert((Params.size() == FTy->getNumParams()) ||
 279          (FTy->isVarArg() && Params.size() > FTy->getNumParams()) &&
 280          "Calling a function with bad signature");
 281
 282   for (unsigned i = 0, e = Params.size(); i != e; i++)
 283     OL[i+3].init(Params[i], this);
 284 }
 285
 286 InvokeInst::InvokeInst(Value *Fn, BasicBlock *IfNormal,
 287                        BasicBlock *IfException,
 288                        const std::vector<Value*> &Params,
 289                        const std::string &Name, Instruction *InsertBefore)
 290   : TerminatorInst(cast<FunctionType>(cast<PointerType>(Fn->getType())
 291                                     ->getElementType())->getReturnType(),
 292                    Instruction::Invoke, 0, 0, Name, InsertBefore) {
 293   init(Fn, IfNormal, IfException, Params);
 294 }
 295
 296 InvokeInst::InvokeInst(Value *Fn, BasicBlock *IfNormal,
 297                        BasicBlock *IfException,
 298                        const std::vector<Value*> &Params,
 299                        const std::string &Name, BasicBlock *InsertAtEnd)
 300   : TerminatorInst(cast<FunctionType>(cast<PointerType>(Fn->getType())
 301                                     ->getElementType())->getReturnType(),
 302                    Instruction::Invoke, 0, 0, Name, InsertAtEnd) {
 303   init(Fn, IfNormal, IfException, Params);
 304 }
 305
 306 InvokeInst::InvokeInst(const InvokeInst &II)
 307   : TerminatorInst(II.getType(), Instruction::Invoke,
 308                    new Use[II.getNumOperands()], II.getNumOperands()) {
 309   Use *OL = OperandList, *InOL = II.OperandList;
 310   for (unsigned i = 0, e = II.getNumOperands(); i != e; ++i)
 311     OL[i].init(InOL[i], this);
 312 }
 313
 314 BasicBlock *InvokeInst::getSuccessorV(unsigned idx) const {
 315   return getSuccessor(idx);
 316 }
 317 unsigned InvokeInst::getNumSuccessorsV() const {
 318   return getNumSuccessors();
 319 }
 320 void InvokeInst::setSuccessorV(unsigned idx, BasicBlock *B) {
 321   return setSuccessor(idx, B);
 322 }
 323
 324
 325 //===----------------------------------------------------------------------===//
 326 //                        ReturnInst Implementation
 327 //===----------------------------------------------------------------------===//
 328
 329 void ReturnInst::init(Value *retVal) {
 330   if (retVal && retVal->getType() != Type::VoidTy) {
 331     assert(!isa<BasicBlock>(retVal) &&
 332            "Cannot return basic block.  Probably using the incorrect ctor");
 333     NumOperands = 1;
 334     RetVal.init(retVal, this);
 335   }
 336 }
 337
 338 unsigned ReturnInst::getNumSuccessorsV() const {
 339   return getNumSuccessors();
 340 }
 341
 342 // Out-of-line ReturnInst method, put here so the C++ compiler can choose to
 343 // emit the vtable for the class in this translation unit.
 344 void ReturnInst::setSuccessorV(unsigned idx, BasicBlock *NewSucc) {
 345   assert(0 && "ReturnInst has no successors!");
 346 }
 347
 348 BasicBlock *ReturnInst::getSuccessorV(unsigned idx) const {
 349   assert(0 && "ReturnInst has no successors!");
 350   abort();
 351   return 0;
 352 }
 353
 354
 355 //===----------------------------------------------------------------------===//
 356 //                        UnwindInst Implementation
 357 //===----------------------------------------------------------------------===//
 358
 359 unsigned UnwindInst::getNumSuccessorsV() const {
 360   return getNumSuccessors();
 361 }
 362
 363 void UnwindInst::setSuccessorV(unsigned idx, BasicBlock *NewSucc) {
 364   assert(0 && "UnwindInst has no successors!");
 365 }
 366
 367 BasicBlock *UnwindInst::getSuccessorV(unsigned idx) const {
 368   assert(0 && "UnwindInst has no successors!");
 369   abort();
 370   return 0;
 371 }
 372
 373 //===----------------------------------------------------------------------===//
 374 //                      UnreachableInst Implementation
 375 //===----------------------------------------------------------------------===//
 376
 377 unsigned UnreachableInst::getNumSuccessorsV() const {
 378   return getNumSuccessors();
 379 }
 380
 381 void UnreachableInst::setSuccessorV(unsigned idx, BasicBlock *NewSucc) {
 382   assert(0 && "UnwindInst has no successors!");
 383 }
 384
 385 BasicBlock *UnreachableInst::getSuccessorV(unsigned idx) const {
 386   assert(0 && "UnwindInst has no successors!");
 387   abort();
 388   return 0;
 389 }
 390
 391 //===----------------------------------------------------------------------===//
 392 //                        BranchInst Implementation
 393 //===----------------------------------------------------------------------===//
 394
 395 void BranchInst::AssertOK() {
 396   if (isConditional())
 397     assert(getCondition()->getType() == Type::BoolTy &&
 398            "May only branch on boolean predicates!");
 399 }
 400
 401 BranchInst::BranchInst(const BranchInst &BI) :
 402   TerminatorInst(Instruction::Br, Ops, BI.getNumOperands()) {
 403   OperandList[0].init(BI.getOperand(0), this);
 404   if (BI.getNumOperands() != 1) {
 405     assert(BI.getNumOperands() == 3 && "BR can have 1 or 3 operands!");
 406     OperandList[1].init(BI.getOperand(1), this);
 407     OperandList[2].init(BI.getOperand(2), this);
 408   }
 409 }
 410
 411 BasicBlock *BranchInst::getSuccessorV(unsigned idx) const {
 412   return getSuccessor(idx);
 413 }
 414 unsigned BranchInst::getNumSuccessorsV() const {
 415   return getNumSuccessors();
 416 }
 417 void BranchInst::setSuccessorV(unsigned idx, BasicBlock *B) {
 418   setSuccessor(idx, B);
 419 }
 420
 421
 422 //===----------------------------------------------------------------------===//
 423 //                        AllocationInst Implementation
 424 //===----------------------------------------------------------------------===//
 425
 426 static Value *getAISize(Value *Amt) {
 427   if (!Amt)
 428     Amt = ConstantUInt::get(Type::UIntTy, 1);
 429   else
 430     assert(Amt->getType() == Type::UIntTy &&
 431            "Malloc/Allocation array size != UIntTy!");
 432   return Amt;
 433 }
 434
 435 AllocationInst::AllocationInst(const Type *Ty, Value *ArraySize, unsigned iTy,
 436                                const std::string &Name,
 437                                Instruction *InsertBefore)
 438   : UnaryInstruction(PointerType::get(Ty), iTy, getAISize(ArraySize),
 439                      Name, InsertBefore) {
 440   assert(Ty != Type::VoidTy && "Cannot allocate void!");
 441 }
 442
 443 AllocationInst::AllocationInst(const Type *Ty, Value *ArraySize, unsigned iTy,
 444                                const std::string &Name,
 445                                BasicBlock *InsertAtEnd)
 446   : UnaryInstruction(PointerType::get(Ty), iTy, getAISize(ArraySize),
 447                      Name, InsertAtEnd) {
 448   assert(Ty != Type::VoidTy && "Cannot allocate void!");
 449 }
 450
 451 bool AllocationInst::isArrayAllocation() const {
 452   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(getOperand(0)))
 453     return CUI->getValue() != 1;
 454   return true;
 455 }
 456
 457 const Type *AllocationInst::getAllocatedType() const {
 458   return getType()->getElementType();
 459 }
 460
 461 AllocaInst::AllocaInst(const AllocaInst &AI)
 462   : AllocationInst(AI.getType()->getElementType(), (Value*)AI.getOperand(0),
 463                    Instruction::Alloca) {
 464 }
 465
 466 MallocInst::MallocInst(const MallocInst &MI)
 467   : AllocationInst(MI.getType()->getElementType(), (Value*)MI.getOperand(0),
 468                    Instruction::Malloc) {
 469 }
 470
 471 //===----------------------------------------------------------------------===//
 472 //                             FreeInst Implementation
 473 //===----------------------------------------------------------------------===//
 474
 475 void FreeInst::AssertOK() {
 476   assert(isa<PointerType>(getOperand(0)->getType()) &&
 477          "Can not free something of nonpointer type!");
 478 }
 479
 480 FreeInst::FreeInst(Value *Ptr, Instruction *InsertBefore)
 481   : UnaryInstruction(Type::VoidTy, Free, Ptr, "", InsertBefore) {
 482   AssertOK();
 483 }
 484
 485 FreeInst::FreeInst(Value *Ptr, BasicBlock *InsertAtEnd)
 486   : UnaryInstruction(Type::VoidTy, Free, Ptr, "", InsertAtEnd) {
 487   AssertOK();
 488 }
 489
 490
 491 //===----------------------------------------------------------------------===//
 492 //                           LoadInst Implementation
 493 //===----------------------------------------------------------------------===//
 494
 495 void LoadInst::AssertOK() {
 496   assert(isa<PointerType>(getOperand(0)->getType()) &&
 497          "Ptr must have pointer type.");
 498 }
 499
 500 LoadInst::LoadInst(Value *Ptr, const std::string &Name, Instruction *InsertBef)
 501   : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
 502                      Load, Ptr, Name, InsertBef) {
 503   setVolatile(false);
 504   AssertOK();
 505 }
 506
 507 LoadInst::LoadInst(Value *Ptr, const std::string &Name, BasicBlock *InsertAE)
 508   : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
 509                      Load, Ptr, Name, InsertAE) {
 510   setVolatile(false);
 511   AssertOK();
 512 }
 513
 514 LoadInst::LoadInst(Value *Ptr, const std::string &Name, bool isVolatile,
 515                    Instruction *InsertBef)
 516   : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
 517                      Load, Ptr, Name, InsertBef) {
 518   setVolatile(isVolatile);
 519   AssertOK();
 520 }
 521
 522 LoadInst::LoadInst(Value *Ptr, const std::string &Name, bool isVolatile,
 523                    BasicBlock *InsertAE)
 524   : UnaryInstruction(cast<PointerType>(Ptr->getType())->getElementType(),
 525                      Load, Ptr, Name, InsertAE) {
 526   setVolatile(isVolatile);
 527   AssertOK();
 528 }
 529
 530
 531 //===----------------------------------------------------------------------===//
 532 //                           StoreInst Implementation
 533 //===----------------------------------------------------------------------===//
 534
 535 void StoreInst::AssertOK() {
 536   assert(isa<PointerType>(getOperand(1)->getType()) &&
 537          "Ptr must have pointer type!");
 538   assert(getOperand(0)->getType() ==
 539                  cast<PointerType>(getOperand(1)->getType())->getElementType()
 540          && "Ptr must be a pointer to Val type!");
 541 }
 542
 543
 544 StoreInst::StoreInst(Value *val, Value *addr, Instruction *InsertBefore)
 545   : Instruction(Type::VoidTy, Store, Ops, 2, "", InsertBefore) {
 546   Ops[0].init(val, this);
 547   Ops[1].init(addr, this);
 548   setVolatile(false);
 549   AssertOK();
 550 }
 551
 552 StoreInst::StoreInst(Value *val, Value *addr, BasicBlock *InsertAtEnd)
 553   : Instruction(Type::VoidTy, Store, Ops, 2, "", InsertAtEnd) {
 554   Ops[0].init(val, this);
 555   Ops[1].init(addr, this);
 556   setVolatile(false);
 557   AssertOK();
 558 }
 559
 560 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
 561                      Instruction *InsertBefore)
 562   : Instruction(Type::VoidTy, Store, Ops, 2, "", InsertBefore) {
 563   Ops[0].init(val, this);
 564   Ops[1].init(addr, this);
 565   setVolatile(isVolatile);
 566   AssertOK();
 567 }
 568
 569 StoreInst::StoreInst(Value *val, Value *addr, bool isVolatile,
 570                      BasicBlock *InsertAtEnd)
 571   : Instruction(Type::VoidTy, Store, Ops, 2, "", InsertAtEnd) {
 572   Ops[0].init(val, this);
 573   Ops[1].init(addr, this);
 574   setVolatile(isVolatile);
 575   AssertOK();
 576 }
 577
 578 //===----------------------------------------------------------------------===//
 579 //                       GetElementPtrInst Implementation
 580 //===----------------------------------------------------------------------===//
 581
 582 // checkType - Simple wrapper function to give a better assertion failure
 583 // message on bad indexes for a gep instruction.
 584 //
 585 static inline const Type *checkType(const Type *Ty) {
 586   assert(Ty && "Invalid indices for type!");
 587   return Ty;
 588 }
 589
 590 void GetElementPtrInst::init(Value *Ptr, const std::vector<Value*> &Idx) {
 591   NumOperands = 1+Idx.size();
 592   Use *OL = OperandList = new Use[NumOperands];
 593   OL[0].init(Ptr, this);
 594
 595   for (unsigned i = 0, e = Idx.size(); i != e; ++i)
 596     OL[i+1].init(Idx[i], this);
 597 }
 598
 599 void GetElementPtrInst::init(Value *Ptr, Value *Idx0, Value *Idx1) {
 600   NumOperands = 3;
 601   Use *OL = OperandList = new Use[3];
 602   OL[0].init(Ptr, this);
 603   OL[1].init(Idx0, this);
 604   OL[2].init(Idx1, this);
 605 }
 606
 607 void GetElementPtrInst::init(Value *Ptr, Value *Idx) {
 608   NumOperands = 2;
 609   Use *OL = OperandList = new Use[2];
 610   OL[0].init(Ptr, this);
 611   OL[1].init(Idx, this);
 612 }
 613
 614 GetElementPtrInst::GetElementPtrInst(Value *Ptr, const std::vector<Value*> &Idx,
 615                                      const std::string &Name, Instruction *InBe)
 616   : Instruction(PointerType::get(checkType(getIndexedType(Ptr->getType(),
 617                                                           Idx, true))),
 618                 GetElementPtr, 0, 0, Name, InBe) {
 619   init(Ptr, Idx);
 620 }
 621
 622 GetElementPtrInst::GetElementPtrInst(Value *Ptr, const std::vector<Value*> &Idx,
 623                                      const std::string &Name, BasicBlock *IAE)
 624   : Instruction(PointerType::get(checkType(getIndexedType(Ptr->getType(),
 625                                                           Idx, true))),
 626                 GetElementPtr, 0, 0, Name, IAE) {
 627   init(Ptr, Idx);
 628 }
 629
 630 GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx,
 631                                      const std::string &Name, Instruction *InBe)
 632   : Instruction(PointerType::get(checkType(getIndexedType(Ptr->getType(),Idx))),
 633                 GetElementPtr, 0, 0, Name, InBe) {
 634   init(Ptr, Idx);
 635 }
 636
 637 GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx,
 638                                      const std::string &Name, BasicBlock *IAE)
 639   : Instruction(PointerType::get(checkType(getIndexedType(Ptr->getType(),Idx))),
 640                 GetElementPtr, 0, 0, Name, IAE) {
 641   init(Ptr, Idx);
 642 }
 643
 644 GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx0, Value *Idx1,
 645                                      const std::string &Name, Instruction *InBe)
 646   : Instruction(PointerType::get(checkType(getIndexedType(Ptr->getType(),
 647                                                           Idx0, Idx1, true))),
 648                 GetElementPtr, 0, 0, Name, InBe) {
 649   init(Ptr, Idx0, Idx1);
 650 }
 651
 652 GetElementPtrInst::GetElementPtrInst(Value *Ptr, Value *Idx0, Value *Idx1,
 653                                      const std::string &Name, BasicBlock *IAE)
 654   : Instruction(PointerType::get(checkType(getIndexedType(Ptr->getType(),
 655                                                           Idx0, Idx1, true))),
 656                 GetElementPtr, 0, 0, Name, IAE) {
 657   init(Ptr, Idx0, Idx1);
 658 }
 659
 660 GetElementPtrInst::~GetElementPtrInst() {
 661   delete[] OperandList;
 662 }
 663
 664 // getIndexedType - Returns the type of the element that would be loaded with
 665 // a load instruction with the specified parameters.
 666 //
 667 // A null type is returned if the indices are invalid for the specified
 668 // pointer type.
 669 //
 670 const Type* GetElementPtrInst::getIndexedType(const Type *Ptr,
 671                                               const std::vector<Value*> &Idx,
 672                                               bool AllowCompositeLeaf) {
 673   if (!isa<PointerType>(Ptr)) return 0;   // Type isn't a pointer type!
 674
 675   // Handle the special case of the empty set index set...
 676   if (Idx.empty())
 677     if (AllowCompositeLeaf ||
 678         cast<PointerType>(Ptr)->getElementType()->isFirstClassType())
 679       return cast<PointerType>(Ptr)->getElementType();
 680     else
 681       return 0;
 682
 683   unsigned CurIdx = 0;
 684   while (const CompositeType *CT = dyn_cast<CompositeType>(Ptr)) {
 685     if (Idx.size() == CurIdx) {
 686       if (AllowCompositeLeaf || CT->isFirstClassType()) return Ptr;
 687       return 0;   // Can't load a whole structure or array!?!?
 688     }
 689
 690     Value *Index = Idx[CurIdx++];
 691     if (isa<PointerType>(CT) && CurIdx != 1)
 692       return 0;  // Can only index into pointer types at the first index!
 693     if (!CT->indexValid(Index)) return 0;
 694     Ptr = CT->getTypeAtIndex(Index);
 695
 696     // If the new type forwards to another type, then it is in the middle
 697     // of being refined to another type (and hence, may have dropped all
 698     // references to what it was using before).  So, use the new forwarded
 699     // type.
 700     if (const Type * Ty = Ptr->getForwardedType()) {
 701       Ptr = Ty;
 702     }
 703   }
 704   return CurIdx == Idx.size() ? Ptr : 0;
 705 }
 706
 707 const Type* GetElementPtrInst::getIndexedType(const Type *Ptr,
 708                                               Value *Idx0, Value *Idx1,
 709                                               bool AllowCompositeLeaf) {
 710   const PointerType *PTy = dyn_cast<PointerType>(Ptr);
 711   if (!PTy) return 0;   // Type isn't a pointer type!
 712
 713   // Check the pointer index.
 714   if (!PTy->indexValid(Idx0)) return 0;
 715
 716   const CompositeType *CT = dyn_cast<CompositeType>(PTy->getElementType());
 717   if (!CT || !CT->indexValid(Idx1)) return 0;
 718
 719   const Type *ElTy = CT->getTypeAtIndex(Idx1);
 720   if (AllowCompositeLeaf || ElTy->isFirstClassType())
 721     return ElTy;
 722   return 0;
 723 }
 724
 725 const Type* GetElementPtrInst::getIndexedType(const Type *Ptr, Value *Idx) {
 726   const PointerType *PTy = dyn_cast<PointerType>(Ptr);
 727   if (!PTy) return 0;   // Type isn't a pointer type!
 728
 729   // Check the pointer index.
 730   if (!PTy->indexValid(Idx)) return 0;
 731
 732   return PTy->getElementType();
 733 }
 734
 735 //===----------------------------------------------------------------------===//
 736 //                             BinaryOperator Class
 737 //===----------------------------------------------------------------------===//
 738
 739 void BinaryOperator::init(BinaryOps iType)
 740 {
 741   Value *LHS = getOperand(0), *RHS = getOperand(1);
 742   assert(LHS->getType() == RHS->getType() &&
 743          "Binary operator operand types must match!");
 744 #ifndef NDEBUG
 745   switch (iType) {
 746   case Add: case Sub:
 747   case Mul: case Div:
 748   case Rem:
 749     assert(getType() == LHS->getType() &&
 750            "Arithmetic operation should return same type as operands!");
 751     assert((getType()->isInteger() ||
 752             getType()->isFloatingPoint() ||
 753             isa<PackedType>(getType()) ) &&
 754           "Tried to create an arithmetic operation on a non-arithmetic type!");
 755     break;
 756   case And: case Or:
 757   case Xor:
 758     assert(getType() == LHS->getType() &&
 759            "Logical operation should return same type as operands!");
 760     assert(getType()->isIntegral() &&
 761            "Tried to create a logical operation on a non-integral type!");
 762     break;
 763   case SetLT: case SetGT: case SetLE:
 764   case SetGE: case SetEQ: case SetNE:
 765     assert(getType() == Type::BoolTy && "Setcc must return bool!");
 766   default:
 767     break;
 768   }
 769 #endif
 770 }
 771
 772 BinaryOperator *BinaryOperator::create(BinaryOps Op, Value *S1, Value *S2,
 773                                        const std::string &Name,
 774                                        Instruction *InsertBefore) {
 775   assert(S1->getType() == S2->getType() &&
 776          "Cannot create binary operator with two operands of differing type!");
 777   switch (Op) {
 778   // Binary comparison operators...
 779   case SetLT: case SetGT: case SetLE:
 780   case SetGE: case SetEQ: case SetNE:
 781     return new SetCondInst(Op, S1, S2, Name, InsertBefore);
 782
 783   default:
 784     return new BinaryOperator(Op, S1, S2, S1->getType(), Name, InsertBefore);
 785   }
 786 }
 787
 788 BinaryOperator *BinaryOperator::create(BinaryOps Op, Value *S1, Value *S2,
 789                                        const std::string &Name,
 790                                        BasicBlock *InsertAtEnd) {
 791   BinaryOperator *Res = create(Op, S1, S2, Name);
 792   InsertAtEnd->getInstList().push_back(Res);
 793   return Res;
 794 }
 795
 796 BinaryOperator *BinaryOperator::createNeg(Value *Op, const std::string &Name,
 797                                           Instruction *InsertBefore) {
 798   if (!Op->getType()->isFloatingPoint())
 799     return new BinaryOperator(Instruction::Sub,
 800                               Constant::getNullValue(Op->getType()), Op,
 801                               Op->getType(), Name, InsertBefore);
 802   else
 803     return new BinaryOperator(Instruction::Sub,
 804                               ConstantFP::get(Op->getType(), -0.0), Op,
 805                               Op->getType(), Name, InsertBefore);
 806 }
 807
 808 BinaryOperator *BinaryOperator::createNeg(Value *Op, const std::string &Name,
 809                                           BasicBlock *InsertAtEnd) {
 810   if (!Op->getType()->isFloatingPoint())
 811     return new BinaryOperator(Instruction::Sub,
 812                               Constant::getNullValue(Op->getType()), Op,
 813                               Op->getType(), Name, InsertAtEnd);
 814   else
 815     return new BinaryOperator(Instruction::Sub,
 816                               ConstantFP::get(Op->getType(), -0.0), Op,
 817                               Op->getType(), Name, InsertAtEnd);
 818 }
 819
 820 BinaryOperator *BinaryOperator::createNot(Value *Op, const std::string &Name,
 821                                           Instruction *InsertBefore) {
 822   return new BinaryOperator(Instruction::Xor, Op,
 823                             ConstantIntegral::getAllOnesValue(Op->getType()),
 824                             Op->getType(), Name, InsertBefore);
 825 }
 826
 827 BinaryOperator *BinaryOperator::createNot(Value *Op, const std::string &Name,
 828                                           BasicBlock *InsertAtEnd) {
 829   return new BinaryOperator(Instruction::Xor, Op,
 830                             ConstantIntegral::getAllOnesValue(Op->getType()),
 831                             Op->getType(), Name, InsertAtEnd);
 832 }
 833
 834
 835 // isConstantAllOnes - Helper function for several functions below
 836 static inline bool isConstantAllOnes(const Value *V) {
 837   return isa<ConstantIntegral>(V) &&cast<ConstantIntegral>(V)->isAllOnesValue();
 838 }
 839
 840 bool BinaryOperator::isNeg(const Value *V) {
 841   if (const BinaryOperator *Bop = dyn_cast<BinaryOperator>(V))
 842     if (Bop->getOpcode() == Instruction::Sub)
 843       if (!V->getType()->isFloatingPoint())
 844         return Bop->getOperand(0) == Constant::getNullValue(Bop->getType());
 845       else
 846         return Bop->getOperand(0) == ConstantFP::get(Bop->getType(), -0.0);
 847   return false;
 848 }
 849
 850 bool BinaryOperator::isNot(const Value *V) {
 851   if (const BinaryOperator *Bop = dyn_cast<BinaryOperator>(V))
 852     return (Bop->getOpcode() == Instruction::Xor &&
 853             (isConstantAllOnes(Bop->getOperand(1)) ||
 854              isConstantAllOnes(Bop->getOperand(0))));
 855   return false;
 856 }
 857
 858 Value *BinaryOperator::getNegArgument(Value *BinOp) {
 859   assert(isNeg(BinOp) && "getNegArgument from non-'neg' instruction!");
 860   return cast<BinaryOperator>(BinOp)->getOperand(1);
 861 }
 862
 863 const Value *BinaryOperator::getNegArgument(const Value *BinOp) {
 864   return getNegArgument(const_cast<Value*>(BinOp));
 865 }
 866
 867 Value *BinaryOperator::getNotArgument(Value *BinOp) {
 868   assert(isNot(BinOp) && "getNotArgument on non-'not' instruction!");
 869   BinaryOperator *BO = cast<BinaryOperator>(BinOp);
 870   Value *Op0 = BO->getOperand(0);
 871   Value *Op1 = BO->getOperand(1);
 872   if (isConstantAllOnes(Op0)) return Op1;
 873
 874   assert(isConstantAllOnes(Op1));
 875   return Op0;
 876 }
 877
 878 const Value *BinaryOperator::getNotArgument(const Value *BinOp) {
 879   return getNotArgument(const_cast<Value*>(BinOp));
 880 }
 881
 882
 883 // swapOperands - Exchange the two operands to this instruction.  This
 884 // instruction is safe to use on any binary instruction and does not
 885 // modify the semantics of the instruction.  If the instruction is
 886 // order dependent (SetLT f.e.) the opcode is changed.
 887 //
 888 bool BinaryOperator::swapOperands() {
 889   if (isCommutative())
 890     ;  // If the instruction is commutative, it is safe to swap the operands
 891   else if (SetCondInst *SCI = dyn_cast<SetCondInst>(this))
 892     /// FIXME: SetCC instructions shouldn't all have different opcodes.
 893     setOpcode(SCI->getSwappedCondition());
 894   else
 895     return true;   // Can't commute operands
 896
 897   std::swap(Ops[0], Ops[1]);
 898   return false;
 899 }
 900
 901
 902 //===----------------------------------------------------------------------===//
 903 //                             SetCondInst Class
 904 //===----------------------------------------------------------------------===//
 905
 906 SetCondInst::SetCondInst(BinaryOps Opcode, Value *S1, Value *S2,
 907                          const std::string &Name, Instruction *InsertBefore)
 908   : BinaryOperator(Opcode, S1, S2, Type::BoolTy, Name, InsertBefore) {
 909
 910   // Make sure it's a valid type... getInverseCondition will assert out if not.
 911   assert(getInverseCondition(Opcode));
 912 }
 913
 914 SetCondInst::SetCondInst(BinaryOps Opcode, Value *S1, Value *S2,
 915                          const std::string &Name, BasicBlock *InsertAtEnd)
 916   : BinaryOperator(Opcode, S1, S2, Type::BoolTy, Name, InsertAtEnd) {
 917
 918   // Make sure it's a valid type... getInverseCondition will assert out if not.
 919   assert(getInverseCondition(Opcode));
 920 }
 921
 922 // getInverseCondition - Return the inverse of the current condition opcode.
 923 // For example seteq -> setne, setgt -> setle, setlt -> setge, etc...
 924 //
 925 Instruction::BinaryOps SetCondInst::getInverseCondition(BinaryOps Opcode) {
 926   switch (Opcode) {
 927   default:
 928     assert(0 && "Unknown setcc opcode!");
 929   case SetEQ: return SetNE;
 930   case SetNE: return SetEQ;
 931   case SetGT: return SetLE;
 932   case SetLT: return SetGE;
 933   case SetGE: return SetLT;
 934   case SetLE: return SetGT;
 935   }
 936 }
 937
 938 // getSwappedCondition - Return the condition opcode that would be the result
 939 // of exchanging the two operands of the setcc instruction without changing
 940 // the result produced.  Thus, seteq->seteq, setle->setge, setlt->setgt, etc.
 941 //
 942 Instruction::BinaryOps SetCondInst::getSwappedCondition(BinaryOps Opcode) {
 943   switch (Opcode) {
 944   default: assert(0 && "Unknown setcc instruction!");
 945   case SetEQ: case SetNE: return Opcode;
 946   case SetGT: return SetLT;
 947   case SetLT: return SetGT;
 948   case SetGE: return SetLE;
 949   case SetLE: return SetGE;
 950   }
 951 }
 952
 953 //===----------------------------------------------------------------------===//
 954 //                        SwitchInst Implementation
 955 //===----------------------------------------------------------------------===//
 956
 957 void SwitchInst::init(Value *Value, BasicBlock *Default, unsigned NumCases) {
 958   assert(Value && Default);
 959   ReservedSpace = 2+NumCases*2;
 960   NumOperands = 2;
 961   OperandList = new Use[ReservedSpace];
 962
 963   OperandList[0].init(Value, this);
 964   OperandList[1].init(Default, this);
 965 }
 966
 967 SwitchInst::SwitchInst(const SwitchInst &SI)
 968   : TerminatorInst(Instruction::Switch, new Use[SI.getNumOperands()],
 969                    SI.getNumOperands()) {
 970   Use *OL = OperandList, *InOL = SI.OperandList;
 971   for (unsigned i = 0, E = SI.getNumOperands(); i != E; i+=2) {
 972     OL[i].init(InOL[i], this);
 973     OL[i+1].init(InOL[i+1], this);
 974   }
 975 }
 976
 977 SwitchInst::~SwitchInst() {
 978   delete [] OperandList;
 979 }
 980
 981
 982 /// addCase - Add an entry to the switch instruction...
 983 ///
 984 void SwitchInst::addCase(ConstantInt *OnVal, BasicBlock *Dest) {
 985   unsigned OpNo = NumOperands;
 986   if (OpNo+2 > ReservedSpace)
 987     resizeOperands(0);  // Get more space!
 988   // Initialize some new operands.
 989   assert(OpNo+1 < ReservedSpace && "Growing didn't work!");
 990   NumOperands = OpNo+2;
 991   OperandList[OpNo].init(OnVal, this);
 992   OperandList[OpNo+1].init(Dest, this);
 993 }
 994
 995 /// removeCase - This method removes the specified successor from the switch
 996 /// instruction.  Note that this cannot be used to remove the default
 997 /// destination (successor #0).
 998 ///
 999 void SwitchInst::removeCase(unsigned idx) {
1000   assert(idx != 0 && "Cannot remove the default case!");
1001   assert(idx*2 < getNumOperands() && "Successor index out of range!!!");
1002
1003   unsigned NumOps = getNumOperands();
1004   Use *OL = OperandList;
1005
1006   // Move everything after this operand down.
1007   //
1008   // FIXME: we could just swap with the end of the list, then erase.  However,
1009   // client might not expect this to happen.  The code as it is thrashes the
1010   // use/def lists, which is kinda lame.
1011   for (unsigned i = (idx+1)*2; i != NumOps; i += 2) {
1012     OL[i-2] = OL[i];
1013     OL[i-2+1] = OL[i+1];
1014   }
1015
1016   // Nuke the last value.
1017   OL[NumOps-2].set(0);
1018   OL[NumOps-2+1].set(0);
1019   NumOperands = NumOps-2;
1020 }
1021
1022 /// resizeOperands - resize operands - This adjusts the length of the operands
1023 /// list according to the following behavior:
1024 ///   1. If NumOps == 0, grow the operand list in response to a push_back style
1025 ///      of operation.  This grows the number of ops by 1.5 times.
1026 ///   2. If NumOps > NumOperands, reserve space for NumOps operands.
1027 ///   3. If NumOps == NumOperands, trim the reserved space.
1028 ///
1029 void SwitchInst::resizeOperands(unsigned NumOps) {
1030   if (NumOps == 0) {
1031     NumOps = getNumOperands()/2*6;
1032   } else if (NumOps*2 > NumOperands) {
1033     // No resize needed.
1034     if (ReservedSpace >= NumOps) return;
1035   } else if (NumOps == NumOperands) {
1036     if (ReservedSpace == NumOps) return;
1037   } else {
1038     return;
1039   }
1040
1041   ReservedSpace = NumOps;
1042   Use *NewOps = new Use[NumOps];
1043   Use *OldOps = OperandList;
1044   for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
1045       NewOps[i].init(OldOps[i], this);
1046       OldOps[i].set(0);
1047   }
1048   delete [] OldOps;
1049   OperandList = NewOps;
1050 }
1051
1052
1053 BasicBlock *SwitchInst::getSuccessorV(unsigned idx) const {
1054   return getSuccessor(idx);
1055 }
1056 unsigned SwitchInst::getNumSuccessorsV() const {
1057   return getNumSuccessors();
1058 }
1059 void SwitchInst::setSuccessorV(unsigned idx, BasicBlock *B) {
1060   setSuccessor(idx, B);
1061 }
1062
1063
1064 // Define these methods here so vtables don't get emitted into every translation
1065 // unit that uses these classes.
1066
1067 GetElementPtrInst *GetElementPtrInst::clone() const {
1068   return new GetElementPtrInst(*this);
1069 }
1070
1071 BinaryOperator *BinaryOperator::clone() const {
1072   return create(getOpcode(), Ops[0], Ops[1]);
1073 }
1074
1075 MallocInst *MallocInst::clone() const { return new MallocInst(*this); }
1076 AllocaInst *AllocaInst::clone() const { return new AllocaInst(*this); }
1077 FreeInst   *FreeInst::clone()   const { return new FreeInst(getOperand(0)); }
1078 LoadInst   *LoadInst::clone()   const { return new LoadInst(*this); }
1079 StoreInst  *StoreInst::clone()  const { return new StoreInst(*this); }
1080 CastInst   *CastInst::clone()   const { return new CastInst(*this); }
1081 CallInst   *CallInst::clone()   const { return new CallInst(*this); }
1082 ShiftInst  *ShiftInst::clone()  const { return new ShiftInst(*this); }
1083 SelectInst *SelectInst::clone() const { return new SelectInst(*this); }
1084 VANextInst *VANextInst::clone() const { return new VANextInst(*this); }
1085 VAArgInst  *VAArgInst::clone()  const { return new VAArgInst(*this); }
1086 PHINode    *PHINode::clone()    const { return new PHINode(*this); }
1087 ReturnInst *ReturnInst::clone() const { return new ReturnInst(*this); }
1088 BranchInst *BranchInst::clone() const { return new BranchInst(*this); }
1089 SwitchInst *SwitchInst::clone() const { return new SwitchInst(*this); }
1090 InvokeInst *InvokeInst::clone() const { return new InvokeInst(*this); }
1091 UnwindInst *UnwindInst::clone() const { return new UnwindInst(); }
1092 UnreachableInst *UnreachableInst::clone() const { return new UnreachableInst();}