tree 6ca07e23dd51b379e3f897f614e65c3ed0f39830
parent ac9ab0dacf0d27529854f1844ccf63bae5615491
author Diego Novillo <dnovillo@google.com> 1518826370 -0500
committer Diego Novillo <dnovillo@google.com> 1519146246 -0500

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.