On Fri, 2025-07-04 at 10:26 -0700, Eduard Zingerman wrote:
> On Fri, 2025-07-04 at 19:14 +0200, Paul Chaignon wrote:
> > On Thu, Jul 03, 2025 at 11:54:27AM -0700, Eduard Zingerman wrote:
[...]
> > > I think is_branch_taken() modification should not be too complicated.
> > > For JSET it only checks tnum, but does not take ranges into account.
> > > Reasoning about ranges is something along the lines:
> > > - for unsigned range a = b & CONST -> a is in [b_min & CONST, b_max & CONST];
> > > - for signed ranged same thing, but consider two unsigned sub-ranges;
> > > - for non CONST cases, I think same reasoning can apply, but more
> > > min/max combinations need to be explored.
> > > - then check if zero is a member or 'a' range.
> > >
> > > Wdyt?
> >
> > I might be missing something, but I'm not sure that works. For the
> > unsigned range, if we have b & 0x2 with b in [2; 10], then we'd end up
> > with a in [2; 2] and would conclude that the jump is never taken. But
> > b=8 proves us wrong.
>
> I see, what is really needed is an 'or' joined mask of all 'b' values.
> I need to think how that can be obtained (or approximated).
I think the mask can be computed as in or_range() function at the
bottom of the email. This gives the following algorithm, if only
unsigned range is considered:
- assume prediction is needed for "if a & b goto ..."
- bits that may be set in 'a' are or_range(a_min, a_max)
- bits that may be set in 'b' are or_range(b_min, b_max)
- if computed bit masks intersect: both branches are possible
- otherwise only false branch is possible.
Wdyt?
[...]
---
#include <stdint.h>
#include <stdio.h>
static uint64_t or_range(uint64_t lo, uint64_t hi)
{
uint64_t m;
uint32_t i;
m = hi;
i = 0;
while (lo != hi) {
m |= 1lu << i;
lo >>= 1;
hi >>= 1;
i++;
}
return m;
}
static uint64_t or_range_simple(uint64_t lo, uint64_t hi)
{
uint64_t m = 0;
uint64_t v = 0;
for (v = lo; v <= hi; v++)
m |= v;
return m;
}
int main(int argc, char *argv[])
{
int max = 0x1000;
for (int lo = 0; lo < max; lo++) {
for (int hi = lo; hi < max; hi++) {
uint64_t expected = or_range_simple(lo, hi);
uint64_t result = or_range(lo, hi);
if (expected != result) {
printf("mismatch: %x..%x -> expecting %lx, result %lx\n",
lo, hi, expected, result);
return 1;
}
}
}
printf("all ok\n");
return 0;
}
