codegen.cc

PL/0源码

//////////////////////////////////////////////////////////////////////////////
//
//  codegen.cc -- code generation
//
//  Stack frame:
//
//      Last local variable     <-- SP points here
//      ...                         ^ (negative offsets from FP)
//      First local variable        | lower addresses, stack growth
//      Return address          <-- FP points here
//      Dynamic link                |
//      Static link, if any         | (positive offsets from FP)
//
//
//  Calling sequence:
//
//      If called routine is not at outermost nesting level
//          Save static link
//      Jump and link
//      -----
//      Decrement sp by enough to make room for local variables
//      Save fp
//      Save return address
//      ...
//      Load fp
//      Load return address into scratch register
//      Jump register
//      -----
//      If routine is not at outermost nesting level
//          Load static link
//
//  The SP is the last *used* location in the stack.  Note that all offsets
//  are specified in bytes.
//
//  In its current form, the PL/0 compiler keeps nothing interesting in
//  registers across subroutine calls.  The procedure calling sequence
//  therefore doesn't need to save any registers, other than the fp and
//  ra (if non-leaf).  If better code is generated in the future, this
//  will have to change.  Under the MIPS calling convention, the called
//  is supposed to save and restore any registers it uses from the set
//  s0..s7 ($17..$23).
//
//  How code generation *should* work:
//      (1) make a pass over the abstract syntax tree, expanding
//          everything into very basic operations.  Specifically,
//          references to variables in outer scopes should be expanded
//          to explicitly dereference the fp.  If PL/0 had array
//          references, these would be expanded into adds, multiplies,
//          and dereferences.
//      (2) perform machine-independent optimizations, such as copy
//          propagation, common subexpression elimination, strength
//          reduction, induction variable elimination, and hoisting of
//          loop invariants.  Trees for basic blocks would be turned
//          into DAGs in this step.
//      (3) walk the collection of DAGs and do register allocation.
//      (4) walk it all again, dumping code
//
//      [NB: this assumes we are not doing inter-procedural optimization,
//      and it glosses over the interaction of register allocation with
//      instruction scheduling and other machine-specific optimizations.]
//
//  Simplifications:
//      (1) we skip the first pass.  There are no arrays, and static chain
//          following can be done with one scratch register, without messing
//          up register allocation.
//      (2) we don't do much optimization.  The output code is BAD.
//      (3) we do VERY naive register allocation -- more or less using
//          the non-special registers as a stack, and compiler_dying
//          if we run out.
//
//      [NB: One reason to allocate registers (even naively) before
//      dumping code is that we don't know what registers to save in a
//      procedure prologue until after we've done register allocation
//      for the body of the procedure.  (This is assuming of course
//      that we need to save registers, which we don't in the
//      current implementation.)  An alternative would be to generate
//      the prologue at the *bottom* of the routine, and jump back.
//      Another alternative would be to buffer up the code for
//      the routine and then spit it out after the prologue.]
//

#include <strstream>
#include "plzero.h"
#include "scanner.h"
#include "tokens.h"
#include "symtab.h"
#include "attributes.h"
#include "mips.h"
#include "prologue.h"

#define STATIC_LINK_OFFSET      8       // bytes back from the FP
#define RETURN_ADDR_OFFSET      4       // bytes back from the FP
#define FIRST_LOCAL_OFFSET      4       // bytes up from the FP
#define SP_REG                  ((mips_register_t)29)
#define FP_REG                  ((mips_register_t)30)
#define RA_REG                  ((mips_register_t)31)
#define ZERO_REG                ((mips_register_t)0)
#define SCRATCH_REG             ((mips_register_t)2)
#define SCRATCH_REG2            ((mips_register_t)3)
#define OUTPUT_REG              ((mips_register_t)4)

static unsigned register_bits[LAST_REG + 1] =
{
    0x00000001, 0x00000002, 0x00000004, 0x00000008,
    0x00000010, 0x00000020, 0x00000040, 0x00000080,
    0x00000100, 0x00000200, 0x00000400, 0x00000800,
    0x00001000, 0x00002000, 0x00004000, 0x00008000,
    0x00010000, 0x00020000, 0x00040000, 0x00080000,
    0x00100000, 0x00200000, 0x00400000, 0x00800000,
    0x01000000, 0x02000000, 0x04000000, 0x08000000,
    0x10000000, 0x20000000, 0x40000000, 0x80000000
};
//  Bit mask for register allocation.

