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

[Paul Berry]

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

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?