Daily bump.
[official-gcc.git] / gcc / ssa.c
blobc97b35c35883850397a94bd110b48f5c81d1ad3e
1 /* Static Single Assignment conversion routines for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA. */
21 /* References:
23 Building an Optimizing Compiler
24 Robert Morgan
25 Butterworth-Heinemann, 1998
27 Static Single Assignment Construction
28 Preston Briggs, Tim Harvey, Taylor Simpson
29 Technical Report, Rice University, 1995
30 ftp://ftp.cs.rice.edu/public/preston/optimizer/SSA.ps.gz. */
32 #include "config.h"
33 #include "system.h"
35 #include "rtl.h"
36 #include "expr.h"
37 #include "varray.h"
38 #include "partition.h"
39 #include "sbitmap.h"
40 #include "hashtab.h"
41 #include "regs.h"
42 #include "hard-reg-set.h"
43 #include "flags.h"
44 #include "function.h"
45 #include "real.h"
46 #include "insn-config.h"
47 #include "recog.h"
48 #include "basic-block.h"
49 #include "output.h"
50 #include "ssa.h"
52 /* TODO:
54 Handle subregs better, maybe. For now, if a reg that's set in a
55 subreg expression is duplicated going into SSA form, an extra copy
56 is inserted first that copies the entire reg into the duplicate, so
57 that the other bits are preserved. This isn't strictly SSA, since
58 at least part of the reg is assigned in more than one place (though
59 they are adjacent).
61 ??? What to do about strict_low_part. Probably I'll have to split
62 them out of their current instructions first thing.
64 Actually the best solution may be to have a kind of "mid-level rtl"
65 in which the RTL encodes exactly what we want, without exposing a
66 lot of niggling processor details. At some later point we lower
67 the representation, calling back into optabs to finish any necessary
68 expansion. */
70 /* All pseudo-registers and select hard registers are converted to SSA
71 form. When converting out of SSA, these select hard registers are
72 guaranteed to be mapped to their original register number. Each
73 machine's .h file should define CONVERT_HARD_REGISTER_TO_SSA_P
74 indicating which hard registers should be converted.
76 When converting out of SSA, temporaries for all registers are
77 partitioned. The partition is checked to ensure that all uses of
78 the same hard register in the same machine mode are in the same
79 class. */
81 /* If conservative_reg_partition is non-zero, use a conservative
82 register partitioning algorithm (which leaves more regs after
83 emerging from SSA) instead of the coalescing one. This is being
84 left in for a limited time only, as a debugging tool until the
85 coalescing algorithm is validated. */
87 static int conservative_reg_partition;
89 /* This flag is set when the CFG is in SSA form. */
90 int in_ssa_form = 0;
92 /* Element I is the single instruction that sets register I. */
93 varray_type ssa_definition;
95 /* Element I-PSEUDO is the normal register that originated the ssa
96 register in question. */
97 varray_type ssa_rename_from;
99 /* Element I is the normal register that originated the ssa
100 register in question.
102 A hash table stores the (register, rtl) pairs. These are each
103 xmalloc'ed and deleted when the hash table is destroyed. */
104 htab_t ssa_rename_from_ht;
106 /* The running target ssa register for a given pseudo register.
107 (Pseudo registers appear in only one mode.) */
108 static rtx *ssa_rename_to_pseudo;
109 /* Similar, but for hard registers. A hard register can appear in
110 many modes, so we store an equivalent pseudo for each of the
111 modes. */
112 static rtx ssa_rename_to_hard[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
114 /* ssa_rename_from maps pseudo registers to the original corresponding
115 RTL. It is implemented as using a hash table. */
117 typedef struct {
118 unsigned int reg;
119 rtx original;
120 } ssa_rename_from_pair;
122 struct ssa_rename_from_hash_table_data {
123 sbitmap canonical_elements;
124 partition reg_partition;
127 static void ssa_rename_from_initialize
128 PARAMS ((void));
129 static rtx ssa_rename_from_lookup
130 PARAMS ((int reg));
131 static unsigned int original_register
132 PARAMS ((unsigned int regno));
133 static void ssa_rename_from_insert
134 PARAMS ((unsigned int reg, rtx r));
135 static void ssa_rename_from_free
136 PARAMS ((void));
137 typedef int (*srf_trav) PARAMS ((int regno, rtx r, sbitmap canonical_elements, partition reg_partition));
138 static void ssa_rename_from_traverse
139 PARAMS ((htab_trav callback_function, sbitmap canonical_elements, partition reg_partition));
140 /*static Avoid warnign message. */ void ssa_rename_from_print
141 PARAMS ((void));
142 static int ssa_rename_from_print_1
143 PARAMS ((void **slot, void *data));
144 static hashval_t ssa_rename_from_hash_function
145 PARAMS ((const void * srfp));
146 static int ssa_rename_from_equal
147 PARAMS ((const void *srfp1, const void *srfp2));
148 static void ssa_rename_from_delete
149 PARAMS ((void *srfp));
151 static rtx ssa_rename_to_lookup
152 PARAMS ((rtx reg));
153 static void ssa_rename_to_insert
154 PARAMS ((rtx reg, rtx r));
156 /* The number of registers that were live on entry to the SSA routines. */
157 static unsigned int ssa_max_reg_num;
159 /* Local function prototypes. */
161 struct rename_context;
163 static inline rtx * phi_alternative
164 PARAMS ((rtx, int));
165 static void compute_dominance_frontiers_1
166 PARAMS ((sbitmap *frontiers, int *idom, int bb, sbitmap done));
167 static void find_evaluations_1
168 PARAMS ((rtx dest, rtx set, void *data));
169 static void find_evaluations
170 PARAMS ((sbitmap *evals, int nregs));
171 static void compute_iterated_dominance_frontiers
172 PARAMS ((sbitmap *idfs, sbitmap *frontiers, sbitmap *evals, int nregs));
173 static void insert_phi_node
174 PARAMS ((int regno, int b));
175 static void insert_phi_nodes
176 PARAMS ((sbitmap *idfs, sbitmap *evals, int nregs));
177 static void create_delayed_rename
178 PARAMS ((struct rename_context *, rtx *));
179 static void apply_delayed_renames
180 PARAMS ((struct rename_context *));
181 static int rename_insn_1
182 PARAMS ((rtx *ptr, void *data));
183 static void rename_block
184 PARAMS ((int b, int *idom));
185 static void rename_registers
186 PARAMS ((int nregs, int *idom));
188 static inline int ephi_add_node
189 PARAMS ((rtx reg, rtx *nodes, int *n_nodes));
190 static int * ephi_forward
191 PARAMS ((int t, sbitmap visited, sbitmap *succ, int *tstack));
192 static void ephi_backward
193 PARAMS ((int t, sbitmap visited, sbitmap *pred, rtx *nodes));
194 static void ephi_create
195 PARAMS ((int t, sbitmap visited, sbitmap *pred, sbitmap *succ, rtx *nodes));
196 static void eliminate_phi
197 PARAMS ((edge e, partition reg_partition));
198 static int make_regs_equivalent_over_bad_edges
199 PARAMS ((int bb, partition reg_partition));
201 /* These are used only in the conservative register partitioning
202 algorithms. */
203 static int make_equivalent_phi_alternatives_equivalent
204 PARAMS ((int bb, partition reg_partition));
205 static partition compute_conservative_reg_partition
206 PARAMS ((void));
207 static int record_canonical_element_1
208 PARAMS ((void **srfp, void *data));
209 static int check_hard_regs_in_partition
210 PARAMS ((partition reg_partition));
211 static int rename_equivalent_regs_in_insn
212 PARAMS ((rtx *ptr, void *data));
214 /* These are used in the register coalescing algorithm. */
215 static int coalesce_if_unconflicting
216 PARAMS ((partition p, conflict_graph conflicts, int reg1, int reg2));
217 static int coalesce_regs_in_copies
218 PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
219 static int coalesce_reg_in_phi
220 PARAMS ((rtx, int dest_regno, int src_regno, void *data));
221 static int coalesce_regs_in_successor_phi_nodes
222 PARAMS ((basic_block bb, partition p, conflict_graph conflicts));
223 static partition compute_coalesced_reg_partition
224 PARAMS ((void));
225 static int mark_reg_in_phi
226 PARAMS ((rtx *ptr, void *data));
227 static void mark_phi_and_copy_regs
228 PARAMS ((regset phi_set));
230 static int rename_equivalent_regs_in_insn
231 PARAMS ((rtx *ptr, void *data));
232 static void rename_equivalent_regs
233 PARAMS ((partition reg_partition));
235 /* Deal with hard registers. */
236 static int conflicting_hard_regs_p
237 PARAMS ((int reg1, int reg2));
239 /* ssa_rename_to maps registers and machine modes to SSA pseudo registers. */
241 /* Find the register associated with REG in the indicated mode. */
243 static rtx
244 ssa_rename_to_lookup (reg)
245 rtx reg;
247 if (!HARD_REGISTER_P (reg))
248 return ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER];
249 else
250 return ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)];
253 /* Store a new value mapping REG to R in ssa_rename_to. */
255 static void
256 ssa_rename_to_insert(reg, r)
257 rtx reg;
258 rtx r;
260 if (!HARD_REGISTER_P (reg))
261 ssa_rename_to_pseudo[REGNO (reg) - FIRST_PSEUDO_REGISTER] = r;
262 else
263 ssa_rename_to_hard[REGNO (reg)][GET_MODE (reg)] = r;
266 /* Prepare ssa_rename_from for use. */
268 static void
269 ssa_rename_from_initialize ()
271 /* We use an arbitrary initial hash table size of 64. */
272 ssa_rename_from_ht = htab_create (64,
273 &ssa_rename_from_hash_function,
274 &ssa_rename_from_equal,
275 &ssa_rename_from_delete);
278 /* Find the REG entry in ssa_rename_from. Return NULL_RTX if no entry is
279 found. */
281 static rtx
282 ssa_rename_from_lookup (reg)
283 int reg;
285 ssa_rename_from_pair srfp;
286 ssa_rename_from_pair *answer;
287 srfp.reg = reg;
288 srfp.original = NULL_RTX;
289 answer = (ssa_rename_from_pair *)
290 htab_find_with_hash (ssa_rename_from_ht, (void *) &srfp, reg);
291 return (answer == 0 ? NULL_RTX : answer->original);
294 /* Find the number of the original register specified by REGNO. If
295 the register is a pseudo, return the original register's number.
296 Otherwise, return this register number REGNO. */
298 static unsigned int
299 original_register (regno)
300 unsigned int regno;
302 rtx original_rtx = ssa_rename_from_lookup (regno);
303 return original_rtx != NULL_RTX ? REGNO (original_rtx) : regno;
306 /* Add mapping from R to REG to ssa_rename_from even if already present. */
308 static void
309 ssa_rename_from_insert (reg, r)
310 unsigned int reg;
311 rtx r;
313 void **slot;
314 ssa_rename_from_pair *srfp = xmalloc (sizeof (ssa_rename_from_pair));
315 srfp->reg = reg;
316 srfp->original = r;
317 slot = htab_find_slot_with_hash (ssa_rename_from_ht, (const void *) srfp,
318 reg, INSERT);
319 if (*slot != 0)
320 free ((void *) *slot);
321 *slot = srfp;
324 /* Apply the CALLBACK_FUNCTION to each element in ssa_rename_from.
325 CANONICAL_ELEMENTS and REG_PARTITION pass data needed by the only
326 current use of this function. */
328 static void
329 ssa_rename_from_traverse (callback_function,
330 canonical_elements, reg_partition)
331 htab_trav callback_function;
332 sbitmap canonical_elements;
333 partition reg_partition;
335 struct ssa_rename_from_hash_table_data srfhd;
336 srfhd.canonical_elements = canonical_elements;
337 srfhd.reg_partition = reg_partition;
338 htab_traverse (ssa_rename_from_ht, callback_function, (void *) &srfhd);
341 /* Destroy ssa_rename_from. */
343 static void
344 ssa_rename_from_free ()
346 htab_delete (ssa_rename_from_ht);
349 /* Print the contents of ssa_rename_from. */
351 /* static Avoid erroneous error message. */
352 void
353 ssa_rename_from_print ()
355 printf ("ssa_rename_from's hash table contents:\n");
356 htab_traverse (ssa_rename_from_ht, &ssa_rename_from_print_1, NULL);
359 /* Print the contents of the hash table entry SLOT, passing the unused
360 sttribute DATA. Used as a callback function with htab_traverse (). */
362 static int
363 ssa_rename_from_print_1 (slot, data)
364 void **slot;
365 void *data ATTRIBUTE_UNUSED;
367 ssa_rename_from_pair * p = *slot;
368 printf ("ssa_rename_from maps pseudo %i to original %i.\n",
369 p->reg, REGNO (p->original));
370 return 1;
373 /* Given a hash entry SRFP, yield a hash value. */
375 static hashval_t
376 ssa_rename_from_hash_function (srfp)
377 const void *srfp;
379 return ((const ssa_rename_from_pair *) srfp)->reg;
382 /* Test whether two hash table entries SRFP1 and SRFP2 are equal. */
384 static int
385 ssa_rename_from_equal (srfp1, srfp2)
386 const void *srfp1;
387 const void *srfp2;
389 return ssa_rename_from_hash_function (srfp1) ==
390 ssa_rename_from_hash_function (srfp2);
393 /* Delete the hash table entry SRFP. */
395 static void
396 ssa_rename_from_delete (srfp)
397 void *srfp;
399 free (srfp);
402 /* Given the SET of a PHI node, return the address of the alternative
403 for predecessor block C. */
405 static inline rtx *
406 phi_alternative (set, c)
407 rtx set;
408 int c;
410 rtvec phi_vec = XVEC (SET_SRC (set), 0);
411 int v;
413 for (v = GET_NUM_ELEM (phi_vec) - 2; v >= 0; v -= 2)
414 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
415 return &RTVEC_ELT (phi_vec, v);
417 return NULL;
420 /* Given the SET of a phi node, remove the alternative for predecessor
421 block C. Return non-zero on success, or zero if no alternative is
422 found for C. */
425 remove_phi_alternative (set, block)
426 rtx set;
427 basic_block block;
429 rtvec phi_vec = XVEC (SET_SRC (set), 0);
430 int num_elem = GET_NUM_ELEM (phi_vec);
431 int v, c;
433 c = block->index;
434 for (v = num_elem - 2; v >= 0; v -= 2)
435 if (INTVAL (RTVEC_ELT (phi_vec, v + 1)) == c)
437 if (v < num_elem - 2)
439 RTVEC_ELT (phi_vec, v) = RTVEC_ELT (phi_vec, num_elem - 2);
440 RTVEC_ELT (phi_vec, v + 1) = RTVEC_ELT (phi_vec, num_elem - 1);
442 PUT_NUM_ELEM (phi_vec, num_elem - 2);
443 return 1;
446 return 0;
449 /* For all registers, find all blocks in which they are set.
451 This is the transform of what would be local kill information that
452 we ought to be getting from flow. */
454 static sbitmap *fe_evals;
455 static int fe_current_bb;
457 static void
458 find_evaluations_1 (dest, set, data)
459 rtx dest;
460 rtx set ATTRIBUTE_UNUSED;
461 void *data ATTRIBUTE_UNUSED;
463 if (GET_CODE (dest) == REG
464 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
465 SET_BIT (fe_evals[REGNO (dest)], fe_current_bb);
468 static void
469 find_evaluations (evals, nregs)
470 sbitmap *evals;
471 int nregs;
473 int bb;
475 sbitmap_vector_zero (evals, nregs);
476 fe_evals = evals;
478 for (bb = n_basic_blocks; --bb >= 0; )
480 rtx p, last;
482 fe_current_bb = bb;
483 p = BLOCK_HEAD (bb);
484 last = BLOCK_END (bb);
485 while (1)
487 if (INSN_P (p))
488 note_stores (PATTERN (p), find_evaluations_1, NULL);
490 if (p == last)
491 break;
492 p = NEXT_INSN (p);
497 /* Computing the Dominance Frontier:
499 As decribed in Morgan, section 3.5, this may be done simply by
500 walking the dominator tree bottom-up, computing the frontier for
501 the children before the parent. When considering a block B,
502 there are two cases:
504 (1) A flow graph edge leaving B that does not lead to a child
505 of B in the dominator tree must be a block that is either equal
506 to B or not dominated by B. Such blocks belong in the frontier
507 of B.
509 (2) Consider a block X in the frontier of one of the children C
510 of B. If X is not equal to B and is not dominated by B, it
511 is in the frontier of B.
514 static void
515 compute_dominance_frontiers_1 (frontiers, idom, bb, done)
516 sbitmap *frontiers;
517 int *idom;
518 int bb;
519 sbitmap done;
521 basic_block b = BASIC_BLOCK (bb);
522 edge e;
523 int c;
525 SET_BIT (done, bb);
526 sbitmap_zero (frontiers[bb]);
528 /* Do the frontier of the children first. Not all children in the
529 dominator tree (blocks dominated by this one) are children in the
530 CFG, so check all blocks. */
531 for (c = 0; c < n_basic_blocks; ++c)
532 if (idom[c] == bb && ! TEST_BIT (done, c))
533 compute_dominance_frontiers_1 (frontiers, idom, c, done);
535 /* Find blocks conforming to rule (1) above. */
536 for (e = b->succ; e; e = e->succ_next)
538 if (e->dest == EXIT_BLOCK_PTR)
539 continue;
540 if (idom[e->dest->index] != bb)
541 SET_BIT (frontiers[bb], e->dest->index);
544 /* Find blocks conforming to rule (2). */
545 for (c = 0; c < n_basic_blocks; ++c)
546 if (idom[c] == bb)
548 int x;
549 EXECUTE_IF_SET_IN_SBITMAP (frontiers[c], 0, x,
551 if (idom[x] != bb)
552 SET_BIT (frontiers[bb], x);
557 void
558 compute_dominance_frontiers (frontiers, idom)
559 sbitmap *frontiers;
560 int *idom;
562 sbitmap done = sbitmap_alloc (n_basic_blocks);
563 sbitmap_zero (done);
565 compute_dominance_frontiers_1 (frontiers, idom, 0, done);
567 sbitmap_free (done);
570 /* Computing the Iterated Dominance Frontier:
572 This is the set of merge points for a given register.
574 This is not particularly intuitive. See section 7.1 of Morgan, in
575 particular figures 7.3 and 7.4 and the immediately surrounding text.
578 static void
579 compute_iterated_dominance_frontiers (idfs, frontiers, evals, nregs)
580 sbitmap *idfs;
581 sbitmap *frontiers;
582 sbitmap *evals;
583 int nregs;
585 sbitmap worklist;
586 int reg, passes = 0;
588 worklist = sbitmap_alloc (n_basic_blocks);
590 for (reg = 0; reg < nregs; ++reg)
592 sbitmap idf = idfs[reg];
593 int b, changed;
595 /* Start the iterative process by considering those blocks that
596 evaluate REG. We'll add their dominance frontiers to the
597 IDF, and then consider the blocks we just added. */
598 sbitmap_copy (worklist, evals[reg]);
600 /* Morgan's algorithm is incorrect here. Blocks that evaluate
601 REG aren't necessarily in REG's IDF. Start with an empty IDF. */
602 sbitmap_zero (idf);
604 /* Iterate until the worklist is empty. */
607 changed = 0;
608 passes++;
609 EXECUTE_IF_SET_IN_SBITMAP (worklist, 0, b,
611 RESET_BIT (worklist, b);
612 /* For each block on the worklist, add to the IDF all
613 blocks on its dominance frontier that aren't already
614 on the IDF. Every block that's added is also added
615 to the worklist. */
616 sbitmap_union_of_diff (worklist, worklist, frontiers[b], idf);
617 sbitmap_a_or_b (idf, idf, frontiers[b]);
618 changed = 1;
621 while (changed);
624 sbitmap_free (worklist);
626 if (rtl_dump_file)
628 fprintf (rtl_dump_file,
629 "Iterated dominance frontier: %d passes on %d regs.\n",
630 passes, nregs);
634 /* Insert the phi nodes. */
636 static void
637 insert_phi_node (regno, bb)
638 int regno, bb;
640 basic_block b = BASIC_BLOCK (bb);
641 edge e;
642 int npred, i;
643 rtvec vec;
644 rtx phi, reg;
645 rtx insn;
646 int end_p;
648 /* Find out how many predecessors there are. */
649 for (e = b->pred, npred = 0; e; e = e->pred_next)
650 if (e->src != ENTRY_BLOCK_PTR)
651 npred++;
653 /* If this block has no "interesting" preds, then there is nothing to
654 do. Consider a block that only has the entry block as a pred. */
655 if (npred == 0)
656 return;
658 /* This is the register to which the phi function will be assigned. */
659 reg = regno_reg_rtx[regno];
661 /* Construct the arguments to the PHI node. The use of pc_rtx is just
662 a placeholder; we'll insert the proper value in rename_registers. */
663 vec = rtvec_alloc (npred * 2);
664 for (e = b->pred, i = 0; e ; e = e->pred_next, i += 2)
665 if (e->src != ENTRY_BLOCK_PTR)
667 RTVEC_ELT (vec, i + 0) = pc_rtx;
668 RTVEC_ELT (vec, i + 1) = GEN_INT (e->src->index);
671 phi = gen_rtx_PHI (VOIDmode, vec);
672 phi = gen_rtx_SET (VOIDmode, reg, phi);
674 insn = first_insn_after_basic_block_note (b);
675 end_p = PREV_INSN (insn) == b->end;
676 emit_insn_before (phi, insn);
677 if (end_p)
678 b->end = PREV_INSN (insn);
681 static void
682 insert_phi_nodes (idfs, evals, nregs)
683 sbitmap *idfs;
684 sbitmap *evals ATTRIBUTE_UNUSED;
685 int nregs;
687 int reg;
689 for (reg = 0; reg < nregs; ++reg)
690 if (CONVERT_REGISTER_TO_SSA_P (reg))
692 int b;
693 EXECUTE_IF_SET_IN_SBITMAP (idfs[reg], 0, b,
695 if (REGNO_REG_SET_P (BASIC_BLOCK (b)->global_live_at_start, reg))
696 insert_phi_node (reg, b);
701 /* Rename the registers to conform to SSA.
703 This is essentially the algorithm presented in Figure 7.8 of Morgan,
704 with a few changes to reduce pattern search time in favour of a bit
705 more memory usage. */
707 /* One of these is created for each set. It will live in a list local
708 to its basic block for the duration of that block's processing. */
709 struct rename_set_data
711 struct rename_set_data *next;
712 /* This is the SET_DEST of the (first) SET that sets the REG. */
713 rtx *reg_loc;
714 /* This is what used to be at *REG_LOC. */
715 rtx old_reg;
716 /* This is the REG that will replace OLD_REG. It's set only
717 when the rename data is moved onto the DONE_RENAMES queue. */
718 rtx new_reg;
719 /* This is what to restore ssa_rename_to_lookup (old_reg) to. It is
720 usually the previous contents of ssa_rename_to_lookup (old_reg). */
721 rtx prev_reg;
722 /* This is the insn that contains all the SETs of the REG. */
723 rtx set_insn;
726 /* This struct is used to pass information to callback functions while
727 renaming registers. */
728 struct rename_context
730 struct rename_set_data *new_renames;
731 struct rename_set_data *done_renames;
732 rtx current_insn;
735 /* Queue the rename of *REG_LOC. */
736 static void
737 create_delayed_rename (c, reg_loc)
738 struct rename_context *c;
739 rtx *reg_loc;
741 struct rename_set_data *r;
742 r = (struct rename_set_data *) xmalloc (sizeof(*r));
744 if (GET_CODE (*reg_loc) != REG
745 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*reg_loc)))
746 abort ();
748 r->reg_loc = reg_loc;
749 r->old_reg = *reg_loc;
750 r->prev_reg = ssa_rename_to_lookup(r->old_reg);
751 r->set_insn = c->current_insn;
752 r->next = c->new_renames;
753 c->new_renames = r;
756 /* This is part of a rather ugly hack to allow the pre-ssa regno to be
757 reused. If, during processing, a register has not yet been touched,
758 ssa_rename_to[regno][machno] will be NULL. Now, in the course of pushing
759 and popping values from ssa_rename_to, when we would ordinarily
760 pop NULL back in, we pop RENAME_NO_RTX. We treat this exactly the
761 same as NULL, except that it signals that the original regno has
762 already been reused. */
763 #define RENAME_NO_RTX pc_rtx
765 /* Move all the entries from NEW_RENAMES onto DONE_RENAMES by
766 applying all the renames on NEW_RENAMES. */
768 static void
769 apply_delayed_renames (c)
770 struct rename_context *c;
772 struct rename_set_data *r;
773 struct rename_set_data *last_r = NULL;
775 for (r = c->new_renames; r != NULL; r = r->next)
777 int new_regno;
779 /* Failure here means that someone has a PARALLEL that sets
780 a register twice (bad!). */
781 if (ssa_rename_to_lookup (r->old_reg) != r->prev_reg)
782 abort ();
783 /* Failure here means we have changed REG_LOC before applying
784 the rename. */
785 /* For the first set we come across, reuse the original regno. */
786 if (r->prev_reg == NULL_RTX && !HARD_REGISTER_P (r->old_reg))
788 r->new_reg = r->old_reg;
789 /* We want to restore RENAME_NO_RTX rather than NULL_RTX. */
790 r->prev_reg = RENAME_NO_RTX;
792 else
793 r->new_reg = gen_reg_rtx (GET_MODE (r->old_reg));
794 new_regno = REGNO (r->new_reg);
795 ssa_rename_to_insert (r->old_reg, r->new_reg);
797 if (new_regno >= (int) ssa_definition->num_elements)
799 int new_limit = new_regno * 5 / 4;
800 VARRAY_GROW (ssa_definition, new_limit);
803 VARRAY_RTX (ssa_definition, new_regno) = r->set_insn;
804 ssa_rename_from_insert (new_regno, r->old_reg);
805 last_r = r;
807 if (last_r != NULL)
809 last_r->next = c->done_renames;
810 c->done_renames = c->new_renames;
811 c->new_renames = NULL;
815 /* Part one of the first step of rename_block, called through for_each_rtx.
816 Mark pseudos that are set for later update. Transform uses of pseudos. */
818 static int
819 rename_insn_1 (ptr, data)
820 rtx *ptr;
821 void *data;
823 rtx x = *ptr;
824 struct rename_context *context = data;
826 if (x == NULL_RTX)
827 return 0;
829 switch (GET_CODE (x))
831 case SET:
833 rtx *destp = &SET_DEST (x);
834 rtx dest = SET_DEST (x);
836 /* An assignment to a paradoxical SUBREG does not read from
837 the destination operand, and thus does not need to be
838 wrapped into a SEQUENCE when translating into SSA form.
839 We merely strip off the SUBREG and proceed normally for
840 this case. */
841 if (GET_CODE (dest) == SUBREG
842 && (GET_MODE_SIZE (GET_MODE (dest))
843 > GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))))
844 && GET_CODE (SUBREG_REG (dest)) == REG
845 && CONVERT_REGISTER_TO_SSA_P (REGNO (SUBREG_REG (dest))))
847 destp = &XEXP (dest, 0);
848 dest = XEXP (dest, 0);
851 /* Some SETs also use the REG specified in their LHS.
852 These can be detected by the presence of
853 STRICT_LOW_PART, SUBREG, SIGN_EXTRACT, and ZERO_EXTRACT
854 in the LHS. Handle these by changing
855 (set (subreg (reg foo)) ...)
856 into
857 (sequence [(set (reg foo_1) (reg foo))
858 (set (subreg (reg foo_1)) ...)])
860 FIXME: Much of the time this is too much. For some constructs
861 we know that the output register is strictly an output
862 (paradoxical SUBREGs and some libcalls for example).
864 For those cases we are better off not making the false
865 dependency. */
866 if (GET_CODE (dest) == STRICT_LOW_PART
867 || GET_CODE (dest) == SUBREG
868 || GET_CODE (dest) == SIGN_EXTRACT
869 || GET_CODE (dest) == ZERO_EXTRACT)
871 rtx i, reg;
872 reg = dest;
874 while (GET_CODE (reg) == STRICT_LOW_PART
875 || GET_CODE (reg) == SUBREG
876 || GET_CODE (reg) == SIGN_EXTRACT
877 || GET_CODE (reg) == ZERO_EXTRACT)
878 reg = XEXP (reg, 0);
880 if (GET_CODE (reg) == REG
881 && CONVERT_REGISTER_TO_SSA_P (REGNO (reg)))
883 /* Generate (set reg reg), and do renaming on it so
884 that it becomes (set reg_1 reg_0), and we will
885 replace reg with reg_1 in the SUBREG. */
887 struct rename_set_data *saved_new_renames;
888 saved_new_renames = context->new_renames;
889 context->new_renames = NULL;
890 i = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
891 for_each_rtx (&i, rename_insn_1, data);
892 apply_delayed_renames (context);
893 context->new_renames = saved_new_renames;
896 else if (GET_CODE (dest) == REG
897 && CONVERT_REGISTER_TO_SSA_P (REGNO (dest)))
899 /* We found a genuine set of an interesting register. Tag
900 it so that we can create a new name for it after we finish
901 processing this insn. */
903 create_delayed_rename (context, destp);
905 /* Since we do not wish to (directly) traverse the
906 SET_DEST, recurse through for_each_rtx for the SET_SRC
907 and return. */
908 if (GET_CODE (x) == SET)
909 for_each_rtx (&SET_SRC (x), rename_insn_1, data);
910 return -1;
913 /* Otherwise, this was not an interesting destination. Continue
914 on, marking uses as normal. */
915 return 0;
918 case REG:
919 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)) &&
920 REGNO (x) < ssa_max_reg_num)
922 rtx new_reg = ssa_rename_to_lookup (x);
924 if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
926 if (GET_MODE (x) != GET_MODE (new_reg))
927 abort ();
928 *ptr = new_reg;
930 /* Else this is a use before a set. Warn? */
932 return -1;
934 case CLOBBER:
935 /* There is considerable debate on how CLOBBERs ought to be
936 handled in SSA. For now, we're keeping the CLOBBERs, which
937 means that we don't really have SSA form. There are a couple
938 of proposals for how to fix this problem, but neither is
939 implemented yet. */
941 rtx dest = XCEXP (x, 0, CLOBBER);
942 if (REG_P (dest))
944 if (CONVERT_REGISTER_TO_SSA_P (REGNO (dest))
945 && REGNO (dest) < ssa_max_reg_num)
947 rtx new_reg = ssa_rename_to_lookup (dest);
948 if (new_reg != NULL_RTX && new_reg != RENAME_NO_RTX)
949 XCEXP (x, 0, CLOBBER) = new_reg;
951 /* Stop traversing. */
952 return -1;
954 else
955 /* Continue traversing. */
956 return 0;
959 case PHI:
960 /* Never muck with the phi. We do that elsewhere, special-like. */
961 return -1;
963 default:
964 /* Anything else, continue traversing. */
965 return 0;
969 static void
970 rename_block (bb, idom)
971 int bb;
972 int *idom;
974 basic_block b = BASIC_BLOCK (bb);
975 edge e;
976 rtx insn, next, last;
977 struct rename_set_data *set_data = NULL;
978 int c;
980 /* Step One: Walk the basic block, adding new names for sets and
981 replacing uses. */
983 next = b->head;
984 last = b->end;
987 insn = next;
988 if (INSN_P (insn))
990 struct rename_context context;
991 context.done_renames = set_data;
992 context.new_renames = NULL;
993 context.current_insn = insn;
995 start_sequence ();
996 for_each_rtx (&PATTERN (insn), rename_insn_1, &context);
997 for_each_rtx (&REG_NOTES (insn), rename_insn_1, &context);
999 /* Sometimes, we end up with a sequence of insns that
1000 SSA needs to treat as a single insn. Wrap these in a
1001 SEQUENCE. (Any notes now get attached to the SEQUENCE,
1002 not to the old version inner insn.) */
1003 if (get_insns () != NULL_RTX)
1005 rtx seq;
1006 int i;
1008 emit (PATTERN (insn));
1009 seq = gen_sequence ();
1010 /* We really want a SEQUENCE of SETs, not a SEQUENCE
1011 of INSNs. */
1012 for (i = 0; i < XVECLEN (seq, 0); i++)
1013 XVECEXP (seq, 0, i) = PATTERN (XVECEXP (seq, 0, i));
1014 PATTERN (insn) = seq;
1016 end_sequence ();
1018 apply_delayed_renames (&context);
1019 set_data = context.done_renames;
1022 next = NEXT_INSN (insn);
1024 while (insn != last);
1026 /* Step Two: Update the phi nodes of this block's successors. */
1028 for (e = b->succ; e; e = e->succ_next)
1030 if (e->dest == EXIT_BLOCK_PTR)
1031 continue;
1033 insn = first_insn_after_basic_block_note (e->dest);
1035 while (PHI_NODE_P (insn))
1037 rtx phi = PATTERN (insn);
1038 rtx reg;
1040 /* Find out which of our outgoing registers this node is
1041 intended to replace. Note that if this is not the first PHI
1042 node to have been created for this register, we have to
1043 jump through rename links to figure out which register
1044 we're talking about. This can easily be recognized by
1045 noting that the regno is new to this pass. */
1046 reg = SET_DEST (phi);
1047 if (REGNO (reg) >= ssa_max_reg_num)
1048 reg = ssa_rename_from_lookup (REGNO (reg));
1049 if (reg == NULL_RTX)
1050 abort ();
1051 reg = ssa_rename_to_lookup (reg);
1053 /* It is possible for the variable to be uninitialized on
1054 edges in. Reduce the arity of the PHI so that we don't
1055 consider those edges. */
1056 if (reg == NULL || reg == RENAME_NO_RTX)
1058 if (! remove_phi_alternative (phi, b))
1059 abort ();
1061 else
1063 /* When we created the PHI nodes, we did not know what mode
1064 the register should be. Now that we've found an original,
1065 we can fill that in. */
1066 if (GET_MODE (SET_DEST (phi)) == VOIDmode)
1067 PUT_MODE (SET_DEST (phi), GET_MODE (reg));
1068 else if (GET_MODE (SET_DEST (phi)) != GET_MODE (reg))
1069 abort ();
1071 *phi_alternative (phi, bb) = reg;
1074 insn = NEXT_INSN (insn);
1078 /* Step Three: Do the same to the children of this block in
1079 dominator order. */
1081 for (c = 0; c < n_basic_blocks; ++c)
1082 if (idom[c] == bb)
1083 rename_block (c, idom);
1085 /* Step Four: Update the sets to refer to their new register,
1086 and restore ssa_rename_to to its previous state. */
1088 while (set_data)
1090 struct rename_set_data *next;
1091 rtx old_reg = *set_data->reg_loc;
1093 if (*set_data->reg_loc != set_data->old_reg)
1094 abort ();
1095 *set_data->reg_loc = set_data->new_reg;
1097 ssa_rename_to_insert (old_reg, set_data->prev_reg);
1099 next = set_data->next;
1100 free (set_data);
1101 set_data = next;
1105 static void
1106 rename_registers (nregs, idom)
1107 int nregs;
1108 int *idom;
1110 VARRAY_RTX_INIT (ssa_definition, nregs * 3, "ssa_definition");
1111 ssa_rename_from_initialize ();
1113 ssa_rename_to_pseudo = (rtx *) alloca (nregs * sizeof(rtx));
1114 memset ((char *) ssa_rename_to_pseudo, 0, nregs * sizeof(rtx));
1115 memset ((char *) ssa_rename_to_hard, 0,
1116 FIRST_PSEUDO_REGISTER * NUM_MACHINE_MODES * sizeof (rtx));
1118 rename_block (0, idom);
1120 /* ??? Update basic_block_live_at_start, and other flow info
1121 as needed. */
1123 ssa_rename_to_pseudo = NULL;
1126 /* The main entry point for moving to SSA. */
1128 void
1129 convert_to_ssa ()
1131 /* Element I is the set of blocks that set register I. */
1132 sbitmap *evals;
1134 /* Dominator bitmaps. */
1135 sbitmap *dfs;
1136 sbitmap *idfs;
1138 /* Element I is the immediate dominator of block I. */
1139 int *idom;
1141 int nregs;
1143 /* Don't do it twice. */
1144 if (in_ssa_form)
1145 abort ();
1147 /* Need global_live_at_{start,end} up to date. Do not remove any
1148 dead code. We'll let the SSA optimizers do that. */
1149 life_analysis (get_insns (), NULL, 0);
1151 idom = (int *) alloca (n_basic_blocks * sizeof (int));
1152 memset ((void *) idom, -1, (size_t) n_basic_blocks * sizeof (int));
1153 calculate_dominance_info (idom, NULL, CDI_DOMINATORS);
1155 if (rtl_dump_file)
1157 int i;
1158 fputs (";; Immediate Dominators:\n", rtl_dump_file);
1159 for (i = 0; i < n_basic_blocks; ++i)
1160 fprintf (rtl_dump_file, ";\t%3d = %3d\n", i, idom[i]);
1161 fflush (rtl_dump_file);
1164 /* Compute dominance frontiers. */
1166 dfs = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
1167 compute_dominance_frontiers (dfs, idom);
1169 if (rtl_dump_file)
1171 dump_sbitmap_vector (rtl_dump_file, ";; Dominance Frontiers:",
1172 "; Basic Block", dfs, n_basic_blocks);
1173 fflush (rtl_dump_file);
1176 /* Compute register evaluations. */
1178 ssa_max_reg_num = max_reg_num ();
1179 nregs = ssa_max_reg_num;
1180 evals = sbitmap_vector_alloc (nregs, n_basic_blocks);
1181 find_evaluations (evals, nregs);
1183 /* Compute the iterated dominance frontier for each register. */
1185 idfs = sbitmap_vector_alloc (nregs, n_basic_blocks);
1186 compute_iterated_dominance_frontiers (idfs, dfs, evals, nregs);
1188 if (rtl_dump_file)
1190 dump_sbitmap_vector (rtl_dump_file, ";; Iterated Dominance Frontiers:",
1191 "; Register", idfs, nregs);
1192 fflush (rtl_dump_file);
1195 /* Insert the phi nodes. */
1197 insert_phi_nodes (idfs, evals, nregs);
1199 /* Rename the registers to satisfy SSA. */
1201 rename_registers (nregs, idom);
1203 /* All done! Clean up and go home. */
1205 sbitmap_vector_free (dfs);
1206 sbitmap_vector_free (evals);
1207 sbitmap_vector_free (idfs);
1208 in_ssa_form = 1;
1210 reg_scan (get_insns (), max_reg_num (), 1);
1213 /* REG is the representative temporary of its partition. Add it to the
1214 set of nodes to be processed, if it hasn't been already. Return the
1215 index of this register in the node set. */
1217 static inline int
1218 ephi_add_node (reg, nodes, n_nodes)
1219 rtx reg, *nodes;
1220 int *n_nodes;
1222 int i;
1223 for (i = *n_nodes - 1; i >= 0; --i)
1224 if (REGNO (reg) == REGNO (nodes[i]))
1225 return i;
1227 nodes[i = (*n_nodes)++] = reg;
1228 return i;
1231 /* Part one of the topological sort. This is a forward (downward) search
1232 through the graph collecting a stack of nodes to process. Assuming no
1233 cycles, the nodes at top of the stack when we are finished will have
1234 no other dependencies. */
1236 static int *
1237 ephi_forward (t, visited, succ, tstack)
1238 int t;
1239 sbitmap visited;
1240 sbitmap *succ;
1241 int *tstack;
1243 int s;
1245 SET_BIT (visited, t);
1247 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1249 if (! TEST_BIT (visited, s))
1250 tstack = ephi_forward (s, visited, succ, tstack);
1253 *tstack++ = t;
1254 return tstack;
1257 /* Part two of the topological sort. The is a backward search through
1258 a cycle in the graph, copying the data forward as we go. */
1260 static void
1261 ephi_backward (t, visited, pred, nodes)
1262 int t;
1263 sbitmap visited, *pred;
1264 rtx *nodes;
1266 int p;
1268 SET_BIT (visited, t);
1270 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1272 if (! TEST_BIT (visited, p))
1274 ephi_backward (p, visited, pred, nodes);
1275 emit_move_insn (nodes[p], nodes[t]);
1280 /* Part two of the topological sort. Create the copy for a register
1281 and any cycle of which it is a member. */
1283 static void
1284 ephi_create (t, visited, pred, succ, nodes)
1285 int t;
1286 sbitmap visited, *pred, *succ;
1287 rtx *nodes;
1289 rtx reg_u = NULL_RTX;
1290 int unvisited_predecessors = 0;
1291 int p;
1293 /* Iterate through the predecessor list looking for unvisited nodes.
1294 If there are any, we have a cycle, and must deal with that. At
1295 the same time, look for a visited predecessor. If there is one,
1296 we won't need to create a temporary. */
1298 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1300 if (! TEST_BIT (visited, p))
1301 unvisited_predecessors = 1;
1302 else if (!reg_u)
1303 reg_u = nodes[p];
1306 if (unvisited_predecessors)
1308 /* We found a cycle. Copy out one element of the ring (if necessary),
1309 then traverse the ring copying as we go. */
1311 if (!reg_u)
1313 reg_u = gen_reg_rtx (GET_MODE (nodes[t]));
1314 emit_move_insn (reg_u, nodes[t]);
1317 EXECUTE_IF_SET_IN_SBITMAP (pred[t], 0, p,
1319 if (! TEST_BIT (visited, p))
1321 ephi_backward (p, visited, pred, nodes);
1322 emit_move_insn (nodes[p], reg_u);
1326 else
1328 /* No cycle. Just copy the value from a successor. */
1330 int s;
1331 EXECUTE_IF_SET_IN_SBITMAP (succ[t], 0, s,
1333 SET_BIT (visited, t);
1334 emit_move_insn (nodes[t], nodes[s]);
1335 return;
1340 /* Convert the edge to normal form. */
1342 static void
1343 eliminate_phi (e, reg_partition)
1344 edge e;
1345 partition reg_partition;
1347 int n_nodes;
1348 sbitmap *pred, *succ;
1349 sbitmap visited;
1350 rtx *nodes;
1351 int *stack, *tstack;
1352 rtx insn;
1353 int i;
1355 /* Collect an upper bound on the number of registers needing processing. */
1357 insn = first_insn_after_basic_block_note (e->dest);
1359 n_nodes = 0;
1360 while (PHI_NODE_P (insn))
1362 insn = next_nonnote_insn (insn);
1363 n_nodes += 2;
1366 if (n_nodes == 0)
1367 return;
1369 /* Build the auxiliary graph R(B).
1371 The nodes of the graph are the members of the register partition
1372 present in Phi(B). There is an edge from FIND(T0)->FIND(T1) for
1373 each T0 = PHI(...,T1,...), where T1 is for the edge from block C. */
1375 nodes = (rtx *) alloca (n_nodes * sizeof(rtx));
1376 pred = sbitmap_vector_alloc (n_nodes, n_nodes);
1377 succ = sbitmap_vector_alloc (n_nodes, n_nodes);
1378 sbitmap_vector_zero (pred, n_nodes);
1379 sbitmap_vector_zero (succ, n_nodes);
1381 insn = first_insn_after_basic_block_note (e->dest);
1383 n_nodes = 0;
1384 for (; PHI_NODE_P (insn); insn = next_nonnote_insn (insn))
1386 rtx* preg = phi_alternative (PATTERN (insn), e->src->index);
1387 rtx tgt = SET_DEST (PATTERN (insn));
1388 rtx reg;
1390 /* There may be no phi alternative corresponding to this edge.
1391 This indicates that the phi variable is undefined along this
1392 edge. */
1393 if (preg == NULL)
1394 continue;
1395 reg = *preg;
1397 if (GET_CODE (reg) != REG || GET_CODE (tgt) != REG)
1398 abort ();
1400 reg = regno_reg_rtx[partition_find (reg_partition, REGNO (reg))];
1401 tgt = regno_reg_rtx[partition_find (reg_partition, REGNO (tgt))];
1402 /* If the two registers are already in the same partition,
1403 nothing will need to be done. */
1404 if (reg != tgt)
1406 int ireg, itgt;
1408 ireg = ephi_add_node (reg, nodes, &n_nodes);
1409 itgt = ephi_add_node (tgt, nodes, &n_nodes);
1411 SET_BIT (pred[ireg], itgt);
1412 SET_BIT (succ[itgt], ireg);
1416 if (n_nodes == 0)
1417 goto out;
1419 /* Begin a topological sort of the graph. */
1421 visited = sbitmap_alloc (n_nodes);
1422 sbitmap_zero (visited);
1424 tstack = stack = (int *) alloca (n_nodes * sizeof (int));
1426 for (i = 0; i < n_nodes; ++i)
1427 if (! TEST_BIT (visited, i))
1428 tstack = ephi_forward (i, visited, succ, tstack);
1430 sbitmap_zero (visited);
1432 /* As we find a solution to the tsort, collect the implementation
1433 insns in a sequence. */
1434 start_sequence ();
1436 while (tstack != stack)
1438 i = *--tstack;
1439 if (! TEST_BIT (visited, i))
1440 ephi_create (i, visited, pred, succ, nodes);
1443 insn = gen_sequence ();
1444 end_sequence ();
1445 insert_insn_on_edge (insn, e);
1446 if (rtl_dump_file)
1447 fprintf (rtl_dump_file, "Emitting copy on edge (%d,%d)\n",
1448 e->src->index, e->dest->index);
1450 sbitmap_free (visited);
1451 out:
1452 sbitmap_vector_free (pred);
1453 sbitmap_vector_free (succ);
1456 /* For basic block B, consider all phi insns which provide an
1457 alternative corresponding to an incoming abnormal critical edge.
1458 Place the phi alternative corresponding to that abnormal critical
1459 edge in the same register class as the destination of the set.
1461 From Morgan, p. 178:
1463 For each abnormal critical edge (C, B),
1464 if T0 = phi (T1, ..., Ti, ..., Tm) is a phi node in B,
1465 and C is the ith predecessor of B,
1466 then T0 and Ti must be equivalent.
1468 Return non-zero iff any such cases were found for which the two
1469 regs were not already in the same class. */
1471 static int
1472 make_regs_equivalent_over_bad_edges (bb, reg_partition)
1473 int bb;
1474 partition reg_partition;
1476 int changed = 0;
1477 basic_block b = BASIC_BLOCK (bb);
1478 rtx phi;
1480 /* Advance to the first phi node. */
1481 phi = first_insn_after_basic_block_note (b);
1483 /* Scan all the phi nodes. */
1484 for (;
1485 PHI_NODE_P (phi);
1486 phi = next_nonnote_insn (phi))
1488 edge e;
1489 int tgt_regno;
1490 rtx set = PATTERN (phi);
1491 rtx tgt = SET_DEST (set);
1493 /* The set target is expected to be an SSA register. */
1494 if (GET_CODE (tgt) != REG
1495 || !CONVERT_REGISTER_TO_SSA_P (REGNO (tgt)))
1496 abort ();
1497 tgt_regno = REGNO (tgt);
1499 /* Scan incoming abnormal critical edges. */
1500 for (e = b->pred; e; e = e->pred_next)
1501 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
1503 rtx *alt = phi_alternative (set, e->src->index);
1504 int alt_regno;
1506 /* If there is no alternative corresponding to this edge,
1507 the value is undefined along the edge, so just go on. */
1508 if (alt == 0)
1509 continue;
1511 /* The phi alternative is expected to be an SSA register. */
1512 if (GET_CODE (*alt) != REG
1513 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
1514 abort ();
1515 alt_regno = REGNO (*alt);
1517 /* If the set destination and the phi alternative aren't
1518 already in the same class... */
1519 if (partition_find (reg_partition, tgt_regno)
1520 != partition_find (reg_partition, alt_regno))
1522 /* ... make them such. */
1523 if (conflicting_hard_regs_p (tgt_regno, alt_regno))
1524 /* It is illegal to unify a hard register with a
1525 different register. */
1526 abort ();
1528 partition_union (reg_partition,
1529 tgt_regno, alt_regno);
1530 ++changed;
1535 return changed;
1538 /* Consider phi insns in basic block BB pairwise. If the set target
1539 of both isns are equivalent pseudos, make the corresponding phi
1540 alternatives in each phi corresponding equivalent.
1542 Return nonzero if any new register classes were unioned. */
1544 static int
1545 make_equivalent_phi_alternatives_equivalent (bb, reg_partition)
1546 int bb;
1547 partition reg_partition;
1549 int changed = 0;
1550 basic_block b = BASIC_BLOCK (bb);
1551 rtx phi;
1553 /* Advance to the first phi node. */
1554 phi = first_insn_after_basic_block_note (b);
1556 /* Scan all the phi nodes. */
1557 for (;
1558 PHI_NODE_P (phi);
1559 phi = next_nonnote_insn (phi))
1561 rtx set = PATTERN (phi);
1562 /* The regno of the destination of the set. */
1563 int tgt_regno = REGNO (SET_DEST (PATTERN (phi)));
1565 rtx phi2 = next_nonnote_insn (phi);
1567 /* Scan all phi nodes following this one. */
1568 for (;
1569 PHI_NODE_P (phi2);
1570 phi2 = next_nonnote_insn (phi2))
1572 rtx set2 = PATTERN (phi2);
1573 /* The regno of the destination of the set. */
1574 int tgt2_regno = REGNO (SET_DEST (set2));
1576 /* Are the set destinations equivalent regs? */
1577 if (partition_find (reg_partition, tgt_regno) ==
1578 partition_find (reg_partition, tgt2_regno))
1580 edge e;
1581 /* Scan over edges. */
1582 for (e = b->pred; e; e = e->pred_next)
1584 int pred_block = e->src->index;
1585 /* Identify the phi alternatives from both phi
1586 nodes corresponding to this edge. */
1587 rtx *alt = phi_alternative (set, pred_block);
1588 rtx *alt2 = phi_alternative (set2, pred_block);
1590 /* If one of the phi nodes doesn't have a
1591 corresponding alternative, just skip it. */
1592 if (alt == 0 || alt2 == 0)
1593 continue;
1595 /* Both alternatives should be SSA registers. */
1596 if (GET_CODE (*alt) != REG
1597 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt)))
1598 abort ();
1599 if (GET_CODE (*alt2) != REG
1600 || !CONVERT_REGISTER_TO_SSA_P (REGNO (*alt2)))
1601 abort ();
1603 /* If the alternatives aren't already in the same
1604 class ... */
1605 if (partition_find (reg_partition, REGNO (*alt))
1606 != partition_find (reg_partition, REGNO (*alt2)))
1608 /* ... make them so. */
1609 if (conflicting_hard_regs_p (REGNO (*alt), REGNO (*alt2)))
1610 /* It is illegal to unify a hard register with
1611 a different register. */
1612 abort ();
1614 partition_union (reg_partition,
1615 REGNO (*alt), REGNO (*alt2));
1616 ++changed;
1623 return changed;
1626 /* Compute a conservative partition of outstanding pseudo registers.
1627 See Morgan 7.3.1. */
1629 static partition
1630 compute_conservative_reg_partition ()
1632 int bb;
1633 int changed = 0;
1635 /* We don't actually work with hard registers, but it's easier to
1636 carry them around anyway rather than constantly doing register
1637 number arithmetic. */
1638 partition p =
1639 partition_new (ssa_definition->num_elements);
1641 /* The first priority is to make sure registers that might have to
1642 be copied on abnormal critical edges are placed in the same
1643 partition. This saves us from having to split abnormal critical
1644 edges. */
1645 for (bb = n_basic_blocks; --bb >= 0; )
1646 changed += make_regs_equivalent_over_bad_edges (bb, p);
1648 /* Now we have to insure that corresponding arguments of phi nodes
1649 assigning to corresponding regs are equivalent. Iterate until
1650 nothing changes. */
1651 while (changed > 0)
1653 changed = 0;
1654 for (bb = n_basic_blocks; --bb >= 0; )
1655 changed += make_equivalent_phi_alternatives_equivalent (bb, p);
1658 return p;
1661 /* The following functions compute a register partition that attempts
1662 to eliminate as many reg copies and phi node copies as possible by
1663 coalescing registers. This is the strategy:
1665 1. As in the conservative case, the top priority is to coalesce
1666 registers that otherwise would cause copies to be placed on
1667 abnormal critical edges (which isn't possible).
1669 2. Figure out which regs are involved (in the LHS or RHS) of
1670 copies and phi nodes. Compute conflicts among these regs.
1672 3. Walk around the instruction stream, placing two regs in the
1673 same class of the partition if one appears on the LHS and the
1674 other on the RHS of a copy or phi node and the two regs don't
1675 conflict. The conflict information of course needs to be
1676 updated.
1678 4. If anything has changed, there may be new opportunities to
1679 coalesce regs, so go back to 2.
1682 /* If REG1 and REG2 don't conflict in CONFLICTS, place them in the
1683 same class of partition P, if they aren't already. Update
1684 CONFLICTS appropriately.
1686 Returns one if REG1 and REG2 were placed in the same class but were
1687 not previously; zero otherwise.
1689 See Morgan figure 11.15. */
1691 static int
1692 coalesce_if_unconflicting (p, conflicts, reg1, reg2)
1693 partition p;
1694 conflict_graph conflicts;
1695 int reg1;
1696 int reg2;
1698 int reg;
1700 /* Work only on SSA registers. */
1701 if (!CONVERT_REGISTER_TO_SSA_P (reg1) || !CONVERT_REGISTER_TO_SSA_P (reg2))
1702 return 0;
1704 /* Find the canonical regs for the classes containing REG1 and
1705 REG2. */
1706 reg1 = partition_find (p, reg1);
1707 reg2 = partition_find (p, reg2);
1709 /* If they're already in the same class, there's nothing to do. */
1710 if (reg1 == reg2)
1711 return 0;
1713 /* If the regs conflict, our hands are tied. */
1714 if (conflicting_hard_regs_p (reg1, reg2) ||
1715 conflict_graph_conflict_p (conflicts, reg1, reg2))
1716 return 0;
1718 /* We're good to go. Put the regs in the same partition. */
1719 partition_union (p, reg1, reg2);
1721 /* Find the new canonical reg for the merged class. */
1722 reg = partition_find (p, reg1);
1724 /* Merge conflicts from the two previous classes. */
1725 conflict_graph_merge_regs (conflicts, reg, reg1);
1726 conflict_graph_merge_regs (conflicts, reg, reg2);
1728 return 1;
1731 /* For each register copy insn in basic block BB, place the LHS and
1732 RHS regs in the same class in partition P if they do not conflict
1733 according to CONFLICTS.
1735 Returns the number of changes that were made to P.
1737 See Morgan figure 11.14. */
1739 static int
1740 coalesce_regs_in_copies (bb, p, conflicts)
1741 basic_block bb;
1742 partition p;
1743 conflict_graph conflicts;
1745 int changed = 0;
1746 rtx insn;
1747 rtx end = bb->end;
1749 /* Scan the instruction stream of the block. */
1750 for (insn = bb->head; insn != end; insn = NEXT_INSN (insn))
1752 rtx pattern;
1753 rtx src;
1754 rtx dest;
1756 /* If this isn't a set insn, go to the next insn. */
1757 if (GET_CODE (insn) != INSN)
1758 continue;
1759 pattern = PATTERN (insn);
1760 if (GET_CODE (pattern) != SET)
1761 continue;
1763 src = SET_SRC (pattern);
1764 dest = SET_DEST (pattern);
1766 /* We're only looking for copies. */
1767 if (GET_CODE (src) != REG || GET_CODE (dest) != REG)
1768 continue;
1770 /* Coalesce only if the reg modes are the same. As long as
1771 each reg's rtx is unique, it can have only one mode, so two
1772 pseudos of different modes can't be coalesced into one.
1774 FIXME: We can probably get around this by inserting SUBREGs
1775 where appropriate, but for now we don't bother. */
1776 if (GET_MODE (src) != GET_MODE (dest))
1777 continue;
1779 /* Found a copy; see if we can use the same reg for both the
1780 source and destination (and thus eliminate the copy,
1781 ultimately). */
1782 changed += coalesce_if_unconflicting (p, conflicts,
1783 REGNO (src), REGNO (dest));
1786 return changed;
1789 struct phi_coalesce_context
1791 partition p;
1792 conflict_graph conflicts;
1793 int changed;
1796 /* Callback function for for_each_successor_phi. If the set
1797 destination and the phi alternative regs do not conflict, place
1798 them in the same paritition class. DATA is a pointer to a
1799 phi_coalesce_context struct. */
1801 static int
1802 coalesce_reg_in_phi (insn, dest_regno, src_regno, data)
1803 rtx insn ATTRIBUTE_UNUSED;
1804 int dest_regno;
1805 int src_regno;
1806 void *data;
1808 struct phi_coalesce_context *context =
1809 (struct phi_coalesce_context *) data;
1811 /* Attempt to use the same reg, if they don't conflict. */
1812 context->changed
1813 += coalesce_if_unconflicting (context->p, context->conflicts,
1814 dest_regno, src_regno);
1815 return 0;
1818 /* For each alternative in a phi function corresponding to basic block
1819 BB (in phi nodes in successor block to BB), place the reg in the
1820 phi alternative and the reg to which the phi value is set into the
1821 same class in partition P, if allowed by CONFLICTS.
1823 Return the number of changes that were made to P.
1825 See Morgan figure 11.14. */
1827 static int
1828 coalesce_regs_in_successor_phi_nodes (bb, p, conflicts)
1829 basic_block bb;
1830 partition p;
1831 conflict_graph conflicts;
1833 struct phi_coalesce_context context;
1834 context.p = p;
1835 context.conflicts = conflicts;
1836 context.changed = 0;
1838 for_each_successor_phi (bb, &coalesce_reg_in_phi, &context);
1840 return context.changed;
1843 /* Compute and return a partition of pseudos. Where possible,
1844 non-conflicting pseudos are placed in the same class.
1846 The caller is responsible for deallocating the returned partition. */
1848 static partition
1849 compute_coalesced_reg_partition ()
1851 int bb;
1852 int changed = 0;
1853 regset_head phi_set_head;
1854 regset phi_set = &phi_set_head;
1856 partition p =
1857 partition_new (ssa_definition->num_elements);
1859 /* The first priority is to make sure registers that might have to
1860 be copied on abnormal critical edges are placed in the same
1861 partition. This saves us from having to split abnormal critical
1862 edges (which can't be done). */
1863 for (bb = n_basic_blocks; --bb >= 0; )
1864 make_regs_equivalent_over_bad_edges (bb, p);
1866 INIT_REG_SET (phi_set);
1870 conflict_graph conflicts;
1872 changed = 0;
1874 /* Build the set of registers involved in phi nodes, either as
1875 arguments to the phi function or as the target of a set. */
1876 CLEAR_REG_SET (phi_set);
1877 mark_phi_and_copy_regs (phi_set);
1879 /* Compute conflicts. */
1880 conflicts = conflict_graph_compute (phi_set, p);
1882 /* FIXME: Better would be to process most frequently executed
1883 blocks first, so that most frequently executed copies would
1884 be more likely to be removed by register coalescing. But any
1885 order will generate correct, if non-optimal, results. */
1886 for (bb = n_basic_blocks; --bb >= 0; )
1888 basic_block block = BASIC_BLOCK (bb);
1889 changed += coalesce_regs_in_copies (block, p, conflicts);
1890 changed +=
1891 coalesce_regs_in_successor_phi_nodes (block, p, conflicts);
1894 conflict_graph_delete (conflicts);
1896 while (changed > 0);
1898 FREE_REG_SET (phi_set);
1900 return p;
1903 /* Mark the regs in a phi node. PTR is a phi expression or one of its
1904 components (a REG or a CONST_INT). DATA is a reg set in which to
1905 set all regs. Called from for_each_rtx. */
1907 static int
1908 mark_reg_in_phi (ptr, data)
1909 rtx *ptr;
1910 void *data;
1912 rtx expr = *ptr;
1913 regset set = (regset) data;
1915 switch (GET_CODE (expr))
1917 case REG:
1918 SET_REGNO_REG_SET (set, REGNO (expr));
1919 /* Fall through. */
1920 case CONST_INT:
1921 case PHI:
1922 return 0;
1923 default:
1924 abort ();
1928 /* Mark in PHI_SET all pseudos that are used in a phi node -- either
1929 set from a phi expression, or used as an argument in one. Also
1930 mark regs that are the source or target of a reg copy. Uses
1931 ssa_definition. */
1933 static void
1934 mark_phi_and_copy_regs (phi_set)
1935 regset phi_set;
1937 unsigned int reg;
1939 /* Scan the definitions of all regs. */
1940 for (reg = 0; reg < VARRAY_SIZE (ssa_definition); ++reg)
1941 if (CONVERT_REGISTER_TO_SSA_P (reg))
1943 rtx insn = VARRAY_RTX (ssa_definition, reg);
1944 rtx pattern;
1945 rtx src;
1947 if (insn == NULL
1948 || (GET_CODE (insn) == NOTE
1949 && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED))
1950 continue;
1951 pattern = PATTERN (insn);
1952 /* Sometimes we get PARALLEL insns. These aren't phi nodes or
1953 copies. */
1954 if (GET_CODE (pattern) != SET)
1955 continue;
1956 src = SET_SRC (pattern);
1958 if (GET_CODE (src) == REG)
1960 /* It's a reg copy. */
1961 SET_REGNO_REG_SET (phi_set, reg);
1962 SET_REGNO_REG_SET (phi_set, REGNO (src));
1964 else if (GET_CODE (src) == PHI)
1966 /* It's a phi node. Mark the reg being set. */
1967 SET_REGNO_REG_SET (phi_set, reg);
1968 /* Mark the regs used in the phi function. */
1969 for_each_rtx (&src, mark_reg_in_phi, phi_set);
1971 /* ... else nothing to do. */
1975 /* Rename regs in insn PTR that are equivalent. DATA is the register
1976 partition which specifies equivalences. */
1978 static int
1979 rename_equivalent_regs_in_insn (ptr, data)
1980 rtx *ptr;
1981 void* data;
1983 rtx x = *ptr;
1984 partition reg_partition = (partition) data;
1986 if (x == NULL_RTX)
1987 return 0;
1989 switch (GET_CODE (x))
1991 case REG:
1992 if (CONVERT_REGISTER_TO_SSA_P (REGNO (x)))
1994 unsigned int regno = REGNO (x);
1995 unsigned int new_regno = partition_find (reg_partition, regno);
1996 rtx canonical_element_rtx = ssa_rename_from_lookup (new_regno);
1998 if (canonical_element_rtx != NULL_RTX &&
1999 HARD_REGISTER_P (canonical_element_rtx))
2001 if (REGNO (canonical_element_rtx) != regno)
2002 *ptr = canonical_element_rtx;
2004 else if (regno != new_regno)
2006 rtx new_reg = regno_reg_rtx[new_regno];
2007 if (GET_MODE (x) != GET_MODE (new_reg))
2008 abort ();
2009 *ptr = new_reg;
2012 return -1;
2014 case PHI:
2015 /* No need to rename the phi nodes. We'll check equivalence
2016 when inserting copies. */
2017 return -1;
2019 default:
2020 /* Anything else, continue traversing. */
2021 return 0;
2025 /* Record the register's canonical element stored in SRFP in the
2026 canonical_elements sbitmap packaged in DATA. This function is used
2027 as a callback function for traversing ssa_rename_from. */
2029 static int
2030 record_canonical_element_1 (srfp, data)
2031 void **srfp;
2032 void *data;
2034 unsigned int reg = ((ssa_rename_from_pair *) *srfp)->reg;
2035 sbitmap canonical_elements =
2036 ((struct ssa_rename_from_hash_table_data *) data)->canonical_elements;
2037 partition reg_partition =
2038 ((struct ssa_rename_from_hash_table_data *) data)->reg_partition;
2040 SET_BIT (canonical_elements, partition_find (reg_partition, reg));
2041 return 1;
2044 /* For each class in the REG_PARTITION corresponding to a particular
2045 hard register and machine mode, check that there are no other
2046 classes with the same hard register and machine mode. Returns
2047 nonzero if this is the case, i.e., the partition is acceptable. */
2049 static int
2050 check_hard_regs_in_partition (reg_partition)
2051 partition reg_partition;
2053 /* CANONICAL_ELEMENTS has a nonzero bit if a class with the given register
2054 number and machine mode has already been seen. This is a
2055 problem with the partition. */
2056 sbitmap canonical_elements;
2057 int element_index;
2058 int already_seen[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
2059 int reg;
2060 int mach_mode;
2062 /* Collect a list of canonical elements. */
2063 canonical_elements = sbitmap_alloc (max_reg_num ());
2064 sbitmap_zero (canonical_elements);
2065 ssa_rename_from_traverse (&record_canonical_element_1,
2066 canonical_elements, reg_partition);
2068 /* We have not seen any hard register uses. */
2069 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; ++reg)
2070 for (mach_mode = 0; mach_mode < NUM_MACHINE_MODES; ++mach_mode)
2071 already_seen[reg][mach_mode] = 0;
2073 /* Check for classes with the same hard register and machine mode. */
2074 EXECUTE_IF_SET_IN_SBITMAP (canonical_elements, 0, element_index,
2076 rtx hard_reg_rtx = ssa_rename_from_lookup (element_index);
2077 if (hard_reg_rtx != NULL_RTX &&
2078 HARD_REGISTER_P (hard_reg_rtx) &&
2079 already_seen[REGNO (hard_reg_rtx)][GET_MODE (hard_reg_rtx)] != 0)
2080 /* Two distinct partition classes should be mapped to the same
2081 hard register. */
2082 return 0;
2085 sbitmap_free (canonical_elements);
2087 return 1;
2090 /* Rename regs that are equivalent in REG_PARTITION. Also collapse
2091 any SEQUENCE insns. */
2093 static void
2094 rename_equivalent_regs (reg_partition)
2095 partition reg_partition;
2097 int bb;
2099 for (bb = n_basic_blocks; --bb >= 0; )
2101 basic_block b = BASIC_BLOCK (bb);
2102 rtx next = b->head;
2103 rtx last = b->end;
2104 rtx insn;
2108 insn = next;
2109 if (INSN_P (insn))
2111 for_each_rtx (&PATTERN (insn),
2112 rename_equivalent_regs_in_insn,
2113 reg_partition);
2114 for_each_rtx (&REG_NOTES (insn),
2115 rename_equivalent_regs_in_insn,
2116 reg_partition);
2118 if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2120 rtx s = PATTERN (insn);
2121 int slen = XVECLEN (s, 0);
2122 int i;
2124 if (slen <= 1)
2125 abort ();
2127 PATTERN (insn) = XVECEXP (s, 0, slen-1);
2128 for (i = 0; i < slen - 1; i++)
2129 emit_insn_before (XVECEXP (s, 0, i), insn);
2133 next = NEXT_INSN (insn);
2135 while (insn != last);
2139 /* The main entry point for moving from SSA. */
2141 void
2142 convert_from_ssa ()
2144 int bb;
2145 partition reg_partition;
2146 rtx insns = get_insns ();
2148 /* Need global_live_at_{start,end} up to date. There should not be
2149 any significant dead code at this point, except perhaps dead
2150 stores. So do not take the time to perform dead code elimination.
2152 Register coalescing needs death notes, so generate them. */
2153 life_analysis (insns, NULL, PROP_DEATH_NOTES);
2155 /* Figure out which regs in copies and phi nodes don't conflict and
2156 therefore can be coalesced. */
2157 if (conservative_reg_partition)
2158 reg_partition = compute_conservative_reg_partition ();
2159 else
2160 reg_partition = compute_coalesced_reg_partition ();
2162 if (!check_hard_regs_in_partition (reg_partition))
2163 /* Two separate partitions should correspond to the same hard
2164 register but do not. */
2165 abort ();
2167 rename_equivalent_regs (reg_partition);
2169 /* Eliminate the PHI nodes. */
2170 for (bb = n_basic_blocks; --bb >= 0; )
2172 basic_block b = BASIC_BLOCK (bb);
2173 edge e;
2175 for (e = b->pred; e; e = e->pred_next)
2176 if (e->src != ENTRY_BLOCK_PTR)
2177 eliminate_phi (e, reg_partition);
2180 partition_delete (reg_partition);
2182 /* Actually delete the PHI nodes. */
2183 for (bb = n_basic_blocks; --bb >= 0; )
2185 rtx insn = BLOCK_HEAD (bb);
2187 while (1)
2189 /* If this is a PHI node delete it. */
2190 if (PHI_NODE_P (insn))
2192 if (insn == BLOCK_END (bb))
2193 BLOCK_END (bb) = PREV_INSN (insn);
2194 insn = delete_insn (insn);
2196 /* Since all the phi nodes come at the beginning of the
2197 block, if we find an ordinary insn, we can stop looking
2198 for more phi nodes. */
2199 else if (INSN_P (insn))
2200 break;
2201 /* If we've reached the end of the block, stop. */
2202 else if (insn == BLOCK_END (bb))
2203 break;
2204 else
2205 insn = NEXT_INSN (insn);
2209 /* Commit all the copy nodes needed to convert out of SSA form. */
2210 commit_edge_insertions ();
2212 in_ssa_form = 0;
2214 count_or_remove_death_notes (NULL, 1);
2216 /* Deallocate the data structures. */
2217 VARRAY_FREE (ssa_definition);
2218 ssa_rename_from_free ();
2221 /* Scan phi nodes in successors to BB. For each such phi node that
2222 has a phi alternative value corresponding to BB, invoke FN. FN
2223 is passed the entire phi node insn, the regno of the set
2224 destination, the regno of the phi argument corresponding to BB,
2225 and DATA.
2227 If FN ever returns non-zero, stops immediately and returns this
2228 value. Otherwise, returns zero. */
2231 for_each_successor_phi (bb, fn, data)
2232 basic_block bb;
2233 successor_phi_fn fn;
2234 void *data;
2236 edge e;
2238 if (bb == EXIT_BLOCK_PTR)
2239 return 0;
2241 /* Scan outgoing edges. */
2242 for (e = bb->succ; e != NULL; e = e->succ_next)
2244 rtx insn;
2246 basic_block successor = e->dest;
2247 if (successor == ENTRY_BLOCK_PTR
2248 || successor == EXIT_BLOCK_PTR)
2249 continue;
2251 /* Advance to the first non-label insn of the successor block. */
2252 insn = first_insn_after_basic_block_note (successor);
2254 if (insn == NULL)
2255 continue;
2257 /* Scan phi nodes in the successor. */
2258 for ( ; PHI_NODE_P (insn); insn = NEXT_INSN (insn))
2260 int result;
2261 rtx phi_set = PATTERN (insn);
2262 rtx *alternative = phi_alternative (phi_set, bb->index);
2263 rtx phi_src;
2265 /* This phi function may not have an alternative
2266 corresponding to the incoming edge, indicating the
2267 assigned variable is not defined along the edge. */
2268 if (alternative == NULL)
2269 continue;
2270 phi_src = *alternative;
2272 /* Invoke the callback. */
2273 result = (*fn) (insn, REGNO (SET_DEST (phi_set)),
2274 REGNO (phi_src), data);
2276 /* Terminate if requested. */
2277 if (result != 0)
2278 return result;
2282 return 0;
2285 /* Assuming the ssa_rename_from mapping has been established, yields
2286 nonzero if 1) only one SSA register of REG1 and REG2 comes from a
2287 hard register or 2) both SSA registers REG1 and REG2 come from
2288 different hard registers. */
2290 static int
2291 conflicting_hard_regs_p (reg1, reg2)
2292 int reg1;
2293 int reg2;
2295 int orig_reg1 = original_register (reg1);
2296 int orig_reg2 = original_register (reg2);
2297 if (HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2)
2298 && orig_reg1 != orig_reg2)
2299 return 1;
2300 if (HARD_REGISTER_NUM_P (orig_reg1) && !HARD_REGISTER_NUM_P (orig_reg2))
2301 return 1;
2302 if (!HARD_REGISTER_NUM_P (orig_reg1) && HARD_REGISTER_NUM_P (orig_reg2))
2303 return 1;
2305 return 0;