gcc/tree-vect-stmts.c

   1 /* Statement Analysis and Transformation for Vectorization
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Dorit Naishlos <dorit@il.ibm.com>
   5    and Ira Rosen <irar@il.ibm.com>
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it under
  10 the terms of the GNU General Public License as published by the Free
  11 Software Foundation; either version 3, or (at your option) any later
  12 version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  17 for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "target.h"
  30 #include "basic-block.h"
  31 #include "tree-pretty-print.h"
  32 #include "gimple-pretty-print.h"
  33 #include "tree-flow.h"
  34 #include "tree-dump.h"
  35 #include "cfgloop.h"
  36 #include "cfglayout.h"
  37 #include "expr.h"
  38 #include "recog.h"
  39 #include "optabs.h"
  40 #include "diagnostic-core.h"
  41 #include "toplev.h"
  42 #include "tree-vectorizer.h"
  43 #include "langhooks.h"
  44
  45
  46 /* Utility functions used by vect_mark_stmts_to_be_vectorized.  */
  47
  48 /* Function vect_mark_relevant.
  49
  50    Mark STMT as "relevant for vectorization" and add it to WORKLIST.  */
  51
  52 static void
  53 vect_mark_relevant (VEC(gimple,heap) **worklist, gimple stmt,
  54                     enum vect_relevant relevant, bool live_p)
  55 {
  56   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
  57   enum vect_relevant save_relevant = STMT_VINFO_RELEVANT (stmt_info);
  58   bool save_live_p = STMT_VINFO_LIVE_P (stmt_info);
  59
  60   if (vect_print_dump_info (REPORT_DETAILS))
  61     fprintf (vect_dump, "mark relevant %d, live %d.", relevant, live_p);
  62
  63   if (STMT_VINFO_IN_PATTERN_P (stmt_info))
  64     {
  65       gimple pattern_stmt;
  66
  67       /* This is the last stmt in a sequence that was detected as a
  68          pattern that can potentially be vectorized.  Don't mark the stmt
  69          as relevant/live because it's not going to be vectorized.
  70          Instead mark the pattern-stmt that replaces it.  */
  71
  72       pattern_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
  73
  74       if (vect_print_dump_info (REPORT_DETAILS))
  75         fprintf (vect_dump, "last stmt in pattern. don't mark relevant/live.");
  76       stmt_info = vinfo_for_stmt (pattern_stmt);
  77       gcc_assert (STMT_VINFO_RELATED_STMT (stmt_info) == stmt);
  78       save_relevant = STMT_VINFO_RELEVANT (stmt_info);
  79       save_live_p = STMT_VINFO_LIVE_P (stmt_info);
  80       stmt = pattern_stmt;
  81     }
  82
  83   STMT_VINFO_LIVE_P (stmt_info) |= live_p;
  84   if (relevant > STMT_VINFO_RELEVANT (stmt_info))
  85     STMT_VINFO_RELEVANT (stmt_info) = relevant;
  86
  87   if (STMT_VINFO_RELEVANT (stmt_info) == save_relevant
  88       && STMT_VINFO_LIVE_P (stmt_info) == save_live_p)
  89     {
  90       if (vect_print_dump_info (REPORT_DETAILS))
  91         fprintf (vect_dump, "already marked relevant/live.");
  92       return;
  93     }
  94
  95   VEC_safe_push (gimple, heap, *worklist, stmt);
  96 }
  97
  98
  99 /* Function vect_stmt_relevant_p.
 100
 101    Return true if STMT in loop that is represented by LOOP_VINFO is
 102    "relevant for vectorization".
 103
 104    A stmt is considered "relevant for vectorization" if:
 105    - it has uses outside the loop.
 106    - it has vdefs (it alters memory).
 107    - control stmts in the loop (except for the exit condition).
 108
 109    CHECKME: what other side effects would the vectorizer allow?  */
 110
 111 static bool
 112 vect_stmt_relevant_p (gimple stmt, loop_vec_info loop_vinfo,
 113                       enum vect_relevant *relevant, bool *live_p)
 114 {
 115   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 116   ssa_op_iter op_iter;
 117   imm_use_iterator imm_iter;
 118   use_operand_p use_p;
 119   def_operand_p def_p;
 120
 121   *relevant = vect_unused_in_scope;
 122   *live_p = false;
 123
 124   /* cond stmt other than loop exit cond.  */
 125   if (is_ctrl_stmt (stmt)
 126       && STMT_VINFO_TYPE (vinfo_for_stmt (stmt))
 127          != loop_exit_ctrl_vec_info_type)
 128     *relevant = vect_used_in_scope;
 129
 130   /* changing memory.  */
 131   if (gimple_code (stmt) != GIMPLE_PHI)
 132     if (gimple_vdef (stmt))
 133       {
 134         if (vect_print_dump_info (REPORT_DETAILS))
 135           fprintf (vect_dump, "vec_stmt_relevant_p: stmt has vdefs.");
 136         *relevant = vect_used_in_scope;
 137       }
 138
 139   /* uses outside the loop.  */
 140   FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, op_iter, SSA_OP_DEF)
 141     {
 142       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
 143         {
 144           basic_block bb = gimple_bb (USE_STMT (use_p));
 145           if (!flow_bb_inside_loop_p (loop, bb))
 146             {
 147               if (vect_print_dump_info (REPORT_DETAILS))
 148                 fprintf (vect_dump, "vec_stmt_relevant_p: used out of loop.");
 149
 150               if (is_gimple_debug (USE_STMT (use_p)))
 151                 continue;
 152
 153               /* We expect all such uses to be in the loop exit phis
 154                  (because of loop closed form)   */
 155               gcc_assert (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI);
 156               gcc_assert (bb == single_exit (loop)->dest);
 157
 158               *live_p = true;
 159             }
 160         }
 161     }
 162
 163   return (*live_p || *relevant);
 164 }
 165
 166
 167 /* Function exist_non_indexing_operands_for_use_p
 168
 169    USE is one of the uses attached to STMT.  Check if USE is
 170    used in STMT for anything other than indexing an array.  */
 171
 172 static bool
 173 exist_non_indexing_operands_for_use_p (tree use, gimple stmt)
 174 {
 175   tree operand;
 176   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 177
 178   /* USE corresponds to some operand in STMT.  If there is no data
 179      reference in STMT, then any operand that corresponds to USE
 180      is not indexing an array.  */
 181   if (!STMT_VINFO_DATA_REF (stmt_info))
 182     return true;
 183
 184   /* STMT has a data_ref. FORNOW this means that its of one of
 185      the following forms:
 186      -1- ARRAY_REF = var
 187      -2- var = ARRAY_REF
 188      (This should have been verified in analyze_data_refs).
 189
 190      'var' in the second case corresponds to a def, not a use,
 191      so USE cannot correspond to any operands that are not used
 192      for array indexing.
 193
 194      Therefore, all we need to check is if STMT falls into the
 195      first case, and whether var corresponds to USE.  */
 196
 197   if (!gimple_assign_copy_p (stmt))
 198     return false;
 199   if (TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME)
 200     return false;
 201   operand = gimple_assign_rhs1 (stmt);
 202   if (TREE_CODE (operand) != SSA_NAME)
 203     return false;
 204
 205   if (operand == use)
 206     return true;
 207
 208   return false;
 209 }
 210
 211
 212 /*
 213    Function process_use.
 214
 215    Inputs:
 216    - a USE in STMT in a loop represented by LOOP_VINFO
 217    - LIVE_P, RELEVANT - enum values to be set in the STMT_VINFO of the stmt
 218      that defined USE.  This is done by calling mark_relevant and passing it
 219      the WORKLIST (to add DEF_STMT to the WORKLIST in case it is relevant).
 220
 221    Outputs:
 222    Generally, LIVE_P and RELEVANT are used to define the liveness and
 223    relevance info of the DEF_STMT of this USE:
 224        STMT_VINFO_LIVE_P (DEF_STMT_info) <-- live_p
 225        STMT_VINFO_RELEVANT (DEF_STMT_info) <-- relevant
 226    Exceptions:
 227    - case 1: If USE is used only for address computations (e.g. array indexing),
 228    which does not need to be directly vectorized, then the liveness/relevance
 229    of the respective DEF_STMT is left unchanged.
 230    - case 2: If STMT is a reduction phi and DEF_STMT is a reduction stmt, we
 231    skip DEF_STMT cause it had already been processed.
 232    - case 3: If DEF_STMT and STMT are in different nests, then  "relevant" will
 233    be modified accordingly.
 234
 235    Return true if everything is as expected. Return false otherwise.  */
 236
 237 static bool
 238 process_use (gimple stmt, tree use, loop_vec_info loop_vinfo, bool live_p,
 239              enum vect_relevant relevant, VEC(gimple,heap) **worklist)
 240 {
 241   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 242   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 243   stmt_vec_info dstmt_vinfo;
 244   basic_block bb, def_bb;
 245   tree def;
 246   gimple def_stmt;
 247   enum vect_def_type dt;
 248
 249   /* case 1: we are only interested in uses that need to be vectorized.  Uses
 250      that are used for address computation are not considered relevant.  */
 251   if (!exist_non_indexing_operands_for_use_p (use, stmt))
 252      return true;
 253
 254   if (!vect_is_simple_use (use, loop_vinfo, NULL, &def_stmt, &def, &dt))
 255     {
 256       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
 257         fprintf (vect_dump, "not vectorized: unsupported use in stmt.");
 258       return false;
 259     }
 260
 261   if (!def_stmt || gimple_nop_p (def_stmt))
 262     return true;
 263
 264   def_bb = gimple_bb (def_stmt);
 265   if (!flow_bb_inside_loop_p (loop, def_bb))
 266     {
 267       if (vect_print_dump_info (REPORT_DETAILS))
 268         fprintf (vect_dump, "def_stmt is out of loop.");
 269       return true;
 270     }
 271
 272   /* case 2: A reduction phi (STMT) defined by a reduction stmt (DEF_STMT).
 273      DEF_STMT must have already been processed, because this should be the
 274      only way that STMT, which is a reduction-phi, was put in the worklist,
 275      as there should be no other uses for DEF_STMT in the loop.  So we just
 276      check that everything is as expected, and we are done.  */
 277   dstmt_vinfo = vinfo_for_stmt (def_stmt);
 278   bb = gimple_bb (stmt);
 279   if (gimple_code (stmt) == GIMPLE_PHI
 280       && STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
 281       && gimple_code (def_stmt) != GIMPLE_PHI
 282       && STMT_VINFO_DEF_TYPE (dstmt_vinfo) == vect_reduction_def
 283       && bb->loop_father == def_bb->loop_father)
 284     {
 285       if (vect_print_dump_info (REPORT_DETAILS))
 286         fprintf (vect_dump, "reduc-stmt defining reduc-phi in the same nest.");
 287       if (STMT_VINFO_IN_PATTERN_P (dstmt_vinfo))
 288         dstmt_vinfo = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (dstmt_vinfo));
 289       gcc_assert (STMT_VINFO_RELEVANT (dstmt_vinfo) < vect_used_by_reduction);
 290       gcc_assert (STMT_VINFO_LIVE_P (dstmt_vinfo)
 291                   || STMT_VINFO_RELEVANT (dstmt_vinfo) > vect_unused_in_scope);
 292       return true;
 293     }
 294
 295   /* case 3a: outer-loop stmt defining an inner-loop stmt:
 296         outer-loop-header-bb:
 297                 d = def_stmt
 298         inner-loop:
 299                 stmt # use (d)
 300         outer-loop-tail-bb:
 301                 ...               */
 302   if (flow_loop_nested_p (def_bb->loop_father, bb->loop_father))
 303     {
 304       if (vect_print_dump_info (REPORT_DETAILS))
 305         fprintf (vect_dump, "outer-loop def-stmt defining inner-loop stmt.");
 306
 307       switch (relevant)
 308         {
 309         case vect_unused_in_scope:
 310           relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_nested_cycle) ?
 311                       vect_used_in_scope : vect_unused_in_scope;
 312           break;
 313
 314         case vect_used_in_outer_by_reduction:
 315           gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def);
 316           relevant = vect_used_by_reduction;
 317           break;
 318
 319         case vect_used_in_outer:
 320           gcc_assert (STMT_VINFO_DEF_TYPE (stmt_vinfo) != vect_reduction_def);
 321           relevant = vect_used_in_scope;
 322           break;
 323
 324         case vect_used_in_scope:
 325           break;
 326
 327         default:
 328           gcc_unreachable ();
 329         }
 330     }
 331
 332   /* case 3b: inner-loop stmt defining an outer-loop stmt:
 333         outer-loop-header-bb:
 334                 ...
 335         inner-loop:
 336                 d = def_stmt
 337         outer-loop-tail-bb (or outer-loop-exit-bb in double reduction):
 338                 stmt # use (d)          */
 339   else if (flow_loop_nested_p (bb->loop_father, def_bb->loop_father))
 340     {
 341       if (vect_print_dump_info (REPORT_DETAILS))
 342         fprintf (vect_dump, "inner-loop def-stmt defining outer-loop stmt.");
 343
 344       switch (relevant)
 345         {
 346         case vect_unused_in_scope:
 347           relevant = (STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_reduction_def
 348             || STMT_VINFO_DEF_TYPE (stmt_vinfo) == vect_double_reduction_def) ?
 349                       vect_used_in_outer_by_reduction : vect_unused_in_scope;
 350           break;
 351
 352         case vect_used_by_reduction:
 353           relevant = vect_used_in_outer_by_reduction;
 354           break;
 355
 356         case vect_used_in_scope:
 357           relevant = vect_used_in_outer;
 358           break;
 359
 360         default:
 361           gcc_unreachable ();
 362         }
 363     }
 364
 365   vect_mark_relevant (worklist, def_stmt, relevant, live_p);
 366   return true;
 367 }
 368
 369
 370 /* Function vect_mark_stmts_to_be_vectorized.
 371
 372    Not all stmts in the loop need to be vectorized. For example:
 373
 374      for i...
 375        for j...
 376    1.    T0 = i + j
 377    2.    T1 = a[T0]
 378
 379    3.    j = j + 1
 380
 381    Stmt 1 and 3 do not need to be vectorized, because loop control and
 382    addressing of vectorized data-refs are handled differently.
 383
 384    This pass detects such stmts.  */
 385
 386 bool
 387 vect_mark_stmts_to_be_vectorized (loop_vec_info loop_vinfo)
 388 {
 389   VEC(gimple,heap) *worklist;
 390   struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 391   basic_block *bbs = LOOP_VINFO_BBS (loop_vinfo);
 392   unsigned int nbbs = loop->num_nodes;
 393   gimple_stmt_iterator si;
 394   gimple stmt;
 395   unsigned int i;
 396   stmt_vec_info stmt_vinfo;
 397   basic_block bb;
 398   gimple phi;
 399   bool live_p;
 400   enum vect_relevant relevant, tmp_relevant;
 401   enum vect_def_type def_type;
 402
 403   if (vect_print_dump_info (REPORT_DETAILS))
 404     fprintf (vect_dump, "=== vect_mark_stmts_to_be_vectorized ===");
 405
 406   worklist = VEC_alloc (gimple, heap, 64);
 407
 408   /* 1. Init worklist.  */
 409   for (i = 0; i < nbbs; i++)
 410     {
 411       bb = bbs[i];
 412       for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
 413         {
 414           phi = gsi_stmt (si);
 415           if (vect_print_dump_info (REPORT_DETAILS))
 416             {
 417               fprintf (vect_dump, "init: phi relevant? ");
 418               print_gimple_stmt (vect_dump, phi, 0, TDF_SLIM);
 419             }
 420
 421           if (vect_stmt_relevant_p (phi, loop_vinfo, &relevant, &live_p))
 422             vect_mark_relevant (&worklist, phi, relevant, live_p);
 423         }
 424       for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
 425         {
 426           stmt = gsi_stmt (si);
 427           if (vect_print_dump_info (REPORT_DETAILS))
 428             {
 429               fprintf (vect_dump, "init: stmt relevant? ");
 430               print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 431             }
 432
 433           if (vect_stmt_relevant_p (stmt, loop_vinfo, &relevant, &live_p))
 434             vect_mark_relevant (&worklist, stmt, relevant, live_p);
 435         }
 436     }
 437
 438   /* 2. Process_worklist */
 439   while (VEC_length (gimple, worklist) > 0)
 440     {
 441       use_operand_p use_p;
 442       ssa_op_iter iter;
 443
 444       stmt = VEC_pop (gimple, worklist);
 445       if (vect_print_dump_info (REPORT_DETAILS))
 446         {
 447           fprintf (vect_dump, "worklist: examine stmt: ");
 448           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
 449         }
 450
 451       /* Examine the USEs of STMT. For each USE, mark the stmt that defines it
 452          (DEF_STMT) as relevant/irrelevant and live/dead according to the
 453          liveness and relevance properties of STMT.  */
 454       stmt_vinfo = vinfo_for_stmt (stmt);
 455       relevant = STMT_VINFO_RELEVANT (stmt_vinfo);
 456       live_p = STMT_VINFO_LIVE_P (stmt_vinfo);
 457
 458       /* Generally, the liveness and relevance properties of STMT are
 459          propagated as is to the DEF_STMTs of its USEs:
 460           live_p <-- STMT_VINFO_LIVE_P (STMT_VINFO)
 461           relevant <-- STMT_VINFO_RELEVANT (STMT_VINFO)
 462
 463          One exception is when STMT has been identified as defining a reduction
 464          variable; in this case we set the liveness/relevance as follows:
 465            live_p = false
 466            relevant = vect_used_by_reduction
 467          This is because we distinguish between two kinds of relevant stmts -
 468          those that are used by a reduction computation, and those that are
 469          (also) used by a regular computation.  This allows us later on to
 470          identify stmts that are used solely by a reduction, and therefore the
 471          order of the results that they produce does not have to be kept.  */
 472
 473       def_type = STMT_VINFO_DEF_TYPE (stmt_vinfo);
 474       tmp_relevant = relevant;
 475       switch (def_type)
 476         {
 477           case vect_reduction_def:
 478             switch (tmp_relevant)
 479               {
 480                 case vect_unused_in_scope:
 481                   relevant = vect_used_by_reduction;
 482                   break;
 483
 484                 case vect_used_by_reduction:
 485                   if (gimple_code (stmt) == GIMPLE_PHI)
 486                     break;
 487                   /* fall through */
 488
 489                 default:
 490                   if (vect_print_dump_info (REPORT_DETAILS))
 491                     fprintf (vect_dump, "unsupported use of reduction.");
 492
 493                   VEC_free (gimple, heap, worklist);
 494                   return false;
 495               }
 496
 497             live_p = false;
 498             break;
 499
 500           case vect_nested_cycle:
 501             if (tmp_relevant != vect_unused_in_scope
 502                 && tmp_relevant != vect_used_in_outer_by_reduction
 503                 && tmp_relevant != vect_used_in_outer)
 504               {
 505                 if (vect_print_dump_info (REPORT_DETAILS))
 506                   fprintf (vect_dump, "unsupported use of nested cycle.");
 507
 508                 VEC_free (gimple, heap, worklist);
 509                 return false;
 510               }
 511
 512             live_p = false;
 513             break;
 514
 515           case vect_double_reduction_def:
 516             if (tmp_relevant != vect_unused_in_scope
 517                 && tmp_relevant != vect_used_by_reduction)
 518               {
 519                 if (vect_print_dump_info (REPORT_DETAILS))
 520                   fprintf (vect_dump, "unsupported use of double reduction.");
 521
 522                 VEC_free (gimple, heap, worklist);
 523                 return false;
 524               }
 525
 526             live_p = false;
 527             break;
 528
 529           default:
 530             break;
 531         }
 532
 533       FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
 534         {
 535           tree op = USE_FROM_PTR (use_p);
 536           if (!process_use (stmt, op, loop_vinfo, live_p, relevant, &worklist))
 537             {
 538               VEC_free (gimple, heap, worklist);
 539               return false;
 540             }
 541         }
 542     } /* while worklist */
 543
 544   VEC_free (gimple, heap, worklist);
 545   return true;
 546 }
 547
 548
 549 /* Get cost by calling cost target builtin.  */
 550
 551 static inline
 552 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost)
 553 {
 554   tree dummy_type = NULL;
 555   int dummy = 0;
 556
 557   return targetm.vectorize.builtin_vectorization_cost (type_of_cost,
 558                                                        dummy_type, dummy);
 559 }
 560
 561
 562 /* Get cost for STMT.  */
 563
 564 int
 565 cost_for_stmt (gimple stmt)
 566 {
 567   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 568
 569   switch (STMT_VINFO_TYPE (stmt_info))
 570   {
 571   case load_vec_info_type:
 572     return vect_get_stmt_cost (scalar_load);
 573   case store_vec_info_type:
 574     return vect_get_stmt_cost (scalar_store);
 575   case op_vec_info_type:
 576   case condition_vec_info_type:
 577   case assignment_vec_info_type:
 578   case reduc_vec_info_type:
 579   case induc_vec_info_type:
 580   case type_promotion_vec_info_type:
 581   case type_demotion_vec_info_type:
 582   case type_conversion_vec_info_type:
 583   case call_vec_info_type:
 584     return vect_get_stmt_cost (scalar_stmt);
 585   case undef_vec_info_type:
 586   default:
 587     gcc_unreachable ();
 588   }
 589 }
 590
 591 /* Function vect_model_simple_cost.
 592
 593    Models cost for simple operations, i.e. those that only emit ncopies of a
 594    single op.  Right now, this does not account for multiple insns that could
 595    be generated for the single vector op.  We will handle that shortly.  */
 596
 597 void
 598 vect_model_simple_cost (stmt_vec_info stmt_info, int ncopies,
 599                         enum vect_def_type *dt, slp_tree slp_node)
 600 {
 601   int i;
 602   int inside_cost = 0, outside_cost = 0;
 603
 604   /* The SLP costs were already calculated during SLP tree build.  */
 605   if (PURE_SLP_STMT (stmt_info))
 606     return;
 607
 608   inside_cost = ncopies * vect_get_stmt_cost (vector_stmt);
 609
 610   /* FORNOW: Assuming maximum 2 args per stmts.  */
 611   for (i = 0; i < 2; i++)
 612     {
 613       if (dt[i] == vect_constant_def || dt[i] == vect_external_def)
 614         outside_cost += vect_get_stmt_cost (vector_stmt);
 615     }
 616
 617   if (vect_print_dump_info (REPORT_COST))
 618     fprintf (vect_dump, "vect_model_simple_cost: inside_cost = %d, "
 619              "outside_cost = %d .", inside_cost, outside_cost);
 620
 621   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
 622   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
 623   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
 624 }
 625
 626
 627 /* Function vect_cost_strided_group_size
 628
 629    For strided load or store, return the group_size only if it is the first
 630    load or store of a group, else return 1.  This ensures that group size is
 631    only returned once per group.  */
 632
 633 static int
 634 vect_cost_strided_group_size (stmt_vec_info stmt_info)
 635 {
 636   gimple first_stmt = DR_GROUP_FIRST_DR (stmt_info);
 637
 638   if (first_stmt == STMT_VINFO_STMT (stmt_info))
 639     return DR_GROUP_SIZE (stmt_info);
 640
 641   return 1;
 642 }
 643
 644
 645 /* Function vect_model_store_cost
 646
 647    Models cost for stores.  In the case of strided accesses, one access
 648    has the overhead of the strided access attributed to it.  */
 649
 650 void
 651 vect_model_store_cost (stmt_vec_info stmt_info, int ncopies,
 652                        enum vect_def_type dt, slp_tree slp_node)
 653 {
 654   int group_size;
 655   unsigned int inside_cost = 0, outside_cost = 0;
 656   struct data_reference *first_dr;
 657   gimple first_stmt;
 658
 659   /* The SLP costs were already calculated during SLP tree build.  */
 660   if (PURE_SLP_STMT (stmt_info))
 661     return;
 662
 663   if (dt == vect_constant_def || dt == vect_external_def)
 664     outside_cost = vect_get_stmt_cost (scalar_to_vec);
 665
 666   /* Strided access?  */
 667   if (DR_GROUP_FIRST_DR (stmt_info))
 668     {
 669       if (slp_node)
 670         {
 671           first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
 672           group_size = 1;
 673         }
 674       else
 675         {
 676           first_stmt = DR_GROUP_FIRST_DR (stmt_info);
 677           group_size = vect_cost_strided_group_size (stmt_info);
 678         }
 679
 680       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
 681     }
 682   /* Not a strided access.  */
 683   else
 684     {
 685       group_size = 1;
 686       first_dr = STMT_VINFO_DATA_REF (stmt_info);
 687     }
 688
 689   /* Is this an access in a group of stores, which provide strided access?
 690      If so, add in the cost of the permutes.  */
 691   if (group_size > 1)
 692     {
 693       /* Uses a high and low interleave operation for each needed permute.  */
 694       inside_cost = ncopies * exact_log2(group_size) * group_size
 695         * vect_get_stmt_cost (vector_stmt);
 696
 697       if (vect_print_dump_info (REPORT_COST))
 698         fprintf (vect_dump, "vect_model_store_cost: strided group_size = %d .",
 699                  group_size);
 700
 701     }
 702
 703   /* Costs of the stores.  */
 704   vect_get_store_cost (first_dr, ncopies, &inside_cost);
 705
 706   if (vect_print_dump_info (REPORT_COST))
 707     fprintf (vect_dump, "vect_model_store_cost: inside_cost = %d, "
 708              "outside_cost = %d .", inside_cost, outside_cost);
 709
 710   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
 711   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
 712   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
 713 }
 714
 715
 716 /* Calculate cost of DR's memory access.  */
 717 void
 718 vect_get_store_cost (struct data_reference *dr, int ncopies,
 719                      unsigned int *inside_cost)
 720 {
 721   int alignment_support_scheme = vect_supportable_dr_alignment (dr, false);
 722
 723   switch (alignment_support_scheme)
 724     {
 725     case dr_aligned:
 726       {
 727         *inside_cost += ncopies * vect_get_stmt_cost (vector_store);
 728
 729         if (vect_print_dump_info (REPORT_COST))
 730           fprintf (vect_dump, "vect_model_store_cost: aligned.");
 731
 732         break;
 733       }
 734
 735     case dr_unaligned_supported:
 736       {
 737         gimple stmt = DR_STMT (dr);
 738         stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 739         tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 740
 741         /* Here, we assign an additional cost for the unaligned store.  */
 742         *inside_cost += ncopies
 743           * targetm.vectorize.builtin_vectorization_cost (unaligned_store,
 744                                  vectype, DR_MISALIGNMENT (dr));
 745
 746         if (vect_print_dump_info (REPORT_COST))
 747           fprintf (vect_dump, "vect_model_store_cost: unaligned supported by "
 748                    "hardware.");
 749
 750         break;
 751       }
 752
 753     default:
 754       gcc_unreachable ();
 755     }
 756 }
 757
 758
 759 /* Function vect_model_load_cost
 760
 761    Models cost for loads.  In the case of strided accesses, the last access
 762    has the overhead of the strided access attributed to it.  Since unaligned
 763    accesses are supported for loads, we also account for the costs of the
 764    access scheme chosen.  */
 765
 766 void
 767 vect_model_load_cost (stmt_vec_info stmt_info, int ncopies, slp_tree slp_node)
 768
 769 {
 770   int group_size;
 771   gimple first_stmt;
 772   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr;
 773   unsigned int inside_cost = 0, outside_cost = 0;
 774
 775   /* The SLP costs were already calculated during SLP tree build.  */
 776   if (PURE_SLP_STMT (stmt_info))
 777     return;
 778
 779   /* Strided accesses?  */
 780   first_stmt = DR_GROUP_FIRST_DR (stmt_info);
 781   if (first_stmt && !slp_node)
 782     {
 783       group_size = vect_cost_strided_group_size (stmt_info);
 784       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
 785     }
 786   /* Not a strided access.  */
 787   else
 788     {
 789       group_size = 1;
 790       first_dr = dr;
 791     }
 792
 793   /* Is this an access in a group of loads providing strided access?
 794      If so, add in the cost of the permutes.  */
 795   if (group_size > 1)
 796     {
 797       /* Uses an even and odd extract operations for each needed permute.  */
 798       inside_cost = ncopies * exact_log2(group_size) * group_size
 799         * vect_get_stmt_cost (vector_stmt);
 800
 801       if (vect_print_dump_info (REPORT_COST))
 802         fprintf (vect_dump, "vect_model_load_cost: strided group_size = %d .",
 803                  group_size);
 804     }
 805
 806   /* The loads themselves.  */
 807   vect_get_load_cost (first_dr, ncopies,
 808          ((!DR_GROUP_FIRST_DR (stmt_info)) || group_size > 1 || slp_node),
 809          &inside_cost, &outside_cost);
 810
 811   if (vect_print_dump_info (REPORT_COST))
 812     fprintf (vect_dump, "vect_model_load_cost: inside_cost = %d, "
 813              "outside_cost = %d .", inside_cost, outside_cost);
 814
 815   /* Set the costs either in STMT_INFO or SLP_NODE (if exists).  */
 816   stmt_vinfo_set_inside_of_loop_cost (stmt_info, slp_node, inside_cost);
 817   stmt_vinfo_set_outside_of_loop_cost (stmt_info, slp_node, outside_cost);
 818 }
 819
 820
 821 /* Calculate cost of DR's memory access.  */
 822 void
 823 vect_get_load_cost (struct data_reference *dr, int ncopies,
 824                     bool add_realign_cost, unsigned int *inside_cost,
 825                     unsigned int *outside_cost)
 826 {
 827   int alignment_support_scheme = vect_supportable_dr_alignment (dr, false);
 828
 829   switch (alignment_support_scheme)
 830     {
 831     case dr_aligned:
 832       {
 833         *inside_cost += ncopies * vect_get_stmt_cost (vector_load);
 834
 835         if (vect_print_dump_info (REPORT_COST))
 836           fprintf (vect_dump, "vect_model_load_cost: aligned.");
 837
 838         break;
 839       }
 840     case dr_unaligned_supported:
 841       {
 842         gimple stmt = DR_STMT (dr);
 843         stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
 844         tree vectype = STMT_VINFO_VECTYPE (stmt_info);
 845
 846         /* Here, we assign an additional cost for the unaligned load.  */
 847         *inside_cost += ncopies
 848           * targetm.vectorize.builtin_vectorization_cost (unaligned_load,
 849                                            vectype, DR_MISALIGNMENT (dr));
 850         if (vect_print_dump_info (REPORT_COST))
 851           fprintf (vect_dump, "vect_model_load_cost: unaligned supported by "
 852                    "hardware.");
 853
 854         break;
 855       }
 856     case dr_explicit_realign:
 857       {
 858         *inside_cost += ncopies * (2 * vect_get_stmt_cost (vector_load)
 859            + vect_get_stmt_cost (vector_stmt));
 860
 861         /* FIXME: If the misalignment remains fixed across the iterations of
 862            the containing loop, the following cost should be added to the
 863            outside costs.  */
 864         if (targetm.vectorize.builtin_mask_for_load)
 865           *inside_cost += vect_get_stmt_cost (vector_stmt);
 866
 867         break;
 868       }
 869     case dr_explicit_realign_optimized:
 870       {
 871         if (vect_print_dump_info (REPORT_COST))
 872           fprintf (vect_dump, "vect_model_load_cost: unaligned software "
 873                    "pipelined.");
 874
 875         /* Unaligned software pipeline has a load of an address, an initial
 876            load, and possibly a mask operation to "prime" the loop.  However,
 877            if this is an access in a group of loads, which provide strided
 878            access, then the above cost should only be considered for one
 879            access in the group.  Inside the loop, there is a load op
 880            and a realignment op.  */
 881
 882         if (add_realign_cost)
 883           {
 884             *outside_cost = 2 * vect_get_stmt_cost (vector_stmt);
 885             if (targetm.vectorize.builtin_mask_for_load)
 886               *outside_cost += vect_get_stmt_cost (vector_stmt);
 887           }
 888
 889         *inside_cost += ncopies * (vect_get_stmt_cost (vector_load)
 890           + vect_get_stmt_cost (vector_stmt));
 891         break;
 892       }
 893
 894     default:
 895       gcc_unreachable ();
 896     }
 897 }
 898
 899
 900 /* Function vect_init_vector.
 901
 902    Insert a new stmt (INIT_STMT) that initializes a new vector variable with
 903    the vector elements of VECTOR_VAR.  Place the initialization at BSI if it
 904    is not NULL.  Otherwise, place the initialization at the loop preheader.
 905    Return the DEF of INIT_STMT.
 906    It will be used in the vectorization of STMT.  */
 907
 908 tree
 909 vect_init_vector (gimple stmt, tree vector_var, tree vector_type,
 910                   gimple_stmt_iterator *gsi)
 911 {
 912   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 913   tree new_var;
 914   gimple init_stmt;
 915   tree vec_oprnd;
 916   edge pe;
 917   tree new_temp;
 918   basic_block new_bb;
 919
 920   new_var = vect_get_new_vect_var (vector_type, vect_simple_var, "cst_");
 921   add_referenced_var (new_var);
 922   init_stmt = gimple_build_assign  (new_var, vector_var);
 923   new_temp = make_ssa_name (new_var, init_stmt);
 924   gimple_assign_set_lhs (init_stmt, new_temp);
 925
 926   if (gsi)
 927     vect_finish_stmt_generation (stmt, init_stmt, gsi);
 928   else
 929     {
 930       loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 931
 932       if (loop_vinfo)
 933         {
 934           struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
 935
 936           if (nested_in_vect_loop_p (loop, stmt))
 937             loop = loop->inner;
 938
 939           pe = loop_preheader_edge (loop);
 940           new_bb = gsi_insert_on_edge_immediate (pe, init_stmt);
 941           gcc_assert (!new_bb);
 942         }
 943       else
 944        {
 945           bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_vinfo);
 946           basic_block bb;
 947           gimple_stmt_iterator gsi_bb_start;
 948
 949           gcc_assert (bb_vinfo);
 950           bb = BB_VINFO_BB (bb_vinfo);
 951           gsi_bb_start = gsi_after_labels (bb);
 952           gsi_insert_before (&gsi_bb_start, init_stmt, GSI_SAME_STMT);
 953        }
 954     }
 955
 956   if (vect_print_dump_info (REPORT_DETAILS))
 957     {
 958       fprintf (vect_dump, "created new init_stmt: ");
 959       print_gimple_stmt (vect_dump, init_stmt, 0, TDF_SLIM);
 960     }
 961
 962   vec_oprnd = gimple_assign_lhs (init_stmt);
 963   return vec_oprnd;
 964 }
 965
 966
 967 /* Function vect_get_vec_def_for_operand.
 968
 969    OP is an operand in STMT.  This function returns a (vector) def that will be
 970    used in the vectorized stmt for STMT.
 971
 972    In the case that OP is an SSA_NAME which is defined in the loop, then
 973    STMT_VINFO_VEC_STMT of the defining stmt holds the relevant def.
 974
 975    In case OP is an invariant or constant, a new stmt that creates a vector def
 976    needs to be introduced.  */
 977
 978 tree
 979 vect_get_vec_def_for_operand (tree op, gimple stmt, tree *scalar_def)
 980 {
 981   tree vec_oprnd;
 982   gimple vec_stmt;
 983   gimple def_stmt;
 984   stmt_vec_info def_stmt_info = NULL;
 985   stmt_vec_info stmt_vinfo = vinfo_for_stmt (stmt);
 986   unsigned int nunits;
 987   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_vinfo);
 988   tree vec_inv;
 989   tree vec_cst;
 990   tree def;
 991   enum vect_def_type dt;
 992   bool is_simple_use;
 993   tree vector_type;
 994
 995   if (vect_print_dump_info (REPORT_DETAILS))
 996     {
 997       fprintf (vect_dump, "vect_get_vec_def_for_operand: ");
 998       print_generic_expr (vect_dump, op, TDF_SLIM);
 999     }
