contrib/gcc-4.1/gcc/tree-vectorizer.h

   1 /* Loop Vectorization
   2    Copyright (C) 2003, 2004, 2005 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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-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.  */
  40 enum 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.  */
  47 enum operation_type {
  48   unary_op = 1,
  49   binary_op
  50 };
  51
  52 /* Define type of available alignment support.  */
  53 enum 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.  */
  61 enum 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.  */
  71 enum 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 /*-----------------------------------------------------------------*/
  87 typedef 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 /*-----------------------------------------------------------------*/
 160 enum 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
 170 typedef struct data_reference *dr_p;
 171 DEF_VEC_P(dr_p);
 172 DEF_VEC_ALLOC_P(dr_p,heap);
 173
 174 typedef 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
 228 static inline void set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info);
 229 static inline stmt_vec_info vinfo_for_stmt (tree stmt);
 230
 231 static inline void
 232 set_stmt_info (tree_ann_t ann, stmt_vec_info stmt_info)
 233 {
 234   if (ann)
 235     ann->common.aux = (char *) stmt_info;
 236 }
 237
 238 static inline stmt_vec_info
 239 vinfo_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
 253 static inline bool
 254 aligned_access_p (struct data_reference *data_ref_info)
 255 {
 256   return (DR_MISALIGNMENT (data_ref_info) == 0);
 257 }
 258
 259 static inline bool
 260 known_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.  */
 269 extern FILE *vect_dump;
 270 extern enum verbosity_levels vect_verbosity_level;
 271
 272 /* Number of loops, at the beginning of vectorization.  */
 273 extern unsigned int vect_loops_num;
 274
 275 /* Bitmap of virtual variables to be renamed.  */
 276 extern 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.  */
 292 extern struct loop *slpeel_tree_peel_loop_to_edge
 293   (struct loop *, struct loops *, edge, tree, tree, bool);
 294 extern void slpeel_make_loop_iterate_ntimes (struct loop *, tree);
 295 extern bool slpeel_can_duplicate_loop_p (struct loop *, edge);
 296 #ifdef ENABLE_CHECKING
 297 extern 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 **/
 305 extern tree vect_strip_conversion (tree);
 306 extern tree get_vectype_for_scalar_type (tree);
 307 extern bool vect_is_simple_use (tree, loop_vec_info, tree *, tree *,
 308                                 enum vect_def_type *);
 309 extern bool vect_is_simple_iv_evolution (unsigned, tree, tree *, tree *);
 310 extern tree vect_is_simple_reduction (struct loop *, tree);
 311 extern bool vect_can_force_dr_alignment_p (tree, unsigned int);
 312 extern enum dr_alignment_support vect_supportable_dr_alignment
 313   (struct data_reference *);
 314 extern bool reduction_code_for_scalar_code (enum tree_code, enum tree_code *);
 315
 316 /* Creation and deletion of loop and stmt info structs.  */
 317 extern loop_vec_info new_loop_vec_info (struct loop *loop);
 318 extern void destroy_loop_vec_info (loop_vec_info);
 319 extern stmt_vec_info new_stmt_vec_info (tree stmt, loop_vec_info);
 320 /* Main driver.  */
 321 extern void vectorize_loops (struct loops *);
 322
 323 /** In tree-vect-analyze.c  **/
 324 /* Driver for analysis stage.  */
 325 extern loop_vec_info vect_analyze_loop (struct loop *);
 326
 327 /** In tree-vect-transform.c  **/
 328 extern bool vectorizable_load (tree, block_stmt_iterator *, tree *);
 329 extern bool vectorizable_store (tree, block_stmt_iterator *, tree *);
 330 extern bool vectorizable_operation (tree, block_stmt_iterator *, tree *);
 331 extern bool vectorizable_assignment (tree, block_stmt_iterator *, tree *);
 332 extern bool vectorizable_condition (tree, block_stmt_iterator *, tree *);
 333 extern bool vectorizable_live_operation (tree, block_stmt_iterator *, tree *);
 334 extern bool vectorizable_reduction (tree, block_stmt_iterator *, tree *);
 335 /* Driver for transformation stage.  */
 336 extern void vect_transform_loop (loop_vec_info, struct loops *);
 337
 338 /*************************************************************************
 339   Vectorization Debug Information - in tree-vectorizer.c
 340  *************************************************************************/
 341 extern bool vect_print_dump_info (enum verbosity_levels);
 342 extern void vect_set_verbosity_level (const char *);
 343 extern LOC find_loop_location (struct loop *);
 344
 345 #endif  /* GCC_TREE_VECTORIZER_H  */