llvm dev - May 2017 - [RFC] Canonicalization of unsigned subtraction with saturation

Hi,

This message is a result of a discussion of backend optimization for sub(max)
pattern(https://reviews.llvm.org/D25987), which can be either converted to
unsigned min-max or unsigned saturation instruction(if the target supports it).
Currently these versions of the code produce different IR(and we need to manage
both types in backend):

(1.16)
void foo(unsigned short *p, unsigned short max, int n) {
  int i;
unsigned short m;
for (i = 0; i < n; i++) {
    m = *--p;
    *p =(m >= max ? m-max : 0);
  }
}

(2.16)
void goo(unsigned short *p, unsigned short max, int n) {
  int i;
  unsigned short m;
  for (i = 0; i < n; i++) {
    m = *--p;
    unsigned short umax = m > max ? m : max;
    *p =umax - max;
  }
}

(1.16)
%cmp = icmp ugt i16 %x, %y
%sub2 = sub i16 %y, %x
%res = select i1 %cmp, i16 0, i16 %sub2
 
or 

(2.16)
%cmp = icmp ugt i16 %x, %y
%sel = select i1 %cmp, i16 %x, i16 %y
%sub = sub i16 %sel, %x

Which of these versions is canonical? I think first version is better, because
it can be converted to unsigned saturation instruction(i.e. PSUBUS), using
existing backend code.

Thanks for posting this question, Julia.

I had a similar question about a signed min/max variant here:
http://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html

The 2nd version in each case contains a canonical max/min representation in
IR, and this could enable more IR analysis.
A secondary advantage is that the backend recognizes the max/min in the
second IR form when creating DAG nodes,
and this directly affects isel for many targets.

A possibly important difference between the earlier example and the current
unsigned case:
is a select with a zero constant operand easier to reason about in IR than
the canonical min/max?


On Tue, May 16, 2017 at 5:30 AM, Koval, Julia <julia.koval at intel.com>
wrote:
> Hi,
>
> This message is a result of a discussion of backend optimization for
> sub(max) pattern(https://reviews.llvm.org/D25987), which can be either
> converted to unsigned min-max or unsigned saturation instruction(if the
> target supports it).
> Currently these versions of the code produce different IR(and we need to
> manage both types in backend):
>
> (1.16)
> void foo(unsigned short *p, unsigned short max, int n) {
>   int i;
> unsigned short m;
> for (i = 0; i < n; i++) {
>     m = *--p;
>     *p =(m >= max ? m-max : 0);
>   }
> }
>
> (2.16)
> void goo(unsigned short *p, unsigned short max, int n) {
>   int i;
>   unsigned short m;
>   for (i = 0; i < n; i++) {
>     m = *--p;
>     unsigned short umax = m > max ? m : max;
>     *p =umax - max;
>   }
> }
>
> (1.16)
> %cmp = icmp ugt i16 %x, %y
> %sub2 = sub i16 %y, %x
> %res = select i1 %cmp, i16 0, i16 %sub2
>
> or
>
> (2.16)
> %cmp = icmp ugt i16 %x, %y
> %sel = select i1 %cmp, i16 %x, i16 %y
> %sub = sub i16 %sel, %x
>
> Which of these versions is canonical? I think first version is better,
> because it can be converted to unsigned saturation instruction(i.e.
> PSUBUS), using existing backend code.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170516/196368bc/attachment.html>

On 5/16/2017 6:30 AM, Sanjay Patel wrote:
> Thanks for posting this question, Julia.
>
> I had a similar question about a signed min/max variant here:
> http://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html
>
> The 2nd version in each case contains a canonical max/min 
> representation in IR, and this could enable more IR analysis.
> A secondary advantage is that the backend recognizes the max/min in 
> the second IR form when creating DAG nodes,
> and this directly affects isel for many targets.
This seems important.  And pattern-matching max(x,y)-y to a saturating 
subtract seems easy in the backend.
> A possibly important difference between the earlier example and the 
> current unsigned case:
> is a select with a zero constant operand easier to reason about in IR 
> than the canonical min/max?
It might be in some cases... maybe?  I mean, it might be easier to 
analyze in ComputeMaskedBits or something, but we don't really do much 
to optimize selects involving zero.

-Eli
> On Tue, May 16, 2017 at 5:30 AM, Koval, Julia <julia.koval at intel.com 
> <mailto:julia.koval at intel.com>> wrote:
>
>     (1.16)
>     %cmp = icmp ugt i16 %x, %y
>     %sub2 = sub i16 %y, %x
>     %res = select i1 %cmp, i16 0, i16 %sub2
>
>     or
>
>     (2.16)
>     %cmp = icmp ugt i16 %x, %y
>     %sel = select i1 %cmp, i16 %x, i16 %y
>     %sub = sub i16 %sel, %x
>
>     Which of these versions is canonical? I think first version is
>     better, because it can be converted to unsigned saturation
>     instruction(i.e. PSUBUS), using existing backend code.
>
>
-- 
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux
Foundation Collaborative Project

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170516/2346d49b/attachment.html>