1/* Instruction scheduling pass. This file contains definitions used 2 internally in the scheduler. 3 Copyright (C) 2006-2015 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 3, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#ifndef GCC_SEL_SCHED_IR_H 22#define GCC_SEL_SCHED_IR_H 23 24/* For state_t. */ 25#include "insn-attr.h" 26#include "regset.h" 27/* For reg_note. */ 28#include "rtl.h" 29#include "ggc.h" 30#include "bitmap.h" 31#include "sched-int.h" 32#include "cfgloop.h" 33 34/* tc_t is a short for target context. This is a state of the target 35 backend. */ 36typedef void *tc_t; 37 38/* List data types used for av sets, fences, paths, and boundaries. */ 39 40/* Forward declarations for types that are part of some list nodes. */ 41struct _list_node; 42 43/* List backend. */ 44typedef struct _list_node *_list_t; 45#define _LIST_NEXT(L) ((L)->next) 46 47/* Instruction data that is part of vinsn type. */ 48struct idata_def; 49typedef struct idata_def *idata_t; 50 51/* A virtual instruction, i.e. an instruction as seen by the scheduler. */ 52struct vinsn_def; 53typedef struct vinsn_def *vinsn_t; 54 55/* RTX list. 56 This type is the backend for ilist. */ 57typedef _list_t _xlist_t; 58#define _XLIST_X(L) ((L)->u.x) 59#define _XLIST_NEXT(L) (_LIST_NEXT (L)) 60 61/* Instruction. */ 62typedef rtx_insn *insn_t; 63 64/* List of insns. */ 65typedef _list_t ilist_t; 66#define ILIST_INSN(L) ((L)->u.insn) 67#define ILIST_NEXT(L) (_LIST_NEXT (L)) 68 69/* This lists possible transformations that done locally, i.e. in 70 moveup_expr. */ 71enum local_trans_type 72 { 73 TRANS_SUBSTITUTION, 74 TRANS_SPECULATION 75 }; 76 77/* This struct is used to record the history of expression's 78 transformations. */ 79struct expr_history_def_1 80{ 81 /* UID of the insn. */ 82 unsigned uid; 83 84 /* How the expression looked like. */ 85 vinsn_t old_expr_vinsn; 86 87 /* How the expression looks after the transformation. */ 88 vinsn_t new_expr_vinsn; 89 90 /* And its speculative status. */ 91 ds_t spec_ds; 92 93 /* Type of the transformation. */ 94 enum local_trans_type type; 95}; 96 97typedef struct expr_history_def_1 expr_history_def; 98 99 100/* Expression information. */ 101struct _expr 102{ 103 /* Insn description. */ 104 vinsn_t vinsn; 105 106 /* SPEC is the degree of speculativeness. 107 FIXME: now spec is increased when an rhs is moved through a 108 conditional, thus showing only control speculativeness. In the 109 future we'd like to count data spec separately to allow a better 110 control on scheduling. */ 111 int spec; 112 113 /* Degree of speculativeness measured as probability of executing 114 instruction's original basic block given relative to 115 the current scheduling point. */ 116 int usefulness; 117 118 /* A priority of this expression. */ 119 int priority; 120 121 /* A priority adjustment of this expression. */ 122 int priority_adj; 123 124 /* Number of times the insn was scheduled. */ 125 int sched_times; 126 127 /* A basic block index this was originated from. Zero when there is 128 more than one originator. */ 129 int orig_bb_index; 130 131 /* Instruction should be of SPEC_DONE_DS type in order to be moved to this 132 point. */ 133 ds_t spec_done_ds; 134 135 /* SPEC_TO_CHECK_DS hold speculation types that should be checked 136 (used only during move_op ()). */ 137 ds_t spec_to_check_ds; 138 139 /* Cycle on which original insn was scheduled. Zero when it has not yet 140 been scheduled or more than one originator. */ 141 int orig_sched_cycle; 142 143 /* This vector contains the history of insn's transformations. */ 144 vec<expr_history_def> history_of_changes; 145 146 /* True (1) when original target (register or memory) of this instruction 147 is available for scheduling, false otherwise. -1 means we're not sure; 148 please run find_used_regs to clarify. */ 149 signed char target_available; 150 151 /* True when this expression needs a speculation check to be scheduled. 152 This is used during find_used_regs. */ 153 BOOL_BITFIELD needs_spec_check_p : 1; 154 155 /* True when the expression was substituted. Used for statistical 156 purposes. */ 157 BOOL_BITFIELD was_substituted : 1; 158 159 /* True when the expression was renamed. */ 160 BOOL_BITFIELD was_renamed : 1; 161 162 /* True when expression can't be moved. */ 163 BOOL_BITFIELD cant_move : 1; 164}; 165 166typedef struct _expr expr_def; 167typedef expr_def *expr_t; 168 169#define EXPR_VINSN(EXPR) ((EXPR)->vinsn) 170#define EXPR_INSN_RTX(EXPR) (VINSN_INSN_RTX (EXPR_VINSN (EXPR))) 171#define EXPR_PATTERN(EXPR) (VINSN_PATTERN (EXPR_VINSN (EXPR))) 172#define EXPR_LHS(EXPR) (VINSN_LHS (EXPR_VINSN (EXPR))) 173#define EXPR_RHS(EXPR) (VINSN_RHS (EXPR_VINSN (EXPR))) 174#define EXPR_TYPE(EXPR) (VINSN_TYPE (EXPR_VINSN (EXPR))) 175#define EXPR_SEPARABLE_P(EXPR) (VINSN_SEPARABLE_P (EXPR_VINSN (EXPR))) 176 177#define EXPR_SPEC(EXPR) ((EXPR)->spec) 178#define EXPR_USEFULNESS(EXPR) ((EXPR)->usefulness) 179#define EXPR_PRIORITY(EXPR) ((EXPR)->priority) 180#define EXPR_PRIORITY_ADJ(EXPR) ((EXPR)->priority_adj) 181#define EXPR_SCHED_TIMES(EXPR) ((EXPR)->sched_times) 182#define EXPR_ORIG_BB_INDEX(EXPR) ((EXPR)->orig_bb_index) 183#define EXPR_ORIG_SCHED_CYCLE(EXPR) ((EXPR)->orig_sched_cycle) 184#define EXPR_SPEC_DONE_DS(EXPR) ((EXPR)->spec_done_ds) 185#define EXPR_SPEC_TO_CHECK_DS(EXPR) ((EXPR)->spec_to_check_ds) 186#define EXPR_HISTORY_OF_CHANGES(EXPR) ((EXPR)->history_of_changes) 187#define EXPR_TARGET_AVAILABLE(EXPR) ((EXPR)->target_available) 188#define EXPR_NEEDS_SPEC_CHECK_P(EXPR) ((EXPR)->needs_spec_check_p) 189#define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted) 190#define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed) 191#define EXPR_CANT_MOVE(EXPR) ((EXPR)->cant_move) 192 193/* Insn definition for list of original insns in find_used_regs. */ 194struct _def 195{ 196 insn_t orig_insn; 197 198 /* FIXME: Get rid of CROSSES_CALL in each def, since if we're moving up 199 rhs from two different places, but only one of the code motion paths 200 crosses a call, we can't use any of the call_used_regs, no matter which 201 path or whether all paths crosses a call. Thus we should move CROSSES_CALL 202 to static params. */ 203 bool crosses_call; 204}; 205typedef struct _def *def_t; 206 207 208/* Availability sets are sets of expressions we're scheduling. */ 209typedef _list_t av_set_t; 210#define _AV_SET_EXPR(L) (&(L)->u.expr) 211#define _AV_SET_NEXT(L) (_LIST_NEXT (L)) 212 213 214/* Boundary of the current fence group. */ 215struct _bnd 216{ 217 /* The actual boundary instruction. */ 218 insn_t to; 219 220 /* Its path to the fence. */ 221 ilist_t ptr; 222 223 /* Availability set at the boundary. */ 224 av_set_t av; 225 226 /* This set moved to the fence. */ 227 av_set_t av1; 228 229 /* Deps context at this boundary. As long as we have one boundary per fence, 230 this is just a pointer to the same deps context as in the corresponding 231 fence. */ 232 deps_t dc; 233}; 234typedef struct _bnd *bnd_t; 235#define BND_TO(B) ((B)->to) 236 237/* PTR stands not for pointer as you might think, but as a Path To Root of the 238 current instruction group from boundary B. */ 239#define BND_PTR(B) ((B)->ptr) 240#define BND_AV(B) ((B)->av) 241#define BND_AV1(B) ((B)->av1) 242#define BND_DC(B) ((B)->dc) 243 244/* List of boundaries. */ 245typedef _list_t blist_t; 246#define BLIST_BND(L) (&(L)->u.bnd) 247#define BLIST_NEXT(L) (_LIST_NEXT (L)) 248 249 250/* Fence information. A fence represents current scheduling point and also 251 blocks code motion through it when pipelining. */ 252struct _fence 253{ 254 /* Insn before which we gather an instruction group.*/ 255 insn_t insn; 256 257 /* Modeled state of the processor pipeline. */ 258 state_t state; 259 260 /* Current cycle that is being scheduled on this fence. */ 261 int cycle; 262 263 /* Number of insns that were scheduled on the current cycle. 264 This information has to be local to a fence. */ 265 int cycle_issued_insns; 266 267 /* At the end of fill_insns () this field holds the list of the instructions 268 that are inner boundaries of the scheduled parallel group. */ 269 ilist_t bnds; 270 271 /* Deps context at this fence. It is used to model dependencies at the 272 fence so that insn ticks can be properly evaluated. */ 273 deps_t dc; 274 275 /* Target context at this fence. Used to save and load any local target 276 scheduling information when changing fences. */ 277 tc_t tc; 278 279 /* A vector of insns that are scheduled but not yet completed. */ 280 vec<rtx_insn *, va_gc> *executing_insns; 281 282 /* A vector indexed by UIDs that caches the earliest cycle on which 283 an insn can be scheduled on this fence. */ 284 int *ready_ticks; 285 286 /* Its size. */ 287 int ready_ticks_size; 288 289 /* Insn, which has been scheduled last on this fence. */ 290 rtx_insn *last_scheduled_insn; 291 292 /* The last value of can_issue_more variable on this fence. */ 293 int issue_more; 294 295 /* If non-NULL force the next scheduled insn to be SCHED_NEXT. */ 296 rtx_insn *sched_next; 297 298 /* True if fill_insns processed this fence. */ 299 BOOL_BITFIELD processed_p : 1; 300 301 /* True if fill_insns actually scheduled something on this fence. */ 302 BOOL_BITFIELD scheduled_p : 1; 303 304 /* True when the next insn scheduled here would start a cycle. */ 305 BOOL_BITFIELD starts_cycle_p : 1; 306 307 /* True when the next insn scheduled here would be scheduled after a stall. */ 308 BOOL_BITFIELD after_stall_p : 1; 309}; 310typedef struct _fence *fence_t; 311 312#define FENCE_INSN(F) ((F)->insn) 313#define FENCE_STATE(F) ((F)->state) 314#define FENCE_BNDS(F) ((F)->bnds) 315#define FENCE_PROCESSED_P(F) ((F)->processed_p) 316#define FENCE_SCHEDULED_P(F) ((F)->scheduled_p) 317#define FENCE_ISSUED_INSNS(F) ((F)->cycle_issued_insns) 318#define FENCE_CYCLE(F) ((F)->cycle) 319#define FENCE_STARTS_CYCLE_P(F) ((F)->starts_cycle_p) 320#define FENCE_AFTER_STALL_P(F) ((F)->after_stall_p) 321#define FENCE_DC(F) ((F)->dc) 322#define FENCE_TC(F) ((F)->tc) 323#define FENCE_LAST_SCHEDULED_INSN(F) ((F)->last_scheduled_insn) 324#define FENCE_ISSUE_MORE(F) ((F)->issue_more) 325#define FENCE_EXECUTING_INSNS(F) ((F)->executing_insns) 326#define FENCE_READY_TICKS(F) ((F)->ready_ticks) 327#define FENCE_READY_TICKS_SIZE(F) ((F)->ready_ticks_size) 328#define FENCE_SCHED_NEXT(F) ((F)->sched_next) 329 330/* List of fences. */ 331typedef _list_t flist_t; 332#define FLIST_FENCE(L) (&(L)->u.fence) 333#define FLIST_NEXT(L) (_LIST_NEXT (L)) 334 335/* List of fences with pointer to the tail node. */ 336struct flist_tail_def 337{ 338 flist_t head; 339 flist_t *tailp; 340}; 341 342typedef struct flist_tail_def *flist_tail_t; 343#define FLIST_TAIL_HEAD(L) ((L)->head) 344#define FLIST_TAIL_TAILP(L) ((L)->tailp) 345 346/* List node information. A list node can be any of the types above. */ 347struct _list_node 348{ 349 _list_t next; 350 351 union 352 { 353 rtx x; 354 insn_t insn; 355 struct _bnd bnd; 356 expr_def expr; 357 struct _fence fence; 358 struct _def def; 359 void *data; 360 } u; 361}; 362 363 364/* _list_t functions. 365 All of _*list_* functions are used through accessor macros, thus 366 we can't move them in sel-sched-ir.c. */ 367extern alloc_pool sched_lists_pool; 368 369static inline _list_t 370_list_alloc (void) 371{ 372 return (_list_t) pool_alloc (sched_lists_pool); 373} 374 375static inline void 376_list_add (_list_t *lp) 377{ 378 _list_t l = _list_alloc (); 379 380 _LIST_NEXT (l) = *lp; 381 *lp = l; 382} 383 384static inline void 385_list_remove_nofree (_list_t *lp) 386{ 387 _list_t n = *lp; 388 389 *lp = _LIST_NEXT (n); 390} 391 392static inline void 393_list_remove (_list_t *lp) 394{ 395 _list_t n = *lp; 396 397 *lp = _LIST_NEXT (n); 398 pool_free (sched_lists_pool, n); 399} 400 401static inline void 402_list_clear (_list_t *l) 403{ 404 while (*l) 405 _list_remove (l); 406} 407 408 409/* List iterator backend. */ 410struct _list_iterator 411{ 412 /* The list we're iterating. */ 413 _list_t *lp; 414 415 /* True when this iterator supprts removing. */ 416 bool can_remove_p; 417 418 /* True when we've actually removed something. */ 419 bool removed_p; 420}; 421 422static inline void 423_list_iter_start (_list_iterator *ip, _list_t *lp, bool can_remove_p) 424{ 425 ip->lp = lp; 426 ip->can_remove_p = can_remove_p; 427 ip->removed_p = false; 428} 429 430static inline void 431_list_iter_next (_list_iterator *ip) 432{ 433 if (!ip->removed_p) 434 ip->lp = &_LIST_NEXT (*ip->lp); 435 else 436 ip->removed_p = false; 437} 438 439static inline void 440_list_iter_remove (_list_iterator *ip) 441{ 442 gcc_assert (!ip->removed_p && ip->can_remove_p); 443 _list_remove (ip->lp); 444 ip->removed_p = true; 445} 446 447static inline void 448_list_iter_remove_nofree (_list_iterator *ip) 449{ 450 gcc_assert (!ip->removed_p && ip->can_remove_p); 451 _list_remove_nofree (ip->lp); 452 ip->removed_p = true; 453} 454 455/* General macros to traverse a list. FOR_EACH_* interfaces are 456 implemented using these. */ 457#define _FOR_EACH(TYPE, ELEM, I, L) \ 458 for (_list_iter_start (&(I), &(L), false); \ 459 _list_iter_cond_##TYPE (*(I).lp, &(ELEM)); \ 460 _list_iter_next (&(I))) 461 462#define _FOR_EACH_1(TYPE, ELEM, I, LP) \ 463 for (_list_iter_start (&(I), (LP), true); \ 464 _list_iter_cond_##TYPE (*(I).lp, &(ELEM)); \ 465 _list_iter_next (&(I))) 466 467 468/* _xlist_t functions. */ 469 470static inline void 471_xlist_add (_xlist_t *lp, rtx x) 472{ 473 _list_add (lp); 474 _XLIST_X (*lp) = x; 475} 476 477#define _xlist_remove(LP) (_list_remove (LP)) 478#define _xlist_clear(LP) (_list_clear (LP)) 479 480static inline bool 481_xlist_is_in_p (_xlist_t l, rtx x) 482{ 483 while (l) 484 { 485 if (_XLIST_X (l) == x) 486 return true; 487 l = _XLIST_NEXT (l); 488 } 489 490 return false; 491} 492 493/* Used through _FOR_EACH. */ 494static inline bool 495_list_iter_cond_x (_xlist_t l, rtx *xp) 496{ 497 if (l) 498 { 499 *xp = _XLIST_X (l); 500 return true; 501 } 502 503 return false; 504} 505 506#define _xlist_iter_remove(IP) (_list_iter_remove (IP)) 507 508typedef _list_iterator _xlist_iterator; 509#define _FOR_EACH_X(X, I, L) _FOR_EACH (x, (X), (I), (L)) 510#define _FOR_EACH_X_1(X, I, LP) _FOR_EACH_1 (x, (X), (I), (LP)) 511 512 513/* ilist_t functions. */ 514 515static inline void 516ilist_add (ilist_t *lp, insn_t insn) 517{ 518 _list_add (lp); 519 ILIST_INSN (*lp) = insn; 520} 521#define ilist_remove(LP) (_list_remove (LP)) 522#define ilist_clear(LP) (_list_clear (LP)) 523 524static inline bool 525ilist_is_in_p (ilist_t l, insn_t insn) 526{ 527 while (l) 528 { 529 if (ILIST_INSN (l) == insn) 530 return true; 531 l = ILIST_NEXT (l); 532 } 533 534 return false; 535} 536 537/* Used through _FOR_EACH. */ 538static inline bool 539_list_iter_cond_insn (ilist_t l, insn_t *ip) 540{ 541 if (l) 542 { 543 *ip = ILIST_INSN (l); 544 return true; 545 } 546 547 return false; 548} 549 550#define ilist_iter_remove(IP) (_list_iter_remove (IP)) 551 552typedef _list_iterator ilist_iterator; 553#define FOR_EACH_INSN(INSN, I, L) _FOR_EACH (insn, (INSN), (I), (L)) 554#define FOR_EACH_INSN_1(INSN, I, LP) _FOR_EACH_1 (insn, (INSN), (I), (LP)) 555 556 557/* Av set iterators. */ 558typedef _list_iterator av_set_iterator; 559#define FOR_EACH_EXPR(EXPR, I, AV) _FOR_EACH (expr, (EXPR), (I), (AV)) 560#define FOR_EACH_EXPR_1(EXPR, I, AV) _FOR_EACH_1 (expr, (EXPR), (I), (AV)) 561 562inline bool 563_list_iter_cond_expr (av_set_t av, expr_t *exprp) 564{ 565 if (av) 566 { 567 *exprp = _AV_SET_EXPR (av); 568 return true; 569 } 570 571 return false; 572} 573 574 575/* Def list iterators. */ 576typedef _list_t def_list_t; 577typedef _list_iterator def_list_iterator; 578 579#define DEF_LIST_NEXT(L) (_LIST_NEXT (L)) 580#define DEF_LIST_DEF(L) (&(L)->u.def) 581 582#define FOR_EACH_DEF(DEF, I, DEF_LIST) _FOR_EACH (def, (DEF), (I), (DEF_LIST)) 583 584static inline bool 585_list_iter_cond_def (def_list_t def_list, def_t *def) 586{ 587 if (def_list) 588 { 589 *def = DEF_LIST_DEF (def_list); 590 return true; 591 } 592 593 return false; 594} 595 596 597/* InstructionData. Contains information about insn pattern. */ 598struct idata_def 599{ 600 /* Type of the insn. 601 o CALL_INSN - Call insn 602 o JUMP_INSN - Jump insn 603 o INSN - INSN that cannot be cloned 604 o USE - INSN that can be cloned 605 o SET - INSN that can be cloned and separable into lhs and rhs 606 o PC - simplejump. Insns that simply redirect control flow should not 607 have any dependencies. Sched-deps.c, though, might consider them as 608 producers or consumers of certain registers. To avoid that we handle 609 dependency for simple jumps ourselves. */ 610 int type; 611 612 /* If insn is a SET, this is its left hand side. */ 613 rtx lhs; 614 615 /* If insn is a SET, this is its right hand side. */ 616 rtx rhs; 617 618 /* Registers that are set/used by this insn. This info is now gathered 619 via sched-deps.c. The downside of this is that we also use live info 620 from flow that is accumulated in the basic blocks. These two infos 621 can be slightly inconsistent, hence in the beginning we make a pass 622 through CFG and calculating the conservative solution for the info in 623 basic blocks. When this scheduler will be switched to use dataflow, 624 this can be unified as df gives us both per basic block and per 625 instruction info. Actually, we don't do that pass and just hope 626 for the best. */ 627 regset reg_sets; 628 629 regset reg_clobbers; 630 631 regset reg_uses; 632}; 633 634#define IDATA_TYPE(ID) ((ID)->type) 635#define IDATA_LHS(ID) ((ID)->lhs) 636#define IDATA_RHS(ID) ((ID)->rhs) 637#define IDATA_REG_SETS(ID) ((ID)->reg_sets) 638#define IDATA_REG_USES(ID) ((ID)->reg_uses) 639#define IDATA_REG_CLOBBERS(ID) ((ID)->reg_clobbers) 640 641/* Type to represent all needed info to emit an insn. 642 This is a virtual equivalent of the insn. 643 Every insn in the stream has an associated vinsn. This is used 644 to reduce memory consumption basing on the fact that many insns 645 don't change through the scheduler. 646 647 vinsn can be either normal or unique. 648 * Normal vinsn is the one, that can be cloned multiple times and typically 649 corresponds to normal instruction. 650 651 * Unique vinsn derivates from CALL, ASM, JUMP (for a while) and other 652 unusual stuff. Such a vinsn is described by its INSN field, which is a 653 reference to the original instruction. */ 654struct vinsn_def 655{ 656 /* Associated insn. */ 657 rtx_insn *insn_rtx; 658 659 /* Its description. */ 660 struct idata_def id; 661 662 /* Hash of vinsn. It is computed either from pattern or from rhs using 663 hash_rtx. It is not placed in ID for faster compares. */ 664 unsigned hash; 665 666 /* Hash of the insn_rtx pattern. */ 667 unsigned hash_rtx; 668 669 /* Smart pointer counter. */ 670 int count; 671 672 /* Cached cost of the vinsn. To access it please use vinsn_cost (). */ 673 int cost; 674 675 /* Mark insns that may trap so we don't move them through jumps. */ 676 bool may_trap_p; 677}; 678 679#define VINSN_INSN_RTX(VI) ((VI)->insn_rtx) 680#define VINSN_PATTERN(VI) (PATTERN (VINSN_INSN_RTX (VI))) 681 682#define VINSN_ID(VI) (&((VI)->id)) 683#define VINSN_HASH(VI) ((VI)->hash) 684#define VINSN_HASH_RTX(VI) ((VI)->hash_rtx) 685#define VINSN_TYPE(VI) (IDATA_TYPE (VINSN_ID (VI))) 686#define VINSN_SEPARABLE_P(VI) (VINSN_TYPE (VI) == SET) 687#define VINSN_CLONABLE_P(VI) (VINSN_SEPARABLE_P (VI) || VINSN_TYPE (VI) == USE) 688#define VINSN_UNIQUE_P(VI) (!VINSN_CLONABLE_P (VI)) 689#define VINSN_LHS(VI) (IDATA_LHS (VINSN_ID (VI))) 690#define VINSN_RHS(VI) (IDATA_RHS (VINSN_ID (VI))) 691#define VINSN_REG_SETS(VI) (IDATA_REG_SETS (VINSN_ID (VI))) 692#define VINSN_REG_USES(VI) (IDATA_REG_USES (VINSN_ID (VI))) 693#define VINSN_REG_CLOBBERS(VI) (IDATA_REG_CLOBBERS (VINSN_ID (VI))) 694#define VINSN_COUNT(VI) ((VI)->count) 695#define VINSN_MAY_TRAP_P(VI) ((VI)->may_trap_p) 696 697 698/* An entry of the hashtable describing transformations happened when 699 moving up through an insn. */ 700struct transformed_insns 701{ 702 /* Previous vinsn. Used to find the proper element. */ 703 vinsn_t vinsn_old; 704 705 /* A new vinsn. */ 706 vinsn_t vinsn_new; 707 708 /* Speculative status. */ 709 ds_t ds; 710 711 /* Type of transformation happened. */ 712 enum local_trans_type type; 713 714 /* Whether a conflict on the target register happened. */ 715 BOOL_BITFIELD was_target_conflict : 1; 716 717 /* Whether a check was needed. */ 718 BOOL_BITFIELD needs_check : 1; 719}; 720 721/* Indexed by INSN_LUID, the collection of all data associated with 722 a single instruction that is in the stream. */ 723struct _sel_insn_data 724{ 725 /* The expression that contains vinsn for this insn and some 726 flow-sensitive data like priority. */ 727 expr_def expr; 728 729 /* If (WS_LEVEL == GLOBAL_LEVEL) then AV is empty. */ 730 int ws_level; 731 732 /* A number that helps in defining a traversing order for a region. */ 733 int seqno; 734 735 /* A liveness data computed above this insn. */ 736 regset live; 737 738 /* An INSN_UID bit is set when deps analysis result is already known. */ 739 bitmap analyzed_deps; 740 741 /* An INSN_UID bit is set when a hard dep was found, not set when 742 no dependence is found. This is meaningful only when the analyzed_deps 743 bitmap has its bit set. */ 744 bitmap found_deps; 745 746 /* An INSN_UID bit is set when this is a bookkeeping insn generated from 747 a parent with this uid. If a parent is a bookkeeping copy, all its 748 originators are transitively included in this set. */ 749 bitmap originators; 750 751 /* A hashtable caching the result of insn transformations through this one. */ 752 htab_t transformed_insns; 753 754 /* A context incapsulating this insn. */ 755 struct deps_desc deps_context; 756 757 /* This field is initialized at the beginning of scheduling and is used 758 to handle sched group instructions. If it is non-null, then it points 759 to the instruction, which should be forced to schedule next. Such 760 instructions are unique. */ 761 insn_t sched_next; 762 763 /* Cycle at which insn was scheduled. It is greater than zero if insn was 764 scheduled. This is used for bundling. */ 765 int sched_cycle; 766 767 /* Cycle at which insn's data will be fully ready. */ 768 int ready_cycle; 769 770 /* Speculations that are being checked by this insn. */ 771 ds_t spec_checked_ds; 772 773 /* Whether the live set valid or not. */ 774 BOOL_BITFIELD live_valid_p : 1; 775 /* Insn is an ASM. */ 776 BOOL_BITFIELD asm_p : 1; 777 778 /* True when an insn is scheduled after we've determined that a stall is 779 required. 780 This is used when emulating the Haifa scheduler for bundling. */ 781 BOOL_BITFIELD after_stall_p : 1; 782}; 783 784typedef struct _sel_insn_data sel_insn_data_def; 785typedef sel_insn_data_def *sel_insn_data_t; 786 787extern vec<sel_insn_data_def> s_i_d; 788 789/* Accessor macros for s_i_d. */ 790#define SID(INSN) (&s_i_d[INSN_LUID (INSN)]) 791#define SID_BY_UID(UID) (&s_i_d[LUID_BY_UID (UID)]) 792 793extern sel_insn_data_def insn_sid (insn_t); 794 795#define INSN_ASM_P(INSN) (SID (INSN)->asm_p) 796#define INSN_SCHED_NEXT(INSN) (SID (INSN)->sched_next) 797#define INSN_ANALYZED_DEPS(INSN) (SID (INSN)->analyzed_deps) 798#define INSN_FOUND_DEPS(INSN) (SID (INSN)->found_deps) 799#define INSN_DEPS_CONTEXT(INSN) (SID (INSN)->deps_context) 800#define INSN_ORIGINATORS(INSN) (SID (INSN)->originators) 801#define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators) 802#define INSN_TRANSFORMED_INSNS(INSN) (SID (INSN)->transformed_insns) 803 804#define INSN_EXPR(INSN) (&SID (INSN)->expr) 805#define INSN_LIVE(INSN) (SID (INSN)->live) 806#define INSN_LIVE_VALID_P(INSN) (SID (INSN)->live_valid_p) 807#define INSN_VINSN(INSN) (EXPR_VINSN (INSN_EXPR (INSN))) 808#define INSN_TYPE(INSN) (VINSN_TYPE (INSN_VINSN (INSN))) 809#define INSN_SIMPLEJUMP_P(INSN) (INSN_TYPE (INSN) == PC) 810#define INSN_LHS(INSN) (VINSN_LHS (INSN_VINSN (INSN))) 811#define INSN_RHS(INSN) (VINSN_RHS (INSN_VINSN (INSN))) 812#define INSN_REG_SETS(INSN) (VINSN_REG_SETS (INSN_VINSN (INSN))) 813#define INSN_REG_CLOBBERS(INSN) (VINSN_REG_CLOBBERS (INSN_VINSN (INSN))) 814#define INSN_REG_USES(INSN) (VINSN_REG_USES (INSN_VINSN (INSN))) 815#define INSN_SCHED_TIMES(INSN) (EXPR_SCHED_TIMES (INSN_EXPR (INSN))) 816#define INSN_SEQNO(INSN) (SID (INSN)->seqno) 817#define INSN_AFTER_STALL_P(INSN) (SID (INSN)->after_stall_p) 818#define INSN_SCHED_CYCLE(INSN) (SID (INSN)->sched_cycle) 819#define INSN_READY_CYCLE(INSN) (SID (INSN)->ready_cycle) 820#define INSN_SPEC_CHECKED_DS(INSN) (SID (INSN)->spec_checked_ds) 821 822/* A global level shows whether an insn is valid or not. */ 823extern int global_level; 824 825#define INSN_WS_LEVEL(INSN) (SID (INSN)->ws_level) 826 827extern av_set_t get_av_set (insn_t); 828extern int get_av_level (insn_t); 829 830#define AV_SET(INSN) (get_av_set (INSN)) 831#define AV_LEVEL(INSN) (get_av_level (INSN)) 832#define AV_SET_VALID_P(INSN) (AV_LEVEL (INSN) == global_level) 833 834/* A list of fences currently in the works. */ 835extern flist_t fences; 836 837/* A NOP pattern used as a placeholder for real insns. */ 838extern rtx nop_pattern; 839 840/* An insn that 'contained' in EXIT block. */ 841extern rtx_insn *exit_insn; 842 843/* Provide a separate luid for the insn. */ 844#define INSN_INIT_TODO_LUID (1) 845 846/* Initialize s_s_i_d. */ 847#define INSN_INIT_TODO_SSID (2) 848 849/* Initialize data for simplejump. */ 850#define INSN_INIT_TODO_SIMPLEJUMP (4) 851 852/* Return true if INSN is a local NOP. The nop is local in the sense that 853 it was emitted by the scheduler as a temporary insn and will soon be 854 deleted. These nops are identified by their pattern. */ 855#define INSN_NOP_P(INSN) (PATTERN (INSN) == nop_pattern) 856 857/* Return true if INSN is linked into instruction stream. 858 NB: It is impossible for INSN to have one field null and the other not 859 null: gcc_assert ((PREV_INSN (INSN) == NULL_RTX) 860 == (NEXT_INSN (INSN) == NULL_RTX)) is valid. */ 861#define INSN_IN_STREAM_P(INSN) (PREV_INSN (INSN) && NEXT_INSN (INSN)) 862 863/* Return true if INSN is in current fence. */ 864#define IN_CURRENT_FENCE_P(INSN) (flist_lookup (fences, INSN) != NULL) 865 866/* Marks loop as being considered for pipelining. */ 867#define MARK_LOOP_FOR_PIPELINING(LOOP) ((LOOP)->aux = (void *)(size_t)(1)) 868#define LOOP_MARKED_FOR_PIPELINING_P(LOOP) ((size_t)((LOOP)->aux)) 869 870/* Saved loop preheader to transfer when scheduling the loop. */ 871#define LOOP_PREHEADER_BLOCKS(LOOP) ((size_t)((LOOP)->aux) == 1 \ 872 ? NULL \ 873 : ((vec<basic_block> *) (LOOP)->aux)) 874#define SET_LOOP_PREHEADER_BLOCKS(LOOP,BLOCKS) ((LOOP)->aux \ 875 = (BLOCKS != NULL \ 876 ? BLOCKS \ 877 : (LOOP)->aux)) 878 879extern bitmap blocks_to_reschedule; 880 881 882/* A variable to track which part of rtx we are scanning in 883 sched-deps.c: sched_analyze_insn (). */ 884enum deps_where_t 885{ 886 DEPS_IN_INSN, 887 DEPS_IN_LHS, 888 DEPS_IN_RHS, 889 DEPS_IN_NOWHERE 890}; 891 892 893/* Per basic block data for the whole CFG. */ 894struct sel_global_bb_info_def 895{ 896 /* For each bb header this field contains a set of live registers. 897 For all other insns this field has a NULL. 898 We also need to know LV sets for the instructions, that are immediately 899 after the border of the region. */ 900 regset lv_set; 901 902 /* Status of LV_SET. 903 true - block has usable LV_SET. 904 false - block's LV_SET should be recomputed. */ 905 bool lv_set_valid_p; 906}; 907 908typedef sel_global_bb_info_def *sel_global_bb_info_t; 909 910 911/* Per basic block data. This array is indexed by basic block index. */ 912extern vec<sel_global_bb_info_def> sel_global_bb_info; 913 914extern void sel_extend_global_bb_info (void); 915extern void sel_finish_global_bb_info (void); 916 917/* Get data for BB. */ 918#define SEL_GLOBAL_BB_INFO(BB) \ 919 (&sel_global_bb_info[(BB)->index]) 920 921/* Access macros. */ 922#define BB_LV_SET(BB) (SEL_GLOBAL_BB_INFO (BB)->lv_set) 923#define BB_LV_SET_VALID_P(BB) (SEL_GLOBAL_BB_INFO (BB)->lv_set_valid_p) 924 925/* Per basic block data for the region. */ 926struct sel_region_bb_info_def 927{ 928 /* This insn stream is constructed in such a way that it should be 929 traversed by PREV_INSN field - (*not* NEXT_INSN). */ 930 rtx_insn *note_list; 931 932 /* Cached availability set at the beginning of a block. 933 See also AV_LEVEL () for conditions when this av_set can be used. */ 934 av_set_t av_set; 935 936 /* If (AV_LEVEL == GLOBAL_LEVEL) then AV is valid. */ 937 int av_level; 938}; 939 940typedef sel_region_bb_info_def *sel_region_bb_info_t; 941 942 943/* Per basic block data. This array is indexed by basic block index. */ 944extern vec<sel_region_bb_info_def> sel_region_bb_info; 945 946/* Get data for BB. */ 947#define SEL_REGION_BB_INFO(BB) (&sel_region_bb_info[(BB)->index]) 948 949/* Get BB's note_list. 950 A note_list is a list of various notes that was scattered across BB 951 before scheduling, and will be appended at the beginning of BB after 952 scheduling is finished. */ 953#define BB_NOTE_LIST(BB) (SEL_REGION_BB_INFO (BB)->note_list) 954 955#define BB_AV_SET(BB) (SEL_REGION_BB_INFO (BB)->av_set) 956#define BB_AV_LEVEL(BB) (SEL_REGION_BB_INFO (BB)->av_level) 957#define BB_AV_SET_VALID_P(BB) (BB_AV_LEVEL (BB) == global_level) 958 959/* Used in bb_in_ebb_p. */ 960extern bitmap_head *forced_ebb_heads; 961 962/* The loop nest being pipelined. */ 963extern struct loop *current_loop_nest; 964 965/* Saves pipelined blocks. Bitmap is indexed by bb->index. */ 966extern sbitmap bbs_pipelined; 967 968/* Various flags. */ 969extern bool enable_moveup_set_path_p; 970extern bool pipelining_p; 971extern bool bookkeeping_p; 972extern int max_insns_to_rename; 973extern bool preheader_removed; 974 975/* Software lookahead window size. 976 According to the results in Nakatani and Ebcioglu [1993], window size of 16 977 is enough to extract most ILP in integer code. */ 978#define MAX_WS (PARAM_VALUE (PARAM_SELSCHED_MAX_LOOKAHEAD)) 979 980extern regset sel_all_regs; 981 982 983/* Successor iterator backend. */ 984struct succ_iterator 985{ 986 /* True if we're at BB end. */ 987 bool bb_end; 988 989 /* An edge on which we're iterating. */ 990 edge e1; 991 992 /* The previous edge saved after skipping empty blocks. */ 993 edge e2; 994 995 /* Edge iterator used when there are successors in other basic blocks. */ 996 edge_iterator ei; 997 998 /* Successor block we're traversing. */ 999 basic_block bb; 1000 1001 /* Flags that are passed to the iterator. We return only successors 1002 that comply to these flags. */ 1003 short flags; 1004 1005 /* When flags include SUCCS_ALL, this will be set to the exact type 1006 of the successor we're traversing now. */ 1007 short current_flags; 1008 1009 /* If skip to loop exits, save here information about loop exits. */ 1010 int current_exit; 1011 vec<edge> loop_exits; 1012}; 1013 1014/* A structure returning all successor's information. */ 1015struct succs_info 1016{ 1017 /* Flags that these succcessors were computed with. */ 1018 short flags; 1019 1020 /* Successors that correspond to the flags. */ 1021 insn_vec_t succs_ok; 1022 1023 /* Their probabilities. As of now, we don't need this for other 1024 successors. */ 1025 vec<int> probs_ok; 1026 1027 /* Other successors. */ 1028 insn_vec_t succs_other; 1029 1030 /* Probability of all successors. */ 1031 int all_prob; 1032 1033 /* The number of all successors. */ 1034 int all_succs_n; 1035 1036 /* The number of good successors. */ 1037 int succs_ok_n; 1038}; 1039 1040/* Some needed definitions. */ 1041extern basic_block after_recovery; 1042 1043extern rtx_insn *sel_bb_head (basic_block); 1044extern rtx_insn *sel_bb_end (basic_block); 1045extern bool sel_bb_empty_p (basic_block); 1046extern bool in_current_region_p (basic_block); 1047 1048/* True when BB is a header of the inner loop. */ 1049static inline bool 1050inner_loop_header_p (basic_block bb) 1051{ 1052 struct loop *inner_loop; 1053 1054 if (!current_loop_nest) 1055 return false; 1056 1057 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1058 return false; 1059 1060 inner_loop = bb->loop_father; 1061 if (inner_loop == current_loop_nest) 1062 return false; 1063 1064 /* If successor belongs to another loop. */ 1065 if (bb == inner_loop->header 1066 && flow_bb_inside_loop_p (current_loop_nest, bb)) 1067 { 1068 /* Could be '=' here because of wrong loop depths. */ 1069 gcc_assert (loop_depth (inner_loop) >= loop_depth (current_loop_nest)); 1070 return true; 1071 } 1072 1073 return false; 1074} 1075 1076/* Return exit edges of LOOP, filtering out edges with the same dest bb. */ 1077static inline vec<edge> 1078get_loop_exit_edges_unique_dests (const struct loop *loop) 1079{ 1080 vec<edge> edges = vNULL; 1081 struct loop_exit *exit; 1082 1083 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun) 1084 && current_loops->state & LOOPS_HAVE_RECORDED_EXITS); 1085 1086 for (exit = loop->exits->next; exit->e; exit = exit->next) 1087 { 1088 int i; 1089 edge e; 1090 bool was_dest = false; 1091 1092 for (i = 0; edges.iterate (i, &e); i++) 1093 if (e->dest == exit->e->dest) 1094 { 1095 was_dest = true; 1096 break; 1097 } 1098 1099 if (!was_dest) 1100 edges.safe_push (exit->e); 1101 } 1102 return edges; 1103} 1104 1105static bool 1106sel_bb_empty_or_nop_p (basic_block bb) 1107{ 1108 insn_t first = sel_bb_head (bb), last; 1109 1110 if (first == NULL_RTX) 1111 return true; 1112 1113 if (!INSN_NOP_P (first)) 1114 return false; 1115 1116 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) 1117 return false; 1118 1119 last = sel_bb_end (bb); 1120 if (first != last) 1121 return false; 1122 1123 return true; 1124} 1125 1126/* Collect all loop exits recursively, skipping empty BBs between them. 1127 E.g. if BB is a loop header which has several loop exits, 1128 traverse all of them and if any of them turns out to be another loop header 1129 (after skipping empty BBs), add its loop exits to the resulting vector 1130 as well. */ 1131static inline vec<edge> 1132get_all_loop_exits (basic_block bb) 1133{ 1134 vec<edge> exits = vNULL; 1135 1136 /* If bb is empty, and we're skipping to loop exits, then 1137 consider bb as a possible gate to the inner loop now. */ 1138 while (sel_bb_empty_or_nop_p (bb) 1139 && in_current_region_p (bb) 1140 && EDGE_COUNT (bb->succs) > 0) 1141 { 1142 bb = single_succ (bb); 1143 1144 /* This empty block could only lead outside the region. */ 1145 gcc_assert (! in_current_region_p (bb)); 1146 } 1147 1148 /* And now check whether we should skip over inner loop. */ 1149 if (inner_loop_header_p (bb)) 1150 { 1151 struct loop *this_loop; 1152 struct loop *pred_loop = NULL; 1153 int i; 1154 edge e; 1155 1156 for (this_loop = bb->loop_father; 1157 this_loop && this_loop != current_loop_nest; 1158 this_loop = loop_outer (this_loop)) 1159 pred_loop = this_loop; 1160 1161 this_loop = pred_loop; 1162 gcc_assert (this_loop != NULL); 1163 1164 exits = get_loop_exit_edges_unique_dests (this_loop); 1165 1166 /* Traverse all loop headers. */ 1167 for (i = 0; exits.iterate (i, &e); i++) 1168 if (in_current_region_p (e->dest) 1169 || inner_loop_header_p (e->dest)) 1170 { 1171 vec<edge> next_exits = get_all_loop_exits (e->dest); 1172 1173 if (next_exits.exists ()) 1174 { 1175 int j; 1176 edge ne; 1177 1178 /* Add all loop exits for the current edge into the 1179 resulting vector. */ 1180 for (j = 0; next_exits.iterate (j, &ne); j++) 1181 exits.safe_push (ne); 1182 1183 /* Remove the original edge. */ 1184 exits.ordered_remove (i); 1185 1186 /* Decrease the loop counter so we won't skip anything. */ 1187 i--; 1188 continue; 1189 } 1190 } 1191 } 1192 1193 return exits; 1194} 1195 1196/* Flags to pass to compute_succs_info and FOR_EACH_SUCC. 1197 Any successor will fall into exactly one category. */ 1198 1199/* Include normal successors. */ 1200#define SUCCS_NORMAL (1) 1201 1202/* Include back-edge successors. */ 1203#define SUCCS_BACK (2) 1204 1205/* Include successors that are outside of the current region. */ 1206#define SUCCS_OUT (4) 1207 1208/* When pipelining of the outer loops is enabled, skip innermost loops 1209 to their exits. */ 1210#define SUCCS_SKIP_TO_LOOP_EXITS (8) 1211 1212/* Include all successors. */ 1213#define SUCCS_ALL (SUCCS_NORMAL | SUCCS_BACK | SUCCS_OUT) 1214 1215/* We need to return a succ_iterator to avoid 'unitialized' warning 1216 during bootstrap. */ 1217static inline succ_iterator 1218_succ_iter_start (insn_t *succp, insn_t insn, int flags) 1219{ 1220 succ_iterator i; 1221 1222 basic_block bb = BLOCK_FOR_INSN (insn); 1223 1224 gcc_assert (INSN_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn)); 1225 1226 i.flags = flags; 1227 1228 /* Avoid 'uninitialized' warning. */ 1229 *succp = NULL; 1230 i.e1 = NULL; 1231 i.e2 = NULL; 1232 i.bb = bb; 1233 i.current_flags = 0; 1234 i.current_exit = -1; 1235 i.loop_exits.create (0); 1236 1237 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun) && BB_END (bb) != insn) 1238 { 1239 i.bb_end = false; 1240 1241 /* Avoid 'uninitialized' warning. */ 1242 i.ei.index = 0; 1243 i.ei.container = 0; 1244 } 1245 else 1246 { 1247 i.ei = ei_start (bb->succs); 1248 i.bb_end = true; 1249 } 1250 1251 return i; 1252} 1253 1254static inline bool 1255_succ_iter_cond (succ_iterator *ip, insn_t *succp, insn_t insn, 1256 bool check (edge, succ_iterator *)) 1257{ 1258 if (!ip->bb_end) 1259 { 1260 /* When we're in a middle of a basic block, return 1261 the next insn immediately, but only when SUCCS_NORMAL is set. */ 1262 if (*succp != NULL || (ip->flags & SUCCS_NORMAL) == 0) 1263 return false; 1264 1265 *succp = NEXT_INSN (insn); 1266 ip->current_flags = SUCCS_NORMAL; 1267 return true; 1268 } 1269 else 1270 { 1271 while (1) 1272 { 1273 edge e_tmp = NULL; 1274 1275 /* First, try loop exits, if we have them. */ 1276 if (ip->loop_exits.exists ()) 1277 { 1278 do 1279 { 1280 ip->loop_exits.iterate (ip->current_exit, &e_tmp); 1281 ip->current_exit++; 1282 } 1283 while (e_tmp && !check (e_tmp, ip)); 1284 1285 if (!e_tmp) 1286 ip->loop_exits.release (); 1287 } 1288 1289 /* If we have found a successor, then great. */ 1290 if (e_tmp) 1291 { 1292 ip->e1 = e_tmp; 1293 break; 1294 } 1295 1296 /* If not, then try the next edge. */ 1297 while (ei_cond (ip->ei, &(ip->e1))) 1298 { 1299 basic_block bb = ip->e1->dest; 1300 1301 /* Consider bb as a possible loop header. */ 1302 if ((ip->flags & SUCCS_SKIP_TO_LOOP_EXITS) 1303 && flag_sel_sched_pipelining_outer_loops 1304 && (!in_current_region_p (bb) 1305 || BLOCK_TO_BB (ip->bb->index) 1306 < BLOCK_TO_BB (bb->index))) 1307 { 1308 /* Get all loop exits recursively. */ 1309 ip->loop_exits = get_all_loop_exits (bb); 1310 1311 if (ip->loop_exits.exists ()) 1312 { 1313 ip->current_exit = 0; 1314 /* Move the iterator now, because we won't do 1315 succ_iter_next until loop exits will end. */ 1316 ei_next (&(ip->ei)); 1317 break; 1318 } 1319 } 1320 1321 /* bb is not a loop header, check as usual. */ 1322 if (check (ip->e1, ip)) 1323 break; 1324 1325 ei_next (&(ip->ei)); 1326 } 1327 1328 /* If loop_exits are non null, we have found an inner loop; 1329 do one more iteration to fetch an edge from these exits. */ 1330 if (ip->loop_exits.exists ()) 1331 continue; 1332 1333 /* Otherwise, we've found an edge in a usual way. Break now. */ 1334 break; 1335 } 1336 1337 if (ip->e1) 1338 { 1339 basic_block bb = ip->e2->dest; 1340 1341 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == after_recovery) 1342 *succp = exit_insn; 1343 else 1344 { 1345 *succp = sel_bb_head (bb); 1346 1347 gcc_assert (ip->flags != SUCCS_NORMAL 1348 || *succp == NEXT_INSN (bb_note (bb))); 1349 gcc_assert (BLOCK_FOR_INSN (*succp) == bb); 1350 } 1351 1352 return true; 1353 } 1354 else 1355 return false; 1356 } 1357} 1358 1359static inline void 1360_succ_iter_next (succ_iterator *ip) 1361{ 1362 gcc_assert (!ip->e2 || ip->e1); 1363 1364 if (ip->bb_end && ip->e1 && !ip->loop_exits.exists ()) 1365 ei_next (&(ip->ei)); 1366} 1367 1368/* Returns true when E1 is an eligible successor edge, possibly skipping 1369 empty blocks. When E2P is not null, the resulting edge is written there. 1370 FLAGS are used to specify whether back edges and out-of-region edges 1371 should be considered. */ 1372static inline bool 1373_eligible_successor_edge_p (edge e1, succ_iterator *ip) 1374{ 1375 edge e2 = e1; 1376 basic_block bb; 1377 int flags = ip->flags; 1378 bool src_outside_rgn = !in_current_region_p (e1->src); 1379 1380 gcc_assert (flags != 0); 1381 1382 if (src_outside_rgn) 1383 { 1384 /* Any successor of the block that is outside current region is 1385 ineligible, except when we're skipping to loop exits. */ 1386 gcc_assert (flags & (SUCCS_OUT | SUCCS_SKIP_TO_LOOP_EXITS)); 1387 1388 if (flags & SUCCS_OUT) 1389 return false; 1390 } 1391 1392 bb = e2->dest; 1393 1394 /* Skip empty blocks, but be careful not to leave the region. */ 1395 while (1) 1396 { 1397 if (!sel_bb_empty_p (bb)) 1398 { 1399 edge ne; 1400 basic_block nbb; 1401 1402 if (!sel_bb_empty_or_nop_p (bb)) 1403 break; 1404 1405 ne = EDGE_SUCC (bb, 0); 1406 nbb = ne->dest; 1407 1408 if (!in_current_region_p (nbb) 1409 && !(flags & SUCCS_OUT)) 1410 break; 1411 1412 e2 = ne; 1413 bb = nbb; 1414 continue; 1415 } 1416 1417 if (!in_current_region_p (bb) 1418 && !(flags & SUCCS_OUT)) 1419 return false; 1420 1421 if (EDGE_COUNT (bb->succs) == 0) 1422 return false; 1423 1424 e2 = EDGE_SUCC (bb, 0); 1425 bb = e2->dest; 1426 } 1427 1428 /* Save the second edge for later checks. */ 1429 ip->e2 = e2; 1430 1431 if (in_current_region_p (bb)) 1432 { 1433 /* BLOCK_TO_BB sets topological order of the region here. 1434 It is important to use real predecessor here, which is ip->bb, 1435 as we may well have e1->src outside current region, 1436 when skipping to loop exits. */ 1437 bool succeeds_in_top_order = (BLOCK_TO_BB (ip->bb->index) 1438 < BLOCK_TO_BB (bb->index)); 1439 1440 /* This is true for the all cases except the last one. */ 1441 ip->current_flags = SUCCS_NORMAL; 1442 1443 /* We are advancing forward in the region, as usual. */ 1444 if (succeeds_in_top_order) 1445 { 1446 /* We are skipping to loop exits here. */ 1447 gcc_assert (!src_outside_rgn 1448 || flag_sel_sched_pipelining_outer_loops); 1449 return !!(flags & SUCCS_NORMAL); 1450 } 1451 1452 /* This is a back edge. During pipelining we ignore back edges, 1453 but only when it leads to the same loop. It can lead to the header 1454 of the outer loop, which will also be the preheader of 1455 the current loop. */ 1456 if (pipelining_p 1457 && e1->src->loop_father == bb->loop_father) 1458 return !!(flags & SUCCS_NORMAL); 1459 1460 /* A back edge should be requested explicitly. */ 1461 ip->current_flags = SUCCS_BACK; 1462 return !!(flags & SUCCS_BACK); 1463 } 1464 1465 ip->current_flags = SUCCS_OUT; 1466 return !!(flags & SUCCS_OUT); 1467} 1468 1469#define FOR_EACH_SUCC_1(SUCC, ITER, INSN, FLAGS) \ 1470 for ((ITER) = _succ_iter_start (&(SUCC), (INSN), (FLAGS)); \ 1471 _succ_iter_cond (&(ITER), &(SUCC), (INSN), _eligible_successor_edge_p); \ 1472 _succ_iter_next (&(ITER))) 1473 1474#define FOR_EACH_SUCC(SUCC, ITER, INSN) \ 1475 FOR_EACH_SUCC_1 (SUCC, ITER, INSN, SUCCS_NORMAL) 1476 1477/* Return the current edge along which a successor was built. */ 1478#define SUCC_ITER_EDGE(ITER) ((ITER)->e1) 1479 1480/* Return the next block of BB not running into inconsistencies. */ 1481static inline basic_block 1482bb_next_bb (basic_block bb) 1483{ 1484 switch (EDGE_COUNT (bb->succs)) 1485 { 1486 case 0: 1487 return bb->next_bb; 1488 1489 case 1: 1490 return single_succ (bb); 1491 1492 case 2: 1493 return FALLTHRU_EDGE (bb)->dest; 1494 1495 default: 1496 return bb->next_bb; 1497 } 1498 1499 gcc_unreachable (); 1500} 1501 1502 1503 1504/* Functions that are used in sel-sched.c. */ 1505 1506/* List functions. */ 1507extern ilist_t ilist_copy (ilist_t); 1508extern ilist_t ilist_invert (ilist_t); 1509extern void blist_add (blist_t *, insn_t, ilist_t, deps_t); 1510extern void blist_remove (blist_t *); 1511extern void flist_tail_init (flist_tail_t); 1512 1513extern fence_t flist_lookup (flist_t, insn_t); 1514extern void flist_clear (flist_t *); 1515extern void def_list_add (def_list_t *, insn_t, bool); 1516 1517/* Target context functions. */ 1518extern tc_t create_target_context (bool); 1519extern void set_target_context (tc_t); 1520extern void reset_target_context (tc_t, bool); 1521 1522/* Deps context functions. */ 1523extern void advance_deps_context (deps_t, insn_t); 1524 1525/* Fences functions. */ 1526extern void init_fences (insn_t); 1527extern void add_clean_fence_to_fences (flist_tail_t, insn_t, fence_t); 1528extern void add_dirty_fence_to_fences (flist_tail_t, insn_t, fence_t); 1529extern void move_fence_to_fences (flist_t, flist_tail_t); 1530 1531/* Pool functions. */ 1532extern regset get_regset_from_pool (void); 1533extern regset get_clear_regset_from_pool (void); 1534extern void return_regset_to_pool (regset); 1535extern void free_regset_pool (void); 1536 1537extern insn_t get_nop_from_pool (insn_t); 1538extern void return_nop_to_pool (insn_t, bool); 1539extern void free_nop_pool (void); 1540 1541/* Vinsns functions. */ 1542extern bool vinsn_separable_p (vinsn_t); 1543extern bool vinsn_cond_branch_p (vinsn_t); 1544extern void recompute_vinsn_lhs_rhs (vinsn_t); 1545extern int sel_vinsn_cost (vinsn_t); 1546extern insn_t sel_gen_insn_from_rtx_after (rtx, expr_t, int, insn_t); 1547extern insn_t sel_gen_recovery_insn_from_rtx_after (rtx, expr_t, int, insn_t); 1548extern insn_t sel_gen_insn_from_expr_after (expr_t, vinsn_t, int, insn_t); 1549extern insn_t sel_move_insn (expr_t, int, insn_t); 1550extern void vinsn_attach (vinsn_t); 1551extern void vinsn_detach (vinsn_t); 1552extern vinsn_t vinsn_copy (vinsn_t, bool); 1553extern bool vinsn_equal_p (vinsn_t, vinsn_t); 1554 1555/* EXPR functions. */ 1556extern void copy_expr (expr_t, expr_t); 1557extern void copy_expr_onside (expr_t, expr_t); 1558extern void merge_expr_data (expr_t, expr_t, insn_t); 1559extern void merge_expr (expr_t, expr_t, insn_t); 1560extern void clear_expr (expr_t); 1561extern unsigned expr_dest_regno (expr_t); 1562extern rtx expr_dest_reg (expr_t); 1563extern int find_in_history_vect (vec<expr_history_def> , 1564 rtx, vinsn_t, bool); 1565extern void insert_in_history_vect (vec<expr_history_def> *, 1566 unsigned, enum local_trans_type, 1567 vinsn_t, vinsn_t, ds_t); 1568extern void mark_unavailable_targets (av_set_t, av_set_t, regset); 1569extern int speculate_expr (expr_t, ds_t); 1570 1571/* Av set functions. */ 1572extern void av_set_add (av_set_t *, expr_t); 1573extern void av_set_iter_remove (av_set_iterator *); 1574extern expr_t av_set_lookup (av_set_t, vinsn_t); 1575extern expr_t merge_with_other_exprs (av_set_t *, av_set_iterator *, expr_t); 1576extern bool av_set_is_in_p (av_set_t, vinsn_t); 1577extern av_set_t av_set_copy (av_set_t); 1578extern void av_set_union_and_clear (av_set_t *, av_set_t *, insn_t); 1579extern void av_set_union_and_live (av_set_t *, av_set_t *, regset, regset, insn_t); 1580extern void av_set_clear (av_set_t *); 1581extern void av_set_leave_one_nonspec (av_set_t *); 1582extern expr_t av_set_element (av_set_t, int); 1583extern void av_set_substract_cond_branches (av_set_t *); 1584extern void av_set_split_usefulness (av_set_t, int, int); 1585extern void av_set_code_motion_filter (av_set_t *, av_set_t); 1586 1587extern void sel_save_haifa_priorities (void); 1588 1589extern void sel_init_global_and_expr (bb_vec_t); 1590extern void sel_finish_global_and_expr (void); 1591 1592extern regset compute_live (insn_t); 1593extern bool register_unavailable_p (regset, rtx); 1594 1595/* Dependence analysis functions. */ 1596extern void sel_clear_has_dependence (void); 1597extern ds_t has_dependence_p (expr_t, insn_t, ds_t **); 1598 1599extern int tick_check_p (expr_t, deps_t, fence_t); 1600 1601/* Functions to work with insns. */ 1602extern bool lhs_of_insn_equals_to_dest_p (insn_t, rtx); 1603extern bool insn_eligible_for_subst_p (insn_t); 1604extern void get_dest_and_mode (rtx, rtx *, machine_mode *); 1605 1606extern bool bookkeeping_can_be_created_if_moved_through_p (insn_t); 1607extern bool sel_remove_insn (insn_t, bool, bool); 1608extern bool bb_header_p (insn_t); 1609extern void sel_init_invalid_data_sets (insn_t); 1610extern bool insn_at_boundary_p (insn_t); 1611 1612/* Basic block and CFG functions. */ 1613 1614extern rtx_insn *sel_bb_head (basic_block); 1615extern bool sel_bb_head_p (insn_t); 1616extern rtx_insn *sel_bb_end (basic_block); 1617extern bool sel_bb_end_p (insn_t); 1618extern bool sel_bb_empty_p (basic_block); 1619 1620extern bool in_current_region_p (basic_block); 1621extern basic_block fallthru_bb_of_jump (const rtx_insn *); 1622 1623extern void sel_init_bbs (bb_vec_t); 1624extern void sel_finish_bbs (void); 1625 1626extern struct succs_info * compute_succs_info (insn_t, short); 1627extern void free_succs_info (struct succs_info *); 1628extern bool sel_insn_has_single_succ_p (insn_t, int); 1629extern bool sel_num_cfg_preds_gt_1 (insn_t); 1630extern int get_seqno_by_preds (rtx_insn *); 1631 1632extern bool bb_ends_ebb_p (basic_block); 1633extern bool in_same_ebb_p (insn_t, insn_t); 1634 1635extern bool tidy_control_flow (basic_block, bool); 1636extern void free_bb_note_pool (void); 1637 1638extern void purge_empty_blocks (void); 1639extern basic_block sel_split_edge (edge); 1640extern basic_block sel_create_recovery_block (insn_t); 1641extern bool sel_redirect_edge_and_branch (edge, basic_block); 1642extern void sel_redirect_edge_and_branch_force (edge, basic_block); 1643extern void sel_init_pipelining (void); 1644extern void sel_finish_pipelining (void); 1645extern void sel_sched_region (int); 1646extern loop_p get_loop_nest_for_rgn (unsigned int); 1647extern bool considered_for_pipelining_p (struct loop *); 1648extern void make_region_from_loop_preheader (vec<basic_block> *&); 1649extern void sel_add_loop_preheaders (bb_vec_t *); 1650extern bool sel_is_loop_preheader_p (basic_block); 1651extern void clear_outdated_rtx_info (basic_block); 1652extern void free_data_sets (basic_block); 1653extern void exchange_data_sets (basic_block, basic_block); 1654extern void copy_data_sets (basic_block, basic_block); 1655 1656extern void sel_register_cfg_hooks (void); 1657extern void sel_unregister_cfg_hooks (void); 1658 1659/* Expression transformation routines. */ 1660extern rtx_insn *create_insn_rtx_from_pattern (rtx, rtx); 1661extern vinsn_t create_vinsn_from_insn_rtx (rtx_insn *, bool); 1662extern rtx_insn *create_copy_of_insn_rtx (rtx); 1663extern void change_vinsn_in_expr (expr_t, vinsn_t); 1664 1665/* Various initialization functions. */ 1666extern void init_lv_sets (void); 1667extern void free_lv_sets (void); 1668extern void setup_nop_and_exit_insns (void); 1669extern void free_nop_and_exit_insns (void); 1670extern void free_data_for_scheduled_insn (insn_t); 1671extern void setup_nop_vinsn (void); 1672extern void free_nop_vinsn (void); 1673extern void sel_set_sched_flags (void); 1674extern void sel_setup_sched_infos (void); 1675extern void alloc_sched_pools (void); 1676extern void free_sched_pools (void); 1677 1678#endif /* GCC_SEL_SCHED_IR_H */ 1679 1680 1681 1682 1683 1684 1685 1686 1687