static int space_in_scope[MAX_SCOPES + 1];
//  Amount of space (in bytes) required for the variables
//  in each scope.  Needed for procedure prologues.


//////////////////////////////////////////////////////////////////////////////
//
//  Utility routines.
//

static int name_numbers['z' + 1];
//  Used for generating names for use in compiler_target code

//  Initialize the register variable stuff:
//    8..15, 24, 25 (t0..t9) are safe.
//    2 is used for SCRATCH_REG, 3 for SCRATCH_REG2 which is used for static
//    chaining and 31 is used for linking return addresses.
static unsigned available_regs = register_bits[8] | register_bits[9]
                                 | register_bits[10] | register_bits[11]
                                 | register_bits[12] | register_bits[13]
                                 | register_bits[14] | register_bits[15]
                                 | register_bits[24] | register_bits[25];
static const unsigned special_regs = ~(register_bits[3]|available_regs);

ofstream code;
//  file stream for assembler output

////////
//  Return next available name of form XXnnnn, where X is firstChar
//  and nnn is the next serial number from name_numbers
//  The first char is doubled to avoid confusion with MIPS register names.
//
static void next_name(mips_name_t rtn, char firstChar)
{
    int n;
    assert((n = ++name_numbers[firstChar]) < 10000);
    rtn[0] = rtn[1] = firstChar;
    rtn[5] = '0' + n % 10; n /= 10;
    rtn[4] = '0' + n % 10; n /= 10;
    rtn[3] = '0' + n % 10; n /= 10;
    rtn[2] = '0' + n;
    rtn[6] = 0;
}

////////
//  Allocate next available register, stack style.  Die if there aren't any
//  more available.  NB: this sort of simplistic register allocation would
//  be unacceptable in a production-quality compiler
//
static mips_register_t get_register (void)
{
    for (mips_register_t i = FIRST_REG; i <= LAST_REG; i++)
        if (register_bits[i] & available_regs) {
        available_regs &= ~register_bits[i];
        return i;
        }
    die_compiler ("Not enough registers.");
    return 0;
}

////////
//  Return register to the free pool
//
static void free_register (mips_register_t r)
{
    assert(r <= LAST_REG);
        // can't free non-existent register
    if (!(register_bits[r] & special_regs)) {
    available_regs |= register_bits[r];
    }
}

////////
//  Allocate a register and mark it as the location for the results of this
//  node of the syntax tree.
//
void put_in_register (syntax_code_t * q)
{
    q->result_register = get_register();
    q->result_place = R_REGISTER;
    q->result_value = 0;
    q->registers_used = register_bits[q->result_register];
}

//////////////////////////////////////////////////////////////////////////////
//
//  Allocate_space:
//
//  Traverse the symbol table, assigning memory locations and frame
//  pointer offsets.  Each symbol entry type must implement the allocate_space
//  member function.
//

static int      next_fp_offset;
static void allocate_space(void)
{
    scope_number_t last = last_scope();
    for (scope_number_t s = predefined_scope; s <= last; s++) {
    next_fp_offset = FIRST_LOCAL_OFFSET;
        for (symbol_entry_t *p = first_in_scope(s); p != NULL; p = p->next()) {
            p->allocate_space();
    }
    space_in_scope[s] = next_fp_offset - FIRST_LOCAL_OFFSET;
    }
}

void symbol_entry_t::allocate_space(void)
{
    // Generic symbols don't need any storage.
}

void se_constant_t::allocate_space(void)
{
    // Constants are inlined, they don't need any external storage data.
}

