1/* IRA conflict builder.
2 Copyright (C) 2006-2017 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 "params.h"
35#include "sparseset.h"
36#include "addresses.h"
37
38/* This file contains code responsible for allocno conflict creation,
39 allocno copy creation and allocno info accumulation on upper level
40 regions. */
41
42/* ira_allocnos_num array of arrays of bits, recording whether two
43 allocno's conflict (can't go in the same hardware register).
44
45 Some arrays will be used as conflict bit vector of the
46 corresponding allocnos see function build_object_conflicts. */
47static IRA_INT_TYPE **conflicts;
48
49/* Macro to test a conflict of C1 and C2 in `conflicts'. */
50#define OBJECTS_CONFLICT_P(C1, C2) \
51 (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2) \
52 && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1) \
53 && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)], \
54 OBJECT_CONFLICT_ID (C2), \
55 OBJECT_MIN (C1), OBJECT_MAX (C1)))
56
57
58/* Record a conflict between objects OBJ1 and OBJ2. If necessary,
59 canonicalize the conflict by recording it for lower-order subobjects
60 of the corresponding allocnos. */
61static void
62record_object_conflict (ira_object_t obj1, ira_object_t obj2)
63{
64 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
65 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
66 int w1 = OBJECT_SUBWORD (obj1);
67 int w2 = OBJECT_SUBWORD (obj2);
68 int id1, id2;
69
70 /* Canonicalize the conflict. If two identically-numbered words
71 conflict, always record this as a conflict between words 0. That
72 is the only information we need, and it is easier to test for if
73 it is collected in each allocno's lowest-order object. */
74 if (w1 == w2 && w1 > 0)
75 {
76 obj1 = ALLOCNO_OBJECT (a1, 0);
77 obj2 = ALLOCNO_OBJECT (a2, 0);
78 }
79 id1 = OBJECT_CONFLICT_ID (obj1);
80 id2 = OBJECT_CONFLICT_ID (obj2);
81
82 SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
83 OBJECT_MAX (obj1));
84 SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
85 OBJECT_MAX (obj2));
86}
87
88/* Build allocno conflict table by processing allocno live ranges.
89 Return true if the table was built. The table is not built if it
90 is too big. */
91static bool
92build_conflict_bit_table (void)
93{
94 int i;
95 unsigned int j;
96 enum reg_class aclass;
97 int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
98 live_range_t r;
99 ira_allocno_t allocno;
100 ira_allocno_iterator ai;
101 sparseset objects_live;
102 ira_object_t obj;
103 ira_allocno_object_iterator aoi;
104
105 allocated_words_num = 0;
106 FOR_EACH_ALLOCNO (allocno, ai)
107 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
108 {
109 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
110 continue;
111 conflict_bit_vec_words_num
112 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
113 / IRA_INT_BITS);
114 allocated_words_num += conflict_bit_vec_words_num;
115 if ((uint64_t) allocated_words_num * sizeof (IRA_INT_TYPE)
116 > (uint64_t) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024)
117 {
118 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
119 fprintf
120 (ira_dump_file,
121 "+++Conflict table will be too big(>%dMB) -- don't use it\n",
122 IRA_MAX_CONFLICT_TABLE_SIZE);
123 return false;
124 }
125 }
126
127 conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
128 * ira_objects_num);
129 allocated_words_num = 0;
130 FOR_EACH_ALLOCNO (allocno, ai)
131 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
132 {
133 int id = OBJECT_CONFLICT_ID (obj);
134 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
135 {
136 conflicts[id] = NULL;
137 continue;
138 }
139 conflict_bit_vec_words_num
140 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
141 / IRA_INT_BITS);
142 allocated_words_num += conflict_bit_vec_words_num;
143 conflicts[id]
144 = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
145 * conflict_bit_vec_words_num);
146 memset (conflicts[id], 0,
147 sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
148 }
149
150 object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
151 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
152 fprintf
153 (ira_dump_file,
154 "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
155 (long) allocated_words_num * sizeof (IRA_INT_TYPE),
156 (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE));
157
158 objects_live = sparseset_alloc (ira_objects_num);
159 for (i = 0; i < ira_max_point; i++)
160 {
161 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
162 {
163 ira_object_t obj = r->object;
164 ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
165 int id = OBJECT_CONFLICT_ID (obj);
166
167 gcc_assert (id < ira_objects_num);
168
169 aclass = ALLOCNO_CLASS (allocno);
170 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
171 {
172 ira_object_t live_obj = ira_object_id_map[j];
173 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
174 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
175
176 if (ira_reg_classes_intersect_p[aclass][live_aclass]
177 /* Don't set up conflict for the allocno with itself. */
178 && live_a != allocno)
179 {
180 record_object_conflict (obj, live_obj);
181 }
182 }
183 sparseset_set_bit (objects_live, id);
184 }
185
186 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
187 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
188 }
189 sparseset_free (objects_live);
190 return true;
191}
192
193/* Return true iff allocnos A1 and A2 cannot be allocated to the same
194 register due to conflicts. */
195
196static bool
197allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
198{
199 /* Due to the fact that we canonicalize conflicts (see
200 record_object_conflict), we only need to test for conflicts of
201 the lowest order words. */
202 ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
203 ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
204
205 return OBJECTS_CONFLICT_P (obj1, obj2);
206}
207
208/* Check that X is REG or SUBREG of REG. */
209#define REG_SUBREG_P(x) \
210 (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
211
212/* Return X if X is a REG, otherwise it should be SUBREG of REG and
213 the function returns the reg in this case. *OFFSET will be set to
214 0 in the first case or the regno offset in the first case. */
215static rtx
216go_through_subreg (rtx x, int *offset)
217{
218 rtx reg;
219
220 *offset = 0;
221 if (REG_P (x))
222 return x;
223 ira_assert (GET_CODE (x) == SUBREG);
224 reg = SUBREG_REG (x);
225 ira_assert (REG_P (reg));
226 if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
227 *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
228 SUBREG_BYTE (x), GET_MODE (x));
229 else
230 *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
231 return reg;
232}
233
234/* Process registers REG1 and REG2 in move INSN with execution
235 frequency FREQ. The function also processes the registers in a
236 potential move insn (INSN == NULL in this case) with frequency
237 FREQ. The function can modify hard register costs of the
238 corresponding allocnos or create a copy involving the corresponding
239 allocnos. The function does nothing if the both registers are hard
240 registers. When nothing is changed, the function returns
241 FALSE. */
242static bool
243process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
244 rtx_insn *insn, int freq)
245{
246 int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
247 bool only_regs_p;
248 ira_allocno_t a;
249 reg_class_t rclass, aclass;
250 machine_mode mode;
251 ira_copy_t cp;
252
253 gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
254 only_regs_p = REG_P (reg1) && REG_P (reg2);
255 reg1 = go_through_subreg (reg1, &offset1);
256 reg2 = go_through_subreg (reg2, &offset2);
257 /* Set up hard regno preferenced by allocno. If allocno gets the
258 hard regno the copy (or potential move) insn will be removed. */
259 if (HARD_REGISTER_P (reg1))
260 {
261 if (HARD_REGISTER_P (reg2))
262 return false;
263 allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
264 a = ira_curr_regno_allocno_map[REGNO (reg2)];
265 }
266 else if (HARD_REGISTER_P (reg2))
267 {
268 allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
269 a = ira_curr_regno_allocno_map[REGNO (reg1)];
270 }
271 else
272 {
273 ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
274 ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
275
276 if (!allocnos_conflict_for_copy_p (a1, a2) && offset1 == offset2)
277 {
278 cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
279 ira_curr_loop_tree_node);
280 bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
281 return true;
282 }
283 else
284 return false;
285 }
286
287 if (! IN_RANGE (allocno_preferenced_hard_regno,
288 0, FIRST_PSEUDO_REGISTER - 1))
289 /* Can not be tied. */
290 return false;
291 rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
292 mode = ALLOCNO_MODE (a);
293 aclass = ALLOCNO_CLASS (a);
294 if (only_regs_p && insn != NULL_RTX
295 && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
296 /* It is already taken into account in ira-costs.c. */
297 return false;
298 index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
299 if (index < 0)
300 /* Can not be tied. It is not in the allocno class. */
301 return false;
302 ira_init_register_move_cost_if_necessary (mode);
303 if (HARD_REGISTER_P (reg1))
304 cost = ira_register_move_cost[mode][aclass][rclass] * freq;
305 else
306 cost = ira_register_move_cost[mode][rclass][aclass] * freq;
307 do
308 {
309 ira_allocate_and_set_costs
310 (&ALLOCNO_HARD_REG_COSTS (a), aclass,
311 ALLOCNO_CLASS_COST (a));
312 ira_allocate_and_set_costs
313 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0);
314 ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
315 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
316 if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
317 ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
318 ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq);
319 a = ira_parent_or_cap_allocno (a);
320 }
321 while (a != NULL);
322 return true;
323}
324
325/* Process all of the output registers of the current insn which are
326 not bound (BOUND_P) and the input register REG (its operand number
327 OP_NUM) which dies in the insn as if there were a move insn between
328 them with frequency FREQ. */
329static void
330process_reg_shuffles (rtx reg, int op_num, int freq, bool *bound_p)
331{
332 int i;
333 rtx another_reg;
334
335 gcc_assert (REG_SUBREG_P (reg));
336 for (i = 0; i < recog_data.n_operands; i++)
337 {
338 another_reg = recog_data.operand[i];
339
340 if (!REG_SUBREG_P (another_reg) || op_num == i
341 || recog_data.operand_type[i] != OP_OUT
342 || bound_p[i])
343 continue;
344
345 process_regs_for_copy (reg, another_reg, false, NULL, freq);
346 }
347}
348
349/* Process INSN and create allocno copies if necessary. For example,
350 it might be because INSN is a pseudo-register move or INSN is two
351 operand insn. */
352static void
353add_insn_allocno_copies (rtx_insn *insn)
354{
355 rtx set, operand, dup;
356 bool bound_p[MAX_RECOG_OPERANDS];
357 int i, n, freq;
358 HARD_REG_SET alts;
359
360 freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
361 if (freq == 0)
362 freq = 1;
363 if ((set = single_set (insn)) != NULL_RTX
364 && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
365 && ! side_effects_p (set)
366 && find_reg_note (insn, REG_DEAD,
367 REG_P (SET_SRC (set))
368 ? SET_SRC (set)
369 : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
370 {
371 process_regs_for_copy (SET_SRC (set), SET_DEST (set),
372 false, insn, freq);
373 return;
374 }
375 /* Fast check of possibility of constraint or shuffle copies. If
376 there are no dead registers, there will be no such copies. */
377 if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
378 return;
379 ira_setup_alts (insn, alts);
380 for (i = 0; i < recog_data.n_operands; i++)
381 bound_p[i] = false;
382 for (i = 0; i < recog_data.n_operands; i++)
383 {
384 operand = recog_data.operand[i];
385 if (! REG_SUBREG_P (operand))
386 continue;
387 if ((n = ira_get_dup_out_num (i, alts)) >= 0)
388 {
389 bound_p[n] = true;
390 dup = recog_data.operand[n];
391 if (REG_SUBREG_P (dup)
392 && find_reg_note (insn, REG_DEAD,
393 REG_P (operand)
394 ? operand
395 : SUBREG_REG (operand)) != NULL_RTX)
396 process_regs_for_copy (operand, dup, true, NULL,
397 freq);
398 }
399 }
400 for (i = 0; i < recog_data.n_operands; i++)
401 {
402 operand = recog_data.operand[i];
403 if (REG_SUBREG_P (operand)
404 && find_reg_note (insn, REG_DEAD,
405 REG_P (operand)
406 ? operand : SUBREG_REG (operand)) != NULL_RTX)
407 /* If an operand dies, prefer its hard register for the output
408 operands by decreasing the hard register cost or creating
409 the corresponding allocno copies. The cost will not
410 correspond to a real move insn cost, so make the frequency
411 smaller. */
412 process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8, bound_p);
413 }
414}
415
416/* Add copies originated from BB given by LOOP_TREE_NODE. */
417static void
418add_copies (ira_loop_tree_node_t loop_tree_node)
419{
420 basic_block bb;
421 rtx_insn *insn;
422
423 bb = loop_tree_node->bb;
424 if (bb == NULL)
425 return;
426 FOR_BB_INSNS (bb, insn)
427 if (NONDEBUG_INSN_P (insn))
428 add_insn_allocno_copies (insn);
429}
430
431/* Propagate copies the corresponding allocnos on upper loop tree
432 level. */
433static void
434propagate_copies (void)
435{
436 ira_copy_t cp;
437 ira_copy_iterator ci;
438 ira_allocno_t a1, a2, parent_a1, parent_a2;
439
440 FOR_EACH_COPY (cp, ci)
441 {
442 a1 = cp->first;
443 a2 = cp->second;
444 if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
445 continue;
446 ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
447 parent_a1 = ira_parent_or_cap_allocno (a1);
448 parent_a2 = ira_parent_or_cap_allocno (a2);
449 ira_assert (parent_a1 != NULL && parent_a2 != NULL);
450 if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
451 ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
452 cp->constraint_p, cp->insn, cp->loop_tree_node);
453 }
454}
455
456/* Array used to collect all conflict allocnos for given allocno. */
457static ira_object_t *collected_conflict_objects;
458
459/* Build conflict vectors or bit conflict vectors (whatever is more
460 profitable) for object OBJ from the conflict table. */
461static void
462build_object_conflicts (ira_object_t obj)
463{
464 int i, px, parent_num;
465 ira_allocno_t parent_a, another_parent_a;
466 ira_object_t parent_obj;
467 ira_allocno_t a = OBJECT_ALLOCNO (obj);
468 IRA_INT_TYPE *object_conflicts;
469 minmax_set_iterator asi;
470 int parent_min, parent_max ATTRIBUTE_UNUSED;
471
472 object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
473 px = 0;
474 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
475 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
476 {
477 ira_object_t another_obj = ira_object_id_map[i];
478 ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
479
480 ira_assert (ira_reg_classes_intersect_p
481 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
482 collected_conflict_objects[px++] = another_obj;
483 }
484 if (ira_conflict_vector_profitable_p (obj, px))
485 {
486 ira_object_t *vec;
487 ira_allocate_conflict_vec (obj, px);
488 vec = OBJECT_CONFLICT_VEC (obj);
489 memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
490 vec[px] = NULL;
491 OBJECT_NUM_CONFLICTS (obj) = px;
492 }
493 else
494 {
495 int conflict_bit_vec_words_num;
496
497 OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
498 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
499 conflict_bit_vec_words_num = 0;
500 else
501 conflict_bit_vec_words_num
502 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
503 / IRA_INT_BITS);
504 OBJECT_CONFLICT_ARRAY_SIZE (obj)
505 = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
506 }
507
508 parent_a = ira_parent_or_cap_allocno (a);
509 if (parent_a == NULL)
510 return;
511 ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
512 ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
513 parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
514 parent_num = OBJECT_CONFLICT_ID (parent_obj);
515 parent_min = OBJECT_MIN (parent_obj);
516 parent_max = OBJECT_MAX (parent_obj);
517 FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
518 OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
519 {
520 ira_object_t another_obj = ira_object_id_map[i];
521 ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
522 int another_word = OBJECT_SUBWORD (another_obj);
523
524 ira_assert (ira_reg_classes_intersect_p
525 [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
526
527 another_parent_a = ira_parent_or_cap_allocno (another_a);
528 if (another_parent_a == NULL)
529 continue;
530 ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
531 ira_assert (ALLOCNO_CLASS (another_a)
532 == ALLOCNO_CLASS (another_parent_a));
533 ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
534 == ALLOCNO_NUM_OBJECTS (another_parent_a));
535 SET_MINMAX_SET_BIT (conflicts[parent_num],
536 OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
537 another_word)),
538 parent_min, parent_max);
539 }
540}
541
542/* Build conflict vectors or bit conflict vectors (whatever is more
543 profitable) of all allocnos from the conflict table. */
544static void
545build_conflicts (void)
546{
547 int i;
548 ira_allocno_t a, cap;
549
550 collected_conflict_objects
551 = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
552 * ira_objects_num);
553 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
554 for (a = ira_regno_allocno_map[i];
555 a != NULL;
556 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
557 {
558 int j, nregs = ALLOCNO_NUM_OBJECTS (a);
559 for (j = 0; j < nregs; j++)
560 {
561 ira_object_t obj = ALLOCNO_OBJECT (a, j);
562 build_object_conflicts (obj);
563 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
564 {
565 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
566 gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
567 build_object_conflicts (cap_obj);
568 }
569 }
570 }
571 ira_free (collected_conflict_objects);
572}
573
574
575
576/* Print hard reg set SET with TITLE to FILE. */
577static void
578print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
579{
580 int i, start;
581
582 fputs (title, file);
583 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
584 {
585 if (TEST_HARD_REG_BIT (set, i))
586 {
587 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
588 start = i;
589 }
590 if (start >= 0
591 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
592 {
593 if (start == i - 1)
594 fprintf (file, " %d", start);
595 else if (start == i - 2)
596 fprintf (file, " %d %d", start, start + 1);
597 else
598 fprintf (file, " %d-%d", start, i - 1);
599 start = -1;
600 }
601 }
602 putc ('\n', file);
603}
604
605static void
606print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
607{
608 HARD_REG_SET conflicting_hard_regs;
609 basic_block bb;
610 int n, i;
611
612 if (reg_p)
613 fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
614 else
615 {
616 fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
617 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
618 fprintf (file, "b%d", bb->index);
619 else
620 fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
621 putc (')', file);
622 }
623
624 fputs (" conflicts:", file);
625 n = ALLOCNO_NUM_OBJECTS (a);
626 for (i = 0; i < n; i++)
627 {
628 ira_object_t obj = ALLOCNO_OBJECT (a, i);
629 ira_object_t conflict_obj;
630 ira_object_conflict_iterator oci;
631
632 if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
633 continue;
634 if (n > 1)
635 fprintf (file, "\n;; subobject %d:", i);
636 FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
637 {
638 ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
639 if (reg_p)
640 fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
641 else
642 {
643 fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
644 ALLOCNO_REGNO (conflict_a));
645 if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
646 fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
647 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
648 fprintf (file, ",b%d", bb->index);
649 else
650 fprintf (file, ",l%d",
651 ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
652 putc (')', file);
653 }
654 }
655 COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
656 AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
657 AND_HARD_REG_SET (conflicting_hard_regs,
658 reg_class_contents[ALLOCNO_CLASS (a)]);
659 print_hard_reg_set (file, "\n;; total conflict hard regs:",
660 conflicting_hard_regs);
661
662 COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_CONFLICT_HARD_REGS (obj));
663 AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
664 AND_HARD_REG_SET (conflicting_hard_regs,
665 reg_class_contents[ALLOCNO_CLASS (a)]);
666 print_hard_reg_set (file, ";; conflict hard regs:",
667 conflicting_hard_regs);
668 putc ('\n', file);
669 }
670
671}
672
673/* Print information about allocno or only regno (if REG_P) conflicts
674 to FILE. */
675static void
676print_conflicts (FILE *file, bool reg_p)
677{
678 ira_allocno_t a;
679 ira_allocno_iterator ai;
680
681 FOR_EACH_ALLOCNO (a, ai)
682 print_allocno_conflicts (file, reg_p, a);
683}
684
685/* Print information about allocno or only regno (if REG_P) conflicts
686 to stderr. */
687void
688ira_debug_conflicts (bool reg_p)
689{
690 print_conflicts (stderr, reg_p);
691}
692
693
694
695/* Entry function which builds allocno conflicts and allocno copies
696 and accumulate some allocno info on upper level regions. */
697void
698ira_build_conflicts (void)
699{
700 enum reg_class base;
701 ira_allocno_t a;
702 ira_allocno_iterator ai;
703 HARD_REG_SET temp_hard_reg_set;
704
705 if (ira_conflicts_p)
706 {
707 ira_conflicts_p = build_conflict_bit_table ();
708 if (ira_conflicts_p)
709 {
710 ira_object_t obj;
711 ira_object_iterator oi;
712
713 build_conflicts ();
714 ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
715 /* We need finished conflict table for the subsequent call. */
716 if (flag_ira_region == IRA_REGION_ALL
717 || flag_ira_region == IRA_REGION_MIXED)
718 propagate_copies ();
719
720 /* Now we can free memory for the conflict table (see function
721 build_object_conflicts for details). */
722 FOR_EACH_OBJECT (obj, oi)
723 {
724 if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
725 ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
726 }
727 ira_free (conflicts);
728 }
729 }
730 base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH);
731 if (! targetm.class_likely_spilled_p (base))
732 CLEAR_HARD_REG_SET (temp_hard_reg_set);
733 else
734 {
735 COPY_HARD_REG_SET (temp_hard_reg_set, reg_class_contents[base]);
736 AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs);
737 AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set);
738 }
739 FOR_EACH_ALLOCNO (a, ai)
740 {
741 int i, n = ALLOCNO_NUM_OBJECTS (a);
742
743 for (i = 0; i < n; i++)
744 {
745 ira_object_t obj = ALLOCNO_OBJECT (a, i);
746 machine_mode obj_mode = obj->allocno->mode;
747 rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
748
749 if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
750 /* For debugging purposes don't put user defined variables in
751 callee-clobbered registers. However, do allow parameters
752 in callee-clobbered registers to improve debugging. This
753 is a bit of a fragile hack. */
754 || (optimize == 0
755 && REG_USERVAR_P (allocno_reg)
756 && ! reg_is_parm_p (allocno_reg)))
757 {
758 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
759 call_used_reg_set);
760 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
761 call_used_reg_set);
762 }
763 else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
764 {
765 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
766 no_caller_save_reg_set);
767 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
768 temp_hard_reg_set);
769 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
770 no_caller_save_reg_set);
771 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
772 temp_hard_reg_set);
773 }
774
775 /* Now we deal with paradoxical subreg cases where certain registers
776 cannot be accessed in the widest mode. */
777 machine_mode outer_mode = ALLOCNO_WMODE (a);
778 machine_mode inner_mode = ALLOCNO_MODE (a);
779 if (paradoxical_subreg_p (outer_mode, inner_mode))
780 {
781 enum reg_class aclass = ALLOCNO_CLASS (a);
782 for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
783 {
784 int inner_regno = ira_class_hard_regs[aclass][j];
785 int outer_regno = simplify_subreg_regno (inner_regno,
786 inner_mode, 0,
787 outer_mode);
788 if (outer_regno < 0
789 || !in_hard_reg_set_p (reg_class_contents[aclass],
790 outer_mode, outer_regno))
791 {
792 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
793 inner_regno);
794 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
795 inner_regno);
796 }
797 }
798 }
799
800 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
801 {
802 int regno;
803
804 /* Allocnos bigger than the saved part of call saved
805 regs must conflict with them. */
806 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
807 if (!TEST_HARD_REG_BIT (call_used_reg_set, regno)
808 && targetm.hard_regno_call_part_clobbered (regno,
809 obj_mode))
810 {
811 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
812 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
813 regno);
814 }
815 }
816 }
817 }
818 if (optimize && ira_conflicts_p
819 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
820 print_conflicts (ira_dump_file, false);
821}
822