[Bug tree-optimization/29333] New: Generation of MAX_EXPRs and MIN_EXPRs missed by phiopt

[Bug tree-optimization/29333] New: Generation of MAX_EXPRs and MIN_EXPRs missed by phiopt

[roberto dot costa at st dot com]

There are cases in which phiopt doesn't recognize MAX_EXPRs or MIN_EXPRs
patterns.
In particular, source codes that look very similar at first sight may induce
phiopt to behave differently.

Let's consider the following two functions:

-----------------------------
int minmax_correct(int a)
{
        if (a > 32767) a = 32767;
        else if (a < -32768) a = -32768;

        return a;
}

int minmax_wrong(int a)
{
        if (a > 32767) a = 32767;
        if (a < -32768) a = -32768;

        return a;
}
-----------------------------

MIN_EXPRs and MAX_EXPRs are generated for the first function, but not for the
second.

Here is the contents of trace file minmax.c.042t.phicprop1:

-----------------------------
;; Function minmax_correct (minmax_correct)

minmax_correct (a)
{
<bb 2>:
  if (a_2 > 32767) goto <L3>; else goto <L1>;

<L1>:;
  if (a_2 < -32768) goto <L2>; else goto <L3>;

<L2>:;

  # a_1 = PHI <32767(2), a_2(3), -32768(4)>;
<L3>:;
  <retval> = a_1;
  return <retval>;

}

;; Function minmax_wrong (minmax_wrong)

Removing basic block 6
minmax_wrong (a)
{
<bb 2>:
  if (a_3 > 32767) goto <L6>; else goto <L1>;

<L1>:;
  if (a_3 < -32768) goto <L3>; else goto <L6>;

  # a_9 = PHI <a_3(3), 32767(2)>;
<L6>:;

  # a_2 = PHI <a_9(4), -32768(3)>;
<L3>:;
  <retval> = a_2;
  return <retval>;

}
-----------------------------

And here is minmax.c.043t.phiopt1:

-----------------------------
;; Function minmax_correct (minmax_correct)

Removing basic block 4
Removing basic block 3
Merging blocks 2 and 5
minmax_correct (a)
{
<bb 2>:
  a_7 = MAX_EXPR <-32768, a_2>;
  a_8 = MIN_EXPR <a_7, 32767>;
  <retval> = a_8;
  return <retval>;

}

;; Function minmax_wrong (minmax_wrong)

minmax_wrong (a)
{
<bb 2>:
  if (a_3 > 32767) goto <L6>; else goto <L1>;

<L1>:;
  if (a_3 < -32768) goto <L3>; else goto <L6>;

  # a_9 = PHI <a_3(3), 32767(2)>;
<L6>:;

  # a_2 = PHI <a_9(4), -32768(3)>;
<L3>:;
  <retval> = a_2;
  return <retval>;

}
-----------------------------


-- 
           Summary: Generation of MAX_EXPRs and MIN_EXPRs missed by phiopt
           Product: gcc
           Version: 4.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: roberto dot costa at st dot com


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

[Bug tree-optimization/29333] Generation of MAX_EXPRs and MIN_EXPRs missed by phiopt

[roberto dot costa at st dot com]

------- Comment #1 from roberto dot costa at st dot com  2006-10-03 16:05 -------
Created an attachment (id=12378)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=12378&action=view)
Source code of the example


-- 


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

[Bug tree-optimization/29333] Generation of MAX_EXPRs and MIN_EXPRs missed by phiopt

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
           Keywords|                            |missed-optimization


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

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2006-10-03 16:11 -------
Actually this is a case where jump threading gets in the way of PHI-OPT. 
Really PHI-OPT should be put before VRP and DOM, I don't know why it was not.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2006-10-03 16:11:22
               date|                            |
            Summary|Generation of MAX_EXPRs and |Jump threading getting in
                   |MIN_EXPRs missed by phiopt  |the way of PHI-OPT


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

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[roberto dot costa at st dot com]

