gcc/tree-vect-transform.c

   1 /* Transformation Utilities for Loop Vectorization.
   2    Copyright (C) 2003,2004,2005 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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "errors.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "target.h"
  30 #include "rtl.h"
  31 #include "basic-block.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "tree-dump.h"
  35 #include "timevar.h"
  36 #include "cfgloop.h"
  37 #include "expr.h"
  38 #include "optabs.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
  47 /* Utility functions for the code transformation.  */
  48 static bool vect_transform_stmt (tree, block_stmt_iterator *);
  49 static void vect_align_data_ref (tree);
  50 static tree vect_create_destination_var (tree, tree);
  51 static tree vect_create_data_ref_ptr
  52   (tree, block_stmt_iterator *, tree, tree *, bool);
  53 static tree vect_create_index_for_vector_ref (loop_vec_info);
  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);
  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
  63 /* Utility function dealing with loop peeling (not peeling itself).  */
  64 static void vect_generate_tmps_on_preheader
  65   (loop_vec_info, tree *, tree *, tree *);
  66 static tree vect_build_loop_niters (loop_vec_info);
  67 static void vect_update_ivs_after_vectorizer (loop_vec_info, tree, edge);
  68 static tree vect_gen_niters_for_prolog_loop (loop_vec_info, tree);
  69 static void vect_update_init_of_dr (struct data_reference *, tree niters);
  70 static void vect_update_inits_of_drs (loop_vec_info, tree);
  71 static void vect_do_peeling_for_alignment (loop_vec_info, struct loops *);
  72 static void vect_do_peeling_for_loop_bound
  73   (loop_vec_info, tree *, struct loops *);
  74
  75
  76 /* Function vect_get_new_vect_var.
  77
  78    Returns a name for a new variable. The current naming scheme appends the
  79    prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
  80    the name of vectorizer generated variables, and appends that to NAME if
  81    provided.  */
  82
  83 static tree
  84 vect_get_new_vect_var (tree type, enum vect_var_kind var_kind, const char *name)
  85 {
  86   const char *prefix;
  87   tree new_vect_var;
  88
  89   if (var_kind == vect_simple_var)
  90     prefix = "vect_";
  91   else
  92     prefix = "vect_p";
  93
  94   if (name)
  95     new_vect_var = create_tmp_var (type, concat (prefix, name, NULL));
  96   else
  97     new_vect_var = create_tmp_var (type, prefix);
  98
  99   return new_vect_var;
 100 }
 101
 102
 103 /* Function vect_create_index_for_vector_ref.
 104
 105    Create (and return) an index variable, along with it's update chain in the
 106    loop. This variable will be used to access a memory location in a vector
 107    operation.
 108
 109    Input:
 110    LOOP: The loop being vectorized.
 111    BSI: The block_stmt_iterator where STMT is. Any new stmts created by this
 112         function can be added here, or in the loop pre-header.
 113
 114    Output:
 115    Return an index that will be used to index a vector array.  It is expected
 116    that a pointer to the first vector will be used as the base address for the
 117    indexed reference.
 118
 119    FORNOW: we are not trying to be efficient, just creating a new index each
 120    time from scratch.  At this time all vector references could use the same
 121    index.
 122
 123    TODO: create only one index to be used by all vector references.  Record
 124    the index in the LOOP_VINFO the first time this procedure is called and
 125    return it on subsequent calls.  The increment of this index must be placed
 126    just before the conditional expression that ends the single block loop.  */
 127
 128 static tree
 129 vect_create_index_for_vector_ref (loop_vec_info loop_vinfo)
 130 {
 131   tree init, step;
 132   block_stmt_iterator incr_bsi;
 133   bool insert_after;
 134   tree indx_before_incr, indx_after_incr;
 135   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 136   tree incr;
 137
 138   /* It is assumed that the base pointer used for vectorized access contains
 139      the address of the first vector.  Therefore the index used for vectorized
 140      access must be initialized to zero and incremented by 1.  */
 141
 142   init = integer_zero_node;
 143   step = integer_one_node;
 144
 145   standard_iv_increment_position (loop, &incr_bsi, &insert_after);
 146   create_iv (init, step, NULL_TREE, loop, &incr_bsi, insert_after,
 147         &indx_before_incr, &indx_after_incr);
 148   incr = bsi_stmt (incr_bsi);
 149   set_stmt_info (stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo));
 150
 151   return indx_before_incr;
 152 }
 153
 154
 155 /* Function vect_create_addr_base_for_vector_ref.
 156
 157    Create an expression that computes the address of the first memory location
 158    that will be accessed for a data reference.
 159
 160    Input:
 161    STMT: The statement containing the data reference.
 162    NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
 163    OFFSET: Optional. If supplied, it is be added to the initial address.
 164
 165    Output:
 166    1. Return an SSA_NAME whose value is the address of the memory location of
 167       the first vector of the data reference.
 168    2. If new_stmt_list is not NULL_TREE after return then the caller must insert
 169       these statement(s) which define the returned SSA_NAME.
 170
 171    FORNOW: We are only handling array accesses with step 1.  */
 172
 173 static tree
 174 vect_create_addr_base_for_vector_ref (tree stmt,
 175                                       tree *new_stmt_list,
 176                                       tree offset)
 177 {
 178   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 179   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 180   tree data_ref_base =
 181     unshare_expr (STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info));
 182   tree base_name = build_fold_indirect_ref (data_ref_base);
 183   tree ref = DR_REF (dr);
 184   tree scalar_type = TREE_TYPE (ref);
 185   tree scalar_ptr_type = build_pointer_type (scalar_type);
 186   tree vec_stmt;
 187   tree new_temp;
 188   tree addr_base, addr_expr;
 189   tree dest, new_stmt;
 190   tree base_offset = unshare_expr (STMT_VINFO_VECT_INIT_OFFSET (stmt_info));
 191
 192   /* Create base_offset */
 193   dest = create_tmp_var (TREE_TYPE (base_offset), "base_off");
 194   add_referenced_tmp_var (dest);
 195   base_offset = force_gimple_operand (base_offset, &new_stmt, false, dest);
 196   append_to_statement_list_force (new_stmt, new_stmt_list);
 197
 198   if (offset)
 199     {
 200       tree tmp = create_tmp_var (TREE_TYPE (base_offset), "offset");
 201       add_referenced_tmp_var (tmp);
 202       offset = fold (build2 (MULT_EXPR, TREE_TYPE (offset), offset,
 203                              STMT_VINFO_VECT_STEP (stmt_info)));
 204       base_offset = fold (build2 (PLUS_EXPR, TREE_TYPE (base_offset),
 205                                   base_offset, offset));
 206       base_offset = force_gimple_operand (base_offset, &new_stmt, false, tmp);
 207       append_to_statement_list_force (new_stmt, new_stmt_list);
 208     }
 209
 210   /* base + base_offset */
 211   addr_base = fold (build2 (PLUS_EXPR, TREE_TYPE (data_ref_base), data_ref_base,
 212                             base_offset));
 213
 214   /* addr_expr = addr_base */
 215   addr_expr = vect_get_new_vect_var (scalar_ptr_type, vect_pointer_var,
 216                                      get_name (base_name));
 217   add_referenced_tmp_var (addr_expr);
 218   vec_stmt = build2 (MODIFY_EXPR, void_type_node, addr_expr, addr_base);
 219   new_temp = make_ssa_name (addr_expr, vec_stmt);
 220   TREE_OPERAND (vec_stmt, 0) = new_temp;
 221   append_to_statement_list_force (vec_stmt, new_stmt_list);
 222
 223   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 224     {
 225       fprintf (vect_dump, "created ");
 226       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
 227     }
 228   return new_temp;
 229 }
 230
 231
 232 /* Function vect_align_data_ref.
 233
 234    Handle mislignment of a memory accesses.
 235
 236    FORNOW: Can't handle misaligned accesses.
 237    Make sure that the dataref is aligned.  */
 238
 239 static void
 240 vect_align_data_ref (tree stmt)
 241 {
 242   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 243   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 244
 245   /* FORNOW: can't handle misaligned accesses;
 246              all accesses expected to be aligned.  */
 247   gcc_assert (aligned_access_p (dr));
 248 }
 249
 250
 251 /* Function vect_create_data_ref_ptr.
 252
 253    Create a memory reference expression for vector access, to be used in a
 254    vector load/store stmt. The reference is based on a new pointer to vector
 255    type (vp).
 256
 257    Input:
 258    1. STMT: a stmt that references memory. Expected to be of the form
 259          MODIFY_EXPR <name, data-ref> or MODIFY_EXPR <data-ref, name>.
 260    2. BSI: block_stmt_iterator where new stmts can be added.
 261    3. OFFSET (optional): an offset to be added to the initial address accessed
 262         by the data-ref in STMT.
 263    4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
 264         pointing to the initial address.
 265
 266    Output:
 267    1. Declare a new ptr to vector_type, and have it point to the base of the
 268       data reference (initial addressed accessed by the data reference).
 269       For example, for vector of type V8HI, the following code is generated:
 270
 271       v8hi *vp;
 272       vp = (v8hi *)initial_address;
 273
 274       if OFFSET is not supplied:
 275          initial_address = &a[init];
 276       if OFFSET is supplied:
 277          initial_address = &a[init + OFFSET];
 278
 279       Return the initial_address in INITIAL_ADDRESS.
 280
 281    2. Create a data-reference in the loop based on the new vector pointer vp,
 282       and using a new index variable 'idx' as follows:
 283
 284       vp' = vp + update
 285
 286       where if ONLY_INIT is true:
 287          update = zero
 288       and otherwise
 289          update = idx + vector_type_size
 290
 291       Return the pointer vp'.
 292
 293
 294    FORNOW: handle only aligned and consecutive accesses.  */
 295
 296 static tree
 297 vect_create_data_ref_ptr (tree stmt, block_stmt_iterator *bsi, tree offset,
 298                           tree *initial_address, bool only_init)
 299 {
 300   tree base_name;
 301   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 302   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 303   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 304   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 305   tree vect_ptr_type;
 306   tree vect_ptr;
 307   tree tag;
 308   tree new_temp;
 309   tree vec_stmt;
 310   tree new_stmt_list = NULL_TREE;
 311   tree idx;
 312   edge pe = loop_preheader_edge (loop);
 313   basic_block new_bb;
 314   tree vect_ptr_init;
 315   tree vectype_size;
 316   tree ptr_update;
 317   tree data_ref_ptr;
 318   tree type, tmp, size;
 319
 320   base_name =  build_fold_indirect_ref (unshare_expr (
 321                       STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info)));
 322
 323   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 324     {
 325       tree data_ref_base = base_name;
 326       fprintf (vect_dump, "create array_ref of type: ");
 327       print_generic_expr (vect_dump, vectype, TDF_SLIM);
 328       if (TREE_CODE (data_ref_base) == VAR_DECL)
 329         fprintf (vect_dump, "  vectorizing a one dimensional array ref: ");
 330       else if (TREE_CODE (data_ref_base) == ARRAY_REF)
 331         fprintf (vect_dump, "  vectorizing a multidimensional array ref: ");
 332       else if (TREE_CODE (data_ref_base) == COMPONENT_REF)
 333         fprintf (vect_dump, "  vectorizing a record based array ref: ");
 334       else if (TREE_CODE (data_ref_base) == SSA_NAME)
 335         fprintf (vect_dump, "  vectorizing a pointer ref: ");
 336       print_generic_expr (vect_dump, base_name, TDF_SLIM);
 337     }
 338
 339   /** (1) Create the new vector-pointer variable:  **/
 340
 341   vect_ptr_type = build_pointer_type (vectype);
 342   vect_ptr = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
 343                                     get_name (base_name));
 344   add_referenced_tmp_var (vect_ptr);
 345
 346
 347   /** (2) Add aliasing information to the new vector-pointer:
 348           (The points-to info (SSA_NAME_PTR_INFO) may be defined later.)  **/
 349
 350   tag = STMT_VINFO_MEMTAG (stmt_info);
 351   gcc_assert (tag);
 352
 353   /* If the memory tag of the original reference was not a type tag or
 354      if the pointed-to type of VECT_PTR has an alias set number
 355      different than TAG's, then we need to create a new type tag for
 356      VECT_PTR and add TAG to its alias set.  */
 357   if (var_ann (tag)->mem_tag_kind == NOT_A_TAG
 358       || get_alias_set (tag) != get_alias_set (TREE_TYPE (vect_ptr_type)))
 359     add_type_alias (vect_ptr, tag);
 360   else
 361     var_ann (vect_ptr)->type_mem_tag = tag;
 362
 363   var_ann (vect_ptr)->subvars = STMT_VINFO_SUBVARS (stmt_info);
 364
 365   /** (3) Calculate the initial address the vector-pointer, and set
 366           the vector-pointer to point to it before the loop:  **/
 367
 368   /* Create: (&(base[init_val+offset]) in the loop preheader.  */
 369   new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
 370                                                    offset);
 371   pe = loop_preheader_edge (loop);
 372   new_bb = bsi_insert_on_edge_immediate (pe, new_stmt_list);
 373   gcc_assert (!new_bb);
 374   *initial_address = new_temp;
 375
 376   /* Create: p = (vectype *) initial_base  */
 377   vec_stmt = fold_convert (vect_ptr_type, new_temp);
 378   vec_stmt = build2 (MODIFY_EXPR, void_type_node, vect_ptr, vec_stmt);
 379   new_temp = make_ssa_name (vect_ptr, vec_stmt);
 380   TREE_OPERAND (vec_stmt, 0) = new_temp;
 381   new_bb = bsi_insert_on_edge_immediate (pe, vec_stmt);
 382   gcc_assert (!new_bb);
 383   vect_ptr_init = TREE_OPERAND (vec_stmt, 0);
 384
 385
 386   /** (4) Handle the updating of the vector-pointer inside the loop: **/
 387
 388   if (only_init) /* No update in loop is required.  */
 389     {
 390       /* Copy the points-to information if it exists. */
 391       if (STMT_VINFO_PTR_INFO (stmt_info))
 392         duplicate_ssa_name_ptr_info (vect_ptr_init,
 393                                      STMT_VINFO_PTR_INFO (stmt_info));
 394       return vect_ptr_init;
 395     }
 396
 397   idx = vect_create_index_for_vector_ref (loop_vinfo);
 398
 399   /* Create: update = idx * vectype_size  */
 400   tmp = create_tmp_var (integer_type_node, "update");
 401   add_referenced_tmp_var (tmp);
 402   size = TYPE_SIZE (vect_ptr_type);
 403   type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
 404   ptr_update = create_tmp_var (type, "update");
 405   add_referenced_tmp_var (ptr_update);
 406   vectype_size = TYPE_SIZE_UNIT (vectype);
 407   vec_stmt = build2 (MULT_EXPR, integer_type_node, idx, vectype_size);
 408   vec_stmt = build2 (MODIFY_EXPR, void_type_node, tmp, vec_stmt);
 409   new_temp = make_ssa_name (tmp, vec_stmt);
 410   TREE_OPERAND (vec_stmt, 0) = new_temp;
 411   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
 412   vec_stmt = fold_convert (type, new_temp);
 413   vec_stmt = build2 (MODIFY_EXPR, void_type_node, ptr_update, vec_stmt);
 414   new_temp = make_ssa_name (ptr_update, vec_stmt);
 415   TREE_OPERAND (vec_stmt, 0) = new_temp;
 416   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
 417
 418   /* Create: data_ref_ptr = vect_ptr_init + update  */
 419   vec_stmt = build2 (PLUS_EXPR, vect_ptr_type, vect_ptr_init, new_temp);
 420   vec_stmt = build2 (MODIFY_EXPR, void_type_node, vect_ptr, vec_stmt);
 421   new_temp = make_ssa_name (vect_ptr, vec_stmt);
 422   TREE_OPERAND (vec_stmt, 0) = new_temp;
 423   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
 424   data_ref_ptr = TREE_OPERAND (vec_stmt, 0);
 425
 426   /* Copy the points-to information if it exists. */
 427   if (STMT_VINFO_PTR_INFO (stmt_info))
 428     duplicate_ssa_name_ptr_info (data_ref_ptr, STMT_VINFO_PTR_INFO (stmt_info));
 429   return data_ref_ptr;
 430 }
 431
 432
 433 /* Function vect_create_destination_var.
 434
 435    Create a new temporary of type VECTYPE.  */
 436
 437 static tree
 438 vect_create_destination_var (tree scalar_dest, tree vectype)
 439 {
 440   tree vec_dest;
 441   const char *new_name;
 442
 443   gcc_assert (TREE_CODE (scalar_dest) == SSA_NAME);
 444
 445   new_name = get_name (scalar_dest);
 446   if (!new_name)
 447     new_name = "var_";
 448   vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, new_name);
 449   add_referenced_tmp_var (vec_dest);
 450
 451   return vec_dest;
 452 }
 453
 454
 455 /* Function vect_init_vector.
 456
 457    Insert a new stmt (INIT_STMT) that initializes a new vector variable with
 458    the vector elements of VECTOR_VAR. Return the DEF of INIT_STMT. It will be
 459    used in the vectorization of STMT.  */
 460
 461 static tree
 462 vect_init_vector (tree stmt, tree vector_var)
 463 {
 464   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 465   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 466   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 467   tree new_var;
 468   tree init_stmt;
 469   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
 470   tree vec_oprnd;
 471   edge pe;
 472   tree new_temp;
 473   basic_block new_bb;
 474
 475   new_var = vect_get_new_vect_var (vectype, vect_simple_var, "cst_");
 476   add_referenced_tmp_var (new_var);
 477
 478   init_stmt = build2 (MODIFY_EXPR, vectype, new_var, vector_var);
 479   new_temp = make_ssa_name (new_var, init_stmt);
 480   TREE_OPERAND (init_stmt, 0) = new_temp;
 481
 482   pe = loop_preheader_edge (loop);
 483   new_bb = bsi_insert_on_edge_immediate (pe, init_stmt);
 484   gcc_assert (!new_bb);
 485
 486   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 487     {
 488       fprintf (vect_dump, "created new init_stmt: ");
 489       print_generic_expr (vect_dump, init_stmt, TDF_SLIM);
 490     }
 491
 492   vec_oprnd = TREE_OPERAND (init_stmt, 0);
 493   return vec_oprnd;
 494 }
 495
 496
 497 /* Function vect_get_vec_def_for_operand.
 498
 499    OP is an operand in STMT. This function returns a (vector) def that will be
 500    used in the vectorized stmt for STMT.
 501
 502    In the case that OP is an SSA_NAME which is defined in the loop, then
 503    STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
 504
 505    In case OP is an invariant or constant, a new stmt that creates a vector def
 506    needs to be introduced.  */
 507
 508 static tree
 509 vect_get_vec_def_for_operand (tree op, tree stmt)
 510 {
 511   tree vec_oprnd;
 512   tree vec_stmt;
 513   tree def_stmt;
 514   stmt_vec_info def_stmt_info = NULL;
 515   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 516   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
 517   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
 518   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 519   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 520   basic_block bb;
 521   tree vec_inv;
 522   tree t = NULL_TREE;
 523   tree def;
 524   int i;
 525
 526   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 527     {
 528       fprintf (vect_dump, "vect_get_vec_def_for_operand: ");
 529       print_generic_expr (vect_dump, op, TDF_SLIM);
 530     }
 531
 532   /** ===> Case 1: operand is a constant.  **/
 533
 534   if (TREE_CODE (op) == INTEGER_CST || TREE_CODE (op) == REAL_CST)
 535     {
 536       /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
 537
 538       tree vec_cst;
 539
 540       /* Build a tree with vector elements.  */
 541       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 542         fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
 543
 544       for (i = nunits - 1; i >= 0; --i)
 545         {
 546           t = tree_cons (NULL_TREE, op, t);
 547         }
 548       vec_cst = build_vector (vectype, t);
 549       return vect_init_vector (stmt, vec_cst);
 550     }
 551
 552   gcc_assert (TREE_CODE (op) == SSA_NAME);
 553
 554   /** ===> Case 2: operand is an SSA_NAME - find the stmt that defines it.  **/
 555
 556   def_stmt = SSA_NAME_DEF_STMT (op);
 557   def_stmt_info = vinfo_for_stmt (def_stmt);
 558
 559   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 560     {
 561       fprintf (vect_dump, "vect_get_vec_def_for_operand: def_stmt: ");
 562       print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
 563     }
 564
 565
 566   /** ==> Case 2.1: operand is defined inside the loop.  **/
 567
 568   if (def_stmt_info)
 569     {
 570       /* Get the def from the vectorized stmt.  */
 571
 572       vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
 573       gcc_assert (vec_stmt);
 574       vec_oprnd = TREE_OPERAND (vec_stmt, 0);
 575       return vec_oprnd;
 576     }
 577
 578
 579   /** ==> Case 2.2: operand is defined by the loop-header phi-node -
 580                     it is a reduction/induction.  **/
 581
 582   bb = bb_for_stmt (def_stmt);
 583   if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb))
 584     {
 585       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 586         fprintf (vect_dump, "reduction/induction - unsupported.");
 587       internal_error ("no support for reduction/induction"); /* FORNOW */
 588     }
 589
 590
 591   /** ==> Case 2.3: operand is defined outside the loop -
 592                     it is a loop invariant.  */
 593
 594   switch (TREE_CODE (def_stmt))
 595     {
 596     case PHI_NODE:
 597       def = PHI_RESULT (def_stmt);
 598       break;
 599     case MODIFY_EXPR:
 600       def = TREE_OPERAND (def_stmt, 0);
 601       break;
 602     case NOP_EXPR:
 603       def = TREE_OPERAND (def_stmt, 0);
 604       gcc_assert (IS_EMPTY_STMT (def_stmt));
 605       def = op;
 606       break;
 607     default:
 608       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 609         {
 610           fprintf (vect_dump, "unsupported defining stmt: ");
 611           print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
 612         }
 613       internal_error ("unsupported defining stmt");
 614     }
 615
 616   /* Build a tree with vector elements.
 617      Create 'vec_inv = {inv,inv,..,inv}'  */
 618
 619   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 620     fprintf (vect_dump, "Create vector_inv.");
 621
 622   for (i = nunits - 1; i >= 0; --i)
 623     {
 624       t = tree_cons (NULL_TREE, def, t);
 625     }
 626
 627   vec_inv = build_constructor (vectype, t);
 628   return vect_init_vector (stmt, vec_inv);
 629 }
 630
 631
 632 /* Function vect_finish_stmt_generation.
 633
 634    Insert a new stmt.  */
 635
 636 static void
 637 vect_finish_stmt_generation (tree stmt, tree vec_stmt, block_stmt_iterator *bsi)
 638 {
 639   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
 640
 641   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 642     {
 643       fprintf (vect_dump, "add new stmt: ");
 644       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
 645     }
 646
 647 #ifdef ENABLE_CHECKING
 648   /* Make sure bsi points to the stmt that is being vectorized.  */
 649   gcc_assert (stmt == bsi_stmt (*bsi));
 650 #endif
 651
 652 #ifdef USE_MAPPED_LOCATION
 653   SET_EXPR_LOCATION (vec_stmt, EXPR_LOCATION (stmt));
 654 #else
 655   SET_EXPR_LOCUS (vec_stmt, EXPR_LOCUS (stmt));
 656 #endif
 657 }
 658
 659
 660 /* Function vectorizable_assignment.
 661
 662    Check if STMT performs an assignment (copy) that can be vectorized.
 663    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
 664    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
 665    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
 666
 667 bool
 668 vectorizable_assignment (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
 669 {
 670   tree vec_dest;
 671   tree scalar_dest;
 672   tree op;
 673   tree vec_oprnd;
 674   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 675   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 676   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 677   tree new_temp;
 678
 679   /* Is vectorizable assignment?  */
 680
 681   if (TREE_CODE (stmt) != MODIFY_EXPR)
 682     return false;
 683
 684   scalar_dest = TREE_OPERAND (stmt, 0);
 685   if (TREE_CODE (scalar_dest) != SSA_NAME)
 686     return false;
 687
 688   op = TREE_OPERAND (stmt, 1);
 689   if (!vect_is_simple_use (op, loop_vinfo, NULL))
 690     {
 691       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 692         fprintf (vect_dump, "use not simple.");
 693       return false;
 694     }
 695
 696   if (!vec_stmt) /* transformation not required.  */
 697     {
 698       STMT_VINFO_TYPE (stmt_info) = assignment_vec_info_type;
 699       return true;
 700     }
 701
 702   /** Transform.  **/
 703   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 704     fprintf (vect_dump, "transform assignment.");
 705
 706   /* Handle def.  */
 707   vec_dest = vect_create_destination_var (scalar_dest, vectype);
 708
 709   /* Handle use.  */
 710   op = TREE_OPERAND (stmt, 1);
 711   vec_oprnd = vect_get_vec_def_for_operand (op, stmt);
 712
 713   /* Arguments are ready. create the new vector stmt.  */
 714   *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, vec_oprnd);
 715   new_temp = make_ssa_name (vec_dest, *vec_stmt);
 716   TREE_OPERAND (*vec_stmt, 0) = new_temp;
 717   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
 718
 719   return true;
 720 }
 721
 722
 723 /* Function vectorizable_operation.
 724
 725    Check if STMT performs a binary or unary operation that can be vectorized.
 726    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
 727    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
 728    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
 729
 730 bool
 731 vectorizable_operation (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
 732 {
 733   tree vec_dest;
 734   tree scalar_dest;
 735   tree operation;
 736   tree op0, op1 = NULL;
 737   tree vec_oprnd0, vec_oprnd1=NULL;
 738   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 739   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 740   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 741   int i;
 742   enum tree_code code;
 743   enum machine_mode vec_mode;
 744   tree new_temp;
 745   int op_type;
 746   tree op;
 747   optab optab;
 748
 749   /* Is STMT a vectorizable binary/unary operation?   */
 750   if (TREE_CODE (stmt) != MODIFY_EXPR)
 751     return false;
 752
 753   if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
 754     return false;
 755
 756   operation = TREE_OPERAND (stmt, 1);
 757   code = TREE_CODE (operation);
 758   optab = optab_for_tree_code (code, vectype);
 759
 760   /* Support only unary or binary operations.  */
 761   op_type = TREE_CODE_LENGTH (code);
 762   if (op_type != unary_op && op_type != binary_op)
 763     {
 764       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 765         fprintf (vect_dump, "num. args = %d (not unary/binary op).", op_type);
 766       return false;
 767     }
 768
 769   for (i = 0; i < op_type; i++)
 770     {
 771       op = TREE_OPERAND (operation, i);
 772       if (!vect_is_simple_use (op, loop_vinfo, NULL))
 773         {
 774           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 775             fprintf (vect_dump, "use not simple.");
 776           return false;
 777         }
 778     }
 779
 780   /* Supportable by target?  */
 781   if (!optab)
 782     {
 783       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 784         fprintf (vect_dump, "no optab.");
 785       return false;
 786     }
 787   vec_mode = TYPE_MODE (vectype);
 788   if (optab->handlers[(int) vec_mode].insn_code == CODE_FOR_nothing)
 789     {
 790       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 791         fprintf (vect_dump, "op not supported by target.");
 792       return false;
 793     }
 794
 795   if (!vec_stmt) /* transformation not required.  */
 796     {
 797       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
 798       return true;
 799     }
 800
 801   /** Transform.  **/
 802
 803   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 804     fprintf (vect_dump, "transform binary/unary operation.");
 805
 806   /* Handle def.  */
 807   scalar_dest = TREE_OPERAND (stmt, 0);
 808   vec_dest = vect_create_destination_var (scalar_dest, vectype);
 809
 810   /* Handle uses.  */
 811   op0 = TREE_OPERAND (operation, 0);
 812   vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt);
 813
 814   if (op_type == binary_op)
 815     {
 816       op1 = TREE_OPERAND (operation, 1);
 817       vec_oprnd1 = vect_get_vec_def_for_operand (op1, stmt);
 818     }
 819
 820   /* Arguments are ready. create the new vector stmt.  */
 821
 822   if (op_type == binary_op)
 823     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
 824                 build2 (code, vectype, vec_oprnd0, vec_oprnd1));
 825   else
 826     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
 827                 build1 (code, vectype, vec_oprnd0));
 828   new_temp = make_ssa_name (vec_dest, *vec_stmt);
 829   TREE_OPERAND (*vec_stmt, 0) = new_temp;
 830   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
 831
 832   return true;
 833 }
 834
 835
 836 /* Function vectorizable_store.
 837
 838    Check if STMT defines a non scalar data-ref (array/pointer/structure) that
 839    can be vectorized.
 840    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
 841    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
 842    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
 843
 844 bool
 845 vectorizable_store (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
 846 {
 847   tree scalar_dest;
 848   tree data_ref;
 849   tree op;
 850   tree vec_oprnd1;
 851   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 852   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 853   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 854   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 855   enum machine_mode vec_mode;
 856   tree dummy;
 857   enum dr_alignment_support alignment_support_cheme;
 858   ssa_op_iter iter;
 859   tree def;
 860
 861   /* Is vectorizable store? */
 862
 863   if (TREE_CODE (stmt) != MODIFY_EXPR)
 864     return false;
 865
 866   scalar_dest = TREE_OPERAND (stmt, 0);
 867   if (TREE_CODE (scalar_dest) != ARRAY_REF
 868       && TREE_CODE (scalar_dest) != INDIRECT_REF)
 869     return false;
 870
 871   op = TREE_OPERAND (stmt, 1);
 872   if (!vect_is_simple_use (op, loop_vinfo, NULL))
 873     {
 874       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 875         fprintf (vect_dump, "use not simple.");
 876       return false;
 877     }
 878
 879   vec_mode = TYPE_MODE (vectype);
 880   /* FORNOW. In some cases can vectorize even if data-type not supported
 881      (e.g. - array initialization with 0).  */
 882   if (mov_optab->handlers[(int)vec_mode].insn_code == CODE_FOR_nothing)
 883     return false;
 884
 885   if (!STMT_VINFO_DATA_REF (stmt_info))
 886     return false;
 887
 888
 889   if (!vec_stmt) /* transformation not required.  */
 890     {
 891       STMT_VINFO_TYPE (stmt_info) = store_vec_info_type;
 892       return true;
 893     }
 894
 895   /** Transform.  **/
 896
 897   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 898     fprintf (vect_dump, "transform store");
 899
 900   alignment_support_cheme = vect_supportable_dr_alignment (dr);
 901   gcc_assert (alignment_support_cheme);
 902   gcc_assert (alignment_support_cheme == dr_aligned);  /* FORNOW */
 903
 904   /* Handle use - get the vectorized def from the defining stmt.  */
 905   vec_oprnd1 = vect_get_vec_def_for_operand (op, stmt);
 906
 907   /* Handle def.  */
 908   /* FORNOW: make sure the data reference is aligned.  */
 909   vect_align_data_ref (stmt);
 910   data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
 911   data_ref = build_fold_indirect_ref (data_ref);
 912
 913   /* Arguments are ready. create the new vector stmt.  */
 914   *vec_stmt = build2 (MODIFY_EXPR, vectype, data_ref, vec_oprnd1);
 915   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
 916
 917   /* Mark all non-SSA variables in the statement for rewriting.  */
 918   mark_new_vars_to_rename (*vec_stmt);
 919
 920   /* The new vectorized statement will have better aliasing
 921      information, so some of the virtual definitions of the old
 922      statement will likely disappear from the IL.  Mark them to have
 923      their SSA form updated.  */
 924   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
 925     mark_sym_for_renaming (SSA_NAME_VAR (def));
 926
 927   return true;
 928 }
 929
 930
 931 /* vectorizable_load.
 932
 933    Check if STMT reads a non scalar data-ref (array/pointer/structure) that
 934    can be vectorized.
 935    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
 936    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
 937    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
 938
 939 bool
 940 vectorizable_load (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
 941 {
 942   tree scalar_dest;
 943   tree vec_dest = NULL;
 944   tree data_ref = NULL;
 945   tree op;
 946   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 947   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 948   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 949   tree new_temp;
 950   int mode;
 951   tree init_addr;
 952   tree new_stmt;
 953   tree dummy;
 954   basic_block new_bb;
 955   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 956   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 957   edge pe = loop_preheader_edge (loop);
 958   enum dr_alignment_support alignment_support_cheme;
 959
 960   /* Is vectorizable load? */
 961
 962   if (TREE_CODE (stmt) != MODIFY_EXPR)
 963     return false;
 964
 965   scalar_dest = TREE_OPERAND (stmt, 0);
 966   if (TREE_CODE (scalar_dest) != SSA_NAME)
 967     return false;
 968
 969   op = TREE_OPERAND (stmt, 1);
 970   if (TREE_CODE (op) != ARRAY_REF && TREE_CODE (op) != INDIRECT_REF)
 971     return false;
 972
 973   if (!STMT_VINFO_DATA_REF (stmt_info))
 974     return false;
 975
 976   mode = (int) TYPE_MODE (vectype);
 977
 978   /* FORNOW. In some cases can vectorize even if data-type not supported
 979     (e.g. - data copies).  */
 980   if (mov_optab->handlers[mode].insn_code == CODE_FOR_nothing)
 981     {
 982       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
 983         fprintf (vect_dump, "Aligned load, but unsupported type.");
 984       return false;
 985     }
 986
 987   if (!vec_stmt) /* transformation not required.  */
 988     {
 989       STMT_VINFO_TYPE (stmt_info) = load_vec_info_type;
 990       return true;
 991     }
 992
 993   /** Transform.  **/
 994
 995   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 996     fprintf (vect_dump, "transform load.");
 997
 998   alignment_support_cheme = vect_supportable_dr_alignment (dr);
 999   gcc_assert (alignment_support_cheme);
