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