Rewriting dead branch elimination.
authorAlan Baker <alanbaker@google.com>
Thu, 4 Jan 2018 22:04:03 +0000 (17:04 -0500)
committerDavid Neto <dneto@google.com>
Tue, 9 Jan 2018 17:21:39 +0000 (12:21 -0500)
commit1b6cfd34092ad1f06bcaeee684778201da2f7856
tree9f3dc8a77579f9e9c7c89634e5ef9e102a45b400
parente5560d64de40bcc52b38ee44fd8a0bbc42f64399
Rewriting dead branch elimination.

Pass now paints live blocks and fixes constant branches and switches as
it goes. No longer requires structured control flow. It also removes
unreachable blocks as a side effect. It fixes the IR (phis) before doing
any code removal (other than terminator changes).

Added several unit tests for updated/new functionality.

Does not remove dead edge from a phi node:
* Checks that incoming edges are live in order to retain them
* Added BasicBlock::IsSuccessor
* added test

Fixing phi updates in the presence of extra backedge blocks

* Added tests to catch bug

Reworked how phis are updated

* Instead of creating a new Phi and RAUW'ing the old phi with it, I now
replace the phi operands, but maintain the def/use manager correctly.

For unreachable merge:

* When considering unreachable continue blocks the code now properly
checks whether the incoming edge will continue to be live.

Major refactoring for review

* Broke into 4 major functions
 * marking live blocks
 * marking structured targets
 * fixing phis
 * deleting blocks
include/spirv-tools/optimizer.hpp
source/opt/basic_block.cpp
source/opt/basic_block.h
source/opt/dead_branch_elim_pass.cpp
source/opt/dead_branch_elim_pass.h
source/opt/mem_pass.cpp
source/opt/mem_pass.h
test/opt/dead_branch_elim_test.cpp