Working Through WACC – Chapter 14 , pointers

WACC is this great book:

I am blogging my way through it, chapter by chapter.

Major Refactoring

Well first off we need to rewrite the parsing of declarations because it just got a lot more complex. I wasnt happy with my previous ‘making it up as you go along’ version – so I am happy to do this.

Secondly I reworked how Symbols are represented. Was not entirely happy before, now I am much happier. I met one of rusts well known issues. We need

pub enum SymbolType {
    Int32,
    Int64,
    UInt32,
    UInt64,
    Double,
    Function(Vec<SymbolType>, SymbolType),
    Pointer(SymbolType),
}

This is a recursive definition; the non-basic types contain other symbols (think ‘pointer to int’ for example). rust cant do this, in fact what you need is

pub enum SymbolType {
    Int32,
    Int64,
    UInt32,
    UInt64,
    Double,
    Function(Vec<SymbolType>, Box<SymbolType>),
    Pointer(Box<SymbolType>),
}

where Box is a pointer to an object on the heap (think unique_ptr in c++).

A symbol is this

pub(crate) struct Symbol {
    pub name: String,
    pub state: SymbolState,
    pub rename: String,
    pub stype: SymbolType,
    pub linkage: SymbolLinkage,
    pub explicit_external: bool,
    pub scope_pull: bool,
}

the scope_pull field is for dealing with code like this

int a;
int main(void) {
    int a;
    {
        extern int a;
    }
    return 0;
}

that inner extern int a is pulling the global ‘a’ from the first line into scope.!

The rename field is for symbols that have been renamed – ie locals or function parameters.

Declarator Processing

That was tough. Having to write parsing code for stuff that I did not know was legal c is hard. I do not have an intuitive feel for what it should do.

I am one of those c coders that has to look up how to do function pointer types because they seem like a random sequence of ‘*()’ characters. I know we do not support function pointer types, but the declarator parser has to deal with the logic behind them.

Hard work

Converting The Book to Single Pass Front End

I diverged from Nora’s recommended approach right from the start. Nora has a two pass front end that reads the C source into an intermediate form that she calls an AST (I disagree that its an AST, but thats a minor nit). The second pass reads that intermediate form and generates TACKY from it. My front end parses the c code directly to TACKY.

This means that when I read a chapter I have to approach from two ends and kind of meet in the middle. I Read the EBNF as a guide to structuring the parser front end. I read the TACKY in the section that’s always called ‘TACKY generation’ to see what I need to generate. The TACKY generation also captures the essence of what the compiler needs to understand and pass to the backend.

I then iterate back and forth, simultaneously reading the intermediate form manipulation to understand the conversion logic. One of the good side effects of this is that I really understand what’s going on; I am not just blindly copying Nora’s pseudo-code and making it into rust.

I am still left with a piece of ‘magic’ code that I do not fully understand. This is the whole PlainValue / DefeferencedPointer / and_convert stuff. It works, because I now pass all the tests, but I am not sure what its really doing. I do not like magic code (same for the precedence parser, which is still voodoo as far as I am concerned). I am going to reread the book and my code once I have cleaned up and checked in at the completion of this chapter.

Complaints

As always, any complaint needs to be seen in the light of what a fantastic book this is

We now hit code where * and & are binary and unary operators. This caused some glitches for me. It would have been nice to have a heads up on this. In fact it unearthed the fact that I had 2 bugs working in tandem that made it look like I was parsing things correctly, but I was not.

The front end now explicitly knows that pointers are 64 bit.

Rather than defining a dedicated construct for null point-
ers, we’ll use the ULongInit(0) initializer, since pointers are unsigned 64-bit
integers.

I don’t think that is right approach. I mean it’s true for the x64 target this compiler is aimed at, but the front end should not have to know that. IMHO the correct way to do it is to explicitly have a NullPointer value.

Tests

One test that really had me perplexed was this one

/* This will be divisible by eight, since LONG64 is eight byte-aligned */
    return (ptr_as_long % 8 == 0);

The test suite would fail this. Then I would do my usual workflow of copying the source to my work area , building it and running it. It always worked, huh?

What I had was a program that was doing different things when run in different situations, to any c programmer this tells you that you have hit UB: the dreaded Undefined Behavior. Typically it would be an uninitialized variable, a buffer or array overrun etc. Rust programmers know, however, that those things do not happen in rust. The devils bargain you make with the compiler is this

I promise to code in the way rust demands, and not use the word ‘unsafe’
Rust promises that my program never crashes or exhibits UB and always behaves in a predictable fashion.

Well I did my part (you have no choice, the compiler wont let you do things not in the rule book unless you use the magic word ‘unsafe’), so what’s going on?

I compared the assembler generated by the working and non working compiles, identical.

Finally I worked it out. I was not 8 byte aligning my 64 bit longs. So I had a 50/50 chance of that test (% 8 == 0) being true.

