[InstCombine] Failure to recognise CTTZ pattern using CTLZ

[RKSimon]

While we correctly fold this hackers delight ctpop pattern into ctz:

define i4 @src_ctpop(i4 %a0) {
  %dec = add i4 %a0, -1
  %not = xor i4 %a0, -1
  %and = and i4 %dec, %not
  %clz = tail call i4 @llvm.ctpop.i4(i4 %and)
  ret i4 %clz
}
define i4 @tgt_ctpop(i4 %a0) {
  %ctz = tail call i4 @llvm.cttz.i4(i4 %a0, i1 false)
  ret i4 %ctz
}

we fail to recognise the related clz pattern:

define i4 @src_lz(i4 %a0) {
  %dec = add i4 %a0, -1
  %not = xor i4 %a0, -1
  %and = and i4 %dec, %not
  %clz = tail call i4 @llvm.ctlz.i4(i4 %and, i1 false) ; undef = true is ok as well
  %ctz = sub i4 4, %clz
  ret i4 %ctz
}
define i4 @tgt_lz(i4 %a0) {
  %ctz = tail call i4 @llvm.cttz.i4(i4 %a0, i1 false)
  ret i4 %ctz
}

Alive2: https://alive2.llvm.org/ce/z/AdPVa5

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor is working on this issue. If someone is assigned to the issue or claimed to be working on it, ping the person. After one week without a response, the assignee may be changed.
2. Leave a comment indicating that you are working on the issue, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Simon Pilgrim (RKSimon)

While we correctly fold this hackers delight ctpop pattern into ctz: ```ll define i4 @src_ctpop(i4 %a0) { %dec = add i4 %a0, -1 %not = xor i4 %a0, -1 %and = and i4 %dec, %not %clz = tail call i4 @llvm.ctpop.i4(i4 %and) ret i4 %clz } define i4 @tgt_ctpop(i4 %a0) { %ctz = tail call i4 @llvm.cttz.i4(i4 %a0, i1 false) ret i4 %ctz } ``` we fail to recognise the related clz pattern: ```ll define i4 @src_lz(i4 %a0) { %dec = add i4 %a0, -1 %not = xor i4 %a0, -1 %and = and i4 %dec, %not %clz = tail call i4 @llvm.ctlz.i4(i4 %and, i1 false) ; undef = true is ok as well %ctz = sub i4 4, %clz ret i4 %ctz } define i4 @tgt_lz(i4 %a0) { %ctz = tail call i4 @llvm.cttz.i4(i4 %a0, i1 false) ret i4 %ctz } ```

Alive2: https://alive2.llvm.org/ce/z/AdPVa5

[RKSimon]

Some playing with this suggests the last sub often disappears before the clz pattern could be matched so this might be a better fold:

define i4 @src_lz(i4 %a0) {
  %dec = add i4 %a0, -1
  %not = xor i4 %a0, -1
  %and = and i4 %dec, %not
  %clz = tail call i4 @llvm.ctlz.i4(i4 %and, i1 false) ; undef = true is ok as well
  ret i4 %clz
}
define i4 @tgt_lz(i4 %a0) {
  %ctz = tail call i4 @llvm.cttz.i4(i4 %a0, i1 false)
  %res = sub i4 4, %ctz
  ret i4 %res
}

[MihailMihov]

I would like to work on this. :)

[dtcxzyw]

I would like to work on this. :)

Please read https://llvm.org/docs/InstCombineContributorGuide.html before submitting a patch.