llvm dev - Mar 2016 - Deleting function IR after codegen

Hi all

After codegen for a given function, the IR should no longer be needed.  In the
AsmPrinter we convert from MI->MCInstr, and then we never go back and look at
the IR during the MC layer.

I’ve prototyped a simple pass which can be (optionally) scheduled to do just
this.  It is added at the end of addPassesToEmitFile.  It is optional so that
clang can continue to leak the IR with --disable-free, but i would propose that
all other tools, and especially LTO, would enable it.  The savings are 20% of
peak memory in LTO of clang itself.

I could attach a patch, but first i’d really like to know if anyone is
fundamentally opposed to this.

I should note, a couple of issues have come up in the prototype.
- llvm::getDISubprogram was walking the function body to find the subprogram. 
This is trivial to fix as functions now have !dbg on them.
- The AsmPrinter is calling canBeOmittedFromSymbolTable on GlobalValue’s which
then walks all their uses.  I think this should be done earlier in codegen as an
analysis whose results are available to the AsmPrinter.
- BB’s whose addresses are taken, i.e. jump tables, can’t be deleted.  Those
functions will just keep their IR around so no changes there.

With the above issues fixed, I can run make check and pass all the tests.

Comments very welcome.

Cheers,
Pete

----- Original Message -----
> From: "Pete Cooper" <peter_cooper at apple.com>
> To: "Chandler Carruth" <chandlerc at gmail.com>,
"Duncan P. N. Exon Smith" <dexonsmith at apple.com>, "Hal
Finkel"
> <hfinkel at anl.gov>, "Philip Reames" <listmail at
philipreames.com>, "Mehdi Amini" <mehdi.amini at apple.com>,
"Rafael
> Espíndola" <rafael.espindola at gmail.com>
> Cc: "llvm-dev" <llvm-dev at lists.llvm.org>
> Sent: Monday, March 7, 2016 6:44:06 PM
> Subject: Deleting function IR after codegen
> 
> Hi all
> 
> After codegen for a given function, the IR should no longer be
> needed.  In the AsmPrinter we convert from MI->MCInstr, and then we
> never go back and look at the IR during the MC layer.
> 
> I’ve prototyped a simple pass which can be (optionally) scheduled to
> do just this.  It is added at the end of addPassesToEmitFile.  It is
> optional so that clang can continue to leak the IR with
> --disable-free, but i would propose that all other tools, and
> especially LTO, would enable it.  The savings are 20% of peak memory
> in LTO of clang itself.
> 
> I could attach a patch, but first i’d really like to know if anyone
> is fundamentally opposed to this.
> 
> I should note, a couple of issues have come up in the prototype.
> - llvm::getDISubprogram was walking the function body to find the
> subprogram.  This is trivial to fix as functions now have !dbg on
> them.
> - The AsmPrinter is calling canBeOmittedFromSymbolTable on
> GlobalValue’s which then walks all their uses.  I think this should
> be done earlier in codegen as an analysis whose results are
> available to the AsmPrinter.
I imagine that these are good cleanups regardless, it sounds like the fixes are
also likely compile-time improvements.
> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted.
>  Those functions will just keep their IR around so no changes there.
> 
> With the above issues fixed, I can run make check and pass all the
> tests.
> 
> Comments very welcome.
As an optional feature, it certainly makes sense to me.

 -Hal
> 
> Cheers,
> Pete
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

