OSDN Git Service

54c36ddc7e3adafe0060f00e7f0b2670db16ef3a
[pf3gnuchains/gcc-fork.git] / gcc / ssa.c
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 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.
10
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.
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 the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 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 unsigned 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 ((void));
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 (&REG_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           unsigned 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));
767   bzero ((char *) ssa_rename_to, nregs * sizeof(rtx));
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 (&REG_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 }