Gitiles
Code Review Sign In
gerrit-public.fairphone.software / toolchain / llvm-project / 993e527b301751a6ad151cfc1b4adff8ef5b6f7a / . / llvm / docs / tutorial / JITTutorial2.html
blob: 504d96597b00d45624b58a531d93ed7082f81f2c [file] [log] [blame]
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3
4<html>
5<head>
6 <title>LLVM Tutorial 2: A More Complicated Function</title>
7 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
8 <meta name="author" content="Owen Anderson">
9 <meta name="description"
10 content="LLVM Tutorial 2: A More Complicated Function.">
11 <link rel="stylesheet" href="../llvm.css" type="text/css">
12</head>
13
14<body>
15
16<div class="doc_title"> LLVM Tutorial 2: A More Complicated Function </div>
17
18<div class="doc_author">
19 <p>Written by <a href="mailto:owen@apple.com">Owen Anderson</a></p>
20</div>
21
22<!-- *********************************************************************** -->
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]23<div class="doc_section"><a name="intro">A First Function</a></div>
24<!-- *********************************************************************** -->
25
26<div class="doc_text">
27
28<p>Now that we understand the basics of creating functions in LLVM, let's move on to a more complicated example: something with control flow. As an example, let's consider Euclid's Greatest Common Denominator (GCD) algorithm:</p>
29
30<div class="doc_code">
31<pre>
32unsigned gcd(unsigned x, unsigned y) {
33 if(x == y) {
34 return x;
Chris Lattnera1ad2bf2008-02-10 19:11:04 +0000[diff] [blame]35 } else if(x &lt; y) {
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]36 return gcd(x, y - x);
37 } else {
38 return gcd(x - y, y);
39 }
40}
41</pre>
42</div>
43
44<p>With this example, we'll learn how to create functions with multiple blocks and control flow, and how to make function calls within your LLVM code. For starters, consider the diagram below.</p>
45
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]46<div style="text-align: center;"><img src="JITTutorial2-1.png" alt="GCD CFG" width="60%"></div>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]47
Chris Lattnera1ad2bf2008-02-10 19:11:04 +0000[diff] [blame]48<p>This is a graphical representation of a program in LLVM IR. It places each basic block on a node of a graph and uses directed edges to indicate flow control. These blocks will be serialized when written to a text or bitcode file, but it is often useful conceptually to think of them as a graph. Again, if you are unsure about the code in the diagram, you should skim through the <a href="../LangRef.html">LLVM Language Reference Manual</a> and convince yourself that it is, in fact, the GCD algorithm.</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]49
Owen Andersonc2802162007-11-19 16:10:59 +0000[diff] [blame]50<p>The first part of our code is practically the same as from the first tutorial. The same basic setup is required: creating a module, verifying it, and running the <code>PrintModulePass</code> on it. Even the first segment of <code>makeLLVMModule()</code> looks essentially the same, except that <code>gcd</code> takes one fewer parameter than <code>mul_add</code>.</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]51
52<div class="doc_code">
53<pre>
Gabor Greif42225e52009-03-11 20:23:40 +0000[diff] [blame]54#include "llvm/Module.h"
55#include "llvm/Function.h"
56#include "llvm/PassManager.h"
57#include "llvm/Analysis/Verifier.h"
58#include "llvm/Assembly/PrintModulePass.h"
59#include "llvm/Support/IRBuilder.h"
Bill Wendlingcb368e22009-05-12 18:29:42 +0000[diff] [blame]60#include "llvm/Support/raw_ostream.h"
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]61
62using namespace llvm;
63
64Module* makeLLVMModule();
65
66int main(int argc, char**argv) {
67 Module* Mod = makeLLVMModule();
68
69 verifyModule(*Mod, PrintMessageAction);
70
71 PassManager PM;
Bill Wendlingcb368e22009-05-12 18:29:42 +0000[diff] [blame]72 PM.add(createPrintModulePass(&amp;outs()));
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]73 PM.run(*Mod);
Bill Wendlingacbcce42008-05-19 00:20:45 +0000[diff] [blame]74
75 delete Mod;
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]76 return 0;
77}
78
79Module* makeLLVMModule() {
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]80 Module* mod = new Module(&quot;tut2&quot;);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]81
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]82 Constant* c = mod-&gt;getOrInsertFunction(&quot;gcd&quot;,
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]83 IntegerType::get(32),
84 IntegerType::get(32),
85 IntegerType::get(32),
86 NULL);
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]87 Function* gcd = cast&lt;Function&gt;(c);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]88
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]89 Function::arg_iterator args = gcd-&gt;arg_begin();
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]90 Value* x = args++;
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]91 x-&gt;setName(&quot;x&quot;);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]92 Value* y = args++;
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]93 y-&gt;setName(&quot;y&quot;);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]94</pre>
95</div>
96
97<p>Here, however, is where our code begins to diverge from the first tutorial. Because <code>gcd</code> has control flow, it is composed of multiple blocks interconnected by branching (<code>br</code>) instructions. For those familiar with assembly language, a block is similar to a labeled set of instructions. For those not familiar with assembly language, a block is basically a set of instructions that can be branched to and is executed linearly until the block is terminated by one of a small number of control flow instructions, such as <code>br</code> or <code>ret</code>.</p>
98
Chris Lattnera1ad2bf2008-02-10 19:11:04 +0000[diff] [blame]99<p>Blocks correspond to the nodes in the diagram we looked at in the beginning of this tutorial. From the diagram, we can see that this function contains five blocks, so we'll go ahead and create them. Note that we're making use of LLVM's automatic name uniquing in this code sample, since we're giving two blocks the same name.</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]100
101<div class="doc_code">
102<pre>
Owen Anderson55f1c092009-08-13 21:58:54 +0000[diff] [blame]103 BasicBlock* entry = BasicBlock::Create(getGlobalContext(), (&quot;entry&quot;, gcd);
104 BasicBlock* ret = BasicBlock::Create(getGlobalContext(), (&quot;return&quot;, gcd);
105 BasicBlock* cond_false = BasicBlock::Create(getGlobalContext(), (&quot;cond_false&quot;, gcd);
106 BasicBlock* cond_true = BasicBlock::Create(getGlobalContext(), (&quot;cond_true&quot;, gcd);
107 BasicBlock* cond_false_2 = BasicBlock::Create(getGlobalContext(), (&quot;cond_false&quot;, gcd);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]108</pre>
109</div>
110
Chris Lattnera1ad2bf2008-02-10 19:11:04 +0000[diff] [blame]111<p>Now we're ready to begin generating code! We'll start with the <code>entry</code> block. This block corresponds to the top-level if-statement in the original C code, so we need to compare <code>x</code> and <code>y</code>. To achieve this, we perform an explicit comparison using <code>ICmpEQ</code>. <code>ICmpEQ</code> stands for an <em>integer comparison for equality</em> and returns a 1-bit integer result. This 1-bit result is then used as the input to a conditional branch, with <code>ret</code> as the <code>true</code> and <code>cond_false</code> as the <code>false</code> case.</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]112
113<div class="doc_code">
114<pre>
Gabor Greifbfdf23f2009-03-11 19:51:07 +0000[diff] [blame]115 IRBuilder&lt;&gt; builder(entry);
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]116 Value* xEqualsY = builder.CreateICmpEQ(x, y, &quot;tmp&quot;);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]117 builder.CreateCondBr(xEqualsY, ret, cond_false);
118</pre>
119</div>
120
Duncan Sandsa07136e2008-04-13 06:22:09 +0000[diff] [blame]121<p>Our next block, <code>ret</code>, is pretty simple: it just returns the value of <code>x</code>. Recall that this block is only reached if <code>x == y</code>, so this is the correct behavior. Notice that instead of creating a new <code>IRBuilder</code> for each block, we can use <code>SetInsertPoint</code> to retarget our existing one. This saves on construction and memory allocation costs.</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]122
123<div class="doc_code">
124<pre>
125 builder.SetInsertPoint(ret);
126 builder.CreateRet(x);
127</pre>
128</div>
129
Bill Wendlingd01e2632008-05-19 00:25:01 +0000[diff] [blame]130<p><code>cond_false</code> is a more interesting block: we now know that <code>x
131!= y</code>, so we must branch again to determine which of <code>x</code>
132and <code>y</code> is larger. This is achieved using the <code>ICmpULT</code>
133instruction, which stands for <em>integer comparison for unsigned
134less-than</em>. In LLVM, integer types do not carry sign; a 32-bit integer
135pseudo-register can be interpreted as signed or unsigned without casting.
136Whether a signed or unsigned interpretation is desired is specified in the
137instruction. This is why several instructions in the LLVM IR, such as integer
138less-than, include a specifier for signed or unsigned.</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]139
Chris Lattnera1ad2bf2008-02-10 19:11:04 +0000[diff] [blame]140<p>Also note that we're again making use of LLVM's automatic name uniquing, this time at a register level. We've deliberately chosen to name every instruction "tmp" to illustrate that LLVM will give them all unique names without getting confused.</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]141
142<div class="doc_code">
143<pre>
144 builder.SetInsertPoint(cond_false);
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]145 Value* xLessThanY = builder.CreateICmpULT(x, y, &quot;tmp&quot;);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]146 builder.CreateCondBr(xLessThanY, cond_true, cond_false_2);
147</pre>
148</div>
149
150<p>Our last two blocks are quite similar; they're both recursive calls to <code>gcd</code> with different parameters. To create a call instruction, we have to create a <code>vector</code> (or any other container with <code>InputInterator</code>s) to hold the arguments. We then pass in the beginning and ending iterators for this vector.</p>
151
152<div class="doc_code">
153<pre>
154 builder.SetInsertPoint(cond_true);
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]155 Value* yMinusX = builder.CreateSub(y, x, &quot;tmp&quot;);
156 std::vector&lt;Value*&gt; args1;
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]157 args1.push_back(x);
158 args1.push_back(yMinusX);
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]159 Value* recur_1 = builder.CreateCall(gcd, args1.begin(), args1.end(), &quot;tmp&quot;);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]160 builder.CreateRet(recur_1);
161
162 builder.SetInsertPoint(cond_false_2);
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]163 Value* xMinusY = builder.CreateSub(x, y, &quot;tmp&quot;);
164 std::vector&lt;Value*&gt; args2;
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]165 args2.push_back(xMinusY);
166 args2.push_back(y);
Owen Andersonb5d89042007-10-23 06:22:21 +0000[diff] [blame]167 Value* recur_2 = builder.CreateCall(gcd, args2.begin(), args2.end(), &quot;tmp&quot;);
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]168 builder.CreateRet(recur_2);
169
170 return mod;
171}
172</pre>
173</div>
174
Duncan Sandsf8bc4062007-11-05 15:15:50 +0000[diff] [blame]175<p>And that's it! You can compile and execute your code in the same way as before, by doing:</p>
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]176
177<div class="doc_code">
178<pre>
Owen Andersonce268212008-03-24 21:38:01 +0000[diff] [blame]179# c++ -g tut2.cpp `llvm-config --cxxflags --ldflags --libs core` -o tut2
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]180# ./tut2
181</pre>
182</div>
183
184</div>
185
Owen Andersonaf8059c2007-10-25 06:45:01 +0000[diff] [blame]186<!-- *********************************************************************** -->
187<hr>
188<address>
189 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
190 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
191 <a href="http://validator.w3.org/check/referer"><img
192 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
193
194 <a href="mailto:owen@apple.com">Owen Anderson</a><br>
195 <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
196 Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
197</address>
198
Owen Anderson299be452007-10-23 06:03:24 +0000[diff] [blame]199</body>
Duncan Sandsf8bc4062007-11-05 15:15:50 +0000[diff] [blame]200</html>