/* Static Single Assignment conversion routines for the GNU compiler.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2001, 2002, 2003
+ 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. */
Static Single Assignment Construction
Preston Briggs, Tim Harvey, Taylor Simpson
Technical Report, Rice University, 1995
- ftp://ftp.cs.rice.edu/public/preston/optimizer/SSA.ps.gz
-*/
+ ftp://ftp.cs.rice.edu/public/preston/optimizer/SSA.ps.gz. */
#include "config.h"
#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
+#include "expr.h"
+#include "varray.h"
+#include "partition.h"
+#include "sbitmap.h"
+#include "hashtab.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "recog.h"
#include "basic-block.h"
#include "output.h"
-#include "partition.h"
+#include "ssa.h"
+/* TODO:
-/* TODO:
+ Handle subregs better, maybe. For now, if a reg that's set in a
+ subreg expression is duplicated going into SSA form, an extra copy
+ is inserted first that copies the entire reg into the duplicate, so
+ that the other bits are preserved. This isn't strictly SSA, since
+ at least part of the reg is assigned in more than one place (though
+ they are adjacent).
??? What to do about strict_low_part. Probably I'll have to split
them out of their current instructions first thing.
in which the RTL encodes exactly what we want, without exposing a
lot of niggling processor details. At some later point we lower
the representation, calling back into optabs to finish any necessary
- expansion.
-*/
+ expansion. */
+/* All pseudo-registers and select hard registers are converted to SSA
+ form. When converting out of SSA, these select hard registers are
+ guaranteed to be mapped to their original register number. Each
+ machine's .h file should define CONVERT_HARD_REGISTER_TO_SSA_P
+ indicating which hard registers should be converted.
-/* Element I is the single instruction that sets register I+PSEUDO. */
-varray_type ssa_definition;
+ When converting out of SSA, temporaries for all registers are
+ partitioned. The partition is checked to ensure that all uses of
+ the same hard register in the same machine mode are in the same
+ class. */
+
+/* If conservative_reg_partition is nonzero, use a conservative
+ register partitioning algorithm (which leaves more regs after
+ emerging from SSA) instead of the coalescing one. This is being
+ left in for a limited time only, as a debugging tool until the
+ coalescing algorithm is validated. */
+
+static int conservative_reg_partition;
-/* Element I is an INSN_LIST of instructions that use register I+PSEUDO. */
-varray_type ssa_uses;
+/* This flag is set when the CFG is in SSA form. */
+int in_ssa_form = 0;
+
+/* Element I is the single instruction that sets register I. */
+varray_type ssa_definition;
/* Element I-PSEUDO is the normal register that originated the ssa
register in question. */
varray_type ssa_rename_from;
-/* The running target ssa register for a given normal register. */
-static rtx *ssa_rename_to;
+/* Element I is the normal register that originated the ssa
+ register in question.
+
+ A hash table stores the (register, rtl) pairs. These are each
+ xmalloc'ed and deleted when the hash table is destroyed. */
+htab_t ssa_rename_from_ht;
+
+/* The running target ssa register for a given pseudo register.
+ (Pseudo registers appear in only one mode.) */
+static rtx *ssa_rename_to_pseudo;
+/* Similar, but for hard registers. A hard register can appear in
+ many modes, so we store an equivalent pseudo for each of the
+ modes. */
+static rtx ssa_rename_to_hard[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
+
+/* ssa_rename_from maps pseudo registers to the original corresponding
+ RTL. It is implemented as using a hash table. */
+
+typedef struct {
+ unsigned int reg;
+ rtx original;
+} ssa_rename_from_pair;
+
+struct ssa_rename_from_hash_table_data {
+ sbitmap canonical_elements;
+ partition reg_partition;
+};
+
+static rtx gen_sequence (void);
+static void ssa_rename_from_initialize (void);
+static rtx ssa_rename_from_lookup (int reg);
+static unsigned int original_register (unsigned int regno);
+static void ssa_rename_from_insert (unsigned int reg, rtx r);
+static void ssa_rename_from_free (void);
+typedef int (*srf_trav) (int regno, rtx r, sbitmap canonical_elements,
+ partition reg_partition);
+static void ssa_rename_from_traverse (htab_trav callback_function,
+ sbitmap canonical_elements, partition reg_partition);
+/*static Avoid warning message. */ void ssa_rename_from_print (void);
+static int ssa_rename_from_print_1 (void **slot, void *data);
+static hashval_t ssa_rename_from_hash_function (const void * srfp);
+static int ssa_rename_from_equal (const void *srfp1, const void *srfp2);
+static void ssa_rename_from_delete (void *srfp);
+
+static rtx ssa_rename_to_lookup (rtx reg);
+static void ssa_rename_to_insert (rtx reg, rtx r);
/* The number of registers that were live on entry to the SSA routines. */
static unsigned int ssa_max_reg_num;
/* Local function prototypes. */
-static inline rtx * phi_alternative
- PARAMS ((rtx, int));
-
-static int remove_phi_alternative
- PARAMS ((rtx, int));
-static void simplify_to_immediate_dominators
- PARAMS ((int *idom, sbitmap *dominators));
-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
- PARAMS ((sbitmap *evals, int nregs));
-static void compute_iterated_dominance_frontiers
- PARAMS ((sbitmap *idfs, sbitmap *frontiers, sbitmap *evals, int nregs));
-static void insert_phi_node
- PARAMS ((int regno, int b));
-static void insert_phi_nodes
- PARAMS ((sbitmap *idfs, sbitmap *evals, int nregs));
-static int rename_insn_1
- PARAMS ((rtx *ptr, void *data));
-static void rename_block
- PARAMS ((int b, int *idom));
-static void rename_registers
- PARAMS ((int nregs, int *idom));
-
-static inline int ephi_add_node
- PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
-static int * ephi_forward
- PARAMS ((int t, sbitmap visited, sbitmap *succ, int *tstack));
-static void ephi_backward
- PARAMS ((int t, sbitmap visited, sbitmap *pred, rtx *nodes));
-static void ephi_create
- PARAMS ((int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes));
-static void eliminate_phi
- PARAMS ((edge e, partition reg_partition));
-
-static int make_regs_equivalent_over_bad_edges
- PARAMS ((int bb, partition reg_partition));
-static int make_equivalent_phi_alternatives_equivalent
- PARAMS ((int bb, partition reg_partition));
-static partition compute_conservative_reg_partition
- PARAMS ((void));
-static int rename_equivalent_regs_in_insn
- PARAMS ((rtx *ptr, void *data));
-static void rename_equivalent_regs
- PARAMS ((partition reg_partition));
-
-
-/* Determine if the insn is a PHI node. */
-#define PHI_NODE_P(X) \
- (X && GET_CODE (X) == INSN \
- && GET_CODE (PATTERN (X)) == SET \
- && GET_CODE (SET_SRC (PATTERN (X))) == PHI)
+struct rename_context;
+
+static inline rtx * phi_alternative (rtx, int);
+static void compute_dominance_frontiers_1 (sbitmap *frontiers,
+ dominance_info idom, int bb,
+ sbitmap done);
+static void find_evaluations_1 (rtx dest, rtx set, void *data);
+static void find_evaluations (sbitmap *evals, int nregs);
+static void compute_iterated_dominance_frontiers (sbitmap *idfs,
+ sbitmap *frontiers,
+ sbitmap *evals, int nregs);
+static void insert_phi_node (int regno, int b);
+static void insert_phi_nodes (sbitmap *idfs, sbitmap *evals, int nregs);
+static void create_delayed_rename (struct rename_context *, rtx *);
+static void apply_delayed_renames (struct rename_context *);
+static int rename_insn_1 (rtx *ptr, void *data);
+static void rename_block (int b, dominance_info dom);
+static void rename_registers (int nregs, dominance_info idom);
+
+static inline int ephi_add_node (rtx reg, rtx *nodes, int *n_nodes);
+static int * ephi_forward (int t, sbitmap visited, sbitmap *succ, int *tstack);
+static void ephi_backward (int t, sbitmap visited, sbitmap *pred, rtx *nodes);
+static void ephi_create (int t, sbitmap visited, sbitmap *pred,
+ sbitmap *succ, rtx *nodes);
+static void eliminate_phi (edge e, partition reg_partition);
+static int make_regs_equivalent_over_bad_edges (int bb,
+ partition reg_partition);
+
+/* These are used only in the conservative register partitioning
+ algorithms. */
+static int make_equivalent_phi_alternatives_equivalent
+ (int bb, partition reg_partition);
+static partition compute_conservative_reg_partition (void);
+static int record_canonical_element_1 (void **srfp, void *data);
+static int check_hard_regs_in_partition (partition reg_partition);
+
+/* These are used in the register coalescing algorithm. */
+static int coalesce_if_unconflicting (partition p, conflict_graph conflicts,
+ int reg1, int reg2);
+static int coalesce_regs_in_copies (basic_block bb, partition p,
+ conflict_graph conflicts);
+static int coalesce_reg_in_phi (rtx, int dest_regno, int src_regno,
+ void *data);
+static int coalesce_regs_in_successor_phi_nodes (basic_block bb,
+ partition p,
+ conflict_graph conflicts);
+static partition compute_coalesced_reg_partition (void);
+static int mark_reg_in_phi (rtx *ptr, void *data);
+static void mark_phi_and_copy_regs (regset phi_set);
+
+static int rename_equivalent_regs_in_insn (rtx *ptr, void *data);
+static void rename_equivalent_regs (partition reg_partition);
+
+/* Deal with hard registers. */
+static int conflicting_hard_regs_p (int reg1, int reg2);
+
+/* ssa_rename_to maps registers and machine modes to SSA pseudo registers. */
+
+/* Find the register associated with REG in the indicated mode. */
+
+static rtx
+ssa_rename_to_lookup (rtx reg)
+{
+ if (!HARD_REGISTER_P (reg))
+ return ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER];
+ else
+ return ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)];
+}
+
+/* Store a new value mapping REG to R in ssa_rename_to. */
+
+static void
+ssa_rename_to_insert (rtx reg, rtx r)
+{
+ if (!HARD_REGISTER_P (reg))
+ ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER] = r;
+ else
+ ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)] = r;
+}
+
+/* Prepare ssa_rename_from for use. */
+
+static void
+ssa_rename_from_initialize (void)
+{
+ /* We use an arbitrary initial hash table size of 64. */
+ ssa_rename_from_ht = htab_create (64,
+ &ssa_rename_from_hash_function,
+ &ssa_rename_from_equal,
+ &ssa_rename_from_delete);
+}
+
+/* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
+ found. */
+
+static rtx
+ssa_rename_from_lookup (int reg)
+{
+ ssa_rename_from_pair srfp;
+ ssa_rename_from_pair *answer;
+ srfp.reg = reg;
+ srfp.original = NULL_RTX;
+ answer = htab_find_with_hash (ssa_rename_from_ht, (void *) &srfp, reg);
+ return (answer == 0 ? NULL_RTX : answer->original);
+}
+
+/* Find the number of the original register specified by REGNO. If
+ the register is a pseudo, return the original register's number.
+ Otherwise, return this register number REGNO. */
+
+static unsigned int
+original_register (unsigned int regno)
+{
+ rtx original_rtx = ssa_rename_from_lookup (regno);
+ return original_rtx != NULL_RTX ? REGNO (original_rtx) : regno;
+}
+
+/* Add mapping from R to REG to ssa_rename_from even if already present. */
+
+static void
+ssa_rename_from_insert (unsigned int reg, rtx r)
+{
+ void **slot;
+ ssa_rename_from_pair *srfp = xmalloc (sizeof (ssa_rename_from_pair));
+ srfp->reg = reg;
+ srfp->original = r;
+ slot = htab_find_slot_with_hash (ssa_rename_from_ht, (const void *) srfp,
+ reg, INSERT);
+ if (*slot != 0)
+ free ((void *) *slot);
+ *slot = srfp;
+}
+
+/* Apply the CALLBACK_FUNCTION to each element in ssa_rename_from.
+ CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
+ current use of this function. */
+
+static void
+ssa_rename_from_traverse (htab_trav callback_function,
+ sbitmap canonical_elements, partition reg_partition)
+{
+ struct ssa_rename_from_hash_table_data srfhd;
+ srfhd.canonical_elements = canonical_elements;
+ srfhd.reg_partition = reg_partition;
+ htab_traverse (ssa_rename_from_ht, callback_function, (void *) &srfhd);
+}
+
+/* Destroy ssa_rename_from. */
+
+static void
+ssa_rename_from_free (void)
+{
+ htab_delete (ssa_rename_from_ht);
+}
+
+/* Print the contents of ssa_rename_from. */
+
+/* static Avoid erroneous error message. */
+void
+ssa_rename_from_print (void)
+{
+ printf ("ssa_rename_from's hash table contents:\n");
+ htab_traverse (ssa_rename_from_ht, &ssa_rename_from_print_1, NULL);
+}
+
+/* Print the contents of the hash table entry SLOT, passing the unused
+ attribute DATA. Used as a callback function with htab_traverse (). */
+
+static int
+ssa_rename_from_print_1 (void **slot, void *data ATTRIBUTE_UNUSED)
+{
+ ssa_rename_from_pair * p = *slot;
+ printf ("ssa_rename_from maps pseudo %i to original %i.\n",
+ p->reg, REGNO (p->original));
+ return 1;
+}
+
+/* Given a hash entry SRFP, yield a hash value. */
+
+static hashval_t
+ssa_rename_from_hash_function (const void *srfp)
+{
+ return ((const ssa_rename_from_pair *) srfp)->reg;
+}
+
+/* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
+
+static int
+ssa_rename_from_equal (const void *srfp1, const void *srfp2)
+{
+ return ssa_rename_from_hash_function (srfp1) ==
+ ssa_rename_from_hash_function (srfp2);
+}
+
+/* Delete the hash table entry SRFP. */
+
+static void
+ssa_rename_from_delete (void *srfp)
+{
+ free (srfp);
+}
/* Given the SET of a PHI node, return the address of the alternative
for predecessor block C. */
static inline rtx *
-phi_alternative (set, c)
- rtx set;
- int c;
+phi_alternative (rtx set, int c)
{
rtvec phi_vec = XVEC (SET_SRC (set), 0);
int v;
}
/* Given the SET of a phi node, remove the alternative for predecessor
- block C. Return non-zero on success, or zero if no alternative is
+ block C. Return nonzero on success, or zero if no alternative is
found for C. */
-static int
-remove_phi_alternative (set, c)
- rtx set;
- int c;
+int
+remove_phi_alternative (rtx set, 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)
{
return 0;
}
-/* Computing the Immediate Dominators:
-
- Throughout, we don't actually want the full dominators set as
- calculated by flow, but rather the immediate dominators.
-*/
-
-static void
-simplify_to_immediate_dominators (idom, dominators)
- int *idom;
- sbitmap *dominators;
-{
- sbitmap *tmp;
- int b;
-
- tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
-
- /* Begin with tmp(n) = dom(n) - { n }. */
- for (b = n_basic_blocks; --b >= 0; )
- {
- sbitmap_copy (tmp[b], dominators[b]);
- RESET_BIT (tmp[b], b);
- }
-
- /* Subtract out all of our dominator's dominators. */
- for (b = n_basic_blocks; --b >= 0; )
- {
- sbitmap tmp_b = tmp[b];
- int s;
-
- for (s = n_basic_blocks; --s >= 0; )
- if (TEST_BIT (tmp_b, s))
- sbitmap_difference (tmp_b, tmp_b, tmp[s]);
- }
-
- /* Find the one bit set in the bitmap and put it in the output array. */
- for (b = n_basic_blocks; --b >= 0; )
- {
- int t;
- EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
- }
-
- sbitmap_vector_free (tmp);
-}
-
-
/* For all registers, find all blocks in which they are set.
This is the transform of what would be local kill information that
static int fe_current_bb;
static void
-find_evaluations_1 (dest, set, data)
- rtx dest;
- rtx set ATTRIBUTE_UNUSED;
- void *data ATTRIBUTE_UNUSED;
+find_evaluations_1 (rtx dest, rtx set ATTRIBUTE_UNUSED,
+ void *data ATTRIBUTE_UNUSED)
{
if (GET_CODE (dest) == REG
- && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
- SET_BIT (fe_evals[REGNO (dest) - FIRST_PSEUDO_REGISTER], fe_current_bb);
+ && CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
+ SET_BIT (fe_evals[REGNO (dest)], fe_current_bb);
}
static void
-find_evaluations (evals, nregs)
- sbitmap *evals;
- int nregs;
+find_evaluations (sbitmap *evals, int nregs)
{
- int bb;
+ basic_block bb;
sbitmap_vector_zero (evals, nregs);
fe_evals = evals;
- for (bb = n_basic_blocks; --bb >= 0; )
+ FOR_EACH_BB_REVERSE (bb)
{
rtx p, last;
- fe_current_bb = bb;
- p = BLOCK_HEAD (bb);
- last = BLOCK_END (bb);
+ fe_current_bb = bb->index;
+ p = bb->head;
+ last = bb->end;
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)
}
}
-
/* Computing the Dominance Frontier:
-
- As decribed in Morgan, section 3.5, this may be done simply by
+
+ As described in Morgan, section 3.5, this may be done simply by
walking the dominator tree bottom-up, computing the frontier for
the children before the parent. When considering a block B,
there are two cases:
*/
static void
-compute_dominance_frontiers_1 (frontiers, idom, bb, done)
- sbitmap *frontiers;
- int *idom;
- int bb;
- sbitmap done;
+compute_dominance_frontiers_1 (sbitmap *frontiers, dominance_info idom,
+ int bb, sbitmap done)
{
basic_block b = BASIC_BLOCK (bb);
edge e;
- int c;
+ basic_block c;
SET_BIT (done, bb);
sbitmap_zero (frontiers[bb]);
/* Do the frontier of the children first. Not all children in the
dominator tree (blocks dominated by this one) are children in the
CFG, so check all blocks. */
- for (c = 0; c < n_basic_blocks; ++c)
- if (idom[c] == bb && ! TEST_BIT (done, c))
- compute_dominance_frontiers_1 (frontiers, idom, c, done);
+ FOR_EACH_BB (c)
+ if (get_immediate_dominator (idom, c)->index == bb
+ && ! TEST_BIT (done, c->index))
+ compute_dominance_frontiers_1 (frontiers, idom, c->index, done);
/* Find blocks conforming to rule (1) above. */
for (e = b->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
- if (idom[e->dest->index] != bb)
+ if (get_immediate_dominator (idom, e->dest)->index != bb)
SET_BIT (frontiers[bb], e->dest->index);
}
/* Find blocks conforming to rule (2). */
- for (c = 0; c < n_basic_blocks; ++c)
- if (idom[c] == bb)
+ FOR_EACH_BB (c)
+ if (get_immediate_dominator (idom, c)->index == bb)
{
int x;
- EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x,
+ EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x,
{
- if (idom[x] != bb)
+ if (get_immediate_dominator (idom, BASIC_BLOCK (x))->index != bb)
SET_BIT (frontiers[bb], x);
});
}
}
-static void
-compute_dominance_frontiers (frontiers, idom)
- sbitmap *frontiers;
- int *idom;
+void
+compute_dominance_frontiers (sbitmap *frontiers, dominance_info idom)
{
- sbitmap done = sbitmap_alloc (n_basic_blocks);
+ sbitmap done = sbitmap_alloc (last_basic_block);
sbitmap_zero (done);
compute_dominance_frontiers_1 (frontiers, idom, 0, done);
sbitmap_free (done);
}
-
/* Computing the Iterated Dominance Frontier:
This is the set of merge points for a given register.
*/
static void
-compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs)
- sbitmap *idfs;
- sbitmap *frontiers;
- sbitmap *evals;
- int nregs;
+compute_iterated_dominance_frontiers (sbitmap *idfs, sbitmap *frontiers,
+ sbitmap *evals, int nregs)
{
sbitmap worklist;
int reg, passes = 0;
- worklist = sbitmap_alloc (n_basic_blocks);
+ worklist = sbitmap_alloc (last_basic_block);
for (reg = 0; reg < nregs; ++reg)
{
if (rtl_dump_file)
{
- fprintf(rtl_dump_file,
- "Iterated dominance frontier: %d passes on %d regs.\n",
- passes, nregs);
+ fprintf (rtl_dump_file,
+ "Iterated dominance frontier: %d passes on %d regs.\n",
+ passes, nregs);
}
}
-
/* Insert the phi nodes. */
static void
-insert_phi_node (regno, bb)
- int regno, bb;
+insert_phi_node (int regno, int bb)
{
basic_block b = BASIC_BLOCK (bb);
edge e;
int npred, i;
rtvec vec;
rtx phi, reg;
+ rtx insn;
+ int end_p;
/* Find out how many predecessors there are. */
for (e = b->pred, npred = 0; e; e = e->pred_next)
if (npred == 0)
return;
- /* This is the register to which the phi function will be assinged. */
- reg = regno_reg_rtx[regno + FIRST_PSEUDO_REGISTER];
+ /* This is the register to which the phi function will be assigned. */
+ reg = regno_reg_rtx[regno];
/* Construct the arguments to the PHI node. The use of pc_rtx is just
a placeholder; we'll insert the proper value in rename_registers. */
phi = gen_rtx_PHI (VOIDmode, vec);
phi = gen_rtx_SET (VOIDmode, reg, phi);
- if (GET_CODE (b->head) == CODE_LABEL)
- emit_insn_after (phi, b->head);
- else
- b->head = emit_insn_before (phi, b->head);
+ insn = first_insn_after_basic_block_note (b);
+ end_p = PREV_INSN (insn) == b->end;
+ emit_insn_before (phi, insn);
+ if (end_p)
+ b->end = PREV_INSN (insn);
}
-
static void
-insert_phi_nodes (idfs, evals, nregs)
- sbitmap *idfs;
- sbitmap *evals ATTRIBUTE_UNUSED;
- int nregs;
+insert_phi_nodes (sbitmap *idfs, sbitmap *evals ATTRIBUTE_UNUSED, int nregs)
{
int reg;
for (reg = 0; reg < nregs; ++reg)
+ if (CONVERT_REGISTER_TO_SSA_P (reg))
{
int b;
EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b,
{
- if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
- reg + FIRST_PSEUDO_REGISTER))
+ if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, reg))
insert_phi_node (reg, b);
});
}
}
-/* Rename the registers to conform to SSA.
+/* Rename the registers to conform to SSA.
This is essentially the algorithm presented in Figure 7.8 of Morgan,
- with a few changes to reduce pattern search time in favour of a bit
+ with a few changes to reduce pattern search time in favor of a bit
more memory usage. */
-
/* One of these is created for each set. It will live in a list local
to its basic block for the duration of that block's processing. */
struct rename_set_data
{
struct rename_set_data *next;
+ /* This is the SET_DEST of the (first) SET that sets the REG. */
rtx *reg_loc;
- rtx set_dest;
+ /* This is what used to be at *REG_LOC. */
+ rtx old_reg;
+ /* This is the REG that will replace OLD_REG. It's set only
+ when the rename data is moved onto the DONE_RENAMES queue. */
rtx new_reg;
+ /* This is what to restore ssa_rename_to_lookup (old_reg) to. It is
+ usually the previous contents of ssa_rename_to_lookup (old_reg). */
rtx prev_reg;
+ /* This is the insn that contains all the SETs of the REG. */
+ rtx set_insn;
};
-static void new_registers_for_updates
- PARAMS ((struct rename_set_data *set_data,
- struct rename_set_data *old_set_data, rtx insn));
+/* This struct is used to pass information to callback functions while
+ renaming registers. */
+struct rename_context
+{
+ struct rename_set_data *new_renames;
+ struct rename_set_data *done_renames;
+ rtx current_insn;
+};
+
+/* Queue the rename of *REG_LOC. */
+static void
+create_delayed_rename (struct rename_context *c, rtx *reg_loc)
+{
+ struct rename_set_data *r;
+ r = xmalloc (sizeof(*r));
+
+ if (GET_CODE (*reg_loc) != REG
+ || !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc)))
+ abort ();
+
+ r->reg_loc = reg_loc;
+ r->old_reg = *reg_loc;
+ r->prev_reg = ssa_rename_to_lookup(r->old_reg);
+ r->set_insn = c->current_insn;
+ r->next = c->new_renames;
+ c->new_renames = r;
+}
/* This is part of a rather ugly hack to allow the pre-ssa regno to be
reused. If, during processing, a register has not yet been touched,
- ssa_rename_to[regno] will be NULL. Now, in the course of pushing
- and popping values from ssa_rename_to, when we would ordinarily
+ ssa_rename_to[regno][machno] will be NULL. Now, in the course of pushing
+ and popping values from ssa_rename_to, when we would ordinarily
pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
same as NULL, except that it signals that the original regno has
already been reused. */
#define RENAME_NO_RTX pc_rtx
-/* Part one of the first step of rename_block, called through for_each_rtx.
+/* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
+ applying all the renames on NEW_RENAMES. */
+
+static void
+apply_delayed_renames (struct rename_context *c)
+{
+ struct rename_set_data *r;
+ struct rename_set_data *last_r = NULL;
+
+ for (r = c->new_renames; r != NULL; r = r->next)
+ {
+ int new_regno;
+
+ /* Failure here means that someone has a PARALLEL that sets
+ a register twice (bad!). */
+ if (ssa_rename_to_lookup (r->old_reg) != r->prev_reg)
+ abort ();
+ /* Failure here means we have changed REG_LOC before applying
+ the rename. */
+ /* For the first set we come across, reuse the original regno. */
+ 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. */
+ r->prev_reg = RENAME_NO_RTX;
+ }
+ else
+ r->new_reg = gen_reg_rtx (GET_MODE (r->old_reg));
+ new_regno = REGNO (r->new_reg);
+ ssa_rename_to_insert (r->old_reg, r->new_reg);
+
+ if (new_regno >= (int) ssa_definition->num_elements)
+ {
+ int new_limit = new_regno * 5 / 4;
+ VARRAY_GROW (ssa_definition, new_limit);
+ }
+
+ VARRAY_RTX (ssa_definition, new_regno) = r->set_insn;
+ ssa_rename_from_insert (new_regno, r->old_reg);
+ last_r = r;
+ }
+ if (last_r != NULL)
+ {
+ last_r->next = c->done_renames;
+ c->done_renames = c->new_renames;
+ c->new_renames = NULL;
+ }
+}
+
+/* Part one of the first step of rename_block, called through for_each_rtx.
Mark pseudos that are set for later update. Transform uses of pseudos. */
static int
-rename_insn_1 (ptr, data)
- rtx *ptr;
- void *data;
+rename_insn_1 (rtx *ptr, void *data)
{
rtx x = *ptr;
- struct rename_set_data **set_datap = data;
+ struct rename_context *context = data;
if (x == NULL_RTX)
return 0;
rtx *destp = &SET_DEST (x);
rtx dest = SET_DEST (x);
- /* Subregs at word 0 are interesting. Subregs at word != 0 are
- presumed to be part of a contiguous multi-word set sequence. */
- while (GET_CODE (dest) == SUBREG
- && SUBREG_WORD (dest) == 0)
+ /* 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 = &SUBREG_REG (dest);
- dest = SUBREG_REG (dest);
+ destp = &XEXP (dest, 0);
+ dest = XEXP (dest, 0);
}
- if (GET_CODE (dest) == REG
- && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
+ /* 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
+ in the LHS. Handle these by changing
+ (set (subreg (reg foo)) ...)
+ into
+ (sequence [(set (reg foo_1) (reg foo))
+ (set (subreg (reg foo_1)) ...)])
+
+ 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
+ || GET_CODE (dest) == ZERO_EXTRACT)
+ {
+ rtx i, reg;
+ reg = dest;
+
+ while (GET_CODE (reg) == STRICT_LOW_PART
+ || GET_CODE (reg) == SUBREG
+ || GET_CODE (reg) == SIGN_EXTRACT
+ || GET_CODE (reg) == ZERO_EXTRACT)
+ reg = XEXP (reg, 0);
+
+ if (GET_CODE (reg) == REG
+ && CONVERT_REGISTER_TO_SSA_P (REGNO (reg)))
+ {
+ /* Generate (set reg reg), and do renaming on it so
+ that it becomes (set reg_1 reg_0), and we will
+ replace reg with reg_1 in the SUBREG. */
+
+ struct rename_set_data *saved_new_renames;
+ saved_new_renames = context->new_renames;
+ context->new_renames = NULL;
+ i = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
+ for_each_rtx (&i, rename_insn_1, data);
+ apply_delayed_renames (context);
+ context->new_renames = saved_new_renames;
+ }
+ }
+ 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
processing this insn. */
- struct rename_set_data *r;
- r = (struct rename_set_data *) xmalloc (sizeof(*r));
-
- r->reg_loc = destp;
- r->set_dest = SET_DEST (x);
- r->next = *set_datap;
- *set_datap = r;
+ create_delayed_rename (context, destp);
/* Since we do not wish to (directly) traverse the
SET_DEST, recurse through for_each_rtx for the SET_SRC
and return. */
- for_each_rtx (&SET_SRC (x), rename_insn_1, data);
+ if (GET_CODE (x) == SET)
+ for_each_rtx (&SET_SRC (x), rename_insn_1, data);
return -1;
}
}
case REG:
- if (REGNO (x) >= FIRST_PSEUDO_REGISTER
+ if (CONVERT_REGISTER_TO_SSA_P (REGNO (x))
&& REGNO (x) < ssa_max_reg_num)
{
- rtx new_reg = ssa_rename_to[REGNO(x) - FIRST_PSEUDO_REGISTER];
+ rtx new_reg = ssa_rename_to_lookup (x);
- if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
+ if (new_reg != RENAME_NO_RTX && new_reg != NULL_RTX)
{
if (GET_MODE (x) != GET_MODE (new_reg))
abort ();
*ptr = new_reg;
- /* ??? Mark for a new ssa_uses entry. */
}
- /* Else this is a use before a set. Warn? */
+ else
+ {
+ /* Undefined value used, rename it to a new pseudo register so
+ that it cannot conflict with an existing register. */
+ *ptr = gen_reg_rtx (GET_MODE (x));
+ }
}
return -1;
+ case CLOBBER:
+ /* There is considerable debate on how CLOBBERs ought to be
+ handled in SSA. For now, we're keeping the CLOBBERs, which
+ means that we don't really have SSA form. There are a couple
+ of proposals for how to fix this problem, but neither is
+ implemented yet. */
+ {
+ rtx dest = XCEXP (x, 0, CLOBBER);
+ if (REG_P (dest))
+ {
+ if (CONVERT_REGISTER_TO_SSA_P (REGNO (dest))
+ && REGNO (dest) < ssa_max_reg_num)
+ {
+ rtx new_reg = ssa_rename_to_lookup (dest);
+ if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
+ XCEXP (x, 0, CLOBBER) = new_reg;
+ }
+ /* Stop traversing. */
+ return -1;
+ }
+ else
+ /* Continue traversing. */
+ return 0;
+ }
+
case PHI:
/* Never muck with the phi. We do that elsewhere, special-like. */
return -1;
}
}
-/* Second part of the first step of rename_block. The portion of the list
- beginning at SET_DATA through OLD_SET_DATA contain the sets present in
- INSN. Update data structures accordingly. */
-
-static void
-new_registers_for_updates (set_data, old_set_data, insn)
- struct rename_set_data *set_data, *old_set_data;
- rtx insn;
+static rtx
+gen_sequence (void)
{
- while (set_data != old_set_data)
- {
- int regno, new_regno;
- rtx old_reg, new_reg, prev_reg;
-
- old_reg = *set_data->reg_loc;
- regno = REGNO (*set_data->reg_loc);
-
- /* For the first set we come across, reuse the original regno. */
- if (ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] == NULL_RTX)
- {
- new_reg = old_reg;
- prev_reg = RENAME_NO_RTX;
- }
- else
- {
- prev_reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER];
- new_reg = gen_reg_rtx (GET_MODE (old_reg));
- }
+ rtx first_insn = get_insns ();
+ rtx result;
+ rtx tem;
+ int i;
+ int len;
- set_data->new_reg = new_reg;
- set_data->prev_reg = prev_reg;
- new_regno = REGNO (new_reg);
- ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] = new_reg;
+ /* Count the insns in the chain. */
+ len = 0;
+ for (tem = first_insn; tem; tem = NEXT_INSN (tem))
+ len++;
- 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);
- ssa_rename_from = VARRAY_GROW (ssa_rename_from, new_limit);
- }
+ result = gen_rtx_SEQUENCE (VOIDmode, rtvec_alloc (len));
- VARRAY_RTX (ssa_definition, new_regno) = insn;
- VARRAY_RTX (ssa_rename_from, new_regno) = old_reg;
+ for (i = 0, tem = first_insn; tem; tem = NEXT_INSN (tem), i++)
+ XVECEXP (result, 0, i) = tem;
- set_data = set_data->next;
- }
+ return result;
}
static void
-rename_block (bb, idom)
- int bb;
- int *idom;
+rename_block (int bb, dominance_info idom)
{
basic_block b = BASIC_BLOCK (bb);
edge e;
rtx insn, next, last;
struct rename_set_data *set_data = NULL;
- int c;
+ basic_block c;
/* Step One: Walk the basic block, adding new names for sets and
replacing uses. */
-
+
next = b->head;
last = b->end;
do
{
insn = next;
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ if (INSN_P (insn))
{
- struct rename_set_data *old_set_data = set_data;
+ struct rename_context context;
+ context.done_renames = set_data;
+ context.new_renames = NULL;
+ context.current_insn = insn;
+
+ start_sequence ();
+ for_each_rtx (&PATTERN (insn), rename_insn_1, &context);
+ for_each_rtx (®_NOTES (insn), rename_insn_1, &context);
+
+ /* Sometimes, we end up with a sequence of insns that
+ SSA needs to treat as a single insn. Wrap these in a
+ SEQUENCE. (Any notes now get attached to the SEQUENCE,
+ not to the old version inner insn.) */
+ if (get_insns () != NULL_RTX)
+ {
+ rtx seq;
+ int i;
+
+ emit (PATTERN (insn));
+ seq = gen_sequence ();
+ /* We really want a SEQUENCE of SETs, not a SEQUENCE
+ of INSNs. */
+ for (i = 0; i < XVECLEN (seq, 0); i++)
+ XVECEXP (seq, 0, i) = PATTERN (XVECEXP (seq, 0, i));
+ PATTERN (insn) = seq;
+ }
+ end_sequence ();
- for_each_rtx (&PATTERN (insn), rename_insn_1, &set_data);
- for_each_rtx (®_NOTES (insn), rename_insn_1, &set_data);
-
- new_registers_for_updates (set_data, old_set_data, insn);
+ apply_delayed_renames (&context);
+ set_data = context.done_renames;
}
next = NEXT_INSN (insn);
if (e->dest == EXIT_BLOCK_PTR)
continue;
- insn = e->dest->head;
- if (GET_CODE (insn) == CODE_LABEL)
- insn = NEXT_INSN (insn);
+ insn = first_insn_after_basic_block_note (e->dest);
while (PHI_NODE_P (insn))
{
rtx phi = PATTERN (insn);
- unsigned int regno;
rtx reg;
/* Find out which of our outgoing registers this node is
- indended to replace. Note that if this not the first PHI
+ intended to replace. Note that if this is not the first PHI
node to have been created for this register, we have to
jump through rename links to figure out which register
we're talking about. This can easily be recognized by
noting that the regno is new to this pass. */
- regno = REGNO (SET_DEST (phi));
- if (regno >= ssa_max_reg_num)
- regno = REGNO (VARRAY_RTX (ssa_rename_from, regno));
- reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER];
+ reg = SET_DEST (phi);
+ if (REGNO (reg) >= ssa_max_reg_num)
+ reg = ssa_rename_from_lookup (REGNO (reg));
+ if (reg == NULL_RTX)
+ abort ();
+ reg = ssa_rename_to_lookup (reg);
/* It is possible for the variable to be uninitialized on
edges in. Reduce the arity of the PHI so that we don't
consider those edges. */
if (reg == NULL || reg == RENAME_NO_RTX)
{
- if (! remove_phi_alternative (phi, bb))
+ if (! remove_phi_alternative (phi, b))
abort ();
}
else
{
/* When we created the PHI nodes, we did not know what mode
- the register should be. Now that we've found an original,
- we can fill that in. */
+ the register should be. Now that we've found an original,
+ we can fill that in. */
if (GET_MODE (SET_DEST (phi)) == VOIDmode)
PUT_MODE (SET_DEST (phi), GET_MODE (reg));
else if (GET_MODE (SET_DEST (phi)) != GET_MODE (reg))
- abort();
+ abort ();
*phi_alternative (phi, bb) = reg;
- /* ??? Mark for a new ssa_uses entry. */
}
insn = NEXT_INSN (insn);
/* Step Three: Do the same to the children of this block in
dominator order. */
- for (c = 0; c < n_basic_blocks; ++c)
- if (idom[c] == bb)
- rename_block (c, idom);
+ FOR_EACH_BB (c)
+ if (get_immediate_dominator (idom, c)->index == bb)
+ rename_block (c->index, idom);
- /* Step Four: Update the sets to refer to their new register. */
+ /* Step Four: Update the sets to refer to their new register,
+ and restore ssa_rename_to to its previous state. */
while (set_data)
{
struct rename_set_data *next;
- rtx old_reg;
+ rtx old_reg = *set_data->reg_loc;
- old_reg = *set_data->reg_loc;
+ if (*set_data->reg_loc != set_data->old_reg)
+ abort ();
*set_data->reg_loc = set_data->new_reg;
- ssa_rename_to[REGNO (old_reg)-FIRST_PSEUDO_REGISTER]
- = set_data->prev_reg;
+
+ ssa_rename_to_insert (old_reg, set_data->prev_reg);
next = set_data->next;
free (set_data);
set_data = next;
- }
+ }
}
static void
-rename_registers (nregs, idom)
- int nregs;
- int *idom;
+rename_registers (int nregs, dominance_info idom)
{
VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
- VARRAY_RTX_INIT (ssa_uses, nregs * 3, "ssa_uses");
- VARRAY_RTX_INIT (ssa_rename_from, nregs * 3, "ssa_rename_from");
+ ssa_rename_from_initialize ();
- ssa_rename_to = (rtx *) alloca (nregs * sizeof(rtx));
- bzero ((char *) ssa_rename_to, nregs * sizeof(rtx));
+ ssa_rename_to_pseudo = alloca (nregs * sizeof(rtx));
+ memset (ssa_rename_to_pseudo, 0, nregs * sizeof(rtx));
+ memset (ssa_rename_to_hard, 0,
+ FIRST_PSEUDO_REGISTER * NUM_MACHINE_MODES * sizeof (rtx));
rename_block (0, idom);
- /* ??? Update basic_block_live_at_start, and other flow info
+ /* ??? Update basic_block_live_at_start, and other flow info
as needed. */
- ssa_rename_to = NULL;
+ ssa_rename_to_pseudo = NULL;
}
-
/* The main entry point for moving to SSA. */
void
-convert_to_ssa()
+convert_to_ssa (void)
{
/* Element I is the set of blocks that set register I. */
sbitmap *evals;
/* Dominator bitmaps. */
- sbitmap *dominators;
sbitmap *dfs;
sbitmap *idfs;
/* Element I is the immediate dominator of block I. */
- int *idom;
+ dominance_info idom;
int nregs;
- find_basic_blocks (get_insns (), max_reg_num(), NULL);
- /* The dominator algorithms assume all blocks are reachable, clean
- up first. */
- cleanup_cfg (get_insns ());
- life_analysis (get_insns (), max_reg_num (), NULL, 1);
+ basic_block bb;
- /* Compute dominators. */
- dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
- compute_flow_dominators (dominators, NULL);
+ /* Don't do it twice. */
+ if (in_ssa_form)
+ abort ();
- idom = (int *) alloca (n_basic_blocks * sizeof (int));
- memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
- simplify_to_immediate_dominators (idom, dominators);
+ /* 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);
- sbitmap_vector_free (dominators);
+ idom = calculate_dominance_info (CDI_DOMINATORS);
if (rtl_dump_file)
{
- int i;
fputs (";; Immediate Dominators:\n", rtl_dump_file);
- for (i = 0; i < n_basic_blocks; ++i)
- fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]);
+ FOR_EACH_BB (bb)
+ fprintf (rtl_dump_file, ";\t%3d = %3d\n", bb->index,
+ get_immediate_dominator (idom, bb)->index);
fflush (rtl_dump_file);
}
/* Compute dominance frontiers. */
- dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
+ dfs = sbitmap_vector_alloc (last_basic_block, last_basic_block);
compute_dominance_frontiers (dfs, idom);
if (rtl_dump_file)
{
dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
- "; Basic Block", dfs, n_basic_blocks);
+ "; Basic Block", dfs, last_basic_block);
fflush (rtl_dump_file);
}
/* Compute register evaluations. */
- ssa_max_reg_num = max_reg_num();
- nregs = ssa_max_reg_num - FIRST_PSEUDO_REGISTER;
- evals = sbitmap_vector_alloc (nregs, n_basic_blocks);
+ ssa_max_reg_num = max_reg_num ();
+ nregs = ssa_max_reg_num;
+ evals = sbitmap_vector_alloc (nregs, last_basic_block);
find_evaluations (evals, nregs);
/* Compute the iterated dominance frontier for each register. */
- idfs = sbitmap_vector_alloc (nregs, n_basic_blocks);
+ idfs = sbitmap_vector_alloc (nregs, last_basic_block);
compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);
if (rtl_dump_file)
{
dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
- "; Register-FIRST_PSEUDO_REGISTER", idfs, nregs);
+ "; Register", idfs, nregs);
fflush (rtl_dump_file);
}
sbitmap_vector_free (dfs);
sbitmap_vector_free (evals);
sbitmap_vector_free (idfs);
-}
-
-
-/* This is intended to be the FIND of a UNION/FIND algorithm managing
- the partitioning of the pseudos. Glancing through the rest of the
- global optimizations, it seems things will work out best if the
- partition is set up just before convert_from_ssa is called. See
- section 11.4 of Morgan.
-
- ??? Morgan's algorithm, perhaps with some care, may allow copy
- propagation to happen concurrently with the conversion from SSA.
-
- However, it presents potential problems with critical edges -- to
- split or not to split. He mentions beginning the partitioning by
- unioning registers associated by a PHI across abnormal critical
- edges. This is the approache taken here. It is unclear to me how
- we are able to do that arbitrarily, though.
-
- Alternately, Briggs presents an algorithm in which critical edges
- need not be split, at the expense of the creation of new pseudos,
- and the need for some concurrent register renaming. Moreover, it
- is ameanable for modification such that the instructions can be
- placed anywhere in the target block, which solves the before-call
- placement problem. However, I don't immediately see how we could
- do that concurrently with copy propoagation.
+ in_ssa_form = 1;
- More study is required. */
-
-
-/*
- * Eliminate the PHI across the edge from C to B.
- */
+ reg_scan (get_insns (), max_reg_num (), 1);
+ free_dominance_info (idom);
+}
/* REG is the representative temporary of its partition. Add it to the
set of nodes to be processed, if it hasn't been already. Return the
index of this register in the node set. */
static inline int
-ephi_add_node (reg, nodes, n_nodes)
- rtx reg, *nodes;
- int *n_nodes;
+ephi_add_node (rtx reg, rtx *nodes, int *n_nodes)
{
int i;
for (i = *n_nodes - 1; i >= 0; --i)
/* Part one of the topological sort. This is a forward (downward) search
through the graph collecting a stack of nodes to process. Assuming no
cycles, the nodes at top of the stack when we are finished will have
- no other dependancies. */
+ no other dependencies. */
static int *
-ephi_forward (t, visited, succ, tstack)
- int t;
- sbitmap visited;
- sbitmap *succ;
- int *tstack;
+ephi_forward (int t, sbitmap visited, sbitmap *succ, int *tstack)
{
int s;
EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
{
if (! TEST_BIT (visited, s))
- tstack = ephi_forward (s, visited, succ, tstack);
+ tstack = ephi_forward (s, visited, succ, tstack);
});
*tstack++ = t;
a cycle in the graph, copying the data forward as we go. */
static void
-ephi_backward (t, visited, pred, nodes)
- int t;
- sbitmap visited, *pred;
- rtx *nodes;
+ephi_backward (int t, sbitmap visited, sbitmap *pred, rtx *nodes)
{
int p;
and any cycle of which it is a member. */
static void
-ephi_create (t, visited, pred, succ, nodes)
- int t;
- sbitmap visited, *pred, *succ;
- rtx *nodes;
+ephi_create (int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes)
{
rtx reg_u = NULL_RTX;
int unvisited_predecessors = 0;
int p;
/* Iterate through the predecessor list looking for unvisited nodes.
- If there are any, we have a cycle, and must deal with that. At
+ If there are any, we have a cycle, and must deal with that. At
the same time, look for a visited predecessor. If there is one,
we won't need to create a temporary. */
emit_move_insn (nodes[p], reg_u);
}
});
- }
- else
+ }
+ else
{
/* No cycle. Just copy the value from a successor. */
/* Convert the edge to normal form. */
static void
-eliminate_phi (e, reg_partition)
- edge e;
- partition reg_partition;
+eliminate_phi (edge e, partition reg_partition)
{
int n_nodes;
sbitmap *pred, *succ;
/* Collect an upper bound on the number of registers needing processing. */
- insn = e->dest->head;
- if (GET_CODE (insn) == CODE_LABEL)
- insn = next_nonnote_insn (insn);
+ insn = first_insn_after_basic_block_note (e->dest);
n_nodes = 0;
while (PHI_NODE_P (insn))
if (n_nodes == 0)
return;
- /* Build the auxilliary graph R(B).
+ /* Build the auxiliary graph R(B).
The nodes of the graph are the members of the register partition
present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
- nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
+ nodes = alloca (n_nodes * sizeof(rtx));
pred = sbitmap_vector_alloc (n_nodes, n_nodes);
succ = sbitmap_vector_alloc (n_nodes, n_nodes);
sbitmap_vector_zero (pred, n_nodes);
sbitmap_vector_zero (succ, n_nodes);
- insn = e->dest->head;
- if (GET_CODE (insn) == CODE_LABEL)
- insn = next_nonnote_insn (insn);
+ insn = first_insn_after_basic_block_note (e->dest);
n_nodes = 0;
for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
reg = *preg;
if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
- abort();
+ abort ();
- /* If the two registers are already in the same partition,
+ reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
+ tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
+ /* If the two registers are already in the same partition,
nothing will need to be done. */
- if (partition_find (reg_partition, REGNO (reg))
- != partition_find (reg_partition, REGNO (tgt)))
+ if (reg != tgt)
{
int ireg, itgt;
visited = sbitmap_alloc (n_nodes);
sbitmap_zero (visited);
- tstack = stack = (int *) alloca (n_nodes * sizeof (int));
+ tstack = stack = alloca (n_nodes * sizeof (int));
for (i = 0; i < n_nodes; ++i)
if (! TEST_BIT (visited, i))
sbitmap_zero (visited);
- /* As we find a solution to the tsort, collect the implementation
+ /* As we find a solution to the tsort, collect the implementation
insns in a sequence. */
start_sequence ();
-
+
while (tstack != stack)
{
i = *--tstack;
ephi_create (i, visited, pred, succ, nodes);
}
- insn = gen_sequence ();
+ insn = get_insns ();
end_sequence ();
insert_insn_on_edge (insn, e);
if (rtl_dump_file)
sbitmap_vector_free (succ);
}
-
/* For basic block B, consider all phi insns which provide an
alternative corresponding to an incoming abnormal critical edge.
Place the phi alternative corresponding to that abnormal critical
- edge in the same register class as the destination of the set.
+ edge in the same register class as the destination of the set.
From Morgan, p. 178:
- For each abnormal critical edge (C, B),
- if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
- and C is the ith predecessor of B,
- then T0 and Ti must be equivalent.
+ For each abnormal critical edge (C, B),
+ if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
+ and C is the ith predecessor of B,
+ then T0 and Ti must be equivalent.
- Return non-zero iff any such cases were found for which the two
+ Return nonzero iff any such cases were found for which the two
regs were not already in the same class. */
static int
-make_regs_equivalent_over_bad_edges (bb, reg_partition)
- int bb;
- partition reg_partition;
+make_regs_equivalent_over_bad_edges (int bb, partition reg_partition)
{
int changed = 0;
basic_block b = BASIC_BLOCK (bb);
- rtx phi = b->head;
+ rtx phi;
/* Advance to the first phi node. */
- if (GET_CODE (phi) == CODE_LABEL)
- phi = next_nonnote_insn (phi);
+ phi = first_insn_after_basic_block_note (b);
/* Scan all the phi nodes. */
- for (;
+ for (;
PHI_NODE_P (phi);
phi = next_nonnote_insn (phi))
{
rtx set = PATTERN (phi);
rtx tgt = SET_DEST (set);
- /* The set target is expected to be a pseudo. */
- if (GET_CODE (tgt) != REG
- || REGNO (tgt) < FIRST_PSEUDO_REGISTER)
+ /* The set target is expected to be an SSA register. */
+ if (GET_CODE (tgt) != REG
+ || !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt)))
abort ();
tgt_regno = REGNO (tgt);
/* Scan incoming abnormal critical edges. */
for (e = b->pred; e; e = e->pred_next)
- if (e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL))
+ if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
{
rtx *alt = phi_alternative (set, e->src->index);
int alt_regno;
if (alt == 0)
continue;
- /* The phi alternative is expected to be a pseudo. */
- if (GET_CODE (*alt) != REG
- || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
+ /* The phi alternative is expected to be an SSA register. */
+ if (GET_CODE (*alt) != REG
+ || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
abort ();
alt_regno = REGNO (*alt);
/* If the set destination and the phi alternative aren't
already in the same class... */
- if (partition_find (reg_partition, tgt_regno)
+ if (partition_find (reg_partition, tgt_regno)
!= partition_find (reg_partition, alt_regno))
{
/* ... make them such. */
- partition_union (reg_partition,
+ if (conflicting_hard_regs_p (tgt_regno, alt_regno))
+ /* It is illegal to unify a hard register with a
+ different register. */
+ abort ();
+
+ partition_union (reg_partition,
tgt_regno, alt_regno);
++changed;
}
return changed;
}
-
/* Consider phi insns in basic block BB pairwise. If the set target
- of both isns are equivalent pseudos, make the corresponding phi
+ of both insns are equivalent pseudos, make the corresponding phi
alternatives in each phi corresponding equivalent.
Return nonzero if any new register classes were unioned. */
static int
-make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
- int bb;
- partition reg_partition;
+make_equivalent_phi_alternatives_equivalent (int bb, partition reg_partition)
{
int changed = 0;
- rtx phi = BLOCK_HEAD (bb);
basic_block b = BASIC_BLOCK (bb);
+ rtx phi;
/* Advance to the first phi node. */
- if (GET_CODE (phi) == CODE_LABEL)
- phi = next_nonnote_insn (phi);
+ phi = first_insn_after_basic_block_note (b);
/* Scan all the phi nodes. */
- for (;
+ for (;
PHI_NODE_P (phi);
phi = next_nonnote_insn (phi))
{
rtx set2 = PATTERN (phi2);
/* The regno of the destination of the set. */
int tgt2_regno = REGNO (SET_DEST (set2));
-
+
/* Are the set destinations equivalent regs? */
if (partition_find (reg_partition, tgt_regno) ==
partition_find (reg_partition, tgt2_regno))
for (e = b->pred; e; e = e->pred_next)
{
int pred_block = e->src->index;
- /* Identify the phi altnernatives from both phi
+ /* Identify the phi alternatives from both phi
nodes corresponding to this edge. */
rtx *alt = phi_alternative (set, pred_block);
rtx *alt2 = phi_alternative (set2, pred_block);
if (alt == 0 || alt2 == 0)
continue;
- /* Both alternatives should be pseudos. */
+ /* Both alternatives should be SSA registers. */
if (GET_CODE (*alt) != REG
- || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
+ || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
abort ();
if (GET_CODE (*alt2) != REG
- || REGNO (*alt2) < FIRST_PSEUDO_REGISTER)
+ || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2)))
abort ();
- /* If the altneratives aren't already in the same
- class ... */
- if (partition_find (reg_partition, REGNO (*alt))
+ /* If the alternatives aren't already in the same
+ class ... */
+ if (partition_find (reg_partition, REGNO (*alt))
!= partition_find (reg_partition, REGNO (*alt2)))
{
/* ... make them so. */
- partition_union (reg_partition,
+ if (conflicting_hard_regs_p (REGNO (*alt), REGNO (*alt2)))
+ /* It is illegal to unify a hard register with
+ a different register. */
+ abort ();
+
+ partition_union (reg_partition,
REGNO (*alt), REGNO (*alt2));
++changed;
}
return changed;
}
-
/* Compute a conservative partition of outstanding pseudo registers.
See Morgan 7.3.1. */
static partition
-compute_conservative_reg_partition ()
+compute_conservative_reg_partition (void)
{
- int bb;
+ basic_block bb;
int changed = 0;
/* We don't actually work with hard registers, but it's easier to
carry them around anyway rather than constantly doing register
number arithmetic. */
- partition p =
- partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);
+ partition p =
+ partition_new (ssa_definition->num_elements);
/* The first priority is to make sure registers that might have to
be copied on abnormal critical edges are placed in the same
partition. This saves us from having to split abnormal critical
edges. */
- for (bb = n_basic_blocks; --bb >= 0; )
- changed += make_regs_equivalent_over_bad_edges (bb, p);
-
+ FOR_EACH_BB_REVERSE (bb)
+ changed += make_regs_equivalent_over_bad_edges (bb->index, p);
+
/* Now we have to insure that corresponding arguments of phi nodes
assigning to corresponding regs are equivalent. Iterate until
nothing changes. */
while (changed > 0)
{
changed = 0;
- for (bb = n_basic_blocks; --bb >= 0; )
- changed += make_equivalent_phi_alternatives_equivalent (bb, p);
+ FOR_EACH_BB_REVERSE (bb)
+ changed += make_equivalent_phi_alternatives_equivalent (bb->index, p);
}
return p;
}
+/* The following functions compute a register partition that attempts
+ to eliminate as many reg copies and phi node copies as possible by
+ coalescing registers. This is the strategy:
-/* Rename regs in insn PTR that are equivalent. DATA is the register
- partition which specifies equivalences. */
+ 1. As in the conservative case, the top priority is to coalesce
+ registers that otherwise would cause copies to be placed on
+ abnormal critical edges (which isn't possible).
+
+ 2. Figure out which regs are involved (in the LHS or RHS) of
+ copies and phi nodes. Compute conflicts among these regs.
+
+ 3. Walk around the instruction stream, placing two regs in the
+ same class of the partition if one appears on the LHS and the
+ other on the RHS of a copy or phi node and the two regs don't
+ conflict. The conflict information of course needs to be
+ updated.
+
+ 4. If anything has changed, there may be new opportunities to
+ coalesce regs, so go back to 2.
+*/
+
+/* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
+ same class of partition P, if they aren't already. Update
+ CONFLICTS appropriately.
+
+ Returns one if REG1 and REG2 were placed in the same class but were
+ not previously; zero otherwise.
+
+ See Morgan figure 11.15. */
static int
-rename_equivalent_regs_in_insn (ptr, data)
- rtx *ptr;
- void* data;
+coalesce_if_unconflicting (partition p, conflict_graph conflicts,
+ int reg1, int reg2)
{
- rtx x = *ptr;
- partition reg_partition = (partition) data;
+ int reg;
- if (x == NULL_RTX)
+ /* Work only on SSA registers. */
+ if (!CONVERT_REGISTER_TO_SSA_P (reg1) || !CONVERT_REGISTER_TO_SSA_P (reg2))
return 0;
- switch (GET_CODE (x))
+ /* Find the canonical regs for the classes containing REG1 and
+ REG2. */
+ reg1 = partition_find (p, reg1);
+ reg2 = partition_find (p, reg2);
+
+ /* If they're already in the same class, there's nothing to do. */
+ if (reg1 == reg2)
+ return 0;
+
+ /* If the regs conflict, our hands are tied. */
+ if (conflicting_hard_regs_p (reg1, reg2) ||
+ conflict_graph_conflict_p (conflicts, reg1, reg2))
+ return 0;
+
+ /* We're good to go. Put the regs in the same partition. */
+ partition_union (p, reg1, reg2);
+
+ /* Find the new canonical reg for the merged class. */
+ reg = partition_find (p, reg1);
+
+ /* Merge conflicts from the two previous classes. */
+ conflict_graph_merge_regs (conflicts, reg, reg1);
+ conflict_graph_merge_regs (conflicts, reg, reg2);
+
+ return 1;
+}
+
+/* For each register copy insn in basic block BB, place the LHS and
+ RHS regs in the same class in partition P if they do not conflict
+ according to CONFLICTS.
+
+ Returns the number of changes that were made to P.
+
+ See Morgan figure 11.14. */
+
+static int
+coalesce_regs_in_copies (basic_block bb, partition p, conflict_graph conflicts)
+{
+ int changed = 0;
+ rtx insn;
+ rtx end = bb->end;
+
+ /* Scan the instruction stream of the block. */
+ for (insn = bb->head; insn != end; insn = NEXT_INSN (insn))
{
- case SET:
- {
- rtx *destp = &SET_DEST (x);
- rtx dest = SET_DEST (x);
+ rtx pattern;
+ rtx src;
+ rtx dest;
+
+ /* If this isn't a set insn, go to the next insn. */
+ if (GET_CODE (insn) != INSN)
+ continue;
+ pattern = PATTERN (insn);
+ if (GET_CODE (pattern) != SET)
+ continue;
+
+ src = SET_SRC (pattern);
+ dest = SET_DEST (pattern);
+
+ /* We're only looking for copies. */
+ if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
+ continue;
+
+ /* Coalesce only if the reg modes are the same. As long as
+ each reg's rtx is unique, it can have only one mode, so two
+ pseudos of different modes can't be coalesced into one.
+
+ FIXME: We can probably get around this by inserting SUBREGs
+ where appropriate, but for now we don't bother. */
+ if (GET_MODE (src) != GET_MODE (dest))
+ continue;
+
+ /* Found a copy; see if we can use the same reg for both the
+ source and destination (and thus eliminate the copy,
+ ultimately). */
+ changed += coalesce_if_unconflicting (p, conflicts,
+ REGNO (src), REGNO (dest));
+ }
+
+ return changed;
+}
+
+struct phi_coalesce_context
+{
+ partition p;
+ conflict_graph conflicts;
+ int changed;
+};
+
+/* Callback function for for_each_successor_phi. If the set
+ destination and the phi alternative regs do not conflict, place
+ them in the same partition class. DATA is a pointer to a
+ phi_coalesce_context struct. */
+
+static int
+coalesce_reg_in_phi (rtx insn ATTRIBUTE_UNUSED, int dest_regno,
+ int src_regno, void *data)
+{
+ struct phi_coalesce_context *context =
+ (struct phi_coalesce_context *) data;
+
+ /* Attempt to use the same reg, if they don't conflict. */
+ context->changed
+ += coalesce_if_unconflicting (context->p, context->conflicts,
+ dest_regno, src_regno);
+ return 0;
+}
+
+/* For each alternative in a phi function corresponding to basic block
+ BB (in phi nodes in successor block to BB), place the reg in the
+ phi alternative and the reg to which the phi value is set into the
+ same class in partition P, if allowed by CONFLICTS.
+
+ Return the number of changes that were made to P.
+
+ See Morgan figure 11.14. */
+
+static int
+coalesce_regs_in_successor_phi_nodes (basic_block bb, partition p,
+ conflict_graph conflicts)
+{
+ struct phi_coalesce_context context;
+ context.p = p;
+ context.conflicts = conflicts;
+ context.changed = 0;
+
+ for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);
+
+ return context.changed;
+}
+
+/* Compute and return a partition of pseudos. Where possible,
+ non-conflicting pseudos are placed in the same class.
+
+ The caller is responsible for deallocating the returned partition. */
+
+static partition
+compute_coalesced_reg_partition (void)
+{
+ basic_block bb;
+ int changed = 0;
+ regset_head phi_set_head;
+ regset phi_set = &phi_set_head;
+
+ partition p =
+ partition_new (ssa_definition->num_elements);
+
+ /* The first priority is to make sure registers that might have to
+ be copied on abnormal critical edges are placed in the same
+ partition. This saves us from having to split abnormal critical
+ edges (which can't be done). */
+ FOR_EACH_BB_REVERSE (bb)
+ make_regs_equivalent_over_bad_edges (bb->index, p);
+
+ INIT_REG_SET (phi_set);
+
+ do
+ {
+ conflict_graph conflicts;
+
+ changed = 0;
+
+ /* Build the set of registers involved in phi nodes, either as
+ arguments to the phi function or as the target of a set. */
+ CLEAR_REG_SET (phi_set);
+ mark_phi_and_copy_regs (phi_set);
+
+ /* Compute conflicts. */
+ conflicts = conflict_graph_compute (phi_set, p);
+
+ /* FIXME: Better would be to process most frequently executed
+ blocks first, so that most frequently executed copies would
+ be more likely to be removed by register coalescing. But any
+ order will generate correct, if non-optimal, results. */
+ FOR_EACH_BB_REVERSE (bb)
+ {
+ changed += coalesce_regs_in_copies (bb, p, conflicts);
+ changed +=
+ coalesce_regs_in_successor_phi_nodes (bb, p, conflicts);
+ }
+
+ conflict_graph_delete (conflicts);
+ }
+ while (changed > 0);
+
+ FREE_REG_SET (phi_set);
+
+ return p;
+}
+
+/* Mark the regs in a phi node. PTR is a phi expression or one of its
+ components (a REG or a CONST_INT). DATA is a reg set in which to
+ set all regs. Called from for_each_rtx. */
- /* Subregs at word 0 are interesting. Subregs at word != 0 are
- presumed to be part of a contiguous multi-word set sequence. */
- while (GET_CODE (dest) == SUBREG
- && SUBREG_WORD (dest) == 0)
+static int
+mark_reg_in_phi (rtx *ptr, void *data)
+{
+ rtx expr = *ptr;
+ regset set = (regset) data;
+
+ switch (GET_CODE (expr))
+ {
+ case REG:
+ SET_REGNO_REG_SET (set, REGNO (expr));
+ /* Fall through. */
+ case CONST_INT:
+ case PHI:
+ return 0;
+ default:
+ abort ();
+ }
+}
+
+/* Mark in PHI_SET all pseudos that are used in a phi node -- either
+ set from a phi expression, or used as an argument in one. Also
+ mark regs that are the source or target of a reg copy. Uses
+ ssa_definition. */
+
+static void
+mark_phi_and_copy_regs (regset phi_set)
+{
+ unsigned int reg;
+
+ /* Scan the definitions of all regs. */
+ for (reg = 0; reg < VARRAY_SIZE (ssa_definition); ++reg)
+ if (CONVERT_REGISTER_TO_SSA_P (reg))
+ {
+ rtx insn = VARRAY_RTX (ssa_definition, reg);
+ rtx pattern;
+ rtx src;
+
+ 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
+ copies. */
+ if (GET_CODE (pattern) != SET)
+ continue;
+ src = SET_SRC (pattern);
+
+ if (GET_CODE (src) == REG)
{
- destp = &SUBREG_REG (dest);
- dest = SUBREG_REG (dest);
+ /* It's a reg copy. */
+ SET_REGNO_REG_SET (phi_set, reg);
+ SET_REGNO_REG_SET (phi_set, REGNO (src));
}
-
- if (GET_CODE (dest) == REG
- && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
+ else if (GET_CODE (src) == PHI)
{
- /* Got a pseudo; replace it. */
- int regno = REGNO (dest);
- int new_regno = partition_find (reg_partition, regno);
- if (regno != new_regno)
- *destp = regno_reg_rtx [new_regno];
-
- for_each_rtx (&SET_SRC (x),
- rename_equivalent_regs_in_insn,
- data);
- return -1;
+ /* It's a phi node. Mark the reg being set. */
+ SET_REGNO_REG_SET (phi_set, reg);
+ /* Mark the regs used in the phi function. */
+ for_each_rtx (&src, mark_reg_in_phi, phi_set);
}
-
- /* Otherwise, this was not an interesting destination. Continue
- on, marking uses as normal. */
- return 0;
+ /* ... else nothing to do. */
}
+}
+
+/* Rename regs in insn PTR that are equivalent. DATA is the register
+ partition which specifies equivalences. */
+static int
+rename_equivalent_regs_in_insn (rtx *ptr, void* data)
+{
+ rtx x = *ptr;
+ partition reg_partition = (partition) data;
+
+ if (x == NULL_RTX)
+ return 0;
+
+ switch (GET_CODE (x))
+ {
case REG:
- if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
+ if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
{
- int regno = REGNO (x);
- int new_regno = partition_find (reg_partition, regno);
- if (regno != new_regno)
+ unsigned int regno = REGNO (x);
+ unsigned int new_regno = partition_find (reg_partition, regno);
+ rtx canonical_element_rtx = ssa_rename_from_lookup (new_regno);
+
+ if (canonical_element_rtx != NULL_RTX &&
+ HARD_REGISTER_P (canonical_element_rtx))
+ {
+ if (REGNO (canonical_element_rtx) != regno)
+ *ptr = canonical_element_rtx;
+ }
+ else if (regno != new_regno)
{
rtx new_reg = regno_reg_rtx[new_regno];
if (GET_MODE (x) != GET_MODE (new_reg))
}
}
+/* Record the register's canonical element stored in SRFP in the
+ canonical_elements sbitmap packaged in DATA. This function is used
+ as a callback function for traversing ssa_rename_from. */
+
+static int
+record_canonical_element_1 (void **srfp, void *data)
+{
+ unsigned int reg = ((ssa_rename_from_pair *) *srfp)->reg;
+ sbitmap canonical_elements =
+ ((struct ssa_rename_from_hash_table_data *) data)->canonical_elements;
+ partition reg_partition =
+ ((struct ssa_rename_from_hash_table_data *) data)->reg_partition;
+
+ SET_BIT (canonical_elements, partition_find (reg_partition, reg));
+ return 1;
+}
+
+/* For each class in the REG_PARTITION corresponding to a particular
+ hard register and machine mode, check that there are no other
+ classes with the same hard register and machine mode. Returns
+ nonzero if this is the case, i.e., the partition is acceptable. */
-/* Rename regs that are equivalent in REG_PARTITION. */
+static int
+check_hard_regs_in_partition (partition reg_partition)
+{
+ /* CANONICAL_ELEMENTS has a nonzero bit if a class with the given register
+ number and machine mode has already been seen. This is a
+ problem with the partition. */
+ sbitmap canonical_elements;
+ int element_index;
+ int already_seen[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
+ int reg;
+ int mach_mode;
+
+ /* Collect a list of canonical elements. */
+ canonical_elements = sbitmap_alloc (max_reg_num ());
+ sbitmap_zero (canonical_elements);
+ ssa_rename_from_traverse (&record_canonical_element_1,
+ canonical_elements, reg_partition);
+
+ /* We have not seen any hard register uses. */
+ for (reg = 0; reg < FIRST_PSEUDO_REGISTER; ++reg)
+ for (mach_mode = 0; mach_mode < NUM_MACHINE_MODES; ++mach_mode)
+ already_seen[reg][mach_mode] = 0;
+
+ /* Check for classes with the same hard register and machine mode. */
+ EXECUTE_IF_SET_IN_SBITMAP (canonical_elements, 0, element_index,
+ {
+ rtx hard_reg_rtx = ssa_rename_from_lookup (element_index);
+ if (hard_reg_rtx != NULL_RTX &&
+ HARD_REGISTER_P (hard_reg_rtx) &&
+ already_seen[REGNO (hard_reg_rtx)][GET_MODE (hard_reg_rtx)] != 0)
+ /* Two distinct partition classes should be mapped to the same
+ hard register. */
+ return 0;
+ });
+
+ sbitmap_free (canonical_elements);
+
+ return 1;
+}
+
+/* Rename regs that are equivalent in REG_PARTITION. Also collapse
+ any SEQUENCE insns. */
static void
-rename_equivalent_regs (reg_partition)
- partition reg_partition;
+rename_equivalent_regs (partition reg_partition)
{
- int bb;
+ basic_block b;
- for (bb = n_basic_blocks; --bb >= 0; )
+ FOR_EACH_BB_REVERSE (b)
{
- basic_block b = BASIC_BLOCK (bb);
rtx next = b->head;
rtx last = b->end;
rtx insn;
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,
+ for_each_rtx (&PATTERN (insn),
+ rename_equivalent_regs_in_insn,
reg_partition);
- for_each_rtx (®_NOTES (insn),
- rename_equivalent_regs_in_insn,
+ for_each_rtx (®_NOTES (insn),
+ rename_equivalent_regs_in_insn,
reg_partition);
+
+ if (GET_CODE (PATTERN (insn)) == SEQUENCE)
+ {
+ rtx s = PATTERN (insn);
+ int slen = XVECLEN (s, 0);
+ int i;
+
+ if (slen <= 1)
+ abort ();
+
+ PATTERN (insn) = XVECEXP (s, 0, slen-1);
+ for (i = 0; i < slen - 1; i++)
+ emit_insn_before (XVECEXP (s, 0, i), insn);
+ }
}
next = NEXT_INSN (insn);
}
}
-
/* The main entry point for moving from SSA. */
void
-convert_from_ssa()
+convert_from_ssa (void)
{
- int bb;
+ basic_block b, bb;
partition reg_partition;
-
- reg_partition = compute_conservative_reg_partition ();
+ rtx insns = get_insns ();
+
+ /* 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. */
+ if (conservative_reg_partition)
+ reg_partition = compute_conservative_reg_partition ();
+ else
+ reg_partition = compute_coalesced_reg_partition ();
+
+ if (!check_hard_regs_in_partition (reg_partition))
+ /* Two separate partitions should correspond to the same hard
+ register but do not. */
+ abort ();
+
rename_equivalent_regs (reg_partition);
/* Eliminate the PHI nodes. */
- for (bb = n_basic_blocks; --bb >= 0; )
+ FOR_EACH_BB_REVERSE (b)
{
- basic_block b = BASIC_BLOCK (bb);
edge e;
for (e = b->pred; e; e = e->pred_next)
partition_delete (reg_partition);
/* Actually delete the PHI nodes. */
- for (bb = n_basic_blocks; --bb >= 0; )
+ FOR_EACH_BB_REVERSE (bb)
{
- rtx insn = BLOCK_HEAD (bb);
- int start = (GET_CODE (insn) != CODE_LABEL);
+ rtx insn = bb->head;
- if (! start)
- insn = next_nonnote_insn (insn);
- while (PHI_NODE_P (insn))
+ while (1)
{
- insn = delete_insn (insn);
- if (GET_CODE (insn) == NOTE)
- insn = next_nonnote_insn (insn);
+ /* If this is a PHI node delete it. */
+ if (PHI_NODE_P (insn))
+ {
+ if (insn == bb->end)
+ bb->end = PREV_INSN (insn);
+ insn = delete_insn (insn);
+ }
+ /* Since all the phi nodes come at the beginning of the
+ block, if we find an ordinary insn, we can stop looking
+ for more phi nodes. */
+ else if (INSN_P (insn))
+ break;
+ /* If we've reached the end of the block, stop. */
+ else if (insn == bb->end)
+ break;
+ else
+ insn = NEXT_INSN (insn);
}
- if (start)
- BLOCK_HEAD (bb) = insn;
}
/* Commit all the copy nodes needed to convert out of SSA form. */
commit_edge_insertions ();
+ in_ssa_form = 0;
+
count_or_remove_death_notes (NULL, 1);
+
+ /* Deallocate the data structures. */
+ ssa_definition = 0;
+ ssa_rename_from_free ();
+}
+
+/* Scan phi nodes in successors to BB. For each such phi node that
+ has a phi alternative value corresponding to BB, invoke FN. FN
+ is passed the entire phi node insn, the regno of the set
+ destination, the regno of the phi argument corresponding to BB,
+ and DATA.
+
+ If FN ever returns nonzero, stops immediately and returns this
+ value. Otherwise, returns zero. */
+
+int
+for_each_successor_phi (basic_block bb, successor_phi_fn fn, void *data)
+{
+ edge e;
+
+ if (bb == EXIT_BLOCK_PTR)
+ return 0;
+
+ /* Scan outgoing edges. */
+ for (e = bb->succ; e != NULL; e = e->succ_next)
+ {
+ rtx insn;
+
+ basic_block successor = e->dest;
+ if (successor == ENTRY_BLOCK_PTR
+ || successor == EXIT_BLOCK_PTR)
+ continue;
+
+ /* Advance to the first non-label insn of the successor block. */
+ insn = first_insn_after_basic_block_note (successor);
+
+ if (insn == NULL)
+ continue;
+
+ /* Scan phi nodes in the successor. */
+ for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
+ {
+ int result;
+ rtx phi_set = PATTERN (insn);
+ rtx *alternative = phi_alternative (phi_set, bb->index);
+ rtx phi_src;
+
+ /* This phi function may not have an alternative
+ corresponding to the incoming edge, indicating the
+ assigned variable is not defined along the edge. */
+ if (alternative == NULL)
+ continue;
+ phi_src = *alternative;
+
+ /* Invoke the callback. */
+ result = (*fn) (insn, REGNO (SET_DEST (phi_set)),
+ REGNO (phi_src), data);
+
+ /* Terminate if requested. */
+ if (result != 0)
+ return result;
+ }
+ }
+
+ return 0;
+}
+
+/* Assuming the ssa_rename_from mapping has been established, yields
+ nonzero if 1) only one SSA register of REG1 and REG2 comes from a
+ hard register or 2) both SSA registers REG1 and REG2 come from
+ different hard registers. */
+
+static int
+conflicting_hard_regs_p (int reg1, int reg2)
+{
+ int orig_reg1 = original_register (reg1);
+ int orig_reg2 = original_register (reg2);
+ if (HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2)
+ && orig_reg1 != orig_reg2)
+ return 1;
+ if (HARD_REGISTER_NUM_P (orig_reg1) && !HARD_REGISTER_NUM_P (orig_reg2))
+ return 1;
+ if (!HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2))
+ return 1;
+
+ return 0;
}
OSDN Git Service
