<div dir="auto"><div>That is a very nice suggestion!</div><div dir="auto"><br></div><div dir="auto">I'll have a look at that, and see if I can hack a quick implementation.</div><div dir="auto">It would probably be much better than my multi-map approach.</div><div dir="auto">It felt like sort of a hack-fix on the current algorithm.</div><div dir="auto">Doing all replacements in one run would also be really nice,</div><div dir="auto">as my investigations have found copy propagation to be one of the</div><div dir="auto">few passes that benefit from multiple runs of the pass.</div><div dir="auto">It is not unlikely that some of the other passes that benefit from 3+</div><div dir="auto">runs of the pass get those late effects simply because copy propagation </div><div dir="auto">has not fully completed the work it can do until the second pass.</div><div dir="auto"><div class="gmail_extra" dir="auto"><br><div class="gmail_quote">On Dec 31, 2016 05:39, "Connor Abbott" <<a href="mailto:cwabbott0@gmail.com">cwabbott0@gmail.com</a>> wrote:<br type="attribution"><blockquote class="quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="quoted-text">On Fri, Dec 30, 2016 at 10:04 AM, Vladislav Egorov <<a href="mailto:vegorov180@gmail.com">vegorov180@gmail.com</a>> wrote:<br>
> Oh, thanks! A very nice torture case. However, it seems to be related to<br>
> another problem. The test case has no IF or LOOP blocks, so it can't be<br>
> possibly improved with speeding up the cloning of the table (the torture<br>
> case can be modified with a few ifs and fors on top though...).<br>
><br>
> Anyway, on Gallium the time goes down from 1.91s before my WIP patch to<br>
> 0.10s after my patch-series mostly due to improvements in<br>
> glsl_to_tgsi_visitor::copy_<wbr>propagation(). On Intel I don't see much of<br>
> improvement however: 157s (!) -> 132s.<br>
><br>
> Seems to be another case of linear scanning of the ACP table. Mesa has<br>
> several variations of the same copy propagation algorithm, and all of them<br>
> (with exception do_copy_propagation_elements that uses a hash-table)<br>
> linearly scan the entire table when they want to kill all the copies of a<br>
> variable. Which makes the implementation O(N^2) and blows up execution time<br>
> on huge functions like the ones from shadertoy. However most of the time it<br>
> still spends in tree_grafting that also uses all types of linear scans and<br>
> tree walks instead of lookup tables (ir_expression::get_num_<wbr>operands() gets<br>
> executed > 6 billion times!) -- I'll try to look into it.<br>
<br>
</div>Since the problem seemed interesting, I thought about it a little bit<br>
and realized that we could do something even better than what<br>
copy_propagation_elements does. Instead of having a hash table from<br>
ir_variables to ir_variables, we could have a hash table from<br>
ir_variable to acp_entry, where acp_entry contains the original<br>
variable as well as the acp_entry (*not* just the variable) we want to<br>
replace it with. That is, when we see a copy where we've never seen<br>
the lhs or rhs before, we insert two new acp_entry's and make one<br>
point to the other. To kill a variable, we would simply mark its<br>
associated acp_entry as dead and remove it from the table. When we go<br>
to look up a variable's replacement, we check if the acp_entry for the<br>
replacement is dead and ignore it if it is. That should make<br>
everything O(1) (assuming hash table lookup is O(1)) while being much<br>
simpler and probably faster than keeping a separate hash table of rhs<br>
variables.<br>
<br>
Another thing that would be potentially interesting is to recursively<br>
replace variables. Right now, with something like:<br>
<br>
bar = foo<br>
baz = bar<br>
... = baz<br>
<br>
we need two iterations of copy propagation in order to replace "baz"<br>
with "foo" on the rhs. If instead of looking up baz -> bar we looped<br>
through the acp_entry's until the replacement is killed or NULL, we<br>
could look up baz -> bar -> foo and do the whole thing in one shot.<br>
That might make some shaders require less iterations to reach a fixed<br>
point, helping compile times further.<br><br>
I haven't thought too much about copy_propagation_elements, but we<br>
could probably adapt it to do a similar thing too. Of course, we'd get<br>
less of a benefit out of that.<br>
<div class="elided-text"><br>
><br>
> Also, reading the bug report, I don't understand why did you treat<br>
> do_copy_propagation_elements() and do_copy_propagation() differently -- in<br>
> one case added hash-table for both sides of COPY(to, from), in another only<br>
> for one side?<br>
><br>
><br>
> <a href="tel:30.12.2016%2009" value="+13012201609">30.12.2016 09</a>:08, Tapani Pälli пишет:<br>
><br>
>><br>
>><br>
>> On 12/30/2016 05:53 AM, Vladislav Egorov wrote:<br>
>>><br>
>>> I've looked into it recently (I'm working on series of many various<br>
>>> trivial optimizations)<br>
>>><br>
>>> and it's faster to just memcpy() it. Just throwing out superfluous<br>
>>> hashing still keeps slow<br>
>>><br>
>>> hash-table insertion around -- with resizing, rehashing, memory<br>
>>> allocation/deallocation, internal<br>
>>><br>
>>> hash-function through integer division, collisions and so on. It<br>
>>> produces a nice speed improvement<br>
>>><br>
>>> actually. It's possible to explore approaches without any copying at<br>
>>> LOOP/IF entering at all,<br>
>>><br>
>>> but I am not sure it will improve performance.<br>
>><br>
>><br>
>> When profiling copy_propagation(_elements) pass you can use Martina's<br>
>> testcase from this bug:<br>
>><br>
>> <a href="https://bugs.freedesktop.org/show_bug.cgi?id=94477" rel="noreferrer" target="_blank">https://bugs.freedesktop.org/<wbr>show_bug.cgi?id=94477</a><br>
>><br>
>> We still have a very long compile time for the WebGL case mentioned in the<br>
>> bug so would be cool to have some optimizations there.<br>
>><br>
>><br>
>>><br>
>>> <a href="tel:30.12.2016%2002" value="+13012201602">30.12.2016 02</a>:49, Thomas Helland пишет:<br>
>>>><br>
>>>> Really, we should have some kind of function for copying the whole<br>
>>>> table,<br>
>>>> but this will work for now.<br>
>>>> ---<br>
>>>> src/compiler/glsl/opt_copy_<wbr>propagation.cpp | 6 ++++--<br>
>>>> 1 file changed, 4 insertions(+), 2 deletions(-)<br>
>>>><br>
>>>> diff --git a/src/compiler/glsl/opt_copy_<wbr>propagation.cpp<br>
>>>> b/src/compiler/glsl/opt_copy_<wbr>propagation.cpp<br>
>>>> index 247c498..e9f82e0 100644<br>
>>>> --- a/src/compiler/glsl/opt_copy_<wbr>propagation.cpp<br>
>>>> +++ b/src/compiler/glsl/opt_copy_<wbr>propagation.cpp<br>
>>>> @@ -210,7 +210,8 @@<br>
>>>> ir_copy_propagation_visitor::<wbr>handle_if_block(exec_list *instructions)<br>
>>>> /* Populate the initial acp with a copy of the original */<br>
>>>> struct hash_entry *entry;<br>
>>>> hash_table_foreach(orig_acp, entry) {<br>
>>>> - _mesa_hash_table_insert(acp, entry->key, entry->data);<br>
>>>> + _mesa_hash_table_insert_pre_<wbr>hashed(acp, entry->hash,<br>
>>>> + entry->key, entry->data);<br>
>>>> }<br>
>>>> visit_list_elements(this, instructions);<br>
>>>> @@ -259,7 +260,8 @@ ir_copy_propagation_visitor::<wbr>handle_loop(ir_loop<br>
>>>> *ir, bool keep_acp)<br>
>>>> if (keep_acp) {<br>
>>>> struct hash_entry *entry;<br>
>>>> hash_table_foreach(orig_acp, entry) {<br>
>>>> - _mesa_hash_table_insert(acp, entry->key, entry->data);<br>
>>>> + _mesa_hash_table_insert_pre_<wbr>hashed(acp, entry->hash,<br>
>>>> + entry->key, entry->data);<br>
>>>> }<br>
>>>> }<br>
>>>><br>
>>><br>
>>> ______________________________<wbr>_________________<br>
>>> mesa-dev mailing list<br>
>>> <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
>>> <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/<wbr>mailman/listinfo/mesa-dev</a><br>
><br>
><br>
> ______________________________<wbr>_________________<br>
> mesa-dev mailing list<br>
> <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
> <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/<wbr>mailman/listinfo/mesa-dev</a><br>
______________________________<wbr>_________________<br>
mesa-dev mailing list<br>
<a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
<a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/<wbr>mailman/listinfo/mesa-dev</a><br>
</div></blockquote></div><br></div></div></div>