Working through WACC – Chapter 8, Loops

All part of the series about this book:

Time to add while, do {} while, for, break and continue. And just because all text is boring here’s a picture:

This is where I started to doubt my single phase parse direct to TACKY. Particularly in the extra credit.

For Loops

A for loop like this:

for (int x = 0; x < 10; x++){
    foo(x);
}

Is shorthand for:

  int x = 0;
start:
  if !(x < 10) goto end;
  foo(x);
  x++;
  goto start;
end:

Okie dokie, how hard can that be to compile? Well…

The main compile phase is the C to TACKY pass. TACKY can almost be automatically mapped to assembly code, the heavy lifting is in the first phase. Reminder, I ignored Nora’s advice and my front end is a single pass, the parser takes the lexer output stream and generates the TACKY directly.

Whats the problem? Look at the expanded code again, here is an abstracted version

// for (<init>;<condition>;<post-body>) {<body>}
// produces

  <init>
start:
  if !(<condition>) goto end;
  <body>
  <post-body>
  goto start;
end:

Listing 1

See the issue? The parser sees the code in the order init, condition, post-body, body, but it needs to output the code for body (which it hasnt seen yet) before the code for post-body

Sidebar: Some Compiler History

Older computer languages like c, Fortran, Cobol were born in the days when computers were very, very tight on resources. C started on a PDP-11, actually this specific one

This system had 64kb of RAM. This meant that you could not read a whole program’s source code into memory, munge on it, and then spit out the assembler, or machine code, you had to be able to generate code as you went along. This, in turn, meant that the language had to be designed to facilitate a single pass. This why you cannot do this

int main(){
   int y = 42;
   process(y);
}

void process(int y){
  *y = *y + 1;
  return y;
}

When the compiler hits the word ‘process’ it has no idea what it means. (In fact C assumes that it is a function that takes one int and returns one int, so it gets upset when it sees the true definition later)

You have to do

void process(int y);

int main(){
   int y = 42;
   process(y);
}

void process(int y){
  *y = *y + 1;
  return y;
}

void process(int y){
  *y = *y + 1;
  return y;
}

int main(){
   int y = 42;
   process(y);
}

So the compiler knows what ‘process’ means by the time it hits the call to it.

What this means is that the first C implementations could deal with the ‘out of order’ clauses in a for loop only by some clever jumping about. This is what I worked out is needed: a liberal helping of spaghetti

// for (<init>;<condition>;<post-body>) {<body>}
// produces

  <init>
start:
  if !(<condition>) goto end;
  goto body:
post:
  <post-body>
  goto start;
body:
  <body>
  goto post;
end:

Listing 2

This code can be generated as we read the lex stream. The only piece of ‘smartness’ now required is the ability to do a forward jump. An assembler has to be able to do this as well so the tricks for doing it are (and were well know at the time) simple.

More modern compilers will generate the Listing 1 code because they can, they read the whole source code before starting to generate output. (Why do they want to do that? Its less code and less jumps, modern CPUs hate jumps)

This means that we should be able to tell how a compiler works inside just by looking at the code it generates. Lets see. Here is the output from 2 different c compilers for this code

int main(){
   int i;
   for( i = 0; i < 10; i++){
      printf("%d\n", i);
   }
 }

Compiler #1

        mov     DWORD PTR i$1[rsp], 0
        jmp     SHORT $LN4@main
$LN2@main:
        mov     eax, DWORD PTR i$1[rsp]
        inc     eax
        mov     DWORD PTR i$1[rsp], eax
$LN4@main:
        cmp     DWORD PTR i$1[rsp], 10
        jge     SHORT $LN3@main
; Line 3
        mov     edx, DWORD PTR i$1[rsp]
        lea     rcx, OFFSET FLAT:$SG7475
        call    printf
; Line 4
        jmp     SHORT $LN2@main
$LN3@main:
; Line 5

Compiler #2

    mov     eax, 0
    mov     [ebp+var_4], eax
 loc_8000012:                
    mov     eax, [ebp+var_4]
    cmp     eax, 0Ah
    jge     locret_8000044
    jmp     loc_8000030
 loc_8000023:                     
    mov     eax, [ebp+var_4]
    mov     ecx, eax
    add     eax, 1
    mov     [ebp+var_4], eax
    jmp     short loc_8000012
 loc_8000030:                     
    mov     eax, [ebp+var_4]
    push    eax
    mov     eax, offset L_0
    push    eax
    call    printf
    add     esp, 8
    jmp     short loc_8000023
  locret_8000044:

I hope you can see that compiler #1 has reorganized the code so that it goes

  <init>
  goto cond;
post:
  <post>
cond:
  if !(<condition>) goto end;
  <body>
  goto post;

Whereas #2 has

  <init>
start: //loc_8000012:
  if !(<condition>) goto end;
  goto body:
post:  // loc_8000023: 
  <post-body>
  goto start;
body:  //  loc_8000030:  
  <body>
  goto post;
