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]

Re: Find more shrink-wrapping opportunities


Richard Sandiford <rdsandiford@googlemail.com> writes:
> Richard Sandiford <rdsandiford@googlemail.com> writes:
>> Bernd Schmidt <bernds@codesourcery.com> writes:
>>>> The reason I'm suddenly "reviewing" the code now is that it
>>>> doesn't prevent shrink-wrapping, because nothing adds register 2
>>>> to the liveness info of the affected blocks.  The temporary prologue
>>>> value of register 2 is then moved into register 15.
>>>
>>> Hmm. Are we just missing another df_analyze call?
>>
>> Well, if we do the kind of backwards walk I was thinking about (so that
>> we can handle chains), it might be better to update the liveness sets
>> we care about as we go.  A full df_analyze after each move would be
>> pretty expensive.
>
> FWIW, I've got a patch that I'll try to test this weekend.

OK, here it is.  As well as switching to the backward scan and incremental
liveness updates, I added a test for another case that I stumbled over:

  /* Reject targets of abnormal edges.  This is needed for correctness
     on ports like Alpha and MIPS, whose pic_offset_table_rtx can die on
     exception edges even though it is generally treated as call-saved
     for the majority of the compilation.  Moving across abnormal edges
     isn't going to be interesting for shrink-wrap usage anyway.  */
  if (live_edge->flags & EDGE_ABNORMAL)
    return NULL;

The point is that when Alpha and MIPS have call-clobbered global pointers,
they say that the global pointer is call-saved and ensure that the call
patterns restore the gp where necessary.  These combined "call and load"
patterns get split after reload (or in MIPS's case, after prologue/
epilogue generation).  The ports then make sure that exception_receiver
also restores the gp.  The problem is that, if we insert a move from
pic_offset_table_rtx before exception_receiver, we end up moving the
wrong value.

Now all this is really a bit of a hack.  The information ought to be
made more explicit to the target-independent parts of the compiler.
That's going to be quite hard to fix though, and probably isn't stage 3
material.  So while I admit I don't like the test above, it feels like
the best fix for now.

Also, it seemed easiest to drop the single-register restriction at
the same time.  Hopefully this will help for things like DF moves
on 32-bit MIPS FPUs.

While moving bb_note to cfgrtl.c, I was tempted to make rtl_split_block
use it rather than first_insn_after_basic_block_note.  It isn't exactly
a one-for-one transformation though, at least not as far as null checks
go, so I'll leave it for a possible stage 1 cleanup.

Tested on mips64-linux-gnu.  OK to install?

Richard


gcc/
	* sched-int.h (bb_note): Move to...
	* basic-block.h: ...here.
	* haifa-sched.c (bb_note): Move to...
	* cfgrtl.c: ...here.
	* function.c (next_block_for_reg): New function.
	(move_insn_for_shrink_wrap): Likewise.
	(prepare_shrink_wrap): Rewrite to use the above.

Index: gcc/sched-int.h
===================================================================
*** gcc/sched-int.h	2011-12-04 08:52:37.000000000 +0000
--- gcc/sched-int.h	2011-12-04 12:03:51.000000000 +0000
*************** extern void sched_insns_init (rtx);
*** 130,136 ****
  extern void sched_insns_finish (void);
  
  extern void *xrecalloc (void *, size_t, size_t, size_t);
- extern rtx bb_note (basic_block);
  
  extern void reemit_notes (rtx);
  
--- 130,135 ----
Index: gcc/basic-block.h
===================================================================
*** gcc/basic-block.h	2011-12-04 08:52:37.000000000 +0000
--- gcc/basic-block.h	2011-12-04 12:03:51.000000000 +0000
*************** extern void flow_edge_list_print (const
*** 801,806 ****
--- 801,807 ----
  
  /* In cfgrtl.c  */
  extern rtx block_label (basic_block);
+ extern rtx bb_note (basic_block);
  extern bool purge_all_dead_edges (void);
  extern bool purge_dead_edges (basic_block);
  extern bool fixup_abnormal_edges (void);
Index: gcc/haifa-sched.c
===================================================================
*** gcc/haifa-sched.c	2011-12-04 08:52:37.000000000 +0000
--- gcc/haifa-sched.c	2011-12-04 12:03:51.000000000 +0000
*************** add_jump_dependencies (rtx insn, rtx jum
*** 6489,6508 ****
    gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
  }
  
- /* Return the NOTE_INSN_BASIC_BLOCK of BB.  */
- rtx
- bb_note (basic_block bb)
- {
-   rtx note;
- 
-   note = BB_HEAD (bb);
-   if (LABEL_P (note))
-     note = NEXT_INSN (note);
- 
-   gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
-   return note;
- }
- 
  /* Extend data structures for logical insn UID.  */
  void
  sched_extend_luids (void)
--- 6489,6494 ----
Index: gcc/cfgrtl.c
===================================================================
*** gcc/cfgrtl.c	2011-12-04 08:52:37.000000000 +0000
--- gcc/cfgrtl.c	2011-12-04 12:03:51.000000000 +0000
*************** update_bb_for_insn (basic_block bb)
*** 500,505 ****
--- 500,519 ----
  }
  
  
