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