[InstCombine] failed to convert selects into add

[rotateright]

Bugzilla Link	30273
Version	trunk
OS	All
CC	@preames,@RKSimon

Extended Description

This example is a simplified test based on actual code in InstCombineCompares.cpp as of r280624:

$ cat boolcow.c

#include <stdbool.h>

unsigned foo(bool a, bool b) {
  unsigned ret = 0;
  if (a) ++ret;
  if (b) ++ret;
  return ret;
}

This is logically equivalent in C99 or C++ to:

unsigned goo(bool a, bool b) {
  return a + b;
}

It seems that there's a missing transform in InstCombine itself because the IR for these two cases is:

$ ./clang -O1 boolcow.c -S -o - -emit-llvm

define i32 @foo(i1 %a, i1 %b) {
  %. = zext i1 %a to i32
  %inc4 = select i1 %a, i32 2, i32 1
  %ret.1 = select i1 %b, i32 %inc4, i32 %.
  ret i32 %ret.1
}

define i32 @goo(i1 %a, i1 %b) {
  %conv = zext i1 %a to i32
  %conv3 = zext i1 %b to i32
  %add = add nuw nsw i32 %conv3, %conv
  ret i32 %add
}

...so fix this bug, and the compiler might get faster. :)

[preames]

When looking at some findings from Souper (John Regehr's super optimizer tool) for some of our IR, I found a whole bunch of variations on this pattern.

Many of these have encodings on x86 using ADC or SBC to materialize carry flags. We don't get them in the backend today. That's not directly relevant for instcombine, but it may be evidence that we're canonicalizing the wrong direction here.

;; Can become %a + zext %c
define i8 @sel1(i8 %a) {
  %c = icmp eq i8 %a, 25
  %res = select i1 %c, i8 26, i8 %a
  ret i8 %res
}

define i8 @sel1alt(i8 %a) {
  %c = icmp eq i8 %a, 25
  %d = zext i1 %c to i8
  %res = add i8 %a, %d
  ret i8 %res
}

;; Can become %a + sext %c
define i8 @sel1neg(i8 %a) {
  %c = icmp eq i8 %a, 25
  %res = select i1 %c, i8 24, i8 %a
  ret i8 %res
}

;; Can become 46 + zext %c
define i8 @sel_con1(i8 %a, i1 %c) {
  %res = select i1 %c, i8 47, i8 46
  ret i8 %res
}

;; Can become 46 + (zext %c * 4)
define i8 @sel_con2(i8 %a, i1 %c) {
  %res = select i1 %c, i8 50, i8 46
  ret i8 %res
}

;; Can become 46 + sext %c
define i8 @sel_con3(i8 %a, i1 %c) {
  %res = select i1 %c, i8 46, i8 45
  ret i8 %res
}

;; Can become 57 * zext %c
define i8 @sel_con5(i8 %a, i1 %c) {
  %res = select i1 %c, i8 57, i8 0
  ret i8 %res
}

;; Can become sext(%c) | 1
define i8 @sel_con4(i8 %a, i1 %c) {
  %res = select i1 %c, i8 -1, i8 1
  ret i8 %res
}

[rotateright]

In the most basic case, we need to recognize that a select with 'true op' == 'false op' + 1 is an ext+add:

define i32 @​f(i1 %a) { %sel = select i1 %a, i32 2, i32 1 ret i32 %sel }

This won't be straightforward. There's already a canonicalization in InstCombine to go the opposite way:

// zext(bool) + C -> bool ? C + 1 : C
if (ZExtInst *ZI = dyn_cast<ZExtInst>(LHS))
  if (ZI->getSrcTy()->isIntegerTy(1))
    return SelectInst::Create(ZI->getOperand(0), AddOne(CI), CI);

[rotateright]

In the most basic case, we need to recognize that a select with 'true op' == 'false op' + 1 is an ext+add:

define i32 @f(i1 %a) {
  %sel = select i1 %a, i32 2, i32 1
  ret i32 %sel
}

[rotateright]

If we simplify to just one bool input value, we still miss this:

unsigned foo(bool a) {
  unsigned ret = 0;
  if (a) ++ret;
  if (a) ++ret;
  return ret;
}

unsigned goo(bool a) {
  return a + a;
}

define i32 @foo(i1 zeroext %a) {
  %. = zext i1 %a to i32
  %ret.1 = select i1 %a, i32 2, i32 %.
  ret i32 %ret.1
}

define i32 @goo(i1 %a) {
  %conv = zext i1 %a to i32
  %add = shl nuw nsw i32 %conv, 1
  ret i32 %add
}