end:  //locret_8000044:

Which is the Listing 2 style. What compilers are they?

#1 is Microsoft Visual C. A modern compiler that runs on chunky machines.
#2 is TCC : Tiny C Compiler an extremely lean mean compiler, its clearly an old fashioned single pass compiler.

Lets look at one more

	movl $0, %ebx
.Lfor_start.4:
	cmpl $10, %ebx
	movl $0, %r9d
	setl %r9b
	cmpl $0, %r9d
	je .Lbreak.for.3
	movl %ebx, %edi
	call print
.Lcontinue.for.3:
	addl $1, %ebx
	jmp .Lfor_start.4
.Lbreak.for.3:

This code does init, compare, body, post-body. This means it’s clearly a multi pass compiler, note that it has not done the more aggressive reordering that MSVC did. What compiler is it? its Nora’s reference implementation nlsandler/nqcc2: Reference implementation for Writing a C Compiler. So now we see the difference my front end choice makes, I generate code that looks like the output of tcc, Nora’s looks like MSVC

Implementing for

At this point I still have my single pass compiler so I will use the Listing 2 plan.

The remaining challenge is break and continue. We have to keep track of what they mean. They are both goto‘s but the destination is implicit. The trick is to maintain a stack of break and continue destinations, every time you enter a new loop push new destinations onto the stack, when you leave the loop pop that stack.

Generate 4 labels that correspond to the start , post, body and end labels in listing 2. The continue target is post and the break target is end

Here is my TACKY code for an example with a break

int main(void){
    int i = 0;
 
   for(int i = 0; i < 10; i = i + 1){
      if (i > 5)
         break;
   }
 }

  Copy Int(0) Variable("i$1")
Label "_start_for_1"
  Binary LessThan Variable("i$1") Int(10) Variable("temp.4")
  JumpIfZero Variable("temp.4") "_end_for_0"
  Jump "_body_for_2"
Label "_inc_for_3"
  Binary Add Variable("i$1") Int(1) Variable("temp.5")
  Copy Variable("temp.5") Variable("i$1")
  Jump "_start_for_1"
Label "_body_for_2"
  Binary GreaterThan Variable("i$1") Int(5) Variable("temp.6")
  JumpIfZero Variable("temp.6") "_if_false_7"
  Jump "_end_for_0"
  Jump "_if_end_8"
Label "_if_false_7"
Label "_if_end_8"
   Jump "_inc_for_3"
Label "_end_for_0"
      Return Int(0)

I hope that the noisiness of the if block doesn’t make this too obscure

And we’re done.

Extra Credit

switch statements how hard can they be! Extremely, it turns out.

First we have the code ordering problem gone into above. It would be nice if

switch (x){
   case 1:
   case 2:
      foo();
      break;
   case 3:
      bar();
      break;
   default:
      bong();
}

Could be compiled as

    if (x == 1) goto case1;
    if (x == 2) goto case2;
    if (x == 3) goto case3;
    goto default;
case1:
case2:
    foo()
    goto end;
case3;
    bas();
    goto end;
default:
    bong();
end:

but my single pass parser is not smart enough to do that, it requires way too much forward knowledge

Second problem is that there are some very strange semantics in switch, the C standard even calls them out.

6.8.4.2 The switch statement has

switch (expr)
{
   int i = 4;
   f(i);
case 0:
   i = 17;
/* falls through into default code */
default:
   printf("%d\n", i);
}

and says

the object whose identifier is i exists with automatic storage duration (within the block) but is never initialized, and thus if
the controlling expression has a nonzero value, the call to the printf function will access an indeterminate value. Similarly,
the call to the function f cannot be reached.

Huh, it means that this code really means

switch (expr)
{
   int i /* = 4 */;
   // f(i);
case 0:
   i = 17;
/* falls through into default code */
default:
   printf("%d\n", i);
}

ie, variable declarations work before the first case but no executable code is generated. Also worth noting that no c compiler I tried even warned you that the f(i) code is ignored, gcc did warn that the = 4 is ignored. So I have to suspend code generation while parsing that.

Other oddness, default does not have to be at the end, but is taken when its hit.

Also break works in a switch but not continue (it works but not for the switch, its still attached to the containing loop). This means that we have to change the code that keeps track of these. For the loops so far break and continue always track the same, but now they need to be split into 2 different stacks.

break stack: push and pop on do, while, do{ }while, for and switch
continue stack: push and pop on do, while, do{ }while and for

Single Pass Switch Code

So how does the single pass code for a switch look.

Each case block looks like this

   ...
next_case_x:
   if expr != value
      goto next_case_y
drop_thru_x:
   <body>
   goto drop_thru_y
   ...

A break just resolves to a goto exit; ,
two case labels with no code are not a special case, its just a drop thru without any intervening code
default is a case without the if statement

So this switch

switch (expr){
  case 1:
     <body1>
  case 4:
     <body2>
     break;
  case 7:
  case 8:
     <body3>
     break;
  default:
     <body4>
}