> On Mar 7, 2016, at 4:44 PM, Pete Cooper <peter_cooper at apple.com>
wrote:
> 
> Hi all
> 
> After codegen for a given function, the IR should no longer be needed.  In
the AsmPrinter we convert from MI->MCInstr, and then we never go back and
look at the IR during the MC layer.
> 
> I’ve prototyped a simple pass which can be (optionally) scheduled to do
just this.  It is added at the end of addPassesToEmitFile.  It is optional so
that clang can continue to leak the IR with --disable-free, but i would propose
that all other tools, and especially LTO, would enable it.  The savings are 20%
of peak memory in LTO of clang itself.
I think such a pass is worth it. 
I see a conceptual issue with it though, it would have to be FunctionPass, and
such pass are not allowed to delete globals and Functions (see
http://llvm.org/docs/WritingAnLLVMPass.html#the-functionpass-class ).
That said the CodeGen could be made a CallGraphSCCPass (which is something we
thought about investigating to help register allocation at call site when you
have already CodeGen the callee and can infer what is preserved). I'm not
sure your feature alone justify such a change though.

Out of curiosity, how do you expose it to the client by the way:

Target->addPassesToEmitFile(PM, ....)
if (deleteFunctionAfterCodeGen)
	PM.addPass(createFunctionDeletionPass())
or 

Target->addPassesToEmitFile(PM, ...., deleteFunctionAfterCodeGen);

-- 
Mehdi


> 
> I could attach a patch, but first i’d really like to know if anyone is
fundamentally opposed to this.
> 
> I should note, a couple of issues have come up in the prototype.
> - llvm::getDISubprogram was walking the function body to find the
subprogram.  This is trivial to fix as functions now have !dbg on them.
> - The AsmPrinter is calling canBeOmittedFromSymbolTable on GlobalValue’s
which then walks all their uses.  I think this should be done earlier in codegen
as an analysis whose results are available to the AsmPrinter.
> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted. 
Those functions will just keep their IR around so no changes there.
> 
> With the above issues fixed, I can run make check and pass all the tests.
> 
> Comments very welcome.
> 
> Cheers,
> Pete

Pete Cooper via llvm-dev <llvm-dev at lists.llvm.org>
writes:
> Hi all
>
> After codegen for a given function, the IR should no longer be needed.
> In the AsmPrinter we convert from MI->MCInstr, and then we never go
> back and look at the IR during the MC layer.
>
> I’ve prototyped a simple pass which can be (optionally) scheduled to
> do just this.  It is added at the end of addPassesToEmitFile.  It is
> optional so that clang can continue to leak the IR with
> --disable-free, but i would propose that all other tools, and
> especially LTO, would enable it.  The savings are 20% of peak memory
> in LTO of clang itself.
Did you happen to measure whether it's even worth keeping for
--disable-free? I suppose the cost of deleting it might be enough to
worry about for very small compilations, in which case we'd probably
want to keep the current behaviour.
> I could attach a patch, but first i’d really like to know if anyone is
> fundamentally opposed to this.
I'm definitely interested in seeing the patch. ISTM that anywhere the MC
layer needs to access IR would be a bit of a layering violation already,
so we'd want to clean that up anyway.
> I should note, a couple of issues have come up in the prototype.
> - llvm::getDISubprogram was walking the function body to find the
>   subprogram.  This is trivial to fix as functions now have !dbg on
>   them.
> - The AsmPrinter is calling canBeOmittedFromSymbolTable on
>   GlobalValue’s which then walks all their uses.  I think this should be
>   done earlier in codegen as an analysis whose results are available to
>   the AsmPrinter.
> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted.
>   Those functions will just keep their IR around so no changes there.
>
> With the above issues fixed, I can run make check and pass all the tests.
>
> Comments very welcome.
>
> Cheers,
> Pete
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> On Mar 7, 2016, at 4:56 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> ----- Original Message -----
>> From: "Pete Cooper" <peter_cooper at apple.com
<mailto:peter_cooper at apple.com>>
>> To: "Chandler Carruth" <chandlerc at gmail.com
<mailto:chandlerc at gmail.com>>, "Duncan P. N. Exon Smith"
<dexonsmith at apple.com <mailto:dexonsmith at apple.com>>,
"Hal Finkel"
>> <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>,
"Philip Reames" <listmail at philipreames.com <mailto:listmail
at philipreames.com>>, "Mehdi Amini" <mehdi.amini at
apple.com <mailto:mehdi.amini at apple.com>>, "Rafael
>> Espíndola" <rafael.espindola at gmail.com
<mailto:rafael.espindola at gmail.com>>
>> Cc: "llvm-dev" <llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org>>
>> Sent: Monday, March 7, 2016 6:44:06 PM
>> Subject: Deleting function IR after codegen
>> 
>> Hi all
>> 
>> After codegen for a given function, the IR should no longer be
>> needed.  In the AsmPrinter we convert from MI->MCInstr, and then we
>> never go back and look at the IR during the MC layer.
>> 
>> I’ve prototyped a simple pass which can be (optionally) scheduled to
>> do just this.  It is added at the end of addPassesToEmitFile.  It is
>> optional so that clang can continue to leak the IR with
>> --disable-free, but i would propose that all other tools, and
>> especially LTO, would enable it.  The savings are 20% of peak memory
>> in LTO of clang itself.
>> 
>> I could attach a patch, but first i’d really like to know if anyone
>> is fundamentally opposed to this.
>> 
>> I should note, a couple of issues have come up in the prototype.
>> - llvm::getDISubprogram was walking the function body to find the
>> subprogram.  This is trivial to fix as functions now have !dbg on
>> them.
>> - The AsmPrinter is calling canBeOmittedFromSymbolTable on
>> GlobalValue’s which then walks all their uses.  I think this should
>> be done earlier in codegen as an analysis whose results are
>> available to the AsmPrinter.
> 
> I imagine that these are good cleanups regardless, it sounds like the fixes
are also likely compile-time improvements.
Cool.  I’ll get some patches together for these then.  The first should be out
soon.

And yes, the !dbg one in particular should be a small compile time
improvement.
> 
>> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted.
>> Those functions will just keep their IR around so no changes there.
>> 
>> With the above issues fixed, I can run make check and pass all the
>> tests.
>> 
>> Comments very welcome.
> 
> As an optional feature, it certainly makes sense to me.
Thanks! :)

