llvm dev - Aug 2012 - [LLVMdev] Proposal to merge SimplifyLibCalls into InstCombiner

Hi All,

I finally got around to cleaning up my proposal to merge `SimplifyLibCalls`
into `InstCombiner`.  There is still an open question or two and I am sure
there are parts that could be better specified, but this is good enough to
discuss.  Feedback is most welcome.

Abstract
=======
This proposal is an attack plan for PR11895 [1].

Currently within LLVM we have two passes that are used to fold library calls:
(1) `SimplifyLibCalls` and (2) `InstCombiner` (by way of `visitCallSite`).
Having multiple methods to implement an optimization class makes
understanding the optimizer more difficult, presents a maintenance burden,
and makes it unclear where new optimizations within the class should go.
As such, the two call folding methods should be combined.

Each of the current methods has their own strengths and weaknesses.  The
`SimplifyLibCalls` pass is completely self-contained in
'Transforms/Scalar/SimplifyLibCalls.cpp', implements explicit loops for
walking the basic blocks and instructions, and has a nice table-driven
approach for adding new library call folders.  The portion of the
`InstCombiners` pass that is responsible for call folding is scattered
across 'Transforms/InstCombine/InstCombineCalls.cpp' and
'Transforms/Utils/BuildLibCalls.cpp', is limited to
"fortified" library
calls , uses a simple if/else cascade for each call folder, and takes
advantage of the nice call-site visitor framework in `InstCombiner`.

An design that combines the strength of the table-driven folder approach
into the `InstCombiner` visitor framework is proposed.

Proposal
=======
The following three sections specify a proposal for how the work will be broken
down.  In a way they specify milestones.

Extend test coverage
--------------------

Between the two existing methods the following library calls are folded:

1. `InstCombiners`: __memcpy_chk, __mempcpy_chk, __memset_chk, __strcpy_chk,
    __stpcpy_chk, __strncpy_chk, __stpncpy_chk, __strcat_chk, __strncat_chk.

2. `SimplifyLibCalls`: strcat, strncat, strchar, strrchr, strcmp, strncmp,
   strcpy, strncpy, strlen, strpbrk, strtol, strtod, strtof, strtoul,
   strtoll, strtold, strtoull, strtold, strtoull, strspn, strcspn, strstr,
   memcmp, memcpy, memmove, memset, __strcpy_chk, cosf, cos, cosl, powf,
   pow, powl, llvm.pow.f32, llvm.pow.f64, llvm.pow.f80, llvm.pow.f128,
   llvm.pow.ppcf128, exp21, exp2, exp2f, llvm.exp2.ppcf128, llvm.exp2.f128,
   llvm.exp2.f80, llvm.exp2.f64, llvm.exp2.f32, floor, cell, round, rint,
   nearbyint, ffs, ffsl, ffsll, abs, labs, llabs, isdigit, isascii,
   toascii, sprintf, print, fwrite, fputs, fprintf, puts.

Test cases that exercise the library call folders for each of these
functions should be present.  Any missing test cases will be added.

Create new `LibCallSimplifier` class
------------------------------------

A new self-contained `LibCallSimplifier` class will be created.  An instance
of the class will be instantiated when running the `InstCombiner` pass. 
It's
folding functionality will be invoked from `InstCombiner::tryOptimizeCall` and
the implementation will be table-driven like `SimplifyLibCalls`.  All of the
existing fortified library call simplifiers will be migrated to this new class
at this step.

Migrate `SimplifyLibCalls` to `LibCallSimplifier`
-------------------------------------------------
All of the individual optimizations from `SimplifyLibCalls` will be migrated
over to the new `LibCallSimplifier` infrastructure.  This will done
incrementally one optimization at a time to make things easier to review.
An option for enabling/disabling library call simplification in `InstCombiner`
will be available.  For backwards compatibility perhaps it should remain
'-simplify-libcalls'.  The `NumSimplified` and `NumAnnotated` statistics
shall
be added to `InstCombiner`.

As a result of this migration 'Transforms/Scalar/SimplifyLibCalls.cpp'
will go
away.

Proof of Concept
===============
A very rough proof of concept patch has been attached to this proposal
showing how the table-driven method can be integrated into `InstCombiner`.
This is *not* meant to be a patch submission, so please don't provide
review points on style, implementation bugs, and other typical code review
points.  It is merely provided to show the general direction of the
implementation.  That being said, it does currently pass the regression
test suite as of r161099.

Open Questions
=============
1. What should be done about the `SimplifyFortifiedLibCalls` use in
   `CodeGenPrepare`?

