llvm dev - Sep 2016 - IR canonicalization: select or bool math?

I have another round of questions about IR select canonicalizations. For
the purity of this quiz, please disregard prior knowledge of how this is
handled by instcombine or how this is lowered by your favorite target...of
course we'll fix it. :) Some answers in the links below if you do want to
know.

Which, if any, of these is canonical?

1. Is a zext simpler than a select?
a. define i32 @sel_1_or_0(i1 %a) {
  %b = select i1 %a, i32 1, i32 0
  ret i32 %b
}

b. define i32 @sel_1_or_0(i1 %a) {
  %b = zext i1 %a to i32
  ret i32 %b
}

2. What if we have to 'not' the bool?
a. define i32 @sel_0_or_1(i1 %a) {
  %b = select i1 %a, i32 0, i32 1
  ret i32 %b
}

b. define i32 @sel_0_or_1(i1 %a) {
  %not.a = xor i1 %a, true
  %b = zext i1 %not.a to i32
  ret i32 %b
}

3. Is sext handled differently?
a. define i32 @sel_-1_or_0(i1 %a) {
  %b = select i1 %a, i32 -1, i32 0
  ret i32 %b
}

b. define i32 @sel_-1_or_0(i1 %a) {
  %b = sext i1 %a to i32
  ret i32 %b
}

4. What if the sext needs a 'not'?
a. define i32 @sel_0_or_-1(i1 %a) {
  %b = select i1 %a, i32 0, i32 -1
  ret i32 %b
}

b. define i32 @sel_0_or_-1(i1 %a) {
  %not.a = xor i1 %a, true
  %b = sext i1 %not.a to i32
  ret i32 %b
}

5. What if both constants are non-zero? Ie, the implicit add/sub of the
earlier cases can't be eliminated.
a. define i32 @sel_2_or_1(i1 %a) {
  %b = select i1 %a, i32 2, i32 1
  ret i32 %b
}

b. define i32 @sel_2_or_1(i1 %a) {
  %b = zext i1 to i32 %a
  %c = add i32 %b, 1
  ret i32 %b
}

6. Does 'sub' make a difference?
a. define i32 @sel_1_or_2(i1 %a) {
  %b = select i1 %a, i32 1, i32 2
  ret i32 %b
}

b. define i32 @sel_1_or_2(i1 %a) {
  %b = zext i1 %a to i32
  %c = sub i32 2, %b
  ret i32 %c
}

7. Choose between integers that are not consecutive?
a. define i32 @sel_0_or_2(i1 %a) {
  %sel = select i1 %a, i32 2, i32 0
  ret i32 %sel2
}

b. define i32 @sel_0_or_2(i1 %a) {
  %zexta = zext i1 %a to i32
  %add = add i32 %zexta, %zexta
  ret i32 %add
}

8. Choose {0,1,2} based on 2 bools?
a. define i32 @sel_sel(i1 %a, i1 %b) {
  %zexta = zext i1 %a to i32
  %sel1 = select i1 %a, i32 2, i32 1
  %sel2 = select i1 %b, i32 %sel1, %zexta
  ret i32 %sel2
}

b. define i32 @sel_sel(i1 %a, i1 %b) {
  %zexta = zext i1 %a to i32
  %zextb = zext i1 %b to i32
  %add = add i32 %zexta, %zextb
  ret i32 %add
}

Links for reference:
https://llvm.org/bugs/show_bug.cgi?id=30273
https://llvm.org/bugs/show_bug.cgi?id=30327
https://reviews.llvm.org/D24480
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160928/a2028774/attachment.html>

----- Original Message -----
> From: "Sanjay Patel" <spatel at rotateright.com>
> To: "llvm-dev" <llvm-dev at lists.llvm.org>
> Cc: "Eli Friedman" <efriedma at codeaurora.org>,
"David Majnemer"
> <david.majnemer at gmail.com>, "Michael Kuperstein"
> <mkuper at google.com>, "Philip Reames" <listmail at
philipreames.com>,
> "Hal Finkel" <hfinkel at anl.gov>
> Sent: Wednesday, September 28, 2016 5:39:38 PM
> Subject: IR canonicalization: select or bool math?
> I have another round of questions about IR select canonicalizations.
> For the purity of this quiz, please disregard prior knowledge of how
> this is handled by instcombine or how this is lowered by your
> favorite target...of course we'll fix it. :) Some answers in the
> links below if you do want to know.
> Which, if any, of these is canonical?
I think that we should prefer the single-IR-instruction forms as canonical.
zext/sext, when it is all that is needed, and the select otherwise. I suspect
that will be better for analysis and follow-on optimizations, at least most of
the time. For lowering, OTOH, I'd prefer the forms with zext/sext combined
with xor/add/sub.

