Compilation:
A Retrospective
CS 671
April 29, 2008
What You’ve Learned This Semester
What happens when you compile your code
High-Level
Programming
Languages
Compiler
Machine
Code
Error Messages
Theory of compilers
– Internal challenges and solutions: widely-used algorithms
– Available tools and their other applications
– Traditional and modern challenges
1
CS 671 – Spring 2008
An Interface to High-Level Languages
High-Level
Programming
Languages
Compiler
Machine
Code
Programmers write in high-level languages
• Increases productivity
• Easier to maintain/debug
• More portable
HLLs also protect the programmer from lowlevel details
• Registers and caches – the register keyword
• Instruction selection
• Instruction-level parallelism
The catch: HLLs are less efficient
2
CS 671 – Spring 2008
An Interface to Computer Architectures
High-Level
Programming
Languages
Compiler
Machine
Code
Parallelism
• Instruction level
•
– multiple operations at once; minimize dependences
Processor level
– multiple threads at once; minimize synchronization
Memory Hierarchies
• Register allocation (only portion explicitly managed in SW)
• Code and data layout (helps the hardware cache manager)
Designs driven by how well compilers can
leverage new features!
3
CS 671 – Spring 2008
Simplified Compiler Structure
Source code
(character stream)
if (b==0) a = b;
Lexical Analysis
Token stream
Parsing
Front End
Machine independent
Abstract syntax tree
Intermediate Code Generation
Intermediate code
Code Optimization
Assembly code
(character stream)
CMP CX, 0
CMOVZ CX, DX
4
IR
Code Generation
CS 671 – Spring 2008
Back End
Machine dependent
Building a Lexer
Specification
NFA for each RE
Giant NFA
“if”
“while”
[a-zA-Z][a-zA-Z0-9]*
[0-9][0-9]*
(
)
Giant DFA
5
CS 671 – Spring 2008
Table-driven code
High Level View
source code
Scanner
tokens
Compile time
Design time
specification
Scanner
Generator
Regular expressions = specification
Finite automata = implementation
Every regex has a FSA that recognizes its
language
6
CS 671 – Spring 2008
Lex: A Lexical Analyzer Generator
• Lex produces a C program from a lexical specification
• http://www.epaperpress.com/lexandyacc/index.html
%%
DIGITS [0-9]+
ALPHA [A-Za-z]
CHARACTER {ALPHA}|_
IDENTIFIER {ALPHA}({CHARACTER}|{DIGITS})*
%%
if
{return IF; }
{IDENTIFIER}
{return ID; }
{DIGITS}
{return NUM; }
([0-9]+”.”[0-9]*)|([0-9]*”.”[0-9]+) {return REAL; }
.
{error(); }
7
CS 671 – Spring 2008
Phases of a Compiler
Source code
(character stream)
if (b==0) a = b;
Lexical Analysis
Token stream
Parsing
Front End
Machine independent
Abstract syntax tree
Intermediate Code Generation
Intermediate code
Code Optimization
Assembly code
(character stream)
CMP CX, 0
CMOVZ CX, DX
8
IR
Code Generation
CS 671 – Spring 2008
Back End
Machine dependent
Parsing – Syntax Analysis
• Convert a linear structure – sequence of tokens –
to a hierarchical tree-like structure – an AST
• The parser imposes the syntax rules of the
language
• Work should be linear in the size of the input 
type consistency cannot be checked in this phase
•Deterministic context free languages for the basis
• Bison and yacc allow a user to construct parsers
from CFG specifications
9
CS 671 – Spring 2008
Context-Free Grammar Terminology
• Terminals
– Token or ε
S  (S) S
• Non-terminals
– Syntactic variables
Sε
• Start symbol
– A special nonterminal is designated (S)
• Productions
– Specify how non-terminals may be expanded to
form strings
– LHS: single non-terminal, RHS: string of terminals
or non-terminals
• Vertical bar is shorthand for multiple productions
10
CS 671 – Spring 2008
Shift-Reduce Parsing
Bottom-up parsing uses two kinds of actions:
Shift and Reduce
Shift: Move I one place to the right
• Shifts a terminal to the left string
E + (I int )  E + (int I )
Reduce: Apply an inverse production at the right
end of the left string
• If E  E + ( E ) is a production, then
E + (E + ( E ) I )  E +(E I )
11
CS 671 – Spring 2008
Shift-Reduce Parsing Table
terminal symbols non-terminal symbols
state
Action table
next
actions
next state
on
reduction
1. shift and goto state n
2. reduce using X → γ
– pop symbols γ off stack
– using state label of top (end) of stack, look up X
in goto table and goto that state
• DFA + stack = push-down automaton (PDA)
12
CS 671 – Spring 2008
Parsing Table
(
1
s3
2
S→id
3
s3
)
id
,
$
s2
S→id
S→id
S
g4
S→id
S→id
s2
g7
4
accep
t
5
s6
s8
6 S→(L) S→(L) S→(L) S→(L) S→(L)
7
L→S
8
s3
L→S
L→S
L→S
L→S
s2
9 L→L,S L→L,S L→L,S L→L,S L→L,S
13
L
CS 671 – Spring 2008
g9
g5
Yacc / Bison
•Yet Another Compiler Compiler
•Automatically constructs an LALR(1) parsing
table from a set of grammar rules
•Yacc/Bison specification:
file.y
parser declarations
%%
grammar rules
%%
auxiliary code
14
bison –vd file.y
-oryacc –vd file.y
CS 671 – Spring 2008
y.tab.c
y.tab.h
y.output
Parsing - Semantic Analysis
• Calculates the program’s “meaning”
• Rules of the language are checked (variable
declaration, type checking)
• Type checking also needed for code generation
(code gen for a + b depends on the type of a and b)
15
CS 671 – Spring 2008
Symbol Table Implementation
Can consist of:
• a hash table for all names, and
•a stack to keep track of scope
a \
a
x
y \
X
x \
x
16
CS 671 – Spring 2008
y
y
x
x
Scope
change
Typical Semantic Errors
Traverse the AST created by the parser to find:
•Multiple declarations: a variable should be
declared (in the same scope) at most once
•Undeclared variable: a variable should not be used
before being declared
•Type mismatch: type of the left-hand side of an
assignment should match the type of the right-hand
side
•Wrong arguments: methods should be called with
the right number and types of arguments
17
CS 671 – Spring 2008
Stack Frames
Activation record or stack frame stores:
• local vars
• parameters
• return address
• temporaries
• (…etc)
fp
(Frame size not known until
late in the compilation process)
sp
18
CS 671 – Spring 2008
Arg n
…
Arg 2
Arg 1
Static link
Local vars
Ret address
Temporaries
Saved regs
Arg m
…
Arg 1
Static link
previous
frame
current
frame
next
frame
Phases of a Compiler
Source code
(character stream)
if (b==0) a = b;
Lexical Analysis
Token stream
Parsing
Front End
Machine independent
Abstract syntax tree
Intermediate Code Generation
Intermediate code
Code Optimization
Assembly code
(character stream)
CMP CX, 0
CMOVZ CX, DX
19
IR
Code Generation
CS 671 – Spring 2008
Back End
Machine dependent
Intermediate Code Generation
• Makes it easy to port compiler to other architectures
– e.g., Pentium to MIPS
• Can also be the basis for interpreters
– such as in Java
• Enables optimizations that are not machine specific
optimize
AST
IR
x86
PowerPC
Alpha
20
CS 671 – Spring 2008
Phases of a Compiler
Source program
Lexical analyzer
Syntax analyzer
Semantic analyzer
Intermediate
code generator
Intermediate Code Optimization
• Constant propagation, dead
code elimination, common subexpression elimination, strength
reduction, etc.
• Based on dataflow analysis –
properties that are independent of
execution paths
Code optimizer
Code generator
Target program
21
CS 671 – Spring 2008
Analysis and Transformation
Most optimizations require some global
understanding of program flow
• Moving, removing, rearranging instructions
Achieve understanding by discovering the
control flow of the procedure
• What blocks follow/are reachable from other blocks
• Where loops exist (focus optimization efforts)
• We call this Control-Flow Analysis
Connect definitions and uses of variables
• We call this Data-Flow Analysis
22
CS 671 – Spring 2008
Data-Flow Analysis
Properties:
• either a forward analysis (out as function of in) or
• a backward analysis (in as a function of out).
• either an “along some path” problem or
• an “along all paths” problem.
out[I] = ( in[I] – kill[I] )  gen[I]
in[B] =
 out[B’]
