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
))
656 rtx
*destp
= &SET_DEST (x
);
657 rtx dest
= SET_DEST (x
);
659 /* Some SETs also use the REG specified in their LHS.
660 These can be detected by the presence of
661 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
662 in the LHS. Handle these by changing
663 (set (subreg (reg foo)) ...)
665 (sequence [(set (reg foo_1) (reg foo))
666 (set (subreg (reg foo_1)) ...)])
668 FIXME: Much of the time this is too much. For many libcalls,
669 paradoxical SUBREGs, etc., the input register is dead. We should
670 recognise this in rename_block or here and not make a false
673 if (GET_CODE (dest
) == STRICT_LOW_PART
674 || GET_CODE (dest
) == SUBREG
675 || GET_CODE (dest
) == SIGN_EXTRACT
676 || GET_CODE (dest
) == ZERO_EXTRACT
)
681 while (GET_CODE (reg
) == STRICT_LOW_PART
682 || GET_CODE (reg
) == SUBREG
683 || GET_CODE (reg
) == SIGN_EXTRACT
684 || GET_CODE (reg
) == ZERO_EXTRACT
)
687 if (GET_CODE (reg
) == REG
688 && REGNO (reg
) >= FIRST_PSEUDO_REGISTER
)
690 /* Generate (set reg reg), and do renaming on it so
691 that it becomes (set reg_1 reg_0), and we will
692 replace reg with reg_1 in the SUBREG. */
694 struct rename_set_data
*saved_new_renames
;
695 saved_new_renames
= context
->new_renames
;
696 context
->new_renames
= NULL
;
697 i
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
698 for_each_rtx (&i
, rename_insn_1
, data
);
699 apply_delayed_renames (context
);
700 context
->new_renames
= saved_new_renames
;
703 else if (GET_CODE (dest
) == REG
704 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
706 /* We found a genuine set of an interesting register. Tag
707 it so that we can create a new name for it after we finish
708 processing this insn. */
710 create_delayed_rename (context
, destp
);
712 /* Since we do not wish to (directly) traverse the
713 SET_DEST, recurse through for_each_rtx for the SET_SRC
715 if (GET_CODE (x
) == SET
)
716 for_each_rtx (&SET_SRC (x
), rename_insn_1
, data
);
720 /* Otherwise, this was not an interesting destination. Continue
721 on, marking uses as normal. */
726 if (REGNO (x
) >= FIRST_PSEUDO_REGISTER
727 && REGNO (x
) < ssa_max_reg_num
)
729 rtx new_reg
= ssa_rename_to
[REGNO(x
) - FIRST_PSEUDO_REGISTER
];
731 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
733 if (GET_MODE (x
) != GET_MODE (new_reg
))
737 /* Else this is a use before a set. Warn? */
742 /* Never muck with the phi. We do that elsewhere, special-like. */
746 /* Anything else, continue traversing. */
752 rename_block (bb
, idom
)
756 basic_block b
= BASIC_BLOCK (bb
);
758 rtx insn
, next
, last
;
759 struct rename_set_data
*set_data
= NULL
;
762 /* Step One: Walk the basic block, adding new names for sets and
770 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
772 struct rename_context context
;
773 context
.done_renames
= set_data
;
774 context
.new_renames
= NULL
;
775 context
.current_insn
= insn
;
778 for_each_rtx (&PATTERN (insn
), rename_insn_1
, &context
);
779 for_each_rtx (®_NOTES (insn
), rename_insn_1
, &context
);
781 /* Sometimes, we end up with a sequence of insns that
782 SSA needs to treat as a single insn. Wrap these in a
783 SEQUENCE. (Any notes now get attached to the SEQUENCE,
784 not to the old version inner insn.) */
785 if (get_insns () != NULL_RTX
)
790 emit (PATTERN (insn
));
791 seq
= gen_sequence ();
792 /* We really want a SEQUENCE of SETs, not a SEQUENCE
794 for (i
= 0; i
< XVECLEN (seq
, 0); i
++)
795 XVECEXP (seq
, 0, i
) = PATTERN (XVECEXP (seq
, 0, i
));
796 PATTERN (insn
) = seq
;
800 apply_delayed_renames (&context
);
801 set_data
= context
.done_renames
;
804 next
= NEXT_INSN (insn
);
806 while (insn
!= last
);
808 /* Step Two: Update the phi nodes of this block's successors. */
810 for (e
= b
->succ
; e
; e
= e
->succ_next
)
812 if (e
->dest
== EXIT_BLOCK_PTR
)
815 insn
= e
->dest
->head
;
816 if (GET_CODE (insn
) == CODE_LABEL
)
817 insn
= NEXT_INSN (insn
);
819 while (PHI_NODE_P (insn
))
821 rtx phi
= PATTERN (insn
);
825 /* Find out which of our outgoing registers this node is
826 indended to replace. Note that if this not the first PHI
827 node to have been created for this register, we have to
828 jump through rename links to figure out which register
829 we're talking about. This can easily be recognized by
830 noting that the regno is new to this pass. */
831 regno
= REGNO (SET_DEST (phi
));
832 if (regno
>= ssa_max_reg_num
)
833 regno
= REGNO (VARRAY_RTX (ssa_rename_from
, regno
));
834 reg
= ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
];
836 /* It is possible for the variable to be uninitialized on
837 edges in. Reduce the arity of the PHI so that we don't
838 consider those edges. */
839 if (reg
== NULL
|| reg
== RENAME_NO_RTX
)
841 if (! remove_phi_alternative (phi
, bb
))
846 /* When we created the PHI nodes, we did not know what mode
847 the register should be. Now that we've found an original,
848 we can fill that in. */
849 if (GET_MODE (SET_DEST (phi
)) == VOIDmode
)
850 PUT_MODE (SET_DEST (phi
), GET_MODE (reg
));
851 else if (GET_MODE (SET_DEST (phi
)) != GET_MODE (reg
))
854 *phi_alternative (phi
, bb
) = reg
;
855 /* ??? Mark for a new ssa_uses entry. */
858 insn
= NEXT_INSN (insn
);
862 /* Step Three: Do the same to the children of this block in
865 for (c
= 0; c
< n_basic_blocks
; ++c
)
867 rename_block (c
, idom
);
869 /* Step Four: Update the sets to refer to their new register,
870 and restore ssa_rename_to to its previous state. */
874 struct rename_set_data
*next
;
875 rtx old_reg
= *set_data
->reg_loc
;
877 if (*set_data
->reg_loc
!= set_data
->old_reg
)
879 *set_data
->reg_loc
= set_data
->new_reg
;
881 ssa_rename_to
[REGNO (old_reg
)-FIRST_PSEUDO_REGISTER
]
882 = set_data
->prev_reg
;
884 next
= set_data
->next
;
891 rename_registers (nregs
, idom
)
895 VARRAY_RTX_INIT (ssa_definition
, nregs
* 3, "ssa_definition");
896 VARRAY_RTX_INIT (ssa_uses
, nregs
* 3, "ssa_uses");
897 VARRAY_RTX_INIT (ssa_rename_from
, nregs
* 3, "ssa_rename_from");
899 ssa_rename_to
= (rtx
*) alloca (nregs
* sizeof(rtx
));
900 bzero ((char *) ssa_rename_to
, nregs
* sizeof(rtx
));
902 rename_block (0, idom
);
904 /* ??? Update basic_block_live_at_start, and other flow info
907 ssa_rename_to
= NULL
;
911 /* The main entry point for moving to SSA. */
916 /* Element I is the set of blocks that set register I. */
919 /* Dominator bitmaps. */
924 /* Element I is the immediate dominator of block I. */
929 /* Don't do it twice. */
933 /* Need global_live_at_{start,end} up to date. */
934 life_analysis (get_insns (), NULL
, PROP_KILL_DEAD_CODE
| PROP_SCAN_DEAD_CODE
);
936 /* Compute dominators. */
937 dominators
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
938 compute_flow_dominators (dominators
, NULL
);
940 idom
= (int *) alloca (n_basic_blocks
* sizeof (int));
941 memset ((void *)idom
, -1, (size_t)n_basic_blocks
* sizeof (int));
942 simplify_to_immediate_dominators (idom
, dominators
);
944 sbitmap_vector_free (dominators
);
949 fputs (";; Immediate Dominators:\n", rtl_dump_file
);
950 for (i
= 0; i
< n_basic_blocks
; ++i
)
951 fprintf (rtl_dump_file
, ";\t%3d = %3d\n", i
, idom
[i
]);
952 fflush (rtl_dump_file
);
955 /* Compute dominance frontiers. */
957 dfs
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
958 compute_dominance_frontiers (dfs
, idom
);
962 dump_sbitmap_vector (rtl_dump_file
, ";; Dominance Frontiers:",
963 "; Basic Block", dfs
, n_basic_blocks
);
964 fflush (rtl_dump_file
);
967 /* Compute register evaluations. */
969 ssa_max_reg_num
= max_reg_num();
970 nregs
= ssa_max_reg_num
- FIRST_PSEUDO_REGISTER
;
971 evals
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
972 find_evaluations (evals
, nregs
);
974 /* Compute the iterated dominance frontier for each register. */
976 idfs
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
977 compute_iterated_dominance_frontiers (idfs
, dfs
, evals
, nregs
);
981 dump_sbitmap_vector (rtl_dump_file
, ";; Iterated Dominance Frontiers:",
982 "; Register-FIRST_PSEUDO_REGISTER", idfs
, nregs
);
983 fflush (rtl_dump_file
);
986 /* Insert the phi nodes. */
988 insert_phi_nodes (idfs
, evals
, nregs
);
990 /* Rename the registers to satisfy SSA. */
992 rename_registers (nregs
, idom
);
994 /* All done! Clean up and go home. */
996 sbitmap_vector_free (dfs
);
997 sbitmap_vector_free (evals
);
998 sbitmap_vector_free (idfs
);
1001 reg_scan (get_insns (), max_reg_num (), 1);
1005 /* REG is the representative temporary of its partition. Add it to the
1006 set of nodes to be processed, if it hasn't been already. Return the
1007 index of this register in the node set. */
1010 ephi_add_node (reg
, nodes
, n_nodes
)
1015 for (i
= *n_nodes
- 1; i
>= 0; --i
)
1016 if (REGNO (reg
) == REGNO (nodes
[i
]))
1019 nodes
[i
= (*n_nodes
)++] = reg
;
1023 /* Part one of the topological sort. This is a forward (downward) search
1024 through the graph collecting a stack of nodes to process. Assuming no
1025 cycles, the nodes at top of the stack when we are finished will have
1026 no other dependancies. */
1029 ephi_forward (t
, visited
, succ
, tstack
)
1037 SET_BIT (visited
, t
);
1039 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1041 if (! TEST_BIT (visited
, s
))
1042 tstack
= ephi_forward (s
, visited
, succ
, tstack
);
1049 /* Part two of the topological sort. The is a backward search through
1050 a cycle in the graph, copying the data forward as we go. */
1053 ephi_backward (t
, visited
, pred
, nodes
)
1055 sbitmap visited
, *pred
;
1060 SET_BIT (visited
, t
);
1062 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1064 if (! TEST_BIT (visited
, p
))
1066 ephi_backward (p
, visited
, pred
, nodes
);
1067 emit_move_insn (nodes
[p
], nodes
[t
]);
1072 /* Part two of the topological sort. Create the copy for a register
1073 and any cycle of which it is a member. */
1076 ephi_create (t
, visited
, pred
, succ
, nodes
)
1078 sbitmap visited
, *pred
, *succ
;
1081 rtx reg_u
= NULL_RTX
;
1082 int unvisited_predecessors
= 0;
1085 /* Iterate through the predecessor list looking for unvisited nodes.
1086 If there are any, we have a cycle, and must deal with that. At
1087 the same time, look for a visited predecessor. If there is one,
1088 we won't need to create a temporary. */
1090 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1092 if (! TEST_BIT (visited
, p
))
1093 unvisited_predecessors
= 1;
1098 if (unvisited_predecessors
)
1100 /* We found a cycle. Copy out one element of the ring (if necessary),
1101 then traverse the ring copying as we go. */
1105 reg_u
= gen_reg_rtx (GET_MODE (nodes
[t
]));
1106 emit_move_insn (reg_u
, nodes
[t
]);
1109 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1111 if (! TEST_BIT (visited
, p
))
1113 ephi_backward (p
, visited
, pred
, nodes
);
1114 emit_move_insn (nodes
[p
], reg_u
);
1120 /* No cycle. Just copy the value from a successor. */
1123 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1125 SET_BIT (visited
, t
);
1126 emit_move_insn (nodes
[t
], nodes
[s
]);
1132 /* Convert the edge to normal form. */
1135 eliminate_phi (e
, reg_partition
)
1137 partition reg_partition
;
1140 sbitmap
*pred
, *succ
;
1143 int *stack
, *tstack
;
1147 /* Collect an upper bound on the number of registers needing processing. */
1149 insn
= e
->dest
->head
;
1150 if (GET_CODE (insn
) == CODE_LABEL
)
1151 insn
= next_nonnote_insn (insn
);
1154 while (PHI_NODE_P (insn
))
1156 insn
= next_nonnote_insn (insn
);
1163 /* Build the auxilliary graph R(B).
1165 The nodes of the graph are the members of the register partition
1166 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1167 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1169 nodes
= (rtx
*) alloca (n_nodes
* sizeof(rtx
));
1170 pred
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1171 succ
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1172 sbitmap_vector_zero (pred
, n_nodes
);
1173 sbitmap_vector_zero (succ
, n_nodes
);
1175 insn
= e
->dest
->head
;
1176 if (GET_CODE (insn
) == CODE_LABEL
)
1177 insn
= next_nonnote_insn (insn
);
1180 for (; PHI_NODE_P (insn
); insn
= next_nonnote_insn (insn
))
1182 rtx
* preg
= phi_alternative (PATTERN (insn
), e
->src
->index
);
1183 rtx tgt
= SET_DEST (PATTERN (insn
));
1186 /* There may be no phi alternative corresponding to this edge.
1187 This indicates that the phi variable is undefined along this
1193 if (GET_CODE (reg
) != REG
|| GET_CODE (tgt
) != REG
)
1196 reg
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (reg
))];
1197 tgt
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (tgt
))];
1198 /* If the two registers are already in the same partition,
1199 nothing will need to be done. */
1204 ireg
= ephi_add_node (reg
, nodes
, &n_nodes
);
1205 itgt
= ephi_add_node (tgt
, nodes
, &n_nodes
);
1207 SET_BIT (pred
[ireg
], itgt
);
1208 SET_BIT (succ
[itgt
], ireg
);
1215 /* Begin a topological sort of the graph. */
1217 visited
= sbitmap_alloc (n_nodes
);
1218 sbitmap_zero (visited
);
1220 tstack
= stack
= (int *) alloca (n_nodes
* sizeof (int));
1222 for (i
= 0; i
< n_nodes
; ++i
)
1223 if (! TEST_BIT (visited
, i
))
1224 tstack
= ephi_forward (i
, visited
, succ
, tstack
);
1226 sbitmap_zero (visited
);
1228 /* As we find a solution to the tsort, collect the implementation
1229 insns in a sequence. */
1232 while (tstack
!= stack
)
1235 if (! TEST_BIT (visited
, i
))
1236 ephi_create (i
, visited
, pred
, succ
, nodes
);
1239 insn
= gen_sequence ();
1241 insert_insn_on_edge (insn
, e
);
1243 fprintf (rtl_dump_file
, "Emitting copy on edge (%d,%d)\n",
1244 e
->src
->index
, e
->dest
->index
);
1246 sbitmap_free (visited
);
1248 sbitmap_vector_free (pred
);
1249 sbitmap_vector_free (succ
);
1253 /* For basic block B, consider all phi insns which provide an
1254 alternative corresponding to an incoming abnormal critical edge.
1255 Place the phi alternative corresponding to that abnormal critical
1256 edge in the same register class as the destination of the set.
1258 From Morgan, p. 178:
1260 For each abnormal critical edge (C, B),
1261 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1262 and C is the ith predecessor of B,
1263 then T0 and Ti must be equivalent.
1265 Return non-zero iff any such cases were found for which the two
1266 regs were not already in the same class. */
1269 make_regs_equivalent_over_bad_edges (bb
, reg_partition
)
1271 partition reg_partition
;
1274 basic_block b
= BASIC_BLOCK (bb
);
1277 /* Advance to the first phi node. */
1278 if (GET_CODE (phi
) == CODE_LABEL
)
1279 phi
= next_nonnote_insn (phi
);
1281 /* Scan all the phi nodes. */
1284 phi
= next_nonnote_insn (phi
))
1288 rtx set
= PATTERN (phi
);
1289 rtx tgt
= SET_DEST (set
);
1291 /* The set target is expected to be a pseudo. */
1292 if (GET_CODE (tgt
) != REG
1293 || REGNO (tgt
) < FIRST_PSEUDO_REGISTER
)
1295 tgt_regno
= REGNO (tgt
);
1297 /* Scan incoming abnormal critical edges. */
1298 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1299 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1300 == (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1302 rtx
*alt
= phi_alternative (set
, e
->src
->index
);
1305 /* If there is no alternative corresponding to this edge,
1306 the value is undefined along the edge, so just go on. */
1310 /* The phi alternative is expected to be a pseudo. */
1311 if (GET_CODE (*alt
) != REG
1312 || REGNO (*alt
) < FIRST_PSEUDO_REGISTER
)
1314 alt_regno
= REGNO (*alt
);
1316 /* If the set destination and the phi alternative aren't
1317 already in the same class... */
1318 if (partition_find (reg_partition
, tgt_regno
)
1319 != partition_find (reg_partition
, alt_regno
))
1321 /* ... make them such. */
1322 partition_union (reg_partition
,
1323 tgt_regno
, alt_regno
);
1333 /* Consider phi insns in basic block BB pairwise. If the set target
1334 of both isns are equivalent pseudos, make the corresponding phi
1335 alternatives in each phi corresponding equivalent.
1337 Return nonzero if any new register classes were unioned. */
1340 make_equivalent_phi_alternatives_equivalent (bb
, reg_partition
)
1342 partition reg_partition
;
1345 rtx phi
= BLOCK_HEAD (bb
);
1346 basic_block b
= BASIC_BLOCK (bb
);
1348 /* Advance to the first phi node. */
1349 if (GET_CODE (phi
) == CODE_LABEL
)
1350 phi
= next_nonnote_insn (phi
);
1352 /* Scan all the phi nodes. */
1355 phi
= next_nonnote_insn (phi
))
1357 rtx set
= PATTERN (phi
);
1358 /* The regno of the destination of the set. */
1359 int tgt_regno
= REGNO (SET_DEST (PATTERN (phi
)));
1361 rtx phi2
= next_nonnote_insn (phi
);
1363 /* Scan all phi nodes following this one. */
1366 phi2
= next_nonnote_insn (phi2
))
1368 rtx set2
= PATTERN (phi2
);
1369 /* The regno of the destination of the set. */
1370 int tgt2_regno
= REGNO (SET_DEST (set2
));
1372 /* Are the set destinations equivalent regs? */
1373 if (partition_find (reg_partition
, tgt_regno
) ==
1374 partition_find (reg_partition
, tgt2_regno
))
1377 /* Scan over edges. */
1378 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1380 int pred_block
= e
->src
->index
;
1381 /* Identify the phi altnernatives from both phi
1382 nodes corresponding to this edge. */
1383 rtx
*alt
= phi_alternative (set
, pred_block
);
1384 rtx
*alt2
= phi_alternative (set2
, pred_block
);
1386 /* If one of the phi nodes doesn't have a
1387 corresponding alternative, just skip it. */
1388 if (alt
== 0 || alt2
== 0)
1391 /* Both alternatives should be pseudos. */
1392 if (GET_CODE (*alt
) != REG
1393 || REGNO (*alt
) < FIRST_PSEUDO_REGISTER
)
1395 if (GET_CODE (*alt2
) != REG
1396 || REGNO (*alt2
) < FIRST_PSEUDO_REGISTER
)
1399 /* If the altneratives aren't already in the same
1401 if (partition_find (reg_partition
, REGNO (*alt
))
1402 != partition_find (reg_partition
, REGNO (*alt2
)))
1404 /* ... make them so. */
1405 partition_union (reg_partition
,
1406 REGNO (*alt
), REGNO (*alt2
));
1417 /* Compute a conservative partition of outstanding pseudo registers.
1418 See Morgan 7.3.1. */
1421 compute_conservative_reg_partition ()
1426 /* We don't actually work with hard registers, but it's easier to
1427 carry them around anyway rather than constantly doing register
1428 number arithmetic. */
1430 partition_new (ssa_definition
->num_elements
+ FIRST_PSEUDO_REGISTER
);
1432 /* The first priority is to make sure registers that might have to
1433 be copied on abnormal critical edges are placed in the same
1434 partition. This saves us from having to split abnormal critical
1436 for (bb
= n_basic_blocks
; --bb
>= 0; )
1437 changed
+= make_regs_equivalent_over_bad_edges (bb
, p
);
1439 /* Now we have to insure that corresponding arguments of phi nodes
1440 assigning to corresponding regs are equivalent. Iterate until
1445 for (bb
= n_basic_blocks
; --bb
>= 0; )
1446 changed
+= make_equivalent_phi_alternatives_equivalent (bb
, p
);
1452 /* The following functions compute a register partition that attempts
1453 to eliminate as many reg copies and phi node copies as possible by
1454 coalescing registers. This is the strategy:
1456 1. As in the conservative case, the top priority is to coalesce
1457 registers that otherwise would cause copies to be placed on
1458 abnormal critical edges (which isn't possible).
1460 2. Figure out which regs are involved (in the LHS or RHS) of
1461 copies and phi nodes. Compute conflicts among these regs.
1463 3. Walk around the instruction stream, placing two regs in the
1464 same class of the partition if one appears on the LHS and the
1465 other on the RHS of a copy or phi node and the two regs don't
1466 conflict. The conflict information of course needs to be
1469 4. If anything has changed, there may be new opportunities to
1470 coalesce regs, so go back to 2.
1473 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1474 same class of partition P, if they aren't already. Update
1475 CONFLICTS appropriately.
1477 Returns one if REG1 and REG2 were placed in the same class but were
1478 not previously; zero otherwise.
1480 See Morgan figure 11.15. */
1483 coalesce_if_unconflicting (p
, conflicts
, reg1
, reg2
)
1485 conflict_graph conflicts
;
1491 /* Don't mess with hard regs. */
1492 if (reg1
< FIRST_PSEUDO_REGISTER
|| reg2
< FIRST_PSEUDO_REGISTER
)
1495 /* Find the canonical regs for the classes containing REG1 and
1497 reg1
= partition_find (p
, reg1
);
1498 reg2
= partition_find (p
, reg2
);
1500 /* If they're already in the same class, there's nothing to do. */
1504 /* If the regs conflict, our hands are tied. */
1505 if (conflict_graph_conflict_p (conflicts
, reg1
, reg2
))
1508 /* We're good to go. Put the regs in the same partition. */
1509 partition_union (p
, reg1
, reg2
);
1511 /* Find the new canonical reg for the merged class. */
1512 reg
= partition_find (p
, reg1
);
1514 /* Merge conflicts from the two previous classes. */
1515 conflict_graph_merge_regs (conflicts
, reg
, reg1
);
1516 conflict_graph_merge_regs (conflicts
, reg
, reg2
);
1521 /* For each register copy insn in basic block BB, place the LHS and
1522 RHS regs in the same class in partition P if they do not conflict
1523 according to CONFLICTS.
1525 Returns the number of changes that were made to P.
1527 See Morgan figure 11.14. */
1530 coalesce_regs_in_copies (bb
, p
, conflicts
)
1533 conflict_graph conflicts
;
1539 /* Scan the instruction stream of the block. */
1540 for (insn
= bb
->head
; insn
!= end
; insn
= NEXT_INSN (insn
))
1546 /* If this isn't a set insn, go to the next insn. */
1547 if (GET_CODE (insn
) != INSN
)
1549 pattern
= PATTERN (insn
);
1550 if (GET_CODE (pattern
) != SET
)
1553 src
= SET_SRC (pattern
);
1554 dest
= SET_DEST (pattern
);
1556 /* We're only looking for copies. */
1557 if (GET_CODE (src
) != REG
|| GET_CODE (dest
) != REG
)
1560 /* Coalesce only if the reg modes are the same. As long as
1561 each reg's rtx is unique, it can have only one mode, so two
1562 pseudos of different modes can't be coalesced into one.
1564 FIXME: We can probably get around this by inserting SUBREGs
1565 where appropriate, but for now we don't bother. */
1566 if (GET_MODE (src
) != GET_MODE (dest
))
1569 /* Found a copy; see if we can use the same reg for both the
1570 source and destination (and thus eliminate the copy,
1572 changed
+= coalesce_if_unconflicting (p
, conflicts
,
1573 REGNO (src
), REGNO (dest
));
1580 struct phi_coalesce_context
1583 conflict_graph conflicts
;
1587 /* Callback function for for_each_successor_phi. If the set
1588 destination and the phi alternative regs do not conflict, place
1589 them in the same paritition class. DATA is a pointer to a
1590 phi_coalesce_context struct. */
1593 coalesce_reg_in_phi (insn
, dest_regno
, src_regno
, data
)
1594 rtx insn ATTRIBUTE_UNUSED
;
1599 struct phi_coalesce_context
*context
=
1600 (struct phi_coalesce_context
*) data
;
1602 /* Attempt to use the same reg, if they don't conflict. */
1604 += coalesce_if_unconflicting (context
->p
, context
->conflicts
,
1605 dest_regno
, src_regno
);
1609 /* For each alternative in a phi function corresponding to basic block
1610 BB (in phi nodes in successor block to BB), place the reg in the
1611 phi alternative and the reg to which the phi value is set into the
1612 same class in partition P, if allowed by CONFLICTS.
1614 Return the number of changes that were made to P.
1616 See Morgan figure 11.14. */
1619 coalesce_regs_in_successor_phi_nodes (bb
, p
, conflicts
)
1622 conflict_graph conflicts
;
1624 struct phi_coalesce_context context
;
1626 context
.conflicts
= conflicts
;
1627 context
.changed
= 0;
1629 for_each_successor_phi (bb
, &coalesce_reg_in_phi
, &context
);
1631 return context
.changed
;
1634 /* Compute and return a partition of pseudos. Where possible,
1635 non-conflicting pseudos are placed in the same class.
1637 The caller is responsible for deallocating the returned partition. */
1640 compute_coalesced_reg_partition ()
1645 /* We don't actually work with hard registers, but it's easier to
1646 carry them around anyway rather than constantly doing register
1647 number arithmetic. */
1649 partition_new (ssa_definition
->num_elements
+ FIRST_PSEUDO_REGISTER
);
1651 /* The first priority is to make sure registers that might have to
1652 be copied on abnormal critical edges are placed in the same
1653 partition. This saves us from having to split abnormal critical
1654 edges (which can't be done). */
1655 for (bb
= n_basic_blocks
; --bb
>= 0; )
1656 make_regs_equivalent_over_bad_edges (bb
, p
);
1660 regset_head phi_set
;
1661 conflict_graph conflicts
;
1665 /* Build the set of registers involved in phi nodes, either as
1666 arguments to the phi function or as the target of a set. */
1667 INITIALIZE_REG_SET (phi_set
);
1668 mark_phi_and_copy_regs (&phi_set
);
1670 /* Compute conflicts. */
1671 conflicts
= conflict_graph_compute (&phi_set
, p
);
1673 /* FIXME: Better would be to process most frequently executed
1674 blocks first, so that most frequently executed copies would
1675 be more likely to be removed by register coalescing. But any
1676 order will generate correct, if non-optimal, results. */
1677 for (bb
= n_basic_blocks
; --bb
>= 0; )
1679 basic_block block
= BASIC_BLOCK (bb
);
1680 changed
+= coalesce_regs_in_copies (block
, p
, conflicts
);
1682 coalesce_regs_in_successor_phi_nodes (block
, p
, conflicts
);
1685 conflict_graph_delete (conflicts
);
1687 while (changed
> 0);
1692 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1693 components (a REG or a CONST_INT). DATA is a reg set in which to
1694 set all regs. Called from for_each_rtx. */
1697 mark_reg_in_phi (ptr
, data
)
1702 regset set
= (regset
) data
;
1704 switch (GET_CODE (expr
))
1707 SET_REGNO_REG_SET (set
, REGNO (expr
));
1717 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1718 set from a phi expression, or used as an argument in one. Also
1719 mark regs that are the source or target of a reg copy. Uses
1723 mark_phi_and_copy_regs (phi_set
)
1728 /* Scan the definitions of all regs. */
1729 for (reg
= VARRAY_SIZE (ssa_definition
);
1730 --reg
>= FIRST_PSEUDO_REGISTER
;
1733 rtx insn
= VARRAY_RTX (ssa_definition
, reg
);
1739 pattern
= PATTERN (insn
);
1740 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1742 if (GET_CODE (pattern
) != SET
)
1744 src
= SET_SRC (pattern
);
1746 if (GET_CODE (src
) == REG
)
1748 /* It's a reg copy. */
1749 SET_REGNO_REG_SET (phi_set
, reg
);
1750 SET_REGNO_REG_SET (phi_set
, REGNO (src
));
1752 else if (GET_CODE (src
) == PHI
)
1754 /* It's a phi node. Mark the reg being set. */
1755 SET_REGNO_REG_SET (phi_set
, reg
);
1756 /* Mark the regs used in the phi function. */
1757 for_each_rtx (&src
, mark_reg_in_phi
, phi_set
);
1759 /* ... else nothing to do. */
1763 /* Rename regs in insn PTR that are equivalent. DATA is the register
1764 partition which specifies equivalences. */
1767 rename_equivalent_regs_in_insn (ptr
, data
)
1772 partition reg_partition
= (partition
) data
;
1777 switch (GET_CODE (x
))
1780 if (REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1782 int regno
= REGNO (x
);
1783 int new_regno
= partition_find (reg_partition
, regno
);
1784 if (regno
!= new_regno
)
1786 rtx new_reg
= regno_reg_rtx
[new_regno
];
1787 if (GET_MODE (x
) != GET_MODE (new_reg
))
1795 /* No need to rename the phi nodes. We'll check equivalence
1796 when inserting copies. */
1800 /* Anything else, continue traversing. */
1805 /* Rename regs that are equivalent in REG_PARTITION.
1806 Also collapse any SEQUENCE insns. */
1809 rename_equivalent_regs (reg_partition
)
1810 partition reg_partition
;
1814 for (bb
= n_basic_blocks
; --bb
>= 0; )
1816 basic_block b
= BASIC_BLOCK (bb
);
1824 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1826 for_each_rtx (&PATTERN (insn
),
1827 rename_equivalent_regs_in_insn
,
1829 for_each_rtx (®_NOTES (insn
),
1830 rename_equivalent_regs_in_insn
,
1833 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
1835 rtx s
= PATTERN (insn
);
1836 int slen
= XVECLEN (s
, 0);
1842 PATTERN (insn
) = XVECEXP (s
, 0, slen
-1);
1843 for (i
= 0; i
< slen
- 1; i
++)
1844 emit_block_insn_before (XVECEXP (s
, 0, i
), insn
, b
);
1848 next
= NEXT_INSN (insn
);
1850 while (insn
!= last
);
1854 /* The main entry point for moving from SSA. */
1860 partition reg_partition
;
1861 rtx insns
= get_insns ();
1863 /* Need global_live_at_{start,end} up to date. */
1864 life_analysis (insns
, NULL
,
1865 PROP_KILL_DEAD_CODE
| PROP_SCAN_DEAD_CODE
| PROP_DEATH_NOTES
);
1867 /* Figure out which regs in copies and phi nodes don't conflict and
1868 therefore can be coalesced. */
1869 if (conservative_reg_partition
)
1870 reg_partition
= compute_conservative_reg_partition ();
1872 reg_partition
= compute_coalesced_reg_partition ();
1874 rename_equivalent_regs (reg_partition
);
1876 /* Eliminate the PHI nodes. */
1877 for (bb
= n_basic_blocks
; --bb
>= 0; )
1879 basic_block b
= BASIC_BLOCK (bb
);
1882 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1883 if (e
->src
!= ENTRY_BLOCK_PTR
)
1884 eliminate_phi (e
, reg_partition
);
1887 partition_delete (reg_partition
);
1889 /* Actually delete the PHI nodes. */
1890 for (bb
= n_basic_blocks
; --bb
>= 0; )
1892 rtx insn
= BLOCK_HEAD (bb
);
1893 int start
= (GET_CODE (insn
) != CODE_LABEL
);
1896 insn
= next_nonnote_insn (insn
);
1897 while (PHI_NODE_P (insn
))
1899 /* If a phi node is the last insn in the block, there must
1900 have been nothing else. Set the block end to the block
1902 if (insn
== BLOCK_END (bb
))
1903 BLOCK_END (bb
) = BLOCK_HEAD (bb
);
1904 insn
= delete_insn (insn
);
1905 if (GET_CODE (insn
) == NOTE
)
1906 insn
= next_nonnote_insn (insn
);
1909 BLOCK_HEAD (bb
) = insn
;
1912 /* Commit all the copy nodes needed to convert out of SSA form. */
1913 commit_edge_insertions ();
1917 count_or_remove_death_notes (NULL
, 1);
1920 /* Scan phi nodes in successors to BB. For each such phi node that
1921 has a phi alternative value corresponding to BB, invoke FN. FN
1922 is passed the entire phi node insn, the regno of the set
1923 destination, the regno of the phi argument corresponding to BB,
1926 If FN ever returns non-zero, stops immediately and returns this
1927 value. Otherwise, returns zero. */
1930 for_each_successor_phi (bb
, fn
, data
)
1932 successor_phi_fn fn
;
1937 if (bb
== EXIT_BLOCK_PTR
)
1940 /* Scan outgoing edges. */
1941 for (e
= bb
->succ
; e
!= NULL
; e
= e
->succ_next
)
1945 basic_block successor
= e
->dest
;
1946 if (successor
== ENTRY_BLOCK_PTR
1947 || successor
== EXIT_BLOCK_PTR
)
1950 /* Advance to the first non-label insn of the successor block. */
1951 insn
= successor
->head
;
1953 && (GET_CODE (insn
) == CODE_LABEL
1954 || GET_CODE (insn
) == NOTE
))
1955 insn
= NEXT_INSN (insn
);
1960 /* Scan phi nodes in the successor. */
1961 for ( ; PHI_NODE_P (insn
); insn
= NEXT_INSN (insn
))
1964 rtx phi_set
= PATTERN (insn
);
1965 rtx
*alternative
= phi_alternative (phi_set
, bb
->index
);
1968 /* This phi function may not have an alternative
1969 corresponding to the incoming edge, indicating the
1970 assigned variable is not defined along the edge. */
1971 if (alternative
== NULL
)
1973 phi_src
= *alternative
;
1975 /* Invoke the callback. */
1976 result
= (*fn
) (insn
, REGNO (SET_DEST (phi_set
)),
1977 REGNO (phi_src
), data
);
1979 /* Terminate if requested. */