Line data Source code
1 : /* IRA conflict builder.
2 : Copyright (C) 2006-2026 Free Software Foundation, Inc.
3 : Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "target.h"
26 : #include "rtl.h"
27 : #include "predict.h"
28 : #include "memmodel.h"
29 : #include "tm_p.h"
30 : #include "insn-config.h"
31 : #include "regs.h"
32 : #include "ira.h"
33 : #include "ira-int.h"
34 : #include "sparseset.h"
35 : #include "addresses.h"
36 :
37 : /* This file contains code responsible for allocno conflict creation,
38 : allocno copy creation and allocno info accumulation on upper level
39 : regions. */
40 :
41 : /* ira_allocnos_num array of arrays of bits, recording whether two
42 : allocno's conflict (can't go in the same hardware register).
43 :
44 : Some arrays will be used as conflict bit vector of the
45 : corresponding allocnos see function build_object_conflicts. */
46 : static IRA_INT_TYPE **conflicts;
47 :
48 : /* Macro to test a conflict of C1 and C2 in `conflicts'. */
49 : #define OBJECTS_CONFLICT_P(C1, C2) \
50 : (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2) \
51 : && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1) \
52 : && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)], \
53 : OBJECT_CONFLICT_ID (C2), \
54 : OBJECT_MIN (C1), OBJECT_MAX (C1)))
55 :
56 :
57 : /* Record a conflict between objects OBJ1 and OBJ2. If necessary,
58 : canonicalize the conflict by recording it for lower-order subobjects
59 : of the corresponding allocnos. */
60 : static void
61 217742838 : record_object_conflict (ira_object_t obj1, ira_object_t obj2)
62 : {
63 217742838 : ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
64 217742838 : ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
65 217742838 : int w1 = OBJECT_SUBWORD (obj1);
66 217742838 : int w2 = OBJECT_SUBWORD (obj2);
67 217742838 : int id1, id2;
68 :
69 : /* Canonicalize the conflict. If two identically-numbered words
70 : conflict, always record this as a conflict between words 0. That
71 : is the only information we need, and it is easier to test for if
72 : it is collected in each allocno's lowest-order object. */
73 217742838 : if (w1 == w2 && w1 > 0)
74 : {
75 1273951 : obj1 = ALLOCNO_OBJECT (a1, 0);
76 1273951 : obj2 = ALLOCNO_OBJECT (a2, 0);
77 : }
78 217742838 : id1 = OBJECT_CONFLICT_ID (obj1);
79 217742838 : id2 = OBJECT_CONFLICT_ID (obj2);
80 :
81 217742838 : SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
82 : OBJECT_MAX (obj1));
83 217742838 : SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
84 : OBJECT_MAX (obj2));
85 217742838 : }
86 :
87 : /* Build allocno conflict table by processing allocno live ranges.
88 : Return true if the table was built. The table is not built if it
89 : is too big. */
90 : static bool
91 1057059 : build_conflict_bit_table (void)
92 : {
93 1057059 : int i;
94 1057059 : unsigned int j;
95 1057059 : enum reg_class aclass;
96 1057059 : int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
97 1057059 : live_range_t r;
98 1057059 : ira_allocno_t allocno;
99 1057059 : ira_allocno_iterator ai;
100 1057059 : sparseset objects_live;
101 1057059 : ira_object_t obj;
102 1057059 : ira_allocno_object_iterator aoi;
103 :
104 1057059 : allocated_words_num = 0;
105 27417551 : FOR_EACH_ALLOCNO (allocno, ai)
106 52143639 : FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
107 : {
108 25783147 : if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
109 909901 : continue;
110 24873246 : conflict_bit_vec_words_num
111 24873246 : = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
112 : / IRA_INT_BITS);
113 24873246 : allocated_words_num += conflict_bit_vec_words_num;
114 24873246 : if ((uint64_t) allocated_words_num * sizeof (IRA_INT_TYPE)
115 24873246 : > (uint64_t) param_ira_max_conflict_table_size * 1024 * 1024)
116 : {
117 0 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
118 0 : fprintf (ira_dump_file,
119 : "+++Conflict table will be too big(>%dMB) "
120 : "-- don't use it\n",
121 : param_ira_max_conflict_table_size);
122 0 : return false;
123 : }
124 : }
125 :
126 2114118 : conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
127 1057059 : * ira_objects_num);
128 1057059 : allocated_words_num = 0;
129 27417551 : FOR_EACH_ALLOCNO (allocno, ai)
130 52143639 : FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
131 : {
132 25783147 : int id = OBJECT_CONFLICT_ID (obj);
133 25783147 : if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
134 : {
135 909901 : conflicts[id] = NULL;
136 909901 : continue;
137 : }
138 24873246 : conflict_bit_vec_words_num
139 24873246 : = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
140 : / IRA_INT_BITS);
141 24873246 : allocated_words_num += conflict_bit_vec_words_num;
142 24873246 : conflicts[id]
143 49746492 : = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
144 24873246 : * conflict_bit_vec_words_num);
145 24873246 : memset (conflicts[id], 0,
146 : sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
147 : }
148 :
149 1057059 : object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
150 1057059 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
151 39 : fprintf (ira_dump_file,
152 : "+++Allocating " HOST_SIZE_T_PRINT_UNSIGNED
153 : " bytes for conflict table (uncompressed size "
154 : HOST_SIZE_T_PRINT_UNSIGNED ")\n",
155 39 : (fmt_size_t) (sizeof (IRA_INT_TYPE) * allocated_words_num),
156 39 : (fmt_size_t) (sizeof (IRA_INT_TYPE) * object_set_words
157 39 : * ira_objects_num));
158 :
159 1057059 : objects_live = sparseset_alloc (ira_objects_num);
160 30786151 : for (i = 0; i < ira_max_point; i++)
161 : {
162 57011298 : for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
163 : {
164 27282206 : ira_object_t obj = r->object;
165 27282206 : ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
166 27282206 : int id = OBJECT_CONFLICT_ID (obj);
167 :
168 27282206 : gcc_assert (id < ira_objects_num);
169 :
170 27282206 : aclass = ALLOCNO_CLASS (allocno);
171 531625136 : EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
172 : {
173 286076381 : ira_object_t live_obj = ira_object_id_map[j];
174 286076381 : ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
175 286076381 : enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
176 :
177 286076381 : if (ira_reg_classes_intersect_p[aclass][live_aclass]
178 : /* Don't set up conflict for the allocno with itself. */
179 218266549 : && live_a != allocno)
180 : {
181 217742838 : record_object_conflict (obj, live_obj);
182 : }
183 : }
184 27282206 : sparseset_set_bit (objects_live, id);
185 : }
186 :
187 57011298 : for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
188 27282206 : sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
189 : }
190 1057059 : sparseset_free (objects_live);
191 1057059 : return true;
192 : }
193 :
194 : /* Return true iff allocnos A1 and A2 cannot be allocated to the same
195 : register due to conflicts. */
196 :
197 : static bool
198 8022408 : allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
199 : {
200 : /* Due to the fact that we canonicalize conflicts (see
201 : record_object_conflict), we only need to test for conflicts of
202 : the lowest order words. */
203 8022408 : ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
204 8022408 : ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
205 :
206 8022408 : return OBJECTS_CONFLICT_P (obj1, obj2);
207 : }
208 :
209 : /* Check that X is REG or SUBREG of REG. */
210 : #define REG_SUBREG_P(x) \
211 : (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
212 :
213 : /* Return X if X is a REG, otherwise it should be SUBREG of REG and
214 : the function returns the reg in this case. *OFFSET will be set to
215 : 0 in the first case or the regno offset in the first case. */
216 : static rtx
217 25161334 : go_through_subreg (rtx x, int *offset)
218 : {
219 25161334 : rtx reg;
220 :
221 25161334 : *offset = 0;
222 25161334 : if (REG_P (x))
223 : return x;
224 1066079 : ira_assert (GET_CODE (x) == SUBREG);
225 1066079 : reg = SUBREG_REG (x);
226 1066079 : ira_assert (REG_P (reg));
227 1066079 : if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
228 0 : *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
229 0 : SUBREG_BYTE (x), GET_MODE (x));
230 : /* The offset is always 0 for paradoxical subregs. */
231 1066079 : else if (!can_div_trunc_p (SUBREG_BYTE (x),
232 1066079 : REGMODE_NATURAL_SIZE (GET_MODE (reg)), offset))
233 : /* Checked by validate_subreg. We must know at compile time which
234 : inner hard registers are being accessed. */
235 : gcc_unreachable ();
236 : return reg;
237 : }
238 :
239 : /* Return the recomputed frequency for this shuffle copy or its similar
240 : case, since it's not for a real move insn, make it smaller. */
241 :
242 : static int
243 11620296 : get_freq_for_shuffle_copy (int freq)
244 : {
245 9813947 : return freq < 8 ? 1 : freq / 8;
246 : }
247 :
248 : /* Process registers REG1 and REG2 in move INSN with execution
249 : frequency FREQ. The function also processes the registers in a
250 : potential move insn (INSN == NULL in this case) with frequency
251 : FREQ. The function can modify hard register costs of the
252 : corresponding allocnos or create a copy involving the corresponding
253 : allocnos. The function does nothing if the both registers are hard
254 : registers. When nothing is changed, the function returns FALSE.
255 : SINGLE_INPUT_OP_HAS_CSTR_P is only meaningful when constraint_p
256 : is true, see function ira_get_dup_out_num for its meaning. */
257 : static bool
258 12580667 : process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p, rtx_insn *insn,
259 : int freq, bool single_input_op_has_cstr_p = true)
260 : {
261 12580667 : int allocno_preferenced_hard_regno, index, offset1, offset2;
262 12580667 : int cost, conflict_cost, move_cost;
263 12580667 : bool only_regs_p;
264 12580667 : ira_allocno_t a;
265 12580667 : reg_class_t rclass, aclass;
266 12580667 : machine_mode mode;
267 12580667 : ira_copy_t cp;
268 :
269 12580667 : gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
270 12580667 : only_regs_p = REG_P (reg1) && REG_P (reg2);
271 12580667 : reg1 = go_through_subreg (reg1, &offset1);
272 12580667 : reg2 = go_through_subreg (reg2, &offset2);
273 : /* Set up hard regno preferenced by allocno. If allocno gets the
274 : hard regno the copy (or potential move) insn will be removed. */
275 12580667 : if (HARD_REGISTER_P (reg1))
276 : {
277 3025193 : if (HARD_REGISTER_P (reg2))
278 : return false;
279 3025193 : allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
280 3025193 : a = ira_curr_regno_allocno_map[REGNO (reg2)];
281 : }
282 9555474 : else if (HARD_REGISTER_P (reg2))
283 : {
284 3269430 : allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
285 3269430 : a = ira_curr_regno_allocno_map[REGNO (reg1)];
286 : }
287 : else
288 : {
289 6286044 : ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
290 6286044 : ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
291 :
292 6286044 : if (!allocnos_conflict_for_copy_p (a1, a2)
293 5783559 : && offset1 == offset2
294 6286044 : && ordered_p (GET_MODE_PRECISION (ALLOCNO_MODE (a1)),
295 5711142 : GET_MODE_PRECISION (ALLOCNO_MODE (a2))))
296 : {
297 5711142 : cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
298 : ira_curr_loop_tree_node);
299 5711142 : bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
300 5711142 : return true;
301 : }
302 : else
303 : return false;
304 : }
305 :
306 6294623 : if (! IN_RANGE (allocno_preferenced_hard_regno,
307 : 0, FIRST_PSEUDO_REGISTER - 1))
308 : /* Cannot be tied. */
309 : return false;
310 6294623 : rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
311 6294623 : mode = ALLOCNO_MODE (a);
312 6294623 : aclass = ALLOCNO_CLASS (a);
313 6294623 : if (only_regs_p && insn != NULL_RTX
314 6224962 : && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
315 : /* It is already taken into account in ira-costs.cc. */
316 : return false;
317 376785 : index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
318 376785 : if (index < 0)
319 : /* Cannot be tied. It is not in the allocno class. */
320 : return false;
321 365083 : ira_init_register_move_cost_if_necessary (mode);
322 365083 : if (HARD_REGISTER_P (reg1))
323 180125 : move_cost = ira_register_move_cost[mode][aclass][rclass];
324 : else
325 184958 : move_cost = ira_register_move_cost[mode][rclass][aclass];
326 :
327 365083 : if (!single_input_op_has_cstr_p)
328 : {
329 : /* When this is a constraint copy and the matching constraint
330 : doesn't only exist for this given operand but also for some
331 : other operand(s), it means saving the possible move cost does
332 : NOT need to require reg1 and reg2 to use the same hardware
333 : register, so this hardware preference isn't required to be
334 : fixed. To avoid it to over prefer this hardware register,
335 : and over disparage this hardware register on conflicted
336 : objects, we need some cost tweaking here, similar to what
337 : we do for shuffle copy. */
338 0 : gcc_assert (constraint_p);
339 0 : int reduced_freq = get_freq_for_shuffle_copy (freq);
340 0 : if (HARD_REGISTER_P (reg1))
341 : /* For reg2 = opcode(reg1, reg3 ...), assume that reg3 is a
342 : pseudo register which has matching constraint on reg2,
343 : even if reg2 isn't assigned by reg1, it's still possible
344 : not to have register moves if reg2 and reg3 use the same
345 : hardware register. So to avoid the allocation to over
346 : prefer reg1, we can just take it as a shuffle copy. */
347 0 : cost = conflict_cost = move_cost * reduced_freq;
348 : else
349 : {
350 : /* For reg1 = opcode(reg2, reg3 ...), assume that reg3 is a
351 : pseudo register which has matching constraint on reg2,
352 : to save the register move, it's better to assign reg1
353 : to either of reg2 and reg3 (or one of other pseudos like
354 : reg3), it's reasonable to use freq for the cost. But
355 : for conflict_cost, since reg2 and reg3 conflicts with
356 : each other, both of them has the chance to be assigned
357 : by reg1, assume reg3 has one copy which also conflicts
358 : with reg2, we shouldn't make it less preferred on reg1
359 : since reg3 has the same chance to be assigned by reg1.
360 : So it adjusts the conflic_cost to make it same as what
361 : we use for shuffle copy. */
362 0 : cost = move_cost * freq;
363 0 : conflict_cost = move_cost * reduced_freq;
364 : }
365 : }
366 : else
367 365083 : cost = conflict_cost = move_cost * freq;
368 :
369 408697 : do
370 : {
371 408697 : ira_allocate_and_set_costs
372 408697 : (&ALLOCNO_HARD_REG_COSTS (a), aclass,
373 : ALLOCNO_CLASS_COST (a));
374 408697 : ira_allocate_and_set_costs
375 408697 : (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0);
376 408697 : ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
377 408697 : ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= conflict_cost;
378 408697 : if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
379 367070 : ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
380 408697 : ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq);
381 408697 : a = ira_parent_or_cap_allocno (a);
382 : }
383 408697 : while (a != NULL);
384 : return true;
385 : }
386 :
387 : /* Go through all of OP's dependent filters, check if they reference
388 : REF, and if so, check for all eligible hard regs in its class
389 : whether the filter allows the same regno for both (dependent) operand,
390 : as well as referenced operand. Return true if all filters allow that,
391 : or false otherwise. */
392 :
393 : static bool
394 0 : dependent_filter_same_reg_ok_p (const operand_alternative *op_alt,
395 : int op, int ref)
396 : {
397 0 : unsigned mask = alternative_dependent_filters (op_alt, op);
398 0 : if (!mask)
399 : return true;
400 :
401 0 : enum reg_class cl
402 0 : = ira_reg_class_intersect[op_alt[op].cl][op_alt[ref].cl];
403 :
404 0 : machine_mode mode = recog_data.operand_mode[op];
405 0 : machine_mode ref_mode = recog_data.operand_mode[ref];
406 :
407 0 : for (int id = 0; id < NUM_DEPENDENT_FILTERS; ++id)
408 : {
409 : if (!(mask & (1U << id)))
410 : continue;
411 : if (get_dependent_filter_ref (id) != ref)
412 : continue;
413 :
414 : bool ok = false;
415 : for (int i = 0; i < ira_class_hard_regs_num[cl]; ++i)
416 : {
417 : unsigned regno = ira_class_hard_regs[cl][i];
418 : ok = eval_dependent_filter (id, regno, mode, regno, ref_mode);
419 : if (ok)
420 : break;
421 : }
422 : if (!ok)
423 : return false;
424 : }
425 0 : return true;
426 : }
427 :
428 : /* Return true if output operand OUTPUT and input operand INPUT of
429 : INSN can use the same register class for at least one alternative.
430 : INSN is already described in recog_data and recog_op_alt. */
431 : static bool
432 2729072 : can_use_same_reg_p (rtx_insn *insn, int output, int input)
433 : {
434 2729072 : alternative_mask preferred = get_preferred_alternatives (insn);
435 3934750 : for (int nalt = 0; nalt < recog_data.n_alternatives; nalt++)
436 : {
437 3711029 : if (!TEST_BIT (preferred, nalt))
438 821771 : continue;
439 :
440 2889258 : const operand_alternative *op_alt
441 2889258 : = &recog_op_alt[nalt * recog_data.n_operands];
442 2889258 : if (op_alt[input].matches == output)
443 : return true;
444 :
445 1775585 : if (op_alt[output].earlyclobber)
446 76470 : continue;
447 :
448 1699115 : if (ira_reg_class_intersect[op_alt[input].cl][op_alt[output].cl]
449 : == NO_REGS)
450 307437 : continue;
451 :
452 : if (NUM_DEPENDENT_FILTERS
453 : && (!dependent_filter_same_reg_ok_p (op_alt, input, output)
454 : || !dependent_filter_same_reg_ok_p (op_alt, output, input)))
455 : continue;
456 :
457 : return true;
458 : }
459 : return false;
460 : }
461 :
462 : /* Process all of the output registers of the current insn (INSN) which
463 : are not bound (BOUND_P) and the input register REG (its operand number
464 : OP_NUM) which dies in the insn as if there were a move insn between
465 : them with frequency FREQ. */
466 : static void
467 11620296 : process_reg_shuffles (rtx_insn *insn, rtx reg, int op_num, int freq,
468 : bool *bound_p)
469 : {
470 11620296 : int i;
471 11620296 : rtx another_reg;
472 :
473 11620296 : gcc_assert (REG_SUBREG_P (reg));
474 41909808 : for (i = 0; i < recog_data.n_operands; i++)
475 : {
476 30289512 : another_reg = recog_data.operand[i];
477 :
478 30289512 : if (!REG_SUBREG_P (another_reg) || op_num == i
479 10376537 : || recog_data.operand_type[i] != OP_OUT
480 5774296 : || bound_p[i]
481 32995731 : || (!can_use_same_reg_p (insn, i, op_num)
482 208941 : && (recog_data.constraints[op_num][0] != '%'
483 12779 : || !can_use_same_reg_p (insn, i, op_num + 1))
484 200868 : && (op_num == 0
485 200868 : || recog_data.constraints[op_num - 1][0] != '%'
486 10074 : || !can_use_same_reg_p (insn, i, op_num - 1))))
487 27784161 : continue;
488 :
489 2505351 : process_regs_for_copy (reg, another_reg, false, NULL, freq);
490 : }
491 11620296 : }
492 :
493 : /* Process INSN and create allocno copies if necessary. For example,
494 : it might be because INSN is a pseudo-register move or INSN is two
495 : operand insn. */
496 : static void
497 59373850 : add_insn_allocno_copies (rtx_insn *insn)
498 : {
499 59373850 : rtx set = single_set (insn), operand, dup;
500 59373850 : bool bound_p[MAX_RECOG_OPERANDS];
501 59373850 : int i, n, freq;
502 59373850 : alternative_mask alts;
503 :
504 59373850 : freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
505 49320452 : if (freq == 0)
506 7910326 : freq = 1;
507 :
508 : /* Tie output register operands of two consecutive single_sets
509 : marked as a fused pair. */
510 59373850 : if (single_output_fused_pair_p (insn))
511 0 : process_regs_for_copy (SET_DEST (set),
512 0 : SET_DEST (single_set (prev_nonnote_nondebug_insn (insn))),
513 : true, NULL, freq);
514 :
515 0 : if (set != NULL_RTX
516 55440234 : && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
517 9845972 : && ! side_effects_p (set)
518 69219822 : && find_reg_note (insn, REG_DEAD,
519 9845972 : REG_P (SET_SRC (set))
520 : ? SET_SRC (set)
521 : : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
522 : {
523 7538113 : process_regs_for_copy (SET_SRC (set), SET_DEST (set),
524 : false, insn, freq);
525 46654569 : return;
526 : }
527 : /* Fast check of possibility of constraint or shuffle copies. If
528 : there are no dead registers, there will be no such copies. */
529 51835737 : if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
530 : return;
531 20257394 : alts = ira_setup_alts (insn);
532 87974907 : for (i = 0; i < recog_data.n_operands; i++)
533 47460119 : bound_p[i] = false;
534 67717513 : for (i = 0; i < recog_data.n_operands; i++)
535 : {
536 47460119 : operand = recog_data.operand[i];
537 47460119 : if (! REG_SUBREG_P (operand))
538 26605960 : continue;
539 20854159 : bool single_input_op_has_cstr_p;
540 20854159 : if ((n = ira_get_dup_out_num (i, alts, single_input_op_has_cstr_p)) >= 0)
541 : {
542 3090649 : bound_p[n] = true;
543 3090649 : dup = recog_data.operand[n];
544 138841 : if (REG_SUBREG_P (dup)
545 6168580 : && find_reg_note (insn, REG_DEAD,
546 3077931 : REG_P (operand)
547 : ? operand
548 : : SUBREG_REG (operand)) != NULL_RTX)
549 2537203 : process_regs_for_copy (operand, dup, true, NULL, freq,
550 : single_input_op_has_cstr_p);
551 : }
552 : }
553 67717513 : for (i = 0; i < recog_data.n_operands; i++)
554 : {
555 47460119 : operand = recog_data.operand[i];
556 27452400 : if (REG_SUBREG_P (operand)
557 48306559 : && find_reg_note (insn, REG_DEAD,
558 : REG_P (operand)
559 : ? operand : SUBREG_REG (operand)) != NULL_RTX)
560 : {
561 : /* If an operand dies, prefer its hard register for the output
562 : operands by decreasing the hard register cost or creating
563 : the corresponding allocno copies. The cost will not
564 : correspond to a real move insn cost, so make the frequency
565 : smaller. */
566 11620296 : int new_freq = get_freq_for_shuffle_copy (freq);
567 11620296 : process_reg_shuffles (insn, operand, i, new_freq, bound_p);
568 : }
569 : }
570 : }
571 :
572 : /* Add copies originated from BB given by LOOP_TREE_NODE. */
573 : static void
574 12350481 : add_copies (ira_loop_tree_node_t loop_tree_node)
575 : {
576 12350481 : basic_block bb;
577 12350481 : rtx_insn *insn;
578 :
579 12350481 : bb = loop_tree_node->bb;
580 12350481 : if (bb == NULL)
581 : return;
582 143779512 : FOR_BB_INSNS (bb, insn)
583 132652009 : if (NONDEBUG_INSN_P (insn))
584 59373850 : add_insn_allocno_copies (insn);
585 : }
586 :
587 : /* Propagate copies the corresponding allocnos on upper loop tree
588 : level. */
589 : static void
590 1010507 : propagate_copies (void)
591 : {
592 1010507 : ira_copy_t cp;
593 1010507 : ira_copy_iterator ci;
594 1010507 : ira_allocno_t a1, a2, parent_a1, parent_a2;
595 :
596 8258815 : FOR_EACH_COPY (cp, ci)
597 : {
598 7248308 : a1 = cp->first;
599 7248308 : a2 = cp->second;
600 7248308 : if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
601 5511944 : continue;
602 1736364 : ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
603 1736364 : parent_a1 = ira_parent_or_cap_allocno (a1);
604 1736364 : parent_a2 = ira_parent_or_cap_allocno (a2);
605 1736364 : ira_assert (parent_a1 != NULL && parent_a2 != NULL);
606 1736364 : if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
607 1736060 : ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
608 1736060 : cp->constraint_p, cp->insn, cp->loop_tree_node);
609 : }
610 1010507 : }
611 :
612 : /* Array used to collect all conflict allocnos for given allocno. */
613 : static ira_object_t *collected_conflict_objects;
614 :
615 : /* Build conflict vectors or bit conflict vectors (whatever is more
616 : profitable) for object OBJ from the conflict table. */
617 : static void
618 25783147 : build_object_conflicts (ira_object_t obj)
619 : {
620 25783147 : int i, px, parent_num;
621 25783147 : ira_allocno_t parent_a, another_parent_a;
622 25783147 : ira_object_t parent_obj;
623 25783147 : ira_allocno_t a = OBJECT_ALLOCNO (obj);
624 25783147 : IRA_INT_TYPE *object_conflicts;
625 25783147 : minmax_set_iterator asi;
626 25783147 : int parent_min, parent_max ATTRIBUTE_UNUSED;
627 :
628 25783147 : object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
629 25783147 : px = 0;
630 634877174 : FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
631 : OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
632 : {
633 583310880 : ira_object_t another_obj = ira_object_id_map[i];
634 583310880 : ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
635 :
636 583310880 : ira_assert (ira_reg_classes_intersect_p
637 : [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
638 583310880 : collected_conflict_objects[px++] = another_obj;
639 : }
640 25783147 : if (ira_conflict_vector_profitable_p (obj, px))
641 : {
642 5019937 : ira_object_t *vec;
643 5019937 : ira_allocate_conflict_vec (obj, px);
644 5019937 : vec = OBJECT_CONFLICT_VEC (obj);
645 5019937 : memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
646 5019937 : vec[px] = NULL;
647 5019937 : OBJECT_NUM_CONFLICTS (obj) = px;
648 : }
649 : else
650 : {
651 20763210 : int conflict_bit_vec_words_num;
652 :
653 20763210 : OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
654 20763210 : if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
655 : conflict_bit_vec_words_num = 0;
656 : else
657 19853309 : conflict_bit_vec_words_num
658 19853309 : = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
659 : / IRA_INT_BITS);
660 20763210 : OBJECT_CONFLICT_ARRAY_SIZE (obj)
661 20763210 : = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
662 : }
663 :
664 25783147 : parent_a = ira_parent_or_cap_allocno (a);
665 25783147 : if (parent_a == NULL)
666 18913835 : return;
667 6869312 : ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
668 6869312 : ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
669 6869312 : parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
670 6869312 : parent_num = OBJECT_CONFLICT_ID (parent_obj);
671 6869312 : parent_min = OBJECT_MIN (parent_obj);
672 6869312 : parent_max = OBJECT_MAX (parent_obj);
673 339905442 : FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
674 : OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
675 : {
676 326166818 : ira_object_t another_obj = ira_object_id_map[i];
677 326166818 : ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
678 326166818 : int another_word = OBJECT_SUBWORD (another_obj);
679 :
680 326166818 : ira_assert (ira_reg_classes_intersect_p
681 : [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
682 :
683 326166818 : another_parent_a = ira_parent_or_cap_allocno (another_a);
684 326166818 : if (another_parent_a == NULL)
685 0 : continue;
686 326166818 : ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
687 326166818 : ira_assert (ALLOCNO_CLASS (another_a)
688 : == ALLOCNO_CLASS (another_parent_a));
689 326166818 : ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
690 : == ALLOCNO_NUM_OBJECTS (another_parent_a));
691 326166818 : SET_MINMAX_SET_BIT (conflicts[parent_num],
692 : OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
693 : another_word)),
694 : parent_min, parent_max);
695 : }
696 : }
697 :
698 : /* Build conflict vectors or bit conflict vectors (whatever is more
699 : profitable) of all allocnos from the conflict table. */
700 : static void
701 1057059 : build_conflicts (void)
702 : {
703 1057059 : int i;
704 1057059 : ira_allocno_t a, cap;
705 :
706 1057059 : collected_conflict_objects
707 2114118 : = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
708 1057059 : * ira_objects_num);
709 52838788 : for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
710 51781729 : for (a = ira_regno_allocno_map[i];
711 73442675 : a != NULL;
712 21660946 : a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
713 : {
714 21660946 : int j, nregs = ALLOCNO_NUM_OBJECTS (a);
715 43758465 : for (j = 0; j < nregs; j++)
716 : {
717 22097519 : ira_object_t obj = ALLOCNO_OBJECT (a, j);
718 22097519 : build_object_conflicts (obj);
719 25783147 : for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
720 : {
721 3685628 : ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
722 3685628 : gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
723 3685628 : build_object_conflicts (cap_obj);
724 : }
725 : }
726 : }
727 1057059 : ira_free (collected_conflict_objects);
728 1057059 : }
729 :
730 :
731 :
732 : /* Print hard reg set SET with TITLE to FILE. */
733 : static void
734 836 : print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
735 : {
736 836 : int i, start, end;
737 :
738 836 : fputs (title, file);
739 77748 : for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
740 : {
741 76912 : bool reg_included = TEST_HARD_REG_BIT (set, i);
742 :
743 76912 : if (reg_included)
744 : {
745 782 : if (start == -1)
746 450 : start = i;
747 : end = i;
748 : }
749 76912 : if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
750 : {
751 450 : if (start == end)
752 142 : fprintf (file, " %d", start);
753 308 : else if (start == end + 1)
754 0 : fprintf (file, " %d %d", start, end);
755 : else
756 308 : fprintf (file, " %d-%d", start, end);
757 : start = -1;
758 : }
759 : }
760 836 : putc ('\n', file);
761 836 : }
762 :
763 : static void
764 451 : print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
765 : {
766 451 : HARD_REG_SET conflicting_hard_regs;
767 451 : basic_block bb;
768 451 : int n, i;
769 :
770 451 : if (reg_p)
771 0 : fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
772 : else
773 : {
774 451 : fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
775 451 : if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
776 0 : fprintf (file, "b%d", bb->index);
777 : else
778 451 : fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
779 451 : putc (')', file);
780 : }
781 :
782 451 : fputs (" conflicts:", file);
783 451 : n = ALLOCNO_NUM_OBJECTS (a);
784 902 : for (i = 0; i < n; i++)
785 : {
786 451 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
787 451 : ira_object_t conflict_obj;
788 451 : ira_object_conflict_iterator oci;
789 :
790 451 : if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
791 : {
792 33 : fprintf (file, "\n;; total conflict hard regs:\n");
793 33 : fprintf (file, ";; conflict hard regs:\n\n");
794 33 : continue;
795 : }
796 :
797 418 : if (n > 1)
798 0 : fprintf (file, "\n;; subobject %d:", i);
799 3578 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
800 : {
801 3160 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
802 3160 : if (reg_p)
803 0 : fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
804 : else
805 : {
806 3160 : fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
807 : ALLOCNO_REGNO (conflict_a));
808 3160 : if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
809 0 : fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
810 3160 : if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
811 0 : fprintf (file, ",b%d", bb->index);
812 : else
813 3160 : fprintf (file, ",l%d",
814 : ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
815 3160 : putc (')', file);
816 : }
817 : }
818 418 : conflicting_hard_regs = (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
819 418 : & ~ira_no_alloc_regs
820 418 : & reg_class_contents[ALLOCNO_CLASS (a)]);
821 418 : print_hard_reg_set (file, "\n;; total conflict hard regs:",
822 : conflicting_hard_regs);
823 :
824 418 : conflicting_hard_regs = (OBJECT_CONFLICT_HARD_REGS (obj)
825 418 : & ~ira_no_alloc_regs
826 418 : & reg_class_contents[ALLOCNO_CLASS (a)]);
827 418 : print_hard_reg_set (file, ";; conflict hard regs:",
828 : conflicting_hard_regs);
829 418 : putc ('\n', file);
830 : }
831 :
832 451 : }
833 :
834 : /* Print information about allocno or only regno (if REG_P) conflicts
835 : to FILE. */
836 : static void
837 39 : print_conflicts (FILE *file, bool reg_p)
838 : {
839 39 : ira_allocno_t a;
840 39 : ira_allocno_iterator ai;
841 :
842 490 : FOR_EACH_ALLOCNO (a, ai)
843 451 : print_allocno_conflicts (file, reg_p, a);
844 39 : putc ('\n', file);
845 39 : }
846 :
847 : /* Print information about allocno or only regno (if REG_P) conflicts
848 : to stderr. */
849 : void
850 0 : ira_debug_conflicts (bool reg_p)
851 : {
852 0 : print_conflicts (stderr, reg_p);
853 0 : }
854 :
855 :
856 :
857 : /* Entry function which builds allocno conflicts and allocno copies
858 : and accumulate some allocno info on upper level regions. */
859 : void
860 1504950 : ira_build_conflicts (void)
861 : {
862 1504950 : enum reg_class base;
863 1504950 : ira_allocno_t a;
864 1504950 : ira_allocno_iterator ai;
865 1504950 : HARD_REG_SET temp_hard_reg_set;
866 :
867 1504950 : if (ira_conflicts_p)
868 : {
869 1057059 : ira_conflicts_p = build_conflict_bit_table ();
870 1057059 : if (ira_conflicts_p)
871 : {
872 1057059 : ira_object_t obj;
873 1057059 : ira_object_iterator oi;
874 :
875 1057059 : build_conflicts ();
876 1057059 : ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
877 : /* We need finished conflict table for the subsequent call. */
878 1057059 : if (flag_ira_region == IRA_REGION_ALL
879 1057059 : || flag_ira_region == IRA_REGION_MIXED)
880 1010507 : propagate_copies ();
881 :
882 : /* Now we can free memory for the conflict table (see function
883 : build_object_conflicts for details). */
884 27897265 : FOR_EACH_OBJECT (obj, oi)
885 : {
886 25783147 : if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
887 5019937 : ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
888 : }
889 1057059 : ira_free (conflicts);
890 : }
891 : }
892 1504950 : base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH);
893 1504950 : if (! targetm.class_likely_spilled_p (base))
894 1504950 : CLEAR_HARD_REG_SET (temp_hard_reg_set);
895 : else
896 0 : temp_hard_reg_set = reg_class_contents[base] & ~ira_no_alloc_regs;
897 38438235 : FOR_EACH_ALLOCNO (a, ai)
898 : {
899 36933285 : int i, n = ALLOCNO_NUM_OBJECTS (a);
900 :
901 75187808 : for (i = 0; i < n; i++)
902 : {
903 38254523 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
904 38254523 : rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
905 :
906 : /* For debugging purposes don't put user defined variables in
907 : callee-clobbered registers. However, do allow parameters
908 : in callee-clobbered registers to improve debugging. This
909 : is a bit of a fragile hack. */
910 38254523 : if (optimize == 0
911 12471376 : && REG_USERVAR_P (allocno_reg)
912 38265458 : && ! reg_is_parm_p (allocno_reg))
913 : {
914 10796 : HARD_REG_SET new_conflict_regs = crtl->abi->full_reg_clobbers ();
915 43184 : OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
916 10796 : OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
917 : }
918 :
919 38254523 : if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
920 : {
921 4034494 : HARD_REG_SET new_conflict_regs = ira_need_caller_save_regs (a);
922 4034494 : if (flag_caller_saves)
923 7243818 : new_conflict_regs &= (~savable_regs | temp_hard_reg_set);
924 16137976 : OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
925 4034494 : OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
926 : }
927 :
928 : /* Now we deal with paradoxical subreg cases where certain registers
929 : cannot be accessed in the widest mode. */
930 38254523 : machine_mode outer_mode = ALLOCNO_WMODE (a);
931 38254523 : machine_mode inner_mode = ALLOCNO_MODE (a);
932 38254523 : if (paradoxical_subreg_p (outer_mode, inner_mode))
933 : {
934 646767 : enum reg_class aclass = ALLOCNO_CLASS (a);
935 7226336 : for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
936 : {
937 6579569 : int inner_regno = ira_class_hard_regs[aclass][j];
938 6579569 : int outer_regno = simplify_subreg_regno (inner_regno,
939 : inner_mode, 0,
940 : outer_mode);
941 6579569 : if (outer_regno < 0
942 6579569 : || !in_hard_reg_set_p (reg_class_contents[aclass],
943 : outer_mode, outer_regno))
944 : {
945 3218 : SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
946 : inner_regno);
947 3218 : SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
948 : inner_regno);
949 : }
950 : }
951 : }
952 : }
953 : }
954 1504950 : if (optimize && ira_conflicts_p
955 1057059 : && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
956 39 : print_conflicts (ira_dump_file, false);
957 1504950 : }
|
