1# SaveState Bridges 2 3## Overview 4This is a tool that can be used in optimizations that can break correct state of SaveStates. 5 6`SaveStateBridges` has several use cases: 71. Fix `SaveStates` for all object in BasicBlock 82. Fix `SaveStates` for `source` instruction **ONLY** on path from `source` instructions to `target` instruction. 9 10## Rationality 11Some optimisations can break correct state of `SaveStates` and if in this case GC is triggered between incorrect SaveState and usage then we will lost object - we will not find out about his movement and will load him at the wrong address. 12 13## Dependence 14We need to be sure that the `source` instruction dominates the `target` instruction. 15 16## Algorithm 17We bypass the graph in the opposite direction from the `target` instruction to the `source` and we are looking for SS that need to be fixed. We always can do it, because we sure, that the `source` instruction dominates `target`. 18 19## Usage 20Create **`SaveStateBridgesBuilder`** in place where during all time of the pass object will be live. For example, in `.h` file of pass. Functions below are class methods. 21 22**`SearchAndCreateMissingObjInSaveState`** includes `SearchMissingObjInSaveStates` and, if it is required, `CreateBridgeInSS`. It inserts `source` instruction into `SaveStates` on path in each SaveState between `source` and `target` instructions to save the object in case GC is triggered on this path. 23 24**`FixSaveStatesInBB`** fixes all SaveStates in the BasicBlock, if necessary. Searches for the use of objects (reference) and their definition, and on this path enters the object into the SaveState inputs if it is not there. Delete object from the SaveState, if instruction does not dominate this input. Requires a BasicBlock and works within its boundaries. (Despite this, it takes into account the definition and usage outside of this block.) 25 26**`SearchMissingObjInSaveStates`** is using for search SaveState on path to `target`, which don't have `source` instruction in input. Return `ArenaVector<Inst *> *` all of these SaveState. If is empty, bridges are not needed. As an *optional* parameters takes `stop_search`, which restricts the search for SaveState when traversing backwards from `target`, and `target_block` (for the case when we need to build bridges until the end of an empty block, so `target` is `nullptr`). 27 28**`CreateBridgeInSS`** is using for append `source` as a bridge in all SaveStates from `ArenaVector<Inst *> *` received above. 29 30**`DumpBridges`** write in your `std::ostream` all bridges which need add for this `source` instruction. 31 32## Simple example of work without any optimization 33 34### Before: 35 36Receiving and using is at a distance, and the object is not recorded in the intermediate SaveState. This is an incorrect graph, because after SaveState v4 or SaveState v7 GC can be triggered. So obj `1.ref` can be deleted or moved, but the pointer will not change. As a result, in instruction v10 we can use the object at an **invalid address**. 37``` 38 1.ref Intrinsic.GET (v10) 39 ... 40 4. SaveState ... 41 ... 42 7. SaveState ... 43 ... 44 10. Intrinsic.USE v1 45``` 46 47### After `SaveState Bridges`: 48Here the tool corrected SaveState thus restored the object's safety. 49 50``` 51 1.ref Intrinsic.GET (v10) 52 ... 53 4. SaveState v1(bridge), ... 54 ... 55 7. SaveState v1(bridge), ... 56 ... 57 10. Intrinsic.USE v1 58``` 59 60## Example in VN 61 62Instrinsic below with clear flag `NO_CSE`. 63 64Before VN: 65 66``` 67 0.ref Intrinsic.GET (v1) <==| 68 1.void Intrinsic.USE v0 | 69 2. SaveState -> ... | 70 3.ref Intrinsic.GET (v4) <==| Inst v3 is equal inst v0, 71 4.void Intrinsic.USE v3 | they return the same reference 72``` 73 74After VN with bridges + Cleanup: 75``` 76 0.ref Intrinsic.GET (v4, v2, v1) 77 1.void Intrinsic.USE v0 78 2. SaveState v0(bridge) -> ... <==| Added bridge on way 79 | to target instruction 80 <==| VN delete inst v3 81 4.void Intrinsic.USE v0 82``` 83 84## Links 85 86Source code: 87[analysis.h](../optimizer/ir/analysis.h) 88[analysis.cpp](../optimizer/ir/analysis.cpp) 89 90Tests: 91[Tests for GVN](../tests/vn_test.cpp) 92[Tests for Scheduler](../tests/scheduler_test.cpp) 93