+/* 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 (p, conflicts, reg1, reg2)
+ partition p;
+ conflict_graph conflicts;
+ int reg1;
+ int reg2;
+{
+ int reg;
+
+ /* Don't mess with hard regs. */
+ if (reg1 < FIRST_PSEUDO_REGISTER || reg2 < FIRST_PSEUDO_REGISTER)
+ 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 (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 (bb, p, conflicts)
+ int bb;
+ partition p;
+ conflict_graph conflicts;
+{
+ int changed = 0;
+ rtx insn;
+ rtx end = BLOCK_END (bb);
+
+ /* Scan the instruction stream of the block. */
+ for (insn = BLOCK_HEAD (bb); 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);
+
+ /* If src or dest are subregs, find the underlying reg. */
+ while (GET_CODE (src) == SUBREG
+ && SUBREG_WORD (src) != 0)
+ src = SUBREG_REG (src);
+ while (GET_CODE (dest) == SUBREG
+ && SUBREG_WORD (dest) != 0)
+ dest = SUBREG_REG (dest);
+
+ /* 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 paritition class. DATA is a pointer to a
+ phi_coalesce_context struct. */
+
+static int
+coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
+ 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 (bb, p, conflicts)
+ int 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 ()
+{
+ int 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);
+
+ /* 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 (bb = n_basic_blocks; --bb >= 0; )
+ make_regs_equivalent_over_bad_edges (bb, p);
+
+ do
+ {
+ regset_head phi_set;
+ 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. */
+ INITIALIZE_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 (bb = n_basic_blocks; --bb >= 0; )
+ {
+ 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);
+
+ 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 (ptr, data)
+ 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 (phi_set)
+ regset phi_set;
+{
+ int reg;
+
+ /* Scan the definitions of all regs. */
+ for (reg = VARRAY_SIZE (ssa_definition);
+ --reg >= FIRST_PSEUDO_REGISTER;
+ )
+ {
+ rtx insn = VARRAY_RTX (ssa_definition, reg);
+ rtx pattern;
+ rtx src;
+
+ if (insn == NULL)
+ 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. */
+ }
+}
git://gcc.gnu.org / gcc.git / blobdiff