docs/tutorial/JITTutorial2.html

   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 <!-- *********************************************************************** -->
  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>
  32 unsigned gcd(unsigned x, unsigned y) {
  33   if(x == y) {
  34     return x;
  35   } else if(x &lt; y) {
  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
  46 <div style="text-align: center;"><img src="JITTutorial2-1.png" alt="GCD CFG" width="60%"></div>
  47
  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>
  49
  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>
  51
  52 <div class="doc_code">
  53 <pre>
  54 #include &lt;llvm/Module.h&gt;
  55 #include &lt;llvm/Function.h&gt;
  56 #include &lt;llvm/PassManager.h&gt;
  57 #include &lt;llvm/Analysis/Verifier.h&gt;
  58 #include &lt;llvm/Assembly/PrintModulePass.h&gt;
  59 #include &lt;llvm/Support/IRBuilder.h&gt;
  60
  61 using namespace llvm;
  62
  63 Module* makeLLVMModule();
  64
  65 int main(int argc, char**argv) {
  66   Module* Mod = makeLLVMModule();
  67
  68   verifyModule(*Mod, PrintMessageAction);
  69
  70   PassManager PM;
  71   PM.add(new PrintModulePass(&amp;llvm::cout));
  72   PM.run(*Mod);
  73
  74   delete Mod;
  75   return 0;
  76 }
  77
  78 Module* makeLLVMModule() {
  79   Module* mod = new Module(&quot;tut2&quot;);
  80
  81   Constant* c = mod-&gt;getOrInsertFunction(&quot;gcd&quot;,
  82                                          IntegerType::get(32),
  83                                          IntegerType::get(32),
  84                                          IntegerType::get(32),
  85                                          NULL);
  86   Function* gcd = cast&lt;Function&gt;(c);
  87
  88   Function::arg_iterator args = gcd-&gt;arg_begin();
  89   Value* x = args++;
  90   x-&gt;setName(&quot;x&quot;);
  91   Value* y = args++;
  92   y-&gt;setName(&quot;y&quot;);
  93 </pre>
  94 </div>
  95
  96 <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>
  97
  98 <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>
  99
 100 <div class="doc_code">
 101 <pre>
 102   BasicBlock* entry = BasicBlock::Create(&quot;entry&quot;, gcd);
 103   BasicBlock* ret = BasicBlock::Create(&quot;return&quot;, gcd);
 104   BasicBlock* cond_false = BasicBlock::Create(&quot;cond_false&quot;, gcd);
 105   BasicBlock* cond_true = BasicBlock::Create(&quot;cond_true&quot;, gcd);
 106   BasicBlock* cond_false_2 = BasicBlock::Create(&quot;cond_false&quot;, gcd);
 107 </pre>
 108 </div>
 109
 110 <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>
 111
 112 <div class="doc_code">
 113 <pre>
 114   IRBuilder builder(entry);
 115   Value* xEqualsY = builder.CreateICmpEQ(x, y, &quot;tmp&quot;);
 116   builder.CreateCondBr(xEqualsY, ret, cond_false);
 117 </pre>
 118 </div>
 119
 120 <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>
 121
 122 <div class="doc_code">
 123 <pre>
 124   builder.SetInsertPoint(ret);
 125   builder.CreateRet(x);
 126 </pre>
 127 </div>
 128
 129 <p><code>cond_false</code> is a more interesting block: we now know that <code>x
 130 != y</code>, so we must branch again to determine which of <code>x</code>
 131 and <code>y</code> is larger.  This is achieved using the <code>ICmpULT</code>
 132 instruction, which stands for <em>integer comparison for unsigned
 133 less-than</em>.  In LLVM, integer types do not carry sign; a 32-bit integer
 134 pseudo-register can be interpreted as signed or unsigned without casting.
 135 Whether a signed or unsigned interpretation is desired is specified in the
 136 instruction.  This is why several instructions in the LLVM IR, such as integer
 137 less-than, include a specifier for signed or unsigned.</p>
 138
 139 <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>
 140
 141 <div class="doc_code">
 142 <pre>
 143   builder.SetInsertPoint(cond_false);
 144   Value* xLessThanY = builder.CreateICmpULT(x, y, &quot;tmp&quot;);
 145   builder.CreateCondBr(xLessThanY, cond_true, cond_false_2);
 146 </pre>
 147 </div>
 148
 149 <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>
 150
 151 <div class="doc_code">
 152 <pre>
 153   builder.SetInsertPoint(cond_true);
 154   Value* yMinusX = builder.CreateSub(y, x, &quot;tmp&quot;);
 155   std::vector&lt;Value*&gt; args1;
 156   args1.push_back(x);
 157   args1.push_back(yMinusX);
 158   Value* recur_1 = builder.CreateCall(gcd, args1.begin(), args1.end(), &quot;tmp&quot;);
 159   builder.CreateRet(recur_1);
 160
 161   builder.SetInsertPoint(cond_false_2);
 162   Value* xMinusY = builder.CreateSub(x, y, &quot;tmp&quot;);
 163   std::vector&lt;Value*&gt; args2;
 164   args2.push_back(xMinusY);
 165   args2.push_back(y);
 166   Value* recur_2 = builder.CreateCall(gcd, args2.begin(), args2.end(), &quot;tmp&quot;);
 167   builder.CreateRet(recur_2);
 168
 169   return mod;
 170 }
 171 </pre>
 172 </div>
 173
 174 <p>And that's it!  You can compile and execute your code in the same way as before, by doing:</p>
 175
 176 <div class="doc_code">
 177 <pre>
 178 # c++ -g tut2.cpp `llvm-config --cxxflags --ldflags --libs core` -o tut2
 179 # ./tut2
 180 </pre>
 181 </div>
 182
 183 </div>
 184
 185 <!-- *********************************************************************** -->
 186 <hr>
 187 <address>
 188   <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
 189   src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
 190   <a href="http://validator.w3.org/check/referer"><img
 191   src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
 192
 193   <a href="mailto:owen@apple.com">Owen Anderson</a><br>
 194   <a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
 195   Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $
 196 </address>
 197
 198 </body>
 199 </html>