]>
Commit | Line | Data |
---|---|---|
55a2c322 | 1 | /* Local Register Allocator (LRA) intercommunication header file. |
d1e082c2 | 2 | Copyright (C) 2010-2013 Free Software Foundation, Inc. |
55a2c322 VM |
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 "lra.h" | |
22 | #include "bitmap.h" | |
23 | #include "recog.h" | |
24 | #include "insn-attr.h" | |
25 | #include "insn-codes.h" | |
7b3b6ae4 LC |
26 | #include "insn-config.h" |
27 | #include "regs.h" | |
55a2c322 | 28 | |
a202e609 | 29 | #define lra_assert(c) gcc_checking_assert (c) |
55a2c322 VM |
30 | |
31 | /* The parameter used to prevent infinite reloading for an insn. Each | |
32 | insn operands might require a reload and, if it is a memory, its | |
33 | base and index registers might require a reload too. */ | |
34 | #define LRA_MAX_INSN_RELOADS (MAX_RECOG_OPERANDS * 3) | |
35 | ||
36 | /* Return the hard register which given pseudo REGNO assigned to. | |
37 | Negative value means that the register got memory or we don't know | |
38 | allocation yet. */ | |
39 | static inline int | |
40 | lra_get_regno_hard_regno (int regno) | |
41 | { | |
42 | resize_reg_info (); | |
43 | return reg_renumber[regno]; | |
44 | } | |
45 | ||
46 | typedef struct lra_live_range *lra_live_range_t; | |
47 | ||
48 | /* The structure describes program points where a given pseudo lives. | |
49 | The live ranges can be used to find conflicts with other pseudos. | |
50 | If the live ranges of two pseudos are intersected, the pseudos are | |
51 | in conflict. */ | |
52 | struct lra_live_range | |
53 | { | |
54 | /* Pseudo regno whose live range is described by given | |
55 | structure. */ | |
56 | int regno; | |
57 | /* Program point range. */ | |
58 | int start, finish; | |
59 | /* Next structure describing program points where the pseudo | |
60 | lives. */ | |
61 | lra_live_range_t next; | |
62 | /* Pointer to structures with the same start. */ | |
63 | lra_live_range_t start_next; | |
64 | }; | |
65 | ||
66 | typedef struct lra_copy *lra_copy_t; | |
67 | ||
68 | /* Copy between pseudos which affects assigning hard registers. */ | |
69 | struct lra_copy | |
70 | { | |
71 | /* True if regno1 is the destination of the copy. */ | |
72 | bool regno1_dest_p; | |
73 | /* Execution frequency of the copy. */ | |
74 | int freq; | |
75 | /* Pseudos connected by the copy. REGNO1 < REGNO2. */ | |
76 | int regno1, regno2; | |
77 | /* Next copy with correspondingly REGNO1 and REGNO2. */ | |
78 | lra_copy_t regno1_next, regno2_next; | |
79 | }; | |
80 | ||
81 | /* Common info about a register (pseudo or hard register). */ | |
82 | struct lra_reg | |
83 | { | |
84 | /* Bitmap of UIDs of insns (including debug insns) referring the | |
85 | reg. */ | |
86 | bitmap_head insn_bitmap; | |
87 | /* The following fields are defined only for pseudos. */ | |
88 | /* Hard registers with which the pseudo conflicts. */ | |
89 | HARD_REG_SET conflict_hard_regs; | |
90 | /* We assign hard registers to reload pseudos which can occur in few | |
91 | places. So two hard register preferences are enough for them. | |
92 | The following fields define the preferred hard registers. If | |
93 | there are no such hard registers the first field value is | |
94 | negative. If there is only one preferred hard register, the 2nd | |
95 | field is negative. */ | |
96 | int preferred_hard_regno1, preferred_hard_regno2; | |
97 | /* Profits to use the corresponding preferred hard registers. If | |
98 | the both hard registers defined, the first hard register has not | |
99 | less profit than the second one. */ | |
100 | int preferred_hard_regno_profit1, preferred_hard_regno_profit2; | |
101 | #ifdef STACK_REGS | |
102 | /* True if the pseudo should not be assigned to a stack register. */ | |
103 | bool no_stack_p; | |
104 | #endif | |
105 | #ifdef ENABLE_CHECKING | |
106 | /* True if the pseudo crosses a call. It is setup in lra-lives.c | |
107 | and used to check that the pseudo crossing a call did not get a | |
108 | call used hard register. */ | |
109 | bool call_p; | |
110 | #endif | |
111 | /* Number of references and execution frequencies of the register in | |
112 | *non-debug* insns. */ | |
113 | int nrefs, freq; | |
114 | int last_reload; | |
115 | /* Regno used to undo the inheritance. It can be non-zero only | |
116 | between couple of inheritance and undo inheritance passes. */ | |
117 | int restore_regno; | |
118 | /* Value holding by register. If the pseudos have the same value | |
119 | they do not conflict. */ | |
120 | int val; | |
121 | /* These members are set up in lra-lives.c and updated in | |
122 | lra-coalesce.c. */ | |
123 | /* The biggest size mode in which each pseudo reg is referred in | |
124 | whole function (possibly via subreg). */ | |
125 | enum machine_mode biggest_mode; | |
126 | /* Live ranges of the pseudo. */ | |
127 | lra_live_range_t live_ranges; | |
128 | /* This member is set up in lra-lives.c for subsequent | |
129 | assignments. */ | |
130 | lra_copy_t copies; | |
131 | }; | |
132 | ||
133 | /* References to the common info about each register. */ | |
134 | extern struct lra_reg *lra_reg_info; | |
135 | ||
136 | /* Static info about each insn operand (common for all insns with the | |
137 | same ICODE). Warning: if the structure definition is changed, the | |
138 | initializer for debug_operand_data in lra.c should be changed | |
139 | too. */ | |
140 | struct lra_operand_data | |
141 | { | |
142 | /* The machine description constraint string of the operand. */ | |
143 | const char *constraint; | |
144 | /* It is taken only from machine description (which is different | |
145 | from recog_data.operand_mode) and can be of VOIDmode. */ | |
146 | ENUM_BITFIELD(machine_mode) mode : 16; | |
147 | /* The type of the operand (in/out/inout). */ | |
148 | ENUM_BITFIELD (op_type) type : 8; | |
149 | /* Through if accessed through STRICT_LOW. */ | |
150 | unsigned int strict_low : 1; | |
151 | /* True if the operand is an operator. */ | |
152 | unsigned int is_operator : 1; | |
153 | /* True if there is an early clobber alternative for this operand. | |
154 | This field is set up every time when corresponding | |
155 | operand_alternative in lra_static_insn_data is set up. */ | |
156 | unsigned int early_clobber : 1; | |
157 | /* True if the operand is an address. */ | |
158 | unsigned int is_address : 1; | |
159 | }; | |
160 | ||
161 | /* Info about register occurrence in an insn. */ | |
162 | struct lra_insn_reg | |
163 | { | |
164 | /* The biggest mode through which the insn refers to the register | |
165 | occurrence (remember the register can be accessed through a | |
166 | subreg in the insn). */ | |
167 | ENUM_BITFIELD(machine_mode) biggest_mode : 16; | |
168 | /* The type of the corresponding operand which is the register. */ | |
169 | ENUM_BITFIELD (op_type) type : 8; | |
170 | /* True if the reg is accessed through a subreg and the subreg is | |
171 | just a part of the register. */ | |
172 | unsigned int subreg_p : 1; | |
173 | /* True if there is an early clobber alternative for this | |
174 | operand. */ | |
175 | unsigned int early_clobber : 1; | |
176 | /* The corresponding regno of the register. */ | |
177 | int regno; | |
178 | /* Next reg info of the same insn. */ | |
179 | struct lra_insn_reg *next; | |
180 | }; | |
181 | ||
182 | /* Static part (common info for insns with the same ICODE) of LRA | |
183 | internal insn info. It exists in at most one exemplar for each | |
184 | non-negative ICODE. There is only one exception. Each asm insn has | |
185 | own structure. Warning: if the structure definition is changed, | |
186 | the initializer for debug_insn_static_data in lra.c should be | |
187 | changed too. */ | |
188 | struct lra_static_insn_data | |
189 | { | |
190 | /* Static info about each insn operand. */ | |
191 | struct lra_operand_data *operand; | |
192 | /* Each duplication refers to the number of the corresponding | |
193 | operand which is duplicated. */ | |
194 | int *dup_num; | |
195 | /* The number of an operand marked as commutative, -1 otherwise. */ | |
196 | int commutative; | |
197 | /* Number of operands, duplications, and alternatives of the | |
198 | insn. */ | |
199 | char n_operands; | |
200 | char n_dups; | |
201 | char n_alternatives; | |
202 | /* Insns in machine description (or clobbers in asm) may contain | |
203 | explicit hard regs which are not operands. The following list | |
204 | describes such hard registers. */ | |
205 | struct lra_insn_reg *hard_regs; | |
206 | /* Array [n_alternatives][n_operand] of static constraint info for | |
207 | given operand in given alternative. This info can be changed if | |
208 | the target reg info is changed. */ | |
209 | struct operand_alternative *operand_alternative; | |
210 | }; | |
211 | ||
212 | /* LRA internal info about an insn (LRA internal insn | |
213 | representation). */ | |
214 | struct lra_insn_recog_data | |
215 | { | |
216 | /* The insn code. */ | |
217 | int icode; | |
218 | /* The insn itself. */ | |
219 | rtx insn; | |
220 | /* Common data for insns with the same ICODE. Asm insns (their | |
221 | ICODE is negative) do not share such structures. */ | |
222 | struct lra_static_insn_data *insn_static_data; | |
223 | /* Two arrays of size correspondingly equal to the operand and the | |
224 | duplication numbers: */ | |
225 | rtx **operand_loc; /* The operand locations, NULL if no operands. */ | |
226 | rtx **dup_loc; /* The dup locations, NULL if no dups. */ | |
227 | /* Number of hard registers implicitly used in given call insn. The | |
228 | value can be NULL or points to array of the hard register numbers | |
229 | ending with a negative value. */ | |
230 | int *arg_hard_regs; | |
55a2c322 VM |
231 | /* Alternative enabled for the insn. NULL for debug insns. */ |
232 | bool *alternative_enabled_p; | |
55a2c322 VM |
233 | /* The alternative should be used for the insn, -1 if invalid, or we |
234 | should try to use any alternative, or the insn is a debug | |
235 | insn. */ | |
236 | int used_insn_alternative; | |
237 | /* The following member value is always NULL for a debug insn. */ | |
238 | struct lra_insn_reg *regs; | |
239 | }; | |
240 | ||
241 | typedef struct lra_insn_recog_data *lra_insn_recog_data_t; | |
242 | ||
c5cd5a7e VM |
243 | /* Whether the clobber is used temporary in LRA. */ |
244 | #define LRA_TEMP_CLOBBER_P(x) \ | |
245 | (RTL_FLAG_CHECK1 ("TEMP_CLOBBER_P", (x), CLOBBER)->unchanging) | |
246 | ||
821b7577 VM |
247 | /* Cost factor for each additional reload and maximal cost reject for |
248 | insn reloads. One might ask about such strange numbers. Their | |
249 | values occurred historically from former reload pass. */ | |
250 | #define LRA_LOSER_COST_FACTOR 6 | |
251 | #define LRA_MAX_REJECT 600 | |
252 | ||
8e3a4869 VM |
253 | /* Maximum allowed number of constraint pass iterations after the last |
254 | spill pass. It is for preventing LRA cycling in a bug case. */ | |
255 | #define LRA_MAX_CONSTRAINT_ITERATION_NUMBER 30 | |
256 | ||
257 | /* The maximal number of inheritance/split passes in LRA. It should | |
258 | be more 1 in order to perform caller saves transformations and much | |
259 | less MAX_CONSTRAINT_ITERATION_NUMBER to prevent LRA to do as many | |
260 | as permitted constraint passes in some complicated cases. The | |
261 | first inheritance/split pass has a biggest impact on generated code | |
262 | quality. Each subsequent affects generated code in less degree. | |
263 | For example, the 3rd pass does not change generated SPEC2000 code | |
264 | at all on x86-64. */ | |
265 | #define LRA_MAX_INHERITANCE_PASSES 2 | |
266 | ||
267 | #if LRA_MAX_INHERITANCE_PASSES <= 0 \ | |
268 | || LRA_MAX_INHERITANCE_PASSES >= LRA_MAX_CONSTRAINT_ITERATION_NUMBER - 8 | |
269 | #error wrong LRA_MAX_INHERITANCE_PASSES value | |
270 | #endif | |
271 | ||
55a2c322 VM |
272 | /* lra.c: */ |
273 | ||
274 | extern FILE *lra_dump_file; | |
275 | ||
276 | extern bool lra_reg_spill_p; | |
277 | ||
278 | extern HARD_REG_SET lra_no_alloc_regs; | |
279 | ||
280 | extern int lra_insn_recog_data_len; | |
281 | extern lra_insn_recog_data_t *lra_insn_recog_data; | |
282 | ||
283 | extern int lra_curr_reload_num; | |
284 | ||
285 | extern void lra_push_insn (rtx); | |
286 | extern void lra_push_insn_by_uid (unsigned int); | |
287 | extern void lra_push_insn_and_update_insn_regno_info (rtx); | |
288 | extern rtx lra_pop_insn (void); | |
289 | extern unsigned int lra_insn_stack_length (void); | |
290 | ||
291 | extern rtx lra_create_new_reg_with_unique_value (enum machine_mode, rtx, | |
292 | enum reg_class, const char *); | |
293 | extern void lra_set_regno_unique_value (int); | |
294 | extern void lra_invalidate_insn_data (rtx); | |
295 | extern void lra_set_insn_deleted (rtx); | |
296 | extern void lra_delete_dead_insn (rtx); | |
297 | extern void lra_emit_add (rtx, rtx, rtx); | |
298 | extern void lra_emit_move (rtx, rtx); | |
299 | extern void lra_update_dups (lra_insn_recog_data_t, signed char *); | |
300 | ||
301 | extern void lra_process_new_insns (rtx, rtx, rtx, const char *); | |
302 | ||
303 | extern lra_insn_recog_data_t lra_set_insn_recog_data (rtx); | |
304 | extern lra_insn_recog_data_t lra_update_insn_recog_data (rtx); | |
305 | extern void lra_set_used_insn_alternative (rtx, int); | |
306 | extern void lra_set_used_insn_alternative_by_uid (int, int); | |
307 | ||
308 | extern void lra_invalidate_insn_regno_info (rtx); | |
309 | extern void lra_update_insn_regno_info (rtx); | |
310 | extern struct lra_insn_reg *lra_get_insn_regs (int); | |
311 | ||
312 | extern void lra_free_copies (void); | |
313 | extern void lra_create_copy (int, int, int); | |
314 | extern lra_copy_t lra_get_copy (int); | |
315 | extern bool lra_former_scratch_p (int); | |
316 | extern bool lra_former_scratch_operand_p (rtx, int); | |
317 | ||
f681cf95 | 318 | extern int lra_new_regno_start; |
55a2c322 VM |
319 | extern int lra_constraint_new_regno_start; |
320 | extern bitmap_head lra_inheritance_pseudos; | |
321 | extern bitmap_head lra_split_regs; | |
322 | extern bitmap_head lra_optional_reload_pseudos; | |
323 | extern int lra_constraint_new_insn_uid_start; | |
324 | ||
325 | /* lra-constraints.c: */ | |
326 | ||
327 | extern int lra_constraint_offset (int, enum machine_mode); | |
328 | ||
329 | extern int lra_constraint_iter; | |
330 | extern int lra_constraint_iter_after_spill; | |
331 | extern bool lra_risky_transformations_p; | |
332 | extern int lra_inheritance_iter; | |
333 | extern int lra_undo_inheritance_iter; | |
334 | extern bool lra_constraints (bool); | |
335 | extern void lra_constraints_init (void); | |
336 | extern void lra_constraints_finish (void); | |
337 | extern void lra_inheritance (void); | |
338 | extern bool lra_undo_inheritance (void); | |
339 | ||
340 | /* lra-lives.c: */ | |
341 | ||
342 | extern int lra_live_max_point; | |
343 | extern int *lra_point_freq; | |
344 | ||
345 | extern int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER]; | |
346 | ||
347 | extern int lra_live_range_iter; | |
348 | extern void lra_create_live_ranges (bool); | |
349 | extern lra_live_range_t lra_copy_live_range_list (lra_live_range_t); | |
350 | extern lra_live_range_t lra_merge_live_ranges (lra_live_range_t, | |
351 | lra_live_range_t); | |
352 | extern bool lra_intersected_live_ranges_p (lra_live_range_t, | |
353 | lra_live_range_t); | |
354 | extern void lra_print_live_range_list (FILE *, lra_live_range_t); | |
7b3b6ae4 LC |
355 | extern void debug (lra_live_range &ref); |
356 | extern void debug (lra_live_range *ptr); | |
55a2c322 VM |
357 | extern void lra_debug_live_range_list (lra_live_range_t); |
358 | extern void lra_debug_pseudo_live_ranges (int); | |
359 | extern void lra_debug_live_ranges (void); | |
360 | extern void lra_clear_live_ranges (void); | |
361 | extern void lra_live_ranges_init (void); | |
362 | extern void lra_live_ranges_finish (void); | |
363 | extern void lra_setup_reload_pseudo_preferenced_hard_reg (int, int, int); | |
364 | ||
365 | /* lra-assigns.c: */ | |
366 | ||
367 | extern void lra_setup_reg_renumber (int, int, bool); | |
368 | extern bool lra_assign (void); | |
369 | ||
370 | ||
371 | /* lra-coalesce.c: */ | |
372 | ||
373 | extern int lra_coalesce_iter; | |
374 | extern bool lra_coalesce (void); | |
375 | ||
376 | /* lra-spills.c: */ | |
377 | ||
378 | extern bool lra_need_for_spills_p (void); | |
379 | extern void lra_spill (void); | |
c5cd5a7e | 380 | extern void lra_final_code_change (void); |
55a2c322 VM |
381 | |
382 | ||
383 | /* lra-elimination.c: */ | |
384 | ||
385 | extern void lra_debug_elim_table (void); | |
386 | extern int lra_get_elimination_hard_regno (int); | |
387 | extern rtx lra_eliminate_regs_1 (rtx, enum machine_mode, bool, bool, bool); | |
388 | extern void lra_eliminate (bool); | |
389 | ||
390 | extern void lra_eliminate_reg_if_possible (rtx *); | |
391 | ||
392 | \f | |
393 | ||
394 | /* Update insn operands which are duplication of NOP operand. The | |
395 | insn is represented by its LRA internal representation ID. */ | |
396 | static inline void | |
397 | lra_update_dup (lra_insn_recog_data_t id, int nop) | |
398 | { | |
399 | int i; | |
400 | struct lra_static_insn_data *static_id = id->insn_static_data; | |
401 | ||
402 | for (i = 0; i < static_id->n_dups; i++) | |
403 | if (static_id->dup_num[i] == nop) | |
404 | *id->dup_loc[i] = *id->operand_loc[nop]; | |
405 | } | |
406 | ||
407 | /* Process operator duplications in insn with ID. We do it after the | |
408 | operands processing. Generally speaking, we could do this probably | |
409 | simultaneously with operands processing because a common practice | |
410 | is to enumerate the operators after their operands. */ | |
411 | static inline void | |
412 | lra_update_operator_dups (lra_insn_recog_data_t id) | |
413 | { | |
414 | int i; | |
415 | struct lra_static_insn_data *static_id = id->insn_static_data; | |
416 | ||
417 | for (i = 0; i < static_id->n_dups; i++) | |
418 | { | |
419 | int ndup = static_id->dup_num[i]; | |
f4eafc30 | 420 | |
55a2c322 VM |
421 | if (static_id->operand[ndup].is_operator) |
422 | *id->dup_loc[i] = *id->operand_loc[ndup]; | |
423 | } | |
424 | } | |
425 | ||
426 | /* Return info about INSN. Set up the info if it is not done yet. */ | |
427 | static inline lra_insn_recog_data_t | |
428 | lra_get_insn_recog_data (rtx insn) | |
429 | { | |
430 | lra_insn_recog_data_t data; | |
431 | unsigned int uid = INSN_UID (insn); | |
432 | ||
433 | if (lra_insn_recog_data_len > (int) uid | |
434 | && (data = lra_insn_recog_data[uid]) != NULL) | |
435 | { | |
436 | /* Check that we did not change insn without updating the insn | |
437 | info. */ | |
438 | lra_assert (data->insn == insn | |
439 | && (INSN_CODE (insn) < 0 | |
440 | || data->icode == INSN_CODE (insn))); | |
441 | return data; | |
442 | } | |
443 | return lra_set_insn_recog_data (insn); | |
444 | } | |
445 | ||
446 | \f | |
447 | ||
448 | struct target_lra_int | |
449 | { | |
450 | /* Map INSN_UID -> the operand alternative data (NULL if unknown). | |
451 | We assume that this data is valid until register info is changed | |
452 | because classes in the data can be changed. */ | |
453 | struct operand_alternative *x_op_alt_data[LAST_INSN_CODE]; | |
454 | }; | |
455 | ||
456 | extern struct target_lra_int default_target_lra_int; | |
457 | #if SWITCHABLE_TARGET | |
458 | extern struct target_lra_int *this_target_lra_int; | |
459 | #else | |
460 | #define this_target_lra_int (&default_target_lra_int) | |
461 | #endif | |
462 | ||
463 | #define op_alt_data (this_target_lra_int->x_op_alt_data) |