blob: f54effcd859c4031aa4e33e97e3181d1cefcfbc6 [file] [log] [blame]
Chris Lattner602c832c2007-10-31 06:30:21 +00001<!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: Extending the Language: Control Flow</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: Extending the Language: Control Flow</div>
15
16<div class="doc_author">
17 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
18</div>
19
20<!-- *********************************************************************** -->
21<div class="doc_section"><a name="intro">Part 5 Introduction</a></div>
22<!-- *********************************************************************** -->
23
24<div class="doc_text">
25
26<p>Welcome to Part 5 of the "<a href="index.html">Implementing a language with
27LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
28Kaleidoscope language and included support for generating LLVM IR, following by
29optimizations and a JIT compiler. Unfortunately, as presented, Kaleidoscope is
30mostly useless: it has no control flow other than call and return. This means
31that you can't have conditional branches in the code, significantly limiting its
32power. In this episode of "build that compiler", we'll extend Kaleidoscope to
33have an if/then/else expression plus a simple looping construct.</p>
34
35</div>
36
37<!-- *********************************************************************** -->
38<div class="doc_section"><a name="ifthen">If/Then/Else</a></div>
39<!-- *********************************************************************** -->
40
41<div class="doc_text">
42
43<p>
44Extending Kaleidoscope to support if/then/else is quite straight-forward. It
45basically requires adding lexer support for this "new" concept to the lexer,
46parser, AST, and LLVM code emitter. This example is nice, because it shows how
47easy it is to "grow" a language over time, incrementally extending it as new
48ideas are discovered.</p>
49
50<p>Before we get going on "how" we do this extension, lets talk about what we
51want. The basic idea is that we want to be able to write this sort of thing:
52</p>
53
54<div class="doc_code">
55<pre>
56def fib(x)
57 if x &lt; 3 then
58 1
59 else
60 fib(x-1)+fib(x-2);
61</pre>
62</div>
63
64<p>In Kaleidoscope, every construct is an expression: there are no statements.
65As such, the if/then/else expression needs to return a value like any other.
66Since we're using a mostly functional form, we'll have it evaluate its
67conditional, then return the 'then' or 'else' value based on how the condition
68was resolved. This is very similar to the C "?:" expression.</p>
69
70<p>The semantics of the if/then/else expression is that it first evaluates the
71condition to a boolean equality value: 0.0 is false and everything else is true.
72If the condition is true, the first subexpression is evaluated and returned, if
73the condition is false, the second subexpression is evaluated and returned.
74Since Kaleidoscope allows side-effects, this behavior is important to nail down.
75</p>
76
77<p>Now that we know what we want, lets break this down into its constituent
78pieces.</p>
79
80</div>
81
82<!-- ======================================================================= -->
83<div class="doc_subsubsection"><a name="iflexer">Lexer Extensions for
84If/Then/Else</a></div>
85<!-- ======================================================================= -->
86
87
88<div class="doc_text">
89
90<p>The lexer extensions are straight-forward. First we add new enum values
91for the relevant tokens:</p>
92
93<div class="doc_code">
94<pre>
95 // control
96 tok_if = -6, tok_then = -7, tok_else = -8,
97</pre>
98</div>
99
100<p>Once we have that, we recognize the new keywords in the lexer, pretty simple
101stuff:</p>
102
103<div class="doc_code">
104<pre>
105 ...
106 if (IdentifierStr == "def") return tok_def;
107 if (IdentifierStr == "extern") return tok_extern;
108 <b>if (IdentifierStr == "if") return tok_if;
109 if (IdentifierStr == "then") return tok_then;
110 if (IdentifierStr == "else") return tok_else;</b>
111 return tok_identifier;
112</pre>
113</div>
114
115</div>
116
117<!-- ======================================================================= -->
118<div class="doc_subsubsection"><a name="ifast">AST Extensions for
119 If/Then/Else </a></div>
120<!-- ======================================================================= -->
121
122<div class="doc_text">
123
124<p>To represent the new expression we add a new AST node for it:</p>
125
126<div class="doc_code">
127<pre>
128/// IfExprAST - Expression class for if/then/else.
129class IfExprAST : public ExprAST {
130 ExprAST *Cond, *Then, *Else;
131public:
132 IfExprAST(ExprAST *cond, ExprAST *then, ExprAST *_else)
133 : Cond(cond), Then(then), Else(_else) {}
134 virtual Value *Codegen();
135};
136</pre>
137</div>
138
139<p>The AST node just has pointers to the various subexpressions.</p>
140
141</div>
142
143<!-- ======================================================================= -->
144<div class="doc_subsubsection"><a name="ifparser">Parser Extensions for
145If/Then/Else </a></div>
146<!-- ======================================================================= -->
147
148<div class="doc_text">
149
150<p>Now that we have the relevant tokens coming from the lexer and we have the
151AST node to build, our parsing logic is relatively straight-forward. First we
152define a new parsing function:</p>
153
154<div class="doc_code">
155<pre>
156/// ifexpr ::= 'if' expression 'then' expression 'else' expression
157static ExprAST *ParseIfExpr() {
158 getNextToken(); // eat the if.
159
160 // condition.
161 ExprAST *Cond = ParseExpression();
162 if (!Cond) return 0;
163
164 if (CurTok != tok_then)
165 return Error("expected then");
166 getNextToken(); // eat the then
167
168 ExprAST *Then = ParseExpression();
169 if (Then == 0) return 0;
170
171 if (CurTok != tok_else)
172 return Error("expected else");
173
174 getNextToken();
175
176 ExprAST *Else = ParseExpression();
177 if (!Else) return 0;
178
179 return new IfExprAST(Cond, Then, Else);
180}
181</pre>
182</div>
183
184<p>Next we hook it up as a primary expression:</p>
185
186<div class="doc_code">
187<pre>
188static ExprAST *ParsePrimary() {
189 switch (CurTok) {
190 default: return Error("unknown token when expecting an expression");
191 case tok_identifier: return ParseIdentifierExpr();
192 case tok_number: return ParseNumberExpr();
193 case '(': return ParseParenExpr();
194 <b>case tok_if: return ParseIfExpr();</b>
195 }
196}
197</pre>
198</div>
199
200</div>
201
202<!-- ======================================================================= -->
203<div class="doc_subsubsection"><a name="ifir">LLVM IR for If/Then/Else</a></div>
204<!-- ======================================================================= -->
205
206<div class="doc_text">
207
208<p>Now that we have it parsing and building the AST, the final piece is adding
209LLVM code generation support. This is the most interesting part of the
210if/then/else example, because this is where it starts to introduce new concepts.
211All of the code above has been described in previous chapters fairly thoroughly.
212</p>
213
214<p>To motivate the code we want to produce, lets take a look at a simple
215example. Consider:</p>
216
217<div class="doc_code">
218<pre>
219extern foo();
220extern bar();
221def baz(x) if x then foo() else bar();
222</pre>
223</div>
224
225<p>If you disable optimizations, the code you'll (soon) get from Kaleidoscope
226looks like this:</p>
227
228<div class="doc_code">
229<pre>
230declare double @foo()
231
232declare double @bar()
233
234define double @baz(double %x) {
235entry:
236 %ifcond = fcmp one double %x, 0.000000e+00
237 br i1 %ifcond, label %then, label %else
238
239then: ; preds = %entry
240 %calltmp = call double @foo()
241 br label %ifcont
242
243else: ; preds = %entry
244 %calltmp1 = call double @bar()
245 br label %ifcont
246
247ifcont: ; preds = %else, %then
248 %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
249 ret double %iftmp
250}
251</pre>
252</div>
253
254<p>To visualize the control flow graph, you can use a nifty feature of the LLVM
255'<a href="http://llvm.org/cmds/opt.html">opt</a>' tool. If you put this LLVM IR
256into "t.ll" and run "<tt>llvm-as &lt; t.ll | opt -analyze -view-cfg</tt>", <a
257href="../ProgrammersManual.html#ViewGraph">a window will pop up</a> and you'll
258see this graph:</p>
259
260<center><img src="LangImpl5-cfg.png" alt="Example CFG" width="423"
261height="315"></center>
262
263<p>Another way to get this is to call "<tt>F-&gt;viewCFG()</tt>" or
264"<tt>F-&gt;viewCFGOnly()</tt>" (where F is a "<tt>Function*</tt>") either by
265inserting actual calls into the code and recompiling or by calling these in the
266debugger. LLVM has many nice features for visualizing various graphs.</p>
267
268<p>Coming back to the generated code, it is fairly simple: the entry block
269evaluates the conditional expression ("x" in our case here) and compares the
270result to 0.0 with the "<tt><a href="../LangRef.html#i_fcmp">fcmp</a> one</tt>"
271instruction ('one' is "ordered and not equal"). Based on the result of this
272expression, the code jumps to either the "then" or "else" blocks, which contain
273the expressions for the true/false case.</p>
274
275<p>Once the then/else blocks is finished executing, they both branch back to the
276else block to execute the code that happens after the if/then/else. In this
277case the only thing left to do is to return to the caller of the function. The
278question then becomes: how does the code know which expression to return?</p>
279
280<p>The answer to this question involves an important SSA operation: the
281<a href="http://en.wikipedia.org/wiki/Static_single_assignment_form">Phi
282operation</a>. If you're not familiar with SSA, <a
283href="http://en.wikipedia.org/wiki/Static_single_assignment_form">the wikipedia
284article</a> is a good introduction and there are various other introductions to
285it available on your favorite search engine. The short version is that
286"execution" of the Phi operation requires "remembering" which block control came
287from. The Phi operation takes on the value corresponding to the input control
288block. In this case, if control comes in from the "then" block, it gets the
289value of "calltmp". If control comes from the "else" block, it gets the value
290of "calltmp1".</p>
291
292<p>At this point, you are probably starting to think "on no! this means my
293simple and elegant front-end will have to start generating SSA form in order to
294use LLVM!". Fortunately, this is not the case, and we strongly advise
295<em>not</em> implementing an SSA construction algorithm in your front-end
296unless there is an amazingly good reason to do so. In practice, there are two
297sorts of values that float around in code written in your average imperative
298programming language that might need Phi nodes:</p>
299
300<ol>
301<li>Code that involves user variables: <tt>x = 1; x = x + 1; </tt></li>
302<li>Values that are implicit in the structure of your AST, such as the phi node
303in this case.</li>
304</ol>
305
306<p>At a future point in this tutorial ("mutable variables"), we'll talk about #1
307in depth. For now, just believe me that you don't need SSA construction to
308handle them. For #2, you have the choice of using the techniques that we will
309describe for #1, or you can insert Phi nodes directly if convenient. In this
310case, it is really really easy to generate the Phi node, so we choose to do it
311directly.</p>
312
313<p>Okay, enough of the motivation and overview, lets generate code!</p>
314
315</div>
316
317<!-- ======================================================================= -->
318<div class="doc_subsubsection"><a name="ifcodegen">Code Generation for
319If/Then/Else</a></div>
320<!-- ======================================================================= -->
321
322<div class="doc_text">
323
324<p>In order to generate code for this, we implement the <tt>Codegen</tt> method
325for <tt>IfExprAST</tt>:</p>
326
327<div class="doc_code">
328<pre>
329Value *IfExprAST::Codegen() {
330 Value *CondV = Cond-&gt;Codegen();
331 if (CondV == 0) return 0;
332
333 // Convert condition to a bool by comparing equal to 0.0.
334 CondV = Builder.CreateFCmpONE(CondV,
335 ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
336 "ifcond");
337</pre>
338</div>
339
340<p>This code is straight-forward and similar to what we saw before. We emit the
341expression for the condition, then compare that value to zero to get a truth
342value as a 1-bit (bool) value.</p>
343
344<div class="doc_code">
345<pre>
346 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
347
348 // Create blocks for the then and else cases. Insert the 'then' block at the
349 // end of the function.
350 BasicBlock *ThenBB = new BasicBlock("then", TheFunction);
351 BasicBlock *ElseBB = new BasicBlock("else");
352 BasicBlock *MergeBB = new BasicBlock("ifcont");
353
354 Builder.CreateCondBr(CondV, ThenBB, ElseBB);
355</pre>
356</div>
357
358<p>This code creates the basic blocks that are related to the if/then/else
359statement, and correspond directly to the blocks in the example above. The
360first line of this gets the current Function object that is being built. It
361gets this by asking the builder for the current BasicBlock, and asking that
362block for its "parent" (the function it is currently embedded into).</p>
363
364<p>Once it has that, it creates three blocks. Note that it passes "TheFunction"
365into the constructor for the "then" block. This causes the constructor to
366automatically insert the new block onto the end of the specified function. The
367other two blocks are created, but aren't yet inserted into the function.</p>
368
369<p>Once the blocks are created, we can emit the conditional branch that chooses
370between them. Note that creating new blocks does not implicitly affect the
371LLVMBuilder, so it is still inserting into the block that the condition
372went into. Also note that it is creating a branch to the "then" block and the
373"else" block, even though the "else" block isn't inserted into the function yet.
374This is all ok: it is the standard way that LLVM supports forward
375references.</p>
376
377<div class="doc_code">
378<pre>
379 // Emit then value.
380 Builder.SetInsertPoint(ThenBB);
381
382 Value *ThenV = Then-&gt;Codegen();
383 if (ThenV == 0) return 0;
384
385 Builder.CreateBr(MergeBB);
386 // Codegen of 'Then' can change the current block, update ThenBB for the PHI.
387 ThenBB = Builder.GetInsertBlock();
388</pre>
389</div>
390
391<p>After the conditional branch is inserted, we move the builder to start
392inserting into the "then" block. Strictly speaking, this call moves the
393insertion point to be at the end of the specified block. However, since the
394"then" block is empty, it also starts out by inserting at the beginning of the
395block. :)</p>
396
397<p>Once the insertion point is set, we recursively codegen the "then" expression
398from the AST. To finish off the then block, we create an unconditional branch
399to the merge block. One interesting (and very important) aspect of the LLVM IR
400is that it <a href="../LangRef.html#functionstructure">requires all basic blocks
401to be "terminated"</a> with a <a href="../LangRef.html#terminators">control flow
402instruction</a> such as return or branch. This means that all control flow,
403<em>including fall throughs</em> must be made explicit in the LLVM IR. If you
404violate this rule, the verifier will emit an error.</p>
405
406<p>The final line here is quite subtle, but is very important. The basic issue
407is that when we create the Phi node in the merge block, we need to set up the
408block/value pairs that indicate how the Phi will work. Importantly, the Phi
409node expects to have an extry for each predecessor of the block in the CFG. Why
410then are we getting the current block when we just set it to ThenBB 5 lines
411above? The problem is that the "Then" expression may actually itself change the
412block that the Builder is emitting into if, for example, it contains a nested
413"if/then/else" expression. Because calling Codegen recursively could
414arbitrarily change the notion of the current block, we are required to get an
415up-to-date value for code that will set up the Phi node.</p>
416
417<div class="doc_code">
418<pre>
419 // Emit else block.
420 TheFunction-&gt;getBasicBlockList().push_back(ElseBB);
421 Builder.SetInsertPoint(ElseBB);
422
423 Value *ElseV = Else-&gt;Codegen();
424 if (ElseV == 0) return 0;
425
426 Builder.CreateBr(MergeBB);
427 // Codegen of 'Else' can change the current block, update ElseBB for the PHI.
428 ElseBB = Builder.GetInsertBlock();
429</pre>
430</div>
431
432<p>Code generation for the 'else' block is basically identical to codegen for
433the 'then' block. The only significant difference is the first line, which adds
434the 'else' block to the function. Recall previously that the 'else' block was
435created, but not added to the function. Now that the 'then' and 'else' blocks
436are emitted, we can finish up with the merge code:</p>
437
438<div class="doc_code">
439<pre>
440 // Emit merge block.
441 TheFunction->getBasicBlockList().push_back(MergeBB);
442 Builder.SetInsertPoint(MergeBB);
443 PHINode *PN = Builder.CreatePHI(Type::DoubleTy, "iftmp");
444
445 PN->addIncoming(ThenV, ThenBB);
446 PN->addIncoming(ElseV, ElseBB);
447 return PN;
448}
449</pre>
450</div>
451
452<p>The first two lines here are now familiar: the first adds the "merge" block
453to the Function object (it was previously floating, like the else block above).
454The second block changes the insertion point so that newly created code will go
455into the "merge" block. Once that is done, we need to create the PHI node and
456set up the block/value pairs for the PHI.</p>
457
458<p>Finally, the CodeGen function returns the phi node as the value computed by
459the if/then/else expression. In our example above, this returned value will
460feed into the code for the top-level function, which will create the return
461instruction.</p>
462
463<p>Overall, we now have the ability to execution conditional code in
464Kaleidoscope. With this extension, Kaleidoscope is a fairly complete language
465that can calculate a wide variety of numeric functions. Next up we'll add
466another useful expression that is familiar from non-functional languages...</p>
467
468</div>
469
470<!-- *********************************************************************** -->
471<div class="doc_section"><a name="for">'for' Loop Expression</a></div>
472<!-- *********************************************************************** -->
473
474<div class="doc_text">
475
Chris Lattnerf5234802007-10-31 06:47:39 +0000476<p>Now that we know how to add basic control flow constructs to the language,
477we have the tools to add more powerful things. Lets add something more
478aggressive, a 'for' expression:</p>
479
480<div class="doc_code">
481<pre>
482 # print 100 '*' (ascii 42) characters
483 extern putchard(char)
484 for x = 1, x &lt; 100, 1.0 in putchard(42);
485</pre>
486</div>
487
488<p>This expression defines a new variable ("x" in this case) which iterates from
489a starting value, while the condition ("x &lt; 100" in this case) is true,
490incrementing by an optional step value ("1.0" in this case). If the step value
491is omitted, it defaults to 1.0. While the loop is true, it executes its
492body expression. Because we don't have anything better to return, we'll just
493define the loop as always returning 0.0. In the future when we have mutable
494variables, it will get more useful.</p>
495
496<p>As before, lets talk about the changes that we need to Kaleidoscope to
497support this.</p>
498
499</div>
500
501<!-- ======================================================================= -->
502<div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
503the 'for' Loop</a></div>
504<!-- ======================================================================= -->
505
506<div class="doc_text">
507
508<p>The lexer extensions are the same sort of thing as for if/then/else:</p>
509
510<div class="doc_code">
511<pre>
512 ... in enum Token ...
513 // control
514 tok_if = -6, tok_then = -7, tok_else = -8,
515<b> tok_for = -9, tok_in = -10</b>
516
517 ... in gettok ...
518 if (IdentifierStr == "def") return tok_def;
519 if (IdentifierStr == "extern") return tok_extern;
520 if (IdentifierStr == "if") return tok_if;
521 if (IdentifierStr == "then") return tok_then;
522 if (IdentifierStr == "else") return tok_else;
523 <b>if (IdentifierStr == "for") return tok_for;
524 if (IdentifierStr == "in") return tok_in;</b>
525 return tok_identifier;
526</pre>
527</div>
528
529</div>
530
531<!-- ======================================================================= -->
532<div class="doc_subsubsection"><a name="forast">AST Extensions for
533the 'for' Loop</a></div>
534<!-- ======================================================================= -->
535
536<div class="doc_text">
537
538<p>The AST node is similarly simple. It basically boils down to capturing
539the variable name and the consituent expressions in the node.</p>
540
541<div class="doc_code">
542<pre>
543/// ForExprAST - Expression class for for/in.
544class ForExprAST : public ExprAST {
545 std::string VarName;
546 ExprAST *Start, *End, *Step, *Body;
547public:
548 ForExprAST(const std::string &amp;varname, ExprAST *start, ExprAST *end,
549 ExprAST *step, ExprAST *body)
550 : VarName(varname), Start(start), End(end), Step(step), Body(body) {}
551 virtual Value *Codegen();
552};
553</pre>
554</div>
555
556</div>
557
558<!-- ======================================================================= -->
559<div class="doc_subsubsection"><a name="forparser">Parser Extensions for
560the 'for' Loop</a></div>
561<!-- ======================================================================= -->
562
563<div class="doc_text">
564
565<p>The parser code is also fairly standard. The only interesting thing here is
566handling of the optional step value. The parser code handles it by checking to
567see if the second comma is present. If not, it sets the step value to null in
568the AST node:</p>
569
570<div class="doc_code">
571<pre>
572/// forexpr ::= 'for' identifer '=' expr ',' expr (',' expr)? 'in' expression
573static ExprAST *ParseForExpr() {
574 getNextToken(); // eat the for.
575
576 if (CurTok != tok_identifier)
577 return Error("expected identifier after for");
578
579 std::string IdName = IdentifierStr;
580 getNextToken(); // eat identifer.
581
582 if (CurTok != '=')
583 return Error("expected '=' after for");
584 getNextToken(); // eat '='.
585
586
587 ExprAST *Start = ParseExpression();
588 if (Start == 0) return 0;
589 if (CurTok != ',')
590 return Error("expected ',' after for start value");
591 getNextToken();
592
593 ExprAST *End = ParseExpression();
594 if (End == 0) return 0;
595
596 // The step value is optional.
597 ExprAST *Step = 0;
598 if (CurTok == ',') {
599 getNextToken();
600 Step = ParseExpression();
601 if (Step == 0) return 0;
602 }
603
604 if (CurTok != tok_in)
605 return Error("expected 'in' after for");
606 getNextToken(); // eat 'in'.
607
608 ExprAST *Body = ParseExpression();
609 if (Body == 0) return 0;
610
611 return new ForExprAST(IdName, Start, End, Step, Body);
612}
613</pre>
614</div>
615
616</div>
617
618<!-- ======================================================================= -->
619<div class="doc_subsubsection"><a name="forir">LLVM IR for
620the 'for' Loop</a></div>
621<!-- ======================================================================= -->
622
623<div class="doc_text">
624
625<p>Now we get to the good part: the LLVM IR we want to generate for this thing.
626</p>
627
628
629
630</div>
631
632<!-- ======================================================================= -->
633<div class="doc_subsubsection"><a name="forcodegen">Code Generation for
634the 'for' Loop</a></div>
635<!-- ======================================================================= -->
636
637<div class="doc_text">
638
639
640<div class="doc_code">
641<pre>
642Value *ForExprAST::Codegen() {
643 // Output this as:
644 // ...
645 // start = startexpr
646 // goto loop
647 // loop:
648 // variable = phi [start, loopheader], [nextvariable, loopend]
649 // ...
650 // bodyexpr
651 // ...
652 // loopend:
653 // step = stepexpr
654 // nextvariable = variable + step
655 // endcond = endexpr
656 // br endcond, loop, endloop
657 // outloop:
658
659 // Emit the start code first, without 'variable' in scope.
660 Value *StartVal = Start-&gt;Codegen();
661 if (StartVal == 0) return 0;
662
663 // Make the new basic block for the loop header, inserting after current
664 // block.
665 Function *TheFunction = Builder.GetInsertBlock()-&gt;getParent();
666 BasicBlock *PreheaderBB = Builder.GetInsertBlock();
667 BasicBlock *LoopBB = new BasicBlock("loop", TheFunction);
668
669 // Insert an explicit fall through from the current block to the LoopBB.
670 // Start insertion in LoopBB.
671 Builder.CreateBr(LoopBB);
672 Builder.SetInsertPoint(LoopBB);
673
674 // Start the PHI node with an entry for Start.
675 PHINode *Variable = Builder.CreatePHI(Type::DoubleTy, VarName.c_str());
676 Variable-&gt;addIncoming(StartVal, PreheaderBB);
677
678 // Within the loop, the variable is defined equal to the PHI node. If it
679 // shadows an existing variable, we have to restore it, so save it now.
680 Value *OldVal = NamedValues[VarName];
681 NamedValues[VarName] = Variable;
682
683 // Emit the body of the loop. This, like any other expr, can change the
684 // current BB. Note that we ignore the value computed by the body, but don't
685 // allow an error.
686 if (Body-&gt;Codegen() == 0)
687 return 0;
688
689 // Emit the step value.
690 Value *StepVal;
691 if (Step) {
692 StepVal = Step-&gt;Codegen();
693 if (StepVal == 0) return 0;
694 } else {
695 // If not specified, use 1.0.
696 StepVal = ConstantFP::get(Type::DoubleTy, APFloat(1.0));
697 }
698
699 Value *NextVar = Builder.CreateAdd(Variable, StepVal, "nextvar");
700
701 // When evaluating the end condition, the value of the variable is the
702 // incremented value.
703 NamedValues[VarName] = Variable;
704
705
706 // Compute the end condition.
707 Value *EndCond = End-&gt;Codegen();
708 if (EndCond == 0) return EndCond;
709
710 // Convert condition to a bool by comparing equal to 0.0.
711 EndCond = Builder.CreateFCmpONE(EndCond,
712 ConstantFP::get(Type::DoubleTy, APFloat(0.0)),
713 "loopcond");
714
715 // Create the "after loop" block and insert it.
716 BasicBlock *LoopEndBB = Builder.GetInsertBlock();
717 BasicBlock *AfterBB = new BasicBlock("afterloop", TheFunction);
718
719 // Insert the conditional branch into the end of LoopEndBB.
720 Builder.CreateCondBr(EndCond, LoopBB, AfterBB);
721
722 // Any new code will be inserted in AfterBB.
723 Builder.SetInsertPoint(AfterBB);
724
725 // Add a new entry to the PHI node for the backedge.
726 Variable-&gt;addIncoming(NextVar, LoopEndBB);
727
728 // Restore the unshadowed variable.
729 if (OldVal)
730 NamedValues[VarName] = OldVal;
731 else
732 NamedValues.erase(VarName);
733
734
735 // for expr always returns 0.0.
736 return Constant::getNullValue(Type::DoubleTy);
737}
738</pre>
739</div>
740
Chris Lattner602c832c2007-10-31 06:30:21 +0000741
742</div>
743
744<!-- *********************************************************************** -->
745<div class="doc_section"><a name="code">Full Code Listing</a></div>
746<!-- *********************************************************************** -->
747
748<div class="doc_text">
749
750<p>
751Here is the complete code listing for our running example, enhanced with the
752if/then/else and for expressions.. To build this example, use:
753</p>
754
755<div class="doc_code">
756<pre>
757 # Compile
758 g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
759 # Run
760 ./toy
761</pre>
762</div>
763
764<p>Here is the code:</p>
765
766<div class="doc_code">
767<pre>
768...
769</pre>
770</div>
771
772</div>
773
774<!-- *********************************************************************** -->
775<hr>
776<address>
777 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
778 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
779 <a href="http://validator.w3.org/check/referer"><img
780 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
781
782 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
783 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
784 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
785</address>
786</body>
787</html>