[Bug tree-optimization/21559] New: [4.1 Regression] missed jump threading

[Bug tree-optimization/21559] New: [4.1 Regression] missed jump threading

[pinskia at gcc dot gnu dot org]

The following code should have no check for bytes == 0 but does on the mainline:
static int blocksize = 4096;

int bar (int);

void foo (void)
{
  int toread;
  int bytes;
  static char eof_reached = 0;

  toread = blocksize;
  bytes = 1;

  while (toread != 0)
    {
      bytes = bar (toread);
      if (bytes <= 0)
        {
          if (bytes < 0)
            continue;
          break;
        }
      toread -= bytes;
    }

  if (bytes == 0)
    eof_reached = 1;
}

This started to happen before 20050420 so it was ___not___ the jump threading changes.

-- 
           Summary: [4.1 Regression] missed jump threading
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.1.0


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[steven at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-05-16 00:07:25
               date|                            |


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-07-27 17:13 -------
It's highly unlikely threading is going to be able to completely eliminate the
test for bytes == 0.

The fundamental problem is the threader has no way of knowing that the loop exit
test (toread != 0) can never be true if bytes == 0.

Now there is a missed threading opportunity in this code, when bytes <= 0, but
! (bytes < 0) we exit the loop via a break statement.  Clearly when we exit the
loop via that break statement, we need not test bytes == 0 again outside the loop.

It's also the case that the test bytes < 0 can and should be simplified into
bytes != 0.   In fact, if VRP is enhanced to perform that simplification, then
we do thread the loop exit via the break statement.

jeff





-- 


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[law at redhat dot com]

------- Additional Comments From law at redhat dot com  2005-07-28 22:00 -------
The attached patch is a piece of what will be necessary to fully optimize this
testcase in the future.

The first step is getting VRP to discover that all the paths to the bytes == 0
test have a range of either [0, 0] or ~[0, 0].  Two changes are necessary to
make that happen.

   a. When we're searching for uses of a conditional's operand, we currently
      ignore any uses in blocks that have been visited.  That causes us to miss
      uses, particularly those in PHI nodes at dominance frontiers.  With that
      fixed, we get some additional ASSERT_EXPRs on the paths out of the loop
      to the bytes == 0 test.  The first hunk in the patch takes care of this
      issue.

   b. When evaluating a PHI, we have some checks to avoid expanding ranges
      over and over and over again as we gain more information at PHI nodes.

      This is fine and good, except that it's too aggressive.  Consider if
      we are meeting two ranges [ , -1] and [1, ].  vrp_meet will correctly
      give us ~ [0, 0], but the code in vrp_visit_phi_node will try to expand
      the [ , -1] range rather than use the anti-range returned by vrp_meet.
      This results in getting a VARYING range rather than ~[0, 0].  THe second
      hunk in the attached patch fixes that little goof.

Once VRP computes all the necessary information, it's just a matter of using
that information to perform the optimization we want.  I haven't decided what
the best approach would be.   It's really a jump threading optimization.

  a. Jump threading in tree-vrp.  This may not be as sick as it sounds.  The
     idea would be that much of the jump threading code would become a common
     routine used by tree-vrp and DOM.    That would probably mean the remaining
     VRP bits in DOM would disappear since tree-vrp would perform any threading
     based on VRP.

  b. Make range information persistent so that DOM could use the VRP information
     computed by tree-vrp.

Anyway, this is definitely not stuff we want to try to squeeze into 4.1.  So I'm
going to attach my work-to-date so that nobody has to recreate it when we open
up stage1 for GCC 4.2.



-- 


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |minor


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[phython at gcc dot gnu dot org]

------- Additional Comments From phython at gcc dot gnu dot org  2005-07-31 05:45 -------
 I would really prefer option b, where we keep VRP information persistant.  That
way fold can use VRP information when available.

-- 


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P2                          |P5
   Target Milestone|4.2.0                       |4.1.0


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2005-10-29 18:09 -------
Another one of these I filed this bug after looking at someone else's bug for
code gen regressions.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.1.0                       |4.2.0


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

[Bug tree-optimization/21559] [4.1 Regression] missed jump threading

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2005-10-27 00:12 -------
I should note that this is a true code gen regression and not just a missed one
at the tree level.


-- 


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