[Mesa-dev] [PATCH 1/4] Revert "glsl: Skip processing the first function's body in do_dead_functions()."

[Paul Berry]

On 1 August 2011 17:35, Ian Romanick <idr at freedesktop.org> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 08/01/2011 04:07 PM, Paul Berry wrote:
>> opt_dead_functions contained a shortcut to skip processing the first
>> function's body, based on the assumption that IR functions are
>> topologically sorted, with callees always coming before their callers
>> (therefore the first function cannot contain any calls).
>
> After linking, that is absolutely true.
>
> When linking, we start with an empty shader.  Then we find main, and
> pull it in.  For each function pulled in (initially just main), we
> recursively pull in all the called functions.
>
> In the absence of cycles (i.e., recursion), that should guarantee the
> desired sort order.  Right?

Hmm, what you say makes sense, but there must be something more subtle
going on, because what led me to make this patch was that I first
tried writing the rest of the patch series, and then when I tested it
I ran into problems because at link time, the functions weren't sorted
in callee-to-caller order.

I will investigate things further in the morning and let you know what I find.

>
>> This assumption turns out not to be true in general.  For example, the
>> following code snippet gets translated to IR that violates this
>> assumption:
>>
>>     void f();
>>     void g();
>>     void f() { g(); }
>>     void g() { ... }
>>
>> In practice, the shortcut didn't cause bugs because of a coincidence
>> of the circumstances in which opt_dead_functions is called:
>>
>> (a) we do inlining right before dead function elimination, and
>>     inlining (when successful) eliminates all calls.
>>
>> (b) for user-defined functions, inlining is always successful, because
>>     previous optimization passes (during compilation) have reduced
>>     them to a form that is eligible for inlining.
>>
>> (c) the function that appears first in the IR can't possibly call a
>>     built-in function, because built-in functions are always emitted
>>     before the function that calls them.
>>
>> It seems unnecessarily fragile to have opt_dead_functions depend on
>> these coincidences.  And the next patch in this series will break (c).
>
> In any case, that is probably true.  I have this notion in the back of
> mind for rewriting the function inliner.  As part of that, I've been
> thinking about adding ir_function_signature::is_leaf for functions that
> do not contain any calls.  The seen_another_function_signature flag here
> is sort of a rough approximation of an is_leaf flag.  Using the is_leaf
> flag instead should actually make performance better.

That's an intriguing idea, and it meshes well with some things Eric
was saying today, about how some of our optimization stages spend a
lot of time digging around the IR looking for something that we might
know a priori isn't there (e.g. if a shader never calls a texture
lookup function, there's no reason we would ever need to call
do_lower_texture_projection()).  Your is_leaf idea could be the first
of several optimizations of this kind.

>
>> So I'm reverting the shortcut.  The consequence will be a slight
>> increase in link time for complex shaders.
>>
>> This reverts commit c75427f4c8767e131e5fb3de44fbc9d904cb992d.
>> ---
>>  src/glsl/opt_dead_functions.cpp |   11 +----------
>>  1 files changed, 1 insertions(+), 10 deletions(-)
>>
>> diff --git a/src/glsl/opt_dead_functions.cpp b/src/glsl/opt_dead_functions.cpp
>> index 7c64c61..51c77e3 100644
>> --- a/src/glsl/opt_dead_functions.cpp
>> +++ b/src/glsl/opt_dead_functions.cpp
>> @@ -50,7 +50,6 @@ public:
>>     ir_dead_functions_visitor()
>>     {
>>        this->mem_ctx = ralloc_context(NULL);
>> -      this->seen_another_function_signature = false;
>>     }
>>
>>     ~ir_dead_functions_visitor()
>> @@ -65,8 +64,6 @@ public:
>>
>>     bool (*predicate)(ir_instruction *ir);
>>
>> -   bool seen_another_function_signature;
>> -
>>     /* List of signature_entry */
>>     exec_list signature_list;
>>     void *mem_ctx;
>> @@ -97,13 +94,7 @@ ir_dead_functions_visitor::visit_enter(ir_function_signature *ir)
>>        entry->used = true;
>>     }
>>
>> -   /* If this is the first signature to look at, no need to descend to see
>> -    * if it has calls to another function signature.
>> -    */
>> -   if (!this->seen_another_function_signature) {
>> -      this->seen_another_function_signature = true;
>> -      return visit_continue_with_parent;
>> -   }
>> +
>>
>>     return visit_continue;
>>  }
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/
>
> iEYEARECAAYFAk43RlkACgkQX1gOwKyEAw/8fACgmRSrAJpDwOHrKdpPgapzoaHZ
> ShoAn3Suwp/ON23kYtYE6ORe3U3r5mF8
> =Qyu8
> -----END PGP SIGNATURE-----
>