Initial checkin of interpreter
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@361 91177308-0d34-0410-b5e6-96231b3b80d8
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;
+ }
+}