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::exitCalled(GenericValue GV) {
 423   cout << "Program returned ";
 424   print(Type::IntTy, GV);
 425   cout << " via 'void exit(int)'\n";
 426
 427   ExitCode = GV.SByteVal;
 428   ECStack.clear();
 429 }
 430
 431 void Interpreter::executeRetInst(ReturnInst *I, ExecutionContext &SF) {
 432   const Type *RetTy = 0;
 433   GenericValue Result;
 434
 435   // Save away the return value... (if we are not 'ret void')
 436   if (I->getNumOperands()) {
 437     RetTy  = I->getReturnValue()->getType();
 438     Result = getOperandValue(I->getReturnValue(), SF);
 439   }
 440
 441   // Save previously executing meth
 442   const Method *M = ECStack.back().CurMethod;
 443
 444   // Pop the current stack frame... this invalidates SF
 445   ECStack.pop_back();
 446
 447   if (ECStack.empty()) {  // Finished main.  Put result into exit code...
 448     if (RetTy) {          // Nonvoid return type?
 449       cout << "Method " << M->getType() << " \"" << M->getName()
 450            << "\" returned ";
 451       print(RetTy, Result);
 452       cout << endl;
 453
 454       if (RetTy->isIntegral())
 455         ExitCode = Result.SByteVal;   // Capture the exit code of the program
 456     } else {
 457       ExitCode = 0;
 458     }
 459     return;
 460   }
 461
 462   // If we have a previous stack frame, and we have a previous call, fill in
 463   // the return value...
 464   //
 465   ExecutionContext &NewSF = ECStack.back();
 466   if (NewSF.Caller) {
 467     if (NewSF.Caller->getType() != Type::VoidTy)             // Save result...
 468       SetValue(NewSF.Caller, Result, NewSF);
 469
 470     NewSF.Caller = 0;          // We returned from the call...
 471   } else {
 472     // This must be a function that is executing because of a user 'call'
 473     // instruction.
 474     cout << "Method " << M->getType() << " \"" << M->getName()
 475          << "\" returned ";
 476     print(RetTy, Result);
 477     cout << endl;
 478   }
 479 }
 480
 481 void Interpreter::executeBrInst(BranchInst *I, ExecutionContext &SF) {
 482   SF.PrevBB = SF.CurBB;               // Update PrevBB so that PHI nodes work...
 483   BasicBlock *Dest;
 484
 485   Dest = I->getSuccessor(0);          // Uncond branches have a fixed dest...
 486   if (!I->isUnconditional()) {
 487     if (getOperandValue(I->getCondition(), SF).BoolVal == 0) // If false cond...
 488       Dest = I->getSuccessor(1);
 489   }
 490   SF.CurBB   = Dest;                  // Update CurBB to branch destination
 491   SF.CurInst = SF.CurBB->begin();     // Update new instruction ptr...
 492 }
 493
 494 //===----------------------------------------------------------------------===//
 495 //                     Memory Instruction Implementations
 496 //===----------------------------------------------------------------------===//
 497
 498 void Interpreter::executeAllocInst(AllocationInst *I, ExecutionContext &SF) {
 499   const Type *Ty = I->getType()->getValueType();  // Type to be allocated
 500   unsigned NumElements = 1;
 501
 502   if (I->getNumOperands()) {   // Allocating a unsized array type?
 503     assert(isa<ArrayType>(Ty) && cast<const ArrayType>(Ty)->isUnsized() &&
 504            "Allocation inst with size operand for !unsized array type???");
 505     Ty = cast<const ArrayType>(Ty)->getElementType();  // Get the actual type...
 506
 507     // Get the number of elements being allocated by the array...
 508     GenericValue NumEl = getOperandValue(I->getOperand(0), SF);
 509     NumElements = NumEl.UIntVal;
 510   }
 511
 512   // Allocate enough memory to hold the type...
 513   GenericValue Result;
 514   Result.PointerVal = (GenericValue*)malloc(NumElements * TD.getTypeSize(Ty));
 515   assert(Result.PointerVal != 0 && "Null pointer returned by malloc!");
 516   SetValue(I, Result, SF);
 517
 518   if (I->getOpcode() == Instruction::Alloca) {
 519     // TODO: FIXME: alloca should keep track of memory to free it later...
 520   }
 521 }
 522
 523 static void executeFreeInst(FreeInst *I, ExecutionContext &SF) {
 524   assert(I->getOperand(0)->getType()->isPointerType() && "Freeing nonptr?");
 525   GenericValue Value = getOperandValue(I->getOperand(0), SF);
 526   // TODO: Check to make sure memory is allocated
 527   free(Value.PointerVal);   // Free memory
 528 }
 529
 530 static void executeLoadInst(LoadInst *I, ExecutionContext &SF) {
 531   assert(I->getNumOperands() == 1 && "NI!");
 532   GenericValue *Ptr = getOperandValue(I->getPtrOperand(), SF).PointerVal;
 533   GenericValue Result;
 534
 535   switch (I->getType()->getPrimitiveID()) {
 536   case Type::BoolTyID:
 537   case Type::UByteTyID:
 538   case Type::SByteTyID:   Result.SByteVal = Ptr->SByteVal; break;
 539   case Type::UShortTyID:
 540   case Type::ShortTyID:   Result.ShortVal = Ptr->ShortVal; break;
 541   case Type::UIntTyID:
 542   case Type::IntTyID:     Result.IntVal = Ptr->IntVal; break;
 543   case Type::ULongTyID:
 544   case Type::LongTyID:    Result.LongVal = Ptr->LongVal; break;
 545   case Type::FloatTyID:   Result.FloatVal = Ptr->FloatVal; break;
 546   case Type::DoubleTyID:  Result.DoubleVal = Ptr->DoubleVal; break;
 547   case Type::PointerTyID: Result.PointerVal =(GenericValue*)Ptr->LongVal; break;
 548   default:
 549     cout << "Cannot load value of type " << I->getType() << "!\n";
 550   }
 551
 552   SetValue(I, Result, SF);
 553 }
 554
 555 static void executeStoreInst(StoreInst *I, ExecutionContext &SF) {
 556   GenericValue *Ptr = getOperandValue(I->getPtrOperand(), SF).PointerVal;
 557   GenericValue Val = getOperandValue(I->getOperand(0), SF);
 558   assert(I->getNumOperands() == 2 && "NI!");
 559
 560   switch (I->getOperand(0)->getType()->getPrimitiveID()) {
 561   case Type::BoolTyID:
 562   case Type::UByteTyID:
 563   case Type::SByteTyID:   Ptr->SByteVal = Val.SByteVal; break;
 564   case Type::UShortTyID:
 565   case Type::ShortTyID:   Ptr->ShortVal = Val.ShortVal; break;
 566   case Type::UIntTyID:
 567   case Type::IntTyID:     Ptr->IntVal = Val.IntVal; break;
 568   case Type::ULongTyID:
 569   case Type::LongTyID:    Ptr->LongVal = Val.LongVal; break;
 570   case Type::FloatTyID:   Ptr->FloatVal = Val.FloatVal; break;
 571   case Type::DoubleTyID:  Ptr->DoubleVal = Val.DoubleVal; break;
 572   case Type::PointerTyID: Ptr->PointerVal = Val.PointerVal; break;
 573   default:
 574     cout << "Cannot store value of type " << I->getType() << "!\n";
 575   }
 576 }
 577
 578
 579 //===----------------------------------------------------------------------===//
 580 //                 Miscellaneous Instruction Implementations
 581 //===----------------------------------------------------------------------===//
 582
 583 void Interpreter::executeCallInst(CallInst *I, ExecutionContext &SF) {
 584   ECStack.back().Caller = I;
 585   vector<GenericValue> ArgVals;
 586   ArgVals.reserve(I->getNumOperands()-1);
 587   for (unsigned i = 1; i < I->getNumOperands(); ++i)
 588     ArgVals.push_back(getOperandValue(I->getOperand(i), SF));
 589
 590   callMethod(I->getCalledMethod(), ArgVals);
 591 }
 592
 593 static void executePHINode(PHINode *I, ExecutionContext &SF) {
 594   BasicBlock *PrevBB = SF.PrevBB;
 595   Value *IncomingValue = 0;
 596
 597   // Search for the value corresponding to this previous bb...
 598   for (unsigned i = I->getNumIncomingValues(); i > 0;) {
 599     if (I->getIncomingBlock(--i) == PrevBB) {
 600       IncomingValue = I->getIncomingValue(i);
 601       break;
 602     }
 603   }
 604   assert(IncomingValue && "No PHI node predecessor for current PrevBB!");
 605
 606   // Found the value, set as the result...
 607   SetValue(I, getOperandValue(IncomingValue, SF), SF);
 608 }
 609
 610 #define IMPLEMENT_SHIFT(OP, TY) \
 611    case Type::TY##TyID: Dest.TY##Val = Src1.TY##Val OP Src2.UByteVal; break
 612
 613 static void executeShlInst(ShiftInst *I, ExecutionContext &SF) {
 614   const Type *Ty = I->getOperand(0)->getType();
 615   GenericValue Src1  = getOperandValue(I->getOperand(0), SF);
 616   GenericValue Src2  = getOperandValue(I->getOperand(1), SF);
 617   GenericValue Dest;
 618
 619   switch (Ty->getPrimitiveID()) {
 620     IMPLEMENT_SHIFT(<<, UByte);
 621     IMPLEMENT_SHIFT(<<, SByte);
 622     IMPLEMENT_SHIFT(<<, UShort);
 623     IMPLEMENT_SHIFT(<<, Short);
 624     IMPLEMENT_SHIFT(<<, UInt);
 625     IMPLEMENT_SHIFT(<<, Int);
 626     IMPLEMENT_SHIFT(<<, ULong);
 627     IMPLEMENT_SHIFT(<<, Long);
 628   default:
 629     cout << "Unhandled type for Shl instruction: " << Ty << endl;
 630   }
 631   SetValue(I, Dest, SF);
 632 }
 633
 634 static void executeShrInst(ShiftInst *I, ExecutionContext &SF) {
 635   const Type *Ty = I->getOperand(0)->getType();
 636   GenericValue Src1  = getOperandValue(I->getOperand(0), SF);
 637   GenericValue Src2  = getOperandValue(I->getOperand(1), SF);
 638   GenericValue Dest;
 639
 640   switch (Ty->getPrimitiveID()) {
 641     IMPLEMENT_SHIFT(>>, UByte);
 642     IMPLEMENT_SHIFT(>>, SByte);
 643     IMPLEMENT_SHIFT(>>, UShort);
 644     IMPLEMENT_SHIFT(>>, Short);
 645     IMPLEMENT_SHIFT(>>, UInt);
 646     IMPLEMENT_SHIFT(>>, Int);
 647     IMPLEMENT_SHIFT(>>, ULong);
 648     IMPLEMENT_SHIFT(>>, Long);
 649   default:
 650     cout << "Unhandled type for Shr instruction: " << Ty << endl;
 651   }
 652   SetValue(I, Dest, SF);
 653 }
 654
 655 #define IMPLEMENT_CAST(DTY, DCTY, STY) \
 656    case Type::STY##TyID: Dest.DTY##Val = (DCTY)Src.STY##Val; break;
 657
 658 #define IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY)    \
 659   case Type::DESTTY##TyID:                      \
 660     switch (SrcTy->getPrimitiveID()) {          \
 661       IMPLEMENT_CAST(DESTTY, DESTCTY, UByte);   \
 662       IMPLEMENT_CAST(DESTTY, DESTCTY, SByte);   \
 663       IMPLEMENT_CAST(DESTTY, DESTCTY, UShort);  \
 664       IMPLEMENT_CAST(DESTTY, DESTCTY, Short);   \
 665       IMPLEMENT_CAST(DESTTY, DESTCTY, UInt);    \
 666       IMPLEMENT_CAST(DESTTY, DESTCTY, Int);     \
 667       IMPLEMENT_CAST(DESTTY, DESTCTY, ULong);   \
 668       IMPLEMENT_CAST(DESTTY, DESTCTY, Long);
 669
 670 #define IMPLEMENT_CAST_CASE_PTR_IMP(DESTTY, DESTCTY) \
 671       IMPLEMENT_CAST(DESTTY, DESTCTY, Pointer)
 672
 673 #define IMPLEMENT_CAST_CASE_FP_IMP(DESTTY, DESTCTY) \
 674       IMPLEMENT_CAST(DESTTY, DESTCTY, Float);   \
 675       IMPLEMENT_CAST(DESTTY, DESTCTY, Double)
 676
 677 #define IMPLEMENT_CAST_CASE_END()    \
 678     default: cout << "Unhandled cast: " << SrcTy << " to " << Ty << endl;  \
 679       break;                                    \
 680     }                                           \
 681     break
 682
 683 #define IMPLEMENT_CAST_CASE(DESTTY, DESTCTY) \
 684    IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY);   \
 685    IMPLEMENT_CAST_CASE_FP_IMP(DESTTY, DESTCTY); \
 686    IMPLEMENT_CAST_CASE_PTR_IMP(DESTTY, DESTCTY); \
 687    IMPLEMENT_CAST_CASE_END()
 688
 689 #define IMPLEMENT_CAST_CASE_FP(DESTTY, DESTCTY) \
 690    IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY);   \
 691    IMPLEMENT_CAST_CASE_FP_IMP(DESTTY, DESTCTY); \
 692    IMPLEMENT_CAST_CASE_END()
 693
 694 #define IMPLEMENT_CAST_CASE_PTR(DESTTY, DESTCTY) \
 695    IMPLEMENT_CAST_CASE_START(DESTTY, DESTCTY);   \
 696    IMPLEMENT_CAST_CASE_PTR_IMP(DESTTY, DESTCTY); \
 697    IMPLEMENT_CAST_CASE_END()
 698
 699 static void executeCastInst(CastInst *I, ExecutionContext &SF) {
 700   const Type *Ty = I->getType();
 701   const Type *SrcTy = I->getOperand(0)->getType();
 702   GenericValue Src  = getOperandValue(I->getOperand(0), SF);
 703   GenericValue Dest;
 704
 705   switch (Ty->getPrimitiveID()) {
 706     IMPLEMENT_CAST_CASE(UByte , unsigned char);
 707     IMPLEMENT_CAST_CASE(SByte ,   signed char);
 708     IMPLEMENT_CAST_CASE(UShort, unsigned short);
 709     IMPLEMENT_CAST_CASE(Short ,   signed char);
 710     IMPLEMENT_CAST_CASE(UInt  , unsigned int );
 711     IMPLEMENT_CAST_CASE(Int   ,   signed int );
 712     IMPLEMENT_CAST_CASE(ULong , uint64_t );
 713     IMPLEMENT_CAST_CASE(Long  ,  int64_t );
 714     IMPLEMENT_CAST_CASE_FP(Float ,          float);
 715     IMPLEMENT_CAST_CASE_FP(Double,          double);
 716     IMPLEMENT_CAST_CASE_PTR(Pointer, GenericValue *);
 717   default:
 718     cout << "Unhandled dest type for cast instruction: " << Ty << endl;
 719   }
 720   SetValue(I, Dest, SF);
 721 }
 722
 723
 724
 725
 726 //===----------------------------------------------------------------------===//
 727 //                        Dispatch and Execution Code
 728 //===----------------------------------------------------------------------===//
 729
 730 MethodInfo::MethodInfo(Method *M) : Annotation(MethodInfoAID) {
 731   // Assign slot numbers to the method arguments...
 732   const Method::ArgumentListType &ArgList = M->getArgumentList();
 733   for (Method::ArgumentListType::const_iterator AI = ArgList.begin(),
 734          AE = ArgList.end(); AI != AE; ++AI) {
 735     MethodArgument *MA = *AI;
 736     MA->addAnnotation(new SlotNumber(getValueSlot(MA)));
 737   }
 738
 739   // Iterate over all of the instructions...
 740   unsigned InstNum = 0;
 741   for (Method::inst_iterator MI = M->inst_begin(), ME = M->inst_end();
 742        MI != ME; ++MI) {
 743     Instruction *I = *MI;                          // For each instruction...
 744     I->addAnnotation(new InstNumber(++InstNum, getValueSlot(I))); // Add Annote
 745   }
 746 }
 747
 748 unsigned MethodInfo::getValueSlot(const Value *V) {
 749   unsigned Plane = V->getType()->getUniqueID();
 750   if (Plane >= NumPlaneElements.size())
 751     NumPlaneElements.resize(Plane+1, 0);
 752   return NumPlaneElements[Plane]++;
 753 }
 754
 755
 756 //===----------------------------------------------------------------------===//
 757 // callMethod - Execute the specified method...
 758 //
 759 void Interpreter::callMethod(Method *M, const vector<GenericValue> &ArgVals) {
 760   assert((ECStack.empty() || ECStack.back().Caller == 0 ||
 761           ECStack.back().Caller->getNumOperands()-1 == ArgVals.size()) &&
 762          "Incorrect number of arguments passed into function call!");
 763   if (M->isExternal()) {
 764     callExternalMethod(M, ArgVals);
 765     return;
 766   }
 767
 768   // Process the method, assigning instruction numbers to the instructions in
 769   // the method.  Also calculate the number of values for each type slot active.
 770   //
 771   MethodInfo *MethInfo = (MethodInfo*)M->getOrCreateAnnotation(MethodInfoAID);
 772   ECStack.push_back(ExecutionContext());         // Make a new stack frame...
 773
 774   ExecutionContext &StackFrame = ECStack.back(); // Fill it in...
 775   StackFrame.CurMethod = M;
 776   StackFrame.CurBB     = M->front();
 777   StackFrame.CurInst   = StackFrame.CurBB->begin();
 778   StackFrame.MethInfo  = MethInfo;
 779
 780   // Initialize the values to nothing...
 781   StackFrame.Values.resize(MethInfo->NumPlaneElements.size());
 782   for (unsigned i = 0; i < MethInfo->NumPlaneElements.size(); ++i)
 783     StackFrame.Values[i].resize(MethInfo->NumPlaneElements[i]);
 784
 785   StackFrame.PrevBB = 0;  // No previous BB for PHI nodes...
 786
 787
 788   // Run through the method arguments and initialize their values...
 789   assert(ArgVals.size() == M->getArgumentList().size() &&
 790          "Invalid number of values passed to method invocation!");
 791   unsigned i = 0;
 792   for (Method::ArgumentListType::iterator MI = M->getArgumentList().begin(),
 793          ME = M->getArgumentList().end(); MI != ME; ++MI, ++i) {
 794     SetValue(*MI, ArgVals[i], StackFrame);
 795   }
 796 }
 797
 798 // executeInstruction - Interpret a single instruction, increment the "PC", and
 799 // return true if the next instruction is a breakpoint...
 800 //
 801 bool Interpreter::executeInstruction() {
 802   assert(!ECStack.empty() && "No program running, cannot execute inst!");
 803
 804   ExecutionContext &SF = ECStack.back();  // Current stack frame
 805   Instruction *I = *SF.CurInst++;         // Increment before execute
 806
 807   if (I->isBinaryOp()) {
 808     executeBinaryInst((BinaryOperator*)I, SF);
 809   } else {
 810     switch (I->getOpcode()) {
 811       // Terminators
 812     case Instruction::Ret:     executeRetInst   ((ReturnInst*)I, SF); break;
 813     case Instruction::Br:      executeBrInst    ((BranchInst*)I, SF); break;
 814       // Memory Instructions
 815     case Instruction::Alloca:
 816     case Instruction::Malloc:  executeAllocInst ((AllocationInst*)I, SF); break;
 817     case Instruction::Free:    executeFreeInst  (cast<FreeInst> (I), SF); break;
 818     case Instruction::Load:    executeLoadInst  (cast<LoadInst> (I), SF); break;
 819     case Instruction::Store:   executeStoreInst (cast<StoreInst>(I), SF); break;
 820
 821       // Miscellaneous Instructions
 822     case Instruction::Call:    executeCallInst  (cast<CallInst> (I), SF); break;
 823     case Instruction::PHINode: executePHINode   (cast<PHINode>  (I), SF); break;
 824     case Instruction::Shl:     executeShlInst   (cast<ShiftInst>(I), SF); break;
 825     case Instruction::Shr:     executeShrInst   (cast<ShiftInst>(I), SF); break;
 826     case Instruction::Cast:    executeCastInst  (cast<CastInst> (I), SF); break;
 827     default:
 828       cout << "Don't know how to execute this instruction!\n-->" << I;
 829     }
 830   }
 831
 832   // Reset the current frame location to the top of stack
 833   CurFrame = ECStack.size()-1;
 834
 835   if (CurFrame == -1) return false;  // No breakpoint if no code
 836
 837   // Return true if there is a breakpoint annotation on the instruction...
 838   return (*ECStack[CurFrame].CurInst)->getAnnotation(BreakpointAID) != 0;
 839 }
 840
 841 void Interpreter::stepInstruction() {  // Do the 'step' command
 842   if (ECStack.empty()) {
 843     cout << "Error: no program running, cannot step!\n";
 844     return;
 845   }
 846
 847   // Run an instruction...
 848   executeInstruction();
 849
 850   // Print the next instruction to execute...
 851   printCurrentInstruction();
 852 }
 853
 854 // --- UI Stuff...
 855 void Interpreter::nextInstruction() {  // Do the 'next' command
 856   if (ECStack.empty()) {
 857     cout << "Error: no program running, cannot 'next'!\n";
 858     return;
 859   }
 860
 861   // If this is a call instruction, step over the call instruction...
 862   // TODO: ICALL, CALL WITH, ...
 863   if ((*ECStack.back().CurInst)->getOpcode() == Instruction::Call) {
 864     // Step into the function...
 865     if (executeInstruction()) {
 866       // Hit a breakpoint, print current instruction, then return to user...
 867       cout << "Breakpoint hit!\n";
 868       printCurrentInstruction();
 869       return;
 870     }
 871
 872     // Finish executing the function...
 873     finish();
 874   } else {
 875     // Normal instruction, just step...
 876     stepInstruction();
 877   }
 878 }
 879
 880 void Interpreter::run() {
 881   if (ECStack.empty()) {
 882     cout << "Error: no program running, cannot run!\n";
 883     return;
 884   }
 885
 886   bool HitBreakpoint = false;
 887   while (!ECStack.empty() && !HitBreakpoint) {
 888     // Run an instruction...
 889     HitBreakpoint = executeInstruction();
 890   }
 891
 892   if (HitBreakpoint) {
 893     cout << "Breakpoint hit!\n";
 894   }
 895   // Print the next instruction to execute...
 896   printCurrentInstruction();
 897 }
 898
 899 void Interpreter::finish() {
 900   if (ECStack.empty()) {
 901     cout << "Error: no program running, cannot run!\n";
 902     return;
 903   }
 904
 905   unsigned StackSize = ECStack.size();
 906   bool HitBreakpoint = false;
 907   while (ECStack.size() >= StackSize && !HitBreakpoint) {
 908     // Run an instruction...
 909     HitBreakpoint = executeInstruction();
 910   }
 911
 912   if (HitBreakpoint) {
 913     cout << "Breakpoint hit!\n";
 914   }
 915
 916   // Print the next instruction to execute...
 917   printCurrentInstruction();
 918 }
 919
 920
 921
 922 // printCurrentInstruction - Print out the instruction that the virtual PC is
 923 // at, or fail silently if no program is running.
 924 //
 925 void Interpreter::printCurrentInstruction() {
 926   if (!ECStack.empty()) {
 927     Instruction *I = *ECStack.back().CurInst;
 928     InstNumber *IN = (InstNumber*)I->getAnnotation(SlotNumberAID);
 929     assert(IN && "Instruction has no numbering annotation!");
 930     cout << "#" << IN->InstNum << I;
 931   }
 932 }
 933
 934 void Interpreter::printValue(const Type *Ty, GenericValue V) {
 935   switch (Ty->getPrimitiveID()) {
 936   case Type::BoolTyID:   cout << (V.BoolVal?"true":"false"); break;
 937   case Type::SByteTyID:  cout << V.SByteVal;  break;
 938   case Type::UByteTyID:  cout << V.UByteVal;  break;
 939   case Type::ShortTyID:  cout << V.ShortVal;  break;
 940   case Type::UShortTyID: cout << V.UShortVal; break;
 941   case Type::IntTyID:    cout << V.IntVal;    break;
 942   case Type::UIntTyID:   cout << V.UIntVal;   break;
 943   case Type::LongTyID:   cout << V.LongVal;   break;
 944   case Type::ULongTyID:  cout << V.ULongVal;  break;
 945   case Type::FloatTyID:  cout << V.FloatVal;  break;
 946   case Type::DoubleTyID: cout << V.DoubleVal; break;
 947   case Type::PointerTyID:cout << V.PointerVal; break;
 948   default:
 949     cout << "- Don't know how to print value of this type!";
 950     break;
 951   }
 952 }
 953
 954 void Interpreter::print(const Type *Ty, GenericValue V) {
 955   cout << Ty << " ";
 956   printValue(Ty, V);
 957 }
 958
 959 void Interpreter::print(const string &Name) {
 960   Value *PickedVal = ChooseOneOption(Name, LookupMatchingNames(Name));
 961   if (!PickedVal) return;
 962
 963   if (const Method *M = dyn_cast<const Method>(PickedVal)) {
 964     cout << M;  // Print the method
 965   } else {      // Otherwise there should be an annotation for the slot#
 966     print(PickedVal->getType(),
 967           getOperandValue(PickedVal, ECStack[CurFrame]));
 968     cout << endl;
 969   }
 970
 971 }
 972
 973 void Interpreter::infoValue(const string &Name) {
 974   Value *PickedVal = ChooseOneOption(Name, LookupMatchingNames(Name));
 975   if (!PickedVal) return;
 976
 977   cout << "Value: ";
 978   print(PickedVal->getType(),
 979         getOperandValue(PickedVal, ECStack[CurFrame]));
 980   cout << endl;
 981   printOperandInfo(PickedVal, ECStack[CurFrame]);
 982 }
 983
 984 void Interpreter::list() {
 985   if (ECStack.empty())
 986     cout << "Error: No program executing!\n";
 987   else
 988     cout << ECStack[CurFrame].CurMethod;   // Just print the method out...
 989 }
 990
 991 void Interpreter::printStackTrace() {
 992   if (ECStack.empty()) cout << "No program executing!\n";
 993
 994   for (unsigned i = 0; i < ECStack.size(); ++i) {
 995     cout << (((int)i == CurFrame) ? '>' : '-');
 996     cout << "#" << i << ". " << ECStack[i].CurMethod->getType() << " \""
 997          << ECStack[i].CurMethod->getName() << "\"(";
 998     // TODO: Print Args
 999     cout << ")" << endl;
1000     cout << *ECStack[i].CurInst;
1001   }
1002 }