1 /* Vectorizer Specific Loop Manipulations 2 Copyright (C) 2003-2013 Free Software Foundation, Inc. 3 Contributed by Dorit Naishlos <dorit@il.ibm.com> 4 and Ira Rosen <irar@il.ibm.com> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #include "config.h" 23 #include "system.h" 24 #include "coretypes.h" 25 #include "dumpfile.h" 26 #include "tm.h" 27 #include "ggc.h" 28 #include "tree.h" 29 #include "basic-block.h" 30 #include "gimple-pretty-print.h" 31 #include "tree-flow.h" 32 #include "tree-pass.h" 33 #include "cfgloop.h" 34 #include "diagnostic-core.h" 35 #include "tree-scalar-evolution.h" 36 #include "tree-vectorizer.h" 37 #include "langhooks.h" 38 39 /************************************************************************* 40 Simple Loop Peeling Utilities 41 42 Utilities to support loop peeling for vectorization purposes. 43 *************************************************************************/ 44 45 46 /* Renames the use *OP_P. */ 47 48 static void 49 rename_use_op (use_operand_p op_p) 50 { 51 tree new_name; 52 53 if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME) 54 return; 55 56 new_name = get_current_def (USE_FROM_PTR (op_p)); 57 58 /* Something defined outside of the loop. */ 59 if (!new_name) 60 return; 61 62 /* An ordinary ssa name defined in the loop. */ 63 64 SET_USE (op_p, new_name); 65 } 66 67 68 /* Renames the variables in basic block BB. */ 69 70 static void 71 rename_variables_in_bb (basic_block bb) 72 { 73 gimple_stmt_iterator gsi; 74 gimple stmt; 75 use_operand_p use_p; 76 ssa_op_iter iter; 77 edge e; 78 edge_iterator ei; 79 struct loop *loop = bb->loop_father; 80 81 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 82 { 83 stmt = gsi_stmt (gsi); 84 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 85 rename_use_op (use_p); 86 } 87 88 FOR_EACH_EDGE (e, ei, bb->preds) 89 { 90 if (!flow_bb_inside_loop_p (loop, e->src)) 91 continue; 92 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 93 rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (gsi_stmt (gsi), e)); 94 } 95 } 96 97 98 typedef struct 99 { 100 tree from, to; 101 basic_block bb; 102 } adjust_info; 103 104 /* A stack of values to be adjusted in debug stmts. We have to 105 process them LIFO, so that the closest substitution applies. If we 106 processed them FIFO, without the stack, we might substitute uses 107 with a PHI DEF that would soon become non-dominant, and when we got 108 to the suitable one, it wouldn't have anything to substitute any 109 more. */ 110 static vec<adjust_info, va_stack> adjust_vec; 111 112 /* Adjust any debug stmts that referenced AI->from values to use the 113 loop-closed AI->to, if the references are dominated by AI->bb and 114 not by the definition of AI->from. */ 115 116 static void 117 adjust_debug_stmts_now (adjust_info *ai) 118 { 119 basic_block bbphi = ai->bb; 120 tree orig_def = ai->from; 121 tree new_def = ai->to; 122 imm_use_iterator imm_iter; 123 gimple stmt; 124 basic_block bbdef = gimple_bb (SSA_NAME_DEF_STMT (orig_def)); 125 126 gcc_assert (dom_info_available_p (CDI_DOMINATORS)); 127 128 /* Adjust any debug stmts that held onto non-loop-closed 129 references. */ 130 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, orig_def) 131 { 132 use_operand_p use_p; 133 basic_block bbuse; 134 135 if (!is_gimple_debug (stmt)) 136 continue; 137 138 gcc_assert (gimple_debug_bind_p (stmt)); 139 140 bbuse = gimple_bb (stmt); 141 142 if ((bbuse == bbphi 143 || dominated_by_p (CDI_DOMINATORS, bbuse, bbphi)) 144 && !(bbuse == bbdef 145 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))) 146 { 147 if (new_def) 148 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) 149 SET_USE (use_p, new_def); 150 else 151 { 152 gimple_debug_bind_reset_value (stmt); 153 update_stmt (stmt); 154 } 155 } 156 } 157 } 158 159 /* Adjust debug stmts as scheduled before. */ 160 161 static void 162 adjust_vec_debug_stmts (void) 163 { 164 if (!MAY_HAVE_DEBUG_STMTS) 165 return; 166 167 gcc_assert (adjust_vec.exists ()); 168 169 while (!adjust_vec.is_empty ()) 170 { 171 adjust_debug_stmts_now (&adjust_vec.last ()); 172 adjust_vec.pop (); 173 } 174 175 adjust_vec.release (); 176 } 177 178 /* Adjust any debug stmts that referenced FROM values to use the 179 loop-closed TO, if the references are dominated by BB and not by 180 the definition of FROM. If adjust_vec is non-NULL, adjustments 181 will be postponed until adjust_vec_debug_stmts is called. */ 182 183 static void 184 adjust_debug_stmts (tree from, tree to, basic_block bb) 185 { 186 adjust_info ai; 187 188 if (MAY_HAVE_DEBUG_STMTS 189 && TREE_CODE (from) == SSA_NAME 190 && ! SSA_NAME_IS_DEFAULT_DEF (from) 191 && ! virtual_operand_p (from)) 192 { 193 ai.from = from; 194 ai.to = to; 195 ai.bb = bb; 196 197 if (adjust_vec.exists ()) 198 adjust_vec.safe_push (ai); 199 else 200 adjust_debug_stmts_now (&ai); 201 } 202 } 203 204 /* Change E's phi arg in UPDATE_PHI to NEW_DEF, and record information 205 to adjust any debug stmts that referenced the old phi arg, 206 presumably non-loop-closed references left over from other 207 transformations. */ 208 209 static void 210 adjust_phi_and_debug_stmts (gimple update_phi, edge e, tree new_def) 211 { 212 tree orig_def = PHI_ARG_DEF_FROM_EDGE (update_phi, e); 213 214 SET_PHI_ARG_DEF (update_phi, e->dest_idx, new_def); 215 216 if (MAY_HAVE_DEBUG_STMTS) 217 adjust_debug_stmts (orig_def, PHI_RESULT (update_phi), 218 gimple_bb (update_phi)); 219 } 220 221 222 /* Update PHI nodes for a guard of the LOOP. 223 224 Input: 225 - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that 226 controls whether LOOP is to be executed. GUARD_EDGE is the edge that 227 originates from the guard-bb, skips LOOP and reaches the (unique) exit 228 bb of LOOP. This loop-exit-bb is an empty bb with one successor. 229 We denote this bb NEW_MERGE_BB because before the guard code was added 230 it had a single predecessor (the LOOP header), and now it became a merge 231 point of two paths - the path that ends with the LOOP exit-edge, and 232 the path that ends with GUARD_EDGE. 233 - NEW_EXIT_BB: New basic block that is added by this function between LOOP 234 and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis. 235 236 ===> The CFG before the guard-code was added: 237 LOOP_header_bb: 238 loop_body 239 if (exit_loop) goto update_bb 240 else goto LOOP_header_bb 241 update_bb: 242 243 ==> The CFG after the guard-code was added: 244 guard_bb: 245 if (LOOP_guard_condition) goto new_merge_bb 246 else goto LOOP_header_bb 247 LOOP_header_bb: 248 loop_body 249 if (exit_loop_condition) goto new_merge_bb 250 else goto LOOP_header_bb 251 new_merge_bb: 252 goto update_bb 253 update_bb: 254 255 ==> The CFG after this function: 256 guard_bb: 257 if (LOOP_guard_condition) goto new_merge_bb 258 else goto LOOP_header_bb 259 LOOP_header_bb: 260 loop_body 261 if (exit_loop_condition) goto new_exit_bb 262 else goto LOOP_header_bb 263 new_exit_bb: 264 new_merge_bb: 265 goto update_bb 266 update_bb: 267 268 This function: 269 1. creates and updates the relevant phi nodes to account for the new 270 incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves: 271 1.1. Create phi nodes at NEW_MERGE_BB. 272 1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted 273 UPDATE_BB). UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB 274 2. preserves loop-closed-ssa-form by creating the required phi nodes 275 at the exit of LOOP (i.e, in NEW_EXIT_BB). 276 277 There are two flavors to this function: 278 279 slpeel_update_phi_nodes_for_guard1: 280 Here the guard controls whether we enter or skip LOOP, where LOOP is a 281 prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are 282 for variables that have phis in the loop header. 283 284 slpeel_update_phi_nodes_for_guard2: 285 Here the guard controls whether we enter or skip LOOP, where LOOP is an 286 epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are 287 for variables that have phis in the loop exit. 288 289 I.E., the overall structure is: 290 291 loop1_preheader_bb: 292 guard1 (goto loop1/merge1_bb) 293 loop1 294 loop1_exit_bb: 295 guard2 (goto merge1_bb/merge2_bb) 296 merge1_bb 297 loop2 298 loop2_exit_bb 299 merge2_bb 300 next_bb 301 302 slpeel_update_phi_nodes_for_guard1 takes care of creating phis in 303 loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars 304 that have phis in loop1->header). 305 306 slpeel_update_phi_nodes_for_guard2 takes care of creating phis in 307 loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars 308 that have phis in next_bb). It also adds some of these phis to 309 loop1_exit_bb. 310 311 slpeel_update_phi_nodes_for_guard1 is always called before 312 slpeel_update_phi_nodes_for_guard2. They are both needed in order 313 to create correct data-flow and loop-closed-ssa-form. 314 315 Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables 316 that change between iterations of a loop (and therefore have a phi-node 317 at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates 318 phis for variables that are used out of the loop (and therefore have 319 loop-closed exit phis). Some variables may be both updated between 320 iterations and used after the loop. This is why in loop1_exit_bb we 321 may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1) 322 and exit phis (created by slpeel_update_phi_nodes_for_guard2). 323 324 - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of 325 an original loop. i.e., we have: 326 327 orig_loop 328 guard_bb (goto LOOP/new_merge) 329 new_loop <-- LOOP 330 new_exit 331 new_merge 332 next_bb 333 334 If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we 335 have: 336 337 new_loop 338 guard_bb (goto LOOP/new_merge) 339 orig_loop <-- LOOP 340 new_exit 341 new_merge 342 next_bb 343 344 The SSA names defined in the original loop have a current 345 reaching definition that that records the corresponding new 346 ssa-name used in the new duplicated loop copy. 347 */ 348 349 /* Function slpeel_update_phi_nodes_for_guard1 350 351 Input: 352 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above. 353 - DEFS - a bitmap of ssa names to mark new names for which we recorded 354 information. 355 356 In the context of the overall structure, we have: 357 358 loop1_preheader_bb: 359 guard1 (goto loop1/merge1_bb) 360 LOOP-> loop1 361 loop1_exit_bb: 362 guard2 (goto merge1_bb/merge2_bb) 363 merge1_bb 364 loop2 365 loop2_exit_bb 366 merge2_bb 367 next_bb 368 369 For each name updated between loop iterations (i.e - for each name that has 370 an entry (loop-header) phi in LOOP) we create a new phi in: 371 1. merge1_bb (to account for the edge from guard1) 372 2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form) 373 */ 374 375 static void 376 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop, 377 bool is_new_loop, basic_block *new_exit_bb) 378 { 379 gimple orig_phi, new_phi; 380 gimple update_phi, update_phi2; 381 tree guard_arg, loop_arg; 382 basic_block new_merge_bb = guard_edge->dest; 383 edge e = EDGE_SUCC (new_merge_bb, 0); 384 basic_block update_bb = e->dest; 385 basic_block orig_bb = loop->header; 386 edge new_exit_e; 387 tree current_new_name; 388 gimple_stmt_iterator gsi_orig, gsi_update; 389 390 /* Create new bb between loop and new_merge_bb. */ 391 *new_exit_bb = split_edge (single_exit (loop)); 392 393 new_exit_e = EDGE_SUCC (*new_exit_bb, 0); 394 395 for (gsi_orig = gsi_start_phis (orig_bb), 396 gsi_update = gsi_start_phis (update_bb); 397 !gsi_end_p (gsi_orig) && !gsi_end_p (gsi_update); 398 gsi_next (&gsi_orig), gsi_next (&gsi_update)) 399 { 400 source_location loop_locus, guard_locus; 401 tree new_res; 402 orig_phi = gsi_stmt (gsi_orig); 403 update_phi = gsi_stmt (gsi_update); 404 405 /** 1. Handle new-merge-point phis **/ 406 407 /* 1.1. Generate new phi node in NEW_MERGE_BB: */ 408 new_res = copy_ssa_name (PHI_RESULT (orig_phi), NULL); 409 new_phi = create_phi_node (new_res, new_merge_bb); 410 411 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge 412 of LOOP. Set the two phi args in NEW_PHI for these edges: */ 413 loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0)); 414 loop_locus = gimple_phi_arg_location_from_edge (orig_phi, 415 EDGE_SUCC (loop->latch, 416 0)); 417 guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop)); 418 guard_locus 419 = gimple_phi_arg_location_from_edge (orig_phi, 420 loop_preheader_edge (loop)); 421 422 add_phi_arg (new_phi, loop_arg, new_exit_e, loop_locus); 423 add_phi_arg (new_phi, guard_arg, guard_edge, guard_locus); 424 425 /* 1.3. Update phi in successor block. */ 426 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg 427 || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg); 428 adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi)); 429 update_phi2 = new_phi; 430 431 432 /** 2. Handle loop-closed-ssa-form phis **/ 433 434 if (virtual_operand_p (PHI_RESULT (orig_phi))) 435 continue; 436 437 /* 2.1. Generate new phi node in NEW_EXIT_BB: */ 438 new_res = copy_ssa_name (PHI_RESULT (orig_phi), NULL); 439 new_phi = create_phi_node (new_res, *new_exit_bb); 440 441 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */ 442 add_phi_arg (new_phi, loop_arg, single_exit (loop), loop_locus); 443 444 /* 2.3. Update phi in successor of NEW_EXIT_BB: */ 445 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg); 446 adjust_phi_and_debug_stmts (update_phi2, new_exit_e, 447 PHI_RESULT (new_phi)); 448 449 /* 2.4. Record the newly created name with set_current_def. 450 We want to find a name such that 451 name = get_current_def (orig_loop_name) 452 and to set its current definition as follows: 453 set_current_def (name, new_phi_name) 454 455 If LOOP is a new loop then loop_arg is already the name we're 456 looking for. If LOOP is the original loop, then loop_arg is 457 the orig_loop_name and the relevant name is recorded in its 458 current reaching definition. */ 459 if (is_new_loop) 460 current_new_name = loop_arg; 461 else 462 { 463 current_new_name = get_current_def (loop_arg); 464 /* current_def is not available only if the variable does not 465 change inside the loop, in which case we also don't care 466 about recording a current_def for it because we won't be 467 trying to create loop-exit-phis for it. */ 468 if (!current_new_name) 469 continue; 470 } 471 gcc_assert (get_current_def (current_new_name) == NULL_TREE); 472 473 set_current_def (current_new_name, PHI_RESULT (new_phi)); 474 } 475 } 476 477 478 /* Function slpeel_update_phi_nodes_for_guard2 479 480 Input: 481 - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above. 482 483 In the context of the overall structure, we have: 484 485 loop1_preheader_bb: 486 guard1 (goto loop1/merge1_bb) 487 loop1 488 loop1_exit_bb: 489 guard2 (goto merge1_bb/merge2_bb) 490 merge1_bb 491 LOOP-> loop2 492 loop2_exit_bb 493 merge2_bb 494 next_bb 495 496 For each name used out side the loop (i.e - for each name that has an exit 497 phi in next_bb) we create a new phi in: 498 1. merge2_bb (to account for the edge from guard_bb) 499 2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form) 500 3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form), 501 if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1). 502 */ 503 504 static void 505 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop, 506 bool is_new_loop, basic_block *new_exit_bb) 507 { 508 gimple orig_phi, new_phi; 509 gimple update_phi, update_phi2; 510 tree guard_arg, loop_arg; 511 basic_block new_merge_bb = guard_edge->dest; 512 edge e = EDGE_SUCC (new_merge_bb, 0); 513 basic_block update_bb = e->dest; 514 edge new_exit_e; 515 tree orig_def, orig_def_new_name; 516 tree new_name, new_name2; 517 tree arg; 518 gimple_stmt_iterator gsi; 519 520 /* Create new bb between loop and new_merge_bb. */ 521 *new_exit_bb = split_edge (single_exit (loop)); 522 523 new_exit_e = EDGE_SUCC (*new_exit_bb, 0); 524 525 for (gsi = gsi_start_phis (update_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 526 { 527 tree new_res; 528 update_phi = gsi_stmt (gsi); 529 orig_phi = update_phi; 530 orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e); 531 /* This loop-closed-phi actually doesn't represent a use 532 out of the loop - the phi arg is a constant. */ 533 if (TREE_CODE (orig_def) != SSA_NAME) 534 continue; 535 orig_def_new_name = get_current_def (orig_def); 536 arg = NULL_TREE; 537 538 /** 1. Handle new-merge-point phis **/ 539 540 /* 1.1. Generate new phi node in NEW_MERGE_BB: */ 541 new_res = copy_ssa_name (PHI_RESULT (orig_phi), NULL); 542 new_phi = create_phi_node (new_res, new_merge_bb); 543 544 /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge 545 of LOOP. Set the two PHI args in NEW_PHI for these edges: */ 546 new_name = orig_def; 547 new_name2 = NULL_TREE; 548 if (orig_def_new_name) 549 { 550 new_name = orig_def_new_name; 551 /* Some variables have both loop-entry-phis and loop-exit-phis. 552 Such variables were given yet newer names by phis placed in 553 guard_bb by slpeel_update_phi_nodes_for_guard1. I.e: 554 new_name2 = get_current_def (get_current_def (orig_name)). */ 555 new_name2 = get_current_def (new_name); 556 } 557 558 if (is_new_loop) 559 { 560 guard_arg = orig_def; 561 loop_arg = new_name; 562 } 563 else 564 { 565 guard_arg = new_name; 566 loop_arg = orig_def; 567 } 568 if (new_name2) 569 guard_arg = new_name2; 570 571 add_phi_arg (new_phi, loop_arg, new_exit_e, UNKNOWN_LOCATION); 572 add_phi_arg (new_phi, guard_arg, guard_edge, UNKNOWN_LOCATION); 573 574 /* 1.3. Update phi in successor block. */ 575 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def); 576 adjust_phi_and_debug_stmts (update_phi, e, PHI_RESULT (new_phi)); 577 update_phi2 = new_phi; 578 579 580 /** 2. Handle loop-closed-ssa-form phis **/ 581 582 /* 2.1. Generate new phi node in NEW_EXIT_BB: */ 583 new_res = copy_ssa_name (PHI_RESULT (orig_phi), NULL); 584 new_phi = create_phi_node (new_res, *new_exit_bb); 585 586 /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */ 587 add_phi_arg (new_phi, loop_arg, single_exit (loop), UNKNOWN_LOCATION); 588 589 /* 2.3. Update phi in successor of NEW_EXIT_BB: */ 590 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg); 591 adjust_phi_and_debug_stmts (update_phi2, new_exit_e, 592 PHI_RESULT (new_phi)); 593 594 595 /** 3. Handle loop-closed-ssa-form phis for first loop **/ 596 597 /* 3.1. Find the relevant names that need an exit-phi in 598 GUARD_BB, i.e. names for which 599 slpeel_update_phi_nodes_for_guard1 had not already created a 600 phi node. This is the case for names that are used outside 601 the loop (and therefore need an exit phi) but are not updated 602 across loop iterations (and therefore don't have a 603 loop-header-phi). 604 605 slpeel_update_phi_nodes_for_guard1 is responsible for 606 creating loop-exit phis in GUARD_BB for names that have a 607 loop-header-phi. When such a phi is created we also record 608 the new name in its current definition. If this new name 609 exists, then guard_arg was set to this new name (see 1.2 610 above). Therefore, if guard_arg is not this new name, this 611 is an indication that an exit-phi in GUARD_BB was not yet 612 created, so we take care of it here. */ 613 if (guard_arg == new_name2) 614 continue; 615 arg = guard_arg; 616 617 /* 3.2. Generate new phi node in GUARD_BB: */ 618 new_res = copy_ssa_name (PHI_RESULT (orig_phi), NULL); 619 new_phi = create_phi_node (new_res, guard_edge->src); 620 621 /* 3.3. GUARD_BB has one incoming edge: */ 622 gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1); 623 add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0), 624 UNKNOWN_LOCATION); 625 626 /* 3.4. Update phi in successor of GUARD_BB: */ 627 gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge) 628 == guard_arg); 629 adjust_phi_and_debug_stmts (update_phi2, guard_edge, 630 PHI_RESULT (new_phi)); 631 } 632 } 633 634 635 /* Make the LOOP iterate NITERS times. This is done by adding a new IV 636 that starts at zero, increases by one and its limit is NITERS. 637 638 Assumption: the exit-condition of LOOP is the last stmt in the loop. */ 639 640 void 641 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters) 642 { 643 tree indx_before_incr, indx_after_incr; 644 gimple cond_stmt; 645 gimple orig_cond; 646 edge exit_edge = single_exit (loop); 647 gimple_stmt_iterator loop_cond_gsi; 648 gimple_stmt_iterator incr_gsi; 649 bool insert_after; 650 tree init = build_int_cst (TREE_TYPE (niters), 0); 651 tree step = build_int_cst (TREE_TYPE (niters), 1); 652 LOC loop_loc; 653 enum tree_code code; 654 655 orig_cond = get_loop_exit_condition (loop); 656 gcc_assert (orig_cond); 657 loop_cond_gsi = gsi_for_stmt (orig_cond); 658 659 standard_iv_increment_position (loop, &incr_gsi, &insert_after); 660 create_iv (init, step, NULL_TREE, loop, 661 &incr_gsi, insert_after, &indx_before_incr, &indx_after_incr); 662 663 indx_after_incr = force_gimple_operand_gsi (&loop_cond_gsi, indx_after_incr, 664 true, NULL_TREE, true, 665 GSI_SAME_STMT); 666 niters = force_gimple_operand_gsi (&loop_cond_gsi, niters, true, NULL_TREE, 667 true, GSI_SAME_STMT); 668 669 code = (exit_edge->flags & EDGE_TRUE_VALUE) ? GE_EXPR : LT_EXPR; 670 cond_stmt = gimple_build_cond (code, indx_after_incr, niters, NULL_TREE, 671 NULL_TREE); 672 673 gsi_insert_before (&loop_cond_gsi, cond_stmt, GSI_SAME_STMT); 674 675 /* Remove old loop exit test: */ 676 gsi_remove (&loop_cond_gsi, true); 677 free_stmt_vec_info (orig_cond); 678 679 loop_loc = find_loop_location (loop); 680 if (dump_enabled_p ()) 681 { 682 if (LOCATION_LOCUS (loop_loc) != UNKNOWN_LOC) 683 dump_printf (MSG_NOTE, "\nloop at %s:%d: ", LOC_FILE (loop_loc), 684 LOC_LINE (loop_loc)); 685 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, cond_stmt, 0); 686 } 687 loop->nb_iterations = niters; 688 } 689 690 691 /* Given LOOP this function generates a new copy of it and puts it 692 on E which is either the entry or exit of LOOP. */ 693 694 struct loop * 695 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e) 696 { 697 struct loop *new_loop; 698 basic_block *new_bbs, *bbs; 699 bool at_exit; 700 bool was_imm_dom; 701 basic_block exit_dest; 702 edge exit, new_exit; 703 704 exit = single_exit (loop); 705 at_exit = (e == exit); 706 if (!at_exit && e != loop_preheader_edge (loop)) 707 return NULL; 708 709 bbs = XNEWVEC (basic_block, loop->num_nodes + 1); 710 get_loop_body_with_size (loop, bbs, loop->num_nodes); 711 712 /* Check whether duplication is possible. */ 713 if (!can_copy_bbs_p (bbs, loop->num_nodes)) 714 { 715 free (bbs); 716 return NULL; 717 } 718 719 /* Generate new loop structure. */ 720 new_loop = duplicate_loop (loop, loop_outer (loop)); 721 duplicate_subloops (loop, new_loop); 722 723 exit_dest = exit->dest; 724 was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS, 725 exit_dest) == loop->header ? 726 true : false); 727 728 /* Also copy the pre-header, this avoids jumping through hoops to 729 duplicate the loop entry PHI arguments. Create an empty 730 pre-header unconditionally for this. */ 731 basic_block preheader = split_edge (loop_preheader_edge (loop)); 732 edge entry_e = single_pred_edge (preheader); 733 bbs[loop->num_nodes] = preheader; 734 new_bbs = XNEWVEC (basic_block, loop->num_nodes + 1); 735 736 copy_bbs (bbs, loop->num_nodes + 1, new_bbs, 737 &exit, 1, &new_exit, NULL, 738 e->src); 739 basic_block new_preheader = new_bbs[loop->num_nodes]; 740 741 add_phi_args_after_copy (new_bbs, loop->num_nodes + 1, NULL); 742 743 if (at_exit) /* Add the loop copy at exit. */ 744 { 745 redirect_edge_and_branch_force (e, new_preheader); 746 flush_pending_stmts (e); 747 set_immediate_dominator (CDI_DOMINATORS, new_preheader, e->src); 748 if (was_imm_dom) 749 set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header); 750 751 /* And remove the non-necessary forwarder again. Keep the other 752 one so we have a proper pre-header for the loop at the exit edge. */ 753 redirect_edge_pred (single_succ_edge (preheader), single_pred (preheader)); 754 delete_basic_block (preheader); 755 set_immediate_dominator (CDI_DOMINATORS, loop->header, 756 loop_preheader_edge (loop)->src); 757 } 758 else /* Add the copy at entry. */ 759 { 760 redirect_edge_and_branch_force (entry_e, new_preheader); 761 flush_pending_stmts (entry_e); 762 set_immediate_dominator (CDI_DOMINATORS, new_preheader, entry_e->src); 763 764 redirect_edge_and_branch_force (new_exit, preheader); 765 flush_pending_stmts (new_exit); 766 set_immediate_dominator (CDI_DOMINATORS, preheader, new_exit->src); 767 768 /* And remove the non-necessary forwarder again. Keep the other 769 one so we have a proper pre-header for the loop at the exit edge. */ 770 redirect_edge_pred (single_succ_edge (new_preheader), single_pred (new_preheader)); 771 delete_basic_block (new_preheader); 772 set_immediate_dominator (CDI_DOMINATORS, new_loop->header, 773 loop_preheader_edge (new_loop)->src); 774 } 775 776 for (unsigned i = 0; i < loop->num_nodes+1; i++) 777 rename_variables_in_bb (new_bbs[i]); 778 779 free (new_bbs); 780 free (bbs); 781 782 #ifdef ENABLE_CHECKING 783 verify_dominators (CDI_DOMINATORS); 784 #endif 785 786 return new_loop; 787 } 788 789 790 /* Given the condition statement COND, put it as the last statement 791 of GUARD_BB; EXIT_BB is the basic block to skip the loop; 792 Assumes that this is the single exit of the guarded loop. 793 Returns the skip edge, inserts new stmts on the COND_EXPR_STMT_LIST. */ 794 795 static edge 796 slpeel_add_loop_guard (basic_block guard_bb, tree cond, 797 gimple_seq cond_expr_stmt_list, 798 basic_block exit_bb, basic_block dom_bb, 799 int probability) 800 { 801 gimple_stmt_iterator gsi; 802 edge new_e, enter_e; 803 gimple cond_stmt; 804 gimple_seq gimplify_stmt_list = NULL; 805 806 enter_e = EDGE_SUCC (guard_bb, 0); 807 enter_e->flags &= ~EDGE_FALLTHRU; 808 enter_e->flags |= EDGE_FALSE_VALUE; 809 gsi = gsi_last_bb (guard_bb); 810 811 cond = force_gimple_operand_1 (cond, &gimplify_stmt_list, is_gimple_condexpr, 812 NULL_TREE); 813 if (gimplify_stmt_list) 814 gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list); 815 cond_stmt = gimple_build_cond_from_tree (cond, NULL_TREE, NULL_TREE); 816 if (cond_expr_stmt_list) 817 gsi_insert_seq_after (&gsi, cond_expr_stmt_list, GSI_NEW_STMT); 818 819 gsi = gsi_last_bb (guard_bb); 820 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); 821 822 /* Add new edge to connect guard block to the merge/loop-exit block. */ 823 new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE); 824 825 new_e->count = guard_bb->count; 826 new_e->probability = probability; 827 new_e->count = apply_probability (enter_e->count, probability); 828 enter_e->count -= new_e->count; 829 enter_e->probability = inverse_probability (probability); 830 set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb); 831 return new_e; 832 } 833 834 835 /* This function verifies that the following restrictions apply to LOOP: 836 (1) it is innermost 837 (2) it consists of exactly 2 basic blocks - header, and an empty latch. 838 (3) it is single entry, single exit 839 (4) its exit condition is the last stmt in the header 840 (5) E is the entry/exit edge of LOOP. 841 */ 842 843 bool 844 slpeel_can_duplicate_loop_p (const struct loop *loop, const_edge e) 845 { 846 edge exit_e = single_exit (loop); 847 edge entry_e = loop_preheader_edge (loop); 848 gimple orig_cond = get_loop_exit_condition (loop); 849 gimple_stmt_iterator loop_exit_gsi = gsi_last_bb (exit_e->src); 850 851 if (need_ssa_update_p (cfun)) 852 return false; 853 854 if (loop->inner 855 /* All loops have an outer scope; the only case loop->outer is NULL is for 856 the function itself. */ 857 || !loop_outer (loop) 858 || loop->num_nodes != 2 859 || !empty_block_p (loop->latch) 860 || !single_exit (loop) 861 /* Verify that new loop exit condition can be trivially modified. */ 862 || (!orig_cond || orig_cond != gsi_stmt (loop_exit_gsi)) 863 || (e != exit_e && e != entry_e)) 864 return false; 865 866 return true; 867 } 868 869 #ifdef ENABLE_CHECKING 870 static void 871 slpeel_verify_cfg_after_peeling (struct loop *first_loop, 872 struct loop *second_loop) 873 { 874 basic_block loop1_exit_bb = single_exit (first_loop)->dest; 875 basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src; 876 basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src; 877 878 /* A guard that controls whether the second_loop is to be executed or skipped 879 is placed in first_loop->exit. first_loop->exit therefore has two 880 successors - one is the preheader of second_loop, and the other is a bb 881 after second_loop. 882 */ 883 gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2); 884 885 /* 1. Verify that one of the successors of first_loop->exit is the preheader 886 of second_loop. */ 887 888 /* The preheader of new_loop is expected to have two predecessors: 889 first_loop->exit and the block that precedes first_loop. */ 890 891 gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2 892 && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb 893 && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb) 894 || (EDGE_PRED (loop2_entry_bb, 1)->src == loop1_exit_bb 895 && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb))); 896 897 /* Verify that the other successor of first_loop->exit is after the 898 second_loop. */ 899 /* TODO */ 900 } 901 #endif 902 903 /* If the run time cost model check determines that vectorization is 904 not profitable and hence scalar loop should be generated then set 905 FIRST_NITERS to prologue peeled iterations. This will allow all the 906 iterations to be executed in the prologue peeled scalar loop. */ 907 908 static void 909 set_prologue_iterations (basic_block bb_before_first_loop, 910 tree *first_niters, 911 struct loop *loop, 912 unsigned int th, 913 int probability) 914 { 915 edge e; 916 basic_block cond_bb, then_bb; 917 tree var, prologue_after_cost_adjust_name; 918 gimple_stmt_iterator gsi; 919 gimple newphi; 920 edge e_true, e_false, e_fallthru; 921 gimple cond_stmt; 922 gimple_seq stmts = NULL; 923 tree cost_pre_condition = NULL_TREE; 924 tree scalar_loop_iters = 925 unshare_expr (LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop))); 926 927 e = single_pred_edge (bb_before_first_loop); 928 cond_bb = split_edge(e); 929 930 e = single_pred_edge (bb_before_first_loop); 931 then_bb = split_edge(e); 932 set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb); 933 934 e_false = make_single_succ_edge (cond_bb, bb_before_first_loop, 935 EDGE_FALSE_VALUE); 936 set_immediate_dominator (CDI_DOMINATORS, bb_before_first_loop, cond_bb); 937 938 e_true = EDGE_PRED (then_bb, 0); 939 e_true->flags &= ~EDGE_FALLTHRU; 940 e_true->flags |= EDGE_TRUE_VALUE; 941 942 e_true->probability = probability; 943 e_false->probability = inverse_probability (probability); 944 e_true->count = apply_probability (cond_bb->count, probability); 945 e_false->count = cond_bb->count - e_true->count; 946 then_bb->frequency = EDGE_FREQUENCY (e_true); 947 then_bb->count = e_true->count; 948 949 e_fallthru = EDGE_SUCC (then_bb, 0); 950 e_fallthru->count = then_bb->count; 951 952 gsi = gsi_last_bb (cond_bb); 953 cost_pre_condition = 954 fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters, 955 build_int_cst (TREE_TYPE (scalar_loop_iters), th)); 956 cost_pre_condition = 957 force_gimple_operand_gsi_1 (&gsi, cost_pre_condition, is_gimple_condexpr, 958 NULL_TREE, false, GSI_CONTINUE_LINKING); 959 cond_stmt = gimple_build_cond_from_tree (cost_pre_condition, 960 NULL_TREE, NULL_TREE); 961 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); 962 963 var = create_tmp_var (TREE_TYPE (scalar_loop_iters), 964 "prologue_after_cost_adjust"); 965 prologue_after_cost_adjust_name = 966 force_gimple_operand (scalar_loop_iters, &stmts, false, var); 967 968 gsi = gsi_last_bb (then_bb); 969 if (stmts) 970 gsi_insert_seq_after (&gsi, stmts, GSI_NEW_STMT); 971 972 newphi = create_phi_node (var, bb_before_first_loop); 973 add_phi_arg (newphi, prologue_after_cost_adjust_name, e_fallthru, 974 UNKNOWN_LOCATION); 975 add_phi_arg (newphi, *first_niters, e_false, UNKNOWN_LOCATION); 976 977 *first_niters = PHI_RESULT (newphi); 978 } 979 980 /* Function slpeel_tree_peel_loop_to_edge. 981 982 Peel the first (last) iterations of LOOP into a new prolog (epilog) loop 983 that is placed on the entry (exit) edge E of LOOP. After this transformation 984 we have two loops one after the other - first-loop iterates FIRST_NITERS 985 times, and second-loop iterates the remainder NITERS - FIRST_NITERS times. 986 If the cost model indicates that it is profitable to emit a scalar 987 loop instead of the vector one, then the prolog (epilog) loop will iterate 988 for the entire unchanged scalar iterations of the loop. 989 990 Input: 991 - LOOP: the loop to be peeled. 992 - E: the exit or entry edge of LOOP. 993 If it is the entry edge, we peel the first iterations of LOOP. In this 994 case first-loop is LOOP, and second-loop is the newly created loop. 995 If it is the exit edge, we peel the last iterations of LOOP. In this 996 case, first-loop is the newly created loop, and second-loop is LOOP. 997 - NITERS: the number of iterations that LOOP iterates. 998 - FIRST_NITERS: the number of iterations that the first-loop should iterate. 999 - UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible 1000 for updating the loop bound of the first-loop to FIRST_NITERS. If it 1001 is false, the caller of this function may want to take care of this 1002 (this can be useful if we don't want new stmts added to first-loop). 1003 - TH: cost model profitability threshold of iterations for vectorization. 1004 - CHECK_PROFITABILITY: specify whether cost model check has not occurred 1005 during versioning and hence needs to occur during 1006 prologue generation or whether cost model check 1007 has not occurred during prologue generation and hence 1008 needs to occur during epilogue generation. 1009 - BOUND1 is the upper bound on number of iterations of the first loop (if known) 1010 - BOUND2 is the upper bound on number of iterations of the second loop (if known) 1011 1012 1013 Output: 1014 The function returns a pointer to the new loop-copy, or NULL if it failed 1015 to perform the transformation. 1016 1017 The function generates two if-then-else guards: one before the first loop, 1018 and the other before the second loop: 1019 The first guard is: 1020 if (FIRST_NITERS == 0) then skip the first loop, 1021 and go directly to the second loop. 1022 The second guard is: 1023 if (FIRST_NITERS == NITERS) then skip the second loop. 1024 1025 If the optional COND_EXPR and COND_EXPR_STMT_LIST arguments are given 1026 then the generated condition is combined with COND_EXPR and the 1027 statements in COND_EXPR_STMT_LIST are emitted together with it. 1028 1029 FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p). 1030 FORNOW the resulting code will not be in loop-closed-ssa form. 1031 */ 1032 1033 static struct loop* 1034 slpeel_tree_peel_loop_to_edge (struct loop *loop, 1035 edge e, tree *first_niters, 1036 tree niters, bool update_first_loop_count, 1037 unsigned int th, bool check_profitability, 1038 tree cond_expr, gimple_seq cond_expr_stmt_list, 1039 int bound1, int bound2) 1040 { 1041 struct loop *new_loop = NULL, *first_loop, *second_loop; 1042 edge skip_e; 1043 tree pre_condition = NULL_TREE; 1044 basic_block bb_before_second_loop, bb_after_second_loop; 1045 basic_block bb_before_first_loop; 1046 basic_block bb_between_loops; 1047 basic_block new_exit_bb; 1048 gimple_stmt_iterator gsi; 1049 edge exit_e = single_exit (loop); 1050 LOC loop_loc; 1051 tree cost_pre_condition = NULL_TREE; 1052 /* There are many aspects to how likely the first loop is going to be executed. 1053 Without histogram we can't really do good job. Simply set it to 1054 2/3, so the first loop is not reordered to the end of function and 1055 the hot path through stays short. */ 1056 int first_guard_probability = 2 * REG_BR_PROB_BASE / 3; 1057 int second_guard_probability = 2 * REG_BR_PROB_BASE / 3; 1058 int probability_of_second_loop; 1059 1060 if (!slpeel_can_duplicate_loop_p (loop, e)) 1061 return NULL; 1062 1063 /* If the loop has a virtual PHI, but exit bb doesn't, create a virtual PHI 1064 in the exit bb and rename all the uses after the loop. This simplifies 1065 the *guard[12] routines, which assume loop closed SSA form for all PHIs 1066 (but normally loop closed SSA form doesn't require virtual PHIs to be 1067 in the same form). Doing this early simplifies the checking what 1068 uses should be renamed. */ 1069 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi)) 1070 if (virtual_operand_p (gimple_phi_result (gsi_stmt (gsi)))) 1071 { 1072 gimple phi = gsi_stmt (gsi); 1073 for (gsi = gsi_start_phis (exit_e->dest); 1074 !gsi_end_p (gsi); gsi_next (&gsi)) 1075 if (virtual_operand_p (gimple_phi_result (gsi_stmt (gsi)))) 1076 break; 1077 if (gsi_end_p (gsi)) 1078 { 1079 tree new_vop = copy_ssa_name (PHI_RESULT (phi), NULL); 1080 gimple new_phi = create_phi_node (new_vop, exit_e->dest); 1081 tree vop = PHI_ARG_DEF_FROM_EDGE (phi, EDGE_SUCC (loop->latch, 0)); 1082 imm_use_iterator imm_iter; 1083 gimple stmt; 1084 use_operand_p use_p; 1085 1086 add_phi_arg (new_phi, vop, exit_e, UNKNOWN_LOCATION); 1087 gimple_phi_set_result (new_phi, new_vop); 1088 FOR_EACH_IMM_USE_STMT (stmt, imm_iter, vop) 1089 if (stmt != new_phi && gimple_bb (stmt) != loop->header) 1090 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter) 1091 SET_USE (use_p, new_vop); 1092 } 1093 break; 1094 } 1095 1096 /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP). 1097 Resulting CFG would be: 1098 1099 first_loop: 1100 do { 1101 } while ... 1102 1103 second_loop: 1104 do { 1105 } while ... 1106 1107 orig_exit_bb: 1108 */ 1109 1110 if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e))) 1111 { 1112 loop_loc = find_loop_location (loop); 1113 dump_printf_loc (MSG_MISSED_OPTIMIZATION, loop_loc, 1114 "tree_duplicate_loop_to_edge_cfg failed.\n"); 1115 return NULL; 1116 } 1117 1118 if (MAY_HAVE_DEBUG_STMTS) 1119 { 1120 gcc_assert (!adjust_vec.exists ()); 1121 vec_stack_alloc (adjust_info, adjust_vec, 32); 1122 } 1123 1124 if (e == exit_e) 1125 { 1126 /* NEW_LOOP was placed after LOOP. */ 1127 first_loop = loop; 1128 second_loop = new_loop; 1129 } 1130 else 1131 { 1132 /* NEW_LOOP was placed before LOOP. */ 1133 first_loop = new_loop; 1134 second_loop = loop; 1135 } 1136 1137 /* 2. Add the guard code in one of the following ways: 1138 1139 2.a Add the guard that controls whether the first loop is executed. 1140 This occurs when this function is invoked for prologue or epilogue 1141 generation and when the cost model check can be done at compile time. 1142 1143 Resulting CFG would be: 1144 1145 bb_before_first_loop: 1146 if (FIRST_NITERS == 0) GOTO bb_before_second_loop 1147 GOTO first-loop 1148 1149 first_loop: 1150 do { 1151 } while ... 1152 1153 bb_before_second_loop: 1154 1155 second_loop: 1156 do { 1157 } while ... 1158 1159 orig_exit_bb: 1160 1161 2.b Add the cost model check that allows the prologue 1162 to iterate for the entire unchanged scalar 1163 iterations of the loop in the event that the cost 1164 model indicates that the scalar loop is more 1165 profitable than the vector one. This occurs when 1166 this function is invoked for prologue generation 1167 and the cost model check needs to be done at run 1168 time. 1169 1170 Resulting CFG after prologue peeling would be: 1171 1172 if (scalar_loop_iterations <= th) 1173 FIRST_NITERS = scalar_loop_iterations 1174 1175 bb_before_first_loop: 1176 if (FIRST_NITERS == 0) GOTO bb_before_second_loop 1177 GOTO first-loop 1178 1179 first_loop: 1180 do { 1181 } while ... 1182 1183 bb_before_second_loop: 1184 1185 second_loop: 1186 do { 1187 } while ... 1188 1189 orig_exit_bb: 1190 1191 2.c Add the cost model check that allows the epilogue 1192 to iterate for the entire unchanged scalar 1193 iterations of the loop in the event that the cost 1194 model indicates that the scalar loop is more 1195 profitable than the vector one. This occurs when 1196 this function is invoked for epilogue generation 1197 and the cost model check needs to be done at run 1198 time. This check is combined with any pre-existing 1199 check in COND_EXPR to avoid versioning. 1200 1201 Resulting CFG after prologue peeling would be: 1202 1203 bb_before_first_loop: 1204 if ((scalar_loop_iterations <= th) 1205 || 1206 FIRST_NITERS == 0) GOTO bb_before_second_loop 1207 GOTO first-loop 1208 1209 first_loop: 1210 do { 1211 } while ... 1212 1213 bb_before_second_loop: 1214 1215 second_loop: 1216 do { 1217 } while ... 1218 1219 orig_exit_bb: 1220 */ 1221 1222 bb_before_first_loop = split_edge (loop_preheader_edge (first_loop)); 1223 /* Loop copying insterted a forwarder block for us here. */ 1224 bb_before_second_loop = single_exit (first_loop)->dest; 1225 1226 probability_of_second_loop = (inverse_probability (first_guard_probability) 1227 + combine_probabilities (second_guard_probability, 1228 first_guard_probability)); 1229 /* Theoretically preheader edge of first loop and exit edge should have 1230 same frequencies. Loop exit probablities are however easy to get wrong. 1231 It is safer to copy value from original loop entry. */ 1232 bb_before_second_loop->frequency 1233 = apply_probability (bb_before_first_loop->frequency, 1234 probability_of_second_loop); 1235 bb_before_second_loop->count 1236 = apply_probability (bb_before_first_loop->count, 1237 probability_of_second_loop); 1238 single_succ_edge (bb_before_second_loop)->count 1239 = bb_before_second_loop->count; 1240 1241 /* Epilogue peeling. */ 1242 if (!update_first_loop_count) 1243 { 1244 pre_condition = 1245 fold_build2 (LE_EXPR, boolean_type_node, *first_niters, 1246 build_int_cst (TREE_TYPE (*first_niters), 0)); 1247 if (check_profitability) 1248 { 1249 tree scalar_loop_iters 1250 = unshare_expr (LOOP_VINFO_NITERS_UNCHANGED 1251 (loop_vec_info_for_loop (loop))); 1252 cost_pre_condition = 1253 fold_build2 (LE_EXPR, boolean_type_node, scalar_loop_iters, 1254 build_int_cst (TREE_TYPE (scalar_loop_iters), th)); 1255 1256 pre_condition = fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 1257 cost_pre_condition, pre_condition); 1258 } 1259 if (cond_expr) 1260 { 1261 pre_condition = 1262 fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 1263 pre_condition, 1264 fold_build1 (TRUTH_NOT_EXPR, boolean_type_node, 1265 cond_expr)); 1266 } 1267 } 1268 1269 /* Prologue peeling. */ 1270 else 1271 { 1272 if (check_profitability) 1273 set_prologue_iterations (bb_before_first_loop, first_niters, 1274 loop, th, first_guard_probability); 1275 1276 pre_condition = 1277 fold_build2 (LE_EXPR, boolean_type_node, *first_niters, 1278 build_int_cst (TREE_TYPE (*first_niters), 0)); 1279 } 1280 1281 skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition, 1282 cond_expr_stmt_list, 1283 bb_before_second_loop, bb_before_first_loop, 1284 inverse_probability (first_guard_probability)); 1285 scale_loop_profile (first_loop, first_guard_probability, 1286 check_profitability && (int)th > bound1 ? th : bound1); 1287 slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop, 1288 first_loop == new_loop, 1289 &new_exit_bb); 1290 1291 1292 /* 3. Add the guard that controls whether the second loop is executed. 1293 Resulting CFG would be: 1294 1295 bb_before_first_loop: 1296 if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop) 1297 GOTO first-loop 1298 1299 first_loop: 1300 do { 1301 } while ... 1302 1303 bb_between_loops: 1304 if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop) 1305 GOTO bb_before_second_loop 1306 1307 bb_before_second_loop: 1308 1309 second_loop: 1310 do { 1311 } while ... 1312 1313 bb_after_second_loop: 1314 1315 orig_exit_bb: 1316 */ 1317 1318 bb_between_loops = new_exit_bb; 1319 bb_after_second_loop = split_edge (single_exit (second_loop)); 1320 1321 pre_condition = 1322 fold_build2 (EQ_EXPR, boolean_type_node, *first_niters, niters); 1323 skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition, NULL, 1324 bb_after_second_loop, bb_before_first_loop, 1325 inverse_probability (second_guard_probability)); 1326 scale_loop_profile (second_loop, probability_of_second_loop, bound2); 1327 slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop, 1328 second_loop == new_loop, &new_exit_bb); 1329 1330 /* 4. Make first-loop iterate FIRST_NITERS times, if requested. 1331 */ 1332 if (update_first_loop_count) 1333 slpeel_make_loop_iterate_ntimes (first_loop, *first_niters); 1334 1335 delete_update_ssa (); 1336 1337 adjust_vec_debug_stmts (); 1338 1339 return new_loop; 1340 } 1341 1342 /* Function vect_get_loop_location. 1343 1344 Extract the location of the loop in the source code. 1345 If the loop is not well formed for vectorization, an estimated 1346 location is calculated. 1347 Return the loop location if succeed and NULL if not. */ 1348 1349 LOC 1350 find_loop_location (struct loop *loop) 1351 { 1352 gimple stmt = NULL; 1353 basic_block bb; 1354 gimple_stmt_iterator si; 1355 1356 if (!loop) 1357 return UNKNOWN_LOC; 1358 1359 stmt = get_loop_exit_condition (loop); 1360 1361 if (stmt 1362 && LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION) 1363 return gimple_location (stmt); 1364 1365 /* If we got here the loop is probably not "well formed", 1366 try to estimate the loop location */ 1367 1368 if (!loop->header) 1369 return UNKNOWN_LOC; 1370 1371 bb = loop->header; 1372 1373 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si)) 1374 { 1375 stmt = gsi_stmt (si); 1376 if (LOCATION_LOCUS (gimple_location (stmt)) > BUILTINS_LOCATION) 1377 return gimple_location (stmt); 1378 } 1379 1380 return UNKNOWN_LOC; 1381 } 1382 1383 1384 /* This function builds ni_name = number of iterations loop executes 1385 on the loop preheader. If SEQ is given the stmt is instead emitted 1386 there. */ 1387 1388 static tree 1389 vect_build_loop_niters (loop_vec_info loop_vinfo, gimple_seq seq) 1390 { 1391 tree ni_name, var; 1392 gimple_seq stmts = NULL; 1393 edge pe; 1394 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1395 tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo)); 1396 1397 var = create_tmp_var (TREE_TYPE (ni), "niters"); 1398 ni_name = force_gimple_operand (ni, &stmts, false, var); 1399 1400 pe = loop_preheader_edge (loop); 1401 if (stmts) 1402 { 1403 if (seq) 1404 gimple_seq_add_seq (&seq, stmts); 1405 else 1406 { 1407 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts); 1408 gcc_assert (!new_bb); 1409 } 1410 } 1411 1412 return ni_name; 1413 } 1414 1415 1416 /* This function generates the following statements: 1417 1418 ni_name = number of iterations loop executes 1419 ratio = ni_name / vf 1420 ratio_mult_vf_name = ratio * vf 1421 1422 and places them at the loop preheader edge or in COND_EXPR_STMT_LIST 1423 if that is non-NULL. */ 1424 1425 static void 1426 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo, 1427 tree *ni_name_ptr, 1428 tree *ratio_mult_vf_name_ptr, 1429 tree *ratio_name_ptr, 1430 gimple_seq cond_expr_stmt_list) 1431 { 1432 1433 edge pe; 1434 basic_block new_bb; 1435 gimple_seq stmts; 1436 tree ni_name, ni_minus_gap_name; 1437 tree var; 1438 tree ratio_name; 1439 tree ratio_mult_vf_name; 1440 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1441 tree ni = LOOP_VINFO_NITERS (loop_vinfo); 1442 int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo); 1443 tree log_vf; 1444 1445 pe = loop_preheader_edge (loop); 1446 1447 /* Generate temporary variable that contains 1448 number of iterations loop executes. */ 1449 1450 ni_name = vect_build_loop_niters (loop_vinfo, cond_expr_stmt_list); 1451 log_vf = build_int_cst (TREE_TYPE (ni), exact_log2 (vf)); 1452 1453 /* If epilogue loop is required because of data accesses with gaps, we 1454 subtract one iteration from the total number of iterations here for 1455 correct calculation of RATIO. */ 1456 if (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo)) 1457 { 1458 ni_minus_gap_name = fold_build2 (MINUS_EXPR, TREE_TYPE (ni_name), 1459 ni_name, 1460 build_one_cst (TREE_TYPE (ni_name))); 1461 if (!is_gimple_val (ni_minus_gap_name)) 1462 { 1463 var = create_tmp_var (TREE_TYPE (ni), "ni_gap"); 1464 1465 stmts = NULL; 1466 ni_minus_gap_name = force_gimple_operand (ni_minus_gap_name, &stmts, 1467 true, var); 1468 if (cond_expr_stmt_list) 1469 gimple_seq_add_seq (&cond_expr_stmt_list, stmts); 1470 else 1471 { 1472 pe = loop_preheader_edge (loop); 1473 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts); 1474 gcc_assert (!new_bb); 1475 } 1476 } 1477 } 1478 else 1479 ni_minus_gap_name = ni_name; 1480 1481 /* Create: ratio = ni >> log2(vf) */ 1482 1483 ratio_name = fold_build2 (RSHIFT_EXPR, TREE_TYPE (ni_minus_gap_name), 1484 ni_minus_gap_name, log_vf); 1485 if (!is_gimple_val (ratio_name)) 1486 { 1487 var = create_tmp_var (TREE_TYPE (ni), "bnd"); 1488 1489 stmts = NULL; 1490 ratio_name = force_gimple_operand (ratio_name, &stmts, true, var); 1491 if (cond_expr_stmt_list) 1492 gimple_seq_add_seq (&cond_expr_stmt_list, stmts); 1493 else 1494 { 1495 pe = loop_preheader_edge (loop); 1496 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts); 1497 gcc_assert (!new_bb); 1498 } 1499 } 1500 1501 /* Create: ratio_mult_vf = ratio << log2 (vf). */ 1502 1503 ratio_mult_vf_name = fold_build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name), 1504 ratio_name, log_vf); 1505 if (!is_gimple_val (ratio_mult_vf_name)) 1506 { 1507 var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf"); 1508 1509 stmts = NULL; 1510 ratio_mult_vf_name = force_gimple_operand (ratio_mult_vf_name, &stmts, 1511 true, var); 1512 if (cond_expr_stmt_list) 1513 gimple_seq_add_seq (&cond_expr_stmt_list, stmts); 1514 else 1515 { 1516 pe = loop_preheader_edge (loop); 1517 new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts); 1518 gcc_assert (!new_bb); 1519 } 1520 } 1521 1522 *ni_name_ptr = ni_name; 1523 *ratio_mult_vf_name_ptr = ratio_mult_vf_name; 1524 *ratio_name_ptr = ratio_name; 1525 1526 return; 1527 } 1528 1529 /* Function vect_can_advance_ivs_p 1530 1531 In case the number of iterations that LOOP iterates is unknown at compile 1532 time, an epilog loop will be generated, and the loop induction variables 1533 (IVs) will be "advanced" to the value they are supposed to take just before 1534 the epilog loop. Here we check that the access function of the loop IVs 1535 and the expression that represents the loop bound are simple enough. 1536 These restrictions will be relaxed in the future. */ 1537 1538 bool 1539 vect_can_advance_ivs_p (loop_vec_info loop_vinfo) 1540 { 1541 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1542 basic_block bb = loop->header; 1543 gimple phi; 1544 gimple_stmt_iterator gsi; 1545 1546 /* Analyze phi functions of the loop header. */ 1547 1548 if (dump_enabled_p ()) 1549 dump_printf_loc (MSG_NOTE, vect_location, "vect_can_advance_ivs_p:"); 1550 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1551 { 1552 tree access_fn = NULL; 1553 tree evolution_part; 1554 1555 phi = gsi_stmt (gsi); 1556 if (dump_enabled_p ()) 1557 { 1558 dump_printf_loc (MSG_NOTE, vect_location, "Analyze phi: "); 1559 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0); 1560 } 1561 1562 /* Skip virtual phi's. The data dependences that are associated with 1563 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */ 1564 1565 if (virtual_operand_p (PHI_RESULT (phi))) 1566 { 1567 if (dump_enabled_p ()) 1568 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 1569 "virtual phi. skip."); 1570 continue; 1571 } 1572 1573 /* Skip reduction phis. */ 1574 1575 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def) 1576 { 1577 if (dump_enabled_p ()) 1578 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 1579 "reduc phi. skip."); 1580 continue; 1581 } 1582 1583 /* Analyze the evolution function. */ 1584 1585 access_fn = instantiate_parameters 1586 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); 1587 1588 if (!access_fn) 1589 { 1590 if (dump_enabled_p ()) 1591 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 1592 "No Access function."); 1593 return false; 1594 } 1595 1596 STRIP_NOPS (access_fn); 1597 if (dump_enabled_p ()) 1598 { 1599 dump_printf_loc (MSG_NOTE, vect_location, 1600 "Access function of PHI: "); 1601 dump_generic_expr (MSG_NOTE, TDF_SLIM, access_fn); 1602 } 1603 1604 evolution_part = evolution_part_in_loop_num (access_fn, loop->num); 1605 1606 if (evolution_part == NULL_TREE) 1607 { 1608 if (dump_enabled_p ()) 1609 dump_printf (MSG_MISSED_OPTIMIZATION, "No evolution."); 1610 return false; 1611 } 1612 1613 /* FORNOW: We do not transform initial conditions of IVs 1614 which evolution functions are a polynomial of degree >= 2. */ 1615 1616 if (tree_is_chrec (evolution_part)) 1617 return false; 1618 } 1619 1620 return true; 1621 } 1622 1623 1624 /* Function vect_update_ivs_after_vectorizer. 1625 1626 "Advance" the induction variables of LOOP to the value they should take 1627 after the execution of LOOP. This is currently necessary because the 1628 vectorizer does not handle induction variables that are used after the 1629 loop. Such a situation occurs when the last iterations of LOOP are 1630 peeled, because: 1631 1. We introduced new uses after LOOP for IVs that were not originally used 1632 after LOOP: the IVs of LOOP are now used by an epilog loop. 1633 2. LOOP is going to be vectorized; this means that it will iterate N/VF 1634 times, whereas the loop IVs should be bumped N times. 1635 1636 Input: 1637 - LOOP - a loop that is going to be vectorized. The last few iterations 1638 of LOOP were peeled. 1639 - NITERS - the number of iterations that LOOP executes (before it is 1640 vectorized). i.e, the number of times the ivs should be bumped. 1641 - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path 1642 coming out from LOOP on which there are uses of the LOOP ivs 1643 (this is the path from LOOP->exit to epilog_loop->preheader). 1644 1645 The new definitions of the ivs are placed in LOOP->exit. 1646 The phi args associated with the edge UPDATE_E in the bb 1647 UPDATE_E->dest are updated accordingly. 1648 1649 Assumption 1: Like the rest of the vectorizer, this function assumes 1650 a single loop exit that has a single predecessor. 1651 1652 Assumption 2: The phi nodes in the LOOP header and in update_bb are 1653 organized in the same order. 1654 1655 Assumption 3: The access function of the ivs is simple enough (see 1656 vect_can_advance_ivs_p). This assumption will be relaxed in the future. 1657 1658 Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path 1659 coming out of LOOP on which the ivs of LOOP are used (this is the path 1660 that leads to the epilog loop; other paths skip the epilog loop). This 1661 path starts with the edge UPDATE_E, and its destination (denoted update_bb) 1662 needs to have its phis updated. 1663 */ 1664 1665 static void 1666 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters, 1667 edge update_e) 1668 { 1669 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1670 basic_block exit_bb = single_exit (loop)->dest; 1671 gimple phi, phi1; 1672 gimple_stmt_iterator gsi, gsi1; 1673 basic_block update_bb = update_e->dest; 1674 1675 /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */ 1676 1677 /* Make sure there exists a single-predecessor exit bb: */ 1678 gcc_assert (single_pred_p (exit_bb)); 1679 1680 for (gsi = gsi_start_phis (loop->header), gsi1 = gsi_start_phis (update_bb); 1681 !gsi_end_p (gsi) && !gsi_end_p (gsi1); 1682 gsi_next (&gsi), gsi_next (&gsi1)) 1683 { 1684 tree init_expr; 1685 tree step_expr, off; 1686 tree type; 1687 tree var, ni, ni_name; 1688 gimple_stmt_iterator last_gsi; 1689 stmt_vec_info stmt_info; 1690 1691 phi = gsi_stmt (gsi); 1692 phi1 = gsi_stmt (gsi1); 1693 if (dump_enabled_p ()) 1694 { 1695 dump_printf_loc (MSG_NOTE, vect_location, 1696 "vect_update_ivs_after_vectorizer: phi: "); 1697 dump_gimple_stmt (MSG_NOTE, TDF_SLIM, phi, 0); 1698 } 1699 1700 /* Skip virtual phi's. */ 1701 if (virtual_operand_p (PHI_RESULT (phi))) 1702 { 1703 if (dump_enabled_p ()) 1704 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 1705 "virtual phi. skip."); 1706 continue; 1707 } 1708 1709 /* Skip reduction phis. */ 1710 stmt_info = vinfo_for_stmt (phi); 1711 if (STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def) 1712 { 1713 if (dump_enabled_p ()) 1714 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location, 1715 "reduc phi. skip."); 1716 continue; 1717 } 1718 1719 type = TREE_TYPE (gimple_phi_result (phi)); 1720 step_expr = STMT_VINFO_LOOP_PHI_EVOLUTION_PART (stmt_info); 1721 step_expr = unshare_expr (step_expr); 1722 1723 /* FORNOW: We do not support IVs whose evolution function is a polynomial 1724 of degree >= 2 or exponential. */ 1725 gcc_assert (!tree_is_chrec (step_expr)); 1726 1727 init_expr = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop)); 1728 1729 off = fold_build2 (MULT_EXPR, TREE_TYPE (step_expr), 1730 fold_convert (TREE_TYPE (step_expr), niters), 1731 step_expr); 1732 if (POINTER_TYPE_P (type)) 1733 ni = fold_build_pointer_plus (init_expr, off); 1734 else 1735 ni = fold_build2 (PLUS_EXPR, type, 1736 init_expr, fold_convert (type, off)); 1737 1738 var = create_tmp_var (type, "tmp"); 1739 1740 last_gsi = gsi_last_bb (exit_bb); 1741 ni_name = force_gimple_operand_gsi (&last_gsi, ni, false, var, 1742 true, GSI_SAME_STMT); 1743 1744 /* Fix phi expressions in the successor bb. */ 1745 adjust_phi_and_debug_stmts (phi1, update_e, ni_name); 1746 } 1747 } 1748 1749 /* Function vect_do_peeling_for_loop_bound 1750 1751 Peel the last iterations of the loop represented by LOOP_VINFO. 1752 The peeled iterations form a new epilog loop. Given that the loop now 1753 iterates NITERS times, the new epilog loop iterates 1754 NITERS % VECTORIZATION_FACTOR times. 1755 1756 The original loop will later be made to iterate 1757 NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO). 1758 1759 COND_EXPR and COND_EXPR_STMT_LIST are combined with a new generated 1760 test. */ 1761 1762 void 1763 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio, 1764 unsigned int th, bool check_profitability) 1765 { 1766 tree ni_name, ratio_mult_vf_name; 1767 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1768 struct loop *new_loop; 1769 edge update_e; 1770 basic_block preheader; 1771 int loop_num; 1772 int max_iter; 1773 tree cond_expr = NULL_TREE; 1774 gimple_seq cond_expr_stmt_list = NULL; 1775 1776 if (dump_enabled_p ()) 1777 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 1778 "=== vect_do_peeling_for_loop_bound ==="); 1779 1780 initialize_original_copy_tables (); 1781 1782 /* Generate the following variables on the preheader of original loop: 1783 1784 ni_name = number of iteration the original loop executes 1785 ratio = ni_name / vf 1786 ratio_mult_vf_name = ratio * vf */ 1787 vect_generate_tmps_on_preheader (loop_vinfo, &ni_name, 1788 &ratio_mult_vf_name, ratio, 1789 cond_expr_stmt_list); 1790 1791 loop_num = loop->num; 1792 1793 new_loop = slpeel_tree_peel_loop_to_edge (loop, single_exit (loop), 1794 &ratio_mult_vf_name, ni_name, false, 1795 th, check_profitability, 1796 cond_expr, cond_expr_stmt_list, 1797 0, LOOP_VINFO_VECT_FACTOR (loop_vinfo)); 1798 gcc_assert (new_loop); 1799 gcc_assert (loop_num == loop->num); 1800 #ifdef ENABLE_CHECKING 1801 slpeel_verify_cfg_after_peeling (loop, new_loop); 1802 #endif 1803 1804 /* A guard that controls whether the new_loop is to be executed or skipped 1805 is placed in LOOP->exit. LOOP->exit therefore has two successors - one 1806 is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other 1807 is a bb after NEW_LOOP, where these IVs are not used. Find the edge that 1808 is on the path where the LOOP IVs are used and need to be updated. */ 1809 1810 preheader = loop_preheader_edge (new_loop)->src; 1811 if (EDGE_PRED (preheader, 0)->src == single_exit (loop)->dest) 1812 update_e = EDGE_PRED (preheader, 0); 1813 else 1814 update_e = EDGE_PRED (preheader, 1); 1815 1816 /* Update IVs of original loop as if they were advanced 1817 by ratio_mult_vf_name steps. */ 1818 vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e); 1819 1820 /* For vectorization factor N, we need to copy last N-1 values in epilogue 1821 and this means N-2 loopback edge executions. 1822 1823 PEELING_FOR_GAPS works by subtracting last iteration and thus the epilogue 1824 will execute at least LOOP_VINFO_VECT_FACTOR times. */ 1825 max_iter = (LOOP_VINFO_PEELING_FOR_GAPS (loop_vinfo) 1826 ? LOOP_VINFO_VECT_FACTOR (loop_vinfo) * 2 1827 : LOOP_VINFO_VECT_FACTOR (loop_vinfo)) - 2; 1828 if (check_profitability) 1829 max_iter = MAX (max_iter, (int) th - 1); 1830 record_niter_bound (new_loop, double_int::from_shwi (max_iter), false, true); 1831 dump_printf (MSG_OPTIMIZED_LOCATIONS, 1832 "Setting upper bound of nb iterations for epilogue " 1833 "loop to %d\n", max_iter); 1834 1835 /* After peeling we have to reset scalar evolution analyzer. */ 1836 scev_reset (); 1837 1838 free_original_copy_tables (); 1839 } 1840 1841 1842 /* Function vect_gen_niters_for_prolog_loop 1843 1844 Set the number of iterations for the loop represented by LOOP_VINFO 1845 to the minimum between LOOP_NITERS (the original iteration count of the loop) 1846 and the misalignment of DR - the data reference recorded in 1847 LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of 1848 this loop, the data reference DR will refer to an aligned location. 1849 1850 The following computation is generated: 1851 1852 If the misalignment of DR is known at compile time: 1853 addr_mis = int mis = DR_MISALIGNMENT (dr); 1854 Else, compute address misalignment in bytes: 1855 addr_mis = addr & (vectype_align - 1) 1856 1857 prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step) 1858 1859 (elem_size = element type size; an element is the scalar element whose type 1860 is the inner type of the vectype) 1861 1862 When the step of the data-ref in the loop is not 1 (as in interleaved data 1863 and SLP), the number of iterations of the prolog must be divided by the step 1864 (which is equal to the size of interleaved group). 1865 1866 The above formulas assume that VF == number of elements in the vector. This 1867 may not hold when there are multiple-types in the loop. 1868 In this case, for some data-references in the loop the VF does not represent 1869 the number of elements that fit in the vector. Therefore, instead of VF we 1870 use TYPE_VECTOR_SUBPARTS. */ 1871 1872 static tree 1873 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters, int *bound) 1874 { 1875 struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo); 1876 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1877 tree var; 1878 gimple_seq stmts; 1879 tree iters, iters_name; 1880 edge pe; 1881 basic_block new_bb; 1882 gimple dr_stmt = DR_STMT (dr); 1883 stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt); 1884 tree vectype = STMT_VINFO_VECTYPE (stmt_info); 1885 int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT; 1886 tree niters_type = TREE_TYPE (loop_niters); 1887 int nelements = TYPE_VECTOR_SUBPARTS (vectype); 1888 1889 pe = loop_preheader_edge (loop); 1890 1891 if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0) 1892 { 1893 int npeel = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo); 1894 1895 if (dump_enabled_p ()) 1896 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 1897 "known peeling = %d.", npeel); 1898 1899 iters = build_int_cst (niters_type, npeel); 1900 *bound = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo); 1901 } 1902 else 1903 { 1904 gimple_seq new_stmts = NULL; 1905 bool negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0; 1906 tree offset = negative 1907 ? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE; 1908 tree start_addr = vect_create_addr_base_for_vector_ref (dr_stmt, 1909 &new_stmts, offset, loop); 1910 tree type = unsigned_type_for (TREE_TYPE (start_addr)); 1911 tree vectype_align_minus_1 = build_int_cst (type, vectype_align - 1); 1912 HOST_WIDE_INT elem_size = 1913 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype))); 1914 tree elem_size_log = build_int_cst (type, exact_log2 (elem_size)); 1915 tree nelements_minus_1 = build_int_cst (type, nelements - 1); 1916 tree nelements_tree = build_int_cst (type, nelements); 1917 tree byte_misalign; 1918 tree elem_misalign; 1919 1920 new_bb = gsi_insert_seq_on_edge_immediate (pe, new_stmts); 1921 gcc_assert (!new_bb); 1922 1923 /* Create: byte_misalign = addr & (vectype_align - 1) */ 1924 byte_misalign = 1925 fold_build2 (BIT_AND_EXPR, type, fold_convert (type, start_addr), 1926 vectype_align_minus_1); 1927 1928 /* Create: elem_misalign = byte_misalign / element_size */ 1929 elem_misalign = 1930 fold_build2 (RSHIFT_EXPR, type, byte_misalign, elem_size_log); 1931 1932 /* Create: (niters_type) (nelements - elem_misalign)&(nelements - 1) */ 1933 if (negative) 1934 iters = fold_build2 (MINUS_EXPR, type, elem_misalign, nelements_tree); 1935 else 1936 iters = fold_build2 (MINUS_EXPR, type, nelements_tree, elem_misalign); 1937 iters = fold_build2 (BIT_AND_EXPR, type, iters, nelements_minus_1); 1938 iters = fold_convert (niters_type, iters); 1939 *bound = nelements; 1940 } 1941 1942 /* Create: prolog_loop_niters = min (iters, loop_niters) */ 1943 /* If the loop bound is known at compile time we already verified that it is 1944 greater than vf; since the misalignment ('iters') is at most vf, there's 1945 no need to generate the MIN_EXPR in this case. */ 1946 if (TREE_CODE (loop_niters) != INTEGER_CST) 1947 iters = fold_build2 (MIN_EXPR, niters_type, iters, loop_niters); 1948 1949 if (dump_enabled_p ()) 1950 { 1951 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 1952 "niters for prolog loop: "); 1953 dump_generic_expr (MSG_OPTIMIZED_LOCATIONS, TDF_SLIM, iters); 1954 } 1955 1956 var = create_tmp_var (niters_type, "prolog_loop_niters"); 1957 stmts = NULL; 1958 iters_name = force_gimple_operand (iters, &stmts, false, var); 1959 1960 /* Insert stmt on loop preheader edge. */ 1961 if (stmts) 1962 { 1963 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, stmts); 1964 gcc_assert (!new_bb); 1965 } 1966 1967 return iters_name; 1968 } 1969 1970 1971 /* Function vect_update_init_of_dr 1972 1973 NITERS iterations were peeled from LOOP. DR represents a data reference 1974 in LOOP. This function updates the information recorded in DR to 1975 account for the fact that the first NITERS iterations had already been 1976 executed. Specifically, it updates the OFFSET field of DR. */ 1977 1978 static void 1979 vect_update_init_of_dr (struct data_reference *dr, tree niters) 1980 { 1981 tree offset = DR_OFFSET (dr); 1982 1983 niters = fold_build2 (MULT_EXPR, sizetype, 1984 fold_convert (sizetype, niters), 1985 fold_convert (sizetype, DR_STEP (dr))); 1986 offset = fold_build2 (PLUS_EXPR, sizetype, 1987 fold_convert (sizetype, offset), niters); 1988 DR_OFFSET (dr) = offset; 1989 } 1990 1991 1992 /* Function vect_update_inits_of_drs 1993 1994 NITERS iterations were peeled from the loop represented by LOOP_VINFO. 1995 This function updates the information recorded for the data references in 1996 the loop to account for the fact that the first NITERS iterations had 1997 already been executed. Specifically, it updates the initial_condition of 1998 the access_function of all the data_references in the loop. */ 1999 2000 static void 2001 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters) 2002 { 2003 unsigned int i; 2004 vec<data_reference_p> datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); 2005 struct data_reference *dr; 2006 2007 if (dump_enabled_p ()) 2008 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 2009 "=== vect_update_inits_of_dr ==="); 2010 2011 FOR_EACH_VEC_ELT (datarefs, i, dr) 2012 vect_update_init_of_dr (dr, niters); 2013 } 2014 2015 2016 /* Function vect_do_peeling_for_alignment 2017 2018 Peel the first 'niters' iterations of the loop represented by LOOP_VINFO. 2019 'niters' is set to the misalignment of one of the data references in the 2020 loop, thereby forcing it to refer to an aligned location at the beginning 2021 of the execution of this loop. The data reference for which we are 2022 peeling is recorded in LOOP_VINFO_UNALIGNED_DR. */ 2023 2024 void 2025 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo, 2026 unsigned int th, bool check_profitability) 2027 { 2028 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 2029 tree niters_of_prolog_loop, ni_name; 2030 tree n_iters; 2031 tree wide_prolog_niters; 2032 struct loop *new_loop; 2033 int max_iter; 2034 int bound = 0; 2035 2036 if (dump_enabled_p ()) 2037 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 2038 "=== vect_do_peeling_for_alignment ==="); 2039 2040 initialize_original_copy_tables (); 2041 2042 ni_name = vect_build_loop_niters (loop_vinfo, NULL); 2043 niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, 2044 ni_name, 2045 &bound); 2046 2047 /* Peel the prolog loop and iterate it niters_of_prolog_loop. */ 2048 new_loop = 2049 slpeel_tree_peel_loop_to_edge (loop, loop_preheader_edge (loop), 2050 &niters_of_prolog_loop, ni_name, true, 2051 th, check_profitability, NULL_TREE, NULL, 2052 bound, 2053 0); 2054 2055 gcc_assert (new_loop); 2056 #ifdef ENABLE_CHECKING 2057 slpeel_verify_cfg_after_peeling (new_loop, loop); 2058 #endif 2059 /* For vectorization factor N, we need to copy at most N-1 values 2060 for alignment and this means N-2 loopback edge executions. */ 2061 max_iter = LOOP_VINFO_VECT_FACTOR (loop_vinfo) - 2; 2062 if (check_profitability) 2063 max_iter = MAX (max_iter, (int) th - 1); 2064 record_niter_bound (new_loop, double_int::from_shwi (max_iter), false, true); 2065 dump_printf (MSG_OPTIMIZED_LOCATIONS, 2066 "Setting upper bound of nb iterations for prologue " 2067 "loop to %d\n", max_iter); 2068 2069 /* Update number of times loop executes. */ 2070 n_iters = LOOP_VINFO_NITERS (loop_vinfo); 2071 LOOP_VINFO_NITERS (loop_vinfo) = fold_build2 (MINUS_EXPR, 2072 TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop); 2073 2074 if (types_compatible_p (sizetype, TREE_TYPE (niters_of_prolog_loop))) 2075 wide_prolog_niters = niters_of_prolog_loop; 2076 else 2077 { 2078 gimple_seq seq = NULL; 2079 edge pe = loop_preheader_edge (loop); 2080 tree wide_iters = fold_convert (sizetype, niters_of_prolog_loop); 2081 tree var = create_tmp_var (sizetype, "prolog_loop_adjusted_niters"); 2082 wide_prolog_niters = force_gimple_operand (wide_iters, &seq, false, 2083 var); 2084 if (seq) 2085 { 2086 /* Insert stmt on loop preheader edge. */ 2087 basic_block new_bb = gsi_insert_seq_on_edge_immediate (pe, seq); 2088 gcc_assert (!new_bb); 2089 } 2090 } 2091 2092 /* Update the init conditions of the access functions of all data refs. */ 2093 vect_update_inits_of_drs (loop_vinfo, wide_prolog_niters); 2094 2095 /* After peeling we have to reset scalar evolution analyzer. */ 2096 scev_reset (); 2097 2098 free_original_copy_tables (); 2099 } 2100 2101 2102 /* Function vect_create_cond_for_align_checks. 2103 2104 Create a conditional expression that represents the alignment checks for 2105 all of data references (array element references) whose alignment must be 2106 checked at runtime. 2107 2108 Input: 2109 COND_EXPR - input conditional expression. New conditions will be chained 2110 with logical AND operation. 2111 LOOP_VINFO - two fields of the loop information are used. 2112 LOOP_VINFO_PTR_MASK is the mask used to check the alignment. 2113 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked. 2114 2115 Output: 2116 COND_EXPR_STMT_LIST - statements needed to construct the conditional 2117 expression. 2118 The returned value is the conditional expression to be used in the if 2119 statement that controls which version of the loop gets executed at runtime. 2120 2121 The algorithm makes two assumptions: 2122 1) The number of bytes "n" in a vector is a power of 2. 2123 2) An address "a" is aligned if a%n is zero and that this 2124 test can be done as a&(n-1) == 0. For example, for 16 2125 byte vectors the test is a&0xf == 0. */ 2126 2127 static void 2128 vect_create_cond_for_align_checks (loop_vec_info loop_vinfo, 2129 tree *cond_expr, 2130 gimple_seq *cond_expr_stmt_list) 2131 { 2132 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 2133 vec<gimple> may_misalign_stmts 2134 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo); 2135 gimple ref_stmt; 2136 int mask = LOOP_VINFO_PTR_MASK (loop_vinfo); 2137 tree mask_cst; 2138 unsigned int i; 2139 tree int_ptrsize_type; 2140 char tmp_name[20]; 2141 tree or_tmp_name = NULL_TREE; 2142 tree and_tmp_name; 2143 gimple and_stmt; 2144 tree ptrsize_zero; 2145 tree part_cond_expr; 2146 2147 /* Check that mask is one less than a power of 2, i.e., mask is 2148 all zeros followed by all ones. */ 2149 gcc_assert ((mask != 0) && ((mask & (mask+1)) == 0)); 2150 2151 int_ptrsize_type = signed_type_for (ptr_type_node); 2152 2153 /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address 2154 of the first vector of the i'th data reference. */ 2155 2156 FOR_EACH_VEC_ELT (may_misalign_stmts, i, ref_stmt) 2157 { 2158 gimple_seq new_stmt_list = NULL; 2159 tree addr_base; 2160 tree addr_tmp_name; 2161 tree new_or_tmp_name; 2162 gimple addr_stmt, or_stmt; 2163 stmt_vec_info stmt_vinfo = vinfo_for_stmt (ref_stmt); 2164 tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo); 2165 bool negative = tree_int_cst_compare 2166 (DR_STEP (STMT_VINFO_DATA_REF (stmt_vinfo)), size_zero_node) < 0; 2167 tree offset = negative 2168 ? size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1) : NULL_TREE; 2169 2170 /* create: addr_tmp = (int)(address_of_first_vector) */ 2171 addr_base = 2172 vect_create_addr_base_for_vector_ref (ref_stmt, &new_stmt_list, 2173 offset, loop); 2174 if (new_stmt_list != NULL) 2175 gimple_seq_add_seq (cond_expr_stmt_list, new_stmt_list); 2176 2177 sprintf (tmp_name, "addr2int%d", i); 2178 addr_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL, tmp_name); 2179 addr_stmt = gimple_build_assign_with_ops (NOP_EXPR, addr_tmp_name, 2180 addr_base, NULL_TREE); 2181 gimple_seq_add_stmt (cond_expr_stmt_list, addr_stmt); 2182 2183 /* The addresses are OR together. */ 2184 2185 if (or_tmp_name != NULL_TREE) 2186 { 2187 /* create: or_tmp = or_tmp | addr_tmp */ 2188 sprintf (tmp_name, "orptrs%d", i); 2189 new_or_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL, tmp_name); 2190 or_stmt = gimple_build_assign_with_ops (BIT_IOR_EXPR, 2191 new_or_tmp_name, 2192 or_tmp_name, addr_tmp_name); 2193 gimple_seq_add_stmt (cond_expr_stmt_list, or_stmt); 2194 or_tmp_name = new_or_tmp_name; 2195 } 2196 else 2197 or_tmp_name = addr_tmp_name; 2198 2199 } /* end for i */ 2200 2201 mask_cst = build_int_cst (int_ptrsize_type, mask); 2202 2203 /* create: and_tmp = or_tmp & mask */ 2204 and_tmp_name = make_temp_ssa_name (int_ptrsize_type, NULL, "andmask"); 2205 2206 and_stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, and_tmp_name, 2207 or_tmp_name, mask_cst); 2208 gimple_seq_add_stmt (cond_expr_stmt_list, and_stmt); 2209 2210 /* Make and_tmp the left operand of the conditional test against zero. 2211 if and_tmp has a nonzero bit then some address is unaligned. */ 2212 ptrsize_zero = build_int_cst (int_ptrsize_type, 0); 2213 part_cond_expr = fold_build2 (EQ_EXPR, boolean_type_node, 2214 and_tmp_name, ptrsize_zero); 2215 if (*cond_expr) 2216 *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 2217 *cond_expr, part_cond_expr); 2218 else 2219 *cond_expr = part_cond_expr; 2220 } 2221 2222 2223 /* Function vect_vfa_segment_size. 2224 2225 Create an expression that computes the size of segment 2226 that will be accessed for a data reference. The functions takes into 2227 account that realignment loads may access one more vector. 2228 2229 Input: 2230 DR: The data reference. 2231 LENGTH_FACTOR: segment length to consider. 2232 2233 Return an expression whose value is the size of segment which will be 2234 accessed by DR. */ 2235 2236 static tree 2237 vect_vfa_segment_size (struct data_reference *dr, tree length_factor) 2238 { 2239 tree segment_length; 2240 2241 if (integer_zerop (DR_STEP (dr))) 2242 segment_length = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))); 2243 else 2244 segment_length = size_binop (MULT_EXPR, 2245 fold_convert (sizetype, DR_STEP (dr)), 2246 fold_convert (sizetype, length_factor)); 2247 2248 if (vect_supportable_dr_alignment (dr, false) 2249 == dr_explicit_realign_optimized) 2250 { 2251 tree vector_size = TYPE_SIZE_UNIT 2252 (STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)))); 2253 2254 segment_length = size_binop (PLUS_EXPR, segment_length, vector_size); 2255 } 2256 return segment_length; 2257 } 2258 2259 2260 /* Function vect_create_cond_for_alias_checks. 2261 2262 Create a conditional expression that represents the run-time checks for 2263 overlapping of address ranges represented by a list of data references 2264 relations passed as input. 2265 2266 Input: 2267 COND_EXPR - input conditional expression. New conditions will be chained 2268 with logical AND operation. 2269 LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs 2270 to be checked. 2271 2272 Output: 2273 COND_EXPR - conditional expression. 2274 COND_EXPR_STMT_LIST - statements needed to construct the conditional 2275 expression. 2276 2277 2278 The returned value is the conditional expression to be used in the if 2279 statement that controls which version of the loop gets executed at runtime. 2280 */ 2281 2282 static void 2283 vect_create_cond_for_alias_checks (loop_vec_info loop_vinfo, 2284 tree * cond_expr, 2285 gimple_seq * cond_expr_stmt_list) 2286 { 2287 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 2288 vec<ddr_p> may_alias_ddrs = 2289 LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo); 2290 int vect_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo); 2291 tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo); 2292 2293 ddr_p ddr; 2294 unsigned int i; 2295 tree part_cond_expr, length_factor; 2296 2297 /* Create expression 2298 ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) 2299 || (load_ptr_0 + load_segment_length_0) <= store_ptr_0)) 2300 && 2301 ... 2302 && 2303 ((store_ptr_n + store_segment_length_n) <= load_ptr_n) 2304 || (load_ptr_n + load_segment_length_n) <= store_ptr_n)) */ 2305 2306 if (may_alias_ddrs.is_empty ()) 2307 return; 2308 2309 FOR_EACH_VEC_ELT (may_alias_ddrs, i, ddr) 2310 { 2311 struct data_reference *dr_a, *dr_b; 2312 gimple dr_group_first_a, dr_group_first_b; 2313 tree addr_base_a, addr_base_b; 2314 tree segment_length_a, segment_length_b; 2315 gimple stmt_a, stmt_b; 2316 tree seg_a_min, seg_a_max, seg_b_min, seg_b_max; 2317 2318 dr_a = DDR_A (ddr); 2319 stmt_a = DR_STMT (DDR_A (ddr)); 2320 dr_group_first_a = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_a)); 2321 if (dr_group_first_a) 2322 { 2323 stmt_a = dr_group_first_a; 2324 dr_a = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_a)); 2325 } 2326 2327 dr_b = DDR_B (ddr); 2328 stmt_b = DR_STMT (DDR_B (ddr)); 2329 dr_group_first_b = GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_b)); 2330 if (dr_group_first_b) 2331 { 2332 stmt_b = dr_group_first_b; 2333 dr_b = STMT_VINFO_DATA_REF (vinfo_for_stmt (stmt_b)); 2334 } 2335 2336 addr_base_a = 2337 vect_create_addr_base_for_vector_ref (stmt_a, cond_expr_stmt_list, 2338 NULL_TREE, loop); 2339 addr_base_b = 2340 vect_create_addr_base_for_vector_ref (stmt_b, cond_expr_stmt_list, 2341 NULL_TREE, loop); 2342 2343 if (!operand_equal_p (DR_STEP (dr_a), DR_STEP (dr_b), 0)) 2344 length_factor = scalar_loop_iters; 2345 else 2346 length_factor = size_int (vect_factor); 2347 segment_length_a = vect_vfa_segment_size (dr_a, length_factor); 2348 segment_length_b = vect_vfa_segment_size (dr_b, length_factor); 2349 2350 if (dump_enabled_p ()) 2351 { 2352 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 2353 "create runtime check for data references "); 2354 dump_generic_expr (MSG_OPTIMIZED_LOCATIONS, TDF_SLIM, DR_REF (dr_a)); 2355 dump_printf (MSG_OPTIMIZED_LOCATIONS, " and "); 2356 dump_generic_expr (MSG_OPTIMIZED_LOCATIONS, TDF_SLIM, DR_REF (dr_b)); 2357 } 2358 2359 seg_a_min = addr_base_a; 2360 seg_a_max = fold_build_pointer_plus (addr_base_a, segment_length_a); 2361 if (tree_int_cst_compare (DR_STEP (dr_a), size_zero_node) < 0) 2362 seg_a_min = seg_a_max, seg_a_max = addr_base_a; 2363 2364 seg_b_min = addr_base_b; 2365 seg_b_max = fold_build_pointer_plus (addr_base_b, segment_length_b); 2366 if (tree_int_cst_compare (DR_STEP (dr_b), size_zero_node) < 0) 2367 seg_b_min = seg_b_max, seg_b_max = addr_base_b; 2368 2369 part_cond_expr = 2370 fold_build2 (TRUTH_OR_EXPR, boolean_type_node, 2371 fold_build2 (LE_EXPR, boolean_type_node, seg_a_max, seg_b_min), 2372 fold_build2 (LE_EXPR, boolean_type_node, seg_b_max, seg_a_min)); 2373 2374 if (*cond_expr) 2375 *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, 2376 *cond_expr, part_cond_expr); 2377 else 2378 *cond_expr = part_cond_expr; 2379 } 2380 2381 if (dump_enabled_p ()) 2382 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 2383 "created %u versioning for alias checks.\n", 2384 may_alias_ddrs.length ()); 2385 } 2386 2387 2388 /* Function vect_loop_versioning. 2389 2390 If the loop has data references that may or may not be aligned or/and 2391 has data reference relations whose independence was not proven then 2392 two versions of the loop need to be generated, one which is vectorized 2393 and one which isn't. A test is then generated to control which of the 2394 loops is executed. The test checks for the alignment of all of the 2395 data references that may or may not be aligned. An additional 2396 sequence of runtime tests is generated for each pairs of DDRs whose 2397 independence was not proven. The vectorized version of loop is 2398 executed only if both alias and alignment tests are passed. 2399 2400 The test generated to check which version of loop is executed 2401 is modified to also check for profitability as indicated by the 2402 cost model initially. 2403 2404 The versioning precondition(s) are placed in *COND_EXPR and 2405 *COND_EXPR_STMT_LIST. */ 2406 2407 void 2408 vect_loop_versioning (loop_vec_info loop_vinfo, 2409 unsigned int th, bool check_profitability) 2410 { 2411 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 2412 basic_block condition_bb; 2413 gimple_stmt_iterator gsi, cond_exp_gsi; 2414 basic_block merge_bb; 2415 basic_block new_exit_bb; 2416 edge new_exit_e, e; 2417 gimple orig_phi, new_phi; 2418 tree cond_expr = NULL_TREE; 2419 gimple_seq cond_expr_stmt_list = NULL; 2420 tree arg; 2421 unsigned prob = 4 * REG_BR_PROB_BASE / 5; 2422 gimple_seq gimplify_stmt_list = NULL; 2423 tree scalar_loop_iters = LOOP_VINFO_NITERS (loop_vinfo); 2424 2425 if (check_profitability) 2426 { 2427 cond_expr = fold_build2 (GT_EXPR, boolean_type_node, scalar_loop_iters, 2428 build_int_cst (TREE_TYPE (scalar_loop_iters), th)); 2429 cond_expr = force_gimple_operand_1 (cond_expr, &cond_expr_stmt_list, 2430 is_gimple_condexpr, NULL_TREE); 2431 } 2432 2433 if (LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT (loop_vinfo)) 2434 vect_create_cond_for_align_checks (loop_vinfo, &cond_expr, 2435 &cond_expr_stmt_list); 2436 2437 if (LOOP_REQUIRES_VERSIONING_FOR_ALIAS (loop_vinfo)) 2438 vect_create_cond_for_alias_checks (loop_vinfo, &cond_expr, 2439 &cond_expr_stmt_list); 2440 2441 cond_expr = force_gimple_operand_1 (cond_expr, &gimplify_stmt_list, 2442 is_gimple_condexpr, NULL_TREE); 2443 gimple_seq_add_seq (&cond_expr_stmt_list, gimplify_stmt_list); 2444 2445 initialize_original_copy_tables (); 2446 loop_version (loop, cond_expr, &condition_bb, 2447 prob, prob, REG_BR_PROB_BASE - prob, true); 2448 free_original_copy_tables(); 2449 2450 /* Loop versioning violates an assumption we try to maintain during 2451 vectorization - that the loop exit block has a single predecessor. 2452 After versioning, the exit block of both loop versions is the same 2453 basic block (i.e. it has two predecessors). Just in order to simplify 2454 following transformations in the vectorizer, we fix this situation 2455 here by adding a new (empty) block on the exit-edge of the loop, 2456 with the proper loop-exit phis to maintain loop-closed-form. */ 2457 2458 merge_bb = single_exit (loop)->dest; 2459 gcc_assert (EDGE_COUNT (merge_bb->preds) == 2); 2460 new_exit_bb = split_edge (single_exit (loop)); 2461 new_exit_e = single_exit (loop); 2462 e = EDGE_SUCC (new_exit_bb, 0); 2463 2464 for (gsi = gsi_start_phis (merge_bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2465 { 2466 tree new_res; 2467 orig_phi = gsi_stmt (gsi); 2468 new_res = copy_ssa_name (PHI_RESULT (orig_phi), NULL); 2469 new_phi = create_phi_node (new_res, new_exit_bb); 2470 arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, e); 2471 add_phi_arg (new_phi, arg, new_exit_e, 2472 gimple_phi_arg_location_from_edge (orig_phi, e)); 2473 adjust_phi_and_debug_stmts (orig_phi, e, PHI_RESULT (new_phi)); 2474 } 2475 2476 /* End loop-exit-fixes after versioning. */ 2477 2478 update_ssa (TODO_update_ssa); 2479 if (cond_expr_stmt_list) 2480 { 2481 cond_exp_gsi = gsi_last_bb (condition_bb); 2482 gsi_insert_seq_before (&cond_exp_gsi, cond_expr_stmt_list, 2483 GSI_SAME_STMT); 2484 } 2485 } 2486