OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [ira-int.h] - Blame information for rev 684

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.