Compiler Construction Flashcards
1
Q
Left recursion
A
Top-down parsers cannot handle left-recursion in a grammar
-> transform the grammar to fix this cf sl. 40/41
2
Q
Context-free grammars
A
s
syntax is context-free
semantics is context-sensitive
3
Q
intermediate representation
A
aka parse tree
-> a notation that is not tied to any particular source language or target machine
Choosing the “right” IR is not an easy task: source code is too
high level for performing many analyses, and machine code is
too low level. Sometimes an AST is used (i.e., closer to source
code), and sometimes a special kind of abstract instruction set
(i.e., closer to machine code).
4
Q
derivation
A
s
5
Q
left-recursion
A
s
6
Q
Bytecode
A
The “machine-code” of the virtual machine
7
Q
What is the difference between a compiler and an
interpreter?
A
s
8
Q
What are important qualities of compilers?
A
s
9
Q
Why are compilers commonly split into multiple passes?
A
s
10
Q
What are the typical responsibilities of the different parts of a modern compiler?
A
s
11
Q
How are context-free grammars specified?
A
s
12
Q
What is “abstract” about an abstract syntax tree?
A
s
13
Q
What is intermediate representation and what is it for?
A
s
14
Q
Why is optimization a separate activity?
A
s
15
Q
Is Java compiled or interpreted? What about Smalltalk?
Ruby? PHP? Are you sure?
A
s
16
Q
What are the key differences between modern compilers and compilers written in the 1970s?
A
s
17
Q
Why is it hard for compilers to generate good error
messages?
A
s
18
Q
What is “context-free” about a context-free grammar?
A
s
19
Q
Traditional two pass compiler
A
A classical compiler consists of a front end that parses the source
code into an intermediate representation, and a back end that
generates executable code.
20
Q
front end
A
parses the source code into an intermediate representation
- the front end should deal with all things to do with the language and source code
- consists of scanner (tokens) and parser (IR)
21
Q
back end
A
generates executable code
- the back end should deal with all things to do with the
target architecture
- translate IR into target machine code
22
Q
scanner
A
is responsible for converting the source code into a stream of tokens of the source language
23
Q
parser
A
is responsible for recognizing structure in the stream of tokens - job of the parser is to recognize structure in the stream of tokens produced by the scanner - Typically it builds a parse tree representing this structure, but it may also produce another kind of IR (intermediate representation) more suitable for the backend
24
Q
IR
A
e.g. parse tree
25
context-free?
“context-free” because rules for nonterminals
can be written without regard for the context in which
they appear
26
context-sensitive
context sensitive: you need the context of a code to validate it
context free: you do not need the context of a code to validate it
27
unambiguous grammar
it always produces a unique parse for a given valid input.
28
the parse and the parse tree
The parse is the sequence of productions needed to parse the input.
The parse tree is a structure representing this derivation
29
LL(1), LR(1)
"sweet spots": allow interesting languages to be specified, but can also be parsed efficiently
30
syntax analysis
An AST is usually the result of the syntax analysis phase of a compiler
lexical analysis -> syntax analysis
31
Leftmost vs rightmost derivation
replace the leftmost non-terminal at each step
vs
replace the rightmost non-terminal at each step
32
table-driven parser
- Our recursive descent parser encodes state information in its call stack.
- Using recursive procedure calls to implement a stack
abstraction may not be particularly efficient
- This suggests other implementation methods:
—explicit stack, hand-coded parser
—stack-based, table-driven parser
33
constant expression propagation and folding
evaluate and propagate constant expressions at compile time
Constant propagation entails recognizing that certain “variables” actually have constant values, and then propagating these constants to expressions where they are used. Later we will see SSA is ideal to analyze this.
constant folding:
> Evaluate constant expressions at compile time
> Only possible when side-effect freeness guaranteed
34
ambiguous grammar
If a grammar has more than one derivation for a single
| sentential form
35
Top-down parser (LL)
- starts at the root of derivation tree and fills in
- picks a production and tries to match the input
- may require backtracking
- some grammars are backtrack-free (predictive)
- uses leftmost derivation
- can be either hand-written or generated
- cannot handle left-recursion in a grammar
-> Since a parser does not just parse, but must also produce a suitable IR, we must decorate the grammar with additional actions that the generated parser will take
36
Bottom-up parser (LR)
- starts at the leaves and fills in
- starts in a state valid for legal first tokens
- as input is consumed, changes state to encode possibilities (recognize valid prefixes)
- uses a stack to store both state and sentential forms
- uses rightmost derivation
- are normally built by parser generators
Reading in reverse, we have a rightmost derivation, first replacing
S, then B, A and A again. 9
37
parser generators
- build bottom-up parsers
38
dead code elimination
eliminate code that can never be
| executed
39
left-recursion
```
If the parser makes the wrong choices, expansion doesn’t terminate!
-> solve using right recursion:
E -> E + T
E -> T
rewrite as:
E -> T E'
E' -> + T E'
E' ->
```
40
look-ahead
top-down parsers may need to backtrack when they select the wrong production
- large subclasses of CFGs can be parsed with limited lookahead
- Among the interesting subclasses are:
LL(1): Left to right scan, Left-most derivation, 1-token look-ahead
LR(1): Left to right scan, Right-most derivation, 1-token look-ahead
41
recursive descent / predictive parsing
basic idea: For any two productions A → α | β, we would like a distinct way of choosing the
correct production to expand.
Whenever two productions A → α and A → β both appear in the grammar, we would like:
FIRST(α) ∩ FIRST(β) = ∅
This would allow the parser to make a correct choice with a look-ahead of only one symbol!
=> this type of parsing works only on grammars where the first terminal symbol of each subexpression provides enough information to choose which production to use (iff FIRST property can be established!).
What if a grammar does not have this property?
-> left factoring
42
left factoring
sometimes we can transform a grammar in order to have this property (FIRST(α) ∩ FIRST(β) = ∅):
- For each non-terminal A find the longest prefix α common to two or more of its alternatives
- if α ≠ ε then replace all of the A productions
A → αβ1 | αβ2 | … | αβn
with
A → α A´
A´ → β1 | β2 | … | βn
where A´ is fresh
- Repeat until no two alternatives for a single non-terminal have a common prefix.
-> we do this so that the token lookahead will be unambiguous! i.e. that selection requires only a single token look-ahead
43
lexical analyzer
The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code. If the lexical analyzer finds a token invalid, it generates an error. The lexical analyzer works closely with the syntax analyzer. It reads character streams from the source code, checks for legal tokens, and passes the data to the syntax analyzer when it demands.
44
FIRST(a)
FIRST(a) is the set of all terminal symbols that can begin any string derived from a
-> if two different productions have the same left-hand-side symbol X and their right-hand sides have overlapping FIRST sets, then the grammar cannot be parsed using predictive parsing.
45
construct a predictive / recursive-descent parser
p. 50/51
- create predictive parsing table with one production per entry (if > 1 production, predictive parsing will not work -> is ambiguous)
- > an ambiguous grammar will always lead to duplicate entries in a predictive parsing table
- > need to find an unambiguous grammar
- > grammars whose predictive parsing tables contain no duplicate entries are called LL(1) = left-to-right prase, leftmost-derivation, 1-symbol lookahead
- > a recursive-descent parser does its job just by looking at the next token of the input, never looking more than one token ahead
... FIRST property
46
LL(k)
generalize the notion of FIRST sets to describe the first k tokens of a string, and make an LL(k) parsing table whose rows are the nonterminals and columns are every sequence of k terminals (rarely done -> tables get large!)
47
NFA -> DFA
Any NFA can be converted into a DFA, by simulating sets of simultaneous states.
Since a DFA must always be in a unique state, the states of the DFA must be all possible subsets of the NFA states.
48
NFA to DFA using the subset construction
s
49
Non-recursive predictive parsing
- use parse table
| -
50
DFA Minimization algorithm
s
51
LL(1) parse table
s
52
Properties of LL(1) grammars
- No left-recursive grammar is LL(1)
- No ambiguous grammar is LL(1)
- Some languages have no LL(1) grammar
- An ε–free grammar where each alternative expansion for A begins with a distinct terminal is a simple LL(1) grammar
53
What are the key responsibilities of a scanner?
s
54
Bottom-up parsing
Goal:
- Given an input string w and a grammar G, construct a parse tree by starting at the leaves and working to the root.
- We parse bottom-up, replacing terms by non-terminals!
the question is always whether to shift or reduce!
55
What is a regular language?
s
56
handle
A handle of a right-sentential form γ is a production A → β and a position in γ where β may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation of γ
—Suppose: S ⇒* αAw ⇒ αβw
—Then A → β in the position following α is a handle of αβw
-> NB: Because γ is a right-sentential form, the substring to the right of a handle contains only terminal symbols.
57
How can you generate a DFA recognizer from a regular
| expression?
by a scanner generator
58
Why aren’t regular languages expressive enough for
| parsing?
s
59
handle-pruning, bottom-up parser
shift-reduce parser
Shift-reduce parsers use a stack and an input buffer
1. initialize stack with $
2. Repeat until the top of the stack is the goal symbol and the input token is $:
a) Find the handle.
If we don’t have a handle on top of the stack, shift (push) an input symbol onto the stack
b) Prune the handle.
If we have a handle A → β on the stack, reduce
I. Pop |β| symbols off the stack
II. Push A onto the stack
A shift-reduce parser has just four canonical actions:
shift, reduce, accept, error
60
left-to-right-scan?
| right-to-left-scan?
s
61
Scanning vs. parsing
...
| CFGs are used to impose structure!!!
62
lexical analysis
1. Maps sequences of characters to tokens
2. Eliminates white space (tabs, blanks, comments etc.)
- > happens within the scanner
- > The string value of a token is a lexeme
63
CFG / parsing
CFGs are used to impose structure!!!
- For practical purposes it is important that a grammar
be unambiguous, i.e., that it always produces a unique parse for a given valid input
- Although parsers read their input Left to Right (the first “L” in most of these categories), they may work either top-down — producing a leftmost derivation — or bottom-up — producing a rightmost derivation.
- The process of discovering a derivation is called parsing.
64
left recursion vs right recursion
pro-contra?
Rule of thumb:
—right recursion for top-down parsers
—left recursion for bottom-up parsers
65
Leftmost derivation
replace the leftmost non-terminal at each step
| - corresponds to top-down parsing, and is especially well-suited to recursive descent parsers
66
Rightmost derivation
replace the rightmost non-terminal at each
step
- is produced bottom-up, and is better-suited to table-driven parsing
67
review: LR(k):
must be able to recognize the occurrence of the right hand side of a production after having seen all that is derived from that right hand side with k symbols of look-ahead.
LR dilemma: pick A → b or B → b ? (how to reduce?)
68
Resolving ambiguity
eliminate by rearranging the grammar
69
Visitor Pattern
Intent: Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.
- > A visitor gathers related operations
- > Visitor makes adding new operations easy (write new visitor)
- > Visitor can break encapsulation
70
Java Tree Builder (JTB)
- front-end for javacc
- supports the building of syntax trees that can be traversed using visitors.
- transforms a bare JavaCC grammar into three
components:
1) a JavaCC grammar with embedded Java code for building a syntax tree
2) one class for every form of syntax tree node
3) a default visitor which can do a depth-first traversal of a syntax tree
71
Why use intermediate representations?
—break compiler into manageable pieces
—isolates back end from front end
—different languages can share IR and back end
- Enables machine-independent optimization -> general techniques, multiple passes
72
IR types
- Abstract syntax trees (AST)
- Linear operator form of tree (e.g., postfix notation)
- Directed acyclic graphs (DAG)
- Control flow graphs (CFG)
- Program dependence graphs (PDG)
- Static single assignment form (SSA)
- 3-address code
- Hybrid combinations
73
lookahead
to decide which production rule to apply at any point without backtracking
74
Abstract syntax tree
An AST is a parse tree with nodes for most non-terminals removed.
-> Since the program is already parsed, non-terminals needed to establish precedence and associativity can be collapsed!
Remember: Concrete syntax trees, or parse trees, show all of the intermediate non-terminals needed to produce an unambiguous grammar. An abstract syntax tree collapses these to offer a much simpler version of the parse tree.
75
parsing
the process of discovering a derivation
76
Leftmost vs rightmost derivation
replace the leftmost non-terminal at each step
vs
replace the rightmost non-terminal at each step
77
3-address code
Statements take the form: x = y op z
Advantages:
—compact form
—names for intermediate values
78
Static Single Assignment Form (SSA)
Goal: simplify procedure-global optimizations
Program is in SSA form if every variable is only assigned once
- is only used for static analysis and optimization. It will
disappear when we generate the final executable code
- SSA is normally used for control-flow graphs (CFG)c
79
The Φ-Function
- Φ-functions are always at the beginning of a basic block
| - Selects between values depending on control-flow
80
Minimal SSA
Two steps:
—Place Φ-functions
—Rename Variables
We want minimal amount of needed Φ
—Save memory
—Algorithms will work faster
81
Dominance Property of SSA
Dominance: node D dominates node N if every path from the
start node to N goes through D
(“strictly dominates”: D ≠ N)
-Definition dominates use
-> Dominance can be used to efficiently build SSA
82
Dominance Frontier
DF(D) = the set of all nodes N such that D dominates an immediate predecessor of N but does not strictly
dominate N.
application of DF: Φ-Functions are placed in all basic blocks of the
Dominance Frontier
83
parser generators
s
84
top-down parsing
A top-down parser starts with the root of the parse tree, labeled with the start or goal symbol of the grammar.
85
SSA and Register Allocation
- Idea: remove Φ as late as possible
- Variables in Φ-function never live at the same time!
- > Can be stored in the same register
- > Do register allocation on SSA!
So, don’t remove Φ functions before register allocation
86
look-ahead
top-down parsers may need to backtrack when they select the wrong production
- large subclasses of CFGs can be parsed with limited lookahead
- Among the interesting subclasses are:
LL(1): Left to right scan, Left-most derivation, 1-token look-ahead
LR(1): Left to right scan, Right-most derivation, 1-token look-ahead
87
predictive parsing
basic idea: For any two productions A → α | β, we would like a distinct way of choosing the
correct production to expand.
88
Lattices
A lattice is a partially ordered set with meet and join.
A partially ordered set is a set S and a binary relation ≤ such that
a ≤ a (reflexivity)
if a ≤ b and b ≤ a, then a = b (antisymmetry)
if a ≤ b and b ≤ c, then a ≤ c (transitivity)
A complete lattice is a lattice where every subset has a supremum and infimum
-> For static analysis, abstract interpretation is mostly performed over finite lattices
89
Dataflow analysis
Flow based analysis is a particular instance of abstract interpretation
90
Optimization
Performance: faster execution
Size: smaller executable, smaller memory footprint
Tradeoffs:
1) Performance vs. Size
2) Compilation speed and memory
Optimizations both in the optimizer and back-end!
- Back-end optimizations may focus on how the machine code is optimally generated
91
Optimizations in the Backend
> Register Allocation
> Instruction Selection
> Peep-hole Optimization
92
LL(k)
generalize the notion of FIRST sets to describe the first k tokens of a string, and make an LL(k) parsing table whose rows are the nonterminals and columns are every sequence of k terminals (rarely done -> tables get large!)
93
sentential form
is any string derivable from the start symbol
94
left-recursion elimination (after left factoring)
cf. 03 sl 56
95
Examples for Optimizations
```
> Constant Folding / Propagation
> Copy Propagation
> Algebraic Simplifications
> Strength Reduction
> Dead Code Elimination (Structure Simplifications)
> Loop Optimizations
> Partial Redundancy Elimination
> Code Inlining
```
96
FOLLOW(X)
is the set of terminals that can immediately follow X
i. e. t e FOLLOW(X) if there is any derivation containing Xt. This can occur if the derivation contains XYZt where Y and Z both derive epsilon
- > I.e., a non-terminal’s FOLLOW set specifies the tokens that can legally appear after it
- A terminal symbol has no FOLLOW set.
97
LL(1) parse table
s
98
Properties of LL(1) grammars
- No left-recursive grammar is LL(1)
- No ambiguous grammar is LL(1)
- Some languages have no LL(1) grammar
- An ε–free grammar where each alternative expansion for A begins with a distinct terminal is a simple LL(1) grammar
99
derivation vs parse
s
100
Bottom-up parsing
Goal:
- Given an input string w and a grammar G, construct a parse tree by starting at the leaves and working to the root.
- We parse bottom-up, replacing terms by non-terminals!
101
right-sentential form
s
102
handle
A handle of a right-sentential form γ is a production A → β and a position in γ where β may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation of γ
—Suppose: S ⇒* αAw ⇒ αβw
—Then A → β in the position following α is a handle of αβw
-> NB: Because γ is a right-sentential form, the substring to the right of a handle contains only terminal symbols.
103
Common Subexpression Elimination (CSE)
Common Subexpression:
—There is another occurrence of the expression whose evaluation always precedes this one
—operands remain unchanged
104
Loop Optimizations
Optimizing code in loops is important
—often executed, large payoff!
e.g.
—fission/fusion: split/combine loops to improve locality or reduce overhead
—scheduling: run parts in multiple processors
—unrolling: duplicate body several times in order to decrease the number of times the loop condition is tested
—loop-invariant code motion: move invariant code out of loop
105
handle-pruning, bottom-up parser
shift-reduce parser
Shift-reduce parsers use a stack and an input buffer
1. initialize stack with $
2. Repeat until the top of the stack is the goal symbol and the input token is $
106
Induction Variable Optimizations
Values of variables form an arithmetic progression
sl. 38
107
LR(k)
A grammar is LR(k) if k tokens of lookahead are enough to determine a unique parse:
108
Why study LR grammars?
- LR(1) grammars are used to construct LR(1) parsers
- everyone’s favorite parser
- virtually all context-free programming language constructs can be expressed in an LR(1) form
- LR grammars are the most general grammars parsable by a deterministic, bottom-up parser
- efficient parsers can be implemented for LR(1) grammars
- LR parsers detect an error as soon as possible in a left-to-right scan of the input
- LR grammars describe a proper superset of the languages recognized by predictive (i.e., LL) parsers
109
Optimization on SSA
e.g. three simple ones:
—Constant Propagation
-> SSA: Variables are assigned once
-> We know that we can replace all uses by the constant!
```
—Copy Propagation
-> SSA: for a statement x1 := y1
-> replace later uses of x1 with y1
-> as a “clean up” optimization after
other optimizations have been performed
```
—Simple Dead Code Elimination
- > SSA: Variable is live if the list of uses is not empty
- > Dead definitions can be deleted
110
Profile-guided optimization
Approach:
—Generate code,
—profile it in a typical scenario,
—then use that information to optimize it
Problem:
—usage scenarios can change in deployment, there is no way to react to that as profile is generated at compile time.
111
review: Recursive descent
A hand coded recursive descent parser directly encodes a grammar (typically an LL(1) grammar) into a series of mutually recursive procedures. It has most of the linguistic limitations of LL(1).
112
review: LL(k):
must be able to recognize the use of a production after seeing only the first k symbols of its right hand side.
LL dilemma: pick A → b or A → c ? (which rule to apply?)
113
Optimization: Iterative Process
- There is no general “right” order of optimizations
- One optimization generates new opportunities for a preceding one.
=> Optimization is an iterative process
Compile Time vs. Code Quality
114
JavaCC
- based on LL(k)
- Grammars are written in EBNF
- Transforms an EBNF grammar into an LL(k) parser
- Top-down parsing (recursive descent) with variable lookahead
-
115
Visitor Pattern
Intent: Represent an operation to be performed on the elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.
116
Runtime storage organization
study slides again + chap. 6
117
Procedure call conventions
s
118
Calls: Saving and restoring registers
CC-08 sl 24
usual approach:
caller’s registers: callee saves
Call includes bitmap of caller’s registers to be saved/restored. Best: saves fewer registers, compact call sequences
119
parse tree
the syntactic structure of the program
120
Abstract syntax tree
An AST is a parse tree with nodes for most non-terminals removed.
-> Since the program is already parsed, non-terminals needed to establish precedence and associativity can be collapsed!
121
Directed acyclic graph
A DAG is an AST with
unique, shared nodes
for each value.
122
Control flow graph
A CFG models transfer of control in a program
123
3-address code
Statements take the form: x = y op z
Advantages:
—compact form
—names for intermediate values
124
Static Single Assignment Form (SSA)
Goal: simplify procedure-global optimizations
Program is in SSA form if every variable is only assigned once
- is only used for static analysis and optimization. It will
disappear when we generate the final executable code
125
The Φ-Function
- Φ-functions are always at the beginning of a basic block
| - Selects between values depending on control-flow
126
Optimum tiling
s
127
Dominance Property of SSA
Dominance: node D dominates node N if every path from the
start node to N goes through D
- Definition dominates use
- > Dominance can be used to efficiently build SSA
128
Main Components of a VM
s
Virtual machine provides a virtual processor
The VM provides a virtual processor
that interprets bytecode instructions
129
Applications of SSA
Simplifies many optimizations:
- Every variable has only one definition
- Every use knows its definition, every definition knows its uses
- Unrelated variables get different names
```
Examples:
—Constant propagation
—Value numbering
—Invariant code motion and removal
—Strength reduction
—Partial redundancy elimination
```
130
Pharo Bytecode
```
256 Bytecodes, four groups:
Stack Bytecodes
Send Bytecodes
Return Bytecodes
Jump Bytecodes
```
131
SSA and Register Allocation
- Idea: remove Φ as late as possible
- Variables in Φ-function never live at the same time!
- > Can be stored in the same register
- > Do register allocation on SSA!
132
Program Analysis
Types:
- static vs dynamically checked
- soundness
- type checking
- > Typing rules are usually written as natural deductions
- Abstract Interpretation:
- > One of the most generic and fundamental ways of approximating the behavior of a program
133
Method Contexts
sl 38 cc-09
A method context is an object that represents an activation record (stack frame) for a method invocation. Each method context points to the context of its caller, thus constituting a stack of contexts.
134
Lattices
A lattice is a partially ordered set with meet and join.
A partially ordered set is a set S and a binary relation ≤ such that
a ≤ a (reflexivity)
if a ≤ b and b ≤ a, then a = b (antisymmetry)
if a ≤ b and b ≤ c, then a ≤ c (transitivity)
A complete lattice is a lattice where every subset has a supremum and infimum
-> For static analysis, abstract interpretation is mostly performed over finite lattices
135
Dataflow analysis
Flow based analysis is a particular instance of abstract interpretation
136
Optimization
Performance: faster execution
Size: smaller executable, smaller memory footprint
Tradeoffs:
1) Performance vs. Size
2) Compilation speed and memory
Optimizations both in the optimizer and back-end!
- Back-end optimizations may focus on how the machine code is optimally generated
137
Optimizations in the Backend
> Register Allocation
> Instruction Selection
> Peep-hole Optimization
138
GC Remembered Set
Write barrier: remember objects with old-young pointers in "Remembered Set":
When marking young generation, use objects in remembered set as additional roots
139
Instruction Selection
For every expression, there are many ways to realize
them for a processor
Example: Multiplication*2 can be done by bit-shift
Instruction selection is a form of optimization
-> Group IR-tree nodes into clumps that correspond to actions of targetmachine instructions
140
Pharo GC
mark and sweep compacting collector with two
generations
> Cooperative, i.e., not concurrent
> Single threaded
141
Examples for Optimizations
```
> Constant Folding / Propagation
> Copy Propagation
> Algebraic Simplifications
> Strength Reduction
> Dead Code Elimination (Structure Simplifications)
> Loop Optimizations
> Partial Redundancy Elimination
> Code Inlining
```
142
Threading System
Multithreading is the ability to create concurrently
running “processes”
Non-native threads (green threads):
– Only one native thread used by the VM
– Simpler to implement and easier to port
Native threads
– Using the native thread system provided by the OS
– Potentially higher performance
143
Constant Propagation
y
144
Optimization: JIT
Idea: Just In Time Compilation
> Translate unit (method, loop, ...) into native machine code at runtime
> Store native code in a buffer on the heap
Challenges
> Run-time overhead of compilation
> Machine code takes a lot of space (4-8x compared to bytecode)
> Deoptimization (for debugging) is very tricky
Adaptive compilation: gather statistics to compile only units that are heavily used (hot spots)
145
Algebraic Simplifications
s
146
Strength Reduction
s
Replace expensive operations with simpler ones
-> Peephole optimizations are often strength reductions
147
Dead Code
a
148
Simplify Structure
Similar to dead code: Simplify CFG Structure
e. g.
- Delete Empty Basic Blocks
- Fuse Basic Blocks (e.g. “conditional” jumps between basic blocks where conditions are always true)
-> Optimizations will degenerate CFG:
— Needs to be cleaned to simplify further optimization!
149
Common Subexpression Elimination (CSE)
s
150
Loop Optimizations
Optimizing code in loops is important
—often executed, large payoff!
e.g.
—fission/fusion: split/combine loops to improve locality or reduce overhead
—scheduling: run parts in multiple processors
—unrolling: duplicate body several times in order to decrease the number of times the loop condition is tested
—loop-invariant code motion: move invariant code out of loop
151
What can’t PEGs express directly?
> Ambiguous languages
—That’s what CFGs are for!
>
152
Induction Variable Optimizations
Values of variables form an arithmetic progression
sl. 38
153
Scannerless parsers
> Traditional linear-time parsers have fixed lookahead
—With unlimited lookahead, don’t need separate lexical analysis!
- especially useful when mixing languages
with different terminals
154
Memoized parsing: Packrat Parsers
By memoizing parsing results, we avoid having to recalculate partially successful parses.
=> A “packrat parser” is a PEG that memoizes (i.e., caches) intermediate parsing results so they do not have to be recomputed while backtracking.
155
Optimization on SSA
e.g. hree simple ones:
—Constant Propagation
—Copy Propagation
—Simple Dead Code Elimination
156
What is Packrat Parsing not good for?
> General CFG parsing (ambiguous grammars)
—produces at most one result
> Parsing highly “stateful” syntax (C, C++)
—memoization depends on statelessness
> Parsing in minimal space
—LL/LR parsers grow with stack depth, not input size
157
Parser Combinators
> Parser combinators in functional languages are higher order functions used to build parsers
—e.g., Parsec, Haskell
> In an OO language, a combinator is a (functional) object
—To build a parser, you simply compose the combinators
158
JIT compilation
Dynamic Translation: Compilation done during execution of a program – at run time – rather than prior to execution
Improve time and space efficiency of programs using:
> portable and space-efficient byte-code
> run-time information → feedback directed optimizations
> speculative optimization
159
Optimization: Iterative Process
- There is no general “right” order of optimizations
- One optimization generates new opportunities for a preceding one.
=> Optimization is an iterative process
Compile Time vs. Code Quality
160
Stratego
—A language for specifying program transformations
XT:
A collection of transformation tools
161
Registers
s
162
Runtime storage organization
study slides again + chap. 6
163
Stratego vs TXL
Scannerless GLR parsing vs Agile parsing (top-down + bottom-up)
Reusable, generic traversal strategies vs Fixed traversals
Separates rewrite rules from traversal strategies vs Traversals part of rewrite rules
164
Instruction selection
s
165
maximal munch
The “maximal munch” principle is the rule that as much of the input as possible should be processed when creating some construct.
166
Register allocation (Code generation)
Choose registers for variables and temporary values; variables not
simultaneously live can share same register
167
Liveness analysis
Liveness analysis:
Problem:
—IR has unbounded # temporaries
—Machines has bounded # registers
Approach:
—Temporaries with disjoint live ranges can map to same register
—If not enough registers, then spill some temporaries (i.e., keep in memory)
The compiler must perform liveness analysis for each
temporary
—It is live if it holds a value that may still be needed
Liveness information is a form of data flow
analysis over the control flow graph
-> liveness analysis calculates places where each variable holds a still-needed (live) value
168
downward exposure
s
169
upward exposure
s
170
optimal tiling
s
171
Optimum tiling
s
172
virtual machine
an abstract computing
architecture supporting a programming language
in a hardware-independent fashion
173
Main Components of a VM
s
Virtual machine provides a virtual processor
174
Bytecode:
The “machine-code” of the virtual machine
Bytecode is analogous to assembler, except it targets a virtual machine rather than a physical one. Many VMs are stack machines: the generated bytecode pushes values onto a stack, and executes operations that consume one or more values on the top of the stack, replacing them with results
Different forms of bytecodes:
Single bytecodes
Groups of similar bytecodes
Multibyte bytecodes
175
Pharo Bytecode
```
256 Bytecodes, four groups:
Stack Bytecodes
Send Bytecodes
Return Bytecodes
Jump Bytecodes
```
176
Stack vs. Register VMs
Stack machines
• Smalltalk, Java and most other VMs
• Simple to implement for different hardware architectures
• Very compact code
Register machines
• Potentially faster than stack machines
• Only a few register VMs exist, e.g., Parrot VM (Perl6
177
Interpreter State and Loop
s
178
Method Contexts
sl 38 cc-09
A method context is an object that represents an activation record (stack frame) for a method invocation. Each method context points to the context of its caller, thus constituting a stack of contexts.
179
Automatic Memory Management
Tell when an object is no longer used and then recycle the memory
```
Challenges
– Fast allocation
– Fast program execution
– Small predictable pauses
– Scalable to large heaps
– Minimal space usage
```
Main Approaches:
1. Reference Counting (cool idea but fragile)
2. Mark and Sweep
180
Reference Counting GC
Idea
> For each store operation increment count field in header of newly stored object
> Decrement if object is overwritten
> If count is 0, collect object and decrement the counter o each object it pointed to
Problems
> Run-time overhead of counting (particularly on stack)
> Inability to detect cycles (need additional GC technique)
181
Mark and Sweep GC
Idea
> Suspend current process
> Mark phase: trace each accessible object leaving a mark in the object header (start at known root objects)
> Sweep phase: all objects with no mark are collected
> Remove all marks and resume current process
Problems
> Need to “stop the world”
> Slow for large heaps generational collectors
> Fragmentation compacting collectors
182
Generational Collectors
"Most new objects live very short lives;
most older objects live forever"
Idea
> Partition objects into generations
> Create objects in young generation
> Tenuring: move live objects from young to old generation
> Incremental GC: frequently collect young generation (very fast)
> Full GC: infrequently collect young+old generation (slow)
Difficulty
> Need to track pointers from old to new space
183
GC Remembered Set
Write barrier: remember objects with old-young pointers in "Remembered Set":
When marking young generation, use objects in remembered set as additional roots
184
GC Compacting Collectors
Idea
> During the sweep phase all live objects are packed to the beginning of the heap
> Simplifies allocation since free space is in one contiguous block
Challenge
> Adjust all pointers of moved objects
– object references on the heap
– pointer variables of the interpreter!
185
Pharo GC
mark and sweep compacting collector with two
generations
> Cooperative, i.e., not concurrent
> Single threaded
186
When Does the GC Run?
– Incremental GC on allocation count or memory needs
– Full GC on memory needs
– Tenure objects if survivor threshold exceeded
187
Threading System
Multithreading is the ability to create concurrently
running “processes”
Non-native threads (green threads):
– Only one native thread used by the VM
– Simpler to implement and easier to port
Native threads
– Using the native thread system provided by the OS
– Potentially higher performance
188
VM Optimizations
- Method cache for faster lookup: receiver’s class + method selector
- Method context cache (as much as 80% of objects created are context objects!)
- Interpreter loop: 256 way case statement to dispatch bytecodes
- Quick returns: methods that simply return a variable or known constant are compiled as a primitive method
- Small integers are tagged pointers: value is directly encoded in field references
189
Optimization: JIT
Idea: Just In Time Compilation
> Translate unit (method, loop, ...) into native machine code at runtime
> Store native code in a buffer on the heap
Challenges
> Run-time overhead of compilation
> Machine code takes a lot of space (4-8x compared to bytecode)
> Deoptimization (for debugging) is very tricky
190
Process Scheduler
> Cooperative between processes of the same priority
| > Preemptive between processes of different priorities
191
Designing a Language Syntax
Textbook Method
1. Formalize syntax via a context-free grammar
2. Write a parser generator (.*CC) specification
3. Hack on grammar until “nearly LALR(1)”
4. Use generated parser
192
What exactly does a CFG describe?
a rule system to generate language strings
but we really want: a rule system to recognize language strings
193
Parsing Expression Grammars (PEGs)
model recursive descent parsing best practice
PEG specifies rules to recognize sentences in a topdown fashion.
CFG:
S → aaS
S → ε
PEG:
S ← aaS / ε
PEG specifies rules to recognize sentences in a topdown fashion
CFG: a rule system to generate language strings
PEG: a rule system to recognize language strings
194
Key benefits of PEGs
> Simplicity, formalism of CFGs
> Closer match to syntax practices
—More expressive than deterministic CFGs (LL/LR)
—Unlimited lookahead, backtracking
> Linear time parsing for any PEG (!)
-> linear parse time can be achieved with the help
of memoization using a “packrat parser”.
195
Formal properties of PEGs
> Expresses all deterministic languages — LR(k)
> Closed under union, intersection, complement
> Can express some non-context free languages
—e.g., a^nb^nc^n
> Undecidable whether L(G) = ∅
196
What can’t PEGs express directly?
> Ambiguous languages
—That’s what CFGs are for!
>
197
Top-down parsing techniques
Predictive parsers
• use lookahead to decide which rule to trigger
• fast, linear time
Backtracking parsers
• try alternatives in order; backtrack on failure
• simpler, more expressive (possibly exponential time!)
198
Scannerless parsers
- especially useful when mixing languages
| with different terminals
199
Memoized parsing: Packrat Parsers
By memoizing parsing results, we avoid having to recalculate partially successful parses
200
What is Packrat Parsing good for?
> Linear cost
—bounded by size(input) × #(parser rules)
> Recognizes strictly larger class of languages than
deterministic parsing algorithms (LL(k), LR(k))
> Good for scannerless parsing
—fine-grained tokens, unlimited lookahead
> Scannerless parsing enables unified grammar for entire
language
—Can express grammars for mixed languages with different lexemes!
201
What is Packrat Parsing not good for?
> General CFG parsing (ambiguous grammars)
—produces at most one result
> Parsing highly “stateful” syntax (C, C++)
—memoization depends on statelessness
> Parsing in minimal space
—LL/LR parsers grow with stack depth, not input size
202
Parser Combinators
> Parser combinators in functional languages are higher order functions used to build parsers
—e.g., Parsec, Haskell
> In an OO language, a combinator is a (functional) object
—To build a parser, you simply compose the combinators
203
Program Transformation
Translation:
- Compilation
- migration from procedural to OO
Rephrasing:
- desugaring regular expressions
- partial evaluation
204
Program Transformation pipeline
program -> parse -> (tree) -> transform -> (tree) -> transform -> (tree) -> pretty-print -> program
205
Stratego
—A language for specifying program transformations
XT:
A collection of transformation tools
206
Stratego Parsing
Stratego parses any
context-free language
using Scannerless
Generalized LR Parsing
207
TXL
general-purpose source to source transformation language
-> original designed as a desugaring tool for syntactic
extensions to the teaching language Turing
208
Stratego vs TXL
Scannerless GLR parsing vs Agile parsing (top-down + bottom-up)
Reusable, generic traversal strategies vs Fixed traversals
Separates rewrite rules from traversal strategies vs Traversals part of rewrite rules
209
Refactoring
The process of changing a software system in such a
way that it does not alter the external behaviour of the
code, yet improves its internal structure
210
AOP
cross-cutting concerns:
Certain features (like logging, persistence and security), cannot usually be encapsulated as classes. They cross-cut code of the system.
AOP improves modularity by supporting the
separation of cross-cutting concerns.
An aspect packages cross-cutting concerns.
A pointcut specifies a set of join points in the target system to be affected.
Weaving is the process of applying the aspect to
the target system
211
Program transformation: rewrite rules?
s
212
symbol table
aka environment
| symbol table map variable names to information about the variables (e.g. type, location)
213
virtual machine primitive
- > Primitive methods trigger a VM routine and are executed without a new method context unless they fail
- Do work that can only be done in VM (new object creation, process manipulation, become, ...)
- Improve performance
214
regular expressions
—Simpler and more concise for tokens than a grammar
—More efficient scanners can be built from REs
- > CFGs are used to impose structure
- > lexical analysis: Lexical analysis is the first phase of a compiler. The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source code.
215
token / lexeme
Lexemes are said to be a sequence of characters (alphanumeric) in a token. There are some predefined rules for every lexeme to be identified as a valid token. These rules are defined by grammar rules, by means of a pattern. A pattern explains what can be a token, and these patterns are defined by means of regular expressions.
216
interpreter
a program that reads an executable
program and produces the results
of running that program
The job of an interpreter is to execute source code, possibly consuming input, and producing output. An interpreter typically will translate the source code to some intermediate representation along the way, but this intermediate form will not necessarily be
stored as an artifact. In contrast to a compiler, an interpreter does execute the source
program.
217
LALR
LookAhead LR (uses “lookahead sets”)
218
derivation
a proof that shows a sentence is in the language of a grammar.
- > start with the start symbol, then repeatedly replace any nonterminal by one of its right-hand sides
- there are many different derivations of the same sentence
- a parse tree is made by connecting each symbol in a derivation to the one from which it was derived
We can view the productions of a CFG as rewriting rules.
The process of discovering a derivation is called parsing
219
Scanner generators
```
automatically construct code from
regular expression-like descriptions
—construct a DFA
—use state minimization techniques
—emit code for the scanner (table driven or direct code )
```