-Hal 
> 1. Is a zext simpler than a select?
> a. define i32 @sel_1_or_0(i1 %a) {
> %b = select i1 %a, i32 1, i32 0
> ret i32 %b
> }
> b. define i32 @sel_1_or_0(i1 %a) {
> %b = zext i1 %a to i32
> ret i32 %b
> }
> 2. What if we have to 'not' the bool?
> a. define i32 @sel_0_or_1(i1 %a) {
> %b = select i1 %a, i32 0, i32 1
> ret i32 %b
> }
> b. define i32 @sel_0_or_1(i1 %a) {
> %not.a = xor i1 %a, true
> %b = zext i1 %not.a to i32
> ret i32 %b
> }
> 3. Is sext handled differently?
> a. define i32 @sel_-1_or_0(i1 %a) {
> %b = select i1 %a, i32 -1, i32 0
> ret i32 %b
> }
> b. define i32 @sel_-1_or_0(i1 %a) {
> %b = sext i1 %a to i32
> ret i32 %b
> }
> 4. What if the sext needs a 'not'?
> a. define i32 @sel_0_or_-1(i1 %a) {
> %b = select i1 %a, i32 0, i32 -1
> ret i32 %b
> }
> b. define i32 @sel_0_or_-1(i1 %a) {
> %not.a = xor i1 %a, true
> %b = sext i1 %not.a to i32
> ret i32 %b
> }
> 5. What if both constants are non-zero? Ie, the implicit add/sub of
> the earlier cases can't be eliminated.
> a. define i32 @sel_2_or_1(i1 %a) {
> %b = select i1 %a, i32 2, i32 1
> ret i32 %b
> }
> b. define i32 @sel_2_or_1(i1 %a) {
> %b = zext i1 to i32 %a
> %c = add i32 %b, 1
> ret i32 %b
> }
> 6. Does 'sub' make a difference?
> a. define i32 @sel_1_or_2(i1 %a) {
> %b = select i1 %a, i32 1, i32 2
> ret i32 %b
> }
> b. define i32 @sel_1_or_2(i1 %a) {
> %b = zext i1 %a to i32
> %c = sub i32 2, %b
> ret i32 %c
> }
> 7. Choose between integers that are not consecutive?
> a. define i32 @sel_0_or_2(i1 %a) {
> %sel = select i1 %a, i32 2, i32 0
> ret i32 %sel2
> }
> b. define i32 @sel_0_or_2(i1 %a) {
> %zexta = zext i1 %a to i32
> %add = add i32 %zexta, %zexta
> ret i32 %add
> }
> 8. Choose {0,1,2} based on 2 bools?
> a. define i32 @sel_sel(i1 %a, i1 %b) {
> %zexta = zext i1 %a to i32
> %sel1 = select i1 %a, i32 2, i32 1
> %sel2 = select i1 %b, i32 %sel1, %zexta
> ret i32 %sel2
> }
> b. define i32 @sel_sel(i1 %a, i1 %b) {
> %zexta = zext i1 %a to i32
> %zextb = zext i1 %b to i32
> %add = add i32 %zexta, %zextb
> ret i32 %add
> }
> Links for reference:
> https://llvm.org/bugs/show_bug.cgi?id=30273
> https://llvm.org/bugs/show_bug.cgi?id=30327
> https://reviews.llvm.org/D24480
-- 

Hal Finkel 
Lead, Compiler Technology and Programming Languages 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160928/793fdae8/attachment.html>

Thanks for sharing this! Quite interesting questions indeed :)

I regret that we don’t have any documentation (on the same level as LangRef)
that would record and describe the canonicalization of the IR and the motivation
for each case.

