/* RTL factoring (sequence abstraction).
- Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "tree-flow.h"
#include "timevar.h"
#include "output.h"
+#include "df.h"
+#include "addresses.h"
/* Sequence abstraction:
TODO:
- Use REG_ALLOC_ORDER when choosing link register.
- Handle JUMP_INSNs. Also handle volatile function calls (handle them
- simmilar to unconditional jumps.)
+ similar to unconditional jumps.)
- Test command line option -fpic.
*/
struct seq_block_def *next_seq_block;
} *seq_block;
-/* Contains same sequence candidates for futher searching. */
+/* Contains same sequence candidates for further searching. */
typedef struct hash_bucket_def
{
/* The hash value of the group. */
/* List of sequence candidates. */
htab_t seq_candidates;
} *p_hash_bucket;
+typedef const struct hash_bucket_def *const_p_hash_bucket;
/* Contains the last insn of the sequence, and its index value. */
typedef struct hash_elem_def
/* The cached length of the insn. */
int length;
} *p_hash_elem;
+typedef const struct hash_elem_def *const_p_hash_elem;
/* The list of same sequence candidates. */
static htab_t hash_buckets;
tmp_bucket.hash = compute_hash (insn);
/* Select the hash group. */
- bucket = htab_find (hash_buckets, &tmp_bucket);
+ bucket = (p_hash_bucket) htab_find (hash_buckets, &tmp_bucket);
if (bucket)
{
tmp_elem.insn = insn;
/* Select the insn. */
- elem = htab_find (bucket->seq_candidates, &tmp_elem);
+ elem = (p_hash_elem) htab_find (bucket->seq_candidates, &tmp_elem);
/* If INSN is parsed the cost will be the cached length. */
if (elem)
htab_iterator hti0, hti1, hti2;
p_hash_bucket hash_bucket;
p_hash_elem e0, e1;
-#ifdef STACK_REGS
+#if defined STACK_REGS || defined HAVE_cc0
basic_block bb;
- bitmap_head stack_reg_live;
+ bitmap_head dont_collect;
/* Extra initialization step to ensure that no stack registers (if present)
- are live across abnormal edges. Set a flag in STACK_REG_LIVE for an insn
- if a stack register is live after the insn. */
- bitmap_initialize (&stack_reg_live, NULL);
+ or cc0 code (if present) are live across abnormal edges.
+ Set a flag in DONT_COLLECT for an insn if a stack register is live
+ after the insn or the insn is cc0 setter or user. */
+ bitmap_initialize (&dont_collect, NULL);
+#ifdef STACK_REGS
FOR_EACH_BB (bb)
{
regset_head live;
- struct propagate_block_info *pbi;
rtx insn;
+ rtx prev;
/* Initialize liveness propagation. */
INIT_REG_SET (&live);
- COPY_REG_SET (&live, bb->il.rtl->global_live_at_end);
- pbi = init_propagate_block_info (bb, &live, NULL, NULL, 0);
+ bitmap_copy (&live, DF_LR_OUT (bb));
+ df_simulate_artificial_refs_at_end (bb, &live);
/* Propagate liveness info and mark insns where a stack reg is live. */
insn = BB_END (bb);
- while (1)
+ for (insn = BB_END (bb); ; insn = prev)
{
- int reg;
- for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
- {
- if (REGNO_REG_SET_P (&live, reg))
- {
- bitmap_set_bit (&stack_reg_live, INSN_UID (insn));
- break;
- }
- }
-
- if (insn == BB_HEAD (bb))
- break;
- insn = propagate_one_insn (pbi, insn);
+ prev = PREV_INSN (insn);
+ if (INSN_P (insn))
+ {
+ int reg;
+ for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
+ {
+ if (REGNO_REG_SET_P (&live, reg))
+ {
+ bitmap_set_bit (&dont_collect, INSN_UID (insn));
+ break;
+ }
+ }
+
+ }
+ if (insn == BB_HEAD (bb))
+ break;
+ df_simulate_one_insn (bb, insn, &live);
+ insn = prev;
}
/* Free unused data. */
CLEAR_REG_SET (&live);
- free_propagate_block_info (pbi);
}
#endif
+#ifdef HAVE_cc0
+ /* Mark CC0 setters and users as ineligible for collection into sequences.
+ This is an over-conservative fix, since it is OK to include
+ a cc0_setter, but only if we also include the corresponding cc0_user,
+ and vice versa. */
+ FOR_EACH_BB (bb)
+ {
+ rtx insn;
+ rtx next_tail;
+
+ next_tail = NEXT_INSN (BB_END (bb));
+
+ for (insn = BB_HEAD (bb); insn != next_tail; insn = NEXT_INSN (insn))
+ {
+ if (INSN_P (insn) && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
+ bitmap_set_bit (&dont_collect, INSN_UID (insn));
+ }
+ }
+#endif
+
+#endif /* defined STACK_REGS || defined HAVE_cc0 */
+
/* Initialize PATTERN_SEQS to empty. */
pattern_seqs = 0;
FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem,
hti2)
if (e0 != e1
-#ifdef STACK_REGS
- && !bitmap_bit_p (&stack_reg_live, INSN_UID (e0->insn))
- && !bitmap_bit_p (&stack_reg_live, INSN_UID (e1->insn))
+#if defined STACK_REGS || defined HAVE_cc0
+ && !bitmap_bit_p (&dont_collect, INSN_UID (e0->insn))
+ && !bitmap_bit_p (&dont_collect, INSN_UID (e1->insn))
#endif
)
match_seqs (e0, e1);
-#ifdef STACK_REGS
+#if defined STACK_REGS || defined HAVE_cc0
/* Free unused data. */
- bitmap_clear (&stack_reg_live);
+ bitmap_clear (&dont_collect);
#endif
}
basic_block bb;
regset_head live;
HARD_REG_SET hlive;
- struct propagate_block_info *pbi;
rtx x;
int i;
/* Initialize liveness propagation. */
bb = BLOCK_FOR_INSN (insn);
INIT_REG_SET (&live);
- COPY_REG_SET (&live, bb->il.rtl->global_live_at_end);
- pbi = init_propagate_block_info (bb, &live, NULL, NULL, 0);
+ bitmap_copy (&live, DF_LR_OUT (bb));
+ df_simulate_artificial_refs_at_end (bb, &live);
/* Propagate until INSN if found. */
- for (x = BB_END (bb); x != insn;)
- x = propagate_one_insn (pbi, x);
+ for (x = BB_END (bb); x != insn; x = PREV_INSN (x))
+ df_simulate_one_insn (bb, x, &live);
/* Clear registers live after INSN. */
renumbered_reg_set_to_hard_reg_set (&hlive, &live);
/* Clear registers live in and before the sequence. */
for (i = 0; i < length;)
{
- rtx prev = propagate_one_insn (pbi, x);
+ rtx prev = PREV_INSN (x);
+ df_simulate_one_insn (bb, x, &live);
if (INSN_P (x))
{
}
/* Free unused data. */
- free_propagate_block_info (pbi);
CLEAR_REG_SET (&live);
}
#ifdef REGNO_OK_FOR_INDIRECT_JUMP_P
|| (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode))
#else
- || (!REGNO_MODE_OK_FOR_BASE_P (i, Pmode))
- || (!reg_class_subset_p (REGNO_REG_CLASS (i), BASE_REG_CLASS))
+ || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))
+ || (!reg_class_subset_p (REGNO_REG_CLASS (i),
+ base_reg_class (VOIDmode, MEM, SCRATCH)))
#endif
|| (hascall && call_used_regs[i])
- || (!call_used_regs[i] && !regs_ever_live[i]))
+ || (!call_used_regs[i] && !df_regs_ever_live_p (i)))
CLEAR_HARD_REG_BIT (linkregs, i);
/* Find an appropriate register to be used as the link register. */
}
/* Ensure that SB contains a seq_block with the appropriate length.
- Insert a new seq_block if neccessary. */
+ Insert a new seq_block if necessary. */
if (!seq_blocks || ((*mseq)->abstracted_length < seq_blocks->length))
{
sb = (seq_block) xmalloc (sizeof (struct seq_block_def));
/* Builds a symbol_ref for LABEL. */
static rtx
-gen_symbol_ref_rtx_for_label (rtx label)
+gen_symbol_ref_rtx_for_label (const_rtx label)
{
char name[20];
rtx sym;
return sym;
}
+/* Splits basic block at the requested insn and rebuilds dataflow. */
+
+static basic_block
+split_block_and_df_analyze (basic_block bb, rtx insn)
+{
+ basic_block next;
+ next = split_block (bb, insn)->dest;
+ df_analyze ();
+ return next;
+}
+
/* Ensures that INSN is the last insn in its block and returns the block label
of the next block. */
if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR))
return block_label (bb->next_bb);
else
- return block_label (split_block (bb, insn)->dest);
+ return block_label (split_block_and_df_analyze (bb, insn));
}
/* Ensures that the last insns of the best pattern and its matching sequences
for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
{
block_label_after (mseq->insn);
- IOR_REG_SET (BLOCK_FOR_INSN (pattern_seqs->insn)->
- il.rtl->global_live_at_end,
- BLOCK_FOR_INSN (mseq->insn)->il.rtl->global_live_at_end);
+ IOR_REG_SET (df_get_live_out (BLOCK_FOR_INSN (pattern_seqs->insn)),
+ df_get_live_out (BLOCK_FOR_INSN (mseq->insn)));
}
}
}
-/* Splits the best pattern sequence accoring to SEQ_BLOCKS. Emits pseudo-call
+/* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
and -return insns before and after the sequence. */
static void
/* Emit an indirect jump via the link register after the sequence acting
as the return insn. Also emit a barrier and update the basic block. */
- retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
- BB_END (bb));
+ if (!find_reg_note (BB_END (bb), REG_NORETURN, NULL))
+ retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
+ BB_END (bb));
emit_barrier_after (BB_END (bb));
/* Replace all outgoing edges with a new one to the block of RETLABEL. */
for (; i < sb->length; i++)
insn = prev_insn_in_block (insn);
- sb->label = block_label (split_block (bb, insn)->dest);
+ sb->label = block_label (split_block_and_df_analyze (bb, insn));
}
/* Emit an insn saving the return address to the link register before the
gen_symbol_ref_rtx_for_label
(retlabel)), BB_END (bb));
/* Update liveness info. */
- SET_REGNO_REG_SET (bb->il.rtl->global_live_at_end,
+ SET_REGNO_REG_SET (df_get_live_out (bb),
REGNO (pattern_seqs->link_reg));
}
/* Delete the insns of the sequence. */
for (i = 0; i < sb->length; i++)
insn = prev_insn_in_block (insn);
- delete_basic_block (split_block (bb, insn)->dest);
+ delete_basic_block (split_block_and_df_analyze (bb, insn));
/* Emit an insn saving the return address to the link register
before the deleted sequence. */
BB_END (bb) = callinsn;
/* Maintain control flow and liveness information. */
- SET_REGNO_REG_SET (bb->il.rtl->global_live_at_end,
+ SET_REGNO_REG_SET (df_get_live_out (bb),
REGNO (pattern_seqs->link_reg));
emit_barrier_after (BB_END (bb));
make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0);
- IOR_REG_SET (bb->il.rtl->global_live_at_end,
- BLOCK_FOR_INSN (sb->label)->il.rtl->global_live_at_start);
+ IOR_REG_SET (df_get_live_out (bb),
+ df_get_live_in (BLOCK_FOR_INSN (sb->label)));
make_edge (BLOCK_FOR_INSN (seq_blocks->label),
BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
free_seq_blocks ();
/* Record the usage of the link register. */
- regs_ever_live[REGNO (pattern_seqs->link_reg)] = 1;
+ df_set_regs_ever_live (REGNO (pattern_seqs->link_reg), true);
/* Remove the best pattern sequence. */
bestpseq = pattern_seqs;
static unsigned int
htab_hash_bucket (const void *p)
{
- p_hash_bucket bucket = (p_hash_bucket) p;
+ const_p_hash_bucket bucket = (const_p_hash_bucket) p;
return bucket->hash;
}
static unsigned int
htab_hash_elem (const void *p)
{
- p_hash_elem elem = (p_hash_elem) p;
+ const_p_hash_elem elem = (const_p_hash_elem) p;
return htab_hash_pointer (elem->insn);
}
tmp_bucket.hash = compute_hash (insn);
/* Select the hash group. */
- bucket = htab_find (hash_buckets, &tmp_bucket);
+ bucket = (p_hash_bucket) htab_find (hash_buckets, &tmp_bucket);
if (!bucket)
{
rtl_seqabstr (void)
{
int iter;
+ df_set_flags (DF_LR_RUN_DCE);
+ df_analyze ();
/* Create a hash list for COLLECT_PATTERN_SEQS. */
hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket ,
/* Iterate until there are no sequences to abstract. */
for (iter = 1;; iter++)
{
- /* Recompute gain for sequences if neccessary and select sequence with
+ /* Recompute gain for sequences if necessary and select sequence with
biggest gain. */
recompute_gain ();
if (!pattern_seqs)
/* Cleanup hash tables. */
htab_delete (hash_buckets);
-
- if (iter > 1)
- {
- /* Update notes. */
- count_or_remove_death_notes (NULL, 1);
-
- life_analysis (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
- | PROP_KILL_DEAD_CODE);
-
- /* Extra cleanup. */
- cleanup_cfg (CLEANUP_EXPENSIVE |
- CLEANUP_UPDATE_LIFE |
- (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
- }
}
/* The gate function for TREE_OPT_PASS. */
/* The entry point of the sequence abstraction algorithm. */
-static void
+static unsigned int
rest_of_rtl_seqabstr (void)
{
- life_analysis (PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE | PROP_KILL_DEAD_CODE);
-
- cleanup_cfg (CLEANUP_EXPENSIVE |
- CLEANUP_UPDATE_LIFE |
- (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
-
/* Abstract out common insn sequences. */
rtl_seqabstr ();
+ return 0;
}
-struct tree_opt_pass pass_rtl_seqabstr = {
+struct rtl_opt_pass pass_rtl_seqabstr =
+{
+ {
+ RTL_PASS,
"seqabstr", /* name */
gate_rtl_seqabstr, /* gate */
rest_of_rtl_seqabstr, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
+ TODO_df_finish | TODO_verify_rtl_sharing |
TODO_dump_func |
- TODO_ggc_collect, /* todo_flags_finish */
- 'Q' /* letter */
+ TODO_ggc_collect /* todo_flags_finish */
+ }
};