Meador Inge
2012-Aug-02 04:49 UTC
[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
Chris Lattner
2012-Aug-02 16:11 UTC
[LLVMdev] Proposal to merge SimplifyLibCalls into InstCombiner
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
Meador Inge
2012-Aug-03 19:56 UTC
[LLVMdev] Proposal to merge SimplifyLibCalls into InstCombiner
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
Possibly Parallel Threads
- [LLVMdev] Proposal to merge SimplifyLibCalls into InstCombiner
- [LLVMdev] Proposal to merge SimplifyLibCalls into InstCombiner
- [LLVMdev] Proposal to merge SimplifyLibCalls into InstCombiner
- Accelerating TLI getLibFunc lookups
- [LLVMdev] Which pass converts call printf to puts?