cfg merge part 20 - gcse tweek 2
Jan Hubicka
jh@suse.cz
Mon May 27 08:16:00 GMT 2002
Hi,
the patch to make gcse grok parallels is somewhat involved so I split it
in the half. This part has almost no functional changes, just makes
gcse to use hoisting infrastructure. The only visible effect is to rely
on rtx_cost to decide whether to GCSE given value or not, that is what
local CSE does and at the moment it forgets how to hoists PLUS
instructions on i386, since by default PLUS is represented using addsi
pattern clobbering flags, but old GCSE managed to notice it can create
lea not clobbering the flags and did it from time to time that resulted
in worse register allocation in numberous cases.
The missing bit is that liveness shouild be used to validate each
movement of instruction, that is tricky for PRE as PRE first kills the
duplicates and then does the movements, that needs to be reorganized for
the case moving fails.
The patch contains all logic to handle liveness information but at the moment
it feeds everywhere NULL pointers as liveness bitmap. Code hoisting bits knows
how to be conservative in such a case.
In second stage I would like to break gcse.c into mulitple files -
globalopt.c for the generic helper code, gcse.c, cprop.c and
storemotion.c as the current situation is getting confusing.
Regtested/bootstrapped i386
Honza
Mon May 27 14:33:11 CEST 2002 Jan Hubicka <jh@suse.cz>
* gcse.c (struct_expr): Add insn field.
(want_to_gcse_p): Simplify; use rtx_cost.
(insert_expr_in_table): Store insn.
(hash_scan_set): Do not get confused by single_set with unused
registers; check whether insn is hoistable.
(end_bb_insertion_point): Split out from...
(insert_insn_end_bb): ... here; use hoisting bits.
(can_insert_insn_end_bb_p): New.
(can_insert_insn_edge_p): New.
(pre_edge_insert): Use hoisting bits.
(hoist_code): LIkewise.
Index: gcse.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/gcse.c,v
retrieving revision 1.190
diff -c -3 -p -r1.190 gcse.c
*** gcse.c 23 May 2002 19:23:40 -0000 1.190
--- gcse.c 27 May 2002 12:30:38 -0000
*************** struct expr
*** 315,320 ****
--- 315,321 ----
{
/* The expression (SET_SRC for expressions, PATTERN for assignments). */
rtx expr;
+ rtx insn;
/* Index in the available expression bitmaps. */
int bitmap_index;
/* Next entry with the same hash. */
*************** static void free_pre_mem PARAMS ((void))
*** 624,630 ****
static void compute_pre_data PARAMS ((void));
static int pre_expr_reaches_here_p PARAMS ((basic_block, struct expr *,
basic_block));
! static void insert_insn_end_bb PARAMS ((struct expr *, basic_block, int));
static void pre_insert_copy_insn PARAMS ((struct expr *, rtx));
static void pre_insert_copies PARAMS ((void));
static int pre_delete PARAMS ((void));
--- 625,634 ----
static void compute_pre_data PARAMS ((void));
static int pre_expr_reaches_here_p PARAMS ((basic_block, struct expr *,
basic_block));
! static void insert_insn_end_bb PARAMS ((struct expr *, basic_block));
! static bool can_insert_insn_end_bb_p PARAMS ((struct expr *, basic_block));
! static bool can_insert_insn_edge_p PARAMS ((struct expr *, edge));
! static rtx end_bb_insertion_point PARAMS ((basic_block));
static void pre_insert_copy_insn PARAMS ((struct expr *, rtx));
static void pre_insert_copies PARAMS ((void));
static int pre_delete PARAMS ((void));
*************** static void invalidate_nonnull_info PARA
*** 661,667 ****
static void delete_null_pointer_checks_1 PARAMS ((unsigned int *,
sbitmap *, sbitmap *,
struct null_pointer_info *));
- static rtx process_insert_insn PARAMS ((struct expr *));
static int pre_edge_insert PARAMS ((struct edge_list *, struct expr **));
static int expr_reaches_here_p_work PARAMS ((struct occr *, struct expr *,
basic_block, int, char *));
--- 665,670 ----
*************** static int
*** 1308,1356 ****
want_to_gcse_p (x)
rtx x;
{
! static rtx test_insn = 0;
! int num_clobbers = 0;
! int icode;
!
! switch (GET_CODE (x))
! {
! case REG:
! case SUBREG:
! case CONST_INT:
! case CONST_DOUBLE:
! case CONST_VECTOR:
! case CALL:
! return 0;
!
! default:
! break;
! }
!
! /* If this is a valid operand, we are OK. If it's VOIDmode, we aren't. */
! if (general_operand (x, GET_MODE (x)))
! return 1;
! else if (GET_MODE (x) == VOIDmode)
return 0;
!
! /* Otherwise, check if we can make a valid insn from it. First initialize
! our test insn if we haven't already. */
! if (test_insn == 0)
! {
! test_insn
! = make_insn_raw (gen_rtx_SET (VOIDmode,
! gen_rtx_REG (word_mode,
! FIRST_PSEUDO_REGISTER * 2),
! const0_rtx));
! NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0;
! ggc_add_rtx_root (&test_insn, 1);
! }
!
! /* Now make an insn like the one we would make when GCSE'ing and see if
! valid. */
! PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
! SET_SRC (PATTERN (test_insn)) = x;
! return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0
! && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode)));
}
/* Return non-zero if the operands of expression X are unchanged from the
--- 1312,1324 ----
want_to_gcse_p (x)
rtx x;
{
! if (GET_CODE (x) == CALL)
return 0;
! if (GET_MODE (x) == VOIDmode)
! return 0;
! if (CONSTANT_P (x))
! return 0;
! return (rtx_cost (x, SET) != 0);
}
/* Return non-zero if the operands of expression X are unchanged from the
*************** insert_expr_in_table (x, mode, insn, ant
*** 1997,2002 ****
--- 1965,1971 ----
/* Set the fields of the expr element. */
cur_expr->expr = x;
+ cur_expr->insn = insn;
cur_expr->bitmap_index = n_exprs++;
cur_expr->next_same_hash = NULL;
cur_expr->antic_occr = NULL;
*************** insert_set_in_table (x, insn)
*** 2122,2127 ****
--- 2091,2097 ----
We must copy X because it can be modified when copy propagation is
performed on its operands. */
cur_expr->expr = copy_rtx (x);
+ cur_expr->insn = insn;
cur_expr->bitmap_index = n_sets++;
cur_expr->next_same_hash = NULL;
cur_expr->antic_occr = NULL;
*************** hash_scan_set (pat, insn, set_p)
*** 2183,2188 ****
--- 2153,2164 ----
unsigned int regno = REGNO (dest);
rtx tmp;
+ /* Avoid storing sets with REG_UNUSED. This prevents multiple set
+ insns passing single_set from confusing us. */
+
+ if (find_reg_note (insn, REG_UNUSED, dest))
+ return;
+
/* If this is a single set and we are doing constant propagation,
see if a REG_NOTE shows this equivalent to a constant. */
if (set_p && (note = find_reg_equal_equiv_note (insn)) != 0
*************** hash_scan_set (pat, insn, set_p)
*** 2200,2205 ****
--- 2176,2185 ----
&& !find_reg_note (insn, REG_EH_REGION, NULL_RTX)
/* Is SET_SRC something we want to gcse? */
&& want_to_gcse_p (src)
+ /* At the moment rest of GCSE pass expect all instructions to be
+ hoistable. In the future we will want to avoid this limitation
+ by teaching passes to first validate the transformation. */
+ && can_hoist_insn_p (insn, SET_DEST (pat), NULL)
/* Don't CSE a nop. */
&& ! set_noop_p (pat)
/* Don't GCSE if it has attached REG_EQUIV note.
*************** pre_expr_reaches_here_p (occr_bb, expr,
*** 4599,4659 ****
return rval;
}
-
- /* Given an expr, generate RTL which we can insert at the end of a BB,
- or on an edge. Set the block number of any insns generated to
- the value of BB. */
-
static rtx
! process_insert_insn (expr)
! struct expr *expr;
! {
! rtx reg = expr->reaching_reg;
! rtx exp = copy_rtx (expr->expr);
! rtx pat;
!
! start_sequence ();
!
! /* If the expression is something that's an operand, like a constant,
! just copy it to a register. */
! if (general_operand (exp, GET_MODE (reg)))
! emit_move_insn (reg, exp);
!
! /* Otherwise, make a new insn to compute this expression and make sure the
! insn will be recognized (this also adds any needed CLOBBERs). Copy the
! expression to make sure we don't have any sharing issues. */
! else if (insn_invalid_p (emit_insn (gen_rtx_SET (VOIDmode, reg, exp))))
! abort ();
!
! pat = gen_sequence ();
! end_sequence ();
!
! return pat;
! }
!
! /* Add EXPR to the end of basic block BB.
!
! This is used by both the PRE and code hoisting.
!
! For PRE, we want to verify that the expr is either transparent
! or locally anticipatable in the target block. This check makes
! no sense for code hoisting. */
!
! static void
! insert_insn_end_bb (expr, bb, pre)
! struct expr *expr;
basic_block bb;
- int pre;
{
rtx insn = bb->end;
- rtx new_insn;
- rtx reg = expr->reaching_reg;
- int regno = REGNO (reg);
- rtx pat;
- int i;
-
- pat = process_insert_insn (expr);
-
/* If the last insn is a jump, insert EXPR in front [taking care to
handle cc0, etc. properly]. Similary we need to care trapping
instructions in presence of non-call exceptions. */
--- 4579,4589 ----
return rval;
}
static rtx
! end_bb_insertion_point (bb)
basic_block bb;
{
rtx insn = bb->end;
/* If the last insn is a jump, insert EXPR in front [taking care to
handle cc0, etc. properly]. Similary we need to care trapping
instructions in presence of non-call exceptions. */
*************** insert_insn_end_bb (expr, bb, pre)
*** 4665,4688 ****
#ifdef HAVE_cc0
rtx note;
#endif
- /* It should always be the case that we can put these instructions
- anywhere in the basic block with performing PRE optimizations.
- Check this. */
- if (GET_CODE (insn) == INSN && pre
- && !TEST_BIT (antloc[bb->index], expr->bitmap_index)
- && !TEST_BIT (transp[bb->index], expr->bitmap_index))
- abort ();
-
/* If this is a jump table, then we can't insert stuff here. Since
! we know the previous real insn must be the tablejump, we insert
! the new instruction just before the tablejump. */
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
insn = prev_real_insn (insn);
#ifdef HAVE_cc0
/* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
! if cc0 isn't set. */
note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
if (note)
insn = XEXP (note, 0);
--- 4595,4610 ----
#ifdef HAVE_cc0
rtx note;
#endif
/* If this is a jump table, then we can't insert stuff here. Since
! we know the previous real insn must be the tablejump, we insert
! the new instruction just before the tablejump. */
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
insn = prev_real_insn (insn);
#ifdef HAVE_cc0
/* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
! if cc0 isn't set. */
note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
if (note)
insn = XEXP (note, 0);
*************** insert_insn_end_bb (expr, bb, pre)
*** 4696,4702 ****
}
#endif
/* FIXME: What if something in cc0/jump uses value set in new insn? */
! new_insn = emit_insn_before (pat, insn);
}
/* Likewise if the last insn is a call, as will happen in the presence
--- 4618,4624 ----
}
#endif
/* FIXME: What if something in cc0/jump uses value set in new insn? */
! return PREV_INSN (insn);
}
/* Likewise if the last insn is a call, as will happen in the presence
*************** insert_insn_end_bb (expr, bb, pre)
*** 4705,4766 ****
&& (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL)))
{
/* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
! we search backward and place the instructions before the first
! parameter is loaded. Do this for everyone for consistency and a
! presumtion that we'll get better code elsewhere as well.
!
! It should always be the case that we can put these instructions
! anywhere in the basic block with performing PRE optimizations.
! Check this. */
!
! if (pre
! && !TEST_BIT (antloc[bb->index], expr->bitmap_index)
! && !TEST_BIT (transp[bb->index], expr->bitmap_index))
! abort ();
/* Since different machines initialize their parameter registers
! in different orders, assume nothing. Collect the set of all
! parameter registers. */
insn = find_first_parameter_load (insn, bb->head);
/* If we found all the parameter loads, then we want to insert
! before the first parameter load.
! If we did not find all the parameter loads, then we might have
! stopped on the head of the block, which could be a CODE_LABEL.
! If we inserted before the CODE_LABEL, then we would be putting
! the insn in the wrong basic block. In that case, put the insn
! after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
! while (GET_CODE (insn) == CODE_LABEL
! || NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
! new_insn = emit_insn_before (pat, insn);
}
else
! new_insn = emit_insn_after (pat, insn);
/* Keep block number table up to date.
Note, PAT could be a multiple insn sequence, we have to make
sure that each insn in the sequence is handled. */
! if (GET_CODE (pat) == SEQUENCE)
! {
! for (i = 0; i < XVECLEN (pat, 0); i++)
! {
! rtx insn = XVECEXP (pat, 0, i);
! if (INSN_P (insn))
! add_label_notes (PATTERN (insn), new_insn);
!
! note_stores (PATTERN (insn), record_set_info, insn);
! }
! }
! else
! {
! add_label_notes (pat, new_insn);
!
! /* Keep register set table up to date. */
! record_one_set (regno, new_insn);
! }
gcse_create_count++;
--- 4627,4686 ----
&& (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL)))
{
/* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
! we search backward and place the instructions before the first
! parameter is loaded. Do this for everyone for consistency and a
! presumtion that we'll get better code elsewhere as well. */
/* Since different machines initialize their parameter registers
! in different orders, assume nothing. Collect the set of all
! parameter registers. */
insn = find_first_parameter_load (insn, bb->head);
/* If we found all the parameter loads, then we want to insert
! before the first parameter load.
! If we did not find all the parameter loads, then we might have
! stopped on the head of the block, which could be a CODE_LABEL.
! If we inserted before the CODE_LABEL, then we would be putting
! the insn in the wrong basic block. In that case, put the insn
! after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
! while (GET_CODE (insn) == CODE_LABEL || NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
! return PREV_INSN (insn);
}
else
! return PREV_INSN (insn);
! }
!
! /* Add EXPR to the end of basic block BB.
!
! This is used by both the PRE and code hoisting.
!
! For PRE, we want to verify that the expr is either transparent
! or locally anticipatable in the target block. This check makes
! no sense for code hoisting. */
!
! static void
! insert_insn_end_bb (expr, bb)
! struct expr *expr;
! basic_block bb;
! {
! rtx insn = bb->end;
! rtx new_insn;
! rtx reg = expr->reaching_reg;
! int regno = REGNO (reg);
! rtx after;
!
! after = end_bb_insertion_point (bb);
!
! new_insn = hoist_insn_after (expr->insn, after,
! SET_DEST (single_set (expr->insn)), reg);
/* Keep block number table up to date.
Note, PAT could be a multiple insn sequence, we have to make
sure that each insn in the sequence is handled. */
! note_stores (PATTERN (new_insn), record_set_info, insn);
gcse_create_count++;
*************** insert_insn_end_bb (expr, bb, pre)
*** 4773,4778 ****
--- 4693,4743 ----
}
}
+ /* Return true if we can hoist EXPR to the end of BB.
+
+ This is used by both the PRE and code hoisting. */
+
+ static bool
+ can_insert_insn_end_bb_p (expr, bb)
+ struct expr *expr;
+ basic_block bb;
+ {
+ rtx last = bb->end;
+ struct propagate_block_info *pbi;
+ regset live;
+ rtx insn;
+ bool retval;
+ regset_head live_head;
+
+ if (simplejump_p (last))
+ last = PREV_INSN (last);
+
+ if (end_bb_insertion_point (bb) == last
+ || !bb->global_live_at_end)
+ return can_hoist_insn_p (expr->insn, SET_DEST (single_set (expr->insn)),
+ bb->global_live_at_end);
+
+ live = INITIALIZE_REG_SET (live_head);
+ pbi = init_propagate_block_info (bb, live, NULL, NULL, PROP_EQUAL_NOTES);
+ COPY_REG_SET (live, bb->global_live_at_end);
+ for (insn = bb->end; insn != last; insn = PREV_INSN (insn))
+ propagate_one_insn (pbi, insn);
+ retval = can_hoist_insn_p (expr->insn, SET_DEST (single_set (expr->insn)),
+ live);
+ free_propagate_block_info (pbi);
+ FREE_REG_SET (live);
+ return retval;
+ }
+
+ static bool
+ can_insert_insn_edge_p (expr, e)
+ struct expr *expr;
+ edge e;
+ {
+ return can_hoist_insn_p (expr->insn, SET_DEST (single_set (expr->insn)),
+ e->dest->global_live_at_start);
+ }
+
/* Insert partially redundant expressions on edges in the CFG to make
the expressions fully redundant. */
*************** pre_edge_insert (edge_list, index_map)
*** 4817,4823 ****
reach the deleted occurrence in BB. */
if (!TEST_BIT (inserted[e], j))
{
- rtx insn;
edge eg = INDEX_EDGE (edge_list, e);
/* We can't insert anything on an abnormal and
--- 4782,4787 ----
*************** pre_edge_insert (edge_list, index_map)
*** 4828,4838 ****
now. */
if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
! insert_insn_end_bb (index_map[j], bb, 0);
else
{
! insn = process_insert_insn (index_map[j]);
! insert_insn_on_edge (insn, eg);
}
if (gcse_file)
--- 4792,4813 ----
now. */
if ((eg->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
! {
! #ifdef ENABLE_CHECKING
! if (!can_insert_insn_end_bb_p (index_map[j], bb))
! abort ();
! #endif
! insert_insn_end_bb (index_map[j], bb);
! }
else
{
! #ifdef ENABLE_CHECKING
! if (!can_insert_insn_edge_p (index_map[j], eg))
! abort ();
! #endif
! hoist_insn_to_edge (expr->insn, eg,
! SET_DEST (single_set (expr->insn)),
! expr->reaching_reg);
}
if (gcse_file)
*************** hoist_code ()
*** 5814,5850 ****
if (!occr)
abort ();
insn = occr->insn;
set = single_set (insn);
if (! set)
abort ();
! /* Create a pseudo-reg to store the result of reaching
! expressions into. Get the mode for the new pseudo
! from the mode of the original destination pseudo. */
! if (expr->reaching_reg == NULL)
! expr->reaching_reg
! = gen_reg_rtx (GET_MODE (SET_DEST (set)));
!
! /* In theory this should never fail since we're creating
! a reg->reg copy.
!
! However, on the x86 some of the movXX patterns
! actually contain clobbers of scratch regs. This may
! cause the insn created by validate_change to not
! match any pattern and thus cause validate_change to
! fail. */
! if (validate_change (insn, &SET_SRC (set),
! expr->reaching_reg, 0))
{
! occr->deleted_p = 1;
! if (!insn_inserted_p)
! {
! insert_insn_end_bb (index_map[i], bb, 0);
! insn_inserted_p = 1;
! }
}
}
}
}
--- 5807,5844 ----
if (!occr)
abort ();
+ if (occr->deleted_p)
+ continue;
+
insn = occr->insn;
set = single_set (insn);
if (! set)
abort ();
! if (!insn_inserted_p)
{
! if (!can_insert_insn_end_bb_p (index_map[i], bb))
! {
! if (rtl_dump_file)
! fprintf (rtl_dump_file, "Can not hoist insn %i\n", i);
! break;
! }
!
! /* Create a pseudo-reg to store the result of reaching
! expressions into. Get the mode for the new pseudo
! from the mode of the original destination pseudo. */
! if (expr->reaching_reg == NULL)
! expr->reaching_reg
! = gen_reg_rtx (GET_MODE (SET_DEST (set)));
!
! insert_insn_end_bb (index_map[i], bb);
! insn_inserted_p = 1;
}
+
+ gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
+ delete_insn (insn);
+ occr->deleted_p = 1;
}
}
}
More information about the Gcc-patches
mailing list