OSDN Git Service

* ira.c (check_allocation): Use REG_WORDS_BIG_ENDIAN, not
[pf3gnuchains/gcc-fork.git] / gcc / ira.c
1 /* Integrated Register Allocator (IRA) entry point.
2    Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011, 2012
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 *Allocno class* is a register class used for allocation of
42        given allocno.  It means that only hard register of given
43        register class can be assigned to given allocno.  In reality,
44        even smaller subset of (*profitable*) hard registers can be
45        assigned.  In rare cases, the subset can be even smaller
46        because our modification of Chaitin-Briggs algorithm requires
47        that sets of hard registers can be assigned to allocnos forms a
48        forest, i.e. the sets can be ordered in a way where any
49        previous set is not intersected with given set or is a superset
50        of given set.
51
52      o *Pressure class* is a register class belonging to a set of
53        register classes containing all of the hard-registers available
54        for register allocation.  The set of all pressure classes for a
55        target is defined in the corresponding machine-description file
56        according some criteria.  Register pressure is calculated only
57        for pressure classes and it affects some IRA decisions as
58        forming allocation regions.
59
60      o *Allocno* represents the live range of a pseudo-register in a
61        region.  Besides the obvious attributes like the corresponding
62        pseudo-register number, allocno class, conflicting allocnos and
63        conflicting hard-registers, there are a few allocno attributes
64        which are important for understanding the allocation algorithm:
65
66        - *Live ranges*.  This is a list of ranges of *program points*
67          where the allocno lives.  Program points represent places
68          where a pseudo can be born or become dead (there are
69          approximately two times more program points than the insns)
70          and they are represented by integers starting with 0.  The
71          live ranges are used to find conflicts between allocnos.
72          They also play very important role for the transformation of
73          the IRA internal representation of several regions into a one
74          region representation.  The later is used during the reload
75          pass work because each allocno represents all of the
76          corresponding pseudo-registers.
77
78        - *Hard-register costs*.  This is a vector of size equal to the
79          number of available hard-registers of the allocno class.  The
80          cost of a callee-clobbered hard-register for an allocno is
81          increased by the cost of save/restore code around the calls
82          through the given allocno's life.  If the allocno is a move
83          instruction operand and another operand is a hard-register of
84          the allocno class, the cost of the hard-register is decreased
85          by the move cost.
86
87          When an allocno is assigned, the hard-register with minimal
88          full cost is used.  Initially, a hard-register's full cost is
89          the corresponding value from the hard-register's cost vector.
90          If the allocno is connected by a *copy* (see below) to
91          another allocno which has just received a hard-register, the
92          cost of the hard-register is decreased.  Before choosing a
93          hard-register for an allocno, the allocno's current costs of
94          the hard-registers are modified by the conflict hard-register
95          costs of all of the conflicting allocnos which are not
96          assigned yet.
97
98        - *Conflict hard-register costs*.  This is a vector of the same
99          size as the hard-register costs vector.  To permit an
100          unassigned allocno to get a better hard-register, IRA uses
101          this vector to calculate the final full cost of the
102          available hard-registers.  Conflict hard-register costs of an
103          unassigned allocno are also changed with a change of the
104          hard-register cost of the allocno when a copy involving the
105          allocno is processed as described above.  This is done to
106          show other unassigned allocnos that a given allocno prefers
107          some hard-registers in order to remove the move instruction
108          corresponding to the copy.
109
110      o *Cap*.  If a pseudo-register does not live in a region but
111        lives in a nested region, IRA creates a special allocno called
112        a cap in the outer region.  A region cap is also created for a
113        subregion cap.
114
115      o *Copy*.  Allocnos can be connected by copies.  Copies are used
116        to modify hard-register costs for allocnos during coloring.
117        Such modifications reflects a preference to use the same
118        hard-register for the allocnos connected by copies.  Usually
119        copies are created for move insns (in this case it results in
120        register coalescing).  But IRA also creates copies for operands
121        of an insn which should be assigned to the same hard-register
122        due to constraints in the machine description (it usually
123        results in removing a move generated in reload to satisfy
124        the constraints) and copies referring to the allocno which is
125        the output operand of an instruction and the allocno which is
126        an input operand dying in the instruction (creation of such
127        copies results in less register shuffling).  IRA *does not*
128        create copies between the same register allocnos from different
129        regions because we use another technique for propagating
130        hard-register preference on the borders of regions.
131
132    Allocnos (including caps) for the upper region in the region tree
133    *accumulate* information important for coloring from allocnos with
134    the same pseudo-register from nested regions.  This includes
135    hard-register and memory costs, conflicts with hard-registers,
136    allocno conflicts, allocno copies and more.  *Thus, attributes for
137    allocnos in a region have the same values as if the region had no
138    subregions*.  It means that attributes for allocnos in the
139    outermost region corresponding to the function have the same values
140    as though the allocation used only one region which is the entire
141    function.  It also means that we can look at IRA work as if the
142    first IRA did allocation for all function then it improved the
143    allocation for loops then their subloops and so on.
144
145    IRA major passes are:
146
147      o Building IRA internal representation which consists of the
148        following subpasses:
149
150        * First, IRA builds regions and creates allocnos (file
151          ira-build.c) and initializes most of their attributes.
152
153        * Then IRA finds an allocno class for each allocno and
154          calculates its initial (non-accumulated) cost of memory and
155          each hard-register of its allocno class (file ira-cost.c).
156
157        * IRA creates live ranges of each allocno, calulates register
158          pressure for each pressure class in each region, sets up
159          conflict hard registers for each allocno and info about calls
160          the allocno lives through (file ira-lives.c).
161
162        * IRA removes low register pressure loops from the regions
163          mostly to speed IRA up (file ira-build.c).
164
165        * IRA propagates accumulated allocno info from lower region
166          allocnos to corresponding upper region allocnos (file
167          ira-build.c).
168
169        * IRA creates all caps (file ira-build.c).
170
171        * Having live-ranges of allocnos and their classes, IRA creates
172          conflicting allocnos for each allocno.  Conflicting allocnos
173          are stored as a bit vector or array of pointers to the
174          conflicting allocnos whatever is more profitable (file
175          ira-conflicts.c).  At this point IRA creates allocno copies.
176
177      o Coloring.  Now IRA has all necessary info to start graph coloring
178        process.  It is done in each region on top-down traverse of the
179        region tree (file ira-color.c).  There are following subpasses:
180
181        * Finding profitable hard registers of corresponding allocno
182          class for each allocno.  For example, only callee-saved hard
183          registers are frequently profitable for allocnos living
184          through colors.  If the profitable hard register set of
185          allocno does not form a tree based on subset relation, we use
186          some approximation to form the tree.  This approximation is
187          used to figure out trivial colorability of allocnos.  The
188          approximation is a pretty rare case.
189
190        * Putting allocnos onto the coloring stack.  IRA uses Briggs
191          optimistic coloring which is a major improvement over
192          Chaitin's coloring.  Therefore IRA does not spill allocnos at
193          this point.  There is some freedom in the order of putting
194          allocnos on the stack which can affect the final result of
195          the allocation.  IRA uses some heuristics to improve the
196          order.
197          
198          We also use a modification of Chaitin-Briggs algorithm which
199          works for intersected register classes of allocnos.  To
200          figure out trivial colorability of allocnos, the mentioned
201          above tree of hard register sets is used.  To get an idea how
202          the algorithm works in i386 example, let us consider an
203          allocno to which any general hard register can be assigned.
204          If the allocno conflicts with eight allocnos to which only
205          EAX register can be assigned, given allocno is still
206          trivially colorable because all conflicting allocnos might be
207          assigned only to EAX and all other general hard registers are
208          still free.
209
210          To get an idea of the used trivial colorability criterion, it
211          is also useful to read article "Graph-Coloring Register
212          Allocation for Irregular Architectures" by Michael D. Smith
213          and Glen Holloway.  Major difference between the article
214          approach and approach used in IRA is that Smith's approach
215          takes register classes only from machine description and IRA
216          calculate register classes from intermediate code too
217          (e.g. an explicit usage of hard registers in RTL code for
218          parameter passing can result in creation of additional
219          register classes which contain or exclude the hard
220          registers).  That makes IRA approach useful for improving
221          coloring even for architectures with regular register files
222          and in fact some benchmarking shows the improvement for
223          regular class architectures is even bigger than for irregular
224          ones.  Another difference is that Smith's approach chooses
225          intersection of classes of all insn operands in which a given
226          pseudo occurs.  IRA can use bigger classes if it is still
227          more profitable than memory usage.
228
229        * Popping the allocnos from the stack and assigning them hard
230          registers.  If IRA can not assign a hard register to an
231          allocno and the allocno is coalesced, IRA undoes the
232          coalescing and puts the uncoalesced allocnos onto the stack in
233          the hope that some such allocnos will get a hard register
234          separately.  If IRA fails to assign hard register or memory
235          is more profitable for it, IRA spills the allocno.  IRA
236          assigns the allocno the hard-register with minimal full
237          allocation cost which reflects the cost of usage of the
238          hard-register for the allocno and cost of usage of the
239          hard-register for allocnos conflicting with given allocno.
240
241        * Chaitin-Briggs coloring assigns as many pseudos as possible
242          to hard registers.  After coloringh we try to improve
243          allocation with cost point of view.  We improve the
244          allocation by spilling some allocnos and assigning the freed
245          hard registers to other allocnos if it decreases the overall
246          allocation cost.
247
248        * After allono assigning in the region, IRA modifies the hard
249          register and memory costs for the corresponding allocnos in
250          the subregions to reflect the cost of possible loads, stores,
251          or moves on the border of the region and its subregions.
252          When default regional allocation algorithm is used
253          (-fira-algorithm=mixed), IRA just propagates the assignment
254          for allocnos if the register pressure in the region for the
255          corresponding pressure class is less than number of available
256          hard registers for given pressure class.
257
258      o Spill/restore code moving.  When IRA performs an allocation
259        by traversing regions in top-down order, it does not know what
260        happens below in the region tree.  Therefore, sometimes IRA
261        misses opportunities to perform a better allocation.  A simple
262        optimization tries to improve allocation in a region having
263        subregions and containing in another region.  If the
264        corresponding allocnos in the subregion are spilled, it spills
265        the region allocno if it is profitable.  The optimization
266        implements a simple iterative algorithm performing profitable
267        transformations while they are still possible.  It is fast in
268        practice, so there is no real need for a better time complexity
269        algorithm.
270
271      o Code change.  After coloring, two allocnos representing the
272        same pseudo-register outside and inside a region respectively
273        may be assigned to different locations (hard-registers or
274        memory).  In this case IRA creates and uses a new
275        pseudo-register inside the region and adds code to move allocno
276        values on the region's borders.  This is done during top-down
277        traversal of the regions (file ira-emit.c).  In some
278        complicated cases IRA can create a new allocno to move allocno
279        values (e.g. when a swap of values stored in two hard-registers
280        is needed).  At this stage, the new allocno is marked as
281        spilled.  IRA still creates the pseudo-register and the moves
282        on the region borders even when both allocnos were assigned to
283        the same hard-register.  If the reload pass spills a
284        pseudo-register for some reason, the effect will be smaller
285        because another allocno will still be in the hard-register.  In
286        most cases, this is better then spilling both allocnos.  If
287        reload does not change the allocation for the two
288        pseudo-registers, the trivial move will be removed by
289        post-reload optimizations.  IRA does not generate moves for
290        allocnos assigned to the same hard register when the default
291        regional allocation algorithm is used and the register pressure
292        in the region for the corresponding pressure class is less than
293        number of available hard registers for given pressure class.
294        IRA also does some optimizations to remove redundant stores and
295        to reduce code duplication on the region borders.
296
297      o Flattening internal representation.  After changing code, IRA
298        transforms its internal representation for several regions into
299        one region representation (file ira-build.c).  This process is
300        called IR flattening.  Such process is more complicated than IR
301        rebuilding would be, but is much faster.
302
303      o After IR flattening, IRA tries to assign hard registers to all
304        spilled allocnos.  This is impelemented by a simple and fast
305        priority coloring algorithm (see function
306        ira_reassign_conflict_allocnos::ira-color.c).  Here new allocnos
307        created during the code change pass can be assigned to hard
308        registers.
309
310      o At the end IRA calls the reload pass.  The reload pass
311        communicates with IRA through several functions in file
312        ira-color.c to improve its decisions in
313
314        * sharing stack slots for the spilled pseudos based on IRA info
315          about pseudo-register conflicts.
316
317        * reassigning hard-registers to all spilled pseudos at the end
318          of each reload iteration.
319
320        * choosing a better hard-register to spill based on IRA info
321          about pseudo-register live ranges and the register pressure
322          in places where the pseudo-register lives.
323
324    IRA uses a lot of data representing the target processors.  These
325    data are initilized in file ira.c.
326
327    If function has no loops (or the loops are ignored when
328    -fira-algorithm=CB is used), we have classic Chaitin-Briggs
329    coloring (only instead of separate pass of coalescing, we use hard
330    register preferencing).  In such case, IRA works much faster
331    because many things are not made (like IR flattening, the
332    spill/restore optimization, and the code change).
333
334    Literature is worth to read for better understanding the code:
335
336    o Preston Briggs, Keith D. Cooper, Linda Torczon.  Improvements to
337      Graph Coloring Register Allocation.
338
339    o David Callahan, Brian Koblenz.  Register allocation via
340      hierarchical graph coloring.
341
342    o Keith Cooper, Anshuman Dasgupta, Jason Eckhardt. Revisiting Graph
343      Coloring Register Allocation: A Study of the Chaitin-Briggs and
344      Callahan-Koblenz Algorithms.
345
346    o Guei-Yuan Lueh, Thomas Gross, and Ali-Reza Adl-Tabatabai. Global
347      Register Allocation Based on Graph Fusion.
348
349    o Michael D. Smith and Glenn Holloway.  Graph-Coloring Register
350      Allocation for Irregular Architectures
351
352    o Vladimir Makarov. The Integrated Register Allocator for GCC.
353
354    o Vladimir Makarov.  The top-down register allocator for irregular
355      register file architectures.
356
357 */
358
359
360 #include "config.h"
361 #include "system.h"
362 #include "coretypes.h"
363 #include "tm.h"
364 #include "regs.h"
365 #include "rtl.h"
366 #include "tm_p.h"
367 #include "target.h"
368 #include "flags.h"
369 #include "obstack.h"
370 #include "bitmap.h"
371 #include "hard-reg-set.h"
372 #include "basic-block.h"
373 #include "df.h"
374 #include "expr.h"
375 #include "recog.h"
376 #include "params.h"
377 #include "timevar.h"
378 #include "tree-pass.h"
379 #include "output.h"
380 #include "except.h"
381 #include "reload.h"
382 #include "diagnostic-core.h"
383 #include "integrate.h"
384 #include "ggc.h"
385 #include "ira-int.h"
386 #include "dce.h"
387
388
389 struct target_ira default_target_ira;
390 struct target_ira_int default_target_ira_int;
391 #if SWITCHABLE_TARGET
392 struct target_ira *this_target_ira = &default_target_ira;
393 struct target_ira_int *this_target_ira_int = &default_target_ira_int;
394 #endif
395
396 /* A modified value of flag `-fira-verbose' used internally.  */
397 int internal_flag_ira_verbose;
398
399 /* Dump file of the allocator if it is not NULL.  */
400 FILE *ira_dump_file;
401
402 /* The number of elements in the following array.  */
403 int ira_spilled_reg_stack_slots_num;
404
405 /* The following array contains info about spilled pseudo-registers
406    stack slots used in current function so far.  */
407 struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;
408
409 /* Correspondingly overall cost of the allocation, overall cost before
410    reload, cost of the allocnos assigned to hard-registers, cost of
411    the allocnos assigned to memory, cost of loads, stores and register
412    move insns generated for pseudo-register live range splitting (see
413    ira-emit.c).  */
414 int ira_overall_cost, overall_cost_before;
415 int ira_reg_cost, ira_mem_cost;
416 int ira_load_cost, ira_store_cost, ira_shuffle_cost;
417 int ira_move_loops_num, ira_additional_jumps_num;
418
419 /* All registers that can be eliminated.  */
420
421 HARD_REG_SET eliminable_regset;
422
423 /* Temporary hard reg set used for a different calculation.  */
424 static HARD_REG_SET temp_hard_regset;
425
426 \f
427
428 /* The function sets up the map IRA_REG_MODE_HARD_REGSET.  */
429 static void
430 setup_reg_mode_hard_regset (void)
431 {
432   int i, m, hard_regno;
433
434   for (m = 0; m < NUM_MACHINE_MODES; m++)
435     for (hard_regno = 0; hard_regno < FIRST_PSEUDO_REGISTER; hard_regno++)
436       {
437         CLEAR_HARD_REG_SET (ira_reg_mode_hard_regset[hard_regno][m]);
438         for (i = hard_regno_nregs[hard_regno][m] - 1; i >= 0; i--)
439           if (hard_regno + i < FIRST_PSEUDO_REGISTER)
440             SET_HARD_REG_BIT (ira_reg_mode_hard_regset[hard_regno][m],
441                               hard_regno + i);
442       }
443 }
444
445 \f
446 #define no_unit_alloc_regs \
447   (this_target_ira_int->x_no_unit_alloc_regs)
448
449 /* The function sets up the three arrays declared above.  */
450 static void
451 setup_class_hard_regs (void)
452 {
453   int cl, i, hard_regno, n;
454   HARD_REG_SET processed_hard_reg_set;
455
456   ira_assert (SHRT_MAX >= FIRST_PSEUDO_REGISTER);
457   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
458     {
459       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
460       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
461       CLEAR_HARD_REG_SET (processed_hard_reg_set);
462       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
463         {
464           ira_non_ordered_class_hard_regs[cl][i] = -1;
465           ira_class_hard_reg_index[cl][i] = -1;
466         }
467       for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
468         {
469 #ifdef REG_ALLOC_ORDER
470           hard_regno = reg_alloc_order[i];
471 #else
472           hard_regno = i;
473 #endif
474           if (TEST_HARD_REG_BIT (processed_hard_reg_set, hard_regno))
475             continue;
476           SET_HARD_REG_BIT (processed_hard_reg_set, hard_regno);
477           if (! TEST_HARD_REG_BIT (temp_hard_regset, hard_regno))
478             ira_class_hard_reg_index[cl][hard_regno] = -1;
479           else
480             {
481               ira_class_hard_reg_index[cl][hard_regno] = n;
482               ira_class_hard_regs[cl][n++] = hard_regno;
483             }
484         }
485       ira_class_hard_regs_num[cl] = n;
486       for (n = 0, i = 0; i < FIRST_PSEUDO_REGISTER; i++)
487         if (TEST_HARD_REG_BIT (temp_hard_regset, i))
488           ira_non_ordered_class_hard_regs[cl][n++] = i;
489       ira_assert (ira_class_hard_regs_num[cl] == n);
490     }
491 }
492
493 /* Set up IRA_AVAILABLE_CLASS_REGS.  */
494 static void
495 setup_available_class_regs (void)
496 {
497   int i, j;
498
499   memset (ira_available_class_regs, 0, sizeof (ira_available_class_regs));
500   for (i = 0; i < N_REG_CLASSES; i++)
501     {
502       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
503       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
504       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
505         if (TEST_HARD_REG_BIT (temp_hard_regset, j))
506           ira_available_class_regs[i]++;
507     }
508 }
509
510 /* Set up global variables defining info about hard registers for the
511    allocation.  These depend on USE_HARD_FRAME_P whose TRUE value means
512    that we can use the hard frame pointer for the allocation.  */
513 static void
514 setup_alloc_regs (bool use_hard_frame_p)
515 {
516 #ifdef ADJUST_REG_ALLOC_ORDER
517   ADJUST_REG_ALLOC_ORDER;
518 #endif
519   COPY_HARD_REG_SET (no_unit_alloc_regs, fixed_reg_set);
520   if (! use_hard_frame_p)
521     SET_HARD_REG_BIT (no_unit_alloc_regs, HARD_FRAME_POINTER_REGNUM);
522   setup_class_hard_regs ();
523   setup_available_class_regs ();
524 }
525
526 \f
527
528 #define alloc_reg_class_subclasses \
529   (this_target_ira_int->x_alloc_reg_class_subclasses)
530
531 /* Initialize the table of subclasses of each reg class.  */
532 static void
533 setup_reg_subclasses (void)
534 {
535   int i, j;
536   HARD_REG_SET temp_hard_regset2;
537
538   for (i = 0; i < N_REG_CLASSES; i++)
539     for (j = 0; j < N_REG_CLASSES; j++)
540       alloc_reg_class_subclasses[i][j] = LIM_REG_CLASSES;
541
542   for (i = 0; i < N_REG_CLASSES; i++)
543     {
544       if (i == (int) NO_REGS)
545         continue;
546
547       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
548       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
549       if (hard_reg_set_empty_p (temp_hard_regset))
550         continue;
551       for (j = 0; j < N_REG_CLASSES; j++)
552         if (i != j)
553           {
554             enum reg_class *p;
555
556             COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[j]);
557             AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
558             if (! hard_reg_set_subset_p (temp_hard_regset,
559                                          temp_hard_regset2))
560               continue;
561             p = &alloc_reg_class_subclasses[j][0];
562             while (*p != LIM_REG_CLASSES) p++;
563             *p = (enum reg_class) i;
564           }
565     }
566 }
567
568 \f
569
570 /* Set up IRA_MEMORY_MOVE_COST and IRA_MAX_MEMORY_MOVE_COST.  */
571 static void
572 setup_class_subset_and_memory_move_costs (void)
573 {
574   int cl, cl2, mode, cost;
575   HARD_REG_SET temp_hard_regset2;
576
577   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
578     ira_memory_move_cost[mode][NO_REGS][0]
579       = ira_memory_move_cost[mode][NO_REGS][1] = SHRT_MAX;
580   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
581     {
582       if (cl != (int) NO_REGS)
583         for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
584           {
585             ira_max_memory_move_cost[mode][cl][0]
586               = ira_memory_move_cost[mode][cl][0]
587               = memory_move_cost ((enum machine_mode) mode,
588                                   (reg_class_t) cl, false);
589             ira_max_memory_move_cost[mode][cl][1]
590               = ira_memory_move_cost[mode][cl][1]
591               = memory_move_cost ((enum machine_mode) mode,
592                                   (reg_class_t) cl, true);
593             /* Costs for NO_REGS are used in cost calculation on the
594                1st pass when the preferred register classes are not
595                known yet.  In this case we take the best scenario.  */
596             if (ira_memory_move_cost[mode][NO_REGS][0]
597                 > ira_memory_move_cost[mode][cl][0])
598               ira_max_memory_move_cost[mode][NO_REGS][0]
599                 = ira_memory_move_cost[mode][NO_REGS][0]
600                 = ira_memory_move_cost[mode][cl][0];
601             if (ira_memory_move_cost[mode][NO_REGS][1]
602                 > ira_memory_move_cost[mode][cl][1])
603               ira_max_memory_move_cost[mode][NO_REGS][1]
604                 = ira_memory_move_cost[mode][NO_REGS][1]
605                 = ira_memory_move_cost[mode][cl][1];
606           }
607     }
608   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
609     for (cl2 = (int) N_REG_CLASSES - 1; cl2 >= 0; cl2--)
610       {
611         COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
612         AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
613         COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
614         AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
615         ira_class_subset_p[cl][cl2]
616           = hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2);
617         if (! hard_reg_set_empty_p (temp_hard_regset2)
618             && hard_reg_set_subset_p (reg_class_contents[cl2],
619                                       reg_class_contents[cl]))
620           for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
621             {
622               cost = ira_memory_move_cost[mode][cl2][0];
623               if (cost > ira_max_memory_move_cost[mode][cl][0])
624                 ira_max_memory_move_cost[mode][cl][0] = cost;
625               cost = ira_memory_move_cost[mode][cl2][1];
626               if (cost > ira_max_memory_move_cost[mode][cl][1])
627                 ira_max_memory_move_cost[mode][cl][1] = cost;
628             }
629       }
630   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
631     for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
632       {
633         ira_memory_move_cost[mode][cl][0]
634           = ira_max_memory_move_cost[mode][cl][0];
635         ira_memory_move_cost[mode][cl][1]
636           = ira_max_memory_move_cost[mode][cl][1];
637       }
638   setup_reg_subclasses ();
639 }
640
641 \f
642
643 /* Define the following macro if allocation through malloc if
644    preferable.  */
645 #define IRA_NO_OBSTACK
646
647 #ifndef IRA_NO_OBSTACK
648 /* Obstack used for storing all dynamic data (except bitmaps) of the
649    IRA.  */
650 static struct obstack ira_obstack;
651 #endif
652
653 /* Obstack used for storing all bitmaps of the IRA.  */
654 static struct bitmap_obstack ira_bitmap_obstack;
655
656 /* Allocate memory of size LEN for IRA data.  */
657 void *
658 ira_allocate (size_t len)
659 {
660   void *res;
661
662 #ifndef IRA_NO_OBSTACK
663   res = obstack_alloc (&ira_obstack, len);
664 #else
665   res = xmalloc (len);
666 #endif
667   return res;
668 }
669
670 /* Free memory ADDR allocated for IRA data.  */
671 void
672 ira_free (void *addr ATTRIBUTE_UNUSED)
673 {
674 #ifndef IRA_NO_OBSTACK
675   /* do nothing */
676 #else
677   free (addr);
678 #endif
679 }
680
681
682 /* Allocate and returns bitmap for IRA.  */
683 bitmap
684 ira_allocate_bitmap (void)
685 {
686   return BITMAP_ALLOC (&ira_bitmap_obstack);
687 }
688
689 /* Free bitmap B allocated for IRA.  */
690 void
691 ira_free_bitmap (bitmap b ATTRIBUTE_UNUSED)
692 {
693   /* do nothing */
694 }
695
696 \f
697
698 /* Output information about allocation of all allocnos (except for
699    caps) into file F.  */
700 void
701 ira_print_disposition (FILE *f)
702 {
703   int i, n, max_regno;
704   ira_allocno_t a;
705   basic_block bb;
706
707   fprintf (f, "Disposition:");
708   max_regno = max_reg_num ();
709   for (n = 0, i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
710     for (a = ira_regno_allocno_map[i];
711          a != NULL;
712          a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
713       {
714         if (n % 4 == 0)
715           fprintf (f, "\n");
716         n++;
717         fprintf (f, " %4d:r%-4d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
718         if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
719           fprintf (f, "b%-3d", bb->index);
720         else
721           fprintf (f, "l%-3d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
722         if (ALLOCNO_HARD_REGNO (a) >= 0)
723           fprintf (f, " %3d", ALLOCNO_HARD_REGNO (a));
724         else
725           fprintf (f, " mem");
726       }
727   fprintf (f, "\n");
728 }
729
730 /* Outputs information about allocation of all allocnos into
731    stderr.  */
732 void
733 ira_debug_disposition (void)
734 {
735   ira_print_disposition (stderr);
736 }
737
738 \f
739
740 /* Set up ira_stack_reg_pressure_class which is the biggest pressure
741    register class containing stack registers or NO_REGS if there are
742    no stack registers.  To find this class, we iterate through all
743    register pressure classes and choose the first register pressure
744    class containing all the stack registers and having the biggest
745    size.  */
746 static void
747 setup_stack_reg_pressure_class (void)
748 {
749   ira_stack_reg_pressure_class = NO_REGS;
750 #ifdef STACK_REGS
751   {
752     int i, best, size;
753     enum reg_class cl;
754     HARD_REG_SET temp_hard_regset2;
755
756     CLEAR_HARD_REG_SET (temp_hard_regset);
757     for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
758       SET_HARD_REG_BIT (temp_hard_regset, i);
759     best = 0;
760     for (i = 0; i < ira_pressure_classes_num; i++)
761       {
762         cl = ira_pressure_classes[i];
763         COPY_HARD_REG_SET (temp_hard_regset2, temp_hard_regset);
764         AND_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
765         size = hard_reg_set_size (temp_hard_regset2);
766         if (best < size)
767           {
768             best = size;
769             ira_stack_reg_pressure_class = cl;
770           }
771       }
772   }
773 #endif
774 }
775
776 /* Find pressure classes which are register classes for which we
777    calculate register pressure in IRA, register pressure sensitive
778    insn scheduling, and register pressure sensitive loop invariant
779    motion.
780
781    To make register pressure calculation easy, we always use
782    non-intersected register pressure classes.  A move of hard
783    registers from one register pressure class is not more expensive
784    than load and store of the hard registers.  Most likely an allocno
785    class will be a subset of a register pressure class and in many
786    cases a register pressure class.  That makes usage of register
787    pressure classes a good approximation to find a high register
788    pressure.  */
789 static void
790 setup_pressure_classes (void)
791 {
792   int cost, i, n, curr;
793   int cl, cl2;
794   enum reg_class pressure_classes[N_REG_CLASSES];
795   int m;
796   HARD_REG_SET temp_hard_regset2;
797   bool insert_p;
798
799   n = 0;
800   for (cl = 0; cl < N_REG_CLASSES; cl++)
801     {
802       if (ira_available_class_regs[cl] == 0)
803         continue;
804       if (ira_available_class_regs[cl] != 1
805           /* A register class without subclasses may contain a few
806              hard registers and movement between them is costly
807              (e.g. SPARC FPCC registers).  We still should consider it
808              as a candidate for a pressure class.  */
809           && alloc_reg_class_subclasses[cl][0] != LIM_REG_CLASSES)
810         {
811           /* Check that the moves between any hard registers of the
812              current class are not more expensive for a legal mode
813              than load/store of the hard registers of the current
814              class.  Such class is a potential candidate to be a
815              register pressure class.  */
816           for (m = 0; m < NUM_MACHINE_MODES; m++)
817             {
818               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
819               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
820               AND_COMPL_HARD_REG_SET (temp_hard_regset,
821                                       ira_prohibited_class_mode_regs[cl][m]);
822               if (hard_reg_set_empty_p (temp_hard_regset))
823                 continue;
824               ira_init_register_move_cost_if_necessary ((enum machine_mode) m);
825               cost = ira_register_move_cost[m][cl][cl];
826               if (cost <= ira_max_memory_move_cost[m][cl][1]
827                   || cost <= ira_max_memory_move_cost[m][cl][0])
828                 break;
829             }
830           if (m >= NUM_MACHINE_MODES)
831             continue;
832         }
833       curr = 0;
834       insert_p = true;
835       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
836       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
837       /* Remove so far added pressure classes which are subset of the
838          current candidate class.  Prefer GENERAL_REGS as a pressure
839          register class to another class containing the same
840          allocatable hard registers.  We do this because machine
841          dependent cost hooks might give wrong costs for the latter
842          class but always give the right cost for the former class
843          (GENERAL_REGS).  */
844       for (i = 0; i < n; i++)
845         {
846           cl2 = pressure_classes[i];
847           COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl2]);
848           AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
849           if (hard_reg_set_subset_p (temp_hard_regset, temp_hard_regset2)
850               && (! hard_reg_set_equal_p (temp_hard_regset, temp_hard_regset2)
851                   || cl2 == (int) GENERAL_REGS))
852             {
853               pressure_classes[curr++] = (enum reg_class) cl2;
854               insert_p = false;
855               continue;
856             }
857           if (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset)
858               && (! hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset)
859                   || cl == (int) GENERAL_REGS))
860             continue;
861           if (hard_reg_set_equal_p (temp_hard_regset2, temp_hard_regset))
862             insert_p = false;
863           pressure_classes[curr++] = (enum reg_class) cl2;
864         }
865       /* If the current candidate is a subset of a so far added
866          pressure class, don't add it to the list of the pressure
867          classes.  */
868       if (insert_p)
869         pressure_classes[curr++] = (enum reg_class) cl;
870       n = curr;
871     }
872 #ifdef ENABLE_IRA_CHECKING
873   {
874     HARD_REG_SET ignore_hard_regs;
875
876     /* Check pressure classes correctness: here we check that hard
877        registers from all register pressure classes contains all hard
878        registers available for the allocation.  */
879     CLEAR_HARD_REG_SET (temp_hard_regset);
880     CLEAR_HARD_REG_SET (temp_hard_regset2);
881     COPY_HARD_REG_SET (ignore_hard_regs, no_unit_alloc_regs);
882     for (cl = 0; cl < LIM_REG_CLASSES; cl++)
883       {
884         /* For some targets (like MIPS with MD_REGS), there are some
885            classes with hard registers available for allocation but
886            not able to hold value of any mode.  */
887         for (m = 0; m < NUM_MACHINE_MODES; m++)
888           if (contains_reg_of_mode[cl][m])
889             break;
890         if (m >= NUM_MACHINE_MODES)
891           {
892             IOR_HARD_REG_SET (ignore_hard_regs, reg_class_contents[cl]);
893             continue;
894           }
895         for (i = 0; i < n; i++)
896           if ((int) pressure_classes[i] == cl)
897             break;
898         IOR_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
899         if (i < n)
900           IOR_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
901       }
902     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
903       /* Some targets (like SPARC with ICC reg) have alocatable regs
904          for which no reg class is defined.  */
905       if (REGNO_REG_CLASS (i) == NO_REGS)
906         SET_HARD_REG_BIT (ignore_hard_regs, i);
907     AND_COMPL_HARD_REG_SET (temp_hard_regset, ignore_hard_regs);
908     AND_COMPL_HARD_REG_SET (temp_hard_regset2, ignore_hard_regs);
909     ira_assert (hard_reg_set_subset_p (temp_hard_regset2, temp_hard_regset));
910   }
911 #endif
912   ira_pressure_classes_num = 0;
913   for (i = 0; i < n; i++)
914     {
915       cl = (int) pressure_classes[i];
916       ira_reg_pressure_class_p[cl] = true;
917       ira_pressure_classes[ira_pressure_classes_num++] = (enum reg_class) cl;
918     }
919   setup_stack_reg_pressure_class ();
920 }
921
922 /* Set up IRA_ALLOCNO_CLASSES, IRA_ALLOCNO_CLASSES_NUM,
923    IRA_IMPORTANT_CLASSES, and IRA_IMPORTANT_CLASSES_NUM.
924
925    Target may have many subtargets and not all target hard regiters can
926    be used for allocation, e.g. x86 port in 32-bit mode can not use
927    hard registers introduced in x86-64 like r8-r15).  Some classes
928    might have the same allocatable hard registers, e.g.  INDEX_REGS
929    and GENERAL_REGS in x86 port in 32-bit mode.  To decrease different
930    calculations efforts we introduce allocno classes which contain
931    unique non-empty sets of allocatable hard-registers.
932
933    Pseudo class cost calculation in ira-costs.c is very expensive.
934    Therefore we are trying to decrease number of classes involved in
935    such calculation.  Register classes used in the cost calculation
936    are called important classes.  They are allocno classes and other
937    non-empty classes whose allocatable hard register sets are inside
938    of an allocno class hard register set.  From the first sight, it
939    looks like that they are just allocno classes.  It is not true.  In
940    example of x86-port in 32-bit mode, allocno classes will contain
941    GENERAL_REGS but not LEGACY_REGS (because allocatable hard
942    registers are the same for the both classes).  The important
943    classes will contain GENERAL_REGS and LEGACY_REGS.  It is done
944    because a machine description insn constraint may refers for
945    LEGACY_REGS and code in ira-costs.c is mostly base on investigation
946    of the insn constraints.  */
947 static void
948 setup_allocno_and_important_classes (void)
949 {
950   int i, j, n, cl;
951   bool set_p;
952   HARD_REG_SET temp_hard_regset2;
953   static enum reg_class classes[LIM_REG_CLASSES + 1];
954
955   n = 0;
956   /* Collect classes which contain unique sets of allocatable hard
957      registers.  Prefer GENERAL_REGS to other classes containing the
958      same set of hard registers.  */
959   for (i = 0; i < LIM_REG_CLASSES; i++)
960     {
961       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[i]);
962       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
963       for (j = 0; j < n; j++)
964         {
965           cl = classes[j];
966           COPY_HARD_REG_SET (temp_hard_regset2, reg_class_contents[cl]);
967           AND_COMPL_HARD_REG_SET (temp_hard_regset2,
968                                   no_unit_alloc_regs);
969           if (hard_reg_set_equal_p (temp_hard_regset,
970                                     temp_hard_regset2))
971             break;
972         }
973       if (j >= n)
974         classes[n++] = (enum reg_class) i;
975       else if (i == GENERAL_REGS)
976         /* Prefer general regs.  For i386 example, it means that
977            we prefer GENERAL_REGS over INDEX_REGS or LEGACY_REGS
978            (all of them consists of the same available hard
979            registers).  */
980         classes[j] = (enum reg_class) i;
981     }
982   classes[n] = LIM_REG_CLASSES;
983
984   /* Set up classes which can be used for allocnos as classes
985      conatining non-empty unique sets of allocatable hard
986      registers.  */
987   ira_allocno_classes_num = 0;
988   for (i = 0; (cl = classes[i]) != LIM_REG_CLASSES; i++)
989     {
990       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
991       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
992       if (hard_reg_set_empty_p (temp_hard_regset))
993         continue;
994       ira_allocno_classes[ira_allocno_classes_num++] = (enum reg_class) cl;
995     }
996   ira_important_classes_num = 0;
997   /* Add non-allocno classes containing to non-empty set of
998      allocatable hard regs.  */
999   for (cl = 0; cl < N_REG_CLASSES; cl++)
1000     {
1001       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1002       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1003       if (! hard_reg_set_empty_p (temp_hard_regset))
1004         {
1005           set_p = false;
1006           for (j = 0; j < ira_allocno_classes_num; j++)
1007             {
1008               COPY_HARD_REG_SET (temp_hard_regset2,
1009                                  reg_class_contents[ira_allocno_classes[j]]);
1010               AND_COMPL_HARD_REG_SET (temp_hard_regset2, no_unit_alloc_regs);
1011               if ((enum reg_class) cl == ira_allocno_classes[j])
1012                 break;
1013               else if (hard_reg_set_subset_p (temp_hard_regset,
1014                                               temp_hard_regset2))
1015                 set_p = true;
1016             }
1017           if (set_p && j >= ira_allocno_classes_num)
1018             ira_important_classes[ira_important_classes_num++]
1019               = (enum reg_class) cl;
1020         }
1021     }
1022   /* Now add allocno classes to the important classes.  */
1023   for (j = 0; j < ira_allocno_classes_num; j++)
1024     ira_important_classes[ira_important_classes_num++]
1025       = ira_allocno_classes[j];
1026   for (cl = 0; cl < N_REG_CLASSES; cl++)
1027     {
1028       ira_reg_allocno_class_p[cl] = false;
1029       ira_reg_pressure_class_p[cl] = false;
1030     }
1031   for (j = 0; j < ira_allocno_classes_num; j++)
1032     ira_reg_allocno_class_p[ira_allocno_classes[j]] = true;
1033   setup_pressure_classes ();
1034 }
1035
1036 /* Setup translation in CLASS_TRANSLATE of all classes into a class
1037    given by array CLASSES of length CLASSES_NUM.  The function is used
1038    make translation any reg class to an allocno class or to an
1039    pressure class.  This translation is necessary for some
1040    calculations when we can use only allocno or pressure classes and
1041    such translation represents an approximate representation of all
1042    classes.
1043
1044    The translation in case when allocatable hard register set of a
1045    given class is subset of allocatable hard register set of a class
1046    in CLASSES is pretty simple.  We use smallest classes from CLASSES
1047    containing a given class.  If allocatable hard register set of a
1048    given class is not a subset of any corresponding set of a class
1049    from CLASSES, we use the cheapest (with load/store point of view)
1050    class from CLASSES whose set intersects with given class set */
1051 static void
1052 setup_class_translate_array (enum reg_class *class_translate,
1053                              int classes_num, enum reg_class *classes)
1054 {
1055   int cl, mode;
1056   enum reg_class aclass, best_class, *cl_ptr;
1057   int i, cost, min_cost, best_cost;
1058
1059   for (cl = 0; cl < N_REG_CLASSES; cl++)
1060     class_translate[cl] = NO_REGS;
1061
1062   for (i = 0; i < classes_num; i++)
1063     {
1064       aclass = classes[i];
1065       for (cl_ptr = &alloc_reg_class_subclasses[aclass][0];
1066            (cl = *cl_ptr) != LIM_REG_CLASSES;
1067            cl_ptr++)
1068         if (class_translate[cl] == NO_REGS)
1069           class_translate[cl] = aclass;
1070       class_translate[aclass] = aclass;
1071     }
1072   /* For classes which are not fully covered by one of given classes
1073      (in other words covered by more one given class), use the
1074      cheapest class.  */
1075   for (cl = 0; cl < N_REG_CLASSES; cl++)
1076     {
1077       if (cl == NO_REGS || class_translate[cl] != NO_REGS)
1078         continue;
1079       best_class = NO_REGS;
1080       best_cost = INT_MAX;
1081       for (i = 0; i < classes_num; i++)
1082         {
1083           aclass = classes[i];
1084           COPY_HARD_REG_SET (temp_hard_regset,
1085                              reg_class_contents[aclass]);
1086           AND_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl]);
1087           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1088           if (! hard_reg_set_empty_p (temp_hard_regset))
1089             {
1090               min_cost = INT_MAX;
1091               for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1092                 {
1093                   cost = (ira_memory_move_cost[mode][cl][0]
1094                           + ira_memory_move_cost[mode][cl][1]);
1095                   if (min_cost > cost)
1096                     min_cost = cost;
1097                 }
1098               if (best_class == NO_REGS || best_cost > min_cost)
1099                 {
1100                   best_class = aclass;
1101                   best_cost = min_cost;
1102                 }
1103             }
1104         }
1105       class_translate[cl] = best_class;
1106     }
1107 }
1108
1109 /* Set up array IRA_ALLOCNO_CLASS_TRANSLATE and
1110    IRA_PRESSURE_CLASS_TRANSLATE.  */
1111 static void
1112 setup_class_translate (void)
1113 {
1114   setup_class_translate_array (ira_allocno_class_translate,
1115                                ira_allocno_classes_num, ira_allocno_classes);
1116   setup_class_translate_array (ira_pressure_class_translate,
1117                                ira_pressure_classes_num, ira_pressure_classes);
1118 }
1119
1120 /* Order numbers of allocno classes in original target allocno class
1121    array, -1 for non-allocno classes.  */
1122 static int allocno_class_order[N_REG_CLASSES];
1123
1124 /* The function used to sort the important classes.  */
1125 static int
1126 comp_reg_classes_func (const void *v1p, const void *v2p)
1127 {
1128   enum reg_class cl1 = *(const enum reg_class *) v1p;
1129   enum reg_class cl2 = *(const enum reg_class *) v2p;
1130   enum reg_class tcl1, tcl2;
1131   int diff;
1132
1133   tcl1 = ira_allocno_class_translate[cl1];
1134   tcl2 = ira_allocno_class_translate[cl2];
1135   if (tcl1 != NO_REGS && tcl2 != NO_REGS
1136       && (diff = allocno_class_order[tcl1] - allocno_class_order[tcl2]) != 0)
1137     return diff;
1138   return (int) cl1 - (int) cl2;
1139 }
1140
1141 /* For correct work of function setup_reg_class_relation we need to
1142    reorder important classes according to the order of their allocno
1143    classes.  It places important classes containing the same
1144    allocatable hard register set adjacent to each other and allocno
1145    class with the allocatable hard register set right after the other
1146    important classes with the same set.
1147
1148    In example from comments of function
1149    setup_allocno_and_important_classes, it places LEGACY_REGS and
1150    GENERAL_REGS close to each other and GENERAL_REGS is after
1151    LEGACY_REGS.  */
1152 static void
1153 reorder_important_classes (void)
1154 {
1155   int i;
1156
1157   for (i = 0; i < N_REG_CLASSES; i++)
1158     allocno_class_order[i] = -1;
1159   for (i = 0; i < ira_allocno_classes_num; i++)
1160     allocno_class_order[ira_allocno_classes[i]] = i;
1161   qsort (ira_important_classes, ira_important_classes_num,
1162          sizeof (enum reg_class), comp_reg_classes_func);
1163   for (i = 0; i < ira_important_classes_num; i++)
1164     ira_important_class_nums[ira_important_classes[i]] = i;
1165 }
1166
1167 /* Set up IRA_REG_CLASS_SUBUNION, IRA_REG_CLASS_SUPERUNION,
1168    IRA_REG_CLASS_SUPER_CLASSES, IRA_REG_CLASSES_INTERSECT, and
1169    IRA_REG_CLASSES_INTERSECT_P.  For the meaning of the relations,
1170    please see corresponding comments in ira-int.h.  */
1171 static void
1172 setup_reg_class_relations (void)
1173 {
1174   int i, cl1, cl2, cl3;
1175   HARD_REG_SET intersection_set, union_set, temp_set2;
1176   bool important_class_p[N_REG_CLASSES];
1177
1178   memset (important_class_p, 0, sizeof (important_class_p));
1179   for (i = 0; i < ira_important_classes_num; i++)
1180     important_class_p[ira_important_classes[i]] = true;
1181   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1182     {
1183       ira_reg_class_super_classes[cl1][0] = LIM_REG_CLASSES;
1184       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1185         {
1186           ira_reg_classes_intersect_p[cl1][cl2] = false;
1187           ira_reg_class_intersect[cl1][cl2] = NO_REGS;
1188           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1189           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1190           COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
1191           AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1192           if (hard_reg_set_empty_p (temp_hard_regset)
1193               && hard_reg_set_empty_p (temp_set2))
1194             {
1195               /* The both classes have no allocatable hard registers
1196                  -- take all class hard registers into account and use
1197                  reg_class_subunion and reg_class_superunion.  */
1198               for (i = 0;; i++)
1199                 {
1200                   cl3 = reg_class_subclasses[cl1][i];
1201                   if (cl3 == LIM_REG_CLASSES)
1202                     break;
1203                   if (reg_class_subset_p (ira_reg_class_intersect[cl1][cl2],
1204                                           (enum reg_class) cl3))
1205                     ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1206                 }
1207               ira_reg_class_subunion[cl1][cl2] = reg_class_subunion[cl1][cl2];
1208               ira_reg_class_superunion[cl1][cl2] = reg_class_superunion[cl1][cl2];
1209               continue;
1210             }
1211           ira_reg_classes_intersect_p[cl1][cl2]
1212             = hard_reg_set_intersect_p (temp_hard_regset, temp_set2);
1213           if (important_class_p[cl1] && important_class_p[cl2]
1214               && hard_reg_set_subset_p (temp_hard_regset, temp_set2))
1215             {
1216               /* CL1 and CL2 are important classes and CL1 allocatable
1217                  hard register set is inside of CL2 allocatable hard
1218                  registers -- make CL1 a superset of CL2.  */
1219               enum reg_class *p;
1220
1221               p = &ira_reg_class_super_classes[cl1][0];
1222               while (*p != LIM_REG_CLASSES)
1223                 p++;
1224               *p++ = (enum reg_class) cl2;
1225               *p = LIM_REG_CLASSES;
1226             }
1227           ira_reg_class_subunion[cl1][cl2] = NO_REGS;
1228           ira_reg_class_superunion[cl1][cl2] = NO_REGS;
1229           COPY_HARD_REG_SET (intersection_set, reg_class_contents[cl1]);
1230           AND_HARD_REG_SET (intersection_set, reg_class_contents[cl2]);
1231           AND_COMPL_HARD_REG_SET (intersection_set, no_unit_alloc_regs);
1232           COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
1233           IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
1234           AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
1235           for (i = 0; i < ira_important_classes_num; i++)
1236             {
1237               cl3 = ira_important_classes[i];
1238               COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
1239               AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1240               if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
1241                 {
1242                   /* CL3 allocatable hard register set is inside of
1243                      intersection of allocatable hard register sets
1244                      of CL1 and CL2.  */
1245                   COPY_HARD_REG_SET
1246                     (temp_set2,
1247                      reg_class_contents[(int)
1248                                         ira_reg_class_intersect[cl1][cl2]]);
1249                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1250                   if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1251                       /* If the allocatable hard register sets are the
1252                          same, prefer GENERAL_REGS or the smallest
1253                          class for debugging purposes.  */
1254                       || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
1255                           && (cl3 == GENERAL_REGS
1256                               || (ira_reg_class_intersect[cl1][cl2] != GENERAL_REGS
1257                                   && hard_reg_set_subset_p
1258                                      (reg_class_contents[cl3],
1259                                       reg_class_contents
1260                                       [(int) ira_reg_class_intersect[cl1][cl2]])))))
1261                     ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
1262                 }
1263               if (hard_reg_set_subset_p (temp_hard_regset, union_set))
1264                 {
1265                   /* CL3 allocatbale hard register set is inside of
1266                      union of allocatable hard register sets of CL1
1267                      and CL2.  */
1268                   COPY_HARD_REG_SET
1269                     (temp_set2,
1270                      reg_class_contents[(int) ira_reg_class_subunion[cl1][cl2]]);
1271                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1272                   if (ira_reg_class_subunion[cl1][cl2] == NO_REGS
1273                       || (hard_reg_set_subset_p (temp_set2, temp_hard_regset)
1274                           
1275                           && (! hard_reg_set_equal_p (temp_set2,
1276                                                       temp_hard_regset)
1277                               || cl3 == GENERAL_REGS
1278                               /* If the allocatable hard register sets are the
1279                                  same, prefer GENERAL_REGS or the smallest
1280                                  class for debugging purposes.  */
1281                               || (ira_reg_class_subunion[cl1][cl2] != GENERAL_REGS
1282                                   && hard_reg_set_subset_p
1283                                      (reg_class_contents[cl3],
1284                                       reg_class_contents
1285                                       [(int) ira_reg_class_subunion[cl1][cl2]])))))
1286                     ira_reg_class_subunion[cl1][cl2] = (enum reg_class) cl3;
1287                 }
1288               if (hard_reg_set_subset_p (union_set, temp_hard_regset))
1289                 {
1290                   /* CL3 allocatable hard register set contains union
1291                      of allocatable hard register sets of CL1 and
1292                      CL2.  */
1293                   COPY_HARD_REG_SET
1294                     (temp_set2,
1295                      reg_class_contents[(int) ira_reg_class_superunion[cl1][cl2]]);
1296                   AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
1297                   if (ira_reg_class_superunion[cl1][cl2] == NO_REGS
1298                       || (hard_reg_set_subset_p (temp_hard_regset, temp_set2)
1299
1300                           && (! hard_reg_set_equal_p (temp_set2,
1301                                                       temp_hard_regset)
1302                               || cl3 == GENERAL_REGS
1303                               /* If the allocatable hard register sets are the
1304                                  same, prefer GENERAL_REGS or the smallest
1305                                  class for debugging purposes.  */
1306                               || (ira_reg_class_superunion[cl1][cl2] != GENERAL_REGS
1307                                   && hard_reg_set_subset_p
1308                                      (reg_class_contents[cl3],
1309                                       reg_class_contents
1310                                       [(int) ira_reg_class_superunion[cl1][cl2]])))))
1311                     ira_reg_class_superunion[cl1][cl2] = (enum reg_class) cl3;
1312                 }
1313             }
1314         }
1315     }
1316 }
1317
1318 /* Output all possible allocno classes and the translation map into
1319    file F.  */
1320 static void
1321 print_classes (FILE *f, bool pressure_p)
1322 {
1323   int classes_num = (pressure_p
1324                      ? ira_pressure_classes_num : ira_allocno_classes_num);
1325   enum reg_class *classes = (pressure_p
1326                              ? ira_pressure_classes : ira_allocno_classes);
1327   enum reg_class *class_translate = (pressure_p
1328                                      ? ira_pressure_class_translate
1329                                      : ira_allocno_class_translate);
1330   static const char *const reg_class_names[] = REG_CLASS_NAMES;
1331   int i;
1332
1333   fprintf (f, "%s classes:\n", pressure_p ? "Pressure" : "Allocno");
1334   for (i = 0; i < classes_num; i++)
1335     fprintf (f, " %s", reg_class_names[classes[i]]);
1336   fprintf (f, "\nClass translation:\n");
1337   for (i = 0; i < N_REG_CLASSES; i++)
1338     fprintf (f, " %s -> %s\n", reg_class_names[i],
1339              reg_class_names[class_translate[i]]);
1340 }
1341
1342 /* Output all possible allocno and translation classes and the
1343    translation maps into stderr.  */
1344 void
1345 ira_debug_allocno_classes (void)
1346 {
1347   print_classes (stderr, false);
1348   print_classes (stderr, true);
1349 }
1350
1351 /* Set up different arrays concerning class subsets, allocno and
1352    important classes.  */
1353 static void
1354 find_reg_classes (void)
1355 {
1356   setup_allocno_and_important_classes ();
1357   setup_class_translate ();
1358   reorder_important_classes ();
1359   setup_reg_class_relations ();
1360 }
1361
1362 \f
1363
1364 /* Set up the array above.  */
1365 static void
1366 setup_hard_regno_aclass (void)
1367 {
1368   int i;
1369
1370   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1371     {
1372 #if 1
1373       ira_hard_regno_allocno_class[i]
1374         = (TEST_HARD_REG_BIT (no_unit_alloc_regs, i)
1375            ? NO_REGS
1376            : ira_allocno_class_translate[REGNO_REG_CLASS (i)]);
1377 #else
1378       int j;
1379       enum reg_class cl;
1380       ira_hard_regno_allocno_class[i] = NO_REGS;
1381       for (j = 0; j < ira_allocno_classes_num; j++)
1382         {
1383           cl = ira_allocno_classes[j];
1384           if (ira_class_hard_reg_index[cl][i] >= 0)
1385             {
1386               ira_hard_regno_allocno_class[i] = cl;
1387               break;
1388             }
1389         }
1390 #endif
1391     }
1392 }
1393
1394 \f
1395
1396 /* Form IRA_REG_CLASS_MAX_NREGS and IRA_REG_CLASS_MIN_NREGS maps.  */
1397 static void
1398 setup_reg_class_nregs (void)
1399 {
1400   int i, cl, cl2, m;
1401
1402   for (m = 0; m < MAX_MACHINE_MODE; m++)
1403     {
1404       for (cl = 0; cl < N_REG_CLASSES; cl++)
1405         ira_reg_class_max_nregs[cl][m]
1406           = ira_reg_class_min_nregs[cl][m]
1407           = targetm.class_max_nregs ((reg_class_t) cl, (enum machine_mode) m);
1408       for (cl = 0; cl < N_REG_CLASSES; cl++)
1409         for (i = 0;
1410              (cl2 = alloc_reg_class_subclasses[cl][i]) != LIM_REG_CLASSES;
1411              i++)
1412           if (ira_reg_class_min_nregs[cl2][m]
1413               < ira_reg_class_min_nregs[cl][m])
1414             ira_reg_class_min_nregs[cl][m] = ira_reg_class_min_nregs[cl2][m];
1415     }
1416 }
1417
1418 \f
1419
1420 /* Set up IRA_PROHIBITED_CLASS_MODE_REGS.  */
1421 static void
1422 setup_prohibited_class_mode_regs (void)
1423 {
1424   int j, k, hard_regno, cl;
1425
1426   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1427     {
1428       for (j = 0; j < NUM_MACHINE_MODES; j++)
1429         {
1430           CLEAR_HARD_REG_SET (ira_prohibited_class_mode_regs[cl][j]);
1431           for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1432             {
1433               hard_regno = ira_class_hard_regs[cl][k];
1434               if (! HARD_REGNO_MODE_OK (hard_regno, (enum machine_mode) j))
1435                 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1436                                   hard_regno);
1437             }
1438         }
1439     }
1440 }
1441
1442 /* Clarify IRA_PROHIBITED_CLASS_MODE_REGS by excluding hard registers
1443    spanning from one register pressure class to another one.  It is
1444    called after defining the pressure classes.  */
1445 static void
1446 clarify_prohibited_class_mode_regs (void)
1447 {
1448   int j, k, hard_regno, cl, pclass, nregs;
1449
1450   for (cl = (int) N_REG_CLASSES - 1; cl >= 0; cl--)
1451     for (j = 0; j < NUM_MACHINE_MODES; j++)
1452       for (k = ira_class_hard_regs_num[cl] - 1; k >= 0; k--)
1453         {
1454           hard_regno = ira_class_hard_regs[cl][k];
1455           if (TEST_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j], hard_regno))
1456             continue;
1457           nregs = hard_regno_nregs[hard_regno][j];
1458           if (hard_regno + nregs > FIRST_PSEUDO_REGISTER)
1459             {
1460               SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1461                                 hard_regno);
1462                continue;
1463             }
1464           pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1465           for (nregs-- ;nregs >= 0; nregs--)
1466             if (((enum reg_class) pclass
1467                  != ira_pressure_class_translate[REGNO_REG_CLASS
1468                                                  (hard_regno + nregs)]))
1469               {
1470                 SET_HARD_REG_BIT (ira_prohibited_class_mode_regs[cl][j],
1471                                   hard_regno);
1472                 break;
1473               }
1474         }
1475 }
1476
1477 \f
1478
1479 /* Allocate and initialize IRA_REGISTER_MOVE_COST,
1480    IRA_MAX_REGISTER_MOVE_COST, IRA_MAY_MOVE_IN_COST,
1481    IRA_MAY_MOVE_OUT_COST, IRA_MAX_MAY_MOVE_IN_COST, and
1482    IRA_MAX_MAY_MOVE_OUT_COST for MODE if it is not done yet.  */
1483 void
1484 ira_init_register_move_cost (enum machine_mode mode)
1485 {
1486   int cl1, cl2, cl3;
1487
1488   ira_assert (ira_register_move_cost[mode] == NULL
1489               && ira_max_register_move_cost[mode] == NULL
1490               && ira_may_move_in_cost[mode] == NULL
1491               && ira_may_move_out_cost[mode] == NULL
1492               && ira_max_may_move_in_cost[mode] == NULL
1493               && ira_max_may_move_out_cost[mode] == NULL);
1494   if (move_cost[mode] == NULL)
1495     init_move_cost (mode);
1496   ira_register_move_cost[mode] = move_cost[mode];
1497   /* Don't use ira_allocate because the tables exist out of scope of a
1498      IRA call.  */
1499   ira_max_register_move_cost[mode]
1500     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1501   memcpy (ira_max_register_move_cost[mode], ira_register_move_cost[mode],
1502           sizeof (move_table) * N_REG_CLASSES);
1503   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1504     {
1505       /* Some subclasses are to small to have enough registers to hold
1506          a value of MODE.  Just ignore them.  */
1507       if (ira_reg_class_max_nregs[cl1][mode] > ira_available_class_regs[cl1])
1508         continue;
1509       COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
1510       AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1511       if (hard_reg_set_empty_p (temp_hard_regset))
1512         continue;
1513       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1514         if (hard_reg_set_subset_p (reg_class_contents[cl1],
1515                                    reg_class_contents[cl2]))
1516           for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
1517             {
1518               if (ira_max_register_move_cost[mode][cl2][cl3]
1519                   < ira_register_move_cost[mode][cl1][cl3])
1520                 ira_max_register_move_cost[mode][cl2][cl3]
1521                   = ira_register_move_cost[mode][cl1][cl3];
1522               if (ira_max_register_move_cost[mode][cl3][cl2]
1523                   < ira_register_move_cost[mode][cl3][cl1])
1524                 ira_max_register_move_cost[mode][cl3][cl2]
1525                   = ira_register_move_cost[mode][cl3][cl1];
1526             }
1527     }
1528   ira_may_move_in_cost[mode]
1529     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1530   memcpy (ira_may_move_in_cost[mode], may_move_in_cost[mode],
1531           sizeof (move_table) * N_REG_CLASSES);
1532   ira_may_move_out_cost[mode]
1533     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1534   memcpy (ira_may_move_out_cost[mode], may_move_out_cost[mode],
1535           sizeof (move_table) * N_REG_CLASSES);
1536   ira_max_may_move_in_cost[mode]
1537     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1538   memcpy (ira_max_may_move_in_cost[mode], ira_max_register_move_cost[mode],
1539           sizeof (move_table) * N_REG_CLASSES);
1540   ira_max_may_move_out_cost[mode]
1541     = (move_table *) xmalloc (sizeof (move_table) * N_REG_CLASSES);
1542   memcpy (ira_max_may_move_out_cost[mode], ira_max_register_move_cost[mode],
1543           sizeof (move_table) * N_REG_CLASSES);
1544   for (cl1 = 0; cl1 < N_REG_CLASSES; cl1++)
1545     {
1546       for (cl2 = 0; cl2 < N_REG_CLASSES; cl2++)
1547         {
1548           COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl2]);
1549           AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
1550           if (hard_reg_set_empty_p (temp_hard_regset))
1551             continue;
1552           if (ira_class_subset_p[cl1][cl2])
1553             ira_may_move_in_cost[mode][cl1][cl2] = 0;
1554           if (ira_class_subset_p[cl2][cl1])
1555             ira_may_move_out_cost[mode][cl1][cl2] = 0;
1556           if (ira_class_subset_p[cl1][cl2])
1557             ira_max_may_move_in_cost[mode][cl1][cl2] = 0;
1558           if (ira_class_subset_p[cl2][cl1])
1559             ira_max_may_move_out_cost[mode][cl1][cl2] = 0;
1560           ira_register_move_cost[mode][cl1][cl2]
1561             = ira_max_register_move_cost[mode][cl1][cl2];
1562           ira_may_move_in_cost[mode][cl1][cl2]
1563             = ira_max_may_move_in_cost[mode][cl1][cl2];
1564           ira_may_move_out_cost[mode][cl1][cl2]
1565             = ira_max_may_move_out_cost[mode][cl1][cl2];
1566         }
1567     }
1568 }
1569
1570 \f
1571
1572 /* This is called once during compiler work.  It sets up
1573    different arrays whose values don't depend on the compiled
1574    function.  */
1575 void
1576 ira_init_once (void)
1577 {
1578   int mode;
1579
1580   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1581     {
1582       ira_register_move_cost[mode] = NULL;
1583       ira_max_register_move_cost[mode] = NULL;
1584       ira_may_move_in_cost[mode] = NULL;
1585       ira_may_move_out_cost[mode] = NULL;
1586       ira_max_may_move_in_cost[mode] = NULL;
1587       ira_max_may_move_out_cost[mode] = NULL;
1588     }
1589   ira_init_costs_once ();
1590 }
1591
1592 /* Free ira_max_register_move_cost, ira_may_move_in_cost,
1593    ira_may_move_out_cost, ira_max_may_move_in_cost, and
1594    ira_max_may_move_out_cost for each mode.  */
1595 static void
1596 free_register_move_costs (void)
1597 {
1598   int mode;
1599
1600   for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
1601     {
1602       free (ira_max_register_move_cost[mode]);
1603       free (ira_may_move_in_cost[mode]);
1604       free (ira_may_move_out_cost[mode]);
1605       free (ira_max_may_move_in_cost[mode]);
1606       free (ira_max_may_move_out_cost[mode]);
1607       ira_register_move_cost[mode] = NULL;
1608       ira_max_register_move_cost[mode] = NULL;
1609       ira_may_move_in_cost[mode] = NULL;
1610       ira_may_move_out_cost[mode] = NULL;
1611       ira_max_may_move_in_cost[mode] = NULL;
1612       ira_max_may_move_out_cost[mode] = NULL;
1613     }
1614 }
1615
1616 /* This is called every time when register related information is
1617    changed.  */
1618 void
1619 ira_init (void)
1620 {
1621   free_register_move_costs ();
1622   setup_reg_mode_hard_regset ();
1623   setup_alloc_regs (flag_omit_frame_pointer != 0);
1624   setup_class_subset_and_memory_move_costs ();
1625   setup_reg_class_nregs ();
1626   setup_prohibited_class_mode_regs ();
1627   find_reg_classes ();
1628   clarify_prohibited_class_mode_regs ();
1629   setup_hard_regno_aclass ();
1630   ira_init_costs ();
1631 }
1632
1633 /* Function called once at the end of compiler work.  */
1634 void
1635 ira_finish_once (void)
1636 {
1637   ira_finish_costs_once ();
1638   free_register_move_costs ();
1639 }
1640
1641 \f
1642 #define ira_prohibited_mode_move_regs_initialized_p \
1643   (this_target_ira_int->x_ira_prohibited_mode_move_regs_initialized_p)
1644
1645 /* Set up IRA_PROHIBITED_MODE_MOVE_REGS.  */
1646 static void
1647 setup_prohibited_mode_move_regs (void)
1648 {
1649   int i, j;
1650   rtx test_reg1, test_reg2, move_pat, move_insn;
1651
1652   if (ira_prohibited_mode_move_regs_initialized_p)
1653     return;
1654   ira_prohibited_mode_move_regs_initialized_p = true;
1655   test_reg1 = gen_rtx_REG (VOIDmode, 0);
1656   test_reg2 = gen_rtx_REG (VOIDmode, 0);
1657   move_pat = gen_rtx_SET (VOIDmode, test_reg1, test_reg2);
1658   move_insn = gen_rtx_INSN (VOIDmode, 0, 0, 0, 0, move_pat, 0, -1, 0);
1659   for (i = 0; i < NUM_MACHINE_MODES; i++)
1660     {
1661       SET_HARD_REG_SET (ira_prohibited_mode_move_regs[i]);
1662       for (j = 0; j < FIRST_PSEUDO_REGISTER; j++)
1663         {
1664           if (! HARD_REGNO_MODE_OK (j, (enum machine_mode) i))
1665             continue;
1666           SET_REGNO_RAW (test_reg1, j);
1667           PUT_MODE (test_reg1, (enum machine_mode) i);
1668           SET_REGNO_RAW (test_reg2, j);
1669           PUT_MODE (test_reg2, (enum machine_mode) i);
1670           INSN_CODE (move_insn) = -1;
1671           recog_memoized (move_insn);
1672           if (INSN_CODE (move_insn) < 0)
1673             continue;
1674           extract_insn (move_insn);
1675           if (! constrain_operands (1))
1676             continue;
1677           CLEAR_HARD_REG_BIT (ira_prohibited_mode_move_regs[i], j);
1678         }
1679     }
1680 }
1681
1682 \f
1683
1684 /* Return nonzero if REGNO is a particularly bad choice for reloading X.  */
1685 static bool
1686 ira_bad_reload_regno_1 (int regno, rtx x)
1687 {
1688   int x_regno, n, i;
1689   ira_allocno_t a;
1690   enum reg_class pref;
1691
1692   /* We only deal with pseudo regs.  */
1693   if (! x || GET_CODE (x) != REG)
1694     return false;
1695
1696   x_regno = REGNO (x);
1697   if (x_regno < FIRST_PSEUDO_REGISTER)
1698     return false;
1699
1700   /* If the pseudo prefers REGNO explicitly, then do not consider
1701      REGNO a bad spill choice.  */
1702   pref = reg_preferred_class (x_regno);
1703   if (reg_class_size[pref] == 1)
1704     return !TEST_HARD_REG_BIT (reg_class_contents[pref], regno);
1705
1706   /* If the pseudo conflicts with REGNO, then we consider REGNO a
1707      poor choice for a reload regno.  */
1708   a = ira_regno_allocno_map[x_regno];
1709   n = ALLOCNO_NUM_OBJECTS (a);
1710   for (i = 0; i < n; i++)
1711     {
1712       ira_object_t obj = ALLOCNO_OBJECT (a, i);
1713       if (TEST_HARD_REG_BIT (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), regno))
1714         return true;
1715     }
1716   return false;
1717 }
1718
1719 /* Return nonzero if REGNO is a particularly bad choice for reloading
1720    IN or OUT.  */
1721 bool
1722 ira_bad_reload_regno (int regno, rtx in, rtx out)
1723 {
1724   return (ira_bad_reload_regno_1 (regno, in)
1725           || ira_bad_reload_regno_1 (regno, out));
1726 }
1727
1728 /* Return TRUE if *LOC contains an asm.  */
1729 static int
1730 insn_contains_asm_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
1731 {
1732   if ( !*loc)
1733     return FALSE;
1734   if (GET_CODE (*loc) == ASM_OPERANDS)
1735     return TRUE;
1736   return FALSE;
1737 }
1738
1739
1740 /* Return TRUE if INSN contains an ASM.  */
1741 static bool
1742 insn_contains_asm (rtx insn)
1743 {
1744   return for_each_rtx (&insn, insn_contains_asm_1, NULL);
1745 }
1746
1747 /* Add register clobbers from asm statements.  */
1748 static void
1749 compute_regs_asm_clobbered (void)
1750 {
1751   basic_block bb;
1752
1753   FOR_EACH_BB (bb)
1754     {
1755       rtx insn;
1756       FOR_BB_INSNS_REVERSE (bb, insn)
1757         {
1758           df_ref *def_rec;
1759
1760           if (insn_contains_asm (insn))
1761             for (def_rec = DF_INSN_DEFS (insn); *def_rec; def_rec++)
1762               {
1763                 df_ref def = *def_rec;
1764                 unsigned int dregno = DF_REF_REGNO (def);
1765                 if (HARD_REGISTER_NUM_P (dregno))
1766                   add_to_hard_reg_set (&crtl->asm_clobbers,
1767                                        GET_MODE (DF_REF_REAL_REG (def)),
1768                                        dregno);
1769               }
1770         }
1771     }
1772 }
1773
1774
1775 /* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE.  */
1776 void
1777 ira_setup_eliminable_regset (void)
1778 {
1779 #ifdef ELIMINABLE_REGS
1780   int i;
1781   static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
1782 #endif
1783   /* FIXME: If EXIT_IGNORE_STACK is set, we will not save and restore
1784      sp for alloca.  So we can't eliminate the frame pointer in that
1785      case.  At some point, we should improve this by emitting the
1786      sp-adjusting insns for this case.  */
1787   int need_fp
1788     = (! flag_omit_frame_pointer
1789        || (cfun->calls_alloca && EXIT_IGNORE_STACK)
1790        /* We need the frame pointer to catch stack overflow exceptions
1791           if the stack pointer is moving.  */
1792        || (flag_stack_check && STACK_CHECK_MOVING_SP)
1793        || crtl->accesses_prior_frames
1794        || crtl->stack_realign_needed
1795        || targetm.frame_pointer_required ());
1796
1797   frame_pointer_needed = need_fp;
1798
1799   COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
1800   CLEAR_HARD_REG_SET (eliminable_regset);
1801
1802   compute_regs_asm_clobbered ();
1803
1804   /* Build the regset of all eliminable registers and show we can't
1805      use those that we already know won't be eliminated.  */
1806 #ifdef ELIMINABLE_REGS
1807   for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
1808     {
1809       bool cannot_elim
1810         = (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
1811            || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
1812
1813       if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
1814         {
1815             SET_HARD_REG_BIT (eliminable_regset, eliminables[i].from);
1816
1817             if (cannot_elim)
1818               SET_HARD_REG_BIT (ira_no_alloc_regs, eliminables[i].from);
1819         }
1820       else if (cannot_elim)
1821         error ("%s cannot be used in asm here",
1822                reg_names[eliminables[i].from]);
1823       else
1824         df_set_regs_ever_live (eliminables[i].from, true);
1825     }
1826 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
1827   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1828     {
1829       SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
1830       if (need_fp)
1831         SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
1832     }
1833   else if (need_fp)
1834     error ("%s cannot be used in asm here",
1835            reg_names[HARD_FRAME_POINTER_REGNUM]);
1836   else
1837     df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
1838 #endif
1839
1840 #else
1841   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
1842     {
1843       SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
1844       if (need_fp)
1845         SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
1846     }
1847   else if (need_fp)
1848     error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
1849   else
1850     df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
1851 #endif
1852 }
1853
1854 \f
1855
1856 /* The length of the following two arrays.  */
1857 int ira_reg_equiv_len;
1858
1859 /* The element value is TRUE if the corresponding regno value is
1860    invariant.  */
1861 bool *ira_reg_equiv_invariant_p;
1862
1863 /* The element value is equiv constant of given pseudo-register or
1864    NULL_RTX.  */
1865 rtx *ira_reg_equiv_const;
1866
1867 /* Set up the two arrays declared above.  */
1868 static void
1869 find_reg_equiv_invariant_const (void)
1870 {
1871   unsigned int i;
1872   bool invariant_p;
1873   rtx list, insn, note, constant, x;
1874
1875   for (i = FIRST_PSEUDO_REGISTER; i < VEC_length (reg_equivs_t, reg_equivs); i++)
1876     {
1877       constant = NULL_RTX;
1878       invariant_p = false;
1879       for (list = reg_equiv_init (i); list != NULL_RTX; list = XEXP (list, 1))
1880         {
1881           insn = XEXP (list, 0);
1882           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
1883
1884           if (note == NULL_RTX)
1885             continue;
1886
1887           x = XEXP (note, 0);
1888
1889           if (! CONSTANT_P (x)
1890               || ! flag_pic || LEGITIMATE_PIC_OPERAND_P (x))
1891             {
1892               /* It can happen that a REG_EQUIV note contains a MEM
1893                  that is not a legitimate memory operand.  As later
1894                  stages of the reload assume that all addresses found
1895                  in the reg_equiv_* arrays were originally legitimate,
1896                  we ignore such REG_EQUIV notes.  */
1897               if (memory_operand (x, VOIDmode))
1898                 invariant_p = MEM_READONLY_P (x);
1899               else if (function_invariant_p (x))
1900                 {
1901                   if (GET_CODE (x) == PLUS
1902                       || x == frame_pointer_rtx || x == arg_pointer_rtx)
1903                     invariant_p = true;
1904                   else
1905                     constant = x;
1906                 }
1907             }
1908         }
1909       ira_reg_equiv_invariant_p[i] = invariant_p;
1910       ira_reg_equiv_const[i] = constant;
1911     }
1912 }
1913
1914 \f
1915
1916 /* Vector of substitutions of register numbers,
1917    used to map pseudo regs into hardware regs.
1918    This is set up as a result of register allocation.
1919    Element N is the hard reg assigned to pseudo reg N,
1920    or is -1 if no hard reg was assigned.
1921    If N is a hard reg number, element N is N.  */
1922 short *reg_renumber;
1923
1924 /* Set up REG_RENUMBER and CALLER_SAVE_NEEDED (used by reload) from
1925    the allocation found by IRA.  */
1926 static void
1927 setup_reg_renumber (void)
1928 {
1929   int regno, hard_regno;
1930   ira_allocno_t a;
1931   ira_allocno_iterator ai;
1932
1933   caller_save_needed = 0;
1934   FOR_EACH_ALLOCNO (a, ai)
1935     {
1936       /* There are no caps at this point.  */
1937       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1938       if (! ALLOCNO_ASSIGNED_P (a))
1939         /* It can happen if A is not referenced but partially anticipated
1940            somewhere in a region.  */
1941         ALLOCNO_ASSIGNED_P (a) = true;
1942       ira_free_allocno_updated_costs (a);
1943       hard_regno = ALLOCNO_HARD_REGNO (a);
1944       regno = ALLOCNO_REGNO (a);
1945       reg_renumber[regno] = (hard_regno < 0 ? -1 : hard_regno);
1946       if (hard_regno >= 0)
1947         {
1948           int i, nwords;
1949           enum reg_class pclass;
1950           ira_object_t obj;
1951           
1952           pclass = ira_pressure_class_translate[REGNO_REG_CLASS (hard_regno)];
1953           nwords = ALLOCNO_NUM_OBJECTS (a);
1954           for (i = 0; i < nwords; i++)
1955             {
1956               obj = ALLOCNO_OBJECT (a, i);
1957               IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
1958                                       reg_class_contents[pclass]);
1959             }
1960           if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0
1961               && ira_hard_reg_set_intersection_p (hard_regno, ALLOCNO_MODE (a),
1962                                                   call_used_reg_set))
1963             {
1964               ira_assert (!optimize || flag_caller_saves
1965                           || regno >= ira_reg_equiv_len
1966                           || ira_reg_equiv_const[regno]
1967                           || ira_reg_equiv_invariant_p[regno]);
1968               caller_save_needed = 1;
1969             }
1970         }
1971     }
1972 }
1973
1974 /* Set up allocno assignment flags for further allocation
1975    improvements.  */
1976 static void
1977 setup_allocno_assignment_flags (void)
1978 {
1979   int hard_regno;
1980   ira_allocno_t a;
1981   ira_allocno_iterator ai;
1982
1983   FOR_EACH_ALLOCNO (a, ai)
1984     {
1985       if (! ALLOCNO_ASSIGNED_P (a))
1986         /* It can happen if A is not referenced but partially anticipated
1987            somewhere in a region.  */
1988         ira_free_allocno_updated_costs (a);
1989       hard_regno = ALLOCNO_HARD_REGNO (a);
1990       /* Don't assign hard registers to allocnos which are destination
1991          of removed store at the end of loop.  It has no sense to keep
1992          the same value in different hard registers.  It is also
1993          impossible to assign hard registers correctly to such
1994          allocnos because the cost info and info about intersected
1995          calls are incorrect for them.  */
1996       ALLOCNO_ASSIGNED_P (a) = (hard_regno >= 0
1997                                 || ALLOCNO_EMIT_DATA (a)->mem_optimized_dest_p
1998                                 || (ALLOCNO_MEMORY_COST (a)
1999                                     - ALLOCNO_CLASS_COST (a)) < 0);
2000       ira_assert
2001         (hard_regno < 0
2002          || ira_hard_reg_in_set_p (hard_regno, ALLOCNO_MODE (a),
2003                                    reg_class_contents[ALLOCNO_CLASS (a)]));
2004     }
2005 }
2006
2007 /* Evaluate overall allocation cost and the costs for using hard
2008    registers and memory for allocnos.  */
2009 static void
2010 calculate_allocation_cost (void)
2011 {
2012   int hard_regno, cost;
2013   ira_allocno_t a;
2014   ira_allocno_iterator ai;
2015
2016   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
2017   FOR_EACH_ALLOCNO (a, ai)
2018     {
2019       hard_regno = ALLOCNO_HARD_REGNO (a);
2020       ira_assert (hard_regno < 0
2021                   || (ira_hard_reg_in_set_p
2022                       (hard_regno, ALLOCNO_MODE (a),
2023                        reg_class_contents[ALLOCNO_CLASS (a)])));
2024       if (hard_regno < 0)
2025         {
2026           cost = ALLOCNO_MEMORY_COST (a);
2027           ira_mem_cost += cost;
2028         }
2029       else if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
2030         {
2031           cost = (ALLOCNO_HARD_REG_COSTS (a)
2032                   [ira_class_hard_reg_index
2033                    [ALLOCNO_CLASS (a)][hard_regno]]);
2034           ira_reg_cost += cost;
2035         }
2036       else
2037         {
2038           cost = ALLOCNO_CLASS_COST (a);
2039           ira_reg_cost += cost;
2040         }
2041       ira_overall_cost += cost;
2042     }
2043
2044   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2045     {
2046       fprintf (ira_dump_file,
2047                "+++Costs: overall %d, reg %d, mem %d, ld %d, st %d, move %d\n",
2048                ira_overall_cost, ira_reg_cost, ira_mem_cost,
2049                ira_load_cost, ira_store_cost, ira_shuffle_cost);
2050       fprintf (ira_dump_file, "+++       move loops %d, new jumps %d\n",
2051                ira_move_loops_num, ira_additional_jumps_num);
2052     }
2053
2054 }
2055
2056 #ifdef ENABLE_IRA_CHECKING
2057 /* Check the correctness of the allocation.  We do need this because
2058    of complicated code to transform more one region internal
2059    representation into one region representation.  */
2060 static void
2061 check_allocation (void)
2062 {
2063   ira_allocno_t a;
2064   int hard_regno, nregs, conflict_nregs;
2065   ira_allocno_iterator ai;
2066
2067   FOR_EACH_ALLOCNO (a, ai)
2068     {
2069       int n = ALLOCNO_NUM_OBJECTS (a);
2070       int i;
2071
2072       if (ALLOCNO_CAP_MEMBER (a) != NULL
2073           || (hard_regno = ALLOCNO_HARD_REGNO (a)) < 0)
2074         continue;
2075       nregs = hard_regno_nregs[hard_regno][ALLOCNO_MODE (a)];
2076       if (nregs == 1)
2077         /* We allocated a single hard register.  */
2078         n = 1;
2079       else if (n > 1)
2080         /* We allocated multiple hard registers, and we will test
2081            conflicts in a granularity of single hard regs.  */
2082         nregs = 1;
2083
2084       for (i = 0; i < n; i++)
2085         {
2086           ira_object_t obj = ALLOCNO_OBJECT (a, i);
2087           ira_object_t conflict_obj;
2088           ira_object_conflict_iterator oci;
2089           int this_regno = hard_regno;
2090           if (n > 1)
2091             {
2092               if (REG_WORDS_BIG_ENDIAN)
2093                 this_regno += n - i - 1;
2094               else
2095                 this_regno += i;
2096             }
2097           FOR_EACH_OBJECT_CONFLICT (obj, conflict_obj, oci)
2098             {
2099               ira_allocno_t conflict_a = OBJECT_ALLOCNO (conflict_obj);
2100               int conflict_hard_regno = ALLOCNO_HARD_REGNO (conflict_a);
2101               if (conflict_hard_regno < 0)
2102                 continue;
2103
2104               conflict_nregs
2105                 = (hard_regno_nregs
2106                    [conflict_hard_regno][ALLOCNO_MODE (conflict_a)]);
2107
2108               if (ALLOCNO_NUM_OBJECTS (conflict_a) > 1
2109                   && conflict_nregs == ALLOCNO_NUM_OBJECTS (conflict_a))
2110                 {
2111                   if (REG_WORDS_BIG_ENDIAN)
2112                     conflict_hard_regno += (ALLOCNO_NUM_OBJECTS (conflict_a)
2113                                             - OBJECT_SUBWORD (conflict_obj) - 1);
2114                   else
2115                     conflict_hard_regno += OBJECT_SUBWORD (conflict_obj);
2116                   conflict_nregs = 1;
2117                 }
2118
2119               if ((conflict_hard_regno <= this_regno
2120                  && this_regno < conflict_hard_regno + conflict_nregs)
2121                 || (this_regno <= conflict_hard_regno
2122                     && conflict_hard_regno < this_regno + nregs))
2123                 {
2124                   fprintf (stderr, "bad allocation for %d and %d\n",
2125                            ALLOCNO_REGNO (a), ALLOCNO_REGNO (conflict_a));
2126                   gcc_unreachable ();
2127                 }
2128             }
2129         }
2130     }
2131 }
2132 #endif
2133
2134 /* Fix values of array REG_EQUIV_INIT after live range splitting done
2135    by IRA.  */
2136 static void
2137 fix_reg_equiv_init (void)
2138 {
2139   unsigned int max_regno = max_reg_num ();
2140   int i, new_regno, max;
2141   rtx x, prev, next, insn, set;
2142
2143   if (VEC_length (reg_equivs_t, reg_equivs) < max_regno)
2144     {
2145       max = VEC_length (reg_equivs_t, reg_equivs);
2146       grow_reg_equivs ();
2147       for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
2148         for (prev = NULL_RTX, x = reg_equiv_init (i);
2149              x != NULL_RTX;
2150              x = next)
2151           {
2152             next = XEXP (x, 1);
2153             insn = XEXP (x, 0);
2154             set = single_set (insn);
2155             ira_assert (set != NULL_RTX
2156                         && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))));
2157             if (REG_P (SET_DEST (set))
2158                 && ((int) REGNO (SET_DEST (set)) == i
2159                     || (int) ORIGINAL_REGNO (SET_DEST (set)) == i))
2160               new_regno = REGNO (SET_DEST (set));
2161             else if (REG_P (SET_SRC (set))
2162                      && ((int) REGNO (SET_SRC (set)) == i
2163                          || (int) ORIGINAL_REGNO (SET_SRC (set)) == i))
2164               new_regno = REGNO (SET_SRC (set));
2165             else
2166               gcc_unreachable ();
2167             if (new_regno == i)
2168               prev = x;
2169             else
2170               {
2171                 if (prev == NULL_RTX)
2172                   reg_equiv_init (i) = next;
2173                 else
2174                   XEXP (prev, 1) = next;
2175                 XEXP (x, 1) = reg_equiv_init (new_regno);
2176                 reg_equiv_init (new_regno) = x;
2177               }
2178           }
2179     }
2180 }
2181
2182 #ifdef ENABLE_IRA_CHECKING
2183 /* Print redundant memory-memory copies.  */
2184 static void
2185 print_redundant_copies (void)
2186 {
2187   int hard_regno;
2188   ira_allocno_t a;
2189   ira_copy_t cp, next_cp;
2190   ira_allocno_iterator ai;
2191
2192   FOR_EACH_ALLOCNO (a, ai)
2193     {
2194       if (ALLOCNO_CAP_MEMBER (a) != NULL)
2195         /* It is a cap. */
2196         continue;
2197       hard_regno = ALLOCNO_HARD_REGNO (a);
2198       if (hard_regno >= 0)
2199         continue;
2200       for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
2201         if (cp->first == a)
2202           next_cp = cp->next_first_allocno_copy;
2203         else
2204           {
2205             next_cp = cp->next_second_allocno_copy;
2206             if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL
2207                 && cp->insn != NULL_RTX
2208                 && ALLOCNO_HARD_REGNO (cp->first) == hard_regno)
2209               fprintf (ira_dump_file,
2210                        "        Redundant move from %d(freq %d):%d\n",
2211                        INSN_UID (cp->insn), cp->freq, hard_regno);
2212           }
2213     }
2214 }
2215 #endif
2216
2217 /* Setup preferred and alternative classes for new pseudo-registers
2218    created by IRA starting with START.  */
2219 static void
2220 setup_preferred_alternate_classes_for_new_pseudos (int start)
2221 {
2222   int i, old_regno;
2223   int max_regno = max_reg_num ();
2224
2225   for (i = start; i < max_regno; i++)
2226     {
2227       old_regno = ORIGINAL_REGNO (regno_reg_rtx[i]);
2228       ira_assert (i != old_regno);
2229       setup_reg_classes (i, reg_preferred_class (old_regno),
2230                          reg_alternate_class (old_regno),
2231                          reg_allocno_class (old_regno));
2232       if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
2233         fprintf (ira_dump_file,
2234                  "    New r%d: setting preferred %s, alternative %s\n",
2235                  i, reg_class_names[reg_preferred_class (old_regno)],
2236                  reg_class_names[reg_alternate_class (old_regno)]);
2237     }
2238 }
2239
2240 \f
2241
2242 /* Regional allocation can create new pseudo-registers.  This function
2243    expands some arrays for pseudo-registers.  */
2244 static void
2245 expand_reg_info (int old_size)
2246 {
2247   int i;
2248   int size = max_reg_num ();
2249
2250   resize_reg_info ();
2251   for (i = old_size; i < size; i++)
2252     setup_reg_classes (i, GENERAL_REGS, ALL_REGS, GENERAL_REGS);
2253 }
2254
2255 /* Return TRUE if there is too high register pressure in the function.
2256    It is used to decide when stack slot sharing is worth to do.  */
2257 static bool
2258 too_high_register_pressure_p (void)
2259 {
2260   int i;
2261   enum reg_class pclass;
2262
2263   for (i = 0; i < ira_pressure_classes_num; i++)
2264     {
2265       pclass = ira_pressure_classes[i];
2266       if (ira_loop_tree_root->reg_pressure[pclass] > 10000)
2267         return true;
2268     }
2269   return false;
2270 }
2271
2272 \f
2273
2274 /* Indicate that hard register number FROM was eliminated and replaced with
2275    an offset from hard register number TO.  The status of hard registers live
2276    at the start of a basic block is updated by replacing a use of FROM with
2277    a use of TO.  */
2278
2279 void
2280 mark_elimination (int from, int to)
2281 {
2282   basic_block bb;
2283
2284   FOR_EACH_BB (bb)
2285     {
2286       /* We don't use LIVE info in IRA.  */
2287       bitmap r = DF_LR_IN (bb);
2288
2289       if (REGNO_REG_SET_P (r, from))
2290         {
2291           CLEAR_REGNO_REG_SET (r, from);
2292           SET_REGNO_REG_SET (r, to);
2293         }
2294     }
2295 }
2296
2297 \f
2298
2299 struct equivalence
2300 {
2301   /* Set when a REG_EQUIV note is found or created.  Use to
2302      keep track of what memory accesses might be created later,
2303      e.g. by reload.  */
2304   rtx replacement;
2305   rtx *src_p;
2306   /* The list of each instruction which initializes this register.  */
2307   rtx init_insns;
2308   /* Loop depth is used to recognize equivalences which appear
2309      to be present within the same loop (or in an inner loop).  */
2310   int loop_depth;
2311   /* Nonzero if this had a preexisting REG_EQUIV note.  */
2312   int is_arg_equivalence;
2313   /* Set when an attempt should be made to replace a register
2314      with the associated src_p entry.  */
2315   char replace;
2316 };
2317
2318 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
2319    structure for that register.  */
2320 static struct equivalence *reg_equiv;
2321
2322 /* Used for communication between the following two functions: contains
2323    a MEM that we wish to ensure remains unchanged.  */
2324 static rtx equiv_mem;
2325
2326 /* Set nonzero if EQUIV_MEM is modified.  */
2327 static int equiv_mem_modified;
2328
2329 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
2330    Called via note_stores.  */
2331 static void
2332 validate_equiv_mem_from_store (rtx dest, const_rtx set ATTRIBUTE_UNUSED,
2333                                void *data ATTRIBUTE_UNUSED)
2334 {
2335   if ((REG_P (dest)
2336        && reg_overlap_mentioned_p (dest, equiv_mem))
2337       || (MEM_P (dest)
2338           && true_dependence (dest, VOIDmode, equiv_mem)))
2339     equiv_mem_modified = 1;
2340 }
2341
2342 /* Verify that no store between START and the death of REG invalidates
2343    MEMREF.  MEMREF is invalidated by modifying a register used in MEMREF,
2344    by storing into an overlapping memory location, or with a non-const
2345    CALL_INSN.
2346
2347    Return 1 if MEMREF remains valid.  */
2348 static int
2349 validate_equiv_mem (rtx start, rtx reg, rtx memref)
2350 {
2351   rtx insn;
2352   rtx note;
2353
2354   equiv_mem = memref;
2355   equiv_mem_modified = 0;
2356
2357   /* If the memory reference has side effects or is volatile, it isn't a
2358      valid equivalence.  */
2359   if (side_effects_p (memref))
2360     return 0;
2361
2362   for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
2363     {
2364       if (! INSN_P (insn))
2365         continue;
2366
2367       if (find_reg_note (insn, REG_DEAD, reg))
2368         return 1;
2369
2370       /* This used to ignore readonly memory and const/pure calls.  The problem
2371          is the equivalent form may reference a pseudo which gets assigned a
2372          call clobbered hard reg.  When we later replace REG with its
2373          equivalent form, the value in the call-clobbered reg has been
2374          changed and all hell breaks loose.  */
2375       if (CALL_P (insn))
2376         return 0;
2377
2378       note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
2379
2380       /* If a register mentioned in MEMREF is modified via an
2381          auto-increment, we lose the equivalence.  Do the same if one
2382          dies; although we could extend the life, it doesn't seem worth
2383          the trouble.  */
2384
2385       for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2386         if ((REG_NOTE_KIND (note) == REG_INC
2387              || REG_NOTE_KIND (note) == REG_DEAD)
2388             && REG_P (XEXP (note, 0))
2389             && reg_overlap_mentioned_p (XEXP (note, 0), memref))
2390           return 0;
2391     }
2392
2393   return 0;
2394 }
2395
2396 /* Returns zero if X is known to be invariant.  */
2397 static int
2398 equiv_init_varies_p (rtx x)
2399 {
2400   RTX_CODE code = GET_CODE (x);
2401   int i;
2402   const char *fmt;
2403
2404   switch (code)
2405     {
2406     case MEM:
2407       return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
2408
2409     case CONST:
2410     case CONST_INT:
2411     case CONST_DOUBLE:
2412     case CONST_FIXED:
2413     case CONST_VECTOR:
2414     case SYMBOL_REF:
2415     case LABEL_REF:
2416       return 0;
2417
2418     case REG:
2419       return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
2420
2421     case ASM_OPERANDS:
2422       if (MEM_VOLATILE_P (x))
2423         return 1;
2424
2425       /* Fall through.  */
2426
2427     default:
2428       break;
2429     }
2430
2431   fmt = GET_RTX_FORMAT (code);
2432   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2433     if (fmt[i] == 'e')
2434       {
2435         if (equiv_init_varies_p (XEXP (x, i)))
2436           return 1;
2437       }
2438     else if (fmt[i] == 'E')
2439       {
2440         int j;
2441         for (j = 0; j < XVECLEN (x, i); j++)
2442           if (equiv_init_varies_p (XVECEXP (x, i, j)))
2443             return 1;
2444       }
2445
2446   return 0;
2447 }
2448
2449 /* Returns nonzero if X (used to initialize register REGNO) is movable.
2450    X is only movable if the registers it uses have equivalent initializations
2451    which appear to be within the same loop (or in an inner loop) and movable
2452    or if they are not candidates for local_alloc and don't vary.  */
2453 static int
2454 equiv_init_movable_p (rtx x, int regno)
2455 {
2456   int i, j;
2457   const char *fmt;
2458   enum rtx_code code = GET_CODE (x);
2459
2460   switch (code)
2461     {
2462     case SET:
2463       return equiv_init_movable_p (SET_SRC (x), regno);
2464
2465     case CC0:
2466     case CLOBBER:
2467       return 0;
2468
2469     case PRE_INC:
2470     case PRE_DEC:
2471     case POST_INC:
2472     case POST_DEC:
2473     case PRE_MODIFY:
2474     case POST_MODIFY:
2475       return 0;
2476
2477     case REG:
2478       return ((reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
2479                && reg_equiv[REGNO (x)].replace)
2480               || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS
2481                   && ! rtx_varies_p (x, 0)));
2482
2483     case UNSPEC_VOLATILE:
2484       return 0;
2485
2486     case ASM_OPERANDS:
2487       if (MEM_VOLATILE_P (x))
2488         return 0;
2489
2490       /* Fall through.  */
2491
2492     default:
2493       break;
2494     }
2495
2496   fmt = GET_RTX_FORMAT (code);
2497   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2498     switch (fmt[i])
2499       {
2500       case 'e':
2501         if (! equiv_init_movable_p (XEXP (x, i), regno))
2502           return 0;
2503         break;
2504       case 'E':
2505         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2506           if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
2507             return 0;
2508         break;
2509       }
2510
2511   return 1;
2512 }
2513
2514 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is
2515    true.  */
2516 static int
2517 contains_replace_regs (rtx x)
2518 {
2519   int i, j;
2520   const char *fmt;
2521   enum rtx_code code = GET_CODE (x);
2522
2523   switch (code)
2524     {
2525     case CONST_INT:
2526     case CONST:
2527     case LABEL_REF:
2528     case SYMBOL_REF:
2529     case CONST_DOUBLE:
2530     case CONST_FIXED:
2531     case CONST_VECTOR:
2532     case PC:
2533     case CC0:
2534     case HIGH:
2535       return 0;
2536
2537     case REG:
2538       return reg_equiv[REGNO (x)].replace;
2539
2540     default:
2541       break;
2542     }
2543
2544   fmt = GET_RTX_FORMAT (code);
2545   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2546     switch (fmt[i])
2547       {
2548       case 'e':
2549         if (contains_replace_regs (XEXP (x, i)))
2550           return 1;
2551         break;
2552       case 'E':
2553         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2554           if (contains_replace_regs (XVECEXP (x, i, j)))
2555             return 1;
2556         break;
2557       }
2558
2559   return 0;
2560 }
2561
2562 /* TRUE if X references a memory location that would be affected by a store
2563    to MEMREF.  */
2564 static int
2565 memref_referenced_p (rtx memref, rtx x)
2566 {
2567   int i, j;
2568   const char *fmt;
2569   enum rtx_code code = GET_CODE (x);
2570
2571   switch (code)
2572     {
2573     case CONST_INT:
2574     case CONST:
2575     case LABEL_REF:
2576     case SYMBOL_REF:
2577     case CONST_DOUBLE:
2578     case CONST_FIXED:
2579     case CONST_VECTOR:
2580     case PC:
2581     case CC0:
2582     case HIGH:
2583     case LO_SUM:
2584       return 0;
2585
2586     case REG:
2587       return (reg_equiv[REGNO (x)].replacement
2588               && memref_referenced_p (memref,
2589                                       reg_equiv[REGNO (x)].replacement));
2590
2591     case MEM:
2592       if (true_dependence (memref, VOIDmode, x))
2593         return 1;
2594       break;
2595
2596     case SET:
2597       /* If we are setting a MEM, it doesn't count (its address does), but any
2598          other SET_DEST that has a MEM in it is referencing the MEM.  */
2599       if (MEM_P (SET_DEST (x)))
2600         {
2601           if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
2602             return 1;
2603         }
2604       else if (memref_referenced_p (memref, SET_DEST (x)))
2605         return 1;
2606
2607       return memref_referenced_p (memref, SET_SRC (x));
2608
2609     default:
2610       break;
2611     }
2612
2613   fmt = GET_RTX_FORMAT (code);
2614   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2615     switch (fmt[i])
2616       {
2617       case 'e':
2618         if (memref_referenced_p (memref, XEXP (x, i)))
2619           return 1;
2620         break;
2621       case 'E':
2622         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2623           if (memref_referenced_p (memref, XVECEXP (x, i, j)))
2624             return 1;
2625         break;
2626       }
2627
2628   return 0;
2629 }
2630
2631 /* TRUE if some insn in the range (START, END] references a memory location
2632    that would be affected by a store to MEMREF.  */
2633 static int
2634 memref_used_between_p (rtx memref, rtx start, rtx end)
2635 {
2636   rtx insn;
2637
2638   for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
2639        insn = NEXT_INSN (insn))
2640     {
2641       if (!NONDEBUG_INSN_P (insn))
2642         continue;
2643
2644       if (memref_referenced_p (memref, PATTERN (insn)))
2645         return 1;
2646
2647       /* Nonconst functions may access memory.  */
2648       if (CALL_P (insn) && (! RTL_CONST_CALL_P (insn)))
2649         return 1;
2650     }
2651
2652   return 0;
2653 }
2654
2655 /* Mark REG as having no known equivalence.
2656    Some instructions might have been processed before and furnished
2657    with REG_EQUIV notes for this register; these notes will have to be
2658    removed.
2659    STORE is the piece of RTL that does the non-constant / conflicting
2660    assignment - a SET, CLOBBER or REG_INC note.  It is currently not used,
2661    but needs to be there because this function is called from note_stores.  */
2662 static void
2663 no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
2664           void *data ATTRIBUTE_UNUSED)
2665 {
2666   int regno;
2667   rtx list;
2668
2669   if (!REG_P (reg))
2670     return;
2671   regno = REGNO (reg);
2672   list = reg_equiv[regno].init_insns;
2673   if (list == const0_rtx)
2674     return;
2675   reg_equiv[regno].init_insns = const0_rtx;
2676   reg_equiv[regno].replacement = NULL_RTX;
2677   /* This doesn't matter for equivalences made for argument registers, we
2678      should keep their initialization insns.  */
2679   if (reg_equiv[regno].is_arg_equivalence)
2680     return;
2681   reg_equiv_init (regno) = NULL_RTX;
2682   for (; list; list =  XEXP (list, 1))
2683     {
2684       rtx insn = XEXP (list, 0);
2685       remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
2686     }
2687 }
2688
2689 /* In DEBUG_INSN location adjust REGs from CLEARED_REGS bitmap to the
2690    equivalent replacement.  */
2691
2692 static rtx
2693 adjust_cleared_regs (rtx loc, const_rtx old_rtx ATTRIBUTE_UNUSED, void *data)
2694 {
2695   if (REG_P (loc))
2696     {
2697       bitmap cleared_regs = (bitmap) data;
2698       if (bitmap_bit_p (cleared_regs, REGNO (loc)))
2699         return simplify_replace_fn_rtx (*reg_equiv[REGNO (loc)].src_p,
2700                                         NULL_RTX, adjust_cleared_regs, data);
2701     }
2702   return NULL_RTX;
2703 }
2704
2705 /* Nonzero if we recorded an equivalence for a LABEL_REF.  */
2706 static int recorded_label_ref;
2707
2708 /* Find registers that are equivalent to a single value throughout the
2709    compilation (either because they can be referenced in memory or are
2710    set once from a single constant).  Lower their priority for a
2711    register.
2712
2713    If such a register is only referenced once, try substituting its
2714    value into the using insn.  If it succeeds, we can eliminate the
2715    register completely.
2716
2717    Initialize the REG_EQUIV_INIT array of initializing insns.
2718
2719    Return non-zero if jump label rebuilding should be done.  */
2720 static int
2721 update_equiv_regs (void)
2722 {
2723   rtx insn;
2724   basic_block bb;
2725   int loop_depth;
2726   bitmap cleared_regs;
2727
2728   /* We need to keep track of whether or not we recorded a LABEL_REF so
2729      that we know if the jump optimizer needs to be rerun.  */
2730   recorded_label_ref = 0;
2731
2732   reg_equiv = XCNEWVEC (struct equivalence, max_regno);
2733   grow_reg_equivs ();
2734
2735   init_alias_analysis ();
2736
2737   /* Scan the insns and find which registers have equivalences.  Do this
2738      in a separate scan of the insns because (due to -fcse-follow-jumps)
2739      a register can be set below its use.  */
2740   FOR_EACH_BB (bb)
2741     {
2742       loop_depth = bb->loop_depth;
2743
2744       for (insn = BB_HEAD (bb);
2745            insn != NEXT_INSN (BB_END (bb));
2746            insn = NEXT_INSN (insn))
2747         {
2748           rtx note;
2749           rtx set;
2750           rtx dest, src;
2751           int regno;
2752
2753           if (! INSN_P (insn))
2754             continue;
2755
2756           for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
2757             if (REG_NOTE_KIND (note) == REG_INC)
2758               no_equiv (XEXP (note, 0), note, NULL);
2759
2760           set = single_set (insn);
2761
2762           /* If this insn contains more (or less) than a single SET,
2763              only mark all destinations as having no known equivalence.  */
2764           if (set == 0)
2765             {
2766               note_stores (PATTERN (insn), no_equiv, NULL);
2767               continue;
2768             }
2769           else if (GET_CODE (PATTERN (insn)) == PARALLEL)
2770             {
2771               int i;
2772
2773               for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
2774                 {
2775                   rtx part = XVECEXP (PATTERN (insn), 0, i);
2776                   if (part != set)
2777                     note_stores (part, no_equiv, NULL);
2778                 }
2779             }
2780
2781           dest = SET_DEST (set);
2782           src = SET_SRC (set);
2783
2784           /* See if this is setting up the equivalence between an argument
2785              register and its stack slot.  */
2786           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2787           if (note)
2788             {
2789               gcc_assert (REG_P (dest));
2790               regno = REGNO (dest);
2791
2792               /* Note that we don't want to clear reg_equiv_init even if there
2793                  are multiple sets of this register.  */
2794               reg_equiv[regno].is_arg_equivalence = 1;
2795
2796               /* Record for reload that this is an equivalencing insn.  */
2797               if (rtx_equal_p (src, XEXP (note, 0)))
2798                 reg_equiv_init (regno)
2799                   = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
2800
2801               /* Continue normally in case this is a candidate for
2802                  replacements.  */
2803             }
2804
2805           if (!optimize)
2806             continue;
2807
2808           /* We only handle the case of a pseudo register being set
2809              once, or always to the same value.  */
2810           /* ??? The mn10200 port breaks if we add equivalences for
2811              values that need an ADDRESS_REGS register and set them equivalent
2812              to a MEM of a pseudo.  The actual problem is in the over-conservative
2813              handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
2814              calculate_needs, but we traditionally work around this problem
2815              here by rejecting equivalences when the destination is in a register
2816              that's likely spilled.  This is fragile, of course, since the
2817              preferred class of a pseudo depends on all instructions that set
2818              or use it.  */
2819
2820           if (!REG_P (dest)
2821               || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
2822               || reg_equiv[regno].init_insns == const0_rtx
2823               || (targetm.class_likely_spilled_p (reg_preferred_class (regno))
2824                   && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
2825             {
2826               /* This might be setting a SUBREG of a pseudo, a pseudo that is
2827                  also set somewhere else to a constant.  */
2828               note_stores (set, no_equiv, NULL);
2829               continue;
2830             }
2831
2832           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
2833
2834           /* cse sometimes generates function invariants, but doesn't put a
2835              REG_EQUAL note on the insn.  Since this note would be redundant,
2836              there's no point creating it earlier than here.  */
2837           if (! note && ! rtx_varies_p (src, 0))
2838             note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2839
2840           /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
2841              since it represents a function call */
2842           if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
2843             note = NULL_RTX;
2844
2845           if (DF_REG_DEF_COUNT (regno) != 1
2846               && (! note
2847                   || rtx_varies_p (XEXP (note, 0), 0)
2848                   || (reg_equiv[regno].replacement
2849                       && ! rtx_equal_p (XEXP (note, 0),
2850                                         reg_equiv[regno].replacement))))
2851             {
2852               no_equiv (dest, set, NULL);
2853               continue;
2854             }
2855           /* Record this insn as initializing this register.  */
2856           reg_equiv[regno].init_insns
2857             = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
2858
2859           /* If this register is known to be equal to a constant, record that
2860              it is always equivalent to the constant.  */
2861           if (DF_REG_DEF_COUNT (regno) == 1
2862               && note && ! rtx_varies_p (XEXP (note, 0), 0))
2863             {
2864               rtx note_value = XEXP (note, 0);
2865               remove_note (insn, note);
2866               set_unique_reg_note (insn, REG_EQUIV, note_value);
2867             }
2868
2869           /* If this insn introduces a "constant" register, decrease the priority
2870              of that register.  Record this insn if the register is only used once
2871              more and the equivalence value is the same as our source.
2872
2873              The latter condition is checked for two reasons:  First, it is an
2874              indication that it may be more efficient to actually emit the insn
2875              as written (if no registers are available, reload will substitute
2876              the equivalence).  Secondly, it avoids problems with any registers
2877              dying in this insn whose death notes would be missed.
2878
2879              If we don't have a REG_EQUIV note, see if this insn is loading
2880              a register used only in one basic block from a MEM.  If so, and the
2881              MEM remains unchanged for the life of the register, add a REG_EQUIV
2882              note.  */
2883
2884           note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
2885
2886           if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2887               && MEM_P (SET_SRC (set))
2888               && validate_equiv_mem (insn, dest, SET_SRC (set)))
2889             note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
2890
2891           if (note)
2892             {
2893               int regno = REGNO (dest);
2894               rtx x = XEXP (note, 0);
2895
2896               /* If we haven't done so, record for reload that this is an
2897                  equivalencing insn.  */
2898               if (!reg_equiv[regno].is_arg_equivalence)
2899                 reg_equiv_init (regno)
2900                   = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
2901
2902               /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
2903                  We might end up substituting the LABEL_REF for uses of the
2904                  pseudo here or later.  That kind of transformation may turn an
2905                  indirect jump into a direct jump, in which case we must rerun the
2906                  jump optimizer to ensure that the JUMP_LABEL fields are valid.  */
2907               if (GET_CODE (x) == LABEL_REF
2908                   || (GET_CODE (x) == CONST
2909                       && GET_CODE (XEXP (x, 0)) == PLUS
2910                       && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
2911                 recorded_label_ref = 1;
2912
2913               reg_equiv[regno].replacement = x;
2914               reg_equiv[regno].src_p = &SET_SRC (set);
2915               reg_equiv[regno].loop_depth = loop_depth;
2916
2917               /* Don't mess with things live during setjmp.  */
2918               if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
2919                 {
2920                   /* Note that the statement below does not affect the priority
2921                      in local-alloc!  */
2922                   REG_LIVE_LENGTH (regno) *= 2;
2923
2924                   /* If the register is referenced exactly twice, meaning it is
2925                      set once and used once, indicate that the reference may be
2926                      replaced by the equivalence we computed above.  Do this
2927                      even if the register is only used in one block so that
2928                      dependencies can be handled where the last register is
2929                      used in a different block (i.e. HIGH / LO_SUM sequences)
2930                      and to reduce the number of registers alive across
2931                      calls.  */
2932
2933                   if (REG_N_REFS (regno) == 2
2934                       && (rtx_equal_p (x, src)
2935                           || ! equiv_init_varies_p (src))
2936                       && NONJUMP_INSN_P (insn)
2937                       && equiv_init_movable_p (PATTERN (insn), regno))
2938                     reg_equiv[regno].replace = 1;
2939                 }
2940             }
2941         }
2942     }
2943
2944   if (!optimize)
2945     goto out;
2946
2947   /* A second pass, to gather additional equivalences with memory.  This needs
2948      to be done after we know which registers we are going to replace.  */
2949
2950   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
2951     {
2952       rtx set, src, dest;
2953       unsigned regno;
2954
2955       if (! INSN_P (insn))
2956         continue;
2957
2958       set = single_set (insn);
2959       if (! set)
2960         continue;
2961
2962       dest = SET_DEST (set);
2963       src = SET_SRC (set);
2964
2965       /* If this sets a MEM to the contents of a REG that is only used
2966          in a single basic block, see if the register is always equivalent
2967          to that memory location and if moving the store from INSN to the
2968          insn that set REG is safe.  If so, put a REG_EQUIV note on the
2969          initializing insn.
2970
2971          Don't add a REG_EQUIV note if the insn already has one.  The existing
2972          REG_EQUIV is likely more useful than the one we are adding.
2973
2974          If one of the regs in the address has reg_equiv[REGNO].replace set,
2975          then we can't add this REG_EQUIV note.  The reg_equiv[REGNO].replace
2976          optimization may move the set of this register immediately before
2977          insn, which puts it after reg_equiv[REGNO].init_insns, and hence
2978          the mention in the REG_EQUIV note would be to an uninitialized
2979          pseudo.  */
2980
2981       if (MEM_P (dest) && REG_P (src)
2982           && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
2983           && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
2984           && DF_REG_DEF_COUNT (regno) == 1
2985           && reg_equiv[regno].init_insns != 0
2986           && reg_equiv[regno].init_insns != const0_rtx
2987           && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
2988                               REG_EQUIV, NULL_RTX)
2989           && ! contains_replace_regs (XEXP (dest, 0)))
2990         {
2991           rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
2992           if (validate_equiv_mem (init_insn, src, dest)
2993               && ! memref_used_between_p (dest, init_insn, insn)
2994               /* Attaching a REG_EQUIV note will fail if INIT_INSN has
2995                  multiple sets.  */
2996               && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
2997             {
2998               /* This insn makes the equivalence, not the one initializing
2999                  the register.  */
3000               reg_equiv_init (regno)
3001                 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
3002               df_notes_rescan (init_insn);
3003             }
3004         }
3005     }
3006
3007   cleared_regs = BITMAP_ALLOC (NULL);
3008   /* Now scan all regs killed in an insn to see if any of them are
3009      registers only used that once.  If so, see if we can replace the
3010      reference with the equivalent form.  If we can, delete the
3011      initializing reference and this register will go away.  If we
3012      can't replace the reference, and the initializing reference is
3013      within the same loop (or in an inner loop), then move the register
3014      initialization just before the use, so that they are in the same
3015      basic block.  */
3016   FOR_EACH_BB_REVERSE (bb)
3017     {
3018       loop_depth = bb->loop_depth;
3019       for (insn = BB_END (bb);
3020            insn != PREV_INSN (BB_HEAD (bb));
3021            insn = PREV_INSN (insn))
3022         {
3023           rtx link;
3024
3025           if (! INSN_P (insn))
3026             continue;
3027
3028           /* Don't substitute into a non-local goto, this confuses CFG.  */
3029           if (JUMP_P (insn)
3030               && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
3031             continue;
3032
3033           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3034             {
3035               if (REG_NOTE_KIND (link) == REG_DEAD
3036                   /* Make sure this insn still refers to the register.  */
3037                   && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
3038                 {
3039                   int regno = REGNO (XEXP (link, 0));
3040                   rtx equiv_insn;
3041
3042                   if (! reg_equiv[regno].replace
3043                       || reg_equiv[regno].loop_depth < loop_depth
3044                       /* There is no sense to move insns if we did
3045                          register pressure-sensitive scheduling was
3046                          done because it will not improve allocation
3047                          but worsen insn schedule with a big
3048                          probability.  */
3049                       || (flag_sched_pressure && flag_schedule_insns))
3050                     continue;
3051
3052                   /* reg_equiv[REGNO].replace gets set only when
3053                      REG_N_REFS[REGNO] is 2, i.e. the register is set
3054                      once and used once.  (If it were only set, but not used,
3055                      flow would have deleted the setting insns.)  Hence
3056                      there can only be one insn in reg_equiv[REGNO].init_insns.  */
3057                   gcc_assert (reg_equiv[regno].init_insns
3058                               && !XEXP (reg_equiv[regno].init_insns, 1));
3059                   equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
3060
3061                   /* We may not move instructions that can throw, since
3062                      that changes basic block boundaries and we are not
3063                      prepared to adjust the CFG to match.  */
3064                   if (can_throw_internal (equiv_insn))
3065                     continue;
3066
3067                   if (asm_noperands (PATTERN (equiv_insn)) < 0
3068                       && validate_replace_rtx (regno_reg_rtx[regno],
3069                                                *(reg_equiv[regno].src_p), insn))
3070                     {
3071                       rtx equiv_link;
3072                       rtx last_link;
3073                       rtx note;
3074
3075                       /* Find the last note.  */
3076                       for (last_link = link; XEXP (last_link, 1);
3077                            last_link = XEXP (last_link, 1))
3078                         ;
3079
3080                       /* Append the REG_DEAD notes from equiv_insn.  */
3081                       equiv_link = REG_NOTES (equiv_insn);
3082                       while (equiv_link)
3083                         {
3084                           note = equiv_link;
3085                           equiv_link = XEXP (equiv_link, 1);
3086                           if (REG_NOTE_KIND (note) == REG_DEAD)
3087                             {
3088                               remove_note (equiv_insn, note);
3089                               XEXP (last_link, 1) = note;
3090                               XEXP (note, 1) = NULL_RTX;
3091                               last_link = note;
3092                             }
3093                         }
3094
3095                       remove_death (regno, insn);
3096                       SET_REG_N_REFS (regno, 0);
3097                       REG_FREQ (regno) = 0;
3098                       delete_insn (equiv_insn);
3099
3100                       reg_equiv[regno].init_insns
3101                         = XEXP (reg_equiv[regno].init_insns, 1);
3102
3103                       reg_equiv_init (regno) = NULL_RTX;
3104                       bitmap_set_bit (cleared_regs, regno);
3105                     }
3106                   /* Move the initialization of the register to just before
3107                      INSN.  Update the flow information.  */
3108                   else if (prev_nondebug_insn (insn) != equiv_insn)
3109                     {
3110                       rtx new_insn;
3111
3112                       new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
3113                       REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
3114                       REG_NOTES (equiv_insn) = 0;
3115                       /* Rescan it to process the notes.  */
3116                       df_insn_rescan (new_insn);
3117
3118                       /* Make sure this insn is recognized before
3119                          reload begins, otherwise
3120                          eliminate_regs_in_insn will die.  */
3121                       INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
3122
3123                       delete_insn (equiv_insn);
3124
3125                       XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
3126
3127                       REG_BASIC_BLOCK (regno) = bb->index;
3128                       REG_N_CALLS_CROSSED (regno) = 0;
3129                       REG_FREQ_CALLS_CROSSED (regno) = 0;
3130                       REG_N_THROWING_CALLS_CROSSED (regno) = 0;
3131                       REG_LIVE_LENGTH (regno) = 2;
3132
3133                       if (insn == BB_HEAD (bb))
3134                         BB_HEAD (bb) = PREV_INSN (insn);
3135
3136                       reg_equiv_init (regno)
3137                         = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
3138                       bitmap_set_bit (cleared_regs, regno);
3139                     }
3140                 }
3141             }
3142         }
3143     }
3144
3145   if (!bitmap_empty_p (cleared_regs))
3146     {
3147       FOR_EACH_BB (bb)
3148         {
3149           bitmap_and_compl_into (DF_LIVE_IN (bb), cleared_regs);
3150           bitmap_and_compl_into (DF_LIVE_OUT (bb), cleared_regs);
3151           bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
3152           bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
3153         }
3154
3155       /* Last pass - adjust debug insns referencing cleared regs.  */
3156       if (MAY_HAVE_DEBUG_INSNS)
3157         for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
3158           if (DEBUG_INSN_P (insn))
3159             {
3160               rtx old_loc = INSN_VAR_LOCATION_LOC (insn);
3161               INSN_VAR_LOCATION_LOC (insn)
3162                 = simplify_replace_fn_rtx (old_loc, NULL_RTX,
3163                                            adjust_cleared_regs,
3164                                            (void *) cleared_regs);
3165               if (old_loc != INSN_VAR_LOCATION_LOC (insn))
3166                 df_insn_rescan (insn);
3167             }
3168     }
3169
3170   BITMAP_FREE (cleared_regs);
3171
3172   out:
3173   /* Clean up.  */
3174
3175   end_alias_analysis ();
3176   free (reg_equiv);
3177   return recorded_label_ref;
3178 }
3179
3180 \f
3181
3182 /* Print chain C to FILE.  */
3183 static void
3184 print_insn_chain (FILE *file, struct insn_chain *c)
3185 {
3186   fprintf (file, "insn=%d, ", INSN_UID(c->insn));
3187   bitmap_print (file, &c->live_throughout, "live_throughout: ", ", ");
3188   bitmap_print (file, &c->dead_or_set, "dead_or_set: ", "\n");
3189 }
3190
3191
3192 /* Print all reload_insn_chains to FILE.  */
3193 static void
3194 print_insn_chains (FILE *file)
3195 {
3196   struct insn_chain *c;
3197   for (c = reload_insn_chain; c ; c = c->next)
3198     print_insn_chain (file, c);
3199 }
3200
3201 /* Return true if pseudo REGNO should be added to set live_throughout
3202    or dead_or_set of the insn chains for reload consideration.  */
3203 static bool
3204 pseudo_for_reload_consideration_p (int regno)
3205 {
3206   /* Consider spilled pseudos too for IRA because they still have a
3207      chance to get hard-registers in the reload when IRA is used.  */
3208   return (reg_renumber[regno] >= 0 || ira_conflicts_p);
3209 }
3210
3211 /* Init LIVE_SUBREGS[ALLOCNUM] and LIVE_SUBREGS_USED[ALLOCNUM] using
3212    REG to the number of nregs, and INIT_VALUE to get the
3213    initialization.  ALLOCNUM need not be the regno of REG.  */
3214 static void
3215 init_live_subregs (bool init_value, sbitmap *live_subregs,
3216                    int *live_subregs_used, int allocnum, rtx reg)
3217 {
3218   unsigned int regno = REGNO (SUBREG_REG (reg));
3219   int size = GET_MODE_SIZE (GET_MODE (regno_reg_rtx[regno]));
3220
3221   gcc_assert (size > 0);
3222
3223   /* Been there, done that.  */
3224   if (live_subregs_used[allocnum])
3225     return;
3226
3227   /* Create a new one with zeros.  */
3228   if (live_subregs[allocnum] == NULL)
3229     live_subregs[allocnum] = sbitmap_alloc (size);
3230
3231   /* If the entire reg was live before blasting into subregs, we need
3232      to init all of the subregs to ones else init to 0.  */
3233   if (init_value)
3234     sbitmap_ones (live_subregs[allocnum]);
3235   else
3236     sbitmap_zero (live_subregs[allocnum]);
3237
3238   /* Set the number of bits that we really want.  */
3239   live_subregs_used[allocnum] = size;
3240 }
3241
3242 /* Walk the insns of the current function and build reload_insn_chain,
3243    and record register life information.  */
3244 static void
3245 build_insn_chain (void)
3246 {
3247   unsigned int i;
3248   struct insn_chain **p = &reload_insn_chain;
3249   basic_block bb;
3250   struct insn_chain *c = NULL;
3251   struct insn_chain *next = NULL;
3252   bitmap live_relevant_regs = BITMAP_ALLOC (NULL);
3253   bitmap elim_regset = BITMAP_ALLOC (NULL);
3254   /* live_subregs is a vector used to keep accurate information about
3255      which hardregs are live in multiword pseudos.  live_subregs and
3256      live_subregs_used are indexed by pseudo number.  The live_subreg
3257      entry for a particular pseudo is only used if the corresponding
3258      element is non zero in live_subregs_used.  The value in
3259      live_subregs_used is number of bytes that the pseudo can
3260      occupy.  */
3261   sbitmap *live_subregs = XCNEWVEC (sbitmap, max_regno);
3262   int *live_subregs_used = XNEWVEC (int, max_regno);
3263
3264   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
3265     if (TEST_HARD_REG_BIT (eliminable_regset, i))
3266       bitmap_set_bit (elim_regset, i);
3267   FOR_EACH_BB_REVERSE (bb)
3268     {
3269       bitmap_iterator bi;
3270       rtx insn;
3271
3272       CLEAR_REG_SET (live_relevant_regs);
3273       memset (live_subregs_used, 0, max_regno * sizeof (int));
3274
3275       EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb), 0, i, bi)
3276         {
3277           if (i >= FIRST_PSEUDO_REGISTER)
3278             break;
3279           bitmap_set_bit (live_relevant_regs, i);
3280         }
3281
3282       EXECUTE_IF_SET_IN_BITMAP (DF_LR_OUT (bb),
3283                                 FIRST_PSEUDO_REGISTER, i, bi)
3284         {
3285           if (pseudo_for_reload_consideration_p (i))
3286             bitmap_set_bit (live_relevant_regs, i);
3287         }
3288
3289       FOR_BB_INSNS_REVERSE (bb, insn)
3290         {
3291           if (!NOTE_P (insn) && !BARRIER_P (insn))
3292             {
3293               unsigned int uid = INSN_UID (insn);
3294               df_ref *def_rec;
3295               df_ref *use_rec;
3296
3297               c = new_insn_chain ();
3298               c->next = next;
3299               next = c;
3300               *p = c;
3301               p = &c->prev;
3302
3303               c->insn = insn;
3304               c->block = bb->index;
3305
3306               if (INSN_P (insn))
3307                 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3308                   {
3309                     df_ref def = *def_rec;
3310                     unsigned int regno = DF_REF_REGNO (def);
3311
3312                     /* Ignore may clobbers because these are generated
3313                        from calls. However, every other kind of def is
3314                        added to dead_or_set.  */
3315                     if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
3316                       {
3317                         if (regno < FIRST_PSEUDO_REGISTER)
3318                           {
3319                             if (!fixed_regs[regno])
3320                               bitmap_set_bit (&c->dead_or_set, regno);
3321                           }
3322                         else if (pseudo_for_reload_consideration_p (regno))
3323                           bitmap_set_bit (&c->dead_or_set, regno);
3324                       }
3325
3326                     if ((regno < FIRST_PSEUDO_REGISTER
3327                          || reg_renumber[regno] >= 0
3328                          || ira_conflicts_p)
3329                         && (!DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL)))
3330                       {
3331                         rtx reg = DF_REF_REG (def);
3332
3333                         /* We can model subregs, but not if they are
3334                            wrapped in ZERO_EXTRACTS.  */
3335                         if (GET_CODE (reg) == SUBREG
3336                             && !DF_REF_FLAGS_IS_SET (def, DF_REF_ZERO_EXTRACT))
3337                           {
3338                             unsigned int start = SUBREG_BYTE (reg);
3339                             unsigned int last = start
3340                               + GET_MODE_SIZE (GET_MODE (reg));
3341
3342                             init_live_subregs
3343                               (bitmap_bit_p (live_relevant_regs, regno),
3344                                live_subregs, live_subregs_used, regno, reg);
3345
3346                             if (!DF_REF_FLAGS_IS_SET
3347                                 (def, DF_REF_STRICT_LOW_PART))
3348                               {
3349                                 /* Expand the range to cover entire words.
3350                                    Bytes added here are "don't care".  */
3351                                 start
3352                                   = start / UNITS_PER_WORD * UNITS_PER_WORD;
3353                                 last = ((last + UNITS_PER_WORD - 1)
3354                                         / UNITS_PER_WORD * UNITS_PER_WORD);
3355                               }
3356
3357                             /* Ignore the paradoxical bits.  */
3358                             if ((int)last > live_subregs_used[regno])
3359                               last = live_subregs_used[regno];
3360
3361                             while (start < last)
3362                               {
3363                                 RESET_BIT (live_subregs[regno], start);
3364                                 start++;
3365                               }
3366
3367                             if (sbitmap_empty_p (live_subregs[regno]))
3368                               {
3369                                 live_subregs_used[regno] = 0;
3370                                 bitmap_clear_bit (live_relevant_regs, regno);
3371                               }
3372                             else
3373                               /* Set live_relevant_regs here because
3374                                  that bit has to be true to get us to
3375                                  look at the live_subregs fields.  */
3376                               bitmap_set_bit (live_relevant_regs, regno);
3377                           }
3378                         else
3379                           {
3380                             /* DF_REF_PARTIAL is generated for
3381                                subregs, STRICT_LOW_PART, and
3382                                ZERO_EXTRACT.  We handle the subreg
3383                                case above so here we have to keep from
3384                                modeling the def as a killing def.  */
3385                             if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL))
3386                               {
3387                                 bitmap_clear_bit (live_relevant_regs, regno);
3388                                 live_subregs_used[regno] = 0;
3389                               }
3390                           }
3391                       }
3392                   }
3393
3394               bitmap_and_compl_into (live_relevant_regs, elim_regset);
3395               bitmap_copy (&c->live_throughout, live_relevant_regs);
3396
3397               if (INSN_P (insn))
3398                 for (use_rec = DF_INSN_UID_USES (uid); *use_rec; use_rec++)
3399                   {
3400                     df_ref use = *use_rec;
3401                     unsigned int regno = DF_REF_REGNO (use);
3402                     rtx reg = DF_REF_REG (use);
3403
3404                     /* DF_REF_READ_WRITE on a use means that this use
3405                        is fabricated from a def that is a partial set
3406                        to a multiword reg.  Here, we only model the
3407                        subreg case that is not wrapped in ZERO_EXTRACT
3408                        precisely so we do not need to look at the
3409                        fabricated use. */
3410                     if (DF_REF_FLAGS_IS_SET (use, DF_REF_READ_WRITE)
3411                         && !DF_REF_FLAGS_IS_SET (use, DF_REF_ZERO_EXTRACT)
3412                         && DF_REF_FLAGS_IS_SET (use, DF_REF_SUBREG))
3413                       continue;
3414
3415                     /* Add the last use of each var to dead_or_set.  */
3416                     if (!bitmap_bit_p (live_relevant_regs, regno))
3417                       {
3418                         if (regno < FIRST_PSEUDO_REGISTER)
3419                           {
3420                             if (!fixed_regs[regno])
3421                               bitmap_set_bit (&c->dead_or_set, regno);
3422                           }
3423                         else if (pseudo_for_reload_consideration_p (regno))
3424                           bitmap_set_bit (&c->dead_or_set, regno);
3425                       }