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