Line data Source code
1 : /* Build live ranges for pseudos.
2 : Copyright (C) 2010-2026 Free Software Foundation, Inc.
3 : Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 :
22 : /* This file contains code to build pseudo live-ranges (analogous
23 : structures used in IRA, so read comments about the live-ranges
24 : there) and other info necessary for other passes to assign
25 : hard-registers to pseudos, coalesce the spilled pseudos, and assign
26 : stack memory slots to spilled pseudos. */
27 :
28 : #include "config.h"
29 : #include "system.h"
30 : #include "coretypes.h"
31 : #include "backend.h"
32 : #include "rtl.h"
33 : #include "tree.h"
34 : #include "predict.h"
35 : #include "df.h"
36 : #include "memmodel.h"
37 : #include "tm_p.h"
38 : #include "insn-config.h"
39 : #include "regs.h"
40 : #include "ira.h"
41 : #include "ira-int.h"
42 : #include "recog.h"
43 : #include "cfganal.h"
44 : #include "sparseset.h"
45 : #include "lra-int.h"
46 : #include "target.h"
47 : #include "function-abi.h"
48 :
49 : /* Program points are enumerated by numbers from range
50 : 0..LRA_LIVE_MAX_POINT-1. There are approximately two times more
51 : program points than insns. Program points are places in the
52 : program where liveness info can be changed. In most general case
53 : (there are more complicated cases too) some program points
54 : correspond to places where input operand dies and other ones
55 : correspond to places where output operands are born. */
56 : int lra_live_max_point;
57 :
58 : /* Accumulated execution frequency of all references for each hard
59 : register. */
60 : int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER];
61 :
62 : /* A global flag whose true value says to build live ranges for all
63 : pseudos, otherwise the live ranges only for pseudos got memory is
64 : build. True value means also building copies and setting up hard
65 : register preferences. The complete info is necessary for
66 : assignment, rematerialization and spill to register passes. The
67 : complete info is not needed for the coalescing and spill to memory
68 : passes. */
69 : static bool complete_info_p;
70 :
71 : /* Pseudos live at current point in the RTL scan. */
72 : static sparseset pseudos_live;
73 :
74 : /* Pseudos probably living through calls and setjumps. As setjump is
75 : a call too, if a bit in PSEUDOS_LIVE_THROUGH_SETJUMPS is set up
76 : then the corresponding bit in PSEUDOS_LIVE_THROUGH_CALLS is set up
77 : too. These data are necessary for cases when only one subreg of a
78 : multi-reg pseudo is set up after a call. So we decide it is
79 : probably live when traversing bb backward. We are sure about
80 : living when we see its usage or definition of the pseudo. */
81 : static sparseset pseudos_live_through_calls;
82 : static sparseset pseudos_live_through_setjumps;
83 :
84 : /* Set of hard regs (except eliminable ones) currently live. */
85 : static HARD_REG_SET hard_regs_live;
86 :
87 : /* Set of pseudos and hard registers start living/dying in the current
88 : insn. These sets are used to update REG_DEAD and REG_UNUSED notes
89 : in the insn. */
90 : static sparseset start_living, start_dying;
91 :
92 : /* Set of pseudos and hard regs dead and unused in the current
93 : insn. */
94 : static sparseset unused_set, dead_set;
95 :
96 : /* Bitmap used for holding intermediate bitmap operation results. */
97 : static bitmap_head temp_bitmap;
98 :
99 : /* Pool for pseudo live ranges. */
100 : static object_allocator<lra_live_range> lra_live_range_pool ("live ranges");
101 :
102 : /* Free live range list LR. */
103 : static void
104 339772423 : free_live_range_list (lra_live_range_t lr)
105 : {
106 339772423 : lra_live_range_t next;
107 :
108 444752609 : while (lr != NULL)
109 : {
110 104980186 : next = lr->next;
111 104980186 : lra_live_range_pool.remove (lr);
112 104980186 : lr = next;
113 : }
114 339772423 : }
115 :
116 : /* Reset and release live range list LR. */
117 : void
118 0 : lra_reset_live_range_list (lra_live_range_t &lr)
119 : {
120 0 : lra_live_range_t first = lr;
121 0 : lr = NULL;
122 0 : free_live_range_list (first);
123 0 : }
124 :
125 : /* Create and return pseudo live range with given attributes. */
126 : static lra_live_range_t
127 115648225 : create_live_range (int regno, int start, int finish, lra_live_range_t next)
128 : {
129 0 : lra_live_range_t p = lra_live_range_pool.allocate ();
130 115648225 : p->regno = regno;
131 115648225 : p->start = start;
132 115648225 : p->finish = finish;
133 115648225 : p->next = next;
134 115648225 : return p;
135 : }
136 :
137 : /* Copy live range R and return the result. */
138 : static lra_live_range_t
139 2160740 : copy_live_range (lra_live_range_t r)
140 : {
141 2160740 : return new (lra_live_range_pool) lra_live_range (*r);
142 : }
143 :
144 : /* Copy live range list given by its head R and return the result. */
145 : lra_live_range_t
146 1454118 : lra_copy_live_range_list (lra_live_range_t r)
147 : {
148 1454118 : lra_live_range_t p, first, *chain;
149 :
150 1454118 : first = NULL;
151 3614858 : for (chain = &first; r != NULL; r = r->next)
152 : {
153 2160740 : p = copy_live_range (r);
154 2160740 : *chain = p;
155 2160740 : chain = &p->next;
156 : }
157 1454118 : return first;
158 : }
159 :
160 : /* Merge *non-intersected* ranges R1 and R2 and returns the result.
161 : The function maintains the order of ranges and tries to minimize
162 : size of the result range list. Ranges R1 and R2 may not be used
163 : after the call. */
164 : lra_live_range_t
165 1454118 : lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
166 : {
167 1454118 : lra_live_range_t first, last;
168 :
169 1454118 : if (r1 == NULL)
170 : return r2;
171 680596 : if (r2 == NULL)
172 : return r1;
173 5829231 : for (first = last = NULL; r1 != NULL && r2 != NULL;)
174 : {
175 5148635 : if (r1->start < r2->start)
176 420669 : std::swap (r1, r2);
177 :
178 5148635 : if (r1->start == r2->finish + 1)
179 : {
180 : /* Joint ranges: merge r1 and r2 into r1. */
181 45788 : r1->start = r2->start;
182 45788 : lra_live_range_t temp = r2;
183 45788 : r2 = r2->next;
184 45788 : lra_live_range_pool.remove (temp);
185 : }
186 : else
187 : {
188 5102847 : gcc_assert (r2->finish + 1 < r1->start);
189 : /* Add r1 to the result. */
190 5102847 : if (first == NULL)
191 : first = last = r1;
192 : else
193 : {
194 4425932 : last->next = r1;
195 4425932 : last = r1;
196 : }
197 5102847 : r1 = r1->next;
198 : }
199 : }
200 680596 : if (r1 != NULL)
201 : {
202 15906 : if (first == NULL)
203 : first = r1;
204 : else
205 12225 : last->next = r1;
206 : }
207 : else
208 : {
209 664690 : lra_assert (r2 != NULL);
210 664690 : if (first == NULL)
211 : first = r2;
212 : else
213 664690 : last->next = r2;
214 : }
215 : return first;
216 : }
217 :
218 : /* Return TRUE if live ranges R1 and R2 intersect. */
219 : bool
220 27054362 : lra_intersected_live_ranges_p (lra_live_range_t r1, lra_live_range_t r2)
221 : {
222 : /* Remember the live ranges are always kept ordered. */
223 47575565 : while (r1 != NULL && r2 != NULL)
224 : {
225 46892387 : if (r1->start > r2->finish)
226 18788173 : r1 = r1->next;
227 28104214 : else if (r2->start > r1->finish)
228 1733030 : r2 = r2->next;
229 : else
230 : return true;
231 : }
232 : return false;
233 : }
234 :
235 : enum point_type {
236 : DEF_POINT,
237 : USE_POINT
238 : };
239 :
240 : /* Return TRUE if set A contains a pseudo register, otherwise, return FALSE. */
241 : static bool
242 821809716 : sparseset_contains_pseudos_p (sparseset a)
243 : {
244 821809716 : int regno;
245 966029590 : EXECUTE_IF_SET_IN_SPARSESET (a, regno)
246 350381371 : if (!HARD_REGISTER_NUM_P (regno))
247 : return true;
248 : return false;
249 : }
250 :
251 : /* Mark pseudo REGNO as living or dying at program point POINT, depending on
252 : whether TYPE is a definition or a use. If this is the first reference to
253 : REGNO that we've encountered, then create a new live range for it. */
254 :
255 : static void
256 1329581312 : update_pseudo_point (int regno, int point, enum point_type type)
257 : {
258 1329581312 : lra_live_range_t p;
259 :
260 : /* Don't compute points for hard registers. */
261 1329581312 : if (HARD_REGISTER_NUM_P (regno))
262 : return;
263 :
264 1212774382 : if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
265 : {
266 1194059703 : if (type == DEF_POINT)
267 : {
268 513994829 : if (sparseset_bit_p (pseudos_live, regno))
269 : {
270 513994829 : p = lra_reg_info[regno].live_ranges;
271 513994829 : lra_assert (p != NULL);
272 513994829 : p->finish = point;
273 : }
274 : }
275 : else /* USE_POINT */
276 : {
277 680064874 : if (!sparseset_bit_p (pseudos_live, regno)
278 680064874 : && ((p = lra_reg_info[regno].live_ranges) == NULL
279 422429606 : || (p->finish != point && p->finish + 1 != point)))
280 115648225 : lra_reg_info[regno].live_ranges
281 115648225 : = create_live_range (regno, point, -1, p);
282 : }
283 : }
284 : }
285 :
286 : /* The corresponding bitmaps of BB currently being processed. */
287 : static bitmap bb_killed_pseudos, bb_gen_pseudos;
288 :
289 : /* Record hard register REGNO as now being live. It updates
290 : living hard regs and START_LIVING. */
291 : static void
292 246436822 : make_hard_regno_live (int regno)
293 : {
294 246436822 : lra_assert (HARD_REGISTER_NUM_P (regno));
295 246436822 : if (TEST_HARD_REG_BIT (hard_regs_live, regno)
296 246436822 : || TEST_HARD_REG_BIT (eliminable_regset, regno))
297 : return;
298 136144872 : SET_HARD_REG_BIT (hard_regs_live, regno);
299 136144872 : sparseset_set_bit (start_living, regno);
300 136144872 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
301 79605299 : bitmap_set_bit (bb_gen_pseudos, regno);
302 : }
303 :
304 : /* Process the definition of hard register REGNO. This updates
305 : hard_regs_live, START_DYING and conflict hard regs for living
306 : pseudos. */
307 : static void
308 134413196 : make_hard_regno_dead (int regno)
309 : {
310 134413196 : if (TEST_HARD_REG_BIT (eliminable_regset, regno))
311 : return;
312 :
313 134412280 : lra_assert (HARD_REGISTER_NUM_P (regno));
314 134412280 : unsigned int i;
315 1365158397 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
316 1230746117 : SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
317 :
318 134412280 : if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
319 : return;
320 134411593 : CLEAR_HARD_REG_BIT (hard_regs_live, regno);
321 134411593 : sparseset_set_bit (start_dying, regno);
322 134411593 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
323 : {
324 79605227 : bitmap_clear_bit (bb_gen_pseudos, regno);
325 79605227 : bitmap_set_bit (bb_killed_pseudos, regno);
326 : }
327 : }
328 :
329 : /* Mark pseudo REGNO as now being live and update START_LIVING. */
330 : static void
331 692751529 : mark_pseudo_live (int regno)
332 : {
333 692751529 : lra_assert (!HARD_REGISTER_NUM_P (regno));
334 692751529 : if (sparseset_bit_p (pseudos_live, regno))
335 : return;
336 :
337 525153091 : sparseset_set_bit (pseudos_live, regno);
338 525153091 : sparseset_set_bit (start_living, regno);
339 : }
340 :
341 : /* Mark pseudo REGNO as now being dead and update START_DYING. */
342 : static void
343 525153091 : mark_pseudo_dead (int regno)
344 : {
345 525153091 : lra_assert (!HARD_REGISTER_NUM_P (regno));
346 525153091 : lra_reg_info[regno].conflict_hard_regs |= hard_regs_live;
347 525153091 : if (!sparseset_bit_p (pseudos_live, regno))
348 : return;
349 :
350 525153091 : sparseset_clear_bit (pseudos_live, regno);
351 525153091 : sparseset_set_bit (start_dying, regno);
352 : }
353 :
354 : /* Mark register REGNO (pseudo or hard register) in MODE as being live
355 : and update BB_GEN_PSEUDOS. */
356 : static void
357 388473481 : mark_regno_live (int regno, machine_mode mode)
358 : {
359 388473481 : int last;
360 :
361 388473481 : if (HARD_REGISTER_NUM_P (regno))
362 : {
363 225744470 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
364 113178397 : make_hard_regno_live (regno);
365 : }
366 : else
367 : {
368 275907408 : mark_pseudo_live (regno);
369 275907408 : bitmap_set_bit (bb_gen_pseudos, regno);
370 : }
371 388473481 : }
372 :
373 :
374 : /* Mark register REGNO (pseudo or hard register) in MODE as being dead
375 : and update BB_GEN_PSEUDOS and BB_KILLED_PSEUDOS. */
376 : static void
377 156947266 : mark_regno_dead (int regno, machine_mode mode)
378 : {
379 156947266 : int last;
380 :
381 156947266 : if (HARD_REGISTER_NUM_P (regno))
382 : {
383 81278094 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
384 40872482 : make_hard_regno_dead (regno);
385 : }
386 : else
387 : {
388 116541654 : mark_pseudo_dead (regno);
389 116541654 : bitmap_clear_bit (bb_gen_pseudos, regno);
390 116541654 : bitmap_set_bit (bb_killed_pseudos, regno);
391 : }
392 156947266 : }
393 :
394 :
395 :
396 : /* This page contains code for making global live analysis of pseudos.
397 : The code works only when pseudo live info is changed on a BB
398 : border. That might be a consequence of some global transformations
399 : in LRA, e.g. PIC pseudo reuse or rematerialization. */
400 :
401 : /* Structure describing local BB data used for pseudo
402 : live-analysis. */
403 : class bb_data_pseudos
404 : {
405 : public:
406 : /* Basic block about which the below data are. */
407 : basic_block bb;
408 : bitmap_head killed_pseudos; /* pseudos killed in the BB. */
409 : bitmap_head gen_pseudos; /* pseudos generated in the BB. */
410 : };
411 :
412 : /* Array for all BB data. Indexed by the corresponding BB index. */
413 : typedef class bb_data_pseudos *bb_data_t;
414 :
415 : /* All basic block data are referred through the following array. */
416 : static bb_data_t bb_data;
417 :
418 : /* Two small functions for access to the bb data. */
419 : static inline bb_data_t
420 77308965 : get_bb_data (basic_block bb)
421 : {
422 77308965 : return &bb_data[(bb)->index];
423 : }
424 :
425 : static inline bb_data_t
426 8594332 : get_bb_data_by_index (int index)
427 : {
428 8594332 : return &bb_data[index];
429 : }
430 :
431 : /* Bitmap with all hard regs. */
432 : static bitmap_head all_hard_regs_bitmap;
433 :
434 : /* The transfer function used by the DF equation solver to propagate
435 : live info through block with BB_INDEX according to the following
436 : equation:
437 :
438 : bb.livein = (bb.liveout - bb.kill) OR bb.gen
439 : */
440 : static bool
441 8594332 : live_trans_fun (int bb_index)
442 : {
443 8594332 : basic_block bb = get_bb_data_by_index (bb_index)->bb;
444 8594332 : bitmap bb_liveout = df_get_live_out (bb);
445 8594332 : bitmap bb_livein = df_get_live_in (bb);
446 8594332 : bb_data_t bb_info = get_bb_data (bb);
447 :
448 8594332 : bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
449 8594332 : return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
450 8594332 : &temp_bitmap, &bb_info->killed_pseudos);
451 : }
452 :
453 : /* The confluence function used by the DF equation solver to set up
454 : live info for a block BB without predecessor. */
455 : static void
456 382773 : live_con_fun_0 (basic_block bb)
457 : {
458 382773 : bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
459 382773 : }
460 :
461 : /* The confluence function used by the DF equation solver to propagate
462 : live info from successor to predecessor on edge E according to the
463 : following equation:
464 :
465 : bb.liveout = 0 for entry block | OR (livein of successors)
466 : */
467 : static bool
468 12538247 : live_con_fun_n (edge e)
469 : {
470 12538247 : basic_block bb = e->src;
471 12538247 : basic_block dest = e->dest;
472 12538247 : bitmap bb_liveout = df_get_live_out (bb);
473 12538247 : bitmap dest_livein = df_get_live_in (dest);
474 :
475 12538247 : return bitmap_ior_and_compl_into (bb_liveout,
476 12538247 : dest_livein, &all_hard_regs_bitmap);
477 : }
478 :
479 : /* Indexes of all function blocks. */
480 : static bitmap_head all_blocks;
481 :
482 : /* Allocate and initialize data needed for global pseudo live
483 : analysis. */
484 : static void
485 1517127 : initiate_live_solver (void)
486 : {
487 1517127 : bitmap_initialize (&all_hard_regs_bitmap, ®_obstack);
488 1517127 : bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
489 1517127 : bb_data = XNEWVEC (class bb_data_pseudos, last_basic_block_for_fn (cfun));
490 1517127 : bitmap_initialize (&all_blocks, ®_obstack);
491 :
492 1517127 : basic_block bb;
493 19377855 : FOR_ALL_BB_FN (bb, cfun)
494 : {
495 17860728 : bb_data_t bb_info = get_bb_data (bb);
496 17860728 : bb_info->bb = bb;
497 17860728 : bitmap_initialize (&bb_info->killed_pseudos, ®_obstack);
498 17860728 : bitmap_initialize (&bb_info->gen_pseudos, ®_obstack);
499 17860728 : bitmap_set_bit (&all_blocks, bb->index);
500 : }
501 1517127 : }
502 :
503 : /* Free all data needed for global pseudo live analysis. */
504 : static void
505 1517127 : finish_live_solver (void)
506 : {
507 1517127 : basic_block bb;
508 :
509 1517127 : bitmap_clear (&all_blocks);
510 19377855 : FOR_ALL_BB_FN (bb, cfun)
511 : {
512 17860728 : bb_data_t bb_info = get_bb_data (bb);
513 17860728 : bitmap_clear (&bb_info->killed_pseudos);
514 17860728 : bitmap_clear (&bb_info->gen_pseudos);
515 : }
516 1517127 : free (bb_data);
517 1517127 : bitmap_clear (&all_hard_regs_bitmap);
518 1517127 : }
519 :
520 :
521 :
522 : /* Insn currently scanned. */
523 : static rtx_insn *curr_insn;
524 : /* The insn data. */
525 : static lra_insn_recog_data_t curr_id;
526 : /* The insn static data. */
527 : static struct lra_static_insn_data *curr_static_id;
528 :
529 : /* Vec containing execution frequencies of program points. */
530 : static vec<int> point_freq_vec;
531 :
532 : /* The start of the above vector elements. */
533 : int *lra_point_freq;
534 :
535 : /* Increment the current program point POINT to the next point which has
536 : execution frequency FREQ. */
537 : static void
538 232708102 : next_program_point (int &point, int freq)
539 : {
540 232708102 : point_freq_vec.safe_push (freq);
541 232708102 : lra_point_freq = point_freq_vec.address ();
542 232708102 : point++;
543 232708102 : }
544 :
545 : /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
546 : void
547 16279644 : lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
548 : int hard_regno, int profit)
549 : {
550 16279644 : lra_assert (regno >= lra_constraint_new_regno_start);
551 16279644 : if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
552 2931049 : lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
553 13348595 : else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
554 88453 : lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
555 13260142 : else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
556 : {
557 10464735 : lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
558 10464735 : lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
559 : }
560 2795407 : else if (lra_reg_info[regno].preferred_hard_regno2 < 0
561 77472 : || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
562 : {
563 2750270 : lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
564 2750270 : lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
565 : }
566 : else
567 : return;
568 : /* Keep the 1st hard regno as more profitable. */
569 16234507 : if (lra_reg_info[regno].preferred_hard_regno1 >= 0
570 16234507 : && lra_reg_info[regno].preferred_hard_regno2 >= 0
571 2918828 : && (lra_reg_info[regno].preferred_hard_regno_profit2
572 2918828 : > lra_reg_info[regno].preferred_hard_regno_profit1))
573 : {
574 116595 : std::swap (lra_reg_info[regno].preferred_hard_regno1,
575 : lra_reg_info[regno].preferred_hard_regno2);
576 116595 : std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
577 : lra_reg_info[regno].preferred_hard_regno_profit2);
578 : }
579 16234507 : if (lra_dump_file != NULL)
580 : {
581 194 : if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
582 194 : fprintf (lra_dump_file,
583 : " Hard reg %d is preferable by r%d with profit %d\n",
584 : hard_regno, regno,
585 : lra_reg_info[regno].preferred_hard_regno_profit1);
586 194 : if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
587 75 : fprintf (lra_dump_file,
588 : " Hard reg %d is preferable by r%d with profit %d\n",
589 : hard_regno, regno,
590 : lra_reg_info[regno].preferred_hard_regno_profit2);
591 : }
592 : }
593 :
594 : /* Check whether REGNO lives through calls and setjmps and clear
595 : the corresponding bits in PSEUDOS_LIVE_THROUGH_CALLS and
596 : PSEUDOS_LIVE_THROUGH_SETJUMPS. All calls in the region described
597 : by PSEUDOS_LIVE_THROUGH_CALLS have the given ABI. */
598 :
599 : static inline void
600 480617956 : check_pseudos_live_through_calls (int regno, const function_abi &abi)
601 : {
602 480617956 : if (! sparseset_bit_p (pseudos_live_through_calls, regno))
603 : return;
604 :
605 97963583 : machine_mode mode = PSEUDO_REGNO_MODE (regno);
606 :
607 97963583 : sparseset_clear_bit (pseudos_live_through_calls, regno);
608 97963583 : lra_reg_info[regno].conflict_hard_regs |= abi.mode_clobbers (mode);
609 97963583 : if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
610 : return;
611 7464 : sparseset_clear_bit (pseudos_live_through_setjumps, regno);
612 : /* Don't allocate pseudos that cross setjmps or any call, if this
613 : function receives a nonlocal goto. */
614 7464 : SET_HARD_REG_SET (lra_reg_info[regno].conflict_hard_regs);
615 : }
616 :
617 : /* Return true if insn REG is an early clobber operand in alternative
618 : NALT. Negative NALT means that we don't know the current insn
619 : alternative. So assume the worst. */
620 : static inline bool
621 400135920 : reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
622 : {
623 400135920 : return (n_alt == LRA_UNKNOWN_ALT
624 400135920 : ? reg->early_clobber_alts != 0
625 : : (n_alt != LRA_NON_CLOBBERED_ALT
626 382705046 : && TEST_BIT (reg->early_clobber_alts, n_alt)));
627 : }
628 :
629 : /* Clear pseudo REGNO in SET or all hard registers of REGNO in MODE in SET. */
630 : static void
631 161608917 : clear_sparseset_regnos (sparseset set, int regno, enum machine_mode mode)
632 : {
633 161608917 : if (regno >= FIRST_PSEUDO_REGISTER)
634 : {
635 89338599 : sparseset_clear_bit (set, regno);
636 89338599 : return;
637 : }
638 144810104 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
639 72539786 : sparseset_clear_bit (set, regno);
640 : }
641 :
642 : /* Return true if pseudo REGNO is in SET or all hard registers of REGNO in MODE
643 : are in SET. */
644 : static bool
645 164084188 : regnos_in_sparseset_p (sparseset set, int regno, enum machine_mode mode)
646 : {
647 164084188 : if (regno >= FIRST_PSEUDO_REGISTER)
648 91701921 : return sparseset_bit_p (set, regno);
649 144922053 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
650 72651735 : if (!sparseset_bit_p (set, regno))
651 : return false;
652 : return true;
653 : }
654 :
655 : /* Process insns of the basic block BB to update pseudo live ranges,
656 : pseudo hard register conflicts, and insn notes. We do it on
657 : backward scan of BB insns. CURR_POINT is the program point where
658 : BB ends. The function updates this counter and returns in
659 : CURR_POINT the program point where BB starts. The function also
660 : does local live info updates and can delete the dead insns if
661 : DEAD_INSN_P. It returns true if pseudo live info was
662 : changed at the BB start. */
663 : static bool
664 32993149 : process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
665 : {
666 32993149 : int i, regno, freq;
667 32993149 : unsigned int j;
668 32993149 : bitmap_iterator bi;
669 32993149 : bitmap reg_live_out;
670 32993149 : unsigned int px;
671 32993149 : rtx_insn *next;
672 32993149 : rtx link, *link_loc;
673 32993149 : bool need_curr_point_incr;
674 : /* Only has a meaningful value once we've seen a call. */
675 32993149 : function_abi last_call_abi = default_function_abi;
676 :
677 32993149 : reg_live_out = df_get_live_out (bb);
678 32993149 : sparseset_clear (pseudos_live);
679 32993149 : sparseset_clear (pseudos_live_through_calls);
680 32993149 : sparseset_clear (pseudos_live_through_setjumps);
681 65986298 : REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
682 32993149 : hard_regs_live &= ~eliminable_regset;
683 449837270 : EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
684 : {
685 416844121 : update_pseudo_point (j, curr_point, USE_POINT);
686 416844121 : mark_pseudo_live (j);
687 : }
688 :
689 32993149 : bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
690 32993149 : bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
691 32993149 : bitmap_clear (bb_gen_pseudos);
692 32993149 : bitmap_clear (bb_killed_pseudos);
693 32993149 : freq = REG_FREQ_FROM_BB (bb);
694 :
695 32993149 : if (lra_dump_file != NULL)
696 445 : fprintf (lra_dump_file, " BB %d\n", bb->index);
697 :
698 : /* Scan the code of this basic block, noting which pseudos and hard
699 : regs are born or die.
700 :
701 : Note that this loop treats uninitialized values as live until the
702 : beginning of the block. For example, if an instruction uses
703 : (reg:DI foo), and only (subreg:SI (reg:DI foo) 0) is ever set,
704 : FOO will remain live until the beginning of the block. Likewise
705 : if FOO is not set at all. This is unnecessarily pessimistic, but
706 : it probably doesn't matter much in practice. */
707 922832109 : FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
708 : {
709 444919480 : int n_alt, dst_regno, src_regno;
710 444919480 : rtx set;
711 444919480 : struct lra_insn_reg *reg;
712 :
713 444919480 : if (!NONDEBUG_INSN_P (curr_insn))
714 216655148 : continue;
715 :
716 228264332 : curr_id = lra_get_insn_recog_data (curr_insn);
717 228264332 : curr_static_id = curr_id->insn_static_data;
718 228264332 : n_alt = curr_id->used_insn_alternative;
719 228264332 : if (lra_dump_file != NULL)
720 2139 : fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n",
721 2139 : INSN_UID (curr_insn), curr_point, n_alt);
722 :
723 228264332 : set = single_set (curr_insn);
724 :
725 228264332 : if (dead_insn_p && set != NULL_RTX
726 174735999 : && REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
727 90992621 : && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
728 90767364 : && ! may_trap_p (PATTERN (curr_insn))
729 : /* Don't do premature remove of pic offset pseudo as we can
730 : start to use it after some reload generation. */
731 310421955 : && (pic_offset_table_rtx == NULL_RTX
732 9317369 : || pic_offset_table_rtx != SET_DEST (set)))
733 : {
734 82091273 : bool remove_p = true;
735 :
736 82751358 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
737 82699634 : if (reg->type != OP_IN
738 82699634 : && (reg->regno < FIRST_PSEUDO_REGISTER
739 82091400 : ? TEST_HARD_REG_BIT (hard_regs_live, reg->regno)
740 82091400 : : sparseset_bit_p (pseudos_live, reg->regno)))
741 : {
742 : remove_p = false;
743 : break;
744 : }
745 83410682 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
746 16380831 : if (reg->type != OP_IN)
747 : {
748 : remove_p = false;
749 : break;
750 : }
751 :
752 82091273 : if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
753 : {
754 47035 : dst_regno = REGNO (SET_DEST (set));
755 47035 : if (lra_dump_file != NULL)
756 0 : fprintf (lra_dump_file, " Deleting dead insn %u\n",
757 0 : INSN_UID (curr_insn));
758 47035 : lra_set_insn_deleted (curr_insn);
759 47035 : if (lra_reg_info[dst_regno].nrefs == 0)
760 : {
761 : /* There might be some debug insns with the pseudo. */
762 6781 : unsigned int uid;
763 6781 : rtx_insn *insn;
764 :
765 6781 : bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
766 7067 : EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
767 : {
768 286 : insn = lra_insn_recog_data[uid]->insn;
769 286 : lra_substitute_pseudo_within_insn (insn, dst_regno,
770 : SET_SRC (set), true);
771 286 : lra_update_insn_regno_info (insn);
772 : }
773 : }
774 47035 : continue;
775 47035 : }
776 : }
777 :
778 : /* Update max ref width and hard reg usage. */
779 595961949 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
780 : {
781 367744652 : int regno = reg->regno;
782 :
783 367744652 : lra_update_biggest_mode (regno, reg->biggest_mode);
784 367744652 : if (HARD_REGISTER_NUM_P (regno))
785 101413997 : lra_hard_reg_usage[regno] += freq;
786 : }
787 :
788 :
789 : /* If we have a simple register copy and the source reg is live after
790 : this instruction, then remove the source reg from the live set so
791 : that it will not conflict with the destination reg. */
792 228217297 : rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
793 228217297 : if (ignore_reg != NULL_RTX)
794 : {
795 61673314 : int ignore_regno = REGNO (ignore_reg);
796 61673314 : if (HARD_REGISTER_NUM_P (ignore_regno)
797 61673314 : && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
798 172737 : CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
799 61500577 : else if (!HARD_REGISTER_NUM_P (ignore_regno)
800 61500577 : && sparseset_bit_p (pseudos_live, ignore_regno))
801 12336347 : sparseset_clear_bit (pseudos_live, ignore_regno);
802 : else
803 : /* We don't need any special handling of the source reg if
804 : it is dead after this instruction. */
805 : ignore_reg = NULL_RTX;
806 : }
807 :
808 218130386 : src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
809 311827668 : ? REGNO (SET_SRC (set)) : -1);
810 218130386 : dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
811 162995901 : ? REGNO (SET_DEST (set)) : -1);
812 228217297 : if (complete_info_p
813 226834215 : && src_regno >= 0 && dst_regno >= 0
814 : /* Check that source regno does not conflict with
815 : destination regno to exclude most impossible
816 : preferences. */
817 289498884 : && (((!HARD_REGISTER_NUM_P (src_regno)
818 54144211 : && (! sparseset_bit_p (pseudos_live, src_regno)
819 9795 : || (!HARD_REGISTER_NUM_P (dst_regno)
820 61281587 : && lra_reg_val_equal_p (src_regno,
821 : lra_reg_info[dst_regno].val,
822 0 : lra_reg_info[dst_regno].offset))))
823 : || (HARD_REGISTER_NUM_P (src_regno)
824 7137376 : && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
825 : /* It might be 'inheritance pseudo <- reload pseudo'. */
826 9808 : || (src_regno >= lra_constraint_new_regno_start
827 304 : && dst_regno >= lra_constraint_new_regno_start
828 : /* Remember to skip special cases where src/dest regnos are
829 : the same, e.g. insn SET pattern has matching constraints
830 : like =r,0. */
831 0 : && src_regno != dst_regno)))
832 : {
833 61271779 : int hard_regno = -1, regno = -1;
834 :
835 61271779 : if (dst_regno >= lra_constraint_new_regno_start
836 16351193 : && src_regno >= lra_constraint_new_regno_start)
837 : {
838 : /* It might be still an original (non-reload) insn with
839 : one unused output and a constraint requiring to use
840 : the same reg for input/output operands. In this case
841 : dst_regno and src_regno have the same value, we don't
842 : need a misleading copy for this case. */
843 6036803 : if (dst_regno != src_regno)
844 6036803 : lra_create_copy (dst_regno, src_regno, freq);
845 : }
846 55234976 : else if (dst_regno >= lra_constraint_new_regno_start)
847 : {
848 10314390 : if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
849 10200839 : hard_regno = reg_renumber[src_regno];
850 : regno = dst_regno;
851 : }
852 44920586 : else if (src_regno >= lra_constraint_new_regno_start)
853 : {
854 11516283 : if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
855 9589893 : hard_regno = reg_renumber[dst_regno];
856 : regno = src_regno;
857 : }
858 61271779 : if (regno >= 0 && hard_regno >= 0)
859 13319424 : lra_setup_reload_pseudo_preferenced_hard_reg
860 13319424 : (regno, hard_regno, freq);
861 : }
862 :
863 228217297 : sparseset_clear (start_living);
864 :
865 : /* Mark each defined value as live. We need to do this for
866 : unused values because they still conflict with quantities
867 : that are live at the time of the definition. */
868 595961949 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
869 367744652 : if (reg->type != OP_IN)
870 : {
871 158038900 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
872 158038900 : mark_regno_live (reg->regno, reg->biggest_mode);
873 : /* ??? Should be a no-op for unused registers. */
874 158038900 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
875 : }
876 :
877 286623434 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
878 58406137 : if (reg->type != OP_IN)
879 42029060 : make_hard_regno_live (reg->regno);
880 :
881 228217297 : if (curr_id->arg_hard_regs != NULL)
882 32762214 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
883 22807933 : if (!HARD_REGISTER_NUM_P (regno))
884 : /* It is a clobber. */
885 0 : make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
886 :
887 228217297 : sparseset_copy (unused_set, start_living);
888 :
889 228217297 : sparseset_clear (start_dying);
890 :
891 : /* See which defined values die here. */
892 595961949 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
893 367744652 : if (reg->type != OP_IN
894 682344715 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
895 : {
896 156561163 : if (reg->type == OP_OUT)
897 136134729 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
898 156561163 : mark_regno_dead (reg->regno, reg->biggest_mode);
899 : }
900 :
901 286623434 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
902 58406137 : if (reg->type != OP_IN
903 117321178 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
904 16885981 : make_hard_regno_dead (reg->regno);
905 :
906 228217297 : if (curr_id->arg_hard_regs != NULL)
907 32762214 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
908 22807933 : if (!HARD_REGISTER_NUM_P (regno))
909 : /* It is a clobber. */
910 0 : make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
911 :
912 228217297 : if (auto call = dyn_cast<rtx_call_insn *> (curr_insn))
913 : {
914 12662129 : function_abi call_abi = insn_callee_abi (call);
915 :
916 12662129 : if (last_call_abi != call_abi)
917 7846995 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
918 5398075 : check_pseudos_live_through_calls (j, last_call_abi);
919 :
920 12662129 : last_call_abi = call_abi;
921 :
922 12662129 : sparseset_ior (pseudos_live_through_calls,
923 : pseudos_live_through_calls, pseudos_live);
924 12662129 : if (cfun->has_nonlocal_label
925 12662129 : || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
926 12657880 : && (find_reg_note (call, REG_SETJMP, NULL_RTX)
927 : != NULL_RTX)))
928 6867 : sparseset_ior (pseudos_live_through_setjumps,
929 : pseudos_live_through_setjumps, pseudos_live);
930 : }
931 :
932 : /* Increment the current program point if we must. */
933 228217297 : if (sparseset_contains_pseudos_p (unused_set)
934 228217297 : || sparseset_contains_pseudos_p (start_dying))
935 115911334 : next_program_point (curr_point, freq);
936 :
937 : /* If we removed the source reg from a simple register copy from the
938 : live set above, then add it back now so we don't accidentally add
939 : it to the start_living set below. */
940 228217297 : if (ignore_reg != NULL_RTX)
941 : {
942 12509084 : int ignore_regno = REGNO (ignore_reg);
943 12509084 : if (HARD_REGISTER_NUM_P (ignore_regno))
944 172737 : SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
945 : else
946 12336347 : sparseset_set_bit (pseudos_live, ignore_regno);
947 : }
948 :
949 228217297 : sparseset_clear (start_living);
950 :
951 : /* Mark each used value as live. */
952 595961949 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
953 367744652 : if (reg->type != OP_OUT)
954 : {
955 230294851 : if (reg->type == OP_IN)
956 209705752 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
957 230294851 : mark_regno_live (reg->regno, reg->biggest_mode);
958 230294851 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
959 : }
960 :
961 286623434 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
962 58406137 : if (reg->type != OP_OUT)
963 16869434 : make_hard_regno_live (reg->regno);
964 :
965 228217297 : if (curr_id->arg_hard_regs != NULL)
966 : /* Make argument hard registers live. */
967 32762214 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
968 22807933 : if (HARD_REGISTER_NUM_P (regno))
969 22807933 : make_hard_regno_live (regno);
970 :
971 228217297 : sparseset_and_compl (dead_set, start_living, start_dying);
972 :
973 228217297 : sparseset_clear (start_dying);
974 :
975 : /* Mark early clobber outputs dead. */
976 595961949 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
977 367744652 : if (reg->type != OP_IN
978 526169655 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
979 : {
980 386103 : if (reg->type == OP_OUT)
981 246373 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
982 386103 : mark_regno_dead (reg->regno, reg->biggest_mode);
983 :
984 : /* We're done processing inputs, so make sure early clobber
985 : operands that are both inputs and outputs are still live. */
986 386103 : if (reg->type == OP_INOUT)
987 139730 : mark_regno_live (reg->regno, reg->biggest_mode);
988 : }
989 :
990 286623434 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
991 58406137 : if (reg->type != OP_IN
992 125578276 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
993 : {
994 25143079 : struct lra_insn_reg *reg2;
995 :
996 : /* We can have early clobbered non-operand hard reg and
997 : the same hard reg as an insn input. Don't make hard
998 : reg dead before the insns. */
999 50596573 : for (reg2 = curr_static_id->hard_regs; reg2 != NULL; reg2 = reg2->next)
1000 25481647 : if (reg2->type != OP_OUT && reg2->regno == reg->regno)
1001 : break;
1002 25143079 : if (reg2 != NULL)
1003 28153 : continue;
1004 :
1005 : HARD_REG_SET clobbered_regset;
1006 25114926 : CLEAR_HARD_REG_SET (clobbered_regset);
1007 25114926 : SET_HARD_REG_BIT (clobbered_regset, reg->regno);
1008 :
1009 69872416 : for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
1010 31933331 : if (reg2->type != OP_OUT && reg2->regno < FIRST_PSEUDO_REGISTER
1011 53257001 : && ira_hard_reg_set_intersection_p (reg2->regno,
1012 8487320 : reg2->biggest_mode,
1013 : clobbered_regset))
1014 : break;
1015 25114926 : if (reg2 == NULL)
1016 : {
1017 25102735 : make_hard_regno_dead (reg->regno);
1018 : }
1019 : else
1020 : {
1021 161495 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1022 149304 : SET_HARD_REG_BIT (lra_reg_info[j].conflict_hard_regs,
1023 : reg->regno);
1024 : }
1025 : }
1026 :
1027 : /* Increment the current program point if we must. */
1028 228217297 : if (sparseset_contains_pseudos_p (dead_set)
1029 228217297 : || sparseset_contains_pseudos_p (start_dying))
1030 90250163 : next_program_point (curr_point, freq);
1031 :
1032 : /* Update notes. */
1033 459859512 : for (link_loc = ®_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1034 : {
1035 231642215 : if (REG_NOTE_KIND (link) != REG_DEAD
1036 95718630 : && REG_NOTE_KIND (link) != REG_UNUSED)
1037 : ;
1038 164084188 : else if (REG_P (XEXP (link, 0)))
1039 : {
1040 164084188 : rtx note_reg = XEXP (link, 0);
1041 164084188 : int note_regno = REGNO (note_reg);
1042 :
1043 166559459 : if ((REG_NOTE_KIND (link) == REG_DEAD
1044 135923585 : && ! regnos_in_sparseset_p (dead_set, note_regno,
1045 135923585 : GET_MODE (note_reg)))
1046 297747706 : || (REG_NOTE_KIND (link) == REG_UNUSED
1047 28160603 : && ! regnos_in_sparseset_p (unused_set, note_regno,
1048 28160603 : GET_MODE (note_reg))))
1049 : {
1050 2475271 : *link_loc = XEXP (link, 1);
1051 2475271 : continue;
1052 : }
1053 161608917 : if (REG_NOTE_KIND (link) == REG_DEAD)
1054 133663518 : clear_sparseset_regnos (dead_set, note_regno,
1055 133663518 : GET_MODE (note_reg));
1056 27945399 : else if (REG_NOTE_KIND (link) == REG_UNUSED)
1057 27945399 : clear_sparseset_regnos (unused_set, note_regno,
1058 27945399 : GET_MODE (note_reg));
1059 : }
1060 229166944 : link_loc = &XEXP (link, 1);
1061 : }
1062 237365499 : EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1063 9148202 : add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1064 456595798 : EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1065 161204 : add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1066 : }
1067 :
1068 32993149 : if (bb_has_eh_pred (bb))
1069 : /* Any pseudos that are currently live conflict with the eh_return
1070 : data registers. For liveness purposes, these registers are set
1071 : by artificial definitions at the start of the BB, so are not
1072 : actually live on entry. */
1073 590488 : for (j = 0; ; ++j)
1074 : {
1075 1771464 : unsigned int regno = EH_RETURN_DATA_REGNO (j);
1076 :
1077 1180976 : if (regno == INVALID_REGNUM)
1078 : break;
1079 :
1080 1180976 : make_hard_regno_live (regno);
1081 1180976 : make_hard_regno_dead (regno);
1082 1180976 : }
1083 :
1084 : /* Pseudos can't go in stack regs at the start of a basic block that
1085 : is reached by an abnormal edge. Likewise for registers that are at
1086 : least partly call clobbered, because caller-save, fixup_abnormal_edges
1087 : and possibly the table driven EH machinery are not quite ready to
1088 : handle such pseudos live across such edges. */
1089 32993149 : if (bb_has_abnormal_pred (bb))
1090 : {
1091 : HARD_REG_SET clobbers;
1092 :
1093 593952 : CLEAR_HARD_REG_SET (clobbers);
1094 : #ifdef STACK_REGS
1095 1799156 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1096 1205204 : lra_reg_info[px].no_stack_p = true;
1097 5345568 : for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1098 4751616 : SET_HARD_REG_BIT (clobbers, px);
1099 : #endif
1100 : /* No need to record conflicts for call clobbered regs if we
1101 : have nonlocal labels around, as we don't ever try to
1102 : allocate such regs in this case. */
1103 593952 : if (!cfun->has_nonlocal_label
1104 593952 : && has_abnormal_call_or_eh_pred_edge_p (bb))
1105 56095505 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1106 55505026 : if (eh_edge_abi.clobbers_at_least_part_of_reg_p (px)
1107 : #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1108 : /* We should create a conflict of PIC pseudo with PIC
1109 : hard reg as PIC hard reg can have a wrong value after
1110 : jump described by the abnormal edge. In this case we
1111 : cannot allocate PIC hard reg to PIC pseudo as PIC
1112 : pseudo will also have a wrong value. */
1113 55959585 : || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1114 590479 : && pic_offset_table_rtx != NULL_RTX
1115 22649 : && !HARD_REGISTER_P (pic_offset_table_rtx))
1116 : #endif
1117 : )
1118 50343238 : SET_HARD_REG_BIT (clobbers, px);
1119 :
1120 593952 : clobbers &= ~hard_regs_live;
1121 56425440 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1122 55831488 : if (TEST_HARD_REG_BIT (clobbers, px))
1123 : {
1124 50371022 : make_hard_regno_live (px);
1125 50371022 : make_hard_regno_dead (px);
1126 : }
1127 : }
1128 :
1129 32993149 : bool live_change_p = false;
1130 : /* Check if bb border live info was changed. */
1131 32993149 : unsigned int live_pseudos_num = 0;
1132 440841968 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1133 : FIRST_PSEUDO_REGISTER, j, bi)
1134 : {
1135 408098332 : live_pseudos_num++;
1136 408098332 : if (! sparseset_bit_p (pseudos_live, j))
1137 : {
1138 249513 : live_change_p = true;
1139 249513 : if (lra_dump_file != NULL)
1140 14 : fprintf (lra_dump_file,
1141 : " r%d is removed as live at bb%d start\n", j, bb->index);
1142 : break;
1143 : }
1144 : }
1145 14 : if (! live_change_p
1146 32743636 : && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1147 : {
1148 192379 : live_change_p = true;
1149 192379 : if (lra_dump_file != NULL)
1150 28 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1151 7 : if (! bitmap_bit_p (df_get_live_in (bb), j))
1152 7 : fprintf (lra_dump_file,
1153 : " r%d is added to live at bb%d start\n", j, bb->index);
1154 : }
1155 : /* See if we'll need an increment at the end of this basic block.
1156 : An increment is needed if the PSEUDOS_LIVE set is not empty,
1157 : to make sure the finish points are set up correctly. */
1158 32993149 : need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1159 :
1160 850216023 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1161 : {
1162 408611437 : update_pseudo_point (i, curr_point, DEF_POINT);
1163 408611437 : mark_pseudo_dead (i);
1164 : }
1165 :
1166 126775661 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1167 : {
1168 115894505 : if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1169 : break;
1170 93782512 : if (sparseset_bit_p (pseudos_live_through_calls, j))
1171 86886130 : check_pseudos_live_through_calls (j, last_call_abi);
1172 : }
1173 :
1174 3134349155 : for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1175 : {
1176 3101356006 : if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1177 3056033027 : continue;
1178 :
1179 45322979 : if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1180 45322979 : continue;
1181 :
1182 0 : if (bitmap_bit_p (df_get_live_in (bb), i))
1183 0 : continue;
1184 :
1185 0 : live_change_p = true;
1186 0 : if (lra_dump_file)
1187 0 : fprintf (lra_dump_file,
1188 : " hard reg r%d is added to live at bb%d start\n", i,
1189 : bb->index);
1190 0 : bitmap_set_bit (df_get_live_in (bb), i);
1191 : }
1192 :
1193 32993149 : if (need_curr_point_incr)
1194 26546605 : next_program_point (curr_point, freq);
1195 :
1196 32993149 : return live_change_p;
1197 : }
1198 :
1199 : /* Compress pseudo live ranges by removing program points where
1200 : nothing happens. Complexity of many algorithms in LRA is linear
1201 : function of program points number. To speed up the code we try to
1202 : minimize the number of the program points here. */
1203 : static void
1204 1614186 : remove_some_program_points_and_update_live_ranges (void)
1205 : {
1206 1614186 : unsigned i;
1207 1614186 : int n, max_regno;
1208 1614186 : int *map;
1209 1614186 : lra_live_range_t r, prev_r, next_r;
1210 1614186 : sbitmap_iterator sbi;
1211 1614186 : bool born_p, dead_p, prev_born_p, prev_dead_p;
1212 :
1213 1614186 : auto_sbitmap born (lra_live_max_point);
1214 1614186 : auto_sbitmap dead (lra_live_max_point);
1215 1614186 : bitmap_clear (born);
1216 1614186 : bitmap_clear (dead);
1217 1614186 : max_regno = max_reg_num ();
1218 179593336 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1219 : {
1220 293627375 : for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1221 : {
1222 115648225 : lra_assert (r->start <= r->finish);
1223 115648225 : bitmap_set_bit (born, r->start);
1224 115648225 : bitmap_set_bit (dead, r->finish);
1225 : }
1226 : }
1227 1614186 : auto_sbitmap born_or_dead (lra_live_max_point);
1228 1614186 : bitmap_ior (born_or_dead, born, dead);
1229 1614186 : map = XCNEWVEC (int, lra_live_max_point);
1230 1614186 : n = -1;
1231 1614186 : prev_born_p = prev_dead_p = false;
1232 203537898 : EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1233 : {
1234 200309527 : born_p = bitmap_bit_p (born, i);
1235 200309527 : dead_p = bitmap_bit_p (dead, i);
1236 200309527 : if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1237 184862914 : || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1238 : {
1239 44101758 : map[i] = n;
1240 44101758 : lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1241 : }
1242 : else
1243 : {
1244 156207769 : map[i] = ++n;
1245 156207769 : lra_point_freq[n] = lra_point_freq[i];
1246 : }
1247 200309527 : prev_born_p = born_p;
1248 200309527 : prev_dead_p = dead_p;
1249 : }
1250 1614186 : n++;
1251 1614186 : if (lra_dump_file != NULL)
1252 92 : fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1253 : lra_live_max_point, n,
1254 92 : lra_live_max_point ? 100 * n / lra_live_max_point : 100);
1255 1614186 : if (n < lra_live_max_point)
1256 : {
1257 1368198 : lra_live_max_point = n;
1258 176060557 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1259 : {
1260 174692359 : for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1261 289535366 : r != NULL;
1262 114843007 : r = next_r)
1263 : {
1264 114843007 : next_r = r->next;
1265 114843007 : r->start = map[r->start];
1266 114843007 : r->finish = map[r->finish];
1267 114843007 : if (prev_r == NULL || prev_r->start > r->finish + 1)
1268 : {
1269 112632536 : prev_r = r;
1270 112632536 : continue;
1271 : }
1272 2210471 : prev_r->start = r->start;
1273 2210471 : prev_r->next = next_r;
1274 2210471 : lra_live_range_pool.remove (r);
1275 : }
1276 : }
1277 : }
1278 1614186 : free (map);
1279 1614186 : }
1280 :
1281 : /* Print live ranges R to file F. */
1282 : void
1283 1932 : lra_print_live_range_list (FILE *f, lra_live_range_t r)
1284 : {
1285 4294 : for (; r != NULL; r = r->next)
1286 2362 : fprintf (f, " [%d..%d]", r->start, r->finish);
1287 1932 : fprintf (f, "\n");
1288 1932 : }
1289 :
1290 : DEBUG_FUNCTION void
1291 0 : debug (lra_live_range &ref)
1292 : {
1293 0 : lra_print_live_range_list (stderr, &ref);
1294 0 : }
1295 :
1296 : DEBUG_FUNCTION void
1297 0 : debug (lra_live_range *ptr)
1298 : {
1299 0 : if (ptr)
1300 0 : debug (*ptr);
1301 : else
1302 0 : fprintf (stderr, "<nil>\n");
1303 0 : }
1304 :
1305 : /* Print live ranges R to stderr. */
1306 : void
1307 0 : lra_debug_live_range_list (lra_live_range_t r)
1308 : {
1309 0 : lra_print_live_range_list (stderr, r);
1310 0 : }
1311 :
1312 : /* Print live ranges of pseudo REGNO to file F. */
1313 : static void
1314 4712 : print_pseudo_live_ranges (FILE *f, int regno)
1315 : {
1316 4712 : if (lra_reg_info[regno].live_ranges == NULL)
1317 : return;
1318 1932 : fprintf (f, " r%d:", regno);
1319 1932 : lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1320 : }
1321 :
1322 : /* Print live ranges of pseudo REGNO to stderr. */
1323 : void
1324 0 : lra_debug_pseudo_live_ranges (int regno)
1325 : {
1326 0 : print_pseudo_live_ranges (stderr, regno);
1327 0 : }
1328 :
1329 : /* Print live ranges of all pseudos to file F. */
1330 : static void
1331 184 : print_live_ranges (FILE *f)
1332 : {
1333 184 : int i, max_regno;
1334 :
1335 184 : max_regno = max_reg_num ();
1336 5080 : for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1337 4712 : print_pseudo_live_ranges (f, i);
1338 184 : }
1339 :
1340 : /* Print live ranges of all pseudos to stderr. */
1341 : void
1342 0 : lra_debug_live_ranges (void)
1343 : {
1344 0 : print_live_ranges (stderr);
1345 0 : }
1346 :
1347 : /* Compress pseudo live ranges. */
1348 : static void
1349 1614186 : compress_live_ranges (void)
1350 : {
1351 1614186 : remove_some_program_points_and_update_live_ranges ();
1352 1614186 : if (lra_dump_file != NULL)
1353 : {
1354 92 : fprintf (lra_dump_file, "Ranges after the compression:\n");
1355 92 : print_live_ranges (lra_dump_file);
1356 : }
1357 1614186 : }
1358 :
1359 :
1360 :
1361 : /* The number of the current live range pass. */
1362 : int lra_live_range_iter;
1363 :
1364 : /* The function creates live ranges only for memory pseudos (or for
1365 : all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1366 : also does dead insn elimination if DEAD_INSN_P and global live
1367 : analysis only for pseudos and only if the pseudo live info was
1368 : changed on a BB border. Return TRUE if the live info was
1369 : changed. */
1370 : static bool
1371 1820678 : lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1372 : {
1373 1820678 : basic_block bb;
1374 1820678 : int i, hard_regno, max_regno = max_reg_num ();
1375 1820678 : int curr_point;
1376 1820678 : bool bb_live_change_p, have_referenced_pseudos = false;
1377 :
1378 1820678 : timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1379 :
1380 1820678 : complete_info_p = all_p;
1381 1820678 : if (lra_dump_file != NULL)
1382 103 : fprintf (lra_dump_file,
1383 : "\n********** Pseudo live ranges #%d: **********\n\n",
1384 : ++lra_live_range_iter);
1385 1820678 : memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1386 353329205 : for (i = 0; i < max_regno; i++)
1387 : {
1388 351508527 : lra_reg_info[i].live_ranges = NULL;
1389 351508527 : CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1390 351508527 : lra_reg_info[i].preferred_hard_regno1 = -1;
1391 351508527 : lra_reg_info[i].preferred_hard_regno2 = -1;
1392 351508527 : lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1393 351508527 : lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1394 : #ifdef STACK_REGS
1395 351508527 : lra_reg_info[i].no_stack_p = false;
1396 : #endif
1397 : /* The biggest mode is already set but its value might be to
1398 : conservative because of recent transformation. Here in this
1399 : file we recalculate it again as it costs practically
1400 : nothing. */
1401 351508527 : if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1402 179476315 : lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1403 : else
1404 172032212 : lra_reg_info[i].biggest_mode = VOIDmode;
1405 351508527 : if (!HARD_REGISTER_NUM_P (i)
1406 180364795 : && lra_reg_info[i].nrefs != 0)
1407 : {
1408 92017438 : if ((hard_regno = reg_renumber[i]) >= 0)
1409 75821936 : lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1410 : have_referenced_pseudos = true;
1411 : }
1412 : }
1413 1820678 : lra_free_copies ();
1414 :
1415 : /* Under some circumstances, we can have functions without pseudo
1416 : registers. For such functions, lra_live_max_point will be 0,
1417 : see e.g. PR55604, and there's nothing more to do for us here. */
1418 1820678 : if (! have_referenced_pseudos)
1419 : {
1420 206492 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1421 206492 : return false;
1422 : }
1423 :
1424 1614186 : pseudos_live = sparseset_alloc (max_regno);
1425 1614186 : pseudos_live_through_calls = sparseset_alloc (max_regno);
1426 1614186 : pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1427 1614186 : start_living = sparseset_alloc (max_regno);
1428 1614186 : start_dying = sparseset_alloc (max_regno);
1429 1614186 : dead_set = sparseset_alloc (max_regno);
1430 1614186 : unused_set = sparseset_alloc (max_regno);
1431 1614186 : curr_point = 0;
1432 1614186 : unsigned new_length = get_max_uid () * 2;
1433 1614186 : point_freq_vec.truncate (0);
1434 1614186 : point_freq_vec.reserve_exact (new_length);
1435 1614186 : lra_point_freq = point_freq_vec.address ();
1436 1614186 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1437 1614186 : int n = inverted_rev_post_order_compute (cfun, rpo);
1438 1614186 : lra_assert (n == n_basic_blocks_for_fn (cfun));
1439 : bb_live_change_p = false;
1440 37835707 : for (i = 0; i < n; ++i)
1441 : {
1442 36221521 : bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
1443 36221521 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1444 34607335 : == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1445 3228372 : continue;
1446 32993149 : if (process_bb_lives (bb, curr_point, dead_insn_p))
1447 36221521 : bb_live_change_p = true;
1448 : }
1449 1614186 : free (rpo);
1450 1614186 : if (bb_live_change_p)
1451 : {
1452 : /* We need to clear pseudo live info as some pseudos can
1453 : disappear, e.g. pseudos with used equivalences. */
1454 6829309 : FOR_EACH_BB_FN (bb, cfun)
1455 : {
1456 6708811 : bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1457 6708811 : max_regno - FIRST_PSEUDO_REGISTER);
1458 6708811 : bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1459 : max_regno - FIRST_PSEUDO_REGISTER);
1460 : }
1461 : /* As we did not change CFG since LRA start we can use
1462 : DF-infrastructure solver to solve live data flow problem. */
1463 11447310 : for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1464 : {
1465 11326812 : if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1466 0 : bitmap_clear_bit (&all_hard_regs_bitmap, i);
1467 : }
1468 120498 : df_simple_dataflow
1469 120498 : (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1470 : live_trans_fun, &all_blocks,
1471 : df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1472 120498 : if (lra_dump_file != NULL)
1473 : {
1474 7 : fprintf (lra_dump_file,
1475 : "Global pseudo live data have been updated:\n");
1476 7 : basic_block bb;
1477 35 : FOR_EACH_BB_FN (bb, cfun)
1478 : {
1479 28 : bb_data_t bb_info = get_bb_data (bb);
1480 28 : bitmap bb_livein = df_get_live_in (bb);
1481 28 : bitmap bb_liveout = df_get_live_out (bb);
1482 :
1483 28 : fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1484 28 : lra_dump_bitmap_with_title (" gen:",
1485 : &bb_info->gen_pseudos, bb->index);
1486 28 : lra_dump_bitmap_with_title (" killed:",
1487 : &bb_info->killed_pseudos, bb->index);
1488 28 : lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1489 28 : lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1490 : }
1491 : }
1492 : }
1493 1614186 : lra_live_max_point = curr_point;
1494 1614186 : if (lra_dump_file != NULL)
1495 92 : print_live_ranges (lra_dump_file);
1496 : /* Clean up. */
1497 1614186 : sparseset_free (unused_set);
1498 1614186 : sparseset_free (dead_set);
1499 1614186 : sparseset_free (start_dying);
1500 1614186 : sparseset_free (start_living);
1501 1614186 : sparseset_free (pseudos_live_through_calls);
1502 1614186 : sparseset_free (pseudos_live_through_setjumps);
1503 1614186 : sparseset_free (pseudos_live);
1504 1614186 : compress_live_ranges ();
1505 1614186 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1506 1614186 : return bb_live_change_p;
1507 : }
1508 :
1509 : /* The main entry function creates live-ranges and other live info
1510 : necessary for the assignment sub-pass. It uses
1511 : lra_creates_live_ranges_1 -- so read comments for the
1512 : function. */
1513 : void
1514 1700180 : lra_create_live_ranges (bool all_p, bool dead_insn_p)
1515 : {
1516 1700180 : if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1517 : return;
1518 120498 : if (lra_dump_file != NULL)
1519 7 : fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1520 : /* Live info was changed on a bb border. It means that some info,
1521 : e.g. about conflict regs, calls crossed, and live ranges may be
1522 : wrong. We need this info for allocation. So recalculate it
1523 : again but without removing dead insns which can change live info
1524 : again. Repetitive live range calculations are expensive therefore
1525 : we stop here as we already have correct info although some
1526 : improvement in rare cases could be possible on this sub-pass if
1527 : we do dead insn elimination again (still the improvement may
1528 : happen later). */
1529 120498 : lra_clear_live_ranges ();
1530 120498 : bool res = lra_create_live_ranges_1 (all_p, false);
1531 120498 : lra_assert (! res);
1532 : }
1533 :
1534 : /* Run lra_create_live_ranges if !complete_info_p. Return FALSE iff
1535 : live ranges are known to have remained unchanged. */
1536 :
1537 : bool
1538 0 : lra_complete_live_ranges (void)
1539 : {
1540 0 : if (complete_info_p)
1541 : return false;
1542 :
1543 0 : lra_create_live_ranges (true, true);
1544 0 : return true;
1545 : }
1546 :
1547 : /* Finish all live ranges. */
1548 : void
1549 1806059 : lra_clear_live_ranges (void)
1550 : {
1551 1806059 : int i;
1552 :
1553 341578482 : for (i = 0; i < max_reg_num (); i++)
1554 339772423 : free_live_range_list (lra_reg_info[i].live_ranges);
1555 1806059 : point_freq_vec.release ();
1556 1806059 : }
1557 :
1558 : /* Initialize live ranges data once per function. */
1559 : void
1560 1517127 : lra_live_ranges_init (void)
1561 : {
1562 1517127 : bitmap_initialize (&temp_bitmap, ®_obstack);
1563 1517127 : initiate_live_solver ();
1564 1517127 : }
1565 :
1566 : /* Finish live ranges data once per function. */
1567 : void
1568 1517127 : lra_live_ranges_finish (void)
1569 : {
1570 1517127 : finish_live_solver ();
1571 1517127 : bitmap_clear (&temp_bitmap);
1572 1517127 : lra_live_range_pool.release ();
1573 1517127 : }
|