lib/ExecutionEngine/Interpreter/Execution.cpp

   1 //===-- Execution.cpp - Implement code to simulate the program ------------===//
   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 contains the actual instruction interpreter.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "interpreter"
  15 #include "Interpreter.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/CodeGen/IntrinsicLowering.h"
  20 #include "llvm/Support/GetElementPtrTypeIterator.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/Support/Debug.h"
  23 #include <cmath>
  24 using namespace llvm;
  25
  26 STATISTIC(NumDynamicInsts, "Number of dynamic instructions executed");
  27 static Interpreter *TheEE = 0;
  28
  29
  30 //===----------------------------------------------------------------------===//
  31 //                     Value Manipulation code
  32 //===----------------------------------------------------------------------===//
  33
  34 static GenericValue executeAddInst(GenericValue Src1, GenericValue Src2,
  35                                    const Type *Ty);
  36 static GenericValue executeSubInst(GenericValue Src1, GenericValue Src2,
  37                                    const Type *Ty);
  38 static GenericValue executeMulInst(GenericValue Src1, GenericValue Src2,
  39                                    const Type *Ty);
  40 static GenericValue executeUDivInst(GenericValue Src1, GenericValue Src2,
  41                                     const Type *Ty);
  42 static GenericValue executeSDivInst(GenericValue Src1, GenericValue Src2,
  43                                     const Type *Ty);
  44 static GenericValue executeFDivInst(GenericValue Src1, GenericValue Src2,
  45                                     const Type *Ty);
  46 static GenericValue executeURemInst(GenericValue Src1, GenericValue Src2,
  47                                     const Type *Ty);
  48 static GenericValue executeSRemInst(GenericValue Src1, GenericValue Src2,
  49                                     const Type *Ty);
  50 static GenericValue executeFRemInst(GenericValue Src1, GenericValue Src2,
  51                                     const Type *Ty);
  52 static GenericValue executeAndInst(GenericValue Src1, GenericValue Src2,
  53                                    const Type *Ty);
  54 static GenericValue executeOrInst(GenericValue Src1, GenericValue Src2,
  55                                    const Type *Ty);
  56 static GenericValue executeXorInst(GenericValue Src1, GenericValue Src2,
  57                                    const Type *Ty);
  58 static GenericValue executeCmpInst(unsigned predicate, GenericValue Src1,
  59                                    GenericValue Src2, const Type *Ty);
  60 static GenericValue executeShlInst(GenericValue Src1, GenericValue Src2,
  61                                    const Type *Ty);
  62 static GenericValue executeLShrInst(GenericValue Src1, GenericValue Src2,
  63                                     const Type *Ty);
  64 static GenericValue executeAShrInst(GenericValue Src1, GenericValue Src2,
  65                                     const Type *Ty);
  66 static GenericValue executeSelectInst(GenericValue Src1, GenericValue Src2,
  67                                       GenericValue Src3);
  68
  69 GenericValue Interpreter::getConstantExprValue (ConstantExpr *CE,
  70                                                 ExecutionContext &SF) {
  71   switch (CE->getOpcode()) {
  72   case Instruction::Trunc:
  73   case Instruction::ZExt:
  74   case Instruction::SExt:
  75   case Instruction::FPTrunc:
  76   case Instruction::FPExt:
  77   case Instruction::UIToFP:
  78   case Instruction::SIToFP:
  79   case Instruction::FPToUI:
  80   case Instruction::FPToSI:
  81   case Instruction::PtrToInt:
  82   case Instruction::IntToPtr:
  83   case Instruction::BitCast:
  84     return executeCastOperation(Instruction::CastOps(CE->getOpcode()),
  85                                 CE->getOperand(0), CE->getType(), SF);
  86   case Instruction::GetElementPtr:
  87     return executeGEPOperation(CE->getOperand(0), gep_type_begin(CE),
  88                                gep_type_end(CE), SF);
  89   case Instruction::Add:
  90     return executeAddInst(getOperandValue(CE->getOperand(0), SF),
  91                           getOperandValue(CE->getOperand(1), SF),
  92                           CE->getOperand(0)->getType());
  93   case Instruction::Sub:
  94     return executeSubInst(getOperandValue(CE->getOperand(0), SF),
  95                           getOperandValue(CE->getOperand(1), SF),
  96                           CE->getOperand(0)->getType());
  97   case Instruction::Mul:
  98     return executeMulInst(getOperandValue(CE->getOperand(0), SF),
  99                           getOperandValue(CE->getOperand(1), SF),
 100                           CE->getOperand(0)->getType());
 101   case Instruction::SDiv:
 102     return executeSDivInst(getOperandValue(CE->getOperand(0), SF),
 103                            getOperandValue(CE->getOperand(1), SF),
 104                            CE->getOperand(0)->getType());
 105   case Instruction::UDiv:
 106     return executeUDivInst(getOperandValue(CE->getOperand(0), SF),
 107                            getOperandValue(CE->getOperand(1), SF),
 108                            CE->getOperand(0)->getType());
 109   case Instruction::FDiv:
 110     return executeFDivInst(getOperandValue(CE->getOperand(0), SF),
 111                            getOperandValue(CE->getOperand(1), SF),
 112                            CE->getOperand(0)->getType());
 113   case Instruction::URem:
 114     return executeURemInst(getOperandValue(CE->getOperand(0), SF),
 115                           getOperandValue(CE->getOperand(1), SF),
 116                           CE->getOperand(0)->getType());
 117   case Instruction::SRem:
 118     return executeSRemInst(getOperandValue(CE->getOperand(0), SF),
 119                           getOperandValue(CE->getOperand(1), SF),
 120                           CE->getOperand(0)->getType());
 121   case Instruction::FRem:
 122     return executeFRemInst(getOperandValue(CE->getOperand(0), SF),
 123                            getOperandValue(CE->getOperand(1), SF),
 124                            CE->getOperand(0)->getType());
 125   case Instruction::And:
 126     return executeAndInst(getOperandValue(CE->getOperand(0), SF),
 127                           getOperandValue(CE->getOperand(1), SF),
 128                           CE->getOperand(0)->getType());
 129   case Instruction::Or:
 130     return executeOrInst(getOperandValue(CE->getOperand(0), SF),
 131                          getOperandValue(CE->getOperand(1), SF),
 132                          CE->getOperand(0)->getType());
 133   case Instruction::Xor:
 134     return executeXorInst(getOperandValue(CE->getOperand(0), SF),
 135                           getOperandValue(CE->getOperand(1), SF),
 136                           CE->getOperand(0)->getType());
 137   case Instruction::FCmp:
 138   case Instruction::ICmp:
 139     return executeCmpInst(CE->getPredicate(),
 140                           getOperandValue(CE->getOperand(0), SF),
 141                           getOperandValue(CE->getOperand(1), SF),
 142                           CE->getOperand(0)->getType());
 143   case Instruction::Shl:
 144     return executeShlInst(getOperandValue(CE->getOperand(0), SF),
 145                           getOperandValue(CE->getOperand(1), SF),
 146                           CE->getOperand(0)->getType());
 147   case Instruction::LShr:
 148     return executeLShrInst(getOperandValue(CE->getOperand(0), SF),
 149                            getOperandValue(CE->getOperand(1), SF),
 150                            CE->getOperand(0)->getType());
 151   case Instruction::AShr:
 152     return executeAShrInst(getOperandValue(CE->getOperand(0), SF),
 153                            getOperandValue(CE->getOperand(1), SF),
 154                            CE->getOperand(0)->getType());
 155   case Instruction::Select:
 156     return executeSelectInst(getOperandValue(CE->getOperand(0), SF),
 157                              getOperandValue(CE->getOperand(1), SF),
 158                              getOperandValue(CE->getOperand(2), SF));
 159   default:
 160     cerr << "Unhandled ConstantExpr: " << *CE << "\n";
 161     abort();
 162     return GenericValue();
 163   }
 164 }
 165
 166 GenericValue Interpreter::getOperandValue(Value *V, ExecutionContext &SF) {
 167   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
 168     return getConstantExprValue(CE, SF);
 169   } else if (Constant *CPV = dyn_cast<Constant>(V)) {
 170     return getConstantValue(CPV);
 171   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
 172     return PTOGV(getPointerToGlobal(GV));
 173   } else {
 174     return SF.Values[V];
 175   }
 176 }
 177
 178 static void SetValue(Value *V, GenericValue Val, ExecutionContext &SF) {
 179   SF.Values[V] = Val;
 180 }
 181
 182 void Interpreter::initializeExecutionEngine() {
 183   TheEE = this;
 184 }
 185
 186 //===----------------------------------------------------------------------===//
 187 //                    Binary Instruction Implementations
 188 //===----------------------------------------------------------------------===//
 189
 190 #define IMPLEMENT_BINARY_OPERATOR(OP, TY) \
 191    case Type::TY##TyID: Dest.TY##Val = Src1.TY##Val OP Src2.TY##Val; break
 192
 193 static GenericValue executeAddInst(GenericValue Src1, GenericValue Src2,
 194                                    const Type *Ty) {
 195   GenericValue Dest;
 196   switch (Ty->getTypeID()) {
 197     IMPLEMENT_BINARY_OPERATOR(+, Int8);
 198     IMPLEMENT_BINARY_OPERATOR(+, Int16);
 199     IMPLEMENT_BINARY_OPERATOR(+, Int32);
 200     IMPLEMENT_BINARY_OPERATOR(+, Int64);
 201     IMPLEMENT_BINARY_OPERATOR(+, Float);
 202     IMPLEMENT_BINARY_OPERATOR(+, Double);
 203   default:
 204     cerr << "Unhandled type for Add instruction: " << *Ty << "\n";
 205     abort();
 206   }
 207   return Dest;
 208 }
 209
 210 static GenericValue executeSubInst(GenericValue Src1, GenericValue Src2,
 211                                    const Type *Ty) {
 212   GenericValue Dest;
 213   switch (Ty->getTypeID()) {
 214     IMPLEMENT_BINARY_OPERATOR(-, Int8);
 215     IMPLEMENT_BINARY_OPERATOR(-, Int16);
 216     IMPLEMENT_BINARY_OPERATOR(-, Int32);
 217     IMPLEMENT_BINARY_OPERATOR(-, Int64);
 218     IMPLEMENT_BINARY_OPERATOR(-, Float);
 219     IMPLEMENT_BINARY_OPERATOR(-, Double);
 220   default:
 221     cerr << "Unhandled type for Sub instruction: " << *Ty << "\n";
 222     abort();
 223   }
 224   return Dest;
 225 }
 226
 227 static GenericValue executeMulInst(GenericValue Src1, GenericValue Src2,
 228                                    const Type *Ty) {
 229   GenericValue Dest;
 230   switch (Ty->getTypeID()) {
 231     IMPLEMENT_BINARY_OPERATOR(*, Int8);
 232     IMPLEMENT_BINARY_OPERATOR(*, Int16);
 233     IMPLEMENT_BINARY_OPERATOR(*, Int32);
 234     IMPLEMENT_BINARY_OPERATOR(*, Int64);
 235     IMPLEMENT_BINARY_OPERATOR(*, Float);
 236     IMPLEMENT_BINARY_OPERATOR(*, Double);
 237   default:
 238     cerr << "Unhandled type for Mul instruction: " << *Ty << "\n";
 239     abort();
 240   }
 241   return Dest;
 242 }
 243
 244 #define IMPLEMENT_SIGNLESS_BINOP(OP, TY, CAST) \
 245    case Type::TY##TyID: Dest.TY##Val = \
 246     ((CAST)Src1.TY##Val) OP ((CAST)Src2.TY##Val); break
 247
 248 static GenericValue executeUDivInst(GenericValue Src1, GenericValue Src2,
 249                                    const Type *Ty) {
 250   GenericValue Dest;
 251   switch (Ty->getTypeID()) {
 252     IMPLEMENT_SIGNLESS_BINOP(/, Int8,  uint8_t);
 253     IMPLEMENT_SIGNLESS_BINOP(/, Int16, uint16_t);
 254     IMPLEMENT_SIGNLESS_BINOP(/, Int32, uint32_t);
 255     IMPLEMENT_SIGNLESS_BINOP(/, Int64, uint64_t);
 256   default:
 257     cerr << "Unhandled type for UDiv instruction: " << *Ty << "\n";
 258     abort();
 259   }
 260   return Dest;
 261 }
 262
 263 static GenericValue executeSDivInst(GenericValue Src1, GenericValue Src2,
 264                                    const Type *Ty) {
 265   GenericValue Dest;
 266   switch (Ty->getTypeID()) {
 267     IMPLEMENT_SIGNLESS_BINOP(/, Int8,  int8_t);
 268     IMPLEMENT_SIGNLESS_BINOP(/, Int16, int16_t);
 269     IMPLEMENT_SIGNLESS_BINOP(/, Int32, int32_t);
 270     IMPLEMENT_SIGNLESS_BINOP(/, Int64, int64_t);
 271   default:
 272     cerr << "Unhandled type for SDiv instruction: " << *Ty << "\n";
 273     abort();
 274   }
 275   return Dest;
 276 }
 277
 278 static GenericValue executeFDivInst(GenericValue Src1, GenericValue Src2,
 279                                    const Type *Ty) {
 280   GenericValue Dest;
 281   switch (Ty->getTypeID()) {
 282     IMPLEMENT_BINARY_OPERATOR(/, Float);
 283     IMPLEMENT_BINARY_OPERATOR(/, Double);
 284   default:
 285     cerr << "Unhandled type for Div instruction: " << *Ty << "\n";
 286     abort();
 287   }
 288   return Dest;
 289 }
 290
 291 static GenericValue executeURemInst(GenericValue Src1, GenericValue Src2,
 292                                    const Type *Ty) {
 293   GenericValue Dest;
 294   switch (Ty->getTypeID()) {
 295     IMPLEMENT_SIGNLESS_BINOP(%, Int8,  uint8_t);
 296     IMPLEMENT_SIGNLESS_BINOP(%, Int16, uint16_t);
 297     IMPLEMENT_SIGNLESS_BINOP(%, Int32, uint32_t);
 298     IMPLEMENT_SIGNLESS_BINOP(%, Int64, uint64_t );
 299   default:
 300     cerr << "Unhandled type for URem instruction: " << *Ty << "\n";
 301     abort();
 302   }
 303   return Dest;
 304 }
 305
 306 static GenericValue executeSRemInst(GenericValue Src1, GenericValue Src2,
 307                                    const Type *Ty) {
 308   GenericValue Dest;
 309   switch (Ty->getTypeID()) {
 310     IMPLEMENT_SIGNLESS_BINOP(%, Int8,  int8_t);
 311     IMPLEMENT_SIGNLESS_BINOP(%, Int16, int16_t);
 312     IMPLEMENT_SIGNLESS_BINOP(%, Int32, int32_t);
 313     IMPLEMENT_SIGNLESS_BINOP(%, Int64, int64_t);
 314   default:
 315     cerr << "Unhandled type for Rem instruction: " << *Ty << "\n";
 316     abort();
 317   }
 318   return Dest;
 319 }
 320
 321 static GenericValue executeFRemInst(GenericValue Src1, GenericValue Src2,
 322                                    const Type *Ty) {
 323   GenericValue Dest;
 324   switch (Ty->getTypeID()) {
 325   case Type::FloatTyID:
 326     Dest.FloatVal = fmod(Src1.FloatVal, Src2.FloatVal);
 327     break;
 328   case Type::DoubleTyID:
 329     Dest.DoubleVal = fmod(Src1.DoubleVal, Src2.DoubleVal);
 330     break;
 331   default:
 332     cerr << "Unhandled type for Rem instruction: " << *Ty << "\n";
 333     abort();
 334   }
 335   return Dest;
 336 }
 337
 338 static GenericValue executeAndInst(GenericValue Src1, GenericValue Src2,
 339                                    const Type *Ty) {
 340   GenericValue Dest;
 341   switch (Ty->getTypeID()) {
 342     IMPLEMENT_BINARY_OPERATOR(&, Int1);
 343     IMPLEMENT_BINARY_OPERATOR(&, Int8);
 344     IMPLEMENT_BINARY_OPERATOR(&, Int16);
 345     IMPLEMENT_BINARY_OPERATOR(&, Int32);
 346     IMPLEMENT_BINARY_OPERATOR(&, Int64);
 347   default:
 348     cerr << "Unhandled type for And instruction: " << *Ty << "\n";
 349     abort();
 350   }
 351   return Dest;
 352 }
 353
 354 static GenericValue executeOrInst(GenericValue Src1, GenericValue Src2,
 355                                   const Type *Ty) {
 356   GenericValue Dest;
 357   switch (Ty->getTypeID()) {
 358     IMPLEMENT_BINARY_OPERATOR(|, Int1);
 359     IMPLEMENT_BINARY_OPERATOR(|, Int8);
 360     IMPLEMENT_BINARY_OPERATOR(|, Int16);
 361     IMPLEMENT_BINARY_OPERATOR(|, Int32);
 362     IMPLEMENT_BINARY_OPERATOR(|, Int64);
 363   default:
 364     cerr << "Unhandled type for Or instruction: " << *Ty << "\n";
 365     abort();
 366   }
 367   return Dest;
 368 }
 369
 370 static GenericValue executeXorInst(GenericValue Src1, GenericValue Src2,
 371                                    const Type *Ty) {
 372   GenericValue Dest;
 373   switch (Ty->getTypeID()) {
 374     IMPLEMENT_BINARY_OPERATOR(^, Int1);
 375     IMPLEMENT_BINARY_OPERATOR(^, Int8);
 376     IMPLEMENT_BINARY_OPERATOR(^, Int16);
 377     IMPLEMENT_BINARY_OPERATOR(^, Int32);
 378     IMPLEMENT_BINARY_OPERATOR(^, Int64);
 379   default:
 380     cerr << "Unhandled type for Xor instruction: " << *Ty << "\n";
 381     abort();
 382   }
 383   return Dest;
 384 }
 385
 386 #define IMPLEMENT_ICMP(OP, TY, CAST) \
 387    case Type::TY##TyID: Dest.Int1Val = \
 388      ((CAST)Src1.TY##Val) OP ((CAST)Src2.TY##Val); break
 389
 390 // Handle pointers specially because they must be compared with only as much
 391 // width as the host has.  We _do not_ want to be comparing 64 bit values when
 392 // running on a 32-bit target, otherwise the upper 32 bits might mess up
 393 // comparisons if they contain garbage.
 394 #define IMPLEMENT_POINTERCMP(OP) \
 395    case Type::PointerTyID: \
 396         Dest.Int1Val = (void*)(intptr_t)Src1.PointerVal OP \
 397                        (void*)(intptr_t)Src2.PointerVal; break
 398
 399 static GenericValue executeICMP_EQ(GenericValue Src1, GenericValue Src2,
 400                                    const Type *Ty) {
 401   GenericValue Dest;
 402   switch (Ty->getTypeID()) {
 403     IMPLEMENT_ICMP(==, Int8,  uint8_t);
 404     IMPLEMENT_ICMP(==, Int16, uint16_t);
 405     IMPLEMENT_ICMP(==, Int32, uint32_t);
 406     IMPLEMENT_ICMP(==, Int64, uint64_t);
 407     IMPLEMENT_POINTERCMP(==);
 408   default:
 409     cerr << "Unhandled type for ICMP_EQ predicate: " << *Ty << "\n";
 410     abort();
 411   }
 412   return Dest;
 413 }
 414
 415 static GenericValue executeICMP_NE(GenericValue Src1, GenericValue Src2,
 416                                    const Type *Ty) {
 417   GenericValue Dest;
 418   switch (Ty->getTypeID()) {
 419     IMPLEMENT_ICMP(!=, Int8,  uint8_t);
 420     IMPLEMENT_ICMP(!=, Int16, uint16_t);
 421     IMPLEMENT_ICMP(!=, Int32, uint32_t);
 422     IMPLEMENT_ICMP(!=, Int64, uint64_t);
 423     IMPLEMENT_POINTERCMP(!=);
 424   default:
 425     cerr << "Unhandled type for ICMP_NE predicate: " << *Ty << "\n";
 426     abort();
 427   }
 428   return Dest;
 429 }
 430
 431 static GenericValue executeICMP_ULT(GenericValue Src1, GenericValue Src2,
 432                                     const Type *Ty) {
 433   GenericValue Dest;
 434   switch (Ty->getTypeID()) {
 435     IMPLEMENT_ICMP(<, Int8,  uint8_t);
 436     IMPLEMENT_ICMP(<, Int16, uint16_t);
 437     IMPLEMENT_ICMP(<, Int32, uint32_t);
 438     IMPLEMENT_ICMP(<, Int64, uint64_t);
 439     IMPLEMENT_POINTERCMP(<);
 440   default:
 441     cerr << "Unhandled type for ICMP_ULT predicate: " << *Ty << "\n";
 442     abort();
 443   }
 444   return Dest;
 445 }
 446
 447 static GenericValue executeICMP_SLT(GenericValue Src1, GenericValue Src2,
 448                                     const Type *Ty) {
 449   GenericValue Dest;
 450   switch (Ty->getTypeID()) {
 451     IMPLEMENT_ICMP(<, Int8,  int8_t);
 452     IMPLEMENT_ICMP(<, Int16, int16_t);
 453     IMPLEMENT_ICMP(<, Int32, int32_t);
 454     IMPLEMENT_ICMP(<, Int64, int64_t);
 455     IMPLEMENT_POINTERCMP(<);
 456   default:
 457     cerr << "Unhandled type for ICMP_SLT predicate: " << *Ty << "\n";
 458     abort();
 459   }
 460   return Dest;
 461 }
 462
 463 static GenericValue executeICMP_UGT(GenericValue Src1, GenericValue Src2,
 464                                     const Type *Ty) {
 465   GenericValue Dest;
 466   switch (Ty->getTypeID()) {
 467     IMPLEMENT_ICMP(>, Int8,  uint8_t);
 468     IMPLEMENT_ICMP(>, Int16, uint16_t);
 469     IMPLEMENT_ICMP(>, Int32, uint32_t);
 470     IMPLEMENT_ICMP(>, Int64, uint64_t);
 471     IMPLEMENT_POINTERCMP(>);
 472   default:
 473     cerr << "Unhandled type for ICMP_UGT predicate: " << *Ty << "\n";
 474     abort();
 475   }
 476   return Dest;
 477 }
 478
 479 static GenericValue executeICMP_SGT(GenericValue Src1, GenericValue Src2,
 480                                     const Type *Ty) {
 481   GenericValue Dest;
 482   switch (Ty->getTypeID()) {
 483     IMPLEMENT_ICMP(>, Int8,  int8_t);
 484     IMPLEMENT_ICMP(>, Int16, int16_t);
 485     IMPLEMENT_ICMP(>, Int32, int32_t);
 486     IMPLEMENT_ICMP(>, Int64, int64_t);
 487     IMPLEMENT_POINTERCMP(>);
 488   default:
 489     cerr << "Unhandled type for ICMP_SGT predicate: " << *Ty << "\n";
 490     abort();
 491   }
 492   return Dest;
 493 }
 494
 495 static GenericValue executeICMP_ULE(GenericValue Src1, GenericValue Src2,
 496                                     const Type *Ty) {
 497   GenericValue Dest;
 498   switch (Ty->getTypeID()) {
 499     IMPLEMENT_ICMP(<=, Int8,  uint8_t);
 500     IMPLEMENT_ICMP(<=, Int16, uint16_t);
 501     IMPLEMENT_ICMP(<=, Int32, uint32_t);
 502     IMPLEMENT_ICMP(<=, Int64, uint64_t);
 503     IMPLEMENT_POINTERCMP(<=);
 504   default:
 505     cerr << "Unhandled type for ICMP_ULE predicate: " << *Ty << "\n";
 506     abort();
 507   }
 508   return Dest;
 509 }
 510
 511 static GenericValue executeICMP_SLE(GenericValue Src1, GenericValue Src2,
 512                                     const Type *Ty) {
 513   GenericValue Dest;
 514   switch (Ty->getTypeID()) {
 515     IMPLEMENT_ICMP(<=, Int8,  int8_t);
 516     IMPLEMENT_ICMP(<=, Int16, int16_t);
 517     IMPLEMENT_ICMP(<=, Int32, int32_t);
 518     IMPLEMENT_ICMP(<=, Int64, int64_t);
 519     IMPLEMENT_POINTERCMP(<=);
 520   default:
 521     cerr << "Unhandled type for ICMP_SLE predicate: " << *Ty << "\n";
 522     abort();
 523   }
 524   return Dest;
 525 }
 526
 527 static GenericValue executeICMP_UGE(GenericValue Src1, GenericValue Src2,
 528                                     const Type *Ty) {
 529   GenericValue Dest;
 530   switch (Ty->getTypeID()) {
 531     IMPLEMENT_ICMP(>=, Int8,  uint8_t);
 532     IMPLEMENT_ICMP(>=, Int16, uint16_t);
 533     IMPLEMENT_ICMP(>=, Int32, uint32_t);
 534     IMPLEMENT_ICMP(>=, Int64, uint64_t);
 535     IMPLEMENT_POINTERCMP(>=);
 536   default:
 537     cerr << "Unhandled type for ICMP_UGE predicate: " << *Ty << "\n";
 538     abort();
 539   }
 540   return Dest;
 541 }
 542
 543 static GenericValue executeICMP_SGE(GenericValue Src1, GenericValue Src2,
 544                                     const Type *Ty) {
 545   GenericValue Dest;
 546   switch (Ty->getTypeID()) {
 547     IMPLEMENT_ICMP(>=, Int8,  int8_t);
 548     IMPLEMENT_ICMP(>=, Int16, int16_t);
 549     IMPLEMENT_ICMP(>=, Int32, int32_t);
 550     IMPLEMENT_ICMP(>=, Int64, int64_t);
 551     IMPLEMENT_POINTERCMP(>=);
 552   default:
 553     cerr << "Unhandled type for ICMP_SGE predicate: " << *Ty << "\n";
 554     abort();
 555   }
 556   return Dest;
 557 }
 558
 559 void Interpreter::visitICmpInst(ICmpInst &I) {
 560   ExecutionContext &SF = ECStack.back();
 561   const Type *Ty    = I.getOperand(0)->getType();
 562   GenericValue Src1 = getOperandValue(I.getOperand(0), SF);
 563   GenericValue Src2 = getOperandValue(I.getOperand(1), SF);
 564   GenericValue R;   // Result
 565
 566   switch (I.getPredicate()) {
 567   case ICmpInst::ICMP_EQ:  R = executeICMP_EQ(Src1, Src2, Ty);  break;
 568   case ICmpInst::ICMP_NE:  R = executeICMP_NE(Src1, Src2, Ty);  break;
 569   case ICmpInst::ICMP_ULT: R = executeICMP_ULT(Src1, Src2, Ty); break;
 570   case ICmpInst::ICMP_SLT: R = executeICMP_SLT(Src1, Src2, Ty); break;
 571   case ICmpInst::ICMP_UGT: R = executeICMP_UGT(Src1, Src2, Ty); break;
 572   case ICmpInst::ICMP_SGT: R = executeICMP_SGT(Src1, Src2, Ty); break;
 573   case ICmpInst::ICMP_ULE: R = executeICMP_ULE(Src1, Src2, Ty); break;
 574   case ICmpInst::ICMP_SLE: R = executeICMP_SLE(Src1, Src2, Ty); break;
 575   case ICmpInst::ICMP_UGE: R = executeICMP_UGE(Src1, Src2, Ty); break;
 576   case ICmpInst::ICMP_SGE: R = executeICMP_SGE(Src1, Src2, Ty); break;
 577   default:
 578     cerr << "Don't know how to handle this ICmp predicate!\n-->" << I;
 579     abort();
 580   }
 581
 582   SetValue(&I, R, SF);
 583 }
 584
 585 #define IMPLEMENT_FCMP(OP, TY) \
 586    case Type::TY##TyID: Dest.Int1Val = Src1.TY##Val OP Src2.TY##Val; break
 587
 588 static GenericValue executeFCMP_EQ(GenericValue Src1, GenericValue Src2,
 589                                    const Type *Ty) {
 590   GenericValue Dest;
 591   switch (Ty->getTypeID()) {
 592     IMPLEMENT_FCMP(==, Float);
 593     IMPLEMENT_FCMP(==, Double);
 594   default:
 595     cerr << "Unhandled type for SetEQ instruction: " << *Ty << "\n";
 596     abort();
 597   }
 598   return Dest;
 599 }
 600
 601 static GenericValue executeFCMP_NE(GenericValue Src1, GenericValue Src2,
 602                                    const Type *Ty) {
 603   GenericValue Dest;
 604   switch (Ty->getTypeID()) {
 605     IMPLEMENT_FCMP(!=, Float);
 606     IMPLEMENT_FCMP(!=, Double);
 607
 608   default:
 609     cerr << "Unhandled type for SetNE instruction: " << *Ty << "\n";
 610     abort();
 611   }
 612   return Dest;
 613 }
 614
 615 static GenericValue executeFCMP_LE(GenericValue Src1, GenericValue Src2,
 616                                    const Type *Ty) {
 617   GenericValue Dest;
 618   switch (Ty->getTypeID()) {
 619     IMPLEMENT_FCMP(<=, Float);
 620     IMPLEMENT_FCMP(<=, Double);
 621   default:
 622     cerr << "Unhandled type for SetLE instruction: " << *Ty << "\n";
 623     abort();
 624   }
 625   return Dest;
 626 }
 627
 628 static GenericValue executeFCMP_GE(GenericValue Src1, GenericValue Src2,
 629                                    const Type *Ty) {
 630   GenericValue Dest;
 631   switch (Ty->getTypeID()) {
 632     IMPLEMENT_FCMP(>=, Float);
 633     IMPLEMENT_FCMP(>=, Double);
 634   default:
 635     cerr << "Unhandled type for SetGE instruction: " << *Ty << "\n";
 636     abort();
 637   }
 638   return Dest;
 639 }
 640
 641 static GenericValue executeFCMP_LT(GenericValue Src1, GenericValue Src2,
 642                                    const Type *Ty) {
 643   GenericValue Dest;
 644   switch (Ty->getTypeID()) {
 645     IMPLEMENT_FCMP(<, Float);
 646     IMPLEMENT_FCMP(<, Double);
 647   default:
 648     cerr << "Unhandled type for SetLT instruction: " << *Ty << "\n";
 649     abort();
 650   }
 651   return Dest;
 652 }
 653
 654 static GenericValue executeFCMP_GT(GenericValue Src1, GenericValue Src2,
 655                                      const Type *Ty) {
 656   GenericValue Dest;
 657   switch (Ty->getTypeID()) {
 658     IMPLEMENT_FCMP(>, Float);
 659     IMPLEMENT_FCMP(>, Double);
 660   default:
 661     cerr << "Unhandled type for SetGT instruction: " << *Ty << "\n";
 662     abort();
 663   }
 664   return Dest;
 665 }
 666
 667 void Interpreter::visitFCmpInst(FCmpInst &I) {
 668   ExecutionContext &SF = ECStack.back();
 669   const Type *Ty    = I.getOperand(0)->getType();
 670   GenericValue Src1 = getOperandValue(I.getOperand(0), SF);
 671   GenericValue Src2 = getOperandValue(I.getOperand(1), SF);
 672   GenericValue R;   // Result
 673
 674   switch (I.getPredicate()) {
 675   case FCmpInst::FCMP_FALSE: R.Int1Val = false;
 676   case FCmpInst::FCMP_ORD:   R = executeFCMP_EQ(Src1, Src2, Ty); break; ///???
 677   case FCmpInst::FCMP_UNO:   R = executeFCMP_NE(Src1, Src2, Ty); break; ///???
 678   case FCmpInst::FCMP_OEQ:
 679   case FCmpInst::FCMP_UEQ:   R = executeFCMP_EQ(Src1, Src2, Ty);  break;
 680   case FCmpInst::FCMP_ONE:
 681   case FCmpInst::FCMP_UNE:   R = executeFCMP_NE(Src1, Src2, Ty);  break;
 682   case FCmpInst::FCMP_OLT:
 683   case FCmpInst::FCMP_ULT:   R = executeFCMP_LT(Src1, Src2, Ty); break;
 684   case FCmpInst::FCMP_OGT:
 685   case FCmpInst::FCMP_UGT:   R = executeFCMP_GT(Src1, Src2, Ty); break;
 686   case FCmpInst::FCMP_OLE:
 687   case FCmpInst::FCMP_ULE:   R = executeFCMP_LE(Src1, Src2, Ty); break;
 688   case FCmpInst::FCMP_OGE:
 689   case FCmpInst::FCMP_UGE:   R = executeFCMP_GE(Src1, Src2, Ty); break;
 690   case FCmpInst::FCMP_TRUE:  R.Int1Val = true;
 691   default:
 692     cerr << "Don't know how to handle this FCmp predicate!\n-->" << I;
 693     abort();
 694   }
 695
 696   SetValue(&I, R, SF);
 697 }
 698
 699 static GenericValue executeCmpInst(unsigned predicate, GenericValue Src1,
 700                                    GenericValue Src2, const Type *Ty) {
 701   GenericValue Result;
 702   switch (predicate) {
 703   case ICmpInst::ICMP_EQ:    return executeICMP_EQ(Src1, Src2, Ty);
 704   case ICmpInst::ICMP_NE:    return executeICMP_NE(Src1, Src2, Ty);
 705   case ICmpInst::ICMP_UGT:   return executeICMP_UGT(Src1, Src2, Ty);
 706   case ICmpInst::ICMP_SGT:   return executeICMP_SGT(Src1, Src2, Ty);
 707   case ICmpInst::ICMP_ULT:   return executeICMP_ULT(Src1, Src2, Ty);
 708   case ICmpInst::ICMP_SLT:   return executeICMP_SLT(Src1, Src2, Ty);
 709   case ICmpInst::ICMP_UGE:   return executeICMP_UGE(Src1, Src2, Ty);
 710   case ICmpInst::ICMP_SGE:   return executeICMP_SGE(Src1, Src2, Ty);
 711   case ICmpInst::ICMP_ULE:   return executeICMP_ULE(Src1, Src2, Ty);
 712   case ICmpInst::ICMP_SLE:   return executeICMP_SLE(Src1, Src2, Ty);
 713   case FCmpInst::FCMP_ORD:   return executeFCMP_EQ(Src1, Src2, Ty); break;
 714   case FCmpInst::FCMP_UNO:   return executeFCMP_NE(Src1, Src2, Ty); break;
 715   case FCmpInst::FCMP_OEQ:
 716   case FCmpInst::FCMP_UEQ:   return executeFCMP_EQ(Src1, Src2, Ty);  break;
 717   case FCmpInst::FCMP_ONE:
 718   case FCmpInst::FCMP_UNE:   return executeFCMP_NE(Src1, Src2, Ty);  break;
 719   case FCmpInst::FCMP_OLT:
 720   case FCmpInst::FCMP_ULT:   return executeFCMP_LT(Src1, Src2, Ty); break;
 721   case FCmpInst::FCMP_OGT:
 722   case FCmpInst::FCMP_UGT:   return executeFCMP_GT(Src1, Src2, Ty); break;
 723   case FCmpInst::FCMP_OLE:
 724   case FCmpInst::FCMP_ULE:   return executeFCMP_LE(Src1, Src2, Ty); break;
 725   case FCmpInst::FCMP_OGE:
 726   case FCmpInst::FCMP_UGE:   return executeFCMP_GE(Src1, Src2, Ty); break;
 727   case FCmpInst::FCMP_FALSE: {
 728     GenericValue Result;
 729     Result.Int1Val = false;
 730     return Result;
 731   }
 732   case FCmpInst::FCMP_TRUE: {
 733     GenericValue Result;
 734     Result.Int1Val = true;
 735     return Result;
 736   }
 737   default:
 738     cerr << "Unhandled Cmp predicate\n";
 739     abort();
 740   }
 741 }
 742
 743 void Interpreter::visitBinaryOperator(BinaryOperator &I) {
 744   ExecutionContext &SF = ECStack.back();
 745   const Type *Ty    = I.getOperand(0)->getType();
 746   GenericValue Src1 = getOperandValue(I.getOperand(0), SF);
 747   GenericValue Src2 = getOperandValue(I.getOperand(1), SF);
 748   GenericValue R;   // Result
 749
 750   switch (I.getOpcode()) {
 751   case Instruction::Add:   R = executeAddInst  (Src1, Src2, Ty); break;
 752   case Instruction::Sub:   R = executeSubInst  (Src1, Src2, Ty); break;
 753   case Instruction::Mul:   R = executeMulInst  (Src1, Src2, Ty); break;
 754   case Instruction::UDiv:  R = executeUDivInst (Src1, Src2, Ty); break;
 755   case Instruction::SDiv:  R = executeSDivInst (Src1, Src2, Ty); break;
 756   case Instruction::FDiv:  R = executeFDivInst (Src1, Src2, Ty); break;
 757   case Instruction::URem:  R = executeURemInst (Src1, Src2, Ty); break;
 758   case Instruction::SRem:  R = executeSRemInst (Src1, Src2, Ty); break;
 759   case Instruction::FRem:  R = executeFRemInst (Src1, Src2, Ty); break;
 760   case Instruction::And:   R = executeAndInst  (Src1, Src2, Ty); break;
 761   case Instruction::Or:    R = executeOrInst   (Src1, Src2, Ty); break;
 762   case Instruction::Xor:   R = executeXorInst  (Src1, Src2, Ty); break;
 763   default:
 764     cerr << "Don't know how to handle this binary operator!\n-->" << I;
 765     abort();
 766   }
 767
 768   SetValue(&I, R, SF);
 769 }
 770
 771 static GenericValue executeSelectInst(GenericValue Src1, GenericValue Src2,
 772                                       GenericValue Src3) {
 773   return Src1.Int1Val ? Src2 : Src3;
 774 }
 775
 776 void Interpreter::visitSelectInst(SelectInst &I) {
 777   ExecutionContext &SF = ECStack.back();
 778   GenericValue Src1 = getOperandValue(I.getOperand(0), SF);
 779   GenericValue Src2 = getOperandValue(I.getOperand(1), SF);
 780   GenericValue Src3 = getOperandValue(I.getOperand(2), SF);
 781   GenericValue R = executeSelectInst(Src1, Src2, Src3);
 782   SetValue(&I, R, SF);
 783 }
 784
 785
 786 //===----------------------------------------------------------------------===//
 787 //                     Terminator Instruction Implementations
 788 //===----------------------------------------------------------------------===//
 789
 790 void Interpreter::exitCalled(GenericValue GV) {
 791   // runAtExitHandlers() assumes there are no stack frames, but
 792   // if exit() was called, then it had a stack frame. Blow away
 793   // the stack before interpreting atexit handlers.
 794   ECStack.clear ();
 795   runAtExitHandlers ();
 796   exit (GV.Int32Val);
 797 }
 798
 799 /// Pop the last stack frame off of ECStack and then copy the result
 800 /// back into the result variable if we are not returning void. The
 801 /// result variable may be the ExitValue, or the Value of the calling
 802 /// CallInst if there was a previous stack frame. This method may
 803 /// invalidate any ECStack iterators you have. This method also takes
 804 /// care of switching to the normal destination BB, if we are returning
 805 /// from an invoke.
 806 ///
 807 void Interpreter::popStackAndReturnValueToCaller (const Type *RetTy,
 808                                                   GenericValue Result) {
 809   // Pop the current stack frame.
 810   ECStack.pop_back();
 811
 812   if (ECStack.empty()) {  // Finished main.  Put result into exit code...
 813     if (RetTy && RetTy->isIntegral()) {          // Nonvoid return type?
 814       ExitValue = Result;   // Capture the exit value of the program
 815     } else {
 816       memset(&ExitValue, 0, sizeof(ExitValue));
 817     }
 818   } else {
 819     // If we have a previous stack frame, and we have a previous call,
 820     // fill in the return value...
 821     ExecutionContext &CallingSF = ECStack.back();
 822     if (Instruction *I = CallingSF.Caller.getInstruction()) {
 823       if (CallingSF.Caller.getType() != Type::VoidTy)      // Save result...
 824         SetValue(I, Result, CallingSF);
 825       if (InvokeInst *II = dyn_cast<InvokeInst> (I))
 826         SwitchToNewBasicBlock (II->getNormalDest (), CallingSF);
 827       CallingSF.Caller = CallSite();          // We returned from the call...
 828     }
 829   }
 830 }
 831
 832 void Interpreter::visitReturnInst(ReturnInst &I) {
 833   ExecutionContext &SF = ECStack.back();
 834   const Type *RetTy = Type::VoidTy;
 835   GenericValue Result;
 836
 837   // Save away the return value... (if we are not 'ret void')
 838   if (I.getNumOperands()) {
 839     RetTy  = I.getReturnValue()->getType();
 840     Result = getOperandValue(I.getReturnValue(), SF);
 841   }
 842
 843   popStackAndReturnValueToCaller(RetTy, Result);
 844 }
 845
 846 void Interpreter::visitUnwindInst(UnwindInst &I) {
 847   // Unwind stack
 848   Instruction *Inst;
 849   do {
 850     ECStack.pop_back ();
 851     if (ECStack.empty ())
 852       abort ();
 853     Inst = ECStack.back ().Caller.getInstruction ();
 854   } while (!(Inst && isa<InvokeInst> (Inst)));
 855
 856   // Return from invoke
 857   ExecutionContext &InvokingSF = ECStack.back ();
 858   InvokingSF.Caller = CallSite ();
 859
 860   // Go to exceptional destination BB of invoke instruction
 861   SwitchToNewBasicBlock(cast<InvokeInst>(Inst)->getUnwindDest(), InvokingSF);
 862 }
 863
 864 void Interpreter::visitUnreachableInst(UnreachableInst &I) {
 865   cerr << "ERROR: Program executed an 'unreachable' instruction!\n";
 866   abort();
 867 }
 868
 869 void Interpreter::visitBranchInst(BranchInst &I) {
 870   ExecutionContext &SF = ECStack.back();
 871   BasicBlock *Dest;
 872
 873   Dest = I.getSuccessor(0);          // Uncond branches have a fixed dest...
 874   if (!I.isUnconditional()) {
 875     Value *Cond = I.getCondition();
 876     if (getOperandValue(Cond, SF).Int1Val == 0) // If false cond...
 877       Dest = I.getSuccessor(1);
 878   }
 879   SwitchToNewBasicBlock(Dest, SF);
 880 }
 881
 882 void Interpreter::visitSwitchInst(SwitchInst &I) {
 883   ExecutionContext &SF = ECStack.back();
 884   GenericValue CondVal = getOperandValue(I.getOperand(0), SF);
 885   const Type *ElTy = I.getOperand(0)->getType();
 886
 887   // Check to see if any of the cases match...
 888   BasicBlock *Dest = 0;
 889   for (unsigned i = 2, e = I.getNumOperands(); i != e; i += 2)
 890     if (executeICMP_EQ(CondVal,
 891                        getOperandValue(I.getOperand(i), SF), ElTy).Int1Val) {
 892       Dest = cast<BasicBlock>(I.getOperand(i+1));
 893       break;
 894     }
 895
 896   if (!Dest) Dest = I.getDefaultDest();   // No cases matched: use default
 897   SwitchToNewBasicBlock(Dest, SF);
 898 }
 899
 900 // SwitchToNewBasicBlock - This method is used to jump to a new basic block.
 901 // This function handles the actual updating of block and instruction iterators
 902 // as well as execution of all of the PHI nodes in the destination block.
 903 //
 904 // This method does this because all of the PHI nodes must be executed
 905 // atomically, reading their inputs before any of the results are updated.  Not
 906 // doing this can cause problems if the PHI nodes depend on other PHI nodes for
 907 // their inputs.  If the input PHI node is updated before it is read, incorrect
 908 // results can happen.  Thus we use a two phase approach.
 909 //
 910 void Interpreter::SwitchToNewBasicBlock(BasicBlock *Dest, ExecutionContext &SF){
 911   BasicBlock *PrevBB = SF.CurBB;      // Remember where we came from...
 912   SF.CurBB   = Dest;                  // Update CurBB to branch destination
 913   SF.CurInst = SF.CurBB->begin();     // Update new instruction ptr...
 914
 915   if (!isa<PHINode>(SF.CurInst)) return;  // Nothing fancy to do
 916
 917   // Loop over all of the PHI nodes in the current block, reading their inputs.
 918   std::vector<GenericValue> ResultValues;
 919
 920   for (; PHINode *PN = dyn_cast<PHINode>(SF.CurInst); ++SF.CurInst) {
 921     // Search for the value corresponding to this previous bb...
 922     int i = PN->getBasicBlockIndex(PrevBB);
 923     assert(i != -1 && "PHINode doesn't contain entry for predecessor??");
 924     Value *IncomingValue = PN->getIncomingValue(i);
 925
 926     // Save the incoming value for this PHI node...
 927     ResultValues.push_back(getOperandValue(IncomingValue, SF));
 928   }
 929
 930   // Now loop over all of the PHI nodes setting their values...
 931   SF.CurInst = SF.CurBB->begin();
 932   for (unsigned i = 0; isa<PHINode>(SF.CurInst); ++SF.CurInst, ++i) {
 933     PHINode *PN = cast<PHINode>(SF.CurInst);
 934     SetValue(PN, ResultValues[i], SF);
 935   }
 936 }
 937
 938 //===----------------------------------------------------------------------===//
 939 //                     Memory Instruction Implementations
 940 //===----------------------------------------------------------------------===//
 941
 942 void Interpreter::visitAllocationInst(AllocationInst &I) {
 943   ExecutionContext &SF = ECStack.back();
 944
 945   const Type *Ty = I.getType()->getElementType();  // Type to be allocated
 946
 947   // Get the number of elements being allocated by the array...
 948   unsigned NumElements = getOperandValue(I.getOperand(0), SF).Int32Val;
 949
 950   // Allocate enough memory to hold the type...
 951   void *Memory = malloc(NumElements * (size_t)TD.getTypeSize(Ty));
 952
 953   GenericValue Result = PTOGV(Memory);
 954   assert(Result.PointerVal != 0 && "Null pointer returned by malloc!");
 955   SetValue(&I, Result, SF);
 956
 957   if (I.getOpcode() == Instruction::Alloca)
 958     ECStack.back().Allocas.add(Memory);
 959 }
 960
 961 void Interpreter::visitFreeInst(FreeInst &I) {
 962   ExecutionContext &SF = ECStack.back();
 963   assert(isa<PointerType>(I.getOperand(0)->getType()) && "Freeing nonptr?");
 964   GenericValue Value = getOperandValue(I.getOperand(0), SF);
 965   // TODO: Check to make sure memory is allocated
 966   free(GVTOP(Value));   // Free memory
 967 }
 968
 969 // getElementOffset - The workhorse for getelementptr.
 970 //
 971 GenericValue Interpreter::executeGEPOperation(Value *Ptr, gep_type_iterator I,
 972                                               gep_type_iterator E,
 973                                               ExecutionContext &SF) {
 974   assert(isa<PointerType>(Ptr->getType()) &&
 975          "Cannot getElementOffset of a nonpointer type!");
 976
 977   PointerTy Total = 0;
 978
 979   for (; I != E; ++I) {
 980     if (const StructType *STy = dyn_cast<StructType>(*I)) {
 981       const StructLayout *SLO = TD.getStructLayout(STy);
 982
 983       const ConstantInt *CPU = cast<ConstantInt>(I.getOperand());
 984       unsigned Index = unsigned(CPU->getZExtValue());
 985
 986       Total += (PointerTy)SLO->MemberOffsets[Index];
 987     } else {
 988       const SequentialType *ST = cast<SequentialType>(*I);
 989       // Get the index number for the array... which must be long type...
 990       GenericValue IdxGV = getOperandValue(I.getOperand(), SF);
 991
 992       uint64_t Idx;
 993       switch (I.getOperand()->getType()->getTypeID()) {
 994       default: assert(0 && "Illegal getelementptr index for sequential type!");
 995       case Type::Int8TyID:  Idx = IdxGV.Int8Val; break;
 996       case Type::Int16TyID: Idx = IdxGV.Int16Val; break;
 997       case Type::Int32TyID: Idx = IdxGV.Int32Val; break;
 998       case Type::Int64TyID: Idx = IdxGV.Int64Val; break;
 999       }
1000       Total += PointerTy(TD.getTypeSize(ST->getElementType())*Idx);
1001     }
1002   }
1003
1004   GenericValue Result;
1005   Result.PointerVal = getOperandValue(Ptr, SF).PointerVal + Total;
1006   return Result;
1007 }
1008
1009 void Interpreter::visitGetElementPtrInst(GetElementPtrInst &I) {
1010   ExecutionContext &SF = ECStack.back();
1011   SetValue(&I, TheEE->executeGEPOperation(I.getPointerOperand(),
1012                                    gep_type_begin(I), gep_type_end(I), SF), SF);
1013 }
1014
1015 void Interpreter::visitLoadInst(LoadInst &I) {
1016   ExecutionContext &SF = ECStack.back();
1017   GenericValue SRC = getOperandValue(I.getPointerOperand(), SF);
1018   GenericValue *Ptr = (GenericValue*)GVTOP(SRC);
1019   GenericValue Result = LoadValueFromMemory(Ptr, I.getType());
1020   SetValue(&I, Result, SF);
1021 }
1022
1023 void Interpreter::visitStoreInst(StoreInst &I) {
1024   ExecutionContext &SF = ECStack.back();
1025   GenericValue Val = getOperandValue(I.getOperand(0), SF);
1026   GenericValue SRC = getOperandValue(I.getPointerOperand(), SF);
1027   StoreValueToMemory(Val, (GenericValue *)GVTOP(SRC),
1028                      I.getOperand(0)->getType());
1029 }
1030
1031 //===----------------------------------------------------------------------===//
1032 //                 Miscellaneous Instruction Implementations
1033 //===----------------------------------------------------------------------===//
1034
1035 void Interpreter::visitCallSite(CallSite CS) {
1036   ExecutionContext &SF = ECStack.back();
1037
1038   // Check to see if this is an intrinsic function call...
1039   if (Function *F = CS.getCalledFunction())
1040    if (F->isExternal ())
1041     switch (F->getIntrinsicID()) {
1042     case Intrinsic::not_intrinsic:
1043       break;
1044     case Intrinsic::vastart: { // va_start
1045       GenericValue ArgIndex;
1046       ArgIndex.UIntPairVal.first = ECStack.size() - 1;
1047       ArgIndex.UIntPairVal.second = 0;
1048       SetValue(CS.getInstruction(), ArgIndex, SF);
1049       return;
1050     }
1051     case Intrinsic::vaend:    // va_end is a noop for the interpreter
1052       return;
1053     case Intrinsic::vacopy:   // va_copy: dest = src
1054       SetValue(CS.getInstruction(), getOperandValue(*CS.arg_begin(), SF), SF);
1055       return;
1056     default:
1057       // If it is an unknown intrinsic function, use the intrinsic lowering
1058       // class to transform it into hopefully tasty LLVM code.
1059       //
1060       Instruction *Prev = CS.getInstruction()->getPrev();
1061       BasicBlock *Parent = CS.getInstruction()->getParent();
1062       IL->LowerIntrinsicCall(cast<CallInst>(CS.getInstruction()));
1063
1064       // Restore the CurInst pointer to the first instruction newly inserted, if
1065       // any.
1066       if (!Prev) {
1067         SF.CurInst = Parent->begin();
1068       } else {
1069         SF.CurInst = Prev;
1070         ++SF.CurInst;
1071       }
1072       return;
1073     }
1074
1075   SF.Caller = CS;
1076   std::vector<GenericValue> ArgVals;
1077   const unsigned NumArgs = SF.Caller.arg_size();
1078   ArgVals.reserve(NumArgs);
1079   for (CallSite::arg_iterator i = SF.Caller.arg_begin(),
1080          e = SF.Caller.arg_end(); i != e; ++i) {
1081     Value *V = *i;
1082     ArgVals.push_back(getOperandValue(V, SF));
1083     // Promote all integral types whose size is < sizeof(int) into ints.  We do
1084     // this by zero or sign extending the value as appropriate according to the
1085     // source type.
1086     const Type *Ty = V->getType();
1087     if (Ty->isIntegral() && Ty->getPrimitiveSize() < 4) {
1088       if (Ty == Type::Int16Ty)
1089         ArgVals.back().Int32Val = ArgVals.back().Int16Val;
1090       else if (Ty == Type::Int8Ty)
1091         ArgVals.back().Int32Val = ArgVals.back().Int8Val;
1092       else if (Ty == Type::Int1Ty)
1093         ArgVals.back().Int32Val = ArgVals.back().Int1Val;
1094       else
1095         assert(0 && "Unknown type!");
1096     }
1097   }
1098
1099   // To handle indirect calls, we must get the pointer value from the argument
1100   // and treat it as a function pointer.
1101   GenericValue SRC = getOperandValue(SF.Caller.getCalledValue(), SF);
1102   callFunction((Function*)GVTOP(SRC), ArgVals);
1103 }
1104
1105 #define IMPLEMENT_SHIFT(OP, TY) \
1106    case Type::TY##TyID: Dest.TY##Val = Src1.TY##Val OP Src2.Int8Val; break
1107
1108 #define IMPLEMENT_SIGNLESS_SHIFT(OP, TY, CAST) \
1109    case Type::TY##TyID: Dest.TY##Val = ((CAST)Src1.TY##Val) OP Src2.Int8Val; \
1110      break
1111
1112 static GenericValue executeShlInst(GenericValue Src1, GenericValue Src2,
1113                                    const Type *Ty) {
1114   GenericValue Dest;
1115   switch (Ty->getTypeID()) {
1116     IMPLEMENT_SHIFT(<<, Int8);
1117     IMPLEMENT_SHIFT(<<, Int16);
1118     IMPLEMENT_SHIFT(<<, Int32);
1119     IMPLEMENT_SHIFT(<<, Int64);
1120   default:
1121     cerr << "Unhandled type for Shl instruction: " << *Ty << "\n";
1122   }
1123   return Dest;
1124 }
1125
1126 static GenericValue executeLShrInst(GenericValue Src1, GenericValue Src2,
1127                                     const Type *Ty) {
1128   GenericValue Dest;
1129   switch (Ty->getTypeID()) {
1130     IMPLEMENT_SIGNLESS_SHIFT(>>, Int8,  uint8_t);
1131     IMPLEMENT_SIGNLESS_SHIFT(>>, Int16, uint16_t);
1132     IMPLEMENT_SIGNLESS_SHIFT(>>, Int32, uint32_t);
1133     IMPLEMENT_SIGNLESS_SHIFT(>>, Int64, uint64_t);
1134   default:
1135     cerr << "Unhandled type for LShr instruction: " << *Ty << "\n";
1136     abort();
1137   }
1138   return Dest;
1139 }
1140
1141 static GenericValue executeAShrInst(GenericValue Src1, GenericValue Src2,
1142                                     const Type *Ty) {
1143   GenericValue Dest;
1144   switch (Ty->getTypeID()) {
1145     IMPLEMENT_SIGNLESS_SHIFT(>>, Int8,  int8_t);
1146     IMPLEMENT_SIGNLESS_SHIFT(>>, Int16, int16_t);
1147     IMPLEMENT_SIGNLESS_SHIFT(>>, Int32, int32_t);
1148     IMPLEMENT_SIGNLESS_SHIFT(>>, Int64, int64_t);
1149   default:
1150     cerr << "Unhandled type for AShr instruction: " << *Ty << "\n";
1151     abort();
1152   }
1153   return Dest;
1154 }
1155
1156 void Interpreter::visitShl(ShiftInst &I) {
1157   ExecutionContext &SF = ECStack.back();
1158   const Type *Ty    = I.getOperand(0)->getType();
1159   GenericValue Src1 = getOperandValue(I.getOperand(0), SF);
1160   GenericValue Src2 = getOperandValue(I.getOperand(1), SF);
1161   GenericValue Dest;
1162   Dest = executeShlInst (Src1, Src2, Ty);
1163   SetValue(&I, Dest, SF);
1164 }
1165
1166 void Interpreter::visitLShr(ShiftInst &I) {
1167   ExecutionContext &SF = ECStack.back();
1168   const Type *Ty    = I.getOperand(0)->getType();
1169   GenericValue Src1 = getOperandValue(I.getOperand(0), SF);
1170   GenericValue Src2 = getOperandValue(I.getOperand(1), SF);
1171   GenericValue Dest;
1172   Dest = executeLShrInst (Src1, Src2, Ty);
1173   SetValue(&I, Dest, SF);
1174 }
1175
1176 void Interpreter::visitAShr(ShiftInst &I) {
1177   ExecutionContext &SF = ECStack.back();
1178   const Type *Ty    = I.getOperand(0)->getType();
1179   GenericValue Src1 = getOperandValue(I.getOperand(0), SF);
1180   GenericValue Src2 = getOperandValue(I.getOperand(1), SF);
1181   GenericValue Dest;
1182   Dest = executeAShrInst (Src1, Src2, Ty);
1183   SetValue(&I, Dest, SF);
1184 }
1185
1186 #define IMPLEMENT_CAST_START \
1187   switch (DstTy->getTypeID()) {
1188
1189 #define IMPLEMENT_CAST(STY, DTY, CAST) \
1190      case Type::STY##TyID: Dest.DTY##Val = (CAST(Src.STY##Val)); break;
1191
1192 #define IMPLEMENT_CAST_CASE(DTY, CAST)          \
1193   case Type::DTY##TyID:                         \
1194     switch (SrcTy->getTypeID()) {               \
1195       IMPLEMENT_CAST(Int1,   DTY, CAST);        \
1196       IMPLEMENT_CAST(Int8,   DTY, CAST);        \
1197       IMPLEMENT_CAST(Int16,  DTY, CAST);        \
1198       IMPLEMENT_CAST(Int32,  DTY, CAST);        \
1199       IMPLEMENT_CAST(Int64,  DTY, CAST);        \
1200       IMPLEMENT_CAST(Pointer,DTY, CAST);        \
1201       IMPLEMENT_CAST(Float,  DTY, CAST);        \
1202       IMPLEMENT_CAST(Double, DTY, CAST);        \
1203     default:                                    \
1204       cerr << "Unhandled cast: "                \
1205         << *SrcTy << " to " << *DstTy << "\n";  \
1206       abort();                                  \
1207     }                                           \
1208     break
1209
1210 #define IMPLEMENT_CAST_END                      \
1211   default: cerr                                 \
1212       << "Unhandled dest type for cast instruction: "  \
1213       << *DstTy << "\n";                        \
1214     abort();                                    \
1215   }
1216
1217 GenericValue Interpreter::executeCastOperation(Instruction::CastOps opcode,
1218                                                Value *SrcVal, const Type *DstTy,
1219                                                ExecutionContext &SF) {
1220   const Type *SrcTy = SrcVal->getType();
1221   GenericValue Dest, Src = getOperandValue(SrcVal, SF);
1222
1223   if (opcode == Instruction::Trunc && DstTy->getTypeID() == Type::Int1TyID) {
1224     // For truncations to bool, we must clear the high order bits of the source
1225     switch (SrcTy->getTypeID()) {
1226       case Type::Int1TyID:  Src.Int1Val  &= 1; break;
1227       case Type::Int8TyID:  Src.Int8Val  &= 1; break;
1228       case Type::Int16TyID: Src.Int16Val &= 1; break;
1229       case Type::Int32TyID: Src.Int32Val &= 1; break;
1230       case Type::Int64TyID: Src.Int64Val &= 1; break;
1231       default:
1232         assert(0 && "Can't trunc a non-integer!");
1233         break;
1234     }
1235   } else if (opcode == Instruction::SExt &&
1236              SrcTy->getTypeID() == Type::Int1TyID) {
1237     // For sign extension from bool, we must extend the source bits.
1238     SrcTy = Type::Int64Ty;
1239     Src.Int64Val = 0 - Src.Int1Val;
1240   }
1241
1242   switch (opcode) {
1243     case Instruction::Trunc:     // src integer, dest integral (can't be long)
1244       IMPLEMENT_CAST_START
1245       IMPLEMENT_CAST_CASE(Int1 , (bool));
1246       IMPLEMENT_CAST_CASE(Int8 , (uint8_t));
1247       IMPLEMENT_CAST_CASE(Int16, (uint16_t));
1248       IMPLEMENT_CAST_CASE(Int32, (uint32_t));
1249       IMPLEMENT_CAST_CASE(Int64, (uint64_t));
1250       IMPLEMENT_CAST_END
1251       break;
1252     case Instruction::ZExt:      // src integral (can't be long), dest integer
1253       IMPLEMENT_CAST_START
1254       IMPLEMENT_CAST_CASE(Int8 , (uint8_t));
1255       IMPLEMENT_CAST_CASE(Int16, (uint16_t));
1256       IMPLEMENT_CAST_CASE(Int32, (uint32_t));
1257       IMPLEMENT_CAST_CASE(Int64, (uint64_t));
1258       IMPLEMENT_CAST_END
1259       break;
1260     case Instruction::SExt:      // src integral (can't be long), dest integer
1261       IMPLEMENT_CAST_START
1262       IMPLEMENT_CAST_CASE(Int8 , (uint8_t)(int8_t));
1263       IMPLEMENT_CAST_CASE(Int16, (uint16_t)(int16_t));
1264       IMPLEMENT_CAST_CASE(Int32, (uint32_t)(int32_t));
1265       IMPLEMENT_CAST_CASE(Int64, (uint64_t)(int64_t));
1266       IMPLEMENT_CAST_END
1267       break;
1268     case Instruction::FPTrunc:   // src double, dest float
1269       IMPLEMENT_CAST_START
1270       IMPLEMENT_CAST_CASE(Float  , (float));
1271       IMPLEMENT_CAST_END
1272       break;
1273     case Instruction::FPExt:     // src float, dest double
1274       IMPLEMENT_CAST_START
1275       IMPLEMENT_CAST_CASE(Double , (double));
1276       IMPLEMENT_CAST_END
1277       break;
1278     case Instruction::UIToFP:    // src integral, dest floating
1279       IMPLEMENT_CAST_START
1280       IMPLEMENT_CAST_CASE(Float  , (float)(uint64_t));
1281       IMPLEMENT_CAST_CASE(Double , (double)(uint64_t));
1282       IMPLEMENT_CAST_END
1283       break;
1284     case Instruction::SIToFP:    // src integeral, dest floating
1285       IMPLEMENT_CAST_START
1286       IMPLEMENT_CAST_CASE(Float  , (float)(int64_t));
1287       IMPLEMENT_CAST_CASE(Double , (double)(int64_t));
1288       IMPLEMENT_CAST_END
1289       break;
1290     case Instruction::FPToUI:    // src floating, dest integral
1291       IMPLEMENT_CAST_START
1292       IMPLEMENT_CAST_CASE(Int1 , (bool));
1293       IMPLEMENT_CAST_CASE(Int8 , (uint8_t));
1294       IMPLEMENT_CAST_CASE(Int16, (uint16_t));
1295       IMPLEMENT_CAST_CASE(Int32, (uint32_t ));
1296       IMPLEMENT_CAST_CASE(Int64, (uint64_t));
1297       IMPLEMENT_CAST_END
1298       break;
1299     case Instruction::FPToSI:    // src floating, dest integral
1300       IMPLEMENT_CAST_START
1301       IMPLEMENT_CAST_CASE(Int1 , (bool));
1302       IMPLEMENT_CAST_CASE(Int8 , (uint8_t) (int8_t));
1303       IMPLEMENT_CAST_CASE(Int16, (uint16_t)(int16_t));
1304       IMPLEMENT_CAST_CASE(Int32, (uint32_t)(int32_t));
1305       IMPLEMENT_CAST_CASE(Int64, (uint64_t)(int64_t));
1306       IMPLEMENT_CAST_END
1307       break;
1308     case Instruction::PtrToInt:  // src pointer,  dest integral
1309       IMPLEMENT_CAST_START
1310       IMPLEMENT_CAST_CASE(Int1 , (bool));
1311       IMPLEMENT_CAST_CASE(Int8 , (uint8_t));
1312       IMPLEMENT_CAST_CASE(Int16, (uint16_t));
1313       IMPLEMENT_CAST_CASE(Int32, (uint32_t));
1314       IMPLEMENT_CAST_CASE(Int64, (uint64_t));
1315       IMPLEMENT_CAST_END
1316       break;
1317     case Instruction::IntToPtr:  // src integral, dest pointer
1318       IMPLEMENT_CAST_START
1319       IMPLEMENT_CAST_CASE(Pointer, (PointerTy));
1320       IMPLEMENT_CAST_END
1321       break;
1322     case Instruction::BitCast:   // src any, dest any (same size)
1323       IMPLEMENT_CAST_START
1324       IMPLEMENT_CAST_CASE(Int1   , (bool));
1325       IMPLEMENT_CAST_CASE(Int8   , (uint8_t));
1326       IMPLEMENT_CAST_CASE(Int16  , (uint16_t));
1327       IMPLEMENT_CAST_CASE(Int32  , (uint32_t));
1328       IMPLEMENT_CAST_CASE(Int64  , (uint64_t));
1329       IMPLEMENT_CAST_CASE(Pointer, (PointerTy));
1330       IMPLEMENT_CAST_CASE(Float  , (float));
1331       IMPLEMENT_CAST_CASE(Double , (double));
1332       IMPLEMENT_CAST_END
1333       break;
1334     default:
1335       cerr << "Invalid cast opcode for cast instruction: " << opcode << "\n";
1336       abort();
1337   }
1338   return Dest;
1339 }
1340
1341 void Interpreter::visitCastInst(CastInst &I) {
1342   ExecutionContext &SF = ECStack.back();
1343   SetValue(&I, executeCastOperation(I.getOpcode(), I.getOperand(0),
1344                                     I.getType(), SF), SF);
1345 }
1346
1347 #define IMPLEMENT_VAARG(TY) \
1348    case Type::TY##TyID: Dest.TY##Val = Src.TY##Val; break
1349
1350 void Interpreter::visitVAArgInst(VAArgInst &I) {
1351   ExecutionContext &SF = ECStack.back();
1352
1353   // Get the incoming valist parameter.  LLI treats the valist as a
1354   // (ec-stack-depth var-arg-index) pair.
1355   GenericValue VAList = getOperandValue(I.getOperand(0), SF);
1356   GenericValue Dest;
1357   GenericValue Src = ECStack[VAList.UIntPairVal.first]
1358    .VarArgs[VAList.UIntPairVal.second];
1359   const Type *Ty = I.getType();
1360   switch (Ty->getTypeID()) {
1361     IMPLEMENT_VAARG(Int8);
1362     IMPLEMENT_VAARG(Int16);
1363     IMPLEMENT_VAARG(Int32);
1364     IMPLEMENT_VAARG(Int64);
1365     IMPLEMENT_VAARG(Pointer);
1366     IMPLEMENT_VAARG(Float);
1367     IMPLEMENT_VAARG(Double);
1368     IMPLEMENT_VAARG(Int1);
1369   default:
1370     cerr << "Unhandled dest type for vaarg instruction: " << *Ty << "\n";
1371     abort();
1372   }
1373
1374   // Set the Value of this Instruction.
1375   SetValue(&I, Dest, SF);
1376
1377   // Move the pointer to the next vararg.
1378   ++VAList.UIntPairVal.second;
1379 }
1380
1381 //===----------------------------------------------------------------------===//
1382 //                        Dispatch and Execution Code
1383 //===----------------------------------------------------------------------===//
1384
1385 //===----------------------------------------------------------------------===//
1386 // callFunction - Execute the specified function...
1387 //
1388 void Interpreter::callFunction(Function *F,
1389                                const std::vector<GenericValue> &ArgVals) {
1390   assert((ECStack.empty() || ECStack.back().Caller.getInstruction() == 0 ||
1391           ECStack.back().Caller.arg_size() == ArgVals.size()) &&
1392          "Incorrect number of arguments passed into function call!");
1393   // Make a new stack frame... and fill it in.
1394   ECStack.push_back(ExecutionContext());
1395   ExecutionContext &StackFrame = ECStack.back();
1396   StackFrame.CurFunction = F;
1397
1398   // Special handling for external functions.
1399   if (F->isExternal()) {
1400     GenericValue Result = callExternalFunction (F, ArgVals);
1401     // Simulate a 'ret' instruction of the appropriate type.
1402     popStackAndReturnValueToCaller (F->getReturnType (), Result);
1403     return;
1404   }
1405
1406   // Get pointers to first LLVM BB & Instruction in function.
1407   StackFrame.CurBB     = F->begin();
1408   StackFrame.CurInst   = StackFrame.CurBB->begin();
1409
1410   // Run through the function arguments and initialize their values...
1411   assert((ArgVals.size() == F->arg_size() ||
1412          (ArgVals.size() > F->arg_size() && F->getFunctionType()->isVarArg()))&&
1413          "Invalid number of values passed to function invocation!");
1414
1415   // Handle non-varargs arguments...
1416   unsigned i = 0;
1417   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI, ++i)
1418     SetValue(AI, ArgVals[i], StackFrame);
1419
1420   // Handle varargs arguments...
1421   StackFrame.VarArgs.assign(ArgVals.begin()+i, ArgVals.end());
1422 }
1423
1424 void Interpreter::run() {
1425   while (!ECStack.empty()) {
1426     // Interpret a single instruction & increment the "PC".
1427     ExecutionContext &SF = ECStack.back();  // Current stack frame
1428     Instruction &I = *SF.CurInst++;         // Increment before execute
1429
1430     // Track the number of dynamic instructions executed.
1431     ++NumDynamicInsts;
1432
1433     DOUT << "About to interpret: " << I;
1434     visit(I);   // Dispatch to one of the visit* methods...
1435   }
1436 }