gcc/tree-vect-analyze.c

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