1/* IRA conflict builder.
2 Copyright (C) 2006-2023 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
119 (stream: ira_dump_file,
120 format: "+++Conflict table will be too big(>%dMB) -- 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
152 (stream: ira_dump_file,
153 format: "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
154 (long) allocated_words_num * sizeof (IRA_INT_TYPE),
155 (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE));
156
157 objects_live = sparseset_alloc (n_elms: ira_objects_num);
158 for (i = 0; i < ira_max_point; i++)
159 {
160 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
161 {
162 ira_object_t obj = r->object;
163 ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
164 int id = OBJECT_CONFLICT_ID (obj);
165
166 gcc_assert (id < ira_objects_num);
167
168 aclass = ALLOCNO_CLASS (allocno);
169 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
170 {
171 ira_object_t live_obj = ira_object_id_map[j];
172 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
173 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
174
175 if (ira_reg_classes_intersect_p[aclass][live_aclass]
176 /* Don't set up conflict for the allocno with itself. */
177 && live_a != allocno)
178 {
179 record_object_conflict (obj1: obj, obj2: live_obj);
180 }
181 }
182 sparseset_set_bit (s: objects_live, e: id);
183 }
184
185 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
186 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
187 }
188 sparseset_free (objects_live);
189 return true;
190}
191
192/* Return true iff allocnos A1 and A2 cannot be allocated to the same
193 register due to conflicts. */
194
195static bool
196allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
197{
198 /* Due to the fact that we canonicalize conflicts (see
199 record_object_conflict), we only need to test for conflicts of
200 the lowest order words. */
201 ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
202 ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
203
204 return OBJECTS_CONFLICT_P (obj1, obj2);
205}
206
207/* Check that X is REG or SUBREG of REG. */
208#define REG_SUBREG_P(x) \
209 (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
210
211/* Return X if X is a REG, otherwise it should be SUBREG of REG and
212 the function returns the reg in this case. *OFFSET will be set to
213 0 in the first case or the regno offset in the first case. */
214static rtx
215go_through_subreg (rtx x, int *offset)
216{
217 rtx reg;
218
219 *offset = 0;
220 if (REG_P (x))
221 return x;
222 ira_assert (GET_CODE (x) == SUBREG);
223 reg = SUBREG_REG (x);
224 ira_assert (REG_P (reg));
225 if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
226 *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
227 SUBREG_BYTE (x), GET_MODE (x));
228 else if (!can_div_trunc_p (SUBREG_BYTE (x),
229 REGMODE_NATURAL_SIZE (GET_MODE (x)), quotient: offset))
230 /* Checked by validate_subreg. We must know at compile time which
231 inner hard registers are being accessed. */
232 gcc_unreachable ();
233 return reg;
234}
235
236/* Return the recomputed frequency for this shuffle copy or its similar
237 case, since it's not for a real move insn, make it smaller. */
238
239static int
240get_freq_for_shuffle_copy (int freq)
241{
242 return freq < 8 ? 1 : freq / 8;
243}
244
245/* Process registers REG1 and REG2 in move INSN with execution
246 frequency FREQ. The function also processes the registers in a
247 potential move insn (INSN == NULL in this case) with frequency
248 FREQ. The function can modify hard register costs of the
249 corresponding allocnos or create a copy involving the corresponding
250 allocnos. The function does nothing if the both registers are hard
251 registers. When nothing is changed, the function returns FALSE.
252 SINGLE_INPUT_OP_HAS_CSTR_P is only meaningful when constraint_p
253 is true, see function ira_get_dup_out_num for its meaning. */
254static bool
255process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p, rtx_insn *insn,
256 int freq, bool single_input_op_has_cstr_p = true)
257{
258 int allocno_preferenced_hard_regno, index, offset1, offset2;
259 int cost, conflict_cost, move_cost;
260 bool only_regs_p;
261 ira_allocno_t a;
262 reg_class_t rclass, aclass;
263 machine_mode mode;
264 ira_copy_t cp;
265
266 gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
267 only_regs_p = REG_P (reg1) && REG_P (reg2);
268 reg1 = go_through_subreg (x: reg1, offset: &offset1);
269 reg2 = go_through_subreg (x: reg2, offset: &offset2);
270 /* Set up hard regno preferenced by allocno. If allocno gets the
271 hard regno the copy (or potential move) insn will be removed. */
272 if (HARD_REGISTER_P (reg1))
273 {
274 if (HARD_REGISTER_P (reg2))
275 return false;
276 allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
277 a = ira_curr_regno_allocno_map[REGNO (reg2)];
278 }
279 else if (HARD_REGISTER_P (reg2))
280 {
281 allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
282 a = ira_curr_regno_allocno_map[REGNO (reg1)];
283 }
284 else
285 {
286 ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
287 ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
288
289 if (!allocnos_conflict_for_copy_p (a1, a2)
290 && offset1 == offset2
291 && ordered_p (a: GET_MODE_PRECISION (ALLOCNO_MODE (a1)),
292 b: GET_MODE_PRECISION (ALLOCNO_MODE (a2))))
293 {
294 cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
295 ira_curr_loop_tree_node);
296 bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
297 return true;
298 }
299 else
300 return false;
301 }
302
303 if (! IN_RANGE (allocno_preferenced_hard_regno,
304 0, FIRST_PSEUDO_REGISTER - 1))
305 /* Cannot be tied. */
306 return false;
307 rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
308 mode = ALLOCNO_MODE (a);
309 aclass = ALLOCNO_CLASS (a);
310 if (only_regs_p && insn != NULL_RTX
311 && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
312 /* It is already taken into account in ira-costs.cc. */
313 return false;
314 index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
315 if (index < 0)
316 /* Cannot be tied. It is not in the allocno class. */
317 return false;
318 ira_init_register_move_cost_if_necessary (mode);
319 if (HARD_REGISTER_P (reg1))
320 move_cost = ira_register_move_cost[mode][aclass][rclass];
321 else
322 move_cost = ira_register_move_cost[mode][rclass][aclass];
323
324 if (!single_input_op_has_cstr_p)
325 {
326 /* When this is a constraint copy and the matching constraint
327 doesn't only exist for this given operand but also for some
328 other operand(s), it means saving the possible move cost does
329 NOT need to require reg1 and reg2 to use the same hardware
330 register, so this hardware preference isn't required to be
331 fixed. To avoid it to over prefer this hardware register,
332 and over disparage this hardware register on conflicted
333 objects, we need some cost tweaking here, similar to what
334 we do for shuffle copy. */
335 gcc_assert (constraint_p);
336 int reduced_freq = get_freq_for_shuffle_copy (freq);
337 if (HARD_REGISTER_P (reg1))
338 /* For reg2 = opcode(reg1, reg3 ...), assume that reg3 is a
339 pseudo register which has matching constraint on reg2,
340 even if reg2 isn't assigned by reg1, it's still possible
341 not to have register moves if reg2 and reg3 use the same
342 hardware register. So to avoid the allocation to over
343 prefer reg1, we can just take it as a shuffle copy. */
344 cost = conflict_cost = move_cost * reduced_freq;
345 else
346 {
347 /* For reg1 = opcode(reg2, reg3 ...), assume that reg3 is a
348 pseudo register which has matching constraint on reg2,
349 to save the register move, it's better to assign reg1
350 to either of reg2 and reg3 (or one of other pseudos like
351 reg3), it's reasonable to use freq for the cost. But
352 for conflict_cost, since reg2 and reg3 conflicts with
353 each other, both of them has the chance to be assigned
354 by reg1, assume reg3 has one copy which also conflicts
355 with reg2, we shouldn't make it less preferred on reg1
356 since reg3 has the same chance to be assigned by reg1.
357 So it adjusts the conflic_cost to make it same as what
358 we use for shuffle copy. */
359 cost = move_cost * freq;
360 conflict_cost = move_cost * reduced_freq;
361 }
362 }
363 else
364 cost = conflict_cost = move_cost * freq;
365
366 do
367 {
368 ira_allocate_and_set_costs
369 (vec: &ALLOCNO_HARD_REG_COSTS (a), aclass,
370 ALLOCNO_CLASS_COST (a));
371 ira_allocate_and_set_costs
372 (vec: &ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, val: 0);
373 ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
374 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= conflict_cost;
375 if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
376 ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
377 ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq);
378 a = ira_parent_or_cap_allocno (a);
379 }
380 while (a != NULL);
381 return true;
382}
383
384/* Return true if output operand OUTPUT and input operand INPUT of
385 INSN can use the same register class for at least one alternative.
386 INSN is already described in recog_data and recog_op_alt. */
387static bool
388can_use_same_reg_p (rtx_insn *insn, int output, int input)
389{
390 alternative_mask preferred = get_preferred_alternatives (insn);
391 for (int nalt = 0; nalt < recog_data.n_alternatives; nalt++)
392 {
393 if (!TEST_BIT (preferred, nalt))
394 continue;
395
396 const operand_alternative *op_alt
397 = &recog_op_alt[nalt * recog_data.n_operands];
398 if (op_alt[input].matches == output)
399 return true;
400
401 if (op_alt[output].earlyclobber)
402 continue;
403
404 if (ira_reg_class_intersect[op_alt[input].cl][op_alt[output].cl]
405 != NO_REGS)
406 return true;
407 }
408 return false;
409}
410
411/* Process all of the output registers of the current insn (INSN) which
412 are not bound (BOUND_P) and the input register REG (its operand number
413 OP_NUM) which dies in the insn as if there were a move insn between
414 them with frequency FREQ. */
415static void
416process_reg_shuffles (rtx_insn *insn, rtx reg, int op_num, int freq,
417 bool *bound_p)
418{
419 int i;
420 rtx another_reg;
421
422 gcc_assert (REG_SUBREG_P (reg));
423 for (i = 0; i < recog_data.n_operands; i++)
424 {
425 another_reg = recog_data.operand[i];
426
427 if (!REG_SUBREG_P (another_reg) || op_num == i
428 || recog_data.operand_type[i] != OP_OUT
429 || bound_p[i]
430 || (!can_use_same_reg_p (insn, output: i, input: op_num)
431 && (recog_data.constraints[op_num][0] != '%'
432 || !can_use_same_reg_p (insn, output: i, input: op_num + 1))
433 && (op_num == 0
434 || recog_data.constraints[op_num - 1][0] != '%'
435 || !can_use_same_reg_p (insn, output: i, input: op_num - 1))))
436 continue;
437
438 process_regs_for_copy (reg1: reg, reg2: another_reg, constraint_p: false, NULL, freq);
439 }
440}
441
442/* Process INSN and create allocno copies if necessary. For example,
443 it might be because INSN is a pseudo-register move or INSN is two
444 operand insn. */
445static void
446add_insn_allocno_copies (rtx_insn *insn)
447{
448 rtx set, operand, dup;
449 bool bound_p[MAX_RECOG_OPERANDS];
450 int i, n, freq;
451 alternative_mask alts;
452
453 freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
454 if (freq == 0)
455 freq = 1;
456 if ((set = single_set (insn)) != NULL_RTX
457 && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
458 && ! side_effects_p (set)
459 && find_reg_note (insn, REG_DEAD,
460 REG_P (SET_SRC (set))
461 ? SET_SRC (set)
462 : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
463 {
464 process_regs_for_copy (SET_SRC (set), SET_DEST (set),
465 constraint_p: false, insn, freq);
466 return;
467 }
468 /* Fast check of possibility of constraint or shuffle copies. If
469 there are no dead registers, there will be no such copies. */
470 if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
471 return;
472 alts = ira_setup_alts (insn);
473 for (i = 0; i < recog_data.n_operands; i++)
474 bound_p[i] = false;
475 for (i = 0; i < recog_data.n_operands; i++)
476 {
477 operand = recog_data.operand[i];
478 if (! REG_SUBREG_P (operand))
479 continue;
480 bool single_input_op_has_cstr_p;
481 if ((n = ira_get_dup_out_num (i, alts, single_input_op_has_cstr_p)) >= 0)
482 {
483 bound_p[n] = true;
484 dup = recog_data.operand[n];
485 if (REG_SUBREG_P (dup)
486 && find_reg_note (insn, REG_DEAD,
487 REG_P (operand)
488 ? operand
489 : SUBREG_REG (operand)) != NULL_RTX)
490 process_regs_for_copy (reg1: operand, reg2: dup, constraint_p: true, NULL, freq,
491 single_input_op_has_cstr_p);
492 }
493 }
494 for (i = 0; i < recog_data.n_operands; i++)
495 {
496 operand = recog_data.operand[i];
497 if (REG_SUBREG_P (operand)
498 && find_reg_note (insn, REG_DEAD,
499 REG_P (operand)
500 ? operand : SUBREG_REG (operand)) != NULL_RTX)
501 {
502 /* If an operand dies, prefer its hard register for the output
503 operands by decreasing the hard register cost or creating
504 the corresponding allocno copies. The cost will not
505 correspond to a real move insn cost, so make the frequency
506 smaller. */
507 int new_freq = get_freq_for_shuffle_copy (freq);
508 process_reg_shuffles (insn, reg: operand, op_num: i, freq: new_freq, bound_p);
509 }
510 }
511}
512
513/* Add copies originated from BB given by LOOP_TREE_NODE. */
514static void
515add_copies (ira_loop_tree_node_t loop_tree_node)
516{
517 basic_block bb;
518 rtx_insn *insn;
519
520 bb = loop_tree_node->bb;
521 if (bb == NULL)
522 return;
523 FOR_BB_INSNS (bb, insn)
524 if (NONDEBUG_INSN_P (insn))
525 add_insn_allocno_copies (insn);
526}
527
528/* Propagate copies the corresponding allocnos on upper loop tree
529 level. */
530static void
531propagate_copies (void)
532{
533 ira_copy_t cp;
534 ira_copy_iterator ci;
535 ira_allocno_t a1, a2, parent_a1, parent_a2;
536
537 FOR_EACH_COPY (cp, ci)
538 {
539 a1 = cp->first;
540 a2 = cp->second;
541 if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
542 continue;
543 ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
544 parent_a1 = ira_parent_or_cap_allocno (a1);
545 parent_a2 = ira_parent_or_cap_allocno (a2);
546 ira_assert (parent_a1 != NULL && parent_a2 != NULL);
547 if (! allocnos_conflict_for_copy_p (a1: parent_a1, a2: parent_a2))
548 ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
549 cp->constraint_p, cp->insn, cp->loop_tree_node);
550 }
551}
552
553/* Array used to collect all conflict allocnos for given allocno. */
554static ira_object_t *collected_conflict_objects;
555
556/* Build conflict vectors or bit conflict vectors (whatever is more
557 profitable) for object OBJ from the conflict table. */
558static void
559build_object_conflicts (ira_object_t obj)
560{
561 int i, px, parent_num;
562 ira_allocno_t parent_a, another_parent_a;
563 ira_object_t parent_obj;
564 ira_allocno_t a = OBJECT_ALLOCNO (obj);
565 IRA_INT_TYPE *object_conflicts;
566 minmax_set_iterator asi;
567 int parent_min, parent_max ATTRIBUTE_UNUSED;
568
569 object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
570 px = 0;
571 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
572 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
573 {
574 ira_object_t another_obj = ira_object_id_map[i];
575 ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
576
577 ira_assert (ira_reg_classes_intersect_p
578 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
579 collected_conflict_objects[px++] = another_obj;
580 }
581 if (ira_conflict_vector_profitable_p (obj, px))
582 {
583 ira_object_t *vec;
584 ira_allocate_conflict_vec (obj, px);
585 vec = OBJECT_CONFLICT_VEC (obj);
586 memcpy (dest: vec, src: collected_conflict_objects, n: sizeof (ira_object_t) * px);
587 vec[px] = NULL;
588 OBJECT_NUM_CONFLICTS (obj) = px;
589 }
590 else
591 {
592 int conflict_bit_vec_words_num;
593
594 OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
595 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
596 conflict_bit_vec_words_num = 0;
597 else
598 conflict_bit_vec_words_num
599 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
600 / IRA_INT_BITS);
601 OBJECT_CONFLICT_ARRAY_SIZE (obj)
602 = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
603 }
604
605 parent_a = ira_parent_or_cap_allocno (a);
606 if (parent_a == NULL)
607 return;
608 ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
609 ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
610 parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
611 parent_num = OBJECT_CONFLICT_ID (parent_obj);
612 parent_min = OBJECT_MIN (parent_obj);
613 parent_max = OBJECT_MAX (parent_obj);
614 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
615 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
616 {
617 ira_object_t another_obj = ira_object_id_map[i];
618 ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
619 int another_word = OBJECT_SUBWORD (another_obj);
620
621 ira_assert (ira_reg_classes_intersect_p
622 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
623
624 another_parent_a = ira_parent_or_cap_allocno (another_a);
625 if (another_parent_a == NULL)
626 continue;
627 ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
628 ira_assert (ALLOCNO_CLASS (another_a)
629 == ALLOCNO_CLASS (another_parent_a));
630 ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
631 == ALLOCNO_NUM_OBJECTS (another_parent_a));
632 SET_MINMAX_SET_BIT (conflicts[parent_num],
633 OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
634 another_word)),
635 parent_min, parent_max);
636 }
637}
638
639/* Build conflict vectors or bit conflict vectors (whatever is more
640 profitable) of all allocnos from the conflict table. */
641static void
642build_conflicts (void)
643{
644 int i;
645 ira_allocno_t a, cap;
646
647 collected_conflict_objects
648 = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
649 * ira_objects_num);
650 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
651 for (a = ira_regno_allocno_map[i];
652 a != NULL;
653 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
654 {
655 int j, nregs = ALLOCNO_NUM_OBJECTS (a);
656 for (j = 0; j < nregs; j++)
657 {
658 ira_object_t obj = ALLOCNO_OBJECT (a, j);
659 build_object_conflicts (obj);
660 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
661 {
662 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
663 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
664 build_object_conflicts (obj: cap_obj);
665 }
666 }
667 }
668 ira_free (addr: collected_conflict_objects);
669}
670
671
672
673/* Print hard reg set SET with TITLE to FILE. */
674static void
675print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
676{
677 int i, start, end;
678
679 fputs (s: title, stream: file);
680 for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
681 {
682 bool reg_included = TEST_HARD_REG_BIT (set, bit: i);
683
684 if (reg_included)
685 {
686 if (start == -1)
687 start = i;
688 end = i;
689 }
690 if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
691 {
692 if (start == end)
693 fprintf (stream: file, format: " %d", start);
694 else if (start == end + 1)
695 fprintf (stream: file, format: " %d %d", start, end);
696 else
697 fprintf (stream: file, format: " %d-%d", start, end);
698 start = -1;
699 }
700 }
701 putc (c: '\n', stream: file);
702}
703
704static void
705print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
706{
707 HARD_REG_SET conflicting_hard_regs;
708 basic_block bb;
709 int n, i;
710
711 if (reg_p)
712 fprintf (stream: file, format: ";; r%d", ALLOCNO_REGNO (a));
713 else
714 {
715 fprintf (stream: file, format: ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
716 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
717 fprintf (stream: file, format: "b%d", bb->index);
718 else
719 fprintf (stream: file, format: "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
720 putc (c: ')', stream: file);
721 }
722
723 fputs (s: " conflicts:", stream: file);
724 n = ALLOCNO_NUM_OBJECTS (a);
725 for (i = 0; i < n; i++)
726 {
727 ira_object_t obj = ALLOCNO_OBJECT (a, i);
728 ira_object_t conflict_obj;
729 ira_object_conflict_iterator oci;
730
731 if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
732 {
733 fprintf (stream: file, format: "\n;; total conflict hard regs:\n");
734 fprintf (stream: file, format: ";; conflict hard regs:\n\n");
735 continue;
736 }
737
738 if (n > 1)
739 fprintf (stream: file, format: "\n;; subobject %d:", i);
740 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
741 {
742 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
743 if (reg_p)
744 fprintf (stream: file, format: " r%d,", ALLOCNO_REGNO (conflict_a));
745 else
746 {
747 fprintf (stream: file, format: " a%d(r%d", ALLOCNO_NUM (conflict_a),
748 ALLOCNO_REGNO (conflict_a));
749 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
750 fprintf (stream: file, format: ",w%d", OBJECT_SUBWORD (conflict_obj));
751 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
752 fprintf (stream: file, format: ",b%d", bb->index);
753 else
754 fprintf (stream: file, format: ",l%d",
755 ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
756 putc (c: ')', stream: file);
757 }
758 }
759 conflicting_hard_regs = (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
760 & ~ira_no_alloc_regs
761 & reg_class_contents[ALLOCNO_CLASS (a)]);
762 print_hard_reg_set (file, title: "\n;; total conflict hard regs:",
763 set: conflicting_hard_regs);
764
765 conflicting_hard_regs = (OBJECT_CONFLICT_HARD_REGS (obj)
766 & ~ira_no_alloc_regs
767 & reg_class_contents[ALLOCNO_CLASS (a)]);
768 print_hard_reg_set (file, title: ";; conflict hard regs:",
769 set: conflicting_hard_regs);
770 putc (c: '\n', stream: file);
771 }
772
773}
774
775/* Print information about allocno or only regno (if REG_P) conflicts
776 to FILE. */
777static void
778print_conflicts (FILE *file, bool reg_p)
779{
780 ira_allocno_t a;
781 ira_allocno_iterator ai;
782
783 FOR_EACH_ALLOCNO (a, ai)
784 print_allocno_conflicts (file, reg_p, a);
785 putc (c: '\n', stream: file);
786}
787
788/* Print information about allocno or only regno (if REG_P) conflicts
789 to stderr. */
790void
791ira_debug_conflicts (bool reg_p)
792{
793 print_conflicts (stderr, reg_p);
794}
795
796
797
798/* Entry function which builds allocno conflicts and allocno copies
799 and accumulate some allocno info on upper level regions. */
800void
801ira_build_conflicts (void)
802{
803 enum reg_class base;
804 ira_allocno_t a;
805 ira_allocno_iterator ai;
806 HARD_REG_SET temp_hard_reg_set;
807
808 if (ira_conflicts_p)
809 {
810 ira_conflicts_p = build_conflict_bit_table ();
811 if (ira_conflicts_p)
812 {
813 ira_object_t obj;
814 ira_object_iterator oi;
815
816 build_conflicts ();
817 ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
818 /* We need finished conflict table for the subsequent call. */
819 if (flag_ira_region == IRA_REGION_ALL
820 || flag_ira_region == IRA_REGION_MIXED)
821 propagate_copies ();
822
823 /* Now we can free memory for the conflict table (see function
824 build_object_conflicts for details). */
825 FOR_EACH_OBJECT (obj, oi)
826 {
827 if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
828 ira_free (addr: conflicts[OBJECT_CONFLICT_ID (obj)]);
829 }
830 ira_free (addr: conflicts);
831 }
832 }
833 base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, outer_code: ADDRESS, index_code: SCRATCH);
834 if (! targetm.class_likely_spilled_p (base))
835 CLEAR_HARD_REG_SET (set&: temp_hard_reg_set);
836 else
837 temp_hard_reg_set = reg_class_contents[base] & ~ira_no_alloc_regs;
838 FOR_EACH_ALLOCNO (a, ai)
839 {
840 int i, n = ALLOCNO_NUM_OBJECTS (a);
841
842 for (i = 0; i < n; i++)
843 {
844 ira_object_t obj = ALLOCNO_OBJECT (a, i);
845 rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
846
847 /* For debugging purposes don't put user defined variables in
848 callee-clobbered registers. However, do allow parameters
849 in callee-clobbered registers to improve debugging. This
850 is a bit of a fragile hack. */
851 if (optimize == 0
852 && REG_USERVAR_P (allocno_reg)
853 && ! reg_is_parm_p (allocno_reg))
854 {
855 HARD_REG_SET new_conflict_regs = crtl->abi->full_reg_clobbers ();
856 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
857 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
858 }
859
860 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
861 {
862 HARD_REG_SET new_conflict_regs = ira_need_caller_save_regs (a);
863 if (flag_caller_saves)
864 new_conflict_regs &= (~savable_regs | temp_hard_reg_set);
865 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
866 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
867 }
868
869 /* Now we deal with paradoxical subreg cases where certain registers
870 cannot be accessed in the widest mode. */
871 machine_mode outer_mode = ALLOCNO_WMODE (a);
872 machine_mode inner_mode = ALLOCNO_MODE (a);
873 if (paradoxical_subreg_p (outermode: outer_mode, innermode: inner_mode))
874 {
875 enum reg_class aclass = ALLOCNO_CLASS (a);
876 for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
877 {
878 int inner_regno = ira_class_hard_regs[aclass][j];
879 int outer_regno = simplify_subreg_regno (inner_regno,
880 inner_mode, 0,
881 outer_mode);
882 if (outer_regno < 0
883 || !in_hard_reg_set_p (reg_class_contents[aclass],
884 mode: outer_mode, regno: outer_regno))
885 {
886 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
887 bit: inner_regno);
888 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
889 bit: inner_regno);
890 }
891 }
892 }
893 }
894 }
895 if (optimize && ira_conflicts_p
896 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
897 print_conflicts (file: ira_dump_file, reg_p: false);
898}
899

source code of gcc/ira-conflicts.cc