1000
1001   is_simple_use = vect_is_simple_use (op, loop_vinfo, NULL, &def_stmt, &def,
1002                                       &dt);
1003   gcc_assert (is_simple_use);
1004   if (vect_print_dump_info (REPORT_DETAILS))
1005     {
1006       if (def)
1007         {
1008           fprintf (vect_dump, "def =  ");
1009           print_generic_expr (vect_dump, def, TDF_SLIM);
1010         }
1011       if (def_stmt)
1012         {
1013           fprintf (vect_dump, "  def_stmt =  ");
1014           print_gimple_stmt (vect_dump, def_stmt, 0, TDF_SLIM);
1015         }
1016     }
1017
1018   switch (dt)
1019     {
1020     /* Case 1: operand is a constant.  */
1021     case vect_constant_def:
1022       {
1023         vector_type = get_vectype_for_scalar_type (TREE_TYPE (op));
1024         gcc_assert (vector_type);
1025         nunits = TYPE_VECTOR_SUBPARTS (vector_type);
1026
1027         if (scalar_def)
1028           *scalar_def = op;
1029
1030         /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
1031         if (vect_print_dump_info (REPORT_DETAILS))
1032           fprintf (vect_dump, "Create vector_cst. nunits = %d", nunits);
1033
1034         vec_cst = build_vector_from_val (vector_type, op);
1035         return vect_init_vector (stmt, vec_cst, vector_type, NULL);
1036       }
1037
1038     /* Case 2: operand is defined outside the loop - loop invariant.  */
1039     case vect_external_def:
1040       {
1041         vector_type = get_vectype_for_scalar_type (TREE_TYPE (def));
1042         gcc_assert (vector_type);
1043         nunits = TYPE_VECTOR_SUBPARTS (vector_type);
1044
1045         if (scalar_def)
1046           *scalar_def = def;
1047
1048         /* Create 'vec_inv = {inv,inv,..,inv}'  */
1049         if (vect_print_dump_info (REPORT_DETAILS))
1050           fprintf (vect_dump, "Create vector_inv.");
1051
1052         vec_inv = build_vector_from_val (vector_type, def);
1053         return vect_init_vector (stmt, vec_inv, vector_type, NULL);
1054       }
1055
1056     /* Case 3: operand is defined inside the loop.  */
1057     case vect_internal_def:
1058       {
1059         if (scalar_def)
1060           *scalar_def = NULL/* FIXME tuples: def_stmt*/;
1061
1062         /* Get the def from the vectorized stmt.  */
1063         def_stmt_info = vinfo_for_stmt (def_stmt);
1064         vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
1065         gcc_assert (vec_stmt);
1066         if (gimple_code (vec_stmt) == GIMPLE_PHI)
1067           vec_oprnd = PHI_RESULT (vec_stmt);
1068         else if (is_gimple_call (vec_stmt))
1069           vec_oprnd = gimple_call_lhs (vec_stmt);
1070         else
1071           vec_oprnd = gimple_assign_lhs (vec_stmt);
1072         return vec_oprnd;
1073       }
1074
1075     /* Case 4: operand is defined by a loop header phi - reduction  */
1076     case vect_reduction_def:
1077     case vect_double_reduction_def:
1078     case vect_nested_cycle:
1079       {
1080         struct loop *loop;
1081
1082         gcc_assert (gimple_code (def_stmt) == GIMPLE_PHI);
1083         loop = (gimple_bb (def_stmt))->loop_father;
1084
1085         /* Get the def before the loop  */
1086         op = PHI_ARG_DEF_FROM_EDGE (def_stmt, loop_preheader_edge (loop));
1087         return get_initial_def_for_reduction (stmt, op, scalar_def);
1088      }
1089
1090     /* Case 5: operand is defined by loop-header phi - induction.  */
1091     case vect_induction_def:
1092       {
1093         gcc_assert (gimple_code (def_stmt) == GIMPLE_PHI);
1094
1095         /* Get the def from the vectorized stmt.  */
1096         def_stmt_info = vinfo_for_stmt (def_stmt);
1097         vec_stmt = STMT_VINFO_VEC_STMT (def_stmt_info);
1098         gcc_assert (vec_stmt && gimple_code (vec_stmt) == GIMPLE_PHI);
1099         vec_oprnd = PHI_RESULT (vec_stmt);
1100         return vec_oprnd;
1101       }
1102
1103     default:
1104       gcc_unreachable ();
1105     }
1106 }
1107
1108
1109 /* Function vect_get_vec_def_for_stmt_copy
1110
1111    Return a vector-def for an operand.  This function is used when the
1112    vectorized stmt to be created (by the caller to this function) is a "copy"
1113    created in case the vectorized result cannot fit in one vector, and several
1114    copies of the vector-stmt are required.  In this case the vector-def is
1115    retrieved from the vector stmt recorded in the STMT_VINFO_RELATED_STMT field
1116    of the stmt that defines VEC_OPRND.
1117    DT is the type of the vector def VEC_OPRND.
1118
1119    Context:
1120         In case the vectorization factor (VF) is bigger than the number
1121    of elements that can fit in a vectype (nunits), we have to generate
1122    more than one vector stmt to vectorize the scalar stmt.  This situation
1123    arises when there are multiple data-types operated upon in the loop; the
1124    smallest data-type determines the VF, and as a result, when vectorizing
1125    stmts operating on wider types we need to create 'VF/nunits' "copies" of the
1126    vector stmt (each computing a vector of 'nunits' results, and together
1127    computing 'VF' results in each iteration).  This function is called when
1128    vectorizing such a stmt (e.g. vectorizing S2 in the illustration below, in
1129    which VF=16 and nunits=4, so the number of copies required is 4):
1130
1131    scalar stmt:         vectorized into:        STMT_VINFO_RELATED_STMT
1132
1133    S1: x = load         VS1.0:  vx.0 = memref0      VS1.1
1134                         VS1.1:  vx.1 = memref1      VS1.2
1135                         VS1.2:  vx.2 = memref2      VS1.3
1136                         VS1.3:  vx.3 = memref3
1137
1138    S2: z = x + ...      VSnew.0:  vz0 = vx.0 + ...  VSnew.1
1139                         VSnew.1:  vz1 = vx.1 + ...  VSnew.2
1140                         VSnew.2:  vz2 = vx.2 + ...  VSnew.3
1141                         VSnew.3:  vz3 = vx.3 + ...
1142
1143    The vectorization of S1 is explained in vectorizable_load.
1144    The vectorization of S2:
1145         To create the first vector-stmt out of the 4 copies - VSnew.0 -
1146    the function 'vect_get_vec_def_for_operand' is called to
1147    get the relevant vector-def for each operand of S2.  For operand x it
1148    returns  the vector-def 'vx.0'.
1149
1150         To create the remaining copies of the vector-stmt (VSnew.j), this
1151    function is called to get the relevant vector-def for each operand.  It is
1152    obtained from the respective VS1.j stmt, which is recorded in the
1153    STMT_VINFO_RELATED_STMT field of the stmt that defines VEC_OPRND.
1154
1155         For example, to obtain the vector-def 'vx.1' in order to create the
1156    vector stmt 'VSnew.1', this function is called with VEC_OPRND='vx.0'.
1157    Given 'vx0' we obtain the stmt that defines it ('VS1.0'); from the
1158    STMT_VINFO_RELATED_STMT field of 'VS1.0' we obtain the next copy - 'VS1.1',
1159    and return its def ('vx.1').
1160    Overall, to create the above sequence this function will be called 3 times:
1161         vx.1 = vect_get_vec_def_for_stmt_copy (dt, vx.0);
1162         vx.2 = vect_get_vec_def_for_stmt_copy (dt, vx.1);
1163         vx.3 = vect_get_vec_def_for_stmt_copy (dt, vx.2);  */
1164
1165 tree
1166 vect_get_vec_def_for_stmt_copy (enum vect_def_type dt, tree vec_oprnd)
1167 {
1168   gimple vec_stmt_for_operand;
1169   stmt_vec_info def_stmt_info;
1170
1171   /* Do nothing; can reuse same def.  */
1172   if (dt == vect_external_def || dt == vect_constant_def )
1173     return vec_oprnd;
1174
1175   vec_stmt_for_operand = SSA_NAME_DEF_STMT (vec_oprnd);
1176   def_stmt_info = vinfo_for_stmt (vec_stmt_for_operand);
1177   gcc_assert (def_stmt_info);
1178   vec_stmt_for_operand = STMT_VINFO_RELATED_STMT (def_stmt_info);
1179   gcc_assert (vec_stmt_for_operand);
1180   vec_oprnd = gimple_get_lhs (vec_stmt_for_operand);
1181   if (gimple_code (vec_stmt_for_operand) == GIMPLE_PHI)
1182     vec_oprnd = PHI_RESULT (vec_stmt_for_operand);
1183   else
1184     vec_oprnd = gimple_get_lhs (vec_stmt_for_operand);
1185   return vec_oprnd;
1186 }
1187
1188
1189 /* Get vectorized definitions for the operands to create a copy of an original
1190    stmt.  See vect_get_vec_def_for_stmt_copy () for details.  */
1191
1192 static void
1193 vect_get_vec_defs_for_stmt_copy (enum vect_def_type *dt,
1194                                  VEC(tree,heap) **vec_oprnds0,
1195                                  VEC(tree,heap) **vec_oprnds1)
1196 {
1197   tree vec_oprnd = VEC_pop (tree, *vec_oprnds0);
1198
1199   vec_oprnd = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd);
1200   VEC_quick_push (tree, *vec_oprnds0, vec_oprnd);
1201
1202   if (vec_oprnds1 && *vec_oprnds1)
1203     {
1204       vec_oprnd = VEC_pop (tree, *vec_oprnds1);
1205       vec_oprnd = vect_get_vec_def_for_stmt_copy (dt[1], vec_oprnd);
1206       VEC_quick_push (tree, *vec_oprnds1, vec_oprnd);
1207     }
1208 }
1209
1210
1211 /* Get vectorized definitions for OP0 and OP1, or SLP_NODE if it is not
1212    NULL.  */
1213
1214 static void
1215 vect_get_vec_defs (tree op0, tree op1, gimple stmt,
1216                    VEC(tree,heap) **vec_oprnds0, VEC(tree,heap) **vec_oprnds1,
1217                    slp_tree slp_node)
1218 {
1219   if (slp_node)
1220     vect_get_slp_defs (op0, op1, slp_node, vec_oprnds0, vec_oprnds1, -1);
1221   else
1222     {
1223       tree vec_oprnd;
1224
1225       *vec_oprnds0 = VEC_alloc (tree, heap, 1);
1226       vec_oprnd = vect_get_vec_def_for_operand (op0, stmt, NULL);
1227       VEC_quick_push (tree, *vec_oprnds0, vec_oprnd);
1228
1229       if (op1)
1230         {
1231           *vec_oprnds1 = VEC_alloc (tree, heap, 1);
1232           vec_oprnd = vect_get_vec_def_for_operand (op1, stmt, NULL);
1233           VEC_quick_push (tree, *vec_oprnds1, vec_oprnd);
1234         }
1235     }
1236 }
1237
1238
1239 /* Function vect_finish_stmt_generation.
1240
1241    Insert a new stmt.  */
1242
1243 void
1244 vect_finish_stmt_generation (gimple stmt, gimple vec_stmt,
1245                              gimple_stmt_iterator *gsi)
1246 {
1247   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1248   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1249   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
1250
1251   gcc_assert (gimple_code (stmt) != GIMPLE_LABEL);
1252
1253   gsi_insert_before (gsi, vec_stmt, GSI_SAME_STMT);
1254
1255   set_vinfo_for_stmt (vec_stmt, new_stmt_vec_info (vec_stmt, loop_vinfo,
1256                                                    bb_vinfo));
1257
1258   if (vect_print_dump_info (REPORT_DETAILS))
1259     {
1260       fprintf (vect_dump, "add new stmt: ");
1261       print_gimple_stmt (vect_dump, vec_stmt, 0, TDF_SLIM);
1262     }
1263
1264   gimple_set_location (vec_stmt, gimple_location (gsi_stmt (*gsi)));
1265 }
1266
1267 /* Checks if CALL can be vectorized in type VECTYPE.  Returns
1268    a function declaration if the target has a vectorized version
1269    of the function, or NULL_TREE if the function cannot be vectorized.  */
1270
1271 tree
1272 vectorizable_function (gimple call, tree vectype_out, tree vectype_in)
1273 {
1274   tree fndecl = gimple_call_fndecl (call);
1275
1276   /* We only handle functions that do not read or clobber memory -- i.e.
1277      const or novops ones.  */
1278   if (!(gimple_call_flags (call) & (ECF_CONST | ECF_NOVOPS)))
1279     return NULL_TREE;
1280
1281   if (!fndecl
1282       || TREE_CODE (fndecl) != FUNCTION_DECL
1283       || !DECL_BUILT_IN (fndecl))
1284     return NULL_TREE;
1285
1286   return targetm.vectorize.builtin_vectorized_function (fndecl, vectype_out,
1287                                                         vectype_in);
1288 }
1289
1290 /* Function vectorizable_call.
1291
1292    Check if STMT performs a function call that can be vectorized.
1293    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1294    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1295    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1296
1297 static bool
1298 vectorizable_call (gimple stmt, gimple_stmt_iterator *gsi, gimple *vec_stmt)
1299 {
1300   tree vec_dest;
1301   tree scalar_dest;
1302   tree op, type;
1303   tree vec_oprnd0 = NULL_TREE, vec_oprnd1 = NULL_TREE;
1304   stmt_vec_info stmt_info = vinfo_for_stmt (stmt), prev_stmt_info;
1305   tree vectype_out, vectype_in;
1306   int nunits_in;
1307   int nunits_out;
1308   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1309   tree fndecl, new_temp, def, rhs_type;
1310   gimple def_stmt;
1311   enum vect_def_type dt[3]
1312     = {vect_unknown_def_type, vect_unknown_def_type, vect_unknown_def_type};
1313   gimple new_stmt = NULL;
1314   int ncopies, j;
1315   VEC(tree, heap) *vargs = NULL;
1316   enum { NARROW, NONE, WIDEN } modifier;
1317   size_t i, nargs;
1318
1319   /* FORNOW: unsupported in basic block SLP.  */
1320   gcc_assert (loop_vinfo);
1321
1322   if (!STMT_VINFO_RELEVANT_P (stmt_info))
1323     return false;
1324
1325   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
1326     return false;
1327
1328   /* FORNOW: SLP not supported.  */
1329   if (STMT_SLP_TYPE (stmt_info))
1330     return false;
1331
1332   /* Is STMT a vectorizable call?   */
1333   if (!is_gimple_call (stmt))
1334     return false;
1335
1336   if (TREE_CODE (gimple_call_lhs (stmt)) != SSA_NAME)
1337     return false;
1338
1339   if (stmt_could_throw_p (stmt))
1340     return false;
1341
1342   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
1343
1344   /* Process function arguments.  */
1345   rhs_type = NULL_TREE;
1346   vectype_in = NULL_TREE;
1347   nargs = gimple_call_num_args (stmt);
1348
1349   /* Bail out if the function has more than three arguments, we do not have
1350      interesting builtin functions to vectorize with more than two arguments
1351      except for fma.  No arguments is also not good.  */
1352   if (nargs == 0 || nargs > 3)
1353     return false;
1354
1355   for (i = 0; i < nargs; i++)
1356     {
1357       tree opvectype;
1358
1359       op = gimple_call_arg (stmt, i);
1360
1361       /* We can only handle calls with arguments of the same type.  */
1362       if (rhs_type
1363           && !types_compatible_p (rhs_type, TREE_TYPE (op)))
1364         {
1365           if (vect_print_dump_info (REPORT_DETAILS))
1366             fprintf (vect_dump, "argument types differ.");
1367           return false;
1368         }
1369       if (!rhs_type)
1370         rhs_type = TREE_TYPE (op);
1371
1372       if (!vect_is_simple_use_1 (op, loop_vinfo, NULL,
1373                                  &def_stmt, &def, &dt[i], &opvectype))
1374         {
1375           if (vect_print_dump_info (REPORT_DETAILS))
1376             fprintf (vect_dump, "use not simple.");
1377           return false;
1378         }
1379
1380       if (!vectype_in)
1381         vectype_in = opvectype;
1382       else if (opvectype
1383                && opvectype != vectype_in)
1384         {
1385           if (vect_print_dump_info (REPORT_DETAILS))
1386             fprintf (vect_dump, "argument vector types differ.");
1387           return false;
1388         }
1389     }
1390   /* If all arguments are external or constant defs use a vector type with
1391      the same size as the output vector type.  */
1392   if (!vectype_in)
1393     vectype_in = get_same_sized_vectype (rhs_type, vectype_out);
1394   if (vec_stmt)
1395     gcc_assert (vectype_in);
1396   if (!vectype_in)
1397     {
1398       if (vect_print_dump_info (REPORT_DETAILS))
1399         {
1400           fprintf (vect_dump, "no vectype for scalar type ");
1401           print_generic_expr (vect_dump, rhs_type, TDF_SLIM);
1402         }
1403
1404       return false;
1405     }
1406
1407   /* FORNOW */
1408   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
1409   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
1410   if (nunits_in == nunits_out / 2)
1411     modifier = NARROW;
1412   else if (nunits_out == nunits_in)
1413     modifier = NONE;
1414   else if (nunits_out == nunits_in / 2)
1415     modifier = WIDEN;
1416   else
1417     return false;
1418
1419   /* For now, we only vectorize functions if a target specific builtin
1420      is available.  TODO -- in some cases, it might be profitable to
1421      insert the calls for pieces of the vector, in order to be able
1422      to vectorize other operations in the loop.  */
1423   fndecl = vectorizable_function (stmt, vectype_out, vectype_in);
1424   if (fndecl == NULL_TREE)
1425     {
1426       if (vect_print_dump_info (REPORT_DETAILS))
1427         fprintf (vect_dump, "function is not vectorizable.");
1428
1429       return false;
1430     }
1431
1432   gcc_assert (!gimple_vuse (stmt));
1433
1434   if (modifier == NARROW)
1435     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
1436   else
1437     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
1438
1439   /* Sanity check: make sure that at least one copy of the vectorized stmt
1440      needs to be generated.  */
1441   gcc_assert (ncopies >= 1);
1442
1443   if (!vec_stmt) /* transformation not required.  */
1444     {
1445       STMT_VINFO_TYPE (stmt_info) = call_vec_info_type;
1446       if (vect_print_dump_info (REPORT_DETAILS))
1447         fprintf (vect_dump, "=== vectorizable_call ===");
1448       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
1449       return true;
1450     }
1451
1452   /** Transform.  **/
1453
1454   if (vect_print_dump_info (REPORT_DETAILS))
1455     fprintf (vect_dump, "transform operation.");
1456
1457   /* Handle def.  */
1458   scalar_dest = gimple_call_lhs (stmt);
1459   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
1460
1461   prev_stmt_info = NULL;
1462   switch (modifier)
1463     {
1464     case NONE:
1465       for (j = 0; j < ncopies; ++j)
1466         {
1467           /* Build argument list for the vectorized call.  */
1468           if (j == 0)
1469             vargs = VEC_alloc (tree, heap, nargs);
1470           else
1471             VEC_truncate (tree, vargs, 0);
1472
1473           for (i = 0; i < nargs; i++)
1474             {
1475               op = gimple_call_arg (stmt, i);
1476               if (j == 0)
1477                 vec_oprnd0
1478                   = vect_get_vec_def_for_operand (op, stmt, NULL);
1479               else
1480                 {
1481                   vec_oprnd0 = gimple_call_arg (new_stmt, i);
1482                   vec_oprnd0
1483                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd0);
1484                 }
1485
1486               VEC_quick_push (tree, vargs, vec_oprnd0);
1487             }
1488
1489           new_stmt = gimple_build_call_vec (fndecl, vargs);
1490           new_temp = make_ssa_name (vec_dest, new_stmt);
1491           gimple_call_set_lhs (new_stmt, new_temp);
1492
1493           vect_finish_stmt_generation (stmt, new_stmt, gsi);
1494           mark_symbols_for_renaming (new_stmt);
1495
1496           if (j == 0)
1497             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
1498           else
1499             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1500
1501           prev_stmt_info = vinfo_for_stmt (new_stmt);
1502         }
1503
1504       break;
1505
1506     case NARROW:
1507       for (j = 0; j < ncopies; ++j)
1508         {
1509           /* Build argument list for the vectorized call.  */
1510           if (j == 0)
1511             vargs = VEC_alloc (tree, heap, nargs * 2);
1512           else
1513             VEC_truncate (tree, vargs, 0);
1514
1515           for (i = 0; i < nargs; i++)
1516             {
1517               op = gimple_call_arg (stmt, i);
1518               if (j == 0)
1519                 {
1520                   vec_oprnd0
1521                     = vect_get_vec_def_for_operand (op, stmt, NULL);
1522                   vec_oprnd1
1523                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd0);
1524                 }
1525               else
1526                 {
1527                   vec_oprnd1 = gimple_call_arg (new_stmt, 2*i);
1528                   vec_oprnd0
1529                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd1);
1530                   vec_oprnd1
1531                     = vect_get_vec_def_for_stmt_copy (dt[i], vec_oprnd0);
1532                 }
1533
1534               VEC_quick_push (tree, vargs, vec_oprnd0);
1535               VEC_quick_push (tree, vargs, vec_oprnd1);
1536             }
1537
1538           new_stmt = gimple_build_call_vec (fndecl, vargs);
1539           new_temp = make_ssa_name (vec_dest, new_stmt);
1540           gimple_call_set_lhs (new_stmt, new_temp);
1541
1542           vect_finish_stmt_generation (stmt, new_stmt, gsi);
1543           mark_symbols_for_renaming (new_stmt);
1544
1545           if (j == 0)
1546             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
1547           else
1548             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1549
1550           prev_stmt_info = vinfo_for_stmt (new_stmt);
1551         }
1552
1553       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
1554
1555       break;
1556
1557     case WIDEN:
1558       /* No current target implements this case.  */
1559       return false;
1560     }
1561
1562   VEC_free (tree, heap, vargs);
1563
1564   /* Update the exception handling table with the vector stmt if necessary.  */
1565   if (maybe_clean_or_replace_eh_stmt (stmt, *vec_stmt))
1566     gimple_purge_dead_eh_edges (gimple_bb (stmt));
1567
1568   /* The call in STMT might prevent it from being removed in dce.
1569      We however cannot remove it here, due to the way the ssa name
1570      it defines is mapped to the new definition.  So just replace
1571      rhs of the statement with something harmless.  */
1572
1573   type = TREE_TYPE (scalar_dest);
1574   new_stmt = gimple_build_assign (gimple_call_lhs (stmt),
1575                                   fold_convert (type, integer_zero_node));
1576   set_vinfo_for_stmt (new_stmt, stmt_info);
1577   set_vinfo_for_stmt (stmt, NULL);
1578   STMT_VINFO_STMT (stmt_info) = new_stmt;
1579   gsi_replace (gsi, new_stmt, false);
1580   SSA_NAME_DEF_STMT (gimple_assign_lhs (new_stmt)) = new_stmt;
1581
1582   return true;
1583 }
1584
1585
1586 /* Function vect_gen_widened_results_half
1587
1588    Create a vector stmt whose code, type, number of arguments, and result
1589    variable are CODE, OP_TYPE, and VEC_DEST, and its arguments are
1590    VEC_OPRND0 and VEC_OPRND1.  The new vector stmt is to be inserted at BSI.
1591    In the case that CODE is a CALL_EXPR, this means that a call to DECL
1592    needs to be created (DECL is a function-decl of a target-builtin).
1593    STMT is the original scalar stmt that we are vectorizing.  */
1594
1595 static gimple
1596 vect_gen_widened_results_half (enum tree_code code,
1597                                tree decl,
1598                                tree vec_oprnd0, tree vec_oprnd1, int op_type,
1599                                tree vec_dest, gimple_stmt_iterator *gsi,
1600                                gimple stmt)
1601 {
1602   gimple new_stmt;
1603   tree new_temp;
1604
1605   /* Generate half of the widened result:  */
1606   if (code == CALL_EXPR)
1607     {
1608       /* Target specific support  */
1609       if (op_type == binary_op)
1610         new_stmt = gimple_build_call (decl, 2, vec_oprnd0, vec_oprnd1);
1611       else
1612         new_stmt = gimple_build_call (decl, 1, vec_oprnd0);
1613       new_temp = make_ssa_name (vec_dest, new_stmt);
1614       gimple_call_set_lhs (new_stmt, new_temp);
1615     }
1616   else
1617     {
1618       /* Generic support */
1619       gcc_assert (op_type == TREE_CODE_LENGTH (code));
1620       if (op_type != binary_op)
1621         vec_oprnd1 = NULL;
1622       new_stmt = gimple_build_assign_with_ops (code, vec_dest, vec_oprnd0,
1623                                                vec_oprnd1);
1624       new_temp = make_ssa_name (vec_dest, new_stmt);
1625       gimple_assign_set_lhs (new_stmt, new_temp);
1626     }
1627   vect_finish_stmt_generation (stmt, new_stmt, gsi);
1628
1629   return new_stmt;
1630 }
1631
1632
1633 /* Check if STMT performs a conversion operation, that can be vectorized.
1634    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1635    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1636    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1637
1638 static bool
1639 vectorizable_conversion (gimple stmt, gimple_stmt_iterator *gsi,
1640                          gimple *vec_stmt, slp_tree slp_node)
1641 {
1642   tree vec_dest;
1643   tree scalar_dest;
1644   tree op0;
1645   tree vec_oprnd0 = NULL_TREE, vec_oprnd1 = NULL_TREE;
1646   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1647   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1648   enum tree_code code, code1 = ERROR_MARK, code2 = ERROR_MARK;
1649   tree decl1 = NULL_TREE, decl2 = NULL_TREE;
1650   tree new_temp;
1651   tree def;
1652   gimple def_stmt;
1653   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
1654   gimple new_stmt = NULL;
1655   stmt_vec_info prev_stmt_info;
1656   int nunits_in;
1657   int nunits_out;
1658   tree vectype_out, vectype_in;
1659   int ncopies, j;
1660   tree rhs_type;
1661   tree builtin_decl;
1662   enum { NARROW, NONE, WIDEN } modifier;
1663   int i;
1664   VEC(tree,heap) *vec_oprnds0 = NULL;
1665   tree vop0;
1666   VEC(tree,heap) *dummy = NULL;
1667   int dummy_int;
1668
1669   /* Is STMT a vectorizable conversion?   */
1670
1671   /* FORNOW: unsupported in basic block SLP.  */
1672   gcc_assert (loop_vinfo);
1673
1674   if (!STMT_VINFO_RELEVANT_P (stmt_info))
1675     return false;
1676
1677   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
1678     return false;
1679
1680   if (!is_gimple_assign (stmt))
1681     return false;
1682
1683   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
1684     return false;
1685
1686   code = gimple_assign_rhs_code (stmt);
1687   if (code != FIX_TRUNC_EXPR && code != FLOAT_EXPR)
1688     return false;
1689
1690   /* Check types of lhs and rhs.  */
1691   scalar_dest = gimple_assign_lhs (stmt);
1692   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
1693
1694   op0 = gimple_assign_rhs1 (stmt);
1695   rhs_type = TREE_TYPE (op0);
1696   /* Check the operands of the operation.  */
1697   if (!vect_is_simple_use_1 (op0, loop_vinfo, NULL,
1698                              &def_stmt, &def, &dt[0], &vectype_in))
1699     {
1700       if (vect_print_dump_info (REPORT_DETAILS))
1701         fprintf (vect_dump, "use not simple.");
1702       return false;
1703     }
1704   /* If op0 is an external or constant defs use a vector type of
1705      the same size as the output vector type.  */
1706   if (!vectype_in)
1707     vectype_in = get_same_sized_vectype (rhs_type, vectype_out);
1708   if (vec_stmt)
1709     gcc_assert (vectype_in);
1710   if (!vectype_in)
1711     {
1712       if (vect_print_dump_info (REPORT_DETAILS))
1713         {
1714           fprintf (vect_dump, "no vectype for scalar type ");
1715           print_generic_expr (vect_dump, rhs_type, TDF_SLIM);
1716         }
1717
1718       return false;
1719     }
1720
1721   /* FORNOW */
1722   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
1723   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
1724   if (nunits_in == nunits_out / 2)
1725     modifier = NARROW;
1726   else if (nunits_out == nunits_in)
1727     modifier = NONE;
1728   else if (nunits_out == nunits_in / 2)
1729     modifier = WIDEN;
1730   else
1731     return false;
1732
1733   if (modifier == NARROW)
1734     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
1735   else
1736     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
1737
1738   /* Multiple types in SLP are handled by creating the appropriate number of
1739      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
1740      case of SLP.  */
1741   if (slp_node)
1742     ncopies = 1;
1743
1744   /* Sanity check: make sure that at least one copy of the vectorized stmt
1745      needs to be generated.  */
1746   gcc_assert (ncopies >= 1);
1747
1748   /* Supportable by target?  */
1749   if ((modifier == NONE
1750        && !targetm.vectorize.builtin_conversion (code, vectype_out, vectype_in))
1751       || (modifier == WIDEN
1752           && !supportable_widening_operation (code, stmt,
1753                                               vectype_out, vectype_in,
1754                                               &decl1, &decl2,
1755                                               &code1, &code2,
1756                                               &dummy_int, &dummy))
1757       || (modifier == NARROW
1758           && !supportable_narrowing_operation (code, vectype_out, vectype_in,
1759                                                &code1, &dummy_int, &dummy)))
1760     {
1761       if (vect_print_dump_info (REPORT_DETAILS))
1762         fprintf (vect_dump, "conversion not supported by target.");
1763       return false;
1764     }
1765
1766   if (modifier != NONE)
1767     {
1768       /* FORNOW: SLP not supported.  */
1769       if (STMT_SLP_TYPE (stmt_info))
1770         return false;
1771     }
1772
1773   if (!vec_stmt)                /* transformation not required.  */
1774     {
1775       STMT_VINFO_TYPE (stmt_info) = type_conversion_vec_info_type;
1776       return true;
1777     }
1778
1779   /** Transform.  **/
1780   if (vect_print_dump_info (REPORT_DETAILS))
1781     fprintf (vect_dump, "transform conversion.");
1782
1783   /* Handle def.  */
1784   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
1785
1786   if (modifier == NONE && !slp_node)
1787     vec_oprnds0 = VEC_alloc (tree, heap, 1);
1788
1789   prev_stmt_info = NULL;
1790   switch (modifier)
1791     {
1792     case NONE:
1793       for (j = 0; j < ncopies; j++)
1794         {
1795           if (j == 0)
1796             vect_get_vec_defs (op0, NULL, stmt, &vec_oprnds0, NULL, slp_node);
1797           else
1798             vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, NULL);
1799
1800           builtin_decl =
1801             targetm.vectorize.builtin_conversion (code,
1802                                                   vectype_out, vectype_in);
1803           FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
1804             {
1805               /* Arguments are ready. create the new vector stmt.  */
1806               new_stmt = gimple_build_call (builtin_decl, 1, vop0);
1807               new_temp = make_ssa_name (vec_dest, new_stmt);
1808               gimple_call_set_lhs (new_stmt, new_temp);
1809               vect_finish_stmt_generation (stmt, new_stmt, gsi);
1810               if (slp_node)
1811                 VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
1812             }
1813
1814           if (j == 0)
1815             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
1816           else
1817             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1818           prev_stmt_info = vinfo_for_stmt (new_stmt);
1819         }
1820       break;
1821
1822     case WIDEN:
1823       /* In case the vectorization factor (VF) is bigger than the number
1824          of elements that we can fit in a vectype (nunits), we have to
1825          generate more than one vector stmt - i.e - we need to "unroll"
1826          the vector stmt by a factor VF/nunits.  */
1827       for (j = 0; j < ncopies; j++)
1828         {
1829           if (j == 0)
1830             vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
1831           else
1832             vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
1833
1834           /* Generate first half of the widened result:  */
1835           new_stmt
1836             = vect_gen_widened_results_half (code1, decl1,
1837                                              vec_oprnd0, vec_oprnd1,
1838                                              unary_op, vec_dest, gsi, stmt);
1839           if (j == 0)
1840             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
1841           else
1842             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1843           prev_stmt_info = vinfo_for_stmt (new_stmt);
1844
1845           /* Generate second half of the widened result:  */
1846           new_stmt
1847             = vect_gen_widened_results_half (code2, decl2,
1848                                              vec_oprnd0, vec_oprnd1,
1849                                              unary_op, vec_dest, gsi, stmt);
1850           STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1851           prev_stmt_info = vinfo_for_stmt (new_stmt);
1852         }
1853       break;
1854
1855     case NARROW:
1856       /* In case the vectorization factor (VF) is bigger than the number
1857          of elements that we can fit in a vectype (nunits), we have to
1858          generate more than one vector stmt - i.e - we need to "unroll"
1859          the vector stmt by a factor VF/nunits.  */
1860       for (j = 0; j < ncopies; j++)
1861         {
1862           /* Handle uses.  */
1863           if (j == 0)
1864             {
1865               vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
1866               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
1867             }
1868           else
1869             {
1870               vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd1);
1871               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
1872             }
1873
1874           /* Arguments are ready.  Create the new vector stmt.  */
1875           new_stmt = gimple_build_assign_with_ops (code1, vec_dest, vec_oprnd0,
1876                                                    vec_oprnd1);
1877           new_temp = make_ssa_name (vec_dest, new_stmt);
1878           gimple_assign_set_lhs (new_stmt, new_temp);
1879           vect_finish_stmt_generation (stmt, new_stmt, gsi);
1880
1881           if (j == 0)
1882             STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
1883           else
1884             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
1885
1886           prev_stmt_info = vinfo_for_stmt (new_stmt);
1887         }
1888
1889       *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
1890     }
1891
1892   if (vec_oprnds0)
1893     VEC_free (tree, heap, vec_oprnds0);
1894
1895   return true;
1896 }
1897
1898
1899 /* Function vectorizable_assignment.
1900
1901    Check if STMT performs an assignment (copy) that can be vectorized.
1902    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
1903    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
1904    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
1905
1906 static bool
1907 vectorizable_assignment (gimple stmt, gimple_stmt_iterator *gsi,
1908                          gimple *vec_stmt, slp_tree slp_node)
1909 {
1910   tree vec_dest;
1911   tree scalar_dest;
1912   tree op;
1913   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
1914   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
1915   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
1916   tree new_temp;
1917   tree def;
1918   gimple def_stmt;
1919   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
1920   unsigned int nunits = TYPE_VECTOR_SUBPARTS (vectype);
1921   int ncopies;
1922   int i, j;
1923   VEC(tree,heap) *vec_oprnds = NULL;
1924   tree vop;
1925   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
1926   gimple new_stmt = NULL;
1927   stmt_vec_info prev_stmt_info = NULL;
1928   enum tree_code code;
1929   tree vectype_in;
1930
1931   /* Multiple types in SLP are handled by creating the appropriate number of
1932      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
1933      case of SLP.  */
1934   if (slp_node)
1935     ncopies = 1;
1936   else
1937     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
1938
1939   gcc_assert (ncopies >= 1);
1940
1941   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
1942     return false;
1943
1944   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
1945     return false;
1946
1947   /* Is vectorizable assignment?  */
1948   if (!is_gimple_assign (stmt))
1949     return false;
1950
1951   scalar_dest = gimple_assign_lhs (stmt);
1952   if (TREE_CODE (scalar_dest) != SSA_NAME)
1953     return false;
1954
1955   code = gimple_assign_rhs_code (stmt);
1956   if (gimple_assign_single_p (stmt)
1957       || code == PAREN_EXPR
1958       || CONVERT_EXPR_CODE_P (code))
1959     op = gimple_assign_rhs1 (stmt);
1960   else
1961     return false;
1962
1963   if (!vect_is_simple_use_1 (op, loop_vinfo, bb_vinfo,
1964                              &def_stmt, &def, &dt[0], &vectype_in))
1965     {
1966       if (vect_print_dump_info (REPORT_DETAILS))
1967         fprintf (vect_dump, "use not simple.");
1968       return false;
1969     }
1970
1971   /* We can handle NOP_EXPR conversions that do not change the number
1972      of elements or the vector size.  */
1973   if (CONVERT_EXPR_CODE_P (code)
1974       && (!vectype_in
1975           || TYPE_VECTOR_SUBPARTS (vectype_in) != nunits
1976           || (GET_MODE_SIZE (TYPE_MODE (vectype))
1977               != GET_MODE_SIZE (TYPE_MODE (vectype_in)))))
1978     return false;
1979
1980   if (!vec_stmt) /* transformation not required.  */
1981     {
1982       STMT_VINFO_TYPE (stmt_info) = assignment_vec_info_type;
1983       if (vect_print_dump_info (REPORT_DETAILS))
1984         fprintf (vect_dump, "=== vectorizable_assignment ===");
1985       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
1986       return true;
1987     }
1988
1989   /** Transform.  **/
1990   if (vect_print_dump_info (REPORT_DETAILS))
1991     fprintf (vect_dump, "transform assignment.");
1992
1993   /* Handle def.  */
1994   vec_dest = vect_create_destination_var (scalar_dest, vectype);
1995
1996   /* Handle use.  */
1997   for (j = 0; j < ncopies; j++)
1998     {
1999       /* Handle uses.  */
2000       if (j == 0)
2001         vect_get_vec_defs (op, NULL, stmt, &vec_oprnds, NULL, slp_node);
2002       else
2003         vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds, NULL);
2004
2005       /* Arguments are ready. create the new vector stmt.  */
2006       FOR_EACH_VEC_ELT (tree, vec_oprnds, i, vop)
2007        {
2008          if (CONVERT_EXPR_CODE_P (code))
2009            vop = build1 (VIEW_CONVERT_EXPR, vectype, vop);
2010          new_stmt = gimple_build_assign (vec_dest, vop);
2011          new_temp = make_ssa_name (vec_dest, new_stmt);
2012          gimple_assign_set_lhs (new_stmt, new_temp);
2013          vect_finish_stmt_generation (stmt, new_stmt, gsi);
2014          if (slp_node)
2015            VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2016        }
2017
2018       if (slp_node)
2019         continue;
2020
2021       if (j == 0)
2022         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
2023       else
2024         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2025
2026       prev_stmt_info = vinfo_for_stmt (new_stmt);
2027     }
2028
2029   VEC_free (tree, heap, vec_oprnds);
2030   return true;
2031 }
2032
2033
2034 /* Function vectorizable_shift.
2035
2036    Check if STMT performs a shift operation that can be vectorized.
2037    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2038    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2039    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2040
2041 static bool
2042 vectorizable_shift (gimple stmt, gimple_stmt_iterator *gsi,
2043                     gimple *vec_stmt, slp_tree slp_node)
2044 {
2045   tree vec_dest;
2046   tree scalar_dest;
2047   tree op0, op1 = NULL;
2048   tree vec_oprnd1 = NULL_TREE;
2049   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2050   tree vectype;
2051   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2052   enum tree_code code;
2053   enum machine_mode vec_mode;
2054   tree new_temp;
2055   optab optab;
2056   int icode;
2057   enum machine_mode optab_op2_mode;
2058   tree def;
2059   gimple def_stmt;
2060   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2061   gimple new_stmt = NULL;
2062   stmt_vec_info prev_stmt_info;
2063   int nunits_in;
2064   int nunits_out;
2065   tree vectype_out;
2066   int ncopies;
2067   int j, i;
2068   VEC (tree, heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
2069   tree vop0, vop1;
2070   unsigned int k;
2071   bool scalar_shift_arg = false;
2072   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2073   int vf;
2074
2075   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
2076     return false;
2077
2078   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2079     return false;
2080
2081   /* Is STMT a vectorizable binary/unary operation?   */
2082   if (!is_gimple_assign (stmt))
2083     return false;
2084
2085   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2086     return false;
2087
2088   code = gimple_assign_rhs_code (stmt);
2089
2090   if (!(code == LSHIFT_EXPR || code == RSHIFT_EXPR || code == LROTATE_EXPR
2091       || code == RROTATE_EXPR))
2092     return false;
2093
2094   scalar_dest = gimple_assign_lhs (stmt);
2095   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
2096
2097   op0 = gimple_assign_rhs1 (stmt);
2098   if (!vect_is_simple_use_1 (op0, loop_vinfo, bb_vinfo,
2099                              &def_stmt, &def, &dt[0], &vectype))
2100     {
2101       if (vect_print_dump_info (REPORT_DETAILS))
2102         fprintf (vect_dump, "use not simple.");
2103       return false;
2104     }
2105   /* If op0 is an external or constant def use a vector type with
2106      the same size as the output vector type.  */
2107   if (!vectype)
2108     vectype = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
2109   if (vec_stmt)
2110     gcc_assert (vectype);
2111   if (!vectype)
2112     {
2113       if (vect_print_dump_info (REPORT_DETAILS))
2114         {
2115           fprintf (vect_dump, "no vectype for scalar type ");
2116           print_generic_expr (vect_dump, TREE_TYPE (op0), TDF_SLIM);
2117         }
2118
2119       return false;
2120     }
2121
2122   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
2123   nunits_in = TYPE_VECTOR_SUBPARTS (vectype);
2124   if (nunits_out != nunits_in)
2125     return false;
2126
2127   op1 = gimple_assign_rhs2 (stmt);
2128   if (!vect_is_simple_use (op1, loop_vinfo, bb_vinfo, &def_stmt, &def, &dt[1]))
2129     {
2130       if (vect_print_dump_info (REPORT_DETAILS))
2131         fprintf (vect_dump, "use not simple.");
2132       return false;
2133     }
2134
2135   if (loop_vinfo)
2136     vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2137   else
2138     vf = 1;
2139
2140   /* Multiple types in SLP are handled by creating the appropriate number of
2141      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
2142      case of SLP.  */
2143   if (slp_node)
2144     ncopies = 1;
2145   else
2146     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
2147
2148   gcc_assert (ncopies >= 1);
2149
2150   /* Determine whether the shift amount is a vector, or scalar.  If the
2151      shift/rotate amount is a vector, use the vector/vector shift optabs.  */
2152
2153   /* Vector shifted by vector.  */
2154   if (dt[1] == vect_internal_def)
2155     {
2156       optab = optab_for_tree_code (code, vectype, optab_vector);
2157       if (vect_print_dump_info (REPORT_DETAILS))
2158         fprintf (vect_dump, "vector/vector shift/rotate found.");
2159     }
2160   /* See if the machine has a vector shifted by scalar insn and if not
2161      then see if it has a vector shifted by vector insn.  */
2162   else if (dt[1] == vect_constant_def || dt[1] == vect_external_def)
2163     {
2164       optab = optab_for_tree_code (code, vectype, optab_scalar);
2165       if (optab
2166           && optab_handler (optab, TYPE_MODE (vectype)) != CODE_FOR_nothing)
2167         {
2168           scalar_shift_arg = true;
2169           if (vect_print_dump_info (REPORT_DETAILS))
2170             fprintf (vect_dump, "vector/scalar shift/rotate found.");
2171         }
2172       else
2173         {
2174           optab = optab_for_tree_code (code, vectype, optab_vector);
2175           if (optab
2176                && (optab_handler (optab, TYPE_MODE (vectype))
2177                       != CODE_FOR_nothing))
2178             {
2179               if (vect_print_dump_info (REPORT_DETAILS))
2180                 fprintf (vect_dump, "vector/vector shift/rotate found.");
2181
2182               /* Unlike the other binary operators, shifts/rotates have
2183                  the rhs being int, instead of the same type as the lhs,
2184                  so make sure the scalar is the right type if we are
2185                  dealing with vectors of short/char.  */
2186               if (dt[1] == vect_constant_def)
2187                 op1 = fold_convert (TREE_TYPE (vectype), op1);
2188             }
2189         }
2190     }
2191   else
2192     {
2193       if (vect_print_dump_info (REPORT_DETAILS))
2194         fprintf (vect_dump, "operand mode requires invariant argument.");
2195       return false;
2196     }
2197
2198   /* Supportable by target?  */
2199   if (!optab)
2200     {
2201       if (vect_print_dump_info (REPORT_DETAILS))
2202         fprintf (vect_dump, "no optab.");
2203       return false;
2204     }
2205   vec_mode = TYPE_MODE (vectype);
2206   icode = (int) optab_handler (optab, vec_mode);
2207   if (icode == CODE_FOR_nothing)
2208     {
2209       if (vect_print_dump_info (REPORT_DETAILS))
2210         fprintf (vect_dump, "op not supported by target.");
2211       /* Check only during analysis.  */
2212       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
2213           || (vf < vect_min_worthwhile_factor (code)
2214               && !vec_stmt))
2215         return false;
2216       if (vect_print_dump_info (REPORT_DETAILS))
2217         fprintf (vect_dump, "proceeding using word mode.");
2218     }
2219
2220   /* Worthwhile without SIMD support?  Check only during analysis.  */
2221   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
2222       && vf < vect_min_worthwhile_factor (code)
2223       && !vec_stmt)
2224     {
2225       if (vect_print_dump_info (REPORT_DETAILS))
2226         fprintf (vect_dump, "not worthwhile without SIMD support.");
2227       return false;
2228     }
2229
2230   if (!vec_stmt) /* transformation not required.  */
2231     {
2232       STMT_VINFO_TYPE (stmt_info) = shift_vec_info_type;
2233       if (vect_print_dump_info (REPORT_DETAILS))
2234         fprintf (vect_dump, "=== vectorizable_shift ===");
2235       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
2236       return true;
2237     }
2238
2239   /** Transform.  **/
2240
2241   if (vect_print_dump_info (REPORT_DETAILS))
2242     fprintf (vect_dump, "transform binary/unary operation.");
2243
2244   /* Handle def.  */
2245   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2246
2247   /* Allocate VECs for vector operands.  In case of SLP, vector operands are
2248      created in the previous stages of the recursion, so no allocation is
2249      needed, except for the case of shift with scalar shift argument.  In that
2250      case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
2251      be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
2252      In case of loop-based vectorization we allocate VECs of size 1.  We
2253      allocate VEC_OPRNDS1 only in case of binary operation.  */
2254   if (!slp_node)
2255     {
2256       vec_oprnds0 = VEC_alloc (tree, heap, 1);
2257       vec_oprnds1 = VEC_alloc (tree, heap, 1);
2258     }
2259   else if (scalar_shift_arg)
2260     vec_oprnds1 = VEC_alloc (tree, heap, slp_node->vec_stmts_size);
2261
2262   prev_stmt_info = NULL;
2263   for (j = 0; j < ncopies; j++)
2264     {
2265       /* Handle uses.  */
2266       if (j == 0)
2267         {
2268           if (scalar_shift_arg)
2269             {
2270               /* Vector shl and shr insn patterns can be defined with scalar
2271                  operand 2 (shift operand).  In this case, use constant or loop
2272                  invariant op1 directly, without extending it to vector mode
2273                  first.  */
2274               optab_op2_mode = insn_data[icode].operand[2].mode;
2275               if (!VECTOR_MODE_P (optab_op2_mode))
2276                 {
2277                   if (vect_print_dump_info (REPORT_DETAILS))
2278                     fprintf (vect_dump, "operand 1 using scalar mode.");
2279                   vec_oprnd1 = op1;
2280                   VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2281                   if (slp_node)
2282                     {
2283                       /* Store vec_oprnd1 for every vector stmt to be created
2284                          for SLP_NODE.  We check during the analysis that all
2285                          the shift arguments are the same.
2286                          TODO: Allow different constants for different vector
2287                          stmts generated for an SLP instance.  */
2288                       for (k = 0; k < slp_node->vec_stmts_size - 1; k++)
2289                         VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
2290                     }
2291                 }
2292             }
2293
2294           /* vec_oprnd1 is available if operand 1 should be of a scalar-type
2295              (a special case for certain kind of vector shifts); otherwise,
2296              operand 1 should be of a vector type (the usual case).  */
2297           if (vec_oprnd1)
2298             vect_get_vec_defs (op0, NULL_TREE, stmt, &vec_oprnds0, NULL,
2299                                slp_node);
2300           else
2301             vect_get_vec_defs (op0, op1, stmt, &vec_oprnds0, &vec_oprnds1,
2302                                slp_node);
2303         }
2304       else
2305         vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, &vec_oprnds1);
2306
2307       /* Arguments are ready.  Create the new vector stmt.  */
2308       FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
2309         {
2310           vop1 = VEC_index (tree, vec_oprnds1, i);
2311           new_stmt = gimple_build_assign_with_ops (code, vec_dest, vop0, vop1);
2312           new_temp = make_ssa_name (vec_dest, new_stmt);
2313           gimple_assign_set_lhs (new_stmt, new_temp);
2314           vect_finish_stmt_generation (stmt, new_stmt, gsi);
2315           if (slp_node)
2316             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2317         }
2318
2319       if (slp_node)
2320         continue;
2321
2322       if (j == 0)
2323         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
2324       else
2325         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2326       prev_stmt_info = vinfo_for_stmt (new_stmt);
2327     }
2328
2329   VEC_free (tree, heap, vec_oprnds0);
2330   VEC_free (tree, heap, vec_oprnds1);
2331
2332   return true;
2333 }
2334
2335
2336 /* Function vectorizable_operation.
2337
2338    Check if STMT performs a binary or unary operation that can be vectorized.
2339    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2340    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2341    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2342
2343 static bool
2344 vectorizable_operation (gimple stmt, gimple_stmt_iterator *gsi,
2345                         gimple *vec_stmt, slp_tree slp_node)
2346 {
2347   tree vec_dest;
2348   tree scalar_dest;
2349   tree op0, op1 = NULL;
2350   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2351   tree vectype;
2352   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2353   enum tree_code code;
2354   enum machine_mode vec_mode;
2355   tree new_temp;
2356   int op_type;
2357   optab optab;
2358   int icode;
2359   tree def;
2360   gimple def_stmt;
2361   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2362   gimple new_stmt = NULL;
2363   stmt_vec_info prev_stmt_info;
2364   int nunits_in;
2365   int nunits_out;
2366   tree vectype_out;
2367   int ncopies;
2368   int j, i;
2369   VEC(tree,heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
2370   tree vop0, vop1;
2371   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
2372   int vf;
2373
2374   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
2375     return false;
2376
2377   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2378     return false;
2379
2380   /* Is STMT a vectorizable binary/unary operation?   */
2381   if (!is_gimple_assign (stmt))
2382     return false;
2383
2384   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2385     return false;
2386
2387   code = gimple_assign_rhs_code (stmt);
2388
2389   /* For pointer addition, we should use the normal plus for
2390      the vector addition.  */
2391   if (code == POINTER_PLUS_EXPR)
2392     code = PLUS_EXPR;
2393
2394   /* Support only unary or binary operations.  */
2395   op_type = TREE_CODE_LENGTH (code);
2396   if (op_type != unary_op && op_type != binary_op)
2397     {
2398       if (vect_print_dump_info (REPORT_DETAILS))
2399         fprintf (vect_dump, "num. args = %d (not unary/binary op).", op_type);
2400       return false;
2401     }
2402
2403   scalar_dest = gimple_assign_lhs (stmt);
2404   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
2405
2406   op0 = gimple_assign_rhs1 (stmt);
2407   if (!vect_is_simple_use_1 (op0, loop_vinfo, bb_vinfo,
2408                              &def_stmt, &def, &dt[0], &vectype))
2409     {
2410       if (vect_print_dump_info (REPORT_DETAILS))
2411         fprintf (vect_dump, "use not simple.");
2412       return false;
2413     }
2414   /* If op0 is an external or constant def use a vector type with
2415      the same size as the output vector type.  */
2416   if (!vectype)
2417     vectype = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
2418   if (vec_stmt)
2419     gcc_assert (vectype);
2420   if (!vectype)
2421     {
2422       if (vect_print_dump_info (REPORT_DETAILS))
2423         {
2424           fprintf (vect_dump, "no vectype for scalar type ");
2425           print_generic_expr (vect_dump, TREE_TYPE (op0), TDF_SLIM);
2426         }
2427
2428       return false;
2429     }
2430
2431   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
2432   nunits_in = TYPE_VECTOR_SUBPARTS (vectype);
2433   if (nunits_out != nunits_in)
2434     return false;
2435
2436   if (op_type == binary_op)
2437     {
2438       op1 = gimple_assign_rhs2 (stmt);
2439       if (!vect_is_simple_use (op1, loop_vinfo, bb_vinfo, &def_stmt, &def,
2440                                &dt[1]))
2441         {
2442           if (vect_print_dump_info (REPORT_DETAILS))
2443             fprintf (vect_dump, "use not simple.");
2444           return false;
2445         }
2446     }
2447
2448   if (loop_vinfo)
2449     vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
2450   else
2451     vf = 1;
2452
2453   /* Multiple types in SLP are handled by creating the appropriate number of
2454      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
2455      case of SLP.  */
2456   if (slp_node)
2457     ncopies = 1;
2458   else
2459     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
2460
2461   gcc_assert (ncopies >= 1);
2462
2463   /* Shifts are handled in vectorizable_shift ().  */
2464   if (code == LSHIFT_EXPR || code == RSHIFT_EXPR || code == LROTATE_EXPR
2465       || code == RROTATE_EXPR)
2466    return false;
2467
2468  optab = optab_for_tree_code (code, vectype, optab_default);
2469
2470   /* Supportable by target?  */
2471   if (!optab)
2472     {
2473       if (vect_print_dump_info (REPORT_DETAILS))
2474         fprintf (vect_dump, "no optab.");
2475       return false;
2476     }
2477   vec_mode = TYPE_MODE (vectype);
2478   icode = (int) optab_handler (optab, vec_mode);
2479   if (icode == CODE_FOR_nothing)
2480     {
2481       if (vect_print_dump_info (REPORT_DETAILS))
2482         fprintf (vect_dump, "op not supported by target.");
2483       /* Check only during analysis.  */
2484       if (GET_MODE_SIZE (vec_mode) != UNITS_PER_WORD
2485           || (vf < vect_min_worthwhile_factor (code)
2486               && !vec_stmt))
2487         return false;
2488       if (vect_print_dump_info (REPORT_DETAILS))
2489         fprintf (vect_dump, "proceeding using word mode.");
2490     }
2491
2492   /* Worthwhile without SIMD support?  Check only during analysis.  */
2493   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
2494       && vf < vect_min_worthwhile_factor (code)
2495       && !vec_stmt)
2496     {
2497       if (vect_print_dump_info (REPORT_DETAILS))
2498         fprintf (vect_dump, "not worthwhile without SIMD support.");
2499       return false;
2500     }
2501
2502   if (!vec_stmt) /* transformation not required.  */
2503     {
2504       STMT_VINFO_TYPE (stmt_info) = op_vec_info_type;
2505       if (vect_print_dump_info (REPORT_DETAILS))
2506         fprintf (vect_dump, "=== vectorizable_operation ===");
2507       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
2508       return true;
2509     }
2510
2511   /** Transform.  **/
2512
2513   if (vect_print_dump_info (REPORT_DETAILS))
2514     fprintf (vect_dump, "transform binary/unary operation.");
2515
2516   /* Handle def.  */
2517   vec_dest = vect_create_destination_var (scalar_dest, vectype);
2518
2519   /* Allocate VECs for vector operands.  In case of SLP, vector operands are
2520      created in the previous stages of the recursion, so no allocation is
2521      needed, except for the case of shift with scalar shift argument.  In that
2522      case we store the scalar operand in VEC_OPRNDS1 for every vector stmt to
2523      be created to vectorize the SLP group, i.e., SLP_NODE->VEC_STMTS_SIZE.
2524      In case of loop-based vectorization we allocate VECs of size 1.  We
2525      allocate VEC_OPRNDS1 only in case of binary operation.  */
2526   if (!slp_node)
2527     {
2528       vec_oprnds0 = VEC_alloc (tree, heap, 1);
2529       if (op_type == binary_op)
2530         vec_oprnds1 = VEC_alloc (tree, heap, 1);
2531     }
2532
2533   /* In case the vectorization factor (VF) is bigger than the number
2534      of elements that we can fit in a vectype (nunits), we have to generate
2535      more than one vector stmt - i.e - we need to "unroll" the
2536      vector stmt by a factor VF/nunits.  In doing so, we record a pointer
2537      from one copy of the vector stmt to the next, in the field
2538      STMT_VINFO_RELATED_STMT.  This is necessary in order to allow following
2539      stages to find the correct vector defs to be used when vectorizing
2540      stmts that use the defs of the current stmt.  The example below
2541      illustrates the vectorization process when VF=16 and nunits=4 (i.e.,
2542      we need to create 4 vectorized stmts):
2543
2544      before vectorization:
2545                                 RELATED_STMT    VEC_STMT
2546         S1:     x = memref      -               -
2547         S2:     z = x + 1       -               -
2548
2549      step 1: vectorize stmt S1 (done in vectorizable_load. See more details
2550              there):
2551                                 RELATED_STMT    VEC_STMT
2552         VS1_0:  vx0 = memref0   VS1_1           -
2553         VS1_1:  vx1 = memref1   VS1_2           -
2554         VS1_2:  vx2 = memref2   VS1_3           -
2555         VS1_3:  vx3 = memref3   -               -
2556         S1:     x = load        -               VS1_0
2557         S2:     z = x + 1       -               -
2558
2559      step2: vectorize stmt S2 (done here):
2560         To vectorize stmt S2 we first need to find the relevant vector
2561         def for the first operand 'x'.  This is, as usual, obtained from
2562         the vector stmt recorded in the STMT_VINFO_VEC_STMT of the stmt
2563         that defines 'x' (S1).  This way we find the stmt VS1_0, and the
2564         relevant vector def 'vx0'.  Having found 'vx0' we can generate
2565         the vector stmt VS2_0, and as usual, record it in the
2566         STMT_VINFO_VEC_STMT of stmt S2.
2567         When creating the second copy (VS2_1), we obtain the relevant vector
2568         def from the vector stmt recorded in the STMT_VINFO_RELATED_STMT of
2569         stmt VS1_0.  This way we find the stmt VS1_1 and the relevant
2570         vector def 'vx1'.  Using 'vx1' we create stmt VS2_1 and record a
2571         pointer to it in the STMT_VINFO_RELATED_STMT of the vector stmt VS2_0.
2572         Similarly when creating stmts VS2_2 and VS2_3.  This is the resulting
2573         chain of stmts and pointers:
2574                                 RELATED_STMT    VEC_STMT
2575         VS1_0:  vx0 = memref0   VS1_1           -
2576         VS1_1:  vx1 = memref1   VS1_2           -
2577         VS1_2:  vx2 = memref2   VS1_3           -
2578         VS1_3:  vx3 = memref3   -               -
2579         S1:     x = load        -               VS1_0
2580         VS2_0:  vz0 = vx0 + v1  VS2_1           -
2581         VS2_1:  vz1 = vx1 + v1  VS2_2           -
2582         VS2_2:  vz2 = vx2 + v1  VS2_3           -
2583         VS2_3:  vz3 = vx3 + v1  -               -
2584         S2:     z = x + 1       -               VS2_0  */
2585
2586   prev_stmt_info = NULL;
2587   for (j = 0; j < ncopies; j++)
2588     {
2589       /* Handle uses.  */
2590       if (j == 0)
2591         {
2592           if (op_type == binary_op)
2593             vect_get_vec_defs (op0, op1, stmt, &vec_oprnds0, &vec_oprnds1,
2594                                slp_node);
2595           else
2596             vect_get_vec_defs (op0, NULL_TREE, stmt, &vec_oprnds0, NULL,
2597                                slp_node);
2598         }
2599       else
2600         vect_get_vec_defs_for_stmt_copy (dt, &vec_oprnds0, &vec_oprnds1);
2601
2602       /* Arguments are ready.  Create the new vector stmt.  */
2603       FOR_EACH_VEC_ELT (tree, vec_oprnds0, i, vop0)
2604         {
2605           vop1 = ((op_type == binary_op)
2606                   ? VEC_index (tree, vec_oprnds1, i) : NULL);
2607           new_stmt = gimple_build_assign_with_ops (code, vec_dest, vop0, vop1);
2608           new_temp = make_ssa_name (vec_dest, new_stmt);
2609           gimple_assign_set_lhs (new_stmt, new_temp);
2610           vect_finish_stmt_generation (stmt, new_stmt, gsi);
2611           if (slp_node)
2612             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2613         }
2614
2615       if (slp_node)
2616         continue;
2617
2618       if (j == 0)
2619         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
2620       else
2621         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
2622       prev_stmt_info = vinfo_for_stmt (new_stmt);
2623     }
2624
2625   VEC_free (tree, heap, vec_oprnds0);
2626   if (vec_oprnds1)
2627     VEC_free (tree, heap, vec_oprnds1);
2628
2629   return true;
2630 }
2631
2632
2633 /* Get vectorized definitions for loop-based vectorization.  For the first
2634    operand we call vect_get_vec_def_for_operand() (with OPRND containing
2635    scalar operand), and for the rest we get a copy with
2636    vect_get_vec_def_for_stmt_copy() using the previous vector definition
2637    (stored in OPRND). See vect_get_vec_def_for_stmt_copy() for details.
2638    The vectors are collected into VEC_OPRNDS.  */
2639
2640 static void
2641 vect_get_loop_based_defs (tree *oprnd, gimple stmt, enum vect_def_type dt,
2642                           VEC (tree, heap) **vec_oprnds, int multi_step_cvt)
2643 {
2644   tree vec_oprnd;
2645
2646   /* Get first vector operand.  */
2647   /* All the vector operands except the very first one (that is scalar oprnd)
2648      are stmt copies.  */
2649   if (TREE_CODE (TREE_TYPE (*oprnd)) != VECTOR_TYPE)
2650     vec_oprnd = vect_get_vec_def_for_operand (*oprnd, stmt, NULL);
2651   else
2652     vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, *oprnd);
2653
2654   VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
2655
2656   /* Get second vector operand.  */
2657   vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, vec_oprnd);
2658   VEC_quick_push (tree, *vec_oprnds, vec_oprnd);
2659
2660   *oprnd = vec_oprnd;
2661
2662   /* For conversion in multiple steps, continue to get operands
2663      recursively.  */
2664   if (multi_step_cvt)
2665     vect_get_loop_based_defs (oprnd, stmt, dt, vec_oprnds,  multi_step_cvt - 1);
2666 }
2667
2668
2669 /* Create vectorized demotion statements for vector operands from VEC_OPRNDS.
2670    For multi-step conversions store the resulting vectors and call the function
2671    recursively.  */
2672
2673 static void
2674 vect_create_vectorized_demotion_stmts (VEC (tree, heap) **vec_oprnds,
2675                                        int multi_step_cvt, gimple stmt,
2676                                        VEC (tree, heap) *vec_dsts,
2677                                        gimple_stmt_iterator *gsi,
2678                                        slp_tree slp_node, enum tree_code code,
2679                                        stmt_vec_info *prev_stmt_info)
2680 {
2681   unsigned int i;
2682   tree vop0, vop1, new_tmp, vec_dest;
2683   gimple new_stmt;
2684   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2685
2686   vec_dest = VEC_pop (tree, vec_dsts);
2687
2688   for (i = 0; i < VEC_length (tree, *vec_oprnds); i += 2)
2689     {
2690       /* Create demotion operation.  */
2691       vop0 = VEC_index (tree, *vec_oprnds, i);
2692       vop1 = VEC_index (tree, *vec_oprnds, i + 1);
2693       new_stmt = gimple_build_assign_with_ops (code, vec_dest, vop0, vop1);
2694       new_tmp = make_ssa_name (vec_dest, new_stmt);
2695       gimple_assign_set_lhs (new_stmt, new_tmp);
2696       vect_finish_stmt_generation (stmt, new_stmt, gsi);
2697
2698       if (multi_step_cvt)
2699         /* Store the resulting vector for next recursive call.  */
2700         VEC_replace (tree, *vec_oprnds, i/2, new_tmp);
2701       else
2702         {
2703           /* This is the last step of the conversion sequence. Store the
2704              vectors in SLP_NODE or in vector info of the scalar statement
2705              (or in STMT_VINFO_RELATED_STMT chain).  */
2706           if (slp_node)
2707             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
2708           else
2709             {
2710               if (!*prev_stmt_info)
2711                 STMT_VINFO_VEC_STMT (stmt_info) = new_stmt;
2712               else
2713                 STMT_VINFO_RELATED_STMT (*prev_stmt_info) = new_stmt;
2714
2715               *prev_stmt_info = vinfo_for_stmt (new_stmt);
2716             }
2717         }
2718     }
2719
2720   /* For multi-step demotion operations we first generate demotion operations
2721      from the source type to the intermediate types, and then combine the
2722      results (stored in VEC_OPRNDS) in demotion operation to the destination
2723      type.  */
2724   if (multi_step_cvt)
2725     {
2726       /* At each level of recursion we have have of the operands we had at the
2727          previous level.  */
2728       VEC_truncate (tree, *vec_oprnds, (i+1)/2);
2729       vect_create_vectorized_demotion_stmts (vec_oprnds, multi_step_cvt - 1,
2730                                              stmt, vec_dsts, gsi, slp_node,
2731                                              code, prev_stmt_info);
2732     }
2733 }
2734
2735
2736 /* Function vectorizable_type_demotion
2737
2738    Check if STMT performs a binary or unary operation that involves
2739    type demotion, and if it can be vectorized.
2740    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
2741    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
2742    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
2743
2744 static bool
2745 vectorizable_type_demotion (gimple stmt, gimple_stmt_iterator *gsi,
2746                             gimple *vec_stmt, slp_tree slp_node)
2747 {
2748   tree vec_dest;
2749   tree scalar_dest;
2750   tree op0;
2751   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2752   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
2753   enum tree_code code, code1 = ERROR_MARK;
2754   tree def;
2755   gimple def_stmt;
2756   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
2757   stmt_vec_info prev_stmt_info;
2758   int nunits_in;
2759   int nunits_out;
2760   tree vectype_out;
2761   int ncopies;
2762   int j, i;
2763   tree vectype_in;
2764   int multi_step_cvt = 0;
2765   VEC (tree, heap) *vec_oprnds0 = NULL;
2766   VEC (tree, heap) *vec_dsts = NULL, *interm_types = NULL, *tmp_vec_dsts = NULL;
2767   tree last_oprnd, intermediate_type;
2768
2769   /* FORNOW: not supported by basic block SLP vectorization.  */
2770   gcc_assert (loop_vinfo);
2771
2772   if (!STMT_VINFO_RELEVANT_P (stmt_info))
2773     return false;
2774
2775   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
2776     return false;
2777
2778   /* Is STMT a vectorizable type-demotion operation?  */
2779   if (!is_gimple_assign (stmt))
2780     return false;
2781
2782   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
2783     return false;
2784
2785   code = gimple_assign_rhs_code (stmt);
2786   if (!CONVERT_EXPR_CODE_P (code))
2787     return false;
2788
2789   scalar_dest = gimple_assign_lhs (stmt);
2790   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
2791
2792   /* Check the operands of the operation.  */
2793   op0 = gimple_assign_rhs1 (stmt);
2794   if (! ((INTEGRAL_TYPE_P (TREE_TYPE (scalar_dest))
2795           && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
2796          || (SCALAR_FLOAT_TYPE_P (TREE_TYPE (scalar_dest))
2797              && SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0))
2798              && CONVERT_EXPR_CODE_P (code))))
2799     return false;
2800   if (!vect_is_simple_use_1 (op0, loop_vinfo, NULL,
2801                              &def_stmt, &def, &dt[0], &vectype_in))
2802     {
2803       if (vect_print_dump_info (REPORT_DETAILS))
2804         fprintf (vect_dump, "use not simple.");
2805       return false;
2806     }
2807   /* If op0 is an external def use a vector type with the
2808      same size as the output vector type if possible.  */
2809   if (!vectype_in)
2810     vectype_in = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
2811   if (vec_stmt)
2812     gcc_assert (vectype_in);
2813   if (!vectype_in)
2814     {
2815       if (vect_print_dump_info (REPORT_DETAILS))
2816         {
2817           fprintf (vect_dump, "no vectype for scalar type ");
2818           print_generic_expr (vect_dump, TREE_TYPE (op0), TDF_SLIM);
2819         }
2820
2821       return false;
2822     }
2823
2824   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
2825   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
2826   if (nunits_in >= nunits_out)
2827     return false;
2828
2829   /* Multiple types in SLP are handled by creating the appropriate number of
2830      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
2831      case of SLP.  */
2832   if (slp_node)
2833     ncopies = 1;
2834   else
2835     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_out;
2836   gcc_assert (ncopies >= 1);
2837
2838   /* Supportable by target?  */
2839   if (!supportable_narrowing_operation (code, vectype_out, vectype_in,
2840                                         &code1, &multi_step_cvt, &interm_types))
2841     return false;
2842
2843   if (!vec_stmt) /* transformation not required.  */
2844     {
2845       STMT_VINFO_TYPE (stmt_info) = type_demotion_vec_info_type;
2846       if (vect_print_dump_info (REPORT_DETAILS))
2847         fprintf (vect_dump, "=== vectorizable_demotion ===");
2848       vect_model_simple_cost (stmt_info, ncopies, dt, NULL);
2849       return true;
2850     }
2851
2852   /** Transform.  **/
2853   if (vect_print_dump_info (REPORT_DETAILS))
2854     fprintf (vect_dump, "transform type demotion operation. ncopies = %d.",
2855              ncopies);
2856
2857   /* In case of multi-step demotion, we first generate demotion operations to
2858      the intermediate types, and then from that types to the final one.
2859      We create vector destinations for the intermediate type (TYPES) received
2860      from supportable_narrowing_operation, and store them in the correct order
2861      for future use in vect_create_vectorized_demotion_stmts().  */
2862   if (multi_step_cvt)
2863     vec_dsts = VEC_alloc (tree, heap, multi_step_cvt + 1);
2864   else
2865     vec_dsts = VEC_alloc (tree, heap, 1);
2866
2867   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
2868   VEC_quick_push (tree, vec_dsts, vec_dest);
2869
2870   if (multi_step_cvt)
2871     {
2872       for (i = VEC_length (tree, interm_types) - 1;
2873            VEC_iterate (tree, interm_types, i, intermediate_type); i--)
2874         {
2875           vec_dest = vect_create_destination_var (scalar_dest,
2876                                                   intermediate_type);
2877           VEC_quick_push (tree, vec_dsts, vec_dest);
2878         }
2879     }
2880
2881   /* In case the vectorization factor (VF) is bigger than the number
2882      of elements that we can fit in a vectype (nunits), we have to generate
2883      more than one vector stmt - i.e - we need to "unroll" the
2884      vector stmt by a factor VF/nunits.   */
2885   last_oprnd = op0;
2886   prev_stmt_info = NULL;
2887   for (j = 0; j < ncopies; j++)
2888     {
2889       /* Handle uses.  */
2890       if (slp_node)
2891         vect_get_slp_defs (op0, NULL_TREE, slp_node, &vec_oprnds0, NULL, -1);
2892       else
2893         {
2894           VEC_free (tree, heap, vec_oprnds0);
2895           vec_oprnds0 = VEC_alloc (tree, heap,
2896                         (multi_step_cvt ? vect_pow2 (multi_step_cvt) * 2 : 2));
2897           vect_get_loop_based_defs (&last_oprnd, stmt, dt[0], &vec_oprnds0,
2898                                     vect_pow2 (multi_step_cvt) - 1);
2899         }
2900
2901       /* Arguments are ready.  Create the new vector stmts.  */
2902       tmp_vec_dsts = VEC_copy (tree, heap, vec_dsts);
2903       vect_create_vectorized_demotion_stmts (&vec_oprnds0,
2904                                              multi_step_cvt, stmt, tmp_vec_dsts,
2905                                              gsi, slp_node, code1,
2906                                              &prev_stmt_info);
2907     }
2908
2909   VEC_free (tree, heap, vec_oprnds0);
2910   VEC_free (tree, heap, vec_dsts);
2911   VEC_free (tree, heap, tmp_vec_dsts);
2912   VEC_free (tree, heap, interm_types);
2913
2914   *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
2915   return true;
2916 }
2917
2918
2919 /* Create vectorized promotion statements for vector operands from VEC_OPRNDS0
2920    and VEC_OPRNDS1 (for binary operations).  For multi-step conversions store
2921    the resulting vectors and call the function recursively.  */
2922
2923 static void
2924 vect_create_vectorized_promotion_stmts (VEC (tree, heap) **vec_oprnds0,
2925                                         VEC (tree, heap) **vec_oprnds1,
2926                                         int multi_step_cvt, gimple stmt,
2927                                         VEC (tree, heap) *vec_dsts,
2928                                         gimple_stmt_iterator *gsi,
2929                                         slp_tree slp_node, enum tree_code code1,
2930                                         enum tree_code code2, tree decl1,
2931                                         tree decl2, int op_type,
2932                                         stmt_vec_info *prev_stmt_info)
2933 {
2934   int i;
2935   tree vop0, vop1, new_tmp1, new_tmp2, vec_dest;
2936   gimple new_stmt1, new_stmt2;
2937   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
2938   VEC (tree, heap) *vec_tmp;
2939
2940   vec_dest = VEC_pop (tree, vec_dsts);
2941   vec_tmp = VEC_alloc (tree, heap, VEC_length (tree, *vec_oprnds0) * 2);
2942
2943   FOR_EACH_VEC_ELT (tree, *vec_oprnds0, i, vop0)
2944     {
2945       if (op_type == binary_op)
2946         vop1 = VEC_index (tree, *vec_oprnds1, i);
2947       else
2948         vop1 = NULL_TREE;
2949
2950       /* Generate the two halves of promotion operation.  */
2951       new_stmt1 = vect_gen_widened_results_half (code1, decl1, vop0, vop1,
2952                                                  op_type, vec_dest, gsi, stmt);
2953       new_stmt2 = vect_gen_widened_results_half (code2, decl2, vop0, vop1,
2954                                                  op_type, vec_dest, gsi, stmt);
2955       if (is_gimple_call (new_stmt1))
2956         {
2957           new_tmp1 = gimple_call_lhs (new_stmt1);
2958           new_tmp2 = gimple_call_lhs (new_stmt2);
2959         }
2960       else
2961         {
2962           new_tmp1 = gimple_assign_lhs (new_stmt1);
2963           new_tmp2 = gimple_assign_lhs (new_stmt2);
2964         }
2965
2966       if (multi_step_cvt)
2967         {
2968           /* Store the results for the recursive call.  */
2969           VEC_quick_push (tree, vec_tmp, new_tmp1);
2970           VEC_quick_push (tree, vec_tmp, new_tmp2);
2971         }
2972       else
2973         {
2974           /* Last step of promotion sequience - store the results.  */
2975           if (slp_node)
2976             {
2977               VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt1);
2978               VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt2);
2979             }
2980           else
2981             {
2982               if (!*prev_stmt_info)
2983                 STMT_VINFO_VEC_STMT (stmt_info) = new_stmt1;
2984               else
2985                 STMT_VINFO_RELATED_STMT (*prev_stmt_info) = new_stmt1;
2986
2987               *prev_stmt_info = vinfo_for_stmt (new_stmt1);
2988               STMT_VINFO_RELATED_STMT (*prev_stmt_info) = new_stmt2;
2989               *prev_stmt_info = vinfo_for_stmt (new_stmt2);
2990             }
2991         }
2992     }
2993
2994   if (multi_step_cvt)
2995     {
2996       /* For multi-step promotion operation we first generate we call the
2997          function recurcively for every stage.  We start from the input type,
2998          create promotion operations to the intermediate types, and then
2999          create promotions to the output type.  */
3000       *vec_oprnds0 = VEC_copy (tree, heap, vec_tmp);
3001       vect_create_vectorized_promotion_stmts (vec_oprnds0, vec_oprnds1,
3002                                               multi_step_cvt - 1, stmt,
3003                                               vec_dsts, gsi, slp_node, code1,
3004                                               code2, decl2, decl2, op_type,
3005                                               prev_stmt_info);
3006     }
3007
3008   VEC_free (tree, heap, vec_tmp);
3009 }
3010
3011
3012 /* Function vectorizable_type_promotion
3013
3014    Check if STMT performs a binary or unary operation that involves
3015    type promotion, and if it can be vectorized.
3016    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3017    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3018    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3019
3020 static bool
3021 vectorizable_type_promotion (gimple stmt, gimple_stmt_iterator *gsi,
3022                              gimple *vec_stmt, slp_tree slp_node)
3023 {
3024   tree vec_dest;
3025   tree scalar_dest;
3026   tree op0, op1 = NULL;
3027   tree vec_oprnd0=NULL, vec_oprnd1=NULL;
3028   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3029   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3030   enum tree_code code, code1 = ERROR_MARK, code2 = ERROR_MARK;
3031   tree decl1 = NULL_TREE, decl2 = NULL_TREE;
3032   int op_type;
3033   tree def;
3034   gimple def_stmt;
3035   enum vect_def_type dt[2] = {vect_unknown_def_type, vect_unknown_def_type};
3036   stmt_vec_info prev_stmt_info;
3037   int nunits_in;
3038   int nunits_out;
3039   tree vectype_out;
3040   int ncopies;
3041   int j, i;
3042   tree vectype_in;
3043   tree intermediate_type = NULL_TREE;
3044   int multi_step_cvt = 0;
3045   VEC (tree, heap) *vec_oprnds0 = NULL, *vec_oprnds1 = NULL;
3046   VEC (tree, heap) *vec_dsts = NULL, *interm_types = NULL, *tmp_vec_dsts = NULL;
3047
3048   /* FORNOW: not supported by basic block SLP vectorization.  */
3049   gcc_assert (loop_vinfo);
3050
3051   if (!STMT_VINFO_RELEVANT_P (stmt_info))
3052     return false;
3053
3054   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
3055     return false;
3056
3057   /* Is STMT a vectorizable type-promotion operation?  */
3058   if (!is_gimple_assign (stmt))
3059     return false;
3060
3061   if (TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME)
3062     return false;
3063
3064   code = gimple_assign_rhs_code (stmt);
3065   if (!CONVERT_EXPR_CODE_P (code)
3066       && code != WIDEN_MULT_EXPR)
3067     return false;
3068
3069   scalar_dest = gimple_assign_lhs (stmt);
3070   vectype_out = STMT_VINFO_VECTYPE (stmt_info);
3071
3072   /* Check the operands of the operation.  */
3073   op0 = gimple_assign_rhs1 (stmt);
3074   if (! ((INTEGRAL_TYPE_P (TREE_TYPE (scalar_dest))
3075           && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
3076          || (SCALAR_FLOAT_TYPE_P (TREE_TYPE (scalar_dest))
3077              && SCALAR_FLOAT_TYPE_P (TREE_TYPE (op0))
3078              && CONVERT_EXPR_CODE_P (code))))
3079     return false;
3080   if (!vect_is_simple_use_1 (op0, loop_vinfo, NULL,
3081                              &def_stmt, &def, &dt[0], &vectype_in))
3082     {
3083       if (vect_print_dump_info (REPORT_DETAILS))
3084         fprintf (vect_dump, "use not simple.");
3085       return false;
3086     }
3087   /* If op0 is an external or constant def use a vector type with
3088      the same size as the output vector type.  */
3089   if (!vectype_in)
3090     vectype_in = get_same_sized_vectype (TREE_TYPE (op0), vectype_out);
3091   if (vec_stmt)
3092     gcc_assert (vectype_in);
3093   if (!vectype_in)
3094     {
3095       if (vect_print_dump_info (REPORT_DETAILS))
3096         {
3097           fprintf (vect_dump, "no vectype for scalar type ");
3098           print_generic_expr (vect_dump, TREE_TYPE (op0), TDF_SLIM);
3099         }
3100
3101       return false;
3102     }
3103
3104   nunits_in = TYPE_VECTOR_SUBPARTS (vectype_in);
3105   nunits_out = TYPE_VECTOR_SUBPARTS (vectype_out);
3106   if (nunits_in <= nunits_out)
3107     return false;
3108
3109   /* Multiple types in SLP are handled by creating the appropriate number of
3110      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
3111      case of SLP.  */
3112   if (slp_node)
3113     ncopies = 1;
3114   else
3115     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits_in;
3116
3117   gcc_assert (ncopies >= 1);
3118
3119   op_type = TREE_CODE_LENGTH (code);
3120   if (op_type == binary_op)
3121     {
3122       op1 = gimple_assign_rhs2 (stmt);
3123       if (!vect_is_simple_use (op1, loop_vinfo, NULL, &def_stmt, &def, &dt[1]))
3124         {
3125           if (vect_print_dump_info (REPORT_DETAILS))
3126             fprintf (vect_dump, "use not simple.");
3127           return false;
3128         }
3129     }
3130
3131   /* Supportable by target?  */
3132   if (!supportable_widening_operation (code, stmt, vectype_out, vectype_in,
3133                                        &decl1, &decl2, &code1, &code2,
3134                                        &multi_step_cvt, &interm_types))
3135     return false;
3136
3137   /* Binary widening operation can only be supported directly by the
3138      architecture.  */
3139   gcc_assert (!(multi_step_cvt && op_type == binary_op));
3140
3141   if (!vec_stmt) /* transformation not required.  */
3142     {
3143       STMT_VINFO_TYPE (stmt_info) = type_promotion_vec_info_type;
3144       if (vect_print_dump_info (REPORT_DETAILS))
3145         fprintf (vect_dump, "=== vectorizable_promotion ===");
3146       vect_model_simple_cost (stmt_info, 2*ncopies, dt, NULL);
3147       return true;
3148     }
3149
3150   /** Transform.  **/
3151
3152   if (vect_print_dump_info (REPORT_DETAILS))
3153     fprintf (vect_dump, "transform type promotion operation. ncopies = %d.",
3154                         ncopies);
3155
3156   /* Handle def.  */
3157   /* In case of multi-step promotion, we first generate promotion operations
3158      to the intermediate types, and then from that types to the final one.
3159      We store vector destination in VEC_DSTS in the correct order for
3160      recursive creation of promotion operations in
3161      vect_create_vectorized_promotion_stmts(). Vector destinations are created
3162      according to TYPES recieved from supportable_widening_operation().   */
3163   if (multi_step_cvt)
3164     vec_dsts = VEC_alloc (tree, heap, multi_step_cvt + 1);
3165   else
3166     vec_dsts = VEC_alloc (tree, heap, 1);
3167
3168   vec_dest = vect_create_destination_var (scalar_dest, vectype_out);
3169   VEC_quick_push (tree, vec_dsts, vec_dest);
3170
3171   if (multi_step_cvt)
3172     {
3173       for (i = VEC_length (tree, interm_types) - 1;
3174            VEC_iterate (tree, interm_types, i, intermediate_type); i--)
3175         {
3176           vec_dest = vect_create_destination_var (scalar_dest,
3177                                                   intermediate_type);
3178           VEC_quick_push (tree, vec_dsts, vec_dest);
3179         }
3180     }
3181
3182   if (!slp_node)
3183     {
3184       vec_oprnds0 = VEC_alloc (tree, heap,
3185                             (multi_step_cvt ? vect_pow2 (multi_step_cvt) : 1));
3186       if (op_type == binary_op)
3187         vec_oprnds1 = VEC_alloc (tree, heap, 1);
3188     }
3189
3190   /* In case the vectorization factor (VF) is bigger than the number
3191      of elements that we can fit in a vectype (nunits), we have to generate
3192      more than one vector stmt - i.e - we need to "unroll" the
3193      vector stmt by a factor VF/nunits.   */
3194
3195   prev_stmt_info = NULL;
3196   for (j = 0; j < ncopies; j++)
3197     {
3198       /* Handle uses.  */
3199       if (j == 0)
3200         {
3201           if (slp_node)
3202               vect_get_slp_defs (op0, op1, slp_node, &vec_oprnds0,
3203                                  &vec_oprnds1, -1);
3204           else
3205             {
3206               vec_oprnd0 = vect_get_vec_def_for_operand (op0, stmt, NULL);
3207               VEC_quick_push (tree, vec_oprnds0, vec_oprnd0);
3208               if (op_type == binary_op)
3209                 {
3210                   vec_oprnd1 = vect_get_vec_def_for_operand (op1, stmt, NULL);
3211                   VEC_quick_push (tree, vec_oprnds1, vec_oprnd1);
3212                 }
3213             }
3214         }
3215       else
3216         {
3217           vec_oprnd0 = vect_get_vec_def_for_stmt_copy (dt[0], vec_oprnd0);
3218           VEC_replace (tree, vec_oprnds0, 0, vec_oprnd0);
3219           if (op_type == binary_op)
3220             {
3221               vec_oprnd1 = vect_get_vec_def_for_stmt_copy (dt[1], vec_oprnd1);
3222               VEC_replace (tree, vec_oprnds1, 0, vec_oprnd1);
3223             }
3224         }
3225
3226       /* Arguments are ready.  Create the new vector stmts.  */
3227       tmp_vec_dsts = VEC_copy (tree, heap, vec_dsts);
3228       vect_create_vectorized_promotion_stmts (&vec_oprnds0, &vec_oprnds1,
3229                                               multi_step_cvt, stmt,
3230                                               tmp_vec_dsts,
3231                                               gsi, slp_node, code1, code2,
3232                                               decl1, decl2, op_type,
3233                                               &prev_stmt_info);
3234     }
3235
3236   VEC_free (tree, heap, vec_dsts);
3237   VEC_free (tree, heap, tmp_vec_dsts);
3238   VEC_free (tree, heap, interm_types);
3239   VEC_free (tree, heap, vec_oprnds0);
3240   VEC_free (tree, heap, vec_oprnds1);
3241
3242   *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
3243   return true;
3244 }
3245
3246
3247 /* Function vectorizable_store.
3248
3249    Check if STMT defines a non scalar data-ref (array/pointer/structure) that
3250    can be vectorized.
3251    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3252    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3253    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3254
3255 static bool
3256 vectorizable_store (gimple stmt, gimple_stmt_iterator *gsi, gimple *vec_stmt,
3257                     slp_tree slp_node)
3258 {
3259   tree scalar_dest;
3260   tree data_ref;
3261   tree op;
3262   tree vec_oprnd = NULL_TREE;
3263   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3264   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr = NULL;
3265   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3266   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3267   struct loop *loop = NULL;
3268   enum machine_mode vec_mode;
3269   tree dummy;
3270   enum dr_alignment_support alignment_support_scheme;
3271   tree def;
3272   gimple def_stmt;
3273   enum vect_def_type dt;
3274   stmt_vec_info prev_stmt_info = NULL;
3275   tree dataref_ptr = NULL_TREE;
3276   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
3277   int ncopies;
3278   int j;
3279   gimple next_stmt, first_stmt = NULL;
3280   bool strided_store = false;
3281   unsigned int group_size, i;
3282   VEC(tree,heap) *dr_chain = NULL, *oprnds = NULL, *result_chain = NULL;
3283   bool inv_p;
3284   VEC(tree,heap) *vec_oprnds = NULL;
3285   bool slp = (slp_node != NULL);
3286   unsigned int vec_num;
3287   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3288
3289   if (loop_vinfo)
3290     loop = LOOP_VINFO_LOOP (loop_vinfo);
3291
3292   /* Multiple types in SLP are handled by creating the appropriate number of
3293      vectorized stmts for each SLP node. Hence, NCOPIES is always 1 in
3294      case of SLP.  */
3295   if (slp)
3296     ncopies = 1;
3297   else
3298     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
3299
3300   gcc_assert (ncopies >= 1);
3301
3302   /* FORNOW. This restriction should be relaxed.  */
3303   if (loop && nested_in_vect_loop_p (loop, stmt) && ncopies > 1)
3304     {
3305       if (vect_print_dump_info (REPORT_DETAILS))
3306         fprintf (vect_dump, "multiple types in nested loop.");
3307       return false;
3308     }
3309
3310   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
3311     return false;
3312
3313   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
3314     return false;
3315
3316   /* Is vectorizable store? */
3317
3318   if (!is_gimple_assign (stmt))
3319     return false;
3320
3321   scalar_dest = gimple_assign_lhs (stmt);
3322   if (TREE_CODE (scalar_dest) != ARRAY_REF
3323       && TREE_CODE (scalar_dest) != INDIRECT_REF
3324       && TREE_CODE (scalar_dest) != COMPONENT_REF
3325       && TREE_CODE (scalar_dest) != IMAGPART_EXPR
3326       && TREE_CODE (scalar_dest) != REALPART_EXPR
3327       && TREE_CODE (scalar_dest) != MEM_REF)
3328     return false;
3329
3330   gcc_assert (gimple_assign_single_p (stmt));
3331   op = gimple_assign_rhs1 (stmt);
3332   if (!vect_is_simple_use (op, loop_vinfo, bb_vinfo, &def_stmt, &def, &dt))
3333     {
3334       if (vect_print_dump_info (REPORT_DETAILS))
3335         fprintf (vect_dump, "use not simple.");
3336       return false;
3337     }
3338
3339   /* The scalar rhs type needs to be trivially convertible to the vector
3340      component type.  This should always be the case.  */
3341   if (!useless_type_conversion_p (TREE_TYPE (vectype), TREE_TYPE (op)))
3342     {
3343       if (vect_print_dump_info (REPORT_DETAILS))
3344         fprintf (vect_dump, "???  operands of different types");
3345       return false;
3346     }
3347
3348   vec_mode = TYPE_MODE (vectype);
3349   /* FORNOW. In some cases can vectorize even if data-type not supported
3350      (e.g. - array initialization with 0).  */
3351   if (optab_handler (mov_optab, vec_mode) == CODE_FOR_nothing)
3352     return false;
3353
3354   if (!STMT_VINFO_DATA_REF (stmt_info))
3355     return false;
3356
3357   if (tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0)
3358     {
3359       if (vect_print_dump_info (REPORT_DETAILS))
3360         fprintf (vect_dump, "negative step for store.");
3361       return false;
3362     }
3363
3364   if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
3365     {
3366       strided_store = true;
3367       first_stmt = DR_GROUP_FIRST_DR (stmt_info);
3368       if (!vect_strided_store_supported (vectype)
3369           && !PURE_SLP_STMT (stmt_info) && !slp)
3370         return false;
3371
3372       if (first_stmt == stmt)
3373         {
3374           /* STMT is the leader of the group. Check the operands of all the
3375              stmts of the group.  */
3376           next_stmt = DR_GROUP_NEXT_DR (stmt_info);
3377           while (next_stmt)
3378             {
3379               gcc_assert (gimple_assign_single_p (next_stmt));
3380               op = gimple_assign_rhs1 (next_stmt);
3381               if (!vect_is_simple_use (op, loop_vinfo, bb_vinfo, &def_stmt,
3382                                        &def, &dt))
3383                 {
3384                   if (vect_print_dump_info (REPORT_DETAILS))
3385                     fprintf (vect_dump, "use not simple.");
3386                   return false;
3387                 }
3388               next_stmt = DR_GROUP_NEXT_DR (vinfo_for_stmt (next_stmt));
3389             }
3390         }
3391     }
3392
3393   if (!vec_stmt) /* transformation not required.  */
3394     {
3395       STMT_VINFO_TYPE (stmt_info) = store_vec_info_type;
3396       vect_model_store_cost (stmt_info, ncopies, dt, NULL);
3397       return true;
3398     }
3399
3400   /** Transform.  **/
3401
3402   if (strided_store)
3403     {
3404       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3405       group_size = DR_GROUP_SIZE (vinfo_for_stmt (first_stmt));
3406
3407       DR_GROUP_STORE_COUNT (vinfo_for_stmt (first_stmt))++;
3408
3409       /* FORNOW */
3410       gcc_assert (!loop || !nested_in_vect_loop_p (loop, stmt));
3411
3412       /* We vectorize all the stmts of the interleaving group when we
3413          reach the last stmt in the group.  */
3414       if (DR_GROUP_STORE_COUNT (vinfo_for_stmt (first_stmt))
3415           < DR_GROUP_SIZE (vinfo_for_stmt (first_stmt))
3416           && !slp)
3417         {
3418           *vec_stmt = NULL;
3419           return true;
3420         }
3421
3422       if (slp)
3423         {
3424           strided_store = false;
3425           /* VEC_NUM is the number of vect stmts to be created for this
3426              group.  */
3427           vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
3428           first_stmt = VEC_index (gimple, SLP_TREE_SCALAR_STMTS (slp_node), 0);
3429           first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3430         }
3431       else
3432         /* VEC_NUM is the number of vect stmts to be created for this
3433            group.  */
3434         vec_num = group_size;
3435     }
3436   else
3437     {
3438       first_stmt = stmt;
3439       first_dr = dr;
3440       group_size = vec_num = 1;
3441     }
3442
3443   if (vect_print_dump_info (REPORT_DETAILS))
3444     fprintf (vect_dump, "transform store. ncopies = %d",ncopies);
3445
3446   dr_chain = VEC_alloc (tree, heap, group_size);
3447   oprnds = VEC_alloc (tree, heap, group_size);
3448
3449   alignment_support_scheme = vect_supportable_dr_alignment (first_dr, false);
3450   gcc_assert (alignment_support_scheme);
3451
3452   /* In case the vectorization factor (VF) is bigger than the number
3453      of elements that we can fit in a vectype (nunits), we have to generate
3454      more than one vector stmt - i.e - we need to "unroll" the
3455      vector stmt by a factor VF/nunits.  For more details see documentation in
3456      vect_get_vec_def_for_copy_stmt.  */
3457
3458   /* In case of interleaving (non-unit strided access):
3459
3460         S1:  &base + 2 = x2
3461         S2:  &base = x0
3462         S3:  &base + 1 = x1
3463         S4:  &base + 3 = x3
3464
3465      We create vectorized stores starting from base address (the access of the
3466      first stmt in the chain (S2 in the above example), when the last store stmt
3467      of the chain (S4) is reached:
3468
3469         VS1: &base = vx2
3470         VS2: &base + vec_size*1 = vx0
3471         VS3: &base + vec_size*2 = vx1
3472         VS4: &base + vec_size*3 = vx3
3473
3474      Then permutation statements are generated:
3475
3476         VS5: vx5 = VEC_INTERLEAVE_HIGH_EXPR < vx0, vx3 >
3477         VS6: vx6 = VEC_INTERLEAVE_LOW_EXPR < vx0, vx3 >
3478         ...
3479
3480      And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3481      (the order of the data-refs in the output of vect_permute_store_chain
3482      corresponds to the order of scalar stmts in the interleaving chain - see
3483      the documentation of vect_permute_store_chain()).
3484
3485      In case of both multiple types and interleaving, above vector stores and
3486      permutation stmts are created for every copy.  The result vector stmts are
3487      put in STMT_VINFO_VEC_STMT for the first copy and in the corresponding
3488      STMT_VINFO_RELATED_STMT for the next copies.
3489   */
3490
3491   prev_stmt_info = NULL;
3492   for (j = 0; j < ncopies; j++)
3493     {
3494       gimple new_stmt;
3495       gimple ptr_incr;
3496
3497       if (j == 0)
3498         {
3499           if (slp)
3500             {
3501               /* Get vectorized arguments for SLP_NODE.  */
3502               vect_get_slp_defs (NULL_TREE, NULL_TREE, slp_node, &vec_oprnds,
3503                                  NULL, -1);
3504
3505               vec_oprnd = VEC_index (tree, vec_oprnds, 0);
3506             }
3507           else
3508             {
3509               /* For interleaved stores we collect vectorized defs for all the
3510                  stores in the group in DR_CHAIN and OPRNDS. DR_CHAIN is then
3511                  used as an input to vect_permute_store_chain(), and OPRNDS as
3512                  an input to vect_get_vec_def_for_stmt_copy() for the next copy.
3513
3514                  If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3515                  OPRNDS are of size 1.  */
3516               next_stmt = first_stmt;
3517               for (i = 0; i < group_size; i++)
3518                 {
3519                   /* Since gaps are not supported for interleaved stores,
3520                      GROUP_SIZE is the exact number of stmts in the chain.
3521                      Therefore, NEXT_STMT can't be NULL_TREE.  In case that
3522                      there is no interleaving, GROUP_SIZE is 1, and only one
3523                      iteration of the loop will be executed.  */
3524                   gcc_assert (next_stmt
3525                               && gimple_assign_single_p (next_stmt));
3526                   op = gimple_assign_rhs1 (next_stmt);
3527
3528                   vec_oprnd = vect_get_vec_def_for_operand (op, next_stmt,
3529                                                             NULL);
3530                   VEC_quick_push(tree, dr_chain, vec_oprnd);
3531                   VEC_quick_push(tree, oprnds, vec_oprnd);
3532                   next_stmt = DR_GROUP_NEXT_DR (vinfo_for_stmt (next_stmt));
3533                 }
3534             }
3535
3536           /* We should have catched mismatched types earlier.  */
3537           gcc_assert (useless_type_conversion_p (vectype,
3538                                                  TREE_TYPE (vec_oprnd)));
3539           dataref_ptr = vect_create_data_ref_ptr (first_stmt, NULL, NULL_TREE,
3540                                                   &dummy, &ptr_incr, false,
3541                                                   &inv_p);
3542           gcc_assert (bb_vinfo || !inv_p);
3543         }
3544       else
3545         {
3546           /* For interleaved stores we created vectorized defs for all the
3547              defs stored in OPRNDS in the previous iteration (previous copy).
3548              DR_CHAIN is then used as an input to vect_permute_store_chain(),
3549              and OPRNDS as an input to vect_get_vec_def_for_stmt_copy() for the
3550              next copy.
3551              If the store is not strided, GROUP_SIZE is 1, and DR_CHAIN and
3552              OPRNDS are of size 1.  */
3553           for (i = 0; i < group_size; i++)
3554             {
3555               op = VEC_index (tree, oprnds, i);
3556               vect_is_simple_use (op, loop_vinfo, bb_vinfo, &def_stmt, &def,
3557                                   &dt);
3558               vec_oprnd = vect_get_vec_def_for_stmt_copy (dt, op);
3559               VEC_replace(tree, dr_chain, i, vec_oprnd);
3560               VEC_replace(tree, oprnds, i, vec_oprnd);
3561             }
3562           dataref_ptr =
3563                 bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt, NULL_TREE);
3564         }
3565
3566       if (strided_store)
3567         {
3568           result_chain = VEC_alloc (tree, heap, group_size);
3569           /* Permute.  */
3570           if (!vect_permute_store_chain (dr_chain, group_size, stmt, gsi,
3571                                          &result_chain))
3572             return false;
3573         }
3574
3575       next_stmt = first_stmt;
3576       for (i = 0; i < vec_num; i++)
3577         {
3578           struct ptr_info_def *pi;
3579
3580           if (i > 0)
3581             /* Bump the vector pointer.  */
3582             dataref_ptr = bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt,
3583                                            NULL_TREE);
3584
3585           if (slp)
3586             vec_oprnd = VEC_index (tree, vec_oprnds, i);
3587           else if (strided_store)
3588             /* For strided stores vectorized defs are interleaved in
3589                vect_permute_store_chain().  */
3590             vec_oprnd = VEC_index (tree, result_chain, i);
3591
3592           data_ref = build2 (MEM_REF, TREE_TYPE (vec_oprnd), dataref_ptr,
3593                              build_int_cst (reference_alias_ptr_type
3594                                             (DR_REF (first_dr)), 0));
3595           pi = get_ptr_info (dataref_ptr);
3596           pi->align = TYPE_ALIGN_UNIT (vectype);
3597           if (aligned_access_p (first_dr))
3598             pi->misalign = 0;
3599           else if (DR_MISALIGNMENT (first_dr) == -1)
3600             {
3601               TREE_TYPE (data_ref)
3602                 = build_aligned_type (TREE_TYPE (data_ref),
3603                                       TYPE_ALIGN (TREE_TYPE (vectype)));
3604               pi->align = TYPE_ALIGN_UNIT (TREE_TYPE (vectype));
3605               pi->misalign = 0;
3606             }
3607           else
3608             {
3609               TREE_TYPE (data_ref)
3610                 = build_aligned_type (TREE_TYPE (data_ref),
3611                                       TYPE_ALIGN (TREE_TYPE (vectype)));
3612               pi->misalign = DR_MISALIGNMENT (first_dr);
3613             }
3614
3615           /* Arguments are ready.  Create the new vector stmt.  */
3616           new_stmt = gimple_build_assign (data_ref, vec_oprnd);
3617           vect_finish_stmt_generation (stmt, new_stmt, gsi);
3618           mark_symbols_for_renaming (new_stmt);
3619
3620           if (slp)
3621             continue;
3622
3623           if (j == 0)
3624             STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt =  new_stmt;
3625           else
3626             STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
3627
3628           prev_stmt_info = vinfo_for_stmt (new_stmt);
3629           next_stmt = DR_GROUP_NEXT_DR (vinfo_for_stmt (next_stmt));
3630           if (!next_stmt)
3631             break;
3632         }
3633     }
3634
3635   VEC_free (tree, heap, dr_chain);
3636   VEC_free (tree, heap, oprnds);
3637   if (result_chain)
3638     VEC_free (tree, heap, result_chain);
3639   if (vec_oprnds)
3640     VEC_free (tree, heap, vec_oprnds);
3641
3642   return true;
3643 }
3644
3645 /* Given a vector type VECTYPE returns a builtin DECL to be used
3646    for vector permutation and stores a mask into *MASK that implements
3647    reversal of the vector elements.  If that is impossible to do
3648    returns NULL (and *MASK is unchanged).  */
3649
3650 static tree
3651 perm_mask_for_reverse (tree vectype, tree *mask)
3652 {
3653   tree builtin_decl;
3654   tree mask_element_type, mask_type;
3655   tree mask_vec = NULL;
3656   int i;
3657   int nunits;
3658   if (!targetm.vectorize.builtin_vec_perm)
3659     return NULL;
3660
3661   builtin_decl = targetm.vectorize.builtin_vec_perm (vectype,
3662                                                      &mask_element_type);
3663   if (!builtin_decl || !mask_element_type)
3664     return NULL;
3665
3666   mask_type = get_vectype_for_scalar_type (mask_element_type);
3667   nunits = TYPE_VECTOR_SUBPARTS (vectype);
3668   if (!mask_type
3669       || TYPE_VECTOR_SUBPARTS (vectype) != TYPE_VECTOR_SUBPARTS (mask_type))
3670     return NULL;
3671
3672   for (i = 0; i < nunits; i++)
3673     mask_vec = tree_cons (NULL, build_int_cst (mask_element_type, i), mask_vec);
3674   mask_vec = build_vector (mask_type, mask_vec);
3675
3676   if (!targetm.vectorize.builtin_vec_perm_ok (vectype, mask_vec))
3677     return NULL;
3678   if (mask)
3679     *mask = mask_vec;
3680   return builtin_decl;
3681 }
3682
3683 /* Given a vector variable X, that was generated for the scalar LHS of
3684    STMT, generate instructions to reverse the vector elements of X,
3685    insert them a *GSI and return the permuted vector variable.  */
3686
3687 static tree
3688 reverse_vec_elements (tree x, gimple stmt, gimple_stmt_iterator *gsi)
3689 {
3690   tree vectype = TREE_TYPE (x);
3691   tree mask_vec, builtin_decl;
3692   tree perm_dest, data_ref;
3693   gimple perm_stmt;
3694
3695   builtin_decl = perm_mask_for_reverse (vectype, &mask_vec);
3696
3697   perm_dest = vect_create_destination_var (gimple_assign_lhs (stmt), vectype);
3698
3699   /* Generate the permute statement.  */
3700   perm_stmt = gimple_build_call (builtin_decl, 3, x, x, mask_vec);
3701   data_ref = make_ssa_name (perm_dest, perm_stmt);
3702   gimple_call_set_lhs (perm_stmt, data_ref);
3703   vect_finish_stmt_generation (stmt, perm_stmt, gsi);
3704
3705   return data_ref;
3706 }
3707
3708 /* vectorizable_load.
3709
3710    Check if STMT reads a non scalar data-ref (array/pointer/structure) that
3711    can be vectorized.
3712    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
3713    stmt to replace it, put it in VEC_STMT, and insert it at BSI.
3714    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
3715
3716 static bool
3717 vectorizable_load (gimple stmt, gimple_stmt_iterator *gsi, gimple *vec_stmt,
3718                    slp_tree slp_node, slp_instance slp_node_instance)
3719 {
3720   tree scalar_dest;
3721   tree vec_dest = NULL;
3722   tree data_ref = NULL;
3723   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
3724   stmt_vec_info prev_stmt_info;
3725   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
3726   struct loop *loop = NULL;
3727   struct loop *containing_loop = (gimple_bb (stmt))->loop_father;
3728   bool nested_in_vect_loop = false;
3729   struct data_reference *dr = STMT_VINFO_DATA_REF (stmt_info), *first_dr;
3730   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
3731   tree new_temp;
3732   enum machine_mode mode;
3733   gimple new_stmt = NULL;
3734   tree dummy;
3735   enum dr_alignment_support alignment_support_scheme;
3736   tree dataref_ptr = NULL_TREE;
3737   gimple ptr_incr;
3738   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
3739   int ncopies;
3740   int i, j, group_size;
3741   tree msq = NULL_TREE, lsq;
3742   tree offset = NULL_TREE;
3743   tree realignment_token = NULL_TREE;
3744   gimple phi = NULL;
3745   VEC(tree,heap) *dr_chain = NULL;
3746   bool strided_load = false;
3747   gimple first_stmt;
3748   tree scalar_type;
3749   bool inv_p;
3750   bool negative;
3751   bool compute_in_loop = false;
3752   struct loop *at_loop;
3753   int vec_num;
3754   bool slp = (slp_node != NULL);
3755   bool slp_perm = false;
3756   enum tree_code code;
3757   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
3758   int vf;
3759
3760   if (loop_vinfo)
3761     {
3762       loop = LOOP_VINFO_LOOP (loop_vinfo);
3763       nested_in_vect_loop = nested_in_vect_loop_p (loop, stmt);
3764       vf = LOOP_VINFO_VECT_FACTOR (loop_vinfo);
3765     }
3766   else
3767     vf = 1;
3768
3769   /* Multiple types in SLP are handled by creating the appropriate number of
3770      vectorized stmts for each SLP node.  Hence, NCOPIES is always 1 in
3771      case of SLP.  */
3772   if (slp)
3773     ncopies = 1;
3774   else
3775     ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
3776
3777   gcc_assert (ncopies >= 1);
3778
3779   /* FORNOW. This restriction should be relaxed.  */
3780   if (nested_in_vect_loop && ncopies > 1)
3781     {
3782       if (vect_print_dump_info (REPORT_DETAILS))
3783         fprintf (vect_dump, "multiple types in nested loop.");
3784       return false;
3785     }
3786
3787   if (!STMT_VINFO_RELEVANT_P (stmt_info) && !bb_vinfo)
3788     return false;
3789
3790   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def)
3791     return false;
3792
3793   /* Is vectorizable load? */
3794   if (!is_gimple_assign (stmt))
3795     return false;
3796
3797   scalar_dest = gimple_assign_lhs (stmt);
3798   if (TREE_CODE (scalar_dest) != SSA_NAME)
3799     return false;
3800
3801   code = gimple_assign_rhs_code (stmt);
3802   if (code != ARRAY_REF
3803       && code != INDIRECT_REF
3804       && code != COMPONENT_REF
3805       && code != IMAGPART_EXPR
3806       && code != REALPART_EXPR
3807       && code != MEM_REF)
3808     return false;
3809
3810   if (!STMT_VINFO_DATA_REF (stmt_info))
3811     return false;
3812
3813   negative = tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0;
3814   if (negative && ncopies > 1)
3815     {
3816       if (vect_print_dump_info (REPORT_DETAILS))
3817         fprintf (vect_dump, "multiple types with negative step.");
3818       return false;
3819     }
3820
3821   scalar_type = TREE_TYPE (DR_REF (dr));
3822   mode = TYPE_MODE (vectype);
3823
3824   /* FORNOW. In some cases can vectorize even if data-type not supported
3825     (e.g. - data copies).  */
3826   if (optab_handler (mov_optab, mode) == CODE_FOR_nothing)
3827     {
3828       if (vect_print_dump_info (REPORT_DETAILS))
3829         fprintf (vect_dump, "Aligned load, but unsupported type.");
3830       return false;
3831     }
3832
3833   /* The vector component type needs to be trivially convertible to the
3834      scalar lhs.  This should always be the case.  */
3835   if (!useless_type_conversion_p (TREE_TYPE (scalar_dest), TREE_TYPE (vectype)))
3836     {
3837       if (vect_print_dump_info (REPORT_DETAILS))
3838         fprintf (vect_dump, "???  operands of different types");
3839       return false;
3840     }
3841
3842   /* Check if the load is a part of an interleaving chain.  */
3843   if (STMT_VINFO_STRIDED_ACCESS (stmt_info))
3844     {
3845       strided_load = true;
3846       /* FORNOW */
3847       gcc_assert (! nested_in_vect_loop);
3848
3849       /* Check if interleaving is supported.  */
3850       if (!vect_strided_load_supported (vectype)
3851           && !PURE_SLP_STMT (stmt_info) && !slp)
3852         return false;
3853     }
3854
3855   if (negative)
3856     {
3857       gcc_assert (!strided_load);
3858       alignment_support_scheme = vect_supportable_dr_alignment (dr, false);
3859       if (alignment_support_scheme != dr_aligned
3860           && alignment_support_scheme != dr_unaligned_supported)
3861         {
3862           if (vect_print_dump_info (REPORT_DETAILS))
3863             fprintf (vect_dump, "negative step but alignment required.");
3864           return false;
3865         }
3866       if (!perm_mask_for_reverse (vectype, NULL))
3867         {
3868           if (vect_print_dump_info (REPORT_DETAILS))
3869             fprintf (vect_dump, "negative step and reversing not supported.");
3870           return false;
3871         }
3872     }
3873
3874   if (!vec_stmt) /* transformation not required.  */
3875     {
3876       STMT_VINFO_TYPE (stmt_info) = load_vec_info_type;
3877       vect_model_load_cost (stmt_info, ncopies, NULL);
3878       return true;
3879     }
3880
3881   if (vect_print_dump_info (REPORT_DETAILS))
3882     fprintf (vect_dump, "transform load.");
3883
3884   /** Transform.  **/
3885
3886   if (strided_load)
3887     {
3888       first_stmt = DR_GROUP_FIRST_DR (stmt_info);
3889       /* Check if the chain of loads is already vectorized.  */
3890       if (STMT_VINFO_VEC_STMT (vinfo_for_stmt (first_stmt)))
3891         {
3892           *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
3893           return true;
3894         }
3895       first_dr = STMT_VINFO_DATA_REF (vinfo_for_stmt (first_stmt));
3896       group_size = DR_GROUP_SIZE (vinfo_for_stmt (first_stmt));
3897
3898       /* VEC_NUM is the number of vect stmts to be created for this group.  */
3899       if (slp)
3900         {
3901           strided_load = false;
3902           vec_num = SLP_TREE_NUMBER_OF_VEC_STMTS (slp_node);
3903           if (SLP_INSTANCE_LOAD_PERMUTATION (slp_node_instance))
3904             slp_perm = true;
3905         }
3906       else
3907         vec_num = group_size;
3908
3909       dr_chain = VEC_alloc (tree, heap, vec_num);
3910     }
3911   else
3912     {
3913       first_stmt = stmt;
3914       first_dr = dr;
3915       group_size = vec_num = 1;
3916     }
3917
3918   alignment_support_scheme = vect_supportable_dr_alignment (first_dr, false);
3919   gcc_assert (alignment_support_scheme);
3920
3921   /* In case the vectorization factor (VF) is bigger than the number
3922      of elements that we can fit in a vectype (nunits), we have to generate
3923      more than one vector stmt - i.e - we need to "unroll" the
3924      vector stmt by a factor VF/nunits.  In doing so, we record a pointer
3925      from one copy of the vector stmt to the next, in the field
3926      STMT_VINFO_RELATED_STMT.  This is necessary in order to allow following
3927      stages to find the correct vector defs to be used when vectorizing
3928      stmts that use the defs of the current stmt.  The example below
3929      illustrates the vectorization process when VF=16 and nunits=4 (i.e., we
3930      need to create 4 vectorized stmts):
3931
3932      before vectorization:
3933                                 RELATED_STMT    VEC_STMT
3934         S1:     x = memref      -               -
3935         S2:     z = x + 1       -               -
3936
3937      step 1: vectorize stmt S1:
3938         We first create the vector stmt VS1_0, and, as usual, record a
3939         pointer to it in the STMT_VINFO_VEC_STMT of the scalar stmt S1.
3940         Next, we create the vector stmt VS1_1, and record a pointer to
3941         it in the STMT_VINFO_RELATED_STMT of the vector stmt VS1_0.
3942         Similarly, for VS1_2 and VS1_3.  This is the resulting chain of
3943         stmts and pointers:
3944                                 RELATED_STMT    VEC_STMT
3945         VS1_0:  vx0 = memref0   VS1_1           -
3946         VS1_1:  vx1 = memref1   VS1_2           -
3947         VS1_2:  vx2 = memref2   VS1_3           -
3948         VS1_3:  vx3 = memref3   -               -
3949         S1:     x = load        -               VS1_0
3950         S2:     z = x + 1       -               -
3951
3952      See in documentation in vect_get_vec_def_for_stmt_copy for how the
3953      information we recorded in RELATED_STMT field is used to vectorize
3954      stmt S2.  */
3955
3956   /* In case of interleaving (non-unit strided access):
3957
3958      S1:  x2 = &base + 2
3959      S2:  x0 = &base
3960      S3:  x1 = &base + 1
3961      S4:  x3 = &base + 3
3962
3963      Vectorized loads are created in the order of memory accesses
3964      starting from the access of the first stmt of the chain:
3965
3966      VS1: vx0 = &base
3967      VS2: vx1 = &base + vec_size*1
3968      VS3: vx3 = &base + vec_size*2
3969      VS4: vx4 = &base + vec_size*3
3970
3971      Then permutation statements are generated:
3972
3973      VS5: vx5 = VEC_EXTRACT_EVEN_EXPR < vx0, vx1 >
3974      VS6: vx6 = VEC_EXTRACT_ODD_EXPR < vx0, vx1 >
3975        ...
3976
3977      And they are put in STMT_VINFO_VEC_STMT of the corresponding scalar stmts
3978      (the order of the data-refs in the output of vect_permute_load_chain
3979      corresponds to the order of scalar stmts in the interleaving chain - see
3980      the documentation of vect_permute_load_chain()).
3981      The generation of permutation stmts and recording them in
3982      STMT_VINFO_VEC_STMT is done in vect_transform_strided_load().
3983
3984      In case of both multiple types and interleaving, the vector loads and
3985      permutation stmts above are created for every copy.  The result vector
3986      stmts are put in STMT_VINFO_VEC_STMT for the first copy and in the
3987      corresponding STMT_VINFO_RELATED_STMT for the next copies.  */
3988
3989   /* If the data reference is aligned (dr_aligned) or potentially unaligned
3990      on a target that supports unaligned accesses (dr_unaligned_supported)
3991      we generate the following code:
3992          p = initial_addr;
3993          indx = 0;
3994          loop {
3995            p = p + indx * vectype_size;
3996            vec_dest = *(p);
3997            indx = indx + 1;
3998          }
3999
4000      Otherwise, the data reference is potentially unaligned on a target that
4001      does not support unaligned accesses (dr_explicit_realign_optimized) -
4002      then generate the following code, in which the data in each iteration is
4003      obtained by two vector loads, one from the previous iteration, and one
4004      from the current iteration:
4005          p1 = initial_addr;
4006          msq_init = *(floor(p1))
4007          p2 = initial_addr + VS - 1;
4008          realignment_token = call target_builtin;
4009          indx = 0;
4010          loop {
4011            p2 = p2 + indx * vectype_size
4012            lsq = *(floor(p2))
4013            vec_dest = realign_load (msq, lsq, realignment_token)
4014            indx = indx + 1;
4015            msq = lsq;
4016          }   */
4017
4018   /* If the misalignment remains the same throughout the execution of the
4019      loop, we can create the init_addr and permutation mask at the loop
4020      preheader.  Otherwise, it needs to be created inside the loop.
4021      This can only occur when vectorizing memory accesses in the inner-loop
4022      nested within an outer-loop that is being vectorized.  */
4023
4024   if (loop && nested_in_vect_loop_p (loop, stmt)
4025       && (TREE_INT_CST_LOW (DR_STEP (dr))
4026           % GET_MODE_SIZE (TYPE_MODE (vectype)) != 0))
4027     {
4028       gcc_assert (alignment_support_scheme != dr_explicit_realign_optimized);
4029       compute_in_loop = true;
4030     }
4031
4032   if ((alignment_support_scheme == dr_explicit_realign_optimized
4033        || alignment_support_scheme == dr_explicit_realign)
4034       && !compute_in_loop)
4035     {
4036       msq = vect_setup_realignment (first_stmt, gsi, &realignment_token,
4037                                     alignment_support_scheme, NULL_TREE,
4038                                     &at_loop);
4039       if (alignment_support_scheme == dr_explicit_realign_optimized)
4040         {
4041           phi = SSA_NAME_DEF_STMT (msq);
4042           offset = size_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
4043         }
4044     }
4045   else
4046     at_loop = loop;
4047
4048   if (negative)
4049     offset = size_int (-TYPE_VECTOR_SUBPARTS (vectype) + 1);
4050
4051   prev_stmt_info = NULL;
4052   for (j = 0; j < ncopies; j++)
4053     {
4054       /* 1. Create the vector pointer update chain.  */
4055       if (j == 0)
4056         dataref_ptr = vect_create_data_ref_ptr (first_stmt,
4057                                                 at_loop, offset,
4058                                                 &dummy, &ptr_incr, false,
4059                                                 &inv_p);
4060       else
4061         dataref_ptr =
4062                 bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt, NULL_TREE);
4063
4064       for (i = 0; i < vec_num; i++)
4065         {
4066           if (i > 0)
4067             dataref_ptr = bump_vector_ptr (dataref_ptr, ptr_incr, gsi, stmt,
4068                                            NULL_TREE);
4069
4070           /* 2. Create the vector-load in the loop.  */
4071           switch (alignment_support_scheme)
4072             {
4073             case dr_aligned:
4074             case dr_unaligned_supported:
4075               {
4076                 struct ptr_info_def *pi;
4077                 data_ref
4078                   = build2 (MEM_REF, vectype, dataref_ptr,
4079                             build_int_cst (reference_alias_ptr_type
4080                                            (DR_REF (first_dr)), 0));
4081                 pi = get_ptr_info (dataref_ptr);
4082                 pi->align = TYPE_ALIGN_UNIT (vectype);
4083                 if (alignment_support_scheme == dr_aligned)
4084                   {
4085                     gcc_assert (aligned_access_p (first_dr));
4086                     pi->misalign = 0;
4087                   }
4088                 else if (DR_MISALIGNMENT (first_dr) == -1)
4089                   {
4090                     TREE_TYPE (data_ref)
4091                       = build_aligned_type (TREE_TYPE (data_ref),
4092                                             TYPE_ALIGN (TREE_TYPE (vectype)));
4093                     pi->align = TYPE_ALIGN_UNIT (TREE_TYPE (vectype));
4094                     pi->misalign = 0;
4095                   }
4096                 else
4097                   {
4098                     TREE_TYPE (data_ref)
4099                       = build_aligned_type (TREE_TYPE (data_ref),
4100                                             TYPE_ALIGN (TREE_TYPE (vectype)));
4101                     pi->misalign = DR_MISALIGNMENT (first_dr);
4102                   }
4103                 break;
4104               }
4105             case dr_explicit_realign:
4106               {
4107                 tree ptr, bump;
4108                 tree vs_minus_1 = size_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
4109
4110                 if (compute_in_loop)
4111                   msq = vect_setup_realignment (first_stmt, gsi,
4112                                                 &realignment_token,
4113                                                 dr_explicit_realign,
4114                                                 dataref_ptr, NULL);
4115
4116                 new_stmt = gimple_build_assign_with_ops
4117                              (BIT_AND_EXPR, NULL_TREE, dataref_ptr,
4118                               build_int_cst
4119                                 (TREE_TYPE (dataref_ptr),
4120                                  -(HOST_WIDE_INT)TYPE_ALIGN_UNIT (vectype)));
4121                 ptr = make_ssa_name (SSA_NAME_VAR (dataref_ptr), new_stmt);
4122                 gimple_assign_set_lhs (new_stmt, ptr);
4123                 vect_finish_stmt_generation (stmt, new_stmt, gsi);
4124                 data_ref
4125                   = build2 (MEM_REF, vectype, ptr,
4126                             build_int_cst (reference_alias_ptr_type
4127                                              (DR_REF (first_dr)), 0));
4128                 vec_dest = vect_create_destination_var (scalar_dest, vectype);
4129                 new_stmt = gimple_build_assign (vec_dest, data_ref);
4130                 new_temp = make_ssa_name (vec_dest, new_stmt);
4131                 gimple_assign_set_lhs (new_stmt, new_temp);
4132                 gimple_set_vdef (new_stmt, gimple_vdef (stmt));
4133                 gimple_set_vuse (new_stmt, gimple_vuse (stmt));
4134                 vect_finish_stmt_generation (stmt, new_stmt, gsi);
4135                 msq = new_temp;
4136
4137                 bump = size_binop (MULT_EXPR, vs_minus_1,
4138                                    TYPE_SIZE_UNIT (scalar_type));
4139                 ptr = bump_vector_ptr (dataref_ptr, NULL, gsi, stmt, bump);
4140                 new_stmt = gimple_build_assign_with_ops
4141                              (BIT_AND_EXPR, NULL_TREE, ptr,
4142                               build_int_cst
4143                                 (TREE_TYPE (ptr),
4144                                  -(HOST_WIDE_INT)TYPE_ALIGN_UNIT (vectype)));
4145                 ptr = make_ssa_name (SSA_NAME_VAR (dataref_ptr), new_stmt);
4146                 gimple_assign_set_lhs (new_stmt, ptr);
4147                 vect_finish_stmt_generation (stmt, new_stmt, gsi);
4148                 data_ref
4149                   = build2 (MEM_REF, vectype, ptr,
4150                             build_int_cst (reference_alias_ptr_type
4151                                              (DR_REF (first_dr)), 0));
4152                 break;
4153               }
4154             case dr_explicit_realign_optimized:
4155               new_stmt = gimple_build_assign_with_ops
4156                            (BIT_AND_EXPR, NULL_TREE, dataref_ptr,
4157                             build_int_cst
4158                               (TREE_TYPE (dataref_ptr),
4159                                -(HOST_WIDE_INT)TYPE_ALIGN_UNIT (vectype)));
4160               new_temp = make_ssa_name (SSA_NAME_VAR (dataref_ptr), new_stmt);
4161               gimple_assign_set_lhs (new_stmt, new_temp);
4162               vect_finish_stmt_generation (stmt, new_stmt, gsi);
4163               data_ref
4164                 = build2 (MEM_REF, vectype, new_temp,
4165                           build_int_cst (reference_alias_ptr_type
4166                                            (DR_REF (first_dr)), 0));
4167               break;
4168             default:
4169               gcc_unreachable ();
4170             }
4171           vec_dest = vect_create_destination_var (scalar_dest, vectype);
4172           new_stmt = gimple_build_assign (vec_dest, data_ref);
4173           new_temp = make_ssa_name (vec_dest, new_stmt);
4174           gimple_assign_set_lhs (new_stmt, new_temp);
4175           vect_finish_stmt_generation (stmt, new_stmt, gsi);
4176           mark_symbols_for_renaming (new_stmt);
4177
4178           /* 3. Handle explicit realignment if necessary/supported.  Create in
4179                 loop: vec_dest = realign_load (msq, lsq, realignment_token)  */
4180           if (alignment_support_scheme == dr_explicit_realign_optimized
4181               || alignment_support_scheme == dr_explicit_realign)
4182             {
4183               tree tmp;
4184
4185               lsq = gimple_assign_lhs (new_stmt);
4186               if (!realignment_token)
4187                 realignment_token = dataref_ptr;
4188               vec_dest = vect_create_destination_var (scalar_dest, vectype);
4189               tmp = build3 (REALIGN_LOAD_EXPR, vectype, msq, lsq,
4190                             realignment_token);
4191               new_stmt = gimple_build_assign (vec_dest, tmp);
4192               new_temp = make_ssa_name (vec_dest, new_stmt);
4193               gimple_assign_set_lhs (new_stmt, new_temp);
4194               vect_finish_stmt_generation (stmt, new_stmt, gsi);
4195
4196               if (alignment_support_scheme == dr_explicit_realign_optimized)
4197                 {
4198                   gcc_assert (phi);
4199                   if (i == vec_num - 1 && j == ncopies - 1)
4200                     add_phi_arg (phi, lsq, loop_latch_edge (containing_loop),
4201                                  UNKNOWN_LOCATION);
4202                   msq = lsq;
4203                 }
4204             }
4205
4206           /* 4. Handle invariant-load.  */
4207           if (inv_p && !bb_vinfo)
4208             {
4209               gcc_assert (!strided_load);
4210               gcc_assert (nested_in_vect_loop_p (loop, stmt));
4211               if (j == 0)
4212                 {
4213                   int k;
4214                   tree t = NULL_TREE;
4215                   tree vec_inv, bitpos, bitsize = TYPE_SIZE (scalar_type);
4216
4217                   /* CHECKME: bitpos depends on endianess?  */
4218                   bitpos = bitsize_zero_node;
4219                   vec_inv = build3 (BIT_FIELD_REF, scalar_type, new_temp,
4220                                     bitsize, bitpos);
4221                   vec_dest =
4222                         vect_create_destination_var (scalar_dest, NULL_TREE);
4223                   new_stmt = gimple_build_assign (vec_dest, vec_inv);
4224                   new_temp = make_ssa_name (vec_dest, new_stmt);
4225                   gimple_assign_set_lhs (new_stmt, new_temp);
4226                   vect_finish_stmt_generation (stmt, new_stmt, gsi);
4227
4228                   for (k = nunits - 1; k >= 0; --k)
4229                     t = tree_cons (NULL_TREE, new_temp, t);
4230                   /* FIXME: use build_constructor directly.  */
4231                   vec_inv = build_constructor_from_list (vectype, t);
4232                   new_temp = vect_init_vector (stmt, vec_inv, vectype, gsi);
4233                   new_stmt = SSA_NAME_DEF_STMT (new_temp);
4234                 }
4235               else
4236                 gcc_unreachable (); /* FORNOW. */
4237             }
4238
4239           if (negative)
4240             {
4241               new_temp = reverse_vec_elements (new_temp, stmt, gsi);
4242               new_stmt = SSA_NAME_DEF_STMT (new_temp);
4243             }
4244
4245           /* Collect vector loads and later create their permutation in
4246              vect_transform_strided_load ().  */
4247           if (strided_load || slp_perm)
4248             VEC_quick_push (tree, dr_chain, new_temp);
4249
4250          /* Store vector loads in the corresponding SLP_NODE.  */
4251           if (slp && !slp_perm)
4252             VEC_quick_push (gimple, SLP_TREE_VEC_STMTS (slp_node), new_stmt);
4253         }
4254
4255       if (slp && !slp_perm)
4256         continue;
4257
4258       if (slp_perm)
4259         {
4260           if (!vect_transform_slp_perm_load (stmt, dr_chain, gsi, vf,
4261                                              slp_node_instance, false))
4262             {
4263               VEC_free (tree, heap, dr_chain);
4264               return false;
4265             }
4266         }
4267       else
4268         {
4269           if (strided_load)
4270             {
4271               if (!vect_transform_strided_load (stmt, dr_chain, group_size, gsi))
4272                 return false;
4273
4274               *vec_stmt = STMT_VINFO_VEC_STMT (stmt_info);
4275               VEC_free (tree, heap, dr_chain);
4276               dr_chain = VEC_alloc (tree, heap, group_size);
4277             }
4278           else
4279             {
4280               if (j == 0)
4281                 STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
4282               else
4283                 STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
4284               prev_stmt_info = vinfo_for_stmt (new_stmt);
4285             }
4286         }
4287     }
4288
4289   if (dr_chain)
4290     VEC_free (tree, heap, dr_chain);
4291
4292   return true;
4293 }
4294
4295 /* Function vect_is_simple_cond.
4296
4297    Input:
4298    LOOP - the loop that is being vectorized.
4299    COND - Condition that is checked for simple use.
4300
4301    Returns whether a COND can be vectorized.  Checks whether
4302    condition operands are supportable using vec_is_simple_use.  */
4303
4304 static bool
4305 vect_is_simple_cond (tree cond, loop_vec_info loop_vinfo)
4306 {
4307   tree lhs, rhs;
4308   tree def;
4309   enum vect_def_type dt;
4310
4311   if (!COMPARISON_CLASS_P (cond))
4312     return false;
4313
4314   lhs = TREE_OPERAND (cond, 0);
4315   rhs = TREE_OPERAND (cond, 1);
4316
4317   if (TREE_CODE (lhs) == SSA_NAME)
4318     {
4319       gimple lhs_def_stmt = SSA_NAME_DEF_STMT (lhs);
4320       if (!vect_is_simple_use (lhs, loop_vinfo, NULL, &lhs_def_stmt, &def,
4321                                &dt))
4322         return false;
4323     }
4324   else if (TREE_CODE (lhs) != INTEGER_CST && TREE_CODE (lhs) != REAL_CST
4325            && TREE_CODE (lhs) != FIXED_CST)
4326     return false;
4327
4328   if (TREE_CODE (rhs) == SSA_NAME)
4329     {
4330       gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
4331       if (!vect_is_simple_use (rhs, loop_vinfo, NULL, &rhs_def_stmt, &def,
4332                                &dt))
4333         return false;
4334     }
4335   else if (TREE_CODE (rhs) != INTEGER_CST  && TREE_CODE (rhs) != REAL_CST
4336            && TREE_CODE (rhs) != FIXED_CST)
4337     return false;
4338
4339   return true;
4340 }
4341
4342 /* vectorizable_condition.
4343
4344    Check if STMT is conditional modify expression that can be vectorized.
4345    If VEC_STMT is also passed, vectorize the STMT: create a vectorized
4346    stmt using VEC_COND_EXPR  to replace it, put it in VEC_STMT, and insert it
4347    at GSI.
4348
4349    When STMT is vectorized as nested cycle, REDUC_DEF is the vector variable
4350    to be used at REDUC_INDEX (in then clause if REDUC_INDEX is 1, and in
4351    else caluse if it is 2).
4352
4353    Return FALSE if not a vectorizable STMT, TRUE otherwise.  */
4354
4355 bool
4356 vectorizable_condition (gimple stmt, gimple_stmt_iterator *gsi,
4357                         gimple *vec_stmt, tree reduc_def, int reduc_index)
4358 {
4359   tree scalar_dest = NULL_TREE;
4360   tree vec_dest = NULL_TREE;
4361   tree op = NULL_TREE;
4362   tree cond_expr, then_clause, else_clause;
4363   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4364   tree vectype = STMT_VINFO_VECTYPE (stmt_info);
4365   tree vec_cond_lhs = NULL_TREE, vec_cond_rhs = NULL_TREE;
4366   tree vec_then_clause = NULL_TREE, vec_else_clause = NULL_TREE;
4367   tree vec_compare, vec_cond_expr;
4368   tree new_temp;
4369   loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
4370   enum machine_mode vec_mode;
4371   tree def;
4372   enum vect_def_type dt, dts[4];
4373   int nunits = TYPE_VECTOR_SUBPARTS (vectype);
4374   int ncopies = LOOP_VINFO_VECT_FACTOR (loop_vinfo) / nunits;
4375   enum tree_code code;
4376   stmt_vec_info prev_stmt_info = NULL;
4377   int j;
4378
4379   /* FORNOW: unsupported in basic block SLP.  */
4380   gcc_assert (loop_vinfo);
4381
4382   gcc_assert (ncopies >= 1);
4383   if (reduc_index && ncopies > 1)
4384     return false; /* FORNOW */
4385
4386   if (!STMT_VINFO_RELEVANT_P (stmt_info))
4387     return false;
4388
4389   if (STMT_VINFO_DEF_TYPE (stmt_info) != vect_internal_def
4390       && !(STMT_VINFO_DEF_TYPE (stmt_info) == vect_nested_cycle
4391            && reduc_def))
4392     return false;
4393
4394   /* FORNOW: SLP not supported.  */
4395   if (STMT_SLP_TYPE (stmt_info))
4396     return false;
4397
4398   /* FORNOW: not yet supported.  */
4399   if (STMT_VINFO_LIVE_P (stmt_info))
4400     {
4401       if (vect_print_dump_info (REPORT_DETAILS))
4402         fprintf (vect_dump, "value used after loop.");
4403       return false;
4404     }
4405
4406   /* Is vectorizable conditional operation?  */
4407   if (!is_gimple_assign (stmt))
4408     return false;
4409
4410   code = gimple_assign_rhs_code (stmt);
4411
4412   if (code != COND_EXPR)
4413     return false;
4414
4415   gcc_assert (gimple_assign_single_p (stmt));
4416   op = gimple_assign_rhs1 (stmt);
4417   cond_expr = TREE_OPERAND (op, 0);
4418   then_clause = TREE_OPERAND (op, 1);
4419   else_clause = TREE_OPERAND (op, 2);
4420
4421   if (!vect_is_simple_cond (cond_expr, loop_vinfo))
4422     return false;
4423
4424   /* We do not handle two different vector types for the condition
4425      and the values.  */
4426   if (!types_compatible_p (TREE_TYPE (TREE_OPERAND (cond_expr, 0)),
4427                            TREE_TYPE (vectype)))
4428     return false;
4429
4430   if (TREE_CODE (then_clause) == SSA_NAME)
4431     {
4432       gimple then_def_stmt = SSA_NAME_DEF_STMT (then_clause);
4433       if (!vect_is_simple_use (then_clause, loop_vinfo, NULL,
4434                                &then_def_stmt, &def, &dt))
4435         return false;
4436     }
4437   else if (TREE_CODE (then_clause) != INTEGER_CST
4438            && TREE_CODE (then_clause) != REAL_CST
4439            && TREE_CODE (then_clause) != FIXED_CST)
4440     return false;
4441
4442   if (TREE_CODE (else_clause) == SSA_NAME)
4443     {
4444       gimple else_def_stmt = SSA_NAME_DEF_STMT (else_clause);
4445       if (!vect_is_simple_use (else_clause, loop_vinfo, NULL,
4446                                &else_def_stmt, &def, &dt))
4447         return false;
4448     }
4449   else if (TREE_CODE (else_clause) != INTEGER_CST
4450            && TREE_CODE (else_clause) != REAL_CST
4451            && TREE_CODE (else_clause) != FIXED_CST)
4452     return false;
4453
4454
4455   vec_mode = TYPE_MODE (vectype);
4456
4457   if (!vec_stmt)
4458     {
4459       STMT_VINFO_TYPE (stmt_info) = condition_vec_info_type;
4460       return expand_vec_cond_expr_p (TREE_TYPE (op), vec_mode);
4461     }
4462
4463   /* Transform */
4464
4465   /* Handle def.  */
4466   scalar_dest = gimple_assign_lhs (stmt);
4467   vec_dest = vect_create_destination_var (scalar_dest, vectype);
4468
4469   /* Handle cond expr.  */
4470   for (j = 0; j < ncopies; j++)
4471     {
4472       gimple new_stmt;
4473       if (j == 0)
4474         {
4475           gimple gtemp;
4476           vec_cond_lhs =
4477               vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 0),
4478                                             stmt, NULL);
4479           vect_is_simple_use (TREE_OPERAND (cond_expr, 0), loop_vinfo,
4480                               NULL, &gtemp, &def, &dts[0]);
4481           vec_cond_rhs =
4482               vect_get_vec_def_for_operand (TREE_OPERAND (cond_expr, 1),
4483                                             stmt, NULL);
4484           vect_is_simple_use (TREE_OPERAND (cond_expr, 1), loop_vinfo,
4485                               NULL, &gtemp, &def, &dts[1]);
4486           if (reduc_index == 1)
4487             vec_then_clause = reduc_def;
4488           else
4489             {
4490               vec_then_clause = vect_get_vec_def_for_operand (then_clause,
4491                                                               stmt, NULL);
4492               vect_is_simple_use (then_clause, loop_vinfo,
4493                                   NULL, &gtemp, &def, &dts[2]);
4494             }
4495           if (reduc_index == 2)
4496             vec_else_clause = reduc_def;
4497           else
4498             {
4499               vec_else_clause = vect_get_vec_def_for_operand (else_clause,
4500                                                               stmt, NULL);
4501               vect_is_simple_use (else_clause, loop_vinfo,
4502                                   NULL, &gtemp, &def, &dts[3]);
4503             }
4504         }
4505       else
4506         {
4507           vec_cond_lhs = vect_get_vec_def_for_stmt_copy (dts[0], vec_cond_lhs);
4508           vec_cond_rhs = vect_get_vec_def_for_stmt_copy (dts[1], vec_cond_rhs);
4509           vec_then_clause = vect_get_vec_def_for_stmt_copy (dts[2],
4510                                                             vec_then_clause);
4511           vec_else_clause = vect_get_vec_def_for_stmt_copy (dts[3],
4512                                                             vec_else_clause);
4513         }
4514
4515       /* Arguments are ready.  Create the new vector stmt.  */
4516       vec_compare = build2 (TREE_CODE (cond_expr), vectype,
4517                             vec_cond_lhs, vec_cond_rhs);
4518       vec_cond_expr = build3 (VEC_COND_EXPR, vectype,
4519                               vec_compare, vec_then_clause, vec_else_clause);
4520
4521       new_stmt = gimple_build_assign (vec_dest, vec_cond_expr);
4522       new_temp = make_ssa_name (vec_dest, new_stmt);
4523       gimple_assign_set_lhs (new_stmt, new_temp);
4524       vect_finish_stmt_generation (stmt, new_stmt, gsi);
4525       if (j == 0)
4526         STMT_VINFO_VEC_STMT (stmt_info) = *vec_stmt = new_stmt;
4527       else
4528         STMT_VINFO_RELATED_STMT (prev_stmt_info) = new_stmt;
4529
4530       prev_stmt_info = vinfo_for_stmt (new_stmt);
4531     }
4532
4533   return true;
4534 }
4535
4536
4537 /* Make sure the statement is vectorizable.  */
4538
4539 bool
4540 vect_analyze_stmt (gimple stmt, bool *need_to_vectorize, slp_tree node)
4541 {
4542   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4543   bb_vec_info bb_vinfo = STMT_VINFO_BB_VINFO (stmt_info);
4544   enum vect_relevant relevance = STMT_VINFO_RELEVANT (stmt_info);
4545   bool ok;
4546   tree scalar_type, vectype;
4547
4548   if (vect_print_dump_info (REPORT_DETAILS))
4549     {
4550       fprintf (vect_dump, "==> examining statement: ");
4551       print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
4552     }
4553
4554   if (gimple_has_volatile_ops (stmt))
4555     {
4556       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
4557         fprintf (vect_dump, "not vectorized: stmt has volatile operands");
4558
4559       return false;
4560     }
4561
4562   /* Skip stmts that do not need to be vectorized. In loops this is expected
4563      to include:
4564      - the COND_EXPR which is the loop exit condition
4565      - any LABEL_EXPRs in the loop
4566      - computations that are used only for array indexing or loop control.
4567      In basic blocks we only analyze statements that are a part of some SLP
4568      instance, therefore, all the statements are relevant.  */
4569
4570   if (!STMT_VINFO_RELEVANT_P (stmt_info)
4571       && !STMT_VINFO_LIVE_P (stmt_info))
4572     {
4573       if (vect_print_dump_info (REPORT_DETAILS))
4574         fprintf (vect_dump, "irrelevant.");
4575
4576       return true;
4577     }
4578
4579   switch (STMT_VINFO_DEF_TYPE (stmt_info))
4580     {
4581       case vect_internal_def:
4582         break;
4583
4584       case vect_reduction_def:
4585       case vect_nested_cycle:
4586          gcc_assert (!bb_vinfo && (relevance == vect_used_in_outer
4587                      || relevance == vect_used_in_outer_by_reduction
4588                      || relevance == vect_unused_in_scope));
4589          break;
4590
4591       case vect_induction_def:
4592       case vect_constant_def:
4593       case vect_external_def:
4594       case vect_unknown_def_type:
4595       default:
4596         gcc_unreachable ();
4597     }
4598
4599   if (bb_vinfo)
4600     {
4601       gcc_assert (PURE_SLP_STMT (stmt_info));
4602
4603       scalar_type = TREE_TYPE (gimple_get_lhs (stmt));
4604       if (vect_print_dump_info (REPORT_DETAILS))
4605         {
4606           fprintf (vect_dump, "get vectype for scalar type:  ");
4607           print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
4608         }
4609
4610       vectype = get_vectype_for_scalar_type (scalar_type);
4611       if (!vectype)
4612         {
4613           if (vect_print_dump_info (REPORT_DETAILS))
4614             {
4615                fprintf (vect_dump, "not SLPed: unsupported data-type ");
4616                print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
4617             }
4618           return false;
4619         }
4620
4621       if (vect_print_dump_info (REPORT_DETAILS))
4622         {
4623           fprintf (vect_dump, "vectype:  ");
4624           print_generic_expr (vect_dump, vectype, TDF_SLIM);
4625         }
4626
4627       STMT_VINFO_VECTYPE (stmt_info) = vectype;
4628    }
4629
4630   if (STMT_VINFO_RELEVANT_P (stmt_info))
4631     {
4632       gcc_assert (!VECTOR_MODE_P (TYPE_MODE (gimple_expr_type (stmt))));
4633       gcc_assert (STMT_VINFO_VECTYPE (stmt_info));
4634       *need_to_vectorize = true;
4635     }
4636
4637    ok = true;
4638    if (!bb_vinfo
4639        && (STMT_VINFO_RELEVANT_P (stmt_info)
4640            || STMT_VINFO_DEF_TYPE (stmt_info) == vect_reduction_def))
4641       ok = (vectorizable_type_promotion (stmt, NULL, NULL, NULL)
4642             || vectorizable_type_demotion (stmt, NULL, NULL, NULL)
4643             || vectorizable_conversion (stmt, NULL, NULL, NULL)
4644             || vectorizable_shift (stmt, NULL, NULL, NULL)
4645             || vectorizable_operation (stmt, NULL, NULL, NULL)
4646             || vectorizable_assignment (stmt, NULL, NULL, NULL)
4647             || vectorizable_load (stmt, NULL, NULL, NULL, NULL)
4648             || vectorizable_call (stmt, NULL, NULL)
4649             || vectorizable_store (stmt, NULL, NULL, NULL)
4650             || vectorizable_reduction (stmt, NULL, NULL, NULL)
4651             || vectorizable_condition (stmt, NULL, NULL, NULL, 0));
4652     else
4653       {
4654         if (bb_vinfo)
4655           ok = (vectorizable_shift (stmt, NULL, NULL, node)
4656                 || vectorizable_operation (stmt, NULL, NULL, node)
4657                 || vectorizable_assignment (stmt, NULL, NULL, node)
4658                 || vectorizable_load (stmt, NULL, NULL, node, NULL)
4659                 || vectorizable_store (stmt, NULL, NULL, node));
4660       }
4661
4662   if (!ok)
4663     {
4664       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
4665         {
4666           fprintf (vect_dump, "not vectorized: relevant stmt not ");
4667           fprintf (vect_dump, "supported: ");
4668           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
4669         }
4670
4671       return false;
4672     }
4673
4674   if (bb_vinfo)
4675     return true;
4676
4677   /* Stmts that are (also) "live" (i.e. - that are used out of the loop)
4678       need extra handling, except for vectorizable reductions.  */
4679   if (STMT_VINFO_LIVE_P (stmt_info)
4680       && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type)
4681     ok = vectorizable_live_operation (stmt, NULL, NULL);
4682
4683   if (!ok)
4684     {
4685       if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
4686         {
4687           fprintf (vect_dump, "not vectorized: live stmt not ");
4688           fprintf (vect_dump, "supported: ");
4689           print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
4690         }
4691
4692        return false;
4693     }
4694
4695   if (!PURE_SLP_STMT (stmt_info))
4696     {
4697       /* Groups of strided accesses whose size is not a power of 2 are not
4698          vectorizable yet using loop-vectorization.  Therefore, if this stmt
4699          feeds non-SLP-able stmts (i.e., this stmt has to be both SLPed and
4700          loop-based vectorized), the loop cannot be vectorized.  */
4701       if (STMT_VINFO_STRIDED_ACCESS (stmt_info)
4702           && exact_log2 (DR_GROUP_SIZE (vinfo_for_stmt (
4703                                         DR_GROUP_FIRST_DR (stmt_info)))) == -1)
4704         {
4705           if (vect_print_dump_info (REPORT_DETAILS))
4706             {
4707               fprintf (vect_dump, "not vectorized: the size of group "
4708                                   "of strided accesses is not a power of 2");
4709               print_gimple_stmt (vect_dump, stmt, 0, TDF_SLIM);
4710             }
4711
4712           return false;
4713         }
4714     }
4715
4716   return true;
4717 }
4718
4719
4720 /* Function vect_transform_stmt.
4721
4722    Create a vectorized stmt to replace STMT, and insert it at BSI.  */
4723
4724 bool
4725 vect_transform_stmt (gimple stmt, gimple_stmt_iterator *gsi,
4726                      bool *strided_store, slp_tree slp_node,
4727                      slp_instance slp_node_instance)
4728 {
4729   bool is_store = false;
4730   gimple vec_stmt = NULL;
4731   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4732   gimple orig_stmt_in_pattern, orig_scalar_stmt = stmt;
4733   bool done;
4734
4735   switch (STMT_VINFO_TYPE (stmt_info))
4736     {
4737     case type_demotion_vec_info_type:
4738       done = vectorizable_type_demotion (stmt, gsi, &vec_stmt, slp_node);
4739       gcc_assert (done);
4740       break;
4741
4742     case type_promotion_vec_info_type:
4743       done = vectorizable_type_promotion (stmt, gsi, &vec_stmt, slp_node);
4744       gcc_assert (done);
4745       break;
4746
4747     case type_conversion_vec_info_type:
4748       done = vectorizable_conversion (stmt, gsi, &vec_stmt, slp_node);
4749       gcc_assert (done);
4750       break;
4751
4752     case induc_vec_info_type:
4753       gcc_assert (!slp_node);
4754       done = vectorizable_induction (stmt, gsi, &vec_stmt);
4755       gcc_assert (done);
4756       break;
4757
4758     case shift_vec_info_type:
4759       done = vectorizable_shift (stmt, gsi, &vec_stmt, slp_node);
4760       gcc_assert (done);
4761       break;
4762
4763     case op_vec_info_type:
4764       done = vectorizable_operation (stmt, gsi, &vec_stmt, slp_node);
4765       gcc_assert (done);
4766       break;
4767
4768     case assignment_vec_info_type:
4769       done = vectorizable_assignment (stmt, gsi, &vec_stmt, slp_node);
4770       gcc_assert (done);
4771       break;
4772
4773     case load_vec_info_type:
4774       done = vectorizable_load (stmt, gsi, &vec_stmt, slp_node,
4775                                 slp_node_instance);
4776       gcc_assert (done);
4777       break;
4778
4779     case store_vec_info_type:
4780       done = vectorizable_store (stmt, gsi, &vec_stmt, slp_node);
4781       gcc_assert (done);
4782       if (STMT_VINFO_STRIDED_ACCESS (stmt_info) && !slp_node)
4783         {
4784           /* In case of interleaving, the whole chain is vectorized when the
4785              last store in the chain is reached.  Store stmts before the last
4786              one are skipped, and there vec_stmt_info shouldn't be freed
4787              meanwhile.  */
4788           *strided_store = true;
4789           if (STMT_VINFO_VEC_STMT (stmt_info))
4790             is_store = true;
4791           }
4792       else
4793         is_store = true;
4794       break;
4795
4796     case condition_vec_info_type:
4797       gcc_assert (!slp_node);
4798       done = vectorizable_condition (stmt, gsi, &vec_stmt, NULL, 0);
4799       gcc_assert (done);
4800       break;
4801
4802     case call_vec_info_type:
4803       gcc_assert (!slp_node);
4804       done = vectorizable_call (stmt, gsi, &vec_stmt);
4805       stmt = gsi_stmt (*gsi);
4806       break;
4807
4808     case reduc_vec_info_type:
4809       done = vectorizable_reduction (stmt, gsi, &vec_stmt, slp_node);
4810       gcc_assert (done);
4811       break;
4812
4813     default:
4814       if (!STMT_VINFO_LIVE_P (stmt_info))
4815         {
4816           if (vect_print_dump_info (REPORT_DETAILS))
4817             fprintf (vect_dump, "stmt not supported.");
4818           gcc_unreachable ();
4819         }
4820     }
4821
4822   /* Handle inner-loop stmts whose DEF is used in the loop-nest that
4823      is being vectorized, but outside the immediately enclosing loop.  */
4824   if (vec_stmt
4825       && STMT_VINFO_LOOP_VINFO (stmt_info)
4826       && nested_in_vect_loop_p (LOOP_VINFO_LOOP (
4827                                 STMT_VINFO_LOOP_VINFO (stmt_info)), stmt)
4828       && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type
4829       && (STMT_VINFO_RELEVANT (stmt_info) == vect_used_in_outer
4830           || STMT_VINFO_RELEVANT (stmt_info) ==
4831                                            vect_used_in_outer_by_reduction))
4832     {
4833       struct loop *innerloop = LOOP_VINFO_LOOP (
4834                                 STMT_VINFO_LOOP_VINFO (stmt_info))->inner;
4835       imm_use_iterator imm_iter;
4836       use_operand_p use_p;
4837       tree scalar_dest;
4838       gimple exit_phi;
4839
4840       if (vect_print_dump_info (REPORT_DETAILS))
4841         fprintf (vect_dump, "Record the vdef for outer-loop vectorization.");
4842
4843       /* Find the relevant loop-exit phi-node, and reord the vec_stmt there
4844         (to be used when vectorizing outer-loop stmts that use the DEF of
4845         STMT).  */
4846       if (gimple_code (stmt) == GIMPLE_PHI)
4847         scalar_dest = PHI_RESULT (stmt);
4848       else
4849         scalar_dest = gimple_assign_lhs (stmt);
4850
4851       FOR_EACH_IMM_USE_FAST (use_p, imm_iter, scalar_dest)
4852        {
4853          if (!flow_bb_inside_loop_p (innerloop, gimple_bb (USE_STMT (use_p))))
4854            {
4855              exit_phi = USE_STMT (use_p);
4856              STMT_VINFO_VEC_STMT (vinfo_for_stmt (exit_phi)) = vec_stmt;
4857            }
4858        }
4859     }
4860
4861   /* Handle stmts whose DEF is used outside the loop-nest that is
4862      being vectorized.  */
4863   if (STMT_VINFO_LIVE_P (stmt_info)
4864       && STMT_VINFO_TYPE (stmt_info) != reduc_vec_info_type)
4865     {
4866       done = vectorizable_live_operation (stmt, gsi, &vec_stmt);
4867       gcc_assert (done);
4868     }
4869
4870   if (vec_stmt)
4871     {
4872       STMT_VINFO_VEC_STMT (stmt_info) = vec_stmt;
4873       orig_stmt_in_pattern = STMT_VINFO_RELATED_STMT (stmt_info);
4874       if (orig_stmt_in_pattern)
4875         {
4876           stmt_vec_info stmt_vinfo = vinfo_for_stmt (orig_stmt_in_pattern);
4877           /* STMT was inserted by the vectorizer to replace a computation idiom.
4878              ORIG_STMT_IN_PATTERN is a stmt in the original sequence that
4879              computed this idiom.  We need to record a pointer to VEC_STMT in
4880              the stmt_info of ORIG_STMT_IN_PATTERN.  See more details in the
4881              documentation of vect_pattern_recog.  */
4882           if (STMT_VINFO_IN_PATTERN_P (stmt_vinfo))
4883             {
4884               gcc_assert (STMT_VINFO_RELATED_STMT (stmt_vinfo)
4885                            == orig_scalar_stmt);
4886               STMT_VINFO_VEC_STMT (stmt_vinfo) = vec_stmt;
4887             }
4888         }
4889     }
4890
4891   return is_store;
4892 }
4893
4894
4895 /* Remove a group of stores (for SLP or interleaving), free their
4896    stmt_vec_info.  */
4897
4898 void
4899 vect_remove_stores (gimple first_stmt)
4900 {
4901   gimple next = first_stmt;
4902   gimple tmp;
4903   gimple_stmt_iterator next_si;
4904
4905   while (next)
4906     {
4907       /* Free the attached stmt_vec_info and remove the stmt.  */
4908       next_si = gsi_for_stmt (next);
4909       gsi_remove (&next_si, true);
4910       tmp = DR_GROUP_NEXT_DR (vinfo_for_stmt (next));
4911       free_stmt_vec_info (next);
4912       next = tmp;
4913     }
4914 }
4915
4916
4917 /* Function new_stmt_vec_info.
4918
4919    Create and initialize a new stmt_vec_info struct for STMT.  */
4920
4921 stmt_vec_info
4922 new_stmt_vec_info (gimple stmt, loop_vec_info loop_vinfo,
4923                    bb_vec_info bb_vinfo)
4924 {
4925   stmt_vec_info res;
4926   res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
4927
4928   STMT_VINFO_TYPE (res) = undef_vec_info_type;
4929   STMT_VINFO_STMT (res) = stmt;
4930   STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
4931   STMT_VINFO_BB_VINFO (res) = bb_vinfo;
4932   STMT_VINFO_RELEVANT (res) = vect_unused_in_scope;
4933   STMT_VINFO_LIVE_P (res) = false;
4934   STMT_VINFO_VECTYPE (res) = NULL;
4935   STMT_VINFO_VEC_STMT (res) = NULL;
4936   STMT_VINFO_VECTORIZABLE (res) = true;
4937   STMT_VINFO_IN_PATTERN_P (res) = false;
4938   STMT_VINFO_RELATED_STMT (res) = NULL;
4939   STMT_VINFO_DATA_REF (res) = NULL;
4940
4941   STMT_VINFO_DR_BASE_ADDRESS (res) = NULL;
4942   STMT_VINFO_DR_OFFSET (res) = NULL;
4943   STMT_VINFO_DR_INIT (res) = NULL;
4944   STMT_VINFO_DR_STEP (res) = NULL;
4945   STMT_VINFO_DR_ALIGNED_TO (res) = NULL;
4946
4947   if (gimple_code (stmt) == GIMPLE_PHI
4948       && is_loop_header_bb_p (gimple_bb (stmt)))
4949     STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
4950   else
4951     STMT_VINFO_DEF_TYPE (res) = vect_internal_def;
4952
4953   STMT_VINFO_SAME_ALIGN_REFS (res) = VEC_alloc (dr_p, heap, 5);
4954   STMT_VINFO_INSIDE_OF_LOOP_COST (res) = 0;
4955   STMT_VINFO_OUTSIDE_OF_LOOP_COST (res) = 0;
4956   STMT_SLP_TYPE (res) = loop_vect;
4957   DR_GROUP_FIRST_DR (res) = NULL;
4958   DR_GROUP_NEXT_DR (res) = NULL;
4959   DR_GROUP_SIZE (res) = 0;
4960   DR_GROUP_STORE_COUNT (res) = 0;
4961   DR_GROUP_GAP (res) = 0;
4962   DR_GROUP_SAME_DR_STMT (res) = NULL;
4963   DR_GROUP_READ_WRITE_DEPENDENCE (res) = false;
4964
4965   return res;
4966 }
4967
4968
4969 /* Create a hash table for stmt_vec_info. */
4970
4971 void
4972 init_stmt_vec_info_vec (void)
4973 {
4974   gcc_assert (!stmt_vec_info_vec);
4975   stmt_vec_info_vec = VEC_alloc (vec_void_p, heap, 50);
4976 }
4977
4978
4979 /* Free hash table for stmt_vec_info. */
4980
4981 void
4982 free_stmt_vec_info_vec (void)
4983 {
4984   gcc_assert (stmt_vec_info_vec);
4985   VEC_free (vec_void_p, heap, stmt_vec_info_vec);
4986 }
4987
4988
4989 /* Free stmt vectorization related info.  */
4990
4991 void
4992 free_stmt_vec_info (gimple stmt)
4993 {
4994   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
4995
4996   if (!stmt_info)
4997     return;
4998
4999   VEC_free (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmt_info));
5000   set_vinfo_for_stmt (stmt, NULL);
5001   free (stmt_info);
5002 }
5003
5004
5005 /* Function get_vectype_for_scalar_type_and_size.
5006
5007    Returns the vector type corresponding to SCALAR_TYPE  and SIZE as supported
5008    by the target.  */
5009
5010 static tree
5011 get_vectype_for_scalar_type_and_size (tree scalar_type, unsigned size)
5012 {
5013   enum machine_mode inner_mode = TYPE_MODE (scalar_type);
5014   enum machine_mode simd_mode;
5015   unsigned int nbytes = GET_MODE_SIZE (inner_mode);
5016   int nunits;
5017   tree vectype;
5018
5019   if (nbytes == 0)
5020     return NULL_TREE;
5021
5022   /* We can't build a vector type of elements with alignment bigger than
5023      their size.  */
5024   if (nbytes < TYPE_ALIGN_UNIT (scalar_type))
5025     return NULL_TREE;
5026
5027   /* If we'd build a vector type of elements whose mode precision doesn't
5028      match their types precision we'll get mismatched types on vector
5029      extracts via BIT_FIELD_REFs.  This effectively means we disable
5030      vectorization of bool and/or enum types in some languages.  */
5031   if (INTEGRAL_TYPE_P (scalar_type)
5032       && GET_MODE_BITSIZE (inner_mode) != TYPE_PRECISION (scalar_type))
5033     return NULL_TREE;
5034
5035   if (GET_MODE_CLASS (inner_mode) != MODE_INT
5036       && GET_MODE_CLASS (inner_mode) != MODE_FLOAT)
5037     return NULL_TREE;
5038
5039   /* If no size was supplied use the mode the target prefers.   Otherwise
5040      lookup a vector mode of the specified size.  */
5041   if (size == 0)
5042     simd_mode = targetm.vectorize.preferred_simd_mode (inner_mode);
5043   else
5044     simd_mode = mode_for_vector (inner_mode, size / nbytes);
5045   nunits = GET_MODE_SIZE (simd_mode) / nbytes;
5046   if (nunits <= 1)
5047     return NULL_TREE;
5048
5049   vectype = build_vector_type (scalar_type, nunits);
5050   if (vect_print_dump_info (REPORT_DETAILS))
5051     {
5052       fprintf (vect_dump, "get vectype with %d units of type ", nunits);
5053       print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
5054     }
5055
5056   if (!vectype)
5057     return NULL_TREE;
5058
5059   if (vect_print_dump_info (REPORT_DETAILS))
5060     {
5061       fprintf (vect_dump, "vectype: ");
5062       print_generic_expr (vect_dump, vectype, TDF_SLIM);
5063     }
5064
5065   if (!VECTOR_MODE_P (TYPE_MODE (vectype))
5066       && !INTEGRAL_MODE_P (TYPE_MODE (vectype)))
5067     {
5068       if (vect_print_dump_info (REPORT_DETAILS))
5069         fprintf (vect_dump, "mode not supported by target.");
5070       return NULL_TREE;
5071     }
5072
5073   return vectype;
5074 }
5075
5076 unsigned int current_vector_size;
5077
5078 /* Function get_vectype_for_scalar_type.
5079
5080    Returns the vector type corresponding to SCALAR_TYPE as supported
5081    by the target.  */
5082
5083 tree
5084 get_vectype_for_scalar_type (tree scalar_type)
5085 {
5086   tree vectype;
5087   vectype = get_vectype_for_scalar_type_and_size (scalar_type,
5088                                                   current_vector_size);
5089   if (vectype
5090       && current_vector_size == 0)
5091     current_vector_size = GET_MODE_SIZE (TYPE_MODE (vectype));
5092   return vectype;
5093 }
5094
5095 /* Function get_same_sized_vectype
5096
5097    Returns a vector type corresponding to SCALAR_TYPE of size
5098    VECTOR_TYPE if supported by the target.  */
5099
5100 tree
5101 get_same_sized_vectype (tree scalar_type, tree vector_type)
5102 {
5103   return get_vectype_for_scalar_type_and_size
5104            (scalar_type, GET_MODE_SIZE (TYPE_MODE (vector_type)));
5105 }
5106
5107 /* Function vect_is_simple_use.
5108
5109    Input:
5110    LOOP_VINFO - the vect info of the loop that is being vectorized.
5111    BB_VINFO - the vect info of the basic block that is being vectorized.
5112    OPERAND - operand of a stmt in the loop or bb.
5113    DEF - the defining stmt in case OPERAND is an SSA_NAME.
5114
5115    Returns whether a stmt with OPERAND can be vectorized.
5116    For loops, supportable operands are constants, loop invariants, and operands
5117    that are defined by the current iteration of the loop.  Unsupportable
5118    operands are those that are defined by a previous iteration of the loop (as
5119    is the case in reduction/induction computations).
5120    For basic blocks, supportable operands are constants and bb invariants.
5121    For now, operands defined outside the basic block are not supported.  */
5122
5123 bool
5124 vect_is_simple_use (tree operand, loop_vec_info loop_vinfo,
5125                     bb_vec_info bb_vinfo, gimple *def_stmt,
5126                     tree *def, enum vect_def_type *dt)
5127 {
5128   basic_block bb;
5129   stmt_vec_info stmt_vinfo;
5130   struct loop *loop = NULL;
5131
5132   if (loop_vinfo)
5133     loop = LOOP_VINFO_LOOP (loop_vinfo);
5134
5135   *def_stmt = NULL;
5136   *def = NULL_TREE;
5137
5138   if (vect_print_dump_info (REPORT_DETAILS))
5139     {
5140       fprintf (vect_dump, "vect_is_simple_use: operand ");
5141       print_generic_expr (vect_dump, operand, TDF_SLIM);
5142     }
5143
5144   if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
5145     {
5146       *dt = vect_constant_def;
5147       return true;
5148     }
5149
5150   if (is_gimple_min_invariant (operand))
5151     {
5152       *def = operand;
5153       *dt = vect_external_def;
5154       return true;
5155     }
5156
5157   if (TREE_CODE (operand) == PAREN_EXPR)
5158     {
5159       if (vect_print_dump_info (REPORT_DETAILS))
5160         fprintf (vect_dump, "non-associatable copy.");
5161       operand = TREE_OPERAND (operand, 0);
5162     }
5163
5164   if (TREE_CODE (operand) != SSA_NAME)
5165     {
5166       if (vect_print_dump_info (REPORT_DETAILS))
5167         fprintf (vect_dump, "not ssa-name.");
5168       return false;
5169     }
5170
5171   *def_stmt = SSA_NAME_DEF_STMT (operand);
5172   if (*def_stmt == NULL)
5173     {
5174       if (vect_print_dump_info (REPORT_DETAILS))
5175         fprintf (vect_dump, "no def_stmt.");
5176       return false;
5177     }
5178
5179   if (vect_print_dump_info (REPORT_DETAILS))
5180     {
5181       fprintf (vect_dump, "def_stmt: ");
5182       print_gimple_stmt (vect_dump, *def_stmt, 0, TDF_SLIM);
5183     }
5184
5185   /* Empty stmt is expected only in case of a function argument.
5186      (Otherwise - we expect a phi_node or a GIMPLE_ASSIGN).  */
5187   if (gimple_nop_p (*def_stmt))
5188     {
5189       *def = operand;
5190       *dt = vect_external_def;
5191       return true;
5192     }
5193
5194   bb = gimple_bb (*def_stmt);
5195
5196   if ((loop && !flow_bb_inside_loop_p (loop, bb))
5197       || (!loop && bb != BB_VINFO_BB (bb_vinfo))
5198       || (!loop && gimple_code (*def_stmt) == GIMPLE_PHI))
5199     *dt = vect_external_def;
5200   else
5201     {
5202       stmt_vinfo = vinfo_for_stmt (*def_stmt);
5203       *dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
5204     }
5205
5206   if (*dt == vect_unknown_def_type)
5207     {
5208       if (vect_print_dump_info (REPORT_DETAILS))
5209         fprintf (vect_dump, "Unsupported pattern.");
5210       return false;
5211     }
5212
5213   if (vect_print_dump_info (REPORT_DETAILS))
5214     fprintf (vect_dump, "type of def: %d.",*dt);
5215
5216   switch (gimple_code (*def_stmt))
5217     {
5218     case GIMPLE_PHI:
5219       *def = gimple_phi_result (*def_stmt);
5220       break;
5221
5222     case GIMPLE_ASSIGN:
5223       *def = gimple_assign_lhs (*def_stmt);
5224       break;
5225
5226     case GIMPLE_CALL:
5227       *def = gimple_call_lhs (*def_stmt);
5228       if (*def != NULL)
5229         break;
5230       /* FALLTHRU */
5231     default:
5232       if (vect_print_dump_info (REPORT_DETAILS))
5233         fprintf (vect_dump, "unsupported defining stmt: ");
5234       return false;
5235     }
5236
5237   return true;
5238 }
5239
5240 /* Function vect_is_simple_use_1.
5241
5242    Same as vect_is_simple_use_1 but also determines the vector operand
5243    type of OPERAND and stores it to *VECTYPE.  If the definition of
5244    OPERAND is vect_uninitialized_def, vect_constant_def or
5245    vect_external_def *VECTYPE will be set to NULL_TREE and the caller
5246    is responsible to compute the best suited vector type for the
5247    scalar operand.  */
5248
5249 bool
5250 vect_is_simple_use_1 (tree operand, loop_vec_info loop_vinfo,
5251                       bb_vec_info bb_vinfo, gimple *def_stmt,
5252                       tree *def, enum vect_def_type *dt, tree *vectype)
5253 {
5254   if (!vect_is_simple_use (operand, loop_vinfo, bb_vinfo, def_stmt, def, dt))
5255     return false;
5256
5257   /* Now get a vector type if the def is internal, otherwise supply
5258      NULL_TREE and leave it up to the caller to figure out a proper
5259      type for the use stmt.  */
5260   if (*dt == vect_internal_def
5261       || *dt == vect_induction_def
5262       || *dt == vect_reduction_def
5263       || *dt == vect_double_reduction_def
5264       || *dt == vect_nested_cycle)
5265     {
5266       stmt_vec_info stmt_info = vinfo_for_stmt (*def_stmt);
5267       if (STMT_VINFO_IN_PATTERN_P (stmt_info))
5268         stmt_info = vinfo_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info));
5269       *vectype = STMT_VINFO_VECTYPE (stmt_info);
5270       gcc_assert (*vectype != NULL_TREE);
5271     }
5272   else if (*dt == vect_uninitialized_def
5273            || *dt == vect_constant_def
5274            || *dt == vect_external_def)
5275     *vectype = NULL_TREE;
5276   else
5277     gcc_unreachable ();
5278
5279   return true;
5280 }
5281
5282
5283 /* Function supportable_widening_operation
5284
5285    Check whether an operation represented by the code CODE is a
5286    widening operation that is supported by the target platform in
5287    vector form (i.e., when operating on arguments of type VECTYPE_IN
5288    producing a result of type VECTYPE_OUT).
5289
5290    Widening operations we currently support are NOP (CONVERT), FLOAT
5291    and WIDEN_MULT.  This function checks if these operations are supported
5292    by the target platform either directly (via vector tree-codes), or via
5293    target builtins.
5294
5295    Output:
5296    - CODE1 and CODE2 are codes of vector operations to be used when
5297    vectorizing the operation, if available.
5298    - DECL1 and DECL2 are decls of target builtin functions to be used
5299    when vectorizing the operation, if available.  In this case,
5300    CODE1 and CODE2 are CALL_EXPR.
5301    - MULTI_STEP_CVT determines the number of required intermediate steps in
5302    case of multi-step conversion (like char->short->int - in that case
5303    MULTI_STEP_CVT will be 1).
5304    - INTERM_TYPES contains the intermediate type required to perform the
5305    widening operation (short in the above example).  */
5306
5307 bool
5308 supportable_widening_operation (enum tree_code code, gimple stmt,
5309                                 tree vectype_out, tree vectype_in,
5310                                 tree *decl1, tree *decl2,
5311                                 enum tree_code *code1, enum tree_code *code2,
5312                                 int *multi_step_cvt,
5313                                 VEC (tree, heap) **interm_types)
5314 {
5315   stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
5316   loop_vec_info loop_info = STMT_VINFO_LOOP_VINFO (stmt_info);
5317   struct loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
5318   bool ordered_p;
5319   enum machine_mode vec_mode;
5320   enum insn_code icode1, icode2;
5321   optab optab1, optab2;
5322   tree vectype = vectype_in;
5323   tree wide_vectype = vectype_out;
5324   enum tree_code c1, c2;
5325
5326   /* The result of a vectorized widening operation usually requires two vectors
5327      (because the widened results do not fit int one vector). The generated
5328      vector results would normally be expected to be generated in the same
5329      order as in the original scalar computation, i.e. if 8 results are
5330      generated in each vector iteration, they are to be organized as follows:
5331         vect1: [res1,res2,res3,res4], vect2: [res5,res6,res7,res8].
5332
5333      However, in the special case that the result of the widening operation is
5334      used in a reduction computation only, the order doesn't matter (because
5335      when vectorizing a reduction we change the order of the computation).
5336      Some targets can take advantage of this and generate more efficient code.
5337      For example, targets like Altivec, that support widen_mult using a sequence
5338      of {mult_even,mult_odd} generate the following vectors:
5339         vect1: [res1,res3,res5,res7], vect2: [res2,res4,res6,res8].
5340
5341      When vectorizing outer-loops, we execute the inner-loop sequentially
5342      (each vectorized inner-loop iteration contributes to VF outer-loop
5343      iterations in parallel).  We therefore don't allow to change the order
5344      of the computation in the inner-loop during outer-loop vectorization.  */
5345
5346    if (STMT_VINFO_RELEVANT (stmt_info) == vect_used_by_reduction
5347        && !nested_in_vect_loop_p (vect_loop, stmt))
5348      ordered_p = false;
5349    else
5350      ordered_p = true;
5351
5352   if (!ordered_p
5353       && code == WIDEN_MULT_EXPR
5354       && targetm.vectorize.builtin_mul_widen_even
5355       && targetm.vectorize.builtin_mul_widen_even (vectype)
5356       && targetm.vectorize.builtin_mul_widen_odd
5357       && targetm.vectorize.builtin_mul_widen_odd (vectype))
5358     {
5359       if (vect_print_dump_info (REPORT_DETAILS))
5360         fprintf (vect_dump, "Unordered widening operation detected.");
5361
5362       *code1 = *code2 = CALL_EXPR;
5363       *decl1 = targetm.vectorize.builtin_mul_widen_even (vectype);
5364       *decl2 = targetm.vectorize.builtin_mul_widen_odd (vectype);
5365       return true;
5366     }
5367
5368   switch (code)
5369     {
5370     case WIDEN_MULT_EXPR:
5371       if (BYTES_BIG_ENDIAN)
5372         {
5373           c1 = VEC_WIDEN_MULT_HI_EXPR;
5374           c2 = VEC_WIDEN_MULT_LO_EXPR;
5375         }
5376       else
5377         {
5378           c2 = VEC_WIDEN_MULT_HI_EXPR;
5379           c1 = VEC_WIDEN_MULT_LO_EXPR;
5380         }
5381       break;
5382
5383     CASE_CONVERT:
5384       if (BYTES_BIG_ENDIAN)
5385         {
5386           c1 = VEC_UNPACK_HI_EXPR;
5387           c2 = VEC_UNPACK_LO_EXPR;
5388         }
5389       else
5390         {
5391           c2 = VEC_UNPACK_HI_EXPR;
5392           c1 = VEC_UNPACK_LO_EXPR;
5393         }
5394       break;
5395
5396     case FLOAT_EXPR:
5397       if (BYTES_BIG_ENDIAN)
5398         {
5399           c1 = VEC_UNPACK_FLOAT_HI_EXPR;
5400           c2 = VEC_UNPACK_FLOAT_LO_EXPR;
5401         }
5402       else
5403         {
5404           c2 = VEC_UNPACK_FLOAT_HI_EXPR;
5405           c1 = VEC_UNPACK_FLOAT_LO_EXPR;
5406         }
5407       break;
5408
5409     case FIX_TRUNC_EXPR:
5410       /* ??? Not yet implemented due to missing VEC_UNPACK_FIX_TRUNC_HI_EXPR/
5411          VEC_UNPACK_FIX_TRUNC_LO_EXPR tree codes and optabs used for
5412          computing the operation.  */
5413       return false;
5414
5415     default:
5416       gcc_unreachable ();
5417     }
5418
5419   if (code == FIX_TRUNC_EXPR)
5420     {
5421       /* The signedness is determined from output operand.  */
5422       optab1 = optab_for_tree_code (c1, vectype_out, optab_default);
5423       optab2 = optab_for_tree_code (c2, vectype_out, optab_default);
5424     }
5425   else
5426     {
5427       optab1 = optab_for_tree_code (c1, vectype, optab_default);
5428       optab2 = optab_for_tree_code (c2, vectype, optab_default);
5429     }
5430
5431   if (!optab1 || !optab2)
5432     return false;
5433
5434   vec_mode = TYPE_MODE (vectype);
5435   if ((icode1 = optab_handler (optab1, vec_mode)) == CODE_FOR_nothing
5436        || (icode2 = optab_handler (optab2, vec_mode)) == CODE_FOR_nothing)
5437     return false;
5438
5439   /* Check if it's a multi-step conversion that can be done using intermediate
5440      types.  */
5441   if (insn_data[icode1].operand[0].mode != TYPE_MODE (wide_vectype)
5442        || insn_data[icode2].operand[0].mode != TYPE_MODE (wide_vectype))
5443     {
5444       int i;
5445       tree prev_type = vectype, intermediate_type;
5446       enum machine_mode intermediate_mode, prev_mode = vec_mode;
5447       optab optab3, optab4;
5448
5449       if (!CONVERT_EXPR_CODE_P (code))
5450         return false;
5451
5452       *code1 = c1;
5453       *code2 = c2;
5454
5455       /* We assume here that there will not be more than MAX_INTERM_CVT_STEPS
5456          intermediate steps in promotion sequence.  We try
5457          MAX_INTERM_CVT_STEPS to get to NARROW_VECTYPE, and fail if we do
5458          not.  */
5459       *interm_types = VEC_alloc (tree, heap, MAX_INTERM_CVT_STEPS);
5460       for (i = 0; i < 3; i++)
5461         {
5462           intermediate_mode = insn_data[icode1].operand[0].mode;
5463           intermediate_type = lang_hooks.types.type_for_mode (intermediate_mode,
5464                                                      TYPE_UNSIGNED (prev_type));
5465           optab3 = optab_for_tree_code (c1, intermediate_type, optab_default);
5466           optab4 = optab_for_tree_code (c2, intermediate_type, optab_default);
5467
5468           if (!optab3 || !optab4
5469               || ((icode1 = optab_handler (optab1, prev_mode))
5470                   == CODE_FOR_nothing)
5471               || insn_data[icode1].operand[0].mode != intermediate_mode
5472               || ((icode2 = optab_handler (optab2, prev_mode))
5473                   == CODE_FOR_nothing)
5474               || insn_data[icode2].operand[0].mode != intermediate_mode
5475               || ((icode1 = optab_handler (optab3, intermediate_mode))
5476                   == CODE_FOR_nothing)
5477               || ((icode2 = optab_handler (optab4, intermediate_mode))
5478                   == CODE_FOR_nothing))
5479             return false;
5480
5481           VEC_quick_push (tree, *interm_types, intermediate_type);
5482           (*multi_step_cvt)++;
5483
5484           if (insn_data[icode1].operand[0].mode == TYPE_MODE (wide_vectype)
5485               && insn_data[icode2].operand[0].mode == TYPE_MODE (wide_vectype))
5486             return true;
5487
5488           prev_type = intermediate_type;
5489           prev_mode = intermediate_mode;
5490         }
5491
5492        return false;
5493     }
5494
5495   *code1 = c1;
5496   *code2 = c2;
5497   return true;
5498 }
5499
5500
5501 /* Function supportable_narrowing_operation
5502
5503    Check whether an operation represented by the code CODE is a
5504    narrowing operation that is supported by the target platform in
5505    vector form (i.e., when operating on arguments of type VECTYPE_IN
5506    and producing a result of type VECTYPE_OUT).
5507
5508    Narrowing operations we currently support are NOP (CONVERT) and
5509    FIX_TRUNC.  This function checks if these operations are supported by
5510    the target platform directly via vector tree-codes.
5511
5512    Output:
5513    - CODE1 is the code of a vector operation to be used when
5514    vectorizing the operation, if available.
5515    - MULTI_STEP_CVT determines the number of required intermediate steps in
5516    case of multi-step conversion (like int->short->char - in that case
5517    MULTI_STEP_CVT will be 1).
5518    - INTERM_TYPES contains the intermediate type required to perform the
5519    narrowing operation (short in the above example).   */
5520
5521 bool
5522 supportable_narrowing_operation (enum tree_code code,
5523                                  tree vectype_out, tree vectype_in,
5524                                  enum tree_code *code1, int *multi_step_cvt,
5525                                  VEC (tree, heap) **interm_types)
5526 {
5527   enum machine_mode vec_mode;
5528   enum insn_code icode1;
5529   optab optab1, interm_optab;
5530   tree vectype = vectype_in;
5531   tree narrow_vectype = vectype_out;
5532   enum tree_code c1;
5533   tree intermediate_type, prev_type;
5534   int i;
5535
5536   switch (code)
5537     {
5538     CASE_CONVERT:
5539       c1 = VEC_PACK_TRUNC_EXPR;
5540       break;
5541
5542     case FIX_TRUNC_EXPR:
5543       c1 = VEC_PACK_FIX_TRUNC_EXPR;
5544       break;
5545
5546     case FLOAT_EXPR:
5547       /* ??? Not yet implemented due to missing VEC_PACK_FLOAT_EXPR
5548          tree code and optabs used for computing the operation.  */
5549       return false;
5550
5551     default:
5552       gcc_unreachable ();
5553     }
5554
5555   if (code == FIX_TRUNC_EXPR)
5556     /* The signedness is determined from output operand.  */
5557     optab1 = optab_for_tree_code (c1, vectype_out, optab_default);
5558   else
5559     optab1 = optab_for_tree_code (c1, vectype, optab_default);
5560
5561   if (!optab1)
5562     return false;
5563
5564   vec_mode = TYPE_MODE (vectype);
5565   if ((icode1 = optab_handler (optab1, vec_mode)) == CODE_FOR_nothing)
5566     return false;
5567
5568   /* Check if it's a multi-step conversion that can be done using intermediate
5569      types.  */
5570   if (insn_data[icode1].operand[0].mode != TYPE_MODE (narrow_vectype))
5571     {
5572       enum machine_mode intermediate_mode, prev_mode = vec_mode;
5573
5574       *code1 = c1;
5575       prev_type = vectype;
5576       /* We assume here that there will not be more than MAX_INTERM_CVT_STEPS
5577          intermediate steps in promotion sequence.  We try
5578          MAX_INTERM_CVT_STEPS to get to NARROW_VECTYPE, and fail if we do
5579          not.  */
5580       *interm_types = VEC_alloc (tree, heap, MAX_INTERM_CVT_STEPS);
5581       for (i = 0; i < 3; i++)
5582         {
5583           intermediate_mode = insn_data[icode1].operand[0].mode;
5584           intermediate_type = lang_hooks.types.type_for_mode (intermediate_mode,
5585                                                      TYPE_UNSIGNED (prev_type));
5586           interm_optab = optab_for_tree_code (c1, intermediate_type,
5587                                               optab_default);
5588           if (!interm_optab
5589               || ((icode1 = optab_handler (optab1, prev_mode))
5590                   == CODE_FOR_nothing)
5591               || insn_data[icode1].operand[0].mode != intermediate_mode
5592               || ((icode1 = optab_handler (interm_optab, intermediate_mode))
5593                   == CODE_FOR_nothing))
5594             return false;
5595
5596           VEC_quick_push (tree, *interm_types, intermediate_type);
5597           (*multi_step_cvt)++;
5598
5599           if (insn_data[icode1].operand[0].mode == TYPE_MODE (narrow_vectype))
5600             return true;
5601
5602           prev_type = intermediate_type;
5603           prev_mode = intermediate_mode;
5604         }
5605
5606       return false;
5607     }
5608
5609   *code1 = c1;
5610   return true;
5611 }