llvm dev - Jul 2015 - [LLVMdev] Why change "sub x, 5" to "add x, -5" ?

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>

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.
>
> —escha

Unaware 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>