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 misalignment 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 vect_min_worthwhile_factor.
 724
 725    For a loop where we could vectorize the operation indicated by CODE,
 726    return the minimum vectorization factor that makes it worthwhile
 727    to use generic vectors.  */
 728 static int
 729 vect_min_worthwhile_factor (enum tree_code code)
 730 {
 731   switch (code)
 732     {
 733     case PLUS_EXPR:
 734     case MINUS_EXPR:
 735     case NEGATE_EXPR:
 736       return 4;
 737
 738     case BIT_AND_EXPR:
 739     case BIT_IOR_EXPR:
 740     case BIT_XOR_EXPR:
 741     case BIT_NOT_EXPR:
 742       return 2;
 743
 744     default:
 745       return INT_MAX;
 746     }
 747 }
 748
 749 /* Function vectorizable_operation.
 750
 751    Check if STMT performs a binary or unary operation that can be vectorized.
 752    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
 753    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
 754    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
 755
 756 bool
 757 vectorizable_operation (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
 758 {
 759   tree vec_dest;
 760   tree scalar_dest;
 761   tree operation;
 762   tree op0, op1 = NULL;
 763   tree vec_oprnd0, vec_oprnd1=NULL;
 764   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 765   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 766   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 767   int i;
 768   enum tree_code code;
 769   enum machine_mode vec_mode;
 770   tree new_temp;
 771   int op_type;
 772   tree op;
 773   optab optab;
 774
 775   /* Is STMT a vectorizable binary/unary operation?   */
 776   if (TREE_CODE (stmt) != MODIFY_EXPR)
 777     return false;
 778
 779   if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
 780     return false;
 781
 782   operation = TREE_OPERAND (stmt, 1);
 783   code = TREE_CODE (operation);
 784   optab = optab_for_tree_code (code, vectype);
 785
 786   /* Support only unary or binary operations.  */
 787   op_type = TREE_CODE_LENGTH (code);
 788   if (op_type != unary_op && op_type != binary_op)
 789     {
 790       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 791         fprintf (vect_dump, "num. args = %d (not unary/binary op).", op_type);
 792       return false;
 793     }
 794
 795   for (i = 0; i < op_type; i++)
 796     {
 797       op = TREE_OPERAND (operation, i);
 798       if (!vect_is_simple_use (op, loop_vinfo, NULL))
 799         {
 800           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 801             fprintf (vect_dump, "use not simple.");
 802           return false;
 803         }
 804     }
 805
 806   /* Supportable by target?  */
 807   if (!optab)
 808     {
 809       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 810         fprintf (vect_dump, "no optab.");
 811       return false;
 812     }
 813   vec_mode = TYPE_MODE (vectype);
 814   if (optab->handlers[(int) vec_mode].insn_code == CODE_FOR_nothing)
 815     {
 816       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 817         fprintf (vect_dump, "op not supported by target.");
 818       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
 819           || LOOP_VINFO_VECT_FACTOR (loop_vinfo)
 820              < vect_min_worthwhile_factor (code))
 821         return false;
 822       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 823         fprintf (vect_dump, "proceeding using word mode.");
 824     }
 825
 826   /* Worthwhile without SIMD support?  */
 827   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
 828       && LOOP_VINFO_VECT_FACTOR (loop_vinfo)
 829          < vect_min_worthwhile_factor (code))
 830     {
 831       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 832         fprintf (vect_dump, "not worthwhile without SIMD support.");
 833       return false;
 834     }
 835
 836   if (!vec_stmt) /* transformation not required.  */
 837     {
 838       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
 839       return true;
 840     }
 841
 842   /** Transform.  **/
 843
 844   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 845     fprintf (vect_dump, "transform binary/unary operation.");
 846
 847   /* Handle def.  */
 848   scalar_dest = TREE_OPERAND (stmt, 0);
 849   vec_dest = vect_create_destination_var (scalar_dest, vectype);
 850
 851   /* Handle uses.  */
 852   op0 = TREE_OPERAND (operation, 0);
 853   vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt);
 854
 855   if (op_type == binary_op)
 856     {
 857       op1 = TREE_OPERAND (operation, 1);
 858       vec_oprnd1 = vect_get_vec_def_for_operand (op1, stmt);
 859     }
 860
 861   /* Arguments are ready. create the new vector stmt.  */
 862
 863   if (op_type == binary_op)
 864     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
 865                 build2 (code, vectype, vec_oprnd0, vec_oprnd1));
 866   else
 867     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
 868                 build1 (code, vectype, vec_oprnd0));
 869   new_temp = make_ssa_name (vec_dest, *vec_stmt);
 870   TREE_OPERAND (*vec_stmt, 0) = new_temp;
 871   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
 872
 873   return true;
 874 }
 875
 876
 877 /* Function vectorizable_store.
 878
 879    Check if STMT defines a non scalar data-ref (array/pointer/structure) that
 880    can be vectorized.
 881    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
 882    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
 883    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
 884
 885 bool
 886 vectorizable_store (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
 887 {
 888   tree scalar_dest;
 889   tree data_ref;
 890   tree op;
 891   tree vec_oprnd1;
 892   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 893   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 894   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 895   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 896   enum machine_mode vec_mode;
 897   tree dummy;
 898   enum dr_alignment_support alignment_support_cheme;
 899   ssa_op_iter iter;
 900   tree def;
 901
 902   /* Is vectorizable store? */
 903
 904   if (TREE_CODE (stmt) != MODIFY_EXPR)
 905     return false;
 906
 907   scalar_dest = TREE_OPERAND (stmt, 0);
 908   if (TREE_CODE (scalar_dest) != ARRAY_REF
 909       && TREE_CODE (scalar_dest) != INDIRECT_REF)
 910     return false;
 911
 912   op = TREE_OPERAND (stmt, 1);
 913   if (!vect_is_simple_use (op, loop_vinfo, NULL))
 914     {
 915       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 916         fprintf (vect_dump, "use not simple.");
 917       return false;
 918     }
 919
 920   vec_mode = TYPE_MODE (vectype);
 921   /* FORNOW. In some cases can vectorize even if data-type not supported
 922      (e.g. - array initialization with 0).  */
 923   if (mov_optab->handlers[(int)vec_mode].insn_code == CODE_FOR_nothing)
 924     return false;
 925
 926   if (!STMT_VINFO_DATA_REF (stmt_info))
 927     return false;
 928
 929
 930   if (!vec_stmt) /* transformation not required.  */
 931     {
 932       STMT_VINFO_TYPE (stmt_info) = store_vec_info_type;
 933       return true;
 934     }
 935
 936   /** Transform.  **/
 937
 938   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
 939     fprintf (vect_dump, "transform store");
 940
 941   alignment_support_cheme = vect_supportable_dr_alignment (dr);
 942   gcc_assert (alignment_support_cheme);
 943   gcc_assert (alignment_support_cheme == dr_aligned);  /* FORNOW */
 944
 945   /* Handle use - get the vectorized def from the defining stmt.  */
 946   vec_oprnd1 = vect_get_vec_def_for_operand (op, stmt);
 947
 948   /* Handle def.  */
 949   /* FORNOW: make sure the data reference is aligned.  */
 950   vect_align_data_ref (stmt);
 951   data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
 952   data_ref = build_fold_indirect_ref (data_ref);
 953
 954   /* Arguments are ready. create the new vector stmt.  */
 955   *vec_stmt = build2 (MODIFY_EXPR, vectype, data_ref, vec_oprnd1);
 956   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
 957
 958   /* Mark all non-SSA variables in the statement for rewriting.  */
 959   mark_new_vars_to_rename (*vec_stmt);
 960
 961   /* The new vectorized statement will have better aliasing
 962      information, so some of the virtual definitions of the old
 963      statement will likely disappear from the IL.  Mark them to have
 964      their SSA form updated.  */
 965   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_VMAYDEF)
 966     mark_sym_for_renaming (SSA_NAME_VAR (def));
 967
 968   return true;
 969 }
 970
 971
 972 /* vectorizable_load.
 973
 974    Check if STMT reads a non scalar data-ref (array/pointer/structure) that
 975    can be vectorized.
 976    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
 977    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
 978    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
 979
 980 bool
 981 vectorizable_load (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
 982 {
 983   tree scalar_dest;
 984   tree vec_dest = NULL;
 985   tree data_ref = NULL;
 986   tree op;
 987   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 988   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
 989   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 990   tree new_temp;
 991   int mode;
 992   tree init_addr;
 993   tree new_stmt;
 994   tree dummy;
 995   basic_block new_bb;
 996   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
 997   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 998   edge pe = loop_preheader_edge (loop);
 999   enum dr_alignment_support alignment_support_cheme;
1000
1001   /* Is vectorizable load? */
1002
1003   if (TREE_CODE (stmt) != MODIFY_EXPR)
1004     return false;
1005
1006   scalar_dest = TREE_OPERAND (stmt, 0);
1007   if (TREE_CODE (scalar_dest) != SSA_NAME)
1008     return false;
1009
1010   op = TREE_OPERAND (stmt, 1);
1011   if (TREE_CODE (op) != ARRAY_REF && TREE_CODE (op) != INDIRECT_REF)
1012     return false;
1013
1014   if (!STMT_VINFO_DATA_REF (stmt_info))
1015     return false;
1016
1017   mode = (int) TYPE_MODE (vectype);
1018
1019   /* FORNOW. In some cases can vectorize even if data-type not supported
1020     (e.g. - data copies).  */
1021   if (mov_optab->handlers[mode].insn_code == CODE_FOR_nothing)
1022     {
1023       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
1024         fprintf (vect_dump, "Aligned load, but unsupported type.");
1025       return false;
1026     }
1027
1028   if (!vec_stmt) /* transformation not required.  */
1029     {
1030       STMT_VINFO_TYPE (stmt_info) = load_vec_info_type;
1031       return true;
1032     }
1033
1034   /** Transform.  **/
1035
1036   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1037     fprintf (vect_dump, "transform load.");
1038
1039   alignment_support_cheme = vect_supportable_dr_alignment (dr);
1040   gcc_assert (alignment_support_cheme);
1041
1042   if (alignment_support_cheme == dr_aligned
1043       || alignment_support_cheme == dr_unaligned_supported)
1044     {
1045       /* Create:
1046          p = initial_addr;
1047          indx = 0;
1048          loop {
1049            vec_dest = *(p);
1050            indx = indx + 1;
1051          }
1052       */
1053
1054       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1055       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
1056       if (aligned_access_p (dr))
1057         data_ref = build_fold_indirect_ref (data_ref);
1058       else
1059         {
1060           int mis = DR_MISALIGNMENT (dr);
1061           tree tmis = (mis == -1 ? size_zero_node : size_int (mis));
1062           tmis = size_binop (MULT_EXPR, tmis, size_int(BITS_PER_UNIT));
1063           data_ref = build2 (MISALIGNED_INDIRECT_REF, vectype, data_ref, tmis);
1064         }
1065       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1066       new_temp = make_ssa_name (vec_dest, new_stmt);
1067       TREE_OPERAND (new_stmt, 0) = new_temp;
1068       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1069       copy_virtual_operands (new_stmt, stmt);
1070     }
1071   else if (alignment_support_cheme == dr_unaligned_software_pipeline)
1072     {
1073       /* Create:
1074          p1 = initial_addr;
1075          msq_init = *(floor(p1))
1076          p2 = initial_addr + VS - 1;
1077          magic = have_builtin ? builtin_result : initial_address;
1078          indx = 0;
1079          loop {
1080            p2' = p2 + indx * vectype_size
1081            lsq = *(floor(p2'))
1082            vec_dest = realign_load (msq, lsq, magic)
1083            indx = indx + 1;
1084            msq = lsq;
1085          }
1086       */
1087
1088       tree offset;
1089       tree magic;
1090       tree phi_stmt;
1091       tree msq_init;
1092       tree msq, lsq;
1093       tree dataref_ptr;
1094       tree params;
1095
1096       /* <1> Create msq_init = *(floor(p1)) in the loop preheader  */
1097       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1098       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE,
1099                                            &init_addr, true);
1100       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, data_ref);
1101       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1102       new_temp = make_ssa_name (vec_dest, new_stmt);
1103       TREE_OPERAND (new_stmt, 0) = new_temp;
1104       new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
1105       gcc_assert (!new_bb);
1106       msq_init = TREE_OPERAND (new_stmt, 0);
1107       copy_virtual_operands (new_stmt, stmt);
1108       update_vuses_to_preheader (new_stmt, loop);
1109
1110
1111       /* <2> Create lsq = *(floor(p2')) in the loop  */
1112       offset = build_int_cst (integer_type_node,
1113                               TYPE_VECTOR_SUBPARTS (vectype));
1114       offset = int_const_binop (MINUS_EXPR, offset, integer_one_node, 1);
1115       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1116       dataref_ptr = vect_create_data_ref_ptr (stmt, bsi, offset, &dummy, false);
1117       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, dataref_ptr);
1118       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
1119       new_temp = make_ssa_name (vec_dest, new_stmt);
1120       TREE_OPERAND (new_stmt, 0) = new_temp;
1121       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1122       lsq = TREE_OPERAND (new_stmt, 0);
1123       copy_virtual_operands (new_stmt, stmt);
1124
1125
1126       /* <3> */
1127       if (targetm.vectorize.builtin_mask_for_load)
1128         {
1129           /* Create permutation mask, if required, in loop preheader.  */
1130           tree builtin_decl;
1131           params = build_tree_list (NULL_TREE, init_addr);
1132           vec_dest = vect_create_destination_var (scalar_dest, vectype);
1133           builtin_decl = targetm.vectorize.builtin_mask_for_load ();
1134           new_stmt = build_function_call_expr (builtin_decl, params);
1135           new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, new_stmt);
1136           new_temp = make_ssa_name (vec_dest, new_stmt);
1137           TREE_OPERAND (new_stmt, 0) = new_temp;
1138           new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
1139           gcc_assert (!new_bb);
1140           magic = TREE_OPERAND (new_stmt, 0);
1141
1142           /* The result of the CALL_EXPR to this builtin is determined from
1143              the value of the parameter and no global variables are touched
1144              which makes the builtin a "const" function.  Requiring the
1145              builtin to have the "const" attribute makes it unnecessary
1146              to call mark_call_clobbered_vars_to_rename.  */
1147           gcc_assert (TREE_READONLY (builtin_decl));
1148         }
1149       else
1150         {
1151           /* Use current address instead of init_addr for reduced reg pressure.
1152            */
1153           magic = dataref_ptr;
1154         }
1155
1156
1157       /* <4> Create msq = phi <msq_init, lsq> in loop  */
1158       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1159       msq = make_ssa_name (vec_dest, NULL_TREE);
1160       phi_stmt = create_phi_node (msq, loop->header); /* CHECKME */
1161       SSA_NAME_DEF_STMT (msq) = phi_stmt;
1162       add_phi_arg (phi_stmt, msq_init, loop_preheader_edge (loop));
1163       add_phi_arg (phi_stmt, lsq, loop_latch_edge (loop));
1164
1165
1166       /* <5> Create <vec_dest = realign_load (msq, lsq, magic)> in loop  */
1167       vec_dest = vect_create_destination_var (scalar_dest, vectype);
1168       new_stmt = build3 (REALIGN_LOAD_EXPR, vectype, msq, lsq, magic);
1169       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, new_stmt);
1170       new_temp = make_ssa_name (vec_dest, new_stmt);
1171       TREE_OPERAND (new_stmt, 0) = new_temp;
1172       vect_finish_stmt_generation (stmt, new_stmt, bsi);
1173     }
1174   else
1175     gcc_unreachable ();
1176
1177   *vec_stmt = new_stmt;
1178   return true;
1179 }
1180
1181 /* Function vect_is_simple_cond.
1182
1183    Input:
1184    LOOP - the loop that is being vectorized.
1185    COND - Condition that is checked for simple use.
1186
1187    Returns whether a COND can be vectorized.  Checks whether
1188    condition operands are supportable using vec_is_simple_use.  */
1189
1190 static bool
1191 vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
1192 {
1193   tree lhs, rhs;
1194
1195   if (!COMPARISON_CLASS_P (cond))
1196     return false;
1197
1198   lhs = TREE_OPERAND (cond, 0);
1199   rhs = TREE_OPERAND (cond, 1);
1200
1201   if (TREE_CODE (lhs) == SSA_NAME)
1202     {
1203       tree lhs_def_stmt = SSA_NAME_DEF_STMT (lhs);
1204       if (!vect_is_simple_use (lhs, loop_vinfo, &lhs_def_stmt))
1205         return false;
1206     }
1207   else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST)
1208     return false;
1209
1210   if (TREE_CODE (rhs) == SSA_NAME)
1211     {
1212       tree rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1213       if (!vect_is_simple_use (rhs, loop_vinfo, &rhs_def_stmt))
1214         return false;
1215     }
1216   else if (TREE_CODE (rhs) != INTEGER_CST  && TREE_CODE (rhs) != REAL_CST)
1217     return false;
1218
1219   return true;
1220 }
1221
1222 /* vectorizable_condition.
1223
1224    Check if STMT is conditional modify expression that can be vectorized.
1225    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1226    stmt using VEC_COND_EXPR  to replace it, put it in VEC_STMT, and insert it
1227    at BSI.
1228
1229    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1230
1231 bool
1232 vectorizable_condition (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
1233 {
1234   tree scalar_dest = NULL_TREE;
1235   tree vec_dest = NULL_TREE;
1236   tree op = NULL_TREE;
1237   tree cond_expr, then_clause, else_clause;
1238   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1239   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1240   tree vec_cond_lhs, vec_cond_rhs, vec_then_clause, vec_else_clause;
1241   tree vec_compare, vec_cond_expr;
1242   tree new_temp;
1243   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1244   enum machine_mode vec_mode;
1245
1246   if (!STMT_VINFO_RELEVANT_P (stmt_info))
1247     return false;
1248
1249   if (TREE_CODE (stmt) != MODIFY_EXPR)
1250     return false;
1251
1252   op = TREE_OPERAND (stmt, 1);
1253
1254   if (TREE_CODE (op) != COND_EXPR)
1255     return false;
1256
1257   cond_expr = TREE_OPERAND (op, 0);
1258   then_clause = TREE_OPERAND (op, 1);
1259   else_clause = TREE_OPERAND (op, 2);
1260
1261   if (!vect_is_simple_cond (cond_expr, loop_vinfo))
1262     return false;
1263
1264   if (TREE_CODE (then_clause) == SSA_NAME)
1265     {
1266       tree then_def_stmt = SSA_NAME_DEF_STMT (then_clause);
1267       if (!vect_is_simple_use (then_clause, loop_vinfo, &then_def_stmt))
1268         return false;
1269     }
1270   else if (TREE_CODE (then_clause) != INTEGER_CST
1271            && TREE_CODE (then_clause) != REAL_CST)
1272     return false;
1273
1274   if (TREE_CODE (else_clause) == SSA_NAME)
1275     {
1276       tree else_def_stmt = SSA_NAME_DEF_STMT (else_clause);
1277       if (!vect_is_simple_use (else_clause, loop_vinfo, &else_def_stmt))
1278         return false;
1279     }
1280   else if (TREE_CODE (else_clause) != INTEGER_CST
1281            && TREE_CODE (else_clause) != REAL_CST)
1282     return false;
1283
1284
1285   vec_mode = TYPE_MODE (vectype);
1286
1287   if (!vec_stmt)
1288     {
1289       STMT_VINFO_TYPE (stmt_info) = condition_vec_info_type;
1290       return expand_vec_cond_expr_p (op, vec_mode);
1291     }
1292
1293   /* Transform */
1294
1295   /* Handle def.  */
1296   scalar_dest = TREE_OPERAND (stmt, 0);
1297   vec_dest = vect_create_destination_var (scalar_dest, vectype);
1298
1299   /* Handle cond expr.  */
1300   vec_cond_lhs =
1301     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 0), stmt);
1302   vec_cond_rhs =
1303     vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 1), stmt);
1304   vec_then_clause = vect_get_vec_def_for_operand (then_clause, stmt);
1305   vec_else_clause = vect_get_vec_def_for_operand (else_clause, stmt);
1306
1307   /* Arguments are ready. create the new vector stmt.  */
1308   vec_compare = build2 (TREE_CODE (cond_expr), vectype,
1309                         vec_cond_lhs, vec_cond_rhs);
1310   vec_cond_expr = build (VEC_COND_EXPR, vectype,
1311                          vec_compare, vec_then_clause, vec_else_clause);
1312
1313   *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, vec_cond_expr);
1314   new_temp = make_ssa_name (vec_dest, *vec_stmt);
1315   TREE_OPERAND (*vec_stmt, 0) = new_temp;
1316   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
1317
1318   return true;
1319 }
1320
1321 /* Function vect_transform_stmt.
1322
1323    Create a vectorized stmt to replace STMT, and insert it at BSI.  */
1324
1325 bool
1326 vect_transform_stmt (tree stmt, block_stmt_iterator *bsi)
1327 {
1328   bool is_store = false;
1329   tree vec_stmt = NULL_TREE;
1330   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1331   bool done;
1332
1333   switch (STMT_VINFO_TYPE (stmt_info))
1334     {
1335     case op_vec_info_type:
1336       done = vectorizable_operation (stmt, bsi, &vec_stmt);
1337       gcc_assert (done);
1338       break;
1339
1340     case assignment_vec_info_type:
1341       done = vectorizable_assignment (stmt, bsi, &vec_stmt);
1342       gcc_assert (done);
1343       break;
1344
1345     case load_vec_info_type:
1346       done = vectorizable_load (stmt, bsi, &vec_stmt);
1347       gcc_assert (done);
1348       break;
1349
1350     case store_vec_info_type:
1351       done = vectorizable_store (stmt, bsi, &vec_stmt);
1352       gcc_assert (done);
1353       is_store = true;
1354       break;
1355
1356     case condition_vec_info_type:
1357       done = vectorizable_condition (stmt, bsi, &vec_stmt);
1358       gcc_assert (done);
1359       break;
1360
1361     default:
1362       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1363         fprintf (vect_dump, "stmt not supported.");
1364       gcc_unreachable ();
1365     }
1366
1367   STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
1368
1369   return is_store;
1370 }
1371
1372
1373 /* This function builds ni_name = number of iterations loop executes
1374    on the loop preheader.  */
1375
1376 static tree
1377 vect_build_loop_niters (loop_vec_info loop_vinfo)
1378 {
1379   tree ni_name, stmt, var;
1380   edge pe;
1381   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1382   tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
1383
1384   var = create_tmp_var (TREE_TYPE (ni), "niters");
1385   add_referenced_tmp_var (var);
1386   ni_name = force_gimple_operand (ni, &stmt, false, var);
1387
1388   pe = loop_preheader_edge (loop);
1389   if (stmt)
1390     {
1391       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1392       gcc_assert (!new_bb);
1393     }
1394
1395   return ni_name;
1396 }
1397
1398
1399 /* This function generates the following statements:
1400
1401  ni_name = number of iterations loop executes
1402  ratio = ni_name / vf
1403  ratio_mult_vf_name = ratio * vf
1404
1405  and places them at the loop preheader edge.  */
1406
1407 static void
1408 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
1409                                  tree *ni_name_ptr,
1410                                  tree *ratio_mult_vf_name_ptr,
1411                                  tree *ratio_name_ptr)
1412 {
1413
1414   edge pe;
1415   basic_block new_bb;
1416   tree stmt, ni_name;
1417   tree var;
1418   tree ratio_name;
1419   tree ratio_mult_vf_name;
1420   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1421   tree ni = LOOP_VINFO_NITERS (loop_vinfo);
1422   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1423   tree log_vf = build_int_cst (unsigned_type_node, exact_log2 (vf));
1424
1425   pe = loop_preheader_edge (loop);
1426
1427   /* Generate temporary variable that contains
1428      number of iterations loop executes.  */
1429
1430   ni_name = vect_build_loop_niters (loop_vinfo);
1431
1432   /* Create: ratio = ni >> log2(vf) */
1433
1434   var = create_tmp_var (TREE_TYPE (ni), "bnd");
1435   add_referenced_tmp_var (var);
1436   ratio_name = make_ssa_name (var, NULL_TREE);
1437   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_name,
1438            build2 (RSHIFT_EXPR, TREE_TYPE (ni_name), ni_name, log_vf));
1439   SSA_NAME_DEF_STMT (ratio_name) = stmt;
1440
1441   pe = loop_preheader_edge (loop);
1442   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1443   gcc_assert (!new_bb);
1444
1445   /* Create: ratio_mult_vf = ratio << log2 (vf).  */
1446
1447   var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
1448   add_referenced_tmp_var (var);
1449   ratio_mult_vf_name = make_ssa_name (var, NULL_TREE);
1450   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_mult_vf_name,
1451            build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name), ratio_name, log_vf));
1452   SSA_NAME_DEF_STMT (ratio_mult_vf_name) = stmt;
1453
1454   pe = loop_preheader_edge (loop);
1455   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1456   gcc_assert (!new_bb);
1457
1458   *ni_name_ptr = ni_name;
1459   *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
1460   *ratio_name_ptr = ratio_name;
1461
1462   return;
1463 }
1464
1465
1466 /* Function update_vuses_to_preheader.
1467
1468    Input:
1469    STMT - a statement with potential VUSEs.
1470    LOOP - the loop whose preheader will contain STMT.
1471
1472    It's possible to vectorize a loop even though an SSA_NAME from a VUSE
1473    appears to be defined in a V_MAY_DEF in another statement in a loop.
1474    One such case is when the VUSE is at the dereference of a __restricted__
1475    pointer in a load and the V_MAY_DEF is at the dereference of a different
1476    __restricted__ pointer in a store.  Vectorization may result in
1477    copy_virtual_uses being called to copy the problematic VUSE to a new
1478    statement that is being inserted in the loop preheader.  This procedure
1479    is called to change the SSA_NAME in the new statement's VUSE from the
1480    SSA_NAME updated in the loop to the related SSA_NAME available on the
1481    path entering the loop.
1482
1483    When this function is called, we have the following situation:
1484
1485         # vuse <name1>
1486         S1: vload
1487     do {
1488         # name1 = phi < name0 , name2>
1489
1490         # vuse <name1>
1491         S2: vload
1492
1493         # name2 = vdef <name1>
1494         S3: vstore
1495
1496     }while...
1497
1498    Stmt S1 was created in the loop preheader block as part of misaligned-load
1499    handling. This function fixes the name of the vuse of S1 from 'name1' to
1500    'name0'.  */
1501
1502 static void
1503 update_vuses_to_preheader (tree stmt, struct loop *loop)
1504 {
1505   basic_block header_bb = loop->header;
1506   edge preheader_e = loop_preheader_edge (loop);
1507   ssa_op_iter iter;
1508   use_operand_p use_p;
1509
1510   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VUSE)
1511     {
1512       tree ssa_name = USE_FROM_PTR (use_p);
1513       tree def_stmt = SSA_NAME_DEF_STMT (ssa_name);
1514       tree name_var = SSA_NAME_VAR (ssa_name);
1515       basic_block bb = bb_for_stmt (def_stmt);
1516
1517       /* For a use before any definitions, def_stmt is a NOP_EXPR.  */
1518       if (!IS_EMPTY_STMT (def_stmt)
1519           && flow_bb_inside_loop_p (loop, bb))
1520         {
1521           /* If the block containing the statement defining the SSA_NAME
1522              is in the loop then it's necessary to find the definition
1523              outside the loop using the PHI nodes of the header.  */
1524           tree phi;
1525           bool updated = false;
1526
1527           for (phi = phi_nodes (header_bb); phi; phi = TREE_CHAIN (phi))
1528             {
1529               if (SSA_NAME_VAR (PHI_RESULT (phi)) == name_var)
1530                 {
1531                   SET_USE (use_p, PHI_ARG_DEF (phi, preheader_e->dest_idx));
1532                   updated = true;
1533                   break;
1534                 }
1535             }
1536           gcc_assert (updated);
1537         }
1538     }
1539 }
1540
1541
1542 /*   Function vect_update_ivs_after_vectorizer.
1543
1544      "Advance" the induction variables of LOOP to the value they should take
1545      after the execution of LOOP.  This is currently necessary because the
1546      vectorizer does not handle induction variables that are used after the
1547      loop.  Such a situation occurs when the last iterations of LOOP are
1548      peeled, because:
1549      1. We introduced new uses after LOOP for IVs that were not originally used
1550         after LOOP: the IVs of LOOP are now used by an epilog loop.
1551      2. LOOP is going to be vectorized; this means that it will iterate N/VF
1552         times, whereas the loop IVs should be bumped N times.
1553
1554      Input:
1555      - LOOP - a loop that is going to be vectorized. The last few iterations
1556               of LOOP were peeled.
1557      - NITERS - the number of iterations that LOOP executes (before it is
1558                 vectorized). i.e, the number of times the ivs should be bumped.
1559      - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
1560                   coming out from LOOP on which there are uses of the LOOP ivs
1561                   (this is the path from LOOP->exit to epilog_loop->preheader).
1562
1563                   The new definitions of the ivs are placed in LOOP->exit.
1564                   The phi args associated with the edge UPDATE_E in the bb
1565                   UPDATE_E->dest are updated accordingly.
1566
1567      Assumption 1: Like the rest of the vectorizer, this function assumes
1568      a single loop exit that has a single predecessor.
1569
1570      Assumption 2: The phi nodes in the LOOP header and in update_bb are
1571      organized in the same order.
1572
1573      Assumption 3: The access function of the ivs is simple enough (see
1574      vect_can_advance_ivs_p).  This assumption will be relaxed in the future.
1575
1576      Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
1577      coming out of LOOP on which the ivs of LOOP are used (this is the path
1578      that leads to the epilog loop; other paths skip the epilog loop).  This
1579      path starts with the edge UPDATE_E, and its destination (denoted update_bb)
1580      needs to have its phis updated.
1581  */
1582
1583 static void
1584 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
1585                                   edge update_e)
1586 {
1587   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1588   basic_block exit_bb = loop->single_exit->dest;
1589   tree phi, phi1;
1590   basic_block update_bb = update_e->dest;
1591
1592   /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
1593
1594   /* Make sure there exists a single-predecessor exit bb:  */
1595   gcc_assert (single_pred_p (exit_bb));
1596
1597   for (phi = phi_nodes (loop->header), phi1 = phi_nodes (update_bb);
1598        phi && phi1;
1599        phi = PHI_CHAIN (phi), phi1 = PHI_CHAIN (phi1))
1600     {
1601       tree access_fn = NULL;
1602       tree evolution_part;
1603       tree init_expr;
1604       tree step_expr;
1605       tree var, stmt, ni, ni_name;
1606       block_stmt_iterator last_bsi;
1607
1608       /* Skip virtual phi's.  */
1609       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1610         {
1611           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1612             fprintf (vect_dump, "virtual phi. skip.");
1613           continue;
1614         }
1615
1616       access_fn = analyze_scalar_evolution (loop, PHI_RESULT (phi));
1617       gcc_assert (access_fn);
1618       evolution_part =
1619          unshare_expr (evolution_part_in_loop_num (access_fn, loop->num));
1620       gcc_assert (evolution_part != NULL_TREE);
1621
1622       /* FORNOW: We do not support IVs whose evolution function is a polynomial
1623          of degree >= 2 or exponential.  */
1624       gcc_assert (!tree_is_chrec (evolution_part));
1625
1626       step_expr = evolution_part;
1627       init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
1628                                                                loop->num));
1629
1630       ni = build2 (PLUS_EXPR, TREE_TYPE (init_expr),
1631                   build2 (MULT_EXPR, TREE_TYPE (niters),
1632                        niters, step_expr), init_expr);
1633
1634       var = create_tmp_var (TREE_TYPE (init_expr), "tmp");
1635       add_referenced_tmp_var (var);
1636
1637       ni_name = force_gimple_operand (ni, &stmt, false, var);
1638
1639       /* Insert stmt into exit_bb.  */
1640       last_bsi = bsi_last (exit_bb);
1641       if (stmt)
1642         bsi_insert_before (&last_bsi, stmt, BSI_SAME_STMT);
1643
1644       /* Fix phi expressions in the successor bb.  */
1645       SET_PHI_ARG_DEF (phi1, update_e->dest_idx, ni_name);
1646     }
1647 }
1648
1649
1650 /* Function vect_do_peeling_for_loop_bound
1651
1652    Peel the last iterations of the loop represented by LOOP_VINFO.
1653    The peeled iterations form a new epilog loop.  Given that the loop now
1654    iterates NITERS times, the new epilog loop iterates
1655    NITERS % VECTORIZATION_FACTOR times.
1656
1657    The original loop will later be made to iterate
1658    NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).  */
1659
1660 static void
1661 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
1662                                 struct loops *loops)
1663 {
1664
1665   tree ni_name, ratio_mult_vf_name;
1666   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1667   struct loop *new_loop;
1668   edge update_e;
1669   basic_block preheader;
1670 #ifdef ENABLE_CHECKING
1671   int loop_num;
1672 #endif
1673
1674   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1675     fprintf (vect_dump, "=== vect_transtorm_for_unknown_loop_bound ===");
1676
1677   /* Generate the following variables on the preheader of original loop:
1678
1679      ni_name = number of iteration the original loop executes
1680      ratio = ni_name / vf
1681      ratio_mult_vf_name = ratio * vf  */
1682   vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
1683                                    &ratio_mult_vf_name, ratio);
1684
1685 #ifdef ENABLE_CHECKING
1686   loop_num  = loop->num;
1687 #endif
1688   new_loop = slpeel_tree_peel_loop_to_edge (loop, loops, loop->single_exit,
1689                                             ratio_mult_vf_name, ni_name, false);
1690 #ifdef ENABLE_CHECKING
1691   gcc_assert (new_loop);
1692   gcc_assert (loop_num == loop->num);
1693   slpeel_verify_cfg_after_peeling (loop, new_loop);
1694 #endif
1695
1696   /* A guard that controls whether the new_loop is to be executed or skipped
1697      is placed in LOOP->exit.  LOOP->exit therefore has two successors - one
1698      is the preheader of NEW_LOOP, where the IVs from LOOP are used.  The other
1699      is a bb after NEW_LOOP, where these IVs are not used.  Find the edge that
1700      is on the path where the LOOP IVs are used and need to be updated.  */
1701
1702   preheader = loop_preheader_edge (new_loop)->src;
1703   if (EDGE_PRED (preheader, 0)->src == loop->single_exit->dest)
1704     update_e = EDGE_PRED (preheader, 0);
1705   else
1706     update_e = EDGE_PRED (preheader, 1);
1707
1708   /* Update IVs of original loop as if they were advanced
1709      by ratio_mult_vf_name steps.  */
1710   vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
1711
1712   /* After peeling we have to reset scalar evolution analyzer.  */
1713   scev_reset ();
1714
1715   return;
1716 }
1717
1718
1719 /* Function vect_gen_niters_for_prolog_loop
1720
1721    Set the number of iterations for the loop represented by LOOP_VINFO
1722    to the minimum between LOOP_NITERS (the original iteration count of the loop)
1723    and the misalignment of DR - the data reference recorded in
1724    LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO).  As a result, after the execution of
1725    this loop, the data reference DR will refer to an aligned location.
1726
1727    The following computation is generated:
1728
1729    If the misalignment of DR is known at compile time:
1730      addr_mis = int mis = DR_MISALIGNMENT (dr);
1731    Else, compute address misalignment in bytes:
1732      addr_mis = addr & (vectype_size - 1)
1733
1734    prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
1735
1736    (elem_size = element type size; an element is the scalar element
1737         whose type is the inner type of the vectype)  */
1738
1739 static tree
1740 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
1741 {
1742   struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
1743   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1744   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1745   tree var, stmt;
1746   tree iters, iters_name;
1747   edge pe;
1748   basic_block new_bb;
1749   tree dr_stmt = DR_STMT (dr);
1750   stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
1751   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1752   int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
1753   tree vf_minus_1 = build_int_cst (unsigned_type_node, vf - 1);
1754   tree niters_type = TREE_TYPE (loop_niters);
1755
1756   pe = loop_preheader_edge (loop);
1757
1758   if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo) > 0)
1759     {
1760       int byte_misalign = LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo);
1761       int element_size = vectype_align/vf;
1762       int elem_misalign = byte_misalign / element_size;
1763
1764       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1765         fprintf (vect_dump, "known alignment = %d.", byte_misalign);
1766       iters = build_int_cst (niters_type, (vf - elem_misalign)&(vf-1));
1767     }
1768   else
1769     {
1770       tree new_stmts = NULL_TREE;
1771       tree start_addr =
1772         vect_create_addr_base_for_vector_ref (dr_stmt, &new_stmts, NULL_TREE);
1773       tree ptr_type = TREE_TYPE (start_addr);
1774       tree size = TYPE_SIZE (ptr_type);
1775       tree type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
1776       tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
1777       tree elem_size_log =
1778         build_int_cst (unsigned_type_node, exact_log2 (vectype_align/vf));
1779       tree vf_tree = build_int_cst (unsigned_type_node, vf);
1780       tree byte_misalign;
1781       tree elem_misalign;
1782
1783       new_bb = bsi_insert_on_edge_immediate (pe, new_stmts);
1784       gcc_assert (!new_bb);
1785
1786       /* Create:  byte_misalign = addr & (vectype_size - 1)  */
1787       byte_misalign =
1788         build2 (BIT_AND_EXPR, type, start_addr, vectype_size_minus_1);
1789
1790       /* Create:  elem_misalign = byte_misalign / element_size  */
1791       elem_misalign =
1792         build2 (RSHIFT_EXPR, unsigned_type_node, byte_misalign, elem_size_log);
1793
1794       /* Create:  (niters_type) (VF - elem_misalign)&(VF - 1)  */
1795       iters = build2 (MINUS_EXPR, unsigned_type_node, vf_tree, elem_misalign);
1796       iters = build2 (BIT_AND_EXPR, unsigned_type_node, iters, vf_minus_1);
1797       iters = fold_convert (niters_type, iters);
1798     }
1799
1800   /* Create:  prolog_loop_niters = min (iters, loop_niters) */
1801   /* If the loop bound is known at compile time we already verified that it is
1802      greater than vf; since the misalignment ('iters') is at most vf, there's
1803      no need to generate the MIN_EXPR in this case.  */
1804   if (TREE_CODE (loop_niters) != INTEGER_CST)
1805     iters = build2 (MIN_EXPR, niters_type, iters, loop_niters);
1806
1807   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1808     {
1809       fprintf (vect_dump, "niters for prolog loop: ");
1810       print_generic_expr (vect_dump, iters, TDF_SLIM);
1811     }
1812
1813   var = create_tmp_var (niters_type, "prolog_loop_niters");
1814   add_referenced_tmp_var (var);
1815   iters_name = force_gimple_operand (iters, &stmt, false, var);
1816
1817   /* Insert stmt on loop preheader edge.  */
1818   if (stmt)
1819     {
1820       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
1821       gcc_assert (!new_bb);
1822     }
1823
1824   return iters_name;
1825 }
1826
1827
1828 /* Function vect_update_init_of_dr
1829
1830    NITERS iterations were peeled from LOOP.  DR represents a data reference
1831    in LOOP.  This function updates the information recorded in DR to
1832    account for the fact that the first NITERS iterations had already been
1833    executed.  Specifically, it updates the OFFSET field of stmt_info.  */
1834
1835 static void
1836 vect_update_init_of_dr (struct data_reference *dr, tree niters)
1837 {
1838   stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
1839   tree offset = STMT_VINFO_VECT_INIT_OFFSET (stmt_info);
1840
1841   niters = fold (build2 (MULT_EXPR, TREE_TYPE (niters), niters,
1842                          STMT_VINFO_VECT_STEP (stmt_info)));
1843   offset = fold (build2 (PLUS_EXPR, TREE_TYPE (offset), offset, niters));
1844   STMT_VINFO_VECT_INIT_OFFSET (stmt_info) = offset;
1845 }
1846
1847
1848 /* Function vect_update_inits_of_drs
1849
1850    NITERS iterations were peeled from the loop represented by LOOP_VINFO.
1851    This function updates the information recorded for the data references in
1852    the loop to account for the fact that the first NITERS iterations had
1853    already been executed.  Specifically, it updates the initial_condition of the
1854    access_function of all the data_references in the loop.  */
1855
1856 static void
1857 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
1858 {
1859   unsigned int i;
1860   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
1861   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
1862
1863   if (vect_dump && (dump_flags & TDF_DETAILS))
1864     fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
1865
1866   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
1867     {
1868       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
1869       vect_update_init_of_dr (dr, niters);
1870     }
1871
1872   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
1873     {
1874       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
1875       vect_update_init_of_dr (dr, niters);
1876     }
1877 }
1878
1879
1880 /* Function vect_do_peeling_for_alignment
1881
1882    Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
1883    'niters' is set to the misalignment of one of the data references in the
1884    loop, thereby forcing it to refer to an aligned location at the beginning
1885    of the execution of this loop.  The data reference for which we are
1886    peeling is recorded in LOOP_VINFO_UNALIGNED_DR.  */
1887
1888 static void
1889 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo, struct loops *loops)
1890 {
1891   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1892   tree niters_of_prolog_loop, ni_name;
1893   tree n_iters;
1894   struct loop *new_loop;
1895
1896   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1897     fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
1898
1899   ni_name = vect_build_loop_niters (loop_vinfo);
1900   niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, ni_name);
1901
1902   /* Peel the prolog loop and iterate it niters_of_prolog_loop.  */
1903   new_loop =
1904         slpeel_tree_peel_loop_to_edge (loop, loops, loop_preheader_edge (loop),
1905                                        niters_of_prolog_loop, ni_name, true);
1906 #ifdef ENABLE_CHECKING
1907   gcc_assert (new_loop);
1908   slpeel_verify_cfg_after_peeling (new_loop, loop);
1909 #endif
1910
1911   /* Update number of times loop executes.  */
1912   n_iters = LOOP_VINFO_NITERS (loop_vinfo);
1913   LOOP_VINFO_NITERS (loop_vinfo) = fold (build2 (MINUS_EXPR,
1914                 TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop));
1915
1916   /* Update the init conditions of the access functions of all data refs.  */
1917   vect_update_inits_of_drs (loop_vinfo, niters_of_prolog_loop);
1918
1919   /* After peeling we have to reset scalar evolution analyzer.  */
1920   scev_reset ();
1921
1922   return;
1923 }
1924
1925
1926 /* Function vect_transform_loop.
1927
1928    The analysis phase has determined that the loop is vectorizable.
1929    Vectorize the loop - created vectorized stmts to replace the scalar
1930    stmts in the loop, and update the loop exit condition.  */
1931
1932 void
1933 vect_transform_loop (loop_vec_info loop_vinfo,
1934                      struct loops *loops ATTRIBUTE_UNUSED)
1935 {
1936   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1937   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
1938   int nbbs = loop->num_nodes;
1939   block_stmt_iterator si;
1940   int i;
1941   tree ratio = NULL;
1942   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
1943
1944   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1945     fprintf (vect_dump, "=== vec_transform_loop ===");
1946
1947
1948   /* Peel the loop if there are data refs with unknown alignment.
1949      Only one data ref with unknown store is allowed.  */
1950
1951   if (LOOP_PEELING_FOR_ALIGNMENT (loop_vinfo))
1952     vect_do_peeling_for_alignment (loop_vinfo, loops);
1953
1954   /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
1955      compile time constant), or it is a constant that doesn't divide by the
1956      vectorization factor, then an epilog loop needs to be created.
1957      We therefore duplicate the loop: the original loop will be vectorized,
1958      and will compute the first (n/VF) iterations. The second copy of the loop
1959      will remain scalar and will compute the remaining (n%VF) iterations.
1960      (VF is the vectorization factor).  */
1961
1962   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1963       || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
1964           && LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0))
1965     vect_do_peeling_for_loop_bound (loop_vinfo, &ratio, loops);
1966   else
1967     ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
1968                 LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
1969
1970   /* 1) Make sure the loop header has exactly two entries
1971      2) Make sure we have a preheader basic block.  */
1972
1973   gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
1974
1975   loop_split_edge_with (loop_preheader_edge (loop), NULL);
1976
1977
1978   /* FORNOW: the vectorizer supports only loops which body consist
1979      of one basic block (header + empty latch). When the vectorizer will
1980      support more involved loop forms, the order by which the BBs are
1981      traversed need to be reconsidered.  */
1982
1983   for (i = 0; i < nbbs; i++)
1984     {
1985       basic_block bb = bbs[i];
1986
1987       for (si = bsi_start (bb); !bsi_end_p (si);)
1988         {
1989           tree stmt = bsi_stmt (si);
1990           stmt_vec_info stmt_info;
1991           bool is_store;
1992
1993           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1994             {
1995               fprintf (vect_dump, "------>vectorizing statement: ");
1996               print_generic_expr (vect_dump, stmt, TDF_SLIM);
1997             }
1998           stmt_info = vinfo_for_stmt (stmt);
1999           gcc_assert (stmt_info);
2000           if (!STMT_VINFO_RELEVANT_P (stmt_info))
2001             {
2002               bsi_next (&si);
2003               continue;
2004             }
2005 #ifdef ENABLE_CHECKING
2006           /* FORNOW: Verify that all stmts operate on the same number of
2007                      units and no inner unrolling is necessary.  */
2008           gcc_assert
2009                 (TYPE_VECTOR_SUBPARTS (STMT_VINFO_VECTYPE (stmt_info))
2010                  == vectorization_factor);
2011 #endif
2012           /* -------- vectorize statement ------------ */
2013           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2014             fprintf (vect_dump, "transform statement.");
2015
2016           is_store = vect_transform_stmt (stmt, &si);
2017           if (is_store)
2018             {
2019               /* Free the attached stmt_vec_info and remove the stmt.  */
2020               stmt_ann_t ann = stmt_ann (stmt);
2021               free (stmt_info);
2022               set_stmt_info (ann, NULL);
2023               bsi_remove (&si);
2024               continue;
2025             }
2026
2027           bsi_next (&si);
2028         }                       /* stmts in BB */
2029     }                           /* BBs in loop */
2030
2031   slpeel_make_loop_iterate_ntimes (loop, ratio);
2032
2033   /* The memory tags and pointers in vectorized statements need to
2034      have their SSA forms updated.  FIXME, why can't this be delayed
2035      until all the loops have been transformed?  */
2036   update_ssa (TODO_update_ssa);
2037
2038   if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS, LOOP_LOC (loop_vinfo)))
2039     fprintf (vect_dump, "LOOP VECTORIZED.");
2040 }