B’  succ(B)
23
CS 671 – Spring 2008
Static Single Assignment Form
B1
B2
if (…)
X5
B3
B4
YX
X3
B2
X0  5
B4
Before SSA
24
if (…)
B1
B3
X2  (X0, X1)
Y0  X2
After SSA
CS 671 – Spring 2008
X1  3
Optimizations
What are they?
• Code transformations
• Improve some metric
Metrics
• Performance: time, instructions, cycles
• Space: Reduce memory usage
• Code Size
• Energy
25
CS 671 – Spring 2008
Optimizations
High-level
IR
Low-level
IR
26
Inlining
Constant folding
Algebraic simplification
Constant propagation
Dead code elimination
Loop-invariant code motion
Common sub-expression elimination
Strength reduction
Branch prediction/optimization
Register allocation
Loop unrolling
Cache optimization
CS 671 – Spring 2008
Scope of Optimization
Local
(or single block)
• Confined to straight-line code
• Simplest to analyze
Intraprocedural
(or global)
• Consider the whole procedure
Interprocedural
(or whole program)
• Consider the whole program
27
CS 671 – Spring 2008
Phases of a Compiler
Source program
Native Code Generation
Lexical analyzer
• Intermediate code is translated into
native code
Syntax analyzer
• Register allocation, instruction
selection
Semantic analyzer
Intermediate
code generator
Code optimizer
Native Code Optimization
• Peephole optimizations – small window
is optimized at a time
Code generator
Target program
28
CS 671 – Spring 2008
Instruction Tiling
x = x + 1;
MOVE t2
MEM
t1 +
+
FP
MEM
x
+
FP
29
1
mov t1, [bp+x]
mov t2, t1
add t2, 1
mov [bp+x], t2
x
CS 671 – Spring 2008
Register Allocation
Live Range
s1
s2
s3
s4
s5
s6






