1169689Skan/* Loop Vectorization 2169689Skan Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 3169689Skan Contributed by Dorit Naishlos <dorit@il.ibm.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan#ifndef GCC_TREE_VECTORIZER_H 23169689Skan#define GCC_TREE_VECTORIZER_H 24169689Skan 25169689Skan#ifdef USE_MAPPED_LOCATION 26169689Skan typedef source_location LOC; 27169689Skan #define UNKNOWN_LOC UNKNOWN_LOCATION 28169689Skan #define EXPR_LOC(e) EXPR_LOCATION(e) 29169689Skan #define LOC_FILE(l) LOCATION_FILE (l) 30169689Skan #define LOC_LINE(l) LOCATION_LINE (l) 31169689Skan#else 32169689Skan typedef source_locus LOC; 33169689Skan #define UNKNOWN_LOC NULL 34169689Skan #define EXPR_LOC(e) EXPR_LOCUS(e) 35169689Skan #define LOC_FILE(l) (l)->file 36169689Skan #define LOC_LINE(l) (l)->line 37169689Skan#endif 38169689Skan 39169689Skan/* Used for naming of new temporaries. */ 40169689Skanenum vect_var_kind { 41169689Skan vect_simple_var, 42169689Skan vect_pointer_var, 43169689Skan vect_scalar_var 44169689Skan}; 45169689Skan 46169689Skan/* Defines type of operation. */ 47169689Skanenum operation_type { 48169689Skan unary_op = 1, 49169689Skan binary_op, 50169689Skan ternary_op 51169689Skan}; 52169689Skan 53169689Skan/* Define type of available alignment support. */ 54169689Skanenum dr_alignment_support { 55169689Skan dr_unaligned_unsupported, 56169689Skan dr_unaligned_supported, 57169689Skan dr_unaligned_software_pipeline, 58169689Skan dr_aligned 59169689Skan}; 60169689Skan 61169689Skan/* Define type of def-use cross-iteration cycle. */ 62169689Skanenum vect_def_type { 63169689Skan vect_constant_def, 64169689Skan vect_invariant_def, 65169689Skan vect_loop_def, 66169689Skan vect_induction_def, 67169689Skan vect_reduction_def, 68169689Skan vect_unknown_def_type 69169689Skan}; 70169689Skan 71169689Skan/* Define verbosity levels. */ 72169689Skanenum verbosity_levels { 73169689Skan REPORT_NONE, 74169689Skan REPORT_VECTORIZED_LOOPS, 75169689Skan REPORT_UNVECTORIZED_LOOPS, 76169689Skan REPORT_ALIGNMENT, 77169689Skan REPORT_DR_DETAILS, 78169689Skan REPORT_BAD_FORM_LOOPS, 79169689Skan REPORT_OUTER_LOOPS, 80169689Skan REPORT_DETAILS, 81169689Skan /* New verbosity levels should be added before this one. */ 82169689Skan MAX_VERBOSITY_LEVEL 83169689Skan}; 84169689Skan 85169689Skan/*-----------------------------------------------------------------*/ 86169689Skan/* Info on vectorized loops. */ 87169689Skan/*-----------------------------------------------------------------*/ 88169689Skantypedef struct _loop_vec_info { 89169689Skan 90169689Skan /* The loop to which this info struct refers to. */ 91169689Skan struct loop *loop; 92169689Skan 93169689Skan /* The loop basic blocks. */ 94169689Skan basic_block *bbs; 95169689Skan 96169689Skan /* The loop exit_condition. */ 97169689Skan tree exit_cond; 98169689Skan 99169689Skan /* Number of iterations. */ 100169689Skan tree num_iters; 101169689Skan 102169689Skan /* Is the loop vectorizable? */ 103169689Skan bool vectorizable; 104169689Skan 105169689Skan /* Unrolling factor */ 106169689Skan int vectorization_factor; 107169689Skan 108169689Skan /* Unknown DRs according to which loop was peeled. */ 109169689Skan struct data_reference *unaligned_dr; 110169689Skan 111169689Skan /* peeling_for_alignment indicates whether peeling for alignment will take 112169689Skan place, and what the peeling factor should be: 113169689Skan peeling_for_alignment = X means: 114169689Skan If X=0: Peeling for alignment will not be applied. 115169689Skan If X>0: Peel first X iterations. 116169689Skan If X=-1: Generate a runtime test to calculate the number of iterations 117169689Skan to be peeled, using the dataref recorded in the field 118169689Skan unaligned_dr. */ 119169689Skan int peeling_for_alignment; 120169689Skan 121169689Skan /* The mask used to check the alignment of pointers or arrays. */ 122169689Skan int ptr_mask; 123169689Skan 124169689Skan /* All data references in the loop. */ 125169689Skan VEC (data_reference_p, heap) *datarefs; 126169689Skan 127169689Skan /* All data dependences in the loop. */ 128169689Skan VEC (ddr_p, heap) *ddrs; 129169689Skan 130169689Skan /* Statements in the loop that have data references that are candidates for a 131169689Skan runtime (loop versioning) misalignment check. */ 132169689Skan VEC(tree,heap) *may_misalign_stmts; 133169689Skan 134169689Skan /* The loop location in the source. */ 135169689Skan LOC loop_line_number; 136169689Skan} *loop_vec_info; 137169689Skan 138169689Skan/* Access Functions. */ 139169689Skan#define LOOP_VINFO_LOOP(L) (L)->loop 140169689Skan#define LOOP_VINFO_BBS(L) (L)->bbs 141169689Skan#define LOOP_VINFO_EXIT_COND(L) (L)->exit_cond 142169689Skan#define LOOP_VINFO_NITERS(L) (L)->num_iters 143169689Skan#define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable 144169689Skan#define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor 145169689Skan#define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask 146169689Skan#define LOOP_VINFO_DATAREFS(L) (L)->datarefs 147169689Skan#define LOOP_VINFO_DDRS(L) (L)->ddrs 148169689Skan#define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters)) 149169689Skan#define LOOP_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment 150169689Skan#define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr 151169689Skan#define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts 152169689Skan#define LOOP_VINFO_LOC(L) (L)->loop_line_number 153169689Skan 154169689Skan#define LOOP_VINFO_NITERS_KNOWN_P(L) \ 155169689Skan(host_integerp ((L)->num_iters,0) \ 156169689Skan&& TREE_INT_CST_LOW ((L)->num_iters) > 0) 157169689Skan 158169689Skan/*-----------------------------------------------------------------*/ 159169689Skan/* Info on vectorized defs. */ 160169689Skan/*-----------------------------------------------------------------*/ 161169689Skanenum stmt_vec_info_type { 162169689Skan undef_vec_info_type = 0, 163169689Skan load_vec_info_type, 164169689Skan store_vec_info_type, 165169689Skan op_vec_info_type, 166169689Skan assignment_vec_info_type, 167169689Skan condition_vec_info_type, 168169689Skan reduc_vec_info_type 169169689Skan}; 170169689Skan 171169689Skantypedef struct data_reference *dr_p; 172169689SkanDEF_VEC_P(dr_p); 173169689SkanDEF_VEC_ALLOC_P(dr_p,heap); 174169689Skan 175169689Skantypedef struct _stmt_vec_info { 176169689Skan 177169689Skan enum stmt_vec_info_type type; 178169689Skan 179169689Skan /* The stmt to which this info struct refers to. */ 180169689Skan tree stmt; 181169689Skan 182169689Skan /* The loop_vec_info with respect to which STMT is vectorized. */ 183169689Skan loop_vec_info loop_vinfo; 184169689Skan 185169689Skan /* Not all stmts in the loop need to be vectorized. e.g, the incrementation 186169689Skan of the loop induction variable and computation of array indexes. relevant 187169689Skan indicates whether the stmt needs to be vectorized. */ 188169689Skan bool relevant; 189169689Skan 190169689Skan /* Indicates whether this stmts is part of a computation whose result is 191169689Skan used outside the loop. */ 192169689Skan bool live; 193169689Skan 194169689Skan /* The vector type to be used. */ 195169689Skan tree vectype; 196169689Skan 197169689Skan /* The vectorized version of the stmt. */ 198169689Skan tree vectorized_stmt; 199169689Skan 200169689Skan 201169689Skan /** The following is relevant only for stmts that contain a non-scalar 202169689Skan data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have 203169689Skan at most one such data-ref. **/ 204169689Skan 205169689Skan /* Information about the data-ref (access function, etc). */ 206169689Skan struct data_reference *data_ref_info; 207169689Skan 208169689Skan /* Stmt is part of some pattern (computation idiom) */ 209169689Skan bool in_pattern_p; 210169689Skan 211169689Skan /* Used for various bookkeeping purposes, generally holding a pointer to 212169689Skan some other stmt S that is in some way "related" to this stmt. 213169689Skan Current use of this field is: 214169689Skan If this stmt is part of a pattern (i.e. the field 'in_pattern_p' is 215169689Skan true): S is the "pattern stmt" that represents (and replaces) the 216169689Skan sequence of stmts that constitutes the pattern. Similarly, the 217169689Skan related_stmt of the "pattern stmt" points back to this stmt (which is 218169689Skan the last stmt in the original sequence of stmts that constitutes the 219169689Skan pattern). */ 220169689Skan tree related_stmt; 221169689Skan 222169689Skan /* List of datarefs that are known to have the same alignment as the dataref 223169689Skan of this stmt. */ 224169689Skan VEC(dr_p,heap) *same_align_refs; 225169689Skan 226169689Skan /* Classify the def of this stmt. */ 227169689Skan enum vect_def_type def_type; 228169689Skan 229169689Skan} *stmt_vec_info; 230169689Skan 231169689Skan/* Access Functions. */ 232169689Skan#define STMT_VINFO_TYPE(S) (S)->type 233169689Skan#define STMT_VINFO_STMT(S) (S)->stmt 234169689Skan#define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo 235169689Skan#define STMT_VINFO_RELEVANT_P(S) (S)->relevant 236169689Skan#define STMT_VINFO_LIVE_P(S) (S)->live 237169689Skan#define STMT_VINFO_VECTYPE(S) (S)->vectype 238169689Skan#define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt 239169689Skan#define STMT_VINFO_DATA_REF(S) (S)->data_ref_info 240169689Skan#define STMT_VINFO_IN_PATTERN_P(S) (S)->in_pattern_p 241169689Skan#define STMT_VINFO_RELATED_STMT(S) (S)->related_stmt 242169689Skan#define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs 243169689Skan#define STMT_VINFO_DEF_TYPE(S) (S)->def_type 244169689Skan 245169689Skanstatic inline void set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info); 246169689Skanstatic inline stmt_vec_info vinfo_for_stmt (tree stmt); 247169689Skan 248169689Skanstatic inline void 249169689Skanset_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info) 250169689Skan{ 251169689Skan if (ann) 252169689Skan ann->common.aux = (char *) stmt_info; 253169689Skan} 254169689Skan 255169689Skanstatic inline stmt_vec_info 256169689Skanvinfo_for_stmt (tree stmt) 257169689Skan{ 258169689Skan stmt_ann_t ann = stmt_ann (stmt); 259169689Skan return ann ? (stmt_vec_info) ann->common.aux : NULL; 260169689Skan} 261169689Skan 262169689Skan/*-----------------------------------------------------------------*/ 263169689Skan/* Info on data references alignment. */ 264169689Skan/*-----------------------------------------------------------------*/ 265169689Skan 266169689Skan/* Reflects actual alignment of first access in the vectorized loop, 267169689Skan taking into account peeling/versioning if applied. */ 268169689Skan#define DR_MISALIGNMENT(DR) (DR)->aux 269169689Skan 270169689Skanstatic inline bool 271169689Skanaligned_access_p (struct data_reference *data_ref_info) 272169689Skan{ 273169689Skan return (DR_MISALIGNMENT (data_ref_info) == 0); 274169689Skan} 275169689Skan 276169689Skanstatic inline bool 277169689Skanknown_alignment_for_access_p (struct data_reference *data_ref_info) 278169689Skan{ 279169689Skan return (DR_MISALIGNMENT (data_ref_info) != -1); 280169689Skan} 281169689Skan 282169689Skan/* Perform signed modulo, always returning a non-negative value. */ 283169689Skan#define VECT_SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y)) 284169689Skan 285169689Skan/* vect_dump will be set to stderr or dump_file if exist. */ 286169689Skanextern FILE *vect_dump; 287169689Skanextern enum verbosity_levels vect_verbosity_level; 288169689Skan 289169689Skan/* Number of loops, at the beginning of vectorization. */ 290169689Skanextern unsigned int vect_loops_num; 291169689Skan 292169689Skan/* Bitmap of virtual variables to be renamed. */ 293169689Skanextern bitmap vect_vnames_to_rename; 294169689Skan 295169689Skan/*-----------------------------------------------------------------*/ 296169689Skan/* Function prototypes. */ 297169689Skan/*-----------------------------------------------------------------*/ 298169689Skan 299169689Skan/************************************************************************* 300169689Skan Simple Loop Peeling Utilities - in tree-vectorizer.c 301169689Skan *************************************************************************/ 302169689Skan/* Entry point for peeling of simple loops. 303169689Skan Peel the first/last iterations of a loop. 304169689Skan It can be used outside of the vectorizer for loops that are simple enough 305169689Skan (see function documentation). In the vectorizer it is used to peel the 306169689Skan last few iterations when the loop bound is unknown or does not evenly 307169689Skan divide by the vectorization factor, and to peel the first few iterations 308169689Skan to force the alignment of data references in the loop. */ 309169689Skanextern struct loop *slpeel_tree_peel_loop_to_edge 310169689Skan (struct loop *, struct loops *, edge, tree, tree, bool); 311169689Skanextern void slpeel_make_loop_iterate_ntimes (struct loop *, tree); 312169689Skanextern bool slpeel_can_duplicate_loop_p (struct loop *, edge); 313169689Skan#ifdef ENABLE_CHECKING 314169689Skanextern void slpeel_verify_cfg_after_peeling (struct loop *, struct loop *); 315169689Skan#endif 316169689Skan 317169689Skan 318169689Skan/************************************************************************* 319169689Skan General Vectorization Utilities 320169689Skan *************************************************************************/ 321169689Skan/** In tree-vectorizer.c **/ 322169689Skanextern tree get_vectype_for_scalar_type (tree); 323169689Skanextern bool vect_is_simple_use (tree, loop_vec_info, tree *, tree *, 324169689Skan enum vect_def_type *); 325169689Skanextern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *); 326169689Skanextern tree vect_is_simple_reduction (struct loop *, tree); 327169689Skanextern bool vect_can_force_dr_alignment_p (tree, unsigned int); 328169689Skanextern enum dr_alignment_support vect_supportable_dr_alignment 329169689Skan (struct data_reference *); 330169689Skanextern bool reduction_code_for_scalar_code (enum tree_code, enum tree_code *); 331169689Skan/* Creation and deletion of loop and stmt info structs. */ 332169689Skanextern loop_vec_info new_loop_vec_info (struct loop *loop); 333169689Skanextern void destroy_loop_vec_info (loop_vec_info); 334169689Skanextern stmt_vec_info new_stmt_vec_info (tree stmt, loop_vec_info); 335169689Skan/* Main driver. */ 336169689Skanextern void vectorize_loops (struct loops *); 337169689Skan 338169689Skan 339169689Skan/** In tree-vect-analyze.c **/ 340169689Skan/* Driver for analysis stage. */ 341169689Skanextern loop_vec_info vect_analyze_loop (struct loop *); 342169689Skan 343169689Skan 344169689Skan/** In tree-vect-patterns.c **/ 345169689Skan/* Pattern recognition functions. 346169689Skan Additional pattern recognition functions can (and will) be added 347169689Skan in the future. */ 348169689Skantypedef tree (* vect_recog_func_ptr) (tree, tree *, tree *); 349169689Skan#define NUM_PATTERNS 3 350169689Skanvoid vect_pattern_recog (loop_vec_info); 351169689Skan 352169689Skan 353169689Skan/** In tree-vect-transform.c **/ 354169689Skanextern bool vectorizable_load (tree, block_stmt_iterator *, tree *); 355169689Skanextern bool vectorizable_store (tree, block_stmt_iterator *, tree *); 356169689Skanextern bool vectorizable_operation (tree, block_stmt_iterator *, tree *); 357169689Skanextern bool vectorizable_assignment (tree, block_stmt_iterator *, tree *); 358169689Skanextern bool vectorizable_condition (tree, block_stmt_iterator *, tree *); 359169689Skanextern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *); 360169689Skanextern bool vectorizable_reduction (tree, block_stmt_iterator *, tree *); 361169689Skan/* Driver for transformation stage. */ 362169689Skanextern void vect_transform_loop (loop_vec_info, struct loops *); 363169689Skan 364169689Skan/************************************************************************* 365169689Skan Vectorization Debug Information - in tree-vectorizer.c 366169689Skan *************************************************************************/ 367169689Skanextern bool vect_print_dump_info (enum verbosity_levels); 368169689Skanextern void vect_set_verbosity_level (const char *); 369169689Skanextern LOC find_loop_location (struct loop *); 370169689Skan 371169689Skan#endif /* GCC_TREE_VECTORIZER_H */ 372