Page MenuHomePhabricator

[InstCombine] remove fold: zext(bool) + C -> bool ? C + 1 : C
AbandonedPublic

Authored by spatel on Sep 12 2016, 4:28 PM.

Details

Summary

This is a small patch with a long backstory.

First, I'm proposing to remove a fold of (zext i1) + C to select of constants.
A pair of sibling folds for this was added at:
https://reviews.llvm.org/rL75531

The commit was made with a request for feedback in case selects might not be the best form. 3 years later, we lost half of the transform with:
https://reviews.llvm.org/rL159230

Sadly, that commit just removed code and didn't bother to canonicalize the other way (from select to ext+add). That left us in a state where logically equivalent code could be present in multiple forms - PR30327:
https://llvm.org/bugs/show_bug.cgi?id=30327

So in addition to removing the remaining piece of r75531, I'm proposing to canonicalize selects to ext+add and filling in whatever folds may be missing as follow-up patches (see the motivating case based on the source code for InstCombine itself in PR30273).

There are a few reasons to prefer ext+add to select:

  1. Adds with constants are easier to combine with other adds and subs.
  2. We are already canonicalizing selects with {-1,0,1} to extends; doing this for all constants is more consistent.
  3. As noted, we already lost half of the original patch, so we're not even consistent about C+1 vs. C-1.
  4. The stated reason for killing the C-1 half of the patch was poor codegen. This is not a valid reason by itself to change a canonicalization (just fix the backend). However, as a practical matter, it is 7 years later and we still have not fixed the backend! See the codegen examples for AArch64 and PowerPC here:

https://llvm.org/bugs/show_bug.cgi?id=30327#c2

In order to avoid a regression on the tests in test/Transforms/InstCombine/icmp-div-constant.ll (note that those are phantom diffs), I'm adding a fold that converts icmp (add (zext), -1) to icmp' (sext) in this patch. I'm not sure how to expose this difference independently of removing the select fold.

Diff Detail

Event Timeline

spatel updated this revision to Diff 71070.Sep 12 2016, 4:28 PM
spatel retitled this revision from to [InstCombine] remove fold: zext(bool) + C -> bool ? C + 1 : C.
spatel updated this object.
spatel added reviewers: efriedma, majnemer, hfinkel.
spatel added a subscriber: llvm-commits.
majnemer edited edge metadata.Sep 12 2016, 4:41 PM

I think r159230 was a step in the wrong direction. An add with a zext seems harder to reason about than a select.

I think r159230 was a step in the wrong direction. An add with a zext seems harder to reason about than a select.

This seems similar to the select -> shuffle canonicalization (D24279) to me. I think it's easier to *read* a select in the IR (I was initially in favor of the select in that case), but it's easier to *combine* the alternative (shuffles or adds). Please let me know if you see an example where a select is easier to combine either in IR or the DAG.

Note that I'm starting from the perspective of:
https://llvm.org/bugs/show_bug.cgi?id=30273

Ie, it's going to take more work to untangle these selects to the adds that most (all?) targets would prefer to codegen:

define i32 @selects_are_hard(i1 zeroext %a, i1 zeroext %b, i1 zeroext %c) {
  %. = zext i1 %a to i32
  %inc5 = select i1 %a, i32 2, i32 1
  %ret.1 = select i1 %b, i32 %inc5, i32 %.
  %inc9 = zext i1 %c to i32
  %inc9.ret.1 = add nuw nsw i32 %inc9, %ret.1
  ret i32 %inc9.ret.1
}

define i32 @adds_are_easy(i1 zeroext %a, i1 zeroext %b, i1 zeroext %c) {
  %conv = zext i1 %a to i32
  %conv4 = zext i1 %b to i32
  %add = add nuw nsw i32 %conv4, %conv
  %conv6 = zext i1 %c to i32
  %add7 = add nuw nsw i32 %add, %conv6
  ret i32 %add7
}

I think IR should be canonicalized with ValueTracking in mind (ComputeKnownBits, etc.)
That SelectionDAG doesn't know how to make selects lower nicely is a problem but it can be localized late in codegen: either in SDAG itself or CGP.

efriedma edited edge metadata.Sep 12 2016, 5:24 PM

The general direction seems fine.

lib/Transforms/InstCombine/InstCombineAddSub.cpp
1070

I guess we should prefer sext(cmp) over add(zext(cmp), -1), but we prefer add(zext(cmp), N) over add(sext(cmp), N-1) for any other N? That works, but you might want to explain that here.

arsenm added a subscriber: arsenm.Sep 12 2016, 5:26 PM

I think IR should be canonicalized with ValueTracking in mind (ComputeKnownBits, etc.)
That SelectionDAG doesn't know how to make selects lower nicely is a problem but it can be localized late in codegen: either in SDAG itself or CGP.

+1

I think IR should be canonicalized with ValueTracking in mind (ComputeKnownBits, etc.)

That sounds good, but this raises questions for me:

  1. Why is select i8 %bool, i8 2, i8 1 better for ValueTracking than zext i1 %bool to i8; add nuw nsw i8 %z, 1? Is there a fundamental or practical difference in what computeKnownBits can extract from either of those?
  1. If select has an advantage and is the canonical form for the case of choosing between constants, then should we remove these existing transforms?
    1. select b, 1, 0 -> zext b to int
    2. select b, -1, 0 -> sext b to int
    3. select b, 0, 1 -> zext !b to int
    4. select b, 0, -1 -> sext !b to int
  1. Is the IR for @selects_are_hard in my earlier comment canonical? Ie, is a select with variable operands also preferred over an add: %ret.1 = select i1 %b, i32 %inc5, i32 %. ?
  1. Should I send a note to llvm-dev for a wider audience?
spatel updated this revision to Diff 72579.Sep 26 2016, 3:28 PM
spatel edited edge metadata.

Ping.

Patch updated:
Added comment about this case of sext over zext as suggested by Eli.

efriedma accepted this revision.Sep 26 2016, 3:54 PM
efriedma edited edge metadata.

LGTM. (If you want to discuss more general questions of when we should prefer select vs. arithmetic, please bring it up on llvmdev.)

This revision is now accepted and ready to land.Sep 26 2016, 3:54 PM

LGTM. (If you want to discuss more general questions of when we should prefer select vs. arithmetic, please bring it up on llvmdev.)

Thanks, Eli.
Sure - I'll post the issues raised here on llvm-dev, so we can get more feedback before trying to commit this.

There seems to be consensus that we should canonicalize towards select in IR (ie, as David suggested - rL159230 was a mistake):
http://lists.llvm.org/pipermail/llvm-dev/2016-September/105335.html
...so I will most likely abandon this patch eventually. Leaving as-is for the moment just in case that changes. And maybe we still want to make the add(zext) --> sext transform as an independent change.

spatel abandoned this revision.Nov 29 2017, 10:05 AM

Abandoning - see D40612.