2
4
s1
s1
s1
s4
Interference
s1 s2 s3 s4 s5 s6
+
+
*
*
s2
1
s2
2
S1
S4
S5
S3
S2
S6
Result
r1  2
Graph Coloring
30
S1
S4
S5
S3
S2
S6
r1  green
r2  blue
r3  pink
CS 671 – Spring 2008
r2
r3
r3
r1
r2





4
r1
r1
r1
r3
+
+
*
*
r2
1
r2
2
Instruction Scheduling
•Create a DAG of dependences
•Determine priority
•Schedule instructions with
– Ready operands
– Highest priority
•Heuristics: If multiple
possibilities, fall back on other
priority functions
– Height, slack, register usage, etc.
5
1m
2m
3
4m
6
7
8
10
31
CS 671 – Spring 2008
9m
Modern Topics!
• Alternatives to the static compilation model
• Compiling for the Core2
• Compiling for GPUs
• Compiling for power and temperature
• Compiling for parallelism
32
CS 671 – Spring 2008
Alternatives to the Traditional Model
Static Compilation
All work is done “ahead-of-time”
Just-in-Time Compilation
Postpone some compilation tasks
Multiversioning and Dynamic Feedback
Include multiple options in binary
Dynamic Binary Optimization
Traditional compilation model
Executables can adapt
33
CS 671 – Spring 2008
Just-in-Time Compilation
Compiler
High-Level
Programming
Languages
Front
End
Back
End
Machine
Code
Error Messages
Ship bytecodes (think IR) rather than binaries
• Binaries execute on machines
• Bytecodes execute on virtual machines
34
CS 671 – Spring 2008
Compiling for the Core Architecture
Netburst architecture: has trace cache with
decoded instructions
Core architecture: instructions are repeatedly
fetched and decoded
Problems:
• Code alignment! (Fetch, brpred effects)
4008c0
8b
4008d0
04
8d
A0
64
56
00
8b
34
8d
20
4a
50
00
44
01
C6
4008e0
42
8d
3c
06
41
83
C0
F6
01
F2
89
34
8d
40
7f
5c
4008f0
00
89
3c
8d
20
4a
50
00
44
89
04
8d
A0
64
56
00
400900
41
29
F8
44
29
C2
48
83
c1
01
48
81
F9
A0
86
01
400910
00
7c
Bb
20% Speedup!!!
35
44
CS 671 – Spring 2008
Compiling for GPUs
CPUs
•Lots of instructions
little data
– Out of order exec
– Branch prediction
•Reuse and locality
•Task parallel
•Needs OS
•Complex sync
•Latency machines
36
GPUs
•Few instructions lots
of data
– SIMD
– Hardware threading
•Little reuse
•Data parallel
•No OS
•Simple sync
•Throughput machines
CS 671 – Spring 2008
Bug Report
Graphics
Shadow acne
Compiler
Round off error
37
CS 671 – Spring 2008
38
CS 671 – Spring 2008
Shader Compiler (SC)
Developers ship games in byte code
– Each time a game starts the shader is compiled
Compiler is hidden in driver
– No user gets to set options or flags
Compiler updates with new driver (once a
month)
Compile done each time game is run
About ½ code is traditional compiler, all the
usual stuff
• Strange features: SC fights MS compiler
39
CS 671 – Spring 2008
Power-Aware Computing
40
CS 671 – Spring 2008
Power Issues in Microprocessors
Capacitive (Dynamic) Power
Static (Leakage) Power
Vdd
V IN
Vin
V OUT
Vout
ISub
I G a te
CL
CL
Di/Dt (Vdd/Gnd Bounce)
Voltage (V)
Current (A)
Temperature
41
CS 671 – Spring 2008
20 cycles
Minimum Voltage
Code Optimizations for Low Power
Reorder instructions to reduce switching effect
at functional units and I/O buses
Operand swapping
• Swap the operands at the input of multiplier
• Result is unaltered, but power changes significantly!
Other standard compiler optimizations
• Software pipelining, dead code elimination,
redundancy elimination
Use processor-specific instruction styles
• on ARM the default int type is ~ 20% more efficient
than char or short (sign/zero extension)
42
CS 671 – Spring 2008
Code Optimization of Parallel Programs
• Crises lead to paradigm shifts
• Most of our algorithms break down in light of
parallelism!
• Many “band aids” exist, need a unified solution
• Need a way to represent synchronization,
parallelism in our dataflow analyses
• Need a new IR … PIR
– CFG + PDG = PPG
• Can then update our dataflow analyses
43
CS 671 – Spring 2008
The Big Picture
We now know:
– All of the components of a compiler
– What needs to be done statically vs. dynamically
– The potential impact of language or architecture
changes
– Why Java moved the “back-end” to run time
– What compiler researchers are working on in
2008!
44
CS 671 – Spring 2008
Descargar

CS 471 - University of Virginia