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

[Thomas Helland]

So I've discovered the issue. I wasn't inserting into both tables.
So we never did any copy propagation. So that was stupid.
Now it assertion fails in _insert_pre_hashed as hashing the
key does not return the same result as the supplied hash.
I'll look more into this some time during the week.

2017-01-01 22:53 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
> Darn it. There appears to be a functional change with patch 14.
> My changes where meant to make no functional change,
> so something is fishy. An example from the public shader-db:
>
> cycles HURT:   ./shaders/tesseract/205.shader_test VS vec4:      54 ->
> 100 (85.19%)
>
> I'll see if I can find some time to debug this during the week.
> If anyone immediately sees the issue, please let me know.
>
> I guess I should write some make-check tests for the new
> hash table, as I suspect that that is where the issue is.
>
> - Thomas
> 2017-01-01 20:41 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
>> Oh, and an important disclaimer.
>> I have not ran this through picking, nor have I done a complete
>> run of shader-db for performance comparisons on more realistic workloads.
>> I'll see what time I can find this evening, or some time tomorrow.
>>
>>
>> On Jan 1, 2017 19:38, "Thomas Helland" <thomashelland90 at gmail.com> wrote:
>>
>> 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
>>
>>