LLVM Bugzilla is read-only and represents the historical archive of all LLVM issues filled before November 26, 2021. Use github to submit LLVM bugs

Bug 19711 - ComputeMaskedBits & friends should know that multiplying by a power of two leaves low bits clear
Summary: ComputeMaskedBits & friends should know that multiplying by a power of two le...
Status: RESOLVED FIXED
Alias: None
Product: libraries
Classification: Unclassified
Component: Scalar Optimizations (show other bugs)
Version: trunk
Hardware: PC All
: P normal
Assignee: Unassigned LLVM Bugs
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-05-11 11:24 PDT by Chris Lattner
Modified: 2021-04-06 05:29 PDT (History)
10 users (show)

See Also:
Fixed By Commit(s):


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Chris Lattner 2014-05-11 11:24:12 PDT
John Regehr reports that GCC is folding X*2&1 to zero.  ComputedMaskedBits and SimplifyDemandedBits should know that multiplications by powers of two leave predictable zeros in the low bits of the result.
Comment 1 Nick Lewycky 2014-05-12 20:22:16 PDT
The bug John reported is: "int a, b; void fn1() { b = a * ~1 == 1; }" and missed IR pattern is:

  %mul = mul nsw i32 %0, -2
  %cmp = icmp eq i32 %mul, 1

What we're missing is that ctz(x*y) >= max(ctz(x), ctz(y)). For %mul that gets us one trailing zero.

Fortunately we get x*2&1 right, and both ComputeMaskedBits and SimplifyDemandedBits know about that one ...
Comment 2 Jay Foad 2014-05-13 03:42:17 PDT
> What we're missing is that ctz(x*y) >= max(ctz(x), ctz(y)). For %mul that gets
> us one trailing zero.

ComputeMaskedBitsMul already does that.

Maybe (in)equality comparisons need to be taught that their operands can't be equal if one has a known zero where the other has a known one?
Comment 3 Jay Foad 2014-05-23 05:17:36 PDT
> Maybe (in)equality comparisons need to be taught that their operands can't be
> equal if one has a known zero where the other has a known one?

Proposed patch here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20140519/218082.html
Comment 4 Gabriel Ravier 2021-02-01 01:24:44 PST
Both the test case in the first and the second post seem to be fixed on trunk.
Comment 5 Jay Foad 2021-02-01 03:51:25 PST
This probably got fixed by https://reviews.llvm.org/D12801 "[ValueTracking] Add a new predicate: isKnownNonEqual()".
Comment 6 Simon Pilgrim 2021-04-06 05:29:59 PDT
Resolving, this was fixed around 3.5: https://c.godbolt.org/z/h7EK93q6T