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 335716035 : free_live_range_list (lra_live_range_t lr)
105 : {
106 335716035 : lra_live_range_t next;
107 :
108 440634232 : while (lr != NULL)
109 : {
110 104918197 : next = lr->next;
111 104918197 : lra_live_range_pool.remove (lr);
112 104918197 : lr = next;
113 : }
114 335716035 : }
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 115666721 : 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 115666721 : p->regno = regno;
131 115666721 : p->start = start;
132 115666721 : p->finish = finish;
133 115666721 : p->next = next;
134 115666721 : return p;
135 : }
136 :
137 : /* Copy live range R and return the result. */
138 : static lra_live_range_t
139 2164490 : copy_live_range (lra_live_range_t r)
140 : {
141 2164490 : 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 1452645 : lra_copy_live_range_list (lra_live_range_t r)
147 : {
148 1452645 : lra_live_range_t p, first, *chain;
149 :
150 1452645 : first = NULL;
151 3617135 : for (chain = &first; r != NULL; r = r->next)
152 : {
153 2164490 : p = copy_live_range (r);
154 2164490 : *chain = p;
155 2164490 : chain = &p->next;
156 : }
157 1452645 : 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 1452645 : lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
166 : {
167 1452645 : lra_live_range_t first, last;
168 :
169 1452645 : if (r1 == NULL)
170 : return r2;
171 681564 : if (r2 == NULL)
172 : return r1;
173 6006717 : for (first = last = NULL; r1 != NULL && r2 != NULL;)
174 : {
175 5325153 : if (r1->start < r2->start)
176 417359 : std::swap (r1, r2);
177 :
178 5325153 : if (r1->start == r2->finish + 1)
179 : {
180 : /* Joint ranges: merge r1 and r2 into r1. */
181 44400 : r1->start = r2->start;
182 44400 : lra_live_range_t temp = r2;
183 44400 : r2 = r2->next;
184 44400 : lra_live_range_pool.remove (temp);
185 : }
186 : else
187 : {
188 5280753 : gcc_assert (r2->finish + 1 < r1->start);
189 : /* Add r1 to the result. */
190 5280753 : if (first == NULL)
191 : first = last = r1;
192 : else
193 : {
194 4602677 : last->next = r1;
195 4602677 : last = r1;
196 : }
197 5280753 : r1 = r1->next;
198 : }
199 : }
200 681564 : if (r1 != NULL)
201 : {
202 15812 : if (first == NULL)
203 : first = r1;
204 : else
205 12324 : last->next = r1;
206 : }
207 : else
208 : {
209 665752 : lra_assert (r2 != NULL);
210 665752 : if (first == NULL)
211 : first = r2;
212 : else
213 665752 : last->next = r2;
214 : }
215 : return first;
216 : }
217 :
218 : /* Return TRUE if live ranges R1 and R2 intersect. */
219 : bool
220 26294671 : 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 46380761 : while (r1 != NULL && r2 != NULL)
224 : {
225 45696854 : if (r1->start > r2->finish)
226 18373173 : r1 = r1->next;
227 27323681 : else if (r2->start > r1->finish)
228 1712917 : 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 821839556 : sparseset_contains_pseudos_p (sparseset a)
243 : {
244 821839556 : int regno;
245 965995744 : EXECUTE_IF_SET_IN_SPARSESET (a, regno)
246 350194350 : 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 1334552713 : update_pseudo_point (int regno, int point, enum point_type type)
257 : {
258 1334552713 : lra_live_range_t p;
259 :
260 : /* Don't compute points for hard registers. */
261 1334552713 : if (HARD_REGISTER_NUM_P (regno))
262 : return;
263 :
264 1217092910 : if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
265 : {
266 1199482975 : if (type == DEF_POINT)
267 : {
268 516673608 : if (sparseset_bit_p (pseudos_live, regno))
269 : {
270 516673608 : p = lra_reg_info[regno].live_ranges;
271 516673608 : lra_assert (p != NULL);
272 516673608 : p->finish = point;
273 : }
274 : }
275 : else /* USE_POINT */
276 : {
277 682809367 : if (!sparseset_bit_p (pseudos_live, regno)
278 682809367 : && ((p = lra_reg_info[regno].live_ranges) == NULL
279 424969465 : || (p->finish != point && p->finish + 1 != point)))
280 115666721 : lra_reg_info[regno].live_ranges
281 115666721 : = 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 245388037 : make_hard_regno_live (int regno)
293 : {
294 245388037 : lra_assert (HARD_REGISTER_NUM_P (regno));
295 245388037 : if (TEST_HARD_REG_BIT (hard_regs_live, regno)
296 245388037 : || TEST_HARD_REG_BIT (eliminable_regset, regno))
297 : return;
298 134908710 : SET_HARD_REG_BIT (hard_regs_live, regno);
299 134908710 : sparseset_set_bit (start_living, regno);
300 134908710 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
301 78554377 : 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 133187742 : make_hard_regno_dead (int regno)
309 : {
310 133187742 : if (TEST_HARD_REG_BIT (eliminable_regset, regno))
311 : return;
312 :
313 133186838 : lra_assert (HARD_REGISTER_NUM_P (regno));
314 133186838 : unsigned int i;
315 1375586583 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
316 1242399745 : SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
317 :
318 133186838 : if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
319 : return;
320 133186151 : CLEAR_HARD_REG_BIT (hard_regs_live, regno);
321 133186151 : sparseset_set_bit (start_dying, regno);
322 133186151 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
323 : {
324 78554425 : bitmap_clear_bit (bb_gen_pseudos, regno);
325 78554425 : 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 695134195 : mark_pseudo_live (int regno)
332 : {
333 695134195 : lra_assert (!HARD_REGISTER_NUM_P (regno));
334 695134195 : if (sparseset_bit_p (pseudos_live, regno))
335 : return;
336 :
337 527580360 : sparseset_set_bit (pseudos_live, regno);
338 527580360 : sparseset_set_bit (start_living, regno);
339 : }
340 :
341 : /* Mark pseudo REGNO as now being dead and update START_DYING. */
342 : static void
343 527580360 : mark_pseudo_dead (int regno)
344 : {
345 527580360 : lra_assert (!HARD_REGISTER_NUM_P (regno));
346 527580360 : lra_reg_info[regno].conflict_hard_regs |= hard_regs_live;
347 527580360 : if (!sparseset_bit_p (pseudos_live, regno))
348 : return;
349 :
350 527580360 : sparseset_clear_bit (pseudos_live, regno);
351 527580360 : 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 388390415 : mark_regno_live (int regno, machine_mode mode)
358 : {
359 388390415 : int last;
360 :
361 388390415 : if (HARD_REGISTER_NUM_P (regno))
362 : {
363 225826948 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
364 113220979 : make_hard_regno_live (regno);
365 : }
366 : else
367 : {
368 275784446 : mark_pseudo_live (regno);
369 275784446 : bitmap_set_bit (bb_gen_pseudos, regno);
370 : }
371 388390415 : }
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 156716929 : mark_regno_dead (int regno, machine_mode mode)
378 : {
379 156716929 : int last;
380 :
381 156716929 : if (HARD_REGISTER_NUM_P (regno))
382 : {
383 81058633 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
384 40764648 : make_hard_regno_dead (regno);
385 : }
386 : else
387 : {
388 116422944 : mark_pseudo_dead (regno);
389 116422944 : bitmap_clear_bit (bb_gen_pseudos, regno);
390 116422944 : bitmap_set_bit (bb_killed_pseudos, regno);
391 : }
392 156716929 : }
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 77434559 : get_bb_data (basic_block bb)
421 : {
422 77434559 : return &bb_data[(bb)->index];
423 : }
424 :
425 : static inline bb_data_t
426 8571341 : get_bb_data_by_index (int index)
427 : {
428 8571341 : 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 8571341 : live_trans_fun (int bb_index)
442 : {
443 8571341 : basic_block bb = get_bb_data_by_index (bb_index)->bb;
444 8571341 : bitmap bb_liveout = df_get_live_out (bb);
445 8571341 : bitmap bb_livein = df_get_live_in (bb);
446 8571341 : bb_data_t bb_info = get_bb_data (bb);
447 :
448 8571341 : bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
449 8571341 : return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
450 8571341 : &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 379046 : live_con_fun_0 (basic_block bb)
457 : {
458 379046 : bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
459 379046 : }
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 12494358 : live_con_fun_n (edge e)
469 : {
470 12494358 : basic_block bb = e->src;
471 12494358 : basic_block dest = e->dest;
472 12494358 : bitmap bb_liveout = df_get_live_out (bb);
473 12494358 : bitmap dest_livein = df_get_live_in (dest);
474 :
475 12494358 : return bitmap_ior_and_compl_into (bb_liveout,
476 12494358 : 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 1515121 : initiate_live_solver (void)
486 : {
487 1515121 : bitmap_initialize (&all_hard_regs_bitmap, ®_obstack);
488 1515121 : bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
489 1515121 : bb_data = XNEWVEC (class bb_data_pseudos, last_basic_block_for_fn (cfun));
490 1515121 : bitmap_initialize (&all_blocks, ®_obstack);
491 :
492 1515121 : basic_block bb;
493 19378627 : FOR_ALL_BB_FN (bb, cfun)
494 : {
495 17863506 : bb_data_t bb_info = get_bb_data (bb);
496 17863506 : bb_info->bb = bb;
497 17863506 : bitmap_initialize (&bb_info->killed_pseudos, ®_obstack);
498 17863506 : bitmap_initialize (&bb_info->gen_pseudos, ®_obstack);
499 17863506 : bitmap_set_bit (&all_blocks, bb->index);
500 : }
501 1515121 : }
502 :
503 : /* Free all data needed for global pseudo live analysis. */
504 : static void
505 1515121 : finish_live_solver (void)
506 : {
507 1515121 : basic_block bb;
508 :
509 1515121 : bitmap_clear (&all_blocks);
510 19378627 : FOR_ALL_BB_FN (bb, cfun)
511 : {
512 17863506 : bb_data_t bb_info = get_bb_data (bb);
513 17863506 : bitmap_clear (&bb_info->killed_pseudos);
514 17863506 : bitmap_clear (&bb_info->gen_pseudos);
515 : }
516 1515121 : free (bb_data);
517 1515121 : bitmap_clear (&all_hard_regs_bitmap);
518 1515121 : }
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 232754860 : next_program_point (int &point, int freq)
539 : {
540 232754860 : point_freq_vec.safe_push (freq);
541 232754860 : lra_point_freq = point_freq_vec.address ();
542 232754860 : point++;
543 232754860 : }
544 :
545 : /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
546 : void
547 16389359 : lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
548 : int hard_regno, int profit)
549 : {
550 16389359 : lra_assert (regno >= lra_constraint_new_regno_start);
551 16389359 : if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
552 2996823 : lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
553 13392536 : else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
554 90000 : lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
555 13302536 : else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
556 : {
557 10497073 : lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
558 10497073 : lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
559 : }
560 2805463 : else if (lra_reg_info[regno].preferred_hard_regno2 < 0
561 84343 : || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
562 : {
563 2753199 : lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
564 2753199 : lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
565 : }
566 : else
567 : return;
568 : /* Keep the 1st hard regno as more profitable. */
569 16337095 : if (lra_reg_info[regno].preferred_hard_regno1 >= 0
570 16337095 : && lra_reg_info[regno].preferred_hard_regno2 >= 0
571 2929414 : && (lra_reg_info[regno].preferred_hard_regno_profit2
572 2929414 : > lra_reg_info[regno].preferred_hard_regno_profit1))
573 : {
574 115013 : std::swap (lra_reg_info[regno].preferred_hard_regno1,
575 : lra_reg_info[regno].preferred_hard_regno2);
576 115013 : std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
577 : lra_reg_info[regno].preferred_hard_regno_profit2);
578 : }
579 16337095 : 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 481116699 : check_pseudos_live_through_calls (int regno, const function_abi &abi)
601 : {
602 481116699 : if (! sparseset_bit_p (pseudos_live_through_calls, regno))
603 : return;
604 :
605 98562303 : machine_mode mode = PSEUDO_REGNO_MODE (regno);
606 :
607 98562303 : sparseset_clear_bit (pseudos_live_through_calls, regno);
608 98562303 : lra_reg_info[regno].conflict_hard_regs |= abi.mode_clobbers (mode);
609 98562303 : if (! sparseset_bit_p (pseudos_live_through_setjumps, regno))
610 : return;
611 7353 : 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 7353 : 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 399990968 : reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
622 : {
623 399990968 : return (n_alt == LRA_UNKNOWN_ALT
624 399990968 : ? reg->early_clobber_alts != 0
625 : : (n_alt != LRA_NON_CLOBBERED_ALT
626 382279228 : && 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 161591070 : clear_sparseset_regnos (sparseset set, int regno, enum machine_mode mode)
632 : {
633 161591070 : if (regno >= FIRST_PSEUDO_REGISTER)
634 : {
635 89368175 : sparseset_clear_bit (set, regno);
636 89368175 : return;
637 : }
638 144715843 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
639 72492948 : 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 164055412 : regnos_in_sparseset_p (sparseset set, int regno, enum machine_mode mode)
646 : {
647 164055412 : if (regno >= FIRST_PSEUDO_REGISTER)
648 91722241 : return sparseset_bit_p (set, regno);
649 144826119 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
650 72603224 : 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 33136178 : process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
665 : {
666 33136178 : int i, regno, freq;
667 33136178 : unsigned int j;
668 33136178 : bitmap_iterator bi;
669 33136178 : bitmap reg_live_out;
670 33136178 : unsigned int px;
671 33136178 : rtx_insn *next;
672 33136178 : rtx link, *link_loc;
673 33136178 : bool need_curr_point_incr;
674 : /* Only has a meaningful value once we've seen a call. */
675 33136178 : function_abi last_call_abi = default_function_abi;
676 :
677 33136178 : reg_live_out = df_get_live_out (bb);
678 33136178 : sparseset_clear (pseudos_live);
679 33136178 : sparseset_clear (pseudos_live_through_calls);
680 33136178 : sparseset_clear (pseudos_live_through_setjumps);
681 66272356 : REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
682 33136178 : hard_regs_live &= ~eliminable_regset;
683 452485927 : EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
684 : {
685 419349749 : update_pseudo_point (j, curr_point, USE_POINT);
686 419349749 : mark_pseudo_live (j);
687 : }
688 :
689 33136178 : bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
690 33136178 : bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
691 33136178 : bitmap_clear (bb_gen_pseudos);
692 33136178 : bitmap_clear (bb_killed_pseudos);
693 33136178 : freq = REG_FREQ_FROM_BB (bb);
694 :
695 33136178 : 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 929338956 : FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
708 : {
709 448101389 : bool call_p;
710 448101389 : int n_alt, dst_regno, src_regno;
711 448101389 : rtx set;
712 448101389 : struct lra_insn_reg *reg;
713 :
714 448101389 : if (!NONDEBUG_INSN_P (curr_insn))
715 219827019 : continue;
716 :
717 228274370 : curr_id = lra_get_insn_recog_data (curr_insn);
718 228274370 : curr_static_id = curr_id->insn_static_data;
719 228274370 : n_alt = curr_id->used_insn_alternative;
720 228274370 : 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 228274370 : set = single_set (curr_insn);
725 :
726 228274370 : if (dead_insn_p && set != NULL_RTX
727 175051858 : && REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
728 91058824 : && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
729 90831157 : && ! 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 310092772 : && (pic_offset_table_rtx == NULL_RTX
733 9212536 : || pic_offset_table_rtx != SET_DEST (set)))
734 : {
735 81752379 : bool remove_p = true;
736 :
737 82344117 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
738 82292421 : if (reg->type != OP_IN
739 82292421 : && (reg->regno < FIRST_PSEUDO_REGISTER
740 81752506 : ? TEST_HARD_REG_BIT (hard_regs_live, reg->regno)
741 81752506 : : sparseset_bit_p (pseudos_live, reg->regno)))
742 : {
743 : remove_p = false;
744 : break;
745 : }
746 83079282 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
747 16345940 : if (reg->type != OP_IN)
748 : {
749 : remove_p = false;
750 : break;
751 : }
752 :
753 81752379 : if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
754 : {
755 47132 : dst_regno = REGNO (SET_DEST (set));
756 47132 : if (lra_dump_file != NULL)
757 0 : fprintf (lra_dump_file, " Deleting dead insn %u\n",
758 0 : INSN_UID (curr_insn));
759 47132 : lra_set_insn_deleted (curr_insn);
760 47132 : if (lra_reg_info[dst_regno].nrefs == 0)
761 : {
762 : /* There might be some debug insns with the pseudo. */
763 6841 : unsigned int uid;
764 6841 : rtx_insn *insn;
765 :
766 6841 : bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
767 7096 : EXECUTE_IF_SET_IN_BITMAP (&temp_bitmap, 0, uid, bi)
768 : {
769 255 : insn = lra_insn_recog_data[uid]->insn;
770 255 : lra_substitute_pseudo_within_insn (insn, dst_regno,
771 : SET_SRC (set), true);
772 255 : lra_update_insn_regno_info (insn);
773 : }
774 : }
775 47132 : continue;
776 47132 : }
777 : }
778 :
779 : /* Update max ref width and hard reg usage. */
780 596004355 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
781 : {
782 367777117 : int regno = reg->regno;
783 :
784 367777117 : lra_update_biggest_mode (regno, reg->biggest_mode);
785 367777117 : if (HARD_REGISTER_NUM_P (regno))
786 101409858 : lra_hard_reg_usage[regno] += freq;
787 : }
788 :
789 228227238 : 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 228227238 : rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
795 228227238 : if (ignore_reg != NULL_RTX)
796 : {
797 61541324 : int ignore_regno = REGNO (ignore_reg);
798 61541324 : if (HARD_REGISTER_NUM_P (ignore_regno)
799 61541324 : && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
800 173328 : CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
801 61367996 : else if (!HARD_REGISTER_NUM_P (ignore_regno)
802 61367996 : && sparseset_bit_p (pseudos_live, ignore_regno))
803 12365374 : 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 218106776 : src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
811 311695497 : ? REGNO (SET_SRC (set)) : -1);
812 218106776 : dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
813 162839667 : ? REGNO (SET_DEST (set)) : -1);
814 228227238 : if (complete_info_p
815 226951016 : && 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 289427880 : && (((!HARD_REGISTER_NUM_P (src_regno)
820 54105860 : && (! sparseset_bit_p (pseudos_live, src_regno)
821 10051 : || (!HARD_REGISTER_NUM_P (dst_regno)
822 61200642 : && 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 7094782 : && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
827 : /* It might be 'inheritance pseudo <- reload pseudo'. */
828 10064 : || (src_regno >= lra_constraint_new_regno_start
829 351 : && 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 61190578 : int hard_regno = -1, regno = -1;
836 :
837 61190578 : if (dst_regno >= lra_constraint_new_regno_start
838 16551931 : && 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 6183927 : if (dst_regno != src_regno)
846 6183927 : lra_create_copy (dst_regno, src_regno, freq);
847 : }
848 55006651 : else if (dst_regno >= lra_constraint_new_regno_start)
849 : {
850 10368004 : if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
851 10256272 : hard_regno = reg_renumber[src_regno];
852 : regno = dst_regno;
853 : }
854 44638647 : else if (src_regno >= lra_constraint_new_regno_start)
855 : {
856 11500042 : if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
857 9576579 : hard_regno = reg_renumber[dst_regno];
858 : regno = src_regno;
859 : }
860 61190578 : if (regno >= 0 && hard_regno >= 0)
861 13322582 : lra_setup_reload_pseudo_preferenced_hard_reg
862 13322582 : (regno, hard_regno, freq);
863 : }
864 :
865 228227238 : 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 596004355 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
871 367777117 : if (reg->type != OP_IN)
872 : {
873 157831091 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
874 157831091 : mark_regno_live (reg->regno, reg->biggest_mode);
875 : /* ??? Should be a no-op for unused registers. */
876 157831091 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
877 : }
878 :
879 286881916 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
880 58654678 : if (reg->type != OP_IN)
881 42164393 : make_hard_regno_live (reg->regno);
882 :
883 228227238 : if (curr_id->arg_hard_regs != NULL)
884 32621885 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
885 22718658 : if (!HARD_REGISTER_NUM_P (regno))
886 : /* It is a clobber. */
887 0 : make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
888 :
889 228227238 : sparseset_copy (unused_set, start_living);
890 :
891 228227238 : sparseset_clear (start_dying);
892 :
893 : /* See which defined values die here. */
894 596004355 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
895 367777117 : if (reg->type != OP_IN
896 681933131 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
897 : {
898 156324923 : if (reg->type == OP_OUT)
899 136018271 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
900 156324923 : mark_regno_dead (reg->regno, reg->biggest_mode);
901 : }
902 :
903 286881916 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
904 58654678 : if (reg->type != OP_IN
905 117866530 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
906 17047459 : make_hard_regno_dead (reg->regno);
907 :
908 228227238 : if (curr_id->arg_hard_regs != NULL)
909 32621885 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
910 22718658 : if (!HARD_REGISTER_NUM_P (regno))
911 : /* It is a clobber. */
912 0 : make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
913 :
914 228227238 : if (call_p)
915 : {
916 12617765 : function_abi call_abi = insn_callee_abi (curr_insn);
917 :
918 12617765 : if (last_call_abi != call_abi)
919 7884837 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
920 5416407 : check_pseudos_live_through_calls (j, last_call_abi);
921 :
922 12617765 : last_call_abi = call_abi;
923 :
924 12617765 : sparseset_ior (pseudos_live_through_calls,
925 : pseudos_live_through_calls, pseudos_live);
926 12617765 : if (cfun->has_nonlocal_label
927 12617765 : || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
928 12613559 : && (find_reg_note (curr_insn, REG_SETJMP, NULL_RTX)
929 : != NULL_RTX)))
930 6814 : 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 228227238 : if (sparseset_contains_pseudos_p (unused_set)
936 228227238 : || sparseset_contains_pseudos_p (start_dying))
937 115784286 : 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 228227238 : if (ignore_reg != NULL_RTX)
943 : {
944 12538702 : int ignore_regno = REGNO (ignore_reg);
945 12538702 : if (HARD_REGISTER_NUM_P (ignore_regno))
946 173328 : SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
947 : else
948 12365374 : sparseset_set_bit (pseudos_live, ignore_regno);
949 : }
950 :
951 228227238 : sparseset_clear (start_living);
952 :
953 : /* Mark each used value as live. */
954 596004355 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
955 367777117 : if (reg->type != OP_OUT)
956 : {
957 230417478 : if (reg->type == OP_IN)
958 209946026 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
959 230417478 : mark_regno_live (reg->regno, reg->biggest_mode);
960 230417478 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
961 : }
962 :
963 286881916 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
964 58654678 : if (reg->type != OP_OUT)
965 16986953 : make_hard_regno_live (reg->regno);
966 :
967 228227238 : if (curr_id->arg_hard_regs != NULL)
968 : /* Make argument hard registers live. */
969 32621885 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
970 22718658 : if (HARD_REGISTER_NUM_P (regno))
971 22718658 : make_hard_regno_live (regno);
972 :
973 228227238 : sparseset_and_compl (dead_set, start_living, start_dying);
974 :
975 228227238 : sparseset_clear (start_dying);
976 :
977 : /* Mark early clobber outputs dead. */
978 596004355 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
979 367777117 : if (reg->type != OP_IN
980 526000214 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
981 : {
982 392006 : if (reg->type == OP_OUT)
983 250160 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
984 392006 : 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 392006 : if (reg->type == OP_INOUT)
989 141846 : mark_regno_live (reg->regno, reg->biggest_mode);
990 : }
991 :
992 286881916 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
993 58654678 : if (reg->type != OP_IN
994 125936005 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
995 : {
996 25116934 : 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 50528366 : for (reg2 = curr_static_id->hard_regs; reg2 != NULL; reg2 = reg2->next)
1002 25438417 : if (reg2->type != OP_OUT && reg2->regno == reg->regno)
1003 : break;
1004 25116934 : if (reg2 != NULL)
1005 26985 : continue;
1006 :
1007 : HARD_REG_SET clobbered_regset;
1008 25089949 : CLEAR_HARD_REG_SET (clobbered_regset);
1009 25089949 : SET_HARD_REG_BIT (clobbered_regset, reg->regno);
1010 :
1011 69801233 : for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
1012 31853233 : if (reg2->type != OP_OUT && reg2->regno < FIRST_PSEUDO_REGISTER
1013 53225171 : && ira_hard_reg_set_intersection_p (reg2->regno,
1014 8502519 : reg2->biggest_mode,
1015 : clobbered_regset))
1016 : break;
1017 25089949 : if (reg2 == NULL)
1018 : {
1019 25078581 : make_hard_regno_dead (reg->regno);
1020 : }
1021 : else
1022 : {
1023 140977 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1024 129609 : 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 228227238 : if (sparseset_contains_pseudos_p (dead_set)
1031 228227238 : || sparseset_contains_pseudos_p (start_dying))
1032 90253876 : next_program_point (curr_point, freq);
1033 :
1034 : /* Update notes. */
1035 459547346 : for (link_loc = ®_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1036 : {
1037 231320108 : if (REG_NOTE_KIND (link) != REG_DEAD
1038 95398713 : && REG_NOTE_KIND (link) != REG_UNUSED)
1039 : ;
1040 164055412 : else if (REG_P (XEXP (link, 0)))
1041 : {
1042 164055412 : rtx note_reg = XEXP (link, 0);
1043 164055412 : int note_regno = REGNO (note_reg);
1044 :
1045 166519754 : if ((REG_NOTE_KIND (link) == REG_DEAD
1046 135921395 : && ! regnos_in_sparseset_p (dead_set, note_regno,
1047 135921395 : GET_MODE (note_reg)))
1048 297724918 : || (REG_NOTE_KIND (link) == REG_UNUSED
1049 28134017 : && ! regnos_in_sparseset_p (unused_set, note_regno,
1050 28134017 : GET_MODE (note_reg))))
1051 : {
1052 2464342 : *link_loc = XEXP (link, 1);
1053 2464342 : continue;
1054 : }
1055 161591070 : if (REG_NOTE_KIND (link) == REG_DEAD)
1056 133669506 : clear_sparseset_regnos (dead_set, note_regno,
1057 133669506 : GET_MODE (note_reg));
1058 27921564 : else if (REG_NOTE_KIND (link) == REG_UNUSED)
1059 27921564 : clear_sparseset_regnos (unused_set, note_regno,
1060 27921564 : GET_MODE (note_reg));
1061 : }
1062 228855766 : link_loc = &XEXP (link, 1);
1063 : }
1064 237423993 : EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1065 9196755 : add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1066 456605943 : EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1067 151467 : add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1068 : }
1069 :
1070 33136178 : 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 589624 : for (j = 0; ; ++j)
1076 : {
1077 1768872 : unsigned int regno = EH_RETURN_DATA_REGNO (j);
1078 :
1079 1179248 : if (regno == INVALID_REGNUM)
1080 : break;
1081 :
1082 1179248 : make_hard_regno_live (regno);
1083 1179248 : make_hard_regno_dead (regno);
1084 1179248 : }
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 33136178 : if (bb_has_abnormal_pred (bb))
1092 : {
1093 : HARD_REG_SET clobbers;
1094 :
1095 592928 : CLEAR_HARD_REG_SET (clobbers);
1096 : #ifdef STACK_REGS
1097 1896015 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1098 1303087 : lra_reg_info[px].no_stack_p = true;
1099 5336352 : for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1100 4743424 : 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 592928 : if (!cfun->has_nonlocal_label
1106 592928 : && has_abnormal_call_or_eh_pred_edge_p (bb))
1107 54834195 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1108 54244580 : 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 54701421 : || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1116 589615 : && pic_offset_table_rtx != NULL_RTX
1117 22731 : && !HARD_REGISTER_P (pic_offset_table_rtx))
1118 : #endif
1119 : )
1120 49091302 : SET_HARD_REG_BIT (clobbers, px);
1121 :
1122 592928 : clobbers &= ~hard_regs_live;
1123 55142304 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1124 54549376 : if (TEST_HARD_REG_BIT (clobbers, px))
1125 : {
1126 49117806 : make_hard_regno_live (px);
1127 49117806 : make_hard_regno_dead (px);
1128 : }
1129 : }
1130 :
1131 33136178 : bool live_change_p = false;
1132 : /* Check if bb border live info was changed. */
1133 33136178 : unsigned int live_pseudos_num = 0;
1134 443549401 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1135 : FIRST_PSEUDO_REGISTER, j, bi)
1136 : {
1137 410661445 : live_pseudos_num++;
1138 410661445 : if (! sparseset_bit_p (pseudos_live, j))
1139 : {
1140 248222 : live_change_p = true;
1141 248222 : 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 32887956 : && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1149 : {
1150 189625 : live_change_p = true;
1151 189625 : 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 33136178 : need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1161 :
1162 855451010 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1163 : {
1164 411157416 : update_pseudo_point (i, curr_point, DEF_POINT);
1165 411157416 : mark_pseudo_dead (i);
1166 : }
1167 :
1168 127554602 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1169 : {
1170 116711244 : if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1171 : break;
1172 94418424 : if (sparseset_bit_p (pseudos_live_through_calls, j))
1173 87451723 : check_pseudos_live_through_calls (j, last_call_abi);
1174 : }
1175 :
1176 3081664554 : for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1177 : {
1178 3048528376 : if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1179 3003057157 : continue;
1180 :
1181 45471219 : if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1182 45471219 : 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 33136178 : if (need_curr_point_incr)
1196 26716698 : next_program_point (curr_point, freq);
1197 :
1198 33136178 : 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 1611664 : remove_some_program_points_and_update_live_ranges (void)
1207 : {
1208 1611664 : unsigned i;
1209 1611664 : int n, max_regno;
1210 1611664 : int *map;
1211 1611664 : lra_live_range_t r, prev_r, next_r;
1212 1611664 : sbitmap_iterator sbi;
1213 1611664 : bool born_p, dead_p, prev_born_p, prev_dead_p;
1214 :
1215 1611664 : auto_sbitmap born (lra_live_max_point);
1216 1611664 : auto_sbitmap dead (lra_live_max_point);
1217 1611664 : bitmap_clear (born);
1218 1611664 : bitmap_clear (dead);
1219 1611664 : max_regno = max_reg_num ();
1220 179491199 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1221 : {
1222 293546256 : for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1223 : {
1224 115666721 : lra_assert (r->start <= r->finish);
1225 115666721 : bitmap_set_bit (born, r->start);
1226 115666721 : bitmap_set_bit (dead, r->finish);
1227 : }
1228 : }
1229 1611664 : auto_sbitmap born_or_dead (lra_live_max_point);
1230 1611664 : bitmap_ior (born_or_dead, born, dead);
1231 1611664 : map = XCNEWVEC (int, lra_live_max_point);
1232 1611664 : n = -1;
1233 1611664 : prev_born_p = prev_dead_p = false;
1234 203670308 : EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1235 : {
1236 200446981 : born_p = bitmap_bit_p (born, i);
1237 200446981 : dead_p = bitmap_bit_p (dead, i);
1238 200446981 : if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1239 185014692 : || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1240 : {
1241 44064140 : map[i] = n;
1242 44064140 : lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1243 : }
1244 : else
1245 : {
1246 156382841 : map[i] = ++n;
1247 156382841 : lra_point_freq[n] = lra_point_freq[i];
1248 : }
1249 200446981 : prev_born_p = born_p;
1250 200446981 : prev_dead_p = dead_p;
1251 : }
1252 1611664 : n++;
1253 1611664 : 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 1611664 : if (n < lra_live_max_point)
1258 : {
1259 1366256 : lra_live_max_point = n;
1260 175972002 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1261 : {
1262 174605746 : for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1263 289473877 : r != NULL;
1264 114868131 : r = next_r)
1265 : {
1266 114868131 : next_r = r->next;
1267 114868131 : r->start = map[r->start];
1268 114868131 : r->finish = map[r->finish];
1269 114868131 : if (prev_r == NULL || prev_r->start > r->finish + 1)
1270 : {
1271 112632322 : prev_r = r;
1272 112632322 : continue;
1273 : }
1274 2235809 : prev_r->start = r->start;
1275 2235809 : prev_r->next = next_r;
1276 2235809 : lra_live_range_pool.remove (r);
1277 : }
1278 : }
1279 : }
1280 1611664 : free (map);
1281 1611664 : }
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 1611664 : compress_live_ranges (void)
1352 : {
1353 1611664 : remove_some_program_points_and_update_live_ranges ();
1354 1611664 : 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 1611664 : }
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 1818503 : lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1374 : {
1375 1818503 : basic_block bb;
1376 1818503 : int i, hard_regno, max_regno = max_reg_num ();
1377 1818503 : int curr_point;
1378 1818503 : bool bb_live_change_p, have_referenced_pseudos = false;
1379 :
1380 1818503 : timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1381 :
1382 1818503 : complete_info_p = all_p;
1383 1818503 : 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 1818503 : memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1388 349379071 : for (i = 0; i < max_regno; i++)
1389 : {
1390 347560568 : lra_reg_info[i].live_ranges = NULL;
1391 347560568 : CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1392 347560568 : lra_reg_info[i].preferred_hard_regno1 = -1;
1393 347560568 : lra_reg_info[i].preferred_hard_regno2 = -1;
1394 347560568 : lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1395 347560568 : lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1396 : #ifdef STACK_REGS
1397 347560568 : 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 347560568 : if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1404 179363710 : lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1405 : else
1406 168196858 : lra_reg_info[i].biggest_mode = VOIDmode;
1407 347560568 : if (!HARD_REGISTER_NUM_P (i)
1408 180258292 : && lra_reg_info[i].nrefs != 0)
1409 : {
1410 92097259 : if ((hard_regno = reg_renumber[i]) >= 0)
1411 75868068 : lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1412 : have_referenced_pseudos = true;
1413 : }
1414 : }
1415 1818503 : 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 1818503 : if (! have_referenced_pseudos)
1421 : {
1422 206839 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1423 206839 : return false;
1424 : }
1425 :
1426 1611664 : pseudos_live = sparseset_alloc (max_regno);
1427 1611664 : pseudos_live_through_calls = sparseset_alloc (max_regno);
1428 1611664 : pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1429 1611664 : start_living = sparseset_alloc (max_regno);
1430 1611664 : start_dying = sparseset_alloc (max_regno);
1431 1611664 : dead_set = sparseset_alloc (max_regno);
1432 1611664 : unused_set = sparseset_alloc (max_regno);
1433 1611664 : curr_point = 0;
1434 1611664 : unsigned new_length = get_max_uid () * 2;
1435 1611664 : point_freq_vec.truncate (0);
1436 1611664 : point_freq_vec.reserve_exact (new_length);
1437 1611664 : lra_point_freq = point_freq_vec.address ();
1438 1611664 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1439 1611664 : int n = inverted_rev_post_order_compute (cfun, rpo);
1440 1611664 : lra_assert (n == n_basic_blocks_for_fn (cfun));
1441 : bb_live_change_p = false;
1442 37971170 : for (i = 0; i < n; ++i)
1443 : {
1444 36359506 : bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
1445 36359506 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1446 34747842 : == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1447 3223328 : continue;
1448 33136178 : if (process_bb_lives (bb, curr_point, dead_insn_p))
1449 36359506 : bb_live_change_p = true;
1450 : }
1451 1611664 : free (rpo);
1452 1611664 : 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 6801043 : FOR_EACH_BB_FN (bb, cfun)
1457 : {
1458 6681642 : bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1459 6681642 : max_regno - FIRST_PSEUDO_REGISTER);
1460 6681642 : 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 11104293 : for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1466 : {
1467 10984892 : if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1468 0 : bitmap_clear_bit (&all_hard_regs_bitmap, i);
1469 : }
1470 119401 : df_simple_dataflow
1471 119401 : (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 119401 : 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 1611664 : lra_live_max_point = curr_point;
1496 1611664 : if (lra_dump_file != NULL)
1497 95 : print_live_ranges (lra_dump_file);
1498 : /* Clean up. */
1499 1611664 : sparseset_free (unused_set);
1500 1611664 : sparseset_free (dead_set);
1501 1611664 : sparseset_free (start_dying);
1502 1611664 : sparseset_free (start_living);
1503 1611664 : sparseset_free (pseudos_live_through_calls);
1504 1611664 : sparseset_free (pseudos_live_through_setjumps);
1505 1611664 : sparseset_free (pseudos_live);
1506 1611664 : compress_live_ranges ();
1507 1611664 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1508 1611664 : 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 1699102 : lra_create_live_ranges (bool all_p, bool dead_insn_p)
1517 : {
1518 1699102 : if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1519 : return;
1520 119401 : 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 119401 : lra_clear_live_ranges ();
1532 119401 : bool res = lra_create_live_ranges_1 (all_p, false);
1533 119401 : 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 1803655 : lra_clear_live_ranges (void)
1552 : {
1553 1803655 : int i;
1554 :
1555 337519690 : for (i = 0; i < max_reg_num (); i++)
1556 335716035 : free_live_range_list (lra_reg_info[i].live_ranges);
1557 1803655 : point_freq_vec.release ();
1558 1803655 : }
1559 :
1560 : /* Initialize live ranges data once per function. */
1561 : void
1562 1515121 : lra_live_ranges_init (void)
1563 : {
1564 1515121 : bitmap_initialize (&temp_bitmap, ®_obstack);
1565 1515121 : initiate_live_solver ();
1566 1515121 : }
1567 :
1568 : /* Finish live ranges data once per function. */
1569 : void
1570 1515121 : lra_live_ranges_finish (void)
1571 : {
1572 1515121 : finish_live_solver ();
1573 1515121 : bitmap_clear (&temp_bitmap);
1574 1515121 : lra_live_range_pool.release ();
1575 1515121 : }
|