1000
1001   if (alignment_support_cheme == dr_aligned
1002       || alignment_support_cheme == dr_unaligned_supported)
1003     {
1004       /* Create:
1005          p = initial_addr;
1006          indx = 0;
1007          loop {
1008            vec_dest = *(p);
1009            indx = indx + 1;
1010          }
1011       */
1012
1013       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1014       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
1015       if (aligned_access_p (dr))
1016         data_ref = build_fold_indirect_ref (data_ref);
1017       else
1018         {
1019           int mis = DR_MISALIGNMENT (dr);
1020           tree tmis = (mis == -1 ? size_zero_node : size_int (mis));
1021           tmis = size_binop (MULT_EXPR, tmis, size_int(BITS_PER_UNIT));
1022           data_ref = build2 (MISALIGNED_INDIRECT_REF, vectype, data_ref, tmis);
1023         }
1024       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1025       new_temp = make_ssa_name (vec_dest, new_stmt);
1026       TREE_OPERAND (new_stmt, 0) = new_temp;
1027       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1028       copy_virtual_operands (new_stmt, stmt);
1029     }
1030   else if (alignment_support_cheme == dr_unaligned_software_pipeline)
1031     {
1032       /* Create:
1033          p1 = initial_addr;
1034          msq_init = *(floor(p1))
1035          p2 = initial_addr + VS - 1;
1036          magic = have_builtin ? builtin_result : initial_address;
1037          indx = 0;
1038          loop {
1039            p2' = p2 + indx * vectype_size
1040            lsq = *(floor(p2'))
1041            vec_dest = realign_load (msq, lsq, magic)
1042            indx = indx + 1;
1043            msq = lsq;
1044          }
1045       */
1046
1047       tree offset;
1048       tree magic;
1049       tree phi_stmt;
1050       tree msq_init;
1051       tree msq, lsq;
1052       tree dataref_ptr;
1053       tree params;
1054
1055       /* <1> Create msq_init = *(floor(p1)) in the loop preheader  */
1056       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1057       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE,
1058                                            &init_addr, true);
1059       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, data_ref);
1060       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1061       new_temp = make_ssa_name (vec_dest, new_stmt);
1062       TREE_OPERAND (new_stmt, 0) = new_temp;
1063       new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
1064       gcc_assert (!new_bb);
1065       msq_init = TREE_OPERAND (new_stmt, 0);
1066       copy_virtual_operands (new_stmt, stmt);
1067       update_vuses_to_preheader (new_stmt, loop);
1068
1069
1070       /* <2> Create lsq = *(floor(p2')) in the loop  */
1071       offset = build_int_cst (integer_type_node,
1072                               TYPE_VECTOR_SUBPARTS (vectype));
1073       offset = int_const_binop (MINUS_EXPR, offset, integer_one_node, 1);
1074       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1075       dataref_ptr = vect_create_data_ref_ptr (stmt, bsi, offset, &dummy, false);
1076       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, dataref_ptr);
1077       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1078       new_temp = make_ssa_name (vec_dest, new_stmt);
1079       TREE_OPERAND (new_stmt, 0) = new_temp;
1080       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1081       lsq = TREE_OPERAND (new_stmt, 0);
1082       copy_virtual_operands (new_stmt, stmt);
1083
1084
1085       /* <3> */
1086       if (targetm.vectorize.builtin_mask_for_load)
1087         {
1088           /* Create permutation mask, if required, in loop preheader.  */
1089           tree builtin_decl;
1090           params = build_tree_list (NULL_TREE, init_addr);
1091           vec_dest = vect_create_destination_var (scalar_dest, vectype);
1092           builtin_decl = targetm.vectorize.builtin_mask_for_load ();
1093           new_stmt = build_function_call_expr (builtin_decl, params);
1094           new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, new_stmt);
1095           new_temp = make_ssa_name (vec_dest, new_stmt);
1096           TREE_OPERAND (new_stmt, 0) = new_temp;
1097           new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
1098           gcc_assert (!new_bb);
1099           magic = TREE_OPERAND (new_stmt, 0);
1100
1101           /* The result of the CALL_EXPR to this builtin is determined from
1102              the value of the parameter and no global variables are touched
1103              which makes the builtin a "const" function.  Requiring the
1104              builtin to have the "const" attribute makes it unnecessary
1105              to call mark_call_clobbered_vars_to_rename.  */
1106           gcc_assert (TREE_READONLY (builtin_decl));
1107         }
1108       else
1109         {
1110           /* Use current address instead of init_addr for reduced reg pressure.
1111            */
1112           magic = dataref_ptr;
1113         }
1114
1115
1116       /* <4> Create msq = phi <msq_init, lsq> in loop  */
1117       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1118       msq = make_ssa_name (vec_dest, NULL_TREE);
1119       phi_stmt = create_phi_node (msq, loop->header); /* CHECKME */
1120       SSA_NAME_DEF_STMT (msq) = phi_stmt;
1121       add_phi_arg (phi_stmt, msq_init, loop_preheader_edge (loop));
1122       add_phi_arg (phi_stmt, lsq, loop_latch_edge (loop));
1123
1124
1125       /* <5> Create <vec_dest = realign_load (msq, lsq, magic)> in loop  */
1126       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1127       new_stmt = build3 (REALIGN_LOAD_EXPR, vectype, msq, lsq, magic);
1128       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, new_stmt);
1129       new_temp = make_ssa_name (vec_dest, new_stmt);
1130       TREE_OPERAND (new_stmt, 0) = new_temp;
1131       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1132     }
1133   else
1134     gcc_unreachable ();
1135
1136   *vec_stmt = new_stmt;
1137   return true;
1138 }
1139
1140 /* Function vect_is_simple_cond.
1141
1142    Input:
1143    LOOP - the loop that is being vectorized.
1144    COND - Condition that is checked for simple use.
1145
1146    Returns whether a COND can be vectorized.  Checks whether
1147    condition operands are supportable using vec_is_simple_use.  */
1148
1149 static bool
1150 vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
1151 {
1152   tree lhs, rhs;
1153
1154   if (TREE_CODE_CLASS (TREE_CODE (cond)) != tcc_comparison)
1155     return false;
1156
1157   lhs = TREE_OPERAND (cond, 0);
1158   rhs = TREE_OPERAND (cond, 1);
1159
1160   if (TREE_CODE (lhs) == SSA_NAME)
1161     {
1162       tree lhs_def_stmt = SSA_NAME_DEF_STMT (lhs);
1163       if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt))
1164         return false;
1165     }
1166   else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST)
1167     return false;
1168
1169   if (TREE_CODE (rhs) == SSA_NAME)
1170     {
1171       tree rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1172       if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt))
1173         return false;
1174     }
1175   else if (TREE_CODE (rhs) != INTEGER_CST  && TREE_CODE (rhs) != REAL_CST)
1176     return false;
1177
1178   return true;
1179 }
1180
1181 /* vectorizable_condition.
1182
1183    Check if STMT is conditional modify expression that can be vectorized.
1184    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1185    stmt using VEC_COND_EXPR  to replace it, put it in VEC_STMT, and insert it
1186    at BSI.
1187
1188    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1189
1190 bool
1191 vectorizable_condition (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
1192 {
1193   tree scalar_dest = NULL_TREE;
1194   tree vec_dest = NULL_TREE;
1195   tree op = NULL_TREE;
1196   tree cond_expr, then_clause, else_clause;
1197   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1198   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1199   tree vec_cond_lhs, vec_cond_rhs, vec_then_clause, vec_else_clause;
1200   tree vec_compare, vec_cond_expr;
1201   tree new_temp;
1202   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1203   enum machine_mode vec_mode;
1204
1205   if (!STMT_VINFO_RELEVANT_P (stmt_info))
1206     return false;
1207
1208   if (TREE_CODE (stmt) != MODIFY_EXPR)
1209     return false;
1210
1211   op = TREE_OPERAND (stmt, 1);
1212
1213   if (TREE_CODE (op) != COND_EXPR)
1214     return false;
1215
1216   cond_expr = TREE_OPERAND (op, 0);
1217   then_clause = TREE_OPERAND (op, 1);
1218   else_clause = TREE_OPERAND (op, 2);
1219
1220   if (!vect_is_simple_cond (cond_expr, loop_vinfo))
1221     return false;
1222
1223   if (TREE_CODE (then_clause) == SSA_NAME)
1224     {
1225       tree then_def_stmt = SSA_NAME_DEF_STMT (then_clause);
1226       if (!vect_is_simple_use (then_clause, loop_vinfo, &then_def_stmt))
1227         return false;
1228     }
1229   else if (TREE_CODE (then_clause) != INTEGER_CST
1230            && TREE_CODE (then_clause) != REAL_CST)
1231     return false;
1232
1233   if (TREE_CODE (else_clause) == SSA_NAME)
1234     {
1235       tree else_def_stmt = SSA_NAME_DEF_STMT (else_clause);
1236       if (!vect_is_simple_use (else_clause, loop_vinfo, &else_def_stmt))
1237         return false;
1238     }
1239   else if (TREE_CODE (else_clause) != INTEGER_CST
1240            && TREE_CODE (else_clause) != REAL_CST)
1241     return false;
1242
1243
1244   vec_mode = TYPE_MODE (vectype);
1245
1246   if (!vec_stmt)
1247     {
1248       STMT_VINFO_TYPE (stmt_info) = condition_vec_info_type;
1249       return expand_vec_cond_expr_p (op, vec_mode);
1250     }
1251
1252   /* Transform */
1253
1254   /* Handle def.  */
1255   scalar_dest = TREE_OPERAND (stmt, 0);
1256   vec_dest = vect_create_destination_var (scalar_dest, vectype);
1257
1258   /* Handle cond expr.  */
1259   vec_cond_lhs =
1260     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 0), stmt);
1261   vec_cond_rhs =
1262     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 1), stmt);
1263   vec_then_clause = vect_get_vec_def_for_operand (then_clause, stmt);
1264   vec_else_clause = vect_get_vec_def_for_operand (else_clause, stmt);
1265
1266   /* Arguments are ready. create the new vector stmt.  */
1267   vec_compare = build2 (TREE_CODE (cond_expr), vectype,
1268                         vec_cond_lhs, vec_cond_rhs);
1269   vec_cond_expr = build (VEC_COND_EXPR, vectype,
1270                          vec_compare, vec_then_clause, vec_else_clause);
1271
1272   *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, vec_cond_expr);
1273   new_temp = make_ssa_name (vec_dest, *vec_stmt);
1274   TREE_OPERAND (*vec_stmt, 0) = new_temp;
1275   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
1276
1277   return true;
1278 }
1279
1280 /* Function vect_transform_stmt.
1281
1282    Create a vectorized stmt to replace STMT, and insert it at BSI.  */
1283
1284 bool
1285 vect_transform_stmt (tree stmt, block_stmt_iterator *bsi)
1286 {
1287   bool is_store = false;
1288   tree vec_stmt = NULL_TREE;
1289   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1290   bool done;
1291
1292   switch (STMT_VINFO_TYPE (stmt_info))
1293     {
1294     case op_vec_info_type:
1295       done = vectorizable_operation (stmt, bsi, &vec_stmt);
1296       gcc_assert (done);
1297       break;
1298
1299     case assignment_vec_info_type:
1300       done = vectorizable_assignment (stmt, bsi, &vec_stmt);
1301       gcc_assert (done);
1302       break;
1303
1304     case load_vec_info_type:
1305       done = vectorizable_load (stmt, bsi, &vec_stmt);
1306       gcc_assert (done);
1307       break;
1308
1309     case store_vec_info_type:
1310       done = vectorizable_store (stmt, bsi, &vec_stmt);
1311       gcc_assert (done);
1312       is_store = true;
1313       break;
1314
1315     case condition_vec_info_type:
1316       done = vectorizable_condition (stmt, bsi, &vec_stmt);
1317       gcc_assert (done);
1318       break;
1319
1320     default:
1321       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1322         fprintf (vect_dump, "stmt not supported.");
1323       gcc_unreachable ();
1324     }
1325
1326   STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
1327
1328   return is_store;
1329 }
1330
1331
1332 /* This function builds ni_name = number of iterations loop executes
1333    on the loop preheader.  */
1334
1335 static tree
1336 vect_build_loop_niters (loop_vec_info loop_vinfo)
1337 {
1338   tree ni_name, stmt, var;
1339   edge pe;
1340   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1341   tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
1342
1343   var = create_tmp_var (TREE_TYPE (ni), "niters");
1344   add_referenced_tmp_var (var);
1345   ni_name = force_gimple_operand (ni, &stmt, false, var);
1346
1347   pe = loop_preheader_edge (loop);
1348   if (stmt)
1349     {
1350       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1351       gcc_assert (!new_bb);
1352     }
1353
1354   return ni_name;
1355 }
1356
1357
1358 /* This function generates the following statements:
1359
1360  ni_name = number of iterations loop executes
1361  ratio = ni_name / vf
1362  ratio_mult_vf_name = ratio * vf
1363
1364  and places them at the loop preheader edge.  */
1365
1366 static void
1367 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
1368                                  tree *ni_name_ptr,
1369                                  tree *ratio_mult_vf_name_ptr,
1370                                  tree *ratio_name_ptr)
1371 {
1372
1373   edge pe;
1374   basic_block new_bb;
1375   tree stmt, ni_name;
1376   tree var;
1377   tree ratio_name;
1378   tree ratio_mult_vf_name;
1379   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1380   tree ni = LOOP_VINFO_NITERS (loop_vinfo);
1381   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1382   tree log_vf = build_int_cst (unsigned_type_node, exact_log2 (vf));
1383
1384   pe = loop_preheader_edge (loop);
1385
1386   /* Generate temporary variable that contains
1387      number of iterations loop executes.  */
1388
1389   ni_name = vect_build_loop_niters (loop_vinfo);
1390
1391   /* Create: ratio = ni >> log2(vf) */
1392
1393   var = create_tmp_var (TREE_TYPE (ni), "bnd");
1394   add_referenced_tmp_var (var);
1395   ratio_name = make_ssa_name (var, NULL_TREE);
1396   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_name,
1397            build2 (RSHIFT_EXPR, TREE_TYPE (ni_name), ni_name, log_vf));
1398   SSA_NAME_DEF_STMT (ratio_name) = stmt;
1399
1400   pe = loop_preheader_edge (loop);
1401   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1402   gcc_assert (!new_bb);
1403
1404   /* Create: ratio_mult_vf = ratio << log2 (vf).  */
1405
1406   var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
1407   add_referenced_tmp_var (var);
1408   ratio_mult_vf_name = make_ssa_name (var, NULL_TREE);
1409   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_mult_vf_name,
1410            build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name), ratio_name, log_vf));
1411   SSA_NAME_DEF_STMT (ratio_mult_vf_name) = stmt;
1412
1413   pe = loop_preheader_edge (loop);
1414   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1415   gcc_assert (!new_bb);
1416
1417   *ni_name_ptr = ni_name;
1418   *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
1419   *ratio_name_ptr = ratio_name;
1420
1421   return;
1422 }
1423
1424
1425 /* Function update_vuses_to_preheader.
1426
1427    Input:
1428    STMT - a statement with potential VUSEs.
1429    LOOP - the loop whose preheader will contain STMT.
1430
1431    It's possible to vectorize a loop even though an SSA_NAME from a VUSE
1432    appears to be defined in a V_MAY_DEF in another statement in a loop.
1433    One such case is when the VUSE is at the dereference of a __restricted__
1434    pointer in a load and the V_MAY_DEF is at the dereference of a different
1435    __restricted__ pointer in a store.  Vectorization may result in
1436    copy_virtual_uses being called to copy the problematic VUSE to a new
1437    statement that is being inserted in the loop preheader.  This procedure
1438    is called to change the SSA_NAME in the new statement's VUSE from the
1439    SSA_NAME updated in the loop to the related SSA_NAME available on the
1440    path entering the loop.
1441
1442    When this function is called, we have the following situation:
1443
1444         # vuse <name1>
1445         S1: vload
1446     do {
1447         # name1 = phi < name0 , name2>
1448
1449         # vuse <name1>
1450         S2: vload
1451
1452         # name2 = vdef <name1>
1453         S3: vstore
1454
1455     }while...
1456
1457    Stmt S1 was created in the loop preheader block as part of misaligned-load
1458    handling. This function fixes the name of the vuse of S1 from 'name1' to
1459    'name0'.  */
1460
1461 static void
1462 update_vuses_to_preheader (tree stmt, struct loop *loop)
1463 {
1464   basic_block header_bb = loop->header;
1465   edge preheader_e = loop_preheader_edge (loop);
1466   vuse_optype vuses = STMT_VUSE_OPS (stmt);
1467   int nvuses = NUM_VUSES (vuses);
1468   int i;
1469
1470   for (i = 0; i < nvuses; i++)
1471     {
1472       tree ssa_name = VUSE_OP (vuses, i);
1473       tree def_stmt = SSA_NAME_DEF_STMT (ssa_name);
1474       tree name_var = SSA_NAME_VAR (ssa_name);
1475       basic_block bb = bb_for_stmt (def_stmt);
1476
1477       /* For a use before any definitions, def_stmt is a NOP_EXPR.  */
1478       if (!IS_EMPTY_STMT (def_stmt)
1479           && flow_bb_inside_loop_p (loop, bb))
1480         {
1481           /* If the block containing the statement defining the SSA_NAME
1482              is in the loop then it's necessary to find the definition
1483              outside the loop using the PHI nodes of the header.  */
1484           tree phi;
1485           bool updated = false;
1486
1487           for (phi = phi_nodes (header_bb); phi; phi = TREE_CHAIN (phi))
1488             {
1489               if (SSA_NAME_VAR (PHI_RESULT (phi)) == name_var)
1490                 {
1491                   SET_VUSE_OP (vuses, i,
1492                                PHI_ARG_DEF (phi, preheader_e->dest_idx));
1493                   updated = true;
1494                   break;
1495                 }
1496             }
1497           gcc_assert (updated);
1498         }
1499     }
1500 }
1501
1502
1503 /*   Function vect_update_ivs_after_vectorizer.
1504
1505      "Advance" the induction variables of LOOP to the value they should take
1506      after the execution of LOOP.  This is currently necessary because the
1507      vectorizer does not handle induction variables that are used after the
1508      loop.  Such a situation occurs when the last iterations of LOOP are
1509      peeled, because:
1510      1. We introduced new uses after LOOP for IVs that were not originally used
1511         after LOOP: the IVs of LOOP are now used by an epilog loop.
1512      2. LOOP is going to be vectorized; this means that it will iterate N/VF
1513         times, whereas the loop IVs should be bumped N times.
1514
1515      Input:
1516      - LOOP - a loop that is going to be vectorized. The last few iterations
1517               of LOOP were peeled.
1518      - NITERS - the number of iterations that LOOP executes (before it is
1519                 vectorized). i.e, the number of times the ivs should be bumped.
1520      - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
1521                   coming out from LOOP on which there are uses of the LOOP ivs
1522                   (this is the path from LOOP->exit to epilog_loop->preheader).
1523
1524                   The new definitions of the ivs are placed in LOOP->exit.
1525                   The phi args associated with the edge UPDATE_E in the bb
1526                   UPDATE_E->dest are updated accordingly.
1527
1528      Assumption 1: Like the rest of the vectorizer, this function assumes
1529      a single loop exit that has a single predecessor.
1530
1531      Assumption 2: The phi nodes in the LOOP header and in update_bb are
1532      organized in the same order.
1533
1534      Assumption 3: The access function of the ivs is simple enough (see
1535      vect_can_advance_ivs_p).  This assumption will be relaxed in the future.
1536
1537      Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
1538      coming out of LOOP on which the ivs of LOOP are used (this is the path
1539      that leads to the epilog loop; other paths skip the epilog loop).  This
1540      path starts with the edge UPDATE_E, and its destination (denoted update_bb)
1541      needs to have its phis updated.
1542  */
1543
1544 static void
1545 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
1546                                   edge update_e)
1547 {
1548   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1549   basic_block exit_bb = loop->single_exit->dest;
1550   tree phi, phi1;
1551   basic_block update_bb = update_e->dest;
1552
1553   /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
1554
1555   /* Make sure there exists a single-predecessor exit bb:  */
1556   gcc_assert (single_pred_p (exit_bb));
1557
1558   for (phi = phi_nodes (loop->header), phi1 = phi_nodes (update_bb);
1559        phi && phi1;
1560        phi = PHI_CHAIN (phi), phi1 = PHI_CHAIN (phi1))
1561     {
1562       tree access_fn = NULL;
1563       tree evolution_part;
1564       tree init_expr;
1565       tree step_expr;
1566       tree var, stmt, ni, ni_name;
1567       block_stmt_iterator last_bsi;
1568
1569       /* Skip virtual phi's.  */
1570       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1571         {
1572           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1573             fprintf (vect_dump, "virtual phi. skip.");
1574           continue;
1575         }
1576
1577       access_fn = analyze_scalar_evolution (loop, PHI_RESULT (phi));
1578       gcc_assert (access_fn);
1579       evolution_part =
1580          unshare_expr (evolution_part_in_loop_num (access_fn, loop->num));
1581       gcc_assert (evolution_part != NULL_TREE);
1582
1583       /* FORNOW: We do not support IVs whose evolution function is a polynomial
1584          of degree >= 2 or exponential.  */
1585       gcc_assert (!tree_is_chrec (evolution_part));
1586
1587       step_expr = evolution_part;
1588       init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
1589                                                                loop->num));
1590
1591       ni = build2 (PLUS_EXPR, TREE_TYPE (init_expr),
1592                   build2 (MULT_EXPR, TREE_TYPE (niters),
1593                        niters, step_expr), init_expr);
1594
1595       var = create_tmp_var (TREE_TYPE (init_expr), "tmp");
1596       add_referenced_tmp_var (var);
1597
1598       ni_name = force_gimple_operand (ni, &stmt, false, var);
1599
1600       /* Insert stmt into exit_bb.  */
1601       last_bsi = bsi_last (exit_bb);
1602       if (stmt)
1603         bsi_insert_before (&last_bsi, stmt, BSI_SAME_STMT);
1604
1605       /* Fix phi expressions in the successor bb.  */
1606       SET_PHI_ARG_DEF (phi1, update_e->dest_idx, ni_name);
1607     }
1608 }
1609
1610
1611 /* Function vect_do_peeling_for_loop_bound
1612
1613    Peel the last iterations of the loop represented by LOOP_VINFO.
1614    The peeled iterations form a new epilog loop.  Given that the loop now
1615    iterates NITERS times, the new epilog loop iterates
1616    NITERS % VECTORIZATION_FACTOR times.
1617
1618    The original loop will later be made to iterate
1619    NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).  */
1620
1621 static void
1622 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
1623                                 struct loops *loops)
1624 {
1625
1626   tree ni_name, ratio_mult_vf_name;
1627   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1628   struct loop *new_loop;
1629   edge update_e;
1630   basic_block preheader;
1631 #ifdef ENABLE_CHECKING
1632   int loop_num;
1633 #endif
1634
1635   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1636     fprintf (vect_dump, "=== vect_transtorm_for_unknown_loop_bound ===");
1637
1638   /* Generate the following variables on the preheader of original loop:
1639
1640      ni_name = number of iteration the original loop executes
1641      ratio = ni_name / vf
1642      ratio_mult_vf_name = ratio * vf  */
1643   vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
1644                                    &ratio_mult_vf_name, ratio);
1645
1646 #ifdef ENABLE_CHECKING
1647   loop_num  = loop->num;
1648 #endif
1649   new_loop = slpeel_tree_peel_loop_to_edge (loop, loops, loop->single_exit,
1650                                             ratio_mult_vf_name, ni_name, false);
1651 #ifdef ENABLE_CHECKING
1652   gcc_assert (new_loop);
1653   gcc_assert (loop_num == loop->num);
1654   slpeel_verify_cfg_after_peeling (loop, new_loop);
1655 #endif
1656
1657   /* A guard that controls whether the new_loop is to be executed or skipped
1658      is placed in LOOP->exit.  LOOP->exit therefore has two successors - one
1659      is the preheader of NEW_LOOP, where the IVs from LOOP are used.  The other
1660      is a bb after NEW_LOOP, where these IVs are not used.  Find the edge that
1661      is on the path where the LOOP IVs are used and need to be updated.  */
1662
1663   preheader = loop_preheader_edge (new_loop)->src;
1664   if (EDGE_PRED (preheader, 0)->src == loop->single_exit->dest)
1665     update_e = EDGE_PRED (preheader, 0);
1666   else
1667     update_e = EDGE_PRED (preheader, 1);
1668
1669   /* Update IVs of original loop as if they were advanced
1670      by ratio_mult_vf_name steps.  */
1671   vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
1672
1673   /* After peeling we have to reset scalar evolution analyzer.  */
1674   scev_reset ();
1675
1676   return;
1677 }
1678
1679
1680 /* Function vect_gen_niters_for_prolog_loop
1681
1682    Set the number of iterations for the loop represented by LOOP_VINFO
1683    to the minimum between LOOP_NITERS (the original iteration count of the loop)
1684    and the misalignment of DR - the data reference recorded in
1685    LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO).  As a result, after the execution of
1686    this loop, the data reference DR will refer to an aligned location.
1687
1688    The following computation is generated:
1689
1690    If the misalignment of DR is known at compile time:
1691      addr_mis = int mis = DR_MISALIGNMENT (dr);
1692    Else, compute address misalignment in bytes:
1693      addr_mis = addr & (vectype_size - 1)
1694
1695    prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
1696
1697    (elem_size = element type size; an element is the scalar element
1698         whose type is the inner type of the vectype)  */
1699
1700 static tree
1701 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
1702 {
1703   struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
1704   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1705   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1706   tree var, stmt;
1707   tree iters, iters_name;
1708   edge pe;
1709   basic_block new_bb;
1710   tree dr_stmt = DR_STMT (dr);
1711   stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
1712   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1713   int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
1714   tree vf_minus_1 = build_int_cst (unsigned_type_node, vf - 1);
1715   tree niters_type = TREE_TYPE (loop_niters);
1716
1717   pe = loop_preheader_edge (loop);
1718
1719   if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
1720     {
1721       int byte_misalign = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
1722       int element_size = vectype_align/vf;
1723       int elem_misalign = byte_misalign / element_size;
1724
1725       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1726         fprintf (vect_dump, "known alignment = %d.", byte_misalign);
1727       iters = build_int_cst (niters_type, (vf - elem_misalign)&(vf-1));
1728     }
1729   else
1730     {
1731       tree new_stmts = NULL_TREE;
1732       tree start_addr =
1733         vect_create_addr_base_for_vector_ref (dr_stmt, &new_stmts, NULL_TREE);
1734       tree ptr_type = TREE_TYPE (start_addr);
1735       tree size = TYPE_SIZE (ptr_type);
1736       tree type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
1737       tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
1738       tree elem_size_log =
1739         build_int_cst (unsigned_type_node, exact_log2 (vectype_align/vf));
1740       tree vf_tree = build_int_cst (unsigned_type_node, vf);
1741       tree byte_misalign;
1742       tree elem_misalign;
1743
1744       new_bb = bsi_insert_on_edge_immediate (pe, new_stmts);
1745       gcc_assert (!new_bb);
1746
1747       /* Create:  byte_misalign = addr & (vectype_size - 1)  */
1748       byte_misalign =
1749         build2 (BIT_AND_EXPR, type, start_addr, vectype_size_minus_1);
1750
1751       /* Create:  elem_misalign = byte_misalign / element_size  */
1752       elem_misalign =
1753         build2 (RSHIFT_EXPR, unsigned_type_node, byte_misalign, elem_size_log);
1754
1755       /* Create:  (niters_type) (VF - elem_misalign)&(VF - 1)  */
1756       iters = build2 (MINUS_EXPR, unsigned_type_node, vf_tree, elem_misalign);
1757       iters = build2 (BIT_AND_EXPR, unsigned_type_node, iters, vf_minus_1);
1758       iters = fold_convert (niters_type, iters);
1759     }
1760
1761   /* Create:  prolog_loop_niters = min (iters, loop_niters) */
1762   /* If the loop bound is known at compile time we already verified that it is
1763      greater than vf; since the misalignment ('iters') is at most vf, there's
1764      no need to generate the MIN_EXPR in this case.  */
1765   if (TREE_CODE (loop_niters) != INTEGER_CST)
1766     iters = build2 (MIN_EXPR, niters_type, iters, loop_niters);
1767
1768   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1769     {
1770       fprintf (vect_dump, "niters for prolog loop: ");
1771       print_generic_expr (vect_dump, iters, TDF_SLIM);
1772     }
1773
1774   var = create_tmp_var (niters_type, "prolog_loop_niters");
1775   add_referenced_tmp_var (var);
1776   iters_name = force_gimple_operand (iters, &stmt, false, var);
1777
1778   /* Insert stmt on loop preheader edge.  */
1779   if (stmt)
1780     {
1781       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1782       gcc_assert (!new_bb);
1783     }
1784
1785   return iters_name;
1786 }
1787
1788
1789 /* Function vect_update_init_of_dr
1790
1791    NITERS iterations were peeled from LOOP.  DR represents a data reference
1792    in LOOP.  This function updates the information recorded in DR to
1793    account for the fact that the first NITERS iterations had already been
1794    executed.  Specifically, it updates the OFFSET field of stmt_info.  */
1795
1796 static void
1797 vect_update_init_of_dr (struct data_reference *dr, tree niters)
1798 {
1799   stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
1800   tree offset = STMT_VINFO_VECT_INIT_OFFSET (stmt_info);
1801
1802   niters = fold (build2 (MULT_EXPR, TREE_TYPE (niters), niters,
1803                          STMT_VINFO_VECT_STEP (stmt_info)));
1804   offset = fold (build2 (PLUS_EXPR, TREE_TYPE (offset), offset, niters));
1805   STMT_VINFO_VECT_INIT_OFFSET (stmt_info) = offset;
1806 }
1807
1808
1809 /* Function vect_update_inits_of_drs
1810
1811    NITERS iterations were peeled from the loop represented by LOOP_VINFO.
1812    This function updates the information recorded for the data references in
1813    the loop to account for the fact that the first NITERS iterations had
1814    already been executed.  Specifically, it updates the initial_condition of the
1815    access_function of all the data_references in the loop.  */
1816
1817 static void
1818 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
1819 {
1820   unsigned int i;
1821   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1822   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1823
1824   if (vect_dump && (dump_flags & TDF_DETAILS))
1825     fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
1826
1827   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1828     {
1829       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1830       vect_update_init_of_dr (dr, niters);
1831     }
1832
1833   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1834     {
1835       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1836       vect_update_init_of_dr (dr, niters);
1837     }
1838 }
1839
1840
1841 /* Function vect_do_peeling_for_alignment
1842
1843    Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
1844    'niters' is set to the misalignment of one of the data references in the
1845    loop, thereby forcing it to refer to an aligned location at the beginning
1846    of the execution of this loop.  The data reference for which we are
1847    peeling is recorded in LOOP_VINFO_UNALIGNED_DR.  */
1848
1849 static void
1850 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo, struct loops *loops)
1851 {
1852   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1853   tree niters_of_prolog_loop, ni_name;
1854   tree n_iters;
1855   struct loop *new_loop;
1856
1857   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1858     fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
1859
1860   ni_name = vect_build_loop_niters (loop_vinfo);
1861   niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, ni_name);
1862
1863   /* Peel the prolog loop and iterate it niters_of_prolog_loop.  */
1864   new_loop =
1865         slpeel_tree_peel_loop_to_edge (loop, loops, loop_preheader_edge (loop),
1866                                        niters_of_prolog_loop, ni_name, true);
1867 #ifdef ENABLE_CHECKING
1868   gcc_assert (new_loop);
1869   slpeel_verify_cfg_after_peeling (new_loop, loop);
1870 #endif
1871
1872   /* Update number of times loop executes.  */
1873   n_iters = LOOP_VINFO_NITERS (loop_vinfo);
1874   LOOP_VINFO_NITERS (loop_vinfo) = fold (build2 (MINUS_EXPR,
1875                 TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop));
1876
1877   /* Update the init conditions of the access functions of all data refs.  */
1878   vect_update_inits_of_drs (loop_vinfo, niters_of_prolog_loop);
1879
1880   /* After peeling we have to reset scalar evolution analyzer.  */
1881   scev_reset ();
1882
1883   return;
1884 }
1885
1886
1887 /* Function vect_transform_loop.
1888
1889    The analysis phase has determined that the loop is vectorizable.
1890    Vectorize the loop - created vectorized stmts to replace the scalar
1891    stmts in the loop, and update the loop exit condition.  */
1892
1893 void
1894 vect_transform_loop (loop_vec_info loop_vinfo,
1895                      struct loops *loops ATTRIBUTE_UNUSED)
1896 {
1897   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1898   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1899   int nbbs = loop->num_nodes;
1900   block_stmt_iterator si;
1901   int i;
1902   tree ratio = NULL;
1903   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1904
1905   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1906     fprintf (vect_dump, "=== vec_transform_loop ===");
1907
1908
1909   /* Peel the loop if there are data refs with unknown alignment.
1910      Only one data ref with unknown store is allowed.  */
1911
1912   if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
1913     vect_do_peeling_for_alignment (loop_vinfo, loops);
1914
1915   /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
1916      compile time constant), or it is a constant that doesn't divide by the
1917      vectorization factor, then an epilog loop needs to be created.
1918      We therefore duplicate the loop: the original loop will be vectorized,
1919      and will compute the first (n/VF) iterations. The second copy of the loop
1920      will remain scalar and will compute the remaining (n%VF) iterations.
1921      (VF is the vectorization factor).  */
1922
1923   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1924       || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1925           && LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0))
1926     vect_do_peeling_for_loop_bound (loop_vinfo, &ratio, loops);
1927   else
1928     ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
1929                 LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
1930
1931   /* 1) Make sure the loop header has exactly two entries
1932      2) Make sure we have a preheader basic block.  */
1933
1934   gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
1935
1936   loop_split_edge_with (loop_preheader_edge (loop), NULL);
1937
1938
1939   /* FORNOW: the vectorizer supports only loops which body consist
1940      of one basic block (header + empty latch). When the vectorizer will
1941      support more involved loop forms, the order by which the BBs are
1942      traversed need to be reconsidered.  */
1943
1944   for (i = 0; i < nbbs; i++)
1945     {
1946       basic_block bb = bbs[i];
1947
1948       for (si = bsi_start (bb); !bsi_end_p (si);)
1949         {
1950           tree stmt = bsi_stmt (si);
1951           stmt_vec_info stmt_info;
1952           bool is_store;
1953
1954           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1955             {
1956               fprintf (vect_dump, "------>vectorizing statement: ");
1957               print_generic_expr (vect_dump, stmt, TDF_SLIM);
1958             }
1959           stmt_info = vinfo_for_stmt (stmt);
1960           gcc_assert (stmt_info);
1961           if (!STMT_VINFO_RELEVANT_P (stmt_info))
1962             {
1963               bsi_next (&si);
1964               continue;
1965             }
1966 #ifdef ENABLE_CHECKING
1967           /* FORNOW: Verify that all stmts operate on the same number of
1968                      units and no inner unrolling is necessary.  */
1969           gcc_assert
1970                 (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
1971                  == vectorization_factor);
1972 #endif
1973           /* -------- vectorize statement ------------ */
1974           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1975             fprintf (vect_dump, "transform statement.");
1976
1977           is_store = vect_transform_stmt (stmt, &si);
1978           if (is_store)
1979             {
1980               /* Free the attached stmt_vec_info and remove the stmt.  */
1981               stmt_ann_t ann = stmt_ann (stmt);
1982               free (stmt_info);
1983               set_stmt_info (ann, NULL);
1984               bsi_remove (&si);
1985               continue;
1986             }
1987
1988           bsi_next (&si);
1989         }                       /* stmts in BB */
1990     }                           /* BBs in loop */
1991
1992   slpeel_make_loop_iterate_ntimes (loop, ratio);
1993
1994   if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS, LOOP_LOC (loop_vinfo)))
1995     fprintf (vect_dump, "LOOP VECTORIZED.");
1996 }