[PATCH,RFC] CSE path following on basic blocks

[Eric Botcazou]

>         * cse.c: Include cfglayout.h.
>         (struct cse_basic_block_data): Remove LAST field.
>         (struct branch_path): Remove BRANCH and TAKEN fields. Add new
>         BB field.
>         (cse_visited_basic_blocks): New static bitmap.

Probably already corrected, but not static in the patch.


>         (cse_end_of_basic_block, cse_basic_block): Remove.
>         (cse_find_path, cse_dump_path, cse_prescan_path,
>         cse_extended_basic_block): New static functions.

!   /* There is a previous path.  Make sure it started with FIRST_BB.  */
!   if (path_size)
!     gcc_assert (data->path[0].bb = first_bb);

Not sure what you're trying to do here.  Or maybe an annoying typo?


!   /* There was only one basic block in the last path.  Clear the path and
!      return, so that paths starting at another basic block can be tried.  */
!   if (path_size == 1)
!     {
!       data->path[--path_size].bb = NULL;
!       goto done;
!     }

I think it is not cse_find_path's job to care "so that paths starting at 
another basic block can be tried", it's that of its caller.  IMHO the caller 
should not expect anything from cse_find_path if it returns false and, in 
this case, must take care of re-initializing the framework.  Same a few lines 
below in the function.


!       /* Otherwise, path_size must be equal to or greater than 2, because
! 	 a previous path exists that is at least two basic blocks long.  */
!       gcc_assert (path_size >= 2);

I'm generally for assertions, but this one is useless as the 0 and 1 cases are 
short-circuited just above.

It seems to me that cse_find_path is a nop if flag_cse_follow_jumps is not set 
so it should not be invoked in this case, only cse_prescan_path should be.

But aren't you fundamentally altering the meaning of flag_cse_follow_jumps 
here?  The current CSE works on extended basic blocks independently of 
whether flag_cse_follow_jumps is set.


! #if ENABLE_CHECKING
! 		  /* We should only see blocks here that we have not
! 		     visited yet.  */
! 		  gcc_assert (!TEST_BIT (cse_visited_basic_blocks, bb->index));
! #endif

Is that really true with a DFS traversal?

>         (cse_insn): Don't CSE over setjmp calls.  Use the CFG to find
>         basic block boundaries.  Don't record jump equivalences here.

        if ((src_ent->first_reg == REGNO (SET_DEST (sets[0].rtl)))
  	  && ! find_reg_note (insn, REG_RETVAL, NULL_RTX))
  	{
  	  /* Scan for the previous nonnote insn, but stop at a basic
  	     block boundary.  */
+ 	  rtx prev = insn;
+ 	  rtx bb_head = BB_HEAD (BLOCK_FOR_INSN (insn));
  	  do
  	    {
  	      prev = PREV_INSN (prev);
  	    }
! 	  while (prev != bb_head);
  
  	  /* Do not swap the registers around if the previous instruction
  	     attaches a REG_EQUIV note to REG1.

Convoluted way to write "prev = bb_head;" :-)


*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5599,5606 ****
  	     This section previously turned the REG_EQUIV into a REG_EQUAL
  	     note.  We cannot do that because REG_EQUIV may provide an
  	     uninitialized stack slot when REG_PARM_STACK_SPACE is used.  */
! 
! 	  if (prev != 0 && NONJUMP_INSN_P (prev)
  	      && GET_CODE (PATTERN (prev)) == SET
  	      && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
  	      && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))
--- 5609,5616 ----
  	     This section previously turned the REG_EQUIV into a REG_EQUAL
  	     note.  We cannot do that because REG_EQUIV may provide an
  	     uninitialized stack slot when REG_PARM_STACK_SPACE is used.  */
! 	  gcc_assert (prev);
! 	  if (NONJUMP_INSN_P (prev)
  	      && GET_CODE (PATTERN (prev)) == SET
  	      && SET_DEST (PATTERN (prev)) == SET_SRC (sets[0].rtl)
  	      && ! find_reg_note (prev, REG_EQUIV, NULL_RTX))

Please explain.


*************** cse_insn (rtx insn, rtx libcall_insn)
*** 5647,5652 ****
--- 5652,5659 ----
    prev_insn_cc0_mode = this_insn_cc0_mode;
    prev_insn = insn;
  #endif
+ 
+   return;
  }
   
Rather clever attempt to grow the size of the patch. :-)


>         (cse_main): Rewrite.  Look for extended basic block headers
>         and call cse_extended_basic_block on them until all paths that
>         start at this header are exhausted.

! 	  /* Get a reasonable extimate for the maximum number of qty's
! 	     needed for this path.  For this, we take the number of sets
! 	     and multiply that by MAX_RECOG_OPERANDS.
! 	     The old CSE path following code would use MIN(2*nsets,500)
! 	     but now that we know exactly how many insns (and hence sets)
! 	     we will see in the path, it seemed like a good idea to just
! 	     use max_qty = 2 * nsets.  Interestingly, we end up writing
! 	     past the end of qty_table with that value for max_qty.  In
! 	     other words, this was a latent bug in cse.c present since 
! 	     at least 1992.
! 	     Oh well, we just take a bigger max_qty now to play safe.  */
! 	  max_qty = ebb_data.nsets * MAX_RECOG_OPERANDS;
! 	  cse_basic_block_start = ebb_data.low_cuid;
! 	  cse_basic_block_end = ebb_data.high_cuid;

Firstly it's MAX(2*nsets,500), not MIN, in the old code.  Secondly, "a 
reasonable estimate" sounds a little worrying and the old code really
thinks it computes an upper bound.  If that's not true, we should try to 
identify the problem instead of papering over it.


>         (rest_of_handle_cse): Initialize cfglayout mode.  Verify that
>         the CFG is incrementally updated and correct after cse_main.
>         Don't call delete_trivially_dead_insns, let cfgcleanup do that.
>         (rest_of_handle_cse2): Verify the CFG here, too, after cse_main.

Why the dissymmetry between rest_of_handle_cse and rest_of_handle_cse2?

! #ifdef ENABLE_CHECKING
!   if (purge_all_dead_edges ())
!     gcc_unreachable ();
! #endif

Could you add a comment (especially in rest_of_handle_cse2)?

>         (pass_cse): Add TODO_verify_flow.
>         (pass_cse2): Likewise.

Thanks for writing down the ChangeLog.

-- 
Eric Botcazou