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 325791417 : free_live_range_list (lra_live_range_t lr)
105 : {
106 325791417 : lra_live_range_t next;
107 :
108 428103935 : while (lr != NULL)
109 : {
110 102312518 : next = lr->next;
111 102312518 : lra_live_range_pool.remove (lr);
112 102312518 : lr = next;
113 : }
114 325791417 : }
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 112760226 : 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 112760226 : p->regno = regno;
131 112760226 : p->start = start;
132 112760226 : p->finish = finish;
133 112760226 : p->next = next;
134 112760226 : return p;
135 : }
136 :
137 : /* Copy live range R and return the result. */
138 : static lra_live_range_t
139 2122537 : copy_live_range (lra_live_range_t r)
140 : {
141 2122537 : 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 1428029 : lra_copy_live_range_list (lra_live_range_t r)
147 : {
148 1428029 : lra_live_range_t p, first, *chain;
149 :
150 1428029 : first = NULL;
151 3550566 : for (chain = &first; r != NULL; r = r->next)
152 : {
153 2122537 : p = copy_live_range (r);
154 2122537 : *chain = p;
155 2122537 : chain = &p->next;
156 : }
157 1428029 : 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 1428029 : lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
166 : {
167 1428029 : lra_live_range_t first, last;
168 :
169 1428029 : if (r1 == NULL)
170 : return r2;
171 667778 : if (r2 == NULL)
172 : return r1;
173 5870858 : for (first = last = NULL; r1 != NULL && r2 != NULL;)
174 : {
175 5203080 : if (r1->start < r2->start)
176 412458 : std::swap (r1, r2);
177 :
178 5203080 : if (r1->start == r2->finish + 1)
179 : {
180 : /* Joint ranges: merge r1 and r2 into r1. */
181 41043 : r1->start = r2->start;
182 41043 : lra_live_range_t temp = r2;
183 41043 : r2 = r2->next;
184 41043 : lra_live_range_pool.remove (temp);
185 : }
186 : else
187 : {
188 5162037 : gcc_assert (r2->finish + 1 < r1->start);
189 : /* Add r1 to the result. */
190 5162037 : if (first == NULL)
191 : first = last = r1;
192 : else
193 : {
194 4497304 : last->next = r1;
195 4497304 : last = r1;
196 : }
197 5162037 : r1 = r1->next;
198 : }
199 : }
200 667778 : if (r1 != NULL)
201 : {
202 13163 : if (first == NULL)
203 : first = r1;
204 : else
205 10118 : last->next = r1;
206 : }
207 : else
208 : {
209 654615 : lra_assert (r2 != NULL);
210 654615 : if (first == NULL)
211 : first = r2;
212 : else
213 654615 : last->next = r2;
214 : }
215 : return first;
216 : }
217 :
218 : /* Return TRUE if live ranges R1 and R2 intersect. */
219 : bool
220 25973247 : 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 45085403 : while (r1 != NULL && r2 != NULL)
224 : {
225 44415416 : if (r1->start > r2->finish)
226 17507262 : r1 = r1->next;
227 26908154 : else if (r2->start > r1->finish)
228 1604894 : 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 797027256 : sparseset_contains_pseudos_p (sparseset a)
243 : {
244 797027256 : int regno;
245 938011529 : EXECUTE_IF_SET_IN_SPARSESET (a, regno)
246 340530628 : 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 1292309374 : update_pseudo_point (int regno, int point, enum point_type type)
257 : {
258 1292309374 : lra_live_range_t p;
259 :
260 : /* Don't compute points for hard registers. */
261 1292309374 : if (HARD_REGISTER_NUM_P (regno))
262 : return;
263 :
264 1175244322 : if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
265 : {
266 1163600556 : if (type == DEF_POINT)
267 : {
268 500973200 : if (sparseset_bit_p (pseudos_live, regno))
269 : {
270 500973200 : p = lra_reg_info[regno].live_ranges;
271 500973200 : lra_assert (p != NULL);
272 500973200 : p->finish = point;
273 : }
274 : }
275 : else /* USE_POINT */
276 : {
277 662627356 : if (!sparseset_bit_p (pseudos_live, regno)
278 662627356 : && ((p = lra_reg_info[regno].live_ranges) == NULL
279 412128133 : || (p->finish != point && p->finish + 1 != point)))
280 112760226 : lra_reg_info[regno].live_ranges
281 112760226 : = 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 234679751 : make_hard_regno_live (int regno)
293 : {
294 234679751 : lra_assert (HARD_REGISTER_NUM_P (regno));
295 234679751 : if (TEST_HARD_REG_BIT (hard_regs_live, regno)
296 234679751 : || TEST_HARD_REG_BIT (eliminable_regset, regno))
297 : return;
298 127634187 : SET_HARD_REG_BIT (hard_regs_live, regno);
299 127634187 : sparseset_set_bit (start_living, regno);
300 127634187 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
301 74458766 : 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 125937688 : make_hard_regno_dead (int regno)
309 : {
310 125937688 : if (TEST_HARD_REG_BIT (eliminable_regset, regno))
311 : return;
312 :
313 125936785 : lra_assert (HARD_REGISTER_NUM_P (regno));
314 125936785 : unsigned int i;
315 1303491474 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
316 1177554689 : SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
317 :
318 125936785 : if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
319 : return;
320 125936041 : CLEAR_HARD_REG_BIT (hard_regs_live, regno);
321 125936041 : sparseset_set_bit (start_dying, regno);
322 125936041 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
323 : {
324 74458508 : bitmap_clear_bit (bb_gen_pseudos, regno);
325 74458508 : 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 673185383 : mark_pseudo_live (int regno)
332 : {
333 673185383 : lra_assert (!HARD_REGISTER_NUM_P (regno));
334 673185383 : if (sparseset_bit_p (pseudos_live, regno))
335 : return;
336 :
337 510621831 : sparseset_set_bit (pseudos_live, regno);
338 510621831 : sparseset_set_bit (start_living, regno);
339 : }
340 :
341 : /* Mark pseudo REGNO as now being dead and update START_DYING. */
342 : static void
343 510621831 : mark_pseudo_dead (int regno)
344 : {
345 510621831 : lra_assert (!HARD_REGISTER_NUM_P (regno));
346 510621831 : lra_reg_info[regno].conflict_hard_regs |= hard_regs_live;
347 510621831 : if (!sparseset_bit_p (pseudos_live, regno))
348 : return;
349 :
350 510621831 : sparseset_clear_bit (pseudos_live, regno);
351 510621831 : 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 376521412 : mark_regno_live (int regno, machine_mode mode)
358 : {
359 376521412 : int last;
360 :
361 376521412 : if (HARD_REGISTER_NUM_P (regno))
362 : {
363 219216783 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
364 109911015 : make_hard_regno_live (regno);
365 : }
366 : else
367 : {
368 267215644 : mark_pseudo_live (regno);
369 267215644 : bitmap_set_bit (bb_gen_pseudos, regno);
370 : }
371 376521412 : }
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 151443445 : mark_regno_dead (int regno, machine_mode mode)
378 : {
379 151443445 : int last;
380 :
381 151443445 : if (HARD_REGISTER_NUM_P (regno))
382 : {
383 78126730 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
384 39294866 : make_hard_regno_dead (regno);
385 : }
386 : else
387 : {
388 112611581 : mark_pseudo_dead (regno);
389 112611581 : bitmap_clear_bit (bb_gen_pseudos, regno);
390 112611581 : bitmap_set_bit (bb_killed_pseudos, regno);
391 : }
392 151443445 : }
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 75389570 : get_bb_data (basic_block bb)
421 : {
422 75389570 : return &bb_data[(bb)->index];
423 : }
424 :
425 : static inline bb_data_t
426 8192791 : get_bb_data_by_index (int index)
427 : {
428 8192791 : 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 8192791 : live_trans_fun (int bb_index)
442 : {
443 8192791 : basic_block bb = get_bb_data_by_index (bb_index)->bb;
444 8192791 : bitmap bb_liveout = df_get_live_out (bb);
445 8192791 : bitmap bb_livein = df_get_live_in (bb);
446 8192791 : bb_data_t bb_info = get_bb_data (bb);
447 :
448 8192791 : bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
449 8192791 : return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
450 8192791 : &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 357951 : live_con_fun_0 (basic_block bb)
457 : {
458 357951 : bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
459 357951 : }
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 11949610 : live_con_fun_n (edge e)
469 : {
470 11949610 : basic_block bb = e->src;
471 11949610 : basic_block dest = e->dest;
472 11949610 : bitmap bb_liveout = df_get_live_out (bb);
473 11949610 : bitmap dest_livein = df_get_live_in (dest);
474 :
475 11949610 : return bitmap_ior_and_compl_into (bb_liveout,
476 11949610 : 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 1480947 : initiate_live_solver (void)
486 : {
487 1480947 : bitmap_initialize (&all_hard_regs_bitmap, ®_obstack);
488 1480947 : bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
489 1480947 : bb_data = XNEWVEC (class bb_data_pseudos, last_basic_block_for_fn (cfun));
490 1480947 : bitmap_initialize (&all_blocks, ®_obstack);
491 :
492 1480947 : basic_block bb;
493 18984256 : FOR_ALL_BB_FN (bb, cfun)
494 : {
495 17503309 : bb_data_t bb_info = get_bb_data (bb);
496 17503309 : bb_info->bb = bb;
497 17503309 : bitmap_initialize (&bb_info->killed_pseudos, ®_obstack);
498 17503309 : bitmap_initialize (&bb_info->gen_pseudos, ®_obstack);
499 17503309 : bitmap_set_bit (&all_blocks, bb->index);
500 : }
501 1480947 : }
502 :
503 : /* Free all data needed for global pseudo live analysis. */
504 : static void
505 1480947 : finish_live_solver (void)
506 : {
507 1480947 : basic_block bb;
508 :
509 1480947 : bitmap_clear (&all_blocks);
510 18984256 : FOR_ALL_BB_FN (bb, cfun)
511 : {
512 17503309 : bb_data_t bb_info = get_bb_data (bb);
513 17503309 : bitmap_clear (&bb_info->killed_pseudos);
514 17503309 : bitmap_clear (&bb_info->gen_pseudos);
515 : }
516 1480947 : free (bb_data);
517 1480947 : bitmap_clear (&all_hard_regs_bitmap);
518 1480947 : }
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 225481456 : next_program_point (int &point, int freq)
539 : {
540 225481456 : point_freq_vec.safe_push (freq);
541 225481456 : lra_point_freq = point_freq_vec.address ();
542 225481456 : point++;
543 225481456 : }
544 :
545 : /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
546 : void
547 15495552 : lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
548 : int hard_regno, int profit)
549 : {
550 15495552 : lra_assert (regno >= lra_constraint_new_regno_start);
551 15495552 : if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
552 2897045 : lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
553 12598507 : else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
554 75947 : lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
555 12522560 : else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
556 : {
557 9897376 : lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
558 9897376 : lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
559 : }
560 2625184 : else if (lra_reg_info[regno].preferred_hard_regno2 < 0
561 69416 : || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
562 : {
563 2582024 : lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
564 2582024 : lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
565 : }
566 : else
567 : return;
568 : /* Keep the 1st hard regno as more profitable. */
569 15452392 : if (lra_reg_info[regno].preferred_hard_regno1 >= 0
570 15452392 : && lra_reg_info[regno].preferred_hard_regno2 >= 0
571 2734323 : && (lra_reg_info[regno].preferred_hard_regno_profit2
572 2734323 : > lra_reg_info[regno].preferred_hard_regno_profit1))
573 : {
574 100507 : std::swap (lra_reg_info[regno].preferred_hard_regno1,
575 : lra_reg_info[regno].preferred_hard_regno2);
576 100507 : std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
577 : lra_reg_info[regno].preferred_hard_regno_profit2);
578 : }
579 15452392 : if (lra_dump_file != NULL)
580 : {
581 253 : if ((hard_regno = lra_reg_info[regno].preferred_hard_regno1) >= 0)
582 253 : 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 253 : if ((hard_regno = lra_reg_info[regno].preferred_hard_regno2) >= 0)
587 97 : 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 465790780 : check_pseudos_live_through_calls (int regno, const function_abi &abi)
601 : {
602 465790780 : if (! sparseset_bit_p (pseudos_live_through_calls, regno))
603 : return;
604 :
605 95054967 : machine_mode mode = PSEUDO_REGNO_MODE (regno);
606 :
607 95054967 : sparseset_clear_bit (pseudos_live_through_calls, regno);
608 95054967 : lra_reg_info[regno].conflict_hard_regs |= abi.mode_clobbers (mode);
609 95054967 : if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
610 : return;
611 7149 : 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 7149 : 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 386884862 : reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
622 : {
623 386884862 : return (n_alt == LRA_UNKNOWN_ALT
624 386884862 : ? reg->early_clobber_alts != 0
625 : : (n_alt != LRA_NON_CLOBBERED_ALT
626 369722578 : && 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 155385044 : clear_sparseset_regnos (sparseset set, int regno, enum machine_mode mode)
632 : {
633 155385044 : if (regno >= FIRST_PSEUDO_REGISTER)
634 : {
635 85723900 : sparseset_clear_bit (dead_set, regno);
636 85723900 : return;
637 : }
638 139577398 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
639 69916254 : 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 158783725 : regnos_in_sparseset_p (sparseset set, int regno, enum machine_mode mode)
646 : {
647 158783725 : if (regno >= FIRST_PSEUDO_REGISTER)
648 88913297 : return sparseset_bit_p (dead_set, regno);
649 139786682 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
650 70125538 : 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 32190133 : process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
665 : {
666 32190133 : int i, regno, freq;
667 32190133 : unsigned int j;
668 32190133 : bitmap_iterator bi;
669 32190133 : bitmap reg_live_out;
670 32190133 : unsigned int px;
671 32190133 : rtx_insn *next;
672 32190133 : rtx link, *link_loc;
673 32190133 : bool need_curr_point_incr;
674 : /* Only has a meaningful value once we've seen a call. */
675 32190133 : function_abi last_call_abi = default_function_abi;
676 :
677 32190133 : reg_live_out = df_get_live_out (bb);
678 32190133 : sparseset_clear (pseudos_live);
679 32190133 : sparseset_clear (pseudos_live_through_calls);
680 32190133 : sparseset_clear (pseudos_live_through_setjumps);
681 64380266 : REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
682 32190133 : hard_regs_live &= ~eliminable_regset;
683 438159872 : EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
684 : {
685 405969739 : update_pseudo_point (j, curr_point, USE_POINT);
686 405969739 : mark_pseudo_live (j);
687 : }
688 :
689 32190133 : bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
690 32190133 : bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
691 32190133 : bitmap_clear (bb_gen_pseudos);
692 32190133 : bitmap_clear (bb_killed_pseudos);
693 32190133 : freq = REG_FREQ_FROM_BB (bb);
694 :
695 32190133 : if (lra_dump_file != NULL)
696 571 : 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 907198500 : FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
708 : {
709 421409117 : bool call_p;
710 421409117 : int n_alt, dst_regno, src_regno;
711 421409117 : rtx set;
712 421409117 : struct lra_insn_reg *reg;
713 :
714 421409117 : if (!NONDEBUG_INSN_P (curr_insn))
715 200032891 : continue;
716 :
717 221376226 : curr_id = lra_get_insn_recog_data (curr_insn);
718 221376226 : curr_static_id = curr_id->insn_static_data;
719 221376226 : n_alt = curr_id->used_insn_alternative;
720 221376226 : if (lra_dump_file != NULL)
721 2710 : fprintf (lra_dump_file, " Insn %u: point = %d, n_alt = %d\n",
722 2710 : INSN_UID (curr_insn), curr_point, n_alt);
723 :
724 221376226 : set = single_set (curr_insn);
725 :
726 221376226 : if (dead_insn_p && set != NULL_RTX
727 170727164 : && REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
728 88849179 : && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
729 88621097 : && ! may_trap_p (PATTERN (curr_insn))
730 : /* Don't do premature remove of pic offset pseudo as we can
731 : start to use it after some reload generation. */
732 301171526 : && (pic_offset_table_rtx == NULL_RTX
733 8915013 : || pic_offset_table_rtx != SET_DEST (set)))
734 : {
735 79730194 : bool remove_p = true;
736 :
737 80308041 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
738 80259177 : if (reg->type != OP_IN
739 80259177 : && (reg->regno < FIRST_PSEUDO_REGISTER
740 79730326 : ? TEST_HARD_REG_BIT (hard_regs_live, reg->regno)
741 79730324 : : sparseset_bit_p (pseudos_live, reg->regno)))
742 : {
743 : remove_p = false;
744 : break;
745 : }
746 80970812 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
747 15813713 : if (reg->type != OP_IN)
748 : {
749 : remove_p = false;
750 : break;
751 : }
752 :
753 79730194 : if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
754 : {
755 43564 : dst_regno = REGNO (SET_DEST (set));
756 43564 : if (lra_dump_file != NULL)
757 0 : fprintf (lra_dump_file, " Deleting dead insn %u\n",
758 0 : INSN_UID (curr_insn));
759 43564 : lra_set_insn_deleted (curr_insn);
760 43564 : if (lra_reg_info[dst_regno].nrefs == 0)
761 : {
762 : /* There might be some debug insns with the pseudo. */
763 6627 : unsigned int uid;
764 6627 : rtx_insn *insn;
765 :
766 6627 : bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
767 6874 : EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
768 : {
769 247 : insn = lra_insn_recog_data[uid]->insn;
770 247 : lra_substitute_pseudo_within_insn (insn, dst_regno,
771 : SET_SRC (set), true);
772 247 : lra_update_insn_regno_info (insn);
773 : }
774 : }
775 43564 : continue;
776 43564 : }
777 : }
778 :
779 : /* Update max ref width and hard reg usage. */
780 577966864 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
781 : {
782 356634202 : int regno = reg->regno;
783 :
784 356634202 : lra_update_biggest_mode (regno, reg->biggest_mode);
785 356634202 : if (HARD_REGISTER_NUM_P (regno))
786 98230222 : lra_hard_reg_usage[regno] += freq;
787 : }
788 :
789 221332662 : call_p = CALL_P (curr_insn);
790 :
791 : /* If we have a simple register copy and the source reg is live after
792 : this instruction, then remove the source reg from the live set so
793 : that it will not conflict with the destination reg. */
794 221332662 : rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
795 221332662 : if (ignore_reg != NULL_RTX)
796 : {
797 59203798 : int ignore_regno = REGNO (ignore_reg);
798 59203798 : if (HARD_REGISTER_NUM_P (ignore_regno)
799 59203798 : && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
800 172107 : CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
801 59031691 : else if (!HARD_REGISTER_NUM_P (ignore_regno)
802 59031691 : && sparseset_bit_p (pseudos_live, ignore_regno))
803 11717194 : sparseset_clear_bit (pseudos_live, ignore_regno);
804 : else
805 : /* We don't need any special handling of the source reg if
806 : it is dead after this instruction. */
807 : ignore_reg = NULL_RTX;
808 : }
809 :
810 211580196 : src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
811 302155306 : ? REGNO (SET_SRC (set)) : -1);
812 211580196 : dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
813 157412983 : ? REGNO (SET_DEST (set)) : -1);
814 221332662 : if (complete_info_p
815 220509440 : && src_regno >= 0 && dst_regno >= 0
816 : /* Check that source regno does not conflict with
817 : destination regno to exclude most impossible
818 : preferences. */
819 280397943 : && (((!HARD_REGISTER_NUM_P (src_regno)
820 52117026 : && (! sparseset_bit_p (pseudos_live, src_regno)
821 9566 : || (!HARD_REGISTER_NUM_P (dst_regno)
822 59065281 : && lra_reg_val_equal_p (src_regno,
823 : lra_reg_info[dst_regno].val,
824 0 : lra_reg_info[dst_regno].offset))))
825 : || (HARD_REGISTER_NUM_P (src_regno)
826 6948255 : && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
827 : /* It might be 'inheritance pseudo <- reload pseudo'. */
828 9579 : || (src_regno >= lra_constraint_new_regno_start
829 225 : && dst_regno >= lra_constraint_new_regno_start
830 : /* Remember to skip special cases where src/dest regnos are
831 : the same, e.g. insn SET pattern has matching constraints
832 : like =r,0. */
833 0 : && src_regno != dst_regno)))
834 : {
835 59055702 : int hard_regno = -1, regno = -1;
836 :
837 59055702 : if (dst_regno >= lra_constraint_new_regno_start
838 15801309 : && src_regno >= lra_constraint_new_regno_start)
839 : {
840 : /* It might be still an original (non-reload) insn with
841 : one unused output and a constraint requiring to use
842 : the same reg for input/output operands. In this case
843 : dst_regno and src_regno have the same value, we don't
844 : need a misleading copy for this case. */
845 5899066 : if (dst_regno != src_regno)
846 5899066 : lra_create_copy (dst_regno, src_regno, freq);
847 : }
848 53156636 : else if (dst_regno >= lra_constraint_new_regno_start)
849 : {
850 9902243 : if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
851 9797115 : hard_regno = reg_renumber[src_regno];
852 : regno = dst_regno;
853 : }
854 43254393 : else if (src_regno >= lra_constraint_new_regno_start)
855 : {
856 10884759 : if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
857 9212346 : hard_regno = reg_renumber[dst_regno];
858 : regno = src_regno;
859 : }
860 59055702 : if (regno >= 0 && hard_regno >= 0)
861 12586580 : lra_setup_reload_pseudo_preferenced_hard_reg
862 12586580 : (regno, hard_regno, freq);
863 : }
864 :
865 221332662 : sparseset_clear (start_living);
866 :
867 : /* Mark each defined value as live. We need to do this for
868 : unused values because they still conflict with quantities
869 : that are live at the time of the definition. */
870 577966864 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
871 356634202 : if (reg->type != OP_IN)
872 : {
873 152546248 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
874 152546248 : mark_regno_live (reg->regno, reg->biggest_mode);
875 : /* ??? Should be a no-op for unused registers. */
876 152546248 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
877 : }
878 :
879 278255180 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
880 56922518 : if (reg->type != OP_IN)
881 40896183 : make_hard_regno_live (reg->regno);
882 :
883 221332662 : if (curr_id->arg_hard_regs != NULL)
884 31863800 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
885 22524394 : if (!HARD_REGISTER_NUM_P (regno))
886 : /* It is a clobber. */
887 944146 : make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
888 :
889 221332662 : sparseset_copy (unused_set, start_living);
890 :
891 221332662 : sparseset_clear (start_dying);
892 :
893 : /* See which defined values die here. */
894 577966864 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
895 356634202 : if (reg->type != OP_IN
896 660280426 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
897 : {
898 151099976 : if (reg->type == OP_OUT)
899 131468483 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
900 151099976 : mark_regno_dead (reg->regno, reg->biggest_mode);
901 : }
902 :
903 278255180 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
904 56922518 : if (reg->type != OP_IN
905 114400550 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
906 16581849 : make_hard_regno_dead (reg->regno);
907 :
908 221332662 : if (curr_id->arg_hard_regs != NULL)
909 31863800 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
910 22524394 : if (!HARD_REGISTER_NUM_P (regno))
911 : /* It is a clobber. */
912 944146 : make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
913 :
914 221332662 : if (call_p)
915 : {
916 12068718 : function_abi call_abi = insn_callee_abi (curr_insn);
917 :
918 12068718 : if (last_call_abi != call_abi)
919 7181993 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
920 4936131 : check_pseudos_live_through_calls (j, last_call_abi);
921 :
922 12068718 : last_call_abi = call_abi;
923 :
924 12068718 : sparseset_ior (pseudos_live_through_calls,
925 : pseudos_live_through_calls, pseudos_live);
926 12068718 : if (cfun->has_nonlocal_label
927 12068718 : || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
928 12064530 : && (find_reg_note (curr_insn, REG_SETJMP, NULL_RTX)
929 : != NULL_RTX)))
930 6717 : sparseset_ior (pseudos_live_through_setjumps,
931 : pseudos_live_through_setjumps, pseudos_live);
932 : }
933 :
934 : /* Increment the current program point if we must. */
935 221332662 : if (sparseset_contains_pseudos_p (unused_set)
936 221332662 : || sparseset_contains_pseudos_p (start_dying))
937 112041159 : next_program_point (curr_point, freq);
938 :
939 : /* If we removed the source reg from a simple register copy from the
940 : live set above, then add it back now so we don't accidentally add
941 : it to the start_living set below. */
942 221332662 : if (ignore_reg != NULL_RTX)
943 : {
944 11889301 : int ignore_regno = REGNO (ignore_reg);
945 11889301 : if (HARD_REGISTER_NUM_P (ignore_regno))
946 172107 : SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
947 : else
948 11717194 : sparseset_set_bit (pseudos_live, ignore_regno);
949 : }
950 :
951 221332662 : sparseset_clear (start_living);
952 :
953 : /* Mark each used value as live. */
954 577966864 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
955 356634202 : if (reg->type != OP_OUT)
956 : {
957 223858395 : if (reg->type == OP_IN)
958 204087954 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
959 223858395 : mark_regno_live (reg->regno, reg->biggest_mode);
960 223858395 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
961 : }
962 :
963 278255180 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
964 56922518 : if (reg->type != OP_OUT)
965 16510145 : make_hard_regno_live (reg->regno);
966 :
967 221332662 : if (curr_id->arg_hard_regs != NULL)
968 : /* Make argument hard registers live. */
969 31863800 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
970 22524394 : if (HARD_REGISTER_NUM_P (regno))
971 21580248 : make_hard_regno_live (regno);
972 :
973 221332662 : sparseset_and_compl (dead_set, start_living, start_dying);
974 :
975 221332662 : sparseset_clear (start_dying);
976 :
977 : /* Mark early clobber outputs dead. */
978 577966864 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
979 356634202 : if (reg->type != OP_IN
980 509523919 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
981 : {
982 343469 : if (reg->type == OP_OUT)
983 226700 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
984 343469 : mark_regno_dead (reg->regno, reg->biggest_mode);
985 :
986 : /* We're done processing inputs, so make sure early clobber
987 : operands that are both inputs and outputs are still live. */
988 343469 : if (reg->type == OP_INOUT)
989 116769 : mark_regno_live (reg->regno, reg->biggest_mode);
990 : }
991 :
992 278255180 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
993 56922518 : if (reg->type != OP_IN
994 122133035 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
995 : {
996 24314334 : struct lra_insn_reg *reg2;
997 :
998 : /* We can have early clobbered non-operand hard reg and
999 : the same hard reg as an insn input. Don't make hard
1000 : reg dead before the insns. */
1001 48927413 : for (reg2 = curr_static_id->hard_regs; reg2 != NULL; reg2 = reg2->next)
1002 24635875 : if (reg2->type != OP_OUT && reg2->regno == reg->regno)
1003 : break;
1004 24314334 : if (reg2 != NULL)
1005 22796 : continue;
1006 :
1007 : HARD_REG_SET clobbered_regset;
1008 24291538 : CLEAR_HARD_REG_SET (clobbered_regset);
1009 24291538 : SET_HARD_REG_BIT (clobbered_regset, reg->regno);
1010 :
1011 67436147 : for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
1012 30634651 : if (reg2->type != OP_OUT && reg2->regno < FIRST_PSEUDO_REGISTER
1013 51449845 : && ira_hard_reg_set_intersection_p (reg2->regno,
1014 8292511 : reg2->biggest_mode,
1015 : clobbered_regset))
1016 : break;
1017 24291538 : if (reg2 == NULL)
1018 : {
1019 24278813 : make_hard_regno_dead (reg->regno);
1020 : }
1021 : else
1022 : {
1023 159405 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1024 146680 : SET_HARD_REG_BIT (lra_reg_info[j].conflict_hard_regs,
1025 : reg->regno);
1026 : }
1027 : }
1028 :
1029 : /* Increment the current program point if we must. */
1030 221332662 : if (sparseset_contains_pseudos_p (dead_set)
1031 221332662 : || sparseset_contains_pseudos_p (start_dying))
1032 87505196 : next_program_point (curr_point, freq);
1033 :
1034 : /* Update notes. */
1035 445263800 : for (link_loc = ®_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1036 : {
1037 223931138 : if (REG_NOTE_KIND (link) != REG_DEAD
1038 92514168 : && REG_NOTE_KIND (link) != REG_UNUSED)
1039 : ;
1040 158783725 : else if (REG_P (XEXP (link, 0)))
1041 : {
1042 158783725 : rtx note_reg = XEXP (link, 0);
1043 158783725 : int note_regno = REGNO (note_reg);
1044 :
1045 162182406 : if ((REG_NOTE_KIND (link) == REG_DEAD
1046 131416970 : && ! regnos_in_sparseset_p (dead_set, note_regno,
1047 131416970 : GET_MODE (note_reg)))
1048 287929753 : || (REG_NOTE_KIND (link) == REG_UNUSED
1049 27366755 : && ! regnos_in_sparseset_p (unused_set, note_regno,
1050 27366755 : GET_MODE (note_reg))))
1051 : {
1052 3398681 : *link_loc = XEXP (link, 1);
1053 3398681 : continue;
1054 : }
1055 155385044 : if (REG_NOTE_KIND (link) == REG_DEAD)
1056 129146028 : clear_sparseset_regnos (dead_set, note_regno,
1057 129146028 : GET_MODE (note_reg));
1058 26239016 : else if (REG_NOTE_KIND (link) == REG_UNUSED)
1059 26239016 : clear_sparseset_regnos (unused_set, note_regno,
1060 26239016 : GET_MODE (note_reg));
1061 : }
1062 220532457 : link_loc = &XEXP (link, 1);
1063 : }
1064 230228379 : EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1065 8895717 : add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1066 444517322 : EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1067 1851998 : add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1068 : }
1069 :
1070 32190133 : if (bb_has_eh_pred (bb))
1071 : /* Any pseudos that are currently live conflict with the eh_return
1072 : data registers. For liveness purposes, these registers are set
1073 : by artificial definitions at the start of the BB, so are not
1074 : actually live on entry. */
1075 525423 : for (j = 0; ; ++j)
1076 : {
1077 1576269 : unsigned int regno = EH_RETURN_DATA_REGNO (j);
1078 :
1079 1050846 : if (regno == INVALID_REGNUM)
1080 : break;
1081 :
1082 1050846 : make_hard_regno_live (regno);
1083 1050846 : make_hard_regno_dead (regno);
1084 1050846 : }
1085 :
1086 : /* Pseudos can't go in stack regs at the start of a basic block that
1087 : is reached by an abnormal edge. Likewise for registers that are at
1088 : least partly call clobbered, because caller-save, fixup_abnormal_edges
1089 : and possibly the table driven EH machinery are not quite ready to
1090 : handle such pseudos live across such edges. */
1091 32190133 : if (bb_has_abnormal_pred (bb))
1092 : {
1093 : HARD_REG_SET clobbers;
1094 :
1095 528705 : CLEAR_HARD_REG_SET (clobbers);
1096 : #ifdef STACK_REGS
1097 1639521 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1098 1110816 : lra_reg_info[px].no_stack_p = true;
1099 4758345 : for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1100 4229640 : SET_HARD_REG_BIT (clobbers, px);
1101 : #endif
1102 : /* No need to record conflicts for call clobbered regs if we
1103 : have nonlocal labels around, as we don't ever try to
1104 : allocate such regs in this case. */
1105 528705 : if (!cfun->has_nonlocal_label
1106 528705 : && has_abnormal_call_or_eh_pred_edge_p (bb))
1107 48863502 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1108 48338088 : if (eh_edge_abi.clobbers_at_least_part_of_reg_p (px)
1109 : #ifdef REAL_PIC_OFFSET_TABLE_REGNUM
1110 : /* We should create a conflict of PIC pseudo with PIC
1111 : hard reg as PIC hard reg can have a wrong value after
1112 : jump described by the abnormal edge. In this case we
1113 : cannot allocate PIC hard reg to PIC pseudo as PIC
1114 : pseudo will also have a wrong value. */
1115 48790596 : || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1116 525414 : && pic_offset_table_rtx != NULL_RTX
1117 22190 : && !HARD_REGISTER_P (pic_offset_table_rtx))
1118 : #endif
1119 : )
1120 43760840 : SET_HARD_REG_BIT (clobbers, px);
1121 :
1122 528705 : clobbers &= ~hard_regs_live;
1123 49169565 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1124 48640860 : if (TEST_HARD_REG_BIT (clobbers, px))
1125 : {
1126 43787168 : make_hard_regno_live (px);
1127 43787168 : make_hard_regno_dead (px);
1128 : }
1129 : }
1130 :
1131 32190133 : bool live_change_p = false;
1132 : /* Check if bb border live info was changed. */
1133 32190133 : unsigned int live_pseudos_num = 0;
1134 429516733 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1135 : FIRST_PSEUDO_REGISTER, j, bi)
1136 : {
1137 397556804 : live_pseudos_num++;
1138 397556804 : if (! sparseset_bit_p (pseudos_live, j))
1139 : {
1140 230204 : live_change_p = true;
1141 230204 : if (lra_dump_file != NULL)
1142 14 : fprintf (lra_dump_file,
1143 : " r%d is removed as live at bb%d start\n", j, bb->index);
1144 : break;
1145 : }
1146 : }
1147 14 : if (! live_change_p
1148 31959929 : && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1149 : {
1150 182727 : live_change_p = true;
1151 182727 : if (lra_dump_file != NULL)
1152 28 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1153 7 : if (! bitmap_bit_p (df_get_live_in (bb), j))
1154 7 : fprintf (lra_dump_file,
1155 : " r%d is added to live at bb%d start\n", j, bb->index);
1156 : }
1157 : /* See if we'll need an increment at the end of this basic block.
1158 : An increment is needed if the PSEUDOS_LIVE set is not empty,
1159 : to make sure the finish points are set up correctly. */
1160 32190133 : need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1161 :
1162 828210633 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1163 : {
1164 398010250 : update_pseudo_point (i, curr_point, DEF_POINT);
1165 398010250 : mark_pseudo_dead (i);
1166 : }
1167 :
1168 123322068 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1169 : {
1170 112882166 : if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1171 : break;
1172 91131935 : if (sparseset_bit_p (pseudos_live_through_calls, j))
1173 84450006 : check_pseudos_live_through_calls (j, last_call_abi);
1174 : }
1175 :
1176 2993682369 : for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1177 : {
1178 2961492236 : if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1179 2917205859 : continue;
1180 :
1181 44286377 : if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1182 44286377 : continue;
1183 :
1184 0 : if (bitmap_bit_p (df_get_live_in (bb), i))
1185 0 : continue;
1186 :
1187 0 : live_change_p = true;
1188 0 : if (lra_dump_file)
1189 0 : fprintf (lra_dump_file,
1190 : " hard reg r%d is added to live at bb%d start\n", i,
1191 : bb->index);
1192 0 : bitmap_set_bit (df_get_live_in (bb), i);
1193 : }
1194 :
1195 32190133 : if (need_curr_point_incr)
1196 25935101 : next_program_point (curr_point, freq);
1197 :
1198 32190133 : return live_change_p;
1199 : }
1200 :
1201 : /* Compress pseudo live ranges by removing program points where
1202 : nothing happens. Complexity of many algorithms in LRA is linear
1203 : function of program points number. To speed up the code we try to
1204 : minimize the number of the program points here. */
1205 : static void
1206 1573994 : remove_some_program_points_and_update_live_ranges (void)
1207 : {
1208 1573994 : unsigned i;
1209 1573994 : int n, max_regno;
1210 1573994 : int *map;
1211 1573994 : lra_live_range_t r, prev_r, next_r;
1212 1573994 : sbitmap_iterator sbi;
1213 1573994 : bool born_p, dead_p, prev_born_p, prev_dead_p;
1214 :
1215 1573994 : auto_sbitmap born (lra_live_max_point);
1216 1573994 : auto_sbitmap dead (lra_live_max_point);
1217 1573994 : bitmap_clear (born);
1218 1573994 : bitmap_clear (dead);
1219 1573994 : max_regno = max_reg_num ();
1220 172719696 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1221 : {
1222 283905928 : for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1223 : {
1224 112760226 : lra_assert (r->start <= r->finish);
1225 112760226 : bitmap_set_bit (born, r->start);
1226 112760226 : bitmap_set_bit (dead, r->finish);
1227 : }
1228 : }
1229 1573994 : auto_sbitmap born_or_dead (lra_live_max_point);
1230 1573994 : bitmap_ior (born_or_dead, born, dead);
1231 1573994 : map = XCNEWVEC (int, lra_live_max_point);
1232 1573994 : n = -1;
1233 1573994 : prev_born_p = prev_dead_p = false;
1234 198096617 : EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1235 : {
1236 194948629 : born_p = bitmap_bit_p (born, i);
1237 194948629 : dead_p = bitmap_bit_p (dead, i);
1238 194948629 : if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1239 179929132 : || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1240 : {
1241 42783490 : map[i] = n;
1242 42783490 : lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1243 : }
1244 : else
1245 : {
1246 152165139 : map[i] = ++n;
1247 152165139 : lra_point_freq[n] = lra_point_freq[i];
1248 : }
1249 194948629 : prev_born_p = born_p;
1250 194948629 : prev_dead_p = dead_p;
1251 : }
1252 1573994 : n++;
1253 1573994 : if (lra_dump_file != NULL)
1254 95 : fprintf (lra_dump_file, "Compressing live ranges: from %d to %d - %d%%\n",
1255 : lra_live_max_point, n,
1256 95 : lra_live_max_point ? 100 * n / lra_live_max_point : 100);
1257 1573994 : if (n < lra_live_max_point)
1258 : {
1259 1338105 : lra_live_max_point = n;
1260 169325166 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1261 : {
1262 167987061 : for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1263 279978529 : r != NULL;
1264 : r = next_r)
1265 : {
1266 111991468 : next_r = r->next;
1267 111991468 : r->start = map[r->start];
1268 111991468 : r->finish = map[r->finish];
1269 111991468 : if (prev_r == NULL || prev_r->start > r->finish + 1)
1270 : {
1271 109836424 : prev_r = r;
1272 109836424 : continue;
1273 : }
1274 2155044 : prev_r->start = r->start;
1275 2155044 : prev_r->next = next_r;
1276 2155044 : lra_live_range_pool.remove (r);
1277 : }
1278 : }
1279 : }
1280 1573994 : free (map);
1281 1573994 : }
1282 :
1283 : /* Print live ranges R to file F. */
1284 : void
1285 2470 : lra_print_live_range_list (FILE *f, lra_live_range_t r)
1286 : {
1287 5466 : for (; r != NULL; r = r->next)
1288 2996 : fprintf (f, " [%d..%d]", r->start, r->finish);
1289 2470 : fprintf (f, "\n");
1290 2470 : }
1291 :
1292 : DEBUG_FUNCTION void
1293 0 : debug (lra_live_range &ref)
1294 : {
1295 0 : lra_print_live_range_list (stderr, &ref);
1296 0 : }
1297 :
1298 : DEBUG_FUNCTION void
1299 0 : debug (lra_live_range *ptr)
1300 : {
1301 0 : if (ptr)
1302 0 : debug (*ptr);
1303 : else
1304 0 : fprintf (stderr, "<nil>\n");
1305 0 : }
1306 :
1307 : /* Print live ranges R to stderr. */
1308 : void
1309 0 : lra_debug_live_range_list (lra_live_range_t r)
1310 : {
1311 0 : lra_print_live_range_list (stderr, r);
1312 0 : }
1313 :
1314 : /* Print live ranges of pseudo REGNO to file F. */
1315 : static void
1316 6022 : print_pseudo_live_ranges (FILE *f, int regno)
1317 : {
1318 6022 : if (lra_reg_info[regno].live_ranges == NULL)
1319 : return;
1320 2470 : fprintf (f, " r%d:", regno);
1321 2470 : lra_print_live_range_list (f, lra_reg_info[regno].live_ranges);
1322 : }
1323 :
1324 : /* Print live ranges of pseudo REGNO to stderr. */
1325 : void
1326 0 : lra_debug_pseudo_live_ranges (int regno)
1327 : {
1328 0 : print_pseudo_live_ranges (stderr, regno);
1329 0 : }
1330 :
1331 : /* Print live ranges of all pseudos to file F. */
1332 : static void
1333 190 : print_live_ranges (FILE *f)
1334 : {
1335 190 : int i, max_regno;
1336 :
1337 190 : max_regno = max_reg_num ();
1338 6402 : for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
1339 6022 : print_pseudo_live_ranges (f, i);
1340 190 : }
1341 :
1342 : /* Print live ranges of all pseudos to stderr. */
1343 : void
1344 0 : lra_debug_live_ranges (void)
1345 : {
1346 0 : print_live_ranges (stderr);
1347 0 : }
1348 :
1349 : /* Compress pseudo live ranges. */
1350 : static void
1351 1573994 : compress_live_ranges (void)
1352 : {
1353 1573994 : remove_some_program_points_and_update_live_ranges ();
1354 1573994 : if (lra_dump_file != NULL)
1355 : {
1356 95 : fprintf (lra_dump_file, "Ranges after the compression:\n");
1357 95 : print_live_ranges (lra_dump_file);
1358 : }
1359 1573994 : }
1360 :
1361 :
1362 :
1363 : /* The number of the current live range pass. */
1364 : int lra_live_range_iter;
1365 :
1366 : /* The function creates live ranges only for memory pseudos (or for
1367 : all ones if ALL_P), set up CONFLICT_HARD_REGS for the pseudos. It
1368 : also does dead insn elimination if DEAD_INSN_P and global live
1369 : analysis only for pseudos and only if the pseudo live info was
1370 : changed on a BB border. Return TRUE if the live info was
1371 : changed. */
1372 : static bool
1373 1779741 : lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1374 : {
1375 1779741 : basic_block bb;
1376 1779741 : int i, hard_regno, max_regno = max_reg_num ();
1377 1779741 : int curr_point;
1378 1779741 : bool bb_live_change_p, have_referenced_pseudos = false;
1379 :
1380 1779741 : timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1381 :
1382 1779741 : complete_info_p = all_p;
1383 1779741 : if (lra_dump_file != NULL)
1384 106 : fprintf (lra_dump_file,
1385 : "\n********** Pseudo live ranges #%d: **********\n\n",
1386 : ++lra_live_range_iter);
1387 1779741 : memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1388 338963004 : for (i = 0; i < max_regno; i++)
1389 : {
1390 337183263 : lra_reg_info[i].live_ranges = NULL;
1391 337183263 : CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1392 337183263 : lra_reg_info[i].preferred_hard_regno1 = -1;
1393 337183263 : lra_reg_info[i].preferred_hard_regno2 = -1;
1394 337183263 : lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1395 337183263 : lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1396 : #ifdef STACK_REGS
1397 337183263 : lra_reg_info[i].no_stack_p = false;
1398 : #endif
1399 : /* The biggest mode is already set but its value might be to
1400 : conservative because of recent transformation. Here in this
1401 : file we recalculate it again as it costs practically
1402 : nothing. */
1403 337183263 : if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1404 172614031 : lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1405 : else
1406 164569232 : lra_reg_info[i].biggest_mode = VOIDmode;
1407 337183263 : if (!HARD_REGISTER_NUM_P (i)
1408 173447091 : && lra_reg_info[i].nrefs != 0)
1409 : {
1410 88996374 : if ((hard_regno = reg_renumber[i]) >= 0)
1411 73456530 : lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1412 : have_referenced_pseudos = true;
1413 : }
1414 : }
1415 1779741 : lra_free_copies ();
1416 :
1417 : /* Under some circumstances, we can have functions without pseudo
1418 : registers. For such functions, lra_live_max_point will be 0,
1419 : see e.g. PR55604, and there's nothing more to do for us here. */
1420 1779741 : if (! have_referenced_pseudos)
1421 : {
1422 205747 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1423 205747 : return false;
1424 : }
1425 :
1426 1573994 : pseudos_live = sparseset_alloc (max_regno);
1427 1573994 : pseudos_live_through_calls = sparseset_alloc (max_regno);
1428 1573994 : pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1429 1573994 : start_living = sparseset_alloc (max_regno);
1430 1573994 : start_dying = sparseset_alloc (max_regno);
1431 1573994 : dead_set = sparseset_alloc (max_regno);
1432 1573994 : unused_set = sparseset_alloc (max_regno);
1433 1573994 : curr_point = 0;
1434 1573994 : unsigned new_length = get_max_uid () * 2;
1435 1573994 : point_freq_vec.truncate (0);
1436 1573994 : point_freq_vec.reserve_exact (new_length);
1437 1573994 : lra_point_freq = point_freq_vec.address ();
1438 1573994 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1439 1573994 : int n = inverted_rev_post_order_compute (cfun, rpo);
1440 1573994 : lra_assert (n == n_basic_blocks_for_fn (cfun));
1441 : bb_live_change_p = false;
1442 36912115 : for (i = 0; i < n; ++i)
1443 : {
1444 35338121 : bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
1445 35338121 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1446 33764127 : == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1447 3147988 : continue;
1448 32190133 : if (process_bb_lives (bb, curr_point, dead_insn_p))
1449 35338121 : bb_live_change_p = true;
1450 : }
1451 1573994 : free (rpo);
1452 1573994 : if (bb_live_change_p)
1453 : {
1454 : /* We need to clear pseudo live info as some pseudos can
1455 : disappear, e.g. pseudos with used equivalences. */
1456 6539797 : FOR_EACH_BB_FN (bb, cfun)
1457 : {
1458 6423610 : bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1459 6423610 : max_regno - FIRST_PSEUDO_REGISTER);
1460 6423610 : bitmap_clear_range (df_get_live_out (bb), FIRST_PSEUDO_REGISTER,
1461 : max_regno - FIRST_PSEUDO_REGISTER);
1462 : }
1463 : /* As we did not change CFG since LRA start we can use
1464 : DF-infrastructure solver to solve live data flow problem. */
1465 10805391 : for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1466 : {
1467 10689204 : if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1468 0 : bitmap_clear_bit (&all_hard_regs_bitmap, i);
1469 : }
1470 116187 : df_simple_dataflow
1471 116187 : (DF_BACKWARD, NULL, live_con_fun_0, live_con_fun_n,
1472 : live_trans_fun, &all_blocks,
1473 : df_get_postorder (DF_BACKWARD), df_get_n_blocks (DF_BACKWARD));
1474 116187 : if (lra_dump_file != NULL)
1475 : {
1476 7 : fprintf (lra_dump_file,
1477 : "Global pseudo live data have been updated:\n");
1478 7 : basic_block bb;
1479 35 : FOR_EACH_BB_FN (bb, cfun)
1480 : {
1481 28 : bb_data_t bb_info = get_bb_data (bb);
1482 28 : bitmap bb_livein = df_get_live_in (bb);
1483 28 : bitmap bb_liveout = df_get_live_out (bb);
1484 :
1485 28 : fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
1486 28 : lra_dump_bitmap_with_title (" gen:",
1487 : &bb_info->gen_pseudos, bb->index);
1488 28 : lra_dump_bitmap_with_title (" killed:",
1489 : &bb_info->killed_pseudos, bb->index);
1490 28 : lra_dump_bitmap_with_title (" livein:", bb_livein, bb->index);
1491 28 : lra_dump_bitmap_with_title (" liveout:", bb_liveout, bb->index);
1492 : }
1493 : }
1494 : }
1495 1573994 : lra_live_max_point = curr_point;
1496 1573994 : if (lra_dump_file != NULL)
1497 95 : print_live_ranges (lra_dump_file);
1498 : /* Clean up. */
1499 1573994 : sparseset_free (unused_set);
1500 1573994 : sparseset_free (dead_set);
1501 1573994 : sparseset_free (start_dying);
1502 1573994 : sparseset_free (start_living);
1503 1573994 : sparseset_free (pseudos_live_through_calls);
1504 1573994 : sparseset_free (pseudos_live_through_setjumps);
1505 1573994 : sparseset_free (pseudos_live);
1506 1573994 : compress_live_ranges ();
1507 1573994 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1508 1573994 : return bb_live_change_p;
1509 : }
1510 :
1511 : /* The main entry function creates live-ranges and other live info
1512 : necessary for the assignment sub-pass. It uses
1513 : lra_creates_live_ranges_1 -- so read comments for the
1514 : function. */
1515 : void
1516 1663554 : lra_create_live_ranges (bool all_p, bool dead_insn_p)
1517 : {
1518 1663554 : if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1519 : return;
1520 116187 : if (lra_dump_file != NULL)
1521 7 : fprintf (lra_dump_file, "Live info was changed -- recalculate it\n");
1522 : /* Live info was changed on a bb border. It means that some info,
1523 : e.g. about conflict regs, calls crossed, and live ranges may be
1524 : wrong. We need this info for allocation. So recalculate it
1525 : again but without removing dead insns which can change live info
1526 : again. Repetitive live range calculations are expensive therefore
1527 : we stop here as we already have correct info although some
1528 : improvement in rare cases could be possible on this sub-pass if
1529 : we do dead insn elimination again (still the improvement may
1530 : happen later). */
1531 116187 : lra_clear_live_ranges ();
1532 116187 : bool res = lra_create_live_ranges_1 (all_p, false);
1533 116187 : lra_assert (! res);
1534 : }
1535 :
1536 : /* Run lra_create_live_ranges if !complete_info_p. Return FALSE iff
1537 : live ranges are known to have remained unchanged. */
1538 :
1539 : bool
1540 0 : lra_complete_live_ranges (void)
1541 : {
1542 0 : if (complete_info_p)
1543 : return false;
1544 :
1545 0 : lra_create_live_ranges (true, true);
1546 0 : return true;
1547 : }
1548 :
1549 : /* Finish all live ranges. */
1550 : void
1551 1764941 : lra_clear_live_ranges (void)
1552 : {
1553 1764941 : int i;
1554 :
1555 327556358 : for (i = 0; i < max_reg_num (); i++)
1556 325791417 : free_live_range_list (lra_reg_info[i].live_ranges);
1557 1764941 : point_freq_vec.release ();
1558 1764941 : }
1559 :
1560 : /* Initialize live ranges data once per function. */
1561 : void
1562 1480947 : lra_live_ranges_init (void)
1563 : {
1564 1480947 : bitmap_initialize (&temp_bitmap, ®_obstack);
1565 1480947 : initiate_live_solver ();
1566 1480947 : }
1567 :
1568 : /* Finish live ranges data once per function. */
1569 : void
1570 1480947 : lra_live_ranges_finish (void)
1571 : {
1572 1480947 : finish_live_solver ();
1573 1480947 : bitmap_clear (&temp_bitmap);
1574 1480947 : lra_live_range_pool.release ();
1575 1480947 : }
|
