Scribd Logo
Upload

Welcome to Scribd!

  • 27 views

    Compiler Construction - Lecture 03

    Uploaded by

    Nusrat Ullah
    The document discusses the different stages in a compiler's back end: instruction selection maps intermediate representations (IR) to target machine instructions, register allocation assigns values to registers, and instruction scheduling orders instructions to avoid stalls and fully utilize hardware. Optimal solutions for register allocation and instruction scheduling are NP-complete problems.

    Copyright:

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

    Compiler Construction - Lecture 03

    Uploaded by

    Nusrat Ullah
    27 views21 pages
    The document discusses the different stages in a compiler's back end: instruction selection maps intermediate representations (IR) to target machine instructions, register allocation assigns values to registers, and instruction scheduling orders instructions to avoid stalls and fully utilize hardware. Optimal solutions for register allocation and instruction scheduling are NP-complete problems.

    Original Description:

    hfdss gff

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses the different stages in a compiler's back end: instruction selection maps intermediate representations (IR) to target machine instructions, register allocation assigns values to registers, and instruction scheduling orders instructions to avoid stalls and fully utilize hardware. Optimal solutions for register allocation and instruction scheduling are NP-complete problems.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    27 views21 pages

    Compiler Construction - Lecture 03

    Uploaded by

    Nusrat Ullah
    The document discusses the different stages in a compiler's back end: instruction selection maps intermediate representations (IR) to target machine instructions, register allocation assigns values to registers, and instruction scheduling orders instructions to avoid stalls and fully utilize hardware. Optimal solutions for register allocation and instruction scheduling are NP-complete problems.

    Copyright:

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

    Compiler

    Construction
    Lecture 3
    Syntax Tree
    goal

    x+2-y expr

    expr op term

    expr op term – <id,y>

    term + <number, 2>


    <id,x> 2
    Abstract Syntax Trees

    The parse tree contains a lot


    of unneeded information.
    Compilers often use an
    abstract syntax tree (AST).

    3
    Abstract Syntax Trees

    + <id,y>
    <id,x> <number,2>

    This is much more concise

    4
    Abstract Syntax Trees
    –

    + <id,y>
    <id,x> <number,2>

     AST summarizes grammatical structure without the details of derivation

    5
    Abstract Syntax Trees
    –

    + <id,y>
    <id,x> <number,2>

    ASTs are one kind of


    intermediate representation
    (IR) 6
    The Back End

    IR Instruction IR Register IR Instruction machine


    selection allocation scheduling code

    errors

    7
    The Back End

    Translate IR into target


    machine code.
    Choose machine (assembly)
    instructions to implement
    each IR operation

    8
    The Back End

    Ensure conformance with


    system interfaces
    Decide which values to keep
    in registers

    9
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Instruction Selection:
    Produce fast, compact code.

    10
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors
    Instruction Selection:
     Take advantage of target features such as addressing modes.

    11
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors
    Instruction Selection:
     Usually viewed as a pattern matching problem – dynamic programming.

    12
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Instruction Selection:
    Spurred by PDP-11 to VAX-11
    - CISC. 13
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Instruction Selection:
    RISC architecture simplified
    this problem. 14
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Register Allocation:
    Have each value in a register
    when it is used. 15
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Register Allocation:
    Manage a limited set of
    resources – register file. 16
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors
    Register Allocation:
     Can change instruction choices and insert LOADs and STOREs.

    17
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Register Allocation:
    Optimal register allocation is
    NP-Complete. 18
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Instruction Scheduling:
    Avoid hardware stalls and
    interlocks. 19
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors

    Instruction Scheduling:
    Use all functional units
    productively. 20
    The Back End
    IR Instruction IR Register IR Instruction machine
    selection allocation scheduling code

    errors
    Instruction Scheduling:
     Optimal scheduling is
    NP-Complete in nearly all cases.

    21

    You might also like