Scribd Logo
Upload

Welcome to Scribd!

  • 30 views

    Code Generation I: Compiler Construction

    Uploaded by

    Muhammad Rohaan Rehan
    This document provides an overview of code generation challenges and tasks. It discusses instruction selection, register allocation and assignment, and instruction ordering as main tasks of a code generator. It also covers design issues such as input and target representations, and approaches to instruction selection, register allocation, and evaluation order. Examples are provided to illustrate generating code for a simple target machine architecture.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Code Generation I: Compiler Construction

    Uploaded by

    Muhammad Rohaan Rehan
    30 views28 pages
    This document provides an overview of code generation challenges and tasks. It discusses instruction selection, register allocation and assignment, and instruction ordering as main tasks of a code generator. It also covers design issues such as input and target representations, and approaches to instruction selection, register allocation, and evaluation order. Examples are provided to illustrate generating code for a simple target machine architecture.

    Original Title

    lecture12

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides an overview of code generation challenges and tasks. It discusses instruction selection, register allocation and assignment, and instruction ordering as main tasks of a code generator. It also covers design issues such as input and target representations, and approaches to instruction selection, register allocation, and evaluation order. Examples are provided to illustrate generating code for a simple target machine architecture.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    30 views28 pages

    Code Generation I: Compiler Construction

    Uploaded by

    Muhammad Rohaan Rehan
    This document provides an overview of code generation challenges and tasks. It discusses instruction selection, register allocation and assignment, and instruction ordering as main tasks of a code generator. It also covers design issues such as input and target representations, and approaches to instruction selection, register allocation, and evaluation order. Examples are provided to illustrate generating code for a simple target machine architecture.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 28

    G22.

    2130-001
    Compiler Construction
    Lecture 12:
    Code Generation I

    Mohamed Zahran (aka Z)


    [email protected]
    semantically
    equivalent

    +
    symbol
    table

    Requirements Challenges
    • Preserve semantic • Problem of generating
    meaning of source optimal target
    program program is
    • Make effective use of undecidable
    available resources of • Many subprogroblems
    target machine encountered in code
    • Code generator itself generation are
    must run efficiently computationally
    intractable
    Main Tasks of Code Generator
    • Instruction selection: choosing
    appropriate target-machine instructions
    to implement the IR statements
    • Registers allocation and assignment:
    deciding what values to keep in which
    registers
    • Instruction ordering: deciding in what
    order to schedule the execution of
    instructions
    Design Issues of
    a Code Generator
    Input
    – three-address presentations (quadruples,
    triples, …)
    – Virtual machine presentations (bytecode,
    stack-machine, …)
    – Linear presentation (postfix, …)
    – Graphical presentation (syntax trees,
    DAGs,…)
    Design Issues of
    a Code Generator
    Target program
    – Instruction set architecture (RISC, CISC)
    – Producing absolute machine-language
    program
    – Producing relocatable machine-language
    program
    – Producing assembly language programs
    Design Issues of
    a Code Generator
    Instruction Selection
    The complexity of mapping IR program
    into code-sequence for target machine
    depends on:
    – Level of IR (high-level or low-level)
    – Nature of instruction set (data type
    support)
    – Desired quality of generated code (speed
    and size)
    Design Issues of
    a Code Generator
    Register Allocation
    • Selecting the set of variables that will
    reside in registers at each point in the
    program
    Register Assignment
    • Picking the specific register that a
    variable will reside in
    Design Issues of
    a Code Generator
    Evaluation Order
    – Selecting the order in which computations
    are performed
    – Affects the efficiency of the target code
    – Picking a best order is NP-complete
    – Some orders require fewer registers than
    others
    Simple Target-Machine
    • Load/store operations
    – LD dst, addr
    – ST x, r
    • Computation operations
    – OP dst, src1, src2
    • Jump operations
    – BR L
    • Conditional jumps
    – Bcond r, L
    • Byte addressable
    • n registers: R0, R1, … Rn-1
    Simple Target-Machine
    • Addressing modes
    – variable name
    – a(r) means contents(a + contents(r))
    – *a(r) means:
    contents(contents(a + contents(r)))
    – immediate: #constant (e.g. LD R1, #100)
    Simple Target-Machine
    Cost
    • cost of an instruction = 1 + cost of
    operands
    • cost of register operand = 0
    • cost involving memory and constants = 1
    • cost of a program = sum of instruction
    costs
    Examples
    X=Y-Z

    b = a[i]
    (8-byte elements)

    x = *p
    More Examples
    • a[j] = c
    • *p = y
    • if X<Y goto L
    Generating Code for
    Handling the Stack
    Size and layout of activation records are
    determined by the code generator using
    information from symbol table
    saves return address constants giving address
    at beginning of activation of beginning of activation record of callee
    record of callee

    CALL callee
    transfers control to
    target code of
    procedure callee

    RETURN
    Basic Blocks and Flow Graphs
    • Graph presentation of intermediate code
    • Nodes of the graph are called basic blocks
    • Edges indicate which block follows which
    other block.
    • The graph is useful for doing better job in:
    – Register allocation
    – Instruction selection
    Basic Blocks
    • Definition: maximal sequence of
    consecutive instructions such that
    – Flow of control can only enter the basic
    block from the first instruction
    – Control leaves the block only at the last
    instruction
    • Each instruction is assigned to exactly
    one basic block
    Fist we determine leader instructions:
    First we determine leader instructions:
    Fist we determine leader instructions:

    Basic block starts with a leader instruction


    and stops before the following leader instruction.
    DAG Representation of
    Basic Blocks
    • Leaves for initial values of variables
    (we may not know the values so we use a0,
    b0, …)
    • Node for each expression
    • Node label is the expression operation
    • Next to the node we put the variable(s)
    for which the node produced last
    definition
    • Children of a node consist of nodes
    producing last definition of operands
    Finding Local Common
    Subexpressions
    Dead Code Elimination
    From the basic block DAG:
    • Remove any root node that has no live
    variables
    • Repeat until no nodes can be removed
    So
    • Skim: 8.3.3, 8.5.4, 8.5.5, 8.5.6, and 8.5.7
    • Read: 8.1 -> 8.5

    You might also like