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 ((basic_block 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 ((basic_block 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 /* Need global_live_at_{start,end} up to date. */
859 life_analysis (get_insns (), NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
861 /* Compute dominators. */
862 dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
863 compute_flow_dominators (dominators, NULL);
865 idom = (int *) alloca (n_basic_blocks * sizeof (int));
866 memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int));
867 simplify_to_immediate_dominators (idom, dominators);
869 sbitmap_vector_free (dominators);
874 fputs (";; Immediate Dominators:\n", rtl_dump_file);
875 for (i = 0; i < n_basic_blocks; ++i)
876 fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]);
877 fflush (rtl_dump_file);
880 /* Compute dominance frontiers. */
882 dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
883 compute_dominance_frontiers (dfs, idom);
887 dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
888 "; Basic Block", dfs, n_basic_blocks);
889 fflush (rtl_dump_file);
892 /* Compute register evaluations. */
894 ssa_max_reg_num = max_reg_num();
895 nregs = ssa_max_reg_num - FIRST_PSEUDO_REGISTER;
896 evals = sbitmap_vector_alloc (nregs, n_basic_blocks);
897 find_evaluations (evals, nregs);
899 /* Compute the iterated dominance frontier for each register. */
901 idfs = sbitmap_vector_alloc (nregs, n_basic_blocks);
902 compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);
906 dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
907 "; Register-FIRST_PSEUDO_REGISTER", idfs, nregs);
908 fflush (rtl_dump_file);
911 /* Insert the phi nodes. */
913 insert_phi_nodes (idfs, evals, nregs);
915 /* Rename the registers to satisfy SSA. */
917 rename_registers (nregs, idom);
919 /* All done! Clean up and go home. */
921 sbitmap_vector_free (dfs);
922 sbitmap_vector_free (evals);
923 sbitmap_vector_free (idfs);
926 reg_scan (get_insns (), max_reg_num (), 1);
930 /* REG is the representative temporary of its partition. Add it to the
931 set of nodes to be processed, if it hasn't been already. Return the
932 index of this register in the node set. */
935 ephi_add_node (reg, nodes, n_nodes)
940 for (i = *n_nodes - 1; i >= 0; --i)
941 if (REGNO (reg) == REGNO (nodes[i]))
944 nodes[i = (*n_nodes)++] = reg;
948 /* Part one of the topological sort. This is a forward (downward) search
949 through the graph collecting a stack of nodes to process. Assuming no
950 cycles, the nodes at top of the stack when we are finished will have
951 no other dependancies. */
954 ephi_forward (t, visited, succ, tstack)
962 SET_BIT (visited, t);
964 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
966 if (! TEST_BIT (visited, s))
967 tstack = ephi_forward (s, visited, succ, tstack);
974 /* Part two of the topological sort. The is a backward search through
975 a cycle in the graph, copying the data forward as we go. */
978 ephi_backward (t, visited, pred, nodes)
980 sbitmap visited, *pred;
985 SET_BIT (visited, t);
987 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
989 if (! TEST_BIT (visited, p))
991 ephi_backward (p, visited, pred, nodes);
992 emit_move_insn (nodes[p], nodes[t]);
997 /* Part two of the topological sort. Create the copy for a register
998 and any cycle of which it is a member. */
1001 ephi_create (t, visited, pred, succ, nodes)
1003 sbitmap visited, *pred, *succ;
1006 rtx reg_u = NULL_RTX;
1007 int unvisited_predecessors = 0;
1010 /* Iterate through the predecessor list looking for unvisited nodes.
1011 If there are any, we have a cycle, and must deal with that. At
1012 the same time, look for a visited predecessor. If there is one,
1013 we won't need to create a temporary. */
1015 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1017 if (! TEST_BIT (visited, p))
1018 unvisited_predecessors = 1;
1023 if (unvisited_predecessors)
1025 /* We found a cycle. Copy out one element of the ring (if necessary),
1026 then traverse the ring copying as we go. */
1030 reg_u = gen_reg_rtx (GET_MODE (nodes[t]));
1031 emit_move_insn (reg_u, nodes[t]);
1034 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1036 if (! TEST_BIT (visited, p))
1038 ephi_backward (p, visited, pred, nodes);
1039 emit_move_insn (nodes[p], reg_u);
1045 /* No cycle. Just copy the value from a successor. */
1048 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1050 SET_BIT (visited, t);
1051 emit_move_insn (nodes[t], nodes[s]);
1057 /* Convert the edge to normal form. */
1060 eliminate_phi (e, reg_partition)
1062 partition reg_partition;
1065 sbitmap *pred, *succ;
1068 int *stack, *tstack;
1072 /* Collect an upper bound on the number of registers needing processing. */
1074 insn = e->dest->head;
1075 if (GET_CODE (insn) == CODE_LABEL)
1076 insn = next_nonnote_insn (insn);
1079 while (PHI_NODE_P (insn))
1081 insn = next_nonnote_insn (insn);
1088 /* Build the auxilliary graph R(B).
1090 The nodes of the graph are the members of the register partition
1091 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1092 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1094 nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
1095 pred = sbitmap_vector_alloc (n_nodes, n_nodes);
1096 succ = sbitmap_vector_alloc (n_nodes, n_nodes);
1097 sbitmap_vector_zero (pred, n_nodes);
1098 sbitmap_vector_zero (succ, n_nodes);
1100 insn = e->dest->head;
1101 if (GET_CODE (insn) == CODE_LABEL)
1102 insn = next_nonnote_insn (insn);
1105 for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
1107 rtx* preg = phi_alternative (PATTERN (insn), e->src->index);
1108 rtx tgt = SET_DEST (PATTERN (insn));
1111 /* There may be no phi alternative corresponding to this edge.
1112 This indicates that the phi variable is undefined along this
1118 if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
1121 reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
1122 tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
1123 /* If the two registers are already in the same partition,
1124 nothing will need to be done. */
1129 ireg = ephi_add_node (reg, nodes, &n_nodes);
1130 itgt = ephi_add_node (tgt, nodes, &n_nodes);
1132 SET_BIT (pred[ireg], itgt);
1133 SET_BIT (succ[itgt], ireg);
1140 /* Begin a topological sort of the graph. */
1142 visited = sbitmap_alloc (n_nodes);
1143 sbitmap_zero (visited);
1145 tstack = stack = (int *) alloca (n_nodes * sizeof (int));
1147 for (i = 0; i < n_nodes; ++i)
1148 if (! TEST_BIT (visited, i))
1149 tstack = ephi_forward (i, visited, succ, tstack);
1151 sbitmap_zero (visited);
1153 /* As we find a solution to the tsort, collect the implementation
1154 insns in a sequence. */
1157 while (tstack != stack)
1160 if (! TEST_BIT (visited, i))
1161 ephi_create (i, visited, pred, succ, nodes);
1164 insn = gen_sequence ();
1166 insert_insn_on_edge (insn, e);
1168 fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n",
1169 e->src->index, e->dest->index);
1171 sbitmap_free (visited);
1173 sbitmap_vector_free (pred);
1174 sbitmap_vector_free (succ);
1178 /* For basic block B, consider all phi insns which provide an
1179 alternative corresponding to an incoming abnormal critical edge.
1180 Place the phi alternative corresponding to that abnormal critical
1181 edge in the same register class as the destination of the set.
1183 From Morgan, p. 178:
1185 For each abnormal critical edge (C, B),
1186 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1187 and C is the ith predecessor of B,
1188 then T0 and Ti must be equivalent.
1190 Return non-zero iff any such cases were found for which the two
1191 regs were not already in the same class. */
1194 make_regs_equivalent_over_bad_edges (bb, reg_partition)
1196 partition reg_partition;
1199 basic_block b = BASIC_BLOCK (bb);
1202 /* Advance to the first phi node. */
1203 if (GET_CODE (phi) == CODE_LABEL)
1204 phi = next_nonnote_insn (phi);
1206 /* Scan all the phi nodes. */
1209 phi = next_nonnote_insn (phi))
1213 rtx set = PATTERN (phi);
1214 rtx tgt = SET_DEST (set);
1216 /* The set target is expected to be a pseudo. */
1217 if (GET_CODE (tgt) != REG
1218 || REGNO (tgt) < FIRST_PSEUDO_REGISTER)
1220 tgt_regno = REGNO (tgt);
1222 /* Scan incoming abnormal critical edges. */
1223 for (e = b->pred; e; e = e->pred_next)
1224 if (e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL))
1226 rtx *alt = phi_alternative (set, e->src->index);
1229 /* If there is no alternative corresponding to this edge,
1230 the value is undefined along the edge, so just go on. */
1234 /* The phi alternative is expected to be a pseudo. */
1235 if (GET_CODE (*alt) != REG
1236 || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
1238 alt_regno = REGNO (*alt);
1240 /* If the set destination and the phi alternative aren't
1241 already in the same class... */
1242 if (partition_find (reg_partition, tgt_regno)
1243 != partition_find (reg_partition, alt_regno))
1245 /* ... make them such. */
1246 partition_union (reg_partition,
1247 tgt_regno, alt_regno);
1257 /* Consider phi insns in basic block BB pairwise. If the set target
1258 of both isns are equivalent pseudos, make the corresponding phi
1259 alternatives in each phi corresponding equivalent.
1261 Return nonzero if any new register classes were unioned. */
1264 make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
1266 partition reg_partition;
1269 rtx phi = BLOCK_HEAD (bb);
1270 basic_block b = BASIC_BLOCK (bb);
1272 /* Advance to the first phi node. */
1273 if (GET_CODE (phi) == CODE_LABEL)
1274 phi = next_nonnote_insn (phi);
1276 /* Scan all the phi nodes. */
1279 phi = next_nonnote_insn (phi))
1281 rtx set = PATTERN (phi);
1282 /* The regno of the destination of the set. */
1283 int tgt_regno = REGNO (SET_DEST (PATTERN (phi)));
1285 rtx phi2 = next_nonnote_insn (phi);
1287 /* Scan all phi nodes following this one. */
1290 phi2 = next_nonnote_insn (phi2))
1292 rtx set2 = PATTERN (phi2);
1293 /* The regno of the destination of the set. */
1294 int tgt2_regno = REGNO (SET_DEST (set2));
1296 /* Are the set destinations equivalent regs? */
1297 if (partition_find (reg_partition, tgt_regno) ==
1298 partition_find (reg_partition, tgt2_regno))
1301 /* Scan over edges. */
1302 for (e = b->pred; e; e = e->pred_next)
1304 int pred_block = e->src->index;
1305 /* Identify the phi altnernatives from both phi
1306 nodes corresponding to this edge. */
1307 rtx *alt = phi_alternative (set, pred_block);
1308 rtx *alt2 = phi_alternative (set2, pred_block);
1310 /* If one of the phi nodes doesn't have a
1311 corresponding alternative, just skip it. */
1312 if (alt == 0 || alt2 == 0)
1315 /* Both alternatives should be pseudos. */
1316 if (GET_CODE (*alt) != REG
1317 || REGNO (*alt) < FIRST_PSEUDO_REGISTER)
1319 if (GET_CODE (*alt2) != REG
1320 || REGNO (*alt2) < FIRST_PSEUDO_REGISTER)
1323 /* If the altneratives aren't already in the same
1325 if (partition_find (reg_partition, REGNO (*alt))
1326 != partition_find (reg_partition, REGNO (*alt2)))
1328 /* ... make them so. */
1329 partition_union (reg_partition,
1330 REGNO (*alt), REGNO (*alt2));
1341 /* Compute a conservative partition of outstanding pseudo registers.
1342 See Morgan 7.3.1. */
1345 compute_conservative_reg_partition ()
1350 /* We don't actually work with hard registers, but it's easier to
1351 carry them around anyway rather than constantly doing register
1352 number arithmetic. */
1354 partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);
1356 /* The first priority is to make sure registers that might have to
1357 be copied on abnormal critical edges are placed in the same
1358 partition. This saves us from having to split abnormal critical
1360 for (bb = n_basic_blocks; --bb >= 0; )
1361 changed += make_regs_equivalent_over_bad_edges (bb, p);
1363 /* Now we have to insure that corresponding arguments of phi nodes
1364 assigning to corresponding regs are equivalent. Iterate until
1369 for (bb = n_basic_blocks; --bb >= 0; )
1370 changed += make_equivalent_phi_alternatives_equivalent (bb, p);
1376 /* The following functions compute a register partition that attempts
1377 to eliminate as many reg copies and phi node copies as possible by
1378 coalescing registers. This is the strategy:
1380 1. As in the conservative case, the top priority is to coalesce
1381 registers that otherwise would cause copies to be placed on
1382 abnormal critical edges (which isn't possible).
1384 2. Figure out which regs are involved (in the LHS or RHS) of
1385 copies and phi nodes. Compute conflicts among these regs.
1387 3. Walk around the instruction stream, placing two regs in the
1388 same class of the partition if one appears on the LHS and the
1389 other on the RHS of a copy or phi node and the two regs don't
1390 conflict. The conflict information of course needs to be
1393 4. If anything has changed, there may be new opportunities to
1394 coalesce regs, so go back to 2.
1397 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1398 same class of partition P, if they aren't already. Update
1399 CONFLICTS appropriately.
1401 Returns one if REG1 and REG2 were placed in the same class but were
1402 not previously; zero otherwise.
1404 See Morgan figure 11.15. */
1407 coalesce_if_unconflicting (p, conflicts, reg1, reg2)
1409 conflict_graph conflicts;
1415 /* Don't mess with hard regs. */
1416 if (reg1 < FIRST_PSEUDO_REGISTER || reg2 < FIRST_PSEUDO_REGISTER)
1419 /* Find the canonical regs for the classes containing REG1 and
1421 reg1 = partition_find (p, reg1);
1422 reg2 = partition_find (p, reg2);
1424 /* If they're already in the same class, there's nothing to do. */
1428 /* If the regs conflict, our hands are tied. */
1429 if (conflict_graph_conflict_p (conflicts, reg1, reg2))
1432 /* We're good to go. Put the regs in the same partition. */
1433 partition_union (p, reg1, reg2);
1435 /* Find the new canonical reg for the merged class. */
1436 reg = partition_find (p, reg1);
1438 /* Merge conflicts from the two previous classes. */
1439 conflict_graph_merge_regs (conflicts, reg, reg1);
1440 conflict_graph_merge_regs (conflicts, reg, reg2);
1445 /* For each register copy insn in basic block BB, place the LHS and
1446 RHS regs in the same class in partition P if they do not conflict
1447 according to CONFLICTS.
1449 Returns the number of changes that were made to P.
1451 See Morgan figure 11.14. */
1454 coalesce_regs_in_copies (bb, p, conflicts)
1457 conflict_graph conflicts;
1463 /* Scan the instruction stream of the block. */
1464 for (insn = bb->head; insn != end; insn = NEXT_INSN (insn))
1470 /* If this isn't a set insn, go to the next insn. */
1471 if (GET_CODE (insn) != INSN)
1473 pattern = PATTERN (insn);
1474 if (GET_CODE (pattern) != SET)
1477 src = SET_SRC (pattern);
1478 dest = SET_DEST (pattern);
1480 /* If src or dest are subregs, find the underlying reg. */
1481 while (GET_CODE (src) == SUBREG
1482 && SUBREG_WORD (src) != 0)
1483 src = SUBREG_REG (src);
1484 while (GET_CODE (dest) == SUBREG
1485 && SUBREG_WORD (dest) != 0)
1486 dest = SUBREG_REG (dest);
1488 /* We're only looking for copies. */
1489 if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
1492 /* Coalesce only if the reg modes are the same. As long as
1493 each reg's rtx is unique, it can have only one mode, so two
1494 pseudos of different modes can't be coalesced into one.
1496 FIXME: We can probably get around this by inserting SUBREGs
1497 where appropriate, but for now we don't bother. */
1498 if (GET_MODE (src) != GET_MODE (dest))
1501 /* Found a copy; see if we can use the same reg for both the
1502 source and destination (and thus eliminate the copy,
1504 changed += coalesce_if_unconflicting (p, conflicts,
1505 REGNO (src), REGNO (dest));
1512 struct phi_coalesce_context
1515 conflict_graph conflicts;
1519 /* Callback function for for_each_successor_phi. If the set
1520 destination and the phi alternative regs do not conflict, place
1521 them in the same paritition class. DATA is a pointer to a
1522 phi_coalesce_context struct. */
1525 coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
1526 rtx insn ATTRIBUTE_UNUSED;
1531 struct phi_coalesce_context *context =
1532 (struct phi_coalesce_context *) data;
1534 /* Attempt to use the same reg, if they don't conflict. */
1536 += coalesce_if_unconflicting (context->p, context->conflicts,
1537 dest_regno, src_regno);
1541 /* For each alternative in a phi function corresponding to basic block
1542 BB (in phi nodes in successor block to BB), place the reg in the
1543 phi alternative and the reg to which the phi value is set into the
1544 same class in partition P, if allowed by CONFLICTS.
1546 Return the number of changes that were made to P.
1548 See Morgan figure 11.14. */
1551 coalesce_regs_in_successor_phi_nodes (bb, p, conflicts)
1554 conflict_graph conflicts;
1556 struct phi_coalesce_context context;
1558 context.conflicts = conflicts;
1559 context.changed = 0;
1561 for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);
1563 return context.changed;
1566 /* Compute and return a partition of pseudos. Where possible,
1567 non-conflicting pseudos are placed in the same class.
1569 The caller is responsible for deallocating the returned partition. */
1572 compute_coalesced_reg_partition ()
1577 /* We don't actually work with hard registers, but it's easier to
1578 carry them around anyway rather than constantly doing register
1579 number arithmetic. */
1581 partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER);
1583 /* The first priority is to make sure registers that might have to
1584 be copied on abnormal critical edges are placed in the same
1585 partition. This saves us from having to split abnormal critical
1586 edges (which can't be done). */
1587 for (bb = n_basic_blocks; --bb >= 0; )
1588 make_regs_equivalent_over_bad_edges (bb, p);
1592 regset_head phi_set;
1593 conflict_graph conflicts;
1597 /* Build the set of registers involved in phi nodes, either as
1598 arguments to the phi function or as the target of a set. */
1599 INITIALIZE_REG_SET (phi_set);
1600 mark_phi_and_copy_regs (&phi_set);
1602 /* Compute conflicts. */
1603 conflicts = conflict_graph_compute (&phi_set, p);
1605 /* FIXME: Better would be to process most frequently executed
1606 blocks first, so that most frequently executed copies would
1607 be more likely to be removed by register coalescing. But any
1608 order will generate correct, if non-optimal, results. */
1609 for (bb = n_basic_blocks; --bb >= 0; )
1611 basic_block block = BASIC_BLOCK (bb);
1612 changed += coalesce_regs_in_copies (block, p, conflicts);
1614 coalesce_regs_in_successor_phi_nodes (block, 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 /* Need global_live_at_{start,end} up to date. */
1815 life_analysis (insns, NULL, PROP_KILL_DEAD_CODE | PROP_SCAN_DEAD_CODE);
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;
1887 if (bb == EXIT_BLOCK_PTR)
1890 /* Scan outgoing edges. */
1891 for (e = bb->succ; e != NULL; e = e->succ_next)
1895 basic_block successor = e->dest;
1896 if (successor == ENTRY_BLOCK_PTR
1897 || successor == EXIT_BLOCK_PTR)
1900 /* Advance to the first non-label insn of the successor block. */
1901 insn = successor->head;
1903 && (GET_CODE (insn) == CODE_LABEL
1904 || GET_CODE (insn) == NOTE))
1905 insn = NEXT_INSN (insn);
1910 /* Scan phi nodes in the successor. */
1911 for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
1914 rtx phi_set = PATTERN (insn);
1915 rtx *alternative = phi_alternative (phi_set, bb->index);
1918 /* This phi function may not have an alternative
1919 corresponding to the incoming edge, indicating the
1920 assigned variable is not defined along the edge. */
1921 if (alternative == NULL)
1923 phi_src = *alternative;
1925 /* Invoke the callback. */
1926 result = (*fn) (insn, REGNO (SET_DEST (phi_set)),
1927 REGNO (phi_src), data);
1929 /* Terminate if requested. */