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 323866249 : free_live_range_list (lra_live_range_t lr)
105 : {
106 323866249 : lra_live_range_t next;
107 :
108 425754369 : while (lr != NULL)
109 : {
110 101888120 : next = lr->next;
111 101888120 : lra_live_range_pool.remove (lr);
112 101888120 : lr = next;
113 : }
114 323866249 : }
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 112331805 : 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 112331805 : p->regno = regno;
131 112331805 : p->start = start;
132 112331805 : p->finish = finish;
133 112331805 : p->next = next;
134 112331805 : return p;
135 : }
136 :
137 : /* Copy live range R and return the result. */
138 : static lra_live_range_t
139 2120167 : copy_live_range (lra_live_range_t r)
140 : {
141 2120167 : 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 1421708 : lra_copy_live_range_list (lra_live_range_t r)
147 : {
148 1421708 : lra_live_range_t p, first, *chain;
149 :
150 1421708 : first = NULL;
151 3541875 : for (chain = &first; r != NULL; r = r->next)
152 : {
153 2120167 : p = copy_live_range (r);
154 2120167 : *chain = p;
155 2120167 : chain = &p->next;
156 : }
157 1421708 : 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 1421708 : lra_merge_live_ranges (lra_live_range_t r1, lra_live_range_t r2)
166 : {
167 1421708 : lra_live_range_t first, last;
168 :
169 1421708 : if (r1 == NULL)
170 : return r2;
171 665244 : if (r2 == NULL)
172 : return r1;
173 5849398 : for (first = last = NULL; r1 != NULL && r2 != NULL;)
174 : {
175 5184154 : if (r1->start < r2->start)
176 411370 : std::swap (r1, r2);
177 :
178 5184154 : if (r1->start == r2->finish + 1)
179 : {
180 : /* Joint ranges: merge r1 and r2 into r1. */
181 41658 : r1->start = r2->start;
182 41658 : lra_live_range_t temp = r2;
183 41658 : r2 = r2->next;
184 41658 : lra_live_range_pool.remove (temp);
185 : }
186 : else
187 : {
188 5142496 : gcc_assert (r2->finish + 1 < r1->start);
189 : /* Add r1 to the result. */
190 5142496 : if (first == NULL)
191 : first = last = r1;
192 : else
193 : {
194 4480402 : last->next = r1;
195 4480402 : last = r1;
196 : }
197 5142496 : r1 = r1->next;
198 : }
199 : }
200 665244 : if (r1 != NULL)
201 : {
202 13457 : if (first == NULL)
203 : first = r1;
204 : else
205 10307 : last->next = r1;
206 : }
207 : else
208 : {
209 651787 : lra_assert (r2 != NULL);
210 651787 : if (first == NULL)
211 : first = r2;
212 : else
213 651787 : last->next = r2;
214 : }
215 : return first;
216 : }
217 :
218 : /* Return TRUE if live ranges R1 and R2 intersect. */
219 : bool
220 25912653 : 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 45003957 : while (r1 != NULL && r2 != NULL)
224 : {
225 44336504 : if (r1->start > r2->finish)
226 17481891 : r1 = r1->next;
227 26854613 : else if (r2->start > r1->finish)
228 1609413 : 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 793765790 : sparseset_contains_pseudos_p (sparseset a)
243 : {
244 793765790 : int regno;
245 934300630 : EXECUTE_IF_SET_IN_SPARSESET (a, regno)
246 339240983 : 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 1293507464 : update_pseudo_point (int regno, int point, enum point_type type)
257 : {
258 1293507464 : lra_live_range_t p;
259 :
260 : /* Don't compute points for hard registers. */
261 1293507464 : if (HARD_REGISTER_NUM_P (regno))
262 : return;
263 :
264 1177606440 : if (complete_info_p || lra_get_regno_hard_regno (regno) < 0)
265 : {
266 1165937555 : if (type == DEF_POINT)
267 : {
268 502326983 : if (sparseset_bit_p (pseudos_live, regno))
269 : {
270 502326983 : p = lra_reg_info[regno].live_ranges;
271 502326983 : lra_assert (p != NULL);
272 502326983 : p->finish = point;
273 : }
274 : }
275 : else /* USE_POINT */
276 : {
277 663610572 : if (!sparseset_bit_p (pseudos_live, regno)
278 663610572 : && ((p = lra_reg_info[regno].live_ranges) == NULL
279 413973190 : || (p->finish != point && p->finish + 1 != point)))
280 112331805 : lra_reg_info[regno].live_ranges
281 112331805 : = 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 234755874 : make_hard_regno_live (int regno)
293 : {
294 234755874 : lra_assert (HARD_REGISTER_NUM_P (regno));
295 234755874 : if (TEST_HARD_REG_BIT (hard_regs_live, regno)
296 234755874 : || TEST_HARD_REG_BIT (eliminable_regset, regno))
297 : return;
298 128472003 : SET_HARD_REG_BIT (hard_regs_live, regno);
299 128472003 : sparseset_set_bit (start_living, regno);
300 128472003 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
301 74947299 : 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 126786091 : make_hard_regno_dead (int regno)
309 : {
310 126786091 : if (TEST_HARD_REG_BIT (eliminable_regset, regno))
311 : return;
312 :
313 126785188 : lra_assert (HARD_REGISTER_NUM_P (regno));
314 126785188 : unsigned int i;
315 1311920543 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
316 1185135355 : SET_HARD_REG_BIT (lra_reg_info[i].conflict_hard_regs, regno);
317 :
318 126785188 : if (! TEST_HARD_REG_BIT (hard_regs_live, regno))
319 : return;
320 126784444 : CLEAR_HARD_REG_BIT (hard_regs_live, regno);
321 126784444 : sparseset_set_bit (start_dying, regno);
322 126784444 : if (fixed_regs[regno] || TEST_HARD_REG_BIT (hard_regs_spilled_into, regno))
323 : {
324 74947078 : bitmap_clear_bit (bb_gen_pseudos, regno);
325 74947078 : 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 674144910 : mark_pseudo_live (int regno)
332 : {
333 674144910 : lra_assert (!HARD_REGISTER_NUM_P (regno));
334 674144910 : if (sparseset_bit_p (pseudos_live, regno))
335 : return;
336 :
337 511950868 : sparseset_set_bit (pseudos_live, regno);
338 511950868 : sparseset_set_bit (start_living, regno);
339 : }
340 :
341 : /* Mark pseudo REGNO as now being dead and update START_DYING. */
342 : static void
343 511950868 : mark_pseudo_dead (int regno)
344 : {
345 511950868 : lra_assert (!HARD_REGISTER_NUM_P (regno));
346 511950868 : lra_reg_info[regno].conflict_hard_regs |= hard_regs_live;
347 511950868 : if (!sparseset_bit_p (pseudos_live, regno))
348 : return;
349 :
350 511950868 : sparseset_clear_bit (pseudos_live, regno);
351 511950868 : 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 374706369 : mark_regno_live (int regno, machine_mode mode)
358 : {
359 374706369 : int last;
360 :
361 374706369 : if (HARD_REGISTER_NUM_P (regno))
362 : {
363 217320894 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
364 108963051 : make_hard_regno_live (regno);
365 : }
366 : else
367 : {
368 266348526 : mark_pseudo_live (regno);
369 266348526 : bitmap_set_bit (bb_gen_pseudos, regno);
370 : }
371 374706369 : }
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 150790544 : mark_regno_dead (int regno, machine_mode mode)
378 : {
379 150790544 : int last;
380 :
381 150790544 : if (HARD_REGISTER_NUM_P (regno))
382 : {
383 77736180 : for (last = end_hard_regno (mode, regno); regno < last; regno++)
384 39099592 : make_hard_regno_dead (regno);
385 : }
386 : else
387 : {
388 112153956 : mark_pseudo_dead (regno);
389 112153956 : bitmap_clear_bit (bb_gen_pseudos, regno);
390 112153956 : bitmap_set_bit (bb_killed_pseudos, regno);
391 : }
392 150790544 : }
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 75374981 : get_bb_data (basic_block bb)
421 : {
422 75374981 : return &bb_data[(bb)->index];
423 : }
424 :
425 : static inline bb_data_t
426 8206095 : get_bb_data_by_index (int index)
427 : {
428 8206095 : 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 8206095 : live_trans_fun (int bb_index)
442 : {
443 8206095 : basic_block bb = get_bb_data_by_index (bb_index)->bb;
444 8206095 : bitmap bb_liveout = df_get_live_out (bb);
445 8206095 : bitmap bb_livein = df_get_live_in (bb);
446 8206095 : bb_data_t bb_info = get_bb_data (bb);
447 :
448 8206095 : bitmap_and_compl (&temp_bitmap, bb_liveout, &all_hard_regs_bitmap);
449 8206095 : return bitmap_ior_and_compl (bb_livein, &bb_info->gen_pseudos,
450 8206095 : &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 359179 : live_con_fun_0 (basic_block bb)
457 : {
458 359179 : bitmap_and_into (df_get_live_out (bb), &all_hard_regs_bitmap);
459 359179 : }
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 11968666 : live_con_fun_n (edge e)
469 : {
470 11968666 : basic_block bb = e->src;
471 11968666 : basic_block dest = e->dest;
472 11968666 : bitmap bb_liveout = df_get_live_out (bb);
473 11968666 : bitmap dest_livein = df_get_live_in (dest);
474 :
475 11968666 : return bitmap_ior_and_compl_into (bb_liveout,
476 11968666 : 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 1471362 : initiate_live_solver (void)
486 : {
487 1471362 : bitmap_initialize (&all_hard_regs_bitmap, ®_obstack);
488 1471362 : bitmap_set_range (&all_hard_regs_bitmap, 0, FIRST_PSEUDO_REGISTER);
489 1471362 : bb_data = XNEWVEC (class bb_data_pseudos, last_basic_block_for_fn (cfun));
490 1471362 : bitmap_initialize (&all_blocks, ®_obstack);
491 :
492 1471362 : basic_block bb;
493 18926800 : FOR_ALL_BB_FN (bb, cfun)
494 : {
495 17455438 : bb_data_t bb_info = get_bb_data (bb);
496 17455438 : bb_info->bb = bb;
497 17455438 : bitmap_initialize (&bb_info->killed_pseudos, ®_obstack);
498 17455438 : bitmap_initialize (&bb_info->gen_pseudos, ®_obstack);
499 17455438 : bitmap_set_bit (&all_blocks, bb->index);
500 : }
501 1471362 : }
502 :
503 : /* Free all data needed for global pseudo live analysis. */
504 : static void
505 1471362 : finish_live_solver (void)
506 : {
507 1471362 : basic_block bb;
508 :
509 1471362 : bitmap_clear (&all_blocks);
510 18926800 : FOR_ALL_BB_FN (bb, cfun)
511 : {
512 17455438 : bb_data_t bb_info = get_bb_data (bb);
513 17455438 : bitmap_clear (&bb_info->killed_pseudos);
514 17455438 : bitmap_clear (&bb_info->gen_pseudos);
515 : }
516 1471362 : free (bb_data);
517 1471362 : bitmap_clear (&all_hard_regs_bitmap);
518 1471362 : }
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 224743603 : next_program_point (int &point, int freq)
539 : {
540 224743603 : point_freq_vec.safe_push (freq);
541 224743603 : lra_point_freq = point_freq_vec.address ();
542 224743603 : point++;
543 224743603 : }
544 :
545 : /* Update the preference of HARD_REGNO for pseudo REGNO by PROFIT. */
546 : void
547 15443171 : lra_setup_reload_pseudo_preferenced_hard_reg (int regno,
548 : int hard_regno, int profit)
549 : {
550 15443171 : lra_assert (regno >= lra_constraint_new_regno_start);
551 15443171 : if (lra_reg_info[regno].preferred_hard_regno1 == hard_regno)
552 2886216 : lra_reg_info[regno].preferred_hard_regno_profit1 += profit;
553 12556955 : else if (lra_reg_info[regno].preferred_hard_regno2 == hard_regno)
554 75788 : lra_reg_info[regno].preferred_hard_regno_profit2 += profit;
555 12481167 : else if (lra_reg_info[regno].preferred_hard_regno1 < 0)
556 : {
557 9865455 : lra_reg_info[regno].preferred_hard_regno1 = hard_regno;
558 9865455 : lra_reg_info[regno].preferred_hard_regno_profit1 = profit;
559 : }
560 2615712 : else if (lra_reg_info[regno].preferred_hard_regno2 < 0
561 69213 : || profit > lra_reg_info[regno].preferred_hard_regno_profit2)
562 : {
563 2572665 : lra_reg_info[regno].preferred_hard_regno2 = hard_regno;
564 2572665 : lra_reg_info[regno].preferred_hard_regno_profit2 = profit;
565 : }
566 : else
567 : return;
568 : /* Keep the 1st hard regno as more profitable. */
569 15400124 : if (lra_reg_info[regno].preferred_hard_regno1 >= 0
570 15400124 : && lra_reg_info[regno].preferred_hard_regno2 >= 0
571 2724527 : && (lra_reg_info[regno].preferred_hard_regno_profit2
572 2724527 : > lra_reg_info[regno].preferred_hard_regno_profit1))
573 : {
574 100561 : std::swap (lra_reg_info[regno].preferred_hard_regno1,
575 : lra_reg_info[regno].preferred_hard_regno2);
576 100561 : std::swap (lra_reg_info[regno].preferred_hard_regno_profit1,
577 : lra_reg_info[regno].preferred_hard_regno_profit2);
578 : }
579 15400124 : 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 464464139 : check_pseudos_live_through_calls (int regno, const function_abi &abi)
601 : {
602 464464139 : if (! sparseset_bit_p (pseudos_live_through_calls, regno))
603 : return;
604 :
605 95570647 : machine_mode mode = PSEUDO_REGNO_MODE (regno);
606 :
607 95570647 : sparseset_clear_bit (pseudos_live_through_calls, regno);
608 95570647 : lra_reg_info[regno].conflict_hard_regs |= abi.mode_clobbers (mode);
609 95570647 : 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 385436304 : reg_early_clobber_p (const struct lra_insn_reg *reg, int n_alt)
622 : {
623 385436304 : return (n_alt == LRA_UNKNOWN_ALT
624 385436304 : ? reg->early_clobber_alts != 0
625 : : (n_alt != LRA_NON_CLOBBERED_ALT
626 368357996 : && 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 154697989 : clear_sparseset_regnos (sparseset set, int regno, enum machine_mode mode)
632 : {
633 154697989 : if (regno >= FIRST_PSEUDO_REGISTER)
634 : {
635 85281604 : sparseset_clear_bit (dead_set, regno);
636 85281604 : return;
637 : }
638 139079927 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
639 69663542 : 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 158084890 : regnos_in_sparseset_p (sparseset set, int regno, enum machine_mode mode)
646 : {
647 158084890 : if (regno >= FIRST_PSEUDO_REGISTER)
648 88460541 : return sparseset_bit_p (dead_set, regno);
649 139287891 : for (int last = end_hard_regno (mode, regno); regno < last; regno++)
650 69871506 : 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 32257982 : process_bb_lives (basic_block bb, int &curr_point, bool dead_insn_p)
665 : {
666 32257982 : int i, regno, freq;
667 32257982 : unsigned int j;
668 32257982 : bitmap_iterator bi;
669 32257982 : bitmap reg_live_out;
670 32257982 : unsigned int px;
671 32257982 : rtx_insn *next;
672 32257982 : rtx link, *link_loc;
673 32257982 : bool need_curr_point_incr;
674 : /* Only has a meaningful value once we've seen a call. */
675 32257982 : function_abi last_call_abi = default_function_abi;
676 :
677 32257982 : reg_live_out = df_get_live_out (bb);
678 32257982 : sparseset_clear (pseudos_live);
679 32257982 : sparseset_clear (pseudos_live_through_calls);
680 32257982 : sparseset_clear (pseudos_live_through_setjumps);
681 64515964 : REG_SET_TO_HARD_REG_SET (hard_regs_live, reg_live_out);
682 32257982 : hard_regs_live &= ~eliminable_regset;
683 440054366 : EXECUTE_IF_SET_IN_BITMAP (reg_live_out, FIRST_PSEUDO_REGISTER, j, bi)
684 : {
685 407796384 : update_pseudo_point (j, curr_point, USE_POINT);
686 407796384 : mark_pseudo_live (j);
687 : }
688 :
689 32257982 : bb_gen_pseudos = &get_bb_data (bb)->gen_pseudos;
690 32257982 : bb_killed_pseudos = &get_bb_data (bb)->killed_pseudos;
691 32257982 : bitmap_clear (bb_gen_pseudos);
692 32257982 : bitmap_clear (bb_killed_pseudos);
693 32257982 : freq = REG_FREQ_FROM_BB (bb);
694 :
695 32257982 : 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 908817816 : FOR_BB_INSNS_REVERSE_SAFE (bb, curr_insn, next)
708 : {
709 422150926 : bool call_p;
710 422150926 : int n_alt, dst_regno, src_regno;
711 422150926 : rtx set;
712 422150926 : struct lra_insn_reg *reg;
713 :
714 422150926 : if (!NONDEBUG_INSN_P (curr_insn))
715 201691030 : continue;
716 :
717 220459896 : curr_id = lra_get_insn_recog_data (curr_insn);
718 220459896 : curr_static_id = curr_id->insn_static_data;
719 220459896 : n_alt = curr_id->used_insn_alternative;
720 220459896 : 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 220459896 : set = single_set (curr_insn);
725 :
726 220459896 : if (dead_insn_p && set != NULL_RTX
727 169839114 : && REG_P (SET_DEST (set)) && !HARD_REGISTER_P (SET_DEST (set))
728 88431271 : && find_reg_note (curr_insn, REG_EH_REGION, NULL_RTX) == NULL_RTX
729 88203140 : && ! 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 299801446 : && (pic_offset_table_rtx == NULL_RTX
733 8905920 : || pic_offset_table_rtx != SET_DEST (set)))
734 : {
735 79276443 : bool remove_p = true;
736 :
737 79851849 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
738 79803068 : if (reg->type != OP_IN
739 79803068 : && (reg->regno < FIRST_PSEUDO_REGISTER
740 79276575 : ? TEST_HARD_REG_BIT (hard_regs_live, reg->regno)
741 79276573 : : sparseset_bit_p (pseudos_live, reg->regno)))
742 : {
743 : remove_p = false;
744 : break;
745 : }
746 80515473 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
747 15722890 : if (reg->type != OP_IN)
748 : {
749 : remove_p = false;
750 : break;
751 : }
752 :
753 79276443 : if (remove_p && ! volatile_refs_p (PATTERN (curr_insn)))
754 : {
755 43479 : dst_regno = REGNO (SET_DEST (set));
756 43479 : if (lra_dump_file != NULL)
757 0 : fprintf (lra_dump_file, " Deleting dead insn %u\n",
758 0 : INSN_UID (curr_insn));
759 43479 : lra_set_insn_deleted (curr_insn);
760 43479 : if (lra_reg_info[dst_regno].nrefs == 0)
761 : {
762 : /* There might be some debug insns with the pseudo. */
763 6630 : unsigned int uid;
764 6630 : rtx_insn *insn;
765 :
766 6630 : bitmap_copy (&temp_bitmap, &lra_reg_info[dst_regno].insn_bitmap);
767 6885 : 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 43479 : continue;
776 43479 : }
777 : }
778 :
779 : /* Update max ref width and hard reg usage. */
780 575262210 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
781 : {
782 354845793 : int regno = reg->regno;
783 :
784 354845793 : lra_update_biggest_mode (regno, reg->biggest_mode);
785 354845793 : if (HARD_REGISTER_NUM_P (regno))
786 97280591 : lra_hard_reg_usage[regno] += freq;
787 : }
788 :
789 220416417 : 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 220416417 : rtx ignore_reg = non_conflicting_reg_copy_p (curr_insn);
795 220416417 : if (ignore_reg != NULL_RTX)
796 : {
797 59157264 : int ignore_regno = REGNO (ignore_reg);
798 59157264 : if (HARD_REGISTER_NUM_P (ignore_regno)
799 59157264 : && TEST_HARD_REG_BIT (hard_regs_live, ignore_regno))
800 170108 : CLEAR_HARD_REG_BIT (hard_regs_live, ignore_regno);
801 58987156 : else if (!HARD_REGISTER_NUM_P (ignore_regno)
802 58987156 : && sparseset_bit_p (pseudos_live, ignore_regno))
803 11753919 : 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 210672127 : src_regno = (set != NULL_RTX && REG_P (SET_SRC (set))
811 300863643 : ? REGNO (SET_SRC (set)) : -1);
812 210672127 : dst_regno = (set != NULL_RTX && REG_P (SET_DEST (set))
813 156817346 : ? REGNO (SET_DEST (set)) : -1);
814 220416417 : if (complete_info_p
815 219589834 : && 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 279434005 : && (((!HARD_REGISTER_NUM_P (src_regno)
820 52070016 : && (! sparseset_bit_p (pseudos_live, src_regno)
821 9246 : || (!HARD_REGISTER_NUM_P (dst_regno)
822 59017588 : && 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 6947572 : && ! TEST_HARD_REG_BIT (hard_regs_live, src_regno)))
827 : /* It might be 'inheritance pseudo <- reload pseudo'. */
828 9259 : || (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 59008329 : int hard_regno = -1, regno = -1;
836 :
837 59008329 : if (dst_regno >= lra_constraint_new_regno_start
838 15795714 : && 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 5897829 : if (dst_regno != src_regno)
846 5897829 : lra_create_copy (dst_regno, src_regno, freq);
847 : }
848 53110500 : else if (dst_regno >= lra_constraint_new_regno_start)
849 : {
850 9897885 : if (!HARD_REGISTER_NUM_P (hard_regno = src_regno))
851 9793228 : hard_regno = reg_renumber[src_regno];
852 : regno = dst_regno;
853 : }
854 43212615 : else if (src_regno >= lra_constraint_new_regno_start)
855 : {
856 10871067 : if (!HARD_REGISTER_NUM_P (hard_regno = dst_regno))
857 9196466 : hard_regno = reg_renumber[dst_regno];
858 : regno = src_regno;
859 : }
860 59008329 : if (regno >= 0 && hard_regno >= 0)
861 12539270 : lra_setup_reload_pseudo_preferenced_hard_reg
862 12539270 : (regno, hard_regno, freq);
863 : }
864 :
865 220416417 : 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 575262210 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
871 354845793 : if (reg->type != OP_IN)
872 : {
873 151882513 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
874 151882513 : mark_regno_live (reg->regno, reg->biggest_mode);
875 : /* ??? Should be a no-op for unused registers. */
876 151882513 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
877 : }
878 :
879 277310232 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
880 56893815 : if (reg->type != OP_IN)
881 40835639 : make_hard_regno_live (reg->regno);
882 :
883 220416417 : if (curr_id->arg_hard_regs != NULL)
884 31830453 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
885 22472681 : if (!HARD_REGISTER_NUM_P (regno))
886 : /* It is a clobber. */
887 944146 : make_hard_regno_live (regno - FIRST_PSEUDO_REGISTER);
888 :
889 220416417 : sparseset_copy (unused_set, start_living);
890 :
891 220416417 : sparseset_clear (start_dying);
892 :
893 : /* See which defined values die here. */
894 575262210 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
895 354845793 : if (reg->type != OP_IN
896 657177570 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
897 : {
898 150449264 : if (reg->type == OP_OUT)
899 130843382 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
900 150449264 : mark_regno_dead (reg->regno, reg->biggest_mode);
901 : }
902 :
903 277310232 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
904 56893815 : if (reg->type != OP_IN
905 114343479 : && ! reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
906 16614025 : make_hard_regno_dead (reg->regno);
907 :
908 220416417 : if (curr_id->arg_hard_regs != NULL)
909 31830453 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
910 22472681 : if (!HARD_REGISTER_NUM_P (regno))
911 : /* It is a clobber. */
912 944146 : make_hard_regno_dead (regno - FIRST_PSEUDO_REGISTER);
913 :
914 220416417 : if (call_p)
915 : {
916 12087246 : function_abi call_abi = insn_callee_abi (curr_insn);
917 :
918 12087246 : if (last_call_abi != call_abi)
919 7078046 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
920 4838352 : check_pseudos_live_through_calls (j, last_call_abi);
921 :
922 12087246 : last_call_abi = call_abi;
923 :
924 12087246 : sparseset_ior (pseudos_live_through_calls,
925 : pseudos_live_through_calls, pseudos_live);
926 12087246 : if (cfun->has_nonlocal_label
927 12087246 : || (!targetm.setjmp_preserves_nonvolatile_regs_p ()
928 12083058 : && (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 220416417 : if (sparseset_contains_pseudos_p (unused_set)
936 220416417 : || sparseset_contains_pseudos_p (start_dying))
937 111591467 : 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 220416417 : if (ignore_reg != NULL_RTX)
943 : {
944 11924027 : int ignore_regno = REGNO (ignore_reg);
945 11924027 : if (HARD_REGISTER_NUM_P (ignore_regno))
946 170108 : SET_HARD_REG_BIT (hard_regs_live, ignore_regno);
947 : else
948 11753919 : sparseset_set_bit (pseudos_live, ignore_regno);
949 : }
950 :
951 220416417 : sparseset_clear (start_living);
952 :
953 : /* Mark each used value as live. */
954 575262210 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
955 354845793 : if (reg->type != OP_OUT)
956 : {
957 222707569 : if (reg->type == OP_IN)
958 202963280 : update_pseudo_point (reg->regno, curr_point, USE_POINT);
959 222707569 : mark_regno_live (reg->regno, reg->biggest_mode);
960 222707569 : check_pseudos_live_through_calls (reg->regno, last_call_abi);
961 : }
962 :
963 277310232 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
964 56893815 : if (reg->type != OP_OUT)
965 16542017 : make_hard_regno_live (reg->regno);
966 :
967 220416417 : if (curr_id->arg_hard_regs != NULL)
968 : /* Make argument hard registers live. */
969 31830453 : for (i = 0; (regno = curr_id->arg_hard_regs[i]) >= 0; i++)
970 22472681 : if (HARD_REGISTER_NUM_P (regno))
971 21528535 : make_hard_regno_live (regno);
972 :
973 220416417 : sparseset_and_compl (dead_set, start_living, start_dying);
974 :
975 220416417 : sparseset_clear (start_dying);
976 :
977 : /* Mark early clobber outputs dead. */
978 575262210 : for (reg = curr_id->regs; reg != NULL; reg = reg->next)
979 354845793 : if (reg->type != OP_IN
980 507069586 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
981 : {
982 341280 : if (reg->type == OP_OUT)
983 224993 : update_pseudo_point (reg->regno, curr_point, DEF_POINT);
984 341280 : 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 341280 : if (reg->type == OP_INOUT)
989 116287 : mark_regno_live (reg->regno, reg->biggest_mode);
990 : }
991 :
992 277310232 : for (reg = curr_static_id->hard_regs; reg != NULL; reg = reg->next)
993 56893815 : if (reg->type != OP_IN
994 121951068 : && reg_early_clobber_p (reg, n_alt) && ! reg->subreg_p)
995 : {
996 24221614 : 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 48742101 : for (reg2 = curr_static_id->hard_regs; reg2 != NULL; reg2 = reg2->next)
1002 24543157 : if (reg2->type != OP_OUT && reg2->regno == reg->regno)
1003 : break;
1004 24221614 : if (reg2 != NULL)
1005 22670 : continue;
1006 :
1007 : HARD_REG_SET clobbered_regset;
1008 24198944 : CLEAR_HARD_REG_SET (clobbered_regset);
1009 24198944 : SET_HARD_REG_BIT (clobbered_regset, reg->regno);
1010 :
1011 67120831 : for (reg2 = curr_id->regs; reg2 != NULL; reg2 = reg2->next)
1012 30495899 : if (reg2->type != OP_OUT && reg2->regno < FIRST_PSEUDO_REGISTER
1013 51186727 : && ira_hard_reg_set_intersection_p (reg2->regno,
1014 8251738 : reg2->biggest_mode,
1015 : clobbered_regset))
1016 : break;
1017 24198944 : if (reg2 == NULL)
1018 : {
1019 24185842 : make_hard_regno_dead (reg->regno);
1020 : }
1021 : else
1022 : {
1023 164716 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, j)
1024 151614 : 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 220416417 : if (sparseset_contains_pseudos_p (dead_set)
1031 220416417 : || sparseset_contains_pseudos_p (start_dying))
1032 87114676 : next_program_point (curr_point, freq);
1033 :
1034 : /* Update notes. */
1035 443766080 : for (link_loc = ®_NOTES (curr_insn); (link = *link_loc) != NULL_RTX;)
1036 : {
1037 223349663 : if (REG_NOTE_KIND (link) != REG_DEAD
1038 92513811 : && REG_NOTE_KIND (link) != REG_UNUSED)
1039 : ;
1040 158084890 : else if (REG_P (XEXP (link, 0)))
1041 : {
1042 158084890 : rtx note_reg = XEXP (link, 0);
1043 158084890 : int note_regno = REGNO (note_reg);
1044 :
1045 161471791 : if ((REG_NOTE_KIND (link) == REG_DEAD
1046 130835852 : && ! regnos_in_sparseset_p (dead_set, note_regno,
1047 130835852 : GET_MODE (note_reg)))
1048 286642004 : || (REG_NOTE_KIND (link) == REG_UNUSED
1049 27249038 : && ! regnos_in_sparseset_p (unused_set, note_regno,
1050 27249038 : GET_MODE (note_reg))))
1051 : {
1052 3386901 : *link_loc = XEXP (link, 1);
1053 3386901 : continue;
1054 : }
1055 154697989 : if (REG_NOTE_KIND (link) == REG_DEAD)
1056 128557114 : clear_sparseset_regnos (dead_set, note_regno,
1057 128557114 : GET_MODE (note_reg));
1058 26140875 : else if (REG_NOTE_KIND (link) == REG_UNUSED)
1059 26140875 : clear_sparseset_regnos (unused_set, note_regno,
1060 26140875 : GET_MODE (note_reg));
1061 : }
1062 219962762 : link_loc = &XEXP (link, 1);
1063 : }
1064 229304870 : EXECUTE_IF_SET_IN_SPARSESET (dead_set, j)
1065 8888453 : add_reg_note (curr_insn, REG_DEAD, regno_reg_rtx[j]);
1066 442666225 : EXECUTE_IF_SET_IN_SPARSESET (unused_set, j)
1067 1833391 : add_reg_note (curr_insn, REG_UNUSED, regno_reg_rtx[j]);
1068 : }
1069 :
1070 32257982 : 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 538414 : for (j = 0; ; ++j)
1076 : {
1077 1615242 : unsigned int regno = EH_RETURN_DATA_REGNO (j);
1078 :
1079 1076828 : if (regno == INVALID_REGNUM)
1080 : break;
1081 :
1082 1076828 : make_hard_regno_live (regno);
1083 1076828 : make_hard_regno_dead (regno);
1084 1076828 : }
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 32257982 : if (bb_has_abnormal_pred (bb))
1092 : {
1093 : HARD_REG_SET clobbers;
1094 :
1095 541692 : CLEAR_HARD_REG_SET (clobbers);
1096 : #ifdef STACK_REGS
1097 1734164 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, px)
1098 1192472 : lra_reg_info[px].no_stack_p = true;
1099 4875228 : for (px = FIRST_STACK_REG; px <= LAST_STACK_REG; px++)
1100 4333536 : 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 541692 : if (!cfun->has_nonlocal_label
1106 541692 : && has_abnormal_call_or_eh_pred_edge_p (bb))
1107 50071665 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1108 49533260 : 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 49986664 : || (px == REAL_PIC_OFFSET_TABLE_REGNUM
1116 538405 : && pic_offset_table_rtx != NULL_RTX
1117 22203 : && !HARD_REGISTER_P (pic_offset_table_rtx))
1118 : #endif
1119 : )
1120 44839362 : SET_HARD_REG_BIT (clobbers, px);
1121 :
1122 541692 : clobbers &= ~hard_regs_live;
1123 50377356 : for (px = 0; HARD_REGISTER_NUM_P (px); px++)
1124 49835664 : if (TEST_HARD_REG_BIT (clobbers, px))
1125 : {
1126 44865658 : make_hard_regno_live (px);
1127 44865658 : make_hard_regno_dead (px);
1128 : }
1129 : }
1130 :
1131 32257982 : bool live_change_p = false;
1132 : /* Check if bb border live info was changed. */
1133 32257982 : unsigned int live_pseudos_num = 0;
1134 431369370 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb),
1135 : FIRST_PSEUDO_REGISTER, j, bi)
1136 : {
1137 399343549 : live_pseudos_num++;
1138 399343549 : if (! sparseset_bit_p (pseudos_live, j))
1139 : {
1140 232161 : live_change_p = true;
1141 232161 : 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 32025821 : && sparseset_cardinality (pseudos_live) != live_pseudos_num)
1149 : {
1150 183107 : live_change_p = true;
1151 183107 : 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 32257982 : need_curr_point_incr = (sparseset_cardinality (pseudos_live) > 0);
1161 :
1162 831851806 : EXECUTE_IF_SET_IN_SPARSESET (pseudos_live, i)
1163 : {
1164 399796912 : update_pseudo_point (i, curr_point, DEF_POINT);
1165 399796912 : mark_pseudo_dead (i);
1166 : }
1167 :
1168 124014157 : EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, j, bi)
1169 : {
1170 113570386 : if (sparseset_cardinality (pseudos_live_through_calls) == 0)
1171 : break;
1172 91756175 : if (sparseset_bit_p (pseudos_live_through_calls, j))
1173 85035705 : check_pseudos_live_through_calls (j, last_call_abi);
1174 : }
1175 :
1176 2999992326 : for (i = 0; HARD_REGISTER_NUM_P (i); ++i)
1177 : {
1178 2967734344 : if (!TEST_HARD_REG_BIT (hard_regs_live, i))
1179 2923470893 : continue;
1180 :
1181 44263451 : if (!TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1182 44263451 : 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 32257982 : if (need_curr_point_incr)
1196 26037460 : next_program_point (curr_point, freq);
1197 :
1198 32257982 : 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 1567167 : remove_some_program_points_and_update_live_ranges (void)
1207 : {
1208 1567167 : unsigned i;
1209 1567167 : int n, max_regno;
1210 1567167 : int *map;
1211 1567167 : lra_live_range_t r, prev_r, next_r;
1212 1567167 : sbitmap_iterator sbi;
1213 1567167 : bool born_p, dead_p, prev_born_p, prev_dead_p;
1214 :
1215 1567167 : auto_sbitmap born (lra_live_max_point);
1216 1567167 : auto_sbitmap dead (lra_live_max_point);
1217 1567167 : bitmap_clear (born);
1218 1567167 : bitmap_clear (dead);
1219 1567167 : max_regno = max_reg_num ();
1220 171851125 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1221 : {
1222 282615763 : for (r = lra_reg_info[i].live_ranges; r != NULL; r = r->next)
1223 : {
1224 112331805 : lra_assert (r->start <= r->finish);
1225 112331805 : bitmap_set_bit (born, r->start);
1226 112331805 : bitmap_set_bit (dead, r->finish);
1227 : }
1228 : }
1229 1567167 : auto_sbitmap born_or_dead (lra_live_max_point);
1230 1567167 : bitmap_ior (born_or_dead, born, dead);
1231 1567167 : map = XCNEWVEC (int, lra_live_max_point);
1232 1567167 : n = -1;
1233 1567167 : prev_born_p = prev_dead_p = false;
1234 197260371 : EXECUTE_IF_SET_IN_BITMAP (born_or_dead, 0, i, sbi)
1235 : {
1236 194126037 : born_p = bitmap_bit_p (born, i);
1237 194126037 : dead_p = bitmap_bit_p (dead, i);
1238 194126037 : if ((prev_born_p && ! prev_dead_p && born_p && ! dead_p)
1239 179153551 : || (prev_dead_p && ! prev_born_p && dead_p && ! born_p))
1240 : {
1241 42647072 : map[i] = n;
1242 42647072 : lra_point_freq[n] = MAX (lra_point_freq[n], lra_point_freq[i]);
1243 : }
1244 : else
1245 : {
1246 151478965 : map[i] = ++n;
1247 151478965 : lra_point_freq[n] = lra_point_freq[i];
1248 : }
1249 194126037 : prev_born_p = born_p;
1250 194126037 : prev_dead_p = dead_p;
1251 : }
1252 1567167 : n++;
1253 1567167 : 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 1567167 : if (n < lra_live_max_point)
1258 : {
1259 1331691 : lra_live_max_point = n;
1260 168464012 : for (i = FIRST_PSEUDO_REGISTER; i < (unsigned) max_regno; i++)
1261 : {
1262 167132321 : for (prev_r = NULL, r = lra_reg_info[i].live_ranges;
1263 278702130 : r != NULL;
1264 : r = next_r)
1265 : {
1266 111569809 : next_r = r->next;
1267 111569809 : r->start = map[r->start];
1268 111569809 : r->finish = map[r->finish];
1269 111569809 : if (prev_r == NULL || prev_r->start > r->finish + 1)
1270 : {
1271 109418930 : prev_r = r;
1272 109418930 : continue;
1273 : }
1274 2150879 : prev_r->start = r->start;
1275 2150879 : prev_r->next = next_r;
1276 2150879 : lra_live_range_pool.remove (r);
1277 : }
1278 : }
1279 : }
1280 1567167 : free (map);
1281 1567167 : }
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 1567167 : compress_live_ranges (void)
1352 : {
1353 1567167 : remove_some_program_points_and_update_live_ranges ();
1354 1567167 : 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 1567167 : }
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 1768372 : lra_create_live_ranges_1 (bool all_p, bool dead_insn_p)
1374 : {
1375 1768372 : basic_block bb;
1376 1768372 : int i, hard_regno, max_regno = max_reg_num ();
1377 1768372 : int curr_point;
1378 1768372 : bool bb_live_change_p, have_referenced_pseudos = false;
1379 :
1380 1768372 : timevar_push (TV_LRA_CREATE_LIVE_RANGES);
1381 :
1382 1768372 : complete_info_p = all_p;
1383 1768372 : 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 1768372 : memset (lra_hard_reg_usage, 0, sizeof (lra_hard_reg_usage));
1388 337012046 : for (i = 0; i < max_regno; i++)
1389 : {
1390 335243674 : lra_reg_info[i].live_ranges = NULL;
1391 335243674 : CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
1392 335243674 : lra_reg_info[i].preferred_hard_regno1 = -1;
1393 335243674 : lra_reg_info[i].preferred_hard_regno2 = -1;
1394 335243674 : lra_reg_info[i].preferred_hard_regno_profit1 = 0;
1395 335243674 : lra_reg_info[i].preferred_hard_regno_profit2 = 0;
1396 : #ifdef STACK_REGS
1397 335243674 : 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 335243674 : if (!HARD_REGISTER_NUM_P (i) && regno_reg_rtx[i] != NULL_RTX)
1404 171727510 : lra_reg_info[i].biggest_mode = GET_MODE (regno_reg_rtx[i]);
1405 : else
1406 163516164 : lra_reg_info[i].biggest_mode = VOIDmode;
1407 335243674 : if (!HARD_REGISTER_NUM_P (i)
1408 172553450 : && lra_reg_info[i].nrefs != 0)
1409 : {
1410 88505675 : if ((hard_regno = reg_renumber[i]) >= 0)
1411 72977803 : lra_hard_reg_usage[hard_regno] += lra_reg_info[i].freq;
1412 : have_referenced_pseudos = true;
1413 : }
1414 : }
1415 1768372 : 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 1768372 : if (! have_referenced_pseudos)
1421 : {
1422 201205 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1423 201205 : return false;
1424 : }
1425 :
1426 1567167 : pseudos_live = sparseset_alloc (max_regno);
1427 1567167 : pseudos_live_through_calls = sparseset_alloc (max_regno);
1428 1567167 : pseudos_live_through_setjumps = sparseset_alloc (max_regno);
1429 1567167 : start_living = sparseset_alloc (max_regno);
1430 1567167 : start_dying = sparseset_alloc (max_regno);
1431 1567167 : dead_set = sparseset_alloc (max_regno);
1432 1567167 : unused_set = sparseset_alloc (max_regno);
1433 1567167 : curr_point = 0;
1434 1567167 : unsigned new_length = get_max_uid () * 2;
1435 1567167 : point_freq_vec.truncate (0);
1436 1567167 : point_freq_vec.reserve_exact (new_length);
1437 1567167 : lra_point_freq = point_freq_vec.address ();
1438 1567167 : int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
1439 1567167 : int n = inverted_rev_post_order_compute (cfun, rpo);
1440 1567167 : lra_assert (n == n_basic_blocks_for_fn (cfun));
1441 : bb_live_change_p = false;
1442 36959483 : for (i = 0; i < n; ++i)
1443 : {
1444 35392316 : bb = BASIC_BLOCK_FOR_FN (cfun, rpo[i]);
1445 35392316 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb
1446 33825149 : == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1447 3134334 : continue;
1448 32257982 : if (process_bb_lives (bb, curr_point, dead_insn_p))
1449 35392316 : bb_live_change_p = true;
1450 : }
1451 1567167 : free (rpo);
1452 1567167 : 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 6553831 : FOR_EACH_BB_FN (bb, cfun)
1457 : {
1458 6437670 : bitmap_clear_range (df_get_live_in (bb), FIRST_PSEUDO_REGISTER,
1459 6437670 : max_regno - FIRST_PSEUDO_REGISTER);
1460 6437670 : 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 10802973 : for (int i = 0; HARD_REGISTER_NUM_P (i); ++i)
1466 : {
1467 10686812 : if (TEST_HARD_REG_BIT (hard_regs_spilled_into, i))
1468 0 : bitmap_clear_bit (&all_hard_regs_bitmap, i);
1469 : }
1470 116161 : df_simple_dataflow
1471 116161 : (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 116161 : 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 1567167 : lra_live_max_point = curr_point;
1496 1567167 : if (lra_dump_file != NULL)
1497 95 : print_live_ranges (lra_dump_file);
1498 : /* Clean up. */
1499 1567167 : sparseset_free (unused_set);
1500 1567167 : sparseset_free (dead_set);
1501 1567167 : sparseset_free (start_dying);
1502 1567167 : sparseset_free (start_living);
1503 1567167 : sparseset_free (pseudos_live_through_calls);
1504 1567167 : sparseset_free (pseudos_live_through_setjumps);
1505 1567167 : sparseset_free (pseudos_live);
1506 1567167 : compress_live_ranges ();
1507 1567167 : timevar_pop (TV_LRA_CREATE_LIVE_RANGES);
1508 1567167 : 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 1652211 : lra_create_live_ranges (bool all_p, bool dead_insn_p)
1517 : {
1518 1652211 : if (! lra_create_live_ranges_1 (all_p, dead_insn_p))
1519 : return;
1520 116161 : 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 116161 : lra_clear_live_ranges ();
1532 116161 : bool res = lra_create_live_ranges_1 (all_p, false);
1533 116161 : 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 1753610 : lra_clear_live_ranges (void)
1552 : {
1553 1753610 : int i;
1554 :
1555 325619859 : for (i = 0; i < max_reg_num (); i++)
1556 323866249 : free_live_range_list (lra_reg_info[i].live_ranges);
1557 1753610 : point_freq_vec.release ();
1558 1753610 : }
1559 :
1560 : /* Initialize live ranges data once per function. */
1561 : void
1562 1471362 : lra_live_ranges_init (void)
1563 : {
1564 1471362 : bitmap_initialize (&temp_bitmap, ®_obstack);
1565 1471362 : initiate_live_solver ();
1566 1471362 : }
1567 :
1568 : /* Finish live ranges data once per function. */
1569 : void
1570 1471362 : lra_live_ranges_finish (void)
1571 : {
1572 1471362 : finish_live_solver ();
1573 1471362 : bitmap_clear (&temp_bitmap);
1574 1471362 : lra_live_range_pool.release ();
1575 1471362 : }
|
