OSDN Git Service

2008-08-26 Vladimir Makarov <vmakarov@redhat.com>
[pf3gnuchains/gcc-fork.git] / gcc / ira.c
1 /* Integrated Register Allocator (IRA) entry point.
2    Copyright (C) 2006, 2007, 2008
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 /* The integrated register allocator (IRA) is a
23    regional register allocator performing graph coloring on a top-down
24    traversal of nested regions.  Graph coloring in a region is based
25    on Chaitin-Briggs algorithm.  It is called integrated because
26    register coalescing, register live range splitting, and choosing a
27    better hard register are done on-the-fly during coloring.  Register
28    coalescing and choosing a cheaper hard register is done by hard
29    register preferencing during hard register assigning.  The live
30    range splitting is a byproduct of the regional register allocation.
31
32    Major IRA notions are:
33
34      o *Region* is a part of CFG where graph coloring based on
35        Chaitin-Briggs algorithm is done.  IRA can work on any set of
36        nested CFG regions forming a tree.  Currently the regions are
37        the entire function for the root region and natural loops for
38        the other regions.  Therefore data structure representing a
39        region is called loop_tree_node.
40
41      o *Cover class* is a register class belonging to a set of
42        non-intersecting register classes containing all of the
43        hard-registers available for register allocation.  The set of
44        all cover classes for a target is defined in the corresponding
45        machine-description file according some criteria.  Such notion
46        is needed because Chaitin-Briggs algorithm works on
47        non-intersected register classes.
48
49      o *Allocno* represents the live range of a pseudo-register in a
50        region.  Besides the obvious attributes like the corresponding
51        pseudo-register number, cover class, conflicting allocnos and
52        conflicting hard-registers, there are a few allocno attributes
53        which are important for understanding the allocation algorithm:
54
55        - *Live ranges*.  This is a list of ranges of *program
56          points* where the allocno lives.  Program points represent
57          places where a pseudo can be born or become dead (there are
58          approximately two times more program points than the insns)
59          and they are represented by integers starting with 0.  The
60          live ranges are used to find conflicts between allocnos of
61          different cover classes.  They also play very important role
62          for the transformation of the IRA internal representation of
63          several regions into a one region representation.  The later is
64          used during the reload pass work because each allocno
65          represents all of the corresponding pseudo-registers.
66
67        - *Hard-register costs*.  This is a vector of size equal to the
68          number of available hard-registers of the allocno's cover
69          class.  The cost of a callee-clobbered hard-register for an
70          allocno is increased by the cost of save/restore code around
71          the calls through the given allocno's life.  If the allocno
72          is a move instruction operand and another operand is a
73          hard-register of the allocno's cover class, the cost of the
74          hard-register is decreased by the move cost.
75
76          When an allocno is assigned, the hard-register with minimal
77          full cost is used.  Initially, a hard-register's full cost is
78          the corresponding value from the hard-register's cost vector.
79          If the allocno is connected by a *copy* (see below) to
80          another allocno which has just received a hard-register, the
81          cost of the hard-register is decreased.  Before choosing a
82          hard-register for an allocno, the allocno's current costs of
83          the hard-registers are modified by the conflict hard-register
84          costs of all of the conflicting allocnos which are not
85          assigned yet.
86
87        - *Conflict hard-register costs*.  This is a vector of the same
88          size as the hard-register costs vector.  To permit an
89          unassigned allocno to get a better hard-register, IRA uses
90          this vector to calculate the final full cost of the
91          available hard-registers.  Conflict hard-register costs of an
92          unassigned allocno are also changed with a change of the
93          hard-register cost of the allocno when a copy involving the
94          allocno is processed as described above.  This is done to
95          show other unassigned allocnos that a given allocno prefers
96          some hard-registers in order to remove the move instruction
97          corresponding to the copy.
98
99      o *Cap*.  If a pseudo-register does not live in a region but
100        lives in a nested region, IRA creates a special allocno called
101        a cap in the outer region.  A region cap is also created for a
102        subregion cap.
103
104      o *Copy*.  Allocnos can be connected by copies.  Copies are used
105        to modify hard-register costs for allocnos during coloring.
106        Such modifications reflects a preference to use the same
107        hard-register for the allocnos connected by copies.  Usually
108        copies are created for move insns (in this case it results in
109        register coalescing).  But IRA also creates copies for operands
110        of an insn which should be assigned to the same hard-register
111        due to constraints in the machine description (it usually
112        results in removing a move generated in reload to satisfy
113        the constraints) and copies referring to the allocno which is
114        the output operand of an instruction and the allocno which is
115        an input operand dying in the instruction (creation of such
116        copies results in less register shuffling).  IRA *does not*
117        create copies between the same register allocnos from different
118        regions because we use another technique for propagating
119        hard-register preference on the borders of regions.
120
121    Allocnos (including caps) for the upper region in the region tree
122    *accumulate* information important for coloring from allocnos with
123    the same pseudo-register from nested regions.  This includes
124    hard-register and memory costs, conflicts with hard-registers,
125    allocno conflicts, allocno copies and more.  *Thus, attributes for
126    allocnos in a region have the same values as if the region had no
127    subregions*.  It means that attributes for allocnos in the
128    outermost region corresponding to the function have the same values
129    as though the allocation used only one region which is the entire
130    function.  It also means that we can look at IRA work as if the
131    first IRA did allocation for all function then it improved the
132    allocation for loops then their subloops and so on.
133
134    IRA major passes are:
135
136      o Building IRA internal representation which consists of the
137        following subpasses:
138
139        * First, IRA builds regions and creates allocnos (file
140          ira-build.c) and initializes most of their attributes.
141
142        * Then IRA finds a cover class for each allocno and calculates
143          its initial (non-accumulated) cost of memory and each
144          hard-register of its cover class (file ira-cost.c).
145
146        * IRA creates live ranges of each allocno, calulates register
147          pressure for each cover class in each region, sets up
148          conflict hard registers for each allocno and info about calls
149          the allocno lives through (file ira-lives.c).
150
151        * IRA removes low register pressure loops from the regions
152          mostly to speed IRA up (file ira-build.c).
153
154        * IRA propagates accumulated allocno info from lower region
155          allocnos to corresponding upper region allocnos (file
156          ira-build.c).
157
158        * IRA creates all caps (file ira-build.c).
159
160        * Having live-ranges of allocnos and their cover classes, IRA
161          creates conflicting allocnos of the same cover class for each
162          allocno.  Conflicting allocnos are stored as a bit vector or
163          array of pointers to the conflicting allocnos whatever is
164          more profitable (file ira-conflicts.c).  At this point IRA
165          creates allocno copies.
166
167      o Coloring.  Now IRA has all necessary info to start graph coloring
168        process.  It is done in each region on top-down traverse of the
169        region tree (file ira-color.c).  There are following subpasses:
170         
171        * Optional aggressive coalescing of allocnos in the region.
172
173        * Putting allocnos onto the coloring stack.  IRA uses Briggs
174          optimistic coloring which is a major improvement over
175          Chaitin's coloring.  Therefore IRA does not spill allocnos at
176          this point.  There is some freedom in the order of putting
177          allocnos on the stack which can affect the final result of
178          the allocation.  IRA uses some heuristics to improve the order.
179
180        * Popping the allocnos from the stack and assigning them hard
181          registers.  If IRA can not assign a hard register to an
182          allocno and the allocno is coalesced, IRA undoes the
183          coalescing and puts the uncoalesced allocnos onto the stack in
184          the hope that some such allocnos will get a hard register
185          separately.  If IRA fails to assign hard register or memory
186          is more profitable for it, IRA spills the allocno.  IRA
187          assigns the allocno the hard-register with minimal full
188          allocation cost which reflects the cost of usage of the
189          hard-register for the allocno and cost of usage of the
190          hard-register for allocnos conflicting with given allocno.
191
192        * After allono assigning in the region, IRA modifies the hard
193          register and memory costs for the corresponding allocnos in
194          the subregions to reflect the cost of possible loads, stores,
195          or moves on the border of the region and its subregions.
196          When default regional allocation algorithm is used
197          (-fira-algorithm=mixed), IRA just propagates the assignment
198          for allocnos if the register pressure in the region for the
199          corresponding cover class is less than number of available
200          hard registers for given cover class.
201
202      o Spill/restore code moving.  When IRA performs an allocation
203        by traversing regions in top-down order, it does not know what
204        happens below in the region tree.  Therefore, sometimes IRA
205        misses opportunities to perform a better allocation.  A simple
206        optimization tries to improve allocation in a region having
207        subregions and containing in another region.  If the
208        corresponding allocnos in the subregion are spilled, it spills
209        the region allocno if it is profitable.  The optimization
210        implements a simple iterative algorithm performing profitable
211        transformations while they are still possible.  It is fast in
212        practice, so there is no real need for a better time complexity
213        algorithm.
214
215      o Code change.  After coloring, two allocnos representing the same
216        pseudo-register outside and inside a region respectively may be
217        assigned to different locations (hard-registers or memory).  In
218        this case IRA creates and uses a new pseudo-register inside the
219        region and adds code to move allocno values on the region's
220        borders.  This is done during top-down traversal of the regions
221        (file ira-emit.c).  In some complicated cases IRA can create a
222        new allocno to move allocno values (e.g. when a swap of values
223        stored in two hard-registers is needed).  At this stage, the
224        new allocno is marked as spilled.  IRA still creates the
225        pseudo-register and the moves on the region borders even when
226        both allocnos were assigned to the same hard-register.  If the
227        reload pass spills a pseudo-register for some reason, the
228        effect will be smaller because another allocno will still be in
229        the hard-register.  In most cases, this is better then spilling
230        both allocnos.  If reload does not change the allocation
231        for the two pseudo-registers, the trivial move will be removed
232        by post-reload optimizations.  IRA does not generate moves for
233        allocnos assigned to the same hard register when the default
234        regional allocation algorithm is used and the register pressure
235        in the region for the corresponding allocno cover class is less
236        than number of available hard registers for given cover class.
237        IRA also does some optimizations to remove redundant stores and
238        to reduce code duplication on the region borders.
239
240      o Flattening internal representation.  After changing code, IRA
241        transforms its internal representation for several regions into
242        one region representation (file ira-build.c).  This process is
243        called IR flattening.  Such process is more complicated than IR
244        rebuilding would be, but is much faster.
245
246      o After IR flattening, IRA tries to assign hard registers to all
247        spilled allocnos.  This is impelemented by a simple and fast
248        priority coloring algorithm (see function
249        ira_reassign_conflict_allocnos::ira-color.c).  Here new allocnos
250        created during the code change pass can be assigned to hard
251        registers.
252
253      o At the end IRA calls the reload pass.  The reload pass
254        communicates with IRA through several functions in file
255        ira-color.c to improve its decisions in
256
257        * sharing stack slots for the spilled pseudos based on IRA info
258          about pseudo-register conflicts.
259
260        * reassigning hard-registers to all spilled pseudos at the end
261          of each reload iteration.
262
263        * choosing a better hard-register to spill based on IRA info
264          about pseudo-register live ranges and the register pressure
265          in places where the pseudo-register lives.
266
267    IRA uses a lot of data representing the target processors.  These
268    data are initilized in file ira.c.
269
270    If function has no loops (or the loops are ignored when
271    -fira-algorithm=CB is used), we have classic Chaitin-Briggs
272    coloring (only instead of separate pass of coalescing, we use hard
273    register preferencing).  In such case, IRA works much faster
274    because many things are not made (like IR flattening, the
275    spill/restore optimization, and the code change).
276
277    Literature is worth to read for better understanding the code:
278
279    o Preston Briggs, Keith D. Cooper, Linda Torczon.  Improvements to
280      Graph Coloring Register Allocation.
281
282    o David Callahan, Brian Koblenz.  Register allocation via
283      hierarchical graph coloring.
284
285    o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
286      Coloring Register Allocation: A Study of the Chaitin-Briggs and
287      Callahan-Koblenz Algorithms.
288
289    o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
290      Register Allocation Based on Graph Fusion.
291
292    o Vladimir Makarov. The Integrated Register Allocator for GCC.
293
294    o Vladimir Makarov.  The top-down register allocator for irregular
295      register file architectures.
296
297 */
298
299
300 #include "config.h"
301 #include "system.h"
302 #include "coretypes.h"
303 #include "tm.h"
304 #include "regs.h"
305 #include "rtl.h"
306 #include "tm_p.h"
307 #include "target.h"
308 #include "flags.h"
309 #include "obstack.h"
310 #include "bitmap.h"
311 #include "hard-reg-set.h"
312 #include "basic-block.h"
313 #include "expr.h"
314 #include "recog.h"
315 #include "params.h"
316 #include "timevar.h"
317 #include "tree-pass.h"
318 #include "output.h"
319 #include "reload.h"
320 #include "errors.h"
321 #include "integrate.h"
322 #include "df.h"
323 #include "ggc.h"
324 #include "ira-int.h"
325
326
327 /* A modified value of flag `-fira-verbose' used internally.  */
328 int internal_flag_ira_verbose;
329
330 /* Dump file of the allocator if it is not NULL.  */
331 FILE *ira_dump_file;
332
333 /* Pools for allocnos, copies, allocno live ranges.  */
334 alloc_pool allocno_pool, copy_pool, allocno_live_range_pool;
335
336 /* The number of elements in the following array.  */
337 int ira_spilled_reg_stack_slots_num;
338
339 /* The following array contains info about spilled pseudo-registers
340    stack slots used in current function so far.  */
341 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
342
343 /* Correspondingly overall cost of the allocation, cost of the
344    allocnos assigned to hard-registers, cost of the allocnos assigned
345    to memory, cost of loads, stores and register move insns generated
346    for pseudo-register live range splitting (see ira-emit.c).  */
347 int ira_overall_cost;
348 int ira_reg_cost, ira_mem_cost;
349 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
350 int ira_move_loops_num, ira_additional_jumps_num;
351
352 /* Map: hard regs X modes -> set of hard registers for storing value
353    of given mode starting with given hard register.  */
354 HARD_REG_SET ira_reg_mode_hard_regset[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
355
356 /* The following two variables are array analogs of the macros
357    MEMORY_MOVE_COST and REGISTER_MOVE_COST.  */
358 short int ira_memory_move_cost[MAX_MACHINE_MODE][N_REG_CLASSES][2];
359 move_table *ira_register_move_cost[MAX_MACHINE_MODE];
360
361 /* Similar to may_move_in_cost but it is calculated in IRA instead of
362    regclass.  Another difference is that we take only available hard
363    registers into account to figure out that one register class is a
364    subset of the another one.  */
365 move_table *ira_may_move_in_cost[MAX_MACHINE_MODE];
366
367 /* Similar to may_move_out_cost but it is calculated in IRA instead of
368    regclass.  Another difference is that we take only available hard
369    registers into account to figure out that one register class is a
370    subset of the another one.  */
371 move_table *ira_may_move_out_cost[MAX_MACHINE_MODE];
372
373 /* Register class subset relation: TRUE if the first class is a subset
374    of the second one considering only hard registers available for the
375    allocation.  */
376 int ira_class_subset_p[N_REG_CLASSES][N_REG_CLASSES];
377
378 /* Temporary hard reg set used for a different calculation.  */
379 static HARD_REG_SET temp_hard_regset;
380
381 \f
382
383 /* The function sets up the map IRA_REG_MODE_HARD_REGSET.  */
384 static void
385 setup_reg_mode_hard_regset (void)
386 {
387   int i, m, hard_regno;
388
389   for (m = 0; m < NUM_MACHINE_MODES; m++)
390     for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
391       {
392         CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
393         for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
394           if (hard_regno + i < FIRST_PSEUDO_REGISTER)
395             SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
396                               hard_regno + i);
397       }
398 }
399
400 \f
401
402 /* Hard registers that can not be used for the register allocator for
403    all functions of the current compilation unit.  */
404 static HARD_REG_SET no_unit_alloc_regs;
405
406 /* Array of the number of hard registers of given class which are
407    available for allocation.  The order is defined by the
408    allocation order.  */
409 short ira_class_hard_regs[N_REG_CLASSES][FIRST_PSEUDO_REGISTER];
410
411 /* The number of elements of the above array for given register
412    class.  */
413 int ira_class_hard_regs_num[N_REG_CLASSES];
414
415 /* Index (in ira_class_hard_regs) for given register class and hard
416    register (in general case a hard register can belong to several
417    register classes).  The index is negative for hard registers
418    unavailable for the allocation. */
419 short ira_class_hard_reg_index[N_REG_CLASSES][FIRST_PSEUDO_REGISTER];
420
421 /* The function sets up the three arrays declared above.  */
422 static void
423 setup_class_hard_regs (void)
424 {
425   int cl, i, hard_regno, n;
426   HARD_REG_SET processed_hard_reg_set;
427
428   ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
429   /* We could call ORDER_REGS_FOR_LOCAL_ALLOC here (it is usually
430      putting hard callee-used hard registers first).  But our
431      heuristics work better.  */
432   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
433     {
434       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
435       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
436       CLEAR_HARD_REG_SET (processed_hard_reg_set);
437       for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
438         {
439 #ifdef REG_ALLOC_ORDER
440           hard_regno = reg_alloc_order[i];
441 #else
442           hard_regno = i;
443 #endif    
444           if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
445             continue;
446           SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
447           if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
448             ira_class_hard_reg_index[cl][hard_regno] = -1;
449           else
450             {
451               ira_class_hard_reg_index[cl][hard_regno] = n;
452               ira_class_hard_regs[cl][n++] = hard_regno;
453             }
454         }
455       ira_class_hard_regs_num[cl] = n;
456     }
457 }
458
459 /* Number of given class hard registers available for the register
460    allocation for given classes.  */
461 int ira_available_class_regs[N_REG_CLASSES];
462
463 /* Set up IRA_AVAILABLE_CLASS_REGS.  */
464 static void
465 setup_available_class_regs (void)
466 {
467   int i, j;
468
469   memset (ira_available_class_regs, 0, sizeof (ira_available_class_regs));
470   for (i = 0; i < N_REG_CLASSES; i++)
471     {
472       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
473       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
474       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
475         if (TEST_HARD_REG_BIT (temp_hard_regset, j))
476           ira_available_class_regs[i]++;
477     }
478 }
479
480 /* Set up global variables defining info about hard registers for the
481    allocation.  These depend on USE_HARD_FRAME_P whose TRUE value means
482    that we can use the hard frame pointer for the allocation.  */
483 static void
484 setup_alloc_regs (bool use_hard_frame_p)
485 {
486   COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
487   if (! use_hard_frame_p)
488     SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
489   setup_class_hard_regs ();
490   setup_available_class_regs ();
491 }
492
493 \f
494
495 /* Set up IRA_MEMORY_MOVE_COST, IRA_REGISTER_MOVE_COST.  */
496 static void
497 setup_class_subset_and_memory_move_costs (void)
498 {
499   int cl, cl2;
500   enum machine_mode mode;
501   HARD_REG_SET temp_hard_regset2;
502
503   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
504     ira_memory_move_cost[mode][NO_REGS][0]
505       = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
506   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
507     {
508       if (cl != (int) NO_REGS)
509         for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
510           {
511             ira_memory_move_cost[mode][cl][0] = MEMORY_MOVE_COST (mode, cl, 0);
512             ira_memory_move_cost[mode][cl][1] = MEMORY_MOVE_COST (mode, cl, 1);
513             /* Costs for NO_REGS are used in cost calculation on the
514                1st pass when the preferred register classes are not
515                known yet.  In this case we take the best scenario.  */
516             if (ira_memory_move_cost[mode][NO_REGS][0]
517                 > ira_memory_move_cost[mode][cl][0])
518               ira_memory_move_cost[mode][NO_REGS][0]
519                 = ira_memory_move_cost[mode][cl][0];
520             if (ira_memory_move_cost[mode][NO_REGS][1]
521                 > ira_memory_move_cost[mode][cl][1])
522               ira_memory_move_cost[mode][NO_REGS][1]
523                 = ira_memory_move_cost[mode][cl][1];
524           }
525       for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
526         {
527           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
528           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
529           COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
530           AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
531           ira_class_subset_p[cl][cl2]
532             = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
533         }
534     }
535 }
536
537 \f
538
539 /* Define the following macro if allocation through malloc if
540    preferable.  */
541 #define IRA_NO_OBSTACK
542
543 #ifndef IRA_NO_OBSTACK
544 /* Obstack used for storing all dynamic data (except bitmaps) of the
545    IRA.  */
546 static struct obstack ira_obstack;
547 #endif
548
549 /* Obstack used for storing all bitmaps of the IRA.  */
550 static struct bitmap_obstack ira_bitmap_obstack;
551
552 /* Allocate memory of size LEN for IRA data.  */
553 void *
554 ira_allocate (size_t len)
555 {
556   void *res;
557
558 #ifndef IRA_NO_OBSTACK
559   res = obstack_alloc (&ira_obstack, len);
560 #else
561   res = xmalloc (len);
562 #endif
563   return res;
564 }
565
566 /* Reallocate memory PTR of size LEN for IRA data.  */
567 void *
568 ira_reallocate (void *ptr, size_t len)
569 {
570   void *res;
571
572 #ifndef IRA_NO_OBSTACK
573   res = obstack_alloc (&ira_obstack, len);
574 #else
575   res = xrealloc (ptr, len);
576 #endif
577   return res;
578 }
579
580 /* Free memory ADDR allocated for IRA data.  */
581 void
582 ira_free (void *addr ATTRIBUTE_UNUSED)
583 {
584 #ifndef IRA_NO_OBSTACK
585   /* do nothing */
586 #else
587   free (addr);
588 #endif
589 }
590
591
592 /* Allocate and returns bitmap for IRA.  */
593 bitmap
594 ira_allocate_bitmap (void)
595 {
596   return BITMAP_ALLOC (&ira_bitmap_obstack);
597 }
598
599 /* Free bitmap B allocated for IRA.  */
600 void
601 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
602 {
603   /* do nothing */
604 }
605
606 \f
607
608 /* Output information about allocation of all allocnos (except for
609    caps) into file F.  */
610 void
611 ira_print_disposition (FILE *f)
612 {
613   int i, n, max_regno;
614   ira_allocno_t a;
615   basic_block bb;
616
617   fprintf (f, "Disposition:");
618   max_regno = max_reg_num ();
619   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
620     for (a = ira_regno_allocno_map[i];
621          a != NULL;
622          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
623       {
624         if (n % 4 == 0)
625           fprintf (f, "\n");
626         n++;
627         fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
628         if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
629           fprintf (f, "b%-3d", bb->index);
630         else
631           fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
632         if (ALLOCNO_HARD_REGNO (a) >= 0)
633           fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
634         else
635           fprintf (f, " mem");
636       }
637   fprintf (f, "\n");
638 }
639
640 /* Outputs information about allocation of all allocnos into
641    stderr.  */
642 void
643 ira_debug_disposition (void)
644 {
645   ira_print_disposition (stderr);
646 }
647
648 \f
649
650 /* For each reg class, table listing all the classes contained in it
651    (excluding the class itself.  Non-allocatable registers are
652    excluded from the consideration).  */
653 static enum reg_class alloc_reg_class_subclasses[N_REG_CLASSES][N_REG_CLASSES];
654
655 /* Initialize the table of subclasses of each reg class.  */
656 static void
657 setup_reg_subclasses (void)
658 {
659   int i, j;
660   HARD_REG_SET temp_hard_regset2;
661
662   for (i = 0; i < N_REG_CLASSES; i++)
663     for (j = 0; j < N_REG_CLASSES; j++)
664       alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
665
666   for (i = 0; i < N_REG_CLASSES; i++)
667     {
668       if (i == (int) NO_REGS)
669         continue;
670
671       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
672       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
673       if (hard_reg_set_equal_p (temp_hard_regset, ira_zero_hard_reg_set))
674         continue;
675       for (j = 0; j < N_REG_CLASSES; j++)
676         if (i != j)
677           {
678             enum reg_class *p;
679
680             COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
681             AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
682             if (! hard_reg_set_subset_p (temp_hard_regset,
683                                          temp_hard_regset2))
684               continue;
685             p = &alloc_reg_class_subclasses[j][0];
686             while (*p != LIM_REG_CLASSES) p++;
687             *p = (enum reg_class) i;
688           }
689     }
690 }
691
692 \f
693
694 /* Number of cover classes.  Cover classes is non-intersected register
695    classes containing all hard-registers available for the
696    allocation.  */
697 int ira_reg_class_cover_size;
698
699 /* The array containing cover classes (see also comments for macro
700    IRA_COVER_CLASSES).  Only first IRA_REG_CLASS_COVER_SIZE elements are
701    used for this.  */
702 enum reg_class ira_reg_class_cover[N_REG_CLASSES];
703
704 /* The number of elements in the subsequent array.  */
705 int ira_important_classes_num;
706
707 /* The array containing non-empty classes (including non-empty cover
708    classes) which are subclasses of cover classes.  Such classes is
709    important for calculation of the hard register usage costs.  */
710 enum reg_class ira_important_classes[N_REG_CLASSES];
711
712 /* The array containing indexes of important classes in the previous
713    array.  The array elements are defined only for important
714    classes.  */
715 int ira_important_class_nums[N_REG_CLASSES];
716
717 #ifdef IRA_COVER_CLASSES
718
719 /* Check IRA_COVER_CLASSES and sets the four global variables defined
720    above.  */
721 static void
722 setup_cover_and_important_classes (void)
723 {
724   int i, j;
725   enum reg_class cl;
726   static enum reg_class classes[] = IRA_COVER_CLASSES;
727   HARD_REG_SET temp_hard_regset2;
728
729   ira_reg_class_cover_size = 0;
730   for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
731     {
732       for (j = 0; j < i; j++)
733         if (reg_classes_intersect_p (cl, classes[j]))
734           gcc_unreachable ();
735       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
736       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
737       if (! hard_reg_set_equal_p (temp_hard_regset, ira_zero_hard_reg_set))
738         ira_reg_class_cover[ira_reg_class_cover_size++] = cl;
739     }
740   ira_important_classes_num = 0;
741   for (cl = 0; cl < N_REG_CLASSES; cl++)
742     {
743       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
744       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
745       if (! hard_reg_set_equal_p (temp_hard_regset, ira_zero_hard_reg_set))
746         for (j = 0; j < ira_reg_class_cover_size; j++)
747           {
748             COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
749             AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
750             COPY_HARD_REG_SET (temp_hard_regset2,
751                                reg_class_contents[ira_reg_class_cover[j]]);
752             AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
753             if (cl == ira_reg_class_cover[j]
754                 || (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
755                     && ! hard_reg_set_equal_p (temp_hard_regset,
756                                                temp_hard_regset2)))
757               {
758                 ira_important_class_nums[cl] = ira_important_classes_num;
759                 ira_important_classes[ira_important_classes_num++] = cl;
760               }
761           }
762     }
763 }
764 #endif
765
766 /* Map of all register classes to corresponding cover class containing
767    the given class.  If given class is not a subset of a cover class,
768    we translate it into the cheapest cover class.  */
769 enum reg_class ira_class_translate[N_REG_CLASSES];
770
771 #ifdef IRA_COVER_CLASSES
772
773 /* Set up array IRA_CLASS_TRANSLATE.  */
774 static void
775 setup_class_translate (void)
776 {
777   enum reg_class cl, cover_class, best_class, *cl_ptr;
778   enum machine_mode mode;
779   int i, cost, min_cost, best_cost;
780
781   for (cl = 0; cl < N_REG_CLASSES; cl++)
782     ira_class_translate[cl] = NO_REGS;
783   for (i = 0; i < ira_reg_class_cover_size; i++)
784     {
785       cover_class = ira_reg_class_cover[i];
786       for (cl_ptr = &alloc_reg_class_subclasses[cover_class][0];
787            (cl = *cl_ptr) != LIM_REG_CLASSES;
788            cl_ptr++)
789         {
790           if (ira_class_translate[cl] == NO_REGS)
791             ira_class_translate[cl] = cover_class;
792 #ifdef ENABLE_IRA_CHECKING
793           else
794             {
795               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
796               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
797               if (! hard_reg_set_subset_p (temp_hard_regset,
798                                            ira_zero_hard_reg_set))
799                 gcc_unreachable ();
800             }
801 #endif
802         }
803       ira_class_translate[cover_class] = cover_class;
804     }
805   /* For classes which are not fully covered by a cover class (in
806      other words covered by more one cover class), use the cheapest
807      cover class.  */
808   for (cl = 0; cl < N_REG_CLASSES; cl++)
809     {
810       if (cl == NO_REGS || ira_class_translate[cl] != NO_REGS)
811         continue;
812       best_class = NO_REGS;
813       best_cost = INT_MAX;
814       for (i = 0; i < ira_reg_class_cover_size; i++)
815         {
816           cover_class = ira_reg_class_cover[i];
817           COPY_HARD_REG_SET (temp_hard_regset,
818                              reg_class_contents[cover_class]);
819           AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
820           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
821           if (! hard_reg_set_equal_p (temp_hard_regset, ira_zero_hard_reg_set))
822             {
823               min_cost = INT_MAX;
824               for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
825                 {
826                   cost = (ira_memory_move_cost[mode][cl][0]
827                           + ira_memory_move_cost[mode][cl][1]);
828                   if (min_cost > cost)
829                     min_cost = cost;
830                 }
831               if (best_class == NO_REGS || best_cost > min_cost)
832                 {
833                   best_class = cover_class;
834                   best_cost = min_cost;
835                 }
836             }
837         }
838       ira_class_translate[cl] = best_class;
839     }
840 }
841 #endif
842
843 /* The biggest important reg_class inside of intersection of the two
844    reg_classes (that is calculated taking only hard registers
845    available for allocation into account).  If the both reg_classes
846    contain no hard registers available for allocation, the value is
847    calculated by taking all hard-registers including fixed ones into
848    account.  */
849 enum reg_class ira_reg_class_intersect[N_REG_CLASSES][N_REG_CLASSES];
850
851 /* The biggest important reg_class inside of union of the two
852    reg_classes (that is calculated taking only hard registers
853    available for allocation into account).  If the both reg_classes
854    contain no hard registers available for allocation, the value is
855    calculated by taking all hard-registers including fixed ones into
856    account.  In other words, the value is the corresponding
857    reg_class_subunion value.  */
858 enum reg_class ira_reg_class_union[N_REG_CLASSES][N_REG_CLASSES];
859
860 #ifdef IRA_COVER_CLASSES
861
862 /* Set up IRA_REG_CLASS_INTERSECT and IRA_REG_CLASS_UNION.  */
863 static void
864 setup_reg_class_intersect_union (void)
865 {
866   int i, cl1, cl2, cl3;
867   HARD_REG_SET intersection_set, union_set, temp_set2;
868
869   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
870     {
871       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
872         {
873           ira_reg_class_intersect[cl1][cl2] = NO_REGS;
874           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
875           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
876           COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
877           AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
878           if (hard_reg_set_equal_p (temp_hard_regset, ira_zero_hard_reg_set)
879               && hard_reg_set_equal_p (temp_set2, ira_zero_hard_reg_set))
880             {
881               for (i = 0;; i++)
882                 {
883                   cl3 = reg_class_subclasses[cl1][i];
884                   if (cl3 == LIM_REG_CLASSES)
885                     break;
886                   if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
887                                           cl3))
888                     ira_reg_class_intersect[cl1][cl2] = cl3;
889                 }
890               ira_reg_class_union[cl1][cl2] = reg_class_subunion[cl1][cl2];
891               continue;
892             }
893           ira_reg_class_union[cl1][cl2] = NO_REGS;
894           COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
895           AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
896           AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
897           COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
898           IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
899           AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
900           for (i = 0; i < ira_important_classes_num; i++)
901             {
902               cl3 = ira_important_classes[i];
903               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
904               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
905               if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
906                 {
907                   COPY_HARD_REG_SET
908                     (temp_set2,
909                      reg_class_contents[(int)
910                                         ira_reg_class_intersect[cl1][cl2]]);
911                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
912                   if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
913                       /* Ignore unavailable hard registers and prefer
914                          smallest class for debugging purposes.  */
915                       || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
916                           && hard_reg_set_subset_p
917                              (reg_class_contents[cl3],
918                               reg_class_contents
919                               [(int) ira_reg_class_intersect[cl1][cl2]])))
920                     ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
921                 }
922               if (hard_reg_set_subset_p (temp_hard_regset, union_set))
923                 {
924                   COPY_HARD_REG_SET
925                     (temp_set2,
926                      reg_class_contents[(int) ira_reg_class_union[cl1][cl2]]);
927                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
928                   if (ira_reg_class_union[cl1][cl2] == NO_REGS
929                       || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
930                       
931                           && (! hard_reg_set_equal_p (temp_set2,
932                                                       temp_hard_regset)
933                               /* Ignore unavailable hard registers and
934                                  prefer smallest class for debugging
935                                  purposes.  */
936                               || hard_reg_set_subset_p
937                                  (reg_class_contents[cl3],
938                                   reg_class_contents
939                                   [(int) ira_reg_class_union[cl1][cl2]]))))
940                     ira_reg_class_union[cl1][cl2] = (enum reg_class) cl3;
941                 }
942             }
943         }
944     }
945 }
946
947 #endif
948
949 /* Output all cover classes and the translation map into file F.  */
950 static void
951 print_class_cover (FILE *f)
952 {
953   static const char *const reg_class_names[] = REG_CLASS_NAMES;
954   int i;
955
956   fprintf (f, "Class cover:\n");
957   for (i = 0; i < ira_reg_class_cover_size; i++)
958     fprintf (f, " %s", reg_class_names[ira_reg_class_cover[i]]);
959   fprintf (f, "\nClass translation:\n");
960   for (i = 0; i < N_REG_CLASSES; i++)
961     fprintf (f, " %s -> %s\n", reg_class_names[i],
962              reg_class_names[ira_class_translate[i]]);
963 }
964
965 /* Output all cover classes and the translation map into
966    stderr.  */
967 void
968 ira_debug_class_cover (void)
969 {
970   print_class_cover (stderr);
971 }
972
973 /* Set up different arrays concerning class subsets, cover and
974    important classes.  */
975 static void
976 find_reg_class_closure (void)
977 {
978   setup_reg_subclasses ();
979 #ifdef IRA_COVER_CLASSES
980   setup_cover_and_important_classes ();
981   setup_class_translate ();
982   setup_reg_class_intersect_union ();
983 #endif
984 }
985
986 \f
987
988 /* Map: register class x machine mode -> number of hard registers of
989    given class needed to store value of given mode.  If the number is
990    different, the size will be negative.  */
991 int ira_reg_class_nregs[N_REG_CLASSES][MAX_MACHINE_MODE];
992
993 /* Maximal value of the previous array elements.  */
994 int ira_max_nregs;
995
996 /* Form IRA_REG_CLASS_NREGS map.  */
997 static void
998 setup_reg_class_nregs (void)
999 {
1000   int m;
1001   enum reg_class cl;
1002
1003   ira_max_nregs = -1;
1004   for (cl = 0; cl < N_REG_CLASSES; cl++)
1005     for (m = 0; m < MAX_MACHINE_MODE; m++)
1006       {
1007         ira_reg_class_nregs[cl][m] = CLASS_MAX_NREGS (cl, m);
1008         if (ira_max_nregs < ira_reg_class_nregs[cl][m])
1009           ira_max_nregs = ira_reg_class_nregs[cl][m];
1010       }
1011 }
1012
1013 \f
1014
1015 /* Array whose values are hard regset of hard registers available for
1016    the allocation of given register class whose HARD_REGNO_MODE_OK
1017    values for given mode are zero.  */
1018 HARD_REG_SET prohibited_class_mode_regs[N_REG_CLASSES][NUM_MACHINE_MODES];
1019
1020 /* Set up PROHIBITED_CLASS_MODE_REGS.  */
1021 static void
1022 setup_prohibited_class_mode_regs (void)
1023 {
1024   int i, j, k, hard_regno;
1025   enum reg_class cl;
1026
1027   for (i = 0; i < ira_reg_class_cover_size; i++)
1028     {
1029       cl = ira_reg_class_cover[i];
1030       for (j = 0; j < NUM_MACHINE_MODES; j++)
1031         {
1032           CLEAR_HARD_REG_SET (prohibited_class_mode_regs[cl][j]);
1033           for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1034             {
1035               hard_regno = ira_class_hard_regs[cl][k];
1036               if (! HARD_REGNO_MODE_OK (hard_regno, j))
1037                 SET_HARD_REG_BIT (prohibited_class_mode_regs[cl][j],
1038                                   hard_regno);
1039             }
1040         }
1041     }
1042 }
1043
1044 \f
1045
1046 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1047    IRA_MAY_MOVE_IN_COST, and IRA_MAY_MOVE_OUT_COST for MODE if it is
1048    not done yet.  */
1049 void
1050 ira_init_register_move_cost (enum machine_mode mode)
1051 {
1052   int cl1, cl2;
1053
1054   ira_assert (ira_register_move_cost[mode] == NULL
1055               && ira_may_move_in_cost[mode] == NULL
1056               && ira_may_move_out_cost[mode] == NULL);
1057   if (move_cost[mode] == NULL)
1058     init_move_cost (mode);
1059   ira_register_move_cost[mode] = move_cost[mode];
1060   /* Don't use ira_allocate because the tables exist out of scope of a
1061      IRA call.  */
1062   ira_may_move_in_cost[mode]
1063     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1064   memcpy (ira_may_move_in_cost[mode], may_move_in_cost[mode],
1065           sizeof (move_table) * N_REG_CLASSES);
1066   ira_may_move_out_cost[mode]
1067     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1068   memcpy (ira_may_move_out_cost[mode], may_move_out_cost[mode],
1069           sizeof (move_table) * N_REG_CLASSES);
1070   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1071     {
1072       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1073         {
1074           if (ira_class_subset_p[cl1][cl2])
1075             ira_may_move_in_cost[mode][cl1][cl2] = 0;
1076           if (ira_class_subset_p[cl2][cl1])
1077             ira_may_move_out_cost[mode][cl1][cl2] = 0;
1078         }
1079     }
1080 }
1081
1082 \f
1083
1084 /* Hard regsets whose all bits are correspondingly zero or one.  */
1085 HARD_REG_SET ira_zero_hard_reg_set;
1086 HARD_REG_SET ira_one_hard_reg_set;
1087
1088 /* This is called once during compiler work.  It sets up
1089    different arrays whose values don't depend on the compiled
1090    function.  */
1091 void
1092 ira_init_once (void)
1093 {
1094   enum machine_mode mode;
1095
1096   CLEAR_HARD_REG_SET (ira_zero_hard_reg_set);
1097   SET_HARD_REG_SET (ira_one_hard_reg_set);
1098   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1099     {
1100       ira_register_move_cost[mode] = NULL;
1101       ira_may_move_in_cost[mode] = NULL;
1102       ira_may_move_out_cost[mode] = NULL;
1103     }
1104   ira_init_costs_once ();
1105 }
1106
1107 /* Free ira_register_move_cost, ira_may_move_in_cost, and
1108    ira_may_move_out_cost for each mode.  */
1109 static void
1110 free_register_move_costs (void)
1111 {
1112   enum machine_mode mode;
1113
1114   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1115     {
1116       if (ira_may_move_in_cost[mode] != NULL)
1117         free (ira_may_move_in_cost[mode]);
1118       if (ira_may_move_out_cost[mode] != NULL)
1119         free (ira_may_move_out_cost[mode]);
1120       ira_register_move_cost[mode] = NULL;
1121       ira_may_move_in_cost[mode] = NULL;
1122       ira_may_move_out_cost[mode] = NULL;
1123     }
1124 }
1125
1126 /* This is called every time when register related information is
1127    changed.  */
1128 void
1129 ira_init (void)
1130 {
1131   free_register_move_costs ();
1132   setup_reg_mode_hard_regset ();
1133   setup_alloc_regs (flag_omit_frame_pointer != 0);
1134   setup_class_subset_and_memory_move_costs ();
1135   find_reg_class_closure ();
1136   setup_reg_class_nregs ();
1137   setup_prohibited_class_mode_regs ();
1138   ira_init_costs ();
1139 }
1140
1141 /* Function called once at the end of compiler work.  */
1142 void
1143 ira_finish_once (void)
1144 {
1145   ira_finish_costs_once ();
1146   free_register_move_costs ();
1147 }
1148
1149 \f
1150
1151 /* Array whose values are hard regset of hard registers for which
1152    move of the hard register in given mode into itself is
1153    prohibited.  */
1154 HARD_REG_SET ira_prohibited_mode_move_regs[NUM_MACHINE_MODES];
1155
1156 /* Flag of that the above array has been initialized.  */
1157 static bool ira_prohibited_mode_move_regs_initialized_p = false;
1158
1159 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS.  */
1160 static void
1161 setup_prohibited_mode_move_regs (void)
1162 {
1163   int i, j;
1164   rtx test_reg1, test_reg2, move_pat, move_insn;
1165
1166   if (ira_prohibited_mode_move_regs_initialized_p)
1167     return;
1168   ira_prohibited_mode_move_regs_initialized_p = true;
1169   test_reg1 = gen_rtx_REG (VOIDmode, 0);
1170   test_reg2 = gen_rtx_REG (VOIDmode, 0);
1171   move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1172   move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, 0, 0, move_pat, -1, 0);
1173   for (i = 0; i < NUM_MACHINE_MODES; i++)
1174     {
1175       SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1176       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1177         {
1178           if (! HARD_REGNO_MODE_OK (j, i))
1179             continue;
1180           SET_REGNO (test_reg1, j);
1181           PUT_MODE (test_reg1, i);
1182           SET_REGNO (test_reg2, j);
1183           PUT_MODE (test_reg2, i);
1184           INSN_CODE (move_insn) = -1;
1185           recog_memoized (move_insn);
1186           if (INSN_CODE (move_insn) < 0)
1187             continue;
1188           extract_insn (move_insn);
1189           if (! constrain_operands (1))
1190             continue;
1191           CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1192         }
1193     }
1194 }
1195
1196 \f
1197
1198 /* Function specific hard registers that can not be used for the
1199    register allocation.  */
1200 HARD_REG_SET ira_no_alloc_regs;
1201
1202 /* Return TRUE if *LOC contains an asm.  */
1203 static int
1204 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
1205 {
1206   if ( !*loc)
1207     return FALSE;
1208   if (GET_CODE (*loc) == ASM_OPERANDS)
1209     return TRUE;
1210   return FALSE;
1211 }
1212
1213
1214 /* Return TRUE if INSN contains an ASM.  */
1215 static bool
1216 insn_contains_asm (rtx insn)
1217 {
1218   return for_each_rtx (&insn, insn_contains_asm_1, NULL);
1219 }
1220
1221 /* Set up regs_asm_clobbered.  */
1222 static void
1223 compute_regs_asm_clobbered (char *regs_asm_clobbered)
1224 {
1225   basic_block bb;
1226
1227   memset (regs_asm_clobbered, 0, sizeof (char) * FIRST_PSEUDO_REGISTER);
1228   
1229   FOR_EACH_BB (bb)
1230     {
1231       rtx insn;
1232       FOR_BB_INSNS_REVERSE (bb, insn)
1233         {
1234           struct df_ref **def_rec;
1235
1236           if (insn_contains_asm (insn))
1237             for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1238               {
1239                 struct df_ref *def = *def_rec;
1240                 unsigned int dregno = DF_REF_REGNO (def);
1241                 if (dregno < FIRST_PSEUDO_REGISTER)
1242                   {
1243                     unsigned int i;
1244                     enum machine_mode mode = GET_MODE (DF_REF_REAL_REG (def));
1245                     unsigned int end = dregno 
1246                       + hard_regno_nregs[dregno][mode] - 1;
1247
1248                     for (i = dregno; i <= end; ++i)
1249                       regs_asm_clobbered[i] = 1;
1250                   }
1251               }
1252         }
1253     }
1254 }
1255
1256
1257 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE.  */
1258 static void
1259 setup_eliminable_regset (void)
1260 {
1261   int i;
1262   /* Like regs_ever_live, but 1 if a reg is set or clobbered from an
1263      asm.  Unlike regs_ever_live, elements of this array corresponding
1264      to eliminable regs (like the frame pointer) are set if an asm
1265      sets them.  */
1266   char *regs_asm_clobbered
1267     = (char *) alloca (FIRST_PSEUDO_REGISTER * sizeof (char));
1268 #ifdef ELIMINABLE_REGS
1269   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
1270 #endif
1271   /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1272      sp for alloca.  So we can't eliminate the frame pointer in that
1273      case.  At some point, we should improve this by emitting the
1274      sp-adjusting insns for this case.  */
1275   int need_fp
1276     = (! flag_omit_frame_pointer
1277        || (cfun->calls_alloca && EXIT_IGNORE_STACK)
1278        || crtl->accesses_prior_frames
1279        || crtl->stack_realign_needed
1280        || FRAME_POINTER_REQUIRED);
1281
1282   frame_pointer_needed = need_fp;
1283
1284   COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
1285   CLEAR_HARD_REG_SET (eliminable_regset);
1286
1287   compute_regs_asm_clobbered (regs_asm_clobbered);
1288   /* Build the regset of all eliminable registers and show we can't
1289      use those that we already know won't be eliminated.  */
1290 #ifdef ELIMINABLE_REGS
1291   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
1292     {
1293       bool cannot_elim
1294         = (! CAN_ELIMINATE (eliminables[i].from, eliminables[i].to)
1295            || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
1296
1297       if (! regs_asm_clobbered[eliminables[i].from])
1298         {
1299             SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
1300
1301             if (cannot_elim)
1302               SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
1303         }
1304       else if (cannot_elim)
1305         error ("%s cannot be used in asm here",
1306                reg_names[eliminables[i].from]);
1307       else
1308         df_set_regs_ever_live (eliminables[i].from, true);
1309     }
1310 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
1311   if (! regs_asm_clobbered[HARD_FRAME_POINTER_REGNUM])
1312     {
1313       SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
1314       if (need_fp)
1315         SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
1316     }
1317   else if (need_fp)
1318     error ("%s cannot be used in asm here",
1319            reg_names[HARD_FRAME_POINTER_REGNUM]);
1320   else
1321     df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
1322 #endif
1323
1324 #else
1325   if (! regs_asm_clobbered[FRAME_POINTER_REGNUM])
1326     {
1327       SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
1328       if (need_fp)
1329         SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
1330     }
1331   else if (need_fp)
1332     error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
1333   else
1334     df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
1335 #endif
1336 }
1337
1338 \f
1339
1340 /* The length of the following two arrays.  */
1341 int ira_reg_equiv_len;
1342
1343 /* The element value is TRUE if the corresponding regno value is
1344    invariant.  */
1345 bool *ira_reg_equiv_invariant_p;
1346
1347 /* The element value is equiv constant of given pseudo-register or
1348    NULL_RTX.  */
1349 rtx *ira_reg_equiv_const;
1350
1351 /* Set up the two arrays declared above.  */
1352 static void
1353 find_reg_equiv_invariant_const (void)
1354 {
1355   int i;
1356   bool invariant_p;
1357   rtx list, insn, note, constant, x;
1358
1359   for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
1360     {
1361       constant = NULL_RTX;
1362       invariant_p = false;
1363       for (list = reg_equiv_init[i]; list != NULL_RTX; list = XEXP (list, 1))
1364         {
1365           insn = XEXP (list, 0);
1366           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
1367           
1368           if (note == NULL_RTX)
1369             continue;
1370
1371           x = XEXP (note, 0);
1372           
1373           if (! function_invariant_p (x)
1374               || ! flag_pic
1375               /* A function invariant is often CONSTANT_P but may
1376                  include a register.  We promise to only pass CONSTANT_P
1377                  objects to LEGITIMATE_PIC_OPERAND_P.  */
1378               || (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
1379             {
1380               /* It can happen that a REG_EQUIV note contains a MEM
1381                  that is not a legitimate memory operand.  As later
1382                  stages of the reload assume that all addresses found
1383                  in the reg_equiv_* arrays were originally legitimate,
1384                  we ignore such REG_EQUIV notes.  */
1385               if (memory_operand (x, VOIDmode))
1386                 invariant_p = MEM_READONLY_P (x);
1387               else if (function_invariant_p (x))
1388                 {
1389                   if (GET_CODE (x) == PLUS
1390                       || x == frame_pointer_rtx || x == arg_pointer_rtx)
1391                     invariant_p = true;
1392                   else
1393                     constant = x;
1394                 }
1395             }
1396         }
1397       ira_reg_equiv_invariant_p[i] = invariant_p;
1398       ira_reg_equiv_const[i] = constant;
1399     }
1400 }
1401
1402 \f
1403
1404 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1405    the allocation found by IRA.  */
1406 static void
1407 setup_reg_renumber (void)
1408 {
1409   int regno, hard_regno;
1410   ira_allocno_t a;
1411   ira_allocno_iterator ai;
1412
1413   caller_save_needed = 0;
1414   FOR_EACH_ALLOCNO (a, ai)
1415     {
1416       /* There are no caps at this point.  */
1417       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1418       if (! ALLOCNO_ASSIGNED_P (a))
1419         /* It can happen if A is not referenced but partially anticipated
1420            somewhere in a region.  */
1421         ALLOCNO_ASSIGNED_P (a) = true;
1422       ira_free_allocno_updated_costs (a);
1423       hard_regno = ALLOCNO_HARD_REGNO (a);
1424       regno = (int) REGNO (ALLOCNO_REG (a));
1425       reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
1426       if (hard_regno >= 0 && ALLOCNO_CALLS_CROSSED_NUM (a) != 0
1427           && ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1428                                           call_used_reg_set))
1429         {
1430           ira_assert (!optimize || flag_caller_saves
1431                       || regno >= ira_reg_equiv_len
1432                       || ira_reg_equiv_const[regno]
1433                       || ira_reg_equiv_invariant_p[regno]);
1434           caller_save_needed = 1;
1435         }
1436     }
1437 }
1438
1439 /* Set up allocno assignment flags for further allocation
1440    improvements.  */
1441 static void
1442 setup_allocno_assignment_flags (void)
1443 {
1444   int hard_regno;
1445   ira_allocno_t a;
1446   ira_allocno_iterator ai;
1447
1448   FOR_EACH_ALLOCNO (a, ai)
1449     {
1450       if (! ALLOCNO_ASSIGNED_P (a))
1451         /* It can happen if A is not referenced but partially anticipated
1452            somewhere in a region.  */
1453         ira_free_allocno_updated_costs (a);
1454       hard_regno = ALLOCNO_HARD_REGNO (a);
1455       /* Don't assign hard registers to allocnos which are destination
1456          of removed store at the end of loop.  It has no sense to keep
1457          the same value in different hard registers.  It is also
1458          impossible to assign hard registers correctly to such
1459          allocnos because the cost info and info about intersected
1460          calls are incorrect for them.  */
1461       ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
1462                                 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a)
1463                                 || (ALLOCNO_MEMORY_COST (a)
1464                                     - ALLOCNO_COVER_CLASS_COST (a)) < 0);
1465       ira_assert (hard_regno < 0
1466                   || ! ira_hard_reg_not_in_set_p (hard_regno, ALLOCNO_MODE (a),
1467                                                   reg_class_contents
1468                                                   [ALLOCNO_COVER_CLASS (a)]));
1469     }
1470 }
1471
1472 /* Evaluate overall allocation cost and the costs for using hard
1473    registers and memory for allocnos.  */
1474 static void
1475 calculate_allocation_cost (void)
1476 {
1477   int hard_regno, cost;
1478   ira_allocno_t a;
1479   ira_allocno_iterator ai;
1480
1481   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
1482   FOR_EACH_ALLOCNO (a, ai)
1483     {
1484       hard_regno = ALLOCNO_HARD_REGNO (a);
1485       ira_assert (hard_regno < 0
1486                   || ! ira_hard_reg_not_in_set_p
1487                        (hard_regno, ALLOCNO_MODE (a),
1488                         reg_class_contents[ALLOCNO_COVER_CLASS (a)])); 
1489       if (hard_regno < 0)
1490         {
1491           cost = ALLOCNO_MEMORY_COST (a);
1492           ira_mem_cost += cost;
1493         }
1494       else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1495         {
1496           cost = (ALLOCNO_HARD_REG_COSTS (a)
1497                   [ira_class_hard_reg_index
1498                    [ALLOCNO_COVER_CLASS (a)][hard_regno]]);
1499           ira_reg_cost += cost;
1500         }
1501       else
1502         {
1503           cost = ALLOCNO_COVER_CLASS_COST (a);
1504           ira_reg_cost += cost;
1505         }
1506       ira_overall_cost += cost;
1507     }
1508
1509   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1510     {
1511       fprintf (ira_dump_file,
1512                "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
1513                ira_overall_cost, ira_reg_cost, ira_mem_cost,
1514                ira_load_cost, ira_store_cost, ira_shuffle_cost);
1515       fprintf (ira_dump_file, "+++       move loops %d, new jumps %d\n",
1516                ira_move_loops_num, ira_additional_jumps_num);
1517     }
1518
1519 }
1520
1521 #ifdef ENABLE_IRA_CHECKING
1522 /* Check the correctness of the allocation.  We do need this because
1523    of complicated code to transform more one region internal
1524    representation into one region representation.  */
1525 static void
1526 check_allocation (void)
1527 {
1528   ira_allocno_t a, conflict_a;
1529   int hard_regno, conflict_hard_regno, nregs, conflict_nregs;
1530   ira_allocno_conflict_iterator aci;
1531   ira_allocno_iterator ai;
1532
1533   FOR_EACH_ALLOCNO (a, ai)
1534     {
1535       if (ALLOCNO_CAP_MEMBER (a) != NULL
1536           || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
1537         continue;
1538       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
1539       FOR_EACH_ALLOCNO_CONFLICT (a, conflict_a, aci)
1540         if ((conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a)) >= 0)
1541           {
1542             conflict_nregs
1543               = (hard_regno_nregs
1544                  [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
1545             if ((conflict_hard_regno <= hard_regno
1546                  && hard_regno < conflict_hard_regno + conflict_nregs)
1547                 || (hard_regno <= conflict_hard_regno
1548                     && conflict_hard_regno < hard_regno + nregs))
1549               {
1550                 fprintf (stderr, "bad allocation for %d and %d\n",
1551                          ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
1552                 gcc_unreachable ();
1553               }
1554           }
1555     }
1556 }
1557 #endif
1558
1559 /* Fix values of array REG_EQUIV_INIT after live range splitting done
1560    by IRA.  */
1561 static void
1562 fix_reg_equiv_init (void)
1563 {
1564   int max_regno = max_reg_num ();
1565   int i, new_regno;
1566   rtx x, prev, next, insn, set;
1567   
1568   if (reg_equiv_init_size < max_regno)
1569     {
1570       reg_equiv_init
1571         = (rtx *) ggc_realloc (reg_equiv_init, max_regno * sizeof (rtx));
1572       while (reg_equiv_init_size < max_regno)
1573         reg_equiv_init[reg_equiv_init_size++] = NULL_RTX;
1574       for (i = FIRST_PSEUDO_REGISTER; i < reg_equiv_init_size; i++)
1575         for (prev = NULL_RTX, x = reg_equiv_init[i]; x != NULL_RTX; x = next)
1576           {
1577             next = XEXP (x, 1);
1578             insn = XEXP (x, 0);
1579             set = single_set (insn);
1580             ira_assert (set != NULL_RTX
1581                         && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
1582             if (REG_P (SET_DEST (set))
1583                 && ((int) REGNO (SET_DEST (set)) == i
1584                     || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
1585               new_regno = REGNO (SET_DEST (set));
1586             else if (REG_P (SET_SRC (set))
1587                      && ((int) REGNO (SET_SRC (set)) == i
1588                          || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
1589               new_regno = REGNO (SET_SRC (set));
1590             else
1591               gcc_unreachable ();
1592             if (new_regno == i)
1593               prev = x;
1594             else
1595               {
1596                 if (prev == NULL_RTX)
1597                   reg_equiv_init[i] = next;
1598                 else
1599                   XEXP (prev, 1) = next;
1600                 XEXP (x, 1) = reg_equiv_init[new_regno];
1601                 reg_equiv_init[new_regno] = x;
1602               }
1603           }
1604     }
1605 }
1606
1607 #ifdef ENABLE_IRA_CHECKING
1608 /* Print redundant memory-memory copies.  */
1609 static void
1610 print_redundant_copies (void)
1611 {
1612   int hard_regno;
1613   ira_allocno_t a;
1614   ira_copy_t cp, next_cp;
1615   ira_allocno_iterator ai;
1616   
1617   FOR_EACH_ALLOCNO (a, ai)
1618     {
1619       if (ALLOCNO_CAP_MEMBER (a) != NULL)
1620         /* It is a cap. */
1621         continue;
1622       hard_regno = ALLOCNO_HARD_REGNO (a);
1623       if (hard_regno >= 0)
1624         continue;
1625       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1626         if (cp->first == a)
1627           next_cp = cp->next_first_allocno_copy;
1628         else
1629           {
1630             next_cp = cp->next_second_allocno_copy;
1631             if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
1632                 && cp->insn != NULL_RTX
1633                 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
1634               fprintf (ira_dump_file,
1635                        "        Redundant move from %d(freq %d):%d\n",
1636                        INSN_UID (cp->insn), cp->freq, hard_regno);
1637           }
1638     }
1639 }
1640 #endif
1641
1642 /* Setup preferred and alternative classes for new pseudo-registers
1643    created by IRA starting with START.  */
1644 static void
1645 setup_preferred_alternate_classes_for_new_pseudos (int start)
1646 {
1647   int i, old_regno;
1648   int max_regno = max_reg_num ();
1649
1650   for (i = start; i < max_regno; i++)
1651     {
1652       old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
1653       ira_assert (i != old_regno); 
1654       setup_reg_classes (i, reg_preferred_class (old_regno),
1655                          reg_alternate_class (old_regno));
1656       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1657         fprintf (ira_dump_file,
1658                  "    New r%d: setting preferred %s, alternative %s\n",
1659                  i, reg_class_names[reg_preferred_class (old_regno)],
1660                  reg_class_names[reg_alternate_class (old_regno)]);
1661     }
1662 }
1663
1664 \f
1665
1666 /* Regional allocation can create new pseudo-registers.  This function
1667    expands some arrays for pseudo-registers.  */
1668 static void
1669 expand_reg_info (int old_size)
1670 {
1671   int i;
1672   int size = max_reg_num ();
1673
1674   resize_reg_info ();
1675   for (i = old_size; i < size; i++)
1676     {
1677       reg_renumber[i] = -1;
1678       setup_reg_classes (i, GENERAL_REGS, ALL_REGS);
1679     }
1680 }
1681
1682 \f
1683
1684 /* This page contains code for sorting the insn chain used by reload.
1685    In the old register allocator, the insn chain order corresponds to
1686    the order of insns in RTL.  By putting insns with higher execution
1687    frequency BBs first, reload has a better chance to generate less
1688    expensive operand reloads for such insns.  */
1689
1690 /* Map bb index -> order number in the BB chain in RTL code.  */
1691 static int *basic_block_order_nums;
1692
1693 /* Map chain insn uid -> order number in the insn chain before sorting
1694    the insn chain.  */
1695 static int *chain_insn_order;
1696
1697 /* The function is used to sort insn chain according insn execution
1698    frequencies.  */
1699 static int
1700 chain_freq_compare (const void *v1p, const void *v2p)
1701 {
1702   const struct insn_chain *c1 = *(struct insn_chain * const *)v1p;
1703   const struct insn_chain *c2 = *(struct insn_chain * const *)v2p;
1704   int diff;
1705
1706   diff = (BASIC_BLOCK (c2->block)->frequency
1707           - BASIC_BLOCK (c1->block)->frequency);
1708   if (diff)
1709     return diff;
1710   /* Keep the same order in BB scope.  */
1711   return (chain_insn_order[INSN_UID(c1->insn)]
1712           - chain_insn_order[INSN_UID(c2->insn)]);
1713 }
1714
1715 /* Sort the insn chain according insn original order.  */
1716 static int
1717 chain_bb_compare (const void *v1p, const void *v2p)
1718 {
1719   const struct insn_chain *c1 = *(struct insn_chain * const *)v1p;
1720   const struct insn_chain *c2 = *(struct insn_chain * const *)v2p;
1721   int diff;
1722
1723   diff = (basic_block_order_nums[c1->block]
1724           - basic_block_order_nums[c2->block]);
1725   if (diff)
1726     return diff;
1727   /* Keep the same order in BB scope.  */
1728   return (chain_insn_order[INSN_UID(c1->insn)]
1729           - chain_insn_order[INSN_UID(c2->insn)]);
1730 }
1731
1732 /* Sort the insn chain according to insn frequencies if
1733    FREQ_P or according to insn original order otherwise.  */
1734 void
1735 ira_sort_insn_chain (bool freq_p)
1736 {
1737   struct insn_chain *chain, **chain_arr;
1738   basic_block bb;
1739   int i, n;
1740   
1741   chain_insn_order = (int *) ira_allocate (get_max_uid () * sizeof (int));
1742   for (n = 0, chain = reload_insn_chain; chain != 0; chain = chain->next)
1743     {
1744       chain_insn_order[INSN_UID (chain->insn)] = n;
1745       n++;
1746     }
1747   if (n <= 1)
1748     return;
1749   chain_arr
1750     = (struct insn_chain **) ira_allocate (n * sizeof (struct insn_chain *));
1751   basic_block_order_nums
1752     = (int *) ira_allocate (sizeof (int) * last_basic_block);
1753   n = 0;
1754   FOR_EACH_BB (bb)
1755     {
1756       basic_block_order_nums[bb->index] = n++;
1757     }
1758   for (n = 0, chain = reload_insn_chain; chain != 0; chain = chain->next)
1759     chain_arr[n++] = chain;
1760   qsort (chain_arr, n, sizeof (struct insn_chain *),
1761          freq_p ? chain_freq_compare : chain_bb_compare);
1762   ira_free (chain_insn_order);
1763   for (i = 1; i < n - 1; i++)
1764     {
1765       chain_arr[i]->next = chain_arr[i + 1];
1766       chain_arr[i]->prev = chain_arr[i - 1];
1767     }
1768   chain_arr[i]->next = NULL;
1769   chain_arr[i]->prev = chain_arr[i - 1];
1770   reload_insn_chain = chain_arr[0];
1771   reload_insn_chain->prev = NULL;
1772   reload_insn_chain->next = chain_arr[1];
1773   ira_free (basic_block_order_nums);
1774   ira_free (chain_arr);
1775 }
1776
1777 \f
1778
1779 /* All natural loops.  */
1780 struct loops ira_loops;
1781
1782 /* This is the main entry of IRA.  */
1783 static void
1784 ira (FILE *f)
1785 {
1786   int overall_cost_before, allocated_reg_info_size;
1787   bool loops_p;
1788   int max_regno_before_ira, ira_max_point_before_emit;
1789   int rebuild_p;
1790   int saved_flag_ira_algorithm;
1791   basic_block bb;
1792
1793   timevar_push (TV_IRA);
1794
1795   if (flag_ira_verbose < 10)
1796     {
1797       internal_flag_ira_verbose = flag_ira_verbose;
1798       ira_dump_file = f;
1799     }
1800   else
1801     {
1802       internal_flag_ira_verbose = flag_ira_verbose - 10;
1803       ira_dump_file = stderr;
1804     }
1805
1806   setup_prohibited_mode_move_regs ();
1807
1808   df_note_add_problem ();
1809
1810   if (optimize == 1)
1811     {
1812       df_live_add_problem ();
1813       df_live_set_all_dirty ();
1814     }
1815 #ifdef ENABLE_CHECKING
1816   df->changeable_flags |= DF_VERIFY_SCHEDULED;
1817 #endif
1818   df_analyze ();
1819   df_clear_flags (DF_NO_INSN_RESCAN);
1820   regstat_init_n_sets_and_refs ();
1821   regstat_compute_ri ();
1822
1823   /* If we are not optimizing, then this is the only place before
1824      register allocation where dataflow is done.  And that is needed
1825      to generate these warnings.  */
1826   if (warn_clobbered)
1827     generate_setjmp_warnings ();
1828
1829   rebuild_p = update_equiv_regs ();
1830
1831 #ifndef IRA_NO_OBSTACK
1832   gcc_obstack_init (&ira_obstack);
1833 #endif
1834   bitmap_obstack_initialize (&ira_bitmap_obstack);
1835   if (optimize)
1836     {      
1837       max_regno = max_reg_num ();
1838       ira_reg_equiv_len = max_regno;
1839       ira_reg_equiv_invariant_p
1840         = (bool *) ira_allocate (max_regno * sizeof (bool));
1841       memset (ira_reg_equiv_invariant_p, 0, max_regno * sizeof (bool));
1842       ira_reg_equiv_const = (rtx *) ira_allocate (max_regno * sizeof (rtx));
1843       memset (ira_reg_equiv_const, 0, max_regno * sizeof (rtx));
1844       find_reg_equiv_invariant_const ();
1845       if (rebuild_p)
1846         {
1847           timevar_push (TV_JUMP);
1848           rebuild_jump_labels (get_insns ());
1849           purge_all_dead_edges ();
1850           timevar_pop (TV_JUMP);
1851         }
1852     }
1853
1854   max_regno_before_ira = allocated_reg_info_size = max_reg_num ();
1855   allocate_reg_info ();
1856   setup_eliminable_regset ();
1857       
1858   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
1859   ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
1860   ira_move_loops_num = ira_additional_jumps_num = 0;
1861   
1862   ira_assert (current_loops == NULL);
1863   flow_loops_find (&ira_loops);
1864   current_loops = &ira_loops;
1865   saved_flag_ira_algorithm = flag_ira_algorithm;
1866   if (optimize && number_of_loops () > (unsigned) IRA_MAX_LOOPS_NUM)
1867     flag_ira_algorithm = IRA_ALGORITHM_CB;
1868       
1869   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1870     fprintf (ira_dump_file, "Building IRA IR\n");
1871   loops_p = ira_build (optimize
1872                        && (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
1873                            || flag_ira_algorithm == IRA_ALGORITHM_MIXED));
1874   if (optimize)
1875     ira_color ();
1876   else
1877     ira_fast_allocation ();
1878       
1879   ira_max_point_before_emit = ira_max_point;
1880       
1881   ira_emit (loops_p);
1882   
1883   if (optimize)
1884     {
1885       max_regno = max_reg_num ();
1886       
1887       if (! loops_p)
1888         ira_initiate_assign ();
1889       else
1890         {
1891           expand_reg_info (allocated_reg_info_size);
1892           setup_preferred_alternate_classes_for_new_pseudos
1893             (allocated_reg_info_size);
1894           allocated_reg_info_size = max_regno;
1895           
1896           if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
1897             fprintf (ira_dump_file, "Flattening IR\n");
1898           ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
1899           /* New insns were generated: add notes and recalculate live
1900              info.  */
1901           df_analyze ();
1902           
1903           flow_loops_find (&ira_loops);
1904           current_loops = &ira_loops;
1905
1906           setup_allocno_assignment_flags ();
1907           ira_initiate_assign ();
1908           ira_reassign_conflict_allocnos (max_regno);
1909         }
1910     }
1911
1912   setup_reg_renumber ();
1913   
1914   calculate_allocation_cost ();
1915   
1916 #ifdef ENABLE_IRA_CHECKING
1917   if (optimize)
1918     check_allocation ();
1919 #endif
1920       
1921   delete_trivially_dead_insns (get_insns (), max_reg_num ());
1922   max_regno = max_reg_num ();
1923   
1924   /* Determine if the current function is a leaf before running IRA
1925      since this can impact optimizations done by the prologue and
1926      epilogue thus changing register elimination offsets.  */
1927   current_function_is_leaf = leaf_function_p ();
1928   
1929   /* And the reg_equiv_memory_loc array.  */
1930   VEC_safe_grow (rtx, gc, reg_equiv_memory_loc_vec, max_regno);
1931   memset (VEC_address (rtx, reg_equiv_memory_loc_vec), 0,
1932           sizeof (rtx) * max_regno);
1933   reg_equiv_memory_loc = VEC_address (rtx, reg_equiv_memory_loc_vec);
1934
1935   if (max_regno != max_regno_before_ira)
1936     {
1937       regstat_free_n_sets_and_refs ();
1938       regstat_free_ri ();
1939       regstat_init_n_sets_and_refs ();
1940       regstat_compute_ri ();
1941     }
1942
1943   allocate_initial_values (reg_equiv_memory_loc);
1944
1945   overall_cost_before = ira_overall_cost;
1946   if (optimize)
1947     {
1948       fix_reg_equiv_init ();
1949       
1950 #ifdef ENABLE_IRA_CHECKING
1951       print_redundant_copies ();
1952 #endif
1953
1954       ira_spilled_reg_stack_slots_num = 0;
1955       ira_spilled_reg_stack_slots
1956         = ((struct ira_spilled_reg_stack_slot *)
1957            ira_allocate (max_regno
1958                          * sizeof (struct ira_spilled_reg_stack_slot)));
1959       memset (ira_spilled_reg_stack_slots, 0,
1960               max_regno * sizeof (struct ira_spilled_reg_stack_slot));
1961     }
1962   
1963   timevar_pop (TV_IRA);
1964
1965   timevar_push (TV_RELOAD);
1966   df_set_flags (DF_NO_INSN_RESCAN);
1967   build_insn_chain ();
1968
1969   if (optimize)
1970     ira_sort_insn_chain (true);
1971
1972   reload_completed = !reload (get_insns (), optimize > 0);
1973
1974   timevar_pop (TV_RELOAD);
1975
1976   timevar_push (TV_IRA);
1977
1978   if (optimize)
1979     {
1980       ira_free (ira_spilled_reg_stack_slots);
1981       
1982       ira_finish_assign ();
1983       
1984     }  
1985   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
1986       && overall_cost_before != ira_overall_cost)
1987     fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
1988   ira_destroy ();
1989   
1990   flow_loops_free (&ira_loops);
1991   free_dominance_info (CDI_DOMINATORS);
1992   FOR_ALL_BB (bb)
1993     bb->loop_father = NULL;
1994   current_loops = NULL;
1995
1996   flag_ira_algorithm = saved_flag_ira_algorithm;
1997
1998   regstat_free_ri ();
1999   regstat_free_n_sets_and_refs ();
2000       
2001   if (optimize)
2002     {
2003       cleanup_cfg (CLEANUP_EXPENSIVE);
2004       
2005       ira_free (ira_reg_equiv_invariant_p);
2006       ira_free (ira_reg_equiv_const);
2007     }
2008
2009   bitmap_obstack_release (&ira_bitmap_obstack);
2010 #ifndef IRA_NO_OBSTACK
2011   obstack_free (&ira_obstack, NULL);
2012 #endif
2013
2014   /* The code after the reload has changed so much that at this point
2015      we might as well just rescan everything.  Not that
2016      df_rescan_all_insns is not going to help here because it does not
2017      touch the artificial uses and defs.  */
2018   df_finish_pass (true);
2019   if (optimize > 1)
2020     df_live_add_problem ();
2021   df_scan_alloc (NULL);
2022   df_scan_blocks ();
2023
2024   if (optimize)
2025     df_analyze ();
2026
2027   timevar_pop (TV_IRA);
2028 }
2029
2030 \f
2031
2032 static bool
2033 gate_ira (void)
2034 {
2035   return flag_ira != 0;
2036 }
2037
2038 /* Run the integrated register allocator.  */
2039 static unsigned int
2040 rest_of_handle_ira (void)
2041 {
2042   ira (dump_file);
2043   return 0;
2044 }
2045
2046 struct rtl_opt_pass pass_ira =
2047 {
2048  {
2049   RTL_PASS,
2050   "ira",                                /* name */
2051   gate_ira,                             /* gate */
2052   rest_of_handle_ira,                   /* execute */
2053   NULL,                                 /* sub */
2054   NULL,                                 /* next */
2055   0,                                    /* static_pass_number */
2056   0,                                    /* tv_id */
2057   0,                                    /* properties_required */
2058   0,                                    /* properties_provided */
2059   0,                                    /* properties_destroyed */
2060   0,                                    /* todo_flags_start */
2061   TODO_dump_func |
2062   TODO_ggc_collect                      /* todo_flags_finish */
2063  }
2064 };