[Bug tree-optimization/15911] New: DOM optimization not performed

[Bug tree-optimization/15911] New: DOM optimization not performed

[dann at godzilla dot ics dot uci dot edu]

On x86_64-unknown-linux-gnu (RHEL3)
using 
gcc version 3.2.3 20030502 (Red Hat Linux 3.2.3-24)
as the bootstrap compiler

The following code does not get optimized: 
(the link_error calls should all be removed)

extern int link_error (int);

int tst2 (int x, int y)
{
  if ((x > 5555) && (y < 6666))
    {
      if (x > 5555)
        if (y < 6666)
          return 1111;
        else
          return link_error (2222);
      else
        if (y < 6666)
          return link_error (3333);
        else
          return link_error (4444);
    }
  else
    return 0;
}

The .t53.vars dump is:

;; Function tst2 (tst2)

tst2 (x, y)
{
  int T.67;
  _Bool T.65;
  _Bool T.64;

<bb 0>:
  T.64 = x > 5555;
  T.65 = y <= 6665;
  if (T.64 && T.65) goto <L0>; else goto <L11>;

<L11>:;
  T.67 = 0;
  goto <bb 7> (<L8>);

<L0>:;
  if (T.64) goto <L1>; else goto <L4>;

<L1>:;
  if (T.65) goto <L12>; else goto <L3>;

<L12>:;
  T.67 = 1111;
  goto <bb 7> (<L8>);

<L3>:;
  T.67 = link_error (2222) [tail call];
  goto <bb 7> (<L8>);

<L4>:;
  if (T.65) goto <L5>; else goto <L6>;

<L5>:;
  T.67 = link_error (3333) [tail call];
  goto <bb 7> (<L8>);

<L6>:;
  T.67 = link_error (4444) [tail call];

<L8>:;
  return T.67;

}

The code is optimized just fine when compiled on i686-linux!
(the dom1 pass removes the link_error calls)
Like so:

;; Function tst2 (tst2)

tst2 (x, y)
{
  int T.49;

<bb 0>:
  if (x <= 5555) goto <L13>; else goto <L0>;

<L13>:;
  T.49 = 0;
  goto <bb 3> (<L9>);

<L0>:;
  if (y > 6665) goto <L8>; else goto <L14>;

<L14>:;
  T.49 = 1111;
  goto <bb 3> (<L9>);

<L8>:;
  T.49 = 0;

<L9>:;
  return T.49;

}

The problems starts with the stage1 compiler (even stage1 is compiled with gcc
-O0). 
The bootstrap succeeds, and the test results are very similar to other results
posted to gcc-testresults. 
This has been around for a while at least 1 month.
I don't have access to another 64-bit platform right now to check if this has
something to do with 64-bit systems.

-- 
           Summary: DOM optimization not performed
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dann at godzilla dot ics dot uci dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/15911] DOM optimization not performed

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2004-06-10 17:58 -------
This also happens on ia64. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2004-06-10 17:58:34
               date|                            |


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-10 18:50 -------
This is just like PR 13965.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |13965, 15357
           Severity|normal                      |enhancement
           Keywords|                            |missed-optimization


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

[Bug tree-optimization/15911] DOM optimization not performed

[dann at godzilla dot ics dot uci dot edu]

------- Additional Comments From dann at godzilla dot ics dot uci dot edu  2004-06-10 22:24 -------
Hmmm, adding -march=athlon shows the same problem on i386. 
The problem does not occur 0f -march=i386 is used. 

The difference between the 2 cases above appears in the .t03.original dump:

For i386 the first "if" is translated to:
   if (x > 5555 && y <= 6665)  
