1 /* Vectorizer 2 Copyright (C) 2003-2018 Free Software Foundation, Inc. 3 Contributed by Dorit Naishlos <dorit@il.ibm.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 /* Loop and basic block vectorizer. 22 23 This file contains drivers for the three vectorizers: 24 (1) loop vectorizer (inter-iteration parallelism), 25 (2) loop-aware SLP (intra-iteration parallelism) (invoked by the loop 26 vectorizer) 27 (3) BB vectorizer (out-of-loops), aka SLP 28 29 The rest of the vectorizer's code is organized as follows: 30 - tree-vect-loop.c - loop specific parts such as reductions, etc. These are 31 used by drivers (1) and (2). 32 - tree-vect-loop-manip.c - vectorizer's loop control-flow utilities, used by 33 drivers (1) and (2). 34 - tree-vect-slp.c - BB vectorization specific analysis and transformation, 35 used by drivers (2) and (3). 36 - tree-vect-stmts.c - statements analysis and transformation (used by all). 37 - tree-vect-data-refs.c - vectorizer specific data-refs analysis and 38 manipulations (used by all). 39 - tree-vect-patterns.c - vectorizable code patterns detector (used by all) 40 41 Here's a poor attempt at illustrating that: 42 43 tree-vectorizer.c: 44 loop_vect() loop_aware_slp() slp_vect() 45 | / \ / 46 | / \ / 47 tree-vect-loop.c tree-vect-slp.c 48 | \ \ / / | 49 | \ \/ / | 50 | \ /\ / | 51 | \ / \ / | 52 tree-vect-stmts.c tree-vect-data-refs.c 53 \ / 54 tree-vect-patterns.c 55 */ 56 57 #include "config.h" 58 #include "system.h" 59 #include "coretypes.h" 60 #include "backend.h" 61 #include "tree.h" 62 #include "gimple.h" 63 #include "predict.h" 64 #include "tree-pass.h" 65 #include "ssa.h" 66 #include "cgraph.h" 67 #include "fold-const.h" 68 #include "stor-layout.h" 69 #include "gimple-iterator.h" 70 #include "gimple-walk.h" 71 #include "tree-ssa-loop-manip.h" 72 #include "tree-ssa-loop-niter.h" 73 #include "tree-cfg.h" 74 #include "cfgloop.h" 75 #include "tree-vectorizer.h" 76 #include "tree-ssa-propagate.h" 77 #include "dbgcnt.h" 78 #include "tree-scalar-evolution.h" 79 #include "stringpool.h" 80 #include "attribs.h" 81 82 83 /* Loop or bb location. */ 84 source_location vect_location; 85 86 /* Vector mapping GIMPLE stmt to stmt_vec_info. */ 87 vec<stmt_vec_info> stmt_vec_info_vec; 88 89 /* For mapping simduid to vectorization factor. */ 90 91 struct simduid_to_vf : free_ptr_hash<simduid_to_vf> 92 { 93 unsigned int simduid; 94 poly_uint64 vf; 95 96 /* hash_table support. */ 97 static inline hashval_t hash (const simduid_to_vf *); 98 static inline int equal (const simduid_to_vf *, const simduid_to_vf *); 99 }; 100 101 inline hashval_t 102 simduid_to_vf::hash (const simduid_to_vf *p) 103 { 104 return p->simduid; 105 } 106 107 inline int 108 simduid_to_vf::equal (const simduid_to_vf *p1, const simduid_to_vf *p2) 109 { 110 return p1->simduid == p2->simduid; 111 } 112 113 /* This hash maps the OMP simd array to the corresponding simduid used 114 to index into it. Like thus, 115 116 _7 = GOMP_SIMD_LANE (simduid.0) 117 ... 118 ... 119 D.1737[_7] = stuff; 120 121 122 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of 123 simduid.0. */ 124 125 struct simd_array_to_simduid : free_ptr_hash<simd_array_to_simduid> 126 { 127 tree decl; 128 unsigned int simduid; 129 130 /* hash_table support. */ 131 static inline hashval_t hash (const simd_array_to_simduid *); 132 static inline int equal (const simd_array_to_simduid *, 133 const simd_array_to_simduid *); 134 }; 135 136 inline hashval_t 137 simd_array_to_simduid::hash (const simd_array_to_simduid *p) 138 { 139 return DECL_UID (p->decl); 140 } 141 142 inline int 143 simd_array_to_simduid::equal (const simd_array_to_simduid *p1, 144 const simd_array_to_simduid *p2) 145 { 146 return p1->decl == p2->decl; 147 } 148 149 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE, 150 into their corresponding constants and remove 151 IFN_GOMP_SIMD_ORDERED_{START,END}. */ 152 153 static void 154 adjust_simduid_builtins (hash_table<simduid_to_vf> *htab) 155 { 156 basic_block bb; 157 158 FOR_EACH_BB_FN (bb, cfun) 159 { 160 gimple_stmt_iterator i; 161 162 for (i = gsi_start_bb (bb); !gsi_end_p (i); ) 163 { 164 poly_uint64 vf = 1; 165 enum internal_fn ifn; 166 gimple *stmt = gsi_stmt (i); 167 tree t; 168 if (!is_gimple_call (stmt) 169 || !gimple_call_internal_p (stmt)) 170 { 171 gsi_next (&i); 172 continue; 173 } 174 ifn = gimple_call_internal_fn (stmt); 175 switch (ifn) 176 { 177 case IFN_GOMP_SIMD_LANE: 178 case IFN_GOMP_SIMD_VF: 179 case IFN_GOMP_SIMD_LAST_LANE: 180 break; 181 case IFN_GOMP_SIMD_ORDERED_START: 182 case IFN_GOMP_SIMD_ORDERED_END: 183 if (integer_onep (gimple_call_arg (stmt, 0))) 184 { 185 enum built_in_function bcode 186 = (ifn == IFN_GOMP_SIMD_ORDERED_START 187 ? BUILT_IN_GOMP_ORDERED_START 188 : BUILT_IN_GOMP_ORDERED_END); 189 gimple *g 190 = gimple_build_call (builtin_decl_explicit (bcode), 0); 191 tree vdef = gimple_vdef (stmt); 192 gimple_set_vdef (g, vdef); 193 SSA_NAME_DEF_STMT (vdef) = g; 194 gimple_set_vuse (g, gimple_vuse (stmt)); 195 gsi_replace (&i, g, true); 196 continue; 197 } 198 gsi_remove (&i, true); 199 unlink_stmt_vdef (stmt); 200 continue; 201 default: 202 gsi_next (&i); 203 continue; 204 } 205 tree arg = gimple_call_arg (stmt, 0); 206 gcc_assert (arg != NULL_TREE); 207 gcc_assert (TREE_CODE (arg) == SSA_NAME); 208 simduid_to_vf *p = NULL, data; 209 data.simduid = DECL_UID (SSA_NAME_VAR (arg)); 210 /* Need to nullify loop safelen field since it's value is not 211 valid after transformation. */ 212 if (bb->loop_father && bb->loop_father->safelen > 0) 213 bb->loop_father->safelen = 0; 214 if (htab) 215 { 216 p = htab->find (&data); 217 if (p) 218 vf = p->vf; 219 } 220 switch (ifn) 221 { 222 case IFN_GOMP_SIMD_VF: 223 t = build_int_cst (unsigned_type_node, vf); 224 break; 225 case IFN_GOMP_SIMD_LANE: 226 t = build_int_cst (unsigned_type_node, 0); 227 break; 228 case IFN_GOMP_SIMD_LAST_LANE: 229 t = gimple_call_arg (stmt, 1); 230 break; 231 default: 232 gcc_unreachable (); 233 } 234 tree lhs = gimple_call_lhs (stmt); 235 if (lhs) 236 replace_uses_by (lhs, t); 237 release_defs (stmt); 238 gsi_remove (&i, true); 239 } 240 } 241 } 242 243 /* Helper structure for note_simd_array_uses. */ 244 245 struct note_simd_array_uses_struct 246 { 247 hash_table<simd_array_to_simduid> **htab; 248 unsigned int simduid; 249 }; 250 251 /* Callback for note_simd_array_uses, called through walk_gimple_op. */ 252 253 static tree 254 note_simd_array_uses_cb (tree *tp, int *walk_subtrees, void *data) 255 { 256 struct walk_stmt_info *wi = (struct walk_stmt_info *) data; 257 struct note_simd_array_uses_struct *ns 258 = (struct note_simd_array_uses_struct *) wi->info; 259 260 if (TYPE_P (*tp)) 261 *walk_subtrees = 0; 262 else if (VAR_P (*tp) 263 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp)) 264 && DECL_CONTEXT (*tp) == current_function_decl) 265 { 266 simd_array_to_simduid data; 267 if (!*ns->htab) 268 *ns->htab = new hash_table<simd_array_to_simduid> (15); 269 data.decl = *tp; 270 data.simduid = ns->simduid; 271 simd_array_to_simduid **slot = (*ns->htab)->find_slot (&data, INSERT); 272 if (*slot == NULL) 273 { 274 simd_array_to_simduid *p = XNEW (simd_array_to_simduid); 275 *p = data; 276 *slot = p; 277 } 278 else if ((*slot)->simduid != ns->simduid) 279 (*slot)->simduid = -1U; 280 *walk_subtrees = 0; 281 } 282 return NULL_TREE; 283 } 284 285 /* Find "omp simd array" temporaries and map them to corresponding 286 simduid. */ 287 288 static void 289 note_simd_array_uses (hash_table<simd_array_to_simduid> **htab) 290 { 291 basic_block bb; 292 gimple_stmt_iterator gsi; 293 struct walk_stmt_info wi; 294 struct note_simd_array_uses_struct ns; 295 296 memset (&wi, 0, sizeof (wi)); 297 wi.info = &ns; 298 ns.htab = htab; 299 300 FOR_EACH_BB_FN (bb, cfun) 301 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 302 { 303 gimple *stmt = gsi_stmt (gsi); 304 if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt)) 305 continue; 306 switch (gimple_call_internal_fn (stmt)) 307 { 308 case IFN_GOMP_SIMD_LANE: 309 case IFN_GOMP_SIMD_VF: 310 case IFN_GOMP_SIMD_LAST_LANE: 311 break; 312 default: 313 continue; 314 } 315 tree lhs = gimple_call_lhs (stmt); 316 if (lhs == NULL_TREE) 317 continue; 318 imm_use_iterator use_iter; 319 gimple *use_stmt; 320 ns.simduid = DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt, 0))); 321 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs) 322 if (!is_gimple_debug (use_stmt)) 323 walk_gimple_op (use_stmt, note_simd_array_uses_cb, &wi); 324 } 325 } 326 327 /* Shrink arrays with "omp simd array" attribute to the corresponding 328 vectorization factor. */ 329 330 static void 331 shrink_simd_arrays 332 (hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab, 333 hash_table<simduid_to_vf> *simduid_to_vf_htab) 334 { 335 for (hash_table<simd_array_to_simduid>::iterator iter 336 = simd_array_to_simduid_htab->begin (); 337 iter != simd_array_to_simduid_htab->end (); ++iter) 338 if ((*iter)->simduid != -1U) 339 { 340 tree decl = (*iter)->decl; 341 poly_uint64 vf = 1; 342 if (simduid_to_vf_htab) 343 { 344 simduid_to_vf *p = NULL, data; 345 data.simduid = (*iter)->simduid; 346 p = simduid_to_vf_htab->find (&data); 347 if (p) 348 vf = p->vf; 349 } 350 tree atype 351 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl)), vf); 352 TREE_TYPE (decl) = atype; 353 relayout_decl (decl); 354 } 355 356 delete simd_array_to_simduid_htab; 357 } 358 359 /* Initialize the vec_info with kind KIND_IN and target cost data 360 TARGET_COST_DATA_IN. */ 361 362 vec_info::vec_info (vec_info::vec_kind kind_in, void *target_cost_data_in) 363 : kind (kind_in), 364 datarefs (vNULL), 365 ddrs (vNULL), 366 target_cost_data (target_cost_data_in) 367 { 368 } 369 370 vec_info::~vec_info () 371 { 372 slp_instance instance; 373 struct data_reference *dr; 374 unsigned int i; 375 376 FOR_EACH_VEC_ELT (datarefs, i, dr) 377 if (dr->aux) 378 { 379 free (dr->aux); 380 dr->aux = NULL; 381 } 382 383 FOR_EACH_VEC_ELT (slp_instances, i, instance) 384 vect_free_slp_instance (instance); 385 386 free_data_refs (datarefs); 387 free_dependence_relations (ddrs); 388 destroy_cost_data (target_cost_data); 389 } 390 391 /* A helper function to free scev and LOOP niter information, as well as 392 clear loop constraint LOOP_C_FINITE. */ 393 394 void 395 vect_free_loop_info_assumptions (struct loop *loop) 396 { 397 scev_reset_htab (); 398 /* We need to explicitly reset upper bound information since they are 399 used even after free_numbers_of_iterations_estimates. */ 400 loop->any_upper_bound = false; 401 loop->any_likely_upper_bound = false; 402 free_numbers_of_iterations_estimates (loop); 403 loop_constraint_clear (loop, LOOP_C_FINITE); 404 } 405 406 /* Return whether STMT is inside the region we try to vectorize. */ 407 408 bool 409 vect_stmt_in_region_p (vec_info *vinfo, gimple *stmt) 410 { 411 if (!gimple_bb (stmt)) 412 return false; 413 414 if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo)) 415 { 416 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 417 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) 418 return false; 419 } 420 else 421 { 422 bb_vec_info bb_vinfo = as_a <bb_vec_info> (vinfo); 423 if (gimple_bb (stmt) != BB_VINFO_BB (bb_vinfo) 424 || gimple_uid (stmt) == -1U 425 || gimple_code (stmt) == GIMPLE_PHI) 426 return false; 427 } 428 429 return true; 430 } 431 432 433 /* If LOOP has been versioned during ifcvt, return the internal call 434 guarding it. */ 435 436 static gimple * 437 vect_loop_vectorized_call (struct loop *loop) 438 { 439 basic_block bb = loop_preheader_edge (loop)->src; 440 gimple *g; 441 do 442 { 443 g = last_stmt (bb); 444 if (g) 445 break; 446 if (!single_pred_p (bb)) 447 break; 448 bb = single_pred (bb); 449 } 450 while (1); 451 if (g && gimple_code (g) == GIMPLE_COND) 452 { 453 gimple_stmt_iterator gsi = gsi_for_stmt (g); 454 gsi_prev (&gsi); 455 if (!gsi_end_p (gsi)) 456 { 457 g = gsi_stmt (gsi); 458 if (gimple_call_internal_p (g, IFN_LOOP_VECTORIZED) 459 && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->num 460 || tree_to_shwi (gimple_call_arg (g, 1)) == loop->num)) 461 return g; 462 } 463 } 464 return NULL; 465 } 466 467 /* If LOOP has been versioned during loop distribution, return the gurading 468 internal call. */ 469 470 static gimple * 471 vect_loop_dist_alias_call (struct loop *loop) 472 { 473 basic_block bb; 474 basic_block entry; 475 struct loop *outer, *orig; 476 gimple_stmt_iterator gsi; 477 gimple *g; 478 479 if (loop->orig_loop_num == 0) 480 return NULL; 481 482 orig = get_loop (cfun, loop->orig_loop_num); 483 if (orig == NULL) 484 { 485 /* The original loop is somehow destroyed. Clear the information. */ 486 loop->orig_loop_num = 0; 487 return NULL; 488 } 489 490 if (loop != orig) 491 bb = nearest_common_dominator (CDI_DOMINATORS, loop->header, orig->header); 492 else 493 bb = loop_preheader_edge (loop)->src; 494 495 outer = bb->loop_father; 496 entry = ENTRY_BLOCK_PTR_FOR_FN (cfun); 497 498 /* Look upward in dominance tree. */ 499 for (; bb != entry && flow_bb_inside_loop_p (outer, bb); 500 bb = get_immediate_dominator (CDI_DOMINATORS, bb)) 501 { 502 g = last_stmt (bb); 503 if (g == NULL || gimple_code (g) != GIMPLE_COND) 504 continue; 505 506 gsi = gsi_for_stmt (g); 507 gsi_prev (&gsi); 508 if (gsi_end_p (gsi)) 509 continue; 510 511 g = gsi_stmt (gsi); 512 /* The guarding internal function call must have the same distribution 513 alias id. */ 514 if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS) 515 && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->orig_loop_num)) 516 return g; 517 } 518 return NULL; 519 } 520 521 /* Set the uids of all the statements in basic blocks inside loop 522 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal 523 call guarding the loop which has been if converted. */ 524 static void 525 set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call) 526 { 527 tree arg = gimple_call_arg (loop_vectorized_call, 1); 528 basic_block *bbs; 529 unsigned int i; 530 struct loop *scalar_loop = get_loop (cfun, tree_to_shwi (arg)); 531 532 LOOP_VINFO_SCALAR_LOOP (loop_vinfo) = scalar_loop; 533 gcc_checking_assert (vect_loop_vectorized_call (scalar_loop) 534 == loop_vectorized_call); 535 /* If we are going to vectorize outer loop, prevent vectorization 536 of the inner loop in the scalar loop - either the scalar loop is 537 thrown away, so it is a wasted work, or is used only for 538 a few iterations. */ 539 if (scalar_loop->inner) 540 { 541 gimple *g = vect_loop_vectorized_call (scalar_loop->inner); 542 if (g) 543 { 544 arg = gimple_call_arg (g, 0); 545 get_loop (cfun, tree_to_shwi (arg))->dont_vectorize = true; 546 fold_loop_internal_call (g, boolean_false_node); 547 } 548 } 549 bbs = get_loop_body (scalar_loop); 550 for (i = 0; i < scalar_loop->num_nodes; i++) 551 { 552 basic_block bb = bbs[i]; 553 gimple_stmt_iterator gsi; 554 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 555 { 556 gimple *phi = gsi_stmt (gsi); 557 gimple_set_uid (phi, 0); 558 } 559 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 560 { 561 gimple *stmt = gsi_stmt (gsi); 562 gimple_set_uid (stmt, 0); 563 } 564 } 565 free (bbs); 566 } 567 568 /* Function vectorize_loops. 569 570 Entry point to loop vectorization phase. */ 571 572 unsigned 573 vectorize_loops (void) 574 { 575 unsigned int i; 576 unsigned int num_vectorized_loops = 0; 577 unsigned int vect_loops_num; 578 struct loop *loop; 579 hash_table<simduid_to_vf> *simduid_to_vf_htab = NULL; 580 hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL; 581 bool any_ifcvt_loops = false; 582 unsigned ret = 0; 583 struct loop *new_loop; 584 585 vect_loops_num = number_of_loops (cfun); 586 587 /* Bail out if there are no loops. */ 588 if (vect_loops_num <= 1) 589 return 0; 590 591 if (cfun->has_simduid_loops) 592 note_simd_array_uses (&simd_array_to_simduid_htab); 593 594 init_stmt_vec_info_vec (); 595 596 /* ----------- Analyze loops. ----------- */ 597 598 /* If some loop was duplicated, it gets bigger number 599 than all previously defined loops. This fact allows us to run 600 only over initial loops skipping newly generated ones. */ 601 FOR_EACH_LOOP (loop, 0) 602 if (loop->dont_vectorize) 603 { 604 any_ifcvt_loops = true; 605 /* If-conversion sometimes versions both the outer loop 606 (for the case when outer loop vectorization might be 607 desirable) as well as the inner loop in the scalar version 608 of the loop. So we have: 609 if (LOOP_VECTORIZED (1, 3)) 610 { 611 loop1 612 loop2 613 } 614 else 615 loop3 (copy of loop1) 616 if (LOOP_VECTORIZED (4, 5)) 617 loop4 (copy of loop2) 618 else 619 loop5 (copy of loop4) 620 If FOR_EACH_LOOP gives us loop3 first (which has 621 dont_vectorize set), make sure to process loop1 before loop4; 622 so that we can prevent vectorization of loop4 if loop1 623 is successfully vectorized. */ 624 if (loop->inner) 625 { 626 gimple *loop_vectorized_call 627 = vect_loop_vectorized_call (loop); 628 if (loop_vectorized_call 629 && vect_loop_vectorized_call (loop->inner)) 630 { 631 tree arg = gimple_call_arg (loop_vectorized_call, 0); 632 struct loop *vector_loop 633 = get_loop (cfun, tree_to_shwi (arg)); 634 if (vector_loop && vector_loop != loop) 635 { 636 loop = vector_loop; 637 /* Make sure we don't vectorize it twice. */ 638 loop->dont_vectorize = true; 639 goto try_vectorize; 640 } 641 } 642 } 643 } 644 else 645 { 646 loop_vec_info loop_vinfo, orig_loop_vinfo; 647 gimple *loop_vectorized_call, *loop_dist_alias_call; 648 try_vectorize: 649 if (!((flag_tree_loop_vectorize 650 && optimize_loop_nest_for_speed_p (loop)) 651 || loop->force_vectorize)) 652 continue; 653 orig_loop_vinfo = NULL; 654 loop_vectorized_call = vect_loop_vectorized_call (loop); 655 loop_dist_alias_call = vect_loop_dist_alias_call (loop); 656 vectorize_epilogue: 657 vect_location = find_loop_location (loop); 658 if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION 659 && dump_enabled_p ()) 660 dump_printf (MSG_NOTE, "\nAnalyzing loop at %s:%d\n", 661 LOCATION_FILE (vect_location), 662 LOCATION_LINE (vect_location)); 663 664 loop_vinfo = vect_analyze_loop (loop, orig_loop_vinfo); 665 loop->aux = loop_vinfo; 666 667 if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo)) 668 { 669 /* Free existing information if loop is analyzed with some 670 assumptions. */ 671 if (loop_constraint_set_p (loop, LOOP_C_FINITE)) 672 vect_free_loop_info_assumptions (loop); 673 674 /* If we applied if-conversion then try to vectorize the 675 BB of innermost loops. 676 ??? Ideally BB vectorization would learn to vectorize 677 control flow by applying if-conversion on-the-fly, the 678 following retains the if-converted loop body even when 679 only non-if-converted parts took part in BB vectorization. */ 680 if (flag_tree_slp_vectorize != 0 681 && loop_vectorized_call 682 && ! loop->inner) 683 { 684 basic_block bb = loop->header; 685 bool has_mask_load_store = false; 686 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); 687 !gsi_end_p (gsi); gsi_next (&gsi)) 688 { 689 gimple *stmt = gsi_stmt (gsi); 690 if (is_gimple_call (stmt) 691 && gimple_call_internal_p (stmt) 692 && (gimple_call_internal_fn (stmt) == IFN_MASK_LOAD 693 || gimple_call_internal_fn (stmt) == IFN_MASK_STORE)) 694 { 695 has_mask_load_store = true; 696 break; 697 } 698 gimple_set_uid (stmt, -1); 699 gimple_set_visited (stmt, false); 700 } 701 if (! has_mask_load_store && vect_slp_bb (bb)) 702 { 703 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 704 "basic block vectorized\n"); 705 fold_loop_internal_call (loop_vectorized_call, 706 boolean_true_node); 707 loop_vectorized_call = NULL; 708 ret |= TODO_cleanup_cfg; 709 } 710 } 711 /* If outer loop vectorization fails for LOOP_VECTORIZED guarded 712 loop, don't vectorize its inner loop; we'll attempt to 713 vectorize LOOP_VECTORIZED guarded inner loop of the scalar 714 loop version. */ 715 if (loop_vectorized_call && loop->inner) 716 loop->inner->dont_vectorize = true; 717 continue; 718 } 719 720 if (!dbg_cnt (vect_loop)) 721 { 722 /* We may miss some if-converted loops due to 723 debug counter. Set any_ifcvt_loops to visit 724 them at finalization. */ 725 any_ifcvt_loops = true; 726 /* Free existing information if loop is analyzed with some 727 assumptions. */ 728 if (loop_constraint_set_p (loop, LOOP_C_FINITE)) 729 vect_free_loop_info_assumptions (loop); 730 731 break; 732 } 733 734 if (loop_vectorized_call) 735 set_uid_loop_bbs (loop_vinfo, loop_vectorized_call); 736 if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION 737 && dump_enabled_p ()) 738 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 739 "loop vectorized\n"); 740 new_loop = vect_transform_loop (loop_vinfo); 741 num_vectorized_loops++; 742 /* Now that the loop has been vectorized, allow it to be unrolled 743 etc. */ 744 loop->force_vectorize = false; 745 746 if (loop->simduid) 747 { 748 simduid_to_vf *simduid_to_vf_data = XNEW (simduid_to_vf); 749 if (!simduid_to_vf_htab) 750 simduid_to_vf_htab = new hash_table<simduid_to_vf> (15); 751 simduid_to_vf_data->simduid = DECL_UID (loop->simduid); 752 simduid_to_vf_data->vf = loop_vinfo->vectorization_factor; 753 *simduid_to_vf_htab->find_slot (simduid_to_vf_data, INSERT) 754 = simduid_to_vf_data; 755 } 756 757 if (loop_vectorized_call) 758 { 759 fold_loop_internal_call (loop_vectorized_call, boolean_true_node); 760 loop_vectorized_call = NULL; 761 ret |= TODO_cleanup_cfg; 762 } 763 if (loop_dist_alias_call) 764 { 765 tree value = gimple_call_arg (loop_dist_alias_call, 1); 766 fold_loop_internal_call (loop_dist_alias_call, value); 767 loop_dist_alias_call = NULL; 768 ret |= TODO_cleanup_cfg; 769 } 770 771 if (new_loop) 772 { 773 /* Epilogue of vectorized loop must be vectorized too. */ 774 vect_loops_num = number_of_loops (cfun); 775 loop = new_loop; 776 orig_loop_vinfo = loop_vinfo; /* To pass vect_analyze_loop. */ 777 goto vectorize_epilogue; 778 } 779 } 780 781 vect_location = UNKNOWN_LOCATION; 782 783 statistics_counter_event (cfun, "Vectorized loops", num_vectorized_loops); 784 if (dump_enabled_p () 785 || (num_vectorized_loops > 0 && dump_enabled_p ())) 786 dump_printf_loc (MSG_NOTE, vect_location, 787 "vectorized %u loops in function.\n", 788 num_vectorized_loops); 789 790 /* ----------- Finalize. ----------- */ 791 792 if (any_ifcvt_loops) 793 for (i = 1; i < vect_loops_num; i++) 794 { 795 loop = get_loop (cfun, i); 796 if (loop && loop->dont_vectorize) 797 { 798 gimple *g = vect_loop_vectorized_call (loop); 799 if (g) 800 { 801 fold_loop_internal_call (g, boolean_false_node); 802 ret |= TODO_cleanup_cfg; 803 g = NULL; 804 } 805 else 806 g = vect_loop_dist_alias_call (loop); 807 808 if (g) 809 { 810 fold_loop_internal_call (g, boolean_false_node); 811 ret |= TODO_cleanup_cfg; 812 } 813 } 814 } 815 816 for (i = 1; i < vect_loops_num; i++) 817 { 818 loop_vec_info loop_vinfo; 819 bool has_mask_store; 820 821 loop = get_loop (cfun, i); 822 if (!loop) 823 continue; 824 loop_vinfo = (loop_vec_info) loop->aux; 825 has_mask_store = false; 826 if (loop_vinfo) 827 has_mask_store = LOOP_VINFO_HAS_MASK_STORE (loop_vinfo); 828 delete loop_vinfo; 829 if (has_mask_store 830 && targetm.vectorize.empty_mask_is_expensive (IFN_MASK_STORE)) 831 optimize_mask_stores (loop); 832 loop->aux = NULL; 833 } 834 835 free_stmt_vec_info_vec (); 836 837 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */ 838 if (cfun->has_simduid_loops) 839 adjust_simduid_builtins (simduid_to_vf_htab); 840 841 /* Shrink any "omp array simd" temporary arrays to the 842 actual vectorization factors. */ 843 if (simd_array_to_simduid_htab) 844 shrink_simd_arrays (simd_array_to_simduid_htab, simduid_to_vf_htab); 845 delete simduid_to_vf_htab; 846 cfun->has_simduid_loops = false; 847 848 if (num_vectorized_loops > 0) 849 { 850 /* If we vectorized any loop only virtual SSA form needs to be updated. 851 ??? Also while we try hard to update loop-closed SSA form we fail 852 to properly do this in some corner-cases (see PR56286). */ 853 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_only_virtuals); 854 return TODO_cleanup_cfg; 855 } 856 857 return ret; 858 } 859 860 861 /* Entry point to the simduid cleanup pass. */ 862 863 namespace { 864 865 const pass_data pass_data_simduid_cleanup = 866 { 867 GIMPLE_PASS, /* type */ 868 "simduid", /* name */ 869 OPTGROUP_NONE, /* optinfo_flags */ 870 TV_NONE, /* tv_id */ 871 ( PROP_ssa | PROP_cfg ), /* properties_required */ 872 0, /* properties_provided */ 873 0, /* properties_destroyed */ 874 0, /* todo_flags_start */ 875 0, /* todo_flags_finish */ 876 }; 877 878 class pass_simduid_cleanup : public gimple_opt_pass 879 { 880 public: 881 pass_simduid_cleanup (gcc::context *ctxt) 882 : gimple_opt_pass (pass_data_simduid_cleanup, ctxt) 883 {} 884 885 /* opt_pass methods: */ 886 opt_pass * clone () { return new pass_simduid_cleanup (m_ctxt); } 887 virtual bool gate (function *fun) { return fun->has_simduid_loops; } 888 virtual unsigned int execute (function *); 889 890 }; // class pass_simduid_cleanup 891 892 unsigned int 893 pass_simduid_cleanup::execute (function *fun) 894 { 895 hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL; 896 897 note_simd_array_uses (&simd_array_to_simduid_htab); 898 899 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */ 900 adjust_simduid_builtins (NULL); 901 902 /* Shrink any "omp array simd" temporary arrays to the 903 actual vectorization factors. */ 904 if (simd_array_to_simduid_htab) 905 shrink_simd_arrays (simd_array_to_simduid_htab, NULL); 906 fun->has_simduid_loops = false; 907 return 0; 908 } 909 910 } // anon namespace 911 912 gimple_opt_pass * 913 make_pass_simduid_cleanup (gcc::context *ctxt) 914 { 915 return new pass_simduid_cleanup (ctxt); 916 } 917 918 919 /* Entry point to basic block SLP phase. */ 920 921 namespace { 922 923 const pass_data pass_data_slp_vectorize = 924 { 925 GIMPLE_PASS, /* type */ 926 "slp", /* name */ 927 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */ 928 TV_TREE_SLP_VECTORIZATION, /* tv_id */ 929 ( PROP_ssa | PROP_cfg ), /* properties_required */ 930 0, /* properties_provided */ 931 0, /* properties_destroyed */ 932 0, /* todo_flags_start */ 933 TODO_update_ssa, /* todo_flags_finish */ 934 }; 935 936 class pass_slp_vectorize : public gimple_opt_pass 937 { 938 public: 939 pass_slp_vectorize (gcc::context *ctxt) 940 : gimple_opt_pass (pass_data_slp_vectorize, ctxt) 941 {} 942 943 /* opt_pass methods: */ 944 opt_pass * clone () { return new pass_slp_vectorize (m_ctxt); } 945 virtual bool gate (function *) { return flag_tree_slp_vectorize != 0; } 946 virtual unsigned int execute (function *); 947 948 }; // class pass_slp_vectorize 949 950 unsigned int 951 pass_slp_vectorize::execute (function *fun) 952 { 953 basic_block bb; 954 955 bool in_loop_pipeline = scev_initialized_p (); 956 if (!in_loop_pipeline) 957 { 958 loop_optimizer_init (LOOPS_NORMAL); 959 scev_initialize (); 960 } 961 962 /* Mark all stmts as not belonging to the current region and unvisited. */ 963 FOR_EACH_BB_FN (bb, fun) 964 { 965 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 966 gsi_next (&gsi)) 967 { 968 gimple *stmt = gsi_stmt (gsi); 969 gimple_set_uid (stmt, -1); 970 gimple_set_visited (stmt, false); 971 } 972 } 973 974 init_stmt_vec_info_vec (); 975 976 FOR_EACH_BB_FN (bb, fun) 977 { 978 if (vect_slp_bb (bb)) 979 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 980 "basic block vectorized\n"); 981 } 982 983 free_stmt_vec_info_vec (); 984 985 if (!in_loop_pipeline) 986 { 987 scev_finalize (); 988 loop_optimizer_finalize (); 989 } 990 991 return 0; 992 } 993 994 } // anon namespace 995 996 gimple_opt_pass * 997 make_pass_slp_vectorize (gcc::context *ctxt) 998 { 999 return new pass_slp_vectorize (ctxt); 1000 } 1001 1002 1003 /* Increase alignment of global arrays to improve vectorization potential. 1004 TODO: 1005 - Consider also structs that have an array field. 1006 - Use ipa analysis to prune arrays that can't be vectorized? 1007 This should involve global alignment analysis and in the future also 1008 array padding. */ 1009 1010 static unsigned get_vec_alignment_for_type (tree); 1011 static hash_map<tree, unsigned> *type_align_map; 1012 1013 /* Return alignment of array's vector type corresponding to scalar type. 1014 0 if no vector type exists. */ 1015 static unsigned 1016 get_vec_alignment_for_array_type (tree type) 1017 { 1018 gcc_assert (TREE_CODE (type) == ARRAY_TYPE); 1019 poly_uint64 array_size, vector_size; 1020 1021 tree vectype = get_vectype_for_scalar_type (strip_array_types (type)); 1022 if (!vectype 1023 || !poly_int_tree_p (TYPE_SIZE (type), &array_size) 1024 || !poly_int_tree_p (TYPE_SIZE (vectype), &vector_size) 1025 || maybe_lt (array_size, vector_size)) 1026 return 0; 1027 1028 return TYPE_ALIGN (vectype); 1029 } 1030 1031 /* Return alignment of field having maximum alignment of vector type 1032 corresponding to it's scalar type. For now, we only consider fields whose 1033 offset is a multiple of it's vector alignment. 1034 0 if no suitable field is found. */ 1035 static unsigned 1036 get_vec_alignment_for_record_type (tree type) 1037 { 1038 gcc_assert (TREE_CODE (type) == RECORD_TYPE); 1039 1040 unsigned max_align = 0, alignment; 1041 HOST_WIDE_INT offset; 1042 tree offset_tree; 1043 1044 if (TYPE_PACKED (type)) 1045 return 0; 1046 1047 unsigned *slot = type_align_map->get (type); 1048 if (slot) 1049 return *slot; 1050 1051 for (tree field = first_field (type); 1052 field != NULL_TREE; 1053 field = DECL_CHAIN (field)) 1054 { 1055 /* Skip if not FIELD_DECL or if alignment is set by user. */ 1056 if (TREE_CODE (field) != FIELD_DECL 1057 || DECL_USER_ALIGN (field) 1058 || DECL_ARTIFICIAL (field)) 1059 continue; 1060 1061 /* We don't need to process the type further if offset is variable, 1062 since the offsets of remaining members will also be variable. */ 1063 if (TREE_CODE (DECL_FIELD_OFFSET (field)) != INTEGER_CST 1064 || TREE_CODE (DECL_FIELD_BIT_OFFSET (field)) != INTEGER_CST) 1065 break; 1066 1067 /* Similarly stop processing the type if offset_tree 1068 does not fit in unsigned HOST_WIDE_INT. */ 1069 offset_tree = bit_position (field); 1070 if (!tree_fits_uhwi_p (offset_tree)) 1071 break; 1072 1073 offset = tree_to_uhwi (offset_tree); 1074 alignment = get_vec_alignment_for_type (TREE_TYPE (field)); 1075 1076 /* Get maximum alignment of vectorized field/array among those members 1077 whose offset is multiple of the vector alignment. */ 1078 if (alignment 1079 && (offset % alignment == 0) 1080 && (alignment > max_align)) 1081 max_align = alignment; 1082 } 1083 1084 type_align_map->put (type, max_align); 1085 return max_align; 1086 } 1087 1088 /* Return alignment of vector type corresponding to decl's scalar type 1089 or 0 if it doesn't exist or the vector alignment is lesser than 1090 decl's alignment. */ 1091 static unsigned 1092 get_vec_alignment_for_type (tree type) 1093 { 1094 if (type == NULL_TREE) 1095 return 0; 1096 1097 gcc_assert (TYPE_P (type)); 1098 1099 static unsigned alignment = 0; 1100 switch (TREE_CODE (type)) 1101 { 1102 case ARRAY_TYPE: 1103 alignment = get_vec_alignment_for_array_type (type); 1104 break; 1105 case RECORD_TYPE: 1106 alignment = get_vec_alignment_for_record_type (type); 1107 break; 1108 default: 1109 alignment = 0; 1110 break; 1111 } 1112 1113 return (alignment > TYPE_ALIGN (type)) ? alignment : 0; 1114 } 1115 1116 /* Entry point to increase_alignment pass. */ 1117 static unsigned int 1118 increase_alignment (void) 1119 { 1120 varpool_node *vnode; 1121 1122 vect_location = UNKNOWN_LOCATION; 1123 type_align_map = new hash_map<tree, unsigned>; 1124 1125 /* Increase the alignment of all global arrays for vectorization. */ 1126 FOR_EACH_DEFINED_VARIABLE (vnode) 1127 { 1128 tree decl = vnode->decl; 1129 unsigned int alignment; 1130 1131 if ((decl_in_symtab_p (decl) 1132 && !symtab_node::get (decl)->can_increase_alignment_p ()) 1133 || DECL_USER_ALIGN (decl) || DECL_ARTIFICIAL (decl)) 1134 continue; 1135 1136 alignment = get_vec_alignment_for_type (TREE_TYPE (decl)); 1137 if (alignment && vect_can_force_dr_alignment_p (decl, alignment)) 1138 { 1139 vnode->increase_alignment (alignment); 1140 dump_printf (MSG_NOTE, "Increasing alignment of decl: "); 1141 dump_generic_expr (MSG_NOTE, TDF_SLIM, decl); 1142 dump_printf (MSG_NOTE, "\n"); 1143 } 1144 } 1145 1146 delete type_align_map; 1147 return 0; 1148 } 1149 1150 1151 namespace { 1152 1153 const pass_data pass_data_ipa_increase_alignment = 1154 { 1155 SIMPLE_IPA_PASS, /* type */ 1156 "increase_alignment", /* name */ 1157 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */ 1158 TV_IPA_OPT, /* tv_id */ 1159 0, /* properties_required */ 1160 0, /* properties_provided */ 1161 0, /* properties_destroyed */ 1162 0, /* todo_flags_start */ 1163 0, /* todo_flags_finish */ 1164 }; 1165 1166 class pass_ipa_increase_alignment : public simple_ipa_opt_pass 1167 { 1168 public: 1169 pass_ipa_increase_alignment (gcc::context *ctxt) 1170 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment, ctxt) 1171 {} 1172 1173 /* opt_pass methods: */ 1174 virtual bool gate (function *) 1175 { 1176 return flag_section_anchors && flag_tree_loop_vectorize; 1177 } 1178 1179 virtual unsigned int execute (function *) { return increase_alignment (); } 1180 1181 }; // class pass_ipa_increase_alignment 1182 1183 } // anon namespace 1184 1185 simple_ipa_opt_pass * 1186 make_pass_ipa_increase_alignment (gcc::context *ctxt) 1187 { 1188 return new pass_ipa_increase_alignment (ctxt); 1189 } 1190