lib/ExecutionEngine/Interpreter/Execution.cpp

   1 //===-- Execution.cpp - Implement code to simulate the program ------------===//
   2 //
   3 //  This file contains the actual instruction interpreter.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "Interpreter.h"
   8 #include "ExecutionAnnotations.h"
   9 #include "llvm/iOther.h"
  10 #include "llvm/iTerminators.h"
  11 #include "llvm/iMemory.h"
  12 #include "llvm/Type.h"
  13 #include "llvm/ConstPoolVals.h"
  14 #include "llvm/Assembly/Writer.h"
  15 #include "llvm/Support/DataTypes.h"
  16 #include "llvm/Target/TargetData.h"
  17 #include "llvm/GlobalVariable.h"
  18
  19 // Create a TargetData structure to handle memory addressing and size/alignment
  20 // computations
  21 //
  22 static TargetData TD("lli Interpreter");
  23
  24 //===----------------------------------------------------------------------===//
  25 //                     Value Manipulation code
  26 //===----------------------------------------------------------------------===//
  27
  28 static unsigned getOperandSlot(Value *V) {
  29   SlotNumber *SN = (SlotNumber*)V->getAnnotation(SlotNumberAID);
  30   assert(SN && "Operand does not have a slot number annotation!");
  31   return SN->SlotNum;
  32 }
  33
  34 #define GET_CONST_VAL(TY, CLASS) \
  35   case Type::TY##TyID: Result.TY##Val = cast<CLASS>(CPV)->getValue(); break
  36
  37 static GenericValue getOperandValue(Value *V, ExecutionContext &SF) {
  38   if (ConstPoolVal *CPV = dyn_cast<ConstPoolVal>(V)) {
  39     GenericValue Result;
  40     switch (CPV->getType()->getPrimitiveID()) {
  41       GET_CONST_VAL(Bool   , ConstPoolBool);
  42       GET_CONST_VAL(UByte  , ConstPoolUInt);
  43       GET_CONST_VAL(SByte  , ConstPoolSInt);
  44       GET_CONST_VAL(UShort , ConstPoolUInt);
  45       GET_CONST_VAL(Short  , ConstPoolSInt);
  46       GET_CONST_VAL(UInt   , ConstPoolUInt);
  47       GET_CONST_VAL(Int    , ConstPoolSInt);
  48       GET_CONST_VAL(ULong  , ConstPoolUInt);
  49       GET_CONST_VAL(Long   , ConstPoolSInt);
  50       GET_CONST_VAL(Float  , ConstPoolFP);
  51       GET_CONST_VAL(Double , ConstPoolFP);
  52     case Type::PointerTyID:
  53       if (isa<ConstPoolPointerNull>(CPV)) {
  54         Result.PointerVal = 0;
  55       } else if (ConstPoolPointerRef *CPR =dyn_cast<ConstPoolPointerRef>(CPV)) {
  56         assert(0 && "Not implemented!");
  57       } else {
  58         assert(0 && "Unknown constant pointer type!");
  59       }
  60       break;
  61     default:
  62       cout << "ERROR: Constant unimp for type: " << CPV->getType() << endl;
  63     }
  64     return Result;
  65   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
  66     GlobalAddress *Address =
  67       (GlobalAddress*)GV->getOrCreateAnnotation(GlobalAddressAID);
  68     GenericValue Result;
  69     Result.PointerVal = (GenericValue*)Address->Ptr;
  70     return Result;
  71   } else {
  72     unsigned TyP = V->getType()->getUniqueID();   // TypePlane for value
  73     return SF.Values[TyP][getOperandSlot(V)];
  74   }
  75 }
  76
  77 static void printOperandInfo(Value *V, ExecutionContext &SF) {
  78   if (isa<ConstPoolVal>(V)) {
  79     cout << "Constant Pool Value\n";
  80   } else if (isa<GlobalValue>(V)) {
  81     cout << "Global Value\n";
  82   } else {
  83     unsigned TyP  = V->getType()->getUniqueID();   // TypePlane for value
  84     unsigned Slot = getOperandSlot(V);
  85     cout << "Value=" << (void*)V << " TypeID=" << TyP << " Slot=" << Slot
  86          << " Addr=" << &SF.Values[TyP][Slot] << " SF=" << &SF << endl;
  87   }
  88 }
  89
  90
  91
  92 static void SetValue(Value *V, GenericValue Val, ExecutionContext &SF) {
  93   unsigned TyP = V->getType()->getUniqueID();   // TypePlane for value
  94
  95   //cout << "Setting value: " << &SF.Values[TyP][getOperandSlot(V)] << endl;
  96   SF.Values[TyP][getOperandSlot(V)] = Val;
  97 }
  98
  99
 100 //===----------------------------------------------------------------------===//
 101 //                    Annotation Wrangling code
 102 //===----------------------------------------------------------------------===//
 103
 104 void Interpreter::initializeExecutionEngine() {
 105   AnnotationManager::registerAnnotationFactory(MethodInfoAID,
 106                                                &MethodInfo::Create);
 107   AnnotationManager::registerAnnotationFactory(GlobalAddressAID,
 108                                                &GlobalAddress::Create);
 109 }
 110
 111 // InitializeMemory - Recursive function to apply a ConstPool value into the
 112 // specified memory location...
 113 //
 114 static void InitializeMemory(ConstPoolVal *Init, char *Addr) {
 115 #define INITIALIZE_MEMORY(TYID, CLASS, TY)  \
 116   case Type::TYID##TyID: {                  \
 117     TY Tmp = cast<CLASS>(Init)->getValue(); \
 118     memcpy(Addr, &Tmp, sizeof(TY));         \
 119   } return
 120
 121   switch (Init->getType()->getPrimitiveID()) {
 122     INITIALIZE_MEMORY(Bool   , ConstPoolBool, bool);
 123     INITIALIZE_MEMORY(UByte  , ConstPoolUInt, unsigned char);
 124     INITIALIZE_MEMORY(SByte  , ConstPoolSInt, signed   char);
 125     INITIALIZE_MEMORY(UShort , ConstPoolUInt, unsigned short);
 126     INITIALIZE_MEMORY(Short  , ConstPoolSInt, signed   short);
 127     INITIALIZE_MEMORY(UInt   , ConstPoolUInt, unsigned int);
 128     INITIALIZE_MEMORY(Int    , ConstPoolSInt, signed   int);
 129     INITIALIZE_MEMORY(ULong  , ConstPoolUInt, uint64_t);
 130     INITIALIZE_MEMORY(Long   , ConstPoolSInt,  int64_t);
 131     INITIALIZE_MEMORY(Float  , ConstPoolFP  , float);
 132     INITIALIZE_MEMORY(Double , ConstPoolFP  , double);
 133 #undef INITIALIZE_MEMORY
 134
 135   case Type::ArrayTyID: {
 136     ConstPoolArray *CPA = cast<ConstPoolArray>(Init);
 137     const vector<Use> &Val = CPA->getValues();
 138     unsigned ElementSize =
 139       TD.getTypeSize(cast<ArrayType>(CPA->getType())->getElementType());
 140     for (unsigned i = 0; i < Val.size(); ++i)
 141       InitializeMemory(cast<ConstPoolVal>(Val[i].get()), Addr+i*ElementSize);
 142     return;
 143   }
 144
 145   case Type::StructTyID: {
 146     ConstPoolStruct *CPS = cast<ConstPoolStruct>(Init);
 147     const StructLayout *SL=TD.getStructLayout(cast<StructType>(CPS->getType()));
 148     const vector<Use> &Val = CPS->getValues();
 149     for (unsigned i = 0; i < Val.size(); ++i)
 150       InitializeMemory(cast<ConstPoolVal>(Val[i].get()),
 151                        Addr+SL->MemberOffsets[i]);
 152     return;
 153   }
 154
 155   case Type::PointerTyID:
 156     if (isa<ConstPoolPointerNull>(Init)) {
 157       *(void**)Addr = 0;
 158     } else if (ConstPoolPointerRef *CPR = dyn_cast<ConstPoolPointerRef>(Init)) {
 159       GlobalAddress *Address =
 160        (GlobalAddress*)CPR->getValue()->getOrCreateAnnotation(GlobalAddressAID);
 161       *(void**)Addr = (GenericValue*)Address->Ptr;
 162     } else {
 163       assert(0 && "Unknown Constant pointer type!");
 164     }
 165     return;
 166
 167   default:
 168     cout << "Bad Type: " << Init->getType()->getDescription() << endl;
 169     assert(0 && "Unknown constant type to initialize memory with!");
 170   }
 171 }
 172
 173 Annotation *GlobalAddress::Create(AnnotationID AID, const Annotable *O, void *){
 174   assert(AID == GlobalAddressAID);
 175
 176   // This annotation will only be created on GlobalValue objects...
 177   GlobalValue *GVal = cast<GlobalValue>((Value*)O);
 178
 179   if (isa<Method>(GVal)) {
 180     // The GlobalAddress object for a method is just a pointer to method itself.
 181     // Don't delete it when the annotation is gone though!
 182     return new GlobalAddress(GVal, false);
 183   }
 184
 185   // Handle the case of a global variable...
 186   assert(isa<GlobalVariable>(GVal) &&
 187          "Global value found that isn't a method or global variable!");
 188   GlobalVariable *GV = cast<GlobalVariable>(GVal);
 189
 190   // First off, we must allocate space for the global variable to point at...
 191   const Type *Ty = GV->getType()->getValueType();  // Type to be allocated
 192   unsigned NumElements = 1;
 193
 194   if (isa<ArrayType>(Ty) && cast<ArrayType>(Ty)->isUnsized()) {
 195     assert(GV->hasInitializer() && "Const val must have an initializer!");
 196     // Allocating a unsized array type?
 197     Ty = cast<const ArrayType>(Ty)->getElementType();  // Get the actual type...
 198
 199     // Get the number of elements being allocated by the array...
 200     NumElements =cast<ConstPoolArray>(GV->getInitializer())->getValues().size();
 201   }
 202
 203   // Allocate enough memory to hold the type...
 204   void *Addr = malloc(NumElements * TD.getTypeSize(Ty));
 205   assert(Addr != 0 && "Null pointer returned by malloc!");
 206
 207   // Initialize the memory if there is an initializer...
 208   if (GV->hasInitializer())
 209     InitializeMemory(GV->getInitializer(), (char*)Addr);
 210
 211   return new GlobalAddress(Addr, true);  // Simply invoke the ctor
 212 }
 213
 214
 215 //===----------------------------------------------------------------------===//
 216 //                    Binary Instruction Implementations
 217 //===----------------------------------------------------------------------===//
 218
 219 #define IMPLEMENT_BINARY_OPERATOR(OP, TY) \
 220    case Type::TY##TyID: Dest.TY##Val = Src1.TY##Val OP Src2.TY##Val; break
 221 #define IMPLEMENT_BINARY_PTR_OPERATOR(OP) \
 222    case Type::PointerTyID: Dest.PointerVal = \
 223      (GenericValue*)((unsigned long)Src1.PointerVal OP (unsigned long)Src2.PointerVal); break
 224
 225 static GenericValue executeAddInst(GenericValue Src1, GenericValue Src2,
 226                                    const Type *Ty, ExecutionContext &SF) {
 227   GenericValue Dest;
 228   switch (Ty->getPrimitiveID()) {
 229     IMPLEMENT_BINARY_OPERATOR(+, UByte);
 230     IMPLEMENT_BINARY_OPERATOR(+, SByte);
 231     IMPLEMENT_BINARY_OPERATOR(+, UShort);
 232     IMPLEMENT_BINARY_OPERATOR(+, Short);
 233     IMPLEMENT_BINARY_OPERATOR(+, UInt);
 234     IMPLEMENT_BINARY_OPERATOR(+, Int);
 235     IMPLEMENT_BINARY_OPERATOR(+, ULong);
 236     IMPLEMENT_BINARY_OPERATOR(+, Long);
 237     IMPLEMENT_BINARY_OPERATOR(+, Float);
 238     IMPLEMENT_BINARY_OPERATOR(+, Double);
 239     IMPLEMENT_BINARY_PTR_OPERATOR(+);
 240   default:
 241     cout << "Unhandled type for Add instruction: " << Ty << endl;
 242   }
 243   return Dest;
 244 }
 245
 246 static GenericValue executeSubInst(GenericValue Src1, GenericValue Src2,
 247                                    const Type *Ty, ExecutionContext &SF) {
 248   GenericValue Dest;
 249   switch (Ty->getPrimitiveID()) {
 250     IMPLEMENT_BINARY_OPERATOR(-, UByte);
 251     IMPLEMENT_BINARY_OPERATOR(-, SByte);
 252     IMPLEMENT_BINARY_OPERATOR(-, UShort);
 253     IMPLEMENT_BINARY_OPERATOR(-, Short);
 254     IMPLEMENT_BINARY_OPERATOR(-, UInt);
 255     IMPLEMENT_BINARY_OPERATOR(-, Int);
 256     IMPLEMENT_BINARY_OPERATOR(-, ULong);
 257     IMPLEMENT_BINARY_OPERATOR(-, Long);
 258     IMPLEMENT_BINARY_OPERATOR(-, Float);
 259     IMPLEMENT_BINARY_OPERATOR(-, Double);
 260     IMPLEMENT_BINARY_PTR_OPERATOR(-);
 261   default:
 262     cout << "Unhandled type for Sub instruction: " << Ty << endl;
 263   }
 264   return Dest;
 265 }
 266
 267 #define IMPLEMENT_SETCC(OP, TY) \
 268    case Type::TY##TyID: Dest.BoolVal = Src1.TY##Val OP Src2.TY##Val; break
 269
 270 static GenericValue executeSetEQInst(GenericValue Src1, GenericValue Src2,
 271                                      const Type *Ty, ExecutionContext &SF) {
 272   GenericValue Dest;
 273   switch (Ty->getPrimitiveID()) {
 274     IMPLEMENT_SETCC(==, UByte);
 275     IMPLEMENT_SETCC(==, SByte);
 276     IMPLEMENT_SETCC(==, UShort);
 277     IMPLEMENT_SETCC(==, Short);
 278     IMPLEMENT_SETCC(==, UInt);
 279     IMPLEMENT_SETCC(==, Int);
 280     IMPLEMENT_SETCC(==, ULong);
 281     IMPLEMENT_SETCC(==, Long);
 282     IMPLEMENT_SETCC(==, Float);
 283     IMPLEMENT_SETCC(==, Double);
 284     IMPLEMENT_SETCC(==, Pointer);
 285   default:
 286     cout << "Unhandled type for SetEQ instruction: " << Ty << endl;
 287   }
 288   return Dest;
 289 }
 290
 291 static GenericValue executeSetNEInst(GenericValue Src1, GenericValue Src2,
 292                                      const Type *Ty, ExecutionContext &SF) {
 293   GenericValue Dest;
 294   switch (Ty->getPrimitiveID()) {
 295     IMPLEMENT_SETCC(!=, UByte);
 296     IMPLEMENT_SETCC(!=, SByte);
 297     IMPLEMENT_SETCC(!=, UShort);
 298     IMPLEMENT_SETCC(!=, Short);
 299     IMPLEMENT_SETCC(!=, UInt);
 300     IMPLEMENT_SETCC(!=, Int);
 301     IMPLEMENT_SETCC(!=, ULong);
 302     IMPLEMENT_SETCC(!=, Long);
 303     IMPLEMENT_SETCC(!=, Float);
 304     IMPLEMENT_SETCC(!=, Double);
 305     IMPLEMENT_SETCC(!=, Pointer);
 306   default:
 307     cout << "Unhandled type for SetNE instruction: " << Ty << endl;
 308   }
 309   return Dest;
 310 }
 311
 312 static GenericValue executeSetLEInst(GenericValue Src1, GenericValue Src2,
 313                                      const Type *Ty, ExecutionContext &SF) {
 314   GenericValue Dest;
 315   switch (Ty->getPrimitiveID()) {
 316     IMPLEMENT_SETCC(<=, UByte);
 317     IMPLEMENT_SETCC(<=, SByte);
 318     IMPLEMENT_SETCC(<=, UShort);
 319     IMPLEMENT_SETCC(<=, Short);
 320     IMPLEMENT_SETCC(<=, UInt);
 321     IMPLEMENT_SETCC(<=, Int);
 322     IMPLEMENT_SETCC(<=, ULong);
 323     IMPLEMENT_SETCC(<=, Long);
 324     IMPLEMENT_SETCC(<=, Float);
 325     IMPLEMENT_SETCC(<=, Double);
 326     IMPLEMENT_SETCC(<=, Pointer);
 327   default:
 328     cout << "Unhandled type for SetLE instruction: " << Ty << endl;
 329   }
 330   return Dest;
 331 }
 332
 333 static GenericValue executeSetGEInst(GenericValue Src1, GenericValue Src2,
 334                                      const Type *Ty, ExecutionContext &SF) {
 335   GenericValue Dest;
 336   switch (Ty->getPrimitiveID()) {
 337     IMPLEMENT_SETCC(>=, UByte);
 338     IMPLEMENT_SETCC(>=, SByte);
 339     IMPLEMENT_SETCC(>=, UShort);
 340     IMPLEMENT_SETCC(>=, Short);
 341     IMPLEMENT_SETCC(>=, UInt);
 342     IMPLEMENT_SETCC(>=, Int);
 343     IMPLEMENT_SETCC(>=, ULong);
 344     IMPLEMENT_SETCC(>=, Long);
 345     IMPLEMENT_SETCC(>=, Float);
 346     IMPLEMENT_SETCC(>=, Double);
 347     IMPLEMENT_SETCC(>=, Pointer);
 348   default:
 349     cout << "Unhandled type for SetGE instruction: " << Ty << endl;
 350   }
 351   return Dest;
 352 }
 353
 354 static GenericValue executeSetLTInst(GenericValue Src1, GenericValue Src2,
 355                                      const Type *Ty, ExecutionContext &SF) {
 356   GenericValue Dest;
 357   switch (Ty->getPrimitiveID()) {
 358     IMPLEMENT_SETCC(<, UByte);
 359     IMPLEMENT_SETCC(<, SByte);
 360     IMPLEMENT_SETCC(<, UShort);
 361     IMPLEMENT_SETCC(<, Short);
 362     IMPLEMENT_SETCC(<, UInt);
 363     IMPLEMENT_SETCC(<, Int);
 364     IMPLEMENT_SETCC(<, ULong);
 365     IMPLEMENT_SETCC(<, Long);
 366     IMPLEMENT_SETCC(<, Float);
 367     IMPLEMENT_SETCC(<, Double);
 368     IMPLEMENT_SETCC(<, Pointer);
 369   default:
 370     cout << "Unhandled type for SetLT instruction: " << Ty << endl;
 371   }
 372   return Dest;
 373 }
 374
 375 static GenericValue executeSetGTInst(GenericValue Src1, GenericValue Src2,
 376                                      const Type *Ty, ExecutionContext &SF) {
 377   GenericValue Dest;
 378   switch (Ty->getPrimitiveID()) {
 379     IMPLEMENT_SETCC(>, UByte);
 380     IMPLEMENT_SETCC(>, SByte);
 381     IMPLEMENT_SETCC(>, UShort);
 382     IMPLEMENT_SETCC(>, Short);
 383     IMPLEMENT_SETCC(>, UInt);
 384     IMPLEMENT_SETCC(>, Int);
 385     IMPLEMENT_SETCC(>, ULong);
 386     IMPLEMENT_SETCC(>, Long);
 387     IMPLEMENT_SETCC(>, Float);
 388     IMPLEMENT_SETCC(>, Double);
 389     IMPLEMENT_SETCC(>, Pointer);
 390   default:
 391     cout << "Unhandled type for SetGT instruction: " << Ty << endl;
 392   }
 393   return Dest;
 394 }
 395
 396 static void executeBinaryInst(BinaryOperator *I, ExecutionContext &SF) {
 397   const Type *Ty = I->getOperand(0)->getType();
 398   GenericValue Src1  = getOperandValue(I->getOperand(0), SF);
 399   GenericValue Src2  = getOperandValue(I->getOperand(1), SF);
 400   GenericValue R;   // Result
 401
 402   switch (I->getOpcode()) {
 403   case Instruction::Add: R = executeAddInst(Src1, Src2, Ty, SF); break;
 404   case Instruction::Sub: R = executeSubInst(Src1, Src2, Ty, SF); break;
 405   case Instruction::SetEQ: R = executeSetEQInst(Src1, Src2, Ty, SF); break;
 406   case Instruction::SetNE: R = executeSetNEInst(Src1, Src2, Ty, SF); break;
 407   case Instruction::SetLE: R = executeSetLEInst(Src1, Src2, Ty, SF); break;
 408   case Instruction::SetGE: R = executeSetGEInst(Src1, Src2, Ty, SF); break;
 409   case Instruction::SetLT: R = executeSetLTInst(Src1, Src2, Ty, SF); break;
 410   case Instruction::SetGT: R = executeSetGTInst(Src1, Src2, Ty, SF); break;
 411   default:
 412     cout << "Don't know how to handle this binary operator!\n-->" << I;
 413   }
 414
 415   SetValue(I, R, SF);
 416 }
 417
 418 //===----------------------------------------------------------------------===//
 419 //                     Terminator Instruction Implementations
 420 //===----------------------------------------------------------------------===//
 421
 422 void Interpreter::executeRetInst(ReturnInst *I, ExecutionContext &SF) {
 423   const Type *RetTy = 0;
 424   GenericValue Result;
 425
 426   // Save away the return value... (if we are not 'ret void')
 427   if (I->getNumOperands()) {
 428     RetTy  = I->getReturnValue()->getType();
 429     Result = getOperandValue(I->getReturnValue(), SF);
 430   }
 431
 432   // Save previously executing meth
 433   const Method *M = ECStack.back().CurMethod;
 434
 435   // Pop the current stack frame... this invalidates SF
 436   ECStack.pop_back();
 437
 438   if (ECStack.empty()) {  // Finished main.  Put result into exit code...
 439     if (RetTy) {          // Nonvoid return type?
 440       cout << "Method " << M->getType() << " \"" << M->getName()
 441            << "\" returned ";
 442       print(RetTy, Result);
 443       cout << endl;
 444
 445       if (RetTy->isIntegral())
 446         ExitCode = Result.SByteVal;   // Capture the exit code of the program
 447     } else {
 448       ExitCode = 0;
 449     }
 450     return;
 451   }
 452
 453   // If we have a previous stack frame, and we have a previous call, fill in
 454   // the return value...
 455   //
 456   ExecutionContext &NewSF = ECStack.back();
 457   if (NewSF.Caller) {
 458     if (NewSF.Caller->getType() != Type::VoidTy)             // Save result...
 459       SetValue(NewSF.Caller, Result, NewSF);
 460
 461     NewSF.Caller = 0;          // We returned from the call...
 462   } else {
 463     // This must be a function that is executing because of a user 'call'
 464     // instruction.
 465     cout << "Method " << M->getType() << " \"" << M->getName()
 466          << "\" returned ";
 467     print(RetTy, Result);
 468     cout << endl;
 469   }
 470 }
 471
 472 void Interpreter::executeBrInst(BranchInst *I, ExecutionContext &SF) {
 473   SF.PrevBB = SF.CurBB;               // Update PrevBB so that PHI nodes work...
 474   BasicBlock *Dest;
 475
 476   Dest = I->getSuccessor(0);          // Uncond branches have a fixed dest...
 477   if (!I->isUnconditional()) {
 478     if (getOperandValue(I->getCondition(), SF).BoolVal == 0) // If false cond...
 479       Dest = I->getSuccessor(1);
 480   }
 481   SF.CurBB   = Dest;                  // Update CurBB to branch destination
 482   SF.CurInst = SF.CurBB->begin();     // Update new instruction ptr...
 483 }
 484
 485 //===----------------------------------------------------------------------===//
 486 //                     Memory Instruction Implementations
 487 //===----------------------------------------------------------------------===//
 488
 489 void Interpreter::executeAllocInst(AllocationInst *I, ExecutionContext &SF) {
 490   const Type *Ty = I->getType()->getValueType();  // Type to be allocated
 491   unsigned NumElements = 1;
 492
 493   if (I->getNumOperands()) {   // Allocating a unsized array type?
 494     assert(isa<ArrayType>(Ty) && cast<const ArrayType>(Ty)->isUnsized() &&
 495            "Allocation inst with size operand for !unsized array type???");
 496     Ty = cast<const ArrayType>(Ty)->getElementType();  // Get the actual type...
 497
 498     // Get the number of elements being allocated by the array...
 499     GenericValue NumEl = getOperandValue(I->getOperand(0), SF);
 500     NumElements = NumEl.UIntVal;
 501   }
 502
 503   // Allocate enough memory to hold the type...
 504   GenericValue Result;
 505   Result.PointerVal = (GenericValue*)malloc(NumElements * TD.getTypeSize(Ty));
 506   assert(Result.PointerVal != 0 && "Null pointer returned by malloc!");
 507   SetValue(I, Result, SF);
 508
 509   if (I->getOpcode() == Instruction::Alloca) {
 510     // TODO: FIXME: alloca should keep track of memory to free it later...
 511   }
 512 }
 513
 514 static void executeFreeInst(FreeInst *I, ExecutionContext &SF) {
 515   assert(I->getOperand(0)->getType()->isPointerType() && "Freeing nonptr?");
 516   GenericValue Value = getOperandValue(I->getOperand(0), SF);
 517   // TODO: Check to make sure memory is allocated
 518   free(Value.PointerVal);   // Free memory
 519 }
 520
 521 static void executeLoadInst(LoadInst *I, ExecutionContext &SF) {
 522   assert(I->getNumOperands() == 1 && "NI!");
 523   GenericValue *Ptr = getOperandValue(I->getPtrOperand(), SF).PointerVal;
 524   GenericValue Result;
 525
 526   switch (I->getType()->getPrimitiveID()) {
 527   case Type::BoolTyID:
 528   case Type::UByteTyID:
 529   case Type::SByteTyID:   Result.SByteVal = Ptr->SByteVal; break;
 530   case Type::UShortTyID:
 531   case Type::ShortTyID:   Result.ShortVal = Ptr->ShortVal; break;
 532   case Type::UIntTyID:
 533   case Type::IntTyID:     Result.IntVal = Ptr->IntVal; break;
 534   case Type::ULongTyID:
 535   case Type::LongTyID:    Result.LongVal = Ptr->LongVal; break;
 536   case Type::FloatTyID:   Result.FloatVal = Ptr->FloatVal; break;
 537   case Type::DoubleTyID:  Result.DoubleVal = Ptr->DoubleVal; break;
 538   case Type::PointerTyID: Result.PointerVal = Ptr->PointerVal; break;
 539   default:
 540     cout << "Cannot load value of type " << I->getType() << "!\n";
 541   }
 542
 543   SetValue(I, Result, SF);
 544 }
 545
 546 static void executeStoreInst(StoreInst *I, ExecutionContext &SF) {
 547   GenericValue *Ptr = getOperandValue(I->getPtrOperand(), SF).PointerVal;
 548   GenericValue Val = getOperandValue(I->getOperand(0), SF);
 549   assert(I->getNumOperands() == 2 && "NI!");
 550
 551   switch (I->getOperand(0)->getType()->getPrimitiveID()) {
 552   case Type::BoolTyID:
 553   case Type::UByteTyID:
 554   case Type::SByteTyID:   Ptr->SByteVal = Val.SByteVal; break;
 555   case Type::UShortTyID:
 556   case Type::ShortTyID:   Ptr->ShortVal = Val.ShortVal; break;
 557   case Type::UIntTyID:
 558   case Type::IntTyID:     Ptr->IntVal = Val.IntVal; break;
 559   case Type::ULongTyID:
 560   case Type::LongTyID:    Ptr->LongVal = Val.LongVal; break;
 561   case Type::FloatTyID:   Ptr->FloatVal = Val.FloatVal; break;
 562   case Type::DoubleTyID:  Ptr->DoubleVal = Val.DoubleVal; break;
 563   case Type::PointerTyID: Ptr->PointerVal = Val.PointerVal; break;
 564   default:
 565     cout << "Cannot store value of type " << I->getType() << "!\n";
 566   }
 567 }
 568
 569
 570 //===----------------------------------------------------------------------===//
 571 //                 Miscellaneous Instruction Implementations
 572 //===----------------------------------------------------------------------===//
 573
 574 void Interpreter::executeCallInst(CallInst *I, ExecutionContext &SF) {
 575   ECStack.back().Caller = I;
 576   vector<GenericValue> ArgVals;
 577   ArgVals.reserve(I->getNumOperands()-1);
 578   for (unsigned i = 1; i < I->getNumOperands(); ++i)
 579     ArgVals.push_back(getOperandValue(I->getOperand(i), SF));
 580
 581   callMethod(I->getCalledMethod(), ArgVals);
 582 }
 583
 584 static void executePHINode(PHINode *I, ExecutionContext &SF) {
 585   BasicBlock *PrevBB = SF.PrevBB;
 586   Value *IncomingValue = 0;
 587
 588   // Search for the value corresponding to this previous bb...
 589   for (unsigned i = I->getNumIncomingValues(); i > 0;) {
 590     if (I->getIncomingBlock(--i) == PrevBB) {
 591       IncomingValue = I->getIncomingValue(i);
 592       break;
 593     }
 594   }
 595   assert(IncomingValue && "No PHI node predecessor for current PrevBB!");
 596
 597   // Found the value, set as the result...
 598   SetValue(I, getOperandValue(IncomingValue, SF), SF);
 599 }
 600
 601 #define IMPLEMENT_SHIFT(OP, TY) \
 602    case Type::TY##TyID: Dest.TY##Val = Src1.TY##Val OP Src2.UByteVal; break
 603
 604 static void executeShlInst(ShiftInst *I, ExecutionContext &SF) {
 605   const Type *Ty = I->getOperand(0)->getType();
 606   GenericValue Src1  = getOperandValue(I->getOperand(0), SF);
 607   GenericValue Src2  = getOperandValue(I->getOperand(1), SF);
 608   GenericValue Dest;
 609
 610   switch (Ty->getPrimitiveID()) {
 611     IMPLEMENT_SHIFT(<<, UByte);
 612     IMPLEMENT_SHIFT(<<, SByte);
 613     IMPLEMENT_SHIFT(<<, UShort);
 614     IMPLEMENT_SHIFT(<<, Short);
 615     IMPLEMENT_SHIFT(<<, UInt);
 616     IMPLEMENT_SHIFT(<<, Int);
 617     IMPLEMENT_SHIFT(<<, ULong);
 618     IMPLEMENT_SHIFT(<<, Long);
 619   default:
 620     cout << "Unhandled type for Shl instruction: " << Ty << endl;
 621   }
 622   SetValue(I, Dest, SF);
 623 }
 624
 625 static void executeShrInst(ShiftInst *I, ExecutionContext &SF) {
 626   const Type *Ty = I->getOperand(0)->getType();
 627   GenericValue Src1  = getOperandValue(I->getOperand(0), SF);
 628   GenericValue Src2  = getOperandValue(I->getOperand(1), SF);
 629   GenericValue Dest;
 630
 631   switch (Ty->getPrimitiveID()) {
 632     IMPLEMENT_SHIFT(>>, UByte);
 633     IMPLEMENT_SHIFT(>>, SByte);
 634     IMPLEMENT_SHIFT(>>, UShort);
 635     IMPLEMENT_SHIFT(>>, Short);
 636     IMPLEMENT_SHIFT(>>, UInt);
 637     IMPLEMENT_SHIFT(>>, Int);
 638     IMPLEMENT_SHIFT(>>, ULong);
 639     IMPLEMENT_SHIFT(>>, Long);
 640   default:
 641     cout << "Unhandled type for Shr instruction: " << Ty << endl;
 642   }
 643   SetValue(I, Dest, SF);
 644 }
 645
 646 #define IMPLEMENT_CAST(DTY, DCTY, STY) \
 647    case Type::STY##TyID: Dest.DTY##Val = (DCTY)Src.STY##Val; break;
 648
 649 #define IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY)    \
 650   case Type::DESTTY##TyID:                      \
 651     switch (SrcTy->getPrimitiveID()) {          \
 652       IMPLEMENT_CAST(DESTTY, DESTCTY, UByte);   \
 653       IMPLEMENT_CAST(DESTTY, DESTCTY, SByte);   \
 654       IMPLEMENT_CAST(DESTTY, DESTCTY, UShort);  \
 655       IMPLEMENT_CAST(DESTTY, DESTCTY, Short);   \
 656       IMPLEMENT_CAST(DESTTY, DESTCTY, UInt);    \
 657       IMPLEMENT_CAST(DESTTY, DESTCTY, Int);     \
 658       IMPLEMENT_CAST(DESTTY, DESTCTY, ULong);   \
 659       IMPLEMENT_CAST(DESTTY, DESTCTY, Long);
 660
 661 #define IMPLEMENT_CAST_CASE_PTR_IMP(DESTTY, DESTCTY) \
 662       IMPLEMENT_CAST(DESTTY, DESTCTY, Pointer)
 663
 664 #define IMPLEMENT_CAST_CASE_FP_IMP(DESTTY, DESTCTY) \
 665       IMPLEMENT_CAST(DESTTY, DESTCTY, Float);   \
 666       IMPLEMENT_CAST(DESTTY, DESTCTY, Double)
 667
 668 #define IMPLEMENT_CAST_CASE_END()    \
 669     default: cout << "Unhandled cast: " << SrcTy << " to " << Ty << endl;  \
 670       break;                                    \
 671     }                                           \
 672     break
 673
 674 #define IMPLEMENT_CAST_CASE(DESTTY, DESTCTY) \
 675    IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY);   \
 676    IMPLEMENT_CAST_CASE_FP_IMP(DESTTY, DESTCTY); \
 677    IMPLEMENT_CAST_CASE_PTR_IMP(DESTTY, DESTCTY); \
 678    IMPLEMENT_CAST_CASE_END()
 679
 680 #define IMPLEMENT_CAST_CASE_FP(DESTTY, DESTCTY) \
 681    IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY);   \
 682    IMPLEMENT_CAST_CASE_FP_IMP(DESTTY, DESTCTY); \
 683    IMPLEMENT_CAST_CASE_END()
 684
 685 #define IMPLEMENT_CAST_CASE_PTR(DESTTY, DESTCTY) \
 686    IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY);   \
 687    IMPLEMENT_CAST_CASE_PTR_IMP(DESTTY, DESTCTY); \
 688    IMPLEMENT_CAST_CASE_END()
 689
 690 static void executeCastInst(CastInst *I, ExecutionContext &SF) {
 691   const Type *Ty = I->getType();
 692   const Type *SrcTy = I->getOperand(0)->getType();
 693   GenericValue Src  = getOperandValue(I->getOperand(0), SF);
 694   GenericValue Dest;
 695
 696   switch (Ty->getPrimitiveID()) {
 697     IMPLEMENT_CAST_CASE(UByte , unsigned char);
 698     IMPLEMENT_CAST_CASE(SByte ,   signed char);
 699     IMPLEMENT_CAST_CASE(UShort, unsigned short);
 700     IMPLEMENT_CAST_CASE(Short ,   signed char);
 701     IMPLEMENT_CAST_CASE(UInt  , unsigned int );
 702     IMPLEMENT_CAST_CASE(Int   ,   signed int );
 703     IMPLEMENT_CAST_CASE(ULong , uint64_t );
 704     IMPLEMENT_CAST_CASE(Long  ,  int64_t );
 705     IMPLEMENT_CAST_CASE_FP(Float ,          float);
 706     IMPLEMENT_CAST_CASE_FP(Double,          double);
 707     IMPLEMENT_CAST_CASE_PTR(Pointer, GenericValue *);
 708   default:
 709     cout << "Unhandled dest type for cast instruction: " << Ty << endl;
 710   }
 711   SetValue(I, Dest, SF);
 712 }
 713
 714
 715
 716
 717 //===----------------------------------------------------------------------===//
 718 //                        Dispatch and Execution Code
 719 //===----------------------------------------------------------------------===//
 720
 721 MethodInfo::MethodInfo(Method *M) : Annotation(MethodInfoAID) {
 722   // Assign slot numbers to the method arguments...
 723   const Method::ArgumentListType &ArgList = M->getArgumentList();
 724   for (Method::ArgumentListType::const_iterator AI = ArgList.begin(),
 725          AE = ArgList.end(); AI != AE; ++AI) {
 726     MethodArgument *MA = *AI;
 727     MA->addAnnotation(new SlotNumber(getValueSlot(MA)));
 728   }
 729
 730   // Iterate over all of the instructions...
 731   unsigned InstNum = 0;
 732   for (Method::inst_iterator MI = M->inst_begin(), ME = M->inst_end();
 733        MI != ME; ++MI) {
 734     Instruction *I = *MI;                          // For each instruction...
 735     I->addAnnotation(new InstNumber(++InstNum, getValueSlot(I))); // Add Annote
 736   }
 737 }
 738
 739 unsigned MethodInfo::getValueSlot(const Value *V) {
 740   unsigned Plane = V->getType()->getUniqueID();
 741   if (Plane >= NumPlaneElements.size())
 742     NumPlaneElements.resize(Plane+1, 0);
 743   return NumPlaneElements[Plane]++;
 744 }
 745
 746
 747 //===----------------------------------------------------------------------===//
 748 // callMethod - Execute the specified method...
 749 //
 750 void Interpreter::callMethod(Method *M, const vector<GenericValue> &ArgVals) {
 751   assert((ECStack.empty() || ECStack.back().Caller == 0 ||
 752           ECStack.back().Caller->getNumOperands()-1 == ArgVals.size()) &&
 753          "Incorrect number of arguments passed into function call!");
 754   if (M->isExternal()) {
 755     callExternalMethod(M, ArgVals);
 756     return;
 757   }
 758
 759   // Process the method, assigning instruction numbers to the instructions in
 760   // the method.  Also calculate the number of values for each type slot active.
 761   //
 762   MethodInfo *MethInfo = (MethodInfo*)M->getOrCreateAnnotation(MethodInfoAID);
 763   ECStack.push_back(ExecutionContext());         // Make a new stack frame...
 764
 765   ExecutionContext &StackFrame = ECStack.back(); // Fill it in...
 766   StackFrame.CurMethod = M;
 767   StackFrame.CurBB     = M->front();
 768   StackFrame.CurInst   = StackFrame.CurBB->begin();
 769   StackFrame.MethInfo  = MethInfo;
 770
 771   // Initialize the values to nothing...
 772   StackFrame.Values.resize(MethInfo->NumPlaneElements.size());
 773   for (unsigned i = 0; i < MethInfo->NumPlaneElements.size(); ++i)
 774     StackFrame.Values[i].resize(MethInfo->NumPlaneElements[i]);
 775
 776   StackFrame.PrevBB = 0;  // No previous BB for PHI nodes...
 777
 778
 779   // Run through the method arguments and initialize their values...
 780   assert(ArgVals.size() == M->getArgumentList().size() &&
 781          "Invalid number of values passed to method invocation!");
 782   unsigned i = 0;
 783   for (Method::ArgumentListType::iterator MI = M->getArgumentList().begin(),
 784          ME = M->getArgumentList().end(); MI != ME; ++MI, ++i) {
 785     SetValue(*MI, ArgVals[i], StackFrame);
 786   }
 787 }
 788
 789 // executeInstruction - Interpret a single instruction, increment the "PC", and
 790 // return true if the next instruction is a breakpoint...
 791 //
 792 bool Interpreter::executeInstruction() {
 793   assert(!ECStack.empty() && "No program running, cannot execute inst!");
 794
 795   ExecutionContext &SF = ECStack.back();  // Current stack frame
 796   Instruction *I = *SF.CurInst++;         // Increment before execute
 797
 798   if (I->isBinaryOp()) {
 799     executeBinaryInst((BinaryOperator*)I, SF);
 800   } else {
 801     switch (I->getOpcode()) {
 802       // Terminators
 803     case Instruction::Ret:     executeRetInst   ((ReturnInst*)I, SF); break;
 804     case Instruction::Br:      executeBrInst    ((BranchInst*)I, SF); break;
 805       // Memory Instructions
 806     case Instruction::Alloca:
 807     case Instruction::Malloc:  executeAllocInst ((AllocationInst*)I, SF); break;
 808     case Instruction::Free:    executeFreeInst  (cast<FreeInst> (I), SF); break;
 809     case Instruction::Load:    executeLoadInst  (cast<LoadInst> (I), SF); break;
 810     case Instruction::Store:   executeStoreInst (cast<StoreInst>(I), SF); break;
 811
 812       // Miscellaneous Instructions
 813     case Instruction::Call:    executeCallInst  (cast<CallInst> (I), SF); break;
 814     case Instruction::PHINode: executePHINode   (cast<PHINode>  (I), SF); break;
 815     case Instruction::Shl:     executeShlInst   (cast<ShiftInst>(I), SF); break;
 816     case Instruction::Shr:     executeShrInst   (cast<ShiftInst>(I), SF); break;
 817     case Instruction::Cast:    executeCastInst  (cast<CastInst> (I), SF); break;
 818     default:
 819       cout << "Don't know how to execute this instruction!\n-->" << I;
 820     }
 821   }
 822
 823   // Reset the current frame location to the top of stack
 824   CurFrame = ECStack.size()-1;
 825
 826   if (CurFrame == -1) return false;  // No breakpoint if no code
 827
 828   // Return true if there is a breakpoint annotation on the instruction...
 829   return (*ECStack[CurFrame].CurInst)->getAnnotation(BreakpointAID) != 0;
 830 }
 831
 832 void Interpreter::stepInstruction() {  // Do the 'step' command
 833   if (ECStack.empty()) {
 834     cout << "Error: no program running, cannot step!\n";
 835     return;
 836   }
 837
 838   // Run an instruction...
 839   executeInstruction();
 840
 841   // Print the next instruction to execute...
 842   printCurrentInstruction();
 843 }
 844
 845 // --- UI Stuff...
 846 void Interpreter::nextInstruction() {  // Do the 'next' command
 847   if (ECStack.empty()) {
 848     cout << "Error: no program running, cannot 'next'!\n";
 849     return;
 850   }
 851
 852   // If this is a call instruction, step over the call instruction...
 853   // TODO: ICALL, CALL WITH, ...
 854   if ((*ECStack.back().CurInst)->getOpcode() == Instruction::Call) {
 855     // Step into the function...
 856     if (executeInstruction()) {
 857       // Hit a breakpoint, print current instruction, then return to user...
 858       cout << "Breakpoint hit!\n";
 859       printCurrentInstruction();
 860       return;
 861     }
 862
 863     // Finish executing the function...
 864     finish();
 865   } else {
 866     // Normal instruction, just step...
 867     stepInstruction();
 868   }
 869 }
 870
 871 void Interpreter::run() {
 872   if (ECStack.empty()) {
 873     cout << "Error: no program running, cannot run!\n";
 874     return;
 875   }
 876
 877   bool HitBreakpoint = false;
 878   while (!ECStack.empty() && !HitBreakpoint) {
 879     // Run an instruction...
 880     HitBreakpoint = executeInstruction();
 881   }
 882
 883   if (HitBreakpoint) {
 884     cout << "Breakpoint hit!\n";
 885   }
 886   // Print the next instruction to execute...
 887   printCurrentInstruction();
 888 }
 889
 890 void Interpreter::finish() {
 891   if (ECStack.empty()) {
 892     cout << "Error: no program running, cannot run!\n";
 893     return;
 894   }
 895
 896   unsigned StackSize = ECStack.size();
 897   bool HitBreakpoint = false;
 898   while (ECStack.size() >= StackSize && !HitBreakpoint) {
 899     // Run an instruction...
 900     HitBreakpoint = executeInstruction();
 901   }
 902
 903   if (HitBreakpoint) {
 904     cout << "Breakpoint hit!\n";
 905   }
 906
 907   // Print the next instruction to execute...
 908   printCurrentInstruction();
 909 }
 910
 911
 912
 913 // printCurrentInstruction - Print out the instruction that the virtual PC is
 914 // at, or fail silently if no program is running.
 915 //
 916 void Interpreter::printCurrentInstruction() {
 917   if (!ECStack.empty()) {
 918     Instruction *I = *ECStack.back().CurInst;
 919     InstNumber *IN = (InstNumber*)I->getAnnotation(SlotNumberAID);
 920     assert(IN && "Instruction has no numbering annotation!");
 921     cout << "#" << IN->InstNum << I;
 922   }
 923 }
 924
 925 void Interpreter::printValue(const Type *Ty, GenericValue V) {
 926   switch (Ty->getPrimitiveID()) {
 927   case Type::BoolTyID:   cout << (V.BoolVal?"true":"false"); break;
 928   case Type::SByteTyID:  cout << V.SByteVal;  break;
 929   case Type::UByteTyID:  cout << V.UByteVal;  break;
 930   case Type::ShortTyID:  cout << V.ShortVal;  break;
 931   case Type::UShortTyID: cout << V.UShortVal; break;
 932   case Type::IntTyID:    cout << V.IntVal;    break;
 933   case Type::UIntTyID:   cout << V.UIntVal;   break;
 934   case Type::LongTyID:   cout << V.LongVal;   break;
 935   case Type::ULongTyID:  cout << V.ULongVal;  break;
 936   case Type::FloatTyID:  cout << V.FloatVal;  break;
 937   case Type::DoubleTyID: cout << V.DoubleVal; break;
 938   case Type::PointerTyID:cout << V.PointerVal; break;
 939   default:
 940     cout << "- Don't know how to print value of this type!";
 941     break;
 942   }
 943 }
 944
 945 void Interpreter::print(const Type *Ty, GenericValue V) {
 946   cout << Ty << " ";
 947   printValue(Ty, V);
 948 }
 949
 950 void Interpreter::print(const string &Name) {
 951   Value *PickedVal = ChooseOneOption(Name, LookupMatchingNames(Name));
 952   if (!PickedVal) return;
 953
 954   if (const Method *M = dyn_cast<const Method>(PickedVal)) {
 955     cout << M;  // Print the method
 956   } else {      // Otherwise there should be an annotation for the slot#
 957     print(PickedVal->getType(),
 958           getOperandValue(PickedVal, ECStack[CurFrame]));
 959     cout << endl;
 960   }
 961
 962 }
 963
 964 void Interpreter::infoValue(const string &Name) {
 965   Value *PickedVal = ChooseOneOption(Name, LookupMatchingNames(Name));
 966   if (!PickedVal) return;
 967
 968   cout << "Value: ";
 969   print(PickedVal->getType(),
 970         getOperandValue(PickedVal, ECStack[CurFrame]));
 971   cout << endl;
 972   printOperandInfo(PickedVal, ECStack[CurFrame]);
 973 }
 974
 975 void Interpreter::list() {
 976   if (ECStack.empty())
 977     cout << "Error: No program executing!\n";
 978   else
 979     cout << ECStack[CurFrame].CurMethod;   // Just print the method out...
 980 }
 981
 982 void Interpreter::printStackTrace() {
 983   if (ECStack.empty()) cout << "No program executing!\n";
 984
 985   for (unsigned i = 0; i < ECStack.size(); ++i) {
 986     cout << (((int)i == CurFrame) ? '>' : '-');
 987     cout << "#" << i << ". " << ECStack[i].CurMethod->getType() << " \""
 988          << ECStack[i].CurMethod->getName() << "\"(";
 989     // TODO: Print Args
 990     cout << ")" << endl;
 991     cout << *ECStack[i].CurInst;
 992   }
 993 }