[LLVMdev] RFC: ThinLTO Impementation Plan

[Teresa Johnson]

On Fri, May 15, 2015 at 2:52 PM, David Blaikie <dblaikie at gmail.com> wrote:
>
>
> On Fri, May 15, 2015 at 1:15 PM, Teresa Johnson <tejohnson at google.com>
> wrote:
>>
>> On Fri, May 15, 2015 at 10:04 AM, David Blaikie <dblaikie at gmail.com>
>> wrote:
>> >
>> >
>> > On Fri, May 15, 2015 at 9:53 AM, Teresa Johnson <tejohnson at google.com>
>> > wrote:
>> >>
>> >> On Fri, May 15, 2015 at 9:20 AM, David Blaikie <dblaikie at gmail.com>
>> >> wrote:
>> >> >
>> >> >
>> >> > On Fri, May 15, 2015 at 9:18 AM, David Blaikie <dblaikie at gmail.com>
>> >> > wrote:
>> >> >>>
>> >> >>>
>> >> >>> >> - Marking of imported functions (for use in ThinLTO-specific
>> >> >>> >> symbol
>> >> >>> >> linking and global DCE, for example).
>> >> >>> >
>> >> >>> > Marking how?  Do you mean giving them internal linkage, or
>> >> >>> > something
>> >> >>> > else?
>> >> >>>
>> >> >>> Mentioned just after this: either an in-memory flag on the Function
>> >> >>> class, or potentially in the IR. For the prototype I just had a
>> >> >>> flag
>> >> >>> on the Function class.
>> >> >>
>> >> >>
>> >> >> Would this be anything other than "available externally" linkage?
>> >> >> (either
>> >> >> this module is responsible for emitting the definition of this
>> >> >> function
>> >> >> for
>> >> >> other modules to call, or it's not - if it's not, either this module
>> >> >> depends
>> >> >> on another module to provide a definition (this would be "available
>> >> >> externally") or it doesn't (this would be "internal" linkage")) - I
>> >> >> think...
>> >> >> though I'm sort of jumping into the middle of some of this &
>> >> >> might've
>> >> >> missed
>> >> >> some context, sorry.
>> >> >
>> >> >
>> >> > & I see your follow up further down in that thread:
>> >> >
>> >> > "There were only a couple minor tweaks required here (under the flag
>> >> > I
>> >> > added to the Function indicating that this was imported). Only
>> >> > promoted statics are remarked available_externally. For a
>> >> > non-discardable symbol that was imported, we can discard here since
>> >> > we
>> >> > are done with inlining (it is non-discardable in its home module)."
>> >> >
>> >> > &, like Duncan, I'll wait for more details on that front. (may or may
>> >> > not be
>> >> > useful to split some of these subthreads into separate email threads
>> >> > to
>> >> > keep
>> >> > discussion clear - but I'm not sure)
>> >>
>> >> I just went back and looked at my prototype and I had remembered this
>> >> wrong. An imported function is always marked
>> >> AvailableExternallyLinkage, unless it has link once linkage.
>> >>
>> >> As far as using that to indicate that it is an aux function, I was
>> >> concerned about overloading the meaning of that linkage type. See the
>> >> next para for an example where I am unsure about doing this...
>> >>
>> >> Looking back through my GlobalDCE changes, it looks like one of the
>> >> places I had changed (where we mark defined globals in runOnModule)
>> >> already has a guard for !hasAvailableExternallyLinkage and
>> >> !isDiscardableIfUnused, so my additional guard against marking
>> >> imported functions is unnecessary. But the other place I had to change
>> >> was in GlobalIsNeeded where it walks through the function and
>> >> recursively marks any referenced global as needed. Here there was no
>> >> guard against marking a global that is available externally as needed
>> >> if it is referenced. I had added a check here to not mark imported
>> >> functions as needed on reference unless they were discardable (i.e.
>> >> link once). Is this a bug - should this have a guard against marking
>> >> available externally function refs as needed?
>> >
>> >
>> > Duncan's probably got a better idea of what the right answer is here. I
>> > suspect "yes".
>> >
>> > The trick with available_externally is to ensure we keep these around
>> > for
>> > long enough that their definitions are useful (for inlining, constant
>> > prop,
>> > all that good stuff) but remove them before we actually do too much work
>> > on
>> > them, or at least before we emit them into the final object file.
>>
>> Yep, and that is exactly how long I want my imported functions to
>> stick around. Currently I have the ThinLTO import pass added at the
>> start of addLTOOptimizationPasses, just after the AA passes. So the
>> imported functions stick around through global opt, constant merge,
>> combining, and inlining. The call to GlobalDCE is just after inlining
>> and a second globalopt.
>>
>> >
>> > I imagine if GlobalDCE isn't removing available_externally functions
>> > it's
>> > because they're still useful in the optimization pipeline and something
>> > further down the pipe removes them (because they do, ultimately, get
>> > removed).
>>
>> That would be good to know, since if they are useful later on in the
>> pipe then presumably my imported functions could be as well. But I
>> wonder who is removing them since GlobalDCE isn't (if there are refs)?
>
>
> Yep - seems no one removes them (well, probably if there are no calls to the
> function at all they get removed as usual (eg: if all the calls are inlined
> we probably drop the function as we would for a linkonce_odr function)). If
> they're still around come codegen time, we just skip them:
>
> lib/CodeGen/MachineFunctionPass.cpp, MachineFunctionPass::runOnFunction:
>
> 33| bool MachineFunctionPass::runOnFunction(Function &F) {
> 34|   // Do not codegen any 'available_externally' functions at all, they
> have
> 35|   // definitions outside the translation unit.
> 36|   if (F.hasAvailableExternallyLinkage())
> 37|     return false;
> 38|
> 39|   MachineFunction &MF = getAnalysis<MachineFunctionAnalysis>().getMF();
> 40|   return runOnMachineFunction(MF);
> 41| }

