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