------- Comment #3 from roberto dot costa at st dot com  2006-10-05 08:15 -------
I tested what happens if the first PHI-OPT pass is moved right before the first
VRP pass in gcc/passes.c

It looks like PHI-OPT should be run both before and after VRP and DOM.
The example reported shows that, when PHI-OPT is run after VRP and DOM, it
misses some MAX_EXPR and MIN_EXPR generation.
gcc/testsuite/gcc.dg/tree-ssa/phi-opt-5.c shows that, when PHI-OPT anticipates
VRP and DOM, it misses some MAX_EXPR and MIN_EXPR generation as well.

Should an additional PHI-OPT pass be added before VRP and DOM?
(In this case, a few testsuite examples should also be changed in order to
consider what happens after PHI-OPT2 instead of PHI-OPT1)


-- 


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

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|gcc-bugs at gcc dot gnu.org |
         AssignedTo|unassigned at gcc dot       |pinskia at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-01-21 07:28:41 UTC ---
If we do a merge_phi before the phiopt we will find it correctly.
I have a few patches which adds another merge_phi right before the last phiopt
and adds one right before the first phiopt.

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-01-22 00:47:00 UTC ---
This is the patch which I am testing:
Index: gcc/passes.c
===================================================================
--- gcc/passes.c    (revision 183381)
+++ gcc/passes.c    (working copy)
@@ -1300,11 +1300,11 @@ init_optimization_passes (void)
       NEXT_PASS (pass_phiprop);
       NEXT_PASS (pass_fre);
       NEXT_PASS (pass_copy_prop);
-      NEXT_PASS (pass_merge_phi);
       NEXT_PASS (pass_vrp);
       NEXT_PASS (pass_dce);
       NEXT_PASS (pass_cselim);
       NEXT_PASS (pass_tree_ifcombine);
+      NEXT_PASS (pass_merge_phi);
       NEXT_PASS (pass_phiopt);
       NEXT_PASS (pass_tail_recursion);
       NEXT_PASS (pass_ch);
@@ -1401,6 +1401,7 @@ init_optimization_passes (void)
       NEXT_PASS (pass_late_warn_uninitialized);
       NEXT_PASS (pass_dse);
       NEXT_PASS (pass_forwprop);
+      NEXT_PASS (pass_merge_phi);
       NEXT_PASS (pass_phiopt);
       NEXT_PASS (pass_fold_builtins);
       NEXT_PASS (pass_optimize_widening_mul);

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-01-22 22:24:43 UTC ---
(In reply to comment #5)
> This is the patch which I am testing:

I Have a slightly different one since we should do a few more things before the
mergephi and also we ccannot remove the first mergephi as that causes vpr to
lose some optimizations.

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-01-23 10:25:20 UTC ---
(In reply to comment #6)
> (In reply to comment #5)
> > This is the patch which I am testing:
> 
> I Have a slightly different one since we should do a few more things before the
> mergephi and also we ccannot remove the first mergephi as that causes vpr to
> lose some optimizations.

I think it makes sense to do mergephi before phiopt.  mergephi should not
be required for VRP - can you file a bug with a testcase?

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED
   Target Milestone|---                         |9.0

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This actually has been fixed fully since r9-3606.

[Bug tree-optimization/29333] Jump threading getting in the way of PHI-OPT

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to rsandifo@gcc.gnu.org from comment #8)
> This may be worth filing as another PR (let me know if you
> think I should), but another case of VRP stymieing phiopt is:
> 
> void bar (int);
> void
> foo (int a, int b)
> {
>   if (!b)
>     bar (1);
>   else
>     {
>       int c;
>       if (a)
>         c = a;
>       else
>         c = 0;
>       if (c == b)
>         bar (2);
>     }
> }

This was testcase was fixed on trunk by a combo of patches to tree-ssa-phiopt.c
and match.pd (r12-2041, r12-2040, r12-2039, and r12-1152 [there might have been
a few more required which I missed]) which allows early phiopt to change if (a)
c = a else c = 0; to just c = a.