This is an archive of the discontinued LLVM Phabricator instance.

[ThinLTO] Subsume all importing checks into a single flag
ClosedPublic

Authored by tejohnson on Dec 29 2016, 4:26 PM.

Details

Summary

This adds a new summary flag NotEligibleToImport that subsumes
several existing flags (NoRename, HasInlineAsmMaybeReferencingInternal
and IsNotViableToInline). It also subsumes the checking of references
on the summary that was being done during the thin link by
eligibleForImport() for each candidate. It is much more efficient to
do that checking once during the per-module summary build and record
it in the summary.

I wonder whether test/ThinLTO/X86/autoupgrade.ll and
test/ThinLTO/X86/drop-debug-info.ll should be removed, since we
now must conservatively not import anything defined by an old
version of the bitcode?

Diff Detail

Repository
rL LLVM

Event Timeline

tejohnson updated this revision to Diff 82706.Dec 29 2016, 4:26 PM
tejohnson retitled this revision from to [ThinLTO] Subsume all importing checks into a single flag.
tejohnson updated this object.
tejohnson added a reviewer: mehdi_amini.
tejohnson added a subscriber: llvm-commits.
mehdi_amini edited edge metadata.Dec 29 2016, 4:48 PM

So we're losing some information for the ThinLink, which is somehow scary, I hope we won't have to backtrack later.
Originally we had these separate flags because we expected to propagate more information across modules. But I don't see any use-case that would miss these flags right now, so...

