1 /* IRA conflict builder.
2 Copyright (C) 2006-2014 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 "tm.h"
25 #include "regs.h"
26 #include "rtl.h"
27 #include "tm_p.h"
28 #include "target.h"
29 #include "flags.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
32 #include "insn-config.h"
33 #include "recog.h"
34 #include "diagnostic-core.h"
35 #include "params.h"
36 #include "df.h"
37 #include "sparseset.h"
38 #include "ira-int.h"
39 #include "addresses.h"
40
41 /* This file contains code responsible for allocno conflict creation,
42 allocno copy creation and allocno info accumulation on upper level
43 regions. */
44
45 /* ira_allocnos_num array of arrays of bits, recording whether two
46 allocno's conflict (can't go in the same hardware register).
47
48 Some arrays will be used as conflict bit vector of the
49 corresponding allocnos see function build_object_conflicts. */
50 static IRA_INT_TYPE **conflicts;
51
52 /* Macro to test a conflict of C1 and C2 in `conflicts'. */
53 #define OBJECTS_CONFLICT_P(C1, C2) \
54 (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2) \
55 && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1) \
56 && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)], \
57 OBJECT_CONFLICT_ID (C2), \
58 OBJECT_MIN (C1), OBJECT_MAX (C1)))
59
60
61 /* Record a conflict between objects OBJ1 and OBJ2. If necessary,
62 canonicalize the conflict by recording it for lower-order subobjects
63 of the corresponding allocnos. */
64 static void
record_object_conflict(ira_object_t obj1,ira_object_t obj2)65 record_object_conflict (ira_object_t obj1, ira_object_t obj2)
66 {
67 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
68 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
69 int w1 = OBJECT_SUBWORD (obj1);
70 int w2 = OBJECT_SUBWORD (obj2);
71 int id1, id2;
72
73 /* Canonicalize the conflict. If two identically-numbered words
74 conflict, always record this as a conflict between words 0. That
75 is the only information we need, and it is easier to test for if
76 it is collected in each allocno's lowest-order object. */
77 if (w1 == w2 && w1 > 0)
78 {
79 obj1 = ALLOCNO_OBJECT (a1, 0);
80 obj2 = ALLOCNO_OBJECT (a2, 0);
81 }
82 id1 = OBJECT_CONFLICT_ID (obj1);
83 id2 = OBJECT_CONFLICT_ID (obj2);
84
85 SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
86 OBJECT_MAX (obj1));
87 SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
88 OBJECT_MAX (obj2));
89 }
90
91 /* Build allocno conflict table by processing allocno live ranges.
92 Return true if the table was built. The table is not built if it
93 is too big. */
94 static bool
build_conflict_bit_table(void)95 build_conflict_bit_table (void)
96 {
97 int i;
98 unsigned int j;
99 enum reg_class aclass;
100 int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
101 live_range_t r;
102 ira_allocno_t allocno;
103 ira_allocno_iterator ai;
104 sparseset objects_live;
105 ira_object_t obj;
106 ira_allocno_object_iterator aoi;
107
108 allocated_words_num = 0;
109 FOR_EACH_ALLOCNO (allocno, ai)
110 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
111 {
112 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
113 continue;
114 conflict_bit_vec_words_num
115 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
116 / IRA_INT_BITS);
117 allocated_words_num += conflict_bit_vec_words_num;
118 if ((unsigned HOST_WIDEST_INT) allocated_words_num * sizeof (IRA_INT_TYPE)
119 > (unsigned HOST_WIDEST_INT) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024)
120 {
121 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
122 fprintf
123 (ira_dump_file,
124 "+++Conflict table will be too big(>%dMB) -- don't use it\n",
125 IRA_MAX_CONFLICT_TABLE_SIZE);
126 return false;
127 }
128 }
129
130 conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
131 * ira_objects_num);
132 allocated_words_num = 0;
133 FOR_EACH_ALLOCNO (allocno, ai)
134 FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
135 {
136 int id = OBJECT_CONFLICT_ID (obj);
137 if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
138 {
139 conflicts[id] = NULL;
140 continue;
141 }
142 conflict_bit_vec_words_num
143 = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
144 / IRA_INT_BITS);
145 allocated_words_num += conflict_bit_vec_words_num;
146 conflicts[id]
147 = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
148 * conflict_bit_vec_words_num);
149 memset (conflicts[id], 0,
150 sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
151 }
152
153 object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
154 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
155 fprintf
156 (ira_dump_file,
157 "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
158 (long) allocated_words_num * sizeof (IRA_INT_TYPE),
159 (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE));
160
161 objects_live = sparseset_alloc (ira_objects_num);
162 for (i = 0; i < ira_max_point; i++)
163 {
164 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
165 {
166 ira_object_t obj = r->object;
167 ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
168 int id = OBJECT_CONFLICT_ID (obj);
169
170 gcc_assert (id < ira_objects_num);
171
172 aclass = ALLOCNO_CLASS (allocno);
173 sparseset_set_bit (objects_live, id);
174 EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
175 {
176 ira_object_t live_obj = ira_object_id_map[j];
177 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
178 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
179
180 if (ira_reg_classes_intersect_p[aclass][live_aclass]
181 /* Don't set up conflict for the allocno with itself. */
182 && live_a != allocno)
183 {
184 record_object_conflict (obj, live_obj);
185 }
186 }
187 }
188
189 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
190 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
191 }
192 sparseset_free (objects_live);
193 return true;
194 }
195
196 /* Return true iff allocnos A1 and A2 cannot be allocated to the same
197 register due to conflicts. */
198
199 static bool
allocnos_conflict_for_copy_p(ira_allocno_t a1,ira_allocno_t a2)200 allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
201 {
202 /* Due to the fact that we canonicalize conflicts (see
203 record_object_conflict), we only need to test for conflicts of
204 the lowest order words. */
205 ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
206 ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
207
208 return OBJECTS_CONFLICT_P (obj1, obj2);
209 }
210
211 /* Check that X is REG or SUBREG of REG. */
212 #define REG_SUBREG_P(x) \
213 (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
214
215 /* Return X if X is a REG, otherwise it should be SUBREG of REG and
216 the function returns the reg in this case. *OFFSET will be set to
217 0 in the first case or the regno offset in the first case. */
218 static rtx
go_through_subreg(rtx x,int * offset)219 go_through_subreg (rtx x, int *offset)
220 {
221 rtx reg;
222
223 *offset = 0;
224 if (REG_P (x))
225 return x;
226 ira_assert (GET_CODE (x) == SUBREG);
227 reg = SUBREG_REG (x);
228 ira_assert (REG_P (reg));
229 if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
230 *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
231 SUBREG_BYTE (x), GET_MODE (x));
232 else
233 *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
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,int freq)246 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
247 rtx 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 enum 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_RTX, 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)356 add_insn_allocno_copies (rtx 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_RTX,
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;
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 rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
750
751 if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
752 /* For debugging purposes don't put user defined variables in
753 callee-clobbered registers. However, do allow parameters
754 in callee-clobbered registers to improve debugging. This
755 is a bit of a fragile hack. */
756 || (optimize == 0
757 && REG_USERVAR_P (allocno_reg)
758 && ! reg_is_parm_p (allocno_reg)))
759 {
760 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
761 call_used_reg_set);
762 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
763 call_used_reg_set);
764 }
765 else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
766 {
767 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
768 no_caller_save_reg_set);
769 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
770 temp_hard_reg_set);
771 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
772 no_caller_save_reg_set);
773 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
774 temp_hard_reg_set);
775 }
776
777 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
778 {
779 int regno;
780
781 /* Allocnos bigger than the saved part of call saved
782 regs must conflict with them. */
783 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
784 if (!TEST_HARD_REG_BIT (call_used_reg_set, regno)
785 && HARD_REGNO_CALL_PART_CLOBBERED (regno,
786 obj->allocno->mode))
787 {
788 SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno);
789 SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
790 regno);
791 }
792 }
793 }
794 }
795 if (optimize && ira_conflicts_p
796 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
797 print_conflicts (ira_dump_file, false);
798 }
799