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