1# Optimize memory barriers 2 3## Overview 4 5We need to encode barriers after the instructions NewArray, NewObject, NewMultiArray so that if the created objects are used in another thread, the initialization is fully completed. 6We can remove the barrier if we prove that the created object cannot be passed to another thread before the next barrier. 7This can happen if we save the object to memory or pass it to another method 8 9## Rationality 10 11Reducing the number of instructions and speed up execution. 12 13## Dependence 14 15RPO analysis 16 17## Algorithm 18 19There is instruction flag `MEM_BARRIER`. The flag is set to `true` for the instructions NewObject, NewArray and NewMultiArray. 20The pass `OptimizeMemoryBarriers` try remove the flag(set false) from the instruction. 21We pass through all instructions in PRO order. If the instruction has flag `MEM_BARRIER` we add the instruction in special vector `barriers_insts_`. 22If we visit an instruction that can pass an object to another thread(Store instruction, Call instruction e.t.c) we check the instruction inputs. 23If the instruction has input from the `barriers_insts_`, we call function `MergeBarriers`. 24The function set `false` for the flag `MEM_BARRIER`, exclude last instruction from the vector. 25So we will only set the barrier in the last instruction before potentially passing the created objects to another thread 26 27The function `MergeBarriers` also is called at end of the basic block. 28 29Codegen checks the flag `MEM_BARRIER` for the instructions NewObject, NewArray and NewMultiArray and encode memory barrier if the flag `true` 30 31## Pseudocode 32 33``` 34bool OptimizeMemoryBarriers::RunImpl() 35{ 36 barriers_insts.clear(); 37 for (auto bb : GetGraph()->GetBlocksRPO()) { 38 for (auto inst : bb->Insts()) { 39 if (inst->GetFlag(inst_flags::MEM_BARRIER)) { 40 barriers_insts.push_back(inst); 41 } 42 if (InstCanMoveObjectInAnotherthread(inst) && InstHasBarrierInput(inst, barriers_insts)) { 43 MergeBarriers(barriers_insts); 44 } 45 } 46 MergeBarriers(barriers_insts); 47 } 48 return true; 49} 50 51void MemoryBarriersVisitor::MergeBarriers(InstVector& barriers_insts) 52{ 53 if (barriers_insts.empty()) { 54 return; 55 } 56 auto last_barrier_inst = barriers_insts.back(); 57 for (auto inst : barriers_insts) { 58 inst->ClearFlag(inst_flags::MEM_BARRIER); 59 } 60 last_barrier_inst->SetFlag(inst_flags::MEM_BARRIER); 61 barriers_insts.clear(); 62} 63``` 64 65## Examples 66 67``` 68BB 0 69prop: start 70 0.i64 Constant 0x2a -> (v6, v3, v1, v2, v8, v11) 71succs: [bb 2] 72 73BB 2 preds: [bb 0] 74 1. SaveState v0(vr0) -> (v2) 75 2.ref NewArray 1 v0, v1 -> (v6, v3, v8, v11, v12) 76 3. SaveState v0(vr0), v2(vr1) -> (v5, v4) 77 4.ref LoadAndInitClass 'A' v3 -> (v5) 78 5.ref NewObject 2 v4, v3 -> (v6, v8, v11, v12) 79 6. SaveState v0(vr0), v2(vr1), v5(vr2) -> (v7, v12) 80 7.void CallStatic 3 v6 81 8. SaveState v0(vr0), v2(vr1), v5(vr2) -> (v9, v10) 82 9.ref LoadAndInitClass 'B' v8 -> (v10) 83 10.ref NewObject 4 v9, v8 -> (v11, v13) 84 11. SaveState v0(vr0), v2(vr1), v5(vr2), v10(vr3) 85 12.i64 CallVirtual 5 v2, v5, v6 86 13.ref Return v10 87succs: [bb 1] 88 89BB 1 preds: [bb 2] 90prop: end 91``` 92 93Instructions `2.ref NewArray`, `5.ref NewObject` and `10.ref NewObject` have flag `MEM_BARRIER` by default. 94`7.void CallStatic` don't have the instructions `2.ref NewArray`, `5.ref NewObject` as inputs. 95So the pass `OptimizeMemoryBarriers` will remove the flag from these instructions and skip in `10.ref NewObject`. 96 97## Links 98 99Source code: 100[memory_barriers.cpp](../optimizer/optimizations/memory_barriers.cpp) 101[memory_barriers.h](../optimizer/optimizations/memory_barriers.h) 102 103Tests: 104[memory_barriers_test.cpp](../tests/memory_barriers_test.cpp)