[Mesa-dev] [PATCH 00/14] [RFC] Optimizations on copy propagation

[Thomas Helland]

Hi all.

This is a series I've put together to lower the overhead of
the copy propagation pass in glsl. The series is not refined,
so please treat it as a proof of concept / RFC.

The first five patches might be merge-ready, but their benefit is
quite low compared to the actual major change here.

The series goes on to copy our existing hash table implementation,
and modify it in steps to allow insertion of multiple data entries
with the same key. I've kept the series in steps corresponding to
the way I worked when modifying it, as I found it nice for clarity.
There is some obvious cleanups and squashing that will need to happen
before this can be considered for merging.

The major change is the last patch. This uses the new hash table in
our copy propagation pass. This effectively makes the algorithm
O(2n) instead of O(n^2), which is a big win. I tested with the
shader mentioned in [1] but took the shaders and made a shader_test
that I used in conjunction with shader-db to do testing.
I cut down on the ridiculous amount of expression some, to make it
even compile in a reasonable time on my poor laptop.

So, on to the results. Compilation of the aforementioned shader
went from 98 to 75 seconds. Perf shows that previously we spent
19% of the time walking the acp-table with _mesa_hash_table_next_entry.
After this series, the hash table is practically gone from the profile.
This is a major win, and I'm guite happy with the results.
There is obviously a lot more work to be done though.

Please leave critical feedback and ideas. This was merely a test
from my part, but it seems there is some opportunities here.

https://bugs.freedesktop.org/show_bug.cgi?id=94477

Thomas Helland (14):
  glsl: Don't rehash the values when copying to new table
  glsl: Don't compute the hash when we already have it available
  nir: Remove unused include of nir_array
  nir: Move nir_array to util, and rename to dyn_array
  glsl: Use dyn_array instead of the exec_list
  util: Make a copy of the existing hash table implementation
  util: Add field for pointing to next data
  util: Implement the insertion functionality
  util: Implement deletion of entries
  util: Add a comment about ordering of entries with matching keys
  util: Implement returning the last added entry on search
  util: Rename functions and structs
  util: Use hashing functions from hash_table.h
  glsl: Restructure copy propagation to use the non replacing hash table

 src/compiler/Makefile.sources                      |   1 -
 src/compiler/glsl/opt_copy_propagation.cpp         | 112 +++--
 .../glsl/opt_copy_propagation_elements.cpp         |   6 +-
 src/compiler/nir/nir_lower_locals_to_regs.c        |   1 -
 src/compiler/spirv/vtn_cfg.c                       |   6 +-
 src/compiler/spirv/vtn_private.h                   |   4 +-
 src/util/Makefile.sources                          |   3 +
 src/{compiler/nir/nir_array.h => util/dyn_array.h} |  18 +-
 src/util/non_replacing_hash_table.c                | 513 +++++++++++++++++++++
 src/util/non_replacing_hash_table.h                | 135 ++++++
 10 files changed, 743 insertions(+), 56 deletions(-)
 rename src/{compiler/nir/nir_array.h => util/dyn_array.h} (86%)
 create mode 100644 src/util/non_replacing_hash_table.c
 create mode 100644 src/util/non_replacing_hash_table.h

-- 
2.11.0