118334Speter/* Allocate registers within a basic block, for GNU compiler. 290075Sobrien Copyright (C) 1987, 1988, 1991, 1993, 1994, 1995, 1996, 1997, 1998, 3169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, 4169689Skan Inc. 518334Speter 690075SobrienThis file is part of GCC. 718334Speter 890075SobrienGCC is free software; you can redistribute it and/or modify it under 990075Sobrienthe terms of the GNU General Public License as published by the Free 1090075SobrienSoftware Foundation; either version 2, or (at your option) any later 1190075Sobrienversion. 1218334Speter 1390075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1490075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1590075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1690075Sobrienfor more details. 1718334Speter 1818334SpeterYou should have received a copy of the GNU General Public License 1990075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 2218334Speter 2318334Speter/* Allocation of hard register numbers to pseudo registers is done in 2418334Speter two passes. In this pass we consider only regs that are born and 2518334Speter die once within one basic block. We do this one basic block at a 2618334Speter time. Then the next pass allocates the registers that remain. 2718334Speter Two passes are used because this pass uses methods that work only 2818334Speter on linear code, but that do a better job than the general methods 2918334Speter used in global_alloc, and more quickly too. 3018334Speter 3118334Speter The assignments made are recorded in the vector reg_renumber 3218334Speter whose space is allocated here. The rtl code itself is not altered. 3318334Speter 3418334Speter We assign each instruction in the basic block a number 3518334Speter which is its order from the beginning of the block. 3618334Speter Then we can represent the lifetime of a pseudo register with 3718334Speter a pair of numbers, and check for conflicts easily. 3818334Speter We can record the availability of hard registers with a 3918334Speter HARD_REG_SET for each instruction. The HARD_REG_SET 4018334Speter contains 0 or 1 for each hard reg. 4118334Speter 4218334Speter To avoid register shuffling, we tie registers together when one 4318334Speter dies by being copied into another, or dies in an instruction that 4418334Speter does arithmetic to produce another. The tied registers are 4518334Speter allocated as one. Registers with different reg class preferences 4618334Speter can never be tied unless the class preferred by one is a subclass 4718334Speter of the one preferred by the other. 4818334Speter 4918334Speter Tying is represented with "quantity numbers". 5018334Speter A non-tied register is given a new quantity number. 5118334Speter Tied registers have the same quantity number. 5290075Sobrien 5318334Speter We have provision to exempt registers, even when they are contained 5418334Speter within the block, that can be tied to others that are not contained in it. 5518334Speter This is so that global_alloc could process them both and tie them then. 5618334Speter But this is currently disabled since tying in global_alloc is not 5718334Speter yet implemented. */ 5818334Speter 5952284Sobrien/* Pseudos allocated here can be reallocated by global.c if the hard register 6052284Sobrien is used as a spill register. Currently we don't allocate such pseudos 6150397Sobrien here if their preferred class is likely to be used by spills. */ 6250397Sobrien 6318334Speter#include "config.h" 6450397Sobrien#include "system.h" 65132718Skan#include "coretypes.h" 66132718Skan#include "tm.h" 67117395Skan#include "hard-reg-set.h" 6818334Speter#include "rtl.h" 6990075Sobrien#include "tm_p.h" 7018334Speter#include "flags.h" 7118334Speter#include "regs.h" 7290075Sobrien#include "function.h" 7318334Speter#include "insn-config.h" 7450397Sobrien#include "insn-attr.h" 7518334Speter#include "recog.h" 7618334Speter#include "output.h" 7750397Sobrien#include "toplev.h" 7890075Sobrien#include "except.h" 7990075Sobrien#include "integrate.h" 80169689Skan#include "reload.h" 81169689Skan#include "ggc.h" 82169689Skan#include "timevar.h" 83169689Skan#include "tree-pass.h" 8418334Speter 8518334Speter/* Next quantity number available for allocation. */ 8618334Speter 8718334Speterstatic int next_qty; 8818334Speter 8990075Sobrien/* Information we maintain about each quantity. */ 9090075Sobrienstruct qty 9190075Sobrien{ 9290075Sobrien /* The number of refs to quantity Q. */ 9318334Speter 9490075Sobrien int n_refs; 9518334Speter 9690075Sobrien /* The frequency of uses of quantity Q. */ 9718334Speter 9890075Sobrien int freq; 9918334Speter 10090075Sobrien /* Insn number (counting from head of basic block) 10190075Sobrien where quantity Q was born. -1 if birth has not been recorded. */ 10218334Speter 10390075Sobrien int birth; 10418334Speter 10590075Sobrien /* Insn number (counting from head of basic block) 10690075Sobrien where given quantity died. Due to the way tying is done, 10790075Sobrien and the fact that we consider in this pass only regs that die but once, 10890075Sobrien a quantity can die only once. Each quantity's life span 10990075Sobrien is a set of consecutive insns. -1 if death has not been recorded. */ 11018334Speter 11190075Sobrien int death; 11218334Speter 11390075Sobrien /* Number of words needed to hold the data in given quantity. 11490075Sobrien This depends on its machine mode. It is used for these purposes: 115132718Skan 1. It is used in computing the relative importance of qtys, 11690075Sobrien which determines the order in which we look for regs for them. 11790075Sobrien 2. It is used in rules that prevent tying several registers of 11890075Sobrien different sizes in a way that is geometrically impossible 11990075Sobrien (see combine_regs). */ 12018334Speter 12190075Sobrien int size; 12218334Speter 12390075Sobrien /* Number of times a reg tied to given qty lives across a CALL_INSN. */ 12418334Speter 12590075Sobrien int n_calls_crossed; 12618334Speter 127161651Skan /* Number of times a reg tied to given qty lives across a CALL_INSN 128161651Skan that might throw. */ 129161651Skan 130161651Skan int n_throwing_calls_crossed; 131161651Skan 13290075Sobrien /* The register number of one pseudo register whose reg_qty value is Q. 13390075Sobrien This register should be the head of the chain 13490075Sobrien maintained in reg_next_in_qty. */ 13518334Speter 13690075Sobrien int first_reg; 13718334Speter 13890075Sobrien /* Reg class contained in (smaller than) the preferred classes of all 13990075Sobrien the pseudo regs that are tied in given quantity. 14090075Sobrien This is the preferred class for allocating that quantity. */ 14118334Speter 14290075Sobrien enum reg_class min_class; 14318334Speter 14490075Sobrien /* Register class within which we allocate given qty if we can't get 14590075Sobrien its preferred class. */ 14618334Speter 14790075Sobrien enum reg_class alternate_class; 14818334Speter 14990075Sobrien /* This holds the mode of the registers that are tied to given qty, 15090075Sobrien or VOIDmode if registers with differing modes are tied together. */ 15118334Speter 15290075Sobrien enum machine_mode mode; 15318334Speter 15490075Sobrien /* the hard reg number chosen for given quantity, 15590075Sobrien or -1 if none was found. */ 15618334Speter 15790075Sobrien short phys_reg; 15890075Sobrien}; 15918334Speter 16090075Sobrienstatic struct qty *qty; 16118334Speter 16290075Sobrien/* These fields are kept separately to speedup their clearing. */ 16318334Speter 16490075Sobrien/* We maintain two hard register sets that indicate suggested hard registers 16590075Sobrien for each quantity. The first, phys_copy_sugg, contains hard registers 16690075Sobrien that are tied to the quantity by a simple copy. The second contains all 16790075Sobrien hard registers that are tied to the quantity via an arithmetic operation. 16818334Speter 16990075Sobrien The former register set is given priority for allocation. This tends to 17090075Sobrien eliminate copy insns. */ 17118334Speter 17290075Sobrien/* Element Q is a set of hard registers that are suggested for quantity Q by 17390075Sobrien copy insns. */ 17418334Speter 17590075Sobrienstatic HARD_REG_SET *qty_phys_copy_sugg; 17618334Speter 17790075Sobrien/* Element Q is a set of hard registers that are suggested for quantity Q by 17890075Sobrien arithmetic insns. */ 17918334Speter 18090075Sobrienstatic HARD_REG_SET *qty_phys_sugg; 18118334Speter 18290075Sobrien/* Element Q is the number of suggested registers in qty_phys_copy_sugg. */ 18390075Sobrien 18490075Sobrienstatic short *qty_phys_num_copy_sugg; 18590075Sobrien 18690075Sobrien/* Element Q is the number of suggested registers in qty_phys_sugg. */ 18790075Sobrien 18890075Sobrienstatic short *qty_phys_num_sugg; 18990075Sobrien 19018334Speter/* If (REG N) has been assigned a quantity number, is a register number 19118334Speter of another register assigned the same quantity number, or -1 for the 19290075Sobrien end of the chain. qty->first_reg point to the head of this chain. */ 19318334Speter 19418334Speterstatic int *reg_next_in_qty; 19518334Speter 19618334Speter/* reg_qty[N] (where N is a pseudo reg number) is the qty number of that reg 19718334Speter if it is >= 0, 19818334Speter of -1 if this register cannot be allocated by local-alloc, 19918334Speter or -2 if not known yet. 20018334Speter 20118334Speter Note that if we see a use or death of pseudo register N with 20218334Speter reg_qty[N] == -2, register N must be local to the current block. If 20318334Speter it were used in more than one block, we would have reg_qty[N] == -1. 20418334Speter This relies on the fact that if reg_basic_block[N] is >= 0, register N 20518334Speter will not appear in any other block. We save a considerable number of 20618334Speter tests by exploiting this. 20718334Speter 20818334Speter If N is < FIRST_PSEUDO_REGISTER, reg_qty[N] is undefined and should not 20918334Speter be referenced. */ 21018334Speter 21118334Speterstatic int *reg_qty; 21218334Speter 21318334Speter/* The offset (in words) of register N within its quantity. 21418334Speter This can be nonzero if register N is SImode, and has been tied 21518334Speter to a subreg of a DImode register. */ 21618334Speter 21718334Speterstatic char *reg_offset; 21818334Speter 21918334Speter/* Vector of substitutions of register numbers, 22018334Speter used to map pseudo regs into hardware regs. 22118334Speter This is set up as a result of register allocation. 22218334Speter Element N is the hard reg assigned to pseudo reg N, 22318334Speter or is -1 if no hard reg was assigned. 22418334Speter If N is a hard reg number, element N is N. */ 22518334Speter 22618334Spetershort *reg_renumber; 22718334Speter 22818334Speter/* Set of hard registers live at the current point in the scan 22918334Speter of the instructions in a basic block. */ 23018334Speter 23118334Speterstatic HARD_REG_SET regs_live; 23218334Speter 23318334Speter/* Each set of hard registers indicates registers live at a particular 23418334Speter point in the basic block. For N even, regs_live_at[N] says which 23518334Speter hard registers are needed *after* insn N/2 (i.e., they may not 23618334Speter conflict with the outputs of insn N/2 or the inputs of insn N/2 + 1. 23718334Speter 23818334Speter If an object is to conflict with the inputs of insn J but not the 23918334Speter outputs of insn J + 1, we say it is born at index J*2 - 1. Similarly, 24018334Speter if it is to conflict with the outputs of insn J but not the inputs of 24118334Speter insn J + 1, it is said to die at index J*2 + 1. */ 24218334Speter 24318334Speterstatic HARD_REG_SET *regs_live_at; 24418334Speter 24518334Speter/* Communicate local vars `insn_number' and `insn' 24618334Speter from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_qty'. */ 24718334Speterstatic int this_insn_number; 24818334Speterstatic rtx this_insn; 24918334Speter 25090075Sobrienstruct equivalence 25190075Sobrien{ 25290075Sobrien /* Set when an attempt should be made to replace a register 253102780Skan with the associated src_p entry. */ 25450397Sobrien 25590075Sobrien char replace; 25650397Sobrien 25790075Sobrien /* Set when a REG_EQUIV note is found or created. Use to 25890075Sobrien keep track of what memory accesses might be created later, 25990075Sobrien e.g. by reload. */ 26052284Sobrien 26190075Sobrien rtx replacement; 26290075Sobrien 263102780Skan rtx *src_p; 26490075Sobrien 26590075Sobrien /* Loop depth is used to recognize equivalences which appear 26690075Sobrien to be present within the same loop (or in an inner loop). */ 26790075Sobrien 26890075Sobrien int loop_depth; 26990075Sobrien 27090075Sobrien /* The list of each instruction which initializes this register. */ 27190075Sobrien 27290075Sobrien rtx init_insns; 273169689Skan 274169689Skan /* Nonzero if this had a preexisting REG_EQUIV note. */ 275169689Skan 276169689Skan int is_arg_equivalence; 27790075Sobrien}; 27890075Sobrien 27990075Sobrien/* reg_equiv[N] (where N is a pseudo reg number) is the equivalence 28090075Sobrien structure for that register. */ 28190075Sobrien 28290075Sobrienstatic struct equivalence *reg_equiv; 28390075Sobrien 28452284Sobrien/* Nonzero if we recorded an equivalence for a LABEL_REF. */ 28552284Sobrienstatic int recorded_label_ref; 28652284Sobrien 287132718Skanstatic void alloc_qty (int, enum machine_mode, int, int); 288132718Skanstatic void validate_equiv_mem_from_store (rtx, rtx, void *); 289132718Skanstatic int validate_equiv_mem (rtx, rtx, rtx); 290132718Skanstatic int equiv_init_varies_p (rtx); 291132718Skanstatic int equiv_init_movable_p (rtx, int); 292132718Skanstatic int contains_replace_regs (rtx); 293132718Skanstatic int memref_referenced_p (rtx, rtx); 294132718Skanstatic int memref_used_between_p (rtx, rtx, rtx); 295132718Skanstatic void update_equiv_regs (void); 296132718Skanstatic void no_equiv (rtx, rtx, void *); 297132718Skanstatic void block_alloc (int); 298132718Skanstatic int qty_sugg_compare (int, int); 299132718Skanstatic int qty_sugg_compare_1 (const void *, const void *); 300132718Skanstatic int qty_compare (int, int); 301132718Skanstatic int qty_compare_1 (const void *, const void *); 302132718Skanstatic int combine_regs (rtx, rtx, int, int, rtx, int); 303132718Skanstatic int reg_meets_class_p (int, enum reg_class); 304132718Skanstatic void update_qty_class (int, int); 305132718Skanstatic void reg_is_set (rtx, rtx, void *); 306132718Skanstatic void reg_is_born (rtx, int); 307132718Skanstatic void wipe_dead_reg (rtx, int); 308132718Skanstatic int find_free_reg (enum reg_class, enum machine_mode, int, int, int, 309132718Skan int, int); 310132718Skanstatic void mark_life (int, enum machine_mode, int); 311132718Skanstatic void post_mark_life (int, enum machine_mode, int, int, int); 312132718Skanstatic int no_conflict_p (rtx, rtx, rtx); 313132718Skanstatic int requires_inout (const char *); 31418334Speter 31518334Speter/* Allocate a new quantity (new within current basic block) 31618334Speter for register number REGNO which is born at index BIRTH 31718334Speter within the block. MODE and SIZE are info on reg REGNO. */ 31818334Speter 31918334Speterstatic void 320132718Skanalloc_qty (int regno, enum machine_mode mode, int size, int birth) 32118334Speter{ 32290075Sobrien int qtyno = next_qty++; 32318334Speter 32490075Sobrien reg_qty[regno] = qtyno; 32518334Speter reg_offset[regno] = 0; 32618334Speter reg_next_in_qty[regno] = -1; 32718334Speter 32890075Sobrien qty[qtyno].first_reg = regno; 32990075Sobrien qty[qtyno].size = size; 33090075Sobrien qty[qtyno].mode = mode; 33190075Sobrien qty[qtyno].birth = birth; 33290075Sobrien qty[qtyno].n_calls_crossed = REG_N_CALLS_CROSSED (regno); 333161651Skan qty[qtyno].n_throwing_calls_crossed = REG_N_THROWING_CALLS_CROSSED (regno); 33490075Sobrien qty[qtyno].min_class = reg_preferred_class (regno); 33590075Sobrien qty[qtyno].alternate_class = reg_alternate_class (regno); 33690075Sobrien qty[qtyno].n_refs = REG_N_REFS (regno); 33790075Sobrien qty[qtyno].freq = REG_FREQ (regno); 33818334Speter} 33918334Speter 34018334Speter/* Main entry point of this file. */ 34118334Speter 342169689Skanstatic int 343132718Skanlocal_alloc (void) 34418334Speter{ 345117395Skan int i; 34618334Speter int max_qty; 347117395Skan basic_block b; 34818334Speter 34952284Sobrien /* We need to keep track of whether or not we recorded a LABEL_REF so 35052284Sobrien that we know if the jump optimizer needs to be rerun. */ 35152284Sobrien recorded_label_ref = 0; 35252284Sobrien 35318334Speter /* Leaf functions and non-leaf functions have different needs. 35418334Speter If defined, let the machine say what kind of ordering we 35518334Speter should use. */ 35618334Speter#ifdef ORDER_REGS_FOR_LOCAL_ALLOC 35718334Speter ORDER_REGS_FOR_LOCAL_ALLOC; 35818334Speter#endif 35918334Speter 36018334Speter /* Promote REG_EQUAL notes to REG_EQUIV notes and adjust status of affected 36118334Speter registers. */ 362169689Skan update_equiv_regs (); 36318334Speter 36418334Speter /* This sets the maximum number of quantities we can have. Quantity 36552284Sobrien numbers start at zero and we can have one for each pseudo. */ 36652284Sobrien max_qty = (max_regno - FIRST_PSEUDO_REGISTER); 36718334Speter 36818334Speter /* Allocate vectors of temporary data. 36918334Speter See the declarations of these variables, above, 37018334Speter for what they mean. */ 37118334Speter 372169689Skan qty = XNEWVEC (struct qty, max_qty); 373169689Skan qty_phys_copy_sugg = XNEWVEC (HARD_REG_SET, max_qty); 374169689Skan qty_phys_num_copy_sugg = XNEWVEC (short, max_qty); 375169689Skan qty_phys_sugg = XNEWVEC (HARD_REG_SET, max_qty); 376169689Skan qty_phys_num_sugg = XNEWVEC (short, max_qty); 37718334Speter 378169689Skan reg_qty = XNEWVEC (int, max_regno); 379169689Skan reg_offset = XNEWVEC (char, max_regno); 380169689Skan reg_next_in_qty = XNEWVEC (int, max_regno); 38118334Speter 38218334Speter /* Determine which pseudo-registers can be allocated by local-alloc. 38318334Speter In general, these are the registers used only in a single block and 38490075Sobrien which only die once. 38518334Speter 38618334Speter We need not be concerned with which block actually uses the register 38718334Speter since we will never see it outside that block. */ 38818334Speter 38918334Speter for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 39018334Speter { 39190075Sobrien if (REG_BASIC_BLOCK (i) >= 0 && REG_N_DEATHS (i) == 1) 39218334Speter reg_qty[i] = -2; 39318334Speter else 39418334Speter reg_qty[i] = -1; 39518334Speter } 39618334Speter 39718334Speter /* Force loop below to initialize entire quantity array. */ 39818334Speter next_qty = max_qty; 39918334Speter 40018334Speter /* Allocate each block's local registers, block by block. */ 40118334Speter 402117395Skan FOR_EACH_BB (b) 40318334Speter { 40418334Speter /* NEXT_QTY indicates which elements of the `qty_...' 40518334Speter vectors might need to be initialized because they were used 40618334Speter for the previous block; it is set to the entire array before 40718334Speter block 0. Initialize those, with explicit loop if there are few, 40818334Speter else with bzero and bcopy. Do not initialize vectors that are 40918334Speter explicit set by `alloc_qty'. */ 41018334Speter 41118334Speter if (next_qty < 6) 41218334Speter { 41318334Speter for (i = 0; i < next_qty; i++) 41418334Speter { 41518334Speter CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]); 41618334Speter qty_phys_num_copy_sugg[i] = 0; 41718334Speter CLEAR_HARD_REG_SET (qty_phys_sugg[i]); 41818334Speter qty_phys_num_sugg[i] = 0; 41918334Speter } 42018334Speter } 42118334Speter else 42218334Speter { 42318334Speter#define CLEAR(vector) \ 424132718Skan memset ((vector), 0, (sizeof (*(vector))) * next_qty); 42518334Speter 42618334Speter CLEAR (qty_phys_copy_sugg); 42718334Speter CLEAR (qty_phys_num_copy_sugg); 42818334Speter CLEAR (qty_phys_sugg); 42918334Speter CLEAR (qty_phys_num_sugg); 43018334Speter } 43118334Speter 43218334Speter next_qty = 0; 43318334Speter 434117395Skan block_alloc (b->index); 43518334Speter } 43650397Sobrien 43790075Sobrien free (qty); 43890075Sobrien free (qty_phys_copy_sugg); 43990075Sobrien free (qty_phys_num_copy_sugg); 44090075Sobrien free (qty_phys_sugg); 44190075Sobrien free (qty_phys_num_sugg); 44290075Sobrien 44350397Sobrien free (reg_qty); 44450397Sobrien free (reg_offset); 44550397Sobrien free (reg_next_in_qty); 44690075Sobrien 44752284Sobrien return recorded_label_ref; 44818334Speter} 44918334Speter 45018334Speter/* Used for communication between the following two functions: contains 45118334Speter a MEM that we wish to ensure remains unchanged. */ 45218334Speterstatic rtx equiv_mem; 45318334Speter 45418334Speter/* Set nonzero if EQUIV_MEM is modified. */ 45518334Speterstatic int equiv_mem_modified; 45618334Speter 45718334Speter/* If EQUIV_MEM is modified by modifying DEST, indicate that it is modified. 45818334Speter Called via note_stores. */ 45918334Speter 46018334Speterstatic void 461132718Skanvalidate_equiv_mem_from_store (rtx dest, rtx set ATTRIBUTE_UNUSED, 462132718Skan void *data ATTRIBUTE_UNUSED) 46318334Speter{ 464169689Skan if ((REG_P (dest) 46518334Speter && reg_overlap_mentioned_p (dest, equiv_mem)) 466169689Skan || (MEM_P (dest) 46750397Sobrien && true_dependence (dest, VOIDmode, equiv_mem, rtx_varies_p))) 46818334Speter equiv_mem_modified = 1; 46918334Speter} 47018334Speter 47118334Speter/* Verify that no store between START and the death of REG invalidates 47218334Speter MEMREF. MEMREF is invalidated by modifying a register used in MEMREF, 47318334Speter by storing into an overlapping memory location, or with a non-const 47418334Speter CALL_INSN. 47518334Speter 47618334Speter Return 1 if MEMREF remains valid. */ 47718334Speter 47818334Speterstatic int 479132718Skanvalidate_equiv_mem (rtx start, rtx reg, rtx memref) 48018334Speter{ 48118334Speter rtx insn; 48218334Speter rtx note; 48318334Speter 48418334Speter equiv_mem = memref; 48518334Speter equiv_mem_modified = 0; 48618334Speter 48718334Speter /* If the memory reference has side effects or is volatile, it isn't a 48818334Speter valid equivalence. */ 48918334Speter if (side_effects_p (memref)) 49018334Speter return 0; 49118334Speter 49218334Speter for (insn = start; insn && ! equiv_mem_modified; insn = NEXT_INSN (insn)) 49318334Speter { 49490075Sobrien if (! INSN_P (insn)) 49518334Speter continue; 49618334Speter 49718334Speter if (find_reg_note (insn, REG_DEAD, reg)) 49818334Speter return 1; 49918334Speter 500169689Skan if (CALL_P (insn) && ! MEM_READONLY_P (memref) 50190075Sobrien && ! CONST_OR_PURE_CALL_P (insn)) 50218334Speter return 0; 50318334Speter 50490075Sobrien note_stores (PATTERN (insn), validate_equiv_mem_from_store, NULL); 50518334Speter 50618334Speter /* If a register mentioned in MEMREF is modified via an 50718334Speter auto-increment, we lose the equivalence. Do the same if one 50818334Speter dies; although we could extend the life, it doesn't seem worth 50918334Speter the trouble. */ 51018334Speter 51118334Speter for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 51218334Speter if ((REG_NOTE_KIND (note) == REG_INC 51318334Speter || REG_NOTE_KIND (note) == REG_DEAD) 514169689Skan && REG_P (XEXP (note, 0)) 51518334Speter && reg_overlap_mentioned_p (XEXP (note, 0), memref)) 51618334Speter return 0; 51718334Speter } 51818334Speter 51918334Speter return 0; 52018334Speter} 52150397Sobrien 52290075Sobrien/* Returns zero if X is known to be invariant. */ 52350397Sobrien 52450397Sobrienstatic int 525132718Skanequiv_init_varies_p (rtx x) 52650397Sobrien{ 52790075Sobrien RTX_CODE code = GET_CODE (x); 52890075Sobrien int i; 52990075Sobrien const char *fmt; 53090075Sobrien 53190075Sobrien switch (code) 53290075Sobrien { 53390075Sobrien case MEM: 534169689Skan return !MEM_READONLY_P (x) || equiv_init_varies_p (XEXP (x, 0)); 53590075Sobrien 53690075Sobrien case CONST: 53790075Sobrien case CONST_INT: 53890075Sobrien case CONST_DOUBLE: 53996263Sobrien case CONST_VECTOR: 54090075Sobrien case SYMBOL_REF: 54190075Sobrien case LABEL_REF: 54290075Sobrien return 0; 54390075Sobrien 54490075Sobrien case REG: 54590075Sobrien return reg_equiv[REGNO (x)].replace == 0 && rtx_varies_p (x, 0); 54690075Sobrien 54790075Sobrien case ASM_OPERANDS: 54890075Sobrien if (MEM_VOLATILE_P (x)) 54990075Sobrien return 1; 55090075Sobrien 551132718Skan /* Fall through. */ 55290075Sobrien 55390075Sobrien default: 55490075Sobrien break; 55590075Sobrien } 55690075Sobrien 55790075Sobrien fmt = GET_RTX_FORMAT (code); 55890075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 55990075Sobrien if (fmt[i] == 'e') 56090075Sobrien { 56190075Sobrien if (equiv_init_varies_p (XEXP (x, i))) 56290075Sobrien return 1; 56390075Sobrien } 56490075Sobrien else if (fmt[i] == 'E') 56590075Sobrien { 56690075Sobrien int j; 56790075Sobrien for (j = 0; j < XVECLEN (x, i); j++) 56890075Sobrien if (equiv_init_varies_p (XVECEXP (x, i, j))) 56990075Sobrien return 1; 57090075Sobrien } 57190075Sobrien 57290075Sobrien return 0; 57390075Sobrien} 57490075Sobrien 575117395Skan/* Returns nonzero if X (used to initialize register REGNO) is movable. 57690075Sobrien X is only movable if the registers it uses have equivalent initializations 57790075Sobrien which appear to be within the same loop (or in an inner loop) and movable 57890075Sobrien or if they are not candidates for local_alloc and don't vary. */ 57990075Sobrien 58090075Sobrienstatic int 581132718Skanequiv_init_movable_p (rtx x, int regno) 58290075Sobrien{ 58350397Sobrien int i, j; 58490075Sobrien const char *fmt; 58550397Sobrien enum rtx_code code = GET_CODE (x); 58650397Sobrien 58750397Sobrien switch (code) 58850397Sobrien { 58990075Sobrien case SET: 59090075Sobrien return equiv_init_movable_p (SET_SRC (x), regno); 59190075Sobrien 59290075Sobrien case CC0: 59390075Sobrien case CLOBBER: 59490075Sobrien return 0; 59590075Sobrien 59690075Sobrien case PRE_INC: 59790075Sobrien case PRE_DEC: 59890075Sobrien case POST_INC: 59990075Sobrien case POST_DEC: 60090075Sobrien case PRE_MODIFY: 60190075Sobrien case POST_MODIFY: 60290075Sobrien return 0; 60390075Sobrien 60490075Sobrien case REG: 60590075Sobrien return (reg_equiv[REGNO (x)].loop_depth >= reg_equiv[regno].loop_depth 60690075Sobrien && reg_equiv[REGNO (x)].replace) 60790075Sobrien || (REG_BASIC_BLOCK (REGNO (x)) < 0 && ! rtx_varies_p (x, 0)); 60890075Sobrien 60990075Sobrien case UNSPEC_VOLATILE: 61090075Sobrien return 0; 61190075Sobrien 61290075Sobrien case ASM_OPERANDS: 61390075Sobrien if (MEM_VOLATILE_P (x)) 61490075Sobrien return 0; 61590075Sobrien 616132718Skan /* Fall through. */ 61790075Sobrien 61890075Sobrien default: 61990075Sobrien break; 62090075Sobrien } 62190075Sobrien 62290075Sobrien fmt = GET_RTX_FORMAT (code); 62390075Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 62490075Sobrien switch (fmt[i]) 62590075Sobrien { 62690075Sobrien case 'e': 62790075Sobrien if (! equiv_init_movable_p (XEXP (x, i), regno)) 62890075Sobrien return 0; 62990075Sobrien break; 63090075Sobrien case 'E': 63190075Sobrien for (j = XVECLEN (x, i) - 1; j >= 0; j--) 63290075Sobrien if (! equiv_init_movable_p (XVECEXP (x, i, j), regno)) 63390075Sobrien return 0; 63490075Sobrien break; 63590075Sobrien } 63690075Sobrien 63790075Sobrien return 1; 63890075Sobrien} 63990075Sobrien 64090075Sobrien/* TRUE if X uses any registers for which reg_equiv[REGNO].replace is true. */ 64190075Sobrien 64290075Sobrienstatic int 643132718Skancontains_replace_regs (rtx x) 64490075Sobrien{ 64590075Sobrien int i, j; 64690075Sobrien const char *fmt; 64790075Sobrien enum rtx_code code = GET_CODE (x); 64890075Sobrien 64990075Sobrien switch (code) 65090075Sobrien { 65150397Sobrien case CONST_INT: 65250397Sobrien case CONST: 65350397Sobrien case LABEL_REF: 65450397Sobrien case SYMBOL_REF: 65550397Sobrien case CONST_DOUBLE: 65696263Sobrien case CONST_VECTOR: 65750397Sobrien case PC: 65850397Sobrien case CC0: 65950397Sobrien case HIGH: 66050397Sobrien return 0; 66150397Sobrien 66250397Sobrien case REG: 66390075Sobrien return reg_equiv[REGNO (x)].replace; 66450397Sobrien 66550397Sobrien default: 66650397Sobrien break; 66750397Sobrien } 66850397Sobrien 66950397Sobrien fmt = GET_RTX_FORMAT (code); 67050397Sobrien for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 67150397Sobrien switch (fmt[i]) 67250397Sobrien { 67350397Sobrien case 'e': 67490075Sobrien if (contains_replace_regs (XEXP (x, i))) 67550397Sobrien return 1; 67650397Sobrien break; 67750397Sobrien case 'E': 67850397Sobrien for (j = XVECLEN (x, i) - 1; j >= 0; j--) 67990075Sobrien if (contains_replace_regs (XVECEXP (x, i, j))) 68050397Sobrien return 1; 68150397Sobrien break; 68250397Sobrien } 68350397Sobrien 68450397Sobrien return 0; 68550397Sobrien} 68618334Speter 68718334Speter/* TRUE if X references a memory location that would be affected by a store 68818334Speter to MEMREF. */ 68918334Speter 69018334Speterstatic int 691132718Skanmemref_referenced_p (rtx memref, rtx x) 69218334Speter{ 69318334Speter int i, j; 69490075Sobrien const char *fmt; 69518334Speter enum rtx_code code = GET_CODE (x); 69618334Speter 69718334Speter switch (code) 69818334Speter { 69918334Speter case CONST_INT: 70018334Speter case CONST: 70118334Speter case LABEL_REF: 70218334Speter case SYMBOL_REF: 70318334Speter case CONST_DOUBLE: 70496263Sobrien case CONST_VECTOR: 70518334Speter case PC: 70618334Speter case CC0: 70718334Speter case HIGH: 70818334Speter case LO_SUM: 70918334Speter return 0; 71018334Speter 71150397Sobrien case REG: 71290075Sobrien return (reg_equiv[REGNO (x)].replacement 71350397Sobrien && memref_referenced_p (memref, 71490075Sobrien reg_equiv[REGNO (x)].replacement)); 71550397Sobrien 71618334Speter case MEM: 71750397Sobrien if (true_dependence (memref, VOIDmode, x, rtx_varies_p)) 71818334Speter return 1; 71918334Speter break; 72018334Speter 72118334Speter case SET: 72218334Speter /* If we are setting a MEM, it doesn't count (its address does), but any 72318334Speter other SET_DEST that has a MEM in it is referencing the MEM. */ 724169689Skan if (MEM_P (SET_DEST (x))) 72518334Speter { 72618334Speter if (memref_referenced_p (memref, XEXP (SET_DEST (x), 0))) 72718334Speter return 1; 72818334Speter } 72918334Speter else if (memref_referenced_p (memref, SET_DEST (x))) 73018334Speter return 1; 73118334Speter 73218334Speter return memref_referenced_p (memref, SET_SRC (x)); 73390075Sobrien 73450397Sobrien default: 73550397Sobrien break; 73618334Speter } 73718334Speter 73818334Speter fmt = GET_RTX_FORMAT (code); 73918334Speter for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 74018334Speter switch (fmt[i]) 74118334Speter { 74218334Speter case 'e': 74318334Speter if (memref_referenced_p (memref, XEXP (x, i))) 74418334Speter return 1; 74518334Speter break; 74618334Speter case 'E': 74718334Speter for (j = XVECLEN (x, i) - 1; j >= 0; j--) 74818334Speter if (memref_referenced_p (memref, XVECEXP (x, i, j))) 74918334Speter return 1; 75018334Speter break; 75118334Speter } 75218334Speter 75318334Speter return 0; 75418334Speter} 75518334Speter 75618334Speter/* TRUE if some insn in the range (START, END] references a memory location 75718334Speter that would be affected by a store to MEMREF. */ 75818334Speter 75918334Speterstatic int 760132718Skanmemref_used_between_p (rtx memref, rtx start, rtx end) 76118334Speter{ 76218334Speter rtx insn; 76318334Speter 76418334Speter for (insn = NEXT_INSN (start); insn != NEXT_INSN (end); 76518334Speter insn = NEXT_INSN (insn)) 766169689Skan { 767169689Skan if (!INSN_P (insn)) 768169689Skan continue; 769169689Skan 770169689Skan if (memref_referenced_p (memref, PATTERN (insn))) 771169689Skan return 1; 77218334Speter 773169689Skan /* Nonconst functions may access memory. */ 774169689Skan if (CALL_P (insn) 775169689Skan && (! CONST_OR_PURE_CALL_P (insn) 776169689Skan || pure_call_p (insn))) 777169689Skan return 1; 778169689Skan } 779169689Skan 78018334Speter return 0; 78118334Speter} 78218334Speter 78318334Speter/* Find registers that are equivalent to a single value throughout the 78418334Speter compilation (either because they can be referenced in memory or are set once 78518334Speter from a single constant). Lower their priority for a register. 78618334Speter 78718334Speter If such a register is only referenced once, try substituting its value 78818334Speter into the using insn. If it succeeds, we can eliminate the register 789169689Skan completely. 79018334Speter 791169689Skan Initialize the REG_EQUIV_INIT array of initializing insns. */ 792169689Skan 79318334Speterstatic void 794132718Skanupdate_equiv_regs (void) 79518334Speter{ 79618334Speter rtx insn; 797117395Skan basic_block bb; 79890075Sobrien int loop_depth; 79990075Sobrien regset_head cleared_regs; 80090075Sobrien int clear_regnos = 0; 80118334Speter 802169689Skan reg_equiv = XCNEWVEC (struct equivalence, max_regno); 80390075Sobrien INIT_REG_SET (&cleared_regs); 804169689Skan reg_equiv_init = ggc_alloc_cleared (max_regno * sizeof (rtx)); 805169689Skan reg_equiv_init_size = max_regno; 80650397Sobrien 80718334Speter init_alias_analysis (); 80818334Speter 80918334Speter /* Scan the insns and find which registers have equivalences. Do this 81018334Speter in a separate scan of the insns because (due to -fcse-follow-jumps) 81118334Speter a register can be set below its use. */ 812117395Skan FOR_EACH_BB (bb) 81318334Speter { 81490075Sobrien loop_depth = bb->loop_depth; 81518334Speter 816132718Skan for (insn = BB_HEAD (bb); 817132718Skan insn != NEXT_INSN (BB_END (bb)); 818132718Skan insn = NEXT_INSN (insn)) 81918334Speter { 82090075Sobrien rtx note; 82190075Sobrien rtx set; 82290075Sobrien rtx dest, src; 82390075Sobrien int regno; 82418334Speter 82590075Sobrien if (! INSN_P (insn)) 82690075Sobrien continue; 82718334Speter 82890075Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 82990075Sobrien if (REG_NOTE_KIND (note) == REG_INC) 83090075Sobrien no_equiv (XEXP (note, 0), note, NULL); 83152284Sobrien 83290075Sobrien set = single_set (insn); 83352284Sobrien 83490075Sobrien /* If this insn contains more (or less) than a single SET, 83590075Sobrien only mark all destinations as having no known equivalence. */ 83690075Sobrien if (set == 0) 83752284Sobrien { 83890075Sobrien note_stores (PATTERN (insn), no_equiv, NULL); 83990075Sobrien continue; 84052284Sobrien } 84190075Sobrien else if (GET_CODE (PATTERN (insn)) == PARALLEL) 84290075Sobrien { 84390075Sobrien int i; 84452284Sobrien 84590075Sobrien for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) 84690075Sobrien { 84790075Sobrien rtx part = XVECEXP (PATTERN (insn), 0, i); 84890075Sobrien if (part != set) 84990075Sobrien note_stores (part, no_equiv, NULL); 85090075Sobrien } 85190075Sobrien } 85218334Speter 85390075Sobrien dest = SET_DEST (set); 85490075Sobrien src = SET_SRC (set); 85518334Speter 856169689Skan /* See if this is setting up the equivalence between an argument 857169689Skan register and its stack slot. */ 858169689Skan note = find_reg_note (insn, REG_EQUIV, NULL_RTX); 859169689Skan if (note) 860169689Skan { 861169689Skan gcc_assert (REG_P (dest)); 862169689Skan regno = REGNO (dest); 86350397Sobrien 864169689Skan /* Note that we don't want to clear reg_equiv_init even if there 865169689Skan are multiple sets of this register. */ 866169689Skan reg_equiv[regno].is_arg_equivalence = 1; 86750397Sobrien 868169689Skan /* Record for reload that this is an equivalencing insn. */ 869169689Skan if (rtx_equal_p (src, XEXP (note, 0))) 870169689Skan reg_equiv_init[regno] 871169689Skan = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]); 87218334Speter 873169689Skan /* Continue normally in case this is a candidate for 874169689Skan replacements. */ 87590075Sobrien } 87652284Sobrien 877169689Skan if (!optimize) 878169689Skan continue; 879169689Skan 88090075Sobrien /* We only handle the case of a pseudo register being set 88190075Sobrien once, or always to the same value. */ 88290075Sobrien /* ??? The mn10200 port breaks if we add equivalences for 88390075Sobrien values that need an ADDRESS_REGS register and set them equivalent 88490075Sobrien to a MEM of a pseudo. The actual problem is in the over-conservative 88590075Sobrien handling of INPADDR_ADDRESS / INPUT_ADDRESS / INPUT triples in 88690075Sobrien calculate_needs, but we traditionally work around this problem 88790075Sobrien here by rejecting equivalences when the destination is in a register 88890075Sobrien that's likely spilled. This is fragile, of course, since the 88990075Sobrien preferred class of a pseudo depends on all instructions that set 89090075Sobrien or use it. */ 89118334Speter 892169689Skan if (!REG_P (dest) 89390075Sobrien || (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER 89490075Sobrien || reg_equiv[regno].init_insns == const0_rtx 89590075Sobrien || (CLASS_LIKELY_SPILLED_P (reg_preferred_class (regno)) 896169689Skan && MEM_P (src) && ! reg_equiv[regno].is_arg_equivalence)) 89790075Sobrien { 898132718Skan /* This might be setting a SUBREG of a pseudo, a pseudo that is 89990075Sobrien also set somewhere else to a constant. */ 90090075Sobrien note_stores (set, no_equiv, NULL); 90190075Sobrien continue; 90290075Sobrien } 90318334Speter 90490075Sobrien note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 90518334Speter 90690075Sobrien /* cse sometimes generates function invariants, but doesn't put a 90790075Sobrien REG_EQUAL note on the insn. Since this note would be redundant, 90890075Sobrien there's no point creating it earlier than here. */ 90990075Sobrien if (! note && ! rtx_varies_p (src, 0)) 91090075Sobrien note = set_unique_reg_note (insn, REG_EQUAL, src); 91118334Speter 91290075Sobrien /* Don't bother considering a REG_EQUAL note containing an EXPR_LIST 91390075Sobrien since it represents a function call */ 91490075Sobrien if (note && GET_CODE (XEXP (note, 0)) == EXPR_LIST) 91590075Sobrien note = NULL_RTX; 91618334Speter 91790075Sobrien if (REG_N_SETS (regno) != 1 91890075Sobrien && (! note 91990075Sobrien || rtx_varies_p (XEXP (note, 0), 0) 92090075Sobrien || (reg_equiv[regno].replacement 92190075Sobrien && ! rtx_equal_p (XEXP (note, 0), 92290075Sobrien reg_equiv[regno].replacement)))) 92390075Sobrien { 92490075Sobrien no_equiv (dest, set, NULL); 92590075Sobrien continue; 92690075Sobrien } 92790075Sobrien /* Record this insn as initializing this register. */ 92890075Sobrien reg_equiv[regno].init_insns 92990075Sobrien = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv[regno].init_insns); 93018334Speter 93190075Sobrien /* If this register is known to be equal to a constant, record that 93290075Sobrien it is always equivalent to the constant. */ 93390075Sobrien if (note && ! rtx_varies_p (XEXP (note, 0), 0)) 93490075Sobrien PUT_MODE (note, (enum machine_mode) REG_EQUIV); 93518334Speter 93690075Sobrien /* If this insn introduces a "constant" register, decrease the priority 93790075Sobrien of that register. Record this insn if the register is only used once 93890075Sobrien more and the equivalence value is the same as our source. 93918334Speter 94090075Sobrien The latter condition is checked for two reasons: First, it is an 94190075Sobrien indication that it may be more efficient to actually emit the insn 94290075Sobrien as written (if no registers are available, reload will substitute 94390075Sobrien the equivalence). Secondly, it avoids problems with any registers 94490075Sobrien dying in this insn whose death notes would be missed. 94518334Speter 94690075Sobrien If we don't have a REG_EQUIV note, see if this insn is loading 94790075Sobrien a register used only in one basic block from a MEM. If so, and the 94890075Sobrien MEM remains unchanged for the life of the register, add a REG_EQUIV 94990075Sobrien note. */ 95018334Speter 95190075Sobrien note = find_reg_note (insn, REG_EQUIV, NULL_RTX); 95290075Sobrien 95390075Sobrien if (note == 0 && REG_BASIC_BLOCK (regno) >= 0 954169689Skan && MEM_P (SET_SRC (set)) 95590075Sobrien && validate_equiv_mem (insn, dest, SET_SRC (set))) 95690075Sobrien REG_NOTES (insn) = note = gen_rtx_EXPR_LIST (REG_EQUIV, SET_SRC (set), 95790075Sobrien REG_NOTES (insn)); 95890075Sobrien 95990075Sobrien if (note) 96050397Sobrien { 96190075Sobrien int regno = REGNO (dest); 962169689Skan rtx x = XEXP (note, 0); 96318334Speter 964169689Skan /* If we haven't done so, record for reload that this is an 965169689Skan equivalencing insn. */ 966169689Skan if (!reg_equiv[regno].is_arg_equivalence) 967169689Skan reg_equiv_init[regno] 968169689Skan = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init[regno]); 969169689Skan 97090075Sobrien /* Record whether or not we created a REG_EQUIV note for a LABEL_REF. 97190075Sobrien We might end up substituting the LABEL_REF for uses of the 97290075Sobrien pseudo here or later. That kind of transformation may turn an 97390075Sobrien indirect jump into a direct jump, in which case we must rerun the 97490075Sobrien jump optimizer to ensure that the JUMP_LABEL fields are valid. */ 975169689Skan if (GET_CODE (x) == LABEL_REF 976169689Skan || (GET_CODE (x) == CONST 977169689Skan && GET_CODE (XEXP (x, 0)) == PLUS 978169689Skan && (GET_CODE (XEXP (XEXP (x, 0), 0)) == LABEL_REF))) 97990075Sobrien recorded_label_ref = 1; 98018334Speter 981169689Skan reg_equiv[regno].replacement = x; 982102780Skan reg_equiv[regno].src_p = &SET_SRC (set); 98390075Sobrien reg_equiv[regno].loop_depth = loop_depth; 98418334Speter 98590075Sobrien /* Don't mess with things live during setjmp. */ 98690075Sobrien if (REG_LIVE_LENGTH (regno) >= 0 && optimize) 98790075Sobrien { 98890075Sobrien /* Note that the statement below does not affect the priority 98990075Sobrien in local-alloc! */ 99090075Sobrien REG_LIVE_LENGTH (regno) *= 2; 99150397Sobrien 99290075Sobrien /* If the register is referenced exactly twice, meaning it is 99390075Sobrien set once and used once, indicate that the reference may be 99490075Sobrien replaced by the equivalence we computed above. Do this 99590075Sobrien even if the register is only used in one block so that 99690075Sobrien dependencies can be handled where the last register is 99790075Sobrien used in a different block (i.e. HIGH / LO_SUM sequences) 99890075Sobrien and to reduce the number of registers alive across 99990075Sobrien calls. */ 100090075Sobrien 1001169689Skan if (REG_N_REFS (regno) == 2 1002169689Skan && (rtx_equal_p (x, src) 1003169689Skan || ! equiv_init_varies_p (src)) 1004169689Skan && NONJUMP_INSN_P (insn) 1005169689Skan && equiv_init_movable_p (PATTERN (insn), regno)) 1006169689Skan reg_equiv[regno].replace = 1; 100790075Sobrien } 100850397Sobrien } 100918334Speter } 101018334Speter } 101118334Speter 1012169689Skan if (!optimize) 1013169689Skan goto out; 1014169689Skan 1015169689Skan /* A second pass, to gather additional equivalences with memory. This needs 1016169689Skan to be done after we know which registers we are going to replace. */ 1017169689Skan 1018169689Skan for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 1019169689Skan { 1020169689Skan rtx set, src, dest; 1021169689Skan unsigned regno; 1022169689Skan 1023169689Skan if (! INSN_P (insn)) 1024169689Skan continue; 1025169689Skan 1026169689Skan set = single_set (insn); 1027169689Skan if (! set) 1028169689Skan continue; 1029169689Skan 1030169689Skan dest = SET_DEST (set); 1031169689Skan src = SET_SRC (set); 1032169689Skan 1033169689Skan /* If this sets a MEM to the contents of a REG that is only used 1034169689Skan in a single basic block, see if the register is always equivalent 1035169689Skan to that memory location and if moving the store from INSN to the 1036169689Skan insn that set REG is safe. If so, put a REG_EQUIV note on the 1037169689Skan initializing insn. 1038169689Skan 1039169689Skan Don't add a REG_EQUIV note if the insn already has one. The existing 1040169689Skan REG_EQUIV is likely more useful than the one we are adding. 1041169689Skan 1042169689Skan If one of the regs in the address has reg_equiv[REGNO].replace set, 1043169689Skan then we can't add this REG_EQUIV note. The reg_equiv[REGNO].replace 1044169689Skan optimization may move the set of this register immediately before 1045169689Skan insn, which puts it after reg_equiv[REGNO].init_insns, and hence 1046169689Skan the mention in the REG_EQUIV note would be to an uninitialized 1047169689Skan pseudo. */ 1048169689Skan 1049169689Skan if (MEM_P (dest) && REG_P (src) 1050169689Skan && (regno = REGNO (src)) >= FIRST_PSEUDO_REGISTER 1051169689Skan && REG_BASIC_BLOCK (regno) >= 0 1052169689Skan && REG_N_SETS (regno) == 1 1053169689Skan && reg_equiv[regno].init_insns != 0 1054169689Skan && reg_equiv[regno].init_insns != const0_rtx 1055169689Skan && ! find_reg_note (XEXP (reg_equiv[regno].init_insns, 0), 1056169689Skan REG_EQUIV, NULL_RTX) 1057169689Skan && ! contains_replace_regs (XEXP (dest, 0))) 1058169689Skan { 1059169689Skan rtx init_insn = XEXP (reg_equiv[regno].init_insns, 0); 1060169689Skan if (validate_equiv_mem (init_insn, src, dest) 1061169689Skan && ! memref_used_between_p (dest, init_insn, insn)) 1062169689Skan { 1063169689Skan REG_NOTES (init_insn) 1064169689Skan = gen_rtx_EXPR_LIST (REG_EQUIV, dest, 1065169689Skan REG_NOTES (init_insn)); 1066169689Skan /* This insn makes the equivalence, not the one initializing 1067169689Skan the register. */ 1068169689Skan reg_equiv_init[regno] 1069169689Skan = gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX); 1070169689Skan } 1071169689Skan } 1072169689Skan } 1073169689Skan 107450397Sobrien /* Now scan all regs killed in an insn to see if any of them are 107550397Sobrien registers only used that once. If so, see if we can replace the 1076169689Skan reference with the equivalent form. If we can, delete the 107750397Sobrien initializing reference and this register will go away. If we 1078132718Skan can't replace the reference, and the initializing reference is 107990075Sobrien within the same loop (or in an inner loop), then move the register 108090075Sobrien initialization just before the use, so that they are in the same 108190075Sobrien basic block. */ 1082117395Skan FOR_EACH_BB_REVERSE (bb) 108318334Speter { 108490075Sobrien loop_depth = bb->loop_depth; 1085132718Skan for (insn = BB_END (bb); 1086132718Skan insn != PREV_INSN (BB_HEAD (bb)); 1087132718Skan insn = PREV_INSN (insn)) 108890075Sobrien { 108990075Sobrien rtx link; 109050397Sobrien 109190075Sobrien if (! INSN_P (insn)) 109290075Sobrien continue; 109390075Sobrien 1094169689Skan /* Don't substitute into a non-local goto, this confuses CFG. */ 1095169689Skan if (JUMP_P (insn) 1096169689Skan && find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX)) 1097169689Skan continue; 1098169689Skan 109990075Sobrien for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 110050397Sobrien { 110190075Sobrien if (REG_NOTE_KIND (link) == REG_DEAD 110290075Sobrien /* Make sure this insn still refers to the register. */ 110390075Sobrien && reg_mentioned_p (XEXP (link, 0), PATTERN (insn))) 110450397Sobrien { 110590075Sobrien int regno = REGNO (XEXP (link, 0)); 110690075Sobrien rtx equiv_insn; 110790075Sobrien 110890075Sobrien if (! reg_equiv[regno].replace 110990075Sobrien || reg_equiv[regno].loop_depth < loop_depth) 111090075Sobrien continue; 111190075Sobrien 111290075Sobrien /* reg_equiv[REGNO].replace gets set only when 111390075Sobrien REG_N_REFS[REGNO] is 2, i.e. the register is set 111490075Sobrien once and used once. (If it were only set, but not used, 111590075Sobrien flow would have deleted the setting insns.) Hence 111690075Sobrien there can only be one insn in reg_equiv[REGNO].init_insns. */ 1117169689Skan gcc_assert (reg_equiv[regno].init_insns 1118169689Skan && !XEXP (reg_equiv[regno].init_insns, 1)); 111990075Sobrien equiv_insn = XEXP (reg_equiv[regno].init_insns, 0); 112050397Sobrien 112190075Sobrien /* We may not move instructions that can throw, since 112290075Sobrien that changes basic block boundaries and we are not 112390075Sobrien prepared to adjust the CFG to match. */ 112490075Sobrien if (can_throw_internal (equiv_insn)) 112590075Sobrien continue; 112650397Sobrien 112790075Sobrien if (asm_noperands (PATTERN (equiv_insn)) < 0 112890075Sobrien && validate_replace_rtx (regno_reg_rtx[regno], 1129102780Skan *(reg_equiv[regno].src_p), insn)) 113090075Sobrien { 113190075Sobrien rtx equiv_link; 113290075Sobrien rtx last_link; 113390075Sobrien rtx note; 113418334Speter 113590075Sobrien /* Find the last note. */ 113690075Sobrien for (last_link = link; XEXP (last_link, 1); 113790075Sobrien last_link = XEXP (last_link, 1)) 113890075Sobrien ; 113918334Speter 114090075Sobrien /* Append the REG_DEAD notes from equiv_insn. */ 114190075Sobrien equiv_link = REG_NOTES (equiv_insn); 114290075Sobrien while (equiv_link) 114390075Sobrien { 114490075Sobrien note = equiv_link; 114590075Sobrien equiv_link = XEXP (equiv_link, 1); 114690075Sobrien if (REG_NOTE_KIND (note) == REG_DEAD) 114790075Sobrien { 114890075Sobrien remove_note (equiv_insn, note); 114990075Sobrien XEXP (last_link, 1) = note; 115090075Sobrien XEXP (note, 1) = NULL_RTX; 115190075Sobrien last_link = note; 115290075Sobrien } 115390075Sobrien } 115450397Sobrien 115590075Sobrien remove_death (regno, insn); 115690075Sobrien REG_N_REFS (regno) = 0; 115790075Sobrien REG_FREQ (regno) = 0; 115890075Sobrien delete_insn (equiv_insn); 1159117395Skan 116090075Sobrien reg_equiv[regno].init_insns 116190075Sobrien = XEXP (reg_equiv[regno].init_insns, 1); 1162169689Skan 1163169689Skan /* Remember to clear REGNO from all basic block's live 1164169689Skan info. */ 1165169689Skan SET_REGNO_REG_SET (&cleared_regs, regno); 1166169689Skan clear_regnos++; 1167169689Skan reg_equiv_init[regno] = NULL_RTX; 116890075Sobrien } 116990075Sobrien /* Move the initialization of the register to just before 117090075Sobrien INSN. Update the flow information. */ 117190075Sobrien else if (PREV_INSN (insn) != equiv_insn) 117290075Sobrien { 117390075Sobrien rtx new_insn; 117450397Sobrien 117590075Sobrien new_insn = emit_insn_before (PATTERN (equiv_insn), insn); 117690075Sobrien REG_NOTES (new_insn) = REG_NOTES (equiv_insn); 117790075Sobrien REG_NOTES (equiv_insn) = 0; 117850397Sobrien 1179169689Skan /* Make sure this insn is recognized before 1180169689Skan reload begins, otherwise 1181169689Skan eliminate_regs_in_insn will die. */ 118290075Sobrien INSN_CODE (new_insn) = INSN_CODE (equiv_insn); 118350397Sobrien 118490075Sobrien delete_insn (equiv_insn); 118550397Sobrien 118690075Sobrien XEXP (reg_equiv[regno].init_insns, 0) = new_insn; 118750397Sobrien 1188117395Skan REG_BASIC_BLOCK (regno) = bb->index; 118990075Sobrien REG_N_CALLS_CROSSED (regno) = 0; 1190161651Skan REG_N_THROWING_CALLS_CROSSED (regno) = 0; 119190075Sobrien REG_LIVE_LENGTH (regno) = 2; 119290075Sobrien 1193132718Skan if (insn == BB_HEAD (bb)) 1194132718Skan BB_HEAD (bb) = PREV_INSN (insn); 119590075Sobrien 119690075Sobrien /* Remember to clear REGNO from all basic block's live 119790075Sobrien info. */ 119890075Sobrien SET_REGNO_REG_SET (&cleared_regs, regno); 119990075Sobrien clear_regnos++; 1200169689Skan reg_equiv_init[regno] 1201169689Skan = gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX); 120290075Sobrien } 120350397Sobrien } 120450397Sobrien } 120550397Sobrien } 120618334Speter } 120790075Sobrien 120890075Sobrien /* Clear all dead REGNOs from all basic block's live info. */ 120990075Sobrien if (clear_regnos) 121090075Sobrien { 1211169689Skan unsigned j; 1212169689Skan 121390075Sobrien if (clear_regnos > 8) 1214117395Skan { 1215117395Skan FOR_EACH_BB (bb) 121690075Sobrien { 1217169689Skan AND_COMPL_REG_SET (bb->il.rtl->global_live_at_start, 1218169689Skan &cleared_regs); 1219169689Skan AND_COMPL_REG_SET (bb->il.rtl->global_live_at_end, 1220169689Skan &cleared_regs); 122190075Sobrien } 122290075Sobrien } 122390075Sobrien else 1224169689Skan { 1225169689Skan reg_set_iterator rsi; 1226169689Skan EXECUTE_IF_SET_IN_REG_SET (&cleared_regs, 0, j, rsi) 1227169689Skan { 1228169689Skan FOR_EACH_BB (bb) 1229169689Skan { 1230169689Skan CLEAR_REGNO_REG_SET (bb->il.rtl->global_live_at_start, j); 1231169689Skan CLEAR_REGNO_REG_SET (bb->il.rtl->global_live_at_end, j); 1232169689Skan } 1233169689Skan } 1234169689Skan } 123590075Sobrien } 123690075Sobrien 1237169689Skan out: 123890075Sobrien /* Clean up. */ 123990075Sobrien end_alias_analysis (); 124090075Sobrien CLEAR_REG_SET (&cleared_regs); 124190075Sobrien free (reg_equiv); 124218334Speter} 124352284Sobrien 124452284Sobrien/* Mark REG as having no known equivalence. 1245132718Skan Some instructions might have been processed before and furnished 124652284Sobrien with REG_EQUIV notes for this register; these notes will have to be 124752284Sobrien removed. 124852284Sobrien STORE is the piece of RTL that does the non-constant / conflicting 124952284Sobrien assignment - a SET, CLOBBER or REG_INC note. It is currently not used, 125052284Sobrien but needs to be there because this function is called from note_stores. */ 125152284Sobrienstatic void 1252132718Skanno_equiv (rtx reg, rtx store ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED) 125352284Sobrien{ 125452284Sobrien int regno; 125552284Sobrien rtx list; 125652284Sobrien 1257169689Skan if (!REG_P (reg)) 125852284Sobrien return; 125952284Sobrien regno = REGNO (reg); 126090075Sobrien list = reg_equiv[regno].init_insns; 126152284Sobrien if (list == const0_rtx) 126252284Sobrien return; 1263169689Skan reg_equiv[regno].init_insns = const0_rtx; 1264169689Skan reg_equiv[regno].replacement = NULL_RTX; 1265169689Skan /* This doesn't matter for equivalences made for argument registers, we 1266169689Skan should keep their initialization insns. */ 1267169689Skan if (reg_equiv[regno].is_arg_equivalence) 1268169689Skan return; 1269169689Skan reg_equiv_init[regno] = NULL_RTX; 127052284Sobrien for (; list; list = XEXP (list, 1)) 127152284Sobrien { 127252284Sobrien rtx insn = XEXP (list, 0); 127352284Sobrien remove_note (insn, find_reg_note (insn, REG_EQUIV, NULL_RTX)); 127452284Sobrien } 127552284Sobrien} 127618334Speter 127718334Speter/* Allocate hard regs to the pseudo regs used only within block number B. 127818334Speter Only the pseudos that die but once can be handled. */ 127918334Speter 128018334Speterstatic void 1281132718Skanblock_alloc (int b) 128218334Speter{ 128390075Sobrien int i, q; 128490075Sobrien rtx insn; 128590075Sobrien rtx note, hard_reg; 128618334Speter int insn_number = 0; 128718334Speter int insn_count = 0; 128818334Speter int max_uid = get_max_uid (); 128918334Speter int *qty_order; 129018334Speter int no_conflict_combined_regno = -1; 129118334Speter 129218334Speter /* Count the instructions in the basic block. */ 129318334Speter 1294132718Skan insn = BB_END (BASIC_BLOCK (b)); 129518334Speter while (1) 129618334Speter { 1297169689Skan if (!NOTE_P (insn)) 1298169689Skan { 1299169689Skan ++insn_count; 1300169689Skan gcc_assert (insn_count <= max_uid); 1301169689Skan } 1302132718Skan if (insn == BB_HEAD (BASIC_BLOCK (b))) 130318334Speter break; 130418334Speter insn = PREV_INSN (insn); 130518334Speter } 130618334Speter 130718334Speter /* +2 to leave room for a post_mark_life at the last insn and for 130818334Speter the birth of a CLOBBER in the first insn. */ 1309169689Skan regs_live_at = XCNEWVEC (HARD_REG_SET, 2 * insn_count + 2); 131018334Speter 131118334Speter /* Initialize table of hardware registers currently live. */ 131218334Speter 1313169689Skan REG_SET_TO_HARD_REG_SET (regs_live, 1314169689Skan BASIC_BLOCK (b)->il.rtl->global_live_at_start); 131518334Speter 131618334Speter /* This loop scans the instructions of the basic block 131718334Speter and assigns quantities to registers. 131818334Speter It computes which registers to tie. */ 131918334Speter 1320132718Skan insn = BB_HEAD (BASIC_BLOCK (b)); 132118334Speter while (1) 132218334Speter { 1323169689Skan if (!NOTE_P (insn)) 132418334Speter insn_number++; 132518334Speter 132690075Sobrien if (INSN_P (insn)) 132718334Speter { 132890075Sobrien rtx link, set; 132990075Sobrien int win = 0; 133090075Sobrien rtx r0, r1 = NULL_RTX; 133118334Speter int combined_regno = -1; 133218334Speter int i; 133318334Speter 133418334Speter this_insn_number = insn_number; 133518334Speter this_insn = insn; 133618334Speter 133752284Sobrien extract_insn (insn); 133818334Speter which_alternative = -1; 133918334Speter 134018334Speter /* Is this insn suitable for tying two registers? 134118334Speter If so, try doing that. 134218334Speter Suitable insns are those with at least two operands and where 134318334Speter operand 0 is an output that is a register that is not 134418334Speter earlyclobber. 134518334Speter 134618334Speter We can tie operand 0 with some operand that dies in this insn. 134718334Speter First look for operands that are required to be in the same 134818334Speter register as operand 0. If we find such, only try tying that 134918334Speter operand or one that can be put into that operand if the 135018334Speter operation is commutative. If we don't find an operand 135118334Speter that is required to be in the same register as operand 0, 135218334Speter we can tie with any operand. 135318334Speter 135418334Speter Subregs in place of regs are also ok. 135518334Speter 135618334Speter If tying is done, WIN is set nonzero. */ 135718334Speter 135890075Sobrien if (optimize 135990075Sobrien && recog_data.n_operands > 1 136090075Sobrien && recog_data.constraints[0][0] == '=' 136190075Sobrien && recog_data.constraints[0][1] != '&') 136218334Speter { 136318334Speter /* If non-negative, is an operand that must match operand 0. */ 136418334Speter int must_match_0 = -1; 136518334Speter /* Counts number of alternatives that require a match with 136618334Speter operand 0. */ 136718334Speter int n_matching_alts = 0; 136818334Speter 136990075Sobrien for (i = 1; i < recog_data.n_operands; i++) 137018334Speter { 137190075Sobrien const char *p = recog_data.constraints[i]; 137290075Sobrien int this_match = requires_inout (p); 137318334Speter 137418334Speter n_matching_alts += this_match; 137590075Sobrien if (this_match == recog_data.n_alternatives) 137618334Speter must_match_0 = i; 137718334Speter } 137818334Speter 137990075Sobrien r0 = recog_data.operand[0]; 138090075Sobrien for (i = 1; i < recog_data.n_operands; i++) 138118334Speter { 138218334Speter /* Skip this operand if we found an operand that 138318334Speter must match operand 0 and this operand isn't it 138418334Speter and can't be made to be it by commutativity. */ 138518334Speter 138618334Speter if (must_match_0 >= 0 && i != must_match_0 138718334Speter && ! (i == must_match_0 + 1 138890075Sobrien && recog_data.constraints[i-1][0] == '%') 138918334Speter && ! (i == must_match_0 - 1 139090075Sobrien && recog_data.constraints[i][0] == '%')) 139118334Speter continue; 139218334Speter 139318334Speter /* Likewise if each alternative has some operand that 139490075Sobrien must match operand zero. In that case, skip any 139518334Speter operand that doesn't list operand 0 since we know that 139618334Speter the operand always conflicts with operand 0. We 1397132718Skan ignore commutativity in this case to keep things simple. */ 139890075Sobrien if (n_matching_alts == recog_data.n_alternatives 139990075Sobrien && 0 == requires_inout (recog_data.constraints[i])) 140018334Speter continue; 140118334Speter 140290075Sobrien r1 = recog_data.operand[i]; 140318334Speter 140418334Speter /* If the operand is an address, find a register in it. 140518334Speter There may be more than one register, but we only try one 140618334Speter of them. */ 1407117395Skan if (recog_data.constraints[i][0] == 'p' 1408132718Skan || EXTRA_ADDRESS_CONSTRAINT (recog_data.constraints[i][0], 1409132718Skan recog_data.constraints[i])) 141018334Speter while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT) 141118334Speter r1 = XEXP (r1, 0); 141218334Speter 141390075Sobrien /* Avoid making a call-saved register unnecessarily 141490075Sobrien clobbered. */ 141590075Sobrien hard_reg = get_hard_reg_initial_reg (cfun, r1); 141690075Sobrien if (hard_reg != NULL_RTX) 141790075Sobrien { 1418169689Skan if (REG_P (hard_reg) 1419169689Skan && REGNO (hard_reg) < FIRST_PSEUDO_REGISTER 1420169689Skan && !call_used_regs[REGNO (hard_reg)]) 142190075Sobrien continue; 142290075Sobrien } 142390075Sobrien 1424169689Skan if (REG_P (r0) || GET_CODE (r0) == SUBREG) 142518334Speter { 142618334Speter /* We have two priorities for hard register preferences. 142718334Speter If we have a move insn or an insn whose first input 142818334Speter can only be in the same register as the output, give 142918334Speter priority to an equivalence found from that insn. */ 143018334Speter int may_save_copy 143190075Sobrien = (r1 == recog_data.operand[i] && must_match_0 >= 0); 143290075Sobrien 1433169689Skan if (REG_P (r1) || GET_CODE (r1) == SUBREG) 143418334Speter win = combine_regs (r1, r0, may_save_copy, 143518334Speter insn_number, insn, 0); 143618334Speter } 143718334Speter if (win) 143818334Speter break; 143918334Speter } 144018334Speter } 144118334Speter 144218334Speter /* Recognize an insn sequence with an ultimate result 144318334Speter which can safely overlap one of the inputs. 144418334Speter The sequence begins with a CLOBBER of its result, 144518334Speter and ends with an insn that copies the result to itself 144618334Speter and has a REG_EQUAL note for an equivalent formula. 144718334Speter That note indicates what the inputs are. 144818334Speter The result and the input can overlap if each insn in 144918334Speter the sequence either doesn't mention the input 145018334Speter or has a REG_NO_CONFLICT note to inhibit the conflict. 145118334Speter 145218334Speter We do the combining test at the CLOBBER so that the 145318334Speter destination register won't have had a quantity number 145418334Speter assigned, since that would prevent combining. */ 145518334Speter 145690075Sobrien if (optimize 145790075Sobrien && GET_CODE (PATTERN (insn)) == CLOBBER 145818334Speter && (r0 = XEXP (PATTERN (insn), 0), 1459169689Skan REG_P (r0)) 146018334Speter && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0 146118334Speter && XEXP (link, 0) != 0 1462169689Skan && NONJUMP_INSN_P (XEXP (link, 0)) 146318334Speter && (set = single_set (XEXP (link, 0))) != 0 146418334Speter && SET_DEST (set) == r0 && SET_SRC (set) == r0 146518334Speter && (note = find_reg_note (XEXP (link, 0), REG_EQUAL, 146618334Speter NULL_RTX)) != 0) 146718334Speter { 1468169689Skan if (r1 = XEXP (note, 0), REG_P (r1) 146918334Speter /* Check that we have such a sequence. */ 147018334Speter && no_conflict_p (insn, r0, r1)) 147118334Speter win = combine_regs (r1, r0, 1, insn_number, insn, 1); 147218334Speter else if (GET_RTX_FORMAT (GET_CODE (XEXP (note, 0)))[0] == 'e' 147318334Speter && (r1 = XEXP (XEXP (note, 0), 0), 1474169689Skan REG_P (r1) || GET_CODE (r1) == SUBREG) 147518334Speter && no_conflict_p (insn, r0, r1)) 147618334Speter win = combine_regs (r1, r0, 0, insn_number, insn, 1); 147718334Speter 147818334Speter /* Here we care if the operation to be computed is 147918334Speter commutative. */ 1480169689Skan else if (COMMUTATIVE_P (XEXP (note, 0)) 148118334Speter && (r1 = XEXP (XEXP (note, 0), 1), 1482169689Skan (REG_P (r1) || GET_CODE (r1) == SUBREG)) 148318334Speter && no_conflict_p (insn, r0, r1)) 148418334Speter win = combine_regs (r1, r0, 0, insn_number, insn, 1); 148518334Speter 148618334Speter /* If we did combine something, show the register number 148718334Speter in question so that we know to ignore its death. */ 148818334Speter if (win) 148918334Speter no_conflict_combined_regno = REGNO (r1); 149018334Speter } 149118334Speter 149218334Speter /* If registers were just tied, set COMBINED_REGNO 149318334Speter to the number of the register used in this insn 149418334Speter that was tied to the register set in this insn. 149518334Speter This register's qty should not be "killed". */ 149618334Speter 149718334Speter if (win) 149818334Speter { 149918334Speter while (GET_CODE (r1) == SUBREG) 150018334Speter r1 = SUBREG_REG (r1); 150118334Speter combined_regno = REGNO (r1); 150218334Speter } 150318334Speter 150418334Speter /* Mark the death of everything that dies in this instruction, 150518334Speter except for anything that was just combined. */ 150618334Speter 150718334Speter for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 150818334Speter if (REG_NOTE_KIND (link) == REG_DEAD 1509169689Skan && REG_P (XEXP (link, 0)) 151090075Sobrien && combined_regno != (int) REGNO (XEXP (link, 0)) 151190075Sobrien && (no_conflict_combined_regno != (int) REGNO (XEXP (link, 0)) 151290075Sobrien || ! find_reg_note (insn, REG_NO_CONFLICT, 151390075Sobrien XEXP (link, 0)))) 151418334Speter wipe_dead_reg (XEXP (link, 0), 0); 151518334Speter 151618334Speter /* Allocate qty numbers for all registers local to this block 151718334Speter that are born (set) in this instruction. 151818334Speter A pseudo that already has a qty is not changed. */ 151918334Speter 152090075Sobrien note_stores (PATTERN (insn), reg_is_set, NULL); 152118334Speter 152218334Speter /* If anything is set in this insn and then unused, mark it as dying 152318334Speter after this insn, so it will conflict with our outputs. This 152418334Speter can't match with something that combined, and it doesn't matter 152518334Speter if it did. Do this after the calls to reg_is_set since these 152618334Speter die after, not during, the current insn. */ 152718334Speter 152818334Speter for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 152918334Speter if (REG_NOTE_KIND (link) == REG_UNUSED 1530169689Skan && REG_P (XEXP (link, 0))) 153118334Speter wipe_dead_reg (XEXP (link, 0), 1); 153218334Speter 153390075Sobrien /* If this is an insn that has a REG_RETVAL note pointing at a 153418334Speter CLOBBER insn, we have reached the end of a REG_NO_CONFLICT 153518334Speter block, so clear any register number that combined within it. */ 153618334Speter if ((note = find_reg_note (insn, REG_RETVAL, NULL_RTX)) != 0 1537169689Skan && NONJUMP_INSN_P (XEXP (note, 0)) 153818334Speter && GET_CODE (PATTERN (XEXP (note, 0))) == CLOBBER) 153918334Speter no_conflict_combined_regno = -1; 154018334Speter } 154118334Speter 154218334Speter /* Set the registers live after INSN_NUMBER. Note that we never 154318334Speter record the registers live before the block's first insn, since no 154418334Speter pseudos we care about are live before that insn. */ 154518334Speter 154618334Speter IOR_HARD_REG_SET (regs_live_at[2 * insn_number], regs_live); 154718334Speter IOR_HARD_REG_SET (regs_live_at[2 * insn_number + 1], regs_live); 154818334Speter 1549132718Skan if (insn == BB_END (BASIC_BLOCK (b))) 155018334Speter break; 155118334Speter 155218334Speter insn = NEXT_INSN (insn); 155318334Speter } 155418334Speter 155518334Speter /* Now every register that is local to this basic block 155618334Speter should have been given a quantity, or else -1 meaning ignore it. 155790075Sobrien Every quantity should have a known birth and death. 155818334Speter 155918334Speter Order the qtys so we assign them registers in order of the 156018334Speter number of suggested registers they need so we allocate those with 156118334Speter the most restrictive needs first. */ 156218334Speter 1563169689Skan qty_order = XNEWVEC (int, next_qty); 156418334Speter for (i = 0; i < next_qty; i++) 156518334Speter qty_order[i] = i; 156618334Speter 156718334Speter#define EXCHANGE(I1, I2) \ 156818334Speter { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; } 156918334Speter 157018334Speter switch (next_qty) 157118334Speter { 157218334Speter case 3: 157318334Speter /* Make qty_order[2] be the one to allocate last. */ 157418334Speter if (qty_sugg_compare (0, 1) > 0) 157518334Speter EXCHANGE (0, 1); 157618334Speter if (qty_sugg_compare (1, 2) > 0) 157718334Speter EXCHANGE (2, 1); 157818334Speter 157950397Sobrien /* ... Fall through ... */ 158018334Speter case 2: 158118334Speter /* Put the best one to allocate in qty_order[0]. */ 158218334Speter if (qty_sugg_compare (0, 1) > 0) 158318334Speter EXCHANGE (0, 1); 158418334Speter 158550397Sobrien /* ... Fall through ... */ 158618334Speter 158718334Speter case 1: 158818334Speter case 0: 158918334Speter /* Nothing to do here. */ 159018334Speter break; 159118334Speter 159218334Speter default: 159318334Speter qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1); 159418334Speter } 159518334Speter 159618334Speter /* Try to put each quantity in a suggested physical register, if it has one. 159718334Speter This may cause registers to be allocated that otherwise wouldn't be, but 159818334Speter this seems acceptable in local allocation (unlike global allocation). */ 159918334Speter for (i = 0; i < next_qty; i++) 160018334Speter { 160118334Speter q = qty_order[i]; 160218334Speter if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0) 160390075Sobrien qty[q].phys_reg = find_free_reg (qty[q].min_class, qty[q].mode, q, 160490075Sobrien 0, 1, qty[q].birth, qty[q].death); 160518334Speter else 160690075Sobrien qty[q].phys_reg = -1; 160718334Speter } 160818334Speter 160990075Sobrien /* Order the qtys so we assign them registers in order of 161090075Sobrien decreasing length of life. Normally call qsort, but if we 161118334Speter have only a very small number of quantities, sort them ourselves. */ 161218334Speter 161318334Speter for (i = 0; i < next_qty; i++) 161418334Speter qty_order[i] = i; 161518334Speter 161618334Speter#define EXCHANGE(I1, I2) \ 161718334Speter { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; } 161818334Speter 161918334Speter switch (next_qty) 162018334Speter { 162118334Speter case 3: 162218334Speter /* Make qty_order[2] be the one to allocate last. */ 162318334Speter if (qty_compare (0, 1) > 0) 162418334Speter EXCHANGE (0, 1); 162518334Speter if (qty_compare (1, 2) > 0) 162618334Speter EXCHANGE (2, 1); 162718334Speter 162850397Sobrien /* ... Fall through ... */ 162918334Speter case 2: 163018334Speter /* Put the best one to allocate in qty_order[0]. */ 163118334Speter if (qty_compare (0, 1) > 0) 163218334Speter EXCHANGE (0, 1); 163318334Speter 163450397Sobrien /* ... Fall through ... */ 163518334Speter 163618334Speter case 1: 163718334Speter case 0: 163818334Speter /* Nothing to do here. */ 163918334Speter break; 164018334Speter 164118334Speter default: 164218334Speter qsort (qty_order, next_qty, sizeof (int), qty_compare_1); 164318334Speter } 164418334Speter 164518334Speter /* Now for each qty that is not a hardware register, 164618334Speter look for a hardware register to put it in. 164718334Speter First try the register class that is cheapest for this qty, 164818334Speter if there is more than one class. */ 164918334Speter 165018334Speter for (i = 0; i < next_qty; i++) 165118334Speter { 165218334Speter q = qty_order[i]; 165390075Sobrien if (qty[q].phys_reg < 0) 165418334Speter { 165550397Sobrien#ifdef INSN_SCHEDULING 165650397Sobrien /* These values represent the adjusted lifetime of a qty so 165750397Sobrien that it conflicts with qtys which appear near the start/end 165850397Sobrien of this qty's lifetime. 165950397Sobrien 166050397Sobrien The purpose behind extending the lifetime of this qty is to 166150397Sobrien discourage the register allocator from creating false 166250397Sobrien dependencies. 166390075Sobrien 166490075Sobrien The adjustment value is chosen to indicate that this qty 166552284Sobrien conflicts with all the qtys in the instructions immediately 166650397Sobrien before and after the lifetime of this qty. 166750397Sobrien 166850397Sobrien Experiments have shown that higher values tend to hurt 166950397Sobrien overall code performance. 167050397Sobrien 167150397Sobrien If allocation using the extended lifetime fails we will try 167250397Sobrien again with the qty's unadjusted lifetime. */ 167390075Sobrien int fake_birth = MAX (0, qty[q].birth - 2 + qty[q].birth % 2); 167452284Sobrien int fake_death = MIN (insn_number * 2 + 1, 167590075Sobrien qty[q].death + 2 - qty[q].death % 2); 167650397Sobrien#endif 167750397Sobrien 167818334Speter if (N_REG_CLASSES > 1) 167918334Speter { 168050397Sobrien#ifdef INSN_SCHEDULING 168150397Sobrien /* We try to avoid using hard registers allocated to qtys which 168250397Sobrien are born immediately after this qty or die immediately before 168350397Sobrien this qty. 168450397Sobrien 168550397Sobrien This optimization is only appropriate when we will run 168650397Sobrien a scheduling pass after reload and we are not optimizing 168750397Sobrien for code size. */ 168850397Sobrien if (flag_schedule_insns_after_reload 168950397Sobrien && !optimize_size 169050397Sobrien && !SMALL_REGISTER_CLASSES) 169150397Sobrien { 169290075Sobrien qty[q].phys_reg = find_free_reg (qty[q].min_class, 169390075Sobrien qty[q].mode, q, 0, 0, 169450397Sobrien fake_birth, fake_death); 169590075Sobrien if (qty[q].phys_reg >= 0) 169650397Sobrien continue; 169750397Sobrien } 169850397Sobrien#endif 169990075Sobrien qty[q].phys_reg = find_free_reg (qty[q].min_class, 170090075Sobrien qty[q].mode, q, 0, 0, 170190075Sobrien qty[q].birth, qty[q].death); 170290075Sobrien if (qty[q].phys_reg >= 0) 170318334Speter continue; 170418334Speter } 170518334Speter 170650397Sobrien#ifdef INSN_SCHEDULING 170750397Sobrien /* Similarly, avoid false dependencies. */ 170850397Sobrien if (flag_schedule_insns_after_reload 170950397Sobrien && !optimize_size 171050397Sobrien && !SMALL_REGISTER_CLASSES 171190075Sobrien && qty[q].alternate_class != NO_REGS) 171290075Sobrien qty[q].phys_reg = find_free_reg (qty[q].alternate_class, 171390075Sobrien qty[q].mode, q, 0, 0, 171450397Sobrien fake_birth, fake_death); 171550397Sobrien#endif 171690075Sobrien if (qty[q].alternate_class != NO_REGS) 171790075Sobrien qty[q].phys_reg = find_free_reg (qty[q].alternate_class, 171890075Sobrien qty[q].mode, q, 0, 0, 171990075Sobrien qty[q].birth, qty[q].death); 172018334Speter } 172118334Speter } 172218334Speter 172318334Speter /* Now propagate the register assignments 172418334Speter to the pseudo regs belonging to the qtys. */ 172518334Speter 172618334Speter for (q = 0; q < next_qty; q++) 172790075Sobrien if (qty[q].phys_reg >= 0) 172818334Speter { 172990075Sobrien for (i = qty[q].first_reg; i >= 0; i = reg_next_in_qty[i]) 173090075Sobrien reg_renumber[i] = qty[q].phys_reg + reg_offset[i]; 173118334Speter } 173290075Sobrien 173390075Sobrien /* Clean up. */ 173490075Sobrien free (regs_live_at); 173590075Sobrien free (qty_order); 173618334Speter} 173718334Speter 173818334Speter/* Compare two quantities' priority for getting real registers. 173918334Speter We give shorter-lived quantities higher priority. 174018334Speter Quantities with more references are also preferred, as are quantities that 174118334Speter require multiple registers. This is the identical prioritization as 174218334Speter done by global-alloc. 174318334Speter 174418334Speter We used to give preference to registers with *longer* lives, but using 174518334Speter the same algorithm in both local- and global-alloc can speed up execution 174618334Speter of some programs by as much as a factor of three! */ 174718334Speter 174850397Sobrien/* Note that the quotient will never be bigger than 174950397Sobrien the value of floor_log2 times the maximum number of 175090075Sobrien times a register can occur in one insn (surely less than 100) 175190075Sobrien weighted by frequency (max REG_FREQ_MAX). 175290075Sobrien Multiplying this by 10000/REG_FREQ_MAX can't overflow. 175350397Sobrien QTY_CMP_PRI is also used by qty_sugg_compare. */ 175450397Sobrien 175550397Sobrien#define QTY_CMP_PRI(q) \ 175690075Sobrien ((int) (((double) (floor_log2 (qty[q].n_refs) * qty[q].freq * qty[q].size) \ 175790075Sobrien / (qty[q].death - qty[q].birth)) * (10000 / REG_FREQ_MAX))) 175850397Sobrien 175918334Speterstatic int 1760132718Skanqty_compare (int q1, int q2) 176118334Speter{ 176250397Sobrien return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 176318334Speter} 176418334Speter 176518334Speterstatic int 1766132718Skanqty_compare_1 (const void *q1p, const void *q2p) 176718334Speter{ 176890075Sobrien int q1 = *(const int *) q1p, q2 = *(const int *) q2p; 176990075Sobrien int tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 177018334Speter 177150397Sobrien if (tem != 0) 177250397Sobrien return tem; 177318334Speter 177418334Speter /* If qtys are equally good, sort by qty number, 177518334Speter so that the results of qsort leave nothing to chance. */ 177650397Sobrien return q1 - q2; 177718334Speter} 177818334Speter 177918334Speter/* Compare two quantities' priority for getting real registers. This version 178018334Speter is called for quantities that have suggested hard registers. First priority 178118334Speter goes to quantities that have copy preferences, then to those that have 178218334Speter normal preferences. Within those groups, quantities with the lower 178318334Speter number of preferences have the highest priority. Of those, we use the same 178418334Speter algorithm as above. */ 178518334Speter 178650397Sobrien#define QTY_CMP_SUGG(q) \ 178750397Sobrien (qty_phys_num_copy_sugg[q] \ 178850397Sobrien ? qty_phys_num_copy_sugg[q] \ 178950397Sobrien : qty_phys_num_sugg[q] * FIRST_PSEUDO_REGISTER) 179050397Sobrien 179118334Speterstatic int 1792132718Skanqty_sugg_compare (int q1, int q2) 179318334Speter{ 179490075Sobrien int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2); 179518334Speter 179650397Sobrien if (tem != 0) 179750397Sobrien return tem; 179890075Sobrien 179950397Sobrien return QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 180018334Speter} 180118334Speter 180218334Speterstatic int 1803132718Skanqty_sugg_compare_1 (const void *q1p, const void *q2p) 180418334Speter{ 180590075Sobrien int q1 = *(const int *) q1p, q2 = *(const int *) q2p; 180690075Sobrien int tem = QTY_CMP_SUGG (q1) - QTY_CMP_SUGG (q2); 180718334Speter 180850397Sobrien if (tem != 0) 180950397Sobrien return tem; 181018334Speter 181150397Sobrien tem = QTY_CMP_PRI (q2) - QTY_CMP_PRI (q1); 181250397Sobrien if (tem != 0) 181350397Sobrien return tem; 181418334Speter 181518334Speter /* If qtys are equally good, sort by qty number, 181618334Speter so that the results of qsort leave nothing to chance. */ 181750397Sobrien return q1 - q2; 181818334Speter} 181950397Sobrien 182050397Sobrien#undef QTY_CMP_SUGG 182150397Sobrien#undef QTY_CMP_PRI 182218334Speter 182318334Speter/* Attempt to combine the two registers (rtx's) USEDREG and SETREG. 182418334Speter Returns 1 if have done so, or 0 if cannot. 182518334Speter 182618334Speter Combining registers means marking them as having the same quantity 182718334Speter and adjusting the offsets within the quantity if either of 1828132718Skan them is a SUBREG. 182918334Speter 183018334Speter We don't actually combine a hard reg with a pseudo; instead 183118334Speter we just record the hard reg as the suggestion for the pseudo's quantity. 183218334Speter If we really combined them, we could lose if the pseudo lives 1833169689Skan across an insn that clobbers the hard reg (eg, movmem). 183418334Speter 1835117395Skan ALREADY_DEAD is nonzero if USEDREG is known to be dead even though 183618334Speter there is no REG_DEAD note on INSN. This occurs during the processing 183718334Speter of REG_NO_CONFLICT blocks. 183818334Speter 1839132718Skan MAY_SAVE_COPY is nonzero if this insn is simply copying USEDREG to 184018334Speter SETREG or if the input and output must share a register. 184118334Speter In that case, we record a hard reg suggestion in QTY_PHYS_COPY_SUGG. 184290075Sobrien 184318334Speter There are elaborate checks for the validity of combining. */ 184418334Speter 184518334Speterstatic int 1846132718Skancombine_regs (rtx usedreg, rtx setreg, int may_save_copy, int insn_number, 1847132718Skan rtx insn, int already_dead) 184818334Speter{ 184990075Sobrien int ureg, sreg; 185090075Sobrien int offset = 0; 185118334Speter int usize, ssize; 185290075Sobrien int sqty; 185318334Speter 185418334Speter /* Determine the numbers and sizes of registers being used. If a subreg 185518334Speter is present that does not change the entire register, don't consider 185618334Speter this a copy insn. */ 185718334Speter 185818334Speter while (GET_CODE (usedreg) == SUBREG) 185918334Speter { 186090075Sobrien rtx subreg = SUBREG_REG (usedreg); 186190075Sobrien 1862169689Skan if (REG_P (subreg)) 186390075Sobrien { 186490075Sobrien if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD) 186590075Sobrien may_save_copy = 0; 186690075Sobrien 186790075Sobrien if (REGNO (subreg) < FIRST_PSEUDO_REGISTER) 186890075Sobrien offset += subreg_regno_offset (REGNO (subreg), 186990075Sobrien GET_MODE (subreg), 187090075Sobrien SUBREG_BYTE (usedreg), 187190075Sobrien GET_MODE (usedreg)); 187290075Sobrien else 187390075Sobrien offset += (SUBREG_BYTE (usedreg) 187490075Sobrien / REGMODE_NATURAL_SIZE (GET_MODE (usedreg))); 187590075Sobrien } 187690075Sobrien 187790075Sobrien usedreg = subreg; 187818334Speter } 187990075Sobrien 1880169689Skan if (!REG_P (usedreg)) 188118334Speter return 0; 188290075Sobrien 188318334Speter ureg = REGNO (usedreg); 188490075Sobrien if (ureg < FIRST_PSEUDO_REGISTER) 1885169689Skan usize = hard_regno_nregs[ureg][GET_MODE (usedreg)]; 188690075Sobrien else 188790075Sobrien usize = ((GET_MODE_SIZE (GET_MODE (usedreg)) 188890075Sobrien + (REGMODE_NATURAL_SIZE (GET_MODE (usedreg)) - 1)) 188990075Sobrien / REGMODE_NATURAL_SIZE (GET_MODE (usedreg))); 189018334Speter 189118334Speter while (GET_CODE (setreg) == SUBREG) 189218334Speter { 189390075Sobrien rtx subreg = SUBREG_REG (setreg); 189490075Sobrien 1895169689Skan if (REG_P (subreg)) 189690075Sobrien { 189790075Sobrien if (GET_MODE_SIZE (GET_MODE (subreg)) > UNITS_PER_WORD) 189890075Sobrien may_save_copy = 0; 189990075Sobrien 190090075Sobrien if (REGNO (subreg) < FIRST_PSEUDO_REGISTER) 190190075Sobrien offset -= subreg_regno_offset (REGNO (subreg), 190290075Sobrien GET_MODE (subreg), 190390075Sobrien SUBREG_BYTE (setreg), 190490075Sobrien GET_MODE (setreg)); 190590075Sobrien else 190690075Sobrien offset -= (SUBREG_BYTE (setreg) 190790075Sobrien / REGMODE_NATURAL_SIZE (GET_MODE (setreg))); 190890075Sobrien } 190990075Sobrien 191090075Sobrien setreg = subreg; 191118334Speter } 191290075Sobrien 1913169689Skan if (!REG_P (setreg)) 191418334Speter return 0; 191590075Sobrien 191618334Speter sreg = REGNO (setreg); 191790075Sobrien if (sreg < FIRST_PSEUDO_REGISTER) 1918169689Skan ssize = hard_regno_nregs[sreg][GET_MODE (setreg)]; 191990075Sobrien else 192090075Sobrien ssize = ((GET_MODE_SIZE (GET_MODE (setreg)) 192190075Sobrien + (REGMODE_NATURAL_SIZE (GET_MODE (setreg)) - 1)) 192290075Sobrien / REGMODE_NATURAL_SIZE (GET_MODE (setreg))); 192318334Speter 192418334Speter /* If UREG is a pseudo-register that hasn't already been assigned a 192518334Speter quantity number, it means that it is not local to this block or dies 192618334Speter more than once. In either event, we can't do anything with it. */ 192718334Speter if ((ureg >= FIRST_PSEUDO_REGISTER && reg_qty[ureg] < 0) 192818334Speter /* Do not combine registers unless one fits within the other. */ 192918334Speter || (offset > 0 && usize + offset > ssize) 193018334Speter || (offset < 0 && usize + offset < ssize) 193118334Speter /* Do not combine with a smaller already-assigned object 193250397Sobrien if that smaller object is already combined with something bigger. */ 193318334Speter || (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER 193490075Sobrien && usize < qty[reg_qty[ureg]].size) 193518334Speter /* Can't combine if SREG is not a register we can allocate. */ 193618334Speter || (sreg >= FIRST_PSEUDO_REGISTER && reg_qty[sreg] == -1) 193718334Speter /* Don't combine with a pseudo mentioned in a REG_NO_CONFLICT note. 193818334Speter These have already been taken care of. This probably wouldn't 193918334Speter combine anyway, but don't take any chances. */ 194018334Speter || (ureg >= FIRST_PSEUDO_REGISTER 194118334Speter && find_reg_note (insn, REG_NO_CONFLICT, usedreg)) 194218334Speter /* Don't tie something to itself. In most cases it would make no 194318334Speter difference, but it would screw up if the reg being tied to itself 194418334Speter also dies in this insn. */ 194518334Speter || ureg == sreg 194618334Speter /* Don't try to connect two different hardware registers. */ 194718334Speter || (ureg < FIRST_PSEUDO_REGISTER && sreg < FIRST_PSEUDO_REGISTER) 194818334Speter /* Don't connect two different machine modes if they have different 194918334Speter implications as to which registers may be used. */ 195018334Speter || !MODES_TIEABLE_P (GET_MODE (usedreg), GET_MODE (setreg))) 195118334Speter return 0; 195218334Speter 195318334Speter /* Now, if UREG is a hard reg and SREG is a pseudo, record the hard reg in 195418334Speter qty_phys_sugg for the pseudo instead of tying them. 195518334Speter 195618334Speter Return "failure" so that the lifespan of UREG is terminated here; 195718334Speter that way the two lifespans will be disjoint and nothing will prevent 195818334Speter the pseudo reg from being given this hard reg. */ 195918334Speter 196018334Speter if (ureg < FIRST_PSEUDO_REGISTER) 196118334Speter { 196218334Speter /* Allocate a quantity number so we have a place to put our 196318334Speter suggestions. */ 196418334Speter if (reg_qty[sreg] == -2) 196518334Speter reg_is_born (setreg, 2 * insn_number); 196618334Speter 196718334Speter if (reg_qty[sreg] >= 0) 196818334Speter { 196918334Speter if (may_save_copy 197018334Speter && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg)) 197118334Speter { 197218334Speter SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg); 197318334Speter qty_phys_num_copy_sugg[reg_qty[sreg]]++; 197418334Speter } 197518334Speter else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg)) 197618334Speter { 197718334Speter SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg); 197818334Speter qty_phys_num_sugg[reg_qty[sreg]]++; 197918334Speter } 198018334Speter } 198118334Speter return 0; 198218334Speter } 198318334Speter 198418334Speter /* Similarly for SREG a hard register and UREG a pseudo register. */ 198518334Speter 198618334Speter if (sreg < FIRST_PSEUDO_REGISTER) 198718334Speter { 198818334Speter if (may_save_copy 198918334Speter && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg)) 199018334Speter { 199118334Speter SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg); 199218334Speter qty_phys_num_copy_sugg[reg_qty[ureg]]++; 199318334Speter } 199418334Speter else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg)) 199518334Speter { 199618334Speter SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg); 199718334Speter qty_phys_num_sugg[reg_qty[ureg]]++; 199818334Speter } 199918334Speter return 0; 200018334Speter } 200118334Speter 200218334Speter /* At this point we know that SREG and UREG are both pseudos. 200318334Speter Do nothing if SREG already has a quantity or is a register that we 200418334Speter don't allocate. */ 200518334Speter if (reg_qty[sreg] >= -1 200618334Speter /* If we are not going to let any regs live across calls, 200718334Speter don't tie a call-crossing reg to a non-call-crossing reg. */ 200818334Speter || (current_function_has_nonlocal_label 200950397Sobrien && ((REG_N_CALLS_CROSSED (ureg) > 0) 201050397Sobrien != (REG_N_CALLS_CROSSED (sreg) > 0)))) 201118334Speter return 0; 201218334Speter 201318334Speter /* We don't already know about SREG, so tie it to UREG 201418334Speter if this is the last use of UREG, provided the classes they want 201518334Speter are compatible. */ 201618334Speter 201718334Speter if ((already_dead || find_regno_note (insn, REG_DEAD, ureg)) 201890075Sobrien && reg_meets_class_p (sreg, qty[reg_qty[ureg]].min_class)) 201918334Speter { 202018334Speter /* Add SREG to UREG's quantity. */ 202118334Speter sqty = reg_qty[ureg]; 202218334Speter reg_qty[sreg] = sqty; 202318334Speter reg_offset[sreg] = reg_offset[ureg] + offset; 202490075Sobrien reg_next_in_qty[sreg] = qty[sqty].first_reg; 202590075Sobrien qty[sqty].first_reg = sreg; 202618334Speter 202790075Sobrien /* If SREG's reg class is smaller, set qty[SQTY].min_class. */ 202818334Speter update_qty_class (sqty, sreg); 202918334Speter 203018334Speter /* Update info about quantity SQTY. */ 203190075Sobrien qty[sqty].n_calls_crossed += REG_N_CALLS_CROSSED (sreg); 2032161651Skan qty[sqty].n_throwing_calls_crossed 2033161651Skan += REG_N_THROWING_CALLS_CROSSED (sreg); 203490075Sobrien qty[sqty].n_refs += REG_N_REFS (sreg); 203590075Sobrien qty[sqty].freq += REG_FREQ (sreg); 203618334Speter if (usize < ssize) 203718334Speter { 203890075Sobrien int i; 203918334Speter 204090075Sobrien for (i = qty[sqty].first_reg; i >= 0; i = reg_next_in_qty[i]) 204118334Speter reg_offset[i] -= offset; 204218334Speter 204390075Sobrien qty[sqty].size = ssize; 204490075Sobrien qty[sqty].mode = GET_MODE (setreg); 204518334Speter } 204618334Speter } 204718334Speter else 204818334Speter return 0; 204918334Speter 205018334Speter return 1; 205118334Speter} 205218334Speter 205318334Speter/* Return 1 if the preferred class of REG allows it to be tied 205418334Speter to a quantity or register whose class is CLASS. 205518334Speter True if REG's reg class either contains or is contained in CLASS. */ 205618334Speter 205718334Speterstatic int 2058132718Skanreg_meets_class_p (int reg, enum reg_class class) 205918334Speter{ 206090075Sobrien enum reg_class rclass = reg_preferred_class (reg); 206118334Speter return (reg_class_subset_p (rclass, class) 206218334Speter || reg_class_subset_p (class, rclass)); 206318334Speter} 206418334Speter 206590075Sobrien/* Update the class of QTYNO assuming that REG is being tied to it. */ 206618334Speter 206718334Speterstatic void 2068132718Skanupdate_qty_class (int qtyno, int reg) 206918334Speter{ 207018334Speter enum reg_class rclass = reg_preferred_class (reg); 207190075Sobrien if (reg_class_subset_p (rclass, qty[qtyno].min_class)) 207290075Sobrien qty[qtyno].min_class = rclass; 207318334Speter 207418334Speter rclass = reg_alternate_class (reg); 207590075Sobrien if (reg_class_subset_p (rclass, qty[qtyno].alternate_class)) 207690075Sobrien qty[qtyno].alternate_class = rclass; 207718334Speter} 207818334Speter 207918334Speter/* Handle something which alters the value of an rtx REG. 208018334Speter 208118334Speter REG is whatever is set or clobbered. SETTER is the rtx that 208218334Speter is modifying the register. 208318334Speter 208418334Speter If it is not really a register, we do nothing. 208518334Speter The file-global variables `this_insn' and `this_insn_number' 208618334Speter carry info from `block_alloc'. */ 208718334Speter 208818334Speterstatic void 2089132718Skanreg_is_set (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED) 209018334Speter{ 209118334Speter /* Note that note_stores will only pass us a SUBREG if it is a SUBREG of 209218334Speter a hard register. These may actually not exist any more. */ 209318334Speter 209418334Speter if (GET_CODE (reg) != SUBREG 2095169689Skan && !REG_P (reg)) 209618334Speter return; 209718334Speter 209818334Speter /* Mark this register as being born. If it is used in a CLOBBER, mark 209918334Speter it as being born halfway between the previous insn and this insn so that 210018334Speter it conflicts with our inputs but not the outputs of the previous insn. */ 210118334Speter 210218334Speter reg_is_born (reg, 2 * this_insn_number - (GET_CODE (setter) == CLOBBER)); 210318334Speter} 210418334Speter 210518334Speter/* Handle beginning of the life of register REG. 210618334Speter BIRTH is the index at which this is happening. */ 210718334Speter 210818334Speterstatic void 2109132718Skanreg_is_born (rtx reg, int birth) 211018334Speter{ 211190075Sobrien int regno; 211290075Sobrien 211318334Speter if (GET_CODE (reg) == SUBREG) 211490075Sobrien { 211590075Sobrien regno = REGNO (SUBREG_REG (reg)); 211690075Sobrien if (regno < FIRST_PSEUDO_REGISTER) 2117169689Skan regno = subreg_regno (reg); 211890075Sobrien } 211918334Speter else 212018334Speter regno = REGNO (reg); 212118334Speter 212218334Speter if (regno < FIRST_PSEUDO_REGISTER) 212318334Speter { 212418334Speter mark_life (regno, GET_MODE (reg), 1); 212518334Speter 212618334Speter /* If the register was to have been born earlier that the present 212718334Speter insn, mark it as live where it is actually born. */ 212818334Speter if (birth < 2 * this_insn_number) 212918334Speter post_mark_life (regno, GET_MODE (reg), 1, birth, 2 * this_insn_number); 213018334Speter } 213118334Speter else 213218334Speter { 213318334Speter if (reg_qty[regno] == -2) 213418334Speter alloc_qty (regno, GET_MODE (reg), PSEUDO_REGNO_SIZE (regno), birth); 213518334Speter 213618334Speter /* If this register has a quantity number, show that it isn't dead. */ 213718334Speter if (reg_qty[regno] >= 0) 213890075Sobrien qty[reg_qty[regno]].death = -1; 213918334Speter } 214018334Speter} 214118334Speter 2142117395Skan/* Record the death of REG in the current insn. If OUTPUT_P is nonzero, 214318334Speter REG is an output that is dying (i.e., it is never used), otherwise it 214418334Speter is an input (the normal case). 214518334Speter If OUTPUT_P is 1, then we extend the life past the end of this insn. */ 214618334Speter 214718334Speterstatic void 2148132718Skanwipe_dead_reg (rtx reg, int output_p) 214918334Speter{ 215090075Sobrien int regno = REGNO (reg); 215118334Speter 215218334Speter /* If this insn has multiple results, 215318334Speter and the dead reg is used in one of the results, 215418334Speter extend its life to after this insn, 215590075Sobrien so it won't get allocated together with any other result of this insn. 215652284Sobrien 215752284Sobrien It is unsafe to use !single_set here since it will ignore an unused 215852284Sobrien output. Just because an output is unused does not mean the compiler 215952284Sobrien can assume the side effect will not occur. Consider if REG appears 216052284Sobrien in the address of an output and we reload the output. If we allocate 216152284Sobrien REG to the same hard register as an unused output we could set the hard 216252284Sobrien register before the output reload insn. */ 216318334Speter if (GET_CODE (PATTERN (this_insn)) == PARALLEL 216452284Sobrien && multiple_sets (this_insn)) 216518334Speter { 216618334Speter int i; 216718334Speter for (i = XVECLEN (PATTERN (this_insn), 0) - 1; i >= 0; i--) 216818334Speter { 216918334Speter rtx set = XVECEXP (PATTERN (this_insn), 0, i); 217018334Speter if (GET_CODE (set) == SET 2171169689Skan && !REG_P (SET_DEST (set)) 217218334Speter && !rtx_equal_p (reg, SET_DEST (set)) 217318334Speter && reg_overlap_mentioned_p (reg, SET_DEST (set))) 217418334Speter output_p = 1; 217518334Speter } 217618334Speter } 217718334Speter 217818334Speter /* If this register is used in an auto-increment address, then extend its 217918334Speter life to after this insn, so that it won't get allocated together with 218018334Speter the result of this insn. */ 218118334Speter if (! output_p && find_regno_note (this_insn, REG_INC, regno)) 218218334Speter output_p = 1; 218318334Speter 218418334Speter if (regno < FIRST_PSEUDO_REGISTER) 218518334Speter { 218618334Speter mark_life (regno, GET_MODE (reg), 0); 218718334Speter 218818334Speter /* If a hard register is dying as an output, mark it as in use at 218918334Speter the beginning of this insn (the above statement would cause this 219018334Speter not to happen). */ 219118334Speter if (output_p) 219218334Speter post_mark_life (regno, GET_MODE (reg), 1, 219390075Sobrien 2 * this_insn_number, 2 * this_insn_number + 1); 219418334Speter } 219518334Speter 219618334Speter else if (reg_qty[regno] >= 0) 219790075Sobrien qty[reg_qty[regno]].death = 2 * this_insn_number + output_p; 219818334Speter} 219918334Speter 220018334Speter/* Find a block of SIZE words of hard regs in reg_class CLASS 220118334Speter that can hold something of machine-mode MODE 220218334Speter (but actually we test only the first of the block for holding MODE) 220318334Speter and still free between insn BORN_INDEX and insn DEAD_INDEX, 220418334Speter and return the number of the first of them. 220590075Sobrien Return -1 if such a block cannot be found. 220690075Sobrien If QTYNO crosses calls, insist on a register preserved by calls, 220718334Speter unless ACCEPT_CALL_CLOBBERED is nonzero. 220818334Speter 2209117395Skan If JUST_TRY_SUGGESTED is nonzero, only try to see if the suggested 221018334Speter register is available. If not, return -1. */ 221118334Speter 221218334Speterstatic int 2213132718Skanfind_free_reg (enum reg_class class, enum machine_mode mode, int qtyno, 2214132718Skan int accept_call_clobbered, int just_try_suggested, 2215132718Skan int born_index, int dead_index) 221618334Speter{ 221790075Sobrien int i, ins; 2218117395Skan HARD_REG_SET first_used, used; 221918334Speter#ifdef ELIMINABLE_REGS 222090075Sobrien static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS; 222118334Speter#endif 222218334Speter 222318334Speter /* Validate our parameters. */ 2224169689Skan gcc_assert (born_index >= 0 && born_index <= dead_index); 222518334Speter 222618334Speter /* Don't let a pseudo live in a reg across a function call 222718334Speter if we might get a nonlocal goto. */ 222818334Speter if (current_function_has_nonlocal_label 222990075Sobrien && qty[qtyno].n_calls_crossed > 0) 223018334Speter return -1; 223118334Speter 223218334Speter if (accept_call_clobbered) 223318334Speter COPY_HARD_REG_SET (used, call_fixed_reg_set); 223490075Sobrien else if (qty[qtyno].n_calls_crossed == 0) 223518334Speter COPY_HARD_REG_SET (used, fixed_reg_set); 223618334Speter else 223718334Speter COPY_HARD_REG_SET (used, call_used_reg_set); 223818334Speter 223950397Sobrien if (accept_call_clobbered) 224050397Sobrien IOR_HARD_REG_SET (used, losing_caller_save_reg_set); 224150397Sobrien 224218334Speter for (ins = born_index; ins < dead_index; ins++) 224318334Speter IOR_HARD_REG_SET (used, regs_live_at[ins]); 224418334Speter 224518334Speter IOR_COMPL_HARD_REG_SET (used, reg_class_contents[(int) class]); 224618334Speter 224718334Speter /* Don't use the frame pointer reg in local-alloc even if 224818334Speter we may omit the frame pointer, because if we do that and then we 224918334Speter need a frame pointer, reload won't know how to move the pseudo 225018334Speter to another hard reg. It can move only regs made by global-alloc. 225118334Speter 225218334Speter This is true of any register that can be eliminated. */ 225318334Speter#ifdef ELIMINABLE_REGS 225490075Sobrien for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++) 225518334Speter SET_HARD_REG_BIT (used, eliminables[i].from); 225618334Speter#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 225718334Speter /* If FRAME_POINTER_REGNUM is not a real register, then protect the one 225850397Sobrien that it might be eliminated into. */ 225918334Speter SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM); 226018334Speter#endif 226118334Speter#else 226218334Speter SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM); 226318334Speter#endif 226418334Speter 2265117395Skan#ifdef CANNOT_CHANGE_MODE_CLASS 2266117395Skan cannot_change_mode_set_regs (&used, mode, qty[qtyno].first_reg); 226718334Speter#endif 226818334Speter 226918334Speter /* Normally, the registers that can be used for the first register in 227018334Speter a multi-register quantity are the same as those that can be used for 227118334Speter subsequent registers. However, if just trying suggested registers, 227218334Speter restrict our consideration to them. If there are copy-suggested 227318334Speter register, try them. Otherwise, try the arithmetic-suggested 227418334Speter registers. */ 227518334Speter COPY_HARD_REG_SET (first_used, used); 227618334Speter 227718334Speter if (just_try_suggested) 227818334Speter { 227990075Sobrien if (qty_phys_num_copy_sugg[qtyno] != 0) 228090075Sobrien IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qtyno]); 228118334Speter else 228290075Sobrien IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qtyno]); 228318334Speter } 228418334Speter 228518334Speter /* If all registers are excluded, we can't do anything. */ 228618334Speter GO_IF_HARD_REG_SUBSET (reg_class_contents[(int) ALL_REGS], first_used, fail); 228718334Speter 228818334Speter /* If at least one would be suitable, test each hard reg. */ 228918334Speter 229018334Speter for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 229118334Speter { 229218334Speter#ifdef REG_ALLOC_ORDER 229318334Speter int regno = reg_alloc_order[i]; 229418334Speter#else 229518334Speter int regno = i; 229618334Speter#endif 229718334Speter if (! TEST_HARD_REG_BIT (first_used, regno) 229852284Sobrien && HARD_REGNO_MODE_OK (regno, mode) 229990075Sobrien && (qty[qtyno].n_calls_crossed == 0 230052284Sobrien || accept_call_clobbered 230152284Sobrien || ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))) 230218334Speter { 230390075Sobrien int j; 2304169689Skan int size1 = hard_regno_nregs[regno][mode]; 230518334Speter for (j = 1; j < size1 && ! TEST_HARD_REG_BIT (used, regno + j); j++); 230618334Speter if (j == size1) 230718334Speter { 230818334Speter /* Mark that this register is in use between its birth and death 230918334Speter insns. */ 231018334Speter post_mark_life (regno, mode, 1, born_index, dead_index); 231118334Speter return regno; 231218334Speter } 231318334Speter#ifndef REG_ALLOC_ORDER 231490075Sobrien /* Skip starting points we know will lose. */ 231590075Sobrien i += j; 231618334Speter#endif 231718334Speter } 231818334Speter } 231918334Speter 232018334Speter fail: 232118334Speter /* If we are just trying suggested register, we have just tried copy- 232218334Speter suggested registers, and there are arithmetic-suggested registers, 232318334Speter try them. */ 232490075Sobrien 232518334Speter /* If it would be profitable to allocate a call-clobbered register 232618334Speter and save and restore it around calls, do that. */ 232790075Sobrien if (just_try_suggested && qty_phys_num_copy_sugg[qtyno] != 0 232890075Sobrien && qty_phys_num_sugg[qtyno] != 0) 232918334Speter { 233018334Speter /* Don't try the copy-suggested regs again. */ 233190075Sobrien qty_phys_num_copy_sugg[qtyno] = 0; 233290075Sobrien return find_free_reg (class, mode, qtyno, accept_call_clobbered, 1, 233318334Speter born_index, dead_index); 233418334Speter } 233518334Speter 233618334Speter /* We need not check to see if the current function has nonlocal 233718334Speter labels because we don't put any pseudos that are live over calls in 2338161651Skan registers in that case. Avoid putting pseudos crossing calls that 2339161651Skan might throw into call used registers. */ 234018334Speter 234118334Speter if (! accept_call_clobbered 234218334Speter && flag_caller_saves 234318334Speter && ! just_try_suggested 234490075Sobrien && qty[qtyno].n_calls_crossed != 0 2345161651Skan && qty[qtyno].n_throwing_calls_crossed == 0 234690075Sobrien && CALLER_SAVE_PROFITABLE (qty[qtyno].n_refs, 234790075Sobrien qty[qtyno].n_calls_crossed)) 234818334Speter { 234990075Sobrien i = find_free_reg (class, mode, qtyno, 1, 0, born_index, dead_index); 235018334Speter if (i >= 0) 235118334Speter caller_save_needed = 1; 235218334Speter return i; 235318334Speter } 235418334Speter return -1; 235518334Speter} 235618334Speter 235718334Speter/* Mark that REGNO with machine-mode MODE is live starting from the current 2358117395Skan insn (if LIFE is nonzero) or dead starting at the current insn (if LIFE 235918334Speter is zero). */ 236018334Speter 236118334Speterstatic void 2362132718Skanmark_life (int regno, enum machine_mode mode, int life) 236318334Speter{ 2364169689Skan int j = hard_regno_nregs[regno][mode]; 236518334Speter if (life) 236618334Speter while (--j >= 0) 236718334Speter SET_HARD_REG_BIT (regs_live, regno + j); 236818334Speter else 236918334Speter while (--j >= 0) 237018334Speter CLEAR_HARD_REG_BIT (regs_live, regno + j); 237118334Speter} 237218334Speter 237318334Speter/* Mark register number REGNO (with machine-mode MODE) as live (if LIFE 2374117395Skan is nonzero) or dead (if LIFE is zero) from insn number BIRTH (inclusive) 237518334Speter to insn number DEATH (exclusive). */ 237618334Speter 237718334Speterstatic void 2378132718Skanpost_mark_life (int regno, enum machine_mode mode, int life, int birth, 2379132718Skan int death) 238018334Speter{ 2381169689Skan int j = hard_regno_nregs[regno][mode]; 2382132718Skan HARD_REG_SET this_reg; 238318334Speter 238418334Speter CLEAR_HARD_REG_SET (this_reg); 238518334Speter while (--j >= 0) 238618334Speter SET_HARD_REG_BIT (this_reg, regno + j); 238718334Speter 238818334Speter if (life) 238918334Speter while (birth < death) 239018334Speter { 239118334Speter IOR_HARD_REG_SET (regs_live_at[birth], this_reg); 239218334Speter birth++; 239318334Speter } 239418334Speter else 239518334Speter while (birth < death) 239618334Speter { 239718334Speter AND_COMPL_HARD_REG_SET (regs_live_at[birth], this_reg); 239818334Speter birth++; 239918334Speter } 240018334Speter} 240118334Speter 240218334Speter/* INSN is the CLOBBER insn that starts a REG_NO_NOCONFLICT block, R0 240318334Speter is the register being clobbered, and R1 is a register being used in 240418334Speter the equivalent expression. 240518334Speter 240618334Speter If R1 dies in the block and has a REG_NO_CONFLICT note on every insn 240718334Speter in which it is used, return 1. 240818334Speter 240918334Speter Otherwise, return 0. */ 241018334Speter 241118334Speterstatic int 2412132718Skanno_conflict_p (rtx insn, rtx r0 ATTRIBUTE_UNUSED, rtx r1) 241318334Speter{ 241418334Speter int ok = 0; 241518334Speter rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX); 241618334Speter rtx p, last; 241718334Speter 241818334Speter /* If R1 is a hard register, return 0 since we handle this case 241918334Speter when we scan the insns that actually use it. */ 242018334Speter 242118334Speter if (note == 0 2422169689Skan || (REG_P (r1) && REGNO (r1) < FIRST_PSEUDO_REGISTER) 2423169689Skan || (GET_CODE (r1) == SUBREG && REG_P (SUBREG_REG (r1)) 242418334Speter && REGNO (SUBREG_REG (r1)) < FIRST_PSEUDO_REGISTER)) 242518334Speter return 0; 242618334Speter 242718334Speter last = XEXP (note, 0); 242818334Speter 242918334Speter for (p = NEXT_INSN (insn); p && p != last; p = NEXT_INSN (p)) 243090075Sobrien if (INSN_P (p)) 243118334Speter { 243218334Speter if (find_reg_note (p, REG_DEAD, r1)) 243318334Speter ok = 1; 243418334Speter 243550397Sobrien /* There must be a REG_NO_CONFLICT note on every insn, otherwise 243650397Sobrien some earlier optimization pass has inserted instructions into 243750397Sobrien the sequence, and it is not safe to perform this optimization. 243850397Sobrien Note that emit_no_conflict_block always ensures that this is 243950397Sobrien true when these sequences are created. */ 244050397Sobrien if (! find_reg_note (p, REG_NO_CONFLICT, r1)) 244118334Speter return 0; 244218334Speter } 244390075Sobrien 244418334Speter return ok; 244518334Speter} 244618334Speter 244718334Speter/* Return the number of alternatives for which the constraint string P 244818334Speter indicates that the operand must be equal to operand 0 and that no register 244918334Speter is acceptable. */ 245018334Speter 245118334Speterstatic int 2452132718Skanrequires_inout (const char *p) 245318334Speter{ 245418334Speter char c; 245518334Speter int found_zero = 0; 245618334Speter int reg_allowed = 0; 245718334Speter int num_matching_alts = 0; 2458132718Skan int len; 245918334Speter 2460132718Skan for ( ; (c = *p); p += len) 2461132718Skan { 2462132718Skan len = CONSTRAINT_LEN (c, p); 2463132718Skan switch (c) 2464132718Skan { 2465132718Skan case '=': case '+': case '?': 2466132718Skan case '#': case '&': case '!': 2467132718Skan case '*': case '%': 2468132718Skan case 'm': case '<': case '>': case 'V': case 'o': 2469132718Skan case 'E': case 'F': case 'G': case 'H': 2470132718Skan case 's': case 'i': case 'n': 2471132718Skan case 'I': case 'J': case 'K': case 'L': 2472132718Skan case 'M': case 'N': case 'O': case 'P': 2473132718Skan case 'X': 2474132718Skan /* These don't say anything we care about. */ 2475132718Skan break; 247618334Speter 2477132718Skan case ',': 2478132718Skan if (found_zero && ! reg_allowed) 2479132718Skan num_matching_alts++; 248018334Speter 2481132718Skan found_zero = reg_allowed = 0; 2482132718Skan break; 248318334Speter 2484132718Skan case '0': 2485132718Skan found_zero = 1; 2486132718Skan break; 248718334Speter 2488132718Skan case '1': case '2': case '3': case '4': case '5': 2489132718Skan case '6': case '7': case '8': case '9': 2490132718Skan /* Skip the balance of the matching constraint. */ 2491132718Skan do 2492132718Skan p++; 2493132718Skan while (ISDIGIT (*p)); 2494132718Skan len = 0; 2495132718Skan break; 249690075Sobrien 2497132718Skan default: 2498132718Skan if (REG_CLASS_FROM_CONSTRAINT (c, p) == NO_REGS 2499132718Skan && !EXTRA_ADDRESS_CONSTRAINT (c, p)) 2500132718Skan break; 2501132718Skan /* Fall through. */ 2502132718Skan case 'p': 2503132718Skan case 'g': case 'r': 2504132718Skan reg_allowed = 1; 250590075Sobrien break; 2506132718Skan } 2507132718Skan } 250818334Speter 250918334Speter if (found_zero && ! reg_allowed) 251018334Speter num_matching_alts++; 251118334Speter 251218334Speter return num_matching_alts; 251318334Speter} 251418334Speter 251518334Spetervoid 2516132718Skandump_local_alloc (FILE *file) 251718334Speter{ 251890075Sobrien int i; 251918334Speter for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++) 252018334Speter if (reg_renumber[i] != -1) 252118334Speter fprintf (file, ";; Register %d in %d.\n", i, reg_renumber[i]); 252218334Speter} 2523169689Skan 2524169689Skan/* Run old register allocator. Return TRUE if we must exit 2525169689Skan rest_of_compilation upon return. */ 2526169689Skanstatic unsigned int 2527169689Skanrest_of_handle_local_alloc (void) 2528169689Skan{ 2529169689Skan int rebuild_notes; 2530169689Skan 2531169689Skan /* Determine if the current function is a leaf before running reload 2532169689Skan since this can impact optimizations done by the prologue and 2533169689Skan epilogue thus changing register elimination offsets. */ 2534169689Skan current_function_is_leaf = leaf_function_p (); 2535169689Skan 2536169689Skan /* Allocate the reg_renumber array. */ 2537169689Skan allocate_reg_info (max_regno, FALSE, TRUE); 2538169689Skan 2539169689Skan /* And the reg_equiv_memory_loc array. */ 2540169689Skan VEC_safe_grow (rtx, gc, reg_equiv_memory_loc_vec, max_regno); 2541169689Skan memset (VEC_address (rtx, reg_equiv_memory_loc_vec), 0, 2542169689Skan sizeof (rtx) * max_regno); 2543169689Skan reg_equiv_memory_loc = VEC_address (rtx, reg_equiv_memory_loc_vec); 2544169689Skan 2545169689Skan allocate_initial_values (reg_equiv_memory_loc); 2546169689Skan 2547169689Skan regclass (get_insns (), max_reg_num ()); 2548169689Skan rebuild_notes = local_alloc (); 2549169689Skan 2550169689Skan /* Local allocation may have turned an indirect jump into a direct 2551169689Skan jump. If so, we must rebuild the JUMP_LABEL fields of jumping 2552169689Skan instructions. */ 2553169689Skan if (rebuild_notes) 2554169689Skan { 2555169689Skan timevar_push (TV_JUMP); 2556169689Skan 2557169689Skan rebuild_jump_labels (get_insns ()); 2558169689Skan purge_all_dead_edges (); 2559169689Skan delete_unreachable_blocks (); 2560169689Skan 2561169689Skan timevar_pop (TV_JUMP); 2562169689Skan } 2563169689Skan 2564169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2565169689Skan { 2566169689Skan timevar_push (TV_DUMP); 2567169689Skan dump_flow_info (dump_file, dump_flags); 2568169689Skan dump_local_alloc (dump_file); 2569169689Skan timevar_pop (TV_DUMP); 2570169689Skan } 2571169689Skan return 0; 2572169689Skan} 2573169689Skan 2574169689Skanstruct tree_opt_pass pass_local_alloc = 2575169689Skan{ 2576169689Skan "lreg", /* name */ 2577169689Skan NULL, /* gate */ 2578169689Skan rest_of_handle_local_alloc, /* execute */ 2579169689Skan NULL, /* sub */ 2580169689Skan NULL, /* next */ 2581169689Skan 0, /* static_pass_number */ 2582169689Skan TV_LOCAL_ALLOC, /* tv_id */ 2583169689Skan 0, /* properties_required */ 2584169689Skan 0, /* properties_provided */ 2585169689Skan 0, /* properties_destroyed */ 2586169689Skan 0, /* todo_flags_start */ 2587169689Skan TODO_dump_func | 2588169689Skan TODO_ggc_collect, /* todo_flags_finish */ 2589169689Skan 'l' /* letter */ 2590169689Skan}; 2591169689Skan 2592