Ok, thanks for digging this up. I guess that would work for the
imported functions as well, but it seems like a waste of compile time
if they are not useful after inlining/global opt. Is there any reason
to keep them past GlobalDCE or should I try changing GlobalDCE so that
it removes them?

>
>>
>>
>> > Any idea what problematic behavior you were seeing that was
>> > addressed by changing DCE to remove these functions was? I imagine
>> > whatever
>> > the bad behavior was, it could be demonstrated without ThinLTO and with
>> > a
>> > normal module with an available_externally function & would be worth
>> > discussing what the right behavior is in that context, regardless of
>> > ThinLTO.
>>
>> So I never changed GlobalDCE to eliminate available externally
>> functions in general, because I came at this with the view that I
>> shouldn't rely on just the linkage info. But I can certainly try that
>> experiment. What isn't clear to me is what all uses the available
>> externally linkage type currently - do you happen to know?
>>
>> Thanks,
>> Teresa
>>
>> >
>> >>
>> >>
>> >> There was one other change to GlobalDCE that I had to make, where we
>> >> erase the list of DeadFunctions from the module. In my case we may
>> >> have a function body that was eliminated, but still have references to
>> >> it (i.e. in the case I am talking about above). In that case it is now
>> >> just a declaration and we don't erase it from the function list on the
>> >> module. If the GlobalsIsNeeded code is changed to avoid marking
>> >> available externally function refs as needed then this change would be
>> >> needed for that case as well.
>> >>
>> >> Thanks,
>> >> Teresa
>> >>
>> >> >
>> >> >>
>> >> >>
>> >> >>
>> >> >> - David
>> >> >
>> >> >
>> >>
>> >>
>> >>
>> >> --
>> >> Teresa Johnson | Software Engineer | tejohnson at google.com |
>> >> 408-460-2413
>> >
>> >
>>
>>
>>
>> --
>> Teresa Johnson | Software Engineer | tejohnson at google.com | 408-460-2413
>
>



-- 
Teresa Johnson | Software Engineer | tejohnson at google.com | 408-460-2413