1# Lowering
2## Overview 
3
4Lowering makes instructions more low-level(close to the architecture).  
5
6## Rationality
7
8Reducing the number of instructions. 
9
10## Dependence 
11
12* RPO analysis.
13* Encoder from codegen.
14* Peephole optimization.
15
16## Algorithm
17
18We pass through all instructions in PRO order.
19If the instruction and its input can be encoded with single instruction for a specific archecture, then we change the instruction.  
20The main conversation is to replace an instruction with a constant input with the instruction with a constant as an operand, if the architecture supports these instructions.  
21The encoder is used for these  
22
23Lowering doesn't remove instructions. Instructions without users will be removed by [Cleanup](cleanup_doc.md) in next passes
24
25## Pseudocode
26
27for (auto inst: All insts in RPO order) {
28    VisitInstruction(inst);
29}
30
31void VisitAdd/Sub(Inst* inst) {
32    if (!inst->GetInput(1)->IsConst()) {
33        return
34    }
35    uint64_t val = inst->GetInput(1)->GetConst();
36    if (encoder->CanEncodeImmAddSubCmp(val)) {
37        Inst* new_inst = CreateInstAddI(inst->GetType(), inst->GetPc(), val);
38        inst->ReplaceUsers(new_inst)
39    }
40}
41
42}
43
44## Examples
45
46Before Lowering  
47
48```
49BB 0
50prop: start
51    0.u64  Parameter                  arg 0 -> (v9, v8, v7, v6, v4, v5, v17, v17, v18, v18, v19, v20, v10)
52   11.f64  Parameter                  arg 1 -> (v13, v14, v10)
53   12.f32  Parameter                  arg 2 -> (v15, v16, v10)
54    1.i64  Constant                   0xc -> (v7, v4, v19, v10)
55    2.i64  Constant                   0xffffffffffffffff -> (v8, v5, v20, v10)
56    3.i64  Constant                   0x5f5e100 -> (v9, v6, v10)
57   21.f64  Constant                   1.2 -> (v13, v14, v10)
58   22.f32  Constant                   0.5 -> (v15, v16, v10)
59succs: [bb 2]
60
61BB 2  preds: [bb 0]
62    4.u64  Add                        v0, v1 -> (v10)
63    5.u64  Add                        v0, v2 -> (v10)
64    6.u64  Add                        v0, v3 -> (v10)
65    7.u64  Sub                        v0, v1 -> (v10)
66    8.u64  Sub                        v0, v2 -> (v10)
67    9.u64  Sub                        v0, v3 -> (v10)
68   13.f64  Add                        v11, v21 -> (v10)
69   14.f64  Sub                        v11, v21 -> (v10)
70   15.f32  Add                        v12, v22 -> (v10)
71   16.f32  Sub                        v12, v22 -> (v10)
72   17.u64  Add                        v0, v0 -> (v10)
73   18.u64  Sub                        v0, v0 -> (v10)
74   19.u16  Add                        v0, v1 -> (v10)
75   20.u16  Add                        v0, v2 -> (v10)
76   10.     SaveState                  v0(vr0), v1(vr1), v2(vr2), v3(vr3), v4(vr4), v5(vr5), v6(vr6), v7(vr7), v8(vr8), v9(vr9), v11(vr10), v12(vr11), v13(vr12), v14(vr13), v15(vr14), v16(vr15), v17(vr16), v18(vr17), v19(vr18), v20(vr19), v21(vr20), v22(vr21)
77   23.     ReturnVoid
78succs: [bb 1]
79```
80
81After Lowering and DCE
82
83```
84BB 0
85prop: start
86    0.u64  Parameter                  arg 0 -> (v27, v26, v25, v24, v9, v6, v17, v17, v18, v18, v19, v20, v10)
87   11.f64  Parameter                  arg 1 -> (v13, v14, v10)
88   12.f32  Parameter                  arg 2 -> (v15, v16, v10)
89    1.i64  Constant                   0xc -> (v19)
90    2.i64  Constant                   0xffffffffffffffff -> (v20)
91    3.i64  Constant                   0x5f5e100 -> (v9, v6)
92   21.f64  Constant                   1.2 -> (v13, v14)
93   22.f32  Constant                   0.5 -> (v15, v16)
94succs: [bb 2]
95
96BB 2  preds: [bb 0]
97   24.u64  AddI                       v0, 0xc -> (v10)
98   25.u64  SubI                       v0, 0x1 -> (v10)
99    6.u64  Add                        v0, v3 -> (v10)
100   26.u64  SubI                       v0, 0xc -> (v10)
101   27.u64  AddI                       v0, 0x1 -> (v10)
102    9.u64  Sub                        v0, v3 -> (v10)
103   13.f64  Add                        v11, v21 -> (v10)
104   14.f64  Sub                        v11, v21 -> (v10)
105   15.f32  Add                        v12, v22 -> (v10)
106   16.f32  Sub                        v12, v22 -> (v10)
107   17.u64  Add                        v0, v0 -> (v10)
108   18.u64  Sub                        v0, v0 -> (v10)
109   19.u16  Add                        v0, v1 -> (v10)
110   20.u16  Add                        v0, v2 -> (v10)
111   10.     SaveState                  v0(vr0), v20(vr19), v19(vr18), v18(vr17), v24(vr4), v25(vr5), v6(vr6), v26(vr7), v27(vr8), v9(vr9), v11(vr10), v12(vr11), v13(vr12), v14(vr13), v15(vr14), v16(vr15), v17(vr16),  0xc(vr1),  0x3f000000(vr21),  0x3ff3333333333333(vr20),  0xffffffffffffffff(vr2),  0x5f5e100(vr3)
112   23.     ReturnVoid
113succs: [bb 1]
114
115```
116
117## Links
118
119Source code:   
120[lowering.cpp](../optimizer/optimizations/lowering.cpp)  
121[lowering.h](../optimizer/optimizations/lowering.h)  
122
123Tests:  
124[lowering_test.cpp](../tests/lowering_test.cpp)
125