the "&&" corresponds to a tree_andif_expr tree
for -march=athlon it is translated to:
   if (#`truth_and_expr' not supported by pp_c_expression#)
here a truth_and_expr tree is used. 

For i386 the && is transformed in cascading ifs, and DOM knows how to deal with
that. 
For athlon the truth_and_expr is transformed to:

  T.0 = x > 5555;
  T.1 = y <= 6665;
  T.2 = T.0 && T.1;
  if (T.2) ....

In this case DOM does not infere that if T.2 is true then T.0 and T.1 are also
true. 

The question is, should "&&" be lowered to different trees depending on the
target architecture? 




-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|enhancement                 |normal


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-06-10 22:27 -------
Yes we know that this is a problem which is caused by BRANCH_COST, I had a start on a new pass 
which makes the stuff done for BRANCH_COST later and not in fold but my HD died.  I will see if I do 
the pass over the next couple of weeks.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pinskia at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-09-09 03:53 -------
*** Bug 13965 has been marked as a duplicate of this bug. ***

-- 
Bug 15911 depends on bug 13965, which changed state.

Bug 13965 Summary: [tree-ssa] fold takes into account branch target information at tree level
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13965

           What    |Old Value                   |New Value
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |DUPLICATE

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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-05-08 19:18 -------
I am no longer working on this.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|pinskia at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug tree-optimization/15911] DOM optimization not performed

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-04 21:41 -------
*** Bug 20065 has been marked as a duplicate of this bug. ***

-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-04 21:41 -------
VRP does not work on this either.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dnovillo at gcc dot gnu dot
                   |                            |org
            Summary|DOM optimization not        |VRP/DOM does not like
                   |performed                   |TRUTH_AND_EXPR


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-09-08 18:20 -------

This would be fixable inside VRP.  Essentially we would need to insert chains of
ASSERT_EXPRs to represent various predicates:

  D.1613_3 = x_2 > 5555;
  D.1614_5 = y_4 <= 6665;
  D.1615_6 = D.1613_3 && D.1614_5;
  if (D.1615_6) goto <L0>; else goto <L8>;

At label L0, we know that:

  D.1615_10 = 1;
  D.1613_11 = 1;
  D.1614_12 = 1;
  y_13 = ASSERT_EXPR <y_4, y_4 <= 6665>;
  x_14 = ASSERT_EXPR <x_2, x_2 > 5555>;

which is a bit sickening.  It would be Much Better to avoid creating these
obtuse predicates in fold(), though.

Roger, Jeff, is there some hope for fixing this in fold() for 4.2?  If not, I
can work on VRP to try an understand these chains.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sayle at gcc dot gnu dot org
   Target Milestone|---                         |4.2.0


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-09-08 19:04 -------
Subject: Re:  VRP/DOM does not like
	TRUTH_AND_EXPR

On Thu, 2005-09-08 at 18:20 +0000, dnovillo at gcc dot gnu dot org
wrote:
> ------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-09-08 18:20 -------
> 
> This would be fixable inside VRP.  Essentially we would need to insert chains of
> ASSERT_EXPRs to represent various predicates:
> 
>   D.1613_3 = x_2 > 5555;
>   D.1614_5 = y_4 <= 6665;
>   D.1615_6 = D.1613_3 && D.1614_5;
>   if (D.1615_6) goto <L0>; else goto <L8>;
> 
> At label L0, we know that:
> 
>   D.1615_10 = 1;
>   D.1613_11 = 1;
>   D.1614_12 = 1;
>   y_13 = ASSERT_EXPR <y_4, y_4 <= 6665>;
>   x_14 = ASSERT_EXPR <x_2, x_2 > 5555>;
> 
> which is a bit sickening.  It would be Much Better to avoid creating these
> obtuse predicates in fold(), though.
Well, we have a long standing problem with fold using BRANCH_COST to
determine how best to implement certain conditionals.  But even if that
were removed, it's fairly straightforward for a programmer (or better
yet some automated code generator) to create these "obtuse" predicates.

I think we'd be better off teaching VRP how to cope with this.


Jeff



-- 


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

[Bug tree-optimization/15911] VRP/DOM does not like TRUTH_AND_EXPR

[dnovillo at gcc dot gnu dot org]

------- Additional Comments From dnovillo at gcc dot gnu dot org  2005-09-08 19:07 -------
(In reply to comment #10)

> it's fairly straightforward for a programmer (or better
> yet some automated code generator) to create these "obtuse" predicates.
> 
Good point.  I'll work on a fix.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |dnovillo at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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