diff options
Diffstat (limited to 'gcc/ssa.c')
| -rw-r--r-- | gcc/ssa.c | 2214 |
1 files changed, 0 insertions, 2214 deletions
diff --git a/gcc/ssa.c b/gcc/ssa.c deleted file mode 100644 index c12cdbe7afb..00000000000 --- a/gcc/ssa.c +++ /dev/null @@ -1,2214 +0,0 @@ -/* Static Single Assignment conversion routines for the GNU compiler. - Copyright (C) 2000, 2001, 2002, 2003 - Free Software Foundation, Inc. - -This file is part of GCC. - -GCC is free software; you can redistribute it and/or modify it under -the terms of the GNU General Public License as published by the Free -Software Foundation; either version 2, or (at your option) any later -version. - -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 GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ - -/* References: - - Building an Optimizing Compiler - Robert Morgan - Butterworth-Heinemann, 1998 - - 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. */ - -#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 "function.h" -#include "real.h" -#include "insn-config.h" -#include "recog.h" -#include "basic-block.h" -#include "output.h" -#include "ssa.h" - -/* 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. - - Actually the best solution may be to have a kind of "mid-level rtl" - 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. */ - -/* 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. - - 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; - -/* 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; - -/* 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. */ - -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 (rtx set, int c) -{ - rtvec phi_vec = XVEC (SET_SRC (set), 0); - int v; - - for (v = GET_NUM_ELEM (phi_vec) - 2; v >= 0; v -= 2) - if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c) - return &RTVEC_ELT (phi_vec, v); - - return NULL; -} - -/* Given the SET of a phi node, remove the alternative for predecessor - block C. Return nonzero on success, or zero if no alternative is - found for 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, c; - - c = block->index; - for (v = num_elem - 2; v >= 0; v -= 2) - if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c) - { - if (v < num_elem - 2) - { - RTVEC_ELT (phi_vec, v) = RTVEC_ELT (phi_vec, num_elem - 2); - RTVEC_ELT (phi_vec, v + 1) = RTVEC_ELT (phi_vec, num_elem - 1); - } - PUT_NUM_ELEM (phi_vec, num_elem - 2); - return 1; - } - - return 0; -} - -/* For all registers, find all blocks in which they are set. - - This is the transform of what would be local kill information that - we ought to be getting from flow. */ - -static sbitmap *fe_evals; -static int fe_current_bb; - -static void -find_evaluations_1 (rtx dest, rtx set ATTRIBUTE_UNUSED, - void *data ATTRIBUTE_UNUSED) -{ - if (GET_CODE (dest) == REG - && CONVERT_REGISTER_TO_SSA_P (REGNO (dest))) - SET_BIT (fe_evals[REGNO (dest)], fe_current_bb); -} - -static void -find_evaluations (sbitmap *evals, int nregs) -{ - basic_block bb; - - sbitmap_vector_zero (evals, nregs); - fe_evals = evals; - - FOR_EACH_BB_REVERSE (bb) - { - rtx p, last; - - fe_current_bb = bb->index; - p = bb->head; - last = bb->end; - while (1) - { - if (INSN_P (p)) - note_stores (PATTERN (p), find_evaluations_1, NULL); - - if (p == last) - break; - p = NEXT_INSN (p); - } - } -} - -/* Computing the Dominance Frontier: - - 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: - - (1) A flow graph edge leaving B that does not lead to a child - of B in the dominator tree must be a block that is either equal - to B or not dominated by B. Such blocks belong in the frontier - of B. - - (2) Consider a block X in the frontier of one of the children C - of B. If X is not equal to B and is not dominated by B, it - is in the frontier of B. -*/ - -static void -compute_dominance_frontiers_1 (sbitmap *frontiers, dominance_info idom, - int bb, sbitmap done) -{ - basic_block b = BASIC_BLOCK (bb); - edge e; - 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_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 (get_immediate_dominator (idom, e->dest)->index != bb) - SET_BIT (frontiers[bb], e->dest->index); - } - - /* Find blocks conforming to rule (2). */ - FOR_EACH_BB (c) - if (get_immediate_dominator (idom, c)->index == bb) - { - int x; - EXECUTE_IF_SET_IN_SBITMAP (frontiers[c->index], 0, x, - { - if (get_immediate_dominator (idom, BASIC_BLOCK (x))->index != bb) - SET_BIT (frontiers[bb], x); - }); - } -} - -void -compute_dominance_frontiers (sbitmap *frontiers, dominance_info idom) -{ - 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. - - This is not particularly intuitive. See section 7.1 of Morgan, in - particular figures 7.3 and 7.4 and the immediately surrounding text. -*/ - -static void -compute_iterated_dominance_frontiers (sbitmap *idfs, sbitmap *frontiers, - sbitmap *evals, int nregs) -{ - sbitmap worklist; - int reg, passes = 0; - - worklist = sbitmap_alloc (last_basic_block); - - for (reg = 0; reg < nregs; ++reg) - { - sbitmap idf = idfs[reg]; - int b, changed; - - /* Start the iterative process by considering those blocks that - evaluate REG. We'll add their dominance frontiers to the - IDF, and then consider the blocks we just added. */ - sbitmap_copy (worklist, evals[reg]); - - /* Morgan's algorithm is incorrect here. Blocks that evaluate - REG aren't necessarily in REG's IDF. Start with an empty IDF. */ - sbitmap_zero (idf); - - /* Iterate until the worklist is empty. */ - do - { - changed = 0; - passes++; - EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b, - { - RESET_BIT (worklist, b); - /* For each block on the worklist, add to the IDF all - blocks on its dominance frontier that aren't already - on the IDF. Every block that's added is also added - to the worklist. */ - sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf); - sbitmap_a_or_b (idf, idf, frontiers[b]); - changed = 1; - }); - } - while (changed); - } - - sbitmap_free (worklist); - - if (rtl_dump_file) - { - fprintf (rtl_dump_file, - "Iterated dominance frontier: %d passes on %d regs.\n", - passes, nregs); - } -} - -/* Insert the phi nodes. */ - -static void -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 (e->src != ENTRY_BLOCK_PTR) - npred++; - - /* If this block has no "interesting" preds, then there is nothing to - do. Consider a block that only has the entry block as a pred. */ - if (npred == 0) - return; - - /* 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. */ - vec = rtvec_alloc (npred * 2); - for (e = b->pred, i = 0; e ; e = e->pred_next, i += 2) - if (e->src != ENTRY_BLOCK_PTR) - { - RTVEC_ELT (vec, i + 0) = pc_rtx; - RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index); - } - - phi = gen_rtx_PHI (VOIDmode, vec); - phi = gen_rtx_SET (VOIDmode, reg, phi); - - 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 (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)) - insert_phi_node (reg, b); - }); - } -} - -/* 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 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; - /* 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; -}; - -/* 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][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 - -/* 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 (rtx *ptr, void *data) -{ - rtx x = *ptr; - struct rename_context *context = data; - - if (x == NULL_RTX) - return 0; - - switch (GET_CODE (x)) - { - case SET: - { - 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 - 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. */ - - 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. */ - if (GET_CODE (x) == SET) - for_each_rtx (&SET_SRC (x), rename_insn_1, data); - return -1; - } - - /* Otherwise, this was not an interesting destination. Continue - on, marking uses as normal. */ - return 0; - } - - case REG: - if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) - && REGNO (x) < ssa_max_reg_num) - { - rtx new_reg = ssa_rename_to_lookup (x); - - if (new_reg != RENAME_NO_RTX && new_reg != NULL_RTX) - { - if (GET_MODE (x) != GET_MODE (new_reg)) - abort (); - *ptr = new_reg; - } - 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; - - default: - /* Anything else, continue traversing. */ - return 0; - } -} - -static rtx -gen_sequence (void) -{ - rtx first_insn = get_insns (); - rtx result; - rtx tem; - int i; - int len; - - /* Count the insns in the chain. */ - len = 0; - for (tem = first_insn; tem; tem = NEXT_INSN (tem)) - len++; - - result = gen_rtx_SEQUENCE (VOIDmode, rtvec_alloc (len)); - - for (i = 0, tem = first_insn; tem; tem = NEXT_INSN (tem), i++) - XVECEXP (result, 0, i) = tem; - - return result; -} - -static void -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; - 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 (INSN_P (insn)) - { - 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 (); - - apply_delayed_renames (&context); - set_data = context.done_renames; - } - - next = NEXT_INSN (insn); - } - while (insn != last); - - /* Step Two: Update the phi nodes of this block's successors. */ - - for (e = b->succ; e; e = e->succ_next) - { - if (e->dest == EXIT_BLOCK_PTR) - continue; - - insn = first_insn_after_basic_block_note (e->dest); - - while (PHI_NODE_P (insn)) - { - rtx phi = PATTERN (insn); - rtx reg; - - /* Find out which of our outgoing registers this node is - 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. */ - 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, 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. */ - 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 (); - - *phi_alternative (phi, bb) = reg; - } - - insn = NEXT_INSN (insn); - } - } - - /* Step Three: Do the same to the children of this block in - dominator order. */ - - 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, - and restore ssa_rename_to to its previous state. */ - - while (set_data) - { - struct rename_set_data *next; - rtx 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_insert (old_reg, set_data->prev_reg); - - next = set_data->next; - free (set_data); - set_data = next; - } -} - -static void -rename_registers (int nregs, dominance_info idom) -{ - VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition"); - ssa_rename_from_initialize (); - - 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 - as needed. */ - - ssa_rename_to_pseudo = NULL; -} - -/* The main entry point for moving to SSA. */ - -void -convert_to_ssa (void) -{ - /* Element I is the set of blocks that set register I. */ - sbitmap *evals; - - /* Dominator bitmaps. */ - sbitmap *dfs; - sbitmap *idfs; - - /* Element I is the immediate dominator of block I. */ - dominance_info idom; - - int nregs; - - basic_block bb; - - /* Don't do it twice. */ - if (in_ssa_form) - abort (); - - /* 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 = calculate_dominance_info (CDI_DOMINATORS); - - if (rtl_dump_file) - { - fputs (";; Immediate Dominators:\n", rtl_dump_file); - 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 (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, last_basic_block); - fflush (rtl_dump_file); - } - - /* Compute register evaluations. */ - - 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, 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", idfs, nregs); - fflush (rtl_dump_file); - } - - /* Insert the phi nodes. */ - - insert_phi_nodes (idfs, evals, nregs); - - /* Rename the registers to satisfy SSA. */ - - rename_registers (nregs, idom); - - /* All done! Clean up and go home. */ - - sbitmap_vector_free (dfs); - sbitmap_vector_free (evals); - sbitmap_vector_free (idfs); - in_ssa_form = 1; - - 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 (rtx reg, rtx *nodes, int *n_nodes) -{ - int i; - for (i = *n_nodes - 1; i >= 0; --i) - if (REGNO (reg) == REGNO (nodes[i])) - return i; - - nodes[i = (*n_nodes)++] = reg; - return 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 dependencies. */ - -static int * -ephi_forward (int t, sbitmap visited, sbitmap *succ, int *tstack) -{ - int s; - - SET_BIT (visited, t); - - EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s, - { - if (! TEST_BIT (visited, s)) - tstack = ephi_forward (s, visited, succ, tstack); - }); - - *tstack++ = t; - return tstack; -} - -/* Part two of the topological sort. The is a backward search through - a cycle in the graph, copying the data forward as we go. */ - -static void -ephi_backward (int t, sbitmap visited, sbitmap *pred, rtx *nodes) -{ - int p; - - SET_BIT (visited, t); - - EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, - { - if (! TEST_BIT (visited, p)) - { - ephi_backward (p, visited, pred, nodes); - emit_move_insn (nodes[p], nodes[t]); - } - }); -} - -/* Part two of the topological sort. Create the copy for a register - and any cycle of which it is a member. */ - -static void -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 - the same time, look for a visited predecessor. If there is one, - we won't need to create a temporary. */ - - EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, - { - if (! TEST_BIT (visited, p)) - unvisited_predecessors = 1; - else if (!reg_u) - reg_u = nodes[p]; - }); - - if (unvisited_predecessors) - { - /* We found a cycle. Copy out one element of the ring (if necessary), - then traverse the ring copying as we go. */ - - if (!reg_u) - { - reg_u = gen_reg_rtx (GET_MODE (nodes[t])); - emit_move_insn (reg_u, nodes[t]); - } - - EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, - { - if (! TEST_BIT (visited, p)) - { - ephi_backward (p, visited, pred, nodes); - emit_move_insn (nodes[p], reg_u); - } - }); - } - else - { - /* No cycle. Just copy the value from a successor. */ - - int s; - EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s, - { - SET_BIT (visited, t); - emit_move_insn (nodes[t], nodes[s]); - return; - }); - } -} - -/* Convert the edge to normal form. */ - -static void -eliminate_phi (edge e, partition reg_partition) -{ - int n_nodes; - sbitmap *pred, *succ; - sbitmap visited; - rtx *nodes; - int *stack, *tstack; - rtx insn; - int i; - - /* Collect an upper bound on the number of registers needing processing. */ - - insn = first_insn_after_basic_block_note (e->dest); - - n_nodes = 0; - while (PHI_NODE_P (insn)) - { - insn = next_nonnote_insn (insn); - n_nodes += 2; - } - - if (n_nodes == 0) - return; - - /* 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 = 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 = first_insn_after_basic_block_note (e->dest); - - n_nodes = 0; - for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn)) - { - rtx* preg = phi_alternative (PATTERN (insn), e->src->index); - rtx tgt = SET_DEST (PATTERN (insn)); - rtx reg; - - /* There may be no phi alternative corresponding to this edge. - This indicates that the phi variable is undefined along this - edge. */ - if (preg == NULL) - continue; - reg = *preg; - - if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG) - abort (); - - 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 (reg != tgt) - { - int ireg, itgt; - - ireg = ephi_add_node (reg, nodes, &n_nodes); - itgt = ephi_add_node (tgt, nodes, &n_nodes); - - SET_BIT (pred[ireg], itgt); - SET_BIT (succ[itgt], ireg); - } - } - - if (n_nodes == 0) - goto out; - - /* Begin a topological sort of the graph. */ - - visited = sbitmap_alloc (n_nodes); - sbitmap_zero (visited); - - tstack = stack = alloca (n_nodes * sizeof (int)); - - for (i = 0; i < n_nodes; ++i) - if (! TEST_BIT (visited, i)) - tstack = ephi_forward (i, visited, succ, tstack); - - sbitmap_zero (visited); - - /* As we find a solution to the tsort, collect the implementation - insns in a sequence. */ - start_sequence (); - - while (tstack != stack) - { - i = *--tstack; - if (! TEST_BIT (visited, i)) - ephi_create (i, visited, pred, succ, nodes); - } - - insn = get_insns (); - end_sequence (); - insert_insn_on_edge (insn, e); - if (rtl_dump_file) - fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n", - e->src->index, e->dest->index); - - sbitmap_free (visited); -out: - sbitmap_vector_free (pred); - 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. - - 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. - - 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 (int bb, partition reg_partition) -{ - int changed = 0; - basic_block b = BASIC_BLOCK (bb); - rtx phi; - - /* Advance to the first phi node. */ - phi = first_insn_after_basic_block_note (b); - - /* Scan all the phi nodes. */ - for (; - PHI_NODE_P (phi); - phi = next_nonnote_insn (phi)) - { - edge e; - int tgt_regno; - rtx set = PATTERN (phi); - rtx tgt = SET_DEST (set); - - /* 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_P (e)) - { - rtx *alt = phi_alternative (set, e->src->index); - int alt_regno; - - /* If there is no alternative corresponding to this edge, - the value is undefined along the edge, so just go on. */ - if (alt == 0) - continue; - - /* 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) - != partition_find (reg_partition, alt_regno)) - { - /* ... make them such. */ - 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 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 (int bb, partition reg_partition) -{ - int changed = 0; - basic_block b = BASIC_BLOCK (bb); - rtx phi; - - /* Advance to the first phi node. */ - phi = first_insn_after_basic_block_note (b); - - /* Scan all the phi nodes. */ - for (; - PHI_NODE_P (phi); - phi = next_nonnote_insn (phi)) - { - rtx set = PATTERN (phi); - /* The regno of the destination of the set. */ - int tgt_regno = REGNO (SET_DEST (PATTERN (phi))); - - rtx phi2 = next_nonnote_insn (phi); - - /* Scan all phi nodes following this one. */ - for (; - PHI_NODE_P (phi2); - phi2 = next_nonnote_insn (phi2)) - { - 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)) - { - edge e; - /* Scan over edges. */ - for (e = b->pred; e; e = e->pred_next) - { - int pred_block = e->src->index; - /* 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 one of the phi nodes doesn't have a - corresponding alternative, just skip it. */ - if (alt == 0 || alt2 == 0) - continue; - - /* Both alternatives should be SSA registers. */ - if (GET_CODE (*alt) != REG - || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt))) - abort (); - if (GET_CODE (*alt2) != REG - || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2))) - abort (); - - /* 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. */ - 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 (void) -{ - 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); - - /* 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_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_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: - - 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 -coalesce_if_unconflicting (partition p, conflict_graph conflicts, - int reg1, int reg2) -{ - int reg; - - /* Work only on SSA registers. */ - if (!CONVERT_REGISTER_TO_SSA_P (reg1) || !CONVERT_REGISTER_TO_SSA_P (reg2)) - return 0; - - /* 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)) - { - 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. */ - -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) - { - /* It's a reg copy. */ - SET_REGNO_REG_SET (phi_set, reg); - SET_REGNO_REG_SET (phi_set, REGNO (src)); - } - else if (GET_CODE (src) == PHI) - { - /* 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); - } - /* ... 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 (CONVERT_REGISTER_TO_SSA_P (REGNO (x))) - { - 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)) - abort (); - *ptr = new_reg; - } - } - return -1; - - case PHI: - /* No need to rename the phi nodes. We'll check equivalence - when inserting copies. */ - return -1; - - default: - /* Anything else, continue traversing. */ - return 0; - } -} - -/* 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. */ - -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 (partition reg_partition) -{ - basic_block b; - - FOR_EACH_BB_REVERSE (b) - { - rtx next = b->head; - rtx last = b->end; - rtx insn; - - do - { - insn = next; - if (INSN_P (insn)) - { - for_each_rtx (&PATTERN (insn), - rename_equivalent_regs_in_insn, - reg_partition); - 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); - } - while (insn != last); - } -} - -/* The main entry point for moving from SSA. */ - -void -convert_from_ssa (void) -{ - basic_block b, bb; - partition 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_EACH_BB_REVERSE (b) - { - edge e; - - for (e = b->pred; e; e = e->pred_next) - if (e->src != ENTRY_BLOCK_PTR) - eliminate_phi (e, reg_partition); - } - - partition_delete (reg_partition); - - /* Actually delete the PHI nodes. */ - FOR_EACH_BB_REVERSE (bb) - { - rtx insn = bb->head; - - while (1) - { - /* 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); - } - } - - /* 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; -} |