void se_variable_t::allocate_space(void)
{
    code_gen_info = new symbol_code_t;

    if (scope == global_scope) {
        code_gen_info->data_place = R_LABEL;
        next_name(code_gen_info->where.label, 'v');
    }
    else if (scope == predefined_scope) {
        // Labels for predefined variables are just their name.
        unsigned int    i;
        const char *    sp;

        code_gen_info->data_place = R_LABEL;
        for (i = 0, sp = token_chars(name);
                i < sizeof(mips_name_t); sp++, i++) {
            code_gen_info->where.label[i] = tolower(*sp);
            if (!*sp) break;
        }
    }
    else
    {
        code_gen_info->data_place = R_OFFSET;
        code_gen_info->where.offset.reg = FP_REG;
        code_gen_info->where.offset.pos = -next_fp_offset;
                                        // Locals are below the frame pointer.
        next_fp_offset += 4;            // Variables are 4 bytes long.
    }
}

void se_procedure_t::allocate_space(void)
{
    // Procedures need a label, which is later used in their code generation.
    code_gen_info = new symbol_code_t;
    code_gen_info->data_place = R_LABEL;
    next_name(code_gen_info->where.label, 's');
}

//////////////////////////////////////////////////////////////////////////////
//
//  generate_data: Output to code file any data declarations needed.  Each
//                 symbol_table_t subclass must defined a generate_data member
//                 function.  Basically this code should just reserve and space
//                 needed for the symbol in the output file.
//

void symbol_entry_t::generate_data(void)
{
    // Generic symbols don't need any storage.
}

void se_constant_t::generate_data(void)
{
    // Constants are inlined, they don't need any external storage data.
}

void se_variable_t::generate_data(void)
{
    if (code_gen_info != NULL && code_gen_info->data_place == R_LABEL) {
        if (scope != predefined_scope) {
            mips_src_lines(declaration);
            mips_cm(token_chars(name));
            mips_op(code_gen_info->where.label, M_WORD, 0);
        }
    }
}

void se_procedure_t::generate_data(void)
{
    // Procedures are created by their corresponding generate_code function.
}

//////////////////////////////////////////////////////////////////////////////
//
//  Generate code to access symbol table defined data
//
//  The generate_code member function of symbol_entry_t or any of its
//  subclasses generates the code need to access the symbol.  This function
//  would probably be overridden for something like an array.  In our case,
//  all of the currently defined PL/0 symbol table entry types uses either
//  R_LABEL or R_OFFSET addressing.
//

symbol_code_t *symbol_entry_t::generate_code(void)
{
    if (code_gen_info == NULL) {
        dump_object_data();
        die_compiler("Unexpected call to symbol_code_t::generate_code");
    }
    if (code_gen_info->data_place == R_LABEL) {
        ; // Labels don't need any extra code generation
    }
    else if (code_gen_info->data_place == R_OFFSET) {
        if (code_gen_info->where.offset.reg == FP_REG
            || code_gen_info->where.offset.reg == SCRATCH_REG2) {
            // If the register is either the frame pointer or the scratch
            // registers used to tunnel through frames, then we need to
            // make sure that we are at the correct scope depth.

            mips_register_t     addrReg = FP_REG;
            scope_number_t      depth = scope_depth(scope);
            if (depth > 0)
                mips_cm(string("follow the static chain to ")
                    + string(token_chars(name)));
            for (int i = 0; i < depth; i++) {
                mips_op(M_LW, SCRATCH_REG2, STATIC_LINK_OFFSET, addrReg);
                addrReg = SCRATCH_REG2;
            }
            code_gen_info->where.offset.reg = addrReg;
        }
    }
    else {
        dump_object_data();
        ostrstream ost;
        ost << "::generate_code called for symbol with bad data_place: "
            << code_gen_info->data_place;
        die_compiler(ost.str());
    }
    return code_gen_info;
}

//////////////////////////////////////////////////////////////////////////////
//
//  Allocate Registers:
//
//  Each node of the syntax tree must implement the member function
//  allocate_register which allocates any registers needed by the node or its
//  children.
//

syntax_code_t * syntax_tree_t::allocate_registers(void)
{
    code_gen_info = new syntax_code_t;
    code_gen_info->result_place = R_UNKNOWN;
    code_gen_info->result_register = 0;
    code_gen_info->result_value = 0;
    code_gen_info->registers_used = 0;
    return code_gen_info;