https://gcc.gnu.org/bugzilla/show_bug.cgi?id=127913
Bug ID: 127913
Summary: Unnecessary 128-bit arithmetic in ranges::lower_bound
over a bounded iota_view
Product: gcc
Version: 16.2.1
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: adamant.pwn at gmail dot com
Target Milestone: ---
Created attachment 65850
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65850&action=edit
Preprocessed reproducer and GCC build configuration
I ran into this when replacing an indexed binary search with
`std::ranges::lower_bound` over `std::views::iota`. The iota version keeps
128-bit distance arithmetic in the search loop, even when the compiler knows
that both bounds are between 0 and 100.
```cpp
#include <algorithm>
#include <cstdint>
#include <ranges>
using U = std::uint64_t;
U iota_search(const U* data, U first, U last, U value)
{
if (first > last || last > 100)
__builtin_unreachable();
auto indices = std::views::iota(first, last);
auto it = std::ranges::lower_bound(indices, value, {},
[&](U i) { return data[i]; });
return first + (it - indices.begin());
}
U pointer_search(const U* data, U first, U last, U value)
{
if (first > last || last > 100)
__builtin_unreachable();
return std::ranges::lower_bound(data + first, data + last, value) - data;
}
```
Reproduced with GCC 16.2.1 20260810 (Arch Linux), target `x86_64-pc-linux-gnu`:
```sh
g++ -std=c++20 -O2 -S -masm=intel repro.cpp
```
`iota_search` emits `shrd`, `adc` and `sbb` for the loop's distance
calculations. `pointer_search` uses ordinary 64-bit arithmetic. The same
happens at `-O3`.
The wider difference type makes sense for a general 64-bit iota range, but here
the distance starts at no more than 100 and only decreases. Could that
arithmetic be narrowed after inlining?
The attached preprocessed source includes the full `g++ -v` output in a
comment. Compiling with `-Wall -Wextra -D_GLIBCXX_ASSERTIONS` produces no
diagnostics.
Assisted-by: OpenAI Codex