+ /* Return the NOTE_INSN_BASIC_BLOCK of BB.  */
+ rtx
+ bb_note (basic_block bb)
+ {
+   rtx note;
+ 
+   note = BB_HEAD (bb);
+   if (LABEL_P (note))
+     note = NEXT_INSN (note);
+ 
+   gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
+   return note;
+ }
+ 
  /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
     note associated with the BLOCK.  */
  
Index: gcc/function.c
===================================================================
*** gcc/function.c	2011-12-04 08:52:37.000000000 +0000
--- gcc/function.c	2011-12-04 12:21:12.000000000 +0000
*************** requires_stack_frame_p (rtx insn, HARD_R
*** 5330,5455 ****
    return false;
  }
  
! /* Look for sets of call-saved registers in the first block of the
!    function, and move them down into successor blocks if the register
!    is used only on one path.  This exposes more opportunities for
!    shrink-wrapping.
!    These kinds of sets often occur when incoming argument registers are
!    moved to call-saved registers because their values are live across
!    one or more calls during the function.  */
  
! static void
! prepare_shrink_wrap (basic_block entry_block)
  {
!   rtx insn, curr;
!   FOR_BB_INSNS_SAFE (entry_block, insn, curr)
      {
!       basic_block next_bb;
!       edge e, live_edge;
!       edge_iterator ei;
!       rtx set, scan;
!       unsigned destreg, srcreg;
! 
!       if (!NONDEBUG_INSN_P (insn))
! 	continue;
!       set = single_set (insn);
!       if (!set)
! 	continue;
! 
!       if (!REG_P (SET_SRC (set)) || !REG_P (SET_DEST (set)))
! 	continue;
!       srcreg = REGNO (SET_SRC (set));
!       destreg = REGNO (SET_DEST (set));
!       if (hard_regno_nregs[srcreg][GET_MODE (SET_SRC (set))] > 1
! 	  || hard_regno_nregs[destreg][GET_MODE (SET_DEST (set))] > 1)
! 	continue;
  
!       next_bb = entry_block;
!       scan = insn;
  
!       for (;;)
  	{
! 	  live_edge = NULL;
! 	  /* Try to find a single edge across which the register is live.
! 	     If we find one, we'll try to move the set across this edge.  */
! 	  FOR_EACH_EDGE (e, ei, next_bb->succs)
! 	    {
! 	      if (REGNO_REG_SET_P (df_get_live_in (e->dest), destreg))
! 		{
! 		  if (live_edge)
! 		    {
! 		      live_edge = NULL;
! 		      break;
! 		    }
! 		  live_edge = e;
! 		}
! 	    }
! 	  if (!live_edge)
! 	    break;
! 	  /* We can sometimes encounter dead code.  Don't try to move it
! 	     into the exit block.  */
! 	  if (live_edge->dest == EXIT_BLOCK_PTR)
! 	    break;
! 	  if (EDGE_COUNT (live_edge->dest->preds) > 1)
! 	    break;
! 	  while (scan != BB_END (next_bb))
! 	    {
! 	      scan = NEXT_INSN (scan);
! 	      if (NONDEBUG_INSN_P (scan))
! 		{
! 		  rtx link;
! 		  HARD_REG_SET set_regs;
! 
! 		  CLEAR_HARD_REG_SET (set_regs);
! 		  note_stores (PATTERN (scan), record_hard_reg_sets,
! 			       &set_regs);
! 		  if (CALL_P (scan))
! 		    IOR_HARD_REG_SET (set_regs, call_used_reg_set);
! 		  for (link = REG_NOTES (scan); link; link = XEXP (link, 1))
! 		    if (REG_NOTE_KIND (link) == REG_INC)
! 		      record_hard_reg_sets (XEXP (link, 0), NULL, &set_regs);
! 
! 		  if (TEST_HARD_REG_BIT (set_regs, srcreg)
! 		      || reg_referenced_p (SET_DEST (set),
! 					   PATTERN (scan)))
! 		    {
! 		      scan = NULL_RTX;
! 		      break;
! 		    }
! 		  if (CALL_P (scan))
! 		    {
! 		      rtx link = CALL_INSN_FUNCTION_USAGE (scan);
! 		      while (link)
! 			{
! 			  rtx tmp = XEXP (link, 0);
! 			  if (GET_CODE (tmp) == USE
! 			      && reg_referenced_p (SET_DEST (set), tmp))
! 			    break;
! 			  link = XEXP (link, 1);
! 			}
! 		      if (link)
! 			{
! 			  scan = NULL_RTX;
! 			  break;
! 			}
! 		    }
! 		}
! 	    }
! 	  if (!scan)
! 	    break;
! 	  next_bb = live_edge->dest;
  	}
  
!       if (next_bb != entry_block)
  	{
! 	  rtx after = BB_HEAD (next_bb);
! 	  while (!NOTE_P (after)
! 		 || NOTE_KIND (after) != NOTE_INSN_BASIC_BLOCK)
! 	    after = NEXT_INSN (after);
! 	  emit_insn_after (PATTERN (insn), after);
! 	  delete_insn (insn);
  	}
      }
  }
  
  #endif
