[Bug tree-optimization/96351] New: missed opportunity to optimize out redundant loop

[Bug tree-optimization/96351] New: missed opportunity to optimize out redundant loop

[felix.yang at huawei dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96351

            Bug ID: 96351
           Summary: missed opportunity to optimize out redundant loop
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: felix.yang at huawei dot com
  Target Milestone: ---

inline unsigned int
stringLen(const short* const src)
{
    if (src == 0 || *src == 0) {
        return 0;
    } else {
        const short* pszTmp = src + 1;

        while (*pszTmp)
            ++pszTmp;

        return (unsigned int)(pszTmp - src);
    }
}

extern void bar();

void foo(const short* const str) {
    unsigned int len = stringLen(str);
    if (!len) {
        bar();
    }
}

When stringLen is inlined into foo, the else block in stringLen can be
simplified into non-zero, thus eliminating the while loop. This looks like a
tree VRP issue, but this pass does not work as expected for this test case.

$ g++ -S -O2 foo.cpp -fdump-tree-vrp

Consider function foo, value ranges after VRP does not help here:
 48
 49 .MEM_1: <<< error >>> VARYING
 50 str_3(D): const short int * const VARYING
 51 _6: short int VARYING
 52 str_7: const short int * const [1B, +INF]  EQUIVALENCES: { str_3(D) } (1
elements)
 53 pszTmp_8: const short int * [1B, +INF]  EQUIVALENCES: { pszTmp_10 } (1
elements)
 54 pszTmp_9: const short int * const [1B, +INF]
 55 pszTmp_10: const short int * const [1B, +INF]
 56 _11: short int VARYING
 57 pszTmp_12: const short int * [1B, +INF]
 58 _13: unsigned int [0, 0]
 59 _14: long int VARYING
 60 _15: long int [-4611686018427387904, 4611686018427387903]
 61 _16: unsigned int VARYING
 62 _18: unsigned int [0, 0]
 63 pszTmp_19: const short int * [1B, +INF]  EQUIVALENCES: { pszTmp_10 } (1
elements)

 ......

 93   <bb 4> [local count: 439750964]:
 94   pszTmp_9 = str_3(D) + 2;
 95
 96   <bb 5> [local count: 3997736055]:
 97   # pszTmp_10 = PHI <pszTmp_9(4), pszTmp_12(6)>
 98   _11 = *pszTmp_10;
 99   if (_11 == 0)
100     goto <bb 7>; [11.00%]
101   else
102     goto <bb 6>; [89.00%]
103
104   <bb 6> [local count: 3557985095]:
105   pszTmp_12 = pszTmp_10 + 2;
106   goto <bb 5>; [100.00%]
107
108   <bb 7> [local count: 439750964]:
109   # pszTmp_8 = PHI <pszTmp_10(5)>
110   _14 = pszTmp_8 - str_3(D);
111   _15 = _14 /[ex] 2;
112   _16 = (unsigned int) _15;
113   if (_16 == 0)
114     goto <bb 8>; [3.91%]
115   else
116     goto <bb 9>; [96.09%]
117
118   <bb 8> [local count: 354334798]:
119   bar ();
120
121   <bb 9> [local count: 1073741824]:
122   return;

Any suggestions to proceed?

[Bug tree-optimization/96351] missed opportunity to optimize out redundant loop

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96351

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2020-07-28

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
VRP doesn't work "backwards", it also does an incredibly bad job at
tracking pointer ranges where it simply prefers to track non-NULL.
Here we'd need to track symbolic [str_7 + [2, +INF] ] or so which
it cannot do either.

Eventually other analyses (SCEV?) could derive sth for

  # pszTmp_8 = PHI <pszTmp_19(8)>
  _14 = pszTmp_8 - str_7;
  _15 = _14 /[ex] 2;

but even there, since we do not know the number of iterations, the
representation will have its limits.

[Bug tree-optimization/96351] missed opportunity to optimize out redundant loop

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96351

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
I had to do some tweaking and manually inline it, but eventually I managed to
get:

 <bb 4> :
  pszTmp_11 = str_8(D) + 2;
  goto <bb 6>; [INV]

  <bb 5> :
  pszTmp_13 = pszTmp_5 + 2;

  <bb 6> :
  # pszTmp_5 = PHI <pszTmp_11(4), pszTmp_13(5)>
  _1 = *pszTmp_5;
  if (_1 != 0)
    goto <bb 5>; [INV]
  else
    goto <bb 7>; [INV]

  <bb 7> :
  # pszTmp_16 = PHI <pszTmp_5(6)>
  _2 = pszTmp_16 - str_8(D);
  _3 = _2 /[ex] 2;
  len_12 = (unsigned int) _3;

<bb 8> :
  # len_4 = PHI <0(2), len_12(7), 0(3)>
  if (len_4 == 0)
    goto <bb 9>; [INV]
  else
    goto <bb 10>; [INV]


Nothing we can do right now.  Its possible that the relational work in the next
release *might* be able to sort something out, but thats probably down the
road.

We'll be able to record that
a) pszTmp_11 > str_8(D)
b) pszTmp_13 > pszTmp_5
c) when we see 
# pszTmp_5 = PHI <pszTmp_11(4), pszTmp_13(5)>
we might possibly be able to deduce that 
d) pszTmp_5 > str_8(D),  which then leads to
e) pszTmp_16 > str_8(D).

which means we could know that _2 > 0.

The tricky bit will be knowing that not only is _2 > 0, but its actually [2,
+INF].  Initial plans for relations are not to track possible offsets, but it
could be follow up work.

If we can know that, then we'd be able to calculate len_12 = [1, +INF/2].

With a non-zero range for len_12, then it would be possible for the threader to
create 2 execution paths.. the zero and the non-zero path.

on the non-zero path , there would no longer need to be a reference to len_12,
and dead code could conceivably eliminate the enter else block.

I'd keep this around as a reference, but I don't see this happening any time
soon. If the threaders get a revamp next year... then maybe!