1 /* Static Single Assignment conversion routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 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 GCC; 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 "partition.h"
42 #include "hard-reg-set.h"
46 #include "insn-config.h"
48 #include "basic-block.h"
54 Handle subregs better, maybe. For now, if a reg that's set in a
55 subreg expression is duplicated going into SSA form, an extra copy
56 is inserted first that copies the entire reg into the duplicate, so
57 that the other bits are preserved. This isn't strictly SSA, since
58 at least part of the reg is assigned in more than one place (though
61 ??? What to do about strict_low_part. Probably I'll have to split
62 them out of their current instructions first thing.
64 Actually the best solution may be to have a kind of "mid-level rtl"
65 in which the RTL encodes exactly what we want, without exposing a
66 lot of niggling processor details. At some later point we lower
67 the representation, calling back into optabs to finish any necessary
70 /* All pseudo-registers and select hard registers are converted to SSA
71 form. When converting out of SSA, these select hard registers are
72 guaranteed to be mapped to their original register number. Each
73 machine's .h file should define CONVERT_HARD_REGISTER_TO_SSA_P
74 indicating which hard registers should be converted.
76 When converting out of SSA, temporaries for all registers are
77 partitioned. The partition is checked to ensure that all uses of
78 the same hard register in the same machine mode are in the same
81 /* If conservative_reg_partition is non-zero, use a conservative
82 register partitioning algorithm (which leaves more regs after
83 emerging from SSA) instead of the coalescing one. This is being
84 left in for a limited time only, as a debugging tool until the
85 coalescing algorithm is validated. */
87 static int conservative_reg_partition
;
89 /* This flag is set when the CFG is in SSA form. */
92 /* Element I is the single instruction that sets register I. */
93 varray_type ssa_definition
;
95 /* Element I-PSEUDO is the normal register that originated the ssa
96 register in question. */
97 varray_type ssa_rename_from
;
99 /* Element I is the normal register that originated the ssa
100 register in question.
102 A hash table stores the (register, rtl) pairs. These are each
103 xmalloc'ed and deleted when the hash table is destroyed. */
104 htab_t ssa_rename_from_ht
;
106 /* The running target ssa register for a given pseudo register.
107 (Pseudo registers appear in only one mode.) */
108 static rtx
*ssa_rename_to_pseudo
;
109 /* Similar, but for hard registers. A hard register can appear in
110 many modes, so we store an equivalent pseudo for each of the
112 static rtx ssa_rename_to_hard
[FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
114 /* ssa_rename_from maps pseudo registers to the original corresponding
115 RTL. It is implemented as using a hash table. */
120 } ssa_rename_from_pair
;
122 struct ssa_rename_from_hash_table_data
{
123 sbitmap canonical_elements
;
124 partition reg_partition
;
127 static rtx gen_sequence
129 static void ssa_rename_from_initialize
131 static rtx ssa_rename_from_lookup
133 static unsigned int original_register
134 PARAMS ((unsigned int regno
));
135 static void ssa_rename_from_insert
136 PARAMS ((unsigned int reg
, rtx r
));
137 static void ssa_rename_from_free
139 typedef int (*srf_trav
) PARAMS ((int regno
, rtx r
, sbitmap canonical_elements
, partition reg_partition
));
140 static void ssa_rename_from_traverse
141 PARAMS ((htab_trav callback_function
, sbitmap canonical_elements
, partition reg_partition
));
142 /*static Avoid warnign message. */ void ssa_rename_from_print
144 static int ssa_rename_from_print_1
145 PARAMS ((void **slot
, void *data
));
146 static hashval_t ssa_rename_from_hash_function
147 PARAMS ((const void * srfp
));
148 static int ssa_rename_from_equal
149 PARAMS ((const void *srfp1
, const void *srfp2
));
150 static void ssa_rename_from_delete
151 PARAMS ((void *srfp
));
153 static rtx ssa_rename_to_lookup
155 static void ssa_rename_to_insert
156 PARAMS ((rtx reg
, rtx r
));
158 /* The number of registers that were live on entry to the SSA routines. */
159 static unsigned int ssa_max_reg_num
;
161 /* Local function prototypes. */
163 struct rename_context
;
165 static inline rtx
* phi_alternative
167 static void compute_dominance_frontiers_1
168 PARAMS ((sbitmap
*frontiers
, int *idom
, int bb
, sbitmap done
));
169 static void find_evaluations_1
170 PARAMS ((rtx dest
, rtx set
, void *data
));
171 static void find_evaluations
172 PARAMS ((sbitmap
*evals
, int nregs
));
173 static void compute_iterated_dominance_frontiers
174 PARAMS ((sbitmap
*idfs
, sbitmap
*frontiers
, sbitmap
*evals
, int nregs
));
175 static void insert_phi_node
176 PARAMS ((int regno
, int b
));
177 static void insert_phi_nodes
178 PARAMS ((sbitmap
*idfs
, sbitmap
*evals
, int nregs
));
179 static void create_delayed_rename
180 PARAMS ((struct rename_context
*, rtx
*));
181 static void apply_delayed_renames
182 PARAMS ((struct rename_context
*));
183 static int rename_insn_1
184 PARAMS ((rtx
*ptr
, void *data
));
185 static void rename_block
186 PARAMS ((int b
, int *idom
));
187 static void rename_registers
188 PARAMS ((int nregs
, int *idom
));
190 static inline int ephi_add_node
191 PARAMS ((rtx reg
, rtx
*nodes
, int *n_nodes
));
192 static int * ephi_forward
193 PARAMS ((int t
, sbitmap visited
, sbitmap
*succ
, int *tstack
));
194 static void ephi_backward
195 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, rtx
*nodes
));
196 static void ephi_create
197 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, sbitmap
*succ
, rtx
*nodes
));
198 static void eliminate_phi
199 PARAMS ((edge e
, partition reg_partition
));
200 static int make_regs_equivalent_over_bad_edges
201 PARAMS ((int bb
, partition reg_partition
));
203 /* These are used only in the conservative register partitioning
205 static int make_equivalent_phi_alternatives_equivalent
206 PARAMS ((int bb
, partition reg_partition
));
207 static partition compute_conservative_reg_partition
209 static int record_canonical_element_1
210 PARAMS ((void **srfp
, void *data
));
211 static int check_hard_regs_in_partition
212 PARAMS ((partition reg_partition
));
213 static int rename_equivalent_regs_in_insn
214 PARAMS ((rtx
*ptr
, void *data
));
216 /* These are used in the register coalescing algorithm. */
217 static int coalesce_if_unconflicting
218 PARAMS ((partition p
, conflict_graph conflicts
, int reg1
, int reg2
));
219 static int coalesce_regs_in_copies
220 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
221 static int coalesce_reg_in_phi
222 PARAMS ((rtx
, int dest_regno
, int src_regno
, void *data
));
223 static int coalesce_regs_in_successor_phi_nodes
224 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
225 static partition compute_coalesced_reg_partition
227 static int mark_reg_in_phi
228 PARAMS ((rtx
*ptr
, void *data
));
229 static void mark_phi_and_copy_regs
230 PARAMS ((regset phi_set
));
232 static int rename_equivalent_regs_in_insn
233 PARAMS ((rtx
*ptr
, void *data
));
234 static void rename_equivalent_regs
235 PARAMS ((partition reg_partition
));
237 /* Deal with hard registers. */
238 static int conflicting_hard_regs_p
239 PARAMS ((int reg1
, int reg2
));
241 /* ssa_rename_to maps registers and machine modes to SSA pseudo registers. */
243 /* Find the register associated with REG in the indicated mode. */
246 ssa_rename_to_lookup (reg
)
249 if (!HARD_REGISTER_P (reg
))
250 return ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
];
252 return ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)];
255 /* Store a new value mapping REG to R in ssa_rename_to. */
258 ssa_rename_to_insert(reg
, r
)
262 if (!HARD_REGISTER_P (reg
))
263 ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
] = r
;
265 ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)] = r
;
268 /* Prepare ssa_rename_from for use. */
271 ssa_rename_from_initialize ()
273 /* We use an arbitrary initial hash table size of 64. */
274 ssa_rename_from_ht
= htab_create (64,
275 &ssa_rename_from_hash_function
,
276 &ssa_rename_from_equal
,
277 &ssa_rename_from_delete
);
280 /* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
284 ssa_rename_from_lookup (reg
)
287 ssa_rename_from_pair srfp
;
288 ssa_rename_from_pair
*answer
;
290 srfp
.original
= NULL_RTX
;
291 answer
= (ssa_rename_from_pair
*)
292 htab_find_with_hash (ssa_rename_from_ht
, (void *) &srfp
, reg
);
293 return (answer
== 0 ? NULL_RTX
: answer
->original
);
296 /* Find the number of the original register specified by REGNO. If
297 the register is a pseudo, return the original register's number.
298 Otherwise, return this register number REGNO. */
301 original_register (regno
)
304 rtx original_rtx
= ssa_rename_from_lookup (regno
);
305 return original_rtx
!= NULL_RTX
? REGNO (original_rtx
) : regno
;
308 /* Add mapping from R to REG to ssa_rename_from even if already present. */
311 ssa_rename_from_insert (reg
, r
)
316 ssa_rename_from_pair
*srfp
= xmalloc (sizeof (ssa_rename_from_pair
));
319 slot
= htab_find_slot_with_hash (ssa_rename_from_ht
, (const void *) srfp
,
322 free ((void *) *slot
);
326 /* Apply the CALLBACK_FUNCTION to each element in ssa_rename_from.
327 CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
328 current use of this function. */
331 ssa_rename_from_traverse (callback_function
,
332 canonical_elements
, reg_partition
)
333 htab_trav callback_function
;
334 sbitmap canonical_elements
;
335 partition reg_partition
;
337 struct ssa_rename_from_hash_table_data srfhd
;
338 srfhd
.canonical_elements
= canonical_elements
;
339 srfhd
.reg_partition
= reg_partition
;
340 htab_traverse (ssa_rename_from_ht
, callback_function
, (void *) &srfhd
);
343 /* Destroy ssa_rename_from. */
346 ssa_rename_from_free ()
348 htab_delete (ssa_rename_from_ht
);
351 /* Print the contents of ssa_rename_from. */
353 /* static Avoid erroneous error message. */
355 ssa_rename_from_print ()
357 printf ("ssa_rename_from's hash table contents:\n");
358 htab_traverse (ssa_rename_from_ht
, &ssa_rename_from_print_1
, NULL
);
361 /* Print the contents of the hash table entry SLOT, passing the unused
362 sttribute DATA. Used as a callback function with htab_traverse (). */
365 ssa_rename_from_print_1 (slot
, data
)
367 void *data ATTRIBUTE_UNUSED
;
369 ssa_rename_from_pair
* p
= *slot
;
370 printf ("ssa_rename_from maps pseudo %i to original %i.\n",
371 p
->reg
, REGNO (p
->original
));
375 /* Given a hash entry SRFP, yield a hash value. */
378 ssa_rename_from_hash_function (srfp
)
381 return ((const ssa_rename_from_pair
*) srfp
)->reg
;
384 /* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
387 ssa_rename_from_equal (srfp1
, srfp2
)
391 return ssa_rename_from_hash_function (srfp1
) ==
392 ssa_rename_from_hash_function (srfp2
);
395 /* Delete the hash table entry SRFP. */
398 ssa_rename_from_delete (srfp
)
404 /* Given the SET of a PHI node, return the address of the alternative
405 for predecessor block C. */
408 phi_alternative (set
, c
)
412 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
415 for (v
= GET_NUM_ELEM (phi_vec
) - 2; v
>= 0; v
-= 2)
416 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
417 return &RTVEC_ELT (phi_vec
, v
);
422 /* Given the SET of a phi node, remove the alternative for predecessor
423 block C. Return non-zero on success, or zero if no alternative is
427 remove_phi_alternative (set
, block
)
431 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
432 int num_elem
= GET_NUM_ELEM (phi_vec
);
436 for (v
= num_elem
- 2; v
>= 0; v
-= 2)
437 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
439 if (v
< num_elem
- 2)
441 RTVEC_ELT (phi_vec
, v
) = RTVEC_ELT (phi_vec
, num_elem
- 2);
442 RTVEC_ELT (phi_vec
, v
+ 1) = RTVEC_ELT (phi_vec
, num_elem
- 1);
444 PUT_NUM_ELEM (phi_vec
, num_elem
- 2);
451 /* For all registers, find all blocks in which they are set.
453 This is the transform of what would be local kill information that
454 we ought to be getting from flow. */
456 static sbitmap
*fe_evals
;
457 static int fe_current_bb
;
460 find_evaluations_1 (dest
, set
, data
)
462 rtx set ATTRIBUTE_UNUSED
;
463 void *data ATTRIBUTE_UNUSED
;
465 if (GET_CODE (dest
) == REG
466 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
467 SET_BIT (fe_evals
[REGNO (dest
)], fe_current_bb
);
471 find_evaluations (evals
, nregs
)
477 sbitmap_vector_zero (evals
, nregs
);
480 FOR_EACH_BB_REVERSE (bb
)
484 fe_current_bb
= bb
->index
;
490 note_stores (PATTERN (p
), find_evaluations_1
, NULL
);
499 /* Computing the Dominance Frontier:
501 As decribed in Morgan, section 3.5, this may be done simply by
502 walking the dominator tree bottom-up, computing the frontier for
503 the children before the parent. When considering a block B,
506 (1) A flow graph edge leaving B that does not lead to a child
507 of B in the dominator tree must be a block that is either equal
508 to B or not dominated by B. Such blocks belong in the frontier
511 (2) Consider a block X in the frontier of one of the children C
512 of B. If X is not equal to B and is not dominated by B, it
513 is in the frontier of B.
517 compute_dominance_frontiers_1 (frontiers
, idom
, bb
, done
)
523 basic_block b
= BASIC_BLOCK (bb
);
528 sbitmap_zero (frontiers
[bb
]);
530 /* Do the frontier of the children first. Not all children in the
531 dominator tree (blocks dominated by this one) are children in the
532 CFG, so check all blocks. */
534 if (idom
[c
->index
] == bb
&& ! TEST_BIT (done
, c
->index
))
535 compute_dominance_frontiers_1 (frontiers
, idom
, c
->index
, done
);
537 /* Find blocks conforming to rule (1) above. */
538 for (e
= b
->succ
; e
; e
= e
->succ_next
)
540 if (e
->dest
== EXIT_BLOCK_PTR
)
542 if (idom
[e
->dest
->index
] != bb
)
543 SET_BIT (frontiers
[bb
], e
->dest
->index
);
546 /* Find blocks conforming to rule (2). */
548 if (idom
[c
->index
] == bb
)
551 EXECUTE_IF_SET_IN_SBITMAP (frontiers
[c
->index
], 0, x
,
554 SET_BIT (frontiers
[bb
], x
);
560 compute_dominance_frontiers (frontiers
, idom
)
564 sbitmap done
= sbitmap_alloc (last_basic_block
);
567 compute_dominance_frontiers_1 (frontiers
, idom
, 0, done
);
572 /* Computing the Iterated Dominance Frontier:
574 This is the set of merge points for a given register.
576 This is not particularly intuitive. See section 7.1 of Morgan, in
577 particular figures 7.3 and 7.4 and the immediately surrounding text.
581 compute_iterated_dominance_frontiers (idfs
, frontiers
, evals
, nregs
)
590 worklist
= sbitmap_alloc (last_basic_block
);
592 for (reg
= 0; reg
< nregs
; ++reg
)
594 sbitmap idf
= idfs
[reg
];
597 /* Start the iterative process by considering those blocks that
598 evaluate REG. We'll add their dominance frontiers to the
599 IDF, and then consider the blocks we just added. */
600 sbitmap_copy (worklist
, evals
[reg
]);
602 /* Morgan's algorithm is incorrect here. Blocks that evaluate
603 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
606 /* Iterate until the worklist is empty. */
611 EXECUTE_IF_SET_IN_SBITMAP (worklist
, 0, b
,
613 RESET_BIT (worklist
, b
);
614 /* For each block on the worklist, add to the IDF all
615 blocks on its dominance frontier that aren't already
616 on the IDF. Every block that's added is also added
618 sbitmap_union_of_diff (worklist
, worklist
, frontiers
[b
], idf
);
619 sbitmap_a_or_b (idf
, idf
, frontiers
[b
]);
626 sbitmap_free (worklist
);
630 fprintf (rtl_dump_file
,
631 "Iterated dominance frontier: %d passes on %d regs.\n",
636 /* Insert the phi nodes. */
639 insert_phi_node (regno
, bb
)
642 basic_block b
= BASIC_BLOCK (bb
);
650 /* Find out how many predecessors there are. */
651 for (e
= b
->pred
, npred
= 0; e
; e
= e
->pred_next
)
652 if (e
->src
!= ENTRY_BLOCK_PTR
)
655 /* If this block has no "interesting" preds, then there is nothing to
656 do. Consider a block that only has the entry block as a pred. */
660 /* This is the register to which the phi function will be assigned. */
661 reg
= regno_reg_rtx
[regno
];
663 /* Construct the arguments to the PHI node. The use of pc_rtx is just
664 a placeholder; we'll insert the proper value in rename_registers. */
665 vec
= rtvec_alloc (npred
* 2);
666 for (e
= b
->pred
, i
= 0; e
; e
= e
->pred_next
, i
+= 2)
667 if (e
->src
!= ENTRY_BLOCK_PTR
)
669 RTVEC_ELT (vec
, i
+ 0) = pc_rtx
;
670 RTVEC_ELT (vec
, i
+ 1) = GEN_INT (e
->src
->index
);
673 phi
= gen_rtx_PHI (VOIDmode
, vec
);
674 phi
= gen_rtx_SET (VOIDmode
, reg
, phi
);
676 insn
= first_insn_after_basic_block_note (b
);
677 end_p
= PREV_INSN (insn
) == b
->end
;
678 emit_insn_before (phi
, insn
);
680 b
->end
= PREV_INSN (insn
);
684 insert_phi_nodes (idfs
, evals
, nregs
)
686 sbitmap
*evals ATTRIBUTE_UNUSED
;
691 for (reg
= 0; reg
< nregs
; ++reg
)
692 if (CONVERT_REGISTER_TO_SSA_P (reg
))
695 EXECUTE_IF_SET_IN_SBITMAP (idfs
[reg
], 0, b
,
697 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, reg
))
698 insert_phi_node (reg
, b
);
703 /* Rename the registers to conform to SSA.
705 This is essentially the algorithm presented in Figure 7.8 of Morgan,
706 with a few changes to reduce pattern search time in favour of a bit
707 more memory usage. */
709 /* One of these is created for each set. It will live in a list local
710 to its basic block for the duration of that block's processing. */
711 struct rename_set_data
713 struct rename_set_data
*next
;
714 /* This is the SET_DEST of the (first) SET that sets the REG. */
716 /* This is what used to be at *REG_LOC. */
718 /* This is the REG that will replace OLD_REG. It's set only
719 when the rename data is moved onto the DONE_RENAMES queue. */
721 /* This is what to restore ssa_rename_to_lookup (old_reg) to. It is
722 usually the previous contents of ssa_rename_to_lookup (old_reg). */
724 /* This is the insn that contains all the SETs of the REG. */
728 /* This struct is used to pass information to callback functions while
729 renaming registers. */
730 struct rename_context
732 struct rename_set_data
*new_renames
;
733 struct rename_set_data
*done_renames
;
737 /* Queue the rename of *REG_LOC. */
739 create_delayed_rename (c
, reg_loc
)
740 struct rename_context
*c
;
743 struct rename_set_data
*r
;
744 r
= (struct rename_set_data
*) xmalloc (sizeof(*r
));
746 if (GET_CODE (*reg_loc
) != REG
747 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc
)))
750 r
->reg_loc
= reg_loc
;
751 r
->old_reg
= *reg_loc
;
752 r
->prev_reg
= ssa_rename_to_lookup(r
->old_reg
);
753 r
->set_insn
= c
->current_insn
;
754 r
->next
= c
->new_renames
;
758 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
759 reused. If, during processing, a register has not yet been touched,
760 ssa_rename_to[regno][machno] will be NULL. Now, in the course of pushing
761 and popping values from ssa_rename_to, when we would ordinarily
762 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
763 same as NULL, except that it signals that the original regno has
764 already been reused. */
765 #define RENAME_NO_RTX pc_rtx
767 /* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
768 applying all the renames on NEW_RENAMES. */
771 apply_delayed_renames (c
)
772 struct rename_context
*c
;
774 struct rename_set_data
*r
;
775 struct rename_set_data
*last_r
= NULL
;
777 for (r
= c
->new_renames
; r
!= NULL
; r
= r
->next
)
781 /* Failure here means that someone has a PARALLEL that sets
782 a register twice (bad!). */
783 if (ssa_rename_to_lookup (r
->old_reg
) != r
->prev_reg
)
785 /* Failure here means we have changed REG_LOC before applying
787 /* For the first set we come across, reuse the original regno. */
788 if (r
->prev_reg
== NULL_RTX
&& !HARD_REGISTER_P (r
->old_reg
))
790 r
->new_reg
= r
->old_reg
;
791 /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
792 r
->prev_reg
= RENAME_NO_RTX
;
795 r
->new_reg
= gen_reg_rtx (GET_MODE (r
->old_reg
));
796 new_regno
= REGNO (r
->new_reg
);
797 ssa_rename_to_insert (r
->old_reg
, r
->new_reg
);
799 if (new_regno
>= (int) ssa_definition
->num_elements
)
801 int new_limit
= new_regno
* 5 / 4;
802 VARRAY_GROW (ssa_definition
, new_limit
);
805 VARRAY_RTX (ssa_definition
, new_regno
) = r
->set_insn
;
806 ssa_rename_from_insert (new_regno
, r
->old_reg
);
811 last_r
->next
= c
->done_renames
;
812 c
->done_renames
= c
->new_renames
;
813 c
->new_renames
= NULL
;
817 /* Part one of the first step of rename_block, called through for_each_rtx.
818 Mark pseudos that are set for later update. Transform uses of pseudos. */
821 rename_insn_1 (ptr
, data
)
826 struct rename_context
*context
= data
;
831 switch (GET_CODE (x
))
835 rtx
*destp
= &SET_DEST (x
);
836 rtx dest
= SET_DEST (x
);
838 /* An assignment to a paradoxical SUBREG does not read from
839 the destination operand, and thus does not need to be
840 wrapped into a SEQUENCE when translating into SSA form.
841 We merely strip off the SUBREG and proceed normally for
843 if (GET_CODE (dest
) == SUBREG
844 && (GET_MODE_SIZE (GET_MODE (dest
))
845 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
846 && GET_CODE (SUBREG_REG (dest
)) == REG
847 && CONVERT_REGISTER_TO_SSA_P (REGNO (SUBREG_REG (dest
))))
849 destp
= &XEXP (dest
, 0);
850 dest
= XEXP (dest
, 0);
853 /* Some SETs also use the REG specified in their LHS.
854 These can be detected by the presence of
855 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
856 in the LHS. Handle these by changing
857 (set (subreg (reg foo)) ...)
859 (sequence [(set (reg foo_1) (reg foo))
860 (set (subreg (reg foo_1)) ...)])
862 FIXME: Much of the time this is too much. For some constructs
863 we know that the output register is strictly an output
864 (paradoxical SUBREGs and some libcalls for example).
866 For those cases we are better off not making the false
868 if (GET_CODE (dest
) == STRICT_LOW_PART
869 || GET_CODE (dest
) == SUBREG
870 || GET_CODE (dest
) == SIGN_EXTRACT
871 || GET_CODE (dest
) == ZERO_EXTRACT
)
876 while (GET_CODE (reg
) == STRICT_LOW_PART
877 || GET_CODE (reg
) == SUBREG
878 || GET_CODE (reg
) == SIGN_EXTRACT
879 || GET_CODE (reg
) == ZERO_EXTRACT
)
882 if (GET_CODE (reg
) == REG
883 && CONVERT_REGISTER_TO_SSA_P (REGNO (reg
)))
885 /* Generate (set reg reg), and do renaming on it so
886 that it becomes (set reg_1 reg_0), and we will
887 replace reg with reg_1 in the SUBREG. */
889 struct rename_set_data
*saved_new_renames
;
890 saved_new_renames
= context
->new_renames
;
891 context
->new_renames
= NULL
;
892 i
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
893 for_each_rtx (&i
, rename_insn_1
, data
);
894 apply_delayed_renames (context
);
895 context
->new_renames
= saved_new_renames
;
898 else if (GET_CODE (dest
) == REG
899 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
901 /* We found a genuine set of an interesting register. Tag
902 it so that we can create a new name for it after we finish
903 processing this insn. */
905 create_delayed_rename (context
, destp
);
907 /* Since we do not wish to (directly) traverse the
908 SET_DEST, recurse through for_each_rtx for the SET_SRC
910 if (GET_CODE (x
) == SET
)
911 for_each_rtx (&SET_SRC (x
), rename_insn_1
, data
);
915 /* Otherwise, this was not an interesting destination. Continue
916 on, marking uses as normal. */
921 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
))
922 && REGNO (x
) < ssa_max_reg_num
)
924 rtx new_reg
= ssa_rename_to_lookup (x
);
926 if (new_reg
!= RENAME_NO_RTX
)
928 if (new_reg
!= NULL_RTX
)
930 if (GET_MODE (x
) != GET_MODE (new_reg
))
936 /* Undefined value used, rename it to a new pseudo register so
937 that it cannot conflict with an existing register */
938 *ptr
= gen_reg_rtx (GET_MODE(x
));
945 /* There is considerable debate on how CLOBBERs ought to be
946 handled in SSA. For now, we're keeping the CLOBBERs, which
947 means that we don't really have SSA form. There are a couple
948 of proposals for how to fix this problem, but neither is
951 rtx dest
= XCEXP (x
, 0, CLOBBER
);
954 if (CONVERT_REGISTER_TO_SSA_P (REGNO (dest
))
955 && REGNO (dest
) < ssa_max_reg_num
)
957 rtx new_reg
= ssa_rename_to_lookup (dest
);
958 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
959 XCEXP (x
, 0, CLOBBER
) = new_reg
;
961 /* Stop traversing. */
965 /* Continue traversing. */
970 /* Never muck with the phi. We do that elsewhere, special-like. */
974 /* Anything else, continue traversing. */
982 rtx first_insn
= get_insns ();
988 /* Count the insns in the chain. */
990 for (tem
= first_insn
; tem
; tem
= NEXT_INSN (tem
))
993 result
= gen_rtx_SEQUENCE (VOIDmode
, rtvec_alloc (len
));
995 for (i
= 0, tem
= first_insn
; tem
; tem
= NEXT_INSN (tem
), i
++)
996 XVECEXP (result
, 0, i
) = tem
;
1002 rename_block (bb
, idom
)
1006 basic_block b
= BASIC_BLOCK (bb
);
1008 rtx insn
, next
, last
;
1009 struct rename_set_data
*set_data
= NULL
;
1012 /* Step One: Walk the basic block, adding new names for sets and
1022 struct rename_context context
;
1023 context
.done_renames
= set_data
;
1024 context
.new_renames
= NULL
;
1025 context
.current_insn
= insn
;
1028 for_each_rtx (&PATTERN (insn
), rename_insn_1
, &context
);
1029 for_each_rtx (®_NOTES (insn
), rename_insn_1
, &context
);
1031 /* Sometimes, we end up with a sequence of insns that
1032 SSA needs to treat as a single insn. Wrap these in a
1033 SEQUENCE. (Any notes now get attached to the SEQUENCE,
1034 not to the old version inner insn.) */
1035 if (get_insns () != NULL_RTX
)
1040 emit (PATTERN (insn
));
1041 seq
= gen_sequence ();
1042 /* We really want a SEQUENCE of SETs, not a SEQUENCE
1044 for (i
= 0; i
< XVECLEN (seq
, 0); i
++)
1045 XVECEXP (seq
, 0, i
) = PATTERN (XVECEXP (seq
, 0, i
));
1046 PATTERN (insn
) = seq
;
1050 apply_delayed_renames (&context
);
1051 set_data
= context
.done_renames
;
1054 next
= NEXT_INSN (insn
);
1056 while (insn
!= last
);
1058 /* Step Two: Update the phi nodes of this block's successors. */
1060 for (e
= b
->succ
; e
; e
= e
->succ_next
)
1062 if (e
->dest
== EXIT_BLOCK_PTR
)
1065 insn
= first_insn_after_basic_block_note (e
->dest
);
1067 while (PHI_NODE_P (insn
))
1069 rtx phi
= PATTERN (insn
);
1072 /* Find out which of our outgoing registers this node is
1073 intended to replace. Note that if this is not the first PHI
1074 node to have been created for this register, we have to
1075 jump through rename links to figure out which register
1076 we're talking about. This can easily be recognized by
1077 noting that the regno is new to this pass. */
1078 reg
= SET_DEST (phi
);
1079 if (REGNO (reg
) >= ssa_max_reg_num
)
1080 reg
= ssa_rename_from_lookup (REGNO (reg
));
1081 if (reg
== NULL_RTX
)
1083 reg
= ssa_rename_to_lookup (reg
);
1085 /* It is possible for the variable to be uninitialized on
1086 edges in. Reduce the arity of the PHI so that we don't
1087 consider those edges. */
1088 if (reg
== NULL
|| reg
== RENAME_NO_RTX
)
1090 if (! remove_phi_alternative (phi
, b
))
1095 /* When we created the PHI nodes, we did not know what mode
1096 the register should be. Now that we've found an original,
1097 we can fill that in. */
1098 if (GET_MODE (SET_DEST (phi
)) == VOIDmode
)
1099 PUT_MODE (SET_DEST (phi
), GET_MODE (reg
));
1100 else if (GET_MODE (SET_DEST (phi
)) != GET_MODE (reg
))
1103 *phi_alternative (phi
, bb
) = reg
;
1106 insn
= NEXT_INSN (insn
);
1110 /* Step Three: Do the same to the children of this block in
1114 if (idom
[c
->index
] == bb
)
1115 rename_block (c
->index
, idom
);
1117 /* Step Four: Update the sets to refer to their new register,
1118 and restore ssa_rename_to to its previous state. */
1122 struct rename_set_data
*next
;
1123 rtx old_reg
= *set_data
->reg_loc
;
1125 if (*set_data
->reg_loc
!= set_data
->old_reg
)
1127 *set_data
->reg_loc
= set_data
->new_reg
;
1129 ssa_rename_to_insert (old_reg
, set_data
->prev_reg
);
1131 next
= set_data
->next
;
1138 rename_registers (nregs
, idom
)
1142 VARRAY_RTX_INIT (ssa_definition
, nregs
* 3, "ssa_definition");
1143 ssa_rename_from_initialize ();
1145 ssa_rename_to_pseudo
= (rtx
*) alloca (nregs
* sizeof(rtx
));
1146 memset ((char *) ssa_rename_to_pseudo
, 0, nregs
* sizeof(rtx
));
1147 memset ((char *) ssa_rename_to_hard
, 0,
1148 FIRST_PSEUDO_REGISTER
* NUM_MACHINE_MODES
* sizeof (rtx
));
1150 rename_block (0, idom
);
1152 /* ??? Update basic_block_live_at_start, and other flow info
1155 ssa_rename_to_pseudo
= NULL
;
1158 /* The main entry point for moving to SSA. */
1163 /* Element I is the set of blocks that set register I. */
1166 /* Dominator bitmaps. */
1170 /* Element I is the immediate dominator of block I. */
1177 /* Don't do it twice. */
1181 /* Need global_live_at_{start,end} up to date. Do not remove any
1182 dead code. We'll let the SSA optimizers do that. */
1183 life_analysis (get_insns (), NULL
, 0);
1185 idom
= (int *) alloca (last_basic_block
* sizeof (int));
1186 memset ((void *) idom
, -1, (size_t) last_basic_block
* sizeof (int));
1187 calculate_dominance_info (idom
, NULL
, CDI_DOMINATORS
);
1191 fputs (";; Immediate Dominators:\n", rtl_dump_file
);
1193 fprintf (rtl_dump_file
, ";\t%3d = %3d\n", bb
->index
, idom
[bb
->index
]);
1194 fflush (rtl_dump_file
);
1197 /* Compute dominance frontiers. */
1199 dfs
= sbitmap_vector_alloc (last_basic_block
, last_basic_block
);
1200 compute_dominance_frontiers (dfs
, idom
);
1204 dump_sbitmap_vector (rtl_dump_file
, ";; Dominance Frontiers:",
1205 "; Basic Block", dfs
, last_basic_block
);
1206 fflush (rtl_dump_file
);
1209 /* Compute register evaluations. */
1211 ssa_max_reg_num
= max_reg_num ();
1212 nregs
= ssa_max_reg_num
;
1213 evals
= sbitmap_vector_alloc (nregs
, last_basic_block
);
1214 find_evaluations (evals
, nregs
);
1216 /* Compute the iterated dominance frontier for each register. */
1218 idfs
= sbitmap_vector_alloc (nregs
, last_basic_block
);
1219 compute_iterated_dominance_frontiers (idfs
, dfs
, evals
, nregs
);
1223 dump_sbitmap_vector (rtl_dump_file
, ";; Iterated Dominance Frontiers:",
1224 "; Register", idfs
, nregs
);
1225 fflush (rtl_dump_file
);
1228 /* Insert the phi nodes. */
1230 insert_phi_nodes (idfs
, evals
, nregs
);
1232 /* Rename the registers to satisfy SSA. */
1234 rename_registers (nregs
, idom
);
1236 /* All done! Clean up and go home. */
1238 sbitmap_vector_free (dfs
);
1239 sbitmap_vector_free (evals
);
1240 sbitmap_vector_free (idfs
);
1243 reg_scan (get_insns (), max_reg_num (), 1);
1246 /* REG is the representative temporary of its partition. Add it to the
1247 set of nodes to be processed, if it hasn't been already. Return the
1248 index of this register in the node set. */
1251 ephi_add_node (reg
, nodes
, n_nodes
)
1256 for (i
= *n_nodes
- 1; i
>= 0; --i
)
1257 if (REGNO (reg
) == REGNO (nodes
[i
]))
1260 nodes
[i
= (*n_nodes
)++] = reg
;
1264 /* Part one of the topological sort. This is a forward (downward) search
1265 through the graph collecting a stack of nodes to process. Assuming no
1266 cycles, the nodes at top of the stack when we are finished will have
1267 no other dependencies. */
1270 ephi_forward (t
, visited
, succ
, tstack
)
1278 SET_BIT (visited
, t
);
1280 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1282 if (! TEST_BIT (visited
, s
))
1283 tstack
= ephi_forward (s
, visited
, succ
, tstack
);
1290 /* Part two of the topological sort. The is a backward search through
1291 a cycle in the graph, copying the data forward as we go. */
1294 ephi_backward (t
, visited
, pred
, nodes
)
1296 sbitmap visited
, *pred
;
1301 SET_BIT (visited
, t
);
1303 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1305 if (! TEST_BIT (visited
, p
))
1307 ephi_backward (p
, visited
, pred
, nodes
);
1308 emit_move_insn (nodes
[p
], nodes
[t
]);
1313 /* Part two of the topological sort. Create the copy for a register
1314 and any cycle of which it is a member. */
1317 ephi_create (t
, visited
, pred
, succ
, nodes
)
1319 sbitmap visited
, *pred
, *succ
;
1322 rtx reg_u
= NULL_RTX
;
1323 int unvisited_predecessors
= 0;
1326 /* Iterate through the predecessor list looking for unvisited nodes.
1327 If there are any, we have a cycle, and must deal with that. At
1328 the same time, look for a visited predecessor. If there is one,
1329 we won't need to create a temporary. */
1331 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1333 if (! TEST_BIT (visited
, p
))
1334 unvisited_predecessors
= 1;
1339 if (unvisited_predecessors
)
1341 /* We found a cycle. Copy out one element of the ring (if necessary),
1342 then traverse the ring copying as we go. */
1346 reg_u
= gen_reg_rtx (GET_MODE (nodes
[t
]));
1347 emit_move_insn (reg_u
, nodes
[t
]);
1350 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1352 if (! TEST_BIT (visited
, p
))
1354 ephi_backward (p
, visited
, pred
, nodes
);
1355 emit_move_insn (nodes
[p
], reg_u
);
1361 /* No cycle. Just copy the value from a successor. */
1364 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1366 SET_BIT (visited
, t
);
1367 emit_move_insn (nodes
[t
], nodes
[s
]);
1373 /* Convert the edge to normal form. */
1376 eliminate_phi (e
, reg_partition
)
1378 partition reg_partition
;
1381 sbitmap
*pred
, *succ
;
1384 int *stack
, *tstack
;
1388 /* Collect an upper bound on the number of registers needing processing. */
1390 insn
= first_insn_after_basic_block_note (e
->dest
);
1393 while (PHI_NODE_P (insn
))
1395 insn
= next_nonnote_insn (insn
);
1402 /* Build the auxiliary graph R(B).
1404 The nodes of the graph are the members of the register partition
1405 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1406 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1408 nodes
= (rtx
*) alloca (n_nodes
* sizeof(rtx
));
1409 pred
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1410 succ
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1411 sbitmap_vector_zero (pred
, n_nodes
);
1412 sbitmap_vector_zero (succ
, n_nodes
);
1414 insn
= first_insn_after_basic_block_note (e
->dest
);
1417 for (; PHI_NODE_P (insn
); insn
= next_nonnote_insn (insn
))
1419 rtx
* preg
= phi_alternative (PATTERN (insn
), e
->src
->index
);
1420 rtx tgt
= SET_DEST (PATTERN (insn
));
1423 /* There may be no phi alternative corresponding to this edge.
1424 This indicates that the phi variable is undefined along this
1430 if (GET_CODE (reg
) != REG
|| GET_CODE (tgt
) != REG
)
1433 reg
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (reg
))];
1434 tgt
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (tgt
))];
1435 /* If the two registers are already in the same partition,
1436 nothing will need to be done. */
1441 ireg
= ephi_add_node (reg
, nodes
, &n_nodes
);
1442 itgt
= ephi_add_node (tgt
, nodes
, &n_nodes
);
1444 SET_BIT (pred
[ireg
], itgt
);
1445 SET_BIT (succ
[itgt
], ireg
);
1452 /* Begin a topological sort of the graph. */
1454 visited
= sbitmap_alloc (n_nodes
);
1455 sbitmap_zero (visited
);
1457 tstack
= stack
= (int *) alloca (n_nodes
* sizeof (int));
1459 for (i
= 0; i
< n_nodes
; ++i
)
1460 if (! TEST_BIT (visited
, i
))
1461 tstack
= ephi_forward (i
, visited
, succ
, tstack
);
1463 sbitmap_zero (visited
);
1465 /* As we find a solution to the tsort, collect the implementation
1466 insns in a sequence. */
1469 while (tstack
!= stack
)
1472 if (! TEST_BIT (visited
, i
))
1473 ephi_create (i
, visited
, pred
, succ
, nodes
);
1476 insn
= get_insns ();
1478 insert_insn_on_edge (insn
, e
);
1480 fprintf (rtl_dump_file
, "Emitting copy on edge (%d,%d)\n",
1481 e
->src
->index
, e
->dest
->index
);
1483 sbitmap_free (visited
);
1485 sbitmap_vector_free (pred
);
1486 sbitmap_vector_free (succ
);
1489 /* For basic block B, consider all phi insns which provide an
1490 alternative corresponding to an incoming abnormal critical edge.
1491 Place the phi alternative corresponding to that abnormal critical
1492 edge in the same register class as the destination of the set.
1494 From Morgan, p. 178:
1496 For each abnormal critical edge (C, B),
1497 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1498 and C is the ith predecessor of B,
1499 then T0 and Ti must be equivalent.
1501 Return non-zero iff any such cases were found for which the two
1502 regs were not already in the same class. */
1505 make_regs_equivalent_over_bad_edges (bb
, reg_partition
)
1507 partition reg_partition
;
1510 basic_block b
= BASIC_BLOCK (bb
);
1513 /* Advance to the first phi node. */
1514 phi
= first_insn_after_basic_block_note (b
);
1516 /* Scan all the phi nodes. */
1519 phi
= next_nonnote_insn (phi
))
1523 rtx set
= PATTERN (phi
);
1524 rtx tgt
= SET_DEST (set
);
1526 /* The set target is expected to be an SSA register. */
1527 if (GET_CODE (tgt
) != REG
1528 || !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt
)))
1530 tgt_regno
= REGNO (tgt
);
1532 /* Scan incoming abnormal critical edges. */
1533 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1534 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1536 rtx
*alt
= phi_alternative (set
, e
->src
->index
);
1539 /* If there is no alternative corresponding to this edge,
1540 the value is undefined along the edge, so just go on. */
1544 /* The phi alternative is expected to be an SSA register. */
1545 if (GET_CODE (*alt
) != REG
1546 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1548 alt_regno
= REGNO (*alt
);
1550 /* If the set destination and the phi alternative aren't
1551 already in the same class... */
1552 if (partition_find (reg_partition
, tgt_regno
)
1553 != partition_find (reg_partition
, alt_regno
))
1555 /* ... make them such. */
1556 if (conflicting_hard_regs_p (tgt_regno
, alt_regno
))
1557 /* It is illegal to unify a hard register with a
1558 different register. */
1561 partition_union (reg_partition
,
1562 tgt_regno
, alt_regno
);
1571 /* Consider phi insns in basic block BB pairwise. If the set target
1572 of both isns are equivalent pseudos, make the corresponding phi
1573 alternatives in each phi corresponding equivalent.
1575 Return nonzero if any new register classes were unioned. */
1578 make_equivalent_phi_alternatives_equivalent (bb
, reg_partition
)
1580 partition reg_partition
;
1583 basic_block b
= BASIC_BLOCK (bb
);
1586 /* Advance to the first phi node. */
1587 phi
= first_insn_after_basic_block_note (b
);
1589 /* Scan all the phi nodes. */
1592 phi
= next_nonnote_insn (phi
))
1594 rtx set
= PATTERN (phi
);
1595 /* The regno of the destination of the set. */
1596 int tgt_regno
= REGNO (SET_DEST (PATTERN (phi
)));
1598 rtx phi2
= next_nonnote_insn (phi
);
1600 /* Scan all phi nodes following this one. */
1603 phi2
= next_nonnote_insn (phi2
))
1605 rtx set2
= PATTERN (phi2
);
1606 /* The regno of the destination of the set. */
1607 int tgt2_regno
= REGNO (SET_DEST (set2
));
1609 /* Are the set destinations equivalent regs? */
1610 if (partition_find (reg_partition
, tgt_regno
) ==
1611 partition_find (reg_partition
, tgt2_regno
))
1614 /* Scan over edges. */
1615 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1617 int pred_block
= e
->src
->index
;
1618 /* Identify the phi alternatives from both phi
1619 nodes corresponding to this edge. */
1620 rtx
*alt
= phi_alternative (set
, pred_block
);
1621 rtx
*alt2
= phi_alternative (set2
, pred_block
);
1623 /* If one of the phi nodes doesn't have a
1624 corresponding alternative, just skip it. */
1625 if (alt
== 0 || alt2
== 0)
1628 /* Both alternatives should be SSA registers. */
1629 if (GET_CODE (*alt
) != REG
1630 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1632 if (GET_CODE (*alt2
) != REG
1633 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2
)))
1636 /* If the alternatives aren't already in the same
1638 if (partition_find (reg_partition
, REGNO (*alt
))
1639 != partition_find (reg_partition
, REGNO (*alt2
)))
1641 /* ... make them so. */
1642 if (conflicting_hard_regs_p (REGNO (*alt
), REGNO (*alt2
)))
1643 /* It is illegal to unify a hard register with
1644 a different register. */
1647 partition_union (reg_partition
,
1648 REGNO (*alt
), REGNO (*alt2
));
1659 /* Compute a conservative partition of outstanding pseudo registers.
1660 See Morgan 7.3.1. */
1663 compute_conservative_reg_partition ()
1668 /* We don't actually work with hard registers, but it's easier to
1669 carry them around anyway rather than constantly doing register
1670 number arithmetic. */
1672 partition_new (ssa_definition
->num_elements
);
1674 /* The first priority is to make sure registers that might have to
1675 be copied on abnormal critical edges are placed in the same
1676 partition. This saves us from having to split abnormal critical
1678 FOR_EACH_BB_REVERSE (bb
)
1679 changed
+= make_regs_equivalent_over_bad_edges (bb
->index
, p
);
1681 /* Now we have to insure that corresponding arguments of phi nodes
1682 assigning to corresponding regs are equivalent. Iterate until
1687 FOR_EACH_BB_REVERSE (bb
)
1688 changed
+= make_equivalent_phi_alternatives_equivalent (bb
->index
, p
);
1694 /* The following functions compute a register partition that attempts
1695 to eliminate as many reg copies and phi node copies as possible by
1696 coalescing registers. This is the strategy:
1698 1. As in the conservative case, the top priority is to coalesce
1699 registers that otherwise would cause copies to be placed on
1700 abnormal critical edges (which isn't possible).
1702 2. Figure out which regs are involved (in the LHS or RHS) of
1703 copies and phi nodes. Compute conflicts among these regs.
1705 3. Walk around the instruction stream, placing two regs in the
1706 same class of the partition if one appears on the LHS and the
1707 other on the RHS of a copy or phi node and the two regs don't
1708 conflict. The conflict information of course needs to be
1711 4. If anything has changed, there may be new opportunities to
1712 coalesce regs, so go back to 2.
1715 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1716 same class of partition P, if they aren't already. Update
1717 CONFLICTS appropriately.
1719 Returns one if REG1 and REG2 were placed in the same class but were
1720 not previously; zero otherwise.
1722 See Morgan figure 11.15. */
1725 coalesce_if_unconflicting (p
, conflicts
, reg1
, reg2
)
1727 conflict_graph conflicts
;
1733 /* Work only on SSA registers. */
1734 if (!CONVERT_REGISTER_TO_SSA_P (reg1
) || !CONVERT_REGISTER_TO_SSA_P (reg2
))
1737 /* Find the canonical regs for the classes containing REG1 and
1739 reg1
= partition_find (p
, reg1
);
1740 reg2
= partition_find (p
, reg2
);
1742 /* If they're already in the same class, there's nothing to do. */
1746 /* If the regs conflict, our hands are tied. */
1747 if (conflicting_hard_regs_p (reg1
, reg2
) ||
1748 conflict_graph_conflict_p (conflicts
, reg1
, reg2
))
1751 /* We're good to go. Put the regs in the same partition. */
1752 partition_union (p
, reg1
, reg2
);
1754 /* Find the new canonical reg for the merged class. */
1755 reg
= partition_find (p
, reg1
);
1757 /* Merge conflicts from the two previous classes. */
1758 conflict_graph_merge_regs (conflicts
, reg
, reg1
);
1759 conflict_graph_merge_regs (conflicts
, reg
, reg2
);
1764 /* For each register copy insn in basic block BB, place the LHS and
1765 RHS regs in the same class in partition P if they do not conflict
1766 according to CONFLICTS.
1768 Returns the number of changes that were made to P.
1770 See Morgan figure 11.14. */
1773 coalesce_regs_in_copies (bb
, p
, conflicts
)
1776 conflict_graph conflicts
;
1782 /* Scan the instruction stream of the block. */
1783 for (insn
= bb
->head
; insn
!= end
; insn
= NEXT_INSN (insn
))
1789 /* If this isn't a set insn, go to the next insn. */
1790 if (GET_CODE (insn
) != INSN
)
1792 pattern
= PATTERN (insn
);
1793 if (GET_CODE (pattern
) != SET
)
1796 src
= SET_SRC (pattern
);
1797 dest
= SET_DEST (pattern
);
1799 /* We're only looking for copies. */
1800 if (GET_CODE (src
) != REG
|| GET_CODE (dest
) != REG
)
1803 /* Coalesce only if the reg modes are the same. As long as
1804 each reg's rtx is unique, it can have only one mode, so two
1805 pseudos of different modes can't be coalesced into one.
1807 FIXME: We can probably get around this by inserting SUBREGs
1808 where appropriate, but for now we don't bother. */
1809 if (GET_MODE (src
) != GET_MODE (dest
))
1812 /* Found a copy; see if we can use the same reg for both the
1813 source and destination (and thus eliminate the copy,
1815 changed
+= coalesce_if_unconflicting (p
, conflicts
,
1816 REGNO (src
), REGNO (dest
));
1822 struct phi_coalesce_context
1825 conflict_graph conflicts
;
1829 /* Callback function for for_each_successor_phi. If the set
1830 destination and the phi alternative regs do not conflict, place
1831 them in the same paritition class. DATA is a pointer to a
1832 phi_coalesce_context struct. */
1835 coalesce_reg_in_phi (insn
, dest_regno
, src_regno
, data
)
1836 rtx insn ATTRIBUTE_UNUSED
;
1841 struct phi_coalesce_context
*context
=
1842 (struct phi_coalesce_context
*) data
;
1844 /* Attempt to use the same reg, if they don't conflict. */
1846 += coalesce_if_unconflicting (context
->p
, context
->conflicts
,
1847 dest_regno
, src_regno
);
1851 /* For each alternative in a phi function corresponding to basic block
1852 BB (in phi nodes in successor block to BB), place the reg in the
1853 phi alternative and the reg to which the phi value is set into the
1854 same class in partition P, if allowed by CONFLICTS.
1856 Return the number of changes that were made to P.
1858 See Morgan figure 11.14. */
1861 coalesce_regs_in_successor_phi_nodes (bb
, p
, conflicts
)
1864 conflict_graph conflicts
;
1866 struct phi_coalesce_context context
;
1868 context
.conflicts
= conflicts
;
1869 context
.changed
= 0;
1871 for_each_successor_phi (bb
, &coalesce_reg_in_phi
, &context
);
1873 return context
.changed
;
1876 /* Compute and return a partition of pseudos. Where possible,
1877 non-conflicting pseudos are placed in the same class.
1879 The caller is responsible for deallocating the returned partition. */
1882 compute_coalesced_reg_partition ()
1886 regset_head phi_set_head
;
1887 regset phi_set
= &phi_set_head
;
1890 partition_new (ssa_definition
->num_elements
);
1892 /* The first priority is to make sure registers that might have to
1893 be copied on abnormal critical edges are placed in the same
1894 partition. This saves us from having to split abnormal critical
1895 edges (which can't be done). */
1896 FOR_EACH_BB_REVERSE (bb
)
1897 make_regs_equivalent_over_bad_edges (bb
->index
, p
);
1899 INIT_REG_SET (phi_set
);
1903 conflict_graph conflicts
;
1907 /* Build the set of registers involved in phi nodes, either as
1908 arguments to the phi function or as the target of a set. */
1909 CLEAR_REG_SET (phi_set
);
1910 mark_phi_and_copy_regs (phi_set
);
1912 /* Compute conflicts. */
1913 conflicts
= conflict_graph_compute (phi_set
, p
);
1915 /* FIXME: Better would be to process most frequently executed
1916 blocks first, so that most frequently executed copies would
1917 be more likely to be removed by register coalescing. But any
1918 order will generate correct, if non-optimal, results. */
1919 FOR_EACH_BB_REVERSE (bb
)
1921 changed
+= coalesce_regs_in_copies (bb
, p
, conflicts
);
1923 coalesce_regs_in_successor_phi_nodes (bb
, p
, conflicts
);
1926 conflict_graph_delete (conflicts
);
1928 while (changed
> 0);
1930 FREE_REG_SET (phi_set
);
1935 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1936 components (a REG or a CONST_INT). DATA is a reg set in which to
1937 set all regs. Called from for_each_rtx. */
1940 mark_reg_in_phi (ptr
, data
)
1945 regset set
= (regset
) data
;
1947 switch (GET_CODE (expr
))
1950 SET_REGNO_REG_SET (set
, REGNO (expr
));
1960 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1961 set from a phi expression, or used as an argument in one. Also
1962 mark regs that are the source or target of a reg copy. Uses
1966 mark_phi_and_copy_regs (phi_set
)
1971 /* Scan the definitions of all regs. */
1972 for (reg
= 0; reg
< VARRAY_SIZE (ssa_definition
); ++reg
)
1973 if (CONVERT_REGISTER_TO_SSA_P (reg
))
1975 rtx insn
= VARRAY_RTX (ssa_definition
, reg
);
1980 || (GET_CODE (insn
) == NOTE
1981 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
))
1983 pattern
= PATTERN (insn
);
1984 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1986 if (GET_CODE (pattern
) != SET
)
1988 src
= SET_SRC (pattern
);
1990 if (GET_CODE (src
) == REG
)
1992 /* It's a reg copy. */
1993 SET_REGNO_REG_SET (phi_set
, reg
);
1994 SET_REGNO_REG_SET (phi_set
, REGNO (src
));
1996 else if (GET_CODE (src
) == PHI
)
1998 /* It's a phi node. Mark the reg being set. */
1999 SET_REGNO_REG_SET (phi_set
, reg
);
2000 /* Mark the regs used in the phi function. */
2001 for_each_rtx (&src
, mark_reg_in_phi
, phi_set
);
2003 /* ... else nothing to do. */
2007 /* Rename regs in insn PTR that are equivalent. DATA is the register
2008 partition which specifies equivalences. */
2011 rename_equivalent_regs_in_insn (ptr
, data
)
2016 partition reg_partition
= (partition
) data
;
2021 switch (GET_CODE (x
))
2024 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)))
2026 unsigned int regno
= REGNO (x
);
2027 unsigned int new_regno
= partition_find (reg_partition
, regno
);
2028 rtx canonical_element_rtx
= ssa_rename_from_lookup (new_regno
);
2030 if (canonical_element_rtx
!= NULL_RTX
&&
2031 HARD_REGISTER_P (canonical_element_rtx
))
2033 if (REGNO (canonical_element_rtx
) != regno
)
2034 *ptr
= canonical_element_rtx
;
2036 else if (regno
!= new_regno
)
2038 rtx new_reg
= regno_reg_rtx
[new_regno
];
2039 if (GET_MODE (x
) != GET_MODE (new_reg
))
2047 /* No need to rename the phi nodes. We'll check equivalence
2048 when inserting copies. */
2052 /* Anything else, continue traversing. */
2057 /* Record the register's canonical element stored in SRFP in the
2058 canonical_elements sbitmap packaged in DATA. This function is used
2059 as a callback function for traversing ssa_rename_from. */
2062 record_canonical_element_1 (srfp
, data
)
2066 unsigned int reg
= ((ssa_rename_from_pair
*) *srfp
)->reg
;
2067 sbitmap canonical_elements
=
2068 ((struct ssa_rename_from_hash_table_data
*) data
)->canonical_elements
;
2069 partition reg_partition
=
2070 ((struct ssa_rename_from_hash_table_data
*) data
)->reg_partition
;
2072 SET_BIT (canonical_elements
, partition_find (reg_partition
, reg
));
2076 /* For each class in the REG_PARTITION corresponding to a particular
2077 hard register and machine mode, check that there are no other
2078 classes with the same hard register and machine mode. Returns
2079 nonzero if this is the case, i.e., the partition is acceptable. */
2082 check_hard_regs_in_partition (reg_partition
)
2083 partition reg_partition
;
2085 /* CANONICAL_ELEMENTS has a nonzero bit if a class with the given register
2086 number and machine mode has already been seen. This is a
2087 problem with the partition. */
2088 sbitmap canonical_elements
;
2090 int already_seen
[FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
2094 /* Collect a list of canonical elements. */
2095 canonical_elements
= sbitmap_alloc (max_reg_num ());
2096 sbitmap_zero (canonical_elements
);
2097 ssa_rename_from_traverse (&record_canonical_element_1
,
2098 canonical_elements
, reg_partition
);
2100 /* We have not seen any hard register uses. */
2101 for (reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; ++reg
)
2102 for (mach_mode
= 0; mach_mode
< NUM_MACHINE_MODES
; ++mach_mode
)
2103 already_seen
[reg
][mach_mode
] = 0;
2105 /* Check for classes with the same hard register and machine mode. */
2106 EXECUTE_IF_SET_IN_SBITMAP (canonical_elements
, 0, element_index
,
2108 rtx hard_reg_rtx
= ssa_rename_from_lookup (element_index
);
2109 if (hard_reg_rtx
!= NULL_RTX
&&
2110 HARD_REGISTER_P (hard_reg_rtx
) &&
2111 already_seen
[REGNO (hard_reg_rtx
)][GET_MODE (hard_reg_rtx
)] != 0)
2112 /* Two distinct partition classes should be mapped to the same
2117 sbitmap_free (canonical_elements
);
2122 /* Rename regs that are equivalent in REG_PARTITION. Also collapse
2123 any SEQUENCE insns. */
2126 rename_equivalent_regs (reg_partition
)
2127 partition reg_partition
;
2131 FOR_EACH_BB_REVERSE (b
)
2142 for_each_rtx (&PATTERN (insn
),
2143 rename_equivalent_regs_in_insn
,
2145 for_each_rtx (®_NOTES (insn
),
2146 rename_equivalent_regs_in_insn
,
2149 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
2151 rtx s
= PATTERN (insn
);
2152 int slen
= XVECLEN (s
, 0);
2158 PATTERN (insn
) = XVECEXP (s
, 0, slen
-1);
2159 for (i
= 0; i
< slen
- 1; i
++)
2160 emit_insn_before (XVECEXP (s
, 0, i
), insn
);
2164 next
= NEXT_INSN (insn
);
2166 while (insn
!= last
);
2170 /* The main entry point for moving from SSA. */
2176 partition reg_partition
;
2177 rtx insns
= get_insns ();
2179 /* Need global_live_at_{start,end} up to date. There should not be
2180 any significant dead code at this point, except perhaps dead
2181 stores. So do not take the time to perform dead code elimination.
2183 Register coalescing needs death notes, so generate them. */
2184 life_analysis (insns
, NULL
, PROP_DEATH_NOTES
);
2186 /* Figure out which regs in copies and phi nodes don't conflict and
2187 therefore can be coalesced. */
2188 if (conservative_reg_partition
)
2189 reg_partition
= compute_conservative_reg_partition ();
2191 reg_partition
= compute_coalesced_reg_partition ();
2193 if (!check_hard_regs_in_partition (reg_partition
))
2194 /* Two separate partitions should correspond to the same hard
2195 register but do not. */
2198 rename_equivalent_regs (reg_partition
);
2200 /* Eliminate the PHI nodes. */
2201 FOR_EACH_BB_REVERSE (b
)
2205 for (e
= b
->pred
; e
; e
= e
->pred_next
)
2206 if (e
->src
!= ENTRY_BLOCK_PTR
)
2207 eliminate_phi (e
, reg_partition
);
2210 partition_delete (reg_partition
);
2212 /* Actually delete the PHI nodes. */
2213 FOR_EACH_BB_REVERSE (bb
)
2215 rtx insn
= bb
->head
;
2219 /* If this is a PHI node delete it. */
2220 if (PHI_NODE_P (insn
))
2222 if (insn
== bb
->end
)
2223 bb
->end
= PREV_INSN (insn
);
2224 insn
= delete_insn (insn
);
2226 /* Since all the phi nodes come at the beginning of the
2227 block, if we find an ordinary insn, we can stop looking
2228 for more phi nodes. */
2229 else if (INSN_P (insn
))
2231 /* If we've reached the end of the block, stop. */
2232 else if (insn
== bb
->end
)
2235 insn
= NEXT_INSN (insn
);
2239 /* Commit all the copy nodes needed to convert out of SSA form. */
2240 commit_edge_insertions ();
2244 count_or_remove_death_notes (NULL
, 1);
2246 /* Deallocate the data structures. */
2248 ssa_rename_from_free ();
2251 /* Scan phi nodes in successors to BB. For each such phi node that
2252 has a phi alternative value corresponding to BB, invoke FN. FN
2253 is passed the entire phi node insn, the regno of the set
2254 destination, the regno of the phi argument corresponding to BB,
2257 If FN ever returns non-zero, stops immediately and returns this
2258 value. Otherwise, returns zero. */
2261 for_each_successor_phi (bb
, fn
, data
)
2263 successor_phi_fn fn
;
2268 if (bb
== EXIT_BLOCK_PTR
)
2271 /* Scan outgoing edges. */
2272 for (e
= bb
->succ
; e
!= NULL
; e
= e
->succ_next
)
2276 basic_block successor
= e
->dest
;
2277 if (successor
== ENTRY_BLOCK_PTR
2278 || successor
== EXIT_BLOCK_PTR
)
2281 /* Advance to the first non-label insn of the successor block. */
2282 insn
= first_insn_after_basic_block_note (successor
);
2287 /* Scan phi nodes in the successor. */
2288 for ( ; PHI_NODE_P (insn
); insn
= NEXT_INSN (insn
))
2291 rtx phi_set
= PATTERN (insn
);
2292 rtx
*alternative
= phi_alternative (phi_set
, bb
->index
);
2295 /* This phi function may not have an alternative
2296 corresponding to the incoming edge, indicating the
2297 assigned variable is not defined along the edge. */
2298 if (alternative
== NULL
)
2300 phi_src
= *alternative
;
2302 /* Invoke the callback. */
2303 result
= (*fn
) (insn
, REGNO (SET_DEST (phi_set
)),
2304 REGNO (phi_src
), data
);
2306 /* Terminate if requested. */
2315 /* Assuming the ssa_rename_from mapping has been established, yields
2316 nonzero if 1) only one SSA register of REG1 and REG2 comes from a
2317 hard register or 2) both SSA registers REG1 and REG2 come from
2318 different hard registers. */
2321 conflicting_hard_regs_p (reg1
, reg2
)
2325 int orig_reg1
= original_register (reg1
);
2326 int orig_reg2
= original_register (reg2
);
2327 if (HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
)
2328 && orig_reg1
!= orig_reg2
)
2330 if (HARD_REGISTER_NUM_P (orig_reg1
) && !HARD_REGISTER_NUM_P (orig_reg2
))
2332 if (!HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
))