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