User account creation filtered due to spam.

Bug 21559 - [4.2/4.3 Regression] missed jump threading
Summary: [4.2/4.3 Regression] missed jump threading
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.0.0
: P5 minor
Target Milestone: 4.4.0
Assignee: Not yet assigned to anyone
Keywords: missed-optimization
Depends on:
Blocks: 19794 21548 23111
  Show dependency treegraph
Reported: 2005-05-13 22:42 UTC by Andrew Pinski
Modified: 2008-11-22 15:47 UTC (History)
1 user (show)

See Also:
Known to work: 4.4.0
Known to fail: 4.3.2 4.2.4
Last reconfirmed: 2007-03-29 13:09:31

Patch to address data gathering and propagation in VRP (1.21 KB, patch)
2005-07-28 21:59 UTC, Jeffrey A. Law
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Pinski 2005-05-13 22:42:25 UTC
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)
      toread -= bytes;

  if (bytes == 0)
    eof_reached = 1;

This started to happen before 20050420 so it was ___not___ the jump threading changes.
Comment 1 Jeffrey A. Law 2005-07-27 17:13:11 UTC
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.


Comment 2 Jeffrey A. Law 2005-07-28 21:59:03 UTC
Created attachment 9383 [details]
Patch to address data gathering and propagation in VRP
Comment 3 Jeffrey A. Law 2005-07-28 22:00:59 UTC
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

   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.

Comment 4 James A. Morrison 2005-07-31 05:45:38 UTC
 I would really prefer option b, where we keep VRP information persistant.  That
way fold can use VRP information when available.
Comment 5 Andrew Pinski 2005-10-27 00:12:13 UTC
I should note that this is a true code gen regression and not just a missed one at the tree level.
Comment 6 Andrew Pinski 2005-10-29 18:09:01 UTC
Another one of these I filed this bug after looking at someone else's bug for code gen regressions.
Comment 7 Jeffrey A. Law 2006-02-07 20:03:42 UTC
With today's changes we thread the "break" edge out of the loop.  We could still do better.

Basically we need to realize that bytes can never have the value zero when we hit the loop test "while (toread != 0)".  Once we realize that, then we'd know that the test (if bytes == 0) has a known result on all paths reaching the conditional.
Comment 8 Mark Mitchell 2006-05-25 02:36:04 UTC
Will not be fixed in 4.1.1; adjust target milestone to 4.1.2.
Comment 9 Joseph S. Myers 2008-07-04 16:53:04 UTC
Closing 4.1 branch.
Comment 10 Steven Bosscher 2008-11-22 11:36:30 UTC
Trunk today generates the following code (this is the final_cleanup dump):

;; Function foo (foo)

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

<bb 2>:
  toread = 4096;

<bb 3>:
  bytes = bar (toread);
  if (bytes <= 0)
    goto <bb 4>;
    goto <bb 5>;

<bb 4>:
  if (bytes != 0)
    goto <bb 6>;
    goto <bb 7>;

<bb 5>:
  toread = toread - bytes;

<bb 6>:
  if (toread != 0)
    goto <bb 3>;
    goto <bb 8>;

<bb 7>:
  eof_reached = 1;

<bb 8>:


Looks like we can't do any better than that -- can we??
Comment 11 Richard Biener 2008-11-22 15:47:28 UTC
I don't see how.  Fixed thus, WONTFIX on the branches.