计算机代考程序代写 compiler algorithm Compiler Design Week 11 – cscodehelp代写
Compiler Design Week 11
Detailed content
Weekly program
Week
Week
Week
Week
Week
Week
Week
Week
Week
Week 10 – Code Generation
1 – Introduction to Compiler Design 2 – Lexical Analysis
3 – CD Programming Language
4 – Syntax Analysis
5 – Top Down Parsing
6 – Symbol Table and Error Recovery
7 – Bottom-Up Parsing
8 – Semantic Analysis
9 – Run-Time Environment: Stack Machine (SM) Architecture
2
Week 11 – Code Optimisation
Week 12 – Revision
Week 13 – Extra revision (if needed)
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
Week 11 Lecture Outline
Code Optimisation
Introduction
Type and Scope of Optimisations
Machine Independent Optimisations Machine Dependent Optimisations
SM Dependant Optimisations
Register Allocation
Basic Blocks and Flow Control Graphs Basic Block level Optimisations
3
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
Introduction
• Optimizing compilers typically
– Try to implement language abstractions efficiently
– Try to utilize hardware resources efficiently
• Different targets may be generated for different compilation goals
– Improved code speed
– Reduced code size
– Shortened compilation time
– Improved programmer productivity
• Feedback to the users; debugging support
– Other properties
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
4
Introduction • Definition
– An optimisation is a transformation that is expected to improve program in some way
• Goal
– Make the object faster and smaller
• Note these can be both complementary and inverse goals • Cost
– Makes the compiler larger, slower, late • Cost Benefit Tradeoff
– Need to balance
• Implementation Cost, Compiler Cost, Improvement gained
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
5
Introduction
• Components of Optimisation:
– Code analysis: analyse the code to derive knowledge about run- time behaviour
– Code rewriting: use collected knowledge to improve the code
• Basic Idea:
– Detect a pattern of code and replace it by more efficient code.
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
6
Introduction
• Fully optimizing compiler (FOC)
– For any input program P, FOC guarantees to generate the fastest/smallest translation with the same behaviour
– Impossible to construct
• Otherwise, we solve the halting problem!
• The word “Optimisation” – a clear misnomer!!
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
7
Types of Code Optimisations
• Machine-independent optimisations
– Eliminate redundant computation
– Eliminate dead code
– Perform computation at compile time if possible
– Execute code less frequently
• Machine-dependent optimisations
– Redundant instruction elimination
– Replace expensive computations with cheaper ones
– Flow of control optimisation
– Algebraic simplification
– Use of machine idioms
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
8
Scope of Code Optimisations
• Peephole optimisations
– Consider a small window of instructions
• Local optimisations
– Consider instruction sequences within a basic block
• Intra-procedural(global) optimisations
– Consider multiple basic blocks within a procedure
– Need support from control flow analysis
• Branches,loops,mergingofflows
• Inter-procedural optimisations
– Consider the whole program w/ multiple procedures
– Need to analyse calls/returns
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
9
Machine Independent Optimisations
• Can generally be achieved by altering the syntax tree/ intermediate code
1. Constant Folding
– X := Y + Z + 4 + 3 X := Y + Z + 7
• Where might we use this in our CD Compiler?
• Would there be any implications?
• Other examples:
x := 32
x := x + 32
+ YZ
+ +3 4
x := 64
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
10
Machine Independent Optimisations 2. IdentityEvaluation
– (X*1) / (1*X),
– (X+0) / (0+X) X – (X-0) / (X/1)
3. Dead Code Removal
const int x = 10 if ( X == 0) then
……… else
………
– if the value of the constant X is not 0 then don’t generate any code at all
b := a + 1
a := b + c
…
Assuming a is dead (not used) COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
b := a + 1 …
12/10/2021
11
Machine Independent Optimisations
4. Common sub-expressions elimination
–X=Y+Z
W += Y + Z + 3 W += X + 3
– Or more generally (with registers /temporary variables )
12/10/2021
t=Y+Z X=t
W += t + 3
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
12
Machine Independent Optimsations 5. Induction Variable Elimination
• An induction variable is a variable whose value on each loop iteration is a linear function of the iteration index.
J = 0;
for (I = 1; I < N; I++) {
J = I*4; .....
}
• Where does this occur?
J += 4;
• Another example with multiple induction variables
J = 0;
for (I = 1; I < N; I++) {
J = I-1; K = 2 * J; M= 3*K
...
}
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
12/10/2021
13
Machine Independent Optimsations
6. Code Motion
for i := 1 to n do begin
temp := 1;
temp := 1;
for i := 1 to n do begin
...... end; end;
Need to be VERY careful. Why?
The above is incorrect if n is 0. We must make sure that the loop is executed at least once.
Also used a lot in address calculations.
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
14
Machine Dependent Optimsations • Basic Plan
– These are dependent on the instruction set of the target machine
– They are generally done using a peephole optimizer which
12/10/2021
• looks at small pieces of code
• recognizes a certain pattern of instructions (sometimes including their operands and other times not), and
• replaces them with more efficient instructions.
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
15
Machine Dependent Optimsations
1. ReductioninStrength
X^2 X * X (machine dependent?)
X*2 X + X (machine dependent/ Using ShiftL?)
2. RemoveRedundantLoadsandStores
Assume a+2 is in a register r0
x = a+2; mov r0,x y = x mov x, r1
mov r1, y
mov r0,x
REMOVED
mov r0,y
Note: we cannot remove the instruction if it has a label, e.g. if (bool) then x = a+2;
y = x;
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
16
Machine Dependent Optimsations 3. FlowofControloptimsation
– Example 1
...... L1: br L2 L1: br L2
......
L2:
– Example 2
br L1
L1:
L2:
br instruction can be eliminated and possibly L1
br L1 br L2
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
17
Machine Dependent Optimsations 4) Recognise special forms
a := a + 1; add 1, a inc a
mov a , r0 add 1, r0 mov r0, a
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
18
SM Special Case
• From Code Generation (Lecture 10)
• Take the case of:
X += Y+Z
This will have as a Syntax Tree Code could be
LA 1,x
LV 1,x
LV 1,y
LV 1,z Y+Z
ADD
ADD
ST YZ
• BUT .. What else could it be?
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
+=assign
Simple var
Add
X
Simple var
Simple var
19
SM Special Case
• We can use Special SM Instructions: • eg:
X += Y+Z
This will have as a Syntax Tree Code could be
LA 1,x
DUP
+=assign
L
LV 1,y LV 1,z ADD ADD ST
X
Simple var
Simple var
Add
Simple var
YZ
Y+Z
• This uses 3 less bytes and may run faster
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
20
Efficient Register Allocation
• Operations on registers take place within the CPU and so the instruction execution can take less time to execute
• We can therefore produce more efficient code by storing values for the most used variables and intermediate results into registers, thus avoiding storing intermediate results into memory.
– a = …a…a…a…a… mov a, r0 – a = ………………… mov r0, a
• Registers can be assigned on a per-Function-Type basis:
• a block for base addresses
• a block for computations
• one register for the current activation record
– This is easy to implement but it can be inefficient
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
21
Efficient Register Allocation
• Global Register Allocation
– That is, allocated registers across block boundaries
– This is very difficult to do
– We can allocate a fixed number of registers for the most active values in each inner loop – this will often require usage counts to determine which are the most active values.
• Optimal assignment of registers is an NP-complete problem
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
22
Register Allocation: Machine Convention
• Further complicated by the fact the target machine may require certain register-usage conventions
– use of register pairs (even and next odd numbered register)
12/10/2021
• MUL x, y [x is the even register and y the odd register, product occupies entire even/odd register pair]
• DIV x, y [dividend occupies even/odd register pair whose even register is x; even register holds remainder, odd holds the quotient]
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
23
Register Allocation within a Block
• How many registers are needed?
• How many are available?
– generally we will have 0 (stack m/c – note that SMx is “all register” memory though), 1 (accumulator), N (other).
• Set up an array with all values unused and then use two routines
– getReg() – returns a register number to be used, and
– freeReg(n) – sets register n to unused
• What if the N registers is insufficient, where do we store the intermediate values that are required?
– Not on the stack (the SP may change). They become implicit local variables to the procedure and are treated as such – we allocate extra space in the local variables section of the current activation record.
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
24
Register Allocation within a Block
• We can therefore assume that we have a Universal Register Machine (URM) with an infinite number of registers
• This gives rise to a Simple Labelling Algorithm
– This algorithm allows us to optimally order an expression tree to minimise the number of registers (& hence the number of intermediate values generated).
– Use a DAG (Directed Acyclic Graph)
12/10/2021
• Leaves have identifiers (l-values or r-values)
• Interior nodes are operators which represent values that would be generated if that operation were carried out
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
25
Simple Labelling Algorithm
• Assume that we only have binary operators
– we label the expression tree starting with the leaves and continuing with the internal nodes – the minimum number of registers required to compute the value of the entire tree will be the label of the root node.
– It may be possible to improve this algorithm slightly in some cases by making use of the commutativity of some operators.
12/10/2021
COMP3290 – Semester 2 – 2021 | www.newcastle.edu.au
26
Simple Labelling Algorithm
if n is a leaf node then
if n is a left leaf of its parent then
else
end else
Label(n) = 1 Label(n) = 0
L1 = Label(leftchild) L2 = Label(rightchild) if (L1 == L2) then
Label(n) = L1 + 1 else
Label(n) = max(L1, L2) end
end
• If the operators are not binary then Label(n) = max(Li + i – 1) for 1<=i<=k, (Li in descending order)
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
27
Example
• (A+B) / (C * (D–E))
labelling algorithm gives answer 2.
Normal Code (left to right) mov A, r0
add B, r0
mov C, r1
+ ABD
/
* C
-
E
Restructured Code
mov D, r0
sub E, r0
mov C, r1
mul r0, r1 mov A, r0 add B, r0 div r1, r0
mov D, r2 sub E, r2 mul r2, r1 div r1, r0
12/10/2021
// 3 registers
// 2 registers
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
28
Example
• (C * (D–E))
labelling algorithm gives answer 2.
1
C
- 1
E
2 *
1
1
-
E
1
*
0
C 0
D
01
D
Normal Code (left to right) mov C, r0
mov D, r1
sub E, r1
mul r0, r1
Restructured Code
mov D, r0
sub E, r0
mul C, r0
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
29
Flow Graphs
• A flow graph is a graphical depiction of a sequence of instructions with control flow edges
• A flow graph can be defined at the intermediate code level or target code level
MOV 1,R0 MOV n,R1 JMP L2
L1: MUL 2,R0
SUB 1,R1
L2: JMPNZ R1,L1
MOV 0,R0 MOV n,R1 JMP L2
L1: MUL 2,R0
SUB 1,R1
L2: JMPNZ R1,L1
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
30
Basic Blocks
• Basic Block: Definition
– Sequence of consecutive statements
– flow enters at the top and leaves at the bottom
– no chance of halt or branching
• Leader:
– First 3 address instruction is a leader
– Any instruction that is the target of a jump is a leader
– Any instruction that immediately follows a jump is a leader
• A basic block starts from a leader until the next leader or end.
MOV 1,R0 MOV n,R1 JMP L2
L1: MUL 2,R0
SUB 1,R1
L2: JMPNZ R1,L1
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
MOV 1,R0 MOV n,R1 JMP L2
L1: MUL 2,R0 SUB 1,R1
L2: JMPNZ R1,L1
31
Basic Blocks & Control Flow Graphs
•
A control flow graph (CFG) is a directed graph with basic blocks Bi as vertices and with edges BiBj iff Bj can be executed immediately after
Bi
MOV 1,R0
MOV n,R1
JMP L2
L1: MUL 2,R0
SUB 1,R1
L2: JMPNZ R1,L1
MOV 1,R0 MOV n,R1 JMP L2
L1: MUL 2,R0
SUB 1,R1
L2: JMPNZ R1,L1
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
32
Successor and Predecessor Blocks
• Suppose the CFG has an edge B1B2
– Basic block B1 is a predecessor of B2
– Basic block B2 is a successor of B1
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
MOV 1,R0
MOV n,R1
JMP L2
L1: MUL 2,R0 SUB 1,R1
L2: JMPNZ R1,L1
33
Partition Algorithm for Basic Blocks
• Input: A sequence of three-address statements
• Output: A list of basic blocks with each three-address statement
in exactly one block
1. Determine the set of leaders, the first statements if basic blocks a) The first statement is the leader
b) Any statement that is the target of a goto is a leader
c) Any statement that immediately follows a goto is a leader
2. For each leader, its basic block consist of the leader and all statements up to but not including the next leader or the end of the program
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
34
Entry and Exit Blocks
• Do not correspond to the executable intermediate instructions
– entry: edge from entry to the first executable node of the flow graph
– exit: edge to the exit from any basic block that contains the final instruction of the program
Entry
MOV 1,R0
MOV n,R1
JMP L2
B1 B2 B3
L1: MUL 2,R0
SUB 1,R1
L2: JMPNZ R1,L1
Exit
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
35
Equivalence of Basic Blocks
• Two basic blocks are (semantically) equivalent if they compute the same set of expressions
b :=0
t1 := a + b t2 := c * t1 a :=t2
a := c*a a := c*a b := 0 b := 0
Blocks are equivalent, assuming t1 and t2 are dead: no longer used (no longer live)
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
a :=c*a b :=0
36
Next-Use
• Next-use information is needed for dead-code elimination and register assignment
– If the value of a variable is currently in a register and will never be referenced subsequently, then that register can be assigned to another variable
• Next-use is computed by a backward scan of a basic block and performing the following actions on statement
i: x := y op z
– Add liveness/next-use info on x, y, and z to statement i
– Set x to “not live” and “no next use”
– Set y and z to “live” and the next uses of y and z to i • Liveness:
– Statement i assigns a value to x.
– Statement j has x as an operand, and control can flow from i to j along a
path with no intervening assignments to x,
– Then x is live at statement i.
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
37
Next-Use (Step 1)
i: a:=b+c
j: t := a + b [ live(a) = true, live(b) = true, live(t) = true,
nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]
Attach current live/next-use information
Because info is empty, assume variables are live
(Data flow analysis can provide accurate information) 12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
38
Next-Use (Step 2)
live(a) = true live(b) = true live(t) = false
nextuse(a) = j nextuse(b) = j nextuse(t) = none
i: a:=b+c
j: t := a + b [ live(a) = true, live(b) = true, live(t) = true,
nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]
Compute live/next-use information at j
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
39
Next-Use (Step 3)
i: a := b + c [ live(a) = true, live(b) = true, live(c) = false, nextuse(a) = j, nextuse(b) = j, nextuse(c) = none ]
j: t := a + b [ live(a) = true, live(b) = true, live(t) = true,
nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]
Attach current live/next-use information to i
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
40
Next-Use (Step 4)
live(a) = false live(b) = true live(c) = true live(t) = false
nextuse(a) = none nextuse(b) = i nextuse(c) = i nextuse(t) = none
i: a := b + c [ live(a) = true, live(b) = true, live(c) = false, nextuse(a) = j, nextuse(b) = j, nextuse(c) = none ]
j: t := a + b [ live(a) = false, live(b) = false, live(t) = false,
nextuse(a) = none, nextuse(b) = none, nextuse(t) = none ]
Compute live/next-use information i
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
41
•
DAG Representation of Basic Block
DAG for a basic block has:
– A node for each initial values of the variables in the basic block subscripted by 0
– A node N for each statement s within the block.
• Children of N are nodes corresponding to last definitions of the operands of s
• N is labelled by the operator and the list of variables with last definition
– Certain nodes are designated output nodes – nodes whose variables are live on exit form the block.
a=b+c b=a-d c=b+c d=a-d
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
42
•
DAG for Code Optimisations
Common sub expression elimination
a=b+c b=a-d c=b+c d=a-d
•
3 non-leaf nodes3 statements are enough
a=b+c a=b+c b=a-d d=a-d c=b+c c=d+c d=a-d
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
43
References
• Compilers: Principles, Techniques, and Tools (2nd Edition)
– By A.V. Aho, Lam, R. Sethi, . Ullman
• Chapter 8
12/10/2021
COMP3290 - Semester 2 - 2021 | www.newcastle.edu.au
44
