Possible improvement for SimplifyDemandedBits for Mul

[topperc]

If the RHS is a constant with X trailing zeros, then the X MSBs of the LHS are not demanded.

I don't have any plans to do anything with this right now. Just something I thought of while working on https://reviews.llvm.org/D130146 That patch does special isel for (i64 (mul (and X, 0xffffffff), 3 << C)) and requires C < 32. If C >= 32 the AND could be removed, but it doesn't happen today.

FYI @spatel-gh @RKSimon

[RKSimon]

I've been able to prove it if the upper bits of x are simplified to zero: https://alive2.llvm.org/ce/z/NLzMby

But I haven't yet managed to create a test that shows that the upper bits don't matter at all.

[topperc]

Modified your proof to force the bits to 1 instead of 0 and it also verifies https://alive2.llvm.org/ce/z/f5AL-u

[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 has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, 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: Craig Topper (topperc)

If the RHS is a constant with X trailing zeros, then the X MSBs of the LHS are not demanded.

I don't have any plans to do anything with this right now. Just something I thought of while working on https://reviews.llvm.org/D130146 That patch does special isel for (i64 (mul (and X, 0xffffffff), 3 << C)) and requires C < 32. If C >= 32 the AND could be removed, but it doesn't happen today.

FYI @spatel-gh @RKSimon

[RKSimon]

This is the best I've managed: https://alive2.llvm.org/ce/z/F5CyJW

----------------------------------------
define i8 @src(i8 %x, i8 %y, i8 %garbage) {
#0:
  %yz = icmp ne i8 %y, 0
  assume i1 %yz
  %r = mul i8 %x, %y
  ret i8 %r
}
=>
define i8 @tgt(i8 %x, i8 %y, i8 %garbage) {
#0:
  %garbagef = freeze i8 %garbage
  %ytz = cttz i8 %y, 0
  %xm = lshr i8 255, %ytz
  %xmn = xor i8 255, %xm
  %garbagebits = and i8 %xmn, %garbagef
  %xx = or i8 %x, %garbagebits
  %r = mul i8 %xx, %y
  ret i8 %r
}
Transformation seems to be correct!

Basically, we can insert whatever we want to the upper bits of X and it should still work.