gcc/tree-vect-transform.c

   1 /* Transformation 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 "target.h"
  29 #include "rtl.h"
  30 #include "basic-block.h"
  31 #include "diagnostic.h"
  32 #include "tree-flow.h"
  33 #include "tree-dump.h"
  34 #include "timevar.h"
  35 #include "cfgloop.h"
  36 #include "expr.h"
  37 #include "optabs.h"
  38 #include "recog.h"
  39 #include "tree-data-ref.h"
  40 #include "tree-chrec.h"
  41 #include "tree-scalar-evolution.h"
  42 #include "tree-vectorizer.h"
  43 #include "langhooks.h"
  44 #include "tree-pass.h"
  45 #include "toplev.h"
  46 #include "real.h"
  47
  48 /* Utility functions for the code transformation.  */
  49 static bool vect_transform_stmt (tree, block_stmt_iterator *);
  50 static void vect_align_data_ref (tree);
  51 static tree vect_create_destination_var (tree, tree);
  52 static tree vect_create_data_ref_ptr
  53   (tree, block_stmt_iterator *, tree, tree *, bool);
  54 static tree vect_create_addr_base_for_vector_ref (tree, tree *, tree);
  55 static tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
  56 static tree vect_get_vec_def_for_operand (tree, tree, tree *);
  57 static tree vect_init_vector (tree, tree);
  58 static void vect_finish_stmt_generation
  59   (tree stmt, tree vec_stmt, block_stmt_iterator *bsi);
  60 static bool vect_is_simple_cond (tree, loop_vec_info);
  61 static void update_vuses_to_preheader (tree, struct loop*);
  62 static void vect_create_epilog_for_reduction (tree, tree, enum tree_code, tree);
  63 static tree get_initial_def_for_reduction (tree, tree, tree *);
  64
  65 /* Utility function dealing with loop peeling (not peeling itself).  */
  66 static void vect_generate_tmps_on_preheader
  67   (loop_vec_info, tree *, tree *, tree *);
  68 static tree vect_build_loop_niters (loop_vec_info);
  69 static void vect_update_ivs_after_vectorizer (loop_vec_info, tree, edge);
  70 static tree vect_gen_niters_for_prolog_loop (loop_vec_info, tree);
  71 static void vect_update_init_of_dr (struct data_reference *, tree niters);
  72 static void vect_update_inits_of_drs (loop_vec_info, tree);
  73 static void vect_do_peeling_for_alignment (loop_vec_info, struct loops *);
  74 static void vect_do_peeling_for_loop_bound
  75   (loop_vec_info, tree *, struct loops *);
  76 static int vect_min_worthwhile_factor (enum tree_code);
  77
  78
  79 /* Function vect_get_new_vect_var.
  80
  81    Returns a name for a new variable. The current naming scheme appends the
  82    prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
  83    the name of vectorizer generated variables, and appends that to NAME if
  84    provided.  */
  85
  86 static tree
  87 vect_get_new_vect_var (tree type, enum vect_var_kind var_kind, const char *name)
  88 {
  89   const char *prefix;
  90   tree new_vect_var;
  91
  92   switch (var_kind)
  93   {
  94   case vect_simple_var:
  95     prefix = "vect_";
  96     break;
  97   case vect_scalar_var:
  98     prefix = "stmp_";
  99     break;
 100   case vect_pointer_var:
 101     prefix = "vect_p";
 102     break;
 103   default:
 104     gcc_unreachable ();
 105   }
 106
 107   if (name)
 108     new_vect_var = create_tmp_var (type, concat (prefix, name, NULL));
 109   else
 110     new_vect_var = create_tmp_var (type, prefix);
 111
 112   return new_vect_var;
 113 }
 114
 115
 116 /* Function vect_create_addr_base_for_vector_ref.
 117
 118    Create an expression that computes the address of the first memory location
 119    that will be accessed for a data reference.
 120
 121    Input:
 122    STMT: The statement containing the data reference.
 123    NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
 124    OFFSET: Optional. If supplied, it is be added to the initial address.
 125
 126    Output:
 127    1. Return an SSA_NAME whose value is the address of the memory location of
 128       the first vector of the data reference.
 129    2. If new_stmt_list is not NULL_TREE after return then the caller must insert
 130       these statement(s) which define the returned SSA_NAME.
 131
 132    FORNOW: We are only handling array accesses with step 1.  */
 133
 134 static tree
 135 vect_create_addr_base_for_vector_ref (tree stmt,
 136                                       tree *new_stmt_list,
 137                                       tree offset)
 138 {
 139   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 140   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 141   tree data_ref_base = unshare_expr (DR_BASE_ADDRESS (dr));
 142   tree base_name = build_fold_indirect_ref (data_ref_base);
 143   tree ref = DR_REF (dr);
 144   tree scalar_type = TREE_TYPE (ref);
 145   tree scalar_ptr_type = build_pointer_type (scalar_type);
 146   tree vec_stmt;
 147   tree new_temp;
 148   tree addr_base, addr_expr;
 149   tree dest, new_stmt;
 150   tree base_offset = unshare_expr (DR_OFFSET (dr));
 151   tree init = unshare_expr (DR_INIT (dr));
 152
 153   /* Create base_offset */
 154   base_offset = size_binop (PLUS_EXPR, base_offset, init);
 155   dest = create_tmp_var (TREE_TYPE (base_offset), "base_off");
 156   add_referenced_var (dest);
 157   base_offset = force_gimple_operand (base_offset, &new_stmt, false, dest);
 158   append_to_statement_list_force (new_stmt, new_stmt_list);
 159
 160   if (offset)
 161     {
 162       tree tmp = create_tmp_var (TREE_TYPE (base_offset), "offset");
 163       add_referenced_var (tmp);
 164       offset = fold_build2 (MULT_EXPR, TREE_TYPE (offset), offset,
 165                             DR_STEP (dr));
 166       base_offset = fold_build2 (PLUS_EXPR, TREE_TYPE (base_offset),
 167                                  base_offset, offset);
 168       base_offset = force_gimple_operand (base_offset, &new_stmt, false, tmp);
 169       append_to_statement_list_force (new_stmt, new_stmt_list);
 170     }
 171
 172   /* base + base_offset */
 173   addr_base = fold_build2 (PLUS_EXPR, TREE_TYPE (data_ref_base), data_ref_base,
 174                            base_offset);
 175
 176   /* addr_expr = addr_base */
 177   addr_expr = vect_get_new_vect_var (scalar_ptr_type, vect_pointer_var,
 178                                      get_name (base_name));
 179   add_referenced_var (addr_expr);
 180   vec_stmt = build2 (MODIFY_EXPR, void_type_node, addr_expr, addr_base);
 181   new_temp = make_ssa_name (addr_expr, vec_stmt);
 182   TREE_OPERAND (vec_stmt, 0) = new_temp;
 183   append_to_statement_list_force (vec_stmt, new_stmt_list);
 184
 185   if (vect_print_dump_info (REPORT_DETAILS))
 186     {
 187       fprintf (vect_dump, "created ");
 188       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
 189     }
 190   return new_temp;
 191 }
 192
 193
 194 /* Function vect_align_data_ref.
 195
 196    Handle misalignment of a memory accesses.
 197
 198    FORNOW: Can't handle misaligned accesses.
 199    Make sure that the dataref is aligned.  */
 200
 201 static void
 202 vect_align_data_ref (tree stmt)
 203 {
 204   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 205   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 206
 207   /* FORNOW: can't handle misaligned accesses;
 208              all accesses expected to be aligned.  */
 209   gcc_assert (aligned_access_p (dr));
 210 }
 211
 212
 213 /* Function vect_create_data_ref_ptr.
 214
 215    Create a memory reference expression for vector access, to be used in a
 216    vector load/store stmt. The reference is based on a new pointer to vector
 217    type (vp).
 218
 219    Input:
 220    1. STMT: a stmt that references memory. Expected to be of the form
 221          MODIFY_EXPR <name, data-ref> or MODIFY_EXPR <data-ref, name>.
 222    2. BSI: block_stmt_iterator where new stmts can be added.
 223    3. OFFSET (optional): an offset to be added to the initial address accessed
 224         by the data-ref in STMT.
 225    4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
 226         pointing to the initial address.
 227
 228    Output:
 229    1. Declare a new ptr to vector_type, and have it point to the base of the
 230       data reference (initial addressed accessed by the data reference).
 231       For example, for vector of type V8HI, the following code is generated:
 232
 233       v8hi *vp;
 234       vp = (v8hi *)initial_address;
 235
 236       if OFFSET is not supplied:
 237          initial_address = &a[init];
 238       if OFFSET is supplied:
 239          initial_address = &a[init + OFFSET];
 240
 241       Return the initial_address in INITIAL_ADDRESS.
 242
 243    2. If ONLY_INIT is true, return the initial pointer.  Otherwise, create
 244       a data-reference in the loop based on the new vector pointer vp.  This
 245       new data reference will by some means be updated each iteration of
 246       the loop.  Return the pointer vp'.
 247
 248    FORNOW: handle only aligned and consecutive accesses.  */
 249
 250 static tree
 251 vect_create_data_ref_ptr (tree stmt,
 252                           block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
 253                           tree offset, tree *initial_address, bool only_init)
 254 {
 255   tree base_name;
 256   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 257   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 258   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 259   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 260   tree vect_ptr_type;
 261   tree vect_ptr;
 262   tree tag;
 263   tree new_temp;
 264   tree vec_stmt;
 265   tree new_stmt_list = NULL_TREE;
 266   edge pe = loop_preheader_edge (loop);
 267   basic_block new_bb;
 268   tree vect_ptr_init;
 269   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 270
 271   base_name =  build_fold_indirect_ref (unshare_expr (DR_BASE_ADDRESS (dr)));
 272
 273   if (vect_print_dump_info (REPORT_DETAILS))
 274     {
 275       tree data_ref_base = base_name;
 276       fprintf (vect_dump, "create vector-pointer variable to type: ");
 277       print_generic_expr (vect_dump, vectype, TDF_SLIM);
 278       if (TREE_CODE (data_ref_base) == VAR_DECL)
 279         fprintf (vect_dump, "  vectorizing a one dimensional array ref: ");
 280       else if (TREE_CODE (data_ref_base) == ARRAY_REF)
 281         fprintf (vect_dump, "  vectorizing a multidimensional array ref: ");
 282       else if (TREE_CODE (data_ref_base) == COMPONENT_REF)
 283         fprintf (vect_dump, "  vectorizing a record based array ref: ");
 284       else if (TREE_CODE (data_ref_base) == SSA_NAME)
 285         fprintf (vect_dump, "  vectorizing a pointer ref: ");
 286       print_generic_expr (vect_dump, base_name, TDF_SLIM);
 287     }
 288
 289   /** (1) Create the new vector-pointer variable:  **/
 290
 291   vect_ptr_type = build_pointer_type (vectype);
 292   vect_ptr = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
 293                                     get_name (base_name));
 294   add_referenced_var (vect_ptr);
 295
 296
 297   /** (2) Add aliasing information to the new vector-pointer:
 298           (The points-to info (DR_PTR_INFO) may be defined later.)  **/
 299
 300   tag = DR_MEMTAG (dr);
 301   gcc_assert (tag);
 302
 303   /* If tag is a variable (and NOT_A_TAG) than a new symbol memory
 304      tag must be created with tag added to its may alias list.  */
 305   if (!MTAG_P (tag))
 306     new_type_alias (vect_ptr, tag, DR_REF (dr));
 307   else
 308     var_ann (vect_ptr)->symbol_mem_tag = tag;
 309
 310   var_ann (vect_ptr)->subvars = DR_SUBVARS (dr);
 311
 312   /** (3) Calculate the initial address the vector-pointer, and set
 313           the vector-pointer to point to it before the loop:  **/
 314
 315   /* Create: (&(base[init_val+offset]) in the loop preheader.  */
 316   new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
 317                                                    offset);
 318   pe = loop_preheader_edge (loop);
 319   new_bb = bsi_insert_on_edge_immediate (pe, new_stmt_list);
 320   gcc_assert (!new_bb);
 321   *initial_address = new_temp;
 322
 323   /* Create: p = (vectype *) initial_base  */
 324   vec_stmt = fold_convert (vect_ptr_type, new_temp);
 325   vec_stmt = build2 (MODIFY_EXPR, void_type_node, vect_ptr, vec_stmt);
 326   vect_ptr_init = make_ssa_name (vect_ptr, vec_stmt);
 327   TREE_OPERAND (vec_stmt, 0) = vect_ptr_init;
 328   new_bb = bsi_insert_on_edge_immediate (pe, vec_stmt);
 329   gcc_assert (!new_bb);
 330
 331
 332   /** (4) Handle the updating of the vector-pointer inside the loop: **/
 333
 334   if (only_init) /* No update in loop is required.  */
 335     {
 336       /* Copy the points-to information if it exists. */
 337       if (DR_PTR_INFO (dr))
 338         duplicate_ssa_name_ptr_info (vect_ptr_init, DR_PTR_INFO (dr));
 339       return vect_ptr_init;
 340     }
 341   else
 342     {
 343       block_stmt_iterator incr_bsi;
 344       bool insert_after;
 345       tree indx_before_incr, indx_after_incr;
 346       tree incr;
 347
 348       standard_iv_increment_position (loop, &incr_bsi, &insert_after);
 349       create_iv (vect_ptr_init,
 350                  fold_convert (vect_ptr_type, TYPE_SIZE_UNIT (vectype)),
 351                  NULL_TREE, loop, &incr_bsi, insert_after,
 352                  &indx_before_incr, &indx_after_incr);
 353       incr = bsi_stmt (incr_bsi);
 354       set_stmt_info (stmt_ann (incr),
 355                      new_stmt_vec_info (incr, loop_vinfo));
 356
 357       /* Copy the points-to information if it exists. */
 358       if (DR_PTR_INFO (dr))
 359         {
 360           duplicate_ssa_name_ptr_info (indx_before_incr, DR_PTR_INFO (dr));
 361           duplicate_ssa_name_ptr_info (indx_after_incr, DR_PTR_INFO (dr));
 362         }
 363       merge_alias_info (vect_ptr_init, indx_before_incr);
 364       merge_alias_info (vect_ptr_init, indx_after_incr);
 365
 366       return indx_before_incr;
 367     }
 368 }
 369
 370
 371 /* Function vect_create_destination_var.
 372
 373    Create a new temporary of type VECTYPE.  */
 374
 375 static tree
 376 vect_create_destination_var (tree scalar_dest, tree vectype)
 377 {
 378   tree vec_dest;
 379   const char *new_name;
 380   tree type;
 381   enum vect_var_kind kind;
 382
 383   kind = vectype ? vect_simple_var : vect_scalar_var;
 384   type = vectype ? vectype : TREE_TYPE (scalar_dest);
 385
 386   gcc_assert (TREE_CODE (scalar_dest) == SSA_NAME);
 387
 388   new_name = get_name (scalar_dest);
 389   if (!new_name)
 390     new_name = "var_";
 391   vec_dest = vect_get_new_vect_var (type, vect_simple_var, new_name);
 392   add_referenced_var (vec_dest);
 393
 394   return vec_dest;
 395 }
 396
 397
 398 /* Function vect_init_vector.
 399
 400    Insert a new stmt (INIT_STMT) that initializes a new vector variable with
 401    the vector elements of VECTOR_VAR. Return the DEF of INIT_STMT. It will be
 402    used in the vectorization of STMT.  */
 403
 404 static tree
 405 vect_init_vector (tree stmt, tree vector_var)
 406 {
 407   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 408   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 409   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 410   tree new_var;
 411   tree init_stmt;
 412   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
 413   tree vec_oprnd;
 414   edge pe;
 415   tree new_temp;
 416   basic_block new_bb;
 417
 418   new_var = vect_get_new_vect_var (vectype, vect_simple_var, "cst_");
 419   add_referenced_var (new_var);
 420
 421   init_stmt = build2 (MODIFY_EXPR, vectype, new_var, vector_var);
 422   new_temp = make_ssa_name (new_var, init_stmt);
 423   TREE_OPERAND (init_stmt, 0) = new_temp;
 424
 425   pe = loop_preheader_edge (loop);
 426   new_bb = bsi_insert_on_edge_immediate (pe, init_stmt);
 427   gcc_assert (!new_bb);
 428
 429   if (vect_print_dump_info (REPORT_DETAILS))
 430     {
 431       fprintf (vect_dump, "created new init_stmt: ");
 432       print_generic_expr (vect_dump, init_stmt, TDF_SLIM);
 433     }
 434
 435   vec_oprnd = TREE_OPERAND (init_stmt, 0);
 436   return vec_oprnd;
 437 }
 438
 439
 440 /* Function vect_get_vec_def_for_operand.
 441
 442    OP is an operand in STMT. This function returns a (vector) def that will be
 443    used in the vectorized stmt for STMT.
 444
 445    In the case that OP is an SSA_NAME which is defined in the loop, then
 446    STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
 447
 448    In case OP is an invariant or constant, a new stmt that creates a vector def
 449    needs to be introduced.  */
 450
 451 static tree
 452 vect_get_vec_def_for_operand (tree op, tree stmt, tree *scalar_def)
 453 {
 454   tree vec_oprnd;
 455   tree vec_stmt;
 456   tree def_stmt;
 457   stmt_vec_info def_stmt_info = NULL;
 458   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 459   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
 460   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
 461   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 462   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 463   tree vec_inv;
 464   tree vec_cst;
 465   tree t = NULL_TREE;
 466   tree def;
 467   int i;
 468   enum vect_def_type dt;
 469   bool is_simple_use;
 470
 471   if (vect_print_dump_info (REPORT_DETAILS))
 472     {
 473       fprintf (vect_dump, "vect_get_vec_def_for_operand: ");
 474       print_generic_expr (vect_dump, op, TDF_SLIM);
 475     }
 476
 477   is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
 478   gcc_assert (is_simple_use);
 479   if (vect_print_dump_info (REPORT_DETAILS))
 480     {
 481       if (def)
 482         {
 483           fprintf (vect_dump, "def =  ");
 484           print_generic_expr (vect_dump, def, TDF_SLIM);
 485         }
 486       if (def_stmt)
 487         {
 488           fprintf (vect_dump, "  def_stmt =  ");
 489           print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
 490         }
 491     }
 492
 493   switch (dt)
 494     {
 495     /* Case 1: operand is a constant.  */
 496     case vect_constant_def:
 497       {
 498         if (scalar_def)
 499           *scalar_def = op;
 500
 501         /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
 502         if (vect_print_dump_info (REPORT_DETAILS))
 503           fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
 504
 505         for (i = nunits - 1; i >= 0; --i)
 506           {
 507             t = tree_cons (NULL_TREE, op, t);
 508           }
 509         vec_cst = build_vector (vectype, t);
 510         return vect_init_vector (stmt, vec_cst);
 511       }
 512
 513     /* Case 2: operand is defined outside the loop - loop invariant.  */
 514     case vect_invariant_def:
 515       {
 516         if (scalar_def)
 517           *scalar_def = def;
 518
 519         /* Create 'vec_inv = {inv,inv,..,inv}'  */
 520         if (vect_print_dump_info (REPORT_DETAILS))
 521           fprintf (vect_dump, "Create vector_inv.");
 522
 523         for (i = nunits - 1; i >= 0; --i)
 524           {
 525             t = tree_cons (NULL_TREE, def, t);
 526           }
 527
 528         /* FIXME: use build_constructor directly.  */
 529         vec_inv = build_constructor_from_list (vectype, t);
 530         return vect_init_vector (stmt, vec_inv);
 531       }
 532
 533     /* Case 3: operand is defined inside the loop.  */
 534     case vect_loop_def:
 535       {
 536         if (scalar_def)
 537           *scalar_def = def_stmt;
 538
 539         /* Get the def from the vectorized stmt.  */
 540         def_stmt_info = vinfo_for_stmt (def_stmt);
 541         vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
 542         gcc_assert (vec_stmt);
 543         vec_oprnd = TREE_OPERAND (vec_stmt, 0);
 544         return vec_oprnd;
 545       }
 546
 547     /* Case 4: operand is defined by a loop header phi - reduction  */
 548     case vect_reduction_def:
 549       {
 550         gcc_assert (TREE_CODE (def_stmt) == PHI_NODE);
 551
 552         /* Get the def before the loop  */
 553         op = PHI_ARG_DEF_FROM_EDGE (def_stmt, loop_preheader_edge (loop));
 554         return get_initial_def_for_reduction (stmt, op, scalar_def);
 555      }
 556
 557     /* Case 5: operand is defined by loop-header phi - induction.  */
 558     case vect_induction_def:
 559       {
 560         if (vect_print_dump_info (REPORT_DETAILS))
 561           fprintf (vect_dump, "induction - unsupported.");
 562         internal_error ("no support for induction"); /* FORNOW */
 563       }
 564
 565     default:
 566       gcc_unreachable ();
 567     }
 568 }
 569
 570
 571 /* Function vect_finish_stmt_generation.
 572
 573    Insert a new stmt.  */
 574
 575 static void
 576 vect_finish_stmt_generation (tree stmt, tree vec_stmt, block_stmt_iterator *bsi)
 577 {
 578   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
 579
 580   if (vect_print_dump_info (REPORT_DETAILS))
 581     {
 582       fprintf (vect_dump, "add new stmt: ");
 583       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
 584     }
 585
 586   /* Make sure bsi points to the stmt that is being vectorized.  */
 587   gcc_assert (stmt == bsi_stmt (*bsi));
 588
 589 #ifdef USE_MAPPED_LOCATION
 590   SET_EXPR_LOCATION (vec_stmt, EXPR_LOCATION (stmt));
 591 #else
 592   SET_EXPR_LOCUS (vec_stmt, EXPR_LOCUS (stmt));
 593 #endif
 594 }
 595
 596
 597 #define ADJUST_IN_EPILOG 1
 598
 599 /* Function get_initial_def_for_reduction
 600
 601    Input:
 602    STMT - a stmt that performs a reduction operation in the loop.
 603    INIT_VAL - the initial value of the reduction variable
 604
 605    Output:
 606    SCALAR_DEF - a tree that holds a value to be added to the final result
 607         of the reduction (used for "ADJUST_IN_EPILOG" - see below).
 608    Return a vector variable, initialized according to the operation that STMT
 609         performs. This vector will be used as the initial value of the
 610         vector of partial results.
 611
 612    Option1 ("ADJUST_IN_EPILOG"): Initialize the vector as follows:
 613      add:         [0,0,...,0,0]
 614      mult:        [1,1,...,1,1]
 615      min/max:     [init_val,init_val,..,init_val,init_val]
 616      bit and/or:  [init_val,init_val,..,init_val,init_val]
 617    and when necessary (e.g. add/mult case) let the caller know
 618    that it needs to adjust the result by init_val.
 619
 620    Option2: Initialize the vector as follows:
 621      add:         [0,0,...,0,init_val]
 622      mult:        [1,1,...,1,init_val]
 623      min/max:     [init_val,init_val,...,init_val]
 624      bit and/or:  [init_val,init_val,...,init_val]
 625    and no adjustments are needed.
 626
 627    For example, for the following code:
 628
 629    s = init_val;
 630    for (i=0;i<n;i++)
 631      s = s + a[i];
 632
 633    STMT is 's = s + a[i]', and the reduction variable is 's'.
 634    For a vector of 4 units, we want to return either [0,0,0,init_val],
 635    or [0,0,0,0] and let the caller know that it needs to adjust
 636    the result at the end by 'init_val'.
 637
 638    FORNOW: We use the "ADJUST_IN_EPILOG" scheme.
 639    TODO: Use some cost-model to estimate which scheme is more profitable.
 640 */
 641
 642 static tree
 643 get_initial_def_for_reduction (tree stmt, tree init_val, tree *scalar_def)
 644 {
 645   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 646   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
 647   int nunits = GET_MODE_NUNITS (TYPE_MODE (vectype));
 648   int nelements;
 649   enum tree_code code = TREE_CODE (TREE_OPERAND (stmt, 1));
 650   tree type = TREE_TYPE (init_val);
 651   tree def;
 652   tree vec, t = NULL_TREE;
 653   bool need_epilog_adjust;
 654   int i;
 655
 656   gcc_assert (INTEGRAL_TYPE_P (type) || SCALAR_FLOAT_TYPE_P (type));
 657
 658   switch (code)
 659   {
 660   case WIDEN_SUM_EXPR:
 661   case DOT_PROD_EXPR:
 662   case PLUS_EXPR:
 663     if (INTEGRAL_TYPE_P (type))
 664       def = build_int_cst (type, 0);
 665     else
 666       def = build_real (type, dconst0);
 667
 668 #ifdef ADJUST_IN_EPILOG
 669     /* All the 'nunits' elements are set to 0. The final result will be
 670        adjusted by 'init_val' at the loop epilog.  */
 671     nelements = nunits;
 672     need_epilog_adjust = true;
 673 #else
 674     /* 'nunits - 1' elements are set to 0; The last element is set to
 675         'init_val'.  No further adjustments at the epilog are needed.  */
 676     nelements = nunits - 1;
 677     need_epilog_adjust = false;
 678 #endif
 679     break;
 680
 681   case MIN_EXPR:
 682   case MAX_EXPR:
 683     def = init_val;
 684     nelements = nunits;
 685     need_epilog_adjust = false;
 686     break;
 687
 688   default:
 689     gcc_unreachable ();
 690   }
 691
 692   for (i = nelements - 1; i >= 0; --i)
 693     t = tree_cons (NULL_TREE, def, t);
 694
 695   if (nelements == nunits - 1)
 696     {
 697       /* Set the last element of the vector.  */
 698       t = tree_cons (NULL_TREE, init_val, t);
 699       nelements += 1;
 700     }
 701   gcc_assert (nelements == nunits);
 702
 703   if (TREE_CODE (init_val) == INTEGER_CST || TREE_CODE (init_val) == REAL_CST)
 704     vec = build_vector (vectype, t);
 705   else
 706     vec = build_constructor_from_list (vectype, t);
 707
 708   if (!need_epilog_adjust)
 709     *scalar_def = NULL_TREE;
 710   else
 711     *scalar_def = init_val;
 712
 713   return vect_init_vector (stmt, vec);
 714 }
 715
 716
 717 /* Function vect_create_epilog_for_reduction
 718
 719    Create code at the loop-epilog to finalize the result of a reduction
 720    computation.
 721
 722    VECT_DEF is a vector of partial results.
 723    REDUC_CODE is the tree-code for the epilog reduction.
 724    STMT is the scalar reduction stmt that is being vectorized.
 725    REDUCTION_PHI is the phi-node that carries the reduction computation.
 726
 727    This function:
 728    1. Creates the reduction def-use cycle: sets the the arguments for
 729       REDUCTION_PHI:
 730       The loop-entry argument is the vectorized initial-value of the reduction.
 731       The loop-latch argument is VECT_DEF - the vector of partial sums.
 732    2. "Reduces" the vector of partial results VECT_DEF into a single result,
 733       by applying the operation specified by REDUC_CODE if available, or by
 734       other means (whole-vector shifts or a scalar loop).
 735       The function also creates a new phi node at the loop exit to preserve
 736       loop-closed form, as illustrated below.
 737
 738      The flow at the entry to this function:
 739
 740         loop:
 741           vec_def = phi <null, null>            # REDUCTION_PHI
 742           VECT_DEF = vector_stmt                # vectorized form of STMT
 743           s_loop = scalar_stmt                  # (scalar) STMT
 744         loop_exit:
 745           s_out0 = phi <s_loop>                 # (scalar) EXIT_PHI
 746           use <s_out0>
 747           use <s_out0>
 748
 749      The above is transformed by this function into:
 750
 751         loop:
 752           vec_def = phi <vec_init, VECT_DEF>    # REDUCTION_PHI
 753           VECT_DEF = vector_stmt                # vectorized form of STMT
 754           s_loop = scalar_stmt                  # (scalar) STMT
 755         loop_exit:
 756           s_out0 = phi <s_loop>                 # (scalar) EXIT_PHI
 757           v_out1 = phi <VECT_DEF>               # NEW_EXIT_PHI
 758           v_out2 = reduce <v_out1>
 759           s_out3 = extract_field <v_out2, 0>
 760           s_out4 = adjust_result <s_out3>
 761           use <s_out4>
 762           use <s_out4>
 763 */
 764
 765 static void
 766 vect_create_epilog_for_reduction (tree vect_def, tree stmt,
 767                                   enum tree_code reduc_code, tree reduction_phi)
 768 {
 769   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 770   tree vectype;
 771   enum machine_mode mode;
 772   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 773   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 774   basic_block exit_bb;
 775   tree scalar_dest;
 776   tree scalar_type;
 777   tree new_phi;
 778   block_stmt_iterator exit_bsi;
 779   tree vec_dest;
 780   tree new_temp;
 781   tree new_name;
 782   tree epilog_stmt;
 783   tree new_scalar_dest, exit_phi;
 784   tree bitsize, bitpos, bytesize;
 785   enum tree_code code = TREE_CODE (TREE_OPERAND (stmt, 1));
 786   tree scalar_initial_def;
 787   tree vec_initial_def;
 788   tree orig_name;
 789   imm_use_iterator imm_iter;
 790   use_operand_p use_p;
 791   bool extract_scalar_result;
 792   tree reduction_op;
 793   tree orig_stmt;
 794   tree use_stmt;
 795   tree operation = TREE_OPERAND (stmt, 1);
 796   int op_type;
 797
 798   op_type = TREE_CODE_LENGTH (TREE_CODE (operation));
 799   reduction_op = TREE_OPERAND (operation, op_type-1);
 800   vectype = get_vectype_for_scalar_type (TREE_TYPE (reduction_op));
 801   mode = TYPE_MODE (vectype);
 802
 803   /*** 1. Create the reduction def-use cycle  ***/
 804
 805   /* 1.1 set the loop-entry arg of the reduction-phi:  */
 806   /* For the case of reduction, vect_get_vec_def_for_operand returns
 807      the scalar def before the loop, that defines the initial value
 808      of the reduction variable.  */
 809   vec_initial_def = vect_get_vec_def_for_operand (reduction_op, stmt,
 810                                                   &scalar_initial_def);
 811   add_phi_arg (reduction_phi, vec_initial_def, loop_preheader_edge (loop));
 812
 813   /* 1.2 set the loop-latch arg for the reduction-phi:  */
 814   add_phi_arg (reduction_phi, vect_def, loop_latch_edge (loop));
 815
 816   if (vect_print_dump_info (REPORT_DETAILS))
 817     {
 818       fprintf (vect_dump, "transform reduction: created def-use cycle:");
 819       print_generic_expr (vect_dump, reduction_phi, TDF_SLIM);
 820       fprintf (vect_dump, "\n");
 821       print_generic_expr (vect_dump, SSA_NAME_DEF_STMT (vect_def), TDF_SLIM);
 822     }
 823
 824
 825   /*** 2. Create epilog code
 826           The reduction epilog code operates across the elements of the vector
 827           of partial results computed by the vectorized loop.
 828           The reduction epilog code consists of:
 829           step 1: compute the scalar result in a vector (v_out2)
 830           step 2: extract the scalar result (s_out3) from the vector (v_out2)
 831           step 3: adjust the scalar result (s_out3) if needed.
 832
 833           Step 1 can be accomplished using one the following three schemes:
 834           (scheme 1) using reduc_code, if available.
 835           (scheme 2) using whole-vector shifts, if available.
 836           (scheme 3) using a scalar loop. In this case steps 1+2 above are
 837                      combined.
 838
 839           The overall epilog code looks like this:
 840
 841           s_out0 = phi <s_loop>         # original EXIT_PHI
 842           v_out1 = phi <VECT_DEF>       # NEW_EXIT_PHI
 843           v_out2 = reduce <v_out1>              # step 1
 844           s_out3 = extract_field <v_out2, 0>    # step 2
 845           s_out4 = adjust_result <s_out3>       # step 3
 846
 847           (step 3 is optional, and step2 1 and 2 may be combined).
 848           Lastly, the uses of s_out0 are replaced by s_out4.
 849
 850           ***/
 851
 852   /* 2.1 Create new loop-exit-phi to preserve loop-closed form:
 853         v_out1 = phi <v_loop>  */
 854
 855   exit_bb = loop->single_exit->dest;
 856   new_phi = create_phi_node (SSA_NAME_VAR (vect_def), exit_bb);
 857   SET_PHI_ARG_DEF (new_phi, loop->single_exit->dest_idx, vect_def);
 858   exit_bsi = bsi_start (exit_bb);
 859
 860   /* 2.2 Get the relevant tree-code to use in the epilog for schemes 2,3
 861          (i.e. when reduc_code is not available) and in the final adjustment code
 862          (if needed).  Also get the original scalar reduction variable as
 863          defined in the loop.  In case STMT is a "pattern-stmt" (i.e. - it
 864          represents a reduction pattern), the tree-code and scalar-def are
 865          taken from the original stmt that the pattern-stmt (STMT) replaces.
 866          Otherwise (it is a regular reduction) - the tree-code and scalar-def
 867          are taken from STMT.  */
 868
 869   orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
 870   if (!orig_stmt)
 871     {
 872       /* Regular reduction  */
 873       orig_stmt = stmt;
 874     }
 875   else
 876     {
 877       /* Reduction pattern  */
 878       stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt);
 879       gcc_assert (STMT_VINFO_IN_PATTERN_P (stmt_vinfo));
 880       gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
 881     }
 882   code = TREE_CODE (TREE_OPERAND (orig_stmt, 1));
 883   scalar_dest = TREE_OPERAND (orig_stmt, 0);
 884   scalar_type = TREE_TYPE (scalar_dest);
 885   new_scalar_dest = vect_create_destination_var (scalar_dest, NULL);
 886   bitsize = TYPE_SIZE (scalar_type);
 887   bytesize = TYPE_SIZE_UNIT (scalar_type);
 888
 889   /* 2.3 Create the reduction code, using one of the three schemes described
 890          above.  */
 891
 892   if (reduc_code < NUM_TREE_CODES)
 893     {
 894       /*** Case 1:  Create:
 895            v_out2 = reduc_expr <v_out1>  */
 896
 897       if (vect_print_dump_info (REPORT_DETAILS))
 898         fprintf (vect_dump, "Reduce using direct vector reduction.");
 899
 900       vec_dest = vect_create_destination_var (scalar_dest, vectype);
 901       epilog_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
 902                         build1 (reduc_code, vectype,  PHI_RESULT (new_phi)));
 903       new_temp = make_ssa_name (vec_dest, epilog_stmt);
 904       TREE_OPERAND (epilog_stmt, 0) = new_temp;
 905       bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
 906
 907       extract_scalar_result = true;
 908     }
 909   else
 910     {
 911       enum tree_code shift_code = 0;
 912       bool have_whole_vector_shift = true;
 913       int bit_offset;
 914       int element_bitsize = tree_low_cst (bitsize, 1);
 915       int vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
 916       tree vec_temp;
 917
 918       if (vec_shr_optab->handlers[mode].insn_code != CODE_FOR_nothing)
 919         shift_code = VEC_RSHIFT_EXPR;
 920       else
 921         have_whole_vector_shift = false;
 922
 923       /* Regardless of whether we have a whole vector shift, if we're
 924          emulating the operation via tree-vect-generic, we don't want
 925          to use it.  Only the first round of the reduction is likely
 926          to still be profitable via emulation.  */
 927       /* ??? It might be better to emit a reduction tree code here, so that
 928          tree-vect-generic can expand the first round via bit tricks.  */
 929       if (!VECTOR_MODE_P (mode))
 930         have_whole_vector_shift = false;
 931       else
 932         {
 933           optab optab = optab_for_tree_code (code, vectype);
 934           if (optab->handlers[mode].insn_code == CODE_FOR_nothing)
 935             have_whole_vector_shift = false;
 936         }
 937
 938       if (have_whole_vector_shift)
 939         {
 940           /*** Case 2: Create:
 941              for (offset = VS/2; offset >= element_size; offset/=2)
 942                 {
 943                   Create:  va' = vec_shift <va, offset>
 944                   Create:  va = vop <va, va'>
 945                 }  */
 946
 947           if (vect_print_dump_info (REPORT_DETAILS))
 948             fprintf (vect_dump, "Reduce using vector shifts");
 949
 950           vec_dest = vect_create_destination_var (scalar_dest, vectype);
 951           new_temp = PHI_RESULT (new_phi);
 952
 953           for (bit_offset = vec_size_in_bits/2;
 954                bit_offset >= element_bitsize;
 955                bit_offset /= 2)
 956             {
 957               tree bitpos = size_int (bit_offset);
 958
 959               epilog_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
 960               build2 (shift_code, vectype, new_temp, bitpos));
 961               new_name = make_ssa_name (vec_dest, epilog_stmt);
 962               TREE_OPERAND (epilog_stmt, 0) = new_name;
 963               bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
 964
 965               epilog_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
 966               build2 (code, vectype, new_name, new_temp));
 967               new_temp = make_ssa_name (vec_dest, epilog_stmt);
 968               TREE_OPERAND (epilog_stmt, 0) = new_temp;
 969               bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
 970             }
 971
 972           extract_scalar_result = true;
 973         }
 974       else
 975         {
 976           tree rhs;
 977
 978           /*** Case 3: Create:
 979              s = extract_field <v_out2, 0>
 980              for (offset = element_size;
 981                   offset < vector_size;
 982                   offset += element_size;)
 983                {
 984                  Create:  s' = extract_field <v_out2, offset>
 985                  Create:  s = op <s, s'>
 986                }  */
 987
 988           if (vect_print_dump_info (REPORT_DETAILS))
 989             fprintf (vect_dump, "Reduce using scalar code. ");
 990
 991           vec_temp = PHI_RESULT (new_phi);
 992           vec_size_in_bits = tree_low_cst (TYPE_SIZE (vectype), 1);
 993           rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
 994                          bitsize_zero_node);
 995           BIT_FIELD_REF_UNSIGNED (rhs) = TYPE_UNSIGNED (scalar_type);
 996           epilog_stmt = build2 (MODIFY_EXPR, scalar_type, new_scalar_dest, rhs);
 997           new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
 998           TREE_OPERAND (epilog_stmt, 0) = new_temp;
 999           bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
