1# Checks Elimination 2## Overview 3**Checks Elimination** - optimization which try to reduce number of checks(NullCheck, ZeroCheck, NegativeCheck, BoundsCheck). 4 5## Rationality 6Reduce number of instructions and removes unnecessary data-flow dependencies. 7 8## Dependences 9* RPO 10* BoundsAnalysis 11* DomTree 12* LoopAnalysis 13 14## Algorithm 15Visit all check instructions in RPO order and check specific rules. 16If one of the rules is applicable, the instruction is deleted. 17 18Instruction deleted in two steps: 191. Check instruction inputs connects to check users. 202. Check instruction replace on `NOP` instruction. 21 22### Rules 23#### All checks 24All the same checks that are dominated by the current one are deleted and consecutive checks deleted. 25#### NullCheck: 261. NullChecks with allocation instruction input is deleted. 272. If based on bounds analysis input of NullCheck is more then 0, check is deleted. 28 29Loop invariant NullChecks replaced by `DeoptimiseIf` instruction before loop. 30 31#### ZeroCheck: 32If based on bounds analysis input of ZeroCheck isn't equal than 0, check is deleted. 33#### NegativeCheck: 34If based on bounds analysis input of NegativeCheck is more then 0, check is deleted. 35#### BoundsChecks: 36If based on bounds analysis input of BoundsCheck is more or equal than 0 and less than length of array, check is deleted. 37 38If BoundsCheck isn't deleted, it insert in special structure `NotFullyRedundantBoundsCheck`. 39``` 40// parent_index->{Vector<bound_check>, max_val, min_val} 41using GroupedBoundsChecks = ArenaUnorderedMap<Inst*, std::tuple<ArenaVector<Inst*>, int64_t, int64_t>>; 42// loop->len_array->GroupedBoundsChecks 43using NotFullyRedundantBoundsCheck = ArenaDoubleUnorderedMap<Loop*, Inst*, GroupedBoundsChecks>; 44``` 45For example, for this method: 46``` 47int Foo(array a, int index) { 48 BoundCheck(len_array(a), index); // id = 1 49 BoundCheck(len_array(a), index+1); // id = 2 50 BoundCheck(len_array(a), index-2); // id = 3 51 return a[index] + a[index+1] + a[index-2]; 52} 53``` 54NotFullyRedundantBoundsCheck will be filled in this way: 55``` 56Root_loop->len_array(a)-> index -> {{BoundsChecks 1,2,3}, max_val = 1, min_val = -2} 57``` 58 59For countable loops witch index in `NotFullyRedundantBoundsCheck`, algorithm try to replace boundschecks by `DeoptimiseIf` instructions before loop. 60 61For example, loop: 62``` 63for ( int i = 0; i < x; i++) { 64 BoundCheck(i); 65 a[i] = 0; 66} 67``` 68will be transormed to 69``` 70deoptimizeIf(x >= len_array(a)); 71for ( int i = 0; i < x; i++) { 72 a[i] = 0; 73} 74 75``` 76 77For another BoundsCheck instructions in `NotFullyRedundantBoundsCheck` algorithm try to replace more then 2 grouped bounds checks by `DeoptimiseIf`. 78For example, this method: 79``` 80int Foo(array a, int index) { 81 BoundCheck(len_array(a), index); // id = 1 82 BoundCheck(len_array(a), index+1); // id = 2 83 BoundCheck(len_array(a), index-2); // id = 3 84 return a[index] + a[index+1] + a[index-2]; 85} 86``` 87will be transformed to: 88``` 89int Foo(array a, int index) { 90 deoptimizeIf(index-2 < 0); 91 deoptimizeIf(index+1 >= len_array(a)); 92 return a[index] + a[index+1] + a[index-2]; 93} 94``` 95 96## Pseudocode 97 TODO 98 99## Examples 100 101Before Checks Elimination: 102``` 1031.ref Parameter -> v3, v4 1042.i64 Constant 1 -> v5, v6 105 1063.ref NullCheck v1 -> v7 1074.ref NullCheck v1 -> v8 1085.i32 ZeroCheck v2 -> v9 1096.i32 NegativeCheck v2 -> v10 110``` 111After Checks Elimination: 112``` 1131.ref Parameter -> v3 1142.i64 Constant 1 -> v9, v10 115 1163.ref NullCheck v1 -> v7, v8 1174.ref NOP 1185.i32 NOP 1196.i32 NOP 120``` 121 122## Links 123Source code: 124[checks_elimination.h](../optimizer/optimizations/checks_elimination.h) 125[checks_elimination.cpp](../optimizer/optimizations/checks_elimination.cpp) 126 127Tests: 128[checks_elimination_test.cpp](../tests/checks_elimination_test.cpp)