diff options
Diffstat (limited to 'miniany/doc/Writing a C Compiler, Part 4.html')
| -rw-r--r-- | miniany/doc/Writing a C Compiler, Part 4.html | 449 |
1 files changed, 449 insertions, 0 deletions
diff --git a/miniany/doc/Writing a C Compiler, Part 4.html b/miniany/doc/Writing a C Compiler, Part 4.html new file mode 100644 index 0000000..25effd8 --- /dev/null +++ b/miniany/doc/Writing a C Compiler, Part 4.html @@ -0,0 +1,449 @@ +<!DOCTYPE html> +<!-- saved from url=(0058)https://norasandler.com/2017/12/28/Write-a-Compiler-4.html --> +<html lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> + + <meta http-equiv="X-UA-Compatible" content="IE=edge"> + <meta name="viewport" content="width=device-width, initial-scale=1"> + + <title>Writing a C Compiler, Part 4</title> + <meta name="description" content="This is the fourth post in a series. Read part 1 here."> + + <link rel="stylesheet" href="./Writing a C Compiler, Part 4_files/main.css"> + <link rel="canonical" href="https://norasandler.com/2017/12/28/Write-a-Compiler-4.html"> + <link rel="alternate" type="application/rss+xml" title="Nora Sandler" href="https://norasandler.com/feed.xml"> + +</head> + + + <body> + + <header class="site-header" role="banner"> + + <div class="wrapper"> + + + <a class="site-title" href="https://norasandler.com/">Nora Sandler</a> + + + <nav class="site-nav"> + <input type="checkbox" id="nav-trigger" class="nav-trigger"> + <label for="nav-trigger"> + <span class="menu-icon"> + <svg viewBox="0 0 18 15" width="18px" height="15px"> + <path fill="#424242" d="M18,1.484c0,0.82-0.665,1.484-1.484,1.484H1.484C0.665,2.969,0,2.304,0,1.484l0,0C0,0.665,0.665,0,1.484,0 h15.031C17.335,0,18,0.665,18,1.484L18,1.484z"></path> + <path fill="#424242" d="M18,7.516C18,8.335,17.335,9,16.516,9H1.484C0.665,9,0,8.335,0,7.516l0,0c0-0.82,0.665-1.484,1.484-1.484 h15.031C17.335,6.031,18,6.696,18,7.516L18,7.516z"></path> + <path fill="#424242" d="M18,13.516C18,14.335,17.335,15,16.516,15H1.484C0.665,15,0,14.335,0,13.516l0,0 c0-0.82,0.665-1.484,1.484-1.484h15.031C17.335,12.031,18,12.696,18,13.516L18,13.516z"></path> + </svg> + </span> + </label> + + <div class="trigger"> + + + + + + + + + + <a class="page-link" href="https://norasandler.com/about/">About</a> + + + + + + + <a class="page-link" href="https://norasandler.com/archive/">Archive</a> + + + + + + + + + + + + + + + + + + + + + + <a class="page-link" href="https://github.com/nlsandler">Github</a> + <a href="https://norasandler.com/feed.xml"><img id="rss" height="20" width="20" src="./Writing a C Compiler, Part 4_files/rss.png"></a> + + </div> + </nav> + + </div> +</header> + + + <main class="page-content" aria-label="Content"> + <div class="wrapper"> + <article class="post h-entry" itemscope="" itemtype="http://schema.org/BlogPosting"> + + <header class="post-header"> + <h1 class="post-title p-name" itemprop="name headline">Writing a C Compiler, Part 4</h1> + <p class="post-meta"> + <time class="dt-published" datetime="2017-12-28T23:30:00+00:00" itemprop="datePublished">Dec 28, 2017 + </time></p> + </header> + + <div class="post-content e-content" itemprop="articleBody"> + <p><em>This is the fourth post in a series. Read part 1 <a href="https://norasandler.com/2017/11/29/Write-a-Compiler.html">here</a>.</em></p> + +<p>This week we’re adding some boolean operators (<code class="language-plaintext highlighter-rouge">&&</code>, <code class="language-plaintext highlighter-rouge">||</code>) and a whole bunch of relational operators (<code class="language-plaintext highlighter-rouge"><</code>, <code class="language-plaintext highlighter-rouge">==</code>, etc.). Since we already know how to handle binary operators, this week will be pretty straightforward. As always, you can find the accompanying tests <a href="https://github.com/nlsandler/write_a_c_compiler">here</a>.</p> + +<p>The test suite is slightly weird this week; the three tests whose names start with <code class="language-plaintext highlighter-rouge">skip_on_failure_</code> use local variables, which we haven’t implemented yet. I’ve included them because otherwise the test suite can’t validate that short-circuiting works correctly. When you run the test suite, they should show up as <code class="language-plaintext highlighter-rouge">NOT_IMPLEMENTED</code> rather than <code class="language-plaintext highlighter-rouge">FAIL</code> in the results, and they shouldn’t count toward the total number of failures. Once you’ve implemented local variables, these tests should pass.</p> + +<h1 id="week-4-even-more-binary-operators">Week 4: Even More Binary Operators</h1> + +<p>We’re adding eight new operators this week:</p> + +<ul> + <li>Logical AND <code class="language-plaintext highlighter-rouge">&&</code></li> + <li>Logical OR <code class="language-plaintext highlighter-rouge">||</code></li> + <li>Equal to <code class="language-plaintext highlighter-rouge">==</code></li> + <li>Not equal to <code class="language-plaintext highlighter-rouge">!=</code></li> + <li>Less than <code class="language-plaintext highlighter-rouge"><</code></li> + <li>Less than or equal to <code class="language-plaintext highlighter-rouge"><=</code></li> + <li>Greater than <code class="language-plaintext highlighter-rouge">></code></li> + <li>Greater than or equal to <code class="language-plaintext highlighter-rouge">>=</code></li> +</ul> + +<p>As usual, we’ll update our lexing, parsing, and code generation passes to support these operations.</p> + +<h2 id="lexing">Lexing</h2> + +<p>Each new operator corresponds to a new token. Here’s the full list of tokens we need to support, with old tokens at the top and new tokens in bold at the bottom:</p> + +<ul> + <li>Open brace <code class="language-plaintext highlighter-rouge">{</code></li> + <li>Close brace <code class="language-plaintext highlighter-rouge">}</code></li> + <li>Open parenthesis <code class="language-plaintext highlighter-rouge">(</code></li> + <li>Close parenthesis <code class="language-plaintext highlighter-rouge">)</code></li> + <li>Semicolon <code class="language-plaintext highlighter-rouge">;</code></li> + <li>Int keyword <code class="language-plaintext highlighter-rouge">int</code></li> + <li>Return keyword <code class="language-plaintext highlighter-rouge">return</code></li> + <li>Identifier <code class="language-plaintext highlighter-rouge">[a-zA-Z]\w*</code></li> + <li>Integer literal <code class="language-plaintext highlighter-rouge">[0-9]+</code></li> + <li>Minus <code class="language-plaintext highlighter-rouge">-</code></li> + <li>Bitwise complement <code class="language-plaintext highlighter-rouge">~</code></li> + <li>Logical negation <code class="language-plaintext highlighter-rouge">!</code></li> + <li>Addition <code class="language-plaintext highlighter-rouge">+</code></li> + <li>Multiplication <code class="language-plaintext highlighter-rouge">*</code></li> + <li>Division <code class="language-plaintext highlighter-rouge">/</code></li> + <li><strong>AND <code class="language-plaintext highlighter-rouge">&&</code></strong></li> + <li><strong>OR <code class="language-plaintext highlighter-rouge">||</code></strong></li> + <li><strong>Equal <code class="language-plaintext highlighter-rouge">==</code></strong></li> + <li><strong>Not Equal <code class="language-plaintext highlighter-rouge">!=</code></strong></li> + <li><strong>Less than <code class="language-plaintext highlighter-rouge"><</code></strong></li> + <li><strong>Less than or equal <code class="language-plaintext highlighter-rouge"><=</code></strong></li> + <li><strong>Greater than <code class="language-plaintext highlighter-rouge">></code></strong></li> + <li><strong>Greater than or equal <code class="language-plaintext highlighter-rouge">>=</code></strong></li> +</ul> + +<h4 id="-task">☑ Task:</h4> +<p>Update the <em>lex</em> function to handle the new tokens. It should work for all valid and invalid stage 1-4 examples in the test suite, except the <code class="language-plaintext highlighter-rouge">skip_on_failure_</code> ones.</p> + +<h2 id="parsing">Parsing</h2> + +<p>Last week, we found that we needed one production rule in our grammar for each operator precedence level. This week we have a lot more precedence levels, which means our grammar will grow a lot. However, our parsing strategy hasn’t changed at all; we’ll handle our new production rules exactly the same way as the old rules for <code class="language-plaintext highlighter-rouge">exp</code> and <code class="language-plaintext highlighter-rouge">term</code>. Honestly, this is going to be pretty tedious, but I hope it will help solidify all the stuff about parsing from last week.</p> + +<p>Here are our all binary operators, from highest to lowest precedence<sup id="anchor1"><a href="https://norasandler.com/2017/12/28/Write-a-Compiler-4.html#fn1">1</a></sup>:</p> + +<ul> + <li>Multiplication & division (<code class="language-plaintext highlighter-rouge">*</code>, <code class="language-plaintext highlighter-rouge">/</code>)</li> + <li>Addition & subtraction (<code class="language-plaintext highlighter-rouge">+</code>,<code class="language-plaintext highlighter-rouge">-</code>)</li> + <li>Relational less than/greater than/less than or equal/greater than or equal (<code class="language-plaintext highlighter-rouge"><</code>, <code class="language-plaintext highlighter-rouge">></code>,<code class="language-plaintext highlighter-rouge"><=</code>,<code class="language-plaintext highlighter-rouge">>=</code>)</li> + <li>Relational equal/not equal (<code class="language-plaintext highlighter-rouge">==</code>, <code class="language-plaintext highlighter-rouge">!=</code>)</li> + <li>Logical AND (<code class="language-plaintext highlighter-rouge">&&</code>)</li> + <li>Logical OR (<code class="language-plaintext highlighter-rouge">||</code>)</li> +</ul> + +<p>We handled the first two bullet points last week; the last four are new. We’ll add a production rule for each of the last four bullet points. The new grammar is below, with changed/added rules bolded.</p> + +<pre><program> ::= <function> +<function> ::= "int" <id> "(" ")" "{" <statement> "}" +<statement> ::= "return" <exp> ";" +<b><exp> ::= <logical-and-exp> { "||" <logical-and-exp> }</b> +<b><logical-and-exp> ::= <equality-exp> { "&&" <equality-exp> }</b> +<b><equality-exp> ::= <relational-exp> { ("!=" | "==") <relational-exp> }</b> +<b><relational-exp> ::= <additive-exp> { ("<" | ">" | "<=" | ">=") <additive-exp> }</b> +<b><additive-exp> ::= <term> { ("+" | "-") <term> }</b> +<term> ::= <factor> { ("*" | "/") <factor> } +<factor> ::= "(" <exp> ")" | <unary_op> <factor> | <int> +<unary_op> ::= "!" | "~" | "-" +</pre> + +<p><code class="language-plaintext highlighter-rouge"><additive-exp></code> is the same as <code class="language-plaintext highlighter-rouge"><exp></code> from last week. We had to rename it because <code class="language-plaintext highlighter-rouge"><exp></code> now refers to logical OR expressions, which now have lowest precedence.</p> + +<p>Last week you wrote <code class="language-plaintext highlighter-rouge">parse_exp</code> and <code class="language-plaintext highlighter-rouge">parse_term</code>; now you’ll need <code class="language-plaintext highlighter-rouge">parse_relational_exp</code>, <code class="language-plaintext highlighter-rouge">parse_equality_exp</code>, etc. Other than handling different operators, these functions will all be identical.</p> + +<p>And for the sake of completeness, here’s our AST definition:</p> + +<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>program = Program(function_declaration) +function_declaration = Function(string, statement) //string is the function name +statement = Return(exp) +exp = BinOp(binary_operator, exp, exp) + | UnOp(unary_operator, exp) + | Constant(int) +</code></pre></div></div> + +<p>This is identical to last week, except we’ve added more possible values of <code class="language-plaintext highlighter-rouge">binary_operator</code>.</p> + +<h4 id="-task-1">☑ Task:</h4> +<p>Update your expression-parsing code to handle this week’s new binary operators. It should successfully parse all valid stage 1-4 examples in the test suite (except the <code class="language-plaintext highlighter-rouge">skip_on_failure</code> ones), and fail on all invalid stage 1-4 examples. The test suite doesn’t directly verify that your program generates the correct AST, so you’ll need to manually inspect the AST for each example to make sure it’s right.</p> + +<h2 id="code-generation">Code Generation</h2> + +<p>Our general approach to code generation for binary operations is the same as last week:</p> + +<ol> + <li>Calculate <code class="language-plaintext highlighter-rouge">e1</code></li> + <li>Push it onto the stack</li> + <li>Calculate <code class="language-plaintext highlighter-rouge">e2</code></li> + <li>Pop <code class="language-plaintext highlighter-rouge">e1</code> from the stack back into a register</li> + <li>Perform the operation on <code class="language-plaintext highlighter-rouge">e1</code> and <code class="language-plaintext highlighter-rouge">e2</code>.</li> +</ol> + +<p>All the new stuff will be in step 5.</p> + +<h3 id="relational-operators">Relational Operators</h3> + +<p>Let’s handle the relational operators first. Like the logical NOT operator (<code class="language-plaintext highlighter-rouge">!</code>) in week 2, these return 1 for true results and 0 for false results. These operators are almost identical to <code class="language-plaintext highlighter-rouge">!</code> except that they compare two expressions to each other, instead of comparing an expression to zero.</p> + +<p>Here’s the assembly we generated for <code class="language-plaintext highlighter-rouge">!</code> in week 2:</p> + +<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="err"><</span><span class="nf">CODE</span> <span class="nv">FOR</span> <span class="nv">exp</span> <span class="nv">GOES</span> <span class="nv">HERE</span><span class="o">></span> + <span class="nf">cmpl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">;set ZF on if exp == 0, set it off otherwise</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">;zero out EAX (doesn't change FLAGS)</span> + <span class="nf">sete</span> <span class="o">%</span><span class="nb">al</span> <span class="c1">;set AL register (the lower byte of EAX) to 1 iff ZF is 1</span> +</code></pre></div></div> + +<p>We can modify this slightly to implement <code class="language-plaintext highlighter-rouge">==</code>:</p> + +<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="err"><</span><span class="nf">CODE</span> <span class="nv">FOR</span> <span class="nv">e1</span> <span class="nv">GOES</span> <span class="nv">HERE</span><span class="o">></span> + <span class="nf">push</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; save value of e1 on the stack</span> + <span class="err"><</span><span class="nf">CODE</span> <span class="nv">FOR</span> <span class="nv">e2</span> <span class="nv">GOES</span> <span class="nv">HERE</span><span class="o">></span> + <span class="nf">pop</span> <span class="o">%</span><span class="nb">ecx</span> <span class="c1">; pop e1 from the stack into ecx - e2 is already in eax</span> + <span class="nf">cmpl</span> <span class="o">%</span><span class="nb">eax</span><span class="p">,</span> <span class="o">%</span><span class="nb">ecx</span> <span class="c1">;set ZF on if e1 == e2, set it off otherwise</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">;zero out EAX (doesn't change FLAGS)</span> + <span class="nf">sete</span> <span class="o">%</span><span class="nb">al</span> <span class="c1">;set AL register (the lower byte of EAX) to 1 iff ZF is on</span> +</code></pre></div></div> + +<p>The <code class="language-plaintext highlighter-rouge">sete</code> instruction is just one of a whole slew of conditional set instructions. There’s also <code class="language-plaintext highlighter-rouge">setne</code> (set if not equal), <code class="language-plaintext highlighter-rouge">setge</code> (set if greater than or equal), and so on. To implement <code class="language-plaintext highlighter-rouge"><</code>, <code class="language-plaintext highlighter-rouge">></code>, and the other relational operators, we can generate exactly the same assembly as we used for <code class="language-plaintext highlighter-rouge">==</code> above, just replacing <code class="language-plaintext highlighter-rouge">sete</code> with the appropriate conditional set instruction. Easy!</p> + +<p>In week 2, we talked about testing for equality with the zero flag (ZF). But we can’t use ZF to determine which operand is larger. For that, we need the sign flag (SF), which is set if the result of an operation is negative, like so:</p> + +<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nf">movl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">;zero out EAX</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">2</span><span class="p">,</span> <span class="o">%</span><span class="nb">ecx</span> <span class="c1">;ECX = 2</span> + <span class="nf">cmpl</span> <span class="kc">$</span><span class="mi">3</span><span class="p">,</span> <span class="o">%</span><span class="nb">ecx</span> <span class="c1">;compute 2 - 3, set flags</span> + <span class="nf">setl</span> <span class="o">%</span><span class="nb">al</span> <span class="c1">;set AL if 2 < 3, i.e. if 2 - 3 is negative</span> +</code></pre></div></div> + +<p>Now let’s talk about <code class="language-plaintext highlighter-rouge">&&</code> and <code class="language-plaintext highlighter-rouge">||</code>. I’ll use <code class="language-plaintext highlighter-rouge">&</code> and <code class="language-plaintext highlighter-rouge">|</code> to indicate bitwise AND and OR, respectively.</p> + +<h3 id="short-circuit-evaluation">Short-Circuit Evaluation</h3> + +<p>The C11 standard guarantees that evaluation of <code class="language-plaintext highlighter-rouge">&&</code> and <code class="language-plaintext highlighter-rouge">||</code> will short-circuit: if we know the result after evaluating the first clause, we don’t evaluate the second clause<sup id="anchor2"><a href="https://norasandler.com/2017/12/28/Write-a-Compiler-4.html#fn2">2</a></sup>. For example, consider the following line of code:</p> + +<div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="k">return</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">foo</span><span class="p">();</span> +</code></pre></div></div> + +<p>Because the first clause is false, we don’t need to know the return value of <code class="language-plaintext highlighter-rouge">foo</code>, so we won’t call <code class="language-plaintext highlighter-rouge">foo</code> at all. Whether <code class="language-plaintext highlighter-rouge">foo</code> is called won’t change the return value on this line, but it could perform I/O, update global variables, or have other important side effects. So making sure that <code class="language-plaintext highlighter-rouge">&&</code> and <code class="language-plaintext highlighter-rouge">||</code> short-circuit isn’t just a performance optimization; it’s required for some programs to execute correctly.</p> + +<h3 id="logical-or">Logical OR</h3> + +<p>To guarantee that logical OR short-circuits, we’ll need to jump over clause 2 when clause 1 is true. +We’ll follow these steps to calculate <code class="language-plaintext highlighter-rouge">e1 || e2</code>:</p> + +<ol> + <li>Calculate <code class="language-plaintext highlighter-rouge">e1</code></li> + <li>If the result is 0, jump to the step 4.</li> + <li>Set EAX to 1 and jump to the end.</li> + <li>Calculate <code class="language-plaintext highlighter-rouge">e2</code>.</li> + <li>If the result is 0, set EAX to 0. Otherwise set EAX to 1.</li> +</ol> + +<p>Step 2 will require a new type of instruction called <strong>conditional jumps</strong>. These are similar to the conditional set instructions, like <code class="language-plaintext highlighter-rouge">sete</code> and <code class="language-plaintext highlighter-rouge">setne</code>, that we’ve already used. The only difference is that instead of setting a byte to 1, they jump to a specific point in the assembly code, which we specify with a label. Here’s an example of <code class="language-plaintext highlighter-rouge">je</code>, the “jump if equal” instruction, in action:</p> + +<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nf">cmpl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; set ZF if EAX == 0</span> + <span class="nf">je</span> <span class="nv">_there</span> <span class="c1">; if ZF is set, go to _there</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">1</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> + <span class="nf">ret</span> +<span class="nl">_there:</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">2</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> + <span class="nf">ret</span> +</code></pre></div></div> + +<p>If EAX is 0 at the start of this code snippet, it will return 2; otherwise it will return 1. Let’s look at exactly what instructions will execute in each case.</p> + +<p>First consider the case where EAX is 0 at the start:</p> +<ol> + <li><code class="language-plaintext highlighter-rouge">cmpl $0, %eax</code> Because EAX is 0, this will set the zero flag (ZF) to true.</li> + <li><code class="language-plaintext highlighter-rouge">je _there</code> Because ZF is true, it <strong>will</strong> jump.</li> + <li><code class="language-plaintext highlighter-rouge">movl $2, %eax</code> This executes next because it’s the first instruction after <code class="language-plaintext highlighter-rouge">_there</code>. It sets EAX to 2.</li> + <li><code class="language-plaintext highlighter-rouge">ret</code> The return value will be 2.</li> +</ol> + +<p>Now consider the case where EAX isn’t zero:</p> +<ol> + <li><code class="language-plaintext highlighter-rouge">cmpl $0, %eax</code> Because EAX isn’t 0, this will set ZF to false.</li> + <li><code class="language-plaintext highlighter-rouge">je _there</code> Because ZF is false, it <strong>will not</strong> jump, so this instruction is a no-op.</li> + <li><code class="language-plaintext highlighter-rouge">movl $1, %eax</code> Since we didn’t jump, control passes to the next instruction as usual. It sets EAX to 1.</li> + <li><code class="language-plaintext highlighter-rouge">ret</code> The return value will be 1.</li> +</ol> + +<p>We’ll also need the <code class="language-plaintext highlighter-rouge">jmp</code> instruction, which performs an unconditional jump. Here’s an example of <code class="language-plaintext highlighter-rouge">jmp</code> in action:</p> + +<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nf">movl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; zero out EAX</span> + <span class="nf">jmp</span> <span class="nv">_there</span> <span class="c1">; go to _there label</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">5</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; this will never execute, we always jump over it</span> +<span class="nl">_there:</span> + <span class="nf">ret</span> <span class="c1">; will always return zero</span> +</code></pre></div></div> + +<p>Now that we’re familiar with <code class="language-plaintext highlighter-rouge">jmp</code> and <code class="language-plaintext highlighter-rouge">je</code>, here’s the assembly for <code class="language-plaintext highlighter-rouge">e1 || e2</code>:</p> + +<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="err"><</span><span class="nf">CODE</span> <span class="nv">FOR</span> <span class="nv">e1</span> <span class="nv">GOES</span> <span class="nv">HERE</span><span class="o">></span> + <span class="nf">cmpl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; check if e1 is true</span> + <span class="nf">je</span> <span class="nv">_clause2</span> <span class="c1">; e1 is 0, so we need to evaluate clause 2</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">1</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; we didn't jump, so e1 is true and therefore result is 1</span> + <span class="nf">jmp</span> <span class="nv">_end</span> +<span class="nl">_clause2:</span> + <span class="err"><</span><span class="nf">CODE</span> <span class="nv">FOR</span> <span class="nv">e2</span> <span class="nv">GOES</span> <span class="nv">HERE</span><span class="o">></span> + <span class="nf">cmpl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; check if e2 is true</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; zero out EAX without changing ZF</span> + <span class="nf">setne</span> <span class="o">%</span><span class="nb">al</span> <span class="c1">; set AL register (the low byte of EAX) to 1 iff e2 != 0</span> +<span class="nl">_end:</span> +</code></pre></div></div> + +<p>Note that labels have to be unique. This means you can’t actually use <code class="language-plaintext highlighter-rouge">_clause2</code> or <code class="language-plaintext highlighter-rouge">_end</code> as labels, because you’ll have duplicate labels if your program includes more than one logical OR. You should probably write a utility function to generate unique labels. It doesn’t have to be fancy; the label generator in <a href="https://github.com/nlsandler/nqcc/blob/master/src/util.ml">nqcc</a> just includes an incrementing counter in every label.</p> + +<p>The <code class="language-plaintext highlighter-rouge">_end</code> label here may look odd, since it doesn’t appear to label anything. Actually, it labels whatever comes right after this expression; it just gives us a target to jump over <code class="language-plaintext highlighter-rouge">_clause2</code>.</p> + +<h3 id="logical-and">Logical AND</h3> + +<p>Almost identical to logical OR, except we short-circuit if <code class="language-plaintext highlighter-rouge">e1</code> is 0. We use the <code class="language-plaintext highlighter-rouge">jne</code> (jump if not equal) instruction. In that case we don’t need to move anything into EAX, since 0 is the result we want. Here’s the assembly:</p> + +<div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="err"><</span><span class="nf">CODE</span> <span class="nv">FOR</span> <span class="nv">e1</span> <span class="nv">GOES</span> <span class="nv">HERE</span><span class="o">></span> + <span class="nf">cmpl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; check if e1 is true</span> + <span class="nf">jne</span> <span class="nv">_clause2</span> <span class="c1">; e1 isn't 0, so we need to evaluate clause 2</span> + <span class="nf">jmp</span> <span class="nv">_end</span> +<span class="nl">_clause2:</span> + <span class="err"><</span><span class="nf">CODE</span> <span class="nv">FOR</span> <span class="nv">e2</span> <span class="nv">GOES</span> <span class="nv">HERE</span><span class="o">></span> + <span class="nf">cmpl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; check if e2 is true</span> + <span class="nf">movl</span> <span class="kc">$</span><span class="mi">0</span><span class="p">,</span> <span class="o">%</span><span class="nb">eax</span> <span class="c1">; zero out EAX without changing ZF</span> + <span class="nf">setne</span> <span class="o">%</span><span class="nb">al</span> <span class="c1">; set AL register (the low byte of EAX) to 1 iff e2 != 0</span> +<span class="nl">_end:</span> +</code></pre></div></div> + +<p>As with logical OR, we need to make sure the labels are unique.</p> + +<h4 id="-task-2">☑ Task:</h4> +<p>Update your code-generation pass to emit correct code for <code class="language-plaintext highlighter-rouge">&&</code>, <code class="language-plaintext highlighter-rouge">||</code>, <code class="language-plaintext highlighter-rouge">==</code>, <code class="language-plaintext highlighter-rouge">!=</code>, <code class="language-plaintext highlighter-rouge"><</code>, <code class="language-plaintext highlighter-rouge"><=</code>, <code class="language-plaintext highlighter-rouge">></code>, and <code class="language-plaintext highlighter-rouge">>=</code>. It should succeed on all valid examples (except the <code class="language-plaintext highlighter-rouge">skip_on_failure_</code> ones) and fail on all invalid examples for stages 1-4.</p> + +<h2 id="other-binary-operators">Other Binary Operators</h2> + +<p>We still haven’t implemented all the binary operators! We can’t implement assignment operators yet (like <code class="language-plaintext highlighter-rouge">+=</code> and <code class="language-plaintext highlighter-rouge">-=</code>), because we don’t have support for local variables. But there are other operators you should be able to implement on your own now:</p> + +<ul> + <li>Modulo <code class="language-plaintext highlighter-rouge">%</code></li> + <li>Bitwise AND <code class="language-plaintext highlighter-rouge">&</code></li> + <li>Bitwise OR <code class="language-plaintext highlighter-rouge">|</code></li> + <li>Bitwise XOR <code class="language-plaintext highlighter-rouge">^</code></li> + <li>Bitwise shift left <code class="language-plaintext highlighter-rouge"><<</code></li> + <li>Bitwise shift right <code class="language-plaintext highlighter-rouge">>></code></li> +</ul> + +<p>This week’s tests don’t cover these, so it’s up to you whether to implement them or skip them.</p> + +<h2 id="up-next">Up Next</h2> + +<p><a href="https://norasandler.com/2018/01/08/Write-a-Compiler-5.html">Next week</a> we’ll add local variables! That means we’ll finally be able to write programs that aren’t just return statements. See you then!</p> + +<h2 id="update-222019">Update 2/2/2019</h2> + +<ul> + <li>Updated code generation for logical AND and OR to short-circuit correctly.</li> +</ul> + +<p><em>If you have any questions, corrections, or other feedback, you can <a href="mailto:nora@norasandler.com">email me</a> or <a href="https://github.com/nlsandler/write_a_c_compiler/issues">open an issue</a>.</em></p> + +<div class="footnote"> + <p><sup id="fn1">1</sup> +You can find a complete C operator precedence table <a href="https://en.cppreference.com/w/c/language/operator_precedence">here</a>.<a href="https://norasandler.com/2017/12/28/Write-a-Compiler-4.html#anchor1">↩</a></p> +</div> + +<div class="footnote"> + <p><sup id="fn2">2</sup> +See section 6.5.13, paragraph 4, for logical AND and 6.5.14, paragraph 4 for logical OR.<a href="https://norasandler.com/2017/12/28/Write-a-Compiler-4.html#anchor2">↩</a></p> +</div> + + </div><a class="u-url" href="https://norasandler.com/2017/12/28/Write-a-Compiler-4.html" hidden=""></a> +</article> + + </div> + </main> + + <footer class="site-footer"> + + <div class="wrapper"> + <div class="footer-col-wrapper"> + <div class="footer-col footer-col-1"> + <div class="rc-scout" data-scout-rendered="true"><p class="rc-scout__text"><i class="rc-scout__logo"></i> Want to become a better programmer? <a class="rc-scout__link" href="https://www.recurse.com/scout/click?t=8f520efbc4be09fb83a71920f53a07b7">Join the Recurse Center!</a></p></div><script async="" defer="" src="./Writing a C Compiler, Part 4_files/loader.js"></script> + </div> + </div> + <div class="footer-col-wrapper"> + <div class="footer-col footer-col-1"> + © 2023 Nora Sandler. + </div> + </div> + </div> + +</footer> + + + + + +<script async="" src="./Writing a C Compiler, Part 4_files/scout-176be16681a03cbddd686f3cc96694d3aab338ea5cb65452f83d989309810528.js"></script><style class="rc-scout__style" type="text/css">.rc-scout { + display: block; + padding: 0; + border: 0; + margin: 0; +} +.rc-scout__text { + display: block; + padding: 0; + border: 0; + margin: 0; + height: 100%; + font-size: 100%; +} +.rc-scout__logo { + display: inline-block; + padding: 0; + border: 0; + margin: 0; + width: 0.85em; + height: 0.85em; + background: no-repeat center url('data:image/svg+xml;utf8,%3Csvg%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%20viewBox%3D%220%200%2012%2015%22%3E%3Crect%20x%3D%220%22%20y%3D%220%22%20width%3D%2212%22%20height%3D%2210%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%221%22%20y%3D%221%22%20width%3D%2210%22%20height%3D%228%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%222%22%20y%3D%222%22%20width%3D%228%22%20height%3D%226%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%222%22%20y%3D%223%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%224%22%20y%3D%223%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%226%22%20y%3D%223%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%223%22%20y%3D%225%22%20width%3D%222%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%226%22%20y%3D%225%22%20width%3D%222%22%20height%3D%221%22%20fill%3D%22%233dc06c%22%3E%3C%2Frect%3E%3Crect%20x%3D%224%22%20y%3D%229%22%20width%3D%224%22%20height%3D%223%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%221%22%20y%3D%2211%22%20width%3D%2210%22%20height%3D%224%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%220%22%20y%3D%2212%22%20width%3D%2212%22%20height%3D%223%22%20fill%3D%22%23000%22%3E%3C%2Frect%3E%3Crect%20x%3D%222%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%223%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%224%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%225%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%226%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%227%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%228%22%20y%3D%2213%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3Crect%20x%3D%229%22%20y%3D%2212%22%20width%3D%221%22%20height%3D%221%22%20fill%3D%22%23fff%22%3E%3C%2Frect%3E%3C%2Fsvg%3E'); +} +.rc-scout__link:link, .rc-scout__link:visited { + color: #3dc06c; + text-decoration: underline; +} +.rc-scout__link:hover, .rc-scout__link:active { + color: #4e8b1d; +} +</style></body></html>
\ No newline at end of file |