]>
Commit | Line | Data |
---|---|---|
d9d4fb43 AS |
1 | /* Static Single Assignment conversion routines for the GNU compiler. |
2 | Copyright (C) 2000 Free Software Foundation, Inc. | |
3 | ||
770ae6cc | 4 | This file is part of GNU CC. |
d9d4fb43 | 5 | |
770ae6cc RK |
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 | |
9 | later version. | |
d9d4fb43 | 10 | |
770ae6cc RK |
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 | |
14 | for more details. | |
d9d4fb43 | 15 | |
770ae6cc RK |
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 | |
19 | 02111-1307, USA. */ | |
d9d4fb43 AS |
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 | ||
4e872036 AS |
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 | |
56 | they are adjacent). | |
57 | ||
d9d4fb43 AS |
58 | ??? What to do about strict_low_part. Probably I'll have to split |
59 | them out of their current instructions first thing. | |
60 | ||
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 | |
4e872036 AS |
65 | expansion. */ |
66 | ||
67 | ||
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; | |
d9d4fb43 | 74 | |
4e872036 AS |
75 | /* This flag is set when the CFG is in SSA form. */ |
76 | int in_ssa_form = 0; | |
d9d4fb43 AS |
77 | |
78 | /* Element I is the single instruction that sets register I+PSEUDO. */ | |
79 | varray_type ssa_definition; | |
80 | ||
81 | /* Element I is an INSN_LIST of instructions that use register I+PSEUDO. */ | |
82 | varray_type ssa_uses; | |
83 | ||
84 | /* Element I-PSEUDO is the normal register that originated the ssa | |
85 | register in question. */ | |
86 | varray_type ssa_rename_from; | |
87 | ||
88 | /* The running target ssa register for a given normal register. */ | |
89 | static rtx *ssa_rename_to; | |
90 | ||
91 | /* The number of registers that were live on entry to the SSA routines. */ | |
770ae6cc | 92 | static unsigned int ssa_max_reg_num; |
d9d4fb43 AS |
93 | |
94 | /* Local function prototypes. */ | |
95 | ||
96 | static inline rtx * phi_alternative | |
97 | PARAMS ((rtx, int)); | |
98 | ||
99 | static int remove_phi_alternative | |
100 | PARAMS ((rtx, int)); | |
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)); | |
123 | ||
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)); | |
d9d4fb43 AS |
134 | static int make_regs_equivalent_over_bad_edges |
135 | PARAMS ((int bb, partition reg_partition)); | |
4e872036 AS |
136 | |
137 | /* These are used only in the conservative register partitioning | |
138 | algorithms. */ | |
d9d4fb43 AS |
139 | static int make_equivalent_phi_alternatives_equivalent |
140 | PARAMS ((int bb, partition reg_partition)); | |
141 | static partition compute_conservative_reg_partition | |
4e872036 AS |
142 | PARAMS (()); |
143 | static int rename_equivalent_regs_in_insn | |
144 | PARAMS ((rtx *ptr, void *data)); | |
145 | ||
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 ((int 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 ((int bb, partition p, conflict_graph conflicts)); | |
155 | static partition compute_coalesced_reg_partition | |
156 | PARAMS (()); | |
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)); | |
161 | ||
d9d4fb43 AS |
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)); | |
166 | ||
167 | ||
d9d4fb43 AS |
168 | /* Given the SET of a PHI node, return the address of the alternative |
169 | for predecessor block C. */ | |
170 | ||
171 | static inline rtx * | |
172 | phi_alternative (set, c) | |
173 | rtx set; | |
174 | int c; | |
175 | { | |
176 | rtvec phi_vec = XVEC (SET_SRC (set), 0); | |
177 | int v; | |
178 | ||
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); | |
182 | ||
183 | return NULL; | |
184 | } | |
185 | ||
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 | |
188 | found for C. */ | |
189 | ||
190 | static int | |
191 | remove_phi_alternative (set, c) | |
192 | rtx set; | |
193 | int c; | |
194 | { | |
195 | rtvec phi_vec = XVEC (SET_SRC (set), 0); | |
196 | int num_elem = GET_NUM_ELEM (phi_vec); | |
197 | int v; | |
198 | ||
199 | for (v = num_elem - 2; v >= 0; v -= 2) | |
200 | if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c) | |
201 | { | |
202 | if (v < num_elem - 2) | |
203 | { | |
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); | |
206 | } | |
207 | PUT_NUM_ELEM (phi_vec, num_elem - 2); | |
208 | return 1; | |
209 | } | |
210 | ||
211 | return 0; | |
212 | } | |
213 | ||
214 | /* Computing the Immediate Dominators: | |
215 | ||
216 | Throughout, we don't actually want the full dominators set as | |
217 | calculated by flow, but rather the immediate dominators. | |
218 | */ | |
219 | ||
220 | static void | |
221 | simplify_to_immediate_dominators (idom, dominators) | |
222 | int *idom; | |
223 | sbitmap *dominators; | |
224 | { | |
225 | sbitmap *tmp; | |
226 | int b; | |
227 | ||
228 | tmp = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); | |
229 | ||
230 | /* Begin with tmp(n) = dom(n) - { n }. */ | |
231 | for (b = n_basic_blocks; --b >= 0; ) | |
232 | { | |
233 | sbitmap_copy (tmp[b], dominators[b]); | |
234 | RESET_BIT (tmp[b], b); | |
235 | } | |
236 | ||
237 | /* Subtract out all of our dominator's dominators. */ | |
238 | for (b = n_basic_blocks; --b >= 0; ) | |
239 | { | |
240 | sbitmap tmp_b = tmp[b]; | |
241 | int s; | |
242 | ||
243 | for (s = n_basic_blocks; --s >= 0; ) | |
244 | if (TEST_BIT (tmp_b, s)) | |
245 | sbitmap_difference (tmp_b, tmp_b, tmp[s]); | |
246 | } | |
247 | ||
248 | /* Find the one bit set in the bitmap and put it in the output array. */ | |
249 | for (b = n_basic_blocks; --b >= 0; ) | |
250 | { | |
251 | int t; | |
252 | EXECUTE_IF_SET_IN_SBITMAP (tmp[b], 0, t, { idom[b] = t; }); | |
253 | } | |
254 | ||
255 | sbitmap_vector_free (tmp); | |
256 | } | |
257 | ||
258 | ||
259 | /* For all registers, find all blocks in which they are set. | |
260 | ||
261 | This is the transform of what would be local kill information that | |
262 | we ought to be getting from flow. */ | |
263 | ||
264 | static sbitmap *fe_evals; | |
265 | static int fe_current_bb; | |
266 | ||
267 | static void | |
268 | find_evaluations_1 (dest, set, data) | |
269 | rtx dest; | |
270 | rtx set ATTRIBUTE_UNUSED; | |
271 | void *data ATTRIBUTE_UNUSED; | |
272 | { | |
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); | |
276 | } | |
277 | ||
278 | static void | |
279 | find_evaluations (evals, nregs) | |
280 | sbitmap *evals; | |
281 | int nregs; | |
282 | { | |
283 | int bb; | |
284 | ||
285 | sbitmap_vector_zero (evals, nregs); | |
286 | fe_evals = evals; | |
287 | ||
288 | for (bb = n_basic_blocks; --bb >= 0; ) | |
289 | { | |
290 | rtx p, last; | |
291 | ||
292 | fe_current_bb = bb; | |
293 | p = BLOCK_HEAD (bb); | |
294 | last = BLOCK_END (bb); | |
295 | while (1) | |
296 | { | |
297 | if (GET_RTX_CLASS (GET_CODE (p)) == 'i') | |
298 | note_stores (PATTERN (p), find_evaluations_1, NULL); | |
299 | ||
300 | if (p == last) | |
301 | break; | |
302 | p = NEXT_INSN (p); | |
303 | } | |
304 | } | |
305 | } | |
306 | ||
307 | ||
308 | /* Computing the Dominance Frontier: | |
309 | ||
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, | |
313 | there are two cases: | |
314 | ||
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 | |
318 | of B. | |
319 | ||
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. | |
323 | */ | |
324 | ||
325 | static void | |
326 | compute_dominance_frontiers_1 (frontiers, idom, bb, done) | |
327 | sbitmap *frontiers; | |
328 | int *idom; | |
329 | int bb; | |
330 | sbitmap done; | |
331 | { | |
332 | basic_block b = BASIC_BLOCK (bb); | |
333 | edge e; | |
334 | int c; | |
335 | ||
336 | SET_BIT (done, bb); | |
337 | sbitmap_zero (frontiers[bb]); | |
338 | ||
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); | |
345 | ||
346 | /* Find blocks conforming to rule (1) above. */ | |
347 | for (e = b->succ; e; e = e->succ_next) | |
348 | { | |
349 | if (e->dest == EXIT_BLOCK_PTR) | |
350 | continue; | |
351 | if (idom[e->dest->index] != bb) | |
352 | SET_BIT (frontiers[bb], e->dest->index); | |
353 | } | |
354 | ||
355 | /* Find blocks conforming to rule (2). */ | |
356 | for (c = 0; c < n_basic_blocks; ++c) | |
357 | if (idom[c] == bb) | |
358 | { | |
359 | int x; | |
360 | EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x, | |
361 | { | |
362 | if (idom[x] != bb) | |
363 | SET_BIT (frontiers[bb], x); | |
364 | }); | |
365 | } | |
366 | } | |
367 | ||
368 | static void | |
369 | compute_dominance_frontiers (frontiers, idom) | |
370 | sbitmap *frontiers; | |
371 | int *idom; | |
372 | { | |
373 | sbitmap done = sbitmap_alloc (n_basic_blocks); | |
374 | sbitmap_zero (done); | |
375 | ||
376 | compute_dominance_frontiers_1 (frontiers, idom, 0, done); | |
377 | ||
378 | sbitmap_free (done); | |
379 | } | |
380 | ||
381 | ||
382 | /* Computing the Iterated Dominance Frontier: | |
383 | ||
384 | This is the set of merge points for a given register. | |
385 | ||
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. | |
388 | */ | |
389 | ||
390 | static void | |
391 | compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs) | |
392 | sbitmap *idfs; | |
393 | sbitmap *frontiers; | |
394 | sbitmap *evals; | |
395 | int nregs; | |
396 | { | |
397 | sbitmap worklist; | |
398 | int reg, passes = 0; | |
399 | ||
400 | worklist = sbitmap_alloc (n_basic_blocks); | |
401 | ||
402 | for (reg = 0; reg < nregs; ++reg) | |
403 | { | |
404 | sbitmap idf = idfs[reg]; | |
405 | int b, changed; | |
406 | ||
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]); | |
411 | ||
412 | /* Morgan's algorithm is incorrect here. Blocks that evaluate | |
413 | REG aren't necessarily in REG's IDF. Start with an empty IDF. */ | |
414 | sbitmap_zero (idf); | |
415 | ||
416 | /* Iterate until the worklist is empty. */ | |
417 | do | |
418 | { | |
419 | changed = 0; | |
420 | passes++; | |
421 | EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b, | |
422 | { | |
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 | |
427 | to the worklist. */ | |
428 | sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf); | |
429 | sbitmap_a_or_b (idf, idf, frontiers[b]); | |
430 | changed = 1; | |
431 | }); | |
432 | } | |
433 | while (changed); | |
434 | } | |
435 | ||
436 | sbitmap_free (worklist); | |
437 | ||
438 | if (rtl_dump_file) | |
439 | { | |
440 | fprintf(rtl_dump_file, | |
441 | "Iterated dominance frontier: %d passes on %d regs.\n", | |
442 | passes, nregs); | |
443 | } | |
444 | } | |
445 | ||
446 | ||
447 | /* Insert the phi nodes. */ | |
448 | ||
449 | static void | |
450 | insert_phi_node (regno, bb) | |
451 | int regno, bb; | |
452 | { | |
453 | basic_block b = BASIC_BLOCK (bb); | |
454 | edge e; | |
455 | int npred, i; | |
456 | rtvec vec; | |
457 | rtx phi, reg; | |
458 | ||
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) | |
462 | npred++; | |
463 | ||
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. */ | |
466 | if (npred == 0) | |
467 | return; | |
468 | ||
469 | /* This is the register to which the phi function will be assinged. */ | |
470 | reg = regno_reg_rtx[regno + FIRST_PSEUDO_REGISTER]; | |
471 | ||
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) | |
477 | { | |
478 | RTVEC_ELT (vec, i + 0) = pc_rtx; | |
479 | RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index); | |
480 | } | |
481 | ||
482 | phi = gen_rtx_PHI (VOIDmode, vec); | |
483 | phi = gen_rtx_SET (VOIDmode, reg, phi); | |
484 | ||
485 | if (GET_CODE (b->head) == CODE_LABEL) | |
486 | emit_insn_after (phi, b->head); | |
487 | else | |
488 | b->head = emit_insn_before (phi, b->head); | |
489 | } | |
490 | ||
491 | ||
492 | static void | |
493 | insert_phi_nodes (idfs, evals, nregs) | |
494 | sbitmap *idfs; | |
495 | sbitmap *evals ATTRIBUTE_UNUSED; | |
496 | int nregs; | |
497 | { | |
498 | int reg; | |
499 | ||
500 | for (reg = 0; reg < nregs; ++reg) | |
501 | { | |
502 | int b; | |
503 | EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b, | |
504 | { | |
505 | if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, | |
506 | reg + FIRST_PSEUDO_REGISTER)) | |
507 | insert_phi_node (reg, b); | |
508 | }); | |
509 | } | |
510 | } | |
511 | ||
512 | /* Rename the registers to conform to SSA. | |
513 | ||
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. */ | |
517 | ||
518 | ||
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 | |
522 | { | |
523 | struct rename_set_data *next; | |
524 | rtx *reg_loc; | |
525 | rtx set_dest; | |
526 | rtx new_reg; | |
527 | rtx prev_reg; | |
4e872036 AS |
528 | rtx set_insn; |
529 | }; | |
530 | ||
531 | /* This struct is used to pass information to callback functions while | |
532 | renaming registers. */ | |
533 | struct rename_context | |
534 | { | |
535 | struct rename_set_data *set_data; | |
536 | rtx current_insn; | |
d9d4fb43 AS |
537 | }; |
538 | ||
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)); | |
542 | ||
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 | |
551 | ||
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. */ | |
554 | ||
555 | static int | |
556 | rename_insn_1 (ptr, data) | |
557 | rtx *ptr; | |
558 | void *data; | |
559 | { | |
560 | rtx x = *ptr; | |
4e872036 AS |
561 | struct rename_context *context = data; |
562 | struct rename_set_data **set_datap = &(context->set_data); | |
d9d4fb43 AS |
563 | |
564 | if (x == NULL_RTX) | |
565 | return 0; | |
566 | ||
567 | switch (GET_CODE (x)) | |
568 | { | |
569 | case SET: | |
570 | { | |
571 | rtx *destp = &SET_DEST (x); | |
572 | rtx dest = SET_DEST (x); | |
573 | ||
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) | |
578 | { | |
579 | destp = &SUBREG_REG (dest); | |
580 | dest = SUBREG_REG (dest); | |
581 | } | |
582 | ||
583 | if (GET_CODE (dest) == REG | |
584 | && REGNO (dest) >= FIRST_PSEUDO_REGISTER) | |
585 | { | |
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. */ | |
589 | ||
590 | struct rename_set_data *r; | |
591 | r = (struct rename_set_data *) xmalloc (sizeof(*r)); | |
592 | ||
593 | r->reg_loc = destp; | |
594 | r->set_dest = SET_DEST (x); | |
4e872036 | 595 | r->set_insn = context->current_insn; |
d9d4fb43 AS |
596 | r->next = *set_datap; |
597 | *set_datap = r; | |
598 | ||
599 | /* Since we do not wish to (directly) traverse the | |
600 | SET_DEST, recurse through for_each_rtx for the SET_SRC | |
601 | and return. */ | |
602 | for_each_rtx (&SET_SRC (x), rename_insn_1, data); | |
603 | return -1; | |
604 | } | |
605 | ||
606 | /* Otherwise, this was not an interesting destination. Continue | |
607 | on, marking uses as normal. */ | |
608 | return 0; | |
609 | } | |
610 | ||
611 | case REG: | |
612 | if (REGNO (x) >= FIRST_PSEUDO_REGISTER | |
613 | && REGNO (x) < ssa_max_reg_num) | |
614 | { | |
615 | rtx new_reg = ssa_rename_to[REGNO(x) - FIRST_PSEUDO_REGISTER]; | |
616 | ||
617 | if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX) | |
618 | { | |
619 | if (GET_MODE (x) != GET_MODE (new_reg)) | |
620 | abort (); | |
621 | *ptr = new_reg; | |
d9d4fb43 AS |
622 | } |
623 | /* Else this is a use before a set. Warn? */ | |
624 | } | |
625 | return -1; | |
626 | ||
627 | case PHI: | |
628 | /* Never muck with the phi. We do that elsewhere, special-like. */ | |
629 | return -1; | |
630 | ||
631 | default: | |
632 | /* Anything else, continue traversing. */ | |
633 | return 0; | |
634 | } | |
635 | } | |
636 | ||
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. */ | |
640 | ||
641 | static void | |
642 | new_registers_for_updates (set_data, old_set_data, insn) | |
643 | struct rename_set_data *set_data, *old_set_data; | |
644 | rtx insn; | |
645 | { | |
646 | while (set_data != old_set_data) | |
647 | { | |
648 | int regno, new_regno; | |
649 | rtx old_reg, new_reg, prev_reg; | |
650 | ||
651 | old_reg = *set_data->reg_loc; | |
652 | regno = REGNO (*set_data->reg_loc); | |
653 | ||
654 | /* For the first set we come across, reuse the original regno. */ | |
655 | if (ssa_rename_to[regno - FIRST_PSEUDO_REGISTER] == NULL_RTX) | |
656 | { | |
657 | new_reg = old_reg; | |
658 | prev_reg = RENAME_NO_RTX; | |
659 | } | |
660 | else | |
661 | { | |
662 | prev_reg = ssa_rename_to[regno - FIRST_PSEUDO_REGISTER]; | |
663 | new_reg = gen_reg_rtx (GET_MODE (old_reg)); | |
664 | } | |
665 | ||
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; | |
670 | ||
671 | if (new_regno >= (int) ssa_definition->num_elements) | |
672 | { | |
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); | |
677 | } | |
678 | ||
679 | VARRAY_RTX (ssa_definition, new_regno) = insn; | |
680 | VARRAY_RTX (ssa_rename_from, new_regno) = old_reg; | |
681 | ||
682 | set_data = set_data->next; | |
683 | } | |
684 | } | |
685 | ||
686 | static void | |
687 | rename_block (bb, idom) | |
688 | int bb; | |
689 | int *idom; | |
690 | { | |
691 | basic_block b = BASIC_BLOCK (bb); | |
692 | edge e; | |
693 | rtx insn, next, last; | |
694 | struct rename_set_data *set_data = NULL; | |
695 | int c; | |
696 | ||
697 | /* Step One: Walk the basic block, adding new names for sets and | |
698 | replacing uses. */ | |
699 | ||
700 | next = b->head; | |
701 | last = b->end; | |
702 | do | |
703 | { | |
704 | insn = next; | |
705 | if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') | |
706 | { | |
4e872036 AS |
707 | struct rename_context context; |
708 | context.set_data = set_data; | |
709 | context.current_insn = insn; | |
d9d4fb43 | 710 | |
4e872036 AS |
711 | for_each_rtx (&PATTERN (insn), rename_insn_1, &context); |
712 | for_each_rtx (®_NOTES (insn), rename_insn_1, &context); | |
d9d4fb43 | 713 | |
4e872036 AS |
714 | new_registers_for_updates (context.set_data, set_data, insn); |
715 | set_data = context.set_data; | |
d9d4fb43 AS |
716 | } |
717 | ||
718 | next = NEXT_INSN (insn); | |
719 | } | |
720 | while (insn != last); | |
721 | ||
722 | /* Step Two: Update the phi nodes of this block's successors. */ | |
723 | ||
724 | for (e = b->succ; e; e = e->succ_next) | |
725 | { | |
726 | if (e->dest == EXIT_BLOCK_PTR) | |
727 | continue; | |
728 | ||
729 | insn = e->dest->head; | |
730 | if (GET_CODE (insn) == CODE_LABEL) | |
731 | insn = NEXT_INSN (insn); | |
732 | ||
733 | while (PHI_NODE_P (insn)) | |
734 | { | |
735 | rtx phi = PATTERN (insn); | |
770ae6cc | 736 | unsigned int regno; |
d9d4fb43 AS |
737 | rtx reg; |
738 | ||
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]; | |
749 | ||
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) | |
754 | { | |
755 | if (! remove_phi_alternative (phi, bb)) | |
756 | abort (); | |
757 | } | |
758 | else | |
759 | { | |
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)) | |
766 | abort(); | |
767 | ||
768 | *phi_alternative (phi, bb) = reg; | |
769 | /* ??? Mark for a new ssa_uses entry. */ | |
770 | } | |
771 | ||
772 | insn = NEXT_INSN (insn); | |
773 | } | |
774 | } | |
775 | ||
776 | /* Step Three: Do the same to the children of this block in | |
777 | dominator order. */ | |
778 | ||
779 | for (c = 0; c < n_basic_blocks; ++c) | |
780 | if (idom[c] == bb) | |
781 | rename_block (c, idom); | |
782 | ||
783 | /* Step Four: Update the sets to refer to their new register. */ | |
784 | ||
785 | while (set_data) | |
786 | { | |
787 | struct rename_set_data *next; | |
4e872036 AS |
788 | rtx old_reg = *set_data->reg_loc; |
789 | ||
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. */ | |
794 | ||
795 | if (GET_CODE (set_data->set_dest) == SUBREG) | |
796 | { | |
797 | if (old_reg != set_data->new_reg) | |
798 | { | |
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); | |
802 | } | |
803 | } | |
d9d4fb43 | 804 | |
d9d4fb43 AS |
805 | *set_data->reg_loc = set_data->new_reg; |
806 | ssa_rename_to[REGNO (old_reg)-FIRST_PSEUDO_REGISTER] | |
807 | = set_data->prev_reg; | |
808 | ||
809 | next = set_data->next; | |
810 | free (set_data); | |
811 | set_data = next; | |
812 | } | |
813 | } | |
814 | ||
815 | static void | |
816 | rename_registers (nregs, idom) | |
817 | int nregs; | |
818 | int *idom; | |
819 | { | |
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"); | |
823 | ||
824 | ssa_rename_to = (rtx *) alloca (nregs * sizeof(rtx)); | |
665f2503 | 825 | bzero ((char *) ssa_rename_to, nregs * sizeof(rtx)); |
d9d4fb43 AS |
826 | |
827 | rename_block (0, idom); | |
828 | ||
829 | /* ??? Update basic_block_live_at_start, and other flow info | |
830 | as needed. */ | |
831 | ||
832 | ssa_rename_to = NULL; | |
833 | } | |
834 | ||
835 | ||
836 | /* The main entry point for moving to SSA. */ | |
837 | ||
838 | void | |
839 | convert_to_ssa() | |
840 | { | |
841 | /* Element I is the set of blocks that set register I. */ | |
842 | sbitmap *evals; | |
843 | ||
844 | /* Dominator bitmaps. */ | |
845 | sbitmap *dominators; | |
846 | sbitmap *dfs; | |
847 | sbitmap *idfs; | |
848 | ||
849 | /* Element I is the immediate dominator of block I. */ | |
850 | int *idom; | |
851 | ||
852 | int nregs; | |
853 | ||
4e872036 AS |
854 | /* Don't do it twice. */ |
855 | if (in_ssa_form) | |
856 | abort (); | |
857 | ||
d9d4fb43 | 858 | find_basic_blocks (get_insns (), max_reg_num(), NULL); |
4e872036 | 859 | /* The dominator algorithms assume all blocks are reachable; clean |
d9d4fb43 AS |
860 | up first. */ |
861 | cleanup_cfg (get_insns ()); | |
4e872036 AS |
862 | /* Don't eliminate dead code here. The CFG we computed above must |
863 | remain unchanged until we are finished emerging from SSA form -- | |
864 | the phi node representation depends on it. */ | |
865 | life_analysis (get_insns (), max_reg_num (), NULL, 0); | |
d9d4fb43 AS |
866 | |
867 | /* Compute dominators. */ | |
868 | dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); | |
869 | compute_flow_dominators (dominators, NULL); | |
870 | ||
871 | idom = (int *) alloca (n_basic_blocks * sizeof (int)); | |
872 | memset ((void *)idom, -1, (size_t)n_basic_blocks * sizeof (int)); | |
873 | simplify_to_immediate_dominators (idom, dominators); | |
874 | ||
875 | sbitmap_vector_free (dominators); | |
876 | ||
877 | if (rtl_dump_file) | |
878 | { | |
879 | int i; | |
880 | fputs (";; Immediate Dominators:\n", rtl_dump_file); | |
881 | for (i = 0; i < n_basic_blocks; ++i) | |
882 | fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]); | |
883 | fflush (rtl_dump_file); | |
884 | } | |
885 | ||
886 | /* Compute dominance frontiers. */ | |
887 | ||
888 | dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); | |
889 | compute_dominance_frontiers (dfs, idom); | |
890 | ||
891 | if (rtl_dump_file) | |
892 | { | |
893 | dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:", | |
894 | "; Basic Block", dfs, n_basic_blocks); | |
895 | fflush (rtl_dump_file); | |
896 | } | |
897 | ||
898 | /* Compute register evaluations. */ | |
899 | ||
900 | ssa_max_reg_num = max_reg_num(); | |
901 | nregs = ssa_max_reg_num - FIRST_PSEUDO_REGISTER; | |
902 | evals = sbitmap_vector_alloc (nregs, n_basic_blocks); | |
903 | find_evaluations (evals, nregs); | |
904 | ||
905 | /* Compute the iterated dominance frontier for each register. */ | |
906 | ||
907 | idfs = sbitmap_vector_alloc (nregs, n_basic_blocks); | |
908 | compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs); | |
909 | ||
910 | if (rtl_dump_file) | |
911 | { | |
912 | dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:", | |
913 | "; Register-FIRST_PSEUDO_REGISTER", idfs, nregs); | |
914 | fflush (rtl_dump_file); | |
915 | } | |
916 | ||
917 | /* Insert the phi nodes. */ | |
918 | ||
919 | insert_phi_nodes (idfs, evals, nregs); | |
920 | ||
921 | /* Rename the registers to satisfy SSA. */ | |
922 | ||
923 | rename_registers (nregs, idom); | |
924 | ||
925 | /* All done! Clean up and go home. */ | |
926 | ||
927 | sbitmap_vector_free (dfs); | |
928 | sbitmap_vector_free (evals); | |
929 | sbitmap_vector_free (idfs); | |
4e872036 | 930 | in_ssa_form = 1; |
d9d4fb43 | 931 | |
4e872036 AS |
932 | reg_scan (get_insns (), max_reg_num (), 1); |
933 | find_basic_blocks (get_insns (), max_reg_num (), NULL); | |
934 | life_analysis (get_insns (), max_reg_num (), NULL, 0); | |
935 | } | |
d9d4fb43 | 936 | |
d9d4fb43 AS |
937 | |
938 | /* REG is the representative temporary of its partition. Add it to the | |
939 | set of nodes to be processed, if it hasn't been already. Return the | |
940 | index of this register in the node set. */ | |
941 | ||
942 | static inline int | |
943 | ephi_add_node (reg, nodes, n_nodes) | |
944 | rtx reg, *nodes; | |
945 | int *n_nodes; | |
946 | { | |
947 | int i; | |
948 | for (i = *n_nodes - 1; i >= 0; --i) | |
949 | if (REGNO (reg) == REGNO (nodes[i])) | |
950 | return i; | |
951 | ||
952 | nodes[i = (*n_nodes)++] = reg; | |
953 | return i; | |
954 | } | |
955 | ||
956 | /* Part one of the topological sort. This is a forward (downward) search | |
957 | through the graph collecting a stack of nodes to process. Assuming no | |
958 | cycles, the nodes at top of the stack when we are finished will have | |
959 | no other dependancies. */ | |
960 | ||
961 | static int * | |
962 | ephi_forward (t, visited, succ, tstack) | |
963 | int t; | |
964 | sbitmap visited; | |
965 | sbitmap *succ; | |
966 | int *tstack; | |
967 | { | |
968 | int s; | |
969 | ||
970 | SET_BIT (visited, t); | |
971 | ||
972 | EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s, | |
973 | { | |
974 | if (! TEST_BIT (visited, s)) | |
975 | tstack = ephi_forward (s, visited, succ, tstack); | |
976 | }); | |
977 | ||
978 | *tstack++ = t; | |
979 | return tstack; | |
980 | } | |
981 | ||
982 | /* Part two of the topological sort. The is a backward search through | |
983 | a cycle in the graph, copying the data forward as we go. */ | |
984 | ||
985 | static void | |
986 | ephi_backward (t, visited, pred, nodes) | |
987 | int t; | |
988 | sbitmap visited, *pred; | |
989 | rtx *nodes; | |
990 | { | |
991 | int p; | |
992 | ||
993 | SET_BIT (visited, t); | |
994 | ||
995 | EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, | |
996 | { | |
997 | if (! TEST_BIT (visited, p)) | |
998 | { | |
999 | ephi_backward (p, visited, pred, nodes); | |
1000 | emit_move_insn (nodes[p], nodes[t]); | |
1001 | } | |
1002 | }); | |
1003 | } | |
1004 | ||
1005 | /* Part two of the topological sort. Create the copy for a register | |
1006 | and any cycle of which it is a member. */ | |
1007 | ||
1008 | static void | |
1009 | ephi_create (t, visited, pred, succ, nodes) | |
1010 | int t; | |
1011 | sbitmap visited, *pred, *succ; | |
1012 | rtx *nodes; | |
1013 | { | |
1014 | rtx reg_u = NULL_RTX; | |
1015 | int unvisited_predecessors = 0; | |
1016 | int p; | |
1017 | ||
1018 | /* Iterate through the predecessor list looking for unvisited nodes. | |
1019 | If there are any, we have a cycle, and must deal with that. At | |
1020 | the same time, look for a visited predecessor. If there is one, | |
1021 | we won't need to create a temporary. */ | |
1022 | ||
1023 | EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, | |
1024 | { | |
1025 | if (! TEST_BIT (visited, p)) | |
1026 | unvisited_predecessors = 1; | |
1027 | else if (!reg_u) | |
1028 | reg_u = nodes[p]; | |
1029 | }); | |
1030 | ||
1031 | if (unvisited_predecessors) | |
1032 | { | |
1033 | /* We found a cycle. Copy out one element of the ring (if necessary), | |
1034 | then traverse the ring copying as we go. */ | |
1035 | ||
1036 | if (!reg_u) | |
1037 | { | |
1038 | reg_u = gen_reg_rtx (GET_MODE (nodes[t])); | |
1039 | emit_move_insn (reg_u, nodes[t]); | |
1040 | } | |
1041 | ||
1042 | EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p, | |
1043 | { | |
1044 | if (! TEST_BIT (visited, p)) | |
1045 | { | |
1046 | ephi_backward (p, visited, pred, nodes); | |
1047 | emit_move_insn (nodes[p], reg_u); | |
1048 | } | |
1049 | }); | |
1050 | } | |
1051 | else | |
1052 | { | |
1053 | /* No cycle. Just copy the value from a successor. */ | |
1054 | ||
1055 | int s; | |
1056 | EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s, | |
1057 | { | |
1058 | SET_BIT (visited, t); | |
1059 | emit_move_insn (nodes[t], nodes[s]); | |
1060 | return; | |
1061 | }); | |
1062 | } | |
1063 | } | |
1064 | ||
1065 | /* Convert the edge to normal form. */ | |
1066 | ||
1067 | static void | |
1068 | eliminate_phi (e, reg_partition) | |
1069 | edge e; | |
1070 | partition reg_partition; | |
1071 | { | |
1072 | int n_nodes; | |
1073 | sbitmap *pred, *succ; | |
1074 | sbitmap visited; | |
1075 | rtx *nodes; | |
1076 | int *stack, *tstack; | |
1077 | rtx insn; | |
1078 | int i; | |
1079 | ||
1080 | /* Collect an upper bound on the number of registers needing processing. */ | |
1081 | ||
1082 | insn = e->dest->head; | |
1083 | if (GET_CODE (insn) == CODE_LABEL) | |
1084 | insn = next_nonnote_insn (insn); | |
1085 | ||
1086 | n_nodes = 0; | |
1087 | while (PHI_NODE_P (insn)) | |
1088 | { | |
1089 | insn = next_nonnote_insn (insn); | |
1090 | n_nodes += 2; | |
1091 | } | |
1092 | ||
1093 | if (n_nodes == 0) | |
1094 | return; | |
1095 | ||
1096 | /* Build the auxilliary graph R(B). | |
1097 | ||
1098 | The nodes of the graph are the members of the register partition | |
1099 | present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for | |
1100 | each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */ | |
1101 | ||
1102 | nodes = (rtx *) alloca (n_nodes * sizeof(rtx)); | |
1103 | pred = sbitmap_vector_alloc (n_nodes, n_nodes); | |
1104 | succ = sbitmap_vector_alloc (n_nodes, n_nodes); | |
1105 | sbitmap_vector_zero (pred, n_nodes); | |
1106 | sbitmap_vector_zero (succ, n_nodes); | |
1107 | ||
1108 | insn = e->dest->head; | |
1109 | if (GET_CODE (insn) == CODE_LABEL) | |
1110 | insn = next_nonnote_insn (insn); | |
1111 | ||
1112 | n_nodes = 0; | |
1113 | for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn)) | |
1114 | { | |
1115 | rtx* preg = phi_alternative (PATTERN (insn), e->src->index); | |
1116 | rtx tgt = SET_DEST (PATTERN (insn)); | |
1117 | rtx reg; | |
1118 | ||
1119 | /* There may be no phi alternative corresponding to this edge. | |
1120 | This indicates that the phi variable is undefined along this | |
1121 | edge. */ | |
1122 | if (preg == NULL) | |
1123 | continue; | |
1124 | reg = *preg; | |
1125 | ||
1126 | if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG) | |
1127 | abort(); | |
1128 | ||
4e872036 AS |
1129 | reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))]; |
1130 | tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))]; | |
d9d4fb43 AS |
1131 | /* If the two registers are already in the same partition, |
1132 | nothing will need to be done. */ | |
4e872036 | 1133 | if (reg != tgt) |
d9d4fb43 AS |
1134 | { |
1135 | int ireg, itgt; | |
1136 | ||
1137 | ireg = ephi_add_node (reg, nodes, &n_nodes); | |
1138 | itgt = ephi_add_node (tgt, nodes, &n_nodes); | |
1139 | ||
1140 | SET_BIT (pred[ireg], itgt); | |
1141 | SET_BIT (succ[itgt], ireg); | |
1142 | } | |
1143 | } | |
1144 | ||
1145 | if (n_nodes == 0) | |
1146 | goto out; | |
1147 | ||
1148 | /* Begin a topological sort of the graph. */ | |
1149 | ||
1150 | visited = sbitmap_alloc (n_nodes); | |
1151 | sbitmap_zero (visited); | |
1152 | ||
1153 | tstack = stack = (int *) alloca (n_nodes * sizeof (int)); | |
1154 | ||
1155 | for (i = 0; i < n_nodes; ++i) | |
1156 | if (! TEST_BIT (visited, i)) | |
1157 | tstack = ephi_forward (i, visited, succ, tstack); | |
1158 | ||
1159 | sbitmap_zero (visited); | |
1160 | ||
1161 | /* As we find a solution to the tsort, collect the implementation | |
1162 | insns in a sequence. */ | |
1163 | start_sequence (); | |
1164 | ||
1165 | while (tstack != stack) | |
1166 | { | |
1167 | i = *--tstack; | |
1168 | if (! TEST_BIT (visited, i)) | |
1169 | ephi_create (i, visited, pred, succ, nodes); | |
1170 | } | |
1171 | ||
1172 | insn = gen_sequence (); | |
1173 | end_sequence (); | |
1174 | insert_insn_on_edge (insn, e); | |
1175 | if (rtl_dump_file) | |
1176 | fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n", | |
1177 | e->src->index, e->dest->index); | |
1178 | ||
1179 | sbitmap_free (visited); | |
1180 | out: | |
1181 | sbitmap_vector_free (pred); | |
1182 | sbitmap_vector_free (succ); | |
1183 | } | |
1184 | ||
1185 | ||
1186 | /* For basic block B, consider all phi insns which provide an | |
1187 | alternative corresponding to an incoming abnormal critical edge. | |
1188 | Place the phi alternative corresponding to that abnormal critical | |
1189 | edge in the same register class as the destination of the set. | |
1190 | ||
1191 | From Morgan, p. 178: | |
1192 | ||
1193 | For each abnormal critical edge (C, B), | |
1194 | if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B, | |
1195 | and C is the ith predecessor of B, | |
1196 | then T0 and Ti must be equivalent. | |
1197 | ||
1198 | Return non-zero iff any such cases were found for which the two | |
1199 | regs were not already in the same class. */ | |
1200 | ||
1201 | static int | |
1202 | make_regs_equivalent_over_bad_edges (bb, reg_partition) | |
1203 | int bb; | |
1204 | partition reg_partition; | |
1205 | { | |
1206 | int changed = 0; | |
1207 | basic_block b = BASIC_BLOCK (bb); | |
1208 | rtx phi = b->head; | |
1209 | ||
1210 | /* Advance to the first phi node. */ | |
1211 | if (GET_CODE (phi) == CODE_LABEL) | |
1212 | phi = next_nonnote_insn (phi); | |
1213 | ||
1214 | /* Scan all the phi nodes. */ | |
1215 | for (; | |
1216 | PHI_NODE_P (phi); | |
1217 | phi = next_nonnote_insn (phi)) | |
1218 | { | |
1219 | edge e; | |
1220 | int tgt_regno; | |
1221 | rtx set = PATTERN (phi); | |
1222 | rtx tgt = SET_DEST (set); | |
1223 | ||
1224 | /* The set target is expected to be a pseudo. */ | |
1225 | if (GET_CODE (tgt) != REG | |
1226 | || REGNO (tgt) < FIRST_PSEUDO_REGISTER) | |
1227 | abort (); | |
1228 | tgt_regno = REGNO (tgt); | |
1229 | ||
1230 | /* Scan incoming abnormal critical edges. */ | |
1231 | for (e = b->pred; e; e = e->pred_next) | |
1232 | if (e->flags & (EDGE_ABNORMAL | EDGE_CRITICAL)) | |
1233 | { | |
1234 | rtx *alt = phi_alternative (set, e->src->index); | |
1235 | int alt_regno; | |
1236 | ||
1237 | /* If there is no alternative corresponding to this edge, | |
1238 | the value is undefined along the edge, so just go on. */ | |
1239 | if (alt == 0) | |
1240 | continue; | |
1241 | ||
1242 | /* The phi alternative is expected to be a pseudo. */ | |
1243 | if (GET_CODE (*alt) != REG | |
1244 | || REGNO (*alt) < FIRST_PSEUDO_REGISTER) | |
1245 | abort (); | |
1246 | alt_regno = REGNO (*alt); | |
1247 | ||
1248 | /* If the set destination and the phi alternative aren't | |
1249 | already in the same class... */ | |
1250 | if (partition_find (reg_partition, tgt_regno) | |
1251 | != partition_find (reg_partition, alt_regno)) | |
1252 | { | |
1253 | /* ... make them such. */ | |
1254 | partition_union (reg_partition, | |
1255 | tgt_regno, alt_regno); | |
1256 | ++changed; | |
1257 | } | |
1258 | } | |
1259 | } | |
1260 | ||
1261 | return changed; | |
1262 | } | |
1263 | ||
1264 | ||
1265 | /* Consider phi insns in basic block BB pairwise. If the set target | |
1266 | of both isns are equivalent pseudos, make the corresponding phi | |
1267 | alternatives in each phi corresponding equivalent. | |
1268 | ||
1269 | Return nonzero if any new register classes were unioned. */ | |
1270 | ||
1271 | static int | |
1272 | make_equivalent_phi_alternatives_equivalent (bb, reg_partition) | |
1273 | int bb; | |
1274 | partition reg_partition; | |
1275 | { | |
1276 | int changed = 0; | |
1277 | rtx phi = BLOCK_HEAD (bb); | |
1278 | basic_block b = BASIC_BLOCK (bb); | |
1279 | ||
1280 | /* Advance to the first phi node. */ | |
1281 | if (GET_CODE (phi) == CODE_LABEL) | |
1282 | phi = next_nonnote_insn (phi); | |
1283 | ||
1284 | /* Scan all the phi nodes. */ | |
1285 | for (; | |
1286 | PHI_NODE_P (phi); | |
1287 | phi = next_nonnote_insn (phi)) | |
1288 | { | |
1289 | rtx set = PATTERN (phi); | |
1290 | /* The regno of the destination of the set. */ | |
1291 | int tgt_regno = REGNO (SET_DEST (PATTERN (phi))); | |
1292 | ||
1293 | rtx phi2 = next_nonnote_insn (phi); | |
1294 | ||
1295 | /* Scan all phi nodes following this one. */ | |
1296 | for (; | |
1297 | PHI_NODE_P (phi2); | |
1298 | phi2 = next_nonnote_insn (phi2)) | |
1299 | { | |
1300 | rtx set2 = PATTERN (phi2); | |
1301 | /* The regno of the destination of the set. */ | |
1302 | int tgt2_regno = REGNO (SET_DEST (set2)); | |
1303 | ||
1304 | /* Are the set destinations equivalent regs? */ | |
1305 | if (partition_find (reg_partition, tgt_regno) == | |
1306 | partition_find (reg_partition, tgt2_regno)) | |
1307 | { | |
1308 | edge e; | |
1309 | /* Scan over edges. */ | |
1310 | for (e = b->pred; e; e = e->pred_next) | |
1311 | { | |
1312 | int pred_block = e->src->index; | |
1313 | /* Identify the phi altnernatives from both phi | |
1314 | nodes corresponding to this edge. */ | |
1315 | rtx *alt = phi_alternative (set, pred_block); | |
1316 | rtx *alt2 = phi_alternative (set2, pred_block); | |
1317 | ||
1318 | /* If one of the phi nodes doesn't have a | |
1319 | corresponding alternative, just skip it. */ | |
1320 | if (alt == 0 || alt2 == 0) | |
1321 | continue; | |
1322 | ||
1323 | /* Both alternatives should be pseudos. */ | |
1324 | if (GET_CODE (*alt) != REG | |
1325 | || REGNO (*alt) < FIRST_PSEUDO_REGISTER) | |
1326 | abort (); | |
1327 | if (GET_CODE (*alt2) != REG | |
1328 | || REGNO (*alt2) < FIRST_PSEUDO_REGISTER) | |
1329 | abort (); | |
1330 | ||
1331 | /* If the altneratives aren't already in the same | |
1332 | class ... */ | |
1333 | if (partition_find (reg_partition, REGNO (*alt)) | |
1334 | != partition_find (reg_partition, REGNO (*alt2))) | |
1335 | { | |
1336 | /* ... make them so. */ | |
1337 | partition_union (reg_partition, | |
1338 | REGNO (*alt), REGNO (*alt2)); | |
1339 | ++changed; | |
1340 | } | |
1341 | } | |
1342 | } | |
1343 | } | |
1344 | } | |
1345 | ||
1346 | return changed; | |
1347 | } | |
1348 | ||
d9d4fb43 AS |
1349 | /* Compute a conservative partition of outstanding pseudo registers. |
1350 | See Morgan 7.3.1. */ | |
1351 | ||
1352 | static partition | |
1353 | compute_conservative_reg_partition () | |
1354 | { | |
1355 | int bb; | |
1356 | int changed = 0; | |
1357 | ||
1358 | /* We don't actually work with hard registers, but it's easier to | |
1359 | carry them around anyway rather than constantly doing register | |
1360 | number arithmetic. */ | |
1361 | partition p = | |
1362 | partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER); | |
1363 | ||
1364 | /* The first priority is to make sure registers that might have to | |
1365 | be copied on abnormal critical edges are placed in the same | |
1366 | partition. This saves us from having to split abnormal critical | |
1367 | edges. */ | |
1368 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1369 | changed += make_regs_equivalent_over_bad_edges (bb, p); | |
1370 | ||
1371 | /* Now we have to insure that corresponding arguments of phi nodes | |
1372 | assigning to corresponding regs are equivalent. Iterate until | |
1373 | nothing changes. */ | |
1374 | while (changed > 0) | |
1375 | { | |
1376 | changed = 0; | |
1377 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1378 | changed += make_equivalent_phi_alternatives_equivalent (bb, p); | |
1379 | } | |
1380 | ||
1381 | return p; | |
1382 | } | |
1383 | ||
4e872036 AS |
1384 | /* The following functions compute a register partition that attempts |
1385 | to eliminate as many reg copies and phi node copies as possible by | |
1386 | coalescing registers. This is the strategy: | |
1387 | ||
1388 | 1. As in the conservative case, the top priority is to coalesce | |
1389 | registers that otherwise would cause copies to be placed on | |
1390 | abnormal critical edges (which isn't possible). | |
1391 | ||
1392 | 2. Figure out which regs are involved (in the LHS or RHS) of | |
1393 | copies and phi nodes. Compute conflicts among these regs. | |
1394 | ||
1395 | 3. Walk around the instruction stream, placing two regs in the | |
1396 | same class of the partition if one appears on the LHS and the | |
1397 | other on the RHS of a copy or phi node and the two regs don't | |
1398 | conflict. The conflict information of course needs to be | |
1399 | updated. | |
1400 | ||
1401 | 4. If anything has changed, there may be new opportunities to | |
1402 | coalesce regs, so go back to 2. | |
1403 | */ | |
1404 | ||
1405 | /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the | |
1406 | same class of partition P, if they aren't already. Update | |
1407 | CONFLICTS appropriately. | |
1408 | ||
1409 | Returns one if REG1 and REG2 were placed in the same class but were | |
1410 | not previously; zero otherwise. | |
1411 | ||
1412 | See Morgan figure 11.15. */ | |
1413 | ||
1414 | static int | |
1415 | coalesce_if_unconflicting (p, conflicts, reg1, reg2) | |
1416 | partition p; | |
1417 | conflict_graph conflicts; | |
1418 | int reg1; | |
1419 | int reg2; | |
1420 | { | |
1421 | int reg; | |
1422 | ||
1423 | /* Don't mess with hard regs. */ | |
1424 | if (reg1 < FIRST_PSEUDO_REGISTER || reg2 < FIRST_PSEUDO_REGISTER) | |
1425 | return 0; | |
1426 | ||
1427 | /* Find the canonical regs for the classes containing REG1 and | |
1428 | REG2. */ | |
1429 | reg1 = partition_find (p, reg1); | |
1430 | reg2 = partition_find (p, reg2); | |
1431 | ||
1432 | /* If they're already in the same class, there's nothing to do. */ | |
1433 | if (reg1 == reg2) | |
1434 | return 0; | |
1435 | ||
1436 | /* If the regs conflict, our hands are tied. */ | |
1437 | if (conflict_graph_conflict_p (conflicts, reg1, reg2)) | |
1438 | return 0; | |
1439 | ||
1440 | /* We're good to go. Put the regs in the same partition. */ | |
1441 | partition_union (p, reg1, reg2); | |
1442 | ||
1443 | /* Find the new canonical reg for the merged class. */ | |
1444 | reg = partition_find (p, reg1); | |
1445 | ||
1446 | /* Merge conflicts from the two previous classes. */ | |
1447 | conflict_graph_merge_regs (conflicts, reg, reg1); | |
1448 | conflict_graph_merge_regs (conflicts, reg, reg2); | |
1449 | ||
1450 | return 1; | |
1451 | } | |
1452 | ||
1453 | /* For each register copy insn in basic block BB, place the LHS and | |
1454 | RHS regs in the same class in partition P if they do not conflict | |
1455 | according to CONFLICTS. | |
1456 | ||
1457 | Returns the number of changes that were made to P. | |
1458 | ||
1459 | See Morgan figure 11.14. */ | |
1460 | ||
1461 | static int | |
1462 | coalesce_regs_in_copies (bb, p, conflicts) | |
1463 | int bb; | |
1464 | partition p; | |
1465 | conflict_graph conflicts; | |
1466 | { | |
1467 | int changed = 0; | |
1468 | rtx insn; | |
1469 | rtx end = BLOCK_END (bb); | |
1470 | ||
1471 | /* Scan the instruction stream of the block. */ | |
1472 | for (insn = BLOCK_HEAD (bb); insn != end; insn = NEXT_INSN (insn)) | |
1473 | { | |
1474 | rtx pattern; | |
1475 | rtx src; | |
1476 | rtx dest; | |
1477 | ||
1478 | /* If this isn't a set insn, go to the next insn. */ | |
1479 | if (GET_CODE (insn) != INSN) | |
1480 | continue; | |
1481 | pattern = PATTERN (insn); | |
1482 | if (GET_CODE (pattern) != SET) | |
1483 | continue; | |
1484 | ||
1485 | src = SET_SRC (pattern); | |
1486 | dest = SET_DEST (pattern); | |
1487 | ||
1488 | /* If src or dest are subregs, find the underlying reg. */ | |
1489 | while (GET_CODE (src) == SUBREG | |
1490 | && SUBREG_WORD (src) != 0) | |
1491 | src = SUBREG_REG (src); | |
1492 | while (GET_CODE (dest) == SUBREG | |
1493 | && SUBREG_WORD (dest) != 0) | |
1494 | dest = SUBREG_REG (dest); | |
1495 | ||
1496 | /* We're only looking for copies. */ | |
1497 | if (GET_CODE (src) != REG || GET_CODE (dest) != REG) | |
1498 | continue; | |
1499 | ||
1500 | /* Coalesce only if the reg modes are the same. As long as | |
1501 | each reg's rtx is unique, it can have only one mode, so two | |
1502 | pseudos of different modes can't be coalesced into one. | |
1503 | ||
1504 | FIXME: We can probably get around this by inserting SUBREGs | |
1505 | where appropriate, but for now we don't bother. */ | |
1506 | if (GET_MODE (src) != GET_MODE (dest)) | |
1507 | continue; | |
1508 | ||
1509 | /* Found a copy; see if we can use the same reg for both the | |
1510 | source and destination (and thus eliminate the copy, | |
1511 | ultimately). */ | |
1512 | changed += coalesce_if_unconflicting (p, conflicts, | |
1513 | REGNO (src), REGNO (dest)); | |
1514 | } | |
1515 | ||
1516 | return changed; | |
1517 | } | |
1518 | ||
1519 | ||
1520 | struct phi_coalesce_context | |
1521 | { | |
1522 | partition p; | |
1523 | conflict_graph conflicts; | |
1524 | int changed; | |
1525 | }; | |
1526 | ||
1527 | /* Callback function for for_each_successor_phi. If the set | |
1528 | destination and the phi alternative regs do not conflict, place | |
1529 | them in the same paritition class. DATA is a pointer to a | |
1530 | phi_coalesce_context struct. */ | |
1531 | ||
1532 | static int | |
1533 | coalesce_reg_in_phi (insn, dest_regno, src_regno, data) | |
1534 | rtx insn ATTRIBUTE_UNUSED; | |
1535 | int dest_regno; | |
1536 | int src_regno; | |
1537 | void *data; | |
1538 | { | |
1539 | struct phi_coalesce_context *context = | |
1540 | (struct phi_coalesce_context *) data; | |
1541 | ||
1542 | /* Attempt to use the same reg, if they don't conflict. */ | |
1543 | context->changed | |
1544 | += coalesce_if_unconflicting (context->p, context->conflicts, | |
1545 | dest_regno, src_regno); | |
1546 | return 0; | |
1547 | } | |
1548 | ||
1549 | /* For each alternative in a phi function corresponding to basic block | |
1550 | BB (in phi nodes in successor block to BB), place the reg in the | |
1551 | phi alternative and the reg to which the phi value is set into the | |
1552 | same class in partition P, if allowed by CONFLICTS. | |
1553 | ||
1554 | Return the number of changes that were made to P. | |
1555 | ||
1556 | See Morgan figure 11.14. */ | |
1557 | ||
1558 | static int | |
1559 | coalesce_regs_in_successor_phi_nodes (bb, p, conflicts) | |
1560 | int bb; | |
1561 | partition p; | |
1562 | conflict_graph conflicts; | |
1563 | { | |
1564 | struct phi_coalesce_context context; | |
1565 | context.p = p; | |
1566 | context.conflicts = conflicts; | |
1567 | context.changed = 0; | |
1568 | ||
1569 | for_each_successor_phi (bb, &coalesce_reg_in_phi, &context); | |
1570 | ||
1571 | return context.changed; | |
1572 | } | |
1573 | ||
1574 | /* Compute and return a partition of pseudos. Where possible, | |
1575 | non-conflicting pseudos are placed in the same class. | |
1576 | ||
1577 | The caller is responsible for deallocating the returned partition. */ | |
1578 | ||
1579 | static partition | |
1580 | compute_coalesced_reg_partition () | |
1581 | { | |
1582 | int bb; | |
1583 | int changed = 0; | |
1584 | ||
1585 | /* We don't actually work with hard registers, but it's easier to | |
1586 | carry them around anyway rather than constantly doing register | |
1587 | number arithmetic. */ | |
1588 | partition p = | |
1589 | partition_new (ssa_definition->num_elements + FIRST_PSEUDO_REGISTER); | |
1590 | ||
1591 | /* The first priority is to make sure registers that might have to | |
1592 | be copied on abnormal critical edges are placed in the same | |
1593 | partition. This saves us from having to split abnormal critical | |
1594 | edges (which can't be done). */ | |
1595 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1596 | make_regs_equivalent_over_bad_edges (bb, p); | |
1597 | ||
1598 | do | |
1599 | { | |
1600 | regset_head phi_set; | |
1601 | conflict_graph conflicts; | |
1602 | ||
1603 | changed = 0; | |
1604 | ||
1605 | /* Build the set of registers involved in phi nodes, either as | |
1606 | arguments to the phi function or as the target of a set. */ | |
1607 | INITIALIZE_REG_SET (phi_set); | |
1608 | mark_phi_and_copy_regs (&phi_set); | |
1609 | ||
1610 | /* Compute conflicts. */ | |
1611 | conflicts = conflict_graph_compute (&phi_set, p); | |
1612 | ||
1613 | /* FIXME: Better would be to process most frequently executed | |
1614 | blocks first, so that most frequently executed copies would | |
1615 | be more likely to be removed by register coalescing. But any | |
1616 | order will generate correct, if non-optimal, results. */ | |
1617 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1618 | { | |
1619 | changed += coalesce_regs_in_copies (bb, p, conflicts); | |
1620 | changed += coalesce_regs_in_successor_phi_nodes (bb, p, conflicts); | |
1621 | } | |
1622 | ||
1623 | conflict_graph_delete (conflicts); | |
1624 | } | |
1625 | while (changed > 0); | |
1626 | ||
1627 | return p; | |
1628 | } | |
1629 | ||
1630 | /* Mark the regs in a phi node. PTR is a phi expression or one of its | |
1631 | components (a REG or a CONST_INT). DATA is a reg set in which to | |
1632 | set all regs. Called from for_each_rtx. */ | |
1633 | ||
1634 | static int | |
1635 | mark_reg_in_phi (ptr, data) | |
1636 | rtx *ptr; | |
1637 | void *data; | |
1638 | { | |
1639 | rtx expr = *ptr; | |
1640 | regset set = (regset) data; | |
1641 | ||
1642 | switch (GET_CODE (expr)) | |
1643 | { | |
1644 | case REG: | |
1645 | SET_REGNO_REG_SET (set, REGNO (expr)); | |
1646 | /* Fall through. */ | |
1647 | case CONST_INT: | |
1648 | case PHI: | |
1649 | return 0; | |
1650 | default: | |
1651 | abort (); | |
1652 | } | |
1653 | } | |
1654 | ||
1655 | /* Mark in PHI_SET all pseudos that are used in a phi node -- either | |
1656 | set from a phi expression, or used as an argument in one. Also | |
1657 | mark regs that are the source or target of a reg copy. Uses | |
1658 | ssa_definition. */ | |
1659 | ||
1660 | static void | |
1661 | mark_phi_and_copy_regs (phi_set) | |
1662 | regset phi_set; | |
1663 | { | |
1664 | int reg; | |
1665 | ||
1666 | /* Scan the definitions of all regs. */ | |
1667 | for (reg = VARRAY_SIZE (ssa_definition); | |
1668 | --reg >= FIRST_PSEUDO_REGISTER; | |
1669 | ) | |
1670 | { | |
1671 | rtx insn = VARRAY_RTX (ssa_definition, reg); | |
1672 | rtx pattern; | |
1673 | rtx src; | |
1674 | ||
1675 | if (insn == NULL) | |
1676 | continue; | |
1677 | pattern = PATTERN (insn); | |
1678 | /* Sometimes we get PARALLEL insns. These aren't phi nodes or | |
1679 | copies. */ | |
1680 | if (GET_CODE (pattern) != SET) | |
1681 | continue; | |
1682 | src = SET_SRC (pattern); | |
1683 | ||
1684 | if (GET_CODE (src) == REG) | |
1685 | { | |
1686 | /* It's a reg copy. */ | |
1687 | SET_REGNO_REG_SET (phi_set, reg); | |
1688 | SET_REGNO_REG_SET (phi_set, REGNO (src)); | |
1689 | } | |
1690 | else if (GET_CODE (src) == PHI) | |
1691 | { | |
1692 | /* It's a phi node. Mark the reg being set. */ | |
1693 | SET_REGNO_REG_SET (phi_set, reg); | |
1694 | /* Mark the regs used in the phi function. */ | |
1695 | for_each_rtx (&src, mark_reg_in_phi, phi_set); | |
1696 | } | |
1697 | /* ... else nothing to do. */ | |
1698 | } | |
1699 | } | |
d9d4fb43 AS |
1700 | |
1701 | /* Rename regs in insn PTR that are equivalent. DATA is the register | |
1702 | partition which specifies equivalences. */ | |
1703 | ||
1704 | static int | |
1705 | rename_equivalent_regs_in_insn (ptr, data) | |
1706 | rtx *ptr; | |
1707 | void* data; | |
1708 | { | |
1709 | rtx x = *ptr; | |
1710 | partition reg_partition = (partition) data; | |
1711 | ||
1712 | if (x == NULL_RTX) | |
1713 | return 0; | |
1714 | ||
1715 | switch (GET_CODE (x)) | |
1716 | { | |
1717 | case SET: | |
1718 | { | |
1719 | rtx *destp = &SET_DEST (x); | |
1720 | rtx dest = SET_DEST (x); | |
1721 | ||
1722 | /* Subregs at word 0 are interesting. Subregs at word != 0 are | |
1723 | presumed to be part of a contiguous multi-word set sequence. */ | |
1724 | while (GET_CODE (dest) == SUBREG | |
1725 | && SUBREG_WORD (dest) == 0) | |
1726 | { | |
1727 | destp = &SUBREG_REG (dest); | |
1728 | dest = SUBREG_REG (dest); | |
1729 | } | |
1730 | ||
1731 | if (GET_CODE (dest) == REG | |
1732 | && REGNO (dest) >= FIRST_PSEUDO_REGISTER) | |
1733 | { | |
1734 | /* Got a pseudo; replace it. */ | |
1735 | int regno = REGNO (dest); | |
1736 | int new_regno = partition_find (reg_partition, regno); | |
1737 | if (regno != new_regno) | |
4e872036 | 1738 | *destp = regno_reg_rtx[new_regno]; |
d9d4fb43 AS |
1739 | |
1740 | for_each_rtx (&SET_SRC (x), | |
1741 | rename_equivalent_regs_in_insn, | |
1742 | data); | |
1743 | return -1; | |
1744 | } | |
1745 | ||
1746 | /* Otherwise, this was not an interesting destination. Continue | |
1747 | on, marking uses as normal. */ | |
1748 | return 0; | |
1749 | } | |
1750 | ||
1751 | case REG: | |
1752 | if (REGNO (x) >= FIRST_PSEUDO_REGISTER) | |
1753 | { | |
1754 | int regno = REGNO (x); | |
1755 | int new_regno = partition_find (reg_partition, regno); | |
1756 | if (regno != new_regno) | |
1757 | { | |
1758 | rtx new_reg = regno_reg_rtx[new_regno]; | |
1759 | if (GET_MODE (x) != GET_MODE (new_reg)) | |
1760 | abort (); | |
1761 | *ptr = new_reg; | |
1762 | } | |
1763 | } | |
1764 | return -1; | |
1765 | ||
1766 | case PHI: | |
1767 | /* No need to rename the phi nodes. We'll check equivalence | |
1768 | when inserting copies. */ | |
1769 | return -1; | |
1770 | ||
1771 | default: | |
1772 | /* Anything else, continue traversing. */ | |
1773 | return 0; | |
1774 | } | |
1775 | } | |
1776 | ||
d9d4fb43 AS |
1777 | /* Rename regs that are equivalent in REG_PARTITION. */ |
1778 | ||
1779 | static void | |
1780 | rename_equivalent_regs (reg_partition) | |
1781 | partition reg_partition; | |
1782 | { | |
1783 | int bb; | |
1784 | ||
1785 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1786 | { | |
1787 | basic_block b = BASIC_BLOCK (bb); | |
1788 | rtx next = b->head; | |
1789 | rtx last = b->end; | |
1790 | rtx insn; | |
1791 | ||
1792 | do | |
1793 | { | |
1794 | insn = next; | |
1795 | if (GET_RTX_CLASS (GET_CODE (insn)) == 'i') | |
1796 | { | |
1797 | for_each_rtx (&PATTERN (insn), | |
1798 | rename_equivalent_regs_in_insn, | |
1799 | reg_partition); | |
1800 | for_each_rtx (®_NOTES (insn), | |
1801 | rename_equivalent_regs_in_insn, | |
1802 | reg_partition); | |
1803 | } | |
1804 | ||
1805 | next = NEXT_INSN (insn); | |
1806 | } | |
1807 | while (insn != last); | |
1808 | } | |
1809 | } | |
1810 | ||
d9d4fb43 AS |
1811 | /* The main entry point for moving from SSA. */ |
1812 | ||
1813 | void | |
1814 | convert_from_ssa() | |
1815 | { | |
1816 | int bb; | |
1817 | partition reg_partition; | |
4e872036 AS |
1818 | rtx insns = get_insns (); |
1819 | ||
1820 | /* We need up-to-date life information. */ | |
1821 | find_basic_blocks (insns, max_reg_num (), NULL); | |
1822 | life_analysis (insns, max_reg_num (), NULL, 0); | |
1823 | ||
1824 | /* Figure out which regs in copies and phi nodes don't conflict and | |
1825 | therefore can be coalesced. */ | |
1826 | if (conservative_reg_partition) | |
1827 | reg_partition = compute_conservative_reg_partition (); | |
1828 | else | |
1829 | reg_partition = compute_coalesced_reg_partition (); | |
1830 | ||
d9d4fb43 AS |
1831 | rename_equivalent_regs (reg_partition); |
1832 | ||
1833 | /* Eliminate the PHI nodes. */ | |
1834 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1835 | { | |
1836 | basic_block b = BASIC_BLOCK (bb); | |
1837 | edge e; | |
1838 | ||
1839 | for (e = b->pred; e; e = e->pred_next) | |
1840 | if (e->src != ENTRY_BLOCK_PTR) | |
1841 | eliminate_phi (e, reg_partition); | |
1842 | } | |
1843 | ||
1844 | partition_delete (reg_partition); | |
1845 | ||
1846 | /* Actually delete the PHI nodes. */ | |
1847 | for (bb = n_basic_blocks; --bb >= 0; ) | |
1848 | { | |
1849 | rtx insn = BLOCK_HEAD (bb); | |
1850 | int start = (GET_CODE (insn) != CODE_LABEL); | |
1851 | ||
1852 | if (! start) | |
1853 | insn = next_nonnote_insn (insn); | |
1854 | while (PHI_NODE_P (insn)) | |
1855 | { | |
4e872036 AS |
1856 | /* If a phi node is the last insn in the block, there must |
1857 | have been nothing else. Set the block end to the block | |
1858 | head. */ | |
1859 | if (insn == BLOCK_END (bb)) | |
1860 | BLOCK_END (bb) = BLOCK_HEAD (bb); | |
d9d4fb43 AS |
1861 | insn = delete_insn (insn); |
1862 | if (GET_CODE (insn) == NOTE) | |
1863 | insn = next_nonnote_insn (insn); | |
1864 | } | |
1865 | if (start) | |
1866 | BLOCK_HEAD (bb) = insn; | |
1867 | } | |
1868 | ||
1869 | /* Commit all the copy nodes needed to convert out of SSA form. */ | |
1870 | commit_edge_insertions (); | |
1871 | ||
4e872036 AS |
1872 | in_ssa_form = 0; |
1873 | ||
d9d4fb43 AS |
1874 | count_or_remove_death_notes (NULL, 1); |
1875 | } | |
4e872036 AS |
1876 | |
1877 | /* Scan phi nodes in successors to BB. For each such phi node that | |
1878 | has a phi alternative value corresponding to BB, invoke FN. FN | |
1879 | is passed the entire phi node insn, the regno of the set | |
1880 | destination, the regno of the phi argument corresponding to BB, | |
1881 | and DATA. | |
1882 | ||
1883 | If FN ever returns non-zero, stops immediately and returns this | |
1884 | value. Otherwise, returns zero. */ | |
1885 | ||
1886 | int | |
1887 | for_each_successor_phi (bb, fn, data) | |
1888 | int bb; | |
1889 | successor_phi_fn fn; | |
1890 | void *data; | |
1891 | { | |
1892 | basic_block block; | |
1893 | edge e; | |
1894 | ||
1895 | if (bb == EXIT_BLOCK) | |
1896 | return 0; | |
1897 | else if (bb == ENTRY_BLOCK) | |
1898 | block = ENTRY_BLOCK_PTR; | |
1899 | else | |
1900 | block = BASIC_BLOCK (bb); | |
1901 | ||
1902 | /* Scan outgoing edges. */ | |
1903 | for (e = block->succ; e != NULL; e = e->succ_next) | |
1904 | { | |
1905 | rtx insn; | |
1906 | ||
1907 | basic_block successor = e->dest; | |
1908 | if (successor->index == ENTRY_BLOCK | |
1909 | || successor->index == EXIT_BLOCK) | |
1910 | continue; | |
1911 | ||
1912 | /* Advance to the first non-label insn of the successor block. */ | |
1913 | insn = successor->head; | |
1914 | while (insn != NULL | |
1915 | && (GET_CODE (insn) == CODE_LABEL | |
1916 | || GET_CODE (insn) == NOTE)) | |
1917 | insn = NEXT_INSN (insn); | |
1918 | ||
1919 | if (insn == NULL) | |
1920 | continue; | |
1921 | ||
1922 | /* Scan phi nodes in the successor. */ | |
1923 | for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn)) | |
1924 | { | |
1925 | int result; | |
1926 | rtx phi_set = PATTERN (insn); | |
1927 | rtx *alternative = phi_alternative (phi_set, block->index); | |
1928 | rtx phi_src; | |
1929 | ||
1930 | /* This phi function may not have an alternative | |
1931 | corresponding to the incoming edge, indicating the | |
1932 | assigned variable is not defined along the edge. */ | |
1933 | if (alternative == NULL) | |
1934 | continue; | |
1935 | phi_src = *alternative; | |
1936 | ||
1937 | /* Invoke the callback. */ | |
1938 | result = (*fn) (insn, REGNO (SET_DEST (phi_set)), | |
1939 | REGNO (phi_src), data); | |
1940 | ||
1941 | /* Terminate if requested. */ | |
1942 | if (result != 0) | |
1943 | return result; | |
1944 | } | |
1945 | } | |
1946 | ||
1947 | return 0; | |
1948 | } |