This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
RFC [cfg-branch] code hoisting infrastructure fucntions
- From: Jan Hubicka <jh at suse dot cz>
- To: gcc-pdo at atrey dot karlin dot mff dot cuni dot cz, gcc-patches at gcc dot gnu dot org, law at cygnus dot com, m dot hayes at elec dot canterbury dot ac dot nz
- Date: Tue, 15 Jan 2002 16:57:52 +0100
- Subject: RFC [cfg-branch] code hoisting infrastructure fucntions
[sorry for resent, I made typo in email address :( ]
Hi,
this code adds some infrastructure for code hoisting. Basically I expect user
to decide that he wants to move given instruction to location with given live
hard registers. can_hoist_insn verifyes that the motion is correct and it will
not overwrite some live hard registers - rest needs to be checked by caller
(trapping, side effects, validity to extend live range).
I want to use it for loop unswitching and to improve gcse ability to move invariant
code out of the loops to replace old loop.c code eventually.
In future I would like to extend the existing bits to support libcalls.
Honza
Tue Jan 15 17:47:33 CET 2002 Jan Hubicka <jh@suse.cz>
* cfgrtl.c: Include insn-config.h, recog.h and expr.h
(hoist_test_store, hoist_update_store): New static functions.
(can_hoist_insn, hoist_insn_after, hoist_insn_to_edge): New
global functions.
* emit-rtl.c (emit_copy_of_insn_after): New.
* cfglayout.c (cfg_layout_duplicate_bb): Use emit_copy_of_insn_after.
* basic-block.h (can_hoist_insn_p, hoist_insn_after,
hoist_insn_to_edge): Declare.
* Makefile.in (cfgrtl.o): Add dependencies.
* rtl.h (emit_copy_of_insn_after): Declare.
*** ../../n/egcs/gcc/cfgrtl.c Thu Jan 10 14:38:20 2002
--- cfgrtl.c Tue Jan 15 17:45:04 2002
*************** Software Foundation, 59 Temple Place - S
*** 56,61 ****
--- 56,64 ----
#include "toplev.h"
#include "tm_p.h"
#include "obstack.h"
+ #include "insn-config.h"
+ #include "recog.h"
+ #include "expr.h"
/* Stubs in case we don't have a return insn. */
#ifndef HAVE_return
*************** static bool try_redirect_by_replacing_ju
*** 79,84 ****
--- 82,89 ----
static rtx last_loop_beg_note PARAMS ((rtx));
static bool back_edge_of_syntactic_loop_p PARAMS ((basic_block, basic_block));
static basic_block force_nonfallthru_and_redirect PARAMS ((edge, basic_block));
+ static bool hoist_test_store PARAMS ((rtx, rtx, regset));
+ static void hoist_update_store PARAMS ((rtx, rtx *, rtx, rtx));
/* Return true if NOTE is not one of the ones that must be kept paired,
so that we may simply delete it. */
*************** purge_all_dead_edges (update_life_p)
*** 2166,2169 ****
--- 2172,2412 ----
if (update_life_p)
sbitmap_free (blocks);
return purged;
+ }
+
+ static bool
+ hoist_test_store (x, val, live)
+ rtx x, val;
+ regset live;
+ {
+ if (GET_CODE (x) == SCRATCH)
+ return true;
+
+ if (rtx_equal_p (x, val))
+ return true;
+
+ /* Allow subreg of X in case it is not writting just part of multireg pseudo.
+ Then we would need to update all users to care hoisting the store too.
+ Caller may represent that by specifying whole subreg as val. */
+
+ if (GET_CODE (x) == SUBREG && rtx_equal_p (SUBREG_REG (x), val))
+ {
+ if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD
+ && GET_MODE_BITSIZE (GET_MODE (x)) <
+ GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
+ return false;
+ return true;
+ }
+ if (GET_CODE (x) == SUBREG)
+ x = SUBREG_REG (x);
+
+ /* Anything except register store is not hoistable. This includes the
+ partial stores to registers. */
+
+ if (!REG_P (x))
+ return false;
+
+ /* Pseudo registers can be allways replaced by another pseudo to avoid
+ the side effect, for hard register we must ensure that they are dead.
+ Eventually we may want to add code to try turn pseudos to hards, but it
+ is unlikely usefull. */
+
+ if (REGNO (x) < FIRST_PSEUDO_REGISTER)
+ {
+ int regno = REGNO (x);
+ int n = HARD_REGNO_NREGS (regno, GET_MODE (x));
+
+ if (!live)
+ return false;
+ if (REGNO_REG_SET_P (live, regno))
+ return false;
+ while (--n > 0)
+ if (REGNO_REG_SET_P (live, regno + n))
+ return false;
+ }
+ return true;
+ }
+
+ bool
+ can_hoist_insn_p (insn, val, live)
+ rtx insn, val;
+ regset live;
+ {
+ rtx pat = PATTERN (insn);
+ int i;
+
+ /* It probably does not worth the complexity to handle multiple
+ set stores. */
+ if (!single_set (insn))
+ return false;
+ /* We can move CALL_INSN, but we need to check that all caller clobbered
+ regs are dead. */
+ if (GET_CODE (insn) == CALL_INSN)
+ return false;
+ /* In future we will handle hoisting of libcall sequences, but
+ give up for now. */
+ if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ return false;
+ switch (GET_CODE (pat))
+ {
+ case SET:
+ if (!hoist_test_store (SET_DEST (pat), val, live))
+ return false;
+ break;
+ case USE:
+ break;
+ case CLOBBER:
+ if (!hoist_test_store (XEXP (pat, 0), val, live))
+ return false;
+ break;
+ case PARALLEL:
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
+ switch (GET_CODE (x))
+ {
+ case SET:
+ if (!hoist_test_store (SET_DEST (x), val, live))
+ return false;
+ break;
+ case USE:
+ break;
+ case CLOBBER:
+ if (!hoist_test_store (SET_DEST (x), val, live))
+ return false;
+ break;
+ default:
+ break;
+ }
+ }
+ break;
+ default:
+ abort ();
+ }
+ return true;
+ }
+
+ static void
+ hoist_update_store (insn, xp, val, new)
+ rtx insn, *xp, val, new;
+ {
+ rtx x = *xp;
+
+ if (GET_CODE (x) == SCRATCH)
+ return;
+
+ if (GET_CODE (x) == SUBREG && SUBREG_REG (x) == val)
+ validate_change (insn, xp,
+ simplify_gen_subreg (GET_MODE (x), new, GET_MODE (new),
+ SUBREG_BYTE (x)), 1);
+ if (rtx_equal_p (x, val))
+ {
+ validate_change (insn, xp, new, 1);
+ return;
+ }
+ if (GET_CODE (x) == SUBREG)
+ {
+ xp = &SUBREG_REG (x);
+ x = *xp;
+ }
+
+ if (!REG_P (x))
+ abort ();
+
+ /* We've verified that hard registers are dead, so we may keep the side
+ effect. Otherwise replace it by new pseudo. */
+ if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
+ validate_change (insn, xp, gen_reg_rtx (GET_MODE (x)), 1);
+ REG_NOTES (insn)
+ = alloc_EXPR_LIST (REG_UNUSED, *xp, REG_NOTES (insn));
+ }
+
+ /* Create a copy of INSN after AFTER replacing store of VAL to NEW
+ and each other side effect to pseudo register by new pseudo register. */
+
+ rtx
+ hoist_insn_after (insn, after, val, new)
+ rtx insn, after, val, new;
+ {
+ rtx pat;
+ int i;
+ rtx new_insn = NULL_RTX;
+ rtx note;
+
+ insn = emit_copy_of_insn_after (insn, after);
+ pat = PATTERN (insn);
+
+ /* Remove REG_UNUSED notes as we will re-emit them. */
+ while ((note = find_reg_note (insn, REG_UNUSED, NULL_RTX)))
+ remove_note (insn, note);
+
+ /* Remove REG_DEAD notes as they might not be valid anymore in case
+ we create redundancy. */
+ while ((note = find_reg_note (insn, REG_DEAD, NULL_RTX)))
+ remove_note (insn, note);
+ switch (GET_CODE (pat))
+ {
+ case SET:
+ hoist_update_store (insn, &SET_DEST (pat), val, new);
+ break;
+ case USE:
+ break;
+ case CLOBBER:
+ hoist_update_store (insn, &XEXP (pat, 0), val, new);
+ break;
+ case PARALLEL:
+ for (i = 0; i < XVECLEN (pat, 0); i++)
+ {
+ rtx x = XVECEXP (pat, 0, i);
+ switch (GET_CODE (x))
+ {
+ case SET:
+ hoist_update_store (insn, &SET_DEST (x), val, new);
+ break;
+ case USE:
+ break;
+ case CLOBBER:
+ hoist_update_store (insn, &SET_DEST (x), val, new);
+ break;
+ default:
+ break;
+ }
+ }
+ break;
+ default:
+ abort ();
+ }
+ if (!apply_change_group ())
+ abort ();
+
+ return new_insn;
+ }
+
+ rtx
+ hoist_insn_to_edge (insn, e, val, new)
+ rtx insn, val, new;
+ edge e;
+ {
+ rtx new_insn;
+
+ /* We cannot insert instructions on an abnormal critical edge.
+ It will be easier to find the culprit if we die now. */
+ if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
+ abort ();
+
+ /* Do not use emit_insn_on_edge as we want to preserve notes and similar
+ stuff. We also emit CALL_INSNS and firends. */
+ if (e->insns == NULL_RTX)
+ {
+ start_sequence ();
+ emit_note (NULL, NOTE_INSN_DELETED);
+ }
+ else
+ push_to_sequence (e->insns);
+
+ new_insn = hoist_insn_after (insn, get_last_insn (), val, new);
+
+ e->insns = get_insns ();
+ end_sequence ();
+ return new_insn;
}
*** ../../n/egcs/gcc/emit-rtl.c Mon Jan 7 14:56:49 2002
--- emit-rtl.c Tue Jan 15 11:52:01 2002
*************** restore_line_number_status (old_value)
*** 5002,5005 ****
--- 5013,5081 ----
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 (copy_insn (PATTERN (insn)));
+ break;
+
+ case CALL_INSN:
+ new = emit_call_insn (copy_insn (PATTERN (insn)));
+ 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;
}
*** ../../n/egcs/gcc/cfglayout.c Sat Jan 12 17:52:16 2002
--- cfglayout.c Tue Jan 15 12:01:38 2002
*************** cfg_layout_duplicate_bb (bb, e)
*** 691,696 ****
--- 690,699 ----
abort ();
#endif
+ /* 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 = RBI (bb)->eff_head; insn != NEXT_INSN (RBI (bb)->eff_end);
*************** cfg_layout_duplicate_bb (bb, e)
*** 700,768 ****
switch (GET_CODE (insn))
{
case INSN:
! new = emit_insn (copy_insn (PATTERN (insn)));
!
! /* This code is common to INSN, JUMP_INSN and CALL_INSN. */
! insn_common:
! /* 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));
!
! /* 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);
! if (p == pre_head)
! abort ();
! }
! XEXP (note1, 0) = p;
! XEXP (note2, 0) = new;
! }
! break;
!
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)
! abort ();
! new = emit_jump_insn (copy_insn (PATTERN (insn)));
! goto insn_common;
!
! case CALL_INSN:
! new = emit_call_insn (copy_insn (PATTERN (insn)));
! 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);
! goto insn_common;
case CODE_LABEL:
break;
--- 703,722 ----
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;
*** ../../n/egcs/gcc/basic-block.h Sat Jan 12 19:44:58 2002
--- basic-block.h Tue Jan 15 03:06:50 2002
*************** extern conflict_graph conflict_graph_com
*** 705,710 ****
--- 712,720 ----
extern bool mark_dfs_back_edges PARAMS ((void));
extern void set_edge_can_fallthru_flag PARAMS ((void));
extern void update_br_prob_note PARAMS ((basic_block));
+ extern bool can_hoist_insn_p PARAMS ((rtx, rtx, regset));
+ extern rtx hoist_insn_after PARAMS ((rtx, rtx, rtx, rtx));
+ extern rtx hoist_insn_to_edge PARAMS ((rtx, edge, rtx, rtx));
/* In dominance.c */
*** ../../n/egcs/gcc/Makefile.in Sat Jan 12 17:27:14 2002
--- Makefile.in Tue Jan 15 17:46:34 2002
*************** cfg.o : cfg.c $(CONFIG_H) $(SYSTEM_H) $(
*** 1489,1497 ****
function.h except.h $(GGC_H) $(TM_P_H)
cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
! function.h except.h $(GGC_H) $(TM_P_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h $(GGC_H)
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H)
--- 1489,1497 ----
function.h except.h $(GGC_H) $(TM_P_H)
cfgrtl.o : cfgrtl.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
! function.h except.h $(GGC_H) $(TM_P_H) insn-config.h $(RECOG_H) $(EXPR_H)
cfganal.o : cfganal.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \
$(BASIC_BLOCK_H) hard-reg-set.h $(GGC_H)
cfgbuild.o : cfgbuild.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h insn-config.h \
$(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h $(RECOG_H) \
function.h except.h $(GGC_H)
*** ../../n/egcs/gcc/rtl.h Sat Jan 12 17:44:16 2002
--- rtl.h Tue Jan 15 11:53:39 2002
*************** extern rtx gen_rtx PARAMS ((enum rtx_c
*** 1236,1241 ****
--- 1236,1242 ----
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));