Initial checkin of interpreter

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@361 91177308-0d34-0410-b5e6-96231b3b80d8

8 files changed, 1132 insertions, 0 deletions

diff --git a/lib/ExecutionEngine/Interpreter/Execution.cpp b/lib/ExecutionEngine/Interpreter/Execution.cpp
new file mode 100644
index 0000000..92d8b66
--- /dev/null
+++ b/lib/ExecutionEngine/Interpreter/Execution.cpp
@@ -0,0 +1,598 @@
+//===-- Execution.cpp - Implement code to simulate the program ------------===//
+// 
+//  This file contains the actual instruction interpreter.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Interpreter.h"
+#include "ExecutionAnnotations.h"
+#include "llvm/iOther.h"
+#include "llvm/iTerminators.h"
+#include "llvm/Type.h"
+#include "llvm/ConstPoolVals.h"
+#include "llvm/Assembly/Writer.h"
+
+static unsigned getOperandSlot(Value *V) {
+  SlotNumber *SN = (SlotNumber*)V->getAnnotation(SlotNumberAID);
+  assert(SN && "Operand does not have a slot number annotation!");
+  return SN->SlotNum;
+}
+
+#define GET_CONST_VAL(TY, CLASS) \
+  case Type::TY##TyID: Result.TY##Val = ((CLASS*)CPV)->getValue(); break
+
+static GenericValue getOperandValue(Value *V, ExecutionContext &SF) {
+  if (ConstPoolVal *CPV = V->castConstant()) {
+    GenericValue Result;
+    switch (CPV->getType()->getPrimitiveID()) {
+      GET_CONST_VAL(Bool   , ConstPoolBool);
+      GET_CONST_VAL(UByte  , ConstPoolUInt);
+      GET_CONST_VAL(SByte  , ConstPoolSInt);
+      GET_CONST_VAL(UShort , ConstPoolUInt);
+      GET_CONST_VAL(Short  , ConstPoolSInt);
+      GET_CONST_VAL(UInt   , ConstPoolUInt);
+      GET_CONST_VAL(Int    , ConstPoolSInt);
+      GET_CONST_VAL(Float  , ConstPoolFP);
+      GET_CONST_VAL(Double , ConstPoolFP);
+    default:
+      cout << "ERROR: Constant unimp for type: " << CPV->getType() << endl;
+    }
+    return Result;
+  } else {
+    unsigned TyP = V->getType()->getUniqueID();   // TypePlane for value
+    return SF.Values[TyP][getOperandSlot(V)];
+  }
+}
+
+static void SetValue(Value *V, GenericValue Val, ExecutionContext &SF) {
+  unsigned TyP = V->getType()->getUniqueID();   // TypePlane for value
+  SF.Values[TyP][getOperandSlot(V)] = Val;
+}
+
+
+
+//===----------------------------------------------------------------------===//
+//                    Binary Instruction Implementations
+//===----------------------------------------------------------------------===//
+
+#define IMPLEMENT_BINARY_OPERATOR(OP, TY) \
+   case Type::TY##TyID: Dest.TY##Val = Src1.TY##Val OP Src2.TY##Val; break
+
+static GenericValue executeAddInst(GenericValue Src1, GenericValue Src2, 
+				   const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_BINARY_OPERATOR(+, UByte);
+    IMPLEMENT_BINARY_OPERATOR(+, SByte);
+    IMPLEMENT_BINARY_OPERATOR(+, UShort);
+    IMPLEMENT_BINARY_OPERATOR(+, Short);
+    IMPLEMENT_BINARY_OPERATOR(+, UInt);
+    IMPLEMENT_BINARY_OPERATOR(+, Int);
+    IMPLEMENT_BINARY_OPERATOR(+, Float);
+    IMPLEMENT_BINARY_OPERATOR(+, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for Add instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+static GenericValue executeSubInst(GenericValue Src1, GenericValue Src2, 
+				   const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_BINARY_OPERATOR(-, UByte);
+    IMPLEMENT_BINARY_OPERATOR(-, SByte);
+    IMPLEMENT_BINARY_OPERATOR(-, UShort);
+    IMPLEMENT_BINARY_OPERATOR(-, Short);
+    IMPLEMENT_BINARY_OPERATOR(-, UInt);
+    IMPLEMENT_BINARY_OPERATOR(-, Int);
+    IMPLEMENT_BINARY_OPERATOR(-, Float);
+    IMPLEMENT_BINARY_OPERATOR(-, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for Sub instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+#define IMPLEMENT_SETCC(OP, TY) \
+   case Type::TY##TyID: Dest.BoolVal = Src1.TY##Val OP Src2.TY##Val; break
+
+
+static GenericValue executeSetEQInst(GenericValue Src1, GenericValue Src2, 
+				     const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_SETCC(==, UByte);
+    IMPLEMENT_SETCC(==, SByte);
+    IMPLEMENT_SETCC(==, UShort);
+    IMPLEMENT_SETCC(==, Short);
+    IMPLEMENT_SETCC(==, UInt);
+    IMPLEMENT_SETCC(==, Int);
+    IMPLEMENT_SETCC(==, Float);
+    IMPLEMENT_SETCC(==, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for SetEQ instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+static GenericValue executeSetNEInst(GenericValue Src1, GenericValue Src2, 
+				     const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_SETCC(!=, UByte);
+    IMPLEMENT_SETCC(!=, SByte);
+    IMPLEMENT_SETCC(!=, UShort);
+    IMPLEMENT_SETCC(!=, Short);
+    IMPLEMENT_SETCC(!=, UInt);
+    IMPLEMENT_SETCC(!=, Int);
+    IMPLEMENT_SETCC(!=, Float);
+    IMPLEMENT_SETCC(!=, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for SetNE instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+static GenericValue executeSetLEInst(GenericValue Src1, GenericValue Src2, 
+				     const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_SETCC(<=, UByte);
+    IMPLEMENT_SETCC(<=, SByte);
+    IMPLEMENT_SETCC(<=, UShort);
+    IMPLEMENT_SETCC(<=, Short);
+    IMPLEMENT_SETCC(<=, UInt);
+    IMPLEMENT_SETCC(<=, Int);
+    IMPLEMENT_SETCC(<=, Float);
+    IMPLEMENT_SETCC(<=, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for SetLE instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+static GenericValue executeSetGEInst(GenericValue Src1, GenericValue Src2, 
+				     const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_SETCC(>=, UByte);
+    IMPLEMENT_SETCC(>=, SByte);
+    IMPLEMENT_SETCC(>=, UShort);
+    IMPLEMENT_SETCC(>=, Short);
+    IMPLEMENT_SETCC(>=, UInt);
+    IMPLEMENT_SETCC(>=, Int);
+    IMPLEMENT_SETCC(>=, Float);
+    IMPLEMENT_SETCC(>=, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for SetGE instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+static GenericValue executeSetLTInst(GenericValue Src1, GenericValue Src2, 
+				     const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_SETCC(<, UByte);
+    IMPLEMENT_SETCC(<, SByte);
+    IMPLEMENT_SETCC(<, UShort);
+    IMPLEMENT_SETCC(<, Short);
+    IMPLEMENT_SETCC(<, UInt);
+    IMPLEMENT_SETCC(<, Int);
+    IMPLEMENT_SETCC(<, Float);
+    IMPLEMENT_SETCC(<, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for SetLT instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+static GenericValue executeSetGTInst(GenericValue Src1, GenericValue Src2, 
+				     const Type *Ty, ExecutionContext &SF) {
+  GenericValue Dest;
+  switch (Ty->getPrimitiveID()) {
+    IMPLEMENT_SETCC(>, UByte);
+    IMPLEMENT_SETCC(>, SByte);
+    IMPLEMENT_SETCC(>, UShort);
+    IMPLEMENT_SETCC(>, Short);
+    IMPLEMENT_SETCC(>, UInt);
+    IMPLEMENT_SETCC(>, Int);
+    IMPLEMENT_SETCC(>, Float);
+    IMPLEMENT_SETCC(>, Double);
+  case Type::ULongTyID:
+  case Type::LongTyID:
+  default:
+    cout << "Unhandled type for SetGT instruction: " << Ty << endl;
+  }
+  return Dest;
+}
+
+static void executeBinaryInst(BinaryOperator *I, ExecutionContext &SF) {
+  const Type *Ty = I->getOperand(0)->getType();
+  GenericValue Src1  = getOperandValue(I->getOperand(0), SF);
+  GenericValue Src2  = getOperandValue(I->getOperand(1), SF);
+  GenericValue R;   // Result
+
+  switch (I->getOpcode()) {
+  case Instruction::Add: R = executeAddInst(Src1, Src2, Ty, SF); break;
+  case Instruction::Sub: R = executeSubInst(Src1, Src2, Ty, SF); break;
+  case Instruction::SetEQ: R = executeSetEQInst(Src1, Src2, Ty, SF); break;
+  case Instruction::SetNE: R = executeSetNEInst(Src1, Src2, Ty, SF); break;
+  case Instruction::SetLE: R = executeSetLEInst(Src1, Src2, Ty, SF); break;
+  case Instruction::SetGE: R = executeSetGEInst(Src1, Src2, Ty, SF); break;
+  case Instruction::SetLT: R = executeSetLTInst(Src1, Src2, Ty, SF); break;
+  case Instruction::SetGT: R = executeSetGTInst(Src1, Src2, Ty, SF); break;
+  default:
+    cout << "Don't know how to handle this binary operator!\n-->" << I;
+  }
+
+  SetValue(I, R, SF);
+}
+
+
+//===----------------------------------------------------------------------===//
+//                     Terminator Instruction Implementations
+//===----------------------------------------------------------------------===//
+
+void Interpreter::executeRetInst(ReturnInst *I, ExecutionContext &SF) {
+  const Type *RetTy = 0;
+  GenericValue Result;
+
+  // Save away the return value... (if we are not 'ret void')
+  if (I->getNumOperands()) {
+    RetTy  = I->getReturnValue()->getType();
+    Result = getOperandValue(I->getReturnValue(), SF);
+  }
+
+  // Save previously executing meth
+  const Method *M = ECStack.back().CurMethod;
+
+  // Pop the current stack frame... this invalidates SF
+  ECStack.pop_back();
+
+  if (ECStack.empty()) {  // Finished main.  Put result into exit code...
+    if (RetTy) {          // Nonvoid return type?
+      cout << "Method " << M->getType() << " \"" << M->getName()
+	   << "\" returned ";
+      printValue(RetTy, Result);
+      cout << endl;
+
+      if (RetTy->isIntegral())
+	ExitCode = Result.SByteVal;   // Capture the exit code of the program
+    } else {
+      ExitCode = 0;
+    }
+    return;
+  }
+
+  // If we have a previous stack frame, and we have a previous call, fill in
+  // the return value...
+  //
+  ExecutionContext &NewSF = ECStack.back();
+  if (NewSF.Caller) {
+    if (NewSF.Caller->getType() != Type::VoidTy)             // Save result...
+      SetValue(NewSF.Caller, Result, NewSF);
+
+    NewSF.Caller = 0;          // We returned from the call...
+  }
+}
+
+void Interpreter::executeBrInst(BranchInst *I, ExecutionContext &SF) {
+  SF.PrevBB = SF.CurBB;               // Update PrevBB so that PHI nodes work...
+  BasicBlock *Dest;
+
+  Dest = I->getSuccessor(0);          // Uncond branches have a fixed dest...
+  if (!I->isUnconditional()) {
+    if (getOperandValue(I->getCondition(), SF).BoolVal == 0) // If false cond...
+      Dest = I->getSuccessor(1);    
+  }
+  SF.CurBB   = Dest;                  // Update CurBB to branch destination
+  SF.CurInst = SF.CurBB->begin();     // Update new instruction ptr...
+}
+
+//===----------------------------------------------------------------------===//
+//                 Miscellaneous Instruction Implementations
+//===----------------------------------------------------------------------===//
+
+void Interpreter::executeCallInst(CallInst *I, ExecutionContext &SF) {
+  ECStack.back().Caller = I;
+  callMethod(I->getCalledMethod(), &ECStack.back());
+}
+
+static void executePHINode(PHINode *I, ExecutionContext &SF) {
+  BasicBlock *PrevBB = SF.PrevBB;
+  Value *IncomingValue = 0;
+
+  // Search for the value corresponding to this previous bb...
+  for (unsigned i = I->getNumIncomingValues(); i > 0;) {
+    if (I->getIncomingBlock(--i) == PrevBB) {
+      IncomingValue = I->getIncomingValue(i);
+      break;
+    }
+  }
+  assert(IncomingValue && "No PHI node predecessor for current PrevBB!");
+
+  // Found the value, set as the result...
+  SetValue(I, getOperandValue(IncomingValue, SF), SF);
+}
+
+
+
+
+
+//===----------------------------------------------------------------------===//
+//                        Dispatch and Execution Code
+//===----------------------------------------------------------------------===//
+
+MethodInfo::MethodInfo(Method *M) : Annotation(MethodInfoAID) {
+  // Assign slot numbers to the method arguments...
+  const Method::ArgumentListType &ArgList = M->getArgumentList();
+  for (Method::ArgumentListType::const_iterator AI = ArgList.begin(), 
+	 AE = ArgList.end(); AI != AE; ++AI) {
+    MethodArgument *MA = *AI;
+    MA->addAnnotation(new SlotNumber(getValueSlot(MA)));
+  }
+
+  // Iterate over all of the instructions...
+  unsigned InstNum = 0;
+  for (Method::inst_iterator MI = M->inst_begin(), ME = M->inst_end();
+       MI != ME; ++MI) {
+    Instruction *I = *MI;                          // For each instruction...
+    I->addAnnotation(new InstNumber(++InstNum, getValueSlot(I))); // Add Annote
+  }
+}
+
+unsigned MethodInfo::getValueSlot(const Value *V) {
+  unsigned Plane = V->getType()->getUniqueID();
+  if (Plane >= NumPlaneElements.size())
+    NumPlaneElements.resize(Plane+1, 0);
+  return NumPlaneElements[Plane]++;
+}
+
+
+void Interpreter::initializeExecutionEngine() {
+  AnnotationManager::registerAnnotationFactory(MethodInfoAID, CreateMethodInfo);
+}
+
+
+
+//===----------------------------------------------------------------------===//
+// callMethod - Execute the specified method...
+//
+void Interpreter::callMethod(Method *M, ExecutionContext *CallingSF = 0) {
+  if (M->isExternal()) {
+    // Handle builtin methods
+    cout << "Error: Method '" << M->getName() << "' is external!\n";
+    return;
+  }
+
+  // Process the method, assigning instruction numbers to the instructions in
+  // the method.  Also calculate the number of values for each type slot active.
+  //
+  MethodInfo *MethInfo = (MethodInfo*)M->getOrCreateAnnotation(MethodInfoAID);
+
+  ECStack.push_back(ExecutionContext());         // Make a new stack frame...
+  ExecutionContext &StackFrame = ECStack.back(); // Fill it in...
+  StackFrame.CurMethod = M;
+  StackFrame.CurBB     = M->front();
+  StackFrame.CurInst   = StackFrame.CurBB->begin();
+  StackFrame.MethInfo  = MethInfo;
+
+  // Initialize the values to nothing...
+  StackFrame.Values.resize(MethInfo->NumPlaneElements.size());
+  for (unsigned i = 0; i < MethInfo->NumPlaneElements.size(); ++i)
+    StackFrame.Values[i].resize(MethInfo->NumPlaneElements[i]);
+
+  StackFrame.PrevBB = 0;  // No previous BB for PHI nodes...
+
+  // Run through the method arguments and initialize their values...
+  if (CallingSF) {
+    CallInst *Call = CallingSF->Caller;
+    assert(Call && "Caller improperly initialized!");
+    
+    unsigned i = 0;
+    for (Method::ArgumentListType::iterator MI = M->getArgumentList().begin(),
+	   ME = M->getArgumentList().end(); MI != ME; ++MI, ++i) {
+      Value *V = Call->getOperand(i+1);
+      MethodArgument *MA = *MI;
+
+      SetValue(MA, getOperandValue(V, *CallingSF), StackFrame);
+    }
+  }
+}
+
+// executeInstruction - Interpret a single instruction, increment the "PC", and
+// return true if the next instruction is a breakpoint...
+//
+bool Interpreter::executeInstruction() {
+  assert(!ECStack.empty() && "No program running, cannot execute inst!");
+
+  ExecutionContext &SF = ECStack.back();  // Current stack frame
+  Instruction *I = *SF.CurInst++;         // Increment before execute
+
+  if (I->isBinaryOp()) {
+    executeBinaryInst((BinaryOperator*)I, SF);
+  } else {
+    switch (I->getOpcode()) {
+    case Instruction::Ret:     executeRetInst   ((ReturnInst*)I, SF); break;
+    case Instruction::Br:      executeBrInst    ((BranchInst*)I, SF); break;
+    case Instruction::Call:    executeCallInst  ((CallInst*)  I, SF); break;
+    case Instruction::PHINode: executePHINode   ((PHINode*)   I, SF); break;
+    default:
+      cout << "Don't know how to execute this instruction!\n-->" << I;
+    }
+  }
+  
+  // Reset the current frame location to the top of stack
+  CurFrame = ECStack.size()-1;
+
+  if (CurFrame == -1) return false;  // No breakpoint if no code
+
+  // Return true if there is a breakpoint annotation on the instruction...
+  return (*ECStack[CurFrame].CurInst)->getAnnotation(BreakpointAID) != 0;
+}
+
+void Interpreter::stepInstruction() {  // Do the 'step' command
+  if (ECStack.empty()) {
+    cout << "Error: no program running, cannot step!\n";
+    return;
+  }
+
+  // Run an instruction...
+  executeInstruction();
+
+  // Print the next instruction to execute...
+  printCurrentInstruction();
+}
+
+// --- UI Stuff...
+
+
+
+void Interpreter::nextInstruction() {  // Do the 'next' command
+  if (ECStack.empty()) {
+    cout << "Error: no program running, cannot 'next'!\n";
+    return;
+  }
+
+  // If this is a call instruction, step over the call instruction...
+  // TODO: ICALL, CALL WITH, ...
+  if ((*ECStack.back().CurInst)->getOpcode() == Instruction::Call) {
+    // Step into the function...
+    if (executeInstruction()) {
+      // Hit a breakpoint, print current instruction, then return to user...
+      cout << "Breakpoint hit!\n";
+      printCurrentInstruction();
+      return;
+    }
+
+    // Finish executing the function...
+    finish();
+  } else {
+    // Normal instruction, just step...
+    stepInstruction();
+  }
+}
+
+void Interpreter::run() {
+  if (ECStack.empty()) {
+    cout << "Error: no program running, cannot run!\n";
+    return;
+  }
+
+  bool HitBreakpoint = false;
+  while (!ECStack.empty() && !HitBreakpoint) {
+    // Run an instruction...
+    HitBreakpoint = executeInstruction();
+  }
+
+  if (HitBreakpoint) {
+    cout << "Breakpoint hit!\n";
+  }
+
+  // Print the next instruction to execute...
+  printCurrentInstruction();
+}
+
+void Interpreter::finish() {
+  if (ECStack.empty()) {
+    cout << "Error: no program running, cannot run!\n";
+    return;
+  }
+
+  unsigned StackSize = ECStack.size();
+  bool HitBreakpoint = false;
+  while (ECStack.size() >= StackSize && !HitBreakpoint) {
+    // Run an instruction...
+    HitBreakpoint = executeInstruction();
+  }
+
+  if (HitBreakpoint) {
+    cout << "Breakpoint hit!\n";
+  }
+
+  // Print the next instruction to execute...
+  printCurrentInstruction();
+}
+
+
+
+// printCurrentInstruction - Print out the instruction that the virtual PC is
+// at, or fail silently if no program is running.
+//
+void Interpreter::printCurrentInstruction() {
+  if (!ECStack.empty()) {
+    Instruction *I = *ECStack.back().CurInst;
+    InstNumber *IN = (InstNumber*)I->getAnnotation(SlotNumberAID);
+    assert(IN && "Instruction has no numbering annotation!");
+    cout << "#" << IN->InstNum << I;
+  }
+}
+
+void Interpreter::printValue(const Type *Ty, GenericValue V) {
+  cout << Ty << " ";
+
+  switch (Ty->getPrimitiveID()) {
+  case Type::BoolTyID:   cout << (V.BoolVal?"true":"false"); break;
+  case Type::SByteTyID:  cout << V.SByteVal;  break;
+  case Type::UByteTyID:  cout << V.UByteVal;  break;
+  case Type::ShortTyID:  cout << V.ShortVal;  break;
+  case Type::UShortTyID: cout << V.UShortVal; break;
+  case Type::IntTyID:    cout << V.IntVal;    break;
+  case Type::UIntTyID:   cout << V.UIntVal;   break;
+  case Type::FloatTyID:  cout << V.FloatVal;  break;
+  case Type::DoubleTyID: cout << V.DoubleVal; break;
+  default:
+    cout << "- Don't know how to print value of this type!";
+    break;
+  }
+}
+
+void Interpreter::printValue(const string &Name) {
+  Value *PickedVal = ChooseOneOption(Name, LookupMatchingNames(Name));
+  if (!PickedVal) return;
+
+  if (const Method *M = PickedVal->castMethod()) {
+    cout << M;  // Print the method
+  } else {      // Otherwise there should be an annotation for the slot#
+    printValue(PickedVal->getType(), 
+	       getOperandValue(PickedVal, ECStack[CurFrame]));
+    cout << endl;
+  }
+    
+}
+
+void Interpreter::list() {
+  if (ECStack.empty())
+    cout << "Error: No program executing!\n";
+  else
+    cout << ECStack[CurFrame].CurMethod;   // Just print the method out...
+}
+
+void Interpreter::printStackTrace() {
+  if (ECStack.empty()) cout << "No program executing!\n";
+
+  for (unsigned i = 0; i < ECStack.size(); ++i) {
+    cout << (((int)i == CurFrame) ? '>' : '-');
+    cout << "#" << i << ". " << ECStack[i].CurMethod->getType() << " \""
+	 << ECStack[i].CurMethod->getName() << "\"(";
+    // TODO: Print Args
+    cout << ")" << endl;
+    cout << *ECStack[i].CurInst;
+  }
+}
diff --git a/lib/ExecutionEngine/Interpreter/ExecutionAnnotations.h b/lib/ExecutionEngine/Interpreter/ExecutionAnnotations.h
new file mode 100644
index 0000000..931de6a
--- /dev/null
+++ b/lib/ExecutionEngine/Interpreter/ExecutionAnnotations.h
@@ -0,0 +1,91 @@
+//===-- ExecutionAnnotations.h ---------------------------------*- C++ -*--===//
+//
+// This header file defines annotations used by the execution engine.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLI_EXECUTION_ANNOTATIONS_H
+#define LLI_EXECUTION_ANNOTATIONS_H
+
+//===----------------------------------------------------------------------===//
+// Support for MethodInfo annotations
+//===----------------------------------------------------------------------===//
+
+// This annotation (attached only to Method objects) is used to cache useful
+// information about the method, including the number of types present in the
+// method, and the number of values for each type.
+//
+// This annotation object is created on demand, and attaches other annotation
+// objects to the instructions in the method when it's created.
+//
+static AnnotationID MethodInfoAID(
+	            AnnotationManager::getID("Interpreter::MethodInfo"));
+
+struct MethodInfo : public Annotation {
+  MethodInfo(Method *M);
+  vector<unsigned> NumPlaneElements;
+
+private:
+  unsigned getValueSlot(const Value *V);
+};
+
+// CreateMethodInfo - Factory function to allow MethodInfo annotations to be
+// created on demand.
+//
+inline static Annotation *CreateMethodInfo(AnnotationID AID, Annotable *O) {
+  assert(AID == MethodInfoAID);
+  return new MethodInfo((Method*)O);  // Simply invoke the ctor
+}
+
+
+//===----------------------------------------------------------------------===//
+// Support for the SlotNumber annotation
+//===----------------------------------------------------------------------===//
+
+// This annotation (attached only to MethodArgument & Instruction objects) is
+// used to hold the the slot number for the value in its type plane.
+//
+// Entities have this annotation attached to them when the containing
+// method has it's MethodInfo created (by the MethodInfo ctor).
+//
+static AnnotationID SlotNumberAID(
+	            AnnotationManager::getID("Interpreter::SlotNumber"));
+
+struct SlotNumber : public Annotation {
+  unsigned SlotNum;   // Ranges from 0->
+
+  SlotNumber(unsigned sn) : Annotation(SlotNumberAID), 
+			    SlotNum(sn) {}
+};
+
+
+
+
+//===----------------------------------------------------------------------===//
+// Support for the InstNumber annotation
+//===----------------------------------------------------------------------===//
+
+// This annotation (attached only to Instruction objects) is used to hold the
+// instruction number of the instruction, and the slot number for the value in
+// its type plane.  InstNumber's are used for user interaction, and for
+// calculating which value slot to store the result of the instruction in.
+//
+// Instructions have this annotation attached to them when the containing method
+// has it's MethodInfo created (by the MethodInfo ctor).
+//
+struct InstNumber : public SlotNumber {
+  unsigned InstNum;   // Ranges from 1->
+
+  InstNumber(unsigned in, unsigned sn) : SlotNumber(sn), InstNum(in) {}
+};
+
+
+//===----------------------------------------------------------------------===//
+// Support for the Breakpoint annotation
+//===----------------------------------------------------------------------===//
+
+static AnnotationID BreakpointAID(
+	            AnnotationManager::getID("Interpreter::Breakpoint"));
+// Just use an Annotation directly, Breakpoint is currently just a marker
+
+#endif
diff --git a/lib/ExecutionEngine/Interpreter/Interpreter.h b/lib/ExecutionEngine/Interpreter/Interpreter.h
new file mode 100644
index 0000000..9ff8336
--- /dev/null
+++ b/lib/ExecutionEngine/Interpreter/Interpreter.h
@@ -0,0 +1,129 @@
+//===-- Interpreter.h ------------------------------------------*- C++ -*--===//
+//
+// This header file defines the interpreter structure
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLI_INTERPRETER_H
+#define LLI_INTERPRETER_H
+
+#include "llvm/Module.h"
+#include "llvm/Method.h"
+
+struct MethodInfo;          // Defined in ExecutionAnnotations.h
+class CallInst;
+class ReturnInst;
+class BranchInst;
+
+union GenericValue {
+  bool            BoolVal;
+  unsigned char   UByteVal;
+  signed   char   SByteVal;
+  unsigned short  UShortVal;
+  signed   short  ShortVal;
+  unsigned int    UIntVal;
+  signed   int    IntVal;
+  double          DoubleVal;
+  float           FloatVal;
+  GenericValue *PointerVal;
+};
+
+typedef vector<GenericValue> ValuePlaneTy;
+
+// ExecutionContext struct - This struct represents one stack frame currently
+// executing.
+//
+struct ExecutionContext {
+  Method               *CurMethod;  // The currently executing method
+  BasicBlock           *CurBB;      // The currently executing BB
+  BasicBlock::iterator  CurInst;    // The next instruction to execute
+  MethodInfo           *MethInfo;   // The MethInfo annotation for the method
+  vector<ValuePlaneTy>  Values;     // ValuePlanes for each type
+
+  BasicBlock           *PrevBB;     // The previous BB or null if in first BB
+  CallInst             *Caller;     // Holds the call that called subframes.
+                                    // NULL if main func or debugger invoked fn
+};
+
+
+// Interpreter - This class represents the entirety of the interpreter.
+//
+class Interpreter {
+  Module *CurMod;              // The current Module being executed (0 if none)
+  int ExitCode;                // The exit code to be returned by the lli util
+  bool Profile;                // Profiling enabled?
+  int CurFrame;                // The current stack frame being inspected
+
+  // The runtime stack of executing code.  The top of the stack is the current
+  // method record.
+  vector<ExecutionContext> ECStack;
+
+public:
+  Interpreter();
+  inline ~Interpreter() { delete CurMod; }
+
+  // getExitCode - return the code that should be the exit code for the lli
+  // utility.
+  inline int getExitCode() const { return ExitCode; }
+
+  // enableProfiling() - Turn profiling on, clear stats?
+  void enableProfiling() { Profile = true; }
+
+  void initializeExecutionEngine();
+  void handleUserInput();
+
+  // User Interation Methods...
+  bool callMethod(const string &Name);      // return true on failure
+  void setBreakpoint(const string &Name);
+  void printValue(const string &Name);
+  void printValue(const Type *Ty, GenericValue V);
+
+
+  void list();             // Do the 'list' command
+  void printStackTrace();  // Do the 'backtrace' command
+
+  // Code execution methods...
+  void callMethod(Method *Meth, ExecutionContext *SF = 0);
+  bool executeInstruction(); // Execute one instruction...
+
+  void stepInstruction();  // Do the 'step' command
+  void nextInstruction();  // Do the 'next' command
+  void run();              // Do the 'run' command
+  void finish();           // Do the 'finish' command
+
+  // Opcode Implementations
+  void executeCallInst(CallInst *I, ExecutionContext &SF);
+  void executeRetInst(ReturnInst *I, ExecutionContext &SF);
+  void executeBrInst(BranchInst *I, ExecutionContext &SF);
+
+  // getCurrentMethod - Return the currently executing method
+  inline Method *getCurrentMethod() const {
+    return CurFrame < 0 ? 0 : ECStack[CurFrame].CurMethod;
+  }
+
+  // isStopped - Return true if a program is stopped.  Return false if no
+  // program is running.
+  //
+  inline bool isStopped() const { return !ECStack.empty(); }
+
+private:  // Helper functions
+  // printCurrentInstruction - Print out the instruction that the virtual PC is
+  // at, or fail silently if no program is running.
+  //
+  void printCurrentInstruction();
+
+  // LookupMatchingNames - Search the current method namespace, then the global
+  // namespace looking for values that match the specified name.  Return ALL
+  // matches to that name.  This is obviously slow, and should only be used for
+  // user interaction.
+  //
+  vector<Value*> LookupMatchingNames(const string &Name);
+
+  // ChooseOneOption - Prompt the user to choose among the specified options to
+  // pick one value.  If no options are provided, emit an error.  If a single 
+  // option is provided, just return that option.
+  //
+  Value *ChooseOneOption(const string &Name, const vector<Value*> &Opts);
+};
+
+#endif
diff --git a/lib/ExecutionEngine/Interpreter/Support.cpp b/lib/ExecutionEngine/Interpreter/Support.cpp
new file mode 100644
index 0000000..a619304
--- /dev/null
+++ b/lib/ExecutionEngine/Interpreter/Support.cpp
@@ -0,0 +1,78 @@
+//===-- Support.cpp - Support routines for interpreter --------------------===//
+// 
+//  This file contains support routines for the interpreter core.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Interpreter.h"
+#include "llvm/SymbolTable.h"
+#include "llvm/Assembly/Writer.h"
+
+//===----------------------------------------------------------------------===//
+//
+// LookupMatchingNames helper - Search a symbol table for values matching Name.
+//
+static inline void LookupMatchingNames(const string &Name, SymTabValue &STV,
+				       vector<Value*> &Results) {
+  SymbolTable *SymTab = STV.getSymbolTable();
+  if (SymTab == 0) return;                         // No symbolic values :(
+
+  // Loop over all of the type planes in the symbol table...
+  for (SymbolTable::iterator I = SymTab->begin(), E = SymTab->end();
+       I != E; ++I) {
+    SymbolTable::VarMap &Plane = I->second;
+    
+    // Search the symbol table plane for this name...
+    SymbolTable::VarMap::iterator Val = Plane.find(Name);
+    if (Val != Plane.end())
+      Results.push_back(Val->second);                    // Found a name match!
+  }
+}
+
+// LookupMatchingNames - Search the current method namespace, then the global
+// namespace looking for values that match the specified name.  Return ALL
+// matches to that name.  This is obviously slow, and should only be used for
+// user interaction.
+//
+vector<Value*> Interpreter::LookupMatchingNames(const string &Name) {
+  vector<Value*> Results;
+  Method *CurMeth = getCurrentMethod();
+  
+  if (CurMeth) ::LookupMatchingNames(Name, *CurMeth, Results);
+  if (CurMod ) ::LookupMatchingNames(Name, *CurMod , Results);
+  return Results;
+}
+
+// ChooseOneOption - Prompt the user to choose among the specified options to
+// pick one value.  If no options are provided, emit an error.  If a single 
+// option is provided, just return that option.
+//
+Value *Interpreter::ChooseOneOption(const string &Name,
+				    const vector<Value*> &Opts) {
+  switch (Opts.size()) {
+  case 1: return Opts[0];
+  case 0: 
+    cout << "Error: no entities named '" << Name << "' found!\n";
+    return 0;
+  default: break;  // Must prompt user...
+  }
+
+  cout << "Multiple entities named '" << Name << "' found!  Please choose:\n";
+  cout << "  0. Cancel operation\n";
+  for (unsigned i = 0; i < Opts.size(); ++i) {
+    cout << "  " << (i+1) << ".";
+    WriteAsOperand(cout, Opts[i]) << endl;
+  }
+
+  unsigned Option;
+  do {
+    cout << "lli> " << flush;
+    cin >> Option;
+    if (Option > Opts.size())
+      cout << "Invalid selection: Please choose from 0 to " << Opts.size()
+	   << endl;
+  } while (Option > Opts.size());
+
+  if (Option == 0) return 0;
+  return Opts[Option-1];
+}
diff --git a/lib/ExecutionEngine/Interpreter/UserInput.cpp b/lib/ExecutionEngine/Interpreter/UserInput.cpp
new file mode 100644
index 0000000..cfa74f1
--- /dev/null
+++ b/lib/ExecutionEngine/Interpreter/UserInput.cpp
@@ -0,0 +1,147 @@
+//===-- UserInput.cpp - Interpreter Input Loop support --------------------===//
+// 
+//  This file implements the interpreter Input I/O loop.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Interpreter.h"
+#include "llvm/Assembly/Writer.h"
+#include <algorithm>
+
+enum CommandID {
+  Quit, Help,                           // Basics
+  Print, List, StackTrace, Up, Down,    // Inspection
+  Next, Step, Run, Finish, Call,        // Control flow changes
+  Break, Watch,                         // Debugging
+  Load, Flush
+};
+
+// CommandTable - Build a lookup table for the commands available to the user...
+static struct CommandTableElement {
+  const char *Name;
+  enum CommandID CID;
+
+  inline bool operator<(const CommandTableElement &E) const {
+    return string(Name) < string(E.Name);
+  }
+  inline bool operator==(const string &S) const { 
+    return string(Name) == S;
+  }
+} CommandTable[] = {
+  { "quit"     , Quit       }, { "q", Quit }, { "", Quit }, // Empty str = eof
+  { "help"     , Help       }, { "h", Help },
+
+  { "print"    , Print      }, { "p", Print },
+  { "list"     , List       },
+  { "backtrace", StackTrace }, { "bt", StackTrace }, { "where", StackTrace },
+  { "up"       , Up         },
+  { "down"     , Down       },
+
+  { "next"     , Next       }, { "n", Next },
+  { "step"     , Step       }, { "s", Step },
+  { "run"      , Run        },
+  { "finish"   , Finish     },
+  { "call"     , Call       },
+
+  { "break"    , Break      }, { "b", Break },
+  { "watch"    , Watch      },
+
+  { "load"     , Load       },
+  { "flush"    , Flush      },
+};
+static CommandTableElement *CommandTableEnd = 
+   CommandTable+sizeof(CommandTable)/sizeof(CommandTable[0]);
+
+
+//===----------------------------------------------------------------------===//
+// handleUserInput - Enter the input loop for the interpreter.  This function
+// returns when the user quits the interpreter.
+//
+void Interpreter::handleUserInput() {
+  bool UserQuit = false;
+
+  // Sort the table...
+  sort(CommandTable, CommandTableEnd);
+
+  // Print the instruction that we are stopped at...
+  printCurrentInstruction();
+
+  do {
+    string Command;
+    cout << "lli> " << flush;
+    cin >> Command;
+
+    CommandTableElement *E = find(CommandTable, CommandTableEnd, Command);
+
+    if (E == CommandTableEnd) {
+      cout << "Error: '" << Command << "' not recognized!\n";
+      continue;
+    }
+
+    switch (E->CID) {
+    case Quit:       UserQuit = true;   break;
+    case Print:
+      cin >> Command;
+      printValue(Command);
+      break;
+    case List:       list();            break;
+    case StackTrace: printStackTrace(); break;
+    case Up: 
+      if (CurFrame > 0) --CurFrame;
+      else cout << "Error: Already at root of stack!\n";
+      break;
+    case Down:
+      if ((unsigned)CurFrame < ECStack.size()-1) ++CurFrame;
+      else cout << "Error: Already at bottom of stack!\n";
+      break;
+    case Next:       nextInstruction(); break;
+    case Step:       stepInstruction(); break;
+    case Run:        run();             break;
+    case Finish:     finish();          break;
+    case Call:
+      cin >> Command;
+      callMethod(Command);    // Enter the specified method
+      finish();               // Run until it's complete
+      break;
+
+    default:
+      cout << "Command '" << Command << "' unimplemented!\n";
+      break;
+    }
+
+  } while (!UserQuit);
+}
+
+
+//===----------------------------------------------------------------------===//
+// setBreakpoint - Enable a breakpoint at the specified location
+//
+void Interpreter::setBreakpoint(const string &Name) {
+  Value *PickedVal = ChooseOneOption(Name, LookupMatchingNames(Name));
+  // TODO: Set a breakpoint on PickedVal
+}
+
+//===----------------------------------------------------------------------===//
+// callMethod - Enter the specified method...
+//
+bool Interpreter::callMethod(const string &Name) {
+  vector<Value*> Options = LookupMatchingNames(Name);
+
+  for (unsigned i = 0; i < Options.size(); ++i) { // Remove nonmethod matches...
+    if (!Options[i]->isMethod()) {
+      Options.erase(Options.begin()+i);
+      --i;
+    }
+  }
+
+  Value *PickedMeth = ChooseOneOption(Name, Options);
+  if (PickedMeth == 0)
+    return true;
+
+  callMethod(PickedMeth->castMethodAsserting());  // Start executing it...
+
+  // Reset the current frame location to the top of stack
+  CurFrame = ECStack.size()-1;
+
+  return false;
+}
diff --git a/lib/ExecutionEngine/Makefile b/lib/ExecutionEngine/Makefile
new file mode 100644
index 0000000..522665f
--- /dev/null
+++ b/lib/ExecutionEngine/Makefile
@@ -0,0 +1,11 @@
+LEVEL = ../..
+include $(LEVEL)/Makefile.common
+
+all:: lli
+clean::	
+	rm -f lli
+
+lli : $(ObjectsG)
+	$(LinkG) -o $@ $(ObjectsG) \
+		-lopt -lbcreader -lbcwriter \
+		-lvmcore -lasmwriter -lanalysis -lsupport
diff --git a/tools/lli/Makefile b/tools/lli/Makefile
new file mode 100644
index 0000000..522665f
--- /dev/null
+++ b/tools/lli/Makefile
@@ -0,0 +1,11 @@
+LEVEL = ../..
+include $(LEVEL)/Makefile.common
+
+all:: lli
+clean::	
+	rm -f lli
+
+lli : $(ObjectsG)
+	$(LinkG) -o $@ $(ObjectsG) \
+		-lopt -lbcreader -lbcwriter \
+		-lvmcore -lasmwriter -lanalysis -lsupport
diff --git a/tools/lli/lli.cpp b/tools/lli/lli.cpp
new file mode 100644
index 0000000..9611e0c
--- /dev/null
+++ b/tools/lli/lli.cpp
@@ -0,0 +1,67 @@
+//===----------------------------------------------------------------------===//
+// LLVM INTERPRETER/DEBUGGER/PROFILER UTILITY 
+//
+// This utility is an interactive frontend to almost all other LLVM
+// functionality.  It may be used as an interpreter to run code, a debugger to
+// find problems, or a profiler to analyze execution frequencies.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Interpreter.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Bytecode/Reader.h"
+
+cl::String InputFilename(""       , "Input filename", cl::NoFlags, "-");
+cl::String MainFunction ("f"      , "Function to execute", cl::NoFlags, "main");
+cl::Flag   DebugMode    ("debug"  , "Start program in debugger");
+cl::Alias  DebugModeA   ("d"      , "Alias for -debug", cl::NoFlags, DebugMode);
+cl::Flag   ProfileMode  ("profile", "Enable Profiling [unimp]");
+
+//===----------------------------------------------------------------------===//
+// Interpreter ctor - Initialize stuff
+//
+Interpreter::Interpreter() : ExitCode(0), Profile(ProfileMode), CurFrame(-1) {
+  CurMod = ParseBytecodeFile(InputFilename);
+  if (CurMod == 0) {
+    cout << "Error parsing '" << InputFilename << "': No module loaded.\n";
+  }
+
+  // Initialize the "backend"
+  initializeExecutionEngine();
+}
+
+//===----------------------------------------------------------------------===//
+// main Driver function
+//
+int main(int argc, char** argv) {
+  cl::ParseCommandLineOptions(argc, argv, " llvm interpreter\n");
+
+  // Create the interpreter...
+  Interpreter I;
+
+  // Handle alternate names of the program.  If started as llp, enable profiling
+  // if started as ldb, enable debugging...
+  //
+  if (argv[0] == "ldb")       // TODO: Obviously incorrect, but you get the idea
+    DebugMode = true;
+  else if (argv[0] == "llp")
+    ProfileMode = true;
+
+  // If running with the profiler, enable it now...
+  if (ProfileMode) I.enableProfiling();
+
+  // Start interpreter into the main function...
+  //
+  if (!I.callMethod(MainFunction) && !DebugMode) {
+    // If not in debug mode and if the call succeeded, run the code now...
+    I.run();
+  }
+
+  // If debug mode, allow the user to interact... also, if the user pressed 
+  // ctrl-c or execution hit an error, enter the event loop...
+  if (DebugMode || I.isStopped())
+    I.handleUserInput();
+
+  // Return the status code of the program executed...
+  return I.getExitCode();
+}