Generates

    int temp = expr; 

    if temp != 1
       goto next_case_1;
    <body1>
    goto drop_thru_1;

next_case_1:
    if temp != 4
       goto next_case_2;
drop_thru_1:
    <body2>
    goto exit;
    goto drop_thru_2;

next_case_2:
    if temp != 7
       goto next_case_3;
    // no body
    goto drop_thru3

next_case_3:
    if temp != 8
       goto next_case_4;
drop_thru_3:
    <body3>
    goto drop_thru_4;

next_case_4:
     if 0 goto next_case_5;
     <body4>
     goto drop_thru_5;

next_case_5:
drop_thru_5:
exit:

Some redundant parts can be eliminated but leaving all in allows you to see how each case is fundamentally the same.

This is my design, lets see what Monsieur Bellard does in tcc.

BTW, I have actually caught up to myself in this blog. Implementing switch is where I am up to, and I just now decided to look at the tcc output

    jmp     loc_8000027
    jmp     loc_8000030
loc_8000027:                         
    cmp     eax, 1
    jnz     loc_800003D
loc_8000030:                       
    mov     eax, 1
    mov     [ebp+var_8], eax
    jmp     loc_8000046
loc_800003D:  // next_case_1   
    cmp     eax, 4
    jnz     loc_8000058
loc_8000046:  // drop_thru_1          
    mov     eax, 2
    mov     [ebp+var_8], eax
    jmp     locret_8000084 //break
    jmp     loc_8000061
loc_8000058:   // next_case_2            
    cmp     eax, 7
    jnz     loc_8000066
loc_8000061:   // drop_thru_2                
    jmp     loc_800006F
loc_8000066:                       
    cmp     eax, 8
    jnz     loc_800007C
loc_800006F:                      
    mov     eax, 3
    mov     [ebp+var_8], eax
    jmp     locret_8000084
loc_800007C:                         
    mov     eax, 4
    mov     [ebp+var_8], eax
locret_8000084:

Woohoo, its identical, right down to the redundant jump after the break

I added comments showing the correspondence between the tcc listing and mine. The tcc listing was generated using the excellent IDA Free; tcc does not have an option to generate assembly output.

Out of curiosity let’s look at msvc.

; Line 5
	mov	eax, DWORD PTR expr$[rsp]
	mov	DWORD PTR tv64[rsp], eax
	cmp	DWORD PTR tv64[rsp], 1
	je	SHORT $LN4@main
	cmp	DWORD PTR tv64[rsp], 4
	je	SHORT $LN5@main
	cmp	DWORD PTR tv64[rsp], 7
	je	SHORT $LN6@main
	cmp	DWORD PTR tv64[rsp], 8
	je	SHORT $LN7@main
	jmp	SHORT $LN8@main
$LN4@main:
; Line 7
	mov	DWORD PTR z$[rsp], 1
$LN5@main:
; Line 9
	mov	DWORD PTR z$[rsp], 2
; Line 10
	jmp	SHORT $LN2@main
$LN6@main:
$LN7@main:
; Line 13
	mov	DWORD PTR z$[rsp], 3
; Line 14
	jmp	SHORT $LN2@main
$LN8@main:
; Line 16
	mov	DWORD PTR z$[rsp], 4
$LN2@main:

Much cleaner and clearer, the power of two passes.

Dont Ignore Nora – part 2

Now I see the benefit of the two pass front end. I think a discussion of this in the book would have been useful, explaining the strengths and weaknesses of each approach.

In the face of the switch spaghetti I reconsidered my approach, I even started coding up the intermediate representation in the c =>TACKY phase. But right now, I have decided to keep my current one pass method.

One thing I am aware of is that there are optimization opportunities at this point in the pipeline that I do not have. I skipped forward to part III and it seems to operate in the TACKY=>x64 phase, so I am not going to lose out (I use the recommended structure in that phase)

OK, time to complete the pasta-like switch and move on.

Implementing `switch`

switch needs a context block that is used to keep track of nested switch statements. It contains:

a list of seen case values (duplicates are illegal)
the name of the next case label
the name of the next drop thru label
the name of the exit label
the value of the expression to be compared
A flag indicating if we have seen a default, only 1 is allowed
A flag indicating if we are before the first case, this is so we can suppress code generation there.

Note that the break destination label is not in this, there is a separate break label stack.

There is a stack of these, push a new one onto the stack when entering a switch block, pop when leaving.

Ran 372 tests in 47.489s

OK
PS C:\work\forks\writing-a-c-compiler-tests>

Now onto the hard part of using windows, calling functions

Working through WACC – Chapter 8, Loops

For Loops

Sidebar: Some Compiler History

Implementing for

Extra Credit

Single Pass Switch Code

Dont Ignore Nora – part 2

Implementing switch

Share this:

Comments

Leave a comment Cancel reply

Implementing `switch`