[Bug middle-end/23181] [4.1 Regression] Dominator opts slows down bresenham line drawing by roughly 20%

["law at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #8 from law at redhat dot com  2005-10-13 17:11 -------
Subject: Re:  [4.1 Regression] Dominator opts
        slows down bresenham line drawing by roughly 20%

On Wed, 2005-10-12 at 00:37 +0000, pinskia at gcc dot gnu dot org wrote:
> int g(int);
> int f(int i, int j)
> {
>   i +=1;
>   if (j)
>    i+=100;
>   i+=1;
>   g(i);
>   return i;
> }
I don't really see how this is a DOM problem:


Before edge-splitting and PRE we have the following:

f (i, j)
{
  int D.1282;

  # BLOCK 0 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  i_3 = i_2 + 1;
  if (j_4 != 0) goto <L0>; else goto <L1>;
  # SUCC: 1 [67.0%]  (true,exec) 2 [33.0%]  (false,exec)

  # BLOCK 1 freq:6700
  # PRED: 0 [67.0%]  (true,exec)
<L0>:;
  i_8 = i_2 + 101;
  # SUCC: 2 [100.0%]  (fallthru,exec)

  # BLOCK 2 freq:10000
  # PRED: 0 [33.0%]  (false,exec) 1 [100.0%]  (fallthru,exec)
  # i_1 = PHI <i_3(0), i_8(1)>;
<L1>:;
  i_5 = i_1 + 1;
  g (i_5);
  return i_5;
  # SUCC: EXIT [100.0%]

}


Which is exactly what I would expect -- this is a simple, straightfoward
translation of the code.  When turned into RTL this will need a single
branch.

critical edge splitting splits the edge from 0->2 resulting in:

;; Function f (f)

f (i, j)
{
  int D.1282;

  # BLOCK 0 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  i_3 = i_2 + 1;
  if (j_4 != 0) goto <L0>; else goto <L3>;
  # SUCC: 1 [67.0%]  (true,exec) 3 [33.0%]  (false,exec)

  # BLOCK 3 freq:3300
  # PRED: 0 [33.0%]  (false,exec)
<L3>:;
  goto <bb 2> (<L1>);
  # SUCC: 2 [100.0%]  (fallthru)

  # BLOCK 1 freq:6700
  # PRED: 0 [67.0%]  (true,exec)
<L0>:;
  i_8 = i_2 + 101;
  # SUCC: 2 [100.0%]  (fallthru,exec)

  # BLOCK 2 freq:10000
  # PRED: 3 [100.0%]  (fallthru) 1 [100.0%]  (fallthru,exec)
  # i_1 = PHI <i_3(3), i_8(1)>;
<L1>:;
  i_5 = i_1 + 1;
  g (i_5);
  return i_5;
  # SUCC: EXIT [100.0%]

}

Which again is OK -- if nothing gets inserted into BB3, then it will
go away later again leaving us with one branch.  Neither reassociation
nor PRE make any changes.

Code sinking (correctly) drops i3 = i2 + 1 into BB3.  It may not be
the most profitable thing to do in this specific case, but it is
precisely what code sinking is supposed to do.  Thus after code
sinking we have:

Sinking i_3 = i_2 + 1 from bb 0 to bb 3
f (i, j)
{
  int D.1282;

  # BLOCK 0 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  if (j_4 != 0) goto <L0>; else goto <L3>;
  # SUCC: 1 [67.0%]  (true,exec) 3 [33.0%]  (false,exec)

  # BLOCK 3 freq:3300
  # PRED: 0 [33.0%]  (false,exec)
<L3>:;
  i_3 = i_2 + 1;
  goto <bb 2> (<L1>);
  # SUCC: 2 [100.0%]  (fallthru)

  # BLOCK 1 freq:6700
  # PRED: 0 [67.0%]  (true,exec)
<L0>:;
  i_8 = i_2 + 101;
  # SUCC: 2 [100.0%]  (fallthru,exec)

  # BLOCK 2 freq:10000
  # PRED: 3 [100.0%]  (fallthru) 1 [100.0%]  (fallthru,exec)
  # i_1 = PHI <i_3(3), i_8(1)>;
<L1>:;
  i_5 = i_1 + 1;
  g (i_5);
  return i_5;
  # SUCC: EXIT [100.0%]

}

Which now requires two branches no matter how the code is laid out.

Nothing after code sinking makes any significant changes to this code.
The extra branches are really an artifact of code sinking moving code
into BB3.


Jeff


-- 


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