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

[Thomas Helland]

2017-01-01 23:20 GMT+01:00 Thomas Helland <thomashelland90 at gmail.com>:
> 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.
>

Couldn't sleep until I'd found the issue. I was not setting the
hash when hitting the new insertion codepath. Adding this
makes things work, and reduces the functional changes to
just two shaders from tf2 that are seeing an increase of one
single instruction in their vertex shaders. But that's for another day.
As for the compile time; I've only given it a shader-db run on
normal shaders without disabling validation or nir optimizations.
(Apart from the aforementioned unrealistic shader from the bug).
It appears to give no noticeable difference, if something it
might regress performance ever so slightly. I'd have to do more
testing to verify if it has any major impact. It would not be
unlikely that it would cause some regressions on smaller
shaders though, as we are balancing hashing-overhead,
and the fact we are inserting into two tables,
with the overhead of array-traversal in the hash table.
Some thorough testing will be needed.

> 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
>>>
>>>