1 /* Static Single Assignment conversion routines for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GNU CC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 Building an Optimizing Compiler
25 Butterworth-Heinemann, 1998
27 Static Single Assignment Construction
28 Preston Briggs, Tim Harvey, Taylor Simpson
29 Technical Report, Rice University, 1995
30 ftp://ftp.cs.rice.edu/public/preston/optimizer/SSA.ps.gz
38 #include "hard-reg-set.h"
42 #include "insn-config.h"
44 #include "basic-block.h"
46 #include "partition.h"
51 Handle subregs better, maybe. For now, if a reg that's set in a
52 subreg expression is duplicated going into SSA form, an extra copy
53 is inserted first that copies the entire reg into the duplicate, so
54 that the other bits are preserved. This isn't strictly SSA, since
55 at least part of the reg is assigned in more than one place (though
58 ??? What to do about strict_low_part. Probably I'll have to split
59 them out of their current instructions first thing.
61 Actually the best solution may be to have a kind of "mid-level rtl"
62 in which the RTL encodes exactly what we want, without exposing a
63 lot of niggling processor details. At some later point we lower
64 the representation, calling back into optabs to finish any necessary
68 /* If conservative_reg_partition is non-zero, use a conservative
69 register partitioning algorithm (which leaves more regs after
70 emerging from SSA) instead of the coalescing one. This is being
71 left in for a limited time only, as a debugging tool until the
72 coalescing algorithm is validated. */
73 static int conservative_reg_partition
;
75 /* This flag is set when the CFG is in SSA form. */
78 /* Element I is the single instruction that sets register I+PSEUDO. */
79 varray_type ssa_definition
;
81 /* Element I is an INSN_LIST of instructions that use register I+PSEUDO. */
84 /* Element I-PSEUDO is the normal register that originated the ssa
85 register in question. */
86 varray_type ssa_rename_from
;
88 /* The running target ssa register for a given normal register. */
89 static rtx
*ssa_rename_to
;
91 /* The number of registers that were live on entry to the SSA routines. */
92 static unsigned int ssa_max_reg_num
;
94 /* Local function prototypes. */
96 static inline rtx
* phi_alternative
99 static int remove_phi_alternative
101 static void simplify_to_immediate_dominators
102 PARAMS ((int *idom
, sbitmap
*dominators
));
103 static void compute_dominance_frontiers_1
104 PARAMS ((sbitmap
*frontiers
, int *idom
, int bb
, sbitmap done
));
105 static void compute_dominance_frontiers
106 PARAMS ((sbitmap
*frontiers
, int *idom
));
107 static void find_evaluations_1
108 PARAMS ((rtx dest
, rtx set
, void *data
));
109 static void find_evaluations
110 PARAMS ((sbitmap
*evals
, int nregs
));
111 static void compute_iterated_dominance_frontiers
112 PARAMS ((sbitmap
*idfs
, sbitmap
*frontiers
, sbitmap
*evals
, int nregs
));
113 static void insert_phi_node
114 PARAMS ((int regno
, int b
));
115 static void insert_phi_nodes
116 PARAMS ((sbitmap
*idfs
, sbitmap
*evals
, int nregs
));
117 static int rename_insn_1
118 PARAMS ((rtx
*ptr
, void *data
));
119 static void rename_block
120 PARAMS ((int b
, int *idom
));
121 static void rename_registers
122 PARAMS ((int nregs
, int *idom
));
124 static inline int ephi_add_node
125 PARAMS ((rtx reg
, rtx
*nodes
, int *n_nodes
));
126 static int * ephi_forward
127 PARAMS ((int t
, sbitmap visited
, sbitmap
*succ
, int *tstack
));
128 static void ephi_backward
129 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, rtx
*nodes
));
130 static void ephi_create
131 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, sbitmap
*succ
, rtx
*nodes
));
132 static void eliminate_phi
133 PARAMS ((edge e
, partition reg_partition
));
134 static int make_regs_equivalent_over_bad_edges
135 PARAMS ((int bb
, partition reg_partition
));
137 /* These are used only in the conservative register partitioning
139 static int make_equivalent_phi_alternatives_equivalent
140 PARAMS ((int bb
, partition reg_partition
));
141 static partition compute_conservative_reg_partition
143 static int rename_equivalent_regs_in_insn
144 PARAMS ((rtx
*ptr
, void *data
));
146 /* These are used in the register coalescing algorithm. */
147 static int coalesce_if_unconflicting
148 PARAMS ((partition p
, conflict_graph conflicts
, int reg1
, int reg2
));
149 static int coalesce_regs_in_copies
150 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
151 static int coalesce_reg_in_phi
152 PARAMS ((rtx
, int dest_regno
, int src_regno
, void *data
));
153 static int coalesce_regs_in_successor_phi_nodes
154 PARAMS ((basic_block bb
, partition p
, conflict_graph conflicts
));
155 static partition compute_coalesced_reg_partition
157 static int mark_reg_in_phi
158 PARAMS ((rtx
*ptr
, void *data
));
159 static void mark_phi_and_copy_regs
160 PARAMS ((regset phi_set
));
162 static int rename_equivalent_regs_in_insn
163 PARAMS ((rtx
*ptr
, void *data
));
164 static void rename_equivalent_regs
165 PARAMS ((partition reg_partition
));
168 /* Given the SET of a PHI node, return the address of the alternative
169 for predecessor block C. */
172 phi_alternative (set
, c
)
176 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
179 for (v
= GET_NUM_ELEM (phi_vec
) - 2; v
>= 0; v
-= 2)
180 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
181 return &RTVEC_ELT (phi_vec
, v
);
186 /* Given the SET of a phi node, remove the alternative for predecessor
187 block C. Return non-zero on success, or zero if no alternative is
191 remove_phi_alternative (set
, c
)
195 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
196 int num_elem
= GET_NUM_ELEM (phi_vec
);
199 for (v
= num_elem
- 2; v
>= 0; v
-= 2)
200 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
202 if (v
< num_elem
- 2)
204 RTVEC_ELT (phi_vec
, v
) = RTVEC_ELT (phi_vec
, num_elem
- 2);
205 RTVEC_ELT (phi_vec
, v
+ 1) = RTVEC_ELT (phi_vec
, num_elem
- 1);
207 PUT_NUM_ELEM (phi_vec
, num_elem
- 2);
214 /* Computing the Immediate Dominators:
216 Throughout, we don't actually want the full dominators set as
217 calculated by flow, but rather the immediate dominators.
221 simplify_to_immediate_dominators (idom
, dominators
)
228 tmp
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
230 /* Begin with tmp(n) = dom(n) - { n }. */
231 for (b
= n_basic_blocks
; --b
>= 0; )
233 sbitmap_copy (tmp
[b
], dominators
[b
]);
234 RESET_BIT (tmp
[b
], b
);
237 /* Subtract out all of our dominator's dominators. */
238 for (b
= n_basic_blocks
; --b
>= 0; )
240 sbitmap tmp_b
= tmp
[b
];
243 for (s
= n_basic_blocks
; --s
>= 0; )
244 if (TEST_BIT (tmp_b
, s
))
245 sbitmap_difference (tmp_b
, tmp_b
, tmp
[s
]);
248 /* Find the one bit set in the bitmap and put it in the output array. */
249 for (b
= n_basic_blocks
; --b
>= 0; )
252 EXECUTE_IF_SET_IN_SBITMAP (tmp
[b
], 0, t
, { idom
[b
] = t
; });
255 sbitmap_vector_free (tmp
);
259 /* For all registers, find all blocks in which they are set.
261 This is the transform of what would be local kill information that
262 we ought to be getting from flow. */
264 static sbitmap
*fe_evals
;
265 static int fe_current_bb
;
268 find_evaluations_1 (dest
, set
, data
)
270 rtx set ATTRIBUTE_UNUSED
;
271 void *data ATTRIBUTE_UNUSED
;
273 if (GET_CODE (dest
) == REG
274 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
275 SET_BIT (fe_evals
[REGNO (dest
) - FIRST_PSEUDO_REGISTER
], fe_current_bb
);
279 find_evaluations (evals
, nregs
)
285 sbitmap_vector_zero (evals
, nregs
);
288 for (bb
= n_basic_blocks
; --bb
>= 0; )
294 last
= BLOCK_END (bb
);
297 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i')
298 note_stores (PATTERN (p
), find_evaluations_1
, NULL
);
308 /* Computing the Dominance Frontier:
310 As decribed in Morgan, section 3.5, this may be done simply by
311 walking the dominator tree bottom-up, computing the frontier for
312 the children before the parent. When considering a block B,
315 (1) A flow graph edge leaving B that does not lead to a child
316 of B in the dominator tree must be a block that is either equal
317 to B or not dominated by B. Such blocks belong in the frontier
320 (2) Consider a block X in the frontier of one of the children C
321 of B. If X is not equal to B and is not dominated by B, it
322 is in the frontier of B.
326 compute_dominance_frontiers_1 (frontiers
, idom
, bb
, done
)
332 basic_block b
= BASIC_BLOCK (bb
);
337 sbitmap_zero (frontiers
[bb
]);
339 /* Do the frontier of the children first. Not all children in the
340 dominator tree (blocks dominated by this one) are children in the
341 CFG, so check all blocks. */
342 for (c
= 0; c
< n_basic_blocks
; ++c
)
343 if (idom
[c
] == bb
&& ! TEST_BIT (done
, c
))
344 compute_dominance_frontiers_1 (frontiers
, idom
, c
, done
);
346 /* Find blocks conforming to rule (1) above. */
347 for (e
= b
->succ
; e
; e
= e
->succ_next
)
349 if (e
->dest
== EXIT_BLOCK_PTR
)
351 if (idom
[e
->dest
->index
] != bb
)
352 SET_BIT (frontiers
[bb
], e
->dest
->index
);
355 /* Find blocks conforming to rule (2). */
356 for (c
= 0; c
< n_basic_blocks
; ++c
)
360 EXECUTE_IF_SET_IN_SBITMAP (frontiers
[c
], 0, x
,
363 SET_BIT (frontiers
[bb
], x
);
369 compute_dominance_frontiers (frontiers
, idom
)
373 sbitmap done
= sbitmap_alloc (n_basic_blocks
);
376 compute_dominance_frontiers_1 (frontiers
, idom
, 0, done
);
382 /* Computing the Iterated Dominance Frontier:
384 This is the set of merge points for a given register.
386 This is not particularly intuitive. See section 7.1 of Morgan, in
387 particular figures 7.3 and 7.4 and the immediately surrounding text.
391 compute_iterated_dominance_frontiers (idfs
, frontiers
, evals
, nregs
)
400 worklist
= sbitmap_alloc (n_basic_blocks
);
402 for (reg
= 0; reg
< nregs
; ++reg
)
404 sbitmap idf
= idfs
[reg
];
407 /* Start the iterative process by considering those blocks that
408 evaluate REG. We'll add their dominance frontiers to the
409 IDF, and then consider the blocks we just added. */
410 sbitmap_copy (worklist
, evals
[reg
]);
412 /* Morgan's algorithm is incorrect here. Blocks that evaluate
413 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
416 /* Iterate until the worklist is empty. */
421 EXECUTE_IF_SET_IN_SBITMAP (worklist
, 0, b
,
423 RESET_BIT (worklist
, b
);
424 /* For each block on the worklist, add to the IDF all
425 blocks on its dominance frontier that aren't already
426 on the IDF. Every block that's added is also added
428 sbitmap_union_of_diff (worklist
, worklist
, frontiers
[b
], idf
);
429 sbitmap_a_or_b (idf
, idf
, frontiers
[b
]);
436 sbitmap_free (worklist
);
440 fprintf(rtl_dump_file
,
441 "Iterated dominance frontier: %d passes on %d regs.\n",
447 /* Insert the phi nodes. */
450 insert_phi_node (regno
, bb
)
453 basic_block b
= BASIC_BLOCK (bb
);
459 /* Find out how many predecessors there are. */
460 for (e
= b
->pred
, npred
= 0; e
; e
= e
->pred_next
)
461 if (e
->src
!= ENTRY_BLOCK_PTR
)
464 /* If this block has no "interesting" preds, then there is nothing to
465 do. Consider a block that only has the entry block as a pred. */
469 /* This is the register to which the phi function will be assinged. */
470 reg
= regno_reg_rtx
[regno
+ FIRST_PSEUDO_REGISTER
];
472 /* Construct the arguments to the PHI node. The use of pc_rtx is just
473 a placeholder; we'll insert the proper value in rename_registers. */
474 vec
= rtvec_alloc (npred
* 2);
475 for (e
= b
->pred
, i
= 0; e
; e
= e
->pred_next
, i
+= 2)
476 if (e
->src
!= ENTRY_BLOCK_PTR
)
478 RTVEC_ELT (vec
, i
+ 0) = pc_rtx
;
479 RTVEC_ELT (vec
, i
+ 1) = GEN_INT (e
->src
->index
);
482 phi
= gen_rtx_PHI (VOIDmode
, vec
);
483 phi
= gen_rtx_SET (VOIDmode
, reg
, phi
);
485 if (GET_CODE (b
->head
) == CODE_LABEL
)
486 emit_insn_after (phi
, b
->head
);
488 b
->head
= emit_insn_before (phi
, b
->head
);
493 insert_phi_nodes (idfs
, evals
, nregs
)
495 sbitmap
*evals ATTRIBUTE_UNUSED
;
500 for (reg
= 0; reg
< nregs
; ++reg
)
503 EXECUTE_IF_SET_IN_SBITMAP (idfs
[reg
], 0, b
,
505 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
,
506 reg
+ FIRST_PSEUDO_REGISTER
))
507 insert_phi_node (reg
, b
);
512 /* Rename the registers to conform to SSA.
514 This is essentially the algorithm presented in Figure 7.8 of Morgan,
515 with a few changes to reduce pattern search time in favour of a bit
516 more memory usage. */
519 /* One of these is created for each set. It will live in a list local
520 to its basic block for the duration of that block's processing. */
521 struct rename_set_data
523 struct rename_set_data
*next
;
531 /* This struct is used to pass information to callback functions while
532 renaming registers. */
533 struct rename_context
535 struct rename_set_data
*set_data
;
539 static void new_registers_for_updates
540 PARAMS ((struct rename_set_data
*set_data
,
541 struct rename_set_data
*old_set_data
, rtx insn
));
543 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
544 reused. If, during processing, a register has not yet been touched,
545 ssa_rename_to[regno] will be NULL. Now, in the course of pushing
546 and popping values from ssa_rename_to, when we would ordinarily
547 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
548 same as NULL, except that it signals that the original regno has
549 already been reused. */
550 #define RENAME_NO_RTX pc_rtx
552 /* Part one of the first step of rename_block, called through for_each_rtx.
553 Mark pseudos that are set for later update. Transform uses of pseudos. */
556 rename_insn_1 (ptr
, data
)
561 struct rename_context
*context
= data
;
562 struct rename_set_data
**set_datap
= &(context
->set_data
);
567 switch (GET_CODE (x
))
571 rtx
*destp
= &SET_DEST (x
);
572 rtx dest
= SET_DEST (x
);
574 /* Subregs at word 0 are interesting. Subregs at word != 0 are
575 presumed to be part of a contiguous multi-word set sequence. */
576 while (GET_CODE (dest
) == SUBREG
577 && SUBREG_WORD (dest
) == 0)
579 destp
= &SUBREG_REG (dest
);
580 dest
= SUBREG_REG (dest
);
583 if (GET_CODE (dest
) == REG
584 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
586 /* We found a genuine set of an interesting register. Tag
587 it so that we can create a new name for it after we finish
588 processing this insn. */
590 struct rename_set_data
*r
;
591 r
= (struct rename_set_data
*) xmalloc (sizeof(*r
));
594 r
->set_dest
= SET_DEST (x
);
595 r
->set_insn
= context
->current_insn
;
596 r
->next
= *set_datap
;
599 /* Since we do not wish to (directly) traverse the
600 SET_DEST, recurse through for_each_rtx for the SET_SRC
602 for_each_rtx (&SET_SRC (x
), rename_insn_1
, data
);
606 /* Otherwise, this was not an interesting destination. Continue
607 on, marking uses as normal. */
612 if (REGNO (x
) >= FIRST_PSEUDO_REGISTER
613 && REGNO (x
) < ssa_max_reg_num
)
615 rtx new_reg
= ssa_rename_to
[REGNO(x
) - FIRST_PSEUDO_REGISTER
];
617 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
619 if (GET_MODE (x
) != GET_MODE (new_reg
))
623 /* Else this is a use before a set. Warn? */
628 /* Never muck with the phi. We do that elsewhere, special-like. */
632 /* Anything else, continue traversing. */
637 /* Second part of the first step of rename_block. The portion of the list
638 beginning at SET_DATA through OLD_SET_DATA contain the sets present in
639 INSN. Update data structures accordingly. */
642 new_registers_for_updates (set_data
, old_set_data
, insn
)
643 struct rename_set_data
*set_data
, *old_set_data
;
646 while (set_data
!= old_set_data
)
648 int regno
, new_regno
;
649 rtx old_reg
, new_reg
, prev_reg
;
651 old_reg
= *set_data
->reg_loc
;
652 regno
= REGNO (*set_data
->reg_loc
);
654 /* For the first set we come across, reuse the original regno. */
655 if (ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
] == NULL_RTX
)
658 prev_reg
= RENAME_NO_RTX
;
662 prev_reg
= ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
];
663 new_reg
= gen_reg_rtx (GET_MODE (old_reg
));
666 set_data
->new_reg
= new_reg
;
667 set_data
->prev_reg
= prev_reg
;
668 new_regno
= REGNO (new_reg
);
669 ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
] = new_reg
;
671 if (new_regno
>= (int) ssa_definition
->num_elements
)
673 int new_limit
= new_regno
* 5 / 4;
674 ssa_definition
= VARRAY_GROW (ssa_definition
, new_limit
);
675 ssa_uses
= VARRAY_GROW (ssa_uses
, new_limit
);
676 ssa_rename_from
= VARRAY_GROW (ssa_rename_from
, new_limit
);
679 VARRAY_RTX (ssa_definition
, new_regno
) = insn
;
680 VARRAY_RTX (ssa_rename_from
, new_regno
) = old_reg
;
682 set_data
= set_data
->next
;
687 rename_block (bb
, idom
)
691 basic_block b
= BASIC_BLOCK (bb
);
693 rtx insn
, next
, last
;
694 struct rename_set_data
*set_data
= NULL
;
697 /* Step One: Walk the basic block, adding new names for sets and
705 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
707 struct rename_context context
;
708 context
.set_data
= set_data
;
709 context
.current_insn
= insn
;
711 for_each_rtx (&PATTERN (insn
), rename_insn_1
, &context
);
712 for_each_rtx (®_NOTES (insn
), rename_insn_1
, &context
);
714 new_registers_for_updates (context
.set_data
, set_data
, insn
);
715 set_data
= context
.set_data
;
718 next
= NEXT_INSN (insn
);
720 while (insn
!= last
);
722 /* Step Two: Update the phi nodes of this block's successors. */
724 for (e
= b
->succ
; e
; e
= e
->succ_next
)
726 if (e
->dest
== EXIT_BLOCK_PTR
)
729 insn
= e
->dest
->head
;
730 if (GET_CODE (insn
) == CODE_LABEL
)
731 insn
= NEXT_INSN (insn
);
733 while (PHI_NODE_P (insn
))
735 rtx phi
= PATTERN (insn
);
739 /* Find out which of our outgoing registers this node is
740 indended to replace. Note that if this not the first PHI
741 node to have been created for this register, we have to
742 jump through rename links to figure out which register
743 we're talking about. This can easily be recognized by
744 noting that the regno is new to this pass. */
745 regno
= REGNO (SET_DEST (phi
));
746 if (regno
>= ssa_max_reg_num
)
747 regno
= REGNO (VARRAY_RTX (ssa_rename_from
, regno
));
748 reg
= ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
];
750 /* It is possible for the variable to be uninitialized on
751 edges in. Reduce the arity of the PHI so that we don't
752 consider those edges. */
753 if (reg
== NULL
|| reg
== RENAME_NO_RTX
)
755 if (! remove_phi_alternative (phi
, bb
))
760 /* When we created the PHI nodes, we did not know what mode
761 the register should be. Now that we've found an original,
762 we can fill that in. */
763 if (GET_MODE (SET_DEST (phi
)) == VOIDmode
)
764 PUT_MODE (SET_DEST (phi
), GET_MODE (reg
));
765 else if (GET_MODE (SET_DEST (phi
)) != GET_MODE (reg
))
768 *phi_alternative (phi
, bb
) = reg
;
769 /* ??? Mark for a new ssa_uses entry. */
772 insn
= NEXT_INSN (insn
);
776 /* Step Three: Do the same to the children of this block in
779 for (c
= 0; c
< n_basic_blocks
; ++c
)
781 rename_block (c
, idom
);
783 /* Step Four: Update the sets to refer to their new register. */
787 struct rename_set_data
*next
;
788 rtx old_reg
= *set_data
->reg_loc
;
790 /* If the set is of a subreg only, copy the entire reg first so
791 that unmodified bits are preserved. Of course, we don't
792 strictly have SSA any more, but that's the best we can do
793 without a lot of hard work. */
795 if (GET_CODE (set_data
->set_dest
) == SUBREG
)
797 if (old_reg
!= set_data
->new_reg
)
799 rtx copy
= gen_rtx_SET (GET_MODE (old_reg
),
800 set_data
->new_reg
, old_reg
);
801 emit_insn_before (copy
, set_data
->set_insn
);
805 *set_data
->reg_loc
= set_data
->new_reg
;
806 ssa_rename_to
[REGNO (old_reg
)-FIRST_PSEUDO_REGISTER
]
807 = set_data
->prev_reg
;
809 next
= set_data
->next
;
816 rename_registers (nregs
, idom
)
820 VARRAY_RTX_INIT (ssa_definition
, nregs
* 3, "ssa_definition");
821 VARRAY_RTX_INIT (ssa_uses
, nregs
* 3, "ssa_uses");
822 VARRAY_RTX_INIT (ssa_rename_from
, nregs
* 3, "ssa_rename_from");
824 ssa_rename_to
= (rtx
*) alloca (nregs
* sizeof(rtx
));
825 bzero ((char *) ssa_rename_to
, nregs
* sizeof(rtx
));
827 rename_block (0, idom
);
829 /* ??? Update basic_block_live_at_start, and other flow info
832 ssa_rename_to
= NULL
;
836 /* The main entry point for moving to SSA. */
841 /* Element I is the set of blocks that set register I. */
844 /* Dominator bitmaps. */
849 /* Element I is the immediate dominator of block I. */
854 /* Don't do it twice. */
858 /* Need global_live_at_{start,end} up to date. */
859 life_analysis (get_insns (), NULL
, PROP_KILL_DEAD_CODE
| PROP_SCAN_DEAD_CODE
);
861 /* Compute dominators. */
862 dominators
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
863 compute_flow_dominators (dominators
, NULL
);
865 idom
= (int *) alloca (n_basic_blocks
* sizeof (int));
866 memset ((void *)idom
, -1, (size_t)n_basic_blocks
* sizeof (int));
867 simplify_to_immediate_dominators (idom
, dominators
);
869 sbitmap_vector_free (dominators
);
874 fputs (";; Immediate Dominators:\n", rtl_dump_file
);
875 for (i
= 0; i
< n_basic_blocks
; ++i
)
876 fprintf (rtl_dump_file
, ";\t%3d = %3d\n", i
, idom
[i
]);
877 fflush (rtl_dump_file
);
880 /* Compute dominance frontiers. */
882 dfs
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
883 compute_dominance_frontiers (dfs
, idom
);
887 dump_sbitmap_vector (rtl_dump_file
, ";; Dominance Frontiers:",
888 "; Basic Block", dfs
, n_basic_blocks
);
889 fflush (rtl_dump_file
);
892 /* Compute register evaluations. */
894 ssa_max_reg_num
= max_reg_num();
895 nregs
= ssa_max_reg_num
- FIRST_PSEUDO_REGISTER
;
896 evals
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
897 find_evaluations (evals
, nregs
);
899 /* Compute the iterated dominance frontier for each register. */
901 idfs
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
902 compute_iterated_dominance_frontiers (idfs
, dfs
, evals
, nregs
);
906 dump_sbitmap_vector (rtl_dump_file
, ";; Iterated Dominance Frontiers:",
907 "; Register-FIRST_PSEUDO_REGISTER", idfs
, nregs
);
908 fflush (rtl_dump_file
);
911 /* Insert the phi nodes. */
913 insert_phi_nodes (idfs
, evals
, nregs
);
915 /* Rename the registers to satisfy SSA. */
917 rename_registers (nregs
, idom
);
919 /* All done! Clean up and go home. */
921 sbitmap_vector_free (dfs
);
922 sbitmap_vector_free (evals
);
923 sbitmap_vector_free (idfs
);
926 reg_scan (get_insns (), max_reg_num (), 1);
930 /* REG is the representative temporary of its partition. Add it to the
931 set of nodes to be processed, if it hasn't been already. Return the
932 index of this register in the node set. */
935 ephi_add_node (reg
, nodes
, n_nodes
)
940 for (i
= *n_nodes
- 1; i
>= 0; --i
)
941 if (REGNO (reg
) == REGNO (nodes
[i
]))
944 nodes
[i
= (*n_nodes
)++] = reg
;
948 /* Part one of the topological sort. This is a forward (downward) search
949 through the graph collecting a stack of nodes to process. Assuming no
950 cycles, the nodes at top of the stack when we are finished will have
951 no other dependancies. */
954 ephi_forward (t
, visited
, succ
, tstack
)
962 SET_BIT (visited
, t
);
964 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
966 if (! TEST_BIT (visited
, s
))
967 tstack
= ephi_forward (s
, visited
, succ
, tstack
);
974 /* Part two of the topological sort. The is a backward search through
975 a cycle in the graph, copying the data forward as we go. */
978 ephi_backward (t
, visited
, pred
, nodes
)
980 sbitmap visited
, *pred
;
985 SET_BIT (visited
, t
);
987 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
989 if (! TEST_BIT (visited
, p
))
991 ephi_backward (p
, visited
, pred
, nodes
);
992 emit_move_insn (nodes
[p
], nodes
[t
]);
997 /* Part two of the topological sort. Create the copy for a register
998 and any cycle of which it is a member. */
1001 ephi_create (t
, visited
, pred
, succ
, nodes
)
1003 sbitmap visited
, *pred
, *succ
;
1006 rtx reg_u
= NULL_RTX
;
1007 int unvisited_predecessors
= 0;
1010 /* Iterate through the predecessor list looking for unvisited nodes.
1011 If there are any, we have a cycle, and must deal with that. At
1012 the same time, look for a visited predecessor. If there is one,
1013 we won't need to create a temporary. */
1015 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1017 if (! TEST_BIT (visited
, p
))
1018 unvisited_predecessors
= 1;
1023 if (unvisited_predecessors
)
1025 /* We found a cycle. Copy out one element of the ring (if necessary),
1026 then traverse the ring copying as we go. */
1030 reg_u
= gen_reg_rtx (GET_MODE (nodes
[t
]));
1031 emit_move_insn (reg_u
, nodes
[t
]);
1034 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1036 if (! TEST_BIT (visited
, p
))
1038 ephi_backward (p
, visited
, pred
, nodes
);
1039 emit_move_insn (nodes
[p
], reg_u
);
1045 /* No cycle. Just copy the value from a successor. */
1048 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1050 SET_BIT (visited
, t
);
1051 emit_move_insn (nodes
[t
], nodes
[s
]);
1057 /* Convert the edge to normal form. */
1060 eliminate_phi (e
, reg_partition
)
1062 partition reg_partition
;
1065 sbitmap
*pred
, *succ
;
1068 int *stack
, *tstack
;
1072 /* Collect an upper bound on the number of registers needing processing. */
1074 insn
= e
->dest
->head
;
1075 if (GET_CODE (insn
) == CODE_LABEL
)
1076 insn
= next_nonnote_insn (insn
);
1079 while (PHI_NODE_P (insn
))
1081 insn
= next_nonnote_insn (insn
);
1088 /* Build the auxilliary graph R(B).
1090 The nodes of the graph are the members of the register partition
1091 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1092 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1094 nodes
= (rtx
*) alloca (n_nodes
* sizeof(rtx
));
1095 pred
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1096 succ
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1097 sbitmap_vector_zero (pred
, n_nodes
);
1098 sbitmap_vector_zero (succ
, n_nodes
);
1100 insn
= e
->dest
->head
;
1101 if (GET_CODE (insn
) == CODE_LABEL
)
1102 insn
= next_nonnote_insn (insn
);
1105 for (; PHI_NODE_P (insn
); insn
= next_nonnote_insn (insn
))
1107 rtx
* preg
= phi_alternative (PATTERN (insn
), e
->src
->index
);
1108 rtx tgt
= SET_DEST (PATTERN (insn
));
1111 /* There may be no phi alternative corresponding to this edge.
1112 This indicates that the phi variable is undefined along this
1118 if (GET_CODE (reg
) != REG
|| GET_CODE (tgt
) != REG
)
1121 reg
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (reg
))];
1122 tgt
= regno_reg_rtx
[partition_find (reg_partition
, REGNO (tgt
))];
1123 /* If the two registers are already in the same partition,
1124 nothing will need to be done. */
1129 ireg
= ephi_add_node (reg
, nodes
, &n_nodes
);
1130 itgt
= ephi_add_node (tgt
, nodes
, &n_nodes
);
1132 SET_BIT (pred
[ireg
], itgt
);
1133 SET_BIT (succ
[itgt
], ireg
);
1140 /* Begin a topological sort of the graph. */
1142 visited
= sbitmap_alloc (n_nodes
);
1143 sbitmap_zero (visited
);
1145 tstack
= stack
= (int *) alloca (n_nodes
* sizeof (int));
1147 for (i
= 0; i
< n_nodes
; ++i
)
1148 if (! TEST_BIT (visited
, i
))
1149 tstack
= ephi_forward (i
, visited
, succ
, tstack
);
1151 sbitmap_zero (visited
);
1153 /* As we find a solution to the tsort, collect the implementation
1154 insns in a sequence. */
1157 while (tstack
!= stack
)
1160 if (! TEST_BIT (visited
, i
))
1161 ephi_create (i
, visited
, pred
, succ
, nodes
);
1164 insn
= gen_sequence ();
1166 insert_insn_on_edge (insn
, e
);
1168 fprintf (rtl_dump_file
, "Emitting copy on edge (%d,%d)\n",
1169 e
->src
->index
, e
->dest
->index
);
1171 sbitmap_free (visited
);
1173 sbitmap_vector_free (pred
);
1174 sbitmap_vector_free (succ
);
1178 /* For basic block B, consider all phi insns which provide an
1179 alternative corresponding to an incoming abnormal critical edge.
1180 Place the phi alternative corresponding to that abnormal critical
1181 edge in the same register class as the destination of the set.
1183 From Morgan, p. 178:
1185 For each abnormal critical edge (C, B),
1186 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1187 and C is the ith predecessor of B,
1188 then T0 and Ti must be equivalent.
1190 Return non-zero iff any such cases were found for which the two
1191 regs were not already in the same class. */
1194 make_regs_equivalent_over_bad_edges (bb
, reg_partition
)
1196 partition reg_partition
;
1199 basic_block b
= BASIC_BLOCK (bb
);
1202 /* Advance to the first phi node. */
1203 if (GET_CODE (phi
) == CODE_LABEL
)
1204 phi
= next_nonnote_insn (phi
);
1206 /* Scan all the phi nodes. */
1209 phi
= next_nonnote_insn (phi
))
1213 rtx set
= PATTERN (phi
);
1214 rtx tgt
= SET_DEST (set
);
1216 /* The set target is expected to be a pseudo. */
1217 if (GET_CODE (tgt
) != REG
1218 || REGNO (tgt
) < FIRST_PSEUDO_REGISTER
)
1220 tgt_regno
= REGNO (tgt
);
1222 /* Scan incoming abnormal critical edges. */
1223 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1224 if ((e
->flags
& (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1225 == (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1227 rtx
*alt
= phi_alternative (set
, e
->src
->index
);
1230 /* If there is no alternative corresponding to this edge,
1231 the value is undefined along the edge, so just go on. */
1235 /* The phi alternative is expected to be a pseudo. */
1236 if (GET_CODE (*alt
) != REG
1237 || REGNO (*alt
) < FIRST_PSEUDO_REGISTER
)
1239 alt_regno
= REGNO (*alt
);
1241 /* If the set destination and the phi alternative aren't
1242 already in the same class... */
1243 if (partition_find (reg_partition
, tgt_regno
)
1244 != partition_find (reg_partition
, alt_regno
))
1246 /* ... make them such. */
1247 partition_union (reg_partition
,
1248 tgt_regno
, alt_regno
);
1258 /* Consider phi insns in basic block BB pairwise. If the set target
1259 of both isns are equivalent pseudos, make the corresponding phi
1260 alternatives in each phi corresponding equivalent.
1262 Return nonzero if any new register classes were unioned. */
1265 make_equivalent_phi_alternatives_equivalent (bb
, reg_partition
)
1267 partition reg_partition
;
1270 rtx phi
= BLOCK_HEAD (bb
);
1271 basic_block b
= BASIC_BLOCK (bb
);
1273 /* Advance to the first phi node. */
1274 if (GET_CODE (phi
) == CODE_LABEL
)
1275 phi
= next_nonnote_insn (phi
);
1277 /* Scan all the phi nodes. */
1280 phi
= next_nonnote_insn (phi
))
1282 rtx set
= PATTERN (phi
);
1283 /* The regno of the destination of the set. */
1284 int tgt_regno
= REGNO (SET_DEST (PATTERN (phi
)));
1286 rtx phi2
= next_nonnote_insn (phi
);
1288 /* Scan all phi nodes following this one. */
1291 phi2
= next_nonnote_insn (phi2
))
1293 rtx set2
= PATTERN (phi2
);
1294 /* The regno of the destination of the set. */
1295 int tgt2_regno
= REGNO (SET_DEST (set2
));
1297 /* Are the set destinations equivalent regs? */
1298 if (partition_find (reg_partition
, tgt_regno
) ==
1299 partition_find (reg_partition
, tgt2_regno
))
1302 /* Scan over edges. */
1303 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1305 int pred_block
= e
->src
->index
;
1306 /* Identify the phi altnernatives from both phi
1307 nodes corresponding to this edge. */
1308 rtx
*alt
= phi_alternative (set
, pred_block
);
1309 rtx
*alt2
= phi_alternative (set2
, pred_block
);
1311 /* If one of the phi nodes doesn't have a
1312 corresponding alternative, just skip it. */
1313 if (alt
== 0 || alt2
== 0)
1316 /* Both alternatives should be pseudos. */
1317 if (GET_CODE (*alt
) != REG
1318 || REGNO (*alt
) < FIRST_PSEUDO_REGISTER
)
1320 if (GET_CODE (*alt2
) != REG
1321 || REGNO (*alt2
) < FIRST_PSEUDO_REGISTER
)
1324 /* If the altneratives aren't already in the same
1326 if (partition_find (reg_partition
, REGNO (*alt
))
1327 != partition_find (reg_partition
, REGNO (*alt2
)))
1329 /* ... make them so. */
1330 partition_union (reg_partition
,
1331 REGNO (*alt
), REGNO (*alt2
));
1342 /* Compute a conservative partition of outstanding pseudo registers.
1343 See Morgan 7.3.1. */
1346 compute_conservative_reg_partition ()
1351 /* We don't actually work with hard registers, but it's easier to
1352 carry them around anyway rather than constantly doing register
1353 number arithmetic. */
1355 partition_new (ssa_definition
->num_elements
+ FIRST_PSEUDO_REGISTER
);
1357 /* The first priority is to make sure registers that might have to
1358 be copied on abnormal critical edges are placed in the same
1359 partition. This saves us from having to split abnormal critical
1361 for (bb
= n_basic_blocks
; --bb
>= 0; )
1362 changed
+= make_regs_equivalent_over_bad_edges (bb
, p
);
1364 /* Now we have to insure that corresponding arguments of phi nodes
1365 assigning to corresponding regs are equivalent. Iterate until
1370 for (bb
= n_basic_blocks
; --bb
>= 0; )
1371 changed
+= make_equivalent_phi_alternatives_equivalent (bb
, p
);
1377 /* The following functions compute a register partition that attempts
1378 to eliminate as many reg copies and phi node copies as possible by
1379 coalescing registers. This is the strategy:
1381 1. As in the conservative case, the top priority is to coalesce
1382 registers that otherwise would cause copies to be placed on
1383 abnormal critical edges (which isn't possible).
1385 2. Figure out which regs are involved (in the LHS or RHS) of
1386 copies and phi nodes. Compute conflicts among these regs.
1388 3. Walk around the instruction stream, placing two regs in the
1389 same class of the partition if one appears on the LHS and the
1390 other on the RHS of a copy or phi node and the two regs don't
1391 conflict. The conflict information of course needs to be
1394 4. If anything has changed, there may be new opportunities to
1395 coalesce regs, so go back to 2.
1398 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1399 same class of partition P, if they aren't already. Update
1400 CONFLICTS appropriately.
1402 Returns one if REG1 and REG2 were placed in the same class but were
1403 not previously; zero otherwise.
1405 See Morgan figure 11.15. */
1408 coalesce_if_unconflicting (p
, conflicts
, reg1
, reg2
)
1410 conflict_graph conflicts
;
1416 /* Don't mess with hard regs. */
1417 if (reg1
< FIRST_PSEUDO_REGISTER
|| reg2
< FIRST_PSEUDO_REGISTER
)
1420 /* Find the canonical regs for the classes containing REG1 and
1422 reg1
= partition_find (p
, reg1
);
1423 reg2
= partition_find (p
, reg2
);
1425 /* If they're already in the same class, there's nothing to do. */
1429 /* If the regs conflict, our hands are tied. */
1430 if (conflict_graph_conflict_p (conflicts
, reg1
, reg2
))
1433 /* We're good to go. Put the regs in the same partition. */
1434 partition_union (p
, reg1
, reg2
);
1436 /* Find the new canonical reg for the merged class. */
1437 reg
= partition_find (p
, reg1
);
1439 /* Merge conflicts from the two previous classes. */
1440 conflict_graph_merge_regs (conflicts
, reg
, reg1
);
1441 conflict_graph_merge_regs (conflicts
, reg
, reg2
);
1446 /* For each register copy insn in basic block BB, place the LHS and
1447 RHS regs in the same class in partition P if they do not conflict
1448 according to CONFLICTS.
1450 Returns the number of changes that were made to P.
1452 See Morgan figure 11.14. */
1455 coalesce_regs_in_copies (bb
, p
, conflicts
)
1458 conflict_graph conflicts
;
1464 /* Scan the instruction stream of the block. */
1465 for (insn
= bb
->head
; insn
!= end
; insn
= NEXT_INSN (insn
))
1471 /* If this isn't a set insn, go to the next insn. */
1472 if (GET_CODE (insn
) != INSN
)
1474 pattern
= PATTERN (insn
);
1475 if (GET_CODE (pattern
) != SET
)
1478 src
= SET_SRC (pattern
);
1479 dest
= SET_DEST (pattern
);
1481 /* If src or dest are subregs, find the underlying reg. */
1482 while (GET_CODE (src
) == SUBREG
1483 && SUBREG_WORD (src
) != 0)
1484 src
= SUBREG_REG (src
);
1485 while (GET_CODE (dest
) == SUBREG
1486 && SUBREG_WORD (dest
) != 0)
1487 dest
= SUBREG_REG (dest
);
1489 /* We're only looking for copies. */
1490 if (GET_CODE (src
) != REG
|| GET_CODE (dest
) != REG
)
1493 /* Coalesce only if the reg modes are the same. As long as
1494 each reg's rtx is unique, it can have only one mode, so two
1495 pseudos of different modes can't be coalesced into one.
1497 FIXME: We can probably get around this by inserting SUBREGs
1498 where appropriate, but for now we don't bother. */
1499 if (GET_MODE (src
) != GET_MODE (dest
))
1502 /* Found a copy; see if we can use the same reg for both the
1503 source and destination (and thus eliminate the copy,
1505 changed
+= coalesce_if_unconflicting (p
, conflicts
,
1506 REGNO (src
), REGNO (dest
));
1513 struct phi_coalesce_context
1516 conflict_graph conflicts
;
1520 /* Callback function for for_each_successor_phi. If the set
1521 destination and the phi alternative regs do not conflict, place
1522 them in the same paritition class. DATA is a pointer to a
1523 phi_coalesce_context struct. */
1526 coalesce_reg_in_phi (insn
, dest_regno
, src_regno
, data
)
1527 rtx insn ATTRIBUTE_UNUSED
;
1532 struct phi_coalesce_context
*context
=
1533 (struct phi_coalesce_context
*) data
;
1535 /* Attempt to use the same reg, if they don't conflict. */
1537 += coalesce_if_unconflicting (context
->p
, context
->conflicts
,
1538 dest_regno
, src_regno
);
1542 /* For each alternative in a phi function corresponding to basic block
1543 BB (in phi nodes in successor block to BB), place the reg in the
1544 phi alternative and the reg to which the phi value is set into the
1545 same class in partition P, if allowed by CONFLICTS.
1547 Return the number of changes that were made to P.
1549 See Morgan figure 11.14. */
1552 coalesce_regs_in_successor_phi_nodes (bb
, p
, conflicts
)
1555 conflict_graph conflicts
;
1557 struct phi_coalesce_context context
;
1559 context
.conflicts
= conflicts
;
1560 context
.changed
= 0;
1562 for_each_successor_phi (bb
, &coalesce_reg_in_phi
, &context
);
1564 return context
.changed
;
1567 /* Compute and return a partition of pseudos. Where possible,
1568 non-conflicting pseudos are placed in the same class.
1570 The caller is responsible for deallocating the returned partition. */
1573 compute_coalesced_reg_partition ()
1578 /* We don't actually work with hard registers, but it's easier to
1579 carry them around anyway rather than constantly doing register
1580 number arithmetic. */
1582 partition_new (ssa_definition
->num_elements
+ FIRST_PSEUDO_REGISTER
);
1584 /* The first priority is to make sure registers that might have to
1585 be copied on abnormal critical edges are placed in the same
1586 partition. This saves us from having to split abnormal critical
1587 edges (which can't be done). */
1588 for (bb
= n_basic_blocks
; --bb
>= 0; )
1589 make_regs_equivalent_over_bad_edges (bb
, p
);
1593 regset_head phi_set
;
1594 conflict_graph conflicts
;
1598 /* Build the set of registers involved in phi nodes, either as
1599 arguments to the phi function or as the target of a set. */
1600 INITIALIZE_REG_SET (phi_set
);
1601 mark_phi_and_copy_regs (&phi_set
);
1603 /* Compute conflicts. */
1604 conflicts
= conflict_graph_compute (&phi_set
, p
);
1606 /* FIXME: Better would be to process most frequently executed
1607 blocks first, so that most frequently executed copies would
1608 be more likely to be removed by register coalescing. But any
1609 order will generate correct, if non-optimal, results. */
1610 for (bb
= n_basic_blocks
; --bb
>= 0; )
1612 basic_block block
= BASIC_BLOCK (bb
);
1613 changed
+= coalesce_regs_in_copies (block
, p
, conflicts
);
1615 coalesce_regs_in_successor_phi_nodes (block
, p
, conflicts
);
1618 conflict_graph_delete (conflicts
);
1620 while (changed
> 0);
1625 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1626 components (a REG or a CONST_INT). DATA is a reg set in which to
1627 set all regs. Called from for_each_rtx. */
1630 mark_reg_in_phi (ptr
, data
)
1635 regset set
= (regset
) data
;
1637 switch (GET_CODE (expr
))
1640 SET_REGNO_REG_SET (set
, REGNO (expr
));
1650 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1651 set from a phi expression, or used as an argument in one. Also
1652 mark regs that are the source or target of a reg copy. Uses
1656 mark_phi_and_copy_regs (phi_set
)
1661 /* Scan the definitions of all regs. */
1662 for (reg
= VARRAY_SIZE (ssa_definition
);
1663 --reg
>= FIRST_PSEUDO_REGISTER
;
1666 rtx insn
= VARRAY_RTX (ssa_definition
, reg
);
1672 pattern
= PATTERN (insn
);
1673 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1675 if (GET_CODE (pattern
) != SET
)
1677 src
= SET_SRC (pattern
);
1679 if (GET_CODE (src
) == REG
)
1681 /* It's a reg copy. */
1682 SET_REGNO_REG_SET (phi_set
, reg
);
1683 SET_REGNO_REG_SET (phi_set
, REGNO (src
));
1685 else if (GET_CODE (src
) == PHI
)
1687 /* It's a phi node. Mark the reg being set. */
1688 SET_REGNO_REG_SET (phi_set
, reg
);
1689 /* Mark the regs used in the phi function. */
1690 for_each_rtx (&src
, mark_reg_in_phi
, phi_set
);
1692 /* ... else nothing to do. */
1696 /* Rename regs in insn PTR that are equivalent. DATA is the register
1697 partition which specifies equivalences. */
1700 rename_equivalent_regs_in_insn (ptr
, data
)
1705 partition reg_partition
= (partition
) data
;
1710 switch (GET_CODE (x
))
1714 rtx
*destp
= &SET_DEST (x
);
1715 rtx dest
= SET_DEST (x
);
1717 /* Subregs at word 0 are interesting. Subregs at word != 0 are
1718 presumed to be part of a contiguous multi-word set sequence. */
1719 while (GET_CODE (dest
) == SUBREG
1720 && SUBREG_WORD (dest
) == 0)
1722 destp
= &SUBREG_REG (dest
);
1723 dest
= SUBREG_REG (dest
);
1726 if (GET_CODE (dest
) == REG
1727 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
1729 /* Got a pseudo; replace it. */
1730 int regno
= REGNO (dest
);
1731 int new_regno
= partition_find (reg_partition
, regno
);
1732 if (regno
!= new_regno
)
1733 *destp
= regno_reg_rtx
[new_regno
];
1735 for_each_rtx (&SET_SRC (x
),
1736 rename_equivalent_regs_in_insn
,
1741 /* Otherwise, this was not an interesting destination. Continue
1742 on, marking uses as normal. */
1747 if (REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1749 int regno
= REGNO (x
);
1750 int new_regno
= partition_find (reg_partition
, regno
);
1751 if (regno
!= new_regno
)
1753 rtx new_reg
= regno_reg_rtx
[new_regno
];
1754 if (GET_MODE (x
) != GET_MODE (new_reg
))
1762 /* No need to rename the phi nodes. We'll check equivalence
1763 when inserting copies. */
1767 /* Anything else, continue traversing. */
1772 /* Rename regs that are equivalent in REG_PARTITION. */
1775 rename_equivalent_regs (reg_partition
)
1776 partition reg_partition
;
1780 for (bb
= n_basic_blocks
; --bb
>= 0; )
1782 basic_block b
= BASIC_BLOCK (bb
);
1790 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1792 for_each_rtx (&PATTERN (insn
),
1793 rename_equivalent_regs_in_insn
,
1795 for_each_rtx (®_NOTES (insn
),
1796 rename_equivalent_regs_in_insn
,
1800 next
= NEXT_INSN (insn
);
1802 while (insn
!= last
);
1806 /* The main entry point for moving from SSA. */
1812 partition reg_partition
;
1813 rtx insns
= get_insns ();
1815 /* Need global_live_at_{start,end} up to date. */
1816 life_analysis (insns
, NULL
,
1817 PROP_KILL_DEAD_CODE
| PROP_SCAN_DEAD_CODE
| PROP_DEATH_NOTES
);
1819 /* Figure out which regs in copies and phi nodes don't conflict and
1820 therefore can be coalesced. */
1821 if (conservative_reg_partition
)
1822 reg_partition
= compute_conservative_reg_partition ();
1824 reg_partition
= compute_coalesced_reg_partition ();
1826 rename_equivalent_regs (reg_partition
);
1828 /* Eliminate the PHI nodes. */
1829 for (bb
= n_basic_blocks
; --bb
>= 0; )
1831 basic_block b
= BASIC_BLOCK (bb
);
1834 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1835 if (e
->src
!= ENTRY_BLOCK_PTR
)
1836 eliminate_phi (e
, reg_partition
);
1839 partition_delete (reg_partition
);
1841 /* Actually delete the PHI nodes. */
1842 for (bb
= n_basic_blocks
; --bb
>= 0; )
1844 rtx insn
= BLOCK_HEAD (bb
);
1845 int start
= (GET_CODE (insn
) != CODE_LABEL
);
1848 insn
= next_nonnote_insn (insn
);
1849 while (PHI_NODE_P (insn
))
1851 /* If a phi node is the last insn in the block, there must
1852 have been nothing else. Set the block end to the block
1854 if (insn
== BLOCK_END (bb
))
1855 BLOCK_END (bb
) = BLOCK_HEAD (bb
);
1856 insn
= delete_insn (insn
);
1857 if (GET_CODE (insn
) == NOTE
)
1858 insn
= next_nonnote_insn (insn
);
1861 BLOCK_HEAD (bb
) = insn
;
1864 /* Commit all the copy nodes needed to convert out of SSA form. */
1865 commit_edge_insertions ();
1869 count_or_remove_death_notes (NULL
, 1);
1872 /* Scan phi nodes in successors to BB. For each such phi node that
1873 has a phi alternative value corresponding to BB, invoke FN. FN
1874 is passed the entire phi node insn, the regno of the set
1875 destination, the regno of the phi argument corresponding to BB,
1878 If FN ever returns non-zero, stops immediately and returns this
1879 value. Otherwise, returns zero. */
1882 for_each_successor_phi (bb
, fn
, data
)
1884 successor_phi_fn fn
;
1889 if (bb
== EXIT_BLOCK_PTR
)
1892 /* Scan outgoing edges. */
1893 for (e
= bb
->succ
; e
!= NULL
; e
= e
->succ_next
)
1897 basic_block successor
= e
->dest
;
1898 if (successor
== ENTRY_BLOCK_PTR
1899 || successor
== EXIT_BLOCK_PTR
)
1902 /* Advance to the first non-label insn of the successor block. */
1903 insn
= successor
->head
;
1905 && (GET_CODE (insn
) == CODE_LABEL
1906 || GET_CODE (insn
) == NOTE
))
1907 insn
= NEXT_INSN (insn
);
1912 /* Scan phi nodes in the successor. */
1913 for ( ; PHI_NODE_P (insn
); insn
= NEXT_INSN (insn
))
1916 rtx phi_set
= PATTERN (insn
);
1917 rtx
*alternative
= phi_alternative (phi_set
, bb
->index
);
1920 /* This phi function may not have an alternative
1921 corresponding to the incoming edge, indicating the
1922 assigned variable is not defined along the edge. */
1923 if (alternative
== NULL
)
1925 phi_src
= *alternative
;
1927 /* Invoke the callback. */
1928 result
= (*fn
) (insn
, REGNO (SET_DEST (phi_set
)),
1929 REGNO (phi_src
), data
);
1931 /* Terminate if requested. */