Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" |
| 2 | "http://www.w3.org/TR/html4/strict.dtd"> |
| 3 | |
| 4 | <html> |
| 5 | <head> |
| 6 | <title>Kaleidoscope: Implementing code generation to LLVM IR</title> |
| 7 | <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> |
| 8 | <meta name="author" content="Chris Lattner"> |
| 9 | <link rel="stylesheet" href="../llvm.css" type="text/css"> |
| 10 | </head> |
| 11 | |
| 12 | <body> |
| 13 | |
| 14 | <div class="doc_title">Kaleidoscope: Code generation to LLVM IR</div> |
| 15 | |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 16 | <ul> |
Chris Lattner | 0e555b1 | 2007-11-05 20:04:56 +0000 | [diff] [blame] | 17 | <li><a href="index.html">Up to Tutorial Index</a></li> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 18 | <li>Chapter 3 |
| 19 | <ol> |
| 20 | <li><a href="#intro">Chapter 3 Introduction</a></li> |
Chris Lattner | 7badb2d | 2007-11-06 07:26:32 +0000 | [diff] [blame] | 21 | <li><a href="#basics">Code Generation Setup</a></li> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 22 | <li><a href="#exprs">Expression Code Generation</a></li> |
| 23 | <li><a href="#funcs">Function Code Generation</a></li> |
| 24 | <li><a href="#driver">Driver Changes and Closing Thoughts</a></li> |
| 25 | <li><a href="#code">Full Code Listing</a></li> |
| 26 | </ol> |
| 27 | </li> |
Chris Lattner | 0e555b1 | 2007-11-05 20:04:56 +0000 | [diff] [blame] | 28 | <li><a href="LangImpl4.html">Chapter 4</a>: Adding JIT and Optimizer |
| 29 | Support</li> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 30 | </ul> |
| 31 | |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 32 | <div class="doc_author"> |
| 33 | <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p> |
| 34 | </div> |
| 35 | |
| 36 | <!-- *********************************************************************** --> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 37 | <div class="doc_section"><a name="intro">Chapter 3 Introduction</a></div> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 38 | <!-- *********************************************************************** --> |
| 39 | |
| 40 | <div class="doc_text"> |
| 41 | |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 42 | <p>Welcome to Chapter 3 of the "<a href="index.html">Implementing a language |
| 43 | with LLVM</a>" tutorial. This chapter shows you how to transform the <a |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 44 | href="LangImpl2.html">Abstract Syntax Tree</a>, built in Chapter 2, into LLVM IR. |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 45 | This will teach you a little bit about how LLVM does things, as well as |
| 46 | demonstrate how easy it is to use. It's much more work to build a lexer and |
Chris Lattner | 7badb2d | 2007-11-06 07:26:32 +0000 | [diff] [blame] | 47 | parser than it is to generate LLVM IR code. :) |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 48 | </p> |
| 49 | |
Chris Lattner | 51c9717 | 2007-11-28 19:26:42 +0000 | [diff] [blame] | 50 | <p><b>Please note</b>: the code in this chapter and later require LLVM 2.2 or |
Chris Lattner | d4c2491 | 2008-05-28 06:16:08 +0000 | [diff] [blame] | 51 | later. LLVM 2.1 and before will not work with it. Also note that you need |
| 52 | to use a version of this tutorial that matches your LLVM release: If you are |
| 53 | using an official LLVM release, use the version of the documentation included |
| 54 | with your release or on the <a href="http://llvm.org/releases/">llvm.org |
| 55 | releases page</a>.</p> |
Chris Lattner | 51c9717 | 2007-11-28 19:26:42 +0000 | [diff] [blame] | 56 | |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 57 | </div> |
| 58 | |
| 59 | <!-- *********************************************************************** --> |
Chris Lattner | 7badb2d | 2007-11-06 07:26:32 +0000 | [diff] [blame] | 60 | <div class="doc_section"><a name="basics">Code Generation Setup</a></div> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 61 | <!-- *********************************************************************** --> |
| 62 | |
| 63 | <div class="doc_text"> |
| 64 | |
| 65 | <p> |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 66 | In order to generate LLVM IR, we want some simple setup to get started. First |
| 67 | we define virtual code generation (codegen) methods in each AST class:</p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 68 | |
| 69 | <div class="doc_code"> |
| 70 | <pre> |
| 71 | /// ExprAST - Base class for all expression nodes. |
| 72 | class ExprAST { |
| 73 | public: |
| 74 | virtual ~ExprAST() {} |
Chris Lattner | cac2135 | 2007-11-05 19:25:14 +0000 | [diff] [blame] | 75 | <b>virtual Value *Codegen() = 0;</b> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 76 | }; |
| 77 | |
| 78 | /// NumberExprAST - Expression class for numeric literals like "1.0". |
| 79 | class NumberExprAST : public ExprAST { |
| 80 | double Val; |
| 81 | public: |
Chris Lattner | 28571ed | 2007-10-23 04:27:44 +0000 | [diff] [blame] | 82 | explicit NumberExprAST(double val) : Val(val) {} |
Chris Lattner | cac2135 | 2007-11-05 19:25:14 +0000 | [diff] [blame] | 83 | <b>virtual Value *Codegen();</b> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 84 | }; |
| 85 | ... |
| 86 | </pre> |
| 87 | </div> |
| 88 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 89 | <p>The Codegen() method says to emit IR for that AST node along with all the things it |
Chris Lattner | 28571ed | 2007-10-23 04:27:44 +0000 | [diff] [blame] | 90 | depends on, and they all return an LLVM Value object. |
| 91 | "Value" is the class used to represent a "<a |
| 92 | href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single |
| 93 | Assignment (SSA)</a> register" or "SSA value" in LLVM. The most distinct aspect |
| 94 | of SSA values is that their value is computed as the related instruction |
| 95 | executes, and it does not get a new value until (and if) the instruction |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 96 | re-executes. In other words, there is no way to "change" an SSA value. For |
Chris Lattner | 28571ed | 2007-10-23 04:27:44 +0000 | [diff] [blame] | 97 | more information, please read up on <a |
| 98 | href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Static Single |
| 99 | Assignment</a> - the concepts are really quite natural once you grok them.</p> |
| 100 | |
Chris Lattner | cac2135 | 2007-11-05 19:25:14 +0000 | [diff] [blame] | 101 | <p>Note that instead of adding virtual methods to the ExprAST class hierarchy, |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 102 | it could also make sense to use a <a |
| 103 | href="http://en.wikipedia.org/wiki/Visitor_pattern">visitor pattern</a> or some |
| 104 | other way to model this. Again, this tutorial won't dwell on good software |
| 105 | engineering practices: for our purposes, adding a virtual method is |
| 106 | simplest.</p> |
Chris Lattner | cac2135 | 2007-11-05 19:25:14 +0000 | [diff] [blame] | 107 | |
Chris Lattner | 28571ed | 2007-10-23 04:27:44 +0000 | [diff] [blame] | 108 | <p>The |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 109 | second thing we want is an "Error" method like we used for the parser, which will |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 110 | be used to report errors found during code generation (for example, use of an |
| 111 | undeclared parameter):</p> |
| 112 | |
| 113 | <div class="doc_code"> |
| 114 | <pre> |
| 115 | Value *ErrorV(const char *Str) { Error(Str); return 0; } |
| 116 | |
| 117 | static Module *TheModule; |
Owen Anderson | d1fbd14 | 2009-07-08 20:50:47 +0000 | [diff] [blame] | 118 | static IRBuilder<> Builder(getGlobalContext()); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 119 | static std::map<std::string, Value*> NamedValues; |
| 120 | </pre> |
| 121 | </div> |
| 122 | |
| 123 | <p>The static variables will be used during code generation. <tt>TheModule</tt> |
| 124 | is the LLVM construct that contains all of the functions and global variables in |
| 125 | a chunk of code. In many ways, it is the top-level structure that the LLVM IR |
| 126 | uses to contain code.</p> |
| 127 | |
| 128 | <p>The <tt>Builder</tt> object is a helper object that makes it easy to generate |
Chris Lattner | f6e53df | 2007-11-05 18:02:15 +0000 | [diff] [blame] | 129 | LLVM instructions. Instances of the <a |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 130 | href="http://llvm.org/doxygen/IRBuilder_8h-source.html"><tt>IRBuilder</tt></a> |
Gabor Greif | d6c1ed0 | 2009-03-11 19:51:07 +0000 | [diff] [blame] | 131 | class template keep track of the current place to insert instructions and has |
| 132 | methods to create new instructions.</p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 133 | |
| 134 | <p>The <tt>NamedValues</tt> map keeps track of which values are defined in the |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 135 | current scope and what their LLVM representation is. (In other words, it is a |
| 136 | symbol table for the code). In this form of Kaleidoscope, the only things that |
| 137 | can be referenced are function parameters. As such, function parameters will |
| 138 | be in this map when generating code for their function body.</p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 139 | |
| 140 | <p> |
| 141 | With these basics in place, we can start talking about how to generate code for |
| 142 | each expression. Note that this assumes that the <tt>Builder</tt> has been set |
| 143 | up to generate code <em>into</em> something. For now, we'll assume that this |
| 144 | has already been done, and we'll just use it to emit code. |
| 145 | </p> |
| 146 | |
| 147 | </div> |
| 148 | |
| 149 | <!-- *********************************************************************** --> |
| 150 | <div class="doc_section"><a name="exprs">Expression Code Generation</a></div> |
| 151 | <!-- *********************************************************************** --> |
| 152 | |
| 153 | <div class="doc_text"> |
| 154 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 155 | <p>Generating LLVM code for expression nodes is very straightforward: less |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 156 | than 45 lines of commented code for all four of our expression nodes. First |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 157 | we'll do numeric literals:</p> |
| 158 | |
| 159 | <div class="doc_code"> |
| 160 | <pre> |
| 161 | Value *NumberExprAST::Codegen() { |
Owen Anderson | 914e50c | 2009-07-16 19:05:41 +0000 | [diff] [blame^] | 162 | return getGlobalContext().getConstantFP(APFloat(Val)); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 163 | } |
| 164 | </pre> |
| 165 | </div> |
| 166 | |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 167 | <p>In the LLVM IR, numeric constants are represented with the |
| 168 | <tt>ConstantFP</tt> class, which holds the numeric value in an <tt>APFloat</tt> |
| 169 | internally (<tt>APFloat</tt> has the capability of holding floating point |
| 170 | constants of <em>A</em>rbitrary <em>P</em>recision). This code basically just |
| 171 | creates and returns a <tt>ConstantFP</tt>. Note that in the LLVM IR |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 172 | that constants are all uniqued together and shared. For this reason, the API |
Owen Anderson | 914e50c | 2009-07-16 19:05:41 +0000 | [diff] [blame^] | 173 | uses "the Context.get..." idiom instead of "new foo(..)" or "foo::Create(..)".</p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 174 | |
| 175 | <div class="doc_code"> |
| 176 | <pre> |
| 177 | Value *VariableExprAST::Codegen() { |
| 178 | // Look this variable up in the function. |
| 179 | Value *V = NamedValues[Name]; |
| 180 | return V ? V : ErrorV("Unknown variable name"); |
| 181 | } |
| 182 | </pre> |
| 183 | </div> |
| 184 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 185 | <p>References to variables are also quite simple using LLVM. In the simple version |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 186 | of Kaleidoscope, we assume that the variable has already been emited somewhere |
| 187 | and its value is available. In practice, the only values that can be in the |
| 188 | <tt>NamedValues</tt> map are function arguments. This |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 189 | code simply checks to see that the specified name is in the map (if not, an |
Chris Lattner | 7badb2d | 2007-11-06 07:26:32 +0000 | [diff] [blame] | 190 | unknown variable is being referenced) and returns the value for it. In future |
| 191 | chapters, we'll add support for <a href="LangImpl5.html#for">loop induction |
| 192 | variables</a> in the symbol table, and for <a |
| 193 | href="LangImpl7.html#localvars">local variables</a>.</p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 194 | |
| 195 | <div class="doc_code"> |
| 196 | <pre> |
| 197 | Value *BinaryExprAST::Codegen() { |
| 198 | Value *L = LHS->Codegen(); |
| 199 | Value *R = RHS->Codegen(); |
| 200 | if (L == 0 || R == 0) return 0; |
| 201 | |
| 202 | switch (Op) { |
| 203 | case '+': return Builder.CreateAdd(L, R, "addtmp"); |
| 204 | case '-': return Builder.CreateSub(L, R, "subtmp"); |
| 205 | case '*': return Builder.CreateMul(L, R, "multmp"); |
| 206 | case '<': |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 207 | L = Builder.CreateFCmpULT(L, R, "cmptmp"); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 208 | // Convert bool 0/1 to double 0.0 or 1.0 |
| 209 | return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp"); |
| 210 | default: return ErrorV("invalid binary operator"); |
| 211 | } |
| 212 | } |
| 213 | </pre> |
| 214 | </div> |
| 215 | |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 216 | <p>Binary operators start to get more interesting. The basic idea here is that |
| 217 | we recursively emit code for the left-hand side of the expression, then the |
| 218 | right-hand side, then we compute the result of the binary expression. In this |
| 219 | code, we do a simple switch on the opcode to create the right LLVM instruction. |
| 220 | </p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 221 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 222 | <p>In the example above, the LLVM builder class is starting to show its value. |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 223 | IRBuilder knows where to insert the newly created instruction, all you have to |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 224 | do is specify what instruction to create (e.g. with <tt>CreateAdd</tt>), which |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 225 | operands to use (<tt>L</tt> and <tt>R</tt> here) and optionally provide a name |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 226 | for the generated instruction.</p> |
| 227 | |
| 228 | <p>One nice thing about LLVM is that the name is just a hint. For instance, if |
| 229 | the code above emits multiple "addtmp" variables, LLVM will automatically |
| 230 | provide each one with an increasing, unique numeric suffix. Local value names |
| 231 | for instructions are purely optional, but it makes it much easier to read the |
| 232 | IR dumps.</p> |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 233 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 234 | <p><a href="../LangRef.html#instref">LLVM instructions</a> are constrained by |
Chris Lattner | 7badb2d | 2007-11-06 07:26:32 +0000 | [diff] [blame] | 235 | strict rules: for example, the Left and Right operators of |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 236 | an <a href="../LangRef.html#i_add">add instruction</a> must have the same |
| 237 | type, and the result type of the add must match the operand types. Because |
Chris Lattner | 7badb2d | 2007-11-06 07:26:32 +0000 | [diff] [blame] | 238 | all values in Kaleidoscope are doubles, this makes for very simple code for add, |
| 239 | sub and mul.</p> |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 240 | |
| 241 | <p>On the other hand, LLVM specifies that the <a |
| 242 | href="../LangRef.html#i_fcmp">fcmp instruction</a> always returns an 'i1' value |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 243 | (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 |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 244 | a <a href="../LangRef.html#i_uitofp">uitofp instruction</a>. This instruction |
| 245 | converts its input integer into a floating point value by treating the input |
| 246 | as an unsigned value. In contrast, if we used the <a |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 247 | href="../LangRef.html#i_sitofp">sitofp instruction</a>, the Kaleidoscope '<' |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 248 | operator would return 0.0 and -1.0, depending on the input value.</p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 249 | |
| 250 | <div class="doc_code"> |
| 251 | <pre> |
| 252 | Value *CallExprAST::Codegen() { |
| 253 | // Look up the name in the global module table. |
| 254 | Function *CalleeF = TheModule->getFunction(Callee); |
| 255 | if (CalleeF == 0) |
| 256 | return ErrorV("Unknown function referenced"); |
| 257 | |
| 258 | // If argument mismatch error. |
| 259 | if (CalleeF->arg_size() != Args.size()) |
| 260 | return ErrorV("Incorrect # arguments passed"); |
| 261 | |
| 262 | std::vector<Value*> ArgsV; |
| 263 | for (unsigned i = 0, e = Args.size(); i != e; ++i) { |
| 264 | ArgsV.push_back(Args[i]->Codegen()); |
| 265 | if (ArgsV.back() == 0) return 0; |
| 266 | } |
| 267 | |
| 268 | return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); |
| 269 | } |
| 270 | </pre> |
| 271 | </div> |
| 272 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 273 | <p>Code generation for function calls is quite straightforward with LLVM. The |
| 274 | code above initially does a function name lookup in the LLVM Module's symbol |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 275 | table. Recall that the LLVM Module is the container that holds all of the |
| 276 | functions we are JIT'ing. By giving each function the same name as what the |
| 277 | user specifies, we can use the LLVM symbol table to resolve function names for |
| 278 | us.</p> |
| 279 | |
| 280 | <p>Once we have the function to call, we recursively codegen each argument that |
| 281 | is to be passed in, and create an LLVM <a href="../LangRef.html#i_call">call |
| 282 | instruction</a>. Note that LLVM uses the native C calling conventions by |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 283 | default, allowing these calls to also call into standard library functions like |
| 284 | "sin" and "cos", with no additional effort.</p> |
Chris Lattner | d3f0cdd | 2007-10-23 04:51:30 +0000 | [diff] [blame] | 285 | |
| 286 | <p>This wraps up our handling of the four basic expressions that we have so far |
| 287 | in Kaleidoscope. Feel free to go in and add some more. For example, by |
| 288 | browsing the <a href="../LangRef.html">LLVM language reference</a> you'll find |
| 289 | several other interesting instructions that are really easy to plug into our |
| 290 | basic framework.</p> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 291 | |
| 292 | </div> |
| 293 | |
| 294 | <!-- *********************************************************************** --> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 295 | <div class="doc_section"><a name="funcs">Function Code Generation</a></div> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 296 | <!-- *********************************************************************** --> |
| 297 | |
| 298 | <div class="doc_text"> |
| 299 | |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 300 | <p>Code generation for prototypes and functions must handle a number of |
| 301 | details, which make their code less beautiful than expression code |
| 302 | generation, but allows us to illustrate some important points. First, lets |
| 303 | talk about code generation for prototypes: they are used both for function |
| 304 | bodies and external function declarations. The code starts with:</p> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 305 | |
| 306 | <div class="doc_code"> |
| 307 | <pre> |
| 308 | Function *PrototypeAST::Codegen() { |
| 309 | // Make the function type: double(double,double) etc. |
| 310 | std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy); |
Owen Anderson | 914e50c | 2009-07-16 19:05:41 +0000 | [diff] [blame^] | 311 | FunctionType *FT = getGlobalContext().getFunctionType(Type::DoubleTy, Doubles, false); |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 312 | |
Gabor Greif | df7d2b4 | 2008-04-19 22:25:09 +0000 | [diff] [blame] | 313 | Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 314 | </pre> |
| 315 | </div> |
| 316 | |
Chris Lattner | cf9893d | 2007-11-05 19:22:50 +0000 | [diff] [blame] | 317 | <p>This code packs a lot of power into a few lines. Note first that this |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 318 | function returns a "Function*" instead of a "Value*". Because a "prototype" |
| 319 | really talks about the external interface for a function (not the value computed |
| 320 | by an expression), it makes sense for it to return the LLVM Function it |
| 321 | corresponds to when codegen'd.</p> |
Chris Lattner | cf9893d | 2007-11-05 19:22:50 +0000 | [diff] [blame] | 322 | |
Owen Anderson | 914e50c | 2009-07-16 19:05:41 +0000 | [diff] [blame^] | 323 | <p>The call to <tt>Context.get</tt> creates |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 324 | the <tt>FunctionType</tt> that should be used for a given Prototype. Since all |
| 325 | function arguments in Kaleidoscope are of type double, the first line creates |
Owen Anderson | 914e50c | 2009-07-16 19:05:41 +0000 | [diff] [blame^] | 326 | a vector of "N" LLVM double types. It then uses the <tt>Context.get</tt> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 327 | method to create a function type that takes "N" doubles as arguments, returns |
| 328 | one double as a result, and that is not vararg (the false parameter indicates |
| 329 | this). Note that Types in LLVM are uniqued just like Constants are, so you |
| 330 | don't "new" a type, you "get" it.</p> |
| 331 | |
| 332 | <p>The final line above actually creates the function that the prototype will |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 333 | correspond to. This indicates the type, linkage and name to use, as well as which |
Chris Lattner | 1ace67c | 2008-04-15 16:59:22 +0000 | [diff] [blame] | 334 | module to insert into. "<a href="../LangRef.html#linkage">external linkage</a>" |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 335 | means that the function may be defined outside the current module and/or that it |
| 336 | is callable by functions outside the module. The Name passed in is the name the |
| 337 | user specified: since "<tt>TheModule</tt>" is specified, this name is registered |
| 338 | in "<tt>TheModule</tt>"s symbol table, which is used by the function call code |
| 339 | above.</p> |
| 340 | |
| 341 | <div class="doc_code"> |
| 342 | <pre> |
| 343 | // If F conflicted, there was already something named 'Name'. If it has a |
| 344 | // body, don't allow redefinition or reextern. |
| 345 | if (F->getName() != Name) { |
| 346 | // Delete the one we just made and get the existing one. |
| 347 | F->eraseFromParent(); |
| 348 | F = TheModule->getFunction(Name); |
| 349 | </pre> |
| 350 | </div> |
| 351 | |
| 352 | <p>The Module symbol table works just like the Function symbol table when it |
| 353 | comes to name conflicts: if a new function is created with a name was previously |
| 354 | added to the symbol table, it will get implicitly renamed when added to the |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 355 | Module. The code above exploits this fact to determine if there was a previous |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 356 | definition of this function.</p> |
| 357 | |
| 358 | <p>In Kaleidoscope, I choose to allow redefinitions of functions in two cases: |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 359 | first, we want to allow 'extern'ing a function more than once, as long as the |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 360 | prototypes for the externs match (since all arguments have the same type, we |
| 361 | just have to check that the number of arguments match). Second, we want to |
| 362 | allow 'extern'ing a function and then definining a body for it. This is useful |
| 363 | when defining mutually recursive functions.</p> |
| 364 | |
| 365 | <p>In order to implement this, the code above first checks to see if there is |
| 366 | a collision on the name of the function. If so, it deletes the function we just |
| 367 | created (by calling <tt>eraseFromParent</tt>) and then calling |
| 368 | <tt>getFunction</tt> to get the existing function with the specified name. Note |
| 369 | that many APIs in LLVM have "erase" forms and "remove" forms. The "remove" form |
| 370 | unlinks the object from its parent (e.g. a Function from a Module) and returns |
| 371 | it. The "erase" form unlinks the object and then deletes it.</p> |
| 372 | |
| 373 | <div class="doc_code"> |
| 374 | <pre> |
| 375 | // If F already has a body, reject this. |
| 376 | if (!F->empty()) { |
| 377 | ErrorF("redefinition of function"); |
| 378 | return 0; |
| 379 | } |
| 380 | |
| 381 | // If F took a different number of args, reject. |
| 382 | if (F->arg_size() != Args.size()) { |
| 383 | ErrorF("redefinition of function with different # args"); |
| 384 | return 0; |
| 385 | } |
| 386 | } |
| 387 | </pre> |
| 388 | </div> |
| 389 | |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 390 | <p>In order to verify the logic above, we first check to see if the pre-existing |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 391 | function is "empty". In this case, empty means that it has no basic blocks in |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 392 | it, which means it has no body. If it has no body, it is a forward |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 393 | declaration. Since we don't allow anything after a full definition of the |
| 394 | function, the code rejects this case. If the previous reference to a function |
| 395 | was an 'extern', we simply verify that the number of arguments for that |
| 396 | definition and this one match up. If not, we emit an error.</p> |
| 397 | |
| 398 | <div class="doc_code"> |
| 399 | <pre> |
| 400 | // Set names for all arguments. |
| 401 | unsigned Idx = 0; |
| 402 | for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); |
| 403 | ++AI, ++Idx) { |
| 404 | AI->setName(Args[Idx]); |
| 405 | |
| 406 | // Add arguments to variable symbol table. |
| 407 | NamedValues[Args[Idx]] = AI; |
| 408 | } |
| 409 | return F; |
| 410 | } |
| 411 | </pre> |
| 412 | </div> |
| 413 | |
| 414 | <p>The last bit of code for prototypes loops over all of the arguments in the |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 415 | function, setting the name of the LLVM Argument objects to match, and registering |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 416 | the arguments in the <tt>NamedValues</tt> map for future use by the |
| 417 | <tt>VariableExprAST</tt> AST node. Once this is set up, it returns the Function |
| 418 | object to the caller. Note that we don't check for conflicting |
| 419 | argument names here (e.g. "extern foo(a b a)"). Doing so would be very |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 420 | straight-forward with the mechanics we have already used above.</p> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 421 | |
| 422 | <div class="doc_code"> |
| 423 | <pre> |
| 424 | Function *FunctionAST::Codegen() { |
| 425 | NamedValues.clear(); |
| 426 | |
| 427 | Function *TheFunction = Proto->Codegen(); |
| 428 | if (TheFunction == 0) |
| 429 | return 0; |
| 430 | </pre> |
| 431 | </div> |
| 432 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 433 | <p>Code generation for function definitions starts out simply enough: we just |
| 434 | codegen the prototype (Proto) and verify that it is ok. We then clear out the |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 435 | <tt>NamedValues</tt> map to make sure that there isn't anything in it from the |
Chris Lattner | a1cd224 | 2007-11-06 05:07:30 +0000 | [diff] [blame] | 436 | last function we compiled. Code generation of the prototype ensures that there |
| 437 | is an LLVM Function object that is ready to go for us.</p> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 438 | |
| 439 | <div class="doc_code"> |
| 440 | <pre> |
| 441 | // Create a new basic block to start insertion into. |
Gabor Greif | df7d2b4 | 2008-04-19 22:25:09 +0000 | [diff] [blame] | 442 | BasicBlock *BB = BasicBlock::Create("entry", TheFunction); |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 443 | Builder.SetInsertPoint(BB); |
| 444 | |
| 445 | if (Value *RetVal = Body->Codegen()) { |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 446 | </pre> |
| 447 | </div> |
| 448 | |
| 449 | <p>Now we get to the point where the <tt>Builder</tt> is set up. The first |
| 450 | line creates a new <a href="http://en.wikipedia.org/wiki/Basic_block">basic |
| 451 | block</a> (named "entry"), which is inserted into <tt>TheFunction</tt>. The |
| 452 | second line then tells the builder that new instructions should be inserted into |
| 453 | the end of the new basic block. Basic blocks in LLVM are an important part |
| 454 | of functions that define the <a |
| 455 | href="http://en.wikipedia.org/wiki/Control_flow_graph">Control Flow Graph</a>. |
| 456 | Since we don't have any control flow, our functions will only contain one |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 457 | block at this point. We'll fix this in <a href="LangImpl5.html">Chapter 5</a> :).</p> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 458 | |
Chris Lattner | d9b8616 | 2007-10-25 04:30:35 +0000 | [diff] [blame] | 459 | <div class="doc_code"> |
| 460 | <pre> |
| 461 | if (Value *RetVal = Body->Codegen()) { |
| 462 | // Finish off the function. |
| 463 | Builder.CreateRet(RetVal); |
| 464 | |
| 465 | // Validate the generated code, checking for consistency. |
| 466 | verifyFunction(*TheFunction); |
| 467 | return TheFunction; |
| 468 | } |
| 469 | </pre> |
| 470 | </div> |
| 471 | |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 472 | <p>Once the insertion point is set up, we call the <tt>CodeGen()</tt> method for |
| 473 | the root expression of the function. If no error happens, this emits code to |
| 474 | compute the expression into the entry block and returns the value that was |
| 475 | computed. Assuming no error, we then create an LLVM <a |
Chris Lattner | d9b8616 | 2007-10-25 04:30:35 +0000 | [diff] [blame] | 476 | href="../LangRef.html#i_ret">ret instruction</a>, which completes the function. |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 477 | Once the function is built, we call <tt>verifyFunction</tt>, which |
Chris Lattner | d9b8616 | 2007-10-25 04:30:35 +0000 | [diff] [blame] | 478 | is provided by LLVM. This function does a variety of consistency checks on the |
| 479 | generated code, to determine if our compiler is doing everything right. Using |
| 480 | this is important: it can catch a lot of bugs. Once the function is finished |
| 481 | and validated, we return it.</p> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 482 | |
| 483 | <div class="doc_code"> |
| 484 | <pre> |
| 485 | // Error reading body, remove function. |
| 486 | TheFunction->eraseFromParent(); |
| 487 | return 0; |
| 488 | } |
| 489 | </pre> |
| 490 | </div> |
| 491 | |
| 492 | <p>The only piece left here is handling of the error case. For simplicity, we |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 493 | handle this by merely deleting the function we produced with the |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 494 | <tt>eraseFromParent</tt> method. This allows the user to redefine a function |
| 495 | that they incorrectly typed in before: if we didn't delete it, it would live in |
| 496 | the symbol table, with a body, preventing future redefinition.</p> |
| 497 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 498 | <p>This code does have a bug, though. Since the <tt>PrototypeAST::Codegen</tt> |
| 499 | can return a previously defined forward declaration, our code can actually delete |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 500 | a forward declaration. There are a number of ways to fix this bug, see what you |
| 501 | can come up with! Here is a testcase:</p> |
| 502 | |
| 503 | <div class="doc_code"> |
| 504 | <pre> |
| 505 | extern foo(a b); # ok, defines foo. |
| 506 | def foo(a b) c; # error, 'c' is invalid. |
| 507 | def bar() foo(1, 2); # error, unknown function "foo" |
| 508 | </pre> |
| 509 | </div> |
| 510 | |
| 511 | </div> |
| 512 | |
| 513 | <!-- *********************************************************************** --> |
| 514 | <div class="doc_section"><a name="driver">Driver Changes and |
| 515 | Closing Thoughts</a></div> |
| 516 | <!-- *********************************************************************** --> |
| 517 | |
| 518 | <div class="doc_text"> |
| 519 | |
| 520 | <p> |
| 521 | For now, code generation to LLVM doesn't really get us much, except that we can |
| 522 | look at the pretty IR calls. The sample code inserts calls to Codegen into the |
| 523 | "<tt>HandleDefinition</tt>", "<tt>HandleExtern</tt>" etc functions, and then |
| 524 | dumps out the LLVM IR. This gives a nice way to look at the LLVM IR for simple |
| 525 | functions. For example: |
| 526 | </p> |
| 527 | |
| 528 | <div class="doc_code"> |
| 529 | <pre> |
| 530 | ready> <b>4+5</b>; |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 531 | Read top-level expression: |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 532 | define double @""() { |
| 533 | entry: |
| 534 | %addtmp = add double 4.000000e+00, 5.000000e+00 |
| 535 | ret double %addtmp |
| 536 | } |
| 537 | </pre> |
| 538 | </div> |
| 539 | |
| 540 | <p>Note how the parser turns the top-level expression into anonymous functions |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 541 | for us. This will be handy when we add <a href="LangImpl4.html#jit">JIT |
| 542 | support</a> in the next chapter. Also note that the code is very literally |
| 543 | transcribed, no optimizations are being performed. We will |
| 544 | <a href="LangImpl4.html#trivialconstfold">add optimizations</a> explicitly in |
| 545 | the next chapter.</p> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 546 | |
| 547 | <div class="doc_code"> |
| 548 | <pre> |
| 549 | ready> <b>def foo(a b) a*a + 2*a*b + b*b;</b> |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 550 | Read function definition: |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 551 | define double @foo(double %a, double %b) { |
| 552 | entry: |
| 553 | %multmp = mul double %a, %a |
| 554 | %multmp1 = mul double 2.000000e+00, %a |
| 555 | %multmp2 = mul double %multmp1, %b |
| 556 | %addtmp = add double %multmp, %multmp2 |
| 557 | %multmp3 = mul double %b, %b |
| 558 | %addtmp4 = add double %addtmp, %multmp3 |
| 559 | ret double %addtmp4 |
| 560 | } |
| 561 | </pre> |
| 562 | </div> |
| 563 | |
| 564 | <p>This shows some simple arithmetic. Notice the striking similarity to the |
| 565 | LLVM builder calls that we use to create the instructions.</p> |
| 566 | |
| 567 | <div class="doc_code"> |
| 568 | <pre> |
| 569 | ready> <b>def bar(a) foo(a, 4.0) + bar(31337);</b> |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 570 | Read function definition: |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 571 | define double @bar(double %a) { |
| 572 | entry: |
| 573 | %calltmp = call double @foo( double %a, double 4.000000e+00 ) |
| 574 | %calltmp1 = call double @bar( double 3.133700e+04 ) |
| 575 | %addtmp = add double %calltmp, %calltmp1 |
| 576 | ret double %addtmp |
| 577 | } |
| 578 | </pre> |
| 579 | </div> |
| 580 | |
Chris Lattner | fc60ab0 | 2007-11-05 17:39:26 +0000 | [diff] [blame] | 581 | <p>This shows some function calls. Note that this function will take a long |
| 582 | time to execute if you call it. In the future we'll add conditional control |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 583 | flow to actually make recursion useful :).</p> |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 584 | |
| 585 | <div class="doc_code"> |
| 586 | <pre> |
| 587 | ready> <b>extern cos(x);</b> |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 588 | Read extern: |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 589 | declare double @cos(double) |
| 590 | |
| 591 | ready> <b>cos(1.234);</b> |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 592 | Read top-level expression: |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 593 | define double @""() { |
| 594 | entry: |
Chris Lattner | 8eef4b2 | 2007-10-23 06:30:50 +0000 | [diff] [blame] | 595 | %calltmp = call double @cos( double 1.234000e+00 ) |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 596 | ret double %calltmp |
| 597 | } |
| 598 | </pre> |
| 599 | </div> |
| 600 | |
| 601 | <p>This shows an extern for the libm "cos" function, and a call to it.</p> |
| 602 | |
| 603 | |
| 604 | <div class="doc_code"> |
| 605 | <pre> |
| 606 | ready> <b>^D</b> |
| 607 | ; ModuleID = 'my cool jit' |
| 608 | |
| 609 | define double @""() { |
| 610 | entry: |
| 611 | %addtmp = add double 4.000000e+00, 5.000000e+00 |
| 612 | ret double %addtmp |
| 613 | } |
| 614 | |
| 615 | define double @foo(double %a, double %b) { |
| 616 | entry: |
| 617 | %multmp = mul double %a, %a |
| 618 | %multmp1 = mul double 2.000000e+00, %a |
| 619 | %multmp2 = mul double %multmp1, %b |
| 620 | %addtmp = add double %multmp, %multmp2 |
| 621 | %multmp3 = mul double %b, %b |
| 622 | %addtmp4 = add double %addtmp, %multmp3 |
| 623 | ret double %addtmp4 |
| 624 | } |
| 625 | |
| 626 | define double @bar(double %a) { |
| 627 | entry: |
| 628 | %calltmp = call double @foo( double %a, double 4.000000e+00 ) |
| 629 | %calltmp1 = call double @bar( double 3.133700e+04 ) |
| 630 | %addtmp = add double %calltmp, %calltmp1 |
| 631 | ret double %addtmp |
| 632 | } |
| 633 | |
| 634 | declare double @cos(double) |
| 635 | |
| 636 | define double @""() { |
| 637 | entry: |
| 638 | %calltmp = call double @cos( double 1.234000e+00 ) |
| 639 | ret double %calltmp |
| 640 | } |
| 641 | </pre> |
| 642 | </div> |
| 643 | |
| 644 | <p>When you quit the current demo, it dumps out the IR for the entire module |
| 645 | generated. Here you can see the big picture with all the functions referencing |
| 646 | each other.</p> |
| 647 | |
Chris Lattner | 41fcea3 | 2007-11-13 07:06:30 +0000 | [diff] [blame] | 648 | <p>This wraps up the third chapter of the Kaleidoscope tutorial. Up next, we'll |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 649 | describe how to <a href="LangImpl4.html">add JIT codegen and optimizer |
| 650 | support</a> to this so we can actually start running code!</p> |
| 651 | |
| 652 | </div> |
| 653 | |
| 654 | |
| 655 | <!-- *********************************************************************** --> |
| 656 | <div class="doc_section"><a name="code">Full Code Listing</a></div> |
| 657 | <!-- *********************************************************************** --> |
| 658 | |
| 659 | <div class="doc_text"> |
| 660 | |
| 661 | <p> |
| 662 | Here is the complete code listing for our running example, enhanced with the |
| 663 | LLVM code generator. Because this uses the LLVM libraries, we need to link |
| 664 | them in. To do this, we use the <a |
| 665 | href="http://llvm.org/cmds/llvm-config.html">llvm-config</a> tool to inform |
| 666 | our makefile/command line about which options to use:</p> |
| 667 | |
| 668 | <div class="doc_code"> |
| 669 | <pre> |
| 670 | # Compile |
Chris Lattner | d96b159 | 2007-11-07 05:07:10 +0000 | [diff] [blame] | 671 | g++ -g -O3 toy.cpp `llvm-config --cppflags --ldflags --libs core` -o toy |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 672 | # Run |
| 673 | ./toy |
| 674 | </pre> |
| 675 | </div> |
| 676 | |
| 677 | <p>Here is the code:</p> |
| 678 | |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 679 | <div class="doc_code"> |
| 680 | <pre> |
| 681 | // To build this: |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 682 | // See example below. |
| 683 | |
| 684 | #include "llvm/DerivedTypes.h" |
Owen Anderson | d1fbd14 | 2009-07-08 20:50:47 +0000 | [diff] [blame] | 685 | #include "llvm/LLVMContext.h" |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 686 | #include "llvm/Module.h" |
Chris Lattner | d9b8616 | 2007-10-25 04:30:35 +0000 | [diff] [blame] | 687 | #include "llvm/Analysis/Verifier.h" |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 688 | #include "llvm/Support/IRBuilder.h" |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 689 | #include <cstdio> |
| 690 | #include <string> |
| 691 | #include <map> |
| 692 | #include <vector> |
| 693 | using namespace llvm; |
| 694 | |
| 695 | //===----------------------------------------------------------------------===// |
| 696 | // Lexer |
| 697 | //===----------------------------------------------------------------------===// |
| 698 | |
| 699 | // The lexer returns tokens [0-255] if it is an unknown character, otherwise one |
| 700 | // of these for known things. |
| 701 | enum Token { |
| 702 | tok_eof = -1, |
| 703 | |
| 704 | // commands |
| 705 | tok_def = -2, tok_extern = -3, |
| 706 | |
| 707 | // primary |
| 708 | tok_identifier = -4, tok_number = -5, |
| 709 | }; |
| 710 | |
| 711 | static std::string IdentifierStr; // Filled in if tok_identifier |
| 712 | static double NumVal; // Filled in if tok_number |
| 713 | |
| 714 | /// gettok - Return the next token from standard input. |
| 715 | static int gettok() { |
| 716 | static int LastChar = ' '; |
| 717 | |
| 718 | // Skip any whitespace. |
| 719 | while (isspace(LastChar)) |
| 720 | LastChar = getchar(); |
| 721 | |
| 722 | if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* |
| 723 | IdentifierStr = LastChar; |
| 724 | while (isalnum((LastChar = getchar()))) |
| 725 | IdentifierStr += LastChar; |
| 726 | |
| 727 | if (IdentifierStr == "def") return tok_def; |
| 728 | if (IdentifierStr == "extern") return tok_extern; |
| 729 | return tok_identifier; |
| 730 | } |
| 731 | |
| 732 | if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ |
| 733 | std::string NumStr; |
| 734 | do { |
| 735 | NumStr += LastChar; |
| 736 | LastChar = getchar(); |
| 737 | } while (isdigit(LastChar) || LastChar == '.'); |
| 738 | |
| 739 | NumVal = strtod(NumStr.c_str(), 0); |
| 740 | return tok_number; |
| 741 | } |
| 742 | |
| 743 | if (LastChar == '#') { |
| 744 | // Comment until end of line. |
| 745 | do LastChar = getchar(); |
Chris Lattner | c80c23f | 2007-12-02 22:46:01 +0000 | [diff] [blame] | 746 | while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 747 | |
| 748 | if (LastChar != EOF) |
| 749 | return gettok(); |
| 750 | } |
| 751 | |
| 752 | // Check for end of file. Don't eat the EOF. |
| 753 | if (LastChar == EOF) |
| 754 | return tok_eof; |
| 755 | |
| 756 | // Otherwise, just return the character as its ascii value. |
| 757 | int ThisChar = LastChar; |
| 758 | LastChar = getchar(); |
| 759 | return ThisChar; |
| 760 | } |
| 761 | |
| 762 | //===----------------------------------------------------------------------===// |
| 763 | // Abstract Syntax Tree (aka Parse Tree) |
| 764 | //===----------------------------------------------------------------------===// |
| 765 | |
| 766 | /// ExprAST - Base class for all expression nodes. |
| 767 | class ExprAST { |
| 768 | public: |
| 769 | virtual ~ExprAST() {} |
| 770 | virtual Value *Codegen() = 0; |
| 771 | }; |
| 772 | |
| 773 | /// NumberExprAST - Expression class for numeric literals like "1.0". |
| 774 | class NumberExprAST : public ExprAST { |
| 775 | double Val; |
| 776 | public: |
Chris Lattner | 28571ed | 2007-10-23 04:27:44 +0000 | [diff] [blame] | 777 | explicit NumberExprAST(double val) : Val(val) {} |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 778 | virtual Value *Codegen(); |
| 779 | }; |
| 780 | |
| 781 | /// VariableExprAST - Expression class for referencing a variable, like "a". |
| 782 | class VariableExprAST : public ExprAST { |
| 783 | std::string Name; |
| 784 | public: |
Chris Lattner | 28571ed | 2007-10-23 04:27:44 +0000 | [diff] [blame] | 785 | explicit VariableExprAST(const std::string &name) : Name(name) {} |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 786 | virtual Value *Codegen(); |
| 787 | }; |
| 788 | |
| 789 | /// BinaryExprAST - Expression class for a binary operator. |
| 790 | class BinaryExprAST : public ExprAST { |
| 791 | char Op; |
| 792 | ExprAST *LHS, *RHS; |
| 793 | public: |
| 794 | BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) |
| 795 | : Op(op), LHS(lhs), RHS(rhs) {} |
| 796 | virtual Value *Codegen(); |
| 797 | }; |
| 798 | |
| 799 | /// CallExprAST - Expression class for function calls. |
| 800 | class CallExprAST : public ExprAST { |
| 801 | std::string Callee; |
| 802 | std::vector<ExprAST*> Args; |
| 803 | public: |
| 804 | CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) |
| 805 | : Callee(callee), Args(args) {} |
| 806 | virtual Value *Codegen(); |
| 807 | }; |
| 808 | |
| 809 | /// PrototypeAST - This class represents the "prototype" for a function, |
| 810 | /// which captures its argument names as well as if it is an operator. |
| 811 | class PrototypeAST { |
| 812 | std::string Name; |
| 813 | std::vector<std::string> Args; |
| 814 | public: |
| 815 | PrototypeAST(const std::string &name, const std::vector<std::string> &args) |
| 816 | : Name(name), Args(args) {} |
| 817 | |
| 818 | Function *Codegen(); |
| 819 | }; |
| 820 | |
| 821 | /// FunctionAST - This class represents a function definition itself. |
| 822 | class FunctionAST { |
| 823 | PrototypeAST *Proto; |
| 824 | ExprAST *Body; |
| 825 | public: |
| 826 | FunctionAST(PrototypeAST *proto, ExprAST *body) |
| 827 | : Proto(proto), Body(body) {} |
| 828 | |
| 829 | Function *Codegen(); |
| 830 | }; |
| 831 | |
| 832 | //===----------------------------------------------------------------------===// |
| 833 | // Parser |
| 834 | //===----------------------------------------------------------------------===// |
| 835 | |
| 836 | /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current |
| 837 | /// token the parser it looking at. getNextToken reads another token from the |
| 838 | /// lexer and updates CurTok with its results. |
| 839 | static int CurTok; |
| 840 | static int getNextToken() { |
| 841 | return CurTok = gettok(); |
| 842 | } |
| 843 | |
| 844 | /// BinopPrecedence - This holds the precedence for each binary operator that is |
| 845 | /// defined. |
| 846 | static std::map<char, int> BinopPrecedence; |
| 847 | |
| 848 | /// GetTokPrecedence - Get the precedence of the pending binary operator token. |
| 849 | static int GetTokPrecedence() { |
| 850 | if (!isascii(CurTok)) |
| 851 | return -1; |
| 852 | |
| 853 | // Make sure it's a declared binop. |
| 854 | int TokPrec = BinopPrecedence[CurTok]; |
| 855 | if (TokPrec <= 0) return -1; |
| 856 | return TokPrec; |
| 857 | } |
| 858 | |
| 859 | /// Error* - These are little helper functions for error handling. |
| 860 | ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} |
| 861 | PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } |
| 862 | FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } |
| 863 | |
| 864 | static ExprAST *ParseExpression(); |
| 865 | |
| 866 | /// identifierexpr |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 867 | /// ::= identifier |
| 868 | /// ::= identifier '(' expression* ')' |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 869 | static ExprAST *ParseIdentifierExpr() { |
| 870 | std::string IdName = IdentifierStr; |
| 871 | |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 872 | getNextToken(); // eat identifier. |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 873 | |
| 874 | if (CurTok != '(') // Simple variable ref. |
| 875 | return new VariableExprAST(IdName); |
| 876 | |
| 877 | // Call. |
| 878 | getNextToken(); // eat ( |
| 879 | std::vector<ExprAST*> Args; |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 880 | if (CurTok != ')') { |
| 881 | while (1) { |
| 882 | ExprAST *Arg = ParseExpression(); |
| 883 | if (!Arg) return 0; |
| 884 | Args.push_back(Arg); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 885 | |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 886 | if (CurTok == ')') break; |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 887 | |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 888 | if (CurTok != ',') |
Chris Lattner | 6c4be9c | 2008-04-14 16:44:41 +0000 | [diff] [blame] | 889 | return Error("Expected ')' or ',' in argument list"); |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 890 | getNextToken(); |
| 891 | } |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 892 | } |
| 893 | |
| 894 | // Eat the ')'. |
| 895 | getNextToken(); |
| 896 | |
| 897 | return new CallExprAST(IdName, Args); |
| 898 | } |
| 899 | |
| 900 | /// numberexpr ::= number |
| 901 | static ExprAST *ParseNumberExpr() { |
| 902 | ExprAST *Result = new NumberExprAST(NumVal); |
| 903 | getNextToken(); // consume the number |
| 904 | return Result; |
| 905 | } |
| 906 | |
| 907 | /// parenexpr ::= '(' expression ')' |
| 908 | static ExprAST *ParseParenExpr() { |
| 909 | getNextToken(); // eat (. |
| 910 | ExprAST *V = ParseExpression(); |
| 911 | if (!V) return 0; |
| 912 | |
| 913 | if (CurTok != ')') |
| 914 | return Error("expected ')'"); |
| 915 | getNextToken(); // eat ). |
| 916 | return V; |
| 917 | } |
| 918 | |
| 919 | /// primary |
| 920 | /// ::= identifierexpr |
| 921 | /// ::= numberexpr |
| 922 | /// ::= parenexpr |
| 923 | static ExprAST *ParsePrimary() { |
| 924 | switch (CurTok) { |
| 925 | default: return Error("unknown token when expecting an expression"); |
| 926 | case tok_identifier: return ParseIdentifierExpr(); |
| 927 | case tok_number: return ParseNumberExpr(); |
| 928 | case '(': return ParseParenExpr(); |
| 929 | } |
| 930 | } |
| 931 | |
| 932 | /// binoprhs |
| 933 | /// ::= ('+' primary)* |
| 934 | static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { |
| 935 | // If this is a binop, find its precedence. |
| 936 | while (1) { |
| 937 | int TokPrec = GetTokPrecedence(); |
| 938 | |
| 939 | // If this is a binop that binds at least as tightly as the current binop, |
| 940 | // consume it, otherwise we are done. |
| 941 | if (TokPrec < ExprPrec) |
| 942 | return LHS; |
| 943 | |
| 944 | // Okay, we know this is a binop. |
| 945 | int BinOp = CurTok; |
| 946 | getNextToken(); // eat binop |
| 947 | |
| 948 | // Parse the primary expression after the binary operator. |
| 949 | ExprAST *RHS = ParsePrimary(); |
| 950 | if (!RHS) return 0; |
| 951 | |
| 952 | // If BinOp binds less tightly with RHS than the operator after RHS, let |
| 953 | // the pending operator take RHS as its LHS. |
| 954 | int NextPrec = GetTokPrecedence(); |
| 955 | if (TokPrec < NextPrec) { |
| 956 | RHS = ParseBinOpRHS(TokPrec+1, RHS); |
| 957 | if (RHS == 0) return 0; |
| 958 | } |
| 959 | |
| 960 | // Merge LHS/RHS. |
| 961 | LHS = new BinaryExprAST(BinOp, LHS, RHS); |
| 962 | } |
| 963 | } |
| 964 | |
| 965 | /// expression |
| 966 | /// ::= primary binoprhs |
| 967 | /// |
| 968 | static ExprAST *ParseExpression() { |
| 969 | ExprAST *LHS = ParsePrimary(); |
| 970 | if (!LHS) return 0; |
| 971 | |
| 972 | return ParseBinOpRHS(0, LHS); |
| 973 | } |
| 974 | |
| 975 | /// prototype |
| 976 | /// ::= id '(' id* ')' |
| 977 | static PrototypeAST *ParsePrototype() { |
| 978 | if (CurTok != tok_identifier) |
| 979 | return ErrorP("Expected function name in prototype"); |
| 980 | |
| 981 | std::string FnName = IdentifierStr; |
| 982 | getNextToken(); |
| 983 | |
| 984 | if (CurTok != '(') |
| 985 | return ErrorP("Expected '(' in prototype"); |
| 986 | |
| 987 | std::vector<std::string> ArgNames; |
| 988 | while (getNextToken() == tok_identifier) |
| 989 | ArgNames.push_back(IdentifierStr); |
| 990 | if (CurTok != ')') |
| 991 | return ErrorP("Expected ')' in prototype"); |
| 992 | |
| 993 | // success. |
| 994 | getNextToken(); // eat ')'. |
| 995 | |
| 996 | return new PrototypeAST(FnName, ArgNames); |
| 997 | } |
| 998 | |
| 999 | /// definition ::= 'def' prototype expression |
| 1000 | static FunctionAST *ParseDefinition() { |
| 1001 | getNextToken(); // eat def. |
| 1002 | PrototypeAST *Proto = ParsePrototype(); |
| 1003 | if (Proto == 0) return 0; |
| 1004 | |
| 1005 | if (ExprAST *E = ParseExpression()) |
| 1006 | return new FunctionAST(Proto, E); |
| 1007 | return 0; |
| 1008 | } |
| 1009 | |
| 1010 | /// toplevelexpr ::= expression |
| 1011 | static FunctionAST *ParseTopLevelExpr() { |
| 1012 | if (ExprAST *E = ParseExpression()) { |
| 1013 | // Make an anonymous proto. |
| 1014 | PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); |
| 1015 | return new FunctionAST(Proto, E); |
| 1016 | } |
| 1017 | return 0; |
| 1018 | } |
| 1019 | |
| 1020 | /// external ::= 'extern' prototype |
| 1021 | static PrototypeAST *ParseExtern() { |
| 1022 | getNextToken(); // eat extern. |
| 1023 | return ParsePrototype(); |
| 1024 | } |
| 1025 | |
| 1026 | //===----------------------------------------------------------------------===// |
| 1027 | // Code Generation |
| 1028 | //===----------------------------------------------------------------------===// |
| 1029 | |
| 1030 | static Module *TheModule; |
Gabor Greif | d6c1ed0 | 2009-03-11 19:51:07 +0000 | [diff] [blame] | 1031 | static IRBuilder<> Builder; |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1032 | static std::map<std::string, Value*> NamedValues; |
| 1033 | |
| 1034 | Value *ErrorV(const char *Str) { Error(Str); return 0; } |
| 1035 | |
| 1036 | Value *NumberExprAST::Codegen() { |
Owen Anderson | 914e50c | 2009-07-16 19:05:41 +0000 | [diff] [blame^] | 1037 | return getGlobalContext().getConstantFP(APFloat(Val)); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1038 | } |
| 1039 | |
| 1040 | Value *VariableExprAST::Codegen() { |
| 1041 | // Look this variable up in the function. |
| 1042 | Value *V = NamedValues[Name]; |
| 1043 | return V ? V : ErrorV("Unknown variable name"); |
| 1044 | } |
| 1045 | |
| 1046 | Value *BinaryExprAST::Codegen() { |
| 1047 | Value *L = LHS->Codegen(); |
| 1048 | Value *R = RHS->Codegen(); |
| 1049 | if (L == 0 || R == 0) return 0; |
| 1050 | |
| 1051 | switch (Op) { |
| 1052 | case '+': return Builder.CreateAdd(L, R, "addtmp"); |
| 1053 | case '-': return Builder.CreateSub(L, R, "subtmp"); |
| 1054 | case '*': return Builder.CreateMul(L, R, "multmp"); |
| 1055 | case '<': |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 1056 | L = Builder.CreateFCmpULT(L, R, "cmptmp"); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1057 | // Convert bool 0/1 to double 0.0 or 1.0 |
| 1058 | return Builder.CreateUIToFP(L, Type::DoubleTy, "booltmp"); |
| 1059 | default: return ErrorV("invalid binary operator"); |
| 1060 | } |
| 1061 | } |
| 1062 | |
| 1063 | Value *CallExprAST::Codegen() { |
| 1064 | // Look up the name in the global module table. |
| 1065 | Function *CalleeF = TheModule->getFunction(Callee); |
| 1066 | if (CalleeF == 0) |
| 1067 | return ErrorV("Unknown function referenced"); |
| 1068 | |
| 1069 | // If argument mismatch error. |
| 1070 | if (CalleeF->arg_size() != Args.size()) |
| 1071 | return ErrorV("Incorrect # arguments passed"); |
| 1072 | |
| 1073 | std::vector<Value*> ArgsV; |
| 1074 | for (unsigned i = 0, e = Args.size(); i != e; ++i) { |
| 1075 | ArgsV.push_back(Args[i]->Codegen()); |
| 1076 | if (ArgsV.back() == 0) return 0; |
| 1077 | } |
| 1078 | |
| 1079 | return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); |
| 1080 | } |
| 1081 | |
| 1082 | Function *PrototypeAST::Codegen() { |
| 1083 | // Make the function type: double(double,double) etc. |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 1084 | std::vector<const Type*> Doubles(Args.size(), Type::DoubleTy); |
Owen Anderson | 914e50c | 2009-07-16 19:05:41 +0000 | [diff] [blame^] | 1085 | FunctionType *FT = getGlobalContext().getFunctionType(Type::DoubleTy, Doubles, false); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1086 | |
Gabor Greif | df7d2b4 | 2008-04-19 22:25:09 +0000 | [diff] [blame] | 1087 | Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1088 | |
| 1089 | // If F conflicted, there was already something named 'Name'. If it has a |
| 1090 | // body, don't allow redefinition or reextern. |
| 1091 | if (F->getName() != Name) { |
| 1092 | // Delete the one we just made and get the existing one. |
| 1093 | F->eraseFromParent(); |
| 1094 | F = TheModule->getFunction(Name); |
| 1095 | |
| 1096 | // If F already has a body, reject this. |
| 1097 | if (!F->empty()) { |
| 1098 | ErrorF("redefinition of function"); |
| 1099 | return 0; |
| 1100 | } |
| 1101 | |
| 1102 | // If F took a different number of args, reject. |
| 1103 | if (F->arg_size() != Args.size()) { |
| 1104 | ErrorF("redefinition of function with different # args"); |
| 1105 | return 0; |
| 1106 | } |
| 1107 | } |
| 1108 | |
| 1109 | // Set names for all arguments. |
| 1110 | unsigned Idx = 0; |
| 1111 | for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); |
| 1112 | ++AI, ++Idx) { |
| 1113 | AI->setName(Args[Idx]); |
| 1114 | |
| 1115 | // Add arguments to variable symbol table. |
| 1116 | NamedValues[Args[Idx]] = AI; |
| 1117 | } |
| 1118 | |
| 1119 | return F; |
| 1120 | } |
| 1121 | |
| 1122 | Function *FunctionAST::Codegen() { |
| 1123 | NamedValues.clear(); |
| 1124 | |
| 1125 | Function *TheFunction = Proto->Codegen(); |
| 1126 | if (TheFunction == 0) |
| 1127 | return 0; |
| 1128 | |
| 1129 | // Create a new basic block to start insertion into. |
Gabor Greif | df7d2b4 | 2008-04-19 22:25:09 +0000 | [diff] [blame] | 1130 | BasicBlock *BB = BasicBlock::Create("entry", TheFunction); |
Chris Lattner | 35abbf5 | 2007-10-23 06:23:57 +0000 | [diff] [blame] | 1131 | Builder.SetInsertPoint(BB); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1132 | |
| 1133 | if (Value *RetVal = Body->Codegen()) { |
| 1134 | // Finish off the function. |
| 1135 | Builder.CreateRet(RetVal); |
Chris Lattner | d9b8616 | 2007-10-25 04:30:35 +0000 | [diff] [blame] | 1136 | |
| 1137 | // Validate the generated code, checking for consistency. |
| 1138 | verifyFunction(*TheFunction); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1139 | return TheFunction; |
| 1140 | } |
| 1141 | |
| 1142 | // Error reading body, remove function. |
| 1143 | TheFunction->eraseFromParent(); |
| 1144 | return 0; |
| 1145 | } |
| 1146 | |
| 1147 | //===----------------------------------------------------------------------===// |
| 1148 | // Top-Level parsing and JIT Driver |
| 1149 | //===----------------------------------------------------------------------===// |
| 1150 | |
| 1151 | static void HandleDefinition() { |
| 1152 | if (FunctionAST *F = ParseDefinition()) { |
| 1153 | if (Function *LF = F->Codegen()) { |
| 1154 | fprintf(stderr, "Read function definition:"); |
| 1155 | LF->dump(); |
| 1156 | } |
| 1157 | } else { |
| 1158 | // Skip token for error recovery. |
| 1159 | getNextToken(); |
| 1160 | } |
| 1161 | } |
| 1162 | |
| 1163 | static void HandleExtern() { |
| 1164 | if (PrototypeAST *P = ParseExtern()) { |
| 1165 | if (Function *F = P->Codegen()) { |
| 1166 | fprintf(stderr, "Read extern: "); |
| 1167 | F->dump(); |
| 1168 | } |
| 1169 | } else { |
| 1170 | // Skip token for error recovery. |
| 1171 | getNextToken(); |
| 1172 | } |
| 1173 | } |
| 1174 | |
| 1175 | static void HandleTopLevelExpression() { |
| 1176 | // Evaluate a top level expression into an anonymous function. |
| 1177 | if (FunctionAST *F = ParseTopLevelExpr()) { |
| 1178 | if (Function *LF = F->Codegen()) { |
| 1179 | fprintf(stderr, "Read top-level expression:"); |
| 1180 | LF->dump(); |
| 1181 | } |
| 1182 | } else { |
| 1183 | // Skip token for error recovery. |
| 1184 | getNextToken(); |
| 1185 | } |
| 1186 | } |
| 1187 | |
| 1188 | /// top ::= definition | external | expression | ';' |
| 1189 | static void MainLoop() { |
| 1190 | while (1) { |
| 1191 | fprintf(stderr, "ready> "); |
| 1192 | switch (CurTok) { |
| 1193 | case tok_eof: return; |
| 1194 | case ';': getNextToken(); break; // ignore top level semicolons. |
| 1195 | case tok_def: HandleDefinition(); break; |
| 1196 | case tok_extern: HandleExtern(); break; |
| 1197 | default: HandleTopLevelExpression(); break; |
| 1198 | } |
| 1199 | } |
| 1200 | } |
| 1201 | |
| 1202 | |
| 1203 | |
| 1204 | //===----------------------------------------------------------------------===// |
| 1205 | // "Library" functions that can be "extern'd" from user code. |
| 1206 | //===----------------------------------------------------------------------===// |
| 1207 | |
| 1208 | /// putchard - putchar that takes a double and returns 0. |
| 1209 | extern "C" |
| 1210 | double putchard(double X) { |
| 1211 | putchar((char)X); |
| 1212 | return 0; |
| 1213 | } |
| 1214 | |
| 1215 | //===----------------------------------------------------------------------===// |
| 1216 | // Main driver code. |
| 1217 | //===----------------------------------------------------------------------===// |
| 1218 | |
| 1219 | int main() { |
Owen Anderson | d1fbd14 | 2009-07-08 20:50:47 +0000 | [diff] [blame] | 1220 | TheModule = new Module("my cool jit", getGlobalContext()); |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1221 | |
| 1222 | // Install standard binary operators. |
| 1223 | // 1 is lowest precedence. |
| 1224 | BinopPrecedence['<'] = 10; |
| 1225 | BinopPrecedence['+'] = 20; |
| 1226 | BinopPrecedence['-'] = 20; |
| 1227 | BinopPrecedence['*'] = 40; // highest. |
| 1228 | |
| 1229 | // Prime the first token. |
| 1230 | fprintf(stderr, "ready> "); |
| 1231 | getNextToken(); |
| 1232 | |
| 1233 | MainLoop(); |
| 1234 | TheModule->dump(); |
| 1235 | return 0; |
| 1236 | } |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1237 | </pre> |
| 1238 | </div> |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 1239 | <a href="LangImpl4.html">Next: Adding JIT and Optimizer Support</a> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1240 | </div> |
| 1241 | |
| 1242 | <!-- *********************************************************************** --> |
| 1243 | <hr> |
| 1244 | <address> |
| 1245 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
| 1246 | src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> |
| 1247 | <a href="http://validator.w3.org/check/referer"><img |
Chris Lattner | 8eef4b2 | 2007-10-23 06:30:50 +0000 | [diff] [blame] | 1248 | src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a> |
Chris Lattner | 2e90204 | 2007-10-22 07:01:42 +0000 | [diff] [blame] | 1249 | |
| 1250 | <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
| 1251 | <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br> |
| 1252 | Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $ |
| 1253 | </address> |
| 1254 | </body> |
| 1255 | </html> |