------- 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