1 /* Instruction scheduling pass. Selective scheduler and pipeliner. 2 Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it under 7 the terms of the GNU General Public License as published by the Free 8 Software Foundation; either version 3, or (at your option) any later 9 version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "tm.h" 24 #include "toplev.h" 25 #include "rtl.h" 26 #include "tm_p.h" 27 #include "hard-reg-set.h" 28 #include "regs.h" 29 #include "function.h" 30 #include "flags.h" 31 #include "insn-config.h" 32 #include "insn-attr.h" 33 #include "except.h" 34 #include "toplev.h" 35 #include "recog.h" 36 #include "params.h" 37 #include "target.h" 38 #include "timevar.h" 39 #include "tree-pass.h" 40 #include "sched-int.h" 41 #include "ggc.h" 42 #include "tree.h" 43 #include "vec.h" 44 #include "langhooks.h" 45 #include "rtlhooks-def.h" 46 47 #ifdef INSN_SCHEDULING 48 #include "sel-sched-ir.h" 49 /* We don't have to use it except for sel_print_insn. */ 50 #include "sel-sched-dump.h" 51 52 /* A vector holding bb info for whole scheduling pass. */ 53 VEC(sel_global_bb_info_def, heap) *sel_global_bb_info = NULL; 54 55 /* A vector holding bb info. */ 56 VEC(sel_region_bb_info_def, heap) *sel_region_bb_info = NULL; 57 58 /* A pool for allocating all lists. */ 59 alloc_pool sched_lists_pool; 60 61 /* This contains information about successors for compute_av_set. */ 62 struct succs_info current_succs; 63 64 /* Data structure to describe interaction with the generic scheduler utils. */ 65 static struct common_sched_info_def sel_common_sched_info; 66 67 /* The loop nest being pipelined. */ 68 struct loop *current_loop_nest; 69 70 /* LOOP_NESTS is a vector containing the corresponding loop nest for 71 each region. */ 72 static VEC(loop_p, heap) *loop_nests = NULL; 73 74 /* Saves blocks already in loop regions, indexed by bb->index. */ 75 static sbitmap bbs_in_loop_rgns = NULL; 76 77 /* CFG hooks that are saved before changing create_basic_block hook. */ 78 static struct cfg_hooks orig_cfg_hooks; 79 80 81 /* Array containing reverse topological index of function basic blocks, 82 indexed by BB->INDEX. */ 83 static int *rev_top_order_index = NULL; 84 85 /* Length of the above array. */ 86 static int rev_top_order_index_len = -1; 87 88 /* A regset pool structure. */ 89 static struct 90 { 91 /* The stack to which regsets are returned. */ 92 regset *v; 93 94 /* Its pointer. */ 95 int n; 96 97 /* Its size. */ 98 int s; 99 100 /* In VV we save all generated regsets so that, when destructing the 101 pool, we can compare it with V and check that every regset was returned 102 back to pool. */ 103 regset *vv; 104 105 /* The pointer of VV stack. */ 106 int nn; 107 108 /* Its size. */ 109 int ss; 110 111 /* The difference between allocated and returned regsets. */ 112 int diff; 113 } regset_pool = { NULL, 0, 0, NULL, 0, 0, 0 }; 114 115 /* This represents the nop pool. */ 116 static struct 117 { 118 /* The vector which holds previously emitted nops. */ 119 insn_t *v; 120 121 /* Its pointer. */ 122 int n; 123 124 /* Its size. */ 125 int s; 126 } nop_pool = { NULL, 0, 0 }; 127 128 /* The pool for basic block notes. */ 129 static rtx_vec_t bb_note_pool; 130 131 /* A NOP pattern used to emit placeholder insns. */ 132 rtx nop_pattern = NULL_RTX; 133 /* A special instruction that resides in EXIT_BLOCK. 134 EXIT_INSN is successor of the insns that lead to EXIT_BLOCK. */ 135 rtx exit_insn = NULL_RTX; 136 137 /* TRUE if while scheduling current region, which is loop, its preheader 138 was removed. */ 139 bool preheader_removed = false; 140 141 142 /* Forward static declarations. */ 143 static void fence_clear (fence_t); 144 145 static void deps_init_id (idata_t, insn_t, bool); 146 static void init_id_from_df (idata_t, insn_t, bool); 147 static expr_t set_insn_init (expr_t, vinsn_t, int); 148 149 static void cfg_preds (basic_block, insn_t **, int *); 150 static void prepare_insn_expr (insn_t, int); 151 static void free_history_vect (VEC (expr_history_def, heap) **); 152 153 static void move_bb_info (basic_block, basic_block); 154 static void remove_empty_bb (basic_block, bool); 155 static void sel_merge_blocks (basic_block, basic_block); 156 static void sel_remove_loop_preheader (void); 157 static bool bb_has_removable_jump_to_p (basic_block, basic_block); 158 159 static bool insn_is_the_only_one_in_bb_p (insn_t); 160 static void create_initial_data_sets (basic_block); 161 162 static void free_av_set (basic_block); 163 static void invalidate_av_set (basic_block); 164 static void extend_insn_data (void); 165 static void sel_init_new_insn (insn_t, int); 166 static void finish_insns (void); 167 168 /* Various list functions. */ 169 170 /* Copy an instruction list L. */ 171 ilist_t 172 ilist_copy (ilist_t l) 173 { 174 ilist_t head = NULL, *tailp = &head; 175 176 while (l) 177 { 178 ilist_add (tailp, ILIST_INSN (l)); 179 tailp = &ILIST_NEXT (*tailp); 180 l = ILIST_NEXT (l); 181 } 182 183 return head; 184 } 185 186 /* Invert an instruction list L. */ 187 ilist_t 188 ilist_invert (ilist_t l) 189 { 190 ilist_t res = NULL; 191 192 while (l) 193 { 194 ilist_add (&res, ILIST_INSN (l)); 195 l = ILIST_NEXT (l); 196 } 197 198 return res; 199 } 200 201 /* Add a new boundary to the LP list with parameters TO, PTR, and DC. */ 202 void 203 blist_add (blist_t *lp, insn_t to, ilist_t ptr, deps_t dc) 204 { 205 bnd_t bnd; 206 207 _list_add (lp); 208 bnd = BLIST_BND (*lp); 209 210 BND_TO (bnd) = to; 211 BND_PTR (bnd) = ptr; 212 BND_AV (bnd) = NULL; 213 BND_AV1 (bnd) = NULL; 214 BND_DC (bnd) = dc; 215 } 216 217 /* Remove the list note pointed to by LP. */ 218 void 219 blist_remove (blist_t *lp) 220 { 221 bnd_t b = BLIST_BND (*lp); 222 223 av_set_clear (&BND_AV (b)); 224 av_set_clear (&BND_AV1 (b)); 225 ilist_clear (&BND_PTR (b)); 226 227 _list_remove (lp); 228 } 229 230 /* Init a fence tail L. */ 231 void 232 flist_tail_init (flist_tail_t l) 233 { 234 FLIST_TAIL_HEAD (l) = NULL; 235 FLIST_TAIL_TAILP (l) = &FLIST_TAIL_HEAD (l); 236 } 237 238 /* Try to find fence corresponding to INSN in L. */ 239 fence_t 240 flist_lookup (flist_t l, insn_t insn) 241 { 242 while (l) 243 { 244 if (FENCE_INSN (FLIST_FENCE (l)) == insn) 245 return FLIST_FENCE (l); 246 247 l = FLIST_NEXT (l); 248 } 249 250 return NULL; 251 } 252 253 /* Init the fields of F before running fill_insns. */ 254 static void 255 init_fence_for_scheduling (fence_t f) 256 { 257 FENCE_BNDS (f) = NULL; 258 FENCE_PROCESSED_P (f) = false; 259 FENCE_SCHEDULED_P (f) = false; 260 } 261 262 /* Add new fence consisting of INSN and STATE to the list pointed to by LP. */ 263 static void 264 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc, 265 insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns, 266 int *ready_ticks, int ready_ticks_size, insn_t sched_next, 267 int cycle, int cycle_issued_insns, int issue_more, 268 bool starts_cycle_p, bool after_stall_p) 269 { 270 fence_t f; 271 272 _list_add (lp); 273 f = FLIST_FENCE (*lp); 274 275 FENCE_INSN (f) = insn; 276 277 gcc_assert (state != NULL); 278 FENCE_STATE (f) = state; 279 280 FENCE_CYCLE (f) = cycle; 281 FENCE_ISSUED_INSNS (f) = cycle_issued_insns; 282 FENCE_STARTS_CYCLE_P (f) = starts_cycle_p; 283 FENCE_AFTER_STALL_P (f) = after_stall_p; 284 285 gcc_assert (dc != NULL); 286 FENCE_DC (f) = dc; 287 288 gcc_assert (tc != NULL || targetm.sched.alloc_sched_context == NULL); 289 FENCE_TC (f) = tc; 290 291 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn; 292 FENCE_ISSUE_MORE (f) = issue_more; 293 FENCE_EXECUTING_INSNS (f) = executing_insns; 294 FENCE_READY_TICKS (f) = ready_ticks; 295 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size; 296 FENCE_SCHED_NEXT (f) = sched_next; 297 298 init_fence_for_scheduling (f); 299 } 300 301 /* Remove the head node of the list pointed to by LP. */ 302 static void 303 flist_remove (flist_t *lp) 304 { 305 if (FENCE_INSN (FLIST_FENCE (*lp))) 306 fence_clear (FLIST_FENCE (*lp)); 307 _list_remove (lp); 308 } 309 310 /* Clear the fence list pointed to by LP. */ 311 void 312 flist_clear (flist_t *lp) 313 { 314 while (*lp) 315 flist_remove (lp); 316 } 317 318 /* Add ORIGINAL_INSN the def list DL honoring CROSSES_CALL. */ 319 void 320 def_list_add (def_list_t *dl, insn_t original_insn, bool crosses_call) 321 { 322 def_t d; 323 324 _list_add (dl); 325 d = DEF_LIST_DEF (*dl); 326 327 d->orig_insn = original_insn; 328 d->crosses_call = crosses_call; 329 } 330 331 332 /* Functions to work with target contexts. */ 333 334 /* Bulk target context. It is convenient for debugging purposes to ensure 335 that there are no uninitialized (null) target contexts. */ 336 static tc_t bulk_tc = (tc_t) 1; 337 338 /* Target hooks wrappers. In the future we can provide some default 339 implementations for them. */ 340 341 /* Allocate a store for the target context. */ 342 static tc_t 343 alloc_target_context (void) 344 { 345 return (targetm.sched.alloc_sched_context 346 ? targetm.sched.alloc_sched_context () : bulk_tc); 347 } 348 349 /* Init target context TC. 350 If CLEAN_P is true, then make TC as it is beginning of the scheduler. 351 Overwise, copy current backend context to TC. */ 352 static void 353 init_target_context (tc_t tc, bool clean_p) 354 { 355 if (targetm.sched.init_sched_context) 356 targetm.sched.init_sched_context (tc, clean_p); 357 } 358 359 /* Allocate and initialize a target context. Meaning of CLEAN_P is the same as 360 int init_target_context (). */ 361 tc_t 362 create_target_context (bool clean_p) 363 { 364 tc_t tc = alloc_target_context (); 365 366 init_target_context (tc, clean_p); 367 return tc; 368 } 369 370 /* Copy TC to the current backend context. */ 371 void 372 set_target_context (tc_t tc) 373 { 374 if (targetm.sched.set_sched_context) 375 targetm.sched.set_sched_context (tc); 376 } 377 378 /* TC is about to be destroyed. Free any internal data. */ 379 static void 380 clear_target_context (tc_t tc) 381 { 382 if (targetm.sched.clear_sched_context) 383 targetm.sched.clear_sched_context (tc); 384 } 385 386 /* Clear and free it. */ 387 static void 388 delete_target_context (tc_t tc) 389 { 390 clear_target_context (tc); 391 392 if (targetm.sched.free_sched_context) 393 targetm.sched.free_sched_context (tc); 394 } 395 396 /* Make a copy of FROM in TO. 397 NB: May be this should be a hook. */ 398 static void 399 copy_target_context (tc_t to, tc_t from) 400 { 401 tc_t tmp = create_target_context (false); 402 403 set_target_context (from); 404 init_target_context (to, false); 405 406 set_target_context (tmp); 407 delete_target_context (tmp); 408 } 409 410 /* Create a copy of TC. */ 411 static tc_t 412 create_copy_of_target_context (tc_t tc) 413 { 414 tc_t copy = alloc_target_context (); 415 416 copy_target_context (copy, tc); 417 418 return copy; 419 } 420 421 /* Clear TC and initialize it according to CLEAN_P. The meaning of CLEAN_P 422 is the same as in init_target_context (). */ 423 void 424 reset_target_context (tc_t tc, bool clean_p) 425 { 426 clear_target_context (tc); 427 init_target_context (tc, clean_p); 428 } 429 430 /* Functions to work with dependence contexts. 431 Dc (aka deps context, aka deps_t, aka struct deps_desc *) is short for dependence 432 context. It accumulates information about processed insns to decide if 433 current insn is dependent on the processed ones. */ 434 435 /* Make a copy of FROM in TO. */ 436 static void 437 copy_deps_context (deps_t to, deps_t from) 438 { 439 init_deps (to, false); 440 deps_join (to, from); 441 } 442 443 /* Allocate store for dep context. */ 444 static deps_t 445 alloc_deps_context (void) 446 { 447 return XNEW (struct deps_desc); 448 } 449 450 /* Allocate and initialize dep context. */ 451 static deps_t 452 create_deps_context (void) 453 { 454 deps_t dc = alloc_deps_context (); 455 456 init_deps (dc, false); 457 return dc; 458 } 459 460 /* Create a copy of FROM. */ 461 static deps_t 462 create_copy_of_deps_context (deps_t from) 463 { 464 deps_t to = alloc_deps_context (); 465 466 copy_deps_context (to, from); 467 return to; 468 } 469 470 /* Clean up internal data of DC. */ 471 static void 472 clear_deps_context (deps_t dc) 473 { 474 free_deps (dc); 475 } 476 477 /* Clear and free DC. */ 478 static void 479 delete_deps_context (deps_t dc) 480 { 481 clear_deps_context (dc); 482 free (dc); 483 } 484 485 /* Clear and init DC. */ 486 static void 487 reset_deps_context (deps_t dc) 488 { 489 clear_deps_context (dc); 490 init_deps (dc, false); 491 } 492 493 /* This structure describes the dependence analysis hooks for advancing 494 dependence context. */ 495 static struct sched_deps_info_def advance_deps_context_sched_deps_info = 496 { 497 NULL, 498 499 NULL, /* start_insn */ 500 NULL, /* finish_insn */ 501 NULL, /* start_lhs */ 502 NULL, /* finish_lhs */ 503 NULL, /* start_rhs */ 504 NULL, /* finish_rhs */ 505 haifa_note_reg_set, 506 haifa_note_reg_clobber, 507 haifa_note_reg_use, 508 NULL, /* note_mem_dep */ 509 NULL, /* note_dep */ 510 511 0, 0, 0 512 }; 513 514 /* Process INSN and add its impact on DC. */ 515 void 516 advance_deps_context (deps_t dc, insn_t insn) 517 { 518 sched_deps_info = &advance_deps_context_sched_deps_info; 519 deps_analyze_insn (dc, insn); 520 } 521 522 523 /* Functions to work with DFA states. */ 524 525 /* Allocate store for a DFA state. */ 526 static state_t 527 state_alloc (void) 528 { 529 return xmalloc (dfa_state_size); 530 } 531 532 /* Allocate and initialize DFA state. */ 533 static state_t 534 state_create (void) 535 { 536 state_t state = state_alloc (); 537 538 state_reset (state); 539 advance_state (state); 540 return state; 541 } 542 543 /* Free DFA state. */ 544 static void 545 state_free (state_t state) 546 { 547 free (state); 548 } 549 550 /* Make a copy of FROM in TO. */ 551 static void 552 state_copy (state_t to, state_t from) 553 { 554 memcpy (to, from, dfa_state_size); 555 } 556 557 /* Create a copy of FROM. */ 558 static state_t 559 state_create_copy (state_t from) 560 { 561 state_t to = state_alloc (); 562 563 state_copy (to, from); 564 return to; 565 } 566 567 568 /* Functions to work with fences. */ 569 570 /* Clear the fence. */ 571 static void 572 fence_clear (fence_t f) 573 { 574 state_t s = FENCE_STATE (f); 575 deps_t dc = FENCE_DC (f); 576 void *tc = FENCE_TC (f); 577 578 ilist_clear (&FENCE_BNDS (f)); 579 580 gcc_assert ((s != NULL && dc != NULL && tc != NULL) 581 || (s == NULL && dc == NULL && tc == NULL)); 582 583 if (s != NULL) 584 free (s); 585 586 if (dc != NULL) 587 delete_deps_context (dc); 588 589 if (tc != NULL) 590 delete_target_context (tc); 591 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f)); 592 free (FENCE_READY_TICKS (f)); 593 FENCE_READY_TICKS (f) = NULL; 594 } 595 596 /* Init a list of fences with successors of OLD_FENCE. */ 597 void 598 init_fences (insn_t old_fence) 599 { 600 insn_t succ; 601 succ_iterator si; 602 bool first = true; 603 int ready_ticks_size = get_max_uid () + 1; 604 605 FOR_EACH_SUCC_1 (succ, si, old_fence, 606 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS) 607 { 608 609 if (first) 610 first = false; 611 else 612 gcc_assert (flag_sel_sched_pipelining_outer_loops); 613 614 flist_add (&fences, succ, 615 state_create (), 616 create_deps_context () /* dc */, 617 create_target_context (true) /* tc */, 618 NULL_RTX /* last_scheduled_insn */, 619 NULL, /* executing_insns */ 620 XCNEWVEC (int, ready_ticks_size), /* ready_ticks */ 621 ready_ticks_size, 622 NULL_RTX /* sched_next */, 623 1 /* cycle */, 0 /* cycle_issued_insns */, 624 issue_rate, /* issue_more */ 625 1 /* starts_cycle_p */, 0 /* after_stall_p */); 626 } 627 } 628 629 /* Merges two fences (filling fields of fence F with resulting values) by 630 following rules: 1) state, target context and last scheduled insn are 631 propagated from fallthrough edge if it is available; 632 2) deps context and cycle is propagated from more probable edge; 633 3) all other fields are set to corresponding constant values. 634 635 INSN, STATE, DC, TC, LAST_SCHEDULED_INSN, EXECUTING_INSNS, 636 READY_TICKS, READY_TICKS_SIZE, SCHED_NEXT, CYCLE, ISSUE_MORE 637 and AFTER_STALL_P are the corresponding fields of the second fence. */ 638 static void 639 merge_fences (fence_t f, insn_t insn, 640 state_t state, deps_t dc, void *tc, 641 rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns, 642 int *ready_ticks, int ready_ticks_size, 643 rtx sched_next, int cycle, int issue_more, bool after_stall_p) 644 { 645 insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f); 646 647 gcc_assert (sel_bb_head_p (FENCE_INSN (f)) 648 && !sched_next && !FENCE_SCHED_NEXT (f)); 649 650 /* Check if we can decide which path fences came. 651 If we can't (or don't want to) - reset all. */ 652 if (last_scheduled_insn == NULL 653 || last_scheduled_insn_old == NULL 654 /* This is a case when INSN is reachable on several paths from 655 one insn (this can happen when pipelining of outer loops is on and 656 there are two edges: one going around of inner loop and the other - 657 right through it; in such case just reset everything). */ 658 || last_scheduled_insn == last_scheduled_insn_old) 659 { 660 state_reset (FENCE_STATE (f)); 661 state_free (state); 662 663 reset_deps_context (FENCE_DC (f)); 664 delete_deps_context (dc); 665 666 reset_target_context (FENCE_TC (f), true); 667 delete_target_context (tc); 668 669 if (cycle > FENCE_CYCLE (f)) 670 FENCE_CYCLE (f) = cycle; 671 672 FENCE_LAST_SCHEDULED_INSN (f) = NULL; 673 FENCE_ISSUE_MORE (f) = issue_rate; 674 VEC_free (rtx, gc, executing_insns); 675 free (ready_ticks); 676 if (FENCE_EXECUTING_INSNS (f)) 677 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0, 678 VEC_length (rtx, FENCE_EXECUTING_INSNS (f))); 679 if (FENCE_READY_TICKS (f)) 680 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f)); 681 } 682 else 683 { 684 edge edge_old = NULL, edge_new = NULL; 685 edge candidate; 686 succ_iterator si; 687 insn_t succ; 688 689 /* Find fallthrough edge. */ 690 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb); 691 candidate = find_fallthru_edge (BLOCK_FOR_INSN (insn)->prev_bb); 692 693 if (!candidate 694 || (candidate->src != BLOCK_FOR_INSN (last_scheduled_insn) 695 && candidate->src != BLOCK_FOR_INSN (last_scheduled_insn_old))) 696 { 697 /* No fallthrough edge leading to basic block of INSN. */ 698 state_reset (FENCE_STATE (f)); 699 state_free (state); 700 701 reset_target_context (FENCE_TC (f), true); 702 delete_target_context (tc); 703 704 FENCE_LAST_SCHEDULED_INSN (f) = NULL; 705 FENCE_ISSUE_MORE (f) = issue_rate; 706 } 707 else 708 if (candidate->src == BLOCK_FOR_INSN (last_scheduled_insn)) 709 { 710 /* Would be weird if same insn is successor of several fallthrough 711 edges. */ 712 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb 713 != BLOCK_FOR_INSN (last_scheduled_insn_old)); 714 715 state_free (FENCE_STATE (f)); 716 FENCE_STATE (f) = state; 717 718 delete_target_context (FENCE_TC (f)); 719 FENCE_TC (f) = tc; 720 721 FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn; 722 FENCE_ISSUE_MORE (f) = issue_more; 723 } 724 else 725 { 726 /* Leave STATE, TC and LAST_SCHEDULED_INSN fields untouched. */ 727 state_free (state); 728 delete_target_context (tc); 729 730 gcc_assert (BLOCK_FOR_INSN (insn)->prev_bb 731 != BLOCK_FOR_INSN (last_scheduled_insn)); 732 } 733 734 /* Find edge of first predecessor (last_scheduled_insn_old->insn). */ 735 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn_old, 736 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS) 737 { 738 if (succ == insn) 739 { 740 /* No same successor allowed from several edges. */ 741 gcc_assert (!edge_old); 742 edge_old = si.e1; 743 } 744 } 745 /* Find edge of second predecessor (last_scheduled_insn->insn). */ 746 FOR_EACH_SUCC_1 (succ, si, last_scheduled_insn, 747 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS) 748 { 749 if (succ == insn) 750 { 751 /* No same successor allowed from several edges. */ 752 gcc_assert (!edge_new); 753 edge_new = si.e1; 754 } 755 } 756 757 /* Check if we can choose most probable predecessor. */ 758 if (edge_old == NULL || edge_new == NULL) 759 { 760 reset_deps_context (FENCE_DC (f)); 761 delete_deps_context (dc); 762 VEC_free (rtx, gc, executing_insns); 763 free (ready_ticks); 764 765 FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle); 766 if (FENCE_EXECUTING_INSNS (f)) 767 VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0, 768 VEC_length (rtx, FENCE_EXECUTING_INSNS (f))); 769 if (FENCE_READY_TICKS (f)) 770 memset (FENCE_READY_TICKS (f), 0, FENCE_READY_TICKS_SIZE (f)); 771 } 772 else 773 if (edge_new->probability > edge_old->probability) 774 { 775 delete_deps_context (FENCE_DC (f)); 776 FENCE_DC (f) = dc; 777 VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f)); 778 FENCE_EXECUTING_INSNS (f) = executing_insns; 779 free (FENCE_READY_TICKS (f)); 780 FENCE_READY_TICKS (f) = ready_ticks; 781 FENCE_READY_TICKS_SIZE (f) = ready_ticks_size; 782 FENCE_CYCLE (f) = cycle; 783 } 784 else 785 { 786 /* Leave DC and CYCLE untouched. */ 787 delete_deps_context (dc); 788 VEC_free (rtx, gc, executing_insns); 789 free (ready_ticks); 790 } 791 } 792 793 /* Fill remaining invariant fields. */ 794 if (after_stall_p) 795 FENCE_AFTER_STALL_P (f) = 1; 796 797 FENCE_ISSUED_INSNS (f) = 0; 798 FENCE_STARTS_CYCLE_P (f) = 1; 799 FENCE_SCHED_NEXT (f) = NULL; 800 } 801 802 /* Add a new fence to NEW_FENCES list, initializing it from all 803 other parameters. */ 804 static void 805 add_to_fences (flist_tail_t new_fences, insn_t insn, 806 state_t state, deps_t dc, void *tc, rtx last_scheduled_insn, 807 VEC(rtx, gc) *executing_insns, int *ready_ticks, 808 int ready_ticks_size, rtx sched_next, int cycle, 809 int cycle_issued_insns, int issue_rate, 810 bool starts_cycle_p, bool after_stall_p) 811 { 812 fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn); 813 814 if (! f) 815 { 816 flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc, 817 last_scheduled_insn, executing_insns, ready_ticks, 818 ready_ticks_size, sched_next, cycle, cycle_issued_insns, 819 issue_rate, starts_cycle_p, after_stall_p); 820 821 FLIST_TAIL_TAILP (new_fences) 822 = &FLIST_NEXT (*FLIST_TAIL_TAILP (new_fences)); 823 } 824 else 825 { 826 merge_fences (f, insn, state, dc, tc, last_scheduled_insn, 827 executing_insns, ready_ticks, ready_ticks_size, 828 sched_next, cycle, issue_rate, after_stall_p); 829 } 830 } 831 832 /* Move the first fence in the OLD_FENCES list to NEW_FENCES. */ 833 void 834 move_fence_to_fences (flist_t old_fences, flist_tail_t new_fences) 835 { 836 fence_t f, old; 837 flist_t *tailp = FLIST_TAIL_TAILP (new_fences); 838 839 old = FLIST_FENCE (old_fences); 840 f = flist_lookup (FLIST_TAIL_HEAD (new_fences), 841 FENCE_INSN (FLIST_FENCE (old_fences))); 842 if (f) 843 { 844 merge_fences (f, old->insn, old->state, old->dc, old->tc, 845 old->last_scheduled_insn, old->executing_insns, 846 old->ready_ticks, old->ready_ticks_size, 847 old->sched_next, old->cycle, old->issue_more, 848 old->after_stall_p); 849 } 850 else 851 { 852 _list_add (tailp); 853 FLIST_TAIL_TAILP (new_fences) = &FLIST_NEXT (*tailp); 854 *FLIST_FENCE (*tailp) = *old; 855 init_fence_for_scheduling (FLIST_FENCE (*tailp)); 856 } 857 FENCE_INSN (old) = NULL; 858 } 859 860 /* Add a new fence to NEW_FENCES list and initialize most of its data 861 as a clean one. */ 862 void 863 add_clean_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence) 864 { 865 int ready_ticks_size = get_max_uid () + 1; 866 867 add_to_fences (new_fences, 868 succ, state_create (), create_deps_context (), 869 create_target_context (true), 870 NULL_RTX, NULL, 871 XCNEWVEC (int, ready_ticks_size), ready_ticks_size, 872 NULL_RTX, FENCE_CYCLE (fence) + 1, 873 0, issue_rate, 1, FENCE_AFTER_STALL_P (fence)); 874 } 875 876 /* Add a new fence to NEW_FENCES list and initialize all of its data 877 from FENCE and SUCC. */ 878 void 879 add_dirty_fence_to_fences (flist_tail_t new_fences, insn_t succ, fence_t fence) 880 { 881 int * new_ready_ticks 882 = XNEWVEC (int, FENCE_READY_TICKS_SIZE (fence)); 883 884 memcpy (new_ready_ticks, FENCE_READY_TICKS (fence), 885 FENCE_READY_TICKS_SIZE (fence) * sizeof (int)); 886 add_to_fences (new_fences, 887 succ, state_create_copy (FENCE_STATE (fence)), 888 create_copy_of_deps_context (FENCE_DC (fence)), 889 create_copy_of_target_context (FENCE_TC (fence)), 890 FENCE_LAST_SCHEDULED_INSN (fence), 891 VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)), 892 new_ready_ticks, 893 FENCE_READY_TICKS_SIZE (fence), 894 FENCE_SCHED_NEXT (fence), 895 FENCE_CYCLE (fence), 896 FENCE_ISSUED_INSNS (fence), 897 FENCE_ISSUE_MORE (fence), 898 FENCE_STARTS_CYCLE_P (fence), 899 FENCE_AFTER_STALL_P (fence)); 900 } 901 902 903 /* Functions to work with regset and nop pools. */ 904 905 /* Returns the new regset from pool. It might have some of the bits set 906 from the previous usage. */ 907 regset 908 get_regset_from_pool (void) 909 { 910 regset rs; 911 912 if (regset_pool.n != 0) 913 rs = regset_pool.v[--regset_pool.n]; 914 else 915 /* We need to create the regset. */ 916 { 917 rs = ALLOC_REG_SET (®_obstack); 918 919 if (regset_pool.nn == regset_pool.ss) 920 regset_pool.vv = XRESIZEVEC (regset, regset_pool.vv, 921 (regset_pool.ss = 2 * regset_pool.ss + 1)); 922 regset_pool.vv[regset_pool.nn++] = rs; 923 } 924 925 regset_pool.diff++; 926 927 return rs; 928 } 929 930 /* Same as above, but returns the empty regset. */ 931 regset 932 get_clear_regset_from_pool (void) 933 { 934 regset rs = get_regset_from_pool (); 935 936 CLEAR_REG_SET (rs); 937 return rs; 938 } 939 940 /* Return regset RS to the pool for future use. */ 941 void 942 return_regset_to_pool (regset rs) 943 { 944 gcc_assert (rs); 945 regset_pool.diff--; 946 947 if (regset_pool.n == regset_pool.s) 948 regset_pool.v = XRESIZEVEC (regset, regset_pool.v, 949 (regset_pool.s = 2 * regset_pool.s + 1)); 950 regset_pool.v[regset_pool.n++] = rs; 951 } 952 953 #ifdef ENABLE_CHECKING 954 /* This is used as a qsort callback for sorting regset pool stacks. 955 X and XX are addresses of two regsets. They are never equal. */ 956 static int 957 cmp_v_in_regset_pool (const void *x, const void *xx) 958 { 959 return *((const regset *) x) - *((const regset *) xx); 960 } 961 #endif 962 963 /* Free the regset pool possibly checking for memory leaks. */ 964 void 965 free_regset_pool (void) 966 { 967 #ifdef ENABLE_CHECKING 968 { 969 regset *v = regset_pool.v; 970 int i = 0; 971 int n = regset_pool.n; 972 973 regset *vv = regset_pool.vv; 974 int ii = 0; 975 int nn = regset_pool.nn; 976 977 int diff = 0; 978 979 gcc_assert (n <= nn); 980 981 /* Sort both vectors so it will be possible to compare them. */ 982 qsort (v, n, sizeof (*v), cmp_v_in_regset_pool); 983 qsort (vv, nn, sizeof (*vv), cmp_v_in_regset_pool); 984 985 while (ii < nn) 986 { 987 if (v[i] == vv[ii]) 988 i++; 989 else 990 /* VV[II] was lost. */ 991 diff++; 992 993 ii++; 994 } 995 996 gcc_assert (diff == regset_pool.diff); 997 } 998 #endif 999 1000 /* If not true - we have a memory leak. */ 1001 gcc_assert (regset_pool.diff == 0); 1002 1003 while (regset_pool.n) 1004 { 1005 --regset_pool.n; 1006 FREE_REG_SET (regset_pool.v[regset_pool.n]); 1007 } 1008 1009 free (regset_pool.v); 1010 regset_pool.v = NULL; 1011 regset_pool.s = 0; 1012 1013 free (regset_pool.vv); 1014 regset_pool.vv = NULL; 1015 regset_pool.nn = 0; 1016 regset_pool.ss = 0; 1017 1018 regset_pool.diff = 0; 1019 } 1020 1021 1022 /* Functions to work with nop pools. NOP insns are used as temporary 1023 placeholders of the insns being scheduled to allow correct update of 1024 the data sets. When update is finished, NOPs are deleted. */ 1025 1026 /* A vinsn that is used to represent a nop. This vinsn is shared among all 1027 nops sel-sched generates. */ 1028 static vinsn_t nop_vinsn = NULL; 1029 1030 /* Emit a nop before INSN, taking it from pool. */ 1031 insn_t 1032 get_nop_from_pool (insn_t insn) 1033 { 1034 insn_t nop; 1035 bool old_p = nop_pool.n != 0; 1036 int flags; 1037 1038 if (old_p) 1039 nop = nop_pool.v[--nop_pool.n]; 1040 else 1041 nop = nop_pattern; 1042 1043 nop = emit_insn_before (nop, insn); 1044 1045 if (old_p) 1046 flags = INSN_INIT_TODO_SSID; 1047 else 1048 flags = INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID; 1049 1050 set_insn_init (INSN_EXPR (insn), nop_vinsn, INSN_SEQNO (insn)); 1051 sel_init_new_insn (nop, flags); 1052 1053 return nop; 1054 } 1055 1056 /* Remove NOP from the instruction stream and return it to the pool. */ 1057 void 1058 return_nop_to_pool (insn_t nop, bool full_tidying) 1059 { 1060 gcc_assert (INSN_IN_STREAM_P (nop)); 1061 sel_remove_insn (nop, false, full_tidying); 1062 1063 if (nop_pool.n == nop_pool.s) 1064 nop_pool.v = XRESIZEVEC (rtx, nop_pool.v, 1065 (nop_pool.s = 2 * nop_pool.s + 1)); 1066 nop_pool.v[nop_pool.n++] = nop; 1067 } 1068 1069 /* Free the nop pool. */ 1070 void 1071 free_nop_pool (void) 1072 { 1073 nop_pool.n = 0; 1074 nop_pool.s = 0; 1075 free (nop_pool.v); 1076 nop_pool.v = NULL; 1077 } 1078 1079 1080 /* Skip unspec to support ia64 speculation. Called from rtx_equal_p_cb. 1081 The callback is given two rtxes XX and YY and writes the new rtxes 1082 to NX and NY in case some needs to be skipped. */ 1083 static int 1084 skip_unspecs_callback (const_rtx *xx, const_rtx *yy, rtx *nx, rtx* ny) 1085 { 1086 const_rtx x = *xx; 1087 const_rtx y = *yy; 1088 1089 if (GET_CODE (x) == UNSPEC 1090 && (targetm.sched.skip_rtx_p == NULL 1091 || targetm.sched.skip_rtx_p (x))) 1092 { 1093 *nx = XVECEXP (x, 0, 0); 1094 *ny = CONST_CAST_RTX (y); 1095 return 1; 1096 } 1097 1098 if (GET_CODE (y) == UNSPEC 1099 && (targetm.sched.skip_rtx_p == NULL 1100 || targetm.sched.skip_rtx_p (y))) 1101 { 1102 *nx = CONST_CAST_RTX (x); 1103 *ny = XVECEXP (y, 0, 0); 1104 return 1; 1105 } 1106 1107 return 0; 1108 } 1109 1110 /* Callback, called from hash_rtx_cb. Helps to hash UNSPEC rtx X in a correct way 1111 to support ia64 speculation. When changes are needed, new rtx X and new mode 1112 NMODE are written, and the callback returns true. */ 1113 static int 1114 hash_with_unspec_callback (const_rtx x, enum machine_mode mode ATTRIBUTE_UNUSED, 1115 rtx *nx, enum machine_mode* nmode) 1116 { 1117 if (GET_CODE (x) == UNSPEC 1118 && targetm.sched.skip_rtx_p 1119 && targetm.sched.skip_rtx_p (x)) 1120 { 1121 *nx = XVECEXP (x, 0 ,0); 1122 *nmode = VOIDmode; 1123 return 1; 1124 } 1125 1126 return 0; 1127 } 1128 1129 /* Returns LHS and RHS are ok to be scheduled separately. */ 1130 static bool 1131 lhs_and_rhs_separable_p (rtx lhs, rtx rhs) 1132 { 1133 if (lhs == NULL || rhs == NULL) 1134 return false; 1135 1136 /* Do not schedule CONST, CONST_INT and CONST_DOUBLE etc as rhs: no point 1137 to use reg, if const can be used. Moreover, scheduling const as rhs may 1138 lead to mode mismatch cause consts don't have modes but they could be 1139 merged from branches where the same const used in different modes. */ 1140 if (CONSTANT_P (rhs)) 1141 return false; 1142 1143 /* ??? Do not rename predicate registers to avoid ICEs in bundling. */ 1144 if (COMPARISON_P (rhs)) 1145 return false; 1146 1147 /* Do not allow single REG to be an rhs. */ 1148 if (REG_P (rhs)) 1149 return false; 1150 1151 /* See comment at find_used_regs_1 (*1) for explanation of this 1152 restriction. */ 1153 /* FIXME: remove this later. */ 1154 if (MEM_P (lhs)) 1155 return false; 1156 1157 /* This will filter all tricky things like ZERO_EXTRACT etc. 1158 For now we don't handle it. */ 1159 if (!REG_P (lhs) && !MEM_P (lhs)) 1160 return false; 1161 1162 return true; 1163 } 1164 1165 /* Initialize vinsn VI for INSN. Only for use from vinsn_create (). When 1166 FORCE_UNIQUE_P is true, the resulting vinsn will not be clonable. This is 1167 used e.g. for insns from recovery blocks. */ 1168 static void 1169 vinsn_init (vinsn_t vi, insn_t insn, bool force_unique_p) 1170 { 1171 hash_rtx_callback_function hrcf; 1172 int insn_class; 1173 1174 VINSN_INSN_RTX (vi) = insn; 1175 VINSN_COUNT (vi) = 0; 1176 vi->cost = -1; 1177 1178 if (INSN_NOP_P (insn)) 1179 return; 1180 1181 if (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL) 1182 init_id_from_df (VINSN_ID (vi), insn, force_unique_p); 1183 else 1184 deps_init_id (VINSN_ID (vi), insn, force_unique_p); 1185 1186 /* Hash vinsn depending on whether it is separable or not. */ 1187 hrcf = targetm.sched.skip_rtx_p ? hash_with_unspec_callback : NULL; 1188 if (VINSN_SEPARABLE_P (vi)) 1189 { 1190 rtx rhs = VINSN_RHS (vi); 1191 1192 VINSN_HASH (vi) = hash_rtx_cb (rhs, GET_MODE (rhs), 1193 NULL, NULL, false, hrcf); 1194 VINSN_HASH_RTX (vi) = hash_rtx_cb (VINSN_PATTERN (vi), 1195 VOIDmode, NULL, NULL, 1196 false, hrcf); 1197 } 1198 else 1199 { 1200 VINSN_HASH (vi) = hash_rtx_cb (VINSN_PATTERN (vi), VOIDmode, 1201 NULL, NULL, false, hrcf); 1202 VINSN_HASH_RTX (vi) = VINSN_HASH (vi); 1203 } 1204 1205 insn_class = haifa_classify_insn (insn); 1206 if (insn_class >= 2 1207 && (!targetm.sched.get_insn_spec_ds 1208 || ((targetm.sched.get_insn_spec_ds (insn) & BEGIN_CONTROL) 1209 == 0))) 1210 VINSN_MAY_TRAP_P (vi) = true; 1211 else 1212 VINSN_MAY_TRAP_P (vi) = false; 1213 } 1214 1215 /* Indicate that VI has become the part of an rtx object. */ 1216 void 1217 vinsn_attach (vinsn_t vi) 1218 { 1219 /* Assert that VI is not pending for deletion. */ 1220 gcc_assert (VINSN_INSN_RTX (vi)); 1221 1222 VINSN_COUNT (vi)++; 1223 } 1224 1225 /* Create and init VI from the INSN. Use UNIQUE_P for determining the correct 1226 VINSN_TYPE (VI). */ 1227 static vinsn_t 1228 vinsn_create (insn_t insn, bool force_unique_p) 1229 { 1230 vinsn_t vi = XCNEW (struct vinsn_def); 1231 1232 vinsn_init (vi, insn, force_unique_p); 1233 return vi; 1234 } 1235 1236 /* Return a copy of VI. When REATTACH_P is true, detach VI and attach 1237 the copy. */ 1238 vinsn_t 1239 vinsn_copy (vinsn_t vi, bool reattach_p) 1240 { 1241 rtx copy; 1242 bool unique = VINSN_UNIQUE_P (vi); 1243 vinsn_t new_vi; 1244 1245 copy = create_copy_of_insn_rtx (VINSN_INSN_RTX (vi)); 1246 new_vi = create_vinsn_from_insn_rtx (copy, unique); 1247 if (reattach_p) 1248 { 1249 vinsn_detach (vi); 1250 vinsn_attach (new_vi); 1251 } 1252 1253 return new_vi; 1254 } 1255 1256 /* Delete the VI vinsn and free its data. */ 1257 static void 1258 vinsn_delete (vinsn_t vi) 1259 { 1260 gcc_assert (VINSN_COUNT (vi) == 0); 1261 1262 if (!INSN_NOP_P (VINSN_INSN_RTX (vi))) 1263 { 1264 return_regset_to_pool (VINSN_REG_SETS (vi)); 1265 return_regset_to_pool (VINSN_REG_USES (vi)); 1266 return_regset_to_pool (VINSN_REG_CLOBBERS (vi)); 1267 } 1268 1269 free (vi); 1270 } 1271 1272 /* Indicate that VI is no longer a part of some rtx object. 1273 Remove VI if it is no longer needed. */ 1274 void 1275 vinsn_detach (vinsn_t vi) 1276 { 1277 gcc_assert (VINSN_COUNT (vi) > 0); 1278 1279 if (--VINSN_COUNT (vi) == 0) 1280 vinsn_delete (vi); 1281 } 1282 1283 /* Returns TRUE if VI is a branch. */ 1284 bool 1285 vinsn_cond_branch_p (vinsn_t vi) 1286 { 1287 insn_t insn; 1288 1289 if (!VINSN_UNIQUE_P (vi)) 1290 return false; 1291 1292 insn = VINSN_INSN_RTX (vi); 1293 if (BB_END (BLOCK_FOR_INSN (insn)) != insn) 1294 return false; 1295 1296 return control_flow_insn_p (insn); 1297 } 1298 1299 /* Return latency of INSN. */ 1300 static int 1301 sel_insn_rtx_cost (rtx insn) 1302 { 1303 int cost; 1304 1305 /* A USE insn, or something else we don't need to 1306 understand. We can't pass these directly to 1307 result_ready_cost or insn_default_latency because it will 1308 trigger a fatal error for unrecognizable insns. */ 1309 if (recog_memoized (insn) < 0) 1310 cost = 0; 1311 else 1312 { 1313 cost = insn_default_latency (insn); 1314 1315 if (cost < 0) 1316 cost = 0; 1317 } 1318 1319 return cost; 1320 } 1321 1322 /* Return the cost of the VI. 1323 !!! FIXME: Unify with haifa-sched.c: insn_cost (). */ 1324 int 1325 sel_vinsn_cost (vinsn_t vi) 1326 { 1327 int cost = vi->cost; 1328 1329 if (cost < 0) 1330 { 1331 cost = sel_insn_rtx_cost (VINSN_INSN_RTX (vi)); 1332 vi->cost = cost; 1333 } 1334 1335 return cost; 1336 } 1337 1338 1339 /* Functions for insn emitting. */ 1340 1341 /* Emit new insn after AFTER based on PATTERN and initialize its data from 1342 EXPR and SEQNO. */ 1343 insn_t 1344 sel_gen_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, insn_t after) 1345 { 1346 insn_t new_insn; 1347 1348 gcc_assert (EXPR_TARGET_AVAILABLE (expr) == true); 1349 1350 new_insn = emit_insn_after (pattern, after); 1351 set_insn_init (expr, NULL, seqno); 1352 sel_init_new_insn (new_insn, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SSID); 1353 1354 return new_insn; 1355 } 1356 1357 /* Force newly generated vinsns to be unique. */ 1358 static bool init_insn_force_unique_p = false; 1359 1360 /* Emit new speculation recovery insn after AFTER based on PATTERN and 1361 initialize its data from EXPR and SEQNO. */ 1362 insn_t 1363 sel_gen_recovery_insn_from_rtx_after (rtx pattern, expr_t expr, int seqno, 1364 insn_t after) 1365 { 1366 insn_t insn; 1367 1368 gcc_assert (!init_insn_force_unique_p); 1369 1370 init_insn_force_unique_p = true; 1371 insn = sel_gen_insn_from_rtx_after (pattern, expr, seqno, after); 1372 CANT_MOVE (insn) = 1; 1373 init_insn_force_unique_p = false; 1374 1375 return insn; 1376 } 1377 1378 /* Emit new insn after AFTER based on EXPR and SEQNO. If VINSN is not NULL, 1379 take it as a new vinsn instead of EXPR's vinsn. 1380 We simplify insns later, after scheduling region in 1381 simplify_changed_insns. */ 1382 insn_t 1383 sel_gen_insn_from_expr_after (expr_t expr, vinsn_t vinsn, int seqno, 1384 insn_t after) 1385 { 1386 expr_t emit_expr; 1387 insn_t insn; 1388 int flags; 1389 1390 emit_expr = set_insn_init (expr, vinsn ? vinsn : EXPR_VINSN (expr), 1391 seqno); 1392 insn = EXPR_INSN_RTX (emit_expr); 1393 add_insn_after (insn, after, BLOCK_FOR_INSN (insn)); 1394 1395 flags = INSN_INIT_TODO_SSID; 1396 if (INSN_LUID (insn) == 0) 1397 flags |= INSN_INIT_TODO_LUID; 1398 sel_init_new_insn (insn, flags); 1399 1400 return insn; 1401 } 1402 1403 /* Move insn from EXPR after AFTER. */ 1404 insn_t 1405 sel_move_insn (expr_t expr, int seqno, insn_t after) 1406 { 1407 insn_t insn = EXPR_INSN_RTX (expr); 1408 basic_block bb = BLOCK_FOR_INSN (after); 1409 insn_t next = NEXT_INSN (after); 1410 1411 /* Assert that in move_op we disconnected this insn properly. */ 1412 gcc_assert (EXPR_VINSN (INSN_EXPR (insn)) != NULL); 1413 PREV_INSN (insn) = after; 1414 NEXT_INSN (insn) = next; 1415 1416 NEXT_INSN (after) = insn; 1417 PREV_INSN (next) = insn; 1418 1419 /* Update links from insn to bb and vice versa. */ 1420 df_insn_change_bb (insn, bb); 1421 if (BB_END (bb) == after) 1422 BB_END (bb) = insn; 1423 1424 prepare_insn_expr (insn, seqno); 1425 return insn; 1426 } 1427 1428 1429 /* Functions to work with right-hand sides. */ 1430 1431 /* Search for a hash value determined by UID/NEW_VINSN in a sorted vector 1432 VECT and return true when found. Use NEW_VINSN for comparison only when 1433 COMPARE_VINSNS is true. Write to INDP the index on which 1434 the search has stopped, such that inserting the new element at INDP will 1435 retain VECT's sort order. */ 1436 static bool 1437 find_in_history_vect_1 (VEC(expr_history_def, heap) *vect, 1438 unsigned uid, vinsn_t new_vinsn, 1439 bool compare_vinsns, int *indp) 1440 { 1441 expr_history_def *arr; 1442 int i, j, len = VEC_length (expr_history_def, vect); 1443 1444 if (len == 0) 1445 { 1446 *indp = 0; 1447 return false; 1448 } 1449 1450 arr = VEC_address (expr_history_def, vect); 1451 i = 0, j = len - 1; 1452 1453 while (i <= j) 1454 { 1455 unsigned auid = arr[i].uid; 1456 vinsn_t avinsn = arr[i].new_expr_vinsn; 1457 1458 if (auid == uid 1459 /* When undoing transformation on a bookkeeping copy, the new vinsn 1460 may not be exactly equal to the one that is saved in the vector. 1461 This is because the insn whose copy we're checking was possibly 1462 substituted itself. */ 1463 && (! compare_vinsns 1464 || vinsn_equal_p (avinsn, new_vinsn))) 1465 { 1466 *indp = i; 1467 return true; 1468 } 1469 else if (auid > uid) 1470 break; 1471 i++; 1472 } 1473 1474 *indp = i; 1475 return false; 1476 } 1477 1478 /* Search for a uid of INSN and NEW_VINSN in a sorted vector VECT. Return 1479 the position found or -1, if no such value is in vector. 1480 Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */ 1481 int 1482 find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn, 1483 vinsn_t new_vinsn, bool originators_p) 1484 { 1485 int ind; 1486 1487 if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn, 1488 false, &ind)) 1489 return ind; 1490 1491 if (INSN_ORIGINATORS (insn) && originators_p) 1492 { 1493 unsigned uid; 1494 bitmap_iterator bi; 1495 1496 EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi) 1497 if (find_in_history_vect_1 (vect, uid, new_vinsn, false, &ind)) 1498 return ind; 1499 } 1500 1501 return -1; 1502 } 1503 1504 /* Insert new element in a sorted history vector pointed to by PVECT, 1505 if it is not there already. The element is searched using 1506 UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save 1507 the history of a transformation. */ 1508 void 1509 insert_in_history_vect (VEC (expr_history_def, heap) **pvect, 1510 unsigned uid, enum local_trans_type type, 1511 vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn, 1512 ds_t spec_ds) 1513 { 1514 VEC(expr_history_def, heap) *vect = *pvect; 1515 expr_history_def temp; 1516 bool res; 1517 int ind; 1518 1519 res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, true, &ind); 1520 1521 if (res) 1522 { 1523 expr_history_def *phist = VEC_index (expr_history_def, vect, ind); 1524 1525 /* It is possible that speculation types of expressions that were 1526 propagated through different paths will be different here. In this 1527 case, merge the status to get the correct check later. */ 1528 if (phist->spec_ds != spec_ds) 1529 phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds); 1530 return; 1531 } 1532 1533 temp.uid = uid; 1534 temp.old_expr_vinsn = old_expr_vinsn; 1535 temp.new_expr_vinsn = new_expr_vinsn; 1536 temp.spec_ds = spec_ds; 1537 temp.type = type; 1538 1539 vinsn_attach (old_expr_vinsn); 1540 vinsn_attach (new_expr_vinsn); 1541 VEC_safe_insert (expr_history_def, heap, vect, ind, &temp); 1542 *pvect = vect; 1543 } 1544 1545 /* Free history vector PVECT. */ 1546 static void 1547 free_history_vect (VEC (expr_history_def, heap) **pvect) 1548 { 1549 unsigned i; 1550 expr_history_def *phist; 1551 1552 if (! *pvect) 1553 return; 1554 1555 for (i = 0; 1556 VEC_iterate (expr_history_def, *pvect, i, phist); 1557 i++) 1558 { 1559 vinsn_detach (phist->old_expr_vinsn); 1560 vinsn_detach (phist->new_expr_vinsn); 1561 } 1562 1563 VEC_free (expr_history_def, heap, *pvect); 1564 *pvect = NULL; 1565 } 1566 1567 /* Merge vector FROM to PVECT. */ 1568 static void 1569 merge_history_vect (VEC (expr_history_def, heap) **pvect, 1570 VEC (expr_history_def, heap) *from) 1571 { 1572 expr_history_def *phist; 1573 int i; 1574 1575 /* We keep this vector sorted. */ 1576 for (i = 0; VEC_iterate (expr_history_def, from, i, phist); i++) 1577 insert_in_history_vect (pvect, phist->uid, phist->type, 1578 phist->old_expr_vinsn, phist->new_expr_vinsn, 1579 phist->spec_ds); 1580 } 1581 1582 /* Compare two vinsns as rhses if possible and as vinsns otherwise. */ 1583 bool 1584 vinsn_equal_p (vinsn_t x, vinsn_t y) 1585 { 1586 rtx_equal_p_callback_function repcf; 1587 1588 if (x == y) 1589 return true; 1590 1591 if (VINSN_TYPE (x) != VINSN_TYPE (y)) 1592 return false; 1593 1594 if (VINSN_HASH (x) != VINSN_HASH (y)) 1595 return false; 1596 1597 repcf = targetm.sched.skip_rtx_p ? skip_unspecs_callback : NULL; 1598 if (VINSN_SEPARABLE_P (x)) 1599 { 1600 /* Compare RHSes of VINSNs. */ 1601 gcc_assert (VINSN_RHS (x)); 1602 gcc_assert (VINSN_RHS (y)); 1603 1604 return rtx_equal_p_cb (VINSN_RHS (x), VINSN_RHS (y), repcf); 1605 } 1606 1607 return rtx_equal_p_cb (VINSN_PATTERN (x), VINSN_PATTERN (y), repcf); 1608 } 1609 1610 1611 /* Functions for working with expressions. */ 1612 1613 /* Initialize EXPR. */ 1614 static void 1615 init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority, 1616 int sched_times, int orig_bb_index, ds_t spec_done_ds, 1617 ds_t spec_to_check_ds, int orig_sched_cycle, 1618 VEC(expr_history_def, heap) *history, signed char target_available, 1619 bool was_substituted, bool was_renamed, bool needs_spec_check_p, 1620 bool cant_move) 1621 { 1622 vinsn_attach (vi); 1623 1624 EXPR_VINSN (expr) = vi; 1625 EXPR_SPEC (expr) = spec; 1626 EXPR_USEFULNESS (expr) = use; 1627 EXPR_PRIORITY (expr) = priority; 1628 EXPR_PRIORITY_ADJ (expr) = 0; 1629 EXPR_SCHED_TIMES (expr) = sched_times; 1630 EXPR_ORIG_BB_INDEX (expr) = orig_bb_index; 1631 EXPR_ORIG_SCHED_CYCLE (expr) = orig_sched_cycle; 1632 EXPR_SPEC_DONE_DS (expr) = spec_done_ds; 1633 EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds; 1634 1635 if (history) 1636 EXPR_HISTORY_OF_CHANGES (expr) = history; 1637 else 1638 EXPR_HISTORY_OF_CHANGES (expr) = NULL; 1639 1640 EXPR_TARGET_AVAILABLE (expr) = target_available; 1641 EXPR_WAS_SUBSTITUTED (expr) = was_substituted; 1642 EXPR_WAS_RENAMED (expr) = was_renamed; 1643 EXPR_NEEDS_SPEC_CHECK_P (expr) = needs_spec_check_p; 1644 EXPR_CANT_MOVE (expr) = cant_move; 1645 } 1646 1647 /* Make a copy of the expr FROM into the expr TO. */ 1648 void 1649 copy_expr (expr_t to, expr_t from) 1650 { 1651 VEC(expr_history_def, heap) *temp = NULL; 1652 1653 if (EXPR_HISTORY_OF_CHANGES (from)) 1654 { 1655 unsigned i; 1656 expr_history_def *phist; 1657 1658 temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from)); 1659 for (i = 0; 1660 VEC_iterate (expr_history_def, temp, i, phist); 1661 i++) 1662 { 1663 vinsn_attach (phist->old_expr_vinsn); 1664 vinsn_attach (phist->new_expr_vinsn); 1665 } 1666 } 1667 1668 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), 1669 EXPR_USEFULNESS (from), EXPR_PRIORITY (from), 1670 EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from), 1671 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 1672 EXPR_ORIG_SCHED_CYCLE (from), temp, 1673 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from), 1674 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from), 1675 EXPR_CANT_MOVE (from)); 1676 } 1677 1678 /* Same, but the final expr will not ever be in av sets, so don't copy 1679 "uninteresting" data such as bitmap cache. */ 1680 void 1681 copy_expr_onside (expr_t to, expr_t from) 1682 { 1683 init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from), EXPR_USEFULNESS (from), 1684 EXPR_PRIORITY (from), EXPR_SCHED_TIMES (from), 0, 1685 EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from), 0, NULL, 1686 EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from), 1687 EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from), 1688 EXPR_CANT_MOVE (from)); 1689 } 1690 1691 /* Prepare the expr of INSN for scheduling. Used when moving insn and when 1692 initializing new insns. */ 1693 static void 1694 prepare_insn_expr (insn_t insn, int seqno) 1695 { 1696 expr_t expr = INSN_EXPR (insn); 1697 ds_t ds; 1698 1699 INSN_SEQNO (insn) = seqno; 1700 EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn); 1701 EXPR_SPEC (expr) = 0; 1702 EXPR_ORIG_SCHED_CYCLE (expr) = 0; 1703 EXPR_WAS_SUBSTITUTED (expr) = 0; 1704 EXPR_WAS_RENAMED (expr) = 0; 1705 EXPR_TARGET_AVAILABLE (expr) = 1; 1706 INSN_LIVE_VALID_P (insn) = false; 1707 1708 /* ??? If this expression is speculative, make its dependence 1709 as weak as possible. We can filter this expression later 1710 in process_spec_exprs, because we do not distinguish 1711 between the status we got during compute_av_set and the 1712 existing status. To be fixed. */ 1713 ds = EXPR_SPEC_DONE_DS (expr); 1714 if (ds) 1715 EXPR_SPEC_DONE_DS (expr) = ds_get_max_dep_weak (ds); 1716 1717 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr)); 1718 } 1719 1720 /* Update target_available bits when merging exprs TO and FROM. SPLIT_POINT 1721 is non-null when expressions are merged from different successors at 1722 a split point. */ 1723 static void 1724 update_target_availability (expr_t to, expr_t from, insn_t split_point) 1725 { 1726 if (EXPR_TARGET_AVAILABLE (to) < 0 1727 || EXPR_TARGET_AVAILABLE (from) < 0) 1728 EXPR_TARGET_AVAILABLE (to) = -1; 1729 else 1730 { 1731 /* We try to detect the case when one of the expressions 1732 can only be reached through another one. In this case, 1733 we can do better. */ 1734 if (split_point == NULL) 1735 { 1736 int toind, fromind; 1737 1738 toind = EXPR_ORIG_BB_INDEX (to); 1739 fromind = EXPR_ORIG_BB_INDEX (from); 1740 1741 if (toind && toind == fromind) 1742 /* Do nothing -- everything is done in 1743 merge_with_other_exprs. */ 1744 ; 1745 else 1746 EXPR_TARGET_AVAILABLE (to) = -1; 1747 } 1748 else 1749 EXPR_TARGET_AVAILABLE (to) &= EXPR_TARGET_AVAILABLE (from); 1750 } 1751 } 1752 1753 /* Update speculation bits when merging exprs TO and FROM. SPLIT_POINT 1754 is non-null when expressions are merged from different successors at 1755 a split point. */ 1756 static void 1757 update_speculative_bits (expr_t to, expr_t from, insn_t split_point) 1758 { 1759 ds_t old_to_ds, old_from_ds; 1760 1761 old_to_ds = EXPR_SPEC_DONE_DS (to); 1762 old_from_ds = EXPR_SPEC_DONE_DS (from); 1763 1764 EXPR_SPEC_DONE_DS (to) = ds_max_merge (old_to_ds, old_from_ds); 1765 EXPR_SPEC_TO_CHECK_DS (to) |= EXPR_SPEC_TO_CHECK_DS (from); 1766 EXPR_NEEDS_SPEC_CHECK_P (to) |= EXPR_NEEDS_SPEC_CHECK_P (from); 1767 1768 /* When merging e.g. control & data speculative exprs, or a control 1769 speculative with a control&data speculative one, we really have 1770 to change vinsn too. Also, when speculative status is changed, 1771 we also need to record this as a transformation in expr's history. */ 1772 if ((old_to_ds & SPECULATIVE) || (old_from_ds & SPECULATIVE)) 1773 { 1774 old_to_ds = ds_get_speculation_types (old_to_ds); 1775 old_from_ds = ds_get_speculation_types (old_from_ds); 1776 1777 if (old_to_ds != old_from_ds) 1778 { 1779 ds_t record_ds; 1780 1781 /* When both expressions are speculative, we need to change 1782 the vinsn first. */ 1783 if ((old_to_ds & SPECULATIVE) && (old_from_ds & SPECULATIVE)) 1784 { 1785 int res; 1786 1787 res = speculate_expr (to, EXPR_SPEC_DONE_DS (to)); 1788 gcc_assert (res >= 0); 1789 } 1790 1791 if (split_point != NULL) 1792 { 1793 /* Record the change with proper status. */ 1794 record_ds = EXPR_SPEC_DONE_DS (to) & SPECULATIVE; 1795 record_ds &= ~(old_to_ds & SPECULATIVE); 1796 record_ds &= ~(old_from_ds & SPECULATIVE); 1797 1798 insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to), 1799 INSN_UID (split_point), TRANS_SPECULATION, 1800 EXPR_VINSN (from), EXPR_VINSN (to), 1801 record_ds); 1802 } 1803 } 1804 } 1805 } 1806 1807 1808 /* Merge bits of FROM expr to TO expr. When SPLIT_POINT is not NULL, 1809 this is done along different paths. */ 1810 void 1811 merge_expr_data (expr_t to, expr_t from, insn_t split_point) 1812 { 1813 /* For now, we just set the spec of resulting expr to be minimum of the specs 1814 of merged exprs. */ 1815 if (EXPR_SPEC (to) > EXPR_SPEC (from)) 1816 EXPR_SPEC (to) = EXPR_SPEC (from); 1817 1818 if (split_point) 1819 EXPR_USEFULNESS (to) += EXPR_USEFULNESS (from); 1820 else 1821 EXPR_USEFULNESS (to) = MAX (EXPR_USEFULNESS (to), 1822 EXPR_USEFULNESS (from)); 1823 1824 if (EXPR_PRIORITY (to) < EXPR_PRIORITY (from)) 1825 EXPR_PRIORITY (to) = EXPR_PRIORITY (from); 1826 1827 if (EXPR_SCHED_TIMES (to) > EXPR_SCHED_TIMES (from)) 1828 EXPR_SCHED_TIMES (to) = EXPR_SCHED_TIMES (from); 1829 1830 if (EXPR_ORIG_BB_INDEX (to) != EXPR_ORIG_BB_INDEX (from)) 1831 EXPR_ORIG_BB_INDEX (to) = 0; 1832 1833 EXPR_ORIG_SCHED_CYCLE (to) = MIN (EXPR_ORIG_SCHED_CYCLE (to), 1834 EXPR_ORIG_SCHED_CYCLE (from)); 1835 1836 EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from); 1837 EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (from); 1838 EXPR_CANT_MOVE (to) |= EXPR_CANT_MOVE (from); 1839 1840 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (to), 1841 EXPR_HISTORY_OF_CHANGES (from)); 1842 update_target_availability (to, from, split_point); 1843 update_speculative_bits (to, from, split_point); 1844 } 1845 1846 /* Merge bits of FROM expr to TO expr. Vinsns in the exprs should be equal 1847 in terms of vinsn_equal_p. SPLIT_POINT is non-null when expressions 1848 are merged from different successors at a split point. */ 1849 void 1850 merge_expr (expr_t to, expr_t from, insn_t split_point) 1851 { 1852 vinsn_t to_vi = EXPR_VINSN (to); 1853 vinsn_t from_vi = EXPR_VINSN (from); 1854 1855 gcc_assert (vinsn_equal_p (to_vi, from_vi)); 1856 1857 /* Make sure that speculative pattern is propagated into exprs that 1858 have non-speculative one. This will provide us with consistent 1859 speculative bits and speculative patterns inside expr. */ 1860 if (EXPR_SPEC_DONE_DS (to) == 0 1861 && EXPR_SPEC_DONE_DS (from) != 0) 1862 change_vinsn_in_expr (to, EXPR_VINSN (from)); 1863 1864 merge_expr_data (to, from, split_point); 1865 gcc_assert (EXPR_USEFULNESS (to) <= REG_BR_PROB_BASE); 1866 } 1867 1868 /* Clear the information of this EXPR. */ 1869 void 1870 clear_expr (expr_t expr) 1871 { 1872 1873 vinsn_detach (EXPR_VINSN (expr)); 1874 EXPR_VINSN (expr) = NULL; 1875 1876 free_history_vect (&EXPR_HISTORY_OF_CHANGES (expr)); 1877 } 1878 1879 /* For a given LV_SET, mark EXPR having unavailable target register. */ 1880 static void 1881 set_unavailable_target_for_expr (expr_t expr, regset lv_set) 1882 { 1883 if (EXPR_SEPARABLE_P (expr)) 1884 { 1885 if (REG_P (EXPR_LHS (expr)) 1886 && bitmap_bit_p (lv_set, REGNO (EXPR_LHS (expr)))) 1887 { 1888 /* If it's an insn like r1 = use (r1, ...), and it exists in 1889 different forms in each of the av_sets being merged, we can't say 1890 whether original destination register is available or not. 1891 However, this still works if destination register is not used 1892 in the original expression: if the branch at which LV_SET we're 1893 looking here is not actually 'other branch' in sense that same 1894 expression is available through it (but it can't be determined 1895 at computation stage because of transformations on one of the 1896 branches), it still won't affect the availability. 1897 Liveness of a register somewhere on a code motion path means 1898 it's either read somewhere on a codemotion path, live on 1899 'other' branch, live at the point immediately following 1900 the original operation, or is read by the original operation. 1901 The latter case is filtered out in the condition below. 1902 It still doesn't cover the case when register is defined and used 1903 somewhere within the code motion path, and in this case we could 1904 miss a unifying code motion along both branches using a renamed 1905 register, but it won't affect a code correctness since upon 1906 an actual code motion a bookkeeping code would be generated. */ 1907 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)), 1908 REGNO (EXPR_LHS (expr)))) 1909 EXPR_TARGET_AVAILABLE (expr) = -1; 1910 else 1911 EXPR_TARGET_AVAILABLE (expr) = false; 1912 } 1913 } 1914 else 1915 { 1916 unsigned regno; 1917 reg_set_iterator rsi; 1918 1919 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_SETS (EXPR_VINSN (expr)), 1920 0, regno, rsi) 1921 if (bitmap_bit_p (lv_set, regno)) 1922 { 1923 EXPR_TARGET_AVAILABLE (expr) = false; 1924 break; 1925 } 1926 1927 EXECUTE_IF_SET_IN_REG_SET (VINSN_REG_CLOBBERS (EXPR_VINSN (expr)), 1928 0, regno, rsi) 1929 if (bitmap_bit_p (lv_set, regno)) 1930 { 1931 EXPR_TARGET_AVAILABLE (expr) = false; 1932 break; 1933 } 1934 } 1935 } 1936 1937 /* Try to make EXPR speculative. Return 1 when EXPR's pattern 1938 or dependence status have changed, 2 when also the target register 1939 became unavailable, 0 if nothing had to be changed. */ 1940 int 1941 speculate_expr (expr_t expr, ds_t ds) 1942 { 1943 int res; 1944 rtx orig_insn_rtx; 1945 rtx spec_pat; 1946 ds_t target_ds, current_ds; 1947 1948 /* Obtain the status we need to put on EXPR. */ 1949 target_ds = (ds & SPECULATIVE); 1950 current_ds = EXPR_SPEC_DONE_DS (expr); 1951 ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX); 1952 1953 orig_insn_rtx = EXPR_INSN_RTX (expr); 1954 1955 res = sched_speculate_insn (orig_insn_rtx, ds, &spec_pat); 1956 1957 switch (res) 1958 { 1959 case 0: 1960 EXPR_SPEC_DONE_DS (expr) = ds; 1961 return current_ds != ds ? 1 : 0; 1962 1963 case 1: 1964 { 1965 rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX); 1966 vinsn_t spec_vinsn = create_vinsn_from_insn_rtx (spec_insn_rtx, false); 1967 1968 change_vinsn_in_expr (expr, spec_vinsn); 1969 EXPR_SPEC_DONE_DS (expr) = ds; 1970 EXPR_NEEDS_SPEC_CHECK_P (expr) = true; 1971 1972 /* Do not allow clobbering the address register of speculative 1973 insns. */ 1974 if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)), 1975 expr_dest_regno (expr))) 1976 { 1977 EXPR_TARGET_AVAILABLE (expr) = false; 1978 return 2; 1979 } 1980 1981 return 1; 1982 } 1983 1984 case -1: 1985 return -1; 1986 1987 default: 1988 gcc_unreachable (); 1989 return -1; 1990 } 1991 } 1992 1993 /* Return a destination register, if any, of EXPR. */ 1994 rtx 1995 expr_dest_reg (expr_t expr) 1996 { 1997 rtx dest = VINSN_LHS (EXPR_VINSN (expr)); 1998 1999 if (dest != NULL_RTX && REG_P (dest)) 2000 return dest; 2001 2002 return NULL_RTX; 2003 } 2004 2005 /* Returns the REGNO of the R's destination. */ 2006 unsigned 2007 expr_dest_regno (expr_t expr) 2008 { 2009 rtx dest = expr_dest_reg (expr); 2010 2011 gcc_assert (dest != NULL_RTX); 2012 return REGNO (dest); 2013 } 2014 2015 /* For a given LV_SET, mark all expressions in JOIN_SET, but not present in 2016 AV_SET having unavailable target register. */ 2017 void 2018 mark_unavailable_targets (av_set_t join_set, av_set_t av_set, regset lv_set) 2019 { 2020 expr_t expr; 2021 av_set_iterator avi; 2022 2023 FOR_EACH_EXPR (expr, avi, join_set) 2024 if (av_set_lookup (av_set, EXPR_VINSN (expr)) == NULL) 2025 set_unavailable_target_for_expr (expr, lv_set); 2026 } 2027 2028 2029 /* Av set functions. */ 2030 2031 /* Add a new element to av set SETP. 2032 Return the element added. */ 2033 static av_set_t 2034 av_set_add_element (av_set_t *setp) 2035 { 2036 /* Insert at the beginning of the list. */ 2037 _list_add (setp); 2038 return *setp; 2039 } 2040 2041 /* Add EXPR to SETP. */ 2042 void 2043 av_set_add (av_set_t *setp, expr_t expr) 2044 { 2045 av_set_t elem; 2046 2047 gcc_assert (!INSN_NOP_P (EXPR_INSN_RTX (expr))); 2048 elem = av_set_add_element (setp); 2049 copy_expr (_AV_SET_EXPR (elem), expr); 2050 } 2051 2052 /* Same, but do not copy EXPR. */ 2053 static void 2054 av_set_add_nocopy (av_set_t *setp, expr_t expr) 2055 { 2056 av_set_t elem; 2057 2058 elem = av_set_add_element (setp); 2059 *_AV_SET_EXPR (elem) = *expr; 2060 } 2061 2062 /* Remove expr pointed to by IP from the av_set. */ 2063 void 2064 av_set_iter_remove (av_set_iterator *ip) 2065 { 2066 clear_expr (_AV_SET_EXPR (*ip->lp)); 2067 _list_iter_remove (ip); 2068 } 2069 2070 /* Search for an expr in SET, such that it's equivalent to SOUGHT_VINSN in the 2071 sense of vinsn_equal_p function. Return NULL if no such expr is 2072 in SET was found. */ 2073 expr_t 2074 av_set_lookup (av_set_t set, vinsn_t sought_vinsn) 2075 { 2076 expr_t expr; 2077 av_set_iterator i; 2078 2079 FOR_EACH_EXPR (expr, i, set) 2080 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn)) 2081 return expr; 2082 return NULL; 2083 } 2084 2085 /* Same, but also remove the EXPR found. */ 2086 static expr_t 2087 av_set_lookup_and_remove (av_set_t *setp, vinsn_t sought_vinsn) 2088 { 2089 expr_t expr; 2090 av_set_iterator i; 2091 2092 FOR_EACH_EXPR_1 (expr, i, setp) 2093 if (vinsn_equal_p (EXPR_VINSN (expr), sought_vinsn)) 2094 { 2095 _list_iter_remove_nofree (&i); 2096 return expr; 2097 } 2098 return NULL; 2099 } 2100 2101 /* Search for an expr in SET, such that it's equivalent to EXPR in the 2102 sense of vinsn_equal_p function of their vinsns, but not EXPR itself. 2103 Returns NULL if no such expr is in SET was found. */ 2104 static expr_t 2105 av_set_lookup_other_equiv_expr (av_set_t set, expr_t expr) 2106 { 2107 expr_t cur_expr; 2108 av_set_iterator i; 2109 2110 FOR_EACH_EXPR (cur_expr, i, set) 2111 { 2112 if (cur_expr == expr) 2113 continue; 2114 if (vinsn_equal_p (EXPR_VINSN (cur_expr), EXPR_VINSN (expr))) 2115 return cur_expr; 2116 } 2117 2118 return NULL; 2119 } 2120 2121 /* If other expression is already in AVP, remove one of them. */ 2122 expr_t 2123 merge_with_other_exprs (av_set_t *avp, av_set_iterator *ip, expr_t expr) 2124 { 2125 expr_t expr2; 2126 2127 expr2 = av_set_lookup_other_equiv_expr (*avp, expr); 2128 if (expr2 != NULL) 2129 { 2130 /* Reset target availability on merge, since taking it only from one 2131 of the exprs would be controversial for different code. */ 2132 EXPR_TARGET_AVAILABLE (expr2) = -1; 2133 EXPR_USEFULNESS (expr2) = 0; 2134 2135 merge_expr (expr2, expr, NULL); 2136 2137 /* Fix usefulness as it should be now REG_BR_PROB_BASE. */ 2138 EXPR_USEFULNESS (expr2) = REG_BR_PROB_BASE; 2139 2140 av_set_iter_remove (ip); 2141 return expr2; 2142 } 2143 2144 return expr; 2145 } 2146 2147 /* Return true if there is an expr that correlates to VI in SET. */ 2148 bool 2149 av_set_is_in_p (av_set_t set, vinsn_t vi) 2150 { 2151 return av_set_lookup (set, vi) != NULL; 2152 } 2153 2154 /* Return a copy of SET. */ 2155 av_set_t 2156 av_set_copy (av_set_t set) 2157 { 2158 expr_t expr; 2159 av_set_iterator i; 2160 av_set_t res = NULL; 2161 2162 FOR_EACH_EXPR (expr, i, set) 2163 av_set_add (&res, expr); 2164 2165 return res; 2166 } 2167 2168 /* Join two av sets that do not have common elements by attaching second set 2169 (pointed to by FROMP) to the end of first set (TO_TAILP must point to 2170 _AV_SET_NEXT of first set's last element). */ 2171 static void 2172 join_distinct_sets (av_set_t *to_tailp, av_set_t *fromp) 2173 { 2174 gcc_assert (*to_tailp == NULL); 2175 *to_tailp = *fromp; 2176 *fromp = NULL; 2177 } 2178 2179 /* Makes set pointed to by TO to be the union of TO and FROM. Clear av_set 2180 pointed to by FROMP afterwards. */ 2181 void 2182 av_set_union_and_clear (av_set_t *top, av_set_t *fromp, insn_t insn) 2183 { 2184 expr_t expr1; 2185 av_set_iterator i; 2186 2187 /* Delete from TOP all exprs, that present in FROMP. */ 2188 FOR_EACH_EXPR_1 (expr1, i, top) 2189 { 2190 expr_t expr2 = av_set_lookup (*fromp, EXPR_VINSN (expr1)); 2191 2192 if (expr2) 2193 { 2194 merge_expr (expr2, expr1, insn); 2195 av_set_iter_remove (&i); 2196 } 2197 } 2198 2199 join_distinct_sets (i.lp, fromp); 2200 } 2201 2202 /* Same as above, but also update availability of target register in 2203 TOP judging by TO_LV_SET and FROM_LV_SET. */ 2204 void 2205 av_set_union_and_live (av_set_t *top, av_set_t *fromp, regset to_lv_set, 2206 regset from_lv_set, insn_t insn) 2207 { 2208 expr_t expr1; 2209 av_set_iterator i; 2210 av_set_t *to_tailp, in_both_set = NULL; 2211 2212 /* Delete from TOP all expres, that present in FROMP. */ 2213 FOR_EACH_EXPR_1 (expr1, i, top) 2214 { 2215 expr_t expr2 = av_set_lookup_and_remove (fromp, EXPR_VINSN (expr1)); 2216 2217 if (expr2) 2218 { 2219 /* It may be that the expressions have different destination 2220 registers, in which case we need to check liveness here. */ 2221 if (EXPR_SEPARABLE_P (expr1)) 2222 { 2223 int regno1 = (REG_P (EXPR_LHS (expr1)) 2224 ? (int) expr_dest_regno (expr1) : -1); 2225 int regno2 = (REG_P (EXPR_LHS (expr2)) 2226 ? (int) expr_dest_regno (expr2) : -1); 2227 2228 /* ??? We don't have a way to check restrictions for 2229 *other* register on the current path, we did it only 2230 for the current target register. Give up. */ 2231 if (regno1 != regno2) 2232 EXPR_TARGET_AVAILABLE (expr2) = -1; 2233 } 2234 else if (EXPR_INSN_RTX (expr1) != EXPR_INSN_RTX (expr2)) 2235 EXPR_TARGET_AVAILABLE (expr2) = -1; 2236 2237 merge_expr (expr2, expr1, insn); 2238 av_set_add_nocopy (&in_both_set, expr2); 2239 av_set_iter_remove (&i); 2240 } 2241 else 2242 /* EXPR1 is present in TOP, but not in FROMP. Check it on 2243 FROM_LV_SET. */ 2244 set_unavailable_target_for_expr (expr1, from_lv_set); 2245 } 2246 to_tailp = i.lp; 2247 2248 /* These expressions are not present in TOP. Check liveness 2249 restrictions on TO_LV_SET. */ 2250 FOR_EACH_EXPR (expr1, i, *fromp) 2251 set_unavailable_target_for_expr (expr1, to_lv_set); 2252 2253 join_distinct_sets (i.lp, &in_both_set); 2254 join_distinct_sets (to_tailp, fromp); 2255 } 2256 2257 /* Clear av_set pointed to by SETP. */ 2258 void 2259 av_set_clear (av_set_t *setp) 2260 { 2261 expr_t expr; 2262 av_set_iterator i; 2263 2264 FOR_EACH_EXPR_1 (expr, i, setp) 2265 av_set_iter_remove (&i); 2266 2267 gcc_assert (*setp == NULL); 2268 } 2269 2270 /* Leave only one non-speculative element in the SETP. */ 2271 void 2272 av_set_leave_one_nonspec (av_set_t *setp) 2273 { 2274 expr_t expr; 2275 av_set_iterator i; 2276 bool has_one_nonspec = false; 2277 2278 /* Keep all speculative exprs, and leave one non-speculative 2279 (the first one). */ 2280 FOR_EACH_EXPR_1 (expr, i, setp) 2281 { 2282 if (!EXPR_SPEC_DONE_DS (expr)) 2283 { 2284 if (has_one_nonspec) 2285 av_set_iter_remove (&i); 2286 else 2287 has_one_nonspec = true; 2288 } 2289 } 2290 } 2291 2292 /* Return the N'th element of the SET. */ 2293 expr_t 2294 av_set_element (av_set_t set, int n) 2295 { 2296 expr_t expr; 2297 av_set_iterator i; 2298 2299 FOR_EACH_EXPR (expr, i, set) 2300 if (n-- == 0) 2301 return expr; 2302 2303 gcc_unreachable (); 2304 return NULL; 2305 } 2306 2307 /* Deletes all expressions from AVP that are conditional branches (IFs). */ 2308 void 2309 av_set_substract_cond_branches (av_set_t *avp) 2310 { 2311 av_set_iterator i; 2312 expr_t expr; 2313 2314 FOR_EACH_EXPR_1 (expr, i, avp) 2315 if (vinsn_cond_branch_p (EXPR_VINSN (expr))) 2316 av_set_iter_remove (&i); 2317 } 2318 2319 /* Multiplies usefulness attribute of each member of av-set *AVP by 2320 value PROB / ALL_PROB. */ 2321 void 2322 av_set_split_usefulness (av_set_t av, int prob, int all_prob) 2323 { 2324 av_set_iterator i; 2325 expr_t expr; 2326 2327 FOR_EACH_EXPR (expr, i, av) 2328 EXPR_USEFULNESS (expr) = (all_prob 2329 ? (EXPR_USEFULNESS (expr) * prob) / all_prob 2330 : 0); 2331 } 2332 2333 /* Leave in AVP only those expressions, which are present in AV, 2334 and return it, merging history expressions. */ 2335 void 2336 av_set_code_motion_filter (av_set_t *avp, av_set_t av) 2337 { 2338 av_set_iterator i; 2339 expr_t expr, expr2; 2340 2341 FOR_EACH_EXPR_1 (expr, i, avp) 2342 if ((expr2 = av_set_lookup (av, EXPR_VINSN (expr))) == NULL) 2343 av_set_iter_remove (&i); 2344 else 2345 /* When updating av sets in bookkeeping blocks, we can add more insns 2346 there which will be transformed but the upper av sets will not 2347 reflect those transformations. We then fail to undo those 2348 when searching for such insns. So merge the history saved 2349 in the av set of the block we are processing. */ 2350 merge_history_vect (&EXPR_HISTORY_OF_CHANGES (expr), 2351 EXPR_HISTORY_OF_CHANGES (expr2)); 2352 } 2353 2354 2355 2356 /* Dependence hooks to initialize insn data. */ 2357 2358 /* This is used in hooks callable from dependence analysis when initializing 2359 instruction's data. */ 2360 static struct 2361 { 2362 /* Where the dependence was found (lhs/rhs). */ 2363 deps_where_t where; 2364 2365 /* The actual data object to initialize. */ 2366 idata_t id; 2367 2368 /* True when the insn should not be made clonable. */ 2369 bool force_unique_p; 2370 2371 /* True when insn should be treated as of type USE, i.e. never renamed. */ 2372 bool force_use_p; 2373 } deps_init_id_data; 2374 2375 2376 /* Setup ID for INSN. FORCE_UNIQUE_P is true when INSN should not be 2377 clonable. */ 2378 static void 2379 setup_id_for_insn (idata_t id, insn_t insn, bool force_unique_p) 2380 { 2381 int type; 2382 2383 /* Determine whether INSN could be cloned and return appropriate vinsn type. 2384 That clonable insns which can be separated into lhs and rhs have type SET. 2385 Other clonable insns have type USE. */ 2386 type = GET_CODE (insn); 2387 2388 /* Only regular insns could be cloned. */ 2389 if (type == INSN && !force_unique_p) 2390 type = SET; 2391 else if (type == JUMP_INSN && simplejump_p (insn)) 2392 type = PC; 2393 else if (type == DEBUG_INSN) 2394 type = !force_unique_p ? USE : INSN; 2395 2396 IDATA_TYPE (id) = type; 2397 IDATA_REG_SETS (id) = get_clear_regset_from_pool (); 2398 IDATA_REG_USES (id) = get_clear_regset_from_pool (); 2399 IDATA_REG_CLOBBERS (id) = get_clear_regset_from_pool (); 2400 } 2401 2402 /* Start initializing insn data. */ 2403 static void 2404 deps_init_id_start_insn (insn_t insn) 2405 { 2406 gcc_assert (deps_init_id_data.where == DEPS_IN_NOWHERE); 2407 2408 setup_id_for_insn (deps_init_id_data.id, insn, 2409 deps_init_id_data.force_unique_p); 2410 deps_init_id_data.where = DEPS_IN_INSN; 2411 } 2412 2413 /* Start initializing lhs data. */ 2414 static void 2415 deps_init_id_start_lhs (rtx lhs) 2416 { 2417 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN); 2418 gcc_assert (IDATA_LHS (deps_init_id_data.id) == NULL); 2419 2420 if (IDATA_TYPE (deps_init_id_data.id) == SET) 2421 { 2422 IDATA_LHS (deps_init_id_data.id) = lhs; 2423 deps_init_id_data.where = DEPS_IN_LHS; 2424 } 2425 } 2426 2427 /* Finish initializing lhs data. */ 2428 static void 2429 deps_init_id_finish_lhs (void) 2430 { 2431 deps_init_id_data.where = DEPS_IN_INSN; 2432 } 2433 2434 /* Note a set of REGNO. */ 2435 static void 2436 deps_init_id_note_reg_set (int regno) 2437 { 2438 haifa_note_reg_set (regno); 2439 2440 if (deps_init_id_data.where == DEPS_IN_RHS) 2441 deps_init_id_data.force_use_p = true; 2442 2443 if (IDATA_TYPE (deps_init_id_data.id) != PC) 2444 SET_REGNO_REG_SET (IDATA_REG_SETS (deps_init_id_data.id), regno); 2445 2446 #ifdef STACK_REGS 2447 /* Make instructions that set stack registers to be ineligible for 2448 renaming to avoid issues with find_used_regs. */ 2449 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG)) 2450 deps_init_id_data.force_use_p = true; 2451 #endif 2452 } 2453 2454 /* Note a clobber of REGNO. */ 2455 static void 2456 deps_init_id_note_reg_clobber (int regno) 2457 { 2458 haifa_note_reg_clobber (regno); 2459 2460 if (deps_init_id_data.where == DEPS_IN_RHS) 2461 deps_init_id_data.force_use_p = true; 2462 2463 if (IDATA_TYPE (deps_init_id_data.id) != PC) 2464 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (deps_init_id_data.id), regno); 2465 } 2466 2467 /* Note a use of REGNO. */ 2468 static void 2469 deps_init_id_note_reg_use (int regno) 2470 { 2471 haifa_note_reg_use (regno); 2472 2473 if (IDATA_TYPE (deps_init_id_data.id) != PC) 2474 SET_REGNO_REG_SET (IDATA_REG_USES (deps_init_id_data.id), regno); 2475 } 2476 2477 /* Start initializing rhs data. */ 2478 static void 2479 deps_init_id_start_rhs (rtx rhs) 2480 { 2481 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN); 2482 2483 /* And there was no sel_deps_reset_to_insn (). */ 2484 if (IDATA_LHS (deps_init_id_data.id) != NULL) 2485 { 2486 IDATA_RHS (deps_init_id_data.id) = rhs; 2487 deps_init_id_data.where = DEPS_IN_RHS; 2488 } 2489 } 2490 2491 /* Finish initializing rhs data. */ 2492 static void 2493 deps_init_id_finish_rhs (void) 2494 { 2495 gcc_assert (deps_init_id_data.where == DEPS_IN_RHS 2496 || deps_init_id_data.where == DEPS_IN_INSN); 2497 deps_init_id_data.where = DEPS_IN_INSN; 2498 } 2499 2500 /* Finish initializing insn data. */ 2501 static void 2502 deps_init_id_finish_insn (void) 2503 { 2504 gcc_assert (deps_init_id_data.where == DEPS_IN_INSN); 2505 2506 if (IDATA_TYPE (deps_init_id_data.id) == SET) 2507 { 2508 rtx lhs = IDATA_LHS (deps_init_id_data.id); 2509 rtx rhs = IDATA_RHS (deps_init_id_data.id); 2510 2511 if (lhs == NULL || rhs == NULL || !lhs_and_rhs_separable_p (lhs, rhs) 2512 || deps_init_id_data.force_use_p) 2513 { 2514 /* This should be a USE, as we don't want to schedule its RHS 2515 separately. However, we still want to have them recorded 2516 for the purposes of substitution. That's why we don't 2517 simply call downgrade_to_use () here. */ 2518 gcc_assert (IDATA_TYPE (deps_init_id_data.id) == SET); 2519 gcc_assert (!lhs == !rhs); 2520 2521 IDATA_TYPE (deps_init_id_data.id) = USE; 2522 } 2523 } 2524 2525 deps_init_id_data.where = DEPS_IN_NOWHERE; 2526 } 2527 2528 /* This is dependence info used for initializing insn's data. */ 2529 static struct sched_deps_info_def deps_init_id_sched_deps_info; 2530 2531 /* This initializes most of the static part of the above structure. */ 2532 static const struct sched_deps_info_def const_deps_init_id_sched_deps_info = 2533 { 2534 NULL, 2535 2536 deps_init_id_start_insn, 2537 deps_init_id_finish_insn, 2538 deps_init_id_start_lhs, 2539 deps_init_id_finish_lhs, 2540 deps_init_id_start_rhs, 2541 deps_init_id_finish_rhs, 2542 deps_init_id_note_reg_set, 2543 deps_init_id_note_reg_clobber, 2544 deps_init_id_note_reg_use, 2545 NULL, /* note_mem_dep */ 2546 NULL, /* note_dep */ 2547 2548 0, /* use_cselib */ 2549 0, /* use_deps_list */ 2550 0 /* generate_spec_deps */ 2551 }; 2552 2553 /* Initialize INSN's lhs and rhs in ID. When FORCE_UNIQUE_P is true, 2554 we don't actually need information about lhs and rhs. */ 2555 static void 2556 setup_id_lhs_rhs (idata_t id, insn_t insn, bool force_unique_p) 2557 { 2558 rtx pat = PATTERN (insn); 2559 2560 if (NONJUMP_INSN_P (insn) 2561 && GET_CODE (pat) == SET 2562 && !force_unique_p) 2563 { 2564 IDATA_RHS (id) = SET_SRC (pat); 2565 IDATA_LHS (id) = SET_DEST (pat); 2566 } 2567 else 2568 IDATA_LHS (id) = IDATA_RHS (id) = NULL; 2569 } 2570 2571 /* Possibly downgrade INSN to USE. */ 2572 static void 2573 maybe_downgrade_id_to_use (idata_t id, insn_t insn) 2574 { 2575 bool must_be_use = false; 2576 unsigned uid = INSN_UID (insn); 2577 df_ref *rec; 2578 rtx lhs = IDATA_LHS (id); 2579 rtx rhs = IDATA_RHS (id); 2580 2581 /* We downgrade only SETs. */ 2582 if (IDATA_TYPE (id) != SET) 2583 return; 2584 2585 if (!lhs || !lhs_and_rhs_separable_p (lhs, rhs)) 2586 { 2587 IDATA_TYPE (id) = USE; 2588 return; 2589 } 2590 2591 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++) 2592 { 2593 df_ref def = *rec; 2594 2595 if (DF_REF_INSN (def) 2596 && DF_REF_FLAGS_IS_SET (def, DF_REF_PRE_POST_MODIFY) 2597 && loc_mentioned_in_p (DF_REF_LOC (def), IDATA_RHS (id))) 2598 { 2599 must_be_use = true; 2600 break; 2601 } 2602 2603 #ifdef STACK_REGS 2604 /* Make instructions that set stack registers to be ineligible for 2605 renaming to avoid issues with find_used_regs. */ 2606 if (IN_RANGE (DF_REF_REGNO (def), FIRST_STACK_REG, LAST_STACK_REG)) 2607 { 2608 must_be_use = true; 2609 break; 2610 } 2611 #endif 2612 } 2613 2614 if (must_be_use) 2615 IDATA_TYPE (id) = USE; 2616 } 2617 2618 /* Setup register sets describing INSN in ID. */ 2619 static void 2620 setup_id_reg_sets (idata_t id, insn_t insn) 2621 { 2622 unsigned uid = INSN_UID (insn); 2623 df_ref *rec; 2624 regset tmp = get_clear_regset_from_pool (); 2625 2626 for (rec = DF_INSN_UID_DEFS (uid); *rec; rec++) 2627 { 2628 df_ref def = *rec; 2629 unsigned int regno = DF_REF_REGNO (def); 2630 2631 /* Post modifies are treated like clobbers by sched-deps.c. */ 2632 if (DF_REF_FLAGS_IS_SET (def, (DF_REF_MUST_CLOBBER 2633 | DF_REF_PRE_POST_MODIFY))) 2634 SET_REGNO_REG_SET (IDATA_REG_CLOBBERS (id), regno); 2635 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER)) 2636 { 2637 SET_REGNO_REG_SET (IDATA_REG_SETS (id), regno); 2638 2639 #ifdef STACK_REGS 2640 /* For stack registers, treat writes to them as writes 2641 to the first one to be consistent with sched-deps.c. */ 2642 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG)) 2643 SET_REGNO_REG_SET (IDATA_REG_SETS (id), FIRST_STACK_REG); 2644 #endif 2645 } 2646 /* Mark special refs that generate read/write def pair. */ 2647 if (DF_REF_FLAGS_IS_SET (def, DF_REF_CONDITIONAL) 2648 || regno == STACK_POINTER_REGNUM) 2649 bitmap_set_bit (tmp, regno); 2650 } 2651 2652 for (rec = DF_INSN_UID_USES (uid); *rec; rec++) 2653 { 2654 df_ref use = *rec; 2655 unsigned int regno = DF_REF_REGNO (use); 2656 2657 /* When these refs are met for the first time, skip them, as 2658 these uses are just counterparts of some defs. */ 2659 if (bitmap_bit_p (tmp, regno)) 2660 bitmap_clear_bit (tmp, regno); 2661 else if (! DF_REF_FLAGS_IS_SET (use, DF_REF_CALL_STACK_USAGE)) 2662 { 2663 SET_REGNO_REG_SET (IDATA_REG_USES (id), regno); 2664 2665 #ifdef STACK_REGS 2666 /* For stack registers, treat reads from them as reads from 2667 the first one to be consistent with sched-deps.c. */ 2668 if (IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG)) 2669 SET_REGNO_REG_SET (IDATA_REG_USES (id), FIRST_STACK_REG); 2670 #endif 2671 } 2672 } 2673 2674 return_regset_to_pool (tmp); 2675 } 2676 2677 /* Initialize instruction data for INSN in ID using DF's data. */ 2678 static void 2679 init_id_from_df (idata_t id, insn_t insn, bool force_unique_p) 2680 { 2681 gcc_assert (DF_INSN_UID_SAFE_GET (INSN_UID (insn)) != NULL); 2682 2683 setup_id_for_insn (id, insn, force_unique_p); 2684 setup_id_lhs_rhs (id, insn, force_unique_p); 2685 2686 if (INSN_NOP_P (insn)) 2687 return; 2688 2689 maybe_downgrade_id_to_use (id, insn); 2690 setup_id_reg_sets (id, insn); 2691 } 2692 2693 /* Initialize instruction data for INSN in ID. */ 2694 static void 2695 deps_init_id (idata_t id, insn_t insn, bool force_unique_p) 2696 { 2697 struct deps_desc _dc, *dc = &_dc; 2698 2699 deps_init_id_data.where = DEPS_IN_NOWHERE; 2700 deps_init_id_data.id = id; 2701 deps_init_id_data.force_unique_p = force_unique_p; 2702 deps_init_id_data.force_use_p = false; 2703 2704 init_deps (dc, false); 2705 2706 memcpy (&deps_init_id_sched_deps_info, 2707 &const_deps_init_id_sched_deps_info, 2708 sizeof (deps_init_id_sched_deps_info)); 2709 2710 if (spec_info != NULL) 2711 deps_init_id_sched_deps_info.generate_spec_deps = 1; 2712 2713 sched_deps_info = &deps_init_id_sched_deps_info; 2714 2715 deps_analyze_insn (dc, insn); 2716 2717 free_deps (dc); 2718 2719 deps_init_id_data.id = NULL; 2720 } 2721 2722 2723 2724 /* Implement hooks for collecting fundamental insn properties like if insn is 2725 an ASM or is within a SCHED_GROUP. */ 2726 2727 /* True when a "one-time init" data for INSN was already inited. */ 2728 static bool 2729 first_time_insn_init (insn_t insn) 2730 { 2731 return INSN_LIVE (insn) == NULL; 2732 } 2733 2734 /* Hash an entry in a transformed_insns hashtable. */ 2735 static hashval_t 2736 hash_transformed_insns (const void *p) 2737 { 2738 return VINSN_HASH_RTX (((const struct transformed_insns *) p)->vinsn_old); 2739 } 2740 2741 /* Compare the entries in a transformed_insns hashtable. */ 2742 static int 2743 eq_transformed_insns (const void *p, const void *q) 2744 { 2745 rtx i1 = VINSN_INSN_RTX (((const struct transformed_insns *) p)->vinsn_old); 2746 rtx i2 = VINSN_INSN_RTX (((const struct transformed_insns *) q)->vinsn_old); 2747 2748 if (INSN_UID (i1) == INSN_UID (i2)) 2749 return 1; 2750 return rtx_equal_p (PATTERN (i1), PATTERN (i2)); 2751 } 2752 2753 /* Free an entry in a transformed_insns hashtable. */ 2754 static void 2755 free_transformed_insns (void *p) 2756 { 2757 struct transformed_insns *pti = (struct transformed_insns *) p; 2758 2759 vinsn_detach (pti->vinsn_old); 2760 vinsn_detach (pti->vinsn_new); 2761 free (pti); 2762 } 2763 2764 /* Init the s_i_d data for INSN which should be inited just once, when 2765 we first see the insn. */ 2766 static void 2767 init_first_time_insn_data (insn_t insn) 2768 { 2769 /* This should not be set if this is the first time we init data for 2770 insn. */ 2771 gcc_assert (first_time_insn_init (insn)); 2772 2773 /* These are needed for nops too. */ 2774 INSN_LIVE (insn) = get_regset_from_pool (); 2775 INSN_LIVE_VALID_P (insn) = false; 2776 2777 if (!INSN_NOP_P (insn)) 2778 { 2779 INSN_ANALYZED_DEPS (insn) = BITMAP_ALLOC (NULL); 2780 INSN_FOUND_DEPS (insn) = BITMAP_ALLOC (NULL); 2781 INSN_TRANSFORMED_INSNS (insn) 2782 = htab_create (16, hash_transformed_insns, 2783 eq_transformed_insns, free_transformed_insns); 2784 init_deps (&INSN_DEPS_CONTEXT (insn), true); 2785 } 2786 } 2787 2788 /* Free almost all above data for INSN that is scheduled already. 2789 Used for extra-large basic blocks. */ 2790 void 2791 free_data_for_scheduled_insn (insn_t insn) 2792 { 2793 gcc_assert (! first_time_insn_init (insn)); 2794 2795 if (! INSN_ANALYZED_DEPS (insn)) 2796 return; 2797 2798 BITMAP_FREE (INSN_ANALYZED_DEPS (insn)); 2799 BITMAP_FREE (INSN_FOUND_DEPS (insn)); 2800 htab_delete (INSN_TRANSFORMED_INSNS (insn)); 2801 2802 /* This is allocated only for bookkeeping insns. */ 2803 if (INSN_ORIGINATORS (insn)) 2804 BITMAP_FREE (INSN_ORIGINATORS (insn)); 2805 free_deps (&INSN_DEPS_CONTEXT (insn)); 2806 2807 INSN_ANALYZED_DEPS (insn) = NULL; 2808 2809 /* Clear the readonly flag so we would ICE when trying to recalculate 2810 the deps context (as we believe that it should not happen). */ 2811 (&INSN_DEPS_CONTEXT (insn))->readonly = 0; 2812 } 2813 2814 /* Free the same data as above for INSN. */ 2815 static void 2816 free_first_time_insn_data (insn_t insn) 2817 { 2818 gcc_assert (! first_time_insn_init (insn)); 2819 2820 free_data_for_scheduled_insn (insn); 2821 return_regset_to_pool (INSN_LIVE (insn)); 2822 INSN_LIVE (insn) = NULL; 2823 INSN_LIVE_VALID_P (insn) = false; 2824 } 2825 2826 /* Initialize region-scope data structures for basic blocks. */ 2827 static void 2828 init_global_and_expr_for_bb (basic_block bb) 2829 { 2830 if (sel_bb_empty_p (bb)) 2831 return; 2832 2833 invalidate_av_set (bb); 2834 } 2835 2836 /* Data for global dependency analysis (to initialize CANT_MOVE and 2837 SCHED_GROUP_P). */ 2838 static struct 2839 { 2840 /* Previous insn. */ 2841 insn_t prev_insn; 2842 } init_global_data; 2843 2844 /* Determine if INSN is in the sched_group, is an asm or should not be 2845 cloned. After that initialize its expr. */ 2846 static void 2847 init_global_and_expr_for_insn (insn_t insn) 2848 { 2849 if (LABEL_P (insn)) 2850 return; 2851 2852 if (NOTE_INSN_BASIC_BLOCK_P (insn)) 2853 { 2854 init_global_data.prev_insn = NULL_RTX; 2855 return; 2856 } 2857 2858 gcc_assert (INSN_P (insn)); 2859 2860 if (SCHED_GROUP_P (insn)) 2861 /* Setup a sched_group. */ 2862 { 2863 insn_t prev_insn = init_global_data.prev_insn; 2864 2865 if (prev_insn) 2866 INSN_SCHED_NEXT (prev_insn) = insn; 2867 2868 init_global_data.prev_insn = insn; 2869 } 2870 else 2871 init_global_data.prev_insn = NULL_RTX; 2872 2873 if (GET_CODE (PATTERN (insn)) == ASM_INPUT 2874 || asm_noperands (PATTERN (insn)) >= 0) 2875 /* Mark INSN as an asm. */ 2876 INSN_ASM_P (insn) = true; 2877 2878 { 2879 bool force_unique_p; 2880 ds_t spec_done_ds; 2881 2882 /* Certain instructions cannot be cloned. */ 2883 if (CANT_MOVE (insn) 2884 || INSN_ASM_P (insn) 2885 || SCHED_GROUP_P (insn) 2886 || prologue_epilogue_contains (insn) 2887 /* Exception handling insns are always unique. */ 2888 || (flag_non_call_exceptions && can_throw_internal (insn)) 2889 /* TRAP_IF though have an INSN code is control_flow_insn_p (). */ 2890 || control_flow_insn_p (insn)) 2891 force_unique_p = true; 2892 else 2893 force_unique_p = false; 2894 2895 if (targetm.sched.get_insn_spec_ds) 2896 { 2897 spec_done_ds = targetm.sched.get_insn_spec_ds (insn); 2898 spec_done_ds = ds_get_max_dep_weak (spec_done_ds); 2899 } 2900 else 2901 spec_done_ds = 0; 2902 2903 /* Initialize INSN's expr. */ 2904 init_expr (INSN_EXPR (insn), vinsn_create (insn, force_unique_p), 0, 2905 REG_BR_PROB_BASE, INSN_PRIORITY (insn), 0, BLOCK_NUM (insn), 2906 spec_done_ds, 0, 0, NULL, true, false, false, false, 2907 CANT_MOVE (insn)); 2908 } 2909 2910 init_first_time_insn_data (insn); 2911 } 2912 2913 /* Scan the region and initialize instruction data for basic blocks BBS. */ 2914 void 2915 sel_init_global_and_expr (bb_vec_t bbs) 2916 { 2917 /* ??? It would be nice to implement push / pop scheme for sched_infos. */ 2918 const struct sched_scan_info_def ssi = 2919 { 2920 NULL, /* extend_bb */ 2921 init_global_and_expr_for_bb, /* init_bb */ 2922 extend_insn_data, /* extend_insn */ 2923 init_global_and_expr_for_insn /* init_insn */ 2924 }; 2925 2926 sched_scan (&ssi, bbs, NULL, NULL, NULL); 2927 } 2928 2929 /* Finalize region-scope data structures for basic blocks. */ 2930 static void 2931 finish_global_and_expr_for_bb (basic_block bb) 2932 { 2933 av_set_clear (&BB_AV_SET (bb)); 2934 BB_AV_LEVEL (bb) = 0; 2935 } 2936 2937 /* Finalize INSN's data. */ 2938 static void 2939 finish_global_and_expr_insn (insn_t insn) 2940 { 2941 if (LABEL_P (insn) || NOTE_INSN_BASIC_BLOCK_P (insn)) 2942 return; 2943 2944 gcc_assert (INSN_P (insn)); 2945 2946 if (INSN_LUID (insn) > 0) 2947 { 2948 free_first_time_insn_data (insn); 2949 INSN_WS_LEVEL (insn) = 0; 2950 CANT_MOVE (insn) = 0; 2951 2952 /* We can no longer assert this, as vinsns of this insn could be 2953 easily live in other insn's caches. This should be changed to 2954 a counter-like approach among all vinsns. */ 2955 gcc_assert (true || VINSN_COUNT (INSN_VINSN (insn)) == 1); 2956 clear_expr (INSN_EXPR (insn)); 2957 } 2958 } 2959 2960 /* Finalize per instruction data for the whole region. */ 2961 void 2962 sel_finish_global_and_expr (void) 2963 { 2964 { 2965 bb_vec_t bbs; 2966 int i; 2967 2968 bbs = VEC_alloc (basic_block, heap, current_nr_blocks); 2969 2970 for (i = 0; i < current_nr_blocks; i++) 2971 VEC_quick_push (basic_block, bbs, BASIC_BLOCK (BB_TO_BLOCK (i))); 2972 2973 /* Clear AV_SETs and INSN_EXPRs. */ 2974 { 2975 const struct sched_scan_info_def ssi = 2976 { 2977 NULL, /* extend_bb */ 2978 finish_global_and_expr_for_bb, /* init_bb */ 2979 NULL, /* extend_insn */ 2980 finish_global_and_expr_insn /* init_insn */ 2981 }; 2982 2983 sched_scan (&ssi, bbs, NULL, NULL, NULL); 2984 } 2985 2986 VEC_free (basic_block, heap, bbs); 2987 } 2988 2989 finish_insns (); 2990 } 2991 2992 2993 /* In the below hooks, we merely calculate whether or not a dependence 2994 exists, and in what part of insn. However, we will need more data 2995 when we'll start caching dependence requests. */ 2996 2997 /* Container to hold information for dependency analysis. */ 2998 static struct 2999 { 3000 deps_t dc; 3001 3002 /* A variable to track which part of rtx we are scanning in 3003 sched-deps.c: sched_analyze_insn (). */ 3004 deps_where_t where; 3005 3006 /* Current producer. */ 3007 insn_t pro; 3008 3009 /* Current consumer. */ 3010 vinsn_t con; 3011 3012 /* Is SEL_DEPS_HAS_DEP_P[DEPS_IN_X] is true, then X has a dependence. 3013 X is from { INSN, LHS, RHS }. */ 3014 ds_t has_dep_p[DEPS_IN_NOWHERE]; 3015 } has_dependence_data; 3016 3017 /* Start analyzing dependencies of INSN. */ 3018 static void 3019 has_dependence_start_insn (insn_t insn ATTRIBUTE_UNUSED) 3020 { 3021 gcc_assert (has_dependence_data.where == DEPS_IN_NOWHERE); 3022 3023 has_dependence_data.where = DEPS_IN_INSN; 3024 } 3025 3026 /* Finish analyzing dependencies of an insn. */ 3027 static void 3028 has_dependence_finish_insn (void) 3029 { 3030 gcc_assert (has_dependence_data.where == DEPS_IN_INSN); 3031 3032 has_dependence_data.where = DEPS_IN_NOWHERE; 3033 } 3034 3035 /* Start analyzing dependencies of LHS. */ 3036 static void 3037 has_dependence_start_lhs (rtx lhs ATTRIBUTE_UNUSED) 3038 { 3039 gcc_assert (has_dependence_data.where == DEPS_IN_INSN); 3040 3041 if (VINSN_LHS (has_dependence_data.con) != NULL) 3042 has_dependence_data.where = DEPS_IN_LHS; 3043 } 3044 3045 /* Finish analyzing dependencies of an lhs. */ 3046 static void 3047 has_dependence_finish_lhs (void) 3048 { 3049 has_dependence_data.where = DEPS_IN_INSN; 3050 } 3051 3052 /* Start analyzing dependencies of RHS. */ 3053 static void 3054 has_dependence_start_rhs (rtx rhs ATTRIBUTE_UNUSED) 3055 { 3056 gcc_assert (has_dependence_data.where == DEPS_IN_INSN); 3057 3058 if (VINSN_RHS (has_dependence_data.con) != NULL) 3059 has_dependence_data.where = DEPS_IN_RHS; 3060 } 3061 3062 /* Start analyzing dependencies of an rhs. */ 3063 static void 3064 has_dependence_finish_rhs (void) 3065 { 3066 gcc_assert (has_dependence_data.where == DEPS_IN_RHS 3067 || has_dependence_data.where == DEPS_IN_INSN); 3068 3069 has_dependence_data.where = DEPS_IN_INSN; 3070 } 3071 3072 /* Note a set of REGNO. */ 3073 static void 3074 has_dependence_note_reg_set (int regno) 3075 { 3076 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno]; 3077 3078 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro, 3079 VINSN_INSN_RTX 3080 (has_dependence_data.con))) 3081 { 3082 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where]; 3083 3084 if (reg_last->sets != NULL 3085 || reg_last->clobbers != NULL) 3086 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT; 3087 3088 if (reg_last->uses) 3089 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI; 3090 } 3091 } 3092 3093 /* Note a clobber of REGNO. */ 3094 static void 3095 has_dependence_note_reg_clobber (int regno) 3096 { 3097 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno]; 3098 3099 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro, 3100 VINSN_INSN_RTX 3101 (has_dependence_data.con))) 3102 { 3103 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where]; 3104 3105 if (reg_last->sets) 3106 *dsp = (*dsp & ~SPECULATIVE) | DEP_OUTPUT; 3107 3108 if (reg_last->uses) 3109 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI; 3110 } 3111 } 3112 3113 /* Note a use of REGNO. */ 3114 static void 3115 has_dependence_note_reg_use (int regno) 3116 { 3117 struct deps_reg *reg_last = &has_dependence_data.dc->reg_last[regno]; 3118 3119 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro, 3120 VINSN_INSN_RTX 3121 (has_dependence_data.con))) 3122 { 3123 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where]; 3124 3125 if (reg_last->sets) 3126 *dsp = (*dsp & ~SPECULATIVE) | DEP_TRUE; 3127 3128 if (reg_last->clobbers) 3129 *dsp = (*dsp & ~SPECULATIVE) | DEP_ANTI; 3130 3131 /* Handle BE_IN_SPEC. */ 3132 if (reg_last->uses) 3133 { 3134 ds_t pro_spec_checked_ds; 3135 3136 pro_spec_checked_ds = INSN_SPEC_CHECKED_DS (has_dependence_data.pro); 3137 pro_spec_checked_ds = ds_get_max_dep_weak (pro_spec_checked_ds); 3138 3139 if (pro_spec_checked_ds != 0) 3140 /* Merge BE_IN_SPEC bits into *DSP. */ 3141 *dsp = ds_full_merge (*dsp, pro_spec_checked_ds, 3142 NULL_RTX, NULL_RTX); 3143 } 3144 } 3145 } 3146 3147 /* Note a memory dependence. */ 3148 static void 3149 has_dependence_note_mem_dep (rtx mem ATTRIBUTE_UNUSED, 3150 rtx pending_mem ATTRIBUTE_UNUSED, 3151 insn_t pending_insn ATTRIBUTE_UNUSED, 3152 ds_t ds ATTRIBUTE_UNUSED) 3153 { 3154 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro, 3155 VINSN_INSN_RTX (has_dependence_data.con))) 3156 { 3157 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where]; 3158 3159 *dsp = ds_full_merge (ds, *dsp, pending_mem, mem); 3160 } 3161 } 3162 3163 /* Note a dependence. */ 3164 static void 3165 has_dependence_note_dep (insn_t pro ATTRIBUTE_UNUSED, 3166 ds_t ds ATTRIBUTE_UNUSED) 3167 { 3168 if (!sched_insns_conditions_mutex_p (has_dependence_data.pro, 3169 VINSN_INSN_RTX (has_dependence_data.con))) 3170 { 3171 ds_t *dsp = &has_dependence_data.has_dep_p[has_dependence_data.where]; 3172 3173 *dsp = ds_full_merge (ds, *dsp, NULL_RTX, NULL_RTX); 3174 } 3175 } 3176 3177 /* Mark the insn as having a hard dependence that prevents speculation. */ 3178 void 3179 sel_mark_hard_insn (rtx insn) 3180 { 3181 int i; 3182 3183 /* Only work when we're in has_dependence_p mode. 3184 ??? This is a hack, this should actually be a hook. */ 3185 if (!has_dependence_data.dc || !has_dependence_data.pro) 3186 return; 3187 3188 gcc_assert (insn == VINSN_INSN_RTX (has_dependence_data.con)); 3189 gcc_assert (has_dependence_data.where == DEPS_IN_INSN); 3190 3191 for (i = 0; i < DEPS_IN_NOWHERE; i++) 3192 has_dependence_data.has_dep_p[i] &= ~SPECULATIVE; 3193 } 3194 3195 /* This structure holds the hooks for the dependency analysis used when 3196 actually processing dependencies in the scheduler. */ 3197 static struct sched_deps_info_def has_dependence_sched_deps_info; 3198 3199 /* This initializes most of the fields of the above structure. */ 3200 static const struct sched_deps_info_def const_has_dependence_sched_deps_info = 3201 { 3202 NULL, 3203 3204 has_dependence_start_insn, 3205 has_dependence_finish_insn, 3206 has_dependence_start_lhs, 3207 has_dependence_finish_lhs, 3208 has_dependence_start_rhs, 3209 has_dependence_finish_rhs, 3210 has_dependence_note_reg_set, 3211 has_dependence_note_reg_clobber, 3212 has_dependence_note_reg_use, 3213 has_dependence_note_mem_dep, 3214 has_dependence_note_dep, 3215 3216 0, /* use_cselib */ 3217 0, /* use_deps_list */ 3218 0 /* generate_spec_deps */ 3219 }; 3220 3221 /* Initialize has_dependence_sched_deps_info with extra spec field. */ 3222 static void 3223 setup_has_dependence_sched_deps_info (void) 3224 { 3225 memcpy (&has_dependence_sched_deps_info, 3226 &const_has_dependence_sched_deps_info, 3227 sizeof (has_dependence_sched_deps_info)); 3228 3229 if (spec_info != NULL) 3230 has_dependence_sched_deps_info.generate_spec_deps = 1; 3231 3232 sched_deps_info = &has_dependence_sched_deps_info; 3233 } 3234 3235 /* Remove all dependences found and recorded in has_dependence_data array. */ 3236 void 3237 sel_clear_has_dependence (void) 3238 { 3239 int i; 3240 3241 for (i = 0; i < DEPS_IN_NOWHERE; i++) 3242 has_dependence_data.has_dep_p[i] = 0; 3243 } 3244 3245 /* Return nonzero if EXPR has is dependent upon PRED. Return the pointer 3246 to the dependence information array in HAS_DEP_PP. */ 3247 ds_t 3248 has_dependence_p (expr_t expr, insn_t pred, ds_t **has_dep_pp) 3249 { 3250 int i; 3251 ds_t ds; 3252 struct deps_desc *dc; 3253 3254 if (INSN_SIMPLEJUMP_P (pred)) 3255 /* Unconditional jump is just a transfer of control flow. 3256 Ignore it. */ 3257 return false; 3258 3259 dc = &INSN_DEPS_CONTEXT (pred); 3260 3261 /* We init this field lazily. */ 3262 if (dc->reg_last == NULL) 3263 init_deps_reg_last (dc); 3264 3265 if (!dc->readonly) 3266 { 3267 has_dependence_data.pro = NULL; 3268 /* Initialize empty dep context with information about PRED. */ 3269 advance_deps_context (dc, pred); 3270 dc->readonly = 1; 3271 } 3272 3273 has_dependence_data.where = DEPS_IN_NOWHERE; 3274 has_dependence_data.pro = pred; 3275 has_dependence_data.con = EXPR_VINSN (expr); 3276 has_dependence_data.dc = dc; 3277 3278 sel_clear_has_dependence (); 3279 3280 /* Now catch all dependencies that would be generated between PRED and 3281 INSN. */ 3282 setup_has_dependence_sched_deps_info (); 3283 deps_analyze_insn (dc, EXPR_INSN_RTX (expr)); 3284 has_dependence_data.dc = NULL; 3285 3286 /* When a barrier was found, set DEPS_IN_INSN bits. */ 3287 if (dc->last_reg_pending_barrier == TRUE_BARRIER) 3288 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_TRUE; 3289 else if (dc->last_reg_pending_barrier == MOVE_BARRIER) 3290 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI; 3291 3292 /* Do not allow stores to memory to move through checks. Currently 3293 we don't move this to sched-deps.c as the check doesn't have 3294 obvious places to which this dependence can be attached. 3295 FIMXE: this should go to a hook. */ 3296 if (EXPR_LHS (expr) 3297 && MEM_P (EXPR_LHS (expr)) 3298 && sel_insn_is_speculation_check (pred)) 3299 has_dependence_data.has_dep_p[DEPS_IN_INSN] = DEP_ANTI; 3300 3301 *has_dep_pp = has_dependence_data.has_dep_p; 3302 ds = 0; 3303 for (i = 0; i < DEPS_IN_NOWHERE; i++) 3304 ds = ds_full_merge (ds, has_dependence_data.has_dep_p[i], 3305 NULL_RTX, NULL_RTX); 3306 3307 return ds; 3308 } 3309 3310 3311 /* Dependence hooks implementation that checks dependence latency constraints 3312 on the insns being scheduled. The entry point for these routines is 3313 tick_check_p predicate. */ 3314 3315 static struct 3316 { 3317 /* An expr we are currently checking. */ 3318 expr_t expr; 3319 3320 /* A minimal cycle for its scheduling. */ 3321 int cycle; 3322 3323 /* Whether we have seen a true dependence while checking. */ 3324 bool seen_true_dep_p; 3325 } tick_check_data; 3326 3327 /* Update minimal scheduling cycle for tick_check_insn given that it depends 3328 on PRO with status DS and weight DW. */ 3329 static void 3330 tick_check_dep_with_dw (insn_t pro_insn, ds_t ds, dw_t dw) 3331 { 3332 expr_t con_expr = tick_check_data.expr; 3333 insn_t con_insn = EXPR_INSN_RTX (con_expr); 3334 3335 if (con_insn != pro_insn) 3336 { 3337 enum reg_note dt; 3338 int tick; 3339 3340 if (/* PROducer was removed from above due to pipelining. */ 3341 !INSN_IN_STREAM_P (pro_insn) 3342 /* Or PROducer was originally on the next iteration regarding the 3343 CONsumer. */ 3344 || (INSN_SCHED_TIMES (pro_insn) 3345 - EXPR_SCHED_TIMES (con_expr)) > 1) 3346 /* Don't count this dependence. */ 3347 return; 3348 3349 dt = ds_to_dt (ds); 3350 if (dt == REG_DEP_TRUE) 3351 tick_check_data.seen_true_dep_p = true; 3352 3353 gcc_assert (INSN_SCHED_CYCLE (pro_insn) > 0); 3354 3355 { 3356 dep_def _dep, *dep = &_dep; 3357 3358 init_dep (dep, pro_insn, con_insn, dt); 3359 3360 tick = INSN_SCHED_CYCLE (pro_insn) + dep_cost_1 (dep, dw); 3361 } 3362 3363 /* When there are several kinds of dependencies between pro and con, 3364 only REG_DEP_TRUE should be taken into account. */ 3365 if (tick > tick_check_data.cycle 3366 && (dt == REG_DEP_TRUE || !tick_check_data.seen_true_dep_p)) 3367 tick_check_data.cycle = tick; 3368 } 3369 } 3370 3371 /* An implementation of note_dep hook. */ 3372 static void 3373 tick_check_note_dep (insn_t pro, ds_t ds) 3374 { 3375 tick_check_dep_with_dw (pro, ds, 0); 3376 } 3377 3378 /* An implementation of note_mem_dep hook. */ 3379 static void 3380 tick_check_note_mem_dep (rtx mem1, rtx mem2, insn_t pro, ds_t ds) 3381 { 3382 dw_t dw; 3383 3384 dw = (ds_to_dt (ds) == REG_DEP_TRUE 3385 ? estimate_dep_weak (mem1, mem2) 3386 : 0); 3387 3388 tick_check_dep_with_dw (pro, ds, dw); 3389 } 3390 3391 /* This structure contains hooks for dependence analysis used when determining 3392 whether an insn is ready for scheduling. */ 3393 static struct sched_deps_info_def tick_check_sched_deps_info = 3394 { 3395 NULL, 3396 3397 NULL, 3398 NULL, 3399 NULL, 3400 NULL, 3401 NULL, 3402 NULL, 3403 haifa_note_reg_set, 3404 haifa_note_reg_clobber, 3405 haifa_note_reg_use, 3406 tick_check_note_mem_dep, 3407 tick_check_note_dep, 3408 3409 0, 0, 0 3410 }; 3411 3412 /* Estimate number of cycles from the current cycle of FENCE until EXPR can be 3413 scheduled. Return 0 if all data from producers in DC is ready. */ 3414 int 3415 tick_check_p (expr_t expr, deps_t dc, fence_t fence) 3416 { 3417 int cycles_left; 3418 /* Initialize variables. */ 3419 tick_check_data.expr = expr; 3420 tick_check_data.cycle = 0; 3421 tick_check_data.seen_true_dep_p = false; 3422 sched_deps_info = &tick_check_sched_deps_info; 3423 3424 gcc_assert (!dc->readonly); 3425 dc->readonly = 1; 3426 deps_analyze_insn (dc, EXPR_INSN_RTX (expr)); 3427 dc->readonly = 0; 3428 3429 cycles_left = tick_check_data.cycle - FENCE_CYCLE (fence); 3430 3431 return cycles_left >= 0 ? cycles_left : 0; 3432 } 3433 3434 3435 /* Functions to work with insns. */ 3436 3437 /* Returns true if LHS of INSN is the same as DEST of an insn 3438 being moved. */ 3439 bool 3440 lhs_of_insn_equals_to_dest_p (insn_t insn, rtx dest) 3441 { 3442 rtx lhs = INSN_LHS (insn); 3443 3444 if (lhs == NULL || dest == NULL) 3445 return false; 3446 3447 return rtx_equal_p (lhs, dest); 3448 } 3449 3450 /* Return s_i_d entry of INSN. Callable from debugger. */ 3451 sel_insn_data_def 3452 insn_sid (insn_t insn) 3453 { 3454 return *SID (insn); 3455 } 3456 3457 /* True when INSN is a speculative check. We can tell this by looking 3458 at the data structures of the selective scheduler, not by examining 3459 the pattern. */ 3460 bool 3461 sel_insn_is_speculation_check (rtx insn) 3462 { 3463 return s_i_d && !! INSN_SPEC_CHECKED_DS (insn); 3464 } 3465 3466 /* Extracts machine mode MODE and destination location DST_LOC 3467 for given INSN. */ 3468 void 3469 get_dest_and_mode (rtx insn, rtx *dst_loc, enum machine_mode *mode) 3470 { 3471 rtx pat = PATTERN (insn); 3472 3473 gcc_assert (dst_loc); 3474 gcc_assert (GET_CODE (pat) == SET); 3475 3476 *dst_loc = SET_DEST (pat); 3477 3478 gcc_assert (*dst_loc); 3479 gcc_assert (MEM_P (*dst_loc) || REG_P (*dst_loc)); 3480 3481 if (mode) 3482 *mode = GET_MODE (*dst_loc); 3483 } 3484 3485 /* Returns true when moving through JUMP will result in bookkeeping 3486 creation. */ 3487 bool 3488 bookkeeping_can_be_created_if_moved_through_p (insn_t jump) 3489 { 3490 insn_t succ; 3491 succ_iterator si; 3492 3493 FOR_EACH_SUCC (succ, si, jump) 3494 if (sel_num_cfg_preds_gt_1 (succ)) 3495 return true; 3496 3497 return false; 3498 } 3499 3500 /* Return 'true' if INSN is the only one in its basic block. */ 3501 static bool 3502 insn_is_the_only_one_in_bb_p (insn_t insn) 3503 { 3504 return sel_bb_head_p (insn) && sel_bb_end_p (insn); 3505 } 3506 3507 #ifdef ENABLE_CHECKING 3508 /* Check that the region we're scheduling still has at most one 3509 backedge. */ 3510 static void 3511 verify_backedges (void) 3512 { 3513 if (pipelining_p) 3514 { 3515 int i, n = 0; 3516 edge e; 3517 edge_iterator ei; 3518 3519 for (i = 0; i < current_nr_blocks; i++) 3520 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (BB_TO_BLOCK (i))->succs) 3521 if (in_current_region_p (e->dest) 3522 && BLOCK_TO_BB (e->dest->index) < i) 3523 n++; 3524 3525 gcc_assert (n <= 1); 3526 } 3527 } 3528 #endif 3529 3530 3531 /* Functions to work with control flow. */ 3532 3533 /* Recompute BLOCK_TO_BB and BB_FOR_BLOCK for current region so that blocks 3534 are sorted in topological order (it might have been invalidated by 3535 redirecting an edge). */ 3536 static void 3537 sel_recompute_toporder (void) 3538 { 3539 int i, n, rgn; 3540 int *postorder, n_blocks; 3541 3542 postorder = XALLOCAVEC (int, n_basic_blocks); 3543 n_blocks = post_order_compute (postorder, false, false); 3544 3545 rgn = CONTAINING_RGN (BB_TO_BLOCK (0)); 3546 for (n = 0, i = n_blocks - 1; i >= 0; i--) 3547 if (CONTAINING_RGN (postorder[i]) == rgn) 3548 { 3549 BLOCK_TO_BB (postorder[i]) = n; 3550 BB_TO_BLOCK (n) = postorder[i]; 3551 n++; 3552 } 3553 3554 /* Assert that we updated info for all blocks. We may miss some blocks if 3555 this function is called when redirecting an edge made a block 3556 unreachable, but that block is not deleted yet. */ 3557 gcc_assert (n == RGN_NR_BLOCKS (rgn)); 3558 } 3559 3560 /* Tidy the possibly empty block BB. */ 3561 static bool 3562 maybe_tidy_empty_bb (basic_block bb) 3563 { 3564 basic_block succ_bb, pred_bb; 3565 VEC (basic_block, heap) *dom_bbs; 3566 edge e; 3567 edge_iterator ei; 3568 bool rescan_p; 3569 3570 /* Keep empty bb only if this block immediately precedes EXIT and 3571 has incoming non-fallthrough edge, or it has no predecessors or 3572 successors. Otherwise remove it. */ 3573 if (!sel_bb_empty_p (bb) 3574 || (single_succ_p (bb) 3575 && single_succ (bb) == EXIT_BLOCK_PTR 3576 && (!single_pred_p (bb) 3577 || !(single_pred_edge (bb)->flags & EDGE_FALLTHRU))) 3578 || EDGE_COUNT (bb->preds) == 0 3579 || EDGE_COUNT (bb->succs) == 0) 3580 return false; 3581 3582 /* Do not attempt to redirect complex edges. */ 3583 FOR_EACH_EDGE (e, ei, bb->preds) 3584 if (e->flags & EDGE_COMPLEX) 3585 return false; 3586 3587 free_data_sets (bb); 3588 3589 /* Do not delete BB if it has more than one successor. 3590 That can occur when we moving a jump. */ 3591 if (!single_succ_p (bb)) 3592 { 3593 gcc_assert (can_merge_blocks_p (bb->prev_bb, bb)); 3594 sel_merge_blocks (bb->prev_bb, bb); 3595 return true; 3596 } 3597 3598 succ_bb = single_succ (bb); 3599 rescan_p = true; 3600 pred_bb = NULL; 3601 dom_bbs = NULL; 3602 3603 /* Redirect all non-fallthru edges to the next bb. */ 3604 while (rescan_p) 3605 { 3606 rescan_p = false; 3607 3608 FOR_EACH_EDGE (e, ei, bb->preds) 3609 { 3610 pred_bb = e->src; 3611 3612 if (!(e->flags & EDGE_FALLTHRU)) 3613 { 3614 /* We can not invalidate computed topological order by moving 3615 the edge destination block (E->SUCC) along a fallthru edge. 3616 3617 We will update dominators here only when we'll get 3618 an unreachable block when redirecting, otherwise 3619 sel_redirect_edge_and_branch will take care of it. */ 3620 if (e->dest != bb 3621 && single_pred_p (e->dest)) 3622 VEC_safe_push (basic_block, heap, dom_bbs, e->dest); 3623 sel_redirect_edge_and_branch (e, succ_bb); 3624 rescan_p = true; 3625 break; 3626 } 3627 /* If the edge is fallthru, but PRED_BB ends in a conditional jump 3628 to BB (so there is no non-fallthru edge from PRED_BB to BB), we 3629 still have to adjust it. */ 3630 else if (single_succ_p (pred_bb) && any_condjump_p (BB_END (pred_bb))) 3631 { 3632 /* If possible, try to remove the unneeded conditional jump. */ 3633 if (INSN_SCHED_TIMES (BB_END (pred_bb)) == 0 3634 && !IN_CURRENT_FENCE_P (BB_END (pred_bb))) 3635 { 3636 if (!sel_remove_insn (BB_END (pred_bb), false, false)) 3637 tidy_fallthru_edge (e); 3638 } 3639 else 3640 sel_redirect_edge_and_branch (e, succ_bb); 3641 rescan_p = true; 3642 break; 3643 } 3644 } 3645 } 3646 3647 if (can_merge_blocks_p (bb->prev_bb, bb)) 3648 sel_merge_blocks (bb->prev_bb, bb); 3649 else 3650 { 3651 /* This is a block without fallthru predecessor. Just delete it. */ 3652 gcc_assert (pred_bb != NULL); 3653 3654 if (in_current_region_p (pred_bb)) 3655 move_bb_info (pred_bb, bb); 3656 remove_empty_bb (bb, true); 3657 } 3658 3659 if (!VEC_empty (basic_block, dom_bbs)) 3660 { 3661 VEC_safe_push (basic_block, heap, dom_bbs, succ_bb); 3662 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false); 3663 VEC_free (basic_block, heap, dom_bbs); 3664 } 3665 3666 return true; 3667 } 3668 3669 /* Tidy the control flow after we have removed original insn from 3670 XBB. Return true if we have removed some blocks. When FULL_TIDYING 3671 is true, also try to optimize control flow on non-empty blocks. */ 3672 bool 3673 tidy_control_flow (basic_block xbb, bool full_tidying) 3674 { 3675 bool changed = true; 3676 insn_t first, last; 3677 3678 /* First check whether XBB is empty. */ 3679 changed = maybe_tidy_empty_bb (xbb); 3680 if (changed || !full_tidying) 3681 return changed; 3682 3683 /* Check if there is a unnecessary jump after insn left. */ 3684 if (bb_has_removable_jump_to_p (xbb, xbb->next_bb) 3685 && INSN_SCHED_TIMES (BB_END (xbb)) == 0 3686 && !IN_CURRENT_FENCE_P (BB_END (xbb))) 3687 { 3688 if (sel_remove_insn (BB_END (xbb), false, false)) 3689 return true; 3690 tidy_fallthru_edge (EDGE_SUCC (xbb, 0)); 3691 } 3692 3693 first = sel_bb_head (xbb); 3694 last = sel_bb_end (xbb); 3695 if (MAY_HAVE_DEBUG_INSNS) 3696 { 3697 if (first != last && DEBUG_INSN_P (first)) 3698 do 3699 first = NEXT_INSN (first); 3700 while (first != last && (DEBUG_INSN_P (first) || NOTE_P (first))); 3701 3702 if (first != last && DEBUG_INSN_P (last)) 3703 do 3704 last = PREV_INSN (last); 3705 while (first != last && (DEBUG_INSN_P (last) || NOTE_P (last))); 3706 } 3707 /* Check if there is an unnecessary jump in previous basic block leading 3708 to next basic block left after removing INSN from stream. 3709 If it is so, remove that jump and redirect edge to current 3710 basic block (where there was INSN before deletion). This way 3711 when NOP will be deleted several instructions later with its 3712 basic block we will not get a jump to next instruction, which 3713 can be harmful. */ 3714 if (first == last 3715 && !sel_bb_empty_p (xbb) 3716 && INSN_NOP_P (last) 3717 /* Flow goes fallthru from current block to the next. */ 3718 && EDGE_COUNT (xbb->succs) == 1 3719 && (EDGE_SUCC (xbb, 0)->flags & EDGE_FALLTHRU) 3720 /* When successor is an EXIT block, it may not be the next block. */ 3721 && single_succ (xbb) != EXIT_BLOCK_PTR 3722 /* And unconditional jump in previous basic block leads to 3723 next basic block of XBB and this jump can be safely removed. */ 3724 && in_current_region_p (xbb->prev_bb) 3725 && bb_has_removable_jump_to_p (xbb->prev_bb, xbb->next_bb) 3726 && INSN_SCHED_TIMES (BB_END (xbb->prev_bb)) == 0 3727 /* Also this jump is not at the scheduling boundary. */ 3728 && !IN_CURRENT_FENCE_P (BB_END (xbb->prev_bb))) 3729 { 3730 bool recompute_toporder_p; 3731 /* Clear data structures of jump - jump itself will be removed 3732 by sel_redirect_edge_and_branch. */ 3733 clear_expr (INSN_EXPR (BB_END (xbb->prev_bb))); 3734 recompute_toporder_p 3735 = sel_redirect_edge_and_branch (EDGE_SUCC (xbb->prev_bb, 0), xbb); 3736 3737 gcc_assert (EDGE_SUCC (xbb->prev_bb, 0)->flags & EDGE_FALLTHRU); 3738 3739 /* It can turn out that after removing unused jump, basic block 3740 that contained that jump, becomes empty too. In such case 3741 remove it too. */ 3742 if (sel_bb_empty_p (xbb->prev_bb)) 3743 changed = maybe_tidy_empty_bb (xbb->prev_bb); 3744 if (recompute_toporder_p) 3745 sel_recompute_toporder (); 3746 } 3747 3748 #ifdef ENABLE_CHECKING 3749 verify_backedges (); 3750 verify_dominators (CDI_DOMINATORS); 3751 #endif 3752 3753 return changed; 3754 } 3755 3756 /* Purge meaningless empty blocks in the middle of a region. */ 3757 void 3758 purge_empty_blocks (void) 3759 { 3760 int i; 3761 3762 /* Do not attempt to delete the first basic block in the region. */ 3763 for (i = 1; i < current_nr_blocks; ) 3764 { 3765 basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i)); 3766 3767 if (maybe_tidy_empty_bb (b)) 3768 continue; 3769 3770 i++; 3771 } 3772 } 3773 3774 /* Rip-off INSN from the insn stream. When ONLY_DISCONNECT is true, 3775 do not delete insn's data, because it will be later re-emitted. 3776 Return true if we have removed some blocks afterwards. */ 3777 bool 3778 sel_remove_insn (insn_t insn, bool only_disconnect, bool full_tidying) 3779 { 3780 basic_block bb = BLOCK_FOR_INSN (insn); 3781 3782 gcc_assert (INSN_IN_STREAM_P (insn)); 3783 3784 if (DEBUG_INSN_P (insn) && BB_AV_SET_VALID_P (bb)) 3785 { 3786 expr_t expr; 3787 av_set_iterator i; 3788 3789 /* When we remove a debug insn that is head of a BB, it remains 3790 in the AV_SET of the block, but it shouldn't. */ 3791 FOR_EACH_EXPR_1 (expr, i, &BB_AV_SET (bb)) 3792 if (EXPR_INSN_RTX (expr) == insn) 3793 { 3794 av_set_iter_remove (&i); 3795 break; 3796 } 3797 } 3798 3799 if (only_disconnect) 3800 { 3801 insn_t prev = PREV_INSN (insn); 3802 insn_t next = NEXT_INSN (insn); 3803 basic_block bb = BLOCK_FOR_INSN (insn); 3804 3805 NEXT_INSN (prev) = next; 3806 PREV_INSN (next) = prev; 3807 3808 if (BB_HEAD (bb) == insn) 3809 { 3810 gcc_assert (BLOCK_FOR_INSN (prev) == bb); 3811 BB_HEAD (bb) = prev; 3812 } 3813 if (BB_END (bb) == insn) 3814 BB_END (bb) = prev; 3815 } 3816 else 3817 { 3818 remove_insn (insn); 3819 clear_expr (INSN_EXPR (insn)); 3820 } 3821 3822 /* It is necessary to null this fields before calling add_insn (). */ 3823 PREV_INSN (insn) = NULL_RTX; 3824 NEXT_INSN (insn) = NULL_RTX; 3825 3826 return tidy_control_flow (bb, full_tidying); 3827 } 3828 3829 /* Estimate number of the insns in BB. */ 3830 static int 3831 sel_estimate_number_of_insns (basic_block bb) 3832 { 3833 int res = 0; 3834 insn_t insn = NEXT_INSN (BB_HEAD (bb)), next_tail = NEXT_INSN (BB_END (bb)); 3835 3836 for (; insn != next_tail; insn = NEXT_INSN (insn)) 3837 if (NONDEBUG_INSN_P (insn)) 3838 res++; 3839 3840 return res; 3841 } 3842 3843 /* We don't need separate luids for notes or labels. */ 3844 static int 3845 sel_luid_for_non_insn (rtx x) 3846 { 3847 gcc_assert (NOTE_P (x) || LABEL_P (x)); 3848 3849 return -1; 3850 } 3851 3852 /* Return seqno of the only predecessor of INSN. */ 3853 static int 3854 get_seqno_of_a_pred (insn_t insn) 3855 { 3856 int seqno; 3857 3858 gcc_assert (INSN_SIMPLEJUMP_P (insn)); 3859 3860 if (!sel_bb_head_p (insn)) 3861 seqno = INSN_SEQNO (PREV_INSN (insn)); 3862 else 3863 { 3864 basic_block bb = BLOCK_FOR_INSN (insn); 3865 3866 if (single_pred_p (bb) 3867 && !in_current_region_p (single_pred (bb))) 3868 { 3869 /* We can have preds outside a region when splitting edges 3870 for pipelining of an outer loop. Use succ instead. 3871 There should be only one of them. */ 3872 insn_t succ = NULL; 3873 succ_iterator si; 3874 bool first = true; 3875 3876 gcc_assert (flag_sel_sched_pipelining_outer_loops 3877 && current_loop_nest); 3878 FOR_EACH_SUCC_1 (succ, si, insn, 3879 SUCCS_NORMAL | SUCCS_SKIP_TO_LOOP_EXITS) 3880 { 3881 gcc_assert (first); 3882 first = false; 3883 } 3884 3885 gcc_assert (succ != NULL); 3886 seqno = INSN_SEQNO (succ); 3887 } 3888 else 3889 { 3890 insn_t *preds; 3891 int n; 3892 3893 cfg_preds (BLOCK_FOR_INSN (insn), &preds, &n); 3894 gcc_assert (n == 1); 3895 3896 seqno = INSN_SEQNO (preds[0]); 3897 3898 free (preds); 3899 } 3900 } 3901 3902 return seqno; 3903 } 3904 3905 /* Find the proper seqno for inserting at INSN. Returns -1 if no predecessors 3906 with positive seqno exist. */ 3907 int 3908 get_seqno_by_preds (rtx insn) 3909 { 3910 basic_block bb = BLOCK_FOR_INSN (insn); 3911 rtx tmp = insn, head = BB_HEAD (bb); 3912 insn_t *preds; 3913 int n, i, seqno; 3914 3915 while (tmp != head) 3916 if (INSN_P (tmp)) 3917 return INSN_SEQNO (tmp); 3918 else 3919 tmp = PREV_INSN (tmp); 3920 3921 cfg_preds (bb, &preds, &n); 3922 for (i = 0, seqno = -1; i < n; i++) 3923 seqno = MAX (seqno, INSN_SEQNO (preds[i])); 3924 3925 return seqno; 3926 } 3927 3928 3929 3930 /* Extend pass-scope data structures for basic blocks. */ 3931 void 3932 sel_extend_global_bb_info (void) 3933 { 3934 VEC_safe_grow_cleared (sel_global_bb_info_def, heap, sel_global_bb_info, 3935 last_basic_block); 3936 } 3937 3938 /* Extend region-scope data structures for basic blocks. */ 3939 static void 3940 extend_region_bb_info (void) 3941 { 3942 VEC_safe_grow_cleared (sel_region_bb_info_def, heap, sel_region_bb_info, 3943 last_basic_block); 3944 } 3945 3946 /* Extend all data structures to fit for all basic blocks. */ 3947 static void 3948 extend_bb_info (void) 3949 { 3950 sel_extend_global_bb_info (); 3951 extend_region_bb_info (); 3952 } 3953 3954 /* Finalize pass-scope data structures for basic blocks. */ 3955 void 3956 sel_finish_global_bb_info (void) 3957 { 3958 VEC_free (sel_global_bb_info_def, heap, sel_global_bb_info); 3959 } 3960 3961 /* Finalize region-scope data structures for basic blocks. */ 3962 static void 3963 finish_region_bb_info (void) 3964 { 3965 VEC_free (sel_region_bb_info_def, heap, sel_region_bb_info); 3966 } 3967 3968 3969 /* Data for each insn in current region. */ 3970 VEC (sel_insn_data_def, heap) *s_i_d = NULL; 3971 3972 /* A vector for the insns we've emitted. */ 3973 static insn_vec_t new_insns = NULL; 3974 3975 /* Extend data structures for insns from current region. */ 3976 static void 3977 extend_insn_data (void) 3978 { 3979 int reserve; 3980 3981 sched_extend_target (); 3982 sched_deps_init (false); 3983 3984 /* Extend data structures for insns from current region. */ 3985 reserve = (sched_max_luid + 1 3986 - VEC_length (sel_insn_data_def, s_i_d)); 3987 if (reserve > 0 3988 && ! VEC_space (sel_insn_data_def, s_i_d, reserve)) 3989 { 3990 int size; 3991 3992 if (sched_max_luid / 2 > 1024) 3993 size = sched_max_luid + 1024; 3994 else 3995 size = 3 * sched_max_luid / 2; 3996 3997 3998 VEC_safe_grow_cleared (sel_insn_data_def, heap, s_i_d, size); 3999 } 4000 } 4001 4002 /* Finalize data structures for insns from current region. */ 4003 static void 4004 finish_insns (void) 4005 { 4006 unsigned i; 4007 4008 /* Clear here all dependence contexts that may have left from insns that were 4009 removed during the scheduling. */ 4010 for (i = 0; i < VEC_length (sel_insn_data_def, s_i_d); i++) 4011 { 4012 sel_insn_data_def *sid_entry = VEC_index (sel_insn_data_def, s_i_d, i); 4013 4014 if (sid_entry->live) 4015 return_regset_to_pool (sid_entry->live); 4016 if (sid_entry->analyzed_deps) 4017 { 4018 BITMAP_FREE (sid_entry->analyzed_deps); 4019 BITMAP_FREE (sid_entry->found_deps); 4020 htab_delete (sid_entry->transformed_insns); 4021 free_deps (&sid_entry->deps_context); 4022 } 4023 if (EXPR_VINSN (&sid_entry->expr)) 4024 { 4025 clear_expr (&sid_entry->expr); 4026 4027 /* Also, clear CANT_MOVE bit here, because we really don't want it 4028 to be passed to the next region. */ 4029 CANT_MOVE_BY_LUID (i) = 0; 4030 } 4031 } 4032 4033 VEC_free (sel_insn_data_def, heap, s_i_d); 4034 } 4035 4036 /* A proxy to pass initialization data to init_insn (). */ 4037 static sel_insn_data_def _insn_init_ssid; 4038 static sel_insn_data_t insn_init_ssid = &_insn_init_ssid; 4039 4040 /* If true create a new vinsn. Otherwise use the one from EXPR. */ 4041 static bool insn_init_create_new_vinsn_p; 4042 4043 /* Set all necessary data for initialization of the new insn[s]. */ 4044 static expr_t 4045 set_insn_init (expr_t expr, vinsn_t vi, int seqno) 4046 { 4047 expr_t x = &insn_init_ssid->expr; 4048 4049 copy_expr_onside (x, expr); 4050 if (vi != NULL) 4051 { 4052 insn_init_create_new_vinsn_p = false; 4053 change_vinsn_in_expr (x, vi); 4054 } 4055 else 4056 insn_init_create_new_vinsn_p = true; 4057 4058 insn_init_ssid->seqno = seqno; 4059 return x; 4060 } 4061 4062 /* Init data for INSN. */ 4063 static void 4064 init_insn_data (insn_t insn) 4065 { 4066 expr_t expr; 4067 sel_insn_data_t ssid = insn_init_ssid; 4068 4069 /* The fields mentioned below are special and hence are not being 4070 propagated to the new insns. */ 4071 gcc_assert (!ssid->asm_p && ssid->sched_next == NULL 4072 && !ssid->after_stall_p && ssid->sched_cycle == 0); 4073 gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0); 4074 4075 expr = INSN_EXPR (insn); 4076 copy_expr (expr, &ssid->expr); 4077 prepare_insn_expr (insn, ssid->seqno); 4078 4079 if (insn_init_create_new_vinsn_p) 4080 change_vinsn_in_expr (expr, vinsn_create (insn, init_insn_force_unique_p)); 4081 4082 if (first_time_insn_init (insn)) 4083 init_first_time_insn_data (insn); 4084 } 4085 4086 /* This is used to initialize spurious jumps generated by 4087 sel_redirect_edge (). */ 4088 static void 4089 init_simplejump_data (insn_t insn) 4090 { 4091 init_expr (INSN_EXPR (insn), vinsn_create (insn, false), 0, 4092 REG_BR_PROB_BASE, 0, 0, 0, 0, 0, 0, NULL, true, false, false, 4093 false, true); 4094 INSN_SEQNO (insn) = get_seqno_of_a_pred (insn); 4095 init_first_time_insn_data (insn); 4096 } 4097 4098 /* Perform deferred initialization of insns. This is used to process 4099 a new jump that may be created by redirect_edge. */ 4100 void 4101 sel_init_new_insn (insn_t insn, int flags) 4102 { 4103 /* We create data structures for bb when the first insn is emitted in it. */ 4104 if (INSN_P (insn) 4105 && INSN_IN_STREAM_P (insn) 4106 && insn_is_the_only_one_in_bb_p (insn)) 4107 { 4108 extend_bb_info (); 4109 create_initial_data_sets (BLOCK_FOR_INSN (insn)); 4110 } 4111 4112 if (flags & INSN_INIT_TODO_LUID) 4113 sched_init_luids (NULL, NULL, NULL, insn); 4114 4115 if (flags & INSN_INIT_TODO_SSID) 4116 { 4117 extend_insn_data (); 4118 init_insn_data (insn); 4119 clear_expr (&insn_init_ssid->expr); 4120 } 4121 4122 if (flags & INSN_INIT_TODO_SIMPLEJUMP) 4123 { 4124 extend_insn_data (); 4125 init_simplejump_data (insn); 4126 } 4127 4128 gcc_assert (CONTAINING_RGN (BLOCK_NUM (insn)) 4129 == CONTAINING_RGN (BB_TO_BLOCK (0))); 4130 } 4131 4132 4133 /* Functions to init/finish work with lv sets. */ 4134 4135 /* Init BB_LV_SET of BB from DF_LR_IN set of BB. */ 4136 static void 4137 init_lv_set (basic_block bb) 4138 { 4139 gcc_assert (!BB_LV_SET_VALID_P (bb)); 4140 4141 BB_LV_SET (bb) = get_regset_from_pool (); 4142 COPY_REG_SET (BB_LV_SET (bb), DF_LR_IN (bb)); 4143 BB_LV_SET_VALID_P (bb) = true; 4144 } 4145 4146 /* Copy liveness information to BB from FROM_BB. */ 4147 static void 4148 copy_lv_set_from (basic_block bb, basic_block from_bb) 4149 { 4150 gcc_assert (!BB_LV_SET_VALID_P (bb)); 4151 4152 COPY_REG_SET (BB_LV_SET (bb), BB_LV_SET (from_bb)); 4153 BB_LV_SET_VALID_P (bb) = true; 4154 } 4155 4156 /* Initialize lv set of all bb headers. */ 4157 void 4158 init_lv_sets (void) 4159 { 4160 basic_block bb; 4161 4162 /* Initialize of LV sets. */ 4163 FOR_EACH_BB (bb) 4164 init_lv_set (bb); 4165 4166 /* Don't forget EXIT_BLOCK. */ 4167 init_lv_set (EXIT_BLOCK_PTR); 4168 } 4169 4170 /* Release lv set of HEAD. */ 4171 static void 4172 free_lv_set (basic_block bb) 4173 { 4174 gcc_assert (BB_LV_SET (bb) != NULL); 4175 4176 return_regset_to_pool (BB_LV_SET (bb)); 4177 BB_LV_SET (bb) = NULL; 4178 BB_LV_SET_VALID_P (bb) = false; 4179 } 4180 4181 /* Finalize lv sets of all bb headers. */ 4182 void 4183 free_lv_sets (void) 4184 { 4185 basic_block bb; 4186 4187 /* Don't forget EXIT_BLOCK. */ 4188 free_lv_set (EXIT_BLOCK_PTR); 4189 4190 /* Free LV sets. */ 4191 FOR_EACH_BB (bb) 4192 if (BB_LV_SET (bb)) 4193 free_lv_set (bb); 4194 } 4195 4196 /* Initialize an invalid AV_SET for BB. 4197 This set will be updated next time compute_av () process BB. */ 4198 static void 4199 invalidate_av_set (basic_block bb) 4200 { 4201 gcc_assert (BB_AV_LEVEL (bb) <= 0 4202 && BB_AV_SET (bb) == NULL); 4203 4204 BB_AV_LEVEL (bb) = -1; 4205 } 4206 4207 /* Create initial data sets for BB (they will be invalid). */ 4208 static void 4209 create_initial_data_sets (basic_block bb) 4210 { 4211 if (BB_LV_SET (bb)) 4212 BB_LV_SET_VALID_P (bb) = false; 4213 else 4214 BB_LV_SET (bb) = get_regset_from_pool (); 4215 invalidate_av_set (bb); 4216 } 4217 4218 /* Free av set of BB. */ 4219 static void 4220 free_av_set (basic_block bb) 4221 { 4222 av_set_clear (&BB_AV_SET (bb)); 4223 BB_AV_LEVEL (bb) = 0; 4224 } 4225 4226 /* Free data sets of BB. */ 4227 void 4228 free_data_sets (basic_block bb) 4229 { 4230 free_lv_set (bb); 4231 free_av_set (bb); 4232 } 4233 4234 /* Exchange lv sets of TO and FROM. */ 4235 static void 4236 exchange_lv_sets (basic_block to, basic_block from) 4237 { 4238 { 4239 regset to_lv_set = BB_LV_SET (to); 4240 4241 BB_LV_SET (to) = BB_LV_SET (from); 4242 BB_LV_SET (from) = to_lv_set; 4243 } 4244 4245 { 4246 bool to_lv_set_valid_p = BB_LV_SET_VALID_P (to); 4247 4248 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from); 4249 BB_LV_SET_VALID_P (from) = to_lv_set_valid_p; 4250 } 4251 } 4252 4253 4254 /* Exchange av sets of TO and FROM. */ 4255 static void 4256 exchange_av_sets (basic_block to, basic_block from) 4257 { 4258 { 4259 av_set_t to_av_set = BB_AV_SET (to); 4260 4261 BB_AV_SET (to) = BB_AV_SET (from); 4262 BB_AV_SET (from) = to_av_set; 4263 } 4264 4265 { 4266 int to_av_level = BB_AV_LEVEL (to); 4267 4268 BB_AV_LEVEL (to) = BB_AV_LEVEL (from); 4269 BB_AV_LEVEL (from) = to_av_level; 4270 } 4271 } 4272 4273 /* Exchange data sets of TO and FROM. */ 4274 void 4275 exchange_data_sets (basic_block to, basic_block from) 4276 { 4277 exchange_lv_sets (to, from); 4278 exchange_av_sets (to, from); 4279 } 4280 4281 /* Copy data sets of FROM to TO. */ 4282 void 4283 copy_data_sets (basic_block to, basic_block from) 4284 { 4285 gcc_assert (!BB_LV_SET_VALID_P (to) && !BB_AV_SET_VALID_P (to)); 4286 gcc_assert (BB_AV_SET (to) == NULL); 4287 4288 BB_AV_LEVEL (to) = BB_AV_LEVEL (from); 4289 BB_LV_SET_VALID_P (to) = BB_LV_SET_VALID_P (from); 4290 4291 if (BB_AV_SET_VALID_P (from)) 4292 { 4293 BB_AV_SET (to) = av_set_copy (BB_AV_SET (from)); 4294 } 4295 if (BB_LV_SET_VALID_P (from)) 4296 { 4297 gcc_assert (BB_LV_SET (to) != NULL); 4298 COPY_REG_SET (BB_LV_SET (to), BB_LV_SET (from)); 4299 } 4300 } 4301 4302 /* Return an av set for INSN, if any. */ 4303 av_set_t 4304 get_av_set (insn_t insn) 4305 { 4306 av_set_t av_set; 4307 4308 gcc_assert (AV_SET_VALID_P (insn)); 4309 4310 if (sel_bb_head_p (insn)) 4311 av_set = BB_AV_SET (BLOCK_FOR_INSN (insn)); 4312 else 4313 av_set = NULL; 4314 4315 return av_set; 4316 } 4317 4318 /* Implementation of AV_LEVEL () macro. Return AV_LEVEL () of INSN. */ 4319 int 4320 get_av_level (insn_t insn) 4321 { 4322 int av_level; 4323 4324 gcc_assert (INSN_P (insn)); 4325 4326 if (sel_bb_head_p (insn)) 4327 av_level = BB_AV_LEVEL (BLOCK_FOR_INSN (insn)); 4328 else 4329 av_level = INSN_WS_LEVEL (insn); 4330 4331 return av_level; 4332 } 4333 4334 4335 4336 /* Variables to work with control-flow graph. */ 4337 4338 /* The basic block that already has been processed by the sched_data_update (), 4339 but hasn't been in sel_add_bb () yet. */ 4340 static VEC (basic_block, heap) *last_added_blocks = NULL; 4341 4342 /* A pool for allocating successor infos. */ 4343 static struct 4344 { 4345 /* A stack for saving succs_info structures. */ 4346 struct succs_info *stack; 4347 4348 /* Its size. */ 4349 int size; 4350 4351 /* Top of the stack. */ 4352 int top; 4353 4354 /* Maximal value of the top. */ 4355 int max_top; 4356 } succs_info_pool; 4357 4358 /* Functions to work with control-flow graph. */ 4359 4360 /* Return basic block note of BB. */ 4361 insn_t 4362 sel_bb_head (basic_block bb) 4363 { 4364 insn_t head; 4365 4366 if (bb == EXIT_BLOCK_PTR) 4367 { 4368 gcc_assert (exit_insn != NULL_RTX); 4369 head = exit_insn; 4370 } 4371 else 4372 { 4373 insn_t note; 4374 4375 note = bb_note (bb); 4376 head = next_nonnote_insn (note); 4377 4378 if (head && (BARRIER_P (head) || BLOCK_FOR_INSN (head) != bb)) 4379 head = NULL_RTX; 4380 } 4381 4382 return head; 4383 } 4384 4385 /* Return true if INSN is a basic block header. */ 4386 bool 4387 sel_bb_head_p (insn_t insn) 4388 { 4389 return sel_bb_head (BLOCK_FOR_INSN (insn)) == insn; 4390 } 4391 4392 /* Return last insn of BB. */ 4393 insn_t 4394 sel_bb_end (basic_block bb) 4395 { 4396 if (sel_bb_empty_p (bb)) 4397 return NULL_RTX; 4398 4399 gcc_assert (bb != EXIT_BLOCK_PTR); 4400 4401 return BB_END (bb); 4402 } 4403 4404 /* Return true if INSN is the last insn in its basic block. */ 4405 bool 4406 sel_bb_end_p (insn_t insn) 4407 { 4408 return insn == sel_bb_end (BLOCK_FOR_INSN (insn)); 4409 } 4410 4411 /* Return true if BB consist of single NOTE_INSN_BASIC_BLOCK. */ 4412 bool 4413 sel_bb_empty_p (basic_block bb) 4414 { 4415 return sel_bb_head (bb) == NULL; 4416 } 4417 4418 /* True when BB belongs to the current scheduling region. */ 4419 bool 4420 in_current_region_p (basic_block bb) 4421 { 4422 if (bb->index < NUM_FIXED_BLOCKS) 4423 return false; 4424 4425 return CONTAINING_RGN (bb->index) == CONTAINING_RGN (BB_TO_BLOCK (0)); 4426 } 4427 4428 /* Return the block which is a fallthru bb of a conditional jump JUMP. */ 4429 basic_block 4430 fallthru_bb_of_jump (rtx jump) 4431 { 4432 if (!JUMP_P (jump)) 4433 return NULL; 4434 4435 if (!any_condjump_p (jump)) 4436 return NULL; 4437 4438 /* A basic block that ends with a conditional jump may still have one successor 4439 (and be followed by a barrier), we are not interested. */ 4440 if (single_succ_p (BLOCK_FOR_INSN (jump))) 4441 return NULL; 4442 4443 return FALLTHRU_EDGE (BLOCK_FOR_INSN (jump))->dest; 4444 } 4445 4446 /* Remove all notes from BB. */ 4447 static void 4448 init_bb (basic_block bb) 4449 { 4450 remove_notes (bb_note (bb), BB_END (bb)); 4451 BB_NOTE_LIST (bb) = note_list; 4452 } 4453 4454 void 4455 sel_init_bbs (bb_vec_t bbs, basic_block bb) 4456 { 4457 const struct sched_scan_info_def ssi = 4458 { 4459 extend_bb_info, /* extend_bb */ 4460 init_bb, /* init_bb */ 4461 NULL, /* extend_insn */ 4462 NULL /* init_insn */ 4463 }; 4464 4465 sched_scan (&ssi, bbs, bb, new_insns, NULL); 4466 } 4467 4468 /* Restore notes for the whole region. */ 4469 static void 4470 sel_restore_notes (void) 4471 { 4472 int bb; 4473 insn_t insn; 4474 4475 for (bb = 0; bb < current_nr_blocks; bb++) 4476 { 4477 basic_block first, last; 4478 4479 first = EBB_FIRST_BB (bb); 4480 last = EBB_LAST_BB (bb)->next_bb; 4481 4482 do 4483 { 4484 note_list = BB_NOTE_LIST (first); 4485 restore_other_notes (NULL, first); 4486 BB_NOTE_LIST (first) = NULL_RTX; 4487 4488 FOR_BB_INSNS (first, insn) 4489 if (NONDEBUG_INSN_P (insn)) 4490 reemit_notes (insn); 4491 4492 first = first->next_bb; 4493 } 4494 while (first != last); 4495 } 4496 } 4497 4498 /* Free per-bb data structures. */ 4499 void 4500 sel_finish_bbs (void) 4501 { 4502 sel_restore_notes (); 4503 4504 /* Remove current loop preheader from this loop. */ 4505 if (current_loop_nest) 4506 sel_remove_loop_preheader (); 4507 4508 finish_region_bb_info (); 4509 } 4510 4511 /* Return true if INSN has a single successor of type FLAGS. */ 4512 bool 4513 sel_insn_has_single_succ_p (insn_t insn, int flags) 4514 { 4515 insn_t succ; 4516 succ_iterator si; 4517 bool first_p = true; 4518 4519 FOR_EACH_SUCC_1 (succ, si, insn, flags) 4520 { 4521 if (first_p) 4522 first_p = false; 4523 else 4524 return false; 4525 } 4526 4527 return true; 4528 } 4529 4530 /* Allocate successor's info. */ 4531 static struct succs_info * 4532 alloc_succs_info (void) 4533 { 4534 if (succs_info_pool.top == succs_info_pool.max_top) 4535 { 4536 int i; 4537 4538 if (++succs_info_pool.max_top >= succs_info_pool.size) 4539 gcc_unreachable (); 4540 4541 i = ++succs_info_pool.top; 4542 succs_info_pool.stack[i].succs_ok = VEC_alloc (rtx, heap, 10); 4543 succs_info_pool.stack[i].succs_other = VEC_alloc (rtx, heap, 10); 4544 succs_info_pool.stack[i].probs_ok = VEC_alloc (int, heap, 10); 4545 } 4546 else 4547 succs_info_pool.top++; 4548 4549 return &succs_info_pool.stack[succs_info_pool.top]; 4550 } 4551 4552 /* Free successor's info. */ 4553 void 4554 free_succs_info (struct succs_info * sinfo) 4555 { 4556 gcc_assert (succs_info_pool.top >= 0 4557 && &succs_info_pool.stack[succs_info_pool.top] == sinfo); 4558 succs_info_pool.top--; 4559 4560 /* Clear stale info. */ 4561 VEC_block_remove (rtx, sinfo->succs_ok, 4562 0, VEC_length (rtx, sinfo->succs_ok)); 4563 VEC_block_remove (rtx, sinfo->succs_other, 4564 0, VEC_length (rtx, sinfo->succs_other)); 4565 VEC_block_remove (int, sinfo->probs_ok, 4566 0, VEC_length (int, sinfo->probs_ok)); 4567 sinfo->all_prob = 0; 4568 sinfo->succs_ok_n = 0; 4569 sinfo->all_succs_n = 0; 4570 } 4571 4572 /* Compute successor info for INSN. FLAGS are the flags passed 4573 to the FOR_EACH_SUCC_1 iterator. */ 4574 struct succs_info * 4575 compute_succs_info (insn_t insn, short flags) 4576 { 4577 succ_iterator si; 4578 insn_t succ; 4579 struct succs_info *sinfo = alloc_succs_info (); 4580 4581 /* Traverse *all* successors and decide what to do with each. */ 4582 FOR_EACH_SUCC_1 (succ, si, insn, SUCCS_ALL) 4583 { 4584 /* FIXME: this doesn't work for skipping to loop exits, as we don't 4585 perform code motion through inner loops. */ 4586 short current_flags = si.current_flags & ~SUCCS_SKIP_TO_LOOP_EXITS; 4587 4588 if (current_flags & flags) 4589 { 4590 VEC_safe_push (rtx, heap, sinfo->succs_ok, succ); 4591 VEC_safe_push (int, heap, sinfo->probs_ok, 4592 /* FIXME: Improve calculation when skipping 4593 inner loop to exits. */ 4594 (si.bb_end 4595 ? si.e1->probability 4596 : REG_BR_PROB_BASE)); 4597 sinfo->succs_ok_n++; 4598 } 4599 else 4600 VEC_safe_push (rtx, heap, sinfo->succs_other, succ); 4601 4602 /* Compute all_prob. */ 4603 if (!si.bb_end) 4604 sinfo->all_prob = REG_BR_PROB_BASE; 4605 else 4606 sinfo->all_prob += si.e1->probability; 4607 4608 sinfo->all_succs_n++; 4609 } 4610 4611 return sinfo; 4612 } 4613 4614 /* Return the predecessors of BB in PREDS and their number in N. 4615 Empty blocks are skipped. SIZE is used to allocate PREDS. */ 4616 static void 4617 cfg_preds_1 (basic_block bb, insn_t **preds, int *n, int *size) 4618 { 4619 edge e; 4620 edge_iterator ei; 4621 4622 gcc_assert (BLOCK_TO_BB (bb->index) != 0); 4623 4624 FOR_EACH_EDGE (e, ei, bb->preds) 4625 { 4626 basic_block pred_bb = e->src; 4627 insn_t bb_end = BB_END (pred_bb); 4628 4629 if (!in_current_region_p (pred_bb)) 4630 { 4631 gcc_assert (flag_sel_sched_pipelining_outer_loops 4632 && current_loop_nest); 4633 continue; 4634 } 4635 4636 if (sel_bb_empty_p (pred_bb)) 4637 cfg_preds_1 (pred_bb, preds, n, size); 4638 else 4639 { 4640 if (*n == *size) 4641 *preds = XRESIZEVEC (insn_t, *preds, 4642 (*size = 2 * *size + 1)); 4643 (*preds)[(*n)++] = bb_end; 4644 } 4645 } 4646 4647 gcc_assert (*n != 0 4648 || (flag_sel_sched_pipelining_outer_loops 4649 && current_loop_nest)); 4650 } 4651 4652 /* Find all predecessors of BB and record them in PREDS and their number 4653 in N. Empty blocks are skipped, and only normal (forward in-region) 4654 edges are processed. */ 4655 static void 4656 cfg_preds (basic_block bb, insn_t **preds, int *n) 4657 { 4658 int size = 0; 4659 4660 *preds = NULL; 4661 *n = 0; 4662 cfg_preds_1 (bb, preds, n, &size); 4663 } 4664 4665 /* Returns true if we are moving INSN through join point. */ 4666 bool 4667 sel_num_cfg_preds_gt_1 (insn_t insn) 4668 { 4669 basic_block bb; 4670 4671 if (!sel_bb_head_p (insn) || INSN_BB (insn) == 0) 4672 return false; 4673 4674 bb = BLOCK_FOR_INSN (insn); 4675 4676 while (1) 4677 { 4678 if (EDGE_COUNT (bb->preds) > 1) 4679 return true; 4680 4681 gcc_assert (EDGE_PRED (bb, 0)->dest == bb); 4682 bb = EDGE_PRED (bb, 0)->src; 4683 4684 if (!sel_bb_empty_p (bb)) 4685 break; 4686 } 4687 4688 return false; 4689 } 4690 4691 /* Returns true when BB should be the end of an ebb. Adapted from the 4692 code in sched-ebb.c. */ 4693 bool 4694 bb_ends_ebb_p (basic_block bb) 4695 { 4696 basic_block next_bb = bb_next_bb (bb); 4697 edge e; 4698 edge_iterator ei; 4699 4700 if (next_bb == EXIT_BLOCK_PTR 4701 || bitmap_bit_p (forced_ebb_heads, next_bb->index) 4702 || (LABEL_P (BB_HEAD (next_bb)) 4703 /* NB: LABEL_NUSES () is not maintained outside of jump.c. 4704 Work around that. */ 4705 && !single_pred_p (next_bb))) 4706 return true; 4707 4708 if (!in_current_region_p (next_bb)) 4709 return true; 4710 4711 FOR_EACH_EDGE (e, ei, bb->succs) 4712 if ((e->flags & EDGE_FALLTHRU) != 0) 4713 { 4714 gcc_assert (e->dest == next_bb); 4715 4716 return false; 4717 } 4718 4719 return true; 4720 } 4721 4722 /* Returns true when INSN and SUCC are in the same EBB, given that SUCC is a 4723 successor of INSN. */ 4724 bool 4725 in_same_ebb_p (insn_t insn, insn_t succ) 4726 { 4727 basic_block ptr = BLOCK_FOR_INSN (insn); 4728 4729 for(;;) 4730 { 4731 if (ptr == BLOCK_FOR_INSN (succ)) 4732 return true; 4733 4734 if (bb_ends_ebb_p (ptr)) 4735 return false; 4736 4737 ptr = bb_next_bb (ptr); 4738 } 4739 4740 gcc_unreachable (); 4741 return false; 4742 } 4743 4744 /* Recomputes the reverse topological order for the function and 4745 saves it in REV_TOP_ORDER_INDEX. REV_TOP_ORDER_INDEX_LEN is also 4746 modified appropriately. */ 4747 static void 4748 recompute_rev_top_order (void) 4749 { 4750 int *postorder; 4751 int n_blocks, i; 4752 4753 if (!rev_top_order_index || rev_top_order_index_len < last_basic_block) 4754 { 4755 rev_top_order_index_len = last_basic_block; 4756 rev_top_order_index = XRESIZEVEC (int, rev_top_order_index, 4757 rev_top_order_index_len); 4758 } 4759 4760 postorder = XNEWVEC (int, n_basic_blocks); 4761 4762 n_blocks = post_order_compute (postorder, true, false); 4763 gcc_assert (n_basic_blocks == n_blocks); 4764 4765 /* Build reverse function: for each basic block with BB->INDEX == K 4766 rev_top_order_index[K] is it's reverse topological sort number. */ 4767 for (i = 0; i < n_blocks; i++) 4768 { 4769 gcc_assert (postorder[i] < rev_top_order_index_len); 4770 rev_top_order_index[postorder[i]] = i; 4771 } 4772 4773 free (postorder); 4774 } 4775 4776 /* Clear all flags from insns in BB that could spoil its rescheduling. */ 4777 void 4778 clear_outdated_rtx_info (basic_block bb) 4779 { 4780 rtx insn; 4781 4782 FOR_BB_INSNS (bb, insn) 4783 if (INSN_P (insn)) 4784 { 4785 SCHED_GROUP_P (insn) = 0; 4786 INSN_AFTER_STALL_P (insn) = 0; 4787 INSN_SCHED_TIMES (insn) = 0; 4788 EXPR_PRIORITY_ADJ (INSN_EXPR (insn)) = 0; 4789 4790 /* We cannot use the changed caches, as previously we could ignore 4791 the LHS dependence due to enabled renaming and transform 4792 the expression, and currently we'll be unable to do this. */ 4793 htab_empty (INSN_TRANSFORMED_INSNS (insn)); 4794 } 4795 } 4796 4797 /* Add BB_NOTE to the pool of available basic block notes. */ 4798 static void 4799 return_bb_to_pool (basic_block bb) 4800 { 4801 rtx note = bb_note (bb); 4802 4803 gcc_assert (NOTE_BASIC_BLOCK (note) == bb 4804 && bb->aux == NULL); 4805 4806 /* It turns out that current cfg infrastructure does not support 4807 reuse of basic blocks. Don't bother for now. */ 4808 /*VEC_safe_push (rtx, heap, bb_note_pool, note);*/ 4809 } 4810 4811 /* Get a bb_note from pool or return NULL_RTX if pool is empty. */ 4812 static rtx 4813 get_bb_note_from_pool (void) 4814 { 4815 if (VEC_empty (rtx, bb_note_pool)) 4816 return NULL_RTX; 4817 else 4818 { 4819 rtx note = VEC_pop (rtx, bb_note_pool); 4820 4821 PREV_INSN (note) = NULL_RTX; 4822 NEXT_INSN (note) = NULL_RTX; 4823 4824 return note; 4825 } 4826 } 4827 4828 /* Free bb_note_pool. */ 4829 void 4830 free_bb_note_pool (void) 4831 { 4832 VEC_free (rtx, heap, bb_note_pool); 4833 } 4834 4835 /* Setup scheduler pool and successor structure. */ 4836 void 4837 alloc_sched_pools (void) 4838 { 4839 int succs_size; 4840 4841 succs_size = MAX_WS + 1; 4842 succs_info_pool.stack = XCNEWVEC (struct succs_info, succs_size); 4843 succs_info_pool.size = succs_size; 4844 succs_info_pool.top = -1; 4845 succs_info_pool.max_top = -1; 4846 4847 sched_lists_pool = create_alloc_pool ("sel-sched-lists", 4848 sizeof (struct _list_node), 500); 4849 } 4850 4851 /* Free the pools. */ 4852 void 4853 free_sched_pools (void) 4854 { 4855 int i; 4856 4857 free_alloc_pool (sched_lists_pool); 4858 gcc_assert (succs_info_pool.top == -1); 4859 for (i = 0; i < succs_info_pool.max_top; i++) 4860 { 4861 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_ok); 4862 VEC_free (rtx, heap, succs_info_pool.stack[i].succs_other); 4863 VEC_free (int, heap, succs_info_pool.stack[i].probs_ok); 4864 } 4865 free (succs_info_pool.stack); 4866 } 4867 4868 4869 /* Returns a position in RGN where BB can be inserted retaining 4870 topological order. */ 4871 static int 4872 find_place_to_insert_bb (basic_block bb, int rgn) 4873 { 4874 bool has_preds_outside_rgn = false; 4875 edge e; 4876 edge_iterator ei; 4877 4878 /* Find whether we have preds outside the region. */ 4879 FOR_EACH_EDGE (e, ei, bb->preds) 4880 if (!in_current_region_p (e->src)) 4881 { 4882 has_preds_outside_rgn = true; 4883 break; 4884 } 4885 4886 /* Recompute the top order -- needed when we have > 1 pred 4887 and in case we don't have preds outside. */ 4888 if (flag_sel_sched_pipelining_outer_loops 4889 && (has_preds_outside_rgn || EDGE_COUNT (bb->preds) > 1)) 4890 { 4891 int i, bbi = bb->index, cur_bbi; 4892 4893 recompute_rev_top_order (); 4894 for (i = RGN_NR_BLOCKS (rgn) - 1; i >= 0; i--) 4895 { 4896 cur_bbi = BB_TO_BLOCK (i); 4897 if (rev_top_order_index[bbi] 4898 < rev_top_order_index[cur_bbi]) 4899 break; 4900 } 4901 4902 /* We skipped the right block, so we increase i. We accomodate 4903 it for increasing by step later, so we decrease i. */ 4904 return (i + 1) - 1; 4905 } 4906 else if (has_preds_outside_rgn) 4907 { 4908 /* This is the case when we generate an extra empty block 4909 to serve as region head during pipelining. */ 4910 e = EDGE_SUCC (bb, 0); 4911 gcc_assert (EDGE_COUNT (bb->succs) == 1 4912 && in_current_region_p (EDGE_SUCC (bb, 0)->dest) 4913 && (BLOCK_TO_BB (e->dest->index) == 0)); 4914 return -1; 4915 } 4916 4917 /* We don't have preds outside the region. We should have 4918 the only pred, because the multiple preds case comes from 4919 the pipelining of outer loops, and that is handled above. 4920 Just take the bbi of this single pred. */ 4921 if (EDGE_COUNT (bb->succs) > 0) 4922 { 4923 int pred_bbi; 4924 4925 gcc_assert (EDGE_COUNT (bb->preds) == 1); 4926 4927 pred_bbi = EDGE_PRED (bb, 0)->src->index; 4928 return BLOCK_TO_BB (pred_bbi); 4929 } 4930 else 4931 /* BB has no successors. It is safe to put it in the end. */ 4932 return current_nr_blocks - 1; 4933 } 4934 4935 /* Deletes an empty basic block freeing its data. */ 4936 static void 4937 delete_and_free_basic_block (basic_block bb) 4938 { 4939 gcc_assert (sel_bb_empty_p (bb)); 4940 4941 if (BB_LV_SET (bb)) 4942 free_lv_set (bb); 4943 4944 bitmap_clear_bit (blocks_to_reschedule, bb->index); 4945 4946 /* Can't assert av_set properties because we use sel_aremove_bb 4947 when removing loop preheader from the region. At the point of 4948 removing the preheader we already have deallocated sel_region_bb_info. */ 4949 gcc_assert (BB_LV_SET (bb) == NULL 4950 && !BB_LV_SET_VALID_P (bb) 4951 && BB_AV_LEVEL (bb) == 0 4952 && BB_AV_SET (bb) == NULL); 4953 4954 delete_basic_block (bb); 4955 } 4956 4957 /* Add BB to the current region and update the region data. */ 4958 static void 4959 add_block_to_current_region (basic_block bb) 4960 { 4961 int i, pos, bbi = -2, rgn; 4962 4963 rgn = CONTAINING_RGN (BB_TO_BLOCK (0)); 4964 bbi = find_place_to_insert_bb (bb, rgn); 4965 bbi += 1; 4966 pos = RGN_BLOCKS (rgn) + bbi; 4967 4968 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0 4969 && ebb_head[bbi] == pos); 4970 4971 /* Make a place for the new block. */ 4972 extend_regions (); 4973 4974 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--) 4975 BLOCK_TO_BB (rgn_bb_table[i])++; 4976 4977 memmove (rgn_bb_table + pos + 1, 4978 rgn_bb_table + pos, 4979 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table)); 4980 4981 /* Initialize data for BB. */ 4982 rgn_bb_table[pos] = bb->index; 4983 BLOCK_TO_BB (bb->index) = bbi; 4984 CONTAINING_RGN (bb->index) = rgn; 4985 4986 RGN_NR_BLOCKS (rgn)++; 4987 4988 for (i = rgn + 1; i <= nr_regions; i++) 4989 RGN_BLOCKS (i)++; 4990 } 4991 4992 /* Remove BB from the current region and update the region data. */ 4993 static void 4994 remove_bb_from_region (basic_block bb) 4995 { 4996 int i, pos, bbi = -2, rgn; 4997 4998 rgn = CONTAINING_RGN (BB_TO_BLOCK (0)); 4999 bbi = BLOCK_TO_BB (bb->index); 5000 pos = RGN_BLOCKS (rgn) + bbi; 5001 5002 gcc_assert (RGN_HAS_REAL_EBB (rgn) == 0 5003 && ebb_head[bbi] == pos); 5004 5005 for (i = RGN_BLOCKS (rgn + 1) - 1; i >= pos; i--) 5006 BLOCK_TO_BB (rgn_bb_table[i])--; 5007 5008 memmove (rgn_bb_table + pos, 5009 rgn_bb_table + pos + 1, 5010 (RGN_BLOCKS (nr_regions) - pos) * sizeof (*rgn_bb_table)); 5011 5012 RGN_NR_BLOCKS (rgn)--; 5013 for (i = rgn + 1; i <= nr_regions; i++) 5014 RGN_BLOCKS (i)--; 5015 } 5016 5017 /* Add BB to the current region and update all data. If BB is NULL, add all 5018 blocks from last_added_blocks vector. */ 5019 static void 5020 sel_add_bb (basic_block bb) 5021 { 5022 /* Extend luids so that new notes will receive zero luids. */ 5023 sched_init_luids (NULL, NULL, NULL, NULL); 5024 sched_init_bbs (); 5025 sel_init_bbs (last_added_blocks, NULL); 5026 5027 /* When bb is passed explicitly, the vector should contain 5028 the only element that equals to bb; otherwise, the vector 5029 should not be NULL. */ 5030 gcc_assert (last_added_blocks != NULL); 5031 5032 if (bb != NULL) 5033 { 5034 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1 5035 && VEC_index (basic_block, 5036 last_added_blocks, 0) == bb); 5037 add_block_to_current_region (bb); 5038 5039 /* We associate creating/deleting data sets with the first insn 5040 appearing / disappearing in the bb. */ 5041 if (!sel_bb_empty_p (bb) && BB_LV_SET (bb) == NULL) 5042 create_initial_data_sets (bb); 5043 5044 VEC_free (basic_block, heap, last_added_blocks); 5045 } 5046 else 5047 /* BB is NULL - process LAST_ADDED_BLOCKS instead. */ 5048 { 5049 int i; 5050 basic_block temp_bb = NULL; 5051 5052 for (i = 0; 5053 VEC_iterate (basic_block, last_added_blocks, i, bb); i++) 5054 { 5055 add_block_to_current_region (bb); 5056 temp_bb = bb; 5057 } 5058 5059 /* We need to fetch at least one bb so we know the region 5060 to update. */ 5061 gcc_assert (temp_bb != NULL); 5062 bb = temp_bb; 5063 5064 VEC_free (basic_block, heap, last_added_blocks); 5065 } 5066 5067 rgn_setup_region (CONTAINING_RGN (bb->index)); 5068 } 5069 5070 /* Remove BB from the current region and update all data. 5071 If REMOVE_FROM_CFG_PBB is true, also remove the block cfom cfg. */ 5072 static void 5073 sel_remove_bb (basic_block bb, bool remove_from_cfg_p) 5074 { 5075 unsigned idx = bb->index; 5076 5077 gcc_assert (bb != NULL && BB_NOTE_LIST (bb) == NULL_RTX); 5078 5079 remove_bb_from_region (bb); 5080 return_bb_to_pool (bb); 5081 bitmap_clear_bit (blocks_to_reschedule, idx); 5082 5083 if (remove_from_cfg_p) 5084 { 5085 basic_block succ = single_succ (bb); 5086 delete_and_free_basic_block (bb); 5087 set_immediate_dominator (CDI_DOMINATORS, succ, 5088 recompute_dominator (CDI_DOMINATORS, succ)); 5089 } 5090 5091 rgn_setup_region (CONTAINING_RGN (idx)); 5092 } 5093 5094 /* Concatenate info of EMPTY_BB to info of MERGE_BB. */ 5095 static void 5096 move_bb_info (basic_block merge_bb, basic_block empty_bb) 5097 { 5098 gcc_assert (in_current_region_p (merge_bb)); 5099 5100 concat_note_lists (BB_NOTE_LIST (empty_bb), 5101 &BB_NOTE_LIST (merge_bb)); 5102 BB_NOTE_LIST (empty_bb) = NULL_RTX; 5103 5104 } 5105 5106 /* Remove EMPTY_BB. If REMOVE_FROM_CFG_P is false, remove EMPTY_BB from 5107 region, but keep it in CFG. */ 5108 static void 5109 remove_empty_bb (basic_block empty_bb, bool remove_from_cfg_p) 5110 { 5111 /* The block should contain just a note or a label. 5112 We try to check whether it is unused below. */ 5113 gcc_assert (BB_HEAD (empty_bb) == BB_END (empty_bb) 5114 || LABEL_P (BB_HEAD (empty_bb))); 5115 5116 /* If basic block has predecessors or successors, redirect them. */ 5117 if (remove_from_cfg_p 5118 && (EDGE_COUNT (empty_bb->preds) > 0 5119 || EDGE_COUNT (empty_bb->succs) > 0)) 5120 { 5121 basic_block pred; 5122 basic_block succ; 5123 5124 /* We need to init PRED and SUCC before redirecting edges. */ 5125 if (EDGE_COUNT (empty_bb->preds) > 0) 5126 { 5127 edge e; 5128 5129 gcc_assert (EDGE_COUNT (empty_bb->preds) == 1); 5130 5131 e = EDGE_PRED (empty_bb, 0); 5132 gcc_assert (e->src == empty_bb->prev_bb 5133 && (e->flags & EDGE_FALLTHRU)); 5134 5135 pred = empty_bb->prev_bb; 5136 } 5137 else 5138 pred = NULL; 5139 5140 if (EDGE_COUNT (empty_bb->succs) > 0) 5141 { 5142 /* We do not check fallthruness here as above, because 5143 after removing a jump the edge may actually be not fallthru. */ 5144 gcc_assert (EDGE_COUNT (empty_bb->succs) == 1); 5145 succ = EDGE_SUCC (empty_bb, 0)->dest; 5146 } 5147 else 5148 succ = NULL; 5149 5150 if (EDGE_COUNT (empty_bb->preds) > 0 && succ != NULL) 5151 { 5152 edge e = EDGE_PRED (empty_bb, 0); 5153 5154 if (e->flags & EDGE_FALLTHRU) 5155 redirect_edge_succ_nodup (e, succ); 5156 else 5157 sel_redirect_edge_and_branch (EDGE_PRED (empty_bb, 0), succ); 5158 } 5159 5160 if (EDGE_COUNT (empty_bb->succs) > 0 && pred != NULL) 5161 { 5162 edge e = EDGE_SUCC (empty_bb, 0); 5163 5164 if (find_edge (pred, e->dest) == NULL) 5165 redirect_edge_pred (e, pred); 5166 } 5167 } 5168 5169 /* Finish removing. */ 5170 sel_remove_bb (empty_bb, remove_from_cfg_p); 5171 } 5172 5173 /* An implementation of create_basic_block hook, which additionally updates 5174 per-bb data structures. */ 5175 static basic_block 5176 sel_create_basic_block (void *headp, void *endp, basic_block after) 5177 { 5178 basic_block new_bb; 5179 insn_t new_bb_note; 5180 5181 gcc_assert (flag_sel_sched_pipelining_outer_loops 5182 || last_added_blocks == NULL); 5183 5184 new_bb_note = get_bb_note_from_pool (); 5185 5186 if (new_bb_note == NULL_RTX) 5187 new_bb = orig_cfg_hooks.create_basic_block (headp, endp, after); 5188 else 5189 { 5190 new_bb = create_basic_block_structure ((rtx) headp, (rtx) endp, 5191 new_bb_note, after); 5192 new_bb->aux = NULL; 5193 } 5194 5195 VEC_safe_push (basic_block, heap, last_added_blocks, new_bb); 5196 5197 return new_bb; 5198 } 5199 5200 /* Implement sched_init_only_bb (). */ 5201 static void 5202 sel_init_only_bb (basic_block bb, basic_block after) 5203 { 5204 gcc_assert (after == NULL); 5205 5206 extend_regions (); 5207 rgn_make_new_region_out_of_new_block (bb); 5208 } 5209 5210 /* Update the latch when we've splitted or merged it from FROM block to TO. 5211 This should be checked for all outer loops, too. */ 5212 static void 5213 change_loops_latches (basic_block from, basic_block to) 5214 { 5215 gcc_assert (from != to); 5216 5217 if (current_loop_nest) 5218 { 5219 struct loop *loop; 5220 5221 for (loop = current_loop_nest; loop; loop = loop_outer (loop)) 5222 if (considered_for_pipelining_p (loop) && loop->latch == from) 5223 { 5224 gcc_assert (loop == current_loop_nest); 5225 loop->latch = to; 5226 gcc_assert (loop_latch_edge (loop)); 5227 } 5228 } 5229 } 5230 5231 /* Splits BB on two basic blocks, adding it to the region and extending 5232 per-bb data structures. Returns the newly created bb. */ 5233 static basic_block 5234 sel_split_block (basic_block bb, rtx after) 5235 { 5236 basic_block new_bb; 5237 insn_t insn; 5238 5239 new_bb = sched_split_block_1 (bb, after); 5240 sel_add_bb (new_bb); 5241 5242 /* This should be called after sel_add_bb, because this uses 5243 CONTAINING_RGN for the new block, which is not yet initialized. 5244 FIXME: this function may be a no-op now. */ 5245 change_loops_latches (bb, new_bb); 5246 5247 /* Update ORIG_BB_INDEX for insns moved into the new block. */ 5248 FOR_BB_INSNS (new_bb, insn) 5249 if (INSN_P (insn)) 5250 EXPR_ORIG_BB_INDEX (INSN_EXPR (insn)) = new_bb->index; 5251 5252 if (sel_bb_empty_p (bb)) 5253 { 5254 gcc_assert (!sel_bb_empty_p (new_bb)); 5255 5256 /* NEW_BB has data sets that need to be updated and BB holds 5257 data sets that should be removed. Exchange these data sets 5258 so that we won't lose BB's valid data sets. */ 5259 exchange_data_sets (new_bb, bb); 5260 free_data_sets (bb); 5261 } 5262 5263 if (!sel_bb_empty_p (new_bb) 5264 && bitmap_bit_p (blocks_to_reschedule, bb->index)) 5265 bitmap_set_bit (blocks_to_reschedule, new_bb->index); 5266 5267 return new_bb; 5268 } 5269 5270 /* If BB ends with a jump insn whose ID is bigger then PREV_MAX_UID, return it. 5271 Otherwise returns NULL. */ 5272 static rtx 5273 check_for_new_jump (basic_block bb, int prev_max_uid) 5274 { 5275 rtx end; 5276 5277 end = sel_bb_end (bb); 5278 if (end && INSN_UID (end) >= prev_max_uid) 5279 return end; 5280 return NULL; 5281 } 5282 5283 /* Look for a new jump either in FROM_BB block or in newly created JUMP_BB block. 5284 New means having UID at least equal to PREV_MAX_UID. */ 5285 static rtx 5286 find_new_jump (basic_block from, basic_block jump_bb, int prev_max_uid) 5287 { 5288 rtx jump; 5289 5290 /* Return immediately if no new insns were emitted. */ 5291 if (get_max_uid () == prev_max_uid) 5292 return NULL; 5293 5294 /* Now check both blocks for new jumps. It will ever be only one. */ 5295 if ((jump = check_for_new_jump (from, prev_max_uid))) 5296 return jump; 5297 5298 if (jump_bb != NULL 5299 && (jump = check_for_new_jump (jump_bb, prev_max_uid))) 5300 return jump; 5301 return NULL; 5302 } 5303 5304 /* Splits E and adds the newly created basic block to the current region. 5305 Returns this basic block. */ 5306 basic_block 5307 sel_split_edge (edge e) 5308 { 5309 basic_block new_bb, src, other_bb = NULL; 5310 int prev_max_uid; 5311 rtx jump; 5312 5313 src = e->src; 5314 prev_max_uid = get_max_uid (); 5315 new_bb = split_edge (e); 5316 5317 if (flag_sel_sched_pipelining_outer_loops 5318 && current_loop_nest) 5319 { 5320 int i; 5321 basic_block bb; 5322 5323 /* Some of the basic blocks might not have been added to the loop. 5324 Add them here, until this is fixed in force_fallthru. */ 5325 for (i = 0; 5326 VEC_iterate (basic_block, last_added_blocks, i, bb); i++) 5327 if (!bb->loop_father) 5328 { 5329 add_bb_to_loop (bb, e->dest->loop_father); 5330 5331 gcc_assert (!other_bb && (new_bb->index != bb->index)); 5332 other_bb = bb; 5333 } 5334 } 5335 5336 /* Add all last_added_blocks to the region. */ 5337 sel_add_bb (NULL); 5338 5339 jump = find_new_jump (src, new_bb, prev_max_uid); 5340 if (jump) 5341 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP); 5342 5343 /* Put the correct lv set on this block. */ 5344 if (other_bb && !sel_bb_empty_p (other_bb)) 5345 compute_live (sel_bb_head (other_bb)); 5346 5347 return new_bb; 5348 } 5349 5350 /* Implement sched_create_empty_bb (). */ 5351 static basic_block 5352 sel_create_empty_bb (basic_block after) 5353 { 5354 basic_block new_bb; 5355 5356 new_bb = sched_create_empty_bb_1 (after); 5357 5358 /* We'll explicitly initialize NEW_BB via sel_init_only_bb () a bit 5359 later. */ 5360 gcc_assert (VEC_length (basic_block, last_added_blocks) == 1 5361 && VEC_index (basic_block, last_added_blocks, 0) == new_bb); 5362 5363 VEC_free (basic_block, heap, last_added_blocks); 5364 return new_bb; 5365 } 5366 5367 /* Implement sched_create_recovery_block. ORIG_INSN is where block 5368 will be splitted to insert a check. */ 5369 basic_block 5370 sel_create_recovery_block (insn_t orig_insn) 5371 { 5372 basic_block first_bb, second_bb, recovery_block; 5373 basic_block before_recovery = NULL; 5374 rtx jump; 5375 5376 first_bb = BLOCK_FOR_INSN (orig_insn); 5377 if (sel_bb_end_p (orig_insn)) 5378 { 5379 /* Avoid introducing an empty block while splitting. */ 5380 gcc_assert (single_succ_p (first_bb)); 5381 second_bb = single_succ (first_bb); 5382 } 5383 else 5384 second_bb = sched_split_block (first_bb, orig_insn); 5385 5386 recovery_block = sched_create_recovery_block (&before_recovery); 5387 if (before_recovery) 5388 copy_lv_set_from (before_recovery, EXIT_BLOCK_PTR); 5389 5390 gcc_assert (sel_bb_empty_p (recovery_block)); 5391 sched_create_recovery_edges (first_bb, recovery_block, second_bb); 5392 if (current_loops != NULL) 5393 add_bb_to_loop (recovery_block, first_bb->loop_father); 5394 5395 sel_add_bb (recovery_block); 5396 5397 jump = BB_END (recovery_block); 5398 gcc_assert (sel_bb_head (recovery_block) == jump); 5399 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP); 5400 5401 return recovery_block; 5402 } 5403 5404 /* Merge basic block B into basic block A. */ 5405 static void 5406 sel_merge_blocks (basic_block a, basic_block b) 5407 { 5408 gcc_assert (sel_bb_empty_p (b) 5409 && EDGE_COUNT (b->preds) == 1 5410 && EDGE_PRED (b, 0)->src == b->prev_bb); 5411 5412 move_bb_info (b->prev_bb, b); 5413 remove_empty_bb (b, false); 5414 merge_blocks (a, b); 5415 change_loops_latches (b, a); 5416 } 5417 5418 /* A wrapper for redirect_edge_and_branch_force, which also initializes 5419 data structures for possibly created bb and insns. Returns the newly 5420 added bb or NULL, when a bb was not needed. */ 5421 void 5422 sel_redirect_edge_and_branch_force (edge e, basic_block to) 5423 { 5424 basic_block jump_bb, src, orig_dest = e->dest; 5425 int prev_max_uid; 5426 rtx jump; 5427 5428 /* This function is now used only for bookkeeping code creation, where 5429 we'll never get the single pred of orig_dest block and thus will not 5430 hit unreachable blocks when updating dominator info. */ 5431 gcc_assert (!sel_bb_empty_p (e->src) 5432 && !single_pred_p (orig_dest)); 5433 src = e->src; 5434 prev_max_uid = get_max_uid (); 5435 jump_bb = redirect_edge_and_branch_force (e, to); 5436 5437 if (jump_bb != NULL) 5438 sel_add_bb (jump_bb); 5439 5440 /* This function could not be used to spoil the loop structure by now, 5441 thus we don't care to update anything. But check it to be sure. */ 5442 if (current_loop_nest 5443 && pipelining_p) 5444 gcc_assert (loop_latch_edge (current_loop_nest)); 5445 5446 jump = find_new_jump (src, jump_bb, prev_max_uid); 5447 if (jump) 5448 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP); 5449 set_immediate_dominator (CDI_DOMINATORS, to, 5450 recompute_dominator (CDI_DOMINATORS, to)); 5451 set_immediate_dominator (CDI_DOMINATORS, orig_dest, 5452 recompute_dominator (CDI_DOMINATORS, orig_dest)); 5453 } 5454 5455 /* A wrapper for redirect_edge_and_branch. Return TRUE if blocks connected by 5456 redirected edge are in reverse topological order. */ 5457 bool 5458 sel_redirect_edge_and_branch (edge e, basic_block to) 5459 { 5460 bool latch_edge_p; 5461 basic_block src, orig_dest = e->dest; 5462 int prev_max_uid; 5463 rtx jump; 5464 edge redirected; 5465 bool recompute_toporder_p = false; 5466 bool maybe_unreachable = single_pred_p (orig_dest); 5467 5468 latch_edge_p = (pipelining_p 5469 && current_loop_nest 5470 && e == loop_latch_edge (current_loop_nest)); 5471 5472 src = e->src; 5473 prev_max_uid = get_max_uid (); 5474 5475 redirected = redirect_edge_and_branch (e, to); 5476 5477 gcc_assert (redirected && last_added_blocks == NULL); 5478 5479 /* When we've redirected a latch edge, update the header. */ 5480 if (latch_edge_p) 5481 { 5482 current_loop_nest->header = to; 5483 gcc_assert (loop_latch_edge (current_loop_nest)); 5484 } 5485 5486 /* In rare situations, the topological relation between the blocks connected 5487 by the redirected edge can change (see PR42245 for an example). Update 5488 block_to_bb/bb_to_block. */ 5489 if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index) 5490 && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index)) 5491 recompute_toporder_p = true; 5492 5493 jump = find_new_jump (src, NULL, prev_max_uid); 5494 if (jump) 5495 sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP); 5496 5497 /* Only update dominator info when we don't have unreachable blocks. 5498 Otherwise we'll update in maybe_tidy_empty_bb. */ 5499 if (!maybe_unreachable) 5500 { 5501 set_immediate_dominator (CDI_DOMINATORS, to, 5502 recompute_dominator (CDI_DOMINATORS, to)); 5503 set_immediate_dominator (CDI_DOMINATORS, orig_dest, 5504 recompute_dominator (CDI_DOMINATORS, orig_dest)); 5505 } 5506 return recompute_toporder_p; 5507 } 5508 5509 /* This variable holds the cfg hooks used by the selective scheduler. */ 5510 static struct cfg_hooks sel_cfg_hooks; 5511 5512 /* Register sel-sched cfg hooks. */ 5513 void 5514 sel_register_cfg_hooks (void) 5515 { 5516 sched_split_block = sel_split_block; 5517 5518 orig_cfg_hooks = get_cfg_hooks (); 5519 sel_cfg_hooks = orig_cfg_hooks; 5520 5521 sel_cfg_hooks.create_basic_block = sel_create_basic_block; 5522 5523 set_cfg_hooks (sel_cfg_hooks); 5524 5525 sched_init_only_bb = sel_init_only_bb; 5526 sched_split_block = sel_split_block; 5527 sched_create_empty_bb = sel_create_empty_bb; 5528 } 5529 5530 /* Unregister sel-sched cfg hooks. */ 5531 void 5532 sel_unregister_cfg_hooks (void) 5533 { 5534 sched_create_empty_bb = NULL; 5535 sched_split_block = NULL; 5536 sched_init_only_bb = NULL; 5537 5538 set_cfg_hooks (orig_cfg_hooks); 5539 } 5540 5541 5542 /* Emit an insn rtx based on PATTERN. If a jump insn is wanted, 5543 LABEL is where this jump should be directed. */ 5544 rtx 5545 create_insn_rtx_from_pattern (rtx pattern, rtx label) 5546 { 5547 rtx insn_rtx; 5548 5549 gcc_assert (!INSN_P (pattern)); 5550 5551 start_sequence (); 5552 5553 if (label == NULL_RTX) 5554 insn_rtx = emit_insn (pattern); 5555 else if (DEBUG_INSN_P (label)) 5556 insn_rtx = emit_debug_insn (pattern); 5557 else 5558 { 5559 insn_rtx = emit_jump_insn (pattern); 5560 JUMP_LABEL (insn_rtx) = label; 5561 ++LABEL_NUSES (label); 5562 } 5563 5564 end_sequence (); 5565 5566 sched_init_luids (NULL, NULL, NULL, NULL); 5567 sched_extend_target (); 5568 sched_deps_init (false); 5569 5570 /* Initialize INSN_CODE now. */ 5571 recog_memoized (insn_rtx); 5572 return insn_rtx; 5573 } 5574 5575 /* Create a new vinsn for INSN_RTX. FORCE_UNIQUE_P is true when the vinsn 5576 must not be clonable. */ 5577 vinsn_t 5578 create_vinsn_from_insn_rtx (rtx insn_rtx, bool force_unique_p) 5579 { 5580 gcc_assert (INSN_P (insn_rtx) && !INSN_IN_STREAM_P (insn_rtx)); 5581 5582 /* If VINSN_TYPE is not USE, retain its uniqueness. */ 5583 return vinsn_create (insn_rtx, force_unique_p); 5584 } 5585 5586 /* Create a copy of INSN_RTX. */ 5587 rtx 5588 create_copy_of_insn_rtx (rtx insn_rtx) 5589 { 5590 rtx res; 5591 5592 if (DEBUG_INSN_P (insn_rtx)) 5593 return create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)), 5594 insn_rtx); 5595 5596 gcc_assert (NONJUMP_INSN_P (insn_rtx)); 5597 5598 res = create_insn_rtx_from_pattern (copy_rtx (PATTERN (insn_rtx)), 5599 NULL_RTX); 5600 return res; 5601 } 5602 5603 /* Change vinsn field of EXPR to hold NEW_VINSN. */ 5604 void 5605 change_vinsn_in_expr (expr_t expr, vinsn_t new_vinsn) 5606 { 5607 vinsn_detach (EXPR_VINSN (expr)); 5608 5609 EXPR_VINSN (expr) = new_vinsn; 5610 vinsn_attach (new_vinsn); 5611 } 5612 5613 /* Helpers for global init. */ 5614 /* This structure is used to be able to call existing bundling mechanism 5615 and calculate insn priorities. */ 5616 static struct haifa_sched_info sched_sel_haifa_sched_info = 5617 { 5618 NULL, /* init_ready_list */ 5619 NULL, /* can_schedule_ready_p */ 5620 NULL, /* schedule_more_p */ 5621 NULL, /* new_ready */ 5622 NULL, /* rgn_rank */ 5623 sel_print_insn, /* rgn_print_insn */ 5624 contributes_to_priority, 5625 NULL, /* insn_finishes_block_p */ 5626 5627 NULL, NULL, 5628 NULL, NULL, 5629 0, 0, 5630 5631 NULL, /* add_remove_insn */ 5632 NULL, /* begin_schedule_ready */ 5633 NULL, /* advance_target_bb */ 5634 SEL_SCHED | NEW_BBS 5635 }; 5636 5637 /* Setup special insns used in the scheduler. */ 5638 void 5639 setup_nop_and_exit_insns (void) 5640 { 5641 gcc_assert (nop_pattern == NULL_RTX 5642 && exit_insn == NULL_RTX); 5643 5644 nop_pattern = constm1_rtx; 5645 5646 start_sequence (); 5647 emit_insn (nop_pattern); 5648 exit_insn = get_insns (); 5649 end_sequence (); 5650 set_block_for_insn (exit_insn, EXIT_BLOCK_PTR); 5651 } 5652 5653 /* Free special insns used in the scheduler. */ 5654 void 5655 free_nop_and_exit_insns (void) 5656 { 5657 exit_insn = NULL_RTX; 5658 nop_pattern = NULL_RTX; 5659 } 5660 5661 /* Setup a special vinsn used in new insns initialization. */ 5662 void 5663 setup_nop_vinsn (void) 5664 { 5665 nop_vinsn = vinsn_create (exit_insn, false); 5666 vinsn_attach (nop_vinsn); 5667 } 5668 5669 /* Free a special vinsn used in new insns initialization. */ 5670 void 5671 free_nop_vinsn (void) 5672 { 5673 gcc_assert (VINSN_COUNT (nop_vinsn) == 1); 5674 vinsn_detach (nop_vinsn); 5675 nop_vinsn = NULL; 5676 } 5677 5678 /* Call a set_sched_flags hook. */ 5679 void 5680 sel_set_sched_flags (void) 5681 { 5682 /* ??? This means that set_sched_flags were called, and we decided to 5683 support speculation. However, set_sched_flags also modifies flags 5684 on current_sched_info, doing this only at global init. And we 5685 sometimes change c_s_i later. So put the correct flags again. */ 5686 if (spec_info && targetm.sched.set_sched_flags) 5687 targetm.sched.set_sched_flags (spec_info); 5688 } 5689 5690 /* Setup pointers to global sched info structures. */ 5691 void 5692 sel_setup_sched_infos (void) 5693 { 5694 rgn_setup_common_sched_info (); 5695 5696 memcpy (&sel_common_sched_info, common_sched_info, 5697 sizeof (sel_common_sched_info)); 5698 5699 sel_common_sched_info.fix_recovery_cfg = NULL; 5700 sel_common_sched_info.add_block = NULL; 5701 sel_common_sched_info.estimate_number_of_insns 5702 = sel_estimate_number_of_insns; 5703 sel_common_sched_info.luid_for_non_insn = sel_luid_for_non_insn; 5704 sel_common_sched_info.sched_pass_id = SCHED_SEL_PASS; 5705 5706 common_sched_info = &sel_common_sched_info; 5707 5708 current_sched_info = &sched_sel_haifa_sched_info; 5709 current_sched_info->sched_max_insns_priority = 5710 get_rgn_sched_max_insns_priority (); 5711 5712 sel_set_sched_flags (); 5713 } 5714 5715 5716 /* Adds basic block BB to region RGN at the position *BB_ORD_INDEX, 5717 *BB_ORD_INDEX after that is increased. */ 5718 static void 5719 sel_add_block_to_region (basic_block bb, int *bb_ord_index, int rgn) 5720 { 5721 RGN_NR_BLOCKS (rgn) += 1; 5722 RGN_DONT_CALC_DEPS (rgn) = 0; 5723 RGN_HAS_REAL_EBB (rgn) = 0; 5724 CONTAINING_RGN (bb->index) = rgn; 5725 BLOCK_TO_BB (bb->index) = *bb_ord_index; 5726 rgn_bb_table[RGN_BLOCKS (rgn) + *bb_ord_index] = bb->index; 5727 (*bb_ord_index)++; 5728 5729 /* FIXME: it is true only when not scheduling ebbs. */ 5730 RGN_BLOCKS (rgn + 1) = RGN_BLOCKS (rgn) + RGN_NR_BLOCKS (rgn); 5731 } 5732 5733 /* Functions to support pipelining of outer loops. */ 5734 5735 /* Creates a new empty region and returns it's number. */ 5736 static int 5737 sel_create_new_region (void) 5738 { 5739 int new_rgn_number = nr_regions; 5740 5741 RGN_NR_BLOCKS (new_rgn_number) = 0; 5742 5743 /* FIXME: This will work only when EBBs are not created. */ 5744 if (new_rgn_number != 0) 5745 RGN_BLOCKS (new_rgn_number) = RGN_BLOCKS (new_rgn_number - 1) + 5746 RGN_NR_BLOCKS (new_rgn_number - 1); 5747 else 5748 RGN_BLOCKS (new_rgn_number) = 0; 5749 5750 /* Set the blocks of the next region so the other functions may 5751 calculate the number of blocks in the region. */ 5752 RGN_BLOCKS (new_rgn_number + 1) = RGN_BLOCKS (new_rgn_number) + 5753 RGN_NR_BLOCKS (new_rgn_number); 5754 5755 nr_regions++; 5756 5757 return new_rgn_number; 5758 } 5759 5760 /* If X has a smaller topological sort number than Y, returns -1; 5761 if greater, returns 1. */ 5762 static int 5763 bb_top_order_comparator (const void *x, const void *y) 5764 { 5765 basic_block bb1 = *(const basic_block *) x; 5766 basic_block bb2 = *(const basic_block *) y; 5767 5768 gcc_assert (bb1 == bb2 5769 || rev_top_order_index[bb1->index] 5770 != rev_top_order_index[bb2->index]); 5771 5772 /* It's a reverse topological order in REV_TOP_ORDER_INDEX, so 5773 bbs with greater number should go earlier. */ 5774 if (rev_top_order_index[bb1->index] > rev_top_order_index[bb2->index]) 5775 return -1; 5776 else 5777 return 1; 5778 } 5779 5780 /* Create a region for LOOP and return its number. If we don't want 5781 to pipeline LOOP, return -1. */ 5782 static int 5783 make_region_from_loop (struct loop *loop) 5784 { 5785 unsigned int i; 5786 int new_rgn_number = -1; 5787 struct loop *inner; 5788 5789 /* Basic block index, to be assigned to BLOCK_TO_BB. */ 5790 int bb_ord_index = 0; 5791 basic_block *loop_blocks; 5792 basic_block preheader_block; 5793 5794 if (loop->num_nodes 5795 > (unsigned) PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_BLOCKS)) 5796 return -1; 5797 5798 /* Don't pipeline loops whose latch belongs to some of its inner loops. */ 5799 for (inner = loop->inner; inner; inner = inner->inner) 5800 if (flow_bb_inside_loop_p (inner, loop->latch)) 5801 return -1; 5802 5803 loop->ninsns = num_loop_insns (loop); 5804 if ((int) loop->ninsns > PARAM_VALUE (PARAM_MAX_PIPELINE_REGION_INSNS)) 5805 return -1; 5806 5807 loop_blocks = get_loop_body_in_custom_order (loop, bb_top_order_comparator); 5808 5809 for (i = 0; i < loop->num_nodes; i++) 5810 if (loop_blocks[i]->flags & BB_IRREDUCIBLE_LOOP) 5811 { 5812 free (loop_blocks); 5813 return -1; 5814 } 5815 5816 preheader_block = loop_preheader_edge (loop)->src; 5817 gcc_assert (preheader_block); 5818 gcc_assert (loop_blocks[0] == loop->header); 5819 5820 new_rgn_number = sel_create_new_region (); 5821 5822 sel_add_block_to_region (preheader_block, &bb_ord_index, new_rgn_number); 5823 SET_BIT (bbs_in_loop_rgns, preheader_block->index); 5824 5825 for (i = 0; i < loop->num_nodes; i++) 5826 { 5827 /* Add only those blocks that haven't been scheduled in the inner loop. 5828 The exception is the basic blocks with bookkeeping code - they should 5829 be added to the region (and they actually don't belong to the loop 5830 body, but to the region containing that loop body). */ 5831 5832 gcc_assert (new_rgn_number >= 0); 5833 5834 if (! TEST_BIT (bbs_in_loop_rgns, loop_blocks[i]->index)) 5835 { 5836 sel_add_block_to_region (loop_blocks[i], &bb_ord_index, 5837 new_rgn_number); 5838 SET_BIT (bbs_in_loop_rgns, loop_blocks[i]->index); 5839 } 5840 } 5841 5842 free (loop_blocks); 5843 MARK_LOOP_FOR_PIPELINING (loop); 5844 5845 return new_rgn_number; 5846 } 5847 5848 /* Create a new region from preheader blocks LOOP_BLOCKS. */ 5849 void 5850 make_region_from_loop_preheader (VEC(basic_block, heap) **loop_blocks) 5851 { 5852 unsigned int i; 5853 int new_rgn_number = -1; 5854 basic_block bb; 5855 5856 /* Basic block index, to be assigned to BLOCK_TO_BB. */ 5857 int bb_ord_index = 0; 5858 5859 new_rgn_number = sel_create_new_region (); 5860 5861 for (i = 0; VEC_iterate (basic_block, *loop_blocks, i, bb); i++) 5862 { 5863 gcc_assert (new_rgn_number >= 0); 5864 5865 sel_add_block_to_region (bb, &bb_ord_index, new_rgn_number); 5866 } 5867 5868 VEC_free (basic_block, heap, *loop_blocks); 5869 gcc_assert (*loop_blocks == NULL); 5870 } 5871 5872 5873 /* Create region(s) from loop nest LOOP, such that inner loops will be 5874 pipelined before outer loops. Returns true when a region for LOOP 5875 is created. */ 5876 static bool 5877 make_regions_from_loop_nest (struct loop *loop) 5878 { 5879 struct loop *cur_loop; 5880 int rgn_number; 5881 5882 /* Traverse all inner nodes of the loop. */ 5883 for (cur_loop = loop->inner; cur_loop; cur_loop = cur_loop->next) 5884 if (! TEST_BIT (bbs_in_loop_rgns, cur_loop->header->index)) 5885 return false; 5886 5887 /* At this moment all regular inner loops should have been pipelined. 5888 Try to create a region from this loop. */ 5889 rgn_number = make_region_from_loop (loop); 5890 5891 if (rgn_number < 0) 5892 return false; 5893 5894 VEC_safe_push (loop_p, heap, loop_nests, loop); 5895 return true; 5896 } 5897 5898 /* Initalize data structures needed. */ 5899 void 5900 sel_init_pipelining (void) 5901 { 5902 /* Collect loop information to be used in outer loops pipelining. */ 5903 loop_optimizer_init (LOOPS_HAVE_PREHEADERS 5904 | LOOPS_HAVE_FALLTHRU_PREHEADERS 5905 | LOOPS_HAVE_RECORDED_EXITS 5906 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); 5907 current_loop_nest = NULL; 5908 5909 bbs_in_loop_rgns = sbitmap_alloc (last_basic_block); 5910 sbitmap_zero (bbs_in_loop_rgns); 5911 5912 recompute_rev_top_order (); 5913 } 5914 5915 /* Returns a struct loop for region RGN. */ 5916 loop_p 5917 get_loop_nest_for_rgn (unsigned int rgn) 5918 { 5919 /* Regions created with extend_rgns don't have corresponding loop nests, 5920 because they don't represent loops. */ 5921 if (rgn < VEC_length (loop_p, loop_nests)) 5922 return VEC_index (loop_p, loop_nests, rgn); 5923 else 5924 return NULL; 5925 } 5926 5927 /* True when LOOP was included into pipelining regions. */ 5928 bool 5929 considered_for_pipelining_p (struct loop *loop) 5930 { 5931 if (loop_depth (loop) == 0) 5932 return false; 5933 5934 /* Now, the loop could be too large or irreducible. Check whether its 5935 region is in LOOP_NESTS. 5936 We determine the region number of LOOP as the region number of its 5937 latch. We can't use header here, because this header could be 5938 just removed preheader and it will give us the wrong region number. 5939 Latch can't be used because it could be in the inner loop too. */ 5940 if (LOOP_MARKED_FOR_PIPELINING_P (loop)) 5941 { 5942 int rgn = CONTAINING_RGN (loop->latch->index); 5943 5944 gcc_assert ((unsigned) rgn < VEC_length (loop_p, loop_nests)); 5945 return true; 5946 } 5947 5948 return false; 5949 } 5950 5951 /* Makes regions from the rest of the blocks, after loops are chosen 5952 for pipelining. */ 5953 static void 5954 make_regions_from_the_rest (void) 5955 { 5956 int cur_rgn_blocks; 5957 int *loop_hdr; 5958 int i; 5959 5960 basic_block bb; 5961 edge e; 5962 edge_iterator ei; 5963 int *degree; 5964 5965 /* Index in rgn_bb_table where to start allocating new regions. */ 5966 cur_rgn_blocks = nr_regions ? RGN_BLOCKS (nr_regions) : 0; 5967 5968 /* Make regions from all the rest basic blocks - those that don't belong to 5969 any loop or belong to irreducible loops. Prepare the data structures 5970 for extend_rgns. */ 5971 5972 /* LOOP_HDR[I] == -1 if I-th bb doesn't belong to any loop, 5973 LOOP_HDR[I] == LOOP_HDR[J] iff basic blocks I and J reside within the same 5974 loop. */ 5975 loop_hdr = XNEWVEC (int, last_basic_block); 5976 degree = XCNEWVEC (int, last_basic_block); 5977 5978 5979 /* For each basic block that belongs to some loop assign the number 5980 of innermost loop it belongs to. */ 5981 for (i = 0; i < last_basic_block; i++) 5982 loop_hdr[i] = -1; 5983 5984 FOR_EACH_BB (bb) 5985 { 5986 if (bb->loop_father && !bb->loop_father->num == 0 5987 && !(bb->flags & BB_IRREDUCIBLE_LOOP)) 5988 loop_hdr[bb->index] = bb->loop_father->num; 5989 } 5990 5991 /* For each basic block degree is calculated as the number of incoming 5992 edges, that are going out of bbs that are not yet scheduled. 5993 The basic blocks that are scheduled have degree value of zero. */ 5994 FOR_EACH_BB (bb) 5995 { 5996 degree[bb->index] = 0; 5997 5998 if (!TEST_BIT (bbs_in_loop_rgns, bb->index)) 5999 { 6000 FOR_EACH_EDGE (e, ei, bb->preds) 6001 if (!TEST_BIT (bbs_in_loop_rgns, e->src->index)) 6002 degree[bb->index]++; 6003 } 6004 else 6005 degree[bb->index] = -1; 6006 } 6007 6008 extend_rgns (degree, &cur_rgn_blocks, bbs_in_loop_rgns, loop_hdr); 6009 6010 /* Any block that did not end up in a region is placed into a region 6011 by itself. */ 6012 FOR_EACH_BB (bb) 6013 if (degree[bb->index] >= 0) 6014 { 6015 rgn_bb_table[cur_rgn_blocks] = bb->index; 6016 RGN_NR_BLOCKS (nr_regions) = 1; 6017 RGN_BLOCKS (nr_regions) = cur_rgn_blocks++; 6018 RGN_DONT_CALC_DEPS (nr_regions) = 0; 6019 RGN_HAS_REAL_EBB (nr_regions) = 0; 6020 CONTAINING_RGN (bb->index) = nr_regions++; 6021 BLOCK_TO_BB (bb->index) = 0; 6022 } 6023 6024 free (degree); 6025 free (loop_hdr); 6026 } 6027 6028 /* Free data structures used in pipelining of loops. */ 6029 void sel_finish_pipelining (void) 6030 { 6031 loop_iterator li; 6032 struct loop *loop; 6033 6034 /* Release aux fields so we don't free them later by mistake. */ 6035 FOR_EACH_LOOP (li, loop, 0) 6036 loop->aux = NULL; 6037 6038 loop_optimizer_finalize (); 6039 6040 VEC_free (loop_p, heap, loop_nests); 6041 6042 free (rev_top_order_index); 6043 rev_top_order_index = NULL; 6044 } 6045 6046 /* This function replaces the find_rgns when 6047 FLAG_SEL_SCHED_PIPELINING_OUTER_LOOPS is set. */ 6048 void 6049 sel_find_rgns (void) 6050 { 6051 sel_init_pipelining (); 6052 extend_regions (); 6053 6054 if (current_loops) 6055 { 6056 loop_p loop; 6057 loop_iterator li; 6058 6059 FOR_EACH_LOOP (li, loop, (flag_sel_sched_pipelining_outer_loops 6060 ? LI_FROM_INNERMOST 6061 : LI_ONLY_INNERMOST)) 6062 make_regions_from_loop_nest (loop); 6063 } 6064 6065 /* Make regions from all the rest basic blocks and schedule them. 6066 These blocks include blocks that don't belong to any loop or belong 6067 to irreducible loops. */ 6068 make_regions_from_the_rest (); 6069 6070 /* We don't need bbs_in_loop_rgns anymore. */ 6071 sbitmap_free (bbs_in_loop_rgns); 6072 bbs_in_loop_rgns = NULL; 6073 } 6074 6075 /* Adds the preheader blocks from previous loop to current region taking 6076 it from LOOP_PREHEADER_BLOCKS (current_loop_nest). 6077 This function is only used with -fsel-sched-pipelining-outer-loops. */ 6078 void 6079 sel_add_loop_preheaders (void) 6080 { 6081 int i; 6082 basic_block bb; 6083 VEC(basic_block, heap) *preheader_blocks 6084 = LOOP_PREHEADER_BLOCKS (current_loop_nest); 6085 6086 for (i = 0; 6087 VEC_iterate (basic_block, preheader_blocks, i, bb); 6088 i++) 6089 { 6090 VEC_safe_push (basic_block, heap, last_added_blocks, bb); 6091 sel_add_bb (bb); 6092 } 6093 6094 VEC_free (basic_block, heap, preheader_blocks); 6095 } 6096 6097 /* While pipelining outer loops, returns TRUE if BB is a loop preheader. 6098 Please note that the function should also work when pipelining_p is 6099 false, because it is used when deciding whether we should or should 6100 not reschedule pipelined code. */ 6101 bool 6102 sel_is_loop_preheader_p (basic_block bb) 6103 { 6104 if (current_loop_nest) 6105 { 6106 struct loop *outer; 6107 6108 if (preheader_removed) 6109 return false; 6110 6111 /* Preheader is the first block in the region. */ 6112 if (BLOCK_TO_BB (bb->index) == 0) 6113 return true; 6114 6115 /* We used to find a preheader with the topological information. 6116 Check that the above code is equivalent to what we did before. */ 6117 6118 if (in_current_region_p (current_loop_nest->header)) 6119 gcc_assert (!(BLOCK_TO_BB (bb->index) 6120 < BLOCK_TO_BB (current_loop_nest->header->index))); 6121 6122 /* Support the situation when the latch block of outer loop 6123 could be from here. */ 6124 for (outer = loop_outer (current_loop_nest); 6125 outer; 6126 outer = loop_outer (outer)) 6127 if (considered_for_pipelining_p (outer) && outer->latch == bb) 6128 gcc_unreachable (); 6129 } 6130 6131 return false; 6132 } 6133 6134 /* Check whether JUMP_BB ends with a jump insn that leads only to DEST_BB and 6135 can be removed, making the corresponding edge fallthrough (assuming that 6136 all basic blocks between JUMP_BB and DEST_BB are empty). */ 6137 static bool 6138 bb_has_removable_jump_to_p (basic_block jump_bb, basic_block dest_bb) 6139 { 6140 if (!onlyjump_p (BB_END (jump_bb)) 6141 || tablejump_p (BB_END (jump_bb), NULL, NULL)) 6142 return false; 6143 6144 /* Several outgoing edges, abnormal edge or destination of jump is 6145 not DEST_BB. */ 6146 if (EDGE_COUNT (jump_bb->succs) != 1 6147 || EDGE_SUCC (jump_bb, 0)->flags & (EDGE_ABNORMAL | EDGE_CROSSING) 6148 || EDGE_SUCC (jump_bb, 0)->dest != dest_bb) 6149 return false; 6150 6151 /* If not anything of the upper. */ 6152 return true; 6153 } 6154 6155 /* Removes the loop preheader from the current region and saves it in 6156 PREHEADER_BLOCKS of the father loop, so they will be added later to 6157 region that represents an outer loop. */ 6158 static void 6159 sel_remove_loop_preheader (void) 6160 { 6161 int i, old_len; 6162 int cur_rgn = CONTAINING_RGN (BB_TO_BLOCK (0)); 6163 basic_block bb; 6164 bool all_empty_p = true; 6165 VEC(basic_block, heap) *preheader_blocks 6166 = LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest)); 6167 6168 gcc_assert (current_loop_nest); 6169 old_len = VEC_length (basic_block, preheader_blocks); 6170 6171 /* Add blocks that aren't within the current loop to PREHEADER_BLOCKS. */ 6172 for (i = 0; i < RGN_NR_BLOCKS (cur_rgn); i++) 6173 { 6174 bb = BASIC_BLOCK (BB_TO_BLOCK (i)); 6175 6176 /* If the basic block belongs to region, but doesn't belong to 6177 corresponding loop, then it should be a preheader. */ 6178 if (sel_is_loop_preheader_p (bb)) 6179 { 6180 VEC_safe_push (basic_block, heap, preheader_blocks, bb); 6181 if (BB_END (bb) != bb_note (bb)) 6182 all_empty_p = false; 6183 } 6184 } 6185 6186 /* Remove these blocks only after iterating over the whole region. */ 6187 for (i = VEC_length (basic_block, preheader_blocks) - 1; 6188 i >= old_len; 6189 i--) 6190 { 6191 bb = VEC_index (basic_block, preheader_blocks, i); 6192 sel_remove_bb (bb, false); 6193 } 6194 6195 if (!considered_for_pipelining_p (loop_outer (current_loop_nest))) 6196 { 6197 if (!all_empty_p) 6198 /* Immediately create new region from preheader. */ 6199 make_region_from_loop_preheader (&preheader_blocks); 6200 else 6201 { 6202 /* If all preheader blocks are empty - dont create new empty region. 6203 Instead, remove them completely. */ 6204 for (i = 0; VEC_iterate (basic_block, preheader_blocks, i, bb); i++) 6205 { 6206 edge e; 6207 edge_iterator ei; 6208 basic_block prev_bb = bb->prev_bb, next_bb = bb->next_bb; 6209 6210 /* Redirect all incoming edges to next basic block. */ 6211 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) 6212 { 6213 if (! (e->flags & EDGE_FALLTHRU)) 6214 redirect_edge_and_branch (e, bb->next_bb); 6215 else 6216 redirect_edge_succ (e, bb->next_bb); 6217 } 6218 gcc_assert (BB_NOTE_LIST (bb) == NULL); 6219 delete_and_free_basic_block (bb); 6220 6221 /* Check if after deleting preheader there is a nonconditional 6222 jump in PREV_BB that leads to the next basic block NEXT_BB. 6223 If it is so - delete this jump and clear data sets of its 6224 basic block if it becomes empty. */ 6225 if (next_bb->prev_bb == prev_bb 6226 && prev_bb != ENTRY_BLOCK_PTR 6227 && bb_has_removable_jump_to_p (prev_bb, next_bb)) 6228 { 6229 redirect_edge_and_branch (EDGE_SUCC (prev_bb, 0), next_bb); 6230 if (BB_END (prev_bb) == bb_note (prev_bb)) 6231 free_data_sets (prev_bb); 6232 } 6233 6234 set_immediate_dominator (CDI_DOMINATORS, next_bb, 6235 recompute_dominator (CDI_DOMINATORS, 6236 next_bb)); 6237 } 6238 } 6239 VEC_free (basic_block, heap, preheader_blocks); 6240 } 6241 else 6242 /* Store preheader within the father's loop structure. */ 6243 SET_LOOP_PREHEADER_BLOCKS (loop_outer (current_loop_nest), 6244 preheader_blocks); 6245 } 6246 #endif 6247