/* Global common subexpression elimination/Partial redundancy elimination
and global constant/copy propagation for GNU compiler.
- Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
+ Free Software Foundation, Inc.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC 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 version.
+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
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
You should have received a copy of the GNU General Public License
-along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
/* TODO
- reordering of memory allocation and freeing to be more space efficient
#include "output.h"
#include "function.h"
#include "expr.h"
+#include "except.h"
#include "ggc.h"
#include "params.h"
+
#include "obstack.h"
-#include "df.h"
#define obstack_chunk_alloc gmalloc
#define obstack_chunk_free free
/* Non-zero if can_copy_p has been initialized. */
static int can_copy_init_p;
-/* Dataflow analyzer */
-struct df *df_analyzer;
-
-
struct reg_use {rtx reg_rtx; };
/* Hash table of expressions. */
{
struct expr * expr; /* Gcse expression reference for LM. */
rtx pattern; /* Pattern of this mem. */
- rtx loads; /* INSN list for where load appears */
- rtx stores; /* INSN list for where store appears */
+ rtx loads; /* INSN list of loads seen. */
+ rtx stores; /* INSN list of stores seen. */
struct ls_expr * next; /* Next in the list. */
int invalid; /* Invalid for some reason. */
int index; /* If it maps to a bitmap index. */
/* Bitmap containing one bit for each register in the program.
Used when performing GCSE to track which registers have been set since
the start of the basic block. */
-static sbitmap reg_set_bitmap;
+static regset reg_set_bitmap;
/* For each block, a bitmap of registers set in the block.
This is used by expr_killed_p and compute_transp.
/* Array, indexed by basic block number for a list of insns which modify
memory within that block. */
static rtx * modify_mem_list;
+bitmap modify_mem_list_set;
/* This array parallels modify_mem_list, but is kept canonicalized. */
static rtx * canon_modify_mem_list;
+bitmap canon_modify_mem_list_set;
/* Various variables for statistics gathering. */
/* Memory used in a pass.
struct null_pointer_info
{
/* The basic block being processed. */
- int current_block;
+ basic_block current_block;
/* The first register to be handled in this pass. */
unsigned int min_reg;
/* One greater than the last register to be handled in this pass. */
static int classic_gcse PARAMS ((void));
static int one_classic_gcse_pass PARAMS ((int));
static void invalidate_nonnull_info PARAMS ((rtx, rtx, void *));
-static void delete_null_pointer_checks_1 PARAMS ((varray_type *, unsigned int *,
+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 void compute_ld_motion_mems PARAMS ((void));
static void trim_ld_motion_mems PARAMS ((void));
static void update_ld_motion_stores PARAMS ((struct expr *));
-static int store_ops_ok PARAMS ((rtx, basic_block, rtx, int));
+static void reg_set_info PARAMS ((rtx, rtx, void *));
+static int store_ops_ok PARAMS ((rtx, basic_block));
static void find_moveable_store PARAMS ((rtx));
static int compute_store_table PARAMS ((void));
static int load_kills_store PARAMS ((rtx, rtx));
static int find_loads PARAMS ((rtx, rtx));
static int store_killed_in_insn PARAMS ((rtx, rtx));
-static int store_killed_after PARAMS ((rtx, rtx, basic_block, int));
+static int store_killed_after PARAMS ((rtx, rtx, basic_block));
static int store_killed_before PARAMS ((rtx, rtx, basic_block));
static void build_store_vectors PARAMS ((void));
static void insert_insn_start_bb PARAMS ((rtx, basic_block));
basic_block));
static void free_store_memory PARAMS ((void));
static void store_motion PARAMS ((void));
+static void free_insn_expr_list_list PARAMS ((rtx *));
+static void clear_modify_mem_tables PARAMS ((void));
+static void free_modify_mem_tables PARAMS ((void));
+static rtx gcse_emit_move_after PARAMS ((rtx, rtx, rtx));
\f
/* Entry point for global common subexpression elimination.
F is the first instruction in the function. */
if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
{
if (warn_disabled_optimization)
- warning ("GCSE disabled: %d > 1000 basic blocks and %d >= 20 edges/basic block",
- n_basic_blocks, n_edges / n_basic_blocks);
+ warning ("GCSE disabled: %d > 1000 basic blocks and %d >= 20 edges/basic block",
+ n_basic_blocks, n_edges / n_basic_blocks);
return 0;
}
basic blocks. */
if (changed)
{
- int i;
-
- for (i = 0; i < orig_bb_count; i++)
- {
- if (modify_mem_list[i])
- free_INSN_LIST_list (modify_mem_list + i);
- if (canon_modify_mem_list[i])
- free_INSN_LIST_list (canon_modify_mem_list + i);
- }
+ free_modify_mem_tables ();
modify_mem_list
- = (rtx *) gmalloc (n_basic_blocks * sizeof (rtx *));
+ = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
canon_modify_mem_list
- = (rtx *) gmalloc (n_basic_blocks * sizeof (rtx *));
- memset ((char *) modify_mem_list, 0, n_basic_blocks * sizeof (rtx *));
- memset ((char *) canon_modify_mem_list, 0, n_basic_blocks * sizeof (rtx *));
+ = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
+ memset ((char *) modify_mem_list, 0, last_basic_block * sizeof (rtx));
+ memset ((char *) canon_modify_mem_list, 0, last_basic_block * sizeof (rtx));
orig_bb_count = n_basic_blocks;
}
free_reg_set_mem ();
end_alias_analysis ();
allocate_reg_info (max_reg_num (), FALSE, FALSE);
- if (!optimize_size && flag_gcse_sm)
+ /* Store motion disabled until it is fixed. */
+ if (0 && !optimize_size && flag_gcse_sm)
store_motion ();
/* Record where pseudo-registers are set. */
return run_jump_opt_after_gcse;
{
int i;
#ifndef AVOID_CCMODE_COPIES
- rtx reg,insn;
+ rtx reg, insn;
#endif
memset (can_copy_p, 0, NUM_MACHINE_MODES);
alloc_gcse_mem (f)
rtx f;
{
- int i,n;
+ int i, n;
rtx insn;
/* Find the largest UID and create a mapping from UIDs to CUIDs.
CUID_INSN (i++) = insn;
/* Allocate vars to track sets of regs. */
- reg_set_bitmap = (sbitmap) sbitmap_alloc (max_gcse_regno);
+ reg_set_bitmap = BITMAP_XMALLOC ();
/* Allocate vars to track sets of regs, memory per block. */
- reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks,
+ reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (last_basic_block,
max_gcse_regno);
/* Allocate array to keep a list of insns which modify memory in each
basic block. */
- modify_mem_list = (rtx *) gmalloc (n_basic_blocks * sizeof (rtx *));
- canon_modify_mem_list = (rtx *) gmalloc (n_basic_blocks * sizeof (rtx *));
- memset ((char *) modify_mem_list, 0, n_basic_blocks * sizeof (rtx *));
- memset ((char *) canon_modify_mem_list, 0, n_basic_blocks * sizeof (rtx *));
+ modify_mem_list = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
+ canon_modify_mem_list = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
+ memset ((char *) modify_mem_list, 0, last_basic_block * sizeof (rtx));
+ memset ((char *) canon_modify_mem_list, 0, last_basic_block * sizeof (rtx));
+ modify_mem_list_set = BITMAP_XMALLOC ();
+ canon_modify_mem_list_set = BITMAP_XMALLOC ();
}
/* Free memory allocated by alloc_gcse_mem. */
free (uid_cuid);
free (cuid_insn);
- free (reg_set_bitmap);
+ BITMAP_XFREE (reg_set_bitmap);
sbitmap_vector_free (reg_set_in_block);
- /* re-Cache any INSN_LIST nodes we have allocated. */
- {
- int i;
-
- for (i = 0; i < n_basic_blocks; i++)
- {
- if (modify_mem_list[i])
- free_INSN_LIST_list (modify_mem_list + i);
- if (canon_modify_mem_list[i])
- free_INSN_LIST_list (canon_modify_mem_list + i);
- }
-
- free (modify_mem_list);
- free (canon_modify_mem_list);
- modify_mem_list = 0;
- canon_modify_mem_list = 0;
- }
+ free_modify_mem_tables ();
+ BITMAP_XFREE (modify_mem_list_set);
+ BITMAP_XFREE (canon_modify_mem_list_set);
}
/* Many of the global optimization algorithms work by solving dataflow
if (transp)
{
if (setp)
- sbitmap_vector_zero (transp, n_basic_blocks);
+ sbitmap_vector_zero (transp, last_basic_block);
else
- sbitmap_vector_ones (transp, n_basic_blocks);
+ sbitmap_vector_ones (transp, last_basic_block);
}
if (comp)
- sbitmap_vector_zero (comp, n_basic_blocks);
+ sbitmap_vector_zero (comp, last_basic_block);
if (antloc)
- sbitmap_vector_zero (antloc, n_basic_blocks);
+ sbitmap_vector_zero (antloc, last_basic_block);
/* We use the same code for cprop, pre and hoisting. For cprop
we care about the set hash table, for pre and hoisting we
= (struct reg_set **) grealloc ((char *) reg_set_table,
new_size * sizeof (struct reg_set *));
memset ((char *) (reg_set_table + reg_set_table_size), 0,
- (new_size - reg_set_table_size) * sizeof (struct reg_set *));
+ (new_size - reg_set_table_size) * sizeof (struct reg_set *));
reg_set_table_size = new_size;
}
\f
/* Hash table support. */
-/* For each register, the cuid of the first/last insn in the block to set it,
- or -1 if not set. */
+/* For each register, the cuid of the first/last insn in the block
+ that set it, or -1 if not set. */
#define NEVER_SET -1
-static int *reg_first_set;
-static int *reg_last_set;
+
+struct reg_avail_info
+{
+ basic_block last_bb;
+ int first_set;
+ int last_set;
+};
+
+static struct reg_avail_info *reg_avail_info;
+static basic_block current_bb;
/* See whether X, the source of a set, is something we want to consider for
case SUBREG:
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case CALL:
return 0;
switch (code)
{
case REG:
- if (avail_p)
- return (reg_last_set[REGNO (x)] == NEVER_SET
- || reg_last_set[REGNO (x)] < INSN_CUID (insn));
- else
- return (reg_first_set[REGNO (x)] == NEVER_SET
- || reg_first_set[REGNO (x)] >= INSN_CUID (insn));
+ {
+ struct reg_avail_info *info = ®_avail_info[REGNO (x)];
+
+ if (info->last_bb != current_bb)
+ return 1;
+ if (avail_p)
+ return info->last_set < INSN_CUID (insn);
+ else
+ return info->first_set >= INSN_CUID (insn);
+ }
case MEM:
- if (load_killed_in_block_p (BLOCK_FOR_INSN (insn), INSN_CUID (insn),
+ if (load_killed_in_block_p (current_bb, INSN_CUID (insn),
x, avail_p))
return 0;
else
case CONST:
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
elsewhere. */
if (GET_CODE (dest) != MEM)
return;
+
/* If we are setting a MEM in our list of specially recognized MEMs,
don't mark as killed this time. */
gcse_mems_conflict_p = 1;
return;
}
+
if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand,
rtx_addr_varies_p))
gcse_mems_conflict_p = 1;
const char *ps;
{
unsigned hash = 0;
- const unsigned char *p = (const unsigned char *)ps;
+ const unsigned char *p = (const unsigned char *) ps;
if (p)
while (*p)
+ (unsigned int) CONST_DOUBLE_HIGH (x));
return hash;
+ case CONST_VECTOR:
+ {
+ int units;
+ rtx elt;
+
+ units = CONST_VECTOR_NUNITS (x);
+
+ for (i = 0; i < units; ++i)
+ {
+ elt = CONST_VECTOR_ELT (x, i);
+ hash += hash_expr_1 (elt, GET_MODE (elt), do_not_record_p);
+ }
+
+ return hash;
+ }
+
/* Assume there is only one rtx object for any given label. */
case LABEL_REF:
/* We don't hash on the address of the CODE_LABEL to avoid bootstrap
}
hash += (unsigned int) MEM;
- hash += MEM_ALIAS_SET (x);
+ /* We used alias set for hashing, but this is not good, since the alias
+ set may differ in -fprofile-arcs and -fbranch-probabilities compilation
+ causing the profiles to fail to match. */
x = XEXP (x, 0);
goto repeat;
hash += hash_string_1 (XSTR (x, i));
else if (fmt[i] == 'i')
hash += (unsigned int) XINT (x, i);
- else if (fmt[i] == 't');
else
abort ();
}
expr_equiv_p (x, y)
rtx x, y;
{
- register int i, j;
- register enum rtx_code code;
- register const char *fmt;
+ int i, j;
+ enum rtx_code code;
+ const char *fmt;
if (x == y)
return 1;
break;
case '0':
- case 't':
break;
-
+
default:
abort ();
}
- }
+ }
return 1;
}
&& regno >= FIRST_PSEUDO_REGISTER
/* Don't GCSE something if we can't do a reg/reg copy. */
&& can_copy_p [GET_MODE (dest)]
+ /* GCSE commonly inserts instruction after the insn. We can't
+ do that easily for EH_REGION notes so disable GCSE on these
+ for now. */
+ && !find_reg_note (insn, REG_EH_REGION, NULL_RTX)
/* Is SET_SRC something we want to gcse? */
&& want_to_gcse_p (src)
/* Don't CSE a nop. */
/* Don't GCSE if it has attached REG_EQUIV note.
At this point this only function parameters should have
REG_EQUIV notes and if the argument slot is used somewhere
- explicitely, it means address of parameter has been taken,
+ explicitly, it means address of parameter has been taken,
so we should not extend the lifetime of the pseudo. */
&& ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
|| GET_CODE (XEXP (note, 0)) != MEM))
this insn. */
int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn);
/* An expression is not available if its operands are
- subsequently modified, including this insn. */
- int avail_p = oprs_available_p (src, insn);
+ subsequently modified, including this insn. It's also not
+ available if this is a branch, because we can't insert
+ a set after the branch. */
+ int avail_p = (oprs_available_p (src, insn)
+ && ! JUMP_P (insn));
insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p);
}
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)]
&& REGNO (src) != regno)
- || GET_CODE (src) == CONST_INT
- || GET_CODE (src) == SYMBOL_REF
- || GET_CODE (src) == CONST_DOUBLE)
+ || CONSTANT_P (src))
/* A copy is not available if its src or dest is subsequently
modified. Here we want to search from INSN+1 on, but
oprs_available_p searches from INSN on. */
/* Record register first/last/block set information for REGNO in INSN.
- reg_first_set records the first place in the block where the register
+ first_set records the first place in the block where the register
is set and is used to compute "anticipatability".
- reg_last_set records the last place in the block where the register
+ last_set records the last place in the block where the register
is set and is used to compute "availability".
+ last_bb records the block for which first_set and last_set are
+ valid, as a quick test to invalidate them.
+
reg_set_in_block records whether the register is set in the block
and is used to compute "transparency". */
rtx insn;
int regno;
{
- if (reg_first_set[regno] == NEVER_SET)
- reg_first_set[regno] = INSN_CUID (insn);
+ struct reg_avail_info *info = ®_avail_info[regno];
+ int cuid = INSN_CUID (insn);
- reg_last_set[regno] = INSN_CUID (insn);
- SET_BIT (reg_set_in_block[BLOCK_NUM (insn)], regno);
+ info->last_set = cuid;
+ if (info->last_bb != current_bb)
+ {
+ info->last_bb = current_bb;
+ info->first_set = cuid;
+ SET_BIT (reg_set_in_block[current_bb->index], regno);
+ }
}
void * v_insn;
{
rtx dest_addr, insn;
+ int bb;
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
dest_addr = get_addr (XEXP (dest, 0));
dest_addr = canon_rtx (dest_addr);
insn = (rtx) v_insn;
+ bb = BLOCK_NUM (insn);
- canon_modify_mem_list[BLOCK_NUM (insn)] =
- alloc_INSN_LIST (dest_addr, canon_modify_mem_list[BLOCK_NUM (insn)]);
- canon_modify_mem_list[BLOCK_NUM (insn)] =
- alloc_INSN_LIST (dest, canon_modify_mem_list[BLOCK_NUM (insn)]);
+ canon_modify_mem_list[bb] =
+ alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
+ canon_modify_mem_list[bb] =
+ alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]);
+ bitmap_set_bit (canon_modify_mem_list_set, bb);
}
/* Record memory modification information for INSN. We do not actually care
record_last_mem_set_info (insn)
rtx insn;
{
+ int bb = BLOCK_NUM (insn);
+
/* load_killed_in_block_p will handle the case of calls clobbering
- everything. */
- modify_mem_list[BLOCK_NUM (insn)] =
- alloc_INSN_LIST (insn, modify_mem_list[BLOCK_NUM (insn)]);
+ everything. */
+ modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]);
+ bitmap_set_bit (modify_mem_list_set, bb);
if (GET_CODE (insn) == CALL_INSN)
{
/* Note that traversals of this loop (other than for free-ing)
will break after encountering a CALL_INSN. So, there's no
- need to insert a pair of items, as canon_list_insert does. */
- canon_modify_mem_list[BLOCK_NUM (insn)] =
- alloc_INSN_LIST (insn, canon_modify_mem_list[BLOCK_NUM (insn)]);
+ need to insert a pair of items, as canon_list_insert does. */
+ canon_modify_mem_list[bb] =
+ alloc_INSN_LIST (insn, canon_modify_mem_list[bb]);
+ bitmap_set_bit (canon_modify_mem_list_set, bb);
}
else
- note_stores (PATTERN (insn), canon_list_insert, (void*)insn );
+ note_stores (PATTERN (insn), canon_list_insert, (void*) insn);
}
/* Called from compute_hash_table via note_stores to handle one
compute_hash_table (set_p)
int set_p;
{
- int bb;
+ unsigned int i;
/* While we compute the hash table we also compute a bit array of which
registers are set in which blocks.
??? This isn't needed during const/copy propagation, but it's cheap to
compute. Later. */
- sbitmap_vector_zero (reg_set_in_block, n_basic_blocks);
+ sbitmap_vector_zero (reg_set_in_block, last_basic_block);
/* re-Cache any INSN_LIST nodes we have allocated. */
- {
- int i;
- for (i = 0; i < n_basic_blocks; i++)
- {
- if (modify_mem_list[i])
- free_INSN_LIST_list (modify_mem_list + i);
- if (canon_modify_mem_list[i])
- free_INSN_LIST_list (canon_modify_mem_list + i);
- }
- }
+ clear_modify_mem_tables ();
/* Some working arrays used to track first and last set in each block. */
- /* ??? One could use alloca here, but at some size a threshold is crossed
- beyond which one should use malloc. Are we at that threshold here? */
- reg_first_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
- reg_last_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
+ reg_avail_info = (struct reg_avail_info*)
+ gmalloc (max_gcse_regno * sizeof (struct reg_avail_info));
- for (bb = 0; bb < n_basic_blocks; bb++)
+ for (i = 0; i < max_gcse_regno; ++i)
+ reg_avail_info[i].last_bb = NULL;
+
+ FOR_EACH_BB (current_bb)
{
rtx insn;
unsigned int regno;
int in_libcall_block;
- unsigned int i;
/* First pass over the instructions records information used to
determine when registers and memory are first and last set.
??? hard-reg reg_set_in_block computation
could be moved to compute_sets since they currently don't change. */
- for (i = 0; i < max_gcse_regno; i++)
- reg_first_set[i] = reg_last_set[i] = NEVER_SET;
-
-
- for (insn = BLOCK_HEAD (bb);
- insn && insn != NEXT_INSN (BLOCK_END (bb));
+ for (insn = current_bb->head;
+ insn && insn != NEXT_INSN (current_bb->end);
insn = NEXT_INSN (insn))
{
-#ifdef NON_SAVING_SETJMP
- if (NON_SAVING_SETJMP && GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
- {
- for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- record_last_reg_set_info (insn, regno);
- continue;
- }
-#endif
-
if (! INSN_P (insn))
continue;
if (GET_CODE (insn) == CALL_INSN)
{
+ bool clobbers_all = false;
+#ifdef NON_SAVING_SETJMP
+ if (NON_SAVING_SETJMP
+ && find_reg_note (insn, REG_SETJMP, NULL_RTX))
+ clobbers_all = true;
+#endif
+
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ if (clobbers_all
+ || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
record_last_reg_set_info (insn, regno);
- if (! CONST_CALL_P (insn))
- record_last_mem_set_info (insn);
+ mark_call (insn);
}
note_stores (PATTERN (insn), record_last_set_info, insn);
/* The next pass builds the hash table. */
- for (insn = BLOCK_HEAD (bb), in_libcall_block = 0;
- insn && insn != NEXT_INSN (BLOCK_END (bb));
+ for (insn = current_bb->head, in_libcall_block = 0;
+ insn && insn != NEXT_INSN (current_bb->end);
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
- in_libcall_block = 1;
- else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
- in_libcall_block = 0;
- hash_scan_insn (insn, set_p, in_libcall_block);
- }
+ in_libcall_block = 1;
+ else if (set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ in_libcall_block = 0;
+ hash_scan_insn (insn, set_p, in_libcall_block);
+ if (!set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
+ in_libcall_block = 0;
+ }
}
- free (reg_first_set);
- free (reg_last_set);
-
- /* Catch bugs early. */
- reg_first_set = reg_last_set = 0;
+ free (reg_avail_info);
+ reg_avail_info = NULL;
}
/* Allocate space for the set hash table.
/* Initialize count of number of entries in hash table. */
n_sets = 0;
memset ((char *) set_hash_table, 0,
- set_hash_table_size * sizeof (struct expr *));
+ set_hash_table_size * sizeof (struct expr *));
compute_hash_table (1);
}
/* Initialize count of number of entries in hash table. */
n_exprs = 0;
memset ((char *) expr_hash_table, 0,
- expr_hash_table_size * sizeof (struct expr *));
+ expr_hash_table_size * sizeof (struct expr *));
compute_hash_table (0);
}
return expr;
}
+/* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node
+ types may be mixed. */
+
+static void
+free_insn_expr_list_list (listp)
+ rtx *listp;
+{
+ rtx list, next;
+
+ for (list = *listp; list ; list = next)
+ {
+ next = XEXP (list, 1);
+ if (GET_CODE (list) == EXPR_LIST)
+ free_EXPR_LIST_node (list);
+ else
+ free_INSN_LIST_node (list);
+ }
+
+ *listp = NULL;
+}
+
+/* Clear canon_modify_mem_list and modify_mem_list tables. */
+static void
+clear_modify_mem_tables ()
+{
+ int i;
+
+ EXECUTE_IF_SET_IN_BITMAP
+ (modify_mem_list_set, 0, i, free_INSN_LIST_list (modify_mem_list + i));
+ bitmap_clear (modify_mem_list_set);
+
+ EXECUTE_IF_SET_IN_BITMAP
+ (canon_modify_mem_list_set, 0, i,
+ free_insn_expr_list_list (canon_modify_mem_list + i));
+ bitmap_clear (canon_modify_mem_list_set);
+}
+
+/* Release memory used by modify_mem_list_set and canon_modify_mem_list_set. */
+
+static void
+free_modify_mem_tables ()
+{
+ clear_modify_mem_tables ();
+ free (modify_mem_list);
+ free (canon_modify_mem_list);
+ modify_mem_list = 0;
+ canon_modify_mem_list = 0;
+}
+
/* Reset tables used to keep track of what's still available [since the
start of the block]. */
{
/* Maintain a bitmap of which regs have been set since beginning of
the block. */
- sbitmap_zero (reg_set_bitmap);
+ CLEAR_REG_SET (reg_set_bitmap);
/* Also keep a record of the last instruction to modify memory.
For now this is very trivial, we only record whether any memory
location has been modified. */
- {
- int i;
-
- /* re-Cache any INSN_LIST nodes we have allocated. */
- for (i = 0; i < n_basic_blocks; i++)
- {
- if (modify_mem_list[i])
- free_INSN_LIST_list (modify_mem_list + i);
- if (canon_modify_mem_list[i])
- free_INSN_LIST_list (canon_modify_mem_list + i);
- }
- }
+ clear_modify_mem_tables ();
}
/* Return non-zero if the operands of X are not set before INSN in
case CONST:
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
return oprs_not_set_p (XEXP (x, 0), insn);
case REG:
- return ! TEST_BIT (reg_set_bitmap, REGNO (x));
+ return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
default:
break;
mark_call (insn)
rtx insn;
{
- if (! CONST_CALL_P (insn))
+ if (! CONST_OR_PURE_CALL_P (insn))
record_last_mem_set_info (insn);
}
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG)
- SET_BIT (reg_set_bitmap, REGNO (dest));
+ SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
else if (GET_CODE (dest) == MEM)
record_last_mem_set_info (insn);
clob = XEXP (clob, 0);
if (GET_CODE (clob) == REG)
- SET_BIT (reg_set_bitmap, REGNO (clob));
+ SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
else
record_last_mem_set_info (insn);
}
int n_blocks, n_insns;
{
rd_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
- sbitmap_vector_zero (rd_kill, n_basic_blocks);
+ sbitmap_vector_zero (rd_kill, n_blocks);
rd_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
- sbitmap_vector_zero (rd_gen, n_basic_blocks);
+ sbitmap_vector_zero (rd_gen, n_blocks);
reaching_defs = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
- sbitmap_vector_zero (reaching_defs, n_basic_blocks);
+ sbitmap_vector_zero (reaching_defs, n_blocks);
rd_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
- sbitmap_vector_zero (rd_out, n_basic_blocks);
+ sbitmap_vector_zero (rd_out, n_blocks);
}
/* Free reaching def variables. */
static void
compute_kill_rd ()
{
- int bb, cuid;
+ int cuid;
unsigned int regno;
int i;
+ basic_block bb;
/* For each block
For each set bit in `gen' of the block (i.e each insn which
Look at the linked list starting at reg_set_table[regx]
For each setting of regx in the linked list, which is not in
this block
- Set the bit in `kill' corresponding to that insn. */
- for (bb = 0; bb < n_basic_blocks; bb++)
+ Set the bit in `kill' corresponding to that insn. */
+ FOR_EACH_BB (bb)
for (cuid = 0; cuid < max_cuid; cuid++)
- if (TEST_BIT (rd_gen[bb], cuid))
+ if (TEST_BIT (rd_gen[bb->index], cuid))
{
rtx insn = CUID_INSN (cuid);
rtx pat = PATTERN (insn);
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
- handle_rd_kill_set (insn, regno, BASIC_BLOCK (bb));
+ handle_rd_kill_set (insn, regno, bb);
}
if (GET_CODE (pat) == PARALLEL)
&& GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
handle_rd_kill_set (insn,
REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
- BASIC_BLOCK (bb));
+ bb);
}
}
else if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == REG)
/* Each setting of this register outside of this block
must be marked in the set of kills in this block. */
- handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), BASIC_BLOCK (bb));
+ handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb);
}
}
static void
compute_rd ()
{
- int bb, changed, passes;
+ int changed, passes;
+ basic_block bb;
- for (bb = 0; bb < n_basic_blocks; bb++)
- sbitmap_copy (rd_out[bb] /*dst*/, rd_gen[bb] /*src*/);
+ FOR_EACH_BB (bb)
+ sbitmap_copy (rd_out[bb->index] /*dst*/, rd_gen[bb->index] /*src*/);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
- for (bb = 0; bb < n_basic_blocks; bb++)
+ FOR_EACH_BB (bb)
{
- sbitmap_union_of_preds (reaching_defs[bb], rd_out, bb);
- changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb],
- reaching_defs[bb], rd_kill[bb]);
+ sbitmap_union_of_preds (reaching_defs[bb->index], rd_out, bb->index);
+ changed |= sbitmap_union_of_diff_cg (rd_out[bb->index], rd_gen[bb->index],
+ reaching_defs[bb->index], rd_kill[bb->index]);
}
passes++;
}
int n_blocks, n_exprs;
{
ae_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
- sbitmap_vector_zero (ae_kill, n_basic_blocks);
+ sbitmap_vector_zero (ae_kill, n_blocks);
ae_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
- sbitmap_vector_zero (ae_gen, n_basic_blocks);
+ sbitmap_vector_zero (ae_gen, n_blocks);
ae_in = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
- sbitmap_vector_zero (ae_in, n_basic_blocks);
+ sbitmap_vector_zero (ae_in, n_blocks);
ae_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
- sbitmap_vector_zero (ae_out, n_basic_blocks);
+ sbitmap_vector_zero (ae_out, n_blocks);
}
static void
case CONST:
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
compute_ae_kill (ae_gen, ae_kill)
sbitmap *ae_gen, *ae_kill;
{
- int bb;
+ basic_block bb;
unsigned int i;
struct expr *expr;
- for (bb = 0; bb < n_basic_blocks; bb++)
+ FOR_EACH_BB (bb)
for (i = 0; i < expr_hash_table_size; i++)
for (expr = expr_hash_table[i]; expr; expr = expr->next_same_hash)
{
/* Skip EXPR if generated in this block. */
- if (TEST_BIT (ae_gen[bb], expr->bitmap_index))
+ if (TEST_BIT (ae_gen[bb->index], expr->bitmap_index))
continue;
- if (expr_killed_p (expr->expr, BASIC_BLOCK (bb)))
- SET_BIT (ae_kill[bb], expr->bitmap_index);
+ if (expr_killed_p (expr->expr, bb))
+ SET_BIT (ae_kill[bb->index], expr->bitmap_index);
}
}
\f
}
/* This wrapper for expr_reaches_here_p_work() is to ensure that any
- memory allocated for that function is returned. */
+ memory allocated for that function is returned. */
static int
expr_reaches_here_p (occr, expr, bb, check_self_loop)
int check_self_loop;
{
int rval;
- char *visited = (char *) xcalloc (n_basic_blocks, 1);
+ char *visited = (char *) xcalloc (last_basic_block, 1);
rval = expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited);
|| (((this_reg = reg_set_table[regnum_for_replacing]),
this_reg->next == NULL)
|| can_disregard_other_sets (&this_reg, insn, 0)))
- {
- use_src = 1;
- found_setting = 1;
- }
+ {
+ use_src = 1;
+ found_setting = 1;
+ }
}
if (!found_setting)
SET_DEST (expr_set)),
insn_computes_expr);
- /* Keep block number table up to date. */
- set_block_for_new_insns (new_insn, BLOCK_FOR_INSN (insn_computes_expr));
-
/* Keep register set table up to date. */
record_one_set (REGNO (to), new_insn);
static int
classic_gcse ()
{
- int bb, changed;
+ int changed;
rtx insn;
+ basic_block bb;
/* Note we start at block 1. */
+ if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
+ return 0;
+
changed = 0;
- for (bb = 1; bb < n_basic_blocks; bb++)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
{
/* Reset tables used to keep track of what's still valid [since the
start of the block]. */
reset_opr_set_tables ();
- for (insn = BLOCK_HEAD (bb);
- insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
+ for (insn = bb->head;
+ insn != NULL && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
{
/* Is insn of form (set (pseudo-reg) ...)? */
&& ((expr = lookup_expr (src)) != NULL)
/* Is the expression available [at the start of the
block]? */
- && TEST_BIT (ae_in[bb], expr->bitmap_index)
+ && TEST_BIT (ae_in[bb->index], expr->bitmap_index)
/* Are the operands unchanged since the start of the
block? */
&& oprs_not_set_p (src, insn))
gcse_create_count = 0;
alloc_expr_hash_table (max_cuid);
- alloc_rd_mem (n_basic_blocks, max_cuid);
+ alloc_rd_mem (last_basic_block, max_cuid);
compute_expr_hash_table ();
if (gcse_file)
dump_hash_table (gcse_file, "Expression", expr_hash_table,
{
compute_kill_rd ();
compute_rd ();
- alloc_avail_expr_mem (n_basic_blocks, n_exprs);
+ alloc_avail_expr_mem (last_basic_block, n_exprs);
compute_ae_gen ();
compute_ae_kill (ae_gen, ae_kill);
compute_available (ae_gen, ae_kill, ae_out, ae_in);
sbitmap *bmap;
int set_p;
{
- int bb, i, j;
+ int i, j;
+ basic_block bb;
enum rtx_code code;
reg_set *r;
const char *fmt;
{
if (REGNO (x) < FIRST_PSEUDO_REGISTER)
{
- for (bb = 0; bb < n_basic_blocks; bb++)
- if (TEST_BIT (reg_set_in_block[bb], REGNO (x)))
- SET_BIT (bmap[bb], indx);
+ FOR_EACH_BB (bb)
+ if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
+ SET_BIT (bmap[bb->index], indx);
}
else
{
{
if (REGNO (x) < FIRST_PSEUDO_REGISTER)
{
- for (bb = 0; bb < n_basic_blocks; bb++)
- if (TEST_BIT (reg_set_in_block[bb], REGNO (x)))
- RESET_BIT (bmap[bb], indx);
+ FOR_EACH_BB (bb)
+ if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
+ RESET_BIT (bmap[bb->index], indx);
}
else
{
return;
case MEM:
- for (bb = 0; bb < n_basic_blocks; bb++)
+ FOR_EACH_BB (bb)
{
- rtx list_entry = canon_modify_mem_list[bb];
+ rtx list_entry = canon_modify_mem_list[bb->index];
while (list_entry)
{
if (GET_CODE (XEXP (list_entry, 0)) == CALL_INSN)
{
if (set_p)
- SET_BIT (bmap[bb], indx);
+ SET_BIT (bmap[bb->index], indx);
else
- RESET_BIT (bmap[bb], indx);
+ RESET_BIT (bmap[bb->index], indx);
break;
}
/* LIST_ENTRY must be an INSN of some kind that sets memory.
x, rtx_addr_varies_p))
{
if (set_p)
- SET_BIT (bmap[bb], indx);
+ SET_BIT (bmap[bb->index], indx);
else
- RESET_BIT (bmap[bb], indx);
+ RESET_BIT (bmap[bb->index], indx);
break;
}
list_entry = XEXP (list_entry, 1);
case CONST:
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
/* If we've failed to do replacement, have a single SET, and don't already
have a note, add a REG_EQUAL note to not lose information. */
if (!success && note == 0 && set != 0)
- note = REG_NOTES (insn)
- = gen_rtx_EXPR_LIST (REG_EQUAL, src, REG_NOTES (insn));
+ note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
/* If there is already a NOTE, update the expression in it with our
replacement. */
This can not happen since the set of (reg Y) would have killed the
set of (reg X) making it unavailable at the start of this block. */
while (1)
- {
+ {
rtx src;
struct expr *set = lookup_set (regno, NULL_RTX);
/* Follow the copy chain, ie start another iteration of the loop
and see if we have an available copy into SRC. */
regno = REGNO (src);
- }
+ }
/* SET1 holds the last set that was available and anticipatable at
INSN. */
if (rtx_equal_p (new, SET_SRC (set)))
return 0;
- /* If this is now a no-op leave it that way, but update LABEL_NUSED if
- necessary. */
+ /* If this is now a no-op delete it, otherwise this must be a valid insn. */
if (new == pc_rtx)
+ delete_insn (insn);
+ else
{
- SET_SRC (set) = new;
-
- if (JUMP_LABEL (insn) != 0)
- --LABEL_NUSES (JUMP_LABEL (insn));
- }
-
- /* Otherwise, this must be a valid instruction. */
- else if (! validate_change (insn, &SET_SRC (set), new, 0))
- return 0;
+ if (! validate_change (insn, &SET_SRC (set), new, 0))
+ return 0;
- /* If this has turned into an unconditional jump,
- then put a barrier after it so that the unreachable
- code will be deleted. */
- if (GET_CODE (SET_SRC (set)) == LABEL_REF)
- emit_barrier_after (insn);
+ /* If this has turned into an unconditional jump,
+ then put a barrier after it so that the unreachable
+ code will be deleted. */
+ if (GET_CODE (SET_SRC (set)) == LABEL_REF)
+ emit_barrier_after (insn);
+ }
run_jump_opt_after_gcse = 1;
return 0;
/* If we succeeded, delete the cc0 setter. */
- PUT_CODE (insn, NOTE);
- NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (insn) = 0;
+ delete_insn (insn);
return 1;
- }
+}
#endif
/* Perform constant and copy propagation on INSN.
note = find_reg_equal_equiv_note (insn);
- /* We may win even when propagating constants into notes. */
+ /* We may win even when propagating constants into notes. */
if (note)
find_used_regs (&XEXP (note, 0), NULL);
struct expr *set;
/* Ignore registers created by GCSE.
- We do this because ... */
+ We do this because ... */
if (regno >= max_gcse_regno)
continue;
src = SET_SRC (pat);
/* Constant propagation. */
- if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE
- || GET_CODE (src) == SYMBOL_REF)
+ if (CONSTANT_P (src))
{
/* Handle normal insns first. */
if (GET_CODE (insn) == INSN
cprop (alter_jumps)
int alter_jumps;
{
- int bb, changed;
+ int changed;
+ basic_block bb;
rtx insn;
/* Note we start at block 1. */
+ if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
+ {
+ if (gcse_file != NULL)
+ fprintf (gcse_file, "\n");
+ return 0;
+ }
changed = 0;
- for (bb = 1; bb < n_basic_blocks; bb++)
+ FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
{
/* Reset tables used to keep track of what's still valid [since the
start of the block]. */
reset_opr_set_tables ();
- for (insn = BLOCK_HEAD (bb);
- insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
+ for (insn = bb->head;
+ insn != NULL && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
- changed |= cprop_insn (BASIC_BLOCK (bb), insn, alter_jumps);
+ changed |= cprop_insn (bb, insn, alter_jumps);
/* Keep track of everything modified by this insn. */
/* ??? Need to be careful w.r.t. mods done to INSN. Don't
call mark_oprs_set if we turned the insn into a NOTE. */
if (GET_CODE (insn) != NOTE)
mark_oprs_set (insn);
- }
+ }
}
if (gcse_file != NULL)
n_sets);
if (n_sets > 0)
{
- alloc_cprop_mem (n_basic_blocks, n_sets);
+ alloc_cprop_mem (last_basic_block, n_sets);
compute_cprop_data ();
changed = cprop (alter_jumps);
free_cprop_mem ();
compute_pre_data ()
{
sbitmap trapping_expr;
- int i;
+ basic_block bb;
unsigned int ui;
compute_local_properties (transp, comp, antloc, 0);
- sbitmap_vector_zero (ae_kill, n_basic_blocks);
+ sbitmap_vector_zero (ae_kill, last_basic_block);
/* Collect expressions which might trap. */
trapping_expr = sbitmap_alloc (n_exprs);
This is significantly faster than compute_ae_kill. */
- for (i = 0; i < n_basic_blocks; i++)
+ FOR_EACH_BB (bb)
{
edge e;
kill all trapping expressions because we won't be able to properly
place the instruction on the edge. So make them neither
anticipatable nor transparent. This is fairly conservative. */
- for (e = BASIC_BLOCK (i)->pred; e ; e = e->pred_next)
+ for (e = bb->pred; e ; e = e->pred_next)
if (e->flags & EDGE_ABNORMAL)
{
- sbitmap_difference (antloc[i], antloc[i], trapping_expr);
- sbitmap_difference (transp[i], transp[i], trapping_expr);
+ sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
+ sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr);
break;
}
- sbitmap_a_or_b (ae_kill[i], transp[i], comp[i]);
- sbitmap_not (ae_kill[i], ae_kill[i]);
+ sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
+ sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
}
edge_list = pre_edge_lcm (gcse_file, n_exprs, transp, comp, antloc,
antloc = NULL;
sbitmap_vector_free (ae_kill);
ae_kill = NULL;
- free (trapping_expr);
+ sbitmap_free (trapping_expr);
}
\f
/* PRE utilities */
}
/* The wrapper for pre_expr_reaches_here_work that ensures that any
- memory allocated for that function is returned. */
+ memory allocated for that function is returned. */
static int
pre_expr_reaches_here_p (occr_bb, expr, bb)
basic_block bb;
{
int rval;
- char *visited = (char *) xcalloc (n_basic_blocks, 1);
+ char *visited = (char *) xcalloc (last_basic_block, 1);
- rval = pre_expr_reaches_here_p_work(occr_bb, expr, bb, visited);
+ rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
free (visited);
return rval;
pat = process_insert_insn (expr);
/* If the last insn is a jump, insert EXPR in front [taking care to
- handle cc0, etc. properly]. */
+ handle cc0, etc. properly]. Similary we need to care trapping
+ instructions in presence of non-call exceptions. */
- if (GET_CODE (insn) == JUMP_INSN)
+ if (GET_CODE (insn) == JUMP_INSN
+ || (GET_CODE (insn) == INSN
+ && (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL))))
{
#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
}
#endif
/* FIXME: What if something in cc0/jump uses value set in new insn? */
- new_insn = emit_block_insn_before (pat, insn, bb);
+ new_insn = emit_insn_before (pat, insn);
}
/* Likewise if the last insn is a call, as will happen in the presence
of exception handling. */
- else if (GET_CODE (insn) == CALL_INSN)
+ else if (GET_CODE (insn) == CALL_INSN
+ && (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
|| NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
- new_insn = emit_block_insn_before (pat, insn, bb);
+ new_insn = emit_insn_before (pat, insn);
}
else
- {
- new_insn = emit_insn_after (pat, insn);
- bb->end = new_insn;
- }
+ 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
for (i = 0; i < XVECLEN (pat, 0); i++)
{
rtx insn = XVECEXP (pat, 0, i);
-
- set_block_for_insn (insn, bb);
if (INSN_P (insn))
add_label_notes (PATTERN (insn), new_insn);
}
else
{
- add_label_notes (SET_SRC (pat), new_insn);
- set_block_for_new_insns (new_insn, bb);
+ add_label_notes (pat, new_insn);
/* Keep register set table up to date. */
record_one_set (regno, new_insn);
struct expr *expr = index_map[j];
struct occr *occr;
- /* Now look at each deleted occurence of this expression. */
+ /* Now look at each deleted occurrence of this expression. */
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
if (! occr->deleted_p)
continue;
/* Insert this expression on this edge if if it would
- reach the deleted occurence in BB. */
+ reach the deleted occurrence in BB. */
if (!TEST_BIT (inserted[e], j))
{
rtx insn;
int indx = expr->bitmap_index;
rtx set = single_set (insn);
rtx new_insn;
- basic_block bb = BLOCK_FOR_INSN (insn);
if (!set)
abort ();
new_insn = emit_insn_after (gen_move_insn (reg, SET_DEST (set)), insn);
- /* Keep block number table up to date. */
- set_block_for_new_insns (new_insn, bb);
-
/* Keep register set table up to date. */
record_one_set (regno, new_insn);
- if (insn == bb->end)
- bb->end = new_insn;
gcse_create_count++;
}
}
+/* Emit move from SRC to DEST noting the equivalence with expression computed
+ in INSN. */
+static rtx
+gcse_emit_move_after (src, dest, insn)
+ rtx src, dest, insn;
+{
+ rtx new;
+ rtx set = single_set (insn);
+ rtx note;
+ rtx eqv;
+
+ /* This should never fail since we're creating a reg->reg copy
+ we've verified to be valid. */
+
+ new = emit_insn_after (gen_rtx_SET (VOIDmode, dest, src), insn);
+
+ /* Note the equivalence for local CSE pass. */
+ if ((note = find_reg_equal_equiv_note (insn)))
+ eqv = XEXP (note, 0);
+ else
+ eqv = SET_SRC (set);
+
+ set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (src));
+
+ return new;
+}
+
/* Delete redundant computations.
Deletion is done by changing the insn to copy the `reaching_reg' of
the expression into the result of the SET. It is left to later passes
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;
- SET_BIT (pre_redundant_insns, INSN_CUID (insn));
- changed = 1;
- gcse_subst_count++;
- }
+ gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
+ delete_insn (insn);
+ occr->deleted_p = 1;
+ SET_BIT (pre_redundant_insns, INSN_CUID (insn));
+ changed = 1;
+ gcse_subst_count++;
if (gcse_file)
{
}
free (index_map);
- free (pre_redundant_insns);
+ sbitmap_free (pre_redundant_insns);
return changed;
}
if (n_exprs > 0)
{
- alloc_pre_mem (n_basic_blocks, n_exprs);
+ alloc_pre_mem (last_basic_block, n_exprs);
compute_pre_data ();
changed |= pre_gcse ();
free_edge_list (edge_list);
We no longer ignore such label references (see LABEL_REF handling in
mark_jump_label for additional information). */
- REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
+ REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0),
REG_NOTES (insn));
if (LABEL_P (XEXP (x, 0)))
LABEL_NUSES (XEXP (x, 0))++;
static void
compute_transpout ()
{
- int bb;
+ basic_block bb;
unsigned int i;
struct expr *expr;
- sbitmap_vector_ones (transpout, n_basic_blocks);
+ sbitmap_vector_ones (transpout, last_basic_block);
- for (bb = 0; bb < n_basic_blocks; ++bb)
+ FOR_EACH_BB (bb)
{
/* Note that flow inserted a nop a the end of basic blocks that
end in call instructions for reasons other than abnormal
control flow. */
- if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
+ if (GET_CODE (bb->end) != CALL_INSN)
continue;
for (i = 0; i < expr_hash_table_size; i++)
/* ??? Optimally, we would use interprocedural alias
analysis to determine if this mem is actually killed
by this call. */
- RESET_BIT (transpout[bb], expr->bitmap_index);
+ RESET_BIT (transpout[bb->index], expr->bitmap_index);
}
}
}
regno = REGNO (x) - npi->min_reg;
- RESET_BIT (npi->nonnull_local[npi->current_block], regno);
- SET_BIT (npi->nonnull_killed[npi->current_block], regno);
+ RESET_BIT (npi->nonnull_local[npi->current_block->index], regno);
+ SET_BIT (npi->nonnull_killed[npi->current_block->index], regno);
}
/* Do null-pointer check elimination for the registers indicated in
they are not our responsibility to free. */
static void
-delete_null_pointer_checks_1 (delete_list, block_reg, nonnull_avin,
+delete_null_pointer_checks_1 (block_reg, nonnull_avin,
nonnull_avout, npi)
- varray_type *delete_list;
unsigned int *block_reg;
sbitmap *nonnull_avin;
sbitmap *nonnull_avout;
struct null_pointer_info *npi;
{
- int bb;
- int current_block;
+ basic_block bb, current_block;
sbitmap *nonnull_local = npi->nonnull_local;
sbitmap *nonnull_killed = npi->nonnull_killed;
Note that a register can have both properties in a single block. That
indicates that it's killed, then later in the block a new value is
computed. */
- sbitmap_vector_zero (nonnull_local, n_basic_blocks);
- sbitmap_vector_zero (nonnull_killed, n_basic_blocks);
+ sbitmap_vector_zero (nonnull_local, last_basic_block);
+ sbitmap_vector_zero (nonnull_killed, last_basic_block);
- for (current_block = 0; current_block < n_basic_blocks; current_block++)
+ FOR_EACH_BB (current_block)
{
rtx insn, stop_insn;
/* Scan each insn in the basic block looking for memory references and
register sets. */
- stop_insn = NEXT_INSN (BLOCK_END (current_block));
- for (insn = BLOCK_HEAD (current_block);
+ stop_insn = NEXT_INSN (current_block->end);
+ for (insn = current_block->head;
insn != stop_insn;
insn = NEXT_INSN (insn))
{
continue;
}
- /* See if we've got a useable memory load. We handle it first
+ /* See if we've got a usable memory load. We handle it first
in case it uses its address register as a dest (which kills
the nonnull property). */
if (GET_CODE (SET_SRC (set)) == MEM
&& GET_CODE ((reg = XEXP (SET_SRC (set), 0))) == REG
&& REGNO (reg) >= npi->min_reg
&& REGNO (reg) < npi->max_reg)
- SET_BIT (nonnull_local[current_block],
+ SET_BIT (nonnull_local[current_block->index],
REGNO (reg) - npi->min_reg);
/* Now invalidate stuff clobbered by this insn. */
&& GET_CODE ((reg = XEXP (SET_DEST (set), 0))) == REG
&& REGNO (reg) >= npi->min_reg
&& REGNO (reg) < npi->max_reg)
- SET_BIT (nonnull_local[current_block],
+ SET_BIT (nonnull_local[current_block->index],
REGNO (reg) - npi->min_reg);
}
}
/* Now look at each bb and see if it ends with a compare of a value
against zero. */
- for (bb = 0; bb < n_basic_blocks; bb++)
+ FOR_EACH_BB (bb)
{
- rtx last_insn = BLOCK_END (bb);
+ rtx last_insn = bb->end;
rtx condition, earliest;
int compare_and_branch;
/* Since MIN_REG is always at least FIRST_PSEUDO_REGISTER, and
since BLOCK_REG[BB] is zero if this block did not end with a
comparison against zero, this condition works. */
- if (block_reg[bb] < npi->min_reg
- || block_reg[bb] >= npi->max_reg)
+ if (block_reg[bb->index] < npi->min_reg
+ || block_reg[bb->index] >= npi->max_reg)
continue;
/* LAST_INSN is a conditional jump. Get its condition. */
continue;
/* Is the register known to have a nonzero value? */
- if (!TEST_BIT (nonnull_avout[bb], block_reg[bb] - npi->min_reg))
+ if (!TEST_BIT (nonnull_avout[bb->index], block_reg[bb->index] - npi->min_reg))
continue;
/* Try to compute whether the compare/branch at the loop end is one or
{
rtx new_jump;
- new_jump = emit_jump_insn_before (gen_jump (JUMP_LABEL (last_insn)),
- last_insn);
+ new_jump = emit_jump_insn_after (gen_jump (JUMP_LABEL (last_insn)),
+ last_insn);
JUMP_LABEL (new_jump) = JUMP_LABEL (last_insn);
LABEL_NUSES (JUMP_LABEL (new_jump))++;
emit_barrier_after (new_jump);
}
- if (!*delete_list)
- VARRAY_RTX_INIT (*delete_list, 10, "delete_list");
- VARRAY_PUSH_RTX (*delete_list, last_insn);
+ delete_insn (last_insn);
if (compare_and_branch == 2)
- VARRAY_PUSH_RTX (*delete_list, earliest);
+ delete_insn (earliest);
+ purge_dead_edges (bb);
/* Don't check this block again. (Note that BLOCK_END is
invalid here; we deleted the last instruction in the
block.) */
- block_reg[bb] = 0;
+ block_reg[bb->index] = 0;
}
}
{
sbitmap *nonnull_avin, *nonnull_avout;
unsigned int *block_reg;
- varray_type delete_list = NULL;
- int bb;
+ basic_block bb;
int reg;
int regs_per_pass;
int max_reg;
- unsigned int i;
struct null_pointer_info npi;
/* If we have only a single block, then there's nothing to do. */
/* We need four bitmaps, each with a bit for each register in each
basic block. */
max_reg = max_reg_num ();
- regs_per_pass = get_bitmap_width (4, n_basic_blocks, max_reg);
+ regs_per_pass = get_bitmap_width (4, last_basic_block, max_reg);
/* Allocate bitmaps to hold local and global properties. */
- npi.nonnull_local = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
- npi.nonnull_killed = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
- nonnull_avin = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
- nonnull_avout = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
+ npi.nonnull_local = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
+ npi.nonnull_killed = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
+ nonnull_avin = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
+ nonnull_avout = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
/* Go through the basic blocks, seeing whether or not each block
ends with a conditional branch whose condition is a comparison
against zero. Record the register compared in BLOCK_REG. */
- block_reg = (unsigned int *) xcalloc (n_basic_blocks, sizeof (int));
- for (bb = 0; bb < n_basic_blocks; bb++)
+ block_reg = (unsigned int *) xcalloc (last_basic_block, sizeof (int));
+ FOR_EACH_BB (bb)
{
- rtx last_insn = BLOCK_END (bb);
+ rtx last_insn = bb->end;
rtx condition, earliest, reg;
/* We only want conditional branches. */
/* LAST_INSN is a conditional jump. Get its condition. */
condition = get_condition (last_insn, &earliest);
- /* If we were unable to get the condition, or it is not a equality
+ /* If we were unable to get the condition, or it is not an equality
comparison against zero then there's nothing we can do. */
if (!condition
|| (GET_CODE (condition) != NE && GET_CODE (condition) != EQ)
if (GET_CODE (reg) != REG)
continue;
- block_reg[bb] = REGNO (reg);
+ block_reg[bb->index] = REGNO (reg);
}
/* Go through the algorithm for each block of registers. */
{
npi.min_reg = reg;
npi.max_reg = MIN (reg + regs_per_pass, max_reg);
- delete_null_pointer_checks_1 (&delete_list, block_reg, nonnull_avin,
+ delete_null_pointer_checks_1 (block_reg, nonnull_avin,
nonnull_avout, &npi);
}
- /* Now delete the instructions all at once. This breaks the CFG. */
- if (delete_list)
- {
- for (i = 0; i < VARRAY_ACTIVE_SIZE (delete_list); i++)
- delete_insn (VARRAY_RTX (delete_list, i));
- VARRAY_FREE (delete_list);
- }
-
/* Free the table of registers compared at the end of every block. */
free (block_reg);
static void
compute_code_hoist_vbeinout ()
{
- int bb, changed, passes;
+ int changed, passes;
+ basic_block bb;
- sbitmap_vector_zero (hoist_vbeout, n_basic_blocks);
- sbitmap_vector_zero (hoist_vbein, n_basic_blocks);
+ sbitmap_vector_zero (hoist_vbeout, last_basic_block);
+ sbitmap_vector_zero (hoist_vbein, last_basic_block);
passes = 0;
changed = 1;
/* We scan the blocks in the reverse order to speed up
the convergence. */
- for (bb = n_basic_blocks - 1; bb >= 0; bb--)
+ FOR_EACH_BB_REVERSE (bb)
{
- changed |= sbitmap_a_or_b_and_c (hoist_vbein[bb], antloc[bb],
- hoist_vbeout[bb], transp[bb]);
- if (bb != n_basic_blocks - 1)
- sbitmap_intersection_of_succs (hoist_vbeout[bb], hoist_vbein, bb);
+ changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index],
+ hoist_vbeout[bb->index], transp[bb->index]);
+ if (bb->next_bb != EXIT_BLOCK_PTR)
+ sbitmap_intersection_of_succs (hoist_vbeout[bb->index], hoist_vbein, bb->index);
}
passes++;
if (visited == NULL)
{
- visited_allocated_locally = 1;
- visited = xcalloc (n_basic_blocks, 1);
+ visited_allocated_locally = 1;
+ visited = xcalloc (last_basic_block, 1);
}
for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
static void
hoist_code ()
{
- int bb, dominated;
+ basic_block bb, dominated;
unsigned int i;
struct expr **index_map;
struct expr *expr;
- sbitmap_vector_zero (hoist_exprs, n_basic_blocks);
+ sbitmap_vector_zero (hoist_exprs, last_basic_block);
/* Compute a mapping from expression number (`bitmap_index') to
hash table entry. */
/* Walk over each basic block looking for potentially hoistable
expressions, nothing gets hoisted from the entry block. */
- for (bb = 0; bb < n_basic_blocks; bb++)
+ FOR_EACH_BB (bb)
{
int found = 0;
int insn_inserted_p;
/* Examine each expression that is very busy at the exit of this
block. These are the potentially hoistable expressions. */
- for (i = 0; i < hoist_vbeout[bb]->n_bits; i++)
+ for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
{
int hoistable = 0;
- if (TEST_BIT (hoist_vbeout[bb], i) && TEST_BIT (transpout[bb], i))
+ if (TEST_BIT (hoist_vbeout[bb->index], i) && TEST_BIT (transpout[bb->index], i))
{
/* We've found a potentially hoistable expression, now
we look at every block BB dominates to see if it
computes the expression. */
- for (dominated = 0; dominated < n_basic_blocks; dominated++)
+ FOR_EACH_BB (dominated)
{
/* Ignore self dominance. */
if (bb == dominated
- || ! TEST_BIT (dominators[dominated], bb))
+ || ! TEST_BIT (dominators[dominated->index], bb->index))
continue;
/* We've found a dominated block, now see if it computes
the busy expression and whether or not moving that
expression to the "beginning" of that block is safe. */
- if (!TEST_BIT (antloc[dominated], i))
+ if (!TEST_BIT (antloc[dominated->index], i))
continue;
/* Note if the expression would reach the dominated block
Keep track of how many times this expression is hoistable
from a dominated block into BB. */
- if (hoist_expr_reaches_here_p (BASIC_BLOCK (bb), i,
- BASIC_BLOCK (dominated), NULL))
+ if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
hoistable++;
}
- /* If we found more than one hoistable occurence of this
+ /* If we found more than one hoistable occurrence of this
expression, then note it in the bitmap of expressions to
hoist. It makes no sense to hoist things which are computed
in only one BB, and doing so tends to pessimize register
to nullify any benefit we get from code hoisting. */
if (hoistable > 1)
{
- SET_BIT (hoist_exprs[bb], i);
+ SET_BIT (hoist_exprs[bb->index], i);
found = 1;
}
}
continue;
/* Loop over all the hoistable expressions. */
- for (i = 0; i < hoist_exprs[bb]->n_bits; i++)
+ for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++)
{
/* We want to insert the expression into BB only once, so
note when we've inserted it. */
insn_inserted_p = 0;
/* These tests should be the same as the tests above. */
- if (TEST_BIT (hoist_vbeout[bb], i))
+ if (TEST_BIT (hoist_vbeout[bb->index], i))
{
/* We've found a potentially hoistable expression, now
we look at every block BB dominates to see if it
computes the expression. */
- for (dominated = 0; dominated < n_basic_blocks; dominated++)
+ FOR_EACH_BB (dominated)
{
/* Ignore self dominance. */
if (bb == dominated
- || ! TEST_BIT (dominators[dominated], bb))
+ || ! TEST_BIT (dominators[dominated->index], bb->index))
continue;
/* We've found a dominated block, now see if it computes
the busy expression and whether or not moving that
expression to the "beginning" of that block is safe. */
- if (!TEST_BIT (antloc[dominated], i))
+ if (!TEST_BIT (antloc[dominated->index], i))
continue;
/* The expression is computed in the dominated block and
it would be safe to compute it at the start of the
dominated block. Now we have to determine if the
- expresion would reach the dominated block if it was
+ expression would reach the dominated block if it was
placed at the end of BB. */
- if (hoist_expr_reaches_here_p (BASIC_BLOCK (bb), i,
- BASIC_BLOCK (dominated), NULL))
+ if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
{
struct expr *expr = index_map[i];
struct occr *occr = expr->antic_occr;
rtx insn;
rtx set;
- /* Find the right occurence of this expression. */
- while (BLOCK_NUM (occr->insn) != dominated && occr)
+ /* Find the right occurrence of this expression. */
+ while (BLOCK_FOR_INSN (occr->insn) != dominated && occr)
occr = occr->next;
/* Should never happen. */
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))
+ gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
+ delete_insn (insn);
+ occr->deleted_p = 1;
+ if (!insn_inserted_p)
{
- occr->deleted_p = 1;
- if (!insn_inserted_p)
- {
- insert_insn_end_bb (index_map[i],
- BASIC_BLOCK (bb), 0);
- insn_inserted_p = 1;
- }
+ insert_insn_end_bb (index_map[i], bb, 0);
+ insn_inserted_p = 1;
}
}
}
}
}
- free (index_map);
+ free (index_map);
}
/* Top level routine to perform one code hoisting (aka unification) pass
if (n_exprs > 0)
{
- alloc_code_hoist_mem (n_basic_blocks, n_exprs);
+ alloc_code_hoist_mem (last_basic_block, n_exprs);
compute_code_hoist_data ();
hoist_code ();
free_code_hoist_mem ();
load towards the exit, and we end up with no loads or stores of 'i'
in the loop. */
-/* This will search the ldst list for a matching expresion. If it
+/* This will search the ldst list for a matching expression. If it
doesn't find one, we create one and initialize it. */
static struct ls_expr *
free_ldst_entry (ptr)
struct ls_expr * ptr;
{
+ free_INSN_LIST_list (& ptr->loads);
+ free_INSN_LIST_list (& ptr->stores);
- free_INSN_LIST_list (&ptr->stores);
- free_INSN_LIST_list (&ptr->loads);
free (ptr);
}
if (GET_MODE (x) == BLKmode)
return 0;
-#if 0
- /* See comment in find_moveable_store */
- if (!rtx_addr_varies_p (XEXP (x, 0), 0))
+
+ if (!rtx_varies_p (XEXP (x, 0), 0))
return 1;
-#endif
+
return 0;
}
rtx x;
{
const char * fmt;
- int i,j;
+ int i, j;
struct ls_expr * ptr;
/* Invalidate it in the list. */
/* Find all the 'simple' MEMs which are used in LOADs and STORES. Simple
being defined as MEM loads and stores to symbols, with no
side effects and no registers in the expression. If there are any
- uses/defs which dont match this criteria, it is invalidated and
+ uses/defs which don't match this criteria, it is invalidated and
trimmed out later. */
static void
compute_ld_motion_mems ()
{
struct ls_expr * ptr;
- int bb;
+ basic_block bb;
rtx insn;
pre_ldst_mems = NULL;
- for (bb = 0; bb < n_basic_blocks; bb++)
+ FOR_EACH_BB (bb)
{
- for (insn = BLOCK_HEAD (bb);
- insn && insn != NEXT_INSN (BLOCK_END (bb));
+ for (insn = bb->head;
+ insn && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
/* Make sure there isn't a buried load somewhere. */
invalidate_any_buried_refs (src);
}
+
/* Check for stores. Don't worry about aliased ones, they
will block any movement we might do later. We only care
about this exact pattern since those are the only
copy = gen_move_insn ( reg, SET_SRC (pat));
new = emit_insn_before (copy, insn);
record_one_set (REGNO (reg), new);
- set_block_for_new_insns (new, BLOCK_FOR_INSN (insn));
SET_SRC (pat) = reg;
/* un-recognize this pattern since it's probably different now. */
\f
/* Store motion code. */
+/* This is used to communicate the target bitvector we want to use in the
+ reg_set_info routine when called via the note_stores mechanism. */
+static sbitmap * regvec;
+
/* Used in computing the reverse edge graph bit vectors. */
static sbitmap * st_antloc;
/* Global holding the number of store expressions we are dealing with. */
static int num_stores;
+/* Checks to set if we need to mark a register set. Called from note_stores. */
-/* Mark which registers are used by the mem, in the sbitmap used. */
-static int
-mark_mem_regs (x, used)
- rtx x;
- sbitmap used;
+static void
+reg_set_info (dest, setter, data)
+ rtx dest, setter ATTRIBUTE_UNUSED;
+ void * data ATTRIBUTE_UNUSED;
{
- register const char *fmt;
- int i, j;
-
- if (GET_CODE (x) == REG)
- {
- if (!TEST_BIT (used, REGNO (x)))
- {
- SET_BIT (used, REGNO (x));
- return 1;
-}
- return 0;
- }
-
- fmt = GET_RTX_FORMAT (GET_CODE (x));
- for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
- {
- if (fmt[i] == 'e')
- {
- if (mark_mem_regs (XEXP (x, i),used))
- return 1;
- }
- else if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- if (mark_mem_regs (XVECEXP (x, i, j),used))
- return 1;
- }
+ if (GET_CODE (dest) == SUBREG)
+ dest = SUBREG_REG (dest);
- return 0;
+ if (GET_CODE (dest) == REG)
+ SET_BIT (*regvec, REGNO (dest));
}
-
/* Return non-zero if the register operands of expression X are killed
- before/after insn in basic block BB. */
+ anywhere in basic block BB. */
static int
-store_ops_ok (x, bb,insn, before)
+store_ops_ok (x, bb)
rtx x;
basic_block bb;
- rtx insn;
- int before;
{
int i;
enum rtx_code code;
switch (code)
{
case REG:
- {
- /* Okay, since the reg def chains are ordered by bb/insn
- (since that's how it calculates them, and even if it didn't,
- we could just sort them), we just walk until we find a def
- in our BB, then walk until we find a def after/before our
- insn, and if we find a reg def after/before our insn, in the
- same bb, we return the approriate value. If there is no
- such def, to prevent walking *every* reg def, we stop once
- we are out of our BB again. */
- struct df_link *currref;
- bool thereyet=FALSE;
- for (currref = df_analyzer->regs[REGNO(x)].defs;
- currref;
- currref = currref->next)
- {
- if (! (DF_REF_BB (currref->ref) == bb))
- {
- if (!thereyet)
- continue;
- else
- return 1;
- }
- if (before)
- {
- if (INSN_UID (DF_REF_INSN (currref->ref)) >= INSN_UID (insn))
- continue;
- }
- else
- {
- if (INSN_UID (DF_REF_INSN (currref->ref)) < INSN_UID (insn))
- continue;
- }
- thereyet = TRUE;
- if (DF_REF_TYPE (currref->ref) == DF_REF_REG_DEF)
- return 0;
- }
- return 1;
- }
+ /* If a reg has changed after us in this
+ block, the operand has been killed. */
+ return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
-
case MEM:
x = XEXP (x, 0);
goto repeat;
case CONST:
case CONST_INT:
case CONST_DOUBLE:
+ case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
goto repeat;
}
- if (! store_ops_ok (tem, bb, insn, before))
+ if (! store_ops_ok (tem, bb))
return 0;
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
{
- if (! store_ops_ok (XVECEXP (x, i, j), bb, insn, before))
+ if (! store_ops_ok (XVECEXP (x, i, j), bb))
return 0;
}
}
return 1;
}
-/* Determine whether insn is MEM store pattern that we will consider
- moving. We'll consider moving pretty much anything that we can
- move safely. */
+/* Determine whether insn is MEM store pattern that we will consider moving. */
static void
find_moveable_store (insn)
struct ls_expr * ptr;
rtx dest = PATTERN (insn);
- /* It's it's not a set, it's not a mem store we want to consider.
- Also, if it's an ASM, we certainly don't want to try to touch
- it. */
if (GET_CODE (dest) != SET
|| GET_CODE (SET_SRC (dest)) == ASM_OPERANDS)
return;
if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
|| GET_MODE (dest) == BLKmode)
+ return;
+
+ if (GET_CODE (XEXP (dest, 0)) != SYMBOL_REF)
return;
-#if 0
- /* ??? Is this conservative, or just correct? We get more
- *candidates* without it, but i don't think we ever remove any
- stores where the address did vary. */
- if (rtx_addr_varies_p (XEXP (dest, 0), 0))
+
+ if (rtx_varies_p (XEXP (dest, 0), 0))
return;
-#endif
+
ptr = ldst_entry (dest);
ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
}
-/* Perform store motion.
- Store motion is modeled as a lazy code motion problem, like PRE is
- above. The main diffence is that we want to move stores down as far
- as possible, so we have LCM work on the reverse flowgraph. */
+/* Perform store motion. Much like gcse, except we move expressions the
+ other way by looking at the flowgraph in reverse. */
static int
compute_store_table ()
{
- int bb, ret;
+ int ret;
+ basic_block bb;
+ unsigned regno;
rtx insn, pat;
+
max_gcse_regno = max_reg_num ();
+ reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (last_basic_block,
+ max_gcse_regno);
+ sbitmap_vector_zero (reg_set_in_block, last_basic_block);
pre_ldst_mems = 0;
+
/* Find all the stores we care about. */
- for (bb = 0; bb < n_basic_blocks; bb++)
+ FOR_EACH_BB (bb)
{
- for (insn = BLOCK_END (bb);
- insn && insn != PREV_INSN (BLOCK_HEAD (bb));
+ regvec = & (reg_set_in_block[bb->index]);
+ for (insn = bb->end;
+ insn && insn != PREV_INSN (bb->end);
insn = PREV_INSN (insn))
{
/* Ignore anything that is not a normal insn. */
- if (!INSN_P (insn))
+ if (! INSN_P (insn))
continue;
+ if (GET_CODE (insn) == CALL_INSN)
+ {
+ bool clobbers_all = false;
+#ifdef NON_SAVING_SETJMP
+ if (NON_SAVING_SETJMP
+ && find_reg_note (insn, REG_SETJMP, NULL_RTX))
+ clobbers_all = true;
+#endif
+
+ for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
+ if (clobbers_all
+ || TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
+ SET_BIT (reg_set_in_block[bb->index], regno);
+ }
+
pat = PATTERN (insn);
+ note_stores (pat, reg_set_info, NULL);
+
/* Now that we've marked regs, look for stores. */
if (GET_CODE (pat) == SET)
find_moveable_store (insn);
return ret;
}
-/* Check to see if the load X is aliased with STORE_PATTERN.
- If it is, it means that load kills the store.*/
+/* Check to see if the load X is aliased with STORE_PATTERN. */
static int
load_kills_store (x, store_pattern)
return 0;
}
-/* Go through the entire insn X, looking for any loads which might
- alias, and therefore, kill, STORE_PATTERN. Return 1 if found. */
+/* Go through the entire insn X, looking for any loads which might alias
+ STORE_PATTERN. Return 1 if found. */
static int
find_loads (x, store_pattern)
rtx x, store_pattern;
{
const char * fmt;
- int i,j;
+ int i, j;
int ret = 0;
+ if (!x)
+ return 0;
+
if (GET_CODE (x) == SET)
x = SET_SRC (x);
if (GET_CODE (insn) == CALL_INSN)
{
- if (CONST_CALL_P (insn))
- return 0;
- else
- return 1;
+ /* A normal or pure call might read from pattern,
+ but a const call will not. */
+ return ! CONST_OR_PURE_CALL_P (insn) || pure_call_p (insn);
}
if (GET_CODE (PATTERN (insn)) == SET)
rtx pat = PATTERN (insn);
/* Check for memory stores to aliased objects. */
if (GET_CODE (SET_DEST (pat)) == MEM && !expr_equiv_p (SET_DEST (pat), x))
- {
+ /* pretend its a load and check for aliasing. */
if (find_loads (SET_DEST (pat), x))
return 1;
- }
return find_loads (SET_SRC (pat), x);
}
else
within basic block BB. */
static int
-store_killed_after (x, insn, bb, testops)
+store_killed_after (x, insn, bb)
rtx x, insn;
basic_block bb;
- int testops;
{
- rtx last = bb->end;
-
- if (insn == last)
- return 0;
+ rtx last = bb->end;
- if (testops)
- /* Check if the register operands of the store are OK in this block.*/
- if (!store_ops_ok (XEXP (x, 0), bb, insn, 0))
+ if (insn == last)
+ return 0;
+
+ /* Check if the register operands of the store are OK in this block.
+ Note that if registers are changed ANYWHERE in the block, we'll
+ decide we can't move it, regardless of whether it changed above
+ or below the store. This could be improved by checking the register
+ operands while lookinng for aliasing in each insn. */
+ if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
- for ( ;
- insn && insn != NEXT_INSN (last);
- insn = NEXT_INSN (insn))
- if (store_killed_in_insn (x, insn))
- return 1;
+ for ( ; insn && insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
+ if (store_killed_in_insn (x, insn))
+ return 1;
return 0;
}
-/* Returns 1 if the expression X is loaded or clobbered before INSN
+/* Returns 1 if the expression X is loaded or clobbered on or before INSN
within basic block BB. */
static int
store_killed_before (x, insn, bb)
rtx x, insn;
basic_block bb;
{
- rtx first = bb->head;
+ rtx first = bb->head;
- if (insn == first)
- return store_killed_in_insn (x, insn);
- /* Check if the register operands of the store are OK in this block.*/
- if (!store_ops_ok (XEXP (x, 0), bb, insn, 1))
+ if (insn == first)
+ return store_killed_in_insn (x, insn);
+
+ /* Check if the register operands of the store are OK in this block.
+ Note that if registers are changed ANYWHERE in the block, we'll
+ decide we can't move it, regardless of whether it changed above
+ or below the store. This could be improved by checking the register
+ operands while lookinng for aliasing in each insn. */
+ if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
- for (insn = PREV_INSN (insn) ;
- insn && insn != PREV_INSN (first);
- insn = PREV_INSN (insn))
-
- if (store_killed_in_insn (x, insn))
- return 1;
+ for ( ; insn && insn != PREV_INSN (first); insn = PREV_INSN (insn))
+ if (store_killed_in_insn (x, insn))
+ return 1;
- return 0;
+ return 0;
}
#define ANTIC_STORE_LIST(x) ((x)->loads)
static void
build_store_vectors ()
{
- basic_block bb;
- int b,i,j;
+ basic_block bb, b;
rtx insn, st;
struct ls_expr * ptr;
- sbitmap tested, *result;
- sbitmap used;
/* Build the gen_vector. This is any store in the table which is not killed
by aliasing later in its block. */
- ae_gen = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
- sbitmap_vector_zero (ae_gen, n_basic_blocks);
+ ae_gen = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
+ sbitmap_vector_zero (ae_gen, last_basic_block);
+
+ st_antloc = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
+ sbitmap_vector_zero (st_antloc, last_basic_block);
- st_antloc = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
- sbitmap_vector_zero (st_antloc, n_basic_blocks);
-
- /* Note: In case someone needs something to optimize about store
- motion, here's the next place to look. We currently test one more
- basic block per store than necessary (at least). Since we know, at
- the end of this for loop, whether a store was killed in one of the
- basic blocks (We know both whether it's killed before, and killed
- after, the insn in the bb it resides in. So unless the insn
- consists of multiple store/loads, we know whether it was killed
- in the entire bb), we could avoid testing it for kill and transp in
- the next for loop. */
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
/* Put all the stores into either the antic list, or the avail list,
{
insn = XEXP (st, 0);
bb = BLOCK_FOR_INSN (insn);
- if (!store_killed_after (ptr->pattern, insn, bb, 1))
+
+ if (!store_killed_after (ptr->pattern, insn, bb))
{
/* If we've already seen an availale expression in this block,
we can delete the one we saw already (It occurs earlier in
{
rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
if (gcse_file)
- fprintf(gcse_file, "Removing redundant store:\n");
+ fprintf (gcse_file, "Removing redundant store:\n");
replace_store_insn (r, XEXP (st, 0), bb);
XEXP (st, 0) = insn;
continue;
free_INSN_LIST_list (&store_list);
}
- ae_kill = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
- sbitmap_vector_zero (ae_kill, n_basic_blocks);
-
-
- transp = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
- sbitmap_vector_ones (transp, n_basic_blocks);
-
- tested = sbitmap_alloc (max_gcse_regno);
- sbitmap_zero (tested);
- result = sbitmap_vector_alloc (n_basic_blocks, max_gcse_regno);
- sbitmap_vector_zero (result, n_basic_blocks);
- used = sbitmap_alloc (max_gcse_regno);
- sbitmap_zero (used);
-
- /* This whole big nasty thing computes kill and transparent.
- It's done in this nasty way because profiling showed store motion
- taking twice as long as GCSE, with the cause being 1 million calls
- to store_ops_ok taking 30% of the entire runtime of the
- compiler.
- Since store most expressions use the same registers, there's no
- point in checking them 8 million times for the same basic blocks. If
- they weren't okay in a BB the last time we checked, they won't be
- okay now. Since we check all the bb's on each iteration, we don't
- need a vector for which registers we've tested, just the results.
- We then proceed to use the results of what store_ops_ok was for a
- given reg and bb, and if the results were a kill, we don't even need
- to check if the store was killed in the basic block, it'll be
- in the kill set because it's regs changed between here and there.
-
-
- If the whole store had no registers, we just skip store_ops_okay
- anyway (since it's checking reg operands), and proceed to see if
- it's okay in each bb, setting the approriate bits.
-
- With this in place, we now take almost no time at all to perform
- store motion. (It's not on the first page of the profile, it
- takes less than a second).
-
- */
+ ae_kill = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
+ sbitmap_vector_zero (ae_kill, last_basic_block);
+
+ transp = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
+ sbitmap_vector_zero (transp, last_basic_block);
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
+ FOR_EACH_BB (b)
{
- /* Make sure we don't have a load-only expr, which we never seem
- to, but i don't think there's actually a guarantee */
- if (ptr->stores != NULL)
+ if (store_killed_after (ptr->pattern, b->head, b))
{
- /* First mark the regs used by the mem */
- mark_mem_regs (ptr->pattern, used);
- /* Now see if it had any regs */
- if (!(sbitmap_first_set_bit (used) == -1))
- {
- /* For each register, see if we've tested it */
- EXECUTE_IF_SET_IN_SBITMAP (used, 0, i,
- {
- if (TEST_BIT (tested, i))
- {
- /* Already tested the register, so check the
- result, and if we had an okay result, check the
- store itself. */
- for (j = 0; j < n_basic_blocks; j++)
- {
- if (!TEST_BIT (result[j], i)
- || store_killed_after (ptr->pattern, BLOCK_HEAD (j),
- BASIC_BLOCK (j), FALSE))
- {
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- RESET_BIT (transp[j], ptr->index);
- }
- }
- }
- else
- {
- /* We haven't tested it yet, so mark it tested,
- and perform the tests */
- SET_BIT (tested, i);
- /* Check if it's okay in each BB */
- for (j = 0; j < n_basic_blocks; j++)
- {
- if (store_ops_ok (XEXP (ptr->pattern, 0),
- BASIC_BLOCK (j), BLOCK_HEAD (j), 0))
- {
- SET_BIT (result[j], ptr->index);
- }
- else
- {
- /* It's not okay, so it's killed and maybe
- not transparent */
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- {
- RESET_BIT (transp[j], ptr->index);
- }
- continue;
- }
- /* The ops were okay, so check the store
- itself */
- if (store_killed_after (ptr->pattern, BLOCK_HEAD (j),
- BASIC_BLOCK (j), FALSE))
- {
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- {
- RESET_BIT (transp[j], ptr->index);
- }
- }
- }
- }
- });
- /* Reset the used list */
- sbitmap_zero (used);
- }
- /* If it had no registers, we come here, and do the
- approriate testing */
- else
- {
- for (j = 0; j < n_basic_blocks; j++)
- {
- if (store_killed_after (ptr->pattern, BLOCK_HEAD (j),
- BASIC_BLOCK (j), FALSE))
- {
- SET_BIT (ae_kill[j], ptr->index);
- if (!TEST_BIT (ae_gen[j], ptr->index)
- || !TEST_BIT (st_antloc[j], ptr->index))
- {
- RESET_BIT (transp[j], ptr->index);
- }
- }
- }
- }
+ /* The anticipatable expression is not killed if it's gen'd. */
+ /*
+ We leave this check out for now. If we have a code sequence
+ in a block which looks like:
+ ST MEMa = x
+ L y = MEMa
+ ST MEMa = z
+ We should flag this as having an ANTIC expression, NOT
+ transparent, NOT killed, and AVAIL.
+ Unfortunately, since we haven't re-written all loads to
+ use the reaching reg, we'll end up doing an incorrect
+ Load in the middle here if we push the store down. It happens in
+ gcc.c-torture/execute/960311-1.c with -O3
+ If we always kill it in this case, we'll sometimes do
+ uneccessary work, but it shouldn't actually hurt anything.
+ if (!TEST_BIT (ae_gen[b], ptr->index)). */
+ SET_BIT (ae_kill[b->index], ptr->index);
+ }
+ else
+ SET_BIT (transp[b->index], ptr->index);
+ }
+
+ /* Any block with no exits calls some non-returning function, so
+ we better mark the store killed here, or we might not store to
+ it at all. If we knew it was abort, we wouldn't have to store,
+ but we don't know that for sure. */
+ if (gcse_file)
+ {
+ fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
+ print_ldst_list (gcse_file);
+ dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block);
+ dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block);
+ dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block);
+ dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, last_basic_block);
}
}
- sbitmap_free (tested);
- sbitmap_free (used);
- sbitmap_vector_free (result);
-}
/* Insert an instruction at the begining of a basic block, and update
the BLOCK_HEAD if needed. */
insn = emit_insn_after (insn, prev);
- if (prev == bb->end)
- bb->end = insn;
-
- set_block_for_new_insns (insn, bb);
-
if (gcse_file)
{
fprintf (gcse_file, "STORE_MOTION insert store at start of BB %d:\n",
/* If we are inserting this expression on ALL predecessor edges of a BB,
insert it at the start of the BB, and reset the insert bits on the other
- edges so we don;t try to insert it on the other edges. */
+ edges so we don't try to insert it on the other edges. */
bb = e->dest;
for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
{
insn = gen_move_insn (reg, SET_SRC (PATTERN (del)));
insn = emit_insn_after (insn, del);
- set_block_for_new_insns (insn, bb);
if (gcse_file)
{
fprintf (gcse_file,
"STORE_MOTION delete insn in BB %d:\n ", bb->index);
print_inline_rtx (gcse_file, del, 6);
- fprintf(gcse_file, "\nSTORE MOTION replaced with insn:\n ");
+ fprintf (gcse_file, "\nSTORE MOTION replaced with insn:\n ");
print_inline_rtx (gcse_file, insn, 6);
- fprintf(gcse_file, "\n");
+ fprintf (gcse_file, "\n");
}
- if (bb->end == del)
- bb->end = insn;
-
- if (bb->head == del)
- bb->head = insn;
-
delete_insn (del);
}
free_store_memory ()
{
free_ldst_mems ();
+
if (ae_gen)
sbitmap_vector_free (ae_gen);
if (ae_kill)
sbitmap_vector_free (pre_insert_map);
if (pre_delete_map)
sbitmap_vector_free (pre_delete_map);
+ if (reg_set_in_block)
+ sbitmap_vector_free (reg_set_in_block);
ae_gen = ae_kill = transp = st_antloc = NULL;
pre_insert_map = pre_delete_map = reg_set_in_block = NULL;
static void
store_motion ()
{
+ basic_block bb;
int x;
struct ls_expr * ptr;
- sbitmap trapping_expr;
- int i;
-
int update_flow = 0;
+
if (gcse_file)
{
fprintf (gcse_file, "before store motion\n");
init_alias_analysis ();
- df_analyzer = df_init();
- df_analyse (df_analyzer, 0, DF_RD_CHAIN | DF_HARD_REGS);
+
/* Find all the stores that are live to the end of their block. */
num_stores = compute_store_table ();
if (num_stores == 0)
{
- df_finish (df_analyzer);
+ sbitmap_vector_free (reg_set_in_block);
end_alias_analysis ();
return;
}
add_noreturn_fake_exit_edges ();
build_store_vectors ();
- /* Collect expressions which might trap. */
- trapping_expr = sbitmap_alloc (num_stores);
- sbitmap_zero (trapping_expr);
- for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr(ptr))
- {
- if (may_trap_p (ptr->pattern))
- SET_BIT (trapping_expr, ptr->index);
- }
- for (i = 0; i < n_basic_blocks; i++)
- {
- edge e;
-
- /* If the current block is the destination of an abnormal edge, we
- kill all trapping expressions because we won't be able to properly
- place the instruction on the edge. So make them neither
- anticipatable nor transparent. This is fairly conservative. */
- for (e = BASIC_BLOCK (i)->pred; e ; e = e->pred_next)
- if (e->flags & EDGE_ABNORMAL)
- {
- sbitmap_difference (st_antloc[i], st_antloc[i], trapping_expr);
- sbitmap_difference (transp[i], transp[i], trapping_expr);
- break;
- }
- }
-
edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
st_antloc, ae_kill, &pre_insert_map,
&pre_delete_map);
/* Now we want to insert the new stores which are going to be needed. */
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
- for (x = 0; x < n_basic_blocks; x++)
- if (TEST_BIT (pre_delete_map[x], ptr->index))
- delete_store (ptr, BASIC_BLOCK (x));
+ FOR_EACH_BB (bb)
+ if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
+ delete_store (ptr, bb);
for (x = 0; x < NUM_EDGES (edge_list); x++)
if (TEST_BIT (pre_insert_map[x], ptr->index))
if (update_flow)
commit_edge_insertions ();
- sbitmap_free (trapping_expr);
+
free_store_memory ();
free_edge_list (edge_list);
remove_fake_edges ();
end_alias_analysis ();
- df_finish (df_analyzer);
}
OSDN Git Service