—
Mehdi
> On Sep 28, 2016, at 3:39 PM, Sanjay Patel via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> I have another round of questions about IR select canonicalizations. For
the purity of this quiz, please disregard prior knowledge of how this is handled
by instcombine or how this is lowered by your favorite target...of course
we'll fix it. :) Some answers in the links below if you do want to know.
> 
> Which, if any, of these is canonical?
>  
> 1. Is a zext simpler than a select?
> a. define i32 @sel_1_or_0(i1 %a) {
>   %b = select i1 %a, i32 1, i32 0
>   ret i32 %b
> }
> 
> b. define i32 @sel_1_or_0(i1 %a) {
>   %b = zext i1 %a to i32
>   ret i32 %b
> }
> 
> 2. What if we have to 'not' the bool?
> a. define i32 @sel_0_or_1(i1 %a) {
>   %b = select i1 %a, i32 0, i32 1
>   ret i32 %b
> }
> 
> b. define i32 @sel_0_or_1(i1 %a) {
>   %not.a = xor i1 %a, true
>   %b = zext i1 %not.a to i32
>   ret i32 %b
> }
> 
> 3. Is sext handled differently?
> a. define i32 @sel_-1_or_0(i1 %a) {
>   %b = select i1 %a, i32 -1, i32 0
>   ret i32 %b
> }
> 
> b. define i32 @sel_-1_or_0(i1 %a) {
>   %b = sext i1 %a to i32
>   ret i32 %b
> }
> 
> 4. What if the sext needs a 'not'?
> a. define i32 @sel_0_or_-1(i1 %a) {
>   %b = select i1 %a, i32 0, i32 -1
>   ret i32 %b
> }
> 
> b. define i32 @sel_0_or_-1(i1 %a) {
>   %not.a = xor i1 %a, true
>   %b = sext i1 %not.a to i32
>   ret i32 %b
> }
> 
> 5. What if both constants are non-zero? Ie, the implicit add/sub of the
earlier cases can't be eliminated.
> a. define i32 @sel_2_or_1(i1 %a) {
>   %b = select i1 %a, i32 2, i32 1
>   ret i32 %b
> }
> 
> b. define i32 @sel_2_or_1(i1 %a) {
>   %b = zext i1 to i32 %a
>   %c = add i32 %b, 1
>   ret i32 %b
> }
> 
> 6. Does 'sub' make a difference?
> a. define i32 @sel_1_or_2(i1 %a) {
>   %b = select i1 %a, i32 1, i32 2
>   ret i32 %b
> }
> 
> b. define i32 @sel_1_or_2(i1 %a) {
>   %b = zext i1 %a to i32
>   %c = sub i32 2, %b
>   ret i32 %c
> }
> 
> 7. Choose between integers that are not consecutive?
> a. define i32 @sel_0_or_2(i1 %a) {
>   %sel = select i1 %a, i32 2, i32 0
>   ret i32 %sel2
> }
> 
> b. define i32 @sel_0_or_2(i1 %a) {
>   %zexta = zext i1 %a to i32
>   %add = add i32 %zexta, %zexta
>   ret i32 %add
> }
> 
> 8. Choose {0,1,2} based on 2 bools?
> a. define i32 @sel_sel(i1 %a, i1 %b) {
>   %zexta = zext i1 %a to i32
>   %sel1 = select i1 %a, i32 2, i32 1
>   %sel2 = select i1 %b, i32 %sel1, %zexta
>   ret i32 %sel2
> }
> 
> b. define i32 @sel_sel(i1 %a, i1 %b) {
>   %zexta = zext i1 %a to i32
>   %zextb = zext i1 %b to i32
>   %add = add i32 %zexta, %zextb
>   ret i32 %add
> }
> 
> Links for reference:
> https://llvm.org/bugs/show_bug.cgi?id=30273
<https://llvm.org/bugs/show_bug.cgi?id=30273>
> https://llvm.org/bugs/show_bug.cgi?id=30327
<https://llvm.org/bugs/show_bug.cgi?id=30327>
> https://reviews.llvm.org/D24480 <https://reviews.llvm.org/D24480>
> 
> _______________________________________________
> 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/20160928/aacc363d/attachment.html>

> On Sep 28, 2016, at 5:41 PM, Hal Finkel via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
> I have another round of questions about IR select canonicalizations. For
the purity of this quiz, please disregard prior knowledge of how this is handled
by instcombine or how this is lowered by your favorite target...of course
we'll fix it. :) Some answers in the links below if you do want to know.
> 
> Which, if any, of these is canonical?
> I think that we should prefer the single-IR-instruction forms as canonical.
zext/sext, when it is all that is needed, and the select otherwise. I suspect
that will be better for analysis and follow-on optimizations, at least most of
the time. For lowering, OTOH, I'd prefer the forms with zext/sext combined
with xor/add/sub.
Right.  That’s the general (abstract, and probably not uniformly followed) goal:
canonicalize towards the conceptually most strength reduced operation.  zext is
simpler than select, so it should be more canonical when it applies.

-Chris
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160928/fb2f39f1/attachment.html>

My gut tells me that Hal is right, and we should prefer zexts as long
as the select boils down to one instruction, but let me go against my
intuition and try to list two reasons why we should prefer selects:

  * Folding operations into selects: it is trivial to transform
    f(select X, Const0, Const1) to select X, f(Const0), f(Const1),
    while doing that can be difficult for zexts.

    define i32 @sel_1_or_0(i1 %a) {
      %b = select i1 %a, i32 1, i32 0
      %k = add i32 %b, 50
      ret i32 %k
    }

    ==>

    define i32 @sel_1_or_0(i1 %a) {
      %b = select i1 %a, i32 51, i32 50
      ret i32 %b
    }

    but

    define i32 @sel_1_or_0(i1 %a) {
      %b = zext i1 %a to i32
      %k = add i32 %b, 50
      ret i32 %k
    }

    is not as natural to transform.

  * zexts (resp. sexts) lose information when combined with nuw
    (resp. nsw) operations.

    That is, if we inline

    define i32 @sel_1_or_0(i1 %a) {
      %b = zext i1 %a to i32
      ret i32 %b
    }

    into f and get

    define i32 @f(i32 %x, i32 %y) {
      %x.zext = ...
      %y.zext = ...
      ;; There are some existing use of %x.zext and %y.zext
      %a = add nuw i1 %x, %y
      %b = zext i1 %a to i32
      ret i32 %b
    }

    then we'll get (following your instructions, I've not verified that
    this actually happens :) )

    define i32 @f(i1 %x, i1 %y) {
      %x.zext = ...
      %y.zext = ...
      %a = add nuw i32 %x.zext, %y.zext
      ret i32 %a
    }

    but we've now lost information -- we no longer know that %a is 0 or
    1 -- it can also be 2.  This would not happen if we always
    canonicalized zext i1 C to iN to select C, iN 1, iN 0

-- Sanjoy