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