1 /* Static Single Assignment conversion routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 Building an Optimizing Compiler
26 Butterworth-Heinemann, 1998
28 Static Single Assignment Construction
29 Preston Briggs, Tim Harvey, Taylor Simpson
30 Technical Report, Rice University, 1995
31 ftp://ftp.cs.rice.edu/public/preston/optimizer/SSA.ps.gz. */
35 #include "coretypes.h"
41 #include "partition.h"
45 #include "hard-reg-set.h"
49 #include "insn-config.h"
51 #include "basic-block.h"
57 Handle subregs better, maybe. For now, if a reg that's set in a
58 subreg expression is duplicated going into SSA form, an extra copy
59 is inserted first that copies the entire reg into the duplicate, so
60 that the other bits are preserved. This isn't strictly SSA, since
61 at least part of the reg is assigned in more than one place (though
64 ??? What to do about strict_low_part. Probably I'll have to split
65 them out of their current instructions first thing.
67 Actually the best solution may be to have a kind of "mid-level rtl"
68 in which the RTL encodes exactly what we want, without exposing a
69 lot of niggling processor details. At some later point we lower
70 the representation, calling back into optabs to finish any necessary
73 /* All pseudo-registers and select hard registers are converted to SSA
74 form. When converting out of SSA, these select hard registers are
75 guaranteed to be mapped to their original register number. Each
76 machine's .h file should define CONVERT_HARD_REGISTER_TO_SSA_P
77 indicating which hard registers should be converted.
79 When converting out of SSA, temporaries for all registers are
80 partitioned. The partition is checked to ensure that all uses of
81 the same hard register in the same machine mode are in the same
84 /* If conservative_reg_partition is nonzero, use a conservative
85 register partitioning algorithm (which leaves more regs after
86 emerging from SSA) instead of the coalescing one. This is being
87 left in for a limited time only, as a debugging tool until the
88 coalescing algorithm is validated. */
90 static int conservative_reg_partition
;
92 /* This flag is set when the CFG is in SSA form. */
95 /* Element I is the single instruction that sets register I. */
96 varray_type ssa_definition
;
98 /* Element I-PSEUDO is the normal register that originated the ssa
99 register in question. */
100 varray_type ssa_rename_from
;
102 /* Element I is the normal register that originated the ssa
103 register in question.
105 A hash table stores the (register, rtl) pairs. These are each
106 xmalloc'ed and deleted when the hash table is destroyed. */
107 htab_t ssa_rename_from_ht
;
109 /* The running target ssa register for a given pseudo register.
110 (Pseudo registers appear in only one mode.) */
111 static rtx
*ssa_rename_to_pseudo
;
112 /* Similar, but for hard registers. A hard register can appear in
113 many modes, so we store an equivalent pseudo for each of the
115 static rtx ssa_rename_to_hard
[FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
117 /* ssa_rename_from maps pseudo registers to the original corresponding
118 RTL. It is implemented as using a hash table. */
123 } ssa_rename_from_pair
;
125 struct ssa_rename_from_hash_table_data
{
126 sbitmap canonical_elements
;
127 partition reg_partition
;
130 static rtx
gen_sequence (void);
131 static void ssa_rename_from_initialize (void);
132 static rtx
ssa_rename_from_lookup (int reg
);
133 static unsigned int original_register (unsigned int regno
);
134 static void ssa_rename_from_insert (unsigned int reg
, rtx r
);
135 static void ssa_rename_from_free (void);
136 typedef int (*srf_trav
) (int regno
, rtx r
, sbitmap canonical_elements
,
137 partition reg_partition
);
138 static void ssa_rename_from_traverse (htab_trav callback_function
,
139 sbitmap canonical_elements
, partition reg_partition
);
140 /*static Avoid warning message. */ void ssa_rename_from_print (void);
141 static int ssa_rename_from_print_1 (void **slot
, void *data
);
142 static hashval_t
ssa_rename_from_hash_function (const void * srfp
);
143 static int ssa_rename_from_equal (const void *srfp1
, const void *srfp2
);
144 static void ssa_rename_from_delete (void *srfp
);
146 static rtx
ssa_rename_to_lookup (rtx reg
);
147 static void ssa_rename_to_insert (rtx reg
, rtx r
);
149 /* The number of registers that were live on entry to the SSA routines. */
150 static unsigned int ssa_max_reg_num
;
152 /* Local function prototypes. */
154 struct rename_context
;
156 static inline rtx
* phi_alternative (rtx
, int);
157 static void compute_dominance_frontiers_1 (sbitmap
*frontiers
,
158 dominance_info idom
, int bb
,
160 static void find_evaluations_1 (rtx dest
, rtx set
, void *data
);
161 static void find_evaluations (sbitmap
*evals
, int nregs
);
162 static void compute_iterated_dominance_frontiers (sbitmap
*idfs
,
164 sbitmap
*evals
, int nregs
);
165 static void insert_phi_node (int regno
, int b
);
166 static void insert_phi_nodes (sbitmap
*idfs
, sbitmap
*evals
, int nregs
);
167 static void create_delayed_rename (struct rename_context
*, rtx
*);
168 static void apply_delayed_renames (struct rename_context
*);
169 static int rename_insn_1 (rtx
*ptr
, void *data
);
170 static void rename_block (int b
, dominance_info dom
);
171 static void rename_registers (int nregs
, dominance_info idom
);
173 static inline int ephi_add_node (rtx reg
, rtx
*nodes
, int *n_nodes
);
174 static int * ephi_forward (int t
, sbitmap visited
, sbitmap
*succ
, int *tstack
);
175 static void ephi_backward (int t
, sbitmap visited
, sbitmap
*pred
, rtx
*nodes
);
176 static void ephi_create (int t
, sbitmap visited
, sbitmap
*pred
,
177 sbitmap
*succ
, rtx
*nodes
);
178 static void eliminate_phi (edge e
, partition reg_partition
);
179 static int make_regs_equivalent_over_bad_edges (int bb
,
180 partition reg_partition
);
182 /* These are used only in the conservative register partitioning
184 static int make_equivalent_phi_alternatives_equivalent
185 (int bb
, partition reg_partition
);
186 static partition
compute_conservative_reg_partition (void);
187 static int record_canonical_element_1 (void **srfp
, void *data
);
188 static int check_hard_regs_in_partition (partition reg_partition
);
190 /* These are used in the register coalescing algorithm. */
191 static int coalesce_if_unconflicting (partition p
, conflict_graph conflicts
,
193 static int coalesce_regs_in_copies (basic_block bb
, partition p
,
194 conflict_graph conflicts
);
195 static int coalesce_reg_in_phi (rtx
, int dest_regno
, int src_regno
,
197 static int coalesce_regs_in_successor_phi_nodes (basic_block bb
,
199 conflict_graph conflicts
);
200 static partition
compute_coalesced_reg_partition (void);
201 static int mark_reg_in_phi (rtx
*ptr
, void *data
);
202 static void mark_phi_and_copy_regs (regset phi_set
);
204 static int rename_equivalent_regs_in_insn (rtx
*ptr
, void *data
);
205 static void rename_equivalent_regs (partition reg_partition
);
207 /* Deal with hard registers. */
208 static int conflicting_hard_regs_p (int reg1
, int reg2
);
210 /* ssa_rename_to maps registers and machine modes to SSA pseudo registers. */
212 /* Find the register associated with REG in the indicated mode. */
215 ssa_rename_to_lookup (rtx reg
)
217 if (!HARD_REGISTER_P (reg
))
218 return ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
];
220 return ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)];
223 /* Store a new value mapping REG to R in ssa_rename_to. */
226 ssa_rename_to_insert (rtx reg
, rtx r
)
228 if (!HARD_REGISTER_P (reg
))
229 ssa_rename_to_pseudo
[REGNO (reg
) - FIRST_PSEUDO_REGISTER
] = r
;
231 ssa_rename_to_hard
[REGNO (reg
)][GET_MODE (reg
)] = r
;
234 /* Prepare ssa_rename_from for use. */
237 ssa_rename_from_initialize (void)
239 /* We use an arbitrary initial hash table size of 64. */
240 ssa_rename_from_ht
= htab_create (64,
241 &ssa_rename_from_hash_function
,
242 &ssa_rename_from_equal
,
243 &ssa_rename_from_delete
);
246 /* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
250 ssa_rename_from_lookup (int reg
)
252 ssa_rename_from_pair srfp
;
253 ssa_rename_from_pair
*answer
;
255 srfp
.original
= NULL_RTX
;
256 answer
= htab_find_with_hash (ssa_rename_from_ht
, (void *) &srfp
, reg
);
257 return (answer
== 0 ? NULL_RTX
: answer
->original
);
260 /* Find the number of the original register specified by REGNO. If
261 the register is a pseudo, return the original register's number.
262 Otherwise, return this register number REGNO. */
265 original_register (unsigned int regno
)
267 rtx original_rtx
= ssa_rename_from_lookup (regno
);
268 return original_rtx
!= NULL_RTX
? REGNO (original_rtx
) : regno
;
271 /* Add mapping from R to REG to ssa_rename_from even if already present. */
274 ssa_rename_from_insert (unsigned int reg
, rtx r
)
277 ssa_rename_from_pair
*srfp
= xmalloc (sizeof (ssa_rename_from_pair
));
280 slot
= htab_find_slot_with_hash (ssa_rename_from_ht
, (const void *) srfp
,
283 free ((void *) *slot
);
287 /* Apply the CALLBACK_FUNCTION to each element in ssa_rename_from.
288 CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
289 current use of this function. */
292 ssa_rename_from_traverse (htab_trav callback_function
,
293 sbitmap canonical_elements
, partition reg_partition
)
295 struct ssa_rename_from_hash_table_data srfhd
;
296 srfhd
.canonical_elements
= canonical_elements
;
297 srfhd
.reg_partition
= reg_partition
;
298 htab_traverse (ssa_rename_from_ht
, callback_function
, (void *) &srfhd
);
301 /* Destroy ssa_rename_from. */
304 ssa_rename_from_free (void)
306 htab_delete (ssa_rename_from_ht
);
309 /* Print the contents of ssa_rename_from. */
311 /* static Avoid erroneous error message. */
313 ssa_rename_from_print (void)
315 printf ("ssa_rename_from's hash table contents:\n");
316 htab_traverse (ssa_rename_from_ht
, &ssa_rename_from_print_1
, NULL
);
319 /* Print the contents of the hash table entry SLOT, passing the unused
320 attribute DATA. Used as a callback function with htab_traverse (). */
323 ssa_rename_from_print_1 (void **slot
, void *data ATTRIBUTE_UNUSED
)
325 ssa_rename_from_pair
* p
= *slot
;
326 printf ("ssa_rename_from maps pseudo %i to original %i.\n",
327 p
->reg
, REGNO (p
->original
));
331 /* Given a hash entry SRFP, yield a hash value. */
334 ssa_rename_from_hash_function (const void *srfp
)
336 return ((const ssa_rename_from_pair
*) srfp
)->reg
;
339 /* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
342 ssa_rename_from_equal (const void *srfp1
, const void *srfp2
)
344 return ssa_rename_from_hash_function (srfp1
) ==
345 ssa_rename_from_hash_function (srfp2
);
348 /* Delete the hash table entry SRFP. */
351 ssa_rename_from_delete (void *srfp
)
356 /* Given the SET of a PHI node, return the address of the alternative
357 for predecessor block C. */
360 phi_alternative (rtx set
, int c
)
362 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
365 for (v
= GET_NUM_ELEM (phi_vec
) - 2; v
>= 0; v
-= 2)
366 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
367 return &RTVEC_ELT (phi_vec
, v
);
372 /* Given the SET of a phi node, remove the alternative for predecessor
373 block C. Return nonzero on success, or zero if no alternative is
377 remove_phi_alternative (rtx set
, basic_block block
)
379 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
380 int num_elem
= GET_NUM_ELEM (phi_vec
);
384 for (v
= num_elem
- 2; v
>= 0; v
-= 2)
385 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
387 if (v
< num_elem
- 2)
389 RTVEC_ELT (phi_vec
, v
) = RTVEC_ELT (phi_vec
, num_elem
- 2);
390 RTVEC_ELT (phi_vec
, v
+ 1) = RTVEC_ELT (phi_vec
, num_elem
- 1);
392 PUT_NUM_ELEM (phi_vec
, num_elem
- 2);
399 /* For all registers, find all blocks in which they are set.
401 This is the transform of what would be local kill information that
402 we ought to be getting from flow. */
404 static sbitmap
*fe_evals
;
405 static int fe_current_bb
;
408 find_evaluations_1 (rtx dest
, rtx set ATTRIBUTE_UNUSED
,
409 void *data ATTRIBUTE_UNUSED
)
411 if (GET_CODE (dest
) == REG
412 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
413 SET_BIT (fe_evals
[REGNO (dest
)], fe_current_bb
);
417 find_evaluations (sbitmap
*evals
, int nregs
)
421 sbitmap_vector_zero (evals
, nregs
);
424 FOR_EACH_BB_REVERSE (bb
)
428 fe_current_bb
= bb
->index
;
434 note_stores (PATTERN (p
), find_evaluations_1
, NULL
);
443 /* Computing the Dominance Frontier:
445 As described in Morgan, section 3.5, this may be done simply by
446 walking the dominator tree bottom-up, computing the frontier for
447 the children before the parent. When considering a block B,
450 (1) A flow graph edge leaving B that does not lead to a child
451 of B in the dominator tree must be a block that is either equal
452 to B or not dominated by B. Such blocks belong in the frontier
455 (2) Consider a block X in the frontier of one of the children C
456 of B. If X is not equal to B and is not dominated by B, it
457 is in the frontier of B.
461 compute_dominance_frontiers_1 (sbitmap
*frontiers
, dominance_info idom
,
462 int bb
, sbitmap done
)
464 basic_block b
= BASIC_BLOCK (bb
);
469 sbitmap_zero (frontiers
[bb
]);
471 /* Do the frontier of the children first. Not all children in the
472 dominator tree (blocks dominated by this one) are children in the
473 CFG, so check all blocks. */
475 if (get_immediate_dominator (idom
, c
)->index
== bb
476 && ! TEST_BIT (done
, c
->index
))
477 compute_dominance_frontiers_1 (frontiers
, idom
, c
->index
, done
);
479 /* Find blocks conforming to rule (1) above. */
480 for (e
= b
->succ
; e
; e
= e
->succ_next
)
482 if (e
->dest
== EXIT_BLOCK_PTR
)
484 if (get_immediate_dominator (idom
, e
->dest
)->index
!= bb
)
485 SET_BIT (frontiers
[bb
], e
->dest
->index
);
488 /* Find blocks conforming to rule (2). */
490 if (get_immediate_dominator (idom
, c
)->index
== bb
)
493 EXECUTE_IF_SET_IN_SBITMAP (frontiers
[c
->index
], 0, x
,
495 if (get_immediate_dominator (idom
, BASIC_BLOCK (x
))->index
!= bb
)
496 SET_BIT (frontiers
[bb
], x
);
502 compute_dominance_frontiers (sbitmap
*frontiers
, dominance_info idom
)
504 sbitmap done
= sbitmap_alloc (last_basic_block
);
507 compute_dominance_frontiers_1 (frontiers
, idom
, 0, done
);
512 /* Computing the Iterated Dominance Frontier:
514 This is the set of merge points for a given register.
516 This is not particularly intuitive. See section 7.1 of Morgan, in
517 particular figures 7.3 and 7.4 and the immediately surrounding text.
521 compute_iterated_dominance_frontiers (sbitmap
*idfs
, sbitmap
*frontiers
,
522 sbitmap
*evals
, int nregs
)
527 worklist
= sbitmap_alloc (last_basic_block
);
529 for (reg
= 0; reg
< nregs
; ++reg
)
531 sbitmap idf
= idfs
[reg
];
534 /* Start the iterative process by considering those blocks that
535 evaluate REG. We'll add their dominance frontiers to the
536 IDF, and then consider the blocks we just added. */
537 sbitmap_copy (worklist
, evals
[reg
]);
539 /* Morgan's algorithm is incorrect here. Blocks that evaluate
540 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
543 /* Iterate until the worklist is empty. */
548 EXECUTE_IF_SET_IN_SBITMAP (worklist
, 0, b
,
550 RESET_BIT (worklist
, b
);
551 /* For each block on the worklist, add to the IDF all
552 blocks on its dominance frontier that aren't already
553 on the IDF. Every block that's added is also added
555 sbitmap_union_of_diff (worklist
, worklist
, frontiers
[b
], idf
);
556 sbitmap_a_or_b (idf
, idf
, frontiers
[b
]);
563 sbitmap_free (worklist
);
567 fprintf (rtl_dump_file
,
568 "Iterated dominance frontier: %d passes on %d regs.\n",
573 /* Insert the phi nodes. */
576 insert_phi_node (int regno
, int bb
)
578 basic_block b
= BASIC_BLOCK (bb
);
586 /* Find out how many predecessors there are. */
587 for (e
= b
->pred
, npred
= 0; e
; e
= e
->pred_next
)
588 if (e
->src
!= ENTRY_BLOCK_PTR
)
591 /* If this block has no "interesting" preds, then there is nothing to
592 do. Consider a block that only has the entry block as a pred. */
596 /* This is the register to which the phi function will be assigned. */
597 reg
= regno_reg_rtx
[regno
];
599 /* Construct the arguments to the PHI node. The use of pc_rtx is just
600 a placeholder; we'll insert the proper value in rename_registers. */
601 vec
= rtvec_alloc (npred
* 2);
602 for (e
= b
->pred
, i
= 0; e
; e
= e
->pred_next
, i
+= 2)
603 if (e
->src
!= ENTRY_BLOCK_PTR
)
605 RTVEC_ELT (vec
, i
+ 0) = pc_rtx
;
606 RTVEC_ELT (vec
, i
+ 1) = GEN_INT (e
->src
->index
);
609 phi
= gen_rtx_PHI (VOIDmode
, vec
);
610 phi
= gen_rtx_SET (VOIDmode
, reg
, phi
);
612 insn
= first_insn_after_basic_block_note (b
);
613 end_p
= PREV_INSN (insn
) == b
->end
;
614 emit_insn_before (phi
, insn
);
616 b
->end
= PREV_INSN (insn
);
620 insert_phi_nodes (sbitmap
*idfs
, sbitmap
*evals ATTRIBUTE_UNUSED
, int nregs
)
624 for (reg
= 0; reg
< nregs
; ++reg
)
625 if (CONVERT_REGISTER_TO_SSA_P (reg
))
628 EXECUTE_IF_SET_IN_SBITMAP (idfs
[reg
], 0, b
,
630 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
, reg
))
631 insert_phi_node (reg
, b
);
636 /* Rename the registers to conform to SSA.
638 This is essentially the algorithm presented in Figure 7.8 of Morgan,
639 with a few changes to reduce pattern search time in favor of a bit
640 more memory usage. */
642 /* One of these is created for each set. It will live in a list local
643 to its basic block for the duration of that block's processing. */
644 struct rename_set_data
646 struct rename_set_data
*next
;
647 /* This is the SET_DEST of the (first) SET that sets the REG. */
649 /* This is what used to be at *REG_LOC. */
651 /* This is the REG that will replace OLD_REG. It's set only
652 when the rename data is moved onto the DONE_RENAMES queue. */
654 /* This is what to restore ssa_rename_to_lookup (old_reg) to. It is
655 usually the previous contents of ssa_rename_to_lookup (old_reg). */
657 /* This is the insn that contains all the SETs of the REG. */
661 /* This struct is used to pass information to callback functions while
662 renaming registers. */
663 struct rename_context
665 struct rename_set_data
*new_renames
;
666 struct rename_set_data
*done_renames
;
670 /* Queue the rename of *REG_LOC. */
672 create_delayed_rename (struct rename_context
*c
, rtx
*reg_loc
)
674 struct rename_set_data
*r
;
675 r
= xmalloc (sizeof(*r
));
677 if (GET_CODE (*reg_loc
) != REG
678 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc
)))
681 r
->reg_loc
= reg_loc
;
682 r
->old_reg
= *reg_loc
;
683 r
->prev_reg
= ssa_rename_to_lookup(r
->old_reg
);
684 r
->set_insn
= c
->current_insn
;
685 r
->next
= c
->new_renames
;
689 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
690 reused. If, during processing, a register has not yet been touched,
691 ssa_rename_to[regno][machno] will be NULL. Now, in the course of pushing
692 and popping values from ssa_rename_to, when we would ordinarily
693 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
694 same as NULL, except that it signals that the original regno has
695 already been reused. */
696 #define RENAME_NO_RTX pc_rtx
698 /* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
699 applying all the renames on NEW_RENAMES. */
702 apply_delayed_renames (struct rename_context
*c
)
704 struct rename_set_data
*r
;
705 struct rename_set_data
*last_r
= NULL
;
707 for (r
= c
->new_renames
; r
!= NULL
; r
= r
->next
)
711 /* Failure here means that someone has a PARALLEL that sets
712 a register twice (bad!). */
713 if (ssa_rename_to_lookup (r
->old_reg
) != r
->prev_reg
)
715 /* Failure here means we have changed REG_LOC before applying
717 /* For the first set we come across, reuse the original regno. */
718 if (r
->prev_reg
== NULL_RTX
&& !HARD_REGISTER_P (r
->old_reg
))
720 r
->new_reg
= r
->old_reg
;
721 /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
722 r
->prev_reg
= RENAME_NO_RTX
;
725 r
->new_reg
= gen_reg_rtx (GET_MODE (r
->old_reg
));
726 new_regno
= REGNO (r
->new_reg
);
727 ssa_rename_to_insert (r
->old_reg
, r
->new_reg
);
729 if (new_regno
>= (int) ssa_definition
->num_elements
)
731 int new_limit
= new_regno
* 5 / 4;
732 VARRAY_GROW (ssa_definition
, new_limit
);
735 VARRAY_RTX (ssa_definition
, new_regno
) = r
->set_insn
;
736 ssa_rename_from_insert (new_regno
, r
->old_reg
);
741 last_r
->next
= c
->done_renames
;
742 c
->done_renames
= c
->new_renames
;
743 c
->new_renames
= NULL
;
747 /* Part one of the first step of rename_block, called through for_each_rtx.
748 Mark pseudos that are set for later update. Transform uses of pseudos. */
751 rename_insn_1 (rtx
*ptr
, void *data
)
754 struct rename_context
*context
= data
;
759 switch (GET_CODE (x
))
763 rtx
*destp
= &SET_DEST (x
);
764 rtx dest
= SET_DEST (x
);
766 /* An assignment to a paradoxical SUBREG does not read from
767 the destination operand, and thus does not need to be
768 wrapped into a SEQUENCE when translating into SSA form.
769 We merely strip off the SUBREG and proceed normally for
771 if (GET_CODE (dest
) == SUBREG
772 && (GET_MODE_SIZE (GET_MODE (dest
))
773 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest
))))
774 && GET_CODE (SUBREG_REG (dest
)) == REG
775 && CONVERT_REGISTER_TO_SSA_P (REGNO (SUBREG_REG (dest
))))
777 destp
= &XEXP (dest
, 0);
778 dest
= XEXP (dest
, 0);
781 /* Some SETs also use the REG specified in their LHS.
782 These can be detected by the presence of
783 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
784 in the LHS. Handle these by changing
785 (set (subreg (reg foo)) ...)
787 (sequence [(set (reg foo_1) (reg foo))
788 (set (subreg (reg foo_1)) ...)])
790 FIXME: Much of the time this is too much. For some constructs
791 we know that the output register is strictly an output
792 (paradoxical SUBREGs and some libcalls for example).
794 For those cases we are better off not making the false
796 if (GET_CODE (dest
) == STRICT_LOW_PART
797 || GET_CODE (dest
) == SUBREG
798 || GET_CODE (dest
) == SIGN_EXTRACT
799 || GET_CODE (dest
) == ZERO_EXTRACT
)
804 while (GET_CODE (reg
) == STRICT_LOW_PART
805 || GET_CODE (reg
) == SUBREG
806 || GET_CODE (reg
) == SIGN_EXTRACT
807 || GET_CODE (reg
) == ZERO_EXTRACT
)
810 if (GET_CODE (reg
) == REG
811 && CONVERT_REGISTER_TO_SSA_P (REGNO (reg
)))
813 /* Generate (set reg reg), and do renaming on it so
814 that it becomes (set reg_1 reg_0), and we will
815 replace reg with reg_1 in the SUBREG. */
817 struct rename_set_data
*saved_new_renames
;
818 saved_new_renames
= context
->new_renames
;
819 context
->new_renames
= NULL
;
820 i
= emit_insn (gen_rtx_SET (VOIDmode
, reg
, reg
));
821 for_each_rtx (&i
, rename_insn_1
, data
);
822 apply_delayed_renames (context
);
823 context
->new_renames
= saved_new_renames
;
826 else if (GET_CODE (dest
) == REG
827 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest
)))
829 /* We found a genuine set of an interesting register. Tag
830 it so that we can create a new name for it after we finish
831 processing this insn. */
833 create_delayed_rename (context
, destp
);
835 /* Since we do not wish to (directly) traverse the
836 SET_DEST, recurse through for_each_rtx for the SET_SRC
838 if (GET_CODE (x
) == SET
)
839 for_each_rtx (&SET_SRC (x
), rename_insn_1
, data
);
843 /* Otherwise, this was not an interesting destination. Continue
844 on, marking uses as normal. */
849 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
))
850 && REGNO (x
) < ssa_max_reg_num
)
852 rtx new_reg
= ssa_rename_to_lookup (x
);
854 if (new_reg
!= RENAME_NO_RTX
&& new_reg
!= NULL_RTX
)
856 if (GET_MODE (x
) != GET_MODE (new_reg
))
862 /* Undefined value used, rename it to a new pseudo register so
863 that it cannot conflict with an existing register. */
864 *ptr
= gen_reg_rtx (GET_MODE (x
));
870 /* There is considerable debate on how CLOBBERs ought to be
871 handled in SSA. For now, we're keeping the CLOBBERs, which
872 means that we don't really have SSA form. There are a couple
873 of proposals for how to fix this problem, but neither is
876 rtx dest
= XCEXP (x
, 0, CLOBBER
);
879 if (CONVERT_REGISTER_TO_SSA_P (REGNO (dest
))
880 && REGNO (dest
) < ssa_max_reg_num
)
882 rtx new_reg
= ssa_rename_to_lookup (dest
);
883 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
884 XCEXP (x
, 0, CLOBBER
) = new_reg
;
886 /* Stop traversing. */
890 /* Continue traversing. */
895 /* Never muck with the phi. We do that elsewhere, special-like. */
899 /* Anything else, continue traversing. */
907 rtx first_insn
= get_insns ();
913 /* Count the insns in the chain. */
915 for (tem
= first_insn
; tem
; tem
= NEXT_INSN (tem
))
918 result
= gen_rtx_SEQUENCE (VOIDmode
, rtvec_alloc (len
));
920 for (i
= 0, tem
= first_insn
; tem
; tem
= NEXT_INSN (tem
), i
++)
921 XVECEXP (result
, 0, i
) = tem
;
927 rename_block (int bb
, dominance_info idom
)
929 basic_block b
= BASIC_BLOCK (bb
);
931 rtx insn
, next
, last
;
932 struct rename_set_data
*set_data
= NULL
;
935 /* Step One: Walk the basic block, adding new names for sets and
945 struct rename_context context
;
946 context
.done_renames
= set_data
;
947 context
.new_renames
= NULL
;
948 context
.current_insn
= insn
;
951 for_each_rtx (&PATTERN (insn
), rename_insn_1
, &context
);
952 for_each_rtx (®_NOTES (insn
), rename_insn_1
, &context
);
954 /* Sometimes, we end up with a sequence of insns that
955 SSA needs to treat as a single insn. Wrap these in a
956 SEQUENCE. (Any notes now get attached to the SEQUENCE,
957 not to the old version inner insn.) */
958 if (get_insns () != NULL_RTX
)
963 emit (PATTERN (insn
));
964 seq
= gen_sequence ();
965 /* We really want a SEQUENCE of SETs, not a SEQUENCE
967 for (i
= 0; i
< XVECLEN (seq
, 0); i
++)
968 XVECEXP (seq
, 0, i
) = PATTERN (XVECEXP (seq
, 0, i
));
969 PATTERN (insn
) = seq
;
973 apply_delayed_renames (&context
);
974 set_data
= context
.done_renames
;
977 next
= NEXT_INSN (insn
);
979 while (insn
!= last
);
981 /* Step Two: Update the phi nodes of this block's successors. */
983 for (e
= b
->succ
; e
; e
= e
->succ_next
)
985 if (e
->dest
== EXIT_BLOCK_PTR
)
988 insn
= first_insn_after_basic_block_note (e
->dest
);
990 while (PHI_NODE_P (insn
))
992 rtx phi
= PATTERN (insn
);
995 /* Find out which of our outgoing registers this node is
996 intended to replace. Note that if this is not the first PHI
997 node to have been created for this register, we have to
998 jump through rename links to figure out which register
999 we're talking about. This can easily be recognized by
1000 noting that the regno is new to this pass. */
1001 reg
= SET_DEST (phi
);
1002 if (REGNO (reg
) >= ssa_max_reg_num
)
1003 reg
= ssa_rename_from_lookup (REGNO (reg
));
1004 if (reg
== NULL_RTX
)
1006 reg
= ssa_rename_to_lookup (reg
);
1008 /* It is possible for the variable to be uninitialized on
1009 edges in. Reduce the arity of the PHI so that we don't
1010 consider those edges. */
1011 if (reg
== NULL
|| reg
== RENAME_NO_RTX
)
1013 if (! remove_phi_alternative (phi
, b
))
1018 /* When we created the PHI nodes, we did not know what mode
1019 the register should be. Now that we've found an original,
1020 we can fill that in. */
1021 if (GET_MODE (SET_DEST (phi
)) == VOIDmode
)
1022 PUT_MODE (SET_DEST (phi
), GET_MODE (reg
));
1023 else if (GET_MODE (SET_DEST (phi
)) != GET_MODE (reg
))
1026 *phi_alternative (phi
, bb
) = reg
;
1029 insn
= NEXT_INSN (insn
);
1033 /* Step Three: Do the same to the children of this block in
1037 if (get_immediate_dominator (idom
, c
)->index
== bb
)
1038 rename_block (c
->index
, idom
);
1040 /* Step Four: Update the sets to refer to their new register,
1041 and restore ssa_rename_to to its previous state. */
1045 struct rename_set_data
*next
;
1046 rtx old_reg
= *set_data
->reg_loc
;
1048 if (*set_data
->reg_loc
!= set_data
->old_reg
)
1050 *set_data
->reg_loc
= set_data
->new_reg
;
1052 ssa_rename_to_insert (old_reg
, set_data
->prev_reg
);
1054 next
= set_data
->next
;
1061 rename_registers (int nregs
, dominance_info idom
)
1063 VARRAY_RTX_INIT (ssa_definition
, nregs
* 3, "ssa_definition");
1064 ssa_rename_from_initialize ();
1066 ssa_rename_to_pseudo
= alloca (nregs
* sizeof(rtx
));
1067 memset (ssa_rename_to_pseudo
, 0, nregs
* sizeof(rtx
));
1068 memset (ssa_rename_to_hard
, 0,
1069 FIRST_PSEUDO_REGISTER
* NUM_MACHINE_MODES
* sizeof (rtx
));
1071 rename_block (0, idom
);
1073 /* ??? Update basic_block_live_at_start, and other flow info
1076 ssa_rename_to_pseudo
= NULL
;
1079 /* The main entry point for moving to SSA. */
1082 convert_to_ssa (void)
1084 /* Element I is the set of blocks that set register I. */
1087 /* Dominator bitmaps. */
1091 /* Element I is the immediate dominator of block I. */
1092 dominance_info idom
;
1098 /* Don't do it twice. */
1102 /* Need global_live_at_{start,end} up to date. Do not remove any
1103 dead code. We'll let the SSA optimizers do that. */
1104 life_analysis (get_insns (), NULL
, 0);
1106 idom
= calculate_dominance_info (CDI_DOMINATORS
);
1110 fputs (";; Immediate Dominators:\n", rtl_dump_file
);
1112 fprintf (rtl_dump_file
, ";\t%3d = %3d\n", bb
->index
,
1113 get_immediate_dominator (idom
, bb
)->index
);
1114 fflush (rtl_dump_file
);
1117 /* Compute dominance frontiers. */
1119 dfs
= sbitmap_vector_alloc (last_basic_block
, last_basic_block
);
1120 compute_dominance_frontiers (dfs
, idom
);
1124 dump_sbitmap_vector (rtl_dump_file
, ";; Dominance Frontiers:",
1125 "; Basic Block", dfs
, last_basic_block
);
1126 fflush (rtl_dump_file
);
1129 /* Compute register evaluations. */
1131 ssa_max_reg_num
= max_reg_num ();
1132 nregs
= ssa_max_reg_num
;
1133 evals
= sbitmap_vector_alloc (nregs
, last_basic_block
);
1134 find_evaluations (evals
, nregs
);
1136 /* Compute the iterated dominance frontier for each register. */
1138 idfs
= sbitmap_vector_alloc (nregs
, last_basic_block
);
1139 compute_iterated_dominance_frontiers (idfs
, dfs
, evals
, nregs
);
1143 dump_sbitmap_vector (rtl_dump_file
, ";; Iterated Dominance Frontiers:",
1144 "; Register", idfs
, nregs
);
1145 fflush (rtl_dump_file
);
1148 /* Insert the phi nodes. */
1150 insert_phi_nodes (idfs
, evals
, nregs
);
1152 /* Rename the registers to satisfy SSA. */
1154 rename_registers (nregs
, idom
);
1156 /* All done! Clean up and go home. */
1158 sbitmap_vector_free (dfs
);
1159 sbitmap_vector_free (evals
);
1160 sbitmap_vector_free (idfs
);
1163 reg_scan (get_insns (), max_reg_num (), 1);
1164 free_dominance_info (idom
);
1167 /* REG is the representative temporary of its partition. Add it to the
1168 set of nodes to be processed, if it hasn't been already. Return the
1169 index of this register in the node set. */
1172 ephi_add_node (rtx reg
, rtx
*nodes
, int *n_nodes
)
1175 for (i
= *n_nodes
- 1; i
>= 0; --i
)
1176 if (REGNO (reg
) == REGNO (nodes
[i
]))
1179 nodes
[i
= (*n_nodes
)++] = reg
;
1183 /* Part one of the topological sort. This is a forward (downward) search
1184 through the graph collecting a stack of nodes to process. Assuming no
1185 cycles, the nodes at top of the stack when we are finished will have
1186 no other dependencies. */
1189 ephi_forward (int t
, sbitmap visited
, sbitmap
*succ
, int *tstack
)
1193 SET_BIT (visited
, t
);
1195 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1197 if (! TEST_BIT (visited
, s
))
1198 tstack
= ephi_forward (s
, visited
, succ
, tstack
);
1205 /* Part two of the topological sort. The is a backward search through
1206 a cycle in the graph, copying the data forward as we go. */
1209 ephi_backward (int t
, sbitmap visited
, sbitmap
*pred
, rtx
*nodes
)
1213 SET_BIT (visited
, t
);
1215 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1217 if (! TEST_BIT (visited
, p
))
1219 ephi_backward (p
, visited
, pred
, nodes
);
1220 emit_move_insn (nodes
[p
], nodes
[t
]);
1225 /* Part two of the topological sort. Create the copy for a register
1226 and any cycle of which it is a member. */
1229 ephi_create (int t
, sbitmap visited
, sbitmap
*pred
, sbitmap
*succ
, rtx
*nodes
)
1231 rtx reg_u
= NULL_RTX
;
1232 int unvisited_predecessors
= 0;
1235 /* Iterate through the predecessor list looking for unvisited nodes.
1236 If there are any, we have a cycle, and must deal with that. At
1237 the same time, look for a visited predecessor. If there is one,
1238 we won't need to create a temporary. */
1240 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1242 if (! TEST_BIT (visited
, p
))
1243 unvisited_predecessors
= 1;
1248 if (unvisited_predecessors
)
1250 /* We found a cycle. Copy out one element of the ring (if necessary),
1251 then traverse the ring copying as we go. */
1255 reg_u
= gen_reg_rtx (GET_MODE (nodes
[t
]));
1256 emit_move_insn (reg_u
, nodes
[t
]);
1259 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1261 if (! TEST_BIT (visited
, p
))
1263 ephi_backward (p
, visited
, pred
, nodes
);
1264 emit_move_insn (nodes
[p
], reg_u
);
1270 /* No cycle. Just copy the value from a successor. */
1273 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1275 SET_BIT (visited
, t
);
1276 emit_move_insn (nodes
[t
], nodes
[s
]);
1282 /* Convert the edge to normal form. */
1285 eliminate_phi (edge e
, partition reg_partition
)
1288 sbitmap
*pred
, *succ
;
1291 int *stack
, *tstack
;
1295 /* Collect an upper bound on the number of registers needing processing. */
1297 insn
= first_insn_after_basic_block_note (e
->dest
);
1300 while (PHI_NODE_P (insn
))
1302 insn
= next_nonnote_insn (insn
);
1309 /* Build the auxiliary graph R(B).
1311 The nodes of the graph are the members of the register partition
1312 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1313 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1315 nodes
= alloca (n_nodes
* sizeof(rtx
));
1316 pred
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1317 succ
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1318 sbitmap_vector_zero (pred
, n_nodes
);
1319 sbitmap_vector_zero (succ
, n_nodes
);
1321 insn
= first_insn_after_basic_block_note (e
->dest
);
1324 for (; PHI_NODE_P (insn
); insn
= next_nonnote_insn (insn
))
1326 rtx
* preg
= phi_alternative (PATTERN (insn
), e
->src
->index
);
1327 rtx tgt
= SET_DEST (PATTERN (insn
));
1330 /* There may be no phi alternative corresponding to this edge.
1331 This indicates that the phi variable is undefined along this
1337 if (GET_CODE (reg
) != REG
|| GET_CODE (tgt
) != REG
)
1340 reg
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (reg
))];
1341 tgt
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (tgt
))];
1342 /* If the two registers are already in the same partition,
1343 nothing will need to be done. */
1348 ireg
= ephi_add_node (reg
, nodes
, &n_nodes
);
1349 itgt
= ephi_add_node (tgt
, nodes
, &n_nodes
);
1351 SET_BIT (pred
[ireg
], itgt
);
1352 SET_BIT (succ
[itgt
], ireg
);
1359 /* Begin a topological sort of the graph. */
1361 visited
= sbitmap_alloc (n_nodes
);
1362 sbitmap_zero (visited
);
1364 tstack
= stack
= alloca (n_nodes
* sizeof (int));
1366 for (i
= 0; i
< n_nodes
; ++i
)
1367 if (! TEST_BIT (visited
, i
))
1368 tstack
= ephi_forward (i
, visited
, succ
, tstack
);
1370 sbitmap_zero (visited
);
1372 /* As we find a solution to the tsort, collect the implementation
1373 insns in a sequence. */
1376 while (tstack
!= stack
)
1379 if (! TEST_BIT (visited
, i
))
1380 ephi_create (i
, visited
, pred
, succ
, nodes
);
1383 insn
= get_insns ();
1385 insert_insn_on_edge (insn
, e
);
1387 fprintf (rtl_dump_file
, "Emitting copy on edge (%d,%d)\n",
1388 e
->src
->index
, e
->dest
->index
);
1390 sbitmap_free (visited
);
1392 sbitmap_vector_free (pred
);
1393 sbitmap_vector_free (succ
);
1396 /* For basic block B, consider all phi insns which provide an
1397 alternative corresponding to an incoming abnormal critical edge.
1398 Place the phi alternative corresponding to that abnormal critical
1399 edge in the same register class as the destination of the set.
1401 From Morgan, p. 178:
1403 For each abnormal critical edge (C, B),
1404 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1405 and C is the ith predecessor of B,
1406 then T0 and Ti must be equivalent.
1408 Return nonzero iff any such cases were found for which the two
1409 regs were not already in the same class. */
1412 make_regs_equivalent_over_bad_edges (int bb
, partition reg_partition
)
1415 basic_block b
= BASIC_BLOCK (bb
);
1418 /* Advance to the first phi node. */
1419 phi
= first_insn_after_basic_block_note (b
);
1421 /* Scan all the phi nodes. */
1424 phi
= next_nonnote_insn (phi
))
1428 rtx set
= PATTERN (phi
);
1429 rtx tgt
= SET_DEST (set
);
1431 /* The set target is expected to be an SSA register. */
1432 if (GET_CODE (tgt
) != REG
1433 || !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt
)))
1435 tgt_regno
= REGNO (tgt
);
1437 /* Scan incoming abnormal critical edges. */
1438 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1439 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
1441 rtx
*alt
= phi_alternative (set
, e
->src
->index
);
1444 /* If there is no alternative corresponding to this edge,
1445 the value is undefined along the edge, so just go on. */
1449 /* The phi alternative is expected to be an SSA register. */
1450 if (GET_CODE (*alt
) != REG
1451 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1453 alt_regno
= REGNO (*alt
);
1455 /* If the set destination and the phi alternative aren't
1456 already in the same class... */
1457 if (partition_find (reg_partition
, tgt_regno
)
1458 != partition_find (reg_partition
, alt_regno
))
1460 /* ... make them such. */
1461 if (conflicting_hard_regs_p (tgt_regno
, alt_regno
))
1462 /* It is illegal to unify a hard register with a
1463 different register. */
1466 partition_union (reg_partition
,
1467 tgt_regno
, alt_regno
);
1476 /* Consider phi insns in basic block BB pairwise. If the set target
1477 of both insns are equivalent pseudos, make the corresponding phi
1478 alternatives in each phi corresponding equivalent.
1480 Return nonzero if any new register classes were unioned. */
1483 make_equivalent_phi_alternatives_equivalent (int bb
, partition reg_partition
)
1486 basic_block b
= BASIC_BLOCK (bb
);
1489 /* Advance to the first phi node. */
1490 phi
= first_insn_after_basic_block_note (b
);
1492 /* Scan all the phi nodes. */
1495 phi
= next_nonnote_insn (phi
))
1497 rtx set
= PATTERN (phi
);
1498 /* The regno of the destination of the set. */
1499 int tgt_regno
= REGNO (SET_DEST (PATTERN (phi
)));
1501 rtx phi2
= next_nonnote_insn (phi
);
1503 /* Scan all phi nodes following this one. */
1506 phi2
= next_nonnote_insn (phi2
))
1508 rtx set2
= PATTERN (phi2
);
1509 /* The regno of the destination of the set. */
1510 int tgt2_regno
= REGNO (SET_DEST (set2
));
1512 /* Are the set destinations equivalent regs? */
1513 if (partition_find (reg_partition
, tgt_regno
) ==
1514 partition_find (reg_partition
, tgt2_regno
))
1517 /* Scan over edges. */
1518 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1520 int pred_block
= e
->src
->index
;
1521 /* Identify the phi alternatives from both phi
1522 nodes corresponding to this edge. */
1523 rtx
*alt
= phi_alternative (set
, pred_block
);
1524 rtx
*alt2
= phi_alternative (set2
, pred_block
);
1526 /* If one of the phi nodes doesn't have a
1527 corresponding alternative, just skip it. */
1528 if (alt
== 0 || alt2
== 0)
1531 /* Both alternatives should be SSA registers. */
1532 if (GET_CODE (*alt
) != REG
1533 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt
)))
1535 if (GET_CODE (*alt2
) != REG
1536 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2
)))
1539 /* If the alternatives aren't already in the same
1541 if (partition_find (reg_partition
, REGNO (*alt
))
1542 != partition_find (reg_partition
, REGNO (*alt2
)))
1544 /* ... make them so. */
1545 if (conflicting_hard_regs_p (REGNO (*alt
), REGNO (*alt2
)))
1546 /* It is illegal to unify a hard register with
1547 a different register. */
1550 partition_union (reg_partition
,
1551 REGNO (*alt
), REGNO (*alt2
));
1562 /* Compute a conservative partition of outstanding pseudo registers.
1563 See Morgan 7.3.1. */
1566 compute_conservative_reg_partition (void)
1571 /* We don't actually work with hard registers, but it's easier to
1572 carry them around anyway rather than constantly doing register
1573 number arithmetic. */
1575 partition_new (ssa_definition
->num_elements
);
1577 /* The first priority is to make sure registers that might have to
1578 be copied on abnormal critical edges are placed in the same
1579 partition. This saves us from having to split abnormal critical
1581 FOR_EACH_BB_REVERSE (bb
)
1582 changed
+= make_regs_equivalent_over_bad_edges (bb
->index
, p
);
1584 /* Now we have to insure that corresponding arguments of phi nodes
1585 assigning to corresponding regs are equivalent. Iterate until
1590 FOR_EACH_BB_REVERSE (bb
)
1591 changed
+= make_equivalent_phi_alternatives_equivalent (bb
->index
, p
);
1597 /* The following functions compute a register partition that attempts
1598 to eliminate as many reg copies and phi node copies as possible by
1599 coalescing registers. This is the strategy:
1601 1. As in the conservative case, the top priority is to coalesce
1602 registers that otherwise would cause copies to be placed on
1603 abnormal critical edges (which isn't possible).
1605 2. Figure out which regs are involved (in the LHS or RHS) of
1606 copies and phi nodes. Compute conflicts among these regs.
1608 3. Walk around the instruction stream, placing two regs in the
1609 same class of the partition if one appears on the LHS and the
1610 other on the RHS of a copy or phi node and the two regs don't
1611 conflict. The conflict information of course needs to be
1614 4. If anything has changed, there may be new opportunities to
1615 coalesce regs, so go back to 2.
1618 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1619 same class of partition P, if they aren't already. Update
1620 CONFLICTS appropriately.
1622 Returns one if REG1 and REG2 were placed in the same class but were
1623 not previously; zero otherwise.
1625 See Morgan figure 11.15. */
1628 coalesce_if_unconflicting (partition p
, conflict_graph conflicts
,
1633 /* Work only on SSA registers. */
1634 if (!CONVERT_REGISTER_TO_SSA_P (reg1
) || !CONVERT_REGISTER_TO_SSA_P (reg2
))
1637 /* Find the canonical regs for the classes containing REG1 and
1639 reg1
= partition_find (p
, reg1
);
1640 reg2
= partition_find (p
, reg2
);
1642 /* If they're already in the same class, there's nothing to do. */
1646 /* If the regs conflict, our hands are tied. */
1647 if (conflicting_hard_regs_p (reg1
, reg2
) ||
1648 conflict_graph_conflict_p (conflicts
, reg1
, reg2
))
1651 /* We're good to go. Put the regs in the same partition. */
1652 partition_union (p
, reg1
, reg2
);
1654 /* Find the new canonical reg for the merged class. */
1655 reg
= partition_find (p
, reg1
);
1657 /* Merge conflicts from the two previous classes. */
1658 conflict_graph_merge_regs (conflicts
, reg
, reg1
);
1659 conflict_graph_merge_regs (conflicts
, reg
, reg2
);
1664 /* For each register copy insn in basic block BB, place the LHS and
1665 RHS regs in the same class in partition P if they do not conflict
1666 according to CONFLICTS.
1668 Returns the number of changes that were made to P.
1670 See Morgan figure 11.14. */
1673 coalesce_regs_in_copies (basic_block bb
, partition p
, conflict_graph conflicts
)
1679 /* Scan the instruction stream of the block. */
1680 for (insn
= bb
->head
; insn
!= end
; insn
= NEXT_INSN (insn
))
1686 /* If this isn't a set insn, go to the next insn. */
1687 if (GET_CODE (insn
) != INSN
)
1689 pattern
= PATTERN (insn
);
1690 if (GET_CODE (pattern
) != SET
)
1693 src
= SET_SRC (pattern
);
1694 dest
= SET_DEST (pattern
);
1696 /* We're only looking for copies. */
1697 if (GET_CODE (src
) != REG
|| GET_CODE (dest
) != REG
)
1700 /* Coalesce only if the reg modes are the same. As long as
1701 each reg's rtx is unique, it can have only one mode, so two
1702 pseudos of different modes can't be coalesced into one.
1704 FIXME: We can probably get around this by inserting SUBREGs
1705 where appropriate, but for now we don't bother. */
1706 if (GET_MODE (src
) != GET_MODE (dest
))
1709 /* Found a copy; see if we can use the same reg for both the
1710 source and destination (and thus eliminate the copy,
1712 changed
+= coalesce_if_unconflicting (p
, conflicts
,
1713 REGNO (src
), REGNO (dest
));
1719 struct phi_coalesce_context
1722 conflict_graph conflicts
;
1726 /* Callback function for for_each_successor_phi. If the set
1727 destination and the phi alternative regs do not conflict, place
1728 them in the same partition class. DATA is a pointer to a
1729 phi_coalesce_context struct. */
1732 coalesce_reg_in_phi (rtx insn ATTRIBUTE_UNUSED
, int dest_regno
,
1733 int src_regno
, void *data
)
1735 struct phi_coalesce_context
*context
=
1736 (struct phi_coalesce_context
*) data
;
1738 /* Attempt to use the same reg, if they don't conflict. */
1740 += coalesce_if_unconflicting (context
->p
, context
->conflicts
,
1741 dest_regno
, src_regno
);
1745 /* For each alternative in a phi function corresponding to basic block
1746 BB (in phi nodes in successor block to BB), place the reg in the
1747 phi alternative and the reg to which the phi value is set into the
1748 same class in partition P, if allowed by CONFLICTS.
1750 Return the number of changes that were made to P.
1752 See Morgan figure 11.14. */
1755 coalesce_regs_in_successor_phi_nodes (basic_block bb
, partition p
,
1756 conflict_graph conflicts
)
1758 struct phi_coalesce_context context
;
1760 context
.conflicts
= conflicts
;
1761 context
.changed
= 0;
1763 for_each_successor_phi (bb
, &coalesce_reg_in_phi
, &context
);
1765 return context
.changed
;
1768 /* Compute and return a partition of pseudos. Where possible,
1769 non-conflicting pseudos are placed in the same class.
1771 The caller is responsible for deallocating the returned partition. */
1774 compute_coalesced_reg_partition (void)
1778 regset_head phi_set_head
;
1779 regset phi_set
= &phi_set_head
;
1782 partition_new (ssa_definition
->num_elements
);
1784 /* The first priority is to make sure registers that might have to
1785 be copied on abnormal critical edges are placed in the same
1786 partition. This saves us from having to split abnormal critical
1787 edges (which can't be done). */
1788 FOR_EACH_BB_REVERSE (bb
)
1789 make_regs_equivalent_over_bad_edges (bb
->index
, p
);
1791 INIT_REG_SET (phi_set
);
1795 conflict_graph conflicts
;
1799 /* Build the set of registers involved in phi nodes, either as
1800 arguments to the phi function or as the target of a set. */
1801 CLEAR_REG_SET (phi_set
);
1802 mark_phi_and_copy_regs (phi_set
);
1804 /* Compute conflicts. */
1805 conflicts
= conflict_graph_compute (phi_set
, p
);
1807 /* FIXME: Better would be to process most frequently executed
1808 blocks first, so that most frequently executed copies would
1809 be more likely to be removed by register coalescing. But any
1810 order will generate correct, if non-optimal, results. */
1811 FOR_EACH_BB_REVERSE (bb
)
1813 changed
+= coalesce_regs_in_copies (bb
, p
, conflicts
);
1815 coalesce_regs_in_successor_phi_nodes (bb
, p
, conflicts
);
1818 conflict_graph_delete (conflicts
);
1820 while (changed
> 0);
1822 FREE_REG_SET (phi_set
);
1827 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1828 components (a REG or a CONST_INT). DATA is a reg set in which to
1829 set all regs. Called from for_each_rtx. */
1832 mark_reg_in_phi (rtx
*ptr
, void *data
)
1835 regset set
= (regset
) data
;
1837 switch (GET_CODE (expr
))
1840 SET_REGNO_REG_SET (set
, REGNO (expr
));
1850 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1851 set from a phi expression, or used as an argument in one. Also
1852 mark regs that are the source or target of a reg copy. Uses
1856 mark_phi_and_copy_regs (regset phi_set
)
1860 /* Scan the definitions of all regs. */
1861 for (reg
= 0; reg
< VARRAY_SIZE (ssa_definition
); ++reg
)
1862 if (CONVERT_REGISTER_TO_SSA_P (reg
))
1864 rtx insn
= VARRAY_RTX (ssa_definition
, reg
);
1869 || (GET_CODE (insn
) == NOTE
1870 && NOTE_LINE_NUMBER (insn
) == NOTE_INSN_DELETED
))
1872 pattern
= PATTERN (insn
);
1873 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1875 if (GET_CODE (pattern
) != SET
)
1877 src
= SET_SRC (pattern
);
1879 if (GET_CODE (src
) == REG
)
1881 /* It's a reg copy. */
1882 SET_REGNO_REG_SET (phi_set
, reg
);
1883 SET_REGNO_REG_SET (phi_set
, REGNO (src
));
1885 else if (GET_CODE (src
) == PHI
)
1887 /* It's a phi node. Mark the reg being set. */
1888 SET_REGNO_REG_SET (phi_set
, reg
);
1889 /* Mark the regs used in the phi function. */
1890 for_each_rtx (&src
, mark_reg_in_phi
, phi_set
);
1892 /* ... else nothing to do. */
1896 /* Rename regs in insn PTR that are equivalent. DATA is the register
1897 partition which specifies equivalences. */
1900 rename_equivalent_regs_in_insn (rtx
*ptr
, void* data
)
1903 partition reg_partition
= (partition
) data
;
1908 switch (GET_CODE (x
))
1911 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x
)))
1913 unsigned int regno
= REGNO (x
);
1914 unsigned int new_regno
= partition_find (reg_partition
, regno
);
1915 rtx canonical_element_rtx
= ssa_rename_from_lookup (new_regno
);
1917 if (canonical_element_rtx
!= NULL_RTX
&&
1918 HARD_REGISTER_P (canonical_element_rtx
))
1920 if (REGNO (canonical_element_rtx
) != regno
)
1921 *ptr
= canonical_element_rtx
;
1923 else if (regno
!= new_regno
)
1925 rtx new_reg
= regno_reg_rtx
[new_regno
];
1926 if (GET_MODE (x
) != GET_MODE (new_reg
))
1934 /* No need to rename the phi nodes. We'll check equivalence
1935 when inserting copies. */
1939 /* Anything else, continue traversing. */
1944 /* Record the register's canonical element stored in SRFP in the
1945 canonical_elements sbitmap packaged in DATA. This function is used
1946 as a callback function for traversing ssa_rename_from. */
1949 record_canonical_element_1 (void **srfp
, void *data
)
1951 unsigned int reg
= ((ssa_rename_from_pair
*) *srfp
)->reg
;
1952 sbitmap canonical_elements
=
1953 ((struct ssa_rename_from_hash_table_data
*) data
)->canonical_elements
;
1954 partition reg_partition
=
1955 ((struct ssa_rename_from_hash_table_data
*) data
)->reg_partition
;
1957 SET_BIT (canonical_elements
, partition_find (reg_partition
, reg
));
1961 /* For each class in the REG_PARTITION corresponding to a particular
1962 hard register and machine mode, check that there are no other
1963 classes with the same hard register and machine mode. Returns
1964 nonzero if this is the case, i.e., the partition is acceptable. */
1967 check_hard_regs_in_partition (partition reg_partition
)
1969 /* CANONICAL_ELEMENTS has a nonzero bit if a class with the given register
1970 number and machine mode has already been seen. This is a
1971 problem with the partition. */
1972 sbitmap canonical_elements
;
1974 int already_seen
[FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
1978 /* Collect a list of canonical elements. */
1979 canonical_elements
= sbitmap_alloc (max_reg_num ());
1980 sbitmap_zero (canonical_elements
);
1981 ssa_rename_from_traverse (&record_canonical_element_1
,
1982 canonical_elements
, reg_partition
);
1984 /* We have not seen any hard register uses. */
1985 for (reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; ++reg
)
1986 for (mach_mode
= 0; mach_mode
< NUM_MACHINE_MODES
; ++mach_mode
)
1987 already_seen
[reg
][mach_mode
] = 0;
1989 /* Check for classes with the same hard register and machine mode. */
1990 EXECUTE_IF_SET_IN_SBITMAP (canonical_elements
, 0, element_index
,
1992 rtx hard_reg_rtx
= ssa_rename_from_lookup (element_index
);
1993 if (hard_reg_rtx
!= NULL_RTX
&&
1994 HARD_REGISTER_P (hard_reg_rtx
) &&
1995 already_seen
[REGNO (hard_reg_rtx
)][GET_MODE (hard_reg_rtx
)] != 0)
1996 /* Two distinct partition classes should be mapped to the same
2001 sbitmap_free (canonical_elements
);
2006 /* Rename regs that are equivalent in REG_PARTITION. Also collapse
2007 any SEQUENCE insns. */
2010 rename_equivalent_regs (partition reg_partition
)
2014 FOR_EACH_BB_REVERSE (b
)
2025 for_each_rtx (&PATTERN (insn
),
2026 rename_equivalent_regs_in_insn
,
2028 for_each_rtx (®_NOTES (insn
),
2029 rename_equivalent_regs_in_insn
,
2032 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
2034 rtx s
= PATTERN (insn
);
2035 int slen
= XVECLEN (s
, 0);
2041 PATTERN (insn
) = XVECEXP (s
, 0, slen
-1);
2042 for (i
= 0; i
< slen
- 1; i
++)
2043 emit_insn_before (XVECEXP (s
, 0, i
), insn
);
2047 next
= NEXT_INSN (insn
);
2049 while (insn
!= last
);
2053 /* The main entry point for moving from SSA. */
2056 convert_from_ssa (void)
2059 partition reg_partition
;
2060 rtx insns
= get_insns ();
2062 /* Need global_live_at_{start,end} up to date. There should not be
2063 any significant dead code at this point, except perhaps dead
2064 stores. So do not take the time to perform dead code elimination.
2066 Register coalescing needs death notes, so generate them. */
2067 life_analysis (insns
, NULL
, PROP_DEATH_NOTES
);
2069 /* Figure out which regs in copies and phi nodes don't conflict and
2070 therefore can be coalesced. */
2071 if (conservative_reg_partition
)
2072 reg_partition
= compute_conservative_reg_partition ();
2074 reg_partition
= compute_coalesced_reg_partition ();
2076 if (!check_hard_regs_in_partition (reg_partition
))
2077 /* Two separate partitions should correspond to the same hard
2078 register but do not. */
2081 rename_equivalent_regs (reg_partition
);
2083 /* Eliminate the PHI nodes. */
2084 FOR_EACH_BB_REVERSE (b
)
2088 for (e
= b
->pred
; e
; e
= e
->pred_next
)
2089 if (e
->src
!= ENTRY_BLOCK_PTR
)
2090 eliminate_phi (e
, reg_partition
);
2093 partition_delete (reg_partition
);
2095 /* Actually delete the PHI nodes. */
2096 FOR_EACH_BB_REVERSE (bb
)
2098 rtx insn
= bb
->head
;
2102 /* If this is a PHI node delete it. */
2103 if (PHI_NODE_P (insn
))
2105 if (insn
== bb
->end
)
2106 bb
->end
= PREV_INSN (insn
);
2107 insn
= delete_insn (insn
);
2109 /* Since all the phi nodes come at the beginning of the
2110 block, if we find an ordinary insn, we can stop looking
2111 for more phi nodes. */
2112 else if (INSN_P (insn
))
2114 /* If we've reached the end of the block, stop. */
2115 else if (insn
== bb
->end
)
2118 insn
= NEXT_INSN (insn
);
2122 /* Commit all the copy nodes needed to convert out of SSA form. */
2123 commit_edge_insertions ();
2127 count_or_remove_death_notes (NULL
, 1);
2129 /* Deallocate the data structures. */
2131 ssa_rename_from_free ();
2134 /* Scan phi nodes in successors to BB. For each such phi node that
2135 has a phi alternative value corresponding to BB, invoke FN. FN
2136 is passed the entire phi node insn, the regno of the set
2137 destination, the regno of the phi argument corresponding to BB,
2140 If FN ever returns nonzero, stops immediately and returns this
2141 value. Otherwise, returns zero. */
2144 for_each_successor_phi (basic_block bb
, successor_phi_fn fn
, void *data
)
2148 if (bb
== EXIT_BLOCK_PTR
)
2151 /* Scan outgoing edges. */
2152 for (e
= bb
->succ
; e
!= NULL
; e
= e
->succ_next
)
2156 basic_block successor
= e
->dest
;
2157 if (successor
== ENTRY_BLOCK_PTR
2158 || successor
== EXIT_BLOCK_PTR
)
2161 /* Advance to the first non-label insn of the successor block. */
2162 insn
= first_insn_after_basic_block_note (successor
);
2167 /* Scan phi nodes in the successor. */
2168 for ( ; PHI_NODE_P (insn
); insn
= NEXT_INSN (insn
))
2171 rtx phi_set
= PATTERN (insn
);
2172 rtx
*alternative
= phi_alternative (phi_set
, bb
->index
);
2175 /* This phi function may not have an alternative
2176 corresponding to the incoming edge, indicating the
2177 assigned variable is not defined along the edge. */
2178 if (alternative
== NULL
)
2180 phi_src
= *alternative
;
2182 /* Invoke the callback. */
2183 result
= (*fn
) (insn
, REGNO (SET_DEST (phi_set
)),
2184 REGNO (phi_src
), data
);
2186 /* Terminate if requested. */
2195 /* Assuming the ssa_rename_from mapping has been established, yields
2196 nonzero if 1) only one SSA register of REG1 and REG2 comes from a
2197 hard register or 2) both SSA registers REG1 and REG2 come from
2198 different hard registers. */
2201 conflicting_hard_regs_p (int reg1
, int reg2
)
2203 int orig_reg1
= original_register (reg1
);
2204 int orig_reg2
= original_register (reg2
);
2205 if (HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
)
2206 && orig_reg1
!= orig_reg2
)
2208 if (HARD_REGISTER_NUM_P (orig_reg1
) && !HARD_REGISTER_NUM_P (orig_reg2
))
2210 if (!HARD_REGISTER_NUM_P (orig_reg1
) && HARD_REGISTER_NUM_P (orig_reg2
))