1000
1001           for (bit_offset = element_bitsize;
1002                bit_offset < vec_size_in_bits;
1003                bit_offset += element_bitsize)
1004             {
1005               tree bitpos = bitsize_int (bit_offset);
1006               tree rhs = build3 (BIT_FIELD_REF, scalar_type, vec_temp, bitsize,
1007                                  bitpos);
1008
1009               BIT_FIELD_REF_UNSIGNED (rhs) = TYPE_UNSIGNED (scalar_type);
1010               epilog_stmt = build2 (MODIFY_EXPR, scalar_type, new_scalar_dest,
1011                                     rhs);
1012               new_name = make_ssa_name (new_scalar_dest, epilog_stmt);
1013               TREE_OPERAND (epilog_stmt, 0) = new_name;
1014               bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
1015
1016               epilog_stmt = build2 (MODIFY_EXPR, scalar_type, new_scalar_dest,
1017                                 build2 (code, scalar_type, new_name, new_temp));
1018               new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
1019               TREE_OPERAND (epilog_stmt, 0) = new_temp;
1020               bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
1021             }
1022
1023           extract_scalar_result = false;
1024         }
1025     }
1026
1027   /* 2.4  Extract the final scalar result.  Create:
1028          s_out3 = extract_field <v_out2, bitpos>  */
1029
1030   if (extract_scalar_result)
1031     {
1032       tree rhs;
1033
1034       if (vect_print_dump_info (REPORT_DETAILS))
1035         fprintf (vect_dump, "extract scalar result");
1036
1037       if (BYTES_BIG_ENDIAN)
1038         bitpos = size_binop (MULT_EXPR,
1039                        bitsize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1),
1040                        TYPE_SIZE (scalar_type));
1041       else
1042         bitpos = bitsize_zero_node;
1043
1044       rhs = build3 (BIT_FIELD_REF, scalar_type, new_temp, bitsize, bitpos);
1045       BIT_FIELD_REF_UNSIGNED (rhs) = TYPE_UNSIGNED (scalar_type);
1046       epilog_stmt = build2 (MODIFY_EXPR, scalar_type, new_scalar_dest, rhs);
1047       new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
1048       TREE_OPERAND (epilog_stmt, 0) = new_temp;
1049       bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
1050     }
1051
1052   /* 2.4 Adjust the final result by the initial value of the reduction
1053          variable. (When such adjustment is not needed, then
1054          'scalar_initial_def' is zero).
1055
1056          Create:
1057          s_out4 = scalar_expr <s_out3, scalar_initial_def>  */
1058
1059   if (scalar_initial_def)
1060     {
1061       epilog_stmt = build2 (MODIFY_EXPR, scalar_type, new_scalar_dest,
1062                       build2 (code, scalar_type, new_temp, scalar_initial_def));
1063       new_temp = make_ssa_name (new_scalar_dest, epilog_stmt);
1064       TREE_OPERAND (epilog_stmt, 0) = new_temp;
1065       bsi_insert_after (&exit_bsi, epilog_stmt, BSI_NEW_STMT);
1066     }
1067
1068   /* 2.6 Replace uses of s_out0 with uses of s_out3  */
1069
1070   /* Find the loop-closed-use at the loop exit of the original scalar result.
1071      (The reduction result is expected to have two immediate uses - one at the
1072      latch block, and one at the loop exit).  */
1073   exit_phi = NULL;
1074   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
1075     {
1076       if (!flow_bb_inside_loop_p (loop, bb_for_stmt (USE_STMT (use_p))))
1077         {
1078           exit_phi = USE_STMT (use_p);
1079           break;
1080         }
1081     }
1082   /* We expect to have found an exit_phi because of loop-closed-ssa form.  */
1083   gcc_assert (exit_phi);
1084   /* Replace the uses:  */
1085   orig_name = PHI_RESULT (exit_phi);
1086   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, orig_name)
1087     FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1088       SET_USE (use_p, new_temp);
1089 }
1090
1091
1092 /* Function vectorizable_reduction.
1093
1094    Check if STMT performs a reduction operation that can be vectorized.
1095    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1096    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1097    Return FALSE if not a vectorizable STMT, TRUE otherwise.
1098
1099    This function also handles reduction idioms (patterns) that have been
1100    recognized in advance during vect_pattern_recog. In this case, STMT may be
1101    of this form:
1102      X = pattern_expr (arg0, arg1, ..., X)
1103    and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
1104    sequence that had been detected and replaced by the pattern-stmt (STMT).
1105
1106    In some cases of reduction patterns, the type of the reduction variable X is
1107    different than the type of the other arguments of STMT.
1108    In such cases, the vectype that is used when transforming STMT into a vector
1109    stmt is different than the vectype that is used to determine the
1110    vectorization factor, because it consists of a different number of elements
1111    than the actual number of elements that are being operated upon in parallel.
1112
1113    For example, consider an accumulation of shorts into an int accumulator.
1114    On some targets it's possible to vectorize this pattern operating on 8
1115    shorts at a time (hence, the vectype for purposes of determining the
1116    vectorization factor should be V8HI); on the other hand, the vectype that
1117    is used to create the vector form is actually V4SI (the type of the result).
1118
1119    Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
1120    indicates what is the actual level of parallelism (V8HI in the example), so
1121    that the right vectorization factor would be derived. This vectype
1122    corresponds to the type of arguments to the reduction stmt, and should *NOT*
1123    be used to create the vectorized stmt. The right vectype for the vectorized
1124    stmt is obtained from the type of the result X:
1125         get_vectype_for_scalar_type (TREE_TYPE (X))
1126
1127    This means that, contrary to "regular" reductions (or "regular" stmts in
1128    general), the following equation:
1129       STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
1130    does *NOT* necessarily hold for reduction patterns.  */
1131
1132 bool
1133 vectorizable_reduction (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
1134 {
1135   tree vec_dest;
1136   tree scalar_dest;
1137   tree op;
1138   tree loop_vec_def0, loop_vec_def1;
1139   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1140   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1141   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1142   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1143   tree operation;
1144   enum tree_code code, orig_code, epilog_reduc_code = 0;
1145   enum machine_mode vec_mode;
1146   int op_type;
1147   optab optab, reduc_optab;
1148   tree new_temp;
1149   tree def, def_stmt;
1150   enum vect_def_type dt;
1151   tree new_phi;
1152   tree scalar_type;
1153   bool is_simple_use;
1154   tree orig_stmt;
1155   stmt_vec_info orig_stmt_info;
1156   tree expr = NULL_TREE;
1157   int i;
1158
1159   /* 1. Is vectorizable reduction?  */
1160
1161   /* Not supportable if the reduction variable is used in the loop.  */
1162   if (STMT_VINFO_RELEVANT_P (stmt_info))
1163     return false;
1164
1165   if (!STMT_VINFO_LIVE_P (stmt_info))
1166     return false;
1167
1168   /* Make sure it was already recognized as a reduction computation.  */
1169   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_reduction_def)
1170     return false;
1171
1172   /* 2. Has this been recognized as a reduction pattern?
1173
1174      Check if STMT represents a pattern that has been recognized
1175      in earlier analysis stages.  For stmts that represent a pattern,
1176      the STMT_VINFO_RELATED_STMT field records the last stmt in
1177      the original sequence that constitutes the pattern.  */
1178
1179   orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1180   if (orig_stmt)
1181     {
1182       orig_stmt_info = vinfo_for_stmt (orig_stmt);
1183       gcc_assert (STMT_VINFO_RELATED_STMT (orig_stmt_info) == stmt);
1184       gcc_assert (STMT_VINFO_IN_PATTERN_P (orig_stmt_info));
1185       gcc_assert (!STMT_VINFO_IN_PATTERN_P (stmt_info));
1186     }
1187
1188   /* 3. Check the operands of the operation. The first operands are defined
1189         inside the loop body. The last operand is the reduction variable,
1190         which is defined by the loop-header-phi.  */
1191
1192   gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
1193
1194   operation = TREE_OPERAND (stmt, 1);
1195   code = TREE_CODE (operation);
1196   op_type = TREE_CODE_LENGTH (code);
1197
1198   if (op_type != binary_op && op_type != ternary_op)
1199     return false;
1200   scalar_dest = TREE_OPERAND (stmt, 0);
1201   scalar_type = TREE_TYPE (scalar_dest);
1202
1203   /* All uses but the last are expected to be defined in the loop.
1204      The last use is the reduction variable.  */
1205   for (i = 0; i < op_type-1; i++)
1206     {
1207       op = TREE_OPERAND (operation, i);
1208       is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
1209       gcc_assert (is_simple_use);
1210       gcc_assert (dt == vect_loop_def || dt == vect_invariant_def ||
1211                   dt == vect_constant_def);
1212     }
1213
1214   op = TREE_OPERAND (operation, i);
1215   is_simple_use = vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt);
1216   gcc_assert (is_simple_use);
1217   gcc_assert (dt == vect_reduction_def);
1218   gcc_assert (TREE_CODE (def_stmt) == PHI_NODE);
1219   if (orig_stmt)
1220     gcc_assert (orig_stmt == vect_is_simple_reduction (loop, def_stmt));
1221   else
1222     gcc_assert (stmt == vect_is_simple_reduction (loop, def_stmt));
1223
1224   if (STMT_VINFO_LIVE_P (vinfo_for_stmt (def_stmt)))
1225     return false;
1226
1227   /* 4. Supportable by target?  */
1228
1229   /* 4.1. check support for the operation in the loop  */
1230   optab = optab_for_tree_code (code, vectype);
1231   if (!optab)
1232     {
1233       if (vect_print_dump_info (REPORT_DETAILS))
1234         fprintf (vect_dump, "no optab.");
1235       return false;
1236     }
1237   vec_mode = TYPE_MODE (vectype);
1238   if (optab->handlers[(int) vec_mode].insn_code == CODE_FOR_nothing)
1239     {
1240       if (vect_print_dump_info (REPORT_DETAILS))
1241         fprintf (vect_dump, "op not supported by target.");
1242       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
1243           || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
1244              < vect_min_worthwhile_factor (code))
1245         return false;
1246       if (vect_print_dump_info (REPORT_DETAILS))
1247         fprintf (vect_dump, "proceeding using word mode.");
1248     }
1249
1250   /* Worthwhile without SIMD support?  */
1251   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
1252       && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
1253          < vect_min_worthwhile_factor (code))
1254     {
1255       if (vect_print_dump_info (REPORT_DETAILS))
1256         fprintf (vect_dump, "not worthwhile without SIMD support.");
1257       return false;
1258     }
1259
1260   /* 4.2. Check support for the epilog operation.
1261
1262           If STMT represents a reduction pattern, then the type of the
1263           reduction variable may be different than the type of the rest
1264           of the arguments.  For example, consider the case of accumulation
1265           of shorts into an int accumulator; The original code:
1266                         S1: int_a = (int) short_a;
1267           orig_stmt->   S2: int_acc = plus <int_a ,int_acc>;
1268
1269           was replaced with:
1270                         STMT: int_acc = widen_sum <short_a, int_acc>
1271
1272           This means that:
1273           1. The tree-code that is used to create the vector operation in the
1274              epilog code (that reduces the partial results) is not the
1275              tree-code of STMT, but is rather the tree-code of the original
1276              stmt from the pattern that STMT is replacing. I.e, in the example
1277              above we want to use 'widen_sum' in the loop, but 'plus' in the
1278              epilog.
1279           2. The type (mode) we use to check available target support
1280              for the vector operation to be created in the *epilog*, is
1281              determined by the type of the reduction variable (in the example
1282              above we'd check this: plus_optab[vect_int_mode]).
1283              However the type (mode) we use to check available target support
1284              for the vector operation to be created *inside the loop*, is
1285              determined by the type of the other arguments to STMT (in the
1286              example we'd check this: widen_sum_optab[vect_short_mode]).
1287
1288           This is contrary to "regular" reductions, in which the types of all
1289           the arguments are the same as the type of the reduction variable.
1290           For "regular" reductions we can therefore use the same vector type
1291           (and also the same tree-code) when generating the epilog code and
1292           when generating the code inside the loop.  */
1293
1294   if (orig_stmt)
1295     {
1296       /* This is a reduction pattern: get the vectype from the type of the
1297          reduction variable, and get the tree-code from orig_stmt.  */
1298       orig_code = TREE_CODE (TREE_OPERAND (orig_stmt, 1));
1299       vectype = get_vectype_for_scalar_type (TREE_TYPE (def));
1300       vec_mode = TYPE_MODE (vectype);
1301     }
1302   else
1303     {
1304       /* Regular reduction: use the same vectype and tree-code as used for
1305          the vector code inside the loop can be used for the epilog code. */
1306       orig_code = code;
1307     }
1308
1309   if (!reduction_code_for_scalar_code (orig_code, &epilog_reduc_code))
1310     return false;
1311   reduc_optab = optab_for_tree_code (epilog_reduc_code, vectype);
1312   if (!reduc_optab)
1313     {
1314       if (vect_print_dump_info (REPORT_DETAILS))
1315         fprintf (vect_dump, "no optab for reduction.");
1316       epilog_reduc_code = NUM_TREE_CODES;
1317     }
1318   if (reduc_optab->handlers[(int) vec_mode].insn_code == CODE_FOR_nothing)
1319     {
1320       if (vect_print_dump_info (REPORT_DETAILS))
1321         fprintf (vect_dump, "reduc op not supported by target.");
1322       epilog_reduc_code = NUM_TREE_CODES;
1323     }
1324
1325   if (!vec_stmt) /* transformation not required.  */
1326     {
1327       STMT_VINFO_TYPE (stmt_info) = reduc_vec_info_type;
1328       return true;
1329     }
1330
1331   /** Transform.  **/
1332
1333   if (vect_print_dump_info (REPORT_DETAILS))
1334     fprintf (vect_dump, "transform reduction.");
1335
1336   /* Create the destination vector  */
1337   vec_dest = vect_create_destination_var (scalar_dest, vectype);
1338
1339   /* Create the reduction-phi that defines the reduction-operand.  */
1340   new_phi = create_phi_node (vec_dest, loop->header);
1341
1342   /* Prepare the operand that is defined inside the loop body  */
1343   op = TREE_OPERAND (operation, 0);
1344   loop_vec_def0 = vect_get_vec_def_for_operand (op, stmt, NULL);
1345   if (op_type == binary_op)
1346     expr = build2 (code, vectype, loop_vec_def0, PHI_RESULT (new_phi));
1347   else if (op_type == ternary_op)
1348     {
1349       op = TREE_OPERAND (operation, 1);
1350       loop_vec_def1 = vect_get_vec_def_for_operand (op, stmt, NULL);
1351       expr = build3 (code, vectype, loop_vec_def0, loop_vec_def1,
1352                      PHI_RESULT (new_phi));
1353     }
1354
1355   /* Create the vectorized operation that computes the partial results  */
1356   *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, expr);
1357   new_temp = make_ssa_name (vec_dest, *vec_stmt);
1358   TREE_OPERAND (*vec_stmt, 0) = new_temp;
1359   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
1360
1361   /* Finalize the reduction-phi (set it's arguments) and create the
1362      epilog reduction code.  */
1363   vect_create_epilog_for_reduction (new_temp, stmt, epilog_reduc_code, new_phi);
1364   return true;
1365 }
1366
1367
1368 /* Function vectorizable_assignment.
1369
1370    Check if STMT performs an assignment (copy) that can be vectorized.
1371    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1372    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1373    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1374
1375 bool
1376 vectorizable_assignment (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
1377 {
1378   tree vec_dest;
1379   tree scalar_dest;
1380   tree op;
1381   tree vec_oprnd;
1382   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1383   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1384   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1385   tree new_temp;
1386   tree def, def_stmt;
1387   enum vect_def_type dt;
1388
1389   /* Is vectorizable assignment?  */
1390   if (!STMT_VINFO_RELEVANT_P (stmt_info))
1391     return false;
1392
1393   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
1394
1395   if (TREE_CODE (stmt) != MODIFY_EXPR)
1396     return false;
1397
1398   scalar_dest = TREE_OPERAND (stmt, 0);
1399   if (TREE_CODE (scalar_dest) != SSA_NAME)
1400     return false;
1401
1402   op = TREE_OPERAND (stmt, 1);
1403   if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
1404     {
1405       if (vect_print_dump_info (REPORT_DETAILS))
1406         fprintf (vect_dump, "use not simple.");
1407       return false;
1408     }
1409
1410   if (!vec_stmt) /* transformation not required.  */
1411     {
1412       STMT_VINFO_TYPE (stmt_info) = assignment_vec_info_type;
1413       return true;
1414     }
1415
1416   /** Transform.  **/
1417   if (vect_print_dump_info (REPORT_DETAILS))
1418     fprintf (vect_dump, "transform assignment.");
1419
1420   /* Handle def.  */
1421   vec_dest = vect_create_destination_var (scalar_dest, vectype);
1422
1423   /* Handle use.  */
1424   op = TREE_OPERAND (stmt, 1);
1425   vec_oprnd = vect_get_vec_def_for_operand (op, stmt, NULL);
1426
1427   /* Arguments are ready. create the new vector stmt.  */
1428   *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, vec_oprnd);
1429   new_temp = make_ssa_name (vec_dest, *vec_stmt);
1430   TREE_OPERAND (*vec_stmt, 0) = new_temp;
1431   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
1432
1433   return true;
1434 }
1435
1436
1437 /* Function vect_min_worthwhile_factor.
1438
1439    For a loop where we could vectorize the operation indicated by CODE,
1440    return the minimum vectorization factor that makes it worthwhile
1441    to use generic vectors.  */
1442 static int
1443 vect_min_worthwhile_factor (enum tree_code code)
1444 {
1445   switch (code)
1446     {
1447     case PLUS_EXPR:
1448     case MINUS_EXPR:
1449     case NEGATE_EXPR:
1450       return 4;
1451
1452     case BIT_AND_EXPR:
1453     case BIT_IOR_EXPR:
1454     case BIT_XOR_EXPR:
1455     case BIT_NOT_EXPR:
1456       return 2;
1457
1458     default:
1459       return INT_MAX;
1460     }
1461 }
1462
1463
1464 /* Function vectorizable_operation.
1465
1466    Check if STMT performs a binary or unary operation that can be vectorized.
1467    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1468    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1469    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1470
1471 bool
1472 vectorizable_operation (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
1473 {
1474   tree vec_dest;
1475   tree scalar_dest;
1476   tree operation;
1477   tree op0, op1 = NULL;
1478   tree vec_oprnd0, vec_oprnd1=NULL;
1479   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1480   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1481   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1482   int i;
1483   enum tree_code code;
1484   enum machine_mode vec_mode;
1485   tree new_temp;
1486   int op_type;
1487   tree op;
1488   optab optab;
1489   int icode;
1490   enum machine_mode optab_op2_mode;
1491   tree def, def_stmt;
1492   enum vect_def_type dt;
1493
1494   /* Is STMT a vectorizable binary/unary operation?   */
1495   if (!STMT_VINFO_RELEVANT_P (stmt_info))
1496     return false;
1497
1498   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
1499
1500   if (STMT_VINFO_LIVE_P (stmt_info))
1501     {
1502       /* FORNOW: not yet supported.  */
1503       if (vect_print_dump_info (REPORT_DETAILS))
1504         fprintf (vect_dump, "value used after loop.");
1505       return false;
1506     }
1507
1508   if (TREE_CODE (stmt) != MODIFY_EXPR)
1509     return false;
1510
1511   if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
1512     return false;
1513
1514   operation = TREE_OPERAND (stmt, 1);
1515   code = TREE_CODE (operation);
1516   optab = optab_for_tree_code (code, vectype);
1517
1518   /* Support only unary or binary operations.  */
1519   op_type = TREE_CODE_LENGTH (code);
1520   if (op_type != unary_op && op_type != binary_op)
1521     {
1522       if (vect_print_dump_info (REPORT_DETAILS))
1523         fprintf (vect_dump, "num. args = %d (not unary/binary op).", op_type);
1524       return false;
1525     }
1526
1527   for (i = 0; i < op_type; i++)
1528     {
1529       op = TREE_OPERAND (operation, i);
1530       if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
1531         {
1532           if (vect_print_dump_info (REPORT_DETAILS))
1533             fprintf (vect_dump, "use not simple.");
1534           return false;
1535         }
1536     }
1537
1538   /* Supportable by target?  */
1539   if (!optab)
1540     {
1541       if (vect_print_dump_info (REPORT_DETAILS))
1542         fprintf (vect_dump, "no optab.");
1543       return false;
1544     }
1545   vec_mode = TYPE_MODE (vectype);
1546   icode = (int) optab->handlers[(int) vec_mode].insn_code;
1547   if (icode == CODE_FOR_nothing)
1548     {
1549       if (vect_print_dump_info (REPORT_DETAILS))
1550         fprintf (vect_dump, "op not supported by target.");
1551       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
1552           || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
1553              < vect_min_worthwhile_factor (code))
1554         return false;
1555       if (vect_print_dump_info (REPORT_DETAILS))
1556         fprintf (vect_dump, "proceeding using word mode.");
1557     }
1558
1559   /* Worthwhile without SIMD support?  */
1560   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
1561       && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
1562          < vect_min_worthwhile_factor (code))
1563     {
1564       if (vect_print_dump_info (REPORT_DETAILS))
1565         fprintf (vect_dump, "not worthwhile without SIMD support.");
1566       return false;
1567     }
1568
1569   if (code == LSHIFT_EXPR || code == RSHIFT_EXPR)
1570     {
1571       /* FORNOW: not yet supported.  */
1572       if (!VECTOR_MODE_P (vec_mode))
1573         return false;
1574
1575       /* Invariant argument is needed for a vector shift
1576          by a scalar shift operand.  */
1577       optab_op2_mode = insn_data[icode].operand[2].mode;
1578       if (! (VECTOR_MODE_P (optab_op2_mode)
1579              || dt == vect_constant_def
1580              || dt == vect_invariant_def))
1581         {
1582           if (vect_print_dump_info (REPORT_DETAILS))
1583             fprintf (vect_dump, "operand mode requires invariant argument.");
1584           return false;
1585         }
1586     }
1587
1588   if (!vec_stmt) /* transformation not required.  */
1589     {
1590       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
1591       return true;
1592     }
1593
1594   /** Transform.  **/
1595
1596   if (vect_print_dump_info (REPORT_DETAILS))
1597     fprintf (vect_dump, "transform binary/unary operation.");
1598
1599   /* Handle def.  */
1600   scalar_dest = TREE_OPERAND (stmt, 0);
1601   vec_dest = vect_create_destination_var (scalar_dest, vectype);
1602
1603   /* Handle uses.  */
1604   op0 = TREE_OPERAND (operation, 0);
1605   vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
1606
1607   if (op_type == binary_op)
1608     {
1609       op1 = TREE_OPERAND (operation, 1);
1610
1611       if (code == LSHIFT_EXPR || code == RSHIFT_EXPR)
1612         {
1613           /* Vector shl and shr insn patterns can be defined with
1614              scalar operand 2 (shift operand).  In this case, use
1615              constant or loop invariant op1 directly, without
1616              extending it to vector mode first.  */
1617
1618           optab_op2_mode = insn_data[icode].operand[2].mode;
1619           if (!VECTOR_MODE_P (optab_op2_mode))
1620             {
1621               if (vect_print_dump_info (REPORT_DETAILS))
1622                 fprintf (vect_dump, "operand 1 using scalar mode.");
1623               vec_oprnd1 = op1;
1624             }
1625         }
1626
1627       if (!vec_oprnd1)
1628         vec_oprnd1 = vect_get_vec_def_for_operand (op1, stmt, NULL);
1629     }
1630
1631   /* Arguments are ready. create the new vector stmt.  */
1632
1633   if (op_type == binary_op)
1634     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
1635                 build2 (code, vectype, vec_oprnd0, vec_oprnd1));
1636   else
1637     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
1638                 build1 (code, vectype, vec_oprnd0));
1639   new_temp = make_ssa_name (vec_dest, *vec_stmt);
1640   TREE_OPERAND (*vec_stmt, 0) = new_temp;
1641   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
1642
1643   return true;
1644 }
1645
1646
1647 /* Function vectorizable_store.
1648
1649    Check if STMT defines a non scalar data-ref (array/pointer/structure) that
1650    can be vectorized.
1651    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1652    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1653    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1654
1655 bool
1656 vectorizable_store (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
1657 {
1658   tree scalar_dest;
1659   tree data_ref;
1660   tree op;
1661   tree vec_oprnd1;
1662   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1663   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
1664   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1665   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1666   enum machine_mode vec_mode;
1667   tree dummy;
1668   enum dr_alignment_support alignment_support_cheme;
1669   ssa_op_iter iter;
1670   tree def, def_stmt;
1671   enum vect_def_type dt;
1672
1673   /* Is vectorizable store? */
1674
1675   if (TREE_CODE (stmt) != MODIFY_EXPR)
1676     return false;
1677
1678   scalar_dest = TREE_OPERAND (stmt, 0);
1679   if (TREE_CODE (scalar_dest) != ARRAY_REF
1680       && TREE_CODE (scalar_dest) != INDIRECT_REF)
1681     return false;
1682
1683   op = TREE_OPERAND (stmt, 1);
1684   if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
1685     {
1686       if (vect_print_dump_info (REPORT_DETAILS))
1687         fprintf (vect_dump, "use not simple.");
1688       return false;
1689     }
1690
1691   vec_mode = TYPE_MODE (vectype);
1692   /* FORNOW. In some cases can vectorize even if data-type not supported
1693      (e.g. - array initialization with 0).  */
1694   if (mov_optab->handlers[(int)vec_mode].insn_code == CODE_FOR_nothing)
1695     return false;
1696
1697   if (!STMT_VINFO_DATA_REF (stmt_info))
1698     return false;
1699
1700
1701   if (!vec_stmt) /* transformation not required.  */
1702     {
1703       STMT_VINFO_TYPE (stmt_info) = store_vec_info_type;
1704       return true;
1705     }
1706
1707   /** Transform.  **/
1708
1709   if (vect_print_dump_info (REPORT_DETAILS))
1710     fprintf (vect_dump, "transform store");
1711
1712   alignment_support_cheme = vect_supportable_dr_alignment (dr);
1713   gcc_assert (alignment_support_cheme);
1714   gcc_assert (alignment_support_cheme == dr_aligned);  /* FORNOW */
1715
1716   /* Handle use - get the vectorized def from the defining stmt.  */
1717   vec_oprnd1 = vect_get_vec_def_for_operand (op, stmt, NULL);
1718
1719   /* Handle def.  */
1720   /* FORNOW: make sure the data reference is aligned.  */
1721   vect_align_data_ref (stmt);
1722   data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
1723   data_ref = build_fold_indirect_ref (data_ref);
1724
1725   /* Arguments are ready. create the new vector stmt.  */
1726   *vec_stmt = build2 (MODIFY_EXPR, vectype, data_ref, vec_oprnd1);
1727   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
1728
1729   /* Copy the V_MAY_DEFS representing the aliasing of the original array
1730      element's definition to the vector's definition then update the
1731      defining statement.  The original is being deleted so the same
1732      SSA_NAMEs can be used.  */
1733   copy_virtual_operands (*vec_stmt, stmt);
1734
1735   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
1736     {
1737       SSA_NAME_DEF_STMT (def) = *vec_stmt;
1738
1739       /* If this virtual def has a use outside the loop and a loop peel is
1740          performed then the def may be renamed by the peel.  Mark it for
1741          renaming so the later use will also be renamed.  */
1742       mark_sym_for_renaming (SSA_NAME_VAR (def));
1743     }
1744
1745   return true;
1746 }
1747
1748
1749 /* vectorizable_load.
1750
1751    Check if STMT reads a non scalar data-ref (array/pointer/structure) that
1752    can be vectorized.
1753    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1754    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1755    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1756
1757 bool
1758 vectorizable_load (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
1759 {
1760   tree scalar_dest;
1761   tree vec_dest = NULL;
1762   tree data_ref = NULL;
1763   tree op;
1764   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1765   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
1766   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1767   tree new_temp;
1768   int mode;
1769   tree init_addr;
1770   tree new_stmt;
1771   tree dummy;
1772   basic_block new_bb;
1773   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1774   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1775   edge pe = loop_preheader_edge (loop);
1776   enum dr_alignment_support alignment_support_cheme;
1777
1778   /* Is vectorizable load? */
1779   if (!STMT_VINFO_RELEVANT_P (stmt_info))
1780     return false;
1781
1782   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
1783
1784   if (STMT_VINFO_LIVE_P (stmt_info))
1785     {
1786       /* FORNOW: not yet supported.  */
1787       if (vect_print_dump_info (REPORT_DETAILS))
1788         fprintf (vect_dump, "value used after loop.");
1789       return false;
1790     }
1791
1792   if (TREE_CODE (stmt) != MODIFY_EXPR)
1793     return false;
1794
1795   scalar_dest = TREE_OPERAND (stmt, 0);
1796   if (TREE_CODE (scalar_dest) != SSA_NAME)
1797     return false;
1798
1799   op = TREE_OPERAND (stmt, 1);
1800   if (TREE_CODE (op) != ARRAY_REF && TREE_CODE (op) != INDIRECT_REF)
1801     return false;
1802
1803   if (!STMT_VINFO_DATA_REF (stmt_info))
1804     return false;
1805
1806   mode = (int) TYPE_MODE (vectype);
1807
1808   /* FORNOW. In some cases can vectorize even if data-type not supported
1809     (e.g. - data copies).  */
1810   if (mov_optab->handlers[mode].insn_code == CODE_FOR_nothing)
1811     {
1812       if (vect_print_dump_info (REPORT_DETAILS))
1813         fprintf (vect_dump, "Aligned load, but unsupported type.");
1814       return false;
1815     }
1816
1817   if (!vec_stmt) /* transformation not required.  */
1818     {
1819       STMT_VINFO_TYPE (stmt_info) = load_vec_info_type;
1820       return true;
1821     }
1822
1823   /** Transform.  **/
1824
1825   if (vect_print_dump_info (REPORT_DETAILS))
1826     fprintf (vect_dump, "transform load.");
1827
1828   alignment_support_cheme = vect_supportable_dr_alignment (dr);
1829   gcc_assert (alignment_support_cheme);
1830
1831   if (alignment_support_cheme == dr_aligned
1832       || alignment_support_cheme == dr_unaligned_supported)
1833     {
1834       /* Create:
1835          p = initial_addr;
1836          indx = 0;
1837          loop {
1838            vec_dest = *(p);
1839            indx = indx + 1;
1840          }
1841       */
1842
1843       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1844       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
1845       if (aligned_access_p (dr))
1846         data_ref = build_fold_indirect_ref (data_ref);
1847       else
1848         {
1849           int mis = DR_MISALIGNMENT (dr);
1850           tree tmis = (mis == -1 ? size_zero_node : size_int (mis));
1851           tmis = size_binop (MULT_EXPR, tmis, size_int(BITS_PER_UNIT));
1852           data_ref = build2 (MISALIGNED_INDIRECT_REF, vectype, data_ref, tmis);
1853         }
1854       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1855       new_temp = make_ssa_name (vec_dest, new_stmt);
1856       TREE_OPERAND (new_stmt, 0) = new_temp;
1857       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1858       copy_virtual_operands (new_stmt, stmt);
1859     }
1860   else if (alignment_support_cheme == dr_unaligned_software_pipeline)
1861     {
1862       /* Create:
1863          p1 = initial_addr;
1864          msq_init = *(floor(p1))
1865          p2 = initial_addr + VS - 1;
1866          magic = have_builtin ? builtin_result : initial_address;
1867          indx = 0;
1868          loop {
1869            p2' = p2 + indx * vectype_size
1870            lsq = *(floor(p2'))
1871            vec_dest = realign_load (msq, lsq, magic)
1872            indx = indx + 1;
1873            msq = lsq;
1874          }
1875       */
1876
1877       tree offset;
1878       tree magic;
1879       tree phi_stmt;
1880       tree msq_init;
1881       tree msq, lsq;
1882       tree dataref_ptr;
1883       tree params;
1884
1885       /* <1> Create msq_init = *(floor(p1)) in the loop preheader  */
1886       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1887       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE,
1888                                            &init_addr, true);
1889       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, data_ref);
1890       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1891       new_temp = make_ssa_name (vec_dest, new_stmt);
1892       TREE_OPERAND (new_stmt, 0) = new_temp;
1893       new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
1894       gcc_assert (!new_bb);
1895       msq_init = TREE_OPERAND (new_stmt, 0);
1896       copy_virtual_operands (new_stmt, stmt);
1897       update_vuses_to_preheader (new_stmt, loop);
1898
1899
1900       /* <2> Create lsq = *(floor(p2')) in the loop  */
1901       offset = size_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
1902       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1903       dataref_ptr = vect_create_data_ref_ptr (stmt, bsi, offset, &dummy, false);
1904       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, dataref_ptr);
1905       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1906       new_temp = make_ssa_name (vec_dest, new_stmt);
1907       TREE_OPERAND (new_stmt, 0) = new_temp;
1908       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1909       lsq = TREE_OPERAND (new_stmt, 0);
1910       copy_virtual_operands (new_stmt, stmt);
1911
1912
1913       /* <3> */
1914       if (targetm.vectorize.builtin_mask_for_load)
1915         {
1916           /* Create permutation mask, if required, in loop preheader.  */
1917           tree builtin_decl;
1918           params = build_tree_list (NULL_TREE, init_addr);
1919           builtin_decl = targetm.vectorize.builtin_mask_for_load ();
1920           new_stmt = build_function_call_expr (builtin_decl, params);
1921           vec_dest = vect_create_destination_var (scalar_dest,
1922                                                   TREE_TYPE (new_stmt));
1923           new_stmt = build2 (MODIFY_EXPR, TREE_TYPE (vec_dest), vec_dest,
1924                              new_stmt);
1925           new_temp = make_ssa_name (vec_dest, new_stmt);
1926           TREE_OPERAND (new_stmt, 0) = new_temp;
1927           new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
1928           gcc_assert (!new_bb);
1929           magic = TREE_OPERAND (new_stmt, 0);
1930
1931           /* The result of the CALL_EXPR to this builtin is determined from
1932              the value of the parameter and no global variables are touched
1933              which makes the builtin a "const" function.  Requiring the
1934              builtin to have the "const" attribute makes it unnecessary
1935              to call mark_call_clobbered.  */
1936           gcc_assert (TREE_READONLY (builtin_decl));
1937         }
1938       else
1939         {
1940           /* Use current address instead of init_addr for reduced reg pressure.
1941            */
1942           magic = dataref_ptr;
1943         }
1944
1945
1946       /* <4> Create msq = phi <msq_init, lsq> in loop  */
1947       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1948       msq = make_ssa_name (vec_dest, NULL_TREE);
1949       phi_stmt = create_phi_node (msq, loop->header); /* CHECKME */
1950       SSA_NAME_DEF_STMT (msq) = phi_stmt;
1951       add_phi_arg (phi_stmt, msq_init, loop_preheader_edge (loop));
1952       add_phi_arg (phi_stmt, lsq, loop_latch_edge (loop));
1953
1954
1955       /* <5> Create <vec_dest = realign_load (msq, lsq, magic)> in loop  */
1956       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1957       new_stmt = build3 (REALIGN_LOAD_EXPR, vectype, msq, lsq, magic);
1958       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, new_stmt);
1959       new_temp = make_ssa_name (vec_dest, new_stmt);
1960       TREE_OPERAND (new_stmt, 0) = new_temp;
1961       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1962     }
1963   else
1964     gcc_unreachable ();
1965
1966   *vec_stmt = new_stmt;
1967   return true;
1968 }
1969
1970
1971 /* Function vectorizable_live_operation.
1972
1973    STMT computes a value that is used outside the loop. Check if
1974    it can be supported.  */
1975
1976 bool
1977 vectorizable_live_operation (tree stmt,
1978                              block_stmt_iterator *bsi ATTRIBUTE_UNUSED,
1979                              tree *vec_stmt ATTRIBUTE_UNUSED)
1980 {
1981   tree operation;
1982   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1983   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1984   int i;
1985   enum tree_code code;
1986   int op_type;
1987   tree op;
1988   tree def, def_stmt;
1989   enum vect_def_type dt;
1990
1991   if (!STMT_VINFO_LIVE_P (stmt_info))
1992     return false;
1993
1994   if (TREE_CODE (stmt) != MODIFY_EXPR)
1995     return false;
1996
1997   if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
1998     return false;
1999
2000   operation = TREE_OPERAND (stmt, 1);
2001   code = TREE_CODE (operation);
2002
2003   op_type = TREE_CODE_LENGTH (code);
2004
2005   /* FORNOW: support only if all uses are invariant. This means
2006      that the scalar operations can remain in place, unvectorized.
2007      The original last scalar value that they compute will be used.  */
2008
2009   for (i = 0; i < op_type; i++)
2010     {
2011       op = TREE_OPERAND (operation, i);
2012       if (!vect_is_simple_use (op, loop_vinfo, &def_stmt, &def, &dt))
2013         {
2014           if (vect_print_dump_info (REPORT_DETAILS))
2015             fprintf (vect_dump, "use not simple.");
2016           return false;
2017         }
2018
2019       if (dt != vect_invariant_def && dt != vect_constant_def)
2020         return false;
2021     }
2022
2023   /* No transformation is required for the cases we currently support.  */
2024   return true;
2025 }
2026
2027
2028 /* Function vect_is_simple_cond.
2029
2030    Input:
2031    LOOP - the loop that is being vectorized.
2032    COND - Condition that is checked for simple use.
2033
2034    Returns whether a COND can be vectorized.  Checks whether
2035    condition operands are supportable using vec_is_simple_use.  */
2036
2037 static bool
2038 vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
2039 {
2040   tree lhs, rhs;
2041   tree def;
2042   enum vect_def_type dt;
2043
2044   if (!COMPARISON_CLASS_P (cond))
2045     return false;
2046
2047   lhs = TREE_OPERAND (cond, 0);
2048   rhs = TREE_OPERAND (cond, 1);
2049
2050   if (TREE_CODE (lhs) == SSA_NAME)
2051     {
2052       tree lhs_def_stmt = SSA_NAME_DEF_STMT (lhs);
2053       if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt, &def, &dt))
2054         return false;
2055     }
2056   else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST)
2057     return false;
2058
2059   if (TREE_CODE (rhs) == SSA_NAME)
2060     {
2061       tree rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
2062       if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt, &def, &dt))
2063         return false;
2064     }
2065   else if (TREE_CODE (rhs) != INTEGER_CST  && TREE_CODE (rhs) != REAL_CST)
2066     return false;
2067
2068   return true;
2069 }
2070
2071 /* vectorizable_condition.
2072
2073    Check if STMT is conditional modify expression that can be vectorized.
2074    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2075    stmt using VEC_COND_EXPR  to replace it, put it in VEC_STMT, and insert it
2076    at BSI.
2077
2078    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2079
2080 bool
2081 vectorizable_condition (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
2082 {
2083   tree scalar_dest = NULL_TREE;
2084   tree vec_dest = NULL_TREE;
2085   tree op = NULL_TREE;
2086   tree cond_expr, then_clause, else_clause;
2087   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2088   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2089   tree vec_cond_lhs, vec_cond_rhs, vec_then_clause, vec_else_clause;
2090   tree vec_compare, vec_cond_expr;
2091   tree new_temp;
2092   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2093   enum machine_mode vec_mode;
2094   tree def;
2095   enum vect_def_type dt;
2096
2097   if (!STMT_VINFO_RELEVANT_P (stmt_info))
2098     return false;
2099
2100   gcc_assert (STMT_VINFO_DEF_TYPE (stmt_info) == vect_loop_def);
2101
2102   if (STMT_VINFO_LIVE_P (stmt_info))
2103     {
2104       /* FORNOW: not yet supported.  */
2105       if (vect_print_dump_info (REPORT_DETAILS))
2106         fprintf (vect_dump, "value used after loop.");
2107       return false;
2108     }
2109
2110   if (TREE_CODE (stmt) != MODIFY_EXPR)
2111     return false;
2112
2113   op = TREE_OPERAND (stmt, 1);
2114
2115   if (TREE_CODE (op) != COND_EXPR)
2116     return false;
2117
2118   cond_expr = TREE_OPERAND (op, 0);
2119   then_clause = TREE_OPERAND (op, 1);
2120   else_clause = TREE_OPERAND (op, 2);
2121
2122   if (!vect_is_simple_cond (cond_expr, loop_vinfo))
2123     return false;
2124
2125   /* We do not handle two different vector types for the condition
2126      and the values.  */
2127   if (TREE_TYPE (TREE_OPERAND (cond_expr, 0)) != TREE_TYPE (vectype))
2128     return false;
2129
2130   if (TREE_CODE (then_clause) == SSA_NAME)
2131     {
2132       tree then_def_stmt = SSA_NAME_DEF_STMT (then_clause);
2133       if (!vect_is_simple_use (then_clause, loop_vinfo,
2134                                &then_def_stmt, &def, &dt))
2135         return false;
2136     }
2137   else if (TREE_CODE (then_clause) != INTEGER_CST
2138            && TREE_CODE (then_clause) != REAL_CST)
2139     return false;
2140
2141   if (TREE_CODE (else_clause) == SSA_NAME)
2142     {
2143       tree else_def_stmt = SSA_NAME_DEF_STMT (else_clause);
2144       if (!vect_is_simple_use (else_clause, loop_vinfo,
2145                                &else_def_stmt, &def, &dt))
2146         return false;
2147     }
2148   else if (TREE_CODE (else_clause) != INTEGER_CST
2149            && TREE_CODE (else_clause) != REAL_CST)
2150     return false;
2151
2152
2153   vec_mode = TYPE_MODE (vectype);
2154
2155   if (!vec_stmt)
2156     {
2157       STMT_VINFO_TYPE (stmt_info) = condition_vec_info_type;
2158       return expand_vec_cond_expr_p (op, vec_mode);
2159     }
2160
2161   /* Transform */
2162
2163   /* Handle def.  */
2164   scalar_dest = TREE_OPERAND (stmt, 0);
2165   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2166
2167   /* Handle cond expr.  */
2168   vec_cond_lhs =
2169     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 0), stmt, NULL);
2170   vec_cond_rhs =
2171     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 1), stmt, NULL);
2172   vec_then_clause = vect_get_vec_def_for_operand (then_clause, stmt, NULL);
2173   vec_else_clause = vect_get_vec_def_for_operand (else_clause, stmt, NULL);
2174
2175   /* Arguments are ready. create the new vector stmt.  */
2176   vec_compare = build2 (TREE_CODE (cond_expr), vectype,
2177                         vec_cond_lhs, vec_cond_rhs);
2178   vec_cond_expr = build3 (VEC_COND_EXPR, vectype,
2179                           vec_compare, vec_then_clause, vec_else_clause);
2180
2181   *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, vec_cond_expr);
2182   new_temp = make_ssa_name (vec_dest, *vec_stmt);
2183   TREE_OPERAND (*vec_stmt, 0) = new_temp;
2184   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
2185
2186   return true;
2187 }
2188
2189 /* Function vect_transform_stmt.
2190
2191    Create a vectorized stmt to replace STMT, and insert it at BSI.  */
2192
2193 bool
2194 vect_transform_stmt (tree stmt, block_stmt_iterator *bsi)
2195 {
2196   bool is_store = false;
2197   tree vec_stmt = NULL_TREE;
2198   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2199   tree orig_stmt_in_pattern;
2200   bool done;
2201
2202   if (STMT_VINFO_RELEVANT_P (stmt_info))
2203     {
2204       switch (STMT_VINFO_TYPE (stmt_info))
2205       {
2206       case op_vec_info_type:
2207         done = vectorizable_operation (stmt, bsi, &vec_stmt);
2208         gcc_assert (done);
2209         break;
2210
2211       case assignment_vec_info_type:
2212         done = vectorizable_assignment (stmt, bsi, &vec_stmt);
2213         gcc_assert (done);
2214         break;
2215
2216       case load_vec_info_type:
2217         done = vectorizable_load (stmt, bsi, &vec_stmt);
2218         gcc_assert (done);
2219         break;
2220
2221       case store_vec_info_type:
2222         done = vectorizable_store (stmt, bsi, &vec_stmt);
2223         gcc_assert (done);
2224         is_store = true;
2225         break;
2226
2227       case condition_vec_info_type:
2228         done = vectorizable_condition (stmt, bsi, &vec_stmt);
2229         gcc_assert (done);
2230         break;
2231
2232       default:
2233         if (vect_print_dump_info (REPORT_DETAILS))
2234           fprintf (vect_dump, "stmt not supported.");
2235         gcc_unreachable ();
2236       }
2237
2238       gcc_assert (vec_stmt);
2239       STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
2240       orig_stmt_in_pattern = STMT_VINFO_RELATED_STMT (stmt_info);
2241       if (orig_stmt_in_pattern)
2242         {
2243           stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt_in_pattern);
2244           if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
2245             {
2246               gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo) == stmt);
2247
2248               /* STMT was inserted by the vectorizer to replace a computation
2249                  idiom.  ORIG_STMT_IN_PATTERN is a stmt in the original
2250                  sequence that computed this idiom.  We need to record a pointer
2251                  to VEC_STMT in the stmt_info of ORIG_STMT_IN_PATTERN.  See more
2252                  detail in the documentation of vect_pattern_recog.  */
2253
2254               STMT_VINFO_VEC_STMT (stmt_vinfo) = vec_stmt;
2255             }
2256         }
2257     }
2258
2259   if (STMT_VINFO_LIVE_P (stmt_info))
2260     {
2261       switch (STMT_VINFO_TYPE (stmt_info))
2262       {
2263       case reduc_vec_info_type:
2264         done = vectorizable_reduction (stmt, bsi, &vec_stmt);
2265         gcc_assert (done);
2266         break;
2267
2268       default:
2269         done = vectorizable_live_operation (stmt, bsi, &vec_stmt);
2270         gcc_assert (done);
2271       }
2272
2273       if (vec_stmt)
2274         {
2275           gcc_assert (!STMT_VINFO_VEC_STMT (stmt_info));
2276           STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
2277         }
2278     }
2279
2280   return is_store;
2281 }
2282
2283
2284 /* This function builds ni_name = number of iterations loop executes
2285    on the loop preheader.  */
2286
2287 static tree
2288 vect_build_loop_niters (loop_vec_info loop_vinfo)
2289 {
2290   tree ni_name, stmt, var;
2291   edge pe;
2292   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2293   tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
2294
2295   var = create_tmp_var (TREE_TYPE (ni), "niters");
2296   add_referenced_var (var);
2297   ni_name = force_gimple_operand (ni, &stmt, false, var);
2298
2299   pe = loop_preheader_edge (loop);
2300   if (stmt)
2301     {
2302       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
2303       gcc_assert (!new_bb);
2304     }
2305
2306   return ni_name;
2307 }
2308
2309
2310 /* This function generates the following statements:
2311
2312  ni_name = number of iterations loop executes
2313  ratio = ni_name / vf
2314  ratio_mult_vf_name = ratio * vf
2315
2316  and places them at the loop preheader edge.  */
2317
2318 static void
2319 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
2320                                  tree *ni_name_ptr,
2321                                  tree *ratio_mult_vf_name_ptr,
2322                                  tree *ratio_name_ptr)
2323 {
2324
2325   edge pe;
2326   basic_block new_bb;
2327   tree stmt, ni_name;
2328   tree var;
2329   tree ratio_name;
2330   tree ratio_mult_vf_name;
2331   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2332   tree ni = LOOP_VINFO_NITERS (loop_vinfo);
2333   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2334   tree log_vf;
2335
2336   pe = loop_preheader_edge (loop);
2337
2338   /* Generate temporary variable that contains
2339      number of iterations loop executes.  */
2340
2341   ni_name = vect_build_loop_niters (loop_vinfo);
2342   log_vf = build_int_cst (TREE_TYPE (ni), exact_log2 (vf));
2343
2344   /* Create: ratio = ni >> log2(vf) */
2345
2346   var = create_tmp_var (TREE_TYPE (ni), "bnd");
2347   add_referenced_var (var);
2348   ratio_name = make_ssa_name (var, NULL_TREE);
2349   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_name,
2350            build2 (RSHIFT_EXPR, TREE_TYPE (ni_name), ni_name, log_vf));
2351   SSA_NAME_DEF_STMT (ratio_name) = stmt;
2352
2353   pe = loop_preheader_edge (loop);
2354   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
2355   gcc_assert (!new_bb);
2356
2357   /* Create: ratio_mult_vf = ratio << log2 (vf).  */
2358
2359   var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
2360   add_referenced_var (var);
2361   ratio_mult_vf_name = make_ssa_name (var, NULL_TREE);
2362   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_mult_vf_name,
2363            build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name), ratio_name, log_vf));
2364   SSA_NAME_DEF_STMT (ratio_mult_vf_name) = stmt;
2365
2366   pe = loop_preheader_edge (loop);
2367   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
2368   gcc_assert (!new_bb);
2369
2370   *ni_name_ptr = ni_name;
2371   *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
2372   *ratio_name_ptr = ratio_name;
2373
2374   return;
2375 }
2376
2377
2378 /* Function update_vuses_to_preheader.
2379
2380    Input:
2381    STMT - a statement with potential VUSEs.
2382    LOOP - the loop whose preheader will contain STMT.
2383
2384    It's possible to vectorize a loop even though an SSA_NAME from a VUSE
2385    appears to be defined in a V_MAY_DEF in another statement in a loop.
2386    One such case is when the VUSE is at the dereference of a __restricted__
2387    pointer in a load and the V_MAY_DEF is at the dereference of a different
2388    __restricted__ pointer in a store.  Vectorization may result in
2389    copy_virtual_uses being called to copy the problematic VUSE to a new
2390    statement that is being inserted in the loop preheader.  This procedure
2391    is called to change the SSA_NAME in the new statement's VUSE from the
2392    SSA_NAME updated in the loop to the related SSA_NAME available on the
2393    path entering the loop.
2394
2395    When this function is called, we have the following situation:
2396
2397         # vuse <name1>
2398         S1: vload
2399     do {
2400         # name1 = phi < name0 , name2>
2401
2402         # vuse <name1>
2403         S2: vload
2404
2405         # name2 = vdef <name1>
2406         S3: vstore
2407
2408     }while...
2409
2410    Stmt S1 was created in the loop preheader block as part of misaligned-load
2411    handling. This function fixes the name of the vuse of S1 from 'name1' to
2412    'name0'.  */
2413
2414 static void
2415 update_vuses_to_preheader (tree stmt, struct loop *loop)
2416 {
2417   basic_block header_bb = loop->header;
2418   edge preheader_e = loop_preheader_edge (loop);
2419   ssa_op_iter iter;
2420   use_operand_p use_p;
2421
2422   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VUSE)
2423     {
2424       tree ssa_name = USE_FROM_PTR (use_p);
2425       tree def_stmt = SSA_NAME_DEF_STMT (ssa_name);
2426       tree name_var = SSA_NAME_VAR (ssa_name);
2427       basic_block bb = bb_for_stmt (def_stmt);
2428
2429       /* For a use before any definitions, def_stmt is a NOP_EXPR.  */
2430       if (!IS_EMPTY_STMT (def_stmt)
2431           && flow_bb_inside_loop_p (loop, bb))
2432         {
2433           /* If the block containing the statement defining the SSA_NAME
2434              is in the loop then it's necessary to find the definition
2435              outside the loop using the PHI nodes of the header.  */
2436           tree phi;
2437           bool updated = false;
2438
2439           for (phi = phi_nodes (header_bb); phi; phi = TREE_CHAIN (phi))
2440             {
2441               if (SSA_NAME_VAR (PHI_RESULT (phi)) == name_var)
2442                 {
2443                   SET_USE (use_p, PHI_ARG_DEF (phi, preheader_e->dest_idx));
2444                   updated = true;
2445                   break;
2446                 }
2447             }
2448           gcc_assert (updated);
2449         }
2450     }
2451 }
2452
2453
2454 /*   Function vect_update_ivs_after_vectorizer.
2455
2456      "Advance" the induction variables of LOOP to the value they should take
2457      after the execution of LOOP.  This is currently necessary because the
2458      vectorizer does not handle induction variables that are used after the
2459      loop.  Such a situation occurs when the last iterations of LOOP are
2460      peeled, because:
2461      1. We introduced new uses after LOOP for IVs that were not originally used
2462         after LOOP: the IVs of LOOP are now used by an epilog loop.
2463      2. LOOP is going to be vectorized; this means that it will iterate N/VF
2464         times, whereas the loop IVs should be bumped N times.
2465
2466      Input:
2467      - LOOP - a loop that is going to be vectorized. The last few iterations
2468               of LOOP were peeled.
2469      - NITERS - the number of iterations that LOOP executes (before it is
2470                 vectorized). i.e, the number of times the ivs should be bumped.
2471      - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
2472                   coming out from LOOP on which there are uses of the LOOP ivs
2473                   (this is the path from LOOP->exit to epilog_loop->preheader).
2474
2475                   The new definitions of the ivs are placed in LOOP->exit.
2476                   The phi args associated with the edge UPDATE_E in the bb
2477                   UPDATE_E->dest are updated accordingly.
2478
2479      Assumption 1: Like the rest of the vectorizer, this function assumes
2480      a single loop exit that has a single predecessor.
2481
2482      Assumption 2: The phi nodes in the LOOP header and in update_bb are
2483      organized in the same order.
2484
2485      Assumption 3: The access function of the ivs is simple enough (see
2486      vect_can_advance_ivs_p).  This assumption will be relaxed in the future.
2487
2488      Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
2489      coming out of LOOP on which the ivs of LOOP are used (this is the path
2490      that leads to the epilog loop; other paths skip the epilog loop).  This
2491      path starts with the edge UPDATE_E, and its destination (denoted update_bb)
2492      needs to have its phis updated.
2493  */
2494
2495 static void
2496 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
2497                                   edge update_e)
2498 {
2499   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2500   basic_block exit_bb = loop->single_exit->dest;
2501   tree phi, phi1;
2502   basic_block update_bb = update_e->dest;
2503
2504   /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
2505
2506   /* Make sure there exists a single-predecessor exit bb:  */
2507   gcc_assert (single_pred_p (exit_bb));
2508
2509   for (phi = phi_nodes (loop->header), phi1 = phi_nodes (update_bb);
2510        phi && phi1;
2511        phi = PHI_CHAIN (phi), phi1 = PHI_CHAIN (phi1))
2512     {
2513       tree access_fn = NULL;
2514       tree evolution_part;
2515       tree init_expr;
2516       tree step_expr;
2517       tree var, stmt, ni, ni_name;
2518       block_stmt_iterator last_bsi;
2519
2520       if (vect_print_dump_info (REPORT_DETAILS))
2521         {
2522           fprintf (vect_dump, "vect_update_ivs_after_vectorizer: phi: ");
2523           print_generic_expr (vect_dump, phi, TDF_SLIM);
2524         }
2525
2526       /* Skip virtual phi's.  */
2527       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
2528         {
2529           if (vect_print_dump_info (REPORT_DETAILS))
2530             fprintf (vect_dump, "virtual phi. skip.");
2531           continue;
2532         }
2533
2534       /* Skip reduction phis.  */
2535       if (STMT_VINFO_DEF_TYPE (vinfo_for_stmt (phi)) == vect_reduction_def)
2536         {
2537           if (vect_print_dump_info (REPORT_DETAILS))
2538             fprintf (vect_dump, "reduc phi. skip.");
2539           continue;
2540         }
2541
2542       access_fn = analyze_scalar_evolution (loop, PHI_RESULT (phi));
2543       gcc_assert (access_fn);
2544       evolution_part =
2545          unshare_expr (evolution_part_in_loop_num (access_fn, loop->num));
2546       gcc_assert (evolution_part != NULL_TREE);
2547
2548       /* FORNOW: We do not support IVs whose evolution function is a polynomial
2549          of degree >= 2 or exponential.  */
2550       gcc_assert (!tree_is_chrec (evolution_part));
2551
2552       step_expr = evolution_part;
2553       init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
2554                                                                loop->num));
2555
2556       ni = build2 (PLUS_EXPR, TREE_TYPE (init_expr),
2557                   build2 (MULT_EXPR, TREE_TYPE (niters),
2558                        niters, step_expr), init_expr);
2559
2560       var = create_tmp_var (TREE_TYPE (init_expr), "tmp");
2561       add_referenced_var (var);
2562
2563       ni_name = force_gimple_operand (ni, &stmt, false, var);
2564
2565       /* Insert stmt into exit_bb.  */
2566       last_bsi = bsi_last (exit_bb);
2567       if (stmt)
2568         bsi_insert_before (&last_bsi, stmt, BSI_SAME_STMT);
2569
2570       /* Fix phi expressions in the successor bb.  */
2571       SET_PHI_ARG_DEF (phi1, update_e->dest_idx, ni_name);
2572     }
2573 }
2574
2575
2576 /* Function vect_do_peeling_for_loop_bound
2577
2578    Peel the last iterations of the loop represented by LOOP_VINFO.
2579    The peeled iterations form a new epilog loop.  Given that the loop now
2580    iterates NITERS times, the new epilog loop iterates
2581    NITERS % VECTORIZATION_FACTOR times.
2582
2583    The original loop will later be made to iterate
2584    NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).  */
2585
2586 static void
2587 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
2588                                 struct loops *loops)
2589 {
2590   tree ni_name, ratio_mult_vf_name;
2591   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2592   struct loop *new_loop;
2593   edge update_e;
2594   basic_block preheader;
2595   int loop_num;
2596
2597   if (vect_print_dump_info (REPORT_DETAILS))
2598     fprintf (vect_dump, "=== vect_do_peeling_for_loop_bound ===");
2599
2600   initialize_original_copy_tables ();
2601
2602   /* Generate the following variables on the preheader of original loop:
2603
2604      ni_name = number of iteration the original loop executes
2605      ratio = ni_name / vf
2606      ratio_mult_vf_name = ratio * vf  */
2607   vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
2608                                    &ratio_mult_vf_name, ratio);
2609
2610   loop_num  = loop->num;
2611   new_loop = slpeel_tree_peel_loop_to_edge (loop, loops, loop->single_exit,
2612                                             ratio_mult_vf_name, ni_name, false);
2613   gcc_assert (new_loop);
2614   gcc_assert (loop_num == loop->num);
2615 #ifdef ENABLE_CHECKING
2616   slpeel_verify_cfg_after_peeling (loop, new_loop);
2617 #endif
2618
2619   /* A guard that controls whether the new_loop is to be executed or skipped
2620      is placed in LOOP->exit.  LOOP->exit therefore has two successors - one
2621      is the preheader of NEW_LOOP, where the IVs from LOOP are used.  The other
2622      is a bb after NEW_LOOP, where these IVs are not used.  Find the edge that
2623      is on the path where the LOOP IVs are used and need to be updated.  */
2624
2625   preheader = loop_preheader_edge (new_loop)->src;
2626   if (EDGE_PRED (preheader, 0)->src == loop->single_exit->dest)
2627     update_e = EDGE_PRED (preheader, 0);
2628   else
2629     update_e = EDGE_PRED (preheader, 1);
2630
2631   /* Update IVs of original loop as if they were advanced
2632      by ratio_mult_vf_name steps.  */
2633   vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
2634
2635   /* After peeling we have to reset scalar evolution analyzer.  */
2636   scev_reset ();
2637
2638   free_original_copy_tables ();
2639 }
2640
2641
2642 /* Function vect_gen_niters_for_prolog_loop
2643
2644    Set the number of iterations for the loop represented by LOOP_VINFO
2645    to the minimum between LOOP_NITERS (the original iteration count of the loop)
2646    and the misalignment of DR - the data reference recorded in
2647    LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO).  As a result, after the execution of
2648    this loop, the data reference DR will refer to an aligned location.
2649
2650    The following computation is generated:
2651
2652    If the misalignment of DR is known at compile time:
2653      addr_mis = int mis = DR_MISALIGNMENT (dr);
2654    Else, compute address misalignment in bytes:
2655      addr_mis = addr & (vectype_size - 1)
2656
2657    prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
2658
2659    (elem_size = element type size; an element is the scalar element
2660         whose type is the inner type of the vectype)  */
2661
2662 static tree
2663 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
2664 {
2665   struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
2666   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2667   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2668   tree var, stmt;
2669   tree iters, iters_name;
2670   edge pe;
2671   basic_block new_bb;
2672   tree dr_stmt = DR_STMT (dr);
2673   stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
2674   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2675   int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
2676   tree niters_type = TREE_TYPE (loop_niters);
2677
2678   pe = loop_preheader_edge (loop);
2679
2680   if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
2681     {
2682       int byte_misalign = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
2683       int element_size = vectype_align/vf;
2684       int elem_misalign = byte_misalign / element_size;
2685
2686       if (vect_print_dump_info (REPORT_DETAILS))
2687         fprintf (vect_dump, "known alignment = %d.", byte_misalign);
2688       iters = build_int_cst (niters_type, (vf - elem_misalign)&(vf-1));
2689     }
2690   else
2691     {
2692       tree new_stmts = NULL_TREE;
2693       tree start_addr =
2694         vect_create_addr_base_for_vector_ref (dr_stmt, &new_stmts, NULL_TREE);
2695       tree ptr_type = TREE_TYPE (start_addr);
2696       tree size = TYPE_SIZE (ptr_type);
2697       tree type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
2698       tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
2699       tree elem_size_log =
2700         build_int_cst (type, exact_log2 (vectype_align/vf));
2701       tree vf_minus_1 = build_int_cst (type, vf - 1);
2702       tree vf_tree = build_int_cst (type, vf);
2703       tree byte_misalign;
2704       tree elem_misalign;
2705
2706       new_bb = bsi_insert_on_edge_immediate (pe, new_stmts);
2707       gcc_assert (!new_bb);
2708
2709       /* Create:  byte_misalign = addr & (vectype_size - 1)  */
2710       byte_misalign =
2711         build2 (BIT_AND_EXPR, type, start_addr, vectype_size_minus_1);
2712
2713       /* Create:  elem_misalign = byte_misalign / element_size  */
2714       elem_misalign =
2715         build2 (RSHIFT_EXPR, type, byte_misalign, elem_size_log);
2716
2717       /* Create:  (niters_type) (VF - elem_misalign)&(VF - 1)  */
2718       iters = build2 (MINUS_EXPR, type, vf_tree, elem_misalign);
2719       iters = build2 (BIT_AND_EXPR, type, iters, vf_minus_1);
2720       iters = fold_convert (niters_type, iters);
2721     }
2722
2723   /* Create:  prolog_loop_niters = min (iters, loop_niters) */
2724   /* If the loop bound is known at compile time we already verified that it is
2725      greater than vf; since the misalignment ('iters') is at most vf, there's
2726      no need to generate the MIN_EXPR in this case.  */
2727   if (TREE_CODE (loop_niters) != INTEGER_CST)
2728     iters = build2 (MIN_EXPR, niters_type, iters, loop_niters);
2729
2730   if (vect_print_dump_info (REPORT_DETAILS))
2731     {
2732       fprintf (vect_dump, "niters for prolog loop: ");
2733       print_generic_expr (vect_dump, iters, TDF_SLIM);
2734     }
2735
2736   var = create_tmp_var (niters_type, "prolog_loop_niters");
2737   add_referenced_var (var);
2738   iters_name = force_gimple_operand (iters, &stmt, false, var);
2739
2740   /* Insert stmt on loop preheader edge.  */
2741   if (stmt)
2742     {
2743       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
2744       gcc_assert (!new_bb);
2745     }
2746
2747   return iters_name;
2748 }
2749
2750
2751 /* Function vect_update_init_of_dr
2752
2753    NITERS iterations were peeled from LOOP.  DR represents a data reference
2754    in LOOP.  This function updates the information recorded in DR to
2755    account for the fact that the first NITERS iterations had already been
2756    executed.  Specifically, it updates the OFFSET field of DR.  */
2757
2758 static void
2759 vect_update_init_of_dr (struct data_reference *dr, tree niters)
2760 {
2761   tree offset = DR_OFFSET (dr);
2762
2763   niters = fold_build2 (MULT_EXPR, TREE_TYPE (niters), niters, DR_STEP (dr));
2764   offset = fold_build2 (PLUS_EXPR, TREE_TYPE (offset), offset, niters);
2765   DR_OFFSET (dr) = offset;
2766 }
2767
2768
2769 /* Function vect_update_inits_of_drs
2770
2771    NITERS iterations were peeled from the loop represented by LOOP_VINFO.
2772    This function updates the information recorded for the data references in
2773    the loop to account for the fact that the first NITERS iterations had
2774    already been executed.  Specifically, it updates the initial_condition of the
2775    access_function of all the data_references in the loop.  */
2776
2777 static void
2778 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
2779 {
2780   unsigned int i;
2781   VEC (data_reference_p, heap) *datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
2782   struct data_reference *dr;
2783
2784   if (vect_dump && (dump_flags & TDF_DETAILS))
2785     fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
2786
2787   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
2788     vect_update_init_of_dr (dr, niters);
2789 }
2790
2791
2792 /* Function vect_do_peeling_for_alignment
2793
2794    Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
2795    'niters' is set to the misalignment of one of the data references in the
2796    loop, thereby forcing it to refer to an aligned location at the beginning
2797    of the execution of this loop.  The data reference for which we are
2798    peeling is recorded in LOOP_VINFO_UNALIGNED_DR.  */
2799
2800 static void
2801 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo, struct loops *loops)
2802 {
2803   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2804   tree niters_of_prolog_loop, ni_name;
2805   tree n_iters;
2806   struct loop *new_loop;
2807
2808   if (vect_print_dump_info (REPORT_DETAILS))
2809     fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
2810
2811   initialize_original_copy_tables ();
2812
2813   ni_name = vect_build_loop_niters (loop_vinfo);
2814   niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, ni_name);
2815
2816   /* Peel the prolog loop and iterate it niters_of_prolog_loop.  */
2817   new_loop =
2818         slpeel_tree_peel_loop_to_edge (loop, loops, loop_preheader_edge (loop),
2819                                        niters_of_prolog_loop, ni_name, true);
2820   gcc_assert (new_loop);
2821 #ifdef ENABLE_CHECKING
2822   slpeel_verify_cfg_after_peeling (new_loop, loop);
2823 #endif
2824
2825   /* Update number of times loop executes.  */
2826   n_iters = LOOP_VINFO_NITERS (loop_vinfo);
2827   LOOP_VINFO_NITERS (loop_vinfo) = fold_build2 (MINUS_EXPR,
2828                 TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop);
2829
2830   /* Update the init conditions of the access functions of all data refs.  */
2831   vect_update_inits_of_drs (loop_vinfo, niters_of_prolog_loop);
2832
2833   /* After peeling we have to reset scalar evolution analyzer.  */
2834   scev_reset ();
2835
2836   free_original_copy_tables ();
2837 }
2838
2839
2840 /* Function vect_create_cond_for_align_checks.
2841
2842    Create a conditional expression that represents the alignment checks for
2843    all of data references (array element references) whose alignment must be
2844    checked at runtime.
2845
2846    Input:
2847    LOOP_VINFO - two fields of the loop information are used.
2848                 LOOP_VINFO_PTR_MASK is the mask used to check the alignment.
2849                 LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
2850
2851    Output:
2852    COND_EXPR_STMT_LIST - statements needed to construct the conditional
2853                          expression.
2854    The returned value is the conditional expression to be used in the if
2855    statement that controls which version of the loop gets executed at runtime.
2856
2857    The algorithm makes two assumptions:
2858      1) The number of bytes "n" in a vector is a power of 2.
2859      2) An address "a" is aligned if a%n is zero and that this
2860         test can be done as a&(n-1) == 0.  For example, for 16
2861         byte vectors the test is a&0xf == 0.  */
2862
2863 static tree
2864 vect_create_cond_for_align_checks (loop_vec_info loop_vinfo,
2865                                    tree *cond_expr_stmt_list)
2866 {
2867   VEC(tree,heap) *may_misalign_stmts
2868     = LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo);
2869   tree ref_stmt;
2870   int mask = LOOP_VINFO_PTR_MASK (loop_vinfo);
2871   tree mask_cst;
2872   unsigned int i;
2873   tree psize;
2874   tree int_ptrsize_type;
2875   char tmp_name[20];
2876   tree or_tmp_name = NULL_TREE;
2877   tree and_tmp, and_tmp_name, and_stmt;
2878   tree ptrsize_zero;
2879
2880   /* Check that mask is one less than a power of 2, i.e., mask is
2881      all zeros followed by all ones.  */
2882   gcc_assert ((mask != 0) && ((mask & (mask+1)) == 0));
2883
2884   /* CHECKME: what is the best integer or unsigned type to use to hold a
2885      cast from a pointer value?  */
2886   psize = TYPE_SIZE (ptr_type_node);
2887   int_ptrsize_type
2888     = lang_hooks.types.type_for_size (tree_low_cst (psize, 1), 0);
2889
2890   /* Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address
2891      of the first vector of the i'th data reference. */
2892
2893   for (i = 0; VEC_iterate (tree, may_misalign_stmts, i, ref_stmt); i++)
2894     {
2895       tree new_stmt_list = NULL_TREE;
2896       tree addr_base;
2897       tree addr_tmp, addr_tmp_name, addr_stmt;
2898       tree or_tmp, new_or_tmp_name, or_stmt;
2899
2900       /* create: addr_tmp = (int)(address_of_first_vector) */
2901       addr_base = vect_create_addr_base_for_vector_ref (ref_stmt,
2902                                                         &new_stmt_list,
2903                                                         NULL_TREE);
2904
2905       if (new_stmt_list != NULL_TREE)
2906         append_to_statement_list_force (new_stmt_list, cond_expr_stmt_list);
2907
2908       sprintf (tmp_name, "%s%d", "addr2int", i);
2909       addr_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
2910       add_referenced_var (addr_tmp);
2911       addr_tmp_name = make_ssa_name (addr_tmp, NULL_TREE);
2912       addr_stmt = fold_convert (int_ptrsize_type, addr_base);
2913       addr_stmt = build2 (MODIFY_EXPR, void_type_node,
2914                           addr_tmp_name, addr_stmt);
2915       SSA_NAME_DEF_STMT (addr_tmp_name) = addr_stmt;
2916       append_to_statement_list_force (addr_stmt, cond_expr_stmt_list);
2917
2918       /* The addresses are OR together.  */
2919
2920       if (or_tmp_name != NULL_TREE)
2921         {
2922           /* create: or_tmp = or_tmp | addr_tmp */
2923           sprintf (tmp_name, "%s%d", "orptrs", i);
2924           or_tmp = create_tmp_var (int_ptrsize_type, tmp_name);
2925           add_referenced_var (or_tmp);
2926           new_or_tmp_name = make_ssa_name (or_tmp, NULL_TREE);
2927           or_stmt = build2 (MODIFY_EXPR, void_type_node, new_or_tmp_name,
2928                             build2 (BIT_IOR_EXPR, int_ptrsize_type,
2929                                     or_tmp_name,
2930                                     addr_tmp_name));
2931           SSA_NAME_DEF_STMT (new_or_tmp_name) = or_stmt;
2932           append_to_statement_list_force (or_stmt, cond_expr_stmt_list);
2933           or_tmp_name = new_or_tmp_name;
2934         }
2935       else
2936         or_tmp_name = addr_tmp_name;
2937
2938     } /* end for i */
2939
2940   mask_cst = build_int_cst (int_ptrsize_type, mask);
2941
2942   /* create: and_tmp = or_tmp & mask  */
2943   and_tmp = create_tmp_var (int_ptrsize_type, "andmask" );
2944   add_referenced_var (and_tmp);
2945   and_tmp_name = make_ssa_name (and_tmp, NULL_TREE);
2946
2947   and_stmt = build2 (MODIFY_EXPR, void_type_node,
2948                      and_tmp_name,
2949                      build2 (BIT_AND_EXPR, int_ptrsize_type,
2950                              or_tmp_name, mask_cst));
2951   SSA_NAME_DEF_STMT (and_tmp_name) = and_stmt;
2952   append_to_statement_list_force (and_stmt, cond_expr_stmt_list);
2953
2954   /* Make and_tmp the left operand of the conditional test against zero.
2955      if and_tmp has a nonzero bit then some address is unaligned.  */
2956   ptrsize_zero = build_int_cst (int_ptrsize_type, 0);
2957   return build2 (EQ_EXPR, boolean_type_node,
2958                  and_tmp_name, ptrsize_zero);
2959 }
2960
2961
2962 /* Function vect_transform_loop.
2963
2964    The analysis phase has determined that the loop is vectorizable.
2965    Vectorize the loop - created vectorized stmts to replace the scalar
2966    stmts in the loop, and update the loop exit condition.  */
2967
2968 void
2969 vect_transform_loop (loop_vec_info loop_vinfo,
2970                      struct loops *loops ATTRIBUTE_UNUSED)
2971 {
2972   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2973   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
2974   int nbbs = loop->num_nodes;
2975   block_stmt_iterator si;
2976   int i;
2977   tree ratio = NULL;
2978   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2979   bitmap_iterator bi;
2980   unsigned int j;
2981
2982   if (vect_print_dump_info (REPORT_DETAILS))
2983     fprintf (vect_dump, "=== vec_transform_loop ===");
2984
2985   /* If the loop has data references that may or may not be aligned then
2986      two versions of the loop need to be generated, one which is vectorized
2987      and one which isn't.  A test is then generated to control which of the
2988      loops is executed.  The test checks for the alignment of all of the
2989      data references that may or may not be aligned. */
2990
2991   if (VEC_length (tree, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo)))
2992     {
2993       struct loop *nloop;
2994       tree cond_expr;
2995       tree cond_expr_stmt_list = NULL_TREE;
2996       basic_block condition_bb;
2997       block_stmt_iterator cond_exp_bsi;
2998       basic_block merge_bb;
2999       basic_block new_exit_bb;
3000       edge new_exit_e, e;
3001       tree orig_phi, new_phi, arg;
3002
3003       cond_expr = vect_create_cond_for_align_checks (loop_vinfo,
3004                                                      &cond_expr_stmt_list);
3005       initialize_original_copy_tables ();
3006       nloop = loop_version (loops, loop, cond_expr, &condition_bb, true);
3007       free_original_copy_tables();
3008
3009       /** Loop versioning violates an assumption we try to maintain during
3010          vectorization - that the loop exit block has a single predecessor.
3011          After versioning, the exit block of both loop versions is the same
3012          basic block (i.e. it has two predecessors). Just in order to simplify
3013          following transformations in the vectorizer, we fix this situation
3014          here by adding a new (empty) block on the exit-edge of the loop,
3015          with the proper loop-exit phis to maintain loop-closed-form.  **/
3016
3017       merge_bb = loop->single_exit->dest;
3018       gcc_assert (EDGE_COUNT (merge_bb->preds) == 2);
3019       new_exit_bb = split_edge (loop->single_exit);
3020       add_bb_to_loop (new_exit_bb, loop->outer);
3021       new_exit_e = loop->single_exit;
3022       e = EDGE_SUCC (new_exit_bb, 0);
3023
3024       for (orig_phi = phi_nodes (merge_bb); orig_phi;
3025            orig_phi = PHI_CHAIN (orig_phi))
3026         {
3027           new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
3028                                      new_exit_bb);
3029           arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
3030           add_phi_arg (new_phi, arg, new_exit_e);
3031           SET_PHI_ARG_DEF (orig_phi, e->dest_idx, PHI_RESULT (new_phi));
3032         }
3033
3034       /** end loop-exit-fixes after versioning  **/
3035
3036       update_ssa (TODO_update_ssa);
3037       cond_exp_bsi = bsi_last (condition_bb);
3038       bsi_insert_before (&cond_exp_bsi, cond_expr_stmt_list, BSI_SAME_STMT);
3039     }
3040
3041   /* CHECKME: we wouldn't need this if we called update_ssa once
3042      for all loops.  */
3043   bitmap_zero (vect_vnames_to_rename);
3044
3045   /* Peel the loop if there are data refs with unknown alignment.
3046      Only one data ref with unknown store is allowed.  */
3047
3048   if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
3049     vect_do_peeling_for_alignment (loop_vinfo, loops);
3050
3051   /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
3052      compile time constant), or it is a constant that doesn't divide by the
3053      vectorization factor, then an epilog loop needs to be created.
3054      We therefore duplicate the loop: the original loop will be vectorized,
3055      and will compute the first (n/VF) iterations. The second copy of the loop
3056      will remain scalar and will compute the remaining (n%VF) iterations.
3057      (VF is the vectorization factor).  */
3058
3059   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3060       || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3061           && LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0))
3062     vect_do_peeling_for_loop_bound (loop_vinfo, &ratio, loops);
3063   else
3064     ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
3065                 LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
3066
3067   /* 1) Make sure the loop header has exactly two entries
3068      2) Make sure we have a preheader basic block.  */
3069
3070   gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
3071
3072   loop_split_edge_with (loop_preheader_edge (loop), NULL);
3073
3074
3075   /* FORNOW: the vectorizer supports only loops which body consist
3076      of one basic block (header + empty latch). When the vectorizer will
3077      support more involved loop forms, the order by which the BBs are
3078      traversed need to be reconsidered.  */
3079
3080   for (i = 0; i < nbbs; i++)
3081     {
3082       basic_block bb = bbs[i];
3083
3084       for (si = bsi_start (bb); !bsi_end_p (si);)
3085         {
3086           tree stmt = bsi_stmt (si);
3087           stmt_vec_info stmt_info;
3088           bool is_store;
3089
3090           if (vect_print_dump_info (REPORT_DETAILS))
3091             {
3092               fprintf (vect_dump, "------>vectorizing statement: ");
3093               print_generic_expr (vect_dump, stmt, TDF_SLIM);
3094             }
3095           stmt_info = vinfo_for_stmt (stmt);
3096           gcc_assert (stmt_info);
3097           if (!STMT_VINFO_RELEVANT_P (stmt_info)
3098               && !STMT_VINFO_LIVE_P (stmt_info))
3099             {
3100               bsi_next (&si);
3101               continue;
3102             }
3103           /* FORNOW: Verify that all stmts operate on the same number of
3104                      units and no inner unrolling is necessary.  */
3105           gcc_assert
3106                 (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
3107                  == (unsigned HOST_WIDE_INT) vectorization_factor);
3108
3109           /* -------- vectorize statement ------------ */
3110           if (vect_print_dump_info (REPORT_DETAILS))
3111             fprintf (vect_dump, "transform statement.");
3112
3113           is_store = vect_transform_stmt (stmt, &si);
3114           if (is_store)
3115             {
3116               /* Free the attached stmt_vec_info and remove the stmt.  */
3117               stmt_ann_t ann = stmt_ann (stmt);
3118               free (stmt_info);
3119               set_stmt_info (ann, NULL);
3120               bsi_remove (&si, true);
3121               continue;
3122             }
3123
3124           bsi_next (&si);
3125         }                       /* stmts in BB */
3126     }                           /* BBs in loop */
3127
3128   slpeel_make_loop_iterate_ntimes (loop, ratio);
3129
3130   EXECUTE_IF_SET_IN_BITMAP (vect_vnames_to_rename, 0, j, bi)
3131     mark_sym_for_renaming (SSA_NAME_VAR (ssa_name (j)));
3132
3133   /* The memory tags and pointers in vectorized statements need to
3134      have their SSA forms updated.  FIXME, why can't this be delayed
3135      until all the loops have been transformed?  */
3136   update_ssa (TODO_update_ssa);
3137
3138   if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS))
3139     fprintf (vect_dump, "LOOP VECTORIZED.");
3140 }