--- 5330,5511 ----
    return false;
  }
  
! /* See whether BB has a single successor that uses [REGNO, END_REGNO),
!    and if BB is its only predecessor.  Return that block if so,
!    otherwise return null.  */
  
! static basic_block
! next_block_for_reg (basic_block bb, int regno, int end_regno)
  {
!   edge e, live_edge;
!   edge_iterator ei;
!   bitmap live;
!   int i;
! 
!   live_edge = NULL;
!   FOR_EACH_EDGE (e, ei, bb->succs)
      {
!       live = df_get_live_in (e->dest);
!       for (i = regno; i < end_regno; i++)
! 	if (REGNO_REG_SET_P (live, i))
! 	  {
! 	    if (live_edge && live_edge != e)
! 	      return NULL;
! 	    live_edge = e;
! 	  }
!     }
! 
!   /* We can sometimes encounter dead code.  Don't try to move it
!      into the exit block.  */
!   if (!live_edge || live_edge->dest == EXIT_BLOCK_PTR)
!     return NULL;
! 
!   /* Reject targets of abnormal edges.  This is needed for correctness
!      on ports like Alpha and MIPS, whose pic_offset_table_rtx can die on
!      exception edges even though it is generally treated as call-saved
!      for the majority of the compilation.  Moving across abnormal edges
!      isn't going to be interesting for shrink-wrap usage anyway.  */
!   if (live_edge->flags & EDGE_ABNORMAL)
!     return NULL;
  
!   if (EDGE_COUNT (live_edge->dest->preds) > 1)
!     return NULL;
  
!   return live_edge->dest;
! }
! 
! /* Try to move INSN from BB to a successor.  Return true on success.
!    USES and DEFS are the set of registers that are used and defined
!    after INSN in BB.  */
! 
! static bool
! move_insn_for_shrink_wrap (basic_block bb, rtx insn,
! 			   const HARD_REG_SET uses,
! 			   const HARD_REG_SET defs)
! {
!   rtx set, src, dest;
!   bitmap live_out, live_in, bb_uses, bb_defs;
!   unsigned int i, dregno, end_dregno, sregno, end_sregno;
!   basic_block next_block;
! 
!   /* Look for a simple register copy.  */
!   set = single_set (insn);
!   if (!set)
!     return false;
!   src = SET_SRC (set);
!   dest = SET_DEST (set);
!   if (!REG_P (dest) || !REG_P (src))
!     return false;
! 
!   /* Make sure that the source register isn't defined later in BB.  */
!   sregno = REGNO (src);
!   end_sregno = END_REGNO (src);
!   if (overlaps_hard_reg_set_p (defs, GET_MODE (src), sregno))
!     return false;
! 
!   /* Make sure that the destination register isn't referenced later in BB.  */
!   dregno = REGNO (dest);
!   end_dregno = END_REGNO (dest);
!   if (overlaps_hard_reg_set_p (uses, GET_MODE (dest), dregno)
!       || overlaps_hard_reg_set_p (defs, GET_MODE (dest), dregno))
!     return false;
! 
!   /* See whether there is a successor block to which we could move INSN.  */
!   next_block = next_block_for_reg (bb, dregno, end_dregno);
!   if (!next_block)
!     return false;
! 
!   /* At this point we are committed to moving INSN, but let's try to
!      move it as far as we can.  */
!   do
!     {
!       live_out = df_get_live_out (bb);
!       live_in = df_get_live_in (next_block);
!       bb = next_block;
! 
!       /* Check whether BB uses DEST or clobbers DEST.  We need to add
! 	 INSN to BB if so.  Either way, DEST is no longer live on entry,
! 	 except for any part that overlaps SRC (next loop).  */
!       bb_uses = &DF_LR_BB_INFO (bb)->use;
!       bb_defs = &DF_LR_BB_INFO (bb)->def;
!       for (i = dregno; i < end_dregno; i++)
  	{
! 	  if (REGNO_REG_SET_P (bb_uses, i) || REGNO_REG_SET_P (bb_defs, i))
! 	    next_block = NULL;
! 	  CLEAR_REGNO_REG_SET (live_out, i);
! 	  CLEAR_REGNO_REG_SET (live_in, i);
  	}
  
!       /* Check whether BB clobbers SRC.  We need to add INSN to BB if so.
! 	 Either way, SRC is now live on entry.  */
!       for (i = sregno; i < end_sregno; i++)
  	{
! 	  if (REGNO_REG_SET_P (bb_defs, i))
! 	    next_block = NULL;
! 	  SET_REGNO_REG_SET (live_out, i);
! 	  SET_REGNO_REG_SET (live_in, i);
  	}
+ 
+       /* If we don't need to add the move to BB, look for a single
+ 	 successor block.  */
+       if (next_block)
+ 	next_block = next_block_for_reg (next_block, dregno, end_dregno);
      }
+   while (next_block);
+ 
+   /* BB now defines DEST.  It only uses the parts of DEST that overlap SRC
+      (next loop).  */
+   for (i = dregno; i < end_dregno; i++)
+     {
+       CLEAR_REGNO_REG_SET (bb_uses, i);
+       SET_REGNO_REG_SET (bb_defs, i);
+     }
+ 
+   /* BB now uses SRC.  */
+   for (i = sregno; i < end_sregno; i++)
+     SET_REGNO_REG_SET (bb_uses, i);
+ 
+   emit_insn_after (PATTERN (insn), bb_note (bb));
+   delete_insn (insn);
+   return true;
+ }
+ 
+ /* Look for register copies in the first block of the function, and move
+    them down into successor blocks if the register is used only on one
+    path.  This exposes more opportunities for shrink-wrapping.  These
+    kinds of sets often occur when incoming argument registers are moved
+    to call-saved registers because their values are live across one or
+    more calls during the function.  */
+ 
+ static void
+ prepare_shrink_wrap (basic_block entry_block)
+ {
+   rtx insn, curr, x;
+   HARD_REG_SET uses, defs;
+   df_ref *ref;
+ 
+   CLEAR_HARD_REG_SET (uses);
+   CLEAR_HARD_REG_SET (defs);
+   FOR_BB_INSNS_REVERSE_SAFE (entry_block, insn, curr)
+     if (NONDEBUG_INSN_P (insn)
+ 	&& !move_insn_for_shrink_wrap (entry_block, insn, uses, defs))
+       {
+ 	/* Add all defined registers to DEFs.  */
+ 	for (ref = DF_INSN_DEFS (insn); *ref; ref++)
+ 	  {
+ 	    x = DF_REF_REG (*ref);
+ 	    if (REG_P (x) && HARD_REGISTER_P (x))
+ 	      SET_HARD_REG_BIT (defs, REGNO (x));
+ 	  }
+ 
+ 	/* Add all used registers to USESs.  */
+ 	for (ref = DF_INSN_USES (insn); *ref; ref++)
+ 	  {
+ 	    x = DF_REF_REG (*ref);
+ 	    if (REG_P (x) && HARD_REGISTER_P (x))
+ 	      SET_HARD_REG_BIT (uses, REGNO (x));
+ 	  }
+       }
  }
  
  #endif


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