Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +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> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 6 | <title>Kaleidoscope: Extending the Language: User-defined Operators</title> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 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 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 14 | <div class="doc_title">Kaleidoscope: Extending the Language: User-defined Operators</div> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 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 6 |
| 19 | <ol> |
| 20 | <li><a href="#intro">Chapter 6 Introduction</a></li> |
| 21 | <li><a href="#idea">User-defined Operators: the Idea</a></li> |
| 22 | <li><a href="#binary">User-defined Binary Operators</a></li> |
| 23 | <li><a href="#unary">User-defined Unary Operators</a></li> |
| 24 | <li><a href="#example">Kicking the Tires</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="LangImpl7.html">Chapter 7</a>: Extending the Language: Mutable |
| 29 | Variables / SSA Construction</li> |
Chris Lattner | 128eb86 | 2007-11-05 19:06:59 +0000 | [diff] [blame] | 30 | </ul> |
| 31 | |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +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 6 Introduction</a></div> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +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 6 of the "<a href="index.html">Implementing a language |
| 43 | with LLVM</a>" tutorial. At this point in our tutorial, we now have a fully |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 44 | functional language that is fairly minimal, but also useful. There |
| 45 | is still one big problem with it, however. Our language doesn't have many |
| 46 | useful operators (like division, logical negation, or even any comparisons |
| 47 | besides less-than).</p> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 48 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 49 | <p>This chapter of the tutorial takes a wild digression into adding user-defined |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 50 | operators to the simple and beautiful Kaleidoscope language. This digression now gives |
| 51 | us a simple and ugly language in some ways, but also a powerful one at the same time. |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 52 | One of the great things about creating your own language is that you get to |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 53 | decide what is good or bad. In this tutorial we'll assume that it is okay to |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 54 | use this as a way to show some interesting parsing techniques.</p> |
| 55 | |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 56 | <p>At the end of this tutorial, we'll run through an example Kaleidoscope |
| 57 | application that <a href="#example">renders the Mandelbrot set</a>. This gives |
| 58 | an example of what you can build with Kaleidoscope and its feature set.</p> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 59 | |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 60 | </div> |
| 61 | |
| 62 | <!-- *********************************************************************** --> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 63 | <div class="doc_section"><a name="idea">User-defined Operators: the Idea</a></div> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 64 | <!-- *********************************************************************** --> |
| 65 | |
| 66 | <div class="doc_text"> |
| 67 | |
| 68 | <p> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 69 | The "operator overloading" that we will add to Kaleidoscope is more general than |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 70 | languages like C++. In C++, you are only allowed to redefine existing |
| 71 | operators: you can't programatically change the grammar, introduce new |
| 72 | operators, change precedence levels, etc. In this chapter, we will add this |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 73 | capability to Kaleidoscope, which will let the user round out the set of |
| 74 | operators that are supported.</p> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 75 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 76 | <p>The point of going into user-defined operators in a tutorial like this is to |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 77 | show the power and flexibility of using a hand-written parser. Thus far, the parser |
| 78 | we have been implementing uses recursive descent for most parts of the grammar and |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 79 | operator precedence parsing for the expressions. See <a |
| 80 | href="LangImpl2.html">Chapter 2</a> for details. Without using operator |
| 81 | precedence parsing, it would be very difficult to allow the programmer to |
| 82 | introduce new operators into the grammar: the grammar is dynamically extensible |
| 83 | as the JIT runs.</p> |
| 84 | |
| 85 | <p>The two specific features we'll add are programmable unary operators (right |
| 86 | now, Kaleidoscope has no unary operators at all) as well as binary operators. |
| 87 | An example of this is:</p> |
| 88 | |
| 89 | <div class="doc_code"> |
| 90 | <pre> |
| 91 | # Logical unary not. |
| 92 | def unary!(v) |
| 93 | if v then |
| 94 | 0 |
| 95 | else |
| 96 | 1; |
| 97 | |
| 98 | # Define > with the same precedence as <. |
| 99 | def binary> 10 (LHS RHS) |
Chris Lattner | 61ad449 | 2007-11-23 22:19:33 +0000 | [diff] [blame] | 100 | RHS < LHS; |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 101 | |
| 102 | # Binary "logical or", (note that it does not "short circuit") |
| 103 | def binary| 5 (LHS RHS) |
| 104 | if LHS then |
| 105 | 1 |
| 106 | else if RHS then |
| 107 | 1 |
| 108 | else |
| 109 | 0; |
| 110 | |
| 111 | # Define = with slightly lower precedence than relationals. |
| 112 | def binary= 9 (LHS RHS) |
| 113 | !(LHS < RHS | LHS > RHS); |
| 114 | </pre> |
| 115 | </div> |
| 116 | |
| 117 | <p>Many languages aspire to being able to implement their standard runtime |
| 118 | library in the language itself. In Kaleidoscope, we can implement significant |
| 119 | parts of the language in the library!</p> |
| 120 | |
| 121 | <p>We will break down implementation of these features into two parts: |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 122 | implementing support for user-defined binary operators and adding unary |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 123 | operators.</p> |
| 124 | |
| 125 | </div> |
| 126 | |
| 127 | <!-- *********************************************************************** --> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 128 | <div class="doc_section"><a name="binary">User-defined Binary Operators</a></div> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 129 | <!-- *********************************************************************** --> |
| 130 | |
| 131 | <div class="doc_text"> |
| 132 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 133 | <p>Adding support for user-defined binary operators is pretty simple with our |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 134 | current framework. We'll first add support for the unary/binary keywords:</p> |
| 135 | |
| 136 | <div class="doc_code"> |
| 137 | <pre> |
| 138 | enum Token { |
| 139 | ... |
| 140 | <b>// operators |
| 141 | tok_binary = -11, tok_unary = -12</b> |
| 142 | }; |
| 143 | ... |
| 144 | static int gettok() { |
| 145 | ... |
| 146 | if (IdentifierStr == "for") return tok_for; |
| 147 | if (IdentifierStr == "in") return tok_in; |
| 148 | <b>if (IdentifierStr == "binary") return tok_binary; |
| 149 | if (IdentifierStr == "unary") return tok_unary;</b> |
| 150 | return tok_identifier; |
| 151 | </pre> |
| 152 | </div> |
| 153 | |
| 154 | <p>This just adds lexer support for the unary and binary keywords, like we |
| 155 | did in <a href="LangImpl5.html#iflexer">previous chapters</a>. One nice thing |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 156 | about our current AST, is that we represent binary operators with full generalisation |
| 157 | by using their ASCII code as the opcode. For our extended operators, we'll use this |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 158 | same representation, so we don't need any new AST or parser support.</p> |
| 159 | |
| 160 | <p>On the other hand, we have to be able to represent the definitions of these |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 161 | new operators, in the "def binary| 5" part of the function definition. In our |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 162 | grammar so far, the "name" for the function definition is parsed as the |
| 163 | "prototype" production and into the <tt>PrototypeAST</tt> AST node. To |
| 164 | represent our new user-defined operators as prototypes, we have to extend |
| 165 | the <tt>PrototypeAST</tt> AST node like this:</p> |
| 166 | |
| 167 | <div class="doc_code"> |
| 168 | <pre> |
| 169 | /// PrototypeAST - This class represents the "prototype" for a function, |
| 170 | /// which captures its argument names as well as if it is an operator. |
| 171 | class PrototypeAST { |
| 172 | std::string Name; |
| 173 | std::vector<std::string> Args; |
| 174 | <b>bool isOperator; |
| 175 | unsigned Precedence; // Precedence if a binary op.</b> |
| 176 | public: |
| 177 | PrototypeAST(const std::string &name, const std::vector<std::string> &args, |
| 178 | <b>bool isoperator = false, unsigned prec = 0</b>) |
| 179 | : Name(name), Args(args), <b>isOperator(isoperator), Precedence(prec)</b> {} |
| 180 | |
| 181 | <b>bool isUnaryOp() const { return isOperator && Args.size() == 1; } |
| 182 | bool isBinaryOp() const { return isOperator && Args.size() == 2; } |
| 183 | |
| 184 | char getOperatorName() const { |
| 185 | assert(isUnaryOp() || isBinaryOp()); |
| 186 | return Name[Name.size()-1]; |
| 187 | } |
| 188 | |
| 189 | unsigned getBinaryPrecedence() const { return Precedence; }</b> |
| 190 | |
| 191 | Function *Codegen(); |
| 192 | }; |
| 193 | </pre> |
| 194 | </div> |
| 195 | |
| 196 | <p>Basically, in addition to knowing a name for the prototype, we now keep track |
| 197 | of whether it was an operator, and if it was, what precedence level the operator |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 198 | is at. The precedence is only used for binary operators (as you'll see below, |
| 199 | it just doesn't apply for unary operators). Now that we have a way to represent |
| 200 | the prototype for a user-defined operator, we need to parse it:</p> |
| 201 | |
| 202 | <div class="doc_code"> |
| 203 | <pre> |
| 204 | /// prototype |
| 205 | /// ::= id '(' id* ')' |
| 206 | <b>/// ::= binary LETTER number? (id, id)</b> |
| 207 | static PrototypeAST *ParsePrototype() { |
| 208 | std::string FnName; |
| 209 | |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 210 | <b>unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 211 | unsigned BinaryPrecedence = 30;</b> |
| 212 | |
| 213 | switch (CurTok) { |
| 214 | default: |
| 215 | return ErrorP("Expected function name in prototype"); |
| 216 | case tok_identifier: |
| 217 | FnName = IdentifierStr; |
| 218 | Kind = 0; |
| 219 | getNextToken(); |
| 220 | break; |
| 221 | <b>case tok_binary: |
| 222 | getNextToken(); |
| 223 | if (!isascii(CurTok)) |
| 224 | return ErrorP("Expected binary operator"); |
| 225 | FnName = "binary"; |
| 226 | FnName += (char)CurTok; |
| 227 | Kind = 2; |
| 228 | getNextToken(); |
| 229 | |
| 230 | // Read the precedence if present. |
| 231 | if (CurTok == tok_number) { |
| 232 | if (NumVal < 1 || NumVal > 100) |
| 233 | return ErrorP("Invalid precedecnce: must be 1..100"); |
| 234 | BinaryPrecedence = (unsigned)NumVal; |
| 235 | getNextToken(); |
| 236 | } |
| 237 | break;</b> |
| 238 | } |
| 239 | |
| 240 | if (CurTok != '(') |
| 241 | return ErrorP("Expected '(' in prototype"); |
| 242 | |
| 243 | std::vector<std::string> ArgNames; |
| 244 | while (getNextToken() == tok_identifier) |
| 245 | ArgNames.push_back(IdentifierStr); |
| 246 | if (CurTok != ')') |
| 247 | return ErrorP("Expected ')' in prototype"); |
| 248 | |
| 249 | // success. |
| 250 | getNextToken(); // eat ')'. |
| 251 | |
| 252 | <b>// Verify right number of names for operator. |
| 253 | if (Kind && ArgNames.size() != Kind) |
| 254 | return ErrorP("Invalid number of operands for operator"); |
| 255 | |
| 256 | return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence);</b> |
| 257 | } |
| 258 | </pre> |
| 259 | </div> |
| 260 | |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 261 | <p>This is all fairly straightforward parsing code, and we have already seen |
| 262 | a lot of similar code in the past. One interesting part about the code above is |
| 263 | the couple lines that set up <tt>FnName</tt> for binary operators. This builds names |
| 264 | like "binary@" for a newly defined "@" operator. This then takes advantage of the |
| 265 | fact that symbol names in the LLVM symbol table are allowed to have any character in |
| 266 | them, including embedded nul characters.</p> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 267 | |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 268 | <p>The next interesting thing to add, is codegen support for these binary operators. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 269 | Given our current structure, this is a simple addition of a default case for our |
| 270 | existing binary operator node:</p> |
| 271 | |
| 272 | <div class="doc_code"> |
| 273 | <pre> |
| 274 | Value *BinaryExprAST::Codegen() { |
| 275 | Value *L = LHS->Codegen(); |
| 276 | Value *R = RHS->Codegen(); |
| 277 | if (L == 0 || R == 0) return 0; |
| 278 | |
| 279 | switch (Op) { |
Eric Christopher | 2214b81 | 2010-06-14 06:09:39 +0000 | [diff] [blame] | 280 | case '+': return Builder.CreateFAdd(L, R, "addtmp"); |
| 281 | case '-': return Builder.CreateFSub(L, R, "subtmp"); |
| 282 | case '*': return Builder.CreateFMul(L, R, "multmp"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 283 | case '<': |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 284 | L = Builder.CreateFCmpULT(L, R, "cmptmp"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 285 | // Convert bool 0/1 to double 0.0 or 1.0 |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 286 | return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), |
| 287 | "booltmp"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 288 | <b>default: break;</b> |
| 289 | } |
| 290 | |
| 291 | <b>// If it wasn't a builtin binary operator, it must be a user defined one. Emit |
| 292 | // a call to it. |
| 293 | Function *F = TheModule->getFunction(std::string("binary")+Op); |
| 294 | assert(F && "binary operator not found!"); |
| 295 | |
| 296 | Value *Ops[] = { L, R }; |
| 297 | return Builder.CreateCall(F, Ops, Ops+2, "binop");</b> |
| 298 | } |
| 299 | |
| 300 | </pre> |
| 301 | </div> |
| 302 | |
| 303 | <p>As you can see above, the new code is actually really simple. It just does |
| 304 | a lookup for the appropriate operator in the symbol table and generates a |
| 305 | function call to it. Since user-defined operators are just built as normal |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 306 | functions (because the "prototype" boils down to a function with the right |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 307 | name) everything falls into place.</p> |
| 308 | |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 309 | <p>The final piece of code we are missing, is a bit of top-level magic:</p> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 310 | |
| 311 | <div class="doc_code"> |
| 312 | <pre> |
| 313 | Function *FunctionAST::Codegen() { |
| 314 | NamedValues.clear(); |
| 315 | |
| 316 | Function *TheFunction = Proto->Codegen(); |
| 317 | if (TheFunction == 0) |
| 318 | return 0; |
| 319 | |
| 320 | <b>// If this is an operator, install it. |
| 321 | if (Proto->isBinaryOp()) |
| 322 | BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence();</b> |
| 323 | |
| 324 | // Create a new basic block to start insertion into. |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 325 | BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 326 | Builder.SetInsertPoint(BB); |
| 327 | |
| 328 | if (Value *RetVal = Body->Codegen()) { |
| 329 | ... |
| 330 | </pre> |
| 331 | </div> |
| 332 | |
| 333 | <p>Basically, before codegening a function, if it is a user-defined operator, we |
| 334 | register it in the precedence table. This allows the binary operator parsing |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 335 | logic we already have in place to handle it. Since we are working on a fully-general operator precedence parser, this is all we need to do to "extend the grammar".</p> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 336 | |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 337 | <p>Now we have useful user-defined binary operators. This builds a lot |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 338 | on the previous framework we built for other operators. Adding unary operators |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 339 | is a bit more challenging, because we don't have any framework for it yet - lets |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 340 | see what it takes.</p> |
| 341 | |
| 342 | </div> |
| 343 | |
| 344 | <!-- *********************************************************************** --> |
| 345 | <div class="doc_section"><a name="unary">User-defined Unary Operators</a></div> |
| 346 | <!-- *********************************************************************** --> |
| 347 | |
| 348 | <div class="doc_text"> |
| 349 | |
| 350 | <p>Since we don't currently support unary operators in the Kaleidoscope |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 351 | language, we'll need to add everything to support them. Above, we added simple |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 352 | support for the 'unary' keyword to the lexer. In addition to that, we need an |
| 353 | AST node:</p> |
| 354 | |
| 355 | <div class="doc_code"> |
| 356 | <pre> |
| 357 | /// UnaryExprAST - Expression class for a unary operator. |
| 358 | class UnaryExprAST : public ExprAST { |
| 359 | char Opcode; |
| 360 | ExprAST *Operand; |
| 361 | public: |
| 362 | UnaryExprAST(char opcode, ExprAST *operand) |
| 363 | : Opcode(opcode), Operand(operand) {} |
| 364 | virtual Value *Codegen(); |
| 365 | }; |
| 366 | </pre> |
| 367 | </div> |
| 368 | |
| 369 | <p>This AST node is very simple and obvious by now. It directly mirrors the |
| 370 | binary operator AST node, except that it only has one child. With this, we |
| 371 | need to add the parsing logic. Parsing a unary operator is pretty simple: we'll |
| 372 | add a new function to do it:</p> |
| 373 | |
| 374 | <div class="doc_code"> |
| 375 | <pre> |
| 376 | /// unary |
| 377 | /// ::= primary |
| 378 | /// ::= '!' unary |
| 379 | static ExprAST *ParseUnary() { |
| 380 | // If the current token is not an operator, it must be a primary expr. |
| 381 | if (!isascii(CurTok) || CurTok == '(' || CurTok == ',') |
| 382 | return ParsePrimary(); |
| 383 | |
| 384 | // If this is a unary operator, read it. |
| 385 | int Opc = CurTok; |
| 386 | getNextToken(); |
| 387 | if (ExprAST *Operand = ParseUnary()) |
| 388 | return new UnaryExprAST(Opc, Operand); |
| 389 | return 0; |
| 390 | } |
| 391 | </pre> |
| 392 | </div> |
| 393 | |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 394 | <p>The grammar we add is pretty straightforward here. If we see a unary |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 395 | operator when parsing a primary operator, we eat the operator as a prefix and |
| 396 | parse the remaining piece as another unary operator. This allows us to handle |
| 397 | multiple unary operators (e.g. "!!x"). Note that unary operators can't have |
| 398 | ambiguous parses like binary operators can, so there is no need for precedence |
| 399 | information.</p> |
| 400 | |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 401 | <p>The problem with this function, is that we need to call ParseUnary from somewhere. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 402 | To do this, we change previous callers of ParsePrimary to call ParseUnary |
| 403 | instead:</p> |
| 404 | |
| 405 | <div class="doc_code"> |
| 406 | <pre> |
| 407 | /// binoprhs |
| 408 | /// ::= ('+' unary)* |
| 409 | static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { |
| 410 | ... |
| 411 | <b>// Parse the unary expression after the binary operator. |
| 412 | ExprAST *RHS = ParseUnary(); |
| 413 | if (!RHS) return 0;</b> |
| 414 | ... |
| 415 | } |
| 416 | /// expression |
| 417 | /// ::= unary binoprhs |
| 418 | /// |
| 419 | static ExprAST *ParseExpression() { |
| 420 | <b>ExprAST *LHS = ParseUnary();</b> |
| 421 | if (!LHS) return 0; |
| 422 | |
| 423 | return ParseBinOpRHS(0, LHS); |
| 424 | } |
| 425 | </pre> |
| 426 | </div> |
| 427 | |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 428 | <p>With these two simple changes, we are now able to parse unary operators and build the |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 429 | AST for them. Next up, we need to add parser support for prototypes, to parse |
| 430 | the unary operator prototype. We extend the binary operator code above |
| 431 | with:</p> |
| 432 | |
| 433 | <div class="doc_code"> |
| 434 | <pre> |
| 435 | /// prototype |
| 436 | /// ::= id '(' id* ')' |
| 437 | /// ::= binary LETTER number? (id, id) |
| 438 | <b>/// ::= unary LETTER (id)</b> |
| 439 | static PrototypeAST *ParsePrototype() { |
| 440 | std::string FnName; |
| 441 | |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 442 | unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 443 | unsigned BinaryPrecedence = 30; |
| 444 | |
| 445 | switch (CurTok) { |
| 446 | default: |
| 447 | return ErrorP("Expected function name in prototype"); |
| 448 | case tok_identifier: |
| 449 | FnName = IdentifierStr; |
| 450 | Kind = 0; |
| 451 | getNextToken(); |
| 452 | break; |
| 453 | <b>case tok_unary: |
| 454 | getNextToken(); |
| 455 | if (!isascii(CurTok)) |
| 456 | return ErrorP("Expected unary operator"); |
| 457 | FnName = "unary"; |
| 458 | FnName += (char)CurTok; |
| 459 | Kind = 1; |
| 460 | getNextToken(); |
| 461 | break;</b> |
| 462 | case tok_binary: |
| 463 | ... |
| 464 | </pre> |
| 465 | </div> |
| 466 | |
| 467 | <p>As with binary operators, we name unary operators with a name that includes |
| 468 | the operator character. This assists us at code generation time. Speaking of, |
| 469 | the final piece we need to add is codegen support for unary operators. It looks |
| 470 | like this:</p> |
| 471 | |
| 472 | <div class="doc_code"> |
| 473 | <pre> |
| 474 | Value *UnaryExprAST::Codegen() { |
| 475 | Value *OperandV = Operand->Codegen(); |
| 476 | if (OperandV == 0) return 0; |
| 477 | |
| 478 | Function *F = TheModule->getFunction(std::string("unary")+Opcode); |
| 479 | if (F == 0) |
| 480 | return ErrorV("Unknown unary operator"); |
| 481 | |
| 482 | return Builder.CreateCall(F, OperandV, "unop"); |
| 483 | } |
| 484 | </pre> |
| 485 | </div> |
| 486 | |
| 487 | <p>This code is similar to, but simpler than, the code for binary operators. It |
| 488 | is simpler primarily because it doesn't need to handle any predefined operators. |
| 489 | </p> |
| 490 | |
| 491 | </div> |
| 492 | |
| 493 | <!-- *********************************************************************** --> |
| 494 | <div class="doc_section"><a name="example">Kicking the Tires</a></div> |
| 495 | <!-- *********************************************************************** --> |
| 496 | |
| 497 | <div class="doc_text"> |
| 498 | |
| 499 | <p>It is somewhat hard to believe, but with a few simple extensions we've |
Chris Lattner | b5d81b3 | 2007-11-02 05:54:25 +0000 | [diff] [blame] | 500 | covered in the last chapters, we have grown a real-ish language. With this, we |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 501 | can do a lot of interesting things, including I/O, math, and a bunch of other |
| 502 | things. For example, we can now add a nice sequencing operator (printd is |
| 503 | defined to print out the specified value and a newline):</p> |
| 504 | |
| 505 | <div class="doc_code"> |
| 506 | <pre> |
| 507 | ready> <b>extern printd(x);</b> |
| 508 | Read extern: declare double @printd(double) |
| 509 | ready> <b>def binary : 1 (x y) 0; # Low-precedence operator that ignores operands.</b> |
| 510 | .. |
| 511 | ready> <b>printd(123) : printd(456) : printd(789);</b> |
| 512 | 123.000000 |
| 513 | 456.000000 |
| 514 | 789.000000 |
| 515 | Evaluated to 0.000000 |
| 516 | </pre> |
| 517 | </div> |
| 518 | |
Chris Lattner | b5d81b3 | 2007-11-02 05:54:25 +0000 | [diff] [blame] | 519 | <p>We can also define a bunch of other "primitive" operations, such as:</p> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 520 | |
| 521 | <div class="doc_code"> |
| 522 | <pre> |
| 523 | # Logical unary not. |
| 524 | def unary!(v) |
| 525 | if v then |
| 526 | 0 |
| 527 | else |
| 528 | 1; |
| 529 | |
| 530 | # Unary negate. |
| 531 | def unary-(v) |
| 532 | 0-v; |
| 533 | |
Chris Lattner | 6808cdc | 2010-06-21 20:31:30 +0000 | [diff] [blame] | 534 | # Define > with the same precedence as <. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 535 | def binary> 10 (LHS RHS) |
Chris Lattner | 61ad449 | 2007-11-23 22:19:33 +0000 | [diff] [blame] | 536 | RHS < LHS; |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 537 | |
| 538 | # Binary logical or, which does not short circuit. |
| 539 | def binary| 5 (LHS RHS) |
| 540 | if LHS then |
| 541 | 1 |
| 542 | else if RHS then |
| 543 | 1 |
| 544 | else |
| 545 | 0; |
| 546 | |
| 547 | # Binary logical and, which does not short circuit. |
| 548 | def binary& 6 (LHS RHS) |
| 549 | if !LHS then |
| 550 | 0 |
| 551 | else |
| 552 | !!RHS; |
| 553 | |
| 554 | # Define = with slightly lower precedence than relationals. |
| 555 | def binary = 9 (LHS RHS) |
| 556 | !(LHS < RHS | LHS > RHS); |
| 557 | |
| 558 | </pre> |
| 559 | </div> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 560 | |
| 561 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 562 | <p>Given the previous if/then/else support, we can also define interesting |
| 563 | functions for I/O. For example, the following prints out a character whose |
| 564 | "density" reflects the value passed in: the lower the value, the denser the |
| 565 | character:</p> |
| 566 | |
| 567 | <div class="doc_code"> |
| 568 | <pre> |
| 569 | ready> |
| 570 | <b> |
| 571 | extern putchard(char) |
| 572 | def printdensity(d) |
| 573 | if d > 8 then |
| 574 | putchard(32) # ' ' |
| 575 | else if d > 4 then |
| 576 | putchard(46) # '.' |
| 577 | else if d > 2 then |
| 578 | putchard(43) # '+' |
| 579 | else |
| 580 | putchard(42); # '*'</b> |
| 581 | ... |
| 582 | ready> <b>printdensity(1): printdensity(2): printdensity(3) : |
| 583 | printdensity(4): printdensity(5): printdensity(9): putchard(10);</b> |
| 584 | *++.. |
| 585 | Evaluated to 0.000000 |
| 586 | </pre> |
| 587 | </div> |
| 588 | |
| 589 | <p>Based on these simple primitive operations, we can start to define more |
| 590 | interesting things. For example, here's a little function that solves for the |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 591 | number of iterations it takes a function in the complex plane to |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 592 | converge:</p> |
| 593 | |
| 594 | <div class="doc_code"> |
| 595 | <pre> |
| 596 | # determine whether the specific location diverges. |
| 597 | # Solve for z = z^2 + c in the complex plane. |
| 598 | def mandleconverger(real imag iters creal cimag) |
| 599 | if iters > 255 | (real*real + imag*imag > 4) then |
| 600 | iters |
| 601 | else |
| 602 | mandleconverger(real*real - imag*imag + creal, |
| 603 | 2*real*imag + cimag, |
| 604 | iters+1, creal, cimag); |
| 605 | |
| 606 | # return the number of iterations required for the iteration to escape |
| 607 | def mandleconverge(real imag) |
| 608 | mandleconverger(real, imag, 0, real, imag); |
| 609 | </pre> |
| 610 | </div> |
| 611 | |
Chris Lattner | b5d81b3 | 2007-11-02 05:54:25 +0000 | [diff] [blame] | 612 | <p>This "z = z<sup>2</sup> + c" function is a beautiful little creature that is the basis |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 613 | for computation of the <a |
| 614 | href="http://en.wikipedia.org/wiki/Mandelbrot_set">Mandelbrot Set</a>. Our |
| 615 | <tt>mandelconverge</tt> function returns the number of iterations that it takes |
| 616 | for a complex orbit to escape, saturating to 255. This is not a very useful |
| 617 | function by itself, but if you plot its value over a two-dimensional plane, |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 618 | you can see the Mandelbrot set. Given that we are limited to using putchard |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 619 | here, our amazing graphical output is limited, but we can whip together |
| 620 | something using the density plotter above:</p> |
| 621 | |
| 622 | <div class="doc_code"> |
| 623 | <pre> |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 624 | # compute and plot the mandlebrot set with the specified 2 dimensional range |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 625 | # info. |
| 626 | def mandelhelp(xmin xmax xstep ymin ymax ystep) |
| 627 | for y = ymin, y < ymax, ystep in ( |
| 628 | (for x = xmin, x < xmax, xstep in |
| 629 | printdensity(mandleconverge(x,y))) |
| 630 | : putchard(10) |
| 631 | ) |
| 632 | |
| 633 | # mandel - This is a convenient helper function for ploting the mandelbrot set |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 634 | # from the specified position with the specified Magnification. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 635 | def mandel(realstart imagstart realmag imagmag) |
| 636 | mandelhelp(realstart, realstart+realmag*78, realmag, |
| 637 | imagstart, imagstart+imagmag*40, imagmag); |
| 638 | </pre> |
| 639 | </div> |
| 640 | |
| 641 | <p>Given this, we can try plotting out the mandlebrot set! Lets try it out:</p> |
| 642 | |
| 643 | <div class="doc_code"> |
| 644 | <pre> |
| 645 | ready> <b>mandel(-2.3, -1.3, 0.05, 0.07);</b> |
| 646 | *******************************+++++++++++************************************* |
| 647 | *************************+++++++++++++++++++++++******************************* |
| 648 | **********************+++++++++++++++++++++++++++++**************************** |
| 649 | *******************+++++++++++++++++++++.. ...++++++++************************* |
| 650 | *****************++++++++++++++++++++++.... ...+++++++++*********************** |
| 651 | ***************+++++++++++++++++++++++..... ...+++++++++********************* |
| 652 | **************+++++++++++++++++++++++.... ....+++++++++******************** |
| 653 | *************++++++++++++++++++++++...... .....++++++++******************* |
| 654 | ************+++++++++++++++++++++....... .......+++++++****************** |
| 655 | ***********+++++++++++++++++++.... ... .+++++++***************** |
| 656 | **********+++++++++++++++++....... .+++++++**************** |
| 657 | *********++++++++++++++........... ...+++++++*************** |
| 658 | ********++++++++++++............ ...++++++++************** |
| 659 | ********++++++++++... .......... .++++++++************** |
| 660 | *******+++++++++..... .+++++++++************* |
| 661 | *******++++++++...... ..+++++++++************* |
| 662 | *******++++++....... ..+++++++++************* |
| 663 | *******+++++...... ..+++++++++************* |
| 664 | *******.... .... ...+++++++++************* |
| 665 | *******.... . ...+++++++++************* |
| 666 | *******+++++...... ...+++++++++************* |
| 667 | *******++++++....... ..+++++++++************* |
| 668 | *******++++++++...... .+++++++++************* |
| 669 | *******+++++++++..... ..+++++++++************* |
| 670 | ********++++++++++... .......... .++++++++************** |
| 671 | ********++++++++++++............ ...++++++++************** |
| 672 | *********++++++++++++++.......... ...+++++++*************** |
| 673 | **********++++++++++++++++........ .+++++++**************** |
| 674 | **********++++++++++++++++++++.... ... ..+++++++**************** |
| 675 | ***********++++++++++++++++++++++....... .......++++++++***************** |
| 676 | ************+++++++++++++++++++++++...... ......++++++++****************** |
| 677 | **************+++++++++++++++++++++++.... ....++++++++******************** |
| 678 | ***************+++++++++++++++++++++++..... ...+++++++++********************* |
| 679 | *****************++++++++++++++++++++++.... ...++++++++*********************** |
| 680 | *******************+++++++++++++++++++++......++++++++************************* |
| 681 | *********************++++++++++++++++++++++.++++++++*************************** |
| 682 | *************************+++++++++++++++++++++++******************************* |
| 683 | ******************************+++++++++++++************************************ |
| 684 | ******************************************************************************* |
| 685 | ******************************************************************************* |
| 686 | ******************************************************************************* |
| 687 | Evaluated to 0.000000 |
| 688 | ready> <b>mandel(-2, -1, 0.02, 0.04);</b> |
| 689 | **************************+++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| 690 | ***********************++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| 691 | *********************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++. |
| 692 | *******************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++... |
| 693 | *****************+++++++++++++++++++++++++++++++++++++++++++++++++++++++++..... |
| 694 | ***************++++++++++++++++++++++++++++++++++++++++++++++++++++++++........ |
| 695 | **************++++++++++++++++++++++++++++++++++++++++++++++++++++++........... |
| 696 | ************+++++++++++++++++++++++++++++++++++++++++++++++++++++.............. |
| 697 | ***********++++++++++++++++++++++++++++++++++++++++++++++++++........ . |
| 698 | **********++++++++++++++++++++++++++++++++++++++++++++++............. |
| 699 | ********+++++++++++++++++++++++++++++++++++++++++++.................. |
| 700 | *******+++++++++++++++++++++++++++++++++++++++....................... |
| 701 | ******+++++++++++++++++++++++++++++++++++........................... |
| 702 | *****++++++++++++++++++++++++++++++++............................ |
| 703 | *****++++++++++++++++++++++++++++............................... |
| 704 | ****++++++++++++++++++++++++++...... ......................... |
| 705 | ***++++++++++++++++++++++++......... ...... ........... |
| 706 | ***++++++++++++++++++++++............ |
| 707 | **+++++++++++++++++++++.............. |
| 708 | **+++++++++++++++++++................ |
| 709 | *++++++++++++++++++................. |
| 710 | *++++++++++++++++............ ... |
| 711 | *++++++++++++++.............. |
| 712 | *+++....++++................ |
| 713 | *.......... ........... |
| 714 | * |
| 715 | *.......... ........... |
| 716 | *+++....++++................ |
| 717 | *++++++++++++++.............. |
| 718 | *++++++++++++++++............ ... |
| 719 | *++++++++++++++++++................. |
| 720 | **+++++++++++++++++++................ |
| 721 | **+++++++++++++++++++++.............. |
| 722 | ***++++++++++++++++++++++............ |
| 723 | ***++++++++++++++++++++++++......... ...... ........... |
| 724 | ****++++++++++++++++++++++++++...... ......................... |
| 725 | *****++++++++++++++++++++++++++++............................... |
| 726 | *****++++++++++++++++++++++++++++++++............................ |
| 727 | ******+++++++++++++++++++++++++++++++++++........................... |
| 728 | *******+++++++++++++++++++++++++++++++++++++++....................... |
| 729 | ********+++++++++++++++++++++++++++++++++++++++++++.................. |
| 730 | Evaluated to 0.000000 |
| 731 | ready> <b>mandel(-0.9, -1.4, 0.02, 0.03);</b> |
| 732 | ******************************************************************************* |
| 733 | ******************************************************************************* |
| 734 | ******************************************************************************* |
| 735 | **********+++++++++++++++++++++************************************************ |
| 736 | *+++++++++++++++++++++++++++++++++++++++*************************************** |
| 737 | +++++++++++++++++++++++++++++++++++++++++++++********************************** |
| 738 | ++++++++++++++++++++++++++++++++++++++++++++++++++***************************** |
| 739 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++************************* |
| 740 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++********************** |
| 741 | +++++++++++++++++++++++++++++++++.........++++++++++++++++++******************* |
| 742 | +++++++++++++++++++++++++++++++.... ......+++++++++++++++++++**************** |
| 743 | +++++++++++++++++++++++++++++....... ........+++++++++++++++++++************** |
| 744 | ++++++++++++++++++++++++++++........ ........++++++++++++++++++++************ |
| 745 | +++++++++++++++++++++++++++......... .. ...+++++++++++++++++++++********** |
| 746 | ++++++++++++++++++++++++++........... ....++++++++++++++++++++++******** |
| 747 | ++++++++++++++++++++++++............. .......++++++++++++++++++++++****** |
| 748 | +++++++++++++++++++++++............. ........+++++++++++++++++++++++**** |
| 749 | ++++++++++++++++++++++........... ..........++++++++++++++++++++++*** |
| 750 | ++++++++++++++++++++........... .........++++++++++++++++++++++* |
| 751 | ++++++++++++++++++............ ...........++++++++++++++++++++ |
| 752 | ++++++++++++++++............... .............++++++++++++++++++ |
| 753 | ++++++++++++++................. ...............++++++++++++++++ |
| 754 | ++++++++++++.................. .................++++++++++++++ |
| 755 | +++++++++.................. .................+++++++++++++ |
| 756 | ++++++........ . ......... ..++++++++++++ |
| 757 | ++............ ...... ....++++++++++ |
| 758 | .............. ...++++++++++ |
| 759 | .............. ....+++++++++ |
| 760 | .............. .....++++++++ |
| 761 | ............. ......++++++++ |
| 762 | ........... .......++++++++ |
| 763 | ......... ........+++++++ |
| 764 | ......... ........+++++++ |
| 765 | ......... ....+++++++ |
| 766 | ........ ...+++++++ |
| 767 | ....... ...+++++++ |
| 768 | ....+++++++ |
| 769 | .....+++++++ |
| 770 | ....+++++++ |
| 771 | ....+++++++ |
| 772 | ....+++++++ |
| 773 | Evaluated to 0.000000 |
| 774 | ready> <b>^D</b> |
| 775 | </pre> |
| 776 | </div> |
| 777 | |
| 778 | <p>At this point, you may be starting to realize that Kaleidoscope is a real |
| 779 | and powerful language. It may not be self-similar :), but it can be used to |
| 780 | plot things that are!</p> |
| 781 | |
| 782 | <p>With this, we conclude the "adding user-defined operators" chapter of the |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 783 | tutorial. We have successfully augmented our language, adding the ability to extend the |
| 784 | language in the library, and we have shown how this can be used to build a simple but |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 785 | interesting end-user application in Kaleidoscope. At this point, Kaleidoscope |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 786 | can build a variety of applications that are functional and can call functions |
Chris Lattner | b5d81b3 | 2007-11-02 05:54:25 +0000 | [diff] [blame] | 787 | with side-effects, but it can't actually define and mutate a variable itself. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 788 | </p> |
| 789 | |
Chris Lattner | 3616a8a | 2007-11-07 06:06:38 +0000 | [diff] [blame] | 790 | <p>Strikingly, variable mutation is an important feature of some |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 791 | languages, and it is not at all obvious how to <a href="LangImpl7.html">add |
| 792 | support for mutable variables</a> without having to add an "SSA construction" |
| 793 | phase to your front-end. In the next chapter, we will describe how you can |
Chris Lattner | b7e6b1a | 2007-11-15 04:51:31 +0000 | [diff] [blame] | 794 | add variable mutation without building SSA in your front-end.</p> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 795 | |
| 796 | </div> |
| 797 | |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 798 | <!-- *********************************************************************** --> |
| 799 | <div class="doc_section"><a name="code">Full Code Listing</a></div> |
| 800 | <!-- *********************************************************************** --> |
| 801 | |
| 802 | <div class="doc_text"> |
| 803 | |
| 804 | <p> |
| 805 | Here is the complete code listing for our running example, enhanced with the |
| 806 | if/then/else and for expressions.. To build this example, use: |
| 807 | </p> |
| 808 | |
| 809 | <div class="doc_code"> |
| 810 | <pre> |
| 811 | # Compile |
| 812 | g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy |
| 813 | # Run |
| 814 | ./toy |
| 815 | </pre> |
| 816 | </div> |
| 817 | |
| 818 | <p>Here is the code:</p> |
| 819 | |
| 820 | <div class="doc_code"> |
| 821 | <pre> |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 822 | #include "llvm/DerivedTypes.h" |
| 823 | #include "llvm/ExecutionEngine/ExecutionEngine.h" |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 824 | #include "llvm/ExecutionEngine/JIT.h" |
Owen Anderson | d1fbd14 | 2009-07-08 20:50:47 +0000 | [diff] [blame] | 825 | #include "llvm/LLVMContext.h" |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 826 | #include "llvm/Module.h" |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 827 | #include "llvm/PassManager.h" |
| 828 | #include "llvm/Analysis/Verifier.h" |
| 829 | #include "llvm/Target/TargetData.h" |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 830 | #include "llvm/Target/TargetSelect.h" |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 831 | #include "llvm/Transforms/Scalar.h" |
Duncan Sands | 89f6d88 | 2008-04-13 06:22:09 +0000 | [diff] [blame] | 832 | #include "llvm/Support/IRBuilder.h" |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 833 | #include <cstdio> |
| 834 | #include <string> |
| 835 | #include <map> |
| 836 | #include <vector> |
| 837 | using namespace llvm; |
| 838 | |
| 839 | //===----------------------------------------------------------------------===// |
| 840 | // Lexer |
| 841 | //===----------------------------------------------------------------------===// |
| 842 | |
| 843 | // The lexer returns tokens [0-255] if it is an unknown character, otherwise one |
| 844 | // of these for known things. |
| 845 | enum Token { |
| 846 | tok_eof = -1, |
| 847 | |
| 848 | // commands |
| 849 | tok_def = -2, tok_extern = -3, |
| 850 | |
| 851 | // primary |
| 852 | tok_identifier = -4, tok_number = -5, |
| 853 | |
| 854 | // control |
| 855 | tok_if = -6, tok_then = -7, tok_else = -8, |
| 856 | tok_for = -9, tok_in = -10, |
| 857 | |
| 858 | // operators |
| 859 | tok_binary = -11, tok_unary = -12 |
| 860 | }; |
| 861 | |
| 862 | static std::string IdentifierStr; // Filled in if tok_identifier |
| 863 | static double NumVal; // Filled in if tok_number |
| 864 | |
| 865 | /// gettok - Return the next token from standard input. |
| 866 | static int gettok() { |
| 867 | static int LastChar = ' '; |
| 868 | |
| 869 | // Skip any whitespace. |
| 870 | while (isspace(LastChar)) |
| 871 | LastChar = getchar(); |
| 872 | |
| 873 | if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* |
| 874 | IdentifierStr = LastChar; |
| 875 | while (isalnum((LastChar = getchar()))) |
| 876 | IdentifierStr += LastChar; |
| 877 | |
| 878 | if (IdentifierStr == "def") return tok_def; |
| 879 | if (IdentifierStr == "extern") return tok_extern; |
| 880 | if (IdentifierStr == "if") return tok_if; |
| 881 | if (IdentifierStr == "then") return tok_then; |
| 882 | if (IdentifierStr == "else") return tok_else; |
| 883 | if (IdentifierStr == "for") return tok_for; |
| 884 | if (IdentifierStr == "in") return tok_in; |
| 885 | if (IdentifierStr == "binary") return tok_binary; |
| 886 | if (IdentifierStr == "unary") return tok_unary; |
| 887 | return tok_identifier; |
| 888 | } |
| 889 | |
| 890 | if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ |
| 891 | std::string NumStr; |
| 892 | do { |
| 893 | NumStr += LastChar; |
| 894 | LastChar = getchar(); |
| 895 | } while (isdigit(LastChar) || LastChar == '.'); |
| 896 | |
| 897 | NumVal = strtod(NumStr.c_str(), 0); |
| 898 | return tok_number; |
| 899 | } |
| 900 | |
| 901 | if (LastChar == '#') { |
| 902 | // Comment until end of line. |
| 903 | do LastChar = getchar(); |
Chris Lattner | c80c23f | 2007-12-02 22:46:01 +0000 | [diff] [blame] | 904 | while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 905 | |
| 906 | if (LastChar != EOF) |
| 907 | return gettok(); |
| 908 | } |
| 909 | |
| 910 | // Check for end of file. Don't eat the EOF. |
| 911 | if (LastChar == EOF) |
| 912 | return tok_eof; |
| 913 | |
| 914 | // Otherwise, just return the character as its ascii value. |
| 915 | int ThisChar = LastChar; |
| 916 | LastChar = getchar(); |
| 917 | return ThisChar; |
| 918 | } |
| 919 | |
| 920 | //===----------------------------------------------------------------------===// |
| 921 | // Abstract Syntax Tree (aka Parse Tree) |
| 922 | //===----------------------------------------------------------------------===// |
| 923 | |
| 924 | /// ExprAST - Base class for all expression nodes. |
| 925 | class ExprAST { |
| 926 | public: |
| 927 | virtual ~ExprAST() {} |
| 928 | virtual Value *Codegen() = 0; |
| 929 | }; |
| 930 | |
| 931 | /// NumberExprAST - Expression class for numeric literals like "1.0". |
| 932 | class NumberExprAST : public ExprAST { |
| 933 | double Val; |
| 934 | public: |
| 935 | NumberExprAST(double val) : Val(val) {} |
| 936 | virtual Value *Codegen(); |
| 937 | }; |
| 938 | |
| 939 | /// VariableExprAST - Expression class for referencing a variable, like "a". |
| 940 | class VariableExprAST : public ExprAST { |
| 941 | std::string Name; |
| 942 | public: |
| 943 | VariableExprAST(const std::string &name) : Name(name) {} |
| 944 | virtual Value *Codegen(); |
| 945 | }; |
| 946 | |
| 947 | /// UnaryExprAST - Expression class for a unary operator. |
| 948 | class UnaryExprAST : public ExprAST { |
| 949 | char Opcode; |
| 950 | ExprAST *Operand; |
| 951 | public: |
| 952 | UnaryExprAST(char opcode, ExprAST *operand) |
| 953 | : Opcode(opcode), Operand(operand) {} |
| 954 | virtual Value *Codegen(); |
| 955 | }; |
| 956 | |
| 957 | /// BinaryExprAST - Expression class for a binary operator. |
| 958 | class BinaryExprAST : public ExprAST { |
| 959 | char Op; |
| 960 | ExprAST *LHS, *RHS; |
| 961 | public: |
| 962 | BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) |
| 963 | : Op(op), LHS(lhs), RHS(rhs) {} |
| 964 | virtual Value *Codegen(); |
| 965 | }; |
| 966 | |
| 967 | /// CallExprAST - Expression class for function calls. |
| 968 | class CallExprAST : public ExprAST { |
| 969 | std::string Callee; |
| 970 | std::vector<ExprAST*> Args; |
| 971 | public: |
| 972 | CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) |
| 973 | : Callee(callee), Args(args) {} |
| 974 | virtual Value *Codegen(); |
| 975 | }; |
| 976 | |
| 977 | /// IfExprAST - Expression class for if/then/else. |
| 978 | class IfExprAST : public ExprAST { |
| 979 | ExprAST *Cond, *Then, *Else; |
| 980 | public: |
| 981 | IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else) |
| 982 | : Cond(cond), Then(then), Else(_else) {} |
| 983 | virtual Value *Codegen(); |
| 984 | }; |
| 985 | |
| 986 | /// ForExprAST - Expression class for for/in. |
| 987 | class ForExprAST : public ExprAST { |
| 988 | std::string VarName; |
| 989 | ExprAST *Start, *End, *Step, *Body; |
| 990 | public: |
| 991 | ForExprAST(const std::string &varname, ExprAST *start, ExprAST *end, |
| 992 | ExprAST *step, ExprAST *body) |
| 993 | : VarName(varname), Start(start), End(end), Step(step), Body(body) {} |
| 994 | virtual Value *Codegen(); |
| 995 | }; |
| 996 | |
| 997 | /// PrototypeAST - This class represents the "prototype" for a function, |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 998 | /// which captures its name, and its argument names (thus implicitly the number |
| 999 | /// of arguments the function takes), as well as if it is an operator. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1000 | class PrototypeAST { |
| 1001 | std::string Name; |
| 1002 | std::vector<std::string> Args; |
| 1003 | bool isOperator; |
| 1004 | unsigned Precedence; // Precedence if a binary op. |
| 1005 | public: |
| 1006 | PrototypeAST(const std::string &name, const std::vector<std::string> &args, |
| 1007 | bool isoperator = false, unsigned prec = 0) |
| 1008 | : Name(name), Args(args), isOperator(isoperator), Precedence(prec) {} |
| 1009 | |
| 1010 | bool isUnaryOp() const { return isOperator && Args.size() == 1; } |
| 1011 | bool isBinaryOp() const { return isOperator && Args.size() == 2; } |
| 1012 | |
| 1013 | char getOperatorName() const { |
| 1014 | assert(isUnaryOp() || isBinaryOp()); |
| 1015 | return Name[Name.size()-1]; |
| 1016 | } |
| 1017 | |
| 1018 | unsigned getBinaryPrecedence() const { return Precedence; } |
| 1019 | |
| 1020 | Function *Codegen(); |
| 1021 | }; |
| 1022 | |
| 1023 | /// FunctionAST - This class represents a function definition itself. |
| 1024 | class FunctionAST { |
| 1025 | PrototypeAST *Proto; |
| 1026 | ExprAST *Body; |
| 1027 | public: |
| 1028 | FunctionAST(PrototypeAST *proto, ExprAST *body) |
| 1029 | : Proto(proto), Body(body) {} |
| 1030 | |
| 1031 | Function *Codegen(); |
| 1032 | }; |
| 1033 | |
| 1034 | //===----------------------------------------------------------------------===// |
| 1035 | // Parser |
| 1036 | //===----------------------------------------------------------------------===// |
| 1037 | |
| 1038 | /// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1039 | /// token the parser is looking at. getNextToken reads another token from the |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1040 | /// lexer and updates CurTok with its results. |
| 1041 | static int CurTok; |
| 1042 | static int getNextToken() { |
| 1043 | return CurTok = gettok(); |
| 1044 | } |
| 1045 | |
| 1046 | /// BinopPrecedence - This holds the precedence for each binary operator that is |
| 1047 | /// defined. |
| 1048 | static std::map<char, int> BinopPrecedence; |
| 1049 | |
| 1050 | /// GetTokPrecedence - Get the precedence of the pending binary operator token. |
| 1051 | static int GetTokPrecedence() { |
| 1052 | if (!isascii(CurTok)) |
| 1053 | return -1; |
| 1054 | |
| 1055 | // Make sure it's a declared binop. |
| 1056 | int TokPrec = BinopPrecedence[CurTok]; |
| 1057 | if (TokPrec <= 0) return -1; |
| 1058 | return TokPrec; |
| 1059 | } |
| 1060 | |
| 1061 | /// Error* - These are little helper functions for error handling. |
| 1062 | ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} |
| 1063 | PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } |
| 1064 | FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } |
| 1065 | |
| 1066 | static ExprAST *ParseExpression(); |
| 1067 | |
| 1068 | /// identifierexpr |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 1069 | /// ::= identifier |
| 1070 | /// ::= identifier '(' expression* ')' |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1071 | static ExprAST *ParseIdentifierExpr() { |
| 1072 | std::string IdName = IdentifierStr; |
| 1073 | |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 1074 | getNextToken(); // eat identifier. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1075 | |
| 1076 | if (CurTok != '(') // Simple variable ref. |
| 1077 | return new VariableExprAST(IdName); |
| 1078 | |
| 1079 | // Call. |
| 1080 | getNextToken(); // eat ( |
| 1081 | std::vector<ExprAST*> Args; |
| 1082 | if (CurTok != ')') { |
| 1083 | while (1) { |
| 1084 | ExprAST *Arg = ParseExpression(); |
| 1085 | if (!Arg) return 0; |
| 1086 | Args.push_back(Arg); |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1087 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1088 | if (CurTok == ')') break; |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1089 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1090 | if (CurTok != ',') |
Chris Lattner | 6c4be9c | 2008-04-14 16:44:41 +0000 | [diff] [blame] | 1091 | return Error("Expected ')' or ',' in argument list"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1092 | getNextToken(); |
| 1093 | } |
| 1094 | } |
| 1095 | |
| 1096 | // Eat the ')'. |
| 1097 | getNextToken(); |
| 1098 | |
| 1099 | return new CallExprAST(IdName, Args); |
| 1100 | } |
| 1101 | |
| 1102 | /// numberexpr ::= number |
| 1103 | static ExprAST *ParseNumberExpr() { |
| 1104 | ExprAST *Result = new NumberExprAST(NumVal); |
| 1105 | getNextToken(); // consume the number |
| 1106 | return Result; |
| 1107 | } |
| 1108 | |
| 1109 | /// parenexpr ::= '(' expression ')' |
| 1110 | static ExprAST *ParseParenExpr() { |
| 1111 | getNextToken(); // eat (. |
| 1112 | ExprAST *V = ParseExpression(); |
| 1113 | if (!V) return 0; |
| 1114 | |
| 1115 | if (CurTok != ')') |
| 1116 | return Error("expected ')'"); |
| 1117 | getNextToken(); // eat ). |
| 1118 | return V; |
| 1119 | } |
| 1120 | |
| 1121 | /// ifexpr ::= 'if' expression 'then' expression 'else' expression |
| 1122 | static ExprAST *ParseIfExpr() { |
| 1123 | getNextToken(); // eat the if. |
| 1124 | |
| 1125 | // condition. |
| 1126 | ExprAST *Cond = ParseExpression(); |
| 1127 | if (!Cond) return 0; |
| 1128 | |
| 1129 | if (CurTok != tok_then) |
| 1130 | return Error("expected then"); |
| 1131 | getNextToken(); // eat the then |
| 1132 | |
| 1133 | ExprAST *Then = ParseExpression(); |
| 1134 | if (Then == 0) return 0; |
| 1135 | |
| 1136 | if (CurTok != tok_else) |
| 1137 | return Error("expected else"); |
| 1138 | |
| 1139 | getNextToken(); |
| 1140 | |
| 1141 | ExprAST *Else = ParseExpression(); |
| 1142 | if (!Else) return 0; |
| 1143 | |
| 1144 | return new IfExprAST(Cond, Then, Else); |
| 1145 | } |
| 1146 | |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 1147 | /// forexpr ::= 'for' identifier '=' expr ',' expr (',' expr)? 'in' expression |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1148 | static ExprAST *ParseForExpr() { |
| 1149 | getNextToken(); // eat the for. |
| 1150 | |
| 1151 | if (CurTok != tok_identifier) |
| 1152 | return Error("expected identifier after for"); |
| 1153 | |
| 1154 | std::string IdName = IdentifierStr; |
Chris Lattner | 20a0c80 | 2007-11-05 17:54:34 +0000 | [diff] [blame] | 1155 | getNextToken(); // eat identifier. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1156 | |
| 1157 | if (CurTok != '=') |
| 1158 | return Error("expected '=' after for"); |
| 1159 | getNextToken(); // eat '='. |
| 1160 | |
| 1161 | |
| 1162 | ExprAST *Start = ParseExpression(); |
| 1163 | if (Start == 0) return 0; |
| 1164 | if (CurTok != ',') |
| 1165 | return Error("expected ',' after for start value"); |
| 1166 | getNextToken(); |
| 1167 | |
| 1168 | ExprAST *End = ParseExpression(); |
| 1169 | if (End == 0) return 0; |
| 1170 | |
| 1171 | // The step value is optional. |
| 1172 | ExprAST *Step = 0; |
| 1173 | if (CurTok == ',') { |
| 1174 | getNextToken(); |
| 1175 | Step = ParseExpression(); |
| 1176 | if (Step == 0) return 0; |
| 1177 | } |
| 1178 | |
| 1179 | if (CurTok != tok_in) |
| 1180 | return Error("expected 'in' after for"); |
| 1181 | getNextToken(); // eat 'in'. |
| 1182 | |
| 1183 | ExprAST *Body = ParseExpression(); |
| 1184 | if (Body == 0) return 0; |
| 1185 | |
| 1186 | return new ForExprAST(IdName, Start, End, Step, Body); |
| 1187 | } |
| 1188 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1189 | /// primary |
| 1190 | /// ::= identifierexpr |
| 1191 | /// ::= numberexpr |
| 1192 | /// ::= parenexpr |
| 1193 | /// ::= ifexpr |
| 1194 | /// ::= forexpr |
| 1195 | static ExprAST *ParsePrimary() { |
| 1196 | switch (CurTok) { |
| 1197 | default: return Error("unknown token when expecting an expression"); |
| 1198 | case tok_identifier: return ParseIdentifierExpr(); |
| 1199 | case tok_number: return ParseNumberExpr(); |
| 1200 | case '(': return ParseParenExpr(); |
| 1201 | case tok_if: return ParseIfExpr(); |
| 1202 | case tok_for: return ParseForExpr(); |
| 1203 | } |
| 1204 | } |
| 1205 | |
| 1206 | /// unary |
| 1207 | /// ::= primary |
| 1208 | /// ::= '!' unary |
| 1209 | static ExprAST *ParseUnary() { |
| 1210 | // If the current token is not an operator, it must be a primary expr. |
| 1211 | if (!isascii(CurTok) || CurTok == '(' || CurTok == ',') |
| 1212 | return ParsePrimary(); |
| 1213 | |
| 1214 | // If this is a unary operator, read it. |
| 1215 | int Opc = CurTok; |
| 1216 | getNextToken(); |
| 1217 | if (ExprAST *Operand = ParseUnary()) |
| 1218 | return new UnaryExprAST(Opc, Operand); |
| 1219 | return 0; |
| 1220 | } |
| 1221 | |
| 1222 | /// binoprhs |
| 1223 | /// ::= ('+' unary)* |
| 1224 | static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { |
| 1225 | // If this is a binop, find its precedence. |
| 1226 | while (1) { |
| 1227 | int TokPrec = GetTokPrecedence(); |
| 1228 | |
| 1229 | // If this is a binop that binds at least as tightly as the current binop, |
| 1230 | // consume it, otherwise we are done. |
| 1231 | if (TokPrec < ExprPrec) |
| 1232 | return LHS; |
| 1233 | |
| 1234 | // Okay, we know this is a binop. |
| 1235 | int BinOp = CurTok; |
| 1236 | getNextToken(); // eat binop |
| 1237 | |
| 1238 | // Parse the unary expression after the binary operator. |
| 1239 | ExprAST *RHS = ParseUnary(); |
| 1240 | if (!RHS) return 0; |
| 1241 | |
| 1242 | // If BinOp binds less tightly with RHS than the operator after RHS, let |
| 1243 | // the pending operator take RHS as its LHS. |
| 1244 | int NextPrec = GetTokPrecedence(); |
| 1245 | if (TokPrec < NextPrec) { |
| 1246 | RHS = ParseBinOpRHS(TokPrec+1, RHS); |
| 1247 | if (RHS == 0) return 0; |
| 1248 | } |
| 1249 | |
| 1250 | // Merge LHS/RHS. |
| 1251 | LHS = new BinaryExprAST(BinOp, LHS, RHS); |
| 1252 | } |
| 1253 | } |
| 1254 | |
| 1255 | /// expression |
| 1256 | /// ::= unary binoprhs |
| 1257 | /// |
| 1258 | static ExprAST *ParseExpression() { |
| 1259 | ExprAST *LHS = ParseUnary(); |
| 1260 | if (!LHS) return 0; |
| 1261 | |
| 1262 | return ParseBinOpRHS(0, LHS); |
| 1263 | } |
| 1264 | |
| 1265 | /// prototype |
| 1266 | /// ::= id '(' id* ')' |
| 1267 | /// ::= binary LETTER number? (id, id) |
| 1268 | /// ::= unary LETTER (id) |
| 1269 | static PrototypeAST *ParsePrototype() { |
| 1270 | std::string FnName; |
| 1271 | |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1272 | unsigned Kind = 0; // 0 = identifier, 1 = unary, 2 = binary. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1273 | unsigned BinaryPrecedence = 30; |
| 1274 | |
| 1275 | switch (CurTok) { |
| 1276 | default: |
| 1277 | return ErrorP("Expected function name in prototype"); |
| 1278 | case tok_identifier: |
| 1279 | FnName = IdentifierStr; |
| 1280 | Kind = 0; |
| 1281 | getNextToken(); |
| 1282 | break; |
| 1283 | case tok_unary: |
| 1284 | getNextToken(); |
| 1285 | if (!isascii(CurTok)) |
| 1286 | return ErrorP("Expected unary operator"); |
| 1287 | FnName = "unary"; |
| 1288 | FnName += (char)CurTok; |
| 1289 | Kind = 1; |
| 1290 | getNextToken(); |
| 1291 | break; |
| 1292 | case tok_binary: |
| 1293 | getNextToken(); |
| 1294 | if (!isascii(CurTok)) |
| 1295 | return ErrorP("Expected binary operator"); |
| 1296 | FnName = "binary"; |
| 1297 | FnName += (char)CurTok; |
| 1298 | Kind = 2; |
| 1299 | getNextToken(); |
| 1300 | |
| 1301 | // Read the precedence if present. |
| 1302 | if (CurTok == tok_number) { |
| 1303 | if (NumVal < 1 || NumVal > 100) |
| 1304 | return ErrorP("Invalid precedecnce: must be 1..100"); |
| 1305 | BinaryPrecedence = (unsigned)NumVal; |
| 1306 | getNextToken(); |
| 1307 | } |
| 1308 | break; |
| 1309 | } |
| 1310 | |
| 1311 | if (CurTok != '(') |
| 1312 | return ErrorP("Expected '(' in prototype"); |
| 1313 | |
| 1314 | std::vector<std::string> ArgNames; |
| 1315 | while (getNextToken() == tok_identifier) |
| 1316 | ArgNames.push_back(IdentifierStr); |
| 1317 | if (CurTok != ')') |
| 1318 | return ErrorP("Expected ')' in prototype"); |
| 1319 | |
| 1320 | // success. |
| 1321 | getNextToken(); // eat ')'. |
| 1322 | |
| 1323 | // Verify right number of names for operator. |
| 1324 | if (Kind && ArgNames.size() != Kind) |
| 1325 | return ErrorP("Invalid number of operands for operator"); |
| 1326 | |
| 1327 | return new PrototypeAST(FnName, ArgNames, Kind != 0, BinaryPrecedence); |
| 1328 | } |
| 1329 | |
| 1330 | /// definition ::= 'def' prototype expression |
| 1331 | static FunctionAST *ParseDefinition() { |
| 1332 | getNextToken(); // eat def. |
| 1333 | PrototypeAST *Proto = ParsePrototype(); |
| 1334 | if (Proto == 0) return 0; |
| 1335 | |
| 1336 | if (ExprAST *E = ParseExpression()) |
| 1337 | return new FunctionAST(Proto, E); |
| 1338 | return 0; |
| 1339 | } |
| 1340 | |
| 1341 | /// toplevelexpr ::= expression |
| 1342 | static FunctionAST *ParseTopLevelExpr() { |
| 1343 | if (ExprAST *E = ParseExpression()) { |
| 1344 | // Make an anonymous proto. |
| 1345 | PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); |
| 1346 | return new FunctionAST(Proto, E); |
| 1347 | } |
| 1348 | return 0; |
| 1349 | } |
| 1350 | |
| 1351 | /// external ::= 'extern' prototype |
| 1352 | static PrototypeAST *ParseExtern() { |
| 1353 | getNextToken(); // eat extern. |
| 1354 | return ParsePrototype(); |
| 1355 | } |
| 1356 | |
| 1357 | //===----------------------------------------------------------------------===// |
| 1358 | // Code Generation |
| 1359 | //===----------------------------------------------------------------------===// |
| 1360 | |
| 1361 | static Module *TheModule; |
Owen Anderson | d1fbd14 | 2009-07-08 20:50:47 +0000 | [diff] [blame] | 1362 | static IRBuilder<> Builder(getGlobalContext()); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1363 | static std::map<std::string, Value*> NamedValues; |
| 1364 | static FunctionPassManager *TheFPM; |
| 1365 | |
| 1366 | Value *ErrorV(const char *Str) { Error(Str); return 0; } |
| 1367 | |
| 1368 | Value *NumberExprAST::Codegen() { |
Owen Anderson | 6f83c9c | 2009-07-27 20:59:43 +0000 | [diff] [blame] | 1369 | return ConstantFP::get(getGlobalContext(), APFloat(Val)); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1370 | } |
| 1371 | |
| 1372 | Value *VariableExprAST::Codegen() { |
| 1373 | // Look this variable up in the function. |
| 1374 | Value *V = NamedValues[Name]; |
| 1375 | return V ? V : ErrorV("Unknown variable name"); |
| 1376 | } |
| 1377 | |
| 1378 | Value *UnaryExprAST::Codegen() { |
| 1379 | Value *OperandV = Operand->Codegen(); |
| 1380 | if (OperandV == 0) return 0; |
| 1381 | |
| 1382 | Function *F = TheModule->getFunction(std::string("unary")+Opcode); |
| 1383 | if (F == 0) |
| 1384 | return ErrorV("Unknown unary operator"); |
| 1385 | |
| 1386 | return Builder.CreateCall(F, OperandV, "unop"); |
| 1387 | } |
| 1388 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1389 | Value *BinaryExprAST::Codegen() { |
| 1390 | Value *L = LHS->Codegen(); |
| 1391 | Value *R = RHS->Codegen(); |
| 1392 | if (L == 0 || R == 0) return 0; |
| 1393 | |
| 1394 | switch (Op) { |
Eric Christopher | 2214b81 | 2010-06-14 06:09:39 +0000 | [diff] [blame] | 1395 | case '+': return Builder.CreateFAdd(L, R, "addtmp"); |
| 1396 | case '-': return Builder.CreateFSub(L, R, "subtmp"); |
| 1397 | case '*': return Builder.CreateFMul(L, R, "multmp"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1398 | case '<': |
Chris Lattner | 7115521 | 2007-11-06 01:39:12 +0000 | [diff] [blame] | 1399 | L = Builder.CreateFCmpULT(L, R, "cmptmp"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1400 | // Convert bool 0/1 to double 0.0 or 1.0 |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1401 | return Builder.CreateUIToFP(L, Type::getDoubleTy(getGlobalContext()), |
| 1402 | "booltmp"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1403 | default: break; |
| 1404 | } |
| 1405 | |
| 1406 | // If it wasn't a builtin binary operator, it must be a user defined one. Emit |
| 1407 | // a call to it. |
| 1408 | Function *F = TheModule->getFunction(std::string("binary")+Op); |
| 1409 | assert(F && "binary operator not found!"); |
| 1410 | |
| 1411 | Value *Ops[] = { L, R }; |
| 1412 | return Builder.CreateCall(F, Ops, Ops+2, "binop"); |
| 1413 | } |
| 1414 | |
| 1415 | Value *CallExprAST::Codegen() { |
| 1416 | // Look up the name in the global module table. |
| 1417 | Function *CalleeF = TheModule->getFunction(Callee); |
| 1418 | if (CalleeF == 0) |
| 1419 | return ErrorV("Unknown function referenced"); |
| 1420 | |
| 1421 | // If argument mismatch error. |
| 1422 | if (CalleeF->arg_size() != Args.size()) |
| 1423 | return ErrorV("Incorrect # arguments passed"); |
| 1424 | |
| 1425 | std::vector<Value*> ArgsV; |
| 1426 | for (unsigned i = 0, e = Args.size(); i != e; ++i) { |
| 1427 | ArgsV.push_back(Args[i]->Codegen()); |
| 1428 | if (ArgsV.back() == 0) return 0; |
| 1429 | } |
| 1430 | |
| 1431 | return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp"); |
| 1432 | } |
| 1433 | |
| 1434 | Value *IfExprAST::Codegen() { |
| 1435 | Value *CondV = Cond->Codegen(); |
| 1436 | if (CondV == 0) return 0; |
| 1437 | |
| 1438 | // Convert condition to a bool by comparing equal to 0.0. |
| 1439 | CondV = Builder.CreateFCmpONE(CondV, |
Owen Anderson | 6f83c9c | 2009-07-27 20:59:43 +0000 | [diff] [blame] | 1440 | ConstantFP::get(getGlobalContext(), APFloat(0.0)), |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1441 | "ifcond"); |
| 1442 | |
| 1443 | Function *TheFunction = Builder.GetInsertBlock()->getParent(); |
| 1444 | |
| 1445 | // Create blocks for the then and else cases. Insert the 'then' block at the |
| 1446 | // end of the function. |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 1447 | BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunction); |
| 1448 | BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); |
| 1449 | BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1450 | |
| 1451 | Builder.CreateCondBr(CondV, ThenBB, ElseBB); |
| 1452 | |
| 1453 | // Emit then value. |
| 1454 | Builder.SetInsertPoint(ThenBB); |
| 1455 | |
| 1456 | Value *ThenV = Then->Codegen(); |
| 1457 | if (ThenV == 0) return 0; |
| 1458 | |
| 1459 | Builder.CreateBr(MergeBB); |
| 1460 | // Codegen of 'Then' can change the current block, update ThenBB for the PHI. |
| 1461 | ThenBB = Builder.GetInsertBlock(); |
| 1462 | |
| 1463 | // Emit else block. |
| 1464 | TheFunction->getBasicBlockList().push_back(ElseBB); |
| 1465 | Builder.SetInsertPoint(ElseBB); |
| 1466 | |
| 1467 | Value *ElseV = Else->Codegen(); |
| 1468 | if (ElseV == 0) return 0; |
| 1469 | |
| 1470 | Builder.CreateBr(MergeBB); |
| 1471 | // Codegen of 'Else' can change the current block, update ElseBB for the PHI. |
| 1472 | ElseBB = Builder.GetInsertBlock(); |
| 1473 | |
| 1474 | // Emit merge block. |
| 1475 | TheFunction->getBasicBlockList().push_back(MergeBB); |
| 1476 | Builder.SetInsertPoint(MergeBB); |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1477 | PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), |
| 1478 | "iftmp"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1479 | |
| 1480 | PN->addIncoming(ThenV, ThenBB); |
| 1481 | PN->addIncoming(ElseV, ElseBB); |
| 1482 | return PN; |
| 1483 | } |
| 1484 | |
| 1485 | Value *ForExprAST::Codegen() { |
| 1486 | // Output this as: |
| 1487 | // ... |
| 1488 | // start = startexpr |
| 1489 | // goto loop |
| 1490 | // loop: |
| 1491 | // variable = phi [start, loopheader], [nextvariable, loopend] |
| 1492 | // ... |
| 1493 | // bodyexpr |
| 1494 | // ... |
| 1495 | // loopend: |
| 1496 | // step = stepexpr |
| 1497 | // nextvariable = variable + step |
| 1498 | // endcond = endexpr |
| 1499 | // br endcond, loop, endloop |
| 1500 | // outloop: |
| 1501 | |
| 1502 | // Emit the start code first, without 'variable' in scope. |
| 1503 | Value *StartVal = Start->Codegen(); |
| 1504 | if (StartVal == 0) return 0; |
| 1505 | |
| 1506 | // Make the new basic block for the loop header, inserting after current |
| 1507 | // block. |
| 1508 | Function *TheFunction = Builder.GetInsertBlock()->getParent(); |
| 1509 | BasicBlock *PreheaderBB = Builder.GetInsertBlock(); |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 1510 | BasicBlock *LoopBB = BasicBlock::Create(getGlobalContext(), "loop", TheFunction); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1511 | |
| 1512 | // Insert an explicit fall through from the current block to the LoopBB. |
| 1513 | Builder.CreateBr(LoopBB); |
| 1514 | |
| 1515 | // Start insertion in LoopBB. |
| 1516 | Builder.SetInsertPoint(LoopBB); |
| 1517 | |
| 1518 | // Start the PHI node with an entry for Start. |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 1519 | PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str()); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1520 | Variable->addIncoming(StartVal, PreheaderBB); |
| 1521 | |
| 1522 | // Within the loop, the variable is defined equal to the PHI node. If it |
| 1523 | // shadows an existing variable, we have to restore it, so save it now. |
| 1524 | Value *OldVal = NamedValues[VarName]; |
| 1525 | NamedValues[VarName] = Variable; |
| 1526 | |
| 1527 | // Emit the body of the loop. This, like any other expr, can change the |
| 1528 | // current BB. Note that we ignore the value computed by the body, but don't |
| 1529 | // allow an error. |
| 1530 | if (Body->Codegen() == 0) |
| 1531 | return 0; |
| 1532 | |
| 1533 | // Emit the step value. |
| 1534 | Value *StepVal; |
| 1535 | if (Step) { |
| 1536 | StepVal = Step->Codegen(); |
| 1537 | if (StepVal == 0) return 0; |
| 1538 | } else { |
| 1539 | // If not specified, use 1.0. |
Owen Anderson | 6f83c9c | 2009-07-27 20:59:43 +0000 | [diff] [blame] | 1540 | StepVal = ConstantFP::get(getGlobalContext(), APFloat(1.0)); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1541 | } |
| 1542 | |
Chris Lattner | f57fcf7 | 2010-09-01 20:09:20 +0000 | [diff] [blame] | 1543 | Value *NextVar = Builder.CreateFAdd(Variable, StepVal, "nextvar"); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1544 | |
| 1545 | // Compute the end condition. |
| 1546 | Value *EndCond = End->Codegen(); |
| 1547 | if (EndCond == 0) return EndCond; |
| 1548 | |
| 1549 | // Convert condition to a bool by comparing equal to 0.0. |
| 1550 | EndCond = Builder.CreateFCmpONE(EndCond, |
Owen Anderson | 6f83c9c | 2009-07-27 20:59:43 +0000 | [diff] [blame] | 1551 | ConstantFP::get(getGlobalContext(), APFloat(0.0)), |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1552 | "loopcond"); |
| 1553 | |
| 1554 | // Create the "after loop" block and insert it. |
| 1555 | BasicBlock *LoopEndBB = Builder.GetInsertBlock(); |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 1556 | BasicBlock *AfterBB = BasicBlock::Create(getGlobalContext(), "afterloop", TheFunction); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1557 | |
| 1558 | // Insert the conditional branch into the end of LoopEndBB. |
| 1559 | Builder.CreateCondBr(EndCond, LoopBB, AfterBB); |
| 1560 | |
| 1561 | // Any new code will be inserted in AfterBB. |
| 1562 | Builder.SetInsertPoint(AfterBB); |
| 1563 | |
| 1564 | // Add a new entry to the PHI node for the backedge. |
| 1565 | Variable->addIncoming(NextVar, LoopEndBB); |
| 1566 | |
| 1567 | // Restore the unshadowed variable. |
| 1568 | if (OldVal) |
| 1569 | NamedValues[VarName] = OldVal; |
| 1570 | else |
| 1571 | NamedValues.erase(VarName); |
| 1572 | |
| 1573 | |
| 1574 | // for expr always returns 0.0. |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 1575 | return Constant::getNullValue(Type::getDoubleTy(getGlobalContext())); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1576 | } |
| 1577 | |
| 1578 | Function *PrototypeAST::Codegen() { |
| 1579 | // Make the function type: double(double,double) etc. |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1580 | std::vector<const Type*> Doubles(Args.size(), |
| 1581 | Type::getDoubleTy(getGlobalContext())); |
| 1582 | FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()), |
| 1583 | Doubles, false); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1584 | |
Gabor Greif | df7d2b4 | 2008-04-19 22:25:09 +0000 | [diff] [blame] | 1585 | Function *F = Function::Create(FT, Function::ExternalLinkage, Name, TheModule); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1586 | |
| 1587 | // If F conflicted, there was already something named 'Name'. If it has a |
| 1588 | // body, don't allow redefinition or reextern. |
| 1589 | if (F->getName() != Name) { |
| 1590 | // Delete the one we just made and get the existing one. |
| 1591 | F->eraseFromParent(); |
| 1592 | F = TheModule->getFunction(Name); |
| 1593 | |
| 1594 | // If F already has a body, reject this. |
| 1595 | if (!F->empty()) { |
| 1596 | ErrorF("redefinition of function"); |
| 1597 | return 0; |
| 1598 | } |
| 1599 | |
| 1600 | // If F took a different number of args, reject. |
| 1601 | if (F->arg_size() != Args.size()) { |
| 1602 | ErrorF("redefinition of function with different # args"); |
| 1603 | return 0; |
| 1604 | } |
| 1605 | } |
| 1606 | |
| 1607 | // Set names for all arguments. |
| 1608 | unsigned Idx = 0; |
| 1609 | for (Function::arg_iterator AI = F->arg_begin(); Idx != Args.size(); |
| 1610 | ++AI, ++Idx) { |
| 1611 | AI->setName(Args[Idx]); |
| 1612 | |
| 1613 | // Add arguments to variable symbol table. |
| 1614 | NamedValues[Args[Idx]] = AI; |
| 1615 | } |
| 1616 | |
| 1617 | return F; |
| 1618 | } |
| 1619 | |
| 1620 | Function *FunctionAST::Codegen() { |
| 1621 | NamedValues.clear(); |
| 1622 | |
| 1623 | Function *TheFunction = Proto->Codegen(); |
| 1624 | if (TheFunction == 0) |
| 1625 | return 0; |
| 1626 | |
| 1627 | // If this is an operator, install it. |
| 1628 | if (Proto->isBinaryOp()) |
| 1629 | BinopPrecedence[Proto->getOperatorName()] = Proto->getBinaryPrecedence(); |
| 1630 | |
| 1631 | // Create a new basic block to start insertion into. |
Owen Anderson | 1d0be15 | 2009-08-13 21:58:54 +0000 | [diff] [blame] | 1632 | BasicBlock *BB = BasicBlock::Create(getGlobalContext(), "entry", TheFunction); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1633 | Builder.SetInsertPoint(BB); |
| 1634 | |
| 1635 | if (Value *RetVal = Body->Codegen()) { |
| 1636 | // Finish off the function. |
| 1637 | Builder.CreateRet(RetVal); |
| 1638 | |
| 1639 | // Validate the generated code, checking for consistency. |
| 1640 | verifyFunction(*TheFunction); |
| 1641 | |
| 1642 | // Optimize the function. |
| 1643 | TheFPM->run(*TheFunction); |
| 1644 | |
| 1645 | return TheFunction; |
| 1646 | } |
| 1647 | |
| 1648 | // Error reading body, remove function. |
| 1649 | TheFunction->eraseFromParent(); |
| 1650 | |
| 1651 | if (Proto->isBinaryOp()) |
| 1652 | BinopPrecedence.erase(Proto->getOperatorName()); |
| 1653 | return 0; |
| 1654 | } |
| 1655 | |
| 1656 | //===----------------------------------------------------------------------===// |
| 1657 | // Top-Level parsing and JIT Driver |
| 1658 | //===----------------------------------------------------------------------===// |
| 1659 | |
| 1660 | static ExecutionEngine *TheExecutionEngine; |
| 1661 | |
| 1662 | static void HandleDefinition() { |
| 1663 | if (FunctionAST *F = ParseDefinition()) { |
| 1664 | if (Function *LF = F->Codegen()) { |
| 1665 | fprintf(stderr, "Read function definition:"); |
| 1666 | LF->dump(); |
| 1667 | } |
| 1668 | } else { |
| 1669 | // Skip token for error recovery. |
| 1670 | getNextToken(); |
| 1671 | } |
| 1672 | } |
| 1673 | |
| 1674 | static void HandleExtern() { |
| 1675 | if (PrototypeAST *P = ParseExtern()) { |
| 1676 | if (Function *F = P->Codegen()) { |
| 1677 | fprintf(stderr, "Read extern: "); |
| 1678 | F->dump(); |
| 1679 | } |
| 1680 | } else { |
| 1681 | // Skip token for error recovery. |
| 1682 | getNextToken(); |
| 1683 | } |
| 1684 | } |
| 1685 | |
| 1686 | static void HandleTopLevelExpression() { |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1687 | // Evaluate a top-level expression into an anonymous function. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1688 | if (FunctionAST *F = ParseTopLevelExpr()) { |
| 1689 | if (Function *LF = F->Codegen()) { |
| 1690 | // JIT the function, returning a function pointer. |
| 1691 | void *FPtr = TheExecutionEngine->getPointerToFunction(LF); |
| 1692 | |
| 1693 | // Cast it to the right type (takes no arguments, returns a double) so we |
| 1694 | // can call it as a native function. |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1695 | double (*FP)() = (double (*)())(intptr_t)FPtr; |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1696 | fprintf(stderr, "Evaluated to %f\n", FP()); |
| 1697 | } |
| 1698 | } else { |
| 1699 | // Skip token for error recovery. |
| 1700 | getNextToken(); |
| 1701 | } |
| 1702 | } |
| 1703 | |
| 1704 | /// top ::= definition | external | expression | ';' |
| 1705 | static void MainLoop() { |
| 1706 | while (1) { |
| 1707 | fprintf(stderr, "ready> "); |
| 1708 | switch (CurTok) { |
| 1709 | case tok_eof: return; |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1710 | case ';': getNextToken(); break; // ignore top-level semicolons. |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1711 | case tok_def: HandleDefinition(); break; |
| 1712 | case tok_extern: HandleExtern(); break; |
| 1713 | default: HandleTopLevelExpression(); break; |
| 1714 | } |
| 1715 | } |
| 1716 | } |
| 1717 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1718 | //===----------------------------------------------------------------------===// |
| 1719 | // "Library" functions that can be "extern'd" from user code. |
| 1720 | //===----------------------------------------------------------------------===// |
| 1721 | |
| 1722 | /// putchard - putchar that takes a double and returns 0. |
| 1723 | extern "C" |
| 1724 | double putchard(double X) { |
| 1725 | putchar((char)X); |
| 1726 | return 0; |
| 1727 | } |
| 1728 | |
| 1729 | /// printd - printf that takes a double prints it as "%f\n", returning 0. |
| 1730 | extern "C" |
| 1731 | double printd(double X) { |
| 1732 | printf("%f\n", X); |
| 1733 | return 0; |
| 1734 | } |
| 1735 | |
| 1736 | //===----------------------------------------------------------------------===// |
| 1737 | // Main driver code. |
| 1738 | //===----------------------------------------------------------------------===// |
| 1739 | |
| 1740 | int main() { |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1741 | InitializeNativeTarget(); |
| 1742 | LLVMContext &Context = getGlobalContext(); |
| 1743 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1744 | // Install standard binary operators. |
| 1745 | // 1 is lowest precedence. |
| 1746 | BinopPrecedence['<'] = 10; |
| 1747 | BinopPrecedence['+'] = 20; |
| 1748 | BinopPrecedence['-'] = 20; |
| 1749 | BinopPrecedence['*'] = 40; // highest. |
| 1750 | |
| 1751 | // Prime the first token. |
| 1752 | fprintf(stderr, "ready> "); |
| 1753 | getNextToken(); |
| 1754 | |
| 1755 | // Make the module, which holds all the code. |
Erick Tryzelaar | fd1ec5e | 2009-09-22 21:14:49 +0000 | [diff] [blame] | 1756 | TheModule = new Module("my cool jit", Context); |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1757 | |
Jeffrey Yasskin | f0356fe | 2010-01-27 20:34:15 +0000 | [diff] [blame] | 1758 | // Create the JIT. This takes ownership of the module. |
Jeffrey Yasskin | 42fc558 | 2010-02-11 19:15:20 +0000 | [diff] [blame] | 1759 | std::string ErrStr; |
| 1760 | TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create(); |
| 1761 | if (!TheExecutionEngine) { |
| 1762 | fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str()); |
| 1763 | exit(1); |
| 1764 | } |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1765 | |
Jeffrey Yasskin | f0356fe | 2010-01-27 20:34:15 +0000 | [diff] [blame] | 1766 | FunctionPassManager OurFPM(TheModule); |
Reid Kleckner | 60130f0 | 2009-08-26 20:58:25 +0000 | [diff] [blame] | 1767 | |
| 1768 | // Set up the optimizer pipeline. Start with registering info about how the |
| 1769 | // target lays out data structures. |
| 1770 | OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData())); |
Dan Gohman | dfa1a79 | 2010-11-15 18:41:10 +0000 | [diff] [blame^] | 1771 | // Provide basic AliasAnalysis support for GVN. |
| 1772 | OurFPM.add(createBasicAliasAnalysisPass()); |
Reid Kleckner | 60130f0 | 2009-08-26 20:58:25 +0000 | [diff] [blame] | 1773 | // Do simple "peephole" optimizations and bit-twiddling optzns. |
| 1774 | OurFPM.add(createInstructionCombiningPass()); |
| 1775 | // Reassociate expressions. |
| 1776 | OurFPM.add(createReassociatePass()); |
| 1777 | // Eliminate Common SubExpressions. |
| 1778 | OurFPM.add(createGVNPass()); |
| 1779 | // Simplify the control flow graph (deleting unreachable blocks, etc). |
| 1780 | OurFPM.add(createCFGSimplificationPass()); |
| 1781 | |
Nick Lewycky | 422094c | 2009-09-13 21:38:54 +0000 | [diff] [blame] | 1782 | OurFPM.doInitialization(); |
| 1783 | |
Reid Kleckner | 60130f0 | 2009-08-26 20:58:25 +0000 | [diff] [blame] | 1784 | // Set the global so the code gen can use this. |
| 1785 | TheFPM = &OurFPM; |
| 1786 | |
| 1787 | // Run the main "interpreter loop" now. |
| 1788 | MainLoop(); |
| 1789 | |
| 1790 | TheFPM = 0; |
| 1791 | |
| 1792 | // Print out all of the generated code. |
| 1793 | TheModule->dump(); |
| 1794 | |
Chris Lattner | 58f2c87 | 2007-11-02 05:42:52 +0000 | [diff] [blame] | 1795 | return 0; |
| 1796 | } |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 1797 | </pre> |
| 1798 | </div> |
| 1799 | |
Chris Lattner | 729eb14 | 2008-02-10 19:11:04 +0000 | [diff] [blame] | 1800 | <a href="LangImpl7.html">Next: Extending the language: mutable variables / SSA construction</a> |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 1801 | </div> |
| 1802 | |
| 1803 | <!-- *********************************************************************** --> |
| 1804 | <hr> |
| 1805 | <address> |
| 1806 | <a href="http://jigsaw.w3.org/css-validator/check/referer"><img |
| 1807 | src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a> |
| 1808 | <a href="http://validator.w3.org/check/referer"><img |
| 1809 | src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a> |
| 1810 | |
| 1811 | <a href="mailto:sabre@nondot.org">Chris Lattner</a><br> |
| 1812 | <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br> |
Dan Gohman | 523e392 | 2010-02-03 17:27:31 +0000 | [diff] [blame] | 1813 | Last modified: $Date$ |
Chris Lattner | c9d5d2c | 2007-11-01 06:49:54 +0000 | [diff] [blame] | 1814 | </address> |
| 1815 | </body> |
| 1816 | </html> |