gcc/tree-vectorizer.c

   1 /* Loop Vectorization
   2    Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
   3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /* Loop Vectorization Pass.
  23
  24    This pass tries to vectorize loops. This first implementation focuses on
  25    simple inner-most loops, with no conditional control flow, and a set of
  26    simple operations which vector form can be expressed using existing
  27    tree codes (PLUS, MULT etc).
  28
  29    For example, the vectorizer transforms the following simple loop:
  30
  31         short a[N]; short b[N]; short c[N]; int i;
  32
  33         for (i=0; i<N; i++){
  34           a[i] = b[i] + c[i];
  35         }
  36
  37    as if it was manually vectorized by rewriting the source code into:
  38
  39         typedef int __attribute__((mode(V8HI))) v8hi;
  40         short a[N];  short b[N]; short c[N];   int i;
  41         v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
  42         v8hi va, vb, vc;
  43
  44         for (i=0; i<N/8; i++){
  45           vb = pb[i];
  46           vc = pc[i];
  47           va = vb + vc;
  48           pa[i] = va;
  49         }
  50
  51         The main entry to this pass is vectorize_loops(), in which
  52    the vectorizer applies a set of analyses on a given set of loops,
  53    followed by the actual vectorization transformation for the loops that
  54    had successfully passed the analysis phase.
  55
  56         Throughout this pass we make a distinction between two types of
  57    data: scalars (which are represented by SSA_NAMES), and memory references
  58    ("data-refs"). These two types of data require different handling both
  59    during analysis and transformation. The types of data-refs that the
  60    vectorizer currently supports are ARRAY_REFS which base is an array DECL
  61    (not a pointer), and INDIRECT_REFS through pointers; both array and pointer
  62    accesses are required to have a  simple (consecutive) access pattern.
  63
  64    Analysis phase:
  65    ===============
  66         The driver for the analysis phase is vect_analyze_loop_nest().
  67    It applies a set of analyses, some of which rely on the scalar evolution
  68    analyzer (scev) developed by Sebastian Pop.
  69
  70         During the analysis phase the vectorizer records some information
  71    per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
  72    loop, as well as general information about the loop as a whole, which is
  73    recorded in a "loop_vec_info" struct attached to each loop.
  74
  75    Transformation phase:
  76    =====================
  77         The loop transformation phase scans all the stmts in the loop, and
  78    creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
  79    the loop that needs to be vectorized. It insert the vector code sequence
  80    just before the scalar stmt S, and records a pointer to the vector code
  81    in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
  82    attached to S). This pointer will be used for the vectorization of following
  83    stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
  84    otherwise, we rely on dead code elimination for removing it.
  85
  86         For example, say stmt S1 was vectorized into stmt VS1:
  87
  88    VS1: vb = px[i];
  89    S1:  b = x[i];    STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
  90    S2:  a = b;
  91
  92    To vectorize stmt S2, the vectorizer first finds the stmt that defines
  93    the operand 'b' (S1), and gets the relevant vector def 'vb' from the
  94    vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
  95    resulting sequence would be:
  96
  97    VS1: vb = px[i];
  98    S1:  b = x[i];       STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
  99    VS2: va = vb;
 100    S2:  a = b;          STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
 101
 102         Operands that are not SSA_NAMEs, are data-refs that appear in
 103    load/store operations (like 'x[i]' in S1), and are handled differently.
 104
 105    Target modeling:
 106    =================
 107         Currently the only target specific information that is used is the
 108    size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can
 109    support different sizes of vectors, for now will need to specify one value
 110    for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
 111
 112         Since we only vectorize operations which vector form can be
 113    expressed using existing tree codes, to verify that an operation is
 114    supported, the vectorizer checks the relevant optab at the relevant
 115    machine_mode (e.g, add_optab->handlers[(int) V8HImode].insn_code). If
 116    the value found is CODE_FOR_nothing, then there's no target support, and
 117    we can't vectorize the stmt.
 118
 119    For additional information on this project see:
 120    http://gcc.gnu.org/projects/tree-ssa/vectorization.html
 121 */
 122
 123 #include "config.h"
 124 #include "system.h"
 125 #include "coretypes.h"
 126 #include "tm.h"
 127 #include "ggc.h"
 128 #include "tree.h"
 129 #include "target.h"
 130 #include "rtl.h"
 131 #include "basic-block.h"
 132 #include "diagnostic.h"
 133 #include "tree-flow.h"
 134 #include "tree-dump.h"
 135 #include "timevar.h"
 136 #include "cfgloop.h"
 137 #include "cfglayout.h"
 138 #include "expr.h"
 139 #include "recog.h"
 140 #include "optabs.h"
 141 #include "params.h"
 142 #include "toplev.h"
 143 #include "tree-chrec.h"
 144 #include "tree-data-ref.h"
 145 #include "tree-scalar-evolution.h"
 146 #include "input.h"
 147 #include "tree-vectorizer.h"
 148 #include "tree-pass.h"
 149
 150 /*************************************************************************
 151   Simple Loop Peeling Utilities
 152  *************************************************************************/
 153 static void slpeel_update_phis_for_duplicate_loop
 154   (struct loop *, struct loop *, bool after);
 155 static void slpeel_update_phi_nodes_for_guard1
 156   (edge, struct loop *, bool, basic_block *, bitmap *);
 157 static void slpeel_update_phi_nodes_for_guard2
 158   (edge, struct loop *, bool, basic_block *);
 159 static edge slpeel_add_loop_guard (basic_block, tree, basic_block, basic_block);
 160
 161 static void rename_use_op (use_operand_p);
 162 static void rename_variables_in_bb (basic_block);
 163 static void rename_variables_in_loop (struct loop *);
 164
 165 /*************************************************************************
 166   General Vectorization Utilities
 167  *************************************************************************/
 168 static void vect_set_dump_settings (void);
 169
 170 /* vect_dump will be set to stderr or dump_file if exist.  */
 171 FILE *vect_dump;
 172
 173 /* vect_verbosity_level set to an invalid value
 174    to mark that it's uninitialized.  */
 175 enum verbosity_levels vect_verbosity_level = MAX_VERBOSITY_LEVEL;
 176
 177 /* Number of loops, at the beginning of vectorization.  */
 178 unsigned int vect_loops_num;
 179
 180 /* Loop location.  */
 181 static LOC vect_loop_location;
 182
 183 /* Bitmap of virtual variables to be renamed.  */
 184 bitmap vect_vnames_to_rename;
 185 \f
 186 /*************************************************************************
 187   Simple Loop Peeling Utilities
 188
 189   Utilities to support loop peeling for vectorization purposes.
 190  *************************************************************************/
 191
 192
 193 /* Renames the use *OP_P.  */
 194
 195 static void
 196 rename_use_op (use_operand_p op_p)
 197 {
 198   tree new_name;
 199
 200   if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
 201     return;
 202
 203   new_name = get_current_def (USE_FROM_PTR (op_p));
 204
 205   /* Something defined outside of the loop.  */
 206   if (!new_name)
 207     return;
 208
 209   /* An ordinary ssa name defined in the loop.  */
 210
 211   SET_USE (op_p, new_name);
 212 }
 213
 214
 215 /* Renames the variables in basic block BB.  */
 216
 217 static void
 218 rename_variables_in_bb (basic_block bb)
 219 {
 220   tree phi;
 221   block_stmt_iterator bsi;
 222   tree stmt;
 223   use_operand_p use_p;
 224   ssa_op_iter iter;
 225   edge e;
 226   edge_iterator ei;
 227   struct loop *loop = bb->loop_father;
 228
 229   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 230     {
 231       stmt = bsi_stmt (bsi);
 232       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
 233                                  (SSA_OP_ALL_USES | SSA_OP_ALL_KILLS))
 234         rename_use_op (use_p);
 235     }
 236
 237   FOR_EACH_EDGE (e, ei, bb->succs)
 238     {
 239       if (!flow_bb_inside_loop_p (loop, e->dest))
 240         continue;
 241       for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 242         rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e));
 243     }
 244 }
 245
 246
 247 /* Renames variables in new generated LOOP.  */
 248
 249 static void
 250 rename_variables_in_loop (struct loop *loop)
 251 {
 252   unsigned i;
 253   basic_block *bbs;
 254
 255   bbs = get_loop_body (loop);
 256
 257   for (i = 0; i < loop->num_nodes; i++)
 258     rename_variables_in_bb (bbs[i]);
 259
 260   free (bbs);
 261 }
 262
 263
 264 /* Update the PHI nodes of NEW_LOOP.
 265
 266    NEW_LOOP is a duplicate of ORIG_LOOP.
 267    AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
 268    AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
 269    executes before it.  */
 270
 271 static void
 272 slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
 273                                        struct loop *new_loop, bool after)
 274 {
 275   tree new_ssa_name;
 276   tree phi_new, phi_orig;
 277   tree def;
 278   edge orig_loop_latch = loop_latch_edge (orig_loop);
 279   edge orig_entry_e = loop_preheader_edge (orig_loop);
 280   edge new_loop_exit_e = single_exit (new_loop);
 281   edge new_loop_entry_e = loop_preheader_edge (new_loop);
 282   edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
 283
 284   /*
 285      step 1. For each loop-header-phi:
 286              Add the first phi argument for the phi in NEW_LOOP
 287             (the one associated with the entry of NEW_LOOP)
 288
 289      step 2. For each loop-header-phi:
 290              Add the second phi argument for the phi in NEW_LOOP
 291             (the one associated with the latch of NEW_LOOP)
 292
 293      step 3. Update the phis in the successor block of NEW_LOOP.
 294
 295         case 1: NEW_LOOP was placed before ORIG_LOOP:
 296                 The successor block of NEW_LOOP is the header of ORIG_LOOP.
 297                 Updating the phis in the successor block can therefore be done
 298                 along with the scanning of the loop header phis, because the
 299                 header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
 300                 phi nodes, organized in the same order.
 301
 302         case 2: NEW_LOOP was placed after ORIG_LOOP:
 303                 The successor block of NEW_LOOP is the original exit block of
 304                 ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
 305                 We postpone updating these phis to a later stage (when
 306                 loop guards are added).
 307    */
 308
 309
 310   /* Scan the phis in the headers of the old and new loops
 311      (they are organized in exactly the same order).  */
 312
 313   for (phi_new = phi_nodes (new_loop->header),
 314        phi_orig = phi_nodes (orig_loop->header);
 315        phi_new && phi_orig;
 316        phi_new = PHI_CHAIN (phi_new), phi_orig = PHI_CHAIN (phi_orig))
 317     {
 318       /* step 1.  */
 319       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
 320       add_phi_arg (phi_new, def, new_loop_entry_e);
 321
 322       /* step 2.  */
 323       def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
 324       if (TREE_CODE (def) != SSA_NAME)
 325         continue;
 326
 327       new_ssa_name = get_current_def (def);
 328       if (!new_ssa_name)
 329         {
 330           /* This only happens if there are no definitions
 331              inside the loop. use the phi_result in this case.  */
 332           new_ssa_name = PHI_RESULT (phi_new);
 333         }
 334
 335       /* An ordinary ssa name defined in the loop.  */
 336       add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
 337
 338       /* step 3 (case 1).  */
 339       if (!after)
 340         {
 341           gcc_assert (new_loop_exit_e == orig_entry_e);
 342           SET_PHI_ARG_DEF (phi_orig,
 343                            new_loop_exit_e->dest_idx,
 344                            new_ssa_name);
 345         }
 346     }
 347 }
 348
 349
 350 /* Update PHI nodes for a guard of the LOOP.
 351
 352    Input:
 353    - LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
 354         controls whether LOOP is to be executed.  GUARD_EDGE is the edge that
 355         originates from the guard-bb, skips LOOP and reaches the (unique) exit
 356         bb of LOOP.  This loop-exit-bb is an empty bb with one successor.
 357         We denote this bb NEW_MERGE_BB because before the guard code was added
 358         it had a single predecessor (the LOOP header), and now it became a merge
 359         point of two paths - the path that ends with the LOOP exit-edge, and
 360         the path that ends with GUARD_EDGE.
 361    - NEW_EXIT_BB: New basic block that is added by this function between LOOP
 362         and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
 363
 364    ===> The CFG before the guard-code was added:
 365         LOOP_header_bb:
 366           loop_body
 367           if (exit_loop) goto update_bb
 368           else           goto LOOP_header_bb
 369         update_bb:
 370
 371    ==> The CFG after the guard-code was added:
 372         guard_bb:
 373           if (LOOP_guard_condition) goto new_merge_bb
 374           else                      goto LOOP_header_bb
 375         LOOP_header_bb:
 376           loop_body
 377           if (exit_loop_condition) goto new_merge_bb
 378           else                     goto LOOP_header_bb
 379         new_merge_bb:
 380           goto update_bb
 381         update_bb:
 382
 383    ==> The CFG after this function:
 384         guard_bb:
 385           if (LOOP_guard_condition) goto new_merge_bb
 386           else                      goto LOOP_header_bb
 387         LOOP_header_bb:
 388           loop_body
 389           if (exit_loop_condition) goto new_exit_bb
 390           else                     goto LOOP_header_bb
 391         new_exit_bb:
 392         new_merge_bb:
 393           goto update_bb
 394         update_bb:
 395
 396    This function:
 397    1. creates and updates the relevant phi nodes to account for the new
 398       incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
 399       1.1. Create phi nodes at NEW_MERGE_BB.
 400       1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
 401            UPDATE_BB).  UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
 402    2. preserves loop-closed-ssa-form by creating the required phi nodes
 403       at the exit of LOOP (i.e, in NEW_EXIT_BB).
 404
 405    There are two flavors to this function:
 406
 407    slpeel_update_phi_nodes_for_guard1:
 408      Here the guard controls whether we enter or skip LOOP, where LOOP is a
 409      prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
 410      for variables that have phis in the loop header.
 411
 412    slpeel_update_phi_nodes_for_guard2:
 413      Here the guard controls whether we enter or skip LOOP, where LOOP is an
 414      epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
 415      for variables that have phis in the loop exit.
 416
 417    I.E., the overall structure is:
 418
 419         loop1_preheader_bb:
 420                 guard1 (goto loop1/merg1_bb)
 421         loop1
 422         loop1_exit_bb:
 423                 guard2 (goto merge1_bb/merge2_bb)
 424         merge1_bb
 425         loop2
 426         loop2_exit_bb
 427         merge2_bb
 428         next_bb
 429
 430    slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
 431    loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
 432    that have phis in loop1->header).
 433
 434    slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
 435    loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars
 436    that have phis in next_bb). It also adds some of these phis to
 437    loop1_exit_bb.
 438
 439    slpeel_update_phi_nodes_for_guard1 is always called before
 440    slpeel_update_phi_nodes_for_guard2. They are both needed in order
 441    to create correct data-flow and loop-closed-ssa-form.
 442
 443    Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
 444    that change between iterations of a loop (and therefore have a phi-node
 445    at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates
 446    phis for variables that are used out of the loop (and therefore have
 447    loop-closed exit phis). Some variables may be both updated between
 448    iterations and used after the loop. This is why in loop1_exit_bb we
 449    may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
 450    and exit phis (created by slpeel_update_phi_nodes_for_guard2).
 451
 452    - IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
 453      an original loop. i.e., we have:
 454
 455            orig_loop
 456            guard_bb (goto LOOP/new_merge)
 457            new_loop <-- LOOP
 458            new_exit
 459            new_merge
 460            next_bb
 461
 462      If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
 463      have:
 464
 465            new_loop
 466            guard_bb (goto LOOP/new_merge)
 467            orig_loop <-- LOOP
 468            new_exit
 469            new_merge
 470            next_bb
 471
 472      The SSA names defined in the original loop have a current
 473      reaching definition that that records the corresponding new
 474      ssa-name used in the new duplicated loop copy.
 475   */
 476
 477 /* Function slpeel_update_phi_nodes_for_guard1
 478
 479    Input:
 480    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
 481    - DEFS - a bitmap of ssa names to mark new names for which we recorded
 482             information.
 483
 484    In the context of the overall structure, we have:
 485
 486         loop1_preheader_bb:
 487                 guard1 (goto loop1/merg1_bb)
 488 LOOP->  loop1
 489         loop1_exit_bb:
 490                 guard2 (goto merge1_bb/merge2_bb)
 491         merge1_bb
 492         loop2
 493         loop2_exit_bb
 494         merge2_bb
 495         next_bb
 496
 497    For each name updated between loop iterations (i.e - for each name that has
 498    an entry (loop-header) phi in LOOP) we create a new phi in:
 499    1. merge1_bb (to account for the edge from guard1)
 500    2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
 501 */
 502
 503 static void
 504 slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
 505                                     bool is_new_loop, basic_block *new_exit_bb,
 506                                     bitmap *defs)
 507 {
 508   tree orig_phi, new_phi;
 509   tree update_phi, update_phi2;
 510   tree guard_arg, loop_arg;
 511   basic_block new_merge_bb = guard_edge->dest;
 512   edge e = EDGE_SUCC (new_merge_bb, 0);
 513   basic_block update_bb = e->dest;
 514   basic_block orig_bb = loop->header;
 515   edge new_exit_e;
 516   tree current_new_name;
 517   tree name;
 518
 519   /* Create new bb between loop and new_merge_bb.  */
 520   *new_exit_bb = split_edge (single_exit (loop));
 521
 522   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
 523
 524   for (orig_phi = phi_nodes (orig_bb), update_phi = phi_nodes (update_bb);
 525        orig_phi && update_phi;
 526        orig_phi = PHI_CHAIN (orig_phi), update_phi = PHI_CHAIN (update_phi))
 527     {
 528       /* Virtual phi; Mark it for renaming. We actually want to call
 529          mar_sym_for_renaming, but since all ssa renaming datastructures
 530          are going to be freed before we get to call ssa_upate, we just
 531          record this name for now in a bitmap, and will mark it for
 532          renaming later.  */
 533       name = PHI_RESULT (orig_phi);
 534       if (!is_gimple_reg (SSA_NAME_VAR (name)))
 535         bitmap_set_bit (vect_vnames_to_rename, SSA_NAME_VERSION (name));
 536
 537       /** 1. Handle new-merge-point phis  **/
 538
 539       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
 540       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 541                                  new_merge_bb);
 542
 543       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
 544             of LOOP. Set the two phi args in NEW_PHI for these edges:  */
 545       loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
 546       guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
 547
 548       add_phi_arg (new_phi, loop_arg, new_exit_e);
 549       add_phi_arg (new_phi, guard_arg, guard_edge);
 550
 551       /* 1.3. Update phi in successor block.  */
 552       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
 553                   || PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
 554       SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
 555       update_phi2 = new_phi;
 556
 557
 558       /** 2. Handle loop-closed-ssa-form phis  **/
 559
 560       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
 561       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 562                                  *new_exit_bb);
 563
 564       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
 565       add_phi_arg (new_phi, loop_arg, single_exit (loop));
 566
 567       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
 568       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
 569       SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
 570
 571       /* 2.4. Record the newly created name with set_current_def.
 572          We want to find a name such that
 573                 name = get_current_def (orig_loop_name)
 574          and to set its current definition as follows:
 575                 set_current_def (name, new_phi_name)
 576
 577          If LOOP is a new loop then loop_arg is already the name we're
 578          looking for. If LOOP is the original loop, then loop_arg is
 579          the orig_loop_name and the relevant name is recorded in its
 580          current reaching definition.  */
 581       if (is_new_loop)
 582         current_new_name = loop_arg;
 583       else
 584         {
 585           current_new_name = get_current_def (loop_arg);
 586           /* current_def is not available only if the variable does not
 587              change inside the loop, in which case we also don't care
 588              about recording a current_def for it because we won't be
 589              trying to create loop-exit-phis for it.  */
 590           if (!current_new_name)
 591             continue;
 592         }
 593       gcc_assert (get_current_def (current_new_name) == NULL_TREE);
 594
 595       set_current_def (current_new_name, PHI_RESULT (new_phi));
 596       bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
 597     }
 598
 599   set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
 600 }
 601
 602
 603 /* Function slpeel_update_phi_nodes_for_guard2
 604
 605    Input:
 606    - GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
 607
 608    In the context of the overall structure, we have:
 609
 610         loop1_preheader_bb:
 611                 guard1 (goto loop1/merg1_bb)
 612         loop1
 613         loop1_exit_bb:
 614                 guard2 (goto merge1_bb/merge2_bb)
 615         merge1_bb
 616 LOOP->  loop2
 617         loop2_exit_bb
 618         merge2_bb
 619         next_bb
 620
 621    For each name used out side the loop (i.e - for each name that has an exit
 622    phi in next_bb) we create a new phi in:
 623    1. merge2_bb (to account for the edge from guard_bb)
 624    2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
 625    3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
 626       if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
 627 */
 628
 629 static void
 630 slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
 631                                     bool is_new_loop, basic_block *new_exit_bb)
 632 {
 633   tree orig_phi, new_phi;
 634   tree update_phi, update_phi2;
 635   tree guard_arg, loop_arg;
 636   basic_block new_merge_bb = guard_edge->dest;
 637   edge e = EDGE_SUCC (new_merge_bb, 0);
 638   basic_block update_bb = e->dest;
 639   edge new_exit_e;
 640   tree orig_def, orig_def_new_name;
 641   tree new_name, new_name2;
 642   tree arg;
 643
 644   /* Create new bb between loop and new_merge_bb.  */
 645   *new_exit_bb = split_edge (single_exit (loop));
 646
 647   new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
 648
 649   for (update_phi = phi_nodes (update_bb); update_phi;
 650        update_phi = PHI_CHAIN (update_phi))
 651     {
 652       orig_phi = update_phi;
 653       orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
 654       /* This loop-closed-phi actually doesn't represent a use
 655          out of the loop - the phi arg is a constant.  */
 656       if (TREE_CODE (orig_def) != SSA_NAME)
 657         continue;
 658       orig_def_new_name = get_current_def (orig_def);
 659       arg = NULL_TREE;
 660
 661       /** 1. Handle new-merge-point phis  **/
 662
 663       /* 1.1. Generate new phi node in NEW_MERGE_BB:  */
 664       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 665                                  new_merge_bb);
 666
 667       /* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
 668             of LOOP. Set the two PHI args in NEW_PHI for these edges:  */
 669       new_name = orig_def;
 670       new_name2 = NULL_TREE;
 671       if (orig_def_new_name)
 672         {
 673           new_name = orig_def_new_name;
 674           /* Some variables have both loop-entry-phis and loop-exit-phis.
 675              Such variables were given yet newer names by phis placed in
 676              guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
 677              new_name2 = get_current_def (get_current_def (orig_name)).  */
 678           new_name2 = get_current_def (new_name);
 679         }
 680
 681       if (is_new_loop)
 682         {
 683           guard_arg = orig_def;
 684           loop_arg = new_name;
 685         }
 686       else
 687         {
 688           guard_arg = new_name;
 689           loop_arg = orig_def;
 690         }
 691       if (new_name2)
 692         guard_arg = new_name2;
 693
 694       add_phi_arg (new_phi, loop_arg, new_exit_e);
 695       add_phi_arg (new_phi, guard_arg, guard_edge);
 696
 697       /* 1.3. Update phi in successor block.  */
 698       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
 699       SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
 700       update_phi2 = new_phi;
 701
 702
 703       /** 2. Handle loop-closed-ssa-form phis  **/
 704
 705       /* 2.1. Generate new phi node in NEW_EXIT_BB:  */
 706       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 707                                  *new_exit_bb);
 708
 709       /* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.  */
 710       add_phi_arg (new_phi, loop_arg, single_exit (loop));
 711
 712       /* 2.3. Update phi in successor of NEW_EXIT_BB:  */
 713       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
 714       SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
 715
 716
 717       /** 3. Handle loop-closed-ssa-form phis for first loop  **/
 718
 719       /* 3.1. Find the relevant names that need an exit-phi in
 720          GUARD_BB, i.e. names for which
 721          slpeel_update_phi_nodes_for_guard1 had not already created a
 722          phi node. This is the case for names that are used outside
 723          the loop (and therefore need an exit phi) but are not updated
 724          across loop iterations (and therefore don't have a
 725          loop-header-phi).
 726
 727          slpeel_update_phi_nodes_for_guard1 is responsible for
 728          creating loop-exit phis in GUARD_BB for names that have a
 729          loop-header-phi.  When such a phi is created we also record
 730          the new name in its current definition.  If this new name
 731          exists, then guard_arg was set to this new name (see 1.2
 732          above).  Therefore, if guard_arg is not this new name, this
 733          is an indication that an exit-phi in GUARD_BB was not yet
 734          created, so we take care of it here.  */
 735       if (guard_arg == new_name2)
 736         continue;
 737       arg = guard_arg;
 738
 739       /* 3.2. Generate new phi node in GUARD_BB:  */
 740       new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
 741                                  guard_edge->src);
 742
 743       /* 3.3. GUARD_BB has one incoming edge:  */
 744       gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
 745       add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
 746
 747       /* 3.4. Update phi in successor of GUARD_BB:  */
 748       gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
 749                                                                 == guard_arg);
 750       SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
 751     }
 752
 753   set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
 754 }
 755
 756
 757 /* Make the LOOP iterate NITERS times. This is done by adding a new IV
 758    that starts at zero, increases by one and its limit is NITERS.
 759
 760    Assumption: the exit-condition of LOOP is the last stmt in the loop.  */
 761
 762 void
 763 slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
 764 {
 765   tree indx_before_incr, indx_after_incr, cond_stmt, cond;
 766   tree orig_cond;
 767   edge exit_edge = single_exit (loop);
 768   block_stmt_iterator loop_cond_bsi;
 769   block_stmt_iterator incr_bsi;
 770   bool insert_after;
 771   tree begin_label = tree_block_label (loop->latch);
 772   tree exit_label = tree_block_label (single_exit (loop)->dest);
 773   tree init = build_int_cst (TREE_TYPE (niters), 0);
 774   tree step = build_int_cst (TREE_TYPE (niters), 1);
 775   tree then_label;
 776   tree else_label;
 777   LOC loop_loc;
 778
 779   orig_cond = get_loop_exit_condition (loop);
 780   gcc_assert (orig_cond);
 781   loop_cond_bsi = bsi_for_stmt (orig_cond);
 782
 783   standard_iv_increment_position (loop, &incr_bsi, &insert_after);
 784   create_iv (init, step, NULL_TREE, loop,
 785              &incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
 786
 787   if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop.  */
 788     {
 789       cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
 790       then_label = build1 (GOTO_EXPR, void_type_node, exit_label);
 791       else_label = build1 (GOTO_EXPR, void_type_node, begin_label);
 792     }
 793   else /* 'then' edge loops back.  */
 794     {
 795       cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
 796       then_label = build1 (GOTO_EXPR, void_type_node, begin_label);
 797       else_label = build1 (GOTO_EXPR, void_type_node, exit_label);
 798     }
 799
 800   cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
 801                      then_label, else_label);
 802   bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
 803
 804   /* Remove old loop exit test:  */
 805   bsi_remove (&loop_cond_bsi, true);
 806
 807   loop_loc = find_loop_location (loop);
 808   if (dump_file && (dump_flags & TDF_DETAILS))
 809     {
 810       if (loop_loc != UNKNOWN_LOC)
 811         fprintf (dump_file, "\nloop at %s:%d: ",
 812                  LOC_FILE (loop_loc), LOC_LINE (loop_loc));
 813       print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
 814     }
 815
 816   loop->nb_iterations = niters;
 817 }
 818
 819
 820 /* Given LOOP this function generates a new copy of it and puts it
 821    on E which is either the entry or exit of LOOP.  */
 822
 823 static struct loop *
 824 slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, edge e)
 825 {
 826   struct loop *new_loop;
 827   basic_block *new_bbs, *bbs;
 828   bool at_exit;
 829   bool was_imm_dom;
 830   basic_block exit_dest;
 831   tree phi, phi_arg;
 832   edge exit, new_exit;
 833
 834   at_exit = (e == single_exit (loop));
 835   if (!at_exit && e != loop_preheader_edge (loop))
 836     return NULL;
 837
 838   bbs = get_loop_body (loop);
 839
 840   /* Check whether duplication is possible.  */
 841   if (!can_copy_bbs_p (bbs, loop->num_nodes))
 842     {
 843       free (bbs);
 844       return NULL;
 845     }
 846
 847   /* Generate new loop structure.  */
 848   new_loop = duplicate_loop (loop, loop->outer);
 849   if (!new_loop)
 850     {
 851       free (bbs);
 852       return NULL;
 853     }
 854
 855   exit_dest = single_exit (loop)->dest;
 856   was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
 857                                           exit_dest) == loop->header ?
 858                  true : false);
 859
 860   new_bbs = XNEWVEC (basic_block, loop->num_nodes);
 861
 862   exit = single_exit (loop);
 863   copy_bbs (bbs, loop->num_nodes, new_bbs,
 864             &exit, 1, &new_exit, NULL,
 865             e->src);
 866   set_single_exit (new_loop, new_exit);
 867
 868   /* Duplicating phi args at exit bbs as coming
 869      also from exit of duplicated loop.  */
 870   for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
 871     {
 872       phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, single_exit (loop));
 873       if (phi_arg)
 874         {
 875           edge new_loop_exit_edge;
 876
 877           if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
 878             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
 879           else
 880             new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
 881
 882           add_phi_arg (phi, phi_arg, new_loop_exit_edge);
 883         }
 884     }
 885
 886   if (at_exit) /* Add the loop copy at exit.  */
 887     {
 888       redirect_edge_and_branch_force (e, new_loop->header);
 889       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
 890       if (was_imm_dom)
 891         set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
 892     }
 893   else /* Add the copy at entry.  */
 894     {
 895       edge new_exit_e;
 896       edge entry_e = loop_preheader_edge (loop);
 897       basic_block preheader = entry_e->src;
 898
 899       if (!flow_bb_inside_loop_p (new_loop,
 900                                   EDGE_SUCC (new_loop->header, 0)->dest))
 901         new_exit_e = EDGE_SUCC (new_loop->header, 0);
 902       else
 903         new_exit_e = EDGE_SUCC (new_loop->header, 1);
 904
 905       redirect_edge_and_branch_force (new_exit_e, loop->header);
 906       set_immediate_dominator (CDI_DOMINATORS, loop->header,
 907                                new_exit_e->src);
 908
 909       /* We have to add phi args to the loop->header here as coming
 910          from new_exit_e edge.  */
 911       for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
 912         {
 913           phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
 914           if (phi_arg)
 915             add_phi_arg (phi, phi_arg, new_exit_e);
 916         }
 917
 918       redirect_edge_and_branch_force (entry_e, new_loop->header);
 919       set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
 920     }
 921
 922   free (new_bbs);
 923   free (bbs);
 924
 925   return new_loop;
 926 }
 927
 928
 929 /* Given the condition statement COND, put it as the last statement
 930    of GUARD_BB; EXIT_BB is the basic block to skip the loop;
 931    Assumes that this is the single exit of the guarded loop.
 932    Returns the skip edge.  */
 933
 934 static edge
 935 slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
 936                         basic_block dom_bb)
 937 {
 938   block_stmt_iterator bsi;
 939   edge new_e, enter_e;
 940   tree cond_stmt, then_label, else_label;
 941
 942   enter_e = EDGE_SUCC (guard_bb, 0);
 943   enter_e->flags &= ~EDGE_FALLTHRU;
 944   enter_e->flags |= EDGE_FALSE_VALUE;
 945   bsi = bsi_last (guard_bb);
 946
 947   then_label = build1 (GOTO_EXPR, void_type_node,
 948                        tree_block_label (exit_bb));
 949   else_label = build1 (GOTO_EXPR, void_type_node,
 950                        tree_block_label (enter_e->dest));
 951   cond_stmt = build3 (COND_EXPR, void_type_node, cond,
 952                      then_label, else_label);
 953   bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
 954   /* Add new edge to connect guard block to the merge/loop-exit block.  */
 955   new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
 956   set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
 957   return new_e;
 958 }
 959
 960
 961 /* This function verifies that the following restrictions apply to LOOP:
 962    (1) it is innermost
 963    (2) it consists of exactly 2 basic blocks - header, and an empty latch.
 964    (3) it is single entry, single exit
 965    (4) its exit condition is the last stmt in the header
 966    (5) E is the entry/exit edge of LOOP.
 967  */
 968
 969 bool
 970 slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
 971 {
 972   edge exit_e = single_exit (loop);
 973   edge entry_e = loop_preheader_edge (loop);
 974   tree orig_cond = get_loop_exit_condition (loop);
 975   block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
 976
 977   if (need_ssa_update_p ())
 978     return false;
 979
 980   if (loop->inner
 981       /* All loops have an outer scope; the only case loop->outer is NULL is for
 982          the function itself.  */
 983       || !loop->outer
 984       || loop->num_nodes != 2
 985       || !empty_block_p (loop->latch)
 986       || !single_exit (loop)
 987       /* Verify that new loop exit condition can be trivially modified.  */
 988       || (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
 989       || (e != exit_e && e != entry_e))
 990     return false;
 991
 992   return true;
 993 }
 994
 995 #ifdef ENABLE_CHECKING
 996 void
 997 slpeel_verify_cfg_after_peeling (struct loop *first_loop,
 998                                  struct loop *second_loop)
 999 {
1000   basic_block loop1_exit_bb = single_exit (first_loop)->dest;
1001   basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
1002   basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
1003
1004   /* A guard that controls whether the second_loop is to be executed or skipped
1005      is placed in first_loop->exit.  first_loopt->exit therefore has two
1006      successors - one is the preheader of second_loop, and the other is a bb
1007      after second_loop.
1008    */
1009   gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
1010
1011   /* 1. Verify that one of the successors of first_loopt->exit is the preheader
1012         of second_loop.  */
1013
1014   /* The preheader of new_loop is expected to have two predecessors:
1015      first_loop->exit and the block that precedes first_loop.  */
1016
1017   gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
1018               && ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
1019                    && EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
1020                || (EDGE_PRED (loop2_entry_bb, 1)->src ==  loop1_exit_bb
1021                    && EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
1022
1023   /* Verify that the other successor of first_loopt->exit is after the
1024      second_loop.  */
1025   /* TODO */
1026 }
1027 #endif
1028
1029 /* Function slpeel_tree_peel_loop_to_edge.
1030
1031    Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
1032    that is placed on the entry (exit) edge E of LOOP. After this transformation
1033    we have two loops one after the other - first-loop iterates FIRST_NITERS
1034    times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
1035
1036    Input:
1037    - LOOP: the loop to be peeled.
1038    - E: the exit or entry edge of LOOP.
1039         If it is the entry edge, we peel the first iterations of LOOP. In this
1040         case first-loop is LOOP, and second-loop is the newly created loop.
1041         If it is the exit edge, we peel the last iterations of LOOP. In this
1042         case, first-loop is the newly created loop, and second-loop is LOOP.
1043    - NITERS: the number of iterations that LOOP iterates.
1044    - FIRST_NITERS: the number of iterations that the first-loop should iterate.
1045    - UPDATE_FIRST_LOOP_COUNT:  specified whether this function is responsible
1046         for updating the loop bound of the first-loop to FIRST_NITERS.  If it
1047         is false, the caller of this function may want to take care of this
1048         (this can be useful if we don't want new stmts added to first-loop).
1049
1050    Output:
1051    The function returns a pointer to the new loop-copy, or NULL if it failed
1052    to perform the transformation.
1053
1054    The function generates two if-then-else guards: one before the first loop,
1055    and the other before the second loop:
1056    The first guard is:
1057      if (FIRST_NITERS == 0) then skip the first loop,
1058      and go directly to the second loop.
1059    The second guard is:
1060      if (FIRST_NITERS == NITERS) then skip the second loop.
1061
1062    FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
1063    FORNOW the resulting code will not be in loop-closed-ssa form.
1064 */
1065
1066 struct loop*
1067 slpeel_tree_peel_loop_to_edge (struct loop *loop,
1068                                edge e, tree first_niters,
1069                                tree niters, bool update_first_loop_count)
1070 {
1071   struct loop *new_loop = NULL, *first_loop, *second_loop;
1072   edge skip_e;
1073   tree pre_condition;
1074   bitmap definitions;
1075   basic_block bb_before_second_loop, bb_after_second_loop;
1076   basic_block bb_before_first_loop;
1077   basic_block bb_between_loops;
1078   basic_block new_exit_bb;
1079   edge exit_e = single_exit (loop);
1080   LOC loop_loc;
1081
1082   if (!slpeel_can_duplicate_loop_p (loop, e))
1083     return NULL;
1084
1085   /* We have to initialize cfg_hooks. Then, when calling
1086    cfg_hooks->split_edge, the function tree_split_edge
1087    is actually called and, when calling cfg_hooks->duplicate_block,
1088    the function tree_duplicate_bb is called.  */
1089   tree_register_cfg_hooks ();
1090
1091
1092   /* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
1093         Resulting CFG would be:
1094
1095         first_loop:
1096         do {
1097         } while ...
1098
1099         second_loop:
1100         do {
1101         } while ...
1102
1103         orig_exit_bb:
1104    */
1105
1106   if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, e)))
1107     {
1108       loop_loc = find_loop_location (loop);
1109       if (dump_file && (dump_flags & TDF_DETAILS))
1110         {
1111           if (loop_loc != UNKNOWN_LOC)
1112             fprintf (dump_file, "\n%s:%d: note: ",
1113                      LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1114           fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
1115         }
1116       return NULL;
1117     }
1118
1119   if (e == exit_e)
1120     {
1121       /* NEW_LOOP was placed after LOOP.  */
1122       first_loop = loop;
1123       second_loop = new_loop;
1124     }
1125   else
1126     {
1127       /* NEW_LOOP was placed before LOOP.  */
1128       first_loop = new_loop;
1129       second_loop = loop;
1130     }
1131
1132   definitions = ssa_names_to_replace ();
1133   slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
1134   rename_variables_in_loop (new_loop);
1135
1136
1137   /* 2. Add the guard that controls whether the first loop is executed.
1138         Resulting CFG would be:
1139
1140         bb_before_first_loop:
1141         if (FIRST_NITERS == 0) GOTO bb_before_second_loop
1142                                GOTO first-loop
1143
1144         first_loop:
1145         do {
1146         } while ...
1147
1148         bb_before_second_loop:
1149
1150         second_loop:
1151         do {
1152         } while ...
1153
1154         orig_exit_bb:
1155    */
1156
1157   bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
1158   bb_before_second_loop = split_edge (single_exit (first_loop));
1159
1160   pre_condition =
1161     fold_build2 (LE_EXPR, boolean_type_node, first_niters,
1162                  build_int_cst (TREE_TYPE (first_niters), 0));
1163   skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
1164                                   bb_before_second_loop, bb_before_first_loop);
1165   slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
1166                                       first_loop == new_loop,
1167                                       &new_exit_bb, &definitions);
1168
1169
1170   /* 3. Add the guard that controls whether the second loop is executed.
1171         Resulting CFG would be:
1172
1173         bb_before_first_loop:
1174         if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
1175                                GOTO first-loop
1176
1177         first_loop:
1178         do {
1179         } while ...
1180
1181         bb_between_loops:
1182         if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
1183                                     GOTO bb_before_second_loop
1184
1185         bb_before_second_loop:
1186
1187         second_loop:
1188         do {
1189         } while ...
1190
1191         bb_after_second_loop:
1192
1193         orig_exit_bb:
1194    */
1195
1196   bb_between_loops = new_exit_bb;
1197   bb_after_second_loop = split_edge (single_exit (second_loop));
1198
1199   pre_condition =
1200         fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
1201   skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
1202                                   bb_after_second_loop, bb_before_first_loop);
1203   slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
1204                                      second_loop == new_loop, &new_exit_bb);
1205
1206   /* 4. Make first-loop iterate FIRST_NITERS times, if requested.
1207    */
1208   if (update_first_loop_count)
1209     slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
1210
1211   BITMAP_FREE (definitions);
1212   delete_update_ssa ();
1213
1214   return new_loop;
1215 }
1216
1217 /* Function vect_get_loop_location.
1218
1219    Extract the location of the loop in the source code.
1220    If the loop is not well formed for vectorization, an estimated
1221    location is calculated.
1222    Return the loop location if succeed and NULL if not.  */
1223
1224 LOC
1225 find_loop_location (struct loop *loop)
1226 {
1227   tree node = NULL_TREE;
1228   basic_block bb;
1229   block_stmt_iterator si;
1230
1231   if (!loop)
1232     return UNKNOWN_LOC;
1233
1234   node = get_loop_exit_condition (loop);
1235
1236   if (node && CAN_HAVE_LOCATION_P (node) && EXPR_HAS_LOCATION (node)
1237       && EXPR_FILENAME (node) && EXPR_LINENO (node))
1238     return EXPR_LOC (node);
1239
1240   /* If we got here the loop is probably not "well formed",
1241      try to estimate the loop location */
1242
1243   if (!loop->header)
1244     return UNKNOWN_LOC;
1245
1246   bb = loop->header;
1247
1248   for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1249     {
1250       node = bsi_stmt (si);
1251       if (node && CAN_HAVE_LOCATION_P (node) && EXPR_HAS_LOCATION (node))
1252         return EXPR_LOC (node);
1253     }
1254
1255   return UNKNOWN_LOC;
1256 }
1257
1258
1259 /*************************************************************************
1260   Vectorization Debug Information.
1261  *************************************************************************/
1262
1263 /* Function vect_set_verbosity_level.
1264
1265    Called from toplev.c upon detection of the
1266    -ftree-vectorizer-verbose=N option.  */
1267
1268 void
1269 vect_set_verbosity_level (const char *val)
1270 {
1271    unsigned int vl;
1272
1273    vl = atoi (val);
1274    if (vl < MAX_VERBOSITY_LEVEL)
1275      vect_verbosity_level = vl;
1276    else
1277      vect_verbosity_level = MAX_VERBOSITY_LEVEL - 1;
1278 }
1279
1280
1281 /* Function vect_set_dump_settings.
1282
1283    Fix the verbosity level of the vectorizer if the
1284    requested level was not set explicitly using the flag
1285    -ftree-vectorizer-verbose=N.
1286    Decide where to print the debugging information (dump_file/stderr).
1287    If the user defined the verbosity level, but there is no dump file,
1288    print to stderr, otherwise print to the dump file.  */
1289
1290 static void
1291 vect_set_dump_settings (void)
1292 {
1293   vect_dump = dump_file;
1294
1295   /* Check if the verbosity level was defined by the user:  */
1296   if (vect_verbosity_level != MAX_VERBOSITY_LEVEL)
1297     {
1298       /* If there is no dump file, print to stderr.  */
1299       if (!dump_file)
1300         vect_dump = stderr;
1301       return;
1302     }
1303
1304   /* User didn't specify verbosity level:  */
1305   if (dump_file && (dump_flags & TDF_DETAILS))
1306     vect_verbosity_level = REPORT_DETAILS;
1307   else if (dump_file && (dump_flags & TDF_STATS))
1308     vect_verbosity_level = REPORT_UNVECTORIZED_LOOPS;
1309   else
1310     vect_verbosity_level = REPORT_NONE;
1311
1312   gcc_assert (dump_file || vect_verbosity_level == REPORT_NONE);
1313 }
1314
1315
1316 /* Function debug_loop_details.
1317
1318    For vectorization debug dumps.  */
1319
1320 bool
1321 vect_print_dump_info (enum verbosity_levels vl)
1322 {
1323   if (vl > vect_verbosity_level)
1324     return false;
1325
1326   if (!current_function_decl || !vect_dump)
1327     return false;
1328
1329   if (vect_loop_location == UNKNOWN_LOC)
1330     fprintf (vect_dump, "\n%s:%d: note: ",
1331              DECL_SOURCE_FILE (current_function_decl),
1332              DECL_SOURCE_LINE (current_function_decl));
1333   else
1334     fprintf (vect_dump, "\n%s:%d: note: ",
1335              LOC_FILE (vect_loop_location), LOC_LINE (vect_loop_location));
1336
1337   return true;
1338 }
1339
1340
1341 /*************************************************************************
1342   Vectorization Utilities.
1343  *************************************************************************/
1344
1345 /* Function new_stmt_vec_info.
1346
1347    Create and initialize a new stmt_vec_info struct for STMT.  */
1348
1349 stmt_vec_info
1350 new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
1351 {
1352   stmt_vec_info res;
1353   res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
1354
1355   STMT_VINFO_TYPE (res) = undef_vec_info_type;
1356   STMT_VINFO_STMT (res) = stmt;
1357   STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
1358   STMT_VINFO_RELEVANT (res) = 0;
1359   STMT_VINFO_LIVE_P (res) = false;
1360   STMT_VINFO_VECTYPE (res) = NULL;
1361   STMT_VINFO_VEC_STMT (res) = NULL;
1362   STMT_VINFO_IN_PATTERN_P (res) = false;
1363   STMT_VINFO_RELATED_STMT (res) = NULL;
1364   STMT_VINFO_DATA_REF (res) = NULL;
1365   if (TREE_CODE (stmt) == PHI_NODE)
1366     STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
1367   else
1368     STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
1369   STMT_VINFO_SAME_ALIGN_REFS (res) = VEC_alloc (dr_p, heap, 5);
1370   DR_GROUP_FIRST_DR (res) = NULL_TREE;
1371   DR_GROUP_NEXT_DR (res) = NULL_TREE;
1372   DR_GROUP_SIZE (res) = 0;
1373   DR_GROUP_STORE_COUNT (res) = 0;
1374   DR_GROUP_GAP (res) = 0;
1375   DR_GROUP_SAME_DR_STMT (res) = NULL_TREE;
1376
1377   return res;
1378 }
1379
1380
1381 /* Function new_loop_vec_info.
1382
1383    Create and initialize a new loop_vec_info struct for LOOP, as well as
1384    stmt_vec_info structs for all the stmts in LOOP.  */
1385
1386 loop_vec_info
1387 new_loop_vec_info (struct loop *loop)
1388 {
1389   loop_vec_info res;
1390   basic_block *bbs;
1391   block_stmt_iterator si;
1392   unsigned int i;
1393
1394   res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
1395
1396   bbs = get_loop_body (loop);
1397
1398   /* Create stmt_info for all stmts in the loop.  */
1399   for (i = 0; i < loop->num_nodes; i++)
1400     {
1401       basic_block bb = bbs[i];
1402       tree phi;
1403
1404       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1405         {
1406           stmt_ann_t ann = get_stmt_ann (phi);
1407           set_stmt_info (ann, new_stmt_vec_info (phi, res));
1408         }
1409
1410       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
1411         {
1412           tree stmt = bsi_stmt (si);
1413           stmt_ann_t ann;
1414
1415           ann = stmt_ann (stmt);
1416           set_stmt_info (ann, new_stmt_vec_info (stmt, res));
1417         }
1418     }
1419
1420   LOOP_VINFO_LOOP (res) = loop;
1421   LOOP_VINFO_BBS (res) = bbs;
1422   LOOP_VINFO_EXIT_COND (res) = NULL;
1423   LOOP_VINFO_NITERS (res) = NULL;
1424   LOOP_VINFO_VECTORIZABLE_P (res) = 0;
1425   LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
1426   LOOP_VINFO_VECT_FACTOR (res) = 0;
1427   LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
1428   LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
1429   LOOP_VINFO_UNALIGNED_DR (res) = NULL;
1430   LOOP_VINFO_MAY_MISALIGN_STMTS (res)
1431     = VEC_alloc (tree, heap, PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS));
1432
1433   return res;
1434 }
1435
1436
1437 /* Function destroy_loop_vec_info.
1438
1439    Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
1440    stmts in the loop.  */
1441
1442 void
1443 destroy_loop_vec_info (loop_vec_info loop_vinfo)
1444 {
1445   struct loop *loop;
1446   basic_block *bbs;
1447   int nbbs;
1448   block_stmt_iterator si;
1449   int j;
1450
1451   if (!loop_vinfo)
1452     return;
1453
1454   loop = LOOP_VINFO_LOOP (loop_vinfo);
1455
1456   bbs = LOOP_VINFO_BBS (loop_vinfo);
1457   nbbs = loop->num_nodes;
1458
1459   for (j = 0; j < nbbs; j++)
1460     {
1461       basic_block bb = bbs[j];
1462       tree phi;
1463       stmt_vec_info stmt_info;
1464
1465       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1466         {
1467           stmt_ann_t ann = stmt_ann (phi);
1468
1469           stmt_info = vinfo_for_stmt (phi);
1470           free (stmt_info);
1471           set_stmt_info (ann, NULL);
1472         }
1473
1474       for (si = bsi_start (bb); !bsi_end_p (si); )
1475         {
1476           tree stmt = bsi_stmt (si);
1477           stmt_ann_t ann = stmt_ann (stmt);
1478           stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1479
1480           if (stmt_info)
1481             {
1482               /* Check if this is a "pattern stmt" (introduced by the
1483                  vectorizer during the pattern recognition pass).  */
1484               bool remove_stmt_p = false;
1485               tree orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
1486               if (orig_stmt)
1487                 {
1488                   stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
1489                   if (orig_stmt_info
1490                       && STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
1491                     remove_stmt_p = true;
1492                 }
1493
1494               /* Free stmt_vec_info.  */
1495               VEC_free (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmt_info));
1496               free (stmt_info);
1497               set_stmt_info (ann, NULL);
1498
1499               /* Remove dead "pattern stmts".  */
1500               if (remove_stmt_p)
1501                 bsi_remove (&si, true);
1502             }
1503           bsi_next (&si);
1504         }
1505     }
1506
1507   free (LOOP_VINFO_BBS (loop_vinfo));
1508   free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
1509   free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
1510   VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
1511
1512   free (loop_vinfo);
1513 }
1514
1515
1516 /* Function vect_force_dr_alignment_p.
1517
1518    Returns whether the alignment of a DECL can be forced to be aligned
1519    on ALIGNMENT bit boundary.  */
1520
1521 bool
1522 vect_can_force_dr_alignment_p (tree decl, unsigned int alignment)
1523 {
1524   if (TREE_CODE (decl) != VAR_DECL)
1525     return false;
1526
1527   if (DECL_EXTERNAL (decl))
1528     return false;
1529
1530   if (TREE_ASM_WRITTEN (decl))
1531     return false;
1532
1533   if (TREE_STATIC (decl))
1534     return (alignment <= MAX_OFILE_ALIGNMENT);
1535   else
1536     /* This is not 100% correct.  The absolute correct stack alignment
1537        is STACK_BOUNDARY.  We're supposed to hope, but not assume, that
1538        PREFERRED_STACK_BOUNDARY is honored by all translation units.
1539        However, until someone implements forced stack alignment, SSE
1540        isn't really usable without this.  */
1541     return (alignment <= PREFERRED_STACK_BOUNDARY);
1542 }
1543
1544
1545 /* Function get_vectype_for_scalar_type.
1546
1547    Returns the vector type corresponding to SCALAR_TYPE as supported
1548    by the target.  */
1549
1550 tree
1551 get_vectype_for_scalar_type (tree scalar_type)
1552 {
1553   enum machine_mode inner_mode = TYPE_MODE (scalar_type);
1554   int nbytes = GET_MODE_SIZE (inner_mode);
1555   int nunits;
1556   tree vectype;
1557
1558   if (nbytes == 0 || nbytes >= UNITS_PER_SIMD_WORD)
1559     return NULL_TREE;
1560
1561   /* FORNOW: Only a single vector size per target (UNITS_PER_SIMD_WORD)
1562      is expected.  */
1563   nunits = UNITS_PER_SIMD_WORD / nbytes;
1564
1565   vectype = build_vector_type (scalar_type, nunits);
1566   if (vect_print_dump_info (REPORT_DETAILS))
1567     {
1568       fprintf (vect_dump, "get vectype with %d units of type ", nunits);
1569       print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
1570     }
1571
1572   if (!vectype)
1573     return NULL_TREE;
1574
1575   if (vect_print_dump_info (REPORT_DETAILS))
1576     {
1577       fprintf (vect_dump, "vectype: ");
1578       print_generic_expr (vect_dump, vectype, TDF_SLIM);
1579     }
1580
1581   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
1582       && !INTEGRAL_MODE_P (TYPE_MODE (vectype)))
1583     {
1584       if (vect_print_dump_info (REPORT_DETAILS))
1585         fprintf (vect_dump, "mode not supported by target.");
1586       return NULL_TREE;
1587     }
1588
1589   return vectype;
1590 }
1591
1592
1593 /* Function vect_supportable_dr_alignment
1594
1595    Return whether the data reference DR is supported with respect to its
1596    alignment.  */
1597
1598 enum dr_alignment_support
1599 vect_supportable_dr_alignment (struct data_reference *dr)
1600 {
1601   tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
1602   enum machine_mode mode = (int) TYPE_MODE (vectype);
1603
1604   if (aligned_access_p (dr))
1605     return dr_aligned;
1606
1607   /* Possibly unaligned access.  */
1608
1609   if (DR_IS_READ (dr))
1610     {
1611       if (vec_realign_load_optab->handlers[mode].insn_code != CODE_FOR_nothing
1612           && (!targetm.vectorize.builtin_mask_for_load
1613               || targetm.vectorize.builtin_mask_for_load ()))
1614         return dr_unaligned_software_pipeline;
1615
1616       if (movmisalign_optab->handlers[mode].insn_code != CODE_FOR_nothing)
1617         /* Can't software pipeline the loads, but can at least do them.  */
1618         return dr_unaligned_supported;
1619     }
1620
1621   /* Unsupported.  */
1622   return dr_unaligned_unsupported;
1623 }
1624
1625
1626 /* Function vect_is_simple_use.
1627
1628    Input:
1629    LOOP - the loop that is being vectorized.
1630    OPERAND - operand of a stmt in LOOP.
1631    DEF - the defining stmt in case OPERAND is an SSA_NAME.
1632
1633    Returns whether a stmt with OPERAND can be vectorized.
1634    Supportable operands are constants, loop invariants, and operands that are
1635    defined by the current iteration of the loop. Unsupportable operands are
1636    those that are defined by a previous iteration of the loop (as is the case
1637    in reduction/induction computations).  */
1638
1639 bool
1640 vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
1641                     tree *def, enum vect_def_type *dt)
1642 {
1643   basic_block bb;
1644   stmt_vec_info stmt_vinfo;
1645   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
1646
1647   *def_stmt = NULL_TREE;
1648   *def = NULL_TREE;
1649
1650   if (vect_print_dump_info (REPORT_DETAILS))
1651     {
1652       fprintf (vect_dump, "vect_is_simple_use: operand ");
1653       print_generic_expr (vect_dump, operand, TDF_SLIM);
1654     }
1655
1656   if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
1657     {
1658       *dt = vect_constant_def;
1659       return true;
1660     }
1661
1662   if (TREE_CODE (operand) != SSA_NAME)
1663     {
1664       if (vect_print_dump_info (REPORT_DETAILS))
1665         fprintf (vect_dump, "not ssa-name.");
1666       return false;
1667     }
1668
1669   *def_stmt = SSA_NAME_DEF_STMT (operand);
1670   if (*def_stmt == NULL_TREE )
1671     {
1672       if (vect_print_dump_info (REPORT_DETAILS))
1673         fprintf (vect_dump, "no def_stmt.");
1674       return false;
1675     }
1676
1677   if (vect_print_dump_info (REPORT_DETAILS))
1678     {
1679       fprintf (vect_dump, "def_stmt: ");
1680       print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
1681     }
1682
1683   /* empty stmt is expected only in case of a function argument.
1684      (Otherwise - we expect a phi_node or a GIMPLE_MODIFY_STMT).  */
1685   if (IS_EMPTY_STMT (*def_stmt))
1686     {
1687       tree arg = TREE_OPERAND (*def_stmt, 0);
1688       if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
1689         {
1690           *def = operand;
1691           *dt = vect_invariant_def;
1692           return true;
1693         }
1694
1695       if (vect_print_dump_info (REPORT_DETAILS))
1696         fprintf (vect_dump, "Unexpected empty stmt.");
1697       return false;
1698     }
1699
1700   bb = bb_for_stmt (*def_stmt);
1701   if (!flow_bb_inside_loop_p (loop, bb))
1702     *dt = vect_invariant_def;
1703   else
1704     {
1705       stmt_vinfo = vinfo_for_stmt (*def_stmt);
1706       *dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
1707     }
1708
1709   if (*dt == vect_unknown_def_type)
1710     {
1711       if (vect_print_dump_info (REPORT_DETAILS))
1712         fprintf (vect_dump, "Unsupported pattern.");
1713       return false;
1714     }
1715
1716   /* stmts inside the loop that have been identified as performing
1717      a reduction operation cannot have uses in the loop.  */
1718   if (*dt == vect_reduction_def && TREE_CODE (*def_stmt) != PHI_NODE)
1719     {
1720       if (vect_print_dump_info (REPORT_DETAILS))
1721         fprintf (vect_dump, "reduction used in loop.");
1722       return false;
1723     }
1724
1725   if (vect_print_dump_info (REPORT_DETAILS))
1726     fprintf (vect_dump, "type of def: %d.",*dt);
1727
1728   switch (TREE_CODE (*def_stmt))
1729     {
1730     case PHI_NODE:
1731       *def = PHI_RESULT (*def_stmt);
1732       gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
1733                   || *dt == vect_invariant_def);
1734       break;
1735
1736     case GIMPLE_MODIFY_STMT:
1737       *def = GIMPLE_STMT_OPERAND (*def_stmt, 0);
1738       gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def);
1739       break;
1740
1741     default:
1742       if (vect_print_dump_info (REPORT_DETAILS))
1743         fprintf (vect_dump, "unsupported defining stmt: ");
1744       return false;
1745     }
1746
1747   if (*dt == vect_induction_def)
1748     {
1749       if (vect_print_dump_info (REPORT_DETAILS))
1750         fprintf (vect_dump, "induction not supported.");
1751       return false;
1752     }
1753
1754   return true;
1755 }
1756
1757
1758 /* Function supportable_widening_operation
1759
1760    Check whether an operation represented by the code CODE is a
1761    widening operation that is supported by the target platform in
1762    vector form (i.e., when operating on arguments of type VECTYPE).
1763
1764    The two kinds of widening operations we currently support are
1765    NOP and WIDEN_MULT. This function checks if these operations
1766    are supported by the target platform either directly (via vector
1767    tree-codes), or via target builtins.
1768
1769    Output:
1770    - CODE1 and CODE2 are codes of vector operations to be used when
1771    vectorizing the operation, if available.
1772    - DECL1 and DECL2 are decls of target builtin functions to be used
1773    when vectorizing the operation, if available. In this case,
1774    CODE1 and CODE2 are CALL_EXPR.  */
1775
1776 bool
1777 supportable_widening_operation (enum tree_code code, tree stmt, tree vectype,
1778                                 tree *decl1, tree *decl2,
1779                                 enum tree_code *code1, enum tree_code *code2)
1780 {
1781   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1782   bool ordered_p;
1783   enum machine_mode vec_mode;
1784   enum insn_code icode1, icode2;
1785   optab optab1, optab2;
1786   tree expr = GIMPLE_STMT_OPERAND (stmt, 1);
1787   tree type = TREE_TYPE (expr);
1788   tree wide_vectype = get_vectype_for_scalar_type (type);
1789   enum tree_code c1, c2;
1790
1791   /* The result of a vectorized widening operation usually requires two vectors
1792      (because the widened results do not fit int one vector). The generated
1793      vector results would normally be expected to be generated in the same
1794      order as in the original scalar computation. i.e. if 8 results are
1795      generated in each vector iteration, they are to be organized as follows:
1796         vect1: [res1,res2,res3,res4], vect2: [res5,res6,res7,res8].
1797
1798      However, in the special case that the result of the widening operation is
1799      used in a reduction computation only, the order doesn't matter (because
1800      when vectorizing a reduction we change the order of the computation).
1801      Some targets can take advantage of this and generate more efficient code.
1802      For example, targets like Altivec, that support widen_mult using a sequence
1803      of {mult_even,mult_odd} generate the following vectors:
1804         vect1: [res1,res3,res5,res7], vect2: [res2,res4,res6,res8].  */
1805
1806    if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction)
1807      ordered_p = false;
1808    else
1809      ordered_p = true;
1810
1811   if (!ordered_p
1812       && code == WIDEN_MULT_EXPR
1813       && targetm.vectorize.builtin_mul_widen_even
1814       && targetm.vectorize.builtin_mul_widen_even (vectype)
1815       && targetm.vectorize.builtin_mul_widen_odd
1816       && targetm.vectorize.builtin_mul_widen_odd (vectype))
1817     {
1818       if (vect_print_dump_info (REPORT_DETAILS))
1819         fprintf (vect_dump, "Unordered widening operation detected.");
1820
1821       *code1 = *code2 = CALL_EXPR;
1822       *decl1 = targetm.vectorize.builtin_mul_widen_even (vectype);
1823       *decl2 = targetm.vectorize.builtin_mul_widen_odd (vectype);
1824       return true;
1825     }
1826
1827   switch (code)
1828     {
1829     case WIDEN_MULT_EXPR:
1830       if (BYTES_BIG_ENDIAN)
1831         {
1832           c1 = VEC_WIDEN_MULT_HI_EXPR;
1833           c2 = VEC_WIDEN_MULT_LO_EXPR;
1834         }
1835       else
1836         {
1837           c2 = VEC_WIDEN_MULT_HI_EXPR;
1838           c1 = VEC_WIDEN_MULT_LO_EXPR;
1839         }
1840       break;
1841
1842     case NOP_EXPR:
1843       if (BYTES_BIG_ENDIAN)
1844         {
1845           c1 = VEC_UNPACK_HI_EXPR;
1846           c2 = VEC_UNPACK_LO_EXPR;
1847         }
1848       else
1849         {
1850           c2 = VEC_UNPACK_HI_EXPR;
1851           c1 = VEC_UNPACK_LO_EXPR;
1852         }
1853       break;
1854
1855     default:
1856       gcc_unreachable ();
1857     }
1858
1859   *code1 = c1;
1860   *code2 = c2;
1861   optab1 = optab_for_tree_code (c1, vectype);
1862   optab2 = optab_for_tree_code (c2, vectype);
1863
1864   if (!optab1 || !optab2)
1865     return false;
1866
1867   vec_mode = TYPE_MODE (vectype);
1868   if ((icode1 = optab1->handlers[(int) vec_mode].insn_code) == CODE_FOR_nothing
1869       || insn_data[icode1].operand[0].mode != TYPE_MODE (wide_vectype)
1870       || (icode2 = optab2->handlers[(int) vec_mode].insn_code)
1871                                                         == CODE_FOR_nothing
1872       || insn_data[icode2].operand[0].mode != TYPE_MODE (wide_vectype))
1873     return false;
1874
1875   return true;
1876 }
1877
1878
1879 /* Function reduction_code_for_scalar_code
1880
1881    Input:
1882    CODE - tree_code of a reduction operations.
1883
1884    Output:
1885    REDUC_CODE - the corresponding tree-code to be used to reduce the
1886       vector of partial results into a single scalar result (which
1887       will also reside in a vector).
1888
1889    Return TRUE if a corresponding REDUC_CODE was found, FALSE otherwise.  */
1890
1891 bool
1892 reduction_code_for_scalar_code (enum tree_code code,
1893                                 enum tree_code *reduc_code)
1894 {
1895   switch (code)
1896   {
1897   case MAX_EXPR:
1898     *reduc_code = REDUC_MAX_EXPR;
1899     return true;
1900
1901   case MIN_EXPR:
1902     *reduc_code = REDUC_MIN_EXPR;
1903     return true;
1904
1905   case PLUS_EXPR:
1906     *reduc_code = REDUC_PLUS_EXPR;
1907     return true;
1908
1909   default:
1910     return false;
1911   }
1912 }
1913
1914
1915 /* Function vect_is_simple_reduction
1916
1917    Detect a cross-iteration def-use cucle that represents a simple
1918    reduction computation. We look for the following pattern:
1919
1920    loop_header:
1921      a1 = phi < a0, a2 >
1922      a3 = ...
1923      a2 = operation (a3, a1)
1924
1925    such that:
1926    1. operation is commutative and associative and it is safe to
1927       change the order of the computation.
1928    2. no uses for a2 in the loop (a2 is used out of the loop)
1929    3. no uses of a1 in the loop besides the reduction operation.
1930
1931    Condition 1 is tested here.
1932    Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.  */
1933
1934 tree
1935 vect_is_simple_reduction (struct loop *loop, tree phi)
1936 {
1937   edge latch_e = loop_latch_edge (loop);
1938   tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
1939   tree def_stmt, def1, def2;
1940   enum tree_code code;
1941   int op_type;
1942   tree operation, op1, op2;
1943   tree type;
1944
1945   if (TREE_CODE (loop_arg) != SSA_NAME)
1946     {
1947       if (vect_print_dump_info (REPORT_DETAILS))
1948         {
1949           fprintf (vect_dump, "reduction: not ssa_name: ");
1950           print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
1951         }
1952       return NULL_TREE;
1953     }
1954
1955   def_stmt = SSA_NAME_DEF_STMT (loop_arg);
1956   if (!def_stmt)
1957     {
1958       if (vect_print_dump_info (REPORT_DETAILS))
1959         fprintf (vect_dump, "reduction: no def_stmt.");
1960       return NULL_TREE;
1961     }
1962
1963   if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
1964     {
1965       if (vect_print_dump_info (REPORT_DETAILS))
1966         {
1967           print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
1968         }
1969       return NULL_TREE;
1970     }
1971
1972   operation = GIMPLE_STMT_OPERAND (def_stmt, 1);
1973   code = TREE_CODE (operation);
1974   if (!commutative_tree_code (code) || !associative_tree_code (code))
1975     {
1976       if (vect_print_dump_info (REPORT_DETAILS))
1977         {
1978           fprintf (vect_dump, "reduction: not commutative/associative: ");
1979           print_generic_expr (vect_dump, operation, TDF_SLIM);
1980         }
1981       return NULL_TREE;
1982     }
1983
1984   op_type = TREE_CODE_LENGTH (code);
1985   if (op_type != binary_op)
1986     {
1987       if (vect_print_dump_info (REPORT_DETAILS))
1988         {
1989           fprintf (vect_dump, "reduction: not binary operation: ");
1990           print_generic_expr (vect_dump, operation, TDF_SLIM);
1991         }
1992       return NULL_TREE;
1993     }
1994
1995   op1 = TREE_OPERAND (operation, 0);
1996   op2 = TREE_OPERAND (operation, 1);
1997   if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
1998     {
1999       if (vect_print_dump_info (REPORT_DETAILS))
2000         {
2001           fprintf (vect_dump, "reduction: uses not ssa_names: ");
2002           print_generic_expr (vect_dump, operation, TDF_SLIM);
2003         }
2004       return NULL_TREE;
2005     }
2006
2007   /* Check that it's ok to change the order of the computation.  */
2008   type = TREE_TYPE (operation);
2009   if (TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op1))
2010       || TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op2)))
2011     {
2012       if (vect_print_dump_info (REPORT_DETAILS))
2013         {
2014           fprintf (vect_dump, "reduction: multiple types: operation type: ");
2015           print_generic_expr (vect_dump, type, TDF_SLIM);
2016           fprintf (vect_dump, ", operands types: ");
2017           print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
2018           fprintf (vect_dump, ",");
2019           print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
2020         }
2021       return NULL_TREE;
2022     }
2023
2024   /* CHECKME: check for !flag_finite_math_only too?  */
2025   if (SCALAR_FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
2026     {
2027       /* Changing the order of operations changes the semantics.  */
2028       if (vect_print_dump_info (REPORT_DETAILS))
2029         {
2030           fprintf (vect_dump, "reduction: unsafe fp math optimization: ");
2031           print_generic_expr (vect_dump, operation, TDF_SLIM);
2032         }
2033       return NULL_TREE;
2034     }
2035   else if (INTEGRAL_TYPE_P (type) && !TYPE_UNSIGNED (type) && flag_trapv)
2036     {
2037       /* Changing the order of operations changes the semantics.  */
2038       if (vect_print_dump_info (REPORT_DETAILS))
2039         {
2040           fprintf (vect_dump, "reduction: unsafe int math optimization: ");
2041           print_generic_expr (vect_dump, operation, TDF_SLIM);
2042         }
2043       return NULL_TREE;
2044     }
2045
2046   /* reduction is safe. we're dealing with one of the following:
2047      1) integer arithmetic and no trapv
2048      2) floating point arithmetic, and special flags permit this optimization.
2049    */
2050   def1 = SSA_NAME_DEF_STMT (op1);
2051   def2 = SSA_NAME_DEF_STMT (op2);
2052   if (!def1 || !def2)
2053     {
2054       if (vect_print_dump_info (REPORT_DETAILS))
2055         {
2056           fprintf (vect_dump, "reduction: no defs for operands: ");
2057           print_generic_expr (vect_dump, operation, TDF_SLIM);
2058         }
2059       return NULL_TREE;
2060     }
2061
2062   if (TREE_CODE (def1) == GIMPLE_MODIFY_STMT
2063       && flow_bb_inside_loop_p (loop, bb_for_stmt (def1))
2064       && def2 == phi)
2065     {
2066       if (vect_print_dump_info (REPORT_DETAILS))
2067         {
2068           fprintf (vect_dump, "detected reduction:");
2069           print_generic_expr (vect_dump, operation, TDF_SLIM);
2070         }
2071       return def_stmt;
2072     }
2073   else if (TREE_CODE (def2) == GIMPLE_MODIFY_STMT
2074       && flow_bb_inside_loop_p (loop, bb_for_stmt (def2))
2075       && def1 == phi)
2076     {
2077       /* Swap operands (just for simplicity - so that the rest of the code
2078          can assume that the reduction variable is always the last (second)
2079          argument).  */
2080       if (vect_print_dump_info (REPORT_DETAILS))
2081         {
2082           fprintf (vect_dump, "detected reduction: need to swap operands:");
2083           print_generic_expr (vect_dump, operation, TDF_SLIM);
2084         }
2085       swap_tree_operands (def_stmt, &TREE_OPERAND (operation, 0),
2086                                     &TREE_OPERAND (operation, 1));
2087       return def_stmt;
2088     }
2089   else
2090     {
2091       if (vect_print_dump_info (REPORT_DETAILS))
2092         {
2093           fprintf (vect_dump, "reduction: unknown pattern.");
2094           print_generic_expr (vect_dump, operation, TDF_SLIM);
2095         }
2096       return NULL_TREE;
2097     }
2098 }
2099
2100
2101 /* Function vect_is_simple_iv_evolution.
2102
2103    FORNOW: A simple evolution of an induction variables in the loop is
2104    considered a polynomial evolution with constant step.  */
2105
2106 bool
2107 vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
2108                              tree * step)
2109 {
2110   tree init_expr;
2111   tree step_expr;
2112
2113   tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
2114
2115   /* When there is no evolution in this loop, the evolution function
2116      is not "simple".  */
2117   if (evolution_part == NULL_TREE)
2118     return false;
2119
2120   /* When the evolution is a polynomial of degree >= 2
2121      the evolution function is not "simple".  */
2122   if (tree_is_chrec (evolution_part))
2123     return false;
2124
2125   step_expr = evolution_part;
2126   init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
2127                                                            loop_nb));
2128
2129   if (vect_print_dump_info (REPORT_DETAILS))
2130     {
2131       fprintf (vect_dump, "step: ");
2132       print_generic_expr (vect_dump, step_expr, TDF_SLIM);
2133       fprintf (vect_dump, ",  init: ");
2134       print_generic_expr (vect_dump, init_expr, TDF_SLIM);
2135     }
2136
2137   *init = init_expr;
2138   *step = step_expr;
2139
2140   if (TREE_CODE (step_expr) != INTEGER_CST)
2141     {
2142       if (vect_print_dump_info (REPORT_DETAILS))
2143         fprintf (vect_dump, "step unknown.");
2144       return false;
2145     }
2146
2147   return true;
2148 }
2149
2150
2151 /* Function vectorize_loops.
2152
2153    Entry Point to loop vectorization phase.  */
2154
2155 unsigned
2156 vectorize_loops (void)
2157 {
2158   unsigned int i;
2159   unsigned int num_vectorized_loops = 0;
2160
2161   /* Fix the verbosity level if not defined explicitly by the user.  */
2162   vect_set_dump_settings ();
2163
2164   /* Allocate the bitmap that records which virtual variables that
2165      need to be renamed.  */
2166   vect_vnames_to_rename = BITMAP_ALLOC (NULL);
2167
2168   /*  ----------- Analyze loops. -----------  */
2169
2170   /* If some loop was duplicated, it gets bigger number
2171      than all previously defined loops. This fact allows us to run
2172      only over initial loops skipping newly generated ones.  */
2173   vect_loops_num = current_loops->num;
2174   for (i = 1; i < vect_loops_num; i++)
2175     {
2176       loop_vec_info loop_vinfo;
2177       struct loop *loop = current_loops->parray[i];
2178
2179       if (!loop)
2180         continue;
2181
2182       vect_loop_location = find_loop_location (loop);
2183       loop_vinfo = vect_analyze_loop (loop);
2184       loop->aux = loop_vinfo;
2185
2186       if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
2187         continue;
2188
2189       vect_transform_loop (loop_vinfo);
2190       num_vectorized_loops++;
2191     }
2192   vect_loop_location = UNKNOWN_LOC;
2193
2194   if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS))
2195     fprintf (vect_dump, "vectorized %u loops in function.\n",
2196              num_vectorized_loops);
2197
2198   /*  ----------- Finalize. -----------  */
2199
2200   BITMAP_FREE (vect_vnames_to_rename);
2201
2202   for (i = 1; i < vect_loops_num; i++)
2203     {
2204       struct loop *loop = current_loops->parray[i];
2205       loop_vec_info loop_vinfo;
2206
2207       if (!loop)
2208         continue;
2209       loop_vinfo = loop->aux;
2210       destroy_loop_vec_info (loop_vinfo);
2211       loop->aux = NULL;
2212     }
2213
2214   return num_vectorized_loops > 0 ? TODO_cleanup_cfg : 0;
2215 }