gcc/tree-vectorizer.h

   1 /* Loop Vectorization
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
   3    Contributed by Dorit Naishlos <dorit@il.ibm.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_TREE_VECTORIZER_H
  22 #define GCC_TREE_VECTORIZER_H
  23
  24 typedef source_location LOC;
  25 #define UNKNOWN_LOC UNKNOWN_LOCATION
  26 #define EXPR_LOC(e) EXPR_LOCATION(e)
  27 #define LOC_FILE(l) LOCATION_FILE (l)
  28 #define LOC_LINE(l) LOCATION_LINE (l)
  29
  30 /* Used for naming of new temporaries.  */
  31 enum vect_var_kind {
  32   vect_simple_var,
  33   vect_pointer_var,
  34   vect_scalar_var
  35 };
  36
  37 /* Defines type of operation.  */
  38 enum operation_type {
  39   unary_op = 1,
  40   binary_op,
  41   ternary_op
  42 };
  43
  44 /* Define type of available alignment support.  */
  45 enum dr_alignment_support {
  46   dr_unaligned_unsupported,
  47   dr_unaligned_supported,
  48   dr_explicit_realign,
  49   dr_explicit_realign_optimized,
  50   dr_aligned
  51 };
  52
  53 /* Define type of def-use cross-iteration cycle.  */
  54 enum vect_def_type {
  55   vect_constant_def = 1,
  56   vect_invariant_def,
  57   vect_loop_def,
  58   vect_induction_def,
  59   vect_reduction_def,
  60   vect_unknown_def_type
  61 };
  62
  63 /* Define verbosity levels.  */
  64 enum verbosity_levels {
  65   REPORT_NONE,
  66   REPORT_VECTORIZED_LOOPS,
  67   REPORT_UNVECTORIZED_LOOPS,
  68   REPORT_COST,
  69   REPORT_ALIGNMENT,
  70   REPORT_DR_DETAILS,
  71   REPORT_BAD_FORM_LOOPS,
  72   REPORT_OUTER_LOOPS,
  73   REPORT_SLP,
  74   REPORT_DETAILS,
  75   /* New verbosity levels should be added before this one.  */
  76   MAX_VERBOSITY_LEVEL
  77 };
  78
  79 /************************************************************************
  80   SLP
  81  ************************************************************************/
  82
  83 /* A computation tree of an SLP instance. Each node corresponds to a group of
  84    stmts to be packed in a SIMD stmt.  */
  85 typedef struct _slp_tree {
  86   /* Only binary and unary operations are supported. LEFT child corresponds to
  87      the first operand and RIGHT child to the second if the operation is
  88      binary.  */
  89   struct _slp_tree *left;
  90   struct _slp_tree *right;
  91   /* A group of scalar stmts to be vectorized together.  */
  92   VEC (gimple, heap) *stmts;
  93   /* Vectorized stmt/s.  */
  94   VEC (gimple, heap) *vec_stmts;
  95   /* Number of vector stmts that are created to replace the group of scalar
  96      stmts. It is calculated during the transformation phase as the number of
  97      scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF
  98      divided by vector size.  */
  99   unsigned int vec_stmts_size;
 100   /* Vectorization costs associated with SLP node.  */
 101   struct
 102   {
 103     int outside_of_loop;     /* Statements generated outside loop.  */
 104     int inside_of_loop;      /* Statements generated inside loop.  */
 105   } cost;
 106 } *slp_tree;
 107
 108 DEF_VEC_P(slp_tree);
 109 DEF_VEC_ALLOC_P(slp_tree, heap);
 110
 111 /* SLP instance is a sequence of stmts in a loop that can be packed into
 112    SIMD stmts.  */
 113 typedef struct _slp_instance {
 114   /* The root of SLP tree.  */
 115   slp_tree root;
 116
 117   /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s.  */
 118   unsigned int group_size;
 119
 120   /* The unrolling factor required to vectorized this SLP instance.  */
 121   unsigned int unrolling_factor;
 122
 123   /* Vectorization costs associated with SLP instance.  */
 124   struct
 125   {
 126     int outside_of_loop;     /* Statements generated outside loop.  */
 127     int inside_of_loop;      /* Statements generated inside loop.  */
 128   } cost;
 129
 130   /* Loads permutation relatively to the stores, NULL if there is no
 131      permutation.  */
 132   VEC (int, heap) *load_permutation;
 133
 134   /* The group of nodes that contain loads of this SLP instance.  */
 135   VEC (slp_tree, heap) *loads;
 136
 137   /* The first scalar load of the instance. The created vector loads will be
 138      inserted before this statement.  */
 139   gimple first_load;
 140 } *slp_instance;
 141
 142 DEF_VEC_P(slp_instance);
 143 DEF_VEC_ALLOC_P(slp_instance, heap);
 144
 145 /* Access Functions.  */
 146 #define SLP_INSTANCE_TREE(S)                     (S)->root
 147 #define SLP_INSTANCE_GROUP_SIZE(S)               (S)->group_size
 148 #define SLP_INSTANCE_UNROLLING_FACTOR(S)         (S)->unrolling_factor
 149 #define SLP_INSTANCE_OUTSIDE_OF_LOOP_COST(S)     (S)->cost.outside_of_loop
 150 #define SLP_INSTANCE_INSIDE_OF_LOOP_COST(S)      (S)->cost.inside_of_loop
 151 #define SLP_INSTANCE_LOAD_PERMUTATION(S)         (S)->load_permutation
 152 #define SLP_INSTANCE_LOADS(S)                    (S)->loads
 153 #define SLP_INSTANCE_FIRST_LOAD_STMT(S)          (S)->first_load
 154
 155 #define SLP_TREE_LEFT(S)                         (S)->left
 156 #define SLP_TREE_RIGHT(S)                        (S)->right
 157 #define SLP_TREE_SCALAR_STMTS(S)                 (S)->stmts
 158 #define SLP_TREE_VEC_STMTS(S)                    (S)->vec_stmts
 159 #define SLP_TREE_NUMBER_OF_VEC_STMTS(S)          (S)->vec_stmts_size
 160 #define SLP_TREE_OUTSIDE_OF_LOOP_COST(S)         (S)->cost.outside_of_loop
 161 #define SLP_TREE_INSIDE_OF_LOOP_COST(S)          (S)->cost.inside_of_loop
 162
 163 /*-----------------------------------------------------------------*/
 164 /* Info on vectorized loops.                                       */
 165 /*-----------------------------------------------------------------*/
 166 typedef struct _loop_vec_info {
 167
 168   /* The loop to which this info struct refers to.  */
 169   struct loop *loop;
 170
 171   /* The loop basic blocks.  */
 172   basic_block *bbs;
 173
 174   /* Number of iterations.  */
 175   tree num_iters;
 176   tree num_iters_unchanged;
 177
 178   /* Minimum number of iterations below which vectorization is expected to
 179      not be profitable (as estimated by the cost model).
 180      -1 indicates that vectorization will not be profitable.
 181      FORNOW: This field is an int. Will be a tree in the future, to represent
 182              values unknown at compile time.  */
 183   int min_profitable_iters;
 184
 185   /* Is the loop vectorizable? */
 186   bool vectorizable;
 187
 188   /* Unrolling factor  */
 189   int vectorization_factor;
 190
 191   /* Unknown DRs according to which loop was peeled.  */
 192   struct data_reference *unaligned_dr;
 193
 194   /* peeling_for_alignment indicates whether peeling for alignment will take
 195      place, and what the peeling factor should be:
 196      peeling_for_alignment = X means:
 197         If X=0: Peeling for alignment will not be applied.
 198         If X>0: Peel first X iterations.
 199         If X=-1: Generate a runtime test to calculate the number of iterations
 200                  to be peeled, using the dataref recorded in the field
 201                  unaligned_dr.  */
 202   int peeling_for_alignment;
 203
 204   /* The mask used to check the alignment of pointers or arrays.  */
 205   int ptr_mask;
 206
 207   /* All data references in the loop.  */
 208   VEC (data_reference_p, heap) *datarefs;
 209
 210   /* All data dependences in the loop.  */
 211   VEC (ddr_p, heap) *ddrs;
 212
 213   /* Data Dependence Relations defining address ranges that are candidates
 214      for a run-time aliasing check.  */
 215   VEC (ddr_p, heap) *may_alias_ddrs;
 216
 217   /* Statements in the loop that have data references that are candidates for a
 218      runtime (loop versioning) misalignment check.  */
 219   VEC(gimple,heap) *may_misalign_stmts;
 220
 221   /* The loop location in the source.  */
 222   LOC loop_line_number;
 223
 224   /* All interleaving chains of stores in the loop, represented by the first
 225      stmt in the chain.  */
 226   VEC(gimple, heap) *strided_stores;
 227
 228   /* All SLP instances in the loop. This is a subset of the set of STRIDED_STORES
 229      of the loop.  */
 230   VEC(slp_instance, heap) *slp_instances;
 231
 232   /* The unrolling factor needed to SLP the loop. In case of that pure SLP is
 233      applied to the loop, i.e., no unrolling is needed, this is 1.  */
 234   unsigned slp_unrolling_factor;
 235 } *loop_vec_info;
 236
 237 /* Access Functions.  */
 238 #define LOOP_VINFO_LOOP(L)            (L)->loop
 239 #define LOOP_VINFO_BBS(L)             (L)->bbs
 240 #define LOOP_VINFO_NITERS(L)          (L)->num_iters
 241 /* Since LOOP_VINFO_NITERS can change after prologue peeling
 242    retain total unchanged scalar loop iterations for cost model.  */
 243 #define LOOP_VINFO_NITERS_UNCHANGED(L)          (L)->num_iters_unchanged
 244 #define LOOP_VINFO_COST_MODEL_MIN_ITERS(L)      (L)->min_profitable_iters
 245 #define LOOP_VINFO_VECTORIZABLE_P(L)  (L)->vectorizable
 246 #define LOOP_VINFO_VECT_FACTOR(L)     (L)->vectorization_factor
 247 #define LOOP_VINFO_PTR_MASK(L)        (L)->ptr_mask
 248 #define LOOP_VINFO_DATAREFS(L)        (L)->datarefs
 249 #define LOOP_VINFO_DDRS(L)            (L)->ddrs
 250 #define LOOP_VINFO_INT_NITERS(L)      (TREE_INT_CST_LOW ((L)->num_iters))
 251 #define LOOP_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment
 252 #define LOOP_VINFO_UNALIGNED_DR(L)    (L)->unaligned_dr
 253 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts
 254 #define LOOP_VINFO_LOC(L)             (L)->loop_line_number
 255 #define LOOP_VINFO_MAY_ALIAS_DDRS(L)  (L)->may_alias_ddrs
 256 #define LOOP_VINFO_STRIDED_STORES(L)  (L)->strided_stores
 257 #define LOOP_VINFO_SLP_INSTANCES(L)   (L)->slp_instances
 258 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor
 259
 260 #define NITERS_KNOWN_P(n)                     \
 261 (host_integerp ((n),0)                        \
 262 && TREE_INT_CST_LOW ((n)) > 0)
 263
 264 #define LOOP_VINFO_NITERS_KNOWN_P(L)                     \
 265 NITERS_KNOWN_P((L)->num_iters)
 266
 267 static inline loop_vec_info
 268 loop_vec_info_for_loop (struct loop *loop)
 269 {
 270   return (loop_vec_info) loop->aux;
 271 }
 272
 273 static inline bool
 274 nested_in_vect_loop_p (struct loop *loop, gimple stmt)
 275 {
 276   return (loop->inner
 277           && (loop->inner == (gimple_bb (stmt))->loop_father));
 278 }
 279
 280 /*-----------------------------------------------------------------*/
 281 /* Info on vectorized defs.                                        */
 282 /*-----------------------------------------------------------------*/
 283 enum stmt_vec_info_type {
 284   undef_vec_info_type = 0,
 285   load_vec_info_type,
 286   store_vec_info_type,
 287   op_vec_info_type,
 288   call_vec_info_type,
 289   assignment_vec_info_type,
 290   condition_vec_info_type,
 291   reduc_vec_info_type,
 292   induc_vec_info_type,
 293   type_promotion_vec_info_type,
 294   type_demotion_vec_info_type,
 295   type_conversion_vec_info_type,
 296   loop_exit_ctrl_vec_info_type
 297 };
 298
 299 /* Indicates whether/how a variable is used in the loop.  */
 300 enum vect_relevant {
 301   vect_unused_in_loop = 0,
 302   vect_used_in_outer_by_reduction,
 303   vect_used_in_outer,
 304
 305   /* defs that feed computations that end up (only) in a reduction. These
 306      defs may be used by non-reduction stmts, but eventually, any
 307      computations/values that are affected by these defs are used to compute
 308      a reduction (i.e. don't get stored to memory, for example). We use this
 309      to identify computations that we can change the order in which they are
 310      computed.  */
 311   vect_used_by_reduction,
 312
 313   vect_used_in_loop
 314 };
 315
 316 /* The type of vectorization that can be applied to the stmt: regular loop-based
 317    vectorization; pure SLP - the stmt is a part of SLP instances and does not
 318    have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is
 319    a part of SLP instance and also must be loop-based vectorized, since it has
 320    uses outside SLP sequences.
 321
 322    In the loop context the meanings of pure and hybrid SLP are slightly
 323    different. By saying that pure SLP is applied to the loop, we mean that we
 324    exploit only intra-iteration parallelism in the loop; i.e., the loop can be
 325    vectorized without doing any conceptual unrolling, cause we don't pack
 326    together stmts from different iterations, only within a single iteration.
 327    Loop hybrid SLP means that we exploit both intra-iteration and
 328    inter-iteration parallelism (e.g., number of elements in the vector is 4
 329    and the slp-group-size is 2, in which case we don't have enough parallelism
 330    within an iteration, so we obtain the rest of the parallelism from subsequent
 331    iterations by unrolling the loop by 2).  */
 332 enum slp_vect_type {
 333   loop_vect = 0,
 334   pure_slp,
 335   hybrid
 336 };
 337
 338
 339 typedef struct data_reference *dr_p;
 340 DEF_VEC_P(dr_p);
 341 DEF_VEC_ALLOC_P(dr_p,heap);
 342
 343 typedef struct _stmt_vec_info {
 344
 345   enum stmt_vec_info_type type;
 346
 347   /* The stmt to which this info struct refers to.  */
 348   gimple stmt;
 349
 350   /* The loop_vec_info with respect to which STMT is vectorized.  */
 351   loop_vec_info loop_vinfo;
 352
 353   /* Not all stmts in the loop need to be vectorized. e.g, the increment
 354      of the loop induction variable and computation of array indexes. relevant
 355      indicates whether the stmt needs to be vectorized.  */
 356   enum vect_relevant relevant;
 357
 358   /* Indicates whether this stmts is part of a computation whose result is
 359      used outside the loop.  */
 360   bool live;
 361
 362   /* The vector type to be used.  */
 363   tree vectype;
 364
 365   /* The vectorized version of the stmt.  */
 366   gimple vectorized_stmt;
 367
 368
 369   /** The following is relevant only for stmts that contain a non-scalar
 370      data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have
 371      at most one such data-ref.  **/
 372
 373   /* Information about the data-ref (access function, etc),
 374      relative to the inner-most containing loop.  */
 375   struct data_reference *data_ref_info;
 376
 377   /* Information about the data-ref relative to this loop
 378      nest (the loop that is being considered for vectorization).  */
 379   tree dr_base_address;
 380   tree dr_init;
 381   tree dr_offset;
 382   tree dr_step;
 383   tree dr_aligned_to;
 384
 385   /* Stmt is part of some pattern (computation idiom)  */
 386   bool in_pattern_p;
 387
 388   /* Used for various bookkeeping purposes, generally holding a pointer to
 389      some other stmt S that is in some way "related" to this stmt.
 390      Current use of this field is:
 391         If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is
 392         true): S is the "pattern stmt" that represents (and replaces) the
 393         sequence of stmts that constitutes the pattern.  Similarly, the
 394         related_stmt of the "pattern stmt" points back to this stmt (which is
 395         the last stmt in the original sequence of stmts that constitutes the
 396         pattern).  */
 397   gimple related_stmt;
 398
 399   /* List of datarefs that are known to have the same alignment as the dataref
 400      of this stmt.  */
 401   VEC(dr_p,heap) *same_align_refs;
 402
 403   /* Classify the def of this stmt.  */
 404   enum vect_def_type def_type;
 405
 406   /* Interleaving info.  */
 407   /* First data-ref in the interleaving group.  */
 408   gimple first_dr;
 409   /* Pointer to the next data-ref in the group.  */
 410   gimple next_dr;
 411   /* The size of the interleaving group.  */
 412   unsigned int size;
 413   /* For stores, number of stores from this group seen. We vectorize the last
 414      one.  */
 415   unsigned int store_count;
 416   /* For loads only, the gap from the previous load. For consecutive loads, GAP
 417      is 1.  */
 418   unsigned int gap;
 419   /* In case that two or more stmts share data-ref, this is the pointer to the
 420      previously detected stmt with the same dr.  */
 421   gimple same_dr_stmt;
 422   /* For loads only, if there is a store with the same location, this field is
 423      TRUE.  */
 424   bool read_write_dep;
 425
 426   /* Vectorization costs associated with statement.  */
 427   struct
 428   {
 429     int outside_of_loop;     /* Statements generated outside loop.  */
 430     int inside_of_loop;      /* Statements generated inside loop.  */
 431   } cost;
 432
 433   /*  Whether the stmt is SLPed, loop-based vectorized, or both.  */
 434   enum slp_vect_type slp_type;
 435 } *stmt_vec_info;
 436
 437 /* Access Functions.  */
 438 #define STMT_VINFO_TYPE(S)                 (S)->type
 439 #define STMT_VINFO_STMT(S)                 (S)->stmt
 440 #define STMT_VINFO_LOOP_VINFO(S)           (S)->loop_vinfo
 441 #define STMT_VINFO_RELEVANT(S)             (S)->relevant
 442 #define STMT_VINFO_LIVE_P(S)               (S)->live
 443 #define STMT_VINFO_VECTYPE(S)              (S)->vectype
 444 #define STMT_VINFO_VEC_STMT(S)             (S)->vectorized_stmt
 445 #define STMT_VINFO_DATA_REF(S)             (S)->data_ref_info
 446
 447 #define STMT_VINFO_DR_BASE_ADDRESS(S)      (S)->dr_base_address
 448 #define STMT_VINFO_DR_INIT(S)              (S)->dr_init
 449 #define STMT_VINFO_DR_OFFSET(S)            (S)->dr_offset
 450 #define STMT_VINFO_DR_STEP(S)              (S)->dr_step
 451 #define STMT_VINFO_DR_ALIGNED_TO(S)        (S)->dr_aligned_to
 452
 453 #define STMT_VINFO_IN_PATTERN_P(S)         (S)->in_pattern_p
 454 #define STMT_VINFO_RELATED_STMT(S)         (S)->related_stmt
 455 #define STMT_VINFO_SAME_ALIGN_REFS(S)      (S)->same_align_refs
 456 #define STMT_VINFO_DEF_TYPE(S)             (S)->def_type
 457 #define STMT_VINFO_DR_GROUP_FIRST_DR(S)    (S)->first_dr
 458 #define STMT_VINFO_DR_GROUP_NEXT_DR(S)     (S)->next_dr
 459 #define STMT_VINFO_DR_GROUP_SIZE(S)        (S)->size
 460 #define STMT_VINFO_DR_GROUP_STORE_COUNT(S) (S)->store_count
 461 #define STMT_VINFO_DR_GROUP_GAP(S)         (S)->gap
 462 #define STMT_VINFO_DR_GROUP_SAME_DR_STMT(S)(S)->same_dr_stmt
 463 #define STMT_VINFO_DR_GROUP_READ_WRITE_DEPENDENCE(S)  (S)->read_write_dep
 464 #define STMT_VINFO_STRIDED_ACCESS(S)      ((S)->first_dr != NULL)
 465
 466 #define DR_GROUP_FIRST_DR(S)               (S)->first_dr
 467 #define DR_GROUP_NEXT_DR(S)                (S)->next_dr
 468 #define DR_GROUP_SIZE(S)                   (S)->size
 469 #define DR_GROUP_STORE_COUNT(S)            (S)->store_count
 470 #define DR_GROUP_GAP(S)                    (S)->gap
 471 #define DR_GROUP_SAME_DR_STMT(S)           (S)->same_dr_stmt
 472 #define DR_GROUP_READ_WRITE_DEPENDENCE(S)  (S)->read_write_dep
 473
 474 #define STMT_VINFO_RELEVANT_P(S)          ((S)->relevant != vect_unused_in_loop)
 475 #define STMT_VINFO_OUTSIDE_OF_LOOP_COST(S) (S)->cost.outside_of_loop
 476 #define STMT_VINFO_INSIDE_OF_LOOP_COST(S)  (S)->cost.inside_of_loop
 477
 478 #define HYBRID_SLP_STMT(S)                ((S)->slp_type == hybrid)
 479 #define PURE_SLP_STMT(S)                  ((S)->slp_type == pure_slp)
 480 #define STMT_SLP_TYPE(S)                   (S)->slp_type
 481
 482 /* These are some defines for the initial implementation of the vectorizer's
 483    cost model.  These will later be target specific hooks.  */
 484
 485 /* Cost of conditional taken branch.  */
 486 #ifndef TARG_COND_TAKEN_BRANCH_COST
 487 #define TARG_COND_TAKEN_BRANCH_COST        3
 488 #endif
 489
 490 /* Cost of conditional not taken branch.  */
 491 #ifndef TARG_COND_NOT_TAKEN_BRANCH_COST
 492 #define TARG_COND_NOT_TAKEN_BRANCH_COST        1
 493 #endif
 494
 495 /* Cost of any scalar operation, excluding load and store.  */
 496 #ifndef TARG_SCALAR_STMT_COST
 497 #define TARG_SCALAR_STMT_COST           1
 498 #endif
 499
 500 /* Cost of scalar load.  */
 501 #ifndef TARG_SCALAR_LOAD_COST
 502 #define TARG_SCALAR_LOAD_COST           1
 503 #endif
 504
 505 /* Cost of scalar store.  */
 506 #ifndef TARG_SCALAR_STORE_COST
 507 #define TARG_SCALAR_STORE_COST           1
 508 #endif
 509
 510 /* Cost of any vector operation, excluding load, store or vector to scalar
 511    operation.  */
 512 #ifndef TARG_VEC_STMT_COST
 513 #define TARG_VEC_STMT_COST           1
 514 #endif
 515
 516 /* Cost of vector to scalar operation.  */
 517 #ifndef TARG_VEC_TO_SCALAR_COST
 518 #define TARG_VEC_TO_SCALAR_COST      1
 519 #endif
 520
 521 /* Cost of scalar to vector operation.  */
 522 #ifndef TARG_SCALAR_TO_VEC_COST
 523 #define TARG_SCALAR_TO_VEC_COST      1
 524 #endif
 525
 526 /* Cost of aligned vector load.  */
 527 #ifndef TARG_VEC_LOAD_COST
 528 #define TARG_VEC_LOAD_COST           1
 529 #endif
 530
 531 /* Cost of misaligned vector load.  */
 532 #ifndef TARG_VEC_UNALIGNED_LOAD_COST
 533 #define TARG_VEC_UNALIGNED_LOAD_COST 2
 534 #endif
 535
 536 /* Cost of vector store.  */
 537 #ifndef TARG_VEC_STORE_COST
 538 #define TARG_VEC_STORE_COST          1
 539 #endif
 540
 541 /* Cost of vector permutation.  */
 542 #ifndef TARG_VEC_PERMUTE_COST
 543 #define TARG_VEC_PERMUTE_COST          1
 544 #endif
 545
 546 /* The maximum number of intermediate steps required in multi-step type
 547    conversion.  */
 548 #define MAX_INTERM_CVT_STEPS         3
 549
 550 /* Avoid GTY(()) on stmt_vec_info.  */
 551 typedef void *vec_void_p;
 552 DEF_VEC_P (vec_void_p);
 553 DEF_VEC_ALLOC_P (vec_void_p, heap);
 554
 555 extern VEC(vec_void_p,heap) *stmt_vec_info_vec;
 556
 557 void init_stmt_vec_info_vec (void);
 558 void free_stmt_vec_info_vec (void);
 559
 560 static inline stmt_vec_info
 561 vinfo_for_stmt (gimple stmt)
 562 {
 563   unsigned int uid = gimple_uid (stmt);
 564   if (uid == 0)
 565     return NULL;
 566
 567   gcc_assert (uid <= VEC_length (vec_void_p, stmt_vec_info_vec));
 568   return (stmt_vec_info) VEC_index (vec_void_p, stmt_vec_info_vec, uid - 1);
 569 }
 570
 571 static inline void
 572 set_vinfo_for_stmt (gimple stmt, stmt_vec_info info)
 573 {
 574   unsigned int uid = gimple_uid (stmt);
 575   if (uid == 0)
 576     {
 577       gcc_assert (info);
 578       uid = VEC_length (vec_void_p, stmt_vec_info_vec) + 1;
 579       gimple_set_uid (stmt, uid);
 580       VEC_safe_push (vec_void_p, heap, stmt_vec_info_vec, (vec_void_p) info);
 581     }
 582   else
 583     VEC_replace (vec_void_p, stmt_vec_info_vec, uid - 1, (vec_void_p) info);
 584 }
 585
 586 static inline gimple
 587 get_earlier_stmt (gimple stmt1, gimple stmt2)
 588 {
 589   unsigned int uid1, uid2;
 590
 591   if (stmt1 == NULL)
 592     return stmt2;
 593
 594   if (stmt2 == NULL)
 595     return stmt1;
 596
 597   uid1 = gimple_uid (stmt1);
 598   uid2 = gimple_uid (stmt2);
 599
 600   if (uid1 == 0 || uid2 == 0)
 601     return NULL;
 602
 603   gcc_assert (uid1 <= VEC_length (vec_void_p, stmt_vec_info_vec));
 604   gcc_assert (uid2 <= VEC_length (vec_void_p, stmt_vec_info_vec));
 605
 606   if (uid1 < uid2)
 607     return stmt1;
 608   else
 609     return stmt2;
 610 }
 611
 612 static inline bool
 613 is_pattern_stmt_p (stmt_vec_info stmt_info)
 614 {
 615   gimple related_stmt;
 616   stmt_vec_info related_stmt_info;
 617
 618   related_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
 619   if (related_stmt
 620       && (related_stmt_info = vinfo_for_stmt (related_stmt))
 621       && STMT_VINFO_IN_PATTERN_P (related_stmt_info))
 622     return true;
 623
 624   return false;
 625 }
 626
 627 static inline bool
 628 is_loop_header_bb_p (basic_block bb)
 629 {
 630   if (bb == (bb->loop_father)->header)
 631     return true;
 632   gcc_assert (EDGE_COUNT (bb->preds) == 1);
 633   return false;
 634 }
 635
 636 static inline void
 637 stmt_vinfo_set_inside_of_loop_cost (stmt_vec_info stmt_info, slp_tree slp_node,
 638                                     int cost)
 639 {
 640   if (slp_node)
 641     SLP_TREE_INSIDE_OF_LOOP_COST (slp_node) = cost;
 642   else
 643     STMT_VINFO_INSIDE_OF_LOOP_COST (stmt_info) = cost;
 644 }
 645
 646 static inline void
 647 stmt_vinfo_set_outside_of_loop_cost (stmt_vec_info stmt_info, slp_tree slp_node,
 648                                      int cost)
 649 {
 650   if (slp_node)
 651     SLP_TREE_OUTSIDE_OF_LOOP_COST (slp_node) = cost;
 652   else
 653     STMT_VINFO_OUTSIDE_OF_LOOP_COST (stmt_info) = cost;
 654 }
 655
 656 static inline int
 657 vect_pow2 (int x)
 658 {
 659   int i, res = 1;
 660
 661   for (i = 0; i < x; i++)
 662     res *= 2;
 663
 664   return res;
 665 }
 666
 667 /*-----------------------------------------------------------------*/
 668 /* Info on data references alignment.                              */
 669 /*-----------------------------------------------------------------*/
 670
 671 /* Reflects actual alignment of first access in the vectorized loop,
 672    taking into account peeling/versioning if applied.  */
 673 #define DR_MISALIGNMENT(DR)   ((int) (size_t) (DR)->aux)
 674 #define SET_DR_MISALIGNMENT(DR, VAL)   ((DR)->aux = (void *) (size_t) (VAL))
 675
 676 static inline bool
 677 aligned_access_p (struct data_reference *data_ref_info)
 678 {
 679   return (DR_MISALIGNMENT (data_ref_info) == 0);
 680 }
 681
 682 static inline bool
 683 known_alignment_for_access_p (struct data_reference *data_ref_info)
 684 {
 685   return (DR_MISALIGNMENT (data_ref_info) != -1);
 686 }
 687
 688 /* vect_dump will be set to stderr or dump_file if exist.  */
 689 extern FILE *vect_dump;
 690 extern enum verbosity_levels vect_verbosity_level;
 691
 692 /* Bitmap of virtual variables to be renamed.  */
 693 extern bitmap vect_memsyms_to_rename;
 694
 695 /*-----------------------------------------------------------------*/
 696 /* Function prototypes.                                            */
 697 /*-----------------------------------------------------------------*/
 698
 699 /*************************************************************************
 700   Simple Loop Peeling Utilities - in tree-vectorizer.c
 701  *************************************************************************/
 702 /* Entry point for peeling of simple loops.
 703    Peel the first/last iterations of a loop.
 704    It can be used outside of the vectorizer for loops that are simple enough
 705    (see function documentation).  In the vectorizer it is used to peel the
 706    last few iterations when the loop bound is unknown or does not evenly
 707    divide by the vectorization factor, and to peel the first few iterations
 708    to force the alignment of data references in the loop.  */
 709 extern struct loop *slpeel_tree_peel_loop_to_edge
 710   (struct loop *, edge, tree, tree, bool, unsigned int, bool);
 711 extern void set_prologue_iterations (basic_block, tree,
 712                                      struct loop *, unsigned int);
 713 struct loop *tree_duplicate_loop_on_edge (struct loop *, edge);
 714 extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree);
 715 extern bool slpeel_can_duplicate_loop_p (const struct loop *, const_edge);
 716 #ifdef ENABLE_CHECKING
 717 extern void slpeel_verify_cfg_after_peeling (struct loop *, struct loop *);
 718 #endif
 719
 720
 721 /*************************************************************************
 722   General Vectorization Utilities
 723  *************************************************************************/
 724 /** In tree-vectorizer.c **/
 725 extern tree get_vectype_for_scalar_type (tree);
 726 extern bool vect_is_simple_use (tree, loop_vec_info, gimple *, tree *,
 727                                 enum vect_def_type *);
 728 extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *);
 729 extern gimple vect_is_simple_reduction (loop_vec_info, gimple);
 730 extern bool vect_can_force_dr_alignment_p (const_tree, unsigned int);
 731 extern enum dr_alignment_support vect_supportable_dr_alignment
 732   (struct data_reference *);
 733 extern bool reduction_code_for_scalar_code (enum tree_code, enum tree_code *);
 734 extern bool supportable_widening_operation (enum tree_code, gimple, tree,
 735   tree *, tree *, enum tree_code *, enum tree_code *,
 736   int *, VEC (tree, heap) **);
 737 extern bool supportable_narrowing_operation (enum tree_code, const_gimple,
 738              tree, enum tree_code *, int *, VEC (tree, heap) **);
 739
 740 /* Creation and deletion of loop and stmt info structs.  */
 741 extern loop_vec_info new_loop_vec_info (struct loop *loop);
 742 extern void destroy_loop_vec_info (loop_vec_info, bool);
 743 extern stmt_vec_info new_stmt_vec_info (gimple stmt, loop_vec_info);
 744 extern void free_stmt_vec_info (gimple stmt);
 745
 746
 747 /** In tree-vect-analyze.c  **/
 748 /* Driver for analysis stage.  */
 749 extern loop_vec_info vect_analyze_loop (struct loop *);
 750 extern void vect_free_slp_instance (slp_instance);
 751 extern loop_vec_info vect_analyze_loop_form (struct loop *);
 752 extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *,
 753                                            HOST_WIDE_INT *);
 754
 755 /** In tree-vect-patterns.c  **/
 756 /* Pattern recognition functions.
 757    Additional pattern recognition functions can (and will) be added
 758    in the future.  */
 759 typedef gimple (* vect_recog_func_ptr) (gimple, tree *, tree *);
 760 #define NUM_PATTERNS 4
 761 void vect_pattern_recog (loop_vec_info);
 762
 763
 764 /** In tree-vect-transform.c  **/
 765 extern bool vectorizable_load (gimple, gimple_stmt_iterator *, gimple *,
 766                                slp_tree, slp_instance);
 767 extern bool vectorizable_store (gimple, gimple_stmt_iterator *, gimple *,
 768                                 slp_tree);
 769 extern bool vectorizable_operation (gimple, gimple_stmt_iterator *, gimple *,
 770                                     slp_tree);
 771 extern bool vectorizable_type_promotion (gimple, gimple_stmt_iterator *,
 772                                          gimple *, slp_tree);
 773 extern bool vectorizable_type_demotion (gimple, gimple_stmt_iterator *,
 774                                         gimple *, slp_tree);
 775 extern bool vectorizable_conversion (gimple, gimple_stmt_iterator *, gimple *,
 776                                      slp_tree);
 777 extern bool vectorizable_assignment (gimple, gimple_stmt_iterator *, gimple *,
 778                                      slp_tree);
 779 extern tree vectorizable_function (gimple, tree, tree);
 780 extern bool vectorizable_call (gimple, gimple_stmt_iterator *, gimple *);
 781 extern bool vectorizable_condition (gimple, gimple_stmt_iterator *, gimple *);
 782 extern bool vectorizable_live_operation (gimple, gimple_stmt_iterator *,
 783                                          gimple *);
 784 extern bool vectorizable_reduction (gimple, gimple_stmt_iterator *, gimple *);
 785 extern bool vectorizable_induction (gimple, gimple_stmt_iterator *, gimple *);
 786 extern int  vect_estimate_min_profitable_iters (loop_vec_info);
 787 extern void vect_model_simple_cost (stmt_vec_info, int, enum vect_def_type *,
 788                                     slp_tree);
 789 extern void vect_model_store_cost (stmt_vec_info, int, enum vect_def_type,
 790                                    slp_tree);
 791 extern void vect_model_load_cost (stmt_vec_info, int, slp_tree);
 792 extern bool vect_transform_slp_perm_load (gimple, VEC (tree, heap) *,
 793                              gimple_stmt_iterator *, int, slp_instance, bool);
 794
 795 /* Driver for transformation stage.  */
 796 extern void vect_transform_loop (loop_vec_info);
 797
 798 /*************************************************************************
 799   Vectorization Debug Information - in tree-vectorizer.c
 800  *************************************************************************/
 801 extern bool vect_print_dump_info (enum verbosity_levels);
 802 extern void vect_set_verbosity_level (const char *);
 803 extern LOC find_loop_location (struct loop *);
 804
 805 #endif  /* GCC_TREE_VECTORIZER_H  */