1/* Analysis Utilities for Loop Vectorization. 2 Copyright (C) 2003,2004,2005,2006 Free Software Foundation, Inc. 3 Contributed by Dorit Naishlos <dorit@il.ibm.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "ggc.h" 27#include "tree.h" 28#include "target.h" 29#include "basic-block.h" 30#include "diagnostic.h" 31#include "tree-flow.h" 32#include "tree-dump.h" 33#include "timevar.h" 34#include "cfgloop.h" 35#include "expr.h" 36#include "optabs.h" 37#include "params.h" 38#include "tree-chrec.h" 39#include "tree-data-ref.h" 40#include "tree-scalar-evolution.h" 41#include "tree-vectorizer.h" 42 43/* Main analysis functions. */ 44static loop_vec_info vect_analyze_loop_form (struct loop *); 45static bool vect_analyze_data_refs (loop_vec_info); 46static bool vect_mark_stmts_to_be_vectorized (loop_vec_info); 47static void vect_analyze_scalar_cycles (loop_vec_info); 48static bool vect_analyze_data_ref_accesses (loop_vec_info); 49static bool vect_analyze_data_ref_dependences (loop_vec_info); 50static bool vect_analyze_data_refs_alignment (loop_vec_info); 51static bool vect_compute_data_refs_alignment (loop_vec_info); 52static bool vect_enhance_data_refs_alignment (loop_vec_info); 53static bool vect_analyze_operations (loop_vec_info); 54static bool vect_determine_vectorization_factor (loop_vec_info); 55 56/* Utility functions for the analyses. */ 57static bool exist_non_indexing_operands_for_use_p (tree, tree); 58static void vect_mark_relevant (VEC(tree,heap) **, tree, bool, bool); 59static bool vect_stmt_relevant_p (tree, loop_vec_info, bool *, bool *); 60static tree vect_get_loop_niters (struct loop *, tree *); 61static bool vect_analyze_data_ref_dependence 62 (struct data_dependence_relation *, loop_vec_info); 63static bool vect_compute_data_ref_alignment (struct data_reference *); 64static bool vect_analyze_data_ref_access (struct data_reference *); 65static bool vect_can_advance_ivs_p (loop_vec_info); 66static void vect_update_misalignment_for_peel 67 (struct data_reference *, struct data_reference *, int npeel); 68 69 70/* Function vect_determine_vectorization_factor 71 72 Determine the vectorization factor (VF). VF is the number of data elements 73 that are operated upon in parallel in a single iteration of the vectorized 74 loop. For example, when vectorizing a loop that operates on 4byte elements, 75 on a target with vector size (VS) 16byte, the VF is set to 4, since 4 76 elements can fit in a single vector register. 77 78 We currently support vectorization of loops in which all types operated upon 79 are of the same size. Therefore this function currently sets VF according to 80 the size of the types operated upon, and fails if there are multiple sizes 81 in the loop. 82 83 VF is also the factor by which the loop iterations are strip-mined, e.g.: 84 original loop: 85 for (i=0; i<N; i++){ 86 a[i] = b[i] + c[i]; 87 } 88 89 vectorized loop: 90 for (i=0; i<N; i+=VF){ 91 a[i:VF] = b[i:VF] + c[i:VF]; 92 } 93*/ 94 95static bool 96vect_determine_vectorization_factor (loop_vec_info loop_vinfo) 97{ 98 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 99 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo); 100 int nbbs = loop->num_nodes; 101 block_stmt_iterator si; 102 unsigned int vectorization_factor = 0; 103 int i; 104 tree scalar_type; 105 106 if (vect_print_dump_info (REPORT_DETAILS)) 107 fprintf (vect_dump, "=== vect_determine_vectorization_factor ==="); 108 109 for (i = 0; i < nbbs; i++) 110 { 111 basic_block bb = bbs[i]; 112 113 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 114 { 115 tree stmt = bsi_stmt (si); 116 unsigned int nunits; 117 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 118 tree vectype; 119 120 if (vect_print_dump_info (REPORT_DETAILS)) 121 { 122 fprintf (vect_dump, "==> examining statement: "); 123 print_generic_expr (vect_dump, stmt, TDF_SLIM); 124 } 125 126 gcc_assert (stmt_info); 127 /* skip stmts which do not need to be vectorized. */ 128 if (!STMT_VINFO_RELEVANT_P (stmt_info) 129 && !STMT_VINFO_LIVE_P (stmt_info)) 130 { 131 if (vect_print_dump_info (REPORT_DETAILS)) 132 fprintf (vect_dump, "skip."); 133 continue; 134 } 135 136 if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt)))) 137 { 138 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 139 { 140 fprintf (vect_dump, "not vectorized: vector stmt in loop:"); 141 print_generic_expr (vect_dump, stmt, TDF_SLIM); 142 } 143 return false; 144 } 145 146 if (STMT_VINFO_VECTYPE (stmt_info)) 147 { 148 vectype = STMT_VINFO_VECTYPE (stmt_info); 149 scalar_type = TREE_TYPE (vectype); 150 } 151 else 152 { 153 if (STMT_VINFO_DATA_REF (stmt_info)) 154 scalar_type = 155 TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info))); 156 else if (TREE_CODE (stmt) == MODIFY_EXPR) 157 scalar_type = TREE_TYPE (TREE_OPERAND (stmt, 0)); 158 else 159 scalar_type = TREE_TYPE (stmt); 160 161 if (vect_print_dump_info (REPORT_DETAILS)) 162 { 163 fprintf (vect_dump, "get vectype for scalar type: "); 164 print_generic_expr (vect_dump, scalar_type, TDF_SLIM); 165 } 166 167 vectype = get_vectype_for_scalar_type (scalar_type); 168 if (!vectype) 169 { 170 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 171 { 172 fprintf (vect_dump, 173 "not vectorized: unsupported data-type "); 174 print_generic_expr (vect_dump, scalar_type, TDF_SLIM); 175 } 176 return false; 177 } 178 STMT_VINFO_VECTYPE (stmt_info) = vectype; 179 } 180 181 if (vect_print_dump_info (REPORT_DETAILS)) 182 { 183 fprintf (vect_dump, "vectype: "); 184 print_generic_expr (vect_dump, vectype, TDF_SLIM); 185 } 186 187 nunits = TYPE_VECTOR_SUBPARTS (vectype); 188 if (vect_print_dump_info (REPORT_DETAILS)) 189 fprintf (vect_dump, "nunits = %d", nunits); 190 191 if (vectorization_factor) 192 { 193 /* FORNOW: don't allow mixed units. 194 This restriction will be relaxed in the future. */ 195 if (nunits != vectorization_factor) 196 { 197 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 198 fprintf (vect_dump, "not vectorized: mixed data-types"); 199 return false; 200 } 201 } 202 else 203 vectorization_factor = nunits; 204 205 gcc_assert (GET_MODE_SIZE (TYPE_MODE (scalar_type)) 206 * vectorization_factor == UNITS_PER_SIMD_WORD); 207 } 208 } 209 210 /* TODO: Analyze cost. Decide if worth while to vectorize. */ 211 212 if (vectorization_factor <= 1) 213 { 214 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 215 fprintf (vect_dump, "not vectorized: unsupported data-type"); 216 return false; 217 } 218 LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor; 219 220 return true; 221} 222 223 224/* Function vect_analyze_operations. 225 226 Scan the loop stmts and make sure they are all vectorizable. */ 227 228static bool 229vect_analyze_operations (loop_vec_info loop_vinfo) 230{ 231 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 232 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo); 233 int nbbs = loop->num_nodes; 234 block_stmt_iterator si; 235 unsigned int vectorization_factor = 0; 236 int i; 237 bool ok; 238 tree phi; 239 stmt_vec_info stmt_info; 240 bool need_to_vectorize = false; 241 242 if (vect_print_dump_info (REPORT_DETAILS)) 243 fprintf (vect_dump, "=== vect_analyze_operations ==="); 244 245 gcc_assert (LOOP_VINFO_VECT_FACTOR (loop_vinfo)); 246 vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo); 247 248 for (i = 0; i < nbbs; i++) 249 { 250 basic_block bb = bbs[i]; 251 252 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 253 { 254 stmt_info = vinfo_for_stmt (phi); 255 if (vect_print_dump_info (REPORT_DETAILS)) 256 { 257 fprintf (vect_dump, "examining phi: "); 258 print_generic_expr (vect_dump, phi, TDF_SLIM); 259 } 260 261 gcc_assert (stmt_info); 262 263 if (STMT_VINFO_LIVE_P (stmt_info)) 264 { 265 /* FORNOW: not yet supported. */ 266 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 267 fprintf (vect_dump, "not vectorized: value used after loop."); 268 return false; 269 } 270 271 if (STMT_VINFO_RELEVANT_P (stmt_info)) 272 { 273 /* Most likely a reduction-like computation that is used 274 in the loop. */ 275 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 276 fprintf (vect_dump, "not vectorized: unsupported pattern."); 277 return false; 278 } 279 } 280 281 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 282 { 283 tree stmt = bsi_stmt (si); 284 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 285 286 if (vect_print_dump_info (REPORT_DETAILS)) 287 { 288 fprintf (vect_dump, "==> examining statement: "); 289 print_generic_expr (vect_dump, stmt, TDF_SLIM); 290 } 291 292 gcc_assert (stmt_info); 293 294 /* skip stmts which do not need to be vectorized. 295 this is expected to include: 296 - the COND_EXPR which is the loop exit condition 297 - any LABEL_EXPRs in the loop 298 - computations that are used only for array indexing or loop 299 control */ 300 301 if (!STMT_VINFO_RELEVANT_P (stmt_info) 302 && !STMT_VINFO_LIVE_P (stmt_info)) 303 { 304 if (vect_print_dump_info (REPORT_DETAILS)) 305 fprintf (vect_dump, "irrelevant."); 306 continue; 307 } 308 309 if (STMT_VINFO_RELEVANT_P (stmt_info)) 310 { 311 gcc_assert (!VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt)))); 312 gcc_assert (STMT_VINFO_VECTYPE (stmt_info)); 313 314 ok = (vectorizable_operation (stmt, NULL, NULL) 315 || vectorizable_assignment (stmt, NULL, NULL) 316 || vectorizable_load (stmt, NULL, NULL) 317 || vectorizable_store (stmt, NULL, NULL) 318 || vectorizable_condition (stmt, NULL, NULL)); 319 320 if (!ok) 321 { 322 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 323 { 324 fprintf (vect_dump, 325 "not vectorized: relevant stmt not supported: "); 326 print_generic_expr (vect_dump, stmt, TDF_SLIM); 327 } 328 return false; 329 } 330 need_to_vectorize = true; 331 } 332 333 if (STMT_VINFO_LIVE_P (stmt_info)) 334 { 335 ok = vectorizable_reduction (stmt, NULL, NULL); 336 337 if (ok) 338 need_to_vectorize = true; 339 else 340 ok = vectorizable_live_operation (stmt, NULL, NULL); 341 342 if (!ok) 343 { 344 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 345 { 346 fprintf (vect_dump, 347 "not vectorized: live stmt not supported: "); 348 print_generic_expr (vect_dump, stmt, TDF_SLIM); 349 } 350 return false; 351 } 352 } 353 } /* stmts in bb */ 354 } /* bbs */ 355 356 /* TODO: Analyze cost. Decide if worth while to vectorize. */ 357 358 /* All operations in the loop are either irrelevant (deal with loop 359 control, or dead), or only used outside the loop and can be moved 360 out of the loop (e.g. invariants, inductions). The loop can be 361 optimized away by scalar optimizations. We're better off not 362 touching this loop. */ 363 if (!need_to_vectorize) 364 { 365 if (vect_print_dump_info (REPORT_DETAILS)) 366 fprintf (vect_dump, 367 "All the computation can be taken out of the loop."); 368 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 369 fprintf (vect_dump, 370 "not vectorized: redundant loop. no profit to vectorize."); 371 return false; 372 } 373 374 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) 375 && vect_print_dump_info (REPORT_DETAILS)) 376 fprintf (vect_dump, 377 "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC, 378 vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo)); 379 380 if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) 381 && LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor) 382 { 383 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 384 fprintf (vect_dump, "not vectorized: iteration count too small."); 385 return false; 386 } 387 388 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo) 389 || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0 390 || LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo)) 391 { 392 if (vect_print_dump_info (REPORT_DETAILS)) 393 fprintf (vect_dump, "epilog loop required."); 394 if (!vect_can_advance_ivs_p (loop_vinfo)) 395 { 396 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 397 fprintf (vect_dump, 398 "not vectorized: can't create epilog loop 1."); 399 return false; 400 } 401 if (!slpeel_can_duplicate_loop_p (loop, loop->single_exit)) 402 { 403 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 404 fprintf (vect_dump, 405 "not vectorized: can't create epilog loop 2."); 406 return false; 407 } 408 } 409 410 return true; 411} 412 413 414/* Function exist_non_indexing_operands_for_use_p 415 416 USE is one of the uses attached to STMT. Check if USE is 417 used in STMT for anything other than indexing an array. */ 418 419static bool 420exist_non_indexing_operands_for_use_p (tree use, tree stmt) 421{ 422 tree operand; 423 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 424 425 /* USE corresponds to some operand in STMT. If there is no data 426 reference in STMT, then any operand that corresponds to USE 427 is not indexing an array. */ 428 if (!STMT_VINFO_DATA_REF (stmt_info)) 429 return true; 430 431 /* STMT has a data_ref. FORNOW this means that its of one of 432 the following forms: 433 -1- ARRAY_REF = var 434 -2- var = ARRAY_REF 435 (This should have been verified in analyze_data_refs). 436 437 'var' in the second case corresponds to a def, not a use, 438 so USE cannot correspond to any operands that are not used 439 for array indexing. 440 441 Therefore, all we need to check is if STMT falls into the 442 first case, and whether var corresponds to USE. */ 443 444 if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME) 445 return false; 446 447 operand = TREE_OPERAND (stmt, 1); 448 449 if (TREE_CODE (operand) != SSA_NAME) 450 return false; 451 452 if (operand == use) 453 return true; 454 455 return false; 456} 457 458 459/* Function vect_analyze_scalar_cycles. 460 461 Examine the cross iteration def-use cycles of scalar variables, by 462 analyzing the loop (scalar) PHIs; Classify each cycle as one of the 463 following: invariant, induction, reduction, unknown. 464 465 Some forms of scalar cycles are not yet supported. 466 467 Example1: reduction: (unsupported yet) 468 469 loop1: 470 for (i=0; i<N; i++) 471 sum += a[i]; 472 473 Example2: induction: (unsupported yet) 474 475 loop2: 476 for (i=0; i<N; i++) 477 a[i] = i; 478 479 Note: the following loop *is* vectorizable: 480 481 loop3: 482 for (i=0; i<N; i++) 483 a[i] = b[i]; 484 485 even though it has a def-use cycle caused by the induction variable i: 486 487 loop: i_2 = PHI (i_0, i_1) 488 a[i_2] = ...; 489 i_1 = i_2 + 1; 490 GOTO loop; 491 492 because the def-use cycle in loop3 is considered "not relevant" - i.e., 493 it does not need to be vectorized because it is only used for array 494 indexing (see 'mark_stmts_to_be_vectorized'). The def-use cycle in 495 loop2 on the other hand is relevant (it is being written to memory). 496*/ 497 498static void 499vect_analyze_scalar_cycles (loop_vec_info loop_vinfo) 500{ 501 tree phi; 502 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 503 basic_block bb = loop->header; 504 tree dummy; 505 506 if (vect_print_dump_info (REPORT_DETAILS)) 507 fprintf (vect_dump, "=== vect_analyze_scalar_cycles ==="); 508 509 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 510 { 511 tree access_fn = NULL; 512 tree def = PHI_RESULT (phi); 513 stmt_vec_info stmt_vinfo = vinfo_for_stmt (phi); 514 tree reduc_stmt; 515 516 if (vect_print_dump_info (REPORT_DETAILS)) 517 { 518 fprintf (vect_dump, "Analyze phi: "); 519 print_generic_expr (vect_dump, phi, TDF_SLIM); 520 } 521 522 /* Skip virtual phi's. The data dependences that are associated with 523 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */ 524 525 if (!is_gimple_reg (SSA_NAME_VAR (def))) 526 { 527 if (vect_print_dump_info (REPORT_DETAILS)) 528 fprintf (vect_dump, "virtual phi. skip."); 529 continue; 530 } 531 532 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_unknown_def_type; 533 534 /* Analyze the evolution function. */ 535 536 access_fn = analyze_scalar_evolution (loop, def); 537 538 if (!access_fn) 539 continue; 540 541 if (vect_print_dump_info (REPORT_DETAILS)) 542 { 543 fprintf (vect_dump, "Access function of PHI: "); 544 print_generic_expr (vect_dump, access_fn, TDF_SLIM); 545 } 546 547 if (vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy)) 548 { 549 if (vect_print_dump_info (REPORT_DETAILS)) 550 fprintf (vect_dump, "Detected induction."); 551 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_induction_def; 552 continue; 553 } 554 555 /* TODO: handle invariant phis */ 556 557 reduc_stmt = vect_is_simple_reduction (loop, phi); 558 if (reduc_stmt) 559 { 560 if (vect_print_dump_info (REPORT_DETAILS)) 561 fprintf (vect_dump, "Detected reduction."); 562 STMT_VINFO_DEF_TYPE (stmt_vinfo) = vect_reduction_def; 563 STMT_VINFO_DEF_TYPE (vinfo_for_stmt (reduc_stmt)) = 564 vect_reduction_def; 565 } 566 else 567 if (vect_print_dump_info (REPORT_DETAILS)) 568 fprintf (vect_dump, "Unknown def-use cycle pattern."); 569 570 } 571 572 return; 573} 574 575 576/* Function vect_analyze_data_ref_dependence. 577 578 Return TRUE if there (might) exist a dependence between a memory-reference 579 DRA and a memory-reference DRB. */ 580 581static bool 582vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr, 583 loop_vec_info loop_vinfo) 584{ 585 unsigned int i; 586 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 587 int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo); 588 struct data_reference *dra = DDR_A (ddr); 589 struct data_reference *drb = DDR_B (ddr); 590 stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra)); 591 stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb)); 592 lambda_vector dist_v; 593 unsigned int loop_depth; 594 595 if (DDR_ARE_DEPENDENT (ddr) == chrec_known) 596 return false; 597 598 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know) 599 { 600 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 601 { 602 fprintf (vect_dump, 603 "not vectorized: can't determine dependence between "); 604 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM); 605 fprintf (vect_dump, " and "); 606 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM); 607 } 608 return true; 609 } 610 611 if (DDR_NUM_DIST_VECTS (ddr) == 0) 612 { 613 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 614 { 615 fprintf (vect_dump, "not vectorized: bad dist vector for "); 616 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM); 617 fprintf (vect_dump, " and "); 618 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM); 619 } 620 return true; 621 } 622 623 loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr)); 624 for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++) 625 { 626 int dist = dist_v[loop_depth]; 627 628 if (vect_print_dump_info (REPORT_DR_DETAILS)) 629 fprintf (vect_dump, "dependence distance = %d.", dist); 630 631 /* Same loop iteration. */ 632 if (dist % vectorization_factor == 0) 633 { 634 /* Two references with distance zero have the same alignment. */ 635 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a), drb); 636 VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b), dra); 637 if (vect_print_dump_info (REPORT_ALIGNMENT)) 638 fprintf (vect_dump, "accesses have the same alignment."); 639 if (vect_print_dump_info (REPORT_DR_DETAILS)) 640 { 641 fprintf (vect_dump, "dependence distance modulo vf == 0 between "); 642 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM); 643 fprintf (vect_dump, " and "); 644 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM); 645 } 646 continue; 647 } 648 649 if (abs (dist) >= vectorization_factor) 650 { 651 /* Dependence distance does not create dependence, as far as vectorization 652 is concerned, in this case. */ 653 if (vect_print_dump_info (REPORT_DR_DETAILS)) 654 fprintf (vect_dump, "dependence distance >= VF."); 655 continue; 656 } 657 658 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 659 { 660 fprintf (vect_dump, 661 "not vectorized: possible dependence between data-refs "); 662 print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM); 663 fprintf (vect_dump, " and "); 664 print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM); 665 } 666 667 return true; 668 } 669 670 return false; 671} 672 673 674/* Function vect_analyze_data_ref_dependences. 675 676 Examine all the data references in the loop, and make sure there do not 677 exist any data dependences between them. */ 678 679static bool 680vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo) 681{ 682 unsigned int i; 683 VEC (ddr_p, heap) *ddrs = LOOP_VINFO_DDRS (loop_vinfo); 684 struct data_dependence_relation *ddr; 685 686 if (vect_print_dump_info (REPORT_DETAILS)) 687 fprintf (vect_dump, "=== vect_analyze_dependences ==="); 688 689 for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++) 690 if (vect_analyze_data_ref_dependence (ddr, loop_vinfo)) 691 return false; 692 693 return true; 694} 695 696 697/* Function vect_compute_data_ref_alignment 698 699 Compute the misalignment of the data reference DR. 700 701 Output: 702 1. If during the misalignment computation it is found that the data reference 703 cannot be vectorized then false is returned. 704 2. DR_MISALIGNMENT (DR) is defined. 705 706 FOR NOW: No analysis is actually performed. Misalignment is calculated 707 only for trivial cases. TODO. */ 708 709static bool 710vect_compute_data_ref_alignment (struct data_reference *dr) 711{ 712 tree stmt = DR_STMT (dr); 713 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 714 tree ref = DR_REF (dr); 715 tree vectype; 716 tree base, base_addr; 717 bool base_aligned; 718 tree misalign; 719 tree aligned_to, alignment; 720 721 if (vect_print_dump_info (REPORT_DETAILS)) 722 fprintf (vect_dump, "vect_compute_data_ref_alignment:"); 723 724 /* Initialize misalignment to unknown. */ 725 DR_MISALIGNMENT (dr) = -1; 726 727 misalign = DR_OFFSET_MISALIGNMENT (dr); 728 aligned_to = DR_ALIGNED_TO (dr); 729 base_addr = DR_BASE_ADDRESS (dr); 730 base = build_fold_indirect_ref (base_addr); 731 vectype = STMT_VINFO_VECTYPE (stmt_info); 732 alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT); 733 734 if ((aligned_to && tree_int_cst_compare (aligned_to, alignment) < 0) 735 || !misalign) 736 { 737 if (vect_print_dump_info (REPORT_DETAILS)) 738 { 739 fprintf (vect_dump, "Unknown alignment for access: "); 740 print_generic_expr (vect_dump, base, TDF_SLIM); 741 } 742 return true; 743 } 744 745 if ((DECL_P (base) 746 && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)), 747 alignment) >= 0) 748 || (TREE_CODE (base_addr) == SSA_NAME 749 && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE ( 750 TREE_TYPE (base_addr)))), 751 alignment) >= 0)) 752 base_aligned = true; 753 else 754 base_aligned = false; 755 756 if (!base_aligned) 757 { 758 /* Do not change the alignment of global variables if 759 flag_section_anchors is enabled. */ 760 if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype)) 761 || (TREE_STATIC (base) && flag_section_anchors)) 762 { 763 if (vect_print_dump_info (REPORT_DETAILS)) 764 { 765 fprintf (vect_dump, "can't force alignment of ref: "); 766 print_generic_expr (vect_dump, ref, TDF_SLIM); 767 } 768 return true; 769 } 770 771 /* Force the alignment of the decl. 772 NOTE: This is the only change to the code we make during 773 the analysis phase, before deciding to vectorize the loop. */ 774 if (vect_print_dump_info (REPORT_DETAILS)) 775 fprintf (vect_dump, "force alignment"); 776 DECL_ALIGN (base) = TYPE_ALIGN (vectype); 777 DECL_USER_ALIGN (base) = 1; 778 } 779 780 /* At this point we assume that the base is aligned. */ 781 gcc_assert (base_aligned 782 || (TREE_CODE (base) == VAR_DECL 783 && DECL_ALIGN (base) >= TYPE_ALIGN (vectype))); 784 785 /* Modulo alignment. */ 786 misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment); 787 788 if (!host_integerp (misalign, 1)) 789 { 790 /* Negative or overflowed misalignment value. */ 791 if (vect_print_dump_info (REPORT_DETAILS)) 792 fprintf (vect_dump, "unexpected misalign value"); 793 return false; 794 } 795 796 DR_MISALIGNMENT (dr) = TREE_INT_CST_LOW (misalign); 797 798 if (vect_print_dump_info (REPORT_DETAILS)) 799 { 800 fprintf (vect_dump, "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr)); 801 print_generic_expr (vect_dump, ref, TDF_SLIM); 802 } 803 804 return true; 805} 806 807 808/* Function vect_compute_data_refs_alignment 809 810 Compute the misalignment of data references in the loop. 811 Return FALSE if a data reference is found that cannot be vectorized. */ 812 813static bool 814vect_compute_data_refs_alignment (loop_vec_info loop_vinfo) 815{ 816 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); 817 struct data_reference *dr; 818 unsigned int i; 819 820 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 821 if (!vect_compute_data_ref_alignment (dr)) 822 return false; 823 824 return true; 825} 826 827 828/* Function vect_update_misalignment_for_peel 829 830 DR - the data reference whose misalignment is to be adjusted. 831 DR_PEEL - the data reference whose misalignment is being made 832 zero in the vector loop by the peel. 833 NPEEL - the number of iterations in the peel loop if the misalignment 834 of DR_PEEL is known at compile time. */ 835 836static void 837vect_update_misalignment_for_peel (struct data_reference *dr, 838 struct data_reference *dr_peel, int npeel) 839{ 840 unsigned int i; 841 int drsize; 842 VEC(dr_p,heap) *same_align_drs; 843 struct data_reference *current_dr; 844 845 if (known_alignment_for_access_p (dr) 846 && DR_MISALIGNMENT (dr) == DR_MISALIGNMENT (dr_peel)) 847 { 848 DR_MISALIGNMENT (dr) = 0; 849 return; 850 } 851 852 /* It can be assumed that the data refs with the same alignment as dr_peel 853 are aligned in the vector loop. */ 854 same_align_drs 855 = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel))); 856 for (i = 0; VEC_iterate (dr_p, same_align_drs, i, current_dr); i++) 857 { 858 if (current_dr != dr) 859 continue; 860 gcc_assert (DR_MISALIGNMENT (dr) == DR_MISALIGNMENT (dr_peel)); 861 DR_MISALIGNMENT (dr) = 0; 862 return; 863 } 864 865 if (known_alignment_for_access_p (dr) 866 && known_alignment_for_access_p (dr_peel)) 867 { 868 drsize = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr)))); 869 DR_MISALIGNMENT (dr) += npeel * drsize; 870 DR_MISALIGNMENT (dr) %= UNITS_PER_SIMD_WORD; 871 return; 872 } 873 874 DR_MISALIGNMENT (dr) = -1; 875} 876 877 878/* Function vect_verify_datarefs_alignment 879 880 Return TRUE if all data references in the loop can be 881 handled with respect to alignment. */ 882 883static bool 884vect_verify_datarefs_alignment (loop_vec_info loop_vinfo) 885{ 886 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); 887 struct data_reference *dr; 888 enum dr_alignment_support supportable_dr_alignment; 889 unsigned int i; 890 891 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 892 { 893 supportable_dr_alignment = vect_supportable_dr_alignment (dr); 894 if (!supportable_dr_alignment) 895 { 896 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 897 { 898 if (DR_IS_READ (dr)) 899 fprintf (vect_dump, 900 "not vectorized: unsupported unaligned load."); 901 else 902 fprintf (vect_dump, 903 "not vectorized: unsupported unaligned store."); 904 } 905 return false; 906 } 907 if (supportable_dr_alignment != dr_aligned 908 && vect_print_dump_info (REPORT_ALIGNMENT)) 909 fprintf (vect_dump, "Vectorizing an unaligned access."); 910 } 911 return true; 912} 913 914 915/* Function vector_alignment_reachable_p 916 917 Return true if vector alignment for DR is reachable by peeling 918 a few loop iterations. Return false otherwise. */ 919 920static bool 921vector_alignment_reachable_p (struct data_reference *dr) 922{ 923 tree stmt = DR_STMT (dr); 924 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 925 tree vectype = STMT_VINFO_VECTYPE (stmt_info); 926 927 /* If misalignment is known at the compile time then allow peeling 928 only if natural alignment is reachable through peeling. */ 929 if (known_alignment_for_access_p (dr) && !aligned_access_p (dr)) 930 { 931 HOST_WIDE_INT elmsize = 932 int_cst_value (TYPE_SIZE_UNIT (TREE_TYPE (vectype))); 933 if (vect_print_dump_info (REPORT_DETAILS)) 934 { 935 fprintf (vect_dump, "data size =" HOST_WIDE_INT_PRINT_DEC, elmsize); 936 fprintf (vect_dump, ". misalignment = %d. ", DR_MISALIGNMENT (dr)); 937 } 938 if (DR_MISALIGNMENT (dr) % elmsize) 939 { 940 if (vect_print_dump_info (REPORT_DETAILS)) 941 fprintf (vect_dump, "data size does not divide the misalignment.\n"); 942 return false; 943 } 944 } 945 946 if (!known_alignment_for_access_p (dr)) 947 { 948 tree type = (TREE_TYPE (DR_REF (dr))); 949 tree ba = DR_BASE_OBJECT (dr); 950 bool is_packed = false; 951 952 if (ba) 953 is_packed = contains_packed_reference (ba); 954 955 if (vect_print_dump_info (REPORT_DETAILS)) 956 fprintf (vect_dump, "Unknown misalignment, is_packed = %d",is_packed); 957 if (targetm.vectorize.vector_alignment_reachable (type, is_packed)) 958 return true; 959 else 960 return false; 961 } 962 963 return true; 964} 965 966/* Function vect_enhance_data_refs_alignment 967 968 This pass will use loop versioning and loop peeling in order to enhance 969 the alignment of data references in the loop. 970 971 FOR NOW: we assume that whatever versioning/peeling takes place, only the 972 original loop is to be vectorized; Any other loops that are created by 973 the transformations performed in this pass - are not supposed to be 974 vectorized. This restriction will be relaxed. 975 976 This pass will require a cost model to guide it whether to apply peeling 977 or versioning or a combination of the two. For example, the scheme that 978 intel uses when given a loop with several memory accesses, is as follows: 979 choose one memory access ('p') which alignment you want to force by doing 980 peeling. Then, either (1) generate a loop in which 'p' is aligned and all 981 other accesses are not necessarily aligned, or (2) use loop versioning to 982 generate one loop in which all accesses are aligned, and another loop in 983 which only 'p' is necessarily aligned. 984 985 ("Automatic Intra-Register Vectorization for the Intel Architecture", 986 Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International 987 Journal of Parallel Programming, Vol. 30, No. 2, April 2002.) 988 989 Devising a cost model is the most critical aspect of this work. It will 990 guide us on which access to peel for, whether to use loop versioning, how 991 many versions to create, etc. The cost model will probably consist of 992 generic considerations as well as target specific considerations (on 993 powerpc for example, misaligned stores are more painful than misaligned 994 loads). 995 996 Here are the general steps involved in alignment enhancements: 997 998 -- original loop, before alignment analysis: 999 for (i=0; i<N; i++){ 1000 x = q[i]; # DR_MISALIGNMENT(q) = unknown 1001 p[i] = y; # DR_MISALIGNMENT(p) = unknown 1002 } 1003 1004 -- After vect_compute_data_refs_alignment: 1005 for (i=0; i<N; i++){ 1006 x = q[i]; # DR_MISALIGNMENT(q) = 3 1007 p[i] = y; # DR_MISALIGNMENT(p) = unknown 1008 } 1009 1010 -- Possibility 1: we do loop versioning: 1011 if (p is aligned) { 1012 for (i=0; i<N; i++){ # loop 1A 1013 x = q[i]; # DR_MISALIGNMENT(q) = 3 1014 p[i] = y; # DR_MISALIGNMENT(p) = 0 1015 } 1016 } 1017 else { 1018 for (i=0; i<N; i++){ # loop 1B 1019 x = q[i]; # DR_MISALIGNMENT(q) = 3 1020 p[i] = y; # DR_MISALIGNMENT(p) = unaligned 1021 } 1022 } 1023 1024 -- Possibility 2: we do loop peeling: 1025 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized). 1026 x = q[i]; 1027 p[i] = y; 1028 } 1029 for (i = 3; i < N; i++){ # loop 2A 1030 x = q[i]; # DR_MISALIGNMENT(q) = 0 1031 p[i] = y; # DR_MISALIGNMENT(p) = unknown 1032 } 1033 1034 -- Possibility 3: combination of loop peeling and versioning: 1035 for (i = 0; i < 3; i++){ # (scalar loop, not to be vectorized). 1036 x = q[i]; 1037 p[i] = y; 1038 } 1039 if (p is aligned) { 1040 for (i = 3; i<N; i++){ # loop 3A 1041 x = q[i]; # DR_MISALIGNMENT(q) = 0 1042 p[i] = y; # DR_MISALIGNMENT(p) = 0 1043 } 1044 } 1045 else { 1046 for (i = 3; i<N; i++){ # loop 3B 1047 x = q[i]; # DR_MISALIGNMENT(q) = 0 1048 p[i] = y; # DR_MISALIGNMENT(p) = unaligned 1049 } 1050 } 1051 1052 These loops are later passed to loop_transform to be vectorized. The 1053 vectorizer will use the alignment information to guide the transformation 1054 (whether to generate regular loads/stores, or with special handling for 1055 misalignment). */ 1056 1057static bool 1058vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo) 1059{ 1060 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); 1061 enum dr_alignment_support supportable_dr_alignment; 1062 struct data_reference *dr0 = NULL; 1063 struct data_reference *dr; 1064 unsigned int i; 1065 bool do_peeling = false; 1066 bool do_versioning = false; 1067 bool stat; 1068 1069 /* While cost model enhancements are expected in the future, the high level 1070 view of the code at this time is as follows: 1071 1072 A) If there is a misaligned write then see if peeling to align this write 1073 can make all data references satisfy vect_supportable_dr_alignment. 1074 If so, update data structures as needed and return true. Note that 1075 at this time vect_supportable_dr_alignment is known to return false 1076 for a a misaligned write. 1077 1078 B) If peeling wasn't possible and there is a data reference with an 1079 unknown misalignment that does not satisfy vect_supportable_dr_alignment 1080 then see if loop versioning checks can be used to make all data 1081 references satisfy vect_supportable_dr_alignment. If so, update 1082 data structures as needed and return true. 1083 1084 C) If neither peeling nor versioning were successful then return false if 1085 any data reference does not satisfy vect_supportable_dr_alignment. 1086 1087 D) Return true (all data references satisfy vect_supportable_dr_alignment). 1088 1089 Note, Possibility 3 above (which is peeling and versioning together) is not 1090 being done at this time. */ 1091 1092 /* (1) Peeling to force alignment. */ 1093 1094 /* (1.1) Decide whether to perform peeling, and how many iterations to peel: 1095 Considerations: 1096 + How many accesses will become aligned due to the peeling 1097 - How many accesses will become unaligned due to the peeling, 1098 and the cost of misaligned accesses. 1099 - The cost of peeling (the extra runtime checks, the increase 1100 in code size). 1101 1102 The scheme we use FORNOW: peel to force the alignment of the first 1103 misaligned store in the loop. 1104 Rationale: misaligned stores are not yet supported. 1105 1106 TODO: Use a cost model. */ 1107 1108 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 1109 if (!DR_IS_READ (dr) && !aligned_access_p (dr)) 1110 { 1111 do_peeling = vector_alignment_reachable_p (dr); 1112 if (do_peeling) 1113 dr0 = dr; 1114 if (!do_peeling && vect_print_dump_info (REPORT_DETAILS)) 1115 fprintf (vect_dump, "vector alignment may not be reachable"); 1116 break; 1117 } 1118 1119 /* Often peeling for alignment will require peeling for loop-bound, which in 1120 turn requires that we know how to adjust the loop ivs after the loop. */ 1121 if (!vect_can_advance_ivs_p (loop_vinfo)) 1122 do_peeling = false; 1123 1124 if (do_peeling) 1125 { 1126 int mis; 1127 int npeel = 0; 1128 1129 if (known_alignment_for_access_p (dr0)) 1130 { 1131 /* Since it's known at compile time, compute the number of iterations 1132 in the peeled loop (the peeling factor) for use in updating 1133 DR_MISALIGNMENT values. The peeling factor is the vectorization 1134 factor minus the misalignment as an element count. */ 1135 mis = DR_MISALIGNMENT (dr0); 1136 mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0)))); 1137 npeel = LOOP_VINFO_VECT_FACTOR (loop_vinfo) - mis; 1138 } 1139 1140 /* Ensure that all data refs can be vectorized after the peel. */ 1141 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 1142 { 1143 int save_misalignment; 1144 1145 if (dr == dr0) 1146 continue; 1147 1148 save_misalignment = DR_MISALIGNMENT (dr); 1149 vect_update_misalignment_for_peel (dr, dr0, npeel); 1150 supportable_dr_alignment = vect_supportable_dr_alignment (dr); 1151 DR_MISALIGNMENT (dr) = save_misalignment; 1152 1153 if (!supportable_dr_alignment) 1154 { 1155 do_peeling = false; 1156 break; 1157 } 1158 } 1159 1160 if (do_peeling) 1161 { 1162 /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i. 1163 If the misalignment of DR_i is identical to that of dr0 then set 1164 DR_MISALIGNMENT (DR_i) to zero. If the misalignment of DR_i and 1165 dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i) 1166 by the peeling factor times the element size of DR_i (MOD the 1167 vectorization factor times the size). Otherwise, the 1168 misalignment of DR_i must be set to unknown. */ 1169 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 1170 if (dr != dr0) 1171 vect_update_misalignment_for_peel (dr, dr0, npeel); 1172 1173 LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0; 1174 LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0); 1175 DR_MISALIGNMENT (dr0) = 0; 1176 if (vect_print_dump_info (REPORT_ALIGNMENT)) 1177 fprintf (vect_dump, "Alignment of access forced using peeling."); 1178 1179 if (vect_print_dump_info (REPORT_DETAILS)) 1180 fprintf (vect_dump, "Peeling for alignment will be applied."); 1181 1182 stat = vect_verify_datarefs_alignment (loop_vinfo); 1183 gcc_assert (stat); 1184 return stat; 1185 } 1186 } 1187 1188 1189 /* (2) Versioning to force alignment. */ 1190 1191 /* Try versioning if: 1192 1) flag_tree_vect_loop_version is TRUE 1193 2) optimize_size is FALSE 1194 3) there is at least one unsupported misaligned data ref with an unknown 1195 misalignment, and 1196 4) all misaligned data refs with a known misalignment are supported, and 1197 5) the number of runtime alignment checks is within reason. */ 1198 1199 do_versioning = flag_tree_vect_loop_version && (!optimize_size); 1200 1201 if (do_versioning) 1202 { 1203 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 1204 { 1205 if (aligned_access_p (dr)) 1206 continue; 1207 1208 supportable_dr_alignment = vect_supportable_dr_alignment (dr); 1209 1210 if (!supportable_dr_alignment) 1211 { 1212 tree stmt; 1213 int mask; 1214 tree vectype; 1215 1216 if (known_alignment_for_access_p (dr) 1217 || VEC_length (tree, 1218 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)) 1219 >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS)) 1220 { 1221 do_versioning = false; 1222 break; 1223 } 1224 1225 stmt = DR_STMT (dr); 1226 vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt)); 1227 gcc_assert (vectype); 1228 1229 /* The rightmost bits of an aligned address must be zeros. 1230 Construct the mask needed for this test. For example, 1231 GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the 1232 mask must be 15 = 0xf. */ 1233 mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1; 1234 1235 /* FORNOW: use the same mask to test all potentially unaligned 1236 references in the loop. The vectorizer currently supports 1237 a single vector size, see the reference to 1238 GET_MODE_NUNITS (TYPE_MODE (vectype)) where the 1239 vectorization factor is computed. */ 1240 gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo) 1241 || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask); 1242 LOOP_VINFO_PTR_MASK (loop_vinfo) = mask; 1243 VEC_safe_push (tree, heap, 1244 LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo), 1245 DR_STMT (dr)); 1246 } 1247 } 1248 1249 /* Versioning requires at least one misaligned data reference. */ 1250 if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)) == 0) 1251 do_versioning = false; 1252 else if (!do_versioning) 1253 VEC_truncate (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo), 0); 1254 } 1255 1256 if (do_versioning) 1257 { 1258 VEC(tree,heap) *may_misalign_stmts 1259 = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo); 1260 tree stmt; 1261 1262 /* It can now be assumed that the data references in the statements 1263 in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version 1264 of the loop being vectorized. */ 1265 for (i = 0; VEC_iterate (tree, may_misalign_stmts, i, stmt); i++) 1266 { 1267 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 1268 dr = STMT_VINFO_DATA_REF (stmt_info); 1269 DR_MISALIGNMENT (dr) = 0; 1270 if (vect_print_dump_info (REPORT_ALIGNMENT)) 1271 fprintf (vect_dump, "Alignment of access forced using versioning."); 1272 } 1273 1274 if (vect_print_dump_info (REPORT_DETAILS)) 1275 fprintf (vect_dump, "Versioning for alignment will be applied."); 1276 1277 /* Peeling and versioning can't be done together at this time. */ 1278 gcc_assert (! (do_peeling && do_versioning)); 1279 1280 stat = vect_verify_datarefs_alignment (loop_vinfo); 1281 gcc_assert (stat); 1282 return stat; 1283 } 1284 1285 /* This point is reached if neither peeling nor versioning is being done. */ 1286 gcc_assert (! (do_peeling || do_versioning)); 1287 1288 stat = vect_verify_datarefs_alignment (loop_vinfo); 1289 return stat; 1290} 1291 1292 1293/* Function vect_analyze_data_refs_alignment 1294 1295 Analyze the alignment of the data-references in the loop. 1296 Return FALSE if a data reference is found that cannot be vectorized. */ 1297 1298static bool 1299vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo) 1300{ 1301 if (vect_print_dump_info (REPORT_DETAILS)) 1302 fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ==="); 1303 1304 if (!vect_compute_data_refs_alignment (loop_vinfo)) 1305 { 1306 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1307 fprintf (vect_dump, 1308 "not vectorized: can't calculate alignment for data ref."); 1309 return false; 1310 } 1311 1312 return true; 1313} 1314 1315 1316/* Function vect_analyze_data_ref_access. 1317 1318 Analyze the access pattern of the data-reference DR. For now, a data access 1319 has to be consecutive to be considered vectorizable. */ 1320 1321static bool 1322vect_analyze_data_ref_access (struct data_reference *dr) 1323{ 1324 tree step = DR_STEP (dr); 1325 tree scalar_type = TREE_TYPE (DR_REF (dr)); 1326 1327 if (!step || tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type))) 1328 { 1329 if (vect_print_dump_info (REPORT_DETAILS)) 1330 fprintf (vect_dump, "not consecutive access"); 1331 return false; 1332 } 1333 return true; 1334} 1335 1336 1337/* Function vect_analyze_data_ref_accesses. 1338 1339 Analyze the access pattern of all the data references in the loop. 1340 1341 FORNOW: the only access pattern that is considered vectorizable is a 1342 simple step 1 (consecutive) access. 1343 1344 FORNOW: handle only arrays and pointer accesses. */ 1345 1346static bool 1347vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo) 1348{ 1349 unsigned int i; 1350 VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); 1351 struct data_reference *dr; 1352 1353 if (vect_print_dump_info (REPORT_DETAILS)) 1354 fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ==="); 1355 1356 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 1357 if (!vect_analyze_data_ref_access (dr)) 1358 { 1359 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1360 fprintf (vect_dump, "not vectorized: complicated access pattern."); 1361 return false; 1362 } 1363 1364 return true; 1365} 1366 1367 1368/* Function vect_analyze_data_refs. 1369 1370 Find all the data references in the loop. 1371 1372 The general structure of the analysis of data refs in the vectorizer is as 1373 follows: 1374 1- vect_analyze_data_refs(loop): call compute_data_dependences_for_loop to 1375 find and analyze all data-refs in the loop and their dependences. 1376 2- vect_analyze_dependences(): apply dependence testing using ddrs. 1377 3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok. 1378 4- vect_analyze_drs_access(): check that ref_stmt.step is ok. 1379 1380*/ 1381 1382static bool 1383vect_analyze_data_refs (loop_vec_info loop_vinfo) 1384{ 1385 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1386 unsigned int i; 1387 VEC (data_reference_p, heap) *datarefs; 1388 struct data_reference *dr; 1389 tree scalar_type; 1390 1391 if (vect_print_dump_info (REPORT_DETAILS)) 1392 fprintf (vect_dump, "=== vect_analyze_data_refs ==="); 1393 1394 compute_data_dependences_for_loop (loop, false, 1395 &LOOP_VINFO_DATAREFS (loop_vinfo), 1396 &LOOP_VINFO_DDRS (loop_vinfo)); 1397 1398 /* Go through the data-refs, check that the analysis succeeded. Update pointer 1399 from stmt_vec_info struct to DR and vectype. */ 1400 datarefs = LOOP_VINFO_DATAREFS (loop_vinfo); 1401 1402 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++) 1403 { 1404 tree stmt; 1405 stmt_vec_info stmt_info; 1406 1407 if (!dr || !DR_REF (dr)) 1408 { 1409 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1410 fprintf (vect_dump, "not vectorized: unhandled data-ref "); 1411 return false; 1412 } 1413 1414 /* Update DR field in stmt_vec_info struct. */ 1415 stmt = DR_STMT (dr); 1416 stmt_info = vinfo_for_stmt (stmt); 1417 1418 if (STMT_VINFO_DATA_REF (stmt_info)) 1419 { 1420 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1421 { 1422 fprintf (vect_dump, 1423 "not vectorized: more than one data ref in stmt: "); 1424 print_generic_expr (vect_dump, stmt, TDF_SLIM); 1425 } 1426 return false; 1427 } 1428 STMT_VINFO_DATA_REF (stmt_info) = dr; 1429 1430 /* Check that analysis of the data-ref succeeded. */ 1431 if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr) 1432 || !DR_STEP (dr)) 1433 { 1434 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1435 { 1436 fprintf (vect_dump, "not vectorized: data ref analysis failed "); 1437 print_generic_expr (vect_dump, stmt, TDF_SLIM); 1438 } 1439 return false; 1440 } 1441 if (!DR_MEMTAG (dr)) 1442 { 1443 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1444 { 1445 fprintf (vect_dump, "not vectorized: no memory tag for "); 1446 print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM); 1447 } 1448 return false; 1449 } 1450 1451 /* Set vectype for STMT. */ 1452 scalar_type = TREE_TYPE (DR_REF (dr)); 1453 STMT_VINFO_VECTYPE (stmt_info) = 1454 get_vectype_for_scalar_type (scalar_type); 1455 if (!STMT_VINFO_VECTYPE (stmt_info)) 1456 { 1457 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1458 { 1459 fprintf (vect_dump, 1460 "not vectorized: no vectype for stmt: "); 1461 print_generic_expr (vect_dump, stmt, TDF_SLIM); 1462 fprintf (vect_dump, " scalar_type: "); 1463 print_generic_expr (vect_dump, scalar_type, TDF_DETAILS); 1464 } 1465 return false; 1466 } 1467 } 1468 1469 return true; 1470} 1471 1472 1473/* Utility functions used by vect_mark_stmts_to_be_vectorized. */ 1474 1475/* Function vect_mark_relevant. 1476 1477 Mark STMT as "relevant for vectorization" and add it to WORKLIST. */ 1478 1479static void 1480vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt, 1481 bool relevant_p, bool live_p) 1482{ 1483 stmt_vec_info stmt_info = vinfo_for_stmt (stmt); 1484 bool save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info); 1485 bool save_live_p = STMT_VINFO_LIVE_P (stmt_info); 1486 1487 if (vect_print_dump_info (REPORT_DETAILS)) 1488 fprintf (vect_dump, "mark relevant %d, live %d.",relevant_p, live_p); 1489 1490 if (STMT_VINFO_IN_PATTERN_P (stmt_info)) 1491 { 1492 tree pattern_stmt; 1493 1494 /* This is the last stmt in a sequence that was detected as a 1495 pattern that can potentially be vectorized. Don't mark the stmt 1496 as relevant/live because it's not going to vectorized. 1497 Instead mark the pattern-stmt that replaces it. */ 1498 if (vect_print_dump_info (REPORT_DETAILS)) 1499 fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live."); 1500 pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info); 1501 stmt_info = vinfo_for_stmt (pattern_stmt); 1502 gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt); 1503 save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info); 1504 save_live_p = STMT_VINFO_LIVE_P (stmt_info); 1505 stmt = pattern_stmt; 1506 } 1507 1508 STMT_VINFO_LIVE_P (stmt_info) |= live_p; 1509 STMT_VINFO_RELEVANT_P (stmt_info) |= relevant_p; 1510 1511 if (TREE_CODE (stmt) == PHI_NODE) 1512 /* Don't put phi-nodes in the worklist. Phis that are marked relevant 1513 or live will fail vectorization later on. */ 1514 return; 1515 1516 if (STMT_VINFO_RELEVANT_P (stmt_info) == save_relevant_p 1517 && STMT_VINFO_LIVE_P (stmt_info) == save_live_p) 1518 { 1519 if (vect_print_dump_info (REPORT_DETAILS)) 1520 fprintf (vect_dump, "already marked relevant/live."); 1521 return; 1522 } 1523 1524 VEC_safe_push (tree, heap, *worklist, stmt); 1525} 1526 1527 1528/* Function vect_stmt_relevant_p. 1529 1530 Return true if STMT in loop that is represented by LOOP_VINFO is 1531 "relevant for vectorization". 1532 1533 A stmt is considered "relevant for vectorization" if: 1534 - it has uses outside the loop. 1535 - it has vdefs (it alters memory). 1536 - control stmts in the loop (except for the exit condition). 1537 1538 CHECKME: what other side effects would the vectorizer allow? */ 1539 1540static bool 1541vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo, 1542 bool *relevant_p, bool *live_p) 1543{ 1544 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1545 ssa_op_iter op_iter; 1546 imm_use_iterator imm_iter; 1547 use_operand_p use_p; 1548 def_operand_p def_p; 1549 1550 *relevant_p = false; 1551 *live_p = false; 1552 1553 /* cond stmt other than loop exit cond. */ 1554 if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo))) 1555 *relevant_p = true; 1556 1557 /* changing memory. */ 1558 if (TREE_CODE (stmt) != PHI_NODE) 1559 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 1560 { 1561 if (vect_print_dump_info (REPORT_DETAILS)) 1562 fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs."); 1563 *relevant_p = true; 1564 } 1565 1566 /* uses outside the loop. */ 1567 FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF) 1568 { 1569 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p)) 1570 { 1571 basic_block bb = bb_for_stmt (USE_STMT (use_p)); 1572 if (!flow_bb_inside_loop_p (loop, bb)) 1573 { 1574 if (vect_print_dump_info (REPORT_DETAILS)) 1575 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop."); 1576 1577 /* We expect all such uses to be in the loop exit phis 1578 (because of loop closed form) */ 1579 gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE); 1580 gcc_assert (bb == loop->single_exit->dest); 1581 1582 *live_p = true; 1583 } 1584 } 1585 } 1586 1587 return (*live_p || *relevant_p); 1588} 1589 1590 1591/* Function vect_mark_stmts_to_be_vectorized. 1592 1593 Not all stmts in the loop need to be vectorized. For example: 1594 1595 for i... 1596 for j... 1597 1. T0 = i + j 1598 2. T1 = a[T0] 1599 1600 3. j = j + 1 1601 1602 Stmt 1 and 3 do not need to be vectorized, because loop control and 1603 addressing of vectorized data-refs are handled differently. 1604 1605 This pass detects such stmts. */ 1606 1607static bool 1608vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo) 1609{ 1610 VEC(tree,heap) *worklist; 1611 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1612 basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo); 1613 unsigned int nbbs = loop->num_nodes; 1614 block_stmt_iterator si; 1615 tree stmt, use; 1616 stmt_ann_t ann; 1617 ssa_op_iter iter; 1618 unsigned int i; 1619 stmt_vec_info stmt_vinfo; 1620 basic_block bb; 1621 tree phi; 1622 bool relevant_p, live_p; 1623 tree def, def_stmt; 1624 enum vect_def_type dt; 1625 1626 if (vect_print_dump_info (REPORT_DETAILS)) 1627 fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ==="); 1628 1629 worklist = VEC_alloc (tree, heap, 64); 1630 1631 /* 1. Init worklist. */ 1632 1633 bb = loop->header; 1634 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1635 { 1636 if (vect_print_dump_info (REPORT_DETAILS)) 1637 { 1638 fprintf (vect_dump, "init: phi relevant? "); 1639 print_generic_expr (vect_dump, phi, TDF_SLIM); 1640 } 1641 1642 if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant_p, &live_p)) 1643 vect_mark_relevant (&worklist, phi, relevant_p, live_p); 1644 } 1645 1646 for (i = 0; i < nbbs; i++) 1647 { 1648 bb = bbs[i]; 1649 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si)) 1650 { 1651 stmt = bsi_stmt (si); 1652 1653 if (vect_print_dump_info (REPORT_DETAILS)) 1654 { 1655 fprintf (vect_dump, "init: stmt relevant? "); 1656 print_generic_expr (vect_dump, stmt, TDF_SLIM); 1657 } 1658 1659 if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant_p, &live_p)) 1660 vect_mark_relevant (&worklist, stmt, relevant_p, live_p); 1661 } 1662 } 1663 1664 1665 /* 2. Process_worklist */ 1666 1667 while (VEC_length (tree, worklist) > 0) 1668 { 1669 stmt = VEC_pop (tree, worklist); 1670 1671 if (vect_print_dump_info (REPORT_DETAILS)) 1672 { 1673 fprintf (vect_dump, "worklist: examine stmt: "); 1674 print_generic_expr (vect_dump, stmt, TDF_SLIM); 1675 } 1676 1677 /* Examine the USEs of STMT. For each ssa-name USE thta is defined 1678 in the loop, mark the stmt that defines it (DEF_STMT) as 1679 relevant/irrelevant and live/dead according to the liveness and 1680 relevance properties of STMT. 1681 */ 1682 1683 gcc_assert (TREE_CODE (stmt) != PHI_NODE); 1684 1685 ann = stmt_ann (stmt); 1686 stmt_vinfo = vinfo_for_stmt (stmt); 1687 1688 relevant_p = STMT_VINFO_RELEVANT_P (stmt_vinfo); 1689 live_p = STMT_VINFO_LIVE_P (stmt_vinfo); 1690 1691 /* Generally, the liveness and relevance properties of STMT are 1692 propagated to the DEF_STMTs of its USEs: 1693 STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p 1694 STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- relevant_p 1695 1696 Exceptions: 1697 1698 (case 1) 1699 If USE is used only for address computations (e.g. array indexing), 1700 which does not need to be directly vectorized, then the 1701 liveness/relevance of the respective DEF_STMT is left unchanged. 1702 1703 (case 2) 1704 If STMT has been identified as defining a reduction variable, then 1705 we have two cases: 1706 (case 2.1) 1707 The last use of STMT is the reduction-variable, which is defined 1708 by a loop-header-phi. We don't want to mark the phi as live or 1709 relevant (because it does not need to be vectorized, it is handled 1710 as part of the vectorization of the reduction), so in this case we 1711 skip the call to vect_mark_relevant. 1712 (case 2.2) 1713 The rest of the uses of STMT are defined in the loop body. For 1714 the def_stmt of these uses we want to set liveness/relevance 1715 as follows: 1716 STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false 1717 STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- true 1718 because even though STMT is classified as live (since it defines a 1719 value that is used across loop iterations) and irrelevant (since it 1720 is not used inside the loop), it will be vectorized, and therefore 1721 the corresponding DEF_STMTs need to marked as relevant. 1722 */ 1723 1724 /* case 2.2: */ 1725 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def) 1726 { 1727 gcc_assert (!relevant_p && live_p); 1728 relevant_p = true; 1729 live_p = false; 1730 } 1731 1732 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 1733 { 1734 /* case 1: we are only interested in uses that need to be vectorized. 1735 Uses that are used for address computation are not considered 1736 relevant. 1737 */ 1738 if (!exist_non_indexing_operands_for_use_p (use, stmt)) 1739 continue; 1740 1741 if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt)) 1742 { 1743 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 1744 fprintf (vect_dump, "not vectorized: unsupported use in stmt."); 1745 VEC_free (tree, heap, worklist); 1746 return false; 1747 } 1748 1749 if (!def_stmt || IS_EMPTY_STMT (def_stmt)) 1750 continue; 1751 1752 if (vect_print_dump_info (REPORT_DETAILS)) 1753 { 1754 fprintf (vect_dump, "worklist: examine use %d: ", i); 1755 print_generic_expr (vect_dump, use, TDF_SLIM); 1756 } 1757 1758 bb = bb_for_stmt (def_stmt); 1759 if (!flow_bb_inside_loop_p (loop, bb)) 1760 continue; 1761 1762 /* case 2.1: the reduction-use does not mark the defining-phi 1763 as relevant. */ 1764 if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def 1765 && TREE_CODE (def_stmt) == PHI_NODE) 1766 continue; 1767 1768 vect_mark_relevant (&worklist, def_stmt, relevant_p, live_p); 1769 } 1770 } /* while worklist */ 1771 1772 VEC_free (tree, heap, worklist); 1773 return true; 1774} 1775 1776 1777/* Function vect_can_advance_ivs_p 1778 1779 In case the number of iterations that LOOP iterates is unknown at compile 1780 time, an epilog loop will be generated, and the loop induction variables 1781 (IVs) will be "advanced" to the value they are supposed to take just before 1782 the epilog loop. Here we check that the access function of the loop IVs 1783 and the expression that represents the loop bound are simple enough. 1784 These restrictions will be relaxed in the future. */ 1785 1786static bool 1787vect_can_advance_ivs_p (loop_vec_info loop_vinfo) 1788{ 1789 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); 1790 basic_block bb = loop->header; 1791 tree phi; 1792 1793 /* Analyze phi functions of the loop header. */ 1794 1795 if (vect_print_dump_info (REPORT_DETAILS)) 1796 fprintf (vect_dump, "=== vect_can_advance_ivs_p ==="); 1797 1798 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1799 { 1800 tree access_fn = NULL; 1801 tree evolution_part; 1802 1803 if (vect_print_dump_info (REPORT_DETAILS)) 1804 { 1805 fprintf (vect_dump, "Analyze phi: "); 1806 print_generic_expr (vect_dump, phi, TDF_SLIM); 1807 } 1808 1809 /* Skip virtual phi's. The data dependences that are associated with 1810 virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. */ 1811 1812 if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) 1813 { 1814 if (vect_print_dump_info (REPORT_DETAILS)) 1815 fprintf (vect_dump, "virtual phi. skip."); 1816 continue; 1817 } 1818 1819 /* Skip reduction phis. */ 1820 1821 if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def) 1822 { 1823 if (vect_print_dump_info (REPORT_DETAILS)) 1824 fprintf (vect_dump, "reduc phi. skip."); 1825 continue; 1826 } 1827 1828 /* Analyze the evolution function. */ 1829 1830 access_fn = instantiate_parameters 1831 (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi))); 1832 1833 if (!access_fn) 1834 { 1835 if (vect_print_dump_info (REPORT_DETAILS)) 1836 fprintf (vect_dump, "No Access function."); 1837 return false; 1838 } 1839 1840 if (vect_print_dump_info (REPORT_DETAILS)) 1841 { 1842 fprintf (vect_dump, "Access function of PHI: "); 1843 print_generic_expr (vect_dump, access_fn, TDF_SLIM); 1844 } 1845 1846 evolution_part = evolution_part_in_loop_num (access_fn, loop->num); 1847 1848 if (evolution_part == NULL_TREE) 1849 { 1850 if (vect_print_dump_info (REPORT_DETAILS)) 1851 fprintf (vect_dump, "No evolution."); 1852 return false; 1853 } 1854 1855 /* FORNOW: We do not transform initial conditions of IVs 1856 which evolution functions are a polynomial of degree >= 2. */ 1857 1858 if (tree_is_chrec (evolution_part)) 1859 return false; 1860 } 1861 1862 return true; 1863} 1864 1865 1866/* Function vect_get_loop_niters. 1867 1868 Determine how many iterations the loop is executed. 1869 If an expression that represents the number of iterations 1870 can be constructed, place it in NUMBER_OF_ITERATIONS. 1871 Return the loop exit condition. */ 1872 1873static tree 1874vect_get_loop_niters (struct loop *loop, tree *number_of_iterations) 1875{ 1876 tree niters; 1877 1878 if (vect_print_dump_info (REPORT_DETAILS)) 1879 fprintf (vect_dump, "=== get_loop_niters ==="); 1880 1881 niters = number_of_iterations_in_loop (loop); 1882 1883 if (niters != NULL_TREE 1884 && niters != chrec_dont_know) 1885 { 1886 *number_of_iterations = niters; 1887 1888 if (vect_print_dump_info (REPORT_DETAILS)) 1889 { 1890 fprintf (vect_dump, "==> get_loop_niters:" ); 1891 print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM); 1892 } 1893 } 1894 1895 return get_loop_exit_condition (loop); 1896} 1897 1898 1899/* Function vect_analyze_loop_form. 1900 1901 Verify the following restrictions (some may be relaxed in the future): 1902 - it's an inner-most loop 1903 - number of BBs = 2 (which are the loop header and the latch) 1904 - the loop has a pre-header 1905 - the loop has a single entry and exit 1906 - the loop exit condition is simple enough, and the number of iterations 1907 can be analyzed (a countable loop). */ 1908 1909static loop_vec_info 1910vect_analyze_loop_form (struct loop *loop) 1911{ 1912 loop_vec_info loop_vinfo; 1913 tree loop_cond; 1914 tree number_of_iterations = NULL; 1915 1916 if (vect_print_dump_info (REPORT_DETAILS)) 1917 fprintf (vect_dump, "=== vect_analyze_loop_form ==="); 1918 1919 if (loop->inner) 1920 { 1921 if (vect_print_dump_info (REPORT_OUTER_LOOPS)) 1922 fprintf (vect_dump, "not vectorized: nested loop."); 1923 return NULL; 1924 } 1925 1926 if (!loop->single_exit 1927 || loop->num_nodes != 2 1928 || EDGE_COUNT (loop->header->preds) != 2) 1929 { 1930 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS)) 1931 { 1932 if (!loop->single_exit) 1933 fprintf (vect_dump, "not vectorized: multiple exits."); 1934 else if (loop->num_nodes != 2) 1935 fprintf (vect_dump, "not vectorized: too many BBs in loop."); 1936 else if (EDGE_COUNT (loop->header->preds) != 2) 1937 fprintf (vect_dump, "not vectorized: too many incoming edges."); 1938 } 1939 1940 return NULL; 1941 } 1942 1943 /* We assume that the loop exit condition is at the end of the loop. i.e, 1944 that the loop is represented as a do-while (with a proper if-guard 1945 before the loop if needed), where the loop header contains all the 1946 executable statements, and the latch is empty. */ 1947 if (!empty_block_p (loop->latch) 1948 || phi_nodes (loop->latch)) 1949 { 1950 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS)) 1951 fprintf (vect_dump, "not vectorized: unexpected loop form."); 1952 return NULL; 1953 } 1954 1955 /* Make sure there exists a single-predecessor exit bb: */ 1956 if (!single_pred_p (loop->single_exit->dest)) 1957 { 1958 edge e = loop->single_exit; 1959 if (!(e->flags & EDGE_ABNORMAL)) 1960 { 1961 split_loop_exit_edge (e); 1962 if (vect_print_dump_info (REPORT_DETAILS)) 1963 fprintf (vect_dump, "split exit edge."); 1964 } 1965 else 1966 { 1967 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS)) 1968 fprintf (vect_dump, "not vectorized: abnormal loop exit edge."); 1969 return NULL; 1970 } 1971 } 1972 1973 if (empty_block_p (loop->header)) 1974 { 1975 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS)) 1976 fprintf (vect_dump, "not vectorized: empty loop."); 1977 return NULL; 1978 } 1979 1980 loop_cond = vect_get_loop_niters (loop, &number_of_iterations); 1981 if (!loop_cond) 1982 { 1983 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS)) 1984 fprintf (vect_dump, "not vectorized: complicated exit condition."); 1985 return NULL; 1986 } 1987 1988 if (!number_of_iterations) 1989 { 1990 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS)) 1991 fprintf (vect_dump, 1992 "not vectorized: number of iterations cannot be computed."); 1993 return NULL; 1994 } 1995 1996 if (chrec_contains_undetermined (number_of_iterations)) 1997 { 1998 if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS)) 1999 fprintf (vect_dump, "Infinite number of iterations."); 2000 return false; 2001 } 2002 2003 loop_vinfo = new_loop_vec_info (loop); 2004 LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations; 2005 2006 if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)) 2007 { 2008 if (vect_print_dump_info (REPORT_DETAILS)) 2009 { 2010 fprintf (vect_dump, "Symbolic number of iterations is "); 2011 print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS); 2012 } 2013 } 2014 else 2015 if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0) 2016 { 2017 if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)) 2018 fprintf (vect_dump, "not vectorized: number of iterations = 0."); 2019 return NULL; 2020 } 2021 2022 LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond; 2023 2024 return loop_vinfo; 2025} 2026 2027 2028/* Function vect_analyze_loop. 2029 2030 Apply a set of analyses on LOOP, and create a loop_vec_info struct 2031 for it. The different analyses will record information in the 2032 loop_vec_info struct. */ 2033loop_vec_info 2034vect_analyze_loop (struct loop *loop) 2035{ 2036 bool ok; 2037 loop_vec_info loop_vinfo; 2038 2039 if (vect_print_dump_info (REPORT_DETAILS)) 2040 fprintf (vect_dump, "===== analyze_loop_nest ====="); 2041 2042 /* Check the CFG characteristics of the loop (nesting, entry/exit, etc. */ 2043 2044 loop_vinfo = vect_analyze_loop_form (loop); 2045 if (!loop_vinfo) 2046 { 2047 if (vect_print_dump_info (REPORT_DETAILS)) 2048 fprintf (vect_dump, "bad loop form."); 2049 return NULL; 2050 } 2051 2052 /* Find all data references in the loop (which correspond to vdefs/vuses) 2053 and analyze their evolution in the loop. 2054 2055 FORNOW: Handle only simple, array references, which 2056 alignment can be forced, and aligned pointer-references. */ 2057 2058 ok = vect_analyze_data_refs (loop_vinfo); 2059 if (!ok) 2060 { 2061 if (vect_print_dump_info (REPORT_DETAILS)) 2062 fprintf (vect_dump, "bad data references."); 2063 destroy_loop_vec_info (loop_vinfo); 2064 return NULL; 2065 } 2066 2067 /* Classify all cross-iteration scalar data-flow cycles. 2068 Cross-iteration cycles caused by virtual phis are analyzed separately. */ 2069 2070 vect_analyze_scalar_cycles (loop_vinfo); 2071 2072 vect_pattern_recog (loop_vinfo); 2073 2074 /* Data-flow analysis to detect stmts that do not need to be vectorized. */ 2075 2076 ok = vect_mark_stmts_to_be_vectorized (loop_vinfo); 2077 if (!ok) 2078 { 2079 if (vect_print_dump_info (REPORT_DETAILS)) 2080 fprintf (vect_dump, "unexpected pattern."); 2081 destroy_loop_vec_info (loop_vinfo); 2082 return NULL; 2083 } 2084 2085 /* Analyze the alignment of the data-refs in the loop. 2086 Fail if a data reference is found that cannot be vectorized. */ 2087 2088 ok = vect_analyze_data_refs_alignment (loop_vinfo); 2089 if (!ok) 2090 { 2091 if (vect_print_dump_info (REPORT_DETAILS)) 2092 fprintf (vect_dump, "bad data alignment."); 2093 destroy_loop_vec_info (loop_vinfo); 2094 return NULL; 2095 } 2096 2097 ok = vect_determine_vectorization_factor (loop_vinfo); 2098 if (!ok) 2099 { 2100 if (vect_print_dump_info (REPORT_DETAILS)) 2101 fprintf (vect_dump, "can't determine vectorization factor."); 2102 destroy_loop_vec_info (loop_vinfo); 2103 return NULL; 2104 } 2105 2106 /* Analyze data dependences between the data-refs in the loop. 2107 FORNOW: fail at the first data dependence that we encounter. */ 2108 2109 ok = vect_analyze_data_ref_dependences (loop_vinfo); 2110 if (!ok) 2111 { 2112 if (vect_print_dump_info (REPORT_DETAILS)) 2113 fprintf (vect_dump, "bad data dependence."); 2114 destroy_loop_vec_info (loop_vinfo); 2115 return NULL; 2116 } 2117 2118 /* Analyze the access patterns of the data-refs in the loop (consecutive, 2119 complex, etc.). FORNOW: Only handle consecutive access pattern. */ 2120 2121 ok = vect_analyze_data_ref_accesses (loop_vinfo); 2122 if (!ok) 2123 { 2124 if (vect_print_dump_info (REPORT_DETAILS)) 2125 fprintf (vect_dump, "bad data access."); 2126 destroy_loop_vec_info (loop_vinfo); 2127 return NULL; 2128 } 2129 2130 /* This pass will decide on using loop versioning and/or loop peeling in 2131 order to enhance the alignment of data references in the loop. */ 2132 2133 ok = vect_enhance_data_refs_alignment (loop_vinfo); 2134 if (!ok) 2135 { 2136 if (vect_print_dump_info (REPORT_DETAILS)) 2137 fprintf (vect_dump, "bad data alignment."); 2138 destroy_loop_vec_info (loop_vinfo); 2139 return NULL; 2140 } 2141 2142 /* Scan all the operations in the loop and make sure they are 2143 vectorizable. */ 2144 2145 ok = vect_analyze_operations (loop_vinfo); 2146 if (!ok) 2147 { 2148 if (vect_print_dump_info (REPORT_DETAILS)) 2149 fprintf (vect_dump, "bad operation or unsupported loop bound."); 2150 destroy_loop_vec_info (loop_vinfo); 2151 return NULL; 2152 } 2153 2154 LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1; 2155 2156 return loop_vinfo; 2157} 2158