1 /* IRA conflict builder.
2 Copyright (C) 2006-2021 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 /* Process registers REG1 and REG2 in move INSN with execution
237 frequency FREQ. The function also processes the registers in a
238 potential move insn (INSN == NULL in this case) with frequency
239 FREQ. The function can modify hard register costs of the
240 corresponding allocnos or create a copy involving the corresponding
241 allocnos. The function does nothing if the both registers are hard
242 registers. When nothing is changed, the function returns
243 FALSE. */
244 static bool
process_regs_for_copy(rtx reg1,rtx reg2,bool constraint_p,rtx_insn * insn,int freq)245 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
246 rtx_insn *insn, int freq)
247 {
248 int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
249 bool only_regs_p;
250 ira_allocno_t a;
251 reg_class_t rclass, aclass;
252 machine_mode mode;
253 ira_copy_t cp;
254
255 gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
256 only_regs_p = REG_P (reg1) && REG_P (reg2);
257 reg1 = go_through_subreg (reg1, &offset1);
258 reg2 = go_through_subreg (reg2, &offset2);
259 /* Set up hard regno preferenced by allocno. If allocno gets the
260 hard regno the copy (or potential move) insn will be removed. */
261 if (HARD_REGISTER_P (reg1))
262 {
263 if (HARD_REGISTER_P (reg2))
264 return false;
265 allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
266 a = ira_curr_regno_allocno_map[REGNO (reg2)];
267 }
268 else if (HARD_REGISTER_P (reg2))
269 {
270 allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
271 a = ira_curr_regno_allocno_map[REGNO (reg1)];
272 }
273 else
274 {
275 ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
276 ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
277
278 if (!allocnos_conflict_for_copy_p (a1, a2)
279 && offset1 == offset2
280 && ordered_p (GET_MODE_PRECISION (ALLOCNO_MODE (a1)),
281 GET_MODE_PRECISION (ALLOCNO_MODE (a2))))
282 {
283 cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
284 ira_curr_loop_tree_node);
285 bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
286 return true;
287 }
288 else
289 return false;
290 }
291
292 if (! IN_RANGE (allocno_preferenced_hard_regno,
293 0, FIRST_PSEUDO_REGISTER - 1))
294 /* Cannot be tied. */
295 return false;
296 rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
297 mode = ALLOCNO_MODE (a);
298 aclass = ALLOCNO_CLASS (a);
299 if (only_regs_p && insn != NULL_RTX
300 && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
301 /* It is already taken into account in ira-costs.c. */
302 return false;
303 index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
304 if (index < 0)
305 /* Cannot be tied. It is not in the allocno class. */
306 return false;
307 ira_init_register_move_cost_if_necessary (mode);
308 if (HARD_REGISTER_P (reg1))
309 cost = ira_register_move_cost[mode][aclass][rclass] * freq;
310 else
311 cost = ira_register_move_cost[mode][rclass][aclass] * freq;
312 do
313 {
314 ira_allocate_and_set_costs
315 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
316 ALLOCNO_CLASS_COST (a));
317 ira_allocate_and_set_costs
318 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0);
319 ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
320 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
321 if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
322 ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
323 ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq);
324 a = ira_parent_or_cap_allocno (a);
325 }
326 while (a != NULL);
327 return true;
328 }
329
330 /* Return true if output operand OUTPUT and input operand INPUT of
331 INSN can use the same register class for at least one alternative.
332 INSN is already described in recog_data and recog_op_alt. */
333 static bool
can_use_same_reg_p(rtx_insn * insn,int output,int input)334 can_use_same_reg_p (rtx_insn *insn, int output, int input)
335 {
336 alternative_mask preferred = get_preferred_alternatives (insn);
337 for (int nalt = 0; nalt < recog_data.n_alternatives; nalt++)
338 {
339 if (!TEST_BIT (preferred, nalt))
340 continue;
341
342 const operand_alternative *op_alt
343 = &recog_op_alt[nalt * recog_data.n_operands];
344 if (op_alt[input].matches == output)
345 return true;
346
347 if (ira_reg_class_intersect[op_alt[input].cl][op_alt[output].cl]
348 != NO_REGS)
349 return true;
350 }
351 return false;
352 }
353
354 /* Process all of the output registers of the current insn (INSN) which
355 are not bound (BOUND_P) and the input register REG (its operand number
356 OP_NUM) which dies in the insn as if there were a move insn between
357 them with frequency FREQ. */
358 static void
process_reg_shuffles(rtx_insn * insn,rtx reg,int op_num,int freq,bool * bound_p)359 process_reg_shuffles (rtx_insn *insn, rtx reg, int op_num, int freq,
360 bool *bound_p)
361 {
362 int i;
363 rtx another_reg;
364
365 gcc_assert (REG_SUBREG_P (reg));
366 for (i = 0; i < recog_data.n_operands; i++)
367 {
368 another_reg = recog_data.operand[i];
369
370 if (!REG_SUBREG_P (another_reg) || op_num == i
371 || recog_data.operand_type[i] != OP_OUT
372 || bound_p[i]
373 || (!can_use_same_reg_p (insn, i, op_num)
374 && (recog_data.constraints[op_num][0] != '%'
375 || !can_use_same_reg_p (insn, i, op_num + 1))
376 && (op_num == 0
377 || recog_data.constraints[op_num - 1][0] != '%'
378 || !can_use_same_reg_p (insn, i, op_num - 1))))
379 continue;
380
381 process_regs_for_copy (reg, another_reg, false, NULL, freq);
382 }
383 }
384
385 /* Process INSN and create allocno copies if necessary. For example,
386 it might be because INSN is a pseudo-register move or INSN is two
387 operand insn. */
388 static void
add_insn_allocno_copies(rtx_insn * insn)389 add_insn_allocno_copies (rtx_insn *insn)
390 {
391 rtx set, operand, dup;
392 bool bound_p[MAX_RECOG_OPERANDS];
393 int i, n, freq;
394 alternative_mask alts;
395
396 freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
397 if (freq == 0)
398 freq = 1;
399 if ((set = single_set (insn)) != NULL_RTX
400 && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
401 && ! side_effects_p (set)
402 && find_reg_note (insn, REG_DEAD,
403 REG_P (SET_SRC (set))
404 ? SET_SRC (set)
405 : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
406 {
407 process_regs_for_copy (SET_SRC (set), SET_DEST (set),
408 false, insn, freq);
409 return;
410 }
411 /* Fast check of possibility of constraint or shuffle copies. If
412 there are no dead registers, there will be no such copies. */
413 if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
414 return;
415 alts = ira_setup_alts (insn);
416 for (i = 0; i < recog_data.n_operands; i++)
417 bound_p[i] = false;
418 for (i = 0; i < recog_data.n_operands; i++)
419 {
420 operand = recog_data.operand[i];
421 if (! REG_SUBREG_P (operand))
422 continue;
423 if ((n = ira_get_dup_out_num (i, alts)) >= 0)
424 {
425 bound_p[n] = true;
426 dup = recog_data.operand[n];
427 if (REG_SUBREG_P (dup)
428 && find_reg_note (insn, REG_DEAD,
429 REG_P (operand)
430 ? operand
431 : SUBREG_REG (operand)) != NULL_RTX)
432 process_regs_for_copy (operand, dup, true, NULL,
433 freq);
434 }
435 }
436 for (i = 0; i < recog_data.n_operands; i++)
437 {
438 operand = recog_data.operand[i];
439 if (REG_SUBREG_P (operand)
440 && find_reg_note (insn, REG_DEAD,
441 REG_P (operand)
442 ? operand : SUBREG_REG (operand)) != NULL_RTX)
443 /* If an operand dies, prefer its hard register for the output
444 operands by decreasing the hard register cost or creating
445 the corresponding allocno copies. The cost will not
446 correspond to a real move insn cost, so make the frequency
447 smaller. */
448 process_reg_shuffles (insn, operand, i, freq < 8 ? 1 : freq / 8,
449 bound_p);
450 }
451 }
452
453 /* Add copies originated from BB given by LOOP_TREE_NODE. */
454 static void
add_copies(ira_loop_tree_node_t loop_tree_node)455 add_copies (ira_loop_tree_node_t loop_tree_node)
456 {
457 basic_block bb;
458 rtx_insn *insn;
459
460 bb = loop_tree_node->bb;
461 if (bb == NULL)
462 return;
463 FOR_BB_INSNS (bb, insn)
464 if (NONDEBUG_INSN_P (insn))
465 add_insn_allocno_copies (insn);
466 }
467
468 /* Propagate copies the corresponding allocnos on upper loop tree
469 level. */
470 static void
propagate_copies(void)471 propagate_copies (void)
472 {
473 ira_copy_t cp;
474 ira_copy_iterator ci;
475 ira_allocno_t a1, a2, parent_a1, parent_a2;
476
477 FOR_EACH_COPY (cp, ci)
478 {
479 a1 = cp->first;
480 a2 = cp->second;
481 if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
482 continue;
483 ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
484 parent_a1 = ira_parent_or_cap_allocno (a1);
485 parent_a2 = ira_parent_or_cap_allocno (a2);
486 ira_assert (parent_a1 != NULL && parent_a2 != NULL);
487 if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
488 ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
489 cp->constraint_p, cp->insn, cp->loop_tree_node);
490 }
491 }
492
493 /* Array used to collect all conflict allocnos for given allocno. */
494 static ira_object_t *collected_conflict_objects;
495
496 /* Build conflict vectors or bit conflict vectors (whatever is more
497 profitable) for object OBJ from the conflict table. */
498 static void
build_object_conflicts(ira_object_t obj)499 build_object_conflicts (ira_object_t obj)
500 {
501 int i, px, parent_num;
502 ira_allocno_t parent_a, another_parent_a;
503 ira_object_t parent_obj;
504 ira_allocno_t a = OBJECT_ALLOCNO (obj);
505 IRA_INT_TYPE *object_conflicts;
506 minmax_set_iterator asi;
507 int parent_min, parent_max ATTRIBUTE_UNUSED;
508
509 object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
510 px = 0;
511 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
512 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
513 {
514 ira_object_t another_obj = ira_object_id_map[i];
515 ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
516
517 ira_assert (ira_reg_classes_intersect_p
518 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
519 collected_conflict_objects[px++] = another_obj;
520 }
521 if (ira_conflict_vector_profitable_p (obj, px))
522 {
523 ira_object_t *vec;
524 ira_allocate_conflict_vec (obj, px);
525 vec = OBJECT_CONFLICT_VEC (obj);
526 memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
527 vec[px] = NULL;
528 OBJECT_NUM_CONFLICTS (obj) = px;
529 }
530 else
531 {
532 int conflict_bit_vec_words_num;
533
534 OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
535 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
536 conflict_bit_vec_words_num = 0;
537 else
538 conflict_bit_vec_words_num
539 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
540 / IRA_INT_BITS);
541 OBJECT_CONFLICT_ARRAY_SIZE (obj)
542 = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
543 }
544
545 parent_a = ira_parent_or_cap_allocno (a);
546 if (parent_a == NULL)
547 return;
548 ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
549 ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
550 parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
551 parent_num = OBJECT_CONFLICT_ID (parent_obj);
552 parent_min = OBJECT_MIN (parent_obj);
553 parent_max = OBJECT_MAX (parent_obj);
554 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
555 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
556 {
557 ira_object_t another_obj = ira_object_id_map[i];
558 ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
559 int another_word = OBJECT_SUBWORD (another_obj);
560
561 ira_assert (ira_reg_classes_intersect_p
562 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
563
564 another_parent_a = ira_parent_or_cap_allocno (another_a);
565 if (another_parent_a == NULL)
566 continue;
567 ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
568 ira_assert (ALLOCNO_CLASS (another_a)
569 == ALLOCNO_CLASS (another_parent_a));
570 ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
571 == ALLOCNO_NUM_OBJECTS (another_parent_a));
572 SET_MINMAX_SET_BIT (conflicts[parent_num],
573 OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
574 another_word)),
575 parent_min, parent_max);
576 }
577 }
578
579 /* Build conflict vectors or bit conflict vectors (whatever is more
580 profitable) of all allocnos from the conflict table. */
581 static void
build_conflicts(void)582 build_conflicts (void)
583 {
584 int i;
585 ira_allocno_t a, cap;
586
587 collected_conflict_objects
588 = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
589 * ira_objects_num);
590 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
591 for (a = ira_regno_allocno_map[i];
592 a != NULL;
593 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
594 {
595 int j, nregs = ALLOCNO_NUM_OBJECTS (a);
596 for (j = 0; j < nregs; j++)
597 {
598 ira_object_t obj = ALLOCNO_OBJECT (a, j);
599 build_object_conflicts (obj);
600 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
601 {
602 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
603 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
604 build_object_conflicts (cap_obj);
605 }
606 }
607 }
608 ira_free (collected_conflict_objects);
609 }
610
611
612
613 /* Print hard reg set SET with TITLE to FILE. */
614 static void
print_hard_reg_set(FILE * file,const char * title,HARD_REG_SET set)615 print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
616 {
617 int i, start, end;
618
619 fputs (title, file);
620 for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
621 {
622 bool reg_included = TEST_HARD_REG_BIT (set, i);
623
624 if (reg_included)
625 {
626 if (start == -1)
627 start = i;
628 end = i;
629 }
630 if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
631 {
632 if (start == end)
633 fprintf (file, " %d", start);
634 else if (start == end + 1)
635 fprintf (file, " %d %d", start, end);
636 else
637 fprintf (file, " %d-%d", start, end);
638 start = -1;
639 }
640 }
641 putc ('\n', file);
642 }
643
644 static void
print_allocno_conflicts(FILE * file,bool reg_p,ira_allocno_t a)645 print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
646 {
647 HARD_REG_SET conflicting_hard_regs;
648 basic_block bb;
649 int n, i;
650
651 if (reg_p)
652 fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
653 else
654 {
655 fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
656 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
657 fprintf (file, "b%d", bb->index);
658 else
659 fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
660 putc (')', file);
661 }
662
663 fputs (" conflicts:", file);
664 n = ALLOCNO_NUM_OBJECTS (a);
665 for (i = 0; i < n; i++)
666 {
667 ira_object_t obj = ALLOCNO_OBJECT (a, i);
668 ira_object_t conflict_obj;
669 ira_object_conflict_iterator oci;
670
671 if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
672 {
673 fprintf (file, "\n;; total conflict hard regs:\n");
674 fprintf (file, ";; conflict hard regs:\n\n");
675 continue;
676 }
677
678 if (n > 1)
679 fprintf (file, "\n;; subobject %d:", i);
680 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
681 {
682 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
683 if (reg_p)
684 fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
685 else
686 {
687 fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
688 ALLOCNO_REGNO (conflict_a));
689 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
690 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
691 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
692 fprintf (file, ",b%d", bb->index);
693 else
694 fprintf (file, ",l%d",
695 ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
696 putc (')', file);
697 }
698 }
699 conflicting_hard_regs = (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
700 & ~ira_no_alloc_regs
701 & reg_class_contents[ALLOCNO_CLASS (a)]);
702 print_hard_reg_set (file, "\n;; total conflict hard regs:",
703 conflicting_hard_regs);
704
705 conflicting_hard_regs = (OBJECT_CONFLICT_HARD_REGS (obj)
706 & ~ira_no_alloc_regs
707 & reg_class_contents[ALLOCNO_CLASS (a)]);
708 print_hard_reg_set (file, ";; conflict hard regs:",
709 conflicting_hard_regs);
710 putc ('\n', file);
711 }
712
713 }
714
715 /* Print information about allocno or only regno (if REG_P) conflicts
716 to FILE. */
717 static void
print_conflicts(FILE * file,bool reg_p)718 print_conflicts (FILE *file, bool reg_p)
719 {
720 ira_allocno_t a;
721 ira_allocno_iterator ai;
722
723 FOR_EACH_ALLOCNO (a, ai)
724 print_allocno_conflicts (file, reg_p, a);
725 putc ('\n', file);
726 }
727
728 /* Print information about allocno or only regno (if REG_P) conflicts
729 to stderr. */
730 void
ira_debug_conflicts(bool reg_p)731 ira_debug_conflicts (bool reg_p)
732 {
733 print_conflicts (stderr, reg_p);
734 }
735
736
737
738 /* Entry function which builds allocno conflicts and allocno copies
739 and accumulate some allocno info on upper level regions. */
740 void
ira_build_conflicts(void)741 ira_build_conflicts (void)
742 {
743 enum reg_class base;
744 ira_allocno_t a;
745 ira_allocno_iterator ai;
746 HARD_REG_SET temp_hard_reg_set;
747
748 if (ira_conflicts_p)
749 {
750 ira_conflicts_p = build_conflict_bit_table ();
751 if (ira_conflicts_p)
752 {
753 ira_object_t obj;
754 ira_object_iterator oi;
755
756 build_conflicts ();
757 ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
758 /* We need finished conflict table for the subsequent call. */
759 if (flag_ira_region == IRA_REGION_ALL
760 || flag_ira_region == IRA_REGION_MIXED)
761 propagate_copies ();
762
763 /* Now we can free memory for the conflict table (see function
764 build_object_conflicts for details). */
765 FOR_EACH_OBJECT (obj, oi)
766 {
767 if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
768 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
769 }
770 ira_free (conflicts);
771 }
772 }
773 base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH);
774 if (! targetm.class_likely_spilled_p (base))
775 CLEAR_HARD_REG_SET (temp_hard_reg_set);
776 else
777 temp_hard_reg_set = reg_class_contents[base] & ~ira_no_alloc_regs;
778 FOR_EACH_ALLOCNO (a, ai)
779 {
780 int i, n = ALLOCNO_NUM_OBJECTS (a);
781
782 for (i = 0; i < n; i++)
783 {
784 ira_object_t obj = ALLOCNO_OBJECT (a, i);
785 rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
786
787 /* For debugging purposes don't put user defined variables in
788 callee-clobbered registers. However, do allow parameters
789 in callee-clobbered registers to improve debugging. This
790 is a bit of a fragile hack. */
791 if (optimize == 0
792 && REG_USERVAR_P (allocno_reg)
793 && ! reg_is_parm_p (allocno_reg))
794 {
795 HARD_REG_SET new_conflict_regs = crtl->abi->full_reg_clobbers ();
796 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
797 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
798 }
799
800 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
801 {
802 HARD_REG_SET new_conflict_regs = ira_need_caller_save_regs (a);
803 if (flag_caller_saves)
804 new_conflict_regs &= (~savable_regs | temp_hard_reg_set);
805 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
806 OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
807 }
808
809 /* Now we deal with paradoxical subreg cases where certain registers
810 cannot be accessed in the widest mode. */
811 machine_mode outer_mode = ALLOCNO_WMODE (a);
812 machine_mode inner_mode = ALLOCNO_MODE (a);
813 if (paradoxical_subreg_p (outer_mode, inner_mode))
814 {
815 enum reg_class aclass = ALLOCNO_CLASS (a);
816 for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
817 {
818 int inner_regno = ira_class_hard_regs[aclass][j];
819 int outer_regno = simplify_subreg_regno (inner_regno,
820 inner_mode, 0,
821 outer_mode);
822 if (outer_regno < 0
823 || !in_hard_reg_set_p (reg_class_contents[aclass],
824 outer_mode, outer_regno))
825 {
826 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
827 inner_regno);
828 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
829 inner_regno);
830 }
831 }
832 }
833 }
834 }
835 if (optimize && ira_conflicts_p
836 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
837 print_conflicts (ira_dump_file, false);
838 }
839