Bug 27109 - Simplify "a - 10 > 150" into "a > 160" when range of a is known (in VRP or somewhere else)
Summary: Simplify "a - 10 > 150" into "a > 160" when range of a is known (in VRP or so...
Status: ASSIGNED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.2.0
: P3 enhancement
Target Milestone: ---
Assignee: Andrew Pinski
URL:
Keywords: missed-optimization
: 101815 (view as bug list)
Depends on:
Blocks: VRP
  Show dependency treegraph
 
Reported: 2006-04-11 02:04 UTC by Andrew Pinski
Modified: 2023-08-10 02:38 UTC (History)
5 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2021-06-02 00:00:00


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Pinski 2006-04-11 02:04:17 UTC
Kinda like PR 14490 but for the -fwrapv and unsigned cases:

void bar (void);

void
foo (unsigned a)
{
  if (a < 100)
    return;
  if (200 < a)
    return;

  if (a - 10 > 150)
    bar ();
}
Comment 1 Richard Biener 2006-12-28 12:03:15 UTC
Confirmed.  compare_values needs to be teached to look at value ranges for operands and decide on overflow there - but only for substitute and fold as
earlier we can have invalid intermediate value ranges.
Comment 2 Marc Glisse 2012-12-04 18:48:27 UTC
This seems to be well handled in reassoc1 now:

Optimizing range tests a_2(D) -[0, 99] and +[0, 200] and -[10, 160]
 into a_2(D) + 4294967135 <= 39
Comment 3 Andrew Pinski 2021-06-03 03:27:40 UTC
Here is a better testcase:
void bar(void);
void goo(void);
void
foo (unsigned a)
{
  if (a < 100)
    return;
  goo();
  if (200 < a)
    return;

  if (a - 10 > 150)
    bar ();
}


Note the original testcase is optimized correctly in reassoc1 but that was not the point of it.
Anyways we have:
  # RANGE [90, 190] NONZERO 255
  _1 = a_3(D) + 4294967286;
  if (_1 > 150)

4294967286 is -10
Comment 4 Andrew Macleod 2021-06-03 13:25:45 UTC
well, in evrp we now produce:
=========== BB 6 ============
Imports: a_3(D)
Exports: _1  a_3(D)
         _1 : a_3(D)(I)
a_3(D)  unsigned int [100, 200]
    <bb 6> :
    _1 = a_3(D) + 4294967286;
    if (_1 > 150)
      goto <bb 7>; [INV]
    else
      goto <bb 8>; [INV]

_1 : unsigned int [90, 190]
6->7  (T) _1 :  unsigned int [151, 190]
6->7  (T) a_3(D) :      unsigned int [161, 200]
6->8  (F) _1 :  unsigned int [90, 150]
6->8  (F) a_3(D) :      unsigned int [100, 160]

we know its not going to overflow.  who or what should make the decision? looks like some sort of simplification or peephole.  

Also note that you can now find this out from any pass with the range_query infrastructure that Aldy added:

at the start of the pass call enable_ranger() for context sensitive info, and then anywhere you can 

get_range_query()->range_of_expr (r, stmt, name)  will get a range.
so for the initial stmt
1 = a_3(D) + 4294967286;
asking for the range of a_3 on this stmt would give you [100,200] or asking for the range of the stmt (or i_1 in the next statetment) will give you [90,190]

Aldy has also implemented an overflow checker for expressions.. not sure it applies to stmts.. yet.  If any of this interests you, send him a note.
We're still working out user case functionality, so if there is anything else we need to present this kind of info, let us know.

I think he's planning to write a guide for this next week.

Another option is to work it backwards. given the stmt:
  # RANGE [90, 190] NONZERO 255
  _1 = a_3(D) + 4294967286;
range-ops can tell you that if _1 is [90,190] then it can evaluate the expression and solve that a_3 is [100,200]..   if that helps.  internally it knows if there was a potential overflow, but that isnt exported in any useful way way at the moment.
Comment 5 Andrew Pinski 2021-08-07 22:38:26 UTC
*** Bug 101815 has been marked as a duplicate of this bug. ***
Comment 6 Andrew Pinski 2021-08-07 22:39:48 UTC
Another testcase which shows up via the autovectorizer aliasing checks

int g(unsigned int a)
{
  if (a == 0) __builtin_unreachable();
  unsigned int t = a;
  a += -1;
  return a > 3u;
}
Comment 7 Andrew Pinski 2023-08-09 21:51:45 UTC
I suspect we could add it to simplify_compare_using_ranges_1 very easy.
Let me look into that.