LLD: Simplify LayoutPass

In r226336 I shove off 1.2 seconds out of 9.8 seconds for lld to link lld. That’s done by parallelizing archive member parsing. But I realized that was not the slowest pass.

The single slowest pass in LLD is LayoutPass. Only sort() at the last of Layoutpass::perform takes about 3 seconds (one third of total execution time). It is because the comparison function passed to sort, compareAtoms, does too much stuff.

It looks to me that the entire pass is overkill. We don’t really need that complexity there. I think nobody is actually depends on the details of the pass’s behavior.

I’d like to simplify LayoutPass, so that the pass sorts atoms only by file position and position in file (that means atoms are sorted in the same order as the command line.) I believe that should be enough and we can still keep output the same.

Any comments?

Does this mean you are going to kill the Layout specific references ?

The kindLayoutAfter, kindInGroup references are used to layout atoms by both Mach-O (atom order file) and ELF.

Shankar Easwaran

No, I’m not proposing to kill the layout references because components other than LayoutPass are using them.

I’ll start writing a patch. I’ll probably only modify LayoutPass.cpp and try to make it faster without affecting existing features.

Have you tried switching to a parallel sort? On windows I got a pretty
good perf increase by doing that.

I would also love to simplify this pass, as long as we make it clear
what guarantees we are making.

- Michael Spencer

> In r226336 I shove off 1.2 seconds out of 9.8 seconds for lld to link
lld.
> That's done by parallelizing archive member parsing. But I realized that
was
> not the slowest pass.
>
> The single slowest pass in LLD is LayoutPass. Only sort() at the last of
> Layoutpass::perform takes about 3 seconds (one third of total execution
> time). It is because the comparison function passed to sort,
compareAtoms,
> does too much stuff.
>
> It looks to me that the entire pass is overkill. We don't really need
that
> complexity there. I think nobody is actually depends on the details of
the
> pass's behavior.
>
> I'd like to simplify LayoutPass, so that the pass sorts atoms only by
file
> position and position in file (that means atoms are sorted in the same
order
> as the command line.) I believe that should be enough and we can still
keep
> output the same.
>
> Any comments?
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev@cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Have you tried switching to a parallel sort? On windows I got a pretty
good perf increase by doing that.

Done in r227132, but I only saw a minor performance increase.

I would also love to simplify this pass, as long as we make it clear
what guarantees we are making.

Yeah. I took a look at the history of the file to understand how the
feature set that pass currently provides was chosen, and found that some
features were introduced without clear reasoning and users of the features.
Now a few pieces of code depends on subtle behavior of the pass, I need to
understand the details first.