1 /* Allocate registers within a basic block, for GNU compiler.
2 Copyright (C) 1987, 1988, 1991, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 Free Software Foundation, Inc.
6 This file is part of GCC.
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
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
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/>. */
22 /* Allocation of hard register numbers to pseudo registers is done in
23 two passes. In this pass we consider only regs that are born and
24 die once within one basic block. We do this one basic block at a
25 time. Then the next pass allocates the registers that remain.
26 Two passes are used because this pass uses methods that work only
27 on linear code, but that do a better job than the general methods
28 used in global_alloc, and more quickly too.
30 The assignments made are recorded in the vector reg_renumber
31 whose space is allocated here. The rtl code itself is not altered.
33 We assign each instruction in the basic block a number
34 which is its order from the beginning of the block.
35 Then we can represent the lifetime of a pseudo register with
36 a pair of numbers, and check for conflicts easily.
37 We can record the availability of hard registers with a
38 HARD_REG_SET for each instruction. The HARD_REG_SET
39 contains 0 or 1 for each hard reg.
41 To avoid register shuffling, we tie registers together when one
42 dies by being copied into another, or dies in an instruction that
43 does arithmetic to produce another. The tied registers are
44 allocated as one. Registers with different reg class preferences
45 can never be tied unless the class preferred by one is a subclass
46 of the one preferred by the other.
48 Tying is represented with "quantity numbers".
49 A non-tied register is given a new quantity number.
50 Tied registers have the same quantity number.
52 We have provision to exempt registers, even when they are contained
53 within the block, that can be tied to others that are not contained in it.
54 This is so that global_alloc could process them both and tie them then.
55 But this is currently disabled since tying in global_alloc is not
58 /* Pseudos allocated here can be reallocated by global.c if the hard register
59 is used as a spill register. Currently we don't allocate such pseudos
60 here if their preferred class is likely to be used by spills. */
64 #include "coretypes.h"
66 #include "hard-reg-set.h"
72 #include "insn-config.h"
73 #include "insn-attr.h"
78 #include "integrate.h"
82 #include "tree-pass.h"
87 /* Next quantity number available for allocation. */
91 /* Information we maintain about each quantity. */
94 /* The number of refs to quantity Q. */
98 /* The frequency of uses of quantity Q. */
102 /* Insn number (counting from head of basic block)
103 where quantity Q was born. -1 if birth has not been recorded. */
107 /* Insn number (counting from head of basic block)
108 where given quantity died. Due to the way tying is done,
109 and the fact that we consider in this pass only regs that die but once,
110 a quantity can die only once. Each quantity's life span
111 is a set of consecutive insns. -1 if death has not been recorded. */
115 /* Number of words needed to hold the data in given quantity.
116 This depends on its machine mode. It is used for these purposes:
117 1. It is used in computing the relative importance of qtys,
118 which determines the order in which we look for regs for them.
119 2. It is used in rules that prevent tying several registers of
120 different sizes in a way that is geometrically impossible
121 (see combine_regs). */
125 /* Number of times a reg tied to given qty lives across a CALL_INSN. */
129 /* Number of times a reg tied to given qty lives across a CALL_INSN
132 int n_throwing_calls_crossed;
134 /* The register number of one pseudo register whose reg_qty value is Q.
135 This register should be the head of the chain
136 maintained in reg_next_in_qty. */
140 /* Reg class contained in (smaller than) the preferred classes of all
141 the pseudo regs that are tied in given quantity.
142 This is the preferred class for allocating that quantity. */
144 enum reg_class min_class;
146 /* Register class within which we allocate given qty if we can't get
147 its preferred class. */
149 enum reg_class alternate_class;
151 /* This holds the mode of the registers that are tied to given qty,
152 or VOIDmode if registers with differing modes are tied together. */
154 enum machine_mode mode;
156 /* the hard reg number chosen for given quantity,
157 or -1 if none was found. */
162 static struct qty *qty;
164 /* These fields are kept separately to speedup their clearing. */
166 /* We maintain two hard register sets that indicate suggested hard registers
167 for each quantity. The first, phys_copy_sugg, contains hard registers
168 that are tied to the quantity by a simple copy. The second contains all
169 hard registers that are tied to the quantity via an arithmetic operation.
171 The former register set is given priority for allocation. This tends to
172 eliminate copy insns. */
174 /* Element Q is a set of hard registers that are suggested for quantity Q by
177 static HARD_REG_SET *qty_phys_copy_sugg;
179 /* Element Q is a set of hard registers that are suggested for quantity Q by
182 static HARD_REG_SET *qty_phys_sugg;
184 /* Element Q is the number of suggested registers in qty_phys_copy_sugg. */
186 static short *qty_phys_num_copy_sugg;
188 /* Element Q is the number of suggested registers in qty_phys_sugg. */
190 static short *qty_phys_num_sugg;
192 /* If (REG N) has been assigned a quantity number, is a register number
193 of another register assigned the same quantity number, or -1 for the
194 end of the chain. qty->first_reg point to the head of this chain. */
196 static int *reg_next_in_qty;
198 /* reg_qty[N] (where N is a pseudo reg number) is the qty number of that reg
200 of -1 if this register cannot be allocated by local-alloc,
201 or -2 if not known yet.
203 Note that if we see a use or death of pseudo register N with
204 reg_qty[N] == -2, register N must be local to the current block. If
205 it were used in more than one block, we would have reg_qty[N] == -1.
206 This relies on the fact that if reg_basic_block[N] is >= 0, register N
207 will not appear in any other block. We save a considerable number of
208 tests by exploiting this.
210 If N is < FIRST_PSEUDO_REGISTER, reg_qty[N] is undefined and should not
215 /* The offset (in words) of register N within its quantity.
216 This can be nonzero if register N is SImode, and has been tied
217 to a subreg of a DImode register. */
219 static char *reg_offset;
221 /* Vector of substitutions of register numbers,
222 used to map pseudo regs into hardware regs.
223 This is set up as a result of register allocation.
224 Element N is the hard reg assigned to pseudo reg N,
225 or is -1 if no hard reg was assigned.
226 If N is a hard reg number, element N is N. */
230 /* Set of hard registers live at the current point in the scan
231 of the instructions in a basic block. */
233 static HARD_REG_SET regs_live;
235 /* Each set of hard registers indicates registers live at a particular
236 point in the basic block. For N even, regs_live_at[N] says which
237 hard registers are needed *after* insn N/2 (i.e., they may not
238 conflict with the outputs of insn N/2 or the inputs of insn N/2 + 1.
240 If an object is to conflict with the inputs of insn J but not the
241 outputs of insn J + 1, we say it is born at index J*2 - 1. Similarly,
242 if it is to conflict with the outputs of insn J but not the inputs of
243 insn J + 1, it is said to die at index J*2 + 1. */
245 static HARD_REG_SET *regs_live_at;
247 /* Communicate local vars `insn_number' and `insn'
248 from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_qty'. */
249 static int this_insn_number;
250 static rtx this_insn;
254 /* Set when an attempt should be made to replace a register
255 with the associated src_p entry. */
259 /* Set when a REG_EQUIV note is found or created. Use to
260 keep track of what memory accesses might be created later,
267 /* Loop depth is used to recognize equivalences which appear
268 to be present within the same loop (or in an inner loop). */
272 /* The list of each instruction which initializes this register. */
276 /* Nonzero if this had a preexisting REG_EQUIV note. */
278 int is_arg_equivalence;
281 /* reg_equiv[N] (where N is a pseudo reg number) is the equivalence
282 structure for that register. */
284 static struct equivalence *reg_equiv;
286 /* Nonzero if we recorded an equivalence for a LABEL_REF. */
287 static int recorded_label_ref;
289 static void alloc_qty (int, enum machine_mode, int, int);
290 static void validate_equiv_mem_from_store (rtx, rtx, void *);
291 static int validate_equiv_mem (rtx, rtx, rtx);
292 static int equiv_init_varies_p (rtx);
293 static int equiv_init_movable_p (rtx, int);
294 static int contains_replace_regs (rtx);
295 static int memref_referenced_p (rtx, rtx);
296 static int memref_used_between_p (rtx, rtx, rtx);
297 static void update_equiv_regs (void);
298 static void no_equiv (rtx, rtx, void *);
299 static void block_alloc (int);
300 static int qty_sugg_compare (int, int);
301 static int qty_sugg_compare_1 (const void *, const void *);
302 static int qty_compare (int, int);
303 static int qty_compare_1 (const void *, const void *);
304 static int combine_regs (rtx, rtx, int, int, rtx, int);
305 static int reg_meets_class_p (int, enum reg_class);
306 static void update_qty_class (int, int);
307 static void reg_is_set (rtx, rtx, void *);
308 static void reg_is_born (rtx, int);
309 static void wipe_dead_reg (rtx, int);
310 static int find_free_reg (enum reg_class, enum machine_mode, int, int, int,
312 static void mark_life (int, enum machine_mode, int);
313 static void post_mark_life (int, enum machine_mode, int, int, int);
314 static int no_conflict_p (rtx, rtx, rtx);
315 static int requires_inout (const char *);
317 /* Allocate a new quantity (new within current basic block)
318 for register number REGNO which is born at index BIRTH
319 within the block. MODE and SIZE are info on reg REGNO. */
322 alloc_qty (int regno, enum machine_mode mode, int size, int birth)
324 int qtyno = next_qty++;
326 reg_qty[regno] = qtyno;
327 reg_offset[regno] = 0;
328 reg_next_in_qty[regno] = -1;
330 qty[qtyno].first_reg = regno;
331 qty[qtyno].size = size;
332 qty[qtyno].mode = mode;
333 qty[qtyno].birth = birth;
334 qty[qtyno].n_calls_crossed = REG_N_CALLS_CROSSED (regno);
335 qty[qtyno].n_throwing_calls_crossed = REG_N_THROWING_CALLS_CROSSED (regno);
336 qty[qtyno].min_class = reg_preferred_class (regno);
337 qty[qtyno].alternate_class = reg_alternate_class (regno);
338 qty[qtyno].n_refs = REG_N_REFS (regno);
339 qty[qtyno].freq = REG_FREQ (regno);
342 /* Main entry point of this file. */
351 /* We need to keep track of whether or not we recorded a LABEL_REF so
352 that we know if the jump optimizer needs to be rerun. */
353 recorded_label_ref = 0;
355 /* Leaf functions and non-leaf functions have different needs.
356 If defined, let the machine say what kind of ordering we
358 #ifdef ORDER_REGS_FOR_LOCAL_ALLOC
359 ORDER_REGS_FOR_LOCAL_ALLOC;
362 /* Promote REG_EQUAL notes to REG_EQUIV notes and adjust status of affected
364 update_equiv_regs ();
366 /* This sets the maximum number of quantities we can have. Quantity
367 numbers start at zero and we can have one for each pseudo. */
368 max_qty = (max_regno - FIRST_PSEUDO_REGISTER);
370 /* Allocate vectors of temporary data.
371 See the declarations of these variables, above,
372 for what they mean. */
374 qty = XNEWVEC (struct qty, max_qty);
375 qty_phys_copy_sugg = XNEWVEC (HARD_REG_SET, max_qty);
376 qty_phys_num_copy_sugg = XNEWVEC (short, max_qty);
377 qty_phys_sugg = XNEWVEC (HARD_REG_SET, max_qty);
378 qty_phys_num_sugg = XNEWVEC (short, max_qty);
380 reg_qty = XNEWVEC (int, max_regno);
381 reg_offset = XNEWVEC (char, max_regno);
382 reg_next_in_qty = XNEWVEC (int, max_regno);
384 /* Determine which pseudo-registers can be allocated by local-alloc.
385 In general, these are the registers used only in a single block and
388 We need not be concerned with which block actually uses the register
389 since we will never see it outside that block. */
391 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
393 if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS && REG_N_DEATHS (i) == 1)
399 /* Force loop below to initialize entire quantity array. */
402 /* Allocate each block's local registers, block by block. */
406 /* NEXT_QTY indicates which elements of the `qty_...'
407 vectors might need to be initialized because they were used
408 for the previous block; it is set to the entire array before
409 block 0. Initialize those, with explicit loop if there are few,
410 else with bzero and bcopy. Do not initialize vectors that are
411 explicit set by `alloc_qty'. */
415 for (i = 0; i < next_qty; i++)
417 CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]);
418 qty_phys_num_copy_sugg[i] = 0;
419 CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
420 qty_phys_num_sugg[i] = 0;
425 #define CLEAR(vector) \
426 memset ((vector), 0, (sizeof (*(vector))) * next_qty);
428 CLEAR (qty_phys_copy_sugg);
429 CLEAR (qty_phys_num_copy_sugg);
430 CLEAR (qty_phys_sugg);
431 CLEAR (qty_phys_num_sugg);
436 block_alloc (b->index);
440 free (qty_phys_copy_sugg);
441 free (qty_phys_num_copy_sugg);
442 free (qty_phys_sugg);
443 free (qty_phys_num_sugg);
447 free (reg_next_in_qty);
449 return recorded_label_ref;
452 /* Used for communication between the following two functions: contains
453 a MEM that we wish to ensure remains unchanged. */
454 static rtx equiv_mem;
456 /* Set nonzero if EQUIV_MEM is modified. */
457 static int equiv_mem_modified;
459 /* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified.
460 Called via note_stores. */
463 validate_equiv_mem_from_store (rtx dest, rtx set ATTRIBUTE_UNUSED,
464 void *data ATTRIBUTE_UNUSED)
467 && reg_overlap_mentioned_p (dest, equiv_mem))
469 && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p)))
470 equiv_mem_modified = 1;
473 /* Verify that no store between START and the death of REG invalidates
474 MEMREF. MEMREF is invalidated by modifying a register used in MEMREF,
475 by storing into an overlapping memory location, or with a non-const
478 Return 1 if MEMREF remains valid. */
481 validate_equiv_mem (rtx start, rtx reg, rtx memref)
487 equiv_mem_modified = 0;
489 /* If the memory reference has side effects or is volatile, it isn't a
490 valid equivalence. */
491 if (side_effects_p (memref))
494 for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn))
499 if (find_reg_note (insn, REG_DEAD, reg))
502 if (CALL_P (insn) && ! MEM_READONLY_P (memref)
503 && ! CONST_OR_PURE_CALL_P (insn))
506 note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL);
508 /* If a register mentioned in MEMREF is modified via an
509 auto-increment, we lose the equivalence. Do the same if one
510 dies; although we could extend the life, it doesn't seem worth
513 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
514 if ((REG_NOTE_KIND (note) == REG_INC
515 || REG_NOTE_KIND (note) == REG_DEAD)
516 && REG_P (XEXP (note, 0))
517 && reg_overlap_mentioned_p (XEXP (note, 0), memref))
524 /* Returns zero if X is known to be invariant. */
527 equiv_init_varies_p (rtx x)
529 RTX_CODE code = GET_CODE (x);
536 return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0));
547 return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0);
550 if (MEM_VOLATILE_P (x))
559 fmt = GET_RTX_FORMAT (code);
560 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
563 if (equiv_init_varies_p (XEXP (x, i)))
566 else if (fmt[i] == 'E')
569 for (j = 0; j < XVECLEN (x, i); j++)
570 if (equiv_init_varies_p (XVECEXP (x, i, j)))
577 /* Returns nonzero if X (used to initialize register REGNO) is movable.
578 X is only movable if the registers it uses have equivalent initializations
579 which appear to be within the same loop (or in an inner loop) and movable
580 or if they are not candidates for local_alloc and don't vary. */
583 equiv_init_movable_p (rtx x, int regno)
587 enum rtx_code code = GET_CODE (x);
592 return equiv_init_movable_p (SET_SRC (x), regno);
607 return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth
608 && reg_equiv[REGNO (x)].replace)
609 || (REG_BASIC_BLOCK (REGNO (x)) < NUM_FIXED_BLOCKS && ! rtx_varies_p (x, 0));
611 case UNSPEC_VOLATILE:
615 if (MEM_VOLATILE_P (x))
624 fmt = GET_RTX_FORMAT (code);
625 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
629 if (! equiv_init_movable_p (XEXP (x, i), regno))
633 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
634 if (! equiv_init_movable_p (XVECEXP (x, i, j), regno))
642 /* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true. */
645 contains_replace_regs (rtx x)
649 enum rtx_code code = GET_CODE (x);
665 return reg_equiv[REGNO (x)].replace;
671 fmt = GET_RTX_FORMAT (code);
672 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
676 if (contains_replace_regs (XEXP (x, i)))
680 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
681 if (contains_replace_regs (XVECEXP (x, i, j)))
689 /* TRUE if X references a memory location that would be affected by a store
693 memref_referenced_p (rtx memref, rtx x)
697 enum rtx_code code = GET_CODE (x);
714 return (reg_equiv[REGNO (x)].replacement
715 && memref_referenced_p (memref,
716 reg_equiv[REGNO (x)].replacement));
719 if (true_dependence (memref, VOIDmode, x, rtx_varies_p))
724 /* If we are setting a MEM, it doesn't count (its address does), but any
725 other SET_DEST that has a MEM in it is referencing the MEM. */
726 if (MEM_P (SET_DEST (x)))
728 if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0)))
731 else if (memref_referenced_p (memref, SET_DEST (x)))
734 return memref_referenced_p (memref, SET_SRC (x));
740 fmt = GET_RTX_FORMAT (code);
741 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
745 if (memref_referenced_p (memref, XEXP (x, i)))
749 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
750 if (memref_referenced_p (memref, XVECEXP (x, i, j)))
758 /* TRUE if some insn in the range (START, END] references a memory location
759 that would be affected by a store to MEMREF. */
762 memref_used_between_p (rtx memref, rtx start, rtx end)
766 for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
767 insn = NEXT_INSN (insn))
772 if (memref_referenced_p (memref, PATTERN (insn)))
775 /* Nonconst functions may access memory. */
777 && (! CONST_OR_PURE_CALL_P (insn)
778 || pure_call_p (insn)))
785 /* Find registers that are equivalent to a single value throughout the
786 compilation (either because they can be referenced in memory or are set once
787 from a single constant). Lower their priority for a register.
789 If such a register is only referenced once, try substituting its value
790 into the using insn. If it succeeds, we can eliminate the register
793 Initialize the REG_EQUIV_INIT array of initializing insns. */
796 update_equiv_regs (void)
803 reg_equiv = XCNEWVEC (struct equivalence, max_regno);
804 reg_equiv_init = ggc_alloc_cleared (max_regno * sizeof (rtx));
805 reg_equiv_init_size = max_regno;
807 init_alias_analysis ();
809 /* Scan the insns and find which registers have equivalences. Do this
810 in a separate scan of the insns because (due to -fcse-follow-jumps)
811 a register can be set below its use. */
814 loop_depth = bb->loop_depth;
816 for (insn = BB_HEAD (bb);
817 insn != NEXT_INSN (BB_END (bb));
818 insn = NEXT_INSN (insn))
828 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
829 if (REG_NOTE_KIND (note) == REG_INC)
830 no_equiv (XEXP (note, 0), note, NULL);
832 set = single_set (insn);
834 /* If this insn contains more (or less) than a single SET,
835 only mark all destinations as having no known equivalence. */
838 note_stores (PATTERN (insn), no_equiv, NULL);
841 else if (GET_CODE (PATTERN (insn)) == PARALLEL)
845 for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
847 rtx part = XVECEXP (PATTERN (insn), 0, i);
849 note_stores (part, no_equiv, NULL);
853 dest = SET_DEST (set);
856 /* See if this is setting up the equivalence between an argument
857 register and its stack slot. */
858 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
861 gcc_assert (REG_P (dest));
862 regno = REGNO (dest);
864 /* Note that we don't want to clear reg_equiv_init even if there
865 are multiple sets of this register. */
866 reg_equiv[regno].is_arg_equivalence = 1;
868 /* Record for reload that this is an equivalencing insn. */
869 if (rtx_equal_p (src, XEXP (note, 0)))
870 reg_equiv_init[regno]
871 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
873 /* Continue normally in case this is a candidate for
880 /* We only handle the case of a pseudo register being set
881 once, or always to the same value. */
882 /* ??? The mn10200 port breaks if we add equivalences for
883 values that need an ADDRESS_REGS register and set them equivalent
884 to a MEM of a pseudo. The actual problem is in the over-conservative
885 handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in
886 calculate_needs, but we traditionally work around this problem
887 here by rejecting equivalences when the destination is in a register
888 that's likely spilled. This is fragile, of course, since the
889 preferred class of a pseudo depends on all instructions that set
893 || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
894 || reg_equiv[regno].init_insns == const0_rtx
895 || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno))
896 && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence))
898 /* This might be setting a SUBREG of a pseudo, a pseudo that is
899 also set somewhere else to a constant. */
900 note_stores (set, no_equiv, NULL);
904 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
906 /* cse sometimes generates function invariants, but doesn't put a
907 REG_EQUAL note on the insn. Since this note would be redundant,
908 there's no point creating it earlier than here. */
909 if (! note && ! rtx_varies_p (src, 0))
910 note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
912 /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST
913 since it represents a function call */
914 if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST)
917 if (DF_REG_DEF_COUNT (regno) != 1
919 || rtx_varies_p (XEXP (note, 0), 0)
920 || (reg_equiv[regno].replacement
921 && ! rtx_equal_p (XEXP (note, 0),
922 reg_equiv[regno].replacement))))
924 no_equiv (dest, set, NULL);
927 /* Record this insn as initializing this register. */
928 reg_equiv[regno].init_insns
929 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns);
931 /* If this register is known to be equal to a constant, record that
932 it is always equivalent to the constant. */
933 if (DF_REG_DEF_COUNT (regno) == 1
934 && note && ! rtx_varies_p (XEXP (note, 0), 0))
936 rtx note_value = XEXP (note, 0);
937 remove_note (insn, note);
938 set_unique_reg_note (insn, REG_EQUIV, note_value);
941 /* If this insn introduces a "constant" register, decrease the priority
942 of that register. Record this insn if the register is only used once
943 more and the equivalence value is the same as our source.
945 The latter condition is checked for two reasons: First, it is an
946 indication that it may be more efficient to actually emit the insn
947 as written (if no registers are available, reload will substitute
948 the equivalence). Secondly, it avoids problems with any registers
949 dying in this insn whose death notes would be missed.
951 If we don't have a REG_EQUIV note, see if this insn is loading
952 a register used only in one basic block from a MEM. If so, and the
953 MEM remains unchanged for the life of the register, add a REG_EQUIV
956 note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
958 if (note == 0 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
959 && MEM_P (SET_SRC (set))
960 && validate_equiv_mem (insn, dest, SET_SRC (set)))
961 note = set_unique_reg_note (insn, REG_EQUIV, copy_rtx (SET_SRC (set)));
965 int regno = REGNO (dest);
966 rtx x = XEXP (note, 0);
968 /* If we haven't done so, record for reload that this is an
969 equivalencing insn. */
970 if (!reg_equiv[regno].is_arg_equivalence)
971 reg_equiv_init[regno]
972 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]);
974 /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
975 We might end up substituting the LABEL_REF for uses of the
976 pseudo here or later. That kind of transformation may turn an
977 indirect jump into a direct jump, in which case we must rerun the
978 jump optimizer to ensure that the JUMP_LABEL fields are valid. */
979 if (GET_CODE (x) == LABEL_REF
980 || (GET_CODE (x) == CONST
981 && GET_CODE (XEXP (x, 0)) == PLUS
982 && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF)))
983 recorded_label_ref = 1;
985 reg_equiv[regno].replacement = x;
986 reg_equiv[regno].src_p = &SET_SRC (set);
987 reg_equiv[regno].loop_depth = loop_depth;
989 /* Don't mess with things live during setjmp. */
990 if (REG_LIVE_LENGTH (regno) >= 0 && optimize)
992 /* Note that the statement below does not affect the priority
994 REG_LIVE_LENGTH (regno) *= 2;
996 /* If the register is referenced exactly twice, meaning it is
997 set once and used once, indicate that the reference may be
998 replaced by the equivalence we computed above. Do this
999 even if the register is only used in one block so that
1000 dependencies can be handled where the last register is
1001 used in a different block (i.e. HIGH / LO_SUM sequences)
1002 and to reduce the number of registers alive across
1005 if (REG_N_REFS (regno) == 2
1006 && (rtx_equal_p (x, src)
1007 || ! equiv_init_varies_p (src))
1008 && NONJUMP_INSN_P (insn)
1009 && equiv_init_movable_p (PATTERN (insn), regno))
1010 reg_equiv[regno].replace = 1;
1019 /* A second pass, to gather additional equivalences with memory. This needs
1020 to be done after we know which registers we are going to replace. */
1022 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1027 if (! INSN_P (insn))
1030 set = single_set (insn);
1034 dest = SET_DEST (set);
1035 src = SET_SRC (set);
1037 /* If this sets a MEM to the contents of a REG that is only used
1038 in a single basic block, see if the register is always equivalent
1039 to that memory location and if moving the store from INSN to the
1040 insn that set REG is safe. If so, put a REG_EQUIV note on the
1043 Don't add a REG_EQUIV note if the insn already has one. The existing
1044 REG_EQUIV is likely more useful than the one we are adding.
1046 If one of the regs in the address has reg_equiv[REGNO].replace set,
1047 then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace
1048 optimization may move the set of this register immediately before
1049 insn, which puts it after reg_equiv[REGNO].init_insns, and hence
1050 the mention in the REG_EQUIV note would be to an uninitialized
1053 if (MEM_P (dest) && REG_P (src)
1054 && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER
1055 && REG_BASIC_BLOCK (regno) >= NUM_FIXED_BLOCKS
1056 && DF_REG_DEF_COUNT (regno) == 1
1057 && reg_equiv[regno].init_insns != 0
1058 && reg_equiv[regno].init_insns != const0_rtx
1059 && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0),
1060 REG_EQUIV, NULL_RTX)
1061 && ! contains_replace_regs (XEXP (dest, 0)))
1063 rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0);
1064 if (validate_equiv_mem (init_insn, src, dest)
1065 && ! memref_used_between_p (dest, init_insn, insn)
1066 /* Attaching a REG_EQUIV note will fail if INIT_INSN has
1068 && set_unique_reg_note (init_insn, REG_EQUIV, copy_rtx (dest)))
1070 /* This insn makes the equivalence, not the one initializing
1072 reg_equiv_init[regno]
1073 = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
1074 df_notes_rescan (init_insn);
1079 cleared_regs = BITMAP_ALLOC (NULL);
1080 /* Now scan all regs killed in an insn to see if any of them are
1081 registers only used that once. If so, see if we can replace the
1082 reference with the equivalent form. If we can, delete the
1083 initializing reference and this register will go away. If we
1084 can't replace the reference, and the initializing reference is
1085 within the same loop (or in an inner loop), then move the register
1086 initialization just before the use, so that they are in the same
1088 FOR_EACH_BB_REVERSE (bb)
1090 loop_depth = bb->loop_depth;
1091 for (insn = BB_END (bb);
1092 insn != PREV_INSN (BB_HEAD (bb));
1093 insn = PREV_INSN (insn))
1097 if (! INSN_P (insn))
1100 /* Don't substitute into a non-local goto, this confuses CFG. */
1102 && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
1105 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1107 if (REG_NOTE_KIND (link) == REG_DEAD
1108 /* Make sure this insn still refers to the register. */
1109 && reg_mentioned_p (XEXP (link, 0), PATTERN (insn)))
1111 int regno = REGNO (XEXP (link, 0));
1114 if (! reg_equiv[regno].replace
1115 || reg_equiv[regno].loop_depth < loop_depth)
1118 /* reg_equiv[REGNO].replace gets set only when
1119 REG_N_REFS[REGNO] is 2, i.e. the register is set
1120 once and used once. (If it were only set, but not used,
1121 flow would have deleted the setting insns.) Hence
1122 there can only be one insn in reg_equiv[REGNO].init_insns. */
1123 gcc_assert (reg_equiv[regno].init_insns
1124 && !XEXP (reg_equiv[regno].init_insns, 1));
1125 equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
1127 /* We may not move instructions that can throw, since
1128 that changes basic block boundaries and we are not
1129 prepared to adjust the CFG to match. */
1130 if (can_throw_internal (equiv_insn))
1133 if (asm_noperands (PATTERN (equiv_insn)) < 0
1134 && validate_replace_rtx (regno_reg_rtx[regno],
1135 *(reg_equiv[regno].src_p), insn))
1141 /* Find the last note. */
1142 for (last_link = link; XEXP (last_link, 1);
1143 last_link = XEXP (last_link, 1))
1146 /* Append the REG_DEAD notes from equiv_insn. */
1147 equiv_link = REG_NOTES (equiv_insn);
1151 equiv_link = XEXP (equiv_link, 1);
1152 if (REG_NOTE_KIND (note) == REG_DEAD)
1154 remove_note (equiv_insn, note);
1155 XEXP (last_link, 1) = note;
1156 XEXP (note, 1) = NULL_RTX;
1161 remove_death (regno, insn);
1162 SET_REG_N_REFS (regno, 0);
1163 REG_FREQ (regno) = 0;
1164 delete_insn (equiv_insn);
1166 reg_equiv[regno].init_insns
1167 = XEXP (reg_equiv[regno].init_insns, 1);
1169 reg_equiv_init[regno] = NULL_RTX;
1170 bitmap_set_bit (cleared_regs, regno);
1172 /* Move the initialization of the register to just before
1173 INSN. Update the flow information. */
1174 else if (PREV_INSN (insn) != equiv_insn)
1178 new_insn = emit_insn_before (PATTERN (equiv_insn), insn);
1179 REG_NOTES (new_insn) = REG_NOTES (equiv_insn);
1180 REG_NOTES (equiv_insn) = 0;
1182 /* Make sure this insn is recognized before
1183 reload begins, otherwise
1184 eliminate_regs_in_insn will die. */
1185 INSN_CODE (new_insn) = INSN_CODE (equiv_insn);
1187 delete_insn (equiv_insn);
1189 XEXP (reg_equiv[regno].init_insns, 0) = new_insn;
1191 REG_BASIC_BLOCK (regno) = bb->index;
1192 REG_N_CALLS_CROSSED (regno) = 0;
1193 REG_N_THROWING_CALLS_CROSSED (regno) = 0;
1194 REG_LIVE_LENGTH (regno) = 2;
1196 if (insn == BB_HEAD (bb))
1197 BB_HEAD (bb) = PREV_INSN (insn);
1199 reg_equiv_init[regno]
1200 = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
1201 bitmap_set_bit (cleared_regs, regno);
1208 if (!bitmap_empty_p (cleared_regs))
1211 bitmap_and_compl_into (DF_RA_LIVE_IN (bb), cleared_regs);
1212 if (DF_RA_LIVE_TOP (bb))
1213 bitmap_and_compl_into (DF_RA_LIVE_TOP (bb), cleared_regs);
1214 bitmap_and_compl_into (DF_RA_LIVE_OUT (bb), cleared_regs);
1215 bitmap_and_compl_into (DF_LR_IN (bb), cleared_regs);
1217 bitmap_and_compl_into (DF_LR_TOP (bb), cleared_regs);
1218 bitmap_and_compl_into (DF_LR_OUT (bb), cleared_regs);
1221 BITMAP_FREE (cleared_regs);
1226 end_alias_analysis ();
1230 /* Mark REG as having no known equivalence.
1231 Some instructions might have been processed before and furnished
1232 with REG_EQUIV notes for this register; these notes will have to be
1234 STORE is the piece of RTL that does the non-constant / conflicting
1235 assignment - a SET, CLOBBER or REG_INC note. It is currently not used,
1236 but needs to be there because this function is called from note_stores. */
1238 no_equiv (rtx reg, rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
1245 regno = REGNO (reg);
1246 list = reg_equiv[regno].init_insns;
1247 if (list == const0_rtx)
1249 reg_equiv[regno].init_insns = const0_rtx;
1250 reg_equiv[regno].replacement = NULL_RTX;
1251 /* This doesn't matter for equivalences made for argument registers, we
1252 should keep their initialization insns. */
1253 if (reg_equiv[regno].is_arg_equivalence)
1255 reg_equiv_init[regno] = NULL_RTX;
1256 for (; list; list = XEXP (list, 1))
1258 rtx insn = XEXP (list, 0);
1259 remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX));
1263 /* Allocate hard regs to the pseudo regs used only within block number B.
1264 Only the pseudos that die but once can be handled. */
1272 int insn_number = 0;
1274 int max_uid = get_max_uid ();
1276 int no_conflict_combined_regno = -1;
1278 /* Count the instructions in the basic block. */
1280 insn = BB_END (BASIC_BLOCK (b));
1286 gcc_assert (insn_count <= max_uid);
1288 if (insn == BB_HEAD (BASIC_BLOCK (b)))
1290 insn = PREV_INSN (insn);
1293 /* +2 to leave room for a post_mark_life at the last insn and for
1294 the birth of a CLOBBER in the first insn. */
1295 regs_live_at = XCNEWVEC (HARD_REG_SET, 2 * insn_count + 2);
1297 /* Initialize table of hardware registers currently live. */
1299 REG_SET_TO_HARD_REG_SET (regs_live, DF_LR_TOP (BASIC_BLOCK (b)));
1301 /* This loop scans the instructions of the basic block
1302 and assigns quantities to registers.
1303 It computes which registers to tie. */
1305 insn = BB_HEAD (BASIC_BLOCK (b));
1315 rtx r0, r1 = NULL_RTX;
1316 int combined_regno = -1;
1319 this_insn_number = insn_number;
1322 extract_insn (insn);
1323 which_alternative = -1;
1325 /* Is this insn suitable for tying two registers?
1326 If so, try doing that.
1327 Suitable insns are those with at least two operands and where
1328 operand 0 is an output that is a register that is not
1331 We can tie operand 0 with some operand that dies in this insn.
1332 First look for operands that are required to be in the same
1333 register as operand 0. If we find such, only try tying that
1334 operand or one that can be put into that operand if the
1335 operation is commutative. If we don't find an operand
1336 that is required to be in the same register as operand 0,
1337 we can tie with any operand.
1339 Subregs in place of regs are also ok.
1341 If tying is done, WIN is set nonzero. */
1344 && recog_data.n_operands > 1
1345 && recog_data.constraints[0][0] == '='
1346 && recog_data.constraints[0][1] != '&')
1348 /* If non-negative, is an operand that must match operand 0. */
1349 int must_match_0 = -1;
1350 /* Counts number of alternatives that require a match with
1352 int n_matching_alts = 0;
1354 for (i = 1; i < recog_data.n_operands; i++)
1356 const char *p = recog_data.constraints[i];
1357 int this_match = requires_inout (p);
1359 n_matching_alts += this_match;
1360 if (this_match == recog_data.n_alternatives)
1364 r0 = recog_data.operand[0];
1365 for (i = 1; i < recog_data.n_operands; i++)
1367 /* Skip this operand if we found an operand that
1368 must match operand 0 and this operand isn't it
1369 and can't be made to be it by commutativity. */
1371 if (must_match_0 >= 0 && i != must_match_0
1372 && ! (i == must_match_0 + 1
1373 && recog_data.constraints[i-1][0] == '%')
1374 && ! (i == must_match_0 - 1
1375 && recog_data.constraints[i][0] == '%'))
1378 /* Likewise if each alternative has some operand that
1379 must match operand zero. In that case, skip any
1380 operand that doesn't list operand 0 since we know that
1381 the operand always conflicts with operand 0. We
1382 ignore commutativity in this case to keep things simple. */
1383 if (n_matching_alts == recog_data.n_alternatives
1384 && 0 == requires_inout (recog_data.constraints[i]))
1387 r1 = recog_data.operand[i];
1389 /* If the operand is an address, find a register in it.
1390 There may be more than one register, but we only try one
1392 if (recog_data.constraints[i][0] == 'p'
1393 || EXTRA_ADDRESS_CONSTRAINT (recog_data.constraints[i][0],
1394 recog_data.constraints[i]))
1395 while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
1398 /* Avoid making a call-saved register unnecessarily
1400 hard_reg = get_hard_reg_initial_reg (cfun, r1);
1401 if (hard_reg != NULL_RTX)
1403 if (REG_P (hard_reg)
1404 && REGNO (hard_reg) < FIRST_PSEUDO_REGISTER
1405 && !call_used_regs[REGNO (hard_reg)])
1409 if (REG_P (r0) || GET_CODE (r0) == SUBREG)
1411 /* We have two priorities for hard register preferences.
1412 If we have a move insn or an insn whose first input
1413 can only be in the same register as the output, give
1414 priority to an equivalence found from that insn. */
1416 = (r1 == recog_data.operand[i] && must_match_0 >= 0);
1418 if (REG_P (r1) || GET_CODE (r1) == SUBREG)
1419 win = combine_regs (r1, r0, may_save_copy,
1420 insn_number, insn, 0);
1427 /* Recognize an insn sequence with an ultimate result
1428 which can safely overlap one of the inputs.
1429 The sequence begins with a CLOBBER of its result,
1430 and ends with an insn that copies the result to itself
1431 and has a REG_EQUAL note for an equivalent formula.
1432 That note indicates what the inputs are.
1433 The result and the input can overlap if each insn in
1434 the sequence either doesn't mention the input
1435 or has a REG_NO_CONFLICT note to inhibit the conflict.
1437 We do the combining test at the CLOBBER so that the
1438 destination register won't have had a quantity number
1439 assigned, since that would prevent combining. */
1442 && GET_CODE (PATTERN (insn)) == CLOBBER
1443 && (r0 = XEXP (PATTERN (insn), 0),
1445 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
1446 && XEXP (link, 0) != 0
1447 && NONJUMP_INSN_P (XEXP (link, 0))
1448 && (set = single_set (XEXP (link, 0))) != 0
1449 && SET_DEST (set) == r0 && SET_SRC (set) == r0
1450 && (note = find_reg_note (XEXP (link, 0), REG_EQUAL,
1453 if (r1 = XEXP (note, 0), REG_P (r1)
1454 /* Check that we have such a sequence. */
1455 && no_conflict_p (insn, r0, r1))
1456 win = combine_regs (r1, r0, 1, insn_number, insn, 1);
1457 else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e'
1458 && (r1 = XEXP (XEXP (note, 0), 0),
1459 REG_P (r1) || GET_CODE (r1) == SUBREG)
1460 && no_conflict_p (insn, r0, r1))
1461 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1463 /* Here we care if the operation to be computed is
1465 else if (COMMUTATIVE_P (XEXP (note, 0))
1466 && (r1 = XEXP (XEXP (note, 0), 1),
1467 (REG_P (r1) || GET_CODE (r1) == SUBREG))
1468 && no_conflict_p (insn, r0, r1))
1469 win = combine_regs (r1, r0, 0, insn_number, insn, 1);
1471 /* If we did combine something, show the register number
1472 in question so that we know to ignore its death. */
1474 no_conflict_combined_regno = REGNO (r1);
1477 /* If registers were just tied, set COMBINED_REGNO
1478 to the number of the register used in this insn
1479 that was tied to the register set in this insn.
1480 This register's qty should not be "killed". */
1484 while (GET_CODE (r1) == SUBREG)
1485 r1 = SUBREG_REG (r1);
1486 combined_regno = REGNO (r1);
1489 /* Mark the death of everything that dies in this instruction,
1490 except for anything that was just combined. */
1492 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1493 if (REG_NOTE_KIND (link) == REG_DEAD
1494 && REG_P (XEXP (link, 0))
1495 && combined_regno != (int) REGNO (XEXP (link, 0))
1496 && (no_conflict_combined_regno != (int) REGNO (XEXP (link, 0))
1497 || ! find_reg_note (insn, REG_NO_CONFLICT,
1499 wipe_dead_reg (XEXP (link, 0), 0);
1501 /* Allocate qty numbers for all registers local to this block
1502 that are born (set) in this instruction.
1503 A pseudo that already has a qty is not changed. */
1505 note_stores (PATTERN (insn), reg_is_set, NULL);
1507 /* If anything is set in this insn and then unused, mark it as dying
1508 after this insn, so it will conflict with our outputs. This
1509 can't match with something that combined, and it doesn't matter
1510 if it did. Do this after the calls to reg_is_set since these
1511 die after, not during, the current insn. */
1513 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1514 if (REG_NOTE_KIND (link) == REG_UNUSED
1515 && REG_P (XEXP (link, 0)))
1516 wipe_dead_reg (XEXP (link, 0), 1);
1518 /* If this is an insn that has a REG_RETVAL note pointing at a
1519 CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
1520 block, so clear any register number that combined within it. */
1521 if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0
1522 && NONJUMP_INSN_P (XEXP (note, 0))
1523 && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER)
1524 no_conflict_combined_regno = -1;
1527 /* Set the registers live after INSN_NUMBER. Note that we never
1528 record the registers live before the block's first insn, since no
1529 pseudos we care about are live before that insn. */
1531 IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live);
1532 IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live);
1534 if (insn == BB_END (BASIC_BLOCK (b)))
1537 insn = NEXT_INSN (insn);
1540 /* Now every register that is local to this basic block
1541 should have been given a quantity, or else -1 meaning ignore it.
1542 Every quantity should have a known birth and death.
1544 Order the qtys so we assign them registers in order of the
1545 number of suggested registers they need so we allocate those with
1546 the most restrictive needs first. */
1548 qty_order = XNEWVEC (int, next_qty);
1549 for (i = 0; i < next_qty; i++)
1552 #define EXCHANGE(I1, I2) \
1553 { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1558 /* Make qty_order[2] be the one to allocate last. */
1559 if (qty_sugg_compare (0, 1) > 0)
1561 if (qty_sugg_compare (1, 2) > 0)
1564 /* ... Fall through ... */
1566 /* Put the best one to allocate in qty_order[0]. */
1567 if (qty_sugg_compare (0, 1) > 0)
1570 /* ... Fall through ... */
1574 /* Nothing to do here. */
1578 qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1);
1581 /* Try to put each quantity in a suggested physical register, if it has one.
1582 This may cause registers to be allocated that otherwise wouldn't be, but
1583 this seems acceptable in local allocation (unlike global allocation). */
1584 for (i = 0; i < next_qty; i++)
1587 if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0)
1588 qty[q].phys_reg = find_free_reg (qty[q].min_class, qty[q].mode, q,
1589 0, 1, qty[q].birth, qty[q].death);
1591 qty[q].phys_reg = -1;
1594 /* Order the qtys so we assign them registers in order of
1595 decreasing length of life. Normally call qsort, but if we
1596 have only a very small number of quantities, sort them ourselves. */
1598 for (i = 0; i < next_qty; i++)
1601 #define EXCHANGE(I1, I2) \
1602 { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
1607 /* Make qty_order[2] be the one to allocate last. */
1608 if (qty_compare (0, 1) > 0)
1610 if (qty_compare (1, 2) > 0)
1613 /* ... Fall through ... */
1615 /* Put the best one to allocate in qty_order[0]. */
1616 if (qty_compare (0, 1) > 0)
1619 /* ... Fall through ... */
1623 /* Nothing to do here. */
1627 qsort (qty_order, next_qty, sizeof (int), qty_compare_1);
1630 /* Now for each qty that is not a hardware register,
1631 look for a hardware register to put it in.
1632 First try the register class that is cheapest for this qty,
1633 if there is more than one class. */
1635 for (i = 0; i < next_qty; i++)
1638 if (qty[q].phys_reg < 0)
1640 #ifdef INSN_SCHEDULING
1641 /* These values represent the adjusted lifetime of a qty so
1642 that it conflicts with qtys which appear near the start/end
1643 of this qty's lifetime.
1645 The purpose behind extending the lifetime of this qty is to
1646 discourage the register allocator from creating false
1649 The adjustment value is chosen to indicate that this qty
1650 conflicts with all the qtys in the instructions immediately
1651 before and after the lifetime of this qty.
1653 Experiments have shown that higher values tend to hurt
1654 overall code performance.
1656 If allocation using the extended lifetime fails we will try
1657 again with the qty's unadjusted lifetime. */
1658 int fake_birth = MAX (0, qty[q].birth - 2 + qty[q].birth % 2);
1659 int fake_death = MIN (insn_number * 2 + 1,
1660 qty[q].death + 2 - qty[q].death % 2);
1663 if (N_REG_CLASSES > 1)
1665 #ifdef INSN_SCHEDULING
1666 /* We try to avoid using hard registers allocated to qtys which
1667 are born immediately after this qty or die immediately before
1670 This optimization is only appropriate when we will run
1671 a scheduling pass after reload and we are not optimizing
1673 if (flag_schedule_insns_after_reload && dbg_cnt (local_alloc_for_sched)
1675 && !SMALL_REGISTER_CLASSES)
1677 qty[q].phys_reg = find_free_reg (qty[q].min_class,
1678 qty[q].mode, q, 0, 0,
1679 fake_birth, fake_death);
1680 if (qty[q].phys_reg >= 0)
1684 qty[q].phys_reg = find_free_reg (qty[q].min_class,
1685 qty[q].mode, q, 0, 0,
1686 qty[q].birth, qty[q].death);
1687 if (qty[q].phys_reg >= 0)
1691 #ifdef INSN_SCHEDULING
1692 /* Similarly, avoid false dependencies. */
1693 if (flag_schedule_insns_after_reload && dbg_cnt (local_alloc_for_sched)
1695 && !SMALL_REGISTER_CLASSES
1696 && qty[q].alternate_class != NO_REGS)
1697 qty[q].phys_reg = find_free_reg (qty[q].alternate_class,
1698 qty[q].mode, q, 0, 0,
1699 fake_birth, fake_death);
1701 if (qty[q].alternate_class != NO_REGS)
1702 qty[q].phys_reg = find_free_reg (qty[q].alternate_class,
1703 qty[q].mode, q, 0, 0,
1704 qty[q].birth, qty[q].death);
1708 /* Now propagate the register assignments
1709 to the pseudo regs belonging to the qtys. */
1711 for (q = 0; q < next_qty; q++)
1712 if (qty[q].phys_reg >= 0)
1714 for (i = qty[q].first_reg; i >= 0; i = reg_next_in_qty[i])
1715 reg_renumber[i] = qty[q].phys_reg + reg_offset[i];
1719 free (regs_live_at);
1723 /* Compare two quantities' priority for getting real registers.
1724 We give shorter-lived quantities higher priority.
1725 Quantities with more references are also preferred, as are quantities that
1726 require multiple registers. This is the identical prioritization as
1727 done by global-alloc.
1729 We used to give preference to registers with *longer* lives, but using
1730 the same algorithm in both local- and global-alloc can speed up execution
1731 of some programs by as much as a factor of three! */
1733 /* Note that the quotient will never be bigger than
1734 the value of floor_log2 times the maximum number of
1735 times a register can occur in one insn (surely less than 100)
1736 weighted by frequency (max REG_FREQ_MAX).
1737 Multiplying this by 10000/REG_FREQ_MAX can't overflow.
1738 QTY_CMP_PRI is also used by qty_sugg_compare. */
1740 #define QTY_CMP_PRI(q) \
1741 ((int) (((double) (floor_log2 (qty[q].n_refs) * qty[q].freq * qty[q].size) \
1742 / (qty[q].death - qty[q].birth)) * (10000 / REG_FREQ_MAX)))
1745 qty_compare (int q1, int q2)
1747 return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1751 qty_compare_1 (const void *q1p, const void *q2p)
1753 int q1 = *(const int *) q1p, q2 = *(const int *) q2p;
1754 int tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1759 /* If qtys are equally good, sort by qty number,
1760 so that the results of qsort leave nothing to chance. */
1764 /* Compare two quantities' priority for getting real registers. This version
1765 is called for quantities that have suggested hard registers. First priority
1766 goes to quantities that have copy preferences, then to those that have
1767 normal preferences. Within those groups, quantities with the lower
1768 number of preferences have the highest priority. Of those, we use the same
1769 algorithm as above. */
1771 #define QTY_CMP_SUGG(q) \
1772 (qty_phys_num_copy_sugg[q] \
1773 ? qty_phys_num_copy_sugg[q] \
1774 : qty_phys_num_sugg[q] * FIRST_PSEUDO_REGISTER)
1777 qty_sugg_compare (int q1, int q2)
1779 int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
1784 return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1788 qty_sugg_compare_1 (const void *q1p, const void *q2p)
1790 int q1 = *(const int *) q1p, q2 = *(const int *) q2p;
1791 int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2);
1796 tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1);
1800 /* If qtys are equally good, sort by qty number,
1801 so that the results of qsort leave nothing to chance. */
1808 /* Attempt to combine the two registers (rtx's) USEDREG and SETREG.
1809 Returns 1 if have done so, or 0 if cannot.
1811 Combining registers means marking them as having the same quantity
1812 and adjusting the offsets within the quantity if either of
1815 We don't actually combine a hard reg with a pseudo; instead
1816 we just record the hard reg as the suggestion for the pseudo's quantity.
1817 If we really combined them, we could lose if the pseudo lives
1818 across an insn that clobbers the hard reg (eg, movmem).
1820 ALREADY_DEAD is nonzero if USEDREG is known to be dead even though
1821 there is no REG_DEAD note on INSN. This occurs during the processing
1822 of REG_NO_CONFLICT blocks.
1824 MAY_SAVE_COPY is nonzero if this insn is simply copying USEDREG to
1825 SETREG or if the input and output must share a register.
1826 In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG.
1828 There are elaborate checks for the validity of combining. */
1831 combine_regs (rtx usedreg, rtx setreg, int may_save_copy, int insn_number,
1832 rtx insn, int already_dead)
1839 /* Determine the numbers and sizes of registers being used. If a subreg
1840 is present that does not change the entire register, don't consider
1841 this a copy insn. */
1843 while (GET_CODE (usedreg) == SUBREG)
1845 rtx subreg = SUBREG_REG (usedreg);
1849 if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD)
1852 if (REGNO (subreg) < FIRST_PSEUDO_REGISTER)
1853 offset += subreg_regno_offset (REGNO (subreg),
1855 SUBREG_BYTE (usedreg),
1856 GET_MODE (usedreg));
1858 offset += (SUBREG_BYTE (usedreg)
1859 / REGMODE_NATURAL_SIZE (GET_MODE (usedreg)));
1865 if (!REG_P (usedreg))
1868 ureg = REGNO (usedreg);
1869 if (ureg < FIRST_PSEUDO_REGISTER)
1870 usize = hard_regno_nregs[ureg][GET_MODE (usedreg)];
1872 usize = ((GET_MODE_SIZE (GET_MODE (usedreg))
1873 + (REGMODE_NATURAL_SIZE (GET_MODE (usedreg)) - 1))
1874 / REGMODE_NATURAL_SIZE (GET_MODE (usedreg)));
1876 while (GET_CODE (setreg) == SUBREG)
1878 rtx subreg = SUBREG_REG (setreg);
1882 if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD)
1885 if (REGNO (subreg) < FIRST_PSEUDO_REGISTER)
1886 offset -= subreg_regno_offset (REGNO (subreg),
1888 SUBREG_BYTE (setreg),
1891 offset -= (SUBREG_BYTE (setreg)
1892 / REGMODE_NATURAL_SIZE (GET_MODE (setreg)));
1898 if (!REG_P (setreg))
1901 sreg = REGNO (setreg);
1902 if (sreg < FIRST_PSEUDO_REGISTER)
1903 ssize = hard_regno_nregs[sreg][GET_MODE (setreg)];
1905 ssize = ((GET_MODE_SIZE (GET_MODE (setreg))
1906 + (REGMODE_NATURAL_SIZE (GET_MODE (setreg)) - 1))
1907 / REGMODE_NATURAL_SIZE (GET_MODE (setreg)));
1909 /* If UREG is a pseudo-register that hasn't already been assigned a
1910 quantity number, it means that it is not local to this block or dies
1911 more than once. In either event, we can't do anything with it. */
1912 if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0)
1913 /* Do not combine registers unless one fits within the other. */
1914 || (offset > 0 && usize + offset > ssize)
1915 || (offset < 0 && usize + offset < ssize)
1916 /* Do not combine with a smaller already-assigned object
1917 if that smaller object is already combined with something bigger. */
1918 || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
1919 && usize < qty[reg_qty[ureg]].size)
1920 /* Can't combine if SREG is not a register we can allocate. */
1921 || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1)
1922 /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note.
1923 These have already been taken care of. This probably wouldn't
1924 combine anyway, but don't take any chances. */
1925 || (ureg >= FIRST_PSEUDO_REGISTER
1926 && find_reg_note (insn, REG_NO_CONFLICT, usedreg))
1927 /* Don't tie something to itself. In most cases it would make no
1928 difference, but it would screw up if the reg being tied to itself
1929 also dies in this insn. */
1931 /* Don't try to connect two different hardware registers. */
1932 || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER)
1933 /* Don't connect two different machine modes if they have different
1934 implications as to which registers may be used. */
1935 || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg)))
1938 /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in
1939 qty_phys_sugg for the pseudo instead of tying them.
1941 Return "failure" so that the lifespan of UREG is terminated here;
1942 that way the two lifespans will be disjoint and nothing will prevent
1943 the pseudo reg from being given this hard reg. */
1945 if (ureg < FIRST_PSEUDO_REGISTER)
1947 /* Allocate a quantity number so we have a place to put our
1949 if (reg_qty[sreg] == -2)
1950 reg_is_born (setreg, 2 * insn_number);
1952 if (reg_qty[sreg] >= 0)
1955 && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg))
1957 SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
1958 qty_phys_num_copy_sugg[reg_qty[sreg]]++;
1960 else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg))
1962 SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
1963 qty_phys_num_sugg[reg_qty[sreg]]++;
1969 /* Similarly for SREG a hard register and UREG a pseudo register. */
1971 if (sreg < FIRST_PSEUDO_REGISTER)
1974 && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg))
1976 SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
1977 qty_phys_num_copy_sugg[reg_qty[ureg]]++;
1979 else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg))
1981 SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
1982 qty_phys_num_sugg[reg_qty[ureg]]++;
1987 /* At this point we know that SREG and UREG are both pseudos.
1988 Do nothing if SREG already has a quantity or is a register that we
1990 if (reg_qty[sreg] >= -1
1991 /* If we are not going to let any regs live across calls,
1992 don't tie a call-crossing reg to a non-call-crossing reg. */
1993 || (current_function_has_nonlocal_label
1994 && ((REG_N_CALLS_CROSSED (ureg) > 0)
1995 != (REG_N_CALLS_CROSSED (sreg) > 0))))
1998 /* We don't already know about SREG, so tie it to UREG
1999 if this is the last use of UREG, provided the classes they want
2002 if ((already_dead || find_regno_note (insn, REG_DEAD, ureg))
2003 && reg_meets_class_p (sreg, qty[reg_qty[ureg]].min_class))
2005 /* Add SREG to UREG's quantity. */
2006 sqty = reg_qty[ureg];
2007 reg_qty[sreg] = sqty;
2008 reg_offset[sreg] = reg_offset[ureg] + offset;
2009 reg_next_in_qty[sreg] = qty[sqty].first_reg;
2010 qty[sqty].first_reg = sreg;
2012 /* If SREG's reg class is smaller, set qty[SQTY].min_class. */
2013 update_qty_class (sqty, sreg);
2015 /* Update info about quantity SQTY. */
2016 qty[sqty].n_calls_crossed += REG_N_CALLS_CROSSED (sreg);
2017 qty[sqty].n_throwing_calls_crossed
2018 += REG_N_THROWING_CALLS_CROSSED (sreg);
2019 qty[sqty].n_refs += REG_N_REFS (sreg);
2020 qty[sqty].freq += REG_FREQ (sreg);
2025 for (i = qty[sqty].first_reg; i >= 0; i = reg_next_in_qty[i])
2026 reg_offset[i] -= offset;
2028 qty[sqty].size = ssize;
2029 qty[sqty].mode = GET_MODE (setreg);
2038 /* Return 1 if the preferred class of REG allows it to be tied
2039 to a quantity or register whose class is CLASS.
2040 True if REG's reg class either contains or is contained in CLASS. */
2043 reg_meets_class_p (int reg, enum reg_class class)
2045 enum reg_class rclass = reg_preferred_class (reg);
2046 return (reg_class_subset_p (rclass, class)
2047 || reg_class_subset_p (class, rclass));
2050 /* Update the class of QTYNO assuming that REG is being tied to it. */
2053 update_qty_class (int qtyno, int reg)
2055 enum reg_class rclass = reg_preferred_class (reg);
2056 if (reg_class_subset_p (rclass, qty[qtyno].min_class))
2057 qty[qtyno].min_class = rclass;
2059 rclass = reg_alternate_class (reg);
2060 if (reg_class_subset_p (rclass, qty[qtyno].alternate_class))
2061 qty[qtyno].alternate_class = rclass;
2064 /* Handle something which alters the value of an rtx REG.
2066 REG is whatever is set or clobbered. SETTER is the rtx that
2067 is modifying the register.
2069 If it is not really a register, we do nothing.
2070 The file-global variables `this_insn' and `this_insn_number'
2071 carry info from `block_alloc'. */
2074 reg_is_set (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
2076 /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of
2077 a hard register. These may actually not exist any more. */
2079 if (GET_CODE (reg) != SUBREG
2083 /* Mark this register as being born. If it is used in a CLOBBER, mark
2084 it as being born halfway between the previous insn and this insn so that
2085 it conflicts with our inputs but not the outputs of the previous insn. */
2087 reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER));
2090 /* Handle beginning of the life of register REG.
2091 BIRTH is the index at which this is happening. */
2094 reg_is_born (rtx reg, int birth)
2098 if (GET_CODE (reg) == SUBREG)
2100 regno = REGNO (SUBREG_REG (reg));
2101 if (regno < FIRST_PSEUDO_REGISTER)
2102 regno = subreg_regno (reg);
2105 regno = REGNO (reg);
2107 if (regno < FIRST_PSEUDO_REGISTER)
2109 mark_life (regno, GET_MODE (reg), 1);
2111 /* If the register was to have been born earlier that the present
2112 insn, mark it as live where it is actually born. */
2113 if (birth < 2 * this_insn_number)
2114 post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number);
2118 if (reg_qty[regno] == -2)
2119 alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth);
2121 /* If this register has a quantity number, show that it isn't dead. */
2122 if (reg_qty[regno] >= 0)
2123 qty[reg_qty[regno]].death = -1;
2127 /* Record the death of REG in the current insn. If OUTPUT_P is nonzero,
2128 REG is an output that is dying (i.e., it is never used), otherwise it
2129 is an input (the normal case).
2130 If OUTPUT_P is 1, then we extend the life past the end of this insn. */
2133 wipe_dead_reg (rtx reg, int output_p)
2135 int regno = REGNO (reg);
2137 /* If this insn has multiple results,
2138 and the dead reg is used in one of the results,
2139 extend its life to after this insn,
2140 so it won't get allocated together with any other result of this insn.
2142 It is unsafe to use !single_set here since it will ignore an unused
2143 output. Just because an output is unused does not mean the compiler
2144 can assume the side effect will not occur. Consider if REG appears
2145 in the address of an output and we reload the output. If we allocate
2146 REG to the same hard register as an unused output we could set the hard
2147 register before the output reload insn. */
2148 if (GET_CODE (PATTERN (this_insn)) == PARALLEL
2149 && multiple_sets (this_insn))
2152 for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--)
2154 rtx set = XVECEXP (PATTERN (this_insn), 0, i);
2155 if (GET_CODE (set) == SET
2156 && !REG_P (SET_DEST (set))
2157 && !rtx_equal_p (reg, SET_DEST (set))
2158 && reg_overlap_mentioned_p (reg, SET_DEST (set)))
2163 /* If this register is used in an auto-increment address, then extend its
2164 life to after this insn, so that it won't get allocated together with
2165 the result of this insn. */
2166 if (! output_p && find_regno_note (this_insn, REG_INC, regno))
2169 if (regno < FIRST_PSEUDO_REGISTER)
2171 mark_life (regno, GET_MODE (reg), 0);
2173 /* If a hard register is dying as an output, mark it as in use at
2174 the beginning of this insn (the above statement would cause this
2177 post_mark_life (regno, GET_MODE (reg), 1,
2178 2 * this_insn_number, 2 * this_insn_number + 1);
2181 else if (reg_qty[regno] >= 0)
2182 qty[reg_qty[regno]].death = 2 * this_insn_number + output_p;
2185 /* Find a block of SIZE words of hard regs in reg_class CLASS
2186 that can hold something of machine-mode MODE
2187 (but actually we test only the first of the block for holding MODE)
2188 and still free between insn BORN_INDEX and insn DEAD_INDEX,
2189 and return the number of the first of them.
2190 Return -1 if such a block cannot be found.
2191 If QTYNO crosses calls, insist on a register preserved by calls,
2192 unless ACCEPT_CALL_CLOBBERED is nonzero.
2194 If JUST_TRY_SUGGESTED is nonzero, only try to see if the suggested
2195 register is available. If not, return -1. */
2198 find_free_reg (enum reg_class class, enum machine_mode mode, int qtyno,
2199 int accept_call_clobbered, int just_try_suggested,
2200 int born_index, int dead_index)
2203 HARD_REG_SET first_used, used;
2204 #ifdef ELIMINABLE_REGS
2205 static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
2208 /* Validate our parameters. */
2209 gcc_assert (born_index >= 0 && born_index <= dead_index);
2211 /* Don't let a pseudo live in a reg across a function call
2212 if we might get a nonlocal goto. */
2213 if (current_function_has_nonlocal_label
2214 && qty[qtyno].n_calls_crossed > 0)
2217 if (accept_call_clobbered)
2218 COPY_HARD_REG_SET (used, call_fixed_reg_set);
2219 else if (qty[qtyno].n_calls_crossed == 0)
2220 COPY_HARD_REG_SET (used, fixed_reg_set);
2222 COPY_HARD_REG_SET (used, call_used_reg_set);
2224 if (accept_call_clobbered)
2225 IOR_HARD_REG_SET (used, losing_caller_save_reg_set);
2227 for (ins = born_index; ins < dead_index; ins++)
2228 IOR_HARD_REG_SET (used, regs_live_at[ins]);
2230 IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]);
2232 /* Don't use the frame pointer reg in local-alloc even if
2233 we may omit the frame pointer, because if we do that and then we
2234 need a frame pointer, reload won't know how to move the pseudo
2235 to another hard reg. It can move only regs made by global-alloc.
2237 This is true of any register that can be eliminated. */
2238 #ifdef ELIMINABLE_REGS
2239 for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
2240 SET_HARD_REG_BIT (used, eliminables[i].from);
2241 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2242 /* If FRAME_POINTER_REGNUM is not a real register, then protect the one
2243 that it might be eliminated into. */
2244 SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
2247 SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
2250 #ifdef CANNOT_CHANGE_MODE_CLASS
2251 cannot_change_mode_set_regs (&used, mode, qty[qtyno].first_reg);
2254 /* Normally, the registers that can be used for the first register in
2255 a multi-register quantity are the same as those that can be used for
2256 subsequent registers. However, if just trying suggested registers,
2257 restrict our consideration to them. If there are copy-suggested
2258 register, try them. Otherwise, try the arithmetic-suggested
2260 COPY_HARD_REG_SET (first_used, used);
2262 if (just_try_suggested)
2264 if (qty_phys_num_copy_sugg[qtyno] != 0)
2265 IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qtyno]);
2267 IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qtyno]);
2270 /* If at least one would be suitable, test each hard reg. */
2271 if (!hard_reg_set_subset_p (reg_class_contents[(int) ALL_REGS], first_used))
2272 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2274 #ifdef REG_ALLOC_ORDER
2275 int regno = reg_alloc_order[i];
2279 if (!TEST_HARD_REG_BIT (first_used, regno)
2280 && HARD_REGNO_MODE_OK (regno, mode)
2281 && (qty[qtyno].n_calls_crossed == 0
2282 || accept_call_clobbered
2283 || !HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
2286 int size1 = hard_regno_nregs[regno][mode];
2288 while (j < size1 && !TEST_HARD_REG_BIT (used, regno + j))
2292 /* Mark that this register is in use between its birth
2294 post_mark_life (regno, mode, 1, born_index, dead_index);
2297 #ifndef REG_ALLOC_ORDER
2298 /* Skip starting points we know will lose. */
2304 /* If we are just trying suggested register, we have just tried copy-
2305 suggested registers, and there are arithmetic-suggested registers,
2308 /* If it would be profitable to allocate a call-clobbered register
2309 and save and restore it around calls, do that. */
2310 if (just_try_suggested && qty_phys_num_copy_sugg[qtyno] != 0
2311 && qty_phys_num_sugg[qtyno] != 0)
2313 /* Don't try the copy-suggested regs again. */
2314 qty_phys_num_copy_sugg[qtyno] = 0;
2315 return find_free_reg (class, mode, qtyno, accept_call_clobbered, 1,
2316 born_index, dead_index);
2319 /* We need not check to see if the current function has nonlocal
2320 labels because we don't put any pseudos that are live over calls in
2321 registers in that case. Avoid putting pseudos crossing calls that
2322 might throw into call used registers. */
2324 if (! accept_call_clobbered
2325 && flag_caller_saves
2326 && ! just_try_suggested
2327 && qty[qtyno].n_calls_crossed != 0
2328 && qty[qtyno].n_throwing_calls_crossed == 0
2329 && CALLER_SAVE_PROFITABLE (qty[qtyno].n_refs,
2330 qty[qtyno].n_calls_crossed))
2332 i = find_free_reg (class, mode, qtyno, 1, 0, born_index, dead_index);
2334 caller_save_needed = 1;
2340 /* Mark that REGNO with machine-mode MODE is live starting from the current
2341 insn (if LIFE is nonzero) or dead starting at the current insn (if LIFE
2345 mark_life (int regno, enum machine_mode mode, int life)
2348 add_to_hard_reg_set (®s_live, mode, regno);
2350 remove_from_hard_reg_set (®s_live, mode, regno);
2353 /* Mark register number REGNO (with machine-mode MODE) as live (if LIFE
2354 is nonzero) or dead (if LIFE is zero) from insn number BIRTH (inclusive)
2355 to insn number DEATH (exclusive). */
2358 post_mark_life (int regno, enum machine_mode mode, int life, int birth,
2361 HARD_REG_SET this_reg;
2363 CLEAR_HARD_REG_SET (this_reg);
2364 add_to_hard_reg_set (&this_reg, mode, regno);
2367 while (birth < death)
2369 IOR_HARD_REG_SET (regs_live_at[birth], this_reg);
2373 while (birth < death)
2375 AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg);
2380 /* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0
2381 is the register being clobbered, and R1 is a register being used in
2382 the equivalent expression.
2384 If R1 dies in the block and has a REG_NO_CONFLICT note on every insn
2385 in which it is used, return 1.
2387 Otherwise, return 0. */
2390 no_conflict_p (rtx insn, rtx r0 ATTRIBUTE_UNUSED, rtx r1)
2393 rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
2396 /* If R1 is a hard register, return 0 since we handle this case
2397 when we scan the insns that actually use it. */
2400 || (REG_P (r1) && REGNO (r1) < FIRST_PSEUDO_REGISTER)
2401 || (GET_CODE (r1) == SUBREG && REG_P (SUBREG_REG (r1))
2402 && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER))
2405 last = XEXP (note, 0);
2407 for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p))
2410 if (find_reg_note (p, REG_DEAD, r1))
2413 /* There must be a REG_NO_CONFLICT note on every insn, otherwise
2414 some earlier optimization pass has inserted instructions into
2415 the sequence, and it is not safe to perform this optimization.
2416 Note that emit_no_conflict_block always ensures that this is
2417 true when these sequences are created. */
2418 if (! find_reg_note (p, REG_NO_CONFLICT, r1))
2425 /* Return the number of alternatives for which the constraint string P
2426 indicates that the operand must be equal to operand 0 and that no register
2430 requires_inout (const char *p)
2434 int reg_allowed = 0;
2435 int num_matching_alts = 0;
2438 for ( ; (c = *p); p += len)
2440 len = CONSTRAINT_LEN (c, p);
2443 case '=': case '+': case '?':
2444 case '#': case '&': case '!':
2446 case 'm': case '<': case '>': case 'V': case 'o':
2447 case 'E': case 'F': case 'G': case 'H':
2448 case 's': case 'i': case 'n':
2449 case 'I': case 'J': case 'K': case 'L':
2450 case 'M': case 'N': case 'O': case 'P':
2452 /* These don't say anything we care about. */
2456 if (found_zero && ! reg_allowed)
2457 num_matching_alts++;
2459 found_zero = reg_allowed = 0;
2466 case '1': case '2': case '3': case '4': case '5':
2467 case '6': case '7': case '8': case '9':
2468 /* Skip the balance of the matching constraint. */
2471 while (ISDIGIT (*p));
2476 if (REG_CLASS_FROM_CONSTRAINT (c, p) == NO_REGS
2477 && !EXTRA_ADDRESS_CONSTRAINT (c, p))
2487 if (found_zero && ! reg_allowed)
2488 num_matching_alts++;
2490 return num_matching_alts;
2494 dump_local_alloc (FILE *file)
2497 for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
2498 if (reg_renumber[i] != -1)
2499 fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]);
2502 /* Run old register allocator. Return TRUE if we must exit
2503 rest_of_compilation upon return. */
2505 rest_of_handle_local_alloc (void)
2508 int max_regno = max_reg_num ();
2510 df_note_add_problem ();
2513 df_remove_problem (df_live);
2514 /* Create a new version of df that has the special version of UR if
2515 we are doing optimization. */
2517 df_urec_add_problem ();
2519 regstat_init_n_sets_and_refs ();
2520 regstat_compute_ri ();
2522 /* There is just too much going on in the register allocators to
2523 keep things up to date. At the end we have to rescan anyway
2524 because things change when the reload_completed flag is set.
2525 So we just turn off scanning and we will rescan by hand. */
2526 df_set_flags (DF_NO_INSN_RESCAN);
2529 /* If we are not optimizing, then this is the only place before
2530 register allocation where dataflow is done. And that is needed
2531 to generate these warnings. */
2533 generate_setjmp_warnings ();
2535 /* Determine if the current function is a leaf before running reload
2536 since this can impact optimizations done by the prologue and
2537 epilogue thus changing register elimination offsets. */
2538 current_function_is_leaf = leaf_function_p ();
2540 /* And the reg_equiv_memory_loc array. */
2541 VEC_safe_grow (rtx, gc, reg_equiv_memory_loc_vec, max_regno);
2542 memset (VEC_address (rtx, reg_equiv_memory_loc_vec), 0,
2543 sizeof (rtx) * max_regno);
2544 reg_equiv_memory_loc = VEC_address (rtx, reg_equiv_memory_loc_vec);
2546 allocate_initial_values (reg_equiv_memory_loc);
2548 regclass (get_insns (), max_regno);
2549 rebuild_notes = local_alloc ();
2551 /* Local allocation may have turned an indirect jump into a direct
2552 jump. If so, we must rebuild the JUMP_LABEL fields of jumping
2556 timevar_push (TV_JUMP);
2558 rebuild_jump_labels (get_insns ());
2559 purge_all_dead_edges ();
2560 timevar_pop (TV_JUMP);
2563 if (dump_file && (dump_flags & TDF_DETAILS))
2565 timevar_push (TV_DUMP);
2566 dump_flow_info (dump_file, dump_flags);
2567 dump_local_alloc (dump_file);
2568 timevar_pop (TV_DUMP);
2573 struct tree_opt_pass pass_local_alloc =
2577 rest_of_handle_local_alloc, /* execute */
2580 0, /* static_pass_number */
2581 TV_LOCAL_ALLOC, /* tv_id */
2582 0, /* properties_required */
2583 0, /* properties_provided */
2584 0, /* properties_destroyed */
2585 0, /* todo_flags_start */
2587 TODO_ggc_collect, /* todo_flags_finish */