diff options
| author | Dimitry Andric <dim@FreeBSD.org> | 2015-12-30 11:46:15 +0000 |
|---|---|---|
| committer | Dimitry Andric <dim@FreeBSD.org> | 2015-12-30 11:46:15 +0000 |
| commit | dd58ef019b700900793a1eb48b52123db01b654e (patch) | |
| tree | fcfbb4df56a744f4ddc6122c50521dd3f1c5e196 /docs/tutorial | |
| parent | 2fe5752e3a7c345cdb59e869278d36af33c13fa4 (diff) | |
Notes
Diffstat (limited to 'docs/tutorial')
| -rw-r--r-- | docs/tutorial/LangImpl1.rst | 25 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl2.rst | 185 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl3.rst | 271 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl4.rst | 356 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl5.rst | 201 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl6.rst | 118 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl7.rst | 117 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl8.rst | 43 | ||||
| -rw-r--r-- | docs/tutorial/LangImpl9.rst | 2 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl1.rst | 4 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl2.rst | 6 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl3.rst | 24 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl4.rst | 2 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl5.rst | 2 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl6.rst | 4 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl7.rst | 8 | ||||
| -rw-r--r-- | docs/tutorial/OCamlLangImpl8.rst | 2 |
17 files changed, 813 insertions, 557 deletions
diff --git a/docs/tutorial/LangImpl1.rst b/docs/tutorial/LangImpl1.rst index f4b019166af3..b04cde10274e 100644 --- a/docs/tutorial/LangImpl1.rst +++ b/docs/tutorial/LangImpl1.rst @@ -25,7 +25,7 @@ It is useful to point out ahead of time that this tutorial is really about teaching compiler techniques and LLVM specifically, *not* about teaching modern and sane software engineering principles. In practice, this means that we'll take a number of shortcuts to simplify the -exposition. For example, the code leaks memory, uses global variables +exposition. For example, the code uses global variables all over the place, doesn't use nice design patterns like `visitors <http://en.wikipedia.org/wiki/Visitor_pattern>`_, etc... but it is very simple. If you dig in and use the code as a basis for future @@ -146,7 +146,7 @@ useful for mutually recursive functions). For example: A more interesting example is included in Chapter 6 where we write a little Kaleidoscope application that `displays a Mandelbrot -Set <LangImpl6.html#example>`_ at various levels of magnification. +Set <LangImpl6.html#kicking-the-tires>`_ at various levels of magnification. Lets dive into the implementation of this language! @@ -169,14 +169,16 @@ numeric value of a number). First, we define the possibilities: tok_eof = -1, // commands - tok_def = -2, tok_extern = -3, + tok_def = -2, + tok_extern = -3, // primary - tok_identifier = -4, tok_number = -5, + tok_identifier = -4, + tok_number = -5, }; - static std::string IdentifierStr; // Filled in if tok_identifier - static double NumVal; // Filled in if tok_number + static std::string IdentifierStr; // Filled in if tok_identifier + static double NumVal; // Filled in if tok_number Each token returned by our lexer will either be one of the Token enum values or it will be an 'unknown' character like '+', which is returned @@ -217,8 +219,10 @@ loop: while (isalnum((LastChar = getchar()))) IdentifierStr += LastChar; - if (IdentifierStr == "def") return tok_def; - if (IdentifierStr == "extern") return tok_extern; + if (IdentifierStr == "def") + return tok_def; + if (IdentifierStr == "extern") + return tok_extern; return tok_identifier; } @@ -250,7 +254,8 @@ extend it :). Next we handle comments: if (LastChar == '#') { // Comment until end of line. - do LastChar = getchar(); + do + LastChar = getchar(); while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if (LastChar != EOF) @@ -275,7 +280,7 @@ file. These are handled with this code: } With this, we have the complete lexer for the basic Kaleidoscope -language (the `full code listing <LangImpl2.html#code>`_ for the Lexer +language (the `full code listing <LangImpl2.html#full-code-listing>`_ for the Lexer is available in the `next chapter <LangImpl2.html>`_ of the tutorial). Next we'll `build a simple parser that uses this to build an Abstract Syntax Tree <LangImpl2.html>`_. When we have that, we'll include a diff --git a/docs/tutorial/LangImpl2.rst b/docs/tutorial/LangImpl2.rst index 06b18ff6c239..dab60172b988 100644 --- a/docs/tutorial/LangImpl2.rst +++ b/docs/tutorial/LangImpl2.rst @@ -44,8 +44,9 @@ We'll start with expressions first: /// NumberExprAST - Expression class for numeric literals like "1.0". class NumberExprAST : public ExprAST { double Val; + public: - NumberExprAST(double val) : Val(val) {} + NumberExprAST(double Val) : Val(Val) {} }; The code above shows the definition of the base ExprAST class and one @@ -65,26 +66,31 @@ language: /// VariableExprAST - Expression class for referencing a variable, like "a". class VariableExprAST : public ExprAST { std::string Name; + public: - VariableExprAST(const std::string &name) : Name(name) {} + VariableExprAST(const std::string &Name) : Name(Name) {} }; /// BinaryExprAST - Expression class for a binary operator. class BinaryExprAST : public ExprAST { char Op; - ExprAST *LHS, *RHS; + std::unique_ptr<ExprAST> LHS, RHS; + public: - BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) - : Op(op), LHS(lhs), RHS(rhs) {} + BinaryExprAST(char op, std::unique_ptr<ExprAST> LHS, + std::unique_ptr<ExprAST> RHS) + : Op(op), LHS(std::move(LHS)), RHS(std::move(RHS)) {} }; /// CallExprAST - Expression class for function calls. class CallExprAST : public ExprAST { std::string Callee; - std::vector<ExprAST*> Args; + std::vector<std::unique_ptr<ExprAST>> Args; + public: - CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) - : Callee(callee), Args(args) {} + CallExprAST(const std::string &Callee, + std::vector<std::unique_ptr<ExprAST>> Args) + : Callee(Callee), Args(std::move(Args)) {} }; This is all (intentionally) rather straight-forward: variables capture @@ -109,18 +115,21 @@ way to talk about functions themselves: class PrototypeAST { std::string Name; std::vector<std::string> Args; + public: - PrototypeAST(const std::string &name, const std::vector<std::string> &args) - : Name(name), Args(args) {} + PrototypeAST(const std::string &name, std::vector<std::string> Args) + : Name(name), Args(std::move(Args)) {} }; /// FunctionAST - This class represents a function definition itself. class FunctionAST { - PrototypeAST *Proto; - ExprAST *Body; + std::unique_ptr<PrototypeAST> Proto; + std::unique_ptr<ExprAST> Body; + public: - FunctionAST(PrototypeAST *proto, ExprAST *body) - : Proto(proto), Body(body) {} + FunctionAST(std::unique_ptr<PrototypeAST> Proto, + std::unique_ptr<ExprAST> Body) + : Proto(std::move(Proto)), Body(std::move(Body)) {} }; In Kaleidoscope, functions are typed with just a count of their @@ -142,9 +151,10 @@ be generated with calls like this: .. code-block:: c++ - ExprAST *X = new VariableExprAST("x"); - ExprAST *Y = new VariableExprAST("y"); - ExprAST *Result = new BinaryExprAST('+', X, Y); + auto LHS = llvm::make_unique<VariableExprAST>("x"); + auto RHS = llvm::make_unique<VariableExprAST>("y"); + auto Result = std::make_unique<BinaryExprAST>('+', std::move(LHS), + std::move(RHS)); In order to do this, we'll start by defining some basic helper routines: @@ -167,9 +177,14 @@ be parsed. /// Error* - These are little helper functions for error handling. - ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} - PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } - FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } + std::unique_ptr<ExprAST> Error(const char *Str) { + fprintf(stderr, "Error: %s\n", Str); + return nullptr; + } + std::unique_ptr<PrototypeAST> ErrorP(const char *Str) { + Error(Str); + return nullptr; + } The ``Error`` routines are simple helper routines that our parser will use to handle errors. The error recovery in our parser will not be the @@ -190,10 +205,10 @@ which parses that production. For numeric literals, we have: .. code-block:: c++ /// numberexpr ::= number - static ExprAST *ParseNumberExpr() { - ExprAST *Result = new NumberExprAST(NumVal); + static std::unique_ptr<ExprAST> ParseNumberExpr() { + auto Result = llvm::make_unique<NumberExprAST>(NumVal); getNextToken(); // consume the number - return Result; + return std::move(Result); } This routine is very simple: it expects to be called when the current @@ -211,14 +226,15 @@ the parenthesis operator is defined like this: .. code-block:: c++ /// parenexpr ::= '(' expression ')' - static ExprAST *ParseParenExpr() { - getNextToken(); // eat (. - ExprAST *V = ParseExpression(); - if (!V) return 0; + static std::unique_ptr<ExprAST> ParseParenExpr() { + getNextToken(); // eat (. + auto V = ParseExpression(); + if (!V) + return nullptr; if (CurTok != ')') return Error("expected ')'"); - getNextToken(); // eat ). + getNextToken(); // eat ). return V; } @@ -250,24 +266,26 @@ function calls: /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' - static ExprAST *ParseIdentifierExpr() { + static std::unique_ptr<ExprAST> ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); // eat identifier. if (CurTok != '(') // Simple variable ref. - return new VariableExprAST(IdName); + return llvm::make_unique<VariableExprAST>(IdName); // Call. getNextToken(); // eat ( - std::vector<ExprAST*> Args; + std::vector<std::unique_ptr<ExprAST>> Args; if (CurTok != ')') { while (1) { - ExprAST *Arg = ParseExpression(); - if (!Arg) return 0; - Args.push_back(Arg); + if (auto Arg = ParseExpression()) + Args.push_back(std::move(Arg)); + else + return nullptr; - if (CurTok == ')') break; + if (CurTok == ')') + break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); @@ -278,7 +296,7 @@ function calls: // Eat the ')'. getNextToken(); - return new CallExprAST(IdName, Args); + return llvm::make_unique<CallExprAST>(IdName, std::move(Args)); } This routine follows the same style as the other routines. (It expects @@ -294,7 +312,7 @@ Now that we have all of our simple expression-parsing logic in place, we can define a helper function to wrap it together into one entry point. We call this class of expressions "primary" expressions, for reasons that will become more clear `later in the -tutorial <LangImpl6.html#unary>`_. In order to parse an arbitrary +tutorial <LangImpl6.html#user-defined-unary-operators>`_. In order to parse an arbitrary primary expression, we need to determine what sort of expression it is: .. code-block:: c++ @@ -303,12 +321,16 @@ primary expression, we need to determine what sort of expression it is: /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr - static ExprAST *ParsePrimary() { + static std::unique_ptr<ExprAST> ParsePrimary() { switch (CurTok) { - default: return Error("unknown token when expecting an expression"); - case tok_identifier: return ParseIdentifierExpr(); - case tok_number: return ParseNumberExpr(); - case '(': return ParseParenExpr(); + default: + return Error("unknown token when expecting an expression"); + case tok_identifier: + return ParseIdentifierExpr(); + case tok_number: + return ParseNumberExpr(); + case '(': + return ParseParenExpr(); } } @@ -374,7 +396,7 @@ would be easy enough to eliminate the map and do the comparisons in the With the helper above defined, we can now start parsing binary expressions. The basic idea of operator precedence parsing is to break down an expression with potentially ambiguous binary operators into -pieces. Consider ,for example, the expression "a+b+(c+d)\*e\*f+g". +pieces. Consider, for example, the expression "a+b+(c+d)\*e\*f+g". Operator precedence parsing considers this as a stream of primary expressions separated by binary operators. As such, it will first parse the leading primary expression "a", then it will see the pairs [+, b] @@ -390,11 +412,12 @@ a sequence of [binop,primaryexpr] pairs: /// expression /// ::= primary binoprhs /// - static ExprAST *ParseExpression() { - ExprAST *LHS = ParsePrimary(); - if (!LHS) return 0; + static std::unique_ptr<ExprAST> ParseExpression() { + auto LHS = ParsePrimary(); + if (!LHS) + return nullptr; - return ParseBinOpRHS(0, LHS); + return ParseBinOpRHS(0, std::move(LHS)); } ``ParseBinOpRHS`` is the function that parses the sequence of pairs for @@ -416,7 +439,8 @@ starts with: /// binoprhs /// ::= ('+' primary)* - static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { + static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec, + std::unique_ptr<ExprAST> LHS) { // If this is a binop, find its precedence. while (1) { int TokPrec = GetTokPrecedence(); @@ -440,8 +464,9 @@ expression: getNextToken(); // eat binop // Parse the primary expression after the binary operator. - ExprAST *RHS = ParsePrimary(); - if (!RHS) return 0; + auto RHS = ParsePrimary(); + if (!RHS) + return nullptr; As such, this code eats (and remembers) the binary operator and then parses the primary expression that follows. This builds up the whole @@ -474,7 +499,8 @@ then continue parsing: } // Merge LHS/RHS. - LHS = new BinaryExprAST(BinOp, LHS, RHS); + LHS = llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS), + std::move(RHS)); } // loop around to the top of the while loop. } @@ -498,11 +524,13 @@ above two blocks duplicated for context): // the pending operator take RHS as its LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) { - RHS = ParseBinOpRHS(TokPrec+1, RHS); - if (RHS == 0) return 0; + RHS = ParseBinOpRHS(TokPrec+1, std::move(RHS)); + if (!RHS) + return nullptr; } // Merge LHS/RHS. - LHS = new BinaryExprAST(BinOp, LHS, RHS); + LHS = llvm::make_unique<BinaryExprAST>(BinOp, std::move(LHS), + std::move(RHS)); } // loop around to the top of the while loop. } @@ -541,7 +569,7 @@ expressions): /// prototype /// ::= id '(' id* ')' - static PrototypeAST *ParsePrototype() { + static std::unique_ptr<PrototypeAST> ParsePrototype() { if (CurTok != tok_identifier) return ErrorP("Expected function name in prototype"); @@ -561,7 +589,7 @@ expressions): // success. getNextToken(); // eat ')'. - return new PrototypeAST(FnName, ArgNames); + return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames)); } Given this, a function definition is very simple, just a prototype plus @@ -570,14 +598,14 @@ an expression to implement the body: .. code-block:: c++ /// definition ::= 'def' prototype expression - static FunctionAST *ParseDefinition() { + static std::unique_ptr<FunctionAST> ParseDefinition() { getNextToken(); // eat def. - PrototypeAST *Proto = ParsePrototype(); - if (Proto == 0) return 0; + auto Proto = ParsePrototype(); + if (!Proto) return nullptr; - if (ExprAST *E = ParseExpression()) - return new FunctionAST(Proto, E); - return 0; + if (auto E = ParseExpression()) + return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); + return nullptr; } In addition, we support 'extern' to declare functions like 'sin' and @@ -587,7 +615,7 @@ In addition, we support 'extern' to declare functions like 'sin' and .. code-block:: c++ /// external ::= 'extern' prototype - static PrototypeAST *ParseExtern() { + static std::unique_ptr<PrototypeAST> ParseExtern() { getNextToken(); // eat extern. return ParsePrototype(); } @@ -599,13 +627,13 @@ nullary (zero argument) functions for them: .. code-block:: c++ /// toplevelexpr ::= expression - static FunctionAST *ParseTopLevelExpr() { - if (ExprAST *E = ParseExpression()) { + static std::unique_ptr<FunctionAST> ParseTopLevelExpr() { + if (auto E = ParseExpression()) { // Make an anonymous proto. - PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); - return new FunctionAST(Proto, E); + auto Proto = llvm::make_unique<PrototypeAST>("", std::vector<std::string>()); + return llvm::make_unique<FunctionAST>(std::move(Proto), std::move(E)); } - return 0; + return nullptr; } Now that we have all the pieces, let's build a little driver that will @@ -616,7 +644,7 @@ The Driver The driver for this simply invokes all of the parsing pieces with a top-level dispatch loop. There isn't much interesting here, so I'll just -include the top-level loop. See `below <#code>`_ for full code in the +include the top-level loop. See `below <#full-code-listing>`_ for full code in the "Top-Level Parsing" section. .. code-block:: c++ @@ -626,11 +654,20 @@ include the top-level loop. See `below <#code>`_ for full code in the while (1) { fprintf(stderr, "ready> "); switch (CurTok) { - case tok_eof: return; - case ';': getNextToken(); break; // ignore top-level semicolons. - case tok_def: HandleDefinition(); break; - case tok_extern: HandleExtern(); break; - default: HandleTopLevelExpression(); break; + case tok_eof: + return; + case ';': // ignore top-level semicolons. + getNextToken(); + break; + case tok_def: + HandleDefinition(); + break; + case tok_extern: + HandleExtern(); + break; + default: + HandleTopLevelExpression(); + break; } } } diff --git a/docs/tutorial/LangImpl3.rst b/docs/tutorial/LangImpl3.rst index 26ba4aae956c..83ad35f14aee 100644 --- a/docs/tutorial/LangImpl3.rst +++ b/docs/tutorial/LangImpl3.rst @@ -15,8 +15,8 @@ LLVM IR. This will teach you a little bit about how LLVM does things, as well as demonstrate how easy it is to use. It's much more work to build a lexer and parser than it is to generate LLVM IR code. :) -**Please note**: the code in this chapter and later require LLVM 2.2 or -later. LLVM 2.1 and before will not work with it. Also note that you +**Please note**: the code in this chapter and later require LLVM 3.7 or +later. LLVM 3.6 and before will not work with it. Also note that you need to use a version of this tutorial that matches your LLVM release: If you are using an official LLVM release, use the version of the documentation included with your release or on the `llvm.org releases @@ -35,19 +35,20 @@ class: class ExprAST { public: virtual ~ExprAST() {} - virtual Value *Codegen() = 0; + virtual Value *codegen() = 0; }; /// NumberExprAST - Expression class for numeric literals like "1.0". class NumberExprAST : public ExprAST { double Val; + public: - NumberExprAST(double val) : Val(val) {} - virtual Value *Codegen(); + NumberExprAST(double Val) : Val(Val) {} + virtual Value *codegen(); }; ... -The Codegen() method says to emit IR for that AST node along with all +The codegen() method says to emit IR for that AST node along with all the things it depends on, and they all return an LLVM Value object. "Value" is the class used to represent a "`Static Single Assignment (SSA) <http://en.wikipedia.org/wiki/Static_single_assignment_form>`_ @@ -72,16 +73,20 @@ parser, which will be used to report errors found during code generation .. code-block:: c++ - Value *ErrorV(const char *Str) { Error(Str); return 0; } - - static Module *TheModule; + static std::unique_ptr<Module> *TheModule; static IRBuilder<> Builder(getGlobalContext()); static std::map<std::string, Value*> NamedValues; + Value *ErrorV(const char *Str) { + Error(Str); + return nullptr; + } + The static variables will be used during code generation. ``TheModule`` -is the LLVM construct that contains all of the functions and global -variables in a chunk of code. In many ways, it is the top-level -structure that the LLVM IR uses to contain code. +is an LLVM construct that contains functions and global variables. In many +ways, it is the top-level structure that the LLVM IR uses to contain code. +It will own the memory for all of the IR that we generate, which is why +the codegen() method returns a raw Value\*, rather than a unique_ptr<Value>. The ``Builder`` object is a helper object that makes it easy to generate LLVM instructions. Instances of the @@ -110,7 +115,7 @@ First we'll do numeric literals: .. code-block:: c++ - Value *NumberExprAST::Codegen() { + Value *NumberExprAST::codegen() { return ConstantFP::get(getGlobalContext(), APFloat(Val)); } @@ -124,10 +129,12 @@ are all uniqued together and shared. For this reason, the API uses the .. code-block:: c++ - Value *VariableExprAST::Codegen() { + Value *VariableExprAST::codegen() { // Look this variable up in the function. Value *V = NamedValues[Name]; - return V ? V : ErrorV("Unknown variable name"); + if (!V) + ErrorV("Unknown variable name"); + return V; } References to variables are also quite simple using LLVM. In the simple @@ -137,26 +144,31 @@ values that can be in the ``NamedValues`` map are function arguments. This code simply checks to see that the specified name is in the map (if not, an unknown variable is being referenced) and returns the value for it. In future chapters, we'll add support for `loop induction -variables <LangImpl5.html#for>`_ in the symbol table, and for `local -variables <LangImpl7.html#localvars>`_. +variables <LangImpl5.html#for-loop-expression>`_ in the symbol table, and for `local +variables <LangImpl7.html#user-defined-local-variables>`_. .. code-block:: c++ - Value *BinaryExprAST::Codegen() { - Value *L = LHS->Codegen(); - Value *R = RHS->Codegen(); - if (L == 0 || R == 0) return 0; + Value *BinaryExprAST::codegen() { + Value *L = LHS->codegen(); + Value *R = RHS->codegen(); + if (!L || !R) + return nullptr; switch (Op) { - case '+': return Builder.CreateFAdd(L, R, "addtmp"); - case '-': return Builder.CreateFSub(L, R, "subtmp"); - case '*': return Builder.CreateFMul(L, R, "multmp"); + case '+': + return Builder.CreateFAdd(L, R, "addtmp"); + case '-': + return Builder.CreateFSub(L, R, "subtmp"); + case '*': + return Builder.CreateFMul(L, R, "multmp"); case '<': L = Builder.CreateFCmpULT(L, R, "cmptmp"); // Convert bool 0/1 to double 0.0 or 1.0 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp"); - default: return ErrorV("invalid binary operator"); + default: + return ErrorV("invalid binary operator"); } } @@ -178,55 +190,55 @@ automatically provide each one with an increasing, unique numeric suffix. Local value names for instructions are purely optional, but it makes it much easier to read the IR dumps. -`LLVM instructions <../LangRef.html#instref>`_ are constrained by strict +`LLVM instructions <../LangRef.html#instruction-reference>`_ are constrained by strict rules: for example, the Left and Right operators of an `add -instruction <../LangRef.html#i_add>`_ must have the same type, and the +instruction <../LangRef.html#add-instruction>`_ must have the same type, and the result type of the add must match the operand types. Because all values in Kaleidoscope are doubles, this makes for very simple code for add, sub and mul. On the other hand, LLVM specifies that the `fcmp -instruction <../LangRef.html#i_fcmp>`_ always returns an 'i1' value (a +instruction <../LangRef.html#fcmp-instruction>`_ always returns an 'i1' value (a one bit integer). The problem with this is that Kaleidoscope wants the value to be a 0.0 or 1.0 value. In order to get these semantics, we combine the fcmp instruction with a `uitofp -instruction <../LangRef.html#i_uitofp>`_. This instruction converts its +instruction <../LangRef.html#uitofp-to-instruction>`_. This instruction converts its input integer into a floating point value by treating the input as an unsigned value. In contrast, if we used the `sitofp -instruction <../LangRef.html#i_sitofp>`_, the Kaleidoscope '<' operator +instruction <../LangRef.html#sitofp-to-instruction>`_, the Kaleidoscope '<' operator would return 0.0 and -1.0, depending on the input value. .. code-block:: c++ - Value *CallExprAST::Codegen() { + Value *CallExprAST::codegen() { // Look up the name in the global module table. Function *CalleeF = TheModule->getFunction(Callee); - if (CalleeF == 0) + if (!CalleeF) return ErrorV("Unknown function referenced"); // If argument mismatch error. if (CalleeF->arg_size() != Args.size()) return ErrorV("Incorrect # arguments passed"); - std::vector<Value*> ArgsV; + std::vector<Value *> ArgsV; for (unsigned i = 0, e = Args.size(); i != e; ++i) { - ArgsV.push_back(Args[i]->Codegen()); - if (ArgsV.back() == 0) return 0; + ArgsV.push_back(Args[i]->codegen()); + if (!ArgsV.back()) + return nullptr; } return Builder.CreateCall(CalleeF, ArgsV, "calltmp"); } -Code generation for function calls is quite straightforward with LLVM. -The code above initially does a function name lookup in the LLVM -Module's symbol table. Recall that the LLVM Module is the container that -holds all of the functions we are JIT'ing. By giving each function the -same name as what the user specifies, we can use the LLVM symbol table -to resolve function names for us. +Code generation for function calls is quite straightforward with LLVM. The code +above initially does a function name lookup in the LLVM Module's symbol table. +Recall that the LLVM Module is the container that holds the functions we are +JIT'ing. By giving each function the same name as what the user specifies, we +can use the LLVM symbol table to resolve function names for us. Once we have the function to call, we recursively codegen each argument that is to be passed in, and create an LLVM `call -instruction <../LangRef.html#i_call>`_. Note that LLVM uses the native C +instruction <../LangRef.html#call-instruction>`_. Note that LLVM uses the native C calling conventions by default, allowing these calls to also call into standard library functions like "sin" and "cos", with no additional effort. @@ -249,14 +261,15 @@ with: .. code-block:: c++ - Function *PrototypeAST::Codegen() { + Function *PrototypeAST::codegen() { // Make the function type: double(double,double) etc. std::vector<Type*> Doubles(Args.size(), Type::getDoubleTy(getGlobalContext())); - FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), - Doubles, false); + FunctionType *FT = + FunctionType::get(Type::getDoubleTy(getGlobalContext()), Doubles, false); - Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); + Function *F = + Function::Create(FT, Function::ExternalLinkage, Name, TheModule); This code packs a lot of power into a few lines. Note first that this function returns a "Function\*" instead of a "Value\*". Because a @@ -273,118 +286,67 @@ double as a result, and that is not vararg (the false parameter indicates this). Note that Types in LLVM are uniqued just like Constants are, so you don't "new" a type, you "get" it. -The final line above actually creates the function that the prototype -will correspond to. This indicates the type, linkage and name to use, as +The final line above actually creates the IR Function corresponding to +the Prototype. This indicates the type, linkage and name to use, as well as which module to insert into. "`external linkage <../LangRef.html#linkage>`_" means that the function may be defined outside the current module and/or that it is callable by functions outside the module. The Name passed in is the name the user specified: since "``TheModule``" is specified, this name is registered -in "``TheModule``"s symbol table, which is used by the function call -code above. +in "``TheModule``"s symbol table. .. code-block:: c++ - // If F conflicted, there was already something named 'Name'. If it has a - // body, don't allow redefinition or reextern. - if (F->getName() != Name) { - // Delete the one we just made and get the existing one. - F->eraseFromParent(); - F = TheModule->getFunction(Name); + // Set names for all arguments. + unsigned Idx = 0; + for (auto &Arg : F->args()) + Arg.setName(Args[Idx++]); -The Module symbol table works just like the Function symbol table when -it comes to name conflicts: if a new function is created with a name -that was previously added to the symbol table, the new function will get -implicitly renamed when added to the Module. The code above exploits -this fact to determine if there was a previous definition of this -function. + return F; -In Kaleidoscope, I choose to allow redefinitions of functions in two -cases: first, we want to allow 'extern'ing a function more than once, as -long as the prototypes for the externs match (since all arguments have -the same type, we just have to check that the number of arguments -match). Second, we want to allow 'extern'ing a function and then -defining a body for it. This is useful when defining mutually recursive -functions. +Finally, we set the name of each of the function's arguments according to the +names given in the Prototype. This step isn't strictly necessary, but keeping +the names consistent makes the IR more readable, and allows subsequent code to +refer directly to the arguments for their names, rather than having to look up +them up in the Prototype AST. -In order to implement this, the code above first checks to see if there -is a collision on the name of the function. If so, it deletes the -function we just created (by calling ``eraseFromParent``) and then -calling ``getFunction`` to get the existing function with the specified -name. Note that many APIs in LLVM have "erase" forms and "remove" forms. -The "remove" form unlinks the object from its parent (e.g. a Function -from a Module) and returns it. The "erase" form unlinks the object and -then deletes it. +At this point we have a function prototype with no body. This is how LLVM IR +represents function declarations. For extern statements in Kaleidoscope, this +is as far as we need to go. For function definitions however, we need to +codegen and attach a function body. .. code-block:: c++ - // If F already has a body, reject this. - if (!F->empty()) { - ErrorF("redefinition of function"); - return 0; - } + Function *FunctionAST::codegen() { + // First, check for an existing function from a previous 'extern' declaration. + Function *TheFunction = TheModule->getFunction(Proto->getName()); - // If F took a different number of args, reject. - if (F->arg_size() != Args.size()) { - ErrorF("redefinition of function with different # args"); - return 0; - } - } + if (!TheFunction) + TheFunction = Proto->codegen(); -In order to verify the logic above, we first check to see if the -pre-existing function is "empty". In this case, empty means that it has -no basic blocks in it, which means it has no body. If it has no body, it -is a forward declaration. Since we don't allow anything after a full -definition of the function, the code rejects this case. If the previous -reference to a function was an 'extern', we simply verify that the -number of arguments for that definition and this one match up. If not, -we emit an error. + if (!TheFunction) + return nullptr; -.. code-block:: c++ + if (!TheFunction->empty()) + return (Function*)ErrorV("Function cannot be redefined."); - // Set names for all arguments. - unsigned Idx = 0; - for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); - ++AI, ++Idx) { - AI->setName(Args[Idx]); - // Add arguments to variable symbol table. - NamedValues[Args[Idx]] = AI; - } - return F; - } - -The last bit of code for prototypes loops over all of the arguments in -the function, setting the name of the LLVM Argument objects to match, -and registering the arguments in the ``NamedValues`` map for future use -by the ``VariableExprAST`` AST node. Once this is set up, it returns the -Function object to the caller. Note that we don't check for conflicting -argument names here (e.g. "extern foo(a b a)"). Doing so would be very -straight-forward with the mechanics we have already used above. +For function definitions, we start by searching TheModule's symbol table for an +existing version of this function, in case one has already been created using an +'extern' statement. If Module::getFunction returns null then no previous version +exists, so we'll codegen one from the Prototype. In either case, we want to +assert that the function is empty (i.e. has no body yet) before we start. .. code-block:: c++ - Function *FunctionAST::Codegen() { - NamedValues.clear(); - - Function *TheFunction = Proto->Codegen(); - if (TheFunction == 0) - return 0; + // Create a new basic block to start insertion into. + BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); + Builder.SetInsertPoint(BB); -Code generation for function definitions starts out simply enough: we -just codegen the prototype (Proto) and verify that it is ok. We then -clear out the ``NamedValues`` map to make sure that there isn't anything -in it from the last function we compiled. Code generation of the -prototype ensures that there is an LLVM Function object that is ready to -go for us. - -.. code-block:: c++ - - // Create a new basic block to start insertion into. - BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); - Builder.SetInsertPoint(BB); - - if (Value *RetVal = Body->Codegen()) { + // Record the function arguments in the NamedValues map. + NamedValues.clear(); + for (auto &Arg : TheFunction->args()) + NamedValues[Arg.getName()] = &Arg; Now we get to the point where the ``Builder`` is set up. The first line creates a new `basic block <http://en.wikipedia.org/wiki/Basic_block>`_ @@ -396,9 +358,12 @@ Graph <http://en.wikipedia.org/wiki/Control_flow_graph>`_. Since we don't have any control flow, our functions will only contain one block at this point. We'll fix this in `Chapter 5 <LangImpl5.html>`_ :). +Next we add the function arguments to the NamedValues map (after first clearing +it out) so that they're accessible to ``VariableExprAST`` nodes. + .. code-block:: c++ - if (Value *RetVal = Body->Codegen()) { + if (Value *RetVal = Body->codegen()) { // Finish off the function. Builder.CreateRet(RetVal); @@ -408,11 +373,11 @@ at this point. We'll fix this in `Chapter 5 <LangImpl5.html>`_ :). return TheFunction; } -Once the insertion point is set up, we call the ``CodeGen()`` method for -the root expression of the function. If no error happens, this emits -code to compute the expression into the entry block and returns the -value that was computed. Assuming no error, we then create an LLVM `ret -instruction <../LangRef.html#i_ret>`_, which completes the function. +Once the insertion point has been set up and the NamedValues map populated, +we call the ``codegen()`` method for the root expression of the function. If no +error happens, this emits code to compute the expression into the entry block +and returns the value that was computed. Assuming no error, we then create an +LLVM `ret instruction <../LangRef.html#ret-instruction>`_, which completes the function. Once the function is built, we call ``verifyFunction``, which is provided by LLVM. This function does a variety of consistency checks on the generated code, to determine if our compiler is doing everything @@ -423,7 +388,7 @@ function is finished and validated, we return it. // Error reading body, remove function. TheFunction->eraseFromParent(); - return 0; + return nullptr; } The only piece left here is handling of the error case. For simplicity, @@ -432,23 +397,25 @@ we handle this by merely deleting the function we produced with the that they incorrectly typed in before: if we didn't delete it, it would live in the symbol table, with a body, preventing future redefinition. -This code does have a bug, though. Since the ``PrototypeAST::Codegen`` -can return a previously defined forward declaration, our code can -actually delete a forward declaration. There are a number of ways to fix -this bug, see what you can come up with! Here is a testcase: +This code does have a bug, though: If the ``FunctionAST::codegen()`` method +finds an existing IR Function, it does not validate its signature against the +definition's own prototype. This means that an earlier 'extern' declaration will +take precedence over the function definition's signature, which can cause +codegen to fail, for instance if the function arguments are named differently. +There are a number of ways to fix this bug, see what you can come up with! Here +is a testcase: :: - extern foo(a b); # ok, defines foo. - def foo(a b) c; # error, 'c' is invalid. - def bar() foo(1, 2); # error, unknown function "foo" + extern foo(a); # ok, defines foo. + def foo(b) b; # Error: Unknown variable name. (decl using 'a' takes precedence). Driver Changes and Closing Thoughts =================================== For now, code generation to LLVM doesn't really get us much, except that we can look at the pretty IR calls. The sample code inserts calls to -Codegen into the "``HandleDefinition``", "``HandleExtern``" etc +codegen into the "``HandleDefinition``", "``HandleExtern``" etc functions, and then dumps out the LLVM IR. This gives a nice way to look at the LLVM IR for simple functions. For example: @@ -463,10 +430,10 @@ at the LLVM IR for simple functions. For example: Note how the parser turns the top-level expression into anonymous functions for us. This will be handy when we add `JIT -support <LangImpl4.html#jit>`_ in the next chapter. Also note that the +support <LangImpl4.html#adding-a-jit-compiler>`_ in the next chapter. Also note that the code is very literally transcribed, no optimizations are being performed except simple constant folding done by IRBuilder. We will `add -optimizations <LangImpl4.html#trivialconstfold>`_ explicitly in the next +optimizations <LangImpl4.html#trivial-constant-folding>`_ explicitly in the next chapter. :: diff --git a/docs/tutorial/LangImpl4.rst b/docs/tutorial/LangImpl4.rst index cdaac634dd76..a671d0c37f9d 100644 --- a/docs/tutorial/LangImpl4.rst +++ b/docs/tutorial/LangImpl4.rst @@ -120,57 +120,53 @@ exactly the code we have now, except that we would defer running the optimizer until the entire file has been parsed. In order to get per-function optimizations going, we need to set up a -`FunctionPassManager <../WritingAnLLVMPass.html#passmanager>`_ to hold +`FunctionPassManager <../WritingAnLLVMPass.html#what-passmanager-doesr>`_ to hold and organize the LLVM optimizations that we want to run. Once we have -that, we can add a set of optimizations to run. The code looks like -this: +that, we can add a set of optimizations to run. We'll need a new +FunctionPassManager for each module that we want to optimize, so we'll +write a function to create and initialize both the module and pass manager +for us: .. code-block:: c++ - FunctionPassManager OurFPM(TheModule); + void InitializeModuleAndPassManager(void) { + // Open a new module. + TheModule = llvm::make_unique<Module>("my cool jit", getGlobalContext()); + TheModule->setDataLayout(TheJIT->getTargetMachine().createDataLayout()); + + // Create a new pass manager attached to it. + TheFPM = llvm::make_unique<FunctionPassManager>(TheModule.get()); - // Set up the optimizer pipeline. Start with registering info about how the - // target lays out data structures. - OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout())); // Provide basic AliasAnalysis support for GVN. - OurFPM.add(createBasicAliasAnalysisPass()); + TheFPM.add(createBasicAliasAnalysisPass()); // Do simple "peephole" optimizations and bit-twiddling optzns. - OurFPM.add(createInstructionCombiningPass()); + TheFPM.add(createInstructionCombiningPass()); // Reassociate expressions. - OurFPM.add(createReassociatePass()); + TheFPM.add(createReassociatePass()); // Eliminate Common SubExpressions. - OurFPM.add(createGVNPass()); + TheFPM.add(createGVNPass()); // Simplify the control flow graph (deleting unreachable blocks, etc). - OurFPM.add(createCFGSimplificationPass()); - - OurFPM.doInitialization(); - - // Set the global so the code gen can use this. - TheFPM = &OurFPM; + TheFPM.add(createCFGSimplificationPass()); - // Run the main "interpreter loop" now. - MainLoop(); + TheFPM.doInitialization(); + } -This code defines a ``FunctionPassManager``, "``OurFPM``". It requires a -pointer to the ``Module`` to construct itself. Once it is set up, we use -a series of "add" calls to add a bunch of LLVM passes. The first pass is -basically boilerplate, it adds a pass so that later optimizations know -how the data structures in the program are laid out. The -"``TheExecutionEngine``" variable is related to the JIT, which we will -get to in the next section. +This code initializes the global module ``TheModule``, and the function pass +manager ``TheFPM``, which is attached to ``TheModule``. Once the pass manager is +set up, we use a series of "add" calls to add a bunch of LLVM passes. -In this case, we choose to add 4 optimization passes. The passes we -chose here are a pretty standard set of "cleanup" optimizations that are -useful for a wide variety of code. I won't delve into what they do but, -believe me, they are a good starting place :). +In this case, we choose to add five passes: one analysis pass (alias analysis), +and four optimization passes. The passes we choose here are a pretty standard set +of "cleanup" optimizations that are useful for a wide variety of code. I won't +delve into what they do but, believe me, they are a good starting place :). Once the PassManager is set up, we need to make use of it. We do this by running it after our newly created function is constructed (in -``FunctionAST::Codegen``), but before it is returned to the client: +``FunctionAST::codegen()``), but before it is returned to the client: .. code-block:: c++ - if (Value *RetVal = Body->Codegen()) { + if (Value *RetVal = Body->codegen()) { // Finish off the function. Builder.CreateRet(RetVal); @@ -231,55 +227,85 @@ should evaluate and print out 3. If they define a function, they should be able to call it from the command line. In order to do this, we first declare and initialize the JIT. This is -done by adding a global variable and a call in ``main``: +done by adding a global variable ``TheJIT``, and initializing it in +``main``: .. code-block:: c++ - static ExecutionEngine *TheExecutionEngine; + static std::unique_ptr<KaleidoscopeJIT> TheJIT; ... int main() { .. - // Create the JIT. This takes ownership of the module. - TheExecutionEngine = EngineBuilder(TheModule).create(); - .. + TheJIT = llvm::make_unique<KaleidoscopeJIT>(); + + // Run the main "interpreter loop" now. + MainLoop(); + + return 0; } -This creates an abstract "Execution Engine" which can be either a JIT -compiler or the LLVM interpreter. LLVM will automatically pick a JIT -compiler for you if one is available for your platform, otherwise it -will fall back to the interpreter. +The KaleidoscopeJIT class is a simple JIT built specifically for these +tutorials. In later chapters we will look at how it works and extend it with +new features, but for now we will take it as given. Its API is very simple:: +``addModule`` adds an LLVM IR module to the JIT, making its functions +available for execution; ``removeModule`` removes a module, freeing any +memory associated with the code in that module; and ``findSymbol`` allows us +to look up pointers to the compiled code. -Once the ``ExecutionEngine`` is created, the JIT is ready to be used. -There are a variety of APIs that are useful, but the simplest one is the -"``getPointerToFunction(F)``" method. This method JIT compiles the -specified LLVM Function and returns a function pointer to the generated -machine code. In our case, this means that we can change the code that -parses a top-level expression to look like this: +We can take this simple API and change our code that parses top-level expressions to +look like this: .. code-block:: c++ static void HandleTopLevelExpression() { // Evaluate a top-level expression into an anonymous function. - if (FunctionAST *F = ParseTopLevelExpr()) { - if (Function *LF = F->Codegen()) { - LF->dump(); // Dump the function for exposition purposes. + if (auto FnAST = ParseTopLevelExpr()) { + if (FnAST->codegen()) { + + // JIT the module containing the anonymous expression, keeping a handle so + // we can free it later. + auto H = TheJIT->addModule(std::move(TheModule)); + InitializeModuleAndPassManager(); - // JIT the function, returning a function pointer. - void *FPtr = TheExecutionEngine->getPointerToFunction(LF); + // Search the JIT for the __anon_expr symbol. + auto ExprSymbol = TheJIT->findSymbol("__anon_expr"); + assert(ExprSymbol && "Function not found"); - // Cast it to the right type (takes no arguments, returns a double) so we - // can call it as a native function. - double (*FP)() = (double (*)())(intptr_t)FPtr; + // Get the symbol's address and cast it to the right type (takes no + // arguments, returns a double) so we can call it as a native function. + double (*FP)() = (double (*)())(intptr_t)ExprSymbol.getAddress(); fprintf(stderr, "Evaluated to %f\n", FP()); + + // Delete the anonymous expression module from the JIT. + TheJIT->removeModule(H); } -Recall that we compile top-level expressions into a self-contained LLVM -function that takes no arguments and returns the computed double. -Because the LLVM JIT compiler matches the native platform ABI, this -means that you can just cast the result pointer to a function pointer of -that type and call it directly. This means, there is no difference -between JIT compiled code and native machine code that is statically -linked into your application. +If parsing and codegen succeeed, the next step is to add the module containing +the top-level expression to the JIT. We do this by calling addModule, which +triggers code generation for all the functions in the module, and returns a +handle that can be used to remove the module from the JIT later. Once the module +has been added to the JIT it can no longer be modified, so we also open a new +module to hold subsequent code by calling ``InitializeModuleAndPassManager()``. + +Once we've added the module to the JIT we need to get a pointer to the final +generated code. We do this by calling the JIT's findSymbol method, and passing +the name of the top-level expression function: ``__anon_expr``. Since we just +added this function, we assert that findSymbol returned a result. + +Next, we get the in-memory address of the ``__anon_expr`` function by calling +``getAddress()`` on the symbol. Recall that we compile top-level expressions +into a self-contained LLVM function that takes no arguments and returns the +computed double. Because the LLVM JIT compiler matches the native platform ABI, +this means that you can just cast the result pointer to a function pointer of +that type and call it directly. This means, there is no difference between JIT +compiled code and native machine code that is statically linked into your +application. + +Finally, since we don't support re-evaluation of top-level expressions, we +remove the module from the JIT when we're done to free the associated memory. +Recall, however, that the module we created a few lines earlier (via +``InitializeModuleAndPassManager``) is still open and waiting for new code to be +added. With just these two changes, lets see how Kaleidoscope works now! @@ -320,19 +346,161 @@ demonstrates very basic functionality, but can we do more? Evaluated to 24.000000 -This illustrates that we can now call user code, but there is something -a bit subtle going on here. Note that we only invoke the JIT on the -anonymous functions that *call testfunc*, but we never invoked it on -*testfunc* itself. What actually happened here is that the JIT scanned -for all non-JIT'd functions transitively called from the anonymous -function and compiled all of them before returning from -``getPointerToFunction()``. + ready> testfunc(5, 10); + ready> LLVM ERROR: Program used external function 'testfunc' which could not be resolved! + + +Function definitions and calls also work, but something went very wrong on that +last line. The call looks valid, so what happened? As you may have guessed from +the the API a Module is a unit of allocation for the JIT, and testfunc was part +of the same module that contained anonymous expression. When we removed that +module from the JIT to free the memory for the anonymous expression, we deleted +the definition of ``testfunc`` along with it. Then, when we tried to call +testfunc a second time, the JIT could no longer find it. + +The easiest way to fix this is to put the anonymous expression in a separate +module from the rest of the function definitions. The JIT will happily resolve +function calls across module boundaries, as long as each of the functions called +has a prototype, and is added to the JIT before it is called. By putting the +anonymous expression in a different module we can delete it without affecting +the rest of the functions. + +In fact, we're going to go a step further and put every function in its own +module. Doing so allows us to exploit a useful property of the KaleidoscopeJIT +that will make our environment more REPL-like: Functions can be added to the +JIT more than once (unlike a module where every function must have a unique +definition). When you look up a symbol in KaleidoscopeJIT it will always return +the most recent definition: + +:: + + ready> def foo(x) x + 1; + Read function definition: + define double @foo(double %x) { + entry: + %addtmp = fadd double %x, 1.000000e+00 + ret double %addtmp + } + + ready> foo(2); + Evaluated to 3.000000 + + ready> def foo(x) x + 2; + define double @foo(double %x) { + entry: + %addtmp = fadd double %x, 2.000000e+00 + ret double %addtmp + } + + ready> foo(2); + Evaluated to 4.000000 + + +To allow each function to live in its own module we'll need a way to +re-generate previous function declarations into each new module we open: + +.. code-block:: c++ + + static std::unique_ptr<KaleidoscopeJIT> TheJIT; + + ... + + Function *getFunction(std::string Name) { + // First, see if the function has already been added to the current module. + if (auto *F = TheModule->getFunction(Name)) + return F; + + // If not, check whether we can codegen the declaration from some existing + // prototype. + auto FI = FunctionProtos.find(Name); + if (FI != FunctionProtos.end()) + return FI->second->codegen(); + + // If no existing prototype exists, return null. + return nullptr; + } + + ... + + Value *CallExprAST::codegen() { + // Look up the name in the global module table. + Function *CalleeF = getFunction(Callee); + + ... + + Function *FunctionAST::codegen() { + // Transfer ownership of the prototype to the FunctionProtos map, but keep a + // reference to it for use below. + auto &P = *Proto; + FunctionProtos[Proto->getName()] = std::move(Proto); + Function *TheFunction = getFunction(P.getName()); + if (!TheFunction) + return nullptr; + + +To enable this, we'll start by adding a new global, ``FunctionProtos``, that +holds the most recent prototype for each function. We'll also add a convenience +method, ``getFunction()``, to replace calls to ``TheModule->getFunction()``. +Our convenience method searches ``TheModule`` for an existing function +declaration, falling back to generating a new declaration from FunctionProtos if +it doesn't find one. In ``CallExprAST::codegen()`` we just need to replace the +call to ``TheModule->getFunction()``. In ``FunctionAST::codegen()`` we need to +update the FunctionProtos map first, then call ``getFunction()``. With this +done, we can always obtain a function declaration in the current module for any +previously declared function. + +We also need to update HandleDefinition and HandleExtern: + +.. code-block:: c++ + + static void HandleDefinition() { + if (auto FnAST = ParseDefinition()) { + if (auto *FnIR = FnAST->codegen()) { + fprintf(stderr, "Read function definition:"); + FnIR->dump(); + TheJIT->addModule(std::move(TheModule)); + InitializeModuleAndPassManager(); + } + } else { + // Skip token for error recovery. + getNextToken(); + } + } + + static void HandleExtern() { + if (auto ProtoAST = ParseExtern()) { + if (auto *FnIR = ProtoAST->codegen()) { + fprintf(stderr, "Read extern: "); + FnIR->dump(); + FunctionProtos[ProtoAST->getName()] = std::move(ProtoAST); + } + } else { + // Skip token for error recovery. + getNextToken(); + } + } + +In HandleDefinition, we add two lines to transfer the newly defined function to +the JIT and open a new module. In HandleExtern, we just need to add one line to +add the prototype to FunctionProtos. + +With these changes made, lets try our REPL again (I removed the dump of the +anonymous functions this time, you should get the idea by now :) : + +:: + + ready> def foo(x) x + 1; + ready> foo(2); + Evaluated to 3.000000 + + ready> def foo(x) x + 2; + ready> foo(2); + Evaluated to 4.000000 + +It works! -The JIT provides a number of other more advanced interfaces for things -like freeing allocated machine code, rejit'ing functions to update them, -etc. However, even with this simple code, we get some surprisingly -powerful capabilities - check this out (I removed the dump of the -anonymous functions, you should get the idea by now :) : +Even with this simple code, we get some surprisingly powerful capabilities - +check this out: :: @@ -375,34 +543,30 @@ anonymous functions, you should get the idea by now :) : Evaluated to 1.000000 -Whoa, how does the JIT know about sin and cos? The answer is -surprisingly simple: in this example, the JIT started execution of a -function and got to a function call. It realized that the function was -not yet JIT compiled and invoked the standard set of routines to resolve -the function. In this case, there is no body defined for the function, -so the JIT ended up calling "``dlsym("sin")``" on the Kaleidoscope -process itself. Since "``sin``" is defined within the JIT's address -space, it simply patches up calls in the module to call the libm version -of ``sin`` directly. +Whoa, how does the JIT know about sin and cos? The answer is surprisingly +simple: The KaleidoscopeJIT has a straightforward symbol resolution rule that +it uses to find symbols that aren't available in any given module: First +it searches all the modules that have already been added to the JIT, from the +most recent to the oldest, to find the newest definition. If no definition is +found inside the JIT, it falls back to calling "``dlsym("sin")``" on the +Kaleidoscope process itself. Since "``sin``" is defined within the JIT's +address space, it simply patches up calls in the module to call the libm +version of ``sin`` directly. -The LLVM JIT provides a number of interfaces (look in the -``ExecutionEngine.h`` file) for controlling how unknown functions get -resolved. It allows you to establish explicit mappings between IR -objects and addresses (useful for LLVM global variables that you want to -map to static tables, for example), allows you to dynamically decide on -the fly based on the function name, and even allows you to have the JIT -compile functions lazily the first time they're called. +In the future we'll see how tweaking this symbol resolution rule can be used to +enable all sorts of useful features, from security (restricting the set of +symbols available to JIT'd code), to dynamic code generation based on symbol +names, and even lazy compilation. -One interesting application of this is that we can now extend the -language by writing arbitrary C++ code to implement operations. For -example, if we add: +One immediate benefit of the symbol resolution rule is that we can now extend +the language by writing arbitrary C++ code to implement operations. For example, +if we add: .. code-block:: c++ /// putchard - putchar that takes a double and returns 0. - extern "C" - double putchard(double X) { - putchar((char)X); + extern "C" double putchard(double X) { + fputc((char)X, stderr); return 0; } diff --git a/docs/tutorial/LangImpl5.rst b/docs/tutorial/LangImpl5.rst index ca2ffebc19a2..d916f92bf99e 100644 --- a/docs/tutorial/LangImpl5.rst +++ b/docs/tutorial/LangImpl5.rst @@ -66,7 +66,9 @@ for the relevant tokens: .. code-block:: c++ // control - tok_if = -6, tok_then = -7, tok_else = -8, + tok_if = -6, + tok_then = -7, + tok_else = -8, Once we have that, we recognize the new keywords in the lexer. This is pretty simple stuff: @@ -74,11 +76,16 @@ pretty simple stuff: .. code-block:: c++ ... - if (IdentifierStr == "def") return tok_def; - if (IdentifierStr == "extern") return tok_extern; - if (IdentifierStr == "if") return tok_if; - if (IdentifierStr == "then") return tok_then; - if (IdentifierStr == "else") return tok_else; + if (IdentifierStr == "def") + return tok_def; + if (IdentifierStr == "extern") + return tok_extern; + if (IdentifierStr == "if") + return tok_if; + if (IdentifierStr == "then") + return tok_then; + if (IdentifierStr == "else") + return tok_else; return tok_identifier; AST Extensions for If/Then/Else @@ -90,11 +97,13 @@ To represent the new expression we add a new AST node for it: /// IfExprAST - Expression class for if/then/else. class IfExprAST : public ExprAST { - ExprAST *Cond, *Then, *Else; + std::unique_ptr<ExprAST> Cond, Then, Else; + public: - IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else) - : Cond(cond), Then(then), Else(_else) {} - virtual Value *Codegen(); + IfExprAST(std::unique_ptr<ExprAST> Cond, std::unique_ptr<ExprAST> Then, + std::unique_ptr<ExprAST> Else) + : Cond(std::move(Cond)), Then(std::move(Then)), Else(std::move(Else)) {} + virtual Value *codegen(); }; The AST node just has pointers to the various subexpressions. @@ -109,42 +118,51 @@ First we define a new parsing function: .. code-block:: c++ /// ifexpr ::= 'if' expression 'then' expression 'else' expression - static ExprAST *ParseIfExpr() { + static std::unique_ptr<ExprAST> ParseIfExpr() { getNextToken(); // eat the if. // condition. - ExprAST *Cond = ParseExpression(); - if (!Cond) return 0; + auto Cond = ParseExpression(); + if (!Cond) + return nullptr; if (CurTok != tok_then) return Error("expected then"); getNextToken(); // eat the then - ExprAST *Then = ParseExpression(); - if (Then == 0) return 0; + auto Then = ParseExpression(); + if (!Then) + return nullptr; if (CurTok != tok_else) return Error("expected else"); getNextToken(); - ExprAST *Else = ParseExpression(); - if (!Else) return 0; + auto Else = ParseExpression(); + if (!Else) + return nullptr; - return new IfExprAST(Cond, Then, Else); + return llvm::make_unique<IfExprAST>(std::move(Cond), std::move(Then), + std::move(Else)); } Next we hook it up as a primary expression: .. code-block:: c++ - static ExprAST *ParsePrimary() { + static std::unique_ptr<ExprAST> ParsePrimary() { switch (CurTok) { - default: return Error("unknown token when expecting an expression"); - case tok_identifier: return ParseIdentifierExpr(); - case tok_number: return ParseNumberExpr(); - case '(': return ParseParenExpr(); - case tok_if: return ParseIfExpr(); + default: + return Error("unknown token when expecting an expression"); + case tok_identifier: + return ParseIdentifierExpr(); + case tok_number: + return ParseNumberExpr(); + case '(': + return ParseParenExpr(); + case tok_if: + return ParseIfExpr(); } } @@ -196,7 +214,7 @@ Kaleidoscope looks like this: To visualize the control flow graph, you can use a nifty feature of the LLVM '`opt <http://llvm.org/cmds/opt.html>`_' tool. If you put this LLVM IR into "t.ll" and run "``llvm-as < t.ll | opt -analyze -view-cfg``", `a -window will pop up <../ProgrammersManual.html#ViewGraph>`_ and you'll +window will pop up <../ProgrammersManual.html#viewing-graphs-while-debugging-code>`_ and you'll see this graph: .. figure:: LangImpl5-cfg.png @@ -262,19 +280,19 @@ Okay, enough of the motivation and overview, lets generate code! Code Generation for If/Then/Else -------------------------------- -In order to generate code for this, we implement the ``Codegen`` method +In order to generate code for this, we implement the ``codegen`` method for ``IfExprAST``: .. code-block:: c++ - Value *IfExprAST::Codegen() { - Value *CondV = Cond->Codegen(); - if (CondV == 0) return 0; + Value *IfExprAST::codegen() { + Value *CondV = Cond->codegen(); + if (!CondV) + return nullptr; // Convert condition to a bool by comparing equal to 0.0. - CondV = Builder.CreateFCmpONE(CondV, - ConstantFP::get(getGlobalContext(), APFloat(0.0)), - "ifcond"); + CondV = Builder.CreateFCmpONE( + CondV, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "ifcond"); This code is straightforward and similar to what we saw before. We emit the expression for the condition, then compare that value to zero to get @@ -286,7 +304,8 @@ a truth value as a 1-bit (bool) value. // Create blocks for the then and else cases. Insert the 'then' block at the // end of the function. - BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction); + BasicBlock *ThenBB = + BasicBlock::Create(getGlobalContext(), "then", TheFunction); BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); @@ -318,8 +337,9 @@ that LLVM supports forward references. // Emit then value. Builder.SetInsertPoint(ThenBB); - Value *ThenV = Then->Codegen(); - if (ThenV == 0) return 0; + Value *ThenV = Then->codegen(); + if (!ThenV) + return nullptr; Builder.CreateBr(MergeBB); // Codegen of 'Then' can change the current block, update ThenBB for the PHI. @@ -349,7 +369,7 @@ of the block in the CFG. Why then, are we getting the current block when we just set it to ThenBB 5 lines above? The problem is that the "Then" expression may actually itself change the block that the Builder is emitting into if, for example, it contains a nested "if/then/else" -expression. Because calling Codegen recursively could arbitrarily change +expression. Because calling ``codegen()`` recursively could arbitrarily change the notion of the current block, we are required to get an up-to-date value for code that will set up the Phi node. @@ -359,11 +379,12 @@ value for code that will set up the Phi node. TheFunction->getBasicBlockList().push_back(ElseBB); Builder.SetInsertPoint(ElseBB); - Value *ElseV = Else->Codegen(); - if (ElseV == 0) return 0; + Value *ElseV = Else->codegen(); + if (!ElseV) + return nullptr; Builder.CreateBr(MergeBB); - // Codegen of 'Else' can change the current block, update ElseBB for the PHI. + // codegen of 'Else' can change the current block, update ElseBB for the PHI. ElseBB = Builder.GetInsertBlock(); Code generation for the 'else' block is basically identical to codegen @@ -378,8 +399,8 @@ code: // Emit merge block. TheFunction->getBasicBlockList().push_back(MergeBB); Builder.SetInsertPoint(MergeBB); - PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, - "iftmp"); + PHINode *PN = + Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, "iftmp"); PN->addIncoming(ThenV, ThenBB); PN->addIncoming(ElseV, ElseBB); @@ -444,13 +465,20 @@ The lexer extensions are the same sort of thing as for if/then/else: tok_for = -9, tok_in = -10 ... in gettok ... - if (IdentifierStr == "def") return tok_def; - if (IdentifierStr == "extern") return tok_extern; - if (IdentifierStr == "if") return tok_if; - if (IdentifierStr == "then") return tok_then; - if (IdentifierStr == "else") return tok_else; - if (IdentifierStr == "for") return tok_for; - if (IdentifierStr == "in") return tok_in; + if (IdentifierStr == "def") + return tok_def; + if (IdentifierStr == "extern") + return tok_extern; + if (IdentifierStr == "if") + return tok_if; + if (IdentifierStr == "then") + return tok_then; + if (IdentifierStr == "else") + return tok_else; + if (IdentifierStr == "for") + return tok_for; + if (IdentifierStr == "in") + return tok_in; return tok_identifier; AST Extensions for the 'for' Loop @@ -464,12 +492,15 @@ variable name and the constituent expressions in the node. /// ForExprAST - Expression class for for/in. class ForExprAST : public ExprAST { std::string VarName; - ExprAST *Start, *End, *Step, *Body; + std::unique_ptr<ExprAST> Start, End, Step, Body; + public: - ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end, - ExprAST *step, ExprAST *body) - : VarName(varname), Start(start), End(end), Step(step), Body(body) {} - virtual Value *Codegen(); + ForExprAST(const std::string &VarName, std::unique_ptr<ExprAST> Start, + std::unique_ptr<ExprAST> End, std::unique_ptr<ExprAST> Step, + std::unique_ptr<ExprAST> Body) + : VarName(VarName), Start(std::move(Start)), End(std::move(End)), + Step(std::move(Step)), Body(std::move(Body)) {} + virtual Value *codegen(); }; Parser Extensions for the 'for' Loop @@ -483,7 +514,7 @@ value to null in the AST node: .. code-block:: c++ /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression - static ExprAST *ParseForExpr() { + static std::unique_ptr<ExprAST> ParseForExpr() { getNextToken(); // eat the for. if (CurTok != tok_identifier) @@ -497,31 +528,37 @@ value to null in the AST node: getNextToken(); // eat '='. - ExprAST *Start = ParseExpression(); - if (Start == 0) return 0; + auto Start = ParseExpression(); + if (!Start) + return nullptr; if (CurTok != ',') return Error("expected ',' after for start value"); getNextToken(); - ExprAST *End = ParseExpression(); - if (End == 0) return 0; + auto End = ParseExpression(); + if (!End) + return nullptr; // The step value is optional. - ExprAST *Step = 0; + std::unique_ptr<ExprAST> Step; if (CurTok == ',') { getNextToken(); Step = ParseExpression(); - if (Step == 0) return 0; + if (!Step) + return nullptr; } if (CurTok != tok_in) return Error("expected 'in' after for"); getNextToken(); // eat 'in'. - ExprAST *Body = ParseExpression(); - if (Body == 0) return 0; + auto Body = ParseExpression(); + if (!Body) + return nullptr; - return new ForExprAST(IdName, Start, End, Step, Body); + return llvm::make_unique<ForExprAST>(IdName, std::move(Start), + std::move(End), std::move(Step), + std::move(Body)); } LLVM IR for the 'for' Loop @@ -565,14 +602,14 @@ together. Code Generation for the 'for' Loop ---------------------------------- -The first part of Codegen is very simple: we just output the start +The first part of codegen is very simple: we just output the start expression for the loop value: .. code-block:: c++ - Value *ForExprAST::Codegen() { + Value *ForExprAST::codegen() { // Emit the start code first, without 'variable' in scope. - Value *StartVal = Start->Codegen(); + Value *StartVal = Start->codegen(); if (StartVal == 0) return 0; With this out of the way, the next step is to set up the LLVM basic @@ -587,7 +624,8 @@ expression). // block. Function *TheFunction = Builder.GetInsertBlock()->getParent(); BasicBlock *PreheaderBB = Builder.GetInsertBlock(); - BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction); + BasicBlock *LoopBB = + BasicBlock::Create(getGlobalContext(), "loop", TheFunction); // Insert an explicit fall through from the current block to the LoopBB. Builder.CreateBr(LoopBB); @@ -604,7 +642,8 @@ the two blocks. Builder.SetInsertPoint(LoopBB); // Start the PHI node with an entry for Start. - PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str()); + PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), + 2, VarName.c_str()); Variable->addIncoming(StartVal, PreheaderBB); Now that the "preheader" for the loop is set up, we switch to emitting @@ -624,8 +663,8 @@ backedge, but we can't set it up yet (because it doesn't exist!). // Emit the body of the loop. This, like any other expr, can change the // current BB. Note that we ignore the value computed by the body, but don't // allow an error. - if (Body->Codegen() == 0) - return 0; + if (!Body->codegen()) + return nullptr; Now the code starts to get more interesting. Our 'for' loop introduces a new variable to the symbol table. This means that our symbol table can @@ -647,10 +686,11 @@ table. .. code-block:: c++ // Emit the step value. - Value *StepVal; + Value *StepVal = nullptr; if (Step) { - StepVal = Step->Codegen(); - if (StepVal == 0) return 0; + StepVal = Step->codegen(); + if (!StepVal) + return nullptr; } else { // If not specified, use 1.0. StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0)); @@ -666,13 +706,13 @@ iteration of the loop. .. code-block:: c++ // Compute the end condition. - Value *EndCond = End->Codegen(); - if (EndCond == 0) return EndCond; + Value *EndCond = End->codegen(); + if (!EndCond) + return nullptr; // Convert condition to a bool by comparing equal to 0.0. - EndCond = Builder.CreateFCmpONE(EndCond, - ConstantFP::get(getGlobalContext(), APFloat(0.0)), - "loopcond"); + EndCond = Builder.CreateFCmpONE( + EndCond, ConstantFP::get(getGlobalContext(), APFloat(0.0)), "loopcond"); Finally, we evaluate the exit value of the loop, to determine whether the loop should exit. This mirrors the condition evaluation for the @@ -682,7 +722,8 @@ if/then/else statement. // Create the "after loop" block and insert it. BasicBlock *LoopEndBB = Builder.GetInsertBlock(); - BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); + BasicBlock *AfterBB = + BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); // Insert the conditional branch into the end of LoopEndBB. Builder.CreateCondBr(EndCond, LoopBB, AfterBB); @@ -718,7 +759,7 @@ value, we can add the incoming value to the loop PHI node. After that, we remove the loop variable from the symbol table, so that it isn't in scope after the for loop. Finally, code generation of the for loop always returns 0.0, so that is what we return from -``ForExprAST::Codegen``. +``ForExprAST::codegen()``. With this, we conclude the "adding control flow to Kaleidoscope" chapter of the tutorial. In this chapter we added two control flow constructs, diff --git a/docs/tutorial/LangImpl6.rst b/docs/tutorial/LangImpl6.rst index bf78bdea74d6..827cd392effb 100644 --- a/docs/tutorial/LangImpl6.rst +++ b/docs/tutorial/LangImpl6.rst @@ -24,7 +24,7 @@ is good or bad. In this tutorial we'll assume that it is okay to use this as a way to show some interesting parsing techniques. At the end of this tutorial, we'll run through an example Kaleidoscope -application that `renders the Mandelbrot set <#example>`_. This gives an +application that `renders the Mandelbrot set <#kicking-the-tires>`_. This gives an example of what you can build with Kaleidoscope and its feature set. User-defined Operators: the Idea @@ -96,19 +96,24 @@ keywords: enum Token { ... // operators - tok_binary = -11, tok_unary = -12 + tok_binary = -11, + tok_unary = -12 }; ... static int gettok() { ... - if (IdentifierStr == "for") return tok_for; - if (IdentifierStr == "in") return tok_in; - if (IdentifierStr == "binary") return tok_binary; - if (IdentifierStr == "unary") return tok_unary; + if (IdentifierStr == "for") + return tok_for; + if (IdentifierStr == "in") + return tok_in; + if (IdentifierStr == "binary") + return tok_binary; + if (IdentifierStr == "unary") + return tok_unary; return tok_identifier; This just adds lexer support for the unary and binary keywords, like we -did in `previous chapters <LangImpl5.html#iflexer>`_. One nice thing +did in `previous chapters <LangImpl5.html#lexer-extensions-for-if-then-else>`_. One nice thing about our current AST, is that we represent binary operators with full generalisation by using their ASCII code as the opcode. For our extended operators, we'll use this same representation, so we don't need any new @@ -129,15 +134,17 @@ this: class PrototypeAST { std::string Name; std::vector<std::string> Args; - bool isOperator; + bool IsOperator; unsigned Precedence; // Precedence if a binary op. + public: - PrototypeAST(const std::string &name, const std::vector<std::string> &args, - bool isoperator = false, unsigned prec = 0) - : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {} + PrototypeAST(const std::string &name, std::vector<std::string> Args, + bool IsOperator = false, unsigned Prec = 0) + : Name(name), Args(std::move(Args)), IsOperator(IsOperator), + Precedence(Prec) {} - bool isUnaryOp() const { return isOperator && Args.size() == 1; } - bool isBinaryOp() const { return isOperator && Args.size() == 2; } + bool isUnaryOp() const { return IsOperator && Args.size() == 1; } + bool isBinaryOp() const { return IsOperator && Args.size() == 2; } char getOperatorName() const { assert(isUnaryOp() || isBinaryOp()); @@ -146,7 +153,7 @@ this: unsigned getBinaryPrecedence() const { return Precedence; } - Function *Codegen(); + Function *codegen(); }; Basically, in addition to knowing a name for the prototype, we now keep @@ -161,7 +168,7 @@ user-defined operator, we need to parse it: /// prototype /// ::= id '(' id* ')' /// ::= binary LETTER number? (id, id) - static PrototypeAST *ParsePrototype() { + static std::unique_ptr<PrototypeAST> ParsePrototype() { std::string FnName; unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. @@ -210,7 +217,8 @@ user-defined operator, we need to parse it: if (Kind && ArgNames.size() != Kind) return ErrorP("Invalid number of operands for operator"); - return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence); + return llvm::make_unique<PrototypeAST>(FnName, std::move(ArgNames), Kind != 0, + BinaryPrecedence); } This is all fairly straightforward parsing code, and we have already @@ -227,26 +235,31 @@ default case for our existing binary operator node: .. code-block:: c++ - Value *BinaryExprAST::Codegen() { - Value *L = LHS->Codegen(); - Value *R = RHS->Codegen(); - if (L == 0 || R == 0) return 0; + Value *BinaryExprAST::codegen() { + Value *L = LHS->codegen(); + Value *R = RHS->codegen(); + if (!L || !R) + return nullptr; switch (Op) { - case '+': return Builder.CreateFAdd(L, R, "addtmp"); - case '-': return Builder.CreateFSub(L, R, "subtmp"); - case '*': return Builder.CreateFMul(L, R, "multmp"); + case '+': + return Builder.CreateFAdd(L, R, "addtmp"); + case '-': + return Builder.CreateFSub(L, R, "subtmp"); + case '*': + return Builder.CreateFMul(L, R, "multmp"); case '<': L = Builder.CreateFCmpULT(L, R, "cmptmp"); // Convert bool 0/1 to double 0.0 or 1.0 return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), "booltmp"); - default: break; + default: + break; } // If it wasn't a builtin binary operator, it must be a user defined one. Emit // a call to it. - Function *F = TheModule->getFunction(std::string("binary")+Op); + Function *F = TheModule->getFunction(std::string("binary") + Op); assert(F && "binary operator not found!"); Value *Ops[2] = { L, R }; @@ -263,12 +276,12 @@ The final piece of code we are missing, is a bit of top-level magic: .. code-block:: c++ - Function *FunctionAST::Codegen() { + Function *FunctionAST::codegen() { NamedValues.clear(); - Function *TheFunction = Proto->Codegen(); - if (TheFunction == 0) - return 0; + Function *TheFunction = Proto->codegen(); + if (!TheFunction) + return nullptr; // If this is an operator, install it. if (Proto->isBinaryOp()) @@ -278,7 +291,7 @@ The final piece of code we are missing, is a bit of top-level magic: BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); Builder.SetInsertPoint(BB); - if (Value *RetVal = Body->Codegen()) { + if (Value *RetVal = Body->codegen()) { ... Basically, before codegening a function, if it is a user-defined @@ -305,11 +318,12 @@ that, we need an AST node: /// UnaryExprAST - Expression class for a unary operator. class UnaryExprAST : public ExprAST { char Opcode; - ExprAST *Operand; + std::unique_ptr<ExprAST> Operand; + public: - UnaryExprAST(char opcode, ExprAST *operand) - : Opcode(opcode), Operand(operand) {} - virtual Value *Codegen(); + UnaryExprAST(char Opcode, std::unique_ptr<ExprAST> Operand) + : Opcode(Opcode), Operand(std::move(Operand)) {} + virtual Value *codegen(); }; This AST node is very simple and obvious by now. It directly mirrors the @@ -322,7 +336,7 @@ simple: we'll add a new function to do it: /// unary /// ::= primary /// ::= '!' unary - static ExprAST *ParseUnary() { + static std::unique_ptr<ExprAST> ParseUnary() { // If the current token is not an operator, it must be a primary expr. if (!isascii(CurTok) || CurTok == '(' || CurTok == ',') return ParsePrimary(); @@ -330,9 +344,9 @@ simple: we'll add a new function to do it: // If this is a unary operator, read it. int Opc = CurTok; getNextToken(); - if (ExprAST *Operand = ParseUnary()) - return new UnaryExprAST(Opc, Operand); - return 0; + if (auto Operand = ParseUnary()) + return llvm::unique_ptr<UnaryExprAST>(Opc, std::move(Operand)); + return nullptr; } The grammar we add is pretty straightforward here. If we see a unary @@ -350,21 +364,24 @@ call ParseUnary instead: /// binoprhs /// ::= ('+' unary)* - static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { + static std::unique_ptr<ExprAST> ParseBinOpRHS(int ExprPrec, + std::unique_ptr<ExprAST> LHS) { ... // Parse the unary expression after the binary operator. - ExprAST *RHS = ParseUnary(); - if (!RHS) return 0; + auto RHS = ParseUnary(); + if (!RHS) + return nullptr; ... } /// expression /// ::= unary binoprhs /// - static ExprAST *ParseExpression() { - ExprAST *LHS = ParseUnary(); - if (!LHS) return 0; + static std::unique_ptr<ExprAST> ParseExpression() { + auto LHS = ParseUnary(); + if (!LHS) + return nullptr; - return ParseBinOpRHS(0, LHS); + return ParseBinOpRHS(0, std::move(LHS)); } With these two simple changes, we are now able to parse unary operators @@ -378,7 +395,7 @@ operator code above with: /// ::= id '(' id* ')' /// ::= binary LETTER number? (id, id) /// ::= unary LETTER (id) - static PrototypeAST *ParsePrototype() { + static std::unique_ptr<PrototypeAST> ParsePrototype() { std::string FnName; unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. @@ -411,12 +428,13 @@ unary operators. It looks like this: .. code-block:: c++ - Value *UnaryExprAST::Codegen() { - Value *OperandV = Operand->Codegen(); - if (OperandV == 0) return 0; + Value *UnaryExprAST::codegen() { + Value *OperandV = Operand->codegen(); + if (!OperandV) + return nullptr; Function *F = TheModule->getFunction(std::string("unary")+Opcode); - if (F == 0) + if (!F) return ErrorV("Unknown unary operator"); return Builder.CreateCall(F, OperandV, "unop"); diff --git a/docs/tutorial/LangImpl7.rst b/docs/tutorial/LangImpl7.rst index 648940785b09..1cd7d56fddb4 100644 --- a/docs/tutorial/LangImpl7.rst +++ b/docs/tutorial/LangImpl7.rst @@ -118,7 +118,7 @@ that @G defines *space* for an i32 in the global data area, but its *name* actually refers to the address for that space. Stack variables work the same way, except that instead of being declared with global variable definitions, they are declared with the `LLVM alloca -instruction <../LangRef.html#i_alloca>`_: +instruction <../LangRef.html#alloca-instruction>`_: .. code-block:: llvm @@ -221,7 +221,7 @@ variables in certain circumstances: funny pointer arithmetic is involved, the alloca will not be promoted. #. mem2reg only works on allocas of `first - class <../LangRef.html#t_classifications>`_ values (such as pointers, + class <../LangRef.html#first-class-types>`_ values (such as pointers, scalars and vectors), and only if the array size of the allocation is 1 (or missing in the .ll file). mem2reg is not capable of promoting structs or arrays to registers. Note that the "scalarrepl" pass is @@ -355,10 +355,11 @@ from the stack slot: .. code-block:: c++ - Value *VariableExprAST::Codegen() { + Value *VariableExprAST::codegen() { // Look this variable up in the function. Value *V = NamedValues[Name]; - if (V == 0) return ErrorV("Unknown variable name"); + if (!V) + return ErrorV("Unknown variable name"); // Load the value. return Builder.CreateLoad(V, Name.c_str()); @@ -366,7 +367,7 @@ from the stack slot: As you can see, this is pretty straightforward. Now we need to update the things that define the variables to set up the alloca. We'll start -with ``ForExprAST::Codegen`` (see the `full code listing <#code>`_ for +with ``ForExprAST::codegen()`` (see the `full code listing <#id1>`_ for the unabridged code): .. code-block:: c++ @@ -377,16 +378,18 @@ the unabridged code): AllocaInst *Alloca = CreateEntryBlockAlloca(TheFunction, VarName); // Emit the start code first, without 'variable' in scope. - Value *StartVal = Start->Codegen(); - if (StartVal == 0) return 0; + Value *StartVal = Start->codegen(); + if (!StartVal) + return nullptr; // Store the value into the alloca. Builder.CreateStore(StartVal, Alloca); ... // Compute the end condition. - Value *EndCond = End->Codegen(); - if (EndCond == 0) return EndCond; + Value *EndCond = End->codegen(); + if (!EndCond) + return nullptr; // Reload, increment, and restore the alloca. This handles the case where // the body of the loop mutates the variable. @@ -396,7 +399,7 @@ the unabridged code): ... This code is virtually identical to the code `before we allowed mutable -variables <LangImpl5.html#forcodegen>`_. The big difference is that we +variables <LangImpl5.html#code-generation-for-the-for-loop>`_. The big difference is that we no longer have to construct a PHI node, and we use load/store to access the variable as needed. @@ -423,7 +426,7 @@ them. The code for this is also pretty simple: For each argument, we make an alloca, store the input value to the function into the alloca, and register the alloca as the memory location -for the argument. This method gets invoked by ``FunctionAST::Codegen`` +for the argument. This method gets invoked by ``FunctionAST::codegen()`` right after it sets up the entry block for the function. The final missing piece is adding the mem2reg pass, which allows us to @@ -569,11 +572,11 @@ implement codegen for the assignment operator. This looks like: .. code-block:: c++ - Value *BinaryExprAST::Codegen() { + Value *BinaryExprAST::codegen() { // Special case '=' because we don't want to emit the LHS as an expression. if (Op == '=') { // Assignment requires the LHS to be an identifier. - VariableExprAST *LHSE = dynamic_cast<VariableExprAST*>(LHS); + VariableExprAST *LHSE = dynamic_cast<VariableExprAST*>(LHS.get()); if (!LHSE) return ErrorV("destination of '=' must be a variable"); @@ -587,12 +590,14 @@ allowed. .. code-block:: c++ // Codegen the RHS. - Value *Val = RHS->Codegen(); - if (Val == 0) return 0; + Value *Val = RHS->codegen(); + if (!Val) + return nullptr; // Look up the name. Value *Variable = NamedValues[LHSE->getName()]; - if (Variable == 0) return ErrorV("Unknown variable name"); + if (!Variable) + return ErrorV("Unknown variable name"); Builder.CreateStore(Val, Variable); return Val; @@ -649,10 +654,14 @@ this: ... static int gettok() { ... - if (IdentifierStr == "in") return tok_in; - if (IdentifierStr == "binary") return tok_binary; - if (IdentifierStr == "unary") return tok_unary; - if (IdentifierStr == "var") return tok_var; + if (IdentifierStr == "in") + return tok_in; + if (IdentifierStr == "binary") + return tok_binary; + if (IdentifierStr == "unary") + return tok_unary; + if (IdentifierStr == "var") + return tok_var; return tok_identifier; ... @@ -663,14 +672,15 @@ var/in, it looks like this: /// VarExprAST - Expression class for var/in class VarExprAST : public ExprAST { - std::vector<std::pair<std::string, ExprAST*> > VarNames; - ExprAST *Body; + std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames; + std::unique_ptr<ExprAST> Body; + public: - VarExprAST(const std::vector<std::pair<std::string, ExprAST*> > &varnames, - ExprAST *body) - : VarNames(varnames), Body(body) {} + VarExprAST(std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames, + std::unique_ptr<ExprAST> body) + : VarNames(std::move(VarNames)), Body(std::move(Body)) {} - virtual Value *Codegen(); + virtual Value *codegen(); }; var/in allows a list of names to be defined all at once, and each name @@ -690,15 +700,22 @@ do is add it as a primary expression: /// ::= ifexpr /// ::= forexpr /// ::= varexpr - static ExprAST *ParsePrimary() { + static std::unique_ptr<ExprAST> ParsePrimary() { switch (CurTok) { - default: return Error("unknown token when expecting an expression"); - case tok_identifier: return ParseIdentifierExpr(); - case tok_number: return ParseNumberExpr(); - case '(': return ParseParenExpr(); - case tok_if: return ParseIfExpr(); - case tok_for: return ParseForExpr(); - case tok_var: return ParseVarExpr(); + default: + return Error("unknown token when expecting an expression"); + case tok_identifier: + return ParseIdentifierExpr(); + case tok_number: + return ParseNumberExpr(); + case '(': + return ParseParenExpr(); + case tok_if: + return ParseIfExpr(); + case tok_for: + return ParseForExpr(); + case tok_var: + return ParseVarExpr(); } } @@ -708,10 +725,10 @@ Next we define ParseVarExpr: /// varexpr ::= 'var' identifier ('=' expression)? // (',' identifier ('=' expression)?)* 'in' expression - static ExprAST *ParseVarExpr() { + static std::unique_ptr<ExprAST> ParseVarExpr() { getNextToken(); // eat the var. - std::vector<std::pair<std::string, ExprAST*> > VarNames; + std::vector<std::pair<std::string, std::unique_ptr<ExprAST>>> VarNames; // At least one variable name is required. if (CurTok != tok_identifier) @@ -727,15 +744,15 @@ into the local ``VarNames`` vector. getNextToken(); // eat identifier. // Read the optional initializer. - ExprAST *Init = 0; + std::unique_ptr<ExprAST> Init; if (CurTok == '=') { getNextToken(); // eat the '='. Init = ParseExpression(); - if (Init == 0) return 0; + if (!Init) return nullptr; } - VarNames.push_back(std::make_pair(Name, Init)); + VarNames.push_back(std::make_pair(Name, std::move(Init))); // End of var list, exit loop. if (CurTok != ',') break; @@ -755,10 +772,12 @@ AST node: return Error("expected 'in' keyword after 'var'"); getNextToken(); // eat 'in'. - ExprAST *Body = ParseExpression(); - if (Body == 0) return 0; + auto Body = ParseExpression(); + if (!Body) + return nullptr; - return new VarExprAST(VarNames, Body); + return llvm::make_unique<VarExprAST>(std::move(VarNames), + std::move(Body)); } Now that we can parse and represent the code, we need to support @@ -766,7 +785,7 @@ emission of LLVM IR for it. This code starts out with: .. code-block:: c++ - Value *VarExprAST::Codegen() { + Value *VarExprAST::codegen() { std::vector<AllocaInst *> OldBindings; Function *TheFunction = Builder.GetInsertBlock()->getParent(); @@ -774,7 +793,7 @@ emission of LLVM IR for it. This code starts out with: // Register all variables and emit their initializer. for (unsigned i = 0, e = VarNames.size(); i != e; ++i) { const std::string &VarName = VarNames[i].first; - ExprAST *Init = VarNames[i].second; + ExprAST *Init = VarNames[i].second.get(); Basically it loops over all the variables, installing them one at a time. For each variable we put into the symbol table, we remember the @@ -789,8 +808,9 @@ previous value that we replace in OldBindings. // var a = a in ... # refers to outer 'a'. Value *InitVal; if (Init) { - InitVal = Init->Codegen(); - if (InitVal == 0) return 0; + InitVal = Init->codegen(); + if (!InitVal) + return nullptr; } else { // If not specified, use 0.0. InitVal = ConstantFP::get(getGlobalContext(), APFloat(0.0)); } @@ -814,8 +834,9 @@ we evaluate the body of the var/in expression: .. code-block:: c++ // Codegen the body, now that all vars are in scope. - Value *BodyVal = Body->Codegen(); - if (BodyVal == 0) return 0; + Value *BodyVal = Body->codegen(); + if (!BodyVal) + return nullptr; Finally, before returning, we restore the previous variable bindings: diff --git a/docs/tutorial/LangImpl8.rst b/docs/tutorial/LangImpl8.rst index 0b9b39c84b75..3b0f443f08d5 100644 --- a/docs/tutorial/LangImpl8.rst +++ b/docs/tutorial/LangImpl8.rst @@ -75,8 +75,8 @@ statement be our "main": .. code-block:: udiff - - PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); - + PrototypeAST *Proto = new PrototypeAST("main", std::vector<std::string>()); + - auto Proto = llvm::make_unique<PrototypeAST>("", std::vector<std::string>()); + + auto Proto = llvm::make_unique<PrototypeAST>("main", std::vector<std::string>()); just with the simple change of giving it a name. @@ -108,19 +108,19 @@ code is that the llvm IR goes to standard error: @@ -1108,17 +1108,8 @@ static void HandleExtern() { static void HandleTopLevelExpression() { // Evaluate a top-level expression into an anonymous function. - if (FunctionAST *F = ParseTopLevelExpr()) { - - if (Function *LF = F->Codegen()) { + if (auto FnAST = ParseTopLevelExpr()) { + - if (auto *FnIR = FnAST->codegen()) { - // We're just doing this to make sure it executes. - TheExecutionEngine->finalizeObject(); - // JIT the function, returning a function pointer. - - void *FPtr = TheExecutionEngine->getPointerToFunction(LF); + - void *FPtr = TheExecutionEngine->getPointerToFunction(FnIR); - - // Cast it to the right type (takes no arguments, returns a double) so we - // can call it as a native function. - double (*FP)() = (double (*)())(intptr_t)FPtr; - // Ignore the return value for this. - (void)FP; - + if (!F->Codegen()) { + + if (!F->codegen()) { + fprintf(stderr, "Error generating code for top level expr"); } } else { @@ -165,13 +165,13 @@ DWARF Emission Setup ==================== Similar to the ``IRBuilder`` class we have a -```DIBuilder`` <http://llvm.org/doxygen/classllvm_1_1DIBuilder.html>`_ class +`DIBuilder <http://llvm.org/doxygen/classllvm_1_1DIBuilder.html>`_ class that helps in constructing debug metadata for an llvm IR file. It corresponds 1:1 similarly to ``IRBuilder`` and llvm IR, but with nicer names. Using it does require that you be more familiar with DWARF terminology than you needed to be with ``IRBuilder`` and ``Instruction`` names, but if you read through the general documentation on the -```Metadata Format`` <http://llvm.org/docs/SourceLevelDebugging.html>`_ it +`Metadata Format <http://llvm.org/docs/SourceLevelDebugging.html>`_ it should be a little more clear. We'll be using this class to construct all of our IR level descriptions. Construction for it takes a module so we need to construct it shortly after we construct our module. We've left it @@ -237,7 +237,7 @@ Functions ========= Now that we have our ``Compile Unit`` and our source locations, we can add -function definitions to the debug info. So in ``PrototypeAST::Codegen`` we +function definitions to the debug info. So in ``PrototypeAST::codegen()`` we add a few lines of code to describe a context for our subprogram, in this case the "File", and the actual definition of the function itself. @@ -261,7 +261,8 @@ information) and construct our function definition: DISubprogram *SP = DBuilder->createFunction( FContext, Name, StringRef(), Unit, LineNo, CreateFunctionType(Args.size(), Unit), false /* internal linkage */, - true /* definition */, ScopeLine, DINode::FlagPrototyped, false, F); + true /* definition */, ScopeLine, DINode::FlagPrototyped, false); + F->setSubprogram(SP); and we now have an DISubprogram that contains a reference to all of our metadata for the function. @@ -307,10 +308,12 @@ and then we have added to all of our AST classes a source location: SourceLocation Loc; public: + ExprAST(SourceLocation Loc = CurLoc) : Loc(Loc) {} + virtual ~ExprAST() {} + virtual Value* codegen() = 0; int getLine() const { return Loc.Line; } int getCol() const { return Loc.Col; } - ExprAST(SourceLocation Loc = CurLoc) : Loc(Loc) {} - virtual std::ostream &dump(std::ostream &out, int ind) { + virtual raw_ostream &dump(raw_ostream &out, int ind) { return out << ':' << getLine() << ':' << getCol() << '\n'; } @@ -318,7 +321,8 @@ that we pass down through when we create a new expression: .. code-block:: c++ - LHS = new BinaryExprAST(BinLoc, BinOp, LHS, RHS); + LHS = llvm::make_unique<BinaryExprAST>(BinLoc, BinOp, std::move(LHS), + std::move(RHS)); giving us locations for each of our expressions and variables. @@ -395,13 +399,12 @@ argument allocas in ``PrototypeAST::CreateArgumentAllocas``. DIScope *Scope = KSDbgInfo.LexicalBlocks.back(); DIFile *Unit = DBuilder->createFile(KSDbgInfo.TheCU.getFilename(), KSDbgInfo.TheCU.getDirectory()); - DILocalVariable D = DBuilder->createLocalVariable( - dwarf::DW_TAG_arg_variable, Scope, Args[Idx], Unit, Line, - KSDbgInfo.getDoubleTy(), Idx); + DILocalVariable D = DBuilder->createParameterVariable( + Scope, Args[Idx], Idx + 1, Unit, Line, KSDbgInfo.getDoubleTy(), true); - Instruction *Call = DBuilder->insertDeclare( - Alloca, D, DBuilder->createExpression(), Builder.GetInsertBlock()); - Call->setDebugLoc(DebugLoc::get(Line, 0, Scope)); + DBuilder->insertDeclare(Alloca, D, DBuilder->createExpression(), + DebugLoc::get(Line, 0, Scope), + Builder.GetInsertBlock()); Here we're doing a few things. First, we're grabbing our current scope for the variable so we can say what range of code our variable is valid @@ -409,7 +412,7 @@ through. Second, we're creating the variable, giving it the scope, the name, source location, type, and since it's an argument, the argument index. Third, we create an ``lvm.dbg.declare`` call to indicate at the IR level that we've got a variable in an alloca (and it gives a starting -location for the variable). Lastly, we set a source location for the +location for the variable), and setting a source location for the beginning of the scope on the declare. One interesting thing to note at this point is that various debuggers have diff --git a/docs/tutorial/LangImpl9.rst b/docs/tutorial/LangImpl9.rst index 6c43d53f90f9..f02bba857c14 100644 --- a/docs/tutorial/LangImpl9.rst +++ b/docs/tutorial/LangImpl9.rst @@ -49,7 +49,7 @@ For example, try adding: extending the type system in all sorts of interesting ways. Simple arrays are very easy and are quite useful for many different applications. Adding them is mostly an exercise in learning how the - LLVM `getelementptr <../LangRef.html#i_getelementptr>`_ instruction + LLVM `getelementptr <../LangRef.html#getelementptr-instruction>`_ instruction works: it is so nifty/unconventional, it `has its own FAQ <../GetElementPtr.html>`_! If you add support for recursive types (e.g. linked lists), make sure to read the `section in the LLVM diff --git a/docs/tutorial/OCamlLangImpl1.rst b/docs/tutorial/OCamlLangImpl1.rst index 94ca3a5aa4d3..cf968b5ae89c 100644 --- a/docs/tutorial/OCamlLangImpl1.rst +++ b/docs/tutorial/OCamlLangImpl1.rst @@ -139,7 +139,7 @@ useful for mutually recursive functions). For example: A more interesting example is included in Chapter 6 where we write a little Kaleidoscope application that `displays a Mandelbrot -Set <OCamlLangImpl6.html#example>`_ at various levels of magnification. +Set <OCamlLangImpl6.html#kicking-the-tires>`_ at various levels of magnification. Lets dive into the implementation of this language! @@ -275,7 +275,7 @@ file. These are handled with this code: | [< >] -> [< >] With this, we have the complete lexer for the basic Kaleidoscope -language (the `full code listing <OCamlLangImpl2.html#code>`_ for the +language (the `full code listing <OCamlLangImpl2.html#full-code-listing>`_ for the Lexer is available in the `next chapter <OCamlLangImpl2.html>`_ of the tutorial). Next we'll `build a simple parser that uses this to build an Abstract Syntax Tree <OCamlLangImpl2.html>`_. When we have that, we'll diff --git a/docs/tutorial/OCamlLangImpl2.rst b/docs/tutorial/OCamlLangImpl2.rst index 905b306746f1..f5d6cd6822c9 100644 --- a/docs/tutorial/OCamlLangImpl2.rst +++ b/docs/tutorial/OCamlLangImpl2.rst @@ -130,7 +130,7 @@ We start with numeric literals, because they are the simplest to process. For each production in our grammar, we'll define a function which parses that production. We call this class of expressions "primary" expressions, for reasons that will become more clear `later in -the tutorial <OCamlLangImpl6.html#unary>`_. In order to parse an +the tutorial <OCamlLangImpl6.html#user-defined-unary-operators>`_. In order to parse an arbitrary primary expression, we need to determine what sort of expression it is. For numeric literals, we have: @@ -280,7 +280,7 @@ fixed-size array). With the helper above defined, we can now start parsing binary expressions. The basic idea of operator precedence parsing is to break down an expression with potentially ambiguous binary operators into -pieces. Consider ,for example, the expression "a+b+(c+d)\*e\*f+g". +pieces. Consider, for example, the expression "a+b+(c+d)\*e\*f+g". Operator precedence parsing considers this as a stream of primary expressions separated by binary operators. As such, it will first parse the leading primary expression "a", then it will see the pairs [+, b] @@ -505,7 +505,7 @@ The Driver The driver for this simply invokes all of the parsing pieces with a top-level dispatch loop. There isn't much interesting here, so I'll just -include the top-level loop. See `below <#code>`_ for full code in the +include the top-level loop. See `below <#full-code-listing>`_ for full code in the "Top-Level Parsing" section. .. code-block:: ocaml diff --git a/docs/tutorial/OCamlLangImpl3.rst b/docs/tutorial/OCamlLangImpl3.rst index 10d463b93ac3..a76b46d1bf6b 100644 --- a/docs/tutorial/OCamlLangImpl3.rst +++ b/docs/tutorial/OCamlLangImpl3.rst @@ -114,8 +114,8 @@ values that can be in the ``Codegen.named_values`` map are function arguments. This code simply checks to see that the specified name is in the map (if not, an unknown variable is being referenced) and returns the value for it. In future chapters, we'll add support for `loop -induction variables <LangImpl5.html#for>`_ in the symbol table, and for -`local variables <LangImpl7.html#localvars>`_. +induction variables <LangImpl5.html#for-loop-expression>`_ in the symbol table, and for +`local variables <LangImpl7.html#user-defined-local-variables>`_. .. code-block:: ocaml @@ -152,22 +152,22 @@ automatically provide each one with an increasing, unique numeric suffix. Local value names for instructions are purely optional, but it makes it much easier to read the IR dumps. -`LLVM instructions <../LangRef.html#instref>`_ are constrained by strict +`LLVM instructions <../LangRef.html#instruction-reference>`_ are constrained by strict rules: for example, the Left and Right operators of an `add -instruction <../LangRef.html#i_add>`_ must have the same type, and the +instruction <../LangRef.html#add-instruction>`_ must have the same type, and the result type of the add must match the operand types. Because all values in Kaleidoscope are doubles, this makes for very simple code for add, sub and mul. On the other hand, LLVM specifies that the `fcmp -instruction <../LangRef.html#i_fcmp>`_ always returns an 'i1' value (a +instruction <../LangRef.html#fcmp-instruction>`_ always returns an 'i1' value (a one bit integer). The problem with this is that Kaleidoscope wants the value to be a 0.0 or 1.0 value. In order to get these semantics, we combine the fcmp instruction with a `uitofp -instruction <../LangRef.html#i_uitofp>`_. This instruction converts its +instruction <../LangRef.html#uitofp-to-instruction>`_. This instruction converts its input integer into a floating point value by treating the input as an unsigned value. In contrast, if we used the `sitofp -instruction <../LangRef.html#i_sitofp>`_, the Kaleidoscope '<' operator +instruction <../LangRef.html#sitofp-to-instruction>`_, the Kaleidoscope '<' operator would return 0.0 and -1.0, depending on the input value. .. code-block:: ocaml @@ -196,7 +196,7 @@ to resolve function names for us. Once we have the function to call, we recursively codegen each argument that is to be passed in, and create an LLVM `call -instruction <../LangRef.html#i_call>`_. Note that LLVM uses the native C +instruction <../LangRef.html#call-instruction>`_. Note that LLVM uses the native C calling conventions by default, allowing these calls to also call into standard library functions like "sin" and "cos", with no additional effort. @@ -253,7 +253,7 @@ The final line above checks if the function has already been defined in This indicates the type and name to use, as well as which module to insert into. By default we assume a function has ``Llvm.Linkage.ExternalLinkage``. "`external -linkage <LangRef.html#linkage>`_" means that the function may be defined +linkage <../LangRef.html#linkage>`_" means that the function may be defined outside the current module and/or that it is callable by functions outside the module. The "``name``" passed in is the name the user specified: this name is registered in "``Codegen.the_module``"s symbol @@ -360,7 +360,7 @@ Once the insertion point is set up, we call the ``Codegen.codegen_func`` method for the root expression of the function. If no error happens, this emits code to compute the expression into the entry block and returns the value that was computed. Assuming no error, we then create -an LLVM `ret instruction <../LangRef.html#i_ret>`_, which completes the +an LLVM `ret instruction <../LangRef.html#ret-instruction>`_, which completes the function. Once the function is built, we call ``Llvm_analysis.assert_valid_function``, which is provided by LLVM. This function does a variety of consistency checks on the generated code, to @@ -413,10 +413,10 @@ For example: Note how the parser turns the top-level expression into anonymous functions for us. This will be handy when we add `JIT -support <OCamlLangImpl4.html#jit>`_ in the next chapter. Also note that +support <OCamlLangImpl4.html#adding-a-jit-compiler>`_ in the next chapter. Also note that the code is very literally transcribed, no optimizations are being performed. We will `add -optimizations <OCamlLangImpl4.html#trivialconstfold>`_ explicitly in the +optimizations <OCamlLangImpl4.html#trivial-constant-folding>`_ explicitly in the next chapter. :: diff --git a/docs/tutorial/OCamlLangImpl4.rst b/docs/tutorial/OCamlLangImpl4.rst index b13b2afa8883..feeba01be24b 100644 --- a/docs/tutorial/OCamlLangImpl4.rst +++ b/docs/tutorial/OCamlLangImpl4.rst @@ -130,7 +130,7 @@ exactly the code we have now, except that we would defer running the optimizer until the entire file has been parsed. In order to get per-function optimizations going, we need to set up a -`Llvm.PassManager <../WritingAnLLVMPass.html#passmanager>`_ to hold and +`Llvm.PassManager <../WritingAnLLVMPass.html#what-passmanager-does>`_ to hold and organize the LLVM optimizations that we want to run. Once we have that, we can add a set of optimizations to run. The code looks like this: diff --git a/docs/tutorial/OCamlLangImpl5.rst b/docs/tutorial/OCamlLangImpl5.rst index 0faecfb9222e..675b9bc1978b 100644 --- a/docs/tutorial/OCamlLangImpl5.rst +++ b/docs/tutorial/OCamlLangImpl5.rst @@ -175,7 +175,7 @@ Kaleidoscope looks like this: To visualize the control flow graph, you can use a nifty feature of the LLVM '`opt <http://llvm.org/cmds/opt.html>`_' tool. If you put this LLVM IR into "t.ll" and run "``llvm-as < t.ll | opt -analyze -view-cfg``", `a -window will pop up <../ProgrammersManual.html#ViewGraph>`_ and you'll +window will pop up <../ProgrammersManual.html#viewing-graphs-while-debugging-code>`_ and you'll see this graph: .. figure:: LangImpl5-cfg.png diff --git a/docs/tutorial/OCamlLangImpl6.rst b/docs/tutorial/OCamlLangImpl6.rst index 36bffa8e9696..a3ae11fd7e54 100644 --- a/docs/tutorial/OCamlLangImpl6.rst +++ b/docs/tutorial/OCamlLangImpl6.rst @@ -24,7 +24,7 @@ is good or bad. In this tutorial we'll assume that it is okay to use this as a way to show some interesting parsing techniques. At the end of this tutorial, we'll run through an example Kaleidoscope -application that `renders the Mandelbrot set <#example>`_. This gives an +application that `renders the Mandelbrot set <#kicking-the-tires>`_. This gives an example of what you can build with Kaleidoscope and its feature set. User-defined Operators: the Idea @@ -108,7 +108,7 @@ keywords: | "unary" -> [< 'Token.Unary; stream >] This just adds lexer support for the unary and binary keywords, like we -did in `previous chapters <OCamlLangImpl5.html#iflexer>`_. One nice +did in `previous chapters <OCamlLangImpl5.html#lexer-extensions-for-if-then-else>`_. One nice thing about our current AST, is that we represent binary operators with full generalisation by using their ASCII code as the opcode. For our extended operators, we'll use this same representation, so we don't need diff --git a/docs/tutorial/OCamlLangImpl7.rst b/docs/tutorial/OCamlLangImpl7.rst index 98ea93f42f3f..c8c701b91012 100644 --- a/docs/tutorial/OCamlLangImpl7.rst +++ b/docs/tutorial/OCamlLangImpl7.rst @@ -118,7 +118,7 @@ that @G defines *space* for an i32 in the global data area, but its *name* actually refers to the address for that space. Stack variables work the same way, except that instead of being declared with global variable definitions, they are declared with the `LLVM alloca -instruction <../LangRef.html#i_alloca>`_: +instruction <../LangRef.html#alloca-instruction>`_: .. code-block:: llvm @@ -221,7 +221,7 @@ variables in certain circumstances: funny pointer arithmetic is involved, the alloca will not be promoted. #. mem2reg only works on allocas of `first - class <../LangRef.html#t_classifications>`_ values (such as pointers, + class <../LangRef.html#first-class-types>`_ values (such as pointers, scalars and vectors), and only if the array size of the allocation is 1 (or missing in the .ll file). mem2reg is not capable of promoting structs or arrays to registers. Note that the "scalarrepl" pass is @@ -367,7 +367,7 @@ from the stack slot: As you can see, this is pretty straightforward. Now we need to update the things that define the variables to set up the alloca. We'll start -with ``codegen_expr Ast.For ...`` (see the `full code listing <#code>`_ +with ``codegen_expr Ast.For ...`` (see the `full code listing <#id1>`_ for the unabridged code): .. code-block:: ocaml @@ -407,7 +407,7 @@ for the unabridged code): ... This code is virtually identical to the code `before we allowed mutable -variables <OCamlLangImpl5.html#forcodegen>`_. The big difference is that +variables <OCamlLangImpl5.html#code-generation-for-the-for-loop>`_. The big difference is that we no longer have to construct a PHI node, and we use load/store to access the variable as needed. diff --git a/docs/tutorial/OCamlLangImpl8.rst b/docs/tutorial/OCamlLangImpl8.rst index 0346fa9fed14..3ab6db35dfb0 100644 --- a/docs/tutorial/OCamlLangImpl8.rst +++ b/docs/tutorial/OCamlLangImpl8.rst @@ -48,7 +48,7 @@ For example, try adding: extending the type system in all sorts of interesting ways. Simple arrays are very easy and are quite useful for many different applications. Adding them is mostly an exercise in learning how the - LLVM `getelementptr <../LangRef.html#i_getelementptr>`_ instruction + LLVM `getelementptr <../LangRef.html#getelementptr-instruction>`_ instruction works: it is so nifty/unconventional, it `has its own FAQ <../GetElementPtr.html>`_! If you add support for recursive types (e.g. linked lists), make sure to read the `section in the LLVM |
