2016-08-24 Michael Collison <michael.collison@linaro.org>
[official-gcc.git] / gcc / regrename.c
blob54c7768efa226139c340868e42b784fb011a19b9
1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000-2016 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "target.h"
25 #include "rtl.h"
26 #include "df.h"
27 #include "tm_p.h"
28 #include "insn-config.h"
29 #include "regs.h"
30 #include "emit-rtl.h"
31 #include "recog.h"
32 #include "addresses.h"
33 #include "cfganal.h"
34 #include "tree-pass.h"
35 #include "regrename.h"
37 /* This file implements the RTL register renaming pass of the compiler. It is
38 a semi-local pass whose goal is to maximize the usage of the register file
39 of the processor by substituting registers for others in the solution given
40 by the register allocator. The algorithm is as follows:
42 1. Local def/use chains are built: within each basic block, chains are
43 opened and closed; if a chain isn't closed at the end of the block,
44 it is dropped. We pre-open chains if we have already examined a
45 predecessor block and found chains live at the end which match
46 live registers at the start of the new block.
48 2. We try to combine the local chains across basic block boundaries by
49 comparing chains that were open at the start or end of a block to
50 those in successor/predecessor blocks.
52 3. For each chain, the set of possible renaming registers is computed.
53 This takes into account the renaming of previously processed chains.
54 Optionally, a preferred class is computed for the renaming register.
56 4. The best renaming register is computed for the chain in the above set,
57 using a round-robin allocation. If a preferred class exists, then the
58 round-robin allocation is done within the class first, if possible.
59 The round-robin allocation of renaming registers itself is global.
61 5. If a renaming register has been found, it is substituted in the chain.
63 Targets can parameterize the pass by specifying a preferred class for the
64 renaming register for a given (super)class of registers to be renamed.
66 DEBUG_INSNs are treated specially, in particular registers occurring inside
67 them are treated as requiring ALL_REGS as a class. */
69 #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
70 #error "Use a different bitmap implementation for untracked_operands."
71 #endif
73 enum scan_actions
75 terminate_write,
76 terminate_dead,
77 mark_all_read,
78 mark_read,
79 mark_write,
80 /* mark_access is for marking the destination regs in
81 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
82 note is updated properly. */
83 mark_access
86 static const char * const scan_actions_name[] =
88 "terminate_write",
89 "terminate_dead",
90 "mark_all_read",
91 "mark_read",
92 "mark_write",
93 "mark_access"
96 /* TICK and THIS_TICK are used to record the last time we saw each
97 register. */
98 static int tick[FIRST_PSEUDO_REGISTER];
99 static int this_tick = 0;
101 static struct obstack rename_obstack;
103 /* If nonnull, the code calling into the register renamer requested
104 information about insn operands, and we store it here. */
105 vec<insn_rr_info> insn_rr;
107 static void scan_rtx (rtx_insn *, rtx *, enum reg_class, enum scan_actions,
108 enum op_type);
109 static bool build_def_use (basic_block);
111 /* The id to be given to the next opened chain. */
112 static unsigned current_id;
114 /* A mapping of unique id numbers to chains. */
115 static vec<du_head_p> id_to_chain;
117 /* List of currently open chains. */
118 static struct du_head *open_chains;
120 /* Bitmap of open chains. The bits set always match the list found in
121 open_chains. */
122 static bitmap_head open_chains_set;
124 /* Record the registers being tracked in open_chains. */
125 static HARD_REG_SET live_in_chains;
127 /* Record the registers that are live but not tracked. The intersection
128 between this and live_in_chains is empty. */
129 static HARD_REG_SET live_hard_regs;
131 /* Set while scanning RTL if INSN_RR is nonnull, i.e. if the current analysis
132 is for a caller that requires operand data. Used in
133 record_operand_use. */
134 static operand_rr_info *cur_operand;
136 /* Set while scanning RTL if a register dies. Used to tie chains. */
137 static struct du_head *terminated_this_insn;
139 /* Return the chain corresponding to id number ID. Take into account that
140 chains may have been merged. */
141 du_head_p
142 regrename_chain_from_id (unsigned int id)
144 du_head_p first_chain = id_to_chain[id];
145 du_head_p chain = first_chain;
146 while (chain->id != id)
148 id = chain->id;
149 chain = id_to_chain[id];
151 first_chain->id = id;
152 return chain;
155 /* Dump all def/use chains, starting at id FROM. */
157 static void
158 dump_def_use_chain (int from)
160 du_head_p head;
161 int i;
162 FOR_EACH_VEC_ELT_FROM (id_to_chain, i, head, from)
164 struct du_chain *this_du = head->first;
166 fprintf (dump_file, "Register %s (%d):",
167 reg_names[head->regno], head->nregs);
168 while (this_du)
170 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
171 reg_class_names[this_du->cl]);
172 this_du = this_du->next_use;
174 fprintf (dump_file, "\n");
175 head = head->next_chain;
179 static void
180 free_chain_data (void)
182 int i;
183 du_head_p ptr;
184 for (i = 0; id_to_chain.iterate (i, &ptr); i++)
185 bitmap_clear (&ptr->conflicts);
187 id_to_chain.release ();
190 /* Walk all chains starting with CHAINS and record that they conflict with
191 another chain whose id is ID. */
193 static void
194 mark_conflict (struct du_head *chains, unsigned id)
196 while (chains)
198 bitmap_set_bit (&chains->conflicts, id);
199 chains = chains->next_chain;
203 /* Examine cur_operand, and if it is nonnull, record information about the
204 use THIS_DU which is part of the chain HEAD. */
206 static void
207 record_operand_use (struct du_head *head, struct du_chain *this_du)
209 if (cur_operand == NULL || cur_operand->failed)
210 return;
211 if (head->cannot_rename)
213 cur_operand->failed = true;
214 return;
216 gcc_assert (cur_operand->n_chains < MAX_REGS_PER_ADDRESS);
217 cur_operand->heads[cur_operand->n_chains] = head;
218 cur_operand->chains[cur_operand->n_chains++] = this_du;
221 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
222 and record its occurrence in *LOC, which is being written to in INSN.
223 This access requires a register of class CL. */
225 static du_head_p
226 create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
227 rtx_insn *insn, enum reg_class cl)
229 struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
230 struct du_chain *this_du;
231 int nregs;
233 memset (head, 0, sizeof *head);
234 head->next_chain = open_chains;
235 head->regno = this_regno;
236 head->nregs = this_nregs;
238 id_to_chain.safe_push (head);
239 head->id = current_id++;
241 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
242 bitmap_copy (&head->conflicts, &open_chains_set);
243 mark_conflict (open_chains, head->id);
245 /* Since we're tracking this as a chain now, remove it from the
246 list of conflicting live hard registers and track it in
247 live_in_chains instead. */
248 nregs = head->nregs;
249 while (nregs-- > 0)
251 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
252 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
255 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
256 bitmap_set_bit (&open_chains_set, head->id);
258 open_chains = head;
260 if (dump_file)
262 fprintf (dump_file, "Creating chain %s (%d)",
263 reg_names[head->regno], head->id);
264 if (insn != NULL_RTX)
265 fprintf (dump_file, " at insn %d", INSN_UID (insn));
266 fprintf (dump_file, "\n");
269 if (insn == NULL_RTX)
271 head->first = head->last = NULL;
272 return head;
275 this_du = XOBNEW (&rename_obstack, struct du_chain);
276 head->first = head->last = this_du;
278 this_du->next_use = 0;
279 this_du->loc = loc;
280 this_du->insn = insn;
281 this_du->cl = cl;
282 record_operand_use (head, this_du);
283 return head;
286 /* For a def-use chain HEAD, find which registers overlap its lifetime and
287 set the corresponding bits in *PSET. */
289 static void
290 merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
292 bitmap_iterator bi;
293 unsigned i;
294 IOR_HARD_REG_SET (*pset, head->hard_conflicts);
295 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
297 du_head_p other = regrename_chain_from_id (i);
298 unsigned j = other->nregs;
299 gcc_assert (other != head);
300 while (j-- > 0)
301 SET_HARD_REG_BIT (*pset, other->regno + j);
305 /* Check if NEW_REG can be the candidate register to rename for
306 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
307 registers. */
309 static bool
310 check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg,
311 struct du_head *this_head, HARD_REG_SET this_unavailable)
313 machine_mode mode = GET_MODE (*this_head->first->loc);
314 int nregs = hard_regno_nregs[new_reg][mode];
315 int i;
316 struct du_chain *tmp;
318 for (i = nregs - 1; i >= 0; --i)
319 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
320 || fixed_regs[new_reg + i]
321 || global_regs[new_reg + i]
322 /* Can't use regs which aren't saved by the prologue. */
323 || (! df_regs_ever_live_p (new_reg + i)
324 && ! call_used_regs[new_reg + i])
325 #ifdef LEAF_REGISTERS
326 /* We can't use a non-leaf register if we're in a
327 leaf function. */
328 || (crtl->is_leaf
329 && !LEAF_REGISTERS[new_reg + i])
330 #endif
331 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i))
332 return false;
334 /* See whether it accepts all modes that occur in
335 definition and uses. */
336 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
337 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
338 && ! DEBUG_INSN_P (tmp->insn))
339 || (this_head->need_caller_save_reg
340 && ! (HARD_REGNO_CALL_PART_CLOBBERED
341 (reg, GET_MODE (*tmp->loc)))
342 && (HARD_REGNO_CALL_PART_CLOBBERED
343 (new_reg, GET_MODE (*tmp->loc)))))
344 return false;
346 return true;
349 /* For the chain THIS_HEAD, compute and return the best register to
350 rename to. SUPER_CLASS is the superunion of register classes in
351 the chain. UNAVAILABLE is a set of registers that cannot be used.
352 OLD_REG is the register currently used for the chain. BEST_RENAME
353 controls whether the register chosen must be better than the
354 current one or just respect the given constraint. */
357 find_rename_reg (du_head_p this_head, enum reg_class super_class,
358 HARD_REG_SET *unavailable, int old_reg, bool best_rename)
360 bool has_preferred_class;
361 enum reg_class preferred_class;
362 int pass;
363 int best_new_reg = old_reg;
365 /* Further narrow the set of registers we can use for renaming.
366 If the chain needs a call-saved register, mark the call-used
367 registers as unavailable. */
368 if (this_head->need_caller_save_reg)
369 IOR_HARD_REG_SET (*unavailable, call_used_reg_set);
371 /* Mark registers that overlap this chain's lifetime as unavailable. */
372 merge_overlapping_regs (unavailable, this_head);
374 /* Compute preferred rename class of super union of all the classes
375 in the chain. */
376 preferred_class
377 = (enum reg_class) targetm.preferred_rename_class (super_class);
379 /* Pick and check the register from the tied chain iff the tied chain
380 is not renamed. */
381 if (this_head->tied_chain && !this_head->tied_chain->renamed
382 && check_new_reg_p (old_reg, this_head->tied_chain->regno,
383 this_head, *unavailable))
384 return this_head->tied_chain->regno;
386 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
387 over registers that belong to PREFERRED_CLASS and try to find the
388 best register within the class. If that failed, we iterate in
389 the second pass over registers that don't belong to the class.
390 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
391 ascending order without any preference. */
392 has_preferred_class = (preferred_class != NO_REGS);
393 for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
395 int new_reg;
396 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
398 if (has_preferred_class
399 && (pass == 0)
400 != TEST_HARD_REG_BIT (reg_class_contents[preferred_class],
401 new_reg))
402 continue;
404 if (!check_new_reg_p (old_reg, new_reg, this_head, *unavailable))
405 continue;
407 if (!best_rename)
408 return new_reg;
410 /* In the first pass, we force the renaming of registers that
411 don't belong to PREFERRED_CLASS to registers that do, even
412 though the latters were used not very long ago. */
413 if ((pass == 0
414 && !TEST_HARD_REG_BIT (reg_class_contents[preferred_class],
415 best_new_reg))
416 || tick[best_new_reg] > tick[new_reg])
417 best_new_reg = new_reg;
419 if (pass == 0 && best_new_reg != old_reg)
420 break;
422 return best_new_reg;
425 /* Iterate over elements in the chain HEAD in order to:
426 1. Count number of uses, storing it in *PN_USES.
427 2. Narrow the set of registers we can use for renaming, adding
428 unavailable registers to *PUNAVAILABLE, which must be
429 initialized by the caller.
430 3. Compute the superunion of register classes in this chain
431 and return it. */
432 reg_class
433 regrename_find_superclass (du_head_p head, int *pn_uses,
434 HARD_REG_SET *punavailable)
436 int n_uses = 0;
437 reg_class super_class = NO_REGS;
438 for (du_chain *tmp = head->first; tmp; tmp = tmp->next_use)
440 if (DEBUG_INSN_P (tmp->insn))
441 continue;
442 n_uses++;
443 IOR_COMPL_HARD_REG_SET (*punavailable,
444 reg_class_contents[tmp->cl]);
445 super_class
446 = reg_class_superunion[(int) super_class][(int) tmp->cl];
448 *pn_uses = n_uses;
449 return super_class;
452 /* Perform register renaming on the current function. */
453 static void
454 rename_chains (void)
456 HARD_REG_SET unavailable;
457 du_head_p this_head;
458 int i;
460 memset (tick, 0, sizeof tick);
462 CLEAR_HARD_REG_SET (unavailable);
463 /* Don't clobber traceback for noreturn functions. */
464 if (frame_pointer_needed)
466 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
467 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
468 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
471 FOR_EACH_VEC_ELT (id_to_chain, i, this_head)
473 int best_new_reg;
474 int n_uses;
475 HARD_REG_SET this_unavailable;
476 int reg = this_head->regno;
478 if (this_head->cannot_rename)
479 continue;
481 if (fixed_regs[reg] || global_regs[reg]
482 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
483 && reg == HARD_FRAME_POINTER_REGNUM)
484 || (HARD_FRAME_POINTER_REGNUM && frame_pointer_needed
485 && reg == FRAME_POINTER_REGNUM))
486 continue;
488 COPY_HARD_REG_SET (this_unavailable, unavailable);
490 reg_class super_class = regrename_find_superclass (this_head, &n_uses,
491 &this_unavailable);
492 if (n_uses < 2)
493 continue;
495 best_new_reg = find_rename_reg (this_head, super_class,
496 &this_unavailable, reg, true);
498 if (dump_file)
500 fprintf (dump_file, "Register %s in insn %d",
501 reg_names[reg], INSN_UID (this_head->first->insn));
502 if (this_head->need_caller_save_reg)
503 fprintf (dump_file, " crosses a call");
506 if (best_new_reg == reg)
508 tick[reg] = ++this_tick;
509 if (dump_file)
510 fprintf (dump_file, "; no available better choice\n");
511 continue;
514 if (regrename_do_replace (this_head, best_new_reg))
516 if (dump_file)
517 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
518 tick[best_new_reg] = ++this_tick;
519 df_set_regs_ever_live (best_new_reg, true);
521 else
523 if (dump_file)
524 fprintf (dump_file, ", renaming as %s failed\n",
525 reg_names[best_new_reg]);
526 tick[reg] = ++this_tick;
531 /* A structure to record information for each hard register at the start of
532 a basic block. */
533 struct incoming_reg_info {
534 /* Holds the number of registers used in the chain that gave us information
535 about this register. Zero means no information known yet, while a
536 negative value is used for something that is part of, but not the first
537 register in a multi-register value. */
538 int nregs;
539 /* Set to true if we have accesses that conflict in the number of registers
540 used. */
541 bool unusable;
544 /* A structure recording information about each basic block. It is saved
545 and restored around basic block boundaries.
546 A pointer to such a structure is stored in each basic block's aux field
547 during regrename_analyze, except for blocks we know can't be optimized
548 (such as entry and exit blocks). */
549 struct bb_rename_info
551 /* The basic block corresponding to this structure. */
552 basic_block bb;
553 /* Copies of the global information. */
554 bitmap_head open_chains_set;
555 bitmap_head incoming_open_chains_set;
556 struct incoming_reg_info incoming[FIRST_PSEUDO_REGISTER];
559 /* Initialize a rename_info structure P for basic block BB, which starts a new
560 scan. */
561 static void
562 init_rename_info (struct bb_rename_info *p, basic_block bb)
564 int i;
565 df_ref def;
566 HARD_REG_SET start_chains_set;
568 p->bb = bb;
569 bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack);
570 bitmap_initialize (&p->incoming_open_chains_set, &bitmap_default_obstack);
572 open_chains = NULL;
573 bitmap_clear (&open_chains_set);
575 CLEAR_HARD_REG_SET (live_in_chains);
576 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
577 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
578 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
579 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
581 /* Open chains based on information from (at least one) predecessor
582 block. This gives us a chance later on to combine chains across
583 basic block boundaries. Inconsistencies (in access sizes) will
584 be caught normally and dealt with conservatively by disabling the
585 chain for renaming, and there is no risk of losing optimization
586 opportunities by opening chains either: if we did not open the
587 chains, we'd have to track the live register as a hard reg, and
588 we'd be unable to rename it in any case. */
589 CLEAR_HARD_REG_SET (start_chains_set);
590 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
592 struct incoming_reg_info *iri = p->incoming + i;
593 if (iri->nregs > 0 && !iri->unusable
594 && range_in_hard_reg_set_p (live_hard_regs, i, iri->nregs))
596 SET_HARD_REG_BIT (start_chains_set, i);
597 remove_range_from_hard_reg_set (&live_hard_regs, i, iri->nregs);
600 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
602 struct incoming_reg_info *iri = p->incoming + i;
603 if (TEST_HARD_REG_BIT (start_chains_set, i))
605 du_head_p chain;
606 if (dump_file)
607 fprintf (dump_file, "opening incoming chain\n");
608 chain = create_new_chain (i, iri->nregs, NULL, NULL, NO_REGS);
609 bitmap_set_bit (&p->incoming_open_chains_set, chain->id);
614 /* Record in RI that the block corresponding to it has an incoming
615 live value, described by CHAIN. */
616 static void
617 set_incoming_from_chain (struct bb_rename_info *ri, du_head_p chain)
619 int i;
620 int incoming_nregs = ri->incoming[chain->regno].nregs;
621 int nregs;
623 /* If we've recorded the same information before, everything is fine. */
624 if (incoming_nregs == chain->nregs)
626 if (dump_file)
627 fprintf (dump_file, "reg %d/%d already recorded\n",
628 chain->regno, chain->nregs);
629 return;
632 /* If we have no information for any of the involved registers, update
633 the incoming array. */
634 nregs = chain->nregs;
635 while (nregs-- > 0)
636 if (ri->incoming[chain->regno + nregs].nregs != 0
637 || ri->incoming[chain->regno + nregs].unusable)
638 break;
639 if (nregs < 0)
641 nregs = chain->nregs;
642 ri->incoming[chain->regno].nregs = nregs;
643 while (nregs-- > 1)
644 ri->incoming[chain->regno + nregs].nregs = -nregs;
645 if (dump_file)
646 fprintf (dump_file, "recorded reg %d/%d\n",
647 chain->regno, chain->nregs);
648 return;
651 /* There must be some kind of conflict. Prevent both the old and
652 new ranges from being used. */
653 if (incoming_nregs < 0)
654 ri->incoming[chain->regno + incoming_nregs].unusable = true;
655 for (i = 0; i < chain->nregs; i++)
656 ri->incoming[chain->regno + i].unusable = true;
659 /* Merge the two chains C1 and C2 so that all conflict information is
660 recorded and C1, and the id of C2 is changed to that of C1. */
661 static void
662 merge_chains (du_head_p c1, du_head_p c2)
664 if (c1 == c2)
665 return;
667 if (c2->first != NULL)
669 if (c1->first == NULL)
670 c1->first = c2->first;
671 else
672 c1->last->next_use = c2->first;
673 c1->last = c2->last;
676 c2->first = c2->last = NULL;
677 c2->id = c1->id;
679 IOR_HARD_REG_SET (c1->hard_conflicts, c2->hard_conflicts);
680 bitmap_ior_into (&c1->conflicts, &c2->conflicts);
682 c1->need_caller_save_reg |= c2->need_caller_save_reg;
683 c1->cannot_rename |= c2->cannot_rename;
686 /* Analyze the current function and build chains for renaming. */
688 void
689 regrename_analyze (bitmap bb_mask)
691 struct bb_rename_info *rename_info;
692 int i;
693 basic_block bb;
694 int n_bbs;
695 int *inverse_postorder;
697 inverse_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
698 n_bbs = pre_and_rev_post_order_compute (NULL, inverse_postorder, false);
700 /* Gather some information about the blocks in this function. */
701 rename_info = XCNEWVEC (struct bb_rename_info, n_basic_blocks_for_fn (cfun));
702 i = 0;
703 FOR_EACH_BB_FN (bb, cfun)
705 struct bb_rename_info *ri = rename_info + i;
706 ri->bb = bb;
707 if (bb_mask != NULL && !bitmap_bit_p (bb_mask, bb->index))
708 bb->aux = NULL;
709 else
710 bb->aux = ri;
711 i++;
714 current_id = 0;
715 id_to_chain.create (0);
716 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
718 /* The order in which we visit blocks ensures that whenever
719 possible, we only process a block after at least one of its
720 predecessors, which provides a "seeding" effect to make the logic
721 in set_incoming_from_chain and init_rename_info useful. */
723 for (i = 0; i < n_bbs; i++)
725 basic_block bb1 = BASIC_BLOCK_FOR_FN (cfun, inverse_postorder[i]);
726 struct bb_rename_info *this_info;
727 bool success;
728 edge e;
729 edge_iterator ei;
730 int old_length = id_to_chain.length ();
732 this_info = (struct bb_rename_info *) bb1->aux;
733 if (this_info == NULL)
734 continue;
736 if (dump_file)
737 fprintf (dump_file, "\nprocessing block %d:\n", bb1->index);
739 init_rename_info (this_info, bb1);
741 success = build_def_use (bb1);
742 if (!success)
744 if (dump_file)
745 fprintf (dump_file, "failed\n");
746 bb1->aux = NULL;
747 id_to_chain.truncate (old_length);
748 current_id = old_length;
749 bitmap_clear (&this_info->incoming_open_chains_set);
750 open_chains = NULL;
751 if (insn_rr.exists ())
753 rtx_insn *insn;
754 FOR_BB_INSNS (bb1, insn)
756 insn_rr_info *p = &insn_rr[INSN_UID (insn)];
757 p->op_info = NULL;
760 continue;
763 if (dump_file)
764 dump_def_use_chain (old_length);
765 bitmap_copy (&this_info->open_chains_set, &open_chains_set);
767 /* Add successor blocks to the worklist if necessary, and record
768 data about our own open chains at the end of this block, which
769 will be used to pre-open chains when processing the successors. */
770 FOR_EACH_EDGE (e, ei, bb1->succs)
772 struct bb_rename_info *dest_ri;
773 struct du_head *chain;
775 if (dump_file)
776 fprintf (dump_file, "successor block %d\n", e->dest->index);
778 if (e->flags & (EDGE_EH | EDGE_ABNORMAL))
779 continue;
780 dest_ri = (struct bb_rename_info *)e->dest->aux;
781 if (dest_ri == NULL)
782 continue;
783 for (chain = open_chains; chain; chain = chain->next_chain)
784 set_incoming_from_chain (dest_ri, chain);
788 free (inverse_postorder);
790 /* Now, combine the chains data we have gathered across basic block
791 boundaries.
793 For every basic block, there may be chains open at the start, or at the
794 end. Rather than exclude them from renaming, we look for open chains
795 with matching registers at the other side of the CFG edge.
797 For a given chain using register R, open at the start of block B, we
798 must find an open chain using R on the other side of every edge leading
799 to B, if the register is live across this edge. In the code below,
800 N_PREDS_USED counts the number of edges where the register is live, and
801 N_PREDS_JOINED counts those where we found an appropriate chain for
802 joining.
804 We perform the analysis for both incoming and outgoing edges, but we
805 only need to merge once (in the second part, after verifying outgoing
806 edges). */
807 FOR_EACH_BB_FN (bb, cfun)
809 struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux;
810 unsigned j;
811 bitmap_iterator bi;
813 if (bb_ri == NULL)
814 continue;
816 if (dump_file)
817 fprintf (dump_file, "processing bb %d in edges\n", bb->index);
819 EXECUTE_IF_SET_IN_BITMAP (&bb_ri->incoming_open_chains_set, 0, j, bi)
821 edge e;
822 edge_iterator ei;
823 struct du_head *chain = regrename_chain_from_id (j);
824 int n_preds_used = 0, n_preds_joined = 0;
826 FOR_EACH_EDGE (e, ei, bb->preds)
828 struct bb_rename_info *src_ri;
829 unsigned k;
830 bitmap_iterator bi2;
831 HARD_REG_SET live;
832 bool success = false;
834 REG_SET_TO_HARD_REG_SET (live, df_get_live_out (e->src));
835 if (!range_overlaps_hard_reg_set_p (live, chain->regno,
836 chain->nregs))
837 continue;
838 n_preds_used++;
840 if (e->flags & (EDGE_EH | EDGE_ABNORMAL))
841 continue;
843 src_ri = (struct bb_rename_info *)e->src->aux;
844 if (src_ri == NULL)
845 continue;
847 EXECUTE_IF_SET_IN_BITMAP (&src_ri->open_chains_set,
848 0, k, bi2)
850 struct du_head *outgoing_chain = regrename_chain_from_id (k);
852 if (outgoing_chain->regno == chain->regno
853 && outgoing_chain->nregs == chain->nregs)
855 n_preds_joined++;
856 success = true;
857 break;
860 if (!success && dump_file)
861 fprintf (dump_file, "failure to match with pred block %d\n",
862 e->src->index);
864 if (n_preds_joined < n_preds_used)
866 if (dump_file)
867 fprintf (dump_file, "cannot rename chain %d\n", j);
868 chain->cannot_rename = 1;
872 FOR_EACH_BB_FN (bb, cfun)
874 struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux;
875 unsigned j;
876 bitmap_iterator bi;
878 if (bb_ri == NULL)
879 continue;
881 if (dump_file)
882 fprintf (dump_file, "processing bb %d out edges\n", bb->index);
884 EXECUTE_IF_SET_IN_BITMAP (&bb_ri->open_chains_set, 0, j, bi)
886 edge e;
887 edge_iterator ei;
888 struct du_head *chain = regrename_chain_from_id (j);
889 int n_succs_used = 0, n_succs_joined = 0;
891 FOR_EACH_EDGE (e, ei, bb->succs)
893 bool printed = false;
894 struct bb_rename_info *dest_ri;
895 unsigned k;
896 bitmap_iterator bi2;
897 HARD_REG_SET live;
899 REG_SET_TO_HARD_REG_SET (live, df_get_live_in (e->dest));
900 if (!range_overlaps_hard_reg_set_p (live, chain->regno,
901 chain->nregs))
902 continue;
904 n_succs_used++;
906 dest_ri = (struct bb_rename_info *)e->dest->aux;
907 if (dest_ri == NULL)
908 continue;
910 EXECUTE_IF_SET_IN_BITMAP (&dest_ri->incoming_open_chains_set,
911 0, k, bi2)
913 struct du_head *incoming_chain = regrename_chain_from_id (k);
915 if (incoming_chain->regno == chain->regno
916 && incoming_chain->nregs == chain->nregs)
918 if (dump_file)
920 if (!printed)
921 fprintf (dump_file,
922 "merging blocks for edge %d -> %d\n",
923 e->src->index, e->dest->index);
924 printed = true;
925 fprintf (dump_file,
926 " merging chains %d (->%d) and %d (->%d) [%s]\n",
927 k, incoming_chain->id, j, chain->id,
928 reg_names[incoming_chain->regno]);
931 merge_chains (chain, incoming_chain);
932 n_succs_joined++;
933 break;
937 if (n_succs_joined < n_succs_used)
939 if (dump_file)
940 fprintf (dump_file, "cannot rename chain %d\n",
942 chain->cannot_rename = 1;
947 free (rename_info);
949 FOR_EACH_BB_FN (bb, cfun)
950 bb->aux = NULL;
953 /* Attempt to replace all uses of the register in the chain beginning with
954 HEAD with REG. Returns true on success and false if the replacement is
955 rejected because the insns would not validate. The latter can happen
956 e.g. if a match_parallel predicate enforces restrictions on register
957 numbering in its subpatterns. */
959 bool
960 regrename_do_replace (struct du_head *head, int reg)
962 struct du_chain *chain;
963 unsigned int base_regno = head->regno;
964 machine_mode mode;
966 for (chain = head->first; chain; chain = chain->next_use)
968 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
969 struct reg_attrs *attr = REG_ATTRS (*chain->loc);
970 int reg_ptr = REG_POINTER (*chain->loc);
972 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
973 validate_change (chain->insn, &(INSN_VAR_LOCATION_LOC (chain->insn)),
974 gen_rtx_UNKNOWN_VAR_LOC (), true);
975 else
977 validate_change (chain->insn, chain->loc,
978 gen_raw_REG (GET_MODE (*chain->loc), reg), true);
979 if (regno >= FIRST_PSEUDO_REGISTER)
980 ORIGINAL_REGNO (*chain->loc) = regno;
981 REG_ATTRS (*chain->loc) = attr;
982 REG_POINTER (*chain->loc) = reg_ptr;
986 if (!apply_change_group ())
987 return false;
989 mode = GET_MODE (*head->first->loc);
990 head->renamed = 1;
991 head->regno = reg;
992 head->nregs = hard_regno_nregs[reg][mode];
993 return true;
997 /* True if we found a register with a size mismatch, which means that we
998 can't track its lifetime accurately. If so, we abort the current block
999 without renaming. */
1000 static bool fail_current_block;
1002 /* Return true if OP is a reg for which all bits are set in PSET, false
1003 if all bits are clear.
1004 In other cases, set fail_current_block and return false. */
1006 static bool
1007 verify_reg_in_set (rtx op, HARD_REG_SET *pset)
1009 unsigned regno, nregs;
1010 bool all_live, all_dead;
1011 if (!REG_P (op))
1012 return false;
1014 regno = REGNO (op);
1015 nregs = REG_NREGS (op);
1016 all_live = all_dead = true;
1017 while (nregs-- > 0)
1018 if (TEST_HARD_REG_BIT (*pset, regno + nregs))
1019 all_dead = false;
1020 else
1021 all_live = false;
1022 if (!all_dead && !all_live)
1024 fail_current_block = true;
1025 return false;
1027 return all_live;
1030 /* Return true if OP is a reg that is being tracked already in some form.
1031 May set fail_current_block if it sees an unhandled case of overlap. */
1033 static bool
1034 verify_reg_tracked (rtx op)
1036 return (verify_reg_in_set (op, &live_hard_regs)
1037 || verify_reg_in_set (op, &live_in_chains));
1040 /* Called through note_stores. DATA points to a rtx_code, either SET or
1041 CLOBBER, which tells us which kind of rtx to look at. If we have a
1042 match, record the set register in live_hard_regs and in the hard_conflicts
1043 bitmap of open chains. */
1045 static void
1046 note_sets_clobbers (rtx x, const_rtx set, void *data)
1048 enum rtx_code code = *(enum rtx_code *)data;
1049 struct du_head *chain;
1051 if (GET_CODE (x) == SUBREG)
1052 x = SUBREG_REG (x);
1053 if (!REG_P (x) || GET_CODE (set) != code)
1054 return;
1055 /* There must not be pseudos at this point. */
1056 gcc_assert (HARD_REGISTER_P (x));
1057 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
1058 for (chain = open_chains; chain; chain = chain->next_chain)
1059 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
1062 static void
1063 scan_rtx_reg (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action,
1064 enum op_type type)
1066 struct du_head **p;
1067 rtx x = *loc;
1068 unsigned this_regno = REGNO (x);
1069 int this_nregs = REG_NREGS (x);
1071 if (action == mark_write)
1073 if (type == OP_OUT)
1075 du_head_p c;
1076 rtx pat = PATTERN (insn);
1078 c = create_new_chain (this_regno, this_nregs, loc, insn, cl);
1080 /* We try to tie chains in a move instruction for
1081 a single output. */
1082 if (recog_data.n_operands == 2
1083 && GET_CODE (pat) == SET
1084 && GET_CODE (SET_DEST (pat)) == REG
1085 && GET_CODE (SET_SRC (pat)) == REG
1086 && terminated_this_insn
1087 && terminated_this_insn->nregs
1088 == REG_NREGS (recog_data.operand[1]))
1090 gcc_assert (terminated_this_insn->regno
1091 == REGNO (recog_data.operand[1]));
1093 c->tied_chain = terminated_this_insn;
1094 terminated_this_insn->tied_chain = c;
1096 if (dump_file)
1097 fprintf (dump_file, "Tying chain %s (%d) with %s (%d)\n",
1098 reg_names[c->regno], c->id,
1099 reg_names[terminated_this_insn->regno],
1100 terminated_this_insn->id);
1104 return;
1107 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
1108 return;
1110 for (p = &open_chains; *p;)
1112 struct du_head *head = *p;
1113 struct du_head *next = head->next_chain;
1114 int exact_match = (head->regno == this_regno
1115 && head->nregs == this_nregs);
1116 int superset = (this_regno <= head->regno
1117 && this_regno + this_nregs >= head->regno + head->nregs);
1118 int subset = (this_regno >= head->regno
1119 && this_regno + this_nregs <= head->regno + head->nregs);
1121 if (!bitmap_bit_p (&open_chains_set, head->id)
1122 || head->regno + head->nregs <= this_regno
1123 || this_regno + this_nregs <= head->regno)
1125 p = &head->next_chain;
1126 continue;
1129 if (action == mark_read || action == mark_access)
1131 /* ??? Class NO_REGS can happen if the md file makes use of
1132 EXTRA_CONSTRAINTS to match registers. Which is arguably
1133 wrong, but there we are. */
1135 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
1137 if (dump_file)
1138 fprintf (dump_file,
1139 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1140 reg_names[head->regno], head->id, INSN_UID (insn),
1141 scan_actions_name[(int) action]);
1142 head->cannot_rename = 1;
1143 if (superset)
1145 unsigned nregs = this_nregs;
1146 head->regno = this_regno;
1147 head->nregs = this_nregs;
1148 while (nregs-- > 0)
1149 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
1150 if (dump_file)
1151 fprintf (dump_file,
1152 "Widening register in chain %s (%d) at insn %d\n",
1153 reg_names[head->regno], head->id, INSN_UID (insn));
1155 else if (!subset)
1157 fail_current_block = true;
1158 if (dump_file)
1159 fprintf (dump_file,
1160 "Failing basic block due to unhandled overlap\n");
1163 else
1165 struct du_chain *this_du;
1166 this_du = XOBNEW (&rename_obstack, struct du_chain);
1167 this_du->next_use = 0;
1168 this_du->loc = loc;
1169 this_du->insn = insn;
1170 this_du->cl = cl;
1171 if (head->first == NULL)
1172 head->first = this_du;
1173 else
1174 head->last->next_use = this_du;
1175 record_operand_use (head, this_du);
1176 head->last = this_du;
1178 /* Avoid adding the same location in a DEBUG_INSN multiple times,
1179 which could happen with non-exact overlap. */
1180 if (DEBUG_INSN_P (insn))
1181 return;
1182 /* Otherwise, find any other chains that do not match exactly;
1183 ensure they all get marked unrenamable. */
1184 p = &head->next_chain;
1185 continue;
1188 /* Whether the terminated chain can be used for renaming
1189 depends on the action and this being an exact match.
1190 In either case, we remove this element from open_chains. */
1192 if ((action == terminate_dead || action == terminate_write)
1193 && (superset || subset))
1195 unsigned nregs;
1197 if (subset && !superset)
1198 head->cannot_rename = 1;
1199 bitmap_clear_bit (&open_chains_set, head->id);
1201 nregs = head->nregs;
1202 while (nregs-- > 0)
1204 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
1205 if (subset && !superset
1206 && (head->regno + nregs < this_regno
1207 || head->regno + nregs >= this_regno + this_nregs))
1208 SET_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
1211 if (action == terminate_dead)
1212 terminated_this_insn = *p;
1213 *p = next;
1214 if (dump_file)
1215 fprintf (dump_file,
1216 "Closing chain %s (%d) at insn %d (%s%s)\n",
1217 reg_names[head->regno], head->id, INSN_UID (insn),
1218 scan_actions_name[(int) action],
1219 superset ? ", superset" : subset ? ", subset" : "");
1221 else if (action == terminate_dead || action == terminate_write)
1223 /* In this case, tracking liveness gets too hard. Fail the
1224 entire basic block. */
1225 if (dump_file)
1226 fprintf (dump_file,
1227 "Failing basic block due to unhandled overlap\n");
1228 fail_current_block = true;
1229 return;
1231 else
1233 head->cannot_rename = 1;
1234 if (dump_file)
1235 fprintf (dump_file,
1236 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1237 reg_names[head->regno], head->id, INSN_UID (insn),
1238 scan_actions_name[(int) action]);
1239 p = &head->next_chain;
1244 /* A wrapper around base_reg_class which returns ALL_REGS if INSN is a
1245 DEBUG_INSN. The arguments MODE, AS, CODE and INDEX_CODE are as for
1246 base_reg_class. */
1248 static reg_class
1249 base_reg_class_for_rename (rtx_insn *insn, machine_mode mode, addr_space_t as,
1250 rtx_code code, rtx_code index_code)
1252 if (DEBUG_INSN_P (insn))
1253 return ALL_REGS;
1254 return base_reg_class (mode, as, code, index_code);
1257 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1258 BASE_REG_CLASS depending on how the register is being considered. */
1260 static void
1261 scan_rtx_address (rtx_insn *insn, rtx *loc, enum reg_class cl,
1262 enum scan_actions action, machine_mode mode,
1263 addr_space_t as)
1265 rtx x = *loc;
1266 RTX_CODE code = GET_CODE (x);
1267 const char *fmt;
1268 int i, j;
1270 if (action == mark_write || action == mark_access)
1271 return;
1273 switch (code)
1275 case PLUS:
1277 rtx orig_op0 = XEXP (x, 0);
1278 rtx orig_op1 = XEXP (x, 1);
1279 RTX_CODE code0 = GET_CODE (orig_op0);
1280 RTX_CODE code1 = GET_CODE (orig_op1);
1281 rtx op0 = orig_op0;
1282 rtx op1 = orig_op1;
1283 rtx *locI = NULL;
1284 rtx *locB = NULL;
1285 enum rtx_code index_code = SCRATCH;
1287 if (GET_CODE (op0) == SUBREG)
1289 op0 = SUBREG_REG (op0);
1290 code0 = GET_CODE (op0);
1293 if (GET_CODE (op1) == SUBREG)
1295 op1 = SUBREG_REG (op1);
1296 code1 = GET_CODE (op1);
1299 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1300 || code0 == ZERO_EXTEND || code1 == MEM)
1302 locI = &XEXP (x, 0);
1303 locB = &XEXP (x, 1);
1304 index_code = GET_CODE (*locI);
1306 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1307 || code1 == ZERO_EXTEND || code0 == MEM)
1309 locI = &XEXP (x, 1);
1310 locB = &XEXP (x, 0);
1311 index_code = GET_CODE (*locI);
1313 else if (code0 == CONST_INT || code0 == CONST
1314 || code0 == SYMBOL_REF || code0 == LABEL_REF)
1316 locB = &XEXP (x, 1);
1317 index_code = GET_CODE (XEXP (x, 0));
1319 else if (code1 == CONST_INT || code1 == CONST
1320 || code1 == SYMBOL_REF || code1 == LABEL_REF)
1322 locB = &XEXP (x, 0);
1323 index_code = GET_CODE (XEXP (x, 1));
1325 else if (code0 == REG && code1 == REG)
1327 int index_op;
1328 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
1330 if (REGNO_OK_FOR_INDEX_P (regno1)
1331 && regno_ok_for_base_p (regno0, mode, as, PLUS, REG))
1332 index_op = 1;
1333 else if (REGNO_OK_FOR_INDEX_P (regno0)
1334 && regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
1335 index_op = 0;
1336 else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG)
1337 || REGNO_OK_FOR_INDEX_P (regno1))
1338 index_op = 1;
1339 else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
1340 index_op = 0;
1341 else
1342 index_op = 1;
1344 locI = &XEXP (x, index_op);
1345 locB = &XEXP (x, !index_op);
1346 index_code = GET_CODE (*locI);
1348 else if (code0 == REG)
1350 locI = &XEXP (x, 0);
1351 locB = &XEXP (x, 1);
1352 index_code = GET_CODE (*locI);
1354 else if (code1 == REG)
1356 locI = &XEXP (x, 1);
1357 locB = &XEXP (x, 0);
1358 index_code = GET_CODE (*locI);
1361 if (locI)
1363 reg_class iclass = DEBUG_INSN_P (insn) ? ALL_REGS : INDEX_REG_CLASS;
1364 scan_rtx_address (insn, locI, iclass, action, mode, as);
1366 if (locB)
1368 reg_class bclass = base_reg_class_for_rename (insn, mode, as, PLUS,
1369 index_code);
1370 scan_rtx_address (insn, locB, bclass, action, mode, as);
1372 return;
1375 case POST_INC:
1376 case POST_DEC:
1377 case POST_MODIFY:
1378 case PRE_INC:
1379 case PRE_DEC:
1380 case PRE_MODIFY:
1381 /* If the target doesn't claim to handle autoinc, this must be
1382 something special, like a stack push. Kill this chain. */
1383 if (!AUTO_INC_DEC)
1384 action = mark_all_read;
1386 break;
1388 case MEM:
1390 reg_class bclass = base_reg_class_for_rename (insn, GET_MODE (x),
1391 MEM_ADDR_SPACE (x),
1392 MEM, SCRATCH);
1393 scan_rtx_address (insn, &XEXP (x, 0), bclass, action, GET_MODE (x),
1394 MEM_ADDR_SPACE (x));
1396 return;
1398 case REG:
1399 scan_rtx_reg (insn, loc, cl, action, OP_IN);
1400 return;
1402 default:
1403 break;
1406 fmt = GET_RTX_FORMAT (code);
1407 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1409 if (fmt[i] == 'e')
1410 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode, as);
1411 else if (fmt[i] == 'E')
1412 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1413 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode, as);
1417 static void
1418 scan_rtx (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action,
1419 enum op_type type)
1421 const char *fmt;
1422 rtx x = *loc;
1423 enum rtx_code code = GET_CODE (x);
1424 int i, j;
1426 code = GET_CODE (x);
1427 switch (code)
1429 case CONST:
1430 CASE_CONST_ANY:
1431 case SYMBOL_REF:
1432 case LABEL_REF:
1433 case CC0:
1434 case PC:
1435 return;
1437 case REG:
1438 scan_rtx_reg (insn, loc, cl, action, type);
1439 return;
1441 case MEM:
1443 reg_class bclass = base_reg_class_for_rename (insn, GET_MODE (x),
1444 MEM_ADDR_SPACE (x),
1445 MEM, SCRATCH);
1447 scan_rtx_address (insn, &XEXP (x, 0), bclass, action, GET_MODE (x),
1448 MEM_ADDR_SPACE (x));
1450 return;
1452 case SET:
1453 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
1454 scan_rtx (insn, &SET_DEST (x), cl, action,
1455 (GET_CODE (PATTERN (insn)) == COND_EXEC
1456 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
1457 return;
1459 case STRICT_LOW_PART:
1460 scan_rtx (insn, &XEXP (x, 0), cl, action,
1461 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT);
1462 return;
1464 case ZERO_EXTRACT:
1465 case SIGN_EXTRACT:
1466 scan_rtx (insn, &XEXP (x, 0), cl, action,
1467 (type == OP_IN ? OP_IN :
1468 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT));
1469 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
1470 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
1471 return;
1473 case POST_INC:
1474 case PRE_INC:
1475 case POST_DEC:
1476 case PRE_DEC:
1477 case POST_MODIFY:
1478 case PRE_MODIFY:
1479 /* Should only happen inside MEM. */
1480 gcc_unreachable ();
1482 case CLOBBER:
1483 scan_rtx (insn, &SET_DEST (x), cl, action,
1484 (GET_CODE (PATTERN (insn)) == COND_EXEC
1485 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
1486 return;
1488 case EXPR_LIST:
1489 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
1490 if (XEXP (x, 1))
1491 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
1492 return;
1494 default:
1495 break;
1498 fmt = GET_RTX_FORMAT (code);
1499 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1501 if (fmt[i] == 'e')
1502 scan_rtx (insn, &XEXP (x, i), cl, action, type);
1503 else if (fmt[i] == 'E')
1504 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1505 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
1509 /* Hide operands of the current insn (of which there are N_OPS) by
1510 substituting cc0 for them.
1511 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1512 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1513 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1514 and earlyclobbers. */
1516 static void
1517 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
1518 unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
1520 int i;
1521 const operand_alternative *op_alt = which_op_alt ();
1522 for (i = 0; i < n_ops; i++)
1524 old_operands[i] = recog_data.operand[i];
1525 /* Don't squash match_operator or match_parallel here, since
1526 we don't know that all of the contained registers are
1527 reachable by proper operands. */
1528 if (recog_data.constraints[i][0] == '\0')
1529 continue;
1530 if (do_not_hide & (1 << i))
1531 continue;
1532 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
1533 || op_alt[i].earlyclobber)
1534 *recog_data.operand_loc[i] = cc0_rtx;
1536 for (i = 0; i < recog_data.n_dups; i++)
1538 int opn = recog_data.dup_num[i];
1539 old_dups[i] = *recog_data.dup_loc[i];
1540 if (do_not_hide & (1 << opn))
1541 continue;
1542 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
1543 || op_alt[opn].earlyclobber)
1544 *recog_data.dup_loc[i] = cc0_rtx;
1548 /* Undo the substitution performed by hide_operands. INSN is the insn we
1549 are processing; the arguments are the same as in hide_operands. */
1551 static void
1552 restore_operands (rtx_insn *insn, int n_ops, rtx *old_operands, rtx *old_dups)
1554 int i;
1555 for (i = 0; i < recog_data.n_dups; i++)
1556 *recog_data.dup_loc[i] = old_dups[i];
1557 for (i = 0; i < n_ops; i++)
1558 *recog_data.operand_loc[i] = old_operands[i];
1559 if (recog_data.n_dups)
1560 df_insn_rescan (insn);
1563 /* For each output operand of INSN, call scan_rtx to create a new
1564 open chain. Do this only for normal or earlyclobber outputs,
1565 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
1566 record information about the operands in the insn. */
1568 static void
1569 record_out_operands (rtx_insn *insn, bool earlyclobber, insn_rr_info *insn_info)
1571 int n_ops = recog_data.n_operands;
1572 const operand_alternative *op_alt = which_op_alt ();
1574 int i;
1576 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1578 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1579 rtx *loc = (i < n_ops
1580 ? recog_data.operand_loc[opn]
1581 : recog_data.dup_loc[i - n_ops]);
1582 rtx op = *loc;
1583 enum reg_class cl = alternative_class (op_alt, opn);
1585 struct du_head *prev_open;
1587 if (recog_data.operand_type[opn] != OP_OUT
1588 || op_alt[opn].earlyclobber != earlyclobber)
1589 continue;
1591 if (insn_info)
1592 cur_operand = insn_info->op_info + i;
1594 prev_open = open_chains;
1595 if (earlyclobber)
1596 scan_rtx (insn, loc, cl, terminate_write, OP_OUT);
1597 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
1599 /* ??? Many targets have output constraints on the SET_DEST
1600 of a call insn, which is stupid, since these are certainly
1601 ABI defined hard registers. For these, and for asm operands
1602 that originally referenced hard registers, we must record that
1603 the chain cannot be renamed. */
1604 if (CALL_P (insn)
1605 || (asm_noperands (PATTERN (insn)) > 0
1606 && REG_P (op)
1607 && REGNO (op) == ORIGINAL_REGNO (op)))
1609 if (prev_open != open_chains)
1610 open_chains->cannot_rename = 1;
1613 cur_operand = NULL;
1616 /* Build def/use chain. */
1618 static bool
1619 build_def_use (basic_block bb)
1621 rtx_insn *insn;
1622 unsigned HOST_WIDE_INT untracked_operands;
1624 fail_current_block = false;
1626 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1628 if (NONDEBUG_INSN_P (insn))
1630 int n_ops;
1631 rtx note;
1632 rtx old_operands[MAX_RECOG_OPERANDS];
1633 rtx old_dups[MAX_DUP_OPERANDS];
1634 int i;
1635 int predicated;
1636 enum rtx_code set_code = SET;
1637 enum rtx_code clobber_code = CLOBBER;
1638 insn_rr_info *insn_info = NULL;
1639 terminated_this_insn = NULL;
1641 /* Process the insn, determining its effect on the def-use
1642 chains and live hard registers. We perform the following
1643 steps with the register references in the insn, simulating
1644 its effect:
1645 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1646 by creating chains and marking hard regs live.
1647 (2) Any read outside an operand causes any chain it overlaps
1648 with to be marked unrenamable.
1649 (3) Any read inside an operand is added if there's already
1650 an open chain for it.
1651 (4) For any REG_DEAD note we find, close open chains that
1652 overlap it.
1653 (5) For any non-earlyclobber write we find, close open chains
1654 that overlap it.
1655 (6) For any non-earlyclobber write we find in an operand, make
1656 a new chain or mark the hard register as live.
1657 (7) For any REG_UNUSED, close any chains we just opened.
1659 We cannot deal with situations where we track a reg in one mode
1660 and see a reference in another mode; these will cause the chain
1661 to be marked unrenamable or even cause us to abort the entire
1662 basic block. */
1664 extract_constrain_insn (insn);
1665 preprocess_constraints (insn);
1666 const operand_alternative *op_alt = which_op_alt ();
1667 n_ops = recog_data.n_operands;
1668 untracked_operands = 0;
1670 if (insn_rr.exists ())
1672 insn_info = &insn_rr[INSN_UID (insn)];
1673 insn_info->op_info = XOBNEWVEC (&rename_obstack, operand_rr_info,
1674 recog_data.n_operands);
1675 memset (insn_info->op_info, 0,
1676 sizeof (operand_rr_info) * recog_data.n_operands);
1679 /* Simplify the code below by promoting OP_OUT to OP_INOUT in
1680 predicated instructions, but only for register operands
1681 that are already tracked, so that we can create a chain
1682 when the first SET makes a register live. */
1684 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1685 for (i = 0; i < n_ops; ++i)
1687 rtx op = recog_data.operand[i];
1688 int matches = op_alt[i].matches;
1689 if (matches >= 0 || op_alt[i].matched >= 0
1690 || (predicated && recog_data.operand_type[i] == OP_OUT))
1692 recog_data.operand_type[i] = OP_INOUT;
1693 /* A special case to deal with instruction patterns that
1694 have matching operands with different modes. If we're
1695 not already tracking such a reg, we won't start here,
1696 and we must instead make sure to make the operand visible
1697 to the machinery that tracks hard registers. */
1698 if (matches >= 0
1699 && (GET_MODE_SIZE (recog_data.operand_mode[i])
1700 != GET_MODE_SIZE (recog_data.operand_mode[matches]))
1701 && !verify_reg_in_set (op, &live_in_chains))
1703 untracked_operands |= 1 << i;
1704 untracked_operands |= 1 << matches;
1707 #ifdef STACK_REGS
1708 if (regstack_completed
1709 && REG_P (op)
1710 && IN_RANGE (REGNO (op), FIRST_STACK_REG, LAST_STACK_REG))
1711 untracked_operands |= 1 << i;
1712 #endif
1713 /* If there's an in-out operand with a register that is not
1714 being tracked at all yet, open a chain. */
1715 if (recog_data.operand_type[i] == OP_INOUT
1716 && !(untracked_operands & (1 << i))
1717 && REG_P (op)
1718 && !verify_reg_tracked (op))
1719 create_new_chain (REGNO (op), REG_NREGS (op), NULL, NULL,
1720 NO_REGS);
1723 if (fail_current_block)
1724 break;
1726 /* Step 1a: Mark hard registers that are clobbered in this insn,
1727 outside an operand, as live. */
1728 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1729 false);
1730 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
1731 restore_operands (insn, n_ops, old_operands, old_dups);
1733 /* Step 1b: Begin new chains for earlyclobbered writes inside
1734 operands. */
1735 record_out_operands (insn, true, insn_info);
1737 /* Step 2: Mark chains for which we have reads outside operands
1738 as unrenamable.
1739 We do this by munging all operands into CC0, and closing
1740 everything remaining. */
1742 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1743 false);
1744 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1745 restore_operands (insn, n_ops, old_operands, old_dups);
1747 /* Step 2B: Can't rename function call argument registers. */
1748 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1749 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1750 NO_REGS, mark_all_read, OP_IN);
1752 /* Step 2C: Can't rename asm operands that were originally
1753 hard registers. */
1754 if (asm_noperands (PATTERN (insn)) > 0)
1755 for (i = 0; i < n_ops; i++)
1757 rtx *loc = recog_data.operand_loc[i];
1758 rtx op = *loc;
1760 if (REG_P (op)
1761 && REGNO (op) == ORIGINAL_REGNO (op)
1762 && (recog_data.operand_type[i] == OP_IN
1763 || recog_data.operand_type[i] == OP_INOUT))
1764 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1767 /* Step 3: Append to chains for reads inside operands. */
1768 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1770 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1771 rtx *loc = (i < n_ops
1772 ? recog_data.operand_loc[opn]
1773 : recog_data.dup_loc[i - n_ops]);
1774 enum reg_class cl = alternative_class (op_alt, opn);
1775 enum op_type type = recog_data.operand_type[opn];
1777 /* Don't scan match_operand here, since we've no reg class
1778 information to pass down. Any operands that we could
1779 substitute in will be represented elsewhere. */
1780 if (recog_data.constraints[opn][0] == '\0'
1781 || untracked_operands & (1 << opn))
1782 continue;
1784 if (insn_info)
1785 cur_operand = i == opn ? insn_info->op_info + i : NULL;
1786 if (op_alt[opn].is_address)
1787 scan_rtx_address (insn, loc, cl, mark_read,
1788 VOIDmode, ADDR_SPACE_GENERIC);
1789 else
1790 scan_rtx (insn, loc, cl, mark_read, type);
1792 cur_operand = NULL;
1794 /* Step 3B: Record updates for regs in REG_INC notes, and
1795 source regs in REG_FRAME_RELATED_EXPR notes. */
1796 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1797 if (REG_NOTE_KIND (note) == REG_INC
1798 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1799 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1800 OP_INOUT);
1802 /* Step 4: Close chains for registers that die here, unless
1803 the register is mentioned in a REG_UNUSED note. In that
1804 case we keep the chain open until step #7 below to ensure
1805 it conflicts with other output operands of this insn.
1806 See PR 52573. Arguably the insn should not have both
1807 notes; it has proven difficult to fix that without
1808 other undesirable side effects. */
1809 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1810 if (REG_NOTE_KIND (note) == REG_DEAD
1811 && !find_regno_note (insn, REG_UNUSED, REGNO (XEXP (note, 0))))
1813 remove_from_hard_reg_set (&live_hard_regs,
1814 GET_MODE (XEXP (note, 0)),
1815 REGNO (XEXP (note, 0)));
1816 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1817 OP_IN);
1820 /* Step 4B: If this is a call, any chain live at this point
1821 requires a caller-saved reg. */
1822 if (CALL_P (insn))
1824 struct du_head *p;
1825 for (p = open_chains; p; p = p->next_chain)
1826 p->need_caller_save_reg = 1;
1829 /* Step 5: Close open chains that overlap writes. Similar to
1830 step 2, we hide in-out operands, since we do not want to
1831 close these chains. We also hide earlyclobber operands,
1832 since we've opened chains for them in step 1, and earlier
1833 chains they would overlap with must have been closed at
1834 the previous insn at the latest, as such operands cannot
1835 possibly overlap with any input operands. */
1837 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1838 true);
1839 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1840 restore_operands (insn, n_ops, old_operands, old_dups);
1842 /* Step 6a: Mark hard registers that are set in this insn,
1843 outside an operand, as live. */
1844 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1845 false);
1846 note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
1847 restore_operands (insn, n_ops, old_operands, old_dups);
1849 /* Step 6b: Begin new chains for writes inside operands. */
1850 record_out_operands (insn, false, insn_info);
1852 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1853 notes for update. */
1854 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1855 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1856 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1857 OP_INOUT);
1859 /* Step 7: Close chains for registers that were never
1860 really used here. */
1861 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1862 if (REG_NOTE_KIND (note) == REG_UNUSED)
1864 remove_from_hard_reg_set (&live_hard_regs,
1865 GET_MODE (XEXP (note, 0)),
1866 REGNO (XEXP (note, 0)));
1867 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1868 OP_IN);
1871 else if (DEBUG_INSN_P (insn)
1872 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1874 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1875 ALL_REGS, mark_read, OP_IN);
1877 if (insn == BB_END (bb))
1878 break;
1881 if (fail_current_block)
1882 return false;
1884 return true;
1887 /* Initialize the register renamer. If INSN_INFO is true, ensure that
1888 insn_rr is nonnull. */
1889 void
1890 regrename_init (bool insn_info)
1892 gcc_obstack_init (&rename_obstack);
1893 insn_rr.create (0);
1894 if (insn_info)
1895 insn_rr.safe_grow_cleared (get_max_uid ());
1898 /* Free all global data used by the register renamer. */
1899 void
1900 regrename_finish (void)
1902 insn_rr.release ();
1903 free_chain_data ();
1904 obstack_free (&rename_obstack, NULL);
1907 /* Perform register renaming on the current function. */
1909 static unsigned int
1910 regrename_optimize (void)
1912 df_set_flags (DF_LR_RUN_DCE);
1913 df_note_add_problem ();
1914 df_analyze ();
1915 df_set_flags (DF_DEFER_INSN_RESCAN);
1917 regrename_init (false);
1919 regrename_analyze (NULL);
1921 rename_chains ();
1923 regrename_finish ();
1925 return 0;
1928 namespace {
1930 const pass_data pass_data_regrename =
1932 RTL_PASS, /* type */
1933 "rnreg", /* name */
1934 OPTGROUP_NONE, /* optinfo_flags */
1935 TV_RENAME_REGISTERS, /* tv_id */
1936 0, /* properties_required */
1937 0, /* properties_provided */
1938 0, /* properties_destroyed */
1939 0, /* todo_flags_start */
1940 TODO_df_finish, /* todo_flags_finish */
1943 class pass_regrename : public rtl_opt_pass
1945 public:
1946 pass_regrename (gcc::context *ctxt)
1947 : rtl_opt_pass (pass_data_regrename, ctxt)
1950 /* opt_pass methods: */
1951 virtual bool gate (function *)
1953 return (optimize > 0 && (flag_rename_registers));
1956 virtual unsigned int execute (function *) { return regrename_optimize (); }
1958 }; // class pass_regrename
1960 } // anon namespace
1962 rtl_opt_pass *
1963 make_pass_regrename (gcc::context *ctxt)
1965 return new pass_regrename (ctxt);