RFC: BB duplication code

[Jan Hubicka <jh at suse dot cz>]

Hi,
this patch contains BB duplication code I use in my bb-reorder code and tracer.
It is tied into bb-reorder infrastructure and allows you to simply call
reorder_duplicate_bb for basic block and place it anywhere in the reordered
chain.

While I am able to build bootstrapping and regtesting compiler with this
change (+tracer) I would like to discuss some issues first:

1) In case of copying tablejumps, the vector remains shared.  This is not
   good idea except very latest passes of compilation, but making tablejump
   unshared is dificult task, as code computing destination address using
   the table can be hoisted outside.
   What to do?  Prohibit duplication of tablejumps?
2) Pairable notes are splitted off - I should probably handle the
   paired notes inside single basic block by duplicating, but what to do
   with notes starting or ending in the BB?
   What about EH region notes?  Should I prohibit duplication if EH region
   starts or ends in the BB?
3) Can I update debug information using exiting bb-reorder infrastructure?
   It seems to work already somehow.
4) What about epilogues - I should probably copy the frame_related flag,
   but will the debug output happy to see multiple epilogues?
   It should probably, as it is able to see epilogue in the middle of code.
   What about EPILOGUE_BEGIN note? and FUNCTION_END?
5) Something else I've missed?

Well, thats all for now.  Hope that these issues will settle down somehow
so I will be able to contribute the code soon.

Honza

Wed Aug 22 20:27:43 CEST 2001  Jan Hubicka  <jh@suse.cz>
	* bb-reorder.c (reorder_duplicate_bb): New function.

