gcc/tree-vectorizer.c

   1 /* 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 /* Loop Vectorization Pass.
  23
  24    This pass tries to vectorize loops. This first implementation focuses on
  25    simple inner-most loops, with no conditional control flow, and a set of
  26    simple operations which vector form can be expressed using existing
  27    tree codes (PLUS, MULT etc).
  28
  29    For example, the vectorizer transforms the following simple loop:
  30
  31         short a[N]; short b[N]; short c[N]; int i;
  32
  33         for (i=0; i<N; i++){
  34           a[i] = b[i] + c[i];
  35         }
  36
  37    as if it was manually vectorized by rewriting the source code into:
  38
  39         typedef int __attribute__((mode(V8HI))) v8hi;
  40         short a[N];  short b[N]; short c[N];   int i;
  41         v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
  42         v8hi va, vb, vc;
  43
  44         for (i=0; i<N/8; i++){
  45           vb = pb[i];
  46           vc = pc[i];
  47           va = vb + vc;
  48           pa[i] = va;
  49         }
  50
  51         The main entry to this pass is vectorize_loops(), in which
  52    the vectorizer applies a set of analyses on a given set of loops,
  53    followed by the actual vectorization transformation for the loops that
  54    had successfully passed the analysis phase.
  55
  56         Throughout this pass we make a distinction between two types of
  57    data: scalars (which are represented by SSA_NAMES), and memory references
  58    ("data-refs"). These two types of data require different handling both
  59    during analysis and transformation. The types of data-refs that the
  60    vectorizer currently supports are ARRAY_REFS which base is an array DECL
  61    (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
  62    accesses are required to have a  simple (consecutive) access pattern.
  63
  64    Analysis phase:
  65    ===============
  66         The driver for the analysis phase is vect_analyze_loop_nest().
  67    It applies a set of analyses, some of which rely on the scalar evolution
  68    analyzer (scev) developed by Sebastian Pop.
  69
  70         During the analysis phase the vectorizer records some information
  71    per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
  72    loop, as well as general information about the loop as a whole, which is
  73    recorded in a "loop_vec_info" struct attached to each loop.
  74
  75    Transformation phase:
  76    =====================
  77         The loop transformation phase scans all the stmts in the loop, and
  78    creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
  79    the loop that needs to be vectorized. It insert the vector code sequence
  80    just before the scalar stmt S, and records a pointer to the vector code
  81    in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
  82    attached to S). This pointer will be used for the vectorization of following
  83    stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
  84    otherwise, we rely on dead code elimination for removing it.
  85
  86         For example, say stmt S1 was vectorized into stmt VS1:
  87
  88    VS1: vb = px[i];
  89    S1:  b = x[i];    STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
  90    S2:  a = b;
  91
  92    To vectorize stmt S2, the vectorizer first finds the stmt that defines
  93    the operand 'b' (S1), and gets the relevant vector def 'vb' from the
  94    vector stmt VS1 pointed by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
  95    resulting sequence would be:
  96
  97    VS1: vb = px[i];
  98    S1:  b = x[i];       STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
  99    VS2: va = vb;
 100    S2:  a = b;          STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
 101
 102         Operands that are not SSA_NAMEs, are data-refs that appear in
 103    load/store operations (like 'x[i]' in S1), and are handled differently.
 104
 105    Target modeling:
 106    =================
 107         Currently the only target specific information that is used is the
 108    size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can
 109    support different sizes of vectors, for now will need to specify one value
 110    for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
 111
 112         Since we only vectorize operations which vector form can be
 113    expressed using existing tree codes, to verify that an operation is
 114    supported, the vectorizer checks the relevant optab at the relevant
 115    machine_mode (e.g, add_optab->handlers[(int) V8HImode].insn_code). If
 116    the value found is CODE_FOR_nothing, then there's no target support, and
 117    we can't vectorize the stmt.
 118
 119    For additional information on this project see:
 120    http://gcc.gnu.org/projects/tree-ssa/vectorization.html
 121 */
 122
 123 #include "config.h"
 124 #include "system.h"
 125 #include "coretypes.h"
 126 #include "tm.h"
 127 #include "errors.h"
 128 #include "ggc.h"
 129 #include "tree.h"
 130 #include "target.h"
 131
 132 #include "rtl.h"
 133 #include "basic-block.h"
 134 #include "diagnostic.h"
 135 #include "tree-flow.h"
 136 #include "tree-dump.h"
 137 #include "timevar.h"
 138 #include "cfgloop.h"
 139 #include "cfglayout.h"
 140 #include "expr.h"
 141 #include "optabs.h"
 142 #include "toplev.h"
 143 #include "tree-chrec.h"
 144 #include "tree-data-ref.h"
 145 #include "tree-scalar-evolution.h"
 146 #include "input.h"
 147 #include "tree-vectorizer.h"
 148 #include "tree-pass.h"
 149 #include "langhooks.h"
 150
 151
 152 /*************************************************************************
 153   Simple Loop Peeling Utilities
 154  *************************************************************************/
 155
 156 /* Entry point for peeling of simple loops.
 157    Peel the first/last iterations of a loop.
 158    It can be used outside of the vectorizer for loops that are simple enough
 159    (see function documentation).  In the vectorizer it is used to peel the
 160    last few iterations when the loop bound is unknown or does not evenly
 161    divide by the vectorization factor, and to peel the first few iterations
 162    to force the alignment of data references in the loop.  */
 163 struct loop *slpeel_tree_peel_loop_to_edge
 164   (struct loop *, struct loops *, edge, tree, tree, bool);
 165 static struct loop *slpeel_tree_duplicate_loop_to_edge_cfg
 166   (struct loop *, struct loops *, edge);
 167 static void slpeel_update_phis_for_duplicate_loop
 168   (struct loop *, struct loop *, bool after);
 169 static void slpeel_update_phi_nodes_for_guard (edge, struct loop *, bool, bool);
 170 static void slpeel_make_loop_iterate_ntimes (struct loop *, tree);
 171 static edge slpeel_add_loop_guard (basic_block, tree, basic_block, basic_block);
 172 static bool slpeel_can_duplicate_loop_p (struct loop *, edge);
 173 static void allocate_new_names (bitmap);
 174 static void rename_use_op (use_operand_p);
 175 static void rename_def_op (def_operand_p, tree);
 176 static void rename_variables_in_bb (basic_block);
 177 static void free_new_names (bitmap);
 178 static void rename_variables_in_loop (struct loop *);
 179 #ifdef ENABLE_CHECKING
 180 static void slpeel_verify_cfg_after_peeling (struct loop *, struct loop *);
 181 #endif
 182 static LOC find_loop_location (struct loop *);
 183
 184
 185 /*************************************************************************
 186   Vectorization Utilities.
 187  *************************************************************************/
 188
 189 /* Main analysis functions.  */
 190 static loop_vec_info vect_analyze_loop (struct loop *);
 191 static loop_vec_info vect_analyze_loop_form (struct loop *);
 192 static bool vect_analyze_data_refs (loop_vec_info);
 193 static bool vect_mark_stmts_to_be_vectorized (loop_vec_info);
 194 static bool vect_analyze_scalar_cycles (loop_vec_info);
 195 static bool vect_analyze_data_ref_accesses (loop_vec_info);
 196 static bool vect_analyze_data_ref_dependence
 197   (struct data_reference *, struct data_reference *, loop_vec_info);
 198 static bool vect_analyze_data_ref_dependences (loop_vec_info);
 199 static bool vect_analyze_data_refs_alignment (loop_vec_info);
 200 static bool vect_compute_data_refs_alignment (loop_vec_info);
 201 static bool vect_analyze_operations (loop_vec_info);
 202
 203 /* Main code transformation functions.  */
 204 static void vect_transform_loop (loop_vec_info, struct loops *);
 205 static bool vect_transform_stmt (tree, block_stmt_iterator *);
 206 static bool vectorizable_load (tree, block_stmt_iterator *, tree *);
 207 static bool vectorizable_store (tree, block_stmt_iterator *, tree *);
 208 static bool vectorizable_operation (tree, block_stmt_iterator *, tree *);
 209 static bool vectorizable_assignment (tree, block_stmt_iterator *, tree *);
 210 static enum dr_alignment_support vect_supportable_dr_alignment
 211   (struct data_reference *);
 212 static void vect_align_data_ref (tree);
 213 static void vect_enhance_data_refs_alignment (loop_vec_info);
 214
 215 /* Utility functions for the analyses.  */
 216 static bool vect_is_simple_use (tree , loop_vec_info, tree *);
 217 static bool exist_non_indexing_operands_for_use_p (tree, tree);
 218 static bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *);
 219 static void vect_mark_relevant (varray_type *, tree);
 220 static bool vect_stmt_relevant_p (tree, loop_vec_info);
 221 static tree vect_get_loop_niters (struct loop *, tree *);
 222 static bool vect_compute_data_ref_alignment (struct data_reference *);
 223 static bool vect_analyze_data_ref_access (struct data_reference *);
 224 static bool vect_can_force_dr_alignment_p (tree, unsigned int);
 225 static struct data_reference * vect_analyze_pointer_ref_access
 226   (tree, tree, bool, tree, tree *, tree *);
 227 static bool vect_can_advance_ivs_p (loop_vec_info);
 228 static tree vect_get_ptr_offset (tree, tree, tree *);
 229 static bool vect_analyze_offset_expr (tree, struct loop *, tree, tree *,
 230                                       tree *, tree *);
 231 static tree vect_strip_conversion (tree);
 232 static bool vect_base_addr_differ_p (struct data_reference *,
 233                                      struct data_reference *drb, bool *);
 234 static tree vect_object_analysis (tree, tree, bool, tree,
 235                                   struct data_reference **, tree *, tree *,
 236                                   tree *, bool *);
 237 static tree vect_address_analysis (tree, tree, bool, tree,
 238                                    struct data_reference *, tree *, tree *,
 239                                    tree *, bool *);
 240 static tree vect_get_memtag (tree, struct data_reference *);
 241
 242 /* Utility functions for the code transformation.  */
 243 static tree vect_create_destination_var (tree, tree);
 244 static tree vect_create_data_ref_ptr
 245   (tree, block_stmt_iterator *, tree, tree *, bool);
 246 static tree vect_create_index_for_vector_ref (loop_vec_info);
 247 static tree vect_create_addr_base_for_vector_ref (tree, tree *, tree);
 248 static tree get_vectype_for_scalar_type (tree);
 249 static tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *);
 250 static tree vect_get_vec_def_for_operand (tree, tree);
 251 static tree vect_init_vector (tree, tree);
 252 static void vect_finish_stmt_generation
 253   (tree stmt, tree vec_stmt, block_stmt_iterator *bsi);
 254
 255 /* Utility function dealing with loop peeling (not peeling itself).  */
 256 static void vect_generate_tmps_on_preheader
 257   (loop_vec_info, tree *, tree *, tree *);
 258 static tree vect_build_loop_niters (loop_vec_info);
 259 static void vect_update_ivs_after_vectorizer (loop_vec_info, tree, edge);
 260 static tree vect_gen_niters_for_prolog_loop (loop_vec_info, tree);
 261 static void vect_update_inits_of_dr (struct data_reference *, tree niters);
 262 static void vect_update_inits_of_drs (loop_vec_info, tree);
 263 static void vect_do_peeling_for_alignment (loop_vec_info, struct loops *);
 264 static void vect_do_peeling_for_loop_bound
 265   (loop_vec_info, tree *, struct loops *);
 266
 267 /* Utilities for creation and deletion of vec_info structs.  */
 268 loop_vec_info new_loop_vec_info (struct loop *loop);
 269 void destroy_loop_vec_info (loop_vec_info);
 270 stmt_vec_info new_stmt_vec_info (tree, loop_vec_info);
 271
 272 /*************************************************************************
 273   Vectorization Debug Information.
 274  *************************************************************************/
 275
 276 /* vect_verbosity_level set to invalid verbosity level to mark that it's
 277    uninitialized.  */
 278 enum verbosity_levels vect_verbosity_level = MAX_VERBOSITY_LEVEL;
 279
 280 /* vect_dump will be set to stderr or dump_file if exist.  */
 281 FILE *vect_dump;
 282
 283 /* Utilities for output formatting. */
 284 static bool vect_print_dump_info (enum verbosity_levels, LOC);
 285 static void vect_set_dump_settings (void);
 286 void vect_set_verbosity_level (const char *);
 287
 288
 289 \f
 290 /*************************************************************************
 291   Simple Loop Peeling Utilities
 292
 293   Utilities to support loop peeling for vectorization purposes.
 294  *************************************************************************/
 295
 296
 297 /* For each definition in DEFINITIONS this function allocates
 298    new ssa name.  */
 299
 300 static void
 301 allocate_new_names (bitmap definitions)
 302 {
 303   unsigned ver;
 304   bitmap_iterator bi;
 305
 306   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
 307     {
 308       tree def = ssa_name (ver);
 309       tree *new_name_ptr = xmalloc (sizeof (tree));
 310
 311       bool abnormal = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def);
 312
 313       *new_name_ptr = duplicate_ssa_name (def, SSA_NAME_DEF_STMT (def));
 314       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (*new_name_ptr) = abnormal;
 315
 316       SSA_NAME_AUX (def) = new_name_ptr;
 317     }
 318 }
 319
 320
 321 /* Renames the use *OP_P.  */
 322
 323 static void
 324 rename_use_op (use_operand_p op_p)
 325 {
 326   tree *new_name_ptr;
 327
 328   if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
 329     return;
 330
 331   new_name_ptr = SSA_NAME_AUX (USE_FROM_PTR (op_p));
 332
 333   /* Something defined outside of the loop.  */
 334   if (!new_name_ptr)
 335     return;
 336
 337   /* An ordinary ssa name defined in the loop.  */
 338
 339   SET_USE (op_p, *new_name_ptr);
 340 }
 341
 342
 343 /* Renames the def *OP_P in statement STMT.  */
 344
 345 static void
 346 rename_def_op (def_operand_p op_p, tree stmt)
 347 {
 348   tree *new_name_ptr;
 349
 350   if (TREE_CODE (DEF_FROM_PTR (op_p)) != SSA_NAME)
 351     return;
 352
 353   new_name_ptr = SSA_NAME_AUX (DEF_FROM_PTR (op_p));
 354
 355   /* Something defined outside of the loop.  */
 356   if (!new_name_ptr)
 357     return;
 358
 359   /* An ordinary ssa name defined in the loop.  */
 360
 361   SET_DEF (op_p, *new_name_ptr);
 362   SSA_NAME_DEF_STMT (DEF_FROM_PTR (op_p)) = stmt;
 363 }
 364
 365
 366 /* Renames the variables in basic block BB.  */
 367
 368 static void
 369 rename_variables_in_bb (basic_block bb)
 370 {
 371   tree phi;
 372   block_stmt_iterator bsi;
 373   tree stmt;
 374   stmt_ann_t ann;
 375   use_optype uses;
 376   vuse_optype vuses;
 377   def_optype defs;
 378   v_may_def_optype v_may_defs;
 379   v_must_def_optype v_must_defs;
 380   unsigned i;
 381   edge e;
 382   edge_iterator ei;
 383   struct loop *loop = bb->loop_father;
 384
 385   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 386     rename_def_op (PHI_RESULT_PTR (phi), phi);
 387
 388   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 389     {
 390       stmt = bsi_stmt (bsi);
 391       get_stmt_operands (stmt);
 392       ann = stmt_ann (stmt);
 393
 394       uses = USE_OPS (ann);
 395       for (i = 0; i < NUM_USES (uses); i++)
 396         rename_use_op (USE_OP_PTR (uses, i));
 397
 398       defs = DEF_OPS (ann);
 399       for (i = 0; i < NUM_DEFS (defs); i++)
 400         rename_def_op (DEF_OP_PTR (defs, i), stmt);
 401
 402       vuses = VUSE_OPS (ann);
 403       for (i = 0; i < NUM_VUSES (vuses); i++)
 404         rename_use_op (VUSE_OP_PTR (vuses, i));
 405
 406       v_may_defs = V_MAY_DEF_OPS (ann);
 407       for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 408         {
 409           rename_use_op (V_MAY_DEF_OP_PTR (v_may_defs, i));
 410           rename_def_op (V_MAY_DEF_RESULT_PTR (v_may_defs, i), stmt);
 411         }
 412
 413       v_must_defs = V_MUST_DEF_OPS (ann);
 414       for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
 415         {
 416           rename_use_op (V_MUST_DEF_KILL_PTR (v_must_defs, i));
 417           rename_def_op (V_MUST_DEF_RESULT_PTR (v_must_defs, i), stmt);
 418         }
 419     }
 420
 421   FOR_EACH_EDGE (e, ei, bb->succs)
 422     {
 423       if (!flow_bb_inside_loop_p (loop, e->dest))
 424         continue;
 425       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 426         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e));
 427     }
 428 }
 429
 430
 431 /* Releases the structures holding the new ssa names.  */
 432
 433 static void
 434 free_new_names (bitmap definitions)
 435 {
 436   unsigned ver;
 437   bitmap_iterator bi;
 438
 439   EXECUTE_IF_SET_IN_BITMAP (definitions, 0, ver, bi)
 440     {
 441       tree def = ssa_name (ver);
 442
 443       if (SSA_NAME_AUX (def))
 444         {
 445           free (SSA_NAME_AUX (def));
 446           SSA_NAME_AUX (def) = NULL;
 447         }
 448     }
 449 }
 450
 451
 452 /* Renames variables in new generated LOOP.  */
 453
 454 static void
 455 rename_variables_in_loop (struct loop *loop)
 456 {
 457   unsigned i;
 458   basic_block *bbs;
 459
 460   bbs = get_loop_body (loop);
 461
 462   for (i = 0; i < loop->num_nodes; i++)
 463     rename_variables_in_bb (bbs[i]);
 464
 465   free (bbs);
 466 }
 467
 468
 469 /* Update the PHI nodes of NEW_LOOP.
 470
 471    NEW_LOOP is a duplicate of ORIG_LOOP.
 472    AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
 473    AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
 474    executes before it.  */
 475
 476 static void
 477 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
 478                                        struct loop *new_loop, bool after)
 479 {
 480   tree *new_name_ptr, new_ssa_name;
 481   tree phi_new, phi_orig;
 482   tree def;
 483   edge orig_loop_latch = loop_latch_edge (orig_loop);
 484   edge orig_entry_e = loop_preheader_edge (orig_loop);
 485   edge new_loop_exit_e = new_loop->exit_edges[0];
 486   edge new_loop_entry_e = loop_preheader_edge (new_loop);
 487   edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
 488
 489   /*
 490      step 1. For each loop-header-phi:
 491              Add the first phi argument for the phi in NEW_LOOP
 492             (the one associated with the entry of NEW_LOOP)
 493
 494      step 2. For each loop-header-phi:
 495              Add the second phi argument for the phi in NEW_LOOP
 496             (the one associated with the latch of NEW_LOOP)
 497
 498      step 3. Update the phis in the successor block of NEW_LOOP.
 499
 500         case 1: NEW_LOOP was placed before ORIG_LOOP:
 501                 The successor block of NEW_LOOP is the header of ORIG_LOOP.
 502                 Updating the phis in the successor block can therefore be done
 503                 along with the scanning of the loop header phis, because the
 504                 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
 505                 phi nodes, organized in the same order.
 506
 507         case 2: NEW_LOOP was placed after ORIG_LOOP:
 508                 The successor block of NEW_LOOP is the original exit block of
 509                 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
 510                 We postpone updating these phis to a later stage (when
 511                 loop guards are added).
 512    */
 513
 514
 515   /* Scan the phis in the headers of the old and new loops
 516      (they are organized in exactly the same order).  */
 517
 518   for (phi_new = phi_nodes (new_loop->header),
 519        phi_orig = phi_nodes (orig_loop->header);
 520        phi_new && phi_orig;
 521        phi_new = PHI_CHAIN (phi_new), phi_orig = PHI_CHAIN (phi_orig))
 522     {
 523       /* step 1.  */
 524       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
 525       add_phi_arg (phi_new, def, new_loop_entry_e);
 526
 527       /* step 2.  */
 528       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
 529       if (TREE_CODE (def) != SSA_NAME)
 530         continue;
 531
 532       new_name_ptr = SSA_NAME_AUX (def);
 533       if (!new_name_ptr)
 534         /* Something defined outside of the loop.  */
 535         continue;
 536
 537       /* An ordinary ssa name defined in the loop.  */
 538       new_ssa_name = *new_name_ptr;
 539       add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
 540
 541       /* step 3 (case 1).  */
 542       if (!after)
 543         {
 544           gcc_assert (new_loop_exit_e == orig_entry_e);
 545           SET_PHI_ARG_DEF (phi_orig,
 546                            new_loop_exit_e->dest_idx,
 547                            new_ssa_name);
 548         }
 549     }
 550 }
 551
 552
 553 /* Update PHI nodes for a guard of the LOOP.
 554
 555    Input:
 556    - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
 557         controls whether LOOP is to be executed.  GUARD_EDGE is the edge that
 558         originates from the guard-bb, skips LOOP and reaches the (unique) exit
 559         bb of LOOP.  This loop-exit-bb is an empty bb with one successor.
 560         We denote this bb NEW_MERGE_BB because it had a single predecessor (the
 561         LOOP header) before the guard code was added, and now it became a merge
 562         point of two paths - the path that ends with the LOOP exit-edge, and
 563         the path that ends with GUARD_EDGE.
 564
 565         This function creates and updates the relevant phi nodes to account for
 566         the new incoming edge (GUARD_EDGE) into NEW_MERGE_BB:
 567         1. Create phi nodes at NEW_MERGE_BB.
 568         2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
 569            UPDATE_BB).  UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
 570            was added:
 571
 572         ===> The CFG before the guard-code was added:
 573         LOOP_header_bb:
 574           if (exit_loop) goto update_bb : LOOP_header_bb
 575         update_bb:
 576
 577         ==> The CFG after the guard-code was added:
 578         guard_bb:
 579           if (LOOP_guard_condition) goto new_merge_bb : LOOP_header_bb
 580         LOOP_header_bb:
 581           if (exit_loop_condition) goto new_merge_bb : LOOP_header_bb
 582         new_merge_bb:
 583           goto update_bb
 584         update_bb:
 585
 586    - ENTRY_PHIS: If ENTRY_PHIS is TRUE, this indicates that the phis in
 587         UPDATE_BB are loop entry phis, like the phis in the LOOP header,
 588         organized in the same order.
 589         If ENTRY_PHIs is FALSE, this indicates that the phis in UPDATE_BB are
 590         loop exit phis.
 591
 592    - IS_NEW_LOOP: TRUE if LOOP is a new loop (a duplicated copy of another
 593         "original" loop).  FALSE if LOOP is an original loop (not a newly
 594         created copy).  The SSA_NAME_AUX fields of the defs in the original
 595         loop are the corresponding new ssa-names used in the new duplicated
 596         loop copy.  IS_NEW_LOOP indicates which of the two args of the phi
 597         nodes in UPDATE_BB takes the original ssa-name, and which takes the
 598         new name: If IS_NEW_LOOP is TRUE, the phi-arg that is associated with
 599         the LOOP-exit-edge takes the new-name, and the phi-arg that is
 600         associated with GUARD_EDGE takes the original name.  If IS_NEW_LOOP is
 601         FALSE, it's the other way around.
 602   */
 603
 604 static void
 605 slpeel_update_phi_nodes_for_guard (edge guard_edge,
 606                                    struct loop *loop,
 607                                    bool entry_phis,
 608                                    bool is_new_loop)
 609 {
 610   tree orig_phi, new_phi, update_phi;
 611   tree guard_arg, loop_arg;
 612   basic_block new_merge_bb = guard_edge->dest;
 613   edge e = EDGE_SUCC (new_merge_bb, 0);
 614   basic_block update_bb = e->dest;
 615   basic_block orig_bb = (entry_phis ? loop->header : update_bb);
 616
 617   for (orig_phi = phi_nodes (orig_bb), update_phi = phi_nodes (update_bb);
 618        orig_phi && update_phi;
 619        orig_phi = PHI_CHAIN (orig_phi), update_phi = PHI_CHAIN (update_phi))
 620     {
 621       /* 1. Generate new phi node in NEW_MERGE_BB:  */
 622       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 623                                  new_merge_bb);
 624
 625       /* 2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
 626             of LOOP. Set the two phi args in NEW_PHI for these edges:  */
 627       if (entry_phis)
 628         {
 629           loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi,
 630                                             EDGE_SUCC (loop->latch, 0));
 631           guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop->entry_edges[0]);
 632         }
 633       else /* exit phis */
 634         {
 635           tree orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
 636           tree *new_name_ptr = SSA_NAME_AUX (orig_def);
 637           tree new_name;
 638
 639           if (new_name_ptr)
 640             new_name = *new_name_ptr;
 641           else
 642             /* Something defined outside of the loop  */
 643             new_name = orig_def;
 644
 645           if (is_new_loop)
 646             {
 647               guard_arg = orig_def;
 648               loop_arg = new_name;
 649             }
 650           else
 651             {
 652               guard_arg = new_name;
 653               loop_arg = orig_def;
 654             }
 655         }
 656       add_phi_arg (new_phi, loop_arg, loop->exit_edges[0]);
 657       add_phi_arg (new_phi, guard_arg, guard_edge);
 658
 659       /* 3. Update phi in successor block.  */
 660       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
 661                   || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
 662       SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
 663     }
 664
 665   set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
 666 }
 667
 668
 669 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
 670    that starts at zero, increases by one and its limit is NITERS.
 671
 672    Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
 673
 674 static void
 675 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
 676 {
 677   tree indx_before_incr, indx_after_incr, cond_stmt, cond;
 678   tree orig_cond;
 679   edge exit_edge = loop->exit_edges[0];
 680   block_stmt_iterator loop_cond_bsi;
 681   block_stmt_iterator incr_bsi;
 682   bool insert_after;
 683   tree begin_label = tree_block_label (loop->latch);
 684   tree exit_label = tree_block_label (loop->single_exit->dest);
 685   tree init = build_int_cst (TREE_TYPE (niters), 0);
 686   tree step = build_int_cst (TREE_TYPE (niters), 1);
 687   tree then_label;
 688   tree else_label;
 689   LOC loop_loc;
 690
 691   orig_cond = get_loop_exit_condition (loop);
 692 #ifdef ENABLE_CHECKING
 693   gcc_assert (orig_cond);
 694 #endif
 695   loop_cond_bsi = bsi_for_stmt (orig_cond);
 696
 697   standard_iv_increment_position (loop, &incr_bsi, &insert_after);
 698   create_iv (init, step, NULL_TREE, loop,
 699              &incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
 700
 701   if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop.  */
 702     {
 703       cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
 704       then_label = build1 (GOTO_EXPR, void_type_node, exit_label);
 705       else_label = build1 (GOTO_EXPR, void_type_node, begin_label);
 706     }
 707   else /* 'then' edge loops back.  */
 708     {
 709       cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
 710       then_label = build1 (GOTO_EXPR, void_type_node, begin_label);
 711       else_label = build1 (GOTO_EXPR, void_type_node, exit_label);
 712     }
 713
 714   cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
 715                      then_label, else_label);
 716   bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
 717
 718   /* Remove old loop exit test:  */
 719   bsi_remove (&loop_cond_bsi);
 720
 721   loop_loc = find_loop_location (loop);
 722   if (dump_file && (dump_flags & TDF_DETAILS))
 723     {
 724       if (loop_loc != UNKNOWN_LOC)
 725         fprintf (dump_file, "\nloop at %s:%d: ",
 726                  LOC_FILE (loop_loc), LOC_LINE (loop_loc));
 727       print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
 728     }
 729
 730   loop->nb_iterations = niters;
 731 }
 732
 733
 734 /* Given LOOP this function generates a new copy of it and puts it
 735    on E which is either the entry or exit of LOOP.  */
 736
 737 static struct loop *
 738 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, struct loops *loops,
 739                                         edge e)
 740 {
 741   struct loop *new_loop;
 742   basic_block *new_bbs, *bbs;
 743   bool at_exit;
 744   bool was_imm_dom;
 745   basic_block exit_dest;
 746   tree phi, phi_arg;
 747
 748   at_exit = (e == loop->exit_edges[0]);
 749   if (!at_exit && e != loop_preheader_edge (loop))
 750     return NULL;
 751
 752   bbs = get_loop_body (loop);
 753
 754   /* Check whether duplication is possible.  */
 755   if (!can_copy_bbs_p (bbs, loop->num_nodes))
 756     {
 757       free (bbs);
 758       return NULL;
 759     }
 760
 761   /* Generate new loop structure.  */
 762   new_loop = duplicate_loop (loops, loop, loop->outer);
 763   if (!new_loop)
 764     {
 765       free (bbs);
 766       return NULL;
 767     }
 768
 769   exit_dest = loop->exit_edges[0]->dest;
 770   was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
 771                                           exit_dest) == loop->header ?
 772                  true : false);
 773
 774   new_bbs = xmalloc (sizeof (basic_block) * loop->num_nodes);
 775
 776   copy_bbs (bbs, loop->num_nodes, new_bbs, NULL, 0, NULL, NULL);
 777
 778   /* Duplicating phi args at exit bbs as coming
 779      also from exit of duplicated loop.  */
 780   for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
 781     {
 782       phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, loop->exit_edges[0]);
 783       if (phi_arg)
 784         {
 785           edge new_loop_exit_edge;
 786
 787           if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
 788             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
 789           else
 790             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
 791
 792           add_phi_arg (phi, phi_arg, new_loop_exit_edge);
 793         }
 794     }
 795
 796   if (at_exit) /* Add the loop copy at exit.  */
 797     {
 798       redirect_edge_and_branch_force (e, new_loop->header);
 799       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
 800       if (was_imm_dom)
 801         set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
 802     }
 803   else /* Add the copy at entry.  */
 804     {
 805       edge new_exit_e;
 806       edge entry_e = loop_preheader_edge (loop);
 807       basic_block preheader = entry_e->src;
 808
 809       if (!flow_bb_inside_loop_p (new_loop,
 810                                   EDGE_SUCC (new_loop->header, 0)->dest))
 811         new_exit_e = EDGE_SUCC (new_loop->header, 0);
 812       else
 813         new_exit_e = EDGE_SUCC (new_loop->header, 1);
 814
 815       redirect_edge_and_branch_force (new_exit_e, loop->header);
 816       set_immediate_dominator (CDI_DOMINATORS, loop->header,
 817                                new_exit_e->src);
 818
 819       /* We have to add phi args to the loop->header here as coming
 820          from new_exit_e edge.  */
 821       for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
 822         {
 823           phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
 824           if (phi_arg)
 825             add_phi_arg (phi, phi_arg, new_exit_e);
 826         }
 827
 828       redirect_edge_and_branch_force (entry_e, new_loop->header);
 829       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
 830     }
 831
 832   flow_loop_scan (new_loop, LOOP_ALL);
 833   flow_loop_scan (loop, LOOP_ALL);
 834   free (new_bbs);
 835   free (bbs);
 836
 837   return new_loop;
 838 }
 839
 840
 841 /* Given the condition statement COND, put it as the last statement
 842    of GUARD_BB; EXIT_BB is the basic block to skip the loop;
 843    Assumes that this is the single exit of the guarded loop.
 844    Returns the skip edge.  */
 845
 846 static edge
 847 slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
 848                         basic_block dom_bb)
 849 {
 850   block_stmt_iterator bsi;
 851   edge new_e, enter_e;
 852   tree cond_stmt, then_label, else_label;
 853
 854   enter_e = EDGE_SUCC (guard_bb, 0);
 855   enter_e->flags &= ~EDGE_FALLTHRU;
 856   enter_e->flags |= EDGE_FALSE_VALUE;
 857   bsi = bsi_last (guard_bb);
 858
 859   then_label = build1 (GOTO_EXPR, void_type_node,
 860                        tree_block_label (exit_bb));
 861   else_label = build1 (GOTO_EXPR, void_type_node,
 862                        tree_block_label (enter_e->dest));
 863   cond_stmt = build3 (COND_EXPR, void_type_node, cond,
 864                      then_label, else_label);
 865   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
 866   /* Add new edge to connect entry block to the second loop.  */
 867   new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
 868   set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
 869   return new_e;
 870 }
 871
 872
 873 /* This function verifies that the following restrictions apply to LOOP:
 874    (1) it is innermost
 875    (2) it consists of exactly 2 basic blocks - header, and an empty latch.
 876    (3) it is single entry, single exit
 877    (4) its exit condition is the last stmt in the header
 878    (5) E is the entry/exit edge of LOOP.
 879  */
 880
 881 static bool
 882 slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
 883 {
 884   edge exit_e = loop->exit_edges [0];
 885   edge entry_e = loop_preheader_edge (loop);
 886   tree orig_cond = get_loop_exit_condition (loop);
 887   block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
 888
 889   if (any_marked_for_rewrite_p ())
 890     return false;
 891
 892   if (loop->inner
 893       /* All loops have an outer scope; the only case loop->outer is NULL is for
 894          the function itself.  */
 895       || !loop->outer
 896       || loop->num_nodes != 2
 897       || !empty_block_p (loop->latch)
 898       || loop->num_exits != 1
 899       || loop->num_entries != 1
 900       /* Verify that new loop exit condition can be trivially modified.  */
 901       || (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
 902       || (e != exit_e && e != entry_e))
 903     return false;
 904
 905   return true;
 906 }
 907
 908 #ifdef ENABLE_CHECKING
 909 static void
 910 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
 911                                  struct loop *second_loop)
 912 {
 913   basic_block loop1_exit_bb = first_loop->exit_edges[0]->dest;
 914   basic_block loop2_entry_bb = second_loop->pre_header;
 915   basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
 916
 917   /* A guard that controls whether the second_loop is to be executed or skipped
 918      is placed in first_loop->exit.  first_loopt->exit therefore has two
 919      successors - one is the preheader of second_loop, and the other is a bb
 920      after second_loop.
 921    */
 922   gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
 923
 924
 925   /* 1. Verify that one of the successors of first_loopt->exit is the preheader
 926         of second_loop.  */
 927
 928   /* The preheader of new_loop is expected to have two predessors:
 929      first_loop->exit and the block that precedes first_loop.  */
 930
 931   gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
 932               && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
 933                    && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
 934                || (EDGE_PRED (loop2_entry_bb, 1)->src ==  loop1_exit_bb
 935                    && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
 936
 937   /* Verify that the other successor of first_loopt->exit is after the
 938      second_loop.  */
 939   /* TODO */
 940 }
 941 #endif
 942
 943 /* Function slpeel_tree_peel_loop_to_edge.
 944
 945    Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
 946    that is placed on the entry (exit) edge E of LOOP. After this transformation
 947    we have two loops one after the other - first-loop iterates FIRST_NITERS
 948    times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
 949
 950    Input:
 951    - LOOP: the loop to be peeled.
 952    - E: the exit or entry edge of LOOP.
 953         If it is the entry edge, we peel the first iterations of LOOP. In this
 954         case first-loop is LOOP, and second-loop is the newly created loop.
 955         If it is the exit edge, we peel the last iterations of LOOP. In this
 956         case, first-loop is the newly created loop, and second-loop is LOOP.
 957    - NITERS: the number of iterations that LOOP iterates.
 958    - FIRST_NITERS: the number of iterations that the first-loop should iterate.
 959    - UPDATE_FIRST_LOOP_COUNT:  specified whether this function is responsible
 960         for updating the loop bound of the first-loop to FIRST_NITERS.  If it
 961         is false, the caller of this function may want to take care of this
 962         (this can be useful if we don't want new stmts added to first-loop).
 963
 964    Output:
 965    The function returns a pointer to the new loop-copy, or NULL if it failed
 966    to perform the transformation.
 967
 968    The function generates two if-then-else guards: one before the first loop,
 969    and the other before the second loop:
 970    The first guard is:
 971      if (FIRST_NITERS == 0) then skip the first loop,
 972      and go directly to the second loop.
 973    The second guard is:
 974      if (FIRST_NITERS == NITERS) then skip the second loop.
 975
 976    FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
 977    FORNOW the resulting code will not be in loop-closed-ssa form.
 978 */
 979
 980 struct loop*
 981 slpeel_tree_peel_loop_to_edge (struct loop *loop, struct loops *loops,
 982                                edge e, tree first_niters,
 983                                tree niters, bool update_first_loop_count)
 984 {
 985   struct loop *new_loop = NULL, *first_loop, *second_loop;
 986   edge skip_e;
 987   tree pre_condition;
 988   bitmap definitions;
 989   basic_block bb_before_second_loop, bb_after_second_loop;
 990   basic_block bb_before_first_loop;
 991   basic_block bb_between_loops;
 992   edge exit_e = loop->exit_edges [0];
 993   LOC loop_loc;
 994
 995   if (!slpeel_can_duplicate_loop_p (loop, e))
 996     return NULL;
 997
 998   /* We have to initialize cfg_hooks. Then, when calling
 999    cfg_hooks->split_edge, the function tree_split_edge
1000    is actually called and, when calling cfg_hooks->duplicate_block,
1001    the function tree_duplicate_bb is called.  */
1002   tree_register_cfg_hooks ();
1003
1004
1005   /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1006         Resulting CFG would be:
1007
1008         first_loop:
1009         do {
1010         } while ...
1011
1012         second_loop:
1013         do {
1014         } while ...
1015
1016         orig_exit_bb:
1017    */
1018
1019   if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, loops, e)))
1020     {
1021       loop_loc = find_loop_location (loop);
1022       if (dump_file && (dump_flags & TDF_DETAILS))
1023         {
1024           if (loop_loc != UNKNOWN_LOC)
1025             fprintf (dump_file, "\n%s:%d: note: ",
1026                      LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1027           fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
1028         }
1029       return NULL;
1030     }
1031
1032   if (e == exit_e)
1033     {
1034       /* NEW_LOOP was placed after LOOP.  */
1035       first_loop = loop;
1036       second_loop = new_loop;
1037     }
1038   else
1039     {
1040       /* NEW_LOOP was placed before LOOP.  */
1041       first_loop = new_loop;
1042       second_loop = loop;
1043     }
1044
1045   definitions = marked_ssa_names ();
1046   allocate_new_names (definitions);
1047   slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1048   rename_variables_in_loop (new_loop);
1049
1050
1051   /* 2. Add the guard that controls whether the first loop is executed.
1052         Resulting CFG would be:
1053
1054         bb_before_first_loop:
1055         if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1056                                GOTO first-loop
1057
1058         first_loop:
1059         do {
1060         } while ...
1061
1062         bb_before_second_loop:
1063
1064         second_loop:
1065         do {
1066         } while ...
1067
1068         orig_exit_bb:
1069    */
1070
1071   bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
1072   add_bb_to_loop (bb_before_first_loop, first_loop->outer);
1073   bb_before_second_loop = split_edge (first_loop->exit_edges[0]);
1074   add_bb_to_loop (bb_before_second_loop, first_loop->outer);
1075   flow_loop_scan (first_loop, LOOP_ALL);
1076   flow_loop_scan (second_loop, LOOP_ALL);
1077
1078   pre_condition =
1079         build2 (LE_EXPR, boolean_type_node, first_niters, integer_zero_node);
1080   skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
1081                                   bb_before_second_loop, bb_before_first_loop);
1082   slpeel_update_phi_nodes_for_guard (skip_e, first_loop, true /* entry-phis */,
1083                                      first_loop == new_loop);
1084
1085
1086   /* 3. Add the guard that controls whether the second loop is executed.
1087         Resulting CFG would be:
1088
1089         bb_before_first_loop:
1090         if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1091                                GOTO first-loop
1092
1093         first_loop:
1094         do {
1095         } while ...
1096
1097         bb_between_loops:
1098         if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1099                                     GOTO bb_before_second_loop
1100
1101         bb_before_second_loop:
1102
1103         second_loop:
1104         do {
1105         } while ...
1106
1107         bb_after_second_loop:
1108
1109         orig_exit_bb:
1110    */
1111
1112   bb_between_loops = split_edge (first_loop->exit_edges[0]);
1113   add_bb_to_loop (bb_between_loops, first_loop->outer);
1114   bb_after_second_loop = split_edge (second_loop->exit_edges[0]);
1115   add_bb_to_loop (bb_after_second_loop, second_loop->outer);
1116   flow_loop_scan (first_loop, LOOP_ALL);
1117   flow_loop_scan (second_loop, LOOP_ALL);
1118
1119   pre_condition = build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
1120   skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
1121                                   bb_after_second_loop, bb_before_first_loop);
1122   slpeel_update_phi_nodes_for_guard (skip_e, second_loop, false /* exit-phis */,
1123                                      second_loop == new_loop);
1124
1125   /* Flow loop scan does not update loop->single_exit field.  */
1126   first_loop->single_exit = first_loop->exit_edges[0];
1127   second_loop->single_exit = second_loop->exit_edges[0];
1128
1129   /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1130    */
1131   if (update_first_loop_count)
1132     slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
1133
1134   free_new_names (definitions);
1135   BITMAP_XFREE (definitions);
1136   unmark_all_for_rewrite ();
1137
1138   return new_loop;
1139 }
1140
1141 /* Function vect_get_loop_location.
1142
1143    Extract the location of the loop in the source code.
1144    If the loop is not well formed for vectorization, an estimated
1145    location is calculated.
1146    Return the loop location if succeed and NULL if not.  */
1147
1148 static LOC
1149 find_loop_location (struct loop *loop)
1150 {
1151   tree node = NULL_TREE;
1152   basic_block bb;
1153   block_stmt_iterator si;
1154
1155   if (!loop)
1156     return UNKNOWN_LOC;
1157
1158   node = get_loop_exit_condition (loop);
1159
1160   if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node)
1161       && EXPR_FILENAME (node) && EXPR_LINENO (node))
1162     return EXPR_LOC (node);
1163
1164   /* If we got here the loop is probably not "well formed",
1165      try to estimate the loop location */
1166
1167   if (!loop->header)
1168     return UNKNOWN_LOC;
1169
1170   bb = loop->header;
1171
1172   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1173     {
1174       node = bsi_stmt (si);
1175       if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node))
1176         return EXPR_LOC (node);
1177     }
1178
1179   return UNKNOWN_LOC;
1180 }
1181
1182
1183 /*************************************************************************
1184   Vectorization Debug Information.
1185  *************************************************************************/
1186
1187 /* Function vect_set_verbosity_level.
1188
1189    Called from toplev.c upon detection of the
1190    -ftree-vectorizer-verbose=N option.  */
1191
1192 void
1193 vect_set_verbosity_level (const char *val)
1194 {
1195    unsigned int vl;
1196
1197    vl = atoi (val);
1198    if (vl < MAX_VERBOSITY_LEVEL)
1199      vect_verbosity_level = vl;
1200    else
1201      vect_verbosity_level = MAX_VERBOSITY_LEVEL - 1;
1202 }
1203
1204
1205 /* Function vect_set_dump_settings.
1206
1207    Fix the verbosity level of the vectorizer if the
1208    requested level was not set explicitly using the flag
1209    -ftree-vectorizer-verbose=N.
1210    Decide where to print the debugging information (dump_file/stderr).
1211    If the user defined the verbosity level, but there is no dump file,
1212    print to stderr, otherwise print to the dump file.  */
1213
1214 static void
1215 vect_set_dump_settings (void)
1216 {
1217   vect_dump = dump_file;
1218
1219   /* Check if the verbosity level was defined by the user:  */
1220   if (vect_verbosity_level != MAX_VERBOSITY_LEVEL)
1221     {
1222       /* If there is no dump file, print to stderr.  */
1223       if (!dump_file)
1224         vect_dump = stderr;
1225       return;
1226     }
1227
1228   /* User didn't specify verbosity level:  */
1229   if (dump_file && (dump_flags & TDF_DETAILS))
1230     vect_verbosity_level = REPORT_DETAILS;
1231   else if (dump_file && (dump_flags & TDF_STATS))
1232     vect_verbosity_level = REPORT_UNVECTORIZED_LOOPS;
1233   else
1234     vect_verbosity_level = REPORT_NONE;
1235
1236   gcc_assert (dump_file || vect_verbosity_level == REPORT_NONE);
1237 }
1238
1239
1240 /* Function debug_loop_details.
1241
1242    For vectorization debug dumps.  */
1243
1244 static bool
1245 vect_print_dump_info (enum verbosity_levels vl, LOC loc)
1246 {
1247   if (vl > vect_verbosity_level)
1248     return false;
1249
1250   if (loc == UNKNOWN_LOC)
1251     fprintf (vect_dump, "\n%s:%d: note: ",
1252                  DECL_SOURCE_FILE (current_function_decl),
1253                  DECL_SOURCE_LINE (current_function_decl));
1254   else
1255     fprintf (vect_dump, "\n%s:%d: note: ", LOC_FILE (loc), LOC_LINE (loc));
1256
1257
1258   return true;
1259 }
1260
1261
1262 \f
1263 /* Here the proper Vectorizer starts.  */
1264
1265 /*************************************************************************
1266   Vectorization Utilities.
1267  *************************************************************************/
1268
1269 /* Function new_stmt_vec_info.
1270
1271    Create and initialize a new stmt_vec_info struct for STMT.  */
1272
1273 stmt_vec_info
1274 new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
1275 {
1276   stmt_vec_info res;
1277   res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
1278
1279   STMT_VINFO_TYPE (res) = undef_vec_info_type;
1280   STMT_VINFO_STMT (res) = stmt;
1281   STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
1282   STMT_VINFO_RELEVANT_P (res) = 0;
1283   STMT_VINFO_VECTYPE (res) = NULL;
1284   STMT_VINFO_VEC_STMT (res) = NULL;
1285   STMT_VINFO_DATA_REF (res) = NULL;
1286   STMT_VINFO_MEMTAG (res) = NULL;
1287   STMT_VINFO_VECT_DR_BASE_ADDRESS (res) = NULL;
1288   STMT_VINFO_VECT_INIT_OFFSET (res) = NULL_TREE;
1289   STMT_VINFO_VECT_STEP (res) = NULL_TREE;
1290   STMT_VINFO_VECT_BASE_ALIGNED_P (res) = false;
1291   STMT_VINFO_VECT_MISALIGNMENT (res) = NULL_TREE;
1292
1293   return res;
1294 }
1295
1296
1297 /* Function new_loop_vec_info.
1298
1299    Create and initialize a new loop_vec_info struct for LOOP, as well as
1300    stmt_vec_info structs for all the stmts in LOOP.  */
1301
1302 loop_vec_info
1303 new_loop_vec_info (struct loop *loop)
1304 {
1305   loop_vec_info res;
1306   basic_block *bbs;
1307   block_stmt_iterator si;
1308   unsigned int i;
1309
1310   res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
1311
1312   bbs = get_loop_body (loop);
1313
1314   /* Create stmt_info for all stmts in the loop.  */
1315   for (i = 0; i < loop->num_nodes; i++)
1316     {
1317       basic_block bb = bbs[i];
1318       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1319         {
1320           tree stmt = bsi_stmt (si);
1321           stmt_ann_t ann;
1322
1323           get_stmt_operands (stmt);
1324           ann = stmt_ann (stmt);
1325           set_stmt_info (ann, new_stmt_vec_info (stmt, res));
1326         }
1327     }
1328
1329   LOOP_VINFO_LOOP (res) = loop;
1330   LOOP_VINFO_BBS (res) = bbs;
1331   LOOP_VINFO_EXIT_COND (res) = NULL;
1332   LOOP_VINFO_NITERS (res) = NULL;
1333   LOOP_VINFO_VECTORIZABLE_P (res) = 0;
1334   LOOP_DO_PEELING_FOR_ALIGNMENT (res) = false;
1335   LOOP_VINFO_VECT_FACTOR (res) = 0;
1336   VARRAY_GENERIC_PTR_INIT (LOOP_VINFO_DATAREF_WRITES (res), 20,
1337                            "loop_write_datarefs");
1338   VARRAY_GENERIC_PTR_INIT (LOOP_VINFO_DATAREF_READS (res), 20,
1339                            "loop_read_datarefs");
1340   LOOP_VINFO_UNALIGNED_DR (res) = NULL;
1341   LOOP_VINFO_LOC (res) = UNKNOWN_LOC;
1342
1343   return res;
1344 }
1345
1346
1347 /* Function destroy_loop_vec_info.
1348
1349    Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
1350    stmts in the loop.  */
1351
1352 void
1353 destroy_loop_vec_info (loop_vec_info loop_vinfo)
1354 {
1355   struct loop *loop;
1356   basic_block *bbs;
1357   int nbbs;
1358   block_stmt_iterator si;
1359   int j;
1360
1361   if (!loop_vinfo)
1362     return;
1363
1364   loop = LOOP_VINFO_LOOP (loop_vinfo);
1365
1366   bbs = LOOP_VINFO_BBS (loop_vinfo);
1367   nbbs = loop->num_nodes;
1368
1369   for (j = 0; j < nbbs; j++)
1370     {
1371       basic_block bb = bbs[j];
1372       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1373         {
1374           tree stmt = bsi_stmt (si);
1375           stmt_ann_t ann = stmt_ann (stmt);
1376           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1377           free (stmt_info);
1378           set_stmt_info (ann, NULL);
1379         }
1380     }
1381
1382   free (LOOP_VINFO_BBS (loop_vinfo));
1383   varray_clear (LOOP_VINFO_DATAREF_WRITES (loop_vinfo));
1384   varray_clear (LOOP_VINFO_DATAREF_READS (loop_vinfo));
1385
1386   free (loop_vinfo);
1387 }
1388
1389
1390 /* Function vect_get_ptr_offset
1391
1392    Compute the OFFSET modulo vector-type alignment of pointer REF in bits.  */
1393
1394 static tree
1395 vect_get_ptr_offset (tree ref ATTRIBUTE_UNUSED,
1396                      tree vectype ATTRIBUTE_UNUSED,
1397                      tree *offset ATTRIBUTE_UNUSED)
1398 {
1399   /* TODO: Use alignment information.  */
1400   return NULL_TREE;
1401 }
1402
1403
1404 /* Function vect_strip_conversions
1405
1406    Strip conversions that don't narrow the mode.  */
1407
1408 static tree
1409 vect_strip_conversion (tree expr)
1410 {
1411   tree to, ti, oprnd0;
1412
1413   while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1414     {
1415       to = TREE_TYPE (expr);
1416       oprnd0 = TREE_OPERAND (expr, 0);
1417       ti = TREE_TYPE (oprnd0);
1418
1419       if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1420         return NULL_TREE;
1421       if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1422         return NULL_TREE;
1423
1424       expr = oprnd0;
1425     }
1426   return expr;
1427 }
1428
1429
1430 /* Function vect_analyze_offset_expr
1431
1432    Given an offset expression EXPR received from get_inner_reference, analyze
1433    it and create an expression for INITIAL_OFFSET by substituting the variables
1434    of EXPR with initial_condition of the corresponding access_fn in the loop.
1435    E.g.,
1436       for i
1437          for (j = 3; j < N; j++)
1438             a[j].b[i][j] = 0;
1439
1440    For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1441    substituted, since its access_fn in the inner loop is i. 'j' will be
1442    substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1443    C` =  3 * C_j + C.
1444
1445    Compute MISALIGN (the misalignment of the data reference initial access from
1446    its base) if possible. Misalignment can be calculated only if all the
1447    variables can be substituted with constants, or if a variable is multiplied
1448    by a multiple of VECTYPE_ALIGNMENT. In the above example, since 'i' cannot
1449    be substituted, MISALIGN will be NULL_TREE in case that C_i is not a multiple
1450    of VECTYPE_ALIGNMENT, and C` otherwise. (We perform MISALIGN modulo
1451    VECTYPE_ALIGNMENT computation in the caller of this function).
1452
1453    STEP is an evolution of the data reference in this loop in bytes.
1454    In the above example, STEP is C_j.
1455
1456    Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1457    variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN and STEP)
1458    are NULL_TREEs. Otherwise, return TRUE.
1459
1460 */
1461
1462 static bool
1463 vect_analyze_offset_expr (tree expr,
1464                           struct loop *loop,
1465                           tree vectype_alignment,
1466                           tree *initial_offset,
1467                           tree *misalign,
1468                           tree *step)
1469 {
1470   tree oprnd0;
1471   tree oprnd1;
1472   tree left_offset = ssize_int (0);
1473   tree right_offset = ssize_int (0);
1474   tree left_misalign = ssize_int (0);
1475   tree right_misalign = ssize_int (0);
1476   tree left_step = ssize_int (0);
1477   tree right_step = ssize_int (0);
1478   enum tree_code code;
1479   tree init, evolution;
1480
1481   *step = NULL_TREE;
1482   *misalign = NULL_TREE;
1483   *initial_offset = NULL_TREE;
1484
1485   /* Strip conversions that don't narrow the mode.  */
1486   expr = vect_strip_conversion (expr);
1487   if (!expr)
1488     return false;
1489
1490   /* Stop conditions:
1491      1. Constant.  */
1492   if (TREE_CODE (expr) == INTEGER_CST)
1493     {
1494       *initial_offset = fold_convert (ssizetype, expr);
1495       *misalign = fold_convert (ssizetype, expr);
1496       *step = ssize_int (0);
1497       return true;
1498     }
1499
1500   /* 2. Variable. Try to substitute with initial_condition of the corresponding
1501      access_fn in the current loop.  */
1502   if (SSA_VAR_P (expr))
1503     {
1504       tree access_fn = analyze_scalar_evolution (loop, expr);
1505
1506       if (access_fn == chrec_dont_know)
1507         /* No access_fn.  */
1508         return false;
1509
1510       init = initial_condition_in_loop_num (access_fn, loop->num);
1511       if (init == expr && !expr_invariant_in_loop_p (loop, init))
1512         /* Not enough information: may be not loop invariant.
1513            E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1514            initial_condition is D, but it depends on i - loop's induction
1515            variable.  */
1516         return false;
1517
1518       evolution = evolution_part_in_loop_num (access_fn, loop->num);
1519       if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1520         /* Evolution is not constant.  */
1521         return false;
1522
1523       if (TREE_CODE (init) == INTEGER_CST)
1524         *misalign = fold_convert (ssizetype, init);
1525       else
1526         /* Not constant, misalignment cannot be calculated.  */
1527         *misalign = NULL_TREE;
1528
1529       *initial_offset = fold_convert (ssizetype, init);
1530
1531       *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1532       return true;
1533     }
1534
1535   /* Recursive computation.  */
1536   if (!BINARY_CLASS_P (expr))
1537     {
1538       /* We expect to get binary expressions (PLUS/MINUS and MULT).  */
1539       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1540         {
1541           fprintf (vect_dump, "Not binary expression ");
1542           print_generic_expr (vect_dump, expr, TDF_SLIM);
1543         }
1544       return false;
1545     }
1546   oprnd0 = TREE_OPERAND (expr, 0);
1547   oprnd1 = TREE_OPERAND (expr, 1);
1548
1549   if (!vect_analyze_offset_expr (oprnd0, loop, vectype_alignment, &left_offset,
1550                                 &left_misalign, &left_step)
1551       || !vect_analyze_offset_expr (oprnd1, loop, vectype_alignment,
1552                                    &right_offset, &right_misalign, &right_step))
1553     return false;
1554
1555   /* The type of the operation: plus, minus or mult.  */
1556   code = TREE_CODE (expr);
1557   switch (code)
1558     {
1559     case MULT_EXPR:
1560       if (TREE_CODE (right_offset) != INTEGER_CST)
1561         /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1562            sized types.
1563            FORNOW: We don't support such cases.  */
1564         return false;
1565
1566       /* Strip conversions that don't narrow the mode.  */
1567       left_offset = vect_strip_conversion (left_offset);
1568       if (!left_offset)
1569         return false;
1570       /* Misalignment computation.  */
1571       if (SSA_VAR_P (left_offset))
1572         {
1573           /* If the left side contains variables that can't be substituted with
1574              constants, we check if the right side is a multiple of ALIGNMENT.
1575            */
1576           if (integer_zerop (size_binop (TRUNC_MOD_EXPR, right_offset,
1577                                   fold_convert (ssizetype, vectype_alignment))))
1578             *misalign = ssize_int (0);
1579           else
1580             /* If the remainder is not zero or the right side isn't constant,
1581                we can't compute  misalignment.  */
1582             *misalign = NULL_TREE;
1583         }
1584       else
1585         {
1586           /* The left operand was successfully substituted with constant.  */
1587           if (left_misalign)
1588             /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1589                NULL_TREE.  */
1590             *misalign  = size_binop (code, left_misalign, right_misalign);
1591           else
1592             *misalign = NULL_TREE;
1593         }
1594
1595       /* Step calculation.  */
1596       /* Multiply the step by the right operand.  */
1597       *step  = size_binop (MULT_EXPR, left_step, right_offset);
1598       break;
1599
1600     case PLUS_EXPR:
1601     case MINUS_EXPR:
1602       /* Combine the recursive calculations for step and misalignment.  */
1603       *step = size_binop (code, left_step, right_step);
1604
1605       if (left_misalign && right_misalign)
1606         *misalign  = size_binop (code, left_misalign, right_misalign);
1607       else
1608         *misalign = NULL_TREE;
1609
1610       break;
1611
1612     default:
1613       gcc_unreachable ();
1614     }
1615
1616   /* Compute offset.  */
1617   *initial_offset = fold_convert (ssizetype,
1618                                   fold (build2 (code, TREE_TYPE (left_offset),
1619                                                 left_offset,
1620                                                 right_offset)));
1621   return true;
1622 }
1623
1624
1625 /* Function vect_force_dr_alignment_p.
1626
1627    Returns whether the alignment of a DECL can be forced to be aligned
1628    on ALIGNMENT bit boundary.  */
1629
1630 static bool
1631 vect_can_force_dr_alignment_p (tree decl, unsigned int alignment)
1632 {
1633   if (TREE_CODE (decl) != VAR_DECL)
1634     return false;
1635
1636   if (DECL_EXTERNAL (decl))
1637     return false;
1638
1639   if (TREE_ASM_WRITTEN (decl))
1640     return false;
1641
1642   if (TREE_STATIC (decl))
1643     return (alignment <= MAX_OFILE_ALIGNMENT);
1644   else
1645     /* This is not 100% correct.  The absolute correct stack alignment
1646        is STACK_BOUNDARY.  We're supposed to hope, but not assume, that
1647        PREFERRED_STACK_BOUNDARY is honored by all translation units.
1648        However, until someone implements forced stack alignment, SSE
1649        isn't really usable without this.  */
1650     return (alignment <= PREFERRED_STACK_BOUNDARY);
1651 }
1652
1653
1654 /* Function vect_get_new_vect_var.
1655
1656    Returns a name for a new variable. The current naming scheme appends the
1657    prefix "vect_" or "vect_p" (depending on the value of VAR_KIND) to
1658    the name of vectorizer generated variables, and appends that to NAME if
1659    provided.  */
1660
1661 static tree
1662 vect_get_new_vect_var (tree type, enum vect_var_kind var_kind, const char *name)
1663 {
1664   const char *prefix;
1665   int prefix_len;
1666   tree new_vect_var;
1667
1668   if (var_kind == vect_simple_var)
1669     prefix = "vect_";
1670   else
1671     prefix = "vect_p";
1672
1673   prefix_len = strlen (prefix);
1674
1675   if (name)
1676     new_vect_var = create_tmp_var (type, concat (prefix, name, NULL));
1677   else
1678     new_vect_var = create_tmp_var (type, prefix);
1679
1680   return new_vect_var;
1681 }
1682
1683
1684 /* Function vect_create_index_for_vector_ref.
1685
1686    Create (and return) an index variable, along with it's update chain in the
1687    loop. This variable will be used to access a memory location in a vector
1688    operation.
1689
1690    Input:
1691    LOOP: The loop being vectorized.
1692    BSI: The block_stmt_iterator where STMT is. Any new stmts created by this
1693         function can be added here, or in the loop pre-header.
1694
1695    Output:
1696    Return an index that will be used to index a vector array.  It is expected
1697    that a pointer to the first vector will be used as the base address for the
1698    indexed reference.
1699
1700    FORNOW: we are not trying to be efficient, just creating a new index each
1701    time from scratch.  At this time all vector references could use the same
1702    index.
1703
1704    TODO: create only one index to be used by all vector references.  Record
1705    the index in the LOOP_VINFO the first time this procedure is called and
1706    return it on subsequent calls.  The increment of this index must be placed
1707    just before the conditional expression that ends the single block loop.  */
1708
1709 static tree
1710 vect_create_index_for_vector_ref (loop_vec_info loop_vinfo)
1711 {
1712   tree init, step;
1713   block_stmt_iterator incr_bsi;
1714   bool insert_after;
1715   tree indx_before_incr, indx_after_incr;
1716   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1717   tree incr;
1718
1719   /* It is assumed that the base pointer used for vectorized access contains
1720      the address of the first vector.  Therefore the index used for vectorized
1721      access must be initialized to zero and incremented by 1.  */
1722
1723   init = integer_zero_node;
1724   step = integer_one_node;
1725
1726   standard_iv_increment_position (loop, &incr_bsi, &insert_after);
1727   create_iv (init, step, NULL_TREE, loop, &incr_bsi, insert_after,
1728         &indx_before_incr, &indx_after_incr);
1729   incr = bsi_stmt (incr_bsi);
1730   get_stmt_operands (incr);
1731   set_stmt_info (stmt_ann (incr), new_stmt_vec_info (incr, loop_vinfo));
1732
1733   return indx_before_incr;
1734 }
1735
1736
1737 /* Function vect_create_addr_base_for_vector_ref.
1738
1739    Create an expression that computes the address of the first memory location
1740    that will be accessed for a data reference.
1741
1742    Input:
1743    STMT: The statement containing the data reference.
1744    NEW_STMT_LIST: Must be initialized to NULL_TREE or a statement list.
1745    OFFSET: Optional. If supplied, it is be added to the initial address.
1746
1747    Output:
1748    1. Return an SSA_NAME whose value is the address of the memory location of
1749       the first vector of the data reference.
1750    2. If new_stmt_list is not NULL_TREE after return then the caller must insert
1751       these statement(s) which define the returned SSA_NAME.
1752
1753    FORNOW: We are only handling array accesses with step 1.  */
1754
1755 static tree
1756 vect_create_addr_base_for_vector_ref (tree stmt,
1757                                       tree *new_stmt_list,
1758                                       tree offset)
1759 {
1760   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1761   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
1762   tree data_ref_base =
1763     unshare_expr (STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info));
1764   tree base_name = build_fold_indirect_ref (data_ref_base);
1765   tree ref = DR_REF (dr);
1766   tree scalar_type = TREE_TYPE (ref);
1767   tree scalar_ptr_type = build_pointer_type (scalar_type);
1768   tree vec_stmt;
1769   tree new_temp;
1770   tree addr_base, addr_expr;
1771   tree dest, new_stmt;
1772   tree base_offset = unshare_expr (STMT_VINFO_VECT_INIT_OFFSET (stmt_info));
1773
1774   /* Create base_offset */
1775   dest = create_tmp_var (TREE_TYPE (base_offset), "base_off");
1776   add_referenced_tmp_var (dest);
1777   base_offset = force_gimple_operand (base_offset, &new_stmt, false, dest);
1778   append_to_statement_list_force (new_stmt, new_stmt_list);
1779
1780   if (offset)
1781     {
1782       tree tmp = create_tmp_var (TREE_TYPE (base_offset), "offset");
1783       add_referenced_tmp_var (tmp);
1784       offset = fold (build2 (MULT_EXPR, TREE_TYPE (offset), offset,
1785                              STMT_VINFO_VECT_STEP (stmt_info)));
1786       base_offset = fold (build2 (PLUS_EXPR, TREE_TYPE (base_offset),
1787                                   base_offset, offset));
1788       base_offset = force_gimple_operand (base_offset, &new_stmt, false, tmp);
1789       append_to_statement_list_force (new_stmt, new_stmt_list);
1790     }
1791
1792   /* base + base_offset */
1793   addr_base = fold (build2 (PLUS_EXPR, TREE_TYPE (data_ref_base), data_ref_base,
1794                             base_offset));
1795
1796   /* addr_expr = addr_base */
1797   addr_expr = vect_get_new_vect_var (scalar_ptr_type, vect_pointer_var,
1798                                      get_name (base_name));
1799   add_referenced_tmp_var (addr_expr);
1800   vec_stmt = build2 (MODIFY_EXPR, void_type_node, addr_expr, addr_base);
1801   new_temp = make_ssa_name (addr_expr, vec_stmt);
1802   TREE_OPERAND (vec_stmt, 0) = new_temp;
1803   append_to_statement_list_force (vec_stmt, new_stmt_list);
1804
1805   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1806     {
1807       fprintf (vect_dump, "created ");
1808       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
1809     }
1810   return new_temp;
1811 }
1812
1813
1814 /* Function get_vectype_for_scalar_type.
1815
1816    Returns the vector type corresponding to SCALAR_TYPE as supported
1817    by the target.  */
1818
1819 static tree
1820 get_vectype_for_scalar_type (tree scalar_type)
1821 {
1822   enum machine_mode inner_mode = TYPE_MODE (scalar_type);
1823   int nbytes = GET_MODE_SIZE (inner_mode);
1824   int nunits;
1825   tree vectype;
1826
1827   if (nbytes == 0)
1828     return NULL_TREE;
1829
1830   /* FORNOW: Only a single vector size per target (UNITS_PER_SIMD_WORD)
1831      is expected.  */
1832   nunits = UNITS_PER_SIMD_WORD / nbytes;
1833
1834   vectype = build_vector_type (scalar_type, nunits);
1835   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1836     {
1837       fprintf (vect_dump, "get vectype with %d units of type ", nunits);
1838       print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
1839     }
1840
1841   if (!vectype)
1842     return NULL_TREE;
1843
1844   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1845     {
1846       fprintf (vect_dump, "vectype: ");
1847       print_generic_expr (vect_dump, vectype, TDF_SLIM);
1848     }
1849
1850   if (!VECTOR_MODE_P (TYPE_MODE (vectype)))
1851     {
1852       /* TODO: tree-complex.c sometimes can parallelize operations
1853          on generic vectors.  We can vectorize the loop in that case,
1854          but then we should re-run the lowering pass.  */
1855       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1856         fprintf (vect_dump, "mode not supported by target.");
1857       return NULL_TREE;
1858     }
1859
1860   return vectype;
1861 }
1862
1863
1864 /* Function vect_align_data_ref.
1865
1866    Handle mislignment of a memory accesses.
1867
1868    FORNOW: Can't handle misaligned accesses.
1869    Make sure that the dataref is aligned.  */
1870
1871 static void
1872 vect_align_data_ref (tree stmt)
1873 {
1874   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1875   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
1876
1877   /* FORNOW: can't handle misaligned accesses;
1878              all accesses expected to be aligned.  */
1879   gcc_assert (aligned_access_p (dr));
1880 }
1881
1882
1883 /* Function vect_create_data_ref_ptr.
1884
1885    Create a memory reference expression for vector access, to be used in a
1886    vector load/store stmt. The reference is based on a new pointer to vector
1887    type (vp).
1888
1889    Input:
1890    1. STMT: a stmt that references memory. Expected to be of the form
1891          MODIFY_EXPR <name, data-ref> or MODIFY_EXPR <data-ref, name>.
1892    2. BSI: block_stmt_iterator where new stmts can be added.
1893    3. OFFSET (optional): an offset to be added to the initial address accessed
1894         by the data-ref in STMT.
1895    4. ONLY_INIT: indicate if vp is to be updated in the loop, or remain
1896         pointing to the initial address.
1897
1898    Output:
1899    1. Declare a new ptr to vector_type, and have it point to the base of the
1900       data reference (initial addressed accessed by the data reference).
1901       For example, for vector of type V8HI, the following code is generated:
1902
1903       v8hi *vp;
1904       vp = (v8hi *)initial_address;
1905
1906       if OFFSET is not supplied:
1907          initial_address = &a[init];
1908       if OFFSET is supplied:
1909          initial_address = &a[init + OFFSET];
1910
1911       Return the initial_address in INITIAL_ADDRESS.
1912
1913    2. Create a data-reference in the loop based on the new vector pointer vp,
1914       and using a new index variable 'idx' as follows:
1915
1916       vp' = vp + update
1917
1918       where if ONLY_INIT is true:
1919          update = zero
1920       and otherwise
1921          update = idx + vector_type_size
1922
1923       Return the pointer vp'.
1924
1925
1926    FORNOW: handle only aligned and consecutive accesses.  */
1927
1928 static tree
1929 vect_create_data_ref_ptr (tree stmt, block_stmt_iterator *bsi, tree offset,
1930                           tree *initial_address, bool only_init)
1931 {
1932   tree base_name;
1933   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1934   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1935   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1936   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1937   tree vect_ptr_type;
1938   tree vect_ptr;
1939   tree tag;
1940   v_may_def_optype v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
1941   v_must_def_optype v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
1942   vuse_optype vuses = STMT_VUSE_OPS (stmt);
1943   int nvuses, nv_may_defs, nv_must_defs;
1944   int i;
1945   tree new_temp;
1946   tree vec_stmt;
1947   tree new_stmt_list = NULL_TREE;
1948   tree idx;
1949   edge pe = loop_preheader_edge (loop);
1950   basic_block new_bb;
1951   tree vect_ptr_init;
1952   tree vectype_size;
1953   tree ptr_update;
1954   tree data_ref_ptr;
1955   tree type, tmp, size;
1956
1957   base_name =  build_fold_indirect_ref (unshare_expr (
1958                       STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info)));
1959
1960   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
1961     {
1962       tree data_ref_base = base_name;
1963       fprintf (vect_dump, "create array_ref of type: ");
1964       print_generic_expr (vect_dump, vectype, TDF_SLIM);
1965       if (TREE_CODE (data_ref_base) == VAR_DECL)
1966         fprintf (vect_dump, "  vectorizing a one dimensional array ref: ");
1967       else if (TREE_CODE (data_ref_base) == ARRAY_REF)
1968         fprintf (vect_dump, "  vectorizing a multidimensional array ref: ");
1969       else if (TREE_CODE (data_ref_base) == COMPONENT_REF)
1970         fprintf (vect_dump, "  vectorizing a record based array ref: ");
1971       else if (TREE_CODE (data_ref_base) == SSA_NAME)
1972         fprintf (vect_dump, "  vectorizing a pointer ref: ");
1973       print_generic_expr (vect_dump, base_name, TDF_SLIM);
1974     }
1975
1976   /** (1) Create the new vector-pointer variable:  **/
1977
1978   vect_ptr_type = build_pointer_type (vectype);
1979   vect_ptr = vect_get_new_vect_var (vect_ptr_type, vect_pointer_var,
1980                                     get_name (base_name));
1981   add_referenced_tmp_var (vect_ptr);
1982
1983
1984   /** (2) Handle aliasing information of the new vector-pointer:  **/
1985
1986   tag = STMT_VINFO_MEMTAG (stmt_info);
1987   gcc_assert (tag);
1988   get_var_ann (vect_ptr)->type_mem_tag = tag;
1989
1990   /* Mark for renaming all aliased variables
1991      (i.e, the may-aliases of the type-mem-tag).  */
1992   nvuses = NUM_VUSES (vuses);
1993   nv_may_defs = NUM_V_MAY_DEFS (v_may_defs);
1994   nv_must_defs = NUM_V_MUST_DEFS (v_must_defs);
1995   for (i = 0; i < nvuses; i++)
1996     {
1997       tree use = VUSE_OP (vuses, i);
1998       if (TREE_CODE (use) == SSA_NAME)
1999         bitmap_set_bit (vars_to_rename, var_ann (SSA_NAME_VAR (use))->uid);
2000     }
2001   for (i = 0; i < nv_may_defs; i++)
2002     {
2003       tree def = V_MAY_DEF_RESULT (v_may_defs, i);
2004       if (TREE_CODE (def) == SSA_NAME)
2005         bitmap_set_bit (vars_to_rename, var_ann (SSA_NAME_VAR (def))->uid);
2006     }
2007   for (i = 0; i < nv_must_defs; i++)
2008     {
2009       tree def = V_MUST_DEF_RESULT (v_must_defs, i);
2010       if (TREE_CODE (def) == SSA_NAME)
2011         bitmap_set_bit (vars_to_rename, var_ann (SSA_NAME_VAR (def))->uid);
2012     }
2013
2014
2015   /** (3) Calculate the initial address the vector-pointer, and set
2016           the vector-pointer to point to it before the loop:  **/
2017
2018   /* Create: (&(base[init_val+offset]) in the loop preheader.  */
2019   new_temp = vect_create_addr_base_for_vector_ref (stmt, &new_stmt_list,
2020                                                    offset);
2021   pe = loop_preheader_edge (loop);
2022   new_bb = bsi_insert_on_edge_immediate (pe, new_stmt_list);
2023   gcc_assert (!new_bb);
2024   *initial_address = new_temp;
2025
2026   /* Create: p = (vectype *) initial_base  */
2027   vec_stmt = fold_convert (vect_ptr_type, new_temp);
2028   vec_stmt = build2 (MODIFY_EXPR, void_type_node, vect_ptr, vec_stmt);
2029   new_temp = make_ssa_name (vect_ptr, vec_stmt);
2030   TREE_OPERAND (vec_stmt, 0) = new_temp;
2031   new_bb = bsi_insert_on_edge_immediate (pe, vec_stmt);
2032   gcc_assert (!new_bb);
2033   vect_ptr_init = TREE_OPERAND (vec_stmt, 0);
2034
2035
2036   /** (4) Handle the updating of the vector-pointer inside the loop: **/
2037
2038   if (only_init) /* No update in loop is required.  */
2039     return vect_ptr_init;
2040
2041   idx = vect_create_index_for_vector_ref (loop_vinfo);
2042
2043   /* Create: update = idx * vectype_size  */
2044   tmp = create_tmp_var (integer_type_node, "update");
2045   add_referenced_tmp_var (tmp);
2046   size = TYPE_SIZE (vect_ptr_type);
2047   type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
2048   ptr_update = create_tmp_var (type, "update");
2049   add_referenced_tmp_var (ptr_update);
2050   vectype_size = TYPE_SIZE_UNIT (vectype);
2051   vec_stmt = build2 (MULT_EXPR, integer_type_node, idx, vectype_size);
2052   vec_stmt = build2 (MODIFY_EXPR, void_type_node, tmp, vec_stmt);
2053   new_temp = make_ssa_name (tmp, vec_stmt);
2054   TREE_OPERAND (vec_stmt, 0) = new_temp;
2055   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
2056   vec_stmt = fold_convert (type, new_temp);
2057   vec_stmt = build2 (MODIFY_EXPR, void_type_node, ptr_update, vec_stmt);
2058   new_temp = make_ssa_name (ptr_update, vec_stmt);
2059   TREE_OPERAND (vec_stmt, 0) = new_temp;
2060   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
2061
2062   /* Create: data_ref_ptr = vect_ptr_init + update  */
2063   vec_stmt = build2 (PLUS_EXPR, vect_ptr_type, vect_ptr_init, new_temp);
2064   vec_stmt = build2 (MODIFY_EXPR, void_type_node, vect_ptr, vec_stmt);
2065   new_temp = make_ssa_name (vect_ptr, vec_stmt);
2066   TREE_OPERAND (vec_stmt, 0) = new_temp;
2067   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
2068   data_ref_ptr = TREE_OPERAND (vec_stmt, 0);
2069
2070   return data_ref_ptr;
2071 }
2072
2073
2074 /* Function vect_create_destination_var.
2075
2076    Create a new temporary of type VECTYPE.  */
2077
2078 static tree
2079 vect_create_destination_var (tree scalar_dest, tree vectype)
2080 {
2081   tree vec_dest;
2082   const char *new_name;
2083
2084   gcc_assert (TREE_CODE (scalar_dest) == SSA_NAME);
2085
2086   new_name = get_name (scalar_dest);
2087   if (!new_name)
2088     new_name = "var_";
2089   vec_dest = vect_get_new_vect_var (vectype, vect_simple_var, new_name);
2090   add_referenced_tmp_var (vec_dest);
2091
2092   return vec_dest;
2093 }
2094
2095
2096 /* Function vect_init_vector.
2097
2098    Insert a new stmt (INIT_STMT) that initializes a new vector variable with
2099    the vector elements of VECTOR_VAR. Return the DEF of INIT_STMT. It will be
2100    used in the vectorization of STMT.  */
2101
2102 static tree
2103 vect_init_vector (tree stmt, tree vector_var)
2104 {
2105   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2106   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2107   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2108   tree new_var;
2109   tree init_stmt;
2110   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
2111   tree vec_oprnd;
2112   edge pe;
2113   tree new_temp;
2114   basic_block new_bb;
2115
2116   new_var = vect_get_new_vect_var (vectype, vect_simple_var, "cst_");
2117   add_referenced_tmp_var (new_var);
2118
2119   init_stmt = build2 (MODIFY_EXPR, vectype, new_var, vector_var);
2120   new_temp = make_ssa_name (new_var, init_stmt);
2121   TREE_OPERAND (init_stmt, 0) = new_temp;
2122
2123   pe = loop_preheader_edge (loop);
2124   new_bb = bsi_insert_on_edge_immediate (pe, init_stmt);
2125   gcc_assert (!new_bb);
2126
2127   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2128     {
2129       fprintf (vect_dump, "created new init_stmt: ");
2130       print_generic_expr (vect_dump, init_stmt, TDF_SLIM);
2131     }
2132
2133   vec_oprnd = TREE_OPERAND (init_stmt, 0);
2134   return vec_oprnd;
2135 }
2136
2137
2138 /* Function vect_get_vec_def_for_operand.
2139
2140    OP is an operand in STMT. This function returns a (vector) def that will be
2141    used in the vectorized stmt for STMT.
2142
2143    In the case that OP is an SSA_NAME which is defined in the loop, then
2144    STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
2145
2146    In case OP is an invariant or constant, a new stmt that creates a vector def
2147    needs to be introduced.  */
2148
2149 static tree
2150 vect_get_vec_def_for_operand (tree op, tree stmt)
2151 {
2152   tree vec_oprnd;
2153   tree vec_stmt;
2154   tree def_stmt;
2155   stmt_vec_info def_stmt_info = NULL;
2156   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
2157   tree vectype = STMT_VINFO_VECTYPE (stmt_vinfo);
2158   int nunits = GET_MODE_NUNITS (TYPE_MODE (vectype));
2159   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
2160   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2161   basic_block bb;
2162   tree vec_inv;
2163   tree t = NULL_TREE;
2164   tree def;
2165   int i;
2166
2167   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2168     {
2169       fprintf (vect_dump, "vect_get_vec_def_for_operand: ");
2170       print_generic_expr (vect_dump, op, TDF_SLIM);
2171     }
2172
2173   /** ===> Case 1: operand is a constant.  **/
2174
2175   if (TREE_CODE (op) == INTEGER_CST || TREE_CODE (op) == REAL_CST)
2176     {
2177       /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
2178
2179       tree vec_cst;
2180
2181       /* Build a tree with vector elements.  */
2182       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2183         fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
2184
2185       for (i = nunits - 1; i >= 0; --i)
2186         {
2187           t = tree_cons (NULL_TREE, op, t);
2188         }
2189       vec_cst = build_vector (vectype, t);
2190       return vect_init_vector (stmt, vec_cst);
2191     }
2192
2193   gcc_assert (TREE_CODE (op) == SSA_NAME);
2194
2195   /** ===> Case 2: operand is an SSA_NAME - find the stmt that defines it.  **/
2196
2197   def_stmt = SSA_NAME_DEF_STMT (op);
2198   def_stmt_info = vinfo_for_stmt (def_stmt);
2199
2200   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2201     {
2202       fprintf (vect_dump, "vect_get_vec_def_for_operand: def_stmt: ");
2203       print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
2204     }
2205
2206
2207   /** ==> Case 2.1: operand is defined inside the loop.  **/
2208
2209   if (def_stmt_info)
2210     {
2211       /* Get the def from the vectorized stmt.  */
2212
2213       vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
2214       gcc_assert (vec_stmt);
2215       vec_oprnd = TREE_OPERAND (vec_stmt, 0);
2216       return vec_oprnd;
2217     }
2218
2219
2220   /** ==> Case 2.2: operand is defined by the loop-header phi-node -
2221                     it is a reduction/induction.  **/
2222
2223   bb = bb_for_stmt (def_stmt);
2224   if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb))
2225     {
2226       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2227         fprintf (vect_dump, "reduction/induction - unsupported.");
2228       internal_error ("no support for reduction/induction"); /* FORNOW */
2229     }
2230
2231
2232   /** ==> Case 2.3: operand is defined outside the loop -
2233                     it is a loop invariant.  */
2234
2235   switch (TREE_CODE (def_stmt))
2236     {
2237     case PHI_NODE:
2238       def = PHI_RESULT (def_stmt);
2239       break;
2240     case MODIFY_EXPR:
2241       def = TREE_OPERAND (def_stmt, 0);
2242       break;
2243     case NOP_EXPR:
2244       def = TREE_OPERAND (def_stmt, 0);
2245       gcc_assert (IS_EMPTY_STMT (def_stmt));
2246       def = op;
2247       break;
2248     default:
2249       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2250         {
2251           fprintf (vect_dump, "unsupported defining stmt: ");
2252           print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
2253         }
2254       internal_error ("unsupported defining stmt");
2255     }
2256
2257   /* Build a tree with vector elements.
2258      Create 'vec_inv = {inv,inv,..,inv}'  */
2259
2260   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2261     fprintf (vect_dump, "Create vector_inv.");
2262
2263   for (i = nunits - 1; i >= 0; --i)
2264     {
2265       t = tree_cons (NULL_TREE, def, t);
2266     }
2267
2268   vec_inv = build_constructor (vectype, t);
2269   return vect_init_vector (stmt, vec_inv);
2270 }
2271
2272
2273 /* Function vect_finish_stmt_generation.
2274
2275    Insert a new stmt.  */
2276
2277 static void
2278 vect_finish_stmt_generation (tree stmt, tree vec_stmt, block_stmt_iterator *bsi)
2279 {
2280   bsi_insert_before (bsi, vec_stmt, BSI_SAME_STMT);
2281
2282   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2283     {
2284       fprintf (vect_dump, "add new stmt: ");
2285       print_generic_expr (vect_dump, vec_stmt, TDF_SLIM);
2286     }
2287
2288 #ifdef ENABLE_CHECKING
2289   /* Make sure bsi points to the stmt that is being vectorized.  */
2290   gcc_assert (stmt == bsi_stmt (*bsi));
2291 #endif
2292
2293 #ifdef USE_MAPPED_LOCATION
2294   SET_EXPR_LOCATION (vec_stmt, EXPR_LOCUS (stmt));
2295 #else
2296   SET_EXPR_LOCUS (vec_stmt, EXPR_LOCUS (stmt));
2297 #endif
2298 }
2299
2300
2301 /* Function vectorizable_assignment.
2302
2303    Check if STMT performs an assignment (copy) that can be vectorized.
2304    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2305    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2306    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2307
2308 static bool
2309 vectorizable_assignment (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
2310 {
2311   tree vec_dest;
2312   tree scalar_dest;
2313   tree op;
2314   tree vec_oprnd;
2315   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2316   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2317   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2318   tree new_temp;
2319
2320   /* Is vectorizable assignment?  */
2321
2322   if (TREE_CODE (stmt) != MODIFY_EXPR)
2323     return false;
2324
2325   scalar_dest = TREE_OPERAND (stmt, 0);
2326   if (TREE_CODE (scalar_dest) != SSA_NAME)
2327     return false;
2328
2329   op = TREE_OPERAND (stmt, 1);
2330   if (!vect_is_simple_use (op, loop_vinfo, NULL))
2331     {
2332       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2333         fprintf (vect_dump, "use not simple.");
2334       return false;
2335     }
2336
2337   if (!vec_stmt) /* transformation not required.  */
2338     {
2339       STMT_VINFO_TYPE (stmt_info) = assignment_vec_info_type;
2340       return true;
2341     }
2342
2343   /** Transform.  **/
2344   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2345     fprintf (vect_dump, "transform assignment.");
2346
2347   /* Handle def.  */
2348   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2349
2350   /* Handle use.  */
2351   op = TREE_OPERAND (stmt, 1);
2352   vec_oprnd = vect_get_vec_def_for_operand (op, stmt);
2353
2354   /* Arguments are ready. create the new vector stmt.  */
2355   *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, vec_oprnd);
2356   new_temp = make_ssa_name (vec_dest, *vec_stmt);
2357   TREE_OPERAND (*vec_stmt, 0) = new_temp;
2358   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
2359
2360   return true;
2361 }
2362
2363
2364 /* Function vectorizable_operation.
2365
2366    Check if STMT performs a binary or unary operation that can be vectorized.
2367    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2368    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2369    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2370
2371 static bool
2372 vectorizable_operation (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
2373 {
2374   tree vec_dest;
2375   tree scalar_dest;
2376   tree operation;
2377   tree op0, op1 = NULL;
2378   tree vec_oprnd0, vec_oprnd1=NULL;
2379   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2380   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2381   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2382   int i;
2383   enum tree_code code;
2384   enum machine_mode vec_mode;
2385   tree new_temp;
2386   int op_type;
2387   tree op;
2388   optab optab;
2389
2390   /* Is STMT a vectorizable binary/unary operation?   */
2391   if (TREE_CODE (stmt) != MODIFY_EXPR)
2392     return false;
2393
2394   if (TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
2395     return false;
2396
2397   operation = TREE_OPERAND (stmt, 1);
2398   code = TREE_CODE (operation);
2399   optab = optab_for_tree_code (code, vectype);
2400
2401   /* Support only unary or binary operations.  */
2402   op_type = TREE_CODE_LENGTH (code);
2403   if (op_type != unary_op && op_type != binary_op)
2404     {
2405       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2406         fprintf (vect_dump, "num. args = %d (not unary/binary op).", op_type);
2407       return false;
2408     }
2409
2410   for (i = 0; i < op_type; i++)
2411     {
2412       op = TREE_OPERAND (operation, i);
2413       if (!vect_is_simple_use (op, loop_vinfo, NULL))
2414         {
2415           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2416             fprintf (vect_dump, "use not simple.");
2417           return false;
2418         }
2419     }
2420
2421   /* Supportable by target?  */
2422   if (!optab)
2423     {
2424       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2425         fprintf (vect_dump, "no optab.");
2426       return false;
2427     }
2428   vec_mode = TYPE_MODE (vectype);
2429   if (optab->handlers[(int) vec_mode].insn_code == CODE_FOR_nothing)
2430     {
2431       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2432         fprintf (vect_dump, "op not supported by target.");
2433       return false;
2434     }
2435
2436   if (!vec_stmt) /* transformation not required.  */
2437     {
2438       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
2439       return true;
2440     }
2441
2442   /** Transform.  **/
2443
2444   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2445     fprintf (vect_dump, "transform binary/unary operation.");
2446
2447   /* Handle def.  */
2448   scalar_dest = TREE_OPERAND (stmt, 0);
2449   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2450
2451   /* Handle uses.  */
2452   op0 = TREE_OPERAND (operation, 0);
2453   vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt);
2454
2455   if (op_type == binary_op)
2456     {
2457       op1 = TREE_OPERAND (operation, 1);
2458       vec_oprnd1 = vect_get_vec_def_for_operand (op1, stmt);
2459     }
2460
2461   /* Arguments are ready. create the new vector stmt.  */
2462
2463   if (op_type == binary_op)
2464     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
2465                 build2 (code, vectype, vec_oprnd0, vec_oprnd1));
2466   else
2467     *vec_stmt = build2 (MODIFY_EXPR, vectype, vec_dest,
2468                 build1 (code, vectype, vec_oprnd0));
2469   new_temp = make_ssa_name (vec_dest, *vec_stmt);
2470   TREE_OPERAND (*vec_stmt, 0) = new_temp;
2471   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
2472
2473   return true;
2474 }
2475
2476
2477 /* Function vectorizable_store.
2478
2479    Check if STMT defines a non scalar data-ref (array/pointer/structure) that
2480    can be vectorized.
2481    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2482    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2483    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2484
2485 static bool
2486 vectorizable_store (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
2487 {
2488   tree scalar_dest;
2489   tree data_ref;
2490   tree op;
2491   tree vec_oprnd1;
2492   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2493   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
2494   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2495   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2496   enum machine_mode vec_mode;
2497   tree dummy;
2498   enum dr_alignment_support alignment_support_cheme;
2499
2500   /* Is vectorizable store? */
2501
2502   if (TREE_CODE (stmt) != MODIFY_EXPR)
2503     return false;
2504
2505   scalar_dest = TREE_OPERAND (stmt, 0);
2506   if (TREE_CODE (scalar_dest) != ARRAY_REF
2507       && TREE_CODE (scalar_dest) != INDIRECT_REF)
2508     return false;
2509
2510   op = TREE_OPERAND (stmt, 1);
2511   if (!vect_is_simple_use (op, loop_vinfo, NULL))
2512     {
2513       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2514         fprintf (vect_dump, "use not simple.");
2515       return false;
2516     }
2517
2518   vec_mode = TYPE_MODE (vectype);
2519   /* FORNOW. In some cases can vectorize even if data-type not supported
2520      (e.g. - array initialization with 0).  */
2521   if (mov_optab->handlers[(int)vec_mode].insn_code == CODE_FOR_nothing)
2522     return false;
2523
2524   if (!STMT_VINFO_DATA_REF (stmt_info))
2525     return false;
2526
2527
2528   if (!vec_stmt) /* transformation not required.  */
2529     {
2530       STMT_VINFO_TYPE (stmt_info) = store_vec_info_type;
2531       return true;
2532     }
2533
2534   /** Transform.  **/
2535
2536   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2537     fprintf (vect_dump, "transform store");
2538
2539   alignment_support_cheme = vect_supportable_dr_alignment (dr);
2540   gcc_assert (alignment_support_cheme);
2541   gcc_assert (alignment_support_cheme = dr_aligned);  /* FORNOW */
2542
2543   /* Handle use - get the vectorized def from the defining stmt.  */
2544   vec_oprnd1 = vect_get_vec_def_for_operand (op, stmt);
2545
2546   /* Handle def.  */
2547   /* FORNOW: make sure the data reference is aligned.  */
2548   vect_align_data_ref (stmt);
2549   data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
2550   data_ref = build_fold_indirect_ref (data_ref);
2551
2552   /* Arguments are ready. create the new vector stmt.  */
2553   *vec_stmt = build2 (MODIFY_EXPR, vectype, data_ref, vec_oprnd1);
2554   vect_finish_stmt_generation (stmt, *vec_stmt, bsi);
2555
2556   return true;
2557 }
2558
2559
2560 /* vectorizable_load.
2561
2562    Check if STMT reads a non scalar data-ref (array/pointer/structure) that
2563    can be vectorized.
2564    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2565    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2566    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2567
2568 static bool
2569 vectorizable_load (tree stmt, block_stmt_iterator *bsi, tree *vec_stmt)
2570 {
2571   tree scalar_dest;
2572   tree vec_dest = NULL;
2573   tree data_ref = NULL;
2574   tree op;
2575   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2576   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info);
2577   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
2578   tree new_temp;
2579   int mode;
2580   tree init_addr;
2581   tree new_stmt;
2582   tree dummy;
2583   basic_block new_bb;
2584   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2585   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2586   edge pe = loop_preheader_edge (loop);
2587   enum dr_alignment_support alignment_support_cheme;
2588
2589   /* Is vectorizable load? */
2590
2591   if (TREE_CODE (stmt) != MODIFY_EXPR)
2592     return false;
2593
2594   scalar_dest = TREE_OPERAND (stmt, 0);
2595   if (TREE_CODE (scalar_dest) != SSA_NAME)
2596     return false;
2597
2598   op = TREE_OPERAND (stmt, 1);
2599   if (TREE_CODE (op) != ARRAY_REF && TREE_CODE (op) != INDIRECT_REF)
2600     return false;
2601
2602   if (!STMT_VINFO_DATA_REF (stmt_info))
2603     return false;
2604
2605   mode = (int) TYPE_MODE (vectype);
2606
2607   /* FORNOW. In some cases can vectorize even if data-type not supported
2608     (e.g. - data copies).  */
2609   if (mov_optab->handlers[mode].insn_code == CODE_FOR_nothing)
2610     {
2611       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
2612         fprintf (vect_dump, "Aligned load, but unsupported type.");
2613       return false;
2614     }
2615
2616   if (!vec_stmt) /* transformation not required.  */
2617     {
2618       STMT_VINFO_TYPE (stmt_info) = load_vec_info_type;
2619       return true;
2620     }
2621
2622   /** Transform.  **/
2623
2624   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2625     fprintf (vect_dump, "transform load.");
2626
2627   alignment_support_cheme = vect_supportable_dr_alignment (dr);
2628   gcc_assert (alignment_support_cheme);
2629
2630   if (alignment_support_cheme == dr_aligned
2631       || alignment_support_cheme == dr_unaligned_supported)
2632     {
2633       /* Create:
2634          p = initial_addr;
2635          indx = 0;
2636          loop {
2637            vec_dest = *(p);
2638            indx = indx + 1;
2639          }
2640       */
2641
2642       vec_dest = vect_create_destination_var (scalar_dest, vectype);
2643       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE, &dummy, false);
2644       if (aligned_access_p (dr))
2645         data_ref = build_fold_indirect_ref (data_ref);
2646       else
2647         {
2648           int mis = DR_MISALIGNMENT (dr);
2649           tree tmis = (mis == -1 ? size_zero_node : size_int (mis));
2650           tmis = size_binop (MULT_EXPR, tmis, size_int(BITS_PER_UNIT));
2651           data_ref = build2 (MISALIGNED_INDIRECT_REF, vectype, data_ref, tmis);
2652         }
2653       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
2654       new_temp = make_ssa_name (vec_dest, new_stmt);
2655       TREE_OPERAND (new_stmt, 0) = new_temp;
2656       vect_finish_stmt_generation (stmt, new_stmt, bsi);
2657     }
2658   else if (alignment_support_cheme == dr_unaligned_software_pipeline)
2659     {
2660       /* Create:
2661          p1 = initial_addr;
2662          msq_init = *(floor(p1))
2663          p2 = initial_addr + VS - 1;
2664          magic = have_builtin ? builtin_result : initial_address;
2665          indx = 0;
2666          loop {
2667            p2' = p2 + indx * vectype_size
2668            lsq = *(floor(p2'))
2669            vec_dest = realign_load (msq, lsq, magic)
2670            indx = indx + 1;
2671            msq = lsq;
2672          }
2673       */
2674
2675       tree offset;
2676       tree magic;
2677       tree phi_stmt;
2678       tree msq_init;
2679       tree msq, lsq;
2680       tree dataref_ptr;
2681       tree params;
2682
2683       /* <1> Create msq_init = *(floor(p1)) in the loop preheader  */
2684       vec_dest = vect_create_destination_var (scalar_dest, vectype);
2685       data_ref = vect_create_data_ref_ptr (stmt, bsi, NULL_TREE,
2686                                            &init_addr, true);
2687       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, data_ref);
2688       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
2689       new_temp = make_ssa_name (vec_dest, new_stmt);
2690       TREE_OPERAND (new_stmt, 0) = new_temp;
2691       new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
2692       gcc_assert (!new_bb);
2693       msq_init = TREE_OPERAND (new_stmt, 0);
2694
2695
2696       /* <2> Create lsq = *(floor(p2')) in the loop  */
2697       offset = build_int_cst (integer_type_node,
2698                               GET_MODE_NUNITS (TYPE_MODE (vectype)));
2699       offset = int_const_binop (MINUS_EXPR, offset, integer_one_node, 1);
2700       vec_dest = vect_create_destination_var (scalar_dest, vectype);
2701       dataref_ptr = vect_create_data_ref_ptr (stmt, bsi, offset, &dummy, false);
2702       data_ref = build1 (ALIGN_INDIRECT_REF, vectype, dataref_ptr);
2703       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, data_ref);
2704       new_temp = make_ssa_name (vec_dest, new_stmt);
2705       TREE_OPERAND (new_stmt, 0) = new_temp;
2706       vect_finish_stmt_generation (stmt, new_stmt, bsi);
2707       lsq = TREE_OPERAND (new_stmt, 0);
2708
2709
2710       /* <3> */
2711       if (targetm.vectorize.builtin_mask_for_load)
2712         {
2713           /* Create permutation mask, if required, in loop preheader.  */
2714           tree builtin_decl;
2715           params = build_tree_list (NULL_TREE, init_addr);
2716           vec_dest = vect_create_destination_var (scalar_dest, vectype);
2717           builtin_decl = targetm.vectorize.builtin_mask_for_load ();
2718           new_stmt = build_function_call_expr (builtin_decl, params);
2719           new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, new_stmt);
2720           new_temp = make_ssa_name (vec_dest, new_stmt);
2721           TREE_OPERAND (new_stmt, 0) = new_temp;
2722           new_bb = bsi_insert_on_edge_immediate (pe, new_stmt);
2723           gcc_assert (!new_bb);
2724           magic = TREE_OPERAND (new_stmt, 0);
2725
2726           /* Since we have just created a CALL_EXPR, we may need to
2727              rename call-clobbered variables.  */
2728           mark_call_clobbered_vars_to_rename ();
2729         }
2730       else
2731         {
2732           /* Use current address instead of init_addr for reduced reg pressure.
2733            */
2734           magic = dataref_ptr;
2735         }
2736
2737
2738       /* <4> Create msq = phi <msq_init, lsq> in loop  */
2739       vec_dest = vect_create_destination_var (scalar_dest, vectype);
2740       msq = make_ssa_name (vec_dest, NULL_TREE);
2741       phi_stmt = create_phi_node (msq, loop->header); /* CHECKME */
2742       SSA_NAME_DEF_STMT (msq) = phi_stmt;
2743       add_phi_arg (phi_stmt, msq_init, loop_preheader_edge (loop));
2744       add_phi_arg (phi_stmt, lsq, loop_latch_edge (loop));
2745
2746
2747       /* <5> Create <vec_dest = realign_load (msq, lsq, magic)> in loop  */
2748       vec_dest = vect_create_destination_var (scalar_dest, vectype);
2749       new_stmt = build3 (REALIGN_LOAD_EXPR, vectype, msq, lsq, magic);
2750       new_stmt = build2 (MODIFY_EXPR, vectype, vec_dest, new_stmt);
2751       new_temp = make_ssa_name (vec_dest, new_stmt);
2752       TREE_OPERAND (new_stmt, 0) = new_temp;
2753       vect_finish_stmt_generation (stmt, new_stmt, bsi);
2754     }
2755   else
2756     gcc_unreachable ();
2757
2758   *vec_stmt = new_stmt;
2759   return true;
2760 }
2761
2762
2763 /* Function vect_supportable_dr_alignment
2764
2765    Return whether the data reference DR is supported with respect to its
2766    alignment.  */
2767
2768 static enum dr_alignment_support
2769 vect_supportable_dr_alignment (struct data_reference *dr)
2770 {
2771   tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
2772   enum machine_mode mode = (int) TYPE_MODE (vectype);
2773
2774   if (aligned_access_p (dr))
2775     return dr_aligned;
2776
2777   /* Possibly unaligned access.  */
2778
2779   if (DR_IS_READ (dr))
2780     {
2781       if (vec_realign_load_optab->handlers[mode].insn_code != CODE_FOR_nothing
2782           && (!targetm.vectorize.builtin_mask_for_load
2783               || targetm.vectorize.builtin_mask_for_load ()))
2784         return dr_unaligned_software_pipeline;
2785
2786       if (movmisalign_optab->handlers[mode].insn_code != CODE_FOR_nothing)
2787         /* Can't software pipeline the loads, but can at least do them.  */
2788         return dr_unaligned_supported;
2789     }
2790
2791   /* Unsupported.  */
2792   return dr_unaligned_unsupported;
2793 }
2794
2795
2796 /* Function vect_transform_stmt.
2797
2798    Create a vectorized stmt to replace STMT, and insert it at BSI.  */
2799
2800 static bool
2801 vect_transform_stmt (tree stmt, block_stmt_iterator *bsi)
2802 {
2803   bool is_store = false;
2804   tree vec_stmt = NULL_TREE;
2805   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2806   bool done;
2807
2808   switch (STMT_VINFO_TYPE (stmt_info))
2809     {
2810     case op_vec_info_type:
2811       done = vectorizable_operation (stmt, bsi, &vec_stmt);
2812       gcc_assert (done);
2813       break;
2814
2815     case assignment_vec_info_type:
2816       done = vectorizable_assignment (stmt, bsi, &vec_stmt);
2817       gcc_assert (done);
2818       break;
2819
2820     case load_vec_info_type:
2821       done = vectorizable_load (stmt, bsi, &vec_stmt);
2822       gcc_assert (done);
2823       break;
2824
2825     case store_vec_info_type:
2826       done = vectorizable_store (stmt, bsi, &vec_stmt);
2827       gcc_assert (done);
2828       is_store = true;
2829       break;
2830     default:
2831       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
2832         fprintf (vect_dump, "stmt not supported.");
2833       gcc_unreachable ();
2834     }
2835
2836   STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
2837
2838   return is_store;
2839 }
2840
2841
2842 /* This function builds ni_name = number of iterations loop executes
2843    on the loop preheader.  */
2844
2845 static tree
2846 vect_build_loop_niters (loop_vec_info loop_vinfo)
2847 {
2848   tree ni_name, stmt, var;
2849   edge pe;
2850   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2851   tree ni = unshare_expr (LOOP_VINFO_NITERS (loop_vinfo));
2852
2853   var = create_tmp_var (TREE_TYPE (ni), "niters");
2854   add_referenced_tmp_var (var);
2855   ni_name = force_gimple_operand (ni, &stmt, false, var);
2856
2857   pe = loop_preheader_edge (loop);
2858   if (stmt)
2859     {
2860       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
2861       gcc_assert (!new_bb);
2862     }
2863
2864   return ni_name;
2865 }
2866
2867
2868 /* This function generates the following statements:
2869
2870  ni_name = number of iterations loop executes
2871  ratio = ni_name / vf
2872  ratio_mult_vf_name = ratio * vf
2873
2874  and places them at the loop preheader edge.  */
2875
2876 static void
2877 vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo,
2878                                  tree *ni_name_ptr,
2879                                  tree *ratio_mult_vf_name_ptr,
2880                                  tree *ratio_name_ptr)
2881 {
2882
2883   edge pe;
2884   basic_block new_bb;
2885   tree stmt, ni_name;
2886   tree var;
2887   tree ratio_name;
2888   tree ratio_mult_vf_name;
2889   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2890   tree ni = LOOP_VINFO_NITERS (loop_vinfo);
2891   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2892   tree log_vf = build_int_cst (unsigned_type_node, exact_log2 (vf));
2893
2894   pe = loop_preheader_edge (loop);
2895
2896   /* Generate temporary variable that contains
2897      number of iterations loop executes.  */
2898
2899   ni_name = vect_build_loop_niters (loop_vinfo);
2900
2901   /* Create: ratio = ni >> log2(vf) */
2902
2903   var = create_tmp_var (TREE_TYPE (ni), "bnd");
2904   add_referenced_tmp_var (var);
2905   ratio_name = make_ssa_name (var, NULL_TREE);
2906   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_name,
2907            build2 (RSHIFT_EXPR, TREE_TYPE (ni_name), ni_name, log_vf));
2908   SSA_NAME_DEF_STMT (ratio_name) = stmt;
2909
2910   pe = loop_preheader_edge (loop);
2911   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
2912   gcc_assert (!new_bb);
2913
2914   /* Create: ratio_mult_vf = ratio << log2 (vf).  */
2915
2916   var = create_tmp_var (TREE_TYPE (ni), "ratio_mult_vf");
2917   add_referenced_tmp_var (var);
2918   ratio_mult_vf_name = make_ssa_name (var, NULL_TREE);
2919   stmt = build2 (MODIFY_EXPR, void_type_node, ratio_mult_vf_name,
2920            build2 (LSHIFT_EXPR, TREE_TYPE (ratio_name), ratio_name, log_vf));
2921   SSA_NAME_DEF_STMT (ratio_mult_vf_name) = stmt;
2922
2923   pe = loop_preheader_edge (loop);
2924   new_bb = bsi_insert_on_edge_immediate (pe, stmt);
2925   gcc_assert (!new_bb);
2926
2927   *ni_name_ptr = ni_name;
2928   *ratio_mult_vf_name_ptr = ratio_mult_vf_name;
2929   *ratio_name_ptr = ratio_name;
2930
2931   return;
2932 }
2933
2934
2935 /*   Function vect_update_ivs_after_vectorizer.
2936
2937      "Advance" the induction variables of LOOP to the value they should take
2938      after the execution of LOOP.  This is currently necessary because the
2939      vectorizer does not handle induction variables that are used after the
2940      loop.  Such a situation occurs when the last iterations of LOOP are
2941      peeled, because:
2942      1. We introduced new uses after LOOP for IVs that were not originally used
2943         after LOOP: the IVs of LOOP are now used by an epilog loop.
2944      2. LOOP is going to be vectorized; this means that it will iterate N/VF
2945         times, whereas the loop IVs should be bumped N times.
2946
2947      Input:
2948      - LOOP - a loop that is going to be vectorized. The last few iterations
2949               of LOOP were peeled.
2950      - NITERS - the number of iterations that LOOP executes (before it is
2951                 vectorized). i.e, the number of times the ivs should be bumped.
2952      - UPDATE_E - a successor edge of LOOP->exit that is on the (only) path
2953                   coming out from LOOP on which there are uses of the LOOP ivs
2954                   (this is the path from LOOP->exit to epilog_loop->preheader).
2955
2956                   The new definitions of the ivs are placed in LOOP->exit.
2957                   The phi args associated with the edge UPDATE_E in the bb
2958                   UPDATE_E->dest are updated accordingly.
2959
2960      Assumption 1: Like the rest of the vectorizer, this function assumes
2961      a single loop exit that has a single predecessor.
2962
2963      Assumption 2: The phi nodes in the LOOP header and in update_bb are
2964      organized in the same order.
2965
2966      Assumption 3: The access function of the ivs is simple enough (see
2967      vect_can_advance_ivs_p).  This assumption will be relaxed in the future.
2968
2969      Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path
2970      coming out of LOOP on which the ivs of LOOP are used (this is the path
2971      that leads to the epilog loop; other paths skip the epilog loop).  This
2972      path starts with the edge UPDATE_E, and its destination (denoted update_bb)
2973      needs to have its phis updated.
2974  */
2975
2976 static void
2977 vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters,
2978                                   edge update_e)
2979 {
2980   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
2981   basic_block exit_bb = loop->exit_edges[0]->dest;
2982   tree phi, phi1;
2983   basic_block update_bb = update_e->dest;
2984
2985   /* gcc_assert (vect_can_advance_ivs_p (loop_vinfo)); */
2986
2987   /* Make sure there exists a single-predecessor exit bb:  */
2988   gcc_assert (EDGE_COUNT (exit_bb->preds) == 1);
2989
2990   for (phi = phi_nodes (loop->header), phi1 = phi_nodes (update_bb);
2991        phi && phi1;
2992        phi = PHI_CHAIN (phi), phi1 = PHI_CHAIN (phi1))
2993     {
2994       tree access_fn = NULL;
2995       tree evolution_part;
2996       tree init_expr;
2997       tree step_expr;
2998       tree var, stmt, ni, ni_name;
2999       block_stmt_iterator last_bsi;
3000
3001       /* Skip virtual phi's.  */
3002       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
3003         {
3004           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3005             fprintf (vect_dump, "virtual phi. skip.");
3006           continue;
3007         }
3008
3009       access_fn = analyze_scalar_evolution (loop, PHI_RESULT (phi));
3010       gcc_assert (access_fn);
3011       evolution_part =
3012          unshare_expr (evolution_part_in_loop_num (access_fn, loop->num));
3013       gcc_assert (evolution_part != NULL_TREE);
3014
3015       /* FORNOW: We do not support IVs whose evolution function is a polynomial
3016          of degree >= 2 or exponential.  */
3017       gcc_assert (!tree_is_chrec (evolution_part));
3018
3019       step_expr = evolution_part;
3020       init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
3021                                                                loop->num));
3022
3023       ni = build2 (PLUS_EXPR, TREE_TYPE (init_expr),
3024                   build2 (MULT_EXPR, TREE_TYPE (niters),
3025                        niters, step_expr), init_expr);
3026
3027       var = create_tmp_var (TREE_TYPE (init_expr), "tmp");
3028       add_referenced_tmp_var (var);
3029
3030       ni_name = force_gimple_operand (ni, &stmt, false, var);
3031
3032       /* Insert stmt into exit_bb.  */
3033       last_bsi = bsi_last (exit_bb);
3034       if (stmt)
3035         bsi_insert_before (&last_bsi, stmt, BSI_SAME_STMT);
3036
3037       /* Fix phi expressions in the successor bb.  */
3038       gcc_assert (PHI_ARG_DEF_FROM_EDGE (phi1, update_e) ==
3039                   PHI_ARG_DEF_FROM_EDGE (phi, EDGE_SUCC (loop->latch, 0)));
3040       SET_PHI_ARG_DEF (phi1, update_e->dest_idx, ni_name);
3041     }
3042 }
3043
3044
3045 /* Function vect_do_peeling_for_loop_bound
3046
3047    Peel the last iterations of the loop represented by LOOP_VINFO.
3048    The peeled iterations form a new epilog loop.  Given that the loop now
3049    iterates NITERS times, the new epilog loop iterates
3050    NITERS % VECTORIZATION_FACTOR times.
3051
3052    The original loop will later be made to iterate
3053    NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).  */
3054
3055 static void
3056 vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio,
3057                                 struct loops *loops)
3058 {
3059
3060   tree ni_name, ratio_mult_vf_name;
3061   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3062   struct loop *new_loop;
3063   edge update_e;
3064 #ifdef ENABLE_CHECKING
3065   int loop_num;
3066 #endif
3067
3068   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3069     fprintf (vect_dump, "=== vect_transtorm_for_unknown_loop_bound ===");
3070
3071   /* Generate the following variables on the preheader of original loop:
3072
3073      ni_name = number of iteration the original loop executes
3074      ratio = ni_name / vf
3075      ratio_mult_vf_name = ratio * vf  */
3076   vect_generate_tmps_on_preheader (loop_vinfo, &ni_name,
3077                                    &ratio_mult_vf_name, ratio);
3078
3079   /* Update loop info.  */
3080   loop->pre_header = loop_preheader_edge (loop)->src;
3081   loop->pre_header_edges[0] = loop_preheader_edge (loop);
3082
3083 #ifdef ENABLE_CHECKING
3084   loop_num  = loop->num;
3085 #endif
3086   new_loop = slpeel_tree_peel_loop_to_edge (loop, loops, loop->exit_edges[0],
3087                                             ratio_mult_vf_name, ni_name, false);
3088 #ifdef ENABLE_CHECKING
3089   gcc_assert (new_loop);
3090   gcc_assert (loop_num == loop->num);
3091   slpeel_verify_cfg_after_peeling (loop, new_loop);
3092 #endif
3093
3094   /* A guard that controls whether the new_loop is to be executed or skipped
3095      is placed in LOOP->exit.  LOOP->exit therefore has two successors - one
3096      is the preheader of NEW_LOOP, where the IVs from LOOP are used.  The other
3097      is a bb after NEW_LOOP, where these IVs are not used.  Find the edge that
3098      is on the path where the LOOP IVs are used and need to be updated.  */
3099
3100   if (EDGE_PRED (new_loop->pre_header, 0)->src == loop->exit_edges[0]->dest)
3101     update_e = EDGE_PRED (new_loop->pre_header, 0);
3102   else
3103     update_e = EDGE_PRED (new_loop->pre_header, 1);
3104
3105   /* Update IVs of original loop as if they were advanced
3106      by ratio_mult_vf_name steps.  */
3107   vect_update_ivs_after_vectorizer (loop_vinfo, ratio_mult_vf_name, update_e);
3108
3109   /* After peeling we have to reset scalar evolution analyzer.  */
3110   scev_reset ();
3111
3112   return;
3113 }
3114
3115
3116 /* Function vect_gen_niters_for_prolog_loop
3117
3118    Set the number of iterations for the loop represented by LOOP_VINFO
3119    to the minimum between LOOP_NITERS (the original iteration count of the loop)
3120    and the misalignment of DR - the first data reference recorded in
3121    LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO).  As a result, after the execution of
3122    this loop, the data reference DR will refer to an aligned location.
3123
3124    The following computation is generated:
3125
3126    compute address misalignment in bytes:
3127    addr_mis = addr & (vectype_size - 1)
3128
3129    prolog_niters = min ( LOOP_NITERS , (VF - addr_mis/elem_size)&(VF-1) )
3130
3131    (elem_size = element type size; an element is the scalar element
3132         whose type is the inner type of the vectype)  */
3133
3134 static tree
3135 vect_gen_niters_for_prolog_loop (loop_vec_info loop_vinfo, tree loop_niters)
3136 {
3137   struct data_reference *dr = LOOP_VINFO_UNALIGNED_DR (loop_vinfo);
3138   int vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3139   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3140   tree var, stmt;
3141   tree iters, iters_name;
3142   edge pe;
3143   basic_block new_bb;
3144   tree dr_stmt = DR_STMT (dr);
3145   stmt_vec_info stmt_info = vinfo_for_stmt (dr_stmt);
3146   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3147   int vectype_align = TYPE_ALIGN (vectype) / BITS_PER_UNIT;
3148   tree elem_misalign;
3149   tree byte_misalign;
3150   tree new_stmts = NULL_TREE;
3151   tree start_addr =
3152         vect_create_addr_base_for_vector_ref (dr_stmt, &new_stmts, NULL_TREE);
3153   tree ptr_type = TREE_TYPE (start_addr);
3154   tree size = TYPE_SIZE (ptr_type);
3155   tree type = lang_hooks.types.type_for_size (tree_low_cst (size, 1), 1);
3156   tree vectype_size_minus_1 = build_int_cst (type, vectype_align - 1);
3157   tree vf_minus_1 = build_int_cst (unsigned_type_node, vf - 1);
3158   tree niters_type = TREE_TYPE (loop_niters);
3159   tree elem_size_log =
3160         build_int_cst (unsigned_type_node, exact_log2 (vectype_align/vf));
3161   tree vf_tree = build_int_cst (unsigned_type_node, vf);
3162
3163   pe = loop_preheader_edge (loop);
3164   new_bb = bsi_insert_on_edge_immediate (pe, new_stmts);
3165   gcc_assert (!new_bb);
3166
3167   /* Create:  byte_misalign = addr & (vectype_size - 1)  */
3168   byte_misalign = build2 (BIT_AND_EXPR, type, start_addr, vectype_size_minus_1);
3169
3170   /* Create:  elem_misalign = byte_misalign / element_size  */
3171   elem_misalign =
3172         build2 (RSHIFT_EXPR, unsigned_type_node, byte_misalign, elem_size_log);
3173
3174   /* Create:  (niters_type) (VF - elem_misalign)&(VF - 1)  */
3175   iters = build2 (MINUS_EXPR, unsigned_type_node, vf_tree, elem_misalign);
3176   iters = build2 (BIT_AND_EXPR, unsigned_type_node, iters, vf_minus_1);
3177   iters = fold_convert (niters_type, iters);
3178
3179   /* Create:  prolog_loop_niters = min (iters, loop_niters) */
3180   /* If the loop bound is known at compile time we already verified that it is
3181      greater than vf; since the misalignment ('iters') is at most vf, there's
3182      no need to generate the MIN_EXPR in this case.  */
3183   if (TREE_CODE (loop_niters) != INTEGER_CST)
3184     iters = build2 (MIN_EXPR, niters_type, iters, loop_niters);
3185
3186   var = create_tmp_var (niters_type, "prolog_loop_niters");
3187   add_referenced_tmp_var (var);
3188   iters_name = force_gimple_operand (iters, &stmt, false, var);
3189
3190   /* Insert stmt on loop preheader edge.  */
3191   pe = loop_preheader_edge (loop);
3192   if (stmt)
3193     {
3194       basic_block new_bb = bsi_insert_on_edge_immediate (pe, stmt);
3195       gcc_assert (!new_bb);
3196     }
3197
3198   return iters_name;
3199 }
3200
3201
3202 /* Function vect_update_inits_of_dr
3203
3204    NITERS iterations were peeled from LOOP.  DR represents a data reference
3205    in LOOP.  This function updates the information recorded in DR to
3206    account for the fact that the first NITERS iterations had already been
3207    executed.  Specifically, it updates the OFFSET field of stmt_info.  */
3208
3209 static void
3210 vect_update_inits_of_dr (struct data_reference *dr, tree niters)
3211 {
3212   stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
3213   tree offset = STMT_VINFO_VECT_INIT_OFFSET (stmt_info);
3214
3215   niters = fold (build2 (MULT_EXPR, TREE_TYPE (niters), niters,
3216                          STMT_VINFO_VECT_STEP (stmt_info)));
3217   offset = fold (build2 (PLUS_EXPR, TREE_TYPE (offset), offset, niters));
3218   STMT_VINFO_VECT_INIT_OFFSET (stmt_info) = offset;
3219 }
3220
3221
3222 /* Function vect_update_inits_of_drs
3223
3224    NITERS iterations were peeled from the loop represented by LOOP_VINFO.
3225    This function updates the information recorded for the data references in
3226    the loop to account for the fact that the first NITERS iterations had
3227    already been executed.  Specifically, it updates the initial_condition of the
3228    access_function of all the data_references in the loop.  */
3229
3230 static void
3231 vect_update_inits_of_drs (loop_vec_info loop_vinfo, tree niters)
3232 {
3233   unsigned int i;
3234   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
3235   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
3236
3237   if (vect_dump && (dump_flags & TDF_DETAILS))
3238     fprintf (vect_dump, "=== vect_update_inits_of_dr ===");
3239
3240   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
3241     {
3242       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
3243       vect_update_inits_of_dr (dr, niters);
3244     }
3245
3246   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
3247     {
3248       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
3249       vect_update_inits_of_dr (dr, niters);
3250     }
3251 }
3252
3253
3254 /* Function vect_do_peeling_for_alignment
3255
3256    Peel the first 'niters' iterations of the loop represented by LOOP_VINFO.
3257    'niters' is set to the misalignment of one of the data references in the
3258    loop, thereby forcing it to refer to an aligned location at the beginning
3259    of the execution of this loop.  The data reference for which we are
3260    peeling is recorded in LOOP_VINFO_UNALIGNED_DR.  */
3261
3262 static void
3263 vect_do_peeling_for_alignment (loop_vec_info loop_vinfo, struct loops *loops)
3264 {
3265   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3266   tree niters_of_prolog_loop, ni_name;
3267   tree n_iters;
3268   struct loop *new_loop;
3269
3270   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3271     fprintf (vect_dump, "=== vect_do_peeling_for_alignment ===");
3272
3273   ni_name = vect_build_loop_niters (loop_vinfo);
3274   niters_of_prolog_loop = vect_gen_niters_for_prolog_loop (loop_vinfo, ni_name);
3275
3276   /* Peel the prolog loop and iterate it niters_of_prolog_loop.  */
3277   new_loop =
3278         slpeel_tree_peel_loop_to_edge (loop, loops, loop_preheader_edge (loop),
3279                                        niters_of_prolog_loop, ni_name, true);
3280 #ifdef ENABLE_CHECKING
3281   gcc_assert (new_loop);
3282   slpeel_verify_cfg_after_peeling (new_loop, loop);
3283 #endif
3284
3285   /* Update number of times loop executes.  */
3286   n_iters = LOOP_VINFO_NITERS (loop_vinfo);
3287   LOOP_VINFO_NITERS (loop_vinfo) =
3288     build2 (MINUS_EXPR, TREE_TYPE (n_iters), n_iters, niters_of_prolog_loop);
3289
3290   /* Update the init conditions of the access functions of all data refs.  */
3291   vect_update_inits_of_drs (loop_vinfo, niters_of_prolog_loop);
3292
3293   /* After peeling we have to reset scalar evolution analyzer.  */
3294   scev_reset ();
3295
3296   return;
3297 }
3298
3299
3300 /* Function vect_transform_loop.
3301
3302    The analysis phase has determined that the loop is vectorizable.
3303    Vectorize the loop - created vectorized stmts to replace the scalar
3304    stmts in the loop, and update the loop exit condition.  */
3305
3306 static void
3307 vect_transform_loop (loop_vec_info loop_vinfo,
3308                      struct loops *loops ATTRIBUTE_UNUSED)
3309 {
3310   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3311   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
3312   int nbbs = loop->num_nodes;
3313   block_stmt_iterator si;
3314   int i;
3315   tree ratio = NULL;
3316   int vectorization_factor = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3317
3318   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3319     fprintf (vect_dump, "=== vec_transform_loop ===");
3320
3321
3322   /* Peel the loop if there are data refs with unknown alignment.
3323      Only one data ref with unknown store is allowed.  */
3324
3325   if (LOOP_DO_PEELING_FOR_ALIGNMENT (loop_vinfo))
3326     vect_do_peeling_for_alignment (loop_vinfo, loops);
3327
3328   /* If the loop has a symbolic number of iterations 'n' (i.e. it's not a
3329      compile time constant), or it is a constant that doesn't divide by the
3330      vectorization factor, then an epilog loop needs to be created.
3331      We therefore duplicate the loop: the original loop will be vectorized,
3332      and will compute the first (n/VF) iterations. The second copy of the loop
3333      will remain scalar and will compute the remaining (n%VF) iterations.
3334      (VF is the vectorization factor).  */
3335
3336   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3337       || (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3338           && LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0))
3339     vect_do_peeling_for_loop_bound (loop_vinfo, &ratio, loops);
3340   else
3341     ratio = build_int_cst (TREE_TYPE (LOOP_VINFO_NITERS (loop_vinfo)),
3342                 LOOP_VINFO_INT_NITERS (loop_vinfo) / vectorization_factor);
3343
3344   /* 1) Make sure the loop header has exactly two entries
3345      2) Make sure we have a preheader basic block.  */
3346
3347   gcc_assert (EDGE_COUNT (loop->header->preds) == 2);
3348
3349   loop_split_edge_with (loop_preheader_edge (loop), NULL);
3350
3351
3352   /* FORNOW: the vectorizer supports only loops which body consist
3353      of one basic block (header + empty latch). When the vectorizer will
3354      support more involved loop forms, the order by which the BBs are
3355      traversed need to be reconsidered.  */
3356
3357   for (i = 0; i < nbbs; i++)
3358     {
3359       basic_block bb = bbs[i];
3360
3361       for (si = bsi_start (bb); !bsi_end_p (si);)
3362         {
3363           tree stmt = bsi_stmt (si);
3364           stmt_vec_info stmt_info;
3365           bool is_store;
3366
3367           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3368             {
3369               fprintf (vect_dump, "------>vectorizing statement: ");
3370               print_generic_expr (vect_dump, stmt, TDF_SLIM);
3371             }
3372           stmt_info = vinfo_for_stmt (stmt);
3373           gcc_assert (stmt_info);
3374           if (!STMT_VINFO_RELEVANT_P (stmt_info))
3375             {
3376               bsi_next (&si);
3377               continue;
3378             }
3379 #ifdef ENABLE_CHECKING
3380           /* FORNOW: Verify that all stmts operate on the same number of
3381                      units and no inner unrolling is necessary.  */
3382           gcc_assert
3383                 (GET_MODE_NUNITS (TYPE_MODE (STMT_VINFO_VECTYPE (stmt_info)))
3384                  == vectorization_factor);
3385 #endif
3386           /* -------- vectorize statement ------------ */
3387           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3388             fprintf (vect_dump, "transform statement.");
3389
3390           is_store = vect_transform_stmt (stmt, &si);
3391           if (is_store)
3392             {
3393               /* free the attached stmt_vec_info and remove the stmt.  */
3394               stmt_ann_t ann = stmt_ann (stmt);
3395               free (stmt_info);
3396               set_stmt_info (ann, NULL);
3397               bsi_remove (&si);
3398               continue;
3399             }
3400
3401           bsi_next (&si);
3402         }                       /* stmts in BB */
3403     }                           /* BBs in loop */
3404
3405   slpeel_make_loop_iterate_ntimes (loop, ratio);
3406
3407   if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS, LOOP_LOC (loop_vinfo)))
3408     fprintf (vect_dump, "LOOP VECTORIZED.");
3409 }
3410
3411
3412 /* Function vect_is_simple_use.
3413
3414    Input:
3415    LOOP - the loop that is being vectorized.
3416    OPERAND - operand of a stmt in LOOP.
3417    DEF - the defining stmt in case OPERAND is an SSA_NAME.
3418
3419    Returns whether a stmt with OPERAND can be vectorized.
3420    Supportable operands are constants, loop invariants, and operands that are
3421    defined by the current iteration of the loop. Unsupportable operands are
3422    those that are defined by a previous iteration of the loop (as is the case
3423    in reduction/induction computations).  */
3424
3425 static bool
3426 vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def)
3427 {
3428   tree def_stmt;
3429   basic_block bb;
3430   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3431
3432   if (def)
3433     *def = NULL_TREE;
3434
3435   if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
3436     return true;
3437
3438   if (TREE_CODE (operand) != SSA_NAME)
3439     return false;
3440
3441   def_stmt = SSA_NAME_DEF_STMT (operand);
3442   if (def_stmt == NULL_TREE )
3443     {
3444       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3445         fprintf (vect_dump, "no def_stmt.");
3446       return false;
3447     }
3448
3449   /* empty stmt is expected only in case of a function argument.
3450      (Otherwise - we expect a phi_node or a modify_expr).  */
3451   if (IS_EMPTY_STMT (def_stmt))
3452     {
3453       tree arg = TREE_OPERAND (def_stmt, 0);
3454       if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
3455         return true;
3456       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3457         {
3458           fprintf (vect_dump, "Unexpected empty stmt: ");
3459           print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
3460         }
3461       return false;
3462     }
3463
3464   /* phi_node inside the loop indicates an induction/reduction pattern.
3465      This is not supported yet.  */
3466   bb = bb_for_stmt (def_stmt);
3467   if (TREE_CODE (def_stmt) == PHI_NODE && flow_bb_inside_loop_p (loop, bb))
3468     {
3469       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3470         fprintf (vect_dump, "reduction/induction - unsupported.");
3471       return false; /* FORNOW: not supported yet.  */
3472     }
3473
3474   /* Expecting a modify_expr or a phi_node.  */
3475   if (TREE_CODE (def_stmt) == MODIFY_EXPR
3476       || TREE_CODE (def_stmt) == PHI_NODE)
3477     {
3478       if (def)
3479         *def = def_stmt;
3480       return true;
3481     }
3482
3483   return false;
3484 }
3485
3486
3487 /* Function vect_analyze_operations.
3488
3489    Scan the loop stmts and make sure they are all vectorizable.  */
3490
3491 static bool
3492 vect_analyze_operations (loop_vec_info loop_vinfo)
3493 {
3494   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3495   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
3496   int nbbs = loop->num_nodes;
3497   block_stmt_iterator si;
3498   unsigned int vectorization_factor = 0;
3499   int i;
3500   bool ok;
3501   tree scalar_type;
3502
3503   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3504     fprintf (vect_dump, "=== vect_analyze_operations ===");
3505
3506   for (i = 0; i < nbbs; i++)
3507     {
3508       basic_block bb = bbs[i];
3509
3510       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
3511         {
3512           tree stmt = bsi_stmt (si);
3513           unsigned int nunits;
3514           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3515           tree vectype;
3516
3517           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3518             {
3519               fprintf (vect_dump, "==> examining statement: ");
3520               print_generic_expr (vect_dump, stmt, TDF_SLIM);
3521             }
3522
3523           gcc_assert (stmt_info);
3524
3525           /* skip stmts which do not need to be vectorized.
3526              this is expected to include:
3527              - the COND_EXPR which is the loop exit condition
3528              - any LABEL_EXPRs in the loop
3529              - computations that are used only for array indexing or loop
3530              control  */
3531
3532           if (!STMT_VINFO_RELEVANT_P (stmt_info))
3533             {
3534               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3535                 fprintf (vect_dump, "irrelevant.");
3536               continue;
3537             }
3538
3539           if (VECTOR_MODE_P (TYPE_MODE (TREE_TYPE (stmt))))
3540             {
3541               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3542                                          LOOP_LOC (loop_vinfo)))
3543                 {
3544                   fprintf (vect_dump, "not vectorized: vector stmt in loop:");
3545                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
3546                 }
3547               return false;
3548             }
3549
3550           if (STMT_VINFO_DATA_REF (stmt_info))
3551             scalar_type = TREE_TYPE (DR_REF (STMT_VINFO_DATA_REF (stmt_info)));
3552           else if (TREE_CODE (stmt) == MODIFY_EXPR)
3553             scalar_type = TREE_TYPE (TREE_OPERAND (stmt, 0));
3554           else
3555             scalar_type = TREE_TYPE (stmt);
3556
3557           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3558             {
3559               fprintf (vect_dump, "get vectype for scalar type:  ");
3560               print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
3561             }
3562
3563           vectype = get_vectype_for_scalar_type (scalar_type);
3564           if (!vectype)
3565             {
3566               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3567                                          LOOP_LOC (loop_vinfo)))
3568                 {
3569                   fprintf (vect_dump,
3570                            "not vectorized: unsupported data-type ");
3571                   print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
3572                 }
3573               return false;
3574             }
3575
3576           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3577             {
3578               fprintf (vect_dump, "vectype: ");
3579               print_generic_expr (vect_dump, vectype, TDF_SLIM);
3580             }
3581           STMT_VINFO_VECTYPE (stmt_info) = vectype;
3582
3583           ok = (vectorizable_operation (stmt, NULL, NULL)
3584                 || vectorizable_assignment (stmt, NULL, NULL)
3585                 || vectorizable_load (stmt, NULL, NULL)
3586                 || vectorizable_store (stmt, NULL, NULL));
3587
3588           if (!ok)
3589             {
3590               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3591                                          LOOP_LOC (loop_vinfo)))
3592                 {
3593                   fprintf (vect_dump, "not vectorized: stmt not supported: ");
3594                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
3595                 }
3596               return false;
3597             }
3598
3599           nunits = GET_MODE_NUNITS (TYPE_MODE (vectype));
3600           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3601             fprintf (vect_dump, "nunits = %d", nunits);
3602
3603           if (vectorization_factor)
3604             {
3605               /* FORNOW: don't allow mixed units.
3606                  This restriction will be relaxed in the future.  */
3607               if (nunits != vectorization_factor)
3608                 {
3609                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3610                                              LOOP_LOC (loop_vinfo)))
3611                     fprintf (vect_dump, "not vectorized: mixed data-types");
3612                   return false;
3613                 }
3614             }
3615           else
3616             vectorization_factor = nunits;
3617
3618 #ifdef ENABLE_CHECKING
3619           gcc_assert (GET_MODE_SIZE (TYPE_MODE (scalar_type))
3620                         * vectorization_factor == UNITS_PER_SIMD_WORD);
3621 #endif
3622         }
3623     }
3624
3625   /* TODO: Analyze cost. Decide if worth while to vectorize.  */
3626
3627   if (vectorization_factor <= 1)
3628     {
3629       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3630                                  LOOP_LOC (loop_vinfo)))
3631         fprintf (vect_dump, "not vectorized: unsupported data-type");
3632       return false;
3633     }
3634   LOOP_VINFO_VECT_FACTOR (loop_vinfo) = vectorization_factor;
3635
3636   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3637       && vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3638     fprintf (vect_dump,
3639         "vectorization_factor = %d, niters = " HOST_WIDE_INT_PRINT_DEC,
3640         vectorization_factor, LOOP_VINFO_INT_NITERS (loop_vinfo));
3641
3642   if (LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3643       && LOOP_VINFO_INT_NITERS (loop_vinfo) < vectorization_factor)
3644     {
3645       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3646                                  LOOP_LOC (loop_vinfo)))
3647         fprintf (vect_dump, "not vectorized: iteration count too small.");
3648       return false;
3649     }
3650
3651   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo)
3652       || LOOP_VINFO_INT_NITERS (loop_vinfo) % vectorization_factor != 0)
3653     {
3654       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
3655         fprintf (vect_dump, "epilog loop required.");
3656       if (!vect_can_advance_ivs_p (loop_vinfo))
3657         {
3658           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3659                                      LOOP_LOC (loop_vinfo)))
3660             fprintf (vect_dump,
3661                      "not vectorized: can't create epilog loop 1.");
3662           return false;
3663         }
3664       if (!slpeel_can_duplicate_loop_p (loop, loop->exit_edges[0]))
3665         {
3666           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3667                                      LOOP_LOC (loop_vinfo)))
3668             fprintf (vect_dump,
3669                      "not vectorized: can't create epilog loop 2.");
3670           return false;
3671         }
3672     }
3673
3674   return true;
3675 }
3676
3677
3678 /* Function exist_non_indexing_operands_for_use_p
3679
3680    USE is one of the uses attached to STMT. Check if USE is
3681    used in STMT for anything other than indexing an array.  */
3682
3683 static bool
3684 exist_non_indexing_operands_for_use_p (tree use, tree stmt)
3685 {
3686   tree operand;
3687   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3688
3689   /* USE corresponds to some operand in STMT. If there is no data
3690      reference in STMT, then any operand that corresponds to USE
3691      is not indexing an array.  */
3692   if (!STMT_VINFO_DATA_REF (stmt_info))
3693     return true;
3694
3695   /* STMT has a data_ref. FORNOW this means that its of one of
3696      the following forms:
3697      -1- ARRAY_REF = var
3698      -2- var = ARRAY_REF
3699      (This should have been verified in analyze_data_refs).
3700
3701      'var' in the second case corresponds to a def, not a use,
3702      so USE cannot correspond to any operands that are not used
3703      for array indexing.
3704
3705      Therefore, all we need to check is if STMT falls into the
3706      first case, and whether var corresponds to USE.  */
3707
3708   if (TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
3709     return false;
3710
3711   operand = TREE_OPERAND (stmt, 1);
3712
3713   if (TREE_CODE (operand) != SSA_NAME)
3714     return false;
3715
3716   if (operand == use)
3717     return true;
3718
3719   return false;
3720 }
3721
3722
3723 /* Function vect_is_simple_iv_evolution.
3724
3725    FORNOW: A simple evolution of an induction variables in the loop is
3726    considered a polynomial evolution with constant step.  */
3727
3728 static bool
3729 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
3730                              tree * step)
3731 {
3732   tree init_expr;
3733   tree step_expr;
3734
3735   tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
3736
3737   /* When there is no evolution in this loop, the evolution function
3738      is not "simple".  */
3739   if (evolution_part == NULL_TREE)
3740     return false;
3741
3742   /* When the evolution is a polynomial of degree >= 2
3743      the evolution function is not "simple".  */
3744   if (tree_is_chrec (evolution_part))
3745     return false;
3746
3747   step_expr = evolution_part;
3748   init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
3749                                                            loop_nb));
3750
3751   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3752     {
3753       fprintf (vect_dump, "step: ");
3754       print_generic_expr (vect_dump, step_expr, TDF_SLIM);
3755       fprintf (vect_dump, ",  init: ");
3756       print_generic_expr (vect_dump, init_expr, TDF_SLIM);
3757     }
3758
3759   *init = init_expr;
3760   *step = step_expr;
3761
3762   if (TREE_CODE (step_expr) != INTEGER_CST)
3763     {
3764       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3765         fprintf (vect_dump, "step unknown.");
3766       return false;
3767     }
3768
3769   return true;
3770 }
3771
3772
3773 /* Function vect_analyze_scalar_cycles.
3774
3775    Examine the cross iteration def-use cycles of scalar variables, by
3776    analyzing the loop (scalar) PHIs; verify that the cross iteration def-use
3777    cycles that they represent do not impede vectorization.
3778
3779    FORNOW: Reduction as in the following loop, is not supported yet:
3780               loop1:
3781               for (i=0; i<N; i++)
3782                  sum += a[i];
3783            The cross-iteration cycle corresponding to variable 'sum' will be
3784            considered too complicated and will impede vectorization.
3785
3786    FORNOW: Induction as in the following loop, is not supported yet:
3787               loop2:
3788               for (i=0; i<N; i++)
3789                  a[i] = i;
3790
3791            However, the following loop *is* vectorizable:
3792               loop3:
3793               for (i=0; i<N; i++)
3794                  a[i] = b[i];
3795
3796            In both loops there exists a def-use cycle for the variable i:
3797               loop: i_2 = PHI (i_0, i_1)
3798                     a[i_2] = ...;
3799                     i_1 = i_2 + 1;
3800                     GOTO loop;
3801
3802            The evolution of the above cycle is considered simple enough,
3803            however, we also check that the cycle does not need to be
3804            vectorized, i.e - we check that the variable that this cycle
3805            defines is only used for array indexing or in stmts that do not
3806            need to be vectorized. This is not the case in loop2, but it
3807            *is* the case in loop3.  */
3808
3809 static bool
3810 vect_analyze_scalar_cycles (loop_vec_info loop_vinfo)
3811 {
3812   tree phi;
3813   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
3814   basic_block bb = loop->header;
3815   tree dummy;
3816
3817   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3818     fprintf (vect_dump, "=== vect_analyze_scalar_cycles ===");
3819
3820   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
3821     {
3822       tree access_fn = NULL;
3823
3824       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3825         {
3826           fprintf (vect_dump, "Analyze phi: ");
3827           print_generic_expr (vect_dump, phi, TDF_SLIM);
3828         }
3829
3830       /* Skip virtual phi's. The data dependences that are associated with
3831          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
3832
3833       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
3834         {
3835           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
3836             fprintf (vect_dump, "virtual phi. skip.");
3837           continue;
3838         }
3839
3840       /* Analyze the evolution function.  */
3841
3842       /* FORNOW: The only scalar cross-iteration cycles that we allow are
3843          those of loop induction variables; This property is verified here.
3844
3845          Furthermore, if that induction variable is used in an operation
3846          that needs to be vectorized (i.e, is not solely used to index
3847          arrays and check the exit condition) - we do not support its
3848          vectorization yet. This property is verified in vect_is_simple_use,
3849          during vect_analyze_operations.  */
3850
3851       access_fn = /* instantiate_parameters
3852                      (loop,*/
3853          analyze_scalar_evolution (loop, PHI_RESULT (phi));
3854
3855       if (!access_fn)
3856         {
3857           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3858                                     LOOP_LOC (loop_vinfo)))
3859             fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
3860           return false;
3861         }
3862
3863       if (vect_print_dump_info (REPORT_DETAILS,
3864                                 LOOP_LOC (loop_vinfo)))
3865         {
3866            fprintf (vect_dump, "Access function of PHI: ");
3867            print_generic_expr (vect_dump, access_fn, TDF_SLIM);
3868         }
3869
3870       if (!vect_is_simple_iv_evolution (loop->num, access_fn, &dummy, &dummy))
3871         {
3872           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3873                                     LOOP_LOC (loop_vinfo)))
3874             fprintf (vect_dump, "not vectorized: unsupported scalar cycle.");
3875           return false;
3876         }
3877     }
3878
3879   return true;
3880 }
3881
3882
3883 /* Function vect_base_addr_differ_p.
3884
3885    This is the simplest data dependence test: determines whether the
3886    data references A and B access the same array/region.  Returns
3887    false when the property is not computable at compile time.
3888    Otherwise return true, and DIFFER_P will record the result. This
3889    utility will not be necessary when alias_sets_conflict_p will be
3890    less conservative.  */
3891
3892
3893 static bool
3894 vect_base_addr_differ_p (struct data_reference *dra,
3895                          struct data_reference *drb,
3896                          bool *differ_p)
3897 {
3898   tree stmt_a = DR_STMT (dra);
3899   stmt_vec_info stmt_info_a = vinfo_for_stmt (stmt_a);
3900   tree stmt_b = DR_STMT (drb);
3901   stmt_vec_info stmt_info_b = vinfo_for_stmt (stmt_b);
3902   tree addr_a = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_a);
3903   tree addr_b = STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info_b);
3904   tree type_a = TREE_TYPE (addr_a);
3905   tree type_b = TREE_TYPE (addr_b);
3906   HOST_WIDE_INT alias_set_a, alias_set_b;
3907
3908   gcc_assert (POINTER_TYPE_P (type_a) &&  POINTER_TYPE_P (type_b));
3909
3910   /* Both references are ADDR_EXPR, i.e., we have the objects.  */
3911   if (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR)
3912     return array_base_name_differ_p (dra, drb, differ_p);
3913
3914   alias_set_a = (TREE_CODE (addr_a) == ADDR_EXPR) ?
3915     get_alias_set (TREE_OPERAND (addr_a, 0)) : get_alias_set (addr_a);
3916   alias_set_b = (TREE_CODE (addr_b) == ADDR_EXPR) ?
3917     get_alias_set (TREE_OPERAND (addr_b, 0)) : get_alias_set (addr_b);
3918
3919   if (!alias_sets_conflict_p (alias_set_a, alias_set_b))
3920     {
3921       *differ_p = true;
3922       return true;
3923     }
3924
3925   /* An instruction writing through a restricted pointer is "independent" of any
3926      instruction reading or writing through a different pointer, in the same
3927      block/scope.  */
3928   else if ((TYPE_RESTRICT (type_a) && !DR_IS_READ (dra))
3929       || (TYPE_RESTRICT (type_b) && !DR_IS_READ (drb)))
3930     {
3931       *differ_p = true;
3932       return true;
3933     }
3934   return false;
3935 }
3936
3937
3938 /* Function vect_analyze_data_ref_dependence.
3939
3940    Return TRUE if there (might) exist a dependence between a memory-reference
3941    DRA and a memory-reference DRB.  */
3942
3943 static bool
3944 vect_analyze_data_ref_dependence (struct data_reference *dra,
3945                                   struct data_reference *drb,
3946                                   loop_vec_info loop_vinfo)
3947 {
3948   bool differ_p;
3949   struct data_dependence_relation *ddr;
3950
3951   if (!vect_base_addr_differ_p (dra, drb, &differ_p))
3952     {
3953       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3954                                 LOOP_LOC (loop_vinfo)))
3955         {
3956           fprintf (vect_dump,
3957                 "not vectorized: can't determine dependence between: ");
3958           print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
3959           fprintf (vect_dump, " and ");
3960           print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
3961         }
3962       return true;
3963     }
3964
3965   if (differ_p)
3966     return false;
3967
3968   ddr = initialize_data_dependence_relation (dra, drb);
3969   compute_affine_dependence (ddr);
3970
3971   if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
3972     return false;
3973
3974   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
3975                             LOOP_LOC (loop_vinfo)))
3976     {
3977       fprintf (vect_dump,
3978         "not vectorized: possible dependence between data-refs ");
3979       print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
3980       fprintf (vect_dump, " and ");
3981       print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
3982     }
3983
3984   return true;
3985 }
3986
3987
3988 /* Function vect_analyze_data_ref_dependences.
3989
3990    Examine all the data references in the loop, and make sure there do not
3991    exist any data dependences between them.
3992
3993    TODO: dependences which distance is greater than the vectorization factor
3994          can be ignored.  */
3995
3996 static bool
3997 vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo)
3998 {
3999   unsigned int i, j;
4000   varray_type loop_write_refs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
4001   varray_type loop_read_refs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
4002
4003   /* Examine store-store (output) dependences.  */
4004
4005   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4006     fprintf (vect_dump, "=== vect_analyze_dependences ===");
4007
4008   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4009     fprintf (vect_dump, "compare all store-store pairs.");
4010
4011   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_refs); i++)
4012     {
4013       for (j = i + 1; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
4014         {
4015           struct data_reference *dra =
4016             VARRAY_GENERIC_PTR (loop_write_refs, i);
4017           struct data_reference *drb =
4018             VARRAY_GENERIC_PTR (loop_write_refs, j);
4019           if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
4020             return false;
4021         }
4022     }
4023
4024   /* Examine load-store (true/anti) dependences.  */
4025
4026   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4027     fprintf (vect_dump, "compare all load-store pairs.");
4028
4029   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_refs); i++)
4030     {
4031       for (j = 0; j < VARRAY_ACTIVE_SIZE (loop_write_refs); j++)
4032         {
4033           struct data_reference *dra = VARRAY_GENERIC_PTR (loop_read_refs, i);
4034           struct data_reference *drb =
4035             VARRAY_GENERIC_PTR (loop_write_refs, j);
4036           if (vect_analyze_data_ref_dependence (dra, drb, loop_vinfo))
4037             return false;
4038         }
4039     }
4040
4041   return true;
4042 }
4043
4044
4045 /* Function vect_compute_data_ref_alignment
4046
4047    Compute the misalignment of the data reference DR.
4048
4049    Output:
4050    1. If during the misalignment computation it is found that the data reference
4051       cannot be vectorized then false is returned.
4052    2. DR_MISALIGNMENT (DR) is defined.
4053
4054    FOR NOW: No analysis is actually performed. Misalignment is calculated
4055    only for trivial cases. TODO.  */
4056
4057 static bool
4058 vect_compute_data_ref_alignment (struct data_reference *dr)
4059 {
4060   tree stmt = DR_STMT (dr);
4061   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4062   tree ref = DR_REF (dr);
4063   tree vectype;
4064   tree base, alignment;
4065   bool base_aligned_p;
4066   tree misalign;
4067
4068   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4069     fprintf (vect_dump, "vect_compute_data_ref_alignment:");
4070
4071   /* Initialize misalignment to unknown.  */
4072   DR_MISALIGNMENT (dr) = -1;
4073
4074   misalign = STMT_VINFO_VECT_MISALIGNMENT (stmt_info);
4075   base_aligned_p = STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info);
4076   base = build_fold_indirect_ref (STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info));
4077   vectype = STMT_VINFO_VECTYPE (stmt_info);
4078
4079   if (!misalign)
4080     {
4081       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4082         {
4083           fprintf (vect_dump, "Unknown alignment for access: ");
4084           print_generic_expr (vect_dump, base, TDF_SLIM);
4085         }
4086       return true;
4087     }
4088
4089   if (!base_aligned_p)
4090     {
4091       if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype)))
4092         {
4093           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4094             {
4095               fprintf (vect_dump, "can't force alignment of ref: ");
4096               print_generic_expr (vect_dump, ref, TDF_SLIM);
4097             }
4098           return true;
4099         }
4100
4101       /* Force the alignment of the decl.
4102          NOTE: This is the only change to the code we make during
4103          the analysis phase, before deciding to vectorize the loop.  */
4104       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4105         fprintf (vect_dump, "force alignment");
4106       DECL_ALIGN (base) = TYPE_ALIGN (vectype);
4107       DECL_USER_ALIGN (base) = 1;
4108     }
4109
4110   /* At this point we assume that the base is aligned.  */
4111   gcc_assert (base_aligned_p
4112               || (TREE_CODE (base) == VAR_DECL
4113                   && DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
4114
4115   /* Alignment required, in bytes:  */
4116   alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
4117
4118   /* Modulo alignment.  */
4119   misalign = size_binop (TRUNC_MOD_EXPR, misalign, alignment);
4120   if (tree_int_cst_sgn (misalign) < 0)
4121     {
4122       /* Negative misalignment value.  */
4123       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4124         fprintf (vect_dump, "unexpected misalign value");
4125       return false;
4126     }
4127
4128   DR_MISALIGNMENT (dr) = tree_low_cst (misalign, 1);
4129
4130   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4131     fprintf (vect_dump, "misalign = %d bytes", DR_MISALIGNMENT (dr));
4132
4133   return true;
4134 }
4135
4136
4137 /* Function vect_compute_data_refs_alignment
4138
4139    Compute the misalignment of data references in the loop.
4140    This pass may take place at function granularity instead of at loop
4141    granularity.
4142
4143    FOR NOW: No analysis is actually performed. Misalignment is calculated
4144    only for trivial cases. TODO.  */
4145
4146 static bool
4147 vect_compute_data_refs_alignment (loop_vec_info loop_vinfo)
4148 {
4149   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
4150   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
4151   unsigned int i;
4152
4153   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
4154     {
4155       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
4156       if (!vect_compute_data_ref_alignment (dr))
4157         return false;
4158     }
4159
4160   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
4161     {
4162       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
4163       if (!vect_compute_data_ref_alignment (dr))
4164         return false;
4165     }
4166
4167   return true;
4168 }
4169
4170
4171 /* Function vect_enhance_data_refs_alignment
4172
4173    This pass will use loop versioning and loop peeling in order to enhance
4174    the alignment of data references in the loop.
4175
4176    FOR NOW: we assume that whatever versioning/peeling takes place, only the
4177    original loop is to be vectorized; Any other loops that are created by
4178    the transformations performed in this pass - are not supposed to be
4179    vectorized. This restriction will be relaxed.  */
4180
4181 static void
4182 vect_enhance_data_refs_alignment (loop_vec_info loop_vinfo)
4183 {
4184   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
4185   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
4186   unsigned int i;
4187
4188   /*
4189      This pass will require a cost model to guide it whether to apply peeling
4190      or versioning or a combination of the two. For example, the scheme that
4191      intel uses when given a loop with several memory accesses, is as follows:
4192      choose one memory access ('p') which alignment you want to force by doing
4193      peeling. Then, either (1) generate a loop in which 'p' is aligned and all
4194      other accesses are not necessarily aligned, or (2) use loop versioning to
4195      generate one loop in which all accesses are aligned, and another loop in
4196      which only 'p' is necessarily aligned.
4197
4198      ("Automatic Intra-Register Vectorization for the Intel Architecture",
4199       Aart J.C. Bik, Milind Girkar, Paul M. Grey and Ximmin Tian, International
4200       Journal of Parallel Programming, Vol. 30, No. 2, April 2002.)
4201
4202      Devising a cost model is the most critical aspect of this work. It will
4203      guide us on which access to peel for, whether to use loop versioning, how
4204      many versions to create, etc. The cost model will probably consist of
4205      generic considerations as well as target specific considerations (on
4206      powerpc for example, misaligned stores are more painful than misaligned
4207      loads).
4208
4209      Here is the general steps involved in alignment enhancements:
4210
4211      -- original loop, before alignment analysis:
4212         for (i=0; i<N; i++){
4213           x = q[i];                     # DR_MISALIGNMENT(q) = unknown
4214           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
4215         }
4216
4217      -- After vect_compute_data_refs_alignment:
4218         for (i=0; i<N; i++){
4219           x = q[i];                     # DR_MISALIGNMENT(q) = 3
4220           p[i] = y;                     # DR_MISALIGNMENT(p) = unknown
4221         }
4222
4223      -- Possibility 1: we do loop versioning:
4224      if (p is aligned) {
4225         for (i=0; i<N; i++){    # loop 1A
4226           x = q[i];                     # DR_MISALIGNMENT(q) = 3
4227           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
4228         }
4229      }
4230      else {
4231         for (i=0; i<N; i++){    # loop 1B
4232           x = q[i];                     # DR_MISALIGNMENT(q) = 3
4233           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
4234         }
4235      }
4236
4237      -- Possibility 2: we do loop peeling:
4238      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
4239         x = q[i];
4240         p[i] = y;
4241      }
4242      for (i = 3; i < N; i++){   # loop 2A
4243         x = q[i];                       # DR_MISALIGNMENT(q) = 0
4244         p[i] = y;                       # DR_MISALIGNMENT(p) = unknown
4245      }
4246
4247      -- Possibility 3: combination of loop peeling and versioning:
4248      for (i = 0; i < 3; i++){   # (scalar loop, not to be vectorized).
4249         x = q[i];
4250         p[i] = y;
4251      }
4252      if (p is aligned) {
4253         for (i = 3; i<N; i++){  # loop 3A
4254           x = q[i];                     # DR_MISALIGNMENT(q) = 0
4255           p[i] = y;                     # DR_MISALIGNMENT(p) = 0
4256         }
4257      }
4258      else {
4259         for (i = 3; i<N; i++){  # loop 3B
4260           x = q[i];                     # DR_MISALIGNMENT(q) = 0
4261           p[i] = y;                     # DR_MISALIGNMENT(p) = unaligned
4262         }
4263      }
4264
4265      These loops are later passed to loop_transform to be vectorized. The
4266      vectorizer will use the alignment information to guide the transformation
4267      (whether to generate regular loads/stores, or with special handling for
4268      misalignment).
4269    */
4270
4271   /* (1) Peeling to force alignment.  */
4272
4273   /* (1.1) Decide whether to perform peeling, and how many iterations to peel:
4274      Considerations:
4275      + How many accesses will become aligned due to the peeling
4276      - How many accesses will become unaligned due to the peeling,
4277        and the cost of misaligned accesses.
4278      - The cost of peeling (the extra runtime checks, the increase
4279        in code size).
4280
4281      The scheme we use FORNOW: peel to force the alignment of the first
4282      misaligned store in the loop.
4283      Rationale: misaligned stores are not yet supported.
4284
4285      TODO: Use a better cost model.  */
4286
4287   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
4288     {
4289       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
4290       if (!aligned_access_p (dr))
4291         {
4292           LOOP_VINFO_UNALIGNED_DR (loop_vinfo) = dr;
4293           LOOP_DO_PEELING_FOR_ALIGNMENT (loop_vinfo) = true;
4294           break;
4295         }
4296     }
4297
4298   if (!LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
4299     {
4300       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
4301         fprintf (vect_dump, "Peeling for alignment will not be applied.");
4302       return;
4303     }
4304   else
4305     if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
4306       fprintf (vect_dump, "Peeling for alignment will be applied.");
4307
4308
4309   /* (1.2) Update the alignment info according to the peeling factor.
4310            If the misalignment of the DR we peel for is M, then the
4311            peeling factor is VF - M, and the misalignment of each access DR_i
4312            in the loop is DR_MISALIGNMENT (DR_i) + VF - M.
4313            If the misalignment of the DR we peel for is unknown, then the
4314            misalignment of each access DR_i in the loop is also unknown.
4315
4316            FORNOW: set the misalignment of the accesses to unknown even
4317                    if the peeling factor is known at compile time.
4318
4319            TODO: - if the peeling factor is known at compile time, use that
4320                    when updating the misalignment info of the loop DRs.
4321                  - consider accesses that are known to have the same
4322                    alignment, even if that alignment is unknown.  */
4323
4324   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
4325     {
4326       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
4327       if (dr == LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
4328         {
4329           DR_MISALIGNMENT (dr) = 0;
4330           if (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
4331             fprintf (vect_dump, "Alignment of access forced using peeling.");
4332         }
4333       else
4334         DR_MISALIGNMENT (dr) = -1;
4335     }
4336   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
4337     {
4338       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
4339       if (dr == LOOP_VINFO_UNALIGNED_DR (loop_vinfo))
4340         {
4341           DR_MISALIGNMENT (dr) = 0;
4342           if (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo)))
4343             fprintf (vect_dump, "Alignment of access forced using peeling.");
4344         }
4345       else
4346         DR_MISALIGNMENT (dr) = -1;
4347     }
4348 }
4349
4350
4351 /* Function vect_analyze_data_refs_alignment
4352
4353    Analyze the alignment of the data-references in the loop.
4354    FOR NOW: Until support for misliagned accesses is in place, only if all
4355    accesses are aligned can the loop be vectorized. This restriction will be
4356    relaxed.  */
4357
4358 static bool
4359 vect_analyze_data_refs_alignment (loop_vec_info loop_vinfo)
4360 {
4361   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
4362   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
4363   enum dr_alignment_support supportable_dr_alignment;
4364   unsigned int i;
4365
4366   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4367     fprintf (vect_dump, "=== vect_analyze_data_refs_alignment ===");
4368
4369
4370   /* This pass may take place at function granularity instead of at loop
4371      granularity.  */
4372
4373   if (!vect_compute_data_refs_alignment (loop_vinfo))
4374     {
4375       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4376                                 LOOP_LOC (loop_vinfo)))
4377         fprintf (vect_dump,
4378                  "not vectorized: can't calculate alignment for data ref.");
4379       return false;
4380     }
4381
4382
4383   /* This pass will decide on using loop versioning and/or loop peeling in
4384      order to enhance the alignment of data references in the loop.  */
4385
4386   vect_enhance_data_refs_alignment (loop_vinfo);
4387
4388
4389   /* Finally, check that all the data references in the loop can be
4390      handled with respect to their alignment.  */
4391
4392   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
4393     {
4394       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
4395       supportable_dr_alignment = vect_supportable_dr_alignment (dr);
4396       if (!supportable_dr_alignment)
4397         {
4398           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4399                                     LOOP_LOC (loop_vinfo)))
4400             fprintf (vect_dump, "not vectorized: unsupported unaligned load.");
4401           return false;
4402         }
4403       if (supportable_dr_alignment != dr_aligned
4404           && (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
4405         fprintf (vect_dump, "Vectorizing an unaligned access.");
4406     }
4407   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
4408     {
4409       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
4410       supportable_dr_alignment = vect_supportable_dr_alignment (dr);
4411       if (!supportable_dr_alignment)
4412         {
4413           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4414                                     LOOP_LOC (loop_vinfo)))
4415             fprintf (vect_dump, "not vectorized: unsupported unaligned store.");
4416           return false;
4417         }
4418       if (supportable_dr_alignment != dr_aligned
4419           && (vect_print_dump_info (REPORT_ALIGNMENT, LOOP_LOC (loop_vinfo))))
4420         fprintf (vect_dump, "Vectorizing an unaligned access.");
4421     }
4422
4423   return true;
4424 }
4425
4426
4427 /* Function vect_analyze_data_ref_access.
4428
4429    Analyze the access pattern of the data-reference DR. For now, a data access
4430    has to consecutive to be considered vectorizable.  */
4431
4432 static bool
4433 vect_analyze_data_ref_access (struct data_reference *dr)
4434 {
4435   tree stmt = DR_STMT (dr);
4436   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4437   tree step = STMT_VINFO_VECT_STEP (stmt_info);
4438   tree scalar_type = TREE_TYPE (DR_REF (dr));
4439
4440   if (!step || tree_int_cst_compare (step, TYPE_SIZE_UNIT (scalar_type)))
4441     {
4442       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4443         fprintf (vect_dump, "not consecutive access");
4444       return false;
4445     }
4446   return true;
4447 }
4448
4449
4450 /* Function vect_analyze_data_ref_accesses.
4451
4452    Analyze the access pattern of all the data references in the loop.
4453
4454    FORNOW: the only access pattern that is considered vectorizable is a
4455            simple step 1 (consecutive) access.
4456
4457    FORNOW: handle only arrays and pointer accesses.  */
4458
4459 static bool
4460 vect_analyze_data_ref_accesses (loop_vec_info loop_vinfo)
4461 {
4462   unsigned int i;
4463   varray_type loop_write_datarefs = LOOP_VINFO_DATAREF_WRITES (loop_vinfo);
4464   varray_type loop_read_datarefs = LOOP_VINFO_DATAREF_READS (loop_vinfo);
4465
4466   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4467     fprintf (vect_dump, "=== vect_analyze_data_ref_accesses ===");
4468
4469   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_write_datarefs); i++)
4470     {
4471       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_write_datarefs, i);
4472       bool ok = vect_analyze_data_ref_access (dr);
4473       if (!ok)
4474         {
4475           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4476                                       LOOP_LOC (loop_vinfo)))
4477             fprintf (vect_dump, "not vectorized: complicated access pattern.");
4478           return false;
4479         }
4480     }
4481
4482   for (i = 0; i < VARRAY_ACTIVE_SIZE (loop_read_datarefs); i++)
4483     {
4484       struct data_reference *dr = VARRAY_GENERIC_PTR (loop_read_datarefs, i);
4485       bool ok = vect_analyze_data_ref_access (dr);
4486       if (!ok)
4487         {
4488           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4489                                     LOOP_LOC (loop_vinfo)))
4490             fprintf (vect_dump, "not vectorized: complicated access pattern.");
4491           return false;
4492         }
4493     }
4494
4495   return true;
4496 }
4497
4498
4499 /* Function vect_analyze_pointer_ref_access.
4500
4501    Input:
4502    STMT - a stmt that contains a data-ref.
4503    MEMREF - a data-ref in STMT, which is an INDIRECT_REF.
4504    ACCESS_FN - the access function of MEMREF.
4505
4506    Output:
4507    If the data-ref access is vectorizable, return a data_reference structure
4508    that represents it (DR). Otherwise - return NULL.
4509    STEP - the stride of MEMREF in the loop.
4510    INIT - the initial condition of MEMREF in the loop.
4511 */
4512
4513 static struct data_reference *
4514 vect_analyze_pointer_ref_access (tree memref, tree stmt, bool is_read,
4515                                  tree access_fn, tree *ptr_init, tree *ptr_step)
4516 {
4517   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4518   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4519   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4520   tree step, init;
4521   tree reftype, innertype;
4522   tree indx_access_fn;
4523   int loopnum = loop->num;
4524   struct data_reference *dr;
4525
4526   if (!vect_is_simple_iv_evolution (loopnum, access_fn, &init, &step))
4527     {
4528       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4529                                 LOOP_LOC (loop_vinfo)))
4530         fprintf (vect_dump, "not vectorized: pointer access is not simple.");
4531       return NULL;
4532     }
4533
4534   STRIP_NOPS (init);
4535
4536   if (!expr_invariant_in_loop_p (loop, init))
4537     {
4538       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4539                                 LOOP_LOC (loop_vinfo)))
4540         fprintf (vect_dump,
4541                  "not vectorized: initial condition is not loop invariant.");
4542       return NULL;
4543     }
4544
4545   if (TREE_CODE (step) != INTEGER_CST)
4546     {
4547       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4548                                 LOOP_LOC (loop_vinfo)))
4549         fprintf (vect_dump,
4550                 "not vectorized: non constant step for pointer access.");
4551       return NULL;
4552     }
4553
4554   reftype = TREE_TYPE (TREE_OPERAND (memref, 0));
4555   if (TREE_CODE (reftype) != POINTER_TYPE)
4556     {
4557       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4558                                 LOOP_LOC (loop_vinfo)))
4559         fprintf (vect_dump, "not vectorized: unexpected pointer access form.");
4560       return NULL;
4561     }
4562
4563   reftype = TREE_TYPE (init);
4564   if (TREE_CODE (reftype) != POINTER_TYPE)
4565     {
4566       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4567                                 LOOP_LOC (loop_vinfo)))
4568         fprintf (vect_dump, "not vectorized: unexpected pointer access form.");
4569       return NULL;
4570     }
4571
4572   *ptr_step = fold_convert (ssizetype, step);
4573   innertype = TREE_TYPE (reftype);
4574   /* Check that STEP is a multiple of type size.  */
4575   if (!integer_zerop (size_binop (TRUNC_MOD_EXPR, *ptr_step,
4576                         fold_convert (ssizetype, TYPE_SIZE_UNIT (innertype)))))
4577     {
4578       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4579                                 LOOP_LOC (loop_vinfo)))
4580         fprintf (vect_dump, "not vectorized: non consecutive access.");
4581       return NULL;
4582     }
4583
4584   indx_access_fn =
4585         build_polynomial_chrec (loopnum, integer_zero_node, integer_one_node);
4586   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4587     {
4588       fprintf (vect_dump, "Access function of ptr indx: ");
4589       print_generic_expr (vect_dump, indx_access_fn, TDF_SLIM);
4590     }
4591   dr = init_data_ref (stmt, memref, NULL_TREE, indx_access_fn, is_read);
4592   *ptr_init = init;
4593   return dr;
4594 }
4595
4596
4597 /* Function vect_get_memtag.
4598
4599    The function returns the relevant variable for memory tag (for aliasing
4600    purposes).  */
4601
4602 static tree
4603 vect_get_memtag (tree memref, struct data_reference *dr)
4604 {
4605   tree symbl, tag;
4606
4607   switch (TREE_CODE (memref))
4608     {
4609     case SSA_NAME:
4610       symbl = SSA_NAME_VAR (memref);
4611       tag = get_var_ann (symbl)->type_mem_tag;
4612       if (!tag)
4613         {
4614           tree ptr = TREE_OPERAND (DR_REF (dr), 0);
4615           if (TREE_CODE (ptr) == SSA_NAME)
4616             tag = get_var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
4617         }
4618       return tag;
4619
4620     case ADDR_EXPR:
4621       return TREE_OPERAND (memref, 0);
4622
4623     default:
4624       return NULL_TREE;
4625     }
4626 }
4627
4628
4629 /* Function vect_address_analysis
4630
4631    Return the BASE of the address expression EXPR.
4632    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
4633
4634    Input:
4635    EXPR - the address expression that is being analyzed
4636    STMT - the statement that contains EXPR or its original memory reference
4637    IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
4638    VECTYPE - the type that defines the alignment (i.e, we compute
4639              alignment relative to TYPE_ALIGN(VECTYPE))
4640    DR - data_reference struct for the original memory reference
4641
4642    Output:
4643    BASE (returned value) - the base of the data reference EXPR.
4644    INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
4645    MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
4646               computation is impossible
4647    STEP - evolution of EXPR in the loop
4648    BASE_ALIGNED - indicates if BASE is aligned
4649
4650    If something unexpected is encountered (an unsupported form of data-ref),
4651    then NULL_TREE is returned.
4652  */
4653
4654 static tree
4655 vect_address_analysis (tree expr, tree stmt, bool is_read, tree vectype,
4656                        struct data_reference *dr, tree *offset, tree *misalign,
4657                        tree *step, bool *base_aligned)
4658 {
4659   tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
4660   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
4661
4662   switch (TREE_CODE (expr))
4663     {
4664     case PLUS_EXPR:
4665     case MINUS_EXPR:
4666       /* EXPR is of form {base +/- offset} (or {offset +/- base}).  */
4667       oprnd0 = TREE_OPERAND (expr, 0);
4668       oprnd1 = TREE_OPERAND (expr, 1);
4669
4670       STRIP_NOPS (oprnd0);
4671       STRIP_NOPS (oprnd1);
4672
4673       /* Recursively try to find the base of the address contained in EXPR.
4674          For offset, the returned base will be NULL.  */
4675       base_addr0 = vect_address_analysis (oprnd0, stmt, is_read, vectype, dr,
4676                                      &address_offset, &address_misalign, step,
4677                                      base_aligned);
4678
4679       base_addr1 = vect_address_analysis (oprnd1, stmt, is_read, vectype, dr,
4680                                      &address_offset, &address_misalign, step,
4681                                      base_aligned);
4682
4683       /* We support cases where only one of the operands contains an
4684          address.  */
4685       if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
4686         return NULL_TREE;
4687
4688       /* To revert STRIP_NOPS.  */
4689       oprnd0 = TREE_OPERAND (expr, 0);
4690       oprnd1 = TREE_OPERAND (expr, 1);
4691
4692       offset_expr = base_addr0 ?
4693         fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
4694
4695       /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
4696          a number, we can add it to the misalignment value calculated for base,
4697          otherwise, misalignment is NULL.  */
4698       if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
4699         *misalign = size_binop (TREE_CODE (expr), address_misalign,
4700                                 offset_expr);
4701       else
4702         *misalign = NULL_TREE;
4703
4704       /* Combine offset (from EXPR {base + offset}) with the offset calculated
4705          for base.  */
4706       *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
4707       return base_addr0 ? base_addr0 : base_addr1;
4708
4709     case ADDR_EXPR:
4710       base_address = vect_object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
4711                                    vectype, &dr, offset, misalign, step,
4712                                    base_aligned);
4713       return base_address;
4714
4715     case SSA_NAME:
4716       if (TREE_CODE (TREE_TYPE (expr)) != POINTER_TYPE)
4717         return NULL_TREE;
4718
4719       if (TYPE_ALIGN (TREE_TYPE (TREE_TYPE (expr))) < TYPE_ALIGN (vectype))
4720         {
4721           if (vect_get_ptr_offset (expr, vectype, misalign))
4722             *base_aligned = true;
4723           else
4724             *base_aligned = false;
4725         }
4726       else
4727         {
4728           *base_aligned = true;
4729           *misalign = ssize_int (0);
4730         }
4731       *offset = ssize_int (0);
4732       *step = ssize_int (0);
4733       return expr;
4734
4735     default:
4736       return NULL_TREE;
4737     }
4738 }
4739
4740
4741 /* Function vect_object_analysis
4742
4743    Return the BASE of the data reference MEMREF.
4744    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
4745    E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
4746    'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
4747    instantiated with initial_conditions of access_functions of variables,
4748    modulo alignment, and STEP is the evolution of the DR_REF in this loop.
4749
4750    Function get_inner_reference is used for the above in case of ARRAY_REF and
4751    COMPONENT_REF.
4752
4753    The structure of the function is as follows:
4754    Part 1:
4755    Case 1. For handled_component_p refs
4756           1.1 call get_inner_reference
4757             1.1.1 analyze offset expr received from get_inner_reference
4758           1.2. build data-reference structure for MEMREF
4759         (fall through with BASE)
4760    Case 2. For declarations
4761           2.1 check alignment
4762           2.2 update DR_BASE_NAME if necessary for alias
4763    Case 3. For INDIRECT_REFs
4764           3.1 get the access function
4765           3.2 analyze evolution of MEMREF
4766           3.3 set data-reference structure for MEMREF
4767           3.4 call vect_address_analysis to analyze INIT of the access function
4768
4769    Part 2:
4770    Combine the results of object and address analysis to calculate
4771    INITIAL_OFFSET, STEP and misalignment info.
4772
4773    Input:
4774    MEMREF - the memory reference that is being analyzed
4775    STMT - the statement that contains MEMREF
4776    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
4777    VECTYPE - the type that defines the alignment (i.e, we compute
4778              alignment relative to TYPE_ALIGN(VECTYPE))
4779
4780    Output:
4781    BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
4782                                    E.g, if MEMREF is a.b[k].c[i][j] the returned
4783                                    base is &a.
4784    DR - data_reference struct for MEMREF
4785    INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
4786    MISALIGN - offset of MEMREF from BASE in bytes (a constant) or NULL_TREE if
4787               the computation is impossible
4788    STEP - evolution of the DR_REF in the loop
4789    BASE_ALIGNED - indicates if BASE is aligned
4790
4791    If something unexpected is encountered (an unsupported form of data-ref),
4792    then NULL_TREE is returned.  */
4793
4794 static tree
4795 vect_object_analysis (tree memref, tree stmt, bool is_read,
4796                       tree vectype, struct data_reference **dr,
4797                       tree *offset, tree *misalign, tree *step,
4798                       bool *base_aligned)
4799 {
4800   tree base = NULL_TREE, base_address = NULL_TREE;
4801   tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
4802   tree object_step = ssize_int (0), address_step = ssize_int (0);
4803   bool object_base_aligned = true, address_base_aligned = true;
4804   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
4805   HOST_WIDE_INT pbitsize, pbitpos;
4806   tree poffset, bit_pos_in_bytes;
4807   enum machine_mode pmode;
4808   int punsignedp, pvolatilep;
4809   tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
4810   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4811   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4812   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
4813   struct data_reference *ptr_dr = NULL;
4814   tree access_fn, evolution_part, address_to_analyze;
4815
4816   /* Part 1: */
4817   /* Case 1. handled_component_p refs.  */
4818   if (handled_component_p (memref))
4819     {
4820       /* 1.1 call get_inner_reference.  */
4821       /* Find the base and the offset from it.  */
4822       base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
4823                                   &pmode, &punsignedp, &pvolatilep, false);
4824       if (!base)
4825         return NULL_TREE;
4826
4827       /* 1.1.1 analyze offset expr received from get_inner_reference.  */
4828       if (poffset
4829           && !vect_analyze_offset_expr (poffset, loop, TYPE_SIZE_UNIT (vectype),
4830                                 &object_offset, &object_misalign, &object_step))
4831         {
4832           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4833             {
4834               fprintf (vect_dump, "failed to compute offset or step for ");
4835               print_generic_expr (vect_dump, memref, TDF_SLIM);
4836             }
4837           return NULL_TREE;
4838         }
4839
4840       /* Add bit position to OFFSET and MISALIGN.  */
4841
4842       bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
4843       /* Check that there is no remainder in bits.  */
4844       if (pbitpos%BITS_PER_UNIT)
4845         {
4846           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4847             fprintf (vect_dump, "bit offset alignment.");
4848           return NULL_TREE;
4849         }
4850       object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
4851       if (object_misalign)
4852         object_misalign = size_binop (PLUS_EXPR, object_misalign,
4853                                       bit_pos_in_bytes);
4854
4855       /* Create data-reference for MEMREF. TODO: handle COMPONENT_REFs.  */
4856       if (!(*dr))
4857         {
4858           if (TREE_CODE (memref) == ARRAY_REF)
4859             *dr = analyze_array (stmt, memref, is_read);
4860           else
4861             /* FORNOW.  */
4862             return NULL_TREE;
4863         }
4864       memref = base; /* To continue analysis of BASE.  */
4865       /* fall through  */
4866     }
4867
4868   /*  Part 1: Case 2. Declarations.  */
4869   if (DECL_P (memref))
4870     {
4871       /* We expect to get a decl only if we already have a DR.  */
4872       if (!(*dr))
4873         {
4874           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4875             {
4876               fprintf (vect_dump, "unhandled decl ");
4877               print_generic_expr (vect_dump, memref, TDF_SLIM);
4878             }
4879           return NULL_TREE;
4880         }
4881
4882       /* 2.1 check the alignment.  */
4883       if (DECL_ALIGN (memref) >= TYPE_ALIGN (vectype))
4884         object_base_aligned = true;
4885       else
4886         object_base_aligned = false;
4887
4888       /* 2.2 update DR_BASE_NAME if necessary.  */
4889       if (!DR_BASE_NAME ((*dr)))
4890         /* For alias analysis.  In case the analysis of INDIRECT_REF brought
4891            us to object.  */
4892         DR_BASE_NAME ((*dr)) = memref;
4893
4894       base_address = build_fold_addr_expr (memref);
4895     }
4896
4897   /* Part 1:  Case 3. INDIRECT_REFs.  */
4898   else if (TREE_CODE (memref) == INDIRECT_REF)
4899     {
4900       /* 3.1 get the access function.  */
4901       access_fn = analyze_scalar_evolution (loop, TREE_OPERAND (memref, 0));
4902       if (!access_fn)
4903         {
4904           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4905                                     LOOP_LOC (loop_vinfo)))
4906             fprintf (vect_dump, "not vectorized: complicated pointer access.");
4907           return NULL_TREE;
4908         }
4909       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4910         {
4911           fprintf (vect_dump, "Access function of ptr: ");
4912           print_generic_expr (vect_dump, access_fn, TDF_SLIM);
4913         }
4914
4915       /* 3.2 analyze evolution of MEMREF.  */
4916       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
4917       if (evolution_part)
4918         {
4919           ptr_dr = vect_analyze_pointer_ref_access (memref, stmt, is_read,
4920                                          access_fn, &ptr_init, &ptr_step);
4921           if (!(ptr_dr))
4922             return NULL_TREE;
4923
4924           object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
4925           address_to_analyze = ptr_init;
4926         }
4927       else
4928         {
4929           if (!(*dr))
4930             {
4931               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
4932                                         LOOP_LOC (loop_vinfo)))
4933                 fprintf (vect_dump, "not vectorized: ptr is loop invariant.");
4934               return NULL_TREE;
4935             }
4936           /* Since there exists DR for MEMREF, we are analyzing the base of
4937              handled component, which not necessary has evolution in the
4938              loop.  */
4939           address_to_analyze = TREE_OPERAND (base, 0);
4940         }
4941
4942       /* 3.3 set data-reference structure for MEMREF.  */
4943       *dr = (*dr) ? *dr : ptr_dr;
4944
4945       /* 3.4 call vect_address_analysis to analyze INIT of the access
4946          function.  */
4947       base_address = vect_address_analysis (address_to_analyze, stmt, is_read,
4948                                vectype, *dr, &address_offset, &address_misalign,
4949                                &address_step, &address_base_aligned);
4950     }
4951
4952   if (!base_address)
4953     /* MEMREF cannot be analyzed.  */
4954     return NULL_TREE;
4955
4956   /* Part 2: Combine the results of object and address analysis to calculate
4957      INITIAL_OFFSET, STEP and misalignment info. */
4958   *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
4959   if (object_misalign && address_misalign)
4960     *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
4961   else
4962     *misalign = NULL_TREE;
4963   *step = size_binop (PLUS_EXPR, object_step, address_step);
4964   *base_aligned = object_base_aligned && address_base_aligned;
4965
4966   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
4967     {
4968       fprintf (vect_dump, "Results of object analysis for: ");
4969       print_generic_expr (vect_dump, memref, TDF_SLIM);
4970       fprintf (vect_dump, "\n\tbase: ");
4971       print_generic_expr (vect_dump, base, TDF_SLIM);
4972       fprintf (vect_dump, "\n\toffset: ");
4973       print_generic_expr (vect_dump, *offset, TDF_SLIM);
4974       fprintf (vect_dump, "\n\tstep: ");
4975       print_generic_expr (vect_dump, *step, TDF_SLIM);
4976       fprintf (vect_dump, "\n\tbase aligned %d\n\tmisalign: ", *base_aligned);
4977       print_generic_expr (vect_dump, *misalign, TDF_SLIM);
4978     }
4979   return base_address;
4980 }
4981
4982
4983 /* Function vect_analyze_data_refs.
4984
4985    Find all the data references in the loop.
4986
4987    The general structure of the analysis of data refs in the vectorizer is as
4988    follows:
4989    1- vect_analyze_data_refs(loop):
4990       Find and analyze all data-refs in the loop:
4991           foreach ref
4992              base_address = vect_object_analysis(ref)
4993              ref_stmt.memtag =  vect_get_memtag(base)
4994       1.1- vect_object_analysis(ref):
4995            Analyze ref, and build a DR (data_referece struct) for it;
4996            compute base, initial_offset, step and alignment.
4997            Call get_inner_reference for refs handled in this function.
4998            Call vect_addr_analysis(addr) to analyze pointer type expressions.
4999       Set ref_stmt.base, ref_stmt.initial_offset, ref_stmt.alignment, and
5000       ref_stmt.step accordingly.
5001    2- vect_analyze_dependences(): apply dependence testing using ref_stmt.DR
5002    3- vect_analyze_drs_alignment(): check that ref_stmt.alignment is ok.
5003    4- vect_analyze_drs_access(): check that ref_stmt.step is ok.
5004
5005    FORNOW: Handle aligned INDIRECT_REFs and ARRAY_REFs
5006            which base is really an array (not a pointer) and which alignment
5007            can be forced. This restriction will be relaxed.  */
5008
5009 static bool
5010 vect_analyze_data_refs (loop_vec_info loop_vinfo)
5011 {
5012   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5013   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
5014   int nbbs = loop->num_nodes;
5015   block_stmt_iterator si;
5016   int j;
5017   struct data_reference *dr;
5018
5019   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5020     fprintf (vect_dump, "=== vect_analyze_data_refs ===");
5021
5022   for (j = 0; j < nbbs; j++)
5023     {
5024       basic_block bb = bbs[j];
5025       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5026         {
5027           bool is_read = false;
5028           tree stmt = bsi_stmt (si);
5029           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
5030           v_may_def_optype v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
5031           v_must_def_optype v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
5032           vuse_optype vuses = STMT_VUSE_OPS (stmt);
5033           varray_type *datarefs = NULL;
5034           int nvuses, nv_may_defs, nv_must_defs;
5035           tree memref = NULL;
5036           tree scalar_type, vectype;
5037           tree base, offset, misalign, step, tag;
5038           bool base_aligned;
5039
5040           /* Assumption: there exists a data-ref in stmt, if and only if
5041              it has vuses/vdefs.  */
5042
5043           if (!vuses && !v_may_defs && !v_must_defs)
5044             continue;
5045
5046           nvuses = NUM_VUSES (vuses);
5047           nv_may_defs = NUM_V_MAY_DEFS (v_may_defs);
5048           nv_must_defs = NUM_V_MUST_DEFS (v_must_defs);
5049
5050           if (nvuses && (nv_may_defs || nv_must_defs))
5051             {
5052               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5053                 {
5054                   fprintf (vect_dump, "unexpected vdefs and vuses in stmt: ");
5055                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
5056                 }
5057               return false;
5058             }
5059
5060           if (TREE_CODE (stmt) != MODIFY_EXPR)
5061             {
5062               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5063                 {
5064                   fprintf (vect_dump, "unexpected vops in stmt: ");
5065                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
5066                 }
5067               return false;
5068             }
5069
5070           if (vuses)
5071             {
5072               memref = TREE_OPERAND (stmt, 1);
5073               datarefs = &(LOOP_VINFO_DATAREF_READS (loop_vinfo));
5074               is_read = true;
5075             }
5076           else /* vdefs */
5077             {
5078               memref = TREE_OPERAND (stmt, 0);
5079               datarefs = &(LOOP_VINFO_DATAREF_WRITES (loop_vinfo));
5080               is_read = false;
5081             }
5082
5083           scalar_type = TREE_TYPE (memref);
5084           vectype = get_vectype_for_scalar_type (scalar_type);
5085           if (!vectype)
5086             {
5087               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5088                 {
5089                   fprintf (vect_dump, "no vectype for stmt: ");
5090                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
5091                   fprintf (vect_dump, " scalar_type: ");
5092                   print_generic_expr (vect_dump, scalar_type, TDF_DETAILS);
5093                 }
5094               /* It is not possible to vectorize this data reference.  */
5095               return false;
5096             }
5097          /* Analyze MEMREF. If it is of a supported form, build data_reference
5098              struct for it (DR).  */
5099           dr = NULL;
5100           base = vect_object_analysis (memref, stmt, is_read, vectype, &dr,
5101                                        &offset, &misalign, &step,
5102                                        &base_aligned);
5103           if (!base)
5104             {
5105               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
5106                                         LOOP_LOC (loop_vinfo)))
5107                 {
5108                   fprintf (vect_dump, "not vectorized: unhandled data ref: ");
5109                   print_generic_expr (vect_dump, stmt, TDF_SLIM);
5110                 }
5111               return false;
5112             }
5113           /*  Find memtag for aliasing purposes.  */
5114           tag = vect_get_memtag (base, dr);
5115           if (!tag)
5116             {
5117               if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
5118                                         LOOP_LOC (loop_vinfo)))
5119                 {
5120                   fprintf (vect_dump, "not vectorized: no memtag ref: ");
5121                   print_generic_expr (vect_dump, memref, TDF_SLIM);
5122                 }
5123               return false;
5124             }
5125           STMT_VINFO_VECT_DR_BASE_ADDRESS (stmt_info) = base;
5126           STMT_VINFO_VECT_INIT_OFFSET (stmt_info) = offset;
5127           STMT_VINFO_VECT_STEP (stmt_info) = step;
5128           STMT_VINFO_VECT_MISALIGNMENT (stmt_info) = misalign;
5129           STMT_VINFO_VECT_BASE_ALIGNED_P (stmt_info) = base_aligned;
5130           STMT_VINFO_MEMTAG (stmt_info) = tag;
5131           STMT_VINFO_VECTYPE (stmt_info) = vectype;
5132           VARRAY_PUSH_GENERIC_PTR (*datarefs, dr);
5133           STMT_VINFO_DATA_REF (stmt_info) = dr;
5134         }
5135     }
5136
5137   return true;
5138 }
5139
5140
5141 /* Utility functions used by vect_mark_stmts_to_be_vectorized.  */
5142
5143 /* Function vect_mark_relevant.
5144
5145    Mark STMT as "relevant for vectorization" and add it to WORKLIST.  */
5146
5147 static void
5148 vect_mark_relevant (varray_type *worklist, tree stmt)
5149 {
5150   stmt_vec_info stmt_info;
5151
5152   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5153     fprintf (vect_dump, "mark relevant.");
5154
5155   if (TREE_CODE (stmt) == PHI_NODE)
5156     {
5157       VARRAY_PUSH_TREE (*worklist, stmt);
5158       return;
5159     }
5160
5161   stmt_info = vinfo_for_stmt (stmt);
5162
5163   if (!stmt_info)
5164     {
5165       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5166         {
5167           fprintf (vect_dump, "mark relevant: no stmt info!!.");
5168           print_generic_expr (vect_dump, stmt, TDF_SLIM);
5169         }
5170       return;
5171     }
5172
5173   if (STMT_VINFO_RELEVANT_P (stmt_info))
5174     {
5175       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5176         fprintf (vect_dump, "already marked relevant.");
5177       return;
5178     }
5179
5180   STMT_VINFO_RELEVANT_P (stmt_info) = 1;
5181   VARRAY_PUSH_TREE (*worklist, stmt);
5182 }
5183
5184
5185 /* Function vect_stmt_relevant_p.
5186
5187    Return true if STMT in loop that is represented by LOOP_VINFO is
5188    "relevant for vectorization".
5189
5190    A stmt is considered "relevant for vectorization" if:
5191    - it has uses outside the loop.
5192    - it has vdefs (it alters memory).
5193    - control stmts in the loop (except for the exit condition).
5194
5195    CHECKME: what other side effects would the vectorizer allow?  */
5196
5197 static bool
5198 vect_stmt_relevant_p (tree stmt, loop_vec_info loop_vinfo)
5199 {
5200   v_may_def_optype v_may_defs;
5201   v_must_def_optype v_must_defs;
5202   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5203   int i;
5204   dataflow_t df;
5205   int num_uses;
5206
5207   /* cond stmt other than loop exit cond.  */
5208   if (is_ctrl_stmt (stmt) && (stmt != LOOP_VINFO_EXIT_COND (loop_vinfo)))
5209     return true;
5210
5211   /* changing memory.  */
5212   if (TREE_CODE (stmt) != PHI_NODE)
5213     {
5214       v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
5215       v_must_defs = STMT_V_MUST_DEF_OPS (stmt);
5216       if (v_may_defs || v_must_defs)
5217         {
5218           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5219             fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
5220           return true;
5221         }
5222     }
5223
5224   /* uses outside the loop.  */
5225   df = get_immediate_uses (stmt);
5226   num_uses = num_immediate_uses (df);
5227   for (i = 0; i < num_uses; i++)
5228     {
5229       tree use = immediate_use (df, i);
5230       basic_block bb = bb_for_stmt (use);
5231       if (!flow_bb_inside_loop_p (loop, bb))
5232         {
5233           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5234             fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
5235           return true;
5236         }
5237     }
5238
5239   return false;
5240 }
5241
5242
5243 /* Function vect_mark_stmts_to_be_vectorized.
5244
5245    Not all stmts in the loop need to be vectorized. For example:
5246
5247      for i...
5248        for j...
5249    1.    T0 = i + j
5250    2.    T1 = a[T0]
5251
5252    3.    j = j + 1
5253
5254    Stmt 1 and 3 do not need to be vectorized, because loop control and
5255    addressing of vectorized data-refs are handled differently.
5256
5257    This pass detects such stmts.  */
5258
5259 static bool
5260 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
5261 {
5262   varray_type worklist;
5263   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5264   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
5265   unsigned int nbbs = loop->num_nodes;
5266   block_stmt_iterator si;
5267   tree stmt;
5268   stmt_ann_t ann;
5269   unsigned int i;
5270   int j;
5271   use_optype use_ops;
5272   stmt_vec_info stmt_info;
5273   basic_block bb;
5274   tree phi;
5275
5276   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5277     fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
5278
5279   bb = loop->header;
5280   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5281     {
5282       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5283         {
5284           fprintf (vect_dump, "init: phi relevant? ");
5285           print_generic_expr (vect_dump, phi, TDF_SLIM);
5286         }
5287
5288       if (vect_stmt_relevant_p (phi, loop_vinfo))
5289         {
5290           if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
5291                                     LOOP_LOC (loop_vinfo)))
5292             fprintf (vect_dump, "unsupported reduction/induction.");
5293           return false;
5294         }
5295     }
5296
5297   VARRAY_TREE_INIT (worklist, 64, "work list");
5298
5299   /* 1. Init worklist.  */
5300
5301   for (i = 0; i < nbbs; i++)
5302     {
5303       bb = bbs[i];
5304       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
5305         {
5306           stmt = bsi_stmt (si);
5307
5308           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5309             {
5310               fprintf (vect_dump, "init: stmt relevant? ");
5311               print_generic_expr (vect_dump, stmt, TDF_SLIM);
5312             }
5313
5314           stmt_info = vinfo_for_stmt (stmt);
5315           STMT_VINFO_RELEVANT_P (stmt_info) = 0;
5316
5317           if (vect_stmt_relevant_p (stmt, loop_vinfo))
5318             vect_mark_relevant (&worklist, stmt);
5319         }
5320     }
5321
5322
5323   /* 2. Process_worklist */
5324
5325   while (VARRAY_ACTIVE_SIZE (worklist) > 0)
5326     {
5327       stmt = VARRAY_TOP_TREE (worklist);
5328       VARRAY_POP (worklist);
5329
5330       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5331         {
5332           fprintf (vect_dump, "worklist: examine stmt: ");
5333           print_generic_expr (vect_dump, stmt, TDF_SLIM);
5334         }
5335
5336       /* Examine the USES in this statement. Mark all the statements which
5337          feed this statement's uses as "relevant", unless the USE is used as
5338          an array index.  */
5339
5340       if (TREE_CODE (stmt) == PHI_NODE)
5341         {
5342           /* follow the def-use chain inside the loop.  */
5343           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
5344             {
5345               tree arg = PHI_ARG_DEF (stmt, j);
5346               tree def_stmt = NULL_TREE;
5347               basic_block bb;
5348               if (!vect_is_simple_use (arg, loop_vinfo, &def_stmt))
5349                 {
5350                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
5351                                             LOOP_LOC (loop_vinfo)))
5352                     fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
5353                   varray_clear (worklist);
5354                   return false;
5355                 }
5356               if (!def_stmt)
5357                 continue;
5358
5359               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5360                 {
5361                   fprintf (vect_dump, "worklist: def_stmt: ");
5362                   print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
5363                 }
5364
5365               bb = bb_for_stmt (def_stmt);
5366               if (flow_bb_inside_loop_p (loop, bb))
5367                 vect_mark_relevant (&worklist, def_stmt);
5368             }
5369         }
5370
5371       ann = stmt_ann (stmt);
5372       use_ops = USE_OPS (ann);
5373
5374       for (i = 0; i < NUM_USES (use_ops); i++)
5375         {
5376           tree use = USE_OP (use_ops, i);
5377
5378           /* We are only interested in uses that need to be vectorized. Uses
5379              that are used for address computation are not considered relevant.
5380            */
5381           if (exist_non_indexing_operands_for_use_p (use, stmt))
5382             {
5383               tree def_stmt = NULL_TREE;
5384               basic_block bb;
5385               if (!vect_is_simple_use (use, loop_vinfo, &def_stmt))
5386                 {
5387                   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS,
5388                                             LOOP_LOC (loop_vinfo)))
5389                     fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
5390                   varray_clear (worklist);
5391                   return false;
5392                 }
5393
5394               if (!def_stmt)
5395                 continue;
5396
5397               if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5398                 {
5399                   fprintf (vect_dump, "worklist: examine use %d: ", i);
5400                   print_generic_expr (vect_dump, use, TDF_SLIM);
5401                 }
5402
5403               bb = bb_for_stmt (def_stmt);
5404               if (flow_bb_inside_loop_p (loop, bb))
5405                 vect_mark_relevant (&worklist, def_stmt);
5406             }
5407         }
5408     }                           /* while worklist */
5409
5410   varray_clear (worklist);
5411   return true;
5412 }
5413
5414
5415 /* Function vect_can_advance_ivs_p
5416
5417    In case the number of iterations that LOOP iterates in unknown at compile
5418    time, an epilog loop will be generated, and the loop induction variables
5419    (IVs) will be "advanced" to the value they are supposed to take just before
5420    the epilog loop.  Here we check that the access function of the loop IVs
5421    and the expression that represents the loop bound are simple enough.
5422    These restrictions will be relaxed in the future.  */
5423
5424 static bool
5425 vect_can_advance_ivs_p (loop_vec_info loop_vinfo)
5426 {
5427   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
5428   basic_block bb = loop->header;
5429   tree phi;
5430
5431   /* Analyze phi functions of the loop header.  */
5432
5433   for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
5434     {
5435       tree access_fn = NULL;
5436       tree evolution_part;
5437
5438       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5439         {
5440           fprintf (vect_dump, "Analyze phi: ");
5441           print_generic_expr (vect_dump, phi, TDF_SLIM);
5442         }
5443
5444       /* Skip virtual phi's. The data dependences that are associated with
5445          virtual defs/uses (i.e., memory accesses) are analyzed elsewhere.  */
5446
5447       if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
5448         {
5449           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5450             fprintf (vect_dump, "virtual phi. skip.");
5451           continue;
5452         }
5453
5454       /* Analyze the evolution function.  */
5455
5456       access_fn = instantiate_parameters
5457         (loop, analyze_scalar_evolution (loop, PHI_RESULT (phi)));
5458
5459       if (!access_fn)
5460         {
5461           if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5462             fprintf (vect_dump, "No Access function.");
5463           return false;
5464         }
5465
5466       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5467         {
5468           fprintf (vect_dump, "Access function of PHI: ");
5469           print_generic_expr (vect_dump, access_fn, TDF_SLIM);
5470         }
5471
5472       evolution_part = evolution_part_in_loop_num (access_fn, loop->num);
5473
5474       if (evolution_part == NULL_TREE)
5475         return false;
5476
5477       /* FORNOW: We do not transform initial conditions of IVs
5478          which evolution functions are a polynomial of degree >= 2.  */
5479
5480       if (tree_is_chrec (evolution_part))
5481         return false;
5482     }
5483
5484   return true;
5485 }
5486
5487
5488 /* Function vect_get_loop_niters.
5489
5490    Determine how many iterations the loop is executed.
5491    If an expression that represents the number of iterations
5492    can be constructed, place it in NUMBER_OF_ITERATIONS.
5493    Return the loop exit condition.  */
5494
5495 static tree
5496 vect_get_loop_niters (struct loop *loop, tree *number_of_iterations)
5497 {
5498   tree niters;
5499
5500   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5501     fprintf (vect_dump, "=== get_loop_niters ===");
5502
5503   niters = number_of_iterations_in_loop (loop);
5504
5505   if (niters != NULL_TREE
5506       && niters != chrec_dont_know)
5507     {
5508       *number_of_iterations = niters;
5509
5510       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5511         {
5512           fprintf (vect_dump, "==> get_loop_niters:" );
5513           print_generic_expr (vect_dump, *number_of_iterations, TDF_SLIM);
5514         }
5515     }
5516
5517   return get_loop_exit_condition (loop);
5518 }
5519
5520
5521 /* Function vect_analyze_loop_form.
5522
5523    Verify the following restrictions (some may be relaxed in the future):
5524    - it's an inner-most loop
5525    - number of BBs = 2 (which are the loop header and the latch)
5526    - the loop has a pre-header
5527    - the loop has a single entry and exit
5528    - the loop exit condition is simple enough, and the number of iterations
5529      can be analyzed (a countable loop).  */
5530
5531 static loop_vec_info
5532 vect_analyze_loop_form (struct loop *loop)
5533 {
5534   loop_vec_info loop_vinfo;
5535   tree loop_cond;
5536   tree number_of_iterations = NULL;
5537   bool rescan = false;
5538   LOC loop_loc;
5539
5540   loop_loc = find_loop_location (loop);
5541
5542   if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
5543     fprintf (vect_dump, "=== vect_analyze_loop_form ===");
5544
5545   if (loop->inner)
5546     {
5547       if (vect_print_dump_info (REPORT_OUTER_LOOPS, loop_loc))
5548         fprintf (vect_dump, "not vectorized: nested loop.");
5549       return NULL;
5550     }
5551
5552   if (!loop->single_exit
5553       || loop->num_nodes != 2
5554       || EDGE_COUNT (loop->header->preds) != 2
5555       || loop->num_entries != 1)
5556     {
5557       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
5558         {
5559           if (!loop->single_exit)
5560             fprintf (vect_dump, "not vectorized: multiple exits.");
5561           else if (loop->num_nodes != 2)
5562             fprintf (vect_dump, "not vectorized: too many BBs in loop.");
5563           else if (EDGE_COUNT (loop->header->preds) != 2)
5564             fprintf (vect_dump, "not vectorized: too many incoming edges.");
5565           else if (loop->num_entries != 1)
5566             fprintf (vect_dump, "not vectorized: too many entries.");
5567         }
5568
5569       return NULL;
5570     }
5571
5572   /* We assume that the loop exit condition is at the end of the loop. i.e,
5573      that the loop is represented as a do-while (with a proper if-guard
5574      before the loop if needed), where the loop header contains all the
5575      executable statements, and the latch is empty.  */
5576   if (!empty_block_p (loop->latch))
5577     {
5578       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
5579         fprintf (vect_dump, "not vectorized: unexpectd loop form.");
5580       return NULL;
5581     }
5582
5583   /* Make sure we have a preheader basic block.  */
5584   if (!loop->pre_header)
5585     {
5586       rescan = true;
5587       loop_split_edge_with (loop_preheader_edge (loop), NULL);
5588     }
5589
5590   /* Make sure there exists a single-predecessor exit bb:  */
5591   if (EDGE_COUNT (loop->exit_edges[0]->dest->preds) != 1)
5592     {
5593       rescan = true;
5594       loop_split_edge_with (loop->exit_edges[0], NULL);
5595     }
5596
5597   if (rescan)
5598     {
5599       flow_loop_scan (loop, LOOP_ALL);
5600       /* Flow loop scan does not update loop->single_exit field.  */
5601       loop->single_exit = loop->exit_edges[0];
5602     }
5603
5604   if (empty_block_p (loop->header))
5605     {
5606       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
5607         fprintf (vect_dump, "not vectorized: empty loop.");
5608       return NULL;
5609     }
5610
5611   loop_cond = vect_get_loop_niters (loop, &number_of_iterations);
5612   if (!loop_cond)
5613     {
5614       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
5615         fprintf (vect_dump, "not vectorized: complicated exit condition.");
5616       return NULL;
5617     }
5618
5619   if (!number_of_iterations)
5620     {
5621       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
5622         fprintf (vect_dump,
5623                  "not vectorized: number of iterations cannot be computed.");
5624       return NULL;
5625     }
5626
5627   if (chrec_contains_undetermined (number_of_iterations))
5628     {
5629       if (vect_print_dump_info (REPORT_BAD_FORM_LOOPS, loop_loc))
5630         fprintf (vect_dump, "Infinite number of iterations.");
5631       return false;
5632     }
5633
5634   loop_vinfo = new_loop_vec_info (loop);
5635   LOOP_VINFO_NITERS (loop_vinfo) = number_of_iterations;
5636
5637   if (!LOOP_VINFO_NITERS_KNOWN_P (loop_vinfo))
5638     {
5639       if (vect_print_dump_info (REPORT_DETAILS, loop_loc))
5640         {
5641           fprintf (vect_dump, "Symbolic number of iterations is ");
5642           print_generic_expr (vect_dump, number_of_iterations, TDF_DETAILS);
5643         }
5644     }
5645   else
5646   if (LOOP_VINFO_INT_NITERS (loop_vinfo) == 0)
5647     {
5648       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS, loop_loc))
5649         fprintf (vect_dump, "not vectorized: number of iterations = 0.");
5650       return NULL;
5651     }
5652
5653   LOOP_VINFO_EXIT_COND (loop_vinfo) = loop_cond;
5654   LOOP_VINFO_LOC (loop_vinfo) = loop_loc;
5655
5656   return loop_vinfo;
5657 }
5658
5659
5660 /* Function vect_analyze_loop.
5661
5662    Apply a set of analyses on LOOP, and create a loop_vec_info struct
5663    for it. The different analyses will record information in the
5664    loop_vec_info struct.  */
5665
5666 static loop_vec_info
5667 vect_analyze_loop (struct loop *loop)
5668 {
5669   bool ok;
5670   loop_vec_info loop_vinfo;
5671
5672   if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5673     fprintf (vect_dump, "===== analyze_loop_nest =====");
5674
5675   /* Check the CFG characteristics of the loop (nesting, entry/exit, etc.  */
5676
5677   loop_vinfo = vect_analyze_loop_form (loop);
5678   if (!loop_vinfo)
5679     {
5680       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5681         fprintf (vect_dump, "bad loop form.");
5682       return NULL;
5683     }
5684
5685   /* Find all data references in the loop (which correspond to vdefs/vuses)
5686      and analyze their evolution in the loop.
5687
5688      FORNOW: Handle only simple, array references, which
5689      alignment can be forced, and aligned pointer-references.  */
5690
5691   ok = vect_analyze_data_refs (loop_vinfo);
5692   if (!ok)
5693     {
5694       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
5695         fprintf (vect_dump, "bad data references.");
5696       destroy_loop_vec_info (loop_vinfo);
5697       return NULL;
5698     }
5699
5700   /* Data-flow analysis to detect stmts that do not need to be vectorized.  */
5701
5702   ok = vect_mark_stmts_to_be_vectorized (loop_vinfo);
5703   if (!ok)
5704     {
5705       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
5706         fprintf (vect_dump, "unexpected pattern.");
5707       destroy_loop_vec_info (loop_vinfo);
5708       return NULL;
5709     }
5710
5711   /* Check that all cross-iteration scalar data-flow cycles are OK.
5712      Cross-iteration cycles caused by virtual phis are analyzed separately.  */
5713
5714   ok = vect_analyze_scalar_cycles (loop_vinfo);
5715   if (!ok)
5716     {
5717       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
5718         fprintf (vect_dump, "bad scalar cycle.");
5719       destroy_loop_vec_info (loop_vinfo);
5720       return NULL;
5721     }
5722
5723   /* Analyze data dependences between the data-refs in the loop.
5724      FORNOW: fail at the first data dependence that we encounter.  */
5725
5726   ok = vect_analyze_data_ref_dependences (loop_vinfo);
5727   if (!ok)
5728     {
5729       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
5730         fprintf (vect_dump, "bad data dependence.");
5731       destroy_loop_vec_info (loop_vinfo);
5732       return NULL;
5733     }
5734
5735   /* Analyze the access patterns of the data-refs in the loop (consecutive,
5736      complex, etc.). FORNOW: Only handle consecutive access pattern.  */
5737
5738   ok = vect_analyze_data_ref_accesses (loop_vinfo);
5739   if (!ok)
5740     {
5741       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
5742         fprintf (vect_dump, "bad data access.");
5743       destroy_loop_vec_info (loop_vinfo);
5744       return NULL;
5745     }
5746
5747   /* Analyze the alignment of the data-refs in the loop.
5748      FORNOW: Only aligned accesses are handled.  */
5749
5750   ok = vect_analyze_data_refs_alignment (loop_vinfo);
5751   if (!ok)
5752     {
5753       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
5754         fprintf (vect_dump, "bad data alignment.");
5755       destroy_loop_vec_info (loop_vinfo);
5756       return NULL;
5757     }
5758
5759   /* Scan all the operations in the loop and make sure they are
5760      vectorizable.  */
5761
5762   ok = vect_analyze_operations (loop_vinfo);
5763   if (!ok)
5764     {
5765       if (vect_print_dump_info (REPORT_DETAILS, LOOP_LOC (loop_vinfo)))
5766         fprintf (vect_dump, "bad operation or unsupported loop bound.");
5767       destroy_loop_vec_info (loop_vinfo);
5768       return NULL;
5769     }
5770
5771   LOOP_VINFO_VECTORIZABLE_P (loop_vinfo) = 1;
5772
5773   return loop_vinfo;
5774 }
5775
5776
5777 /* Function need_imm_uses_for.
5778
5779    Return whether we ought to include information for 'var'
5780    when calculating immediate uses.  For this pass we only want use
5781    information for non-virtual variables.  */
5782
5783 static bool
5784 need_imm_uses_for (tree var)
5785 {
5786   return is_gimple_reg (var);
5787 }
5788
5789
5790 /* Function vectorize_loops.
5791
5792    Entry Point to loop vectorization phase.  */
5793
5794 void
5795 vectorize_loops (struct loops *loops)
5796 {
5797   unsigned int i, loops_num;
5798   unsigned int num_vectorized_loops = 0;
5799
5800   /* Fix the verbosity level if not defined explicitly by the user.  */
5801   vect_set_dump_settings ();
5802
5803   /* Does the target support SIMD?  */
5804   /* FORNOW: until more sophisticated machine modelling is in place.  */
5805   if (!UNITS_PER_SIMD_WORD)
5806     {
5807       if (vect_print_dump_info (REPORT_DETAILS, UNKNOWN_LOC))
5808         fprintf (vect_dump, "vectorizer: target vector size is not defined.");
5809       return;
5810     }
5811
5812 #ifdef ENABLE_CHECKING
5813   verify_loop_closed_ssa ();
5814 #endif
5815
5816   compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
5817
5818   /*  ----------- Analyze loops. -----------  */
5819
5820   /* If some loop was duplicated, it gets bigger number
5821      than all previously defined loops. This fact allows us to run
5822      only over initial loops skipping newly generated ones.  */
5823   loops_num = loops->num;
5824   for (i = 1; i < loops_num; i++)
5825     {
5826       loop_vec_info loop_vinfo;
5827       struct loop *loop = loops->parray[i];
5828
5829       if (!loop)
5830         continue;
5831
5832       loop_vinfo = vect_analyze_loop (loop);
5833       loop->aux = loop_vinfo;
5834
5835       if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
5836         continue;
5837
5838       vect_transform_loop (loop_vinfo, loops);
5839       num_vectorized_loops++;
5840     }
5841
5842   if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS, UNKNOWN_LOC))
5843     fprintf (vect_dump, "vectorized %u loops in function.\n",
5844              num_vectorized_loops);
5845
5846   /*  ----------- Finalize. -----------  */
5847
5848   free_df ();
5849   for (i = 1; i < loops_num; i++)
5850     {
5851       struct loop *loop = loops->parray[i];
5852       loop_vec_info loop_vinfo;
5853
5854       if (!loop)
5855         continue;
5856       loop_vinfo = loop->aux;
5857       destroy_loop_vec_info (loop_vinfo);
5858       loop->aux = NULL;
5859     }
5860
5861   rewrite_into_ssa (false);
5862   rewrite_into_loop_closed_ssa (); /* FORNOW */
5863   bitmap_clear (vars_to_rename);
5864 }