<title>Kaleidoscope: Extending the Language: Control Flow</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="author" content="Chris Lattner">
- <link rel="stylesheet" href="../llvm.css" type="text/css">
+ <link rel="stylesheet" href="../_static/llvm.css" type="text/css">
</head>
<body>
-<div class="doc_title">Kaleidoscope: Extending the Language: Control Flow</div>
+<h1>Kaleidoscope: Extending the Language: Control Flow</h1>
<ul>
<li><a href="index.html">Up to Tutorial Index</a></li>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="intro">Chapter 5 Introduction</a></div>
+<h2><a name="intro">Chapter 5 Introduction</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Welcome to Chapter 5 of the "<a href="index.html">Implementing a language
with LLVM</a>" tutorial. Parts 1-4 described the implementation of the simple
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="ifthen">If/Then/Else</a></div>
+<h2><a name="ifthen">If/Then/Else</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
Extending Kaleidoscope to support if/then/else is quite straightforward. It
<p>Now that we know what we "want", lets break this down into its constituent
pieces.</p>
-</div>
-
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="iflexer">Lexer Extensions for
-If/Then/Else</a></div>
+<h4><a name="iflexer">Lexer Extensions for If/Then/Else</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>The lexer extensions are straightforward. First we add new enum values
for the relevant tokens:</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="ifast">AST Extensions for
- If/Then/Else</a></div>
+<h4><a name="ifast">AST Extensions for If/Then/Else</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>To represent the new expression we add a new AST node for it:</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="ifparser">Parser Extensions for
-If/Then/Else</a></div>
+<h4><a name="ifparser">Parser Extensions for If/Then/Else</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>Now that we have the relevant tokens coming from the lexer and we have the
AST node to build, our parsing logic is relatively straightforward. First we
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="ifir">LLVM IR for If/Then/Else</a></div>
+<h4><a name="ifir">LLVM IR for If/Then/Else</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>Now that we have it parsing and building the AST, the final piece is adding
LLVM code generation support. This is the most interesting part of the
define double @baz(double %x) {
entry:
- %ifcond = fcmp one double %x, 0.000000e+00
- br i1 %ifcond, label %then, label %else
+ %ifcond = fcmp one double %x, 0.000000e+00
+ br i1 %ifcond, label %then, label %else
then: ; preds = %entry
- %calltmp = call double @foo()
- br label %ifcont
+ %calltmp = call double @foo()
+ br label %ifcont
else: ; preds = %entry
- %calltmp1 = call double @bar()
- br label %ifcont
+ %calltmp1 = call double @bar()
+ br label %ifcont
ifcont: ; preds = %else, %then
- %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
- ret double %iftmp
+ %iftmp = phi double [ %calltmp, %then ], [ %calltmp1, %else ]
+ ret double %iftmp
}
</pre>
</div>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="ifcodegen">Code Generation for
-If/Then/Else</a></div>
+<h4><a name="ifcodegen">Code Generation for If/Then/Else</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>In order to generate code for this, we implement the <tt>Codegen</tt> method
for <tt>IfExprAST</tt>:</p>
// Emit merge block.
TheFunction->getBasicBlockList().push_back(MergeBB);
Builder.SetInsertPoint(MergeBB);
- PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
+ PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
"iftmp");
PN->addIncoming(ThenV, ThenBB);
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="for">'for' Loop Expression</a></div>
+<h2><a name="for">'for' Loop Expression</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Now that we know how to add basic control flow constructs to the language,
we have the tools to add more powerful things. Lets add something more
<p>As before, lets talk about the changes that we need to Kaleidoscope to
support this.</p>
-</div>
-
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="forlexer">Lexer Extensions for
-the 'for' Loop</a></div>
+<h4><a name="forlexer">Lexer Extensions for the 'for' Loop</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>The lexer extensions are the same sort of thing as for if/then/else:</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="forast">AST Extensions for
-the 'for' Loop</a></div>
+<h4><a name="forast">AST Extensions for the 'for' Loop</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>The AST node is just as simple. It basically boils down to capturing
the variable name and the constituent expressions in the node.</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="forparser">Parser Extensions for
-the 'for' Loop</a></div>
+<h4><a name="forparser">Parser Extensions for the 'for' Loop</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>The parser code is also fairly standard. The only interesting thing here is
handling of the optional step value. The parser code handles it by checking to
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="forir">LLVM IR for
-the 'for' Loop</a></div>
+<h4><a name="forir">LLVM IR for the 'for' Loop</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>Now we get to the good part: the LLVM IR we want to generate for this thing.
With the simple example above, we get this LLVM IR (note that this dump is
define double @printstar(double %n) {
entry:
- ; initial value = 1.0 (inlined into phi)
- br label %loop
+ ; initial value = 1.0 (inlined into phi)
+ br label %loop
loop: ; preds = %loop, %entry
- %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
- ; body
- %calltmp = call double @putchard(double 4.200000e+01)
- ; increment
- %nextvar = fadd double %i, 1.000000e+00
-
- ; termination test
- %cmptmp = fcmp ult double %i, %n
- %booltmp = uitofp i1 %cmptmp to double
- %loopcond = fcmp one double %booltmp, 0.000000e+00
- br i1 %loopcond, label %loop, label %afterloop
+ %i = phi double [ 1.000000e+00, %entry ], [ %nextvar, %loop ]
+ ; body
+ %calltmp = call double @putchard(double 4.200000e+01)
+ ; increment
+ %nextvar = fadd double %i, 1.000000e+00
+
+ ; termination test
+ %cmptmp = fcmp ult double %i, %n
+ %booltmp = uitofp i1 %cmptmp to double
+ %loopcond = fcmp one double %booltmp, 0.000000e+00
+ br i1 %loopcond, label %loop, label %afterloop
afterloop: ; preds = %loop
- ; loop always returns 0.0
- ret double 0.000000e+00
+ ; loop always returns 0.0
+ ret double 0.000000e+00
}
</pre>
</div>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsubsection"><a name="forcodegen">Code Generation for
-the 'for' Loop</a></div>
+<h4><a name="forcodegen">Code Generation for the 'for' Loop</a></h4>
<!-- ======================================================================= -->
-<div class="doc_text">
+<div>
<p>The first part of Codegen is very simple: we just output the start expression
for the loop value:</p>
Builder.SetInsertPoint(LoopBB);
// Start the PHI node with an entry for Start.
- PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
+ PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
Variable->addIncoming(StartVal, PreheaderBB);
</pre>
</div>
</div>
<p>With the code for the body of the loop complete, we just need to finish up
-the control flow for it. This code remembers the end block (for the phi node), then creates the block for the loop exit ("afterloop"). Based on the value of the
-exit condition, it creates a conditional branch that chooses between executing
-the loop again and exiting the loop. Any future code is emitted in the
-"afterloop" block, so it sets the insertion position to it.</p>
+the control flow for it. This code remembers the end block (for the phi node),
+then creates the block for the loop exit ("afterloop"). Based on the value of
+the exit condition, it creates a conditional branch that chooses between
+executing the loop again and exiting the loop. Any future code is emitted in
+the "afterloop" block, so it sets the insertion position to it.</p>
<div class="doc_code">
<pre>
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="code">Full Code Listing</a></div>
+<h2><a name="code">Full Code Listing</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
Here is the complete code listing for our running example, enhanced with the
<div class="doc_code">
<pre>
- # Compile
- g++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
- # Run
- ./toy
+# Compile
+clang++ -g toy.cpp `llvm-config --cppflags --ldflags --libs core jit native` -O3 -o toy
+# Run
+./toy
</pre>
</div>
#include "llvm/DerivedTypes.h"
#include "llvm/ExecutionEngine/ExecutionEngine.h"
#include "llvm/ExecutionEngine/JIT.h"
+#include "llvm/IRBuilder.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/PassManager.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Analysis/Passes.h"
-#include "llvm/Target/TargetData.h"
-#include "llvm/Target/TargetSelect.h"
+#include "llvm/DataLayout.h"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Support/IRBuilder.h"
+#include "llvm/Support/TargetSelect.h"
#include <cstdio>
#include <string>
#include <map>
if (ArgsV.back() == 0) return 0;
}
- return Builder.CreateCall(CalleeF, ArgsV.begin(), ArgsV.end(), "calltmp");
+ return Builder.CreateCall(CalleeF, ArgsV, "calltmp");
}
Value *IfExprAST::Codegen() {
// Emit merge block.
TheFunction->getBasicBlockList().push_back(MergeBB);
Builder.SetInsertPoint(MergeBB);
- PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()),
+ PHINode *PN = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2,
"iftmp");
PN->addIncoming(ThenV, ThenBB);
Builder.SetInsertPoint(LoopBB);
// Start the PHI node with an entry for Start.
- PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), VarName.c_str());
+ PHINode *Variable = Builder.CreatePHI(Type::getDoubleTy(getGlobalContext()), 2, VarName.c_str());
Variable->addIncoming(StartVal, PreheaderBB);
// Within the loop, the variable is defined equal to the PHI node. If it
Function *PrototypeAST::Codegen() {
// Make the function type: double(double,double) etc.
- std::vector<const Type*> Doubles(Args.size(),
- Type::getDoubleTy(getGlobalContext()));
+ std::vector<Type*> Doubles(Args.size(),
+ Type::getDoubleTy(getGlobalContext()));
FunctionType *FT = FunctionType::get(Type::getDoubleTy(getGlobalContext()),
Doubles, false);
// Create the JIT. This takes ownership of the module.
std::string ErrStr;
- TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
+ TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
if (!TheExecutionEngine) {
fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
exit(1);
// Set up the optimizer pipeline. Start with registering info about how the
// target lays out data structures.
- OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
+ OurFPM.add(new DataLayout(*TheExecutionEngine->getDataLayout()));
// Provide basic AliasAnalysis support for GVN.
OurFPM.add(createBasicAliasAnalysisPass());
// Do simple "peephole" optimizations and bit-twiddling optzns.
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
<a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
- <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
+ <a href="http://llvm.org/">The LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
</body>
projects / oota-llvm.git / blobdiff