path solver: Avoid recalculating ranges already in the cache.
authorAldy Hernandez <aldyh@redhat.com>
Mon, 8 Nov 2021 11:13:33 +0000 (12:13 +0100)
committerAldy Hernandez <aldyh@redhat.com>
Mon, 8 Nov 2021 15:08:09 +0000 (16:08 +0100)
commit18546941ae4c56cd9240d2dc2ca2806e01eb6fb7
treea9ec988e8935f31a537c1fbf194dc0d36fe73067
parenta354b4255b679de45bd3d4d8874a26c89f6c74fc
path solver: Avoid recalculating ranges already in the cache.

The problem here is an ordering issue with a path that starts
with 19->3:

 <bb 3> [local count: 916928331]:
  # value_20 = PHI <value_17(19), value_7(D)(17)>
  # n_27 = PHI <n_16(19), 1(17)>
  n_16 = n_27 + 4;
  value_17 = value_20 / 10000;
  if (value_20 > 42949672959999)
    goto <bb 19>; [89.00%]
  else
    goto <bb 4>; [11.00%]

The problem here is that both value_17 and value_20 are in the set of
imports we must pre-calculate.  The value_17 name occurs first in the
bitmap, so we try to resolve it first, which causes us to recursively
solve the value_20 range.  We do so correctly and put them both in the
cache.  However, when we try to solve value_20 from the bitmap, we
ignore that it already has a cached entry and try to resolve the PHI
with the wrong value of value_17:

  # value_20 = PHI <value_17(19), value_7(D)(17)>

The right thing to do is to avoid recalculating definitions already
solved.

Regstrapped and checked for # threads before and after on x86-64 Linux.

gcc/ChangeLog:

PR tree-optimization/103120
* gimple-range-path.cc (path_range_query::range_defined_in_block):
Bail if there's a cache entry.

gcc/testsuite/ChangeLog:

* gcc.dg/pr103120.c: New test.
gcc/gimple-range-path.cc
gcc/testsuite/gcc.dg/pr103120.c [new file with mode: 0644]