Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

missed optimization for y / x when the divisor has [0, 1] range #74242

Closed
k-arrows opened this issue Dec 3, 2023 · 1 comment · Fixed by #73662
Closed

missed optimization for y / x when the divisor has [0, 1] range #74242

k-arrows opened this issue Dec 3, 2023 · 1 comment · Fixed by #73662
Labels
llvm:instcombine missed-optimization

Comments

@k-arrows
Copy link

k-arrows commented Dec 3, 2023

Test case:
https://godbolt.org/z/aonazK5on

unsigned int 
foo(unsigned int x, unsigned int y)
{
  if(x > 1)
    return y;
  return y / x;
}

motivated from the following gcc bugzilla and test:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96094
https://github.com/gcc-mirror/gcc/blob/master/gcc/testsuite/gcc.dg/tree-ssa/pr96094.c
@nikic
Copy link
Contributor

nikic commented Dec 3, 2023

I haven't checked, but it's likely that #73662 will fix this.

This was referenced Dec 3, 2023
Merged
Merged
nikic added a commit that referenced this issue Dec 4, 2023
@nikic
[InstCombine] Add test for #74242 (NFC)
1623292
nikic added a commit that referenced this issue Dec 6, 2023
@nikic
[ValueTracking] Add dominating condition support in computeKnownBits() (
d77067d 
#73662)

This adds support for using dominating conditions in computeKnownBits()
when called from InstCombine. The implementation uses a
DomConditionCache, which stores which branches may provide information
that is relevant for a given value.

DomConditionCache is similar to AssumptionCache, but does not try to do
any kind of automatic tracking. Relevant branches have to be explicitly
registered and invalidated values explicitly removed. The necessary
tracking is done inside InstCombine.

The reason why this doesn't just do exactly the same thing as
AssumptionCache is that a lot more transforms touch branches and branch
conditions than assumptions. AssumptionCache is an immutable analysis
and mostly gets away with this because only a handful of places have to
register additional assumptions (mostly as a result of cloning). This is
very much not the case for branches.

This change regresses compile-time by about ~0.2%. It also improves
stage2-O0-g builds by about ~0.2%, which indicates that this change results
in additional optimizations inside clang itself.

Fixes #74242.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
llvm:instcombine missed-optimization
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

[ValueTracking] Add dominating condition support in computeKnownBits() nikic/llvm-project
3 participants
@nikic @EugeneZelenko @k-arrows