1# Value Numbering 2 3## Overview 4 5Value numbering sets special numbers(`vn`) to all instructions. If two instruction has equal VN, so the instructions are equals. 6At the case we move users from second instruction to first instructions(first instruction is dominate). 7 8## Rationality 9 10Reducing the number of instructions. 11 12## Dependence 13 14RPO analysis, DominatorsTree. 15 16## Algorithm 17 18All instructions have field `vn_`. 19We pass through all instructions in PRO order. If the instruction has attribute NO_Cse, we set next `vn` to the field. 20For other instructions we save information: opcode, type, `vn` of instruction inputs, advanced properties(for example type_id). 21Based on the collected information, we are looking for a equivalent instructions in the hash map. 22 231. If equivalent instructions were found: 24 a. If some equivalent instruction dominates current instruction, we move users from current instruction. 25 b. If all equivalent instructions do not dominate current instruction, we insert the instruction in the equivalent instructions vector, and also get `vn` from the first equivalent instruction ans set to current. 262. If equivalent instructions weren't found, we set next `vn` to the current instruction field and add information about the instruction in the hash map. 27 28Value numbering doesn't remove instructions. Instructions without users will be removed by [Cleanup](cleanup_doc.md) in next passes 29 30## Pseudocode 31 32```cpp 33bool ValNum::RunImpl() { 34 for (auto bb : GetGraph()->GetBlocksRPO()) { 35 for (auto inst : bb->AllInsts()) { 36 FindEqualVnOrCreateNew(inst); 37 } 38 } 39 return true; 40} 41 42void ValNum::FindEqualVnOrCreateNew(Inst* inst) { 43 if (inst->IsNotCseApplicable()) { 44 inst->SetVN(vn_++); 45 return; 46 } 47 auto obj = GetGraph()->GetLocalAllocator()->New<VnObject>(); 48 obj->Add(inst); 49 auto it = map_insts_.find(obj); 50 if (it == map_insts_.cend()) { 51 inst->SetVN(vn_++); 52 map_insts_.insert({obj, {inst}}); 53 return; 54 } 55 auto& equiv_insts = it->second; 56 if (!TryToApplyCse(inst, &equiv_insts)) { 57 equiv_insts.push_back(inst); 58 } 59} 60 61bool ValNum::TryToApplyCse(Inst* inst, InstVector* equiv_insts) { 62 inst->SetVN((*equiv_insts)[0]->GetVN()); 63 for (auto equiv_inst : *equiv_insts) { 64 if (equiv_inst->IsDominate(inst)) { 65 inst->ReplaceUsers(equiv_inst); 66 return true; 67 } 68 } 69 return false; 70} 71``` 72 73## Examples 74 75Before ValNum: 76 77``` 78BB 0 79prop: start 80 0.u64 Parameter arg 0 -> (v10, v6, v7, v13) 81 1.u64 Parameter arg 1 -> (v10, v6, v7, v13) 82 2.f64 Parameter arg 2 -> (v11, v9) 83 3.f64 Parameter arg 3 -> (v11, v9) 84 4.f32 Parameter arg 4 -> (v8, v12) 85 5.f32 Parameter arg 5 -> (v8, v12) 86succs: [bb 2] 87 88BB 2 preds: [bb 0] 89 6.u64 Add v0, v1 -> (v14) 90 7.u32 Sub v1, v0 -> (v14) 91 8.f32 Mul v4, v5 -> (v14) 92 9.f64 Div v3, v2 -> (v14) 93 10.u32 Sub v1, v0 -> (v14) 94 11.f64 Div v3, v2 -> (v14) 95 12.f32 Mul v4, v5 -> (v14) 96 13.u64 Add v0, v1 -> (v14) 97 14.b CallStatic v6, v7, v8, v9, v10, v11, v12, v13 98 15. ReturnVoid 99succs: [bb 1] 100 101BB 1 preds: [bb 2] 102prop: end 103``` 104 105After ValNum 106 107``` 108BB 0 109prop: start 110 0.u64 Parameter arg 0 -> (v10, v6, v7, v13) 111 1.u64 Parameter arg 1 -> (v10, v6, v7, v13) 112 2.f64 Parameter arg 2 -> (v11, v9) 113 3.f64 Parameter arg 3 -> (v11, v9) 114 4.f32 Parameter arg 4 -> (v8, v12) 115 5.f32 Parameter arg 5 -> (v8, v12) 116succs: [bb 2] 117 118BB 2 preds: [bb 0] 119 6.u64 Add v0, v1 -> (v14, v14) 120 7.u32 Sub v1, v0 -> (v14, v14) 121 8.f32 Mul v4, v5 -> (v14, v14) 122 9.f64 Div v3, v2 -> (v14, v14) 123 10.u32 Sub v1, v0 124 11.f64 Div v3, v2 125 12.f32 Mul v4, v5 126 13.u64 Add v0, v1 127 14.b CallStatic v6, v7, v8, v9, v7, v9, v8, v6 128 15. ReturnVoid 129succs: [bb 1] 130``` 131 132After DCE: 133 134``` 135BB 0 136prop: start 137 0.u64 Parameter arg 0 -> (v6, v7) 138 1.u64 Parameter arg 1 -> (v6, v7) 139 2.f64 Parameter arg 2 -> (v9) 140 3.f64 Parameter arg 3 -> (v9) 141 4.f32 Parameter arg 4 -> (v8) 142 5.f32 Parameter arg 5 -> (v8) 143succs: [bb 2] 144 145BB 2 preds: [bb 0] 146 6.u64 Add v0, v1 -> (v14, v14) 147 7.u32 Sub v1, v0 -> (v14, v14) 148 8.f32 Mul v4, v5 -> (v14, v14) 149 9.f64 Div v3, v2 -> (v14, v14) 150 14.b CallStatic v6, v7, v8, v9, v7, v9, v8, v6 151 15. ReturnVoid 152succs: [bb 1] 153``` 154 155## Links 156 157Source code: 158[vn.cpp](../optimizer/optimizations/vn.cpp) 159[vn.h](../optimizer/optimizations/vn.h) 160 161Tests: 162[vn_test.cpp](../tests/vn_test.cpp) 163