150397Sobrien/* Instruction scheduling pass. 2169689Skan Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 3169689Skan 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 450397Sobrien Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, 550397Sobrien and currently maintained by, Jim Wilson (wilson@cygnus.com) 650397Sobrien 790075SobrienThis file is part of GCC. 850397Sobrien 990075SobrienGCC is free software; you can redistribute it and/or modify it under 1090075Sobrienthe terms of the GNU General Public License as published by the Free 1190075SobrienSoftware Foundation; either version 2, or (at your option) any later 1290075Sobrienversion. 1350397Sobrien 1490075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1590075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1690075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1790075Sobrienfor more details. 1850397Sobrien 1990075SobrienYou should have received a copy of the GNU General Public License 2090075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 21169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 22169689Skan02110-1301, USA. */ 2350397Sobrien 2490075Sobrien/* Instruction scheduling pass. This file, along with sched-deps.c, 2590075Sobrien contains the generic parts. The actual entry point is found for 2690075Sobrien the normal instruction scheduling pass is found in sched-rgn.c. 2750397Sobrien 2850397Sobrien We compute insn priorities based on data dependencies. Flow 2950397Sobrien analysis only creates a fraction of the data-dependencies we must 3050397Sobrien observe: namely, only those dependencies which the combiner can be 3150397Sobrien expected to use. For this pass, we must therefore create the 3250397Sobrien remaining dependencies we need to observe: register dependencies, 3350397Sobrien memory dependencies, dependencies to keep function calls in order, 3450397Sobrien and the dependence between a conditional branch and the setting of 3550397Sobrien condition codes are all dealt with here. 3650397Sobrien 3750397Sobrien The scheduler first traverses the data flow graph, starting with 3850397Sobrien the last instruction, and proceeding to the first, assigning values 3950397Sobrien to insn_priority as it goes. This sorts the instructions 4050397Sobrien topologically by data dependence. 4150397Sobrien 4250397Sobrien Once priorities have been established, we order the insns using 4350397Sobrien list scheduling. This works as follows: starting with a list of 4450397Sobrien all the ready insns, and sorted according to priority number, we 4550397Sobrien schedule the insn from the end of the list by placing its 4650397Sobrien predecessors in the list according to their priority order. We 4750397Sobrien consider this insn scheduled by setting the pointer to the "end" of 4850397Sobrien the list to point to the previous insn. When an insn has no 4950397Sobrien predecessors, we either queue it until sufficient time has elapsed 5050397Sobrien or add it to the ready list. As the instructions are scheduled or 5150397Sobrien when stalls are introduced, the queue advances and dumps insns into 5250397Sobrien the ready list. When all insns down to the lowest priority have 5350397Sobrien been scheduled, the critical path of the basic block has been made 5450397Sobrien as short as possible. The remaining insns are then scheduled in 5550397Sobrien remaining slots. 5650397Sobrien 5750397Sobrien The following list shows the order in which we want to break ties 5850397Sobrien among insns in the ready list: 5950397Sobrien 6050397Sobrien 1. choose insn with the longest path to end of bb, ties 6150397Sobrien broken by 6250397Sobrien 2. choose insn with least contribution to register pressure, 6350397Sobrien ties broken by 6450397Sobrien 3. prefer in-block upon interblock motion, ties broken by 6550397Sobrien 4. prefer useful upon speculative motion, ties broken by 6650397Sobrien 5. choose insn with largest control flow probability, ties 6750397Sobrien broken by 6850397Sobrien 6. choose insn with the least dependences upon the previously 6950397Sobrien scheduled insn, or finally 7050397Sobrien 7 choose the insn which has the most insns dependent on it. 7150397Sobrien 8. choose insn with lowest UID. 7250397Sobrien 7350397Sobrien Memory references complicate matters. Only if we can be certain 7450397Sobrien that memory references are not part of the data dependency graph 7550397Sobrien (via true, anti, or output dependence), can we move operations past 7650397Sobrien memory references. To first approximation, reads can be done 7750397Sobrien independently, while writes introduce dependencies. Better 7850397Sobrien approximations will yield fewer dependencies. 7950397Sobrien 8050397Sobrien Before reload, an extended analysis of interblock data dependences 8150397Sobrien is required for interblock scheduling. This is performed in 8250397Sobrien compute_block_backward_dependences (). 8350397Sobrien 8450397Sobrien Dependencies set up by memory references are treated in exactly the 8550397Sobrien same way as other dependencies, by using LOG_LINKS backward 8650397Sobrien dependences. LOG_LINKS are translated into INSN_DEPEND forward 8750397Sobrien dependences for the purpose of forward list scheduling. 8850397Sobrien 8950397Sobrien Having optimized the critical path, we may have also unduly 9050397Sobrien extended the lifetimes of some registers. If an operation requires 9150397Sobrien that constants be loaded into registers, it is certainly desirable 9250397Sobrien to load those constants as early as necessary, but no earlier. 9350397Sobrien I.e., it will not do to load up a bunch of registers at the 9450397Sobrien beginning of a basic block only to use them at the end, if they 9550397Sobrien could be loaded later, since this may result in excessive register 9650397Sobrien utilization. 9750397Sobrien 9850397Sobrien Note that since branches are never in basic blocks, but only end 9950397Sobrien basic blocks, this pass will not move branches. But that is ok, 10050397Sobrien since we can use GNU's delayed branch scheduling pass to take care 10150397Sobrien of this case. 10250397Sobrien 10350397Sobrien Also note that no further optimizations based on algebraic 10450397Sobrien identities are performed, so this pass would be a good one to 10550397Sobrien perform instruction splitting, such as breaking up a multiply 10650397Sobrien instruction into shifts and adds where that is profitable. 10750397Sobrien 10850397Sobrien Given the memory aliasing analysis that this pass should perform, 10950397Sobrien it should be possible to remove redundant stores to memory, and to 11050397Sobrien load values from registers instead of hitting memory. 11150397Sobrien 11250397Sobrien Before reload, speculative insns are moved only if a 'proof' exists 11350397Sobrien that no exception will be caused by this, and if no live registers 11450397Sobrien exist that inhibit the motion (live registers constraints are not 11550397Sobrien represented by data dependence edges). 11650397Sobrien 11750397Sobrien This pass must update information that subsequent passes expect to 11850397Sobrien be correct. Namely: reg_n_refs, reg_n_sets, reg_n_deaths, 119132718Skan reg_n_calls_crossed, and reg_live_length. Also, BB_HEAD, BB_END. 12050397Sobrien 12150397Sobrien The information in the line number notes is carefully retained by 12250397Sobrien this pass. Notes that refer to the starting and ending of 12350397Sobrien exception regions are also carefully retained by this pass. All 12450397Sobrien other NOTE insns are grouped in their same relative order at the 12590075Sobrien beginning of basic blocks and regions that have been scheduled. */ 12650397Sobrien 12750397Sobrien#include "config.h" 12850397Sobrien#include "system.h" 129132718Skan#include "coretypes.h" 130132718Skan#include "tm.h" 13152284Sobrien#include "toplev.h" 13250397Sobrien#include "rtl.h" 13390075Sobrien#include "tm_p.h" 13490075Sobrien#include "hard-reg-set.h" 13550397Sobrien#include "regs.h" 13690075Sobrien#include "function.h" 13750397Sobrien#include "flags.h" 13850397Sobrien#include "insn-config.h" 13950397Sobrien#include "insn-attr.h" 14050397Sobrien#include "except.h" 14150397Sobrien#include "toplev.h" 14252284Sobrien#include "recog.h" 14390075Sobrien#include "sched-int.h" 14490075Sobrien#include "target.h" 145169689Skan#include "output.h" 146169689Skan#include "params.h" 14750397Sobrien 14850397Sobrien#ifdef INSN_SCHEDULING 14950397Sobrien 15050397Sobrien/* issue_rate is the number of insns that can be scheduled in the same 15150397Sobrien machine cycle. It can be defined in the config/mach/mach.h file, 15250397Sobrien otherwise we set it to 1. */ 15350397Sobrien 15450397Sobrienstatic int issue_rate; 15550397Sobrien 15650397Sobrien/* sched-verbose controls the amount of debugging output the 15790075Sobrien scheduler prints. It is controlled by -fsched-verbose=N: 15850397Sobrien N>0 and no -DSR : the output is directed to stderr. 15950397Sobrien N>=10 will direct the printouts to stderr (regardless of -dSR). 16050397Sobrien N=1: same as -dSR. 16150397Sobrien N=2: bb's probabilities, detailed ready list info, unit/insn info. 16250397Sobrien N=3: rtl at abort point, control-flow, regions info. 16350397Sobrien N=5: dependences info. */ 16450397Sobrien 16550397Sobrienstatic int sched_verbose_param = 0; 16690075Sobrienint sched_verbose = 0; 16750397Sobrien 16890075Sobrien/* Debugging file. All printouts are sent to dump, which is always set, 16990075Sobrien either to stderr, or to the dump listing file (-dRS). */ 17090075SobrienFILE *sched_dump = 0; 17150397Sobrien 17290075Sobrien/* Highest uid before scheduling. */ 17390075Sobrienstatic int old_max_uid; 17450397Sobrien 17550397Sobrien/* fix_sched_param() is called from toplev.c upon detection 17690075Sobrien of the -fsched-verbose=N option. */ 17750397Sobrien 17850397Sobrienvoid 179132718Skanfix_sched_param (const char *param, const char *val) 18050397Sobrien{ 18150397Sobrien if (!strcmp (param, "verbose")) 18250397Sobrien sched_verbose_param = atoi (val); 18350397Sobrien else 184169689Skan warning (0, "fix_sched_param: unknown param: %s", param); 18550397Sobrien} 18650397Sobrien 18790075Sobrienstruct haifa_insn_data *h_i_d; 18850397Sobrien 18990075Sobrien#define LINE_NOTE(INSN) (h_i_d[INSN_UID (INSN)].line_note) 19090075Sobrien#define INSN_TICK(INSN) (h_i_d[INSN_UID (INSN)].tick) 191169689Skan#define INTER_TICK(INSN) (h_i_d[INSN_UID (INSN)].inter_tick) 19250397Sobrien 193169689Skan/* If INSN_TICK of an instruction is equal to INVALID_TICK, 194169689Skan then it should be recalculated from scratch. */ 195169689Skan#define INVALID_TICK (-(max_insn_queue_index + 1)) 196169689Skan/* The minimal value of the INSN_TICK of an instruction. */ 197169689Skan#define MIN_TICK (-max_insn_queue_index) 198169689Skan 199169689Skan/* Issue points are used to distinguish between instructions in max_issue (). 200169689Skan For now, all instructions are equally good. */ 201169689Skan#define ISSUE_POINTS(INSN) 1 202169689Skan 20350397Sobrien/* Vector indexed by basic block number giving the starting line-number 20450397Sobrien for each basic block. */ 20550397Sobrienstatic rtx *line_note_head; 20650397Sobrien 20750397Sobrien/* List of important notes we must keep around. This is a pointer to the 20850397Sobrien last element in the list. */ 20950397Sobrienstatic rtx note_list; 21050397Sobrien 211169689Skanstatic struct spec_info_def spec_info_var; 212169689Skan/* Description of the speculative part of the scheduling. 213169689Skan If NULL - no speculation. */ 214169689Skanstatic spec_info_t spec_info; 215169689Skan 216169689Skan/* True, if recovery block was added during scheduling of current block. 217169689Skan Used to determine, if we need to fix INSN_TICKs. */ 218169689Skanstatic bool added_recovery_block_p; 219169689Skan 220169689Skan/* Counters of different types of speculative instructions. */ 221169689Skanstatic int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control; 222169689Skan 223169689Skan/* Pointers to GLAT data. See init_glat for more information. */ 224169689Skanregset *glat_start, *glat_end; 225169689Skan 226169689Skan/* Array used in {unlink, restore}_bb_notes. */ 227169689Skanstatic rtx *bb_header = 0; 228169689Skan 229169689Skan/* Number of basic_blocks. */ 230169689Skanstatic int old_last_basic_block; 231169689Skan 232169689Skan/* Basic block after which recovery blocks will be created. */ 233169689Skanstatic basic_block before_recovery; 234169689Skan 23550397Sobrien/* Queues, etc. */ 23650397Sobrien 23750397Sobrien/* An instruction is ready to be scheduled when all insns preceding it 23850397Sobrien have already been scheduled. It is important to ensure that all 23950397Sobrien insns which use its result will not be executed until its result 24050397Sobrien has been computed. An insn is maintained in one of four structures: 24150397Sobrien 24250397Sobrien (P) the "Pending" set of insns which cannot be scheduled until 24350397Sobrien their dependencies have been satisfied. 24450397Sobrien (Q) the "Queued" set of insns that can be scheduled when sufficient 24550397Sobrien time has passed. 24650397Sobrien (R) the "Ready" list of unscheduled, uncommitted insns. 24750397Sobrien (S) the "Scheduled" list of insns. 24850397Sobrien 24950397Sobrien Initially, all insns are either "Pending" or "Ready" depending on 25050397Sobrien whether their dependencies are satisfied. 25150397Sobrien 25250397Sobrien Insns move from the "Ready" list to the "Scheduled" list as they 25350397Sobrien are committed to the schedule. As this occurs, the insns in the 25450397Sobrien "Pending" list have their dependencies satisfied and move to either 25550397Sobrien the "Ready" list or the "Queued" set depending on whether 25650397Sobrien sufficient time has passed to make them ready. As time passes, 257169689Skan insns move from the "Queued" set to the "Ready" list. 25850397Sobrien 25950397Sobrien The "Pending" list (P) are the insns in the INSN_DEPEND of the unscheduled 26050397Sobrien insns, i.e., those that are ready, queued, and pending. 26150397Sobrien The "Queued" set (Q) is implemented by the variable `insn_queue'. 26250397Sobrien The "Ready" list (R) is implemented by the variables `ready' and 26350397Sobrien `n_ready'. 26450397Sobrien The "Scheduled" list (S) is the new insn chain built by this pass. 26550397Sobrien 26650397Sobrien The transition (R->S) is implemented in the scheduling loop in 26750397Sobrien `schedule_block' when the best insn to schedule is chosen. 26850397Sobrien The transitions (P->R and P->Q) are implemented in `schedule_insn' as 26950397Sobrien insns move from the ready list to the scheduled list. 27050397Sobrien The transition (Q->R) is implemented in 'queue_to_insn' as time 27150397Sobrien passes or stalls are introduced. */ 27250397Sobrien 27350397Sobrien/* Implement a circular buffer to delay instructions until sufficient 274169689Skan time has passed. For the new pipeline description interface, 275169689Skan MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less 276169689Skan than maximal time of instruction execution computed by genattr.c on 277169689Skan the base maximal time of functional unit reservations and getting a 278169689Skan result. This is the longest time an insn may be queued. */ 279117395Skan 280117395Skanstatic rtx *insn_queue; 28150397Sobrienstatic int q_ptr = 0; 28250397Sobrienstatic int q_size = 0; 283169689Skan#define NEXT_Q(X) (((X)+1) & max_insn_queue_index) 284169689Skan#define NEXT_Q_AFTER(X, C) (((X)+C) & max_insn_queue_index) 28550397Sobrien 286169689Skan#define QUEUE_SCHEDULED (-3) 287169689Skan#define QUEUE_NOWHERE (-2) 288169689Skan#define QUEUE_READY (-1) 289169689Skan/* QUEUE_SCHEDULED - INSN is scheduled. 290169689Skan QUEUE_NOWHERE - INSN isn't scheduled yet and is neither in 291169689Skan queue or ready list. 292169689Skan QUEUE_READY - INSN is in ready list. 293169689Skan N >= 0 - INSN queued for X [where NEXT_Q_AFTER (q_ptr, X) == N] cycles. */ 294169689Skan 295169689Skan#define QUEUE_INDEX(INSN) (h_i_d[INSN_UID (INSN)].queue_index) 296117395Skan 297117395Skan/* The following variable value refers for all current and future 298117395Skan reservations of the processor units. */ 299117395Skanstate_t curr_state; 300117395Skan 301117395Skan/* The following variable value is size of memory representing all 302169689Skan current and future reservations of the processor units. */ 303117395Skanstatic size_t dfa_state_size; 304117395Skan 305117395Skan/* The following array is used to find the best insn from ready when 306117395Skan the automaton pipeline interface is used. */ 307117395Skanstatic char *ready_try; 308117395Skan 30990075Sobrien/* Describe the ready list of the scheduler. 31090075Sobrien VEC holds space enough for all insns in the current region. VECLEN 31190075Sobrien says how many exactly. 31290075Sobrien FIRST is the index of the element with the highest priority; i.e. the 31390075Sobrien last one in the ready list, since elements are ordered by ascending 31490075Sobrien priority. 31590075Sobrien N_READY determines how many insns are on the ready list. */ 31650397Sobrien 31790075Sobrienstruct ready_list 31890075Sobrien{ 31990075Sobrien rtx *vec; 32090075Sobrien int veclen; 32190075Sobrien int first; 32290075Sobrien int n_ready; 32390075Sobrien}; 32450397Sobrien 325169689Skan/* The pointer to the ready list. */ 326169689Skanstatic struct ready_list *readyp; 327169689Skan 328169689Skan/* Scheduling clock. */ 329169689Skanstatic int clock_var; 330169689Skan 331169689Skan/* Number of instructions in current scheduling region. */ 332169689Skanstatic int rgn_n_insns; 333169689Skan 334132718Skanstatic int may_trap_exp (rtx, int); 335132718Skan 336132718Skan/* Nonzero iff the address is comprised from at most 1 register. */ 337132718Skan#define CONST_BASED_ADDRESS_P(x) \ 338169689Skan (REG_P (x) \ 339132718Skan || ((GET_CODE (x) == PLUS || GET_CODE (x) == MINUS \ 340132718Skan || (GET_CODE (x) == LO_SUM)) \ 341132718Skan && (CONSTANT_P (XEXP (x, 0)) \ 342132718Skan || CONSTANT_P (XEXP (x, 1))))) 343132718Skan 344132718Skan/* Returns a class that insn with GET_DEST(insn)=x may belong to, 345132718Skan as found by analyzing insn's expression. */ 346132718Skan 347132718Skanstatic int 348132718Skanmay_trap_exp (rtx x, int is_store) 349132718Skan{ 350132718Skan enum rtx_code code; 351132718Skan 352132718Skan if (x == 0) 353132718Skan return TRAP_FREE; 354132718Skan code = GET_CODE (x); 355132718Skan if (is_store) 356132718Skan { 357132718Skan if (code == MEM && may_trap_p (x)) 358132718Skan return TRAP_RISKY; 359132718Skan else 360132718Skan return TRAP_FREE; 361132718Skan } 362132718Skan if (code == MEM) 363132718Skan { 364132718Skan /* The insn uses memory: a volatile load. */ 365132718Skan if (MEM_VOLATILE_P (x)) 366132718Skan return IRISKY; 367132718Skan /* An exception-free load. */ 368132718Skan if (!may_trap_p (x)) 369132718Skan return IFREE; 370132718Skan /* A load with 1 base register, to be further checked. */ 371132718Skan if (CONST_BASED_ADDRESS_P (XEXP (x, 0))) 372132718Skan return PFREE_CANDIDATE; 373132718Skan /* No info on the load, to be further checked. */ 374132718Skan return PRISKY_CANDIDATE; 375132718Skan } 376132718Skan else 377132718Skan { 378132718Skan const char *fmt; 379132718Skan int i, insn_class = TRAP_FREE; 380132718Skan 381132718Skan /* Neither store nor load, check if it may cause a trap. */ 382132718Skan if (may_trap_p (x)) 383132718Skan return TRAP_RISKY; 384132718Skan /* Recursive step: walk the insn... */ 385132718Skan fmt = GET_RTX_FORMAT (code); 386132718Skan for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 387132718Skan { 388132718Skan if (fmt[i] == 'e') 389132718Skan { 390132718Skan int tmp_class = may_trap_exp (XEXP (x, i), is_store); 391132718Skan insn_class = WORST_CLASS (insn_class, tmp_class); 392132718Skan } 393132718Skan else if (fmt[i] == 'E') 394132718Skan { 395132718Skan int j; 396132718Skan for (j = 0; j < XVECLEN (x, i); j++) 397132718Skan { 398132718Skan int tmp_class = may_trap_exp (XVECEXP (x, i, j), is_store); 399132718Skan insn_class = WORST_CLASS (insn_class, tmp_class); 400132718Skan if (insn_class == TRAP_RISKY || insn_class == IRISKY) 401132718Skan break; 402132718Skan } 403132718Skan } 404132718Skan if (insn_class == TRAP_RISKY || insn_class == IRISKY) 405132718Skan break; 406132718Skan } 407132718Skan return insn_class; 408132718Skan } 409132718Skan} 410132718Skan 411132718Skan/* Classifies insn for the purpose of verifying that it can be 412132718Skan moved speculatively, by examining it's patterns, returning: 413132718Skan TRAP_RISKY: store, or risky non-load insn (e.g. division by variable). 414132718Skan TRAP_FREE: non-load insn. 415132718Skan IFREE: load from a globally safe location. 416132718Skan IRISKY: volatile load. 417132718Skan PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for 418132718Skan being either PFREE or PRISKY. */ 419132718Skan 420132718Skanint 421132718Skanhaifa_classify_insn (rtx insn) 422132718Skan{ 423132718Skan rtx pat = PATTERN (insn); 424132718Skan int tmp_class = TRAP_FREE; 425132718Skan int insn_class = TRAP_FREE; 426132718Skan enum rtx_code code; 427132718Skan 428132718Skan if (GET_CODE (pat) == PARALLEL) 429132718Skan { 430132718Skan int i, len = XVECLEN (pat, 0); 431132718Skan 432132718Skan for (i = len - 1; i >= 0; i--) 433132718Skan { 434132718Skan code = GET_CODE (XVECEXP (pat, 0, i)); 435132718Skan switch (code) 436132718Skan { 437132718Skan case CLOBBER: 438132718Skan /* Test if it is a 'store'. */ 439132718Skan tmp_class = may_trap_exp (XEXP (XVECEXP (pat, 0, i), 0), 1); 440132718Skan break; 441132718Skan case SET: 442132718Skan /* Test if it is a store. */ 443132718Skan tmp_class = may_trap_exp (SET_DEST (XVECEXP (pat, 0, i)), 1); 444132718Skan if (tmp_class == TRAP_RISKY) 445132718Skan break; 446132718Skan /* Test if it is a load. */ 447132718Skan tmp_class 448132718Skan = WORST_CLASS (tmp_class, 449132718Skan may_trap_exp (SET_SRC (XVECEXP (pat, 0, i)), 450132718Skan 0)); 451132718Skan break; 452132718Skan case COND_EXEC: 453132718Skan case TRAP_IF: 454132718Skan tmp_class = TRAP_RISKY; 455132718Skan break; 456132718Skan default: 457132718Skan ; 458132718Skan } 459132718Skan insn_class = WORST_CLASS (insn_class, tmp_class); 460132718Skan if (insn_class == TRAP_RISKY || insn_class == IRISKY) 461132718Skan break; 462132718Skan } 463132718Skan } 464132718Skan else 465132718Skan { 466132718Skan code = GET_CODE (pat); 467132718Skan switch (code) 468132718Skan { 469132718Skan case CLOBBER: 470132718Skan /* Test if it is a 'store'. */ 471132718Skan tmp_class = may_trap_exp (XEXP (pat, 0), 1); 472132718Skan break; 473132718Skan case SET: 474132718Skan /* Test if it is a store. */ 475132718Skan tmp_class = may_trap_exp (SET_DEST (pat), 1); 476132718Skan if (tmp_class == TRAP_RISKY) 477132718Skan break; 478132718Skan /* Test if it is a load. */ 479132718Skan tmp_class = 480132718Skan WORST_CLASS (tmp_class, 481132718Skan may_trap_exp (SET_SRC (pat), 0)); 482132718Skan break; 483132718Skan case COND_EXEC: 484132718Skan case TRAP_IF: 485132718Skan tmp_class = TRAP_RISKY; 486132718Skan break; 487132718Skan default:; 488132718Skan } 489132718Skan insn_class = tmp_class; 490132718Skan } 491132718Skan 492132718Skan return insn_class; 493132718Skan} 494132718Skan 49550397Sobrien/* Forward declarations. */ 496117395Skan 497169689SkanHAIFA_INLINE static int insn_cost1 (rtx, enum reg_note, rtx, rtx); 498132718Skanstatic int priority (rtx); 499132718Skanstatic int rank_for_schedule (const void *, const void *); 500132718Skanstatic void swap_sort (rtx *, int); 501132718Skanstatic void queue_insn (rtx, int); 502169689Skanstatic int schedule_insn (rtx); 503132718Skanstatic int find_set_reg_weight (rtx); 504169689Skanstatic void find_insn_reg_weight (basic_block); 505169689Skanstatic void find_insn_reg_weight1 (rtx); 506132718Skanstatic void adjust_priority (rtx); 507132718Skanstatic void advance_one_cycle (void); 50850397Sobrien 50950397Sobrien/* Notes handling mechanism: 51050397Sobrien ========================= 51150397Sobrien Generally, NOTES are saved before scheduling and restored after scheduling. 51250397Sobrien The scheduler distinguishes between three types of notes: 51350397Sobrien 51450397Sobrien (1) LINE_NUMBER notes, generated and used for debugging. Here, 51550397Sobrien before scheduling a region, a pointer to the LINE_NUMBER note is 51650397Sobrien added to the insn following it (in save_line_notes()), and the note 51750397Sobrien is removed (in rm_line_notes() and unlink_line_notes()). After 51850397Sobrien scheduling the region, this pointer is used for regeneration of 51950397Sobrien the LINE_NUMBER note (in restore_line_notes()). 52050397Sobrien 52150397Sobrien (2) LOOP_BEGIN, LOOP_END, SETJMP, EHREGION_BEG, EHREGION_END notes: 52250397Sobrien Before scheduling a region, a pointer to the note is added to the insn 52350397Sobrien that follows or precedes it. (This happens as part of the data dependence 52450397Sobrien computation). After scheduling an insn, the pointer contained in it is 52550397Sobrien used for regenerating the corresponding note (in reemit_notes). 52650397Sobrien 52750397Sobrien (3) All other notes (e.g. INSN_DELETED): Before scheduling a block, 52850397Sobrien these notes are put in a list (in rm_other_notes() and 52950397Sobrien unlink_other_notes ()). After scheduling the block, these notes are 53050397Sobrien inserted at the beginning of the block (in schedule_block()). */ 53150397Sobrien 532132718Skanstatic rtx unlink_other_notes (rtx, rtx); 533132718Skanstatic rtx unlink_line_notes (rtx, rtx); 534169689Skanstatic void reemit_notes (rtx); 53550397Sobrien 536132718Skanstatic rtx *ready_lastpos (struct ready_list *); 537169689Skanstatic void ready_add (struct ready_list *, rtx, bool); 538132718Skanstatic void ready_sort (struct ready_list *); 539132718Skanstatic rtx ready_remove_first (struct ready_list *); 54050397Sobrien 541132718Skanstatic void queue_to_ready (struct ready_list *); 542132718Skanstatic int early_queue_to_ready (state_t, struct ready_list *); 54350397Sobrien 544132718Skanstatic void debug_ready_list (struct ready_list *); 54550397Sobrien 546169689Skanstatic void move_insn (rtx); 54750397Sobrien 548117395Skan/* The following functions are used to implement multi-pass scheduling 549169689Skan on the first cycle. */ 550132718Skanstatic rtx ready_element (struct ready_list *, int); 551132718Skanstatic rtx ready_remove (struct ready_list *, int); 552169689Skanstatic void ready_remove_insn (rtx); 553169689Skanstatic int max_issue (struct ready_list *, int *, int); 554117395Skan 555132718Skanstatic rtx choose_ready (struct ready_list *); 556117395Skan 557169689Skanstatic void fix_inter_tick (rtx, rtx); 558169689Skanstatic int fix_tick_ready (rtx); 559169689Skanstatic void change_queue_index (rtx, int); 560169689Skanstatic void resolve_dep (rtx, rtx); 561169689Skan 562169689Skan/* The following functions are used to implement scheduling of data/control 563169689Skan speculative instructions. */ 564169689Skan 565169689Skanstatic void extend_h_i_d (void); 566169689Skanstatic void extend_ready (int); 567169689Skanstatic void extend_global (rtx); 568169689Skanstatic void extend_all (rtx); 569169689Skanstatic void init_h_i_d (rtx); 570169689Skanstatic void generate_recovery_code (rtx); 571169689Skanstatic void process_insn_depend_be_in_spec (rtx, rtx, ds_t); 572169689Skanstatic void begin_speculative_block (rtx); 573169689Skanstatic void add_to_speculative_block (rtx); 574169689Skanstatic dw_t dep_weak (ds_t); 575169689Skanstatic edge find_fallthru_edge (basic_block); 576169689Skanstatic void init_before_recovery (void); 577169689Skanstatic basic_block create_recovery_block (void); 578169689Skanstatic void create_check_block_twin (rtx, bool); 579169689Skanstatic void fix_recovery_deps (basic_block); 580169689Skanstatic void associate_line_notes_with_blocks (basic_block); 581169689Skanstatic void change_pattern (rtx, rtx); 582169689Skanstatic int speculate_insn (rtx, ds_t, rtx *); 583169689Skanstatic void dump_new_block_header (int, basic_block, rtx, rtx); 584169689Skanstatic void restore_bb_notes (basic_block); 585169689Skanstatic void extend_bb (basic_block); 586169689Skanstatic void fix_jump_move (rtx); 587169689Skanstatic void move_block_after_check (rtx); 588169689Skanstatic void move_succs (VEC(edge,gc) **, basic_block); 589169689Skanstatic void init_glat (void); 590169689Skanstatic void init_glat1 (basic_block); 591169689Skanstatic void attach_life_info1 (basic_block); 592169689Skanstatic void free_glat (void); 593169689Skanstatic void sched_remove_insn (rtx); 594169689Skanstatic void clear_priorities (rtx); 595169689Skanstatic void add_jump_dependencies (rtx, rtx); 596169689Skanstatic void calc_priorities (rtx); 597169689Skan#ifdef ENABLE_CHECKING 598169689Skanstatic int has_edge_p (VEC(edge,gc) *, int); 599169689Skanstatic void check_cfg (rtx, rtx); 600169689Skanstatic void check_sched_flags (void); 601169689Skan#endif 602169689Skan 60350397Sobrien#endif /* INSN_SCHEDULING */ 60450397Sobrien 60590075Sobrien/* Point to state used for the current scheduling pass. */ 60690075Sobrienstruct sched_info *current_sched_info; 60750397Sobrien 60850397Sobrien#ifndef INSN_SCHEDULING 60950397Sobrienvoid 610169689Skanschedule_insns (void) 61150397Sobrien{ 61250397Sobrien} 61350397Sobrien#else 61450397Sobrien 615169689Skan/* Working copy of frontend's sched_info variable. */ 616169689Skanstatic struct sched_info current_sched_info_var; 617169689Skan 61850397Sobrien/* Pointer to the last instruction scheduled. Used by rank_for_schedule, 61950397Sobrien so that insns independent of the last scheduled insn will be preferred 62050397Sobrien over dependent instructions. */ 62150397Sobrien 62250397Sobrienstatic rtx last_scheduled_insn; 62350397Sobrien 624169689Skan/* Compute cost of executing INSN given the dependence LINK on the insn USED. 625169689Skan This is the number of cycles between instruction issue and 626169689Skan instruction results. */ 62750397Sobrien 62890075SobrienHAIFA_INLINE int 629169689Skaninsn_cost (rtx insn, rtx link, rtx used) 63050397Sobrien{ 631169689Skan return insn_cost1 (insn, used ? REG_NOTE_KIND (link) : REG_NOTE_MAX, 632169689Skan link, used); 63350397Sobrien} 63450397Sobrien 635169689Skan/* Compute cost of executing INSN given the dependence on the insn USED. 636169689Skan If LINK is not NULL, then its REG_NOTE_KIND is used as a dependence type. 637169689Skan Otherwise, dependence between INSN and USED is assumed to be of type 638169689Skan DEP_TYPE. This function was introduced as a workaround for 639169689Skan targetm.adjust_cost hook. 64050397Sobrien This is the number of cycles between instruction issue and 64150397Sobrien instruction results. */ 64250397Sobrien 643169689SkanHAIFA_INLINE static int 644169689Skaninsn_cost1 (rtx insn, enum reg_note dep_type, rtx link, rtx used) 64550397Sobrien{ 64690075Sobrien int cost = INSN_COST (insn); 64750397Sobrien 648117395Skan if (cost < 0) 64950397Sobrien { 650117395Skan /* A USE insn, or something else we don't need to 651117395Skan understand. We can't pass these directly to 652117395Skan result_ready_cost or insn_default_latency because it will 653117395Skan trigger a fatal error for unrecognizable insns. */ 654117395Skan if (recog_memoized (insn) < 0) 65550397Sobrien { 656117395Skan INSN_COST (insn) = 0; 657117395Skan return 0; 65850397Sobrien } 65950397Sobrien else 66050397Sobrien { 661169689Skan cost = insn_default_latency (insn); 662117395Skan if (cost < 0) 663117395Skan cost = 0; 664132718Skan 66550397Sobrien INSN_COST (insn) = cost; 66650397Sobrien } 66750397Sobrien } 66850397Sobrien 66990075Sobrien /* In this case estimate cost without caring how insn is used. */ 670169689Skan if (used == 0) 67150397Sobrien return cost; 67250397Sobrien 673117395Skan /* A USE insn should never require the value used to be computed. 674117395Skan This allows the computation of a function's result and parameter 675117395Skan values to overlap the return and call. */ 676117395Skan if (recog_memoized (used) < 0) 67790075Sobrien cost = 0; 678117395Skan else 67950397Sobrien { 680169689Skan gcc_assert (!link || dep_type == REG_NOTE_KIND (link)); 681169689Skan 682169689Skan if (INSN_CODE (insn) >= 0) 68390075Sobrien { 684169689Skan if (dep_type == REG_DEP_ANTI) 685169689Skan cost = 0; 686169689Skan else if (dep_type == REG_DEP_OUTPUT) 687117395Skan { 688169689Skan cost = (insn_default_latency (insn) 689169689Skan - insn_default_latency (used)); 690169689Skan if (cost <= 0) 691169689Skan cost = 1; 692117395Skan } 693169689Skan else if (bypass_p (insn)) 694169689Skan cost = insn_latency (insn, used); 69590075Sobrien } 696117395Skan 697169689Skan if (targetm.sched.adjust_cost_2) 698169689Skan cost = targetm.sched.adjust_cost_2 (used, (int) dep_type, insn, cost); 699169689Skan else 700169689Skan { 701169689Skan gcc_assert (link); 702169689Skan if (targetm.sched.adjust_cost) 703169689Skan cost = targetm.sched.adjust_cost (used, link, insn, cost); 704169689Skan } 705117395Skan 706117395Skan if (cost < 0) 707117395Skan cost = 0; 70850397Sobrien } 709132718Skan 71050397Sobrien return cost; 71150397Sobrien} 71250397Sobrien 71350397Sobrien/* Compute the priority number for INSN. */ 71450397Sobrien 71550397Sobrienstatic int 716132718Skanpriority (rtx insn) 71750397Sobrien{ 71850397Sobrien rtx link; 71950397Sobrien 72090075Sobrien if (! INSN_P (insn)) 72150397Sobrien return 0; 72250397Sobrien 72390075Sobrien if (! INSN_PRIORITY_KNOWN (insn)) 72450397Sobrien { 72590075Sobrien int this_priority = 0; 72690075Sobrien 72750397Sobrien if (INSN_DEPEND (insn) == 0) 72850397Sobrien this_priority = insn_cost (insn, 0, 0); 72950397Sobrien else 73050397Sobrien { 731169689Skan rtx prev_first, twin; 732169689Skan basic_block rec; 73350397Sobrien 734169689Skan /* For recovery check instructions we calculate priority slightly 735169689Skan different than that of normal instructions. Instead of walking 736169689Skan through INSN_DEPEND (check) list, we walk through INSN_DEPEND list 737169689Skan of each instruction in the corresponding recovery block. */ 73850397Sobrien 739169689Skan rec = RECOVERY_BLOCK (insn); 740169689Skan if (!rec || rec == EXIT_BLOCK_PTR) 741169689Skan { 742169689Skan prev_first = PREV_INSN (insn); 743169689Skan twin = insn; 744169689Skan } 745169689Skan else 746169689Skan { 747169689Skan prev_first = NEXT_INSN (BB_HEAD (rec)); 748169689Skan twin = PREV_INSN (BB_END (rec)); 749169689Skan } 75050397Sobrien 751169689Skan do 752169689Skan { 753169689Skan for (link = INSN_DEPEND (twin); link; link = XEXP (link, 1)) 754169689Skan { 755169689Skan rtx next; 756169689Skan int next_priority; 757169689Skan 758169689Skan next = XEXP (link, 0); 759169689Skan 760169689Skan if (BLOCK_FOR_INSN (next) != rec) 761169689Skan { 762169689Skan /* Critical path is meaningful in block boundaries 763169689Skan only. */ 764169689Skan if (! (*current_sched_info->contributes_to_priority) 765169689Skan (next, insn) 766169689Skan /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set, 767169689Skan then speculative instructions will less likely be 768169689Skan scheduled. That is because the priority of 769169689Skan their producers will increase, and, thus, the 770169689Skan producers will more likely be scheduled, thus, 771169689Skan resolving the dependence. */ 772169689Skan || ((current_sched_info->flags & DO_SPECULATION) 773169689Skan && (DEP_STATUS (link) & SPECULATIVE) 774169689Skan && !(spec_info->flags 775169689Skan & COUNT_SPEC_IN_CRITICAL_PATH))) 776169689Skan continue; 777169689Skan 778169689Skan next_priority = insn_cost1 (insn, 779169689Skan twin == insn ? 780169689Skan REG_NOTE_KIND (link) : 781169689Skan REG_DEP_ANTI, 782169689Skan twin == insn ? link : 0, 783169689Skan next) + priority (next); 78450397Sobrien 785169689Skan if (next_priority > this_priority) 786169689Skan this_priority = next_priority; 787169689Skan } 788169689Skan } 789169689Skan 790169689Skan twin = PREV_INSN (twin); 79150397Sobrien } 792169689Skan while (twin != prev_first); 79350397Sobrien } 79490075Sobrien INSN_PRIORITY (insn) = this_priority; 79590075Sobrien INSN_PRIORITY_KNOWN (insn) = 1; 79650397Sobrien } 79750397Sobrien 79890075Sobrien return INSN_PRIORITY (insn); 79950397Sobrien} 80050397Sobrien 80150397Sobrien/* Macros and functions for keeping the priority queue sorted, and 802132718Skan dealing with queuing and dequeuing of instructions. */ 80350397Sobrien 80450397Sobrien#define SCHED_SORT(READY, N_READY) \ 80550397Sobriendo { if ((N_READY) == 2) \ 80650397Sobrien swap_sort (READY, N_READY); \ 80750397Sobrien else if ((N_READY) > 2) \ 80850397Sobrien qsort (READY, N_READY, sizeof (rtx), rank_for_schedule); } \ 80950397Sobrienwhile (0) 81050397Sobrien 81150397Sobrien/* Returns a positive value if x is preferred; returns a negative value if 81250397Sobrien y is preferred. Should never return 0, since that will make the sort 81350397Sobrien unstable. */ 81450397Sobrien 81550397Sobrienstatic int 816132718Skanrank_for_schedule (const void *x, const void *y) 81750397Sobrien{ 81890075Sobrien rtx tmp = *(const rtx *) y; 81990075Sobrien rtx tmp2 = *(const rtx *) x; 82050397Sobrien rtx link; 82150397Sobrien int tmp_class, tmp2_class, depend_count1, depend_count2; 82290075Sobrien int val, priority_val, weight_val, info_val; 82350397Sobrien 824132718Skan /* The insn in a schedule group should be issued the first. */ 825132718Skan if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2)) 826132718Skan return SCHED_GROUP_P (tmp2) ? 1 : -1; 827132718Skan 82890075Sobrien /* Prefer insn with higher priority. */ 82950397Sobrien priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp); 830132718Skan 83150397Sobrien if (priority_val) 83250397Sobrien return priority_val; 83350397Sobrien 834169689Skan /* Prefer speculative insn with greater dependencies weakness. */ 835169689Skan if (spec_info) 836169689Skan { 837169689Skan ds_t ds1, ds2; 838169689Skan dw_t dw1, dw2; 839169689Skan int dw; 840169689Skan 841169689Skan ds1 = TODO_SPEC (tmp) & SPECULATIVE; 842169689Skan if (ds1) 843169689Skan dw1 = dep_weak (ds1); 844169689Skan else 845169689Skan dw1 = NO_DEP_WEAK; 846169689Skan 847169689Skan ds2 = TODO_SPEC (tmp2) & SPECULATIVE; 848169689Skan if (ds2) 849169689Skan dw2 = dep_weak (ds2); 850169689Skan else 851169689Skan dw2 = NO_DEP_WEAK; 852169689Skan 853169689Skan dw = dw2 - dw1; 854169689Skan if (dw > (NO_DEP_WEAK / 8) || dw < -(NO_DEP_WEAK / 8)) 855169689Skan return dw; 856169689Skan } 857169689Skan 85890075Sobrien /* Prefer an insn with smaller contribution to registers-pressure. */ 85950397Sobrien if (!reload_completed && 86050397Sobrien (weight_val = INSN_REG_WEIGHT (tmp) - INSN_REG_WEIGHT (tmp2))) 861132718Skan return weight_val; 86250397Sobrien 86390075Sobrien info_val = (*current_sched_info->rank) (tmp, tmp2); 86490075Sobrien if (info_val) 86590075Sobrien return info_val; 86650397Sobrien 86790075Sobrien /* Compare insns based on their relation to the last-scheduled-insn. */ 868169689Skan if (INSN_P (last_scheduled_insn)) 86950397Sobrien { 87050397Sobrien /* Classify the instructions into three classes: 87150397Sobrien 1) Data dependent on last schedule insn. 87250397Sobrien 2) Anti/Output dependent on last scheduled insn. 87350397Sobrien 3) Independent of last scheduled insn, or has latency of one. 87450397Sobrien Choose the insn from the highest numbered class if different. */ 87550397Sobrien link = find_insn_list (tmp, INSN_DEPEND (last_scheduled_insn)); 87650397Sobrien if (link == 0 || insn_cost (last_scheduled_insn, link, tmp) == 1) 87750397Sobrien tmp_class = 3; 87850397Sobrien else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ 87950397Sobrien tmp_class = 1; 88050397Sobrien else 88150397Sobrien tmp_class = 2; 88250397Sobrien 88350397Sobrien link = find_insn_list (tmp2, INSN_DEPEND (last_scheduled_insn)); 88450397Sobrien if (link == 0 || insn_cost (last_scheduled_insn, link, tmp2) == 1) 88550397Sobrien tmp2_class = 3; 88650397Sobrien else if (REG_NOTE_KIND (link) == 0) /* Data dependence. */ 88750397Sobrien tmp2_class = 1; 88850397Sobrien else 88950397Sobrien tmp2_class = 2; 89050397Sobrien 89150397Sobrien if ((val = tmp2_class - tmp_class)) 89250397Sobrien return val; 89350397Sobrien } 89450397Sobrien 89590075Sobrien /* Prefer the insn which has more later insns that depend on it. 89650397Sobrien This gives the scheduler more freedom when scheduling later 89750397Sobrien instructions at the expense of added register pressure. */ 89850397Sobrien depend_count1 = 0; 89950397Sobrien for (link = INSN_DEPEND (tmp); link; link = XEXP (link, 1)) 90050397Sobrien depend_count1++; 90150397Sobrien 90250397Sobrien depend_count2 = 0; 90350397Sobrien for (link = INSN_DEPEND (tmp2); link; link = XEXP (link, 1)) 90450397Sobrien depend_count2++; 90550397Sobrien 90650397Sobrien val = depend_count2 - depend_count1; 90750397Sobrien if (val) 90850397Sobrien return val; 90990075Sobrien 91050397Sobrien /* If insns are equally good, sort by INSN_LUID (original insn order), 91150397Sobrien so that we make the sort stable. This minimizes instruction movement, 91250397Sobrien thus minimizing sched's effect on debugging and cross-jumping. */ 91350397Sobrien return INSN_LUID (tmp) - INSN_LUID (tmp2); 91450397Sobrien} 91550397Sobrien 91650397Sobrien/* Resort the array A in which only element at index N may be out of order. */ 91750397Sobrien 91850397SobrienHAIFA_INLINE static void 919132718Skanswap_sort (rtx *a, int n) 92050397Sobrien{ 92150397Sobrien rtx insn = a[n - 1]; 92250397Sobrien int i = n - 2; 92350397Sobrien 92450397Sobrien while (i >= 0 && rank_for_schedule (a + i, &insn) >= 0) 92550397Sobrien { 92650397Sobrien a[i + 1] = a[i]; 92750397Sobrien i -= 1; 92850397Sobrien } 92950397Sobrien a[i + 1] = insn; 93050397Sobrien} 93150397Sobrien 93250397Sobrien/* Add INSN to the insn queue so that it can be executed at least 93350397Sobrien N_CYCLES after the currently executing insn. Preserve insns 93450397Sobrien chain for debugging purposes. */ 93550397Sobrien 93650397SobrienHAIFA_INLINE static void 937132718Skanqueue_insn (rtx insn, int n_cycles) 93850397Sobrien{ 93950397Sobrien int next_q = NEXT_Q_AFTER (q_ptr, n_cycles); 94050397Sobrien rtx link = alloc_INSN_LIST (insn, insn_queue[next_q]); 941169689Skan 942169689Skan gcc_assert (n_cycles <= max_insn_queue_index); 943169689Skan 94450397Sobrien insn_queue[next_q] = link; 94550397Sobrien q_size += 1; 94650397Sobrien 94750397Sobrien if (sched_verbose >= 2) 94850397Sobrien { 94990075Sobrien fprintf (sched_dump, ";;\t\tReady-->Q: insn %s: ", 95090075Sobrien (*current_sched_info->print_insn) (insn, 0)); 95150397Sobrien 95290075Sobrien fprintf (sched_dump, "queued for %d cycles.\n", n_cycles); 95350397Sobrien } 954169689Skan 955169689Skan QUEUE_INDEX (insn) = next_q; 95650397Sobrien} 95750397Sobrien 958169689Skan/* Remove INSN from queue. */ 959169689Skanstatic void 960169689Skanqueue_remove (rtx insn) 961169689Skan{ 962169689Skan gcc_assert (QUEUE_INDEX (insn) >= 0); 963169689Skan remove_free_INSN_LIST_elem (insn, &insn_queue[QUEUE_INDEX (insn)]); 964169689Skan q_size--; 965169689Skan QUEUE_INDEX (insn) = QUEUE_NOWHERE; 966169689Skan} 967169689Skan 96890075Sobrien/* Return a pointer to the bottom of the ready list, i.e. the insn 96990075Sobrien with the lowest priority. */ 97050397Sobrien 97190075SobrienHAIFA_INLINE static rtx * 972132718Skanready_lastpos (struct ready_list *ready) 97350397Sobrien{ 974169689Skan gcc_assert (ready->n_ready >= 1); 97590075Sobrien return ready->vec + ready->first - ready->n_ready + 1; 97690075Sobrien} 97750397Sobrien 978169689Skan/* Add an element INSN to the ready list so that it ends up with the 979169689Skan lowest/highest priority depending on FIRST_P. */ 98050397Sobrien 981169689SkanHAIFA_INLINE static void 982169689Skanready_add (struct ready_list *ready, rtx insn, bool first_p) 98390075Sobrien{ 984169689Skan if (!first_p) 98550397Sobrien { 986169689Skan if (ready->first == ready->n_ready) 987169689Skan { 988169689Skan memmove (ready->vec + ready->veclen - ready->n_ready, 989169689Skan ready_lastpos (ready), 990169689Skan ready->n_ready * sizeof (rtx)); 991169689Skan ready->first = ready->veclen - 1; 992169689Skan } 993169689Skan ready->vec[ready->first - ready->n_ready] = insn; 99450397Sobrien } 995169689Skan else 996169689Skan { 997169689Skan if (ready->first == ready->veclen - 1) 998169689Skan { 999169689Skan if (ready->n_ready) 1000169689Skan /* ready_lastpos() fails when called with (ready->n_ready == 0). */ 1001169689Skan memmove (ready->vec + ready->veclen - ready->n_ready - 1, 1002169689Skan ready_lastpos (ready), 1003169689Skan ready->n_ready * sizeof (rtx)); 1004169689Skan ready->first = ready->veclen - 2; 1005169689Skan } 1006169689Skan ready->vec[++(ready->first)] = insn; 1007169689Skan } 1008169689Skan 100990075Sobrien ready->n_ready++; 1010169689Skan 1011169689Skan gcc_assert (QUEUE_INDEX (insn) != QUEUE_READY); 1012169689Skan QUEUE_INDEX (insn) = QUEUE_READY; 101350397Sobrien} 101450397Sobrien 101590075Sobrien/* Remove the element with the highest priority from the ready list and 101690075Sobrien return it. */ 101790075Sobrien 101890075SobrienHAIFA_INLINE static rtx 1019132718Skanready_remove_first (struct ready_list *ready) 102090075Sobrien{ 102190075Sobrien rtx t; 1022169689Skan 1023169689Skan gcc_assert (ready->n_ready); 102490075Sobrien t = ready->vec[ready->first--]; 102590075Sobrien ready->n_ready--; 102690075Sobrien /* If the queue becomes empty, reset it. */ 102790075Sobrien if (ready->n_ready == 0) 102890075Sobrien ready->first = ready->veclen - 1; 1029169689Skan 1030169689Skan gcc_assert (QUEUE_INDEX (t) == QUEUE_READY); 1031169689Skan QUEUE_INDEX (t) = QUEUE_NOWHERE; 1032169689Skan 103390075Sobrien return t; 103490075Sobrien} 103590075Sobrien 1036117395Skan/* The following code implements multi-pass scheduling for the first 1037117395Skan cycle. In other words, we will try to choose ready insn which 1038117395Skan permits to start maximum number of insns on the same cycle. */ 1039117395Skan 1040117395Skan/* Return a pointer to the element INDEX from the ready. INDEX for 1041117395Skan insn with the highest priority is 0, and the lowest priority has 1042117395Skan N_READY - 1. */ 1043117395Skan 1044117395SkanHAIFA_INLINE static rtx 1045132718Skanready_element (struct ready_list *ready, int index) 1046117395Skan{ 1047169689Skan gcc_assert (ready->n_ready && index < ready->n_ready); 1048169689Skan 1049117395Skan return ready->vec[ready->first - index]; 1050117395Skan} 1051117395Skan 1052117395Skan/* Remove the element INDEX from the ready list and return it. INDEX 1053117395Skan for insn with the highest priority is 0, and the lowest priority 1054117395Skan has N_READY - 1. */ 1055117395Skan 1056117395SkanHAIFA_INLINE static rtx 1057132718Skanready_remove (struct ready_list *ready, int index) 1058117395Skan{ 1059117395Skan rtx t; 1060117395Skan int i; 1061117395Skan 1062117395Skan if (index == 0) 1063117395Skan return ready_remove_first (ready); 1064169689Skan gcc_assert (ready->n_ready && index < ready->n_ready); 1065117395Skan t = ready->vec[ready->first - index]; 1066117395Skan ready->n_ready--; 1067117395Skan for (i = index; i < ready->n_ready; i++) 1068117395Skan ready->vec[ready->first - i] = ready->vec[ready->first - i - 1]; 1069169689Skan QUEUE_INDEX (t) = QUEUE_NOWHERE; 1070117395Skan return t; 1071117395Skan} 1072117395Skan 1073169689Skan/* Remove INSN from the ready list. */ 1074169689Skanstatic void 1075169689Skanready_remove_insn (rtx insn) 1076169689Skan{ 1077169689Skan int i; 1078117395Skan 1079169689Skan for (i = 0; i < readyp->n_ready; i++) 1080169689Skan if (ready_element (readyp, i) == insn) 1081169689Skan { 1082169689Skan ready_remove (readyp, i); 1083169689Skan return; 1084169689Skan } 1085169689Skan gcc_unreachable (); 1086169689Skan} 1087169689Skan 108890075Sobrien/* Sort the ready list READY by ascending priority, using the SCHED_SORT 108990075Sobrien macro. */ 109090075Sobrien 109190075SobrienHAIFA_INLINE static void 1092132718Skanready_sort (struct ready_list *ready) 109390075Sobrien{ 109490075Sobrien rtx *first = ready_lastpos (ready); 109590075Sobrien SCHED_SORT (first, ready->n_ready); 109690075Sobrien} 109790075Sobrien 109850397Sobrien/* PREV is an insn that is ready to execute. Adjust its priority if that 109990075Sobrien will help shorten or lengthen register lifetimes as appropriate. Also 110090075Sobrien provide a hook for the target to tweek itself. */ 110150397Sobrien 110250397SobrienHAIFA_INLINE static void 1103132718Skanadjust_priority (rtx prev) 110450397Sobrien{ 110590075Sobrien /* ??? There used to be code here to try and estimate how an insn 110690075Sobrien affected register lifetimes, but it did it by looking at REG_DEAD 110790075Sobrien notes, which we removed in schedule_region. Nor did it try to 110890075Sobrien take into account register pressure or anything useful like that. 110950397Sobrien 111090075Sobrien Revisit when we have a machine model to work with and not before. */ 111150397Sobrien 111290075Sobrien if (targetm.sched.adjust_priority) 111390075Sobrien INSN_PRIORITY (prev) = 1114169689Skan targetm.sched.adjust_priority (prev, INSN_PRIORITY (prev)); 111550397Sobrien} 111650397Sobrien 1117117395Skan/* Advance time on one cycle. */ 1118117395SkanHAIFA_INLINE static void 1119132718Skanadvance_one_cycle (void) 1120117395Skan{ 1121169689Skan if (targetm.sched.dfa_pre_cycle_insn) 1122169689Skan state_transition (curr_state, 1123169689Skan targetm.sched.dfa_pre_cycle_insn ()); 1124117395Skan 1125169689Skan state_transition (curr_state, NULL); 1126169689Skan 1127169689Skan if (targetm.sched.dfa_post_cycle_insn) 1128169689Skan state_transition (curr_state, 1129169689Skan targetm.sched.dfa_post_cycle_insn ()); 1130117395Skan} 1131117395Skan 113252284Sobrien/* Clock at which the previous instruction was issued. */ 113352284Sobrienstatic int last_clock_var; 113452284Sobrien 113550397Sobrien/* INSN is the "currently executing insn". Launch each insn which was 113690075Sobrien waiting on INSN. READY is the ready list which contains the insns 1137132718Skan that are ready to fire. CLOCK is the current cycle. The function 1138132718Skan returns necessary cycle advance after issuing the insn (it is not 1139132718Skan zero for insns in a schedule group). */ 114050397Sobrien 1141132718Skanstatic int 1142169689Skanschedule_insn (rtx insn) 114350397Sobrien{ 114450397Sobrien rtx link; 1145132718Skan int advance = 0; 114650397Sobrien 1147169689Skan if (sched_verbose >= 1) 114850397Sobrien { 1149117395Skan char buf[2048]; 1150117395Skan 1151117395Skan print_insn (buf, insn, 0); 1152132718Skan buf[40] = 0; 1153169689Skan fprintf (sched_dump, ";;\t%3i--> %-40s:", clock_var, buf); 1154117395Skan 1155117395Skan if (recog_memoized (insn) < 0) 1156117395Skan fprintf (sched_dump, "nothing"); 1157117395Skan else 1158117395Skan print_reservation (sched_dump, insn); 1159117395Skan fputc ('\n', sched_dump); 1160117395Skan } 116150397Sobrien 1162169689Skan /* Scheduling instruction should have all its dependencies resolved and 1163169689Skan should have been removed from the ready list. */ 1164169689Skan gcc_assert (INSN_DEP_COUNT (insn) == 0); 1165169689Skan gcc_assert (!LOG_LINKS (insn)); 1166169689Skan gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE); 116750397Sobrien 1168169689Skan QUEUE_INDEX (insn) = QUEUE_SCHEDULED; 1169169689Skan 1170169689Skan /* Now we can free RESOLVED_DEPS list. */ 1171169689Skan if (current_sched_info->flags & USE_DEPS_LIST) 1172169689Skan free_DEPS_LIST_list (&RESOLVED_DEPS (insn)); 1173169689Skan else 1174169689Skan free_INSN_LIST_list (&RESOLVED_DEPS (insn)); 1175169689Skan 1176169689Skan gcc_assert (INSN_TICK (insn) >= MIN_TICK); 1177169689Skan if (INSN_TICK (insn) > clock_var) 1178169689Skan /* INSN has been prematurely moved from the queue to the ready list. 1179169689Skan This is possible only if following flag is set. */ 1180169689Skan gcc_assert (flag_sched_stalled_insns); 118150397Sobrien 1182169689Skan /* ??? Probably, if INSN is scheduled prematurely, we should leave 1183169689Skan INSN_TICK untouched. This is a machine-dependent issue, actually. */ 1184169689Skan INSN_TICK (insn) = clock_var; 1185132718Skan 1186169689Skan /* Update dependent instructions. */ 1187169689Skan for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) 1188132718Skan { 118950397Sobrien rtx next = XEXP (link, 0); 119050397Sobrien 1191169689Skan resolve_dep (next, insn); 119250397Sobrien 1193169689Skan if (!IS_SPECULATION_BRANCHY_CHECK_P (insn)) 119450397Sobrien { 1195169689Skan int effective_cost; 1196169689Skan 1197169689Skan effective_cost = try_ready (next); 1198169689Skan 1199169689Skan if (effective_cost >= 0 1200169689Skan && SCHED_GROUP_P (next) 1201169689Skan && advance < effective_cost) 1202169689Skan advance = effective_cost; 120350397Sobrien } 1204169689Skan else 1205169689Skan /* Check always has only one forward dependence (to the first insn in 1206169689Skan the recovery block), therefore, this will be executed only once. */ 1207169689Skan { 1208169689Skan gcc_assert (XEXP (link, 1) == 0); 1209169689Skan fix_recovery_deps (RECOVERY_BLOCK (insn)); 1210169689Skan } 121150397Sobrien } 121250397Sobrien 121390075Sobrien /* Annotate the instruction with issue information -- TImode 121452284Sobrien indicates that the instruction is expected not to be able 121552284Sobrien to issue on the same cycle as the previous insn. A machine 121652284Sobrien may use this information to decide how the instruction should 121752284Sobrien be aligned. */ 1218132718Skan if (issue_rate > 1 1219117395Skan && GET_CODE (PATTERN (insn)) != USE 1220117395Skan && GET_CODE (PATTERN (insn)) != CLOBBER) 122152284Sobrien { 1222132718Skan if (reload_completed) 1223169689Skan PUT_MODE (insn, clock_var > last_clock_var ? TImode : VOIDmode); 1224169689Skan last_clock_var = clock_var; 122552284Sobrien } 1226169689Skan 1227132718Skan return advance; 122850397Sobrien} 122950397Sobrien 123090075Sobrien/* Functions for handling of notes. */ 123150397Sobrien 123250397Sobrien/* Delete notes beginning with INSN and put them in the chain 123350397Sobrien of notes ended by NOTE_LIST. 123450397Sobrien Returns the insn following the notes. */ 123550397Sobrien 123650397Sobrienstatic rtx 1237132718Skanunlink_other_notes (rtx insn, rtx tail) 123850397Sobrien{ 123950397Sobrien rtx prev = PREV_INSN (insn); 124050397Sobrien 1241169689Skan while (insn != tail && NOTE_NOT_BB_P (insn)) 124250397Sobrien { 124350397Sobrien rtx next = NEXT_INSN (insn); 1244169689Skan basic_block bb = BLOCK_FOR_INSN (insn); 1245169689Skan 124650397Sobrien /* Delete the note from its current position. */ 124750397Sobrien if (prev) 124850397Sobrien NEXT_INSN (prev) = next; 124950397Sobrien if (next) 125050397Sobrien PREV_INSN (next) = prev; 125150397Sobrien 1252169689Skan if (bb) 1253169689Skan { 1254169689Skan /* Basic block can begin with either LABEL or 1255169689Skan NOTE_INSN_BASIC_BLOCK. */ 1256169689Skan gcc_assert (BB_HEAD (bb) != insn); 1257169689Skan 1258169689Skan /* Check if we are removing last insn in the BB. */ 1259169689Skan if (BB_END (bb) == insn) 1260169689Skan BB_END (bb) = prev; 1261169689Skan } 1262169689Skan 126390075Sobrien /* See sched_analyze to see how these are handled. */ 1264169689Skan if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_BEG 126550397Sobrien && NOTE_LINE_NUMBER (insn) != NOTE_INSN_EH_REGION_END) 126650397Sobrien { 126750397Sobrien /* Insert the note at the end of the notes list. */ 126850397Sobrien PREV_INSN (insn) = note_list; 126950397Sobrien if (note_list) 127050397Sobrien NEXT_INSN (note_list) = insn; 127150397Sobrien note_list = insn; 127250397Sobrien } 127350397Sobrien 127450397Sobrien insn = next; 127550397Sobrien } 127650397Sobrien return insn; 127750397Sobrien} 127850397Sobrien 127950397Sobrien/* Delete line notes beginning with INSN. Record line-number notes so 128050397Sobrien they can be reused. Returns the insn following the notes. */ 128150397Sobrien 128250397Sobrienstatic rtx 1283132718Skanunlink_line_notes (rtx insn, rtx tail) 128450397Sobrien{ 128550397Sobrien rtx prev = PREV_INSN (insn); 128650397Sobrien 1287169689Skan while (insn != tail && NOTE_NOT_BB_P (insn)) 128850397Sobrien { 128950397Sobrien rtx next = NEXT_INSN (insn); 129050397Sobrien 129150397Sobrien if (write_symbols != NO_DEBUG && NOTE_LINE_NUMBER (insn) > 0) 129250397Sobrien { 1293169689Skan basic_block bb = BLOCK_FOR_INSN (insn); 1294169689Skan 129550397Sobrien /* Delete the note from its current position. */ 129650397Sobrien if (prev) 129750397Sobrien NEXT_INSN (prev) = next; 129850397Sobrien if (next) 129950397Sobrien PREV_INSN (next) = prev; 130050397Sobrien 1301169689Skan if (bb) 1302169689Skan { 1303169689Skan /* Basic block can begin with either LABEL or 1304169689Skan NOTE_INSN_BASIC_BLOCK. */ 1305169689Skan gcc_assert (BB_HEAD (bb) != insn); 1306169689Skan 1307169689Skan /* Check if we are removing last insn in the BB. */ 1308169689Skan if (BB_END (bb) == insn) 1309169689Skan BB_END (bb) = prev; 1310169689Skan } 1311169689Skan 131250397Sobrien /* Record line-number notes so they can be reused. */ 131350397Sobrien LINE_NOTE (insn) = insn; 131450397Sobrien } 131550397Sobrien else 131650397Sobrien prev = insn; 131750397Sobrien 131850397Sobrien insn = next; 131950397Sobrien } 132050397Sobrien return insn; 132150397Sobrien} 132250397Sobrien 1323169689Skan/* Return the head and tail pointers of ebb starting at BEG and ending 1324169689Skan at END. */ 132550397Sobrien 132690075Sobrienvoid 1327169689Skanget_ebb_head_tail (basic_block beg, basic_block end, rtx *headp, rtx *tailp) 132850397Sobrien{ 1329169689Skan rtx beg_head = BB_HEAD (beg); 1330169689Skan rtx beg_tail = BB_END (beg); 1331169689Skan rtx end_head = BB_HEAD (end); 1332169689Skan rtx end_tail = BB_END (end); 133350397Sobrien 1334169689Skan /* Don't include any notes or labels at the beginning of the BEG 1335169689Skan basic block, or notes at the end of the END basic blocks. */ 133650397Sobrien 1337169689Skan if (LABEL_P (beg_head)) 1338169689Skan beg_head = NEXT_INSN (beg_head); 1339169689Skan 1340169689Skan while (beg_head != beg_tail) 1341169689Skan if (NOTE_P (beg_head)) 1342169689Skan beg_head = NEXT_INSN (beg_head); 1343169689Skan else 1344169689Skan break; 1345169689Skan 1346169689Skan *headp = beg_head; 1347169689Skan 1348169689Skan if (beg == end) 1349169689Skan end_head = beg_head; 1350169689Skan else if (LABEL_P (end_head)) 1351169689Skan end_head = NEXT_INSN (end_head); 1352169689Skan 1353169689Skan while (end_head != end_tail) 1354169689Skan if (NOTE_P (end_tail)) 1355169689Skan end_tail = PREV_INSN (end_tail); 1356169689Skan else 1357169689Skan break; 1358169689Skan 1359169689Skan *tailp = end_tail; 136050397Sobrien} 136150397Sobrien 136290075Sobrien/* Return nonzero if there are no real insns in the range [ HEAD, TAIL ]. */ 136350397Sobrien 136490075Sobrienint 1365132718Skanno_real_insns_p (rtx head, rtx tail) 136650397Sobrien{ 136790075Sobrien while (head != NEXT_INSN (tail)) 136890075Sobrien { 1369169689Skan if (!NOTE_P (head) && !LABEL_P (head)) 137090075Sobrien return 0; 137190075Sobrien head = NEXT_INSN (head); 137290075Sobrien } 137390075Sobrien return 1; 137490075Sobrien} 137590075Sobrien 137690075Sobrien/* Delete line notes from one block. Save them so they can be later restored 137790075Sobrien (in restore_line_notes). HEAD and TAIL are the boundaries of the 137890075Sobrien block in which notes should be processed. */ 137990075Sobrien 138090075Sobrienvoid 1381132718Skanrm_line_notes (rtx head, rtx tail) 138290075Sobrien{ 138350397Sobrien rtx next_tail; 138450397Sobrien rtx insn; 138550397Sobrien 138650397Sobrien next_tail = NEXT_INSN (tail); 138750397Sobrien for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 138850397Sobrien { 138950397Sobrien rtx prev; 139050397Sobrien 139150397Sobrien /* Farm out notes, and maybe save them in NOTE_LIST. 139250397Sobrien This is needed to keep the debugger from 139350397Sobrien getting completely deranged. */ 1394169689Skan if (NOTE_NOT_BB_P (insn)) 139550397Sobrien { 139650397Sobrien prev = insn; 139750397Sobrien insn = unlink_line_notes (insn, next_tail); 139850397Sobrien 1399169689Skan gcc_assert (prev != tail && prev != head && insn != next_tail); 140050397Sobrien } 140150397Sobrien } 140250397Sobrien} 140350397Sobrien 140490075Sobrien/* Save line number notes for each insn in block B. HEAD and TAIL are 140590075Sobrien the boundaries of the block in which notes should be processed. */ 140650397Sobrien 140790075Sobrienvoid 1408132718Skansave_line_notes (int b, rtx head, rtx tail) 140950397Sobrien{ 141050397Sobrien rtx next_tail; 141150397Sobrien 141250397Sobrien /* We must use the true line number for the first insn in the block 141350397Sobrien that was computed and saved at the start of this pass. We can't 141450397Sobrien use the current line number, because scheduling of the previous 141550397Sobrien block may have changed the current line number. */ 141650397Sobrien 141790075Sobrien rtx line = line_note_head[b]; 141850397Sobrien rtx insn; 141950397Sobrien 142050397Sobrien next_tail = NEXT_INSN (tail); 142150397Sobrien 142290075Sobrien for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 1423169689Skan if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0) 142450397Sobrien line = insn; 142550397Sobrien else 142650397Sobrien LINE_NOTE (insn) = line; 142750397Sobrien} 142850397Sobrien 142990075Sobrien/* After a block was scheduled, insert line notes into the insns list. 143090075Sobrien HEAD and TAIL are the boundaries of the block in which notes should 143190075Sobrien be processed. */ 143250397Sobrien 143390075Sobrienvoid 1434132718Skanrestore_line_notes (rtx head, rtx tail) 143550397Sobrien{ 143650397Sobrien rtx line, note, prev, new; 143750397Sobrien int added_notes = 0; 143890075Sobrien rtx next_tail, insn; 143950397Sobrien 144090075Sobrien head = head; 144190075Sobrien next_tail = NEXT_INSN (tail); 144250397Sobrien 144350397Sobrien /* Determine the current line-number. We want to know the current 144450397Sobrien line number of the first insn of the block here, in case it is 144550397Sobrien different from the true line number that was saved earlier. If 144650397Sobrien different, then we need a line number note before the first insn 144750397Sobrien of this block. If it happens to be the same, then we don't want to 144850397Sobrien emit another line number note here. */ 144950397Sobrien for (line = head; line; line = PREV_INSN (line)) 1450169689Skan if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0) 145150397Sobrien break; 145250397Sobrien 145350397Sobrien /* Walk the insns keeping track of the current line-number and inserting 145450397Sobrien the line-number notes as needed. */ 145550397Sobrien for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 1456169689Skan if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0) 145750397Sobrien line = insn; 145850397Sobrien /* This used to emit line number notes before every non-deleted note. 145950397Sobrien However, this confuses a debugger, because line notes not separated 146050397Sobrien by real instructions all end up at the same address. I can find no 146150397Sobrien use for line number notes before other notes, so none are emitted. */ 1462169689Skan else if (!NOTE_P (insn) 146390075Sobrien && INSN_UID (insn) < old_max_uid 146450397Sobrien && (note = LINE_NOTE (insn)) != 0 146550397Sobrien && note != line 146650397Sobrien && (line == 0 1467169689Skan#ifdef USE_MAPPED_LOCATION 1468169689Skan || NOTE_SOURCE_LOCATION (note) != NOTE_SOURCE_LOCATION (line) 1469169689Skan#else 147050397Sobrien || NOTE_LINE_NUMBER (note) != NOTE_LINE_NUMBER (line) 1471169689Skan || NOTE_SOURCE_FILE (note) != NOTE_SOURCE_FILE (line) 1472169689Skan#endif 1473169689Skan )) 147450397Sobrien { 147550397Sobrien line = note; 147650397Sobrien prev = PREV_INSN (insn); 147750397Sobrien if (LINE_NOTE (note)) 147850397Sobrien { 147950397Sobrien /* Re-use the original line-number note. */ 148050397Sobrien LINE_NOTE (note) = 0; 148150397Sobrien PREV_INSN (note) = prev; 148250397Sobrien NEXT_INSN (prev) = note; 148350397Sobrien PREV_INSN (insn) = note; 148450397Sobrien NEXT_INSN (note) = insn; 1485169689Skan set_block_for_insn (note, BLOCK_FOR_INSN (insn)); 148650397Sobrien } 148750397Sobrien else 148850397Sobrien { 148950397Sobrien added_notes++; 149050397Sobrien new = emit_note_after (NOTE_LINE_NUMBER (note), prev); 1491169689Skan#ifndef USE_MAPPED_LOCATION 149250397Sobrien NOTE_SOURCE_FILE (new) = NOTE_SOURCE_FILE (note); 1493169689Skan#endif 149450397Sobrien } 149550397Sobrien } 149650397Sobrien if (sched_verbose && added_notes) 149790075Sobrien fprintf (sched_dump, ";; added %d line-number notes\n", added_notes); 149850397Sobrien} 149950397Sobrien 150050397Sobrien/* After scheduling the function, delete redundant line notes from the 150150397Sobrien insns list. */ 150250397Sobrien 150390075Sobrienvoid 1504132718Skanrm_redundant_line_notes (void) 150550397Sobrien{ 150650397Sobrien rtx line = 0; 150750397Sobrien rtx insn = get_insns (); 150850397Sobrien int active_insn = 0; 150950397Sobrien int notes = 0; 151050397Sobrien 151150397Sobrien /* Walk the insns deleting redundant line-number notes. Many of these 151250397Sobrien are already present. The remainder tend to occur at basic 151350397Sobrien block boundaries. */ 151450397Sobrien for (insn = get_last_insn (); insn; insn = PREV_INSN (insn)) 1515169689Skan if (NOTE_P (insn) && NOTE_LINE_NUMBER (insn) > 0) 151650397Sobrien { 151750397Sobrien /* If there are no active insns following, INSN is redundant. */ 151850397Sobrien if (active_insn == 0) 151950397Sobrien { 152050397Sobrien notes++; 1521169689Skan SET_INSN_DELETED (insn); 152250397Sobrien } 152350397Sobrien /* If the line number is unchanged, LINE is redundant. */ 152450397Sobrien else if (line 1525169689Skan#ifdef USE_MAPPED_LOCATION 1526169689Skan && NOTE_SOURCE_LOCATION (line) == NOTE_SOURCE_LOCATION (insn) 1527169689Skan#else 152850397Sobrien && NOTE_LINE_NUMBER (line) == NOTE_LINE_NUMBER (insn) 1529169689Skan && NOTE_SOURCE_FILE (line) == NOTE_SOURCE_FILE (insn) 1530169689Skan#endif 1531169689Skan) 153250397Sobrien { 153350397Sobrien notes++; 1534169689Skan SET_INSN_DELETED (line); 153550397Sobrien line = insn; 153650397Sobrien } 153750397Sobrien else 153850397Sobrien line = insn; 153950397Sobrien active_insn = 0; 154050397Sobrien } 1541169689Skan else if (!((NOTE_P (insn) 154250397Sobrien && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED) 1543169689Skan || (NONJUMP_INSN_P (insn) 154450397Sobrien && (GET_CODE (PATTERN (insn)) == USE 154550397Sobrien || GET_CODE (PATTERN (insn)) == CLOBBER)))) 154650397Sobrien active_insn++; 154750397Sobrien 154850397Sobrien if (sched_verbose && notes) 154990075Sobrien fprintf (sched_dump, ";; deleted %d line-number notes\n", notes); 155050397Sobrien} 155150397Sobrien 155290075Sobrien/* Delete notes between HEAD and TAIL and put them in the chain 155350397Sobrien of notes ended by NOTE_LIST. */ 155450397Sobrien 155590075Sobrienvoid 1556132718Skanrm_other_notes (rtx head, rtx tail) 155750397Sobrien{ 155850397Sobrien rtx next_tail; 155950397Sobrien rtx insn; 156050397Sobrien 156190075Sobrien note_list = 0; 156290075Sobrien if (head == tail && (! INSN_P (head))) 156350397Sobrien return; 156450397Sobrien 156550397Sobrien next_tail = NEXT_INSN (tail); 156650397Sobrien for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 156750397Sobrien { 156850397Sobrien rtx prev; 156950397Sobrien 157050397Sobrien /* Farm out notes, and maybe save them in NOTE_LIST. 157150397Sobrien This is needed to keep the debugger from 157250397Sobrien getting completely deranged. */ 1573169689Skan if (NOTE_NOT_BB_P (insn)) 157450397Sobrien { 157550397Sobrien prev = insn; 157650397Sobrien 157750397Sobrien insn = unlink_other_notes (insn, next_tail); 157850397Sobrien 1579169689Skan gcc_assert (prev != tail && prev != head && insn != next_tail); 158050397Sobrien } 158150397Sobrien } 158250397Sobrien} 158350397Sobrien 158490075Sobrien/* Functions for computation of registers live/usage info. */ 158550397Sobrien 1586132718Skan/* This function looks for a new register being defined. 1587132718Skan If the destination register is already used by the source, 1588132718Skan a new register is not needed. */ 1589132718Skan 1590132718Skanstatic int 1591132718Skanfind_set_reg_weight (rtx x) 1592132718Skan{ 1593132718Skan if (GET_CODE (x) == CLOBBER 1594132718Skan && register_operand (SET_DEST (x), VOIDmode)) 1595132718Skan return 1; 1596132718Skan if (GET_CODE (x) == SET 1597132718Skan && register_operand (SET_DEST (x), VOIDmode)) 1598132718Skan { 1599169689Skan if (REG_P (SET_DEST (x))) 1600132718Skan { 1601132718Skan if (!reg_mentioned_p (SET_DEST (x), SET_SRC (x))) 1602132718Skan return 1; 1603132718Skan else 1604132718Skan return 0; 1605132718Skan } 1606132718Skan return 1; 1607132718Skan } 1608132718Skan return 0; 1609132718Skan} 1610132718Skan 161190075Sobrien/* Calculate INSN_REG_WEIGHT for all insns of a block. */ 161250397Sobrien 161350397Sobrienstatic void 1614169689Skanfind_insn_reg_weight (basic_block bb) 161550397Sobrien{ 161650397Sobrien rtx insn, next_tail, head, tail; 161750397Sobrien 1618169689Skan get_ebb_head_tail (bb, bb, &head, &tail); 161950397Sobrien next_tail = NEXT_INSN (tail); 162050397Sobrien 162150397Sobrien for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 1622169689Skan find_insn_reg_weight1 (insn); 1623169689Skan} 1624169689Skan 1625169689Skan/* Calculate INSN_REG_WEIGHT for single instruction. 1626169689Skan Separated from find_insn_reg_weight because of need 1627169689Skan to initialize new instruction in generate_recovery_code. */ 1628169689Skanstatic void 1629169689Skanfind_insn_reg_weight1 (rtx insn) 1630169689Skan{ 1631169689Skan int reg_weight = 0; 1632169689Skan rtx x; 1633169689Skan 1634169689Skan /* Handle register life information. */ 1635169689Skan if (! INSN_P (insn)) 1636169689Skan return; 1637169689Skan 1638169689Skan /* Increment weight for each register born here. */ 1639169689Skan x = PATTERN (insn); 1640169689Skan reg_weight += find_set_reg_weight (x); 1641169689Skan if (GET_CODE (x) == PARALLEL) 164250397Sobrien { 1643169689Skan int j; 1644169689Skan for (j = XVECLEN (x, 0) - 1; j >= 0; j--) 164550397Sobrien { 1646169689Skan x = XVECEXP (PATTERN (insn), 0, j); 1647169689Skan reg_weight += find_set_reg_weight (x); 164850397Sobrien } 164950397Sobrien } 1650169689Skan /* Decrement weight for each register that dies here. */ 1651169689Skan for (x = REG_NOTES (insn); x; x = XEXP (x, 1)) 1652169689Skan { 1653169689Skan if (REG_NOTE_KIND (x) == REG_DEAD 1654169689Skan || REG_NOTE_KIND (x) == REG_UNUSED) 1655169689Skan reg_weight--; 1656169689Skan } 1657169689Skan 1658169689Skan INSN_REG_WEIGHT (insn) = reg_weight; 165950397Sobrien} 166050397Sobrien 166150397Sobrien/* Move insns that became ready to fire from queue to ready list. */ 166250397Sobrien 166390075Sobrienstatic void 1664132718Skanqueue_to_ready (struct ready_list *ready) 166550397Sobrien{ 166650397Sobrien rtx insn; 166750397Sobrien rtx link; 166850397Sobrien 166950397Sobrien q_ptr = NEXT_Q (q_ptr); 167050397Sobrien 167150397Sobrien /* Add all pending insns that can be scheduled without stalls to the 167250397Sobrien ready list. */ 167350397Sobrien for (link = insn_queue[q_ptr]; link; link = XEXP (link, 1)) 167450397Sobrien { 167550397Sobrien insn = XEXP (link, 0); 167650397Sobrien q_size -= 1; 167750397Sobrien 167850397Sobrien if (sched_verbose >= 2) 167990075Sobrien fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", 168090075Sobrien (*current_sched_info->print_insn) (insn, 0)); 168150397Sobrien 1682169689Skan /* If the ready list is full, delay the insn for 1 cycle. 1683169689Skan See the comment in schedule_block for the rationale. */ 1684169689Skan if (!reload_completed 1685169689Skan && ready->n_ready > MAX_SCHED_READY_INSNS 1686169689Skan && !SCHED_GROUP_P (insn)) 1687169689Skan { 1688169689Skan if (sched_verbose >= 2) 1689169689Skan fprintf (sched_dump, "requeued because ready full\n"); 1690169689Skan queue_insn (insn, 1); 1691169689Skan } 1692169689Skan else 1693169689Skan { 1694169689Skan ready_add (ready, insn, false); 1695169689Skan if (sched_verbose >= 2) 1696169689Skan fprintf (sched_dump, "moving to ready without stalls\n"); 1697169689Skan } 169850397Sobrien } 1699169689Skan free_INSN_LIST_list (&insn_queue[q_ptr]); 170050397Sobrien 170150397Sobrien /* If there are no ready insns, stall until one is ready and add all 170250397Sobrien of the pending insns at that point to the ready list. */ 170390075Sobrien if (ready->n_ready == 0) 170450397Sobrien { 170590075Sobrien int stalls; 170650397Sobrien 1707169689Skan for (stalls = 1; stalls <= max_insn_queue_index; stalls++) 170850397Sobrien { 170950397Sobrien if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])) 171050397Sobrien { 171150397Sobrien for (; link; link = XEXP (link, 1)) 171250397Sobrien { 171350397Sobrien insn = XEXP (link, 0); 171450397Sobrien q_size -= 1; 171550397Sobrien 171650397Sobrien if (sched_verbose >= 2) 171790075Sobrien fprintf (sched_dump, ";;\t\tQ-->Ready: insn %s: ", 171890075Sobrien (*current_sched_info->print_insn) (insn, 0)); 171950397Sobrien 1720169689Skan ready_add (ready, insn, false); 172150397Sobrien if (sched_verbose >= 2) 172290075Sobrien fprintf (sched_dump, "moving to ready with %d stalls\n", stalls); 172350397Sobrien } 1724169689Skan free_INSN_LIST_list (&insn_queue[NEXT_Q_AFTER (q_ptr, stalls)]); 172550397Sobrien 1726117395Skan advance_one_cycle (); 1727117395Skan 1728117395Skan break; 172950397Sobrien } 1730117395Skan 1731117395Skan advance_one_cycle (); 173250397Sobrien } 173350397Sobrien 173450397Sobrien q_ptr = NEXT_Q_AFTER (q_ptr, stalls); 173550397Sobrien clock_var += stalls; 173650397Sobrien } 173750397Sobrien} 173850397Sobrien 1739132718Skan/* Used by early_queue_to_ready. Determines whether it is "ok" to 1740132718Skan prematurely move INSN from the queue to the ready list. Currently, 1741132718Skan if a target defines the hook 'is_costly_dependence', this function 1742132718Skan uses the hook to check whether there exist any dependences which are 1743132718Skan considered costly by the target, between INSN and other insns that 1744132718Skan have already been scheduled. Dependences are checked up to Y cycles 1745132718Skan back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows 1746132718Skan controlling this value. 1747132718Skan (Other considerations could be taken into account instead (or in 1748132718Skan addition) depending on user flags and target hooks. */ 1749132718Skan 1750132718Skanstatic bool 1751132718Skanok_for_early_queue_removal (rtx insn) 1752132718Skan{ 1753132718Skan int n_cycles; 1754132718Skan rtx prev_insn = last_scheduled_insn; 1755132718Skan 1756132718Skan if (targetm.sched.is_costly_dependence) 1757132718Skan { 1758132718Skan for (n_cycles = flag_sched_stalled_insns_dep; n_cycles; n_cycles--) 1759132718Skan { 1760132718Skan for ( ; prev_insn; prev_insn = PREV_INSN (prev_insn)) 1761132718Skan { 1762132718Skan rtx dep_link = 0; 1763132718Skan int dep_cost; 1764132718Skan 1765169689Skan if (!NOTE_P (prev_insn)) 1766132718Skan { 1767132718Skan dep_link = find_insn_list (insn, INSN_DEPEND (prev_insn)); 1768132718Skan if (dep_link) 1769132718Skan { 1770132718Skan dep_cost = insn_cost (prev_insn, dep_link, insn) ; 1771132718Skan if (targetm.sched.is_costly_dependence (prev_insn, insn, 1772132718Skan dep_link, dep_cost, 1773132718Skan flag_sched_stalled_insns_dep - n_cycles)) 1774132718Skan return false; 1775132718Skan } 1776132718Skan } 1777132718Skan 1778132718Skan if (GET_MODE (prev_insn) == TImode) /* end of dispatch group */ 1779132718Skan break; 1780132718Skan } 1781132718Skan 1782132718Skan if (!prev_insn) 1783132718Skan break; 1784132718Skan prev_insn = PREV_INSN (prev_insn); 1785132718Skan } 1786132718Skan } 1787132718Skan 1788132718Skan return true; 1789132718Skan} 1790132718Skan 1791132718Skan 1792132718Skan/* Remove insns from the queue, before they become "ready" with respect 1793132718Skan to FU latency considerations. */ 1794132718Skan 1795132718Skanstatic int 1796132718Skanearly_queue_to_ready (state_t state, struct ready_list *ready) 1797132718Skan{ 1798132718Skan rtx insn; 1799132718Skan rtx link; 1800132718Skan rtx next_link; 1801132718Skan rtx prev_link; 1802132718Skan bool move_to_ready; 1803132718Skan int cost; 1804132718Skan state_t temp_state = alloca (dfa_state_size); 1805132718Skan int stalls; 1806132718Skan int insns_removed = 0; 1807132718Skan 1808132718Skan /* 1809132718Skan Flag '-fsched-stalled-insns=X' determines the aggressiveness of this 1810132718Skan function: 1811132718Skan 1812132718Skan X == 0: There is no limit on how many queued insns can be removed 1813132718Skan prematurely. (flag_sched_stalled_insns = -1). 1814132718Skan 1815132718Skan X >= 1: Only X queued insns can be removed prematurely in each 1816132718Skan invocation. (flag_sched_stalled_insns = X). 1817132718Skan 1818132718Skan Otherwise: Early queue removal is disabled. 1819132718Skan (flag_sched_stalled_insns = 0) 1820132718Skan */ 1821132718Skan 1822132718Skan if (! flag_sched_stalled_insns) 1823132718Skan return 0; 1824132718Skan 1825169689Skan for (stalls = 0; stalls <= max_insn_queue_index; stalls++) 1826132718Skan { 1827132718Skan if ((link = insn_queue[NEXT_Q_AFTER (q_ptr, stalls)])) 1828132718Skan { 1829132718Skan if (sched_verbose > 6) 1830132718Skan fprintf (sched_dump, ";; look at index %d + %d\n", q_ptr, stalls); 1831132718Skan 1832132718Skan prev_link = 0; 1833132718Skan while (link) 1834132718Skan { 1835132718Skan next_link = XEXP (link, 1); 1836132718Skan insn = XEXP (link, 0); 1837132718Skan if (insn && sched_verbose > 6) 1838132718Skan print_rtl_single (sched_dump, insn); 1839132718Skan 1840132718Skan memcpy (temp_state, state, dfa_state_size); 1841132718Skan if (recog_memoized (insn) < 0) 1842132718Skan /* non-negative to indicate that it's not ready 1843132718Skan to avoid infinite Q->R->Q->R... */ 1844132718Skan cost = 0; 1845132718Skan else 1846132718Skan cost = state_transition (temp_state, insn); 1847132718Skan 1848132718Skan if (sched_verbose >= 6) 1849132718Skan fprintf (sched_dump, "transition cost = %d\n", cost); 1850132718Skan 1851132718Skan move_to_ready = false; 1852132718Skan if (cost < 0) 1853132718Skan { 1854132718Skan move_to_ready = ok_for_early_queue_removal (insn); 1855132718Skan if (move_to_ready == true) 1856132718Skan { 1857132718Skan /* move from Q to R */ 1858132718Skan q_size -= 1; 1859169689Skan ready_add (ready, insn, false); 1860132718Skan 1861132718Skan if (prev_link) 1862132718Skan XEXP (prev_link, 1) = next_link; 1863132718Skan else 1864132718Skan insn_queue[NEXT_Q_AFTER (q_ptr, stalls)] = next_link; 1865132718Skan 1866132718Skan free_INSN_LIST_node (link); 1867132718Skan 1868132718Skan if (sched_verbose >= 2) 1869132718Skan fprintf (sched_dump, ";;\t\tEarly Q-->Ready: insn %s\n", 1870132718Skan (*current_sched_info->print_insn) (insn, 0)); 1871132718Skan 1872132718Skan insns_removed++; 1873132718Skan if (insns_removed == flag_sched_stalled_insns) 1874169689Skan /* Remove no more than flag_sched_stalled_insns insns 1875169689Skan from Q at a time. */ 1876132718Skan return insns_removed; 1877132718Skan } 1878132718Skan } 1879132718Skan 1880132718Skan if (move_to_ready == false) 1881132718Skan prev_link = link; 1882132718Skan 1883132718Skan link = next_link; 1884132718Skan } /* while link */ 1885132718Skan } /* if link */ 1886132718Skan 1887132718Skan } /* for stalls.. */ 1888132718Skan 1889132718Skan return insns_removed; 1890132718Skan} 1891132718Skan 1892132718Skan 189390075Sobrien/* Print the ready list for debugging purposes. Callable from debugger. */ 189450397Sobrien 189550397Sobrienstatic void 1896132718Skandebug_ready_list (struct ready_list *ready) 189750397Sobrien{ 189890075Sobrien rtx *p; 189950397Sobrien int i; 190050397Sobrien 190190075Sobrien if (ready->n_ready == 0) 1902117395Skan { 1903117395Skan fprintf (sched_dump, "\n"); 1904117395Skan return; 1905117395Skan } 190650397Sobrien 190790075Sobrien p = ready_lastpos (ready); 190890075Sobrien for (i = 0; i < ready->n_ready; i++) 190990075Sobrien fprintf (sched_dump, " %s", (*current_sched_info->print_insn) (p[i], 0)); 191090075Sobrien fprintf (sched_dump, "\n"); 191150397Sobrien} 191250397Sobrien 191390075Sobrien/* Search INSN for REG_SAVE_NOTE note pairs for 1914169689Skan NOTE_INSN_EHREGION_{BEG,END}; and convert them back into 191590075Sobrien NOTEs. The REG_SAVE_NOTE note following first one is contains the 191690075Sobrien saved value for NOTE_BLOCK_NUMBER which is useful for 1917169689Skan NOTE_INSN_EH_REGION_{BEG,END} NOTEs. */ 191850397Sobrien 1919169689Skanstatic void 1920169689Skanreemit_notes (rtx insn) 192150397Sobrien{ 1922169689Skan rtx note, last = insn; 192350397Sobrien 192450397Sobrien for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 192550397Sobrien { 192690075Sobrien if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) 192750397Sobrien { 192890075Sobrien enum insn_note note_type = INTVAL (XEXP (note, 0)); 192990075Sobrien 1930117395Skan last = emit_note_before (note_type, last); 193150397Sobrien remove_note (insn, note); 193250397Sobrien } 193350397Sobrien } 193450397Sobrien} 193550397Sobrien 1936169689Skan/* Move INSN. Reemit notes if needed. Update CFG, if needed. */ 1937169689Skanstatic void 1938169689Skanmove_insn (rtx insn) 1939169689Skan{ 1940169689Skan rtx last = last_scheduled_insn; 194150397Sobrien 1942169689Skan if (PREV_INSN (insn) != last) 1943169689Skan { 1944169689Skan basic_block bb; 1945169689Skan rtx note; 1946169689Skan int jump_p = 0; 194750397Sobrien 1948169689Skan bb = BLOCK_FOR_INSN (insn); 1949169689Skan 1950169689Skan /* BB_HEAD is either LABEL or NOTE. */ 1951169689Skan gcc_assert (BB_HEAD (bb) != insn); 195250397Sobrien 1953169689Skan if (BB_END (bb) == insn) 1954169689Skan /* If this is last instruction in BB, move end marker one 1955169689Skan instruction up. */ 1956169689Skan { 1957169689Skan /* Jumps are always placed at the end of basic block. */ 1958169689Skan jump_p = control_flow_insn_p (insn); 195950397Sobrien 1960169689Skan gcc_assert (!jump_p 1961169689Skan || ((current_sched_info->flags & SCHED_RGN) 1962169689Skan && IS_SPECULATION_BRANCHY_CHECK_P (insn)) 1963169689Skan || (current_sched_info->flags & SCHED_EBB)); 1964169689Skan 1965169689Skan gcc_assert (BLOCK_FOR_INSN (PREV_INSN (insn)) == bb); 196650397Sobrien 1967169689Skan BB_END (bb) = PREV_INSN (insn); 1968169689Skan } 1969132718Skan 1970169689Skan gcc_assert (BB_END (bb) != last); 1971169689Skan 1972169689Skan if (jump_p) 1973169689Skan /* We move the block note along with jump. */ 1974169689Skan { 1975169689Skan /* NT is needed for assertion below. */ 1976169689Skan rtx nt = current_sched_info->next_tail; 1977169689Skan 1978169689Skan note = NEXT_INSN (insn); 1979169689Skan while (NOTE_NOT_BB_P (note) && note != nt) 1980169689Skan note = NEXT_INSN (note); 1981169689Skan 1982169689Skan if (note != nt 1983169689Skan && (LABEL_P (note) 1984169689Skan || BARRIER_P (note))) 1985169689Skan note = NEXT_INSN (note); 1986169689Skan 1987169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); 1988169689Skan } 1989169689Skan else 1990169689Skan note = insn; 1991169689Skan 1992169689Skan NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (note); 1993169689Skan PREV_INSN (NEXT_INSN (note)) = PREV_INSN (insn); 1994169689Skan 1995169689Skan NEXT_INSN (note) = NEXT_INSN (last); 1996169689Skan PREV_INSN (NEXT_INSN (last)) = note; 1997169689Skan 1998169689Skan NEXT_INSN (last) = insn; 1999169689Skan PREV_INSN (insn) = last; 2000169689Skan 2001169689Skan bb = BLOCK_FOR_INSN (last); 2002169689Skan 2003169689Skan if (jump_p) 2004169689Skan { 2005169689Skan fix_jump_move (insn); 2006169689Skan 2007169689Skan if (BLOCK_FOR_INSN (insn) != bb) 2008169689Skan move_block_after_check (insn); 2009169689Skan 2010169689Skan gcc_assert (BB_END (bb) == last); 2011169689Skan } 2012169689Skan 2013169689Skan set_block_for_insn (insn, bb); 2014169689Skan 2015169689Skan /* Update BB_END, if needed. */ 2016169689Skan if (BB_END (bb) == last) 2017169689Skan BB_END (bb) = insn; 2018169689Skan } 2019169689Skan 2020169689Skan reemit_notes (insn); 2021169689Skan 2022169689Skan SCHED_GROUP_P (insn) = 0; 202350397Sobrien} 202450397Sobrien 2025117395Skan/* The following structure describe an entry of the stack of choices. */ 2026117395Skanstruct choice_entry 2027117395Skan{ 2028117395Skan /* Ordinal number of the issued insn in the ready queue. */ 2029117395Skan int index; 2030117395Skan /* The number of the rest insns whose issues we should try. */ 2031117395Skan int rest; 2032117395Skan /* The number of issued essential insns. */ 2033117395Skan int n; 2034117395Skan /* State after issuing the insn. */ 2035117395Skan state_t state; 2036117395Skan}; 2037117395Skan 2038117395Skan/* The following array is used to implement a stack of choices used in 2039117395Skan function max_issue. */ 2040117395Skanstatic struct choice_entry *choice_stack; 2041117395Skan 2042117395Skan/* The following variable value is number of essential insns issued on 2043117395Skan the current cycle. An insn is essential one if it changes the 2044117395Skan processors state. */ 2045117395Skanstatic int cycle_issued_insns; 2046117395Skan 2047117395Skan/* The following variable value is maximal number of tries of issuing 2048117395Skan insns for the first cycle multipass insn scheduling. We define 2049117395Skan this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE). We would not 2050117395Skan need this constraint if all real insns (with non-negative codes) 2051117395Skan had reservations because in this case the algorithm complexity is 2052117395Skan O(DFA_LOOKAHEAD**ISSUE_RATE). Unfortunately, the dfa descriptions 2053117395Skan might be incomplete and such insn might occur. For such 2054117395Skan descriptions, the complexity of algorithm (without the constraint) 2055117395Skan could achieve DFA_LOOKAHEAD ** N , where N is the queue length. */ 2056117395Skanstatic int max_lookahead_tries; 2057117395Skan 2058117395Skan/* The following value is value of hook 2059117395Skan `first_cycle_multipass_dfa_lookahead' at the last call of 2060117395Skan `max_issue'. */ 2061117395Skanstatic int cached_first_cycle_multipass_dfa_lookahead = 0; 2062117395Skan 2063117395Skan/* The following value is value of `issue_rate' at the last call of 2064117395Skan `sched_init'. */ 2065117395Skanstatic int cached_issue_rate = 0; 2066117395Skan 2067117395Skan/* The following function returns maximal (or close to maximal) number 2068117395Skan of insns which can be issued on the same cycle and one of which 2069117395Skan insns is insns with the best rank (the first insn in READY). To 2070117395Skan make this function tries different samples of ready insns. READY 2071117395Skan is current queue `ready'. Global array READY_TRY reflects what 2072169689Skan insns are already issued in this try. MAX_POINTS is the sum of points 2073169689Skan of all instructions in READY. The function stops immediately, 2074169689Skan if it reached the such a solution, that all instruction can be issued. 2075169689Skan INDEX will contain index of the best insn in READY. The following 2076169689Skan function is used only for first cycle multipass scheduling. */ 2077117395Skanstatic int 2078169689Skanmax_issue (struct ready_list *ready, int *index, int max_points) 2079117395Skan{ 2080169689Skan int n, i, all, n_ready, best, delay, tries_num, points = -1; 2081117395Skan struct choice_entry *top; 2082117395Skan rtx insn; 2083117395Skan 2084117395Skan best = 0; 2085117395Skan memcpy (choice_stack->state, curr_state, dfa_state_size); 2086117395Skan top = choice_stack; 2087117395Skan top->rest = cached_first_cycle_multipass_dfa_lookahead; 2088117395Skan top->n = 0; 2089117395Skan n_ready = ready->n_ready; 2090117395Skan for (all = i = 0; i < n_ready; i++) 2091117395Skan if (!ready_try [i]) 2092117395Skan all++; 2093117395Skan i = 0; 2094117395Skan tries_num = 0; 2095117395Skan for (;;) 2096117395Skan { 2097117395Skan if (top->rest == 0 || i >= n_ready) 2098117395Skan { 2099117395Skan if (top == choice_stack) 2100117395Skan break; 2101117395Skan if (best < top - choice_stack && ready_try [0]) 2102117395Skan { 2103117395Skan best = top - choice_stack; 2104117395Skan *index = choice_stack [1].index; 2105169689Skan points = top->n; 2106169689Skan if (top->n == max_points || best == all) 2107117395Skan break; 2108117395Skan } 2109117395Skan i = top->index; 2110117395Skan ready_try [i] = 0; 2111117395Skan top--; 2112117395Skan memcpy (curr_state, top->state, dfa_state_size); 2113117395Skan } 2114117395Skan else if (!ready_try [i]) 2115117395Skan { 2116117395Skan tries_num++; 2117117395Skan if (tries_num > max_lookahead_tries) 2118117395Skan break; 2119117395Skan insn = ready_element (ready, i); 2120117395Skan delay = state_transition (curr_state, insn); 2121117395Skan if (delay < 0) 2122117395Skan { 2123117395Skan if (state_dead_lock_p (curr_state)) 2124117395Skan top->rest = 0; 2125117395Skan else 2126117395Skan top->rest--; 2127117395Skan n = top->n; 2128117395Skan if (memcmp (top->state, curr_state, dfa_state_size) != 0) 2129169689Skan n += ISSUE_POINTS (insn); 2130117395Skan top++; 2131117395Skan top->rest = cached_first_cycle_multipass_dfa_lookahead; 2132117395Skan top->index = i; 2133117395Skan top->n = n; 2134117395Skan memcpy (top->state, curr_state, dfa_state_size); 2135117395Skan ready_try [i] = 1; 2136117395Skan i = -1; 2137117395Skan } 2138117395Skan } 2139117395Skan i++; 2140117395Skan } 2141117395Skan while (top != choice_stack) 2142117395Skan { 2143117395Skan ready_try [top->index] = 0; 2144117395Skan top--; 2145117395Skan } 2146169689Skan memcpy (curr_state, choice_stack->state, dfa_state_size); 2147169689Skan 2148169689Skan if (sched_verbose >= 4) 2149169689Skan fprintf (sched_dump, ";;\t\tChoosed insn : %s; points: %d/%d\n", 2150169689Skan (*current_sched_info->print_insn) (ready_element (ready, *index), 2151169689Skan 0), 2152169689Skan points, max_points); 2153169689Skan 2154117395Skan return best; 2155117395Skan} 2156117395Skan 2157117395Skan/* The following function chooses insn from READY and modifies 2158117395Skan *N_READY and READY. The following function is used only for first 2159117395Skan cycle multipass scheduling. */ 2160117395Skan 2161117395Skanstatic rtx 2162132718Skanchoose_ready (struct ready_list *ready) 2163117395Skan{ 2164117395Skan int lookahead = 0; 2165117395Skan 2166117395Skan if (targetm.sched.first_cycle_multipass_dfa_lookahead) 2167169689Skan lookahead = targetm.sched.first_cycle_multipass_dfa_lookahead (); 2168117395Skan if (lookahead <= 0 || SCHED_GROUP_P (ready_element (ready, 0))) 2169117395Skan return ready_remove_first (ready); 2170117395Skan else 2171117395Skan { 2172117395Skan /* Try to choose the better insn. */ 2173169689Skan int index = 0, i, n; 2174117395Skan rtx insn; 2175169689Skan int more_issue, max_points, try_data = 1, try_control = 1; 2176169689Skan 2177117395Skan if (cached_first_cycle_multipass_dfa_lookahead != lookahead) 2178117395Skan { 2179117395Skan cached_first_cycle_multipass_dfa_lookahead = lookahead; 2180117395Skan max_lookahead_tries = 100; 2181117395Skan for (i = 0; i < issue_rate; i++) 2182117395Skan max_lookahead_tries *= lookahead; 2183117395Skan } 2184117395Skan insn = ready_element (ready, 0); 2185117395Skan if (INSN_CODE (insn) < 0) 2186117395Skan return ready_remove_first (ready); 2187169689Skan 2188169689Skan if (spec_info 2189169689Skan && spec_info->flags & (PREFER_NON_DATA_SPEC 2190169689Skan | PREFER_NON_CONTROL_SPEC)) 2191169689Skan { 2192169689Skan for (i = 0, n = ready->n_ready; i < n; i++) 2193169689Skan { 2194169689Skan rtx x; 2195169689Skan ds_t s; 2196169689Skan 2197169689Skan x = ready_element (ready, i); 2198169689Skan s = TODO_SPEC (x); 2199169689Skan 2200169689Skan if (spec_info->flags & PREFER_NON_DATA_SPEC 2201169689Skan && !(s & DATA_SPEC)) 2202169689Skan { 2203169689Skan try_data = 0; 2204169689Skan if (!(spec_info->flags & PREFER_NON_CONTROL_SPEC) 2205169689Skan || !try_control) 2206169689Skan break; 2207169689Skan } 2208169689Skan 2209169689Skan if (spec_info->flags & PREFER_NON_CONTROL_SPEC 2210169689Skan && !(s & CONTROL_SPEC)) 2211169689Skan { 2212169689Skan try_control = 0; 2213169689Skan if (!(spec_info->flags & PREFER_NON_DATA_SPEC) || !try_data) 2214169689Skan break; 2215169689Skan } 2216169689Skan } 2217169689Skan } 2218169689Skan 2219169689Skan if ((!try_data && (TODO_SPEC (insn) & DATA_SPEC)) 2220169689Skan || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)) 2221169689Skan || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec 2222169689Skan && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard_spec 2223169689Skan (insn))) 2224169689Skan /* Discard speculative instruction that stands first in the ready 2225169689Skan list. */ 2226169689Skan { 2227169689Skan change_queue_index (insn, 1); 2228169689Skan return 0; 2229169689Skan } 2230169689Skan 2231169689Skan max_points = ISSUE_POINTS (insn); 2232169689Skan more_issue = issue_rate - cycle_issued_insns - 1; 2233169689Skan 2234117395Skan for (i = 1; i < ready->n_ready; i++) 2235117395Skan { 2236117395Skan insn = ready_element (ready, i); 2237132718Skan ready_try [i] 2238132718Skan = (INSN_CODE (insn) < 0 2239169689Skan || (!try_data && (TODO_SPEC (insn) & DATA_SPEC)) 2240169689Skan || (!try_control && (TODO_SPEC (insn) & CONTROL_SPEC)) 2241132718Skan || (targetm.sched.first_cycle_multipass_dfa_lookahead_guard 2242169689Skan && !targetm.sched.first_cycle_multipass_dfa_lookahead_guard 2243169689Skan (insn))); 2244169689Skan 2245169689Skan if (!ready_try [i] && more_issue-- > 0) 2246169689Skan max_points += ISSUE_POINTS (insn); 2247117395Skan } 2248169689Skan 2249169689Skan if (max_issue (ready, &index, max_points) == 0) 2250117395Skan return ready_remove_first (ready); 2251117395Skan else 2252117395Skan return ready_remove (ready, index); 2253117395Skan } 2254117395Skan} 2255117395Skan 2256169689Skan/* Use forward list scheduling to rearrange insns of block pointed to by 2257169689Skan TARGET_BB, possibly bringing insns from subsequent blocks in the same 2258169689Skan region. */ 225996263Sobrien 226090075Sobrienvoid 2261169689Skanschedule_block (basic_block *target_bb, int rgn_n_insns1) 226250397Sobrien{ 226390075Sobrien struct ready_list ready; 2264132718Skan int i, first_cycle_insn_p; 226550397Sobrien int can_issue_more; 2266117395Skan state_t temp_state = NULL; /* It is used for multipass scheduling. */ 2267132718Skan int sort_p, advance, start_clock_var; 226850397Sobrien 226990075Sobrien /* Head/tail info for this block. */ 227090075Sobrien rtx prev_head = current_sched_info->prev_head; 227190075Sobrien rtx next_tail = current_sched_info->next_tail; 227290075Sobrien rtx head = NEXT_INSN (prev_head); 227390075Sobrien rtx tail = PREV_INSN (next_tail); 227450397Sobrien 227550397Sobrien /* We used to have code to avoid getting parameters moved from hard 227650397Sobrien argument registers into pseudos. 227750397Sobrien 227850397Sobrien However, it was removed when it proved to be of marginal benefit 227950397Sobrien and caused problems because schedule_block and compute_forward_dependences 228050397Sobrien had different notions of what the "head" insn was. */ 228150397Sobrien 2282169689Skan gcc_assert (head != tail || INSN_P (head)); 228350397Sobrien 2284169689Skan added_recovery_block_p = false; 2285169689Skan 228690075Sobrien /* Debug info. */ 228750397Sobrien if (sched_verbose) 2288169689Skan dump_new_block_header (0, *target_bb, head, tail); 228950397Sobrien 2290169689Skan state_reset (curr_state); 229150397Sobrien 2292169689Skan /* Allocate the ready list. */ 2293169689Skan readyp = &ready; 2294169689Skan ready.vec = NULL; 2295169689Skan ready_try = NULL; 2296169689Skan choice_stack = NULL; 229750397Sobrien 2298169689Skan rgn_n_insns = -1; 2299169689Skan extend_ready (rgn_n_insns1 + 1); 2300169689Skan 230190075Sobrien ready.first = ready.veclen - 1; 230290075Sobrien ready.n_ready = 0; 230350397Sobrien 2304169689Skan /* It is used for first cycle multipass scheduling. */ 2305169689Skan temp_state = alloca (dfa_state_size); 2306117395Skan 230790075Sobrien if (targetm.sched.md_init) 2308169689Skan targetm.sched.md_init (sched_dump, sched_verbose, ready.veclen); 230950397Sobrien 231096263Sobrien /* We start inserting insns after PREV_HEAD. */ 231196263Sobrien last_scheduled_insn = prev_head; 231250397Sobrien 2313169689Skan gcc_assert (NOTE_P (last_scheduled_insn) 2314169689Skan && BLOCK_FOR_INSN (last_scheduled_insn) == *target_bb); 2315169689Skan 231690075Sobrien /* Initialize INSN_QUEUE. Q_SIZE is the total number of insns in the 231790075Sobrien queue. */ 231850397Sobrien q_ptr = 0; 231950397Sobrien q_size = 0; 232050397Sobrien 2321169689Skan insn_queue = alloca ((max_insn_queue_index + 1) * sizeof (rtx)); 2322169689Skan memset (insn_queue, 0, (max_insn_queue_index + 1) * sizeof (rtx)); 2323117395Skan 2324169689Skan /* Start just before the beginning of time. */ 2325169689Skan clock_var = -1; 2326169689Skan 2327169689Skan /* We need queue and ready lists and clock_var be initialized 2328169689Skan in try_ready () (which is called through init_ready_list ()). */ 2329169689Skan (*current_sched_info->init_ready_list) (); 2330169689Skan 2331169689Skan /* The algorithm is O(n^2) in the number of ready insns at any given 2332169689Skan time in the worst case. Before reload we are more likely to have 2333169689Skan big lists so truncate them to a reasonable size. */ 2334169689Skan if (!reload_completed && ready.n_ready > MAX_SCHED_READY_INSNS) 2335169689Skan { 2336169689Skan ready_sort (&ready); 2337169689Skan 2338169689Skan /* Find first free-standing insn past MAX_SCHED_READY_INSNS. */ 2339169689Skan for (i = MAX_SCHED_READY_INSNS; i < ready.n_ready; i++) 2340169689Skan if (!SCHED_GROUP_P (ready_element (&ready, i))) 2341169689Skan break; 2342169689Skan 2343169689Skan if (sched_verbose >= 2) 2344169689Skan { 2345169689Skan fprintf (sched_dump, 2346169689Skan ";;\t\tReady list on entry: %d insns\n", ready.n_ready); 2347169689Skan fprintf (sched_dump, 2348169689Skan ";;\t\t before reload => truncated to %d insns\n", i); 2349169689Skan } 2350169689Skan 2351169689Skan /* Delay all insns past it for 1 cycle. */ 2352169689Skan while (i < ready.n_ready) 2353169689Skan queue_insn (ready_remove (&ready, i), 1); 2354169689Skan } 2355169689Skan 2356169689Skan /* Now we can restore basic block notes and maintain precise cfg. */ 2357169689Skan restore_bb_notes (*target_bb); 2358169689Skan 2359117395Skan last_clock_var = -1; 2360117395Skan 2361132718Skan advance = 0; 236290075Sobrien 2363132718Skan sort_p = TRUE; 236490075Sobrien /* Loop until all the insns in BB are scheduled. */ 236590075Sobrien while ((*current_sched_info->schedule_more_p) ()) 236650397Sobrien { 2367132718Skan do 2368132718Skan { 2369132718Skan start_clock_var = clock_var; 237050397Sobrien 2371132718Skan clock_var++; 2372117395Skan 2373132718Skan advance_one_cycle (); 237450397Sobrien 2375132718Skan /* Add to the ready list all pending insns that can be issued now. 2376132718Skan If there are no ready insns, increment clock until one 2377132718Skan is ready and add all pending insns at that point to the ready 2378132718Skan list. */ 2379132718Skan queue_to_ready (&ready); 238050397Sobrien 2381169689Skan gcc_assert (ready.n_ready); 2382132718Skan 2383132718Skan if (sched_verbose >= 2) 2384132718Skan { 2385132718Skan fprintf (sched_dump, ";;\t\tReady list after queue_to_ready: "); 2386132718Skan debug_ready_list (&ready); 2387132718Skan } 2388132718Skan advance -= clock_var - start_clock_var; 2389132718Skan } 2390132718Skan while (advance > 0); 2391132718Skan 2392132718Skan if (sort_p) 239350397Sobrien { 2394132718Skan /* Sort the ready list based on priority. */ 2395132718Skan ready_sort (&ready); 2396132718Skan 2397132718Skan if (sched_verbose >= 2) 2398132718Skan { 2399132718Skan fprintf (sched_dump, ";;\t\tReady list after ready_sort: "); 2400132718Skan debug_ready_list (&ready); 2401132718Skan } 240250397Sobrien } 240350397Sobrien 240490075Sobrien /* Allow the target to reorder the list, typically for 240590075Sobrien better instruction bundling. */ 2406132718Skan if (sort_p && targetm.sched.reorder 2407132718Skan && (ready.n_ready == 0 2408132718Skan || !SCHED_GROUP_P (ready_element (&ready, 0)))) 240990075Sobrien can_issue_more = 2410169689Skan targetm.sched.reorder (sched_dump, sched_verbose, 2411169689Skan ready_lastpos (&ready), 2412169689Skan &ready.n_ready, clock_var); 241390075Sobrien else 241490075Sobrien can_issue_more = issue_rate; 241590075Sobrien 2416117395Skan first_cycle_insn_p = 1; 2417117395Skan cycle_issued_insns = 0; 2418117395Skan for (;;) 241950397Sobrien { 2420117395Skan rtx insn; 2421117395Skan int cost; 2422132718Skan bool asm_p = false; 242350397Sobrien 2424117395Skan if (sched_verbose >= 2) 2425117395Skan { 2426169689Skan fprintf (sched_dump, ";;\tReady list (t = %3d): ", 2427117395Skan clock_var); 2428117395Skan debug_ready_list (&ready); 2429117395Skan } 243050397Sobrien 2431169689Skan if (ready.n_ready == 0 2432169689Skan && can_issue_more 2433169689Skan && reload_completed) 2434117395Skan { 2435169689Skan /* Allow scheduling insns directly from the queue in case 2436169689Skan there's nothing better to do (ready list is empty) but 2437169689Skan there are still vacant dispatch slots in the current cycle. */ 2438169689Skan if (sched_verbose >= 6) 2439169689Skan fprintf(sched_dump,";;\t\tSecond chance\n"); 2440169689Skan memcpy (temp_state, curr_state, dfa_state_size); 2441169689Skan if (early_queue_to_ready (temp_state, &ready)) 2442169689Skan ready_sort (&ready); 2443117395Skan } 2444132718Skan 2445169689Skan if (ready.n_ready == 0 || !can_issue_more 2446169689Skan || state_dead_lock_p (curr_state) 2447169689Skan || !(*current_sched_info->schedule_more_p) ()) 2448169689Skan break; 2449132718Skan 2450169689Skan /* Select and remove the insn from the ready list. */ 2451169689Skan if (sort_p) 2452169689Skan { 2453169689Skan insn = choose_ready (&ready); 2454169689Skan if (!insn) 2455169689Skan continue; 2456169689Skan } 2457169689Skan else 2458169689Skan insn = ready_remove_first (&ready); 2459132718Skan 2460169689Skan if (targetm.sched.dfa_new_cycle 2461169689Skan && targetm.sched.dfa_new_cycle (sched_dump, sched_verbose, 2462169689Skan insn, last_clock_var, 2463169689Skan clock_var, &sort_p)) 2464169689Skan /* SORT_P is used by the target to override sorting 2465169689Skan of the ready list. This is needed when the target 2466169689Skan has modified its internal structures expecting that 2467169689Skan the insn will be issued next. As we need the insn 2468169689Skan to have the highest priority (so it will be returned by 2469169689Skan the ready_remove_first call above), we invoke 2470169689Skan ready_add (&ready, insn, true). 2471169689Skan But, still, there is one issue: INSN can be later 2472169689Skan discarded by scheduler's front end through 2473169689Skan current_sched_info->can_schedule_ready_p, hence, won't 2474169689Skan be issued next. */ 2475169689Skan { 2476169689Skan ready_add (&ready, insn, true); 2477169689Skan break; 2478169689Skan } 2479132718Skan 2480169689Skan sort_p = TRUE; 2481169689Skan memcpy (temp_state, curr_state, dfa_state_size); 2482169689Skan if (recog_memoized (insn) < 0) 2483169689Skan { 2484169689Skan asm_p = (GET_CODE (PATTERN (insn)) == ASM_INPUT 2485169689Skan || asm_noperands (PATTERN (insn)) >= 0); 2486169689Skan if (!first_cycle_insn_p && asm_p) 2487169689Skan /* This is asm insn which is tryed to be issued on the 2488169689Skan cycle not first. Issue it on the next cycle. */ 2489169689Skan cost = 1; 2490117395Skan else 2491169689Skan /* A USE insn, or something else we don't need to 2492169689Skan understand. We can't pass these directly to 2493169689Skan state_transition because it will trigger a 2494169689Skan fatal error for unrecognizable insns. */ 2495169689Skan cost = 0; 2496117395Skan } 2497169689Skan else 2498169689Skan { 2499169689Skan cost = state_transition (temp_state, insn); 2500169689Skan if (cost < 0) 2501169689Skan cost = 0; 2502169689Skan else if (cost == 0) 2503169689Skan cost = 1; 2504169689Skan } 2505117395Skan 250690075Sobrien if (cost >= 1) 250750397Sobrien { 250850397Sobrien queue_insn (insn, cost); 2509169689Skan if (SCHED_GROUP_P (insn)) 2510169689Skan { 2511169689Skan advance = cost; 2512169689Skan break; 2513169689Skan } 2514169689Skan 251590075Sobrien continue; 251650397Sobrien } 251750397Sobrien 2518169689Skan if (current_sched_info->can_schedule_ready_p 2519169689Skan && ! (*current_sched_info->can_schedule_ready_p) (insn)) 2520169689Skan /* We normally get here only if we don't want to move 2521169689Skan insn from the split block. */ 2522169689Skan { 2523169689Skan TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP; 2524169689Skan continue; 2525169689Skan } 252650397Sobrien 2527169689Skan /* DECISION is made. */ 2528169689Skan 2529169689Skan if (TODO_SPEC (insn) & SPECULATIVE) 2530169689Skan generate_recovery_code (insn); 253150397Sobrien 2532169689Skan if (control_flow_insn_p (last_scheduled_insn) 2533169689Skan /* This is used to to switch basic blocks by request 2534169689Skan from scheduler front-end (actually, sched-ebb.c only). 2535169689Skan This is used to process blocks with single fallthru 2536169689Skan edge. If succeeding block has jump, it [jump] will try 2537169689Skan move at the end of current bb, thus corrupting CFG. */ 2538169689Skan || current_sched_info->advance_target_bb (*target_bb, insn)) 2539117395Skan { 2540169689Skan *target_bb = current_sched_info->advance_target_bb 2541169689Skan (*target_bb, 0); 2542169689Skan 2543169689Skan if (sched_verbose) 2544169689Skan { 2545169689Skan rtx x; 2546169689Skan 2547169689Skan x = next_real_insn (last_scheduled_insn); 2548169689Skan gcc_assert (x); 2549169689Skan dump_new_block_header (1, *target_bb, x, tail); 2550169689Skan } 2551169689Skan 2552169689Skan last_scheduled_insn = bb_note (*target_bb); 2553117395Skan } 2554169689Skan 2555169689Skan /* Update counters, etc in the scheduler's front end. */ 2556169689Skan (*current_sched_info->begin_schedule_ready) (insn, 2557169689Skan last_scheduled_insn); 2558169689Skan 2559169689Skan move_insn (insn); 2560169689Skan last_scheduled_insn = insn; 2561169689Skan 2562169689Skan if (memcmp (curr_state, temp_state, dfa_state_size) != 0) 2563169689Skan { 2564169689Skan cycle_issued_insns++; 2565169689Skan memcpy (curr_state, temp_state, dfa_state_size); 2566169689Skan } 2567132718Skan 256890075Sobrien if (targetm.sched.variable_issue) 256990075Sobrien can_issue_more = 2570169689Skan targetm.sched.variable_issue (sched_dump, sched_verbose, 257190075Sobrien insn, can_issue_more); 2572102780Skan /* A naked CLOBBER or USE generates no instruction, so do 2573102780Skan not count them against the issue rate. */ 2574102780Skan else if (GET_CODE (PATTERN (insn)) != USE 2575102780Skan && GET_CODE (PATTERN (insn)) != CLOBBER) 257690075Sobrien can_issue_more--; 257750397Sobrien 2578169689Skan advance = schedule_insn (insn); 257950397Sobrien 2580132718Skan /* After issuing an asm insn we should start a new cycle. */ 2581132718Skan if (advance == 0 && asm_p) 2582132718Skan advance = 1; 2583132718Skan if (advance != 0) 2584132718Skan break; 2585132718Skan 2586117395Skan first_cycle_insn_p = 0; 2587117395Skan 2588132718Skan /* Sort the ready list based on priority. This must be 2589132718Skan redone here, as schedule_insn may have readied additional 2590132718Skan insns that will not be sorted correctly. */ 2591132718Skan if (ready.n_ready > 0) 2592132718Skan ready_sort (&ready); 2593132718Skan 2594132718Skan if (targetm.sched.reorder2 2595132718Skan && (ready.n_ready == 0 2596132718Skan || !SCHED_GROUP_P (ready_element (&ready, 0)))) 259790075Sobrien { 259890075Sobrien can_issue_more = 2599169689Skan targetm.sched.reorder2 (sched_dump, sched_verbose, 2600169689Skan ready.n_ready 2601169689Skan ? ready_lastpos (&ready) : NULL, 2602169689Skan &ready.n_ready, clock_var); 260350397Sobrien } 260450397Sobrien } 260550397Sobrien } 260650397Sobrien 260790075Sobrien /* Debug info. */ 260850397Sobrien if (sched_verbose) 260950397Sobrien { 261090075Sobrien fprintf (sched_dump, ";;\tReady list (final): "); 261190075Sobrien debug_ready_list (&ready); 261250397Sobrien } 261350397Sobrien 2614169689Skan if (current_sched_info->queue_must_finish_empty) 2615169689Skan /* Sanity check -- queue must be empty now. Meaningless if region has 2616169689Skan multiple bbs. */ 2617169689Skan gcc_assert (!q_size && !ready.n_ready); 2618169689Skan else 2619169689Skan { 2620169689Skan /* We must maintain QUEUE_INDEX between blocks in region. */ 2621169689Skan for (i = ready.n_ready - 1; i >= 0; i--) 2622169689Skan { 2623169689Skan rtx x; 2624169689Skan 2625169689Skan x = ready_element (&ready, i); 2626169689Skan QUEUE_INDEX (x) = QUEUE_NOWHERE; 2627169689Skan TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; 2628169689Skan } 262950397Sobrien 2630169689Skan if (q_size) 2631169689Skan for (i = 0; i <= max_insn_queue_index; i++) 2632169689Skan { 2633169689Skan rtx link; 2634169689Skan for (link = insn_queue[i]; link; link = XEXP (link, 1)) 2635169689Skan { 2636169689Skan rtx x; 263750397Sobrien 2638169689Skan x = XEXP (link, 0); 2639169689Skan QUEUE_INDEX (x) = QUEUE_NOWHERE; 2640169689Skan TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; 2641169689Skan } 2642169689Skan free_INSN_LIST_list (&insn_queue[i]); 2643169689Skan } 2644169689Skan } 2645169689Skan 2646169689Skan if (!current_sched_info->queue_must_finish_empty 2647169689Skan || added_recovery_block_p) 2648132718Skan { 2649132718Skan /* INSN_TICK (minimum clock tick at which the insn becomes 2650132718Skan ready) may be not correct for the insn in the subsequent 2651132718Skan blocks of the region. We should use a correct value of 2652132718Skan `clock_var' or modify INSN_TICK. It is better to keep 2653132718Skan clock_var value equal to 0 at the start of a basic block. 2654132718Skan Therefore we modify INSN_TICK here. */ 2655169689Skan fix_inter_tick (NEXT_INSN (prev_head), last_scheduled_insn); 2656132718Skan } 2657132718Skan 2658169689Skan if (targetm.sched.md_finish) 2659169689Skan targetm.sched.md_finish (sched_dump, sched_verbose); 2660169689Skan 2661169689Skan /* Update head/tail boundaries. */ 2662169689Skan head = NEXT_INSN (prev_head); 2663169689Skan tail = last_scheduled_insn; 2664169689Skan 266550397Sobrien /* Restore-other-notes: NOTE_LIST is the end of a chain of notes 266650397Sobrien previously found among the insns. Insert them at the beginning 266750397Sobrien of the insns. */ 266850397Sobrien if (note_list != 0) 266950397Sobrien { 2670169689Skan basic_block head_bb = BLOCK_FOR_INSN (head); 267150397Sobrien rtx note_head = note_list; 267250397Sobrien 267350397Sobrien while (PREV_INSN (note_head)) 267450397Sobrien { 2675169689Skan set_block_for_insn (note_head, head_bb); 267650397Sobrien note_head = PREV_INSN (note_head); 267750397Sobrien } 2678169689Skan /* In the above cycle we've missed this note: */ 2679169689Skan set_block_for_insn (note_head, head_bb); 268050397Sobrien 268150397Sobrien PREV_INSN (note_head) = PREV_INSN (head); 268250397Sobrien NEXT_INSN (PREV_INSN (head)) = note_head; 268350397Sobrien PREV_INSN (head) = note_list; 268450397Sobrien NEXT_INSN (note_list) = head; 268550397Sobrien head = note_head; 268650397Sobrien } 268750397Sobrien 268890075Sobrien /* Debugging. */ 268950397Sobrien if (sched_verbose) 269050397Sobrien { 269190075Sobrien fprintf (sched_dump, ";; total time = %d\n;; new head = %d\n", 269290075Sobrien clock_var, INSN_UID (head)); 269390075Sobrien fprintf (sched_dump, ";; new tail = %d\n\n", 269490075Sobrien INSN_UID (tail)); 269550397Sobrien } 269650397Sobrien 269790075Sobrien current_sched_info->head = head; 269890075Sobrien current_sched_info->tail = tail; 269950397Sobrien 270090075Sobrien free (ready.vec); 2701117395Skan 2702169689Skan free (ready_try); 2703169689Skan for (i = 0; i <= rgn_n_insns; i++) 2704169689Skan free (choice_stack [i].state); 2705169689Skan free (choice_stack); 270650397Sobrien} 270790075Sobrien 270890075Sobrien/* Set_priorities: compute priority of each insn in the block. */ 270950397Sobrien 271090075Sobrienint 2711132718Skanset_priorities (rtx head, rtx tail) 271250397Sobrien{ 271350397Sobrien rtx insn; 271450397Sobrien int n_insn; 2715132718Skan int sched_max_insns_priority = 2716132718Skan current_sched_info->sched_max_insns_priority; 271750397Sobrien rtx prev_head; 271850397Sobrien 271990075Sobrien if (head == tail && (! INSN_P (head))) 272050397Sobrien return 0; 272150397Sobrien 272250397Sobrien n_insn = 0; 2723169689Skan 2724169689Skan prev_head = PREV_INSN (head); 272550397Sobrien for (insn = tail; insn != prev_head; insn = PREV_INSN (insn)) 272650397Sobrien { 2727169689Skan if (!INSN_P (insn)) 272850397Sobrien continue; 272950397Sobrien 2730132718Skan n_insn++; 273150397Sobrien (void) priority (insn); 2732132718Skan 2733132718Skan if (INSN_PRIORITY_KNOWN (insn)) 2734132718Skan sched_max_insns_priority = 2735132718Skan MAX (sched_max_insns_priority, INSN_PRIORITY (insn)); 273650397Sobrien } 273750397Sobrien 2738169689Skan current_sched_info->sched_max_insns_priority = sched_max_insns_priority; 2739169689Skan 274050397Sobrien return n_insn; 274150397Sobrien} 274250397Sobrien 2743169689Skan/* Next LUID to assign to an instruction. */ 2744169689Skanstatic int luid; 274550397Sobrien 2746169689Skan/* Initialize some global state for the scheduler. */ 2747169689Skan 274852284Sobrienvoid 2749169689Skansched_init (void) 275050397Sobrien{ 2751117395Skan basic_block b; 275250397Sobrien rtx insn; 2753117395Skan int i; 275450397Sobrien 2755169689Skan /* Switch to working copy of sched_info. */ 2756169689Skan memcpy (¤t_sched_info_var, current_sched_info, 2757169689Skan sizeof (current_sched_info_var)); 2758169689Skan current_sched_info = ¤t_sched_info_var; 2759169689Skan 276090075Sobrien /* Disable speculative loads in their presence if cc0 defined. */ 276150397Sobrien#ifdef HAVE_cc0 276250397Sobrien flag_schedule_speculative_load = 0; 276350397Sobrien#endif 276450397Sobrien 276590075Sobrien /* Set dump and sched_verbose for the desired debugging output. If no 276690075Sobrien dump-file was specified, but -fsched-verbose=N (any N), print to stderr. 276790075Sobrien For -fsched-verbose=N, N>=10, print everything to stderr. */ 276850397Sobrien sched_verbose = sched_verbose_param; 276950397Sobrien if (sched_verbose_param == 0 && dump_file) 277050397Sobrien sched_verbose = 1; 277190075Sobrien sched_dump = ((sched_verbose_param >= 10 || !dump_file) 277290075Sobrien ? stderr : dump_file); 277350397Sobrien 2774169689Skan /* Initialize SPEC_INFO. */ 2775169689Skan if (targetm.sched.set_sched_flags) 2776169689Skan { 2777169689Skan spec_info = &spec_info_var; 2778169689Skan targetm.sched.set_sched_flags (spec_info); 2779169689Skan if (current_sched_info->flags & DO_SPECULATION) 2780169689Skan spec_info->weakness_cutoff = 2781169689Skan (PARAM_VALUE (PARAM_SCHED_SPEC_PROB_CUTOFF) * MAX_DEP_WEAK) / 100; 2782169689Skan else 2783169689Skan /* So we won't read anything accidentally. */ 2784169689Skan spec_info = 0; 2785169689Skan#ifdef ENABLE_CHECKING 2786169689Skan check_sched_flags (); 2787169689Skan#endif 2788169689Skan } 2789169689Skan else 2790169689Skan /* So we won't read anything accidentally. */ 2791169689Skan spec_info = 0; 2792169689Skan 279390075Sobrien /* Initialize issue_rate. */ 279490075Sobrien if (targetm.sched.issue_rate) 2795169689Skan issue_rate = targetm.sched.issue_rate (); 279690075Sobrien else 279790075Sobrien issue_rate = 1; 279850397Sobrien 2799117395Skan if (cached_issue_rate != issue_rate) 2800117395Skan { 2801117395Skan cached_issue_rate = issue_rate; 2802117395Skan /* To invalidate max_lookahead_tries: */ 2803117395Skan cached_first_cycle_multipass_dfa_lookahead = 0; 2804117395Skan } 2805117395Skan 2806169689Skan old_max_uid = 0; 2807169689Skan h_i_d = 0; 2808169689Skan extend_h_i_d (); 280950397Sobrien 2810117395Skan for (i = 0; i < old_max_uid; i++) 2811117395Skan { 2812169689Skan h_i_d[i].cost = -1; 2813169689Skan h_i_d[i].todo_spec = HARD_DEP; 2814169689Skan h_i_d[i].queue_index = QUEUE_NOWHERE; 2815169689Skan h_i_d[i].tick = INVALID_TICK; 2816169689Skan h_i_d[i].inter_tick = INVALID_TICK; 2817169689Skan } 2818132718Skan 2819169689Skan if (targetm.sched.init_dfa_pre_cycle_insn) 2820169689Skan targetm.sched.init_dfa_pre_cycle_insn (); 2821132718Skan 2822169689Skan if (targetm.sched.init_dfa_post_cycle_insn) 2823169689Skan targetm.sched.init_dfa_post_cycle_insn (); 2824132718Skan 2825169689Skan dfa_start (); 2826169689Skan dfa_state_size = state_size (); 2827169689Skan curr_state = xmalloc (dfa_state_size); 2828117395Skan 282990075Sobrien h_i_d[0].luid = 0; 283090075Sobrien luid = 1; 2831117395Skan FOR_EACH_BB (b) 2832132718Skan for (insn = BB_HEAD (b); ; insn = NEXT_INSN (insn)) 283350397Sobrien { 283490075Sobrien INSN_LUID (insn) = luid; 283550397Sobrien 283690075Sobrien /* Increment the next luid, unless this is a note. We don't 283790075Sobrien really need separate IDs for notes and we don't want to 283890075Sobrien schedule differently depending on whether or not there are 283990075Sobrien line-number notes, i.e., depending on whether or not we're 284090075Sobrien generating debugging information. */ 2841169689Skan if (!NOTE_P (insn)) 284290075Sobrien ++luid; 284390075Sobrien 2844132718Skan if (insn == BB_END (b)) 284550397Sobrien break; 284650397Sobrien } 284750397Sobrien 284890075Sobrien init_dependency_caches (luid); 284950397Sobrien 285050397Sobrien init_alias_analysis (); 285150397Sobrien 2852169689Skan line_note_head = 0; 2853169689Skan old_last_basic_block = 0; 2854169689Skan glat_start = 0; 2855169689Skan glat_end = 0; 2856169689Skan extend_bb (0); 2857169689Skan 2858169689Skan if (current_sched_info->flags & USE_GLAT) 2859169689Skan init_glat (); 2860169689Skan 2861169689Skan /* Compute INSN_REG_WEIGHT for all blocks. We must do this before 2862169689Skan removing death notes. */ 2863169689Skan FOR_EACH_BB_REVERSE (b) 2864169689Skan find_insn_reg_weight (b); 2865169689Skan 2866169689Skan if (targetm.sched.md_init_global) 2867169689Skan targetm.sched.md_init_global (sched_dump, sched_verbose, old_max_uid); 2868169689Skan 2869169689Skan nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0; 2870169689Skan before_recovery = 0; 2871169689Skan 2872169689Skan#ifdef ENABLE_CHECKING 2873169689Skan /* This is used preferably for finding bugs in check_cfg () itself. */ 2874169689Skan check_cfg (0, 0); 2875169689Skan#endif 2876169689Skan} 2877169689Skan 2878169689Skan/* Free global data used during insn scheduling. */ 2879169689Skan 2880169689Skanvoid 2881169689Skansched_finish (void) 2882169689Skan{ 2883169689Skan free (h_i_d); 2884169689Skan free (curr_state); 2885169689Skan dfa_finish (); 2886169689Skan free_dependency_caches (); 2887169689Skan end_alias_analysis (); 2888169689Skan free (line_note_head); 2889169689Skan free_glat (); 2890169689Skan 2891169689Skan if (targetm.sched.md_finish_global) 2892169689Skan targetm.sched.md_finish_global (sched_dump, sched_verbose); 2893169689Skan 2894169689Skan if (spec_info && spec_info->dump) 289550397Sobrien { 2896169689Skan char c = reload_completed ? 'a' : 'b'; 289750397Sobrien 2898169689Skan fprintf (spec_info->dump, 2899169689Skan ";; %s:\n", current_function_name ()); 290050397Sobrien 2901169689Skan fprintf (spec_info->dump, 2902169689Skan ";; Procedure %cr-begin-data-spec motions == %d\n", 2903169689Skan c, nr_begin_data); 2904169689Skan fprintf (spec_info->dump, 2905169689Skan ";; Procedure %cr-be-in-data-spec motions == %d\n", 2906169689Skan c, nr_be_in_data); 2907169689Skan fprintf (spec_info->dump, 2908169689Skan ";; Procedure %cr-begin-control-spec motions == %d\n", 2909169689Skan c, nr_begin_control); 2910169689Skan fprintf (spec_info->dump, 2911169689Skan ";; Procedure %cr-be-in-control-spec motions == %d\n", 2912169689Skan c, nr_be_in_control); 2913169689Skan } 291450397Sobrien 2915169689Skan#ifdef ENABLE_CHECKING 2916169689Skan /* After reload ia64 backend clobbers CFG, so can't check anything. */ 2917169689Skan if (!reload_completed) 2918169689Skan check_cfg (0, 0); 2919169689Skan#endif 2920169689Skan 2921169689Skan current_sched_info = NULL; 2922169689Skan} 2923169689Skan 2924169689Skan/* Fix INSN_TICKs of the instructions in the current block as well as 2925169689Skan INSN_TICKs of their dependents. 2926169689Skan HEAD and TAIL are the begin and the end of the current scheduled block. */ 2927169689Skanstatic void 2928169689Skanfix_inter_tick (rtx head, rtx tail) 2929169689Skan{ 2930169689Skan /* Set of instructions with corrected INSN_TICK. */ 2931169689Skan bitmap_head processed; 2932169689Skan int next_clock = clock_var + 1; 2933169689Skan 2934169689Skan bitmap_initialize (&processed, 0); 2935169689Skan 2936169689Skan /* Iterates over scheduled instructions and fix their INSN_TICKs and 2937169689Skan INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent 2938169689Skan across different blocks. */ 2939169689Skan for (tail = NEXT_INSN (tail); head != tail; head = NEXT_INSN (head)) 2940169689Skan { 2941169689Skan if (INSN_P (head)) 294290075Sobrien { 2943169689Skan int tick; 2944169689Skan rtx link; 2945169689Skan 2946169689Skan tick = INSN_TICK (head); 2947169689Skan gcc_assert (tick >= MIN_TICK); 2948169689Skan 2949169689Skan /* Fix INSN_TICK of instruction from just scheduled block. */ 2950169689Skan if (!bitmap_bit_p (&processed, INSN_LUID (head))) 295150397Sobrien { 2952169689Skan bitmap_set_bit (&processed, INSN_LUID (head)); 2953169689Skan tick -= next_clock; 2954169689Skan 2955169689Skan if (tick < MIN_TICK) 2956169689Skan tick = MIN_TICK; 2957169689Skan 2958169689Skan INSN_TICK (head) = tick; 2959169689Skan } 2960169689Skan 2961169689Skan for (link = INSN_DEPEND (head); link; link = XEXP (link, 1)) 2962169689Skan { 2963169689Skan rtx next; 2964169689Skan 2965169689Skan next = XEXP (link, 0); 2966169689Skan tick = INSN_TICK (next); 2967169689Skan 2968169689Skan if (tick != INVALID_TICK 2969169689Skan /* If NEXT has its INSN_TICK calculated, fix it. 2970169689Skan If not - it will be properly calculated from 2971169689Skan scratch later in fix_tick_ready. */ 2972169689Skan && !bitmap_bit_p (&processed, INSN_LUID (next))) 2973169689Skan { 2974169689Skan bitmap_set_bit (&processed, INSN_LUID (next)); 2975169689Skan tick -= next_clock; 2976169689Skan 2977169689Skan if (tick < MIN_TICK) 2978169689Skan tick = MIN_TICK; 2979169689Skan 2980169689Skan if (tick > INTER_TICK (next)) 2981169689Skan INTER_TICK (next) = tick; 2982169689Skan else 2983169689Skan tick = INTER_TICK (next); 2984169689Skan 2985169689Skan INSN_TICK (next) = tick; 2986169689Skan } 2987169689Skan } 2988169689Skan } 2989169689Skan } 2990169689Skan bitmap_clear (&processed); 2991169689Skan} 2992169689Skan 2993169689Skan/* Check if NEXT is ready to be added to the ready or queue list. 2994169689Skan If "yes", add it to the proper list. 2995169689Skan Returns: 2996169689Skan -1 - is not ready yet, 2997169689Skan 0 - added to the ready list, 2998169689Skan 0 < N - queued for N cycles. */ 2999169689Skanint 3000169689Skantry_ready (rtx next) 3001169689Skan{ 3002169689Skan ds_t old_ts, *ts; 3003169689Skan rtx link; 3004169689Skan 3005169689Skan ts = &TODO_SPEC (next); 3006169689Skan old_ts = *ts; 3007169689Skan 3008169689Skan gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP)) 3009169689Skan && ((old_ts & HARD_DEP) 3010169689Skan || (old_ts & SPECULATIVE))); 3011169689Skan 3012169689Skan if (!(current_sched_info->flags & DO_SPECULATION)) 3013169689Skan { 3014169689Skan if (!LOG_LINKS (next)) 3015169689Skan *ts &= ~HARD_DEP; 3016169689Skan } 3017169689Skan else 3018169689Skan { 3019169689Skan *ts &= ~SPECULATIVE & ~HARD_DEP; 3020169689Skan 3021169689Skan link = LOG_LINKS (next); 3022169689Skan if (link) 3023169689Skan { 3024169689Skan /* LOG_LINKS are maintained sorted. 3025169689Skan So if DEP_STATUS of the first dep is SPECULATIVE, 3026169689Skan than all other deps are speculative too. */ 3027169689Skan if (DEP_STATUS (link) & SPECULATIVE) 3028169689Skan { 3029169689Skan /* Now we've got NEXT with speculative deps only. 3030169689Skan 1. Look at the deps to see what we have to do. 3031169689Skan 2. Check if we can do 'todo'. */ 3032169689Skan *ts = DEP_STATUS (link) & SPECULATIVE; 3033169689Skan while ((link = XEXP (link, 1))) 3034169689Skan *ts = ds_merge (*ts, DEP_STATUS (link) & SPECULATIVE); 3035169689Skan 3036169689Skan if (dep_weak (*ts) < spec_info->weakness_cutoff) 3037169689Skan /* Too few points. */ 3038169689Skan *ts = (*ts & ~SPECULATIVE) | HARD_DEP; 3039169689Skan } 3040169689Skan else 3041169689Skan *ts |= HARD_DEP; 3042169689Skan } 3043169689Skan } 3044169689Skan 3045169689Skan if (*ts & HARD_DEP) 3046169689Skan gcc_assert (*ts == old_ts 3047169689Skan && QUEUE_INDEX (next) == QUEUE_NOWHERE); 3048169689Skan else if (current_sched_info->new_ready) 3049169689Skan *ts = current_sched_info->new_ready (next, *ts); 3050169689Skan 3051169689Skan /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might 3052169689Skan have its original pattern or changed (speculative) one. This is due 3053169689Skan to changing ebb in region scheduling. 3054169689Skan * But if (old_ts & SPECULATIVE), then we are pretty sure that insn 3055169689Skan has speculative pattern. 3056169689Skan 3057169689Skan We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because 3058169689Skan control-speculative NEXT could have been discarded by sched-rgn.c 3059169689Skan (the same case as when discarded by can_schedule_ready_p ()). */ 3060169689Skan 3061169689Skan if ((*ts & SPECULATIVE) 3062169689Skan /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't 3063169689Skan need to change anything. */ 3064169689Skan && *ts != old_ts) 3065169689Skan { 3066169689Skan int res; 3067169689Skan rtx new_pat; 3068169689Skan 3069169689Skan gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE)); 3070169689Skan 3071169689Skan res = speculate_insn (next, *ts, &new_pat); 3072169689Skan 3073169689Skan switch (res) 3074169689Skan { 3075169689Skan case -1: 3076169689Skan /* It would be nice to change DEP_STATUS of all dependences, 3077169689Skan which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP, 3078169689Skan so we won't reanalyze anything. */ 3079169689Skan *ts = (*ts & ~SPECULATIVE) | HARD_DEP; 3080169689Skan break; 3081169689Skan 3082169689Skan case 0: 3083169689Skan /* We follow the rule, that every speculative insn 3084169689Skan has non-null ORIG_PAT. */ 3085169689Skan if (!ORIG_PAT (next)) 3086169689Skan ORIG_PAT (next) = PATTERN (next); 3087169689Skan break; 3088169689Skan 3089169689Skan case 1: 3090169689Skan if (!ORIG_PAT (next)) 3091169689Skan /* If we gonna to overwrite the original pattern of insn, 3092169689Skan save it. */ 3093169689Skan ORIG_PAT (next) = PATTERN (next); 3094169689Skan 3095169689Skan change_pattern (next, new_pat); 3096169689Skan break; 3097169689Skan 3098169689Skan default: 3099169689Skan gcc_unreachable (); 3100169689Skan } 3101169689Skan } 3102169689Skan 3103169689Skan /* We need to restore pattern only if (*ts == 0), because otherwise it is 3104169689Skan either correct (*ts & SPECULATIVE), 3105169689Skan or we simply don't care (*ts & HARD_DEP). */ 3106169689Skan 3107169689Skan gcc_assert (!ORIG_PAT (next) 3108169689Skan || !IS_SPECULATION_BRANCHY_CHECK_P (next)); 3109169689Skan 3110169689Skan if (*ts & HARD_DEP) 3111169689Skan { 3112169689Skan /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because 3113169689Skan control-speculative NEXT could have been discarded by sched-rgn.c 3114169689Skan (the same case as when discarded by can_schedule_ready_p ()). */ 3115169689Skan /*gcc_assert (QUEUE_INDEX (next) == QUEUE_NOWHERE);*/ 3116169689Skan 3117169689Skan change_queue_index (next, QUEUE_NOWHERE); 3118169689Skan return -1; 3119169689Skan } 3120169689Skan else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next)) 3121169689Skan /* We should change pattern of every previously speculative 3122169689Skan instruction - and we determine if NEXT was speculative by using 3123169689Skan ORIG_PAT field. Except one case - speculation checks have ORIG_PAT 3124169689Skan pat too, so skip them. */ 3125169689Skan { 3126169689Skan change_pattern (next, ORIG_PAT (next)); 3127169689Skan ORIG_PAT (next) = 0; 3128169689Skan } 3129169689Skan 3130169689Skan if (sched_verbose >= 2) 3131169689Skan { 3132169689Skan int s = TODO_SPEC (next); 3133169689Skan 3134169689Skan fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s", 3135169689Skan (*current_sched_info->print_insn) (next, 0)); 3136169689Skan 3137169689Skan if (spec_info && spec_info->dump) 3138169689Skan { 3139169689Skan if (s & BEGIN_DATA) 3140169689Skan fprintf (spec_info->dump, "; data-spec;"); 3141169689Skan if (s & BEGIN_CONTROL) 3142169689Skan fprintf (spec_info->dump, "; control-spec;"); 3143169689Skan if (s & BE_IN_CONTROL) 3144169689Skan fprintf (spec_info->dump, "; in-control-spec;"); 3145169689Skan } 3146169689Skan 3147169689Skan fprintf (sched_dump, "\n"); 3148169689Skan } 3149169689Skan 3150169689Skan adjust_priority (next); 3151169689Skan 3152169689Skan return fix_tick_ready (next); 3153169689Skan} 3154169689Skan 3155169689Skan/* Calculate INSN_TICK of NEXT and add it to either ready or queue list. */ 3156169689Skanstatic int 3157169689Skanfix_tick_ready (rtx next) 3158169689Skan{ 3159169689Skan rtx link; 3160169689Skan int tick, delay; 3161169689Skan 3162169689Skan link = RESOLVED_DEPS (next); 3163169689Skan 3164169689Skan if (link) 3165169689Skan { 3166169689Skan int full_p; 3167169689Skan 3168169689Skan tick = INSN_TICK (next); 3169169689Skan /* if tick is not equal to INVALID_TICK, then update 3170169689Skan INSN_TICK of NEXT with the most recent resolved dependence 3171169689Skan cost. Otherwise, recalculate from scratch. */ 3172169689Skan full_p = tick == INVALID_TICK; 3173169689Skan do 3174169689Skan { 3175169689Skan rtx pro; 3176169689Skan int tick1; 3177169689Skan 3178169689Skan pro = XEXP (link, 0); 3179169689Skan gcc_assert (INSN_TICK (pro) >= MIN_TICK); 3180169689Skan 3181169689Skan tick1 = INSN_TICK (pro) + insn_cost (pro, link, next); 3182169689Skan if (tick1 > tick) 3183169689Skan tick = tick1; 3184169689Skan } 3185169689Skan while ((link = XEXP (link, 1)) && full_p); 3186169689Skan } 3187169689Skan else 3188169689Skan tick = -1; 3189169689Skan 3190169689Skan INSN_TICK (next) = tick; 3191169689Skan 3192169689Skan delay = tick - clock_var; 3193169689Skan if (delay <= 0) 3194169689Skan delay = QUEUE_READY; 3195169689Skan 3196169689Skan change_queue_index (next, delay); 3197169689Skan 3198169689Skan return delay; 3199169689Skan} 3200169689Skan 3201169689Skan/* Move NEXT to the proper queue list with (DELAY >= 1), 3202169689Skan or add it to the ready list (DELAY == QUEUE_READY), 3203169689Skan or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE). */ 3204169689Skanstatic void 3205169689Skanchange_queue_index (rtx next, int delay) 3206169689Skan{ 3207169689Skan int i = QUEUE_INDEX (next); 3208169689Skan 3209169689Skan gcc_assert (QUEUE_NOWHERE <= delay && delay <= max_insn_queue_index 3210169689Skan && delay != 0); 3211169689Skan gcc_assert (i != QUEUE_SCHEDULED); 3212169689Skan 3213169689Skan if ((delay > 0 && NEXT_Q_AFTER (q_ptr, delay) == i) 3214169689Skan || (delay < 0 && delay == i)) 3215169689Skan /* We have nothing to do. */ 3216169689Skan return; 3217169689Skan 3218169689Skan /* Remove NEXT from wherever it is now. */ 3219169689Skan if (i == QUEUE_READY) 3220169689Skan ready_remove_insn (next); 3221169689Skan else if (i >= 0) 3222169689Skan queue_remove (next); 3223169689Skan 3224169689Skan /* Add it to the proper place. */ 3225169689Skan if (delay == QUEUE_READY) 3226169689Skan ready_add (readyp, next, false); 3227169689Skan else if (delay >= 1) 3228169689Skan queue_insn (next, delay); 3229169689Skan 3230169689Skan if (sched_verbose >= 2) 3231169689Skan { 3232169689Skan fprintf (sched_dump, ";;\t\ttick updated: insn %s", 3233169689Skan (*current_sched_info->print_insn) (next, 0)); 3234169689Skan 3235169689Skan if (delay == QUEUE_READY) 3236169689Skan fprintf (sched_dump, " into ready\n"); 3237169689Skan else if (delay >= 1) 3238169689Skan fprintf (sched_dump, " into queue with cost=%d\n", delay); 3239169689Skan else 3240169689Skan fprintf (sched_dump, " removed from ready or queue lists\n"); 3241169689Skan } 3242169689Skan} 3243169689Skan 3244169689Skan/* INSN is being scheduled. Resolve the dependence between INSN and NEXT. */ 3245169689Skanstatic void 3246169689Skanresolve_dep (rtx next, rtx insn) 3247169689Skan{ 3248169689Skan rtx dep; 3249169689Skan 3250169689Skan INSN_DEP_COUNT (next)--; 3251169689Skan 3252169689Skan dep = remove_list_elem (insn, &LOG_LINKS (next)); 3253169689Skan XEXP (dep, 1) = RESOLVED_DEPS (next); 3254169689Skan RESOLVED_DEPS (next) = dep; 3255169689Skan 3256169689Skan gcc_assert ((INSN_DEP_COUNT (next) != 0 || !LOG_LINKS (next)) 3257169689Skan && (LOG_LINKS (next) || INSN_DEP_COUNT (next) == 0)); 3258169689Skan} 3259169689Skan 3260169689Skan/* Extend H_I_D data. */ 3261169689Skanstatic void 3262169689Skanextend_h_i_d (void) 3263169689Skan{ 3264169689Skan /* We use LUID 0 for the fake insn (UID 0) which holds dependencies for 3265169689Skan pseudos which do not cross calls. */ 3266169689Skan int new_max_uid = get_max_uid() + 1; 3267169689Skan 3268169689Skan h_i_d = xrecalloc (h_i_d, new_max_uid, old_max_uid, sizeof (*h_i_d)); 3269169689Skan old_max_uid = new_max_uid; 3270169689Skan 3271169689Skan if (targetm.sched.h_i_d_extended) 3272169689Skan targetm.sched.h_i_d_extended (); 3273169689Skan} 3274169689Skan 3275169689Skan/* Extend READY, READY_TRY and CHOICE_STACK arrays. 3276169689Skan N_NEW_INSNS is the number of additional elements to allocate. */ 3277169689Skanstatic void 3278169689Skanextend_ready (int n_new_insns) 3279169689Skan{ 3280169689Skan int i; 3281169689Skan 3282169689Skan readyp->veclen = rgn_n_insns + n_new_insns + 1 + issue_rate; 3283169689Skan readyp->vec = XRESIZEVEC (rtx, readyp->vec, readyp->veclen); 3284169689Skan 3285169689Skan ready_try = xrecalloc (ready_try, rgn_n_insns + n_new_insns + 1, 3286169689Skan rgn_n_insns + 1, sizeof (char)); 3287169689Skan 3288169689Skan rgn_n_insns += n_new_insns; 3289169689Skan 3290169689Skan choice_stack = XRESIZEVEC (struct choice_entry, choice_stack, 3291169689Skan rgn_n_insns + 1); 3292169689Skan 3293169689Skan for (i = rgn_n_insns; n_new_insns--; i--) 3294169689Skan choice_stack[i].state = xmalloc (dfa_state_size); 3295169689Skan} 3296169689Skan 3297169689Skan/* Extend global scheduler structures (those, that live across calls to 3298169689Skan schedule_block) to include information about just emitted INSN. */ 3299169689Skanstatic void 3300169689Skanextend_global (rtx insn) 3301169689Skan{ 3302169689Skan gcc_assert (INSN_P (insn)); 3303169689Skan /* These structures have scheduler scope. */ 3304169689Skan extend_h_i_d (); 3305169689Skan init_h_i_d (insn); 3306169689Skan 3307169689Skan extend_dependency_caches (1, 0); 3308169689Skan} 3309169689Skan 3310169689Skan/* Extends global and local scheduler structures to include information 3311169689Skan about just emitted INSN. */ 3312169689Skanstatic void 3313169689Skanextend_all (rtx insn) 3314169689Skan{ 3315169689Skan extend_global (insn); 3316169689Skan 3317169689Skan /* These structures have block scope. */ 3318169689Skan extend_ready (1); 3319169689Skan 3320169689Skan (*current_sched_info->add_remove_insn) (insn, 0); 3321169689Skan} 3322169689Skan 3323169689Skan/* Initialize h_i_d entry of the new INSN with default values. 3324169689Skan Values, that are not explicitly initialized here, hold zero. */ 3325169689Skanstatic void 3326169689Skaninit_h_i_d (rtx insn) 3327169689Skan{ 3328169689Skan INSN_LUID (insn) = luid++; 3329169689Skan INSN_COST (insn) = -1; 3330169689Skan TODO_SPEC (insn) = HARD_DEP; 3331169689Skan QUEUE_INDEX (insn) = QUEUE_NOWHERE; 3332169689Skan INSN_TICK (insn) = INVALID_TICK; 3333169689Skan INTER_TICK (insn) = INVALID_TICK; 3334169689Skan find_insn_reg_weight1 (insn); 3335169689Skan} 3336169689Skan 3337169689Skan/* Generates recovery code for INSN. */ 3338169689Skanstatic void 3339169689Skangenerate_recovery_code (rtx insn) 3340169689Skan{ 3341169689Skan if (TODO_SPEC (insn) & BEGIN_SPEC) 3342169689Skan begin_speculative_block (insn); 3343169689Skan 3344169689Skan /* Here we have insn with no dependencies to 3345169689Skan instructions other then CHECK_SPEC ones. */ 3346169689Skan 3347169689Skan if (TODO_SPEC (insn) & BE_IN_SPEC) 3348169689Skan add_to_speculative_block (insn); 3349169689Skan} 3350169689Skan 3351169689Skan/* Helper function. 3352169689Skan Tries to add speculative dependencies of type FS between instructions 3353169689Skan in LINK list and TWIN. */ 3354169689Skanstatic void 3355169689Skanprocess_insn_depend_be_in_spec (rtx link, rtx twin, ds_t fs) 3356169689Skan{ 3357169689Skan for (; link; link = XEXP (link, 1)) 3358169689Skan { 3359169689Skan ds_t ds; 3360169689Skan rtx consumer; 3361169689Skan 3362169689Skan consumer = XEXP (link, 0); 3363169689Skan 3364169689Skan ds = DEP_STATUS (link); 3365169689Skan 3366169689Skan if (/* If we want to create speculative dep. */ 3367169689Skan fs 3368169689Skan /* And we can do that because this is a true dep. */ 3369169689Skan && (ds & DEP_TYPES) == DEP_TRUE) 3370169689Skan { 3371169689Skan gcc_assert (!(ds & BE_IN_SPEC)); 3372169689Skan 3373169689Skan if (/* If this dep can be overcome with 'begin speculation'. */ 3374169689Skan ds & BEGIN_SPEC) 3375169689Skan /* Then we have a choice: keep the dep 'begin speculative' 3376169689Skan or transform it into 'be in speculative'. */ 3377169689Skan { 3378169689Skan if (/* In try_ready we assert that if insn once became ready 3379169689Skan it can be removed from the ready (or queue) list only 3380169689Skan due to backend decision. Hence we can't let the 3381169689Skan probability of the speculative dep to decrease. */ 3382169689Skan dep_weak (ds) <= dep_weak (fs)) 3383169689Skan /* Transform it to be in speculative. */ 3384169689Skan ds = (ds & ~BEGIN_SPEC) | fs; 3385169689Skan } 3386169689Skan else 3387169689Skan /* Mark the dep as 'be in speculative'. */ 3388169689Skan ds |= fs; 3389169689Skan } 3390169689Skan 3391169689Skan add_back_forw_dep (consumer, twin, REG_NOTE_KIND (link), ds); 3392169689Skan } 3393169689Skan} 3394169689Skan 3395169689Skan/* Generates recovery code for BEGIN speculative INSN. */ 3396169689Skanstatic void 3397169689Skanbegin_speculative_block (rtx insn) 3398169689Skan{ 3399169689Skan if (TODO_SPEC (insn) & BEGIN_DATA) 3400169689Skan nr_begin_data++; 3401169689Skan if (TODO_SPEC (insn) & BEGIN_CONTROL) 3402169689Skan nr_begin_control++; 3403169689Skan 3404169689Skan create_check_block_twin (insn, false); 3405169689Skan 3406169689Skan TODO_SPEC (insn) &= ~BEGIN_SPEC; 3407169689Skan} 3408169689Skan 3409169689Skan/* Generates recovery code for BE_IN speculative INSN. */ 3410169689Skanstatic void 3411169689Skanadd_to_speculative_block (rtx insn) 3412169689Skan{ 3413169689Skan ds_t ts; 3414169689Skan rtx link, twins = NULL; 3415169689Skan 3416169689Skan ts = TODO_SPEC (insn); 3417169689Skan gcc_assert (!(ts & ~BE_IN_SPEC)); 3418169689Skan 3419169689Skan if (ts & BE_IN_DATA) 3420169689Skan nr_be_in_data++; 3421169689Skan if (ts & BE_IN_CONTROL) 3422169689Skan nr_be_in_control++; 3423169689Skan 3424169689Skan TODO_SPEC (insn) &= ~BE_IN_SPEC; 3425169689Skan gcc_assert (!TODO_SPEC (insn)); 3426169689Skan 3427169689Skan DONE_SPEC (insn) |= ts; 3428169689Skan 3429169689Skan /* First we convert all simple checks to branchy. */ 3430169689Skan for (link = LOG_LINKS (insn); link;) 3431169689Skan { 3432169689Skan rtx check; 3433169689Skan 3434169689Skan check = XEXP (link, 0); 3435169689Skan 3436169689Skan if (IS_SPECULATION_SIMPLE_CHECK_P (check)) 3437169689Skan { 3438169689Skan create_check_block_twin (check, true); 3439169689Skan link = LOG_LINKS (insn); 3440169689Skan } 3441169689Skan else 3442169689Skan link = XEXP (link, 1); 3443169689Skan } 3444169689Skan 3445169689Skan clear_priorities (insn); 3446169689Skan 3447169689Skan do 3448169689Skan { 3449169689Skan rtx link, check, twin; 3450169689Skan basic_block rec; 3451169689Skan 3452169689Skan link = LOG_LINKS (insn); 3453169689Skan gcc_assert (!(DEP_STATUS (link) & BEGIN_SPEC) 3454169689Skan && (DEP_STATUS (link) & BE_IN_SPEC) 3455169689Skan && (DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE); 3456169689Skan 3457169689Skan check = XEXP (link, 0); 3458169689Skan 3459169689Skan gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check) 3460169689Skan && QUEUE_INDEX (check) == QUEUE_NOWHERE); 3461169689Skan 3462169689Skan rec = BLOCK_FOR_INSN (check); 3463169689Skan 3464169689Skan twin = emit_insn_before (copy_rtx (PATTERN (insn)), BB_END (rec)); 3465169689Skan extend_global (twin); 3466169689Skan 3467169689Skan RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn)); 3468169689Skan 3469169689Skan if (sched_verbose && spec_info->dump) 3470169689Skan /* INSN_BB (insn) isn't determined for twin insns yet. 3471169689Skan So we can't use current_sched_info->print_insn. */ 3472169689Skan fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n", 3473169689Skan INSN_UID (twin), rec->index); 3474169689Skan 3475169689Skan twins = alloc_INSN_LIST (twin, twins); 3476169689Skan 3477169689Skan /* Add dependences between TWIN and all appropriate 3478169689Skan instructions from REC. */ 3479169689Skan do 3480169689Skan { 3481169689Skan add_back_forw_dep (twin, check, REG_DEP_TRUE, DEP_TRUE); 3482169689Skan 3483169689Skan do 3484169689Skan { 3485169689Skan link = XEXP (link, 1); 3486169689Skan if (link) 3487169689Skan { 3488169689Skan check = XEXP (link, 0); 3489169689Skan if (BLOCK_FOR_INSN (check) == rec) 3490169689Skan break; 3491169689Skan } 3492169689Skan else 349390075Sobrien break; 349450397Sobrien } 3495169689Skan while (1); 349690075Sobrien } 3497169689Skan while (link); 3498169689Skan 3499169689Skan process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, ts); 3500169689Skan 3501169689Skan for (link = LOG_LINKS (insn); link;) 3502169689Skan { 3503169689Skan check = XEXP (link, 0); 3504169689Skan 3505169689Skan if (BLOCK_FOR_INSN (check) == rec) 3506169689Skan { 3507169689Skan delete_back_forw_dep (insn, check); 3508169689Skan link = LOG_LINKS (insn); 3509169689Skan } 3510169689Skan else 3511169689Skan link = XEXP (link, 1); 3512169689Skan } 351350397Sobrien } 3514169689Skan while (LOG_LINKS (insn)); 351550397Sobrien 3516169689Skan /* We can't add the dependence between insn and twin earlier because 3517169689Skan that would make twin appear in the INSN_DEPEND (insn). */ 3518169689Skan while (twins) 3519169689Skan { 3520169689Skan rtx twin; 352150397Sobrien 3522169689Skan twin = XEXP (twins, 0); 3523169689Skan calc_priorities (twin); 3524169689Skan add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT); 352550397Sobrien 3526169689Skan twin = XEXP (twins, 1); 3527169689Skan free_INSN_LIST_node (twins); 3528169689Skan twins = twin; 3529169689Skan } 3530169689Skan} 3531169689Skan 3532169689Skan/* Extends and fills with zeros (only the new part) array pointed to by P. */ 3533169689Skanvoid * 3534169689Skanxrecalloc (void *p, size_t new_nmemb, size_t old_nmemb, size_t size) 3535169689Skan{ 3536169689Skan gcc_assert (new_nmemb >= old_nmemb); 3537169689Skan p = XRESIZEVAR (void, p, new_nmemb * size); 3538169689Skan memset (((char *) p) + old_nmemb * size, 0, (new_nmemb - old_nmemb) * size); 3539169689Skan return p; 3540169689Skan} 3541169689Skan 3542169689Skan/* Return the probability of speculation success for the speculation 3543169689Skan status DS. */ 3544169689Skanstatic dw_t 3545169689Skandep_weak (ds_t ds) 3546169689Skan{ 3547169689Skan ds_t res = 1, dt; 3548169689Skan int n = 0; 3549169689Skan 3550169689Skan dt = FIRST_SPEC_TYPE; 3551169689Skan do 3552169689Skan { 3553169689Skan if (ds & dt) 3554169689Skan { 3555169689Skan res *= (ds_t) get_dep_weak (ds, dt); 3556169689Skan n++; 3557169689Skan } 3558169689Skan 3559169689Skan if (dt == LAST_SPEC_TYPE) 3560169689Skan break; 3561169689Skan dt <<= SPEC_TYPE_SHIFT; 3562169689Skan } 3563169689Skan while (1); 3564169689Skan 3565169689Skan gcc_assert (n); 3566169689Skan while (--n) 3567169689Skan res /= MAX_DEP_WEAK; 3568169689Skan 3569169689Skan if (res < MIN_DEP_WEAK) 3570169689Skan res = MIN_DEP_WEAK; 3571169689Skan 3572169689Skan gcc_assert (res <= MAX_DEP_WEAK); 3573169689Skan 3574169689Skan return (dw_t) res; 3575169689Skan} 3576169689Skan 3577169689Skan/* Helper function. 3578169689Skan Find fallthru edge from PRED. */ 3579169689Skanstatic edge 3580169689Skanfind_fallthru_edge (basic_block pred) 3581169689Skan{ 3582169689Skan edge e; 3583169689Skan edge_iterator ei; 3584169689Skan basic_block succ; 3585169689Skan 3586169689Skan succ = pred->next_bb; 3587169689Skan gcc_assert (succ->prev_bb == pred); 3588169689Skan 3589169689Skan if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds)) 3590169689Skan { 3591169689Skan FOR_EACH_EDGE (e, ei, pred->succs) 3592169689Skan if (e->flags & EDGE_FALLTHRU) 3593169689Skan { 3594169689Skan gcc_assert (e->dest == succ); 3595169689Skan return e; 3596169689Skan } 3597169689Skan } 3598169689Skan else 3599169689Skan { 3600169689Skan FOR_EACH_EDGE (e, ei, succ->preds) 3601169689Skan if (e->flags & EDGE_FALLTHRU) 3602169689Skan { 3603169689Skan gcc_assert (e->src == pred); 3604169689Skan return e; 3605169689Skan } 3606169689Skan } 3607169689Skan 3608169689Skan return NULL; 3609169689Skan} 3610169689Skan 3611169689Skan/* Initialize BEFORE_RECOVERY variable. */ 3612169689Skanstatic void 3613169689Skaninit_before_recovery (void) 3614169689Skan{ 3615169689Skan basic_block last; 3616169689Skan edge e; 3617169689Skan 3618169689Skan last = EXIT_BLOCK_PTR->prev_bb; 3619169689Skan e = find_fallthru_edge (last); 3620169689Skan 3621169689Skan if (e) 3622169689Skan { 3623169689Skan /* We create two basic blocks: 3624169689Skan 1. Single instruction block is inserted right after E->SRC 3625169689Skan and has jump to 3626169689Skan 2. Empty block right before EXIT_BLOCK. 3627169689Skan Between these two blocks recovery blocks will be emitted. */ 3628169689Skan 3629169689Skan basic_block single, empty; 3630169689Skan rtx x, label; 3631169689Skan 3632169689Skan single = create_empty_bb (last); 3633169689Skan empty = create_empty_bb (single); 3634169689Skan 3635169689Skan single->count = last->count; 3636169689Skan empty->count = last->count; 3637169689Skan single->frequency = last->frequency; 3638169689Skan empty->frequency = last->frequency; 3639169689Skan BB_COPY_PARTITION (single, last); 3640169689Skan BB_COPY_PARTITION (empty, last); 3641169689Skan 3642169689Skan redirect_edge_succ (e, single); 3643169689Skan make_single_succ_edge (single, empty, 0); 3644169689Skan make_single_succ_edge (empty, EXIT_BLOCK_PTR, 3645169689Skan EDGE_FALLTHRU | EDGE_CAN_FALLTHRU); 3646169689Skan 3647169689Skan label = block_label (empty); 3648169689Skan x = emit_jump_insn_after (gen_jump (label), BB_END (single)); 3649169689Skan JUMP_LABEL (x) = label; 3650169689Skan LABEL_NUSES (label)++; 3651169689Skan extend_global (x); 3652169689Skan 3653169689Skan emit_barrier_after (x); 3654169689Skan 3655169689Skan add_block (empty, 0); 3656169689Skan add_block (single, 0); 3657169689Skan 3658169689Skan before_recovery = single; 3659169689Skan 3660169689Skan if (sched_verbose >= 2 && spec_info->dump) 3661169689Skan fprintf (spec_info->dump, 3662169689Skan ";;\t\tFixed fallthru to EXIT : %d->>%d->%d->>EXIT\n", 3663169689Skan last->index, single->index, empty->index); 3664169689Skan } 3665169689Skan else 3666169689Skan before_recovery = last; 3667169689Skan} 3668169689Skan 3669169689Skan/* Returns new recovery block. */ 3670169689Skanstatic basic_block 3671169689Skancreate_recovery_block (void) 3672169689Skan{ 3673169689Skan rtx label; 3674169689Skan rtx barrier; 3675169689Skan basic_block rec; 3676169689Skan 3677169689Skan added_recovery_block_p = true; 3678169689Skan 3679169689Skan if (!before_recovery) 3680169689Skan init_before_recovery (); 3681169689Skan 3682169689Skan barrier = get_last_bb_insn (before_recovery); 3683169689Skan gcc_assert (BARRIER_P (barrier)); 3684169689Skan 3685169689Skan label = emit_label_after (gen_label_rtx (), barrier); 3686169689Skan 3687169689Skan rec = create_basic_block (label, label, before_recovery); 3688169689Skan 3689169689Skan /* Recovery block always end with an unconditional jump. */ 3690169689Skan emit_barrier_after (BB_END (rec)); 3691169689Skan 3692169689Skan if (BB_PARTITION (before_recovery) != BB_UNPARTITIONED) 3693169689Skan BB_SET_PARTITION (rec, BB_COLD_PARTITION); 3694169689Skan 3695169689Skan if (sched_verbose && spec_info->dump) 3696169689Skan fprintf (spec_info->dump, ";;\t\tGenerated recovery block rec%d\n", 3697169689Skan rec->index); 3698169689Skan 3699169689Skan before_recovery = rec; 3700169689Skan 3701169689Skan return rec; 3702169689Skan} 3703169689Skan 3704169689Skan/* This function creates recovery code for INSN. If MUTATE_P is nonzero, 3705169689Skan INSN is a simple check, that should be converted to branchy one. */ 3706169689Skanstatic void 3707169689Skancreate_check_block_twin (rtx insn, bool mutate_p) 3708169689Skan{ 3709169689Skan basic_block rec; 3710169689Skan rtx label, check, twin, link; 3711169689Skan ds_t fs; 3712169689Skan 3713169689Skan gcc_assert (ORIG_PAT (insn) 3714169689Skan && (!mutate_p 3715169689Skan || (IS_SPECULATION_SIMPLE_CHECK_P (insn) 3716169689Skan && !(TODO_SPEC (insn) & SPECULATIVE)))); 3717169689Skan 3718169689Skan /* Create recovery block. */ 3719169689Skan if (mutate_p || targetm.sched.needs_block_p (insn)) 3720169689Skan { 3721169689Skan rec = create_recovery_block (); 3722169689Skan label = BB_HEAD (rec); 3723169689Skan } 3724169689Skan else 3725169689Skan { 3726169689Skan rec = EXIT_BLOCK_PTR; 3727169689Skan label = 0; 3728169689Skan } 3729169689Skan 3730169689Skan /* Emit CHECK. */ 3731169689Skan check = targetm.sched.gen_check (insn, label, mutate_p); 3732169689Skan 3733169689Skan if (rec != EXIT_BLOCK_PTR) 3734169689Skan { 3735169689Skan /* To have mem_reg alive at the beginning of second_bb, 3736169689Skan we emit check BEFORE insn, so insn after splitting 3737169689Skan insn will be at the beginning of second_bb, which will 3738169689Skan provide us with the correct life information. */ 3739169689Skan check = emit_jump_insn_before (check, insn); 3740169689Skan JUMP_LABEL (check) = label; 3741169689Skan LABEL_NUSES (label)++; 3742169689Skan } 3743169689Skan else 3744169689Skan check = emit_insn_before (check, insn); 3745169689Skan 3746169689Skan /* Extend data structures. */ 3747169689Skan extend_all (check); 3748169689Skan RECOVERY_BLOCK (check) = rec; 3749169689Skan 3750169689Skan if (sched_verbose && spec_info->dump) 3751169689Skan fprintf (spec_info->dump, ";;\t\tGenerated check insn : %s\n", 3752169689Skan (*current_sched_info->print_insn) (check, 0)); 3753169689Skan 3754169689Skan gcc_assert (ORIG_PAT (insn)); 3755169689Skan 3756169689Skan /* Initialize TWIN (twin is a duplicate of original instruction 3757169689Skan in the recovery block). */ 3758169689Skan if (rec != EXIT_BLOCK_PTR) 3759169689Skan { 3760169689Skan rtx link; 3761169689Skan 3762169689Skan for (link = RESOLVED_DEPS (insn); link; link = XEXP (link, 1)) 3763169689Skan if (DEP_STATUS (link) & DEP_OUTPUT) 3764169689Skan { 3765169689Skan RESOLVED_DEPS (check) = 3766169689Skan alloc_DEPS_LIST (XEXP (link, 0), RESOLVED_DEPS (check), DEP_TRUE); 3767169689Skan PUT_REG_NOTE_KIND (RESOLVED_DEPS (check), REG_DEP_TRUE); 3768169689Skan } 3769169689Skan 3770169689Skan twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec)); 3771169689Skan extend_global (twin); 3772169689Skan 3773169689Skan if (sched_verbose && spec_info->dump) 3774169689Skan /* INSN_BB (insn) isn't determined for twin insns yet. 3775169689Skan So we can't use current_sched_info->print_insn. */ 3776169689Skan fprintf (spec_info->dump, ";;\t\tGenerated twin insn : %d/rec%d\n", 3777169689Skan INSN_UID (twin), rec->index); 3778169689Skan } 3779169689Skan else 3780169689Skan { 3781169689Skan ORIG_PAT (check) = ORIG_PAT (insn); 3782169689Skan HAS_INTERNAL_DEP (check) = 1; 3783169689Skan twin = check; 3784169689Skan /* ??? We probably should change all OUTPUT dependencies to 3785169689Skan (TRUE | OUTPUT). */ 3786169689Skan } 3787169689Skan 3788169689Skan RESOLVED_DEPS (twin) = copy_DEPS_LIST_list (RESOLVED_DEPS (insn)); 3789169689Skan 3790169689Skan if (rec != EXIT_BLOCK_PTR) 3791169689Skan /* In case of branchy check, fix CFG. */ 3792169689Skan { 3793169689Skan basic_block first_bb, second_bb; 3794169689Skan rtx jump; 3795169689Skan edge e; 3796169689Skan int edge_flags; 3797169689Skan 3798169689Skan first_bb = BLOCK_FOR_INSN (check); 3799169689Skan e = split_block (first_bb, check); 3800169689Skan /* split_block emits note if *check == BB_END. Probably it 3801169689Skan is better to rip that note off. */ 3802169689Skan gcc_assert (e->src == first_bb); 3803169689Skan second_bb = e->dest; 3804169689Skan 3805169689Skan /* This is fixing of incoming edge. */ 3806169689Skan /* ??? Which other flags should be specified? */ 3807169689Skan if (BB_PARTITION (first_bb) != BB_PARTITION (rec)) 3808169689Skan /* Partition type is the same, if it is "unpartitioned". */ 3809169689Skan edge_flags = EDGE_CROSSING; 3810169689Skan else 3811169689Skan edge_flags = 0; 3812169689Skan 3813169689Skan e = make_edge (first_bb, rec, edge_flags); 3814169689Skan 3815169689Skan add_block (second_bb, first_bb); 3816169689Skan 3817169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (BB_HEAD (second_bb))); 3818169689Skan label = block_label (second_bb); 3819169689Skan jump = emit_jump_insn_after (gen_jump (label), BB_END (rec)); 3820169689Skan JUMP_LABEL (jump) = label; 3821169689Skan LABEL_NUSES (label)++; 3822169689Skan extend_global (jump); 3823169689Skan 3824169689Skan if (BB_PARTITION (second_bb) != BB_PARTITION (rec)) 3825169689Skan /* Partition type is the same, if it is "unpartitioned". */ 3826169689Skan { 3827169689Skan /* Rewritten from cfgrtl.c. */ 3828169689Skan if (flag_reorder_blocks_and_partition 3829169689Skan && targetm.have_named_sections 3830169689Skan /*&& !any_condjump_p (jump)*/) 3831169689Skan /* any_condjump_p (jump) == false. 3832169689Skan We don't need the same note for the check because 3833169689Skan any_condjump_p (check) == true. */ 3834169689Skan { 3835169689Skan REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, 3836169689Skan NULL_RTX, 3837169689Skan REG_NOTES (jump)); 3838169689Skan } 3839169689Skan edge_flags = EDGE_CROSSING; 3840169689Skan } 3841169689Skan else 3842169689Skan edge_flags = 0; 3843169689Skan 3844169689Skan make_single_succ_edge (rec, second_bb, edge_flags); 3845169689Skan 3846169689Skan add_block (rec, EXIT_BLOCK_PTR); 3847169689Skan } 3848169689Skan 3849169689Skan /* Move backward dependences from INSN to CHECK and 3850169689Skan move forward dependences from INSN to TWIN. */ 3851169689Skan for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 3852169689Skan { 3853169689Skan ds_t ds; 3854169689Skan 3855169689Skan /* If BEGIN_DATA: [insn ~~TRUE~~> producer]: 3856169689Skan check --TRUE--> producer ??? or ANTI ??? 3857169689Skan twin --TRUE--> producer 3858169689Skan twin --ANTI--> check 3859169689Skan 3860169689Skan If BEGIN_CONTROL: [insn ~~ANTI~~> producer]: 3861169689Skan check --ANTI--> producer 3862169689Skan twin --ANTI--> producer 3863169689Skan twin --ANTI--> check 3864169689Skan 3865169689Skan If BE_IN_SPEC: [insn ~~TRUE~~> producer]: 3866169689Skan check ~~TRUE~~> producer 3867169689Skan twin ~~TRUE~~> producer 3868169689Skan twin --ANTI--> check */ 3869169689Skan 3870169689Skan ds = DEP_STATUS (link); 3871169689Skan 3872169689Skan if (ds & BEGIN_SPEC) 3873169689Skan { 3874169689Skan gcc_assert (!mutate_p); 3875169689Skan ds &= ~BEGIN_SPEC; 3876169689Skan } 3877169689Skan 3878169689Skan if (rec != EXIT_BLOCK_PTR) 3879169689Skan { 3880169689Skan add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds); 3881169689Skan add_back_forw_dep (twin, XEXP (link, 0), REG_NOTE_KIND (link), ds); 3882169689Skan } 3883169689Skan else 3884169689Skan add_back_forw_dep (check, XEXP (link, 0), REG_NOTE_KIND (link), ds); 3885169689Skan } 3886169689Skan 3887169689Skan for (link = LOG_LINKS (insn); link;) 3888169689Skan if ((DEP_STATUS (link) & BEGIN_SPEC) 3889169689Skan || mutate_p) 3890169689Skan /* We can delete this dep only if we totally overcome it with 3891169689Skan BEGIN_SPECULATION. */ 3892169689Skan { 3893169689Skan delete_back_forw_dep (insn, XEXP (link, 0)); 3894169689Skan link = LOG_LINKS (insn); 3895169689Skan } 3896169689Skan else 3897169689Skan link = XEXP (link, 1); 3898169689Skan 3899169689Skan fs = 0; 3900169689Skan 3901169689Skan /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only 3902169689Skan here. */ 3903169689Skan 3904169689Skan gcc_assert (!DONE_SPEC (insn)); 3905169689Skan 3906169689Skan if (!mutate_p) 3907169689Skan { 3908169689Skan ds_t ts = TODO_SPEC (insn); 3909169689Skan 3910169689Skan DONE_SPEC (insn) = ts & BEGIN_SPEC; 3911169689Skan CHECK_SPEC (check) = ts & BEGIN_SPEC; 3912169689Skan 3913169689Skan if (ts & BEGIN_DATA) 3914169689Skan fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA)); 3915169689Skan if (ts & BEGIN_CONTROL) 3916169689Skan fs = set_dep_weak (fs, BE_IN_CONTROL, get_dep_weak (ts, BEGIN_CONTROL)); 3917169689Skan } 3918169689Skan else 3919169689Skan CHECK_SPEC (check) = CHECK_SPEC (insn); 3920169689Skan 3921169689Skan /* Future speculations: call the helper. */ 3922169689Skan process_insn_depend_be_in_spec (INSN_DEPEND (insn), twin, fs); 3923169689Skan 3924169689Skan if (rec != EXIT_BLOCK_PTR) 3925169689Skan { 3926169689Skan /* Which types of dependencies should we use here is, 3927169689Skan generally, machine-dependent question... But, for now, 3928169689Skan it is not. */ 3929169689Skan 3930169689Skan if (!mutate_p) 3931169689Skan { 3932169689Skan add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE); 3933169689Skan add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT); 3934169689Skan } 3935169689Skan else 3936169689Skan { 3937169689Skan if (spec_info->dump) 3938169689Skan fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n", 3939169689Skan (*current_sched_info->print_insn) (insn, 0)); 3940169689Skan 3941169689Skan for (link = INSN_DEPEND (insn); link; link = INSN_DEPEND (insn)) 3942169689Skan delete_back_forw_dep (XEXP (link, 0), insn); 3943169689Skan 3944169689Skan if (QUEUE_INDEX (insn) != QUEUE_NOWHERE) 3945169689Skan try_ready (check); 3946169689Skan 3947169689Skan sched_remove_insn (insn); 3948169689Skan } 3949169689Skan 3950169689Skan add_back_forw_dep (twin, check, REG_DEP_ANTI, DEP_ANTI); 3951169689Skan } 3952169689Skan else 3953169689Skan add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT); 3954169689Skan 3955169689Skan if (!mutate_p) 3956169689Skan /* Fix priorities. If MUTATE_P is nonzero, this is not necessary, 3957169689Skan because it'll be done later in add_to_speculative_block. */ 3958169689Skan { 3959169689Skan clear_priorities (twin); 3960169689Skan calc_priorities (twin); 3961169689Skan } 3962169689Skan} 3963169689Skan 3964169689Skan/* Removes dependency between instructions in the recovery block REC 3965169689Skan and usual region instructions. It keeps inner dependences so it 3966169689Skan won't be necessary to recompute them. */ 3967169689Skanstatic void 3968169689Skanfix_recovery_deps (basic_block rec) 3969169689Skan{ 3970169689Skan rtx note, insn, link, jump, ready_list = 0; 3971169689Skan bitmap_head in_ready; 3972169689Skan 3973169689Skan bitmap_initialize (&in_ready, 0); 3974169689Skan 3975169689Skan /* NOTE - a basic block note. */ 3976169689Skan note = NEXT_INSN (BB_HEAD (rec)); 3977169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); 3978169689Skan insn = BB_END (rec); 3979169689Skan gcc_assert (JUMP_P (insn)); 3980169689Skan insn = PREV_INSN (insn); 3981169689Skan 3982169689Skan do 3983169689Skan { 3984169689Skan for (link = INSN_DEPEND (insn); link;) 3985169689Skan { 3986169689Skan rtx consumer; 3987169689Skan 3988169689Skan consumer = XEXP (link, 0); 3989169689Skan 3990169689Skan if (BLOCK_FOR_INSN (consumer) != rec) 3991169689Skan { 3992169689Skan delete_back_forw_dep (consumer, insn); 3993169689Skan 3994169689Skan if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer))) 3995169689Skan { 3996169689Skan ready_list = alloc_INSN_LIST (consumer, ready_list); 3997169689Skan bitmap_set_bit (&in_ready, INSN_LUID (consumer)); 3998169689Skan } 3999169689Skan 4000169689Skan link = INSN_DEPEND (insn); 4001169689Skan } 4002169689Skan else 4003169689Skan { 4004169689Skan gcc_assert ((DEP_STATUS (link) & DEP_TYPES) == DEP_TRUE); 4005169689Skan 4006169689Skan link = XEXP (link, 1); 4007169689Skan } 4008169689Skan } 4009169689Skan 4010169689Skan insn = PREV_INSN (insn); 4011169689Skan } 4012169689Skan while (insn != note); 4013169689Skan 4014169689Skan bitmap_clear (&in_ready); 4015169689Skan 4016169689Skan /* Try to add instructions to the ready or queue list. */ 4017169689Skan for (link = ready_list; link; link = XEXP (link, 1)) 4018169689Skan try_ready (XEXP (link, 0)); 4019169689Skan free_INSN_LIST_list (&ready_list); 4020169689Skan 4021169689Skan /* Fixing jump's dependences. */ 4022169689Skan insn = BB_HEAD (rec); 4023169689Skan jump = BB_END (rec); 4024169689Skan 4025169689Skan gcc_assert (LABEL_P (insn)); 4026169689Skan insn = NEXT_INSN (insn); 4027169689Skan 4028169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn)); 4029169689Skan add_jump_dependencies (insn, jump); 4030169689Skan} 4031169689Skan 4032169689Skan/* The function saves line notes at the beginning of block B. */ 4033169689Skanstatic void 4034169689Skanassociate_line_notes_with_blocks (basic_block b) 4035169689Skan{ 4036169689Skan rtx line; 4037169689Skan 4038169689Skan for (line = BB_HEAD (b); line; line = PREV_INSN (line)) 4039169689Skan if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0) 4040169689Skan { 4041169689Skan line_note_head[b->index] = line; 4042169689Skan break; 4043169689Skan } 4044169689Skan /* Do a forward search as well, since we won't get to see the first 4045169689Skan notes in a basic block. */ 4046169689Skan for (line = BB_HEAD (b); line; line = NEXT_INSN (line)) 4047169689Skan { 4048169689Skan if (INSN_P (line)) 4049169689Skan break; 4050169689Skan if (NOTE_P (line) && NOTE_LINE_NUMBER (line) > 0) 4051169689Skan line_note_head[b->index] = line; 4052169689Skan } 4053169689Skan} 4054169689Skan 4055169689Skan/* Changes pattern of the INSN to NEW_PAT. */ 4056169689Skanstatic void 4057169689Skanchange_pattern (rtx insn, rtx new_pat) 4058169689Skan{ 4059169689Skan int t; 4060169689Skan 4061169689Skan t = validate_change (insn, &PATTERN (insn), new_pat, 0); 4062169689Skan gcc_assert (t); 4063169689Skan /* Invalidate INSN_COST, so it'll be recalculated. */ 4064169689Skan INSN_COST (insn) = -1; 4065169689Skan /* Invalidate INSN_TICK, so it'll be recalculated. */ 4066169689Skan INSN_TICK (insn) = INVALID_TICK; 4067169689Skan dfa_clear_single_insn_cache (insn); 4068169689Skan} 4069169689Skan 4070169689Skan 4071169689Skan/* -1 - can't speculate, 4072169689Skan 0 - for speculation with REQUEST mode it is OK to use 4073169689Skan current instruction pattern, 4074169689Skan 1 - need to change pattern for *NEW_PAT to be speculative. */ 4075169689Skanstatic int 4076169689Skanspeculate_insn (rtx insn, ds_t request, rtx *new_pat) 4077169689Skan{ 4078169689Skan gcc_assert (current_sched_info->flags & DO_SPECULATION 4079169689Skan && (request & SPECULATIVE)); 4080169689Skan 4081169689Skan if (!NONJUMP_INSN_P (insn) 4082169689Skan || HAS_INTERNAL_DEP (insn) 4083169689Skan || SCHED_GROUP_P (insn) 4084169689Skan || side_effects_p (PATTERN (insn)) 4085169689Skan || (request & spec_info->mask) != request) 4086169689Skan return -1; 4087169689Skan 4088169689Skan gcc_assert (!IS_SPECULATION_CHECK_P (insn)); 4089169689Skan 4090169689Skan if (request & BE_IN_SPEC) 4091169689Skan { 4092169689Skan if (may_trap_p (PATTERN (insn))) 4093169689Skan return -1; 4094169689Skan 4095169689Skan if (!(request & BEGIN_SPEC)) 4096169689Skan return 0; 4097169689Skan } 4098169689Skan 4099169689Skan return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat); 4100169689Skan} 4101169689Skan 4102169689Skan/* Print some information about block BB, which starts with HEAD and 4103169689Skan ends with TAIL, before scheduling it. 4104169689Skan I is zero, if scheduler is about to start with the fresh ebb. */ 4105169689Skanstatic void 4106169689Skandump_new_block_header (int i, basic_block bb, rtx head, rtx tail) 4107169689Skan{ 4108169689Skan if (!i) 4109169689Skan fprintf (sched_dump, 4110169689Skan ";; ======================================================\n"); 4111169689Skan else 4112169689Skan fprintf (sched_dump, 4113169689Skan ";; =====================ADVANCING TO=====================\n"); 4114169689Skan fprintf (sched_dump, 4115169689Skan ";; -- basic block %d from %d to %d -- %s reload\n", 4116169689Skan bb->index, INSN_UID (head), INSN_UID (tail), 4117169689Skan (reload_completed ? "after" : "before")); 4118169689Skan fprintf (sched_dump, 4119169689Skan ";; ======================================================\n"); 4120169689Skan fprintf (sched_dump, "\n"); 4121169689Skan} 4122169689Skan 4123169689Skan/* Unlink basic block notes and labels and saves them, so they 4124169689Skan can be easily restored. We unlink basic block notes in EBB to 4125169689Skan provide back-compatibility with the previous code, as target backends 4126169689Skan assume, that there'll be only instructions between 4127169689Skan current_sched_info->{head and tail}. We restore these notes as soon 4128169689Skan as we can. 4129169689Skan FIRST (LAST) is the first (last) basic block in the ebb. 4130169689Skan NB: In usual case (FIRST == LAST) nothing is really done. */ 4131169689Skanvoid 4132169689Skanunlink_bb_notes (basic_block first, basic_block last) 4133169689Skan{ 4134169689Skan /* We DON'T unlink basic block notes of the first block in the ebb. */ 4135169689Skan if (first == last) 4136169689Skan return; 4137169689Skan 4138169689Skan bb_header = xmalloc (last_basic_block * sizeof (*bb_header)); 4139169689Skan 4140169689Skan /* Make a sentinel. */ 4141169689Skan if (last->next_bb != EXIT_BLOCK_PTR) 4142169689Skan bb_header[last->next_bb->index] = 0; 4143169689Skan 4144169689Skan first = first->next_bb; 4145169689Skan do 4146169689Skan { 4147169689Skan rtx prev, label, note, next; 4148169689Skan 4149169689Skan label = BB_HEAD (last); 4150169689Skan if (LABEL_P (label)) 4151169689Skan note = NEXT_INSN (label); 4152169689Skan else 4153169689Skan note = label; 4154169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); 4155169689Skan 4156169689Skan prev = PREV_INSN (label); 4157169689Skan next = NEXT_INSN (note); 4158169689Skan gcc_assert (prev && next); 4159169689Skan 4160169689Skan NEXT_INSN (prev) = next; 4161169689Skan PREV_INSN (next) = prev; 4162169689Skan 4163169689Skan bb_header[last->index] = label; 4164169689Skan 4165169689Skan if (last == first) 4166169689Skan break; 4167169689Skan 4168169689Skan last = last->prev_bb; 4169169689Skan } 4170169689Skan while (1); 4171169689Skan} 4172169689Skan 4173169689Skan/* Restore basic block notes. 4174169689Skan FIRST is the first basic block in the ebb. */ 4175169689Skanstatic void 4176169689Skanrestore_bb_notes (basic_block first) 4177169689Skan{ 4178169689Skan if (!bb_header) 4179169689Skan return; 4180169689Skan 4181169689Skan /* We DON'T unlink basic block notes of the first block in the ebb. */ 4182169689Skan first = first->next_bb; 4183169689Skan /* Remember: FIRST is actually a second basic block in the ebb. */ 4184169689Skan 4185169689Skan while (first != EXIT_BLOCK_PTR 4186169689Skan && bb_header[first->index]) 4187169689Skan { 4188169689Skan rtx prev, label, note, next; 4189169689Skan 4190169689Skan label = bb_header[first->index]; 4191169689Skan prev = PREV_INSN (label); 4192169689Skan next = NEXT_INSN (prev); 4193169689Skan 4194169689Skan if (LABEL_P (label)) 4195169689Skan note = NEXT_INSN (label); 4196169689Skan else 4197169689Skan note = label; 4198169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); 4199169689Skan 4200169689Skan bb_header[first->index] = 0; 4201169689Skan 4202169689Skan NEXT_INSN (prev) = label; 4203169689Skan NEXT_INSN (note) = next; 4204169689Skan PREV_INSN (next) = note; 4205169689Skan 4206169689Skan first = first->next_bb; 4207169689Skan } 4208169689Skan 4209169689Skan free (bb_header); 4210169689Skan bb_header = 0; 4211169689Skan} 4212169689Skan 4213169689Skan/* Extend per basic block data structures of the scheduler. 4214169689Skan If BB is NULL, initialize structures for the whole CFG. 4215169689Skan Otherwise, initialize them for the just created BB. */ 4216169689Skanstatic void 4217169689Skanextend_bb (basic_block bb) 4218169689Skan{ 4219169689Skan rtx insn; 4220169689Skan 4221169689Skan if (write_symbols != NO_DEBUG) 4222169689Skan { 4223169689Skan /* Save-line-note-head: 4224169689Skan Determine the line-number at the start of each basic block. 4225169689Skan This must be computed and saved now, because after a basic block's 4226169689Skan predecessor has been scheduled, it is impossible to accurately 4227169689Skan determine the correct line number for the first insn of the block. */ 4228169689Skan line_note_head = xrecalloc (line_note_head, last_basic_block, 4229169689Skan old_last_basic_block, 4230169689Skan sizeof (*line_note_head)); 4231169689Skan 4232169689Skan if (bb) 4233169689Skan associate_line_notes_with_blocks (bb); 4234169689Skan else 4235169689Skan FOR_EACH_BB (bb) 4236169689Skan associate_line_notes_with_blocks (bb); 4237169689Skan } 4238169689Skan 4239169689Skan old_last_basic_block = last_basic_block; 4240169689Skan 4241169689Skan if (current_sched_info->flags & USE_GLAT) 4242169689Skan { 4243169689Skan glat_start = xrealloc (glat_start, 4244169689Skan last_basic_block * sizeof (*glat_start)); 4245169689Skan glat_end = xrealloc (glat_end, last_basic_block * sizeof (*glat_end)); 4246169689Skan } 4247169689Skan 4248169689Skan /* The following is done to keep current_sched_info->next_tail non null. */ 4249169689Skan 4250132718Skan insn = BB_END (EXIT_BLOCK_PTR->prev_bb); 425150397Sobrien if (NEXT_INSN (insn) == 0 4252169689Skan || (!NOTE_P (insn) 4253169689Skan && !LABEL_P (insn) 425490075Sobrien /* Don't emit a NOTE if it would end up before a BARRIER. */ 4255169689Skan && !BARRIER_P (NEXT_INSN (insn)))) 425650397Sobrien { 4257169689Skan emit_note_after (NOTE_INSN_DELETED, insn); 425890075Sobrien /* Make insn to appear outside BB. */ 4259169689Skan BB_END (EXIT_BLOCK_PTR->prev_bb) = insn; 426050397Sobrien } 4261169689Skan} 426250397Sobrien 4263169689Skan/* Add a basic block BB to extended basic block EBB. 4264169689Skan If EBB is EXIT_BLOCK_PTR, then BB is recovery block. 4265169689Skan If EBB is NULL, then BB should be a new region. */ 4266169689Skanvoid 4267169689Skanadd_block (basic_block bb, basic_block ebb) 4268169689Skan{ 4269169689Skan gcc_assert (current_sched_info->flags & DETACH_LIFE_INFO 4270169689Skan && bb->il.rtl->global_live_at_start == 0 4271169689Skan && bb->il.rtl->global_live_at_end == 0); 4272169689Skan 4273169689Skan extend_bb (bb); 4274169689Skan 4275169689Skan glat_start[bb->index] = 0; 4276169689Skan glat_end[bb->index] = 0; 4277169689Skan 4278169689Skan if (current_sched_info->add_block) 4279169689Skan /* This changes only data structures of the front-end. */ 4280169689Skan current_sched_info->add_block (bb, ebb); 428190075Sobrien} 428250397Sobrien 4283169689Skan/* Helper function. 4284169689Skan Fix CFG after both in- and inter-block movement of 4285169689Skan control_flow_insn_p JUMP. */ 4286169689Skanstatic void 4287169689Skanfix_jump_move (rtx jump) 4288169689Skan{ 4289169689Skan basic_block bb, jump_bb, jump_bb_next; 429050397Sobrien 4291169689Skan bb = BLOCK_FOR_INSN (PREV_INSN (jump)); 4292169689Skan jump_bb = BLOCK_FOR_INSN (jump); 4293169689Skan jump_bb_next = jump_bb->next_bb; 4294169689Skan 4295169689Skan gcc_assert (current_sched_info->flags & SCHED_EBB 4296169689Skan || IS_SPECULATION_BRANCHY_CHECK_P (jump)); 4297169689Skan 4298169689Skan if (!NOTE_INSN_BASIC_BLOCK_P (BB_END (jump_bb_next))) 4299169689Skan /* if jump_bb_next is not empty. */ 4300169689Skan BB_END (jump_bb) = BB_END (jump_bb_next); 4301169689Skan 4302169689Skan if (BB_END (bb) != PREV_INSN (jump)) 4303169689Skan /* Then there are instruction after jump that should be placed 4304169689Skan to jump_bb_next. */ 4305169689Skan BB_END (jump_bb_next) = BB_END (bb); 4306169689Skan else 4307169689Skan /* Otherwise jump_bb_next is empty. */ 4308169689Skan BB_END (jump_bb_next) = NEXT_INSN (BB_HEAD (jump_bb_next)); 4309169689Skan 4310169689Skan /* To make assertion in move_insn happy. */ 4311169689Skan BB_END (bb) = PREV_INSN (jump); 4312169689Skan 4313169689Skan update_bb_for_insn (jump_bb_next); 4314169689Skan} 4315169689Skan 4316169689Skan/* Fix CFG after interblock movement of control_flow_insn_p JUMP. */ 4317169689Skanstatic void 4318169689Skanmove_block_after_check (rtx jump) 4319169689Skan{ 4320169689Skan basic_block bb, jump_bb, jump_bb_next; 4321169689Skan VEC(edge,gc) *t; 4322169689Skan 4323169689Skan bb = BLOCK_FOR_INSN (PREV_INSN (jump)); 4324169689Skan jump_bb = BLOCK_FOR_INSN (jump); 4325169689Skan jump_bb_next = jump_bb->next_bb; 4326169689Skan 4327169689Skan update_bb_for_insn (jump_bb); 4328169689Skan 4329169689Skan gcc_assert (IS_SPECULATION_CHECK_P (jump) 4330169689Skan || IS_SPECULATION_CHECK_P (BB_END (jump_bb_next))); 4331169689Skan 4332169689Skan unlink_block (jump_bb_next); 4333169689Skan link_block (jump_bb_next, bb); 4334169689Skan 4335169689Skan t = bb->succs; 4336169689Skan bb->succs = 0; 4337169689Skan move_succs (&(jump_bb->succs), bb); 4338169689Skan move_succs (&(jump_bb_next->succs), jump_bb); 4339169689Skan move_succs (&t, jump_bb_next); 4340169689Skan 4341169689Skan if (current_sched_info->fix_recovery_cfg) 4342169689Skan current_sched_info->fix_recovery_cfg 4343169689Skan (bb->index, jump_bb->index, jump_bb_next->index); 4344169689Skan} 4345169689Skan 4346169689Skan/* Helper function for move_block_after_check. 4347169689Skan This functions attaches edge vector pointed to by SUCCSP to 4348169689Skan block TO. */ 4349169689Skanstatic void 4350169689Skanmove_succs (VEC(edge,gc) **succsp, basic_block to) 4351169689Skan{ 4352169689Skan edge e; 4353169689Skan edge_iterator ei; 4354169689Skan 4355169689Skan gcc_assert (to->succs == 0); 4356169689Skan 4357169689Skan to->succs = *succsp; 4358169689Skan 4359169689Skan FOR_EACH_EDGE (e, ei, to->succs) 4360169689Skan e->src = to; 4361169689Skan 4362169689Skan *succsp = 0; 4363169689Skan} 4364169689Skan 4365169689Skan/* Initialize GLAT (global_live_at_{start, end}) structures. 4366169689Skan GLAT structures are used to substitute global_live_{start, end} 4367169689Skan regsets during scheduling. This is necessary to use such functions as 4368169689Skan split_block (), as they assume consistency of register live information. */ 4369169689Skanstatic void 4370169689Skaninit_glat (void) 4371169689Skan{ 4372169689Skan basic_block bb; 4373169689Skan 4374169689Skan FOR_ALL_BB (bb) 4375169689Skan init_glat1 (bb); 4376169689Skan} 4377169689Skan 4378169689Skan/* Helper function for init_glat. */ 4379169689Skanstatic void 4380169689Skaninit_glat1 (basic_block bb) 4381169689Skan{ 4382169689Skan gcc_assert (bb->il.rtl->global_live_at_start != 0 4383169689Skan && bb->il.rtl->global_live_at_end != 0); 4384169689Skan 4385169689Skan glat_start[bb->index] = bb->il.rtl->global_live_at_start; 4386169689Skan glat_end[bb->index] = bb->il.rtl->global_live_at_end; 4387169689Skan 4388169689Skan if (current_sched_info->flags & DETACH_LIFE_INFO) 4389169689Skan { 4390169689Skan bb->il.rtl->global_live_at_start = 0; 4391169689Skan bb->il.rtl->global_live_at_end = 0; 4392169689Skan } 4393169689Skan} 4394169689Skan 4395169689Skan/* Attach reg_live_info back to basic blocks. 4396169689Skan Also save regsets, that should not have been changed during scheduling, 4397169689Skan for checking purposes (see check_reg_live). */ 439890075Sobrienvoid 4399169689Skanattach_life_info (void) 440090075Sobrien{ 4401169689Skan basic_block bb; 4402117395Skan 4403169689Skan FOR_ALL_BB (bb) 4404169689Skan attach_life_info1 (bb); 4405169689Skan} 4406169689Skan 4407169689Skan/* Helper function for attach_life_info. */ 4408169689Skanstatic void 4409169689Skanattach_life_info1 (basic_block bb) 4410169689Skan{ 4411169689Skan gcc_assert (bb->il.rtl->global_live_at_start == 0 4412169689Skan && bb->il.rtl->global_live_at_end == 0); 4413169689Skan 4414169689Skan if (glat_start[bb->index]) 4415117395Skan { 4416169689Skan gcc_assert (glat_end[bb->index]); 4417169689Skan 4418169689Skan bb->il.rtl->global_live_at_start = glat_start[bb->index]; 4419169689Skan bb->il.rtl->global_live_at_end = glat_end[bb->index]; 4420169689Skan 4421169689Skan /* Make them NULL, so they won't be freed in free_glat. */ 4422169689Skan glat_start[bb->index] = 0; 4423169689Skan glat_end[bb->index] = 0; 4424169689Skan 4425169689Skan#ifdef ENABLE_CHECKING 4426169689Skan if (bb->index < NUM_FIXED_BLOCKS 4427169689Skan || current_sched_info->region_head_or_leaf_p (bb, 0)) 4428169689Skan { 4429169689Skan glat_start[bb->index] = ALLOC_REG_SET (®_obstack); 4430169689Skan COPY_REG_SET (glat_start[bb->index], 4431169689Skan bb->il.rtl->global_live_at_start); 4432169689Skan } 4433169689Skan 4434169689Skan if (bb->index < NUM_FIXED_BLOCKS 4435169689Skan || current_sched_info->region_head_or_leaf_p (bb, 1)) 4436169689Skan { 4437169689Skan glat_end[bb->index] = ALLOC_REG_SET (®_obstack); 4438169689Skan COPY_REG_SET (glat_end[bb->index], bb->il.rtl->global_live_at_end); 4439169689Skan } 4440169689Skan#endif 4441117395Skan } 4442169689Skan else 4443169689Skan { 4444169689Skan gcc_assert (!glat_end[bb->index]); 4445169689Skan 4446169689Skan bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 4447169689Skan bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 4448169689Skan } 444950397Sobrien} 4450169689Skan 4451169689Skan/* Free GLAT information. */ 4452169689Skanstatic void 4453169689Skanfree_glat (void) 4454169689Skan{ 4455169689Skan#ifdef ENABLE_CHECKING 4456169689Skan if (current_sched_info->flags & DETACH_LIFE_INFO) 4457169689Skan { 4458169689Skan basic_block bb; 4459169689Skan 4460169689Skan FOR_ALL_BB (bb) 4461169689Skan { 4462169689Skan if (glat_start[bb->index]) 4463169689Skan FREE_REG_SET (glat_start[bb->index]); 4464169689Skan if (glat_end[bb->index]) 4465169689Skan FREE_REG_SET (glat_end[bb->index]); 4466169689Skan } 4467169689Skan } 4468169689Skan#endif 4469169689Skan 4470169689Skan free (glat_start); 4471169689Skan free (glat_end); 4472169689Skan} 4473169689Skan 4474169689Skan/* Remove INSN from the instruction stream. 4475169689Skan INSN should have any dependencies. */ 4476169689Skanstatic void 4477169689Skansched_remove_insn (rtx insn) 4478169689Skan{ 4479169689Skan change_queue_index (insn, QUEUE_NOWHERE); 4480169689Skan current_sched_info->add_remove_insn (insn, 1); 4481169689Skan remove_insn (insn); 4482169689Skan} 4483169689Skan 4484169689Skan/* Clear priorities of all instructions, that are 4485169689Skan forward dependent on INSN. */ 4486169689Skanstatic void 4487169689Skanclear_priorities (rtx insn) 4488169689Skan{ 4489169689Skan rtx link; 4490169689Skan 4491169689Skan for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 4492169689Skan { 4493169689Skan rtx pro; 4494169689Skan 4495169689Skan pro = XEXP (link, 0); 4496169689Skan if (INSN_PRIORITY_KNOWN (pro)) 4497169689Skan { 4498169689Skan INSN_PRIORITY_KNOWN (pro) = 0; 4499169689Skan clear_priorities (pro); 4500169689Skan } 4501169689Skan } 4502169689Skan} 4503169689Skan 4504169689Skan/* Recompute priorities of instructions, whose priorities might have been 4505169689Skan changed due to changes in INSN. */ 4506169689Skanstatic void 4507169689Skancalc_priorities (rtx insn) 4508169689Skan{ 4509169689Skan rtx link; 4510169689Skan 4511169689Skan for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 4512169689Skan { 4513169689Skan rtx pro; 4514169689Skan 4515169689Skan pro = XEXP (link, 0); 4516169689Skan if (!INSN_PRIORITY_KNOWN (pro)) 4517169689Skan { 4518169689Skan priority (pro); 4519169689Skan calc_priorities (pro); 4520169689Skan } 4521169689Skan } 4522169689Skan} 4523169689Skan 4524169689Skan 4525169689Skan/* Add dependences between JUMP and other instructions in the recovery 4526169689Skan block. INSN is the first insn the recovery block. */ 4527169689Skanstatic void 4528169689Skanadd_jump_dependencies (rtx insn, rtx jump) 4529169689Skan{ 4530169689Skan do 4531169689Skan { 4532169689Skan insn = NEXT_INSN (insn); 4533169689Skan if (insn == jump) 4534169689Skan break; 4535169689Skan 4536169689Skan if (!INSN_DEPEND (insn)) 4537169689Skan add_back_forw_dep (jump, insn, REG_DEP_ANTI, DEP_ANTI); 4538169689Skan } 4539169689Skan while (1); 4540169689Skan gcc_assert (LOG_LINKS (jump)); 4541169689Skan} 4542169689Skan 4543169689Skan/* Return the NOTE_INSN_BASIC_BLOCK of BB. */ 4544169689Skanrtx 4545169689Skanbb_note (basic_block bb) 4546169689Skan{ 4547169689Skan rtx note; 4548169689Skan 4549169689Skan note = BB_HEAD (bb); 4550169689Skan if (LABEL_P (note)) 4551169689Skan note = NEXT_INSN (note); 4552169689Skan 4553169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note)); 4554169689Skan return note; 4555169689Skan} 4556169689Skan 4557169689Skan#ifdef ENABLE_CHECKING 4558169689Skanextern void debug_spec_status (ds_t); 4559169689Skan 4560169689Skan/* Dump information about the dependence status S. */ 4561169689Skanvoid 4562169689Skandebug_spec_status (ds_t s) 4563169689Skan{ 4564169689Skan FILE *f = stderr; 4565169689Skan 4566169689Skan if (s & BEGIN_DATA) 4567169689Skan fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak (s, BEGIN_DATA)); 4568169689Skan if (s & BE_IN_DATA) 4569169689Skan fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak (s, BE_IN_DATA)); 4570169689Skan if (s & BEGIN_CONTROL) 4571169689Skan fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak (s, BEGIN_CONTROL)); 4572169689Skan if (s & BE_IN_CONTROL) 4573169689Skan fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak (s, BE_IN_CONTROL)); 4574169689Skan 4575169689Skan if (s & HARD_DEP) 4576169689Skan fprintf (f, "HARD_DEP; "); 4577169689Skan 4578169689Skan if (s & DEP_TRUE) 4579169689Skan fprintf (f, "DEP_TRUE; "); 4580169689Skan if (s & DEP_ANTI) 4581169689Skan fprintf (f, "DEP_ANTI; "); 4582169689Skan if (s & DEP_OUTPUT) 4583169689Skan fprintf (f, "DEP_OUTPUT; "); 4584169689Skan 4585169689Skan fprintf (f, "\n"); 4586169689Skan} 4587169689Skan 4588169689Skan/* Helper function for check_cfg. 4589169689Skan Return nonzero, if edge vector pointed to by EL has edge with TYPE in 4590169689Skan its flags. */ 4591169689Skanstatic int 4592169689Skanhas_edge_p (VEC(edge,gc) *el, int type) 4593169689Skan{ 4594169689Skan edge e; 4595169689Skan edge_iterator ei; 4596169689Skan 4597169689Skan FOR_EACH_EDGE (e, ei, el) 4598169689Skan if (e->flags & type) 4599169689Skan return 1; 4600169689Skan return 0; 4601169689Skan} 4602169689Skan 4603169689Skan/* Check few properties of CFG between HEAD and TAIL. 4604169689Skan If HEAD (TAIL) is NULL check from the beginning (till the end) of the 4605169689Skan instruction stream. */ 4606169689Skanstatic void 4607169689Skancheck_cfg (rtx head, rtx tail) 4608169689Skan{ 4609169689Skan rtx next_tail; 4610169689Skan basic_block bb = 0; 4611169689Skan int not_first = 0, not_last; 4612169689Skan 4613169689Skan if (head == NULL) 4614169689Skan head = get_insns (); 4615169689Skan if (tail == NULL) 4616169689Skan tail = get_last_insn (); 4617169689Skan next_tail = NEXT_INSN (tail); 4618169689Skan 4619169689Skan do 4620169689Skan { 4621169689Skan not_last = head != tail; 4622169689Skan 4623169689Skan if (not_first) 4624169689Skan gcc_assert (NEXT_INSN (PREV_INSN (head)) == head); 4625169689Skan if (not_last) 4626169689Skan gcc_assert (PREV_INSN (NEXT_INSN (head)) == head); 4627169689Skan 4628169689Skan if (LABEL_P (head) 4629169689Skan || (NOTE_INSN_BASIC_BLOCK_P (head) 4630169689Skan && (!not_first 4631169689Skan || (not_first && !LABEL_P (PREV_INSN (head)))))) 4632169689Skan { 4633169689Skan gcc_assert (bb == 0); 4634169689Skan bb = BLOCK_FOR_INSN (head); 4635169689Skan if (bb != 0) 4636169689Skan gcc_assert (BB_HEAD (bb) == head); 4637169689Skan else 4638169689Skan /* This is the case of jump table. See inside_basic_block_p (). */ 4639169689Skan gcc_assert (LABEL_P (head) && !inside_basic_block_p (head)); 4640169689Skan } 4641169689Skan 4642169689Skan if (bb == 0) 4643169689Skan { 4644169689Skan gcc_assert (!inside_basic_block_p (head)); 4645169689Skan head = NEXT_INSN (head); 4646169689Skan } 4647169689Skan else 4648169689Skan { 4649169689Skan gcc_assert (inside_basic_block_p (head) 4650169689Skan || NOTE_P (head)); 4651169689Skan gcc_assert (BLOCK_FOR_INSN (head) == bb); 4652169689Skan 4653169689Skan if (LABEL_P (head)) 4654169689Skan { 4655169689Skan head = NEXT_INSN (head); 4656169689Skan gcc_assert (NOTE_INSN_BASIC_BLOCK_P (head)); 4657169689Skan } 4658169689Skan else 4659169689Skan { 4660169689Skan if (control_flow_insn_p (head)) 4661169689Skan { 4662169689Skan gcc_assert (BB_END (bb) == head); 4663169689Skan 4664169689Skan if (any_uncondjump_p (head)) 4665169689Skan gcc_assert (EDGE_COUNT (bb->succs) == 1 4666169689Skan && BARRIER_P (NEXT_INSN (head))); 4667169689Skan else if (any_condjump_p (head)) 4668169689Skan gcc_assert (/* Usual case. */ 4669169689Skan (EDGE_COUNT (bb->succs) > 1 4670169689Skan && !BARRIER_P (NEXT_INSN (head))) 4671169689Skan /* Or jump to the next instruction. */ 4672169689Skan || (EDGE_COUNT (bb->succs) == 1 4673169689Skan && (BB_HEAD (EDGE_I (bb->succs, 0)->dest) 4674169689Skan == JUMP_LABEL (head)))); 4675169689Skan } 4676169689Skan if (BB_END (bb) == head) 4677169689Skan { 4678169689Skan if (EDGE_COUNT (bb->succs) > 1) 4679169689Skan gcc_assert (control_flow_insn_p (head) 4680169689Skan || has_edge_p (bb->succs, EDGE_COMPLEX)); 4681169689Skan bb = 0; 4682169689Skan } 4683169689Skan 4684169689Skan head = NEXT_INSN (head); 4685169689Skan } 4686169689Skan } 4687169689Skan 4688169689Skan not_first = 1; 4689169689Skan } 4690169689Skan while (head != next_tail); 4691169689Skan 4692169689Skan gcc_assert (bb == 0); 4693169689Skan} 4694169689Skan 4695169689Skan/* Perform a few consistency checks of flags in different data structures. */ 4696169689Skanstatic void 4697169689Skancheck_sched_flags (void) 4698169689Skan{ 4699169689Skan unsigned int f = current_sched_info->flags; 4700169689Skan 4701169689Skan if (flag_sched_stalled_insns) 4702169689Skan gcc_assert (!(f & DO_SPECULATION)); 4703169689Skan if (f & DO_SPECULATION) 4704169689Skan gcc_assert (!flag_sched_stalled_insns 4705169689Skan && (f & DETACH_LIFE_INFO) 4706169689Skan && spec_info 4707169689Skan && spec_info->mask); 4708169689Skan if (f & DETACH_LIFE_INFO) 4709169689Skan gcc_assert (f & USE_GLAT); 4710169689Skan} 4711169689Skan 4712169689Skan/* Check global_live_at_{start, end} regsets. 4713169689Skan If FATAL_P is TRUE, then abort execution at the first failure. 4714169689Skan Otherwise, print diagnostics to STDERR (this mode is for calling 4715169689Skan from debugger). */ 4716169689Skanvoid 4717169689Skancheck_reg_live (bool fatal_p) 4718169689Skan{ 4719169689Skan basic_block bb; 4720169689Skan 4721169689Skan FOR_ALL_BB (bb) 4722169689Skan { 4723169689Skan int i; 4724169689Skan 4725169689Skan i = bb->index; 4726169689Skan 4727169689Skan if (glat_start[i]) 4728169689Skan { 4729169689Skan bool b = bitmap_equal_p (bb->il.rtl->global_live_at_start, 4730169689Skan glat_start[i]); 4731169689Skan 4732169689Skan if (!b) 4733169689Skan { 4734169689Skan gcc_assert (!fatal_p); 4735169689Skan 4736169689Skan fprintf (stderr, ";; check_reg_live_at_start (%d) failed.\n", i); 4737169689Skan } 4738169689Skan } 4739169689Skan 4740169689Skan if (glat_end[i]) 4741169689Skan { 4742169689Skan bool b = bitmap_equal_p (bb->il.rtl->global_live_at_end, 4743169689Skan glat_end[i]); 4744169689Skan 4745169689Skan if (!b) 4746169689Skan { 4747169689Skan gcc_assert (!fatal_p); 4748169689Skan 4749169689Skan fprintf (stderr, ";; check_reg_live_at_end (%d) failed.\n", i); 4750169689Skan } 4751169689Skan } 4752169689Skan } 4753169689Skan} 4754169689Skan#endif /* ENABLE_CHECKING */ 4755169689Skan 475650397Sobrien#endif /* INSN_SCHEDULING */ 4757