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