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 void compute_dominance_frontiers_1
166 PARAMS ((sbitmap
*frontiers
, int *idom
, int bb
, sbitmap done
));
167 static void find_evaluations_1
168 PARAMS ((rtx dest
, rtx set
, void *data
));
169 static void find_evaluations
170 PARAMS ((sbitmap
*evals
, int nregs
));
171 static void compute_iterated_dominance_frontiers
172 PARAMS ((sbitmap
*idfs
, sbitmap
*frontiers
, sbitmap
*evals
, int nregs
));
173 static void insert_phi_node
174 PARAMS ((int regno
, int b
));
175 static void insert_phi_nodes
176 PARAMS ((sbitmap
*idfs
, sbitmap
*evals
, int nregs
));
177 static void create_delayed_rename
178 PARAMS ((struct rename_context
*, rtx
*));
179 static void apply_delayed_renames
180 PARAMS ((struct rename_context
*));
181 static int rename_insn_1
182 PARAMS ((rtx
*ptr
, void *data
));
183 static void rename_block
184 PARAMS ((int b
, int *idom
));
185 static void rename_registers
186 PARAMS ((int nregs
, int *idom
));
188 static inline int ephi_add_node
189 PARAMS ((rtx reg
, rtx
*nodes
, int *n_nodes
));
190 static int * ephi_forward
191 PARAMS ((int t
, sbitmap visited
, sbitmap
*succ
, int *tstack
));
192 static void ephi_backward
193 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, rtx
*nodes
));
194 static void ephi_create
195 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, sbitmap
*succ
, rtx
*nodes
));
196 static void eliminate_phi
197 PARAMS ((edge e
, partition reg_partition
));
198 static int make_regs_equivalent_over_bad_edges
199 PARAMS ((int bb
, partition reg_partition
));
201 /* These are used only in the conservative register partitioning
203 static int make_equivalent_phi_alternatives_equivalent
204 PARAMS ((int bb
, partition reg_partition
));
205 static partition compute_conservative_reg_partition
207 static int record_canonical_element_1
208 PARAMS ((void **srfp
, void *data
));
209 static int check_hard_regs_in_partition
210 PARAMS ((partition reg_partition
));
211 static int rename_equivalent_regs_in_insn
212 PARAMS ((rtx
*ptr
, void *data
));
214 /* These are used in the register coalescing algorithm. */
215 static int coalesce_if_unconflicting
216 PARAMS ((partition p
, conflict_graph conflicts
, int reg1
, int reg2
));
217 static int coalesce_regs_in_copies
218 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
219 static int coalesce_reg_in_phi
220 PARAMS ((rtx
, int dest_regno
, int src_regno
, void *data
));
221 static int coalesce_regs_in_successor_phi_nodes
222 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
223 static partition compute_coalesced_reg_partition
225 static int mark_reg_in_phi
226 PARAMS ((rtx
*ptr
, void *data
));
227 static void mark_phi_and_copy_regs
228 PARAMS ((regset phi_set
));
230 static int rename_equivalent_regs_in_insn
231 PARAMS ((rtx
*ptr
, void *data
));
232 static void rename_equivalent_regs
233 PARAMS ((partition reg_partition
));
235 /* Deal with hard registers. */
236 static int conflicting_hard_regs_p
237 PARAMS ((int reg1
, int reg2
));
239 /* ssa_rename_to maps registers and machine modes to SSA pseudo registers. */
241 /* Find the register associated with REG in the indicated mode. */
244 ssa_rename_to_lookup (reg
)
247 if (!HARD_REGISTER_P (reg
))
248 return ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
];
250 return ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)];
253 /* Store a new value mapping REG to R in ssa_rename_to. */
256 ssa_rename_to_insert(reg
, r
)
260 if (!HARD_REGISTER_P (reg
))
261 ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
] = r
;
263 ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)] = r
;
266 /* Prepare ssa_rename_from for use. */
269 ssa_rename_from_initialize ()
271 /* We use an arbitrary initial hash table size of 64. */
272 ssa_rename_from_ht
= htab_create (64,
273 &ssa_rename_from_hash_function
,
274 &ssa_rename_from_equal
,
275 &ssa_rename_from_delete
);
278 /* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
282 ssa_rename_from_lookup (reg
)
285 ssa_rename_from_pair srfp
;
286 ssa_rename_from_pair
*answer
;
288 srfp
.original
= NULL_RTX
;
289 answer
= (ssa_rename_from_pair
*)
290 htab_find_with_hash (ssa_rename_from_ht
, (void *) &srfp
, reg
);
291 return (answer
== 0 ? NULL_RTX
: answer
->original
);
294 /* Find the number of the original register specified by REGNO. If
295 the register is a pseudo, return the original register's number.
296 Otherwise, return this register number REGNO. */
299 original_register (regno
)
302 rtx original_rtx
= ssa_rename_from_lookup (regno
);
303 return original_rtx
!= NULL_RTX
? REGNO (original_rtx
) : regno
;
306 /* Add mapping from R to REG to ssa_rename_from even if already present. */
309 ssa_rename_from_insert (reg
, r
)
314 ssa_rename_from_pair
*srfp
= xmalloc (sizeof (ssa_rename_from_pair
));
317 slot
= htab_find_slot_with_hash (ssa_rename_from_ht
, (const void *) srfp
,
320 free ((void *) *slot
);
324 /* Apply the CALLBACK_FUNCTION to each element in ssa_rename_from.
325 CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
326 current use of this function. */
329 ssa_rename_from_traverse (callback_function
,
330 canonical_elements
, reg_partition
)
331 htab_trav callback_function
;
332 sbitmap canonical_elements
;
333 partition reg_partition
;
335 struct ssa_rename_from_hash_table_data srfhd
;
336 srfhd
.canonical_elements
= canonical_elements
;
337 srfhd
.reg_partition
= reg_partition
;
338 htab_traverse (ssa_rename_from_ht
, callback_function
, (void *) &srfhd
);
341 /* Destroy ssa_rename_from. */
344 ssa_rename_from_free ()
346 htab_delete (ssa_rename_from_ht
);
349 /* Print the contents of ssa_rename_from. */
351 /* static Avoid erroneous error message. */
353 ssa_rename_from_print ()
355 printf ("ssa_rename_from's hash table contents:\n");
356 htab_traverse (ssa_rename_from_ht
, &ssa_rename_from_print_1
, NULL
);
359 /* Print the contents of the hash table entry SLOT, passing the unused
360 sttribute DATA. Used as a callback function with htab_traverse (). */
363 ssa_rename_from_print_1 (slot
, data
)
365 void *data ATTRIBUTE_UNUSED
;
367 ssa_rename_from_pair
* p
= *slot
;
368 printf ("ssa_rename_from maps pseudo %i to original %i.\n",
369 p
->reg
, REGNO (p
->original
));
373 /* Given a hash entry SRFP, yield a hash value. */
376 ssa_rename_from_hash_function (srfp
)
379 return ((const ssa_rename_from_pair
*) srfp
)->reg
;
382 /* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
385 ssa_rename_from_equal (srfp1
, srfp2
)
389 return ssa_rename_from_hash_function (srfp1
) ==
390 ssa_rename_from_hash_function (srfp2
);
393 /* Delete the hash table entry SRFP. */
396 ssa_rename_from_delete (srfp
)
402 /* Given the SET of a PHI node, return the address of the alternative
403 for predecessor block C. */
406 phi_alternative (set
, c
)
410 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
413 for (v
= GET_NUM_ELEM (phi_vec
) - 2; v
>= 0; v
-= 2)
414 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
415 return &RTVEC_ELT (phi_vec
, v
);
420 /* Given the SET of a phi node, remove the alternative for predecessor
421 block C. Return non-zero on success, or zero if no alternative is
425 remove_phi_alternative (set
, block
)
429 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
430 int num_elem
= GET_NUM_ELEM (phi_vec
);
434 for (v
= num_elem
- 2; v
>= 0; v
-= 2)
435 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
437 if (v
< num_elem
- 2)
439 RTVEC_ELT (phi_vec
, v
) = RTVEC_ELT (phi_vec
, num_elem
- 2);
440 RTVEC_ELT (phi_vec
, v
+ 1) = RTVEC_ELT (phi_vec
, num_elem
- 1);
442 PUT_NUM_ELEM (phi_vec
, num_elem
- 2);
449 /* For all registers, find all blocks in which they are set.
451 This is the transform of what would be local kill information that
452 we ought to be getting from flow. */
454 static sbitmap
*fe_evals
;
455 static int fe_current_bb
;
458 find_evaluations_1 (dest
, set
, data
)
460 rtx set ATTRIBUTE_UNUSED
;
461 void *data ATTRIBUTE_UNUSED
;
463 if (GET_CODE (dest
) == REG
464 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
465 SET_BIT (fe_evals
[REGNO (dest
)], fe_current_bb
);
469 find_evaluations (evals
, nregs
)
475 sbitmap_vector_zero (evals
, nregs
);
478 for (bb
= n_basic_blocks
; --bb
>= 0; )
484 last
= BLOCK_END (bb
);
488 note_stores (PATTERN (p
), find_evaluations_1
, NULL
);
497 /* Computing the Dominance Frontier:
499 As decribed in Morgan, section 3.5, this may be done simply by
500 walking the dominator tree bottom-up, computing the frontier for
501 the children before the parent. When considering a block B,
504 (1) A flow graph edge leaving B that does not lead to a child
505 of B in the dominator tree must be a block that is either equal
506 to B or not dominated by B. Such blocks belong in the frontier
509 (2) Consider a block X in the frontier of one of the children C
510 of B. If X is not equal to B and is not dominated by B, it
511 is in the frontier of B.
515 compute_dominance_frontiers_1 (frontiers
, idom
, bb
, done
)
521 basic_block b
= BASIC_BLOCK (bb
);
526 sbitmap_zero (frontiers
[bb
]);
528 /* Do the frontier of the children first. Not all children in the
529 dominator tree (blocks dominated by this one) are children in the
530 CFG, so check all blocks. */
531 for (c
= 0; c
< n_basic_blocks
; ++c
)
532 if (idom
[c
] == bb
&& ! TEST_BIT (done
, c
))
533 compute_dominance_frontiers_1 (frontiers
, idom
, c
, done
);
535 /* Find blocks conforming to rule (1) above. */
536 for (e
= b
->succ
; e
; e
= e
->succ_next
)
538 if (e
->dest
== EXIT_BLOCK_PTR
)
540 if (idom
[e
->dest
->index
] != bb
)
541 SET_BIT (frontiers
[bb
], e
->dest
->index
);
544 /* Find blocks conforming to rule (2). */
545 for (c
= 0; c
< n_basic_blocks
; ++c
)
549 EXECUTE_IF_SET_IN_SBITMAP (frontiers
[c
], 0, x
,
552 SET_BIT (frontiers
[bb
], x
);
558 compute_dominance_frontiers (frontiers
, idom
)
562 sbitmap done
= sbitmap_alloc (n_basic_blocks
);
565 compute_dominance_frontiers_1 (frontiers
, idom
, 0, done
);
570 /* Computing the Iterated Dominance Frontier:
572 This is the set of merge points for a given register.
574 This is not particularly intuitive. See section 7.1 of Morgan, in
575 particular figures 7.3 and 7.4 and the immediately surrounding text.
579 compute_iterated_dominance_frontiers (idfs
, frontiers
, evals
, nregs
)
588 worklist
= sbitmap_alloc (n_basic_blocks
);
590 for (reg
= 0; reg
< nregs
; ++reg
)
592 sbitmap idf
= idfs
[reg
];
595 /* Start the iterative process by considering those blocks that
596 evaluate REG. We'll add their dominance frontiers to the
597 IDF, and then consider the blocks we just added. */
598 sbitmap_copy (worklist
, evals
[reg
]);
600 /* Morgan's algorithm is incorrect here. Blocks that evaluate
601 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
604 /* Iterate until the worklist is empty. */
609 EXECUTE_IF_SET_IN_SBITMAP (worklist
, 0, b
,
611 RESET_BIT (worklist
, b
);
612 /* For each block on the worklist, add to the IDF all
613 blocks on its dominance frontier that aren't already
614 on the IDF. Every block that's added is also added
616 sbitmap_union_of_diff (worklist
, worklist
, frontiers
[b
], idf
);
617 sbitmap_a_or_b (idf
, idf
, frontiers
[b
]);
624 sbitmap_free (worklist
);
628 fprintf(rtl_dump_file
,
629 "Iterated dominance frontier: %d passes on %d regs.\n",
634 /* Insert the phi nodes. */
637 insert_phi_node (regno
, bb
)
640 basic_block b
= BASIC_BLOCK (bb
);
648 /* Find out how many predecessors there are. */
649 for (e
= b
->pred
, npred
= 0; e
; e
= e
->pred_next
)
650 if (e
->src
!= ENTRY_BLOCK_PTR
)
653 /* If this block has no "interesting" preds, then there is nothing to
654 do. Consider a block that only has the entry block as a pred. */
658 /* This is the register to which the phi function will be assigned. */
659 reg
= regno_reg_rtx
[regno
];
661 /* Construct the arguments to the PHI node. The use of pc_rtx is just
662 a placeholder; we'll insert the proper value in rename_registers. */
663 vec
= rtvec_alloc (npred
* 2);
664 for (e
= b
->pred
, i
= 0; e
; e
= e
->pred_next
, i
+= 2)
665 if (e
->src
!= ENTRY_BLOCK_PTR
)
667 RTVEC_ELT (vec
, i
+ 0) = pc_rtx
;
668 RTVEC_ELT (vec
, i
+ 1) = GEN_INT (e
->src
->index
);
671 phi
= gen_rtx_PHI (VOIDmode
, vec
);
672 phi
= gen_rtx_SET (VOIDmode
, reg
, phi
);
674 insn
= first_insn_after_basic_block_note (b
);
675 end_p
= PREV_INSN (insn
) == b
->end
;
676 emit_insn_before (phi
, insn
);
678 b
->end
= PREV_INSN (insn
);
682 insert_phi_nodes (idfs
, evals
, nregs
)
684 sbitmap
*evals ATTRIBUTE_UNUSED
;
689 for (reg
= 0; reg
< nregs
; ++reg
)
690 if (CONVERT_REGISTER_TO_SSA_P (reg
))
693 EXECUTE_IF_SET_IN_SBITMAP (idfs
[reg
], 0, b
,
695 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, reg
))
696 insert_phi_node (reg
, b
);
701 /* Rename the registers to conform to SSA.
703 This is essentially the algorithm presented in Figure 7.8 of Morgan,
704 with a few changes to reduce pattern search time in favour of a bit
705 more memory usage. */
707 /* One of these is created for each set. It will live in a list local
708 to its basic block for the duration of that block's processing. */
709 struct rename_set_data
711 struct rename_set_data
*next
;
712 /* This is the SET_DEST of the (first) SET that sets the REG. */
714 /* This is what used to be at *REG_LOC. */
716 /* This is the REG that will replace OLD_REG. It's set only
717 when the rename data is moved onto the DONE_RENAMES queue. */
719 /* This is what to restore ssa_rename_to_lookup (old_reg) to. It is
720 usually the previous contents of ssa_rename_to_lookup (old_reg). */
722 /* This is the insn that contains all the SETs of the REG. */
726 /* This struct is used to pass information to callback functions while
727 renaming registers. */
728 struct rename_context
730 struct rename_set_data
*new_renames
;
731 struct rename_set_data
*done_renames
;
735 /* Queue the rename of *REG_LOC. */
737 create_delayed_rename (c
, reg_loc
)
738 struct rename_context
*c
;
741 struct rename_set_data
*r
;
742 r
= (struct rename_set_data
*) xmalloc (sizeof(*r
));
744 if (GET_CODE (*reg_loc
) != REG
745 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc
)))
748 r
->reg_loc
= reg_loc
;
749 r
->old_reg
= *reg_loc
;
750 r
->prev_reg
= ssa_rename_to_lookup(r
->old_reg
);
751 r
->set_insn
= c
->current_insn
;
752 r
->next
= c
->new_renames
;
756 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
757 reused. If, during processing, a register has not yet been touched,
758 ssa_rename_to[regno][machno] will be NULL. Now, in the course of pushing
759 and popping values from ssa_rename_to, when we would ordinarily
760 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
761 same as NULL, except that it signals that the original regno has
762 already been reused. */
763 #define RENAME_NO_RTX pc_rtx
765 /* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
766 applying all the renames on NEW_RENAMES. */
769 apply_delayed_renames (c
)
770 struct rename_context
*c
;
772 struct rename_set_data
*r
;
773 struct rename_set_data
*last_r
= NULL
;
775 for (r
= c
->new_renames
; r
!= NULL
; r
= r
->next
)
779 /* Failure here means that someone has a PARALLEL that sets
780 a register twice (bad!). */
781 if (ssa_rename_to_lookup (r
->old_reg
) != r
->prev_reg
)
783 /* Failure here means we have changed REG_LOC before applying
785 /* For the first set we come across, reuse the original regno. */
786 if (r
->prev_reg
== NULL_RTX
&& !HARD_REGISTER_P (r
->old_reg
))
788 r
->new_reg
= r
->old_reg
;
789 /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
790 r
->prev_reg
= RENAME_NO_RTX
;
793 r
->new_reg
= gen_reg_rtx (GET_MODE (r
->old_reg
));
794 new_regno
= REGNO (r
->new_reg
);
795 ssa_rename_to_insert (r
->old_reg
, r
->new_reg
);
797 if (new_regno
>= (int) ssa_definition
->num_elements
)
799 int new_limit
= new_regno
* 5 / 4;
800 VARRAY_GROW (ssa_definition
, new_limit
);
803 VARRAY_RTX (ssa_definition
, new_regno
) = r
->set_insn
;
804 ssa_rename_from_insert (new_regno
, r
->old_reg
);
809 last_r
->next
= c
->done_renames
;
810 c
->done_renames
= c
->new_renames
;
811 c
->new_renames
= NULL
;
815 /* Part one of the first step of rename_block, called through for_each_rtx.
816 Mark pseudos that are set for later update. Transform uses of pseudos. */
819 rename_insn_1 (ptr
, data
)
824 struct rename_context
*context
= data
;
829 switch (GET_CODE (x
))
833 rtx
*destp
= &SET_DEST (x
);
834 rtx dest
= SET_DEST (x
);
836 /* Some SETs also use the REG specified in their LHS.
837 These can be detected by the presence of
838 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
839 in the LHS. Handle these by changing
840 (set (subreg (reg foo)) ...)
842 (sequence [(set (reg foo_1) (reg foo))
843 (set (subreg (reg foo_1)) ...)])
845 FIXME: Much of the time this is too much. For many libcalls,
846 paradoxical SUBREGs, etc., the input register is dead. We should
847 recognise this in rename_block or here and not make a false
850 if (GET_CODE (dest
) == STRICT_LOW_PART
851 || GET_CODE (dest
) == SUBREG
852 || GET_CODE (dest
) == SIGN_EXTRACT
853 || GET_CODE (dest
) == ZERO_EXTRACT
)
858 while (GET_CODE (reg
) == STRICT_LOW_PART
859 || GET_CODE (reg
) == SUBREG
860 || GET_CODE (reg
) == SIGN_EXTRACT
861 || GET_CODE (reg
) == ZERO_EXTRACT
)
864 if (GET_CODE (reg
) == REG
865 && CONVERT_REGISTER_TO_SSA_P (REGNO (reg
)))
867 /* Generate (set reg reg), and do renaming on it so
868 that it becomes (set reg_1 reg_0), and we will
869 replace reg with reg_1 in the SUBREG. */
871 struct rename_set_data
*saved_new_renames
;
872 saved_new_renames
= context
->new_renames
;
873 context
->new_renames
= NULL
;
874 i
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
875 for_each_rtx (&i
, rename_insn_1
, data
);
876 apply_delayed_renames (context
);
877 context
->new_renames
= saved_new_renames
;
880 else if (GET_CODE (dest
) == REG
&&
881 CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
883 /* We found a genuine set of an interesting register. Tag
884 it so that we can create a new name for it after we finish
885 processing this insn. */
887 create_delayed_rename (context
, destp
);
889 /* Since we do not wish to (directly) traverse the
890 SET_DEST, recurse through for_each_rtx for the SET_SRC
892 if (GET_CODE (x
) == SET
)
893 for_each_rtx (&SET_SRC (x
), rename_insn_1
, data
);
897 /* Otherwise, this was not an interesting destination. Continue
898 on, marking uses as normal. */
903 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)) &&
904 REGNO (x
) < ssa_max_reg_num
)
906 rtx new_reg
= ssa_rename_to_lookup (x
);
908 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
910 if (GET_MODE (x
) != GET_MODE (new_reg
))
914 /* Else this is a use before a set. Warn? */
919 /* There is considerable debate on how CLOBBERs ought to be
920 handled in SSA. For now, we're keeping the CLOBBERs, which
921 means that we don't really have SSA form. There are a couple
922 of proposals for how to fix this problem, but neither is
925 rtx dest
= XCEXP (x
, 0, CLOBBER
);
928 if (CONVERT_REGISTER_TO_SSA_P (REGNO (dest
))
929 && REGNO (dest
) < ssa_max_reg_num
)
931 rtx new_reg
= ssa_rename_to_lookup (dest
);
932 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
933 XCEXP (x
, 0, CLOBBER
) = new_reg
;
935 /* Stop traversing. */
939 /* Continue traversing. */
944 /* Never muck with the phi. We do that elsewhere, special-like. */
948 /* Anything else, continue traversing. */
954 rename_block (bb
, idom
)
958 basic_block b
= BASIC_BLOCK (bb
);
960 rtx insn
, next
, last
;
961 struct rename_set_data
*set_data
= NULL
;
964 /* Step One: Walk the basic block, adding new names for sets and
974 struct rename_context context
;
975 context
.done_renames
= set_data
;
976 context
.new_renames
= NULL
;
977 context
.current_insn
= insn
;
980 for_each_rtx (&PATTERN (insn
), rename_insn_1
, &context
);
981 for_each_rtx (®_NOTES (insn
), rename_insn_1
, &context
);
983 /* Sometimes, we end up with a sequence of insns that
984 SSA needs to treat as a single insn. Wrap these in a
985 SEQUENCE. (Any notes now get attached to the SEQUENCE,
986 not to the old version inner insn.) */
987 if (get_insns () != NULL_RTX
)
992 emit (PATTERN (insn
));
993 seq
= gen_sequence ();
994 /* We really want a SEQUENCE of SETs, not a SEQUENCE
996 for (i
= 0; i
< XVECLEN (seq
, 0); i
++)
997 XVECEXP (seq
, 0, i
) = PATTERN (XVECEXP (seq
, 0, i
));
998 PATTERN (insn
) = seq
;
1002 apply_delayed_renames (&context
);
1003 set_data
= context
.done_renames
;
1006 next
= NEXT_INSN (insn
);
1008 while (insn
!= last
);
1010 /* Step Two: Update the phi nodes of this block's successors. */
1012 for (e
= b
->succ
; e
; e
= e
->succ_next
)
1014 if (e
->dest
== EXIT_BLOCK_PTR
)
1017 insn
= first_insn_after_basic_block_note (e
->dest
);
1019 while (PHI_NODE_P (insn
))
1021 rtx phi
= PATTERN (insn
);
1024 /* Find out which of our outgoing registers this node is
1025 intended to replace. Note that if this is not the first PHI
1026 node to have been created for this register, we have to
1027 jump through rename links to figure out which register
1028 we're talking about. This can easily be recognized by
1029 noting that the regno is new to this pass. */
1030 reg
= SET_DEST (phi
);
1031 if (REGNO (reg
) >= ssa_max_reg_num
)
1032 reg
= ssa_rename_from_lookup (REGNO (reg
));
1033 if (reg
== NULL_RTX
)
1035 reg
= ssa_rename_to_lookup (reg
);
1037 /* It is possible for the variable to be uninitialized on
1038 edges in. Reduce the arity of the PHI so that we don't
1039 consider those edges. */
1040 if (reg
== NULL
|| reg
== RENAME_NO_RTX
)
1042 if (! remove_phi_alternative (phi
, b
))
1047 /* When we created the PHI nodes, we did not know what mode
1048 the register should be. Now that we've found an original,
1049 we can fill that in. */
1050 if (GET_MODE (SET_DEST (phi
)) == VOIDmode
)
1051 PUT_MODE (SET_DEST (phi
), GET_MODE (reg
));
1052 else if (GET_MODE (SET_DEST (phi
)) != GET_MODE (reg
))
1055 *phi_alternative (phi
, bb
) = reg
;
1058 insn
= NEXT_INSN (insn
);
1062 /* Step Three: Do the same to the children of this block in
1065 for (c
= 0; c
< n_basic_blocks
; ++c
)
1067 rename_block (c
, idom
);
1069 /* Step Four: Update the sets to refer to their new register,
1070 and restore ssa_rename_to to its previous state. */
1074 struct rename_set_data
*next
;
1075 rtx old_reg
= *set_data
->reg_loc
;
1077 if (*set_data
->reg_loc
!= set_data
->old_reg
)
1079 *set_data
->reg_loc
= set_data
->new_reg
;
1081 ssa_rename_to_insert (old_reg
, set_data
->prev_reg
);
1083 next
= set_data
->next
;
1090 rename_registers (nregs
, idom
)
1094 VARRAY_RTX_INIT (ssa_definition
, nregs
* 3, "ssa_definition");
1095 ssa_rename_from_initialize ();
1097 ssa_rename_to_pseudo
= (rtx
*) alloca (nregs
* sizeof(rtx
));
1098 memset ((char *) ssa_rename_to_pseudo
, 0, nregs
* sizeof(rtx
));
1099 memset ((char *) ssa_rename_to_hard
, 0,
1100 FIRST_PSEUDO_REGISTER
* NUM_MACHINE_MODES
* sizeof (rtx
));
1102 rename_block (0, idom
);
1104 /* ??? Update basic_block_live_at_start, and other flow info
1107 ssa_rename_to_pseudo
= NULL
;
1110 /* The main entry point for moving to SSA. */
1115 /* Element I is the set of blocks that set register I. */
1118 /* Dominator bitmaps. */
1122 /* Element I is the immediate dominator of block I. */
1127 /* Don't do it twice. */
1131 /* Need global_live_at_{start,end} up to date. Do not remove any
1132 dead code. We'll let the SSA optimizers do that. */
1133 life_analysis (get_insns (), NULL
, 0);
1135 idom
= (int *) alloca (n_basic_blocks
* sizeof (int));
1136 memset ((void *)idom
, -1, (size_t)n_basic_blocks
* sizeof (int));
1137 calculate_dominance_info (idom
, NULL
, CDI_DOMINATORS
);
1142 fputs (";; Immediate Dominators:\n", rtl_dump_file
);
1143 for (i
= 0; i
< n_basic_blocks
; ++i
)
1144 fprintf (rtl_dump_file
, ";\t%3d = %3d\n", i
, idom
[i
]);
1145 fflush (rtl_dump_file
);
1148 /* Compute dominance frontiers. */
1150 dfs
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
1151 compute_dominance_frontiers (dfs
, idom
);
1155 dump_sbitmap_vector (rtl_dump_file
, ";; Dominance Frontiers:",
1156 "; Basic Block", dfs
, n_basic_blocks
);
1157 fflush (rtl_dump_file
);
1160 /* Compute register evaluations. */
1162 ssa_max_reg_num
= max_reg_num();
1163 nregs
= ssa_max_reg_num
;
1164 evals
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
1165 find_evaluations (evals
, nregs
);
1167 /* Compute the iterated dominance frontier for each register. */
1169 idfs
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
1170 compute_iterated_dominance_frontiers (idfs
, dfs
, evals
, nregs
);
1174 dump_sbitmap_vector (rtl_dump_file
, ";; Iterated Dominance Frontiers:",
1175 "; Register", idfs
, nregs
);
1176 fflush (rtl_dump_file
);
1179 /* Insert the phi nodes. */
1181 insert_phi_nodes (idfs
, evals
, nregs
);
1183 /* Rename the registers to satisfy SSA. */
1185 rename_registers (nregs
, idom
);
1187 /* All done! Clean up and go home. */
1189 sbitmap_vector_free (dfs
);
1190 sbitmap_vector_free (evals
);
1191 sbitmap_vector_free (idfs
);
1194 reg_scan (get_insns (), max_reg_num (), 1);
1197 /* REG is the representative temporary of its partition. Add it to the
1198 set of nodes to be processed, if it hasn't been already. Return the
1199 index of this register in the node set. */
1202 ephi_add_node (reg
, nodes
, n_nodes
)
1207 for (i
= *n_nodes
- 1; i
>= 0; --i
)
1208 if (REGNO (reg
) == REGNO (nodes
[i
]))
1211 nodes
[i
= (*n_nodes
)++] = reg
;
1215 /* Part one of the topological sort. This is a forward (downward) search
1216 through the graph collecting a stack of nodes to process. Assuming no
1217 cycles, the nodes at top of the stack when we are finished will have
1218 no other dependancies. */
1221 ephi_forward (t
, visited
, succ
, tstack
)
1229 SET_BIT (visited
, t
);
1231 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1233 if (! TEST_BIT (visited
, s
))
1234 tstack
= ephi_forward (s
, visited
, succ
, tstack
);
1241 /* Part two of the topological sort. The is a backward search through
1242 a cycle in the graph, copying the data forward as we go. */
1245 ephi_backward (t
, visited
, pred
, nodes
)
1247 sbitmap visited
, *pred
;
1252 SET_BIT (visited
, t
);
1254 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1256 if (! TEST_BIT (visited
, p
))
1258 ephi_backward (p
, visited
, pred
, nodes
);
1259 emit_move_insn (nodes
[p
], nodes
[t
]);
1264 /* Part two of the topological sort. Create the copy for a register
1265 and any cycle of which it is a member. */
1268 ephi_create (t
, visited
, pred
, succ
, nodes
)
1270 sbitmap visited
, *pred
, *succ
;
1273 rtx reg_u
= NULL_RTX
;
1274 int unvisited_predecessors
= 0;
1277 /* Iterate through the predecessor list looking for unvisited nodes.
1278 If there are any, we have a cycle, and must deal with that. At
1279 the same time, look for a visited predecessor. If there is one,
1280 we won't need to create a temporary. */
1282 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1284 if (! TEST_BIT (visited
, p
))
1285 unvisited_predecessors
= 1;
1290 if (unvisited_predecessors
)
1292 /* We found a cycle. Copy out one element of the ring (if necessary),
1293 then traverse the ring copying as we go. */
1297 reg_u
= gen_reg_rtx (GET_MODE (nodes
[t
]));
1298 emit_move_insn (reg_u
, nodes
[t
]);
1301 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1303 if (! TEST_BIT (visited
, p
))
1305 ephi_backward (p
, visited
, pred
, nodes
);
1306 emit_move_insn (nodes
[p
], reg_u
);
1312 /* No cycle. Just copy the value from a successor. */
1315 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1317 SET_BIT (visited
, t
);
1318 emit_move_insn (nodes
[t
], nodes
[s
]);
1324 /* Convert the edge to normal form. */
1327 eliminate_phi (e
, reg_partition
)
1329 partition reg_partition
;
1332 sbitmap
*pred
, *succ
;
1335 int *stack
, *tstack
;
1339 /* Collect an upper bound on the number of registers needing processing. */
1341 insn
= first_insn_after_basic_block_note (e
->dest
);
1344 while (PHI_NODE_P (insn
))
1346 insn
= next_nonnote_insn (insn
);
1353 /* Build the auxilliary graph R(B).
1355 The nodes of the graph are the members of the register partition
1356 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1357 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1359 nodes
= (rtx
*) alloca (n_nodes
* sizeof(rtx
));
1360 pred
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1361 succ
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1362 sbitmap_vector_zero (pred
, n_nodes
);
1363 sbitmap_vector_zero (succ
, n_nodes
);
1365 insn
= first_insn_after_basic_block_note (e
->dest
);
1368 for (; PHI_NODE_P (insn
); insn
= next_nonnote_insn (insn
))
1370 rtx
* preg
= phi_alternative (PATTERN (insn
), e
->src
->index
);
1371 rtx tgt
= SET_DEST (PATTERN (insn
));
1374 /* There may be no phi alternative corresponding to this edge.
1375 This indicates that the phi variable is undefined along this
1381 if (GET_CODE (reg
) != REG
|| GET_CODE (tgt
) != REG
)
1384 reg
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (reg
))];
1385 tgt
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (tgt
))];
1386 /* If the two registers are already in the same partition,
1387 nothing will need to be done. */
1392 ireg
= ephi_add_node (reg
, nodes
, &n_nodes
);
1393 itgt
= ephi_add_node (tgt
, nodes
, &n_nodes
);
1395 SET_BIT (pred
[ireg
], itgt
);
1396 SET_BIT (succ
[itgt
], ireg
);
1403 /* Begin a topological sort of the graph. */
1405 visited
= sbitmap_alloc (n_nodes
);
1406 sbitmap_zero (visited
);
1408 tstack
= stack
= (int *) alloca (n_nodes
* sizeof (int));
1410 for (i
= 0; i
< n_nodes
; ++i
)
1411 if (! TEST_BIT (visited
, i
))
1412 tstack
= ephi_forward (i
, visited
, succ
, tstack
);
1414 sbitmap_zero (visited
);
1416 /* As we find a solution to the tsort, collect the implementation
1417 insns in a sequence. */
1420 while (tstack
!= stack
)
1423 if (! TEST_BIT (visited
, i
))
1424 ephi_create (i
, visited
, pred
, succ
, nodes
);
1427 insn
= gen_sequence ();
1429 insert_insn_on_edge (insn
, e
);
1431 fprintf (rtl_dump_file
, "Emitting copy on edge (%d,%d)\n",
1432 e
->src
->index
, e
->dest
->index
);
1434 sbitmap_free (visited
);
1436 sbitmap_vector_free (pred
);
1437 sbitmap_vector_free (succ
);
1440 /* For basic block B, consider all phi insns which provide an
1441 alternative corresponding to an incoming abnormal critical edge.
1442 Place the phi alternative corresponding to that abnormal critical
1443 edge in the same register class as the destination of the set.
1445 From Morgan, p. 178:
1447 For each abnormal critical edge (C, B),
1448 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1449 and C is the ith predecessor of B,
1450 then T0 and Ti must be equivalent.
1452 Return non-zero iff any such cases were found for which the two
1453 regs were not already in the same class. */
1456 make_regs_equivalent_over_bad_edges (bb
, reg_partition
)
1458 partition reg_partition
;
1461 basic_block b
= BASIC_BLOCK (bb
);
1464 /* Advance to the first phi node. */
1465 phi
= first_insn_after_basic_block_note (b
);
1467 /* Scan all the phi nodes. */
1470 phi
= next_nonnote_insn (phi
))
1474 rtx set
= PATTERN (phi
);
1475 rtx tgt
= SET_DEST (set
);
1477 /* The set target is expected to be an SSA register. */
1478 if (GET_CODE (tgt
) != REG
1479 || !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt
)))
1481 tgt_regno
= REGNO (tgt
);
1483 /* Scan incoming abnormal critical edges. */
1484 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1485 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1486 == (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1488 rtx
*alt
= phi_alternative (set
, e
->src
->index
);
1491 /* If there is no alternative corresponding to this edge,
1492 the value is undefined along the edge, so just go on. */
1496 /* The phi alternative is expected to be an SSA register. */
1497 if (GET_CODE (*alt
) != REG
1498 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1500 alt_regno
= REGNO (*alt
);
1502 /* If the set destination and the phi alternative aren't
1503 already in the same class... */
1504 if (partition_find (reg_partition
, tgt_regno
)
1505 != partition_find (reg_partition
, alt_regno
))
1507 /* ... make them such. */
1508 if (conflicting_hard_regs_p (tgt_regno
, alt_regno
))
1509 /* It is illegal to unify a hard register with a
1510 different register. */
1513 partition_union (reg_partition
,
1514 tgt_regno
, alt_regno
);
1523 /* Consider phi insns in basic block BB pairwise. If the set target
1524 of both isns are equivalent pseudos, make the corresponding phi
1525 alternatives in each phi corresponding equivalent.
1527 Return nonzero if any new register classes were unioned. */
1530 make_equivalent_phi_alternatives_equivalent (bb
, reg_partition
)
1532 partition reg_partition
;
1535 basic_block b
= BASIC_BLOCK (bb
);
1538 /* Advance to the first phi node. */
1539 phi
= first_insn_after_basic_block_note (b
);
1541 /* Scan all the phi nodes. */
1544 phi
= next_nonnote_insn (phi
))
1546 rtx set
= PATTERN (phi
);
1547 /* The regno of the destination of the set. */
1548 int tgt_regno
= REGNO (SET_DEST (PATTERN (phi
)));
1550 rtx phi2
= next_nonnote_insn (phi
);
1552 /* Scan all phi nodes following this one. */
1555 phi2
= next_nonnote_insn (phi2
))
1557 rtx set2
= PATTERN (phi2
);
1558 /* The regno of the destination of the set. */
1559 int tgt2_regno
= REGNO (SET_DEST (set2
));
1561 /* Are the set destinations equivalent regs? */
1562 if (partition_find (reg_partition
, tgt_regno
) ==
1563 partition_find (reg_partition
, tgt2_regno
))
1566 /* Scan over edges. */
1567 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1569 int pred_block
= e
->src
->index
;
1570 /* Identify the phi alternatives from both phi
1571 nodes corresponding to this edge. */
1572 rtx
*alt
= phi_alternative (set
, pred_block
);
1573 rtx
*alt2
= phi_alternative (set2
, pred_block
);
1575 /* If one of the phi nodes doesn't have a
1576 corresponding alternative, just skip it. */
1577 if (alt
== 0 || alt2
== 0)
1580 /* Both alternatives should be SSA registers. */
1581 if (GET_CODE (*alt
) != REG
1582 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1584 if (GET_CODE (*alt2
) != REG
1585 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2
)))
1588 /* If the alternatives aren't already in the same
1590 if (partition_find (reg_partition
, REGNO (*alt
))
1591 != partition_find (reg_partition
, REGNO (*alt2
)))
1593 /* ... make them so. */
1594 if (conflicting_hard_regs_p (REGNO (*alt
), REGNO (*alt2
)))
1595 /* It is illegal to unify a hard register with
1596 a different register. */
1599 partition_union (reg_partition
,
1600 REGNO (*alt
), REGNO (*alt2
));
1611 /* Compute a conservative partition of outstanding pseudo registers.
1612 See Morgan 7.3.1. */
1615 compute_conservative_reg_partition ()
1620 /* We don't actually work with hard registers, but it's easier to
1621 carry them around anyway rather than constantly doing register
1622 number arithmetic. */
1624 partition_new (ssa_definition
->num_elements
);
1626 /* The first priority is to make sure registers that might have to
1627 be copied on abnormal critical edges are placed in the same
1628 partition. This saves us from having to split abnormal critical
1630 for (bb
= n_basic_blocks
; --bb
>= 0; )
1631 changed
+= make_regs_equivalent_over_bad_edges (bb
, p
);
1633 /* Now we have to insure that corresponding arguments of phi nodes
1634 assigning to corresponding regs are equivalent. Iterate until
1639 for (bb
= n_basic_blocks
; --bb
>= 0; )
1640 changed
+= make_equivalent_phi_alternatives_equivalent (bb
, p
);
1646 /* The following functions compute a register partition that attempts
1647 to eliminate as many reg copies and phi node copies as possible by
1648 coalescing registers. This is the strategy:
1650 1. As in the conservative case, the top priority is to coalesce
1651 registers that otherwise would cause copies to be placed on
1652 abnormal critical edges (which isn't possible).
1654 2. Figure out which regs are involved (in the LHS or RHS) of
1655 copies and phi nodes. Compute conflicts among these regs.
1657 3. Walk around the instruction stream, placing two regs in the
1658 same class of the partition if one appears on the LHS and the
1659 other on the RHS of a copy or phi node and the two regs don't
1660 conflict. The conflict information of course needs to be
1663 4. If anything has changed, there may be new opportunities to
1664 coalesce regs, so go back to 2.
1667 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1668 same class of partition P, if they aren't already. Update
1669 CONFLICTS appropriately.
1671 Returns one if REG1 and REG2 were placed in the same class but were
1672 not previously; zero otherwise.
1674 See Morgan figure 11.15. */
1677 coalesce_if_unconflicting (p
, conflicts
, reg1
, reg2
)
1679 conflict_graph conflicts
;
1685 /* Work only on SSA registers. */
1686 if (!CONVERT_REGISTER_TO_SSA_P (reg1
) || !CONVERT_REGISTER_TO_SSA_P (reg2
))
1689 /* Find the canonical regs for the classes containing REG1 and
1691 reg1
= partition_find (p
, reg1
);
1692 reg2
= partition_find (p
, reg2
);
1694 /* If they're already in the same class, there's nothing to do. */
1698 /* If the regs conflict, our hands are tied. */
1699 if (conflicting_hard_regs_p (reg1
, reg2
) ||
1700 conflict_graph_conflict_p (conflicts
, reg1
, reg2
))
1703 /* We're good to go. Put the regs in the same partition. */
1704 partition_union (p
, reg1
, reg2
);
1706 /* Find the new canonical reg for the merged class. */
1707 reg
= partition_find (p
, reg1
);
1709 /* Merge conflicts from the two previous classes. */
1710 conflict_graph_merge_regs (conflicts
, reg
, reg1
);
1711 conflict_graph_merge_regs (conflicts
, reg
, reg2
);
1716 /* For each register copy insn in basic block BB, place the LHS and
1717 RHS regs in the same class in partition P if they do not conflict
1718 according to CONFLICTS.
1720 Returns the number of changes that were made to P.
1722 See Morgan figure 11.14. */
1725 coalesce_regs_in_copies (bb
, p
, conflicts
)
1728 conflict_graph conflicts
;
1734 /* Scan the instruction stream of the block. */
1735 for (insn
= bb
->head
; insn
!= end
; insn
= NEXT_INSN (insn
))
1741 /* If this isn't a set insn, go to the next insn. */
1742 if (GET_CODE (insn
) != INSN
)
1744 pattern
= PATTERN (insn
);
1745 if (GET_CODE (pattern
) != SET
)
1748 src
= SET_SRC (pattern
);
1749 dest
= SET_DEST (pattern
);
1751 /* We're only looking for copies. */
1752 if (GET_CODE (src
) != REG
|| GET_CODE (dest
) != REG
)
1755 /* Coalesce only if the reg modes are the same. As long as
1756 each reg's rtx is unique, it can have only one mode, so two
1757 pseudos of different modes can't be coalesced into one.
1759 FIXME: We can probably get around this by inserting SUBREGs
1760 where appropriate, but for now we don't bother. */
1761 if (GET_MODE (src
) != GET_MODE (dest
))
1764 /* Found a copy; see if we can use the same reg for both the
1765 source and destination (and thus eliminate the copy,
1767 changed
+= coalesce_if_unconflicting (p
, conflicts
,
1768 REGNO (src
), REGNO (dest
));
1774 struct phi_coalesce_context
1777 conflict_graph conflicts
;
1781 /* Callback function for for_each_successor_phi. If the set
1782 destination and the phi alternative regs do not conflict, place
1783 them in the same paritition class. DATA is a pointer to a
1784 phi_coalesce_context struct. */
1787 coalesce_reg_in_phi (insn
, dest_regno
, src_regno
, data
)
1788 rtx insn ATTRIBUTE_UNUSED
;
1793 struct phi_coalesce_context
*context
=
1794 (struct phi_coalesce_context
*) data
;
1796 /* Attempt to use the same reg, if they don't conflict. */
1798 += coalesce_if_unconflicting (context
->p
, context
->conflicts
,
1799 dest_regno
, src_regno
);
1803 /* For each alternative in a phi function corresponding to basic block
1804 BB (in phi nodes in successor block to BB), place the reg in the
1805 phi alternative and the reg to which the phi value is set into the
1806 same class in partition P, if allowed by CONFLICTS.
1808 Return the number of changes that were made to P.
1810 See Morgan figure 11.14. */
1813 coalesce_regs_in_successor_phi_nodes (bb
, p
, conflicts
)
1816 conflict_graph conflicts
;
1818 struct phi_coalesce_context context
;
1820 context
.conflicts
= conflicts
;
1821 context
.changed
= 0;
1823 for_each_successor_phi (bb
, &coalesce_reg_in_phi
, &context
);
1825 return context
.changed
;
1828 /* Compute and return a partition of pseudos. Where possible,
1829 non-conflicting pseudos are placed in the same class.
1831 The caller is responsible for deallocating the returned partition. */
1834 compute_coalesced_reg_partition ()
1840 partition_new (ssa_definition
->num_elements
);
1842 /* The first priority is to make sure registers that might have to
1843 be copied on abnormal critical edges are placed in the same
1844 partition. This saves us from having to split abnormal critical
1845 edges (which can't be done). */
1846 for (bb
= n_basic_blocks
; --bb
>= 0; )
1847 make_regs_equivalent_over_bad_edges (bb
, p
);
1851 regset_head phi_set
;
1852 conflict_graph conflicts
;
1856 /* Build the set of registers involved in phi nodes, either as
1857 arguments to the phi function or as the target of a set. */
1858 INITIALIZE_REG_SET (phi_set
);
1859 mark_phi_and_copy_regs (&phi_set
);
1861 /* Compute conflicts. */
1862 conflicts
= conflict_graph_compute (&phi_set
, p
);
1864 /* FIXME: Better would be to process most frequently executed
1865 blocks first, so that most frequently executed copies would
1866 be more likely to be removed by register coalescing. But any
1867 order will generate correct, if non-optimal, results. */
1868 for (bb
= n_basic_blocks
; --bb
>= 0; )
1870 basic_block block
= BASIC_BLOCK (bb
);
1871 changed
+= coalesce_regs_in_copies (block
, p
, conflicts
);
1873 coalesce_regs_in_successor_phi_nodes (block
, p
, conflicts
);
1876 conflict_graph_delete (conflicts
);
1878 while (changed
> 0);
1883 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1884 components (a REG or a CONST_INT). DATA is a reg set in which to
1885 set all regs. Called from for_each_rtx. */
1888 mark_reg_in_phi (ptr
, data
)
1893 regset set
= (regset
) data
;
1895 switch (GET_CODE (expr
))
1898 SET_REGNO_REG_SET (set
, REGNO (expr
));
1908 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1909 set from a phi expression, or used as an argument in one. Also
1910 mark regs that are the source or target of a reg copy. Uses
1914 mark_phi_and_copy_regs (phi_set
)
1919 /* Scan the definitions of all regs. */
1920 for (reg
= 0; reg
< VARRAY_SIZE (ssa_definition
); ++reg
)
1921 if (CONVERT_REGISTER_TO_SSA_P (reg
))
1923 rtx insn
= VARRAY_RTX (ssa_definition
, reg
);
1928 || (GET_CODE (insn
) == NOTE
1929 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
))
1931 pattern
= PATTERN (insn
);
1932 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1934 if (GET_CODE (pattern
) != SET
)
1936 src
= SET_SRC (pattern
);
1938 if (GET_CODE (src
) == REG
)
1940 /* It's a reg copy. */
1941 SET_REGNO_REG_SET (phi_set
, reg
);
1942 SET_REGNO_REG_SET (phi_set
, REGNO (src
));
1944 else if (GET_CODE (src
) == PHI
)
1946 /* It's a phi node. Mark the reg being set. */
1947 SET_REGNO_REG_SET (phi_set
, reg
);
1948 /* Mark the regs used in the phi function. */
1949 for_each_rtx (&src
, mark_reg_in_phi
, phi_set
);
1951 /* ... else nothing to do. */
1955 /* Rename regs in insn PTR that are equivalent. DATA is the register
1956 partition which specifies equivalences. */
1959 rename_equivalent_regs_in_insn (ptr
, data
)
1964 partition reg_partition
= (partition
) data
;
1969 switch (GET_CODE (x
))
1972 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)))
1974 unsigned int regno
= REGNO (x
);
1975 unsigned int new_regno
= partition_find (reg_partition
, regno
);
1976 rtx canonical_element_rtx
= ssa_rename_from_lookup (new_regno
);
1978 if (canonical_element_rtx
!= NULL_RTX
&&
1979 HARD_REGISTER_P (canonical_element_rtx
))
1981 if (REGNO (canonical_element_rtx
) != regno
)
1982 *ptr
= canonical_element_rtx
;
1984 else if (regno
!= new_regno
)
1986 rtx new_reg
= regno_reg_rtx
[new_regno
];
1987 if (GET_MODE (x
) != GET_MODE (new_reg
))
1995 /* No need to rename the phi nodes. We'll check equivalence
1996 when inserting copies. */
2000 /* Anything else, continue traversing. */
2005 /* Record the register's canonical element stored in SRFP in the
2006 canonical_elements sbitmap packaged in DATA. This function is used
2007 as a callback function for traversing ssa_rename_from. */
2010 record_canonical_element_1 (srfp
, data
)
2014 unsigned int reg
= ((ssa_rename_from_pair
*) *srfp
)->reg
;
2015 sbitmap canonical_elements
=
2016 ((struct ssa_rename_from_hash_table_data
*) data
)->canonical_elements
;
2017 partition reg_partition
=
2018 ((struct ssa_rename_from_hash_table_data
*) data
)->reg_partition
;
2020 SET_BIT (canonical_elements
, partition_find (reg_partition
, reg
));
2024 /* For each class in the REG_PARTITION corresponding to a particular
2025 hard register and machine mode, check that there are no other
2026 classes with the same hard register and machine mode. Returns
2027 nonzero if this is the case, i.e., the partition is acceptable. */
2030 check_hard_regs_in_partition (reg_partition
)
2031 partition reg_partition
;
2033 /* CANONICAL_ELEMENTS has a nonzero bit if a class with the given register
2034 number and machine mode has already been seen. This is a
2035 problem with the partition. */
2036 sbitmap canonical_elements
;
2038 int already_seen
[FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
2042 /* Collect a list of canonical elements. */
2043 canonical_elements
= sbitmap_alloc (max_reg_num ());
2044 sbitmap_zero (canonical_elements
);
2045 ssa_rename_from_traverse (&record_canonical_element_1
,
2046 canonical_elements
, reg_partition
);
2048 /* We have not seen any hard register uses. */
2049 for (reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; ++reg
)
2050 for (mach_mode
= 0; mach_mode
< NUM_MACHINE_MODES
; ++mach_mode
)
2051 already_seen
[reg
][mach_mode
] = 0;
2053 /* Check for classes with the same hard register and machine mode. */
2054 EXECUTE_IF_SET_IN_SBITMAP (canonical_elements
, 0, element_index
,
2056 rtx hard_reg_rtx
= ssa_rename_from_lookup (element_index
);
2057 if (hard_reg_rtx
!= NULL_RTX
&&
2058 HARD_REGISTER_P (hard_reg_rtx
) &&
2059 already_seen
[REGNO (hard_reg_rtx
)][GET_MODE (hard_reg_rtx
)] != 0)
2060 /* Two distinct partition classes should be mapped to the same
2065 sbitmap_free (canonical_elements
);
2070 /* Rename regs that are equivalent in REG_PARTITION. Also collapse
2071 any SEQUENCE insns. */
2074 rename_equivalent_regs (reg_partition
)
2075 partition reg_partition
;
2079 for (bb
= n_basic_blocks
; --bb
>= 0; )
2081 basic_block b
= BASIC_BLOCK (bb
);
2091 for_each_rtx (&PATTERN (insn
),
2092 rename_equivalent_regs_in_insn
,
2094 for_each_rtx (®_NOTES (insn
),
2095 rename_equivalent_regs_in_insn
,
2098 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
2100 rtx s
= PATTERN (insn
);
2101 int slen
= XVECLEN (s
, 0);
2107 PATTERN (insn
) = XVECEXP (s
, 0, slen
-1);
2108 for (i
= 0; i
< slen
- 1; i
++)
2109 emit_block_insn_before (XVECEXP (s
, 0, i
), insn
, b
);
2113 next
= NEXT_INSN (insn
);
2115 while (insn
!= last
);
2119 /* The main entry point for moving from SSA. */
2125 partition reg_partition
;
2126 rtx insns
= get_insns ();
2128 /* Need global_live_at_{start,end} up to date. There should not be
2129 any significant dead code at this point, except perhaps dead
2130 stores. So do not take the time to perform dead code elimination.
2132 Register coalescing needs death notes, so generate them. */
2133 life_analysis (insns
, NULL
, PROP_DEATH_NOTES
);
2135 /* Figure out which regs in copies and phi nodes don't conflict and
2136 therefore can be coalesced. */
2137 if (conservative_reg_partition
)
2138 reg_partition
= compute_conservative_reg_partition ();
2140 reg_partition
= compute_coalesced_reg_partition ();
2142 if (!check_hard_regs_in_partition (reg_partition
))
2143 /* Two separate partitions should correspond to the same hard
2144 register but do not. */
2147 rename_equivalent_regs (reg_partition
);
2149 /* Eliminate the PHI nodes. */
2150 for (bb
= n_basic_blocks
; --bb
>= 0; )
2152 basic_block b
= BASIC_BLOCK (bb
);
2155 for (e
= b
->pred
; e
; e
= e
->pred_next
)
2156 if (e
->src
!= ENTRY_BLOCK_PTR
)
2157 eliminate_phi (e
, reg_partition
);
2160 partition_delete (reg_partition
);
2162 /* Actually delete the PHI nodes. */
2163 for (bb
= n_basic_blocks
; --bb
>= 0; )
2165 rtx insn
= BLOCK_HEAD (bb
);
2169 /* If this is a PHI node delete it. */
2170 if (PHI_NODE_P (insn
))
2172 if (insn
== BLOCK_END (bb
))
2173 BLOCK_END (bb
) = PREV_INSN (insn
);
2174 insn
= delete_insn (insn
);
2176 /* Since all the phi nodes come at the beginning of the
2177 block, if we find an ordinary insn, we can stop looking
2178 for more phi nodes. */
2179 else if (INSN_P (insn
))
2181 /* If we've reached the end of the block, stop. */
2182 else if (insn
== BLOCK_END (bb
))
2185 insn
= NEXT_INSN (insn
);
2189 /* Commit all the copy nodes needed to convert out of SSA form. */
2190 commit_edge_insertions ();
2194 count_or_remove_death_notes (NULL
, 1);
2196 /* Deallocate the data structures. */
2197 VARRAY_FREE (ssa_definition
);
2198 ssa_rename_from_free ();
2201 /* Scan phi nodes in successors to BB. For each such phi node that
2202 has a phi alternative value corresponding to BB, invoke FN. FN
2203 is passed the entire phi node insn, the regno of the set
2204 destination, the regno of the phi argument corresponding to BB,
2207 If FN ever returns non-zero, stops immediately and returns this
2208 value. Otherwise, returns zero. */
2211 for_each_successor_phi (bb
, fn
, data
)
2213 successor_phi_fn fn
;
2218 if (bb
== EXIT_BLOCK_PTR
)
2221 /* Scan outgoing edges. */
2222 for (e
= bb
->succ
; e
!= NULL
; e
= e
->succ_next
)
2226 basic_block successor
= e
->dest
;
2227 if (successor
== ENTRY_BLOCK_PTR
2228 || successor
== EXIT_BLOCK_PTR
)
2231 /* Advance to the first non-label insn of the successor block. */
2232 insn
= first_insn_after_basic_block_note (successor
);
2237 /* Scan phi nodes in the successor. */
2238 for ( ; PHI_NODE_P (insn
); insn
= NEXT_INSN (insn
))
2241 rtx phi_set
= PATTERN (insn
);
2242 rtx
*alternative
= phi_alternative (phi_set
, bb
->index
);
2245 /* This phi function may not have an alternative
2246 corresponding to the incoming edge, indicating the
2247 assigned variable is not defined along the edge. */
2248 if (alternative
== NULL
)
2250 phi_src
= *alternative
;
2252 /* Invoke the callback. */
2253 result
= (*fn
) (insn
, REGNO (SET_DEST (phi_set
)),
2254 REGNO (phi_src
), data
);
2256 /* Terminate if requested. */
2265 /* Assuming the ssa_rename_from mapping has been established, yields
2266 nonzero if 1) only one SSA register of REG1 and REG2 comes from a
2267 hard register or 2) both SSA registers REG1 and REG2 come from
2268 different hard registers. */
2271 conflicting_hard_regs_p (reg1
, reg2
)
2275 int orig_reg1
= original_register (reg1
);
2276 int orig_reg2
= original_register (reg2
);
2277 if (HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
)
2278 && orig_reg1
!= orig_reg2
)
2280 if (HARD_REGISTER_NUM_P (orig_reg1
) && !HARD_REGISTER_NUM_P (orig_reg2
))
2282 if (!HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
))