[LLVMdev] [lld] alias atoms and LayoutPass

[Rui Ueyama]

On Thu, Feb 12, 2015 at 12:56 PM, Shankar Easwaran <shankare at codeaurora.org>
wrote:

> On 2/12/2015 2:26 PM, Rui Ueyama wrote:
>
>> Looks like there's a bug. It's weird that the existing test didn't catch
>> that. I'll probably need to fix the ordinal of alias atoms.
>>
>> LayoutPass is retired peacefully. I know that code very well, because
>> after
>> you added code to that file for follow-on/followed-by relations, I spend
>> so
>> much effort improving that functionality while keeping the original
>> intention. I refactored it for readability, fixed various bugs, improved
>> performance (originally it was even quadratic), and added bunch of
>> (overly-designed in hindsight) assertions to verify that too-flexible
>> complex data structure is in a well-formed shape. Eventually I had to
>> conclude that this was not a good design after all -- it was too
>> complicated compared to what it would do. So I cannot agree.
>>
> The whole point of LayoutPass was it was reference based previously and
> now its ordinal based. It was more generic previously(though we didnt need
> that complexity).


Shankar,

You made a good point that the previous design was more generic. The point
is that being more generic is not always a good thing. It comes with cost,
and the cost could be very high. For example, I've seen many systems whose
configuration file is actually Turing complete like a scripting language.
It was sometimes extremely hard to understand a config file and no one even
tried to touch it. Generic systems are tend to be hard to understand.
Choosing the right balance is important.

As to LayoutPass, we basically wanted to do some sort of topological
sorting on the graph of atoms. Conceptually it sounds easy but in reality
it's far from that. Of course we had to guarantee there's no loop in the
graph. Atoms had layout-after and layout-before edges to force the sorting
order. Because nodes in the graph are for some reason doubly-linked, we had
to guarantee that the forwarding and reversing edges are consistent. Also
there's a notion of zero-length atom, and they are allowed to be at
anywhere in the sort result (A -> B and A -> C are both allowed, if either
B or C is zero-length, but if B and C are not empty, they are not allowed
to be laid out out after A).

And the situation was even worse -- we also used other signals to order
atoms, like from which file an atom is created. We sometimes use layout
edges, and sometimes not. We had to guarantee that they are consistent.

If you wanted to update the graph, you had to be cautious not to break that
consistency. It's not like "hey, we want to layout this thing after that,
so just add layout-after between them!" It was actually much harder than
that.

And what the LayoutPass was actually doing? It's just laying out atoms in
the same order as in the command line! We constructed a graph, mutated that
carefully not to break the consistency, ran series of complex graph
algorithms, and what we got is the same layout as in the input.

That's apparently not the right balance.

I think what's clear now is forcing some layout using graph is actually
complicated than one might think. Graph is much more flexible than plain
linear total ordering. When we try to collapse the graph into an
one-dimensional array in deterministic order, we need to make many subtle
choices of how to order them. Conversely, we had to be careful when we
construct the graph so that the graph is eventually reducible to a linear
array.

I hope this describes why I don't want to restore the LayoutPass.


> Shankar Easwaran
>
>  On Thu, Feb 12, 2015 at 10:44 AM, Shankar Easwaran <
>> shankare at codeaurora.org>
>> wrote:
>>
>>  Hi,
>>>
>>> It looks like the COFF reader creates an Alias atom by adding a
>>> kindLayoutAfter reference to the target atom. Now since the
>>> kindLayoutAfter
>>> passes are moved to machO how does it still work ?
>>>
>>> Does it work by chance because of ordinals ? I would think moving
>>> kindLayoutAfter references and having the LayoutPass would be a better
>>> choice.
>>>
>>> Shankar Easwaran
>>>
>>> --
>>> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
>>> by the Linux Foundation
>>>
>>>
>>>
>
> --
> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted
> by the Linux Foundation
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150212/9c1f0cae/attachment.html>