Pete
> 
> -Hal
> 
>> 
>> Cheers,
>> Pete
> 
> -- 
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160307/0f0f36b6/attachment.html>

> On Mar 7, 2016, at 5:01 PM, Mehdi Amini <mehdi.amini at apple.com>
wrote:
> 
> 
>> On Mar 7, 2016, at 4:44 PM, Pete Cooper <peter_cooper at
apple.com> wrote:
>> 
>> Hi all
>> 
>> After codegen for a given function, the IR should no longer be needed. 
In the AsmPrinter we convert from MI->MCInstr, and then we never go back and
look at the IR during the MC layer.
>> 
>> I’ve prototyped a simple pass which can be (optionally) scheduled to do
just this.  It is added at the end of addPassesToEmitFile.  It is optional so
that clang can continue to leak the IR with --disable-free, but i would propose
that all other tools, and especially LTO, would enable it.  The savings are 20%
of peak memory in LTO of clang itself.
> 
> I think such a pass is worth it. 
> I see a conceptual issue with it though, it would have to be FunctionPass,
and such pass are not allowed to delete globals and Functions (see
http://llvm.org/docs/WritingAnLLVMPass.html#the-functionpass-class ).
Ah, yeah this is tricky.  So my pass isn’t deleting the function value, but it
is deleting all the BBs/Instrs inside.  When you read the IR it actually prints
it as a declaration because the AsmWriter thinks that no body implies a
declaration.

One issue this this is that FPPassManager::runOnFunction starts by checking for
declarations and skipping them.  So that means that if a function pass was to
run after my pass, then it would get a function with no body which is not what
it expects.

One option I considered was to replace the function body with a single BB and an
unreachable/return, but I didn’t want to create useless
IR.
> That said the CodeGen could be made a CallGraphSCCPass (which is something
we thought about investigating to help register allocation at call site when you
have already CodeGen the callee and can infer what is preserved). I'm not
sure your feature alone justify such a change though.
I would certainly like to see CodeGen work this way.  If my work requires it
then I have no problem with it, but i’d love to land my changes without this if
its possible, just in case its troublesome to make this
change.
> 
> Out of curiosity, how do you expose it to the client by the way:
> 
> Target->addPassesToEmitFile(PM, ....)
> if (deleteFunctionAfterCodeGen)
> 	PM.addPass(createFunctionDeletionPass())
> or 
> 
> Target->addPassesToEmitFile(PM, ...., deleteFunctionAfterCodeGen);
The above.  The specific lines I changed on the function prototype are this,
which means that I’m opting everyone in to my change, but then as I said we’d
probably change clang to propagate its DisableFree flag in here:

virtual bool addPassesToEmitFile(
       PassManagerBase &, raw_pwrite_stream &, CodeGenFileType,
-      bool /*DisableVerify*/ = true, AnalysisID /*StartBefore*/ = nullptr,
+      bool /*DisableVerify*/ = true, bool /*FreeFunctionIR*/ = true,
+      AnalysisID /*StartBefore*/ = nullptr,
       AnalysisID /*StartAfter*/ = nullptr, AnalysisID /*StopAfter*/ = nullptr,
       MachineFunctionInitializer * /*MFInitializer*/ = nullptr)

Cheers,
Pete
> 
> -- 
> Mehdi
> 
> 
> 
>> 
>> I could attach a patch, but first i’d really like to know if anyone is
fundamentally opposed to this.
>> 
>> I should note, a couple of issues have come up in the prototype.
>> - llvm::getDISubprogram was walking the function body to find the
subprogram.  This is trivial to fix as functions now have !dbg on them.
>> - The AsmPrinter is calling canBeOmittedFromSymbolTable on
GlobalValue’s which then walks all their uses.  I think this should be done
earlier in codegen as an analysis whose results are available to the AsmPrinter.
>> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted. 
Those functions will just keep their IR around so no changes there.
>> 
>> With the above issues fixed, I can run make check and pass all the
tests.
>> 
>> Comments very welcome.
>> 
>> Cheers,
>> Pete
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160307/7ec6668a/attachment.html>

> On Mar 7, 2016, at 5:05 PM, Justin Bogner <mail at justinbogner.com>
wrote:
> 
> Pete Cooper via llvm-dev <llvm-dev at lists.llvm.org <mailto:llvm-dev
at lists.llvm.org>> writes:
>> Hi all
>> 
>> After codegen for a given function, the IR should no longer be needed.
>> In the AsmPrinter we convert from MI->MCInstr, and then we never go
>> back and look at the IR during the MC layer.
>> 
>> I’ve prototyped a simple pass which can be (optionally) scheduled to
>> do just this.  It is added at the end of addPassesToEmitFile.  It is
>> optional so that clang can continue to leak the IR with
>> --disable-free, but i would propose that all other tools, and
>> especially LTO, would enable it.  The savings are 20% of peak memory
>> in LTO of clang itself.
> 
> Did you happen to measure whether it's even worth keeping for
> --disable-free? I suppose the cost of deleting it might be enough to
> worry about for very small compilations, in which case we'd probably
> want to keep the current behavior.
I didn’t, no.  We could though.

I’ve CCed Vedant as I know he looked at the cost of freeing the IR fairly
recently.  I think he said it was about 3-4% compile time, but he can correct me
if i have that wrong.
> 
>> I could attach a patch, but first i’d really like to know if anyone is
>> fundamentally opposed to this.
> 
> I'm definitely interested in seeing the patch. ISTM that anywhere the
MC
> layer needs to access IR would be a bit of a layering violation already,
> so we'd want to clean that up anyway.
Personally I think its a layering violation.  At least I think it is one for the
AsmPrinter FunctionPass to be walking the use lists of Globals.  I don’t think
FunctionPasses at any level should be able to do that.

Cheers,
Pete
> 
>> I should note, a couple of issues have come up in the prototype.
>> - llvm::getDISubprogram was walking the function body to find the
>>  subprogram.  This is trivial to fix as functions now have !dbg on
>>  them.
>> - The AsmPrinter is calling canBeOmittedFromSymbolTable on
>>  GlobalValue’s which then walks all their uses.  I think this should be
>>  done earlier in codegen as an analysis whose results are available to
>>  the AsmPrinter.
>> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted.
>>  Those functions will just keep their IR around so no changes there.
>> 
>> With the above issues fixed, I can run make check and pass all the
tests.
>> 
>> Comments very welcome.
>> 
>> Cheers,
>> Pete
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160307/344e2642/attachment.html>

I like the idea of deleting IR once we are at MC. Hopefully one day
even just after codegen.
> - The AsmPrinter is calling canBeOmittedFromSymbolTable on GlobalValue’s
which then walks all their uses.  I think this should be done earlier in codegen
as an analysis whose results are available to the AsmPrinter.
Starting with an analysis is probably the way to go. At some point it
might make sense to cache that information in the IR somehow for use
in LTO, but that will require some benchmarking to see if it is really
worth it.

Cheers,
Rafael

> On Mar 7, 2016, at 6:46 PM, Rafael Espíndola <rafael.espindola at
gmail.com> wrote:
> 
> I like the idea of deleting IR once we are at MC. Hopefully one day
> even just after codegen.
Yeah, that would be ideal.  Better is some time inside codegen, but the issue
inside codegen is AA, but thats not solvable any time soon I
think.
> 
>> - The AsmPrinter is calling canBeOmittedFromSymbolTable on
GlobalValue’s which then walks all their uses.  I think this should be done
earlier in codegen as an analysis whose results are available to the AsmPrinter.
> 
> Starting with an analysis is probably the way to go. At some point it
> might make sense to cache that information in the IR somehow for use
> in LTO, but that will require some benchmarking to see if it is really
> worth it.
I agree.  I think it was escape analysis, and I can similarly imagine ‘escapes’
being a useful function argument attribute, so we could add it to both globals
and arguments.

Cheers,
Pete
> 
> Cheers,
> Rafael

> I could attach a patch, but first i’d really like to know if anyone is
> fundamentally opposed to this.
>
>
Not necessarily. I think that any information that isn't being serialized
in MI right now for a function could be as well. Definitely something for
GlobalISel to keep in mind.

> I should note, a couple of issues have come up in the prototype.
> - llvm::getDISubprogram was walking the function body to find the
> subprogram.  This is trivial to fix as functions now have !dbg on them.
>
This is definitely worth it, please go ahead and do this.

> - The AsmPrinter is calling canBeOmittedFromSymbolTable on GlobalValue’s
> which then walks all their uses.  I think this should be done earlier in
> codegen as an analysis whose results are available to the AsmPrinter.
>
I think this makes sense, but I worry about late added GlobalValues during
code gen? How would we cope with that? Example: Let's say we start lowering
a target specific construct as an MI pass etc and it constructs a global
value, when do we run the analysis to make sure that all such things
happen? Late as possible I'd assume. Maybe this isn't an issue, but
thought
I'd bring it up. At any rate, could you provide a bit more detail here?

- BB’s whose addresses are taken, i.e. jump tables, can’t be
deleted.
> Those functions will just keep their IR around so no changes there.
>
>
Oh well. Conveniently there aren't a lot of these.

-eric
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160308/1f6ae179/attachment.html>

> On Mar 8, 2016, at 11:50 AM, Eric Christopher <echristo at gmail.com>
wrote:
> 
> 
> 
> 
> I could attach a patch, but first i’d really like to know if anyone is
fundamentally opposed to this.
> 
> 
> Not necessarily. I think that any information that isn't being
serialized in MI right now for a function could be as well. Definitely something
for GlobalISel to keep in mind.
+1.
That’s basically where I would like to go with MachineModule/MachineModulePass.
http://lists.llvm.org/pipermail/llvm-dev/2016-January/094426.html

Cheers,
-Quentin
>  
> I should note, a couple of issues have come up in the prototype.
> - llvm::getDISubprogram was walking the function body to find the
subprogram.  This is trivial to fix as functions now have !dbg on them.
> 
> This is definitely worth it, please go ahead and do this.
>  
> - The AsmPrinter is calling canBeOmittedFromSymbolTable on GlobalValue’s
which then walks all their uses.  I think this should be done earlier in codegen
as an analysis whose results are available to the AsmPrinter.
> 
> I think this makes sense, but I worry about late added GlobalValues during
code gen? How would we cope with that? Example: Let's say we start lowering
a target specific construct as an MI pass etc and it constructs a global value,
when do we run the analysis to make sure that all such things happen? Late as
possible I'd assume. Maybe this isn't an issue, but thought I'd
bring it up. At any rate, could you provide a bit more detail here?
> 
> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted. 
Those functions will just keep their IR around so no changes there.
> 
> 
> Oh well. Conveniently there aren't a lot of these.
> 
> -eric
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160308/2634733f/attachment.html>

> On Mar 8, 2016, at 11:50 AM, Eric Christopher <echristo at gmail.com>
wrote:
> 
> 
> 
> 
> I could attach a patch, but first i’d really like to know if anyone is
fundamentally opposed to this.
> 
> 
> Not necessarily. I think that any information that isn't being
serialized in MI right now for a function could be as well. Definitely something
for GlobalISel to keep in mind.
Probably even depends on the kind of AA.  TBAA is likely mostly useable without
instructions around (you could reference the TBAA from the MIs themselves), but
I guess BasicAA is still introspecting the instructions enough to make it harder
to migrate.
>  
> I should note, a couple of issues have come up in the prototype.
> - llvm::getDISubprogram was walking the function body to find the
subprogram.  This is trivial to fix as functions now have !dbg on them.
> 
> This is definitely worth it, please go ahead and do this.
Will do.  Thanks.
>  
> - The AsmPrinter is calling canBeOmittedFromSymbolTable on GlobalValue’s
which then walks all their uses.  I think this should be done earlier in codegen
as an analysis whose results are available to the AsmPrinter.
> 
> I think this makes sense, but I worry about late added GlobalValues during
code gen?
The code which walks them is looking for an ICmpInst with the global on one
side.  Basically wants to know if the address is interesting.  Globals added
from selection DAG onwards likely won’t have an IR instruction added to compare
them, although if for some reason someone added a global and materialized the
compare directly in MIs then I guess the current code would be
incorrect.
> How would we cope with that? Example: Let's say we start lowering a
target specific construct as an MI pass etc and it constructs a global value,
when do we run the analysis to make sure that all such things happen? Late as
possible I'd assume. Maybe this isn't an issue, but thought I'd
bring it up. At any rate, could you provide a bit more detail here?
It does sound like this is going to be tricky.  I was hoping to run this as a
Module pass prior to starting the codegen function passes, but there’s nothing
to stop CodeGenPrepare from adding a compare to a function, after when I was
hoping to run the analysis.  I’ll need to mull this
over.
> 
> - BB’s whose addresses are taken, i.e. jump tables, can’t be deleted. 
Those functions will just keep their IR around so no changes there.
> 
> 
> Oh well. Conveniently there aren't a lot of these.
Yeah, not ideal, but hopefully not too bad either.

Pete
> 
> -eric
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160310/967d3e2a/attachment.html>