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
38 #include "hard-reg-set.h"
42 #include "insn-config.h"
44 #include "basic-block.h"
46 #include "partition.h"
51 Handle subregs better, maybe. For now, if a reg that's set in a
52 subreg expression is duplicated going into SSA form, an extra copy
53 is inserted first that copies the entire reg into the duplicate, so
54 that the other bits are preserved. This isn't strictly SSA, since
55 at least part of the reg is assigned in more than one place (though
58 ??? What to do about strict_low_part. Probably I'll have to split
59 them out of their current instructions first thing.
61 Actually the best solution may be to have a kind of "mid-level rtl"
62 in which the RTL encodes exactly what we want, without exposing a
63 lot of niggling processor details. At some later point we lower
64 the representation, calling back into optabs to finish any necessary
68 /* If conservative_reg_partition is non-zero, use a conservative
69 register partitioning algorithm (which leaves more regs after
70 emerging from SSA) instead of the coalescing one. This is being
71 left in for a limited time only, as a debugging tool until the
72 coalescing algorithm is validated. */
73 static int conservative_reg_partition;
75 /* This flag is set when the CFG is in SSA form. */
78 /* Element I is the single instruction that sets register I+PSEUDO. */
79 varray_type ssa_definition;
81 /* Element I is an INSN_LIST of instructions that use register I+PSEUDO. */
84 /* Element I-PSEUDO is the normal register that originated the ssa
85 register in question. */
86 varray_type ssa_rename_from;
88 /* The running target ssa register for a given normal register. */
89 static rtx *ssa_rename_to;
91 /* The number of registers that were live on entry to the SSA routines. */
92 static unsigned int ssa_max_reg_num;
94 /* Local function prototypes. */
96 struct rename_context;
98 static inline rtx * phi_alternative
101 static int remove_phi_alternative
103 static void simplify_to_immediate_dominators
104 PARAMS ((int *idom, sbitmap *dominators));
105 static void compute_dominance_frontiers_1
106 PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
107 static void compute_dominance_frontiers
108 PARAMS ((sbitmap *frontiers, int *idom));
109 static void find_evaluations_1
110 PARAMS ((rtx dest, rtx set, void *data));
111 static void find_evaluations
112 PARAMS ((sbitmap *evals, int nregs));
113 static void compute_iterated_dominance_frontiers
114 PARAMS ((sbitmap *idfs, sbitmap *frontiers, sbitmap *evals, int nregs));
115 static void insert_phi_node
116 PARAMS ((int regno, int b));
117 static void insert_phi_nodes
118 PARAMS ((sbitmap *idfs, sbitmap *evals, int nregs));
119 static void create_delayed_rename
120 PARAMS ((struct rename_context *, rtx *));
121 static void apply_delayed_renames
122 PARAMS ((struct rename_context *));
123 static int rename_insn_1
124 PARAMS ((rtx *ptr, void *data));
125 static void rename_block
126 PARAMS ((int b, int *idom));
127 static void rename_registers
128 PARAMS ((int nregs, int *idom));
130 static inline int ephi_add_node
131 PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
132 static int * ephi_forward
133 PARAMS ((int t, sbitmap visited, sbitmap *succ, int *tstack));
134 static void ephi_backward
135 PARAMS ((int t, sbitmap visited, sbitmap *pred, rtx *nodes));
136 static void ephi_create
137 PARAMS ((int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes));
138 static void eliminate_phi
139 PARAMS ((edge e, partition reg_partition));
140 static int make_regs_equivalent_over_bad_edges
141 PARAMS ((int bb, partition reg_partition));
143 /* These are used only in the conservative register partitioning
145 static int make_equivalent_phi_alternatives_equivalent
146 PARAMS ((int bb, partition reg_partition));
147 static partition compute_conservative_reg_partition
149 static int rename_equivalent_regs_in_insn
150 PARAMS ((rtx *ptr, void *data));
152 /* These are used in the register coalescing algorithm. */
153 static int coalesce_if_unconflicting
154 PARAMS ((partition p, conflict_graph conflicts, int reg1, int reg2));
155 static int coalesce_regs_in_copies
156 PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
157 static int coalesce_reg_in_phi
158 PARAMS ((rtx, int dest_regno, int src_regno, void *data));
159 static int coalesce_regs_in_successor_phi_nodes
160 PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
161 static partition compute_coalesced_reg_partition
163 static int mark_reg_in_phi
164 PARAMS ((rtx *ptr, void *data));
165 static void mark_phi_and_copy_regs
166 PARAMS ((regset phi_set));
168 static int rename_equivalent_regs_in_insn
169 PARAMS ((rtx *ptr, void *data));
170 static void rename_equivalent_regs
171 PARAMS ((partition reg_partition));
174 /* Given the SET of a PHI node, return the address of the alternative
175 for predecessor block C. */
178 phi_alternative (set, c)
182 rtvec phi_vec = XVEC (SET_SRC (set), 0);
185 for (v = GET_NUM_ELEM (phi_vec) - 2; v >= 0; v -= 2)
186 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
187 return &RTVEC_ELT (phi_vec, v);
192 /* Given the SET of a phi node, remove the alternative for predecessor
193 block C. Return non-zero on success, or zero if no alternative is
197 remove_phi_alternative (set, c)
201 rtvec phi_vec = XVEC (SET_SRC (set), 0);
202 int num_elem = GET_NUM_ELEM (phi_vec);
205 for (v = num_elem - 2; v >= 0; v -= 2)
206 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
208 if (v < num_elem - 2)
210 RTVEC_ELT (phi_vec, v) = RTVEC_ELT (phi_vec, num_elem - 2);
211 RTVEC_ELT (phi_vec, v + 1) = RTVEC_ELT (phi_vec, num_elem - 1);
213 PUT_NUM_ELEM (phi_vec, num_elem - 2);
220 /* Computing the Immediate Dominators:
222 Throughout, we don't actually want the full dominators set as
223 calculated by flow, but rather the immediate dominators.
227 simplify_to_immediate_dominators (idom, dominators)
234 tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
236 /* Begin with tmp(n) = dom(n) - { n }. */
237 for (b = n_basic_blocks; --b >= 0; )
239 sbitmap_copy (tmp[b], dominators[b]);
240 RESET_BIT (tmp[b], b);
243 /* Subtract out all of our dominator's dominators. */
244 for (b = n_basic_blocks; --b >= 0; )
246 sbitmap tmp_b = tmp[b];
249 for (s = n_basic_blocks; --s >= 0; )
250 if (TEST_BIT (tmp_b, s))
251 sbitmap_difference (tmp_b, tmp_b, tmp[s]);
254 /* Find the one bit set in the bitmap and put it in the output array. */
255 for (b = n_basic_blocks; --b >= 0; )
258 EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
261 sbitmap_vector_free (tmp);
265 /* For all registers, find all blocks in which they are set.
267 This is the transform of what would be local kill information that
268 we ought to be getting from flow. */
270 static sbitmap *fe_evals;
271 static int fe_current_bb;
274 find_evaluations_1 (dest, set, data)
276 rtx set ATTRIBUTE_UNUSED;
277 void *data ATTRIBUTE_UNUSED;
279 if (GET_CODE (dest) == REG
280 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
281 SET_BIT (fe_evals[REGNO (dest) - FIRST_PSEUDO_REGISTER], fe_current_bb);
285 find_evaluations (evals, nregs)
291 sbitmap_vector_zero (evals, nregs);
294 for (bb = n_basic_blocks; --bb >= 0; )
300 last = BLOCK_END (bb);
303 if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
304 note_stores (PATTERN (p), find_evaluations_1, NULL);
314 /* Computing the Dominance Frontier:
316 As decribed in Morgan, section 3.5, this may be done simply by
317 walking the dominator tree bottom-up, computing the frontier for
318 the children before the parent. When considering a block B,
321 (1) A flow graph edge leaving B that does not lead to a child
322 of B in the dominator tree must be a block that is either equal
323 to B or not dominated by B. Such blocks belong in the frontier
326 (2) Consider a block X in the frontier of one of the children C
327 of B. If X is not equal to B and is not dominated by B, it
328 is in the frontier of B.
332 compute_dominance_frontiers_1 (frontiers, idom, bb, done)
338 basic_block b = BASIC_BLOCK (bb);
343 sbitmap_zero (frontiers[bb]);
345 /* Do the frontier of the children first. Not all children in the
346 dominator tree (blocks dominated by this one) are children in the
347 CFG, so check all blocks. */
348 for (c = 0; c < n_basic_blocks; ++c)
349 if (idom[c] == bb && ! TEST_BIT (done, c))
350 compute_dominance_frontiers_1 (frontiers, idom, c, done);
352 /* Find blocks conforming to rule (1) above. */
353 for (e = b->succ; e; e = e->succ_next)
355 if (e->dest == EXIT_BLOCK_PTR)
357 if (idom[e->dest->index] != bb)
358 SET_BIT (frontiers[bb], e->dest->index);
361 /* Find blocks conforming to rule (2). */
362 for (c = 0; c < n_basic_blocks; ++c)
366 EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x,
369 SET_BIT (frontiers[bb], x);
375 compute_dominance_frontiers (frontiers, idom)
379 sbitmap done = sbitmap_alloc (n_basic_blocks);
382 compute_dominance_frontiers_1 (frontiers, idom, 0, done);
388 /* Computing the Iterated Dominance Frontier:
390 This is the set of merge points for a given register.
392 This is not particularly intuitive. See section 7.1 of Morgan, in
393 particular figures 7.3 and 7.4 and the immediately surrounding text.
397 compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs)
406 worklist = sbitmap_alloc (n_basic_blocks);
408 for (reg = 0; reg < nregs; ++reg)
410 sbitmap idf = idfs[reg];
413 /* Start the iterative process by considering those blocks that
414 evaluate REG. We'll add their dominance frontiers to the
415 IDF, and then consider the blocks we just added. */
416 sbitmap_copy (worklist, evals[reg]);
418 /* Morgan's algorithm is incorrect here. Blocks that evaluate
419 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
422 /* Iterate until the worklist is empty. */
427 EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b,
429 RESET_BIT (worklist, b);
430 /* For each block on the worklist, add to the IDF all
431 blocks on its dominance frontier that aren't already
432 on the IDF. Every block that's added is also added
434 sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf);
435 sbitmap_a_or_b (idf, idf, frontiers[b]);
442 sbitmap_free (worklist);
446 fprintf(rtl_dump_file,
447 "Iterated dominance frontier: %d passes on %d regs.\n",
453 /* Insert the phi nodes. */
456 insert_phi_node (regno, bb)
459 basic_block b = BASIC_BLOCK (bb);
465 /* Find out how many predecessors there are. */
466 for (e = b->pred, npred = 0; e; e = e->pred_next)
467 if (e->src != ENTRY_BLOCK_PTR)
470 /* If this block has no "interesting" preds, then there is nothing to
471 do. Consider a block that only has the entry block as a pred. */
475 /* This is the register to which the phi function will be assinged. */
476 reg = regno_reg_rtx[regno + FIRST_PSEUDO_REGISTER];
478 /* Construct the arguments to the PHI node. The use of pc_rtx is just
479 a placeholder; we'll insert the proper value in rename_registers. */
480 vec = rtvec_alloc (npred * 2);
481 for (e = b->pred, i = 0; e ; e = e->pred_next, i += 2)
482 if (e->src != ENTRY_BLOCK_PTR)
484 RTVEC_ELT (vec, i + 0) = pc_rtx;
485 RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index);
488 phi = gen_rtx_PHI (VOIDmode, vec);
489 phi = gen_rtx_SET (VOIDmode, reg, phi);
491 if (GET_CODE (b->head) == CODE_LABEL)
492 emit_insn_after (phi, b->head);
494 b->head = emit_insn_before (phi, b->head);
499 insert_phi_nodes (idfs, evals, nregs)
501 sbitmap *evals ATTRIBUTE_UNUSED;
506 for (reg = 0; reg < nregs; ++reg)
509 EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b,
511 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
512 reg + FIRST_PSEUDO_REGISTER))
513 insert_phi_node (reg, b);
518 /* Rename the registers to conform to SSA.
520 This is essentially the algorithm presented in Figure 7.8 of Morgan,
521 with a few changes to reduce pattern search time in favour of a bit
522 more memory usage. */
525 /* One of these is created for each set. It will live in a list local
526 to its basic block for the duration of that block's processing. */
527 struct rename_set_data
529 struct rename_set_data *next;
530 /* This is the SET_DEST of the (first) SET that sets the REG. */
532 /* This is what used to be at *REG_LOC. */
534 /* This is the REG that will replace OLD_REG. It's set only
535 when the rename data is moved onto the DONE_RENAMES queue. */
537 /* This is what to restore ssa_rename_to[REGNO (old_reg)] to.
538 It is usually the previous contents of ssa_rename_to[REGNO (old_reg)]. */
540 /* This is the insn that contains all the SETs of the REG. */
544 /* This struct is used to pass information to callback functions while
545 renaming registers. */
546 struct rename_context
548 struct rename_set_data *new_renames;
549 struct rename_set_data *done_renames;
553 /* Queue the rename of *REG_LOC. */
555 create_delayed_rename (c, reg_loc)
556 struct rename_context *c;
559 struct rename_set_data *r;
560 r = (struct rename_set_data *) xmalloc (sizeof(*r));
562 if (GET_CODE (*reg_loc) != REG
563 || REGNO (*reg_loc) < FIRST_PSEUDO_REGISTER)
566 r->reg_loc = reg_loc;
567 r->old_reg = *reg_loc;
568 r->prev_reg = ssa_rename_to [REGNO (r->old_reg) - FIRST_PSEUDO_REGISTER];
569 r->set_insn = c->current_insn;
570 r->next = c->new_renames;
574 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
575 reused. If, during processing, a register has not yet been touched,
576 ssa_rename_to[regno] will be NULL. Now, in the course of pushing
577 and popping values from ssa_rename_to, when we would ordinarily
578 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
579 same as NULL, except that it signals that the original regno has
580 already been reused. */
581 #define RENAME_NO_RTX pc_rtx
583 /* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
584 applying all the renames on NEW_RENAMES. */
587 apply_delayed_renames (c)
588 struct rename_context *c;
590 struct rename_set_data *r;
591 struct rename_set_data *last_r = NULL;
593 for (r = c->new_renames; r != NULL; r = r->next)
595 int regno = REGNO (r->old_reg);
598 /* Failure here means that someone has a PARALLEL that sets
599 a register twice (bad!). */
600 if (ssa_rename_to [regno - FIRST_PSEUDO_REGISTER] != r->prev_reg)
602 /* Failure here means we have changed REG_LOC before applying
604 /* For the first set we come across, reuse the original regno. */
605 if (r->prev_reg == NULL_RTX)
607 r->new_reg = r->old_reg;
608 /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
609 r->prev_reg = RENAME_NO_RTX;
612 r->new_reg = gen_reg_rtx (GET_MODE (r->old_reg));
613 new_regno = REGNO (r->new_reg);
614 ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] = r->new_reg;
616 if (new_regno >= (int) ssa_definition->num_elements)
618 int new_limit = new_regno * 5 / 4;
619 ssa_definition = VARRAY_GROW (ssa_definition, new_limit);
620 ssa_uses = VARRAY_GROW (ssa_uses, new_limit);
621 ssa_rename_from = VARRAY_GROW (ssa_rename_from, new_limit);
624 VARRAY_RTX (ssa_definition, new_regno) = r->set_insn;
625 VARRAY_RTX (ssa_rename_from, new_regno) = r->old_reg;
631 last_r->next = c->done_renames;
632 c->done_renames = c->new_renames;
633 c->new_renames = NULL;
637 /* Part one of the first step of rename_block, called through for_each_rtx.
638 Mark pseudos that are set for later update. Transform uses of pseudos. */
641 rename_insn_1 (ptr, data)
646 struct rename_context *context = data;
651 switch (GET_CODE (x))
655 rtx *destp = &SET_DEST (x);
656 rtx dest = SET_DEST (x);
658 /* Some SETs also use the REG specified in their LHS.
659 These can be detected by the presence of
660 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
661 in the LHS. Handle these by changing
662 (set (subreg (reg foo)) ...)
664 (sequence [(set (reg foo_1) (reg foo))
665 (set (subreg (reg foo_1)) ...)])
667 FIXME: Much of the time this is too much. For many libcalls,
668 paradoxical SUBREGs, etc., the input register is dead. We should
669 recognise this in rename_block or here and not make a false
672 if (GET_CODE (dest) == STRICT_LOW_PART
673 || GET_CODE (dest) == SUBREG
674 || GET_CODE (dest) == SIGN_EXTRACT
675 || GET_CODE (dest) == ZERO_EXTRACT)
680 while (GET_CODE (reg) == STRICT_LOW_PART
681 || GET_CODE (reg) == SUBREG
682 || GET_CODE (reg) == SIGN_EXTRACT
683 || GET_CODE (reg) == ZERO_EXTRACT)
686 if (GET_CODE (reg) == REG
687 && REGNO (reg) >= FIRST_PSEUDO_REGISTER)
689 /* Generate (set reg reg), and do renaming on it so
690 that it becomes (set reg_1 reg_0), and we will
691 replace reg with reg_1 in the SUBREG. */
693 struct rename_set_data *saved_new_renames;
694 saved_new_renames = context->new_renames;
695 context->new_renames = NULL;
696 i = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
697 for_each_rtx (&i, rename_insn_1, data);
698 apply_delayed_renames (context);
699 context->new_renames = saved_new_renames;
702 else if (GET_CODE (dest) == REG
703 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
705 /* We found a genuine set of an interesting register. Tag
706 it so that we can create a new name for it after we finish
707 processing this insn. */
709 create_delayed_rename (context, destp);
711 /* Since we do not wish to (directly) traverse the
712 SET_DEST, recurse through for_each_rtx for the SET_SRC
714 if (GET_CODE (x) == SET)
715 for_each_rtx (&SET_SRC (x), rename_insn_1, data);
719 /* Otherwise, this was not an interesting destination. Continue
720 on, marking uses as normal. */
725 if (REGNO (x) >= FIRST_PSEUDO_REGISTER
726 && REGNO (x) < ssa_max_reg_num)
728 rtx new_reg = ssa_rename_to[REGNO(x) - FIRST_PSEUDO_REGISTER];
730 if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
732 if (GET_MODE (x) != GET_MODE (new_reg))
736 /* Else this is a use before a set. Warn? */
741 /* Never muck with the phi. We do that elsewhere, special-like. */
745 /* Anything else, continue traversing. */
751 rename_block (bb, idom)
755 basic_block b = BASIC_BLOCK (bb);
757 rtx insn, next, last;
758 struct rename_set_data *set_data = NULL;
761 /* Step One: Walk the basic block, adding new names for sets and
769 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
771 struct rename_context context;
772 context.done_renames = set_data;
773 context.new_renames = NULL;
774 context.current_insn = insn;
777 for_each_rtx (&PATTERN (insn), rename_insn_1, &context);
778 for_each_rtx (®_NOTES (insn), rename_insn_1, &context);
780 /* Sometimes, we end up with a sequence of insns that
781 SSA needs to treat as a single insn. Wrap these in a
782 SEQUENCE. (Any notes now get attached to the SEQUENCE,
783 not to the old version inner insn.) */
784 if (get_insns () != NULL_RTX)
789 emit (PATTERN (insn));
790 seq = gen_sequence ();
791 /* We really want a SEQUENCE of SETs, not a SEQUENCE
793 for (i = 0; i < XVECLEN (seq, 0); i++)
794 XVECEXP (seq, 0, i) = PATTERN (XVECEXP (seq, 0, i));
795 PATTERN (insn) = seq;
799 apply_delayed_renames (&context);
800 set_data = context.done_renames;
803 next = NEXT_INSN (insn);
805 while (insn != last);
807 /* Step Two: Update the phi nodes of this block's successors. */
809 for (e = b->succ; e; e = e->succ_next)
811 if (e->dest == EXIT_BLOCK_PTR)
814 insn = e->dest->head;
815 if (GET_CODE (insn) == CODE_LABEL)
816 insn = NEXT_INSN (insn);
818 while (PHI_NODE_P (insn))
820 rtx phi = PATTERN (insn);
824 /* Find out which of our outgoing registers this node is
825 indended to replace. Note that if this not the first PHI
826 node to have been created for this register, we have to
827 jump through rename links to figure out which register
828 we're talking about. This can easily be recognized by
829 noting that the regno is new to this pass. */
830 regno = REGNO (SET_DEST (phi));
831 if (regno >= ssa_max_reg_num)
832 regno = REGNO (VARRAY_RTX (ssa_rename_from, regno));
833 reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER];
835 /* It is possible for the variable to be uninitialized on
836 edges in. Reduce the arity of the PHI so that we don't
837 consider those edges. */
838 if (reg == NULL || reg == RENAME_NO_RTX)
840 if (! remove_phi_alternative (phi, bb))
845 /* When we created the PHI nodes, we did not know what mode
846 the register should be. Now that we've found an original,
847 we can fill that in. */
848 if (GET_MODE (SET_DEST (phi)) == VOIDmode)
849 PUT_MODE (SET_DEST (phi), GET_MODE (reg));
850 else if (GET_MODE (SET_DEST (phi)) != GET_MODE (reg))
853 *phi_alternative (phi, bb) = reg;
854 /* ??? Mark for a new ssa_uses entry. */
857 insn = NEXT_INSN (insn);
861 /* Step Three: Do the same to the children of this block in
864 for (c = 0; c < n_basic_blocks; ++c)
866 rename_block (c, idom);
868 /* Step Four: Update the sets to refer to their new register,
869 and restore ssa_rename_to to its previous state. */
873 struct rename_set_data *next;
874 rtx old_reg = *set_data->reg_loc;
876 if (*set_data->reg_loc != set_data->old_reg)
878 *set_data->reg_loc = set_data->new_reg;
880 ssa_rename_to[REGNO (old_reg)-FIRST_PSEUDO_REGISTER]
881 = set_data->prev_reg;
883 next = set_data->next;
890 rename_registers (nregs, idom)
894 VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
895 VARRAY_RTX_INIT (ssa_uses, nregs * 3, "ssa_uses");
896 VARRAY_RTX_INIT (ssa_rename_from, nregs * 3, "ssa_rename_from");
898 ssa_rename_to = (rtx *) alloca (nregs * sizeof(rtx));
899 bzero ((char *) ssa_rename_to, nregs * sizeof(rtx));
901 rename_block (0, idom);
903 /* ??? Update basic_block_live_at_start, and other flow info
906 ssa_rename_to = NULL;
910 /* The main entry point for moving to SSA. */
915 /* Element I is the set of blocks that set register I. */
918 /* Dominator bitmaps. */
923 /* Element I is the immediate dominator of block I. */
928 /* Don't do it twice. */
932 /* Need global_live_at_{start,end} up to date. */
933 life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
935 /* Compute dominators. */
936 dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
937 compute_flow_dominators (dominators, NULL);
939 idom = (int *) alloca (n_basic_blocks * sizeof (int));
940 memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
941 simplify_to_immediate_dominators (idom, dominators);
943 sbitmap_vector_free (dominators);
948 fputs (";; Immediate Dominators:\n", rtl_dump_file);
949 for (i = 0; i < n_basic_blocks; ++i)
950 fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]);
951 fflush (rtl_dump_file);
954 /* Compute dominance frontiers. */
956 dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
957 compute_dominance_frontiers (dfs, idom);
961 dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
962 "; Basic Block", dfs, n_basic_blocks);
963 fflush (rtl_dump_file);
966 /* Compute register evaluations. */
968 ssa_max_reg_num = max_reg_num();
969 nregs = ssa_max_reg_num - FIRST_PSEUDO_REGISTER;
970 evals = sbitmap_vector_alloc (nregs, n_basic_blocks);
971 find_evaluations (evals, nregs);
973 /* Compute the iterated dominance frontier for each register. */
975 idfs = sbitmap_vector_alloc (nregs, n_basic_blocks);
976 compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);
980 dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
981 "; Register-FIRST_PSEUDO_REGISTER", idfs, nregs);
982 fflush (rtl_dump_file);
985 /* Insert the phi nodes. */
987 insert_phi_nodes (idfs, evals, nregs);
989 /* Rename the registers to satisfy SSA. */
991 rename_registers (nregs, idom);
993 /* All done! Clean up and go home. */
995 sbitmap_vector_free (dfs);
996 sbitmap_vector_free (evals);
997 sbitmap_vector_free (idfs);
1000 reg_scan (get_insns (), max_reg_num (), 1);
1004 /* REG is the representative temporary of its partition. Add it to the
1005 set of nodes to be processed, if it hasn't been already. Return the
1006 index of this register in the node set. */
1009 ephi_add_node (reg, nodes, n_nodes)
1014 for (i = *n_nodes - 1; i >= 0; --i)
1015 if (REGNO (reg) == REGNO (nodes[i]))
1018 nodes[i = (*n_nodes)++] = reg;
1022 /* Part one of the topological sort. This is a forward (downward) search
1023 through the graph collecting a stack of nodes to process. Assuming no
1024 cycles, the nodes at top of the stack when we are finished will have
1025 no other dependancies. */
1028 ephi_forward (t, visited, succ, tstack)
1036 SET_BIT (visited, t);
1038 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1040 if (! TEST_BIT (visited, s))
1041 tstack = ephi_forward (s, visited, succ, tstack);
1048 /* Part two of the topological sort. The is a backward search through
1049 a cycle in the graph, copying the data forward as we go. */
1052 ephi_backward (t, visited, pred, nodes)
1054 sbitmap visited, *pred;
1059 SET_BIT (visited, t);
1061 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1063 if (! TEST_BIT (visited, p))
1065 ephi_backward (p, visited, pred, nodes);
1066 emit_move_insn (nodes[p], nodes[t]);
1071 /* Part two of the topological sort. Create the copy for a register
1072 and any cycle of which it is a member. */
1075 ephi_create (t, visited, pred, succ, nodes)
1077 sbitmap visited, *pred, *succ;
1080 rtx reg_u = NULL_RTX;
1081 int unvisited_predecessors = 0;
1084 /* Iterate through the predecessor list looking for unvisited nodes.
1085 If there are any, we have a cycle, and must deal with that. At
1086 the same time, look for a visited predecessor. If there is one,
1087 we won't need to create a temporary. */
1089 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1091 if (! TEST_BIT (visited, p))
1092 unvisited_predecessors = 1;
1097 if (unvisited_predecessors)
1099 /* We found a cycle. Copy out one element of the ring (if necessary),
1100 then traverse the ring copying as we go. */
1104 reg_u = gen_reg_rtx (GET_MODE (nodes[t]));
1105 emit_move_insn (reg_u, nodes[t]);
1108 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1110 if (! TEST_BIT (visited, p))
1112 ephi_backward (p, visited, pred, nodes);
1113 emit_move_insn (nodes[p], reg_u);
1119 /* No cycle. Just copy the value from a successor. */
1122 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1124 SET_BIT (visited, t);
1125 emit_move_insn (nodes[t], nodes[s]);
1131 /* Convert the edge to normal form. */
1134 eliminate_phi (e, reg_partition)
1136 partition reg_partition;
1139 sbitmap *pred, *succ;
1142 int *stack, *tstack;
1146 /* Collect an upper bound on the number of registers needing processing. */
1148 insn = e->dest->head;
1149 if (GET_CODE (insn) == CODE_LABEL)
1150 insn = next_nonnote_insn (insn);
1153 while (PHI_NODE_P (insn))
1155 insn = next_nonnote_insn (insn);
1162 /* Build the auxilliary graph R(B).
1164 The nodes of the graph are the members of the register partition
1165 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1166 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1168 nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
1169 pred = sbitmap_vector_alloc (n_nodes, n_nodes);
1170 succ = sbitmap_vector_alloc (n_nodes, n_nodes);
1171 sbitmap_vector_zero (pred, n_nodes);
1172 sbitmap_vector_zero (succ, n_nodes);
1174 insn = e->dest->head;
1175 if (GET_CODE (insn) == CODE_LABEL)
1176 insn = next_nonnote_insn (insn);
1179 for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
1181 rtx* preg = phi_alternative (PATTERN (insn), e->src->index);
1182 rtx tgt = SET_DEST (PATTERN (insn));
1185 /* There may be no phi alternative corresponding to this edge.
1186 This indicates that the phi variable is undefined along this
1192 if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
1195 reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
1196 tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
1197 /* If the two registers are already in the same partition,
1198 nothing will need to be done. */
1203 ireg = ephi_add_node (reg, nodes, &n_nodes);
1204 itgt = ephi_add_node (tgt, nodes, &n_nodes);
1206 SET_BIT (pred[ireg], itgt);
1207 SET_BIT (succ[itgt], ireg);
1214 /* Begin a topological sort of the graph. */
1216 visited = sbitmap_alloc (n_nodes);
1217 sbitmap_zero (visited);
1219 tstack = stack = (int *) alloca (n_nodes * sizeof (int));
1221 for (i = 0; i < n_nodes; ++i)
1222 if (! TEST_BIT (visited, i))
1223 tstack = ephi_forward (i, visited, succ, tstack);
1225 sbitmap_zero (visited);
1227 /* As we find a solution to the tsort, collect the implementation
1228 insns in a sequence. */
1231 while (tstack != stack)
1234 if (! TEST_BIT (visited, i))
1235 ephi_create (i, visited, pred, succ, nodes);
1238 insn = gen_sequence ();
1240 insert_insn_on_edge (insn, e);
1242 fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n",
1243 e->src->index, e->dest->index);
1245 sbitmap_free (visited);
1247 sbitmap_vector_free (pred);
1248 sbitmap_vector_free (succ);
1252 /* For basic block B, consider all phi insns which provide an
1253 alternative corresponding to an incoming abnormal critical edge.
1254 Place the phi alternative corresponding to that abnormal critical
1255 edge in the same register class as the destination of the set.
1257 From Morgan, p. 178:
1259 For each abnormal critical edge (C, B),
1260 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1261 and C is the ith predecessor of B,
1262 then T0 and Ti must be equivalent.
1264 Return non-zero iff any such cases were found for which the two
1265 regs were not already in the same class. */
1268 make_regs_equivalent_over_bad_edges (bb, reg_partition)
1270 partition reg_partition;
1273 basic_block b = BASIC_BLOCK (bb);
1276 /* Advance to the first phi node. */
1277 if (GET_CODE (phi) == CODE_LABEL)
1278 phi = next_nonnote_insn (phi);
1280 /* Scan all the phi nodes. */
1283 phi = next_nonnote_insn (phi))
1287 rtx set = PATTERN (phi);
1288 rtx tgt = SET_DEST (set);
1290 /* The set target is expected to be a pseudo. */
1291 if (GET_CODE (tgt) != REG
1292 || REGNO (tgt) < FIRST_PSEUDO_REGISTER)
1294 tgt_regno = REGNO (tgt);
1296 /* Scan incoming abnormal critical edges. */
1297 for (e = b->pred; e; e = e->pred_next)
1298 if ((e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL))
1299 == (EDGE_ABNORMAL | EDGE_CRITICAL))
1301 rtx *alt = phi_alternative (set, e->src->index);
1304 /* If there is no alternative corresponding to this edge,
1305 the value is undefined along the edge, so just go on. */
1309 /* The phi alternative is expected to be a pseudo. */
1310 if (GET_CODE (*alt) != REG
1311 || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
1313 alt_regno = REGNO (*alt);
1315 /* If the set destination and the phi alternative aren't
1316 already in the same class... */
1317 if (partition_find (reg_partition, tgt_regno)
1318 != partition_find (reg_partition, alt_regno))
1320 /* ... make them such. */
1321 partition_union (reg_partition,
1322 tgt_regno, alt_regno);
1332 /* Consider phi insns in basic block BB pairwise. If the set target
1333 of both isns are equivalent pseudos, make the corresponding phi
1334 alternatives in each phi corresponding equivalent.
1336 Return nonzero if any new register classes were unioned. */
1339 make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
1341 partition reg_partition;
1344 rtx phi = BLOCK_HEAD (bb);
1345 basic_block b = BASIC_BLOCK (bb);
1347 /* Advance to the first phi node. */
1348 if (GET_CODE (phi) == CODE_LABEL)
1349 phi = next_nonnote_insn (phi);
1351 /* Scan all the phi nodes. */
1354 phi = next_nonnote_insn (phi))
1356 rtx set = PATTERN (phi);
1357 /* The regno of the destination of the set. */
1358 int tgt_regno = REGNO (SET_DEST (PATTERN (phi)));
1360 rtx phi2 = next_nonnote_insn (phi);
1362 /* Scan all phi nodes following this one. */
1365 phi2 = next_nonnote_insn (phi2))
1367 rtx set2 = PATTERN (phi2);
1368 /* The regno of the destination of the set. */
1369 int tgt2_regno = REGNO (SET_DEST (set2));
1371 /* Are the set destinations equivalent regs? */
1372 if (partition_find (reg_partition, tgt_regno) ==
1373 partition_find (reg_partition, tgt2_regno))
1376 /* Scan over edges. */
1377 for (e = b->pred; e; e = e->pred_next)
1379 int pred_block = e->src->index;
1380 /* Identify the phi altnernatives from both phi
1381 nodes corresponding to this edge. */
1382 rtx *alt = phi_alternative (set, pred_block);
1383 rtx *alt2 = phi_alternative (set2, pred_block);
1385 /* If one of the phi nodes doesn't have a
1386 corresponding alternative, just skip it. */
1387 if (alt == 0 || alt2 == 0)
1390 /* Both alternatives should be pseudos. */
1391 if (GET_CODE (*alt) != REG
1392 || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
1394 if (GET_CODE (*alt2) != REG
1395 || REGNO (*alt2) < FIRST_PSEUDO_REGISTER)
1398 /* If the altneratives aren't already in the same
1400 if (partition_find (reg_partition, REGNO (*alt))
1401 != partition_find (reg_partition, REGNO (*alt2)))
1403 /* ... make them so. */
1404 partition_union (reg_partition,
1405 REGNO (*alt), REGNO (*alt2));
1416 /* Compute a conservative partition of outstanding pseudo registers.
1417 See Morgan 7.3.1. */
1420 compute_conservative_reg_partition ()
1425 /* We don't actually work with hard registers, but it's easier to
1426 carry them around anyway rather than constantly doing register
1427 number arithmetic. */
1429 partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);
1431 /* The first priority is to make sure registers that might have to
1432 be copied on abnormal critical edges are placed in the same
1433 partition. This saves us from having to split abnormal critical
1435 for (bb = n_basic_blocks; --bb >= 0; )
1436 changed += make_regs_equivalent_over_bad_edges (bb, p);
1438 /* Now we have to insure that corresponding arguments of phi nodes
1439 assigning to corresponding regs are equivalent. Iterate until
1444 for (bb = n_basic_blocks; --bb >= 0; )
1445 changed += make_equivalent_phi_alternatives_equivalent (bb, p);
1451 /* The following functions compute a register partition that attempts
1452 to eliminate as many reg copies and phi node copies as possible by
1453 coalescing registers. This is the strategy:
1455 1. As in the conservative case, the top priority is to coalesce
1456 registers that otherwise would cause copies to be placed on
1457 abnormal critical edges (which isn't possible).
1459 2. Figure out which regs are involved (in the LHS or RHS) of
1460 copies and phi nodes. Compute conflicts among these regs.
1462 3. Walk around the instruction stream, placing two regs in the
1463 same class of the partition if one appears on the LHS and the
1464 other on the RHS of a copy or phi node and the two regs don't
1465 conflict. The conflict information of course needs to be
1468 4. If anything has changed, there may be new opportunities to
1469 coalesce regs, so go back to 2.
1472 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1473 same class of partition P, if they aren't already. Update
1474 CONFLICTS appropriately.
1476 Returns one if REG1 and REG2 were placed in the same class but were
1477 not previously; zero otherwise.
1479 See Morgan figure 11.15. */
1482 coalesce_if_unconflicting (p, conflicts, reg1, reg2)
1484 conflict_graph conflicts;
1490 /* Don't mess with hard regs. */
1491 if (reg1 < FIRST_PSEUDO_REGISTER || reg2 < FIRST_PSEUDO_REGISTER)
1494 /* Find the canonical regs for the classes containing REG1 and
1496 reg1 = partition_find (p, reg1);
1497 reg2 = partition_find (p, reg2);
1499 /* If they're already in the same class, there's nothing to do. */
1503 /* If the regs conflict, our hands are tied. */
1504 if (conflict_graph_conflict_p (conflicts, reg1, reg2))
1507 /* We're good to go. Put the regs in the same partition. */
1508 partition_union (p, reg1, reg2);
1510 /* Find the new canonical reg for the merged class. */
1511 reg = partition_find (p, reg1);
1513 /* Merge conflicts from the two previous classes. */
1514 conflict_graph_merge_regs (conflicts, reg, reg1);
1515 conflict_graph_merge_regs (conflicts, reg, reg2);
1520 /* For each register copy insn in basic block BB, place the LHS and
1521 RHS regs in the same class in partition P if they do not conflict
1522 according to CONFLICTS.
1524 Returns the number of changes that were made to P.
1526 See Morgan figure 11.14. */
1529 coalesce_regs_in_copies (bb, p, conflicts)
1532 conflict_graph conflicts;
1538 /* Scan the instruction stream of the block. */
1539 for (insn = bb->head; insn != end; insn = NEXT_INSN (insn))
1545 /* If this isn't a set insn, go to the next insn. */
1546 if (GET_CODE (insn) != INSN)
1548 pattern = PATTERN (insn);
1549 if (GET_CODE (pattern) != SET)
1552 src = SET_SRC (pattern);
1553 dest = SET_DEST (pattern);
1555 /* We're only looking for copies. */
1556 if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
1559 /* Coalesce only if the reg modes are the same. As long as
1560 each reg's rtx is unique, it can have only one mode, so two
1561 pseudos of different modes can't be coalesced into one.
1563 FIXME: We can probably get around this by inserting SUBREGs
1564 where appropriate, but for now we don't bother. */
1565 if (GET_MODE (src) != GET_MODE (dest))
1568 /* Found a copy; see if we can use the same reg for both the
1569 source and destination (and thus eliminate the copy,
1571 changed += coalesce_if_unconflicting (p, conflicts,
1572 REGNO (src), REGNO (dest));
1579 struct phi_coalesce_context
1582 conflict_graph conflicts;
1586 /* Callback function for for_each_successor_phi. If the set
1587 destination and the phi alternative regs do not conflict, place
1588 them in the same paritition class. DATA is a pointer to a
1589 phi_coalesce_context struct. */
1592 coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
1593 rtx insn ATTRIBUTE_UNUSED;
1598 struct phi_coalesce_context *context =
1599 (struct phi_coalesce_context *) data;
1601 /* Attempt to use the same reg, if they don't conflict. */
1603 += coalesce_if_unconflicting (context->p, context->conflicts,
1604 dest_regno, src_regno);
1608 /* For each alternative in a phi function corresponding to basic block
1609 BB (in phi nodes in successor block to BB), place the reg in the
1610 phi alternative and the reg to which the phi value is set into the
1611 same class in partition P, if allowed by CONFLICTS.
1613 Return the number of changes that were made to P.
1615 See Morgan figure 11.14. */
1618 coalesce_regs_in_successor_phi_nodes (bb, p, conflicts)
1621 conflict_graph conflicts;
1623 struct phi_coalesce_context context;
1625 context.conflicts = conflicts;
1626 context.changed = 0;
1628 for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);
1630 return context.changed;
1633 /* Compute and return a partition of pseudos. Where possible,
1634 non-conflicting pseudos are placed in the same class.
1636 The caller is responsible for deallocating the returned partition. */
1639 compute_coalesced_reg_partition ()
1644 /* We don't actually work with hard registers, but it's easier to
1645 carry them around anyway rather than constantly doing register
1646 number arithmetic. */
1648 partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);
1650 /* The first priority is to make sure registers that might have to
1651 be copied on abnormal critical edges are placed in the same
1652 partition. This saves us from having to split abnormal critical
1653 edges (which can't be done). */
1654 for (bb = n_basic_blocks; --bb >= 0; )
1655 make_regs_equivalent_over_bad_edges (bb, p);
1659 regset_head phi_set;
1660 conflict_graph conflicts;
1664 /* Build the set of registers involved in phi nodes, either as
1665 arguments to the phi function or as the target of a set. */
1666 INITIALIZE_REG_SET (phi_set);
1667 mark_phi_and_copy_regs (&phi_set);
1669 /* Compute conflicts. */
1670 conflicts = conflict_graph_compute (&phi_set, p);
1672 /* FIXME: Better would be to process most frequently executed
1673 blocks first, so that most frequently executed copies would
1674 be more likely to be removed by register coalescing. But any
1675 order will generate correct, if non-optimal, results. */
1676 for (bb = n_basic_blocks; --bb >= 0; )
1678 basic_block block = BASIC_BLOCK (bb);
1679 changed += coalesce_regs_in_copies (block, p, conflicts);
1681 coalesce_regs_in_successor_phi_nodes (block, p, conflicts);
1684 conflict_graph_delete (conflicts);
1686 while (changed > 0);
1691 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1692 components (a REG or a CONST_INT). DATA is a reg set in which to
1693 set all regs. Called from for_each_rtx. */
1696 mark_reg_in_phi (ptr, data)
1701 regset set = (regset) data;
1703 switch (GET_CODE (expr))
1706 SET_REGNO_REG_SET (set, REGNO (expr));
1716 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1717 set from a phi expression, or used as an argument in one. Also
1718 mark regs that are the source or target of a reg copy. Uses
1722 mark_phi_and_copy_regs (phi_set)
1727 /* Scan the definitions of all regs. */
1728 for (reg = VARRAY_SIZE (ssa_definition);
1729 --reg >= FIRST_PSEUDO_REGISTER;
1732 rtx insn = VARRAY_RTX (ssa_definition, reg);
1738 pattern = PATTERN (insn);
1739 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1741 if (GET_CODE (pattern) != SET)
1743 src = SET_SRC (pattern);
1745 if (GET_CODE (src) == REG)
1747 /* It's a reg copy. */
1748 SET_REGNO_REG_SET (phi_set, reg);
1749 SET_REGNO_REG_SET (phi_set, REGNO (src));
1751 else if (GET_CODE (src) == PHI)
1753 /* It's a phi node. Mark the reg being set. */
1754 SET_REGNO_REG_SET (phi_set, reg);
1755 /* Mark the regs used in the phi function. */
1756 for_each_rtx (&src, mark_reg_in_phi, phi_set);
1758 /* ... else nothing to do. */
1762 /* Rename regs in insn PTR that are equivalent. DATA is the register
1763 partition which specifies equivalences. */
1766 rename_equivalent_regs_in_insn (ptr, data)
1771 partition reg_partition = (partition) data;
1776 switch (GET_CODE (x))
1779 if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
1781 int regno = REGNO (x);
1782 int new_regno = partition_find (reg_partition, regno);
1783 if (regno != new_regno)
1785 rtx new_reg = regno_reg_rtx[new_regno];
1786 if (GET_MODE (x) != GET_MODE (new_reg))
1794 /* No need to rename the phi nodes. We'll check equivalence
1795 when inserting copies. */
1799 /* Anything else, continue traversing. */
1804 /* Rename regs that are equivalent in REG_PARTITION.
1805 Also collapse any SEQUENCE insns. */
1808 rename_equivalent_regs (reg_partition)
1809 partition reg_partition;
1813 for (bb = n_basic_blocks; --bb >= 0; )
1815 basic_block b = BASIC_BLOCK (bb);
1823 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1825 for_each_rtx (&PATTERN (insn),
1826 rename_equivalent_regs_in_insn,
1828 for_each_rtx (®_NOTES (insn),
1829 rename_equivalent_regs_in_insn,
1832 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
1834 rtx s = PATTERN (insn);
1835 int slen = XVECLEN (s, 0);
1841 PATTERN (insn) = XVECEXP (s, 0, slen-1);
1842 for (i = 0; i < slen - 1; i++)
1843 emit_block_insn_before (XVECEXP (s, 0, i), insn, b);
1847 next = NEXT_INSN (insn);
1849 while (insn != last);
1853 /* The main entry point for moving from SSA. */
1859 partition reg_partition;
1860 rtx insns = get_insns ();
1862 /* Need global_live_at_{start,end} up to date. */
1863 life_analysis (insns, NULL,
1864 PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE | PROP_DEATH_NOTES);
1866 /* Figure out which regs in copies and phi nodes don't conflict and
1867 therefore can be coalesced. */
1868 if (conservative_reg_partition)
1869 reg_partition = compute_conservative_reg_partition ();
1871 reg_partition = compute_coalesced_reg_partition ();
1873 rename_equivalent_regs (reg_partition);
1875 /* Eliminate the PHI nodes. */
1876 for (bb = n_basic_blocks; --bb >= 0; )
1878 basic_block b = BASIC_BLOCK (bb);
1881 for (e = b->pred; e; e = e->pred_next)
1882 if (e->src != ENTRY_BLOCK_PTR)
1883 eliminate_phi (e, reg_partition);
1886 partition_delete (reg_partition);
1888 /* Actually delete the PHI nodes. */
1889 for (bb = n_basic_blocks; --bb >= 0; )
1891 rtx insn = BLOCK_HEAD (bb);
1892 int start = (GET_CODE (insn) != CODE_LABEL);
1895 insn = next_nonnote_insn (insn);
1896 while (PHI_NODE_P (insn))
1898 /* If a phi node is the last insn in the block, there must
1899 have been nothing else. Set the block end to the block
1901 if (insn == BLOCK_END (bb))
1902 BLOCK_END (bb) = BLOCK_HEAD (bb);
1903 insn = delete_insn (insn);
1904 if (GET_CODE (insn) == NOTE)
1905 insn = next_nonnote_insn (insn);
1908 BLOCK_HEAD (bb) = insn;
1911 /* Commit all the copy nodes needed to convert out of SSA form. */
1912 commit_edge_insertions ();
1916 count_or_remove_death_notes (NULL, 1);
1919 /* Scan phi nodes in successors to BB. For each such phi node that
1920 has a phi alternative value corresponding to BB, invoke FN. FN
1921 is passed the entire phi node insn, the regno of the set
1922 destination, the regno of the phi argument corresponding to BB,
1925 If FN ever returns non-zero, stops immediately and returns this
1926 value. Otherwise, returns zero. */
1929 for_each_successor_phi (bb, fn, data)
1931 successor_phi_fn fn;
1936 if (bb == EXIT_BLOCK_PTR)
1939 /* Scan outgoing edges. */
1940 for (e = bb->succ; e != NULL; e = e->succ_next)
1944 basic_block successor = e->dest;
1945 if (successor == ENTRY_BLOCK_PTR
1946 || successor == EXIT_BLOCK_PTR)
1949 /* Advance to the first non-label insn of the successor block. */
1950 insn = successor->head;
1952 && (GET_CODE (insn) == CODE_LABEL
1953 || GET_CODE (insn) == NOTE))
1954 insn = NEXT_INSN (insn);
1959 /* Scan phi nodes in the successor. */
1960 for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
1963 rtx phi_set = PATTERN (insn);
1964 rtx *alternative = phi_alternative (phi_set, bb->index);
1967 /* This phi function may not have an alternative
1968 corresponding to the incoming edge, indicating the
1969 assigned variable is not defined along the edge. */
1970 if (alternative == NULL)
1972 phi_src = *alternative;
1974 /* Invoke the callback. */
1975 result = (*fn) (insn, REGNO (SET_DEST (phi_set)),
1976 REGNO (phi_src), data);
1978 /* Terminate if requested. */