Amaury SECHET via llvm-dev
2017-Jan-23 12:06 UTC
[llvm-dev] Early legalization pass ? Doing early legalization in an existing pass ?
Hi all, Some non trivial legalization of operations which aren't supported by the backend would benefit from having the optimizer pass on them. I noticed some example trying to optimize various pieces of code over the past weeks. One offender is the cttz/ctlz intrinsic when defined on 0. On X86, BSR and NSF are undefined on 0, and only recent CPU have the LZCNT and TZCNT instructions that are properly defined for 0. The backend insert code with a branch that checks for 0 and use bsf/bsr or just use a constant. But if we are to branch anyway, and one path of the branch set the value as a constant, there are some obvious optimization which can be done, starting with constant folding. None of these happen in the backend and it doesn't seems to be the right place anyway. See for instance the sample code from a serialization/deserialization routine (the code has been tuned to illustrate the problem in a brief way) : auto a = ctlz(n, false); auto b = ((a * 36) + 35) >> 8; Which will be synthesized as follow: auto a = (n == 0) ? 64 : ctlz(n, true); auto b = ((a * 36) + 35) >> 8; But obviously, recomputing b in the case n is 0 is completely pointless work. A better codegen would be something like: if (n == 0) { a = 64; b = 0; } else { a = ctlz(n, true); b = ((a * 36) + 35) >> 8; } The optimizer knows how to do these kind of transformations, but the backend do not. I encountered the same issue a some time back in a memory allocator, and worked around it, but as I'm encountering it again in the serialization library, I'm assuming there may be some untapped source of optimizations here. I was unsure about where these optimizations should take place. Clearly, we want to do them early in the pipeline so that other passes can pick up on it. I was looking around but it didn't seemed like there was a good place to add this transformation. Other examples of legalization that may benefit from the optimizer are splitting of large integral that the backend do not support into multiple operations on smaller integrals. Would a EarlyLegalization pass be worth it ? It could use infos from the backend and do various transformations that the backend would have to do anyway, which will expose optimization opportunities. Or is there a place that is appropriate to insert theses ? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170123/4d99654e/attachment.html>
via llvm-dev
2017-Jan-23 16:02 UTC
[llvm-dev] Early legalization pass ? Doing early legalization in an existing pass ?
> On Jan 23, 2017, at 4:06 AM, Amaury SECHET via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > Hi all, > > Some non trivial legalization of operations which aren't supported by the backend would benefit from having the optimizer pass on them. I noticed some example trying to optimize various pieces of code over the past weeks. > > One offender is the cttz/ctlz intrinsic when defined on 0. On X86, BSR and NSF are undefined on 0, and only recent CPU have the LZCNT and TZCNT instructions that are properly defined for 0. The backend insert code with a branch that checks for 0 and use bsf/bsr or just use a constant. > > But if we are to branch anyway, and one path of the branch set the value as a constant, there are some obvious optimization which can be done, starting with constant folding. None of these happen in the backend and it doesn't seems to be the right place anyway. See for instance the sample code from a serialization/deserialization routine (the code has been tuned to illustrate the problem in a brief way) : > > auto a = ctlz(n, false); > auto b = ((a * 36) + 35) >> 8; > > Which will be synthesized as follow: > > auto a = (n == 0) ? 64 : ctlz(n, true); > auto b = ((a * 36) + 35) >> 8; > > But obviously, recomputing b in the case n is 0 is completely pointless work. A better codegen would be something like: > > if (n == 0) { > a = 64; > b = 0; > } else { > a = ctlz(n, true); > b = ((a * 36) + 35) >> 8; > } > > The optimizer knows how to do these kind of transformations, but the backend do not. I encountered the same issue a some time back in a memory allocator, and worked around it, but as I'm encountering it again in the serialization library, I'm assuming there may be some untapped source of optimizations here. > > I was unsure about where these optimizations should take place. Clearly, we want to do them early in the pipeline so that other passes can pick up on it. I was looking around but it didn't seemed like there was a good place to add this transformation. > > Other examples of legalization that may benefit from the optimizer are splitting of large integral that the backend do not support into multiple operations on smaller integrals. > > Would a EarlyLegalization pass be worth it ? It could use infos from the backend and do various transformations that the backend would have to do anyway, which will expose optimization opportunities. Or is there a place that is appropriate to insert theses ?At least in theory, SelectionDAG is supposed to be able to do a lot of these kind of optimizations. The goal is to do legalization, then clean up the results of that in combine2. —escha
Nemanja Ivanovic via llvm-dev
2017-Jan-24 12:47 UTC
[llvm-dev] Early legalization pass ? Doing early legalization in an existing pass ?
I may be wrong here, but legalizing early seems like something that is more likely to prevent optimizations than it is to encourage them. But I guess I don't follow why things like TTI, TII and TLI queries don't suffice for this. CodeGenPrepare will break this sequence up. I would imagine that if the target returns false for isCheapToSpeculateCtlz() and false for canInsertSelect(), the code would look the way you'd like it to. But as I said, I'm mostly speculating here and I might be very wrong. On Mon, Jan 23, 2017 at 5:02 PM, via llvm-dev <llvm-dev at lists.llvm.org> wrote:> > > On Jan 23, 2017, at 4:06 AM, Amaury SECHET via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > > > > Hi all, > > > > Some non trivial legalization of operations which aren't supported by > the backend would benefit from having the optimizer pass on them. I noticed > some example trying to optimize various pieces of code over the past weeks. > > > > One offender is the cttz/ctlz intrinsic when defined on 0. On X86, BSR > and NSF are undefined on 0, and only recent CPU have the LZCNT and TZCNT > instructions that are properly defined for 0. The backend insert code with > a branch that checks for 0 and use bsf/bsr or just use a constant. > > > > But if we are to branch anyway, and one path of the branch set the value > as a constant, there are some obvious optimization which can be done, > starting with constant folding. None of these happen in the backend and it > doesn't seems to be the right place anyway. See for instance the sample > code from a serialization/deserialization routine (the code has been tuned > to illustrate the problem in a brief way) : > > > > auto a = ctlz(n, false); > > auto b = ((a * 36) + 35) >> 8; > > > > Which will be synthesized as follow: > > > > auto a = (n == 0) ? 64 : ctlz(n, true); > > auto b = ((a * 36) + 35) >> 8; > > > > But obviously, recomputing b in the case n is 0 is completely pointless > work. A better codegen would be something like: > > > > if (n == 0) { > > a = 64; > > b = 0; > > } else { > > a = ctlz(n, true); > > b = ((a * 36) + 35) >> 8; > > } > > > > The optimizer knows how to do these kind of transformations, but the > backend do not. I encountered the same issue a some time back in a memory > allocator, and worked around it, but as I'm encountering it again in the > serialization library, I'm assuming there may be some untapped source of > optimizations here. > > > > I was unsure about where these optimizations should take place. Clearly, > we want to do them early in the pipeline so that other passes can pick up > on it. I was looking around but it didn't seemed like there was a good > place to add this transformation. > > > > Other examples of legalization that may benefit from the optimizer are > splitting of large integral that the backend do not support into multiple > operations on smaller integrals. > > > > Would a EarlyLegalization pass be worth it ? It could use infos from the > backend and do various transformations that the backend would have to do > anyway, which will expose optimization opportunities. Or is there a place > that is appropriate to insert theses ? > > At least in theory, SelectionDAG is supposed to be able to do a lot of > these kind of optimizations. The goal is to do legalization, then clean up > the results of that in combine2. > > —escha > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > 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/20170124/6a4798aa/attachment.html>
Possibly Parallel Threads
- Early legalization pass ? Doing early legalization in an existing pass ?
- [PATCH 3/4] x86/emulator: properly handle lzcnt and tzcnt
- Git branch with compiling fixes for win32
- [LLVMdev] [PATCH] Emit rbit, clz on ARM for __builtin_ctz
- Bug: Library functions for ISD::SRA, ISD::SHL, and ISD::SRL