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 /* Loop and basic block vectorizer. 22 23 This file contains drivers for the three vectorizers: 24 (1) loop vectorizer (inter-iteration parallelism), 25 (2) loop-aware SLP (intra-iteration parallelism) (invoked by the loop 26 vectorizer) 27 (3) BB vectorizer (out-of-loops), aka SLP 28 29 The rest of the vectorizer's code is organized as follows: 30 - tree-vect-loop.c - loop specific parts such as reductions, etc. These are 31 used by drivers (1) and (2). 32 - tree-vect-loop-manip.c - vectorizer's loop control-flow utilities, used by 33 drivers (1) and (2). 34 - tree-vect-slp.c - BB vectorization specific analysis and transformation, 35 used by drivers (2) and (3). 36 - tree-vect-stmts.c - statements analysis and transformation (used by all). 37 - tree-vect-data-refs.c - vectorizer specific data-refs analysis and 38 manipulations (used by all). 39 - tree-vect-patterns.c - vectorizable code patterns detector (used by all) 40 41 Here's a poor attempt at illustrating that: 42 43 tree-vectorizer.c: 44 loop_vect() loop_aware_slp() slp_vect() 45 | / \ / 46 | / \ / 47 tree-vect-loop.c tree-vect-slp.c 48 | \ \ / / | 49 | \ \/ / | 50 | \ /\ / | 51 | \ / \ / | 52 tree-vect-stmts.c tree-vect-data-refs.c 53 \ / 54 tree-vect-patterns.c 55 */ 56 57 #include "config.h" 58 #include "system.h" 59 #include "coretypes.h" 60 #include "dumpfile.h" 61 #include "tm.h" 62 #include "ggc.h" 63 #include "tree.h" 64 #include "tree-pretty-print.h" 65 #include "tree-flow.h" 66 #include "cfgloop.h" 67 #include "tree-vectorizer.h" 68 #include "tree-pass.h" 69 70 /* Loop or bb location. */ 71 LOC vect_location; 72 73 /* Vector mapping GIMPLE stmt to stmt_vec_info. */ 74 vec<vec_void_p> stmt_vec_info_vec; 75 76 77 /* Function vectorize_loops. 78 79 Entry point to loop vectorization phase. */ 80 81 unsigned 82 vectorize_loops (void) 83 { 84 unsigned int i; 85 unsigned int num_vectorized_loops = 0; 86 unsigned int vect_loops_num; 87 loop_iterator li; 88 struct loop *loop; 89 90 vect_loops_num = number_of_loops (); 91 92 /* Bail out if there are no loops. */ 93 if (vect_loops_num <= 1) 94 return 0; 95 96 init_stmt_vec_info_vec (); 97 98 /* ----------- Analyze loops. ----------- */ 99 100 /* If some loop was duplicated, it gets bigger number 101 than all previously defined loops. This fact allows us to run 102 only over initial loops skipping newly generated ones. */ 103 FOR_EACH_LOOP (li, loop, 0) 104 if (optimize_loop_nest_for_speed_p (loop)) 105 { 106 loop_vec_info loop_vinfo; 107 vect_location = find_loop_location (loop); 108 if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOC 109 && dump_enabled_p ()) 110 dump_printf (MSG_ALL, "\nAnalyzing loop at %s:%d\n", 111 LOC_FILE (vect_location), LOC_LINE (vect_location)); 112 113 loop_vinfo = vect_analyze_loop (loop); 114 loop->aux = loop_vinfo; 115 116 if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo)) 117 continue; 118 119 if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOC 120 && dump_enabled_p ()) 121 dump_printf (MSG_ALL, "\n\nVectorizing loop at %s:%d\n", 122 LOC_FILE (vect_location), LOC_LINE (vect_location)); 123 vect_transform_loop (loop_vinfo); 124 num_vectorized_loops++; 125 } 126 127 vect_location = UNKNOWN_LOC; 128 129 statistics_counter_event (cfun, "Vectorized loops", num_vectorized_loops); 130 if (dump_enabled_p () 131 || (num_vectorized_loops > 0 && dump_enabled_p ())) 132 dump_printf_loc (MSG_ALL, vect_location, 133 "vectorized %u loops in function.\n", 134 num_vectorized_loops); 135 136 /* ----------- Finalize. ----------- */ 137 138 for (i = 1; i < vect_loops_num; i++) 139 { 140 loop_vec_info loop_vinfo; 141 142 loop = get_loop (i); 143 if (!loop) 144 continue; 145 loop_vinfo = (loop_vec_info) loop->aux; 146 destroy_loop_vec_info (loop_vinfo, true); 147 loop->aux = NULL; 148 } 149 150 free_stmt_vec_info_vec (); 151 152 return num_vectorized_loops > 0 ? TODO_cleanup_cfg : 0; 153 } 154 155 156 /* Entry point to basic block SLP phase. */ 157 158 static unsigned int 159 execute_vect_slp (void) 160 { 161 basic_block bb; 162 163 init_stmt_vec_info_vec (); 164 165 FOR_EACH_BB (bb) 166 { 167 vect_location = find_bb_location (bb); 168 169 if (vect_slp_analyze_bb (bb)) 170 { 171 vect_slp_transform_bb (bb); 172 if (dump_enabled_p ()) 173 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, 174 "basic block vectorized using SLP\n"); 175 } 176 } 177 178 free_stmt_vec_info_vec (); 179 return 0; 180 } 181 182 static bool 183 gate_vect_slp (void) 184 { 185 /* Apply SLP either if the vectorizer is on and the user didn't specify 186 whether to run SLP or not, or if the SLP flag was set by the user. */ 187 return ((flag_tree_vectorize != 0 && flag_tree_slp_vectorize != 0) 188 || flag_tree_slp_vectorize == 1); 189 } 190 191 struct gimple_opt_pass pass_slp_vectorize = 192 { 193 { 194 GIMPLE_PASS, 195 "slp", /* name */ 196 OPTGROUP_LOOP 197 | OPTGROUP_VEC, /* optinfo_flags */ 198 gate_vect_slp, /* gate */ 199 execute_vect_slp, /* execute */ 200 NULL, /* sub */ 201 NULL, /* next */ 202 0, /* static_pass_number */ 203 TV_TREE_SLP_VECTORIZATION, /* tv_id */ 204 PROP_ssa | PROP_cfg, /* properties_required */ 205 0, /* properties_provided */ 206 0, /* properties_destroyed */ 207 0, /* todo_flags_start */ 208 TODO_ggc_collect 209 | TODO_verify_ssa 210 | TODO_update_ssa 211 | TODO_verify_stmts /* todo_flags_finish */ 212 } 213 }; 214 215 216 /* Increase alignment of global arrays to improve vectorization potential. 217 TODO: 218 - Consider also structs that have an array field. 219 - Use ipa analysis to prune arrays that can't be vectorized? 220 This should involve global alignment analysis and in the future also 221 array padding. */ 222 223 static unsigned int 224 increase_alignment (void) 225 { 226 struct varpool_node *vnode; 227 228 vect_location = UNKNOWN_LOC; 229 230 /* Increase the alignment of all global arrays for vectorization. */ 231 FOR_EACH_DEFINED_VARIABLE (vnode) 232 { 233 tree vectype, decl = vnode->symbol.decl; 234 tree t; 235 unsigned int alignment; 236 237 t = TREE_TYPE(decl); 238 if (TREE_CODE (t) != ARRAY_TYPE) 239 continue; 240 vectype = get_vectype_for_scalar_type (strip_array_types (t)); 241 if (!vectype) 242 continue; 243 alignment = TYPE_ALIGN (vectype); 244 if (DECL_ALIGN (decl) >= alignment) 245 continue; 246 247 if (vect_can_force_dr_alignment_p (decl, alignment)) 248 { 249 DECL_ALIGN (decl) = TYPE_ALIGN (vectype); 250 DECL_USER_ALIGN (decl) = 1; 251 dump_printf (MSG_NOTE, "Increasing alignment of decl: "); 252 dump_generic_expr (MSG_NOTE, TDF_SLIM, decl); 253 dump_printf (MSG_NOTE, "\n"); 254 } 255 } 256 return 0; 257 } 258 259 260 static bool 261 gate_increase_alignment (void) 262 { 263 return flag_section_anchors && flag_tree_vectorize; 264 } 265 266 267 struct simple_ipa_opt_pass pass_ipa_increase_alignment = 268 { 269 { 270 SIMPLE_IPA_PASS, 271 "increase_alignment", /* name */ 272 OPTGROUP_LOOP 273 | OPTGROUP_VEC, /* optinfo_flags */ 274 gate_increase_alignment, /* gate */ 275 increase_alignment, /* execute */ 276 NULL, /* sub */ 277 NULL, /* next */ 278 0, /* static_pass_number */ 279 TV_IPA_OPT, /* tv_id */ 280 0, /* properties_required */ 281 0, /* properties_provided */ 282 0, /* properties_destroyed */ 283 0, /* todo_flags_start */ 284 0 /* todo_flags_finish */ 285 } 286 }; 287