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