Chapter 8 - Intermediate Code Generation

Reading: Chapter 7 (7.1 - 7.8 pp. 389-446) - Almost all of this should be review as we have talked in detail about the runtime environment and symbol table topics. The two main issues that I have not talked about are displays and the various parameter passing methods other than pass by value and pass by reference. I will probably cover these at a later date.

Chapter 8 - Intermediate Code Generation

Reading: Chapter 8 (8.1 - 8.7 pp. 463-508)

We now turn our attention to code generation. Remember, we are generating three-address code (called quads) for our simulated machine. If we so desired, we could generate assembly language from our quad file and assemble our program into the target code of some machine.

Up to now, we have represented our code with an abstract syntax tree. We now need to take this abstract syntax tree and produce our code for the simulated machine which will look quite different.

Let us consider instructions of the following form:

x = y binop z

In this case, we know that the binop operator applies to y and z. The result of y binop z is calculated and then assigned to be the new value of x.

Consider the C statement:

x = a + b * c;

The three-address code for this statement might look like the following:

t1 = b * c
t2 = a + t1

Why is this code called three-address code?

We are concerned with the following kinds of statements:

1) Assignment Statement without unary operators: x = y binop z

2) Assignment Statement with unary operators: x = unop y

3) Unconditional Jumps: goto Label

4) Conditional Jumps: if (x relop y) goto Label

5) Function Call: Foo (a,b,c)

6) Function Return: return y

7) Indexed Assignments: x = a[i] and a[i] = x

8) Address and Pointer Assignments: x = &a and b = *a and *a = b

Let's take a look at a litte more complicated example as follows:

int Foo(b)
  int b;
{
  output(b);
}


main ()
{
  int a;

  a = 100;
  a = a + 1;
  Foo (a);
}

The partial output from this program run through our compiler is as follows:

  1    int Foo(b)
  2      int b;
  3    {
  4      output(b);
  5    }
  6    
  7    main ()
  8    {
  9      int a;
 10    
 11      a = 100;
 12      a = a + 1;
 13      Foo(a);
 14    }

The quad file will look like the following. I've included horizontal rules to make it easier for you to take notes as we discuss this in class. Follow the output specification exactly as it is detailed in the assignment.

 1  27   0   0   0   0   0   0

 2  22   0   0   0   0   0   0

 2  20   4  -3   0   0   0   0

 2  25   0   1   0   0   0   0

 2  26   0   0   0   0   1   0

 2  23   0   0   0   0   0   0

 2  22   0   3   0   0   0   0

 2  26   2   1   0   0   3   1

 2   1   4   1   2   2   3   2

 2  26   4   2   0   0   3   1

 2  20   4   1   0   0   0   0

 2  21   0   1   0   0   0   1

 2  26   2   0   0   0   3   3

 2  26   0   0   0   0   1   0

 2  23   0   0   0   0   0   0

 1  21   0   0   0   0   0   6

 1  28   0   0   0   0   0   0

3
0
100
1


0 errors

Let's walk through this quad file making sure we know how the activation records are set up and how the runtime environment is going to work. Further, I will post the interpreter code shortly, but for now, here is the addressing mode decoder code.

/************************************************************************/
/*                                                                      */
/*                               intDecode                              */
/*                                                                      */
/*  This function decodes the passed address based on the passed        */
/*  mode and returns the effective address.  Address modes and the      */
/*  effective addresses yielded by them are as follows:                 */
/*                                                                      */
/*         address mode        |  effective address                     */
/*        _____________________|_____________________________           */
/*         IMMEDIATE           |  address                               */
/*         GLOBAL_LVALUE       |  address                               */
/*         GLOBAL_RVALUE       |  stack(address)                        */
/*         LOCAL_LVALUE        |  gAP + address                         */
/*         LOCAL_RVALUE        |  stack(gAP + address)                  */
/*                                                                      */
/*                                                                      */
/************************************************************************/

int intDecode(int wMode,        /* mode of the operand */
              int wAddress)     /* address of where value for operand is found */
{
  switch(wMode)
  {
    case IMMEDIATE:      return(wAddress);
   
    case GLOBAL_RVALUE:  return(gStack[wAddress]);

    case GLOBAL_LVALUE:  return(wAddress);

    case LOCAL_RVALUE:   return(gStack[gAP + wAddress]);

    case LOCAL_LVALUE:   return(gAP + wAddress);
  };
}