1/* IRA conflict builder.
2 Copyright (C) 2006-2025 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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. */
46static 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. */
60static void
61record_object_conflict (ira_object_t obj1, ira_object_t obj2)
62{
63 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
64 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
65 int w1 = OBJECT_SUBWORD (obj1);
66 int w2 = OBJECT_SUBWORD (obj2);
67 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 if (w1 == w2 && w1 > 0)
74 {
75 obj1 = ALLOCNO_OBJECT (a1, 0);
76 obj2 = ALLOCNO_OBJECT (a2, 0);
77 }
78 id1 = OBJECT_CONFLICT_ID (obj1);
79 id2 = OBJECT_CONFLICT_ID (obj2);
80
81 SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
82 OBJECT_MAX (obj1));
83 SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
84 OBJECT_MAX (obj2));
85}
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. */
90static bool
91build_conflict_bit_table (void)
92{
93 int i;
94 unsigned int j;
95 enum reg_class aclass;
96 int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
97 live_range_t r;
98 ira_allocno_t allocno;
99 ira_allocno_iterator ai;
100 sparseset objects_live;
101 ira_object_t obj;
102 ira_allocno_object_iterator aoi;
103
104 allocated_words_num = 0;
105 FOR_EACH_ALLOCNO (allocno, ai)
106 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
107 {
108 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
109 continue;
110 conflict_bit_vec_words_num
111 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
112 / IRA_INT_BITS);
113 allocated_words_num += conflict_bit_vec_words_num;
114 if ((uint64_t) allocated_words_num * sizeof (IRA_INT_TYPE)
115 > (uint64_t) param_ira_max_conflict_table_size * 1024 * 1024)
116 {
117 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
118 fprintf (stream: ira_dump_file,
119 format: "+++Conflict table will be too big(>%dMB) "
120 "-- don't use it\n",
121 param_ira_max_conflict_table_size);
122 return false;
123 }
124 }
125
126 conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
127 * ira_objects_num);
128 allocated_words_num = 0;
129 FOR_EACH_ALLOCNO (allocno, ai)
130 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
131 {
132 int id = OBJECT_CONFLICT_ID (obj);
133 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
134 {
135 conflicts[id] = NULL;
136 continue;
137 }
138 conflict_bit_vec_words_num
139 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
140 / IRA_INT_BITS);
141 allocated_words_num += conflict_bit_vec_words_num;
142 conflicts[id]
143 = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
144 * conflict_bit_vec_words_num);
145 memset (s: conflicts[id], c: 0,
146 n: sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
147 }
148
149 object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
150 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
151 fprintf (stream: ira_dump_file,
152 format: "+++Allocating " HOST_SIZE_T_PRINT_UNSIGNED
153 " bytes for conflict table (uncompressed size "
154 HOST_SIZE_T_PRINT_UNSIGNED ")\n",
155 (fmt_size_t) (sizeof (IRA_INT_TYPE) * allocated_words_num),
156 (fmt_size_t) (sizeof (IRA_INT_TYPE) * object_set_words
157 * ira_objects_num));
158
159 objects_live = sparseset_alloc (n_elms: ira_objects_num);
160 for (i = 0; i < ira_max_point; i++)
161 {
162 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
163 {
164 ira_object_t obj = r->object;
165 ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
166 int id = OBJECT_CONFLICT_ID (obj);
167
168 gcc_assert (id < ira_objects_num);
169
170 aclass = ALLOCNO_CLASS (allocno);
171 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
172 {
173 ira_object_t live_obj = ira_object_id_map[j];
174 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
175 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
176
177 if (ira_reg_classes_intersect_p[aclass][live_aclass]
178 /* Don't set up conflict for the allocno with itself. */
179 && live_a != allocno)
180 {
181 record_object_conflict (obj1: obj, obj2: live_obj);
182 }
183 }
184 sparseset_set_bit (s: objects_live, e: id);
185 }
186
187 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
188 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
189 }
190 sparseset_free (objects_live);
191 return true;
192}
193
194/* Return true iff allocnos A1 and A2 cannot be allocated to the same
195 register due to conflicts. */
196
197static bool
198allocnos_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 ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
204 ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
205
206 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. */
216static rtx
217go_through_subreg (rtx x, int *offset)
218{
219 rtx reg;
220
221 *offset = 0;
222 if (REG_P (x))
223 return x;
224 ira_assert (GET_CODE (x) == SUBREG);
225 reg = SUBREG_REG (x);
226 ira_assert (REG_P (reg));
227 if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
228 *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
229 SUBREG_BYTE (x), GET_MODE (x));
230 /* The offset is always 0 for paradoxical subregs. */
231 else if (!can_div_trunc_p (SUBREG_BYTE (x),
232 REGMODE_NATURAL_SIZE (GET_MODE (reg)), quotient: 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
242static int
243get_freq_for_shuffle_copy (int freq)
244{
245 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. */
257static bool
258process_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 int allocno_preferenced_hard_regno, index, offset1, offset2;
262 int cost, conflict_cost, move_cost;
263 bool only_regs_p;
264 ira_allocno_t a;
265 reg_class_t rclass, aclass;
266 machine_mode mode;
267 ira_copy_t cp;
268
269 gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
270 only_regs_p = REG_P (reg1) && REG_P (reg2);
271 reg1 = go_through_subreg (x: reg1, offset: &offset1);
272 reg2 = go_through_subreg (x: reg2, offset: &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 if (HARD_REGISTER_P (reg1))
276 {
277 if (HARD_REGISTER_P (reg2))
278 return false;
279 allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
280 a = ira_curr_regno_allocno_map[REGNO (reg2)];
281 }
282 else if (HARD_REGISTER_P (reg2))
283 {
284 allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
285 a = ira_curr_regno_allocno_map[REGNO (reg1)];
286 }
287 else
288 {
289 ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
290 ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
291
292 if (!allocnos_conflict_for_copy_p (a1, a2)
293 && offset1 == offset2
294 && ordered_p (a: GET_MODE_PRECISION (ALLOCNO_MODE (a1)),
295 b: GET_MODE_PRECISION (ALLOCNO_MODE (a2))))
296 {
297 cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
298 ira_curr_loop_tree_node);
299 bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
300 return true;
301 }
302 else
303 return false;
304 }
305
306 if (! IN_RANGE (allocno_preferenced_hard_regno,
307 0, FIRST_PSEUDO_REGISTER - 1))
308 /* Cannot be tied. */
309 return false;
310 rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
311 mode = ALLOCNO_MODE (a);
312 aclass = ALLOCNO_CLASS (a);
313 if (only_regs_p && insn != NULL_RTX
314 && 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 index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
318 if (index < 0)
319 /* Cannot be tied. It is not in the allocno class. */
320 return false;
321 ira_init_register_move_cost_if_necessary (mode);
322 if (HARD_REGISTER_P (reg1))
323 move_cost = ira_register_move_cost[mode][aclass][rclass];
324 else
325 move_cost = ira_register_move_cost[mode][rclass][aclass];
326
327 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 gcc_assert (constraint_p);
339 int reduced_freq = get_freq_for_shuffle_copy (freq);
340 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 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 cost = move_cost * freq;
363 conflict_cost = move_cost * reduced_freq;
364 }
365 }
366 else
367 cost = conflict_cost = move_cost * freq;
368
369 do
370 {
371 ira_allocate_and_set_costs
372 (vec: &ALLOCNO_HARD_REG_COSTS (a), aclass,
373 ALLOCNO_CLASS_COST (a));
374 ira_allocate_and_set_costs
375 (vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, val: 0);
376 ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
377 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= conflict_cost;
378 if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
379 ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
380 ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq);
381 a = ira_parent_or_cap_allocno (a);
382 }
383 while (a != NULL);
384 return true;
385}
386
387/* Return true if output operand OUTPUT and input operand INPUT of
388 INSN can use the same register class for at least one alternative.
389 INSN is already described in recog_data and recog_op_alt. */
390static bool
391can_use_same_reg_p (rtx_insn *insn, int output, int input)
392{
393 alternative_mask preferred = get_preferred_alternatives (insn);
394 for (int nalt = 0; nalt < recog_data.n_alternatives; nalt++)
395 {
396 if (!TEST_BIT (preferred, nalt))
397 continue;
398
399 const operand_alternative *op_alt
400 = &recog_op_alt[nalt * recog_data.n_operands];
401 if (op_alt[input].matches == output)
402 return true;
403
404 if (op_alt[output].earlyclobber)
405 continue;
406
407 if (ira_reg_class_intersect[op_alt[input].cl][op_alt[output].cl]
408 != NO_REGS)
409 return true;
410 }
411 return false;
412}
413
414/* Process all of the output registers of the current insn (INSN) which
415 are not bound (BOUND_P) and the input register REG (its operand number
416 OP_NUM) which dies in the insn as if there were a move insn between
417 them with frequency FREQ. */
418static void
419process_reg_shuffles (rtx_insn *insn, rtx reg, int op_num, int freq,
420 bool *bound_p)
421{
422 int i;
423 rtx another_reg;
424
425 gcc_assert (REG_SUBREG_P (reg));
426 for (i = 0; i < recog_data.n_operands; i++)
427 {
428 another_reg = recog_data.operand[i];
429
430 if (!REG_SUBREG_P (another_reg) || op_num == i
431 || recog_data.operand_type[i] != OP_OUT
432 || bound_p[i]
433 || (!can_use_same_reg_p (insn, output: i, input: op_num)
434 && (recog_data.constraints[op_num][0] != '%'
435 || !can_use_same_reg_p (insn, output: i, input: op_num + 1))
436 && (op_num == 0
437 || recog_data.constraints[op_num - 1][0] != '%'
438 || !can_use_same_reg_p (insn, output: i, input: op_num - 1))))
439 continue;
440
441 process_regs_for_copy (reg1: reg, reg2: another_reg, constraint_p: false, NULL, freq);
442 }
443}
444
445/* Process INSN and create allocno copies if necessary. For example,
446 it might be because INSN is a pseudo-register move or INSN is two
447 operand insn. */
448static void
449add_insn_allocno_copies (rtx_insn *insn)
450{
451 rtx set, operand, dup;
452 bool bound_p[MAX_RECOG_OPERANDS];
453 int i, n, freq;
454 alternative_mask alts;
455
456 freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
457 if (freq == 0)
458 freq = 1;
459 if ((set = single_set (insn)) != NULL_RTX
460 && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
461 && ! side_effects_p (set)
462 && find_reg_note (insn, REG_DEAD,
463 REG_P (SET_SRC (set))
464 ? SET_SRC (set)
465 : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
466 {
467 process_regs_for_copy (SET_SRC (set), SET_DEST (set),
468 constraint_p: false, insn, freq);
469 return;
470 }
471 /* Fast check of possibility of constraint or shuffle copies. If
472 there are no dead registers, there will be no such copies. */
473 if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
474 return;
475 alts = ira_setup_alts (insn);
476 for (i = 0; i < recog_data.n_operands; i++)
477 bound_p[i] = false;
478 for (i = 0; i < recog_data.n_operands; i++)
479 {
480 operand = recog_data.operand[i];
481 if (! REG_SUBREG_P (operand))
482 continue;
483 bool single_input_op_has_cstr_p;
484 if ((n = ira_get_dup_out_num (i, alts, single_input_op_has_cstr_p)) >= 0)
485 {
486 bound_p[n] = true;
487 dup = recog_data.operand[n];
488 if (REG_SUBREG_P (dup)
489 && find_reg_note (insn, REG_DEAD,
490 REG_P (operand)
491 ? operand
492 : SUBREG_REG (operand)) != NULL_RTX)
493 process_regs_for_copy (reg1: operand, reg2: dup, constraint_p: true, NULL, freq,
494 single_input_op_has_cstr_p);
495 }
496 }
497 for (i = 0; i < recog_data.n_operands; i++)
498 {
499 operand = recog_data.operand[i];
500 if (REG_SUBREG_P (operand)
501 && find_reg_note (insn, REG_DEAD,
502 REG_P (operand)
503 ? operand : SUBREG_REG (operand)) != NULL_RTX)
504 {
505 /* If an operand dies, prefer its hard register for the output
506 operands by decreasing the hard register cost or creating
507 the corresponding allocno copies. The cost will not
508 correspond to a real move insn cost, so make the frequency
509 smaller. */
510 int new_freq = get_freq_for_shuffle_copy (freq);
511 process_reg_shuffles (insn, reg: operand, op_num: i, freq: new_freq, bound_p);
512 }
513 }
514}
515
516/* Add copies originated from BB given by LOOP_TREE_NODE. */
517static void
518add_copies (ira_loop_tree_node_t loop_tree_node)
519{
520 basic_block bb;
521 rtx_insn *insn;
522
523 bb = loop_tree_node->bb;
524 if (bb == NULL)
525 return;
526 FOR_BB_INSNS (bb, insn)
527 if (NONDEBUG_INSN_P (insn))
528 add_insn_allocno_copies (insn);
529}
530
531/* Propagate copies the corresponding allocnos on upper loop tree
532 level. */
533static void
534propagate_copies (void)
535{
536 ira_copy_t cp;
537 ira_copy_iterator ci;
538 ira_allocno_t a1, a2, parent_a1, parent_a2;
539
540 FOR_EACH_COPY (cp, ci)
541 {
542 a1 = cp->first;
543 a2 = cp->second;
544 if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
545 continue;
546 ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
547 parent_a1 = ira_parent_or_cap_allocno (a1);
548 parent_a2 = ira_parent_or_cap_allocno (a2);
549 ira_assert (parent_a1 != NULL && parent_a2 != NULL);
550 if (! allocnos_conflict_for_copy_p (a1: parent_a1, a2: parent_a2))
551 ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
552 cp->constraint_p, cp->insn, cp->loop_tree_node);
553 }
554}
555
556/* Array used to collect all conflict allocnos for given allocno. */
557static ira_object_t *collected_conflict_objects;
558
559/* Build conflict vectors or bit conflict vectors (whatever is more
560 profitable) for object OBJ from the conflict table. */
561static void
562build_object_conflicts (ira_object_t obj)
563{
564 int i, px, parent_num;
565 ira_allocno_t parent_a, another_parent_a;
566 ira_object_t parent_obj;
567 ira_allocno_t a = OBJECT_ALLOCNO (obj);
568 IRA_INT_TYPE *object_conflicts;
569 minmax_set_iterator asi;
570 int parent_min, parent_max ATTRIBUTE_UNUSED;
571
572 object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
573 px = 0;
574 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
575 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
576 {
577 ira_object_t another_obj = ira_object_id_map[i];
578 ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
579
580 ira_assert (ira_reg_classes_intersect_p
581 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
582 collected_conflict_objects[px++] = another_obj;
583 }
584 if (ira_conflict_vector_profitable_p (obj, px))
585 {
586 ira_object_t *vec;
587 ira_allocate_conflict_vec (obj, px);
588 vec = OBJECT_CONFLICT_VEC (obj);
589 memcpy (dest: vec, src: collected_conflict_objects, n: sizeof (ira_object_t) * px);
590 vec[px] = NULL;
591 OBJECT_NUM_CONFLICTS (obj) = px;
592 }
593 else
594 {
595 int conflict_bit_vec_words_num;
596
597 OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
598 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
599 conflict_bit_vec_words_num = 0;
600 else
601 conflict_bit_vec_words_num
602 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
603 / IRA_INT_BITS);
604 OBJECT_CONFLICT_ARRAY_SIZE (obj)
605 = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
606 }
607
608 parent_a = ira_parent_or_cap_allocno (a);
609 if (parent_a == NULL)
610 return;
611 ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
612 ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
613 parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
614 parent_num = OBJECT_CONFLICT_ID (parent_obj);
615 parent_min = OBJECT_MIN (parent_obj);
616 parent_max = OBJECT_MAX (parent_obj);
617 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
618 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
619 {
620 ira_object_t another_obj = ira_object_id_map[i];
621 ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
622 int another_word = OBJECT_SUBWORD (another_obj);
623
624 ira_assert (ira_reg_classes_intersect_p
625 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
626
627 another_parent_a = ira_parent_or_cap_allocno (another_a);
628 if (another_parent_a == NULL)
629 continue;
630 ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
631 ira_assert (ALLOCNO_CLASS (another_a)
632 == ALLOCNO_CLASS (another_parent_a));
633 ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
634 == ALLOCNO_NUM_OBJECTS (another_parent_a));
635 SET_MINMAX_SET_BIT (conflicts[parent_num],
636 OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
637 another_word)),
638 parent_min, parent_max);
639 }
640}
641
642/* Build conflict vectors or bit conflict vectors (whatever is more
643 profitable) of all allocnos from the conflict table. */
644static void
645build_conflicts (void)
646{
647 int i;
648 ira_allocno_t a, cap;
649
650 collected_conflict_objects
651 = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
652 * ira_objects_num);
653 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
654 for (a = ira_regno_allocno_map[i];
655 a != NULL;
656 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
657 {
658 int j, nregs = ALLOCNO_NUM_OBJECTS (a);
659 for (j = 0; j < nregs; j++)
660 {
661 ira_object_t obj = ALLOCNO_OBJECT (a, j);
662 build_object_conflicts (obj);
663 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
664 {
665 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
666 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
667 build_object_conflicts (obj: cap_obj);
668 }
669 }
670 }
671 ira_free (addr: collected_conflict_objects);
672}
673
674
675
676/* Print hard reg set SET with TITLE to FILE. */
677static void
678print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
679{
680 int i, start, end;
681
682 fputs (s: title, stream: file);
683 for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
684 {
685 bool reg_included = TEST_HARD_REG_BIT (set, bit: i);
686
687 if (reg_included)
688 {
689 if (start == -1)
690 start = i;
691 end = i;
692 }
693 if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
694 {
695 if (start == end)
696 fprintf (stream: file, format: " %d", start);
697 else if (start == end + 1)
698 fprintf (stream: file, format: " %d %d", start, end);
699 else
700 fprintf (stream: file, format: " %d-%d", start, end);
701 start = -1;
702 }
703 }
704 putc (c: '\n', stream: file);
705}
706
707static void
708print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
709{
710 HARD_REG_SET conflicting_hard_regs;
711 basic_block bb;
712 int n, i;
713
714 if (reg_p)
715 fprintf (stream: file, format: ";; r%d", ALLOCNO_REGNO (a));
716 else
717 {
718 fprintf (stream: file, format: ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
719 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
720 fprintf (stream: file, format: "b%d", bb->index);
721 else
722 fprintf (stream: file, format: "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
723 putc (c: ')', stream: file);
724 }
725
726 fputs (s: " conflicts:", stream: file);
727 n = ALLOCNO_NUM_OBJECTS (a);
728 for (i = 0; i < n; i++)
729 {
730 ira_object_t obj = ALLOCNO_OBJECT (a, i);
731 ira_object_t conflict_obj;
732 ira_object_conflict_iterator oci;
733
734 if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
735 {
736 fprintf (stream: file, format: "\n;; total conflict hard regs:\n");
737 fprintf (stream: file, format: ";; conflict hard regs:\n\n");
738 continue;
739 }
740
741 if (n > 1)
742 fprintf (stream: file, format: "\n;; subobject %d:", i);
743 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
744 {
745 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
746 if (reg_p)
747 fprintf (stream: file, format: " r%d,", ALLOCNO_REGNO (conflict_a));
748 else
749 {
750 fprintf (stream: file, format: " a%d(r%d", ALLOCNO_NUM (conflict_a),
751 ALLOCNO_REGNO (conflict_a));
752 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
753 fprintf (stream: file, format: ",w%d", OBJECT_SUBWORD (conflict_obj));
754 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
755 fprintf (stream: file, format: ",b%d", bb->index);
756 else
757 fprintf (stream: file, format: ",l%d",
758 ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
759 putc (c: ')', stream: file);
760 }
761 }
762 conflicting_hard_regs = (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
763 & ~ira_no_alloc_regs
764 & reg_class_contents[ALLOCNO_CLASS (a)]);
765 print_hard_reg_set (file, title: "\n;; total conflict hard regs:",
766 set: conflicting_hard_regs);
767
768 conflicting_hard_regs = (OBJECT_CONFLICT_HARD_REGS (obj)
769 & ~ira_no_alloc_regs
770 & reg_class_contents[ALLOCNO_CLASS (a)]);
771 print_hard_reg_set (file, title: ";; conflict hard regs:",
772 set: conflicting_hard_regs);
773 putc (c: '\n', stream: file);
774 }
775
776}
777
778/* Print information about allocno or only regno (if REG_P) conflicts
779 to FILE. */
780static void
781print_conflicts (FILE *file, bool reg_p)
782{
783 ira_allocno_t a;
784 ira_allocno_iterator ai;
785
786 FOR_EACH_ALLOCNO (a, ai)
787 print_allocno_conflicts (file, reg_p, a);
788 putc (c: '\n', stream: file);
789}
790
791/* Print information about allocno or only regno (if REG_P) conflicts
792 to stderr. */
793void
794ira_debug_conflicts (bool reg_p)
795{
796 print_conflicts (stderr, reg_p);
797}
798
799
800
801/* Entry function which builds allocno conflicts and allocno copies
802 and accumulate some allocno info on upper level regions. */
803void
804ira_build_conflicts (void)
805{
806 enum reg_class base;
807 ira_allocno_t a;
808 ira_allocno_iterator ai;
809 HARD_REG_SET temp_hard_reg_set;
810
811 if (ira_conflicts_p)
812 {
813 ira_conflicts_p = build_conflict_bit_table ();
814 if (ira_conflicts_p)
815 {
816 ira_object_t obj;
817 ira_object_iterator oi;
818
819 build_conflicts ();
820 ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
821 /* We need finished conflict table for the subsequent call. */
822 if (flag_ira_region == IRA_REGION_ALL
823 || flag_ira_region == IRA_REGION_MIXED)
824 propagate_copies ();
825
826 /* Now we can free memory for the conflict table (see function
827 build_object_conflicts for details). */
828 FOR_EACH_OBJECT (obj, oi)
829 {
830 if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
831 ira_free (addr: conflicts[OBJECT_CONFLICT_ID (obj)]);
832 }
833 ira_free (addr: conflicts);
834 }
835 }
836 base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, outer_code: ADDRESS, index_code: SCRATCH);
837 if (! targetm.class_likely_spilled_p (base))
838 CLEAR_HARD_REG_SET (set&: temp_hard_reg_set);
839 else
840 temp_hard_reg_set = reg_class_contents[base] & ~ira_no_alloc_regs;
841 FOR_EACH_ALLOCNO (a, ai)
842 {
843 int i, n = ALLOCNO_NUM_OBJECTS (a);
844
845 for (i = 0; i < n; i++)
846 {
847 ira_object_t obj = ALLOCNO_OBJECT (a, i);
848 rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
849
850 /* For debugging purposes don't put user defined variables in
851 callee-clobbered registers. However, do allow parameters
852 in callee-clobbered registers to improve debugging. This
853 is a bit of a fragile hack. */
854 if (optimize == 0
855 && REG_USERVAR_P (allocno_reg)
856 && ! reg_is_parm_p (allocno_reg))
857 {
858 HARD_REG_SET new_conflict_regs = crtl->abi->full_reg_clobbers ();
859 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
860 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
861 }
862
863 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
864 {
865 HARD_REG_SET new_conflict_regs = ira_need_caller_save_regs (a);
866 if (flag_caller_saves)
867 new_conflict_regs &= (~savable_regs | temp_hard_reg_set);
868 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
869 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
870 }
871
872 /* Now we deal with paradoxical subreg cases where certain registers
873 cannot be accessed in the widest mode. */
874 machine_mode outer_mode = ALLOCNO_WMODE (a);
875 machine_mode inner_mode = ALLOCNO_MODE (a);
876 if (paradoxical_subreg_p (outermode: outer_mode, innermode: inner_mode))
877 {
878 enum reg_class aclass = ALLOCNO_CLASS (a);
879 for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
880 {
881 int inner_regno = ira_class_hard_regs[aclass][j];
882 int outer_regno = simplify_subreg_regno (inner_regno,
883 inner_mode, 0,
884 outer_mode);
885 if (outer_regno < 0
886 || !in_hard_reg_set_p (reg_class_contents[aclass],
887 mode: outer_mode, regno: outer_regno))
888 {
889 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
890 bit: inner_regno);
891 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
892 bit: inner_regno);
893 }
894 }
895 }
896 }
897 }
898 if (optimize && ira_conflicts_p
899 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
900 print_conflicts (file: ira_dump_file, reg_p: false);
901}
902

source code of gcc/ira-conflicts.cc