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