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