OSDN Git Service

244d3bc9b3ef2ecc299e5ee5a962a9b4becc5df0
[pf3gnuchains/gcc-fork.git] / gcc / ira-conflicts.c
1 /* IRA conflict builder.
2    Copyright (C) 2006, 2007, 2008
3    Free Software Foundation, Inc.
4    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along 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.  */
50 static 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.
64    Return true if the table was built.  The table is not built if it
65    is too big.  */
66 static bool
67 build_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;
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     }
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];
139               if (ira_reg_classes_intersect_p
140                   [cover_class][ALLOCNO_COVER_CLASS (live_a)]
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);
159   return true;
160 }
161
162 \f
163
164 /* Return TRUE if the operand constraint STR is commutative.  */
165 static bool
166 commutative_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.  */
197 static int
198 get_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];
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.  */
310 static rtx
311 get_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
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.  */
328 static rtx
329 go_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
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.  */
355 static bool
356 process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p,
357                        rtx insn, int freq)
358 {
359   int allocno_preferenced_hard_regno, cost, index, offset1, offset2;
360   bool only_regs_p;
361   ira_allocno_t a;
362   enum reg_class rclass, cover_class;
363   enum machine_mode mode;
364   ira_copy_t cp;
365   ira_loop_tree_node_t parent;
366
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);
371   /* Set up hard regno preferenced by allocno.  If allocno gets the
372      hard regno the copy (or potential move) insn will be removed.  */
373   if (HARD_REGISTER_P (reg1))
374     {
375       if (HARD_REGISTER_P (reg2))
376         return false;
377       allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
378       a = ira_curr_regno_allocno_map[REGNO (reg2)];
379     }
380   else if (HARD_REGISTER_P (reg2))
381     {
382       allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
383       a = ira_curr_regno_allocno_map[REGNO (reg1)];
384     }
385   else if (!CONFLICT_ALLOCNO_P (ira_curr_regno_allocno_map[REGNO (reg1)],
386                                 ira_curr_regno_allocno_map[REGNO (reg2)])
387            && offset1 == offset2)
388     {
389       cp = ira_add_allocno_copy (ira_curr_regno_allocno_map[REGNO (reg1)],
390                                  ira_curr_regno_allocno_map[REGNO (reg2)],
391                                  freq, constraint_p, insn,
392                                  ira_curr_loop_tree_node);
393       bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num); 
394       return true;
395     }
396   else
397     return false;
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);
402   mode = ALLOCNO_MODE (a);
403   cover_class = ALLOCNO_COVER_CLASS (a);
404   if (only_regs_p && insn != NULL_RTX
405       && reg_class_size[rclass] <= (unsigned) CLASS_MAX_NREGS (rclass, mode))
406     /* It is already taken into account in ira-costs.c.  */
407     return false;
408   index = ira_class_hard_reg_index[cover_class][allocno_preferenced_hard_regno];
409   if (index < 0)
410     /* Can not be tied.  It is not in the cover class.  */
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;
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     }
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.  */
440 static void
441 process_reg_shuffles (rtx reg, int op_num, int freq)
442 {
443   int i;
444   rtx another_reg;
445
446   gcc_assert (REG_SUBREG_P (reg));
447   for (i = 0; i < recog_data.n_operands; i++)
448     {
449       another_reg = recog_data.operand[i];
450       
451       if (!REG_SUBREG_P (another_reg) || op_num == i
452           || recog_data.operand_type[i] != OP_OUT)
453         continue;
454       
455       process_regs_for_copy (reg, another_reg, false, NULL_RTX, freq);
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.  */
462 static void
463 add_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
474       && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
475       && ! side_effects_p (set)
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)
480     process_regs_for_copy (SET_DEST (set), SET_SRC (set), false, insn, freq);
481   else
482     {
483       extract_insn (insn);
484       for (i = 0; i < recog_data.n_operands; i++)
485         {
486           operand = recog_data.operand[i];
487           if (REG_SUBREG_P (operand)
488               && find_reg_note (insn, REG_DEAD,
489                                 REG_P (operand)
490                                 ? operand : SUBREG_REG (operand)) != NULL_RTX)
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
498                     && REG_SUBREG_P (dup)
499                     && process_regs_for_copy (operand, dup, true,
500                                               NULL_RTX, freq))
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.  */
516 static void
517 add_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.  */
532 static void
533 propagate_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))
554         ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
555                               cp->constraint_p, cp->insn, cp->loop_tree_node);
556     }
557 }
558
559 /* Array used to collect all conflict allocnos for given allocno.  */
560 static 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.  */
565 static void
566 build_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];
582       ira_assert (ira_reg_classes_intersect_p
583                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
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];
619       ira_assert (ira_reg_classes_intersect_p
620                   [ALLOCNO_COVER_CLASS (a)][ALLOCNO_COVER_CLASS (another_a)]);
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.  */
637 static void
638 build_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.  */
661 static void
662 print_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.  */
691 static void
692 print_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.  */
752 void
753 ira_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.  */
762 void
763 ira_build_conflicts (void)
764 {
765   ira_allocno_t a;
766   ira_allocno_iterator ai;
767   HARD_REG_SET temp_hard_reg_set;
768
769   if (ira_conflicts_p)
770     {
771       ira_conflicts_p = build_conflict_bit_table ();
772       if (ira_conflicts_p)
773         {
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);
789         }
790     }
791   if (! CLASS_LIKELY_SPILLED_P (BASE_REG_CLASS))
792     CLEAR_HARD_REG_SET (temp_hard_reg_set);
793   else
794     {
795       COPY_HARD_REG_SET (temp_hard_reg_set,
796                          reg_class_contents[BASE_REG_CLASS]);
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     }
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);
816           IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
817                             temp_hard_reg_set);
818           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
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             }
825         }
826     }
827   if (optimize && ira_conflicts_p
828       && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
829     print_conflicts (ira_dump_file, false);
830 }