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.

LGTM with a couple wording suggestions. Thanks.

LGTM. Thanks for working on this!

Please do this kind of cleanup with post-commit review in the future.

If you feel strongly about this then go ahead, though if you're renaming this better to rename it lookUpAnalysis.

This is fine, but you can use post-commit review on this kind of thing.

Feel free to commit this kind of cleanup with post-commit review.

This type of cleanup can be done with post commit review btw.

This is fine, but it doesn't really matter; this is only called like once for an entire compilation (it's basically a hack to set a pipeline-global closure for a particular analysis; only AA uses it now)

Overall, I do like the idea of doing this and this LGTM (although let others chime in). One thing to think about is that if it takes this long to delete a file (even on tmpfs which Joerg mentioned), then how long does it take to allocate the memory for a new file? (let alone write it to disk)

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

nice to see this feature finally implemented!

This LGTM. Thanks for looking so closely at this! It's a very nice speedup!

Abandoning now that D27156 has landed.

Why are we unlinking at all? Hopefully we can just resize the file and ideally reuse most of the pages the kernel already has allocated. Doing so loses the atomicity of the replacement, but so does asynchronously unlinking like you do in this patch (although this patch would manifest the non-atomicity in a more benign way).

This is just wiring up the new machinery from D27198. Looks good.

This makes sense given your current trajectory for the new PM. LGTM with a nit.

Small fixup (delete some code that I forgot to remove in the last patch).

the original simple-minded constexpr containing a for-loop

Somewhat simpler template version. Let me know what you think. I think the improved clarity at the call site is worth it.

In D27156#608816, @ruiu wrote:

I agree that at the call side this looks better, but after reviewing the previous one again, I think I still prefer the previous one, because recursive templates are more complicated than the original simple-minded constexpr containing a for-loop. In practice, static_assert'ing on R_END would be enough as a protection.

Nice! The idea of storing current and next colors solves the nondeterminism in a very simple way!

Sorry for the delay.

I don't think that it makes sense to put this in a file with a generic name like "Concurrent", as this is a quite specialized data structure that depends on specific LLD types. Maybe just call it ConcurrentStringTableBuilder.h?
I'm a bit worried about the layering too, does this class introduce any circular dependencies?