]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/ira-conflicts.c
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
2009-01-13 Vladimir Makarov <vmakarov@redhat.com>
[thirdparty/gcc.git] / gcc / ira-conflicts.c
CommitLineData
47dd2e78 1/* IRA conflict builder.
2 Copyright (C) 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "tm.h"
26#include "regs.h"
27#include "rtl.h"
28#include "tm_p.h"
29#include "target.h"
30#include "flags.h"
31#include "hard-reg-set.h"
32#include "basic-block.h"
33#include "insn-config.h"
34#include "recog.h"
35#include "toplev.h"
36#include "params.h"
37#include "df.h"
38#include "sparseset.h"
39#include "ira-int.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_allocno_conflicts. */
50static IRA_INT_TYPE **conflicts;
51
52/* Macro to test a conflict of A1 and A2 in `conflicts'. */
53#define CONFLICT_ALLOCNO_P(A1, A2) \
54 (ALLOCNO_MIN (A1) <= ALLOCNO_CONFLICT_ID (A2) \
55 && ALLOCNO_CONFLICT_ID (A2) <= ALLOCNO_MAX (A1) \
56 && TEST_ALLOCNO_SET_BIT (conflicts[ALLOCNO_NUM (A1)], \
57 ALLOCNO_CONFLICT_ID (A2), \
58 ALLOCNO_MIN (A1), \
59 ALLOCNO_MAX (A1)))
60
61\f
62
95c83f01 63/* Build allocno conflict table by processing allocno live ranges.
64 Return true if the table was built. The table is not built if it
65 is too big. */
66static bool
47dd2e78 67build_conflict_bit_table (void)
68{
69 int i, num, id, allocated_words_num, conflict_bit_vec_words_num;
70 unsigned int j;
71 enum reg_class cover_class;
72 ira_allocno_t allocno, live_a;
73 allocno_live_range_t r;
74 ira_allocno_iterator ai;
75 sparseset allocnos_live;
76 int allocno_set_words;
77
78 allocno_set_words = (ira_allocnos_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
95c83f01 79 allocated_words_num = 0;
80 FOR_EACH_ALLOCNO (allocno, ai)
81 {
82 if (ALLOCNO_MAX (allocno) < ALLOCNO_MIN (allocno))
83 continue;
84 conflict_bit_vec_words_num
85 = ((ALLOCNO_MAX (allocno) - ALLOCNO_MIN (allocno) + IRA_INT_BITS)
86 / IRA_INT_BITS);
87 allocated_words_num += conflict_bit_vec_words_num;
88 if ((unsigned long long) allocated_words_num * sizeof (IRA_INT_TYPE)
89 > (unsigned long long) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024)
90 {
91 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
92 fprintf
93 (ira_dump_file,
94 "+++Conflict table will be too big(>%dMB) -- don't use it\n",
95 IRA_MAX_CONFLICT_TABLE_SIZE);
96 return false;
97 }
98 }
47dd2e78 99 allocnos_live = sparseset_alloc (ira_allocnos_num);
100 conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
101 * ira_allocnos_num);
102 allocated_words_num = 0;
103 FOR_EACH_ALLOCNO (allocno, ai)
104 {
105 num = ALLOCNO_NUM (allocno);
106 if (ALLOCNO_MAX (allocno) < ALLOCNO_MIN (allocno))
107 {
108 conflicts[num] = NULL;
109 continue;
110 }
111 conflict_bit_vec_words_num
112 = ((ALLOCNO_MAX (allocno) - ALLOCNO_MIN (allocno) + IRA_INT_BITS)
113 / IRA_INT_BITS);
114 allocated_words_num += conflict_bit_vec_words_num;
115 conflicts[num]
116 = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
117 * conflict_bit_vec_words_num);
118 memset (conflicts[num], 0,
119 sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
120 }
121 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
122 fprintf
123 (ira_dump_file,
124 "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n",
125 (long) allocated_words_num * sizeof (IRA_INT_TYPE),
126 (long) allocno_set_words * ira_allocnos_num * sizeof (IRA_INT_TYPE));
127 for (i = 0; i < ira_max_point; i++)
128 {
129 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
130 {
131 allocno = r->allocno;
132 num = ALLOCNO_NUM (allocno);
133 id = ALLOCNO_CONFLICT_ID (allocno);
134 cover_class = ALLOCNO_COVER_CLASS (allocno);
135 sparseset_set_bit (allocnos_live, num);
136 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, j)
137 {
138 live_a = ira_allocnos[j];
14792f4e 139 if (ira_reg_classes_intersect_p
140 [cover_class][ALLOCNO_COVER_CLASS (live_a)]
47dd2e78 141 /* Don't set up conflict for the allocno with itself. */
142 && num != (int) j)
143 {
144 SET_ALLOCNO_SET_BIT (conflicts[num],
145 ALLOCNO_CONFLICT_ID (live_a),
146 ALLOCNO_MIN (allocno),
147 ALLOCNO_MAX (allocno));
148 SET_ALLOCNO_SET_BIT (conflicts[j], id,
149 ALLOCNO_MIN (live_a),
150 ALLOCNO_MAX (live_a));
151 }
152 }
153 }
154
155 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
156 sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
157 }
158 sparseset_free (allocnos_live);
95c83f01 159 return true;
47dd2e78 160}
161
162\f
163
164/* Return TRUE if the operand constraint STR is commutative. */
165static bool
166commutative_constraint_p (const char *str)
167{
168 bool ignore_p;
169 int c;
170
171 for (ignore_p = false;;)
172 {
173 c = *str;
174 if (c == '\0')
175 break;
176 str += CONSTRAINT_LEN (c, str);
177 if (c == '#')
178 ignore_p = true;
179 else if (c == ',')
180 ignore_p = false;
181 else if (! ignore_p)
182 {
183 /* Usually `%' is the first constraint character but the
184 documentation does not require this. */
185 if (c == '%')
186 return true;
187 }
188 }
189 return false;
190}
191
192/* Return the number of the operand which should be the same in any
193 case as operand with number OP_NUM (or negative value if there is
194 no such operand). If USE_COMMUT_OP_P is TRUE, the function makes
195 temporarily commutative operand exchange before this. The function
196 takes only really possible alternatives into consideration. */
197static int
198get_dup_num (int op_num, bool use_commut_op_p)
199{
200 int curr_alt, c, original, dup;
201 bool ignore_p, commut_op_used_p;
202 const char *str;
203 rtx op;
204
205 if (op_num < 0 || recog_data.n_alternatives == 0)
206 return -1;
207 op = recog_data.operand[op_num];
47dd2e78 208 commut_op_used_p = true;
209 if (use_commut_op_p)
210 {
211 if (commutative_constraint_p (recog_data.constraints[op_num]))
212 op_num++;
213 else if (op_num > 0 && commutative_constraint_p (recog_data.constraints
214 [op_num - 1]))
215 op_num--;
216 else
217 commut_op_used_p = false;
218 }
219 str = recog_data.constraints[op_num];
220 for (ignore_p = false, original = -1, curr_alt = 0;;)
221 {
222 c = *str;
223 if (c == '\0')
224 break;
225 if (c == '#')
226 ignore_p = true;
227 else if (c == ',')
228 {
229 curr_alt++;
230 ignore_p = false;
231 }
232 else if (! ignore_p)
233 switch (c)
234 {
235 case 'X':
236 return -1;
237
238 case 'm':
239 case 'o':
240 /* Accept a register which might be placed in memory. */
241 return -1;
242 break;
243
244 case 'V':
245 case '<':
246 case '>':
247 break;
248
249 case 'p':
250 GO_IF_LEGITIMATE_ADDRESS (VOIDmode, op, win_p);
251 break;
252
253 win_p:
254 return -1;
255
256 case 'g':
257 return -1;
258
259 case 'r':
260 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
261 case 'h': case 'j': case 'k': case 'l':
262 case 'q': case 't': case 'u':
263 case 'v': case 'w': case 'x': case 'y': case 'z':
264 case 'A': case 'B': case 'C': case 'D':
265 case 'Q': case 'R': case 'S': case 'T': case 'U':
266 case 'W': case 'Y': case 'Z':
267 {
268 enum reg_class cl;
269
270 cl = (c == 'r'
271 ? GENERAL_REGS : REG_CLASS_FROM_CONSTRAINT (c, str));
272 if (cl != NO_REGS)
273 return -1;
274#ifdef EXTRA_CONSTRAINT_STR
275 else if (EXTRA_CONSTRAINT_STR (op, c, str))
276 return -1;
277#endif
278 break;
279 }
280
281 case '0': case '1': case '2': case '3': case '4':
282 case '5': case '6': case '7': case '8': case '9':
283 if (original != -1 && original != c)
284 return -1;
285 original = c;
286 break;
287 }
288 str += CONSTRAINT_LEN (c, str);
289 }
290 if (original == -1)
291 return -1;
292 dup = original - '0';
293 if (use_commut_op_p)
294 {
295 if (commutative_constraint_p (recog_data.constraints[dup]))
296 dup++;
297 else if (dup > 0
298 && commutative_constraint_p (recog_data.constraints[dup -1]))
299 dup--;
300 else if (! commut_op_used_p)
301 return -1;
302 }
303 return dup;
304}
305
306/* Return the operand which should be, in any case, the same as
307 operand with number OP_NUM. If USE_COMMUT_OP_P is TRUE, the
308 function makes temporarily commutative operand exchange before
309 this. */
310static rtx
311get_dup (int op_num, bool use_commut_op_p)
312{
313 int n = get_dup_num (op_num, use_commut_op_p);
314
315 if (n < 0)
316 return NULL_RTX;
317 else
318 return recog_data.operand[n];
319}
320
f0a46d83 321/* Check that X is REG or SUBREG of REG. */
322#define REG_SUBREG_P(x) \
323 (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
324
325/* Return X if X is a REG, otherwise it should be SUBREG of REG and
326 the function returns the reg in this case. *OFFSET will be set to
327 0 in the first case or the regno offset in the first case. */
328static rtx
329go_through_subreg (rtx x, int *offset)
330{
331 rtx reg;
332
333 *offset = 0;
334 if (REG_P (x))
335 return x;
336 ira_assert (GET_CODE (x) == SUBREG);
337 reg = SUBREG_REG (x);
338 ira_assert (REG_P (reg));
339 if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
340 *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
341 SUBREG_BYTE (x), GET_MODE (x));
342 else
343 *offset = (SUBREG_BYTE (x) / REGMODE_NATURAL_SIZE (GET_MODE (x)));
344 return reg;
345}
346
47dd2e78 347/* Process registers REG1 and REG2 in move INSN with execution
348 frequency FREQ. The function also processes the registers in a
349 potential move insn (INSN == NULL in this case) with frequency
350 FREQ. The function can modify hard register costs of the
351 corresponding allocnos or create a copy involving the corresponding
352 allocnos. The function does nothing if the both registers are hard
353 registers. When nothing is changed, the function returns
354 FALSE. */
355static bool
b7c06809 356process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
357 rtx insn, int freq)
47dd2e78 358{
296a743c 359 int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
f0a46d83 360 bool only_regs_p;
47dd2e78 361 ira_allocno_t a;
362 enum reg_class rclass, cover_class;
363 enum machine_mode mode;
364 ira_copy_t cp;
df07a54c 365 ira_loop_tree_node_t parent;
47dd2e78 366
f0a46d83 367 gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
368 only_regs_p = REG_P (reg1) && REG_P (reg2);
369 reg1 = go_through_subreg (reg1, &offset1);
370 reg2 = go_through_subreg (reg2, &offset2);
296a743c 371 /* Set up hard regno preferenced by allocno. If allocno gets the
372 hard regno the copy (or potential move) insn will be removed. */
47dd2e78 373 if (HARD_REGISTER_P (reg1))
374 {
375 if (HARD_REGISTER_P (reg2))
376 return false;
296a743c 377 allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
47dd2e78 378 a = ira_curr_regno_allocno_map[REGNO (reg2)];
379 }
380 else if (HARD_REGISTER_P (reg2))
381 {
296a743c 382 allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
47dd2e78 383 a = ira_curr_regno_allocno_map[REGNO (reg1)];
384 }
385 else if (!CONFLICT_ALLOCNO_P (ira_curr_regno_allocno_map[REGNO (reg1)],
f0a46d83 386 ira_curr_regno_allocno_map[REGNO (reg2)])
387 && offset1 == offset2)
47dd2e78 388 {
389 cp = ira_add_allocno_copy (ira_curr_regno_allocno_map[REGNO (reg1)],
390 ira_curr_regno_allocno_map[REGNO (reg2)],
b7c06809 391 freq, constraint_p, insn,
392 ira_curr_loop_tree_node);
47dd2e78 393 bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
394 return true;
395 }
396 else
397 return false;
296a743c 398 if (! IN_RANGE (allocno_preferenced_hard_regno, 0, FIRST_PSEUDO_REGISTER - 1))
399 /* Can not be tied. */
400 return false;
401 rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
47dd2e78 402 mode = ALLOCNO_MODE (a);
403 cover_class = ALLOCNO_COVER_CLASS (a);
55c858c5 404 if (only_regs_p && insn != NULL_RTX
405 && reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode))
47dd2e78 406 /* It is already taken into account in ira-costs.c. */
407 return false;
296a743c 408 index = ira_class_hard_reg_index[cover_class][allocno_preferenced_hard_regno];
47dd2e78 409 if (index < 0)
296a743c 410 /* Can not be tied. It is not in the cover class. */
47dd2e78 411 return false;
412 if (HARD_REGISTER_P (reg1))
413 cost = ira_register_move_cost[mode][cover_class][rclass] * freq;
414 else
415 cost = ira_register_move_cost[mode][rclass][cover_class] * freq;
df07a54c 416 for (;;)
417 {
418 ira_allocate_and_set_costs
419 (&ALLOCNO_HARD_REG_COSTS (a), cover_class,
420 ALLOCNO_COVER_CLASS_COST (a));
421 ira_allocate_and_set_costs
422 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class, 0);
423 ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
424 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost;
425 if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_COVER_CLASS_COST (a))
426 ALLOCNO_COVER_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
427 if (ALLOCNO_CAP (a) != NULL)
428 a = ALLOCNO_CAP (a);
429 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
430 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
431 break;
432 }
47dd2e78 433 return true;
434}
435
436/* Process all of the output registers of the current insn and
437 the input register REG (its operand number OP_NUM) which dies in the
438 insn as if there were a move insn between them with frequency
439 FREQ. */
440static void
441process_reg_shuffles (rtx reg, int op_num, int freq)
442{
443 int i;
444 rtx another_reg;
445
f0a46d83 446 gcc_assert (REG_SUBREG_P (reg));
47dd2e78 447 for (i = 0; i < recog_data.n_operands; i++)
448 {
449 another_reg = recog_data.operand[i];
450
f0a46d83 451 if (!REG_SUBREG_P (another_reg) || op_num == i
47dd2e78 452 || recog_data.operand_type[i] != OP_OUT)
453 continue;
454
b7c06809 455 process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq);
47dd2e78 456 }
457}
458
459/* Process INSN and create allocno copies if necessary. For example,
460 it might be because INSN is a pseudo-register move or INSN is two
461 operand insn. */
462static void
463add_insn_allocno_copies (rtx insn)
464{
465 rtx set, operand, dup;
466 const char *str;
467 bool commut_p, bound_p;
468 int i, j, freq;
469
470 freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
471 if (freq == 0)
472 freq = 1;
473 if ((set = single_set (insn)) != NULL_RTX
f0a46d83 474 && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
47dd2e78 475 && ! side_effects_p (set)
f0a46d83 476 && find_reg_note (insn, REG_DEAD,
477 REG_P (SET_SRC (set))
478 ? SET_SRC (set)
479 : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
b7c06809 480 process_regs_for_copy (SET_DEST (set), SET_SRC (set), false, insn, freq);
47dd2e78 481 else
482 {
483 extract_insn (insn);
484 for (i = 0; i < recog_data.n_operands; i++)
485 {
486 operand = recog_data.operand[i];
f0a46d83 487 if (REG_SUBREG_P (operand)
488 && find_reg_note (insn, REG_DEAD,
489 REG_P (operand)
490 ? operand : SUBREG_REG (operand)) != NULL_RTX)
47dd2e78 491 {
492 str = recog_data.constraints[i];
493 while (*str == ' ' && *str == '\t')
494 str++;
495 bound_p = false;
496 for (j = 0, commut_p = false; j < 2; j++, commut_p = true)
497 if ((dup = get_dup (i, commut_p)) != NULL_RTX
f0a46d83 498 && REG_SUBREG_P (dup)
b7c06809 499 && process_regs_for_copy (operand, dup, true,
500 NULL_RTX, freq))
47dd2e78 501 bound_p = true;
502 if (bound_p)
503 continue;
504 /* If an operand dies, prefer its hard register for the
505 output operands by decreasing the hard register cost
506 or creating the corresponding allocno copies. The
507 cost will not correspond to a real move insn cost, so
508 make the frequency smaller. */
509 process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8);
510 }
511 }
512 }
513}
514
515/* Add copies originated from BB given by LOOP_TREE_NODE. */
516static void
517add_copies (ira_loop_tree_node_t loop_tree_node)
518{
519 basic_block bb;
520 rtx insn;
521
522 bb = loop_tree_node->bb;
523 if (bb == NULL)
524 return;
525 FOR_BB_INSNS (bb, insn)
526 if (INSN_P (insn))
527 add_insn_allocno_copies (insn);
528}
529
530/* Propagate copies the corresponding allocnos on upper loop tree
531 level. */
532static void
533propagate_copies (void)
534{
535 ira_copy_t cp;
536 ira_copy_iterator ci;
537 ira_allocno_t a1, a2, parent_a1, parent_a2;
538 ira_loop_tree_node_t parent;
539
540 FOR_EACH_COPY (cp, ci)
541 {
542 a1 = cp->first;
543 a2 = cp->second;
544 if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
545 continue;
546 ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
547 parent = ALLOCNO_LOOP_TREE_NODE (a1)->parent;
548 if ((parent_a1 = ALLOCNO_CAP (a1)) == NULL)
549 parent_a1 = parent->regno_allocno_map[ALLOCNO_REGNO (a1)];
550 if ((parent_a2 = ALLOCNO_CAP (a2)) == NULL)
551 parent_a2 = parent->regno_allocno_map[ALLOCNO_REGNO (a2)];
552 ira_assert (parent_a1 != NULL && parent_a2 != NULL);
553 if (! CONFLICT_ALLOCNO_P (parent_a1, parent_a2))
b7c06809 554 ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
555 cp->constraint_p, cp->insn, cp->loop_tree_node);
47dd2e78 556 }
557}
558
47dd2e78 559/* Array used to collect all conflict allocnos for given allocno. */
560static ira_allocno_t *collected_conflict_allocnos;
561
562/* Build conflict vectors or bit conflict vectors (whatever is more
563 profitable) for allocno A from the conflict table and propagate the
564 conflicts to upper level allocno. */
565static void
566build_allocno_conflicts (ira_allocno_t a)
567{
568 int i, px, parent_num;
569 int conflict_bit_vec_words_num;
570 ira_loop_tree_node_t parent;
571 ira_allocno_t parent_a, another_a, another_parent_a;
572 ira_allocno_t *vec;
573 IRA_INT_TYPE *allocno_conflicts;
574 ira_allocno_set_iterator asi;
575
576 allocno_conflicts = conflicts[ALLOCNO_NUM (a)];
577 px = 0;
578 FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
579 ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
580 {
581 another_a = ira_conflict_id_allocno_map[i];
14792f4e 582 ira_assert (ira_reg_classes_intersect_p
583 [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
47dd2e78 584 collected_conflict_allocnos[px++] = another_a;
585 }
586 if (ira_conflict_vector_profitable_p (a, px))
587 {
588 ira_allocate_allocno_conflict_vec (a, px);
589 vec = (ira_allocno_t*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
590 memcpy (vec, collected_conflict_allocnos, sizeof (ira_allocno_t) * px);
591 vec[px] = NULL;
592 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = px;
593 }
594 else
595 {
596 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = conflicts[ALLOCNO_NUM (a)];
597 if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
598 conflict_bit_vec_words_num = 0;
599 else
600 conflict_bit_vec_words_num
601 = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + IRA_INT_BITS)
602 / IRA_INT_BITS);
603 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a)
604 = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
605 }
606 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
607 if ((parent_a = ALLOCNO_CAP (a)) == NULL
608 && (parent == NULL
609 || (parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
610 == NULL))
611 return;
612 ira_assert (parent != NULL);
613 ira_assert (ALLOCNO_COVER_CLASS (a) == ALLOCNO_COVER_CLASS (parent_a));
614 parent_num = ALLOCNO_NUM (parent_a);
615 FOR_EACH_ALLOCNO_IN_SET (allocno_conflicts,
616 ALLOCNO_MIN (a), ALLOCNO_MAX (a), i, asi)
617 {
618 another_a = ira_conflict_id_allocno_map[i];
14792f4e 619 ira_assert (ira_reg_classes_intersect_p
620 [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
47dd2e78 621 if ((another_parent_a = ALLOCNO_CAP (another_a)) == NULL
622 && (another_parent_a = (parent->regno_allocno_map
623 [ALLOCNO_REGNO (another_a)])) == NULL)
624 continue;
625 ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
626 ira_assert (ALLOCNO_COVER_CLASS (another_a)
627 == ALLOCNO_COVER_CLASS (another_parent_a));
628 SET_ALLOCNO_SET_BIT (conflicts[parent_num],
629 ALLOCNO_CONFLICT_ID (another_parent_a),
630 ALLOCNO_MIN (parent_a),
631 ALLOCNO_MAX (parent_a));
632 }
633}
634
635/* Build conflict vectors or bit conflict vectors (whatever is more
636 profitable) of all allocnos from the conflict table. */
637static void
638build_conflicts (void)
639{
640 int i;
641 ira_allocno_t a, cap;
642
643 collected_conflict_allocnos
644 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
645 * ira_allocnos_num);
646 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
647 for (a = ira_regno_allocno_map[i];
648 a != NULL;
649 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
650 {
651 build_allocno_conflicts (a);
652 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
653 build_allocno_conflicts (cap);
654 }
655 ira_free (collected_conflict_allocnos);
656}
657
658\f
659
660/* Print hard reg set SET with TITLE to FILE. */
661static void
662print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
663{
664 int i, start;
665
666 fprintf (file, title);
667 for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
668 {
669 if (TEST_HARD_REG_BIT (set, i))
670 {
671 if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1))
672 start = i;
673 }
674 if (start >= 0
675 && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i)))
676 {
677 if (start == i - 1)
678 fprintf (file, " %d", start);
679 else if (start == i - 2)
680 fprintf (file, " %d %d", start, start + 1);
681 else
682 fprintf (file, " %d-%d", start, i - 1);
683 start = -1;
684 }
685 }
686 fprintf (file, "\n");
687}
688
689/* Print information about allocno or only regno (if REG_P) conflicts
690 to FILE. */
691static void
692print_conflicts (FILE *file, bool reg_p)
693{
694 ira_allocno_t a;
695 ira_allocno_iterator ai;
696 HARD_REG_SET conflicting_hard_regs;
697
698 FOR_EACH_ALLOCNO (a, ai)
699 {
700 ira_allocno_t conflict_a;
701 ira_allocno_conflict_iterator aci;
702 basic_block bb;
703
704 if (reg_p)
705 fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
706 else
707 {
708 fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
709 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
710 fprintf (file, "b%d", bb->index);
711 else
712 fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
713 fprintf (file, ")");
714 }
715 fprintf (file, " conflicts:");
716 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
717 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
718 {
719 if (reg_p)
720 fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
721 else
722 {
723 fprintf (file, " a%d(r%d,", ALLOCNO_NUM (conflict_a),
724 ALLOCNO_REGNO (conflict_a));
725 if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
726 fprintf (file, "b%d)", bb->index);
727 else
728 fprintf (file, "l%d)",
729 ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop->num);
730 }
731 }
732 COPY_HARD_REG_SET (conflicting_hard_regs,
733 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
734 AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
735 AND_HARD_REG_SET (conflicting_hard_regs,
736 reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
737 print_hard_reg_set (file, "\n;; total conflict hard regs:",
738 conflicting_hard_regs);
739 COPY_HARD_REG_SET (conflicting_hard_regs,
740 ALLOCNO_CONFLICT_HARD_REGS (a));
741 AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs);
742 AND_HARD_REG_SET (conflicting_hard_regs,
743 reg_class_contents[ALLOCNO_COVER_CLASS (a)]);
744 print_hard_reg_set (file, ";; conflict hard regs:",
745 conflicting_hard_regs);
746 }
747 fprintf (file, "\n");
748}
749
750/* Print information about allocno or only regno (if REG_P) conflicts
751 to stderr. */
752void
753ira_debug_conflicts (bool reg_p)
754{
755 print_conflicts (stderr, reg_p);
756}
757
758\f
759
760/* Entry function which builds allocno conflicts and allocno copies
761 and accumulate some allocno info on upper level regions. */
762void
763ira_build_conflicts (void)
764{
765 ira_allocno_t a;
766 ira_allocno_iterator ai;
14792f4e 767 HARD_REG_SET temp_hard_reg_set;
47dd2e78 768
95c83f01 769 if (ira_conflicts_p)
47dd2e78 770 {
95c83f01 771 ira_conflicts_p = build_conflict_bit_table ();
772 if (ira_conflicts_p)
47dd2e78 773 {
95c83f01 774 build_conflicts ();
775 ira_traverse_loop_tree (true, ira_loop_tree_root, NULL, add_copies);
776 /* We need finished conflict table for the subsequent call. */
777 if (flag_ira_region == IRA_REGION_ALL
778 || flag_ira_region == IRA_REGION_MIXED)
779 propagate_copies ();
780 /* Now we can free memory for the conflict table (see function
781 build_allocno_conflicts for details). */
782 FOR_EACH_ALLOCNO (a, ai)
783 {
784 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a)
785 != conflicts[ALLOCNO_NUM (a)])
786 ira_free (conflicts[ALLOCNO_NUM (a)]);
787 }
788 ira_free (conflicts);
47dd2e78 789 }
47dd2e78 790 }
14792f4e 791 if (! CLASS_LIKELY_SPILLED_P (BASE_REG_CLASS))
792 CLEAR_HARD_REG_SET (temp_hard_reg_set);
793 else
794 {
95c83f01 795 COPY_HARD_REG_SET (temp_hard_reg_set,
796 reg_class_contents[BASE_REG_CLASS]);
14792f4e 797 AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs);
798 AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set);
799 }
47dd2e78 800 FOR_EACH_ALLOCNO (a, ai)
801 {
802 if (ALLOCNO_CALLS_CROSSED_NUM (a) == 0)
803 continue;
804 if (! flag_caller_saves)
805 {
806 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
807 call_used_reg_set);
808 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
809 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
810 call_used_reg_set);
811 }
812 else
813 {
814 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
815 no_caller_save_reg_set);
14792f4e 816 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
817 temp_hard_reg_set);
47dd2e78 818 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
14792f4e 819 {
820 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
821 no_caller_save_reg_set);
822 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
823 temp_hard_reg_set);
824 }
47dd2e78 825 }
826 }
95c83f01 827 if (optimize && ira_conflicts_p
828 && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
47dd2e78 829 print_conflicts (ira_dump_file, false);
830}
Mirror of https://gcc.gnu.org/git/gcc.git