文档介绍:1
CS piler Construction
Lecture 1
Introduction
2
Instructor Information
Rajiv Gupta
Office: Room 408
E-mail: ******@
Tel: (951) 827-2558
Office Hours: T, Th 1-2 pm
TA: Min Feng
Office: Engg II Room 463
E-mail: ******@
Tel: (951) 827-2001
Office Hours: M,W 1:30-2:30pm
3
Course Requirements
Grading:
Test 1: 30 points
Test 2: 30 points
Project: 25 points
Homeworks: 15 points
4
Course Overview
Three Address Intermediate Code
Arithmetic Operations
dst = src1 op src2
where op in {+, -, *, /, %}
Relational Operators
dst = src1 relop src2
where relop in {<,<=,!=,==,>=,>}
Logical Operations
dst = src lop src2, where lop in {||,&&}
dst = ! src
5
Three Address Intermediate Code
Array Accesses
dst = src[index]
dst[index] = src
Pointers
dst = & src
* dst = src
Copy Assignment
dst = src
6
Three Address Intermediate Code
Branches
unconditional:
goto label
conditional:
if predicate goto label
or
if src1 relop src2 goto label
labels:
declared or instruction numbers
7
Examples
8
See handouts.
9
Control Flow Graph (CFG)
Intermediate Code can be transformed from linear representation to a directed graph form called Control flow Graph:
Nodes – Basic Blocks: Basic block consists of a sequence of intermediate code statements that must be entered at the top and exited at the bottom, . once the block is entered, all intermediate code statements will be executed.
Edges: directed edges connect basic blocks according to control flow.
CFG representation will be used for program analysis and optimization.
CFG Construction Algorithm
Identify Leaders: the first instruction in a basic block is a leader.
First instruction in the program
Target instruction of a conditional or unconditional branch
Instruction immediately following a conditional or unconditional branch
Construct Basic Blocks:
Starting from the leader append subsequent instructions up to, but not including, the next leader or the end of the program
10