Algorithm 2.1 Build-Basic-Blocks

Input: IR 表示下的指令序列 $P[1..n]$ .

Output: 所有的基块.

1:Let $L[1..n]$ be a new array. // $L[1..n]$ 用来存放所有的Leader的下标

2:Let $IsLeader[1..n]$ be a new array. // $IsLeader[1..n]$ 用来表示第 $i$ 条指令是否为Leader,初始化为false

3: $IsLeader[1]=true$ // 根据定义2.3， $1$ 号结点一定是Leader

4:for $i = 2$ to $n$ do

5:if the type of $P[i]$ is jump then

6: // 根据定理2.1寻找Leader

7: $IsLeader[ target(P[i]) ]=true$ // $target(x) \to$ 跳转指令x的目标指令的序号

8: $IsLeader[ i + 1 ]=true$

9:end if

10:end for

11: $k = 0$ // $k$ 为Leader的数量

12:for $i = 1$ to $n$ do

13:if IsLeader[i] then

14: $L[k+1]=i$

15: $k=k + 1$

16:end if

17:end for

18: // 根据定理2.2输出Basic Block

19:for $i = 1$ to $k$ do

20:output $P[L[i]..L[i+1]-1]$

21:end for