LGTM with a nit.

This is awesome, thanks for doing this Florian!

having the format be open-ended

It looks like this thread has evolved into a design discussion. It isn't clear to me that we all agree on what problem should be solved. Saleem, it seems like you have some interest in having the format be open-ended, while many others (myself included) seem to want this to be as locked-down as possible with a narrow set of really clearly defined operations. Saleem, could you maybe start an RFC on llvm-dev so we can have a higher-level design discussion? Off the top of my head, there are a couple things that have been mentioned in this thread but not really resolved:

In D40670#942340, @yaxunl wrote:

In D40670#942326, @arsenm wrote:

In D40670#942316, @yaxunl wrote:

In D40670#942232, @yaxunl wrote:

In D40670#941244, @nlopes wrote:

This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.

If whether alloca inst can be zero depending on target, then we need to make it target dependent. I will see if I can add this to TargetTransformInfo.

Well, this will incur lots of interface changes. Essentially all value tracking functions and passes relying on value tracking will require TargetTransformInfo. Do we want to do that?

On the other hand, on which specific target alloca inst could be null? As Matt said, alloca cannot be used to represent malloc, why alloca inst could be null?

AMDGPU currently has a workaround to avoid alloca ever returning 0. 0 is a valid pointer though. What we really want to represent is that alloca never returns an invalid pointer, not that it never has a 0 value

If the nullptr is not zero, Clang will generate proper instruction for comparing with non-zero nullptr value, so it is not an issue.

For the issue which this patch is trying to solve, we need to know if alloca can be zero to simplify icmp instruction. Knowing alloca inst is valid pointer is not sufficient to simplify icmp instruction.

So far, I do not see a specific target on which alloca inst could be zero. As an instruction used so extensively, I think it is reasonable to assume any alloca inst is non-zero, no matter what addr space it uses.

FWIW, this makes sense to me. (and I like the naming/path choices)

Sorry for the delay.

Seems pretty straightforward. LGTM.

One way to break up this large RefSCC is to notice that the fanout from the vtable ref edges in the ctors/dtors is contributing a lot to it being so large. If those edges are made more precise, then it can reduce the size. For example, by breaking the vtable ref edges we prevent the ref edges to virtual GetMetadata methods and so the huge RefSCC breaks up as I mentioned earlier.

In D36352#834258, @silvas wrote:

(it's a ref edge, but if we were to fully inline through GoogleOnceInit it would become a call edge. The actual dispatch to protobuf_AssignDesc_foo_2eproto happens through an external function though so we're saved)

In D36352#833455, @chandlerc wrote:

Really nice analysis. I hadn't gotten that far, so that is helpful. Sadly, the descriptor stuff being the source isn't too surprising to me.

Anyways, any thoughts about the patch itself? I've got at least one more fix prepared behind this.

Sorry, to be clear, the entire RefSCC is something like:

In D36352#833140, @chandlerc wrote:

In D36352#833118, @silvas wrote:

When compiling the IR for this file with 'opt' and 'O3', this patch reduces the total time by 8-9%.

Just as a point of reference, do you have handy how much of the total compile time are we spending in the PM's CGSCC / LCG stuff?

Yep, that's how I got here. Before all of my changes to LCG, we spent just under 40% of the total optimizer time (and nearly that much of the total compile time) in this one method.

Removing the parent sets made this method obnoxiously faster (over 2x) and shaved just over 20% off the total optimizer time.

This patch makes this method another 2x faster, and shaves 8% off the total optimizer time.

After both of these, this method remains the only thing hot really, and it is now between 6-8% depending on the noise in the profile. I'm still looking for more things to make faster here. I think i have another 2-4 things that will make it faster.

If we can speed up the overall time by 8-9% by improving it then it suggests that the total time is much larger, which I find somewhat surprising (presumably, we should be spending the vast majority of our time inside of the optimizations themselves).

Me too. Turns out this method is really, really hot.

Is this module you're working on just a really pathological case?

It is entirely possible this module is pathological -- I've not seen this when profiling other compiles.

Unfortunately, it is a pathological case that is *generated code* that for me, happens to represent like 10% of all the files we compile and many of the slowest files we compile. So even if this module is really, really weird I still need it to compile very fast. =]

Or is this maybe a situation where the denormalized ref edge representation is causing a bunch of extra work?

