1 /* Static Single Assignment conversion routines for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GNU CC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 Building an Optimizing Compiler
25 Butterworth-Heinemann, 1998
27 Static Single Assignment Construction
28 Preston Briggs, Tim Harvey, Taylor Simpson
29 Technical Report, Rice University, 1995
30 ftp://ftp.cs.rice.edu/public/preston/optimizer/SSA.ps.gz. */
37 #include "partition.h"
41 #include "hard-reg-set.h"
45 #include "insn-config.h"
47 #include "basic-block.h"
53 Handle subregs better, maybe. For now, if a reg that's set in a
54 subreg expression is duplicated going into SSA form, an extra copy
55 is inserted first that copies the entire reg into the duplicate, so
56 that the other bits are preserved. This isn't strictly SSA, since
57 at least part of the reg is assigned in more than one place (though
60 ??? What to do about strict_low_part. Probably I'll have to split
61 them out of their current instructions first thing.
63 Actually the best solution may be to have a kind of "mid-level rtl"
64 in which the RTL encodes exactly what we want, without exposing a
65 lot of niggling processor details. At some later point we lower
66 the representation, calling back into optabs to finish any necessary
69 /* All pseudo-registers and select hard registers are converted to SSA
70 form. When converting out of SSA, these select hard registers are
71 guaranteed to be mapped to their original register number. Each
72 machine's .h file should define CONVERT_HARD_REGISTER_TO_SSA_P
73 indicating which hard registers should be converted.
75 When converting out of SSA, temporaries for all registers are
76 partitioned. The partition is checked to ensure that all uses of
77 the same hard register in the same machine mode are in the same
80 /* If conservative_reg_partition is non-zero, use a conservative
81 register partitioning algorithm (which leaves more regs after
82 emerging from SSA) instead of the coalescing one. This is being
83 left in for a limited time only, as a debugging tool until the
84 coalescing algorithm is validated. */
86 static int conservative_reg_partition;
88 /* This flag is set when the CFG is in SSA form. */
91 /* Element I is the single instruction that sets register I. */
92 varray_type ssa_definition;
94 /* Element I is an INSN_LIST of instructions that use register I. */
97 /* Element I-PSEUDO is the normal register that originated the ssa
98 register in question. */
99 varray_type ssa_rename_from;
101 /* Element I is the normal register that originated the ssa
102 register in question.
104 A hash table stores the (register, rtl) pairs. These are each
105 xmalloc'ed and deleted when the hash table is destroyed. */
106 htab_t ssa_rename_from_ht;
108 /* The running target ssa register for a given pseudo register.
109 (Pseudo registers appear in only one mode.) */
110 static rtx *ssa_rename_to_pseudo;
111 /* Similar, but for hard registers. A hard register can appear in
112 many modes, so we store an equivalent pseudo for each of the
114 static rtx ssa_rename_to_hard[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
116 /* ssa_rename_from maps pseudo registers to the original corresponding
117 RTL. It is implemented as using a hash table. */
122 } ssa_rename_from_pair;
124 struct ssa_rename_from_hash_table_data {
125 sbitmap canonical_elements;
126 partition reg_partition;
129 static void ssa_rename_from_initialize
131 static rtx ssa_rename_from_lookup
133 static unsigned int original_register
134 PARAMS ((unsigned int regno));
135 static void ssa_rename_from_insert
136 PARAMS ((unsigned int reg, rtx r));
137 static void ssa_rename_from_free
139 typedef int (*srf_trav) PARAMS ((int regno, rtx r, sbitmap canonical_elements, partition reg_partition));
140 static void ssa_rename_from_traverse
141 PARAMS ((htab_trav callback_function, sbitmap canonical_elements, partition reg_partition));
142 /*static Avoid warnign message. */ void ssa_rename_from_print
144 static int ssa_rename_from_print_1
145 PARAMS ((void **slot, void *data));
146 static hashval_t ssa_rename_from_hash_function
147 PARAMS ((const void * srfp));
148 static int ssa_rename_from_equal
149 PARAMS ((const void *srfp1, const void *srfp2));
150 static void ssa_rename_from_delete
151 PARAMS ((void *srfp));
153 static rtx ssa_rename_to_lookup
155 static void ssa_rename_to_insert
156 PARAMS ((rtx reg, rtx r));
158 /* The number of registers that were live on entry to the SSA routines. */
159 static unsigned int ssa_max_reg_num;
161 /* Local function prototypes. */
163 struct rename_context;
165 static inline rtx * phi_alternative
167 static rtx first_insn_after_basic_block_note
168 PARAMS ((basic_block));
169 static int remove_phi_alternative
171 static void compute_dominance_frontiers_1
172 PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
173 static void compute_dominance_frontiers
174 PARAMS ((sbitmap *frontiers, int *idom));
175 static void find_evaluations_1
176 PARAMS ((rtx dest, rtx set, void *data));
177 static void find_evaluations
178 PARAMS ((sbitmap *evals, int nregs));
179 static void compute_iterated_dominance_frontiers
180 PARAMS ((sbitmap *idfs, sbitmap *frontiers, sbitmap *evals, int nregs));
181 static void insert_phi_node
182 PARAMS ((int regno, int b));
183 static void insert_phi_nodes
184 PARAMS ((sbitmap *idfs, sbitmap *evals, int nregs));
185 static void create_delayed_rename
186 PARAMS ((struct rename_context *, rtx *));
187 static void apply_delayed_renames
188 PARAMS ((struct rename_context *));
189 static int rename_insn_1
190 PARAMS ((rtx *ptr, void *data));
191 static void rename_block
192 PARAMS ((int b, int *idom));
193 static void rename_registers
194 PARAMS ((int nregs, int *idom));
196 static inline int ephi_add_node
197 PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
198 static int * ephi_forward
199 PARAMS ((int t, sbitmap visited, sbitmap *succ, int *tstack));
200 static void ephi_backward
201 PARAMS ((int t, sbitmap visited, sbitmap *pred, rtx *nodes));
202 static void ephi_create
203 PARAMS ((int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes));
204 static void eliminate_phi
205 PARAMS ((edge e, partition reg_partition));
206 static int make_regs_equivalent_over_bad_edges
207 PARAMS ((int bb, partition reg_partition));
209 /* These are used only in the conservative register partitioning
211 static int make_equivalent_phi_alternatives_equivalent
212 PARAMS ((int bb, partition reg_partition));
213 static partition compute_conservative_reg_partition
215 static int record_canonical_element_1
216 PARAMS ((void **srfp, void *data));
217 static int check_hard_regs_in_partition
218 PARAMS ((partition reg_partition));
219 static int rename_equivalent_regs_in_insn
220 PARAMS ((rtx *ptr, void *data));
222 /* These are used in the register coalescing algorithm. */
223 static int coalesce_if_unconflicting
224 PARAMS ((partition p, conflict_graph conflicts, int reg1, int reg2));
225 static int coalesce_regs_in_copies
226 PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
227 static int coalesce_reg_in_phi
228 PARAMS ((rtx, int dest_regno, int src_regno, void *data));
229 static int coalesce_regs_in_successor_phi_nodes
230 PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
231 static partition compute_coalesced_reg_partition
233 static int mark_reg_in_phi
234 PARAMS ((rtx *ptr, void *data));
235 static void mark_phi_and_copy_regs
236 PARAMS ((regset phi_set));
238 static int rename_equivalent_regs_in_insn
239 PARAMS ((rtx *ptr, void *data));
240 static void rename_equivalent_regs
241 PARAMS ((partition reg_partition));
243 /* Deal with hard registers. */
244 static int conflicting_hard_regs_p
245 PARAMS ((int reg1, int reg2));
247 /* ssa_rename_to maps registers and machine modes to SSA pseudo registers. */
249 /* Find the register associated with REG in the indicated mode. */
252 ssa_rename_to_lookup (reg)
255 if (!HARD_REGISTER_P (reg))
256 return ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER];
258 return ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)];
261 /* Store a new value mapping REG to R in ssa_rename_to. */
264 ssa_rename_to_insert(reg, r)
268 if (!HARD_REGISTER_P (reg))
269 ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER] = r;
271 ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)] = r;
274 /* Prepare ssa_rename_from for use. */
277 ssa_rename_from_initialize ()
279 /* We use an arbitrary initial hash table size of 64. */
280 ssa_rename_from_ht = htab_create (64,
281 &ssa_rename_from_hash_function,
282 &ssa_rename_from_equal,
283 &ssa_rename_from_delete);
286 /* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
290 ssa_rename_from_lookup (reg)
293 ssa_rename_from_pair srfp;
294 ssa_rename_from_pair *answer;
296 srfp.original = NULL_RTX;
297 answer = (ssa_rename_from_pair *)
298 htab_find_with_hash (ssa_rename_from_ht, (void *) &srfp, reg);
299 return (answer == 0 ? NULL_RTX : answer->original);
302 /* Find the number of the original register specified by REGNO. If
303 the register is a pseudo, return the original register's number.
304 Otherwise, return this register number REGNO. */
307 original_register (regno)
310 rtx original_rtx = ssa_rename_from_lookup (regno);
311 return original_rtx != NULL_RTX ? REGNO (original_rtx) : regno;
314 /* Add mapping from R to REG to ssa_rename_from even if already present. */
317 ssa_rename_from_insert (reg, r)
322 ssa_rename_from_pair *srfp = xmalloc (sizeof (ssa_rename_from_pair));
325 slot = htab_find_slot_with_hash (ssa_rename_from_ht, (const void *) srfp,
328 free ((void *) *slot);
332 /* Apply the CALLBACK_FUNCTION to each element in ssa_rename_from.
333 CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
334 current use of this function. */
337 ssa_rename_from_traverse (callback_function,
338 canonical_elements, reg_partition)
339 htab_trav callback_function;
340 sbitmap canonical_elements;
341 partition reg_partition;
343 struct ssa_rename_from_hash_table_data srfhd;
344 srfhd.canonical_elements = canonical_elements;
345 srfhd.reg_partition = reg_partition;
346 htab_traverse (ssa_rename_from_ht, callback_function, (void *) &srfhd);
349 /* Destroy ssa_rename_from. */
352 ssa_rename_from_free ()
354 htab_delete (ssa_rename_from_ht);
357 /* Print the contents of ssa_rename_from. */
359 /* static Avoid erroneous error message. */
361 ssa_rename_from_print ()
363 printf ("ssa_rename_from's hash table contents:\n");
364 htab_traverse (ssa_rename_from_ht, &ssa_rename_from_print_1, NULL);
367 /* Print the contents of the hash table entry SLOT, passing the unused
368 sttribute DATA. Used as a callback function with htab_traverse (). */
371 ssa_rename_from_print_1 (slot, data)
373 void *data ATTRIBUTE_UNUSED;
375 ssa_rename_from_pair * p = *slot;
376 printf ("ssa_rename_from maps pseudo %i to original %i.\n",
377 p->reg, REGNO (p->original));
381 /* Given a hash entry SRFP, yield a hash value. */
384 ssa_rename_from_hash_function (srfp)
387 return ((ssa_rename_from_pair *) srfp)->reg;
390 /* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
393 ssa_rename_from_equal (srfp1, srfp2)
397 return ssa_rename_from_hash_function (srfp1) ==
398 ssa_rename_from_hash_function (srfp2);
401 /* Delete the hash table entry SRFP. */
404 ssa_rename_from_delete (srfp)
410 /* Given the SET of a PHI node, return the address of the alternative
411 for predecessor block C. */
414 phi_alternative (set, c)
418 rtvec phi_vec = XVEC (SET_SRC (set), 0);
421 for (v = GET_NUM_ELEM (phi_vec) - 2; v >= 0; v -= 2)
422 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
423 return &RTVEC_ELT (phi_vec, v);
428 /* Given the SET of a phi node, remove the alternative for predecessor
429 block C. Return non-zero on success, or zero if no alternative is
433 remove_phi_alternative (set, c)
437 rtvec phi_vec = XVEC (SET_SRC (set), 0);
438 int num_elem = GET_NUM_ELEM (phi_vec);
441 for (v = num_elem - 2; v >= 0; v -= 2)
442 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
444 if (v < num_elem - 2)
446 RTVEC_ELT (phi_vec, v) = RTVEC_ELT (phi_vec, num_elem - 2);
447 RTVEC_ELT (phi_vec, v + 1) = RTVEC_ELT (phi_vec, num_elem - 1);
449 PUT_NUM_ELEM (phi_vec, num_elem - 2);
456 /* For all registers, find all blocks in which they are set.
458 This is the transform of what would be local kill information that
459 we ought to be getting from flow. */
461 static sbitmap *fe_evals;
462 static int fe_current_bb;
465 find_evaluations_1 (dest, set, data)
467 rtx set ATTRIBUTE_UNUSED;
468 void *data ATTRIBUTE_UNUSED;
470 if (GET_CODE (dest) == REG
471 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
472 SET_BIT (fe_evals[REGNO (dest)], fe_current_bb);
476 find_evaluations (evals, nregs)
482 sbitmap_vector_zero (evals, nregs);
485 for (bb = n_basic_blocks; --bb >= 0; )
491 last = BLOCK_END (bb);
495 note_stores (PATTERN (p), find_evaluations_1, NULL);
504 /* Computing the Dominance Frontier:
506 As decribed in Morgan, section 3.5, this may be done simply by
507 walking the dominator tree bottom-up, computing the frontier for
508 the children before the parent. When considering a block B,
511 (1) A flow graph edge leaving B that does not lead to a child
512 of B in the dominator tree must be a block that is either equal
513 to B or not dominated by B. Such blocks belong in the frontier
516 (2) Consider a block X in the frontier of one of the children C
517 of B. If X is not equal to B and is not dominated by B, it
518 is in the frontier of B.
522 compute_dominance_frontiers_1 (frontiers, idom, bb, done)
528 basic_block b = BASIC_BLOCK (bb);
533 sbitmap_zero (frontiers[bb]);
535 /* Do the frontier of the children first. Not all children in the
536 dominator tree (blocks dominated by this one) are children in the
537 CFG, so check all blocks. */
538 for (c = 0; c < n_basic_blocks; ++c)
539 if (idom[c] == bb && ! TEST_BIT (done, c))
540 compute_dominance_frontiers_1 (frontiers, idom, c, done);
542 /* Find blocks conforming to rule (1) above. */
543 for (e = b->succ; e; e = e->succ_next)
545 if (e->dest == EXIT_BLOCK_PTR)
547 if (idom[e->dest->index] != bb)
548 SET_BIT (frontiers[bb], e->dest->index);
551 /* Find blocks conforming to rule (2). */
552 for (c = 0; c < n_basic_blocks; ++c)
556 EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x,
559 SET_BIT (frontiers[bb], x);
565 compute_dominance_frontiers (frontiers, idom)
569 sbitmap done = sbitmap_alloc (n_basic_blocks);
572 compute_dominance_frontiers_1 (frontiers, idom, 0, done);
577 /* Computing the Iterated Dominance Frontier:
579 This is the set of merge points for a given register.
581 This is not particularly intuitive. See section 7.1 of Morgan, in
582 particular figures 7.3 and 7.4 and the immediately surrounding text.
586 compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs)
595 worklist = sbitmap_alloc (n_basic_blocks);
597 for (reg = 0; reg < nregs; ++reg)
599 sbitmap idf = idfs[reg];
602 /* Start the iterative process by considering those blocks that
603 evaluate REG. We'll add their dominance frontiers to the
604 IDF, and then consider the blocks we just added. */
605 sbitmap_copy (worklist, evals[reg]);
607 /* Morgan's algorithm is incorrect here. Blocks that evaluate
608 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
611 /* Iterate until the worklist is empty. */
616 EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b,
618 RESET_BIT (worklist, b);
619 /* For each block on the worklist, add to the IDF all
620 blocks on its dominance frontier that aren't already
621 on the IDF. Every block that's added is also added
623 sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf);
624 sbitmap_a_or_b (idf, idf, frontiers[b]);
631 sbitmap_free (worklist);
635 fprintf(rtl_dump_file,
636 "Iterated dominance frontier: %d passes on %d regs.\n",
641 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
642 note associated with the BLOCK. */
645 first_insn_after_basic_block_note (block)
650 /* Get the first instruction in the block. */
653 if (insn == NULL_RTX)
655 if (GET_CODE (insn) == CODE_LABEL)
656 insn = NEXT_INSN (insn);
657 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
660 return NEXT_INSN (insn);
663 /* Insert the phi nodes. */
666 insert_phi_node (regno, bb)
669 basic_block b = BASIC_BLOCK (bb);
677 /* Find out how many predecessors there are. */
678 for (e = b->pred, npred = 0; e; e = e->pred_next)
679 if (e->src != ENTRY_BLOCK_PTR)
682 /* If this block has no "interesting" preds, then there is nothing to
683 do. Consider a block that only has the entry block as a pred. */
687 /* This is the register to which the phi function will be assigned. */
688 reg = regno_reg_rtx[regno];
690 /* Construct the arguments to the PHI node. The use of pc_rtx is just
691 a placeholder; we'll insert the proper value in rename_registers. */
692 vec = rtvec_alloc (npred * 2);
693 for (e = b->pred, i = 0; e ; e = e->pred_next, i += 2)
694 if (e->src != ENTRY_BLOCK_PTR)
696 RTVEC_ELT (vec, i + 0) = pc_rtx;
697 RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index);
700 phi = gen_rtx_PHI (VOIDmode, vec);
701 phi = gen_rtx_SET (VOIDmode, reg, phi);
703 insn = first_insn_after_basic_block_note (b);
704 end_p = PREV_INSN (insn) == b->end;
705 emit_insn_before (phi, insn);
707 b->end = PREV_INSN (insn);
711 insert_phi_nodes (idfs, evals, nregs)
713 sbitmap *evals ATTRIBUTE_UNUSED;
718 for (reg = 0; reg < nregs; ++reg)
719 if (CONVERT_REGISTER_TO_SSA_P (reg))
722 EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b,
724 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, reg))
725 insert_phi_node (reg, b);
730 /* Rename the registers to conform to SSA.
732 This is essentially the algorithm presented in Figure 7.8 of Morgan,
733 with a few changes to reduce pattern search time in favour of a bit
734 more memory usage. */
736 /* One of these is created for each set. It will live in a list local
737 to its basic block for the duration of that block's processing. */
738 struct rename_set_data
740 struct rename_set_data *next;
741 /* This is the SET_DEST of the (first) SET that sets the REG. */
743 /* This is what used to be at *REG_LOC. */
745 /* This is the REG that will replace OLD_REG. It's set only
746 when the rename data is moved onto the DONE_RENAMES queue. */
748 /* This is what to restore ssa_rename_to_lookup (old_reg) to. It is
749 usually the previous contents of ssa_rename_to_lookup (old_reg). */
751 /* This is the insn that contains all the SETs of the REG. */
755 /* This struct is used to pass information to callback functions while
756 renaming registers. */
757 struct rename_context
759 struct rename_set_data *new_renames;
760 struct rename_set_data *done_renames;
764 /* Queue the rename of *REG_LOC. */
766 create_delayed_rename (c, reg_loc)
767 struct rename_context *c;
770 struct rename_set_data *r;
771 r = (struct rename_set_data *) xmalloc (sizeof(*r));
773 if (GET_CODE (*reg_loc) != REG
774 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc)))
777 r->reg_loc = reg_loc;
778 r->old_reg = *reg_loc;
779 r->prev_reg = ssa_rename_to_lookup(r->old_reg);
780 r->set_insn = c->current_insn;
781 r->next = c->new_renames;
785 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
786 reused. If, during processing, a register has not yet been touched,
787 ssa_rename_to[regno][machno] will be NULL. Now, in the course of pushing
788 and popping values from ssa_rename_to, when we would ordinarily
789 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
790 same as NULL, except that it signals that the original regno has
791 already been reused. */
792 #define RENAME_NO_RTX pc_rtx
794 /* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
795 applying all the renames on NEW_RENAMES. */
798 apply_delayed_renames (c)
799 struct rename_context *c;
801 struct rename_set_data *r;
802 struct rename_set_data *last_r = NULL;
804 for (r = c->new_renames; r != NULL; r = r->next)
808 /* Failure here means that someone has a PARALLEL that sets
809 a register twice (bad!). */
810 if (ssa_rename_to_lookup (r->old_reg) != r->prev_reg)
812 /* Failure here means we have changed REG_LOC before applying
814 /* For the first set we come across, reuse the original regno. */
815 if (r->prev_reg == NULL_RTX && !HARD_REGISTER_P (r->old_reg))
817 r->new_reg = r->old_reg;
818 /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
819 r->prev_reg = RENAME_NO_RTX;
822 r->new_reg = gen_reg_rtx (GET_MODE (r->old_reg));
823 new_regno = REGNO (r->new_reg);
824 ssa_rename_to_insert (r->old_reg, r->new_reg);
826 if (new_regno >= (int) ssa_definition->num_elements)
828 int new_limit = new_regno * 5 / 4;
829 ssa_definition = VARRAY_GROW (ssa_definition, new_limit);
830 ssa_uses = VARRAY_GROW (ssa_uses, new_limit);
833 VARRAY_RTX (ssa_definition, new_regno) = r->set_insn;
834 ssa_rename_from_insert (new_regno, r->old_reg);
839 last_r->next = c->done_renames;
840 c->done_renames = c->new_renames;
841 c->new_renames = NULL;
845 /* Part one of the first step of rename_block, called through for_each_rtx.
846 Mark pseudos that are set for later update. Transform uses of pseudos. */
849 rename_insn_1 (ptr, data)
854 struct rename_context *context = data;
859 switch (GET_CODE (x))
863 rtx *destp = &SET_DEST (x);
864 rtx dest = SET_DEST (x);
866 /* Some SETs also use the REG specified in their LHS.
867 These can be detected by the presence of
868 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
869 in the LHS. Handle these by changing
870 (set (subreg (reg foo)) ...)
872 (sequence [(set (reg foo_1) (reg foo))
873 (set (subreg (reg foo_1)) ...)])
875 FIXME: Much of the time this is too much. For many libcalls,
876 paradoxical SUBREGs, etc., the input register is dead. We should
877 recognise this in rename_block or here and not make a false
880 if (GET_CODE (dest) == STRICT_LOW_PART
881 || GET_CODE (dest) == SUBREG
882 || GET_CODE (dest) == SIGN_EXTRACT
883 || GET_CODE (dest) == ZERO_EXTRACT)
888 while (GET_CODE (reg) == STRICT_LOW_PART
889 || GET_CODE (reg) == SUBREG
890 || GET_CODE (reg) == SIGN_EXTRACT
891 || GET_CODE (reg) == ZERO_EXTRACT)
894 if (GET_CODE (reg) == REG
895 && CONVERT_REGISTER_TO_SSA_P (REGNO (reg)))
897 /* Generate (set reg reg), and do renaming on it so
898 that it becomes (set reg_1 reg_0), and we will
899 replace reg with reg_1 in the SUBREG. */
901 struct rename_set_data *saved_new_renames;
902 saved_new_renames = context->new_renames;
903 context->new_renames = NULL;
904 i = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
905 for_each_rtx (&i, rename_insn_1, data);
906 apply_delayed_renames (context);
907 context->new_renames = saved_new_renames;
910 else if (GET_CODE (dest) == REG &&
911 CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
913 /* We found a genuine set of an interesting register. Tag
914 it so that we can create a new name for it after we finish
915 processing this insn. */
917 create_delayed_rename (context, destp);
919 /* Since we do not wish to (directly) traverse the
920 SET_DEST, recurse through for_each_rtx for the SET_SRC
922 if (GET_CODE (x) == SET)
923 for_each_rtx (&SET_SRC (x), rename_insn_1, data);
927 /* Otherwise, this was not an interesting destination. Continue
928 on, marking uses as normal. */
933 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) &&
934 REGNO (x) < ssa_max_reg_num)
936 rtx new_reg = ssa_rename_to_lookup (x);
938 if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
940 if (GET_MODE (x) != GET_MODE (new_reg))
944 /* Else this is a use before a set. Warn? */
949 /* There is considerable debate on how CLOBBERs ought to be
950 handled in SSA. For now, we're keeping the CLOBBERs, which
951 means that we don't really have SSA form. There are a couple
952 of proposals for how to fix this problem, but neither is
955 rtx dest = XCEXP (x, 0, CLOBBER);
958 if (CONVERT_REGISTER_TO_SSA_P (REGNO (dest))
959 && REGNO (dest) < ssa_max_reg_num)
961 rtx new_reg = ssa_rename_to_lookup (dest);
962 if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
963 XCEXP (x, 0, CLOBBER) = new_reg;
965 /* Stop traversing. */
969 /* Continue traversing. */
974 /* Never muck with the phi. We do that elsewhere, special-like. */
978 /* Anything else, continue traversing. */
984 rename_block (bb, idom)
988 basic_block b = BASIC_BLOCK (bb);
990 rtx insn, next, last;
991 struct rename_set_data *set_data = NULL;
994 /* Step One: Walk the basic block, adding new names for sets and
1004 struct rename_context context;
1005 context.done_renames = set_data;
1006 context.new_renames = NULL;
1007 context.current_insn = insn;
1010 for_each_rtx (&PATTERN (insn), rename_insn_1, &context);
1011 for_each_rtx (®_NOTES (insn), rename_insn_1, &context);
1013 /* Sometimes, we end up with a sequence of insns that
1014 SSA needs to treat as a single insn. Wrap these in a
1015 SEQUENCE. (Any notes now get attached to the SEQUENCE,
1016 not to the old version inner insn.) */
1017 if (get_insns () != NULL_RTX)
1022 emit (PATTERN (insn));
1023 seq = gen_sequence ();
1024 /* We really want a SEQUENCE of SETs, not a SEQUENCE
1026 for (i = 0; i < XVECLEN (seq, 0); i++)
1027 XVECEXP (seq, 0, i) = PATTERN (XVECEXP (seq, 0, i));
1028 PATTERN (insn) = seq;
1032 apply_delayed_renames (&context);
1033 set_data = context.done_renames;
1036 next = NEXT_INSN (insn);
1038 while (insn != last);
1040 /* Step Two: Update the phi nodes of this block's successors. */
1042 for (e = b->succ; e; e = e->succ_next)
1044 if (e->dest == EXIT_BLOCK_PTR)
1047 insn = first_insn_after_basic_block_note (e->dest);
1049 while (PHI_NODE_P (insn))
1051 rtx phi = PATTERN (insn);
1054 /* Find out which of our outgoing registers this node is
1055 intended to replace. Note that if this is not the first PHI
1056 node to have been created for this register, we have to
1057 jump through rename links to figure out which register
1058 we're talking about. This can easily be recognized by
1059 noting that the regno is new to this pass. */
1060 reg = SET_DEST (phi);
1061 if (REGNO (reg) >= ssa_max_reg_num)
1062 reg = ssa_rename_from_lookup (REGNO (reg));
1063 if (reg == NULL_RTX)
1065 reg = ssa_rename_to_lookup (reg);
1067 /* It is possible for the variable to be uninitialized on
1068 edges in. Reduce the arity of the PHI so that we don't
1069 consider those edges. */
1070 if (reg == NULL || reg == RENAME_NO_RTX)
1072 if (! remove_phi_alternative (phi, bb))
1077 /* When we created the PHI nodes, we did not know what mode
1078 the register should be. Now that we've found an original,
1079 we can fill that in. */
1080 if (GET_MODE (SET_DEST (phi)) == VOIDmode)
1081 PUT_MODE (SET_DEST (phi), GET_MODE (reg));
1082 else if (GET_MODE (SET_DEST (phi)) != GET_MODE (reg))
1085 *phi_alternative (phi, bb) = reg;
1086 /* ??? Mark for a new ssa_uses entry. */
1089 insn = NEXT_INSN (insn);
1093 /* Step Three: Do the same to the children of this block in
1096 for (c = 0; c < n_basic_blocks; ++c)
1098 rename_block (c, idom);
1100 /* Step Four: Update the sets to refer to their new register,
1101 and restore ssa_rename_to to its previous state. */
1105 struct rename_set_data *next;
1106 rtx old_reg = *set_data->reg_loc;
1108 if (*set_data->reg_loc != set_data->old_reg)
1110 *set_data->reg_loc = set_data->new_reg;
1112 ssa_rename_to_insert (old_reg, set_data->prev_reg);
1114 next = set_data->next;
1121 rename_registers (nregs, idom)
1125 VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
1126 VARRAY_RTX_INIT (ssa_uses, nregs * 3, "ssa_uses");
1127 ssa_rename_from_initialize ();
1129 ssa_rename_to_pseudo = (rtx *) alloca (nregs * sizeof(rtx));
1130 bzero ((char *) ssa_rename_to_pseudo, nregs * sizeof(rtx));
1131 bzero ((char *) ssa_rename_to_hard,
1132 FIRST_PSEUDO_REGISTER * NUM_MACHINE_MODES * sizeof (rtx));
1134 rename_block (0, idom);
1136 /* ??? Update basic_block_live_at_start, and other flow info
1139 ssa_rename_to_pseudo = NULL;
1142 /* The main entry point for moving to SSA. */
1147 /* Element I is the set of blocks that set register I. */
1150 /* Dominator bitmaps. */
1151 sbitmap *dominators;
1155 /* Element I is the immediate dominator of block I. */
1160 /* Don't do it twice. */
1164 /* Need global_live_at_{start,end} up to date. */
1165 life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
1167 /* Compute dominators. */
1168 dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
1169 compute_flow_dominators (dominators, NULL);
1171 idom = (int *) alloca (n_basic_blocks * sizeof (int));
1172 memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
1173 compute_immediate_dominators (idom, dominators);
1175 sbitmap_vector_free (dominators);
1180 fputs (";; Immediate Dominators:\n", rtl_dump_file);
1181 for (i = 0; i < n_basic_blocks; ++i)
1182 fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]);
1183 fflush (rtl_dump_file);
1186 /* Compute dominance frontiers. */
1188 dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
1189 compute_dominance_frontiers (dfs, idom);
1193 dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
1194 "; Basic Block", dfs, n_basic_blocks);
1195 fflush (rtl_dump_file);
1198 /* Compute register evaluations. */
1200 ssa_max_reg_num = max_reg_num();
1201 nregs = ssa_max_reg_num;
1202 evals = sbitmap_vector_alloc (nregs, n_basic_blocks);
1203 find_evaluations (evals, nregs);
1205 /* Compute the iterated dominance frontier for each register. */
1207 idfs = sbitmap_vector_alloc (nregs, n_basic_blocks);
1208 compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);
1212 dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
1213 "; Register", idfs, nregs);
1214 fflush (rtl_dump_file);
1217 /* Insert the phi nodes. */
1219 insert_phi_nodes (idfs, evals, nregs);
1221 /* Rename the registers to satisfy SSA. */
1223 rename_registers (nregs, idom);
1225 /* All done! Clean up and go home. */
1227 sbitmap_vector_free (dfs);
1228 sbitmap_vector_free (evals);
1229 sbitmap_vector_free (idfs);
1232 reg_scan (get_insns (), max_reg_num (), 1);
1235 /* REG is the representative temporary of its partition. Add it to the
1236 set of nodes to be processed, if it hasn't been already. Return the
1237 index of this register in the node set. */
1240 ephi_add_node (reg, nodes, n_nodes)
1245 for (i = *n_nodes - 1; i >= 0; --i)
1246 if (REGNO (reg) == REGNO (nodes[i]))
1249 nodes[i = (*n_nodes)++] = reg;
1253 /* Part one of the topological sort. This is a forward (downward) search
1254 through the graph collecting a stack of nodes to process. Assuming no
1255 cycles, the nodes at top of the stack when we are finished will have
1256 no other dependancies. */
1259 ephi_forward (t, visited, succ, tstack)
1267 SET_BIT (visited, t);
1269 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1271 if (! TEST_BIT (visited, s))
1272 tstack = ephi_forward (s, visited, succ, tstack);
1279 /* Part two of the topological sort. The is a backward search through
1280 a cycle in the graph, copying the data forward as we go. */
1283 ephi_backward (t, visited, pred, nodes)
1285 sbitmap visited, *pred;
1290 SET_BIT (visited, t);
1292 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1294 if (! TEST_BIT (visited, p))
1296 ephi_backward (p, visited, pred, nodes);
1297 emit_move_insn (nodes[p], nodes[t]);
1302 /* Part two of the topological sort. Create the copy for a register
1303 and any cycle of which it is a member. */
1306 ephi_create (t, visited, pred, succ, nodes)
1308 sbitmap visited, *pred, *succ;
1311 rtx reg_u = NULL_RTX;
1312 int unvisited_predecessors = 0;
1315 /* Iterate through the predecessor list looking for unvisited nodes.
1316 If there are any, we have a cycle, and must deal with that. At
1317 the same time, look for a visited predecessor. If there is one,
1318 we won't need to create a temporary. */
1320 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1322 if (! TEST_BIT (visited, p))
1323 unvisited_predecessors = 1;
1328 if (unvisited_predecessors)
1330 /* We found a cycle. Copy out one element of the ring (if necessary),
1331 then traverse the ring copying as we go. */
1335 reg_u = gen_reg_rtx (GET_MODE (nodes[t]));
1336 emit_move_insn (reg_u, nodes[t]);
1339 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1341 if (! TEST_BIT (visited, p))
1343 ephi_backward (p, visited, pred, nodes);
1344 emit_move_insn (nodes[p], reg_u);
1350 /* No cycle. Just copy the value from a successor. */
1353 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1355 SET_BIT (visited, t);
1356 emit_move_insn (nodes[t], nodes[s]);
1362 /* Convert the edge to normal form. */
1365 eliminate_phi (e, reg_partition)
1367 partition reg_partition;
1370 sbitmap *pred, *succ;
1373 int *stack, *tstack;
1377 /* Collect an upper bound on the number of registers needing processing. */
1379 insn = first_insn_after_basic_block_note (e->dest);
1382 while (PHI_NODE_P (insn))
1384 insn = next_nonnote_insn (insn);
1391 /* Build the auxilliary graph R(B).
1393 The nodes of the graph are the members of the register partition
1394 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1395 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1397 nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
1398 pred = sbitmap_vector_alloc (n_nodes, n_nodes);
1399 succ = sbitmap_vector_alloc (n_nodes, n_nodes);
1400 sbitmap_vector_zero (pred, n_nodes);
1401 sbitmap_vector_zero (succ, n_nodes);
1403 insn = first_insn_after_basic_block_note (e->dest);
1406 for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
1408 rtx* preg = phi_alternative (PATTERN (insn), e->src->index);
1409 rtx tgt = SET_DEST (PATTERN (insn));
1412 /* There may be no phi alternative corresponding to this edge.
1413 This indicates that the phi variable is undefined along this
1419 if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
1422 reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
1423 tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
1424 /* If the two registers are already in the same partition,
1425 nothing will need to be done. */
1430 ireg = ephi_add_node (reg, nodes, &n_nodes);
1431 itgt = ephi_add_node (tgt, nodes, &n_nodes);
1433 SET_BIT (pred[ireg], itgt);
1434 SET_BIT (succ[itgt], ireg);
1441 /* Begin a topological sort of the graph. */
1443 visited = sbitmap_alloc (n_nodes);
1444 sbitmap_zero (visited);
1446 tstack = stack = (int *) alloca (n_nodes * sizeof (int));
1448 for (i = 0; i < n_nodes; ++i)
1449 if (! TEST_BIT (visited, i))
1450 tstack = ephi_forward (i, visited, succ, tstack);
1452 sbitmap_zero (visited);
1454 /* As we find a solution to the tsort, collect the implementation
1455 insns in a sequence. */
1458 while (tstack != stack)
1461 if (! TEST_BIT (visited, i))
1462 ephi_create (i, visited, pred, succ, nodes);
1465 insn = gen_sequence ();
1467 insert_insn_on_edge (insn, e);
1469 fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n",
1470 e->src->index, e->dest->index);
1472 sbitmap_free (visited);
1474 sbitmap_vector_free (pred);
1475 sbitmap_vector_free (succ);
1478 /* For basic block B, consider all phi insns which provide an
1479 alternative corresponding to an incoming abnormal critical edge.
1480 Place the phi alternative corresponding to that abnormal critical
1481 edge in the same register class as the destination of the set.
1483 From Morgan, p. 178:
1485 For each abnormal critical edge (C, B),
1486 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1487 and C is the ith predecessor of B,
1488 then T0 and Ti must be equivalent.
1490 Return non-zero iff any such cases were found for which the two
1491 regs were not already in the same class. */
1494 make_regs_equivalent_over_bad_edges (bb, reg_partition)
1496 partition reg_partition;
1499 basic_block b = BASIC_BLOCK (bb);
1502 /* Advance to the first phi node. */
1503 phi = first_insn_after_basic_block_note (b);
1505 /* Scan all the phi nodes. */
1508 phi = next_nonnote_insn (phi))
1512 rtx set = PATTERN (phi);
1513 rtx tgt = SET_DEST (set);
1515 /* The set target is expected to be an SSA register. */
1516 if (GET_CODE (tgt) != REG
1517 || !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt)))
1519 tgt_regno = REGNO (tgt);
1521 /* Scan incoming abnormal critical edges. */
1522 for (e = b->pred; e; e = e->pred_next)
1523 if ((e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL))
1524 == (EDGE_ABNORMAL | EDGE_CRITICAL))
1526 rtx *alt = phi_alternative (set, e->src->index);
1529 /* If there is no alternative corresponding to this edge,
1530 the value is undefined along the edge, so just go on. */
1534 /* The phi alternative is expected to be an SSA register. */
1535 if (GET_CODE (*alt) != REG
1536 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
1538 alt_regno = REGNO (*alt);
1540 /* If the set destination and the phi alternative aren't
1541 already in the same class... */
1542 if (partition_find (reg_partition, tgt_regno)
1543 != partition_find (reg_partition, alt_regno))
1545 /* ... make them such. */
1546 if (conflicting_hard_regs_p (tgt_regno, alt_regno))
1547 /* It is illegal to unify a hard register with a
1548 different register. */
1551 partition_union (reg_partition,
1552 tgt_regno, alt_regno);
1561 /* Consider phi insns in basic block BB pairwise. If the set target
1562 of both isns are equivalent pseudos, make the corresponding phi
1563 alternatives in each phi corresponding equivalent.
1565 Return nonzero if any new register classes were unioned. */
1568 make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
1570 partition reg_partition;
1573 basic_block b = BASIC_BLOCK (bb);
1576 /* Advance to the first phi node. */
1577 phi = first_insn_after_basic_block_note (b);
1579 /* Scan all the phi nodes. */
1582 phi = next_nonnote_insn (phi))
1584 rtx set = PATTERN (phi);
1585 /* The regno of the destination of the set. */
1586 int tgt_regno = REGNO (SET_DEST (PATTERN (phi)));
1588 rtx phi2 = next_nonnote_insn (phi);
1590 /* Scan all phi nodes following this one. */
1593 phi2 = next_nonnote_insn (phi2))
1595 rtx set2 = PATTERN (phi2);
1596 /* The regno of the destination of the set. */
1597 int tgt2_regno = REGNO (SET_DEST (set2));
1599 /* Are the set destinations equivalent regs? */
1600 if (partition_find (reg_partition, tgt_regno) ==
1601 partition_find (reg_partition, tgt2_regno))
1604 /* Scan over edges. */
1605 for (e = b->pred; e; e = e->pred_next)
1607 int pred_block = e->src->index;
1608 /* Identify the phi alternatives from both phi
1609 nodes corresponding to this edge. */
1610 rtx *alt = phi_alternative (set, pred_block);
1611 rtx *alt2 = phi_alternative (set2, pred_block);
1613 /* If one of the phi nodes doesn't have a
1614 corresponding alternative, just skip it. */
1615 if (alt == 0 || alt2 == 0)
1618 /* Both alternatives should be SSA registers. */
1619 if (GET_CODE (*alt) != REG
1620 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
1622 if (GET_CODE (*alt2) != REG
1623 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2)))
1626 /* If the alternatives aren't already in the same
1628 if (partition_find (reg_partition, REGNO (*alt))
1629 != partition_find (reg_partition, REGNO (*alt2)))
1631 /* ... make them so. */
1632 if (conflicting_hard_regs_p (REGNO (*alt), REGNO (*alt2)))
1633 /* It is illegal to unify a hard register with
1634 a different register. */
1637 partition_union (reg_partition,
1638 REGNO (*alt), REGNO (*alt2));
1649 /* Compute a conservative partition of outstanding pseudo registers.
1650 See Morgan 7.3.1. */
1653 compute_conservative_reg_partition ()
1658 /* We don't actually work with hard registers, but it's easier to
1659 carry them around anyway rather than constantly doing register
1660 number arithmetic. */
1662 partition_new (ssa_definition->num_elements);
1664 /* The first priority is to make sure registers that might have to
1665 be copied on abnormal critical edges are placed in the same
1666 partition. This saves us from having to split abnormal critical
1668 for (bb = n_basic_blocks; --bb >= 0; )
1669 changed += make_regs_equivalent_over_bad_edges (bb, p);
1671 /* Now we have to insure that corresponding arguments of phi nodes
1672 assigning to corresponding regs are equivalent. Iterate until
1677 for (bb = n_basic_blocks; --bb >= 0; )
1678 changed += make_equivalent_phi_alternatives_equivalent (bb, p);
1684 /* The following functions compute a register partition that attempts
1685 to eliminate as many reg copies and phi node copies as possible by
1686 coalescing registers. This is the strategy:
1688 1. As in the conservative case, the top priority is to coalesce
1689 registers that otherwise would cause copies to be placed on
1690 abnormal critical edges (which isn't possible).
1692 2. Figure out which regs are involved (in the LHS or RHS) of
1693 copies and phi nodes. Compute conflicts among these regs.
1695 3. Walk around the instruction stream, placing two regs in the
1696 same class of the partition if one appears on the LHS and the
1697 other on the RHS of a copy or phi node and the two regs don't
1698 conflict. The conflict information of course needs to be
1701 4. If anything has changed, there may be new opportunities to
1702 coalesce regs, so go back to 2.
1705 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1706 same class of partition P, if they aren't already. Update
1707 CONFLICTS appropriately.
1709 Returns one if REG1 and REG2 were placed in the same class but were
1710 not previously; zero otherwise.
1712 See Morgan figure 11.15. */
1715 coalesce_if_unconflicting (p, conflicts, reg1, reg2)
1717 conflict_graph conflicts;
1723 /* Work only on SSA registers. */
1724 if (!CONVERT_REGISTER_TO_SSA_P (reg1) || !CONVERT_REGISTER_TO_SSA_P (reg2))
1727 /* Find the canonical regs for the classes containing REG1 and
1729 reg1 = partition_find (p, reg1);
1730 reg2 = partition_find (p, reg2);
1732 /* If they're already in the same class, there's nothing to do. */
1736 /* If the regs conflict, our hands are tied. */
1737 if (conflicting_hard_regs_p (reg1, reg2) ||
1738 conflict_graph_conflict_p (conflicts, reg1, reg2))
1741 /* We're good to go. Put the regs in the same partition. */
1742 partition_union (p, reg1, reg2);
1744 /* Find the new canonical reg for the merged class. */
1745 reg = partition_find (p, reg1);
1747 /* Merge conflicts from the two previous classes. */
1748 conflict_graph_merge_regs (conflicts, reg, reg1);
1749 conflict_graph_merge_regs (conflicts, reg, reg2);
1754 /* For each register copy insn in basic block BB, place the LHS and
1755 RHS regs in the same class in partition P if they do not conflict
1756 according to CONFLICTS.
1758 Returns the number of changes that were made to P.
1760 See Morgan figure 11.14. */
1763 coalesce_regs_in_copies (bb, p, conflicts)
1766 conflict_graph conflicts;
1772 /* Scan the instruction stream of the block. */
1773 for (insn = bb->head; insn != end; insn = NEXT_INSN (insn))
1779 /* If this isn't a set insn, go to the next insn. */
1780 if (GET_CODE (insn) != INSN)
1782 pattern = PATTERN (insn);
1783 if (GET_CODE (pattern) != SET)
1786 src = SET_SRC (pattern);
1787 dest = SET_DEST (pattern);
1789 /* We're only looking for copies. */
1790 if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
1793 /* Coalesce only if the reg modes are the same. As long as
1794 each reg's rtx is unique, it can have only one mode, so two
1795 pseudos of different modes can't be coalesced into one.
1797 FIXME: We can probably get around this by inserting SUBREGs
1798 where appropriate, but for now we don't bother. */
1799 if (GET_MODE (src) != GET_MODE (dest))
1802 /* Found a copy; see if we can use the same reg for both the
1803 source and destination (and thus eliminate the copy,
1805 changed += coalesce_if_unconflicting (p, conflicts,
1806 REGNO (src), REGNO (dest));
1812 struct phi_coalesce_context
1815 conflict_graph conflicts;
1819 /* Callback function for for_each_successor_phi. If the set
1820 destination and the phi alternative regs do not conflict, place
1821 them in the same paritition class. DATA is a pointer to a
1822 phi_coalesce_context struct. */
1825 coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
1826 rtx insn ATTRIBUTE_UNUSED;
1831 struct phi_coalesce_context *context =
1832 (struct phi_coalesce_context *) data;
1834 /* Attempt to use the same reg, if they don't conflict. */
1836 += coalesce_if_unconflicting (context->p, context->conflicts,
1837 dest_regno, src_regno);
1841 /* For each alternative in a phi function corresponding to basic block
1842 BB (in phi nodes in successor block to BB), place the reg in the
1843 phi alternative and the reg to which the phi value is set into the
1844 same class in partition P, if allowed by CONFLICTS.
1846 Return the number of changes that were made to P.
1848 See Morgan figure 11.14. */
1851 coalesce_regs_in_successor_phi_nodes (bb, p, conflicts)
1854 conflict_graph conflicts;
1856 struct phi_coalesce_context context;
1858 context.conflicts = conflicts;
1859 context.changed = 0;
1861 for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);
1863 return context.changed;
1866 /* Compute and return a partition of pseudos. Where possible,
1867 non-conflicting pseudos are placed in the same class.
1869 The caller is responsible for deallocating the returned partition. */
1872 compute_coalesced_reg_partition ()
1878 partition_new (ssa_definition->num_elements);
1880 /* The first priority is to make sure registers that might have to
1881 be copied on abnormal critical edges are placed in the same
1882 partition. This saves us from having to split abnormal critical
1883 edges (which can't be done). */
1884 for (bb = n_basic_blocks; --bb >= 0; )
1885 make_regs_equivalent_over_bad_edges (bb, p);
1889 regset_head phi_set;
1890 conflict_graph conflicts;
1894 /* Build the set of registers involved in phi nodes, either as
1895 arguments to the phi function or as the target of a set. */
1896 INITIALIZE_REG_SET (phi_set);
1897 mark_phi_and_copy_regs (&phi_set);
1899 /* Compute conflicts. */
1900 conflicts = conflict_graph_compute (&phi_set, p);
1902 /* FIXME: Better would be to process most frequently executed
1903 blocks first, so that most frequently executed copies would
1904 be more likely to be removed by register coalescing. But any
1905 order will generate correct, if non-optimal, results. */
1906 for (bb = n_basic_blocks; --bb >= 0; )
1908 basic_block block = BASIC_BLOCK (bb);
1909 changed += coalesce_regs_in_copies (block, p, conflicts);
1911 coalesce_regs_in_successor_phi_nodes (block, p, conflicts);
1914 conflict_graph_delete (conflicts);
1916 while (changed > 0);
1921 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1922 components (a REG or a CONST_INT). DATA is a reg set in which to
1923 set all regs. Called from for_each_rtx. */
1926 mark_reg_in_phi (ptr, data)
1931 regset set = (regset) data;
1933 switch (GET_CODE (expr))
1936 SET_REGNO_REG_SET (set, REGNO (expr));
1946 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1947 set from a phi expression, or used as an argument in one. Also
1948 mark regs that are the source or target of a reg copy. Uses
1952 mark_phi_and_copy_regs (phi_set)
1957 /* Scan the definitions of all regs. */
1958 for (reg = 0; reg < VARRAY_SIZE (ssa_definition); ++reg)
1959 if (CONVERT_REGISTER_TO_SSA_P (reg))
1961 rtx insn = VARRAY_RTX (ssa_definition, reg);
1967 pattern = PATTERN (insn);
1968 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1970 if (GET_CODE (pattern) != SET)
1972 src = SET_SRC (pattern);
1974 if (GET_CODE (src) == REG)
1976 /* It's a reg copy. */
1977 SET_REGNO_REG_SET (phi_set, reg);
1978 SET_REGNO_REG_SET (phi_set, REGNO (src));
1980 else if (GET_CODE (src) == PHI)
1982 /* It's a phi node. Mark the reg being set. */
1983 SET_REGNO_REG_SET (phi_set, reg);
1984 /* Mark the regs used in the phi function. */
1985 for_each_rtx (&src, mark_reg_in_phi, phi_set);
1987 /* ... else nothing to do. */
1991 /* Rename regs in insn PTR that are equivalent. DATA is the register
1992 partition which specifies equivalences. */
1995 rename_equivalent_regs_in_insn (ptr, data)
2000 partition reg_partition = (partition) data;
2005 switch (GET_CODE (x))
2008 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
2010 unsigned int regno = REGNO (x);
2011 unsigned int new_regno = partition_find (reg_partition, regno);
2012 rtx canonical_element_rtx = ssa_rename_from_lookup (new_regno);
2014 if (canonical_element_rtx != NULL_RTX &&
2015 HARD_REGISTER_P (canonical_element_rtx))
2017 if (REGNO (canonical_element_rtx) != regno)
2018 *ptr = canonical_element_rtx;
2020 else if (regno != new_regno)
2022 rtx new_reg = regno_reg_rtx[new_regno];
2023 if (GET_MODE (x) != GET_MODE (new_reg))
2031 /* No need to rename the phi nodes. We'll check equivalence
2032 when inserting copies. */
2036 /* Anything else, continue traversing. */
2041 /* Record the register's canonical element stored in SRFP in the
2042 canonical_elements sbitmap packaged in DATA. This function is used
2043 as a callback function for traversing ssa_rename_from. */
2046 record_canonical_element_1 (srfp, data)
2050 unsigned int reg = ((ssa_rename_from_pair *) *srfp)->reg;
2051 sbitmap canonical_elements =
2052 ((struct ssa_rename_from_hash_table_data *) data)->canonical_elements;
2053 partition reg_partition =
2054 ((struct ssa_rename_from_hash_table_data *) data)->reg_partition;
2056 SET_BIT (canonical_elements, partition_find (reg_partition, reg));
2060 /* For each class in the REG_PARTITION corresponding to a particular
2061 hard register and machine mode, check that there are no other
2062 classes with the same hard register and machine mode. Returns
2063 nonzero if this is the case, i.e., the partition is acceptable. */
2066 check_hard_regs_in_partition (reg_partition)
2067 partition reg_partition;
2069 /* CANONICAL_ELEMENTS has a nonzero bit if a class with the given register
2070 number and machine mode has already been seen. This is a
2071 problem with the partition. */
2072 sbitmap canonical_elements;
2074 int already_seen[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
2078 /* Collect a list of canonical elements. */
2079 canonical_elements = sbitmap_alloc (max_reg_num ());
2080 sbitmap_zero (canonical_elements);
2081 ssa_rename_from_traverse (&record_canonical_element_1,
2082 canonical_elements, reg_partition);
2084 /* We have not seen any hard register uses. */
2085 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; ++reg)
2086 for (mach_mode = 0; mach_mode < NUM_MACHINE_MODES; ++mach_mode)
2087 already_seen[reg][mach_mode] = 0;
2089 /* Check for classes with the same hard register and machine mode. */
2090 EXECUTE_IF_SET_IN_SBITMAP (canonical_elements, 0, element_index,
2092 rtx hard_reg_rtx = ssa_rename_from_lookup (element_index);
2093 if (hard_reg_rtx != NULL_RTX &&
2094 HARD_REGISTER_P (hard_reg_rtx) &&
2095 already_seen[REGNO (hard_reg_rtx)][GET_MODE (hard_reg_rtx)] != 0)
2096 /* Two distinct partition classes should be mapped to the same
2101 sbitmap_free (canonical_elements);
2106 /* Rename regs that are equivalent in REG_PARTITION. Also collapse
2107 any SEQUENCE insns. */
2110 rename_equivalent_regs (reg_partition)
2111 partition reg_partition;
2115 for (bb = n_basic_blocks; --bb >= 0; )
2117 basic_block b = BASIC_BLOCK (bb);
2127 for_each_rtx (&PATTERN (insn),
2128 rename_equivalent_regs_in_insn,
2130 for_each_rtx (®_NOTES (insn),
2131 rename_equivalent_regs_in_insn,
2134 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2136 rtx s = PATTERN (insn);
2137 int slen = XVECLEN (s, 0);
2143 PATTERN (insn) = XVECEXP (s, 0, slen-1);
2144 for (i = 0; i < slen - 1; i++)
2145 emit_block_insn_before (XVECEXP (s, 0, i), insn, b);
2149 next = NEXT_INSN (insn);
2151 while (insn != last);
2155 /* The main entry point for moving from SSA. */
2161 partition reg_partition;
2162 rtx insns = get_insns ();
2164 /* Need global_live_at_{start,end} up to date. */
2165 life_analysis (insns, NULL,
2166 PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE | PROP_DEATH_NOTES);
2168 /* Figure out which regs in copies and phi nodes don't conflict and
2169 therefore can be coalesced. */
2170 if (conservative_reg_partition)
2171 reg_partition = compute_conservative_reg_partition ();
2173 reg_partition = compute_coalesced_reg_partition ();
2175 if (!check_hard_regs_in_partition (reg_partition))
2176 /* Two separate partitions should correspond to the same hard
2177 register but do not. */
2180 rename_equivalent_regs (reg_partition);
2182 /* Eliminate the PHI nodes. */
2183 for (bb = n_basic_blocks; --bb >= 0; )
2185 basic_block b = BASIC_BLOCK (bb);
2188 for (e = b->pred; e; e = e->pred_next)
2189 if (e->src != ENTRY_BLOCK_PTR)
2190 eliminate_phi (e, reg_partition);
2193 partition_delete (reg_partition);
2195 /* Actually delete the PHI nodes. */
2196 for (bb = n_basic_blocks; --bb >= 0; )
2198 rtx insn = BLOCK_HEAD (bb);
2202 /* If this is a PHI node delete it. */
2203 if (PHI_NODE_P (insn))
2205 if (insn == BLOCK_END (bb))
2206 BLOCK_END (bb) = PREV_INSN (insn);
2207 insn = delete_insn (insn);
2209 /* Since all the phi nodes come at the beginning of the
2210 block, if we find an ordinary insn, we can stop looking
2211 for more phi nodes. */
2212 else if (INSN_P (insn))
2214 /* If we've reached the end of the block, stop. */
2215 else if (insn == BLOCK_END (bb))
2218 insn = NEXT_INSN (insn);
2222 /* Commit all the copy nodes needed to convert out of SSA form. */
2223 commit_edge_insertions ();
2227 count_or_remove_death_notes (NULL, 1);
2229 /* Deallocate the data structures. */
2230 VARRAY_FREE (ssa_definition);
2231 VARRAY_FREE (ssa_uses);
2232 ssa_rename_from_free ();
2235 /* Scan phi nodes in successors to BB. For each such phi node that
2236 has a phi alternative value corresponding to BB, invoke FN. FN
2237 is passed the entire phi node insn, the regno of the set
2238 destination, the regno of the phi argument corresponding to BB,
2241 If FN ever returns non-zero, stops immediately and returns this
2242 value. Otherwise, returns zero. */
2245 for_each_successor_phi (bb, fn, data)
2247 successor_phi_fn fn;
2252 if (bb == EXIT_BLOCK_PTR)
2255 /* Scan outgoing edges. */
2256 for (e = bb->succ; e != NULL; e = e->succ_next)
2260 basic_block successor = e->dest;
2261 if (successor == ENTRY_BLOCK_PTR
2262 || successor == EXIT_BLOCK_PTR)
2265 /* Advance to the first non-label insn of the successor block. */
2266 insn = first_insn_after_basic_block_note (successor);
2271 /* Scan phi nodes in the successor. */
2272 for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
2275 rtx phi_set = PATTERN (insn);
2276 rtx *alternative = phi_alternative (phi_set, bb->index);
2279 /* This phi function may not have an alternative
2280 corresponding to the incoming edge, indicating the
2281 assigned variable is not defined along the edge. */
2282 if (alternative == NULL)
2284 phi_src = *alternative;
2286 /* Invoke the callback. */
2287 result = (*fn) (insn, REGNO (SET_DEST (phi_set)),
2288 REGNO (phi_src), data);
2290 /* Terminate if requested. */
2299 /* Assuming the ssa_rename_from mapping has been established, yields
2300 nonzero if 1) only one SSA register of REG1 and REG2 comes from a
2301 hard register or 2) both SSA registers REG1 and REG2 come from
2302 different hard registers. */
2305 conflicting_hard_regs_p (reg1, reg2)
2309 int orig_reg1 = original_register (reg1);
2310 int orig_reg2 = original_register (reg2);
2311 if (HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2)
2312 && orig_reg1 != orig_reg2)
2314 if (HARD_REGISTER_NUM_P (orig_reg1) && !HARD_REGISTER_NUM_P (orig_reg2))
2316 if (!HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2))