1 /* Vectorizer 2 Copyright (C) 2003-2013 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 #include "tree-data-ref.h" 25 #include "target.h" 26 27 typedef source_location LOC; 28 #define UNKNOWN_LOC UNKNOWN_LOCATION 29 #define EXPR_LOC(e) EXPR_LOCATION(e) 30 #define LOC_FILE(l) LOCATION_FILE (l) 31 #define LOC_LINE(l) LOCATION_LINE (l) 32 33 /* Used for naming of new temporaries. */ 34 enum vect_var_kind { 35 vect_simple_var, 36 vect_pointer_var, 37 vect_scalar_var 38 }; 39 40 /* Defines type of operation. */ 41 enum operation_type { 42 unary_op = 1, 43 binary_op, 44 ternary_op 45 }; 46 47 /* Define type of available alignment support. */ 48 enum dr_alignment_support { 49 dr_unaligned_unsupported, 50 dr_unaligned_supported, 51 dr_explicit_realign, 52 dr_explicit_realign_optimized, 53 dr_aligned 54 }; 55 56 /* Define type of def-use cross-iteration cycle. */ 57 enum vect_def_type { 58 vect_uninitialized_def = 0, 59 vect_constant_def = 1, 60 vect_external_def, 61 vect_internal_def, 62 vect_induction_def, 63 vect_reduction_def, 64 vect_double_reduction_def, 65 vect_nested_cycle, 66 vect_unknown_def_type 67 }; 68 69 #define VECTORIZABLE_CYCLE_DEF(D) (((D) == vect_reduction_def) \ 70 || ((D) == vect_double_reduction_def) \ 71 || ((D) == vect_nested_cycle)) 72 73 /* Structure to encapsulate information about a group of like 74 instructions to be presented to the target cost model. */ 75 typedef struct _stmt_info_for_cost { 76 int count; 77 enum vect_cost_for_stmt kind; 78 gimple stmt; 79 int misalign; 80 } stmt_info_for_cost; 81 82 83 typedef vec<stmt_info_for_cost> stmt_vector_for_cost; 84 85 static inline void 86 add_stmt_info_to_vec (stmt_vector_for_cost *stmt_cost_vec, int count, 87 enum vect_cost_for_stmt kind, gimple stmt, int misalign) 88 { 89 stmt_info_for_cost si; 90 si.count = count; 91 si.kind = kind; 92 si.stmt = stmt; 93 si.misalign = misalign; 94 stmt_cost_vec->safe_push (si); 95 } 96 97 /************************************************************************ 98 SLP 99 ************************************************************************/ 100 typedef void *slp_void_p; 101 102 /* A computation tree of an SLP instance. Each node corresponds to a group of 103 stmts to be packed in a SIMD stmt. */ 104 typedef struct _slp_tree { 105 /* Nodes that contain def-stmts of this node statements operands. */ 106 vec<slp_void_p> children; 107 /* A group of scalar stmts to be vectorized together. */ 108 vec<gimple> stmts; 109 /* Vectorized stmt/s. */ 110 vec<gimple> vec_stmts; 111 /* Number of vector stmts that are created to replace the group of scalar 112 stmts. It is calculated during the transformation phase as the number of 113 scalar elements in one scalar iteration (GROUP_SIZE) multiplied by VF 114 divided by vector size. */ 115 unsigned int vec_stmts_size; 116 } *slp_tree; 117 118 119 /* SLP instance is a sequence of stmts in a loop that can be packed into 120 SIMD stmts. */ 121 typedef struct _slp_instance { 122 /* The root of SLP tree. */ 123 slp_tree root; 124 125 /* Size of groups of scalar stmts that will be replaced by SIMD stmt/s. */ 126 unsigned int group_size; 127 128 /* The unrolling factor required to vectorized this SLP instance. */ 129 unsigned int unrolling_factor; 130 131 /* Vectorization costs associated with SLP instance. */ 132 stmt_vector_for_cost body_cost_vec; 133 134 /* Loads permutation relatively to the stores, NULL if there is no 135 permutation. */ 136 vec<int> load_permutation; 137 138 /* The group of nodes that contain loads of this SLP instance. */ 139 vec<slp_tree> loads; 140 141 /* The first scalar load of the instance. The created vector loads will be 142 inserted before this statement. */ 143 gimple first_load; 144 } *slp_instance; 145 146 147 /* Access Functions. */ 148 #define SLP_INSTANCE_TREE(S) (S)->root 149 #define SLP_INSTANCE_GROUP_SIZE(S) (S)->group_size 150 #define SLP_INSTANCE_UNROLLING_FACTOR(S) (S)->unrolling_factor 151 #define SLP_INSTANCE_BODY_COST_VEC(S) (S)->body_cost_vec 152 #define SLP_INSTANCE_LOAD_PERMUTATION(S) (S)->load_permutation 153 #define SLP_INSTANCE_LOADS(S) (S)->loads 154 #define SLP_INSTANCE_FIRST_LOAD_STMT(S) (S)->first_load 155 156 #define SLP_TREE_CHILDREN(S) (S)->children 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 161 /* This structure is used in creation of an SLP tree. Each instance 162 corresponds to the same operand in a group of scalar stmts in an SLP 163 node. */ 164 typedef struct _slp_oprnd_info 165 { 166 /* Def-stmts for the operands. */ 167 vec<gimple> def_stmts; 168 /* Information about the first statement, its vector def-type, type, the 169 operand itself in case it's constant, and an indication if it's a pattern 170 stmt. */ 171 enum vect_def_type first_dt; 172 tree first_def_type; 173 tree first_const_oprnd; 174 bool first_pattern; 175 } *slp_oprnd_info; 176 177 178 179 typedef struct _vect_peel_info 180 { 181 int npeel; 182 struct data_reference *dr; 183 unsigned int count; 184 } *vect_peel_info; 185 186 typedef struct _vect_peel_extended_info 187 { 188 struct _vect_peel_info peel_info; 189 unsigned int inside_cost; 190 unsigned int outside_cost; 191 stmt_vector_for_cost body_cost_vec; 192 } *vect_peel_extended_info; 193 194 /*-----------------------------------------------------------------*/ 195 /* Info on vectorized loops. */ 196 /*-----------------------------------------------------------------*/ 197 typedef struct _loop_vec_info { 198 199 /* The loop to which this info struct refers to. */ 200 struct loop *loop; 201 202 /* The loop basic blocks. */ 203 basic_block *bbs; 204 205 /* Number of iterations. */ 206 tree num_iters; 207 tree num_iters_unchanged; 208 209 /* Minimum number of iterations below which vectorization is expected to 210 not be profitable (as estimated by the cost model). 211 -1 indicates that vectorization will not be profitable. 212 FORNOW: This field is an int. Will be a tree in the future, to represent 213 values unknown at compile time. */ 214 int min_profitable_iters; 215 216 /* Is the loop vectorizable? */ 217 bool vectorizable; 218 219 /* Unrolling factor */ 220 int vectorization_factor; 221 222 /* The loop location in the source. */ 223 LOC loop_line_number; 224 225 /* Unknown DRs according to which loop was peeled. */ 226 struct data_reference *unaligned_dr; 227 228 /* peeling_for_alignment indicates whether peeling for alignment will take 229 place, and what the peeling factor should be: 230 peeling_for_alignment = X means: 231 If X=0: Peeling for alignment will not be applied. 232 If X>0: Peel first X iterations. 233 If X=-1: Generate a runtime test to calculate the number of iterations 234 to be peeled, using the dataref recorded in the field 235 unaligned_dr. */ 236 int peeling_for_alignment; 237 238 /* The mask used to check the alignment of pointers or arrays. */ 239 int ptr_mask; 240 241 /* The loop nest in which the data dependences are computed. */ 242 vec<loop_p> loop_nest; 243 244 /* All data references in the loop. */ 245 vec<data_reference_p> datarefs; 246 247 /* All data dependences in the loop. */ 248 vec<ddr_p> ddrs; 249 250 /* Data Dependence Relations defining address ranges that are candidates 251 for a run-time aliasing check. */ 252 vec<ddr_p> may_alias_ddrs; 253 254 /* Statements in the loop that have data references that are candidates for a 255 runtime (loop versioning) misalignment check. */ 256 vec<gimple> may_misalign_stmts; 257 258 /* All interleaving chains of stores in the loop, represented by the first 259 stmt in the chain. */ 260 vec<gimple> grouped_stores; 261 262 /* All SLP instances in the loop. This is a subset of the set of GROUP_STORES 263 of the loop. */ 264 vec<slp_instance> slp_instances; 265 266 /* The unrolling factor needed to SLP the loop. In case of that pure SLP is 267 applied to the loop, i.e., no unrolling is needed, this is 1. */ 268 unsigned slp_unrolling_factor; 269 270 /* Reduction cycles detected in the loop. Used in loop-aware SLP. */ 271 vec<gimple> reductions; 272 273 /* All reduction chains in the loop, represented by the first 274 stmt in the chain. */ 275 vec<gimple> reduction_chains; 276 277 /* Hash table used to choose the best peeling option. */ 278 htab_t peeling_htab; 279 280 /* Cost data used by the target cost model. */ 281 void *target_cost_data; 282 283 /* When we have grouped data accesses with gaps, we may introduce invalid 284 memory accesses. We peel the last iteration of the loop to prevent 285 this. */ 286 bool peeling_for_gaps; 287 288 /* Reductions are canonicalized so that the last operand is the reduction 289 operand. If this places a constant into RHS1, this decanonicalizes 290 GIMPLE for other phases, so we must track when this has occurred and 291 fix it up. */ 292 bool operands_swapped; 293 294 } *loop_vec_info; 295 296 /* Access Functions. */ 297 #define LOOP_VINFO_LOOP(L) (L)->loop 298 #define LOOP_VINFO_BBS(L) (L)->bbs 299 #define LOOP_VINFO_NITERS(L) (L)->num_iters 300 /* Since LOOP_VINFO_NITERS can change after prologue peeling 301 retain total unchanged scalar loop iterations for cost model. */ 302 #define LOOP_VINFO_NITERS_UNCHANGED(L) (L)->num_iters_unchanged 303 #define LOOP_VINFO_COST_MODEL_MIN_ITERS(L) (L)->min_profitable_iters 304 #define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable 305 #define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor 306 #define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask 307 #define LOOP_VINFO_LOOP_NEST(L) (L)->loop_nest 308 #define LOOP_VINFO_DATAREFS(L) (L)->datarefs 309 #define LOOP_VINFO_DDRS(L) (L)->ddrs 310 #define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters)) 311 #define LOOP_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment 312 #define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr 313 #define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts 314 #define LOOP_VINFO_LOC(L) (L)->loop_line_number 315 #define LOOP_VINFO_MAY_ALIAS_DDRS(L) (L)->may_alias_ddrs 316 #define LOOP_VINFO_GROUPED_STORES(L) (L)->grouped_stores 317 #define LOOP_VINFO_SLP_INSTANCES(L) (L)->slp_instances 318 #define LOOP_VINFO_SLP_UNROLLING_FACTOR(L) (L)->slp_unrolling_factor 319 #define LOOP_VINFO_REDUCTIONS(L) (L)->reductions 320 #define LOOP_VINFO_REDUCTION_CHAINS(L) (L)->reduction_chains 321 #define LOOP_VINFO_PEELING_HTAB(L) (L)->peeling_htab 322 #define LOOP_VINFO_TARGET_COST_DATA(L) (L)->target_cost_data 323 #define LOOP_VINFO_PEELING_FOR_GAPS(L) (L)->peeling_for_gaps 324 #define LOOP_VINFO_OPERANDS_SWAPPED(L) (L)->operands_swapped 325 326 #define LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT(L) \ 327 ((L)->may_misalign_stmts.length () > 0) 328 #define LOOP_REQUIRES_VERSIONING_FOR_ALIAS(L) \ 329 ((L)->may_alias_ddrs.length () > 0) 330 331 #define NITERS_KNOWN_P(n) \ 332 (host_integerp ((n),0) \ 333 && TREE_INT_CST_LOW ((n)) > 0) 334 335 #define LOOP_VINFO_NITERS_KNOWN_P(L) \ 336 NITERS_KNOWN_P((L)->num_iters) 337 338 static inline loop_vec_info 339 loop_vec_info_for_loop (struct loop *loop) 340 { 341 return (loop_vec_info) loop->aux; 342 } 343 344 static inline bool 345 nested_in_vect_loop_p (struct loop *loop, gimple stmt) 346 { 347 return (loop->inner 348 && (loop->inner == (gimple_bb (stmt))->loop_father)); 349 } 350 351 typedef struct _bb_vec_info { 352 353 basic_block bb; 354 /* All interleaving chains of stores in the basic block, represented by the 355 first stmt in the chain. */ 356 vec<gimple> grouped_stores; 357 358 /* All SLP instances in the basic block. This is a subset of the set of 359 GROUP_STORES of the basic block. */ 360 vec<slp_instance> slp_instances; 361 362 /* All data references in the basic block. */ 363 vec<data_reference_p> datarefs; 364 365 /* All data dependences in the basic block. */ 366 vec<ddr_p> ddrs; 367 368 /* Cost data used by the target cost model. */ 369 void *target_cost_data; 370 371 } *bb_vec_info; 372 373 #define BB_VINFO_BB(B) (B)->bb 374 #define BB_VINFO_GROUPED_STORES(B) (B)->grouped_stores 375 #define BB_VINFO_SLP_INSTANCES(B) (B)->slp_instances 376 #define BB_VINFO_DATAREFS(B) (B)->datarefs 377 #define BB_VINFO_DDRS(B) (B)->ddrs 378 #define BB_VINFO_TARGET_COST_DATA(B) (B)->target_cost_data 379 380 static inline bb_vec_info 381 vec_info_for_bb (basic_block bb) 382 { 383 return (bb_vec_info) bb->aux; 384 } 385 386 /*-----------------------------------------------------------------*/ 387 /* Info on vectorized defs. */ 388 /*-----------------------------------------------------------------*/ 389 enum stmt_vec_info_type { 390 undef_vec_info_type = 0, 391 load_vec_info_type, 392 store_vec_info_type, 393 shift_vec_info_type, 394 op_vec_info_type, 395 call_vec_info_type, 396 assignment_vec_info_type, 397 condition_vec_info_type, 398 reduc_vec_info_type, 399 induc_vec_info_type, 400 type_promotion_vec_info_type, 401 type_demotion_vec_info_type, 402 type_conversion_vec_info_type, 403 loop_exit_ctrl_vec_info_type 404 }; 405 406 /* Indicates whether/how a variable is used in the scope of loop/basic 407 block. */ 408 enum vect_relevant { 409 vect_unused_in_scope = 0, 410 /* The def is in the inner loop, and the use is in the outer loop, and the 411 use is a reduction stmt. */ 412 vect_used_in_outer_by_reduction, 413 /* The def is in the inner loop, and the use is in the outer loop (and is 414 not part of reduction). */ 415 vect_used_in_outer, 416 417 /* defs that feed computations that end up (only) in a reduction. These 418 defs may be used by non-reduction stmts, but eventually, any 419 computations/values that are affected by these defs are used to compute 420 a reduction (i.e. don't get stored to memory, for example). We use this 421 to identify computations that we can change the order in which they are 422 computed. */ 423 vect_used_by_reduction, 424 425 vect_used_in_scope 426 }; 427 428 /* The type of vectorization that can be applied to the stmt: regular loop-based 429 vectorization; pure SLP - the stmt is a part of SLP instances and does not 430 have uses outside SLP instances; or hybrid SLP and loop-based - the stmt is 431 a part of SLP instance and also must be loop-based vectorized, since it has 432 uses outside SLP sequences. 433 434 In the loop context the meanings of pure and hybrid SLP are slightly 435 different. By saying that pure SLP is applied to the loop, we mean that we 436 exploit only intra-iteration parallelism in the loop; i.e., the loop can be 437 vectorized without doing any conceptual unrolling, cause we don't pack 438 together stmts from different iterations, only within a single iteration. 439 Loop hybrid SLP means that we exploit both intra-iteration and 440 inter-iteration parallelism (e.g., number of elements in the vector is 4 441 and the slp-group-size is 2, in which case we don't have enough parallelism 442 within an iteration, so we obtain the rest of the parallelism from subsequent 443 iterations by unrolling the loop by 2). */ 444 enum slp_vect_type { 445 loop_vect = 0, 446 pure_slp, 447 hybrid 448 }; 449 450 451 typedef struct data_reference *dr_p; 452 453 typedef struct _stmt_vec_info { 454 455 enum stmt_vec_info_type type; 456 457 /* Indicates whether this stmts is part of a computation whose result is 458 used outside the loop. */ 459 bool live; 460 461 /* Stmt is part of some pattern (computation idiom) */ 462 bool in_pattern_p; 463 464 /* For loads only, if there is a store with the same location, this field is 465 TRUE. */ 466 bool read_write_dep; 467 468 /* The stmt to which this info struct refers to. */ 469 gimple stmt; 470 471 /* The loop_vec_info with respect to which STMT is vectorized. */ 472 loop_vec_info loop_vinfo; 473 474 /* The vector type to be used for the LHS of this statement. */ 475 tree vectype; 476 477 /* The vectorized version of the stmt. */ 478 gimple vectorized_stmt; 479 480 481 /** The following is relevant only for stmts that contain a non-scalar 482 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have 483 at most one such data-ref. **/ 484 485 /* Information about the data-ref (access function, etc), 486 relative to the inner-most containing loop. */ 487 struct data_reference *data_ref_info; 488 489 /* Information about the data-ref relative to this loop 490 nest (the loop that is being considered for vectorization). */ 491 tree dr_base_address; 492 tree dr_init; 493 tree dr_offset; 494 tree dr_step; 495 tree dr_aligned_to; 496 497 /* For loop PHI nodes, the evolution part of it. This makes sure 498 this information is still available in vect_update_ivs_after_vectorizer 499 where we may not be able to re-analyze the PHI nodes evolution as 500 peeling for the prologue loop can make it unanalyzable. The evolution 501 part is still correct though. */ 502 tree loop_phi_evolution_part; 503 504 /* Used for various bookkeeping purposes, generally holding a pointer to 505 some other stmt S that is in some way "related" to this stmt. 506 Current use of this field is: 507 If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is 508 true): S is the "pattern stmt" that represents (and replaces) the 509 sequence of stmts that constitutes the pattern. Similarly, the 510 related_stmt of the "pattern stmt" points back to this stmt (which is 511 the last stmt in the original sequence of stmts that constitutes the 512 pattern). */ 513 gimple related_stmt; 514 515 /* Used to keep a sequence of def stmts of a pattern stmt if such exists. */ 516 gimple_seq pattern_def_seq; 517 518 /* List of datarefs that are known to have the same alignment as the dataref 519 of this stmt. */ 520 vec<dr_p> same_align_refs; 521 522 /* Classify the def of this stmt. */ 523 enum vect_def_type def_type; 524 525 /* Whether the stmt is SLPed, loop-based vectorized, or both. */ 526 enum slp_vect_type slp_type; 527 528 /* Interleaving and reduction chains info. */ 529 /* First element in the group. */ 530 gimple first_element; 531 /* Pointer to the next element in the group. */ 532 gimple next_element; 533 /* For data-refs, in case that two or more stmts share data-ref, this is the 534 pointer to the previously detected stmt with the same dr. */ 535 gimple same_dr_stmt; 536 /* The size of the group. */ 537 unsigned int size; 538 /* For stores, number of stores from this group seen. We vectorize the last 539 one. */ 540 unsigned int store_count; 541 /* For loads only, the gap from the previous load. For consecutive loads, GAP 542 is 1. */ 543 unsigned int gap; 544 545 /* The minimum negative dependence distance this stmt participates in 546 or zero if none. */ 547 unsigned int min_neg_dist; 548 549 /* Not all stmts in the loop need to be vectorized. e.g, the increment 550 of the loop induction variable and computation of array indexes. relevant 551 indicates whether the stmt needs to be vectorized. */ 552 enum vect_relevant relevant; 553 554 /* The bb_vec_info with respect to which STMT is vectorized. */ 555 bb_vec_info bb_vinfo; 556 557 /* Is this statement vectorizable or should it be skipped in (partial) 558 vectorization. */ 559 bool vectorizable; 560 561 /* For loads only, true if this is a gather load. */ 562 bool gather_p; 563 bool stride_load_p; 564 } *stmt_vec_info; 565 566 /* Access Functions. */ 567 #define STMT_VINFO_TYPE(S) (S)->type 568 #define STMT_VINFO_STMT(S) (S)->stmt 569 #define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo 570 #define STMT_VINFO_BB_VINFO(S) (S)->bb_vinfo 571 #define STMT_VINFO_RELEVANT(S) (S)->relevant 572 #define STMT_VINFO_LIVE_P(S) (S)->live 573 #define STMT_VINFO_VECTYPE(S) (S)->vectype 574 #define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt 575 #define STMT_VINFO_VECTORIZABLE(S) (S)->vectorizable 576 #define STMT_VINFO_DATA_REF(S) (S)->data_ref_info 577 #define STMT_VINFO_GATHER_P(S) (S)->gather_p 578 #define STMT_VINFO_STRIDE_LOAD_P(S) (S)->stride_load_p 579 580 #define STMT_VINFO_DR_BASE_ADDRESS(S) (S)->dr_base_address 581 #define STMT_VINFO_DR_INIT(S) (S)->dr_init 582 #define STMT_VINFO_DR_OFFSET(S) (S)->dr_offset 583 #define STMT_VINFO_DR_STEP(S) (S)->dr_step 584 #define STMT_VINFO_DR_ALIGNED_TO(S) (S)->dr_aligned_to 585 586 #define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p 587 #define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt 588 #define STMT_VINFO_PATTERN_DEF_SEQ(S) (S)->pattern_def_seq 589 #define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs 590 #define STMT_VINFO_DEF_TYPE(S) (S)->def_type 591 #define STMT_VINFO_GROUP_FIRST_ELEMENT(S) (S)->first_element 592 #define STMT_VINFO_GROUP_NEXT_ELEMENT(S) (S)->next_element 593 #define STMT_VINFO_GROUP_SIZE(S) (S)->size 594 #define STMT_VINFO_GROUP_STORE_COUNT(S) (S)->store_count 595 #define STMT_VINFO_GROUP_GAP(S) (S)->gap 596 #define STMT_VINFO_GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt 597 #define STMT_VINFO_GROUP_READ_WRITE_DEPENDENCE(S) (S)->read_write_dep 598 #define STMT_VINFO_GROUPED_ACCESS(S) ((S)->first_element != NULL && (S)->data_ref_info) 599 #define STMT_VINFO_LOOP_PHI_EVOLUTION_PART(S) (S)->loop_phi_evolution_part 600 #define STMT_VINFO_MIN_NEG_DIST(S) (S)->min_neg_dist 601 602 #define GROUP_FIRST_ELEMENT(S) (S)->first_element 603 #define GROUP_NEXT_ELEMENT(S) (S)->next_element 604 #define GROUP_SIZE(S) (S)->size 605 #define GROUP_STORE_COUNT(S) (S)->store_count 606 #define GROUP_GAP(S) (S)->gap 607 #define GROUP_SAME_DR_STMT(S) (S)->same_dr_stmt 608 #define GROUP_READ_WRITE_DEPENDENCE(S) (S)->read_write_dep 609 610 #define STMT_VINFO_RELEVANT_P(S) ((S)->relevant != vect_unused_in_scope) 611 612 #define HYBRID_SLP_STMT(S) ((S)->slp_type == hybrid) 613 #define PURE_SLP_STMT(S) ((S)->slp_type == pure_slp) 614 #define STMT_SLP_TYPE(S) (S)->slp_type 615 616 #define VECT_MAX_COST 1000 617 618 /* The maximum number of intermediate steps required in multi-step type 619 conversion. */ 620 #define MAX_INTERM_CVT_STEPS 3 621 622 /* The maximum vectorization factor supported by any target (V32QI). */ 623 #define MAX_VECTORIZATION_FACTOR 32 624 625 /* Avoid GTY(()) on stmt_vec_info. */ 626 typedef void *vec_void_p; 627 628 extern vec<vec_void_p> stmt_vec_info_vec; 629 630 void init_stmt_vec_info_vec (void); 631 void free_stmt_vec_info_vec (void); 632 633 /* Return a stmt_vec_info corresponding to STMT. */ 634 635 static inline stmt_vec_info 636 vinfo_for_stmt (gimple stmt) 637 { 638 unsigned int uid = gimple_uid (stmt); 639 if (uid == 0) 640 return NULL; 641 642 return (stmt_vec_info) stmt_vec_info_vec[uid - 1]; 643 } 644 645 /* Set vectorizer information INFO for STMT. */ 646 647 static inline void 648 set_vinfo_for_stmt (gimple stmt, stmt_vec_info info) 649 { 650 unsigned int uid = gimple_uid (stmt); 651 if (uid == 0) 652 { 653 gcc_checking_assert (info); 654 uid = stmt_vec_info_vec.length () + 1; 655 gimple_set_uid (stmt, uid); 656 stmt_vec_info_vec.safe_push ((vec_void_p) info); 657 } 658 else 659 stmt_vec_info_vec[uid - 1] = (vec_void_p) info; 660 } 661 662 /* Return the earlier statement between STMT1 and STMT2. */ 663 664 static inline gimple 665 get_earlier_stmt (gimple stmt1, gimple stmt2) 666 { 667 unsigned int uid1, uid2; 668 669 if (stmt1 == NULL) 670 return stmt2; 671 672 if (stmt2 == NULL) 673 return stmt1; 674 675 uid1 = gimple_uid (stmt1); 676 uid2 = gimple_uid (stmt2); 677 678 if (uid1 == 0 || uid2 == 0) 679 return NULL; 680 681 gcc_checking_assert (uid1 <= stmt_vec_info_vec.length () 682 && uid2 <= stmt_vec_info_vec.length ()); 683 684 if (uid1 < uid2) 685 return stmt1; 686 else 687 return stmt2; 688 } 689 690 /* Return the later statement between STMT1 and STMT2. */ 691 692 static inline gimple 693 get_later_stmt (gimple stmt1, gimple stmt2) 694 { 695 unsigned int uid1, uid2; 696 697 if (stmt1 == NULL) 698 return stmt2; 699 700 if (stmt2 == NULL) 701 return stmt1; 702 703 uid1 = gimple_uid (stmt1); 704 uid2 = gimple_uid (stmt2); 705 706 if (uid1 == 0 || uid2 == 0) 707 return NULL; 708 709 gcc_assert (uid1 <= stmt_vec_info_vec.length ()); 710 gcc_assert (uid2 <= stmt_vec_info_vec.length ()); 711 712 if (uid1 > uid2) 713 return stmt1; 714 else 715 return stmt2; 716 } 717 718 /* Return TRUE if a statement represented by STMT_INFO is a part of a 719 pattern. */ 720 721 static inline bool 722 is_pattern_stmt_p (stmt_vec_info stmt_info) 723 { 724 gimple related_stmt; 725 stmt_vec_info related_stmt_info; 726 727 related_stmt = STMT_VINFO_RELATED_STMT (stmt_info); 728 if (related_stmt 729 && (related_stmt_info = vinfo_for_stmt (related_stmt)) 730 && STMT_VINFO_IN_PATTERN_P (related_stmt_info)) 731 return true; 732 733 return false; 734 } 735 736 /* Return true if BB is a loop header. */ 737 738 static inline bool 739 is_loop_header_bb_p (basic_block bb) 740 { 741 if (bb == (bb->loop_father)->header) 742 return true; 743 gcc_checking_assert (EDGE_COUNT (bb->preds) == 1); 744 return false; 745 } 746 747 /* Return pow2 (X). */ 748 749 static inline int 750 vect_pow2 (int x) 751 { 752 int i, res = 1; 753 754 for (i = 0; i < x; i++) 755 res *= 2; 756 757 return res; 758 } 759 760 /* Alias targetm.vectorize.builtin_vectorization_cost. */ 761 762 static inline int 763 builtin_vectorization_cost (enum vect_cost_for_stmt type_of_cost, 764 tree vectype, int misalign) 765 { 766 return targetm.vectorize.builtin_vectorization_cost (type_of_cost, 767 vectype, misalign); 768 } 769 770 /* Get cost by calling cost target builtin. */ 771 772 static inline 773 int vect_get_stmt_cost (enum vect_cost_for_stmt type_of_cost) 774 { 775 return builtin_vectorization_cost (type_of_cost, NULL, 0); 776 } 777 778 /* Alias targetm.vectorize.init_cost. */ 779 780 static inline void * 781 init_cost (struct loop *loop_info) 782 { 783 return targetm.vectorize.init_cost (loop_info); 784 } 785 786 /* Alias targetm.vectorize.add_stmt_cost. */ 787 788 static inline unsigned 789 add_stmt_cost (void *data, int count, enum vect_cost_for_stmt kind, 790 stmt_vec_info stmt_info, int misalign, 791 enum vect_cost_model_location where) 792 { 793 return targetm.vectorize.add_stmt_cost (data, count, kind, 794 stmt_info, misalign, where); 795 } 796 797 /* Alias targetm.vectorize.finish_cost. */ 798 799 static inline void 800 finish_cost (void *data, unsigned *prologue_cost, 801 unsigned *body_cost, unsigned *epilogue_cost) 802 { 803 targetm.vectorize.finish_cost (data, prologue_cost, body_cost, epilogue_cost); 804 } 805 806 /* Alias targetm.vectorize.destroy_cost_data. */ 807 808 static inline void 809 destroy_cost_data (void *data) 810 { 811 targetm.vectorize.destroy_cost_data (data); 812 } 813 814 815 /*-----------------------------------------------------------------*/ 816 /* Info on data references alignment. */ 817 /*-----------------------------------------------------------------*/ 818 819 /* Reflects actual alignment of first access in the vectorized loop, 820 taking into account peeling/versioning if applied. */ 821 #define DR_MISALIGNMENT(DR) ((int) (size_t) (DR)->aux) 822 #define SET_DR_MISALIGNMENT(DR, VAL) ((DR)->aux = (void *) (size_t) (VAL)) 823 824 /* Return TRUE if the data access is aligned, and FALSE otherwise. */ 825 826 static inline bool 827 aligned_access_p (struct data_reference *data_ref_info) 828 { 829 return (DR_MISALIGNMENT (data_ref_info) == 0); 830 } 831 832 /* Return TRUE if the alignment of the data access is known, and FALSE 833 otherwise. */ 834 835 static inline bool 836 known_alignment_for_access_p (struct data_reference *data_ref_info) 837 { 838 return (DR_MISALIGNMENT (data_ref_info) != -1); 839 } 840 841 /* Source location */ 842 extern LOC vect_location; 843 844 /*-----------------------------------------------------------------*/ 845 /* Function prototypes. */ 846 /*-----------------------------------------------------------------*/ 847 848 /* Simple loop peeling and versioning utilities for vectorizer's purposes - 849 in tree-vect-loop-manip.c. */ 850 extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree); 851 extern bool slpeel_can_duplicate_loop_p (const struct loop *, const_edge); 852 extern void vect_loop_versioning (loop_vec_info, unsigned int, bool); 853 extern void vect_do_peeling_for_loop_bound (loop_vec_info, tree *, 854 unsigned int, bool); 855 extern void vect_do_peeling_for_alignment (loop_vec_info, unsigned int, bool); 856 extern LOC find_loop_location (struct loop *); 857 extern bool vect_can_advance_ivs_p (loop_vec_info); 858 859 /* In tree-vect-stmts.c. */ 860 extern unsigned int current_vector_size; 861 extern tree get_vectype_for_scalar_type (tree); 862 extern tree get_same_sized_vectype (tree, tree); 863 extern bool vect_is_simple_use (tree, gimple, loop_vec_info, 864 bb_vec_info, gimple *, 865 tree *, enum vect_def_type *); 866 extern bool vect_is_simple_use_1 (tree, gimple, loop_vec_info, 867 bb_vec_info, gimple *, 868 tree *, enum vect_def_type *, tree *); 869 extern bool supportable_widening_operation (enum tree_code, gimple, tree, tree, 870 enum tree_code *, enum tree_code *, 871 int *, vec<tree> *); 872 extern bool supportable_narrowing_operation (enum tree_code, tree, tree, 873 enum tree_code *, 874 int *, vec<tree> *); 875 extern stmt_vec_info new_stmt_vec_info (gimple stmt, loop_vec_info, 876 bb_vec_info); 877 extern void free_stmt_vec_info (gimple stmt); 878 extern tree vectorizable_function (gimple, tree, tree); 879 extern void vect_model_simple_cost (stmt_vec_info, int, enum vect_def_type *, 880 stmt_vector_for_cost *, 881 stmt_vector_for_cost *); 882 extern void vect_model_store_cost (stmt_vec_info, int, bool, 883 enum vect_def_type, slp_tree, 884 stmt_vector_for_cost *, 885 stmt_vector_for_cost *); 886 extern void vect_model_load_cost (stmt_vec_info, int, bool, slp_tree, 887 stmt_vector_for_cost *, 888 stmt_vector_for_cost *); 889 extern unsigned record_stmt_cost (stmt_vector_for_cost *, int, 890 enum vect_cost_for_stmt, stmt_vec_info, 891 int, enum vect_cost_model_location); 892 extern void vect_finish_stmt_generation (gimple, gimple, 893 gimple_stmt_iterator *); 894 extern bool vect_mark_stmts_to_be_vectorized (loop_vec_info); 895 extern tree vect_get_vec_def_for_operand (tree, gimple, tree *); 896 extern tree vect_init_vector (gimple, tree, tree, 897 gimple_stmt_iterator *); 898 extern tree vect_get_vec_def_for_stmt_copy (enum vect_def_type, tree); 899 extern bool vect_transform_stmt (gimple, gimple_stmt_iterator *, 900 bool *, slp_tree, slp_instance); 901 extern void vect_remove_stores (gimple); 902 extern bool vect_analyze_stmt (gimple, bool *, slp_tree); 903 extern bool vectorizable_condition (gimple, gimple_stmt_iterator *, gimple *, 904 tree, int, slp_tree); 905 extern void vect_get_load_cost (struct data_reference *, int, bool, 906 unsigned int *, unsigned int *, 907 stmt_vector_for_cost *, 908 stmt_vector_for_cost *, bool); 909 extern void vect_get_store_cost (struct data_reference *, int, 910 unsigned int *, stmt_vector_for_cost *); 911 extern bool vect_supportable_shift (enum tree_code, tree); 912 extern void vect_get_vec_defs (tree, tree, gimple, vec<tree> *, 913 vec<tree> *, slp_tree, int); 914 extern tree vect_gen_perm_mask (tree, unsigned char *); 915 916 /* In tree-vect-data-refs.c. */ 917 extern bool vect_can_force_dr_alignment_p (const_tree, unsigned int); 918 extern enum dr_alignment_support vect_supportable_dr_alignment 919 (struct data_reference *, bool); 920 extern tree vect_get_smallest_scalar_type (gimple, HOST_WIDE_INT *, 921 HOST_WIDE_INT *); 922 extern bool vect_analyze_data_ref_dependences (loop_vec_info, bb_vec_info, 923 int *); 924 extern bool vect_enhance_data_refs_alignment (loop_vec_info); 925 extern bool vect_analyze_data_refs_alignment (loop_vec_info, bb_vec_info); 926 extern bool vect_verify_datarefs_alignment (loop_vec_info, bb_vec_info); 927 extern bool vect_analyze_data_ref_accesses (loop_vec_info, bb_vec_info); 928 extern bool vect_prune_runtime_alias_test_list (loop_vec_info); 929 extern tree vect_check_gather (gimple, loop_vec_info, tree *, tree *, 930 int *); 931 extern bool vect_analyze_data_refs (loop_vec_info, bb_vec_info, int *); 932 extern tree vect_create_data_ref_ptr (gimple, tree, struct loop *, tree, 933 tree *, gimple_stmt_iterator *, 934 gimple *, bool, bool *, 935 tree = NULL_TREE); 936 extern tree bump_vector_ptr (tree, gimple, gimple_stmt_iterator *, gimple, tree); 937 extern tree vect_create_destination_var (tree, tree); 938 extern bool vect_grouped_store_supported (tree, unsigned HOST_WIDE_INT); 939 extern bool vect_store_lanes_supported (tree, unsigned HOST_WIDE_INT); 940 extern bool vect_grouped_load_supported (tree, unsigned HOST_WIDE_INT); 941 extern bool vect_load_lanes_supported (tree, unsigned HOST_WIDE_INT); 942 extern void vect_permute_store_chain (vec<tree> ,unsigned int, gimple, 943 gimple_stmt_iterator *, vec<tree> *); 944 extern tree vect_setup_realignment (gimple, gimple_stmt_iterator *, tree *, 945 enum dr_alignment_support, tree, 946 struct loop **); 947 extern void vect_transform_grouped_load (gimple, vec<tree> , int, 948 gimple_stmt_iterator *); 949 extern void vect_record_grouped_load_vectors (gimple, vec<tree> ); 950 extern int vect_get_place_in_interleaving_chain (gimple, gimple); 951 extern tree vect_get_new_vect_var (tree, enum vect_var_kind, const char *); 952 extern tree vect_create_addr_base_for_vector_ref (gimple, gimple_seq *, 953 tree, struct loop *, 954 tree = NULL_TREE); 955 956 /* In tree-vect-loop.c. */ 957 /* FORNOW: Used in tree-parloops.c. */ 958 extern void destroy_loop_vec_info (loop_vec_info, bool); 959 extern gimple vect_force_simple_reduction (loop_vec_info, gimple, bool, bool *); 960 /* Drive for loop analysis stage. */ 961 extern loop_vec_info vect_analyze_loop (struct loop *); 962 /* Drive for loop transformation stage. */ 963 extern void vect_transform_loop (loop_vec_info); 964 extern loop_vec_info vect_analyze_loop_form (struct loop *); 965 extern bool vectorizable_live_operation (gimple, gimple_stmt_iterator *, 966 gimple *); 967 extern bool vectorizable_reduction (gimple, gimple_stmt_iterator *, gimple *, 968 slp_tree); 969 extern bool vectorizable_induction (gimple, gimple_stmt_iterator *, gimple *); 970 extern tree get_initial_def_for_reduction (gimple, tree, tree *); 971 extern int vect_min_worthwhile_factor (enum tree_code); 972 extern int vect_get_known_peeling_cost (loop_vec_info, int, int *, int, 973 stmt_vector_for_cost *, 974 stmt_vector_for_cost *); 975 extern int vect_get_single_scalar_iteration_cost (loop_vec_info); 976 977 /* In tree-vect-slp.c. */ 978 extern void vect_free_slp_instance (slp_instance); 979 extern bool vect_transform_slp_perm_load (gimple, vec<tree> , 980 gimple_stmt_iterator *, int, 981 slp_instance, bool); 982 extern bool vect_schedule_slp (loop_vec_info, bb_vec_info); 983 extern void vect_update_slp_costs_according_to_vf (loop_vec_info); 984 extern bool vect_analyze_slp (loop_vec_info, bb_vec_info); 985 extern bool vect_make_slp_decision (loop_vec_info); 986 extern void vect_detect_hybrid_slp (loop_vec_info); 987 extern void vect_get_slp_defs (vec<tree> , slp_tree, 988 vec<vec<tree> > *, int); 989 990 extern LOC find_bb_location (basic_block); 991 extern bb_vec_info vect_slp_analyze_bb (basic_block); 992 extern void vect_slp_transform_bb (basic_block); 993 994 /* In tree-vect-patterns.c. */ 995 /* Pattern recognition functions. 996 Additional pattern recognition functions can (and will) be added 997 in the future. */ 998 typedef gimple (* vect_recog_func_ptr) (vec<gimple> *, tree *, tree *); 999 #define NUM_PATTERNS 10 1000 void vect_pattern_recog (loop_vec_info, bb_vec_info); 1001 1002 /* In tree-vectorizer.c. */ 1003 unsigned vectorize_loops (void); 1004 1005 #endif /* GCC_TREE_VECTORIZER_H */ 1006