/* Static Single Assignment conversion routines for the GNU compiler.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001 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
+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
+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. */
#include "system.h"
#include "rtl.h"
+#include "expr.h"
#include "varray.h"
#include "partition.h"
#include "sbitmap.h"
#include "recog.h"
#include "basic-block.h"
#include "output.h"
-
-/* We cannot use <assert.h> in GCC source, since that would include
- GCC's assert.h, which may not be compatible with the host compiler. */
-#undef assert
-#ifdef NDEBUG
-# define assert(e)
-#else
-# define assert(e) do { if (! (e)) abort (); } while (0)
-#endif
+#include "ssa.h"
/* TODO:
left in for a limited time only, as a debugging tool until the
coalescing algorithm is validated. */
-/* All pseudo-registers (having register number >=
- FIRST_PSEUDO_REGISTER) and hard registers satisfying
- CONVERT_HARD_REGISTER_TO_SSA_P are converted to SSA form. */
-
-/* Given a hard register number REG_NO, return nonzero if and only if
- the register should be converted to SSA. */
-
-#ifndef CONVERT_HARD_REGISTER_TO_SSA_P
-#define CONVERT_HARD_REGISTER_TO_SSA_P(REG_NO) (0) /* default of no hard registers */
-#endif /* CONVERT_HARD_REGISTER_TO_SSA_P */
-
-/* Given a register number REG_NO, return nonzero if and only if the
- register should be converted to SSA. */
-
-#define CONVERT_REGISTER_TO_SSA_P(REG_NO) \
- ((!HARD_REGISTER_NUM_P (REG_NO)) || \
- (CONVERT_HARD_REGISTER_TO_SSA_P (REG_NO)))
-
static int conservative_reg_partition;
/* This flag is set when the CFG is in SSA form. */
/* Element I is the single instruction that sets register I. */
varray_type ssa_definition;
-/* Element I is an INSN_LIST of instructions that use register I. */
-varray_type ssa_uses;
-
/* Element I-PSEUDO is the normal register that originated the ssa
register in question. */
varray_type ssa_rename_from;
partition reg_partition;
};
-void ssa_rename_from_initialize
+static void ssa_rename_from_initialize
PARAMS ((void));
-rtx ssa_rename_from_lookup
+static rtx ssa_rename_from_lookup
PARAMS ((int reg));
-unsigned int original_register
+static unsigned int original_register
PARAMS ((unsigned int regno));
-void ssa_rename_from_insert
+static void ssa_rename_from_insert
PARAMS ((unsigned int reg, rtx r));
-void ssa_rename_from_free
+static void ssa_rename_from_free
PARAMS ((void));
typedef int (*srf_trav) PARAMS ((int regno, rtx r, sbitmap canonical_elements, partition reg_partition));
static void ssa_rename_from_traverse
PARAMS ((htab_trav callback_function, sbitmap canonical_elements, partition reg_partition));
-static void ssa_rename_from_print
+/*static Avoid warnign message. */ void ssa_rename_from_print
PARAMS ((void));
static int ssa_rename_from_print_1
PARAMS ((void **slot, void *data));
static inline rtx * phi_alternative
PARAMS ((rtx, int));
-static rtx first_insn_after_basic_block_note
- PARAMS ((basic_block));
-static int remove_phi_alternative
- PARAMS ((rtx, int));
static void compute_dominance_frontiers_1
PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
-static void compute_dominance_frontiers
- PARAMS ((sbitmap *frontiers, int *idom));
static void find_evaluations_1
PARAMS ((rtx dest, rtx set, void *data));
static void find_evaluations
/* Prepare ssa_rename_from for use. */
-void
+static void
ssa_rename_from_initialize ()
{
/* We use an arbitrary initial hash table size of 64. */
/* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
found. */
-rtx
+static rtx
ssa_rename_from_lookup (reg)
int reg;
{
the register is a pseudo, return the original register's number.
Otherwise, return this register number REGNO. */
-unsigned int
+static unsigned int
original_register (regno)
unsigned int regno;
{
/* Add mapping from R to REG to ssa_rename_from even if already present. */
-void
+static void
ssa_rename_from_insert (reg, r)
unsigned int reg;
rtx r;
CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
current use of this function. */
-void
+static void
ssa_rename_from_traverse (callback_function,
canonical_elements, reg_partition)
htab_trav callback_function;
/* Destroy ssa_rename_from. */
-void
+static void
ssa_rename_from_free ()
{
htab_delete (ssa_rename_from_ht);
/* Print the contents of ssa_rename_from. */
-static void
+/* static Avoid erroneous error message. */
+void
ssa_rename_from_print ()
{
printf ("ssa_rename_from's hash table contents:\n");
ssa_rename_from_hash_function (srfp)
const void *srfp;
{
- return ((ssa_rename_from_pair *) srfp)->reg;
+ return ((const ssa_rename_from_pair *) srfp)->reg;
}
/* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
block C. Return non-zero on success, or zero if no alternative is
found for C. */
-static int
-remove_phi_alternative (set, c)
+int
+remove_phi_alternative (set, block)
rtx set;
- int c;
+ basic_block block;
{
rtvec phi_vec = XVEC (SET_SRC (set), 0);
int num_elem = GET_NUM_ELEM (phi_vec);
- int v;
+ int v, c;
+ c = block->index;
for (v = num_elem - 2; v >= 0; v -= 2)
if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
{
last = BLOCK_END (bb);
while (1)
{
- if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
+ if (INSN_P (p))
note_stores (PATTERN (p), find_evaluations_1, NULL);
if (p == last)
}
}
-static void
+void
compute_dominance_frontiers (frontiers, idom)
sbitmap *frontiers;
int *idom;
}
}
-/* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
- note associated with the BLOCK. */
-
-static rtx
-first_insn_after_basic_block_note (block)
- basic_block block;
-{
- rtx insn;
-
- /* Get the first instruction in the block. */
- insn = block->head;
-
- if (insn == NULL_RTX)
- return NULL_RTX;
- if (GET_CODE (insn) == CODE_LABEL)
- insn = NEXT_INSN (insn);
- if (!NOTE_INSN_BASIC_BLOCK_P (insn))
- abort ();
-
- return NEXT_INSN (insn);
-}
-
/* Insert the phi nodes. */
static void
if (r->prev_reg == NULL_RTX && !HARD_REGISTER_P (r->old_reg))
{
r->new_reg = r->old_reg;
- /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
+ /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
r->prev_reg = RENAME_NO_RTX;
}
else
if (new_regno >= (int) ssa_definition->num_elements)
{
int new_limit = new_regno * 5 / 4;
- ssa_definition = VARRAY_GROW (ssa_definition, new_limit);
- ssa_uses = VARRAY_GROW (ssa_uses, new_limit);
+ VARRAY_GROW (ssa_definition, new_limit);
}
VARRAY_RTX (ssa_definition, new_regno) = r->set_insn;
rtx *destp = &SET_DEST (x);
rtx dest = SET_DEST (x);
+ /* An assignment to a paradoxical SUBREG does not read from
+ the destination operand, and thus does not need to be
+ wrapped into a SEQUENCE when translating into SSA form.
+ We merely strip off the SUBREG and proceed normally for
+ this case. */
+ if (GET_CODE (dest) == SUBREG
+ && (GET_MODE_SIZE (GET_MODE (dest))
+ > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
+ && GET_CODE (SUBREG_REG (dest)) == REG
+ && CONVERT_REGISTER_TO_SSA_P (REGNO (SUBREG_REG (dest))))
+ {
+ destp = &XEXP (dest, 0);
+ dest = XEXP (dest, 0);
+ }
+
/* Some SETs also use the REG specified in their LHS.
These can be detected by the presence of
STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
(sequence [(set (reg foo_1) (reg foo))
(set (subreg (reg foo_1)) ...)])
- FIXME: Much of the time this is too much. For many libcalls,
- paradoxical SUBREGs, etc., the input register is dead. We should
- recognise this in rename_block or here and not make a false
+ FIXME: Much of the time this is too much. For some constructs
+ we know that the output register is strictly an output
+ (paradoxical SUBREGs and some libcalls for example).
+
+ For those cases we are better off not making the false
dependency. */
-
if (GET_CODE (dest) == STRICT_LOW_PART
|| GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == SIGN_EXTRACT
context->new_renames = saved_new_renames;
}
}
- else if (GET_CODE (dest) == REG &&
- CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
+ else if (GET_CODE (dest) == REG
+ && CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
{
/* We found a genuine set of an interesting register. Tag
it so that we can create a new name for it after we finish
do
{
insn = next;
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ if (INSN_P (insn))
{
struct rename_context context;
context.done_renames = set_data;
reg = SET_DEST (phi);
if (REGNO (reg) >= ssa_max_reg_num)
reg = ssa_rename_from_lookup (REGNO (reg));
- assert (reg != NULL_RTX);
+ if (reg == NULL_RTX)
+ abort ();
reg = ssa_rename_to_lookup (reg);
/* It is possible for the variable to be uninitialized on
consider those edges. */
if (reg == NULL || reg == RENAME_NO_RTX)
{
- if (! remove_phi_alternative (phi, bb))
+ if (! remove_phi_alternative (phi, b))
abort ();
}
else
abort();
*phi_alternative (phi, bb) = reg;
- /* ??? Mark for a new ssa_uses entry. */
}
insn = NEXT_INSN (insn);
int nregs;
int *idom;
{
- int reg;
- int mach_mode;
-
VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
- VARRAY_RTX_INIT (ssa_uses, nregs * 3, "ssa_uses");
ssa_rename_from_initialize ();
ssa_rename_to_pseudo = (rtx *) alloca (nregs * sizeof(rtx));
- bzero ((char *) ssa_rename_to_pseudo, nregs * sizeof(rtx));
- bzero ((char *) ssa_rename_to_hard,
+ memset ((char *) ssa_rename_to_pseudo, 0, nregs * sizeof(rtx));
+ memset ((char *) ssa_rename_to_hard, 0,
FIRST_PSEUDO_REGISTER * NUM_MACHINE_MODES * sizeof (rtx));
rename_block (0, idom);
sbitmap *evals;
/* Dominator bitmaps. */
- sbitmap *dominators;
sbitmap *dfs;
sbitmap *idfs;
if (in_ssa_form)
abort ();
- /* Need global_live_at_{start,end} up to date. */
- life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
-
- /* Compute dominators. */
- dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- compute_flow_dominators (dominators, NULL);
+ /* Need global_live_at_{start,end} up to date. Do not remove any
+ dead code. We'll let the SSA optimizers do that. */
+ life_analysis (get_insns (), NULL, 0);
idom = (int *) alloca (n_basic_blocks * sizeof (int));
memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
- compute_immediate_dominators (idom, dominators);
-
- sbitmap_vector_free (dominators);
+ calculate_dominance_info (idom, NULL, CDI_DOMINATORS);
if (rtl_dump_file)
{
abort ();
/* If the alternatives aren't already in the same
- class ... */
+ class ... */
if (partition_find (reg_partition, REGNO (*alt))
!= partition_find (reg_partition, REGNO (*alt2)))
{
/* ... make them so. */
if (conflicting_hard_regs_p (REGNO (*alt), REGNO (*alt2)))
/* It is illegal to unify a hard register with
- a different register. */
+ a different register. */
abort ();
partition_union (reg_partition,
{
int reg;
- /* Work only on SSA registers. */
+ /* Work only on SSA registers. */
if (!CONVERT_REGISTER_TO_SSA_P (reg1) || !CONVERT_REGISTER_TO_SSA_P (reg2))
return 0;
rtx pattern;
rtx src;
- if (insn == NULL)
+ if (insn == NULL
+ || (GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED))
continue;
pattern = PATTERN (insn);
/* Sometimes we get PARALLEL insns. These aren't phi nodes or
do
{
insn = next;
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ if (INSN_P (insn))
{
for_each_rtx (&PATTERN (insn),
rename_equivalent_regs_in_insn,
partition reg_partition;
rtx insns = get_insns ();
- /* Need global_live_at_{start,end} up to date. */
- life_analysis (insns, NULL,
- PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE | PROP_DEATH_NOTES);
+ /* Need global_live_at_{start,end} up to date. There should not be
+ any significant dead code at this point, except perhaps dead
+ stores. So do not take the time to perform dead code elimination.
+
+ Register coalescing needs death notes, so generate them. */
+ life_analysis (insns, NULL, PROP_DEATH_NOTES);
/* Figure out which regs in copies and phi nodes don't conflict and
therefore can be coalesced. */
/* Deallocate the data structures. */
VARRAY_FREE (ssa_definition);
- VARRAY_FREE (ssa_uses);
ssa_rename_from_free ();
}