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