1 /* Swing Modulo Scheduling implementation. 2 Copyright (C) 2004-2016 Free Software Foundation, Inc. 3 Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 22 #include "config.h" 23 #include "system.h" 24 #include "coretypes.h" 25 #include "backend.h" 26 #include "target.h" 27 #include "rtl.h" 28 #include "tree.h" 29 #include "cfghooks.h" 30 #include "df.h" 31 #include "optabs.h" 32 #include "regs.h" 33 #include "emit-rtl.h" 34 #include "gcov-io.h" 35 #include "profile.h" 36 #include "insn-attr.h" 37 #include "cfgrtl.h" 38 #include "sched-int.h" 39 #include "cfgloop.h" 40 #include "expr.h" 41 #include "params.h" 42 #include "ddg.h" 43 #include "tree-pass.h" 44 #include "dbgcnt.h" 45 #include "loop-unroll.h" 46 47 #ifdef INSN_SCHEDULING 48 49 /* This file contains the implementation of the Swing Modulo Scheduler, 50 described in the following references: 51 [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt. 52 Lifetime--sensitive modulo scheduling in a production environment. 53 IEEE Trans. on Comps., 50(3), March 2001 54 [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero. 55 Swing Modulo Scheduling: A Lifetime Sensitive Approach. 56 PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA). 57 58 The basic structure is: 59 1. Build a data-dependence graph (DDG) for each loop. 60 2. Use the DDG to order the insns of a loop (not in topological order 61 necessarily, but rather) trying to place each insn after all its 62 predecessors _or_ after all its successors. 63 3. Compute MII: a lower bound on the number of cycles to schedule the loop. 64 4. Use the ordering to perform list-scheduling of the loop: 65 1. Set II = MII. We will try to schedule the loop within II cycles. 66 2. Try to schedule the insns one by one according to the ordering. 67 For each insn compute an interval of cycles by considering already- 68 scheduled preds and succs (and associated latencies); try to place 69 the insn in the cycles of this window checking for potential 70 resource conflicts (using the DFA interface). 71 Note: this is different from the cycle-scheduling of schedule_insns; 72 here the insns are not scheduled monotonically top-down (nor bottom- 73 up). 74 3. If failed in scheduling all insns - bump II++ and try again, unless 75 II reaches an upper bound MaxII, in which case report failure. 76 5. If we succeeded in scheduling the loop within II cycles, we now 77 generate prolog and epilog, decrease the counter of the loop, and 78 perform modulo variable expansion for live ranges that span more than 79 II cycles (i.e. use register copies to prevent a def from overwriting 80 itself before reaching the use). 81 82 SMS works with countable loops (1) whose control part can be easily 83 decoupled from the rest of the loop and (2) whose loop count can 84 be easily adjusted. This is because we peel a constant number of 85 iterations into a prologue and epilogue for which we want to avoid 86 emitting the control part, and a kernel which is to iterate that 87 constant number of iterations less than the original loop. So the 88 control part should be a set of insns clearly identified and having 89 its own iv, not otherwise used in the loop (at-least for now), which 90 initializes a register before the loop to the number of iterations. 91 Currently SMS relies on the do-loop pattern to recognize such loops, 92 where (1) the control part comprises of all insns defining and/or 93 using a certain 'count' register and (2) the loop count can be 94 adjusted by modifying this register prior to the loop. 95 TODO: Rely on cfgloop analysis instead. */ 96 97 /* This page defines partial-schedule structures and functions for 98 modulo scheduling. */ 99 100 typedef struct partial_schedule *partial_schedule_ptr; 101 typedef struct ps_insn *ps_insn_ptr; 102 103 /* The minimum (absolute) cycle that a node of ps was scheduled in. */ 104 #define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle) 105 106 /* The maximum (absolute) cycle that a node of ps was scheduled in. */ 107 #define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle) 108 109 /* Perform signed modulo, always returning a non-negative value. */ 110 #define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y)) 111 112 /* The number of different iterations the nodes in ps span, assuming 113 the stage boundaries are placed efficiently. */ 114 #define CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \ 115 + 1 + ii - 1) / ii) 116 /* The stage count of ps. */ 117 #define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count) 118 119 /* A single instruction in the partial schedule. */ 120 struct ps_insn 121 { 122 /* Identifies the instruction to be scheduled. Values smaller than 123 the ddg's num_nodes refer directly to ddg nodes. A value of 124 X - num_nodes refers to register move X. */ 125 int id; 126 127 /* The (absolute) cycle in which the PS instruction is scheduled. 128 Same as SCHED_TIME (node). */ 129 int cycle; 130 131 /* The next/prev PS_INSN in the same row. */ 132 ps_insn_ptr next_in_row, 133 prev_in_row; 134 135 }; 136 137 /* Information about a register move that has been added to a partial 138 schedule. */ 139 struct ps_reg_move_info 140 { 141 /* The source of the move is defined by the ps_insn with id DEF. 142 The destination is used by the ps_insns with the ids in USES. */ 143 int def; 144 sbitmap uses; 145 146 /* The original form of USES' instructions used OLD_REG, but they 147 should now use NEW_REG. */ 148 rtx old_reg; 149 rtx new_reg; 150 151 /* The number of consecutive stages that the move occupies. */ 152 int num_consecutive_stages; 153 154 /* An instruction that sets NEW_REG to the correct value. The first 155 move associated with DEF will have an rhs of OLD_REG; later moves 156 use the result of the previous move. */ 157 rtx_insn *insn; 158 }; 159 160 /* Holds the partial schedule as an array of II rows. Each entry of the 161 array points to a linked list of PS_INSNs, which represents the 162 instructions that are scheduled for that row. */ 163 struct partial_schedule 164 { 165 int ii; /* Number of rows in the partial schedule. */ 166 int history; /* Threshold for conflict checking using DFA. */ 167 168 /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii). */ 169 ps_insn_ptr *rows; 170 171 /* All the moves added for this partial schedule. Index X has 172 a ps_insn id of X + g->num_nodes. */ 173 vec<ps_reg_move_info> reg_moves; 174 175 /* rows_length[i] holds the number of instructions in the row. 176 It is used only (as an optimization) to back off quickly from 177 trying to schedule a node in a full row; that is, to avoid running 178 through futile DFA state transitions. */ 179 int *rows_length; 180 181 /* The earliest absolute cycle of an insn in the partial schedule. */ 182 int min_cycle; 183 184 /* The latest absolute cycle of an insn in the partial schedule. */ 185 int max_cycle; 186 187 ddg_ptr g; /* The DDG of the insns in the partial schedule. */ 188 189 int stage_count; /* The stage count of the partial schedule. */ 190 }; 191 192 193 static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history); 194 static void free_partial_schedule (partial_schedule_ptr); 195 static void reset_partial_schedule (partial_schedule_ptr, int new_ii); 196 void print_partial_schedule (partial_schedule_ptr, FILE *); 197 static void verify_partial_schedule (partial_schedule_ptr, sbitmap); 198 static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr, 199 int, int, sbitmap, sbitmap); 200 static void rotate_partial_schedule (partial_schedule_ptr, int); 201 void set_row_column_for_ps (partial_schedule_ptr); 202 static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap); 203 static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr); 204 205 206 /* This page defines constants and structures for the modulo scheduling 207 driver. */ 208 209 static int sms_order_nodes (ddg_ptr, int, int *, int *); 210 static void set_node_sched_params (ddg_ptr); 211 static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *); 212 static void permute_partial_schedule (partial_schedule_ptr, rtx_insn *); 213 static void generate_prolog_epilog (partial_schedule_ptr, struct loop *, 214 rtx, rtx); 215 static int calculate_stage_count (partial_schedule_ptr, int); 216 static void calculate_must_precede_follow (ddg_node_ptr, int, int, 217 int, int, sbitmap, sbitmap, sbitmap); 218 static int get_sched_window (partial_schedule_ptr, ddg_node_ptr, 219 sbitmap, int, int *, int *, int *); 220 static bool try_scheduling_node_in_cycle (partial_schedule_ptr, int, int, 221 sbitmap, int *, sbitmap, sbitmap); 222 static void remove_node_from_ps (partial_schedule_ptr, ps_insn_ptr); 223 224 #define NODE_ASAP(node) ((node)->aux.count) 225 226 #define SCHED_PARAMS(x) (&node_sched_param_vec[x]) 227 #define SCHED_TIME(x) (SCHED_PARAMS (x)->time) 228 #define SCHED_ROW(x) (SCHED_PARAMS (x)->row) 229 #define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage) 230 #define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column) 231 232 /* The scheduling parameters held for each node. */ 233 typedef struct node_sched_params 234 { 235 int time; /* The absolute scheduling cycle. */ 236 237 int row; /* Holds time % ii. */ 238 int stage; /* Holds time / ii. */ 239 240 /* The column of a node inside the ps. If nodes u, v are on the same row, 241 u will precede v if column (u) < column (v). */ 242 int column; 243 } *node_sched_params_ptr; 244 245 /* The following three functions are copied from the current scheduler 246 code in order to use sched_analyze() for computing the dependencies. 247 They are used when initializing the sched_info structure. */ 248 static const char * 249 sms_print_insn (const rtx_insn *insn, int aligned ATTRIBUTE_UNUSED) 250 { 251 static char tmp[80]; 252 253 sprintf (tmp, "i%4d", INSN_UID (insn)); 254 return tmp; 255 } 256 257 static void 258 compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED, 259 regset used ATTRIBUTE_UNUSED) 260 { 261 } 262 263 static struct common_sched_info_def sms_common_sched_info; 264 265 static struct sched_deps_info_def sms_sched_deps_info = 266 { 267 compute_jump_reg_dependencies, 268 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, 269 NULL, 270 0, 0, 0 271 }; 272 273 static struct haifa_sched_info sms_sched_info = 274 { 275 NULL, 276 NULL, 277 NULL, 278 NULL, 279 NULL, 280 sms_print_insn, 281 NULL, 282 NULL, /* insn_finishes_block_p */ 283 NULL, NULL, 284 NULL, NULL, 285 0, 0, 286 287 NULL, NULL, NULL, NULL, 288 NULL, NULL, 289 0 290 }; 291 292 /* Partial schedule instruction ID in PS is a register move. Return 293 information about it. */ 294 static struct ps_reg_move_info * 295 ps_reg_move (partial_schedule_ptr ps, int id) 296 { 297 gcc_checking_assert (id >= ps->g->num_nodes); 298 return &ps->reg_moves[id - ps->g->num_nodes]; 299 } 300 301 /* Return the rtl instruction that is being scheduled by partial schedule 302 instruction ID, which belongs to schedule PS. */ 303 static rtx_insn * 304 ps_rtl_insn (partial_schedule_ptr ps, int id) 305 { 306 if (id < ps->g->num_nodes) 307 return ps->g->nodes[id].insn; 308 else 309 return ps_reg_move (ps, id)->insn; 310 } 311 312 /* Partial schedule instruction ID, which belongs to PS, occurred in 313 the original (unscheduled) loop. Return the first instruction 314 in the loop that was associated with ps_rtl_insn (PS, ID). 315 If the instruction had some notes before it, this is the first 316 of those notes. */ 317 static rtx_insn * 318 ps_first_note (partial_schedule_ptr ps, int id) 319 { 320 gcc_assert (id < ps->g->num_nodes); 321 return ps->g->nodes[id].first_note; 322 } 323 324 /* Return the number of consecutive stages that are occupied by 325 partial schedule instruction ID in PS. */ 326 static int 327 ps_num_consecutive_stages (partial_schedule_ptr ps, int id) 328 { 329 if (id < ps->g->num_nodes) 330 return 1; 331 else 332 return ps_reg_move (ps, id)->num_consecutive_stages; 333 } 334 335 /* Given HEAD and TAIL which are the first and last insns in a loop; 336 return the register which controls the loop. Return zero if it has 337 more than one occurrence in the loop besides the control part or the 338 do-loop pattern is not of the form we expect. */ 339 static rtx 340 doloop_register_get (rtx_insn *head, rtx_insn *tail) 341 { 342 rtx reg, condition; 343 rtx_insn *insn, *first_insn_not_to_check; 344 345 if (!JUMP_P (tail)) 346 return NULL_RTX; 347 348 if (!targetm.code_for_doloop_end) 349 return NULL_RTX; 350 351 /* TODO: Free SMS's dependence on doloop_condition_get. */ 352 condition = doloop_condition_get (tail); 353 if (! condition) 354 return NULL_RTX; 355 356 if (REG_P (XEXP (condition, 0))) 357 reg = XEXP (condition, 0); 358 else if (GET_CODE (XEXP (condition, 0)) == PLUS 359 && REG_P (XEXP (XEXP (condition, 0), 0))) 360 reg = XEXP (XEXP (condition, 0), 0); 361 else 362 gcc_unreachable (); 363 364 /* Check that the COUNT_REG has no other occurrences in the loop 365 until the decrement. We assume the control part consists of 366 either a single (parallel) branch-on-count or a (non-parallel) 367 branch immediately preceded by a single (decrement) insn. */ 368 first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail 369 : prev_nondebug_insn (tail)); 370 371 for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn)) 372 if (!DEBUG_INSN_P (insn) && reg_mentioned_p (reg, insn)) 373 { 374 if (dump_file) 375 { 376 fprintf (dump_file, "SMS count_reg found "); 377 print_rtl_single (dump_file, reg); 378 fprintf (dump_file, " outside control in insn:\n"); 379 print_rtl_single (dump_file, insn); 380 } 381 382 return NULL_RTX; 383 } 384 385 return reg; 386 } 387 388 /* Check if COUNT_REG is set to a constant in the PRE_HEADER block, so 389 that the number of iterations is a compile-time constant. If so, 390 return the rtx_insn that sets COUNT_REG to a constant, and set COUNT to 391 this constant. Otherwise return 0. */ 392 static rtx_insn * 393 const_iteration_count (rtx count_reg, basic_block pre_header, 394 int64_t * count) 395 { 396 rtx_insn *insn; 397 rtx_insn *head, *tail; 398 399 if (! pre_header) 400 return NULL; 401 402 get_ebb_head_tail (pre_header, pre_header, &head, &tail); 403 404 for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn)) 405 if (NONDEBUG_INSN_P (insn) && single_set (insn) && 406 rtx_equal_p (count_reg, SET_DEST (single_set (insn)))) 407 { 408 rtx pat = single_set (insn); 409 410 if (CONST_INT_P (SET_SRC (pat))) 411 { 412 *count = INTVAL (SET_SRC (pat)); 413 return insn; 414 } 415 416 return NULL; 417 } 418 419 return NULL; 420 } 421 422 /* A very simple resource-based lower bound on the initiation interval. 423 ??? Improve the accuracy of this bound by considering the 424 utilization of various units. */ 425 static int 426 res_MII (ddg_ptr g) 427 { 428 if (targetm.sched.sms_res_mii) 429 return targetm.sched.sms_res_mii (g); 430 431 return ((g->num_nodes - g->num_debug) / issue_rate); 432 } 433 434 435 /* A vector that contains the sched data for each ps_insn. */ 436 static vec<node_sched_params> node_sched_param_vec; 437 438 /* Allocate sched_params for each node and initialize it. */ 439 static void 440 set_node_sched_params (ddg_ptr g) 441 { 442 node_sched_param_vec.truncate (0); 443 node_sched_param_vec.safe_grow_cleared (g->num_nodes); 444 } 445 446 /* Make sure that node_sched_param_vec has an entry for every move in PS. */ 447 static void 448 extend_node_sched_params (partial_schedule_ptr ps) 449 { 450 node_sched_param_vec.safe_grow_cleared (ps->g->num_nodes 451 + ps->reg_moves.length ()); 452 } 453 454 /* Update the sched_params (time, row and stage) for node U using the II, 455 the CYCLE of U and MIN_CYCLE. 456 We're not simply taking the following 457 SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii); 458 because the stages may not be aligned on cycle 0. */ 459 static void 460 update_node_sched_params (int u, int ii, int cycle, int min_cycle) 461 { 462 int sc_until_cycle_zero; 463 int stage; 464 465 SCHED_TIME (u) = cycle; 466 SCHED_ROW (u) = SMODULO (cycle, ii); 467 468 /* The calculation of stage count is done adding the number 469 of stages before cycle zero and after cycle zero. */ 470 sc_until_cycle_zero = CALC_STAGE_COUNT (-1, min_cycle, ii); 471 472 if (SCHED_TIME (u) < 0) 473 { 474 stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii); 475 SCHED_STAGE (u) = sc_until_cycle_zero - stage; 476 } 477 else 478 { 479 stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii); 480 SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1; 481 } 482 } 483 484 static void 485 print_node_sched_params (FILE *file, int num_nodes, partial_schedule_ptr ps) 486 { 487 int i; 488 489 if (! file) 490 return; 491 for (i = 0; i < num_nodes; i++) 492 { 493 node_sched_params_ptr nsp = SCHED_PARAMS (i); 494 495 fprintf (file, "Node = %d; INSN = %d\n", i, 496 INSN_UID (ps_rtl_insn (ps, i))); 497 fprintf (file, " asap = %d:\n", NODE_ASAP (&ps->g->nodes[i])); 498 fprintf (file, " time = %d:\n", nsp->time); 499 fprintf (file, " stage = %d:\n", nsp->stage); 500 } 501 } 502 503 /* Set SCHED_COLUMN for each instruction in row ROW of PS. */ 504 static void 505 set_columns_for_row (partial_schedule_ptr ps, int row) 506 { 507 ps_insn_ptr cur_insn; 508 int column; 509 510 column = 0; 511 for (cur_insn = ps->rows[row]; cur_insn; cur_insn = cur_insn->next_in_row) 512 SCHED_COLUMN (cur_insn->id) = column++; 513 } 514 515 /* Set SCHED_COLUMN for each instruction in PS. */ 516 static void 517 set_columns_for_ps (partial_schedule_ptr ps) 518 { 519 int row; 520 521 for (row = 0; row < ps->ii; row++) 522 set_columns_for_row (ps, row); 523 } 524 525 /* Try to schedule the move with ps_insn identifier I_REG_MOVE in PS. 526 Its single predecessor has already been scheduled, as has its 527 ddg node successors. (The move may have also another move as its 528 successor, in which case that successor will be scheduled later.) 529 530 The move is part of a chain that satisfies register dependencies 531 between a producing ddg node and various consuming ddg nodes. 532 If some of these dependencies have a distance of 1 (meaning that 533 the use is upward-exposed) then DISTANCE1_USES is nonnull and 534 contains the set of uses with distance-1 dependencies. 535 DISTANCE1_USES is null otherwise. 536 537 MUST_FOLLOW is a scratch bitmap that is big enough to hold 538 all current ps_insn ids. 539 540 Return true on success. */ 541 static bool 542 schedule_reg_move (partial_schedule_ptr ps, int i_reg_move, 543 sbitmap distance1_uses, sbitmap must_follow) 544 { 545 unsigned int u; 546 int this_time, this_distance, this_start, this_end, this_latency; 547 int start, end, c, ii; 548 sbitmap_iterator sbi; 549 ps_reg_move_info *move; 550 rtx_insn *this_insn; 551 ps_insn_ptr psi; 552 553 move = ps_reg_move (ps, i_reg_move); 554 ii = ps->ii; 555 if (dump_file) 556 { 557 fprintf (dump_file, "Scheduling register move INSN %d; ii = %d" 558 ", min cycle = %d\n\n", INSN_UID (move->insn), ii, 559 PS_MIN_CYCLE (ps)); 560 print_rtl_single (dump_file, move->insn); 561 fprintf (dump_file, "\n%11s %11s %5s\n", "start", "end", "time"); 562 fprintf (dump_file, "=========== =========== =====\n"); 563 } 564 565 start = INT_MIN; 566 end = INT_MAX; 567 568 /* For dependencies of distance 1 between a producer ddg node A 569 and consumer ddg node B, we have a chain of dependencies: 570 571 A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B 572 573 where Mi is the ith move. For dependencies of distance 0 between 574 a producer ddg node A and consumer ddg node C, we have a chain of 575 dependencies: 576 577 A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C 578 579 where Mi' occupies the same position as Mi but occurs a stage later. 580 We can only schedule each move once, so if we have both types of 581 chain, we model the second as: 582 583 A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C 584 585 First handle the dependencies between the previously-scheduled 586 predecessor and the move. */ 587 this_insn = ps_rtl_insn (ps, move->def); 588 this_latency = insn_latency (this_insn, move->insn); 589 this_distance = distance1_uses && move->def < ps->g->num_nodes ? 1 : 0; 590 this_time = SCHED_TIME (move->def) - this_distance * ii; 591 this_start = this_time + this_latency; 592 this_end = this_time + ii; 593 if (dump_file) 594 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n", 595 this_start, this_end, SCHED_TIME (move->def), 596 INSN_UID (this_insn), this_latency, this_distance, 597 INSN_UID (move->insn)); 598 599 if (start < this_start) 600 start = this_start; 601 if (end > this_end) 602 end = this_end; 603 604 /* Handle the dependencies between the move and previously-scheduled 605 successors. */ 606 EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, u, sbi) 607 { 608 this_insn = ps_rtl_insn (ps, u); 609 this_latency = insn_latency (move->insn, this_insn); 610 if (distance1_uses && !bitmap_bit_p (distance1_uses, u)) 611 this_distance = -1; 612 else 613 this_distance = 0; 614 this_time = SCHED_TIME (u) + this_distance * ii; 615 this_start = this_time - ii; 616 this_end = this_time - this_latency; 617 if (dump_file) 618 fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n", 619 this_start, this_end, SCHED_TIME (u), INSN_UID (move->insn), 620 this_latency, this_distance, INSN_UID (this_insn)); 621 622 if (start < this_start) 623 start = this_start; 624 if (end > this_end) 625 end = this_end; 626 } 627 628 if (dump_file) 629 { 630 fprintf (dump_file, "----------- ----------- -----\n"); 631 fprintf (dump_file, "%11d %11d %5s %s\n", start, end, "", "(max, min)"); 632 } 633 634 bitmap_clear (must_follow); 635 bitmap_set_bit (must_follow, move->def); 636 637 start = MAX (start, end - (ii - 1)); 638 for (c = end; c >= start; c--) 639 { 640 psi = ps_add_node_check_conflicts (ps, i_reg_move, c, 641 move->uses, must_follow); 642 if (psi) 643 { 644 update_node_sched_params (i_reg_move, ii, c, PS_MIN_CYCLE (ps)); 645 if (dump_file) 646 fprintf (dump_file, "\nScheduled register move INSN %d at" 647 " time %d, row %d\n\n", INSN_UID (move->insn), c, 648 SCHED_ROW (i_reg_move)); 649 return true; 650 } 651 } 652 653 if (dump_file) 654 fprintf (dump_file, "\nNo available slot\n\n"); 655 656 return false; 657 } 658 659 /* 660 Breaking intra-loop register anti-dependences: 661 Each intra-loop register anti-dependence implies a cross-iteration true 662 dependence of distance 1. Therefore, we can remove such false dependencies 663 and figure out if the partial schedule broke them by checking if (for a 664 true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and 665 if so generate a register move. The number of such moves is equal to: 666 SCHED_TIME (use) - SCHED_TIME (def) { 0 broken 667 nreg_moves = ----------------------------------- + 1 - { dependence. 668 ii { 1 if not. 669 */ 670 static bool 671 schedule_reg_moves (partial_schedule_ptr ps) 672 { 673 ddg_ptr g = ps->g; 674 int ii = ps->ii; 675 int i; 676 677 for (i = 0; i < g->num_nodes; i++) 678 { 679 ddg_node_ptr u = &g->nodes[i]; 680 ddg_edge_ptr e; 681 int nreg_moves = 0, i_reg_move; 682 rtx prev_reg, old_reg; 683 int first_move; 684 int distances[2]; 685 sbitmap must_follow; 686 sbitmap distance1_uses; 687 rtx set = single_set (u->insn); 688 689 /* Skip instructions that do not set a register. */ 690 if ((set && !REG_P (SET_DEST (set)))) 691 continue; 692 693 /* Compute the number of reg_moves needed for u, by looking at life 694 ranges started at u (excluding self-loops). */ 695 distances[0] = distances[1] = false; 696 for (e = u->out; e; e = e->next_out) 697 if (e->type == TRUE_DEP && e->dest != e->src) 698 { 699 int nreg_moves4e = (SCHED_TIME (e->dest->cuid) 700 - SCHED_TIME (e->src->cuid)) / ii; 701 702 if (e->distance == 1) 703 nreg_moves4e = (SCHED_TIME (e->dest->cuid) 704 - SCHED_TIME (e->src->cuid) + ii) / ii; 705 706 /* If dest precedes src in the schedule of the kernel, then dest 707 will read before src writes and we can save one reg_copy. */ 708 if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid) 709 && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid)) 710 nreg_moves4e--; 711 712 if (nreg_moves4e >= 1) 713 { 714 /* !single_set instructions are not supported yet and 715 thus we do not except to encounter them in the loop 716 except from the doloop part. For the latter case 717 we assume no regmoves are generated as the doloop 718 instructions are tied to the branch with an edge. */ 719 gcc_assert (set); 720 /* If the instruction contains auto-inc register then 721 validate that the regmov is being generated for the 722 target regsiter rather then the inc'ed register. */ 723 gcc_assert (!autoinc_var_is_used_p (u->insn, e->dest->insn)); 724 } 725 726 if (nreg_moves4e) 727 { 728 gcc_assert (e->distance < 2); 729 distances[e->distance] = true; 730 } 731 nreg_moves = MAX (nreg_moves, nreg_moves4e); 732 } 733 734 if (nreg_moves == 0) 735 continue; 736 737 /* Create NREG_MOVES register moves. */ 738 first_move = ps->reg_moves.length (); 739 ps->reg_moves.safe_grow_cleared (first_move + nreg_moves); 740 extend_node_sched_params (ps); 741 742 /* Record the moves associated with this node. */ 743 first_move += ps->g->num_nodes; 744 745 /* Generate each move. */ 746 old_reg = prev_reg = SET_DEST (single_set (u->insn)); 747 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++) 748 { 749 ps_reg_move_info *move = ps_reg_move (ps, first_move + i_reg_move); 750 751 move->def = i_reg_move > 0 ? first_move + i_reg_move - 1 : i; 752 move->uses = sbitmap_alloc (first_move + nreg_moves); 753 move->old_reg = old_reg; 754 move->new_reg = gen_reg_rtx (GET_MODE (prev_reg)); 755 move->num_consecutive_stages = distances[0] && distances[1] ? 2 : 1; 756 move->insn = gen_move_insn (move->new_reg, copy_rtx (prev_reg)); 757 bitmap_clear (move->uses); 758 759 prev_reg = move->new_reg; 760 } 761 762 distance1_uses = distances[1] ? sbitmap_alloc (g->num_nodes) : NULL; 763 764 if (distance1_uses) 765 bitmap_clear (distance1_uses); 766 767 /* Every use of the register defined by node may require a different 768 copy of this register, depending on the time the use is scheduled. 769 Record which uses require which move results. */ 770 for (e = u->out; e; e = e->next_out) 771 if (e->type == TRUE_DEP && e->dest != e->src) 772 { 773 int dest_copy = (SCHED_TIME (e->dest->cuid) 774 - SCHED_TIME (e->src->cuid)) / ii; 775 776 if (e->distance == 1) 777 dest_copy = (SCHED_TIME (e->dest->cuid) 778 - SCHED_TIME (e->src->cuid) + ii) / ii; 779 780 if (SCHED_ROW (e->dest->cuid) == SCHED_ROW (e->src->cuid) 781 && SCHED_COLUMN (e->dest->cuid) < SCHED_COLUMN (e->src->cuid)) 782 dest_copy--; 783 784 if (dest_copy) 785 { 786 ps_reg_move_info *move; 787 788 move = ps_reg_move (ps, first_move + dest_copy - 1); 789 bitmap_set_bit (move->uses, e->dest->cuid); 790 if (e->distance == 1) 791 bitmap_set_bit (distance1_uses, e->dest->cuid); 792 } 793 } 794 795 must_follow = sbitmap_alloc (first_move + nreg_moves); 796 for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++) 797 if (!schedule_reg_move (ps, first_move + i_reg_move, 798 distance1_uses, must_follow)) 799 break; 800 sbitmap_free (must_follow); 801 if (distance1_uses) 802 sbitmap_free (distance1_uses); 803 if (i_reg_move < nreg_moves) 804 return false; 805 } 806 return true; 807 } 808 809 /* Emit the moves associatied with PS. Apply the substitutions 810 associated with them. */ 811 static void 812 apply_reg_moves (partial_schedule_ptr ps) 813 { 814 ps_reg_move_info *move; 815 int i; 816 817 FOR_EACH_VEC_ELT (ps->reg_moves, i, move) 818 { 819 unsigned int i_use; 820 sbitmap_iterator sbi; 821 822 EXECUTE_IF_SET_IN_BITMAP (move->uses, 0, i_use, sbi) 823 { 824 replace_rtx (ps->g->nodes[i_use].insn, move->old_reg, move->new_reg); 825 df_insn_rescan (ps->g->nodes[i_use].insn); 826 } 827 } 828 } 829 830 /* Bump the SCHED_TIMEs of all nodes by AMOUNT. Set the values of 831 SCHED_ROW and SCHED_STAGE. Instruction scheduled on cycle AMOUNT 832 will move to cycle zero. */ 833 static void 834 reset_sched_times (partial_schedule_ptr ps, int amount) 835 { 836 int row; 837 int ii = ps->ii; 838 ps_insn_ptr crr_insn; 839 840 for (row = 0; row < ii; row++) 841 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row) 842 { 843 int u = crr_insn->id; 844 int normalized_time = SCHED_TIME (u) - amount; 845 int new_min_cycle = PS_MIN_CYCLE (ps) - amount; 846 847 if (dump_file) 848 { 849 /* Print the scheduling times after the rotation. */ 850 rtx_insn *insn = ps_rtl_insn (ps, u); 851 852 fprintf (dump_file, "crr_insn->node=%d (insn id %d), " 853 "crr_insn->cycle=%d, min_cycle=%d", u, 854 INSN_UID (insn), normalized_time, new_min_cycle); 855 if (JUMP_P (insn)) 856 fprintf (dump_file, " (branch)"); 857 fprintf (dump_file, "\n"); 858 } 859 860 gcc_assert (SCHED_TIME (u) >= ps->min_cycle); 861 gcc_assert (SCHED_TIME (u) <= ps->max_cycle); 862 863 crr_insn->cycle = normalized_time; 864 update_node_sched_params (u, ii, normalized_time, new_min_cycle); 865 } 866 } 867 868 /* Permute the insns according to their order in PS, from row 0 to 869 row ii-1, and position them right before LAST. This schedules 870 the insns of the loop kernel. */ 871 static void 872 permute_partial_schedule (partial_schedule_ptr ps, rtx_insn *last) 873 { 874 int ii = ps->ii; 875 int row; 876 ps_insn_ptr ps_ij; 877 878 for (row = 0; row < ii ; row++) 879 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row) 880 { 881 rtx_insn *insn = ps_rtl_insn (ps, ps_ij->id); 882 883 if (PREV_INSN (last) != insn) 884 { 885 if (ps_ij->id < ps->g->num_nodes) 886 reorder_insns_nobb (ps_first_note (ps, ps_ij->id), insn, 887 PREV_INSN (last)); 888 else 889 add_insn_before (insn, last, NULL); 890 } 891 } 892 } 893 894 /* Set bitmaps TMP_FOLLOW and TMP_PRECEDE to MUST_FOLLOW and MUST_PRECEDE 895 respectively only if cycle C falls on the border of the scheduling 896 window boundaries marked by START and END cycles. STEP is the 897 direction of the window. */ 898 static inline void 899 set_must_precede_follow (sbitmap *tmp_follow, sbitmap must_follow, 900 sbitmap *tmp_precede, sbitmap must_precede, int c, 901 int start, int end, int step) 902 { 903 *tmp_precede = NULL; 904 *tmp_follow = NULL; 905 906 if (c == start) 907 { 908 if (step == 1) 909 *tmp_precede = must_precede; 910 else /* step == -1. */ 911 *tmp_follow = must_follow; 912 } 913 if (c == end - step) 914 { 915 if (step == 1) 916 *tmp_follow = must_follow; 917 else /* step == -1. */ 918 *tmp_precede = must_precede; 919 } 920 921 } 922 923 /* Return True if the branch can be moved to row ii-1 while 924 normalizing the partial schedule PS to start from cycle zero and thus 925 optimize the SC. Otherwise return False. */ 926 static bool 927 optimize_sc (partial_schedule_ptr ps, ddg_ptr g) 928 { 929 int amount = PS_MIN_CYCLE (ps); 930 sbitmap sched_nodes = sbitmap_alloc (g->num_nodes); 931 int start, end, step; 932 int ii = ps->ii; 933 bool ok = false; 934 int stage_count, stage_count_curr; 935 936 /* Compare the SC after normalization and SC after bringing the branch 937 to row ii-1. If they are equal just bail out. */ 938 stage_count = calculate_stage_count (ps, amount); 939 stage_count_curr = 940 calculate_stage_count (ps, SCHED_TIME (g->closing_branch->cuid) - (ii - 1)); 941 942 if (stage_count == stage_count_curr) 943 { 944 if (dump_file) 945 fprintf (dump_file, "SMS SC already optimized.\n"); 946 947 ok = false; 948 goto clear; 949 } 950 951 if (dump_file) 952 { 953 fprintf (dump_file, "SMS Trying to optimize branch location\n"); 954 fprintf (dump_file, "SMS partial schedule before trial:\n"); 955 print_partial_schedule (ps, dump_file); 956 } 957 958 /* First, normalize the partial scheduling. */ 959 reset_sched_times (ps, amount); 960 rotate_partial_schedule (ps, amount); 961 if (dump_file) 962 { 963 fprintf (dump_file, 964 "SMS partial schedule after normalization (ii, %d, SC %d):\n", 965 ii, stage_count); 966 print_partial_schedule (ps, dump_file); 967 } 968 969 if (SMODULO (SCHED_TIME (g->closing_branch->cuid), ii) == ii - 1) 970 { 971 ok = true; 972 goto clear; 973 } 974 975 bitmap_ones (sched_nodes); 976 977 /* Calculate the new placement of the branch. It should be in row 978 ii-1 and fall into it's scheduling window. */ 979 if (get_sched_window (ps, g->closing_branch, sched_nodes, ii, &start, 980 &step, &end) == 0) 981 { 982 bool success; 983 ps_insn_ptr next_ps_i; 984 int branch_cycle = SCHED_TIME (g->closing_branch->cuid); 985 int row = SMODULO (branch_cycle, ps->ii); 986 int num_splits = 0; 987 sbitmap must_precede, must_follow, tmp_precede, tmp_follow; 988 int min_cycle, c; 989 990 if (dump_file) 991 fprintf (dump_file, "\nTrying to schedule node %d " 992 "INSN = %d in (%d .. %d) step %d\n", 993 g->closing_branch->cuid, 994 (INSN_UID (g->closing_branch->insn)), start, end, step); 995 996 gcc_assert ((step > 0 && start < end) || (step < 0 && start > end)); 997 if (step == 1) 998 { 999 c = start + ii - SMODULO (start, ii) - 1; 1000 gcc_assert (c >= start); 1001 if (c >= end) 1002 { 1003 ok = false; 1004 if (dump_file) 1005 fprintf (dump_file, 1006 "SMS failed to schedule branch at cycle: %d\n", c); 1007 goto clear; 1008 } 1009 } 1010 else 1011 { 1012 c = start - SMODULO (start, ii) - 1; 1013 gcc_assert (c <= start); 1014 1015 if (c <= end) 1016 { 1017 if (dump_file) 1018 fprintf (dump_file, 1019 "SMS failed to schedule branch at cycle: %d\n", c); 1020 ok = false; 1021 goto clear; 1022 } 1023 } 1024 1025 must_precede = sbitmap_alloc (g->num_nodes); 1026 must_follow = sbitmap_alloc (g->num_nodes); 1027 1028 /* Try to schedule the branch is it's new cycle. */ 1029 calculate_must_precede_follow (g->closing_branch, start, end, 1030 step, ii, sched_nodes, 1031 must_precede, must_follow); 1032 1033 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede, 1034 must_precede, c, start, end, step); 1035 1036 /* Find the element in the partial schedule related to the closing 1037 branch so we can remove it from it's current cycle. */ 1038 for (next_ps_i = ps->rows[row]; 1039 next_ps_i; next_ps_i = next_ps_i->next_in_row) 1040 if (next_ps_i->id == g->closing_branch->cuid) 1041 break; 1042 1043 min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii); 1044 remove_node_from_ps (ps, next_ps_i); 1045 success = 1046 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid, c, 1047 sched_nodes, &num_splits, 1048 tmp_precede, tmp_follow); 1049 gcc_assert (num_splits == 0); 1050 if (!success) 1051 { 1052 if (dump_file) 1053 fprintf (dump_file, 1054 "SMS failed to schedule branch at cycle: %d, " 1055 "bringing it back to cycle %d\n", c, branch_cycle); 1056 1057 /* The branch was failed to be placed in row ii - 1. 1058 Put it back in it's original place in the partial 1059 schedualing. */ 1060 set_must_precede_follow (&tmp_follow, must_follow, &tmp_precede, 1061 must_precede, branch_cycle, start, end, 1062 step); 1063 success = 1064 try_scheduling_node_in_cycle (ps, g->closing_branch->cuid, 1065 branch_cycle, sched_nodes, 1066 &num_splits, tmp_precede, 1067 tmp_follow); 1068 gcc_assert (success && (num_splits == 0)); 1069 ok = false; 1070 } 1071 else 1072 { 1073 /* The branch is placed in row ii - 1. */ 1074 if (dump_file) 1075 fprintf (dump_file, 1076 "SMS success in moving branch to cycle %d\n", c); 1077 1078 update_node_sched_params (g->closing_branch->cuid, ii, c, 1079 PS_MIN_CYCLE (ps)); 1080 ok = true; 1081 } 1082 1083 /* This might have been added to a new first stage. */ 1084 if (PS_MIN_CYCLE (ps) < min_cycle) 1085 reset_sched_times (ps, 0); 1086 1087 free (must_precede); 1088 free (must_follow); 1089 } 1090 1091 clear: 1092 free (sched_nodes); 1093 return ok; 1094 } 1095 1096 static void 1097 duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage, 1098 int to_stage, rtx count_reg) 1099 { 1100 int row; 1101 ps_insn_ptr ps_ij; 1102 1103 for (row = 0; row < ps->ii; row++) 1104 for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row) 1105 { 1106 int u = ps_ij->id; 1107 int first_u, last_u; 1108 rtx_insn *u_insn; 1109 1110 /* Do not duplicate any insn which refers to count_reg as it 1111 belongs to the control part. 1112 The closing branch is scheduled as well and thus should 1113 be ignored. 1114 TODO: This should be done by analyzing the control part of 1115 the loop. */ 1116 u_insn = ps_rtl_insn (ps, u); 1117 if (reg_mentioned_p (count_reg, u_insn) 1118 || JUMP_P (u_insn)) 1119 continue; 1120 1121 first_u = SCHED_STAGE (u); 1122 last_u = first_u + ps_num_consecutive_stages (ps, u) - 1; 1123 if (from_stage <= last_u && to_stage >= first_u) 1124 { 1125 if (u < ps->g->num_nodes) 1126 duplicate_insn_chain (ps_first_note (ps, u), u_insn); 1127 else 1128 emit_insn (copy_rtx (PATTERN (u_insn))); 1129 } 1130 } 1131 } 1132 1133 1134 /* Generate the instructions (including reg_moves) for prolog & epilog. */ 1135 static void 1136 generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop, 1137 rtx count_reg, rtx count_init) 1138 { 1139 int i; 1140 int last_stage = PS_STAGE_COUNT (ps) - 1; 1141 edge e; 1142 1143 /* Generate the prolog, inserting its insns on the loop-entry edge. */ 1144 start_sequence (); 1145 1146 if (!count_init) 1147 { 1148 /* Generate instructions at the beginning of the prolog to 1149 adjust the loop count by STAGE_COUNT. If loop count is constant 1150 (count_init), this constant is adjusted by STAGE_COUNT in 1151 generate_prolog_epilog function. */ 1152 rtx sub_reg = NULL_RTX; 1153 1154 sub_reg = expand_simple_binop (GET_MODE (count_reg), MINUS, count_reg, 1155 gen_int_mode (last_stage, 1156 GET_MODE (count_reg)), 1157 count_reg, 1, OPTAB_DIRECT); 1158 gcc_assert (REG_P (sub_reg)); 1159 if (REGNO (sub_reg) != REGNO (count_reg)) 1160 emit_move_insn (count_reg, sub_reg); 1161 } 1162 1163 for (i = 0; i < last_stage; i++) 1164 duplicate_insns_of_cycles (ps, 0, i, count_reg); 1165 1166 /* Put the prolog on the entry edge. */ 1167 e = loop_preheader_edge (loop); 1168 split_edge_and_insert (e, get_insns ()); 1169 if (!flag_resched_modulo_sched) 1170 e->dest->flags |= BB_DISABLE_SCHEDULE; 1171 1172 end_sequence (); 1173 1174 /* Generate the epilog, inserting its insns on the loop-exit edge. */ 1175 start_sequence (); 1176 1177 for (i = 0; i < last_stage; i++) 1178 duplicate_insns_of_cycles (ps, i + 1, last_stage, count_reg); 1179 1180 /* Put the epilogue on the exit edge. */ 1181 gcc_assert (single_exit (loop)); 1182 e = single_exit (loop); 1183 split_edge_and_insert (e, get_insns ()); 1184 if (!flag_resched_modulo_sched) 1185 e->dest->flags |= BB_DISABLE_SCHEDULE; 1186 1187 end_sequence (); 1188 } 1189 1190 /* Mark LOOP as software pipelined so the later 1191 scheduling passes don't touch it. */ 1192 static void 1193 mark_loop_unsched (struct loop *loop) 1194 { 1195 unsigned i; 1196 basic_block *bbs = get_loop_body (loop); 1197 1198 for (i = 0; i < loop->num_nodes; i++) 1199 bbs[i]->flags |= BB_DISABLE_SCHEDULE; 1200 1201 free (bbs); 1202 } 1203 1204 /* Return true if all the BBs of the loop are empty except the 1205 loop header. */ 1206 static bool 1207 loop_single_full_bb_p (struct loop *loop) 1208 { 1209 unsigned i; 1210 basic_block *bbs = get_loop_body (loop); 1211 1212 for (i = 0; i < loop->num_nodes ; i++) 1213 { 1214 rtx_insn *head, *tail; 1215 bool empty_bb = true; 1216 1217 if (bbs[i] == loop->header) 1218 continue; 1219 1220 /* Make sure that basic blocks other than the header 1221 have only notes labels or jumps. */ 1222 get_ebb_head_tail (bbs[i], bbs[i], &head, &tail); 1223 for (; head != NEXT_INSN (tail); head = NEXT_INSN (head)) 1224 { 1225 if (NOTE_P (head) || LABEL_P (head) 1226 || (INSN_P (head) && (DEBUG_INSN_P (head) || JUMP_P (head)))) 1227 continue; 1228 empty_bb = false; 1229 break; 1230 } 1231 1232 if (! empty_bb) 1233 { 1234 free (bbs); 1235 return false; 1236 } 1237 } 1238 free (bbs); 1239 return true; 1240 } 1241 1242 /* Dump file:line from INSN's location info to dump_file. */ 1243 1244 static void 1245 dump_insn_location (rtx_insn *insn) 1246 { 1247 if (dump_file && INSN_HAS_LOCATION (insn)) 1248 { 1249 expanded_location xloc = insn_location (insn); 1250 fprintf (dump_file, " %s:%i", xloc.file, xloc.line); 1251 } 1252 } 1253 1254 /* A simple loop from SMS point of view; it is a loop that is composed of 1255 either a single basic block or two BBs - a header and a latch. */ 1256 #define SIMPLE_SMS_LOOP_P(loop) ((loop->num_nodes < 3 ) \ 1257 && (EDGE_COUNT (loop->latch->preds) == 1) \ 1258 && (EDGE_COUNT (loop->latch->succs) == 1)) 1259 1260 /* Return true if the loop is in its canonical form and false if not. 1261 i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit. */ 1262 static bool 1263 loop_canon_p (struct loop *loop) 1264 { 1265 1266 if (loop->inner || !loop_outer (loop)) 1267 { 1268 if (dump_file) 1269 fprintf (dump_file, "SMS loop inner or !loop_outer\n"); 1270 return false; 1271 } 1272 1273 if (!single_exit (loop)) 1274 { 1275 if (dump_file) 1276 { 1277 rtx_insn *insn = BB_END (loop->header); 1278 1279 fprintf (dump_file, "SMS loop many exits"); 1280 dump_insn_location (insn); 1281 fprintf (dump_file, "\n"); 1282 } 1283 return false; 1284 } 1285 1286 if (! SIMPLE_SMS_LOOP_P (loop) && ! loop_single_full_bb_p (loop)) 1287 { 1288 if (dump_file) 1289 { 1290 rtx_insn *insn = BB_END (loop->header); 1291 1292 fprintf (dump_file, "SMS loop many BBs."); 1293 dump_insn_location (insn); 1294 fprintf (dump_file, "\n"); 1295 } 1296 return false; 1297 } 1298 1299 return true; 1300 } 1301 1302 /* If there are more than one entry for the loop, 1303 make it one by splitting the first entry edge and 1304 redirecting the others to the new BB. */ 1305 static void 1306 canon_loop (struct loop *loop) 1307 { 1308 edge e; 1309 edge_iterator i; 1310 1311 /* Avoid annoying special cases of edges going to exit 1312 block. */ 1313 FOR_EACH_EDGE (e, i, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds) 1314 if ((e->flags & EDGE_FALLTHRU) && (EDGE_COUNT (e->src->succs) > 1)) 1315 split_edge (e); 1316 1317 if (loop->latch == loop->header 1318 || EDGE_COUNT (loop->latch->succs) > 1) 1319 { 1320 FOR_EACH_EDGE (e, i, loop->header->preds) 1321 if (e->src == loop->latch) 1322 break; 1323 split_edge (e); 1324 } 1325 } 1326 1327 /* Setup infos. */ 1328 static void 1329 setup_sched_infos (void) 1330 { 1331 memcpy (&sms_common_sched_info, &haifa_common_sched_info, 1332 sizeof (sms_common_sched_info)); 1333 sms_common_sched_info.sched_pass_id = SCHED_SMS_PASS; 1334 common_sched_info = &sms_common_sched_info; 1335 1336 sched_deps_info = &sms_sched_deps_info; 1337 current_sched_info = &sms_sched_info; 1338 } 1339 1340 /* Probability in % that the sms-ed loop rolls enough so that optimized 1341 version may be entered. Just a guess. */ 1342 #define PROB_SMS_ENOUGH_ITERATIONS 80 1343 1344 /* Used to calculate the upper bound of ii. */ 1345 #define MAXII_FACTOR 2 1346 1347 /* Main entry point, perform SMS scheduling on the loops of the function 1348 that consist of single basic blocks. */ 1349 static void 1350 sms_schedule (void) 1351 { 1352 rtx_insn *insn; 1353 ddg_ptr *g_arr, g; 1354 int * node_order; 1355 int maxii, max_asap; 1356 partial_schedule_ptr ps; 1357 basic_block bb = NULL; 1358 struct loop *loop; 1359 basic_block condition_bb = NULL; 1360 edge latch_edge; 1361 gcov_type trip_count = 0; 1362 1363 loop_optimizer_init (LOOPS_HAVE_PREHEADERS 1364 | LOOPS_HAVE_RECORDED_EXITS); 1365 if (number_of_loops (cfun) <= 1) 1366 { 1367 loop_optimizer_finalize (); 1368 return; /* There are no loops to schedule. */ 1369 } 1370 1371 /* Initialize issue_rate. */ 1372 if (targetm.sched.issue_rate) 1373 { 1374 int temp = reload_completed; 1375 1376 reload_completed = 1; 1377 issue_rate = targetm.sched.issue_rate (); 1378 reload_completed = temp; 1379 } 1380 else 1381 issue_rate = 1; 1382 1383 /* Initialize the scheduler. */ 1384 setup_sched_infos (); 1385 haifa_sched_init (); 1386 1387 /* Allocate memory to hold the DDG array one entry for each loop. 1388 We use loop->num as index into this array. */ 1389 g_arr = XCNEWVEC (ddg_ptr, number_of_loops (cfun)); 1390 1391 if (dump_file) 1392 { 1393 fprintf (dump_file, "\n\nSMS analysis phase\n"); 1394 fprintf (dump_file, "===================\n\n"); 1395 } 1396 1397 /* Build DDGs for all the relevant loops and hold them in G_ARR 1398 indexed by the loop index. */ 1399 FOR_EACH_LOOP (loop, 0) 1400 { 1401 rtx_insn *head, *tail; 1402 rtx count_reg; 1403 1404 /* For debugging. */ 1405 if (dbg_cnt (sms_sched_loop) == false) 1406 { 1407 if (dump_file) 1408 fprintf (dump_file, "SMS reached max limit... \n"); 1409 1410 break; 1411 } 1412 1413 if (dump_file) 1414 { 1415 rtx_insn *insn = BB_END (loop->header); 1416 1417 fprintf (dump_file, "SMS loop num: %d", loop->num); 1418 dump_insn_location (insn); 1419 fprintf (dump_file, "\n"); 1420 } 1421 1422 if (! loop_canon_p (loop)) 1423 continue; 1424 1425 if (! loop_single_full_bb_p (loop)) 1426 { 1427 if (dump_file) 1428 fprintf (dump_file, "SMS not loop_single_full_bb_p\n"); 1429 continue; 1430 } 1431 1432 bb = loop->header; 1433 1434 get_ebb_head_tail (bb, bb, &head, &tail); 1435 latch_edge = loop_latch_edge (loop); 1436 gcc_assert (single_exit (loop)); 1437 if (single_exit (loop)->count) 1438 trip_count = latch_edge->count / single_exit (loop)->count; 1439 1440 /* Perform SMS only on loops that their average count is above threshold. */ 1441 1442 if ( latch_edge->count 1443 && (latch_edge->count < single_exit (loop)->count * SMS_LOOP_AVERAGE_COUNT_THRESHOLD)) 1444 { 1445 if (dump_file) 1446 { 1447 dump_insn_location (tail); 1448 fprintf (dump_file, "\nSMS single-bb-loop\n"); 1449 if (profile_info && flag_branch_probabilities) 1450 { 1451 fprintf (dump_file, "SMS loop-count "); 1452 fprintf (dump_file, "%" PRId64, 1453 (int64_t) bb->count); 1454 fprintf (dump_file, "\n"); 1455 fprintf (dump_file, "SMS trip-count "); 1456 fprintf (dump_file, "%" PRId64, 1457 (int64_t) trip_count); 1458 fprintf (dump_file, "\n"); 1459 fprintf (dump_file, "SMS profile-sum-max "); 1460 fprintf (dump_file, "%" PRId64, 1461 (int64_t) profile_info->sum_max); 1462 fprintf (dump_file, "\n"); 1463 } 1464 } 1465 continue; 1466 } 1467 1468 /* Make sure this is a doloop. */ 1469 if ( !(count_reg = doloop_register_get (head, tail))) 1470 { 1471 if (dump_file) 1472 fprintf (dump_file, "SMS doloop_register_get failed\n"); 1473 continue; 1474 } 1475 1476 /* Don't handle BBs with calls or barriers 1477 or !single_set with the exception of instructions that include 1478 count_reg---these instructions are part of the control part 1479 that do-loop recognizes. 1480 ??? Should handle insns defining subregs. */ 1481 for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn)) 1482 { 1483 rtx set; 1484 1485 if (CALL_P (insn) 1486 || BARRIER_P (insn) 1487 || (NONDEBUG_INSN_P (insn) && !JUMP_P (insn) 1488 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE 1489 && !reg_mentioned_p (count_reg, insn)) 1490 || (INSN_P (insn) && (set = single_set (insn)) 1491 && GET_CODE (SET_DEST (set)) == SUBREG)) 1492 break; 1493 } 1494 1495 if (insn != NEXT_INSN (tail)) 1496 { 1497 if (dump_file) 1498 { 1499 if (CALL_P (insn)) 1500 fprintf (dump_file, "SMS loop-with-call\n"); 1501 else if (BARRIER_P (insn)) 1502 fprintf (dump_file, "SMS loop-with-barrier\n"); 1503 else if ((NONDEBUG_INSN_P (insn) && !JUMP_P (insn) 1504 && !single_set (insn) && GET_CODE (PATTERN (insn)) != USE)) 1505 fprintf (dump_file, "SMS loop-with-not-single-set\n"); 1506 else 1507 fprintf (dump_file, "SMS loop with subreg in lhs\n"); 1508 print_rtl_single (dump_file, insn); 1509 } 1510 1511 continue; 1512 } 1513 1514 /* Always schedule the closing branch with the rest of the 1515 instructions. The branch is rotated to be in row ii-1 at the 1516 end of the scheduling procedure to make sure it's the last 1517 instruction in the iteration. */ 1518 if (! (g = create_ddg (bb, 1))) 1519 { 1520 if (dump_file) 1521 fprintf (dump_file, "SMS create_ddg failed\n"); 1522 continue; 1523 } 1524 1525 g_arr[loop->num] = g; 1526 if (dump_file) 1527 fprintf (dump_file, "...OK\n"); 1528 1529 } 1530 if (dump_file) 1531 { 1532 fprintf (dump_file, "\nSMS transformation phase\n"); 1533 fprintf (dump_file, "=========================\n\n"); 1534 } 1535 1536 /* We don't want to perform SMS on new loops - created by versioning. */ 1537 FOR_EACH_LOOP (loop, 0) 1538 { 1539 rtx_insn *head, *tail; 1540 rtx count_reg; 1541 rtx_insn *count_init; 1542 int mii, rec_mii, stage_count, min_cycle; 1543 int64_t loop_count = 0; 1544 bool opt_sc_p; 1545 1546 if (! (g = g_arr[loop->num])) 1547 continue; 1548 1549 if (dump_file) 1550 { 1551 rtx_insn *insn = BB_END (loop->header); 1552 1553 fprintf (dump_file, "SMS loop num: %d", loop->num); 1554 dump_insn_location (insn); 1555 fprintf (dump_file, "\n"); 1556 1557 print_ddg (dump_file, g); 1558 } 1559 1560 get_ebb_head_tail (loop->header, loop->header, &head, &tail); 1561 1562 latch_edge = loop_latch_edge (loop); 1563 gcc_assert (single_exit (loop)); 1564 if (single_exit (loop)->count) 1565 trip_count = latch_edge->count / single_exit (loop)->count; 1566 1567 if (dump_file) 1568 { 1569 dump_insn_location (tail); 1570 fprintf (dump_file, "\nSMS single-bb-loop\n"); 1571 if (profile_info && flag_branch_probabilities) 1572 { 1573 fprintf (dump_file, "SMS loop-count "); 1574 fprintf (dump_file, "%" PRId64, 1575 (int64_t) bb->count); 1576 fprintf (dump_file, "\n"); 1577 fprintf (dump_file, "SMS profile-sum-max "); 1578 fprintf (dump_file, "%" PRId64, 1579 (int64_t) profile_info->sum_max); 1580 fprintf (dump_file, "\n"); 1581 } 1582 fprintf (dump_file, "SMS doloop\n"); 1583 fprintf (dump_file, "SMS built-ddg %d\n", g->num_nodes); 1584 fprintf (dump_file, "SMS num-loads %d\n", g->num_loads); 1585 fprintf (dump_file, "SMS num-stores %d\n", g->num_stores); 1586 } 1587 1588 1589 /* In case of th loop have doloop register it gets special 1590 handling. */ 1591 count_init = NULL; 1592 if ((count_reg = doloop_register_get (head, tail))) 1593 { 1594 basic_block pre_header; 1595 1596 pre_header = loop_preheader_edge (loop)->src; 1597 count_init = const_iteration_count (count_reg, pre_header, 1598 &loop_count); 1599 } 1600 gcc_assert (count_reg); 1601 1602 if (dump_file && count_init) 1603 { 1604 fprintf (dump_file, "SMS const-doloop "); 1605 fprintf (dump_file, "%" PRId64, 1606 loop_count); 1607 fprintf (dump_file, "\n"); 1608 } 1609 1610 node_order = XNEWVEC (int, g->num_nodes); 1611 1612 mii = 1; /* Need to pass some estimate of mii. */ 1613 rec_mii = sms_order_nodes (g, mii, node_order, &max_asap); 1614 mii = MAX (res_MII (g), rec_mii); 1615 maxii = MAX (max_asap, MAXII_FACTOR * mii); 1616 1617 if (dump_file) 1618 fprintf (dump_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n", 1619 rec_mii, mii, maxii); 1620 1621 for (;;) 1622 { 1623 set_node_sched_params (g); 1624 1625 stage_count = 0; 1626 opt_sc_p = false; 1627 ps = sms_schedule_by_order (g, mii, maxii, node_order); 1628 1629 if (ps) 1630 { 1631 /* Try to achieve optimized SC by normalizing the partial 1632 schedule (having the cycles start from cycle zero). 1633 The branch location must be placed in row ii-1 in the 1634 final scheduling. If failed, shift all instructions to 1635 position the branch in row ii-1. */ 1636 opt_sc_p = optimize_sc (ps, g); 1637 if (opt_sc_p) 1638 stage_count = calculate_stage_count (ps, 0); 1639 else 1640 { 1641 /* Bring the branch to cycle ii-1. */ 1642 int amount = (SCHED_TIME (g->closing_branch->cuid) 1643 - (ps->ii - 1)); 1644 1645 if (dump_file) 1646 fprintf (dump_file, "SMS schedule branch at cycle ii-1\n"); 1647 1648 stage_count = calculate_stage_count (ps, amount); 1649 } 1650 1651 gcc_assert (stage_count >= 1); 1652 } 1653 1654 /* The default value of PARAM_SMS_MIN_SC is 2 as stage count of 1655 1 means that there is no interleaving between iterations thus 1656 we let the scheduling passes do the job in this case. */ 1657 if (stage_count < PARAM_VALUE (PARAM_SMS_MIN_SC) 1658 || (count_init && (loop_count <= stage_count)) 1659 || (flag_branch_probabilities && (trip_count <= stage_count))) 1660 { 1661 if (dump_file) 1662 { 1663 fprintf (dump_file, "SMS failed... \n"); 1664 fprintf (dump_file, "SMS sched-failed (stage-count=%d," 1665 " loop-count=", stage_count); 1666 fprintf (dump_file, "%" PRId64, loop_count); 1667 fprintf (dump_file, ", trip-count="); 1668 fprintf (dump_file, "%" PRId64, trip_count); 1669 fprintf (dump_file, ")\n"); 1670 } 1671 break; 1672 } 1673 1674 if (!opt_sc_p) 1675 { 1676 /* Rotate the partial schedule to have the branch in row ii-1. */ 1677 int amount = SCHED_TIME (g->closing_branch->cuid) - (ps->ii - 1); 1678 1679 reset_sched_times (ps, amount); 1680 rotate_partial_schedule (ps, amount); 1681 } 1682 1683 set_columns_for_ps (ps); 1684 1685 min_cycle = PS_MIN_CYCLE (ps) - SMODULO (PS_MIN_CYCLE (ps), ps->ii); 1686 if (!schedule_reg_moves (ps)) 1687 { 1688 mii = ps->ii + 1; 1689 free_partial_schedule (ps); 1690 continue; 1691 } 1692 1693 /* Moves that handle incoming values might have been added 1694 to a new first stage. Bump the stage count if so. 1695 1696 ??? Perhaps we could consider rotating the schedule here 1697 instead? */ 1698 if (PS_MIN_CYCLE (ps) < min_cycle) 1699 { 1700 reset_sched_times (ps, 0); 1701 stage_count++; 1702 } 1703 1704 /* The stage count should now be correct without rotation. */ 1705 gcc_checking_assert (stage_count == calculate_stage_count (ps, 0)); 1706 PS_STAGE_COUNT (ps) = stage_count; 1707 1708 canon_loop (loop); 1709 1710 if (dump_file) 1711 { 1712 dump_insn_location (tail); 1713 fprintf (dump_file, " SMS succeeded %d %d (with ii, sc)\n", 1714 ps->ii, stage_count); 1715 print_partial_schedule (ps, dump_file); 1716 } 1717 1718 /* case the BCT count is not known , Do loop-versioning */ 1719 if (count_reg && ! count_init) 1720 { 1721 rtx comp_rtx = gen_rtx_GT (VOIDmode, count_reg, 1722 gen_int_mode (stage_count, 1723 GET_MODE (count_reg))); 1724 unsigned prob = (PROB_SMS_ENOUGH_ITERATIONS 1725 * REG_BR_PROB_BASE) / 100; 1726 1727 loop_version (loop, comp_rtx, &condition_bb, 1728 prob, prob, REG_BR_PROB_BASE - prob, 1729 true); 1730 } 1731 1732 /* Set new iteration count of loop kernel. */ 1733 if (count_reg && count_init) 1734 SET_SRC (single_set (count_init)) = GEN_INT (loop_count 1735 - stage_count + 1); 1736 1737 /* Now apply the scheduled kernel to the RTL of the loop. */ 1738 permute_partial_schedule (ps, g->closing_branch->first_note); 1739 1740 /* Mark this loop as software pipelined so the later 1741 scheduling passes don't touch it. */ 1742 if (! flag_resched_modulo_sched) 1743 mark_loop_unsched (loop); 1744 1745 /* The life-info is not valid any more. */ 1746 df_set_bb_dirty (g->bb); 1747 1748 apply_reg_moves (ps); 1749 if (dump_file) 1750 print_node_sched_params (dump_file, g->num_nodes, ps); 1751 /* Generate prolog and epilog. */ 1752 generate_prolog_epilog (ps, loop, count_reg, count_init); 1753 break; 1754 } 1755 1756 free_partial_schedule (ps); 1757 node_sched_param_vec.release (); 1758 free (node_order); 1759 free_ddg (g); 1760 } 1761 1762 free (g_arr); 1763 1764 /* Release scheduler data, needed until now because of DFA. */ 1765 haifa_sched_finish (); 1766 loop_optimizer_finalize (); 1767 } 1768 1769 /* The SMS scheduling algorithm itself 1770 ----------------------------------- 1771 Input: 'O' an ordered list of insns of a loop. 1772 Output: A scheduling of the loop - kernel, prolog, and epilogue. 1773 1774 'Q' is the empty Set 1775 'PS' is the partial schedule; it holds the currently scheduled nodes with 1776 their cycle/slot. 1777 'PSP' previously scheduled predecessors. 1778 'PSS' previously scheduled successors. 1779 't(u)' the cycle where u is scheduled. 1780 'l(u)' is the latency of u. 1781 'd(v,u)' is the dependence distance from v to u. 1782 'ASAP(u)' the earliest time at which u could be scheduled as computed in 1783 the node ordering phase. 1784 'check_hardware_resources_conflicts(u, PS, c)' 1785 run a trace around cycle/slot through DFA model 1786 to check resource conflicts involving instruction u 1787 at cycle c given the partial schedule PS. 1788 'add_to_partial_schedule_at_time(u, PS, c)' 1789 Add the node/instruction u to the partial schedule 1790 PS at time c. 1791 'calculate_register_pressure(PS)' 1792 Given a schedule of instructions, calculate the register 1793 pressure it implies. One implementation could be the 1794 maximum number of overlapping live ranges. 1795 'maxRP' The maximum allowed register pressure, it is usually derived from the number 1796 registers available in the hardware. 1797 1798 1. II = MII. 1799 2. PS = empty list 1800 3. for each node u in O in pre-computed order 1801 4. if (PSP(u) != Q && PSS(u) == Q) then 1802 5. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u). 1803 6. start = Early_start; end = Early_start + II - 1; step = 1 1804 11. else if (PSP(u) == Q && PSS(u) != Q) then 1805 12. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u). 1806 13. start = Late_start; end = Late_start - II + 1; step = -1 1807 14. else if (PSP(u) != Q && PSS(u) != Q) then 1808 15. Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over all every v in PSP(u). 1809 16. Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over all every v in PSS(u). 1810 17. start = Early_start; 1811 18. end = min(Early_start + II - 1 , Late_start); 1812 19. step = 1 1813 20. else "if (PSP(u) == Q && PSS(u) == Q)" 1814 21. start = ASAP(u); end = start + II - 1; step = 1 1815 22. endif 1816 1817 23. success = false 1818 24. for (c = start ; c != end ; c += step) 1819 25. if check_hardware_resources_conflicts(u, PS, c) then 1820 26. add_to_partial_schedule_at_time(u, PS, c) 1821 27. success = true 1822 28. break 1823 29. endif 1824 30. endfor 1825 31. if (success == false) then 1826 32. II = II + 1 1827 33. if (II > maxII) then 1828 34. finish - failed to schedule 1829 35. endif 1830 36. goto 2. 1831 37. endif 1832 38. endfor 1833 39. if (calculate_register_pressure(PS) > maxRP) then 1834 40. goto 32. 1835 41. endif 1836 42. compute epilogue & prologue 1837 43. finish - succeeded to schedule 1838 1839 ??? The algorithm restricts the scheduling window to II cycles. 1840 In rare cases, it may be better to allow windows of II+1 cycles. 1841 The window would then start and end on the same row, but with 1842 different "must precede" and "must follow" requirements. */ 1843 1844 /* A limit on the number of cycles that resource conflicts can span. ??? Should 1845 be provided by DFA, and be dependent on the type of insn scheduled. Currently 1846 set to 0 to save compile time. */ 1847 #define DFA_HISTORY SMS_DFA_HISTORY 1848 1849 /* A threshold for the number of repeated unsuccessful attempts to insert 1850 an empty row, before we flush the partial schedule and start over. */ 1851 #define MAX_SPLIT_NUM 10 1852 /* Given the partial schedule PS, this function calculates and returns the 1853 cycles in which we can schedule the node with the given index I. 1854 NOTE: Here we do the backtracking in SMS, in some special cases. We have 1855 noticed that there are several cases in which we fail to SMS the loop 1856 because the sched window of a node is empty due to tight data-deps. In 1857 such cases we want to unschedule some of the predecessors/successors 1858 until we get non-empty scheduling window. It returns -1 if the 1859 scheduling window is empty and zero otherwise. */ 1860 1861 static int 1862 get_sched_window (partial_schedule_ptr ps, ddg_node_ptr u_node, 1863 sbitmap sched_nodes, int ii, int *start_p, int *step_p, 1864 int *end_p) 1865 { 1866 int start, step, end; 1867 int early_start, late_start; 1868 ddg_edge_ptr e; 1869 sbitmap psp = sbitmap_alloc (ps->g->num_nodes); 1870 sbitmap pss = sbitmap_alloc (ps->g->num_nodes); 1871 sbitmap u_node_preds = NODE_PREDECESSORS (u_node); 1872 sbitmap u_node_succs = NODE_SUCCESSORS (u_node); 1873 int psp_not_empty; 1874 int pss_not_empty; 1875 int count_preds; 1876 int count_succs; 1877 1878 /* 1. compute sched window for u (start, end, step). */ 1879 bitmap_clear (psp); 1880 bitmap_clear (pss); 1881 psp_not_empty = bitmap_and (psp, u_node_preds, sched_nodes); 1882 pss_not_empty = bitmap_and (pss, u_node_succs, sched_nodes); 1883 1884 /* We first compute a forward range (start <= end), then decide whether 1885 to reverse it. */ 1886 early_start = INT_MIN; 1887 late_start = INT_MAX; 1888 start = INT_MIN; 1889 end = INT_MAX; 1890 step = 1; 1891 1892 count_preds = 0; 1893 count_succs = 0; 1894 1895 if (dump_file && (psp_not_empty || pss_not_empty)) 1896 { 1897 fprintf (dump_file, "\nAnalyzing dependencies for node %d (INSN %d)" 1898 "; ii = %d\n\n", u_node->cuid, INSN_UID (u_node->insn), ii); 1899 fprintf (dump_file, "%11s %11s %11s %11s %5s\n", 1900 "start", "early start", "late start", "end", "time"); 1901 fprintf (dump_file, "=========== =========== =========== ===========" 1902 " =====\n"); 1903 } 1904 /* Calculate early_start and limit end. Both bounds are inclusive. */ 1905 if (psp_not_empty) 1906 for (e = u_node->in; e != 0; e = e->next_in) 1907 { 1908 int v = e->src->cuid; 1909 1910 if (bitmap_bit_p (sched_nodes, v)) 1911 { 1912 int p_st = SCHED_TIME (v); 1913 int earliest = p_st + e->latency - (e->distance * ii); 1914 int latest = (e->data_type == MEM_DEP ? p_st + ii - 1 : INT_MAX); 1915 1916 if (dump_file) 1917 { 1918 fprintf (dump_file, "%11s %11d %11s %11d %5d", 1919 "", earliest, "", latest, p_st); 1920 print_ddg_edge (dump_file, e); 1921 fprintf (dump_file, "\n"); 1922 } 1923 1924 early_start = MAX (early_start, earliest); 1925 end = MIN (end, latest); 1926 1927 if (e->type == TRUE_DEP && e->data_type == REG_DEP) 1928 count_preds++; 1929 } 1930 } 1931 1932 /* Calculate late_start and limit start. Both bounds are inclusive. */ 1933 if (pss_not_empty) 1934 for (e = u_node->out; e != 0; e = e->next_out) 1935 { 1936 int v = e->dest->cuid; 1937 1938 if (bitmap_bit_p (sched_nodes, v)) 1939 { 1940 int s_st = SCHED_TIME (v); 1941 int earliest = (e->data_type == MEM_DEP ? s_st - ii + 1 : INT_MIN); 1942 int latest = s_st - e->latency + (e->distance * ii); 1943 1944 if (dump_file) 1945 { 1946 fprintf (dump_file, "%11d %11s %11d %11s %5d", 1947 earliest, "", latest, "", s_st); 1948 print_ddg_edge (dump_file, e); 1949 fprintf (dump_file, "\n"); 1950 } 1951 1952 start = MAX (start, earliest); 1953 late_start = MIN (late_start, latest); 1954 1955 if (e->type == TRUE_DEP && e->data_type == REG_DEP) 1956 count_succs++; 1957 } 1958 } 1959 1960 if (dump_file && (psp_not_empty || pss_not_empty)) 1961 { 1962 fprintf (dump_file, "----------- ----------- ----------- -----------" 1963 " -----\n"); 1964 fprintf (dump_file, "%11d %11d %11d %11d %5s %s\n", 1965 start, early_start, late_start, end, "", 1966 "(max, max, min, min)"); 1967 } 1968 1969 /* Get a target scheduling window no bigger than ii. */ 1970 if (early_start == INT_MIN && late_start == INT_MAX) 1971 early_start = NODE_ASAP (u_node); 1972 else if (early_start == INT_MIN) 1973 early_start = late_start - (ii - 1); 1974 late_start = MIN (late_start, early_start + (ii - 1)); 1975 1976 /* Apply memory dependence limits. */ 1977 start = MAX (start, early_start); 1978 end = MIN (end, late_start); 1979 1980 if (dump_file && (psp_not_empty || pss_not_empty)) 1981 fprintf (dump_file, "%11s %11d %11d %11s %5s final window\n", 1982 "", start, end, "", ""); 1983 1984 /* If there are at least as many successors as predecessors, schedule the 1985 node close to its successors. */ 1986 if (pss_not_empty && count_succs >= count_preds) 1987 { 1988 std::swap (start, end); 1989 step = -1; 1990 } 1991 1992 /* Now that we've finalized the window, make END an exclusive rather 1993 than an inclusive bound. */ 1994 end += step; 1995 1996 *start_p = start; 1997 *step_p = step; 1998 *end_p = end; 1999 sbitmap_free (psp); 2000 sbitmap_free (pss); 2001 2002 if ((start >= end && step == 1) || (start <= end && step == -1)) 2003 { 2004 if (dump_file) 2005 fprintf (dump_file, "\nEmpty window: start=%d, end=%d, step=%d\n", 2006 start, end, step); 2007 return -1; 2008 } 2009 2010 return 0; 2011 } 2012 2013 /* Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the 2014 node currently been scheduled. At the end of the calculation 2015 MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of 2016 U_NODE which are (1) already scheduled in the first/last row of 2017 U_NODE's scheduling window, (2) whose dependence inequality with U 2018 becomes an equality when U is scheduled in this same row, and (3) 2019 whose dependence latency is zero. 2020 2021 The first and last rows are calculated using the following parameters: 2022 START/END rows - The cycles that begins/ends the traversal on the window; 2023 searching for an empty cycle to schedule U_NODE. 2024 STEP - The direction in which we traverse the window. 2025 II - The initiation interval. */ 2026 2027 static void 2028 calculate_must_precede_follow (ddg_node_ptr u_node, int start, int end, 2029 int step, int ii, sbitmap sched_nodes, 2030 sbitmap must_precede, sbitmap must_follow) 2031 { 2032 ddg_edge_ptr e; 2033 int first_cycle_in_window, last_cycle_in_window; 2034 2035 gcc_assert (must_precede && must_follow); 2036 2037 /* Consider the following scheduling window: 2038 {first_cycle_in_window, first_cycle_in_window+1, ..., 2039 last_cycle_in_window}. If step is 1 then the following will be 2040 the order we traverse the window: {start=first_cycle_in_window, 2041 first_cycle_in_window+1, ..., end=last_cycle_in_window+1}, 2042 or {start=last_cycle_in_window, last_cycle_in_window-1, ..., 2043 end=first_cycle_in_window-1} if step is -1. */ 2044 first_cycle_in_window = (step == 1) ? start : end - step; 2045 last_cycle_in_window = (step == 1) ? end - step : start; 2046 2047 bitmap_clear (must_precede); 2048 bitmap_clear (must_follow); 2049 2050 if (dump_file) 2051 fprintf (dump_file, "\nmust_precede: "); 2052 2053 /* Instead of checking if: 2054 (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window) 2055 && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) == 2056 first_cycle_in_window) 2057 && e->latency == 0 2058 we use the fact that latency is non-negative: 2059 SCHED_TIME (e->src) - (e->distance * ii) <= 2060 SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <= 2061 first_cycle_in_window 2062 and check only if 2063 SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window */ 2064 for (e = u_node->in; e != 0; e = e->next_in) 2065 if (bitmap_bit_p (sched_nodes, e->src->cuid) 2066 && ((SCHED_TIME (e->src->cuid) - (e->distance * ii)) == 2067 first_cycle_in_window)) 2068 { 2069 if (dump_file) 2070 fprintf (dump_file, "%d ", e->src->cuid); 2071 2072 bitmap_set_bit (must_precede, e->src->cuid); 2073 } 2074 2075 if (dump_file) 2076 fprintf (dump_file, "\nmust_follow: "); 2077 2078 /* Instead of checking if: 2079 (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window) 2080 && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) == 2081 last_cycle_in_window) 2082 && e->latency == 0 2083 we use the fact that latency is non-negative: 2084 SCHED_TIME (e->dest) + (e->distance * ii) >= 2085 SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >= 2086 last_cycle_in_window 2087 and check only if 2088 SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window */ 2089 for (e = u_node->out; e != 0; e = e->next_out) 2090 if (bitmap_bit_p (sched_nodes, e->dest->cuid) 2091 && ((SCHED_TIME (e->dest->cuid) + (e->distance * ii)) == 2092 last_cycle_in_window)) 2093 { 2094 if (dump_file) 2095 fprintf (dump_file, "%d ", e->dest->cuid); 2096 2097 bitmap_set_bit (must_follow, e->dest->cuid); 2098 } 2099 2100 if (dump_file) 2101 fprintf (dump_file, "\n"); 2102 } 2103 2104 /* Return 1 if U_NODE can be scheduled in CYCLE. Use the following 2105 parameters to decide if that's possible: 2106 PS - The partial schedule. 2107 U - The serial number of U_NODE. 2108 NUM_SPLITS - The number of row splits made so far. 2109 MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at 2110 the first row of the scheduling window) 2111 MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the 2112 last row of the scheduling window) */ 2113 2114 static bool 2115 try_scheduling_node_in_cycle (partial_schedule_ptr ps, 2116 int u, int cycle, sbitmap sched_nodes, 2117 int *num_splits, sbitmap must_precede, 2118 sbitmap must_follow) 2119 { 2120 ps_insn_ptr psi; 2121 bool success = 0; 2122 2123 verify_partial_schedule (ps, sched_nodes); 2124 psi = ps_add_node_check_conflicts (ps, u, cycle, must_precede, must_follow); 2125 if (psi) 2126 { 2127 SCHED_TIME (u) = cycle; 2128 bitmap_set_bit (sched_nodes, u); 2129 success = 1; 2130 *num_splits = 0; 2131 if (dump_file) 2132 fprintf (dump_file, "Scheduled w/o split in %d\n", cycle); 2133 2134 } 2135 2136 return success; 2137 } 2138 2139 /* This function implements the scheduling algorithm for SMS according to the 2140 above algorithm. */ 2141 static partial_schedule_ptr 2142 sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order) 2143 { 2144 int ii = mii; 2145 int i, c, success, num_splits = 0; 2146 int flush_and_start_over = true; 2147 int num_nodes = g->num_nodes; 2148 int start, end, step; /* Place together into one struct? */ 2149 sbitmap sched_nodes = sbitmap_alloc (num_nodes); 2150 sbitmap must_precede = sbitmap_alloc (num_nodes); 2151 sbitmap must_follow = sbitmap_alloc (num_nodes); 2152 sbitmap tobe_scheduled = sbitmap_alloc (num_nodes); 2153 2154 partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY); 2155 2156 bitmap_ones (tobe_scheduled); 2157 bitmap_clear (sched_nodes); 2158 2159 while (flush_and_start_over && (ii < maxii)) 2160 { 2161 2162 if (dump_file) 2163 fprintf (dump_file, "Starting with ii=%d\n", ii); 2164 flush_and_start_over = false; 2165 bitmap_clear (sched_nodes); 2166 2167 for (i = 0; i < num_nodes; i++) 2168 { 2169 int u = nodes_order[i]; 2170 ddg_node_ptr u_node = &ps->g->nodes[u]; 2171 rtx_insn *insn = u_node->insn; 2172 2173 if (!NONDEBUG_INSN_P (insn)) 2174 { 2175 bitmap_clear_bit (tobe_scheduled, u); 2176 continue; 2177 } 2178 2179 if (bitmap_bit_p (sched_nodes, u)) 2180 continue; 2181 2182 /* Try to get non-empty scheduling window. */ 2183 success = 0; 2184 if (get_sched_window (ps, u_node, sched_nodes, ii, &start, 2185 &step, &end) == 0) 2186 { 2187 if (dump_file) 2188 fprintf (dump_file, "\nTrying to schedule node %d " 2189 "INSN = %d in (%d .. %d) step %d\n", u, (INSN_UID 2190 (g->nodes[u].insn)), start, end, step); 2191 2192 gcc_assert ((step > 0 && start < end) 2193 || (step < 0 && start > end)); 2194 2195 calculate_must_precede_follow (u_node, start, end, step, ii, 2196 sched_nodes, must_precede, 2197 must_follow); 2198 2199 for (c = start; c != end; c += step) 2200 { 2201 sbitmap tmp_precede, tmp_follow; 2202 2203 set_must_precede_follow (&tmp_follow, must_follow, 2204 &tmp_precede, must_precede, 2205 c, start, end, step); 2206 success = 2207 try_scheduling_node_in_cycle (ps, u, c, 2208 sched_nodes, 2209 &num_splits, tmp_precede, 2210 tmp_follow); 2211 if (success) 2212 break; 2213 } 2214 2215 verify_partial_schedule (ps, sched_nodes); 2216 } 2217 if (!success) 2218 { 2219 int split_row; 2220 2221 if (ii++ == maxii) 2222 break; 2223 2224 if (num_splits >= MAX_SPLIT_NUM) 2225 { 2226 num_splits = 0; 2227 flush_and_start_over = true; 2228 verify_partial_schedule (ps, sched_nodes); 2229 reset_partial_schedule (ps, ii); 2230 verify_partial_schedule (ps, sched_nodes); 2231 break; 2232 } 2233 2234 num_splits++; 2235 /* The scheduling window is exclusive of 'end' 2236 whereas compute_split_window() expects an inclusive, 2237 ordered range. */ 2238 if (step == 1) 2239 split_row = compute_split_row (sched_nodes, start, end - 1, 2240 ps->ii, u_node); 2241 else 2242 split_row = compute_split_row (sched_nodes, end + 1, start, 2243 ps->ii, u_node); 2244 2245 ps_insert_empty_row (ps, split_row, sched_nodes); 2246 i--; /* Go back and retry node i. */ 2247 2248 if (dump_file) 2249 fprintf (dump_file, "num_splits=%d\n", num_splits); 2250 } 2251 2252 /* ??? If (success), check register pressure estimates. */ 2253 } /* Continue with next node. */ 2254 } /* While flush_and_start_over. */ 2255 if (ii >= maxii) 2256 { 2257 free_partial_schedule (ps); 2258 ps = NULL; 2259 } 2260 else 2261 gcc_assert (bitmap_equal_p (tobe_scheduled, sched_nodes)); 2262 2263 sbitmap_free (sched_nodes); 2264 sbitmap_free (must_precede); 2265 sbitmap_free (must_follow); 2266 sbitmap_free (tobe_scheduled); 2267 2268 return ps; 2269 } 2270 2271 /* This function inserts a new empty row into PS at the position 2272 according to SPLITROW, keeping all already scheduled instructions 2273 intact and updating their SCHED_TIME and cycle accordingly. */ 2274 static void 2275 ps_insert_empty_row (partial_schedule_ptr ps, int split_row, 2276 sbitmap sched_nodes) 2277 { 2278 ps_insn_ptr crr_insn; 2279 ps_insn_ptr *rows_new; 2280 int ii = ps->ii; 2281 int new_ii = ii + 1; 2282 int row; 2283 int *rows_length_new; 2284 2285 verify_partial_schedule (ps, sched_nodes); 2286 2287 /* We normalize sched_time and rotate ps to have only non-negative sched 2288 times, for simplicity of updating cycles after inserting new row. */ 2289 split_row -= ps->min_cycle; 2290 split_row = SMODULO (split_row, ii); 2291 if (dump_file) 2292 fprintf (dump_file, "split_row=%d\n", split_row); 2293 2294 reset_sched_times (ps, PS_MIN_CYCLE (ps)); 2295 rotate_partial_schedule (ps, PS_MIN_CYCLE (ps)); 2296 2297 rows_new = (ps_insn_ptr *) xcalloc (new_ii, sizeof (ps_insn_ptr)); 2298 rows_length_new = (int *) xcalloc (new_ii, sizeof (int)); 2299 for (row = 0; row < split_row; row++) 2300 { 2301 rows_new[row] = ps->rows[row]; 2302 rows_length_new[row] = ps->rows_length[row]; 2303 ps->rows[row] = NULL; 2304 for (crr_insn = rows_new[row]; 2305 crr_insn; crr_insn = crr_insn->next_in_row) 2306 { 2307 int u = crr_insn->id; 2308 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii); 2309 2310 SCHED_TIME (u) = new_time; 2311 crr_insn->cycle = new_time; 2312 SCHED_ROW (u) = new_time % new_ii; 2313 SCHED_STAGE (u) = new_time / new_ii; 2314 } 2315 2316 } 2317 2318 rows_new[split_row] = NULL; 2319 2320 for (row = split_row; row < ii; row++) 2321 { 2322 rows_new[row + 1] = ps->rows[row]; 2323 rows_length_new[row + 1] = ps->rows_length[row]; 2324 ps->rows[row] = NULL; 2325 for (crr_insn = rows_new[row + 1]; 2326 crr_insn; crr_insn = crr_insn->next_in_row) 2327 { 2328 int u = crr_insn->id; 2329 int new_time = SCHED_TIME (u) + (SCHED_TIME (u) / ii) + 1; 2330 2331 SCHED_TIME (u) = new_time; 2332 crr_insn->cycle = new_time; 2333 SCHED_ROW (u) = new_time % new_ii; 2334 SCHED_STAGE (u) = new_time / new_ii; 2335 } 2336 } 2337 2338 /* Updating ps. */ 2339 ps->min_cycle = ps->min_cycle + ps->min_cycle / ii 2340 + (SMODULO (ps->min_cycle, ii) >= split_row ? 1 : 0); 2341 ps->max_cycle = ps->max_cycle + ps->max_cycle / ii 2342 + (SMODULO (ps->max_cycle, ii) >= split_row ? 1 : 0); 2343 free (ps->rows); 2344 ps->rows = rows_new; 2345 free (ps->rows_length); 2346 ps->rows_length = rows_length_new; 2347 ps->ii = new_ii; 2348 gcc_assert (ps->min_cycle >= 0); 2349 2350 verify_partial_schedule (ps, sched_nodes); 2351 2352 if (dump_file) 2353 fprintf (dump_file, "min_cycle=%d, max_cycle=%d\n", ps->min_cycle, 2354 ps->max_cycle); 2355 } 2356 2357 /* Given U_NODE which is the node that failed to be scheduled; LOW and 2358 UP which are the boundaries of it's scheduling window; compute using 2359 SCHED_NODES and II a row in the partial schedule that can be split 2360 which will separate a critical predecessor from a critical successor 2361 thereby expanding the window, and return it. */ 2362 static int 2363 compute_split_row (sbitmap sched_nodes, int low, int up, int ii, 2364 ddg_node_ptr u_node) 2365 { 2366 ddg_edge_ptr e; 2367 int lower = INT_MIN, upper = INT_MAX; 2368 int crit_pred = -1; 2369 int crit_succ = -1; 2370 int crit_cycle; 2371 2372 for (e = u_node->in; e != 0; e = e->next_in) 2373 { 2374 int v = e->src->cuid; 2375 2376 if (bitmap_bit_p (sched_nodes, v) 2377 && (low == SCHED_TIME (v) + e->latency - (e->distance * ii))) 2378 if (SCHED_TIME (v) > lower) 2379 { 2380 crit_pred = v; 2381 lower = SCHED_TIME (v); 2382 } 2383 } 2384 2385 if (crit_pred >= 0) 2386 { 2387 crit_cycle = SCHED_TIME (crit_pred) + 1; 2388 return SMODULO (crit_cycle, ii); 2389 } 2390 2391 for (e = u_node->out; e != 0; e = e->next_out) 2392 { 2393 int v = e->dest->cuid; 2394 2395 if (bitmap_bit_p (sched_nodes, v) 2396 && (up == SCHED_TIME (v) - e->latency + (e->distance * ii))) 2397 if (SCHED_TIME (v) < upper) 2398 { 2399 crit_succ = v; 2400 upper = SCHED_TIME (v); 2401 } 2402 } 2403 2404 if (crit_succ >= 0) 2405 { 2406 crit_cycle = SCHED_TIME (crit_succ); 2407 return SMODULO (crit_cycle, ii); 2408 } 2409 2410 if (dump_file) 2411 fprintf (dump_file, "Both crit_pred and crit_succ are NULL\n"); 2412 2413 return SMODULO ((low + up + 1) / 2, ii); 2414 } 2415 2416 static void 2417 verify_partial_schedule (partial_schedule_ptr ps, sbitmap sched_nodes) 2418 { 2419 int row; 2420 ps_insn_ptr crr_insn; 2421 2422 for (row = 0; row < ps->ii; row++) 2423 { 2424 int length = 0; 2425 2426 for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row) 2427 { 2428 int u = crr_insn->id; 2429 2430 length++; 2431 gcc_assert (bitmap_bit_p (sched_nodes, u)); 2432 /* ??? Test also that all nodes of sched_nodes are in ps, perhaps by 2433 popcount (sched_nodes) == number of insns in ps. */ 2434 gcc_assert (SCHED_TIME (u) >= ps->min_cycle); 2435 gcc_assert (SCHED_TIME (u) <= ps->max_cycle); 2436 } 2437 2438 gcc_assert (ps->rows_length[row] == length); 2439 } 2440 } 2441 2442 2443 /* This page implements the algorithm for ordering the nodes of a DDG 2444 for modulo scheduling, activated through the 2445 "int sms_order_nodes (ddg_ptr, int mii, int * result)" API. */ 2446 2447 #define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info) 2448 #define ASAP(x) (ORDER_PARAMS ((x))->asap) 2449 #define ALAP(x) (ORDER_PARAMS ((x))->alap) 2450 #define HEIGHT(x) (ORDER_PARAMS ((x))->height) 2451 #define MOB(x) (ALAP ((x)) - ASAP ((x))) 2452 #define DEPTH(x) (ASAP ((x))) 2453 2454 typedef struct node_order_params * nopa; 2455 2456 static void order_nodes_of_sccs (ddg_all_sccs_ptr, int * result); 2457 static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int*, int); 2458 static nopa calculate_order_params (ddg_ptr, int, int *); 2459 static int find_max_asap (ddg_ptr, sbitmap); 2460 static int find_max_hv_min_mob (ddg_ptr, sbitmap); 2461 static int find_max_dv_min_mob (ddg_ptr, sbitmap); 2462 2463 enum sms_direction {BOTTOMUP, TOPDOWN}; 2464 2465 struct node_order_params 2466 { 2467 int asap; 2468 int alap; 2469 int height; 2470 }; 2471 2472 /* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1. */ 2473 static void 2474 check_nodes_order (int *node_order, int num_nodes) 2475 { 2476 int i; 2477 sbitmap tmp = sbitmap_alloc (num_nodes); 2478 2479 bitmap_clear (tmp); 2480 2481 if (dump_file) 2482 fprintf (dump_file, "SMS final nodes order: \n"); 2483 2484 for (i = 0; i < num_nodes; i++) 2485 { 2486 int u = node_order[i]; 2487 2488 if (dump_file) 2489 fprintf (dump_file, "%d ", u); 2490 gcc_assert (u < num_nodes && u >= 0 && !bitmap_bit_p (tmp, u)); 2491 2492 bitmap_set_bit (tmp, u); 2493 } 2494 2495 if (dump_file) 2496 fprintf (dump_file, "\n"); 2497 2498 sbitmap_free (tmp); 2499 } 2500 2501 /* Order the nodes of G for scheduling and pass the result in 2502 NODE_ORDER. Also set aux.count of each node to ASAP. 2503 Put maximal ASAP to PMAX_ASAP. Return the recMII for the given DDG. */ 2504 static int 2505 sms_order_nodes (ddg_ptr g, int mii, int * node_order, int *pmax_asap) 2506 { 2507 int i; 2508 int rec_mii = 0; 2509 ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g); 2510 2511 nopa nops = calculate_order_params (g, mii, pmax_asap); 2512 2513 if (dump_file) 2514 print_sccs (dump_file, sccs, g); 2515 2516 order_nodes_of_sccs (sccs, node_order); 2517 2518 if (sccs->num_sccs > 0) 2519 /* First SCC has the largest recurrence_length. */ 2520 rec_mii = sccs->sccs[0]->recurrence_length; 2521 2522 /* Save ASAP before destroying node_order_params. */ 2523 for (i = 0; i < g->num_nodes; i++) 2524 { 2525 ddg_node_ptr v = &g->nodes[i]; 2526 v->aux.count = ASAP (v); 2527 } 2528 2529 free (nops); 2530 free_ddg_all_sccs (sccs); 2531 check_nodes_order (node_order, g->num_nodes); 2532 2533 return rec_mii; 2534 } 2535 2536 static void 2537 order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order) 2538 { 2539 int i, pos = 0; 2540 ddg_ptr g = all_sccs->ddg; 2541 int num_nodes = g->num_nodes; 2542 sbitmap prev_sccs = sbitmap_alloc (num_nodes); 2543 sbitmap on_path = sbitmap_alloc (num_nodes); 2544 sbitmap tmp = sbitmap_alloc (num_nodes); 2545 sbitmap ones = sbitmap_alloc (num_nodes); 2546 2547 bitmap_clear (prev_sccs); 2548 bitmap_ones (ones); 2549 2550 /* Perform the node ordering starting from the SCC with the highest recMII. 2551 For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc. */ 2552 for (i = 0; i < all_sccs->num_sccs; i++) 2553 { 2554 ddg_scc_ptr scc = all_sccs->sccs[i]; 2555 2556 /* Add nodes on paths from previous SCCs to the current SCC. */ 2557 find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes); 2558 bitmap_ior (tmp, scc->nodes, on_path); 2559 2560 /* Add nodes on paths from the current SCC to previous SCCs. */ 2561 find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs); 2562 bitmap_ior (tmp, tmp, on_path); 2563 2564 /* Remove nodes of previous SCCs from current extended SCC. */ 2565 bitmap_and_compl (tmp, tmp, prev_sccs); 2566 2567 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos); 2568 /* Above call to order_nodes_in_scc updated prev_sccs |= tmp. */ 2569 } 2570 2571 /* Handle the remaining nodes that do not belong to any scc. Each call 2572 to order_nodes_in_scc handles a single connected component. */ 2573 while (pos < g->num_nodes) 2574 { 2575 bitmap_and_compl (tmp, ones, prev_sccs); 2576 pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos); 2577 } 2578 sbitmap_free (prev_sccs); 2579 sbitmap_free (on_path); 2580 sbitmap_free (tmp); 2581 sbitmap_free (ones); 2582 } 2583 2584 /* MII is needed if we consider backarcs (that do not close recursive cycles). */ 2585 static struct node_order_params * 2586 calculate_order_params (ddg_ptr g, int mii ATTRIBUTE_UNUSED, int *pmax_asap) 2587 { 2588 int u; 2589 int max_asap; 2590 int num_nodes = g->num_nodes; 2591 ddg_edge_ptr e; 2592 /* Allocate a place to hold ordering params for each node in the DDG. */ 2593 nopa node_order_params_arr; 2594 2595 /* Initialize of ASAP/ALAP/HEIGHT to zero. */ 2596 node_order_params_arr = (nopa) xcalloc (num_nodes, 2597 sizeof (struct node_order_params)); 2598 2599 /* Set the aux pointer of each node to point to its order_params structure. */ 2600 for (u = 0; u < num_nodes; u++) 2601 g->nodes[u].aux.info = &node_order_params_arr[u]; 2602 2603 /* Disregarding a backarc from each recursive cycle to obtain a DAG, 2604 calculate ASAP, ALAP, mobility, distance, and height for each node 2605 in the dependence (direct acyclic) graph. */ 2606 2607 /* We assume that the nodes in the array are in topological order. */ 2608 2609 max_asap = 0; 2610 for (u = 0; u < num_nodes; u++) 2611 { 2612 ddg_node_ptr u_node = &g->nodes[u]; 2613 2614 ASAP (u_node) = 0; 2615 for (e = u_node->in; e; e = e->next_in) 2616 if (e->distance == 0) 2617 ASAP (u_node) = MAX (ASAP (u_node), 2618 ASAP (e->src) + e->latency); 2619 max_asap = MAX (max_asap, ASAP (u_node)); 2620 } 2621 2622 for (u = num_nodes - 1; u > -1; u--) 2623 { 2624 ddg_node_ptr u_node = &g->nodes[u]; 2625 2626 ALAP (u_node) = max_asap; 2627 HEIGHT (u_node) = 0; 2628 for (e = u_node->out; e; e = e->next_out) 2629 if (e->distance == 0) 2630 { 2631 ALAP (u_node) = MIN (ALAP (u_node), 2632 ALAP (e->dest) - e->latency); 2633 HEIGHT (u_node) = MAX (HEIGHT (u_node), 2634 HEIGHT (e->dest) + e->latency); 2635 } 2636 } 2637 if (dump_file) 2638 { 2639 fprintf (dump_file, "\nOrder params\n"); 2640 for (u = 0; u < num_nodes; u++) 2641 { 2642 ddg_node_ptr u_node = &g->nodes[u]; 2643 2644 fprintf (dump_file, "node %d, ASAP: %d, ALAP: %d, HEIGHT: %d\n", u, 2645 ASAP (u_node), ALAP (u_node), HEIGHT (u_node)); 2646 } 2647 } 2648 2649 *pmax_asap = max_asap; 2650 return node_order_params_arr; 2651 } 2652 2653 static int 2654 find_max_asap (ddg_ptr g, sbitmap nodes) 2655 { 2656 unsigned int u = 0; 2657 int max_asap = -1; 2658 int result = -1; 2659 sbitmap_iterator sbi; 2660 2661 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi) 2662 { 2663 ddg_node_ptr u_node = &g->nodes[u]; 2664 2665 if (max_asap < ASAP (u_node)) 2666 { 2667 max_asap = ASAP (u_node); 2668 result = u; 2669 } 2670 } 2671 return result; 2672 } 2673 2674 static int 2675 find_max_hv_min_mob (ddg_ptr g, sbitmap nodes) 2676 { 2677 unsigned int u = 0; 2678 int max_hv = -1; 2679 int min_mob = INT_MAX; 2680 int result = -1; 2681 sbitmap_iterator sbi; 2682 2683 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi) 2684 { 2685 ddg_node_ptr u_node = &g->nodes[u]; 2686 2687 if (max_hv < HEIGHT (u_node)) 2688 { 2689 max_hv = HEIGHT (u_node); 2690 min_mob = MOB (u_node); 2691 result = u; 2692 } 2693 else if ((max_hv == HEIGHT (u_node)) 2694 && (min_mob > MOB (u_node))) 2695 { 2696 min_mob = MOB (u_node); 2697 result = u; 2698 } 2699 } 2700 return result; 2701 } 2702 2703 static int 2704 find_max_dv_min_mob (ddg_ptr g, sbitmap nodes) 2705 { 2706 unsigned int u = 0; 2707 int max_dv = -1; 2708 int min_mob = INT_MAX; 2709 int result = -1; 2710 sbitmap_iterator sbi; 2711 2712 EXECUTE_IF_SET_IN_BITMAP (nodes, 0, u, sbi) 2713 { 2714 ddg_node_ptr u_node = &g->nodes[u]; 2715 2716 if (max_dv < DEPTH (u_node)) 2717 { 2718 max_dv = DEPTH (u_node); 2719 min_mob = MOB (u_node); 2720 result = u; 2721 } 2722 else if ((max_dv == DEPTH (u_node)) 2723 && (min_mob > MOB (u_node))) 2724 { 2725 min_mob = MOB (u_node); 2726 result = u; 2727 } 2728 } 2729 return result; 2730 } 2731 2732 /* Places the nodes of SCC into the NODE_ORDER array starting 2733 at position POS, according to the SMS ordering algorithm. 2734 NODES_ORDERED (in&out parameter) holds the bitset of all nodes in 2735 the NODE_ORDER array, starting from position zero. */ 2736 static int 2737 order_nodes_in_scc (ddg_ptr g, sbitmap nodes_ordered, sbitmap scc, 2738 int * node_order, int pos) 2739 { 2740 enum sms_direction dir; 2741 int num_nodes = g->num_nodes; 2742 sbitmap workset = sbitmap_alloc (num_nodes); 2743 sbitmap tmp = sbitmap_alloc (num_nodes); 2744 sbitmap zero_bitmap = sbitmap_alloc (num_nodes); 2745 sbitmap predecessors = sbitmap_alloc (num_nodes); 2746 sbitmap successors = sbitmap_alloc (num_nodes); 2747 2748 bitmap_clear (predecessors); 2749 find_predecessors (predecessors, g, nodes_ordered); 2750 2751 bitmap_clear (successors); 2752 find_successors (successors, g, nodes_ordered); 2753 2754 bitmap_clear (tmp); 2755 if (bitmap_and (tmp, predecessors, scc)) 2756 { 2757 bitmap_copy (workset, tmp); 2758 dir = BOTTOMUP; 2759 } 2760 else if (bitmap_and (tmp, successors, scc)) 2761 { 2762 bitmap_copy (workset, tmp); 2763 dir = TOPDOWN; 2764 } 2765 else 2766 { 2767 int u; 2768 2769 bitmap_clear (workset); 2770 if ((u = find_max_asap (g, scc)) >= 0) 2771 bitmap_set_bit (workset, u); 2772 dir = BOTTOMUP; 2773 } 2774 2775 bitmap_clear (zero_bitmap); 2776 while (!bitmap_equal_p (workset, zero_bitmap)) 2777 { 2778 int v; 2779 ddg_node_ptr v_node; 2780 sbitmap v_node_preds; 2781 sbitmap v_node_succs; 2782 2783 if (dir == TOPDOWN) 2784 { 2785 while (!bitmap_equal_p (workset, zero_bitmap)) 2786 { 2787 v = find_max_hv_min_mob (g, workset); 2788 v_node = &g->nodes[v]; 2789 node_order[pos++] = v; 2790 v_node_succs = NODE_SUCCESSORS (v_node); 2791 bitmap_and (tmp, v_node_succs, scc); 2792 2793 /* Don't consider the already ordered successors again. */ 2794 bitmap_and_compl (tmp, tmp, nodes_ordered); 2795 bitmap_ior (workset, workset, tmp); 2796 bitmap_clear_bit (workset, v); 2797 bitmap_set_bit (nodes_ordered, v); 2798 } 2799 dir = BOTTOMUP; 2800 bitmap_clear (predecessors); 2801 find_predecessors (predecessors, g, nodes_ordered); 2802 bitmap_and (workset, predecessors, scc); 2803 } 2804 else 2805 { 2806 while (!bitmap_equal_p (workset, zero_bitmap)) 2807 { 2808 v = find_max_dv_min_mob (g, workset); 2809 v_node = &g->nodes[v]; 2810 node_order[pos++] = v; 2811 v_node_preds = NODE_PREDECESSORS (v_node); 2812 bitmap_and (tmp, v_node_preds, scc); 2813 2814 /* Don't consider the already ordered predecessors again. */ 2815 bitmap_and_compl (tmp, tmp, nodes_ordered); 2816 bitmap_ior (workset, workset, tmp); 2817 bitmap_clear_bit (workset, v); 2818 bitmap_set_bit (nodes_ordered, v); 2819 } 2820 dir = TOPDOWN; 2821 bitmap_clear (successors); 2822 find_successors (successors, g, nodes_ordered); 2823 bitmap_and (workset, successors, scc); 2824 } 2825 } 2826 sbitmap_free (tmp); 2827 sbitmap_free (workset); 2828 sbitmap_free (zero_bitmap); 2829 sbitmap_free (predecessors); 2830 sbitmap_free (successors); 2831 return pos; 2832 } 2833 2834 2835 /* This page contains functions for manipulating partial-schedules during 2836 modulo scheduling. */ 2837 2838 /* Create a partial schedule and allocate a memory to hold II rows. */ 2839 2840 static partial_schedule_ptr 2841 create_partial_schedule (int ii, ddg_ptr g, int history) 2842 { 2843 partial_schedule_ptr ps = XNEW (struct partial_schedule); 2844 ps->rows = (ps_insn_ptr *) xcalloc (ii, sizeof (ps_insn_ptr)); 2845 ps->rows_length = (int *) xcalloc (ii, sizeof (int)); 2846 ps->reg_moves.create (0); 2847 ps->ii = ii; 2848 ps->history = history; 2849 ps->min_cycle = INT_MAX; 2850 ps->max_cycle = INT_MIN; 2851 ps->g = g; 2852 2853 return ps; 2854 } 2855 2856 /* Free the PS_INSNs in rows array of the given partial schedule. 2857 ??? Consider caching the PS_INSN's. */ 2858 static void 2859 free_ps_insns (partial_schedule_ptr ps) 2860 { 2861 int i; 2862 2863 for (i = 0; i < ps->ii; i++) 2864 { 2865 while (ps->rows[i]) 2866 { 2867 ps_insn_ptr ps_insn = ps->rows[i]->next_in_row; 2868 2869 free (ps->rows[i]); 2870 ps->rows[i] = ps_insn; 2871 } 2872 ps->rows[i] = NULL; 2873 } 2874 } 2875 2876 /* Free all the memory allocated to the partial schedule. */ 2877 2878 static void 2879 free_partial_schedule (partial_schedule_ptr ps) 2880 { 2881 ps_reg_move_info *move; 2882 unsigned int i; 2883 2884 if (!ps) 2885 return; 2886 2887 FOR_EACH_VEC_ELT (ps->reg_moves, i, move) 2888 sbitmap_free (move->uses); 2889 ps->reg_moves.release (); 2890 2891 free_ps_insns (ps); 2892 free (ps->rows); 2893 free (ps->rows_length); 2894 free (ps); 2895 } 2896 2897 /* Clear the rows array with its PS_INSNs, and create a new one with 2898 NEW_II rows. */ 2899 2900 static void 2901 reset_partial_schedule (partial_schedule_ptr ps, int new_ii) 2902 { 2903 if (!ps) 2904 return; 2905 free_ps_insns (ps); 2906 if (new_ii == ps->ii) 2907 return; 2908 ps->rows = (ps_insn_ptr *) xrealloc (ps->rows, new_ii 2909 * sizeof (ps_insn_ptr)); 2910 memset (ps->rows, 0, new_ii * sizeof (ps_insn_ptr)); 2911 ps->rows_length = (int *) xrealloc (ps->rows_length, new_ii * sizeof (int)); 2912 memset (ps->rows_length, 0, new_ii * sizeof (int)); 2913 ps->ii = new_ii; 2914 ps->min_cycle = INT_MAX; 2915 ps->max_cycle = INT_MIN; 2916 } 2917 2918 /* Prints the partial schedule as an ii rows array, for each rows 2919 print the ids of the insns in it. */ 2920 void 2921 print_partial_schedule (partial_schedule_ptr ps, FILE *dump) 2922 { 2923 int i; 2924 2925 for (i = 0; i < ps->ii; i++) 2926 { 2927 ps_insn_ptr ps_i = ps->rows[i]; 2928 2929 fprintf (dump, "\n[ROW %d ]: ", i); 2930 while (ps_i) 2931 { 2932 rtx_insn *insn = ps_rtl_insn (ps, ps_i->id); 2933 2934 if (JUMP_P (insn)) 2935 fprintf (dump, "%d (branch), ", INSN_UID (insn)); 2936 else 2937 fprintf (dump, "%d, ", INSN_UID (insn)); 2938 2939 ps_i = ps_i->next_in_row; 2940 } 2941 } 2942 } 2943 2944 /* Creates an object of PS_INSN and initializes it to the given parameters. */ 2945 static ps_insn_ptr 2946 create_ps_insn (int id, int cycle) 2947 { 2948 ps_insn_ptr ps_i = XNEW (struct ps_insn); 2949 2950 ps_i->id = id; 2951 ps_i->next_in_row = NULL; 2952 ps_i->prev_in_row = NULL; 2953 ps_i->cycle = cycle; 2954 2955 return ps_i; 2956 } 2957 2958 2959 /* Removes the given PS_INSN from the partial schedule. */ 2960 static void 2961 remove_node_from_ps (partial_schedule_ptr ps, ps_insn_ptr ps_i) 2962 { 2963 int row; 2964 2965 gcc_assert (ps && ps_i); 2966 2967 row = SMODULO (ps_i->cycle, ps->ii); 2968 if (! ps_i->prev_in_row) 2969 { 2970 gcc_assert (ps_i == ps->rows[row]); 2971 ps->rows[row] = ps_i->next_in_row; 2972 if (ps->rows[row]) 2973 ps->rows[row]->prev_in_row = NULL; 2974 } 2975 else 2976 { 2977 ps_i->prev_in_row->next_in_row = ps_i->next_in_row; 2978 if (ps_i->next_in_row) 2979 ps_i->next_in_row->prev_in_row = ps_i->prev_in_row; 2980 } 2981 2982 ps->rows_length[row] -= 1; 2983 free (ps_i); 2984 return; 2985 } 2986 2987 /* Unlike what literature describes for modulo scheduling (which focuses 2988 on VLIW machines) the order of the instructions inside a cycle is 2989 important. Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know 2990 where the current instruction should go relative to the already 2991 scheduled instructions in the given cycle. Go over these 2992 instructions and find the first possible column to put it in. */ 2993 static bool 2994 ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i, 2995 sbitmap must_precede, sbitmap must_follow) 2996 { 2997 ps_insn_ptr next_ps_i; 2998 ps_insn_ptr first_must_follow = NULL; 2999 ps_insn_ptr last_must_precede = NULL; 3000 ps_insn_ptr last_in_row = NULL; 3001 int row; 3002 3003 if (! ps_i) 3004 return false; 3005 3006 row = SMODULO (ps_i->cycle, ps->ii); 3007 3008 /* Find the first must follow and the last must precede 3009 and insert the node immediately after the must precede 3010 but make sure that it there is no must follow after it. */ 3011 for (next_ps_i = ps->rows[row]; 3012 next_ps_i; 3013 next_ps_i = next_ps_i->next_in_row) 3014 { 3015 if (must_follow 3016 && bitmap_bit_p (must_follow, next_ps_i->id) 3017 && ! first_must_follow) 3018 first_must_follow = next_ps_i; 3019 if (must_precede && bitmap_bit_p (must_precede, next_ps_i->id)) 3020 { 3021 /* If we have already met a node that must follow, then 3022 there is no possible column. */ 3023 if (first_must_follow) 3024 return false; 3025 else 3026 last_must_precede = next_ps_i; 3027 } 3028 /* The closing branch must be the last in the row. */ 3029 if (must_precede 3030 && bitmap_bit_p (must_precede, next_ps_i->id) 3031 && JUMP_P (ps_rtl_insn (ps, next_ps_i->id))) 3032 return false; 3033 3034 last_in_row = next_ps_i; 3035 } 3036 3037 /* The closing branch is scheduled as well. Make sure there is no 3038 dependent instruction after it as the branch should be the last 3039 instruction in the row. */ 3040 if (JUMP_P (ps_rtl_insn (ps, ps_i->id))) 3041 { 3042 if (first_must_follow) 3043 return false; 3044 if (last_in_row) 3045 { 3046 /* Make the branch the last in the row. New instructions 3047 will be inserted at the beginning of the row or after the 3048 last must_precede instruction thus the branch is guaranteed 3049 to remain the last instruction in the row. */ 3050 last_in_row->next_in_row = ps_i; 3051 ps_i->prev_in_row = last_in_row; 3052 ps_i->next_in_row = NULL; 3053 } 3054 else 3055 ps->rows[row] = ps_i; 3056 return true; 3057 } 3058 3059 /* Now insert the node after INSERT_AFTER_PSI. */ 3060 3061 if (! last_must_precede) 3062 { 3063 ps_i->next_in_row = ps->rows[row]; 3064 ps_i->prev_in_row = NULL; 3065 if (ps_i->next_in_row) 3066 ps_i->next_in_row->prev_in_row = ps_i; 3067 ps->rows[row] = ps_i; 3068 } 3069 else 3070 { 3071 ps_i->next_in_row = last_must_precede->next_in_row; 3072 last_must_precede->next_in_row = ps_i; 3073 ps_i->prev_in_row = last_must_precede; 3074 if (ps_i->next_in_row) 3075 ps_i->next_in_row->prev_in_row = ps_i; 3076 } 3077 3078 return true; 3079 } 3080 3081 /* Advances the PS_INSN one column in its current row; returns false 3082 in failure and true in success. Bit N is set in MUST_FOLLOW if 3083 the node with cuid N must be come after the node pointed to by 3084 PS_I when scheduled in the same cycle. */ 3085 static int 3086 ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i, 3087 sbitmap must_follow) 3088 { 3089 ps_insn_ptr prev, next; 3090 int row; 3091 3092 if (!ps || !ps_i) 3093 return false; 3094 3095 row = SMODULO (ps_i->cycle, ps->ii); 3096 3097 if (! ps_i->next_in_row) 3098 return false; 3099 3100 /* Check if next_in_row is dependent on ps_i, both having same sched 3101 times (typically ANTI_DEP). If so, ps_i cannot skip over it. */ 3102 if (must_follow && bitmap_bit_p (must_follow, ps_i->next_in_row->id)) 3103 return false; 3104 3105 /* Advance PS_I over its next_in_row in the doubly linked list. */ 3106 prev = ps_i->prev_in_row; 3107 next = ps_i->next_in_row; 3108 3109 if (ps_i == ps->rows[row]) 3110 ps->rows[row] = next; 3111 3112 ps_i->next_in_row = next->next_in_row; 3113 3114 if (next->next_in_row) 3115 next->next_in_row->prev_in_row = ps_i; 3116 3117 next->next_in_row = ps_i; 3118 ps_i->prev_in_row = next; 3119 3120 next->prev_in_row = prev; 3121 if (prev) 3122 prev->next_in_row = next; 3123 3124 return true; 3125 } 3126 3127 /* Inserts a DDG_NODE to the given partial schedule at the given cycle. 3128 Returns 0 if this is not possible and a PS_INSN otherwise. Bit N is 3129 set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come 3130 before/after (respectively) the node pointed to by PS_I when scheduled 3131 in the same cycle. */ 3132 static ps_insn_ptr 3133 add_node_to_ps (partial_schedule_ptr ps, int id, int cycle, 3134 sbitmap must_precede, sbitmap must_follow) 3135 { 3136 ps_insn_ptr ps_i; 3137 int row = SMODULO (cycle, ps->ii); 3138 3139 if (ps->rows_length[row] >= issue_rate) 3140 return NULL; 3141 3142 ps_i = create_ps_insn (id, cycle); 3143 3144 /* Finds and inserts PS_I according to MUST_FOLLOW and 3145 MUST_PRECEDE. */ 3146 if (! ps_insn_find_column (ps, ps_i, must_precede, must_follow)) 3147 { 3148 free (ps_i); 3149 return NULL; 3150 } 3151 3152 ps->rows_length[row] += 1; 3153 return ps_i; 3154 } 3155 3156 /* Advance time one cycle. Assumes DFA is being used. */ 3157 static void 3158 advance_one_cycle (void) 3159 { 3160 if (targetm.sched.dfa_pre_cycle_insn) 3161 state_transition (curr_state, 3162 targetm.sched.dfa_pre_cycle_insn ()); 3163 3164 state_transition (curr_state, NULL); 3165 3166 if (targetm.sched.dfa_post_cycle_insn) 3167 state_transition (curr_state, 3168 targetm.sched.dfa_post_cycle_insn ()); 3169 } 3170 3171 3172 3173 /* Checks if PS has resource conflicts according to DFA, starting from 3174 FROM cycle to TO cycle; returns true if there are conflicts and false 3175 if there are no conflicts. Assumes DFA is being used. */ 3176 static int 3177 ps_has_conflicts (partial_schedule_ptr ps, int from, int to) 3178 { 3179 int cycle; 3180 3181 state_reset (curr_state); 3182 3183 for (cycle = from; cycle <= to; cycle++) 3184 { 3185 ps_insn_ptr crr_insn; 3186 /* Holds the remaining issue slots in the current row. */ 3187 int can_issue_more = issue_rate; 3188 3189 /* Walk through the DFA for the current row. */ 3190 for (crr_insn = ps->rows[SMODULO (cycle, ps->ii)]; 3191 crr_insn; 3192 crr_insn = crr_insn->next_in_row) 3193 { 3194 rtx_insn *insn = ps_rtl_insn (ps, crr_insn->id); 3195 3196 if (!NONDEBUG_INSN_P (insn)) 3197 continue; 3198 3199 /* Check if there is room for the current insn. */ 3200 if (!can_issue_more || state_dead_lock_p (curr_state)) 3201 return true; 3202 3203 /* Update the DFA state and return with failure if the DFA found 3204 resource conflicts. */ 3205 if (state_transition (curr_state, insn) >= 0) 3206 return true; 3207 3208 if (targetm.sched.variable_issue) 3209 can_issue_more = 3210 targetm.sched.variable_issue (sched_dump, sched_verbose, 3211 insn, can_issue_more); 3212 /* A naked CLOBBER or USE generates no instruction, so don't 3213 let them consume issue slots. */ 3214 else if (GET_CODE (PATTERN (insn)) != USE 3215 && GET_CODE (PATTERN (insn)) != CLOBBER) 3216 can_issue_more--; 3217 } 3218 3219 /* Advance the DFA to the next cycle. */ 3220 advance_one_cycle (); 3221 } 3222 return false; 3223 } 3224 3225 /* Checks if the given node causes resource conflicts when added to PS at 3226 cycle C. If not the node is added to PS and returned; otherwise zero 3227 is returned. Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with 3228 cuid N must be come before/after (respectively) the node pointed to by 3229 PS_I when scheduled in the same cycle. */ 3230 ps_insn_ptr 3231 ps_add_node_check_conflicts (partial_schedule_ptr ps, int n, 3232 int c, sbitmap must_precede, 3233 sbitmap must_follow) 3234 { 3235 int has_conflicts = 0; 3236 ps_insn_ptr ps_i; 3237 3238 /* First add the node to the PS, if this succeeds check for 3239 conflicts, trying different issue slots in the same row. */ 3240 if (! (ps_i = add_node_to_ps (ps, n, c, must_precede, must_follow))) 3241 return NULL; /* Failed to insert the node at the given cycle. */ 3242 3243 has_conflicts = ps_has_conflicts (ps, c, c) 3244 || (ps->history > 0 3245 && ps_has_conflicts (ps, 3246 c - ps->history, 3247 c + ps->history)); 3248 3249 /* Try different issue slots to find one that the given node can be 3250 scheduled in without conflicts. */ 3251 while (has_conflicts) 3252 { 3253 if (! ps_insn_advance_column (ps, ps_i, must_follow)) 3254 break; 3255 has_conflicts = ps_has_conflicts (ps, c, c) 3256 || (ps->history > 0 3257 && ps_has_conflicts (ps, 3258 c - ps->history, 3259 c + ps->history)); 3260 } 3261 3262 if (has_conflicts) 3263 { 3264 remove_node_from_ps (ps, ps_i); 3265 return NULL; 3266 } 3267 3268 ps->min_cycle = MIN (ps->min_cycle, c); 3269 ps->max_cycle = MAX (ps->max_cycle, c); 3270 return ps_i; 3271 } 3272 3273 /* Calculate the stage count of the partial schedule PS. The calculation 3274 takes into account the rotation amount passed in ROTATION_AMOUNT. */ 3275 int 3276 calculate_stage_count (partial_schedule_ptr ps, int rotation_amount) 3277 { 3278 int new_min_cycle = PS_MIN_CYCLE (ps) - rotation_amount; 3279 int new_max_cycle = PS_MAX_CYCLE (ps) - rotation_amount; 3280 int stage_count = CALC_STAGE_COUNT (-1, new_min_cycle, ps->ii); 3281 3282 /* The calculation of stage count is done adding the number of stages 3283 before cycle zero and after cycle zero. */ 3284 stage_count += CALC_STAGE_COUNT (new_max_cycle, 0, ps->ii); 3285 3286 return stage_count; 3287 } 3288 3289 /* Rotate the rows of PS such that insns scheduled at time 3290 START_CYCLE will appear in row 0. Updates max/min_cycles. */ 3291 void 3292 rotate_partial_schedule (partial_schedule_ptr ps, int start_cycle) 3293 { 3294 int i, row, backward_rotates; 3295 int last_row = ps->ii - 1; 3296 3297 if (start_cycle == 0) 3298 return; 3299 3300 backward_rotates = SMODULO (start_cycle, ps->ii); 3301 3302 /* Revisit later and optimize this into a single loop. */ 3303 for (i = 0; i < backward_rotates; i++) 3304 { 3305 ps_insn_ptr first_row = ps->rows[0]; 3306 int first_row_length = ps->rows_length[0]; 3307 3308 for (row = 0; row < last_row; row++) 3309 { 3310 ps->rows[row] = ps->rows[row + 1]; 3311 ps->rows_length[row] = ps->rows_length[row + 1]; 3312 } 3313 3314 ps->rows[last_row] = first_row; 3315 ps->rows_length[last_row] = first_row_length; 3316 } 3317 3318 ps->max_cycle -= start_cycle; 3319 ps->min_cycle -= start_cycle; 3320 } 3321 3322 #endif /* INSN_SCHEDULING */ 3323 3324 /* Run instruction scheduler. */ 3325 /* Perform SMS module scheduling. */ 3326 3327 namespace { 3328 3329 const pass_data pass_data_sms = 3330 { 3331 RTL_PASS, /* type */ 3332 "sms", /* name */ 3333 OPTGROUP_NONE, /* optinfo_flags */ 3334 TV_SMS, /* tv_id */ 3335 0, /* properties_required */ 3336 0, /* properties_provided */ 3337 0, /* properties_destroyed */ 3338 0, /* todo_flags_start */ 3339 TODO_df_finish, /* todo_flags_finish */ 3340 }; 3341 3342 class pass_sms : public rtl_opt_pass 3343 { 3344 public: 3345 pass_sms (gcc::context *ctxt) 3346 : rtl_opt_pass (pass_data_sms, ctxt) 3347 {} 3348 3349 /* opt_pass methods: */ 3350 virtual bool gate (function *) 3351 { 3352 return (optimize > 0 && flag_modulo_sched); 3353 } 3354 3355 virtual unsigned int execute (function *); 3356 3357 }; // class pass_sms 3358 3359 unsigned int 3360 pass_sms::execute (function *fun ATTRIBUTE_UNUSED) 3361 { 3362 #ifdef INSN_SCHEDULING 3363 basic_block bb; 3364 3365 /* Collect loop information to be used in SMS. */ 3366 cfg_layout_initialize (0); 3367 sms_schedule (); 3368 3369 /* Update the life information, because we add pseudos. */ 3370 max_regno = max_reg_num (); 3371 3372 /* Finalize layout changes. */ 3373 FOR_EACH_BB_FN (bb, fun) 3374 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun)) 3375 bb->aux = bb->next_bb; 3376 free_dominance_info (CDI_DOMINATORS); 3377 cfg_layout_finalize (); 3378 #endif /* INSN_SCHEDULING */ 3379 return 0; 3380 } 3381 3382 } // anon namespace 3383 3384 rtl_opt_pass * 3385 make_pass_sms (gcc::context *ctxt) 3386 { 3387 return new pass_sms (ctxt); 3388 } 3389