include/llvm/IR/ModuleSummaryIndex.h
125 ↗(On Diff #82706)

Seems to me that it is NotEligibleToImport.

127 ↗(On Diff #82706)

Delegate to the other Ctor:

GVFlags(const GlobalValue &GV, bool NotEligibleToImport)
    : GVFlags(GV.getLinkage(), NotEligibleToImport) {
...
lib/Analysis/ModuleSummaryAnalysis.cpp
191 ↗(On Diff #82706)

This can be moved a few lines above when creating Flags IIUC.

244 ↗(On Diff #82706)

I'm not sure if NonExternallyReferenceable is the best name, I feel it would be more accurate with CantBePromoted or something like that.
(Any local symbols is "not externally referenceable" in the absolute).

test/ThinLTO/X86/autoupgrade.ll
11 ↗(On Diff #82706)

This was an annoying an subtle bug, I'm concerned about losing coverage for this.
If there is no other way, we should regenerate the bitcode file with the new summary.
I'm wondering now if this test can't be triggered with llvm-link instead of llvm-lto. I'll try and report.

test/ThinLTO/X86/drop-debug-info.ll
5 ↗(On Diff #82706)

I'd be OK to drop this test

mehdi_amini added inline comments.Dec 29 2016, 4:56 PM
test/ThinLTO/X86/autoupgrade.ll
11 ↗(On Diff #82706)

r290736

mehdi_amini added inline comments.Dec 29 2016, 5:36 PM
test/ThinLTO/X86/autoupgrade.ll
11 ↗(On Diff #82706)

(and r290740)

So we're losing some information for the ThinLink, which is somehow scary, I hope we won't have to backtrack later.
Originally we had these separate flags because we expected to propagate more information across modules. But I don't see any use-case that would miss these flags right now, so...

Thinking through the individual flags, I am somewhat questioning whether NoRename should be split out. Here's what this patch folds into NotEligibleToImport, along with some thoughts on whether we could eventually import them:

  1. NoRename: can't import a def or a ref if local because that currently requires promotion/renaming. But what if in the future we would be able to import as a local copy? In that case it would be useful to split this out as a separate flag. But right now this is set when it is a local in a section - is it legal to create a copy in that case? If not, we would need to create a different flag for any non-renamable copyable cases that pop up in the future anyway.
  1. HasInlineAsmMaybeReferencingInternal: The only way we can ever safely import something that has opaque references (via inline asm) is if we also imported all locals in the llvm.*used sets as local copies, just to be safe. Not sure we would ever want to do that - I suppose we could eventually encounter a function that contains inline asm and locals in the used set that is profitable to import/inline, but do we want to carry around an extra bit in the summary before we find such a case?
  1. IsNotViableToInline: This one is a hint, not correctness, and currently only set when the function is variadic. If the inliner is ever able to inline variadic functions, we could just remove this flag (or stop setting the new NotEligibleToImport combined flag in that case). So I don't think it is currently worthwhile to split this out into a separate flag anyway. If we want to use inliner information for more complex importing decisions in the thin link I think this would have to be made into a richer set of flags anyway. Or would we ever want to import something that isn't inlineable? The only case I can think of is if it is also a local function that is non-renamable/promoteable, we want to import a reference to it, and we have the ability to import such non-renamable/promoteable local functions as local copies. In that case though, I would argue that we could simply stop marking these functions as NotEligibleToImport - it is just a small compile time/memory improvement anyway.
  1. Anything that references a non-renamable/promoteable local (what I am moving from the thin link to the summary generation with this patch). If we can import these referenced locals as a copy (see #1 above), then we will simply need to stop setting the NotEligibleToImport flag on references to those copyable non-renamable locals. Then once we decide to import any function, we'll need to walk through its references/calls and mark any such references for import (presumably the import logic will ensure that any local function marked for import that is also marked as non-renamable will be imported as a local copy). So I don't think we need to split this one out into a separate flag.

Thoughts?

include/llvm/IR/ModuleSummaryIndex.h
125 ↗(On Diff #82706)

Here I specifically meant that the parameter indicates it is a local that can't be renamed/promoted - it is only one of the things that goes into determining NotEligibleToImport. Rethinking - I will move the variadic check into the caller (it seems more appropriate to have this logic where we compute the summary index anyway), then I will just nuke this constructor and have it invoke the above one.

127 ↗(On Diff #82706)

Going to remove this one (see above comment)

lib/Analysis/ModuleSummaryAnalysis.cpp
191 ↗(On Diff #82706)

I assume you mean the "if (NotRenamableLocal) ... " handling (in phab it looks like it's on the lines above). Yes, I can move this.

244 ↗(On Diff #82706)

Ok, I can change the name. I was trying to find a name that indicates it is 1) a local (currently) and 2) can't be renamed/promoted. I think CantBePromoted is sufficiently descriptive.

test/ThinLTO/X86/autoupgrade.ll
11 ↗(On Diff #82706)

Great thanks, forgot about that functionality.

test/ThinLTO/X86/drop-debug-info.ll
5 ↗(On Diff #82706)

I'll go ahead and give it the same treatment you did to the other test (using llvm-link).

mehdi_amini added inline comments.Dec 30 2016, 10:58 AM
lib/Analysis/ModuleSummaryAnalysis.cpp
191 ↗(On Diff #82706)

I meant FuncSummary->setNotEligibleToImport();.

IIUC it could be:

bool NonRenamableLocal = isNonRenamableLocal(F);
bool IsEligibleForImport = NonRenamableLocal || HasInlineAsmMaybeReferencingInternal
GlobalValueSummary::GVFlags Flags(F, IsEligibleForImport);
test/ThinLTO/X86/drop-debug-info.ll
5 ↗(On Diff #82706)

That's not equivalent though: the other test was stressing bitcode loading, it could be done equally with llvm-link.
This test was making sure we correctly "upgrade" the debug info before linking the IR in FunctionImport.cpp (IIRC). Changing to llvm-link won't exercise this code-path and we'll lose this coverage anyway.
Thinking about it again, we may be able to do it with opt -functionimport though

So we're losing some information for the ThinLink, which is somehow scary, I hope we won't have to backtrack later.
Originally we had these separate flags because we expected to propagate more information across modules. But I don't see any use-case that would miss these flags right now, so...

Thinking through the individual flags, I am somewhat questioning whether NoRename should be split out. Here's what this patch folds into NotEligibleToImport, along with some thoughts on whether we could eventually import them:

  1. NoRename: can't import a def or a ref if local because that currently requires promotion/renaming. But what if in the future we would be able to import as a local copy? In that case it would be useful to split this out as a separate flag. But right now this is set when it is a local in a section - is it legal to create a copy in that case? If not, we would need to create a different flag for any non-renamable copyable cases that pop up in the future anyway.

It is likely that we'd need a separate flag to express the legality of the copy anyway.
So it would be NotEligibleForImport (implicitly "as available_externally"), but another flag could say CanBeDuplicated (straw man name).
The logic in the thin-link is likely gonna be easier this way (less special case or combination to check).

That said we'll need to be careful about what we do with the promotion, I suspect we want to assert (I mean when assertions are enabled) that all the local selected for global promotion passes the existing NoRename test.
This is because now when a function foo references a local bar, but bar is marked as NotEligibleForImport, we still allow to import foo and bar will be promoted. We have no way during the thin-link to check that bar wasn't originally NoRename.
Of course it "shouldn't" be a problem if the logic is right, but with us reading back bitcode with this flag, any fix to the detection of NoRename (or consistency) would be problematic.
(It may not be practical or easy to check this in the backend though).

  1. IsNotViableToInline: This one is a hint, not correctness, and currently only set when the function is variadic. If the inliner is ever able to inline variadic functions, we could just remove this flag (or stop setting the new NotEligibleToImport combined flag in that case). So I don't think it is currently worthwhile to split this out into a separate flag anyway. If we want to use inliner information for more complex importing decisions in the thin link I think this would have to be made into a richer set of flags anyway. Or would we ever want to import something that isn't inlineable?

Till here I follow. And I don't see why we would import something that isn't inlinable.

The only case I can think of is if it is also a local function that is non-renamable/promoteable, we want to import a reference to it, and we have the ability to import such non-renamable/promoteable local functions as local copies. In that case though, I would argue that we could simply stop marking these functions as NotEligibleToImport - it is just a small compile time/memory improvement anyway.

If it is also a function that is NoRename , then we'll apply the logic in 1) above, but this seems orthogonal.

  1. Anything that references a non-renamable/promoteable local (what I am moving from the thin link to the summary generation with this patch). If we can import these referenced locals as a copy (see #1 above), then we will simply need to stop setting the NotEligibleToImport flag on references to those copyable non-renamable locals. Then once we decide to import any function, we'll need to walk through its references/calls and mark any such references for import (presumably the import logic will ensure that any local function marked for import that is also marked as non-renamable will be imported as a local copy).

I wonder if instead of stopping to set the NotEligibleToImport flag for such cases, we may be better to add another flag CanBeImportedWithRefCopy. That's because it'd avoid inspecting all the refs of all the global consider for importing, and only do it when CanBeImportedWithRefCopy is set.

So I don't think we need to split this one out into a separate flag.

Right.

mehdi_amini added inline comments.Dec 30 2016, 11:41 AM
test/ThinLTO/X86/drop-debug-info.ll
5 ↗(On Diff #82706)

Thinking more, the best would likely be to refactor llvm-link to call FunctionImporter::importFunctions. It is silly to have this custom logic in llvm-link.

So we're losing some information for the ThinLink, which is somehow scary, I hope we won't have to backtrack later.
Originally we had these separate flags because we expected to propagate more information across modules. But I don't see any use-case that would miss these flags right now, so...

Thinking through the individual flags, I am somewhat questioning whether NoRename should be split out. Here's what this patch folds into NotEligibleToImport, along with some thoughts on whether we could eventually import them:

  1. NoRename: can't import a def or a ref if local because that currently requires promotion/renaming. But what if in the future we would be able to import as a local copy? In that case it would be useful to split this out as a separate flag. But right now this is set when it is a local in a section - is it legal to create a copy in that case? If not, we would need to create a different flag for any non-renamable copyable cases that pop up in the future anyway.

It is likely that we'd need a separate flag to express the legality of the copy anyway.
So it would be NotEligibleForImport (implicitly "as available_externally"), but another flag could say CanBeDuplicated (straw man name).
The logic in the thin-link is likely gonna be easier this way (less special case or combination to check).

That said we'll need to be careful about what we do with the promotion, I suspect we want to assert (I mean when assertions are enabled) that all the local selected for global promotion passes the existing NoRename test.

Which test? The promotion logic in FunctionImportUtils (which happens in the backend) was already not able to assert on the NoRename flag when renaming on import since we may not have summaries for all references being imported (in the distributed backend case).

Or are you suggesting adding back the NoRename flag to the summary, and adding a check in the thin link (presumably after we decide on imports, to check that no imported ref is a local marked NoRename)?

This is because now when a function foo references a local bar, but bar is marked as NotEligibleForImport, we still allow to import foo and bar will be promoted. We have no way during the thin-link to check that bar wasn't originally NoRename.
Of course it "shouldn't" be a problem if the logic is right, but with us reading back bitcode with this flag, any fix to the detection of NoRename (or consistency) would be problematic.
(It may not be practical or easy to check this in the backend though).

  1. IsNotViableToInline: This one is a hint, not correctness, and currently only set when the function is variadic. If the inliner is ever able to inline variadic functions, we could just remove this flag (or stop setting the new NotEligibleToImport combined flag in that case). So I don't think it is currently worthwhile to split this out into a separate flag anyway. If we want to use inliner information for more complex importing decisions in the thin link I think this would have to be made into a richer set of flags anyway. Or would we ever want to import something that isn't inlineable?

Till here I follow. And I don't see why we would import something that isn't inlinable.

Only import as a copy for a reference we want to import/inline, as described below.

The only case I can think of is if it is also a local function that is non-renamable/promoteable, we want to import a reference to it, and we have the ability to import such non-renamable/promoteable local functions as local copies. In that case though, I would argue that we could simply stop marking these functions as NotEligibleToImport - it is just a small compile time/memory improvement anyway.

If it is also a function that is NoRename , then we'll apply the logic in 1) above, but this seems orthogonal.

Right (i.e. mark with a new "CanBeDuplicated" flag).

  1. Anything that references a non-renamable/promoteable local (what I am moving from the thin link to the summary generation with this patch). If we can import these referenced locals as a copy (see #1 above), then we will simply need to stop setting the NotEligibleToImport flag on references to those copyable non-renamable locals. Then once we decide to import any function, we'll need to walk through its references/calls and mark any such references for import (presumably the import logic will ensure that any local function marked for import that is also marked as non-renamable will be imported as a local copy).

I wonder if instead of stopping to set the NotEligibleToImport flag for such cases, we may be better to add another flag CanBeImportedWithRefCopy. That's because it'd avoid inspecting all the refs of all the global consider for importing, and only do it when CanBeImportedWithRefCopy is set.

So I don't think we need to split this one out into a separate flag.

Right.

It sounds like you are arguing for a separate flag (CanBeImportedWithRefCopy) just above? Or do you mean once we add the copy ability (i.e. for now just set NotEligibleToImport)?

test/ThinLTO/X86/drop-debug-info.ll
5 ↗(On Diff #82706)

That sounds like a good change to make at some point, for now I will change this test to use opt -function-import though.

So we're losing some information for the ThinLink, which is somehow scary, I hope we won't have to backtrack later.
Originally we had these separate flags because we expected to propagate more information across modules. But I don't see any use-case that would miss these flags right now, so...

Thinking through the individual flags, I am somewhat questioning whether NoRename should be split out. Here's what this patch folds into NotEligibleToImport, along with some thoughts on whether we could eventually import them:

  1. NoRename: can't import a def or a ref if local because that currently requires promotion/renaming. But what if in the future we would be able to import as a local copy? In that case it would be useful to split this out as a separate flag. But right now this is set when it is a local in a section - is it legal to create a copy in that case? If not, we would need to create a different flag for any non-renamable copyable cases that pop up in the future anyway.

It is likely that we'd need a separate flag to express the legality of the copy anyway.
So it would be NotEligibleForImport (implicitly "as available_externally"), but another flag could say CanBeDuplicated (straw man name).
The logic in the thin-link is likely gonna be easier this way (less special case or combination to check).

That said we'll need to be careful about what we do with the promotion, I suspect we want to assert (I mean when assertions are enabled) that all the local selected for global promotion passes the existing NoRename test.

Which test? The promotion logic in FunctionImportUtils (which happens in the backend) was already not able to assert on the NoRename flag when renaming on import since we may not have summaries for all references being imported (in the distributed backend case).

I meant that before we were verifying during the import that we don't import a function that references a function that can't be renamed, because we had this information. Now we don't, so the importer is not explicitly checking.
It's not critical, I guess was can trust the information to be correct, I was imagining that an assertion in the backend would help debugging "when things go wrong".

Or are you suggesting adding back the NoRename flag to the summary

No, I was really imagining checking *on the IR* during the backend that what we asked the `backend to do during the ThinLink is not violating anything.

  1. Anything that references a non-renamable/promoteable local (what I am moving from the thin link to the summary generation with this patch). If we can import these referenced locals as a copy (see #1 above), then we will simply need to stop setting the NotEligibleToImport flag on references to those copyable non-renamable locals. Then once we decide to import any function, we'll need to walk through its references/calls and mark any such references for import (presumably the import logic will ensure that any local function marked for import that is also marked as non-renamable will be imported as a local copy).

I wonder if instead of stopping to set the NotEligibleToImport flag for such cases, we may be better to add another flag CanBeImportedWithRefCopy. That's because it'd avoid inspecting all the refs of all the global consider for importing, and only do it when CanBeImportedWithRefCopy is set.

So I don't think we need to split this one out into a separate flag.

It sounds like you are arguing for a separate flag (CanBeImportedWithRefCopy) just above? Or do you mean once we add the copy ability (i.e. for now just set NotEligibleToImport)?

Yes, that's what I meant.

So we're losing some information for the ThinLink, which is somehow scary, I hope we won't have to backtrack later.
Originally we had these separate flags because we expected to propagate more information across modules. But I don't see any use-case that would miss these flags right now, so...

Thinking through the individual flags, I am somewhat questioning whether NoRename should be split out. Here's what this patch folds into NotEligibleToImport, along with some thoughts on whether we could eventually import them:

  1. NoRename: can't import a def or a ref if local because that currently requires promotion/renaming. But what if in the future we would be able to import as a local copy? In that case it would be useful to split this out as a separate flag. But right now this is set when it is a local in a section - is it legal to create a copy in that case? If not, we would need to create a different flag for any non-renamable copyable cases that pop up in the future anyway.

It is likely that we'd need a separate flag to express the legality of the copy anyway.
So it would be NotEligibleForImport (implicitly "as available_externally"), but another flag could say CanBeDuplicated (straw man name).
The logic in the thin-link is likely gonna be easier this way (less special case or combination to check).

That said we'll need to be careful about what we do with the promotion, I suspect we want to assert (I mean when assertions are enabled) that all the local selected for global promotion passes the existing NoRename test.

Which test? The promotion logic in FunctionImportUtils (which happens in the backend) was already not able to assert on the NoRename flag when renaming on import since we may not have summaries for all references being imported (in the distributed backend case).

I meant that before we were verifying during the import that we don't import a function that references a function that can't be renamed, because we had this information. Now we don't, so the importer is not explicitly checking.
It's not critical, I guess was can trust the information to be correct, I was imagining that an assertion in the backend would help debugging "when things go wrong".

Or are you suggesting adding back the NoRename flag to the summary

No, I was really imagining checking *on the IR* during the backend that what we asked the `backend to do during the ThinLink is not violating anything.

Ah ok, that's more than what we do currently. Do you think I should add that to this patch?

test/ThinLTO/X86/drop-debug-info.ll
5 ↗(On Diff #82706)

Actually, opt -function-import has the same issues as llvm-lto - it won't decide to import after this patch. I went ahead and reworked llvm-link to use the FunctionImporter, and changed this test to use it (D28277). I'll remove this change from the patch.

Ah ok, that's more than what we do currently. Do you think I should add that to this patch?

Not necessarily: it'd be nice to have such validation of the expected invariant, but I have no idea how much work it is, so if you think you can do it in ~30min, I'd say "yes please", otherwise I would't require it for us to move forward. Sounds reasonable?

Ah ok, that's more than what we do currently. Do you think I should add that to this patch?

Not necessarily: it'd be nice to have such validation of the expected invariant, but I have no idea how much work it is, so if you think you can do it in ~30min, I'd say "yes please", otherwise I would't require it for us to move forward. Sounds reasonable?

I went ahead and added this in the new patch I am uploading.

include/llvm/IR/ModuleSummaryIndex.h
125 ↗(On Diff #82706)

Removed this constructor, moved variadic check to module summary builder.

127 ↗(On Diff #82706)

ditto

lib/Analysis/ModuleSummaryAnalysis.cpp
191 ↗(On Diff #82706)

Done (but with variable being NotEligibleToImport not IsEligibleToImport)

244 ↗(On Diff #82706)

done

tejohnson updated this revision to Diff 83060.Jan 4 2017, 8:38 AM
tejohnson edited edge metadata.

Address review comments

LGTM, but have you checked that the number of imports is unchanged on a few apps with this?

lib/Transforms/Utils/FunctionImportUtils.cpp
89 ↗(On Diff #83060)

Assert are compiled out in NDEBUG mode, I think it won't do anything.

You may compile out this function entirely in #ifndef NDEBUG (and its declaration) so it can't be called.

mehdi_amini accepted this revision.Jan 4 2017, 9:21 PM
mehdi_amini edited edge metadata.
This revision is now accepted and ready to land.Jan 4 2017, 9:21 PM

LGTM, but have you checked that the number of imports is unchanged on a few apps with this?

Just confirmed they are the same for SPEC benchmarks gcc and xalancbmk.

lib/Transforms/Utils/FunctionImportUtils.cpp
89 ↗(On Diff #83060)

Good point. I changed to compile out the function completely under NDEBUG.

tejohnson updated this revision to Diff 83229.Jan 5 2017, 6:39 AM
tejohnson edited edge metadata.

Address last review comments.

This revision was automatically updated to reflect the committed changes.