]>
Commit | Line | Data |
---|---|---|
47dd2e78 | 1 | /* IRA conflict builder. |
fbd26352 | 2 | Copyright (C) 2006-2019 Free Software Foundation, Inc. |
47dd2e78 | 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" | |
9ef16211 | 24 | #include "backend.h" |
7c29e30e | 25 | #include "target.h" |
47dd2e78 | 26 | #include "rtl.h" |
7c29e30e | 27 | #include "predict.h" |
ad7b10a2 | 28 | #include "memmodel.h" |
47dd2e78 | 29 | #include "tm_p.h" |
47dd2e78 | 30 | #include "insn-config.h" |
7c29e30e | 31 | #include "regs.h" |
32 | #include "ira.h" | |
33 | #include "ira-int.h" | |
47dd2e78 | 34 | #include "params.h" |
47dd2e78 | 35 | #include "sparseset.h" |
bef7b1de | 36 | #include "addresses.h" |
47dd2e78 | 37 | |
38 | /* This file contains code responsible for allocno conflict creation, | |
39 | allocno copy creation and allocno info accumulation on upper level | |
40 | regions. */ | |
41 | ||
42 | /* ira_allocnos_num array of arrays of bits, recording whether two | |
43 | allocno's conflict (can't go in the same hardware register). | |
44 | ||
45 | Some arrays will be used as conflict bit vector of the | |
be18556f | 46 | corresponding allocnos see function build_object_conflicts. */ |
47dd2e78 | 47 | static IRA_INT_TYPE **conflicts; |
48 | ||
ae9587ed | 49 | /* Macro to test a conflict of C1 and C2 in `conflicts'. */ |
be18556f | 50 | #define OBJECTS_CONFLICT_P(C1, C2) \ |
ae9587ed | 51 | (OBJECT_MIN (C1) <= OBJECT_CONFLICT_ID (C2) \ |
52 | && OBJECT_CONFLICT_ID (C2) <= OBJECT_MAX (C1) \ | |
53 | && TEST_MINMAX_SET_BIT (conflicts[OBJECT_CONFLICT_ID (C1)], \ | |
54 | OBJECT_CONFLICT_ID (C2), \ | |
55 | OBJECT_MIN (C1), OBJECT_MAX (C1))) | |
47dd2e78 | 56 | |
57 | \f | |
be18556f | 58 | /* Record a conflict between objects OBJ1 and OBJ2. If necessary, |
59 | canonicalize the conflict by recording it for lower-order subobjects | |
3ad55f68 | 60 | of the corresponding allocnos. */ |
be18556f | 61 | static void |
62 | record_object_conflict (ira_object_t obj1, ira_object_t obj2) | |
63 | { | |
64 | ira_allocno_t a1 = OBJECT_ALLOCNO (obj1); | |
65 | ira_allocno_t a2 = OBJECT_ALLOCNO (obj2); | |
66 | int w1 = OBJECT_SUBWORD (obj1); | |
67 | int w2 = OBJECT_SUBWORD (obj2); | |
68 | int id1, id2; | |
69 | ||
70 | /* Canonicalize the conflict. If two identically-numbered words | |
71 | conflict, always record this as a conflict between words 0. That | |
72 | is the only information we need, and it is easier to test for if | |
73 | it is collected in each allocno's lowest-order object. */ | |
74 | if (w1 == w2 && w1 > 0) | |
75 | { | |
76 | obj1 = ALLOCNO_OBJECT (a1, 0); | |
77 | obj2 = ALLOCNO_OBJECT (a2, 0); | |
78 | } | |
79 | id1 = OBJECT_CONFLICT_ID (obj1); | |
80 | id2 = OBJECT_CONFLICT_ID (obj2); | |
81 | ||
82 | SET_MINMAX_SET_BIT (conflicts[id1], id2, OBJECT_MIN (obj1), | |
83 | OBJECT_MAX (obj1)); | |
84 | SET_MINMAX_SET_BIT (conflicts[id2], id1, OBJECT_MIN (obj2), | |
85 | OBJECT_MAX (obj2)); | |
86 | } | |
87 | ||
95c83f01 | 88 | /* Build allocno conflict table by processing allocno live ranges. |
89 | Return true if the table was built. The table is not built if it | |
90 | is too big. */ | |
91 | static bool | |
47dd2e78 | 92 | build_conflict_bit_table (void) |
93 | { | |
ae9587ed | 94 | int i; |
47dd2e78 | 95 | unsigned int j; |
66d9a7b9 | 96 | enum reg_class aclass; |
ae9587ed | 97 | int object_set_words, allocated_words_num, conflict_bit_vec_words_num; |
fbff82f4 | 98 | live_range_t r; |
ae9587ed | 99 | ira_allocno_t allocno; |
47dd2e78 | 100 | ira_allocno_iterator ai; |
ae9587ed | 101 | sparseset objects_live; |
be18556f | 102 | ira_object_t obj; |
103 | ira_allocno_object_iterator aoi; | |
47dd2e78 | 104 | |
95c83f01 | 105 | allocated_words_num = 0; |
106 | FOR_EACH_ALLOCNO (allocno, ai) | |
be18556f | 107 | FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi) |
108 | { | |
109 | if (OBJECT_MAX (obj) < OBJECT_MIN (obj)) | |
95c83f01 | 110 | continue; |
be18556f | 111 | conflict_bit_vec_words_num |
112 | = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS) | |
113 | / IRA_INT_BITS); | |
114 | allocated_words_num += conflict_bit_vec_words_num; | |
3a4303e7 | 115 | if ((uint64_t) allocated_words_num * sizeof (IRA_INT_TYPE) |
116 | > (uint64_t) IRA_MAX_CONFLICT_TABLE_SIZE * 1024 * 1024) | |
be18556f | 117 | { |
118 | if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) | |
119 | fprintf | |
120 | (ira_dump_file, | |
121 | "+++Conflict table will be too big(>%dMB) -- don't use it\n", | |
122 | IRA_MAX_CONFLICT_TABLE_SIZE); | |
123 | return false; | |
124 | } | |
125 | } | |
ae9587ed | 126 | |
47dd2e78 | 127 | conflicts = (IRA_INT_TYPE **) ira_allocate (sizeof (IRA_INT_TYPE *) |
ae9587ed | 128 | * ira_objects_num); |
47dd2e78 | 129 | allocated_words_num = 0; |
130 | FOR_EACH_ALLOCNO (allocno, ai) | |
be18556f | 131 | FOR_EACH_ALLOCNO_OBJECT (allocno, obj, aoi) |
132 | { | |
133 | int id = OBJECT_CONFLICT_ID (obj); | |
134 | if (OBJECT_MAX (obj) < OBJECT_MIN (obj)) | |
135 | { | |
136 | conflicts[id] = NULL; | |
137 | continue; | |
138 | } | |
139 | conflict_bit_vec_words_num | |
140 | = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS) | |
141 | / IRA_INT_BITS); | |
142 | allocated_words_num += conflict_bit_vec_words_num; | |
143 | conflicts[id] | |
144 | = (IRA_INT_TYPE *) ira_allocate (sizeof (IRA_INT_TYPE) | |
145 | * conflict_bit_vec_words_num); | |
146 | memset (conflicts[id], 0, | |
147 | sizeof (IRA_INT_TYPE) * conflict_bit_vec_words_num); | |
148 | } | |
ae9587ed | 149 | |
150 | object_set_words = (ira_objects_num + IRA_INT_BITS - 1) / IRA_INT_BITS; | |
47dd2e78 | 151 | if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) |
152 | fprintf | |
153 | (ira_dump_file, | |
154 | "+++Allocating %ld bytes for conflict table (uncompressed size %ld)\n", | |
155 | (long) allocated_words_num * sizeof (IRA_INT_TYPE), | |
ae9587ed | 156 | (long) object_set_words * ira_objects_num * sizeof (IRA_INT_TYPE)); |
157 | ||
158 | objects_live = sparseset_alloc (ira_objects_num); | |
47dd2e78 | 159 | for (i = 0; i < ira_max_point; i++) |
160 | { | |
161 | for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next) | |
162 | { | |
9d53e372 | 163 | ira_object_t obj = r->object; |
164 | ira_allocno_t allocno = OBJECT_ALLOCNO (obj); | |
ae9587ed | 165 | int id = OBJECT_CONFLICT_ID (obj); |
166 | ||
be18556f | 167 | gcc_assert (id < ira_objects_num); |
168 | ||
66d9a7b9 | 169 | aclass = ALLOCNO_CLASS (allocno); |
ae9587ed | 170 | EXECUTE_IF_SET_IN_SPARSESET (objects_live, j) |
47dd2e78 | 171 | { |
be18556f | 172 | ira_object_t live_obj = ira_object_id_map[j]; |
173 | ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj); | |
66d9a7b9 | 174 | enum reg_class live_aclass = ALLOCNO_CLASS (live_a); |
ae9587ed | 175 | |
66d9a7b9 | 176 | if (ira_reg_classes_intersect_p[aclass][live_aclass] |
47dd2e78 | 177 | /* Don't set up conflict for the allocno with itself. */ |
be18556f | 178 | && live_a != allocno) |
47dd2e78 | 179 | { |
be18556f | 180 | record_object_conflict (obj, live_obj); |
47dd2e78 | 181 | } |
182 | } | |
630c50aa | 183 | sparseset_set_bit (objects_live, id); |
47dd2e78 | 184 | } |
48e1416a | 185 | |
47dd2e78 | 186 | for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next) |
be18556f | 187 | sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object)); |
47dd2e78 | 188 | } |
ae9587ed | 189 | sparseset_free (objects_live); |
95c83f01 | 190 | return true; |
47dd2e78 | 191 | } |
47dd2e78 | 192 | \f |
ae9587ed | 193 | /* Return true iff allocnos A1 and A2 cannot be allocated to the same |
194 | register due to conflicts. */ | |
195 | ||
196 | static bool | |
be18556f | 197 | allocnos_conflict_for_copy_p (ira_allocno_t a1, ira_allocno_t a2) |
ae9587ed | 198 | { |
be18556f | 199 | /* Due to the fact that we canonicalize conflicts (see |
200 | record_object_conflict), we only need to test for conflicts of | |
201 | the lowest order words. */ | |
202 | ira_object_t obj1 = ALLOCNO_OBJECT (a1, 0); | |
203 | ira_object_t obj2 = ALLOCNO_OBJECT (a2, 0); | |
66d9a7b9 | 204 | |
ae9587ed | 205 | return OBJECTS_CONFLICT_P (obj1, obj2); |
206 | } | |
47dd2e78 | 207 | |
f0a46d83 | 208 | /* Check that X is REG or SUBREG of REG. */ |
209 | #define REG_SUBREG_P(x) \ | |
210 | (REG_P (x) || (GET_CODE (x) == SUBREG && REG_P (SUBREG_REG (x)))) | |
211 | ||
212 | /* Return X if X is a REG, otherwise it should be SUBREG of REG and | |
213 | the function returns the reg in this case. *OFFSET will be set to | |
214 | 0 in the first case or the regno offset in the first case. */ | |
215 | static rtx | |
216 | go_through_subreg (rtx x, int *offset) | |
217 | { | |
218 | rtx reg; | |
219 | ||
220 | *offset = 0; | |
221 | if (REG_P (x)) | |
222 | return x; | |
223 | ira_assert (GET_CODE (x) == SUBREG); | |
224 | reg = SUBREG_REG (x); | |
225 | ira_assert (REG_P (reg)); | |
226 | if (REGNO (reg) < FIRST_PSEUDO_REGISTER) | |
227 | *offset = subreg_regno_offset (REGNO (reg), GET_MODE (reg), | |
228 | SUBREG_BYTE (x), GET_MODE (x)); | |
9edf7ea8 | 229 | else if (!can_div_trunc_p (SUBREG_BYTE (x), |
230 | REGMODE_NATURAL_SIZE (GET_MODE (x)), offset)) | |
231 | /* Checked by validate_subreg. We must know at compile time which | |
232 | inner hard registers are being accessed. */ | |
233 | gcc_unreachable (); | |
f0a46d83 | 234 | return reg; |
235 | } | |
236 | ||
47dd2e78 | 237 | /* Process registers REG1 and REG2 in move INSN with execution |
238 | frequency FREQ. The function also processes the registers in a | |
239 | potential move insn (INSN == NULL in this case) with frequency | |
240 | FREQ. The function can modify hard register costs of the | |
241 | corresponding allocnos or create a copy involving the corresponding | |
242 | allocnos. The function does nothing if the both registers are hard | |
243 | registers. When nothing is changed, the function returns | |
244 | FALSE. */ | |
245 | static bool | |
b7c06809 | 246 | process_regs_for_copy (rtx reg1, rtx reg2, bool constraint_p, |
56067879 | 247 | rtx_insn *insn, int freq) |
47dd2e78 | 248 | { |
296a743c | 249 | int allocno_preferenced_hard_regno, cost, index, offset1, offset2; |
f0a46d83 | 250 | bool only_regs_p; |
47dd2e78 | 251 | ira_allocno_t a; |
d3ba22dc | 252 | reg_class_t rclass, aclass; |
3754d046 | 253 | machine_mode mode; |
47dd2e78 | 254 | ira_copy_t cp; |
255 | ||
f0a46d83 | 256 | gcc_assert (REG_SUBREG_P (reg1) && REG_SUBREG_P (reg2)); |
257 | only_regs_p = REG_P (reg1) && REG_P (reg2); | |
258 | reg1 = go_through_subreg (reg1, &offset1); | |
259 | reg2 = go_through_subreg (reg2, &offset2); | |
296a743c | 260 | /* Set up hard regno preferenced by allocno. If allocno gets the |
261 | hard regno the copy (or potential move) insn will be removed. */ | |
47dd2e78 | 262 | if (HARD_REGISTER_P (reg1)) |
263 | { | |
264 | if (HARD_REGISTER_P (reg2)) | |
265 | return false; | |
296a743c | 266 | allocno_preferenced_hard_regno = REGNO (reg1) + offset1 - offset2; |
47dd2e78 | 267 | a = ira_curr_regno_allocno_map[REGNO (reg2)]; |
268 | } | |
269 | else if (HARD_REGISTER_P (reg2)) | |
270 | { | |
296a743c | 271 | allocno_preferenced_hard_regno = REGNO (reg2) + offset2 - offset1; |
47dd2e78 | 272 | a = ira_curr_regno_allocno_map[REGNO (reg1)]; |
273 | } | |
ae9587ed | 274 | else |
47dd2e78 | 275 | { |
ae9587ed | 276 | ira_allocno_t a1 = ira_curr_regno_allocno_map[REGNO (reg1)]; |
277 | ira_allocno_t a2 = ira_curr_regno_allocno_map[REGNO (reg2)]; | |
9f8ac546 | 278 | |
be18556f | 279 | if (!allocnos_conflict_for_copy_p (a1, a2) && offset1 == offset2) |
ae9587ed | 280 | { |
281 | cp = ira_add_allocno_copy (a1, a2, freq, constraint_p, insn, | |
282 | ira_curr_loop_tree_node); | |
283 | bitmap_set_bit (ira_curr_loop_tree_node->local_copies, cp->num); | |
284 | return true; | |
285 | } | |
286 | else | |
287 | return false; | |
47dd2e78 | 288 | } |
ae9587ed | 289 | |
66d9a7b9 | 290 | if (! IN_RANGE (allocno_preferenced_hard_regno, |
291 | 0, FIRST_PSEUDO_REGISTER - 1)) | |
f4d3c071 | 292 | /* Cannot be tied. */ |
296a743c | 293 | return false; |
294 | rclass = REGNO_REG_CLASS (allocno_preferenced_hard_regno); | |
47dd2e78 | 295 | mode = ALLOCNO_MODE (a); |
66d9a7b9 | 296 | aclass = ALLOCNO_CLASS (a); |
55c858c5 | 297 | if (only_regs_p && insn != NULL_RTX |
d3ba22dc | 298 | && reg_class_size[rclass] <= ira_reg_class_max_nregs [rclass][mode]) |
47dd2e78 | 299 | /* It is already taken into account in ira-costs.c. */ |
300 | return false; | |
66d9a7b9 | 301 | index = ira_class_hard_reg_index[aclass][allocno_preferenced_hard_regno]; |
47dd2e78 | 302 | if (index < 0) |
f4d3c071 | 303 | /* Cannot be tied. It is not in the allocno class. */ |
47dd2e78 | 304 | return false; |
66d9a7b9 | 305 | ira_init_register_move_cost_if_necessary (mode); |
47dd2e78 | 306 | if (HARD_REGISTER_P (reg1)) |
66d9a7b9 | 307 | cost = ira_register_move_cost[mode][aclass][rclass] * freq; |
47dd2e78 | 308 | else |
66d9a7b9 | 309 | cost = ira_register_move_cost[mode][rclass][aclass] * freq; |
c58db480 | 310 | do |
df07a54c | 311 | { |
312 | ira_allocate_and_set_costs | |
66d9a7b9 | 313 | (&ALLOCNO_HARD_REG_COSTS (a), aclass, |
314 | ALLOCNO_CLASS_COST (a)); | |
df07a54c | 315 | ira_allocate_and_set_costs |
66d9a7b9 | 316 | (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass, 0); |
df07a54c | 317 | ALLOCNO_HARD_REG_COSTS (a)[index] -= cost; |
318 | ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] -= cost; | |
66d9a7b9 | 319 | if (ALLOCNO_HARD_REG_COSTS (a)[index] < ALLOCNO_CLASS_COST (a)) |
320 | ALLOCNO_CLASS_COST (a) = ALLOCNO_HARD_REG_COSTS (a)[index]; | |
284f0696 | 321 | ira_add_allocno_pref (a, allocno_preferenced_hard_regno, freq); |
c58db480 | 322 | a = ira_parent_or_cap_allocno (a); |
df07a54c | 323 | } |
c58db480 | 324 | while (a != NULL); |
47dd2e78 | 325 | return true; |
326 | } | |
327 | ||
106453cc | 328 | /* Process all of the output registers of the current insn which are |
329 | not bound (BOUND_P) and the input register REG (its operand number | |
330 | OP_NUM) which dies in the insn as if there were a move insn between | |
331 | them with frequency FREQ. */ | |
47dd2e78 | 332 | static void |
106453cc | 333 | process_reg_shuffles (rtx reg, int op_num, int freq, bool *bound_p) |
47dd2e78 | 334 | { |
335 | int i; | |
336 | rtx another_reg; | |
337 | ||
f0a46d83 | 338 | gcc_assert (REG_SUBREG_P (reg)); |
47dd2e78 | 339 | for (i = 0; i < recog_data.n_operands; i++) |
340 | { | |
341 | another_reg = recog_data.operand[i]; | |
48e1416a | 342 | |
f0a46d83 | 343 | if (!REG_SUBREG_P (another_reg) || op_num == i |
106453cc | 344 | || recog_data.operand_type[i] != OP_OUT |
345 | || bound_p[i]) | |
47dd2e78 | 346 | continue; |
48e1416a | 347 | |
56067879 | 348 | process_regs_for_copy (reg, another_reg, false, NULL, freq); |
47dd2e78 | 349 | } |
350 | } | |
351 | ||
352 | /* Process INSN and create allocno copies if necessary. For example, | |
353 | it might be because INSN is a pseudo-register move or INSN is two | |
354 | operand insn. */ | |
355 | static void | |
56067879 | 356 | add_insn_allocno_copies (rtx_insn *insn) |
47dd2e78 | 357 | { |
4e51a669 | 358 | rtx set, operand, dup; |
284f0696 | 359 | bool bound_p[MAX_RECOG_OPERANDS]; |
360 | int i, n, freq; | |
361 | HARD_REG_SET alts; | |
ae9587ed | 362 | |
47dd2e78 | 363 | freq = REG_FREQ_FROM_BB (BLOCK_FOR_INSN (insn)); |
364 | if (freq == 0) | |
365 | freq = 1; | |
366 | if ((set = single_set (insn)) != NULL_RTX | |
f0a46d83 | 367 | && REG_SUBREG_P (SET_DEST (set)) && REG_SUBREG_P (SET_SRC (set)) |
47dd2e78 | 368 | && ! side_effects_p (set) |
f0a46d83 | 369 | && find_reg_note (insn, REG_DEAD, |
370 | REG_P (SET_SRC (set)) | |
371 | ? SET_SRC (set) | |
372 | : SUBREG_REG (SET_SRC (set))) != NULL_RTX) | |
47dd2e78 | 373 | { |
284f0696 | 374 | process_regs_for_copy (SET_SRC (set), SET_DEST (set), |
66d9a7b9 | 375 | false, insn, freq); |
106453cc | 376 | return; |
377 | } | |
4e51a669 | 378 | /* Fast check of possibility of constraint or shuffle copies. If |
379 | there are no dead registers, there will be no such copies. */ | |
380 | if (! find_reg_note (insn, REG_DEAD, NULL_RTX)) | |
106453cc | 381 | return; |
284f0696 | 382 | ira_setup_alts (insn, alts); |
106453cc | 383 | for (i = 0; i < recog_data.n_operands; i++) |
384 | bound_p[i] = false; | |
385 | for (i = 0; i < recog_data.n_operands; i++) | |
386 | { | |
387 | operand = recog_data.operand[i]; | |
388 | if (! REG_SUBREG_P (operand)) | |
389 | continue; | |
284f0696 | 390 | if ((n = ira_get_dup_out_num (i, alts)) >= 0) |
391 | { | |
392 | bound_p[n] = true; | |
393 | dup = recog_data.operand[n]; | |
394 | if (REG_SUBREG_P (dup) | |
395 | && find_reg_note (insn, REG_DEAD, | |
396 | REG_P (operand) | |
397 | ? operand | |
398 | : SUBREG_REG (operand)) != NULL_RTX) | |
56067879 | 399 | process_regs_for_copy (operand, dup, true, NULL, |
284f0696 | 400 | freq); |
401 | } | |
106453cc | 402 | } |
403 | for (i = 0; i < recog_data.n_operands; i++) | |
404 | { | |
405 | operand = recog_data.operand[i]; | |
406 | if (REG_SUBREG_P (operand) | |
407 | && find_reg_note (insn, REG_DEAD, | |
408 | REG_P (operand) | |
409 | ? operand : SUBREG_REG (operand)) != NULL_RTX) | |
410 | /* If an operand dies, prefer its hard register for the output | |
411 | operands by decreasing the hard register cost or creating | |
412 | the corresponding allocno copies. The cost will not | |
413 | correspond to a real move insn cost, so make the frequency | |
414 | smaller. */ | |
415 | process_reg_shuffles (operand, i, freq < 8 ? 1 : freq / 8, bound_p); | |
47dd2e78 | 416 | } |
417 | } | |
418 | ||
419 | /* Add copies originated from BB given by LOOP_TREE_NODE. */ | |
420 | static void | |
421 | add_copies (ira_loop_tree_node_t loop_tree_node) | |
422 | { | |
423 | basic_block bb; | |
56067879 | 424 | rtx_insn *insn; |
47dd2e78 | 425 | |
426 | bb = loop_tree_node->bb; | |
427 | if (bb == NULL) | |
428 | return; | |
429 | FOR_BB_INSNS (bb, insn) | |
9845d120 | 430 | if (NONDEBUG_INSN_P (insn)) |
47dd2e78 | 431 | add_insn_allocno_copies (insn); |
432 | } | |
433 | ||
434 | /* Propagate copies the corresponding allocnos on upper loop tree | |
435 | level. */ | |
436 | static void | |
437 | propagate_copies (void) | |
438 | { | |
439 | ira_copy_t cp; | |
440 | ira_copy_iterator ci; | |
441 | ira_allocno_t a1, a2, parent_a1, parent_a2; | |
47dd2e78 | 442 | |
443 | FOR_EACH_COPY (cp, ci) | |
444 | { | |
445 | a1 = cp->first; | |
446 | a2 = cp->second; | |
447 | if (ALLOCNO_LOOP_TREE_NODE (a1) == ira_loop_tree_root) | |
448 | continue; | |
449 | ira_assert ((ALLOCNO_LOOP_TREE_NODE (a2) != ira_loop_tree_root)); | |
c58db480 | 450 | parent_a1 = ira_parent_or_cap_allocno (a1); |
451 | parent_a2 = ira_parent_or_cap_allocno (a2); | |
47dd2e78 | 452 | ira_assert (parent_a1 != NULL && parent_a2 != NULL); |
be18556f | 453 | if (! allocnos_conflict_for_copy_p (parent_a1, parent_a2)) |
b7c06809 | 454 | ira_add_allocno_copy (parent_a1, parent_a2, cp->freq, |
455 | cp->constraint_p, cp->insn, cp->loop_tree_node); | |
47dd2e78 | 456 | } |
457 | } | |
458 | ||
47dd2e78 | 459 | /* Array used to collect all conflict allocnos for given allocno. */ |
ae9587ed | 460 | static ira_object_t *collected_conflict_objects; |
47dd2e78 | 461 | |
462 | /* Build conflict vectors or bit conflict vectors (whatever is more | |
be18556f | 463 | profitable) for object OBJ from the conflict table. */ |
47dd2e78 | 464 | static void |
be18556f | 465 | build_object_conflicts (ira_object_t obj) |
47dd2e78 | 466 | { |
467 | int i, px, parent_num; | |
ae9587ed | 468 | ira_allocno_t parent_a, another_parent_a; |
be18556f | 469 | ira_object_t parent_obj; |
470 | ira_allocno_t a = OBJECT_ALLOCNO (obj); | |
471 | IRA_INT_TYPE *object_conflicts; | |
01eb3997 | 472 | minmax_set_iterator asi; |
71a39acf | 473 | int parent_min, parent_max ATTRIBUTE_UNUSED; |
47dd2e78 | 474 | |
be18556f | 475 | object_conflicts = conflicts[OBJECT_CONFLICT_ID (obj)]; |
47dd2e78 | 476 | px = 0; |
be18556f | 477 | FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts, |
ae9587ed | 478 | OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi) |
47dd2e78 | 479 | { |
ae9587ed | 480 | ira_object_t another_obj = ira_object_id_map[i]; |
481 | ira_allocno_t another_a = OBJECT_ALLOCNO (obj); | |
66d9a7b9 | 482 | |
14792f4e | 483 | ira_assert (ira_reg_classes_intersect_p |
66d9a7b9 | 484 | [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]); |
ae9587ed | 485 | collected_conflict_objects[px++] = another_obj; |
47dd2e78 | 486 | } |
ae9587ed | 487 | if (ira_conflict_vector_profitable_p (obj, px)) |
47dd2e78 | 488 | { |
be18556f | 489 | ira_object_t *vec; |
ae9587ed | 490 | ira_allocate_conflict_vec (obj, px); |
491 | vec = OBJECT_CONFLICT_VEC (obj); | |
492 | memcpy (vec, collected_conflict_objects, sizeof (ira_object_t) * px); | |
47dd2e78 | 493 | vec[px] = NULL; |
ae9587ed | 494 | OBJECT_NUM_CONFLICTS (obj) = px; |
47dd2e78 | 495 | } |
496 | else | |
497 | { | |
be18556f | 498 | int conflict_bit_vec_words_num; |
66d9a7b9 | 499 | |
be18556f | 500 | OBJECT_CONFLICT_ARRAY (obj) = object_conflicts; |
ae9587ed | 501 | if (OBJECT_MAX (obj) < OBJECT_MIN (obj)) |
47dd2e78 | 502 | conflict_bit_vec_words_num = 0; |
503 | else | |
504 | conflict_bit_vec_words_num | |
ae9587ed | 505 | = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS) |
47dd2e78 | 506 | / IRA_INT_BITS); |
ae9587ed | 507 | OBJECT_CONFLICT_ARRAY_SIZE (obj) |
47dd2e78 | 508 | = conflict_bit_vec_words_num * sizeof (IRA_INT_TYPE); |
509 | } | |
be18556f | 510 | |
c58db480 | 511 | parent_a = ira_parent_or_cap_allocno (a); |
512 | if (parent_a == NULL) | |
47dd2e78 | 513 | return; |
66d9a7b9 | 514 | ira_assert (ALLOCNO_CLASS (a) == ALLOCNO_CLASS (parent_a)); |
be18556f | 515 | ira_assert (ALLOCNO_NUM_OBJECTS (a) == ALLOCNO_NUM_OBJECTS (parent_a)); |
516 | parent_obj = ALLOCNO_OBJECT (parent_a, OBJECT_SUBWORD (obj)); | |
ae9587ed | 517 | parent_num = OBJECT_CONFLICT_ID (parent_obj); |
66d9a7b9 | 518 | parent_min = OBJECT_MIN (parent_obj); |
519 | parent_max = OBJECT_MAX (parent_obj); | |
be18556f | 520 | FOR_EACH_BIT_IN_MINMAX_SET (object_conflicts, |
ae9587ed | 521 | OBJECT_MIN (obj), OBJECT_MAX (obj), i, asi) |
47dd2e78 | 522 | { |
ae9587ed | 523 | ira_object_t another_obj = ira_object_id_map[i]; |
524 | ira_allocno_t another_a = OBJECT_ALLOCNO (another_obj); | |
be18556f | 525 | int another_word = OBJECT_SUBWORD (another_obj); |
ae9587ed | 526 | |
14792f4e | 527 | ira_assert (ira_reg_classes_intersect_p |
66d9a7b9 | 528 | [ALLOCNO_CLASS (a)][ALLOCNO_CLASS (another_a)]); |
be18556f | 529 | |
c58db480 | 530 | another_parent_a = ira_parent_or_cap_allocno (another_a); |
531 | if (another_parent_a == NULL) | |
47dd2e78 | 532 | continue; |
533 | ira_assert (ALLOCNO_NUM (another_parent_a) >= 0); | |
66d9a7b9 | 534 | ira_assert (ALLOCNO_CLASS (another_a) |
535 | == ALLOCNO_CLASS (another_parent_a)); | |
be18556f | 536 | ira_assert (ALLOCNO_NUM_OBJECTS (another_a) |
537 | == ALLOCNO_NUM_OBJECTS (another_parent_a)); | |
01eb3997 | 538 | SET_MINMAX_SET_BIT (conflicts[parent_num], |
be18556f | 539 | OBJECT_CONFLICT_ID (ALLOCNO_OBJECT (another_parent_a, |
66d9a7b9 | 540 | another_word)), |
541 | parent_min, parent_max); | |
47dd2e78 | 542 | } |
543 | } | |
544 | ||
545 | /* Build conflict vectors or bit conflict vectors (whatever is more | |
546 | profitable) of all allocnos from the conflict table. */ | |
547 | static void | |
548 | build_conflicts (void) | |
549 | { | |
550 | int i; | |
551 | ira_allocno_t a, cap; | |
552 | ||
ae9587ed | 553 | collected_conflict_objects |
554 | = (ira_object_t *) ira_allocate (sizeof (ira_object_t) | |
555 | * ira_objects_num); | |
47dd2e78 | 556 | for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) |
557 | for (a = ira_regno_allocno_map[i]; | |
558 | a != NULL; | |
559 | a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) | |
560 | { | |
be18556f | 561 | int j, nregs = ALLOCNO_NUM_OBJECTS (a); |
562 | for (j = 0; j < nregs; j++) | |
563 | { | |
564 | ira_object_t obj = ALLOCNO_OBJECT (a, j); | |
565 | build_object_conflicts (obj); | |
566 | for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap)) | |
567 | { | |
568 | ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j); | |
569 | gcc_assert (ALLOCNO_NUM_OBJECTS (cap) == ALLOCNO_NUM_OBJECTS (a)); | |
570 | build_object_conflicts (cap_obj); | |
571 | } | |
572 | } | |
47dd2e78 | 573 | } |
ae9587ed | 574 | ira_free (collected_conflict_objects); |
47dd2e78 | 575 | } |
576 | ||
577 | \f | |
578 | ||
579 | /* Print hard reg set SET with TITLE to FILE. */ | |
580 | static void | |
581 | print_hard_reg_set (FILE *file, const char *title, HARD_REG_SET set) | |
582 | { | |
583 | int i, start; | |
584 | ||
609e7ca1 | 585 | fputs (title, file); |
47dd2e78 | 586 | for (start = -1, i = 0; i < FIRST_PSEUDO_REGISTER; i++) |
587 | { | |
588 | if (TEST_HARD_REG_BIT (set, i)) | |
589 | { | |
590 | if (i == 0 || ! TEST_HARD_REG_BIT (set, i - 1)) | |
591 | start = i; | |
592 | } | |
593 | if (start >= 0 | |
594 | && (i == FIRST_PSEUDO_REGISTER - 1 || ! TEST_HARD_REG_BIT (set, i))) | |
595 | { | |
596 | if (start == i - 1) | |
597 | fprintf (file, " %d", start); | |
598 | else if (start == i - 2) | |
599 | fprintf (file, " %d %d", start, start + 1); | |
600 | else | |
601 | fprintf (file, " %d-%d", start, i - 1); | |
602 | start = -1; | |
603 | } | |
604 | } | |
609e7ca1 | 605 | putc ('\n', file); |
47dd2e78 | 606 | } |
607 | ||
47dd2e78 | 608 | static void |
c32f7a5a | 609 | print_allocno_conflicts (FILE * file, bool reg_p, ira_allocno_t a) |
47dd2e78 | 610 | { |
47dd2e78 | 611 | HARD_REG_SET conflicting_hard_regs; |
c32f7a5a | 612 | basic_block bb; |
be18556f | 613 | int n, i; |
47dd2e78 | 614 | |
c32f7a5a | 615 | if (reg_p) |
616 | fprintf (file, ";; r%d", ALLOCNO_REGNO (a)); | |
617 | else | |
47dd2e78 | 618 | { |
c32f7a5a | 619 | fprintf (file, ";; a%d(r%d,", ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); |
620 | if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL) | |
621 | fprintf (file, "b%d", bb->index); | |
47dd2e78 | 622 | else |
9f8ac546 | 623 | fprintf (file, "l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num); |
c32f7a5a | 624 | putc (')', file); |
625 | } | |
ae9587ed | 626 | |
c32f7a5a | 627 | fputs (" conflicts:", file); |
be18556f | 628 | n = ALLOCNO_NUM_OBJECTS (a); |
629 | for (i = 0; i < n; i++) | |
630 | { | |
631 | ira_object_t obj = ALLOCNO_OBJECT (a, i); | |
632 | ira_object_t conflict_obj; | |
633 | ira_object_conflict_iterator oci; | |
634 | ||
635 | if (OBJECT_CONFLICT_ARRAY (obj) == NULL) | |
636 | continue; | |
637 | if (n > 1) | |
638 | fprintf (file, "\n;; subobject %d:", i); | |
639 | FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci) | |
640 | { | |
641 | ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj); | |
642 | if (reg_p) | |
643 | fprintf (file, " r%d,", ALLOCNO_REGNO (conflict_a)); | |
644 | else | |
645 | { | |
646 | fprintf (file, " a%d(r%d", ALLOCNO_NUM (conflict_a), | |
647 | ALLOCNO_REGNO (conflict_a)); | |
648 | if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1) | |
649 | fprintf (file, ",w%d", OBJECT_SUBWORD (conflict_obj)); | |
650 | if ((bb = ALLOCNO_LOOP_TREE_NODE (conflict_a)->bb) != NULL) | |
651 | fprintf (file, ",b%d", bb->index); | |
652 | else | |
653 | fprintf (file, ",l%d", | |
9f8ac546 | 654 | ALLOCNO_LOOP_TREE_NODE (conflict_a)->loop_num); |
be18556f | 655 | putc (')', file); |
656 | } | |
657 | } | |
658 | COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)); | |
659 | AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs); | |
660 | AND_HARD_REG_SET (conflicting_hard_regs, | |
66d9a7b9 | 661 | reg_class_contents[ALLOCNO_CLASS (a)]); |
be18556f | 662 | print_hard_reg_set (file, "\n;; total conflict hard regs:", |
663 | conflicting_hard_regs); | |
664 | ||
665 | COPY_HARD_REG_SET (conflicting_hard_regs, OBJECT_CONFLICT_HARD_REGS (obj)); | |
666 | AND_COMPL_HARD_REG_SET (conflicting_hard_regs, ira_no_alloc_regs); | |
667 | AND_HARD_REG_SET (conflicting_hard_regs, | |
66d9a7b9 | 668 | reg_class_contents[ALLOCNO_CLASS (a)]); |
be18556f | 669 | print_hard_reg_set (file, ";; conflict hard regs:", |
670 | conflicting_hard_regs); | |
671 | putc ('\n', file); | |
672 | } | |
ae9587ed | 673 | |
47dd2e78 | 674 | } |
675 | ||
c32f7a5a | 676 | /* Print information about allocno or only regno (if REG_P) conflicts |
677 | to FILE. */ | |
678 | static void | |
679 | print_conflicts (FILE *file, bool reg_p) | |
680 | { | |
681 | ira_allocno_t a; | |
682 | ira_allocno_iterator ai; | |
683 | ||
684 | FOR_EACH_ALLOCNO (a, ai) | |
685 | print_allocno_conflicts (file, reg_p, a); | |
686 | } | |
687 | ||
47dd2e78 | 688 | /* Print information about allocno or only regno (if REG_P) conflicts |
689 | to stderr. */ | |
690 | void | |
691 | ira_debug_conflicts (bool reg_p) | |
692 | { | |
693 | print_conflicts (stderr, reg_p); | |
694 | } | |
695 | ||
696 | \f | |
697 | ||
698 | /* Entry function which builds allocno conflicts and allocno copies | |
699 | and accumulate some allocno info on upper level regions. */ | |
700 | void | |
701 | ira_build_conflicts (void) | |
702 | { | |
f8a8fc7b | 703 | enum reg_class base; |
47dd2e78 | 704 | ira_allocno_t a; |
705 | ira_allocno_iterator ai; | |
14792f4e | 706 | HARD_REG_SET temp_hard_reg_set; |
47dd2e78 | 707 | |
95c83f01 | 708 | if (ira_conflicts_p) |
47dd2e78 | 709 | { |
95c83f01 | 710 | ira_conflicts_p = build_conflict_bit_table (); |
711 | if (ira_conflicts_p) | |
47dd2e78 | 712 | { |
ae9587ed | 713 | ira_object_t obj; |
714 | ira_object_iterator oi; | |
715 | ||
95c83f01 | 716 | build_conflicts (); |
d068a2f3 | 717 | ira_traverse_loop_tree (true, ira_loop_tree_root, add_copies, NULL); |
95c83f01 | 718 | /* We need finished conflict table for the subsequent call. */ |
719 | if (flag_ira_region == IRA_REGION_ALL | |
720 | || flag_ira_region == IRA_REGION_MIXED) | |
721 | propagate_copies (); | |
ae9587ed | 722 | |
95c83f01 | 723 | /* Now we can free memory for the conflict table (see function |
be18556f | 724 | build_object_conflicts for details). */ |
ae9587ed | 725 | FOR_EACH_OBJECT (obj, oi) |
95c83f01 | 726 | { |
ae9587ed | 727 | if (OBJECT_CONFLICT_ARRAY (obj) != conflicts[OBJECT_CONFLICT_ID (obj)]) |
728 | ira_free (conflicts[OBJECT_CONFLICT_ID (obj)]); | |
95c83f01 | 729 | } |
730 | ira_free (conflicts); | |
47dd2e78 | 731 | } |
47dd2e78 | 732 | } |
f8a8fc7b | 733 | base = base_reg_class (VOIDmode, ADDR_SPACE_GENERIC, ADDRESS, SCRATCH); |
734 | if (! targetm.class_likely_spilled_p (base)) | |
14792f4e | 735 | CLEAR_HARD_REG_SET (temp_hard_reg_set); |
736 | else | |
737 | { | |
f8a8fc7b | 738 | COPY_HARD_REG_SET (temp_hard_reg_set, reg_class_contents[base]); |
14792f4e | 739 | AND_COMPL_HARD_REG_SET (temp_hard_reg_set, ira_no_alloc_regs); |
740 | AND_HARD_REG_SET (temp_hard_reg_set, call_used_reg_set); | |
741 | } | |
47dd2e78 | 742 | FOR_EACH_ALLOCNO (a, ai) |
743 | { | |
be18556f | 744 | int i, n = ALLOCNO_NUM_OBJECTS (a); |
66d9a7b9 | 745 | |
be18556f | 746 | for (i = 0; i < n; i++) |
47dd2e78 | 747 | { |
be18556f | 748 | ira_object_t obj = ALLOCNO_OBJECT (a, i); |
5da94e60 | 749 | machine_mode obj_mode = obj->allocno->mode; |
62f13add | 750 | rtx allocno_reg = regno_reg_rtx [ALLOCNO_REGNO (a)]; |
be18556f | 751 | |
752 | if ((! flag_caller_saves && ALLOCNO_CALLS_CROSSED_NUM (a) != 0) | |
753 | /* For debugging purposes don't put user defined variables in | |
ea239197 | 754 | callee-clobbered registers. However, do allow parameters |
755 | in callee-clobbered registers to improve debugging. This | |
756 | is a bit of a fragile hack. */ | |
757 | || (optimize == 0 | |
758 | && REG_USERVAR_P (allocno_reg) | |
759 | && ! reg_is_parm_p (allocno_reg))) | |
be18556f | 760 | { |
761 | IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), | |
762 | call_used_reg_set); | |
763 | IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), | |
764 | call_used_reg_set); | |
765 | } | |
766 | else if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0) | |
767 | { | |
768 | IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), | |
769 | no_caller_save_reg_set); | |
770 | IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), | |
771 | temp_hard_reg_set); | |
772 | IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), | |
773 | no_caller_save_reg_set); | |
774 | IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), | |
775 | temp_hard_reg_set); | |
776 | } | |
6b71fb7f | 777 | |
d02274e6 | 778 | /* Now we deal with paradoxical subreg cases where certain registers |
779 | cannot be accessed in the widest mode. */ | |
3754d046 | 780 | machine_mode outer_mode = ALLOCNO_WMODE (a); |
781 | machine_mode inner_mode = ALLOCNO_MODE (a); | |
d0257d43 | 782 | if (paradoxical_subreg_p (outer_mode, inner_mode)) |
d02274e6 | 783 | { |
784 | enum reg_class aclass = ALLOCNO_CLASS (a); | |
785 | for (int j = ira_class_hard_regs_num[aclass] - 1; j >= 0; --j) | |
786 | { | |
787 | int inner_regno = ira_class_hard_regs[aclass][j]; | |
788 | int outer_regno = simplify_subreg_regno (inner_regno, | |
789 | inner_mode, 0, | |
790 | outer_mode); | |
791 | if (outer_regno < 0 | |
792 | || !in_hard_reg_set_p (reg_class_contents[aclass], | |
793 | outer_mode, outer_regno)) | |
476b744d | 794 | { |
795 | SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), | |
796 | inner_regno); | |
797 | SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), | |
798 | inner_regno); | |
799 | } | |
d02274e6 | 800 | } |
801 | } | |
802 | ||
6b71fb7f | 803 | if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0) |
804 | { | |
805 | int regno; | |
806 | ||
807 | /* Allocnos bigger than the saved part of call saved | |
808 | regs must conflict with them. */ | |
809 | for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) | |
810 | if (!TEST_HARD_REG_BIT (call_used_reg_set, regno) | |
5c62f29a | 811 | && targetm.hard_regno_call_part_clobbered (NULL, regno, |
5da94e60 | 812 | obj_mode)) |
6b71fb7f | 813 | { |
814 | SET_HARD_REG_BIT (OBJECT_CONFLICT_HARD_REGS (obj), regno); | |
815 | SET_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), | |
816 | regno); | |
817 | } | |
818 | } | |
47dd2e78 | 819 | } |
820 | } | |
95c83f01 | 821 | if (optimize && ira_conflicts_p |
822 | && internal_flag_ira_verbose > 2 && ira_dump_file != NULL) | |
47dd2e78 | 823 | print_conflicts (ira_dump_file, false); |
824 | } |