This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] Avoid creating empty basic blocks in ifcvt.c


As unrelated as it might appear, the following patch is the first
part of my proposed solution to PR tree-optimization/16220 which is
a code quality regression on the alpha.  The mysterious approach
below is to avoid generating empty forwarder blocks on the fallthru
edges of conditional branches in if-conversion's IF-CASE-1 (there's
even a comment in the code that this case may create jump's to jumps).

The IF-CASE-1 transformation concerns the speculative execution of
small basic blocks, whose results are dead if the conditional branch
is taken the other way.  Hence it turns

	if (cond)
	  x = 0;
	else
	  x = big();

Into the equivalent

	x = 0;
	if (!cond)
	  x = big();

[It doesn't look like a huge win, but it avoids a unconditional branch].
The problem is with how we rearrange the CFG to perform this
transformation.  Initially the CFG looks like the following, with
the "test_bb" represented by "0", the "then_bb" represented by "1",
the "else_bb" represented by "2" and the "join_bb" by "3".

	  0-+
	  | |
	+-1 |
	|   |
	| 2<+
	| |
	+>3

The initial transformation to move all of the instructions from the
then_bb and invert the sense of the conditional jump leaves the CFG
in the following state with "1" empty.

	  0-+
	  | |
	+-1 |
	|   |
	| 2 |
	| | |
	+>3<+

The current code effects the second half of this transformation, the
redirecting of the fallthru edge for 0->1 to 0->2 and deleting of
block "1", in that order.  Unfortunately redirecting of the fallthru
edge requires creation of a new basic block, which leads the the
following intermediates.

Step #1, after redirect edge (both 1 and 4 are forwarder blocks).

	  0---+
	  |   |
	  4-+ |
            | |
	+-1 | |
	|   | |
	| 2<+ |
	| |   |
	+>3<--+

Step #2, after delete_basic_block (block 4 is a forwarder block).

	0---+
	|   |
	4-+ |
          | |
	2<+ |
	|   |
	3<--+


Which leaves the fallthru edge from 0 to a forwarder block 4, that
contains an unconditional jump to the original else block 2.  This
is clearly inefficient if the blocks are arranged/ordered as shown
above where the deletion of block 1 would naturally allow "0" to
fallthru to two.  i.e.

	0-+
	| |
	2 |
	| |
	3<+

The patch below implements this optimization and avoids the need
for cleanup_cfg to sort everything out later.


The reason this helps PR tree-optimization/16220 is that the cleaner
CFG allows if-conversion to continue to iterate on the CFG, in this
case the else_block can be conditionally executed once IF-CASE-1 has
been applied, but the unnecessary forwarder block prevents this from
being recognized.

For the example code attached to the bugzilla PR, we previously
generated the following on alpha,

ticks:  cmplt $16,$18,$18
        lda $1,1($31)
        sll $1,32,$0
        beq $18,$L7
        addq $0,$17,$0
        ret $31,($26),1
$L7:    bis $31,$31,$0
        addq $0,$17,$0
        ret $31,($26),1

but with this tweak we now generate the improved (but still not perfect):

ticks:  cmplt $16,$18,$18
        lda $0,1($31)
        sll $0,32,$0
        cmoveq $18,0,$0
        addq $0,$17,$0
        ret $31,($26),1


The following patch has been tested on both i686-pc-linux-gnu and
alphaev67-dec-osf5.1 with a full "make bootstrap", all default languages
and regression tested with a top-level "make -k check" with no new
failures.

Ok for mainline?


2005-01-03  Roger Sayle  <roger@eyesopen.com>

	* ifcvt.c (find_if_case_1): Avoid creating an empty forwarder block,
	if deleting the then-block allows the test-block to fallthru to the
	else-block.

Index: ifcvt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/ifcvt.c,v
retrieving revision 1.174
diff -c -3 -p -r1.174 ifcvt.c
*** ifcvt.c	18 Dec 2004 15:26:32 -0000	1.174
--- ifcvt.c	4 Jan 2005 19:19:10 -0000
*************** find_if_case_1 (basic_block test_bb, edg
*** 2927,2933 ****
  	      else_bb->global_live_at_start,
  	      then_bb->global_live_at_end);

!   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
    then_bb_index = then_bb->index;
    delete_basic_block (then_bb);

--- 2927,2947 ----
  	      else_bb->global_live_at_start,
  	      then_bb->global_live_at_end);

!
!   /* We can avoid creating a new basic block if then_bb is immediately
!      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
!      thru to else_bb.  */
!
!   if (then_bb->next_bb == else_bb
!       && then_bb->prev_bb == test_bb)
!     {
!       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
!       new_bb = 0;
!     }
!   else
!     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
!                                              else_bb);
!
    then_bb_index = then_bb->index;
    delete_basic_block (then_bb);



Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]