cfg merge part 10 - BB duplication framework
Jan Hubicka
jh@suse.cz
Wed Mar 6 10:31:00 GMT 2002
Hi
this patch adds support for easy-to-use :) insn duplication to emit-rtl.c and
BB duplication to cfglayout.c. It is used by new passes in cfg-branch -
software trace cache, superblock formation, loop unrolling, unswitching and
peeling I would like to move into mainline in future.
It depends on part 7 of merge series that has not been approved yet
(together with part 8).
Bootstrapped/regtested on mainline i386 (but the code is mostly dead now), it
has been tested on cfg-branch on i386, sparc, mips, PPC both before and
after reload.
Honza
Wed Mar 6 19:24:18 CET 2002 Jan Hubicka <jh@suse.cz>
* cfglayout.c (fixup_reorder_chain): Dump duplicated
(cfg_layout_can_duplicate_bb_p, cfg_layout_rerirect_edge,
cfg_layout_duplicate_bb): New global function.
(duplicate_insn_chain): New static function.
* cfglayout.h (cfg_layout_can_duplicate_bb_p, cfg_layout_rerirect_edge,
cfg_layout_duplicate_bb): Declare.
(struct reorder_block_def): Add "original" field.
* emit-rtl.c (emit_copy_of_insn_after): New function.
* rtl.h (emit_copy_of_insn_after): Declare.
*** cfglayout.c1 Wed Mar 6 19:17:36 2002
--- cfglayout.c Wed Mar 6 19:19:49 2002
*************** fixup_reorder_chain ()
*** 529,535 ****
for (bb = BASIC_BLOCK (0), index = 0; bb; bb = RBI (bb)->next, index ++)
{
fprintf (rtl_dump_file, " %i ", index);
! if (forwarder_block_p (bb) && GET_CODE (bb->head) != CODE_LABEL)
fprintf (rtl_dump_file, "compensation ");
else
fprintf (rtl_dump_file, "bb %i ", bb->index);
--- 529,538 ----
for (bb = BASIC_BLOCK (0), index = 0; bb; bb = RBI (bb)->next, index ++)
{
fprintf (rtl_dump_file, " %i ", index);
! if (RBI (bb)->original)
! fprintf (rtl_dump_file, "duplicate of %i ",
! RBI (bb)->original->index);
! else if (forwarder_block_p (bb) && GET_CODE (bb->head) != CODE_LABEL)
fprintf (rtl_dump_file, "compensation ");
else
fprintf (rtl_dump_file, "bb %i ", bb->index);
*************** fixup_fallthru_exit_predecessor ()
*** 601,606 ****
--- 604,845 ----
RBI (c)->next = bb;
RBI (bb)->next = NULL;
}
+ }
+
+ /* Return true in case it is possible to duplicate the basic block BB. */
+
+ bool
+ cfg_layout_can_duplicate_bb_p (bb)
+ basic_block bb;
+ {
+ rtx next;
+ edge s;
+
+ if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR)
+ return false;
+
+ /* Duplicating fallthru block to exit would require adding an jump
+ and splitting the real last BB. */
+ for (s = bb->succ; s; s = s->succ_next)
+ if (s->dest == EXIT_BLOCK_PTR && s->flags & EDGE_FALLTHRU)
+ return false;
+
+ /* Do not attempt to duplicate tablejumps, as we need to unshare
+ the dispatch table. This is dificult to do, as the instructions
+ computing jump destination may be hoisted outside the basic block. */
+ if (GET_CODE (bb->end) == JUMP_INSN && JUMP_LABEL (bb->end)
+ && (next = next_nonnote_insn (JUMP_LABEL (bb->end)))
+ && GET_CODE (next) == JUMP_INSN
+ && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
+ return false;
+ return true;
+ }
+
+ static rtx
+ duplicate_insn_chain (from, to)
+ rtx from, to;
+ {
+ rtx insn, last;
+
+ /* Avoid updating of boundaries of previous basic block. The
+ note will get removed from insn stream in fixup. */
+ last = emit_note (NULL, NOTE_INSN_DELETED);
+
+ /* Create copy at the end of INSN chain. The chain will
+ be reordered later. */
+ for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
+ {
+ rtx new;
+ switch (GET_CODE (insn))
+ {
+ case INSN:
+ case CALL_INSN:
+ case JUMP_INSN:
+ /* Avoid copying of dispatch tables. We never duplicate
+ tablejumps, so this can hit only in case the table got
+ moved far from original jump. */
+ if (GET_CODE (PATTERN (insn)) == ADDR_VEC
+ || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
+ break;
+ new = emit_copy_of_insn_after (insn, get_last_insn ());
+ /* Record the INSN_SCOPE. */
+ VARRAY_GROW (insn_scopes, INSN_UID (new) + 1);
+ VARRAY_TREE (insn_scopes, INSN_UID (new))
+ = VARRAY_TREE (insn_scopes, INSN_UID (insn));
+ break;
+
+ case CODE_LABEL:
+ break;
+
+ case BARRIER:
+ emit_barrier ();
+ break;
+
+ case NOTE:
+ switch (NOTE_LINE_NUMBER (insn))
+ {
+ /* In case prologue is empty and function contain label
+ in first BB, we may want to copy the block. */
+ case NOTE_INSN_PROLOGUE_END:
+
+ case NOTE_INSN_LOOP_VTOP:
+ case NOTE_INSN_LOOP_CONT:
+ case NOTE_INSN_LOOP_BEG:
+ case NOTE_INSN_LOOP_END:
+ /* Strip down the loop notes - we don't really want to keep
+ them consistent in loop copies. */
+ case NOTE_INSN_DELETED:
+ case NOTE_INSN_DELETED_LABEL:
+ /* No problem to strip these. */
+ case NOTE_INSN_EPILOGUE_BEG:
+ case NOTE_INSN_FUNCTION_END:
+ /* Debug code expect these notes to exist just once.
+ Keep them in the master copy.
+ ??? It probably makes more sense to duplicate them for each
+ epilogue copy. */
+ case NOTE_INSN_FUNCTION_BEG:
+ /* There is always just single entry to function. */
+ case NOTE_INSN_BASIC_BLOCK:
+ break;
+
+ /* There is no purpose to duplicate prologue. */
+ case NOTE_INSN_BLOCK_BEG:
+ case NOTE_INSN_BLOCK_END:
+ /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB
+ reordering is in the progress. */
+ case NOTE_INSN_EH_REGION_BEG:
+ case NOTE_INSN_EH_REGION_END:
+ case NOTE_INSN_RANGE_BEG:
+ case NOTE_INSN_RANGE_END:
+ /* Should never exist at BB duplication time. */
+ abort ();
+ break;
+ case NOTE_INSN_REPEATED_LINE_NUMBER:
+ emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ break;
+
+ default:
+ if (NOTE_LINE_NUMBER (insn) < 0)
+ abort ();
+ /* It is possible that no_line_number is set and the note
+ won't be emitted. */
+ emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ }
+ break;
+ default:
+ abort ();
+ }
+ }
+ insn = NEXT_INSN (last);
+ delete_insn (last);
+ return insn;
+ }
+
+ /* Redirect Edge to DEST. */
+ void
+ cfg_layout_redirect_edge (e, dest)
+ edge e;
+ basic_block dest;
+ {
+ int old_index = dest->index;
+
+ /* Avoid redirect_edge_and_branch from overactive optimizing. */
+ dest->index = n_basic_blocks + 1;
+ if (e->flags & EDGE_FALLTHRU)
+ redirect_edge_succ (e, dest);
+ else
+ redirect_edge_and_branch (e, dest);
+ dest->index = old_index;
+ }
+
+ /* Create an duplicate of the basic block BB and redirect edge E into it. */
+
+ basic_block
+ cfg_layout_duplicate_bb (bb, e)
+ basic_block bb;
+ edge e;
+ {
+ rtx insn;
+ edge s, n;
+ basic_block new_bb;
+ gcov_type new_count = e ? e->count : 0;
+
+ if (bb->count < new_count)
+ new_count = bb->count;
+ if (!bb->pred)
+ abort ();
+ #ifdef ENABLE_CHECKING
+ if (!cfg_layout_can_duplicate_bb_p (bb))
+ abort ();
+ #endif
+
+ insn = duplicate_insn_chain (bb->head, bb->end);
+ new_bb = create_basic_block (n_basic_blocks, insn,
+ insn ? get_last_insn () : NULL);
+ alloc_aux_for_block (new_bb, sizeof (struct reorder_block_def));
+
+ if (RBI (bb)->header)
+ {
+ insn = RBI (bb)->header;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ insn = duplicate_insn_chain (RBI (bb)->header, insn);
+ if (insn)
+ RBI (new_bb)->header = unlink_insn_chain (insn, get_last_insn ());
+ }
+
+ if (RBI (bb)->footer)
+ {
+ insn = RBI (bb)->footer;
+ while (NEXT_INSN (insn))
+ insn = NEXT_INSN (insn);
+ insn = duplicate_insn_chain (RBI (bb)->footer, insn);
+ if (insn)
+ RBI (new_bb)->footer = unlink_insn_chain (insn, get_last_insn ());
+ }
+
+ if (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);
+ }
+
+ new_bb->loop_depth = bb->loop_depth;
+ new_bb->flags = bb->flags;
+ for (s = bb->succ; s; s = s->succ_next)
+ {
+ n = make_edge (new_bb, s->dest, s->flags);
+ n->probability = s->probability;
+ if (new_count)
+ /* Take care for overflows! */
+ n->count = s->count * (new_count * 10000 / bb->count) / 10000;
+ else
+ n->count = 0;
+ s->count -= n->count;
+ }
+
+ new_bb->count = new_count;
+ bb->count -= new_count;
+
+ if (e)
+ {
+ new_bb->frequency = EDGE_FREQUENCY (e);
+ bb->frequency -= EDGE_FREQUENCY (e);
+
+ cfg_layout_redirect_edge (e, new_bb);
+ }
+
+ if (bb->count < 0)
+ bb->count = 0;
+ if (bb->frequency < 0)
+ bb->frequency = 0;
+
+ RBI (new_bb)->original = bb;
+ RBI (bb)->copy = new_bb;
+ return new_bb;
}
/* Main entry point to this module - initialize the datastructures for
*** cfglayout.h Wed Mar 6 19:16:57 2002
--- /home/hubicka/egcs/gcc/cfglayout.h Mon Feb 25 17:47:27 2002
*************** typedef struct reorder_block_def
*** 24,35 ****
rtx header;
rtx footer;
basic_block next;
int visited;
} *reorder_block_def;
#define RBI(BB) ((reorder_block_def) (BB)->aux)
extern void cfg_layout_initialize PARAMS ((void));
extern void cfg_layout_finalize PARAMS ((void));
extern void scope_to_insns_initialize PARAMS ((void));
extern void scope_to_insns_finalize PARAMS ((void));
--- 24,41 ----
rtx header;
rtx footer;
basic_block next;
+ basic_block original;
+
+ /* These fields are used by bb-reorder pass. */
int visited;
} *reorder_block_def;
#define RBI(BB) ((reorder_block_def) (BB)->aux)
extern void cfg_layout_initialize PARAMS ((void));
extern void cfg_layout_finalize PARAMS ((void));
+ extern bool cfg_layout_can_duplicate_bb_p PARAMS ((basic_block));
+ extern basic_block cfg_layout_duplicate_bb PARAMS ((basic_block, edge));
extern void scope_to_insns_initialize PARAMS ((void));
extern void scope_to_insns_finalize PARAMS ((void));
+ extern void cfg_layout_redirect_edge PARAMS ((edge, basic_block));
Index: emit-rtl.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/emit-rtl.c,v
retrieving revision 1.251
diff -c -3 -p -r1.251 emit-rtl.c
*** emit-rtl.c 2002/02/28 10:10:57 1.251
--- emit-rtl.c 2002/02/28 15:40:29
*************** restore_line_number_status (old_value)
*** 5076,5079 ****
--- 5271,5339 ----
int old_value;
{
no_line_numbers = old_value;
+ }
+
+ /* Produce exact duplicate of insn INSN after AFTER.
+ Care updating of libcall regions if present. */
+
+ rtx
+ emit_copy_of_insn_after (insn, after)
+ rtx insn, after;
+ {
+ rtx new;
+ rtx note1, note2, link;
+
+ switch (GET_CODE (insn))
+ {
+ case INSN:
+ new = emit_insn_after (copy_insn (PATTERN (insn)), after);
+ break;
+
+ case JUMP_INSN:
+ new = emit_jump_insn_after (copy_insn (PATTERN (insn)), after);
+ break;
+
+ case CALL_INSN:
+ new = emit_call_insn_after (copy_insn (PATTERN (insn)), after);
+ if (CALL_INSN_FUNCTION_USAGE (insn))
+ CALL_INSN_FUNCTION_USAGE (new)
+ = copy_insn (CALL_INSN_FUNCTION_USAGE (insn));
+ SIBLING_CALL_P (new) = SIBLING_CALL_P (insn);
+ CONST_OR_PURE_CALL_P (new) = CONST_OR_PURE_CALL_P (insn);
+ break;
+
+ default:
+ abort ();
+ }
+
+ /* Update LABEL_NUSES. */
+ mark_jump_label (PATTERN (new), new, 0);
+
+ /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
+ make them. */
+ for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
+ if (REG_NOTE_KIND (link) != REG_LABEL)
+ {
+ if (GET_CODE (link) == EXPR_LIST)
+ REG_NOTES (new)
+ = copy_insn_1 (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
+ XEXP (link, 0),
+ REG_NOTES (new)));
+ else
+ REG_NOTES (new)
+ = copy_insn_1 (gen_rtx_INSN_LIST (REG_NOTE_KIND (link),
+ XEXP (link, 0),
+ REG_NOTES (new)));
+ }
+
+ /* Fix the libcall sequences. */
+ if ((note1 = find_reg_note (new, REG_RETVAL, NULL_RTX)) != NULL)
+ {
+ rtx p = new;
+ while ((note2 = find_reg_note (p, REG_LIBCALL, NULL_RTX)) == NULL)
+ p = PREV_INSN (p);
+ XEXP (note1, 0) = p;
+ XEXP (note2, 0) = new;
+ }
+ return new;
}
Index: rtl.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/rtl.h,v
retrieving revision 1.331
retrieving revision 1.312.2.17
diff -c -3 -p -r1.331 -r1.312.2.17
*** rtl.h 2002/02/20 23:19:19 1.331
--- rtl.h 2002/02/22 13:25:47 1.312.2.17
*************** extern rtx gen_rtx PARAMS ((enum rtx_c
*** 1237,1242 ****
--- 1272,1278 ----
extern rtvec gen_rtvec PARAMS ((int, ...));
extern rtx copy_insn_1 PARAMS ((rtx));
extern rtx copy_insn PARAMS ((rtx));
+ extern rtx emit_copy_of_insn_after PARAMS ((rtx, rtx));
/* In rtl.c */
extern rtx rtx_alloc PARAMS ((RTX_CODE));
More information about the Gcc-patches
mailing list