I would note that x64 does not seem require 64 bit integer variables to be 8 byte aligned (all previous tests were passing). But the book does.

~~Ran 749 tests in 41.418s~~

Not Done – big Oops!

Above I said that once I had everything working I was going to revisit the ExpResult logic that was introduced to deal with dereferencing pointers.

SO I wen back and reread the code that I had and after a while I asked myself “How the heck is that working? Maybe there’s no test for it”. I looked and there was a test for it. It was then that I found that I had only been running the tests with --validate, so I was not actually running the code.

Then I found that there were tons of failing tests. This was actually a good thing because it forced me into understanding the pointer dereferencing logic, rather than just StackOverflowing the code (ie cutting and pasting code without really getting it)

LValues and RValues

First off – what problem are we trying to solve?

If you have

int a;
int b;
...
a = b;

in the last line a is an lvalue and b is an rvalue. These names come from them being on the left or right of an assignment. Anything can be an rvalue

a = f1();
a = 42;
a = (42 + sqrt(42.0));

but there are strict , but intuitive, rules about lvalues. These are all illegal

f1() = f2();
42 = 45;
(42 + sqrt(42.0)) = a;

In the code for mycc (my implementation of the WACC compiler) up to this chapter (and all other implementations) there is code like this

left = parse()
...
right = parse()
...
...
if operation is assignment {
   if left not lvalue 
      bail("lvalue expected")
   generate code to assign right to left
}
...

You might ask “dont we always have to check that left is an lvalue?”. No we might be processing

int val = (a + b)

here a and b can both be rvalues. So whether or not we need to check for left being an lvalue depends on the operation (val above must be an lvalue). Ok so whats the problem with chapter 14?

Pointers Enter The Game

now we can have

int a = 42;
int *pa = &a;
*pa = 43;
int b = *pa;

when we parse *pa we we need to return the internal object that represents a parsed item. For me thats this

pub enum Value {
    Int32(i32),
    Int64(i64),
    UInt32(u32),
    UInt64(u64),
    Double(f64),
    Variable(String, SymbolType),
}

The result of parsing something is either a constant or a variable. a variable is either a variable in the program (a or b say), or a temporary

int x = 32; => 32 is a constant
int x = y; => y is a variable
int x = (y + 99) => the (y + 99) is a temporary

So what should be returned for this?

int x = *pa;

For any other unary operator (like ~ say) this would be easy. It would parse into two things

operator ‘~’
variable ‘pa’

Downstream we would then generate code to twiddle the bits of pa. But what about. We can do the same here, we have to generate a few extra instructions to read the value pointed at by pa , rather than pa itself, fine. But what about

*pa = x;

‘*pa’ here means something completely different. it does not mean ‘fetch the value pa points at’ it means ‘store whats being assign to me into where pa points’. This means that we do not know what to do with ‘*pa’ until we find out how its going to be used.

Nora proposed a solution but I dont think its well explained, also Nora’s implementation (nqcc2) does not do the extra credit, some of them make this process much more complex, and its where I ended up tying myself in knots

Nora’s ExpResult

The description of this all comes from the section headed ‘A Strategy for TACKY Conversion’, (page 372 in my edition). We start out by creating

exp_result = PlainOperand(val) | DereferencedPointer(val)

Note that this does not appear in the parser AST not in the TACKY, that signals it as being a mechanism to get from AST to TACKY, its an implementation idea (dare I say trick). The use of this is explained in this paragraph

Now let’s update emit_tacky. We’ll make a couple of changes throughout
this function. First, wherever we currently call emit_tacky recursively on
a subexpression—except on the left-hand side of an assignment expression—
we’ll instead call emit_tacky_and_convert. This function will convert the
subexpression to TACKY and then lvalue convert the result. Second, wher-
ever we currently return a TACKY operand, we’ll wrap that operand in a
PlainOperand constructor. Listing 14-21 shows how to handle unary expres-
sions, with this chapter’s changes bolded.

I read and reread this many times and did not understand what it was doing. Finally I got it (after my big oops moment)

What is suggested if that when parsing anything into a Value (Nora’s term is Operand), instead of returning a Value you instead add an extra layer of indirection and return an ExpResult – like this

enum ExpResult{
   PlainOperand(Value)
   DereferencedPointer(Value)
}

Then once we know whether we want the dereferenced pointer to be an lvalue or an rvalue it gets processed appropriately. The big issue is , however , that the extra credit +=, -= etc introduce complexities that Nora does not dig into. When doing

int x = 0;
int *px = &x;
*px += 1;

*px is both an lvalue and an rvalue. Noras pseudo code does not cover this case. I ended up with 2 functions for dealing with this

make_rvalue, which takes a pending result and converts it to a Value

store_into_lvalue, which stores a value into a PendingResult object.

Ran 783 tests in 74.580s

Really woohoo