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

[Ian Romanick]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 08/02/2011 11:41 AM, Paul Berry wrote:
> On 1 August 2011 22:16, Paul Berry <stereotype441 at gmail.com> wrote:
>>
>> I will investigate things further in the morning and let you know what I find.
>>
> 
> Ok, I've spent a while looking through the linker code, and the rabbit
> hole goes deeper than I expected.  There are a number of reasons why
> the linker, as currently implemented, isn't guaranteed to be produce
> topologically sorted output:
> 
> 1. Linking doesn't actually start with an empty shader.  It starts
> with a clone of the compilation unit that defines main() (see
> linker.cpp around line 836).  This means that the order of functions
> defined in that compilation unit will be preserved regardless of the
> call graph.
> 
> 2. When resolving a function that's declared in the compilation unit
> that defines main(), but defined in some other compilation unit, the
> linker inserts the IR for that function wherever the declaration
> existed.  This means that the order of functions _declared_ in the
> compilation unit that defines main will be preserved too.
> 
> Problems 1 and 2 could be addressed by not cloning the IR for the
> compilation unit containing main, and instead using the algorithm you
> described.  But even if we did that, there's an additional problem:
> 
> 3. Linking is performed depth first.  This means that if main calls f
> which calls h, and main also calls g which calls h, then the linker
> first tries to pull in f, then h, and then finally g.  Since the
> linker emits functions at the head of the final linked program, the
> final order (assuming problems 1 and 2 are fixed) would be g, h, f,
> main.  This is the wrong order because g calls h.
> 
> This problem could be addressed by making the linker operate breadth
> first instead of depth first.  But even if we did that, there's still
> another problem:
> 
> 4. Since the linker emits functions at the head of the final linked
> program, if the linker brings in a function (let's call it f()) that
> wasn't declared in the compilation unit that defined main, it winds up
> at the beginning of the linked output, _before_ any global
> declarations.  If f() refers to a global variable, then the IR is
> invalid, because ir_dereference_variable nodes need to occur _after_
> the variables they declare (see ir_validate.cpp line 96).

It seems like it would be worth constructing a test case for this.  A
piglit test would be preferable.  If that's not possible, a unit test
would do.

There was a similar issue long, long ago, but I believe that it was
fixed.  I don't recall the details.

> This problem could be addressed by having the linker emit functions at
> the tail of the final linked program rather than at the head, but that
> would defeat the effort to make callees appear before their callers in
> the linker output.
> 
> There's one final problem, and this to me is the clincher:
> 
> 5. Since our IR groups together all overloaded functions that share
> the same name, there are (admittedly contrived) cases that would be
> impossible to topologically sort.  For example: if main calls f(int)
> which calls g(int), and main also calls g(float) which calls f(float),
> this is a valid program (there's no static recursion), but there's no
> way to order f and g such that callees come before their respective
> callers.
> 
> We could only address this problem by changing our IR format, or
> dropping the topological sort requirement.
> 
> In light of everything I've discovered this morning, my recommendation
> is to drop the topological sort requirement.  I haven't been able to
> find any code other than opt_dead_functions that relies on functions
> being topologically sorted, so unless I'm missing something, dropping
> the requirement is a simple matter of committing this patch.
> 
> In addition, I think we should change link_functions.cpp so that it
> emits functions at the tail of the final linked program rather than at
> the head, to fix problem #4.
> 
> Does this analysis seem right to you, Ian?

Paul, you continue to impress me.  Yeah, that all sounds right.  I had a
hard time believing #1 because I really thought I had implemented the
algorithm from my previous post.  Of course, the code and commit logs
don't lie.  I had thought of #5 shortly after hitting send, but I
decided it was too contrived to post a follow-up.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iEYEARECAAYFAk44oCUACgkQX1gOwKyEAw/TbgCfWTFDif+gDJmIwB1uCNn8U92k
a6sAn1BYZeJg3ZZE2B2aH2/3HO/sT2tf
=eLx4
-----END PGP SIGNATURE-----