Cocke et. al. proposed algebraic re-association in 1970s, and concept was extended by shantaram, and keith cooper and preston briggs in their Partial Redundancy Elimination paper (1995). In algebraic re-association, a subtree of the abstract syntax tree computing an arithmetic expression is re-arranged so that there is not change in output but instead exposes more opportunities for constant propagation, PRE, and other compiler optimizations.
For our project, we identify reassociation as one of the strategies to prevent the ‘C3’s from occurring at un-intended places (an actual function return is an intended ‘C3’ in the machine code). We employ the first few steps as done in ‘breaking basic blocks’:
* use clang to generate an executable of the application
* use gdb -x with disas commands to disassemble the code, and search for C3
* map the unintended C3 instructions back to source code.
—this phaser specific changes—-
*reassociate pass in llvm skips over instructions which do not match the special line numbers.
*selects instructions +- 5 from instructions important to us, applies algebraic re-association.
eg: 4+x-5 ===> x-5+4 (this step is algebraic reassociation)
* we were able to see around 7% reduction in RETs with this approach in some benchmarks
* this pass combines with basic block splitting led to around 33% unintended ret reductions for some benchmarks.
More results in final presentation.