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