Speed up Phi insertion.
authorDiego Novillo <dnovillo@google.com>
Sat, 17 Feb 2018 00:12:50 +0000 (19:12 -0500)
committerDiego Novillo <dnovillo@google.com>
Tue, 20 Feb 2018 17:04:06 +0000 (12:04 -0500)
commit6c75050136a2657dac4501ca16d447852fc69e5f
tree6ca07e23dd51b379e3f897f614e65c3ed0f39830
parentac9ab0dacf0d27529854f1844ccf63bae5615491
Speed up Phi insertion.

On some shader code we have in our testsuite, Phi insertion is showing
massive compile time slowdowns, particularly during destruction.  The
specific shader I was looking at has about 600 variables to keep track
of and around 3200 basic blocks.  The algorithm is currently O(var x
blocks), which means maps with around 2M entries.  This was taking about
8 minutes of compile time.

This patch changes the tracking of stored variables to be more sparse.
Instead of having every basic block contain all the tracked variables in
the map, they now have only the variables actually stored in that block.

This speeds up deallocation, which brings down compile time to about
1m20s.

Note that this is not the definite fix for this.  I will re-write Phi
insertion to use a standard SSA rewriting algorithm
(https://github.com/KhronosGroup/SPIRV-Tools/issues/893).

This contributes to
https://github.com/KhronosGroup/SPIRV-Tools/issues/1328.
source/opt/mem_pass.cpp
source/opt/mem_pass.h