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
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
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
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
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 ??? What to do about strict_low_part. Probably I'll have to split
52 them out of their current instructions first thing.
54 Actually the best solution may be to have a kind of "mid-level rtl"
55 in which the RTL encodes exactly what we want, without exposing a
56 lot of niggling processor details. At some later point we lower
57 the representation, calling back into optabs to finish any necessary
62 /* Element I is the single instruction that sets register I+PSEUDO. */
63 varray_type ssa_definition
;
65 /* Element I is an INSN_LIST of instructions that use register I+PSEUDO. */
68 /* Element I-PSEUDO is the normal register that originated the ssa
69 register in question. */
70 varray_type ssa_rename_from
;
72 /* The running target ssa register for a given normal register. */
73 static rtx
*ssa_rename_to
;
75 /* The number of registers that were live on entry to the SSA routines. */
76 static int ssa_max_reg_num
;
78 /* Local function prototypes. */
80 static inline rtx
* phi_alternative
83 static int remove_phi_alternative
85 static void simplify_to_immediate_dominators
86 PARAMS ((int *idom
, sbitmap
*dominators
));
87 static void compute_dominance_frontiers_1
88 PARAMS ((sbitmap
*frontiers
, int *idom
, int bb
, sbitmap done
));
89 static void compute_dominance_frontiers
90 PARAMS ((sbitmap
*frontiers
, int *idom
));
91 static void find_evaluations_1
92 PARAMS ((rtx dest
, rtx set
, void *data
));
93 static void find_evaluations
94 PARAMS ((sbitmap
*evals
, int nregs
));
95 static void compute_iterated_dominance_frontiers
96 PARAMS ((sbitmap
*idfs
, sbitmap
*frontiers
, sbitmap
*evals
, int nregs
));
97 static void insert_phi_node
98 PARAMS ((int regno
, int b
));
99 static void insert_phi_nodes
100 PARAMS ((sbitmap
*idfs
, sbitmap
*evals
, int nregs
));
101 static int rename_insn_1
102 PARAMS ((rtx
*ptr
, void *data
));
103 static void rename_block
104 PARAMS ((int b
, int *idom
));
105 static void rename_registers
106 PARAMS ((int nregs
, int *idom
));
108 static inline int ephi_add_node
109 PARAMS ((rtx reg
, rtx
*nodes
, int *n_nodes
));
110 static int * ephi_forward
111 PARAMS ((int t
, sbitmap visited
, sbitmap
*succ
, int *tstack
));
112 static void ephi_backward
113 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, rtx
*nodes
));
114 static void ephi_create
115 PARAMS ((int t
, sbitmap visited
, sbitmap
*pred
, sbitmap
*succ
, rtx
*nodes
));
116 static void eliminate_phi
117 PARAMS ((edge e
, partition reg_partition
));
119 static int make_regs_equivalent_over_bad_edges
120 PARAMS ((int bb
, partition reg_partition
));
121 static int make_equivalent_phi_alternatives_equivalent
122 PARAMS ((int bb
, partition reg_partition
));
123 static partition compute_conservative_reg_partition
125 static int rename_equivalent_regs_in_insn
126 PARAMS ((rtx
*ptr
, void *data
));
127 static void rename_equivalent_regs
128 PARAMS ((partition reg_partition
));
131 /* Determine if the insn is a PHI node. */
132 #define PHI_NODE_P(X) \
133 (X && GET_CODE (X) == INSN \
134 && GET_CODE (PATTERN (X)) == SET \
135 && GET_CODE (SET_SRC (PATTERN (X))) == PHI)
137 /* Given the SET of a PHI node, return the address of the alternative
138 for predecessor block C. */
141 phi_alternative (set
, c
)
145 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
148 for (v
= GET_NUM_ELEM (phi_vec
) - 2; v
>= 0; v
-= 2)
149 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
150 return &RTVEC_ELT (phi_vec
, v
);
155 /* Given the SET of a phi node, remove the alternative for predecessor
156 block C. Return non-zero on success, or zero if no alternative is
160 remove_phi_alternative (set
, c
)
164 rtvec phi_vec
= XVEC (SET_SRC (set
), 0);
165 int num_elem
= GET_NUM_ELEM (phi_vec
);
168 for (v
= num_elem
- 2; v
>= 0; v
-= 2)
169 if (INTVAL (RTVEC_ELT (phi_vec
, v
+ 1)) == c
)
171 if (v
< num_elem
- 2)
173 RTVEC_ELT (phi_vec
, v
) = RTVEC_ELT (phi_vec
, num_elem
- 2);
174 RTVEC_ELT (phi_vec
, v
+ 1) = RTVEC_ELT (phi_vec
, num_elem
- 1);
176 PUT_NUM_ELEM (phi_vec
, num_elem
- 2);
183 /* Computing the Immediate Dominators:
185 Throughout, we don't actually want the full dominators set as
186 calculated by flow, but rather the immediate dominators.
190 simplify_to_immediate_dominators (idom
, dominators
)
197 tmp
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
199 /* Begin with tmp(n) = dom(n) - { n }. */
200 for (b
= n_basic_blocks
; --b
>= 0; )
202 sbitmap_copy (tmp
[b
], dominators
[b
]);
203 RESET_BIT (tmp
[b
], b
);
206 /* Subtract out all of our dominator's dominators. */
207 for (b
= n_basic_blocks
; --b
>= 0; )
209 sbitmap tmp_b
= tmp
[b
];
212 for (s
= n_basic_blocks
; --s
>= 0; )
213 if (TEST_BIT (tmp_b
, s
))
214 sbitmap_difference (tmp_b
, tmp_b
, tmp
[s
]);
217 /* Find the one bit set in the bitmap and put it in the output array. */
218 for (b
= n_basic_blocks
; --b
>= 0; )
221 EXECUTE_IF_SET_IN_SBITMAP (tmp
[b
], 0, t
, { idom
[b
] = t
; });
224 sbitmap_vector_free (tmp
);
228 /* For all registers, find all blocks in which they are set.
230 This is the transform of what would be local kill information that
231 we ought to be getting from flow. */
233 static sbitmap
*fe_evals
;
234 static int fe_current_bb
;
237 find_evaluations_1 (dest
, set
, data
)
239 rtx set ATTRIBUTE_UNUSED
;
240 void *data ATTRIBUTE_UNUSED
;
242 if (GET_CODE (dest
) == REG
243 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
244 SET_BIT (fe_evals
[REGNO (dest
) - FIRST_PSEUDO_REGISTER
], fe_current_bb
);
248 find_evaluations (evals
, nregs
)
254 sbitmap_vector_zero (evals
, nregs
);
257 for (bb
= n_basic_blocks
; --bb
>= 0; )
263 last
= BLOCK_END (bb
);
266 if (GET_RTX_CLASS (GET_CODE (p
)) == 'i')
267 note_stores (PATTERN (p
), find_evaluations_1
, NULL
);
277 /* Computing the Dominance Frontier:
279 As decribed in Morgan, section 3.5, this may be done simply by
280 walking the dominator tree bottom-up, computing the frontier for
281 the children before the parent. When considering a block B,
284 (1) A flow graph edge leaving B that does not lead to a child
285 of B in the dominator tree must be a block that is either equal
286 to B or not dominated by B. Such blocks belong in the frontier
289 (2) Consider a block X in the frontier of one of the children C
290 of B. If X is not equal to B and is not dominated by B, it
291 is in the frontier of B.
295 compute_dominance_frontiers_1 (frontiers
, idom
, bb
, done
)
301 basic_block b
= BASIC_BLOCK (bb
);
306 sbitmap_zero (frontiers
[bb
]);
308 /* Do the frontier of the children first. Not all children in the
309 dominator tree (blocks dominated by this one) are children in the
310 CFG, so check all blocks. */
311 for (c
= 0; c
< n_basic_blocks
; ++c
)
312 if (idom
[c
] == bb
&& ! TEST_BIT (done
, c
))
313 compute_dominance_frontiers_1 (frontiers
, idom
, c
, done
);
315 /* Find blocks conforming to rule (1) above. */
316 for (e
= b
->succ
; e
; e
= e
->succ_next
)
318 if (e
->dest
== EXIT_BLOCK_PTR
)
320 if (idom
[e
->dest
->index
] != bb
)
321 SET_BIT (frontiers
[bb
], e
->dest
->index
);
324 /* Find blocks conforming to rule (2). */
325 for (c
= 0; c
< n_basic_blocks
; ++c
)
329 EXECUTE_IF_SET_IN_SBITMAP (frontiers
[c
], 0, x
,
332 SET_BIT (frontiers
[bb
], x
);
338 compute_dominance_frontiers (frontiers
, idom
)
342 sbitmap done
= sbitmap_alloc (n_basic_blocks
);
345 compute_dominance_frontiers_1 (frontiers
, idom
, 0, done
);
351 /* Computing the Iterated Dominance Frontier:
353 This is the set of merge points for a given register.
355 This is not particularly intuitive. See section 7.1 of Morgan, in
356 particular figures 7.3 and 7.4 and the immediately surrounding text.
360 compute_iterated_dominance_frontiers (idfs
, frontiers
, evals
, nregs
)
369 worklist
= sbitmap_alloc (n_basic_blocks
);
371 for (reg
= 0; reg
< nregs
; ++reg
)
373 sbitmap idf
= idfs
[reg
];
376 /* Start the iterative process by considering those blocks that
377 evaluate REG. We'll add their dominance frontiers to the
378 IDF, and then consider the blocks we just added. */
379 sbitmap_copy (worklist
, evals
[reg
]);
381 /* Morgan's algorithm is incorrect here. Blocks that evaluate
382 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
385 /* Iterate until the worklist is empty. */
390 EXECUTE_IF_SET_IN_SBITMAP (worklist
, 0, b
,
392 RESET_BIT (worklist
, b
);
393 /* For each block on the worklist, add to the IDF all
394 blocks on its dominance frontier that aren't already
395 on the IDF. Every block that's added is also added
397 sbitmap_union_of_diff (worklist
, worklist
, frontiers
[b
], idf
);
398 sbitmap_a_or_b (idf
, idf
, frontiers
[b
]);
405 sbitmap_free (worklist
);
409 fprintf(rtl_dump_file
,
410 "Iterated dominance frontier: %d passes on %d regs.\n",
416 /* Insert the phi nodes. */
419 insert_phi_node (regno
, bb
)
422 basic_block b
= BASIC_BLOCK (bb
);
428 /* Find out how many predecessors there are. */
429 for (e
= b
->pred
, npred
= 0; e
; e
= e
->pred_next
)
430 if (e
->src
!= ENTRY_BLOCK_PTR
)
433 /* If this block has no "interesting" preds, then there is nothing to
434 do. Consider a block that only has the entry block as a pred. */
438 /* This is the register to which the phi function will be assinged. */
439 reg
= regno_reg_rtx
[regno
+ FIRST_PSEUDO_REGISTER
];
441 /* Construct the arguments to the PHI node. The use of pc_rtx is just
442 a placeholder; we'll insert the proper value in rename_registers. */
443 vec
= rtvec_alloc (npred
* 2);
444 for (e
= b
->pred
, i
= 0; e
; e
= e
->pred_next
, i
+= 2)
445 if (e
->src
!= ENTRY_BLOCK_PTR
)
447 RTVEC_ELT (vec
, i
+ 0) = pc_rtx
;
448 RTVEC_ELT (vec
, i
+ 1) = GEN_INT (e
->src
->index
);
451 phi
= gen_rtx_PHI (VOIDmode
, vec
);
452 phi
= gen_rtx_SET (VOIDmode
, reg
, phi
);
454 if (GET_CODE (b
->head
) == CODE_LABEL
)
455 emit_insn_after (phi
, b
->head
);
457 b
->head
= emit_insn_before (phi
, b
->head
);
462 insert_phi_nodes (idfs
, evals
, nregs
)
464 sbitmap
*evals ATTRIBUTE_UNUSED
;
469 for (reg
= 0; reg
< nregs
; ++reg
)
472 EXECUTE_IF_SET_IN_SBITMAP (idfs
[reg
], 0, b
,
474 if (REGNO_REG_SET_P (BASIC_BLOCK (b
)->global_live_at_start
,
475 reg
+ FIRST_PSEUDO_REGISTER
))
476 insert_phi_node (reg
, b
);
481 /* Rename the registers to conform to SSA.
483 This is essentially the algorithm presented in Figure 7.8 of Morgan,
484 with a few changes to reduce pattern search time in favour of a bit
485 more memory usage. */
488 /* One of these is created for each set. It will live in a list local
489 to its basic block for the duration of that block's processing. */
490 struct rename_set_data
492 struct rename_set_data
*next
;
499 static void new_registers_for_updates
500 PARAMS ((struct rename_set_data
*set_data
,
501 struct rename_set_data
*old_set_data
, rtx insn
));
503 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
504 reused. If, during processing, a register has not yet been touched,
505 ssa_rename_to[regno] will be NULL. Now, in the course of pushing
506 and popping values from ssa_rename_to, when we would ordinarily
507 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
508 same as NULL, except that it signals that the original regno has
509 already been reused. */
510 #define RENAME_NO_RTX pc_rtx
512 /* Part one of the first step of rename_block, called through for_each_rtx.
513 Mark pseudos that are set for later update. Transform uses of pseudos. */
516 rename_insn_1 (ptr
, data
)
521 struct rename_set_data
**set_datap
= data
;
526 switch (GET_CODE (x
))
530 rtx
*destp
= &SET_DEST (x
);
531 rtx dest
= SET_DEST (x
);
533 /* Subregs at word 0 are interesting. Subregs at word != 0 are
534 presumed to be part of a contiguous multi-word set sequence. */
535 while (GET_CODE (dest
) == SUBREG
536 && SUBREG_WORD (dest
) == 0)
538 destp
= &SUBREG_REG (dest
);
539 dest
= SUBREG_REG (dest
);
542 if (GET_CODE (dest
) == REG
543 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
545 /* We found a genuine set of an interesting register. Tag
546 it so that we can create a new name for it after we finish
547 processing this insn. */
549 struct rename_set_data
*r
;
550 r
= (struct rename_set_data
*) xmalloc (sizeof(*r
));
553 r
->set_dest
= SET_DEST (x
);
554 r
->next
= *set_datap
;
557 /* Since we do not wish to (directly) traverse the
558 SET_DEST, recurse through for_each_rtx for the SET_SRC
560 for_each_rtx (&SET_SRC (x
), rename_insn_1
, data
);
564 /* Otherwise, this was not an interesting destination. Continue
565 on, marking uses as normal. */
570 if (REGNO (x
) >= FIRST_PSEUDO_REGISTER
571 && REGNO (x
) < ssa_max_reg_num
)
573 rtx new_reg
= ssa_rename_to
[REGNO(x
) - FIRST_PSEUDO_REGISTER
];
575 if (new_reg
!= NULL_RTX
&& new_reg
!= RENAME_NO_RTX
)
577 if (GET_MODE (x
) != GET_MODE (new_reg
))
580 /* ??? Mark for a new ssa_uses entry. */
582 /* Else this is a use before a set. Warn? */
587 /* Never muck with the phi. We do that elsewhere, special-like. */
591 /* Anything else, continue traversing. */
596 /* Second part of the first step of rename_block. The portion of the list
597 beginning at SET_DATA through OLD_SET_DATA contain the sets present in
598 INSN. Update data structures accordingly. */
601 new_registers_for_updates (set_data
, old_set_data
, insn
)
602 struct rename_set_data
*set_data
, *old_set_data
;
605 while (set_data
!= old_set_data
)
607 int regno
, new_regno
;
608 rtx old_reg
, new_reg
, prev_reg
;
610 old_reg
= *set_data
->reg_loc
;
611 regno
= REGNO (*set_data
->reg_loc
);
613 /* For the first set we come across, reuse the original regno. */
614 if (ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
] == NULL_RTX
)
617 prev_reg
= RENAME_NO_RTX
;
621 prev_reg
= ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
];
622 new_reg
= gen_reg_rtx (GET_MODE (old_reg
));
625 set_data
->new_reg
= new_reg
;
626 set_data
->prev_reg
= prev_reg
;
627 new_regno
= REGNO (new_reg
);
628 ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
] = new_reg
;
630 if (new_regno
>= (int) ssa_definition
->num_elements
)
632 int new_limit
= new_regno
* 5 / 4;
633 ssa_definition
= VARRAY_GROW (ssa_definition
, new_limit
);
634 ssa_uses
= VARRAY_GROW (ssa_uses
, new_limit
);
635 ssa_rename_from
= VARRAY_GROW (ssa_rename_from
, new_limit
);
638 VARRAY_RTX (ssa_definition
, new_regno
) = insn
;
639 VARRAY_RTX (ssa_rename_from
, new_regno
) = old_reg
;
641 set_data
= set_data
->next
;
646 rename_block (bb
, idom
)
650 basic_block b
= BASIC_BLOCK (bb
);
652 rtx insn
, next
, last
;
653 struct rename_set_data
*set_data
= NULL
;
656 /* Step One: Walk the basic block, adding new names for sets and
664 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
666 struct rename_set_data
*old_set_data
= set_data
;
668 for_each_rtx (&PATTERN (insn
), rename_insn_1
, &set_data
);
669 for_each_rtx (®_NOTES (insn
), rename_insn_1
, &set_data
);
671 new_registers_for_updates (set_data
, old_set_data
, insn
);
674 next
= NEXT_INSN (insn
);
676 while (insn
!= last
);
678 /* Step Two: Update the phi nodes of this block's successors. */
680 for (e
= b
->succ
; e
; e
= e
->succ_next
)
682 if (e
->dest
== EXIT_BLOCK_PTR
)
685 insn
= e
->dest
->head
;
686 if (GET_CODE (insn
) == CODE_LABEL
)
687 insn
= NEXT_INSN (insn
);
689 while (PHI_NODE_P (insn
))
691 rtx phi
= PATTERN (insn
);
695 /* Find out which of our outgoing registers this node is
696 indended to replace. Note that if this not the first PHI
697 node to have been created for this register, we have to
698 jump through rename links to figure out which register
699 we're talking about. This can easily be recognized by
700 noting that the regno is new to this pass. */
701 regno
= REGNO (SET_DEST (phi
));
702 if (regno
>= ssa_max_reg_num
)
703 regno
= REGNO (VARRAY_RTX (ssa_rename_from
, regno
));
704 reg
= ssa_rename_to
[regno
- FIRST_PSEUDO_REGISTER
];
706 /* It is possible for the variable to be uninitialized on
707 edges in. Reduce the arity of the PHI so that we don't
708 consider those edges. */
709 if (reg
== NULL
|| reg
== RENAME_NO_RTX
)
711 if (! remove_phi_alternative (phi
, bb
))
716 /* When we created the PHI nodes, we did not know what mode
717 the register should be. Now that we've found an original,
718 we can fill that in. */
719 if (GET_MODE (SET_DEST (phi
)) == VOIDmode
)
720 PUT_MODE (SET_DEST (phi
), GET_MODE (reg
));
721 else if (GET_MODE (SET_DEST (phi
)) != GET_MODE (reg
))
724 *phi_alternative (phi
, bb
) = reg
;
725 /* ??? Mark for a new ssa_uses entry. */
728 insn
= NEXT_INSN (insn
);
732 /* Step Three: Do the same to the children of this block in
735 for (c
= 0; c
< n_basic_blocks
; ++c
)
737 rename_block (c
, idom
);
739 /* Step Four: Update the sets to refer to their new register. */
743 struct rename_set_data
*next
;
746 old_reg
= *set_data
->reg_loc
;
747 *set_data
->reg_loc
= set_data
->new_reg
;
748 ssa_rename_to
[REGNO (old_reg
)-FIRST_PSEUDO_REGISTER
]
749 = set_data
->prev_reg
;
751 next
= set_data
->next
;
758 rename_registers (nregs
, idom
)
762 VARRAY_RTX_INIT (ssa_definition
, nregs
* 3, "ssa_definition");
763 VARRAY_RTX_INIT (ssa_uses
, nregs
* 3, "ssa_uses");
764 VARRAY_RTX_INIT (ssa_rename_from
, nregs
* 3, "ssa_rename_from");
766 ssa_rename_to
= (rtx
*) alloca (nregs
* sizeof(rtx
));
767 bzero (ssa_rename_to
, nregs
* sizeof(rtx
));
769 rename_block (0, idom
);
771 /* ??? Update basic_block_live_at_start, and other flow info
774 ssa_rename_to
= NULL
;
778 /* The main entry point for moving to SSA. */
783 /* Element I is the set of blocks that set register I. */
786 /* Dominator bitmaps. */
791 /* Element I is the immediate dominator of block I. */
796 find_basic_blocks (get_insns (), max_reg_num(), NULL
);
797 /* The dominator algorithms assume all blocks are reachable, clean
799 cleanup_cfg (get_insns ());
800 life_analysis (get_insns (), max_reg_num (), NULL
, 1);
802 /* Compute dominators. */
803 dominators
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
804 compute_flow_dominators (dominators
, NULL
);
806 idom
= (int *) alloca (n_basic_blocks
* sizeof (int));
807 memset ((void *)idom
, -1, (size_t)n_basic_blocks
* sizeof (int));
808 simplify_to_immediate_dominators (idom
, dominators
);
810 sbitmap_vector_free (dominators
);
815 fputs (";; Immediate Dominators:\n", rtl_dump_file
);
816 for (i
= 0; i
< n_basic_blocks
; ++i
)
817 fprintf (rtl_dump_file
, ";\t%3d = %3d\n", i
, idom
[i
]);
818 fflush (rtl_dump_file
);
821 /* Compute dominance frontiers. */
823 dfs
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
824 compute_dominance_frontiers (dfs
, idom
);
828 dump_sbitmap_vector (rtl_dump_file
, ";; Dominance Frontiers:",
829 "; Basic Block", dfs
, n_basic_blocks
);
830 fflush (rtl_dump_file
);
833 /* Compute register evaluations. */
835 ssa_max_reg_num
= max_reg_num();
836 nregs
= ssa_max_reg_num
- FIRST_PSEUDO_REGISTER
;
837 evals
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
838 find_evaluations (evals
, nregs
);
840 /* Compute the iterated dominance frontier for each register. */
842 idfs
= sbitmap_vector_alloc (nregs
, n_basic_blocks
);
843 compute_iterated_dominance_frontiers (idfs
, dfs
, evals
, nregs
);
847 dump_sbitmap_vector (rtl_dump_file
, ";; Iterated Dominance Frontiers:",
848 "; Register-FIRST_PSEUDO_REGISTER", idfs
, nregs
);
849 fflush (rtl_dump_file
);
852 /* Insert the phi nodes. */
854 insert_phi_nodes (idfs
, evals
, nregs
);
856 /* Rename the registers to satisfy SSA. */
858 rename_registers (nregs
, idom
);
860 /* All done! Clean up and go home. */
862 sbitmap_vector_free (dfs
);
863 sbitmap_vector_free (evals
);
864 sbitmap_vector_free (idfs
);
868 /* This is intended to be the FIND of a UNION/FIND algorithm managing
869 the partitioning of the pseudos. Glancing through the rest of the
870 global optimizations, it seems things will work out best if the
871 partition is set up just before convert_from_ssa is called. See
872 section 11.4 of Morgan.
874 ??? Morgan's algorithm, perhaps with some care, may allow copy
875 propagation to happen concurrently with the conversion from SSA.
877 However, it presents potential problems with critical edges -- to
878 split or not to split. He mentions beginning the partitioning by
879 unioning registers associated by a PHI across abnormal critical
880 edges. This is the approache taken here. It is unclear to me how
881 we are able to do that arbitrarily, though.
883 Alternately, Briggs presents an algorithm in which critical edges
884 need not be split, at the expense of the creation of new pseudos,
885 and the need for some concurrent register renaming. Moreover, it
886 is ameanable for modification such that the instructions can be
887 placed anywhere in the target block, which solves the before-call
888 placement problem. However, I don't immediately see how we could
889 do that concurrently with copy propoagation.
891 More study is required. */
895 * Eliminate the PHI across the edge from C to B.
898 /* REG is the representative temporary of its partition. Add it to the
899 set of nodes to be processed, if it hasn't been already. Return the
900 index of this register in the node set. */
903 ephi_add_node (reg
, nodes
, n_nodes
)
908 for (i
= *n_nodes
- 1; i
>= 0; --i
)
909 if (REGNO (reg
) == REGNO (nodes
[i
]))
912 nodes
[i
= (*n_nodes
)++] = reg
;
916 /* Part one of the topological sort. This is a forward (downward) search
917 through the graph collecting a stack of nodes to process. Assuming no
918 cycles, the nodes at top of the stack when we are finished will have
919 no other dependancies. */
922 ephi_forward (t
, visited
, succ
, tstack
)
930 SET_BIT (visited
, t
);
932 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
934 if (! TEST_BIT (visited
, s
))
935 tstack
= ephi_forward (s
, visited
, succ
, tstack
);
942 /* Part two of the topological sort. The is a backward search through
943 a cycle in the graph, copying the data forward as we go. */
946 ephi_backward (t
, visited
, pred
, nodes
)
948 sbitmap visited
, *pred
;
953 SET_BIT (visited
, t
);
955 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
957 if (! TEST_BIT (visited
, p
))
959 ephi_backward (p
, visited
, pred
, nodes
);
960 emit_move_insn (nodes
[p
], nodes
[t
]);
965 /* Part two of the topological sort. Create the copy for a register
966 and any cycle of which it is a member. */
969 ephi_create (t
, visited
, pred
, succ
, nodes
)
971 sbitmap visited
, *pred
, *succ
;
974 rtx reg_u
= NULL_RTX
;
975 int unvisited_predecessors
= 0;
978 /* Iterate through the predecessor list looking for unvisited nodes.
979 If there are any, we have a cycle, and must deal with that. At
980 the same time, look for a visited predecessor. If there is one,
981 we won't need to create a temporary. */
983 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
985 if (! TEST_BIT (visited
, p
))
986 unvisited_predecessors
= 1;
991 if (unvisited_predecessors
)
993 /* We found a cycle. Copy out one element of the ring (if necessary),
994 then traverse the ring copying as we go. */
998 reg_u
= gen_reg_rtx (GET_MODE (nodes
[t
]));
999 emit_move_insn (reg_u
, nodes
[t
]);
1002 EXECUTE_IF_SET_IN_SBITMAP (pred
[t
], 0, p
,
1004 if (! TEST_BIT (visited
, p
))
1006 ephi_backward (p
, visited
, pred
, nodes
);
1007 emit_move_insn (nodes
[p
], reg_u
);
1013 /* No cycle. Just copy the value from a successor. */
1016 EXECUTE_IF_SET_IN_SBITMAP (succ
[t
], 0, s
,
1018 SET_BIT (visited
, t
);
1019 emit_move_insn (nodes
[t
], nodes
[s
]);
1025 /* Convert the edge to normal form. */
1028 eliminate_phi (e
, reg_partition
)
1030 partition reg_partition
;
1033 sbitmap
*pred
, *succ
;
1036 int *stack
, *tstack
;
1040 /* Collect an upper bound on the number of registers needing processing. */
1042 insn
= e
->dest
->head
;
1043 if (GET_CODE (insn
) == CODE_LABEL
)
1044 insn
= next_nonnote_insn (insn
);
1047 while (PHI_NODE_P (insn
))
1049 insn
= next_nonnote_insn (insn
);
1056 /* Build the auxilliary graph R(B).
1058 The nodes of the graph are the members of the register partition
1059 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1060 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1062 nodes
= (rtx
*) alloca (n_nodes
* sizeof(rtx
));
1063 pred
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1064 succ
= sbitmap_vector_alloc (n_nodes
, n_nodes
);
1065 sbitmap_vector_zero (pred
, n_nodes
);
1066 sbitmap_vector_zero (succ
, n_nodes
);
1068 insn
= e
->dest
->head
;
1069 if (GET_CODE (insn
) == CODE_LABEL
)
1070 insn
= next_nonnote_insn (insn
);
1073 for (; PHI_NODE_P (insn
); insn
= next_nonnote_insn (insn
))
1075 rtx
* preg
= phi_alternative (PATTERN (insn
), e
->src
->index
);
1076 rtx tgt
= SET_DEST (PATTERN (insn
));
1079 /* There may be no phi alternative corresponding to this edge.
1080 This indicates that the phi variable is undefined along this
1086 if (GET_CODE (reg
) != REG
|| GET_CODE (tgt
) != REG
)
1089 /* If the two registers are already in the same partition,
1090 nothing will need to be done. */
1091 if (partition_find (reg_partition
, REGNO (reg
))
1092 != partition_find (reg_partition
, REGNO (tgt
)))
1096 ireg
= ephi_add_node (reg
, nodes
, &n_nodes
);
1097 itgt
= ephi_add_node (tgt
, nodes
, &n_nodes
);
1099 SET_BIT (pred
[ireg
], itgt
);
1100 SET_BIT (succ
[itgt
], ireg
);
1107 /* Begin a topological sort of the graph. */
1109 visited
= sbitmap_alloc (n_nodes
);
1110 sbitmap_zero (visited
);
1112 tstack
= stack
= (int *) alloca (n_nodes
* sizeof (int));
1114 for (i
= 0; i
< n_nodes
; ++i
)
1115 if (! TEST_BIT (visited
, i
))
1116 tstack
= ephi_forward (i
, visited
, succ
, tstack
);
1118 sbitmap_zero (visited
);
1120 /* As we find a solution to the tsort, collect the implementation
1121 insns in a sequence. */
1124 while (tstack
!= stack
)
1127 if (! TEST_BIT (visited
, i
))
1128 ephi_create (i
, visited
, pred
, succ
, nodes
);
1131 insn
= gen_sequence ();
1133 insert_insn_on_edge (insn
, e
);
1135 fprintf (rtl_dump_file
, "Emitting copy on edge (%d,%d)\n",
1136 e
->src
->index
, e
->dest
->index
);
1138 sbitmap_free (visited
);
1140 sbitmap_vector_free (pred
);
1141 sbitmap_vector_free (succ
);
1145 /* For basic block B, consider all phi insns which provide an
1146 alternative corresponding to an incoming abnormal critical edge.
1147 Place the phi alternative corresponding to that abnormal critical
1148 edge in the same register class as the destination of the set.
1150 From Morgan, p. 178:
1152 For each abnormal critical edge (C, B),
1153 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1154 and C is the ith predecessor of B,
1155 then T0 and Ti must be equivalent.
1157 Return non-zero iff any such cases were found for which the two
1158 regs were not already in the same class. */
1161 make_regs_equivalent_over_bad_edges (bb
, reg_partition
)
1163 partition reg_partition
;
1166 basic_block b
= BASIC_BLOCK (bb
);
1169 /* Advance to the first phi node. */
1170 if (GET_CODE (phi
) == CODE_LABEL
)
1171 phi
= next_nonnote_insn (phi
);
1173 /* Scan all the phi nodes. */
1176 phi
= next_nonnote_insn (phi
))
1180 rtx set
= PATTERN (phi
);
1181 rtx tgt
= SET_DEST (set
);
1183 /* The set target is expected to be a pseudo. */
1184 if (GET_CODE (tgt
) != REG
1185 || REGNO (tgt
) < FIRST_PSEUDO_REGISTER
)
1187 tgt_regno
= REGNO (tgt
);
1189 /* Scan incoming abnormal critical edges. */
1190 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1191 if (e
->flags
& (EDGE_ABNORMAL
| EDGE_CRITICAL
))
1193 rtx
*alt
= phi_alternative (set
, e
->src
->index
);
1196 /* If there is no alternative corresponding to this edge,
1197 the value is undefined along the edge, so just go on. */
1201 /* The phi alternative is expected to be a pseudo. */
1202 if (GET_CODE (*alt
) != REG
1203 || REGNO (*alt
) < FIRST_PSEUDO_REGISTER
)
1205 alt_regno
= REGNO (*alt
);
1207 /* If the set destination and the phi alternative aren't
1208 already in the same class... */
1209 if (partition_find (reg_partition
, tgt_regno
)
1210 != partition_find (reg_partition
, alt_regno
))
1212 /* ... make them such. */
1213 partition_union (reg_partition
,
1214 tgt_regno
, alt_regno
);
1224 /* Consider phi insns in basic block BB pairwise. If the set target
1225 of both isns are equivalent pseudos, make the corresponding phi
1226 alternatives in each phi corresponding equivalent.
1228 Return nonzero if any new register classes were unioned. */
1231 make_equivalent_phi_alternatives_equivalent (bb
, reg_partition
)
1233 partition reg_partition
;
1236 rtx phi
= BLOCK_HEAD (bb
);
1237 basic_block b
= BASIC_BLOCK (bb
);
1239 /* Advance to the first phi node. */
1240 if (GET_CODE (phi
) == CODE_LABEL
)
1241 phi
= next_nonnote_insn (phi
);
1243 /* Scan all the phi nodes. */
1246 phi
= next_nonnote_insn (phi
))
1248 rtx set
= PATTERN (phi
);
1249 /* The regno of the destination of the set. */
1250 int tgt_regno
= REGNO (SET_DEST (PATTERN (phi
)));
1252 rtx phi2
= next_nonnote_insn (phi
);
1254 /* Scan all phi nodes following this one. */
1257 phi2
= next_nonnote_insn (phi2
))
1259 rtx set2
= PATTERN (phi2
);
1260 /* The regno of the destination of the set. */
1261 int tgt2_regno
= REGNO (SET_DEST (set2
));
1263 /* Are the set destinations equivalent regs? */
1264 if (partition_find (reg_partition
, tgt_regno
) ==
1265 partition_find (reg_partition
, tgt2_regno
))
1268 /* Scan over edges. */
1269 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1271 int pred_block
= e
->src
->index
;
1272 /* Identify the phi altnernatives from both phi
1273 nodes corresponding to this edge. */
1274 rtx
*alt
= phi_alternative (set
, pred_block
);
1275 rtx
*alt2
= phi_alternative (set2
, pred_block
);
1277 /* If one of the phi nodes doesn't have a
1278 corresponding alternative, just skip it. */
1279 if (alt
== 0 || alt2
== 0)
1282 /* Both alternatives should be pseudos. */
1283 if (GET_CODE (*alt
) != REG
1284 || REGNO (*alt
) < FIRST_PSEUDO_REGISTER
)
1286 if (GET_CODE (*alt2
) != REG
1287 || REGNO (*alt2
) < FIRST_PSEUDO_REGISTER
)
1290 /* If the altneratives aren't already in the same
1292 if (partition_find (reg_partition
, REGNO (*alt
))
1293 != partition_find (reg_partition
, REGNO (*alt2
)))
1295 /* ... make them so. */
1296 partition_union (reg_partition
,
1297 REGNO (*alt
), REGNO (*alt2
));
1309 /* Compute a conservative partition of outstanding pseudo registers.
1310 See Morgan 7.3.1. */
1313 compute_conservative_reg_partition ()
1318 /* We don't actually work with hard registers, but it's easier to
1319 carry them around anyway rather than constantly doing register
1320 number arithmetic. */
1322 partition_new (ssa_definition
->num_elements
+ FIRST_PSEUDO_REGISTER
);
1324 /* The first priority is to make sure registers that might have to
1325 be copied on abnormal critical edges are placed in the same
1326 partition. This saves us from having to split abnormal critical
1328 for (bb
= n_basic_blocks
; --bb
>= 0; )
1329 changed
+= make_regs_equivalent_over_bad_edges (bb
, p
);
1331 /* Now we have to insure that corresponding arguments of phi nodes
1332 assigning to corresponding regs are equivalent. Iterate until
1337 for (bb
= n_basic_blocks
; --bb
>= 0; )
1338 changed
+= make_equivalent_phi_alternatives_equivalent (bb
, p
);
1345 /* Rename regs in insn PTR that are equivalent. DATA is the register
1346 partition which specifies equivalences. */
1349 rename_equivalent_regs_in_insn (ptr
, data
)
1354 partition reg_partition
= (partition
) data
;
1359 switch (GET_CODE (x
))
1363 rtx
*destp
= &SET_DEST (x
);
1364 rtx dest
= SET_DEST (x
);
1366 /* Subregs at word 0 are interesting. Subregs at word != 0 are
1367 presumed to be part of a contiguous multi-word set sequence. */
1368 while (GET_CODE (dest
) == SUBREG
1369 && SUBREG_WORD (dest
) == 0)
1371 destp
= &SUBREG_REG (dest
);
1372 dest
= SUBREG_REG (dest
);
1375 if (GET_CODE (dest
) == REG
1376 && REGNO (dest
) >= FIRST_PSEUDO_REGISTER
)
1378 /* Got a pseudo; replace it. */
1379 int regno
= REGNO (dest
);
1380 int new_regno
= partition_find (reg_partition
, regno
);
1381 if (regno
!= new_regno
)
1382 *destp
= regno_reg_rtx
[new_regno
];
1384 for_each_rtx (&SET_SRC (x
),
1385 rename_equivalent_regs_in_insn
,
1390 /* Otherwise, this was not an interesting destination. Continue
1391 on, marking uses as normal. */
1396 if (REGNO (x
) >= FIRST_PSEUDO_REGISTER
)
1398 int regno
= REGNO (x
);
1399 int new_regno
= partition_find (reg_partition
, regno
);
1400 if (regno
!= new_regno
)
1402 rtx new_reg
= regno_reg_rtx
[new_regno
];
1403 if (GET_MODE (x
) != GET_MODE (new_reg
))
1411 /* No need to rename the phi nodes. We'll check equivalence
1412 when inserting copies. */
1416 /* Anything else, continue traversing. */
1422 /* Rename regs that are equivalent in REG_PARTITION. */
1425 rename_equivalent_regs (reg_partition
)
1426 partition reg_partition
;
1430 for (bb
= n_basic_blocks
; --bb
>= 0; )
1432 basic_block b
= BASIC_BLOCK (bb
);
1440 if (GET_RTX_CLASS (GET_CODE (insn
)) == 'i')
1442 for_each_rtx (&PATTERN (insn
),
1443 rename_equivalent_regs_in_insn
,
1445 for_each_rtx (®_NOTES (insn
),
1446 rename_equivalent_regs_in_insn
,
1450 next
= NEXT_INSN (insn
);
1452 while (insn
!= last
);
1457 /* The main entry point for moving from SSA. */
1463 partition reg_partition
;
1465 reg_partition
= compute_conservative_reg_partition ();
1466 rename_equivalent_regs (reg_partition
);
1468 /* Eliminate the PHI nodes. */
1469 for (bb
= n_basic_blocks
; --bb
>= 0; )
1471 basic_block b
= BASIC_BLOCK (bb
);
1474 for (e
= b
->pred
; e
; e
= e
->pred_next
)
1475 if (e
->src
!= ENTRY_BLOCK_PTR
)
1476 eliminate_phi (e
, reg_partition
);
1479 partition_delete (reg_partition
);
1481 /* Actually delete the PHI nodes. */
1482 for (bb
= n_basic_blocks
; --bb
>= 0; )
1484 rtx insn
= BLOCK_HEAD (bb
);
1485 int start
= (GET_CODE (insn
) != CODE_LABEL
);
1488 insn
= next_nonnote_insn (insn
);
1489 while (PHI_NODE_P (insn
))
1491 insn
= delete_insn (insn
);
1492 if (GET_CODE (insn
) == NOTE
)
1493 insn
= next_nonnote_insn (insn
);
1496 BLOCK_HEAD (bb
) = insn
;
1499 /* Commit all the copy nodes needed to convert out of SSA form. */
1500 commit_edge_insertions ();
1502 count_or_remove_death_notes (NULL
, 1);