[InstCombine] Infer exact for lshr by cttz

[nikic]

From rust-lang/rust#138497:

define i8 @src(i8 %x) {
  %cttz = call i8 @llvm.cttz.i8(i8 %x, i1 false)
  %lshr = lshr i8 %x, %cttz
  ret i8 %lshr
}

define i8 @tgt(i8 %x) {
  %cttz = call i8 @llvm.cttz.i8(i8 %x, i1 false)
  %lshr = lshr exact i8 %x, %cttz
  ret i8 %lshr
}

https://alive2.llvm.org/ce/z/KFemjy

This then allows folding icmp eq %lshr, 0.

[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: Nikita Popov (nikic)

From https://github.com/rust-lang/rust/issues/138497:

define i8 @<!-- -->src(i8 %x) {
  %cttz = call i8 @<!-- -->llvm.cttz.i8(i8 %x, i1 false)
  %lshr = lshr i8 %x, %cttz
  ret i8 %lshr
}

define i8 @<!-- -->tgt(i8 %x) {
  %cttz = call i8 @<!-- -->llvm.cttz.i8(i8 %x, i1 false)
  %lshr = lshr exact i8 %x, %cttz
  ret i8 %lshr
}

https://alive2.llvm.org/ce/z/KFemjy

This then allows folding icmp eq %lshr, 0.

[nikic]

Should be able to handle this with an extra special case similar to this one:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Lines 992 to 996 in 2549517

	// shr (shl X, Y), Y
	if (match(I.getOperand(0), m_Shl(m_Value(), m_Specific(I.getOperand(1))))) {
	I.setIsExact();
	return true;
	}

If you're new to InstCombine development, please take a look at https://llvm.org/docs/InstCombineContributorGuide.html first.

[aayush-tripathi]

I would like to work on this!

[houngkoungting]

Hi @aayush-tripathi , I see you’re assigned to #131444. I’m a new contributor and have a working solution with updated tests ready. Are you currently working on this? If not, I’d like to submit a PR. Happy to coordinate if you’re already on it!

[aayush-tripathi]

Hi @aayush-tripathi , I see you’re assigned to #131444. I’m a new contributor and have a working solution with updated tests ready. Are you currently working on this? If not, I’d like to submit a PR. Happy to coordinate if you’re already on it!

Hey @houngkoungting ! I am actually currently working on this issue and have made some progress. We can collaborate on this, maybe you could review my PR, I plan to submit one soon.

Thanks!

[nikic]

@aayush-tripathi Have you made any progress on this issue?

[houngkoungting]

HI @nikic , I believe I have a solution for this issue.