/* Global common subexpression elimination/Partial redundancy elimination
and global constant/copy propagation for GNU compiler.
Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
- 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ 2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "rtl.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
-#include "real.h"
#include "insn-config.h"
#include "recog.h"
#include "basic-block.h"
#include "hashtab.h"
#include "df.h"
#include "dbgcnt.h"
-
-/* Propagate flow information through back edges and thus enable PRE's
- moving loop invariant calculations out of loops.
-
- Originally this tended to create worse overall code, but several
- improvements during the development of PRE seem to have made following
- back edges generally a win.
-
- Note much of the loop invariant code motion done here would normally
- be done by loop.c, which has more heuristics for when to move invariants
- out of loops. At some point we might need to move some of those
- heuristics into gcse.c. */
+#include "target.h"
+#include "gcse.h"
/* We support GCSE via Partial Redundancy Elimination. PRE optimizations
- are a superset of those done by GCSE.
+ are a superset of those done by classic GCSE.
We perform the following steps:
conditional jumps if the condition can be computed from a value of
an incoming edge.
- 5) Perform store motion.
-
Two passes of copy/constant propagation are done because the first one
enables more GCSE and the second one helps to clean up the copies that
GCSE creates. This is needed more for PRE than for Classic because Classic
(set (pseudo-reg) (expression)).
Function want_to_gcse_p says what these are.
- In addition, expressions in REG_EQUAL notes are candidates for GXSE-ing.
+ In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
This allows PRE to hoist expressions that are expressed in multiple insns,
- such as comprex address calculations (e.g. for PIC code, or loads with a
- high part and as lowe part).
+ such as complex address calculations (e.g. for PIC code, or loads with a
+ high part and a low part).
PRE handles moving invariant expressions out of loops (by treating them as
partially redundant).
- Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
- assignment) based GVN (global value numbering). L. T. Simpson's paper
- (Rice University) on value numbering is a useful reference for this.
-
**********************
We used to support multiple passes but there are diminishing returns in
argue it is not. The number of iterations for the algorithm to converge
is typically 2-4 so I don't view it as that expensive (relatively speaking).
- PRE GCSE depends heavily on the second CSE pass to clean up the copies
+ PRE GCSE depends heavily on the second CPROP pass to clean up the copies
we create. To make an expression reach the place where it's redundant,
the result of the expression is copied to a new register, and the redundant
expression is deleted by replacing it with this new register. Classic GCSE
\f
/* GCSE global vars. */
+struct target_gcse default_target_gcse;
+#if SWITCHABLE_TARGET
+struct target_gcse *this_target_gcse = &default_target_gcse;
+#endif
+
/* Set to non-zero if CSE should run after all GCSE optimizations are done. */
int flag_rerun_cse_after_global_opts;
The value is the newly created pseudo-reg to record a copy of the
expression in all the places that reach the redundant copy. */
rtx reaching_reg;
+ /* Maximum distance in instructions this expression can travel.
+ We avoid moving simple expressions for more than a few instructions
+ to keep register pressure under control.
+ A value of "0" removes restrictions on how far the expression can
+ travel. */
+ int max_distance;
};
/* Occurrence of an expression.
char copied_p;
};
+typedef struct occr *occr_t;
+DEF_VEC_P (occr_t);
+DEF_VEC_ALLOC_P (occr_t, heap);
+
/* Expression and copy propagation hash tables.
Each hash table is an array of buckets.
??? It is known that if it were an array of entries, structure elements
[one could build a mapping table without holes afterwards though].
Someday I'll perform the computation and figure it out. */
-struct hash_table
+struct hash_table_d
{
/* The table itself.
This is an array of `expr_hash_table_size' elements. */
};
/* Expression hash table. */
-static struct hash_table expr_hash_table;
+static struct hash_table_d expr_hash_table;
/* Copy propagation hash table. */
-static struct hash_table set_hash_table;
+static struct hash_table_d set_hash_table;
/* This is a list of expressions which are MEMs and will be used by load
or store motion.
/* Number of global copies propagated. */
static int global_copy_prop_count;
\f
+/* Doing code hoisting. */
+static bool doing_code_hoisting_p = false;
+\f
/* For available exprs */
static sbitmap *ae_kill;
\f
static void *gcse_alloc (unsigned long);
static void alloc_gcse_mem (void);
static void free_gcse_mem (void);
-static void hash_scan_insn (rtx, struct hash_table *);
-static void hash_scan_set (rtx, rtx, struct hash_table *);
-static void hash_scan_clobber (rtx, rtx, struct hash_table *);
-static void hash_scan_call (rtx, rtx, struct hash_table *);
-static int want_to_gcse_p (rtx);
+static void hash_scan_insn (rtx, struct hash_table_d *);
+static void hash_scan_set (rtx, rtx, struct hash_table_d *);
+static void hash_scan_clobber (rtx, rtx, struct hash_table_d *);
+static void hash_scan_call (rtx, rtx, struct hash_table_d *);
+static int want_to_gcse_p (rtx, int *);
static bool gcse_constant_p (const_rtx);
static int oprs_unchanged_p (const_rtx, const_rtx, int);
static int oprs_anticipatable_p (const_rtx, const_rtx);
static int oprs_available_p (const_rtx, const_rtx);
-static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int,
- struct hash_table *);
-static void insert_set_in_table (rtx, rtx, struct hash_table *);
+static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int, int,
+ struct hash_table_d *);
+static void insert_set_in_table (rtx, rtx, struct hash_table_d *);
static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int);
static unsigned int hash_set (int, int);
static int expr_equiv_p (const_rtx, const_rtx);
static void record_last_reg_set_info (rtx, int);
static void record_last_mem_set_info (rtx);
static void record_last_set_info (rtx, const_rtx, void *);
-static void compute_hash_table (struct hash_table *);
-static void alloc_hash_table (int, struct hash_table *, int);
-static void free_hash_table (struct hash_table *);
-static void compute_hash_table_work (struct hash_table *);
-static void dump_hash_table (FILE *, const char *, struct hash_table *);
-static struct expr *lookup_set (unsigned int, struct hash_table *);
+static void compute_hash_table (struct hash_table_d *);
+static void alloc_hash_table (struct hash_table_d *, int);
+static void free_hash_table (struct hash_table_d *);
+static void compute_hash_table_work (struct hash_table_d *);
+static void dump_hash_table (FILE *, const char *, struct hash_table_d *);
+static struct expr *lookup_set (unsigned int, struct hash_table_d *);
static struct expr *next_set (unsigned int, struct expr *);
static void reset_opr_set_tables (void);
static int oprs_not_set_p (const_rtx, const_rtx);
static void alloc_cprop_mem (int, int);
static void free_cprop_mem (void);
static void compute_transp (const_rtx, int, sbitmap *, int);
-static void compute_transpout (void);
static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
- struct hash_table *);
+ struct hash_table_d *);
static void compute_cprop_data (void);
static void find_used_regs (rtx *, void *);
static int try_replace_reg (rtx, rtx, rtx);
static void compute_pre_data (void);
static int pre_expr_reaches_here_p (basic_block, struct expr *,
basic_block);
-static void insert_insn_end_basic_block (struct expr *, basic_block, int);
+static void insert_insn_end_basic_block (struct expr *, basic_block);
static void pre_insert_copy_insn (struct expr *, rtx);
static void pre_insert_copies (void);
static int pre_delete (void);
static void free_code_hoist_mem (void);
static void compute_code_hoist_vbeinout (void);
static void compute_code_hoist_data (void);
-static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *);
+static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *,
+ int, int *);
static int hoist_code (void);
static int one_code_hoisting_pass (void);
static rtx process_insert_insn (struct expr *);
\f
/* Misc. utilities. */
-/* Nonzero for each mode that supports (set (reg) (reg)).
- This is trivially true for integer and floating point values.
- It may or may not be true for condition codes. */
-static char can_copy[(int) NUM_MACHINE_MODES];
+#define can_copy \
+ (this_target_gcse->x_can_copy)
+#define can_copy_init_p \
+ (this_target_gcse->x_can_copy_init_p)
/* Compute which modes support reg/reg copy operations. */
bool
can_copy_p (enum machine_mode mode)
{
- static bool can_copy_init_p = false;
-
if (! can_copy_init_p)
{
compute_can_copy ();
alloc_gcse_mem (void)
{
/* Allocate vars to track sets of regs. */
- reg_set_bitmap = BITMAP_ALLOC (NULL);
+ reg_set_bitmap = ALLOC_REG_SET (NULL);
/* Allocate array to keep a list of insns which modify memory in each
basic block. */
static void
compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
- struct hash_table *table)
+ struct hash_table_d *table)
{
unsigned int i;
if (antloc)
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
- SET_BIT (antloc[BLOCK_NUM (occr->insn)], indx);
+ SET_BIT (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx);
/* While we're scanning the table, this is a good place to
initialize this. */
if (comp)
for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
{
- SET_BIT (comp[BLOCK_NUM (occr->insn)], indx);
+ SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
/* While we're scanning the table, this is a good place to
initialize this. */
GCSE. */
static int
-want_to_gcse_p (rtx x)
+want_to_gcse_p (rtx x, int *max_distance_ptr)
{
#ifdef STACK_REGS
/* On register stack architectures, don't GCSE constants from the
x = avoid_constant_pool_reference (x);
#endif
+ /* GCSE'ing constants:
+
+ We do not specifically distinguish between constant and non-constant
+ expressions in PRE and Hoist. We use rtx_cost below to limit
+ the maximum distance simple expressions can travel.
+
+ Nevertheless, constants are much easier to GCSE, and, hence,
+ it is easy to overdo the optimizations. Usually, excessive PRE and
+ Hoisting of constant leads to increased register pressure.
+
+ RA can deal with this by rematerialing some of the constants.
+ Therefore, it is important that the back-end generates sets of constants
+ in a way that allows reload rematerialize them under high register
+ pressure, i.e., a pseudo register with REG_EQUAL to constant
+ is set only once. Failing to do so will result in IRA/reload
+ spilling such constants under high register pressure instead of
+ rematerializing them. */
+
switch (GET_CODE (x))
{
case REG:
case SUBREG:
+ case CALL:
+ return 0;
+
case CONST_INT:
case CONST_DOUBLE:
case CONST_FIXED:
case CONST_VECTOR:
- case CALL:
- return 0;
+ if (!doing_code_hoisting_p)
+ /* Do not PRE constants. */
+ return 0;
+
+ /* FALLTHRU */
default:
+ if (doing_code_hoisting_p)
+ /* PRE doesn't implement max_distance restriction. */
+ {
+ int cost;
+ int max_distance;
+
+ gcc_assert (!optimize_function_for_speed_p (cfun)
+ && optimize_function_for_size_p (cfun));
+ cost = rtx_cost (x, SET, 0);
+
+ if (cost < COSTS_N_INSNS (GCSE_UNRESTRICTED_COST))
+ {
+ max_distance = (GCSE_COST_DISTANCE_RATIO * cost) / 10;
+ if (max_distance == 0)
+ return 0;
+
+ gcc_assert (max_distance > 0);
+ }
+ else
+ max_distance = 0;
+
+ if (max_distance_ptr)
+ *max_distance_ptr = max_distance;
+ }
+
return can_assign_to_reg_without_clobbers_p (x);
}
}
/* Return true if we can assign X to a pseudo register such that the
resulting insn does not result in clobbering a hard register as a
side-effect.
+
+ Additionally, if the target requires it, check that the resulting insn
+ can be copied. If it cannot, this means that X is special and probably
+ has hidden side-effects we don't want to mess with.
+
This function is typically used by code motion passes, to verify
that it is safe to insert an insn without worrying about clobbering
maybe live hard regs. */
valid. */
PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
SET_SRC (PATTERN (test_insn)) = x;
- return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0
- && (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode)));
+
+ icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
+ if (icode < 0)
+ return false;
+
+ if (num_clobbers > 0 && added_clobbers_hard_reg_p (icode))
+ return false;
+
+ if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (test_insn))
+ return false;
+
+ return true;
}
/* Return nonzero if the operands of expression X are unchanged from the
It is only used if X is a CONST_INT.
ANTIC_P is nonzero if X is an anticipatable expression.
- AVAIL_P is nonzero if X is an available expression. */
+ AVAIL_P is nonzero if X is an available expression.
+
+ MAX_DISTANCE is the maximum distance in instructions this expression can
+ be moved. */
static void
insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p,
- int avail_p, struct hash_table *table)
+ int avail_p, int max_distance, struct hash_table_d *table)
{
int found, do_not_record_p;
unsigned int hash;
cur_expr->next_same_hash = NULL;
cur_expr->antic_occr = NULL;
cur_expr->avail_occr = NULL;
+ gcc_assert (max_distance >= 0);
+ cur_expr->max_distance = max_distance;
}
+ else
+ gcc_assert (cur_expr->max_distance == max_distance);
/* Now record the occurrence(s). */
if (antic_p)
{
antic_occr = cur_expr->antic_occr;
- if (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
+ if (antic_occr
+ && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn))
antic_occr = NULL;
if (antic_occr)
{
avail_occr = cur_expr->avail_occr;
- if (avail_occr && BLOCK_NUM (avail_occr->insn) == BLOCK_NUM (insn))
+ if (avail_occr
+ && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn))
{
/* Found another instance of the expression in the same basic block.
Prefer this occurrence to the currently recorded one. We want
basic block. */
static void
-insert_set_in_table (rtx x, rtx insn, struct hash_table *table)
+insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table)
{
int found;
unsigned int hash;
cur_expr->next_same_hash = NULL;
cur_expr->antic_occr = NULL;
cur_expr->avail_occr = NULL;
+ /* Not used for set_p tables. */
+ cur_expr->max_distance = 0;
}
/* Now record the occurrence. */
cur_occr = cur_expr->avail_occr;
- if (cur_occr && BLOCK_NUM (cur_occr->insn) == BLOCK_NUM (insn))
+ if (cur_occr
+ && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
{
/* Found another instance of the expression in the same basic block.
Prefer this occurrence to the currently recorded one. We want
{
/* Consider a COMPARE of two integers constant. */
if (GET_CODE (x) == COMPARE
- && GET_CODE (XEXP (x, 0)) == CONST_INT
- && GET_CODE (XEXP (x, 1)) == CONST_INT)
+ && CONST_INT_P (XEXP (x, 0))
+ && CONST_INT_P (XEXP (x, 1)))
return true;
/* Consider a COMPARE of the same registers is a constant
expression one). */
static void
-hash_scan_set (rtx pat, rtx insn, struct hash_table *table)
+hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table)
{
rtx src = SET_SRC (pat);
rtx dest = SET_DEST (pat);
{
unsigned int regno = REGNO (dest);
rtx tmp;
+ int max_distance = 0;
/* See if a REG_EQUAL note shows this equivalent to a simpler expression.
&& !REG_P (src)
&& (table->set_p
? gcse_constant_p (XEXP (note, 0))
- : want_to_gcse_p (XEXP (note, 0))))
+ : want_to_gcse_p (XEXP (note, 0), NULL)))
src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
/* Only record sets of pseudo-regs in the hash table. */
/* 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)
+ do that easily for EH edges so disable GCSE on these for now. */
+ /* ??? We can now easily create new EH landing pads at the
+ gimple level, for splitting edges; there's no reason we
+ can't do the same thing at the rtl level. */
+ && !can_throw_internal (insn)
/* Is SET_SRC something we want to gcse? */
- && want_to_gcse_p (src)
+ && want_to_gcse_p (src, &max_distance)
/* Don't CSE a nop. */
&& ! set_noop_p (pat)
/* Don't GCSE if it has attached REG_EQUIV note.
int avail_p = (oprs_available_p (src, insn)
&& ! JUMP_P (insn));
- insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table);
+ insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p,
+ max_distance, table);
}
/* Record sets for constant/copy propagation. */
modified. Here we want to search from INSN+1 on, but
oprs_available_p searches from INSN on. */
&& (insn == BB_END (BLOCK_FOR_INSN (insn))
- || (tmp = next_nonnote_insn (insn)) == NULL_RTX
+ || (tmp = next_nonnote_nondebug_insn (insn)) == NULL_RTX
|| BLOCK_FOR_INSN (tmp) != BLOCK_FOR_INSN (insn)
|| oprs_available_p (pat, tmp)))
insert_set_in_table (pat, insn, table);
else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
{
unsigned int regno = REGNO (src);
+ int max_distance = 0;
/* Do not do this for constant/copy propagation. */
if (! table->set_p
/* Don't GCSE something if we can't do a reg/reg copy. */
&& can_copy_p (GET_MODE (src))
/* 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)
+ do that easily for EH edges so disable GCSE on these for now. */
+ && !can_throw_internal (insn)
/* Is SET_DEST something we want to gcse? */
- && want_to_gcse_p (dest)
+ && want_to_gcse_p (dest, &max_distance)
/* Don't CSE a nop. */
&& ! set_noop_p (pat)
/* Don't GCSE if it has attached REG_EQUIV note.
/* Record the memory expression (DEST) in the hash table. */
insert_expr_in_table (dest, GET_MODE (dest), insn,
- antic_p, avail_p, table);
+ antic_p, avail_p, max_distance, table);
}
}
}
static void
hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
- struct hash_table *table ATTRIBUTE_UNUSED)
+ struct hash_table_d *table ATTRIBUTE_UNUSED)
{
/* Currently nothing to do. */
}
static void
hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
- struct hash_table *table ATTRIBUTE_UNUSED)
+ struct hash_table_d *table ATTRIBUTE_UNUSED)
{
/* Currently nothing to do. */
}
otherwise it is for the expression hash table. */
static void
-hash_scan_insn (rtx insn, struct hash_table *table)
+hash_scan_insn (rtx insn, struct hash_table_d *table)
{
rtx pat = PATTERN (insn);
int i;
}
static void
-dump_hash_table (FILE *file, const char *name, struct hash_table *table)
+dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
{
int i;
/* Flattened out table, so it's printed in proper order. */
if (flat_table[i] != 0)
{
expr = flat_table[i];
- fprintf (file, "Index %d (hash value %d)\n ",
- expr->bitmap_index, hash_val[i]);
+ fprintf (file, "Index %d (hash value %d; max distance %d)\n ",
+ expr->bitmap_index, hash_val[i], expr->max_distance);
print_rtl (file, expr->expr);
fprintf (file, "\n");
}
dest_addr = get_addr (XEXP (dest, 0));
dest_addr = canon_rtx (dest_addr);
insn = (rtx) v_insn;
- bb = BLOCK_NUM (insn);
+ bb = BLOCK_FOR_INSN (insn)->index;
canon_modify_mem_list[bb] =
alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
static void
record_last_mem_set_info (rtx insn)
{
- int bb = BLOCK_NUM (insn);
+ int bb = BLOCK_FOR_INSN (insn)->index;
/* load_killed_in_block_p will handle the case of calls clobbering
everything. */
TABLE is the table computed. */
static void
-compute_hash_table_work (struct hash_table *table)
+compute_hash_table_work (struct hash_table_d *table)
{
int i;
determine when registers and memory are first and last set. */
FOR_BB_INSNS (current_bb, insn)
{
- if (! INSN_P (insn))
+ if (!NONDEBUG_INSN_P (insn))
continue;
if (CALL_P (insn))
/* The next pass builds the hash table. */
FOR_BB_INSNS (current_bb, insn)
- if (INSN_P (insn))
+ if (NONDEBUG_INSN_P (insn))
hash_scan_insn (insn, table);
}
}
/* Allocate space for the set/expr hash TABLE.
- N_INSNS is the number of instructions in the function.
It is used to determine the number of buckets to use.
SET_P determines whether set or expression table will
be created. */
static void
-alloc_hash_table (int n_insns, struct hash_table *table, int set_p)
+alloc_hash_table (struct hash_table_d *table, int set_p)
{
int n;
- table->size = n_insns / 4;
+ n = get_max_insn_count ();
+
+ table->size = n / 4;
if (table->size < 11)
table->size = 11;
/* Free things allocated by alloc_hash_table. */
static void
-free_hash_table (struct hash_table *table)
+free_hash_table (struct hash_table_d *table)
{
free (table->table);
}
expression hash table. */
static void
-compute_hash_table (struct hash_table *table)
+compute_hash_table (struct hash_table_d *table)
{
/* Initialize count of number of entries in hash table. */
table->n_elems = 0;
table entry, or NULL if not found. */
static struct expr *
-lookup_set (unsigned int regno, struct hash_table *table)
+lookup_set (unsigned int regno, struct hash_table_d *table)
{
unsigned int hash = hash_set (regno, table->size);
struct expr *expr;
/* Now iterate over the blocks which have memory modifications
but which do not have any calls. */
- EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set,
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set,
blocks_with_calls,
0, bb_index, bi)
{
with our replacement. */
if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
set_unique_reg_note (insn, REG_EQUAL,
- simplify_replace_rtx (XEXP (note, 0), from,
- copy_rtx (to)));
+ simplify_replace_rtx (XEXP (note, 0), from, to));
if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
{
/* If above failed and this is a single set, try to simplify the source of
&& validate_change (insn, &SET_SRC (set), src, 0))
success = 1;
- /* If we've failed to do replacement, have a single SET, don't already
- have a note, and have no special SET, add a REG_EQUAL note to not
- lose information. */
- if (!success && note == 0 && set != 0
- && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
- && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
+ /* If we've failed perform the replacement, have a single SET to
+ a REG destination and don't yet have a note, add a REG_EQUAL note
+ to not lose information. */
+ if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set)))
note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
}
which contains INSN. */
while (set)
{
- if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
+ if (TEST_BIT (cprop_avin[BLOCK_FOR_INSN (insn)->index],
+ set->bitmap_index))
break;
set = next_set (regno, set);
}
}
}
+ if (changed && DEBUG_INSN_P (insn))
+ return 0;
+
return changed;
}
struct reg_use *reg_used;
bool changed = false;
- cselib_init (false);
+ cselib_init (0);
FOR_EACH_BB (bb)
{
FOR_BB_INSNS (bb, insn)
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
removed_p = 0;
-
+
if (e->flags & EDGE_COMPLEX)
{
ei_next (&ei);
src = SET_SRC (pc_set (jump));
if (setcc != NULL)
- src = simplify_replace_rtx (src,
- SET_DEST (PATTERN (setcc)),
- SET_SRC (PATTERN (setcc)));
+ src = simplify_replace_rtx (src,
+ SET_DEST (PATTERN (setcc)),
+ SET_SRC (PATTERN (setcc)));
new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx,
- SET_SRC (set->expr));
+ SET_SRC (set->expr));
/* Jump bypassing may have already placed instructions on
edges of the CFG. We can't bypass an outgoing edge that
{
setcc = NULL_RTX;
FOR_BB_INSNS (bb, insn)
- if (NONJUMP_INSN_P (insn))
+ if (DEBUG_INSN_P (insn))
+ continue;
+ else if (NONJUMP_INSN_P (insn))
{
if (setcc)
break;
/* Nonzero for expressions that are transparent in the block. */
static sbitmap *transp;
-/* Nonzero for expressions that are transparent at the end of the block.
- This is only zero for expressions killed by abnormal critical edge
- created by a calls. */
-static sbitmap *transpout;
-
/* Nonzero for expressions that are computed (available) in the block. */
static sbitmap *comp;
pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
}
-/* Top level routine to do the dataflow analysis needed by PRE. */
+/* Remove certain expressions from anticipatable and transparent
+ sets of basic blocks that have incoming abnormal edge.
+ For PRE remove potentially trapping expressions to avoid placing
+ them on abnormal edges. For hoisting remove memory references that
+ can be clobbered by calls. */
static void
-compute_pre_data (void)
+prune_expressions (bool pre_p)
{
- sbitmap trapping_expr;
- basic_block bb;
+ sbitmap prune_exprs;
unsigned int ui;
+ basic_block bb;
- compute_local_properties (transp, comp, antloc, &expr_hash_table);
- sbitmap_vector_zero (ae_kill, last_basic_block);
-
- /* Collect expressions which might trap. */
- trapping_expr = sbitmap_alloc (expr_hash_table.n_elems);
- sbitmap_zero (trapping_expr);
+ prune_exprs = sbitmap_alloc (expr_hash_table.n_elems);
+ sbitmap_zero (prune_exprs);
for (ui = 0; ui < expr_hash_table.size; ui++)
{
struct expr *e;
for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash)
- if (may_trap_p (e->expr))
- SET_BIT (trapping_expr, e->bitmap_index);
- }
+ {
+ /* Note potentially trapping expressions. */
+ if (may_trap_p (e->expr))
+ {
+ SET_BIT (prune_exprs, e->bitmap_index);
+ continue;
+ }
- /* Compute ae_kill for each basic block using:
+ if (!pre_p && MEM_P (e->expr))
+ /* Note memory references that can be clobbered by a call.
+ We do not split abnormal edges in hoisting, so would
+ a memory reference get hoisted along an abnormal edge,
+ it would be placed /before/ the call. Therefore, only
+ constant memory references can be hoisted along abnormal
+ edges. */
+ {
+ if (GET_CODE (XEXP (e->expr, 0)) == SYMBOL_REF
+ && CONSTANT_POOL_ADDRESS_P (XEXP (e->expr, 0)))
+ continue;
- ~(TRANSP | COMP)
- */
+ if (MEM_READONLY_P (e->expr)
+ && !MEM_VOLATILE_P (e->expr)
+ && MEM_NOTRAP_P (e->expr))
+ /* Constant memory reference, e.g., a PIC address. */
+ continue;
+
+ /* ??? Optimally, we would use interprocedural alias
+ analysis to determine if this mem is actually killed
+ by this call. */
+
+ SET_BIT (prune_exprs, e->bitmap_index);
+ }
+ }
+ }
FOR_EACH_BB (bb)
{
edge_iterator ei;
/* 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. */
+ kill all trapping (for PRE) and memory (for hoist) 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 hoisting it may be necessary to check for set-and-jump
+ instructions here, not just for abnormal edges. The general problem
+ is that when an expression cannot not be placed right at the end of
+ a basic block we should account for any side-effects of a subsequent
+ jump instructions that could clobber the expression. It would
+ be best to implement this check along the lines of
+ hoist_expr_reaches_here_p where the target block is already known
+ and, hence, there's no need to conservatively prune expressions on
+ "intermediate" set-and-jump instructions. */
FOR_EACH_EDGE (e, ei, bb->preds)
- if (e->flags & EDGE_ABNORMAL)
+ if ((e->flags & EDGE_ABNORMAL)
+ && (pre_p || CALL_P (BB_END (e->src))))
{
- sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
- sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr);
+ sbitmap_difference (antloc[bb->index],
+ antloc[bb->index], prune_exprs);
+ sbitmap_difference (transp[bb->index],
+ transp[bb->index], prune_exprs);
break;
}
+ }
+
+ sbitmap_free (prune_exprs);
+}
+/* It may be necessary to insert a large number of insns on edges to
+ make the existing occurrences of expressions fully redundant. This
+ routine examines the set of insertions and deletions and if the ratio
+ of insertions to deletions is too high for a particular expression, then
+ the expression is removed from the insertion/deletion sets.
+
+ N_ELEMS is the number of elements in the hash table. */
+
+static void
+prune_insertions_deletions (int n_elems)
+{
+ sbitmap_iterator sbi;
+ sbitmap prune_exprs;
+
+ /* We always use I to iterate over blocks/edges and J to iterate over
+ expressions. */
+ unsigned int i, j;
+
+ /* Counts for the number of times an expression needs to be inserted and
+ number of times an expression can be removed as a result. */
+ int *insertions = GCNEWVEC (int, n_elems);
+ int *deletions = GCNEWVEC (int, n_elems);
+
+ /* Set of expressions which require too many insertions relative to
+ the number of deletions achieved. We will prune these out of the
+ insertion/deletion sets. */
+ prune_exprs = sbitmap_alloc (n_elems);
+ sbitmap_zero (prune_exprs);
+
+ /* Iterate over the edges counting the number of times each expression
+ needs to be inserted. */
+ for (i = 0; i < (unsigned) n_edges; i++)
+ {
+ EXECUTE_IF_SET_IN_SBITMAP (pre_insert_map[i], 0, j, sbi)
+ insertions[j]++;
+ }
+
+ /* Similarly for deletions, but those occur in blocks rather than on
+ edges. */
+ for (i = 0; i < (unsigned) last_basic_block; i++)
+ {
+ EXECUTE_IF_SET_IN_SBITMAP (pre_delete_map[i], 0, j, sbi)
+ deletions[j]++;
+ }
+
+ /* Now that we have accurate counts, iterate over the elements in the
+ hash table and see if any need too many insertions relative to the
+ number of evaluations that can be removed. If so, mark them in
+ PRUNE_EXPRS. */
+ for (j = 0; j < (unsigned) n_elems; j++)
+ if (deletions[j]
+ && ((unsigned) insertions[j] / deletions[j]) > MAX_GCSE_INSERTION_RATIO)
+ SET_BIT (prune_exprs, j);
+
+ /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS. */
+ EXECUTE_IF_SET_IN_SBITMAP (prune_exprs, 0, j, sbi)
+ {
+ for (i = 0; i < (unsigned) n_edges; i++)
+ RESET_BIT (pre_insert_map[i], j);
+
+ for (i = 0; i < (unsigned) last_basic_block; i++)
+ RESET_BIT (pre_delete_map[i], j);
+ }
+
+ sbitmap_free (prune_exprs);
+ free (insertions);
+ free (deletions);
+}
+
+/* Top level routine to do the dataflow analysis needed by PRE. */
+
+static void
+compute_pre_data (void)
+{
+ basic_block bb;
+
+ compute_local_properties (transp, comp, antloc, &expr_hash_table);
+ prune_expressions (true);
+ sbitmap_vector_zero (ae_kill, last_basic_block);
+
+ /* Compute ae_kill for each basic block using:
+
+ ~(TRANSP | COMP)
+ */
+
+ FOR_EACH_BB (bb)
+ {
sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
}
antloc = NULL;
sbitmap_vector_free (ae_kill);
ae_kill = NULL;
- sbitmap_free (trapping_expr);
+
+ prune_insertions_deletions (expr_hash_table.n_elems);
}
\f
/* PRE utilities */
{
edge pred;
edge_iterator ei;
-
+
FOR_EACH_EDGE (pred, ei, bb->preds)
{
basic_block pred_bb = pred->src;
if (insn_invalid_p (insn))
gcc_unreachable ();
}
-
+
pat = get_insns ();
end_sequence ();
/* Add EXPR to the end of basic block BB.
- This is used by both the PRE and code hoisting.
-
- For PRE, we want to verify that the expr is either transparent
- or locally anticipatable in the target block. This check makes
- no sense for code hoisting. */
+ This is used by both the PRE and code hoisting. */
static void
-insert_insn_end_basic_block (struct expr *expr, basic_block bb, int pre)
+insert_insn_end_basic_block (struct expr *expr, basic_block bb)
{
rtx insn = BB_END (bb);
rtx new_insn;
#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. */
- gcc_assert (!NONJUMP_INSN_P (insn) || !pre
- || TEST_BIT (antloc[bb->index], expr->bitmap_index)
- || TEST_BIT (transp[bb->index], expr->bitmap_index));
/* If this is a jump table, then we can't insert stuff here. Since
we know the previous real insn must be the tablejump, we insert
the new instruction just before the tablejump. */
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
- insn = prev_real_insn (insn);
+ insn = prev_active_insn (insn);
#ifdef HAVE_cc0
/* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
&& (!single_succ_p (bb)
|| single_succ_edge (bb)->flags & EDGE_ABNORMAL))
{
- /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
- we search backward and place the instructions before the first
- parameter is loaded. Do this for everyone for consistency and a
- presumption that we'll get better code elsewhere as well.
-
- It should always be the case that we can put these instructions
- anywhere in the basic block with performing PRE optimizations.
- Check this. */
-
- gcc_assert (!pre
- || TEST_BIT (antloc[bb->index], expr->bitmap_index)
- || TEST_BIT (transp[bb->index], expr->bitmap_index));
+ /* Keeping in mind targets with small register classes and parameters
+ in registers, we search backward and place the instructions before
+ the first parameter is loaded. Do this for everyone for consistency
+ and a presumption that we'll get better code elsewhere as well. */
/* Since different machines initialize their parameter registers
in different orders, assume nothing. Collect the set of all
now. */
if (eg->flags & EDGE_ABNORMAL)
- insert_insn_end_basic_block (index_map[j], bb, 0);
+ insert_insn_end_basic_block (index_map[j], bb);
else
{
insn = process_insert_insn (index_map[j]);
if (dump_file)
fprintf (dump_file,
"PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
- BLOCK_NUM (insn), INSN_UID (new_insn), indx,
+ BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx,
INSN_UID (insn), regno);
}
gcc_obstack_init (&gcse_obstack);
alloc_gcse_mem ();
- alloc_hash_table (get_max_uid (), &expr_hash_table, 0);
+ alloc_hash_table (&expr_hash_table, 0);
add_noreturn_fake_exit_edges ();
if (flag_gcse_lm)
compute_ld_motion_mems ();
}
}
-/* Compute transparent outgoing information for each block.
-
- An expression is transparent to an edge unless it is killed by
- the edge itself. This can only happen with abnormal control flow,
- when the edge is traversed through a call. This happens with
- non-local labels and exceptions.
-
- This would not be necessary if we split the edge. While this is
- normally impossible for abnormal critical edges, with some effort
- it should be possible with exception handling, since we still have
- control over which handler should be invoked. But due to increased
- EH table sizes, this may not be worthwhile. */
-
-static void
-compute_transpout (void)
-{
- basic_block bb;
- unsigned int i;
- struct expr *expr;
-
- sbitmap_vector_ones (transpout, last_basic_block);
-
- FOR_EACH_BB (bb)
- {
- /* Note that flow inserted a nop at the end of basic blocks that
- end in call instructions for reasons other than abnormal
- control flow. */
- if (! CALL_P (BB_END (bb)))
- continue;
-
- for (i = 0; i < expr_hash_table.size; i++)
- for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash)
- if (MEM_P (expr->expr))
- {
- if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
- && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
- continue;
-
- /* ??? Optimally, we would use interprocedural alias
- analysis to determine if this mem is actually killed
- by this call. */
- RESET_BIT (transpout[bb->index], expr->bitmap_index);
- }
- }
-}
-
/* Code Hoisting variables and subroutines. */
/* Very busy expressions. */
static sbitmap *hoist_vbein;
static sbitmap *hoist_vbeout;
-/* Hoistable expressions. */
-static sbitmap *hoist_exprs;
-
/* ??? We could compute post dominators and run this algorithm in
reverse to perform tail merging, doing so would probably be
more effective than the tail merging code in jump.c.
hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
- hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
- transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
}
/* Free vars used for code hoisting analysis. */
sbitmap_vector_free (hoist_vbein);
sbitmap_vector_free (hoist_vbeout);
- sbitmap_vector_free (hoist_exprs);
- sbitmap_vector_free (transpout);
free_dominance_info (CDI_DOMINATORS);
}
FOR_EACH_BB_REVERSE (bb)
{
if (bb->next_bb != EXIT_BLOCK_PTR)
- sbitmap_intersection_of_succs (hoist_vbeout[bb->index],
- hoist_vbein, bb->index);
+ {
+ sbitmap_intersection_of_succs (hoist_vbeout[bb->index],
+ hoist_vbein, bb->index);
+
+ /* Include expressions in VBEout that are calculated
+ in BB and available at its end. */
+ sbitmap_a_or_b (hoist_vbeout[bb->index],
+ hoist_vbeout[bb->index], comp[bb->index]);
+ }
changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index],
antloc[bb->index],
}
if (dump_file)
- fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes);
+ {
+ fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes);
+
+ FOR_EACH_BB (bb)
+ {
+ fprintf (dump_file, "vbein (%d): ", bb->index);
+ dump_sbitmap_file (dump_file, hoist_vbein[bb->index]);
+ fprintf (dump_file, "vbeout(%d): ", bb->index);
+ dump_sbitmap_file (dump_file, hoist_vbeout[bb->index]);
+ }
+ }
}
/* Top level routine to do the dataflow analysis needed by code hoisting. */
compute_code_hoist_data (void)
{
compute_local_properties (transp, comp, antloc, &expr_hash_table);
- compute_transpout ();
+ prune_expressions (false);
compute_code_hoist_vbeinout ();
calculate_dominance_info (CDI_DOMINATORS);
if (dump_file)
/* Determine if the expression identified by EXPR_INDEX would
reach BB unimpared if it was placed at the end of EXPR_BB.
+ Stop the search if the expression would need to be moved more
+ than DISTANCE instructions.
It's unclear exactly what Muchnick meant by "unimpared". It seems
to me that the expression must either be computed or transparent in
paths. */
static int
-hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, char *visited)
+hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb,
+ char *visited, int distance, int *bb_size)
{
edge pred;
edge_iterator ei;
int visited_allocated_locally = 0;
+ /* Terminate the search if distance, for which EXPR is allowed to move,
+ is exhausted. */
+ if (distance > 0)
+ {
+ distance -= bb_size[bb->index];
+
+ if (distance <= 0)
+ return 0;
+ }
+ else
+ gcc_assert (distance == 0);
if (visited == NULL)
{
else if (visited[pred_bb->index])
continue;
- /* Does this predecessor generate this expression? */
- else if (TEST_BIT (comp[pred_bb->index], expr_index))
- break;
else if (! TEST_BIT (transp[pred_bb->index], expr_index))
break;
else
{
visited[pred_bb->index] = 1;
- if (! hoist_expr_reaches_here_p (expr_bb, expr_index,
- pred_bb, visited))
+ if (! hoist_expr_reaches_here_p (expr_bb, expr_index, pred_bb,
+ visited, distance, bb_size))
break;
}
}
return (pred == NULL);
}
\f
+/* Find occurence in BB. */
+static struct occr *
+find_occr_in_bb (struct occr *occr, basic_block bb)
+{
+ /* Find the right occurrence of this expression. */
+ while (occr && BLOCK_FOR_INSN (occr->insn) != bb)
+ occr = occr->next;
+
+ return occr;
+}
+
/* Actually perform code hoisting. */
static int
hoist_code (void)
{
basic_block bb, dominated;
+ VEC (basic_block, heap) *dom_tree_walk;
+ unsigned int dom_tree_walk_index;
VEC (basic_block, heap) *domby;
unsigned int i,j;
struct expr **index_map;
struct expr *expr;
+ int *to_bb_head;
+ int *bb_size;
int changed = 0;
- sbitmap_vector_zero (hoist_exprs, last_basic_block);
-
/* Compute a mapping from expression number (`bitmap_index') to
hash table entry. */
for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
index_map[expr->bitmap_index] = expr;
+ /* Calculate sizes of basic blocks and note how far
+ each instruction is from the start of its block. We then use this
+ data to restrict distance an expression can travel. */
+
+ to_bb_head = XCNEWVEC (int, get_max_uid ());
+ bb_size = XCNEWVEC (int, last_basic_block);
+
+ FOR_EACH_BB (bb)
+ {
+ rtx insn;
+ int to_head;
+
+ to_head = 0;
+ FOR_BB_INSNS (bb, insn)
+ {
+ /* Don't count debug instructions to avoid them affecting
+ decision choices. */
+ if (NONDEBUG_INSN_P (insn))
+ to_bb_head[INSN_UID (insn)] = to_head++;
+ }
+
+ bb_size[bb->index] = to_head;
+ }
+
+ gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR->succs) == 1
+ && (EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest
+ == ENTRY_BLOCK_PTR->next_bb));
+
+ dom_tree_walk = get_all_dominated_blocks (CDI_DOMINATORS,
+ ENTRY_BLOCK_PTR->next_bb);
+
/* Walk over each basic block looking for potentially hoistable
expressions, nothing gets hoisted from the entry block. */
- FOR_EACH_BB (bb)
+ FOR_EACH_VEC_ELT (basic_block, dom_tree_walk, dom_tree_walk_index, bb)
{
- int found = 0;
- int insn_inserted_p;
+ domby = get_dominated_to_depth (CDI_DOMINATORS, bb, MAX_HOIST_DEPTH);
+
+ if (VEC_length (basic_block, domby) == 0)
+ continue;
- domby = get_dominated_by (CDI_DOMINATORS, bb);
/* 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->index]->n_bits; i++)
{
- int hoistable = 0;
-
- if (TEST_BIT (hoist_vbeout[bb->index], i)
- && TEST_BIT (transpout[bb->index], i))
+ if (TEST_BIT (hoist_vbeout[bb->index], i))
{
+ /* Current expression. */
+ struct expr *expr = index_map[i];
+ /* Number of occurences of EXPR that can be hoisted to BB. */
+ int hoistable = 0;
+ /* Basic blocks that have occurences reachable from BB. */
+ bitmap_head _from_bbs, *from_bbs = &_from_bbs;
+ /* Occurences reachable from BB. */
+ VEC (occr_t, heap) *occrs_to_hoist = NULL;
+ /* We want to insert the expression into BB only once, so
+ note when we've inserted it. */
+ int insn_inserted_p;
+ occr_t occr;
+
+ bitmap_initialize (from_bbs, 0);
+
+ /* If an expression is computed in BB and is available at end of
+ BB, hoist all occurences dominated by BB to BB. */
+ if (TEST_BIT (comp[bb->index], i))
+ {
+ occr = find_occr_in_bb (expr->antic_occr, bb);
+
+ if (occr)
+ {
+ /* An occurence might've been already deleted
+ while processing a dominator of BB. */
+ if (occr->deleted_p)
+ gcc_assert (MAX_HOIST_DEPTH > 1);
+ else
+ {
+ gcc_assert (NONDEBUG_INSN_P (occr->insn));
+ hoistable++;
+ }
+ }
+ else
+ hoistable++;
+ }
+
/* We've found a potentially hoistable expression, now
we look at every block BB dominates to see if it
computes the expression. */
- for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++)
+ FOR_EACH_VEC_ELT (basic_block, domby, j, dominated)
{
+ int max_distance;
+
/* Ignore self dominance. */
if (bb == dominated)
continue;
if (!TEST_BIT (antloc[dominated->index], i))
continue;
+ occr = find_occr_in_bb (expr->antic_occr, dominated);
+ gcc_assert (occr);
+
+ /* An occurence might've been already deleted
+ while processing a dominator of BB. */
+ if (occr->deleted_p)
+ {
+ gcc_assert (MAX_HOIST_DEPTH > 1);
+ continue;
+ }
+ gcc_assert (NONDEBUG_INSN_P (occr->insn));
+
+ max_distance = expr->max_distance;
+ if (max_distance > 0)
+ /* Adjust MAX_DISTANCE to account for the fact that
+ OCCR won't have to travel all of DOMINATED, but
+ only part of it. */
+ max_distance += (bb_size[dominated->index]
+ - to_bb_head[INSN_UID (occr->insn)]);
+
/* Note if the expression would reach the dominated block
unimpared if it was placed at the end of BB.
Keep track of how many times this expression is hoistable
from a dominated block into BB. */
- if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
- hoistable++;
+ if (hoist_expr_reaches_here_p (bb, i, dominated, NULL,
+ max_distance, bb_size))
+ {
+ hoistable++;
+ VEC_safe_push (occr_t, heap,
+ occrs_to_hoist, occr);
+ bitmap_set_bit (from_bbs, dominated->index);
+ }
}
/* If we found more than one hoistable occurrence of this
- expression, then note it in the bitmap of expressions to
+ expression, then note it in the vector 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
allocation. One could increase this value to try harder
the vast majority of hoistable expressions are only movable
from two successors, so raising this threshold is likely
to nullify any benefit we get from code hoisting. */
- if (hoistable > 1)
+ if (hoistable > 1 && dbg_cnt (hoist_insn))
{
- SET_BIT (hoist_exprs[bb->index], i);
- found = 1;
+ /* If (hoistable != VEC_length), then there is
+ an occurence of EXPR in BB itself. Don't waste
+ time looking for LCA in this case. */
+ if ((unsigned) hoistable
+ == VEC_length (occr_t, occrs_to_hoist))
+ {
+ basic_block lca;
+
+ lca = nearest_common_dominator_for_set (CDI_DOMINATORS,
+ from_bbs);
+ if (lca != bb)
+ /* Punt, it's better to hoist these occurences to
+ LCA. */
+ VEC_free (occr_t, heap, occrs_to_hoist);
+ }
}
- }
- }
- /* If we found nothing to hoist, then quit now. */
- if (! found)
- {
- VEC_free (basic_block, heap, domby);
- continue;
- }
+ else
+ /* Punt, no point hoisting a single occurence. */
+ VEC_free (occr_t, heap, occrs_to_hoist);
- /* Loop over all the hoistable expressions. */
- 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;
+ insn_inserted_p = 0;
- /* These tests should be the same as the tests above. */
- if (TEST_BIT (hoist_exprs[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 (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++)
+ /* Walk through occurences of I'th expressions we want
+ to hoist to BB and make the transformations. */
+ FOR_EACH_VEC_ELT (occr_t, occrs_to_hoist, j, occr)
{
- /* Ignore self dominance. */
- if (bb == dominated)
- 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->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
- expression would reach the dominated block if it was
- placed at the end of BB. */
- if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
+ rtx insn;
+ rtx set;
+
+ gcc_assert (!occr->deleted_p);
+
+ insn = occr->insn;
+ set = single_set (insn);
+ gcc_assert (set);
+
+ /* Create a pseudo-reg to store the result of reaching
+ expressions into. Get the mode for the new pseudo
+ from the mode of the original destination pseudo.
+
+ It is important to use new pseudos whenever we
+ emit a set. This will allow reload to use
+ rematerialization for such registers. */
+ if (!insn_inserted_p)
+ expr->reaching_reg
+ = gen_reg_rtx_and_attrs (SET_DEST (set));
+
+ gcse_emit_move_after (expr->reaching_reg, SET_DEST (set),
+ insn);
+ delete_insn (insn);
+ occr->deleted_p = 1;
+ changed = 1;
+ gcse_subst_count++;
+
+ if (!insn_inserted_p)
{
- struct expr *expr = index_map[i];
- struct occr *occr = expr->antic_occr;
- rtx insn;
- rtx set;
-
- /* Find the right occurrence of this expression. */
- while (BLOCK_FOR_INSN (occr->insn) != dominated && occr)
- occr = occr->next;
-
- gcc_assert (occr);
- insn = occr->insn;
- set = single_set (insn);
- gcc_assert (set);
-
- /* Create a pseudo-reg to store the result of reaching
- expressions into. Get the mode for the new pseudo
- from the mode of the original destination pseudo. */
- if (expr->reaching_reg == NULL)
- expr->reaching_reg
- = gen_reg_rtx_and_attrs (SET_DEST (set));
-
- gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
- delete_insn (insn);
- occr->deleted_p = 1;
- changed = 1;
- gcse_subst_count++;
-
- if (!insn_inserted_p)
- {
- insert_insn_end_basic_block (index_map[i], bb, 0);
- insn_inserted_p = 1;
- }
+ insert_insn_end_basic_block (expr, bb);
+ insn_inserted_p = 1;
}
}
+
+ VEC_free (occr_t, heap, occrs_to_hoist);
+ bitmap_clear (from_bbs);
}
}
VEC_free (basic_block, heap, domby);
}
+ VEC_free (basic_block, heap, dom_tree_walk);
+ free (bb_size);
+ free (to_bb_head);
free (index_map);
return changed;
|| is_too_expensive (_("GCSE disabled")))
return 0;
+ doing_code_hoisting_p = true;
+
/* We need alias. */
init_alias_analysis ();
gcc_obstack_init (&gcse_obstack);
alloc_gcse_mem ();
- alloc_hash_table (get_max_uid (), &expr_hash_table, 0);
+ alloc_hash_table (&expr_hash_table, 0);
compute_hash_table (&expr_hash_table);
if (dump_file)
dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
gcse_subst_count, gcse_create_count);
}
+ doing_code_hoisting_p = false;
+
return changed;
}
\f
return 0;
/* If we are handling exceptions, we must be careful with memory references
- that may trap. If we are not, the behavior is undefined, so we may just
+ that may trap. If we are not, the behavior is undefined, so we may just
continue. */
- if (flag_non_call_exceptions && may_trap_p (x))
+ if (cfun->can_throw_non_call_exceptions && may_trap_p (x))
return 0;
if (side_effects_p (x))
{
FOR_BB_INSNS (bb, insn)
{
- if (INSN_P (insn))
+ if (NONDEBUG_INSN_P (insn))
{
if (GET_CODE (PATTERN (insn)) == SET)
{
rtx pat = PATTERN (insn);
rtx src = SET_SRC (pat);
rtx reg = expr->reaching_reg;
- rtx copy, new_rtx;
+ rtx copy;
/* If we've already copied it, continue. */
if (expr->reaching_reg == src)
}
copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
- new_rtx = emit_insn_before (copy, insn);
+ emit_insn_before (copy, insn);
SET_SRC (pat) = reg;
df_insn_rescan (insn);
FIXME: This local pass should not be necessary after CSE (but for
some reason it still is). It is also (proven) not necessary
to run the local pass right after FWPWOP.
-
+
FIXME: The global analysis would not get into infinite loops if it
would use the DF solver (via df_simple_dataflow) instead of
the solver implemented in this file. */
implicit_sets = XCNEWVEC (rtx, last_basic_block);
find_implicit_sets ();
- alloc_hash_table (get_max_uid (), &set_hash_table, 1);
+ alloc_hash_table (&set_hash_table, 1);
compute_hash_table (&set_hash_table);
/* Free implicit_sets before peak usage. */
static unsigned int
execute_rtl_cprop (void)
{
+ int changed;
delete_unreachable_blocks ();
- df_note_add_problem ();
df_set_flags (DF_LR_RUN_DCE);
df_analyze ();
- flag_rerun_cse_after_global_opts |= one_cprop_pass ();
+ changed = one_cprop_pass ();
+ flag_rerun_cse_after_global_opts |= changed;
+ if (changed)
+ cleanup_cfg (0);
return 0;
}
static unsigned int
execute_rtl_pre (void)
{
+ int changed;
delete_unreachable_blocks ();
- df_note_add_problem ();
df_analyze ();
- flag_rerun_cse_after_global_opts |= one_pre_gcse_pass ();
+ changed = one_pre_gcse_pass ();
+ flag_rerun_cse_after_global_opts |= changed;
+ if (changed)
+ cleanup_cfg (0);
return 0;
}
static unsigned int
execute_rtl_hoist (void)
{
+ int changed;
delete_unreachable_blocks ();
- df_note_add_problem ();
df_analyze ();
- flag_rerun_cse_after_global_opts |= one_code_hoisting_pass ();
+ changed = one_code_hoisting_pass ();
+ flag_rerun_cse_after_global_opts |= changed;
+ if (changed)
+ cleanup_cfg (0);
return 0;
}
{
RTL_PASS,
"cprop", /* name */
- gate_rtl_cprop, /* gate */
- execute_rtl_cprop, /* execute */
+ gate_rtl_cprop, /* gate */
+ execute_rtl_cprop, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
{
{
RTL_PASS,
- "pre", /* name */
- gate_rtl_pre, /* gate */
- execute_rtl_pre, /* execute */
+ "rtl pre", /* name */
+ gate_rtl_pre, /* gate */
+ execute_rtl_pre, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
{
RTL_PASS,
"hoist", /* name */
- gate_rtl_hoist, /* gate */
- execute_rtl_hoist, /* execute */
+ gate_rtl_hoist, /* gate */
+ execute_rtl_hoist, /* execute */
NULL, /* sub */
NULL, /* next */
0, /* static_pass_number */
};
#include "gt-gcse.h"
+
OSDN Git Service