I'm sure this is part of the problem. But fixing this is (much) harder than making this routine fast. And it doesn't *appear* to be the primary problem. I instrumented this routine expecting to see removal of 100,000+ edges all the time and think "oh, so its denormalized...". That wasn't what happened. In this (potentially pathological) case, there are only like 7k ref edges ever removed in the entire opt run! And most (some 3.5k) are removed due to a *single* ref edge becoming dead after the inliner runs. The fact that the optimizer is deleting one edge at a time is pretty strong evidence that the denormalization isn't as prominent in this problem as I would have expected. I'm pretty sure based on these numbers that the real reason this ends up slow in this module is the size of RefSCC that we're removing edges from.

O0

When compiling the IR for this file with 'opt' and 'O3', this patch reduces the total time by 8-9%.

In D35276#812007, @jakehehrlich wrote:

Are you concerned about alignment in memory after loading? Since the virtual address is chosen by the user I don't think that matters. If there is ever a case where the loader chooses the virtual address based on alignment then I'd agree, we should tweak p_offset to account for maximum alignment. Otherwise I think having the first section's offset agree with the segment offset is more sensible because the user will be picking the virtual address and there's nothing we can do about that.

In D35276#809811, @jakehehrlich wrote:

If the alignment was set to be the maximum of all sections in the segment then an invalid case could occur where a section in the middle has a larger alignment than the first section and the segment would start at the offset of the first section while having an alignment that didn't agree with that offset.

I think you should be able to deal with most of those issues by sorting the list of sections with an appropriate sorting predicate that coalesces sections that need to be adjacent, which should be fairly unintrusive.

In D35276#807306, @jakehehrlich wrote:

This now sets offsets to be the minimum offset of a collection of sections but does not set file size or memory size. If no sections are specified the Offset is set to zero.

It is too fragile to manually specify file offsets. The actual layout that yaml2obj does right now should be considered opaque, such that any file offsets you could manually choose are "wrong" (even if they are incidentally correct with the current layout of sections that yaml2obj chooses).

Another possible naming convention that might avoid the scenario Matthias is worried about is all/everything like clang's -W options.

IIRC the intention was that in-tree work should not be burdened by experimental targets, up to and including breaking them. E.g. an in-tree API migration wouldn't have to update experimental targets. So in that sense LLVM_TARGETS_TO_BUILD=all is working as intended I think.

Thanks, I like this idea. We might want to do something similar for the tests.

If it is based on D33680 I presume it fixes https://bugs.llvm.org/show_bug.cgi?id=28414 also; would be good to mention that in the description too.

In D31145#707827, @paquette wrote:

In D31145#705994, @silvas wrote:

Why is it O(n) on average? It is two nested for loops with some bailouts that only affect the asymptotic runtime if candidates overlap with little-omega(1) other candidates. And it needs to be big-omega(sqrt(n)) if the runtime is to be reduced to even O(n^1.5).

Compiling for AArch64, for the SingleSource and MultiSource tests in the test suite the average length of a candidate is 10 MachineInstrs. The maximum length of a candidate is 108, which appears in a test with 11251 MachineInstrs. So far, it appears to be linear time on average, because for programs with a lot of candidates, the max length of a candidate is usually dominated by the number of candidates. I should really prove the bound though. It's a little tricky because it's O(m * n) where m is the maximum length of a candidate.

Hand waving/brain dump: The tricky case is where m = NumInstructions/k for k > 2 and n ~ O(NumInstructions). As k gets larger, m gets smaller. When m = 2, we only have to compare against one other candidate for each candidate, so we're good.

Previously, since we did some overlap pruning in the tree, we knew that as k gets smaller, the possible number of candidates in the program got smaller. Now that I think about it, that's not really true anymore. I guess the point here would be to show that we do the same number of overlap checks as in the tree here. But then we aren't really talking about pruneOverlaps, so ¯\_(ツ)_/¯

Btw, I think this is one of the clearest proofs that LLD has crossed a big milestone and is now entering "production quality". You don't see this kind of hack in a non-production-quality program.

Lgtm with a some suggestions that I don't feel too strongly about.

Overlapping candidates are now handled entirely by the pruneOverlaps method that handled anything the suffix tree pruning didn't handle. Since that method is on average O(n), this behaves far better.

In D30544#692075, @ruiu wrote:

I'd think we should continue handling it as an error. There are a few reasons:

1. The GNU linkers don't allow that (thank you George for investigating!). That means almost all Unix projects don't add non-object files to .a files, so in practice the current behavior is desirable for most people.

