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   struct data_reference *dra = DDR_A (ddr);
 588   struct data_reference *drb = DDR_B (ddr);
 589   stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
 590   stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
 591   lambda_vector dist_v;
 592   unsigned int loop_depth;
 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   loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
 623   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
 624     {
 625       int dist = dist_v[loop_depth];
 626
 627       if (vect_print_dump_info (REPORT_DR_DETAILS))
 628         fprintf (vect_dump, "dependence distance  = %d.", dist);
 629
 630       /* Same loop iteration.  */
 631       if (dist % vectorization_factor == 0)
 632         {
 633           /* Two references with distance zero have the same alignment.  */
 634           VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_a), drb);
 635           VEC_safe_push (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmtinfo_b), dra);
 636           if (vect_print_dump_info (REPORT_ALIGNMENT))
 637             fprintf (vect_dump, "accesses have the same alignment.");
 638           if (vect_print_dump_info (REPORT_DR_DETAILS))
 639             {
 640               fprintf (vect_dump, "dependence distance modulo vf == 0 between ");
 641               print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
 642               fprintf (vect_dump, " and ");
 643               print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
 644             }
 645           continue;
 646         }
 647
 648       if (abs (dist) >= vectorization_factor)
 649         {
 650           /* Dependence distance does not create dependence, as far as vectorization
 651              is concerned, in this case.  */
 652           if (vect_print_dump_info (REPORT_DR_DETAILS))
 653             fprintf (vect_dump, "dependence distance >= VF.");
 654           continue;
 655         }
 656
 657       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
 658         {
 659           fprintf (vect_dump,
 660                    "not vectorized: possible dependence between data-refs ");
 661           print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
 662           fprintf (vect_dump, " and ");
 663           print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
 664         }
 665
 666       return true;
 667     }
 668
 669   return false;
 670 }
 671
 672
 673 /* Function vect_analyze_data_ref_dependences.
 674
 675    Examine all the data references in the loop, and make sure there do not
 676    exist any data dependences between them.  */
 677
 678 static bool
 679 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
 680 {
 681   unsigned int i;
 682   varray_type ddrs = LOOP_VINFO_DDRS (loop_vinfo);
 683
 684   if (vect_print_dump_info (REPORT_DETAILS))
 685     fprintf (vect_dump, "=== vect_analyze_dependences ===");
 686
 687   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
 688     {
 689       struct data_dependence_relation *ddr = VARRAY_GENERIC_PTR (ddrs, i);
 690
 691       if (vect_analyze_data_ref_dependence (ddr, loop_vinfo))
 692         return false;
 693     }
 694
 695   return true;
 696 }
 697
 698
 699 /* Function vect_compute_data_ref_alignment
 700
 701    Compute the misalignment of the data reference DR.
 702
 703    Output:
 704    1. If during the misalignment computation it is found that the data reference
 705       cannot be vectorized then false is returned.
 706    2. DR_MISALIGNMENT (DR) is defined.
 707
 708    FOR NOW: No analysis is actually performed. Misalignment is calculated
 709    only for trivial cases. TODO.  */
 710
 711 static bool
 712 vect_compute_data_ref_alignment (struct data_reference *dr)
 713 {
 714   tree stmt = DR_STMT (dr);
 715   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 716   tree ref = DR_REF (dr);
 717   tree vectype;
 718   tree base, base_addr;
 719   bool base_aligned;
 720   tree misalign;
 721   tree aligned_to, alignment;
 722
 723   if (vect_print_dump_info (REPORT_DETAILS))
 724     fprintf (vect_dump, "vect_compute_data_ref_alignment:");
 725
 726   /* Initialize misalignment to unknown.  */
 727   DR_MISALIGNMENT (dr) = -1;
 728
 729   misalign = DR_OFFSET_MISALIGNMENT (dr);
 730   aligned_to = DR_ALIGNED_TO (dr);
 731   base_addr = DR_BASE_ADDRESS (dr);
 732   base = build_fold_indirect_ref (base_addr);
 733   vectype = STMT_VINFO_VECTYPE (stmt_info);
 734   alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
 735
 736   if ((aligned_to && tree_int_cst_compare (aligned_to, alignment) < 0)
 737       || !misalign)
 738     {
 739       if (vect_print_dump_info (REPORT_DETAILS))
 740         {
 741           fprintf (vect_dump, "Unknown alignment for access: ");
 742           print_generic_expr (vect_dump, base, TDF_SLIM);
 743         }
 744       return true;
 745     }
 746
 747   if ((DECL_P (base)
 748        && tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
 749                                 alignment) >= 0)
 750       || (TREE_CODE (base_addr) == SSA_NAME
 751           && tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
 752                                                       TREE_TYPE (base_addr)))),
 753                                    alignment) >= 0))
 754     base_aligned = true;
 755   else
 756     base_aligned = false;
 757
 758   if (!base_aligned)
 759     {
 760       if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype)))
 761         {
 762           if (vect_print_dump_info (REPORT_DETAILS))
 763             {
 764               fprintf (vect_dump, "can't force alignment of ref: ");
 765               print_generic_expr (vect_dump, ref, TDF_SLIM);
 766             }
 767           return true;
 768         }
 769
 770       /* Force the alignment of the decl.
 771          NOTE: This is the only change to the code we make during
 772          the analysis phase, before deciding to vectorize the loop.  */
 773       if (vect_print_dump_info (REPORT_DETAILS))
 774         fprintf (vect_dump, "force alignment");
 775       DECL_ALIGN (base) = TYPE_ALIGN (vectype);
 776       DECL_USER_ALIGN (base) = 1;
 777     }
 778
 779   /* At this point we assume that the base is aligned.  */
 780   gcc_assert (base_aligned
 781               || (TREE_CODE (base) == VAR_DECL
 782                   && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
 783
 784   /* Modulo alignment.  */
 785   misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
 786
 787   if (!host_integerp (misalign, 1))
 788     {
 789       /* Negative or overflowed misalignment value.  */
 790       if (vect_print_dump_info (REPORT_DETAILS))
 791         fprintf (vect_dump, "unexpected misalign value");
 792       return false;
 793     }
 794
 795   DR_MISALIGNMENT (dr) = TREE_INT_CST_LOW (misalign);
 796
 797   if (vect_print_dump_info (REPORT_DETAILS))
 798     {
 799       fprintf (vect_dump, "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
 800       print_generic_expr (vect_dump, ref, TDF_SLIM);
 801     }
 802
 803   return true;
 804 }
 805
 806
 807 /* Function vect_compute_data_refs_alignment
 808
 809    Compute the misalignment of data references in the loop.
 810    Return FALSE if a data reference is found that cannot be vectorized.  */
 811
 812 static bool
 813 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
 814 {
 815   varray_type datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
 816   unsigned int i;
 817
 818   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
 819     {
 820       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
 821       if (!vect_compute_data_ref_alignment (dr))
 822         return false;
 823     }
 824
 825   return true;
 826 }
 827
 828
 829 /* Function vect_update_misalignment_for_peel
 830
 831    DR - the data reference whose misalignment is to be adjusted.
 832    DR_PEEL - the data reference whose misalignment is being made
 833              zero in the vector loop by the peel.
 834    NPEEL - the number of iterations in the peel loop if the misalignment
 835            of DR_PEEL is known at compile time.  */
 836
 837 static void
 838 vect_update_misalignment_for_peel (struct data_reference *dr,
 839                                    struct data_reference *dr_peel, int npeel)
 840 {
 841   unsigned int i;
 842   int drsize;
 843   VEC(dr_p,heap) *same_align_drs;
 844   struct data_reference *current_dr;
 845
 846   if (known_alignment_for_access_p (dr)
 847       && DR_MISALIGNMENT (dr) == DR_MISALIGNMENT (dr_peel))
 848     {
 849       DR_MISALIGNMENT (dr) = 0;
 850       return;
 851     }
 852
 853   /* It can be assumed that the data refs with the same alignment as dr_peel
 854      are aligned in the vector loop.  */
 855   same_align_drs
 856     = STMT_VINFO_SAME_ALIGN_REFS (vinfo_for_stmt (DR_STMT (dr_peel)));
 857   for (i = 0; VEC_iterate (dr_p, same_align_drs, i, current_dr); i++)
 858     {
 859       if (current_dr != dr)
 860         continue;
 861       gcc_assert (DR_MISALIGNMENT (dr) == DR_MISALIGNMENT (dr_peel));
 862       DR_MISALIGNMENT (dr) = 0;
 863       return;
 864     }
 865
 866   if (known_alignment_for_access_p (dr)
 867       && known_alignment_for_access_p (dr_peel))
 868     {
 869       drsize = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
 870       DR_MISALIGNMENT (dr) += npeel * drsize;
 871       DR_MISALIGNMENT (dr) %= UNITS_PER_SIMD_WORD;
 872       return;
 873     }
 874
 875   DR_MISALIGNMENT (dr) = -1;
 876 }
 877
 878
 879 /* Function vect_verify_datarefs_alignment
 880
 881    Return TRUE if all data references in the loop can be
 882    handled with respect to alignment.  */
 883
 884 static bool
 885 vect_verify_datarefs_alignment (loop_vec_info loop_vinfo)
 886 {
 887   varray_type datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
 888   enum dr_alignment_support supportable_dr_alignment;
 889   unsigned int i;
 890
 891   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
 892     {
 893       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
 894       supportable_dr_alignment = vect_supportable_dr_alignment (dr);
 895       if (!supportable_dr_alignment)
 896         {
 897           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
 898             {
 899               if (DR_IS_READ (dr))
 900                 fprintf (vect_dump,
 901                          "not vectorized: unsupported unaligned load.");
 902               else
 903                 fprintf (vect_dump,
 904                          "not vectorized: unsupported unaligned store.");
 905             }
 906           return false;
 907         }
 908       if (supportable_dr_alignment != dr_aligned
 909           && vect_print_dump_info (REPORT_ALIGNMENT))
 910         fprintf (vect_dump, "Vectorizing an unaligned access.");
 911     }
 912   return true;
 913 }
 914
 915
 916 /* Function vect_enhance_data_refs_alignment
 917
 918    This pass will use loop versioning and loop peeling in order to enhance
 919    the alignment of data references in the loop.
 920
 921    FOR NOW: we assume that whatever versioning/peeling takes place, only the
 922    original loop is to be vectorized; Any other loops that are created by
 923    the transformations performed in this pass - are not supposed to be
 924    vectorized. This restriction will be relaxed.
 925
 926    This pass will require a cost model to guide it whether to apply peeling
 927    or versioning or a combination of the two. For example, the scheme that
 928    intel uses when given a loop with several memory accesses, is as follows:
 929    choose one memory access ('p') which alignment you want to force by doing
 930    peeling. Then, either (1) generate a loop in which 'p' is aligned and all
 931    other accesses are not necessarily aligned, or (2) use loop versioning to
 932    generate one loop in which all accesses are aligned, and another loop in
 933    which only 'p' is necessarily aligned.
 934
 935    ("Automatic Intra-Register Vectorization for the Intel Architecture",
 936    Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
 937    Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
 938
 939    Devising a cost model is the most critical aspect of this work. It will
 940    guide us on which access to peel for, whether to use loop versioning, how
 941    many versions to create, etc. The cost model will probably consist of
 942    generic considerations as well as target specific considerations (on
 943    powerpc for example, misaligned stores are more painful than misaligned
 944    loads).
 945
 946    Here are the general steps involved in alignment enhancements:
 947
 948      -- original loop, before alignment analysis:
 949         for (i=0; i<N; i++){
 950           x = q[i];                     # DR_MISALIGNMENT(q) = unknown
 951           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
 952         }
 953
 954      -- After vect_compute_data_refs_alignment:
 955         for (i=0; i<N; i++){
 956           x = q[i];                     # DR_MISALIGNMENT(q) = 3
 957           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
 958         }
 959
 960      -- Possibility 1: we do loop versioning:
 961      if (p is aligned) {
 962         for (i=0; i<N; i++){    # loop 1A
 963           x = q[i];                     # DR_MISALIGNMENT(q) = 3
 964           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
 965         }
 966      }
 967      else {
 968         for (i=0; i<N; i++){    # loop 1B
 969           x = q[i];                     # DR_MISALIGNMENT(q) = 3
 970           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
 971         }
 972      }
 973
 974      -- Possibility 2: we do loop peeling:
 975      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
 976         x = q[i];
 977         p[i] = y;
 978      }
 979      for (i = 3; i < N; i++){   # loop 2A
 980         x = q[i];                       # DR_MISALIGNMENT(q) = 0
 981         p[i] = y;                       # DR_MISALIGNMENT(p) = unknown
 982      }
 983
 984      -- Possibility 3: combination of loop peeling and versioning:
 985      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
 986         x = q[i];
 987         p[i] = y;
 988      }
 989      if (p is aligned) {
 990         for (i = 3; i<N; i++){  # loop 3A
 991           x = q[i];                     # DR_MISALIGNMENT(q) = 0
 992           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
 993         }
 994      }
 995      else {
 996         for (i = 3; i<N; i++){  # loop 3B
 997           x = q[i];                     # DR_MISALIGNMENT(q) = 0
 998           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
 999         }
1000      }
1001
1002      These loops are later passed to loop_transform to be vectorized. The
1003      vectorizer will use the alignment information to guide the transformation
1004      (whether to generate regular loads/stores, or with special handling for
1005      misalignment).  */
1006
1007 static bool
1008 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
1009 {
1010   varray_type datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1011   enum dr_alignment_support supportable_dr_alignment;
1012   struct data_reference *dr0 = NULL;
1013   struct data_reference *dr;
1014   unsigned int i;
1015   bool do_peeling = false;
1016   bool do_versioning = false;
1017   bool stat;
1018
1019   /* While cost model enhancements are expected in the future, the high level
1020      view of the code at this time is as follows:
1021
1022      A) If there is a misaligned write then see if peeling to align this write
1023         can make all data references satisfy vect_supportable_dr_alignment.
1024         If so, update data structures as needed and return true.  Note that
1025         at this time vect_supportable_dr_alignment is known to return false
1026         for a a misaligned write.
1027
1028      B) If peeling wasn't possible and there is a data reference with an
1029         unknown misalignment that does not satisfy vect_supportable_dr_alignment
1030         then see if loop versioning checks can be used to make all data
1031         references satisfy vect_supportable_dr_alignment.  If so, update
1032         data structures as needed and return true.
1033
1034      C) If neither peeling nor versioning were successful then return false if
1035         any data reference does not satisfy vect_supportable_dr_alignment.
1036
1037      D) Return true (all data references satisfy vect_supportable_dr_alignment).
1038
1039      Note, Possibility 3 above (which is peeling and versioning together) is not
1040      being done at this time.  */
1041
1042   /* (1) Peeling to force alignment.  */
1043
1044   /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
1045      Considerations:
1046      + How many accesses will become aligned due to the peeling
1047      - How many accesses will become unaligned due to the peeling,
1048        and the cost of misaligned accesses.
1049      - The cost of peeling (the extra runtime checks, the increase
1050        in code size).
1051
1052      The scheme we use FORNOW: peel to force the alignment of the first
1053      misaligned store in the loop.
1054      Rationale: misaligned stores are not yet supported.
1055
1056      TODO: Use a cost model.  */
1057
1058   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1059     {
1060       dr = VARRAY_GENERIC_PTR (datarefs, i);
1061       if (!DR_IS_READ (dr) && !aligned_access_p (dr))
1062         {
1063           dr0 = dr;
1064           do_peeling = true;
1065           break;
1066         }
1067     }
1068
1069   /* Often peeling for alignment will require peeling for loop-bound, which in
1070      turn requires that we know how to adjust the loop ivs after the loop.  */
1071   if (!vect_can_advance_ivs_p (loop_vinfo))
1072     do_peeling = false;
1073
1074   if (do_peeling)
1075     {
1076       int mis;
1077       int npeel = 0;
1078
1079       if (known_alignment_for_access_p (dr0))
1080         {
1081           /* Since it's known at compile time, compute the number of iterations
1082              in the peeled loop (the peeling factor) for use in updating
1083              DR_MISALIGNMENT values.  The peeling factor is the vectorization
1084              factor minus the misalignment as an element count.  */
1085           mis = DR_MISALIGNMENT (dr0);
1086           mis /= GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr0))));
1087           npeel = LOOP_VINFO_VECT_FACTOR (loop_vinfo) - mis;
1088         }
1089
1090       /* Ensure that all data refs can be vectorized after the peel.  */
1091       for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1092         {
1093           int save_misalignment;
1094
1095           dr = VARRAY_GENERIC_PTR (datarefs, i);
1096           if (dr == dr0)
1097             continue;
1098           save_misalignment = DR_MISALIGNMENT (dr);
1099           vect_update_misalignment_for_peel (dr, dr0, npeel);
1100           supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1101           DR_MISALIGNMENT (dr) = save_misalignment;
1102
1103           if (!supportable_dr_alignment)
1104             {
1105               do_peeling = false;
1106               break;
1107             }
1108         }
1109
1110       if (do_peeling)
1111         {
1112           /* (1.2) Update the DR_MISALIGNMENT of each data reference DR_i.
1113              If the misalignment of DR_i is identical to that of dr0 then set
1114              DR_MISALIGNMENT (DR_i) to zero.  If the misalignment of DR_i and
1115              dr0 are known at compile time then increment DR_MISALIGNMENT (DR_i)
1116              by the peeling factor times the element size of DR_i (MOD the
1117              vectorization factor times the size).  Otherwise, the
1118              misalignment of DR_i must be set to unknown.  */
1119           for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1120             {
1121               dr = VARRAY_GENERIC_PTR (datarefs, i);
1122               if (dr == dr0)
1123                 continue;
1124               vect_update_misalignment_for_peel (dr, dr0, npeel);
1125             }
1126
1127           LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr0;
1128           LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) = DR_MISALIGNMENT (dr0);
1129           DR_MISALIGNMENT (dr0) = 0;
1130           if (vect_print_dump_info (REPORT_ALIGNMENT))
1131             fprintf (vect_dump, "Alignment of access forced using peeling.");
1132
1133           if (vect_print_dump_info (REPORT_DETAILS))
1134             fprintf (vect_dump, "Peeling for alignment will be applied.");
1135
1136           stat = vect_verify_datarefs_alignment (loop_vinfo);
1137           gcc_assert (stat);
1138           return stat;
1139         }
1140     }
1141
1142
1143   /* (2) Versioning to force alignment.  */
1144
1145   /* Try versioning if:
1146      1) flag_tree_vect_loop_version is TRUE
1147      2) optimize_size is FALSE
1148      3) there is at least one unsupported misaligned data ref with an unknown
1149         misalignment, and
1150      4) all misaligned data refs with a known misalignment are supported, and
1151      5) the number of runtime alignment checks is within reason.  */
1152
1153   do_versioning = flag_tree_vect_loop_version && (!optimize_size);
1154
1155   if (do_versioning)
1156     {
1157       for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1158         {
1159           dr = VARRAY_GENERIC_PTR (datarefs, i);
1160
1161           if (aligned_access_p (dr))
1162             continue;
1163
1164           supportable_dr_alignment = vect_supportable_dr_alignment (dr);
1165
1166           if (!supportable_dr_alignment)
1167             {
1168               tree stmt;
1169               int mask;
1170               tree vectype;
1171
1172               if (known_alignment_for_access_p (dr)
1173                   || VEC_length (tree,
1174                                  LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo))
1175                      >= (unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS))
1176                 {
1177                   do_versioning = false;
1178                   break;
1179                 }
1180
1181               stmt = DR_STMT (dr);
1182               vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (stmt));
1183               gcc_assert (vectype);
1184
1185               /* The rightmost bits of an aligned address must be zeros.
1186                  Construct the mask needed for this test.  For example,
1187                  GET_MODE_SIZE for the vector mode V4SI is 16 bytes so the
1188                  mask must be 15 = 0xf. */
1189               mask = GET_MODE_SIZE (TYPE_MODE (vectype)) - 1;
1190
1191               /* FORNOW: use the same mask to test all potentially unaligned
1192                  references in the loop.  The vectorizer currently supports
1193                  a single vector size, see the reference to
1194                  GET_MODE_NUNITS (TYPE_MODE (vectype)) where the
1195                  vectorization factor is computed.  */
1196               gcc_assert (!LOOP_VINFO_PTR_MASK (loop_vinfo)
1197                           || LOOP_VINFO_PTR_MASK (loop_vinfo) == mask);
1198               LOOP_VINFO_PTR_MASK (loop_vinfo) = mask;
1199               VEC_safe_push (tree, heap,
1200                              LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo),
1201                              DR_STMT (dr));
1202             }
1203         }
1204
1205       /* Versioning requires at least one misaligned data reference.  */
1206       if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)) == 0)
1207         do_versioning = false;
1208       else if (!do_versioning)
1209         VEC_truncate (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo), 0);
1210     }
1211
1212   if (do_versioning)
1213     {
1214       VEC(tree,heap) *may_misalign_stmts
1215         = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
1216       tree stmt;
1217
1218       /* It can now be assumed that the data references in the statements
1219          in LOOP_VINFO_MAY_MISALIGN_STMTS will be aligned in the version
1220          of the loop being vectorized.  */
1221       for (i = 0; VEC_iterate (tree, may_misalign_stmts, i, stmt); i++)
1222         {
1223           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1224           dr = STMT_VINFO_DATA_REF (stmt_info);
1225           DR_MISALIGNMENT (dr) = 0;
1226           if (vect_print_dump_info (REPORT_ALIGNMENT))
1227             fprintf (vect_dump, "Alignment of access forced using versioning.");
1228         }
1229
1230       if (vect_print_dump_info (REPORT_DETAILS))
1231         fprintf (vect_dump, "Versioning for alignment will be applied.");
1232
1233       /* Peeling and versioning can't be done together at this time.  */
1234       gcc_assert (! (do_peeling && do_versioning));
1235
1236       stat = vect_verify_datarefs_alignment (loop_vinfo);
1237       gcc_assert (stat);
1238       return stat;
1239     }
1240
1241   /* This point is reached if neither peeling nor versioning is being done.  */
1242   gcc_assert (! (do_peeling || do_versioning));
1243
1244   stat = vect_verify_datarefs_alignment (loop_vinfo);
1245   return stat;
1246 }
1247
1248
1249 /* Function vect_analyze_data_refs_alignment
1250
1251    Analyze the alignment of the data-references in the loop.
1252    Return FALSE if a data reference is found that cannot be vectorized.  */
1253
1254 static bool
1255 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
1256 {
1257   if (vect_print_dump_info (REPORT_DETAILS))
1258     fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
1259
1260   if (!vect_compute_data_refs_alignment (loop_vinfo))
1261     {
1262       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1263         fprintf (vect_dump,
1264                  "not vectorized: can't calculate alignment for data ref.");
1265       return false;
1266     }
1267
1268   return true;
1269 }
1270
1271
1272 /* Function vect_analyze_data_ref_access.
1273
1274    Analyze the access pattern of the data-reference DR. For now, a data access
1275    has to be consecutive to be considered vectorizable.  */
1276
1277 static bool
1278 vect_analyze_data_ref_access (struct data_reference *dr)
1279 {
1280   tree step = DR_STEP (dr);
1281   tree scalar_type = TREE_TYPE (DR_REF (dr));
1282
1283   if (!step || tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
1284     {
1285       if (vect_print_dump_info (REPORT_DETAILS))
1286         fprintf (vect_dump, "not consecutive access");
1287       return false;
1288     }
1289   return true;
1290 }
1291
1292
1293 /* Function vect_analyze_data_ref_accesses.
1294
1295    Analyze the access pattern of all the data references in the loop.
1296
1297    FORNOW: the only access pattern that is considered vectorizable is a
1298            simple step 1 (consecutive) access.
1299
1300    FORNOW: handle only arrays and pointer accesses.  */
1301
1302 static bool
1303 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
1304 {
1305   unsigned int i;
1306   varray_type datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1307
1308   if (vect_print_dump_info (REPORT_DETAILS))
1309     fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
1310
1311   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1312     {
1313       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
1314       if (!vect_analyze_data_ref_access (dr))
1315         {
1316           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1317             fprintf (vect_dump, "not vectorized: complicated access pattern.");
1318           return false;
1319         }
1320     }
1321
1322   return true;
1323 }
1324
1325
1326 /* Function vect_analyze_data_refs.
1327
1328   Find all the data references in the loop.
1329
1330    The general structure of the analysis of data refs in the vectorizer is as
1331    follows:
1332    1- vect_analyze_data_refs(loop): call compute_data_dependences_for_loop to
1333       find and analyze all data-refs in the loop and their dependences.
1334    2- vect_analyze_dependences(): apply dependence testing using ddrs.
1335    3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
1336    4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
1337
1338 */
1339
1340 static bool
1341 vect_analyze_data_refs (loop_vec_info loop_vinfo)
1342 {
1343   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1344   unsigned int i;
1345   varray_type datarefs;
1346   tree scalar_type;
1347
1348   if (vect_print_dump_info (REPORT_DETAILS))
1349     fprintf (vect_dump, "=== vect_analyze_data_refs ===");
1350
1351   compute_data_dependences_for_loop (loop, false,
1352                                      &(LOOP_VINFO_DATAREFS (loop_vinfo)),
1353                                      &(LOOP_VINFO_DDRS (loop_vinfo)));
1354
1355   /* Go through the data-refs, check that the analysis succeeded. Update pointer
1356      from stmt_vec_info struct to DR and vectype.  */
1357   datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
1358   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1359     {
1360       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
1361       tree stmt;
1362       stmt_vec_info stmt_info;
1363
1364       if (!dr || !DR_REF (dr))
1365         {
1366           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1367             fprintf (vect_dump, "not vectorized: unhandled data-ref ");
1368           return false;
1369         }
1370
1371       /* Update DR field in stmt_vec_info struct.  */
1372       stmt = DR_STMT (dr);
1373       stmt_info = vinfo_for_stmt (stmt);
1374
1375       if (STMT_VINFO_DATA_REF (stmt_info))
1376         {
1377           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1378             {
1379               fprintf (vect_dump,
1380                        "not vectorized: more than one data ref in stmt: ");
1381               print_generic_expr (vect_dump, stmt, TDF_SLIM);
1382             }
1383           return false;
1384         }
1385       STMT_VINFO_DATA_REF (stmt_info) = dr;
1386
1387       /* Check that analysis of the data-ref succeeded.  */
1388       if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr) || !DR_INIT (dr)
1389           || !DR_STEP (dr))
1390         {
1391           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1392             {
1393               fprintf (vect_dump, "not vectorized: data ref analysis failed ");
1394               print_generic_expr (vect_dump, stmt, TDF_SLIM);
1395             }
1396           return false;
1397         }
1398       if (!DR_MEMTAG (dr))
1399         {
1400           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1401             {
1402               fprintf (vect_dump, "not vectorized: no memory tag for ");
1403               print_generic_expr (vect_dump, DR_REF (dr), TDF_SLIM);
1404             }
1405           return false;
1406         }
1407
1408       /* Set vectype for STMT.  */
1409       scalar_type = TREE_TYPE (DR_REF (dr));
1410       STMT_VINFO_VECTYPE (stmt_info) =
1411                 get_vectype_for_scalar_type (scalar_type);
1412       if (!STMT_VINFO_VECTYPE (stmt_info))
1413         {
1414           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1415             {
1416               fprintf (vect_dump,
1417                        "not vectorized: no vectype for stmt: ");
1418               print_generic_expr (vect_dump, stmt, TDF_SLIM);
1419               fprintf (vect_dump, " scalar_type: ");
1420               print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
1421             }
1422           return false;
1423         }
1424     }
1425
1426   return true;
1427 }
1428
1429
1430 /* Utility functions used by vect_mark_stmts_to_be_vectorized.  */
1431
1432 /* Function vect_mark_relevant.
1433
1434    Mark STMT as "relevant for vectorization" and add it to WORKLIST.  */
1435
1436 static void
1437 vect_mark_relevant (VEC(tree,heap) **worklist, tree stmt,
1438                     bool relevant_p, bool live_p)
1439 {
1440   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1441   bool save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info);
1442   bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
1443
1444   if (vect_print_dump_info (REPORT_DETAILS))
1445     fprintf (vect_dump, "mark relevant %d, live %d.",relevant_p, live_p);
1446
1447   if (STMT_VINFO_IN_PATTERN_P (stmt_info))
1448     {
1449       tree pattern_stmt;
1450
1451       /* This is the last stmt in a sequence that was detected as a
1452          pattern that can potentially be vectorized.  Don't mark the stmt
1453          as relevant/live because it's not going to vectorized.
1454          Instead mark the pattern-stmt that replaces it.  */
1455       if (vect_print_dump_info (REPORT_DETAILS))
1456         fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
1457       pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1458       stmt_info = vinfo_for_stmt (pattern_stmt);
1459       gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
1460       save_relevant_p = STMT_VINFO_RELEVANT_P (stmt_info);
1461       save_live_p = STMT_VINFO_LIVE_P (stmt_info);
1462       stmt = pattern_stmt;
1463     }
1464
1465   STMT_VINFO_LIVE_P (stmt_info) |= live_p;
1466   STMT_VINFO_RELEVANT_P (stmt_info) |= relevant_p;
1467
1468   if (TREE_CODE (stmt) == PHI_NODE)
1469     /* Don't put phi-nodes in the worklist. Phis that are marked relevant
1470        or live will fail vectorization later on.  */
1471     return;
1472
1473   if (STMT_VINFO_RELEVANT_P (stmt_info) == save_relevant_p
1474       && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
1475     {
1476       if (vect_print_dump_info (REPORT_DETAILS))
1477         fprintf (vect_dump, "already marked relevant/live.");
1478       return;
1479     }
1480
1481   VEC_safe_push (tree, heap, *worklist, stmt);
1482 }
1483
1484
1485 /* Function vect_stmt_relevant_p.
1486
1487    Return true if STMT in loop that is represented by LOOP_VINFO is
1488    "relevant for vectorization".
1489
1490    A stmt is considered "relevant for vectorization" if:
1491    - it has uses outside the loop.
1492    - it has vdefs (it alters memory).
1493    - control stmts in the loop (except for the exit condition).
1494
1495    CHECKME: what other side effects would the vectorizer allow?  */
1496
1497 static bool
1498 vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo,
1499                       bool *relevant_p, bool *live_p)
1500 {
1501   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1502   ssa_op_iter op_iter;
1503   imm_use_iterator imm_iter;
1504   use_operand_p use_p;
1505   def_operand_p def_p;
1506
1507   *relevant_p = false;
1508   *live_p = false;
1509
1510   /* cond stmt other than loop exit cond.  */
1511   if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
1512     *relevant_p = true;
1513
1514   /* changing memory.  */
1515   if (TREE_CODE (stmt) != PHI_NODE)
1516     if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
1517       {
1518         if (vect_print_dump_info (REPORT_DETAILS))
1519           fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
1520         *relevant_p = true;
1521       }
1522
1523   /* uses outside the loop.  */
1524   FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
1525     {
1526       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
1527         {
1528           basic_block bb = bb_for_stmt (USE_STMT (use_p));
1529           if (!flow_bb_inside_loop_p (loop, bb))
1530             {
1531               if (vect_print_dump_info (REPORT_DETAILS))
1532                 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
1533
1534               /* We expect all such uses to be in the loop exit phis
1535                  (because of loop closed form)   */
1536               gcc_assert (TREE_CODE (USE_STMT (use_p)) == PHI_NODE);
1537               gcc_assert (bb == loop->single_exit->dest);
1538
1539               *live_p = true;
1540             }
1541         }
1542     }
1543
1544   return (*live_p || *relevant_p);
1545 }
1546
1547
1548 /* Function vect_mark_stmts_to_be_vectorized.
1549
1550    Not all stmts in the loop need to be vectorized. For example:
1551
1552      for i...
1553        for j...
1554    1.    T0 = i + j
1555    2.    T1 = a[T0]
1556
1557    3.    j = j + 1
1558
1559    Stmt 1 and 3 do not need to be vectorized, because loop control and
1560    addressing of vectorized data-refs are handled differently.
1561
1562    This pass detects such stmts.  */
1563
1564 static bool
1565 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
1566 {
1567   VEC(tree,heap) *worklist;
1568   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1569   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1570   unsigned int nbbs = loop->num_nodes;
1571   block_stmt_iterator si;
1572   tree stmt, use;
1573   stmt_ann_t ann;
1574   ssa_op_iter iter;
1575   unsigned int i;
1576   stmt_vec_info stmt_vinfo;
1577   basic_block bb;
1578   tree phi;
1579   bool relevant_p, live_p;
1580   tree def, def_stmt;
1581   enum vect_def_type dt;
1582
1583   if (vect_print_dump_info (REPORT_DETAILS))
1584     fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
1585
1586   worklist = VEC_alloc (tree, heap, 64);
1587
1588   /* 1. Init worklist.  */
1589
1590   bb = loop->header;
1591   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1592     {
1593       if (vect_print_dump_info (REPORT_DETAILS))
1594         {
1595           fprintf (vect_dump, "init: phi relevant? ");
1596           print_generic_expr (vect_dump, phi, TDF_SLIM);
1597         }
1598
1599       if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant_p, &live_p))
1600         vect_mark_relevant (&worklist, phi, relevant_p, live_p);
1601     }
1602
1603   for (i = 0; i < nbbs; i++)
1604     {
1605       bb = bbs[i];
1606       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1607         {
1608           stmt = bsi_stmt (si);
1609
1610           if (vect_print_dump_info (REPORT_DETAILS))
1611             {
1612               fprintf (vect_dump, "init: stmt relevant? ");
1613               print_generic_expr (vect_dump, stmt, TDF_SLIM);
1614             }
1615
1616           if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant_p, &live_p))
1617             vect_mark_relevant (&worklist, stmt, relevant_p, live_p);
1618         }
1619     }
1620
1621
1622   /* 2. Process_worklist */
1623
1624   while (VEC_length (tree, worklist) > 0)
1625     {
1626       stmt = VEC_pop (tree, worklist);
1627
1628       if (vect_print_dump_info (REPORT_DETAILS))
1629         {
1630           fprintf (vect_dump, "worklist: examine stmt: ");
1631           print_generic_expr (vect_dump, stmt, TDF_SLIM);
1632         }
1633
1634       /* Examine the USEs of STMT. For each ssa-name USE thta is defined
1635          in the loop, mark the stmt that defines it (DEF_STMT) as
1636          relevant/irrelevant and live/dead according to the liveness and
1637          relevance properties of STMT.
1638        */
1639
1640       gcc_assert (TREE_CODE (stmt) != PHI_NODE);
1641
1642       ann = stmt_ann (stmt);
1643       stmt_vinfo = vinfo_for_stmt (stmt);
1644
1645       relevant_p = STMT_VINFO_RELEVANT_P (stmt_vinfo);
1646       live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
1647
1648       /* Generally, the liveness and relevance properties of STMT are
1649          propagated to the DEF_STMTs of its USEs:
1650              STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
1651              STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- relevant_p
1652
1653          Exceptions:
1654
1655          (case 1)
1656            If USE is used only for address computations (e.g. array indexing),
1657            which does not need to be directly vectorized, then the
1658            liveness/relevance of the respective DEF_STMT is left unchanged.
1659
1660          (case 2)
1661            If STMT has been identified as defining a reduction variable, then
1662            we have two cases:
1663            (case 2.1)
1664              The last use of STMT is the reduction-variable, which is defined
1665              by a loop-header-phi. We don't want to mark the phi as live or
1666              relevant (because it does not need to be vectorized, it is handled
1667              as part of the vectorization of the reduction), so in this case we
1668              skip the call to vect_mark_relevant.
1669            (case 2.2)
1670              The rest of the uses of STMT are defined in the loop body. For
1671              the def_stmt of these uses we want to set liveness/relevance
1672              as follows:
1673                STMT_VINFO_LIVE_P (DEF_STMT_info) <-- false
1674                STMT_VINFO_RELEVANT_P (DEF_STMT_info) <-- true
1675              because even though STMT is classified as live (since it defines a
1676              value that is used across loop iterations) and irrelevant (since it
1677              is not used inside the loop), it will be vectorized, and therefore
1678              the corresponding DEF_STMTs need to marked as relevant.
1679        */
1680
1681       /* case 2.2:  */
1682       if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def)
1683         {
1684           gcc_assert (!relevant_p && live_p);
1685           relevant_p = true;
1686           live_p = false;
1687         }
1688
1689       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1690         {
1691           /* case 1: we are only interested in uses that need to be vectorized.
1692              Uses that are used for address computation are not considered
1693              relevant.
1694            */
1695           if (!exist_non_indexing_operands_for_use_p (use, stmt))
1696             continue;
1697
1698           if (!vect_is_simple_use (use, loop_vinfo, &def_stmt, &def, &dt))
1699             {
1700               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1701                 fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
1702               VEC_free (tree, heap, worklist);
1703               return false;
1704             }
1705
1706           if (!def_stmt || IS_EMPTY_STMT (def_stmt))
1707             continue;
1708
1709           if (vect_print_dump_info (REPORT_DETAILS))
1710             {
1711               fprintf (vect_dump, "worklist: examine use %d: ", i);
1712               print_generic_expr (vect_dump, use, TDF_SLIM);
1713             }
1714
1715           bb = bb_for_stmt (def_stmt);
1716           if (!flow_bb_inside_loop_p (loop, bb))
1717             continue;
1718
1719           /* case 2.1: the reduction-use does not mark the defining-phi
1720              as relevant.  */
1721           if (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
1722               && TREE_CODE (def_stmt) == PHI_NODE)
1723             continue;
1724
1725           vect_mark_relevant (&worklist, def_stmt, relevant_p, live_p);
1726         }
1727     }                           /* while worklist */
1728
1729   VEC_free (tree, heap, worklist);
1730   return true;
1731 }
1732
1733
1734 /* Function vect_can_advance_ivs_p
1735
1736    In case the number of iterations that LOOP iterates is unknown at compile
1737    time, an epilog loop will be generated, and the loop induction variables
1738    (IVs) will be "advanced" to the value they are supposed to take just before
1739    the epilog loop.  Here we check that the access function of the loop IVs
1740    and the expression that represents the loop bound are simple enough.
1741    These restrictions will be relaxed in the future.  */
1742
1743 static bool
1744 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
1745 {
1746   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1747   basic_block bb = loop->header;
1748   tree phi;
1749
1750   /* Analyze phi functions of the loop header.  */
1751
1752   if (vect_print_dump_info (REPORT_DETAILS))
1753     fprintf (vect_dump, "=== vect_can_advance_ivs_p ===");
1754
1755   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1756     {
1757       tree access_fn = NULL;
1758       tree evolution_part;
1759
1760       if (vect_print_dump_info (REPORT_DETAILS))
1761         {
1762           fprintf (vect_dump, "Analyze phi: ");
1763           print_generic_expr (vect_dump, phi, TDF_SLIM);
1764         }
1765
1766       /* Skip virtual phi's. The data dependences that are associated with
1767          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
1768
1769       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1770         {
1771           if (vect_print_dump_info (REPORT_DETAILS))
1772             fprintf (vect_dump, "virtual phi. skip.");
1773           continue;
1774         }
1775
1776       /* Skip reduction phis.  */
1777
1778       if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
1779         {
1780           if (vect_print_dump_info (REPORT_DETAILS))
1781             fprintf (vect_dump, "reduc phi. skip.");
1782           continue;
1783         }
1784
1785       /* Analyze the evolution function.  */
1786
1787       access_fn = instantiate_parameters
1788         (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
1789
1790       if (!access_fn)
1791         {
1792           if (vect_print_dump_info (REPORT_DETAILS))
1793             fprintf (vect_dump, "No Access function.");
1794           return false;
1795         }
1796
1797       if (vect_print_dump_info (REPORT_DETAILS))
1798         {
1799           fprintf (vect_dump, "Access function of PHI: ");
1800           print_generic_expr (vect_dump, access_fn, TDF_SLIM);
1801         }
1802
1803       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
1804
1805       if (evolution_part == NULL_TREE)
1806         {
1807           if (vect_print_dump_info (REPORT_DETAILS))
1808             fprintf (vect_dump, "No evolution.");
1809           return false;
1810         }
1811
1812       /* FORNOW: We do not transform initial conditions of IVs
1813          which evolution functions are a polynomial of degree >= 2.  */
1814
1815       if (tree_is_chrec (evolution_part))
1816         return false;
1817     }
1818
1819   return true;
1820 }
1821
1822
1823 /* Function vect_get_loop_niters.
1824
1825    Determine how many iterations the loop is executed.
1826    If an expression that represents the number of iterations
1827    can be constructed, place it in NUMBER_OF_ITERATIONS.
1828    Return the loop exit condition.  */
1829
1830 static tree
1831 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
1832 {
1833   tree niters;
1834
1835   if (vect_print_dump_info (REPORT_DETAILS))
1836     fprintf (vect_dump, "=== get_loop_niters ===");
1837
1838   niters = number_of_iterations_in_loop (loop);
1839
1840   if (niters != NULL_TREE
1841       && niters != chrec_dont_know)
1842     {
1843       *number_of_iterations = niters;
1844
1845       if (vect_print_dump_info (REPORT_DETAILS))
1846         {
1847           fprintf (vect_dump, "==> get_loop_niters:" );
1848           print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
1849         }
1850     }
1851
1852   return get_loop_exit_condition (loop);
1853 }
1854
1855
1856 /* Function vect_analyze_loop_form.
1857
1858    Verify the following restrictions (some may be relaxed in the future):
1859    - it's an inner-most loop
1860    - number of BBs = 2 (which are the loop header and the latch)
1861    - the loop has a pre-header
1862    - the loop has a single entry and exit
1863    - the loop exit condition is simple enough, and the number of iterations
1864      can be analyzed (a countable loop).  */
1865
1866 static loop_vec_info
1867 vect_analyze_loop_form (struct loop *loop)
1868 {
1869   loop_vec_info loop_vinfo;
1870   tree loop_cond;
1871   tree number_of_iterations = NULL;
1872
1873   if (vect_print_dump_info (REPORT_DETAILS))
1874     fprintf (vect_dump, "=== vect_analyze_loop_form ===");
1875
1876   if (loop->inner)
1877     {
1878       if (vect_print_dump_info (REPORT_OUTER_LOOPS))
1879         fprintf (vect_dump, "not vectorized: nested loop.");
1880       return NULL;
1881     }
1882
1883   if (!loop->single_exit
1884       || loop->num_nodes != 2
1885       || EDGE_COUNT (loop->header->preds) != 2)
1886     {
1887       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1888         {
1889           if (!loop->single_exit)
1890             fprintf (vect_dump, "not vectorized: multiple exits.");
1891           else if (loop->num_nodes != 2)
1892             fprintf (vect_dump, "not vectorized: too many BBs in loop.");
1893           else if (EDGE_COUNT (loop->header->preds) != 2)
1894             fprintf (vect_dump, "not vectorized: too many incoming edges.");
1895         }
1896
1897       return NULL;
1898     }
1899
1900   /* We assume that the loop exit condition is at the end of the loop. i.e,
1901      that the loop is represented as a do-while (with a proper if-guard
1902      before the loop if needed), where the loop header contains all the
1903      executable statements, and the latch is empty.  */
1904   if (!empty_block_p (loop->latch))
1905     {
1906       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1907         fprintf (vect_dump, "not vectorized: unexpected loop form.");
1908       return NULL;
1909     }
1910
1911   /* Make sure there exists a single-predecessor exit bb:  */
1912   if (!single_pred_p (loop->single_exit->dest))
1913     {
1914       edge e = loop->single_exit;
1915       if (!(e->flags & EDGE_ABNORMAL))
1916         {
1917           split_loop_exit_edge (e);
1918           if (vect_print_dump_info (REPORT_DETAILS))
1919             fprintf (vect_dump, "split exit edge.");
1920         }
1921       else
1922         {
1923           if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1924             fprintf (vect_dump, "not vectorized: abnormal loop exit edge.");
1925           return NULL;
1926         }
1927     }
1928
1929   if (empty_block_p (loop->header))
1930     {
1931       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1932         fprintf (vect_dump, "not vectorized: empty loop.");
1933       return NULL;
1934     }
1935
1936   loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
1937   if (!loop_cond)
1938     {
1939       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1940         fprintf (vect_dump, "not vectorized: complicated exit condition.");
1941       return NULL;
1942     }
1943
1944   if (!number_of_iterations)
1945     {
1946       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1947         fprintf (vect_dump,
1948                  "not vectorized: number of iterations cannot be computed.");
1949       return NULL;
1950     }
1951
1952   if (chrec_contains_undetermined (number_of_iterations))
1953     {
1954       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS))
1955         fprintf (vect_dump, "Infinite number of iterations.");
1956       return false;
1957     }
1958
1959   loop_vinfo = new_loop_vec_info (loop);
1960   LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
1961
1962   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
1963     {
1964       if (vect_print_dump_info (REPORT_DETAILS))
1965         {
1966           fprintf (vect_dump, "Symbolic number of iterations is ");
1967           print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
1968         }
1969     }
1970   else
1971   if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0)
1972     {
1973       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
1974         fprintf (vect_dump, "not vectorized: number of iterations = 0.");
1975       return NULL;
1976     }
1977
1978   LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
1979
1980   return loop_vinfo;
1981 }
1982
1983
1984 /* Function vect_analyze_loop.
1985
1986    Apply a set of analyses on LOOP, and create a loop_vec_info struct
1987    for it. The different analyses will record information in the
1988    loop_vec_info struct.  */
1989 loop_vec_info
1990 vect_analyze_loop (struct loop *loop)
1991 {
1992   bool ok;
1993   loop_vec_info loop_vinfo;
1994
1995   if (vect_print_dump_info (REPORT_DETAILS))
1996     fprintf (vect_dump, "===== analyze_loop_nest =====");
1997
1998   /* Check the CFG characteristics of the loop (nesting, entry/exit, etc.  */
1999
2000   loop_vinfo = vect_analyze_loop_form (loop);
2001   if (!loop_vinfo)
2002     {
2003       if (vect_print_dump_info (REPORT_DETAILS))
2004         fprintf (vect_dump, "bad loop form.");
2005       return NULL;
2006     }
2007
2008   /* Find all data references in the loop (which correspond to vdefs/vuses)
2009      and analyze their evolution in the loop.
2010
2011      FORNOW: Handle only simple, array references, which
2012      alignment can be forced, and aligned pointer-references.  */
2013
2014   ok = vect_analyze_data_refs (loop_vinfo);
2015   if (!ok)
2016     {
2017       if (vect_print_dump_info (REPORT_DETAILS))
2018         fprintf (vect_dump, "bad data references.");
2019       destroy_loop_vec_info (loop_vinfo);
2020       return NULL;
2021     }
2022
2023   /* Classify all cross-iteration scalar data-flow cycles.
2024      Cross-iteration cycles caused by virtual phis are analyzed separately.  */
2025
2026   vect_analyze_scalar_cycles (loop_vinfo);
2027
2028   vect_pattern_recog (loop_vinfo);
2029
2030   /* Data-flow analysis to detect stmts that do not need to be vectorized.  */
2031
2032   ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
2033   if (!ok)
2034     {
2035       if (vect_print_dump_info (REPORT_DETAILS))
2036         fprintf (vect_dump, "unexpected pattern.");
2037       destroy_loop_vec_info (loop_vinfo);
2038       return NULL;
2039     }
2040
2041   /* Analyze the alignment of the data-refs in the loop.
2042      Fail if a data reference is found that cannot be vectorized.  */
2043
2044   ok = vect_analyze_data_refs_alignment (loop_vinfo);
2045   if (!ok)
2046     {
2047       if (vect_print_dump_info (REPORT_DETAILS))
2048         fprintf (vect_dump, "bad data alignment.");
2049       destroy_loop_vec_info (loop_vinfo);
2050       return NULL;
2051     }
2052
2053   ok = vect_determine_vectorization_factor (loop_vinfo);
2054   if (!ok)
2055     {
2056       if (vect_print_dump_info (REPORT_DETAILS))
2057         fprintf (vect_dump, "can't determine vectorization factor.");
2058       destroy_loop_vec_info (loop_vinfo);
2059       return NULL;
2060     }
2061
2062   /* Analyze data dependences between the data-refs in the loop.
2063      FORNOW: fail at the first data dependence that we encounter.  */
2064
2065   ok = vect_analyze_data_ref_dependences (loop_vinfo);
2066   if (!ok)
2067     {
2068       if (vect_print_dump_info (REPORT_DETAILS))
2069         fprintf (vect_dump, "bad data dependence.");
2070       destroy_loop_vec_info (loop_vinfo);
2071       return NULL;
2072     }
2073
2074   /* Analyze the access patterns of the data-refs in the loop (consecutive,
2075      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
2076
2077   ok = vect_analyze_data_ref_accesses (loop_vinfo);
2078   if (!ok)
2079     {
2080       if (vect_print_dump_info (REPORT_DETAILS))
2081         fprintf (vect_dump, "bad data access.");
2082       destroy_loop_vec_info (loop_vinfo);
2083       return NULL;
2084     }
2085
2086   /* This pass will decide on using loop versioning and/or loop peeling in
2087      order to enhance the alignment of data references in the loop.  */
2088
2089   ok = vect_enhance_data_refs_alignment (loop_vinfo);
2090   if (!ok)
2091     {
2092       if (vect_print_dump_info (REPORT_DETAILS))
2093         fprintf (vect_dump, "bad data alignment.");
2094       destroy_loop_vec_info (loop_vinfo);
2095       return NULL;
2096     }
2097
2098   /* Scan all the operations in the loop and make sure they are
2099      vectorizable.  */
2100
2101   ok = vect_analyze_operations (loop_vinfo);
2102   if (!ok)
2103     {
2104       if (vect_print_dump_info (REPORT_DETAILS))
2105         fprintf (vect_dump, "bad operation or unsupported loop bound.");
2106       destroy_loop_vec_info (loop_vinfo);
2107       return NULL;
2108     }
2109
2110   LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
2111
2112   return loop_vinfo;
2113 }