1/* Loop Vectorization 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Dorit Naishlos <dorit@il.ibm.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 21 22#ifndef GCC_TREE_VECTORIZER_H 23#define GCC_TREE_VECTORIZER_H 24 25#ifdef USE_MAPPED_LOCATION 26 typedef source_location LOC; 27 #define UNKNOWN_LOC UNKNOWN_LOCATION 28 #define EXPR_LOC(e) EXPR_LOCATION(e) 29 #define LOC_FILE(l) LOCATION_FILE (l) 30 #define LOC_LINE(l) LOCATION_LINE (l) 31#else 32 typedef source_locus LOC; 33 #define UNKNOWN_LOC NULL 34 #define EXPR_LOC(e) EXPR_LOCUS(e) 35 #define LOC_FILE(l) (l)->file 36 #define LOC_LINE(l) (l)->line 37#endif 38 39/* Used for naming of new temporaries. */ 40enum vect_var_kind { 41 vect_simple_var, 42 vect_pointer_var, 43 vect_scalar_var 44}; 45 46/* Defines type of operation: unary or binary. */ 47enum operation_type { 48 unary_op = 1, 49 binary_op 50}; 51 52/* Define type of available alignment support. */ 53enum dr_alignment_support { 54 dr_unaligned_unsupported, 55 dr_unaligned_supported, 56 dr_unaligned_software_pipeline, 57 dr_aligned 58}; 59 60/* Define type of def-use cross-iteration cycle. */ 61enum vect_def_type { 62 vect_constant_def, 63 vect_invariant_def, 64 vect_loop_def, 65 vect_induction_def, 66 vect_reduction_def, 67 vect_unknown_def_type 68}; 69 70/* Define verbosity levels. */ 71enum verbosity_levels { 72 REPORT_NONE, 73 REPORT_VECTORIZED_LOOPS, 74 REPORT_UNVECTORIZED_LOOPS, 75 REPORT_ALIGNMENT, 76 REPORT_DR_DETAILS, 77 REPORT_BAD_FORM_LOOPS, 78 REPORT_OUTER_LOOPS, 79 REPORT_DETAILS, 80 /* New verbosity levels should be added before this one. */ 81 MAX_VERBOSITY_LEVEL 82}; 83 84/*-----------------------------------------------------------------*/ 85/* Info on vectorized loops. */ 86/*-----------------------------------------------------------------*/ 87typedef struct _loop_vec_info { 88 89 /* The loop to which this info struct refers to. */ 90 struct loop *loop; 91 92 /* The loop basic blocks. */ 93 basic_block *bbs; 94 95 /* The loop exit_condition. */ 96 tree exit_cond; 97 98 /* Number of iterations. */ 99 tree num_iters; 100 101 /* Is the loop vectorizable? */ 102 bool vectorizable; 103 104 /* Unrolling factor */ 105 int vectorization_factor; 106 107 /* Unknown DRs according to which loop was peeled. */ 108 struct data_reference *unaligned_dr; 109 110 /* peeling_for_alignment indicates whether peeling for alignment will take 111 place, and what the peeling factor should be: 112 peeling_for_alignment = X means: 113 If X=0: Peeling for alignment will not be applied. 114 If X>0: Peel first X iterations. 115 If X=-1: Generate a runtime test to calculate the number of iterations 116 to be peeled, using the dataref recorded in the field 117 unaligned_dr. */ 118 int peeling_for_alignment; 119 120 /* The mask used to check the alignment of pointers or arrays. */ 121 int ptr_mask; 122 123 /* All data references in the loop. */ 124 varray_type datarefs; 125 126 /* All data dependences in the loop. */ 127 varray_type ddrs; 128 129 /* Statements in the loop that have data references that are candidates for a 130 runtime (loop versioning) misalignment check. */ 131 VEC(tree,heap) *may_misalign_stmts; 132 133 /* The loop location in the source. */ 134 LOC loop_line_number; 135} *loop_vec_info; 136 137/* Access Functions. */ 138#define LOOP_VINFO_LOOP(L) (L)->loop 139#define LOOP_VINFO_BBS(L) (L)->bbs 140#define LOOP_VINFO_EXIT_COND(L) (L)->exit_cond 141#define LOOP_VINFO_NITERS(L) (L)->num_iters 142#define LOOP_VINFO_VECTORIZABLE_P(L) (L)->vectorizable 143#define LOOP_VINFO_VECT_FACTOR(L) (L)->vectorization_factor 144#define LOOP_VINFO_PTR_MASK(L) (L)->ptr_mask 145#define LOOP_VINFO_DATAREFS(L) (L)->datarefs 146#define LOOP_VINFO_DDRS(L) (L)->ddrs 147#define LOOP_VINFO_INT_NITERS(L) (TREE_INT_CST_LOW ((L)->num_iters)) 148#define LOOP_PEELING_FOR_ALIGNMENT(L) (L)->peeling_for_alignment 149#define LOOP_VINFO_UNALIGNED_DR(L) (L)->unaligned_dr 150#define LOOP_VINFO_MAY_MISALIGN_STMTS(L) (L)->may_misalign_stmts 151#define LOOP_VINFO_LOC(L) (L)->loop_line_number 152 153#define LOOP_VINFO_NITERS_KNOWN_P(L) \ 154(host_integerp ((L)->num_iters,0) \ 155&& TREE_INT_CST_LOW ((L)->num_iters) > 0) 156 157/*-----------------------------------------------------------------*/ 158/* Info on vectorized defs. */ 159/*-----------------------------------------------------------------*/ 160enum stmt_vec_info_type { 161 undef_vec_info_type = 0, 162 load_vec_info_type, 163 store_vec_info_type, 164 op_vec_info_type, 165 assignment_vec_info_type, 166 condition_vec_info_type, 167 reduc_vec_info_type 168}; 169 170typedef struct data_reference *dr_p; 171DEF_VEC_P(dr_p); 172DEF_VEC_ALLOC_P(dr_p,heap); 173 174typedef struct _stmt_vec_info { 175 176 enum stmt_vec_info_type type; 177 178 /* The stmt to which this info struct refers to. */ 179 tree stmt; 180 181 /* The loop_vec_info with respect to which STMT is vectorized. */ 182 loop_vec_info loop_vinfo; 183 184 /* Not all stmts in the loop need to be vectorized. e.g, the incrementation 185 of the loop induction variable and computation of array indexes. relevant 186 indicates whether the stmt needs to be vectorized. */ 187 bool relevant; 188 189 /* Indicates whether this stmts is part of a computation whose result is 190 used outside the loop. */ 191 bool live; 192 193 /* The vector type to be used. */ 194 tree vectype; 195 196 /* The vectorized version of the stmt. */ 197 tree vectorized_stmt; 198 199 200 /** The following is relevant only for stmts that contain a non-scalar 201 data-ref (array/pointer/struct access). A GIMPLE stmt is expected to have 202 at most one such data-ref. **/ 203 204 /* Information about the data-ref (access function, etc). */ 205 struct data_reference *data_ref_info; 206 207 /* List of datarefs that are known to have the same alignment as the dataref 208 of this stmt. */ 209 VEC(dr_p,heap) *same_align_refs; 210 211 /* Classify the def of this stmt. */ 212 enum vect_def_type def_type; 213 214} *stmt_vec_info; 215 216/* Access Functions. */ 217#define STMT_VINFO_TYPE(S) (S)->type 218#define STMT_VINFO_STMT(S) (S)->stmt 219#define STMT_VINFO_LOOP_VINFO(S) (S)->loop_vinfo 220#define STMT_VINFO_RELEVANT_P(S) (S)->relevant 221#define STMT_VINFO_LIVE_P(S) (S)->live 222#define STMT_VINFO_VECTYPE(S) (S)->vectype 223#define STMT_VINFO_VEC_STMT(S) (S)->vectorized_stmt 224#define STMT_VINFO_DATA_REF(S) (S)->data_ref_info 225#define STMT_VINFO_SAME_ALIGN_REFS(S) (S)->same_align_refs 226#define STMT_VINFO_DEF_TYPE(S) (S)->def_type 227 228static inline void set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info); 229static inline stmt_vec_info vinfo_for_stmt (tree stmt); 230 231static inline void 232set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info) 233{ 234 if (ann) 235 ann->common.aux = (char *) stmt_info; 236} 237 238static inline stmt_vec_info 239vinfo_for_stmt (tree stmt) 240{ 241 tree_ann_t ann = tree_ann (stmt); 242 return ann ? (stmt_vec_info) ann->common.aux : NULL; 243} 244 245/*-----------------------------------------------------------------*/ 246/* Info on data references alignment. */ 247/*-----------------------------------------------------------------*/ 248 249/* Reflects actual alignment of first access in the vectorized loop, 250 taking into account peeling/versioning if applied. */ 251#define DR_MISALIGNMENT(DR) (DR)->aux 252 253static inline bool 254aligned_access_p (struct data_reference *data_ref_info) 255{ 256 return (DR_MISALIGNMENT (data_ref_info) == 0); 257} 258 259static inline bool 260known_alignment_for_access_p (struct data_reference *data_ref_info) 261{ 262 return (DR_MISALIGNMENT (data_ref_info) != -1); 263} 264 265/* Perform signed modulo, always returning a non-negative value. */ 266#define VECT_SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y)) 267 268/* vect_dump will be set to stderr or dump_file if exist. */ 269extern FILE *vect_dump; 270extern enum verbosity_levels vect_verbosity_level; 271 272/* Number of loops, at the beginning of vectorization. */ 273extern unsigned int vect_loops_num; 274 275/* Bitmap of virtual variables to be renamed. */ 276extern bitmap vect_vnames_to_rename; 277 278/*-----------------------------------------------------------------*/ 279/* Function prototypes. */ 280/*-----------------------------------------------------------------*/ 281 282/************************************************************************* 283 Simple Loop Peeling Utilities - in tree-vectorizer.c 284 *************************************************************************/ 285/* Entry point for peeling of simple loops. 286 Peel the first/last iterations of a loop. 287 It can be used outside of the vectorizer for loops that are simple enough 288 (see function documentation). In the vectorizer it is used to peel the 289 last few iterations when the loop bound is unknown or does not evenly 290 divide by the vectorization factor, and to peel the first few iterations 291 to force the alignment of data references in the loop. */ 292extern struct loop *slpeel_tree_peel_loop_to_edge 293 (struct loop *, struct loops *, edge, tree, tree, bool); 294extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree); 295extern bool slpeel_can_duplicate_loop_p (struct loop *, edge); 296#ifdef ENABLE_CHECKING 297extern void slpeel_verify_cfg_after_peeling (struct loop *, struct loop *); 298#endif 299 300 301/************************************************************************* 302 General Vectorization Utilities 303 *************************************************************************/ 304/** In tree-vectorizer.c **/ 305extern tree vect_strip_conversion (tree); 306extern tree get_vectype_for_scalar_type (tree); 307extern bool vect_is_simple_use (tree, loop_vec_info, tree *, tree *, 308 enum vect_def_type *); 309extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *); 310extern tree vect_is_simple_reduction (struct loop *, tree); 311extern bool vect_can_force_dr_alignment_p (tree, unsigned int); 312extern enum dr_alignment_support vect_supportable_dr_alignment 313 (struct data_reference *); 314extern bool reduction_code_for_scalar_code (enum tree_code, enum tree_code *); 315 316/* Creation and deletion of loop and stmt info structs. */ 317extern loop_vec_info new_loop_vec_info (struct loop *loop); 318extern void destroy_loop_vec_info (loop_vec_info); 319extern stmt_vec_info new_stmt_vec_info (tree stmt, loop_vec_info); 320/* Main driver. */ 321extern void vectorize_loops (struct loops *); 322 323/** In tree-vect-analyze.c **/ 324/* Driver for analysis stage. */ 325extern loop_vec_info vect_analyze_loop (struct loop *); 326 327/** In tree-vect-transform.c **/ 328extern bool vectorizable_load (tree, block_stmt_iterator *, tree *); 329extern bool vectorizable_store (tree, block_stmt_iterator *, tree *); 330extern bool vectorizable_operation (tree, block_stmt_iterator *, tree *); 331extern bool vectorizable_assignment (tree, block_stmt_iterator *, tree *); 332extern bool vectorizable_condition (tree, block_stmt_iterator *, tree *); 333extern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *); 334extern bool vectorizable_reduction (tree, block_stmt_iterator *, tree *); 335/* Driver for transformation stage. */ 336extern void vect_transform_loop (loop_vec_info, struct loops *); 337 338/************************************************************************* 339 Vectorization Debug Information - in tree-vectorizer.c 340 *************************************************************************/ 341extern bool vect_print_dump_info (enum verbosity_levels); 342extern void vect_set_verbosity_level (const char *); 343extern LOC find_loop_location (struct loop *); 344 345#endif /* GCC_TREE_VECTORIZER_H */ 346