Apresenta__o_2_PCA_1_2023

Prévia do material em texto

Program Analysis Algorithms
Control Flow Graph
Bruno Almeida
Lucas Dalle
Tayná Fischer
UNB
PCA 1-2023
Table of contents
1. Introduction
2. Structure
3. Code Optimization: Local vs. Global
4. Implementation
5. Schedule
1
What is Control Flow Graph (CFG)?
Definition
A graph representation of all paths that might be traversed through a
program during its execution[3].
Figure 1: Flow graph for the factorial program
2
Goal
Compiler optimizations during static program analysis, precisely after
intermediate code generation.
3
Goal
Figure 2: Translation of an assignment statement[1]
4
Structure
Control Flow Graph structure
• Directed graph;
• Each node represents a basic block;
• Each edge represents a possible flow between basic blocks,
during program execution.
5
Basic Blocks
A straight-line code sequence with no branches in except to the
entry and no branches out except at the exit[2].
• Starts at the first instruction of each block;
• No branches into the middle of the block;
• Only last instruction could be a branch/jump.
6
Basic Blocks
In fact, there’s an algorithm that determines basic blocks by defining
leaders of each block, following these conditions:
1. The first instruction is a leader;
2. The target of a conditional or an unconditional goto/jump
instruction is a leader.
3. The instruction that immediately follows a conditional or an
unconditional goto/jump instruction is a leader.
Therefore, all instructions from a leader to the next leader
(excluding) belong at the same basic block.
7
Flow-of-Control Statements
Figure 3: Simple statements CFG
8
Running Example
Example 01: Factorial
While language
y := x; (1)
z := 1;
while(y > 1) do (2)
z := z * y; (3)
y := y - 1;
y := 0; (4)
9
While program CFG
Figure 4: Flow graph for the factorial program in While
10
Generating CFG by source code
Listing 1: Factorial program in C
i n t main ( ) {
i n t x , y , z ;
y = x ;
z = 1 ;
while ( y > 1 ) {
z = z * y ;
y = y − 1 ;
}
y = 0 ;
return 0 ;
}
11
CFG using LLVM
Figure 5: Generation of CFG by using LLVM compiler framework.
12
Code Optimization: Local vs.
Global
Code Optimization: Local
• Common subexpressions elimination;
• Copy propagation;
• Dead code elimination;
• Frequency Reduction;
• Peephole optimizations.
13
Common subexpressions elimination
Identification of common subexpressions that hasn’t been modified
since last execution.
Figure 6: Application of common subexpressions elimination
14
Copy propagation
Identification of variables that are copies of temporary registers, in
order to avoid their propagation.
Figure 7: Application of copy propagation
In this example, it eases further elimination of x.
15
Dead code elimination
Identification of variables that won’t be used or sequences of code
that won’t ever be executed.
Figure 8: Application of dead code elimination
16
Frequency reduction
Decreases amount of code inside loops, without affecting the
semantics.
Figure 9: Application of frequency reduction
17
Peephole optimizations
• Eliminates redundancy;
• Simplifies constants;
Figure 10: Application of peephole optimizations
18
Peephole optimizations
• Substitute operators that consumes higher execution time;
• Deletes neutral operations in algebraic expressions.
Figure 11: Application of peephole optimizations 19
Code Optimization: Global
• Loop distribution and loop jamming;
• Constant propagation between basic blocks;
• General dead code elimination.
20
Loop distribution and loop jamming
• Loop distribution: Break large loop body into smaller parts
(efficient in multiprocessing)
• Loop jamming: Replace multiple loops with a single one
(reduces temporary alocations and avoid loop control functions)
Figure 12: Application of loop distribution/loop jamming
21
Constant propagation between basic blocks
Useful when eliminating unnecessary conditional checks of values
that never changes.
Figure 13: Application of loop distribution/loop jamming
22
General dead code elimination
Useful when eliminating unnecessary code that won’t ever be
executed.
Figure 14: Application of dead code elimination between basic blocks
23
Advanced optimization techniques
• Data Flow Analysis;
• Profile-guided optimization;
• Automatic vectorization;
• Parallelization.
24
Implementation
While language
Syntactic Categories:
a ∈ AExp: arithmetic expressions
b ∈ BExp: boolean expressions
S ∈ Stmt: statements
25
While language
Operators:
x, y ∈ Var: variables
n ∈ Num: numerals
l ∈ Lab: labels
opa ∈ Opa: arithmetic operators
opb ∈ Opb: boolean operators
opr ∈ Opr: relational operators
26
While language
Syntax:
a ::= x | n | a1 opa a2
b ::= true | false | not b | b1 opb ab
S ::= [x := a]l | [skip]l | S1; S2 |
if [b]l then S1 else S2 | while [b]l do S
27
Library
Here’s the CFG algorithm implementation, so far:
https://github.com/bassilva/pca-1-2023
28
https://github.com/bassilva/pca-1-2023
Schedule
Next Topic: Data Flow Analysis
• Reaching Definitions;
• Available Expressions;
• Live Variable Analysis;
• Very Busy Expressions.
29
References i
A. Aho, R. Sethi, and J. D. Ullman.
Compilers principles, techniques, and.
In Tools. Addison-Wesley Boston, MA, 1985.
T. F. E. Wikipedia.
Basic block.
2023.
Acessed on: May 01 2023.
T. F. E. Wikipedia.
Control-flow graph.
2023.
Acessed on: May 01 2023.
	Introduction
	Structure
	Code Optimization: Local vs. Global
	Implementation
	Schedule
	Appendix