[llvm-dev] IR canonicalization: select or bool math?

[Hal Finkel via llvm-dev]

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