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