1 /* IRA conflict builder.
2 Copyright (C) 2006-2022 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
record_object_conflict(ira_object_t obj1,ira_object_t obj2)61 record_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. */
90 static bool
build_conflict_bit_table(void)91 build_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 (ira_dump_file,
120 "+++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 (conflicts[id], 0,
146 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 (ira_dump_file,
153 "+++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 (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 (obj, live_obj);
180 }
181 }
182 sparseset_set_bit (objects_live, 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
195 static bool
allocnos_conflict_for_copy_p(ira_allocno_t a1,ira_allocno_t a2)196 allocnos_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. */
214 static rtx
go_through_subreg(rtx x,int * offset)215 go_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)), 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
239 static int
get_freq_for_shuffle_copy(int freq)240 get_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. */
254 static bool
process_regs_for_copy(rtx reg1,rtx reg2,bool constraint_p,rtx_insn * insn,int freq,bool single_input_op_has_cstr_p=true)255 process_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 (reg1, &offset1);
269 reg2 = go_through_subreg (reg2, &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 (GET_MODE_PRECISION (ALLOCNO_MODE (a1)),
292 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 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
370 ALLOCNO_CLASS_COST (a));
371 ira_allocate_and_set_costs
372 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 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. */
387 static bool
can_use_same_reg_p(rtx_insn * insn,int output,int input)388 can_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 (ira_reg_class_intersect[op_alt[input].cl][op_alt[output].cl]
402 != NO_REGS)
403 return true;
404 }
405 return false;
406 }
407
408 /* Process all of the output registers of the current insn (INSN) which
409 are not bound (BOUND_P) and the input register REG (its operand number
410 OP_NUM) which dies in the insn as if there were a move insn between
411 them with frequency FREQ. */
412 static void
process_reg_shuffles(rtx_insn * insn,rtx reg,int op_num,int freq,bool * bound_p)413 process_reg_shuffles (rtx_insn *insn, rtx reg, int op_num, int freq,
414 bool *bound_p)
415 {
416 int i;
417 rtx another_reg;
418
419 gcc_assert (REG_SUBREG_P (reg));
420 for (i = 0; i < recog_data.n_operands; i++)
421 {
422 another_reg = recog_data.operand[i];
423
424 if (!REG_SUBREG_P (another_reg) || op_num == i
425 || recog_data.operand_type[i] != OP_OUT
426 || bound_p[i]
427 || (!can_use_same_reg_p (insn, i, op_num)
428 && (recog_data.constraints[op_num][0] != '%'
429 || !can_use_same_reg_p (insn, i, op_num + 1))
430 && (op_num == 0
431 || recog_data.constraints[op_num - 1][0] != '%'
432 || !can_use_same_reg_p (insn, i, op_num - 1))))
433 continue;
434
435 process_regs_for_copy (reg, another_reg, false, NULL, freq);
436 }
437 }
438
439 /* Process INSN and create allocno copies if necessary. For example,
440 it might be because INSN is a pseudo-register move or INSN is two
441 operand insn. */
442 static void
add_insn_allocno_copies(rtx_insn * insn)443 add_insn_allocno_copies (rtx_insn *insn)
444 {
445 rtx set, operand, dup;
446 bool bound_p[MAX_RECOG_OPERANDS];
447 int i, n, freq;
448 alternative_mask alts;
449
450 freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
451 if (freq == 0)
452 freq = 1;
453 if ((set = single_set (insn)) != NULL_RTX
454 && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
455 && ! side_effects_p (set)
456 && find_reg_note (insn, REG_DEAD,
457 REG_P (SET_SRC (set))
458 ? SET_SRC (set)
459 : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
460 {
461 process_regs_for_copy (SET_SRC (set), SET_DEST (set),
462 false, insn, freq);
463 return;
464 }
465 /* Fast check of possibility of constraint or shuffle copies. If
466 there are no dead registers, there will be no such copies. */
467 if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
468 return;
469 alts = ira_setup_alts (insn);
470 for (i = 0; i < recog_data.n_operands; i++)
471 bound_p[i] = false;
472 for (i = 0; i < recog_data.n_operands; i++)
473 {
474 operand = recog_data.operand[i];
475 if (! REG_SUBREG_P (operand))
476 continue;
477 bool single_input_op_has_cstr_p;
478 if ((n = ira_get_dup_out_num (i, alts, single_input_op_has_cstr_p)) >= 0)
479 {
480 bound_p[n] = true;
481 dup = recog_data.operand[n];
482 if (REG_SUBREG_P (dup)
483 && find_reg_note (insn, REG_DEAD,
484 REG_P (operand)
485 ? operand
486 : SUBREG_REG (operand)) != NULL_RTX)
487 process_regs_for_copy (operand, dup, true, NULL, freq,
488 single_input_op_has_cstr_p);
489 }
490 }
491 for (i = 0; i < recog_data.n_operands; i++)
492 {
493 operand = recog_data.operand[i];
494 if (REG_SUBREG_P (operand)
495 && find_reg_note (insn, REG_DEAD,
496 REG_P (operand)
497 ? operand : SUBREG_REG (operand)) != NULL_RTX)
498 {
499 /* If an operand dies, prefer its hard register for the output
500 operands by decreasing the hard register cost or creating
501 the corresponding allocno copies. The cost will not
502 correspond to a real move insn cost, so make the frequency
503 smaller. */
504 int new_freq = get_freq_for_shuffle_copy (freq);
505 process_reg_shuffles (insn, operand, i, new_freq, bound_p);
506 }
507 }
508 }
509
510 /* Add copies originated from BB given by LOOP_TREE_NODE. */
511 static void
add_copies(ira_loop_tree_node_t loop_tree_node)512 add_copies (ira_loop_tree_node_t loop_tree_node)
513 {
514 basic_block bb;
515 rtx_insn *insn;
516
517 bb = loop_tree_node->bb;
518 if (bb == NULL)
519 return;
520 FOR_BB_INSNS (bb, insn)
521 if (NONDEBUG_INSN_P (insn))
522 add_insn_allocno_copies (insn);
523 }
524
525 /* Propagate copies the corresponding allocnos on upper loop tree
526 level. */
527 static void
propagate_copies(void)528 propagate_copies (void)
529 {
530 ira_copy_t cp;
531 ira_copy_iterator ci;
532 ira_allocno_t a1, a2, parent_a1, parent_a2;
533
534 FOR_EACH_COPY (cp, ci)
535 {
536 a1 = cp->first;
537 a2 = cp->second;
538 if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
539 continue;
540 ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
541 parent_a1 = ira_parent_or_cap_allocno (a1);
542 parent_a2 = ira_parent_or_cap_allocno (a2);
543 ira_assert (parent_a1 != NULL && parent_a2 != NULL);
544 if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
545 ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
546 cp->constraint_p, cp->insn, cp->loop_tree_node);
547 }
548 }
549
550 /* Array used to collect all conflict allocnos for given allocno. */
551 static ira_object_t *collected_conflict_objects;
552
553 /* Build conflict vectors or bit conflict vectors (whatever is more
554 profitable) for object OBJ from the conflict table. */
555 static void
build_object_conflicts(ira_object_t obj)556 build_object_conflicts (ira_object_t obj)
557 {
558 int i, px, parent_num;
559 ira_allocno_t parent_a, another_parent_a;
560 ira_object_t parent_obj;
561 ira_allocno_t a = OBJECT_ALLOCNO (obj);
562 IRA_INT_TYPE *object_conflicts;
563 minmax_set_iterator asi;
564 int parent_min, parent_max ATTRIBUTE_UNUSED;
565
566 object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
567 px = 0;
568 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
569 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
570 {
571 ira_object_t another_obj = ira_object_id_map[i];
572 ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
573
574 ira_assert (ira_reg_classes_intersect_p
575 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
576 collected_conflict_objects[px++] = another_obj;
577 }
578 if (ira_conflict_vector_profitable_p (obj, px))
579 {
580 ira_object_t *vec;
581 ira_allocate_conflict_vec (obj, px);
582 vec = OBJECT_CONFLICT_VEC (obj);
583 memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
584 vec[px] = NULL;
585 OBJECT_NUM_CONFLICTS (obj) = px;
586 }
587 else
588 {
589 int conflict_bit_vec_words_num;
590
591 OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
592 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
593 conflict_bit_vec_words_num = 0;
594 else
595 conflict_bit_vec_words_num
596 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
597 / IRA_INT_BITS);
598 OBJECT_CONFLICT_ARRAY_SIZE (obj)
599 = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
600 }
601
602 parent_a = ira_parent_or_cap_allocno (a);
603 if (parent_a == NULL)
604 return;
605 ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
606 ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
607 parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
608 parent_num = OBJECT_CONFLICT_ID (parent_obj);
609 parent_min = OBJECT_MIN (parent_obj);
610 parent_max = OBJECT_MAX (parent_obj);
611 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
612 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
613 {
614 ira_object_t another_obj = ira_object_id_map[i];
615 ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
616 int another_word = OBJECT_SUBWORD (another_obj);
617
618 ira_assert (ira_reg_classes_intersect_p
619 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
620
621 another_parent_a = ira_parent_or_cap_allocno (another_a);
622 if (another_parent_a == NULL)
623 continue;
624 ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
625 ira_assert (ALLOCNO_CLASS (another_a)
626 == ALLOCNO_CLASS (another_parent_a));
627 ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
628 == ALLOCNO_NUM_OBJECTS (another_parent_a));
629 SET_MINMAX_SET_BIT (conflicts[parent_num],
630 OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
631 another_word)),
632 parent_min, parent_max);
633 }
634 }
635
636 /* Build conflict vectors or bit conflict vectors (whatever is more
637 profitable) of all allocnos from the conflict table. */
638 static void
build_conflicts(void)639 build_conflicts (void)
640 {
641 int i;
642 ira_allocno_t a, cap;
643
644 collected_conflict_objects
645 = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
646 * ira_objects_num);
647 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
648 for (a = ira_regno_allocno_map[i];
649 a != NULL;
650 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
651 {
652 int j, nregs = ALLOCNO_NUM_OBJECTS (a);
653 for (j = 0; j < nregs; j++)
654 {
655 ira_object_t obj = ALLOCNO_OBJECT (a, j);
656 build_object_conflicts (obj);
657 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
658 {
659 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
660 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
661 build_object_conflicts (cap_obj);
662 }
663 }
664 }
665 ira_free (collected_conflict_objects);
666 }
667
668
669
670 /* Print hard reg set SET with TITLE to FILE. */
671 static void
print_hard_reg_set(FILE * file,const char * title,HARD_REG_SET set)672 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
673 {
674 int i, start, end;
675
676 fputs (title, file);
677 for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
678 {
679 bool reg_included = TEST_HARD_REG_BIT (set, i);
680
681 if (reg_included)
682 {
683 if (start == -1)
684 start = i;
685 end = i;
686 }
687 if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
688 {
689 if (start == end)
690 fprintf (file, " %d", start);
691 else if (start == end + 1)
692 fprintf (file, " %d %d", start, end);
693 else
694 fprintf (file, " %d-%d", start, end);
695 start = -1;
696 }
697 }
698 putc ('\n', file);
699 }
700
701 static void
print_allocno_conflicts(FILE * file,bool reg_p,ira_allocno_t a)702 print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
703 {
704 HARD_REG_SET conflicting_hard_regs;
705 basic_block bb;
706 int n, i;
707
708 if (reg_p)
709 fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
710 else
711 {
712 fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
713 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
714 fprintf (file, "b%d", bb->index);
715 else
716 fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
717 putc (')', file);
718 }
719
720 fputs (" conflicts:", file);
721 n = ALLOCNO_NUM_OBJECTS (a);
722 for (i = 0; i < n; i++)
723 {
724 ira_object_t obj = ALLOCNO_OBJECT (a, i);
725 ira_object_t conflict_obj;
726 ira_object_conflict_iterator oci;
727
728 if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
729 {
730 fprintf (file, "\n;; total conflict hard regs:\n");
731 fprintf (file, ";; conflict hard regs:\n\n");
732 continue;
733 }
734
735 if (n > 1)
736 fprintf (file, "\n;; subobject %d:", i);
737 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
738 {
739 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
740 if (reg_p)
741 fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
742 else
743 {
744 fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
745 ALLOCNO_REGNO (conflict_a));
746 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
747 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
748 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
749 fprintf (file, ",b%d", bb->index);
750 else
751 fprintf (file, ",l%d",
752 ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
753 putc (')', file);
754 }
755 }
756 conflicting_hard_regs = (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
757 & ~ira_no_alloc_regs
758 & reg_class_contents[ALLOCNO_CLASS (a)]);
759 print_hard_reg_set (file, "\n;; total conflict hard regs:",
760 conflicting_hard_regs);
761
762 conflicting_hard_regs = (OBJECT_CONFLICT_HARD_REGS (obj)
763 & ~ira_no_alloc_regs
764 & reg_class_contents[ALLOCNO_CLASS (a)]);
765 print_hard_reg_set (file, ";; conflict hard regs:",
766 conflicting_hard_regs);
767 putc ('\n', file);
768 }
769
770 }
771
772 /* Print information about allocno or only regno (if REG_P) conflicts
773 to FILE. */
774 static void
print_conflicts(FILE * file,bool reg_p)775 print_conflicts (FILE *file, bool reg_p)
776 {
777 ira_allocno_t a;
778 ira_allocno_iterator ai;
779
780 FOR_EACH_ALLOCNO (a, ai)
781 print_allocno_conflicts (file, reg_p, a);
782 putc ('\n', file);
783 }
784
785 /* Print information about allocno or only regno (if REG_P) conflicts
786 to stderr. */
787 void
ira_debug_conflicts(bool reg_p)788 ira_debug_conflicts (bool reg_p)
789 {
790 print_conflicts (stderr, reg_p);
791 }
792
793
794
795 /* Entry function which builds allocno conflicts and allocno copies
796 and accumulate some allocno info on upper level regions. */
797 void
ira_build_conflicts(void)798 ira_build_conflicts (void)
799 {
800 enum reg_class base;
801 ira_allocno_t a;
802 ira_allocno_iterator ai;
803 HARD_REG_SET temp_hard_reg_set;
804
805 if (ira_conflicts_p)
806 {
807 ira_conflicts_p = build_conflict_bit_table ();
808 if (ira_conflicts_p)
809 {
810 ira_object_t obj;
811 ira_object_iterator oi;
812
813 build_conflicts ();
814 ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
815 /* We need finished conflict table for the subsequent call. */
816 if (flag_ira_region == IRA_REGION_ALL
817 || flag_ira_region == IRA_REGION_MIXED)
818 propagate_copies ();
819
820 /* Now we can free memory for the conflict table (see function
821 build_object_conflicts for details). */
822 FOR_EACH_OBJECT (obj, oi)
823 {
824 if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
825 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
826 }
827 ira_free (conflicts);
828 }
829 }
830 base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH);
831 if (! targetm.class_likely_spilled_p (base))
832 CLEAR_HARD_REG_SET (temp_hard_reg_set);
833 else
834 temp_hard_reg_set = reg_class_contents[base] & ~ira_no_alloc_regs;
835 FOR_EACH_ALLOCNO (a, ai)
836 {
837 int i, n = ALLOCNO_NUM_OBJECTS (a);
838
839 for (i = 0; i < n; i++)
840 {
841 ira_object_t obj = ALLOCNO_OBJECT (a, i);
842 rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
843
844 /* For debugging purposes don't put user defined variables in
845 callee-clobbered registers. However, do allow parameters
846 in callee-clobbered registers to improve debugging. This
847 is a bit of a fragile hack. */
848 if (optimize == 0
849 && REG_USERVAR_P (allocno_reg)
850 && ! reg_is_parm_p (allocno_reg))
851 {
852 HARD_REG_SET new_conflict_regs = crtl->abi->full_reg_clobbers ();
853 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
854 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
855 }
856
857 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
858 {
859 HARD_REG_SET new_conflict_regs = ira_need_caller_save_regs (a);
860 if (flag_caller_saves)
861 new_conflict_regs &= (~savable_regs | temp_hard_reg_set);
862 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
863 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
864 }
865
866 /* Now we deal with paradoxical subreg cases where certain registers
867 cannot be accessed in the widest mode. */
868 machine_mode outer_mode = ALLOCNO_WMODE (a);
869 machine_mode inner_mode = ALLOCNO_MODE (a);
870 if (paradoxical_subreg_p (outer_mode, inner_mode))
871 {
872 enum reg_class aclass = ALLOCNO_CLASS (a);
873 for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
874 {
875 int inner_regno = ira_class_hard_regs[aclass][j];
876 int outer_regno = simplify_subreg_regno (inner_regno,
877 inner_mode, 0,
878 outer_mode);
879 if (outer_regno < 0
880 || !in_hard_reg_set_p (reg_class_contents[aclass],
881 outer_mode, outer_regno))
882 {
883 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
884 inner_regno);
885 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
886 inner_regno);
887 }
888 }
889 }
890 }
891 }
892 if (optimize && ira_conflicts_p
893 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
894 print_conflicts (ira_dump_file, false);
895 }
896