]>
Commit | Line | Data |
---|---|---|
47dd2e78 | 1 | /* Integrated Register Allocator (IRA) intercommunication header file. |
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 "cfgloop.h" | |
23 | #include "ira.h" | |
24 | #include "alloc-pool.h" | |
25 | ||
26 | /* To provide consistency in naming, all IRA external variables, | |
27 | functions, common typedefs start with prefix ira_. */ | |
28 | ||
29 | #ifdef ENABLE_CHECKING | |
30 | #define ENABLE_IRA_CHECKING | |
31 | #endif | |
32 | ||
33 | #ifdef ENABLE_IRA_CHECKING | |
34 | #define ira_assert(c) gcc_assert (c) | |
35 | #else | |
7521b07f | 36 | /* Always define and include C, so that warnings for empty body in an |
37 | ‘if’ statement and unused variable do not occur. */ | |
38 | #define ira_assert(c) ((void)(0 && (c))) | |
47dd2e78 | 39 | #endif |
40 | ||
41 | /* Compute register frequency from edge frequency FREQ. It is | |
42 | analogous to REG_FREQ_FROM_BB. When optimizing for size, or | |
43 | profile driven feedback is available and the function is never | |
44 | executed, frequency is always equivalent. Otherwise rescale the | |
45 | edge frequency. */ | |
46 | #define REG_FREQ_FROM_EDGE_FREQ(freq) \ | |
47 | (optimize_size || (flag_branch_probabilities && !ENTRY_BLOCK_PTR->count) \ | |
48 | ? REG_FREQ_MAX : (freq * REG_FREQ_MAX / BB_FREQ_MAX) \ | |
49 | ? (freq * REG_FREQ_MAX / BB_FREQ_MAX) : 1) | |
50 | ||
51 | /* All natural loops. */ | |
52 | extern struct loops ira_loops; | |
53 | ||
54 | /* A modified value of flag `-fira-verbose' used internally. */ | |
55 | extern int internal_flag_ira_verbose; | |
56 | ||
57 | /* Dump file of the allocator if it is not NULL. */ | |
58 | extern FILE *ira_dump_file; | |
59 | ||
60 | /* Typedefs for pointers to allocno live range, allocno, and copy of | |
61 | allocnos. */ | |
fbff82f4 | 62 | typedef struct live_range *live_range_t; |
47dd2e78 | 63 | typedef struct ira_allocno *ira_allocno_t; |
64 | typedef struct ira_allocno_copy *ira_copy_t; | |
ae9587ed | 65 | typedef struct ira_object *ira_object_t; |
47dd2e78 | 66 | |
67 | /* Definition of vector of allocnos and copies. */ | |
68 | DEF_VEC_P(ira_allocno_t); | |
69 | DEF_VEC_ALLOC_P(ira_allocno_t, heap); | |
ae9587ed | 70 | DEF_VEC_P(ira_object_t); |
71 | DEF_VEC_ALLOC_P(ira_object_t, heap); | |
47dd2e78 | 72 | DEF_VEC_P(ira_copy_t); |
73 | DEF_VEC_ALLOC_P(ira_copy_t, heap); | |
74 | ||
75 | /* Typedef for pointer to the subsequent structure. */ | |
76 | typedef struct ira_loop_tree_node *ira_loop_tree_node_t; | |
77 | ||
78 | /* In general case, IRA is a regional allocator. The regions are | |
79 | nested and form a tree. Currently regions are natural loops. The | |
80 | following structure describes loop tree node (representing basic | |
81 | block or loop). We need such tree because the loop tree from | |
82 | cfgloop.h is not convenient for the optimization: basic blocks are | |
83 | not a part of the tree from cfgloop.h. We also use the nodes for | |
84 | storing additional information about basic blocks/loops for the | |
85 | register allocation purposes. */ | |
86 | struct ira_loop_tree_node | |
87 | { | |
88 | /* The node represents basic block if children == NULL. */ | |
89 | basic_block bb; /* NULL for loop. */ | |
90 | struct loop *loop; /* NULL for BB. */ | |
b038c0c4 | 91 | /* NEXT/SUBLOOP_NEXT is the next node/loop-node of the same parent. |
92 | SUBLOOP_NEXT is always NULL for BBs. */ | |
47dd2e78 | 93 | ira_loop_tree_node_t subloop_next, next; |
b038c0c4 | 94 | /* CHILDREN/SUBLOOPS is the first node/loop-node immediately inside |
95 | the node. They are NULL for BBs. */ | |
47dd2e78 | 96 | ira_loop_tree_node_t subloops, children; |
97 | /* The node immediately containing given node. */ | |
98 | ira_loop_tree_node_t parent; | |
99 | ||
100 | /* Loop level in range [0, ira_loop_tree_height). */ | |
101 | int level; | |
102 | ||
103 | /* All the following members are defined only for nodes representing | |
104 | loops. */ | |
105 | ||
ddf888a5 | 106 | /* True if the loop was marked for removal from the register |
107 | allocation. */ | |
108 | bool to_remove_p; | |
109 | ||
47dd2e78 | 110 | /* Allocnos in the loop corresponding to their regnos. If it is |
111 | NULL the loop does not form a separate register allocation region | |
112 | (e.g. because it has abnormal enter/exit edges and we can not put | |
113 | code for register shuffling on the edges if a different | |
114 | allocation is used for a pseudo-register on different sides of | |
115 | the edges). Caps are not in the map (remember we can have more | |
116 | one cap with the same regno in a region). */ | |
117 | ira_allocno_t *regno_allocno_map; | |
118 | ||
0b1329df | 119 | /* True if there is an entry to given loop not from its parent (or |
120 | grandparent) basic block. For example, it is possible for two | |
121 | adjacent loops inside another loop. */ | |
122 | bool entered_from_non_parent_p; | |
123 | ||
47dd2e78 | 124 | /* Maximal register pressure inside loop for given register class |
125 | (defined only for the cover classes). */ | |
126 | int reg_pressure[N_REG_CLASSES]; | |
127 | ||
2bae4acc | 128 | /* Numbers of allocnos referred or living in the loop node (except |
129 | for its subloops). */ | |
130 | bitmap all_allocnos; | |
131 | ||
132 | /* Numbers of allocnos living at the loop borders. */ | |
133 | bitmap border_allocnos; | |
47dd2e78 | 134 | |
135 | /* Regnos of pseudos modified in the loop node (including its | |
136 | subloops). */ | |
137 | bitmap modified_regnos; | |
138 | ||
47dd2e78 | 139 | /* Numbers of copies referred in the corresponding loop. */ |
140 | bitmap local_copies; | |
141 | }; | |
142 | ||
143 | /* The root of the loop tree corresponding to the all function. */ | |
144 | extern ira_loop_tree_node_t ira_loop_tree_root; | |
145 | ||
146 | /* Height of the loop tree. */ | |
147 | extern int ira_loop_tree_height; | |
148 | ||
149 | /* All nodes representing basic blocks are referred through the | |
150 | following array. We can not use basic block member `aux' for this | |
151 | because it is used for insertion of insns on edges. */ | |
152 | extern ira_loop_tree_node_t ira_bb_nodes; | |
153 | ||
154 | /* Two access macros to the nodes representing basic blocks. */ | |
155 | #if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007) | |
156 | #define IRA_BB_NODE_BY_INDEX(index) __extension__ \ | |
157 | (({ ira_loop_tree_node_t _node = (&ira_bb_nodes[index]); \ | |
158 | if (_node->children != NULL || _node->loop != NULL || _node->bb == NULL)\ | |
159 | { \ | |
160 | fprintf (stderr, \ | |
161 | "\n%s: %d: error in %s: it is not a block node\n", \ | |
162 | __FILE__, __LINE__, __FUNCTION__); \ | |
163 | gcc_unreachable (); \ | |
164 | } \ | |
165 | _node; })) | |
166 | #else | |
167 | #define IRA_BB_NODE_BY_INDEX(index) (&ira_bb_nodes[index]) | |
168 | #endif | |
169 | ||
170 | #define IRA_BB_NODE(bb) IRA_BB_NODE_BY_INDEX ((bb)->index) | |
171 | ||
172 | /* All nodes representing loops are referred through the following | |
173 | array. */ | |
174 | extern ira_loop_tree_node_t ira_loop_nodes; | |
175 | ||
176 | /* Two access macros to the nodes representing loops. */ | |
177 | #if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007) | |
178 | #define IRA_LOOP_NODE_BY_INDEX(index) __extension__ \ | |
179 | (({ ira_loop_tree_node_t const _node = (&ira_loop_nodes[index]);\ | |
180 | if (_node->children == NULL || _node->bb != NULL || _node->loop == NULL)\ | |
181 | { \ | |
182 | fprintf (stderr, \ | |
183 | "\n%s: %d: error in %s: it is not a loop node\n", \ | |
184 | __FILE__, __LINE__, __FUNCTION__); \ | |
185 | gcc_unreachable (); \ | |
186 | } \ | |
187 | _node; })) | |
188 | #else | |
189 | #define IRA_LOOP_NODE_BY_INDEX(index) (&ira_loop_nodes[index]) | |
190 | #endif | |
191 | ||
192 | #define IRA_LOOP_NODE(loop) IRA_LOOP_NODE_BY_INDEX ((loop)->num) | |
193 | ||
194 | \f | |
195 | ||
196 | /* The structure describes program points where a given allocno lives. | |
197 | To save memory we store allocno conflicts only for the same cover | |
198 | class allocnos which is enough to assign hard registers. To find | |
199 | conflicts for other allocnos (e.g. to assign stack memory slot) we | |
200 | use the live ranges. If the live ranges of two allocnos are | |
201 | intersected, the allocnos are in conflict. */ | |
fbff82f4 | 202 | struct live_range |
47dd2e78 | 203 | { |
204 | /* Allocno whose live range is described by given structure. */ | |
9d53e372 | 205 | ira_object_t object; |
47dd2e78 | 206 | /* Program point range. */ |
207 | int start, finish; | |
208 | /* Next structure describing program points where the allocno | |
209 | lives. */ | |
fbff82f4 | 210 | live_range_t next; |
47dd2e78 | 211 | /* Pointer to structures with the same start/finish. */ |
fbff82f4 | 212 | live_range_t start_next, finish_next; |
47dd2e78 | 213 | }; |
214 | ||
215 | /* Program points are enumerated by numbers from range | |
216 | 0..IRA_MAX_POINT-1. There are approximately two times more program | |
217 | points than insns. Program points are places in the program where | |
218 | liveness info can be changed. In most general case (there are more | |
219 | complicated cases too) some program points correspond to places | |
220 | where input operand dies and other ones correspond to places where | |
221 | output operands are born. */ | |
222 | extern int ira_max_point; | |
223 | ||
224 | /* Arrays of size IRA_MAX_POINT mapping a program point to the allocno | |
225 | live ranges with given start/finish point. */ | |
fbff82f4 | 226 | extern live_range_t *ira_start_point_ranges, *ira_finish_point_ranges; |
47dd2e78 | 227 | |
ae9587ed | 228 | /* A structure representing conflict information for an allocno |
229 | (or one of its subwords). */ | |
230 | struct ira_object | |
231 | { | |
232 | /* The allocno associated with this record. */ | |
233 | ira_allocno_t allocno; | |
234 | /* Vector of accumulated conflicting conflict_redords with NULL end | |
235 | marker (if OBJECT_CONFLICT_VEC_P is true) or conflict bit vector | |
236 | otherwise. Only objects belonging to allocnos with the | |
237 | same cover class are in the vector or in the bit vector. */ | |
238 | void *conflicts_array; | |
9d53e372 | 239 | /* Pointer to structures describing at what program point the |
240 | object lives. We always maintain the list in such way that *the | |
241 | ranges in the list are not intersected and ordered by decreasing | |
242 | their program points*. */ | |
243 | live_range_t live_ranges; | |
244 | /* Allocated size of the conflicts array. */ | |
ae9587ed | 245 | unsigned int conflicts_array_size; |
246 | /* A unique number for every instance of this structure which is used | |
247 | to represent it in conflict bit vectors. */ | |
248 | int id; | |
249 | /* Before building conflicts, MIN and MAX are initialized to | |
250 | correspondingly minimal and maximal points of the accumulated | |
251 | allocno live ranges. Afterwards, they hold the minimal and | |
252 | maximal ids of other objects that this one can conflict | |
253 | with. */ | |
254 | int min, max; | |
255 | /* Initial and accumulated hard registers conflicting with this | |
256 | conflict record and as a consequences can not be assigned to the | |
257 | allocno. All non-allocatable hard regs and hard regs of cover | |
258 | classes different from given allocno one are included in the | |
259 | sets. */ | |
260 | HARD_REG_SET conflict_hard_regs, total_conflict_hard_regs; | |
261 | /* Number of accumulated conflicts in the vector of conflicting | |
262 | conflict records. */ | |
263 | int num_accumulated_conflicts; | |
264 | /* TRUE if conflicts are represented by a vector of pointers to | |
265 | ira_object structures. Otherwise, we use a bit vector indexed | |
266 | by conflict ID numbers. */ | |
267 | unsigned int conflict_vec_p : 1; | |
268 | }; | |
269 | ||
47dd2e78 | 270 | /* A structure representing an allocno (allocation entity). Allocno |
271 | represents a pseudo-register in an allocation region. If | |
272 | pseudo-register does not live in a region but it lives in the | |
273 | nested regions, it is represented in the region by special allocno | |
274 | called *cap*. There may be more one cap representing the same | |
275 | pseudo-register in region. It means that the corresponding | |
276 | pseudo-register lives in more one non-intersected subregion. */ | |
277 | struct ira_allocno | |
278 | { | |
279 | /* The allocno order number starting with 0. Each allocno has an | |
280 | unique number and the number is never changed for the | |
281 | allocno. */ | |
282 | int num; | |
283 | /* Regno for allocno or cap. */ | |
284 | int regno; | |
285 | /* Mode of the allocno which is the mode of the corresponding | |
286 | pseudo-register. */ | |
287 | enum machine_mode mode; | |
47dd2e78 | 288 | /* Hard register assigned to given allocno. Negative value means |
289 | that memory was allocated to the allocno. During the reload, | |
290 | spilled allocno has value equal to the corresponding stack slot | |
291 | number (0, ...) - 2. Value -1 is used for allocnos spilled by the | |
292 | reload (at this point pseudo-register has only one allocno) which | |
293 | did not get stack slot yet. */ | |
294 | int hard_regno; | |
0ac758f7 | 295 | /* Final rtx representation of the allocno. */ |
296 | rtx reg; | |
47dd2e78 | 297 | /* Allocnos with the same regno are linked by the following member. |
298 | Allocnos corresponding to inner loops are first in the list (it | |
299 | corresponds to depth-first traverse of the loops). */ | |
300 | ira_allocno_t next_regno_allocno; | |
301 | /* There may be different allocnos with the same regno in different | |
302 | regions. Allocnos are bound to the corresponding loop tree node. | |
303 | Pseudo-register may have only one regular allocno with given loop | |
304 | tree node but more than one cap (see comments above). */ | |
305 | ira_loop_tree_node_t loop_tree_node; | |
306 | /* Accumulated usage references of the allocno. Here and below, | |
307 | word 'accumulated' means info for given region and all nested | |
308 | subregions. In this case, 'accumulated' means sum of references | |
309 | of the corresponding pseudo-register in this region and in all | |
310 | nested subregions recursively. */ | |
311 | int nrefs; | |
312 | /* Accumulated frequency of usage of the allocno. */ | |
313 | int freq; | |
314 | /* Register class which should be used for allocation for given | |
315 | allocno. NO_REGS means that we should use memory. */ | |
316 | enum reg_class cover_class; | |
df07a54c | 317 | /* Minimal accumulated and updated costs of usage register of the |
318 | cover class for the allocno. */ | |
319 | int cover_class_cost, updated_cover_class_cost; | |
47dd2e78 | 320 | /* Minimal accumulated, and updated costs of memory for the allocno. |
321 | At the allocation start, the original and updated costs are | |
322 | equal. The updated cost may be changed after finishing | |
323 | allocation in a region and starting allocation in a subregion. | |
324 | The change reflects the cost of spill/restore code on the | |
325 | subregion border if we assign memory to the pseudo in the | |
326 | subregion. */ | |
327 | int memory_cost, updated_memory_cost; | |
328 | /* Accumulated number of points where the allocno lives and there is | |
329 | excess pressure for its class. Excess pressure for a register | |
330 | class at some point means that there are more allocnos of given | |
331 | register class living at the point than number of hard-registers | |
332 | of the class available for the allocation. */ | |
333 | int excess_pressure_points_num; | |
334 | /* Copies to other non-conflicting allocnos. The copies can | |
335 | represent move insn or potential move insn usually because of two | |
336 | operand insn constraints. */ | |
337 | ira_copy_t allocno_copies; | |
338 | /* It is a allocno (cap) representing given allocno on upper loop tree | |
339 | level. */ | |
340 | ira_allocno_t cap; | |
341 | /* It is a link to allocno (cap) on lower loop level represented by | |
342 | given cap. Null if given allocno is not a cap. */ | |
343 | ira_allocno_t cap_member; | |
344 | /* Coalesced allocnos form a cyclic list. One allocno given by | |
345 | FIRST_COALESCED_ALLOCNO represents all coalesced allocnos. The | |
346 | list is chained by NEXT_COALESCED_ALLOCNO. */ | |
347 | ira_allocno_t first_coalesced_allocno; | |
348 | ira_allocno_t next_coalesced_allocno; | |
ae9587ed | 349 | /* Pointer to a structure describing conflict information about this |
350 | allocno. */ | |
351 | ira_object_t object; | |
47dd2e78 | 352 | /* Accumulated frequency of calls which given allocno |
353 | intersects. */ | |
354 | int call_freq; | |
3b95aad3 | 355 | /* Accumulated number of the intersected calls. */ |
47dd2e78 | 356 | int calls_crossed_num; |
47dd2e78 | 357 | /* TRUE if the allocno assigned to memory was a destination of |
358 | removed move (see ira-emit.c) at loop exit because the value of | |
359 | the corresponding pseudo-register is not changed inside the | |
360 | loop. */ | |
361 | unsigned int mem_optimized_dest_p : 1; | |
362 | /* TRUE if the corresponding pseudo-register has disjoint live | |
363 | ranges and the other allocnos of the pseudo-register except this | |
364 | one changed REG. */ | |
365 | unsigned int somewhere_renamed_p : 1; | |
366 | /* TRUE if allocno with the same REGNO in a subregion has been | |
367 | renamed, in other words, got a new pseudo-register. */ | |
368 | unsigned int child_renamed_p : 1; | |
369 | /* During the reload, value TRUE means that we should not reassign a | |
370 | hard register to the allocno got memory earlier. It is set up | |
371 | when we removed memory-memory move insn before each iteration of | |
372 | the reload. */ | |
373 | unsigned int dont_reassign_p : 1; | |
374 | #ifdef STACK_REGS | |
375 | /* Set to TRUE if allocno can't be assigned to the stack hard | |
376 | register correspondingly in this region and area including the | |
377 | region and all its subregions recursively. */ | |
378 | unsigned int no_stack_reg_p : 1, total_no_stack_reg_p : 1; | |
379 | #endif | |
68d4bdfb | 380 | /* TRUE value means that there is no sense to spill the allocno |
381 | during coloring because the spill will result in additional | |
382 | reloads in reload pass. */ | |
383 | unsigned int bad_spill_p : 1; | |
47dd2e78 | 384 | /* TRUE value means that the allocno was not removed yet from the |
385 | conflicting graph during colouring. */ | |
386 | unsigned int in_graph_p : 1; | |
387 | /* TRUE if a hard register or memory has been assigned to the | |
388 | allocno. */ | |
389 | unsigned int assigned_p : 1; | |
390 | /* TRUE if it is put on the stack to make other allocnos | |
391 | colorable. */ | |
392 | unsigned int may_be_spilled_p : 1; | |
393 | /* TRUE if the allocno was removed from the splay tree used to | |
394 | choose allocn for spilling (see ira-color.c::. */ | |
395 | unsigned int splay_removed_p : 1; | |
0ac758f7 | 396 | /* Non NULL if we remove restoring value from given allocno to |
397 | MEM_OPTIMIZED_DEST at loop exit (see ira-emit.c) because the | |
398 | allocno value is not changed inside the loop. */ | |
399 | ira_allocno_t mem_optimized_dest; | |
47dd2e78 | 400 | /* Array of usage costs (accumulated and the one updated during |
401 | coloring) for each hard register of the allocno cover class. The | |
402 | member value can be NULL if all costs are the same and equal to | |
403 | COVER_CLASS_COST. For example, the costs of two different hard | |
404 | registers can be different if one hard register is callee-saved | |
405 | and another one is callee-used and the allocno lives through | |
406 | calls. Another example can be case when for some insn the | |
407 | corresponding pseudo-register value should be put in specific | |
408 | register class (e.g. AREG for x86) which is a strict subset of | |
409 | the allocno cover class (GENERAL_REGS for x86). We have updated | |
410 | costs to reflect the situation when the usage cost of a hard | |
411 | register is decreased because the allocno is connected to another | |
412 | allocno by a copy and the another allocno has been assigned to | |
413 | the hard register. */ | |
414 | int *hard_reg_costs, *updated_hard_reg_costs; | |
415 | /* Array of decreasing costs (accumulated and the one updated during | |
416 | coloring) for allocnos conflicting with given allocno for hard | |
417 | regno of the allocno cover class. The member value can be NULL | |
418 | if all costs are the same. These costs are used to reflect | |
419 | preferences of other allocnos not assigned yet during assigning | |
420 | to given allocno. */ | |
421 | int *conflict_hard_reg_costs, *updated_conflict_hard_reg_costs; | |
951e5184 | 422 | /* Size (in hard registers) of the same cover class allocnos with |
423 | TRUE in_graph_p value and conflicting with given allocno during | |
424 | each point of graph coloring. */ | |
425 | int left_conflicts_size; | |
47dd2e78 | 426 | /* Number of hard registers of the allocno cover class really |
427 | available for the allocno allocation. */ | |
428 | int available_regs_num; | |
429 | /* Allocnos in a bucket (used in coloring) chained by the following | |
430 | two members. */ | |
431 | ira_allocno_t next_bucket_allocno; | |
432 | ira_allocno_t prev_bucket_allocno; | |
433 | /* Used for temporary purposes. */ | |
434 | int temp; | |
435 | }; | |
436 | ||
437 | /* All members of the allocno structures should be accessed only | |
438 | through the following macros. */ | |
439 | #define ALLOCNO_NUM(A) ((A)->num) | |
440 | #define ALLOCNO_REGNO(A) ((A)->regno) | |
441 | #define ALLOCNO_REG(A) ((A)->reg) | |
442 | #define ALLOCNO_NEXT_REGNO_ALLOCNO(A) ((A)->next_regno_allocno) | |
443 | #define ALLOCNO_LOOP_TREE_NODE(A) ((A)->loop_tree_node) | |
444 | #define ALLOCNO_CAP(A) ((A)->cap) | |
445 | #define ALLOCNO_CAP_MEMBER(A) ((A)->cap_member) | |
47dd2e78 | 446 | #define ALLOCNO_NREFS(A) ((A)->nrefs) |
447 | #define ALLOCNO_FREQ(A) ((A)->freq) | |
448 | #define ALLOCNO_HARD_REGNO(A) ((A)->hard_regno) | |
449 | #define ALLOCNO_CALL_FREQ(A) ((A)->call_freq) | |
450 | #define ALLOCNO_CALLS_CROSSED_NUM(A) ((A)->calls_crossed_num) | |
451 | #define ALLOCNO_MEM_OPTIMIZED_DEST(A) ((A)->mem_optimized_dest) | |
452 | #define ALLOCNO_MEM_OPTIMIZED_DEST_P(A) ((A)->mem_optimized_dest_p) | |
453 | #define ALLOCNO_SOMEWHERE_RENAMED_P(A) ((A)->somewhere_renamed_p) | |
454 | #define ALLOCNO_CHILD_RENAMED_P(A) ((A)->child_renamed_p) | |
455 | #define ALLOCNO_DONT_REASSIGN_P(A) ((A)->dont_reassign_p) | |
456 | #ifdef STACK_REGS | |
457 | #define ALLOCNO_NO_STACK_REG_P(A) ((A)->no_stack_reg_p) | |
458 | #define ALLOCNO_TOTAL_NO_STACK_REG_P(A) ((A)->total_no_stack_reg_p) | |
459 | #endif | |
68d4bdfb | 460 | #define ALLOCNO_BAD_SPILL_P(A) ((A)->bad_spill_p) |
47dd2e78 | 461 | #define ALLOCNO_IN_GRAPH_P(A) ((A)->in_graph_p) |
462 | #define ALLOCNO_ASSIGNED_P(A) ((A)->assigned_p) | |
463 | #define ALLOCNO_MAY_BE_SPILLED_P(A) ((A)->may_be_spilled_p) | |
464 | #define ALLOCNO_SPLAY_REMOVED_P(A) ((A)->splay_removed_p) | |
47dd2e78 | 465 | #define ALLOCNO_MODE(A) ((A)->mode) |
466 | #define ALLOCNO_COPIES(A) ((A)->allocno_copies) | |
467 | #define ALLOCNO_HARD_REG_COSTS(A) ((A)->hard_reg_costs) | |
468 | #define ALLOCNO_UPDATED_HARD_REG_COSTS(A) ((A)->updated_hard_reg_costs) | |
469 | #define ALLOCNO_CONFLICT_HARD_REG_COSTS(A) \ | |
470 | ((A)->conflict_hard_reg_costs) | |
471 | #define ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS(A) \ | |
472 | ((A)->updated_conflict_hard_reg_costs) | |
951e5184 | 473 | #define ALLOCNO_LEFT_CONFLICTS_SIZE(A) ((A)->left_conflicts_size) |
47dd2e78 | 474 | #define ALLOCNO_COVER_CLASS(A) ((A)->cover_class) |
475 | #define ALLOCNO_COVER_CLASS_COST(A) ((A)->cover_class_cost) | |
df07a54c | 476 | #define ALLOCNO_UPDATED_COVER_CLASS_COST(A) ((A)->updated_cover_class_cost) |
47dd2e78 | 477 | #define ALLOCNO_MEMORY_COST(A) ((A)->memory_cost) |
478 | #define ALLOCNO_UPDATED_MEMORY_COST(A) ((A)->updated_memory_cost) | |
479 | #define ALLOCNO_EXCESS_PRESSURE_POINTS_NUM(A) ((A)->excess_pressure_points_num) | |
480 | #define ALLOCNO_AVAILABLE_REGS_NUM(A) ((A)->available_regs_num) | |
481 | #define ALLOCNO_NEXT_BUCKET_ALLOCNO(A) ((A)->next_bucket_allocno) | |
482 | #define ALLOCNO_PREV_BUCKET_ALLOCNO(A) ((A)->prev_bucket_allocno) | |
7f36fbdf | 483 | #define ALLOCNO_TEMP(A) ((A)->temp) |
47dd2e78 | 484 | #define ALLOCNO_FIRST_COALESCED_ALLOCNO(A) ((A)->first_coalesced_allocno) |
485 | #define ALLOCNO_NEXT_COALESCED_ALLOCNO(A) ((A)->next_coalesced_allocno) | |
ae9587ed | 486 | #define ALLOCNO_OBJECT(A) ((A)->object) |
487 | ||
488 | #define OBJECT_ALLOCNO(C) ((C)->allocno) | |
489 | #define OBJECT_CONFLICT_ARRAY(C) ((C)->conflicts_array) | |
490 | #define OBJECT_CONFLICT_VEC(C) ((ira_object_t *)(C)->conflicts_array) | |
491 | #define OBJECT_CONFLICT_BITVEC(C) ((IRA_INT_TYPE *)(C)->conflicts_array) | |
492 | #define OBJECT_CONFLICT_ARRAY_SIZE(C) ((C)->conflicts_array_size) | |
493 | #define OBJECT_CONFLICT_VEC_P(C) ((C)->conflict_vec_p) | |
494 | #define OBJECT_NUM_CONFLICTS(C) ((C)->num_accumulated_conflicts) | |
495 | #define OBJECT_CONFLICT_HARD_REGS(C) ((C)->conflict_hard_regs) | |
496 | #define OBJECT_TOTAL_CONFLICT_HARD_REGS(C) ((C)->total_conflict_hard_regs) | |
497 | #define OBJECT_MIN(C) ((C)->min) | |
498 | #define OBJECT_MAX(C) ((C)->max) | |
499 | #define OBJECT_CONFLICT_ID(C) ((C)->id) | |
9d53e372 | 500 | #define OBJECT_LIVE_RANGES(C) ((C)->live_ranges) |
47dd2e78 | 501 | |
48e1416a | 502 | /* Map regno -> allocnos with given regno (see comments for |
47dd2e78 | 503 | allocno member `next_regno_allocno'). */ |
504 | extern ira_allocno_t *ira_regno_allocno_map; | |
505 | ||
506 | /* Array of references to all allocnos. The order number of the | |
507 | allocno corresponds to the index in the array. Removed allocnos | |
508 | have NULL element value. */ | |
509 | extern ira_allocno_t *ira_allocnos; | |
510 | ||
ae9587ed | 511 | /* The size of the previous array. */ |
47dd2e78 | 512 | extern int ira_allocnos_num; |
513 | ||
ae9587ed | 514 | /* Map a conflict id to its corresponding ira_object structure. */ |
515 | extern ira_object_t *ira_object_id_map; | |
516 | ||
517 | /* The size of the previous array. */ | |
518 | extern int ira_objects_num; | |
47dd2e78 | 519 | |
520 | /* The following structure represents a copy of two allocnos. The | |
521 | copies represent move insns or potential move insns usually because | |
522 | of two operand insn constraints. To remove register shuffle, we | |
523 | also create copies between allocno which is output of an insn and | |
524 | allocno becoming dead in the insn. */ | |
525 | struct ira_allocno_copy | |
526 | { | |
527 | /* The unique order number of the copy node starting with 0. */ | |
528 | int num; | |
529 | /* Allocnos connected by the copy. The first allocno should have | |
530 | smaller order number than the second one. */ | |
531 | ira_allocno_t first, second; | |
532 | /* Execution frequency of the copy. */ | |
533 | int freq; | |
b7c06809 | 534 | bool constraint_p; |
47dd2e78 | 535 | /* It is a move insn which is an origin of the copy. The member |
536 | value for the copy representing two operand insn constraints or | |
537 | for the copy created to remove register shuffle is NULL. In last | |
538 | case the copy frequency is smaller than the corresponding insn | |
539 | execution frequency. */ | |
540 | rtx insn; | |
541 | /* All copies with the same allocno as FIRST are linked by the two | |
542 | following members. */ | |
543 | ira_copy_t prev_first_allocno_copy, next_first_allocno_copy; | |
544 | /* All copies with the same allocno as SECOND are linked by the two | |
545 | following members. */ | |
546 | ira_copy_t prev_second_allocno_copy, next_second_allocno_copy; | |
547 | /* Region from which given copy is originated. */ | |
548 | ira_loop_tree_node_t loop_tree_node; | |
549 | }; | |
550 | ||
551 | /* Array of references to all copies. The order number of the copy | |
552 | corresponds to the index in the array. Removed copies have NULL | |
553 | element value. */ | |
554 | extern ira_copy_t *ira_copies; | |
555 | ||
556 | /* Size of the previous array. */ | |
557 | extern int ira_copies_num; | |
558 | ||
559 | /* The following structure describes a stack slot used for spilled | |
560 | pseudo-registers. */ | |
561 | struct ira_spilled_reg_stack_slot | |
562 | { | |
563 | /* pseudo-registers assigned to the stack slot. */ | |
0f71a633 | 564 | bitmap_head spilled_regs; |
47dd2e78 | 565 | /* RTL representation of the stack slot. */ |
566 | rtx mem; | |
567 | /* Size of the stack slot. */ | |
568 | unsigned int width; | |
569 | }; | |
570 | ||
571 | /* The number of elements in the following array. */ | |
572 | extern int ira_spilled_reg_stack_slots_num; | |
573 | ||
574 | /* The following array contains info about spilled pseudo-registers | |
575 | stack slots used in current function so far. */ | |
576 | extern struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots; | |
577 | ||
578 | /* Correspondingly overall cost of the allocation, cost of the | |
579 | allocnos assigned to hard-registers, cost of the allocnos assigned | |
580 | to memory, cost of loads, stores and register move insns generated | |
581 | for pseudo-register live range splitting (see ira-emit.c). */ | |
582 | extern int ira_overall_cost; | |
583 | extern int ira_reg_cost, ira_mem_cost; | |
584 | extern int ira_load_cost, ira_store_cost, ira_shuffle_cost; | |
585 | extern int ira_move_loops_num, ira_additional_jumps_num; | |
01eb3997 | 586 | \f |
587 | /* This page contains a bitset implementation called 'min/max sets' used to | |
588 | record conflicts in IRA. | |
589 | They are named min/maxs set since we keep track of a minimum and a maximum | |
590 | bit number for each set representing the bounds of valid elements. Otherwise, | |
591 | the implementation resembles sbitmaps in that we store an array of integers | |
592 | whose bits directly represent the members of the set. */ | |
593 | ||
594 | /* The type used as elements in the array, and the number of bits in | |
595 | this type. */ | |
47dd2e78 | 596 | #define IRA_INT_BITS HOST_BITS_PER_WIDE_INT |
597 | #define IRA_INT_TYPE HOST_WIDE_INT | |
598 | ||
599 | /* Set, clear or test bit number I in R, a bit vector of elements with | |
600 | minimal index and maximal index equal correspondingly to MIN and | |
601 | MAX. */ | |
602 | #if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007) | |
603 | ||
01eb3997 | 604 | #define SET_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \ |
47dd2e78 | 605 | (({ int _min = (MIN), _max = (MAX), _i = (I); \ |
606 | if (_i < _min || _i > _max) \ | |
607 | { \ | |
608 | fprintf (stderr, \ | |
609 | "\n%s: %d: error in %s: %d not in range [%d,%d]\n", \ | |
610 | __FILE__, __LINE__, __FUNCTION__, _i, _min, _max); \ | |
611 | gcc_unreachable (); \ | |
612 | } \ | |
613 | ((R)[(unsigned) (_i - _min) / IRA_INT_BITS] \ | |
614 | |= ((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); })) | |
48e1416a | 615 | |
47dd2e78 | 616 | |
01eb3997 | 617 | #define CLEAR_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \ |
47dd2e78 | 618 | (({ int _min = (MIN), _max = (MAX), _i = (I); \ |
619 | if (_i < _min || _i > _max) \ | |
620 | { \ | |
621 | fprintf (stderr, \ | |
622 | "\n%s: %d: error in %s: %d not in range [%d,%d]\n", \ | |
623 | __FILE__, __LINE__, __FUNCTION__, _i, _min, _max); \ | |
624 | gcc_unreachable (); \ | |
625 | } \ | |
626 | ((R)[(unsigned) (_i - _min) / IRA_INT_BITS] \ | |
627 | &= ~((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); })) | |
628 | ||
01eb3997 | 629 | #define TEST_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \ |
47dd2e78 | 630 | (({ int _min = (MIN), _max = (MAX), _i = (I); \ |
631 | if (_i < _min || _i > _max) \ | |
632 | { \ | |
633 | fprintf (stderr, \ | |
634 | "\n%s: %d: error in %s: %d not in range [%d,%d]\n", \ | |
635 | __FILE__, __LINE__, __FUNCTION__, _i, _min, _max); \ | |
636 | gcc_unreachable (); \ | |
637 | } \ | |
638 | ((R)[(unsigned) (_i - _min) / IRA_INT_BITS] \ | |
639 | & ((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); })) | |
640 | ||
641 | #else | |
642 | ||
01eb3997 | 643 | #define SET_MINMAX_SET_BIT(R, I, MIN, MAX) \ |
47dd2e78 | 644 | ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS] \ |
645 | |= ((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS))) | |
646 | ||
01eb3997 | 647 | #define CLEAR_MINMAX_SET_BIT(R, I, MIN, MAX) \ |
47dd2e78 | 648 | ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS] \ |
649 | &= ~((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS))) | |
650 | ||
01eb3997 | 651 | #define TEST_MINMAX_SET_BIT(R, I, MIN, MAX) \ |
47dd2e78 | 652 | ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS] \ |
653 | & ((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS))) | |
654 | ||
655 | #endif | |
656 | ||
01eb3997 | 657 | /* The iterator for min/max sets. */ |
47dd2e78 | 658 | typedef struct { |
659 | ||
01eb3997 | 660 | /* Array containing the bit vector. */ |
47dd2e78 | 661 | IRA_INT_TYPE *vec; |
662 | ||
663 | /* The number of the current element in the vector. */ | |
664 | unsigned int word_num; | |
665 | ||
666 | /* The number of bits in the bit vector. */ | |
667 | unsigned int nel; | |
668 | ||
669 | /* The current bit index of the bit vector. */ | |
670 | unsigned int bit_num; | |
671 | ||
672 | /* Index corresponding to the 1st bit of the bit vector. */ | |
673 | int start_val; | |
674 | ||
675 | /* The word of the bit vector currently visited. */ | |
676 | unsigned IRA_INT_TYPE word; | |
01eb3997 | 677 | } minmax_set_iterator; |
47dd2e78 | 678 | |
01eb3997 | 679 | /* Initialize the iterator I for bit vector VEC containing minimal and |
680 | maximal values MIN and MAX. */ | |
47dd2e78 | 681 | static inline void |
01eb3997 | 682 | minmax_set_iter_init (minmax_set_iterator *i, IRA_INT_TYPE *vec, int min, |
683 | int max) | |
47dd2e78 | 684 | { |
685 | i->vec = vec; | |
686 | i->word_num = 0; | |
687 | i->nel = max < min ? 0 : max - min + 1; | |
688 | i->start_val = min; | |
689 | i->bit_num = 0; | |
690 | i->word = i->nel == 0 ? 0 : vec[0]; | |
691 | } | |
692 | ||
01eb3997 | 693 | /* Return TRUE if we have more elements to visit, in which case *N is |
694 | set to the number of the element to be visited. Otherwise, return | |
47dd2e78 | 695 | FALSE. */ |
696 | static inline bool | |
01eb3997 | 697 | minmax_set_iter_cond (minmax_set_iterator *i, int *n) |
47dd2e78 | 698 | { |
699 | /* Skip words that are zeros. */ | |
700 | for (; i->word == 0; i->word = i->vec[i->word_num]) | |
701 | { | |
702 | i->word_num++; | |
703 | i->bit_num = i->word_num * IRA_INT_BITS; | |
48e1416a | 704 | |
47dd2e78 | 705 | /* If we have reached the end, break. */ |
706 | if (i->bit_num >= i->nel) | |
707 | return false; | |
708 | } | |
48e1416a | 709 | |
47dd2e78 | 710 | /* Skip bits that are zero. */ |
711 | for (; (i->word & 1) == 0; i->word >>= 1) | |
712 | i->bit_num++; | |
48e1416a | 713 | |
47dd2e78 | 714 | *n = (int) i->bit_num + i->start_val; |
48e1416a | 715 | |
47dd2e78 | 716 | return true; |
717 | } | |
718 | ||
01eb3997 | 719 | /* Advance to the next element in the set. */ |
47dd2e78 | 720 | static inline void |
01eb3997 | 721 | minmax_set_iter_next (minmax_set_iterator *i) |
47dd2e78 | 722 | { |
723 | i->word >>= 1; | |
724 | i->bit_num++; | |
725 | } | |
726 | ||
01eb3997 | 727 | /* Loop over all elements of a min/max set given by bit vector VEC and |
47dd2e78 | 728 | their minimal and maximal values MIN and MAX. In each iteration, N |
729 | is set to the number of next allocno. ITER is an instance of | |
01eb3997 | 730 | minmax_set_iterator used to iterate over the set. */ |
731 | #define FOR_EACH_BIT_IN_MINMAX_SET(VEC, MIN, MAX, N, ITER) \ | |
732 | for (minmax_set_iter_init (&(ITER), (VEC), (MIN), (MAX)); \ | |
733 | minmax_set_iter_cond (&(ITER), &(N)); \ | |
734 | minmax_set_iter_next (&(ITER))) | |
735 | \f | |
a1e0509e | 736 | struct target_ira_int { |
74b4a59f | 737 | /* Initialized once. It is a maximal possible size of the allocated |
738 | struct costs. */ | |
739 | int x_max_struct_costs_size; | |
740 | ||
741 | /* Allocated and initialized once, and used to initialize cost values | |
742 | for each insn. */ | |
743 | struct costs *x_init_cost; | |
744 | ||
745 | /* Allocated once, and used for temporary purposes. */ | |
746 | struct costs *x_temp_costs; | |
747 | ||
748 | /* Allocated once, and used for the cost calculation. */ | |
749 | struct costs *x_op_costs[MAX_RECOG_OPERANDS]; | |
750 | struct costs *x_this_op_costs[MAX_RECOG_OPERANDS]; | |
751 | ||
752 | /* Classes used for cost calculation. They may be different on | |
753 | different iterations of the cost calculations or in different | |
754 | optimization modes. */ | |
755 | enum reg_class *x_cost_classes; | |
756 | ||
a1e0509e | 757 | /* Hard registers that can not be used for the register allocator for |
758 | all functions of the current compilation unit. */ | |
759 | HARD_REG_SET x_no_unit_alloc_regs; | |
760 | ||
761 | /* Map: hard regs X modes -> set of hard registers for storing value | |
762 | of given mode starting with given hard register. */ | |
763 | HARD_REG_SET (x_ira_reg_mode_hard_regset | |
764 | [FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES]); | |
765 | ||
766 | /* Array based on TARGET_REGISTER_MOVE_COST. Don't use | |
767 | ira_register_move_cost directly. Use function of | |
768 | ira_get_may_move_cost instead. */ | |
769 | move_table *x_ira_register_move_cost[MAX_MACHINE_MODE]; | |
770 | ||
771 | /* Similar to may_move_in_cost but it is calculated in IRA instead of | |
772 | regclass. Another difference we take only available hard registers | |
773 | into account to figure out that one register class is a subset of | |
774 | the another one. Don't use it directly. Use function of | |
775 | ira_get_may_move_cost instead. */ | |
776 | move_table *x_ira_may_move_in_cost[MAX_MACHINE_MODE]; | |
777 | ||
778 | /* Similar to may_move_out_cost but it is calculated in IRA instead of | |
779 | regclass. Another difference we take only available hard registers | |
780 | into account to figure out that one register class is a subset of | |
781 | the another one. Don't use it directly. Use function of | |
782 | ira_get_may_move_cost instead. */ | |
783 | move_table *x_ira_may_move_out_cost[MAX_MACHINE_MODE]; | |
784 | ||
785 | /* Register class subset relation: TRUE if the first class is a subset | |
786 | of the second one considering only hard registers available for the | |
787 | allocation. */ | |
788 | int x_ira_class_subset_p[N_REG_CLASSES][N_REG_CLASSES]; | |
789 | ||
790 | /* Array of the number of hard registers of given class which are | |
791 | available for allocation. The order is defined by the the hard | |
792 | register numbers. */ | |
793 | short x_ira_non_ordered_class_hard_regs[N_REG_CLASSES][FIRST_PSEUDO_REGISTER]; | |
794 | ||
795 | /* Index (in ira_class_hard_regs; for given register class and hard | |
796 | register (in general case a hard register can belong to several | |
797 | register classes;. The index is negative for hard registers | |
798 | unavailable for the allocation. */ | |
799 | short x_ira_class_hard_reg_index[N_REG_CLASSES][FIRST_PSEUDO_REGISTER]; | |
800 | ||
801 | /* Array whose values are hard regset of hard registers available for | |
802 | the allocation of given register class whose HARD_REGNO_MODE_OK | |
803 | values for given mode are zero. */ | |
804 | HARD_REG_SET x_prohibited_class_mode_regs[N_REG_CLASSES][NUM_MACHINE_MODES]; | |
805 | ||
806 | /* The value is number of elements in the subsequent array. */ | |
807 | int x_ira_important_classes_num; | |
808 | ||
809 | /* The array containing non-empty classes (including non-empty cover | |
810 | classes; which are subclasses of cover classes. Such classes is | |
811 | important for calculation of the hard register usage costs. */ | |
812 | enum reg_class x_ira_important_classes[N_REG_CLASSES]; | |
813 | ||
814 | /* The biggest important class inside of intersection of the two | |
815 | classes (that is calculated taking only hard registers available | |
816 | for allocation into account;. If the both classes contain no hard | |
817 | registers available for allocation, the value is calculated with | |
818 | taking all hard-registers including fixed ones into account. */ | |
819 | enum reg_class x_ira_reg_class_intersect[N_REG_CLASSES][N_REG_CLASSES]; | |
820 | ||
821 | /* True if the two classes (that is calculated taking only hard | |
822 | registers available for allocation into account; are | |
823 | intersected. */ | |
824 | bool x_ira_reg_classes_intersect_p[N_REG_CLASSES][N_REG_CLASSES]; | |
825 | ||
826 | /* Classes with end marker LIM_REG_CLASSES which are intersected with | |
827 | given class (the first index;. That includes given class itself. | |
828 | This is calculated taking only hard registers available for | |
829 | allocation into account. */ | |
830 | enum reg_class x_ira_reg_class_super_classes[N_REG_CLASSES][N_REG_CLASSES]; | |
831 | ||
832 | /* The biggest important class inside of union of the two classes | |
833 | (that is calculated taking only hard registers available for | |
834 | allocation into account;. If the both classes contain no hard | |
835 | registers available for allocation, the value is calculated with | |
836 | taking all hard-registers including fixed ones into account. In | |
837 | other words, the value is the corresponding reg_class_subunion | |
838 | value. */ | |
839 | enum reg_class x_ira_reg_class_union[N_REG_CLASSES][N_REG_CLASSES]; | |
840 | ||
841 | /* For each reg class, table listing all the classes contained in it | |
842 | (excluding the class itself. Non-allocatable registers are | |
843 | excluded from the consideration;. */ | |
844 | enum reg_class x_alloc_reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES]; | |
f3c52538 | 845 | |
846 | /* Array whose values are hard regset of hard registers for which | |
847 | move of the hard register in given mode into itself is | |
848 | prohibited. */ | |
849 | HARD_REG_SET x_ira_prohibited_mode_move_regs[NUM_MACHINE_MODES]; | |
850 | ||
851 | /* Flag of that the above array has been initialized. */ | |
852 | bool x_ira_prohibited_mode_move_regs_initialized_p; | |
a1e0509e | 853 | }; |
854 | ||
855 | extern struct target_ira_int default_target_ira_int; | |
856 | #if SWITCHABLE_TARGET | |
857 | extern struct target_ira_int *this_target_ira_int; | |
858 | #else | |
859 | #define this_target_ira_int (&default_target_ira_int) | |
860 | #endif | |
47dd2e78 | 861 | |
a1e0509e | 862 | #define ira_reg_mode_hard_regset \ |
863 | (this_target_ira_int->x_ira_reg_mode_hard_regset) | |
864 | #define ira_register_move_cost \ | |
865 | (this_target_ira_int->x_ira_register_move_cost) | |
866 | #define ira_may_move_in_cost \ | |
867 | (this_target_ira_int->x_ira_may_move_in_cost) | |
868 | #define ira_may_move_out_cost \ | |
869 | (this_target_ira_int->x_ira_may_move_out_cost) | |
870 | #define ira_class_subset_p \ | |
871 | (this_target_ira_int->x_ira_class_subset_p) | |
872 | #define ira_non_ordered_class_hard_regs \ | |
873 | (this_target_ira_int->x_ira_non_ordered_class_hard_regs) | |
874 | #define ira_class_hard_reg_index \ | |
875 | (this_target_ira_int->x_ira_class_hard_reg_index) | |
876 | #define prohibited_class_mode_regs \ | |
877 | (this_target_ira_int->x_prohibited_class_mode_regs) | |
878 | #define ira_important_classes_num \ | |
879 | (this_target_ira_int->x_ira_important_classes_num) | |
880 | #define ira_important_classes \ | |
881 | (this_target_ira_int->x_ira_important_classes) | |
882 | #define ira_reg_class_intersect \ | |
883 | (this_target_ira_int->x_ira_reg_class_intersect) | |
884 | #define ira_reg_classes_intersect_p \ | |
885 | (this_target_ira_int->x_ira_reg_classes_intersect_p) | |
886 | #define ira_reg_class_super_classes \ | |
887 | (this_target_ira_int->x_ira_reg_class_super_classes) | |
888 | #define ira_reg_class_union \ | |
889 | (this_target_ira_int->x_ira_reg_class_union) | |
f3c52538 | 890 | #define ira_prohibited_mode_move_regs \ |
891 | (this_target_ira_int->x_ira_prohibited_mode_move_regs) | |
a1e0509e | 892 | \f |
893 | /* ira.c: */ | |
47dd2e78 | 894 | |
47dd2e78 | 895 | extern void *ira_allocate (size_t); |
896 | extern void *ira_reallocate (void *, size_t); | |
897 | extern void ira_free (void *addr); | |
898 | extern bitmap ira_allocate_bitmap (void); | |
899 | extern void ira_free_bitmap (bitmap); | |
900 | extern void ira_print_disposition (FILE *); | |
901 | extern void ira_debug_disposition (void); | |
902 | extern void ira_debug_class_cover (void); | |
903 | extern void ira_init_register_move_cost (enum machine_mode); | |
904 | ||
905 | /* The length of the two following arrays. */ | |
906 | extern int ira_reg_equiv_len; | |
907 | ||
908 | /* The element value is TRUE if the corresponding regno value is | |
909 | invariant. */ | |
910 | extern bool *ira_reg_equiv_invariant_p; | |
911 | ||
912 | /* The element value is equiv constant of given pseudo-register or | |
913 | NULL_RTX. */ | |
914 | extern rtx *ira_reg_equiv_const; | |
915 | ||
916 | /* ira-build.c */ | |
917 | ||
918 | /* The current loop tree node and its regno allocno map. */ | |
919 | extern ira_loop_tree_node_t ira_curr_loop_tree_node; | |
920 | extern ira_allocno_t *ira_curr_regno_allocno_map; | |
921 | ||
55c858c5 | 922 | extern void ira_debug_copy (ira_copy_t); |
923 | extern void ira_debug_copies (void); | |
47dd2e78 | 924 | extern void ira_debug_allocno_copies (ira_allocno_t); |
925 | ||
926 | extern void ira_traverse_loop_tree (bool, ira_loop_tree_node_t, | |
927 | void (*) (ira_loop_tree_node_t), | |
928 | void (*) (ira_loop_tree_node_t)); | |
c58db480 | 929 | extern ira_allocno_t ira_parent_allocno (ira_allocno_t); |
930 | extern ira_allocno_t ira_parent_or_cap_allocno (ira_allocno_t); | |
47dd2e78 | 931 | extern ira_allocno_t ira_create_allocno (int, bool, ira_loop_tree_node_t); |
ae9587ed | 932 | extern void ira_create_allocno_object (ira_allocno_t); |
47dd2e78 | 933 | extern void ira_set_allocno_cover_class (ira_allocno_t, enum reg_class); |
ae9587ed | 934 | extern bool ira_conflict_vector_profitable_p (ira_object_t, int); |
935 | extern void ira_allocate_conflict_vec (ira_object_t, int); | |
936 | extern void ira_allocate_object_conflicts (ira_object_t, int); | |
47dd2e78 | 937 | extern void ira_print_expanded_allocno (ira_allocno_t); |
9d53e372 | 938 | extern live_range_t ira_create_live_range (ira_object_t, int, int, |
939 | live_range_t); | |
940 | extern live_range_t ira_copy_live_range_list (live_range_t); | |
941 | extern live_range_t ira_merge_live_ranges (live_range_t, live_range_t); | |
942 | extern bool ira_live_ranges_intersect_p (live_range_t, live_range_t); | |
943 | extern void ira_finish_live_range (live_range_t); | |
944 | extern void ira_finish_live_range_list (live_range_t); | |
47dd2e78 | 945 | extern void ira_free_allocno_updated_costs (ira_allocno_t); |
946 | extern ira_copy_t ira_create_copy (ira_allocno_t, ira_allocno_t, | |
b7c06809 | 947 | int, bool, rtx, ira_loop_tree_node_t); |
47dd2e78 | 948 | extern void ira_add_allocno_copy_to_list (ira_copy_t); |
949 | extern void ira_swap_allocno_copy_ends_if_necessary (ira_copy_t); | |
950 | extern void ira_remove_allocno_copy_from_list (ira_copy_t); | |
b7c06809 | 951 | extern ira_copy_t ira_add_allocno_copy (ira_allocno_t, ira_allocno_t, int, |
952 | bool, rtx, ira_loop_tree_node_t); | |
47dd2e78 | 953 | |
954 | extern int *ira_allocate_cost_vector (enum reg_class); | |
955 | extern void ira_free_cost_vector (int *, enum reg_class); | |
956 | ||
957 | extern void ira_flattening (int, int); | |
958 | extern bool ira_build (bool); | |
959 | extern void ira_destroy (void); | |
960 | ||
961 | /* ira-costs.c */ | |
962 | extern void ira_init_costs_once (void); | |
963 | extern void ira_init_costs (void); | |
964 | extern void ira_finish_costs_once (void); | |
965 | extern void ira_costs (void); | |
966 | extern void ira_tune_allocno_costs_and_cover_classes (void); | |
967 | ||
968 | /* ira-lives.c */ | |
969 | ||
970 | extern void ira_rebuild_start_finish_chains (void); | |
fbff82f4 | 971 | extern void ira_print_live_range_list (FILE *, live_range_t); |
972 | extern void ira_debug_live_range_list (live_range_t); | |
47dd2e78 | 973 | extern void ira_debug_allocno_live_ranges (ira_allocno_t); |
974 | extern void ira_debug_live_ranges (void); | |
975 | extern void ira_create_allocno_live_ranges (void); | |
7f36fbdf | 976 | extern void ira_compress_allocno_live_ranges (void); |
47dd2e78 | 977 | extern void ira_finish_allocno_live_ranges (void); |
978 | ||
979 | /* ira-conflicts.c */ | |
47dd2e78 | 980 | extern void ira_debug_conflicts (bool); |
981 | extern void ira_build_conflicts (void); | |
982 | ||
983 | /* ira-color.c */ | |
984 | extern int ira_loop_edge_freq (ira_loop_tree_node_t, int, bool); | |
985 | extern void ira_reassign_conflict_allocnos (int); | |
986 | extern void ira_initiate_assign (void); | |
987 | extern void ira_finish_assign (void); | |
988 | extern void ira_color (void); | |
47dd2e78 | 989 | |
990 | /* ira-emit.c */ | |
991 | extern void ira_emit (bool); | |
992 | ||
993 | \f | |
994 | ||
8f6c49f5 | 995 | /* Return cost of moving value of MODE from register of class FROM to |
996 | register of class TO. */ | |
997 | static inline int | |
998 | ira_get_register_move_cost (enum machine_mode mode, | |
999 | enum reg_class from, enum reg_class to) | |
1000 | { | |
1001 | if (ira_register_move_cost[mode] == NULL) | |
1002 | ira_init_register_move_cost (mode); | |
1003 | return ira_register_move_cost[mode][from][to]; | |
1004 | } | |
1005 | ||
1006 | /* Return cost of moving value of MODE from register of class FROM to | |
1007 | register of class TO. Return zero if IN_P is true and FROM is | |
1008 | subset of TO or if IN_P is false and FROM is superset of TO. */ | |
1009 | static inline int | |
1010 | ira_get_may_move_cost (enum machine_mode mode, | |
1011 | enum reg_class from, enum reg_class to, | |
1012 | bool in_p) | |
1013 | { | |
1014 | if (ira_register_move_cost[mode] == NULL) | |
1015 | ira_init_register_move_cost (mode); | |
1016 | return (in_p | |
1017 | ? ira_may_move_in_cost[mode][from][to] | |
1018 | : ira_may_move_out_cost[mode][from][to]); | |
1019 | } | |
1020 | ||
1021 | \f | |
1022 | ||
47dd2e78 | 1023 | /* The iterator for all allocnos. */ |
1024 | typedef struct { | |
1025 | /* The number of the current element in IRA_ALLOCNOS. */ | |
1026 | int n; | |
1027 | } ira_allocno_iterator; | |
1028 | ||
1029 | /* Initialize the iterator I. */ | |
1030 | static inline void | |
1031 | ira_allocno_iter_init (ira_allocno_iterator *i) | |
1032 | { | |
1033 | i->n = 0; | |
1034 | } | |
1035 | ||
1036 | /* Return TRUE if we have more allocnos to visit, in which case *A is | |
1037 | set to the allocno to be visited. Otherwise, return FALSE. */ | |
1038 | static inline bool | |
1039 | ira_allocno_iter_cond (ira_allocno_iterator *i, ira_allocno_t *a) | |
1040 | { | |
1041 | int n; | |
1042 | ||
1043 | for (n = i->n; n < ira_allocnos_num; n++) | |
1044 | if (ira_allocnos[n] != NULL) | |
1045 | { | |
1046 | *a = ira_allocnos[n]; | |
1047 | i->n = n + 1; | |
1048 | return true; | |
1049 | } | |
1050 | return false; | |
1051 | } | |
1052 | ||
1053 | /* Loop over all allocnos. In each iteration, A is set to the next | |
1054 | allocno. ITER is an instance of ira_allocno_iterator used to iterate | |
1055 | the allocnos. */ | |
1056 | #define FOR_EACH_ALLOCNO(A, ITER) \ | |
1057 | for (ira_allocno_iter_init (&(ITER)); \ | |
1058 | ira_allocno_iter_cond (&(ITER), &(A));) | |
ae9587ed | 1059 | \f |
1060 | /* The iterator for all objects. */ | |
1061 | typedef struct { | |
1062 | /* The number of the current element in IRA_OBJECT_ID_MAP. */ | |
1063 | int n; | |
1064 | } ira_object_iterator; | |
47dd2e78 | 1065 | |
ae9587ed | 1066 | /* Initialize the iterator I. */ |
1067 | static inline void | |
1068 | ira_object_iter_init (ira_object_iterator *i) | |
1069 | { | |
1070 | i->n = 0; | |
1071 | } | |
1072 | ||
1073 | /* Return TRUE if we have more objects to visit, in which case *OBJ is | |
1074 | set to the object to be visited. Otherwise, return FALSE. */ | |
1075 | static inline bool | |
1076 | ira_object_iter_cond (ira_object_iterator *i, ira_object_t *obj) | |
1077 | { | |
1078 | int n; | |
47dd2e78 | 1079 | |
ae9587ed | 1080 | for (n = i->n; n < ira_objects_num; n++) |
1081 | if (ira_object_id_map[n] != NULL) | |
1082 | { | |
1083 | *obj = ira_object_id_map[n]; | |
1084 | i->n = n + 1; | |
1085 | return true; | |
1086 | } | |
1087 | return false; | |
1088 | } | |
1089 | ||
1090 | /* Loop over all objects. In each iteration, A is set to the next | |
1091 | conflict. ITER is an instance of ira_object_iterator used to iterate | |
1092 | the objects. */ | |
1093 | #define FOR_EACH_OBJECT(OBJ, ITER) \ | |
1094 | for (ira_object_iter_init (&(ITER)); \ | |
1095 | ira_object_iter_cond (&(ITER), &(OBJ));) | |
47dd2e78 | 1096 | \f |
1097 | ||
1098 | /* The iterator for copies. */ | |
1099 | typedef struct { | |
1100 | /* The number of the current element in IRA_COPIES. */ | |
1101 | int n; | |
1102 | } ira_copy_iterator; | |
1103 | ||
1104 | /* Initialize the iterator I. */ | |
1105 | static inline void | |
1106 | ira_copy_iter_init (ira_copy_iterator *i) | |
1107 | { | |
1108 | i->n = 0; | |
1109 | } | |
1110 | ||
1111 | /* Return TRUE if we have more copies to visit, in which case *CP is | |
1112 | set to the copy to be visited. Otherwise, return FALSE. */ | |
1113 | static inline bool | |
1114 | ira_copy_iter_cond (ira_copy_iterator *i, ira_copy_t *cp) | |
1115 | { | |
1116 | int n; | |
1117 | ||
1118 | for (n = i->n; n < ira_copies_num; n++) | |
1119 | if (ira_copies[n] != NULL) | |
1120 | { | |
1121 | *cp = ira_copies[n]; | |
1122 | i->n = n + 1; | |
1123 | return true; | |
1124 | } | |
1125 | return false; | |
1126 | } | |
1127 | ||
1128 | /* Loop over all copies. In each iteration, C is set to the next | |
1129 | copy. ITER is an instance of ira_copy_iterator used to iterate | |
1130 | the copies. */ | |
1131 | #define FOR_EACH_COPY(C, ITER) \ | |
1132 | for (ira_copy_iter_init (&(ITER)); \ | |
1133 | ira_copy_iter_cond (&(ITER), &(C));) | |
47dd2e78 | 1134 | \f |
47dd2e78 | 1135 | /* The iterator for allocno conflicts. */ |
1136 | typedef struct { | |
ae9587ed | 1137 | /* TRUE if the conflicts are represented by vector of objects. */ |
1138 | bool conflict_vec_p; | |
47dd2e78 | 1139 | |
1140 | /* The conflict vector or conflict bit vector. */ | |
1141 | void *vec; | |
1142 | ||
1143 | /* The number of the current element in the vector (of type | |
ae9587ed | 1144 | ira_object_t or IRA_INT_TYPE). */ |
47dd2e78 | 1145 | unsigned int word_num; |
1146 | ||
1147 | /* The bit vector size. It is defined only if | |
ae9587ed | 1148 | OBJECT_CONFLICT_VEC_P is FALSE. */ |
47dd2e78 | 1149 | unsigned int size; |
1150 | ||
1151 | /* The current bit index of bit vector. It is defined only if | |
ae9587ed | 1152 | OBJECT_CONFLICT_VEC_P is FALSE. */ |
47dd2e78 | 1153 | unsigned int bit_num; |
1154 | ||
ae9587ed | 1155 | /* The object id corresponding to the 1st bit of the bit vector. It |
1156 | is defined only if OBJECT_CONFLICT_VEC_P is FALSE. */ | |
47dd2e78 | 1157 | int base_conflict_id; |
1158 | ||
1159 | /* The word of bit vector currently visited. It is defined only if | |
ae9587ed | 1160 | OBJECT_CONFLICT_VEC_P is FALSE. */ |
47dd2e78 | 1161 | unsigned IRA_INT_TYPE word; |
e320331a | 1162 | } ira_object_conflict_iterator; |
47dd2e78 | 1163 | |
1164 | /* Initialize the iterator I with ALLOCNO conflicts. */ | |
1165 | static inline void | |
e320331a | 1166 | ira_object_conflict_iter_init (ira_object_conflict_iterator *i, |
1167 | ira_object_t obj) | |
47dd2e78 | 1168 | { |
ae9587ed | 1169 | i->conflict_vec_p = OBJECT_CONFLICT_VEC_P (obj); |
1170 | i->vec = OBJECT_CONFLICT_ARRAY (obj); | |
47dd2e78 | 1171 | i->word_num = 0; |
ae9587ed | 1172 | if (i->conflict_vec_p) |
47dd2e78 | 1173 | i->size = i->bit_num = i->base_conflict_id = i->word = 0; |
1174 | else | |
1175 | { | |
ae9587ed | 1176 | if (OBJECT_MIN (obj) > OBJECT_MAX (obj)) |
47dd2e78 | 1177 | i->size = 0; |
1178 | else | |
ae9587ed | 1179 | i->size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) |
47dd2e78 | 1180 | + IRA_INT_BITS) |
1181 | / IRA_INT_BITS) * sizeof (IRA_INT_TYPE); | |
1182 | i->bit_num = 0; | |
ae9587ed | 1183 | i->base_conflict_id = OBJECT_MIN (obj); |
47dd2e78 | 1184 | i->word = (i->size == 0 ? 0 : ((IRA_INT_TYPE *) i->vec)[0]); |
1185 | } | |
1186 | } | |
1187 | ||
1188 | /* Return TRUE if we have more conflicting allocnos to visit, in which | |
1189 | case *A is set to the allocno to be visited. Otherwise, return | |
1190 | FALSE. */ | |
1191 | static inline bool | |
e320331a | 1192 | ira_object_conflict_iter_cond (ira_object_conflict_iterator *i, |
1193 | ira_object_t *pobj) | |
47dd2e78 | 1194 | { |
ae9587ed | 1195 | ira_object_t obj; |
47dd2e78 | 1196 | |
ae9587ed | 1197 | if (i->conflict_vec_p) |
47dd2e78 | 1198 | { |
ae9587ed | 1199 | obj = ((ira_object_t *) i->vec)[i->word_num]; |
1200 | if (obj == NULL) | |
47dd2e78 | 1201 | return false; |
47dd2e78 | 1202 | } |
1203 | else | |
1204 | { | |
1205 | /* Skip words that are zeros. */ | |
1206 | for (; i->word == 0; i->word = ((IRA_INT_TYPE *) i->vec)[i->word_num]) | |
1207 | { | |
1208 | i->word_num++; | |
48e1416a | 1209 | |
47dd2e78 | 1210 | /* If we have reached the end, break. */ |
1211 | if (i->word_num * sizeof (IRA_INT_TYPE) >= i->size) | |
1212 | return false; | |
48e1416a | 1213 | |
47dd2e78 | 1214 | i->bit_num = i->word_num * IRA_INT_BITS; |
1215 | } | |
48e1416a | 1216 | |
47dd2e78 | 1217 | /* Skip bits that are zero. */ |
1218 | for (; (i->word & 1) == 0; i->word >>= 1) | |
1219 | i->bit_num++; | |
48e1416a | 1220 | |
ae9587ed | 1221 | obj = ira_object_id_map[i->bit_num + i->base_conflict_id]; |
47dd2e78 | 1222 | } |
ae9587ed | 1223 | |
e320331a | 1224 | *pobj = obj; |
ae9587ed | 1225 | return true; |
47dd2e78 | 1226 | } |
1227 | ||
1228 | /* Advance to the next conflicting allocno. */ | |
1229 | static inline void | |
e320331a | 1230 | ira_object_conflict_iter_next (ira_object_conflict_iterator *i) |
47dd2e78 | 1231 | { |
ae9587ed | 1232 | if (i->conflict_vec_p) |
47dd2e78 | 1233 | i->word_num++; |
1234 | else | |
1235 | { | |
1236 | i->word >>= 1; | |
1237 | i->bit_num++; | |
1238 | } | |
1239 | } | |
1240 | ||
e320331a | 1241 | /* Loop over all objects conflicting with OBJ. In each iteration, |
1242 | CONF is set to the next conflicting object. ITER is an instance | |
1243 | of ira_object_conflict_iterator used to iterate the conflicts. */ | |
1244 | #define FOR_EACH_OBJECT_CONFLICT(OBJ, CONF, ITER) \ | |
1245 | for (ira_object_conflict_iter_init (&(ITER), (OBJ)); \ | |
1246 | ira_object_conflict_iter_cond (&(ITER), &(CONF)); \ | |
1247 | ira_object_conflict_iter_next (&(ITER))) | |
47dd2e78 | 1248 | |
1249 | \f | |
1250 | ||
1251 | /* The function returns TRUE if hard registers starting with | |
1252 | HARD_REGNO and containing value of MODE are not in set | |
1253 | HARD_REGSET. */ | |
1254 | static inline bool | |
1255 | ira_hard_reg_not_in_set_p (int hard_regno, enum machine_mode mode, | |
1256 | HARD_REG_SET hard_regset) | |
1257 | { | |
1258 | int i; | |
1259 | ||
1260 | ira_assert (hard_regno >= 0); | |
1261 | for (i = hard_regno_nregs[hard_regno][mode] - 1; i >= 0; i--) | |
1262 | if (TEST_HARD_REG_BIT (hard_regset, hard_regno + i)) | |
1263 | return false; | |
1264 | return true; | |
1265 | } | |
1266 | ||
1267 | \f | |
1268 | ||
1269 | /* To save memory we use a lazy approach for allocation and | |
1270 | initialization of the cost vectors. We do this only when it is | |
1271 | really necessary. */ | |
1272 | ||
1273 | /* Allocate cost vector *VEC for hard registers of COVER_CLASS and | |
1274 | initialize the elements by VAL if it is necessary */ | |
1275 | static inline void | |
1276 | ira_allocate_and_set_costs (int **vec, enum reg_class cover_class, int val) | |
1277 | { | |
1278 | int i, *reg_costs; | |
1279 | int len; | |
1280 | ||
1281 | if (*vec != NULL) | |
1282 | return; | |
1283 | *vec = reg_costs = ira_allocate_cost_vector (cover_class); | |
1284 | len = ira_class_hard_regs_num[cover_class]; | |
1285 | for (i = 0; i < len; i++) | |
1286 | reg_costs[i] = val; | |
1287 | } | |
1288 | ||
1289 | /* Allocate cost vector *VEC for hard registers of COVER_CLASS and | |
1290 | copy values of vector SRC into the vector if it is necessary */ | |
1291 | static inline void | |
1292 | ira_allocate_and_copy_costs (int **vec, enum reg_class cover_class, int *src) | |
1293 | { | |
1294 | int len; | |
1295 | ||
1296 | if (*vec != NULL || src == NULL) | |
1297 | return; | |
1298 | *vec = ira_allocate_cost_vector (cover_class); | |
1299 | len = ira_class_hard_regs_num[cover_class]; | |
1300 | memcpy (*vec, src, sizeof (int) * len); | |
1301 | } | |
1302 | ||
1303 | /* Allocate cost vector *VEC for hard registers of COVER_CLASS and | |
1304 | add values of vector SRC into the vector if it is necessary */ | |
1305 | static inline void | |
1306 | ira_allocate_and_accumulate_costs (int **vec, enum reg_class cover_class, | |
1307 | int *src) | |
1308 | { | |
1309 | int i, len; | |
1310 | ||
1311 | if (src == NULL) | |
1312 | return; | |
1313 | len = ira_class_hard_regs_num[cover_class]; | |
1314 | if (*vec == NULL) | |
1315 | { | |
1316 | *vec = ira_allocate_cost_vector (cover_class); | |
1317 | memset (*vec, 0, sizeof (int) * len); | |
1318 | } | |
1319 | for (i = 0; i < len; i++) | |
1320 | (*vec)[i] += src[i]; | |
1321 | } | |
1322 | ||
1323 | /* Allocate cost vector *VEC for hard registers of COVER_CLASS and | |
1324 | copy values of vector SRC into the vector or initialize it by VAL | |
1325 | (if SRC is null). */ | |
1326 | static inline void | |
1327 | ira_allocate_and_set_or_copy_costs (int **vec, enum reg_class cover_class, | |
1328 | int val, int *src) | |
1329 | { | |
1330 | int i, *reg_costs; | |
1331 | int len; | |
1332 | ||
1333 | if (*vec != NULL) | |
1334 | return; | |
1335 | *vec = reg_costs = ira_allocate_cost_vector (cover_class); | |
1336 | len = ira_class_hard_regs_num[cover_class]; | |
1337 | if (src != NULL) | |
1338 | memcpy (reg_costs, src, sizeof (int) * len); | |
1339 | else | |
1340 | { | |
1341 | for (i = 0; i < len; i++) | |
1342 | reg_costs[i] = val; | |
1343 | } | |
1344 | } |