construction</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: Mutable Variables</div>
+<h1>Kaleidoscope: Extending the Language: Mutable Variables</h1>
<ul>
<li><a href="index.html">Up to Tutorial Index</a></li>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="intro">Chapter 7 Introduction</a></div>
+<h2><a name="intro">Chapter 7 Introduction</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Welcome to Chapter 7 of the "<a href="index.html">Implementing a language
with LLVM</a>" tutorial. In chapters 1 through 6, we've built a very
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="why">Why is this a hard problem?</a></div>
+<h2><a name="why">Why is this a hard problem?</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
To understand why mutable variables cause complexities in SSA construction,
define i32 @test(i1 %Condition) {
entry:
- br i1 %Condition, label %cond_true, label %cond_false
+ br i1 %Condition, label %cond_true, label %cond_false
cond_true:
- %X.0 = load i32* @G
- br label %cond_next
+ %X.0 = load i32* @G
+ br label %cond_next
cond_false:
- %X.1 = load i32* @H
- br label %cond_next
+ %X.1 = load i32* @H
+ br label %cond_next
cond_next:
- %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
- ret i32 %X.2
+ %X.2 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
+ ret i32 %X.2
}
</pre>
</div>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="memory">Memory in LLVM</a></div>
+<h2><a name="memory">Memory in LLVM</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>The 'trick' here is that while LLVM does require all register values to be
in SSA form, it does not require (or permit) memory objects to be in SSA form.
<pre>
define i32 @example() {
entry:
- %X = alloca i32 ; type of %X is i32*.
- ...
- %tmp = load i32* %X ; load the stack value %X from the stack.
- %tmp2 = add i32 %tmp, 1 ; increment it
- store i32 %tmp2, i32* %X ; store it back
- ...
+ %X = alloca i32 ; type of %X is i32*.
+ ...
+ %tmp = load i32* %X ; load the stack value %X from the stack.
+ %tmp2 = add i32 %tmp, 1 ; increment it
+ store i32 %tmp2, i32* %X ; store it back
+ ...
</pre>
</div>
define i32 @test(i1 %Condition) {
entry:
- %X = alloca i32 ; type of %X is i32*.
- br i1 %Condition, label %cond_true, label %cond_false
+ %X = alloca i32 ; type of %X is i32*.
+ br i1 %Condition, label %cond_true, label %cond_false
cond_true:
- %X.0 = load i32* @G
- store i32 %X.0, i32* %X ; Update X
- br label %cond_next
+ %X.0 = load i32* @G
+ store i32 %X.0, i32* %X ; Update X
+ br label %cond_next
cond_false:
- %X.1 = load i32* @H
- store i32 %X.1, i32* %X ; Update X
- br label %cond_next
+ %X.1 = load i32* @H
+ store i32 %X.1, i32* %X ; Update X
+ br label %cond_next
cond_next:
- %X.2 = load i32* %X ; Read X
- ret i32 %X.2
+ %X.2 = load i32* %X ; Read X
+ ret i32 %X.2
}
</pre>
</div>
define i32 @test(i1 %Condition) {
entry:
- br i1 %Condition, label %cond_true, label %cond_false
+ br i1 %Condition, label %cond_true, label %cond_false
cond_true:
- %X.0 = load i32* @G
- br label %cond_next
+ %X.0 = load i32* @G
+ br label %cond_next
cond_false:
- %X.1 = load i32* @H
- br label %cond_next
+ %X.1 = load i32* @H
+ br label %cond_next
cond_next:
- %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
- ret i32 %X.01
+ %X.01 = phi i32 [ %X.1, %cond_false ], [ %X.0, %cond_true ]
+ ret i32 %X.01
}
</pre>
</div>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="kalvars">Mutable Variables in
-Kaleidoscope</a></div>
+<h2><a name="kalvars">Mutable Variables in Kaleidoscope</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Now that we know the sort of problem we want to tackle, lets see what this
looks like in the context of our little Kaleidoscope language. We're going to
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="adjustments">Adjusting Existing Variables for
-Mutation</a></div>
+<h2><a name="adjustments">Adjusting Existing Variables for Mutation</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
The symbol table in Kaleidoscope is managed at code generation time by the
<b>// Reload, increment, and restore the alloca. This handles the case where
// the body of the loop mutates the variable.
Value *CurVar = Builder.CreateLoad(Alloca);
- Value *NextVar = Builder.CreateAdd(CurVar, StepVal, "nextvar");
+ Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
Builder.CreateStore(NextVar, Alloca);</b>
...
</pre>
<pre>
define double @fib(double %x) {
entry:
- <b>%x1 = alloca double
- store double %x, double* %x1
- %x2 = load double* %x1</b>
- %cmptmp = fcmp ult double %x2, 3.000000e+00
- %booltmp = uitofp i1 %cmptmp to double
- %ifcond = fcmp one double %booltmp, 0.000000e+00
- br i1 %ifcond, label %then, label %else
+ <b>%x1 = alloca double
+ store double %x, double* %x1
+ %x2 = load double* %x1</b>
+ %cmptmp = fcmp ult double %x2, 3.000000e+00
+ %booltmp = uitofp i1 %cmptmp to double
+ %ifcond = fcmp one double %booltmp, 0.000000e+00
+ br i1 %ifcond, label %then, label %else
then: ; preds = %entry
- br label %ifcont
+ br label %ifcont
else: ; preds = %entry
- <b>%x3 = load double* %x1</b>
- %subtmp = sub double %x3, 1.000000e+00
- %calltmp = call double @fib( double %subtmp )
- <b>%x4 = load double* %x1</b>
- %subtmp5 = sub double %x4, 2.000000e+00
- %calltmp6 = call double @fib( double %subtmp5 )
- %addtmp = add double %calltmp, %calltmp6
- br label %ifcont
+ <b>%x3 = load double* %x1</b>
+ %subtmp = fsub double %x3, 1.000000e+00
+ %calltmp = call double @fib(double %subtmp)
+ <b>%x4 = load double* %x1</b>
+ %subtmp5 = fsub double %x4, 2.000000e+00
+ %calltmp6 = call double @fib(double %subtmp5)
+ %addtmp = fadd double %calltmp, %calltmp6
+ br label %ifcont
ifcont: ; preds = %else, %then
- %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
- ret double %iftmp
+ %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
+ ret double %iftmp
}
</pre>
</div>
<pre>
define double @fib(double %x) {
entry:
- %cmptmp = fcmp ult double <b>%x</b>, 3.000000e+00
- %booltmp = uitofp i1 %cmptmp to double
- %ifcond = fcmp one double %booltmp, 0.000000e+00
- br i1 %ifcond, label %then, label %else
+ %cmptmp = fcmp ult double <b>%x</b>, 3.000000e+00
+ %booltmp = uitofp i1 %cmptmp to double
+ %ifcond = fcmp one double %booltmp, 0.000000e+00
+ br i1 %ifcond, label %then, label %else
then:
- br label %ifcont
+ br label %ifcont
else:
- %subtmp = sub double <b>%x</b>, 1.000000e+00
- %calltmp = call double @fib( double %subtmp )
- %subtmp5 = sub double <b>%x</b>, 2.000000e+00
- %calltmp6 = call double @fib( double %subtmp5 )
- %addtmp = add double %calltmp, %calltmp6
- br label %ifcont
+ %subtmp = fsub double <b>%x</b>, 1.000000e+00
+ %calltmp = call double @fib(double %subtmp)
+ %subtmp5 = fsub double <b>%x</b>, 2.000000e+00
+ %calltmp6 = call double @fib(double %subtmp5)
+ %addtmp = fadd double %calltmp, %calltmp6
+ br label %ifcont
ifcont: ; preds = %else, %then
- %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
- ret double %iftmp
+ %iftmp = phi double [ 1.000000e+00, %then ], [ %addtmp, %else ]
+ ret double %iftmp
}
</pre>
</div>
<pre>
define double @fib(double %x) {
entry:
- %cmptmp = fcmp ult double %x, 3.000000e+00
- %booltmp = uitofp i1 %cmptmp to double
- %ifcond = fcmp ueq double %booltmp, 0.000000e+00
- br i1 %ifcond, label %else, label %ifcont
+ %cmptmp = fcmp ult double %x, 3.000000e+00
+ %booltmp = uitofp i1 %cmptmp to double
+ %ifcond = fcmp ueq double %booltmp, 0.000000e+00
+ br i1 %ifcond, label %else, label %ifcont
else:
- %subtmp = sub double %x, 1.000000e+00
- %calltmp = call double @fib( double %subtmp )
- %subtmp5 = sub double %x, 2.000000e+00
- %calltmp6 = call double @fib( double %subtmp5 )
- %addtmp = add double %calltmp, %calltmp6
- ret double %addtmp
+ %subtmp = fsub double %x, 1.000000e+00
+ %calltmp = call double @fib(double %subtmp)
+ %subtmp5 = fsub double %x, 2.000000e+00
+ %calltmp6 = call double @fib(double %subtmp5)
+ %addtmp = fadd double %calltmp, %calltmp6
+ ret double %addtmp
ifcont:
- ret double 1.000000e+00
+ ret double 1.000000e+00
}
</pre>
</div>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="assignment">New Assignment Operator</a></div>
+<h2><a name="assignment">New Assignment Operator</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>With our current framework, adding a new assignment operator is really
simple. We will parse it just like any other binary operator, but handle it
</div>
<!-- *********************************************************************** -->
-<div class="doc_section"><a name="localvars">User-defined Local
-Variables</a></div>
+<h2><a name="localvars">User-defined Local Variables</a></h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>Adding var/in is just like any other other extensions we made to
Kaleidoscope: we extend the lexer, the parser, the AST and the code generator.
</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 mutable
<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>
<pre>
#include "llvm/DerivedTypes.h"
#include "llvm/ExecutionEngine/ExecutionEngine.h"
-#include "llvm/ExecutionEngine/Interpreter.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/Transforms/Scalar.h"
-#include "llvm/Support/IRBuilder.h"
+#include "llvm/Support/TargetSelect.h"
#include <cstdio>
#include <string>
#include <map>
if (L == 0 || R == 0) return 0;
switch (Op) {
- case '+': return Builder.CreateAdd(L, R, "addtmp");
- case '-': return Builder.CreateSub(L, R, "subtmp");
- case '*': return Builder.CreateMul(L, R, "multmp");
+ case '+': return Builder.CreateFAdd(L, R, "addtmp");
+ case '-': return Builder.CreateFSub(L, R, "subtmp");
+ case '*': return Builder.CreateFMul(L, R, "multmp");
case '<':
L = Builder.CreateFCmpULT(L, R, "cmptmp");
// Convert bool 0/1 to double 0.0 or 1.0
Function *F = TheModule->getFunction(std::string("binary")+Op);
assert(F && "binary operator not found!");
- Value *Ops[] = { L, R };
- return Builder.CreateCall(F, Ops, Ops+2, "binop");
+ Value *Ops[2] = { L, R };
+ return Builder.CreateCall(F, Ops, "binop");
}
Value *CallExprAST::Codegen() {
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);
// Reload, increment, and restore the alloca. This handles the case where
// the body of the loop mutates the variable.
Value *CurVar = Builder.CreateLoad(Alloca, VarName.c_str());
- Value *NextVar = Builder.CreateAdd(CurVar, StepVal, "nextvar");
+ Value *NextVar = Builder.CreateFAdd(CurVar, StepVal, "nextvar");
Builder.CreateStore(NextVar, Alloca);
// Convert condition to a bool by comparing equal to 0.0.
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);
TheModule = new Module("my cool jit", Context);
// Create the JIT. This takes ownership of the module.
- TheExecutionEngine = EngineBuilder(TheModule).create();
+ std::string ErrStr;
+ TheExecutionEngine = EngineBuilder(TheModule).setErrorStr(&ErrStr).create();
+ if (!TheExecutionEngine) {
+ fprintf(stderr, "Could not create ExecutionEngine: %s\n", ErrStr.c_str());
+ exit(1);
+ }
FunctionPassManager OurFPM(TheModule);
// Set up the optimizer pipeline. Start with registering info about how the
// target lays out data structures.
OurFPM.add(new TargetData(*TheExecutionEngine->getTargetData()));
+ // Provide basic AliasAnalysis support for GVN.
+ OurFPM.add(createBasicAliasAnalysisPass());
// Promote allocas to registers.
OurFPM.add(createPromoteMemoryToRegisterPass());
// 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