[Bug tree-optimization/44711] New: PRE doesn't remove equivalent computations of induction variables

[irar at il dot ibm dot com]

For the following loop 

  for (i = 0; i < N; i++)
    if (arr[i] < limit)
      {
        pos = i + 1;
        limit = arr[i];
      }

PRE fails to eliminate redundant i_24 + 1 computation. 

Here is Richard's analysis from
http://gcc.gnu.org/ml/gcc-patches/2010-06/msg02982.html:

So the reason is our heuristic in PRE to not introduce new IVs:

Found partial redundancy for expression {plus_expr,i_24,1} (0005)
Skipping insertion of phi for partial redundancy: Looks like an
induction variable
Inserted pretmp.4_2 = i_13 + 1;
 in predecessor 8
Found partial redundancy for expression {plus_expr,i_24,1} (0005)
Inserted pretmp.4_22 = i_24 + 1;
 in predecessor 7
Created phi prephitmp.5_21 = PHI <pretmp.4_22(7), pos_11(4)>
 in block 5
Found partial redundancy for expression {plus_expr,i_24,1} (0005)
Skipping insertion of phi for partial redundancy: Looks like an
induction variable
Replaced i_24 + 1 with prephitmp.5_21 in i_13 = i_24 + 1;
Removing unnecessary insertion:pretmp.4_2 = i_13 + 1;

we do not want to insert into block 3, so we are left with

<bb 3>:
  # pos_23 = PHI <pos_1(8), 1(2)>
  # i_24 = PHI <i_13(8), 0(2)>
  # limit_25 = PHI <limit_4(8), 1.28e+2(2)>
  limit_9 = arr[i_24];
  D.3841_10 = limit_9 < limit_25;
  if (D.3841_10 != 0)
    goto <bb 4>;
  else
    goto <bb 7>;

<bb 7>:
  pretmp.4_22 = i_24 + 1;
  goto <bb 5>;

<bb 4>:
  pos_11 = i_24 + 1;

<bb 5>:
  # pos_1 = PHI <pos_23(7), pos_11(4)>
  # limit_4 = PHI <limit_25(7), limit_9(4)>
  # prephitmp.5_21 = PHI <pretmp.4_22(7), pos_11(4)>
  i_13 = prephitmp.5_21;

where there is no full redundancy for i_24 + 1 now (that is,
we did some useless half-way PRE because of that IV
heuristic ...).


-- 
           Summary: PRE doesn't remove equivalent computations of induction
                    variables
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: irar at il dot ibm dot com


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=44711