1 /* Static Single Assignment conversion routines for the GNU compiler.
2 Copyright (C) 2000, 2001 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 "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 void ssa_rename_from_initialize
129 static rtx ssa_rename_from_lookup
131 static unsigned int original_register
132 PARAMS ((unsigned int regno
));
133 static void ssa_rename_from_insert
134 PARAMS ((unsigned int reg
, rtx r
));
135 static void ssa_rename_from_free
137 typedef int (*srf_trav
) PARAMS ((int regno
, rtx r
, sbitmap canonical_elements
, partition reg_partition
));
138 static void ssa_rename_from_traverse
139 PARAMS ((htab_trav callback_function
, sbitmap canonical_elements
, partition reg_partition
));
140 /*static Avoid warnign message. */ void ssa_rename_from_print
142 static int ssa_rename_from_print_1
143 PARAMS ((void **slot
, void *data
));
144 static hashval_t ssa_rename_from_hash_function
145 PARAMS ((const void * srfp
));
146 static int ssa_rename_from_equal
147 PARAMS ((const void *srfp1
, const void *srfp2
));
148 static void ssa_rename_from_delete
149 PARAMS ((void *srfp
));
151 static rtx ssa_rename_to_lookup
153 static void ssa_rename_to_insert
154 PARAMS ((rtx reg
, rtx r
));
156 /* The number of registers that were live on entry to the SSA routines. */
157 static unsigned int ssa_max_reg_num
;
159 /* Local function prototypes. */
161 struct rename_context
;
163 static inline rtx
* phi_alternative
165 static rtx first_insn_after_basic_block_note
166 PARAMS ((basic_block
));
167 static void compute_dominance_frontiers_1
168 PARAMS ((sbitmap
*frontiers
, int *idom
, int bb
, sbitmap done
));
169 static void compute_dominance_frontiers
170 PARAMS ((sbitmap
*frontiers
, int *idom
));
171 static void find_evaluations_1
172 PARAMS ((rtx dest
, rtx set
, void *data
));
173 static void find_evaluations
174 PARAMS ((sbitmap
*evals
, int nregs
));
175 static void compute_iterated_dominance_frontiers
176 PARAMS ((sbitmap
*idfs
, sbitmap
*frontiers
, sbitmap
*evals
, int nregs
));
177 static void insert_phi_node
178 PARAMS ((int regno
, int b
));
179 static void insert_phi_nodes
180 PARAMS ((sbitmap
*idfs
, sbitmap
*evals
, int nregs
));
181 static void create_delayed_rename
182 PARAMS ((struct rename_context
*, rtx
*));
183 static void apply_delayed_renames
184 PARAMS ((struct rename_context
*));
185 static int rename_insn_1
186 PARAMS ((rtx
*ptr
, void *data
));
187 static void rename_block
188 PARAMS ((int b
, int *idom
));
189 static void rename_registers
190 PARAMS ((int nregs
, int *idom
));
192 static inline int ephi_add_node
193 PARAMS ((rtx reg
, rtx
*nodes
, int *n_nodes
));
194 static int * ephi_forward
195 PARAMS ((int t
, sbitmap visited
, sbitmap
*succ
, int *tstack
));
196 static void ephi_backward
197 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, rtx
*nodes
));
198 static void ephi_create
199 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, sbitmap
*succ
, rtx
*nodes
));
200 static void eliminate_phi
201 PARAMS ((edge e
, partition reg_partition
));
202 static int make_regs_equivalent_over_bad_edges
203 PARAMS ((int bb
, partition reg_partition
));
205 /* These are used only in the conservative register partitioning
207 static int make_equivalent_phi_alternatives_equivalent
208 PARAMS ((int bb
, partition reg_partition
));
209 static partition compute_conservative_reg_partition
211 static int record_canonical_element_1
212 PARAMS ((void **srfp
, void *data
));
213 static int check_hard_regs_in_partition
214 PARAMS ((partition reg_partition
));
215 static int rename_equivalent_regs_in_insn
216 PARAMS ((rtx
*ptr
, void *data
));
218 /* These are used in the register coalescing algorithm. */
219 static int coalesce_if_unconflicting
220 PARAMS ((partition p
, conflict_graph conflicts
, int reg1
, int reg2
));
221 static int coalesce_regs_in_copies
222 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
223 static int coalesce_reg_in_phi
224 PARAMS ((rtx
, int dest_regno
, int src_regno
, void *data
));
225 static int coalesce_regs_in_successor_phi_nodes
226 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
227 static partition compute_coalesced_reg_partition
229 static int mark_reg_in_phi
230 PARAMS ((rtx
*ptr
, void *data
));
231 static void mark_phi_and_copy_regs
232 PARAMS ((regset phi_set
));
234 static int rename_equivalent_regs_in_insn
235 PARAMS ((rtx
*ptr
, void *data
));
236 static void rename_equivalent_regs
237 PARAMS ((partition reg_partition
));
239 /* Deal with hard registers. */
240 static int conflicting_hard_regs_p
241 PARAMS ((int reg1
, int reg2
));
243 /* ssa_rename_to maps registers and machine modes to SSA pseudo registers. */
245 /* Find the register associated with REG in the indicated mode. */
248 ssa_rename_to_lookup (reg
)
251 if (!HARD_REGISTER_P (reg
))
252 return ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
];
254 return ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)];
257 /* Store a new value mapping REG to R in ssa_rename_to. */
260 ssa_rename_to_insert(reg
, r
)
264 if (!HARD_REGISTER_P (reg
))
265 ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
] = r
;
267 ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)] = r
;
270 /* Prepare ssa_rename_from for use. */
273 ssa_rename_from_initialize ()
275 /* We use an arbitrary initial hash table size of 64. */
276 ssa_rename_from_ht
= htab_create (64,
277 &ssa_rename_from_hash_function
,
278 &ssa_rename_from_equal
,
279 &ssa_rename_from_delete
);
282 /* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
286 ssa_rename_from_lookup (reg
)
289 ssa_rename_from_pair srfp
;
290 ssa_rename_from_pair
*answer
;
292 srfp
.original
= NULL_RTX
;
293 answer
= (ssa_rename_from_pair
*)
294 htab_find_with_hash (ssa_rename_from_ht
, (void *) &srfp
, reg
);
295 return (answer
== 0 ? NULL_RTX
: answer
->original
);
298 /* Find the number of the original register specified by REGNO. If
299 the register is a pseudo, return the original register's number.
300 Otherwise, return this register number REGNO. */
303 original_register (regno
)
306 rtx original_rtx
= ssa_rename_from_lookup (regno
);
307 return original_rtx
!= NULL_RTX
? REGNO (original_rtx
) : regno
;
310 /* Add mapping from R to REG to ssa_rename_from even if already present. */
313 ssa_rename_from_insert (reg
, r
)
318 ssa_rename_from_pair
*srfp
= xmalloc (sizeof (ssa_rename_from_pair
));
321 slot
= htab_find_slot_with_hash (ssa_rename_from_ht
, (const void *) srfp
,
324 free ((void *) *slot
);
328 /* Apply the CALLBACK_FUNCTION to each element in ssa_rename_from.
329 CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
330 current use of this function. */
333 ssa_rename_from_traverse (callback_function
,
334 canonical_elements
, reg_partition
)
335 htab_trav callback_function
;
336 sbitmap canonical_elements
;
337 partition reg_partition
;
339 struct ssa_rename_from_hash_table_data srfhd
;
340 srfhd
.canonical_elements
= canonical_elements
;
341 srfhd
.reg_partition
= reg_partition
;
342 htab_traverse (ssa_rename_from_ht
, callback_function
, (void *) &srfhd
);
345 /* Destroy ssa_rename_from. */
348 ssa_rename_from_free ()
350 htab_delete (ssa_rename_from_ht
);
353 /* Print the contents of ssa_rename_from. */
355 /* static Avoid erroneous error message. */
357 ssa_rename_from_print ()
359 printf ("ssa_rename_from's hash table contents:\n");
360 htab_traverse (ssa_rename_from_ht
, &ssa_rename_from_print_1
, NULL
);
363 /* Print the contents of the hash table entry SLOT, passing the unused
364 sttribute DATA. Used as a callback function with htab_traverse (). */
367 ssa_rename_from_print_1 (slot
, data
)
369 void *data ATTRIBUTE_UNUSED
;
371 ssa_rename_from_pair
* p
= *slot
;
372 printf ("ssa_rename_from maps pseudo %i to original %i.\n",
373 p
->reg
, REGNO (p
->original
));
377 /* Given a hash entry SRFP, yield a hash value. */
380 ssa_rename_from_hash_function (srfp
)
383 return ((const ssa_rename_from_pair
*) srfp
)->reg
;
386 /* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
389 ssa_rename_from_equal (srfp1
, srfp2
)
393 return ssa_rename_from_hash_function (srfp1
) ==
394 ssa_rename_from_hash_function (srfp2
);
397 /* Delete the hash table entry SRFP. */
400 ssa_rename_from_delete (srfp
)
406 /* Given the SET of a PHI node, return the address of the alternative
407 for predecessor block C. */
410 phi_alternative (set
, c
)
414 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
417 for (v
= GET_NUM_ELEM (phi_vec
) - 2; v
>= 0; v
-= 2)
418 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
419 return &RTVEC_ELT (phi_vec
, v
);
424 /* Given the SET of a phi node, remove the alternative for predecessor
425 block C. Return non-zero on success, or zero if no alternative is
429 remove_phi_alternative (set
, block
)
433 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
434 int num_elem
= GET_NUM_ELEM (phi_vec
);
438 for (v
= num_elem
- 2; v
>= 0; v
-= 2)
439 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
441 if (v
< num_elem
- 2)
443 RTVEC_ELT (phi_vec
, v
) = RTVEC_ELT (phi_vec
, num_elem
- 2);
444 RTVEC_ELT (phi_vec
, v
+ 1) = RTVEC_ELT (phi_vec
, num_elem
- 1);
446 PUT_NUM_ELEM (phi_vec
, num_elem
- 2);
453 /* For all registers, find all blocks in which they are set.
455 This is the transform of what would be local kill information that
456 we ought to be getting from flow. */
458 static sbitmap
*fe_evals
;
459 static int fe_current_bb
;
462 find_evaluations_1 (dest
, set
, data
)
464 rtx set ATTRIBUTE_UNUSED
;
465 void *data ATTRIBUTE_UNUSED
;
467 if (GET_CODE (dest
) == REG
468 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
469 SET_BIT (fe_evals
[REGNO (dest
)], fe_current_bb
);
473 find_evaluations (evals
, nregs
)
479 sbitmap_vector_zero (evals
, nregs
);
482 for (bb
= n_basic_blocks
; --bb
>= 0; )
488 last
= BLOCK_END (bb
);
492 note_stores (PATTERN (p
), find_evaluations_1
, NULL
);
501 /* Computing the Dominance Frontier:
503 As decribed in Morgan, section 3.5, this may be done simply by
504 walking the dominator tree bottom-up, computing the frontier for
505 the children before the parent. When considering a block B,
508 (1) A flow graph edge leaving B that does not lead to a child
509 of B in the dominator tree must be a block that is either equal
510 to B or not dominated by B. Such blocks belong in the frontier
513 (2) Consider a block X in the frontier of one of the children C
514 of B. If X is not equal to B and is not dominated by B, it
515 is in the frontier of B.
519 compute_dominance_frontiers_1 (frontiers
, idom
, bb
, done
)
525 basic_block b
= BASIC_BLOCK (bb
);
530 sbitmap_zero (frontiers
[bb
]);
532 /* Do the frontier of the children first. Not all children in the
533 dominator tree (blocks dominated by this one) are children in the
534 CFG, so check all blocks. */
535 for (c
= 0; c
< n_basic_blocks
; ++c
)
536 if (idom
[c
] == bb
&& ! TEST_BIT (done
, c
))
537 compute_dominance_frontiers_1 (frontiers
, idom
, c
, done
);
539 /* Find blocks conforming to rule (1) above. */
540 for (e
= b
->succ
; e
; e
= e
->succ_next
)
542 if (e
->dest
== EXIT_BLOCK_PTR
)
544 if (idom
[e
->dest
->index
] != bb
)
545 SET_BIT (frontiers
[bb
], e
->dest
->index
);
548 /* Find blocks conforming to rule (2). */
549 for (c
= 0; c
< n_basic_blocks
; ++c
)
553 EXECUTE_IF_SET_IN_SBITMAP (frontiers
[c
], 0, x
,
556 SET_BIT (frontiers
[bb
], x
);
562 compute_dominance_frontiers (frontiers
, idom
)
566 sbitmap done
= sbitmap_alloc (n_basic_blocks
);
569 compute_dominance_frontiers_1 (frontiers
, idom
, 0, done
);
574 /* Computing the Iterated Dominance Frontier:
576 This is the set of merge points for a given register.
578 This is not particularly intuitive. See section 7.1 of Morgan, in
579 particular figures 7.3 and 7.4 and the immediately surrounding text.
583 compute_iterated_dominance_frontiers (idfs
, frontiers
, evals
, nregs
)
592 worklist
= sbitmap_alloc (n_basic_blocks
);
594 for (reg
= 0; reg
< nregs
; ++reg
)
596 sbitmap idf
= idfs
[reg
];
599 /* Start the iterative process by considering those blocks that
600 evaluate REG. We'll add their dominance frontiers to the
601 IDF, and then consider the blocks we just added. */
602 sbitmap_copy (worklist
, evals
[reg
]);
604 /* Morgan's algorithm is incorrect here. Blocks that evaluate
605 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
608 /* Iterate until the worklist is empty. */
613 EXECUTE_IF_SET_IN_SBITMAP (worklist
, 0, b
,
615 RESET_BIT (worklist
, b
);
616 /* For each block on the worklist, add to the IDF all
617 blocks on its dominance frontier that aren't already
618 on the IDF. Every block that's added is also added
620 sbitmap_union_of_diff (worklist
, worklist
, frontiers
[b
], idf
);
621 sbitmap_a_or_b (idf
, idf
, frontiers
[b
]);
628 sbitmap_free (worklist
);
632 fprintf(rtl_dump_file
,
633 "Iterated dominance frontier: %d passes on %d regs.\n",
638 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
639 note associated with the BLOCK. */
642 first_insn_after_basic_block_note (block
)
647 /* Get the first instruction in the block. */
650 if (insn
== NULL_RTX
)
652 if (GET_CODE (insn
) == CODE_LABEL
)
653 insn
= NEXT_INSN (insn
);
654 if (!NOTE_INSN_BASIC_BLOCK_P (insn
))
657 return NEXT_INSN (insn
);
660 /* Insert the phi nodes. */
663 insert_phi_node (regno
, bb
)
666 basic_block b
= BASIC_BLOCK (bb
);
674 /* Find out how many predecessors there are. */
675 for (e
= b
->pred
, npred
= 0; e
; e
= e
->pred_next
)
676 if (e
->src
!= ENTRY_BLOCK_PTR
)
679 /* If this block has no "interesting" preds, then there is nothing to
680 do. Consider a block that only has the entry block as a pred. */
684 /* This is the register to which the phi function will be assigned. */
685 reg
= regno_reg_rtx
[regno
];
687 /* Construct the arguments to the PHI node. The use of pc_rtx is just
688 a placeholder; we'll insert the proper value in rename_registers. */
689 vec
= rtvec_alloc (npred
* 2);
690 for (e
= b
->pred
, i
= 0; e
; e
= e
->pred_next
, i
+= 2)
691 if (e
->src
!= ENTRY_BLOCK_PTR
)
693 RTVEC_ELT (vec
, i
+ 0) = pc_rtx
;
694 RTVEC_ELT (vec
, i
+ 1) = GEN_INT (e
->src
->index
);
697 phi
= gen_rtx_PHI (VOIDmode
, vec
);
698 phi
= gen_rtx_SET (VOIDmode
, reg
, phi
);
700 insn
= first_insn_after_basic_block_note (b
);
701 end_p
= PREV_INSN (insn
) == b
->end
;
702 emit_insn_before (phi
, insn
);
704 b
->end
= PREV_INSN (insn
);
708 insert_phi_nodes (idfs
, evals
, nregs
)
710 sbitmap
*evals ATTRIBUTE_UNUSED
;
715 for (reg
= 0; reg
< nregs
; ++reg
)
716 if (CONVERT_REGISTER_TO_SSA_P (reg
))
719 EXECUTE_IF_SET_IN_SBITMAP (idfs
[reg
], 0, b
,
721 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, reg
))
722 insert_phi_node (reg
, b
);
727 /* Rename the registers to conform to SSA.
729 This is essentially the algorithm presented in Figure 7.8 of Morgan,
730 with a few changes to reduce pattern search time in favour of a bit
731 more memory usage. */
733 /* One of these is created for each set. It will live in a list local
734 to its basic block for the duration of that block's processing. */
735 struct rename_set_data
737 struct rename_set_data
*next
;
738 /* This is the SET_DEST of the (first) SET that sets the REG. */
740 /* This is what used to be at *REG_LOC. */
742 /* This is the REG that will replace OLD_REG. It's set only
743 when the rename data is moved onto the DONE_RENAMES queue. */
745 /* This is what to restore ssa_rename_to_lookup (old_reg) to. It is
746 usually the previous contents of ssa_rename_to_lookup (old_reg). */
748 /* This is the insn that contains all the SETs of the REG. */
752 /* This struct is used to pass information to callback functions while
753 renaming registers. */
754 struct rename_context
756 struct rename_set_data
*new_renames
;
757 struct rename_set_data
*done_renames
;
761 /* Queue the rename of *REG_LOC. */
763 create_delayed_rename (c
, reg_loc
)
764 struct rename_context
*c
;
767 struct rename_set_data
*r
;
768 r
= (struct rename_set_data
*) xmalloc (sizeof(*r
));
770 if (GET_CODE (*reg_loc
) != REG
771 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc
)))
774 r
->reg_loc
= reg_loc
;
775 r
->old_reg
= *reg_loc
;
776 r
->prev_reg
= ssa_rename_to_lookup(r
->old_reg
);
777 r
->set_insn
= c
->current_insn
;
778 r
->next
= c
->new_renames
;
782 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
783 reused. If, during processing, a register has not yet been touched,
784 ssa_rename_to[regno][machno] will be NULL. Now, in the course of pushing
785 and popping values from ssa_rename_to, when we would ordinarily
786 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
787 same as NULL, except that it signals that the original regno has
788 already been reused. */
789 #define RENAME_NO_RTX pc_rtx
791 /* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
792 applying all the renames on NEW_RENAMES. */
795 apply_delayed_renames (c
)
796 struct rename_context
*c
;
798 struct rename_set_data
*r
;
799 struct rename_set_data
*last_r
= NULL
;
801 for (r
= c
->new_renames
; r
!= NULL
; r
= r
->next
)
805 /* Failure here means that someone has a PARALLEL that sets
806 a register twice (bad!). */
807 if (ssa_rename_to_lookup (r
->old_reg
) != r
->prev_reg
)
809 /* Failure here means we have changed REG_LOC before applying
811 /* For the first set we come across, reuse the original regno. */
812 if (r
->prev_reg
== NULL_RTX
&& !HARD_REGISTER_P (r
->old_reg
))
814 r
->new_reg
= r
->old_reg
;
815 /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
816 r
->prev_reg
= RENAME_NO_RTX
;
819 r
->new_reg
= gen_reg_rtx (GET_MODE (r
->old_reg
));
820 new_regno
= REGNO (r
->new_reg
);
821 ssa_rename_to_insert (r
->old_reg
, r
->new_reg
);
823 if (new_regno
>= (int) ssa_definition
->num_elements
)
825 int new_limit
= new_regno
* 5 / 4;
826 VARRAY_GROW (ssa_definition
, new_limit
);
829 VARRAY_RTX (ssa_definition
, new_regno
) = r
->set_insn
;
830 ssa_rename_from_insert (new_regno
, r
->old_reg
);
835 last_r
->next
= c
->done_renames
;
836 c
->done_renames
= c
->new_renames
;
837 c
->new_renames
= NULL
;
841 /* Part one of the first step of rename_block, called through for_each_rtx.
842 Mark pseudos that are set for later update. Transform uses of pseudos. */
845 rename_insn_1 (ptr
, data
)
850 struct rename_context
*context
= data
;
855 switch (GET_CODE (x
))
859 rtx
*destp
= &SET_DEST (x
);
860 rtx dest
= SET_DEST (x
);
862 /* Some SETs also use the REG specified in their LHS.
863 These can be detected by the presence of
864 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
865 in the LHS. Handle these by changing
866 (set (subreg (reg foo)) ...)
868 (sequence [(set (reg foo_1) (reg foo))
869 (set (subreg (reg foo_1)) ...)])
871 FIXME: Much of the time this is too much. For many libcalls,
872 paradoxical SUBREGs, etc., the input register is dead. We should
873 recognise this in rename_block or here and not make a false
876 if (GET_CODE (dest
) == STRICT_LOW_PART
877 || GET_CODE (dest
) == SUBREG
878 || GET_CODE (dest
) == SIGN_EXTRACT
879 || GET_CODE (dest
) == ZERO_EXTRACT
)
884 while (GET_CODE (reg
) == STRICT_LOW_PART
885 || GET_CODE (reg
) == SUBREG
886 || GET_CODE (reg
) == SIGN_EXTRACT
887 || GET_CODE (reg
) == ZERO_EXTRACT
)
890 if (GET_CODE (reg
) == REG
891 && CONVERT_REGISTER_TO_SSA_P (REGNO (reg
)))
893 /* Generate (set reg reg), and do renaming on it so
894 that it becomes (set reg_1 reg_0), and we will
895 replace reg with reg_1 in the SUBREG. */
897 struct rename_set_data
*saved_new_renames
;
898 saved_new_renames
= context
->new_renames
;
899 context
->new_renames
= NULL
;
900 i
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
901 for_each_rtx (&i
, rename_insn_1
, data
);
902 apply_delayed_renames (context
);
903 context
->new_renames
= saved_new_renames
;
906 else if (GET_CODE (dest
) == REG
&&
907 CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
909 /* We found a genuine set of an interesting register. Tag
910 it so that we can create a new name for it after we finish
911 processing this insn. */
913 create_delayed_rename (context
, destp
);
915 /* Since we do not wish to (directly) traverse the
916 SET_DEST, recurse through for_each_rtx for the SET_SRC
918 if (GET_CODE (x
) == SET
)
919 for_each_rtx (&SET_SRC (x
), rename_insn_1
, data
);
923 /* Otherwise, this was not an interesting destination. Continue
924 on, marking uses as normal. */
929 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)) &&
930 REGNO (x
) < ssa_max_reg_num
)
932 rtx new_reg
= ssa_rename_to_lookup (x
);
934 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
936 if (GET_MODE (x
) != GET_MODE (new_reg
))
940 /* Else this is a use before a set. Warn? */
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. */
980 rename_block (bb
, idom
)
984 basic_block b
= BASIC_BLOCK (bb
);
986 rtx insn
, next
, last
;
987 struct rename_set_data
*set_data
= NULL
;
990 /* Step One: Walk the basic block, adding new names for sets and
1000 struct rename_context context
;
1001 context
.done_renames
= set_data
;
1002 context
.new_renames
= NULL
;
1003 context
.current_insn
= insn
;
1006 for_each_rtx (&PATTERN (insn
), rename_insn_1
, &context
);
1007 for_each_rtx (®_NOTES (insn
), rename_insn_1
, &context
);
1009 /* Sometimes, we end up with a sequence of insns that
1010 SSA needs to treat as a single insn. Wrap these in a
1011 SEQUENCE. (Any notes now get attached to the SEQUENCE,
1012 not to the old version inner insn.) */
1013 if (get_insns () != NULL_RTX
)
1018 emit (PATTERN (insn
));
1019 seq
= gen_sequence ();
1020 /* We really want a SEQUENCE of SETs, not a SEQUENCE
1022 for (i
= 0; i
< XVECLEN (seq
, 0); i
++)
1023 XVECEXP (seq
, 0, i
) = PATTERN (XVECEXP (seq
, 0, i
));
1024 PATTERN (insn
) = seq
;
1028 apply_delayed_renames (&context
);
1029 set_data
= context
.done_renames
;
1032 next
= NEXT_INSN (insn
);
1034 while (insn
!= last
);
1036 /* Step Two: Update the phi nodes of this block's successors. */
1038 for (e
= b
->succ
; e
; e
= e
->succ_next
)
1040 if (e
->dest
== EXIT_BLOCK_PTR
)
1043 insn
= first_insn_after_basic_block_note (e
->dest
);
1045 while (PHI_NODE_P (insn
))
1047 rtx phi
= PATTERN (insn
);
1050 /* Find out which of our outgoing registers this node is
1051 intended to replace. Note that if this is not the first PHI
1052 node to have been created for this register, we have to
1053 jump through rename links to figure out which register
1054 we're talking about. This can easily be recognized by
1055 noting that the regno is new to this pass. */
1056 reg
= SET_DEST (phi
);
1057 if (REGNO (reg
) >= ssa_max_reg_num
)
1058 reg
= ssa_rename_from_lookup (REGNO (reg
));
1059 if (reg
== NULL_RTX
)
1061 reg
= ssa_rename_to_lookup (reg
);
1063 /* It is possible for the variable to be uninitialized on
1064 edges in. Reduce the arity of the PHI so that we don't
1065 consider those edges. */
1066 if (reg
== NULL
|| reg
== RENAME_NO_RTX
)
1068 if (! remove_phi_alternative (phi
, bb
))
1073 /* When we created the PHI nodes, we did not know what mode
1074 the register should be. Now that we've found an original,
1075 we can fill that in. */
1076 if (GET_MODE (SET_DEST (phi
)) == VOIDmode
)
1077 PUT_MODE (SET_DEST (phi
), GET_MODE (reg
));
1078 else if (GET_MODE (SET_DEST (phi
)) != GET_MODE (reg
))
1081 *phi_alternative (phi
, bb
) = reg
;
1084 insn
= NEXT_INSN (insn
);
1088 /* Step Three: Do the same to the children of this block in
1091 for (c
= 0; c
< n_basic_blocks
; ++c
)
1093 rename_block (c
, idom
);
1095 /* Step Four: Update the sets to refer to their new register,
1096 and restore ssa_rename_to to its previous state. */
1100 struct rename_set_data
*next
;
1101 rtx old_reg
= *set_data
->reg_loc
;
1103 if (*set_data
->reg_loc
!= set_data
->old_reg
)
1105 *set_data
->reg_loc
= set_data
->new_reg
;
1107 ssa_rename_to_insert (old_reg
, set_data
->prev_reg
);
1109 next
= set_data
->next
;
1116 rename_registers (nregs
, idom
)
1120 VARRAY_RTX_INIT (ssa_definition
, nregs
* 3, "ssa_definition");
1121 ssa_rename_from_initialize ();
1123 ssa_rename_to_pseudo
= (rtx
*) alloca (nregs
* sizeof(rtx
));
1124 memset ((char *) ssa_rename_to_pseudo
, 0, nregs
* sizeof(rtx
));
1125 memset ((char *) ssa_rename_to_hard
, 0,
1126 FIRST_PSEUDO_REGISTER
* NUM_MACHINE_MODES
* sizeof (rtx
));
1128 rename_block (0, idom
);
1130 /* ??? Update basic_block_live_at_start, and other flow info
1133 ssa_rename_to_pseudo
= NULL
;
1136 /* The main entry point for moving to SSA. */
1141 /* Element I is the set of blocks that set register I. */
1144 /* Dominator bitmaps. */
1148 /* Element I is the immediate dominator of block I. */
1153 /* Don't do it twice. */
1157 /* Need global_live_at_{start,end} up to date. Do not remove any
1158 dead code. We'll let the SSA optimizers do that. */
1159 life_analysis (get_insns (), NULL
, 0);
1161 idom
= (int *) alloca (n_basic_blocks
* sizeof (int));
1162 memset ((void *)idom
, -1, (size_t)n_basic_blocks
* sizeof (int));
1163 calculate_dominance_info (idom
, NULL
, CDI_DOMINATORS
);
1168 fputs (";; Immediate Dominators:\n", rtl_dump_file
);
1169 for (i
= 0; i
< n_basic_blocks
; ++i
)
1170 fprintf (rtl_dump_file
, ";\t%3d = %3d\n", i
, idom
[i
]);
1171 fflush (rtl_dump_file
);
1174 /* Compute dominance frontiers. */
1176 dfs
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
1177 compute_dominance_frontiers (dfs
, idom
);
1181 dump_sbitmap_vector (rtl_dump_file
, ";; Dominance Frontiers:",
1182 "; Basic Block", dfs
, n_basic_blocks
);
1183 fflush (rtl_dump_file
);
1186 /* Compute register evaluations. */
1188 ssa_max_reg_num
= max_reg_num();
1189 nregs
= ssa_max_reg_num
;
1190 evals
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
1191 find_evaluations (evals
, nregs
);
1193 /* Compute the iterated dominance frontier for each register. */
1195 idfs
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
1196 compute_iterated_dominance_frontiers (idfs
, dfs
, evals
, nregs
);
1200 dump_sbitmap_vector (rtl_dump_file
, ";; Iterated Dominance Frontiers:",
1201 "; Register", idfs
, nregs
);
1202 fflush (rtl_dump_file
);
1205 /* Insert the phi nodes. */
1207 insert_phi_nodes (idfs
, evals
, nregs
);
1209 /* Rename the registers to satisfy SSA. */
1211 rename_registers (nregs
, idom
);
1213 /* All done! Clean up and go home. */
1215 sbitmap_vector_free (dfs
);
1216 sbitmap_vector_free (evals
);
1217 sbitmap_vector_free (idfs
);
1220 reg_scan (get_insns (), max_reg_num (), 1);
1223 /* REG is the representative temporary of its partition. Add it to the
1224 set of nodes to be processed, if it hasn't been already. Return the
1225 index of this register in the node set. */
1228 ephi_add_node (reg
, nodes
, n_nodes
)
1233 for (i
= *n_nodes
- 1; i
>= 0; --i
)
1234 if (REGNO (reg
) == REGNO (nodes
[i
]))
1237 nodes
[i
= (*n_nodes
)++] = reg
;
1241 /* Part one of the topological sort. This is a forward (downward) search
1242 through the graph collecting a stack of nodes to process. Assuming no
1243 cycles, the nodes at top of the stack when we are finished will have
1244 no other dependancies. */
1247 ephi_forward (t
, visited
, succ
, tstack
)
1255 SET_BIT (visited
, t
);
1257 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1259 if (! TEST_BIT (visited
, s
))
1260 tstack
= ephi_forward (s
, visited
, succ
, tstack
);
1267 /* Part two of the topological sort. The is a backward search through
1268 a cycle in the graph, copying the data forward as we go. */
1271 ephi_backward (t
, visited
, pred
, nodes
)
1273 sbitmap visited
, *pred
;
1278 SET_BIT (visited
, t
);
1280 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1282 if (! TEST_BIT (visited
, p
))
1284 ephi_backward (p
, visited
, pred
, nodes
);
1285 emit_move_insn (nodes
[p
], nodes
[t
]);
1290 /* Part two of the topological sort. Create the copy for a register
1291 and any cycle of which it is a member. */
1294 ephi_create (t
, visited
, pred
, succ
, nodes
)
1296 sbitmap visited
, *pred
, *succ
;
1299 rtx reg_u
= NULL_RTX
;
1300 int unvisited_predecessors
= 0;
1303 /* Iterate through the predecessor list looking for unvisited nodes.
1304 If there are any, we have a cycle, and must deal with that. At
1305 the same time, look for a visited predecessor. If there is one,
1306 we won't need to create a temporary. */
1308 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1310 if (! TEST_BIT (visited
, p
))
1311 unvisited_predecessors
= 1;
1316 if (unvisited_predecessors
)
1318 /* We found a cycle. Copy out one element of the ring (if necessary),
1319 then traverse the ring copying as we go. */
1323 reg_u
= gen_reg_rtx (GET_MODE (nodes
[t
]));
1324 emit_move_insn (reg_u
, nodes
[t
]);
1327 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1329 if (! TEST_BIT (visited
, p
))
1331 ephi_backward (p
, visited
, pred
, nodes
);
1332 emit_move_insn (nodes
[p
], reg_u
);
1338 /* No cycle. Just copy the value from a successor. */
1341 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1343 SET_BIT (visited
, t
);
1344 emit_move_insn (nodes
[t
], nodes
[s
]);
1350 /* Convert the edge to normal form. */
1353 eliminate_phi (e
, reg_partition
)
1355 partition reg_partition
;
1358 sbitmap
*pred
, *succ
;
1361 int *stack
, *tstack
;
1365 /* Collect an upper bound on the number of registers needing processing. */
1367 insn
= first_insn_after_basic_block_note (e
->dest
);
1370 while (PHI_NODE_P (insn
))
1372 insn
= next_nonnote_insn (insn
);
1379 /* Build the auxilliary graph R(B).
1381 The nodes of the graph are the members of the register partition
1382 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1383 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1385 nodes
= (rtx
*) alloca (n_nodes
* sizeof(rtx
));
1386 pred
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1387 succ
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1388 sbitmap_vector_zero (pred
, n_nodes
);
1389 sbitmap_vector_zero (succ
, n_nodes
);
1391 insn
= first_insn_after_basic_block_note (e
->dest
);
1394 for (; PHI_NODE_P (insn
); insn
= next_nonnote_insn (insn
))
1396 rtx
* preg
= phi_alternative (PATTERN (insn
), e
->src
->index
);
1397 rtx tgt
= SET_DEST (PATTERN (insn
));
1400 /* There may be no phi alternative corresponding to this edge.
1401 This indicates that the phi variable is undefined along this
1407 if (GET_CODE (reg
) != REG
|| GET_CODE (tgt
) != REG
)
1410 reg
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (reg
))];
1411 tgt
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (tgt
))];
1412 /* If the two registers are already in the same partition,
1413 nothing will need to be done. */
1418 ireg
= ephi_add_node (reg
, nodes
, &n_nodes
);
1419 itgt
= ephi_add_node (tgt
, nodes
, &n_nodes
);
1421 SET_BIT (pred
[ireg
], itgt
);
1422 SET_BIT (succ
[itgt
], ireg
);
1429 /* Begin a topological sort of the graph. */
1431 visited
= sbitmap_alloc (n_nodes
);
1432 sbitmap_zero (visited
);
1434 tstack
= stack
= (int *) alloca (n_nodes
* sizeof (int));
1436 for (i
= 0; i
< n_nodes
; ++i
)
1437 if (! TEST_BIT (visited
, i
))
1438 tstack
= ephi_forward (i
, visited
, succ
, tstack
);
1440 sbitmap_zero (visited
);
1442 /* As we find a solution to the tsort, collect the implementation
1443 insns in a sequence. */
1446 while (tstack
!= stack
)
1449 if (! TEST_BIT (visited
, i
))
1450 ephi_create (i
, visited
, pred
, succ
, nodes
);
1453 insn
= gen_sequence ();
1455 insert_insn_on_edge (insn
, e
);
1457 fprintf (rtl_dump_file
, "Emitting copy on edge (%d,%d)\n",
1458 e
->src
->index
, e
->dest
->index
);
1460 sbitmap_free (visited
);
1462 sbitmap_vector_free (pred
);
1463 sbitmap_vector_free (succ
);
1466 /* For basic block B, consider all phi insns which provide an
1467 alternative corresponding to an incoming abnormal critical edge.
1468 Place the phi alternative corresponding to that abnormal critical
1469 edge in the same register class as the destination of the set.
1471 From Morgan, p. 178:
1473 For each abnormal critical edge (C, B),
1474 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1475 and C is the ith predecessor of B,
1476 then T0 and Ti must be equivalent.
1478 Return non-zero iff any such cases were found for which the two
1479 regs were not already in the same class. */
1482 make_regs_equivalent_over_bad_edges (bb
, reg_partition
)
1484 partition reg_partition
;
1487 basic_block b
= BASIC_BLOCK (bb
);
1490 /* Advance to the first phi node. */
1491 phi
= first_insn_after_basic_block_note (b
);
1493 /* Scan all the phi nodes. */
1496 phi
= next_nonnote_insn (phi
))
1500 rtx set
= PATTERN (phi
);
1501 rtx tgt
= SET_DEST (set
);
1503 /* The set target is expected to be an SSA register. */
1504 if (GET_CODE (tgt
) != REG
1505 || !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt
)))
1507 tgt_regno
= REGNO (tgt
);
1509 /* Scan incoming abnormal critical edges. */
1510 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1511 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1512 == (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1514 rtx
*alt
= phi_alternative (set
, e
->src
->index
);
1517 /* If there is no alternative corresponding to this edge,
1518 the value is undefined along the edge, so just go on. */
1522 /* The phi alternative is expected to be an SSA register. */
1523 if (GET_CODE (*alt
) != REG
1524 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1526 alt_regno
= REGNO (*alt
);
1528 /* If the set destination and the phi alternative aren't
1529 already in the same class... */
1530 if (partition_find (reg_partition
, tgt_regno
)
1531 != partition_find (reg_partition
, alt_regno
))
1533 /* ... make them such. */
1534 if (conflicting_hard_regs_p (tgt_regno
, alt_regno
))
1535 /* It is illegal to unify a hard register with a
1536 different register. */
1539 partition_union (reg_partition
,
1540 tgt_regno
, alt_regno
);
1549 /* Consider phi insns in basic block BB pairwise. If the set target
1550 of both isns are equivalent pseudos, make the corresponding phi
1551 alternatives in each phi corresponding equivalent.
1553 Return nonzero if any new register classes were unioned. */
1556 make_equivalent_phi_alternatives_equivalent (bb
, reg_partition
)
1558 partition reg_partition
;
1561 basic_block b
= BASIC_BLOCK (bb
);
1564 /* Advance to the first phi node. */
1565 phi
= first_insn_after_basic_block_note (b
);
1567 /* Scan all the phi nodes. */
1570 phi
= next_nonnote_insn (phi
))
1572 rtx set
= PATTERN (phi
);
1573 /* The regno of the destination of the set. */
1574 int tgt_regno
= REGNO (SET_DEST (PATTERN (phi
)));
1576 rtx phi2
= next_nonnote_insn (phi
);
1578 /* Scan all phi nodes following this one. */
1581 phi2
= next_nonnote_insn (phi2
))
1583 rtx set2
= PATTERN (phi2
);
1584 /* The regno of the destination of the set. */
1585 int tgt2_regno
= REGNO (SET_DEST (set2
));
1587 /* Are the set destinations equivalent regs? */
1588 if (partition_find (reg_partition
, tgt_regno
) ==
1589 partition_find (reg_partition
, tgt2_regno
))
1592 /* Scan over edges. */
1593 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1595 int pred_block
= e
->src
->index
;
1596 /* Identify the phi alternatives from both phi
1597 nodes corresponding to this edge. */
1598 rtx
*alt
= phi_alternative (set
, pred_block
);
1599 rtx
*alt2
= phi_alternative (set2
, pred_block
);
1601 /* If one of the phi nodes doesn't have a
1602 corresponding alternative, just skip it. */
1603 if (alt
== 0 || alt2
== 0)
1606 /* Both alternatives should be SSA registers. */
1607 if (GET_CODE (*alt
) != REG
1608 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1610 if (GET_CODE (*alt2
) != REG
1611 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2
)))
1614 /* If the alternatives aren't already in the same
1616 if (partition_find (reg_partition
, REGNO (*alt
))
1617 != partition_find (reg_partition
, REGNO (*alt2
)))
1619 /* ... make them so. */
1620 if (conflicting_hard_regs_p (REGNO (*alt
), REGNO (*alt2
)))
1621 /* It is illegal to unify a hard register with
1622 a different register. */
1625 partition_union (reg_partition
,
1626 REGNO (*alt
), REGNO (*alt2
));
1637 /* Compute a conservative partition of outstanding pseudo registers.
1638 See Morgan 7.3.1. */
1641 compute_conservative_reg_partition ()
1646 /* We don't actually work with hard registers, but it's easier to
1647 carry them around anyway rather than constantly doing register
1648 number arithmetic. */
1650 partition_new (ssa_definition
->num_elements
);
1652 /* The first priority is to make sure registers that might have to
1653 be copied on abnormal critical edges are placed in the same
1654 partition. This saves us from having to split abnormal critical
1656 for (bb
= n_basic_blocks
; --bb
>= 0; )
1657 changed
+= make_regs_equivalent_over_bad_edges (bb
, p
);
1659 /* Now we have to insure that corresponding arguments of phi nodes
1660 assigning to corresponding regs are equivalent. Iterate until
1665 for (bb
= n_basic_blocks
; --bb
>= 0; )
1666 changed
+= make_equivalent_phi_alternatives_equivalent (bb
, p
);
1672 /* The following functions compute a register partition that attempts
1673 to eliminate as many reg copies and phi node copies as possible by
1674 coalescing registers. This is the strategy:
1676 1. As in the conservative case, the top priority is to coalesce
1677 registers that otherwise would cause copies to be placed on
1678 abnormal critical edges (which isn't possible).
1680 2. Figure out which regs are involved (in the LHS or RHS) of
1681 copies and phi nodes. Compute conflicts among these regs.
1683 3. Walk around the instruction stream, placing two regs in the
1684 same class of the partition if one appears on the LHS and the
1685 other on the RHS of a copy or phi node and the two regs don't
1686 conflict. The conflict information of course needs to be
1689 4. If anything has changed, there may be new opportunities to
1690 coalesce regs, so go back to 2.
1693 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1694 same class of partition P, if they aren't already. Update
1695 CONFLICTS appropriately.
1697 Returns one if REG1 and REG2 were placed in the same class but were
1698 not previously; zero otherwise.
1700 See Morgan figure 11.15. */
1703 coalesce_if_unconflicting (p
, conflicts
, reg1
, reg2
)
1705 conflict_graph conflicts
;
1711 /* Work only on SSA registers. */
1712 if (!CONVERT_REGISTER_TO_SSA_P (reg1
) || !CONVERT_REGISTER_TO_SSA_P (reg2
))
1715 /* Find the canonical regs for the classes containing REG1 and
1717 reg1
= partition_find (p
, reg1
);
1718 reg2
= partition_find (p
, reg2
);
1720 /* If they're already in the same class, there's nothing to do. */
1724 /* If the regs conflict, our hands are tied. */
1725 if (conflicting_hard_regs_p (reg1
, reg2
) ||
1726 conflict_graph_conflict_p (conflicts
, reg1
, reg2
))
1729 /* We're good to go. Put the regs in the same partition. */
1730 partition_union (p
, reg1
, reg2
);
1732 /* Find the new canonical reg for the merged class. */
1733 reg
= partition_find (p
, reg1
);
1735 /* Merge conflicts from the two previous classes. */
1736 conflict_graph_merge_regs (conflicts
, reg
, reg1
);
1737 conflict_graph_merge_regs (conflicts
, reg
, reg2
);
1742 /* For each register copy insn in basic block BB, place the LHS and
1743 RHS regs in the same class in partition P if they do not conflict
1744 according to CONFLICTS.
1746 Returns the number of changes that were made to P.
1748 See Morgan figure 11.14. */
1751 coalesce_regs_in_copies (bb
, p
, conflicts
)
1754 conflict_graph conflicts
;
1760 /* Scan the instruction stream of the block. */
1761 for (insn
= bb
->head
; insn
!= end
; insn
= NEXT_INSN (insn
))
1767 /* If this isn't a set insn, go to the next insn. */
1768 if (GET_CODE (insn
) != INSN
)
1770 pattern
= PATTERN (insn
);
1771 if (GET_CODE (pattern
) != SET
)
1774 src
= SET_SRC (pattern
);
1775 dest
= SET_DEST (pattern
);
1777 /* We're only looking for copies. */
1778 if (GET_CODE (src
) != REG
|| GET_CODE (dest
) != REG
)
1781 /* Coalesce only if the reg modes are the same. As long as
1782 each reg's rtx is unique, it can have only one mode, so two
1783 pseudos of different modes can't be coalesced into one.
1785 FIXME: We can probably get around this by inserting SUBREGs
1786 where appropriate, but for now we don't bother. */
1787 if (GET_MODE (src
) != GET_MODE (dest
))
1790 /* Found a copy; see if we can use the same reg for both the
1791 source and destination (and thus eliminate the copy,
1793 changed
+= coalesce_if_unconflicting (p
, conflicts
,
1794 REGNO (src
), REGNO (dest
));
1800 struct phi_coalesce_context
1803 conflict_graph conflicts
;
1807 /* Callback function for for_each_successor_phi. If the set
1808 destination and the phi alternative regs do not conflict, place
1809 them in the same paritition class. DATA is a pointer to a
1810 phi_coalesce_context struct. */
1813 coalesce_reg_in_phi (insn
, dest_regno
, src_regno
, data
)
1814 rtx insn ATTRIBUTE_UNUSED
;
1819 struct phi_coalesce_context
*context
=
1820 (struct phi_coalesce_context
*) data
;
1822 /* Attempt to use the same reg, if they don't conflict. */
1824 += coalesce_if_unconflicting (context
->p
, context
->conflicts
,
1825 dest_regno
, src_regno
);
1829 /* For each alternative in a phi function corresponding to basic block
1830 BB (in phi nodes in successor block to BB), place the reg in the
1831 phi alternative and the reg to which the phi value is set into the
1832 same class in partition P, if allowed by CONFLICTS.
1834 Return the number of changes that were made to P.
1836 See Morgan figure 11.14. */
1839 coalesce_regs_in_successor_phi_nodes (bb
, p
, conflicts
)
1842 conflict_graph conflicts
;
1844 struct phi_coalesce_context context
;
1846 context
.conflicts
= conflicts
;
1847 context
.changed
= 0;
1849 for_each_successor_phi (bb
, &coalesce_reg_in_phi
, &context
);
1851 return context
.changed
;
1854 /* Compute and return a partition of pseudos. Where possible,
1855 non-conflicting pseudos are placed in the same class.
1857 The caller is responsible for deallocating the returned partition. */
1860 compute_coalesced_reg_partition ()
1866 partition_new (ssa_definition
->num_elements
);
1868 /* The first priority is to make sure registers that might have to
1869 be copied on abnormal critical edges are placed in the same
1870 partition. This saves us from having to split abnormal critical
1871 edges (which can't be done). */
1872 for (bb
= n_basic_blocks
; --bb
>= 0; )
1873 make_regs_equivalent_over_bad_edges (bb
, p
);
1877 regset_head phi_set
;
1878 conflict_graph conflicts
;
1882 /* Build the set of registers involved in phi nodes, either as
1883 arguments to the phi function or as the target of a set. */
1884 INITIALIZE_REG_SET (phi_set
);
1885 mark_phi_and_copy_regs (&phi_set
);
1887 /* Compute conflicts. */
1888 conflicts
= conflict_graph_compute (&phi_set
, p
);
1890 /* FIXME: Better would be to process most frequently executed
1891 blocks first, so that most frequently executed copies would
1892 be more likely to be removed by register coalescing. But any
1893 order will generate correct, if non-optimal, results. */
1894 for (bb
= n_basic_blocks
; --bb
>= 0; )
1896 basic_block block
= BASIC_BLOCK (bb
);
1897 changed
+= coalesce_regs_in_copies (block
, p
, conflicts
);
1899 coalesce_regs_in_successor_phi_nodes (block
, p
, conflicts
);
1902 conflict_graph_delete (conflicts
);
1904 while (changed
> 0);
1909 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1910 components (a REG or a CONST_INT). DATA is a reg set in which to
1911 set all regs. Called from for_each_rtx. */
1914 mark_reg_in_phi (ptr
, data
)
1919 regset set
= (regset
) data
;
1921 switch (GET_CODE (expr
))
1924 SET_REGNO_REG_SET (set
, REGNO (expr
));
1934 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1935 set from a phi expression, or used as an argument in one. Also
1936 mark regs that are the source or target of a reg copy. Uses
1940 mark_phi_and_copy_regs (phi_set
)
1945 /* Scan the definitions of all regs. */
1946 for (reg
= 0; reg
< VARRAY_SIZE (ssa_definition
); ++reg
)
1947 if (CONVERT_REGISTER_TO_SSA_P (reg
))
1949 rtx insn
= VARRAY_RTX (ssa_definition
, reg
);
1955 pattern
= PATTERN (insn
);
1956 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1958 if (GET_CODE (pattern
) != SET
)
1960 src
= SET_SRC (pattern
);
1962 if (GET_CODE (src
) == REG
)
1964 /* It's a reg copy. */
1965 SET_REGNO_REG_SET (phi_set
, reg
);
1966 SET_REGNO_REG_SET (phi_set
, REGNO (src
));
1968 else if (GET_CODE (src
) == PHI
)
1970 /* It's a phi node. Mark the reg being set. */
1971 SET_REGNO_REG_SET (phi_set
, reg
);
1972 /* Mark the regs used in the phi function. */
1973 for_each_rtx (&src
, mark_reg_in_phi
, phi_set
);
1975 /* ... else nothing to do. */
1979 /* Rename regs in insn PTR that are equivalent. DATA is the register
1980 partition which specifies equivalences. */
1983 rename_equivalent_regs_in_insn (ptr
, data
)
1988 partition reg_partition
= (partition
) data
;
1993 switch (GET_CODE (x
))
1996 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)))
1998 unsigned int regno
= REGNO (x
);
1999 unsigned int new_regno
= partition_find (reg_partition
, regno
);
2000 rtx canonical_element_rtx
= ssa_rename_from_lookup (new_regno
);
2002 if (canonical_element_rtx
!= NULL_RTX
&&
2003 HARD_REGISTER_P (canonical_element_rtx
))
2005 if (REGNO (canonical_element_rtx
) != regno
)
2006 *ptr
= canonical_element_rtx
;
2008 else if (regno
!= new_regno
)
2010 rtx new_reg
= regno_reg_rtx
[new_regno
];
2011 if (GET_MODE (x
) != GET_MODE (new_reg
))
2019 /* No need to rename the phi nodes. We'll check equivalence
2020 when inserting copies. */
2024 /* Anything else, continue traversing. */
2029 /* Record the register's canonical element stored in SRFP in the
2030 canonical_elements sbitmap packaged in DATA. This function is used
2031 as a callback function for traversing ssa_rename_from. */
2034 record_canonical_element_1 (srfp
, data
)
2038 unsigned int reg
= ((ssa_rename_from_pair
*) *srfp
)->reg
;
2039 sbitmap canonical_elements
=
2040 ((struct ssa_rename_from_hash_table_data
*) data
)->canonical_elements
;
2041 partition reg_partition
=
2042 ((struct ssa_rename_from_hash_table_data
*) data
)->reg_partition
;
2044 SET_BIT (canonical_elements
, partition_find (reg_partition
, reg
));
2048 /* For each class in the REG_PARTITION corresponding to a particular
2049 hard register and machine mode, check that there are no other
2050 classes with the same hard register and machine mode. Returns
2051 nonzero if this is the case, i.e., the partition is acceptable. */
2054 check_hard_regs_in_partition (reg_partition
)
2055 partition reg_partition
;
2057 /* CANONICAL_ELEMENTS has a nonzero bit if a class with the given register
2058 number and machine mode has already been seen. This is a
2059 problem with the partition. */
2060 sbitmap canonical_elements
;
2062 int already_seen
[FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
2066 /* Collect a list of canonical elements. */
2067 canonical_elements
= sbitmap_alloc (max_reg_num ());
2068 sbitmap_zero (canonical_elements
);
2069 ssa_rename_from_traverse (&record_canonical_element_1
,
2070 canonical_elements
, reg_partition
);
2072 /* We have not seen any hard register uses. */
2073 for (reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; ++reg
)
2074 for (mach_mode
= 0; mach_mode
< NUM_MACHINE_MODES
; ++mach_mode
)
2075 already_seen
[reg
][mach_mode
] = 0;
2077 /* Check for classes with the same hard register and machine mode. */
2078 EXECUTE_IF_SET_IN_SBITMAP (canonical_elements
, 0, element_index
,
2080 rtx hard_reg_rtx
= ssa_rename_from_lookup (element_index
);
2081 if (hard_reg_rtx
!= NULL_RTX
&&
2082 HARD_REGISTER_P (hard_reg_rtx
) &&
2083 already_seen
[REGNO (hard_reg_rtx
)][GET_MODE (hard_reg_rtx
)] != 0)
2084 /* Two distinct partition classes should be mapped to the same
2089 sbitmap_free (canonical_elements
);
2094 /* Rename regs that are equivalent in REG_PARTITION. Also collapse
2095 any SEQUENCE insns. */
2098 rename_equivalent_regs (reg_partition
)
2099 partition reg_partition
;
2103 for (bb
= n_basic_blocks
; --bb
>= 0; )
2105 basic_block b
= BASIC_BLOCK (bb
);
2115 for_each_rtx (&PATTERN (insn
),
2116 rename_equivalent_regs_in_insn
,
2118 for_each_rtx (®_NOTES (insn
),
2119 rename_equivalent_regs_in_insn
,
2122 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
2124 rtx s
= PATTERN (insn
);
2125 int slen
= XVECLEN (s
, 0);
2131 PATTERN (insn
) = XVECEXP (s
, 0, slen
-1);
2132 for (i
= 0; i
< slen
- 1; i
++)
2133 emit_block_insn_before (XVECEXP (s
, 0, i
), insn
, b
);
2137 next
= NEXT_INSN (insn
);
2139 while (insn
!= last
);
2143 /* The main entry point for moving from SSA. */
2149 partition reg_partition
;
2150 rtx insns
= get_insns ();
2152 /* Need global_live_at_{start,end} up to date. There should not be
2153 any significant dead code at this point, except perhaps dead
2154 stores. So do not take the time to perform dead code elimination.
2156 We also do not need death notes, so don't bother creating them. */
2157 life_analysis (insns
, NULL
, 0);
2159 /* Figure out which regs in copies and phi nodes don't conflict and
2160 therefore can be coalesced. */
2161 if (conservative_reg_partition
)
2162 reg_partition
= compute_conservative_reg_partition ();
2164 reg_partition
= compute_coalesced_reg_partition ();
2166 if (!check_hard_regs_in_partition (reg_partition
))
2167 /* Two separate partitions should correspond to the same hard
2168 register but do not. */
2171 rename_equivalent_regs (reg_partition
);
2173 /* Eliminate the PHI nodes. */
2174 for (bb
= n_basic_blocks
; --bb
>= 0; )
2176 basic_block b
= BASIC_BLOCK (bb
);
2179 for (e
= b
->pred
; e
; e
= e
->pred_next
)
2180 if (e
->src
!= ENTRY_BLOCK_PTR
)
2181 eliminate_phi (e
, reg_partition
);
2184 partition_delete (reg_partition
);
2186 /* Actually delete the PHI nodes. */
2187 for (bb
= n_basic_blocks
; --bb
>= 0; )
2189 rtx insn
= BLOCK_HEAD (bb
);
2193 /* If this is a PHI node delete it. */
2194 if (PHI_NODE_P (insn
))
2196 if (insn
== BLOCK_END (bb
))
2197 BLOCK_END (bb
) = PREV_INSN (insn
);
2198 insn
= delete_insn (insn
);
2200 /* Since all the phi nodes come at the beginning of the
2201 block, if we find an ordinary insn, we can stop looking
2202 for more phi nodes. */
2203 else if (INSN_P (insn
))
2205 /* If we've reached the end of the block, stop. */
2206 else if (insn
== BLOCK_END (bb
))
2209 insn
= NEXT_INSN (insn
);
2213 /* Commit all the copy nodes needed to convert out of SSA form. */
2214 commit_edge_insertions ();
2218 count_or_remove_death_notes (NULL
, 1);
2220 /* Deallocate the data structures. */
2221 VARRAY_FREE (ssa_definition
);
2222 ssa_rename_from_free ();
2225 /* Scan phi nodes in successors to BB. For each such phi node that
2226 has a phi alternative value corresponding to BB, invoke FN. FN
2227 is passed the entire phi node insn, the regno of the set
2228 destination, the regno of the phi argument corresponding to BB,
2231 If FN ever returns non-zero, stops immediately and returns this
2232 value. Otherwise, returns zero. */
2235 for_each_successor_phi (bb
, fn
, data
)
2237 successor_phi_fn fn
;
2242 if (bb
== EXIT_BLOCK_PTR
)
2245 /* Scan outgoing edges. */
2246 for (e
= bb
->succ
; e
!= NULL
; e
= e
->succ_next
)
2250 basic_block successor
= e
->dest
;
2251 if (successor
== ENTRY_BLOCK_PTR
2252 || successor
== EXIT_BLOCK_PTR
)
2255 /* Advance to the first non-label insn of the successor block. */
2256 insn
= first_insn_after_basic_block_note (successor
);
2261 /* Scan phi nodes in the successor. */
2262 for ( ; PHI_NODE_P (insn
); insn
= NEXT_INSN (insn
))
2265 rtx phi_set
= PATTERN (insn
);
2266 rtx
*alternative
= phi_alternative (phi_set
, bb
->index
);
2269 /* This phi function may not have an alternative
2270 corresponding to the incoming edge, indicating the
2271 assigned variable is not defined along the edge. */
2272 if (alternative
== NULL
)
2274 phi_src
= *alternative
;
2276 /* Invoke the callback. */
2277 result
= (*fn
) (insn
, REGNO (SET_DEST (phi_set
)),
2278 REGNO (phi_src
), data
);
2280 /* Terminate if requested. */
2289 /* Assuming the ssa_rename_from mapping has been established, yields
2290 nonzero if 1) only one SSA register of REG1 and REG2 comes from a
2291 hard register or 2) both SSA registers REG1 and REG2 come from
2292 different hard registers. */
2295 conflicting_hard_regs_p (reg1
, reg2
)
2299 int orig_reg1
= original_register (reg1
);
2300 int orig_reg2
= original_register (reg2
);
2301 if (HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
)
2302 && orig_reg1
!= orig_reg2
)
2304 if (HARD_REGISTER_NUM_P (orig_reg1
) && !HARD_REGISTER_NUM_P (orig_reg2
))
2306 if (!HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
))