Dear all, I have been working on a new LLVM backend. Some instructions, like sub, can take an positive constante, encoded into 5 bits thus lower than 32, and a register, as operands. Unfortunately, DAGCombiner.cpp changes patterns like 'sub x, 5' into 'add x,-5'. Similarly, I found changes in some IR to IR passes, with no clear gain (at least not clear to me), and even penalty for my specific ISA. %add = add i32 %a, %b %tobool = icmp eq i32 %add, 0 becomes : %add = sub i32 0, %b %tobool = icmp eq i32 %a, % My question is not how to workaround those, but why such changes are done for all targets, in DAG selection or in IR passes. AFAIK, there is no target which has some better encoding with a negative value than with a positive one. And "sub" looks as costly as "add" to me. Is there some other practical reason to perform this kind of change ? Thanks for your highlights. -- Frederic Heitzmann -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150708/ecb42c7e/attachment.html>
Krzysztof Parzyszek
2015-Jul-08 15:10 UTC
[LLVMdev] Why change "sub x, 5" to "add x, -5" ?
Other people can elaborate on that, but the general idea is to transform functionally equivalent programs into the same internal representation. In this case, the desired representation is "add-immediate" for instructions that are equivalent to it. Target-specific selection patterns can deal with it by having predicates that accept or reject the pattern depending on specific values in the DAG: in case of your ISA they could reject the "add" pattern in favor of the "sub" pattern when the immediate is negative. -Krzysztof On 7/8/2015 10:00 AM, Frédéric Heitzmann wrote:> Dear all, > > I have been working on a new LLVM backend. Some instructions, like sub, > can take an positive constante, encoded into 5 bits thus lower than 32, > and a register, as operands. > Unfortunately, DAGCombiner.cpp changes patterns like 'sub x, 5' into > 'add x,-5'. > > Similarly, I found changes in some IR to IR passes, with no clear gain > (at least not clear to me), and even penalty for my specific ISA. > > %add = add i32 %a, %b > %tobool = icmp eq i32 %add, 0 > > becomes : > > %add = sub i32 0, %b > %tobool = icmp eq i32 %a, % > > My question is not how to workaround those, but why such changes are > done for all targets, in DAG selection or in IR passes. > AFAIK, there is no target which has some better encoding with a negative > value than with a positive one. > And "sub" looks as costly as "add" to me. > > Is there some other practical reason to perform this kind of change ? > Thanks for your highlights. > > -- > Frederic Heitzmann > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
On 8 Jul 2015, at 16:00, Frédéric Heitzmann <frederic.heitzmann at gmail.com> wrote:> > AFAIK, there is no target which has some better encoding with a negative value than with a positive one.Many don’t have a sub-with-immediate at all, they have an add-with-sign-extended-immediate. Having a single canonical form simplifies matching for these. David
> On Jul 8, 2015, at 8:00 AM, Frédéric Heitzmann <frederic.heitzmann at gmail.com> wrote: > > Dear all, > > I have been working on a new LLVM backend. Some instructions, like sub, can take an positive constante, encoded into 5 bits thus lower than 32, and a register, as operands. > Unfortunately, DAGCombiner.cpp changes patterns like 'sub x, 5' into 'add x,-5’.Having a single canonical form makes optimizations easier, since you don’t have to check both possibilities at every optimization stage. If you want to “revert" this sort of thing, you can do it at Select() time or PreprocessISelDAG(), which is what I did on an out-of-tree backend to turn add X, -C into sub X, C on selection time. This still lets all the intermediate optimizations take advantage of the canonicalization. —escha
Normalizing values also makes optimizations more powerful as equivalent values become apparent. Simple example: a = sub x, 5 b = add x, -5 c = sub a, b gets normalized to: a = add x, -5 b = add x, -5 c = sub a, b after CSE: a = add x, -5 c = sub a, a and after instcombine: c = 0 - Matthias> On Jul 8, 2015, at 8:58 AM, escha <escha at apple.com> wrote: > > >> On Jul 8, 2015, at 8:00 AM, Frédéric Heitzmann <frederic.heitzmann at gmail.com> wrote: >> >> Dear all, >> >> I have been working on a new LLVM backend. Some instructions, like sub, can take an positive constante, encoded into 5 bits thus lower than 32, and a register, as operands. >> Unfortunately, DAGCombiner.cpp changes patterns like 'sub x, 5' into 'add x,-5’. > > Having a single canonical form makes optimizations easier, since you don’t have to check both possibilities at every optimization stage. > > If you want to “revert" this sort of thing, you can do it at Select() time or PreprocessISelDAG(), which is what I did on an out-of-tree backend to turn add X, -C into sub X, C on selection time. This still lets all the intermediate optimizations take advantage of the canonicalization. > > —escha > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
2015-07-08 17:58 GMT+02:00 escha <escha at apple.com>:> [...] > > If you want to “revert" this sort of thing, you can do it at Select() time > or PreprocessISelDAG(), which is what I did on an out-of-tree backend to > turn add X, -C into sub X, C on selection time. This still lets all the > intermediate optimizations take advantage of the canonicalization. > > —eschaUnaware of your proposal, I used the TargetLowering::PerformDAGCombine hook. Is there a reason to prefere PreprocessISelDAG ? -- Fred -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150710/12e26aab/attachment.html>