*** bb-reorder.c1	Tue Aug 21 17:47:08 2001
--- bb-reorder.c	Wed Aug 22 20:22:35 2001
*************** static rtx get_next_bb_note		PARAMS ((rt
*** 196,201 ****
--- 196,202 ----
  static rtx get_prev_bb_note		PARAMS ((rtx));
  
  void verify_insn_chain			PARAMS ((void));
+ static basic_block reorder_duplicate_bb PARAMS ((basic_block, edge));
  
  /* Skip over inter-block insns occurring after BB which are typically
     associated with BB (e.g., barriers). If there are any such insns,
*************** record_effective_endpoints ()
*** 309,314 ****
--- 310,458 ----
      }
  }
  
+ /* Duplicate block BB and redirect edge E into it.  */
+ static basic_block
+ reorder_duplicate_bb (bb, e)
+      basic_block bb;
+      edge e;
+ {
+   rtx last = get_last_insn ();
+   rtx insn, new = NULL_RTX;
+   edge s, n;
+   basic_block new_bb;
+ 
+   if (!bb->pred || !bb->pred->pred_next)
+     abort ();
+ 
+   /* Create copy at the end of INSN chain.  The chain will
+      be reordered later.  */
+ 
+   new_bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*new_bb));
+   memset (new_bb, 0, sizeof (*new_bb));
+   if (new_bb->global_live_at_start)
+     {
+       new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+       new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
+       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
+     }
+ 
+   /* Place the new block after the last block.  */
+   VARRAY_GROW (basic_block_info, ++n_basic_blocks);
+   new_bb = (basic_block) obstack_alloc (&flow_obstack, sizeof (*new_bb));
+   memset (new_bb, 0, sizeof (*new_bb));
+   BASIC_BLOCK (n_basic_blocks - 1) = new_bb;
+ 
+   new_bb = BASIC_BLOCK (n_basic_blocks - 1);
+   new_bb->loop_depth = bb->loop_depth;
+   for (s = bb->succ; s; s = s->succ_next)
+     {
+       n = (edge) xcalloc (1, sizeof (*n));
+       n->src = new_bb;
+       n->dest = s->dest;
+       n->flags = s->flags;
+       n->probability = s->probability;
+       if (bb->count)
+         n->count = s->count * e->count / bb->count;
+       else
+ 	n->count = 0;
+       n->succ_next = new_bb->succ;
+       new_bb->succ = n;
+       n->pred_next = n->dest->pred;
+       n->dest->pred = n;
+     }
+ 
+   new_bb->count = e->count;
+   new_bb->frequency = EDGE_FREQUENCY (e);
+   bb->count -= e->count;
+   bb->frequency -= EDGE_FREQUENCY (e);
+ 
+ 
+   for (insn = RBI (bb)->eff_head; insn != NEXT_INSN (RBI (bb)->eff_end);
+        insn = NEXT_INSN (insn))
+     {
+       switch (GET_CODE (insn))
+ 	{
+ 	  case INSN:
+ 	    new = emit_insn (copy_insn (PATTERN (insn)));
+ 	    if (REG_NOTES (insn))
+ 	      REG_NOTES (new) = copy_insn (REG_NOTES (insn));
+ 	    break;
+ 	  case JUMP_INSN:
+ 	    /* Share jumptables for both copies of tablejump.  */
+ 	    if (GET_CODE (PATTERN (insn)) == ADDR_VEC
+ 		|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
+ 	      continue;
+ 	    new = emit_jump_insn (copy_insn (PATTERN (insn)));
+ 	    if (REG_NOTES (insn))
+ 	      REG_NOTES (new) = copy_insn (REG_NOTES (insn));
+ 	    mark_jump_label (PATTERN (new), new, 0);
+ 	    if (JUMP_LABEL (new))
+ 	      LABEL_NUSES (JUMP_LABEL (new))++;
+ 	    break;
+ 	  case CALL_INSN:
+ 	    new = emit_call_insn (copy_insn (PATTERN (insn)));
+ 	    if (REG_NOTES (insn))
+ 	      REG_NOTES (new) = copy_insn (REG_NOTES (insn));
+ 	    if (CALL_INSN_FUNCTION_USAGE (insn))
+ 	      CALL_INSN_FUNCTION_USAGE (new) = copy_insn (CALL_INSN_FUNCTION_USAGE (insn));
+ 	  case CODE_LABEL:
+ 	    /*new = emit_label (gen_label_rtx ());*/
+ 	    break;
+ 	  case BARRIER:
+ 	    new = emit_barrier ();
+ 	    break;
+ 	  case NOTE:
+ 	    switch (NOTE_LINE_NUMBER (insn))
+ 	      {
+ 		case NOTE_INSN_DELETED:
+ 		case NOTE_INSN_DELETED_LABEL:
+ 		case NOTE_INSN_LOOP_VTOP:
+ 		case NOTE_INSN_LOOP_CONT:
+ 		  break;
+ 		case NOTE_INSN_BASIC_BLOCK:
+ 		  new = emit_note (NULL, NOTE_INSN_BASIC_BLOCK);
+ 		  NOTE_BASIC_BLOCK (new) = new_bb;
+ 		  new_bb->head = new;
+ 		  break;
+ 		case NOTE_INSN_LOOP_BEG:
+ 		case NOTE_INSN_LOOP_END:
+ 		case NOTE_INSN_RANGE_BEG:
+ 		case NOTE_INSN_RANGE_END:
+ 		case NOTE_INSN_EPILOGUE_BEG:
+ 		case NOTE_INSN_PROLOGUE_END:
+ 		case NOTE_INSN_BLOCK_BEG:
+ 		case NOTE_INSN_BLOCK_END:
+ 		case NOTE_INSN_FUNCTION_END:
+ 		case NOTE_INSN_FUNCTION_BEG:
+ 		case NOTE_INSN_EH_REGION_BEG:
+ 		case NOTE_INSN_EH_REGION_END:
+ 		  /* Strip down pairable notes and keep them only
+ 		     in the "master copy".  */
+ 		  break;
+ 		default:
+ 		  new = emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ 	      }
+ 	}
+       if (bb->end == insn)
+ 	new_bb->end = new;
+       if (new && INSN_P (new) && basic_block_for_insn)
+ 	set_block_for_insn (new, new_bb);
+       /*debug_rtx (new);*/
+     }
+   new_bb->index = n_basic_blocks + 1;
+   if (e->flags & EDGE_FALLTHRU)
+     redirect_edge_succ (e, new_bb);
+   else
+     redirect_edge_and_branch (e, new_bb);
+   new_bb->index = n_basic_blocks - 1;
+   new_bb->aux = xmalloc (sizeof (struct reorder_block_def));
+   RBI (new_bb)->eff_head = NEXT_INSN (last);
+   RBI (new_bb)->eff_end = get_last_insn ();
+   RBI (new_bb)->scope = RBI (bb)->scope;
+   return new_bb;
+ }
+ 
  
  /* Compute an ordering for a subgraph beginning with block BB.  Record the
     ordering in RBI()->index and chained through RBI()->next.  */