Branch data Line data Source code
1 : : /* IRA conflict builder.
2 : : Copyright (C) 2006-2025 Free Software Foundation, Inc.
3 : : Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it under
8 : : the terms of the GNU General Public License as published by the Free
9 : : Software Foundation; either version 3, or (at your option) any later
10 : : version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "config.h"
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "backend.h"
25 : : #include "target.h"
26 : : #include "rtl.h"
27 : : #include "predict.h"
28 : : #include "memmodel.h"
29 : : #include "tm_p.h"
30 : : #include "insn-config.h"
31 : : #include "regs.h"
32 : : #include "ira.h"
33 : : #include "ira-int.h"
34 : : #include "sparseset.h"
35 : : #include "addresses.h"
36 : :
37 : : /* This file contains code responsible for allocno conflict creation,
38 : : allocno copy creation and allocno info accumulation on upper level
39 : : regions. */
40 : :
41 : : /* ira_allocnos_num array of arrays of bits, recording whether two
42 : : allocno's conflict (can't go in the same hardware register).
43 : :
44 : : Some arrays will be used as conflict bit vector of the
45 : : corresponding allocnos see function build_object_conflicts. */
46 : : static IRA_INT_TYPE **conflicts;
47 : :
48 : : /* Macro to test a conflict of C1 and C2 in `conflicts'. */
49 : : #define OBJECTS_CONFLICT_P(C1, C2) \
50 : : (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2) \
51 : : && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1) \
52 : : && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)], \
53 : : OBJECT_CONFLICT_ID (C2), \
54 : : OBJECT_MIN (C1), OBJECT_MAX (C1)))
55 : :
56 : :
57 : : /* Record a conflict between objects OBJ1 and OBJ2. If necessary,
58 : : canonicalize the conflict by recording it for lower-order subobjects
59 : : of the corresponding allocnos. */
60 : : static void
61 : 207870205 : record_object_conflict (ira_object_t obj1, ira_object_t obj2)
62 : : {
63 : 207870205 : ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
64 : 207870205 : ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
65 : 207870205 : int w1 = OBJECT_SUBWORD (obj1);
66 : 207870205 : int w2 = OBJECT_SUBWORD (obj2);
67 : 207870205 : int id1, id2;
68 : :
69 : : /* Canonicalize the conflict. If two identically-numbered words
70 : : conflict, always record this as a conflict between words 0. That
71 : : is the only information we need, and it is easier to test for if
72 : : it is collected in each allocno's lowest-order object. */
73 : 207870205 : if (w1 == w2 && w1 > 0)
74 : : {
75 : 1255208 : obj1 = ALLOCNO_OBJECT (a1, 0);
76 : 1255208 : obj2 = ALLOCNO_OBJECT (a2, 0);
77 : : }
78 : 207870205 : id1 = OBJECT_CONFLICT_ID (obj1);
79 : 207870205 : id2 = OBJECT_CONFLICT_ID (obj2);
80 : :
81 : 207870205 : SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1),
82 : : OBJECT_MAX (obj1));
83 : 207870205 : SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2),
84 : : OBJECT_MAX (obj2));
85 : 207870205 : }
86 : :
87 : : /* Build allocno conflict table by processing allocno live ranges.
88 : : Return true if the table was built. The table is not built if it
89 : : is too big. */
90 : : static bool
91 : 1022084 : build_conflict_bit_table (void)
92 : : {
93 : 1022084 : int i;
94 : 1022084 : unsigned int j;
95 : 1022084 : enum reg_class aclass;
96 : 1022084 : int object_set_words, allocated_words_num, conflict_bit_vec_words_num;
97 : 1022084 : live_range_t r;
98 : 1022084 : ira_allocno_t allocno;
99 : 1022084 : ira_allocno_iterator ai;
100 : 1022084 : sparseset objects_live;
101 : 1022084 : ira_object_t obj;
102 : 1022084 : ira_allocno_object_iterator aoi;
103 : :
104 : 1022084 : allocated_words_num = 0;
105 : 26545586 : FOR_EACH_ALLOCNO (allocno, ai)
106 : 50511374 : FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
107 : : {
108 : 24987872 : if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
109 : 890629 : continue;
110 : 24097243 : conflict_bit_vec_words_num
111 : 24097243 : = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
112 : : / IRA_INT_BITS);
113 : 24097243 : allocated_words_num += conflict_bit_vec_words_num;
114 : 24097243 : if ((uint64_t) allocated_words_num * sizeof (IRA_INT_TYPE)
115 : 24097243 : > (uint64_t) param_ira_max_conflict_table_size * 1024 * 1024)
116 : : {
117 : 0 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
118 : 0 : fprintf (ira_dump_file,
119 : : "+++Conflict table will be too big(>%dMB) "
120 : : "-- don't use it\n",
121 : : param_ira_max_conflict_table_size);
122 : 0 : return false;
123 : : }
124 : : }
125 : :
126 : 2044168 : conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *)
127 : 1022084 : * ira_objects_num);
128 : 1022084 : allocated_words_num = 0;
129 : 26545586 : FOR_EACH_ALLOCNO (allocno, ai)
130 : 50511374 : FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi)
131 : : {
132 : 24987872 : int id = OBJECT_CONFLICT_ID (obj);
133 : 24987872 : if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
134 : : {
135 : 890629 : conflicts[id] = NULL;
136 : 890629 : continue;
137 : : }
138 : 24097243 : conflict_bit_vec_words_num
139 : 24097243 : = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
140 : : / IRA_INT_BITS);
141 : 24097243 : allocated_words_num += conflict_bit_vec_words_num;
142 : 24097243 : conflicts[id]
143 : 48194486 : = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE)
144 : 24097243 : * conflict_bit_vec_words_num);
145 : 24097243 : memset (conflicts[id], 0,
146 : : sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num);
147 : : }
148 : :
149 : 1022084 : object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS;
150 : 1022084 : if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
151 : 39 : fprintf (ira_dump_file,
152 : : "+++Allocating " HOST_SIZE_T_PRINT_UNSIGNED
153 : : " bytes for conflict table (uncompressed size "
154 : : HOST_SIZE_T_PRINT_UNSIGNED ")\n",
155 : 39 : (fmt_size_t) (sizeof (IRA_INT_TYPE) * allocated_words_num),
156 : 39 : (fmt_size_t) (sizeof (IRA_INT_TYPE) * object_set_words
157 : 39 : * ira_objects_num));
158 : :
159 : 1022084 : objects_live = sparseset_alloc (ira_objects_num);
160 : 29962377 : for (i = 0; i < ira_max_point; i++)
161 : : {
162 : 55373182 : for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
163 : : {
164 : 26432889 : ira_object_t obj = r->object;
165 : 26432889 : ira_allocno_t allocno = OBJECT_ALLOCNO (obj);
166 : 26432889 : int id = OBJECT_CONFLICT_ID (obj);
167 : :
168 : 26432889 : gcc_assert (id < ira_objects_num);
169 : :
170 : 26432889 : aclass = ALLOCNO_CLASS (allocno);
171 : 502990857 : EXECUTE_IF_SET_IN_SPARSESET (objects_live, j)
172 : : {
173 : 268147367 : ira_object_t live_obj = ira_object_id_map[j];
174 : 268147367 : ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
175 : 268147367 : enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
176 : :
177 : 268147367 : if (ira_reg_classes_intersect_p[aclass][live_aclass]
178 : : /* Don't set up conflict for the allocno with itself. */
179 : 208410601 : && live_a != allocno)
180 : : {
181 : 207870205 : record_object_conflict (obj, live_obj);
182 : : }
183 : : }
184 : 26432889 : sparseset_set_bit (objects_live, id);
185 : : }
186 : :
187 : 55373182 : for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
188 : 26432889 : sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
189 : : }
190 : 1022084 : sparseset_free (objects_live);
191 : 1022084 : return true;
192 : : }
193 : :
194 : : /* Return true iff allocnos A1 and A2 cannot be allocated to the same
195 : : register due to conflicts. */
196 : :
197 : : static bool
198 : 7656992 : allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2)
199 : : {
200 : : /* Due to the fact that we canonicalize conflicts (see
201 : : record_object_conflict), we only need to test for conflicts of
202 : : the lowest order words. */
203 : 7656992 : ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0);
204 : 7656992 : ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0);
205 : :
206 : 7656992 : return OBJECTS_CONFLICT_P (obj1, obj2);
207 : : }
208 : :
209 : : /* Check that X is REG or SUBREG of REG. */
210 : : #define REG_SUBREG_P(x) \
211 : : (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x))))
212 : :
213 : : /* Return X if X is a REG, otherwise it should be SUBREG of REG and
214 : : the function returns the reg in this case. *OFFSET will be set to
215 : : 0 in the first case or the regno offset in the first case. */
216 : : static rtx
217 : 24361754 : go_through_subreg (rtx x, int *offset)
218 : : {
219 : 24361754 : rtx reg;
220 : :
221 : 24361754 : *offset = 0;
222 : 24361754 : if (REG_P (x))
223 : : return x;
224 : 1055057 : ira_assert (GET_CODE (x) == SUBREG);
225 : 1055057 : reg = SUBREG_REG (x);
226 : 1055057 : ira_assert (REG_P (reg));
227 : 1055057 : if (REGNO (reg) < FIRST_PSEUDO_REGISTER)
228 : 0 : *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg),
229 : 0 : SUBREG_BYTE (x), GET_MODE (x));
230 : : /* The offset is always 0 for paradoxical subregs. */
231 : 1055057 : else if (!can_div_trunc_p (SUBREG_BYTE (x),
232 : 1055057 : REGMODE_NATURAL_SIZE (GET_MODE (reg)), offset))
233 : : /* Checked by validate_subreg. We must know at compile time which
234 : : inner hard registers are being accessed. */
235 : : gcc_unreachable ();
236 : : return reg;
237 : : }
238 : :
239 : : /* Return the recomputed frequency for this shuffle copy or its similar
240 : : case, since it's not for a real move insn, make it smaller. */
241 : :
242 : : static int
243 : 11256335 : get_freq_for_shuffle_copy (int freq)
244 : : {
245 : 9629965 : return freq < 8 ? 1 : freq / 8;
246 : : }
247 : :
248 : : /* Process registers REG1 and REG2 in move INSN with execution
249 : : frequency FREQ. The function also processes the registers in a
250 : : potential move insn (INSN == NULL in this case) with frequency
251 : : FREQ. The function can modify hard register costs of the
252 : : corresponding allocnos or create a copy involving the corresponding
253 : : allocnos. The function does nothing if the both registers are hard
254 : : registers. When nothing is changed, the function returns FALSE.
255 : : SINGLE_INPUT_OP_HAS_CSTR_P is only meaningful when constraint_p
256 : : is true, see function ira_get_dup_out_num for its meaning. */
257 : : static bool
258 : 12180877 : process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p, rtx_insn *insn,
259 : : int freq, bool single_input_op_has_cstr_p = true)
260 : : {
261 : 12180877 : int allocno_preferenced_hard_regno, index, offset1, offset2;
262 : 12180877 : int cost, conflict_cost, move_cost;
263 : 12180877 : bool only_regs_p;
264 : 12180877 : ira_allocno_t a;
265 : 12180877 : reg_class_t rclass, aclass;
266 : 12180877 : machine_mode mode;
267 : 12180877 : ira_copy_t cp;
268 : :
269 : 12180877 : gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2));
270 : 12180877 : only_regs_p = REG_P (reg1) && REG_P (reg2);
271 : 12180877 : reg1 = go_through_subreg (reg1, &offset1);
272 : 12180877 : reg2 = go_through_subreg (reg2, &offset2);
273 : : /* Set up hard regno preferenced by allocno. If allocno gets the
274 : : hard regno the copy (or potential move) insn will be removed. */
275 : 12180877 : if (HARD_REGISTER_P (reg1))
276 : : {
277 : 3025889 : if (HARD_REGISTER_P (reg2))
278 : : return false;
279 : 3025889 : allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2;
280 : 3025889 : a = ira_curr_regno_allocno_map[REGNO (reg2)];
281 : : }
282 : 9154988 : else if (HARD_REGISTER_P (reg2))
283 : : {
284 : 3219345 : allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1;
285 : 3219345 : a = ira_curr_regno_allocno_map[REGNO (reg1)];
286 : : }
287 : : else
288 : : {
289 : 5935643 : ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)];
290 : 5935643 : ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)];
291 : :
292 : 5935643 : if (!allocnos_conflict_for_copy_p (a1, a2)
293 : 5434396 : && offset1 == offset2
294 : 5935643 : && ordered_p (GET_MODE_PRECISION (ALLOCNO_MODE (a1)),
295 : 5349053 : GET_MODE_PRECISION (ALLOCNO_MODE (a2))))
296 : : {
297 : 5349053 : cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn,
298 : : ira_curr_loop_tree_node);
299 : 5349053 : bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num);
300 : 5349053 : return true;
301 : : }
302 : : else
303 : : return false;
304 : : }
305 : :
306 : 6245234 : if (! IN_RANGE (allocno_preferenced_hard_regno,
307 : : 0, FIRST_PSEUDO_REGISTER - 1))
308 : : /* Cannot be tied. */
309 : : return false;
310 : 6245234 : rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno);
311 : 6245234 : mode = ALLOCNO_MODE (a);
312 : 6245234 : aclass = ALLOCNO_CLASS (a);
313 : 6245234 : if (only_regs_p && insn != NULL_RTX
314 : 6185730 : && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode])
315 : : /* It is already taken into account in ira-costs.cc. */
316 : : return false;
317 : 378546 : index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno];
318 : 378546 : if (index < 0)
319 : : /* Cannot be tied. It is not in the allocno class. */
320 : : return false;
321 : 367223 : ira_init_register_move_cost_if_necessary (mode);
322 : 367223 : if (HARD_REGISTER_P (reg1))
323 : 166449 : move_cost = ira_register_move_cost[mode][aclass][rclass];
324 : : else
325 : 200774 : move_cost = ira_register_move_cost[mode][rclass][aclass];
326 : :
327 : 367223 : if (!single_input_op_has_cstr_p)
328 : : {
329 : : /* When this is a constraint copy and the matching constraint
330 : : doesn't only exist for this given operand but also for some
331 : : other operand(s), it means saving the possible move cost does
332 : : NOT need to require reg1 and reg2 to use the same hardware
333 : : register, so this hardware preference isn't required to be
334 : : fixed. To avoid it to over prefer this hardware register,
335 : : and over disparage this hardware register on conflicted
336 : : objects, we need some cost tweaking here, similar to what
337 : : we do for shuffle copy. */
338 : 0 : gcc_assert (constraint_p);
339 : 0 : int reduced_freq = get_freq_for_shuffle_copy (freq);
340 : 0 : if (HARD_REGISTER_P (reg1))
341 : : /* For reg2 = opcode(reg1, reg3 ...), assume that reg3 is a
342 : : pseudo register which has matching constraint on reg2,
343 : : even if reg2 isn't assigned by reg1, it's still possible
344 : : not to have register moves if reg2 and reg3 use the same
345 : : hardware register. So to avoid the allocation to over
346 : : prefer reg1, we can just take it as a shuffle copy. */
347 : 0 : cost = conflict_cost = move_cost * reduced_freq;
348 : : else
349 : : {
350 : : /* For reg1 = opcode(reg2, reg3 ...), assume that reg3 is a
351 : : pseudo register which has matching constraint on reg2,
352 : : to save the register move, it's better to assign reg1
353 : : to either of reg2 and reg3 (or one of other pseudos like
354 : : reg3), it's reasonable to use freq for the cost. But
355 : : for conflict_cost, since reg2 and reg3 conflicts with
356 : : each other, both of them has the chance to be assigned
357 : : by reg1, assume reg3 has one copy which also conflicts
358 : : with reg2, we shouldn't make it less preferred on reg1
359 : : since reg3 has the same chance to be assigned by reg1.
360 : : So it adjusts the conflic_cost to make it same as what
361 : : we use for shuffle copy. */
362 : 0 : cost = move_cost * freq;
363 : 0 : conflict_cost = move_cost * reduced_freq;
364 : : }
365 : : }
366 : : else
367 : 367223 : cost = conflict_cost = move_cost * freq;
368 : :
369 : 410211 : do
370 : : {
371 : 410211 : ira_allocate_and_set_costs
372 : 410211 : (&ALLOCNO_HARD_REG_COSTS (a), aclass,
373 : : ALLOCNO_CLASS_COST (a));
374 : 410211 : ira_allocate_and_set_costs
375 : 410211 : (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0);
376 : 410211 : ALLOCNO_HARD_REG_COSTS (a)[index] -= cost;
377 : 410211 : ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= conflict_cost;
378 : 410211 : if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a))
379 : 367756 : ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index];
380 : 410211 : ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq);
381 : 410211 : a = ira_parent_or_cap_allocno (a);
382 : : }
383 : 410211 : while (a != NULL);
384 : : return true;
385 : : }
386 : :
387 : : /* Return true if output operand OUTPUT and input operand INPUT of
388 : : INSN can use the same register class for at least one alternative.
389 : : INSN is already described in recog_data and recog_op_alt. */
390 : : static bool
391 : 2556939 : can_use_same_reg_p (rtx_insn *insn, int output, int input)
392 : : {
393 : 2556939 : alternative_mask preferred = get_preferred_alternatives (insn);
394 : 3646428 : for (int nalt = 0; nalt < recog_data.n_alternatives; nalt++)
395 : : {
396 : 3425379 : if (!TEST_BIT (preferred, nalt))
397 : 704447 : continue;
398 : :
399 : 2720932 : const operand_alternative *op_alt
400 : 2720932 : = &recog_op_alt[nalt * recog_data.n_operands];
401 : 2720932 : if (op_alt[input].matches == output)
402 : : return true;
403 : :
404 : 1689828 : if (op_alt[output].earlyclobber)
405 : 62733 : continue;
406 : :
407 : 1627095 : if (ira_reg_class_intersect[op_alt[input].cl][op_alt[output].cl]
408 : : != NO_REGS)
409 : : return true;
410 : : }
411 : : return false;
412 : : }
413 : :
414 : : /* Process all of the output registers of the current insn (INSN) which
415 : : are not bound (BOUND_P) and the input register REG (its operand number
416 : : OP_NUM) which dies in the insn as if there were a move insn between
417 : : them with frequency FREQ. */
418 : : static void
419 : 11256335 : process_reg_shuffles (rtx_insn *insn, rtx reg, int op_num, int freq,
420 : : bool *bound_p)
421 : : {
422 : 11256335 : int i;
423 : 11256335 : rtx another_reg;
424 : :
425 : 11256335 : gcc_assert (REG_SUBREG_P (reg));
426 : 40526282 : for (i = 0; i < recog_data.n_operands; i++)
427 : : {
428 : 29269947 : another_reg = recog_data.operand[i];
429 : :
430 : 29269947 : if (!REG_SUBREG_P (another_reg) || op_num == i
431 : 9998978 : || recog_data.operand_type[i] != OP_OUT
432 : 5558549 : || bound_p[i]
433 : 31800155 : || (!can_use_same_reg_p (insn, i, op_num)
434 : 203450 : && (recog_data.constraints[op_num][0] != '%'
435 : 14756 : || !can_use_same_reg_p (insn, i, op_num + 1))
436 : 194318 : && (op_num == 0
437 : 194318 : || recog_data.constraints[op_num - 1][0] != '%'
438 : 11975 : || !can_use_same_reg_p (insn, i, op_num - 1))))
439 : 26934057 : continue;
440 : :
441 : 2335890 : process_regs_for_copy (reg, another_reg, false, NULL, freq);
442 : : }
443 : 11256335 : }
444 : :
445 : : /* Process INSN and create allocno copies if necessary. For example,
446 : : it might be because INSN is a pseudo-register move or INSN is two
447 : : operand insn. */
448 : : static void
449 : 57622640 : add_insn_allocno_copies (rtx_insn *insn)
450 : : {
451 : 57622640 : rtx set, operand, dup;
452 : 57622640 : bool bound_p[MAX_RECOG_OPERANDS];
453 : 57622640 : int i, n, freq;
454 : 57622640 : alternative_mask alts;
455 : :
456 : 57622640 : freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn));
457 : 48006269 : if (freq == 0)
458 : 7587681 : freq = 1;
459 : 57622640 : if ((set = single_set (insn)) != NULL_RTX
460 : 53794183 : && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set))
461 : 9554481 : && ! side_effects_p (set)
462 : 67177121 : && find_reg_note (insn, REG_DEAD,
463 : 9554481 : REG_P (SET_SRC (set))
464 : : ? SET_SRC (set)
465 : : : SUBREG_REG (SET_SRC (set))) != NULL_RTX)
466 : : {
467 : 7372334 : process_regs_for_copy (SET_SRC (set), SET_DEST (set),
468 : : false, insn, freq);
469 : 45478856 : return;
470 : : }
471 : : /* Fast check of possibility of constraint or shuffle copies. If
472 : : there are no dead registers, there will be no such copies. */
473 : 50250306 : if (! find_reg_note (insn, REG_DEAD, NULL_RTX))
474 : : return;
475 : 19516118 : alts = ira_setup_alts (insn);
476 : 84718930 : for (i = 0; i < recog_data.n_operands; i++)
477 : 45686694 : bound_p[i] = false;
478 : 65202812 : for (i = 0; i < recog_data.n_operands; i++)
479 : : {
480 : 45686694 : operand = recog_data.operand[i];
481 : 45686694 : if (! REG_SUBREG_P (operand))
482 : 25557908 : continue;
483 : 20128786 : bool single_input_op_has_cstr_p;
484 : 20128786 : if ((n = ira_get_dup_out_num (i, alts, single_input_op_has_cstr_p)) >= 0)
485 : : {
486 : 3028986 : bound_p[n] = true;
487 : 3028986 : dup = recog_data.operand[n];
488 : 148332 : if (REG_SUBREG_P (dup)
489 : 6044526 : && find_reg_note (insn, REG_DEAD,
490 : 3015540 : REG_P (operand)
491 : : ? operand
492 : : : SUBREG_REG (operand)) != NULL_RTX)
493 : 2472653 : process_regs_for_copy (operand, dup, true, NULL, freq,
494 : : single_input_op_has_cstr_p);
495 : : }
496 : : }
497 : 65202812 : for (i = 0; i < recog_data.n_operands; i++)
498 : : {
499 : 45686694 : operand = recog_data.operand[i];
500 : 26410218 : if (REG_SUBREG_P (operand)
501 : 46539004 : && find_reg_note (insn, REG_DEAD,
502 : : REG_P (operand)
503 : : ? operand : SUBREG_REG (operand)) != NULL_RTX)
504 : : {
505 : : /* If an operand dies, prefer its hard register for the output
506 : : operands by decreasing the hard register cost or creating
507 : : the corresponding allocno copies. The cost will not
508 : : correspond to a real move insn cost, so make the frequency
509 : : smaller. */
510 : 11256335 : int new_freq = get_freq_for_shuffle_copy (freq);
511 : 11256335 : process_reg_shuffles (insn, operand, i, new_freq, bound_p);
512 : : }
513 : : }
514 : : }
515 : :
516 : : /* Add copies originated from BB given by LOOP_TREE_NODE. */
517 : : static void
518 : 11972648 : add_copies (ira_loop_tree_node_t loop_tree_node)
519 : : {
520 : 11972648 : basic_block bb;
521 : 11972648 : rtx_insn *insn;
522 : :
523 : 11972648 : bb = loop_tree_node->bb;
524 : 11972648 : if (bb == NULL)
525 : : return;
526 : 135597159 : FOR_BB_INSNS (bb, insn)
527 : 124810293 : if (NONDEBUG_INSN_P (insn))
528 : 57622640 : add_insn_allocno_copies (insn);
529 : : }
530 : :
531 : : /* Propagate copies the corresponding allocnos on upper loop tree
532 : : level. */
533 : : static void
534 : 978686 : propagate_copies (void)
535 : : {
536 : 978686 : ira_copy_t cp;
537 : 978686 : ira_copy_iterator ci;
538 : 978686 : ira_allocno_t a1, a2, parent_a1, parent_a2;
539 : :
540 : 7858685 : FOR_EACH_COPY (cp, ci)
541 : : {
542 : 6879999 : a1 = cp->first;
543 : 6879999 : a2 = cp->second;
544 : 6879999 : if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root)
545 : 5158650 : continue;
546 : 1721349 : ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root));
547 : 1721349 : parent_a1 = ira_parent_or_cap_allocno (a1);
548 : 1721349 : parent_a2 = ira_parent_or_cap_allocno (a2);
549 : 1721349 : ira_assert (parent_a1 != NULL && parent_a2 != NULL);
550 : 1721349 : if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2))
551 : 1721249 : ira_add_allocno_copy (parent_a1, parent_a2, cp->freq,
552 : 1721249 : cp->constraint_p, cp->insn, cp->loop_tree_node);
553 : : }
554 : 978686 : }
555 : :
556 : : /* Array used to collect all conflict allocnos for given allocno. */
557 : : static ira_object_t *collected_conflict_objects;
558 : :
559 : : /* Build conflict vectors or bit conflict vectors (whatever is more
560 : : profitable) for object OBJ from the conflict table. */
561 : : static void
562 : 24987872 : build_object_conflicts (ira_object_t obj)
563 : : {
564 : 24987872 : int i, px, parent_num;
565 : 24987872 : ira_allocno_t parent_a, another_parent_a;
566 : 24987872 : ira_object_t parent_obj;
567 : 24987872 : ira_allocno_t a = OBJECT_ALLOCNO (obj);
568 : 24987872 : IRA_INT_TYPE *object_conflicts;
569 : 24987872 : minmax_set_iterator asi;
570 : 24987872 : int parent_min, parent_max ATTRIBUTE_UNUSED;
571 : :
572 : 24987872 : object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)];
573 : 24987872 : px = 0;
574 : 606840508 : FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
575 : : OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
576 : : {
577 : 556864764 : ira_object_t another_obj = ira_object_id_map[i];
578 : 556864764 : ira_allocno_t another_a = OBJECT_ALLOCNO (obj);
579 : :
580 : 556864764 : ira_assert (ira_reg_classes_intersect_p
581 : : [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
582 : 556864764 : collected_conflict_objects[px++] = another_obj;
583 : : }
584 : 24987872 : if (ira_conflict_vector_profitable_p (obj, px))
585 : : {
586 : 4953095 : ira_object_t *vec;
587 : 4953095 : ira_allocate_conflict_vec (obj, px);
588 : 4953095 : vec = OBJECT_CONFLICT_VEC (obj);
589 : 4953095 : memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px);
590 : 4953095 : vec[px] = NULL;
591 : 4953095 : OBJECT_NUM_CONFLICTS (obj) = px;
592 : : }
593 : : else
594 : : {
595 : 20034777 : int conflict_bit_vec_words_num;
596 : :
597 : 20034777 : OBJECT_CONFLICT_ARRAY (obj) = object_conflicts;
598 : 20034777 : if (OBJECT_MAX (obj) < OBJECT_MIN (obj))
599 : : conflict_bit_vec_words_num = 0;
600 : : else
601 : 19144148 : conflict_bit_vec_words_num
602 : 19144148 : = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
603 : : / IRA_INT_BITS);
604 : 20034777 : OBJECT_CONFLICT_ARRAY_SIZE (obj)
605 : 20034777 : = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE);
606 : : }
607 : :
608 : 24987872 : parent_a = ira_parent_or_cap_allocno (a);
609 : 24987872 : if (parent_a == NULL)
610 : 18339583 : return;
611 : 6648289 : ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a));
612 : 6648289 : ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a));
613 : 6648289 : parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj));
614 : 6648289 : parent_num = OBJECT_CONFLICT_ID (parent_obj);
615 : 6648289 : parent_min = OBJECT_MIN (parent_obj);
616 : 6648289 : parent_max = OBJECT_MAX (parent_obj);
617 : 326297814 : FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts,
618 : : OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi)
619 : : {
620 : 313001236 : ira_object_t another_obj = ira_object_id_map[i];
621 : 313001236 : ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj);
622 : 313001236 : int another_word = OBJECT_SUBWORD (another_obj);
623 : :
624 : 313001236 : ira_assert (ira_reg_classes_intersect_p
625 : : [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]);
626 : :
627 : 313001236 : another_parent_a = ira_parent_or_cap_allocno (another_a);
628 : 313001236 : if (another_parent_a == NULL)
629 : 0 : continue;
630 : 313001236 : ira_assert (ALLOCNO_NUM (another_parent_a) >= 0);
631 : 313001236 : ira_assert (ALLOCNO_CLASS (another_a)
632 : : == ALLOCNO_CLASS (another_parent_a));
633 : 313001236 : ira_assert (ALLOCNO_NUM_OBJECTS (another_a)
634 : : == ALLOCNO_NUM_OBJECTS (another_parent_a));
635 : 313001236 : SET_MINMAX_SET_BIT (conflicts[parent_num],
636 : : OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a,
637 : : another_word)),
638 : : parent_min, parent_max);
639 : : }
640 : : }
641 : :
642 : : /* Build conflict vectors or bit conflict vectors (whatever is more
643 : : profitable) of all allocnos from the conflict table. */
644 : : static void
645 : 1022084 : build_conflicts (void)
646 : : {
647 : 1022084 : int i;
648 : 1022084 : ira_allocno_t a, cap;
649 : :
650 : 1022084 : collected_conflict_objects
651 : 2044168 : = (ira_object_t *) ira_allocate (sizeof (ira_object_t)
652 : 1022084 : * ira_objects_num);
653 : 50762825 : for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
654 : 49740741 : for (a = ira_regno_allocno_map[i];
655 : 70667163 : a != NULL;
656 : 20926422 : a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
657 : : {
658 : 20926422 : int j, nregs = ALLOCNO_NUM_OBJECTS (a);
659 : 42297092 : for (j = 0; j < nregs; j++)
660 : : {
661 : 21370670 : ira_object_t obj = ALLOCNO_OBJECT (a, j);
662 : 21370670 : build_object_conflicts (obj);
663 : 24987872 : for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
664 : : {
665 : 3617202 : ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
666 : 3617202 : gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a));
667 : 3617202 : build_object_conflicts (cap_obj);
668 : : }
669 : : }
670 : : }
671 : 1022084 : ira_free (collected_conflict_objects);
672 : 1022084 : }
673 : :
674 : :
675 : :
676 : : /* Print hard reg set SET with TITLE to FILE. */
677 : : static void
678 : 852 : print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set)
679 : : {
680 : 852 : int i, start, end;
681 : :
682 : 852 : fputs (title, file);
683 : 79236 : for (start = end = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
684 : : {
685 : 78384 : bool reg_included = TEST_HARD_REG_BIT (set, i);
686 : :
687 : 78384 : if (reg_included)
688 : : {
689 : 782 : if (start == -1)
690 : 450 : start = i;
691 : : end = i;
692 : : }
693 : 78384 : if (start >= 0 && (!reg_included || i == FIRST_PSEUDO_REGISTER - 1))
694 : : {
695 : 450 : if (start == end)
696 : 142 : fprintf (file, " %d", start);
697 : 308 : else if (start == end + 1)
698 : 0 : fprintf (file, " %d %d", start, end);
699 : : else
700 : 308 : fprintf (file, " %d-%d", start, end);
701 : : start = -1;
702 : : }
703 : : }
704 : 852 : putc ('\n', file);
705 : 852 : }
706 : :
707 : : static void
708 : 453 : print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a)
709 : : {
710 : 453 : HARD_REG_SET conflicting_hard_regs;
711 : 453 : basic_block bb;
712 : 453 : int n, i;
713 : :
714 : 453 : if (reg_p)
715 : 0 : fprintf (file, ";; r%d", ALLOCNO_REGNO (a));
716 : : else
717 : : {
718 : 453 : fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
719 : 453 : if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
720 : 0 : fprintf (file, "b%d", bb->index);
721 : : else
722 : 453 : fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
723 : 453 : putc (')', file);
724 : : }
725 : :
726 : 453 : fputs (" conflicts:", file);
727 : 453 : n = ALLOCNO_NUM_OBJECTS (a);
728 : 906 : for (i = 0; i < n; i++)
729 : : {
730 : 453 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
731 : 453 : ira_object_t conflict_obj;
732 : 453 : ira_object_conflict_iterator oci;
733 : :
734 : 453 : if (OBJECT_CONFLICT_ARRAY (obj) == NULL)
735 : : {
736 : 27 : fprintf (file, "\n;; total conflict hard regs:\n");
737 : 27 : fprintf (file, ";; conflict hard regs:\n\n");
738 : 27 : continue;
739 : : }
740 : :
741 : 426 : if (n > 1)
742 : 0 : fprintf (file, "\n;; subobject %d:", i);
743 : 3574 : FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
744 : : {
745 : 3148 : ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
746 : 3148 : if (reg_p)
747 : 0 : fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a));
748 : : else
749 : : {
750 : 3148 : fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a),
751 : : ALLOCNO_REGNO (conflict_a));
752 : 3148 : if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1)
753 : 0 : fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj));
754 : 3148 : if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL)
755 : 0 : fprintf (file, ",b%d", bb->index);
756 : : else
757 : 3148 : fprintf (file, ",l%d",
758 : : ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num);
759 : 3148 : putc (')', file);
760 : : }
761 : : }
762 : 426 : conflicting_hard_regs = (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
763 : 426 : & ~ira_no_alloc_regs
764 : 426 : & reg_class_contents[ALLOCNO_CLASS (a)]);
765 : 426 : print_hard_reg_set (file, "\n;; total conflict hard regs:",
766 : : conflicting_hard_regs);
767 : :
768 : 426 : conflicting_hard_regs = (OBJECT_CONFLICT_HARD_REGS (obj)
769 : 426 : & ~ira_no_alloc_regs
770 : 426 : & reg_class_contents[ALLOCNO_CLASS (a)]);
771 : 426 : print_hard_reg_set (file, ";; conflict hard regs:",
772 : : conflicting_hard_regs);
773 : 426 : putc ('\n', file);
774 : : }
775 : :
776 : 453 : }
777 : :
778 : : /* Print information about allocno or only regno (if REG_P) conflicts
779 : : to FILE. */
780 : : static void
781 : 39 : print_conflicts (FILE *file, bool reg_p)
782 : : {
783 : 39 : ira_allocno_t a;
784 : 39 : ira_allocno_iterator ai;
785 : :
786 : 492 : FOR_EACH_ALLOCNO (a, ai)
787 : 453 : print_allocno_conflicts (file, reg_p, a);
788 : 39 : putc ('\n', file);
789 : 39 : }
790 : :
791 : : /* Print information about allocno or only regno (if REG_P) conflicts
792 : : to stderr. */
793 : : void
794 : 0 : ira_debug_conflicts (bool reg_p)
795 : : {
796 : 0 : print_conflicts (stderr, reg_p);
797 : 0 : }
798 : :
799 : :
800 : :
801 : : /* Entry function which builds allocno conflicts and allocno copies
802 : : and accumulate some allocno info on upper level regions. */
803 : : void
804 : 1443146 : ira_build_conflicts (void)
805 : : {
806 : 1443146 : enum reg_class base;
807 : 1443146 : ira_allocno_t a;
808 : 1443146 : ira_allocno_iterator ai;
809 : 1443146 : HARD_REG_SET temp_hard_reg_set;
810 : :
811 : 1443146 : if (ira_conflicts_p)
812 : : {
813 : 1022084 : ira_conflicts_p = build_conflict_bit_table ();
814 : 1022084 : if (ira_conflicts_p)
815 : : {
816 : 1022084 : ira_object_t obj;
817 : 1022084 : ira_object_iterator oi;
818 : :
819 : 1022084 : build_conflicts ();
820 : 1022084 : ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL);
821 : : /* We need finished conflict table for the subsequent call. */
822 : 1022084 : if (flag_ira_region == IRA_REGION_ALL
823 : 1022084 : || flag_ira_region == IRA_REGION_MIXED)
824 : 978686 : propagate_copies ();
825 : :
826 : : /* Now we can free memory for the conflict table (see function
827 : : build_object_conflicts for details). */
828 : 27032040 : FOR_EACH_OBJECT (obj, oi)
829 : : {
830 : 24987872 : if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)])
831 : 4953095 : ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]);
832 : : }
833 : 1022084 : ira_free (conflicts);
834 : : }
835 : : }
836 : 1443146 : base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH);
837 : 1443146 : if (! targetm.class_likely_spilled_p (base))
838 : 1443146 : CLEAR_HARD_REG_SET (temp_hard_reg_set);
839 : : else
840 : 0 : temp_hard_reg_set = reg_class_contents[base] & ~ira_no_alloc_regs;
841 : 37136905 : FOR_EACH_ALLOCNO (a, ai)
842 : : {
843 : 35693759 : int i, n = ALLOCNO_NUM_OBJECTS (a);
844 : :
845 : 72692052 : for (i = 0; i < n; i++)
846 : : {
847 : 36998293 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
848 : 36998293 : rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)];
849 : :
850 : : /* For debugging purposes don't put user defined variables in
851 : : callee-clobbered registers. However, do allow parameters
852 : : in callee-clobbered registers to improve debugging. This
853 : : is a bit of a fragile hack. */
854 : 36998293 : if (optimize == 0
855 : 12010421 : && REG_USERVAR_P (allocno_reg)
856 : 37007530 : && ! reg_is_parm_p (allocno_reg))
857 : : {
858 : 9124 : HARD_REG_SET new_conflict_regs = crtl->abi->full_reg_clobbers ();
859 : 36496 : OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
860 : 9124 : OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
861 : : }
862 : :
863 : 36998293 : if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
864 : : {
865 : 3906130 : HARD_REG_SET new_conflict_regs = ira_need_caller_save_regs (a);
866 : 3906130 : if (flag_caller_saves)
867 : 7033018 : new_conflict_regs &= (~savable_regs | temp_hard_reg_set);
868 : 15624520 : OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
869 : 3906130 : OBJECT_CONFLICT_HARD_REGS (obj) |= new_conflict_regs;
870 : : }
871 : :
872 : : /* Now we deal with paradoxical subreg cases where certain registers
873 : : cannot be accessed in the widest mode. */
874 : 36998293 : machine_mode outer_mode = ALLOCNO_WMODE (a);
875 : 36998293 : machine_mode inner_mode = ALLOCNO_MODE (a);
876 : 36998293 : if (paradoxical_subreg_p (outer_mode, inner_mode))
877 : : {
878 : 655516 : enum reg_class aclass = ALLOCNO_CLASS (a);
879 : 7220011 : for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j)
880 : : {
881 : 6564495 : int inner_regno = ira_class_hard_regs[aclass][j];
882 : 13128990 : int outer_regno = simplify_subreg_regno (inner_regno,
883 : 6564495 : inner_mode, 0,
884 : : outer_mode);
885 : 6564495 : if (outer_regno < 0
886 : 6564495 : || !in_hard_reg_set_p (reg_class_contents[aclass],
887 : : outer_mode, outer_regno))
888 : : {
889 : 3323 : SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
890 : : inner_regno);
891 : 3323 : SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj),
892 : : inner_regno);
893 : : }
894 : : }
895 : : }
896 : : }
897 : : }
898 : 1443146 : if (optimize && ira_conflicts_p
899 : 1022084 : && internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
900 : 39 : print_conflicts (ira_dump_file, false);
901 : 1443146 : }
|
