1# Redundant Loop Elimination 2## Overview 3**Redundant Loop Elimination(RLE)** - optimization which find and remove useless loops. 4## Rationality 5Reducing number of basic blocks and instructions. 6## Dependence 7* Loop analysis 8## Algorithm 9Visit loops in LRN order (first children, then parent). 10For each loop check that: 11* RLE is applied for all children loops. 12* Loop doesn't contain instructions with side effect (ex. call instructions). 13* Loop doesn't contain instructions with users out of the loop. 14 15If all checks are true then loop is removing: 161. Loop pre-header connect with loop outer block. 172. Loop inner blocks disconnect from graph. 18## Pseudocode 19``` 20LoopVisitLRN(Loop* loop) { 21 for (auto inner_loop : loop->GetInnerLoops()) { 22 LoopVisitLRN(inner_loop); 23 } 24 if (Check(loop)) { 25 Remove(loop); 26 } 27} 28``` 29## Examples 30Before RLE: 31``` 32BB 0 33prop: start 34 0.i64 Constant 0x0 -> (v4p) 35 1.i64 Constant 0x1 -> (v10) 36 2.i64 Constant 0xa -> (v5) 37succs: [bb 3] 38 39BB 3 preds: [bb 0, bb 4] 40prop: head, loop 1 41 4p.i32 Phi v0(bb8), v10(bb4) -> (v5, v10) 42 5.b Compare LT i32 v4p, v2 -> (v6) 43 6. IfImm NE b v5, 0x0 44succs: [bb 4, bb 5] 45 46BB 5 preds: [bb 3] 47 12. ReturnVoid 48succs: [bb 1] 49 50BB 1 preds: [bb 5] 51prop: end 52 53BB 4 preds: [bb 3] 54prop: loop 1 55 10.i32 Add v4p, v1 -> (v4p) 56succs: [bb 3] 57``` 58After RLE: 59``` 60BB 0 61prop: start 62 0.i64 Constant 0x0 63 1.i64 Constant 0x1 64 2.i64 Constant 0xa 65succs: [bb 5] 66 67BB 5 preds: [bb 0] 68 12. ReturnVoid 69succs: [bb 1] 70 71BB 1 preds: [bb 5] 72prop: end 73``` 74## Links 75 76Source code: 77[redundant_loop_elimination.cpp](../optimizer/optimizations/redundant_loop_elimination.cpp) 78[redundant_loop_elimination.h](../optimizer/optimizations/redundant_loop_elimination.h) 79 80Tests: 81[redundant_loop_elimination_test.cpp](../tests/redundant_loop_elimination_test.cpp)