Digital Systems Design Methodologies

High level synthesis

Basic Concepts

26/02/21
 HLS: Basic Concepts

2
 Why use intermediate representations?

Software engineering • break compiler into manageable

principle pieces

Simplifies retargeting
to new host • isolates back end from front end

Simplifies support for • different languages can share IR

multiple languages and back end

Enables machine- • general techniques, multiple

independent
optimization passes

-3-
 Kinds of IR

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

-4-
 Definition. Basic Blocks

A basic block is a maximal sequence of

instructions with:
• no labels (except at the first instruction), and
• no jumps (except in the last instruction)

Idea:
• Cannot jump in a basic block (except at beginning)
• Cannot jump out of a basic block (except at end)
• Each instruction in a basic block is executed after all the
preceding instructions have been executed

-5-
 Basic Block Example

❑ Consider the basic block

1. L:
2. t := 2 * x
3. w := t + x
4. if w > 0 goto L’
❑ No way for (3) to be executed without (2) having been
executed right before
– We can change (3) to w := 3 * x
– Can we eliminate (2) as well?
 Identifying Basic Blocks

❑ Input: sequence of instructions instr(i)

– Identify leaders. Leaders are:
• The entry point of the function

• Any instruction that is a target of a branch

• Any instruction following a (conditional or unconditional)

branch
– Iterate: add subsequent instructions to basic block until we reach
another leader

-7-
 Basic Block Example

1 A=4
2 t1 = A * B Leaders
3 L1: t2 = t1/C
4 if t2 < W goto L2 Basic blocks
5 M = t1 * k
6 t3 = M + I
7 L2: H = I
8 M = t3 – H
9 if t3 >= 0 goto L4
10 L3: goto L1
11 L4: goto L3

8
 Control-Flow Graphs

❑ Control-flow graph:
– Node: an instruction or sequence of instructions (a basic block)
• Two instructions i, j in same basic block
iff execution of i guarantees execution of j
– Directed edge: potential flow of control
– Distinguished start node Entry
• First instruction in program

9
 Control-Flow Edges

❑ Basic blocks = nodes

❑ Edges:
– Add directed edge between B1 and B2 if:
• BRANCH from last statement of B1 to first statement of B2 (B2 is a
leader), or
• B2 immediately follows B1 in program order and B1 does NOT end
with unconditional branch (goto)

10
Static Single Assignment Form

Goal: simplify procedure-global optimizations

Definition: Program is in SSA form if every

variable is only assigned once

11
Why Static?

We only look at the static

program
Why Static? One assignment per
variable in the program

At runtime variables are assigned multiple

times!

- 12 -
 Example: Sequence

❑ Easy to do for sequential programs:

Original SSA
a := b + c a1 := b1 + c1
b := c + 1 b2 := c1 + 1
d := b + c d1 := b2 + c1
a := a + 1 a2 := a1 + 1
e := a + b e1 := a2 + b2

13
 Example: Condition

❑ Conditions: what to do on control-flow merge?

Original SSA
if B then if B then
a := b a1 := b
else else
a := c a2 := c
end End
… a …
… a? …
14
 Solution: -Function

❑ Conditions: what to do on control-flow merge?

Original SSA
if B then if B then
a := b a1 := b
else else
a := c a2 := c
end End
… a … a3 := (a1,a2)
… a3 …
15
 The -Function

❑ -functions are always at the beginning of a basic block

❑ Select between values depending on control-flow

❑ a1 := (a1…ak): the block has k preceding blocks

PHI-functions are all evaluated simultaneously.

16
 SSA and CFG

❑ SSA is normally done for control-flow graphs (CFG)

❑ Basic blocks are in 3-address form

17
 Control flow graph

❑ A CFG models transfer of control in a program

– nodes are basic blocks (straight-line blocks of code)
– edges represent control flow (loops, if/else, goto …)

if x = y then
S1
else
S2
end
S3

18
 SSA: a Simple Example

if B then
a1 := 1
else
a2 := 2
End
a3 := PHI(a1,a2)
… a3 …

19
 3-address code

❑ Statements take the form: x = y op z

– single operator and at most three names

x – 2 * y t1 = 2 * y
t2 = x – t1

> Advantages:
— compact form
— names for intermediate values

20
 Typical 3-address codes

x = y op z
x = op y
assignments
x = y[i]
x=y
branches goto L
conditional branches if x relop y goto L
param x
procedure calls param y
call p
x = &y
address and pointer assignments
*y = z

21
 Data flow graphs

❑ Behavioral views of architectural models.

❑ Useful to represent data-paths.

❑ Each basic block have a data flow graph associated with it

❑ Graph:
– Vertices = operations.
– Edges = dependencies.

22
 Data Flow Graph (cont.)

❑ Used to model data dependencies in the code

❑ Four types of data dependencies
– Flow or read-after-write
– Anti or write-after-read
– Output or write-after-write
– Input or read-after-read
❑ Input dependencies does not affect scheduling
❑ Anti and Output dependencies can be removed by
register renaming technique
❑ So, DFG is used to model only RAW dependencies

23
 Dataflow graph Example

xl = x + dx
ul = u - (3 * x * u * dx) - (3 * y * dx)
yl = y + u * dx
c = xl < a

24
 Example of Data Flow Graph
continued

xl = x + dx
ul = u - (3 * x * u * dx)
- (3 * y * dx)
yl = y + u * dx
c = xl < a

25
 CDFG: control data flow graph

BB2
BB1
* *
+

Data Flow Graph

BB3

26 Control Flow Graph

 CDFG Example

1: t = a + b; BB0
2: u = a – b;
3: if (a < b)
4: v = t + c; BB2
else
{
5: w = u + c; BB3
6: v = w – d;
}
7: x = v + e; BB4
8: y = v – e;
27 27