From 92101acd7fd44fd467fbeb974ae6c042289c74f9 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 23 Aug 2001 17:05:04 +0000 Subject: [PATCH] Initial checkin of interpreter git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@361 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/ExecutionEngine/Interpreter/Execution.cpp | 598 ++++++++++++++++++ .../Interpreter/ExecutionAnnotations.h | 91 +++ lib/ExecutionEngine/Interpreter/Interpreter.h | 129 ++++ lib/ExecutionEngine/Interpreter/Support.cpp | 78 +++ lib/ExecutionEngine/Interpreter/UserInput.cpp | 147 +++++ lib/ExecutionEngine/Makefile | 11 + tools/lli/Makefile | 11 + tools/lli/lli.cpp | 67 ++ 8 files changed, 1132 insertions(+) create mode 100644 lib/ExecutionEngine/Interpreter/Execution.cpp create mode 100644 lib/ExecutionEngine/Interpreter/ExecutionAnnotations.h create mode 100644 lib/ExecutionEngine/Interpreter/Interpreter.h create mode 100644 lib/ExecutionEngine/Interpreter/Support.cpp create mode 100644 lib/ExecutionEngine/Interpreter/UserInput.cpp create mode 100644 lib/ExecutionEngine/Makefile create mode 100644 tools/lli/Makefile create mode 100644 tools/lli/lli.cpp diff --git a/lib/ExecutionEngine/Interpreter/Execution.cpp b/lib/ExecutionEngine/Interpreter/Execution.cpp new file mode 100644 index 00000000000..92d8b663cc5 --- /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 00000000000..931de6a4998 --- /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 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 00000000000..9ff83365dbe --- /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 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 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 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 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 &Opts); +}; + +#endif diff --git a/lib/ExecutionEngine/Interpreter/Support.cpp b/lib/ExecutionEngine/Interpreter/Support.cpp new file mode 100644 index 00000000000..a619304c62b --- /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 &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 Interpreter::LookupMatchingNames(const string &Name) { + vector 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 &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 00000000000..cfa74f1ffa5 --- /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 + +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 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 00000000000..522665f8bef --- /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 00000000000..522665f8bef --- /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 00000000000..9611e0ca85f --- /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(); +} -- 2.34.1