]>
Commit | Line | Data |
---|---|---|
d9d4fb43 AS |
1 | /* Static Single Assignment conversion routines for the GNU compiler. |
2 | Copyright (C) 2000 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GNU CC. | |
5 | ||
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) | |
9 | any later version. | |
10 | ||
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. | |
15 | ||
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. */ | |
20 | ||
21 | /* References: | |
22 | ||
23 | Building an Optimizing Compiler | |
24 | Robert Morgan | |
25 | Butterworth-Heinemann, 1998 | |
26 | ||
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 | |
31 | */ | |
32 | ||
33 | #include "config.h" | |
34 | #include "system.h" | |
35 | ||
36 | #include "rtl.h" | |
37 | #include "regs.h" | |
38 | #include "hard-reg-set.h" | |
39 | #include "flags.h" | |
40 | #include "function.h" | |
41 | #include "real.h" | |
42 | #include "insn-config.h" | |
43 | #include "recog.h" | |
44 | #include "basic-block.h" | |
45 | #include "output.h" | |
46 | #include "partition.h" | |
47 | ||
48 | ||
49 | /* TODO: | |
50 | ||
51 | ??? What to do about strict_low_part. Probably I'll have to split | |
52 | them out of their current instructions first thing. | |
53 | ||
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 | |
58 | expansion. | |
59 | */ | |
60 | ||
61 | ||
62 | /* Element I is the single instruction that sets register I+PSEUDO. */ | |
63 | varray_type ssa_definition; | |
64 | ||
65 | /* Element I is an INSN_LIST of instructions that use register I+PSEUDO. */ | |
66 | varray_type ssa_uses; | |
67 | ||
68 | /* Element I-PSEUDO is the normal register that originated the ssa | |
69 | register in question. */ | |
70 | varray_type ssa_rename_from; | |
71 | ||
72 | /* The running target ssa register for a given normal register. */ | |
73 | static rtx *ssa_rename_to; | |
74 | ||
75 | /* The number of registers that were live on entry to the SSA routines. */ | |
76 | static int ssa_max_reg_num; | |
77 | ||
78 | /* Local function prototypes. */ | |
79 | ||
80 | static inline rtx * phi_alternative | |
81 | PARAMS ((rtx, int)); | |
82 | ||
83 | static int remove_phi_alternative | |
84 | PARAMS ((rtx, int)); | |
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)); | |
107 | ||
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)); | |
118 | ||
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 | |
124 | PARAMS (()); | |
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)); | |
129 | ||
130 | ||
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) | |
136 | ||
137 | /* Given the SET of a PHI node, return the address of the alternative | |
138 | for predecessor block C. */ | |
139 | ||
140 | static inline rtx * | |
141 | phi_alternative (set, c) | |
142 | rtx set; | |
143 | int c; | |
144 | { | |
145 | rtvec phi_vec = XVEC (SET_SRC (set), 0); | |
146 | int v; | |
147 | ||
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); | |
151 | ||
152 | return NULL; | |
153 | } | |
154 | ||
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 | |
157 | found for C. */ | |
158 | ||
159 | static int | |
160 | remove_phi_alternative (set, c) | |
161 | rtx set; | |
162 | int c; | |
163 | { | |
164 | rtvec phi_vec = XVEC (SET_SRC (set), 0); | |
165 | int num_elem = GET_NUM_ELEM (phi_vec); | |
166 | int v; | |
167 | ||
168 | for (v = num_elem - 2; v >= 0; v -= 2) | |
169 | if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c) | |
170 | { | |
171 | if (v < num_elem - 2) | |
172 | { | |
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); | |
175 | } | |
176 | PUT_NUM_ELEM (phi_vec, num_elem - 2); | |
177 | return 1; | |
178 | } | |
179 | ||
180 | return 0; | |
181 | } | |
182 | ||
183 | /* Computing the Immediate Dominators: | |
184 | ||
185 | Throughout, we don't actually want the full dominators set as | |
186 | calculated by flow, but rather the immediate dominators. | |
187 | */ | |
188 | ||
189 | static void | |
190 | simplify_to_immediate_dominators (idom, dominators) | |
191 | int *idom; | |
192 | sbitmap *dominators; | |
193 | { | |
194 | sbitmap *tmp; | |
195 | int b; | |
196 | ||
197 | tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); | |
198 | ||
199 | /* Begin with tmp(n) = dom(n) - { n }. */ | |
200 | for (b = n_basic_blocks; --b >= 0; ) | |
201 | { | |
202 | sbitmap_copy (tmp[b], dominators[b]); | |
203 | RESET_BIT (tmp[b], b); | |
204 | } | |
205 | ||
206 | /* Subtract out all of our dominator's dominators. */ | |
207 | for (b = n_basic_blocks; --b >= 0; ) | |
208 | { | |
209 | sbitmap tmp_b = tmp[b]; | |
210 | int s; | |
211 | ||
212 | for (s = n_basic_blocks; --s >= 0; ) | |
213 | if (TEST_BIT (tmp_b, s)) | |
214 | sbitmap_difference (tmp_b, tmp_b, tmp[s]); | |
215 | } | |
216 | ||
217 | /* Find the one bit set in the bitmap and put it in the output array. */ | |
218 | for (b = n_basic_blocks; --b >= 0; ) | |
219 | { | |
220 | int t; | |
221 | EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; }); | |
222 | } | |
223 | ||
224 | sbitmap_vector_free (tmp); | |
225 | } | |
226 | ||
227 | ||
228 | /* For all registers, find all blocks in which they are set. | |
229 | ||
230 | This is the transform of what would be local kill information that | |
231 | we ought to be getting from flow. */ | |
232 | ||
233 | static sbitmap *fe_evals; | |
234 | static int fe_current_bb; | |
235 | ||
236 | static void | |
237 | find_evaluations_1 (dest, set, data) | |
238 | rtx dest; | |
239 | rtx set ATTRIBUTE_UNUSED; | |
240 | void *data ATTRIBUTE_UNUSED; | |
241 | { | |
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); | |
245 | } | |
246 | ||
247 | static void | |
248 | find_evaluations (evals, nregs) | |
249 | sbitmap *evals; | |
250 | int nregs; | |
251 | { | |
252 | int bb; | |
253 | ||
254 | sbitmap_vector_zero (evals, nregs); | |
255 | fe_evals = evals; | |
256 | ||
257 | for (bb = n_basic_blocks; --bb >= 0; ) | |
258 | { | |
259 | rtx p, last; | |
260 | ||
261 | fe_current_bb = bb; | |
262 | p = BLOCK_HEAD (bb); | |
263 | last = BLOCK_END (bb); | |
264 | while (1) | |
265 | { | |
266 | if (GET_RTX_CLASS (GET_CODE (p)) == 'i') | |
267 | note_stores (PATTERN (p), find_evaluations_1, NULL); | |
268 | ||
269 | if (p == last) | |
270 | break; | |
271 | p = NEXT_INSN (p); | |
272 | } | |
273 | } | |
274 | } | |
275 | ||
276 | ||
277 | /* Computing the Dominance Frontier: | |
278 | ||
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, | |
282 | there are two cases: | |
283 | ||
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 | |
287 | of B. | |
288 | ||
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. | |
292 | */ | |
293 | ||
294 | static void | |
295 | compute_dominance_frontiers_1 (frontiers, idom, bb, done) | |
296 | sbitmap *frontiers; | |
297 | int *idom; | |
298 | int bb; | |
299 | sbitmap done; | |
300 | { | |
301 | basic_block b = BASIC_BLOCK (bb); | |
302 | edge e; | |
303 | int c; | |
304 | ||
305 | SET_BIT (done, bb); | |
306 | sbitmap_zero (frontiers[bb]); | |
307 | ||
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); | |
314 | ||
315 | /* Find blocks conforming to rule (1) above. */ | |
316 | for (e = b->succ; e; e = e->succ_next) | |
317 | { | |
318 | if (e->dest == EXIT_BLOCK_PTR) | |
319 | continue; | |
320 | if (idom[e->dest->index] != bb) | |
321 | SET_BIT (frontiers[bb], e->dest->index); | |
322 | } | |
323 | ||
324 | /* Find blocks conforming to rule (2). */ | |
325 | for (c = 0; c < n_basic_blocks; ++c) | |
326 | if (idom[c] == bb) | |
327 | { | |
328 | int x; | |
329 | EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x, | |
330 | { | |
331 | if (idom[x] != bb) | |
332 | SET_BIT (frontiers[bb], x); | |
333 | }); | |
334 | } | |
335 | } | |
336 | ||
337 | static void | |
338 | compute_dominance_frontiers (frontiers, idom) | |
339 | sbitmap *frontiers; | |
340 | int *idom; | |
341 | { | |
342 | sbitmap done = sbitmap_alloc (n_basic_blocks); | |
343 | sbitmap_zero (done); | |
344 | ||
345 | compute_dominance_frontiers_1 (frontiers, idom, 0, done); | |
346 | ||
347 | sbitmap_free (done); | |
348 | } | |
349 | ||
350 | ||
351 | /* Computing the Iterated Dominance Frontier: | |
352 | ||
353 | This is the set of merge points for a given register. | |
354 | ||
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. | |
357 | */ | |
358 | ||
359 | static void | |
360 | compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs) | |
361 | sbitmap *idfs; | |
362 | sbitmap *frontiers; | |
363 | sbitmap *evals; | |
364 | int nregs; | |
365 | { | |
366 | sbitmap worklist; | |
367 | int reg, passes = 0; | |
368 | ||
369 | worklist = sbitmap_alloc (n_basic_blocks); | |
370 | ||
371 | for (reg = 0; reg < nregs; ++reg) | |
372 | { | |
373 | sbitmap idf = idfs[reg]; | |
374 | int b, changed; | |
375 | ||
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]); | |
380 | ||
381 | /* Morgan's algorithm is incorrect here. Blocks that evaluate | |
382 | REG aren't necessarily in REG's IDF. Start with an empty IDF. */ | |
383 | sbitmap_zero (idf); | |
384 | ||
385 | /* Iterate until the worklist is empty. */ | |
386 | do | |
387 | { | |
388 | changed = 0; | |
389 | passes++; | |
390 | EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b, | |
391 | { | |
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 | |
396 | to the worklist. */ | |
397 | sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf); | |
398 | sbitmap_a_or_b (idf, idf, frontiers[b]); | |
399 | changed = 1; | |
400 | }); | |
401 | } | |
402 | while (changed); | |
403 | } | |
404 | ||
405 | sbitmap_free (worklist); | |
406 | ||
407 | if (rtl_dump_file) | |
408 | { | |
409 | fprintf(rtl_dump_file, | |
410 | "Iterated dominance frontier: %d passes on %d regs.\n", | |
411 | passes, nregs); | |
412 | } | |
413 | } | |
414 | ||
415 | ||
416 | /* Insert the phi nodes. */ | |
417 | ||
418 | static void | |
419 | insert_phi_node (regno, bb) | |
420 | int regno, bb; | |
421 | { | |
422 | basic_block b = BASIC_BLOCK (bb); | |
423 | edge e; | |
424 | int npred, i; | |
425 | rtvec vec; | |
426 | rtx phi, reg; | |
427 | ||
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) | |
431 | npred++; | |
432 | ||
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. */ | |
435 | if (npred == 0) | |
436 | return; | |
437 | ||
438 | /* This is the register to which the phi function will be assinged. */ | |
439 | reg = regno_reg_rtx[regno + FIRST_PSEUDO_REGISTER]; | |
440 | ||
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) | |
446 | { | |
447 | RTVEC_ELT (vec, i + 0) = pc_rtx; | |
448 | RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index); | |
449 | } | |
450 | ||
451 | phi = gen_rtx_PHI (VOIDmode, vec); | |
452 | phi = gen_rtx_SET (VOIDmode, reg, phi); | |
453 | ||
454 | if (GET_CODE (b->head) == CODE_LABEL) | |
455 | emit_insn_after (phi, b->head); | |
456 | else | |
457 | b->head = emit_insn_before (phi, b->head); | |
458 | } | |
459 | ||
460 | ||
461 | static void | |
462 | insert_phi_nodes (idfs, evals, nregs) | |
463 | sbitmap *idfs; | |
464 | sbitmap *evals ATTRIBUTE_UNUSED; | |
465 | int nregs; | |
466 | { | |
467 | int reg; | |
468 | ||
469 | for (reg = 0; reg < nregs; ++reg) | |
470 | { | |
471 | int b; | |
472 | EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b, | |
473 | { | |
474 | if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, | |
475 | reg + FIRST_PSEUDO_REGISTER)) | |
476 | insert_phi_node (reg, b); | |
477 | }); | |
478 | } | |
479 | } | |
480 | ||
481 | /* Rename the registers to conform to SSA. | |
482 | ||
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. */ | |
486 | ||
487 | ||
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 | |
491 | { | |
492 | struct rename_set_data *next; | |
493 | rtx *reg_loc; | |
494 | rtx set_dest; | |
495 | rtx new_reg; | |
496 | rtx prev_reg; | |
497 | }; | |
498 | ||
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)); | |
502 | ||
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 | |
511 | ||
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. */ | |
514 | ||
515 | static int | |
516 | rename_insn_1 (ptr, data) | |
517 | rtx *ptr; | |
518 | void *data; | |
519 | { | |
520 | rtx x = *ptr; | |
521 | struct rename_set_data **set_datap = data; | |
522 | ||
523 | if (x == NULL_RTX) | |
524 | return 0; | |
525 | ||
526 | switch (GET_CODE (x)) | |
527 | { | |
528 | case SET: | |
529 | { | |
530 | rtx *destp = &SET_DEST (x); | |
531 | rtx dest = SET_DEST (x); | |
532 | ||
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) | |
537 | { | |
538 | destp = &SUBREG_REG (dest); | |
539 | dest = SUBREG_REG (dest); | |
540 | } | |
541 | ||
542 | if (GET_CODE (dest) == REG | |
543 | && REGNO (dest) >= FIRST_PSEUDO_REGISTER) | |
544 | { | |
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. */ | |
548 | ||
549 | struct rename_set_data *r; | |
550 | r = (struct rename_set_data *) xmalloc (sizeof(*r)); | |
551 | ||
552 | r->reg_loc = destp; | |
553 | r->set_dest = SET_DEST (x); | |
554 | r->next = *set_datap; | |
555 | *set_datap = r; | |
556 | ||
557 | /* Since we do not wish to (directly) traverse the | |
558 | SET_DEST, recurse through for_each_rtx for the SET_SRC | |
559 | and return. */ | |
560 | for_each_rtx (&SET_SRC (x), rename_insn_1, data); | |
561 | return -1; | |
562 | } | |
563 | ||
564 | /* Otherwise, this was not an interesting destination. Continue | |
565 | on, marking uses as normal. */ | |
566 | return 0; | |
567 | } | |
568 | ||
569 | case REG: | |
570 | if (REGNO (x) >= FIRST_PSEUDO_REGISTER | |
571 | && REGNO (x) < ssa_max_reg_num) | |
572 | { | |
573 | rtx new_reg = ssa_rename_to[REGNO(x) - FIRST_PSEUDO_REGISTER]; | |
574 | ||
575 | if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX) | |
576 | { | |
577 | if (GET_MODE (x) != GET_MODE (new_reg)) | |
578 | abort (); | |
579 | *ptr = new_reg; | |
580 | /* ??? Mark for a new ssa_uses entry. */ | |
581 | } | |
582 | /* Else this is a use before a set. Warn? */ | |
583 | } | |
584 | return -1; | |
585 | ||
586 | case PHI: | |
587 | /* Never muck with the phi. We do that elsewhere, special-like. */ | |
588 | return -1; | |
589 | ||
590 | default: | |
591 | /* Anything else, continue traversing. */ | |
592 | return 0; | |
593 | } | |
594 | } | |
595 | ||
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. */ | |
599 | ||
600 | static void | |
601 | new_registers_for_updates (set_data, old_set_data, insn) | |
602 | struct rename_set_data *set_data, *old_set_data; | |
603 | rtx insn; | |
604 | { | |
605 | while (set_data != old_set_data) | |
606 | { | |
607 | int regno, new_regno; | |
608 | rtx old_reg, new_reg, prev_reg; | |
609 | ||
610 | old_reg = *set_data->reg_loc; | |
611 | regno = REGNO (*set_data->reg_loc); | |
612 | ||
613 | /* For the first set we come across, reuse the original regno. */ | |
614 | if (ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] == NULL_RTX) | |
615 | { | |
616 | new_reg = old_reg; | |
617 | prev_reg = RENAME_NO_RTX; | |
618 | } | |
619 | else | |
620 | { | |
621 | prev_reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER]; | |
622 | new_reg = gen_reg_rtx (GET_MODE (old_reg)); | |
623 | } | |
624 | ||
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; | |
629 | ||
630 | if (new_regno >= (int) ssa_definition->num_elements) | |
631 | { | |
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); | |
636 | } | |
637 | ||
638 | VARRAY_RTX (ssa_definition, new_regno) = insn; | |
639 | VARRAY_RTX (ssa_rename_from, new_regno) = old_reg; | |
640 | ||
641 | set_data = set_data->next; | |
642 | } | |
643 | } | |
644 | ||
645 | static void | |
646 | rename_block (bb, idom) | |
647 | int bb; | |
648 | int *idom; | |
649 | { | |
650 | basic_block b = BASIC_BLOCK (bb); | |
651 | edge e; | |
652 | rtx insn, next, last; | |
653 | struct rename_set_data *set_data = NULL; | |
654 | int c; | |
655 | ||
656 | /* Step One: Walk the basic block, adding new names for sets and | |
657 | replacing uses. */ | |
658 | ||
659 | next = b->head; | |
660 | last = b->end; | |
661 | do | |
662 | { | |
663 | insn = next; | |
664 | if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') | |
665 | { | |
666 | struct rename_set_data *old_set_data = set_data; | |
667 | ||
668 | for_each_rtx (&PATTERN (insn), rename_insn_1, &set_data); | |
669 | for_each_rtx (®_NOTES (insn), rename_insn_1, &set_data); | |
670 | ||
671 | new_registers_for_updates (set_data, old_set_data, insn); | |
672 | } | |
673 | ||
674 | next = NEXT_INSN (insn); | |
675 | } | |
676 | while (insn != last); | |
677 | ||
678 | /* Step Two: Update the phi nodes of this block's successors. */ | |
679 | ||
680 | for (e = b->succ; e; e = e->succ_next) | |
681 | { | |
682 | if (e->dest == EXIT_BLOCK_PTR) | |
683 | continue; | |
684 | ||
685 | insn = e->dest->head; | |
686 | if (GET_CODE (insn) == CODE_LABEL) | |
687 | insn = NEXT_INSN (insn); | |
688 | ||
689 | while (PHI_NODE_P (insn)) | |
690 | { | |
691 | rtx phi = PATTERN (insn); | |
692 | int regno; | |
693 | rtx reg; | |
694 | ||
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]; | |
705 | ||
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) | |
710 | { | |
711 | if (! remove_phi_alternative (phi, bb)) | |
712 | abort (); | |
713 | } | |
714 | else | |
715 | { | |
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)) | |
722 | abort(); | |
723 | ||
724 | *phi_alternative (phi, bb) = reg; | |
725 | /* ??? Mark for a new ssa_uses entry. */ | |
726 | } | |
727 | ||
728 | insn = NEXT_INSN (insn); | |
729 | } | |
730 | } | |
731 | ||
732 | /* Step Three: Do the same to the children of this block in | |
733 | dominator order. */ | |
734 | ||
735 | for (c = 0; c < n_basic_blocks; ++c) | |
736 | if (idom[c] == bb) | |
737 | rename_block (c, idom); | |
738 | ||
739 | /* Step Four: Update the sets to refer to their new register. */ | |
740 | ||
741 | while (set_data) | |
742 | { | |
743 | struct rename_set_data *next; | |
744 | rtx old_reg; | |
745 | ||
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; | |
750 | ||
751 | next = set_data->next; | |
752 | free (set_data); | |
753 | set_data = next; | |
754 | } | |
755 | } | |
756 | ||
757 | static void | |
758 | rename_registers (nregs, idom) | |
759 | int nregs; | |
760 | int *idom; | |
761 | { | |
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"); | |
765 | ||
766 | ssa_rename_to = (rtx *) alloca (nregs * sizeof(rtx)); | |
665f2503 | 767 | bzero ((char *) ssa_rename_to, nregs * sizeof(rtx)); |
d9d4fb43 AS |
768 | |
769 | rename_block (0, idom); | |
770 | ||
771 | /* ??? Update basic_block_live_at_start, and other flow info | |
772 | as needed. */ | |
773 | ||
774 | ssa_rename_to = NULL; | |
775 | } | |
776 | ||
777 | ||
778 | /* The main entry point for moving to SSA. */ | |
779 | ||
780 | void | |
781 | convert_to_ssa() | |
782 | { | |
783 | /* Element I is the set of blocks that set register I. */ | |
784 | sbitmap *evals; | |
785 | ||
786 | /* Dominator bitmaps. */ | |
787 | sbitmap *dominators; | |
788 | sbitmap *dfs; | |
789 | sbitmap *idfs; | |
790 | ||
791 | /* Element I is the immediate dominator of block I. */ | |
792 | int *idom; | |
793 | ||
794 | int nregs; | |
795 | ||
796 | find_basic_blocks (get_insns (), max_reg_num(), NULL); | |
797 | /* The dominator algorithms assume all blocks are reachable, clean | |
798 | up first. */ | |
799 | cleanup_cfg (get_insns ()); | |
800 | life_analysis (get_insns (), max_reg_num (), NULL, 1); | |
801 | ||
802 | /* Compute dominators. */ | |
803 | dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); | |
804 | compute_flow_dominators (dominators, NULL); | |
805 | ||
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); | |
809 | ||
810 | sbitmap_vector_free (dominators); | |
811 | ||
812 | if (rtl_dump_file) | |
813 | { | |
814 | int i; | |
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); | |
819 | } | |
820 | ||
821 | /* Compute dominance frontiers. */ | |
822 | ||
823 | dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); | |
824 | compute_dominance_frontiers (dfs, idom); | |
825 | ||
826 | if (rtl_dump_file) | |
827 | { | |
828 | dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:", | |
829 | "; Basic Block", dfs, n_basic_blocks); | |
830 | fflush (rtl_dump_file); | |
831 | } | |
832 | ||
833 | /* Compute register evaluations. */ | |
834 | ||
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); | |
839 | ||
840 | /* Compute the iterated dominance frontier for each register. */ | |
841 | ||
842 | idfs = sbitmap_vector_alloc (nregs, n_basic_blocks); | |
843 | compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs); | |
844 | ||
845 | if (rtl_dump_file) | |
846 | { | |
847 | dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:", | |
848 | "; Register-FIRST_PSEUDO_REGISTER", idfs, nregs); | |
849 | fflush (rtl_dump_file); | |
850 | } | |
851 | ||
852 | /* Insert the phi nodes. */ | |
853 | ||
854 | insert_phi_nodes (idfs, evals, nregs); | |
855 | ||
856 | /* Rename the registers to satisfy SSA. */ | |
857 | ||
858 | rename_registers (nregs, idom); | |
859 | ||
860 | /* All done! Clean up and go home. */ | |
861 | ||
862 | sbitmap_vector_free (dfs); | |
863 | sbitmap_vector_free (evals); | |
864 | sbitmap_vector_free (idfs); | |
865 | } | |
866 | ||
867 | ||
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. | |
873 | ||
874 | ??? Morgan's algorithm, perhaps with some care, may allow copy | |
875 | propagation to happen concurrently with the conversion from SSA. | |
876 | ||
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. | |
882 | ||
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. | |
890 | ||
891 | More study is required. */ | |
892 | ||
893 | ||
894 | /* | |
895 | * Eliminate the PHI across the edge from C to B. | |
896 | */ | |
897 | ||
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. */ | |
901 | ||
902 | static inline int | |
903 | ephi_add_node (reg, nodes, n_nodes) | |
904 | rtx reg, *nodes; | |
905 | int *n_nodes; | |
906 | { | |
907 | int i; | |
908 | for (i = *n_nodes - 1; i >= 0; --i) | |
909 | if (REGNO (reg) == REGNO (nodes[i])) | |
910 | return i; | |
911 | ||
912 | nodes[i = (*n_nodes)++] = reg; | |
913 | return i; | |
914 | } | |
915 | ||
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. */ | |
920 | ||
921 | static int * | |
922 | ephi_forward (t, visited, succ, tstack) | |
923 | int t; | |
924 | sbitmap visited; | |
925 | sbitmap *succ; | |
926 | int *tstack; | |
927 | { | |
928 | int s; | |
929 | ||
930 | SET_BIT (visited, t); | |
931 | ||
932 | EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s, | |
933 | { | |
934 | if (! TEST_BIT (visited, s)) | |
935 | tstack = ephi_forward (s, visited, succ, tstack); | |
936 | }); | |
937 | ||
938 | *tstack++ = t; | |
939 | return tstack; | |
940 | } | |
941 | ||
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. */ | |
944 | ||
945 | static void | |
946 | ephi_backward (t, visited, pred, nodes) | |
947 | int t; | |
948 | sbitmap visited, *pred; | |
949 | rtx *nodes; | |
950 | { | |
951 | int p; | |
952 | ||
953 | SET_BIT (visited, t); | |
954 | ||
955 | EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, | |
956 | { | |
957 | if (! TEST_BIT (visited, p)) | |
958 | { | |
959 | ephi_backward (p, visited, pred, nodes); | |
960 | emit_move_insn (nodes[p], nodes[t]); | |
961 | } | |
962 | }); | |
963 | } | |
964 | ||
965 | /* Part two of the topological sort. Create the copy for a register | |
966 | and any cycle of which it is a member. */ | |
967 | ||
968 | static void | |
969 | ephi_create (t, visited, pred, succ, nodes) | |
970 | int t; | |
971 | sbitmap visited, *pred, *succ; | |
972 | rtx *nodes; | |
973 | { | |
974 | rtx reg_u = NULL_RTX; | |
975 | int unvisited_predecessors = 0; | |
976 | int p; | |
977 | ||
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. */ | |
982 | ||
983 | EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, | |
984 | { | |
985 | if (! TEST_BIT (visited, p)) | |
986 | unvisited_predecessors = 1; | |
987 | else if (!reg_u) | |
988 | reg_u = nodes[p]; | |
989 | }); | |
990 | ||
991 | if (unvisited_predecessors) | |
992 | { | |
993 | /* We found a cycle. Copy out one element of the ring (if necessary), | |
994 | then traverse the ring copying as we go. */ | |
995 | ||
996 | if (!reg_u) | |
997 | { | |
998 | reg_u = gen_reg_rtx (GET_MODE (nodes[t])); | |
999 | emit_move_insn (reg_u, nodes[t]); | |
1000 | } | |
1001 | ||
1002 | EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, | |
1003 | { | |
1004 | if (! TEST_BIT (visited, p)) | |
1005 | { | |
1006 | ephi_backward (p, visited, pred, nodes); | |
1007 | emit_move_insn (nodes[p], reg_u); | |
1008 | } | |
1009 | }); | |
1010 | } | |
1011 | else | |
1012 | { | |
1013 | /* No cycle. Just copy the value from a successor. */ | |
1014 | ||
1015 | int s; | |
1016 | EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s, | |
1017 | { | |
1018 | SET_BIT (visited, t); | |
1019 | emit_move_insn (nodes[t], nodes[s]); | |
1020 | return; | |
1021 | }); | |
1022 | } | |
1023 | } | |
1024 | ||
1025 | /* Convert the edge to normal form. */ | |
1026 | ||
1027 | static void | |
1028 | eliminate_phi (e, reg_partition) | |
1029 | edge e; | |
1030 | partition reg_partition; | |
1031 | { | |
1032 | int n_nodes; | |
1033 | sbitmap *pred, *succ; | |
1034 | sbitmap visited; | |
1035 | rtx *nodes; | |
1036 | int *stack, *tstack; | |
1037 | rtx insn; | |
1038 | int i; | |
1039 | ||
1040 | /* Collect an upper bound on the number of registers needing processing. */ | |
1041 | ||
1042 | insn = e->dest->head; | |
1043 | if (GET_CODE (insn) == CODE_LABEL) | |
1044 | insn = next_nonnote_insn (insn); | |
1045 | ||
1046 | n_nodes = 0; | |
1047 | while (PHI_NODE_P (insn)) | |
1048 | { | |
1049 | insn = next_nonnote_insn (insn); | |
1050 | n_nodes += 2; | |
1051 | } | |
1052 | ||
1053 | if (n_nodes == 0) | |
1054 | return; | |
1055 | ||
1056 | /* Build the auxilliary graph R(B). | |
1057 | ||
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. */ | |
1061 | ||
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); | |
1067 | ||
1068 | insn = e->dest->head; | |
1069 | if (GET_CODE (insn) == CODE_LABEL) | |
1070 | insn = next_nonnote_insn (insn); | |
1071 | ||
1072 | n_nodes = 0; | |
1073 | for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn)) | |
1074 | { | |
1075 | rtx* preg = phi_alternative (PATTERN (insn), e->src->index); | |
1076 | rtx tgt = SET_DEST (PATTERN (insn)); | |
1077 | rtx reg; | |
1078 | ||
1079 | /* There may be no phi alternative corresponding to this edge. | |
1080 | This indicates that the phi variable is undefined along this | |
1081 | edge. */ | |
1082 | if (preg == NULL) | |
1083 | continue; | |
1084 | reg = *preg; | |
1085 | ||
1086 | if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG) | |
1087 | abort(); | |
1088 | ||
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))) | |
1093 | { | |
1094 | int ireg, itgt; | |
1095 | ||
1096 | ireg = ephi_add_node (reg, nodes, &n_nodes); | |
1097 | itgt = ephi_add_node (tgt, nodes, &n_nodes); | |
1098 | ||
1099 | SET_BIT (pred[ireg], itgt); | |
1100 | SET_BIT (succ[itgt], ireg); | |
1101 | } | |
1102 | } | |
1103 | ||
1104 | if (n_nodes == 0) | |
1105 | goto out; | |
1106 | ||
1107 | /* Begin a topological sort of the graph. */ | |
1108 | ||
1109 | visited = sbitmap_alloc (n_nodes); | |
1110 | sbitmap_zero (visited); | |
1111 | ||
1112 | tstack = stack = (int *) alloca (n_nodes * sizeof (int)); | |
1113 | ||
1114 | for (i = 0; i < n_nodes; ++i) | |
1115 | if (! TEST_BIT (visited, i)) | |
1116 | tstack = ephi_forward (i, visited, succ, tstack); | |
1117 | ||
1118 | sbitmap_zero (visited); | |
1119 | ||
1120 | /* As we find a solution to the tsort, collect the implementation | |
1121 | insns in a sequence. */ | |
1122 | start_sequence (); | |
1123 | ||
1124 | while (tstack != stack) | |
1125 | { | |
1126 | i = *--tstack; | |
1127 | if (! TEST_BIT (visited, i)) | |
1128 | ephi_create (i, visited, pred, succ, nodes); | |
1129 | } | |
1130 | ||
1131 | insn = gen_sequence (); | |
1132 | end_sequence (); | |
1133 | insert_insn_on_edge (insn, e); | |
1134 | if (rtl_dump_file) | |
1135 | fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n", | |
1136 | e->src->index, e->dest->index); | |
1137 | ||
1138 | sbitmap_free (visited); | |
1139 | out: | |
1140 | sbitmap_vector_free (pred); | |
1141 | sbitmap_vector_free (succ); | |
1142 | } | |
1143 | ||
1144 | ||
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. | |
1149 | ||
1150 | From Morgan, p. 178: | |
1151 | ||
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. | |
1156 | ||
1157 | Return non-zero iff any such cases were found for which the two | |
1158 | regs were not already in the same class. */ | |
1159 | ||
1160 | static int | |
1161 | make_regs_equivalent_over_bad_edges (bb, reg_partition) | |
1162 | int bb; | |
1163 | partition reg_partition; | |
1164 | { | |
1165 | int changed = 0; | |
1166 | basic_block b = BASIC_BLOCK (bb); | |
1167 | rtx phi = b->head; | |
1168 | ||
1169 | /* Advance to the first phi node. */ | |
1170 | if (GET_CODE (phi) == CODE_LABEL) | |
1171 | phi = next_nonnote_insn (phi); | |
1172 | ||
1173 | /* Scan all the phi nodes. */ | |
1174 | for (; | |
1175 | PHI_NODE_P (phi); | |
1176 | phi = next_nonnote_insn (phi)) | |
1177 | { | |
1178 | edge e; | |
1179 | int tgt_regno; | |
1180 | rtx set = PATTERN (phi); | |
1181 | rtx tgt = SET_DEST (set); | |
1182 | ||
1183 | /* The set target is expected to be a pseudo. */ | |
1184 | if (GET_CODE (tgt) != REG | |
1185 | || REGNO (tgt) < FIRST_PSEUDO_REGISTER) | |
1186 | abort (); | |
1187 | tgt_regno = REGNO (tgt); | |
1188 | ||
1189 | /* Scan incoming abnormal critical edges. */ | |
1190 | for (e = b->pred; e; e = e->pred_next) | |
1191 | if (e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL)) | |
1192 | { | |
1193 | rtx *alt = phi_alternative (set, e->src->index); | |
1194 | int alt_regno; | |
1195 | ||
1196 | /* If there is no alternative corresponding to this edge, | |
1197 | the value is undefined along the edge, so just go on. */ | |
1198 | if (alt == 0) | |
1199 | continue; | |
1200 | ||
1201 | /* The phi alternative is expected to be a pseudo. */ | |
1202 | if (GET_CODE (*alt) != REG | |
1203 | || REGNO (*alt) < FIRST_PSEUDO_REGISTER) | |
1204 | abort (); | |
1205 | alt_regno = REGNO (*alt); | |
1206 | ||
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)) | |
1211 | { | |
1212 | /* ... make them such. */ | |
1213 | partition_union (reg_partition, | |
1214 | tgt_regno, alt_regno); | |
1215 | ++changed; | |
1216 | } | |
1217 | } | |
1218 | } | |
1219 | ||
1220 | return changed; | |
1221 | } | |
1222 | ||
1223 | ||
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. | |
1227 | ||
1228 | Return nonzero if any new register classes were unioned. */ | |
1229 | ||
1230 | static int | |
1231 | make_equivalent_phi_alternatives_equivalent (bb, reg_partition) | |
1232 | int bb; | |
1233 | partition reg_partition; | |
1234 | { | |
1235 | int changed = 0; | |
1236 | rtx phi = BLOCK_HEAD (bb); | |
1237 | basic_block b = BASIC_BLOCK (bb); | |
1238 | ||
1239 | /* Advance to the first phi node. */ | |
1240 | if (GET_CODE (phi) == CODE_LABEL) | |
1241 | phi = next_nonnote_insn (phi); | |
1242 | ||
1243 | /* Scan all the phi nodes. */ | |
1244 | for (; | |
1245 | PHI_NODE_P (phi); | |
1246 | phi = next_nonnote_insn (phi)) | |
1247 | { | |
1248 | rtx set = PATTERN (phi); | |
1249 | /* The regno of the destination of the set. */ | |
1250 | int tgt_regno = REGNO (SET_DEST (PATTERN (phi))); | |
1251 | ||
1252 | rtx phi2 = next_nonnote_insn (phi); | |
1253 | ||
1254 | /* Scan all phi nodes following this one. */ | |
1255 | for (; | |
1256 | PHI_NODE_P (phi2); | |
1257 | phi2 = next_nonnote_insn (phi2)) | |
1258 | { | |
1259 | rtx set2 = PATTERN (phi2); | |
1260 | /* The regno of the destination of the set. */ | |
1261 | int tgt2_regno = REGNO (SET_DEST (set2)); | |
1262 | ||
1263 | /* Are the set destinations equivalent regs? */ | |
1264 | if (partition_find (reg_partition, tgt_regno) == | |
1265 | partition_find (reg_partition, tgt2_regno)) | |
1266 | { | |
1267 | edge e; | |
1268 | /* Scan over edges. */ | |
1269 | for (e = b->pred; e; e = e->pred_next) | |
1270 | { | |
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); | |
1276 | ||
1277 | /* If one of the phi nodes doesn't have a | |
1278 | corresponding alternative, just skip it. */ | |
1279 | if (alt == 0 || alt2 == 0) | |
1280 | continue; | |
1281 | ||
1282 | /* Both alternatives should be pseudos. */ | |
1283 | if (GET_CODE (*alt) != REG | |
1284 | || REGNO (*alt) < FIRST_PSEUDO_REGISTER) | |
1285 | abort (); | |
1286 | if (GET_CODE (*alt2) != REG | |
1287 | || REGNO (*alt2) < FIRST_PSEUDO_REGISTER) | |
1288 | abort (); | |
1289 | ||
1290 | /* If the altneratives aren't already in the same | |
1291 | class ... */ | |
1292 | if (partition_find (reg_partition, REGNO (*alt)) | |
1293 | != partition_find (reg_partition, REGNO (*alt2))) | |
1294 | { | |
1295 | /* ... make them so. */ | |
1296 | partition_union (reg_partition, | |
1297 | REGNO (*alt), REGNO (*alt2)); | |
1298 | ++changed; | |
1299 | } | |
1300 | } | |
1301 | } | |
1302 | } | |
1303 | } | |
1304 | ||
1305 | return changed; | |
1306 | } | |
1307 | ||
1308 | ||
1309 | /* Compute a conservative partition of outstanding pseudo registers. | |
1310 | See Morgan 7.3.1. */ | |
1311 | ||
1312 | static partition | |
1313 | compute_conservative_reg_partition () | |
1314 | { | |
1315 | int bb; | |
1316 | int changed = 0; | |
1317 | ||
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. */ | |
1321 | partition p = | |
1322 | partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER); | |
1323 | ||
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 | |
1327 | edges. */ | |
1328 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1329 | changed += make_regs_equivalent_over_bad_edges (bb, p); | |
1330 | ||
1331 | /* Now we have to insure that corresponding arguments of phi nodes | |
1332 | assigning to corresponding regs are equivalent. Iterate until | |
1333 | nothing changes. */ | |
1334 | while (changed > 0) | |
1335 | { | |
1336 | changed = 0; | |
1337 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1338 | changed += make_equivalent_phi_alternatives_equivalent (bb, p); | |
1339 | } | |
1340 | ||
1341 | return p; | |
1342 | } | |
1343 | ||
1344 | ||
1345 | /* Rename regs in insn PTR that are equivalent. DATA is the register | |
1346 | partition which specifies equivalences. */ | |
1347 | ||
1348 | static int | |
1349 | rename_equivalent_regs_in_insn (ptr, data) | |
1350 | rtx *ptr; | |
1351 | void* data; | |
1352 | { | |
1353 | rtx x = *ptr; | |
1354 | partition reg_partition = (partition) data; | |
1355 | ||
1356 | if (x == NULL_RTX) | |
1357 | return 0; | |
1358 | ||
1359 | switch (GET_CODE (x)) | |
1360 | { | |
1361 | case SET: | |
1362 | { | |
1363 | rtx *destp = &SET_DEST (x); | |
1364 | rtx dest = SET_DEST (x); | |
1365 | ||
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) | |
1370 | { | |
1371 | destp = &SUBREG_REG (dest); | |
1372 | dest = SUBREG_REG (dest); | |
1373 | } | |
1374 | ||
1375 | if (GET_CODE (dest) == REG | |
1376 | && REGNO (dest) >= FIRST_PSEUDO_REGISTER) | |
1377 | { | |
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]; | |
1383 | ||
1384 | for_each_rtx (&SET_SRC (x), | |
1385 | rename_equivalent_regs_in_insn, | |
1386 | data); | |
1387 | return -1; | |
1388 | } | |
1389 | ||
1390 | /* Otherwise, this was not an interesting destination. Continue | |
1391 | on, marking uses as normal. */ | |
1392 | return 0; | |
1393 | } | |
1394 | ||
1395 | case REG: | |
1396 | if (REGNO (x) >= FIRST_PSEUDO_REGISTER) | |
1397 | { | |
1398 | int regno = REGNO (x); | |
1399 | int new_regno = partition_find (reg_partition, regno); | |
1400 | if (regno != new_regno) | |
1401 | { | |
1402 | rtx new_reg = regno_reg_rtx[new_regno]; | |
1403 | if (GET_MODE (x) != GET_MODE (new_reg)) | |
1404 | abort (); | |
1405 | *ptr = new_reg; | |
1406 | } | |
1407 | } | |
1408 | return -1; | |
1409 | ||
1410 | case PHI: | |
1411 | /* No need to rename the phi nodes. We'll check equivalence | |
1412 | when inserting copies. */ | |
1413 | return -1; | |
1414 | ||
1415 | default: | |
1416 | /* Anything else, continue traversing. */ | |
1417 | return 0; | |
1418 | } | |
1419 | } | |
1420 | ||
1421 | ||
1422 | /* Rename regs that are equivalent in REG_PARTITION. */ | |
1423 | ||
1424 | static void | |
1425 | rename_equivalent_regs (reg_partition) | |
1426 | partition reg_partition; | |
1427 | { | |
1428 | int bb; | |
1429 | ||
1430 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1431 | { | |
1432 | basic_block b = BASIC_BLOCK (bb); | |
1433 | rtx next = b->head; | |
1434 | rtx last = b->end; | |
1435 | rtx insn; | |
1436 | ||
1437 | do | |
1438 | { | |
1439 | insn = next; | |
1440 | if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') | |
1441 | { | |
1442 | for_each_rtx (&PATTERN (insn), | |
1443 | rename_equivalent_regs_in_insn, | |
1444 | reg_partition); | |
1445 | for_each_rtx (®_NOTES (insn), | |
1446 | rename_equivalent_regs_in_insn, | |
1447 | reg_partition); | |
1448 | } | |
1449 | ||
1450 | next = NEXT_INSN (insn); | |
1451 | } | |
1452 | while (insn != last); | |
1453 | } | |
1454 | } | |
1455 | ||
1456 | ||
1457 | /* The main entry point for moving from SSA. */ | |
1458 | ||
1459 | void | |
1460 | convert_from_ssa() | |
1461 | { | |
1462 | int bb; | |
1463 | partition reg_partition; | |
1464 | ||
1465 | reg_partition = compute_conservative_reg_partition (); | |
1466 | rename_equivalent_regs (reg_partition); | |
1467 | ||
1468 | /* Eliminate the PHI nodes. */ | |
1469 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1470 | { | |
1471 | basic_block b = BASIC_BLOCK (bb); | |
1472 | edge e; | |
1473 | ||
1474 | for (e = b->pred; e; e = e->pred_next) | |
1475 | if (e->src != ENTRY_BLOCK_PTR) | |
1476 | eliminate_phi (e, reg_partition); | |
1477 | } | |
1478 | ||
1479 | partition_delete (reg_partition); | |
1480 | ||
1481 | /* Actually delete the PHI nodes. */ | |
1482 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1483 | { | |
1484 | rtx insn = BLOCK_HEAD (bb); | |
1485 | int start = (GET_CODE (insn) != CODE_LABEL); | |
1486 | ||
1487 | if (! start) | |
1488 | insn = next_nonnote_insn (insn); | |
1489 | while (PHI_NODE_P (insn)) | |
1490 | { | |
1491 | insn = delete_insn (insn); | |
1492 | if (GET_CODE (insn) == NOTE) | |
1493 | insn = next_nonnote_insn (insn); | |
1494 | } | |
1495 | if (start) | |
1496 | BLOCK_HEAD (bb) = insn; | |
1497 | } | |
1498 | ||
1499 | /* Commit all the copy nodes needed to convert out of SSA form. */ | |
1500 | commit_edge_insertions (); | |
1501 | ||
1502 | count_or_remove_death_notes (NULL, 1); | |
1503 | } |