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