References
=========
.. [1] PR11895 - SimplifyLibCalls should be merged into instcombine
   (http://llvm.org/bugs/show_bug.cgi?id=11895)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: call-folding-merge-proposal.patch
Type: application/octet-stream
Size: 16181 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120801/1667fa0c/attachment.obj>
-------------- next part --------------

--
Meador Inge
CodeSourcery / Mentor Embedded
http://www.mentor.com/embedded-software

On Aug 1, 2012, at 9:49 PM, Meador Inge <meadori at codesourcery.com>
wrote:
> Hi All,
> 
> I finally got around to cleaning up my proposal to merge `SimplifyLibCalls`
> into `InstCombiner`.  There is still an open question or two and I am sure
> there are parts that could be better specified, but this is good enough to
> discuss.  Feedback is most welcome.
Fantastic, I'm glad that you're looking to tackle this.
> An design that combines the strength of the table-driven folder approach
> into the `InstCombiner` visitor framework is proposed.
Sounds like the right high level design.
> The following three sections specify a proposal for how the work will be
broken
> down.  In a way they specify milestones.
> 
> Extend test coverage
> --------------------
+1
> Create new `LibCallSimplifier` class
> ------------------------------------
> 
> A new self-contained `LibCallSimplifier` class will be created.  An
instance
> of the class will be instantiated when running the `InstCombiner` pass. 
It's
> folding functionality will be invoked from `InstCombiner::tryOptimizeCall`
and
> the implementation will be table-driven like `SimplifyLibCalls`.  All of
the
> existing fortified library call simplifiers will be migrated to this new
class
> at this step.
Ok, the idea is that other general parts of the compiler can use the
LibCallSimplifier interface as well?  That makes sense to me.
> Migrate `SimplifyLibCalls` to `LibCallSimplifier`
> -------------------------------------------------
> All of the individual optimizations from `SimplifyLibCalls` will be
migrated
> over to the new `LibCallSimplifier` infrastructure.  This will done
> incrementally one optimization at a time to make things easier to review.
Makes sense.  After you do the first few and people are happy with the general
approach, later libcalls can be moved in larger chunks (e.g. by family) instead
of each individually.
> An option for enabling/disabling library call simplification in
`InstCombiner`
> will be available.  For backwards compatibility perhaps it should remain
> '-simplify-libcalls'.  The `NumSimplified` and `NumAnnotated`
statistics shall
> be added to `InstCombiner`.
There is no need to preserver the -simplify-libcalls flag.  It's an internal
implementation detail of the compiler, one that is better left in the past :)
> As a result of this migration
'Transforms/Scalar/SimplifyLibCalls.cpp' will go
> away.
Woot.
> Proof of Concept
> ===============> 
> A very rough proof of concept patch has been attached to this proposal
> showing how the table-driven method can be integrated into `InstCombiner`.
> This is *not* meant to be a patch submission, so please don't provide
> review points on style, implementation bugs, and other typical code review
> points.  It is merely provided to show the general direction of the
> implementation.  That being said, it does currently pass the regression
> test suite as of r161099.
Looks pretty decent to me.  You can also land the new LibCallSimplifier
infrastructure first before you switch anything over to use it, if that helps.
> Open Questions
> =============> 
> 1. What should be done about the `SimplifyFortifiedLibCalls` use in
>   `CodeGenPrepare`?
I think it stays where it is.  CGP runs right before the code generator kicks
in.  The idea here is that we want to leave the fortified libcalls in the IR as
long as possible on the off chance that instcombine or something else can expose
range information about underlying buffers... however, if we get all the way to
code gen, then we failed to find a length, so we remove them.

-Chris

On 08/02/2012 11:11 AM, Chris Lattner wrote:
>> A new self-contained `LibCallSimplifier` class will be created.  An
instance
>> of the class will be instantiated when running the `InstCombiner` pass.
It's
>> folding functionality will be invoked from
`InstCombiner::tryOptimizeCall` and
>> the implementation will be table-driven like `SimplifyLibCalls`.  All
of the
>> existing fortified library call simplifiers will be migrated to this
new class
>> at this step.
> 
> Ok, the idea is that other general parts of the compiler can use the
LibCallSimplifier
> interface as well?  That makes sense to me.
Yup, that's it.
>> An option for enabling/disabling library call simplification in
`InstCombiner`
>> will be available.  For backwards compatibility perhaps it should
remain
>> '-simplify-libcalls'.  The `NumSimplified` and `NumAnnotated`
statistics shall
>> be added to `InstCombiner`.
> 
> There is no need to preserver the -simplify-libcalls flag.  It's an
internal
> implementation detail of the compiler, one that is better left in the past
:)
Do you think we still need some way to disable just the library call
simplification now that it is a part of the instruction combiner?
>> 1. What should be done about the `SimplifyFortifiedLibCalls` use in
>>   `CodeGenPrepare`?
> 
> I think it stays where it is.  CGP runs right before the code generator
> kicks in.  The idea here is that we want to leave the fortified libcalls
> in the IR as long as possible on the off chance that instcombine or
something
> else can expose range information about underlying buffers... however, if
we
> get all the way to code gen, then we failed to find a length, so we remove
them.
Thanks for the explanation.  As a part of the merger I really want
`SimplifyFortifiedLibCalls` to go away as well, since the fortified
library call folding is being rolled into `LibCallSimplifier`.  I will
look at applying `LibCallSimplifier` to the CGP case as well (the conditions
for when it is OK to fold is slightly different for CGP).

Thanks for the feedback!

-- 
Meador Inge
CodeSourcery / Mentor Embedded
http://www.mentor.com/embedded-software