gcc/tree-vectorizer.c

   1 /* Loop Vectorization
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* Loop Vectorization Pass.
  22
  23    This pass tries to vectorize loops. This first implementation focuses on
  24    simple inner-most loops, with no conditional control flow, and a set of
  25    simple operations which vector form can be expressed using existing
  26    tree codes (PLUS, MULT etc).
  27
  28    For example, the vectorizer transforms the following simple loop:
  29
  30         short a[N]; short b[N]; short c[N]; int i;
  31
  32         for (i=0; i<N; i++){
  33           a[i] = b[i] + c[i];
  34         }
  35
  36    as if it was manually vectorized by rewriting the source code into:
  37
  38         typedef int __attribute__((mode(V8HI))) v8hi;
  39         short a[N];  short b[N]; short c[N];   int i;
  40         v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
  41         v8hi va, vb, vc;
  42
  43         for (i=0; i<N/8; i++){
  44           vb = pb[i];
  45           vc = pc[i];
  46           va = vb + vc;
  47           pa[i] = va;
  48         }
  49
  50         The main entry to this pass is vectorize_loops(), in which
  51    the vectorizer applies a set of analyses on a given set of loops,
  52    followed by the actual vectorization transformation for the loops that
  53    had successfully passed the analysis phase.
  54
  55         Throughout this pass we make a distinction between two types of
  56    data: scalars (which are represented by SSA_NAMES), and memory references
  57    ("data-refs"). These two types of data require different handling both
  58    during analysis and transformation. The types of data-refs that the
  59    vectorizer currently supports are ARRAY_REFS which base is an array DECL
  60    (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
  61    accesses are required to have a  simple (consecutive) access pattern.
  62
  63    Analysis phase:
  64    ===============
  65         The driver for the analysis phase is vect_analyze_loop_nest().
  66    It applies a set of analyses, some of which rely on the scalar evolution
  67    analyzer (scev) developed by Sebastian Pop.
  68
  69         During the analysis phase the vectorizer records some information
  70    per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
  71    loop, as well as general information about the loop as a whole, which is
  72    recorded in a "loop_vec_info" struct attached to each loop.
  73
  74    Transformation phase:
  75    =====================
  76         The loop transformation phase scans all the stmts in the loop, and
  77    creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
  78    the loop that needs to be vectorized. It insert the vector code sequence
  79    just before the scalar stmt S, and records a pointer to the vector code
  80    in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
  81    attached to S). This pointer will be used for the vectorization of following
  82    stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
  83    otherwise, we rely on dead code elimination for removing it.
  84
  85         For example, say stmt S1 was vectorized into stmt VS1:
  86
  87    VS1: vb = px[i];
  88    S1:  b = x[i];    STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
  89    S2:  a = b;
  90
  91    To vectorize stmt S2, the vectorizer first finds the stmt that defines
  92    the operand 'b' (S1), and gets the relevant vector def 'vb' from the
  93    vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
  94    resulting sequence would be:
  95
  96    VS1: vb = px[i];
  97    S1:  b = x[i];       STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
  98    VS2: va = vb;
  99    S2:  a = b;          STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
 100
 101         Operands that are not SSA_NAMEs, are data-refs that appear in
 102    load/store operations (like 'x[i]' in S1), and are handled differently.
 103
 104    Target modeling:
 105    =================
 106         Currently the only target specific information that is used is the
 107    size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can
 108    support different sizes of vectors, for now will need to specify one value
 109    for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
 110
 111         Since we only vectorize operations which vector form can be
 112    expressed using existing tree codes, to verify that an operation is
 113    supported, the vectorizer checks the relevant optab at the relevant
 114    machine_mode (e.g, optab_handler (add_optab, V8HImode)->insn_code). If
 115    the value found is CODE_FOR_nothing, then there's no target support, and
 116    we can't vectorize the stmt.
 117
 118    For additional information on this project see:
 119    http://gcc.gnu.org/projects/tree-ssa/vectorization.html
 120 */
 121
 122 #include "config.h"
 123 #include "system.h"
 124 #include "coretypes.h"
 125 #include "tm.h"
 126 #include "ggc.h"
 127 #include "tree.h"
 128 #include "target.h"
 129 #include "rtl.h"
 130 #include "basic-block.h"
 131 #include "diagnostic.h"
 132 #include "tree-flow.h"
 133 #include "tree-dump.h"
 134 #include "timevar.h"
 135 #include "cfgloop.h"
 136 #include "cfglayout.h"
 137 #include "expr.h"
 138 #include "recog.h"
 139 #include "optabs.h"
 140 #include "params.h"
 141 #include "toplev.h"
 142 #include "tree-chrec.h"
 143 #include "tree-data-ref.h"
 144 #include "tree-scalar-evolution.h"
 145 #include "input.h"
 146 #include "tree-vectorizer.h"
 147 #include "tree-pass.h"
 148
 149 /*************************************************************************
 150   Simple Loop Peeling Utilities
 151  *************************************************************************/
 152 static void slpeel_update_phis_for_duplicate_loop
 153   (struct loop *, struct loop *, bool after);
 154 static void slpeel_update_phi_nodes_for_guard1
 155   (edge, struct loop *, bool, basic_block *, bitmap *);
 156 static void slpeel_update_phi_nodes_for_guard2
 157   (edge, struct loop *, bool, basic_block *);
 158 static edge slpeel_add_loop_guard (basic_block, tree, basic_block, basic_block);
 159
 160 static void rename_use_op (use_operand_p);
 161 static void rename_variables_in_bb (basic_block);
 162 static void rename_variables_in_loop (struct loop *);
 163
 164 /*************************************************************************
 165   General Vectorization Utilities
 166  *************************************************************************/
 167 static void vect_set_dump_settings (void);
 168
 169 /* vect_dump will be set to stderr or dump_file if exist.  */
 170 FILE *vect_dump;
 171
 172 /* vect_verbosity_level set to an invalid value
 173    to mark that it's uninitialized.  */
 174 enum verbosity_levels vect_verbosity_level = MAX_VERBOSITY_LEVEL;
 175
 176 /* Loop location.  */
 177 static LOC vect_loop_location;
 178
 179 /* Bitmap of virtual variables to be renamed.  */
 180 bitmap vect_memsyms_to_rename;
 181 \f
 182 /*************************************************************************
 183   Simple Loop Peeling Utilities
 184
 185   Utilities to support loop peeling for vectorization purposes.
 186  *************************************************************************/
 187
 188
 189 /* Renames the use *OP_P.  */
 190
 191 static void
 192 rename_use_op (use_operand_p op_p)
 193 {
 194   tree new_name;
 195
 196   if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
 197     return;
 198
 199   new_name = get_current_def (USE_FROM_PTR (op_p));
 200
 201   /* Something defined outside of the loop.  */
 202   if (!new_name)
 203     return;
 204
 205   /* An ordinary ssa name defined in the loop.  */
 206
 207   SET_USE (op_p, new_name);
 208 }
 209
 210
 211 /* Renames the variables in basic block BB.  */
 212
 213 static void
 214 rename_variables_in_bb (basic_block bb)
 215 {
 216   tree phi;
 217   block_stmt_iterator bsi;
 218   tree stmt;
 219   use_operand_p use_p;
 220   ssa_op_iter iter;
 221   edge e;
 222   edge_iterator ei;
 223   struct loop *loop = bb->loop_father;
 224
 225   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 226     {
 227       stmt = bsi_stmt (bsi);
 228       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 229         rename_use_op (use_p);
 230     }
 231
 232   FOR_EACH_EDGE (e, ei, bb->succs)
 233     {
 234       if (!flow_bb_inside_loop_p (loop, e->dest))
 235         continue;
 236       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 237         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e));
 238     }
 239 }
 240
 241
 242 /* Renames variables in new generated LOOP.  */
 243
 244 static void
 245 rename_variables_in_loop (struct loop *loop)
 246 {
 247   unsigned i;
 248   basic_block *bbs;
 249
 250   bbs = get_loop_body (loop);
 251
 252   for (i = 0; i < loop->num_nodes; i++)
 253     rename_variables_in_bb (bbs[i]);
 254
 255   free (bbs);
 256 }
 257
 258
 259 /* Update the PHI nodes of NEW_LOOP.
 260
 261    NEW_LOOP is a duplicate of ORIG_LOOP.
 262    AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
 263    AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
 264    executes before it.  */
 265
 266 static void
 267 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
 268                                        struct loop *new_loop, bool after)
 269 {
 270   tree new_ssa_name;
 271   tree phi_new, phi_orig;
 272   tree def;
 273   edge orig_loop_latch = loop_latch_edge (orig_loop);
 274   edge orig_entry_e = loop_preheader_edge (orig_loop);
 275   edge new_loop_exit_e = single_exit (new_loop);
 276   edge new_loop_entry_e = loop_preheader_edge (new_loop);
 277   edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
 278
 279   /*
 280      step 1. For each loop-header-phi:
 281              Add the first phi argument for the phi in NEW_LOOP
 282             (the one associated with the entry of NEW_LOOP)
 283
 284      step 2. For each loop-header-phi:
 285              Add the second phi argument for the phi in NEW_LOOP
 286             (the one associated with the latch of NEW_LOOP)
 287
 288      step 3. Update the phis in the successor block of NEW_LOOP.
 289
 290         case 1: NEW_LOOP was placed before ORIG_LOOP:
 291                 The successor block of NEW_LOOP is the header of ORIG_LOOP.
 292                 Updating the phis in the successor block can therefore be done
 293                 along with the scanning of the loop header phis, because the
 294                 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
 295                 phi nodes, organized in the same order.
 296
 297         case 2: NEW_LOOP was placed after ORIG_LOOP:
 298                 The successor block of NEW_LOOP is the original exit block of
 299                 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
 300                 We postpone updating these phis to a later stage (when
 301                 loop guards are added).
 302    */
 303
 304
 305   /* Scan the phis in the headers of the old and new loops
 306      (they are organized in exactly the same order).  */
 307
 308   for (phi_new = phi_nodes (new_loop->header),
 309        phi_orig = phi_nodes (orig_loop->header);
 310        phi_new && phi_orig;
 311        phi_new = PHI_CHAIN (phi_new), phi_orig = PHI_CHAIN (phi_orig))
 312     {
 313       /* step 1.  */
 314       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
 315       add_phi_arg (phi_new, def, new_loop_entry_e);
 316
 317       /* step 2.  */
 318       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
 319       if (TREE_CODE (def) != SSA_NAME)
 320         continue;
 321
 322       new_ssa_name = get_current_def (def);
 323       if (!new_ssa_name)
 324         {
 325           /* This only happens if there are no definitions
 326              inside the loop. use the phi_result in this case.  */
 327           new_ssa_name = PHI_RESULT (phi_new);
 328         }
 329
 330       /* An ordinary ssa name defined in the loop.  */
 331       add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
 332
 333       /* step 3 (case 1).  */
 334       if (!after)
 335         {
 336           gcc_assert (new_loop_exit_e == orig_entry_e);
 337           SET_PHI_ARG_DEF (phi_orig,
 338                            new_loop_exit_e->dest_idx,
 339                            new_ssa_name);
 340         }
 341     }
 342 }
 343
 344
 345 /* Update PHI nodes for a guard of the LOOP.
 346
 347    Input:
 348    - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
 349         controls whether LOOP is to be executed.  GUARD_EDGE is the edge that
 350         originates from the guard-bb, skips LOOP and reaches the (unique) exit
 351         bb of LOOP.  This loop-exit-bb is an empty bb with one successor.
 352         We denote this bb NEW_MERGE_BB because before the guard code was added
 353         it had a single predecessor (the LOOP header), and now it became a merge
 354         point of two paths - the path that ends with the LOOP exit-edge, and
 355         the path that ends with GUARD_EDGE.
 356    - NEW_EXIT_BB: New basic block that is added by this function between LOOP
 357         and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
 358
 359    ===> The CFG before the guard-code was added:
 360         LOOP_header_bb:
 361           loop_body
 362           if (exit_loop) goto update_bb
 363           else           goto LOOP_header_bb
 364         update_bb:
 365
 366    ==> The CFG after the guard-code was added:
 367         guard_bb:
 368           if (LOOP_guard_condition) goto new_merge_bb
 369           else                      goto LOOP_header_bb
 370         LOOP_header_bb:
 371           loop_body
 372           if (exit_loop_condition) goto new_merge_bb
 373           else                     goto LOOP_header_bb
 374         new_merge_bb:
 375           goto update_bb
 376         update_bb:
 377
 378    ==> The CFG after this function:
 379         guard_bb:
 380           if (LOOP_guard_condition) goto new_merge_bb
 381           else                      goto LOOP_header_bb
 382         LOOP_header_bb:
 383           loop_body
 384           if (exit_loop_condition) goto new_exit_bb
 385           else                     goto LOOP_header_bb
 386         new_exit_bb:
 387         new_merge_bb:
 388           goto update_bb
 389         update_bb:
 390
 391    This function:
 392    1. creates and updates the relevant phi nodes to account for the new
 393       incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
 394       1.1. Create phi nodes at NEW_MERGE_BB.
 395       1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
 396            UPDATE_BB).  UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
 397    2. preserves loop-closed-ssa-form by creating the required phi nodes
 398       at the exit of LOOP (i.e, in NEW_EXIT_BB).
 399
 400    There are two flavors to this function:
 401
 402    slpeel_update_phi_nodes_for_guard1:
 403      Here the guard controls whether we enter or skip LOOP, where LOOP is a
 404      prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
 405      for variables that have phis in the loop header.
 406
 407    slpeel_update_phi_nodes_for_guard2:
 408      Here the guard controls whether we enter or skip LOOP, where LOOP is an
 409      epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
 410      for variables that have phis in the loop exit.
 411
 412    I.E., the overall structure is:
 413
 414         loop1_preheader_bb:
 415                 guard1 (goto loop1/merg1_bb)
 416         loop1
 417         loop1_exit_bb:
 418                 guard2 (goto merge1_bb/merge2_bb)
 419         merge1_bb
 420         loop2
 421         loop2_exit_bb
 422         merge2_bb
 423         next_bb
 424
 425    slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
 426    loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
 427    that have phis in loop1->header).
 428
 429    slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
 430    loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
 431    that have phis in next_bb). It also adds some of these phis to
 432    loop1_exit_bb.
 433
 434    slpeel_update_phi_nodes_for_guard1 is always called before
 435    slpeel_update_phi_nodes_for_guard2. They are both needed in order
 436    to create correct data-flow and loop-closed-ssa-form.
 437
 438    Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
 439    that change between iterations of a loop (and therefore have a phi-node
 440    at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
 441    phis for variables that are used out of the loop (and therefore have
 442    loop-closed exit phis). Some variables may be both updated between
 443    iterations and used after the loop. This is why in loop1_exit_bb we
 444    may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
 445    and exit phis (created by slpeel_update_phi_nodes_for_guard2).
 446
 447    - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
 448      an original loop. i.e., we have:
 449
 450            orig_loop
 451            guard_bb (goto LOOP/new_merge)
 452            new_loop <-- LOOP
 453            new_exit
 454            new_merge
 455            next_bb
 456
 457      If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
 458      have:
 459
 460            new_loop
 461            guard_bb (goto LOOP/new_merge)
 462            orig_loop <-- LOOP
 463            new_exit
 464            new_merge
 465            next_bb
 466
 467      The SSA names defined in the original loop have a current
 468      reaching definition that that records the corresponding new
 469      ssa-name used in the new duplicated loop copy.
 470   */
 471
 472 /* Function slpeel_update_phi_nodes_for_guard1
 473
 474    Input:
 475    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
 476    - DEFS - a bitmap of ssa names to mark new names for which we recorded
 477             information.
 478
 479    In the context of the overall structure, we have:
 480
 481         loop1_preheader_bb:
 482                 guard1 (goto loop1/merg1_bb)
 483 LOOP->  loop1
 484         loop1_exit_bb:
 485                 guard2 (goto merge1_bb/merge2_bb)
 486         merge1_bb
 487         loop2
 488         loop2_exit_bb
 489         merge2_bb
 490         next_bb
 491
 492    For each name updated between loop iterations (i.e - for each name that has
 493    an entry (loop-header) phi in LOOP) we create a new phi in:
 494    1. merge1_bb (to account for the edge from guard1)
 495    2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
 496 */
 497
 498 static void
 499 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
 500                                     bool is_new_loop, basic_block *new_exit_bb,
 501                                     bitmap *defs)
 502 {
 503   tree orig_phi, new_phi;
 504   tree update_phi, update_phi2;
 505   tree guard_arg, loop_arg;
 506   basic_block new_merge_bb = guard_edge->dest;
 507   edge e = EDGE_SUCC (new_merge_bb, 0);
 508   basic_block update_bb = e->dest;
 509   basic_block orig_bb = loop->header;
 510   edge new_exit_e;
 511   tree current_new_name;
 512   tree name;
 513
 514   /* Create new bb between loop and new_merge_bb.  */
 515   *new_exit_bb = split_edge (single_exit (loop));
 516
 517   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
 518
 519   for (orig_phi = phi_nodes (orig_bb), update_phi = phi_nodes (update_bb);
 520        orig_phi && update_phi;
 521        orig_phi = PHI_CHAIN (orig_phi), update_phi = PHI_CHAIN (update_phi))
 522     {
 523       /* Virtual phi; Mark it for renaming. We actually want to call
 524          mar_sym_for_renaming, but since all ssa renaming datastructures
 525          are going to be freed before we get to call ssa_upate, we just
 526          record this name for now in a bitmap, and will mark it for
 527          renaming later.  */
 528       name = PHI_RESULT (orig_phi);
 529       if (!is_gimple_reg (SSA_NAME_VAR (name)))
 530         bitmap_set_bit (vect_memsyms_to_rename, DECL_UID (SSA_NAME_VAR (name)));
 531
 532       /** 1. Handle new-merge-point phis  **/
 533
 534       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
 535       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 536                                  new_merge_bb);
 537
 538       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
 539             of LOOP. Set the two phi args in NEW_PHI for these edges:  */
 540       loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
 541       guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
 542
 543       add_phi_arg (new_phi, loop_arg, new_exit_e);
 544       add_phi_arg (new_phi, guard_arg, guard_edge);
 545
 546       /* 1.3. Update phi in successor block.  */
 547       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
 548                   || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
 549       SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
 550       update_phi2 = new_phi;
 551
 552
 553       /** 2. Handle loop-closed-ssa-form phis  **/
 554
 555       if (!is_gimple_reg (PHI_RESULT (orig_phi)))
 556         continue;
 557
 558       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
 559       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 560                                  *new_exit_bb);
 561
 562       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
 563       add_phi_arg (new_phi, loop_arg, single_exit (loop));
 564
 565       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
 566       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
 567       SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
 568
 569       /* 2.4. Record the newly created name with set_current_def.
 570          We want to find a name such that
 571                 name = get_current_def (orig_loop_name)
 572          and to set its current definition as follows:
 573                 set_current_def (name, new_phi_name)
 574
 575          If LOOP is a new loop then loop_arg is already the name we're
 576          looking for. If LOOP is the original loop, then loop_arg is
 577          the orig_loop_name and the relevant name is recorded in its
 578          current reaching definition.  */
 579       if (is_new_loop)
 580         current_new_name = loop_arg;
 581       else
 582         {
 583           current_new_name = get_current_def (loop_arg);
 584           /* current_def is not available only if the variable does not
 585              change inside the loop, in which case we also don't care
 586              about recording a current_def for it because we won't be
 587              trying to create loop-exit-phis for it.  */
 588           if (!current_new_name)
 589             continue;
 590         }
 591       gcc_assert (get_current_def (current_new_name) == NULL_TREE);
 592
 593       set_current_def (current_new_name, PHI_RESULT (new_phi));
 594       bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
 595     }
 596
 597   set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
 598 }
 599
 600
 601 /* Function slpeel_update_phi_nodes_for_guard2
 602
 603    Input:
 604    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
 605
 606    In the context of the overall structure, we have:
 607
 608         loop1_preheader_bb:
 609                 guard1 (goto loop1/merg1_bb)
 610         loop1
 611         loop1_exit_bb:
 612                 guard2 (goto merge1_bb/merge2_bb)
 613         merge1_bb
 614 LOOP->  loop2
 615         loop2_exit_bb
 616         merge2_bb
 617         next_bb
 618
 619    For each name used out side the loop (i.e - for each name that has an exit
 620    phi in next_bb) we create a new phi in:
 621    1. merge2_bb (to account for the edge from guard_bb)
 622    2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
 623    3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
 624       if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
 625 */
 626
 627 static void
 628 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
 629                                     bool is_new_loop, basic_block *new_exit_bb)
 630 {
 631   tree orig_phi, new_phi;
 632   tree update_phi, update_phi2;
 633   tree guard_arg, loop_arg;
 634   basic_block new_merge_bb = guard_edge->dest;
 635   edge e = EDGE_SUCC (new_merge_bb, 0);
 636   basic_block update_bb = e->dest;
 637   edge new_exit_e;
 638   tree orig_def, orig_def_new_name;
 639   tree new_name, new_name2;
 640   tree arg;
 641
 642   /* Create new bb between loop and new_merge_bb.  */
 643   *new_exit_bb = split_edge (single_exit (loop));
 644
 645   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
 646
 647   for (update_phi = phi_nodes (update_bb); update_phi;
 648        update_phi = PHI_CHAIN (update_phi))
 649     {
 650       orig_phi = update_phi;
 651       orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
 652       /* This loop-closed-phi actually doesn't represent a use
 653          out of the loop - the phi arg is a constant.  */
 654       if (TREE_CODE (orig_def) != SSA_NAME)
 655         continue;
 656       orig_def_new_name = get_current_def (orig_def);
 657       arg = NULL_TREE;
 658
 659       /** 1. Handle new-merge-point phis  **/
 660
 661       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
 662       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 663                                  new_merge_bb);
 664
 665       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
 666             of LOOP. Set the two PHI args in NEW_PHI for these edges:  */
 667       new_name = orig_def;
 668       new_name2 = NULL_TREE;
 669       if (orig_def_new_name)
 670         {
 671           new_name = orig_def_new_name;
 672           /* Some variables have both loop-entry-phis and loop-exit-phis.
 673              Such variables were given yet newer names by phis placed in
 674              guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
 675              new_name2 = get_current_def (get_current_def (orig_name)).  */
 676           new_name2 = get_current_def (new_name);
 677         }
 678
 679       if (is_new_loop)
 680         {
 681           guard_arg = orig_def;
 682           loop_arg = new_name;
 683         }
 684       else
 685         {
 686           guard_arg = new_name;
 687           loop_arg = orig_def;
 688         }
 689       if (new_name2)
 690         guard_arg = new_name2;
 691
 692       add_phi_arg (new_phi, loop_arg, new_exit_e);
 693       add_phi_arg (new_phi, guard_arg, guard_edge);
 694
 695       /* 1.3. Update phi in successor block.  */
 696       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
 697       SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
 698       update_phi2 = new_phi;
 699
 700
 701       /** 2. Handle loop-closed-ssa-form phis  **/
 702
 703       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
 704       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 705                                  *new_exit_bb);
 706
 707       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
 708       add_phi_arg (new_phi, loop_arg, single_exit (loop));
 709
 710       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
 711       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
 712       SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
 713
 714
 715       /** 3. Handle loop-closed-ssa-form phis for first loop  **/
 716
 717       /* 3.1. Find the relevant names that need an exit-phi in
 718          GUARD_BB, i.e. names for which
 719          slpeel_update_phi_nodes_for_guard1 had not already created a
 720          phi node. This is the case for names that are used outside
 721          the loop (and therefore need an exit phi) but are not updated
 722          across loop iterations (and therefore don't have a
 723          loop-header-phi).
 724
 725          slpeel_update_phi_nodes_for_guard1 is responsible for
 726          creating loop-exit phis in GUARD_BB for names that have a
 727          loop-header-phi.  When such a phi is created we also record
 728          the new name in its current definition.  If this new name
 729          exists, then guard_arg was set to this new name (see 1.2
 730          above).  Therefore, if guard_arg is not this new name, this
 731          is an indication that an exit-phi in GUARD_BB was not yet
 732          created, so we take care of it here.  */
 733       if (guard_arg == new_name2)
 734         continue;
 735       arg = guard_arg;
 736
 737       /* 3.2. Generate new phi node in GUARD_BB:  */
 738       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 739                                  guard_edge->src);
 740
 741       /* 3.3. GUARD_BB has one incoming edge:  */
 742       gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
 743       add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
 744
 745       /* 3.4. Update phi in successor of GUARD_BB:  */
 746       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
 747                                                                 == guard_arg);
 748       SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
 749     }
 750
 751   set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
 752 }
 753
 754
 755 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
 756    that starts at zero, increases by one and its limit is NITERS.
 757
 758    Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
 759
 760 void
 761 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
 762 {
 763   tree indx_before_incr, indx_after_incr, cond_stmt, cond;
 764   tree orig_cond;
 765   edge exit_edge = single_exit (loop);
 766   block_stmt_iterator loop_cond_bsi;
 767   block_stmt_iterator incr_bsi;
 768   bool insert_after;
 769   tree init = build_int_cst (TREE_TYPE (niters), 0);
 770   tree step = build_int_cst (TREE_TYPE (niters), 1);
 771   LOC loop_loc;
 772
 773   orig_cond = get_loop_exit_condition (loop);
 774   gcc_assert (orig_cond);
 775   loop_cond_bsi = bsi_for_stmt (orig_cond);
 776
 777   standard_iv_increment_position (loop, &incr_bsi, &insert_after);
 778   create_iv (init, step, NULL_TREE, loop,
 779              &incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
 780
 781   if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop.  */
 782     cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
 783   else /* 'then' edge loops back.  */
 784     cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
 785
 786   cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
 787                       NULL_TREE, NULL_TREE);
 788   bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
 789
 790   /* Remove old loop exit test:  */
 791   bsi_remove (&loop_cond_bsi, true);
 792
 793   loop_loc = find_loop_location (loop);
 794   if (dump_file && (dump_flags & TDF_DETAILS))
 795     {
 796       if (loop_loc != UNKNOWN_LOC)
 797         fprintf (dump_file, "\nloop at %s:%d: ",
 798                  LOC_FILE (loop_loc), LOC_LINE (loop_loc));
 799       print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
 800     }
 801
 802   loop->nb_iterations = niters;
 803 }
 804
 805
 806 /* Given LOOP this function generates a new copy of it and puts it
 807    on E which is either the entry or exit of LOOP.  */
 808
 809 static struct loop *
 810 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
 811 {
 812   struct loop *new_loop;
 813   basic_block *new_bbs, *bbs;
 814   bool at_exit;
 815   bool was_imm_dom;
 816   basic_block exit_dest;
 817   tree phi, phi_arg;
 818   edge exit, new_exit;
 819
 820   at_exit = (e == single_exit (loop));
 821   if (!at_exit && e != loop_preheader_edge (loop))
 822     return NULL;
 823
 824   bbs = get_loop_body (loop);
 825
 826   /* Check whether duplication is possible.  */
 827   if (!can_copy_bbs_p (bbs, loop->num_nodes))
 828     {
 829       free (bbs);
 830       return NULL;
 831     }
 832
 833   /* Generate new loop structure.  */
 834   new_loop = duplicate_loop (loop, loop_outer (loop));
 835   if (!new_loop)
 836     {
 837       free (bbs);
 838       return NULL;
 839     }
 840
 841   exit_dest = single_exit (loop)->dest;
 842   was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
 843                                           exit_dest) == loop->header ?
 844                  true : false);
 845
 846   new_bbs = XNEWVEC (basic_block, loop->num_nodes);
 847
 848   exit = single_exit (loop);
 849   copy_bbs (bbs, loop->num_nodes, new_bbs,
 850             &exit, 1, &new_exit, NULL,
 851             e->src);
 852
 853   /* Duplicating phi args at exit bbs as coming
 854      also from exit of duplicated loop.  */
 855   for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
 856     {
 857       phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
 858       if (phi_arg)
 859         {
 860           edge new_loop_exit_edge;
 861
 862           if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
 863             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
 864           else
 865             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
 866
 867           add_phi_arg (phi, phi_arg, new_loop_exit_edge);
 868         }
 869     }
 870
 871   if (at_exit) /* Add the loop copy at exit.  */
 872     {
 873       redirect_edge_and_branch_force (e, new_loop->header);
 874       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
 875       if (was_imm_dom)
 876         set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
 877     }
 878   else /* Add the copy at entry.  */
 879     {
 880       edge new_exit_e;
 881       edge entry_e = loop_preheader_edge (loop);
 882       basic_block preheader = entry_e->src;
 883
 884       if (!flow_bb_inside_loop_p (new_loop,
 885                                   EDGE_SUCC (new_loop->header, 0)->dest))
 886         new_exit_e = EDGE_SUCC (new_loop->header, 0);
 887       else
 888         new_exit_e = EDGE_SUCC (new_loop->header, 1);
 889
 890       redirect_edge_and_branch_force (new_exit_e, loop->header);
 891       set_immediate_dominator (CDI_DOMINATORS, loop->header,
 892                                new_exit_e->src);
 893
 894       /* We have to add phi args to the loop->header here as coming
 895          from new_exit_e edge.  */
 896       for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
 897         {
 898           phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
 899           if (phi_arg)
 900             add_phi_arg (phi, phi_arg, new_exit_e);
 901         }
 902
 903       redirect_edge_and_branch_force (entry_e, new_loop->header);
 904       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
 905     }
 906
 907   free (new_bbs);
 908   free (bbs);
 909
 910   return new_loop;
 911 }
 912
 913
 914 /* Given the condition statement COND, put it as the last statement
 915    of GUARD_BB; EXIT_BB is the basic block to skip the loop;
 916    Assumes that this is the single exit of the guarded loop.
 917    Returns the skip edge.  */
 918
 919 static edge
 920 slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
 921                        basic_block dom_bb)
 922 {
 923   block_stmt_iterator bsi;
 924   edge new_e, enter_e;
 925   tree cond_stmt;
 926   tree gimplify_stmt_list;
 927
 928   enter_e = EDGE_SUCC (guard_bb, 0);
 929   enter_e->flags &= ~EDGE_FALLTHRU;
 930   enter_e->flags |= EDGE_FALSE_VALUE;
 931   bsi = bsi_last (guard_bb);
 932
 933   cond =
 934     force_gimple_operand (cond, &gimplify_stmt_list, true,
 935                           NULL_TREE);
 936   cond_stmt = build3 (COND_EXPR, void_type_node, cond,
 937                       NULL_TREE, NULL_TREE);
 938   if (gimplify_stmt_list)
 939     bsi_insert_after (&bsi, gimplify_stmt_list, BSI_NEW_STMT);
 940
 941   bsi = bsi_last (guard_bb);
 942   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
 943
 944   /* Add new edge to connect guard block to the merge/loop-exit block.  */
 945   new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
 946   set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
 947   return new_e;
 948 }
 949
 950
 951 /* This function verifies that the following restrictions apply to LOOP:
 952    (1) it is innermost
 953    (2) it consists of exactly 2 basic blocks - header, and an empty latch.
 954    (3) it is single entry, single exit
 955    (4) its exit condition is the last stmt in the header
 956    (5) E is the entry/exit edge of LOOP.
 957  */
 958
 959 bool
 960 slpeel_can_duplicate_loop_p (const struct loop *loop, const_edge e)
 961 {
 962   edge exit_e = single_exit (loop);
 963   edge entry_e = loop_preheader_edge (loop);
 964   tree orig_cond = get_loop_exit_condition (loop);
 965   block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
 966
 967   if (need_ssa_update_p ())
 968     return false;
 969
 970   if (loop->inner
 971       /* All loops have an outer scope; the only case loop->outer is NULL is for
 972          the function itself.  */
 973       || !loop_outer (loop)
 974       || loop->num_nodes != 2
 975       || !empty_block_p (loop->latch)
 976       || !single_exit (loop)
 977       /* Verify that new loop exit condition can be trivially modified.  */
 978       || (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
 979       || (e != exit_e && e != entry_e))
 980     return false;
 981
 982   return true;
 983 }
 984
 985 #ifdef ENABLE_CHECKING
 986 void
 987 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
 988                                  struct loop *second_loop)
 989 {
 990   basic_block loop1_exit_bb = single_exit (first_loop)->dest;
 991   basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
 992   basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
 993
 994   /* A guard that controls whether the second_loop is to be executed or skipped
 995      is placed in first_loop->exit.  first_loopt->exit therefore has two
 996      successors - one is the preheader of second_loop, and the other is a bb
 997      after second_loop.
 998    */
 999   gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
1000
1001   /* 1. Verify that one of the successors of first_loopt->exit is the preheader
1002         of second_loop.  */
1003
1004   /* The preheader of new_loop is expected to have two predecessors:
1005      first_loop->exit and the block that precedes first_loop.  */
1006
1007   gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
1008               && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
1009                    && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
1010                || (EDGE_PRED (loop2_entry_bb, 1)->src ==  loop1_exit_bb
1011                    && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
1012
1013   /* Verify that the other successor of first_loopt->exit is after the
1014      second_loop.  */
1015   /* TODO */
1016 }
1017 #endif
1018
1019 /* If the run time cost model check determines that vectorization is
1020    not profitable and hence scalar loop should be generated then set
1021    FIRST_NITERS to prologue peeled iterations. This will allow all the
1022    iterations to be executed in the prologue peeled scalar loop.  */
1023
1024 void
1025 set_prologue_iterations (basic_block bb_before_first_loop,
1026                          tree first_niters,
1027                          struct loop *loop,
1028                          unsigned int th)
1029 {
1030   edge e;
1031   basic_block cond_bb, then_bb;
1032   tree var, prologue_after_cost_adjust_name, stmt;
1033   block_stmt_iterator bsi;
1034   tree newphi;
1035   edge e_true, e_false, e_fallthru;
1036   tree cond_stmt;
1037   tree gimplify_stmt_list;
1038   tree cost_pre_condition = NULL_TREE;
1039   tree scalar_loop_iters =
1040     LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop));
1041
1042   e = single_pred_edge (bb_before_first_loop);
1043   cond_bb = split_edge(e);
1044
1045   e = single_pred_edge (bb_before_first_loop);
1046   then_bb = split_edge(e);
1047   set_immediate_dominator (CDI_DOMINATORS, then_bb, cond_bb);
1048
1049   e_false = make_single_succ_edge (cond_bb, bb_before_first_loop,
1050                                    EDGE_FALSE_VALUE);
1051   set_immediate_dominator (CDI_DOMINATORS, bb_before_first_loop, cond_bb);
1052
1053   e_true = EDGE_PRED (then_bb, 0);
1054   e_true->flags &= ~EDGE_FALLTHRU;
1055   e_true->flags |= EDGE_TRUE_VALUE;
1056
1057   e_fallthru = EDGE_SUCC (then_bb, 0);
1058
1059   cost_pre_condition =
1060     build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
1061             build_int_cst (TREE_TYPE (scalar_loop_iters), th));
1062   cost_pre_condition =
1063     force_gimple_operand (cost_pre_condition, &gimplify_stmt_list,
1064                           true, NULL_TREE);
1065   cond_stmt = build3 (COND_EXPR, void_type_node, cost_pre_condition,
1066                       NULL_TREE, NULL_TREE);
1067
1068   bsi = bsi_last (cond_bb);
1069   if (gimplify_stmt_list)
1070     bsi_insert_after (&bsi, gimplify_stmt_list, BSI_NEW_STMT);
1071
1072   bsi = bsi_last (cond_bb);
1073   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
1074
1075   var = create_tmp_var (TREE_TYPE (scalar_loop_iters),
1076                         "prologue_after_cost_adjust");
1077   add_referenced_var (var);
1078   prologue_after_cost_adjust_name =
1079     force_gimple_operand (scalar_loop_iters, &stmt, false, var);
1080
1081   bsi = bsi_last (then_bb);
1082   if (stmt)
1083     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
1084
1085   newphi = create_phi_node (var, bb_before_first_loop);
1086   add_phi_arg (newphi, prologue_after_cost_adjust_name, e_fallthru);
1087   add_phi_arg (newphi, first_niters, e_false);
1088
1089   first_niters = PHI_RESULT (newphi);
1090 }
1091
1092
1093 /* Function slpeel_tree_peel_loop_to_edge.
1094
1095    Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1096    that is placed on the entry (exit) edge E of LOOP. After this transformation
1097    we have two loops one after the other - first-loop iterates FIRST_NITERS
1098    times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1099    If the cost model indicates that it is profitable to emit a scalar
1100    loop instead of the vector one, then the prolog (epilog) loop will iterate
1101    for the entire unchanged scalar iterations of the loop.
1102
1103    Input:
1104    - LOOP: the loop to be peeled.
1105    - E: the exit or entry edge of LOOP.
1106         If it is the entry edge, we peel the first iterations of LOOP. In this
1107         case first-loop is LOOP, and second-loop is the newly created loop.
1108         If it is the exit edge, we peel the last iterations of LOOP. In this
1109         case, first-loop is the newly created loop, and second-loop is LOOP.
1110    - NITERS: the number of iterations that LOOP iterates.
1111    - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1112    - UPDATE_FIRST_LOOP_COUNT:  specified whether this function is responsible
1113         for updating the loop bound of the first-loop to FIRST_NITERS.  If it
1114         is false, the caller of this function may want to take care of this
1115         (this can be useful if we don't want new stmts added to first-loop).
1116    - TH: cost model profitability threshold of iterations for vectorization.
1117    - CHECK_PROFITABILITY: specify whether cost model check has not occured
1118                           during versioning and hence needs to occur during
1119                           prologue generation or whether cost model check
1120                           has not occured during prologue generation and hence
1121                           needs to occur during epilogue generation.
1122
1123
1124    Output:
1125    The function returns a pointer to the new loop-copy, or NULL if it failed
1126    to perform the transformation.
1127
1128    The function generates two if-then-else guards: one before the first loop,
1129    and the other before the second loop:
1130    The first guard is:
1131      if (FIRST_NITERS == 0) then skip the first loop,
1132      and go directly to the second loop.
1133    The second guard is:
1134      if (FIRST_NITERS == NITERS) then skip the second loop.
1135
1136    FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1137    FORNOW the resulting code will not be in loop-closed-ssa form.
1138 */
1139
1140 struct loop*
1141 slpeel_tree_peel_loop_to_edge (struct loop *loop,
1142                                edge e, tree first_niters,
1143                                tree niters, bool update_first_loop_count,
1144                                unsigned int th, bool check_profitability)
1145 {
1146   struct loop *new_loop = NULL, *first_loop, *second_loop;
1147   edge skip_e;
1148   tree pre_condition = NULL_TREE;
1149   bitmap definitions;
1150   basic_block bb_before_second_loop, bb_after_second_loop;
1151   basic_block bb_before_first_loop;
1152   basic_block bb_between_loops;
1153   basic_block new_exit_bb;
1154   edge exit_e = single_exit (loop);
1155   LOC loop_loc;
1156   tree cost_pre_condition = NULL_TREE;
1157   tree scalar_loop_iters =
1158     LOOP_VINFO_NITERS_UNCHANGED (loop_vec_info_for_loop (loop));
1159
1160   if (!slpeel_can_duplicate_loop_p (loop, e))
1161     return NULL;
1162
1163   /* We have to initialize cfg_hooks. Then, when calling
1164    cfg_hooks->split_edge, the function tree_split_edge
1165    is actually called and, when calling cfg_hooks->duplicate_block,
1166    the function tree_duplicate_bb is called.  */
1167   tree_register_cfg_hooks ();
1168
1169
1170   /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1171         Resulting CFG would be:
1172
1173         first_loop:
1174         do {
1175         } while ...
1176
1177         second_loop:
1178         do {
1179         } while ...
1180
1181         orig_exit_bb:
1182    */
1183
1184   if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e)))
1185     {
1186       loop_loc = find_loop_location (loop);
1187       if (dump_file && (dump_flags & TDF_DETAILS))
1188         {
1189           if (loop_loc != UNKNOWN_LOC)
1190             fprintf (dump_file, "\n%s:%d: note: ",
1191                      LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1192           fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
1193         }
1194       return NULL;
1195     }
1196
1197   if (e == exit_e)
1198     {
1199       /* NEW_LOOP was placed after LOOP.  */
1200       first_loop = loop;
1201       second_loop = new_loop;
1202     }
1203   else
1204     {
1205       /* NEW_LOOP was placed before LOOP.  */
1206       first_loop = new_loop;
1207       second_loop = loop;
1208     }
1209
1210   definitions = ssa_names_to_replace ();
1211   slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1212   rename_variables_in_loop (new_loop);
1213
1214
1215   /* 2.  Add the guard code in one of the following ways:
1216
1217      2.a Add the guard that controls whether the first loop is executed.
1218          This occurs when this function is invoked for prologue or epilogiue
1219          generation and when the cost model check can be done at compile time.
1220
1221          Resulting CFG would be:
1222
1223          bb_before_first_loop:
1224          if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1225                                 GOTO first-loop
1226
1227          first_loop:
1228          do {
1229          } while ...
1230
1231          bb_before_second_loop:
1232
1233          second_loop:
1234          do {
1235          } while ...
1236
1237          orig_exit_bb:
1238
1239      2.b Add the cost model check that allows the prologue
1240          to iterate for the entire unchanged scalar
1241          iterations of the loop in the event that the cost
1242          model indicates that the scalar loop is more
1243          profitable than the vector one. This occurs when
1244          this function is invoked for prologue generation
1245          and the cost model check needs to be done at run
1246          time.
1247
1248          Resulting CFG after prologue peeling would be:
1249
1250          if (scalar_loop_iterations <= th)
1251            FIRST_NITERS = scalar_loop_iterations
1252
1253          bb_before_first_loop:
1254          if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1255                                 GOTO first-loop
1256
1257          first_loop:
1258          do {
1259          } while ...
1260
1261          bb_before_second_loop:
1262
1263          second_loop:
1264          do {
1265          } while ...
1266
1267          orig_exit_bb:
1268
1269      2.c Add the cost model check that allows the epilogue
1270          to iterate for the entire unchanged scalar
1271          iterations of the loop in the event that the cost
1272          model indicates that the scalar loop is more
1273          profitable than the vector one. This occurs when
1274          this function is invoked for epilogue generation
1275          and the cost model check needs to be done at run
1276          time.
1277
1278          Resulting CFG after prologue peeling would be:
1279
1280          bb_before_first_loop:
1281          if ((scalar_loop_iterations <= th)
1282              ||
1283              FIRST_NITERS == 0) GOTO bb_before_second_loop
1284                                 GOTO first-loop
1285
1286          first_loop:
1287          do {
1288          } while ...
1289
1290          bb_before_second_loop:
1291
1292          second_loop:
1293          do {
1294          } while ...
1295
1296          orig_exit_bb:
1297   */
1298
1299   bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
1300   bb_before_second_loop = split_edge (single_exit (first_loop));
1301
1302   /* Epilogue peeling.  */
1303   if (!update_first_loop_count)
1304     {
1305       pre_condition =
1306         fold_build2 (LE_EXPR, boolean_type_node, first_niters,
1307                      build_int_cst (TREE_TYPE (first_niters), 0));
1308       if (check_profitability)
1309         {
1310             cost_pre_condition =
1311             build2 (LE_EXPR, boolean_type_node, scalar_loop_iters,
1312                     build_int_cst (TREE_TYPE (scalar_loop_iters), th));
1313
1314           pre_condition = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
1315                                        cost_pre_condition, pre_condition);
1316         }
1317     }
1318
1319   /* Prologue peeling.  */
1320   else
1321     {
1322       if (check_profitability)
1323         set_prologue_iterations (bb_before_first_loop, first_niters,
1324                                  loop, th);
1325
1326       pre_condition =
1327         fold_build2 (LE_EXPR, boolean_type_node, first_niters,
1328                      build_int_cst (TREE_TYPE (first_niters), 0));
1329     }
1330
1331   skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
1332                                   bb_before_second_loop, bb_before_first_loop);
1333   slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
1334                                       first_loop == new_loop,
1335                                       &new_exit_bb, &definitions);
1336
1337
1338   /* 3. Add the guard that controls whether the second loop is executed.
1339         Resulting CFG would be:
1340
1341         bb_before_first_loop:
1342         if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1343                                GOTO first-loop
1344
1345         first_loop:
1346         do {
1347         } while ...
1348
1349         bb_between_loops:
1350         if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1351                                     GOTO bb_before_second_loop
1352
1353         bb_before_second_loop:
1354
1355         second_loop:
1356         do {
1357         } while ...
1358
1359         bb_after_second_loop:
1360
1361         orig_exit_bb:
1362    */
1363
1364   bb_between_loops = new_exit_bb;
1365   bb_after_second_loop = split_edge (single_exit (second_loop));
1366
1367   pre_condition =
1368         fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
1369   skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
1370                                   bb_after_second_loop, bb_before_first_loop);
1371   slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
1372                                      second_loop == new_loop, &new_exit_bb);
1373
1374   /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1375    */
1376   if (update_first_loop_count)
1377     slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
1378
1379   BITMAP_FREE (definitions);
1380   delete_update_ssa ();
1381
1382   return new_loop;
1383 }
1384
1385 /* Function vect_get_loop_location.
1386
1387    Extract the location of the loop in the source code.
1388    If the loop is not well formed for vectorization, an estimated
1389    location is calculated.
1390    Return the loop location if succeed and NULL if not.  */
1391
1392 LOC
1393 find_loop_location (struct loop *loop)
1394 {
1395   tree node = NULL_TREE;
1396   basic_block bb;
1397   block_stmt_iterator si;
1398
1399   if (!loop)
1400     return UNKNOWN_LOC;
1401
1402   node = get_loop_exit_condition (loop);
1403
1404   if (node && CAN_HAVE_LOCATION_P (node) && EXPR_HAS_LOCATION (node)
1405       && EXPR_FILENAME (node) && EXPR_LINENO (node))
1406     return EXPR_LOC (node);
1407
1408   /* If we got here the loop is probably not "well formed",
1409      try to estimate the loop location */
1410
1411   if (!loop->header)
1412     return UNKNOWN_LOC;
1413
1414   bb = loop->header;
1415
1416   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1417     {
1418       node = bsi_stmt (si);
1419       if (node && CAN_HAVE_LOCATION_P (node) && EXPR_HAS_LOCATION (node))
1420         return EXPR_LOC (node);
1421     }
1422
1423   return UNKNOWN_LOC;
1424 }
1425
1426
1427 /*************************************************************************
1428   Vectorization Debug Information.
1429  *************************************************************************/
1430
1431 /* Function vect_set_verbosity_level.
1432
1433    Called from toplev.c upon detection of the
1434    -ftree-vectorizer-verbose=N option.  */
1435
1436 void
1437 vect_set_verbosity_level (const char *val)
1438 {
1439    unsigned int vl;
1440
1441    vl = atoi (val);
1442    if (vl < MAX_VERBOSITY_LEVEL)
1443      vect_verbosity_level = vl;
1444    else
1445      vect_verbosity_level = MAX_VERBOSITY_LEVEL - 1;
1446 }
1447
1448
1449 /* Function vect_set_dump_settings.
1450
1451    Fix the verbosity level of the vectorizer if the
1452    requested level was not set explicitly using the flag
1453    -ftree-vectorizer-verbose=N.
1454    Decide where to print the debugging information (dump_file/stderr).
1455    If the user defined the verbosity level, but there is no dump file,
1456    print to stderr, otherwise print to the dump file.  */
1457
1458 static void
1459 vect_set_dump_settings (void)
1460 {
1461   vect_dump = dump_file;
1462
1463   /* Check if the verbosity level was defined by the user:  */
1464   if (vect_verbosity_level != MAX_VERBOSITY_LEVEL)
1465     {
1466       /* If there is no dump file, print to stderr.  */
1467       if (!dump_file)
1468         vect_dump = stderr;
1469       return;
1470     }
1471
1472   /* User didn't specify verbosity level:  */
1473   if (dump_file && (dump_flags & TDF_DETAILS))
1474     vect_verbosity_level = REPORT_DETAILS;
1475   else if (dump_file && (dump_flags & TDF_STATS))
1476     vect_verbosity_level = REPORT_UNVECTORIZED_LOOPS;
1477   else
1478     vect_verbosity_level = REPORT_NONE;
1479
1480   gcc_assert (dump_file || vect_verbosity_level == REPORT_NONE);
1481 }
1482
1483
1484 /* Function debug_loop_details.
1485
1486    For vectorization debug dumps.  */
1487
1488 bool
1489 vect_print_dump_info (enum verbosity_levels vl)
1490 {
1491   if (vl > vect_verbosity_level)
1492     return false;
1493
1494   if (!current_function_decl || !vect_dump)
1495     return false;
1496
1497   if (vect_loop_location == UNKNOWN_LOC)
1498     fprintf (vect_dump, "\n%s:%d: note: ",
1499              DECL_SOURCE_FILE (current_function_decl),
1500              DECL_SOURCE_LINE (current_function_decl));
1501   else
1502     fprintf (vect_dump, "\n%s:%d: note: ",
1503              LOC_FILE (vect_loop_location), LOC_LINE (vect_loop_location));
1504
1505   return true;
1506 }
1507
1508
1509 /*************************************************************************
1510   Vectorization Utilities.
1511  *************************************************************************/
1512
1513 /* Function new_stmt_vec_info.
1514
1515    Create and initialize a new stmt_vec_info struct for STMT.  */
1516
1517 stmt_vec_info
1518 new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
1519 {
1520   stmt_vec_info res;
1521   res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
1522
1523   STMT_VINFO_TYPE (res) = undef_vec_info_type;
1524   STMT_VINFO_STMT (res) = stmt;
1525   STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
1526   STMT_VINFO_RELEVANT (res) = 0;
1527   STMT_VINFO_LIVE_P (res) = false;
1528   STMT_VINFO_VECTYPE (res) = NULL;
1529   STMT_VINFO_VEC_STMT (res) = NULL;
1530   STMT_VINFO_IN_PATTERN_P (res) = false;
1531   STMT_VINFO_RELATED_STMT (res) = NULL;
1532   STMT_VINFO_DATA_REF (res) = NULL;
1533
1534   STMT_VINFO_DR_BASE_ADDRESS (res) = NULL;
1535   STMT_VINFO_DR_OFFSET (res) = NULL;
1536   STMT_VINFO_DR_INIT (res) = NULL;
1537   STMT_VINFO_DR_STEP (res) = NULL;
1538   STMT_VINFO_DR_ALIGNED_TO (res) = NULL;
1539
1540   if (TREE_CODE (stmt) == PHI_NODE && is_loop_header_bb_p (bb_for_stmt (stmt)))
1541     STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
1542   else
1543     STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
1544   STMT_VINFO_SAME_ALIGN_REFS (res) = VEC_alloc (dr_p, heap, 5);
1545   STMT_VINFO_INSIDE_OF_LOOP_COST (res) = 0;
1546   STMT_VINFO_OUTSIDE_OF_LOOP_COST (res) = 0;
1547   STMT_SLP_TYPE (res) = 0;
1548   DR_GROUP_FIRST_DR (res) = NULL_TREE;
1549   DR_GROUP_NEXT_DR (res) = NULL_TREE;
1550   DR_GROUP_SIZE (res) = 0;
1551   DR_GROUP_STORE_COUNT (res) = 0;
1552   DR_GROUP_GAP (res) = 0;
1553   DR_GROUP_SAME_DR_STMT (res) = NULL_TREE;
1554   DR_GROUP_READ_WRITE_DEPENDENCE (res) = false;
1555
1556   return res;
1557 }
1558
1559
1560 /* Function bb_in_loop_p
1561
1562    Used as predicate for dfs order traversal of the loop bbs.  */
1563
1564 static bool
1565 bb_in_loop_p (const_basic_block bb, const void *data)
1566 {
1567   const struct loop *const loop = (const struct loop *)data;
1568   if (flow_bb_inside_loop_p (loop, bb))
1569     return true;
1570   return false;
1571 }
1572
1573
1574 /* Function new_loop_vec_info.
1575
1576    Create and initialize a new loop_vec_info struct for LOOP, as well as
1577    stmt_vec_info structs for all the stmts in LOOP.  */
1578
1579 loop_vec_info
1580 new_loop_vec_info (struct loop *loop)
1581 {
1582   loop_vec_info res;
1583   basic_block *bbs;
1584   block_stmt_iterator si;
1585   unsigned int i, nbbs;
1586
1587   res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
1588   LOOP_VINFO_LOOP (res) = loop;
1589
1590   bbs = get_loop_body (loop);
1591
1592   /* Create/Update stmt_info for all stmts in the loop.  */
1593   for (i = 0; i < loop->num_nodes; i++)
1594     {
1595       basic_block bb = bbs[i];
1596       tree phi;
1597
1598       /* BBs in a nested inner-loop will have been already processed (because
1599          we will have called vect_analyze_loop_form for any nested inner-loop).
1600          Therefore, for stmts in an inner-loop we just want to update the
1601          STMT_VINFO_LOOP_VINFO field of their stmt_info to point to the new
1602          loop_info of the outer-loop we are currently considering to vectorize
1603          (instead of the loop_info of the inner-loop).
1604          For stmts in other BBs we need to create a stmt_info from scratch.  */
1605       if (bb->loop_father != loop)
1606         {
1607           /* Inner-loop bb.  */
1608           gcc_assert (loop->inner && bb->loop_father == loop->inner);
1609           for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1610             {
1611               stmt_vec_info stmt_info = vinfo_for_stmt (phi);
1612               loop_vec_info inner_loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1613               gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
1614               STMT_VINFO_LOOP_VINFO (stmt_info) = res;
1615             }
1616           for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1617            {
1618               tree stmt = bsi_stmt (si);
1619               stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1620               loop_vec_info inner_loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1621               gcc_assert (loop->inner == LOOP_VINFO_LOOP (inner_loop_vinfo));
1622               STMT_VINFO_LOOP_VINFO (stmt_info) = res;
1623            }
1624         }
1625       else
1626         {
1627           /* bb in current nest.  */
1628           for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1629             {
1630               stmt_ann_t ann = get_stmt_ann (phi);
1631               set_stmt_info (ann, new_stmt_vec_info (phi, res));
1632             }
1633
1634           for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1635             {
1636               tree stmt = bsi_stmt (si);
1637               stmt_ann_t ann = stmt_ann (stmt);
1638               set_stmt_info (ann, new_stmt_vec_info (stmt, res));
1639             }
1640         }
1641     }
1642
1643   /* CHECKME: We want to visit all BBs before their successors (except for
1644      latch blocks, for which this assertion wouldn't hold).  In the simple
1645      case of the loop forms we allow, a dfs order of the BBs would the same
1646      as reversed postorder traversal, so we are safe.  */
1647
1648    free (bbs);
1649    bbs = XCNEWVEC (basic_block, loop->num_nodes);
1650    nbbs = dfs_enumerate_from (loop->header, 0, bb_in_loop_p,
1651                               bbs, loop->num_nodes, loop);
1652    gcc_assert (nbbs == loop->num_nodes);
1653
1654   LOOP_VINFO_BBS (res) = bbs;
1655   LOOP_VINFO_NITERS (res) = NULL;
1656   LOOP_VINFO_NITERS_UNCHANGED (res) = NULL;
1657   LOOP_VINFO_COST_MODEL_MIN_ITERS (res) = 0;
1658   LOOP_VINFO_VECTORIZABLE_P (res) = 0;
1659   LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
1660   LOOP_VINFO_VECT_FACTOR (res) = 0;
1661   LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
1662   LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
1663   LOOP_VINFO_UNALIGNED_DR (res) = NULL;
1664   LOOP_VINFO_MAY_MISALIGN_STMTS (res) =
1665     VEC_alloc (tree, heap, PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIGNMENT_CHECKS));
1666   LOOP_VINFO_MAY_ALIAS_DDRS (res) =
1667     VEC_alloc (ddr_p, heap, PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS));
1668   LOOP_VINFO_STRIDED_STORES (res) = VEC_alloc (tree, heap, 10);
1669   LOOP_VINFO_SLP_INSTANCES (res) = VEC_alloc (slp_instance, heap, 10);
1670   LOOP_VINFO_SLP_UNROLLING_FACTOR (res) = 1;
1671
1672   return res;
1673 }
1674
1675
1676 /* Function destroy_loop_vec_info.
1677
1678    Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
1679    stmts in the loop.  */
1680
1681 void
1682 destroy_loop_vec_info (loop_vec_info loop_vinfo, bool clean_stmts)
1683 {
1684   struct loop *loop;
1685   basic_block *bbs;
1686   int nbbs;
1687   block_stmt_iterator si;
1688   int j;
1689   VEC (slp_instance, heap) *slp_instances;
1690   slp_instance instance;
1691
1692   if (!loop_vinfo)
1693     return;
1694
1695   loop = LOOP_VINFO_LOOP (loop_vinfo);
1696
1697   bbs = LOOP_VINFO_BBS (loop_vinfo);
1698   nbbs = loop->num_nodes;
1699
1700   if (!clean_stmts)
1701     {
1702       free (LOOP_VINFO_BBS (loop_vinfo));
1703       free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
1704       free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
1705       VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
1706
1707       free (loop_vinfo);
1708       loop->aux = NULL;
1709       return;
1710     }
1711
1712   for (j = 0; j < nbbs; j++)
1713     {
1714       basic_block bb = bbs[j];
1715       tree phi;
1716       stmt_vec_info stmt_info;
1717
1718       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1719         {
1720           stmt_ann_t ann = stmt_ann (phi);
1721
1722           stmt_info = vinfo_for_stmt (phi);
1723           free (stmt_info);
1724           set_stmt_info (ann, NULL);
1725         }
1726
1727       for (si = bsi_start (bb); !bsi_end_p (si); )
1728         {
1729           tree stmt = bsi_stmt (si);
1730           stmt_ann_t ann = stmt_ann (stmt);
1731           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1732
1733           if (stmt_info)
1734             {
1735               /* Check if this is a "pattern stmt" (introduced by the
1736                  vectorizer during the pattern recognition pass).  */
1737               bool remove_stmt_p = false;
1738               tree orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1739               if (orig_stmt)
1740                 {
1741                   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
1742                   if (orig_stmt_info
1743                       && STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
1744                     remove_stmt_p = true;
1745                 }
1746
1747               /* Free stmt_vec_info.  */
1748               VEC_free (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmt_info));
1749               free (stmt_info);
1750               set_stmt_info (ann, NULL);
1751
1752               /* Remove dead "pattern stmts".  */
1753               if (remove_stmt_p)
1754                 bsi_remove (&si, true);
1755             }
1756           bsi_next (&si);
1757         }
1758     }
1759
1760   free (LOOP_VINFO_BBS (loop_vinfo));
1761   free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
1762   free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
1763   VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
1764   VEC_free (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo));
1765   slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo);
1766   for (j = 0; VEC_iterate (slp_instance, slp_instances, j, instance); j++)
1767     vect_free_slp_tree (SLP_INSTANCE_TREE (instance));
1768   VEC_free (slp_instance, heap, LOOP_VINFO_SLP_INSTANCES (loop_vinfo));
1769
1770   free (loop_vinfo);
1771   loop->aux = NULL;
1772 }
1773
1774
1775 /* Function vect_force_dr_alignment_p.
1776
1777    Returns whether the alignment of a DECL can be forced to be aligned
1778    on ALIGNMENT bit boundary.  */
1779
1780 bool
1781 vect_can_force_dr_alignment_p (const_tree decl, unsigned int alignment)
1782 {
1783   if (TREE_CODE (decl) != VAR_DECL)
1784     return false;
1785
1786   if (DECL_EXTERNAL (decl))
1787     return false;
1788
1789   if (TREE_ASM_WRITTEN (decl))
1790     return false;
1791
1792   if (TREE_STATIC (decl))
1793     return (alignment <= MAX_OFILE_ALIGNMENT);
1794   else
1795     /* This used to be PREFERRED_STACK_BOUNDARY, however, that is not 100%
1796        correct until someone implements forced stack alignment.  */
1797     return (alignment <= STACK_BOUNDARY);
1798 }
1799
1800
1801 /* Function get_vectype_for_scalar_type.
1802
1803    Returns the vector type corresponding to SCALAR_TYPE as supported
1804    by the target.  */
1805
1806 tree
1807 get_vectype_for_scalar_type (tree scalar_type)
1808 {
1809   enum machine_mode inner_mode = TYPE_MODE (scalar_type);
1810   int nbytes = GET_MODE_SIZE (inner_mode);
1811   int nunits;
1812   tree vectype;
1813
1814   if (nbytes == 0 || nbytes >= UNITS_PER_SIMD_WORD)
1815     return NULL_TREE;
1816
1817   /* FORNOW: Only a single vector size per target (UNITS_PER_SIMD_WORD)
1818      is expected.  */
1819   nunits = UNITS_PER_SIMD_WORD / nbytes;
1820
1821   vectype = build_vector_type (scalar_type, nunits);
1822   if (vect_print_dump_info (REPORT_DETAILS))
1823     {
1824       fprintf (vect_dump, "get vectype with %d units of type ", nunits);
1825       print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
1826     }
1827
1828   if (!vectype)
1829     return NULL_TREE;
1830
1831   if (vect_print_dump_info (REPORT_DETAILS))
1832     {
1833       fprintf (vect_dump, "vectype: ");
1834       print_generic_expr (vect_dump, vectype, TDF_SLIM);
1835     }
1836
1837   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
1838       && !INTEGRAL_MODE_P (TYPE_MODE (vectype)))
1839     {
1840       if (vect_print_dump_info (REPORT_DETAILS))
1841         fprintf (vect_dump, "mode not supported by target.");
1842       return NULL_TREE;
1843     }
1844
1845   return vectype;
1846 }
1847
1848
1849 /* Function vect_supportable_dr_alignment
1850
1851    Return whether the data reference DR is supported with respect to its
1852    alignment.  */
1853
1854 enum dr_alignment_support
1855 vect_supportable_dr_alignment (struct data_reference *dr)
1856 {
1857   tree stmt = DR_STMT (dr);
1858   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1859   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1860   enum machine_mode mode = (int) TYPE_MODE (vectype);
1861   struct loop *vect_loop = LOOP_VINFO_LOOP (STMT_VINFO_LOOP_VINFO (stmt_info));
1862   bool nested_in_vect_loop = nested_in_vect_loop_p (vect_loop, stmt);
1863   bool invariant_in_outerloop = false;
1864
1865   if (aligned_access_p (dr))
1866     return dr_aligned;
1867
1868   if (nested_in_vect_loop)
1869     {
1870       tree outerloop_step = STMT_VINFO_DR_STEP (stmt_info);
1871       invariant_in_outerloop =
1872         (tree_int_cst_compare (outerloop_step, size_zero_node) == 0);
1873     }
1874
1875   /* Possibly unaligned access.  */
1876
1877   /* We can choose between using the implicit realignment scheme (generating
1878      a misaligned_move stmt) and the explicit realignment scheme (generating
1879      aligned loads with a REALIGN_LOAD). There are two variants to the explicit
1880      realignment scheme: optimized, and unoptimized.
1881      We can optimize the realignment only if the step between consecutive
1882      vector loads is equal to the vector size.  Since the vector memory
1883      accesses advance in steps of VS (Vector Size) in the vectorized loop, it
1884      is guaranteed that the misalignment amount remains the same throughout the
1885      execution of the vectorized loop.  Therefore, we can create the
1886      "realignment token" (the permutation mask that is passed to REALIGN_LOAD)
1887      at the loop preheader.
1888
1889      However, in the case of outer-loop vectorization, when vectorizing a
1890      memory access in the inner-loop nested within the LOOP that is now being
1891      vectorized, while it is guaranteed that the misalignment of the
1892      vectorized memory access will remain the same in different outer-loop
1893      iterations, it is *not* guaranteed that is will remain the same throughout
1894      the execution of the inner-loop.  This is because the inner-loop advances
1895      with the original scalar step (and not in steps of VS).  If the inner-loop
1896      step happens to be a multiple of VS, then the misalignment remains fixed
1897      and we can use the optimized realignment scheme.  For example:
1898
1899       for (i=0; i<N; i++)
1900         for (j=0; j<M; j++)
1901           s += a[i+j];
1902
1903      When vectorizing the i-loop in the above example, the step between
1904      consecutive vector loads is 1, and so the misalignment does not remain
1905      fixed across the execution of the inner-loop, and the realignment cannot
1906      be optimized (as illustrated in the following pseudo vectorized loop):
1907
1908       for (i=0; i<N; i+=4)
1909         for (j=0; j<M; j++){
1910           vs += vp[i+j]; // misalignment of &vp[i+j] is {0,1,2,3,0,1,2,3,...}
1911                          // when j is {0,1,2,3,4,5,6,7,...} respectively.
1912                          // (assuming that we start from an aligned address).
1913           }
1914
1915      We therefore have to use the unoptimized realignment scheme:
1916
1917       for (i=0; i<N; i+=4)
1918           for (j=k; j<M; j+=4)
1919           vs += vp[i+j]; // misalignment of &vp[i+j] is always k (assuming
1920                            // that the misalignment of the initial address is
1921                            // 0).
1922
1923      The loop can then be vectorized as follows:
1924
1925       for (k=0; k<4; k++){
1926         rt = get_realignment_token (&vp[k]);
1927         for (i=0; i<N; i+=4){
1928           v1 = vp[i+k];
1929           for (j=k; j<M; j+=4){
1930             v2 = vp[i+j+VS-1];
1931             va = REALIGN_LOAD <v1,v2,rt>;
1932             vs += va;
1933             v1 = v2;
1934           }
1935         }
1936     } */
1937
1938   if (DR_IS_READ (dr))
1939     {
1940       if (optab_handler (vec_realign_load_optab, mode)->insn_code !=
1941                                                              CODE_FOR_nothing
1942           && (!targetm.vectorize.builtin_mask_for_load
1943               || targetm.vectorize.builtin_mask_for_load ()))
1944         {
1945             if (nested_in_vect_loop
1946                 && TREE_INT_CST_LOW (DR_STEP (dr)) != UNITS_PER_SIMD_WORD)
1947               return dr_explicit_realign;
1948             else
1949               return dr_explicit_realign_optimized;
1950         }
1951
1952       if (optab_handler (movmisalign_optab, mode)->insn_code !=
1953                                                              CODE_FOR_nothing)
1954         /* Can't software pipeline the loads, but can at least do them.  */
1955         return dr_unaligned_supported;
1956     }
1957
1958   /* Unsupported.  */
1959   return dr_unaligned_unsupported;
1960 }
1961
1962
1963 /* Function vect_is_simple_use.
1964
1965    Input:
1966    LOOP - the loop that is being vectorized.
1967    OPERAND - operand of a stmt in LOOP.
1968    DEF - the defining stmt in case OPERAND is an SSA_NAME.
1969
1970    Returns whether a stmt with OPERAND can be vectorized.
1971    Supportable operands are constants, loop invariants, and operands that are
1972    defined by the current iteration of the loop. Unsupportable operands are
1973    those that are defined by a previous iteration of the loop (as is the case
1974    in reduction/induction computations).  */
1975
1976 bool
1977 vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
1978                     tree *def, enum vect_def_type *dt)
1979 {
1980   basic_block bb;
1981   stmt_vec_info stmt_vinfo;
1982   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1983
1984   *def_stmt = NULL_TREE;
1985   *def = NULL_TREE;
1986
1987   if (vect_print_dump_info (REPORT_DETAILS))
1988     {
1989       fprintf (vect_dump, "vect_is_simple_use: operand ");
1990       print_generic_expr (vect_dump, operand, TDF_SLIM);
1991     }
1992
1993   if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
1994     {
1995       *dt = vect_constant_def;
1996       return true;
1997     }
1998   if (is_gimple_min_invariant (operand))
1999    {
2000       *def = operand;
2001       *dt = vect_invariant_def;
2002       return true;
2003    }
2004
2005   if (TREE_CODE (operand) != SSA_NAME)
2006     {
2007       if (vect_print_dump_info (REPORT_DETAILS))
2008         fprintf (vect_dump, "not ssa-name.");
2009       return false;
2010     }
2011
2012   *def_stmt = SSA_NAME_DEF_STMT (operand);
2013   if (*def_stmt == NULL_TREE )
2014     {
2015       if (vect_print_dump_info (REPORT_DETAILS))
2016         fprintf (vect_dump, "no def_stmt.");
2017       return false;
2018     }
2019
2020   if (vect_print_dump_info (REPORT_DETAILS))
2021     {
2022       fprintf (vect_dump, "def_stmt: ");
2023       print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
2024     }
2025
2026   /* empty stmt is expected only in case of a function argument.
2027      (Otherwise - we expect a phi_node or a GIMPLE_MODIFY_STMT).  */
2028   if (IS_EMPTY_STMT (*def_stmt))
2029     {
2030       tree arg = TREE_OPERAND (*def_stmt, 0);
2031       if (is_gimple_min_invariant (arg))
2032         {
2033           *def = operand;
2034           *dt = vect_invariant_def;
2035           return true;
2036         }
2037
2038       if (vect_print_dump_info (REPORT_DETAILS))
2039         fprintf (vect_dump, "Unexpected empty stmt.");
2040       return false;
2041     }
2042
2043   bb = bb_for_stmt (*def_stmt);
2044   if (!flow_bb_inside_loop_p (loop, bb))
2045     *dt = vect_invariant_def;
2046   else
2047     {
2048       stmt_vinfo = vinfo_for_stmt (*def_stmt);
2049       *dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
2050     }
2051
2052   if (*dt == vect_unknown_def_type)
2053     {
2054       if (vect_print_dump_info (REPORT_DETAILS))
2055         fprintf (vect_dump, "Unsupported pattern.");
2056       return false;
2057     }
2058
2059   if (vect_print_dump_info (REPORT_DETAILS))
2060     fprintf (vect_dump, "type of def: %d.",*dt);
2061
2062   switch (TREE_CODE (*def_stmt))
2063     {
2064     case PHI_NODE:
2065       *def = PHI_RESULT (*def_stmt);
2066       break;
2067
2068     case GIMPLE_MODIFY_STMT:
2069       *def = GIMPLE_STMT_OPERAND (*def_stmt, 0);
2070       break;
2071
2072     default:
2073       if (vect_print_dump_info (REPORT_DETAILS))
2074         fprintf (vect_dump, "unsupported defining stmt: ");
2075       return false;
2076     }
2077
2078   return true;
2079 }
2080
2081
2082 /* Function supportable_widening_operation
2083
2084    Check whether an operation represented by the code CODE is a
2085    widening operation that is supported by the target platform in
2086    vector form (i.e., when operating on arguments of type VECTYPE).
2087
2088    Widening operations we currently support are NOP (CONVERT), FLOAT
2089    and WIDEN_MULT.  This function checks if these operations are supported
2090    by the target platform either directly (via vector tree-codes), or via
2091    target builtins.
2092
2093    Output:
2094    - CODE1 and CODE2 are codes of vector operations to be used when
2095    vectorizing the operation, if available.
2096    - DECL1 and DECL2 are decls of target builtin functions to be used
2097    when vectorizing the operation, if available. In this case,
2098    CODE1 and CODE2 are CALL_EXPR.  */
2099
2100 bool
2101 supportable_widening_operation (enum tree_code code, tree stmt, tree vectype,
2102                                 tree *decl1, tree *decl2,
2103                                 enum tree_code *code1, enum tree_code *code2)
2104 {
2105   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2106   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_info);
2107   struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
2108   bool ordered_p;
2109   enum machine_mode vec_mode;
2110   enum insn_code icode1, icode2;
2111   optab optab1, optab2;
2112   tree expr = GIMPLE_STMT_OPERAND (stmt, 1);
2113   tree type = TREE_TYPE (expr);
2114   tree wide_vectype = get_vectype_for_scalar_type (type);
2115   enum tree_code c1, c2;
2116
2117   /* The result of a vectorized widening operation usually requires two vectors
2118      (because the widened results do not fit int one vector). The generated
2119      vector results would normally be expected to be generated in the same
2120      order as in the original scalar computation. i.e. if 8 results are
2121      generated in each vector iteration, they are to be organized as follows:
2122         vect1: [res1,res2,res3,res4], vect2: [res5,res6,res7,res8].
2123
2124      However, in the special case that the result of the widening operation is
2125      used in a reduction computation only, the order doesn't matter (because
2126      when vectorizing a reduction we change the order of the computation).
2127      Some targets can take advantage of this and generate more efficient code.
2128      For example, targets like Altivec, that support widen_mult using a sequence
2129      of {mult_even,mult_odd} generate the following vectors:
2130         vect1: [res1,res3,res5,res7], vect2: [res2,res4,res6,res8].
2131
2132      When vectorizaing outer-loops, we execute the inner-loop sequentially
2133      (each vectorized inner-loop iteration contributes to VF outer-loop
2134      iterations in parallel). We therefore don't allow to change the order
2135      of the computation in the inner-loop during outer-loop vectorization.  */
2136
2137    if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction
2138        && !nested_in_vect_loop_p (vect_loop, stmt))
2139      ordered_p = false;
2140    else
2141      ordered_p = true;
2142
2143   if (!ordered_p
2144       && code == WIDEN_MULT_EXPR
2145       && targetm.vectorize.builtin_mul_widen_even
2146       && targetm.vectorize.builtin_mul_widen_even (vectype)
2147       && targetm.vectorize.builtin_mul_widen_odd
2148       && targetm.vectorize.builtin_mul_widen_odd (vectype))
2149     {
2150       if (vect_print_dump_info (REPORT_DETAILS))
2151         fprintf (vect_dump, "Unordered widening operation detected.");
2152
2153       *code1 = *code2 = CALL_EXPR;
2154       *decl1 = targetm.vectorize.builtin_mul_widen_even (vectype);
2155       *decl2 = targetm.vectorize.builtin_mul_widen_odd (vectype);
2156       return true;
2157     }
2158
2159   switch (code)
2160     {
2161     case WIDEN_MULT_EXPR:
2162       if (BYTES_BIG_ENDIAN)
2163         {
2164           c1 = VEC_WIDEN_MULT_HI_EXPR;
2165           c2 = VEC_WIDEN_MULT_LO_EXPR;
2166         }
2167       else
2168         {
2169           c2 = VEC_WIDEN_MULT_HI_EXPR;
2170           c1 = VEC_WIDEN_MULT_LO_EXPR;
2171         }
2172       break;
2173
2174     case NOP_EXPR:
2175     case CONVERT_EXPR:
2176       if (BYTES_BIG_ENDIAN)
2177         {
2178           c1 = VEC_UNPACK_HI_EXPR;
2179           c2 = VEC_UNPACK_LO_EXPR;
2180         }
2181       else
2182         {
2183           c2 = VEC_UNPACK_HI_EXPR;
2184           c1 = VEC_UNPACK_LO_EXPR;
2185         }
2186       break;
2187
2188     case FLOAT_EXPR:
2189       if (BYTES_BIG_ENDIAN)
2190         {
2191           c1 = VEC_UNPACK_FLOAT_HI_EXPR;
2192           c2 = VEC_UNPACK_FLOAT_LO_EXPR;
2193         }
2194       else
2195         {
2196           c2 = VEC_UNPACK_FLOAT_HI_EXPR;
2197           c1 = VEC_UNPACK_FLOAT_LO_EXPR;
2198         }
2199       break;
2200
2201     case FIX_TRUNC_EXPR:
2202       /* ??? Not yet implemented due to missing VEC_UNPACK_FIX_TRUNC_HI_EXPR/
2203          VEC_UNPACK_FIX_TRUNC_LO_EXPR tree codes and optabs used for
2204          computing the operation.  */
2205       return false;
2206
2207     default:
2208       gcc_unreachable ();
2209     }
2210
2211   if (code == FIX_TRUNC_EXPR)
2212     {
2213       /* The signedness is determined from output operand.  */
2214       optab1 = optab_for_tree_code (c1, type);
2215       optab2 = optab_for_tree_code (c2, type);
2216     }
2217   else
2218     {
2219       optab1 = optab_for_tree_code (c1, vectype);
2220       optab2 = optab_for_tree_code (c2, vectype);
2221     }
2222
2223   if (!optab1 || !optab2)
2224     return false;
2225
2226   vec_mode = TYPE_MODE (vectype);
2227   if ((icode1 = optab_handler (optab1, vec_mode)->insn_code) == CODE_FOR_nothing
2228       || insn_data[icode1].operand[0].mode != TYPE_MODE (wide_vectype)
2229       || (icode2 = optab_handler (optab2, vec_mode)->insn_code)
2230                                                         == CODE_FOR_nothing
2231       || insn_data[icode2].operand[0].mode != TYPE_MODE (wide_vectype))
2232     return false;
2233
2234   *code1 = c1;
2235   *code2 = c2;
2236   return true;
2237 }
2238
2239
2240 /* Function supportable_narrowing_operation
2241
2242    Check whether an operation represented by the code CODE is a
2243    narrowing operation that is supported by the target platform in
2244    vector form (i.e., when operating on arguments of type VECTYPE).
2245
2246    Narrowing operations we currently support are NOP (CONVERT) and
2247    FIX_TRUNC. This function checks if these operations are supported by
2248    the target platform directly via vector tree-codes.
2249
2250    Output:
2251    - CODE1 is the code of a vector operation to be used when
2252    vectorizing the operation, if available.  */
2253
2254 bool
2255 supportable_narrowing_operation (enum tree_code code,
2256                                  const_tree stmt, const_tree vectype,
2257                                  enum tree_code *code1)
2258 {
2259   enum machine_mode vec_mode;
2260   enum insn_code icode1;
2261   optab optab1;
2262   tree expr = GIMPLE_STMT_OPERAND (stmt, 1);
2263   tree type = TREE_TYPE (expr);
2264   tree narrow_vectype = get_vectype_for_scalar_type (type);
2265   enum tree_code c1;
2266
2267   switch (code)
2268     {
2269     case NOP_EXPR:
2270     case CONVERT_EXPR:
2271       c1 = VEC_PACK_TRUNC_EXPR;
2272       break;
2273
2274     case FIX_TRUNC_EXPR:
2275       c1 = VEC_PACK_FIX_TRUNC_EXPR;
2276       break;
2277
2278     case FLOAT_EXPR:
2279       /* ??? Not yet implemented due to missing VEC_PACK_FLOAT_EXPR
2280          tree code and optabs used for computing the operation.  */
2281       return false;
2282
2283     default:
2284       gcc_unreachable ();
2285     }
2286
2287   if (code == FIX_TRUNC_EXPR)
2288     /* The signedness is determined from output operand.  */
2289     optab1 = optab_for_tree_code (c1, type);
2290   else
2291     optab1 = optab_for_tree_code (c1, vectype);
2292
2293   if (!optab1)
2294     return false;
2295
2296   vec_mode = TYPE_MODE (vectype);
2297   if ((icode1 = optab_handler (optab1, vec_mode)->insn_code) == CODE_FOR_nothing
2298       || insn_data[icode1].operand[0].mode != TYPE_MODE (narrow_vectype))
2299     return false;
2300
2301   *code1 = c1;
2302   return true;
2303 }
2304
2305
2306 /* Function reduction_code_for_scalar_code
2307
2308    Input:
2309    CODE - tree_code of a reduction operations.
2310
2311    Output:
2312    REDUC_CODE - the corresponding tree-code to be used to reduce the
2313       vector of partial results into a single scalar result (which
2314       will also reside in a vector).
2315
2316    Return TRUE if a corresponding REDUC_CODE was found, FALSE otherwise.  */
2317
2318 bool
2319 reduction_code_for_scalar_code (enum tree_code code,
2320                                 enum tree_code *reduc_code)
2321 {
2322   switch (code)
2323   {
2324   case MAX_EXPR:
2325     *reduc_code = REDUC_MAX_EXPR;
2326     return true;
2327
2328   case MIN_EXPR:
2329     *reduc_code = REDUC_MIN_EXPR;
2330     return true;
2331
2332   case PLUS_EXPR:
2333     *reduc_code = REDUC_PLUS_EXPR;
2334     return true;
2335
2336   default:
2337     return false;
2338   }
2339 }
2340
2341
2342 /* Function vect_is_simple_reduction
2343
2344    Detect a cross-iteration def-use cucle that represents a simple
2345    reduction computation. We look for the following pattern:
2346
2347    loop_header:
2348      a1 = phi < a0, a2 >
2349      a3 = ...
2350      a2 = operation (a3, a1)
2351
2352    such that:
2353    1. operation is commutative and associative and it is safe to
2354       change the order of the computation.
2355    2. no uses for a2 in the loop (a2 is used out of the loop)
2356    3. no uses of a1 in the loop besides the reduction operation.
2357
2358    Condition 1 is tested here.
2359    Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.  */
2360
2361 tree
2362 vect_is_simple_reduction (loop_vec_info loop_info, tree phi)
2363 {
2364   struct loop *loop = (bb_for_stmt (phi))->loop_father;
2365   struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
2366   edge latch_e = loop_latch_edge (loop);
2367   tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
2368   tree def_stmt, def1, def2;
2369   enum tree_code code;
2370   int op_type;
2371   tree operation, op1, op2;
2372   tree type;
2373   int nloop_uses;
2374   tree name;
2375   imm_use_iterator imm_iter;
2376   use_operand_p use_p;
2377
2378   gcc_assert (loop == vect_loop || flow_loop_nested_p (vect_loop, loop));
2379
2380   name = PHI_RESULT (phi);
2381   nloop_uses = 0;
2382   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2383     {
2384       tree use_stmt = USE_STMT (use_p);
2385       if (flow_bb_inside_loop_p (loop, bb_for_stmt (use_stmt))
2386           && vinfo_for_stmt (use_stmt)
2387           && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
2388         nloop_uses++;
2389       if (nloop_uses > 1)
2390         {
2391           if (vect_print_dump_info (REPORT_DETAILS))
2392             fprintf (vect_dump, "reduction used in loop.");
2393           return NULL_TREE;
2394         }
2395     }
2396
2397   if (TREE_CODE (loop_arg) != SSA_NAME)
2398     {
2399       if (vect_print_dump_info (REPORT_DETAILS))
2400         {
2401           fprintf (vect_dump, "reduction: not ssa_name: ");
2402           print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
2403         }
2404       return NULL_TREE;
2405     }
2406
2407   def_stmt = SSA_NAME_DEF_STMT (loop_arg);
2408   if (!def_stmt)
2409     {
2410       if (vect_print_dump_info (REPORT_DETAILS))
2411         fprintf (vect_dump, "reduction: no def_stmt.");
2412       return NULL_TREE;
2413     }
2414
2415   if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
2416     {
2417       if (vect_print_dump_info (REPORT_DETAILS))
2418         print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
2419       return NULL_TREE;
2420     }
2421
2422   name = GIMPLE_STMT_OPERAND (def_stmt, 0);
2423   nloop_uses = 0;
2424   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
2425     {
2426       tree use_stmt = USE_STMT (use_p);
2427       if (flow_bb_inside_loop_p (loop, bb_for_stmt (use_stmt))
2428           && vinfo_for_stmt (use_stmt)
2429           && !is_pattern_stmt_p (vinfo_for_stmt (use_stmt)))
2430         nloop_uses++;
2431       if (nloop_uses > 1)
2432         {
2433           if (vect_print_dump_info (REPORT_DETAILS))
2434             fprintf (vect_dump, "reduction used in loop.");
2435           return NULL_TREE;
2436         }
2437     }
2438
2439   operation = GIMPLE_STMT_OPERAND (def_stmt, 1);
2440   code = TREE_CODE (operation);
2441   if (!commutative_tree_code (code) || !associative_tree_code (code))
2442     {
2443       if (vect_print_dump_info (REPORT_DETAILS))
2444         {
2445           fprintf (vect_dump, "reduction: not commutative/associative: ");
2446           print_generic_expr (vect_dump, operation, TDF_SLIM);
2447         }
2448       return NULL_TREE;
2449     }
2450
2451   op_type = TREE_OPERAND_LENGTH (operation);
2452   if (op_type != binary_op)
2453     {
2454       if (vect_print_dump_info (REPORT_DETAILS))
2455         {
2456           fprintf (vect_dump, "reduction: not binary operation: ");
2457           print_generic_expr (vect_dump, operation, TDF_SLIM);
2458         }
2459       return NULL_TREE;
2460     }
2461
2462   op1 = TREE_OPERAND (operation, 0);
2463   op2 = TREE_OPERAND (operation, 1);
2464   if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
2465     {
2466       if (vect_print_dump_info (REPORT_DETAILS))
2467         {
2468           fprintf (vect_dump, "reduction: uses not ssa_names: ");
2469           print_generic_expr (vect_dump, operation, TDF_SLIM);
2470         }
2471       return NULL_TREE;
2472     }
2473
2474   /* Check that it's ok to change the order of the computation.  */
2475   type = TREE_TYPE (operation);
2476   if (TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op1))
2477       || TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op2)))
2478     {
2479       if (vect_print_dump_info (REPORT_DETAILS))
2480         {
2481           fprintf (vect_dump, "reduction: multiple types: operation type: ");
2482           print_generic_expr (vect_dump, type, TDF_SLIM);
2483           fprintf (vect_dump, ", operands types: ");
2484           print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
2485           fprintf (vect_dump, ",");
2486           print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
2487         }
2488       return NULL_TREE;
2489     }
2490
2491   /* Generally, when vectorizing a reduction we change the order of the
2492      computation.  This may change the behavior of the program in some
2493      cases, so we need to check that this is ok.  One exception is when
2494      vectorizing an outer-loop: the inner-loop is executed sequentially,
2495      and therefore vectorizing reductions in the inner-loop durint
2496      outer-loop vectorization is safe.  */
2497
2498   /* CHECKME: check for !flag_finite_math_only too?  */
2499   if (SCALAR_FLOAT_TYPE_P (type) && !flag_associative_math
2500       && !nested_in_vect_loop_p (vect_loop, def_stmt))
2501     {
2502       /* Changing the order of operations changes the semantics.  */
2503       if (vect_print_dump_info (REPORT_DETAILS))
2504         {
2505           fprintf (vect_dump, "reduction: unsafe fp math optimization: ");
2506           print_generic_expr (vect_dump, operation, TDF_SLIM);
2507         }
2508       return NULL_TREE;
2509     }
2510   else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type)
2511            && !nested_in_vect_loop_p (vect_loop, def_stmt))
2512     {
2513       /* Changing the order of operations changes the semantics.  */
2514       if (vect_print_dump_info (REPORT_DETAILS))
2515         {
2516           fprintf (vect_dump, "reduction: unsafe int math optimization: ");
2517           print_generic_expr (vect_dump, operation, TDF_SLIM);
2518         }
2519       return NULL_TREE;
2520     }
2521   else if (SAT_FIXED_POINT_TYPE_P (type))
2522     {
2523       /* Changing the order of operations changes the semantics.  */
2524       if (vect_print_dump_info (REPORT_DETAILS))
2525         {
2526           fprintf (vect_dump, "reduction: unsafe fixed-point math optimization: ");
2527           print_generic_expr (vect_dump, operation, TDF_SLIM);
2528         }
2529       return NULL_TREE;
2530     }
2531
2532   /* reduction is safe. we're dealing with one of the following:
2533      1) integer arithmetic and no trapv
2534      2) floating point arithmetic, and special flags permit this optimization.
2535    */
2536   def1 = SSA_NAME_DEF_STMT (op1);
2537   def2 = SSA_NAME_DEF_STMT (op2);
2538   if (!def1 || !def2 || IS_EMPTY_STMT (def1) || IS_EMPTY_STMT (def2))
2539     {
2540       if (vect_print_dump_info (REPORT_DETAILS))
2541         {
2542           fprintf (vect_dump, "reduction: no defs for operands: ");
2543           print_generic_expr (vect_dump, operation, TDF_SLIM);
2544         }
2545       return NULL_TREE;
2546     }
2547
2548
2549   /* Check that one def is the reduction def, defined by PHI,
2550      the other def is either defined in the loop ("vect_loop_def"),
2551      or it's an induction (defined by a loop-header phi-node).  */
2552
2553   if (def2 == phi
2554       && flow_bb_inside_loop_p (loop, bb_for_stmt (def1))
2555       && (TREE_CODE (def1) == GIMPLE_MODIFY_STMT
2556           || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1)) == vect_induction_def
2557           || (TREE_CODE (def1) == PHI_NODE
2558               && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def1)) == vect_loop_def
2559               && !is_loop_header_bb_p (bb_for_stmt (def1)))))
2560     {
2561       if (vect_print_dump_info (REPORT_DETAILS))
2562         {
2563           fprintf (vect_dump, "detected reduction:");
2564           print_generic_expr (vect_dump, operation, TDF_SLIM);
2565         }
2566       return def_stmt;
2567     }
2568   else if (def1 == phi
2569            && flow_bb_inside_loop_p (loop, bb_for_stmt (def2))
2570            && (TREE_CODE (def2) == GIMPLE_MODIFY_STMT
2571                || STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2)) == vect_induction_def
2572                || (TREE_CODE (def2) == PHI_NODE
2573                    && STMT_VINFO_DEF_TYPE (vinfo_for_stmt (def2)) == vect_loop_def
2574                    && !is_loop_header_bb_p (bb_for_stmt (def2)))))
2575     {
2576       /* Swap operands (just for simplicity - so that the rest of the code
2577          can assume that the reduction variable is always the last (second)
2578          argument).  */
2579       if (vect_print_dump_info (REPORT_DETAILS))
2580         {
2581           fprintf (vect_dump, "detected reduction: need to swap operands:");
2582           print_generic_expr (vect_dump, operation, TDF_SLIM);
2583         }
2584       swap_tree_operands (def_stmt, &TREE_OPERAND (operation, 0),
2585                                     &TREE_OPERAND (operation, 1));
2586       return def_stmt;
2587     }
2588   else
2589     {
2590       if (vect_print_dump_info (REPORT_DETAILS))
2591         {
2592           fprintf (vect_dump, "reduction: unknown pattern.");
2593           print_generic_expr (vect_dump, operation, TDF_SLIM);
2594         }
2595       return NULL_TREE;
2596     }
2597 }
2598
2599
2600 /* Function vect_is_simple_iv_evolution.
2601
2602    FORNOW: A simple evolution of an induction variables in the loop is
2603    considered a polynomial evolution with constant step.  */
2604
2605 bool
2606 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
2607                              tree * step)
2608 {
2609   tree init_expr;
2610   tree step_expr;
2611   tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
2612
2613   /* When there is no evolution in this loop, the evolution function
2614      is not "simple".  */
2615   if (evolution_part == NULL_TREE)
2616     return false;
2617
2618   /* When the evolution is a polynomial of degree >= 2
2619      the evolution function is not "simple".  */
2620   if (tree_is_chrec (evolution_part))
2621     return false;
2622
2623   step_expr = evolution_part;
2624   init_expr = unshare_expr (initial_condition_in_loop_num (access_fn, loop_nb));
2625
2626   if (vect_print_dump_info (REPORT_DETAILS))
2627     {
2628       fprintf (vect_dump, "step: ");
2629       print_generic_expr (vect_dump, step_expr, TDF_SLIM);
2630       fprintf (vect_dump, ",  init: ");
2631       print_generic_expr (vect_dump, init_expr, TDF_SLIM);
2632     }
2633
2634   *init = init_expr;
2635   *step = step_expr;
2636
2637   if (TREE_CODE (step_expr) != INTEGER_CST)
2638     {
2639       if (vect_print_dump_info (REPORT_DETAILS))
2640         fprintf (vect_dump, "step unknown.");
2641       return false;
2642     }
2643
2644   return true;
2645 }
2646
2647
2648 /* Function vectorize_loops.
2649
2650    Entry Point to loop vectorization phase.  */
2651
2652 unsigned
2653 vectorize_loops (void)
2654 {
2655   unsigned int i;
2656   unsigned int num_vectorized_loops = 0;
2657   unsigned int vect_loops_num;
2658   loop_iterator li;
2659   struct loop *loop;
2660
2661   vect_loops_num = number_of_loops ();
2662
2663   /* Bail out if there are no loops.  */
2664   if (vect_loops_num <= 1)
2665     return 0;
2666
2667   /* Fix the verbosity level if not defined explicitly by the user.  */
2668   vect_set_dump_settings ();
2669
2670   /* Allocate the bitmap that records which virtual variables that
2671      need to be renamed.  */
2672   vect_memsyms_to_rename = BITMAP_ALLOC (NULL);
2673
2674   /*  ----------- Analyze loops. -----------  */
2675
2676   /* If some loop was duplicated, it gets bigger number
2677      than all previously defined loops. This fact allows us to run
2678      only over initial loops skipping newly generated ones.  */
2679   FOR_EACH_LOOP (li, loop, 0)
2680     {
2681       loop_vec_info loop_vinfo;
2682
2683       vect_loop_location = find_loop_location (loop);
2684       loop_vinfo = vect_analyze_loop (loop);
2685       loop->aux = loop_vinfo;
2686
2687       if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
2688         continue;
2689
2690       vect_transform_loop (loop_vinfo);
2691       num_vectorized_loops++;
2692     }
2693   vect_loop_location = UNKNOWN_LOC;
2694
2695   if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS)
2696       || (vect_print_dump_info (REPORT_VECTORIZED_LOOPS)
2697           && num_vectorized_loops > 0))
2698     fprintf (vect_dump, "vectorized %u loops in function.\n",
2699              num_vectorized_loops);
2700
2701   /*  ----------- Finalize. -----------  */
2702
2703   BITMAP_FREE (vect_memsyms_to_rename);
2704
2705   for (i = 1; i < vect_loops_num; i++)
2706     {
2707       loop_vec_info loop_vinfo;
2708
2709       loop = get_loop (i);
2710       if (!loop)
2711         continue;
2712       loop_vinfo = loop->aux;
2713       destroy_loop_vec_info (loop_vinfo, true);
2714       loop->aux = NULL;
2715     }
2716
2717   return num_vectorized_loops > 0 ? TODO_cleanup_cfg : 0;
2718 }
2719
2720 /* Increase alignment of global arrays to improve vectorization potential.
2721    TODO:
2722    - Consider also structs that have an array field.
2723    - Use ipa analysis to prune arrays that can't be vectorized?
2724      This should involve global alignment analysis and in the future also
2725      array padding.  */
2726
2727 static unsigned int
2728 increase_alignment (void)
2729 {
2730   struct varpool_node *vnode;
2731
2732   /* Increase the alignment of all global arrays for vectorization.  */
2733   for (vnode = varpool_nodes_queue;
2734        vnode;
2735        vnode = vnode->next_needed)
2736     {
2737       tree vectype, decl = vnode->decl;
2738       unsigned int alignment;
2739
2740       if (TREE_CODE (TREE_TYPE (decl)) != ARRAY_TYPE)
2741         continue;
2742       vectype = get_vectype_for_scalar_type (TREE_TYPE (TREE_TYPE (decl)));
2743       if (!vectype)
2744         continue;
2745       alignment = TYPE_ALIGN (vectype);
2746       if (DECL_ALIGN (decl) >= alignment)
2747         continue;
2748
2749       if (vect_can_force_dr_alignment_p (decl, alignment))
2750         {
2751           DECL_ALIGN (decl) = TYPE_ALIGN (vectype);
2752           DECL_USER_ALIGN (decl) = 1;
2753           if (dump_file)
2754             {
2755               fprintf (dump_file, "Increasing alignment of decl: ");
2756               print_generic_expr (dump_file, decl, TDF_SLIM);
2757             }
2758         }
2759     }
2760   return 0;
2761 }
2762
2763 static bool
2764 gate_increase_alignment (void)
2765 {
2766   return flag_section_anchors && flag_tree_vectorize;
2767 }
2768
2769 struct tree_opt_pass pass_ipa_increase_alignment =
2770 {
2771   "increase_alignment",                 /* name */
2772   gate_increase_alignment,              /* gate */
2773   increase_alignment,                   /* execute */
2774   NULL,                                 /* sub */
2775   NULL,                                 /* next */
2776   0,                                    /* static_pass_number */
2777   0,                                    /* tv_id */
2778   0,                                    /* properties_required */
2779   0,                                    /* properties_provided */
2780   0,                                    /* properties_destroyed */
2781   0,                                    /* todo_flags_start */
2782   0,                                    /* todo_flags_finish */
2783   0                                     /* letter */
2784 };