[InstCombine] Fold shl of constant by cttz into multiply of lowest set bit - #214517
Merged
Conversation
llvmorg-github-actions
Bot
added
llvm:instcombine
Contributor
Author
|
ping |
Contributor
Author
|
@nikic Could you take a look when you have time? Thank you! |
…project into instcombine-shl # 请输入一个提交信息以解释此合并的必要性，尤其是将一个更新后的上游分支 # 合并到主题分支。 # # 以 '#' 开始的行将被忽略，而空的提交说明将终止提交。
Update comment to clarify behavior of is_zero_poison.
Contributor
Author
|
ping |
dtcxzyw
reviewed
Aug 14, 2026
dtcxzyw
left a comment
dtcxzyw
left a comment
Member
There was a problem hiding this comment.
Generalized proof: https://alive2.llvm.org/ce/z/TmWxrT
| { | ||
| Value *X; | ||
| const APInt *C; | ||
| if (match(Op0, m_APInt(C)) && |
Member
There was a problem hiding this comment.
It should not be limited to constant LHS cases.
Removing the constraint enables more optimizations:
dtcxzyw/llvm-opt-benchmark-nightly#924
dtcxzyw/llvm-opt-benchmark-nightly#926
| Value *X; | ||
| const APInt *C; | ||
| if (match(Op0, m_APInt(C)) && | ||
| match(Op1, m_OneUse(m_Cttz(m_Value(X), m_One())))) { |
Member
There was a problem hiding this comment.
Suggested change
| match(Op1, m_OneUse(m_Cttz(m_Value(X), m_One())))) { | |
| match(Op1, m_OneUse(m_Cttz(m_Value(X), m_Value())))) { |
is_zero_poison can be false.
| match(Op1, m_OneUse(m_Cttz(m_Value(X), m_One())))) { | ||
| Value *NegX = Builder.CreateNeg(X, "neg"); | ||
| Value *LowBit = Builder.CreateAnd(NegX, X); | ||
| return BinaryOperator::CreateMul(LowBit, Op0); |
Contributor
Author
There was a problem hiding this comment.
Thank you for your suggestions. I'll update this patch.
Contributor
Author
|
@dtcxzyw, I've updated the patch to address your feedback:
|
dtcxzyw
approved these changes
Aug 15, 2026
Comment on lines
+1386
to
+1387
| { | ||
| Value *X; |
Member
There was a problem hiding this comment.
Suggested change
| { | |
| Value *X; |
Just use the declaration above.
Contributor
Author
There was a problem hiding this comment.
Applied your suggetion, thanks
…sary brace and reuse existing X variable declaration
dtcxzyw
enabled auto-merge (squash)
August 16, 2026 07:42
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/218/builds/6108 Here is the relevant piece of the build log for the reference |
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/151/builds/10843 Here is the relevant piece of the build log for the reference |
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/158/builds/19926 Here is the relevant piece of the build log for the reference |
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/216/builds/6025 Here is the relevant piece of the build log for the reference |
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/119/builds/10749 Here is the relevant piece of the build log for the reference |
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/105/builds/20560 Here is the relevant piece of the build log for the reference |
Member
|
Should this fold be implemented in codegen instead? It introduced regressions on both aarch64 and x86. |
Member
See https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/926/files. In some cases the mul will be removed by other middle-end optimizations. The backend should recognize this pattern and revert the transform. I am worried that is_zero_poison may not be re-inferred in SDAG. If this is a bottleneck, we have to implement this fold in DAGCombiner. cc @RKSimon |
Contributor
|
Most likely this needs tweaking in isel as a per-backend (not generic) fold - hopefully avoiding a tuning flag....... |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
5 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Currently,
C << cttz(X, true)generates a DeBruijn lookup table on RV64I (13 instructions).And this patch adds a fold in InstCombine:
C << cttz(X, true) --> (-X & X) * CThis reduces the instruction count from 13 to 3 on RV64I.
The fold requires that cttz has a single use (to avoid increasing instruction count)
Alive2 proof: https://alive2.llvm.org/ce/z/TmWxrT