[Bug tree-optimization/23622] New: Dom jump threading at -O1 confuses branch prediction

[Bug tree-optimization/23622] New: Dom jump threading at -O1 confuses branch prediction

[rakdver at gcc dot gnu dot org]

Given a loop

for (i = 0; i < 100; i++)
  something ();

translated as

L1:
  i_1 = phi (0, i_2)
  if (i_1 > 100)
    goto exit;

L2:
  something ();
  i_2 = i_1 + 1;
  goto L1;

Jump threading in dom1 produces

  i_3 = phi(0);
  goto L2;

L1:
  i_1 = phi(i_2);
  if (i_1 > 100)
    goto exit;

L2:
  i_4 = phi (i_3, i_1)
  something ();
  i_2 = i_4 + 1;
  goto L1;

Since dom does not iterate at -O1, the phi nodes with one argument
(in particular, i_3 = phi(0)) are not removed.  This prevents # of iterations
analysis from determining that the loop iterates a constant number of times,
since it does not handle such phi nodes. Consequently we lose the corresponding
branch predictor for this loop.

-- 
           Summary: Dom jump threading at -O1 confuses branch prediction
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: rakdver at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/23622] Dom jump threading at -O1 confuses branch prediction

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-29 12:57 -------
Hmm, in dom1 we get:
<bb 0>:
  goto <bb 4> (<L3>);

  # i_4 = PHI <i_1(2), i_2(4)>;
<L0>:;
  something ();
  i_3 = i_4 + 1;

  # i_1 = PHI <i_3(1)>;
<L1>:;
  if (i_1 <= 99) goto <L0>; else goto <L2>;

<L2>:;
  return;

  # i_2 = PHI <0(0)>;
<L3>:;
  goto <bb 1> (<L0>);

In PHI-OPT we get:
  # i_4 = PHI <i_3(1), 0(0)>;
<L0>:;
  something ();
  i_3 = i_4 + 1;
  if (i_3 <= 99) goto <L0>; else goto <L2>;

Becuase we run a cfg cleanup.  I don't see anything wrong here now.

This is the same for -O2 also.

-- 


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

[Bug tree-optimization/23622] Dom jump threading at -O1 confuses branch prediction

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2005-08-29 13:18 -------
Sorry, I have simplified the testcase and only looked at the dom1 dump.  You
need the following testcase to reproduce the problem (for the second loop):

void foo (void)
{
  int i;

  for (i = 0; i < 100; i++)
    something ();
  for (i = 0; i < 100; i++)
    something ();
}

-- 


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

[Bug tree-optimization/23622] Dom jump threading at -O1 confuses branch prediction

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-29 16:20 -------
If we run CCP right after DOM and do a DCE, we get a cleaned up loops.

-- 


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

[Bug tree-optimization/23622] Dom jump threading at -O1 confuses branch prediction

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-09-15 19:28 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-09-15 19:28:17
               date|                            |


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