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