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 47241 - ValueTracking: Compute known bits doesn't leverage range information on gep
Summary: ValueTracking: Compute known bits doesn't leverage range information on gep
Status: NEW
Alias: None
Product: libraries
Classification: Unclassified
Component: Global Analyses (show other bugs)
Version: trunk
Hardware: PC All
: P enhancement
Assignee: Unassigned LLVM Bugs
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2020-08-19 14:27 PDT by Quentin Colombet
Modified: 2020-10-22 10:43 PDT (History)
2 users (show)

See Also:
Fixed By Commit(s):


Attachments
Case that gets simplified (197 bytes, text/plain)
2020-08-19 14:27 PDT, Quentin Colombet
Details
Case that doesn't get simplified (reproducer) (279 bytes, text/plain)
2020-08-19 14:27 PDT, Quentin Colombet
Details
Tentative fix for the computeKnownBits part (14.31 KB, patch)
2020-08-20 16:18 PDT, Quentin Colombet
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Quentin Colombet 2020-08-19 14:27:14 PDT
Created attachment 23863 [details]
Case that gets simplified

The ValueTracking analysis only tries to fill up trailing zeros when going through GEPs.
In particular, the analysis doesn't take advantage of the range information that may be available, resulting and suboptimal code.

* Example *

Consider the following snippet:
```
define i1 @test4_gep(i64* %ptr) {
entry:
  %val = load volatile i64, i64* %ptr, !range !{i64 64, i64 65536}
  %valptr = inttoptr i64 %val to float*
  %gep = getelementptr float, float* %valptr, i64 128 
  %res = icmp ugt float* %gep, inttoptr (i64 523 to float*)
  ret i1 %res
}
```

Using the range information this example can be simplified into the following code, since 64 + 4*128 is guaranteed to be bigger than 523:
```
define i1 @test4_gep(i64* %ptr) {
entry:
  %val = load volatile i64, i64* %ptr, !range !{i64 64, i64 65536}
  ret i1 true
}
```

But given ValueTracking doesn't leverage the range information, no simplification happens.

Now, rewrite this code with an add like so:
```
define i1 @test3_add(i64* %ptr) {
entry:
  %val = load volatile i64, i64* %ptr, !range !{i64 64, i64 65536}
  %valPlus512 = add i64 %val, 512
  %res = icmp ugt i64 %valPlus512, 523
  ret i1 %res
}
```

And ValueTracking provides the proper known bits and the simplification can happen.

* To Reproduce *
# Not simplified.
opt -S -instcombine value_tracking_gep.ll  -o -
# Simplified.
opt -S -instcombine value_tracking_add.ll  -o -

Note: I have to use a volatile load to prevent instcombine for dropping the range information. I'll file a separate PR for that.
Comment 1 Quentin Colombet 2020-08-19 14:27:47 PDT
Created attachment 23864 [details]
Case that doesn't get simplified (reproducer)
Comment 2 Quentin Colombet 2020-08-19 15:00:27 PDT
File https://llvm.org/PR47243 for the other issue.
Comment 3 Quentin Colombet 2020-08-20 16:18:45 PDT
Created attachment 23869 [details]
Tentative fix for the computeKnownBits part
Comment 4 Quentin Colombet 2020-08-24 10:46:55 PDT
(In reply to Quentin Colombet from comment #3)
> Created attachment 23869 [details]
> Tentative fix for the computeKnownBits part

That's https://reviews.llvm.org/D86364
Comment 5 Quentin Colombet 2020-10-22 10:43:27 PDT
As of e97e9851b22, compute known bits performs the proper analysis on gep.
Next step is to teach instcombine that `inttoptr (i64 523 to float*)` is a compile time constant.