Nice to see this finally land!

btw, down the road you may want to have this pass really know in detail the encoded length of each instruction on x86. There are quite a few *single instructions* that would be beneficial from a code size perspective to outline (if the outlined function is set to have alignment of 1). A quick analysis of an LLD binary (which contains all of LLVM linked in for LTO) shows there is over 5% code size savings just from outlining single instructions (since many x86 instructions encode to be larger than a CALL instruction which is 5 bytes). About half of the benefit (so about 2-3% of the total on this test case) comes from instructions that reference the stack via %rsp (mostly zeroing out stack slots), which could still be outlined if the offset was rewritten.

In D26872#686220, @MatzeB wrote:

?!? This should be true for most compiler transformations. I don't know how these problems are handled in practice but I doubt they enable compiler optimizations. I don't see why we should start this discussion with this particular review.

In D26872#686175, @silvas wrote:

I'm not sure how heavily we care about this security aspect as a community, but I'm a slightly wary of having this on by default at any optimization level due to this issue.

Also, this pass will almost surely introduce timing side-channel attacks into cryptography code (code that would otherwise by "constant time" and needs to be for security).

I just tested on SPECCPU2006 (FullLTO) and no assertion failures!

FYI this doesn't build on Linux with gcc

LGTM

In D27900#683999, @ruiu wrote:

I don't understand why need "note:" labels in so many places. Why don't you just make error messages multi-line? I don't think there's no such rule that you need to put "note:" after every "\n".

In D27900#683228, @grimar wrote:

I think this patch currently implements idea of such output.
(or am I missing something ?)

In D27900#647823, @ruiu wrote:

Did you actually find that the current error message format is useless in some case? In my experience, the current format works pretty well. It prints out enough information to fix an error and not too verbose. If you still want to pursue this change, please split it, so that we can discuss each change instead of as a whole.

r295807, thanks! (and sorry for the delay)

Thanks, this LGTM. Do you need me to commit this for you?

This change does two things (as you mention in the description):

One key issue here is that this analysis mutates the IR, which is rarely done in LLVM, and I think we are trying to remove all cases of doing that (as Chandler puts it in http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf slide 17 "Forms a new, sub-set IR, which is problematic"). On that point, you probably want to start a discussion on LLVMdev (with a link to this review). I anticipate at least Chandler is going to have something to say about this w.r.t the new PM, so make sure to CC him.

LGTM.

Thanks for working on this!

In D29035#654536, @silvas wrote:

We have a chdir in lib/Basic/VirtualFileSystem.cpp that probably can be moved to using this API in a followup patch.

We have a chdir in lib/Basic/VirtualFileSystem.cpp that probably can be moved to using this API in a followup patch.

In D29045#653868, @davide wrote:

In D29045#653812, @davidxl wrote:

I won't mind adding documentation of the flags. Is there a known place to do so (for internal options)?

I personally wouldn't mind them to be added to https://clang.llvm.org/docs/UsersManual.html#profile-guided-optimization (maybe in a separate subsection). It's generally nicer having these flags documented somewhere than looking at the code, IMHO

Are you sure that this CONSTRUCTORS is trying to be a linker keyword? The nearby DATA_DATA is actually a macro expanded from http://src.illumos.org/source/xref/linux-master/include/asm-generic/vmlinux.lds.h#205
Is the CONSTRUCTORS still in file after it has been preprocessed? (I'm guessing so since otherwise this patch wouldn't fix the build, but just wanted to be sure).
Remember to keep in mind that these linker scripts all get preprocessed by the C preprocessor, so remember to look at the preprocessed linker script instead of the original source.

