CSCE 434 Lecture 33

« previous | Wednesday, November 13, 2013 | next »

Lecture Slides

Register Allocation

• Virtual Registers: map "enough" into reality
• Targeting: Prioritize by some "good" metric

Lots of "fuzzy" terms

Intermediate Representation

We will be targeting RISC-like processors

We will abstract RISC as a:

• load-store architecture
• register-transfer language (RTL)
• three-address code
• explicit loads and stores

Examples:

load r1, <addr>    # r1 = value at <addr>
loadi r1, <const>  # r1 = value of <const>
store r1, <addr>   # <addr> = r1
move r1, r2        # r1 = r2
add r1, r2, r3     # r1 = r2 + r3
sub r1, r2, r3     # r1 = r2 - r3
mult r1, r2, r3    # r1 = r2 * r3
jmp <addr>         # jump to <addr>

Storage Layout

Local:

• stack frames
• offsets from frame pointer

Global: offset from known global label

Static: offset from procedure's static data section

Varied size storage

• local, non-static: top of stack frame
• other: allocate on heap

Key Issue: What variables can be safely allocated to registers, and what variables should be allocated to registers?

Assign variables to virtual registers

Treat those that can't be in a register carefully.

depends on register allocator

Simple Expressions

• Represent as simple tree
• assign virtual register to each operator
• emit code in postorder walk

Routines:

• base(str) - name of virtual register that contains base address for str.
• offset(str) - name of virtual register that contains offset of str
• newtemp() - return new virtual register name

Assumptions:

• tree represents correct precedence and associativity
• all operands are integers

int expr(Node *node)
{
    int result, t1, t2, t3;
    switch (node.type) {
        case PLUS:
            t1 = expr(node.left);
            t2 = expr(node.right);
            result = newtemp();
            emit(ADD, result, t1, t2);
            break;
        case ID:
            t1 = base(node.val);
            t2 = offset(node.val);
            t3 = newtemp();
            emit(ADD, t3, t1, t2);
            break;
        case NUM:
            result = newtemp();
            emit(LOADI, result, node.val);
            break;
    }
    return result;
}

Control Structures

Assignment

Strategy:

• Evaluate RHS to value
• Evaluate LHS to an address
  • if LHS is a register, move it
  • if LHS is an address, store it

Registers vs. Memory

• non-aliased scalars can go in registers
• aggregate or potentially aliased: put in memory

Aliased values can belong to multiple processes/threads, so the correct value of that variable must be accessible in memory.

Basic Blocks

Defined as:

• A sequence of straight line code
• If the first instruction executes, they all execute
• A maximal sequence of instructions without branches/jumps
• A label starts a new basic block.

Early optimization work focused on basic blocks.

• common subexpression elimination
• constant folding (realizing that int i = 3 + 7; is the same as int i = 10;
• "optimal" code generation
• list scheduling

If-Then-Else

1. evaluate expression to true or false
2. If true, fall through to then part; branch around else part
3. if false, jump to else part; fall through to next statement

Example:

    r1 = expr
    if not(r1) br L1
    ... then section ...
    br L2
L1:
    ... else section ...
L2:
    ... following statement ...

While/Do Loops

1. evaluate control expression
2. if false, branch beyond end of loop
3. if true, fall through into loop body
4. At end, re-evaluate control expression
5. If true, branch to top of loop body
6. If false, fall through

Example:

    r1 = expr
    if not(r1) br L2
L1:
    ... loop body ...
    r1 = expr
    if r1 br L1
L2:
    ... following statement ...

Since the test is at the end, the simple loop is one block

Case Statements

1. evaluate control expression
2. branch to selected case
3. execute its code
4. branch to the following statement

How to find the right case?

1. linear search (few cases)
2. binary search (sparse cases)
3. jump table (dense cases)

Procedure Calls

Prolog

1. save registers
2. extend basic frame
3. find static data area (if needed)
4. initialize locals

Start of call:

1. allocate child's frame
2. evaluate and store params
3. store frame pointer and return address
4. set frame pointer for child
5. jump to child

Post-Call code:

1. copy return value
2. restore params (if needed)
3. free up child's frame

Epilog Code

1. store return value
2. unextend basic frame
3. restore registers
4. restore parent's frame pointer
5. jump to return address.