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