In case you're wondering, that didn't take that long to reduce to that point. Just have to learn the tools and workflow. We have amazing tools for doing test case reduction and an easily understandable test-suite build system! (mad props to those who made bugpoint; the folks that made test-suite awesome; and LLD's -save-temps; and a bit of -globalopt and -metarenamer to clean things up)

I did a quick run on SPEC CPU 2006 with FullLTO and it seems like I ran into 3 different assertion failures across various programs: https://reviews.llvm.org/P7954
There seem to be 3 different assertions getting hit.

Small nit.

It would be good to build up some verification machinery here at some point in the future.

I couldn't come up with a good name for this either. I described a design in my log here: https://docs.google.com/document/d/1-nrq2y_hTiZhrsJDmH8TzFjFEeApfccs6wwGyaXjSkg/edit#heading=h.ut7bc0x07mmh

Great work!

In D28444#639425, @ruiu wrote:

Sean,

I'm reluctant to change this type from std::string convert_to_slashes(StringRef) to void convert_to_slashes(SmallVectorImpl<char> &) as the former is easier to use than the latter. In some cases, you can avoid string copy with the latter type, but I think that's very important here. I don't want to optimize unless it is needed.

can you put the declaration/definition closer to sys::path::native? Other than that this LGTM.

And FWIW, based on my experience working on the new PM, I do agree that the new PM unit tests are currently harder to understand and debug than they need to be (for reasons that you outlined well in that LLVMdev thread years ago and in the description of this patch). Especially getting more useful error reports out when the tests fail would be fantastic, so I'd really like to see that aspect of gmock! When you post a patch updating some new PM tests to use gmock, definitely include some example error output from when the test fails.

I think that #2 is relatively rarely useful, but there *are* cases where
it is useful. Historically, I think misuse of actual mocking as
described in #2 has led to resistance towards this framework. I am
actually sympathetic to this -- mocking can easily be overused. However
I think this is not a significant concern in LLVM. First and foremost,
LLVM has very careful and rare exposure of abstract interfaces or
dependency injection, which are the most prone to abuse with mocks. So
there are few opportunities to abuse them. Second, a large fraction of
LLVM's unittests are testing *generic code* where mocks actually make
tremendous sense. And gmock is well suited to building interfaces that
exercise generic libraries. Finally, I still think we should be willing
to have testing utilities in tree even if they should be used rarely. We
can use code review to help guide the usage here.

Thoughts?

This is a good idea. Tar is a much more common format that users will be more familiar with. I'm not an expert on Tar files, so I can't review that part of the patch, but hopefully the bots will show if any tar implementations don't like the files we produce.

Nice! Thanks for adding the unittest too!

In D27855#626141, @spatel wrote:

This would be a good argument for Mehdi's suggestion? Ie, this should be in FunctionAttrs.cpp?

This transform seems like it is sensitive to the order in which functions are visited when running function passes, which I think we try to avoid. I.e. if the ordering is right, we can propagate across arbitrarily many transitive calls; but if the ordering is wrong (e.g. we visit callers before callees) then we don't be able to propagate as much.

Thanks for doing this, LGTM with a nit. Overall, it seems that keeping two copies for now is fine, since it is such a small amount of code.

A couple nits. Overall, this is looking a lot better. It's awesome that you sat down with Justin to hash this out.

In D27676#622851, @ruiu wrote:

I thought about this for a while. I'd say that having foo.a(foo.o)(foo.c) and foo.o(foo.c) are not correct because they are inconsistent. If the former were foo.a(foo.o(foo.c)), the two are at least consistent, but I guess that's hard to read.

We have a lot of combinations here.

• Is an object file in an archive file? Yes or no
• Do we know source filename? Yes or not
• What do we know about the error location inside of the object file: Line number in the original source code, section name in an object file, or nothing

Committed in r289733

Update local variable name to be more consistent.

In D27778#622811, @davide wrote:

I am in favour of this change. I think the name is quite explanatory/clear.
Oracle docs (https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter6-54839.html) use the wording "storage unit affected by the reloc", but I prefer target =)

In D27676#621721, @ruiu wrote:

I think my concern is that we are going to print out at most three filenames like this

foo.a(foo.o)(foo.c)

and that error string format looks odd. It is indistinguishable from

foo.o(foo.c)

where in this case foo.o is not an archive but an object file. I think we are using too many parentheses.

A couple more small comments as take another pass looking at the patch.

A couple suggestions to make this patch more understadable.

LGTM with nits.

Some stylistic comments.

Simon has done a pretty good job with the style review. Once his comments are cleaned up it will be easier to provide further comments.

Also, uhm, this needs tests. Maybe you can get away with just adding some more RUN lines to some LegacyGVN tests?

When running with just a single core, can we still do a sharded visitation, but instead of doing NumShards passes through all the pieces (skipping ones not in the current shard), only do a single pass? We should be able to get identical layout in that case.

In D27374#613686, @jlebar wrote:

if you're renaming this better to rename it lookUpAnalysis.

I left it as "lookUpPass" because a lot of the analysis code talks about "passes", or sometimes "analysis passes".

Should we excise mentions of "pass" from the analysis parts? I can write that patch if you think it's the terminology we want to adopt.