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 static inline rtx * phi_alternative
99 static int remove_phi_alternative
101 static void simplify_to_immediate_dominators
102 PARAMS ((int *idom, sbitmap *dominators));
103 static void compute_dominance_frontiers_1
104 PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
105 static void compute_dominance_frontiers
106 PARAMS ((sbitmap *frontiers, int *idom));
107 static void find_evaluations_1
108 PARAMS ((rtx dest, rtx set, void *data));
109 static void find_evaluations
110 PARAMS ((sbitmap *evals, int nregs));
111 static void compute_iterated_dominance_frontiers
112 PARAMS ((sbitmap *idfs, sbitmap *frontiers, sbitmap *evals, int nregs));
113 static void insert_phi_node
114 PARAMS ((int regno, int b));
115 static void insert_phi_nodes
116 PARAMS ((sbitmap *idfs, sbitmap *evals, int nregs));
117 static int rename_insn_1
118 PARAMS ((rtx *ptr, void *data));
119 static void rename_block
120 PARAMS ((int b, int *idom));
121 static void rename_registers
122 PARAMS ((int nregs, int *idom));
124 static inline int ephi_add_node
125 PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
126 static int * ephi_forward
127 PARAMS ((int t, sbitmap visited, sbitmap *succ, int *tstack));
128 static void ephi_backward
129 PARAMS ((int t, sbitmap visited, sbitmap *pred, rtx *nodes));
130 static void ephi_create
131 PARAMS ((int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes));
132 static void eliminate_phi
133 PARAMS ((edge e, partition reg_partition));
134 static int make_regs_equivalent_over_bad_edges
135 PARAMS ((int bb, partition reg_partition));
137 /* These are used only in the conservative register partitioning
139 static int make_equivalent_phi_alternatives_equivalent
140 PARAMS ((int bb, partition reg_partition));
141 static partition compute_conservative_reg_partition
143 static int rename_equivalent_regs_in_insn
144 PARAMS ((rtx *ptr, void *data));
146 /* These are used in the register coalescing algorithm. */
147 static int coalesce_if_unconflicting
148 PARAMS ((partition p, conflict_graph conflicts, int reg1, int reg2));
149 static int coalesce_regs_in_copies
150 PARAMS ((int bb, partition p, conflict_graph conflicts));
151 static int coalesce_reg_in_phi
152 PARAMS ((rtx, int dest_regno, int src_regno, void *data));
153 static int coalesce_regs_in_successor_phi_nodes
154 PARAMS ((int bb, partition p, conflict_graph conflicts));
155 static partition compute_coalesced_reg_partition
157 static int mark_reg_in_phi
158 PARAMS ((rtx *ptr, void *data));
159 static void mark_phi_and_copy_regs
160 PARAMS ((regset phi_set));
162 static int rename_equivalent_regs_in_insn
163 PARAMS ((rtx *ptr, void *data));
164 static void rename_equivalent_regs
165 PARAMS ((partition reg_partition));
168 /* Given the SET of a PHI node, return the address of the alternative
169 for predecessor block C. */
172 phi_alternative (set, c)
176 rtvec phi_vec = XVEC (SET_SRC (set), 0);
179 for (v = GET_NUM_ELEM (phi_vec) - 2; v >= 0; v -= 2)
180 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
181 return &RTVEC_ELT (phi_vec, v);
186 /* Given the SET of a phi node, remove the alternative for predecessor
187 block C. Return non-zero on success, or zero if no alternative is
191 remove_phi_alternative (set, c)
195 rtvec phi_vec = XVEC (SET_SRC (set), 0);
196 int num_elem = GET_NUM_ELEM (phi_vec);
199 for (v = num_elem - 2; v >= 0; v -= 2)
200 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
202 if (v < num_elem - 2)
204 RTVEC_ELT (phi_vec, v) = RTVEC_ELT (phi_vec, num_elem - 2);
205 RTVEC_ELT (phi_vec, v + 1) = RTVEC_ELT (phi_vec, num_elem - 1);
207 PUT_NUM_ELEM (phi_vec, num_elem - 2);
214 /* Computing the Immediate Dominators:
216 Throughout, we don't actually want the full dominators set as
217 calculated by flow, but rather the immediate dominators.
221 simplify_to_immediate_dominators (idom, dominators)
228 tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
230 /* Begin with tmp(n) = dom(n) - { n }. */
231 for (b = n_basic_blocks; --b >= 0; )
233 sbitmap_copy (tmp[b], dominators[b]);
234 RESET_BIT (tmp[b], b);
237 /* Subtract out all of our dominator's dominators. */
238 for (b = n_basic_blocks; --b >= 0; )
240 sbitmap tmp_b = tmp[b];
243 for (s = n_basic_blocks; --s >= 0; )
244 if (TEST_BIT (tmp_b, s))
245 sbitmap_difference (tmp_b, tmp_b, tmp[s]);
248 /* Find the one bit set in the bitmap and put it in the output array. */
249 for (b = n_basic_blocks; --b >= 0; )
252 EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; });
255 sbitmap_vector_free (tmp);
259 /* For all registers, find all blocks in which they are set.
261 This is the transform of what would be local kill information that
262 we ought to be getting from flow. */
264 static sbitmap *fe_evals;
265 static int fe_current_bb;
268 find_evaluations_1 (dest, set, data)
270 rtx set ATTRIBUTE_UNUSED;
271 void *data ATTRIBUTE_UNUSED;
273 if (GET_CODE (dest) == REG
274 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
275 SET_BIT (fe_evals[REGNO (dest) - FIRST_PSEUDO_REGISTER], fe_current_bb);
279 find_evaluations (evals, nregs)
285 sbitmap_vector_zero (evals, nregs);
288 for (bb = n_basic_blocks; --bb >= 0; )
294 last = BLOCK_END (bb);
297 if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
298 note_stores (PATTERN (p), find_evaluations_1, NULL);
308 /* Computing the Dominance Frontier:
310 As decribed in Morgan, section 3.5, this may be done simply by
311 walking the dominator tree bottom-up, computing the frontier for
312 the children before the parent. When considering a block B,
315 (1) A flow graph edge leaving B that does not lead to a child
316 of B in the dominator tree must be a block that is either equal
317 to B or not dominated by B. Such blocks belong in the frontier
320 (2) Consider a block X in the frontier of one of the children C
321 of B. If X is not equal to B and is not dominated by B, it
322 is in the frontier of B.
326 compute_dominance_frontiers_1 (frontiers, idom, bb, done)
332 basic_block b = BASIC_BLOCK (bb);
337 sbitmap_zero (frontiers[bb]);
339 /* Do the frontier of the children first. Not all children in the
340 dominator tree (blocks dominated by this one) are children in the
341 CFG, so check all blocks. */
342 for (c = 0; c < n_basic_blocks; ++c)
343 if (idom[c] == bb && ! TEST_BIT (done, c))
344 compute_dominance_frontiers_1 (frontiers, idom, c, done);
346 /* Find blocks conforming to rule (1) above. */
347 for (e = b->succ; e; e = e->succ_next)
349 if (e->dest == EXIT_BLOCK_PTR)
351 if (idom[e->dest->index] != bb)
352 SET_BIT (frontiers[bb], e->dest->index);
355 /* Find blocks conforming to rule (2). */
356 for (c = 0; c < n_basic_blocks; ++c)
360 EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x,
363 SET_BIT (frontiers[bb], x);
369 compute_dominance_frontiers (frontiers, idom)
373 sbitmap done = sbitmap_alloc (n_basic_blocks);
376 compute_dominance_frontiers_1 (frontiers, idom, 0, done);
382 /* Computing the Iterated Dominance Frontier:
384 This is the set of merge points for a given register.
386 This is not particularly intuitive. See section 7.1 of Morgan, in
387 particular figures 7.3 and 7.4 and the immediately surrounding text.
391 compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs)
400 worklist = sbitmap_alloc (n_basic_blocks);
402 for (reg = 0; reg < nregs; ++reg)
404 sbitmap idf = idfs[reg];
407 /* Start the iterative process by considering those blocks that
408 evaluate REG. We'll add their dominance frontiers to the
409 IDF, and then consider the blocks we just added. */
410 sbitmap_copy (worklist, evals[reg]);
412 /* Morgan's algorithm is incorrect here. Blocks that evaluate
413 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
416 /* Iterate until the worklist is empty. */
421 EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b,
423 RESET_BIT (worklist, b);
424 /* For each block on the worklist, add to the IDF all
425 blocks on its dominance frontier that aren't already
426 on the IDF. Every block that's added is also added
428 sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf);
429 sbitmap_a_or_b (idf, idf, frontiers[b]);
436 sbitmap_free (worklist);
440 fprintf(rtl_dump_file,
441 "Iterated dominance frontier: %d passes on %d regs.\n",
447 /* Insert the phi nodes. */
450 insert_phi_node (regno, bb)
453 basic_block b = BASIC_BLOCK (bb);
459 /* Find out how many predecessors there are. */
460 for (e = b->pred, npred = 0; e; e = e->pred_next)
461 if (e->src != ENTRY_BLOCK_PTR)
464 /* If this block has no "interesting" preds, then there is nothing to
465 do. Consider a block that only has the entry block as a pred. */
469 /* This is the register to which the phi function will be assinged. */
470 reg = regno_reg_rtx[regno + FIRST_PSEUDO_REGISTER];
472 /* Construct the arguments to the PHI node. The use of pc_rtx is just
473 a placeholder; we'll insert the proper value in rename_registers. */
474 vec = rtvec_alloc (npred * 2);
475 for (e = b->pred, i = 0; e ; e = e->pred_next, i += 2)
476 if (e->src != ENTRY_BLOCK_PTR)
478 RTVEC_ELT (vec, i + 0) = pc_rtx;
479 RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index);
482 phi = gen_rtx_PHI (VOIDmode, vec);
483 phi = gen_rtx_SET (VOIDmode, reg, phi);
485 if (GET_CODE (b->head) == CODE_LABEL)
486 emit_insn_after (phi, b->head);
488 b->head = emit_insn_before (phi, b->head);
493 insert_phi_nodes (idfs, evals, nregs)
495 sbitmap *evals ATTRIBUTE_UNUSED;
500 for (reg = 0; reg < nregs; ++reg)
503 EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b,
505 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start,
506 reg + FIRST_PSEUDO_REGISTER))
507 insert_phi_node (reg, b);
512 /* Rename the registers to conform to SSA.
514 This is essentially the algorithm presented in Figure 7.8 of Morgan,
515 with a few changes to reduce pattern search time in favour of a bit
516 more memory usage. */
519 /* One of these is created for each set. It will live in a list local
520 to its basic block for the duration of that block's processing. */
521 struct rename_set_data
523 struct rename_set_data *next;
531 /* This struct is used to pass information to callback functions while
532 renaming registers. */
533 struct rename_context
535 struct rename_set_data *set_data;
539 static void new_registers_for_updates
540 PARAMS ((struct rename_set_data *set_data,
541 struct rename_set_data *old_set_data, rtx insn));
543 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
544 reused. If, during processing, a register has not yet been touched,
545 ssa_rename_to[regno] will be NULL. Now, in the course of pushing
546 and popping values from ssa_rename_to, when we would ordinarily
547 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
548 same as NULL, except that it signals that the original regno has
549 already been reused. */
550 #define RENAME_NO_RTX pc_rtx
552 /* Part one of the first step of rename_block, called through for_each_rtx.
553 Mark pseudos that are set for later update. Transform uses of pseudos. */
556 rename_insn_1 (ptr, data)
561 struct rename_context *context = data;
562 struct rename_set_data **set_datap = &(context->set_data);
567 switch (GET_CODE (x))
571 rtx *destp = &SET_DEST (x);
572 rtx dest = SET_DEST (x);
574 /* Subregs at word 0 are interesting. Subregs at word != 0 are
575 presumed to be part of a contiguous multi-word set sequence. */
576 while (GET_CODE (dest) == SUBREG
577 && SUBREG_WORD (dest) == 0)
579 destp = &SUBREG_REG (dest);
580 dest = SUBREG_REG (dest);
583 if (GET_CODE (dest) == REG
584 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
586 /* We found a genuine set of an interesting register. Tag
587 it so that we can create a new name for it after we finish
588 processing this insn. */
590 struct rename_set_data *r;
591 r = (struct rename_set_data *) xmalloc (sizeof(*r));
594 r->set_dest = SET_DEST (x);
595 r->set_insn = context->current_insn;
596 r->next = *set_datap;
599 /* Since we do not wish to (directly) traverse the
600 SET_DEST, recurse through for_each_rtx for the SET_SRC
602 for_each_rtx (&SET_SRC (x), rename_insn_1, data);
606 /* Otherwise, this was not an interesting destination. Continue
607 on, marking uses as normal. */
612 if (REGNO (x) >= FIRST_PSEUDO_REGISTER
613 && REGNO (x) < ssa_max_reg_num)
615 rtx new_reg = ssa_rename_to[REGNO(x) - FIRST_PSEUDO_REGISTER];
617 if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
619 if (GET_MODE (x) != GET_MODE (new_reg))
623 /* Else this is a use before a set. Warn? */
628 /* Never muck with the phi. We do that elsewhere, special-like. */
632 /* Anything else, continue traversing. */
637 /* Second part of the first step of rename_block. The portion of the list
638 beginning at SET_DATA through OLD_SET_DATA contain the sets present in
639 INSN. Update data structures accordingly. */
642 new_registers_for_updates (set_data, old_set_data, insn)
643 struct rename_set_data *set_data, *old_set_data;
646 while (set_data != old_set_data)
648 int regno, new_regno;
649 rtx old_reg, new_reg, prev_reg;
651 old_reg = *set_data->reg_loc;
652 regno = REGNO (*set_data->reg_loc);
654 /* For the first set we come across, reuse the original regno. */
655 if (ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] == NULL_RTX)
658 prev_reg = RENAME_NO_RTX;
662 prev_reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER];
663 new_reg = gen_reg_rtx (GET_MODE (old_reg));
666 set_data->new_reg = new_reg;
667 set_data->prev_reg = prev_reg;
668 new_regno = REGNO (new_reg);
669 ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] = new_reg;
671 if (new_regno >= (int) ssa_definition->num_elements)
673 int new_limit = new_regno * 5 / 4;
674 ssa_definition = VARRAY_GROW (ssa_definition, new_limit);
675 ssa_uses = VARRAY_GROW (ssa_uses, new_limit);
676 ssa_rename_from = VARRAY_GROW (ssa_rename_from, new_limit);
679 VARRAY_RTX (ssa_definition, new_regno) = insn;
680 VARRAY_RTX (ssa_rename_from, new_regno) = old_reg;
682 set_data = set_data->next;
687 rename_block (bb, idom)
691 basic_block b = BASIC_BLOCK (bb);
693 rtx insn, next, last;
694 struct rename_set_data *set_data = NULL;
697 /* Step One: Walk the basic block, adding new names for sets and
705 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
707 struct rename_context context;
708 context.set_data = set_data;
709 context.current_insn = insn;
711 for_each_rtx (&PATTERN (insn), rename_insn_1, &context);
712 for_each_rtx (®_NOTES (insn), rename_insn_1, &context);
714 new_registers_for_updates (context.set_data, set_data, insn);
715 set_data = context.set_data;
718 next = NEXT_INSN (insn);
720 while (insn != last);
722 /* Step Two: Update the phi nodes of this block's successors. */
724 for (e = b->succ; e; e = e->succ_next)
726 if (e->dest == EXIT_BLOCK_PTR)
729 insn = e->dest->head;
730 if (GET_CODE (insn) == CODE_LABEL)
731 insn = NEXT_INSN (insn);
733 while (PHI_NODE_P (insn))
735 rtx phi = PATTERN (insn);
739 /* Find out which of our outgoing registers this node is
740 indended to replace. Note that if this not the first PHI
741 node to have been created for this register, we have to
742 jump through rename links to figure out which register
743 we're talking about. This can easily be recognized by
744 noting that the regno is new to this pass. */
745 regno = REGNO (SET_DEST (phi));
746 if (regno >= ssa_max_reg_num)
747 regno = REGNO (VARRAY_RTX (ssa_rename_from, regno));
748 reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER];
750 /* It is possible for the variable to be uninitialized on
751 edges in. Reduce the arity of the PHI so that we don't
752 consider those edges. */
753 if (reg == NULL || reg == RENAME_NO_RTX)
755 if (! remove_phi_alternative (phi, bb))
760 /* When we created the PHI nodes, we did not know what mode
761 the register should be. Now that we've found an original,
762 we can fill that in. */
763 if (GET_MODE (SET_DEST (phi)) == VOIDmode)
764 PUT_MODE (SET_DEST (phi), GET_MODE (reg));
765 else if (GET_MODE (SET_DEST (phi)) != GET_MODE (reg))
768 *phi_alternative (phi, bb) = reg;
769 /* ??? Mark for a new ssa_uses entry. */
772 insn = NEXT_INSN (insn);
776 /* Step Three: Do the same to the children of this block in
779 for (c = 0; c < n_basic_blocks; ++c)
781 rename_block (c, idom);
783 /* Step Four: Update the sets to refer to their new register. */
787 struct rename_set_data *next;
788 rtx old_reg = *set_data->reg_loc;
790 /* If the set is of a subreg only, copy the entire reg first so
791 that unmodified bits are preserved. Of course, we don't
792 strictly have SSA any more, but that's the best we can do
793 without a lot of hard work. */
795 if (GET_CODE (set_data->set_dest) == SUBREG)
797 if (old_reg != set_data->new_reg)
799 rtx copy = gen_rtx_SET (GET_MODE (old_reg),
800 set_data->new_reg, old_reg);
801 emit_insn_before (copy, set_data->set_insn);
805 *set_data->reg_loc = set_data->new_reg;
806 ssa_rename_to[REGNO (old_reg)-FIRST_PSEUDO_REGISTER]
807 = set_data->prev_reg;
809 next = set_data->next;
816 rename_registers (nregs, idom)
820 VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
821 VARRAY_RTX_INIT (ssa_uses, nregs * 3, "ssa_uses");
822 VARRAY_RTX_INIT (ssa_rename_from, nregs * 3, "ssa_rename_from");
824 ssa_rename_to = (rtx *) alloca (nregs * sizeof(rtx));
825 bzero ((char *) ssa_rename_to, nregs * sizeof(rtx));
827 rename_block (0, idom);
829 /* ??? Update basic_block_live_at_start, and other flow info
832 ssa_rename_to = NULL;
836 /* The main entry point for moving to SSA. */
841 /* Element I is the set of blocks that set register I. */
844 /* Dominator bitmaps. */
849 /* Element I is the immediate dominator of block I. */
854 /* Don't do it twice. */
858 /* Don't eliminate dead code here. The CFG we computed above must
859 remain unchanged until we are finished emerging from SSA form --
860 the phi node representation depends on it. */
861 life_analysis (get_insns (), max_reg_num (), NULL, 0);
863 /* Compute dominators. */
864 dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
865 compute_flow_dominators (dominators, NULL);
867 idom = (int *) alloca (n_basic_blocks * sizeof (int));
868 memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
869 simplify_to_immediate_dominators (idom, dominators);
871 sbitmap_vector_free (dominators);
876 fputs (";; Immediate Dominators:\n", rtl_dump_file);
877 for (i = 0; i < n_basic_blocks; ++i)
878 fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]);
879 fflush (rtl_dump_file);
882 /* Compute dominance frontiers. */
884 dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
885 compute_dominance_frontiers (dfs, idom);
889 dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
890 "; Basic Block", dfs, n_basic_blocks);
891 fflush (rtl_dump_file);
894 /* Compute register evaluations. */
896 ssa_max_reg_num = max_reg_num();
897 nregs = ssa_max_reg_num - FIRST_PSEUDO_REGISTER;
898 evals = sbitmap_vector_alloc (nregs, n_basic_blocks);
899 find_evaluations (evals, nregs);
901 /* Compute the iterated dominance frontier for each register. */
903 idfs = sbitmap_vector_alloc (nregs, n_basic_blocks);
904 compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);
908 dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
909 "; Register-FIRST_PSEUDO_REGISTER", idfs, nregs);
910 fflush (rtl_dump_file);
913 /* Insert the phi nodes. */
915 insert_phi_nodes (idfs, evals, nregs);
917 /* Rename the registers to satisfy SSA. */
919 rename_registers (nregs, idom);
921 /* All done! Clean up and go home. */
923 sbitmap_vector_free (dfs);
924 sbitmap_vector_free (evals);
925 sbitmap_vector_free (idfs);
928 reg_scan (get_insns (), max_reg_num (), 1);
932 /* REG is the representative temporary of its partition. Add it to the
933 set of nodes to be processed, if it hasn't been already. Return the
934 index of this register in the node set. */
937 ephi_add_node (reg, nodes, n_nodes)
942 for (i = *n_nodes - 1; i >= 0; --i)
943 if (REGNO (reg) == REGNO (nodes[i]))
946 nodes[i = (*n_nodes)++] = reg;
950 /* Part one of the topological sort. This is a forward (downward) search
951 through the graph collecting a stack of nodes to process. Assuming no
952 cycles, the nodes at top of the stack when we are finished will have
953 no other dependancies. */
956 ephi_forward (t, visited, succ, tstack)
964 SET_BIT (visited, t);
966 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
968 if (! TEST_BIT (visited, s))
969 tstack = ephi_forward (s, visited, succ, tstack);
976 /* Part two of the topological sort. The is a backward search through
977 a cycle in the graph, copying the data forward as we go. */
980 ephi_backward (t, visited, pred, nodes)
982 sbitmap visited, *pred;
987 SET_BIT (visited, t);
989 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
991 if (! TEST_BIT (visited, p))
993 ephi_backward (p, visited, pred, nodes);
994 emit_move_insn (nodes[p], nodes[t]);
999 /* Part two of the topological sort. Create the copy for a register
1000 and any cycle of which it is a member. */
1003 ephi_create (t, visited, pred, succ, nodes)
1005 sbitmap visited, *pred, *succ;
1008 rtx reg_u = NULL_RTX;
1009 int unvisited_predecessors = 0;
1012 /* Iterate through the predecessor list looking for unvisited nodes.
1013 If there are any, we have a cycle, and must deal with that. At
1014 the same time, look for a visited predecessor. If there is one,
1015 we won't need to create a temporary. */
1017 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1019 if (! TEST_BIT (visited, p))
1020 unvisited_predecessors = 1;
1025 if (unvisited_predecessors)
1027 /* We found a cycle. Copy out one element of the ring (if necessary),
1028 then traverse the ring copying as we go. */
1032 reg_u = gen_reg_rtx (GET_MODE (nodes[t]));
1033 emit_move_insn (reg_u, nodes[t]);
1036 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1038 if (! TEST_BIT (visited, p))
1040 ephi_backward (p, visited, pred, nodes);
1041 emit_move_insn (nodes[p], reg_u);
1047 /* No cycle. Just copy the value from a successor. */
1050 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1052 SET_BIT (visited, t);
1053 emit_move_insn (nodes[t], nodes[s]);
1059 /* Convert the edge to normal form. */
1062 eliminate_phi (e, reg_partition)
1064 partition reg_partition;
1067 sbitmap *pred, *succ;
1070 int *stack, *tstack;
1074 /* Collect an upper bound on the number of registers needing processing. */
1076 insn = e->dest->head;
1077 if (GET_CODE (insn) == CODE_LABEL)
1078 insn = next_nonnote_insn (insn);
1081 while (PHI_NODE_P (insn))
1083 insn = next_nonnote_insn (insn);
1090 /* Build the auxilliary graph R(B).
1092 The nodes of the graph are the members of the register partition
1093 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1094 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1096 nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
1097 pred = sbitmap_vector_alloc (n_nodes, n_nodes);
1098 succ = sbitmap_vector_alloc (n_nodes, n_nodes);
1099 sbitmap_vector_zero (pred, n_nodes);
1100 sbitmap_vector_zero (succ, n_nodes);
1102 insn = e->dest->head;
1103 if (GET_CODE (insn) == CODE_LABEL)
1104 insn = next_nonnote_insn (insn);
1107 for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
1109 rtx* preg = phi_alternative (PATTERN (insn), e->src->index);
1110 rtx tgt = SET_DEST (PATTERN (insn));
1113 /* There may be no phi alternative corresponding to this edge.
1114 This indicates that the phi variable is undefined along this
1120 if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
1123 reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
1124 tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
1125 /* If the two registers are already in the same partition,
1126 nothing will need to be done. */
1131 ireg = ephi_add_node (reg, nodes, &n_nodes);
1132 itgt = ephi_add_node (tgt, nodes, &n_nodes);
1134 SET_BIT (pred[ireg], itgt);
1135 SET_BIT (succ[itgt], ireg);
1142 /* Begin a topological sort of the graph. */
1144 visited = sbitmap_alloc (n_nodes);
1145 sbitmap_zero (visited);
1147 tstack = stack = (int *) alloca (n_nodes * sizeof (int));
1149 for (i = 0; i < n_nodes; ++i)
1150 if (! TEST_BIT (visited, i))
1151 tstack = ephi_forward (i, visited, succ, tstack);
1153 sbitmap_zero (visited);
1155 /* As we find a solution to the tsort, collect the implementation
1156 insns in a sequence. */
1159 while (tstack != stack)
1162 if (! TEST_BIT (visited, i))
1163 ephi_create (i, visited, pred, succ, nodes);
1166 insn = gen_sequence ();
1168 insert_insn_on_edge (insn, e);
1170 fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n",
1171 e->src->index, e->dest->index);
1173 sbitmap_free (visited);
1175 sbitmap_vector_free (pred);
1176 sbitmap_vector_free (succ);
1180 /* For basic block B, consider all phi insns which provide an
1181 alternative corresponding to an incoming abnormal critical edge.
1182 Place the phi alternative corresponding to that abnormal critical
1183 edge in the same register class as the destination of the set.
1185 From Morgan, p. 178:
1187 For each abnormal critical edge (C, B),
1188 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1189 and C is the ith predecessor of B,
1190 then T0 and Ti must be equivalent.
1192 Return non-zero iff any such cases were found for which the two
1193 regs were not already in the same class. */
1196 make_regs_equivalent_over_bad_edges (bb, reg_partition)
1198 partition reg_partition;
1201 basic_block b = BASIC_BLOCK (bb);
1204 /* Advance to the first phi node. */
1205 if (GET_CODE (phi) == CODE_LABEL)
1206 phi = next_nonnote_insn (phi);
1208 /* Scan all the phi nodes. */
1211 phi = next_nonnote_insn (phi))
1215 rtx set = PATTERN (phi);
1216 rtx tgt = SET_DEST (set);
1218 /* The set target is expected to be a pseudo. */
1219 if (GET_CODE (tgt) != REG
1220 || REGNO (tgt) < FIRST_PSEUDO_REGISTER)
1222 tgt_regno = REGNO (tgt);
1224 /* Scan incoming abnormal critical edges. */
1225 for (e = b->pred; e; e = e->pred_next)
1226 if (e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL))
1228 rtx *alt = phi_alternative (set, e->src->index);
1231 /* If there is no alternative corresponding to this edge,
1232 the value is undefined along the edge, so just go on. */
1236 /* The phi alternative is expected to be a pseudo. */
1237 if (GET_CODE (*alt) != REG
1238 || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
1240 alt_regno = REGNO (*alt);
1242 /* If the set destination and the phi alternative aren't
1243 already in the same class... */
1244 if (partition_find (reg_partition, tgt_regno)
1245 != partition_find (reg_partition, alt_regno))
1247 /* ... make them such. */
1248 partition_union (reg_partition,
1249 tgt_regno, alt_regno);
1259 /* Consider phi insns in basic block BB pairwise. If the set target
1260 of both isns are equivalent pseudos, make the corresponding phi
1261 alternatives in each phi corresponding equivalent.
1263 Return nonzero if any new register classes were unioned. */
1266 make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
1268 partition reg_partition;
1271 rtx phi = BLOCK_HEAD (bb);
1272 basic_block b = BASIC_BLOCK (bb);
1274 /* Advance to the first phi node. */
1275 if (GET_CODE (phi) == CODE_LABEL)
1276 phi = next_nonnote_insn (phi);
1278 /* Scan all the phi nodes. */
1281 phi = next_nonnote_insn (phi))
1283 rtx set = PATTERN (phi);
1284 /* The regno of the destination of the set. */
1285 int tgt_regno = REGNO (SET_DEST (PATTERN (phi)));
1287 rtx phi2 = next_nonnote_insn (phi);
1289 /* Scan all phi nodes following this one. */
1292 phi2 = next_nonnote_insn (phi2))
1294 rtx set2 = PATTERN (phi2);
1295 /* The regno of the destination of the set. */
1296 int tgt2_regno = REGNO (SET_DEST (set2));
1298 /* Are the set destinations equivalent regs? */
1299 if (partition_find (reg_partition, tgt_regno) ==
1300 partition_find (reg_partition, tgt2_regno))
1303 /* Scan over edges. */
1304 for (e = b->pred; e; e = e->pred_next)
1306 int pred_block = e->src->index;
1307 /* Identify the phi altnernatives from both phi
1308 nodes corresponding to this edge. */
1309 rtx *alt = phi_alternative (set, pred_block);
1310 rtx *alt2 = phi_alternative (set2, pred_block);
1312 /* If one of the phi nodes doesn't have a
1313 corresponding alternative, just skip it. */
1314 if (alt == 0 || alt2 == 0)
1317 /* Both alternatives should be pseudos. */
1318 if (GET_CODE (*alt) != REG
1319 || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
1321 if (GET_CODE (*alt2) != REG
1322 || REGNO (*alt2) < FIRST_PSEUDO_REGISTER)
1325 /* If the altneratives aren't already in the same
1327 if (partition_find (reg_partition, REGNO (*alt))
1328 != partition_find (reg_partition, REGNO (*alt2)))
1330 /* ... make them so. */
1331 partition_union (reg_partition,
1332 REGNO (*alt), REGNO (*alt2));
1343 /* Compute a conservative partition of outstanding pseudo registers.
1344 See Morgan 7.3.1. */
1347 compute_conservative_reg_partition ()
1352 /* We don't actually work with hard registers, but it's easier to
1353 carry them around anyway rather than constantly doing register
1354 number arithmetic. */
1356 partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);
1358 /* The first priority is to make sure registers that might have to
1359 be copied on abnormal critical edges are placed in the same
1360 partition. This saves us from having to split abnormal critical
1362 for (bb = n_basic_blocks; --bb >= 0; )
1363 changed += make_regs_equivalent_over_bad_edges (bb, p);
1365 /* Now we have to insure that corresponding arguments of phi nodes
1366 assigning to corresponding regs are equivalent. Iterate until
1371 for (bb = n_basic_blocks; --bb >= 0; )
1372 changed += make_equivalent_phi_alternatives_equivalent (bb, p);
1378 /* The following functions compute a register partition that attempts
1379 to eliminate as many reg copies and phi node copies as possible by
1380 coalescing registers. This is the strategy:
1382 1. As in the conservative case, the top priority is to coalesce
1383 registers that otherwise would cause copies to be placed on
1384 abnormal critical edges (which isn't possible).
1386 2. Figure out which regs are involved (in the LHS or RHS) of
1387 copies and phi nodes. Compute conflicts among these regs.
1389 3. Walk around the instruction stream, placing two regs in the
1390 same class of the partition if one appears on the LHS and the
1391 other on the RHS of a copy or phi node and the two regs don't
1392 conflict. The conflict information of course needs to be
1395 4. If anything has changed, there may be new opportunities to
1396 coalesce regs, so go back to 2.
1399 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1400 same class of partition P, if they aren't already. Update
1401 CONFLICTS appropriately.
1403 Returns one if REG1 and REG2 were placed in the same class but were
1404 not previously; zero otherwise.
1406 See Morgan figure 11.15. */
1409 coalesce_if_unconflicting (p, conflicts, reg1, reg2)
1411 conflict_graph conflicts;
1417 /* Don't mess with hard regs. */
1418 if (reg1 < FIRST_PSEUDO_REGISTER || reg2 < FIRST_PSEUDO_REGISTER)
1421 /* Find the canonical regs for the classes containing REG1 and
1423 reg1 = partition_find (p, reg1);
1424 reg2 = partition_find (p, reg2);
1426 /* If they're already in the same class, there's nothing to do. */
1430 /* If the regs conflict, our hands are tied. */
1431 if (conflict_graph_conflict_p (conflicts, reg1, reg2))
1434 /* We're good to go. Put the regs in the same partition. */
1435 partition_union (p, reg1, reg2);
1437 /* Find the new canonical reg for the merged class. */
1438 reg = partition_find (p, reg1);
1440 /* Merge conflicts from the two previous classes. */
1441 conflict_graph_merge_regs (conflicts, reg, reg1);
1442 conflict_graph_merge_regs (conflicts, reg, reg2);
1447 /* For each register copy insn in basic block BB, place the LHS and
1448 RHS regs in the same class in partition P if they do not conflict
1449 according to CONFLICTS.
1451 Returns the number of changes that were made to P.
1453 See Morgan figure 11.14. */
1456 coalesce_regs_in_copies (bb, p, conflicts)
1459 conflict_graph conflicts;
1463 rtx end = BLOCK_END (bb);
1465 /* Scan the instruction stream of the block. */
1466 for (insn = BLOCK_HEAD (bb); insn != end; insn = NEXT_INSN (insn))
1472 /* If this isn't a set insn, go to the next insn. */
1473 if (GET_CODE (insn) != INSN)
1475 pattern = PATTERN (insn);
1476 if (GET_CODE (pattern) != SET)
1479 src = SET_SRC (pattern);
1480 dest = SET_DEST (pattern);
1482 /* If src or dest are subregs, find the underlying reg. */
1483 while (GET_CODE (src) == SUBREG
1484 && SUBREG_WORD (src) != 0)
1485 src = SUBREG_REG (src);
1486 while (GET_CODE (dest) == SUBREG
1487 && SUBREG_WORD (dest) != 0)
1488 dest = SUBREG_REG (dest);
1490 /* We're only looking for copies. */
1491 if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
1494 /* Coalesce only if the reg modes are the same. As long as
1495 each reg's rtx is unique, it can have only one mode, so two
1496 pseudos of different modes can't be coalesced into one.
1498 FIXME: We can probably get around this by inserting SUBREGs
1499 where appropriate, but for now we don't bother. */
1500 if (GET_MODE (src) != GET_MODE (dest))
1503 /* Found a copy; see if we can use the same reg for both the
1504 source and destination (and thus eliminate the copy,
1506 changed += coalesce_if_unconflicting (p, conflicts,
1507 REGNO (src), REGNO (dest));
1514 struct phi_coalesce_context
1517 conflict_graph conflicts;
1521 /* Callback function for for_each_successor_phi. If the set
1522 destination and the phi alternative regs do not conflict, place
1523 them in the same paritition class. DATA is a pointer to a
1524 phi_coalesce_context struct. */
1527 coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
1528 rtx insn ATTRIBUTE_UNUSED;
1533 struct phi_coalesce_context *context =
1534 (struct phi_coalesce_context *) data;
1536 /* Attempt to use the same reg, if they don't conflict. */
1538 += coalesce_if_unconflicting (context->p, context->conflicts,
1539 dest_regno, src_regno);
1543 /* For each alternative in a phi function corresponding to basic block
1544 BB (in phi nodes in successor block to BB), place the reg in the
1545 phi alternative and the reg to which the phi value is set into the
1546 same class in partition P, if allowed by CONFLICTS.
1548 Return the number of changes that were made to P.
1550 See Morgan figure 11.14. */
1553 coalesce_regs_in_successor_phi_nodes (bb, p, conflicts)
1556 conflict_graph conflicts;
1558 struct phi_coalesce_context context;
1560 context.conflicts = conflicts;
1561 context.changed = 0;
1563 for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);
1565 return context.changed;
1568 /* Compute and return a partition of pseudos. Where possible,
1569 non-conflicting pseudos are placed in the same class.
1571 The caller is responsible for deallocating the returned partition. */
1574 compute_coalesced_reg_partition ()
1579 /* We don't actually work with hard registers, but it's easier to
1580 carry them around anyway rather than constantly doing register
1581 number arithmetic. */
1583 partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);
1585 /* The first priority is to make sure registers that might have to
1586 be copied on abnormal critical edges are placed in the same
1587 partition. This saves us from having to split abnormal critical
1588 edges (which can't be done). */
1589 for (bb = n_basic_blocks; --bb >= 0; )
1590 make_regs_equivalent_over_bad_edges (bb, p);
1594 regset_head phi_set;
1595 conflict_graph conflicts;
1599 /* Build the set of registers involved in phi nodes, either as
1600 arguments to the phi function or as the target of a set. */
1601 INITIALIZE_REG_SET (phi_set);
1602 mark_phi_and_copy_regs (&phi_set);
1604 /* Compute conflicts. */
1605 conflicts = conflict_graph_compute (&phi_set, p);
1607 /* FIXME: Better would be to process most frequently executed
1608 blocks first, so that most frequently executed copies would
1609 be more likely to be removed by register coalescing. But any
1610 order will generate correct, if non-optimal, results. */
1611 for (bb = n_basic_blocks; --bb >= 0; )
1613 changed += coalesce_regs_in_copies (bb, p, conflicts);
1614 changed += coalesce_regs_in_successor_phi_nodes (bb, p, conflicts);
1617 conflict_graph_delete (conflicts);
1619 while (changed > 0);
1624 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1625 components (a REG or a CONST_INT). DATA is a reg set in which to
1626 set all regs. Called from for_each_rtx. */
1629 mark_reg_in_phi (ptr, data)
1634 regset set = (regset) data;
1636 switch (GET_CODE (expr))
1639 SET_REGNO_REG_SET (set, REGNO (expr));
1649 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1650 set from a phi expression, or used as an argument in one. Also
1651 mark regs that are the source or target of a reg copy. Uses
1655 mark_phi_and_copy_regs (phi_set)
1660 /* Scan the definitions of all regs. */
1661 for (reg = VARRAY_SIZE (ssa_definition);
1662 --reg >= FIRST_PSEUDO_REGISTER;
1665 rtx insn = VARRAY_RTX (ssa_definition, reg);
1671 pattern = PATTERN (insn);
1672 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1674 if (GET_CODE (pattern) != SET)
1676 src = SET_SRC (pattern);
1678 if (GET_CODE (src) == REG)
1680 /* It's a reg copy. */
1681 SET_REGNO_REG_SET (phi_set, reg);
1682 SET_REGNO_REG_SET (phi_set, REGNO (src));
1684 else if (GET_CODE (src) == PHI)
1686 /* It's a phi node. Mark the reg being set. */
1687 SET_REGNO_REG_SET (phi_set, reg);
1688 /* Mark the regs used in the phi function. */
1689 for_each_rtx (&src, mark_reg_in_phi, phi_set);
1691 /* ... else nothing to do. */
1695 /* Rename regs in insn PTR that are equivalent. DATA is the register
1696 partition which specifies equivalences. */
1699 rename_equivalent_regs_in_insn (ptr, data)
1704 partition reg_partition = (partition) data;
1709 switch (GET_CODE (x))
1713 rtx *destp = &SET_DEST (x);
1714 rtx dest = SET_DEST (x);
1716 /* Subregs at word 0 are interesting. Subregs at word != 0 are
1717 presumed to be part of a contiguous multi-word set sequence. */
1718 while (GET_CODE (dest) == SUBREG
1719 && SUBREG_WORD (dest) == 0)
1721 destp = &SUBREG_REG (dest);
1722 dest = SUBREG_REG (dest);
1725 if (GET_CODE (dest) == REG
1726 && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
1728 /* Got a pseudo; replace it. */
1729 int regno = REGNO (dest);
1730 int new_regno = partition_find (reg_partition, regno);
1731 if (regno != new_regno)
1732 *destp = regno_reg_rtx[new_regno];
1734 for_each_rtx (&SET_SRC (x),
1735 rename_equivalent_regs_in_insn,
1740 /* Otherwise, this was not an interesting destination. Continue
1741 on, marking uses as normal. */
1746 if (REGNO (x) >= FIRST_PSEUDO_REGISTER)
1748 int regno = REGNO (x);
1749 int new_regno = partition_find (reg_partition, regno);
1750 if (regno != new_regno)
1752 rtx new_reg = regno_reg_rtx[new_regno];
1753 if (GET_MODE (x) != GET_MODE (new_reg))
1761 /* No need to rename the phi nodes. We'll check equivalence
1762 when inserting copies. */
1766 /* Anything else, continue traversing. */
1771 /* Rename regs that are equivalent in REG_PARTITION. */
1774 rename_equivalent_regs (reg_partition)
1775 partition reg_partition;
1779 for (bb = n_basic_blocks; --bb >= 0; )
1781 basic_block b = BASIC_BLOCK (bb);
1789 if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1791 for_each_rtx (&PATTERN (insn),
1792 rename_equivalent_regs_in_insn,
1794 for_each_rtx (®_NOTES (insn),
1795 rename_equivalent_regs_in_insn,
1799 next = NEXT_INSN (insn);
1801 while (insn != last);
1805 /* The main entry point for moving from SSA. */
1811 partition reg_partition;
1812 rtx insns = get_insns ();
1814 /* We need up-to-date life information. */
1815 life_analysis (insns, max_reg_num (), NULL, 0);
1817 /* Figure out which regs in copies and phi nodes don't conflict and
1818 therefore can be coalesced. */
1819 if (conservative_reg_partition)
1820 reg_partition = compute_conservative_reg_partition ();
1822 reg_partition = compute_coalesced_reg_partition ();
1824 rename_equivalent_regs (reg_partition);
1826 /* Eliminate the PHI nodes. */
1827 for (bb = n_basic_blocks; --bb >= 0; )
1829 basic_block b = BASIC_BLOCK (bb);
1832 for (e = b->pred; e; e = e->pred_next)
1833 if (e->src != ENTRY_BLOCK_PTR)
1834 eliminate_phi (e, reg_partition);
1837 partition_delete (reg_partition);
1839 /* Actually delete the PHI nodes. */
1840 for (bb = n_basic_blocks; --bb >= 0; )
1842 rtx insn = BLOCK_HEAD (bb);
1843 int start = (GET_CODE (insn) != CODE_LABEL);
1846 insn = next_nonnote_insn (insn);
1847 while (PHI_NODE_P (insn))
1849 /* If a phi node is the last insn in the block, there must
1850 have been nothing else. Set the block end to the block
1852 if (insn == BLOCK_END (bb))
1853 BLOCK_END (bb) = BLOCK_HEAD (bb);
1854 insn = delete_insn (insn);
1855 if (GET_CODE (insn) == NOTE)
1856 insn = next_nonnote_insn (insn);
1859 BLOCK_HEAD (bb) = insn;
1862 /* Commit all the copy nodes needed to convert out of SSA form. */
1863 commit_edge_insertions ();
1867 count_or_remove_death_notes (NULL, 1);
1870 /* Scan phi nodes in successors to BB. For each such phi node that
1871 has a phi alternative value corresponding to BB, invoke FN. FN
1872 is passed the entire phi node insn, the regno of the set
1873 destination, the regno of the phi argument corresponding to BB,
1876 If FN ever returns non-zero, stops immediately and returns this
1877 value. Otherwise, returns zero. */
1880 for_each_successor_phi (bb, fn, data)
1882 successor_phi_fn fn;
1888 if (bb == EXIT_BLOCK)
1890 else if (bb == ENTRY_BLOCK)
1891 block = ENTRY_BLOCK_PTR;
1893 block = BASIC_BLOCK (bb);
1895 /* Scan outgoing edges. */
1896 for (e = block->succ; e != NULL; e = e->succ_next)
1900 basic_block successor = e->dest;
1901 if (successor->index == ENTRY_BLOCK
1902 || successor->index == EXIT_BLOCK)
1905 /* Advance to the first non-label insn of the successor block. */
1906 insn = successor->head;
1908 && (GET_CODE (insn) == CODE_LABEL
1909 || GET_CODE (insn) == NOTE))
1910 insn = NEXT_INSN (insn);
1915 /* Scan phi nodes in the successor. */
1916 for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
1919 rtx phi_set = PATTERN (insn);
1920 rtx *alternative = phi_alternative (phi_set, block->index);
1923 /* This phi function may not have an alternative
1924 corresponding to the incoming edge, indicating the
1925 assigned variable is not defined along the edge. */
1926 if (alternative == NULL)
1928 phi_src = *alternative;
1930 /* Invoke the callback. */
1931 result = (*fn) (insn, REGNO (SET_DEST (phi_set)),
1932 REGNO (phi_src), data);
1934 /* Terminate if requested. */