1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| ┌───────────────────────────────┐
│ │
│ create IRGenerator │
┌────────▶│ │
│ │ │
│ └───────────────────────────────┘
│ │
│ │
│ ▼
│ ┌───────────────────────────────┐
│ │ │
│ │create cfg -- ControlFlowGraph │
│ │ │
┌───────────────────────────────┐ │ │ │
│ │ │ └───────────────────────────────┘
│ 1. init IRGenerator │ │ │
│ │────────┤ │
│ │ │ ▼
└───────────────────────────────┘ │ ┌───────────────────────────────┐
│ │ │ create entry basic block │
│ │ │ │
│ │ │ maybe we should set the block │
│ │ │ index and block name │
│ │ └───────────────────────────────┘
│ │ │
│ │ │
│ │ │
│ │ ▼
│ │ ┌───────────────────────────────┐
│ │ │ │
│ │ │ add the basic block to cfg │
│ └────────▶│ │
│ │ │
│ └───────────────────────────────┘
│
│
▼
┌───────────────────────────────┐ ┌───────────────────────────────┐
│ │ │ │
│ 2. generate IR │ │ expressions │
│ │─────────────────▶│ │◀─┐
│ │ │ │ │
└───────────────────────────────┘ └───────────────────────────────┘ │
│ │ │
│ │ │
│ ▼ │
│ ┌───────────────────────────────┐ │
│ │ │ │
▼ │ get the current expression │ │
┌───────────────────────────────┐ │ │ │
│ │ │ │ │
│ 3. build inpred order and │ └───────────────────────────────┘ │
│ inpost order graph │ │ │
│ │ │ │
└───────────────────────────────┘ ▼ │
│ ┌───────────────────────────────┐ │ ┌───────────────────────────────┐
│ │ │ │ │ (maybe we should set up a │
│ │ change the expression to IR │ │ │ mapping between the variable │
▼ │ │──┼────▶│ and the block) │
┌───────────────────────────────┐ │ │ │ │ │
│ │ └───────────────────────────────┘ │ └───────────────────────────────┘
│ 4. build dominator tree │ │ │
│ │ │ │
│ │ │ │
└───────────────────────────────┘ ▼ │ ┌─────────────────────────────────────────┐
│ ┌───────────────────────────────┐ │ │ │
│ │ │ │ │ we should create new basic block for if │
▼ │ add IR to basic block │ │ │ statement, loop condition, loop body, │
┌───────────────────────────────┐ │ │──┼────▶│then add basic block link and add to cfg.│
│ │ │ │ │ │(so we should create a branch statement) │
│ 5. insert PhiNodes │ └───────────────────────────────┘ │ │ │
│ │ │ │ │ │
│ │ │ │ └─────────────────────────────────────────┘
└───────────────────────────────┘ └──────────────────┘
│
│
▼
┌───────────────────────────────┐
│ │
│ 6. build SSA │
│ │
│ │
└───────────────────────────────┘
|