1 /* Gimple Represented as Polyhedra. 2 Copyright (C) 2006-2017 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@inria.fr>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License 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 /* This pass converts GIMPLE to GRAPHITE, performs some loop 22 transformations and then converts the resulting representation back 23 to GIMPLE. 24 25 An early description of this pass can be found in the GCC Summit'06 26 paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC". 27 The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to 28 the related work. */ 29 30 #define USES_ISL 31 32 #include "config.h" 33 #include "system.h" 34 #include "coretypes.h" 35 #include "backend.h" 36 #include "diagnostic-core.h" 37 #include "cfgloop.h" 38 #include "tree-pass.h" 39 #include "params.h" 40 #include "pretty-print.h" 41 42 #ifdef HAVE_isl 43 #include "cfghooks.h" 44 #include "tree.h" 45 #include "gimple.h" 46 #include "fold-const.h" 47 #include "gimple-iterator.h" 48 #include "tree-cfg.h" 49 #include "tree-ssa-loop.h" 50 #include "tree-data-ref.h" 51 #include "tree-scalar-evolution.h" 52 #include "dbgcnt.h" 53 #include "tree-parloops.h" 54 #include "tree-cfgcleanup.h" 55 #include "tree-vectorizer.h" 56 #include "graphite.h" 57 58 /* Print global statistics to FILE. */ 59 60 static void 61 print_global_statistics (FILE* file) 62 { 63 long n_bbs = 0; 64 long n_loops = 0; 65 long n_stmts = 0; 66 long n_conditions = 0; 67 long n_p_bbs = 0; 68 long n_p_loops = 0; 69 long n_p_stmts = 0; 70 long n_p_conditions = 0; 71 72 basic_block bb; 73 74 FOR_ALL_BB_FN (bb, cfun) 75 { 76 gimple_stmt_iterator psi; 77 78 n_bbs++; 79 n_p_bbs += bb->count; 80 81 /* Ignore artificial surrounding loop. */ 82 if (bb == bb->loop_father->header 83 && bb->index != 0) 84 { 85 n_loops++; 86 n_p_loops += bb->count; 87 } 88 89 if (EDGE_COUNT (bb->succs) > 1) 90 { 91 n_conditions++; 92 n_p_conditions += bb->count; 93 } 94 95 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 96 { 97 n_stmts++; 98 n_p_stmts += bb->count; 99 } 100 } 101 102 fprintf (file, "\nGlobal statistics ("); 103 fprintf (file, "BBS:%ld, ", n_bbs); 104 fprintf (file, "LOOPS:%ld, ", n_loops); 105 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 106 fprintf (file, "STMTS:%ld)\n", n_stmts); 107 fprintf (file, "\nGlobal profiling statistics ("); 108 fprintf (file, "BBS:%ld, ", n_p_bbs); 109 fprintf (file, "LOOPS:%ld, ", n_p_loops); 110 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); 111 fprintf (file, "STMTS:%ld)\n", n_p_stmts); 112 } 113 114 /* Print statistics for SCOP to FILE. */ 115 116 static void 117 print_graphite_scop_statistics (FILE* file, scop_p scop) 118 { 119 long n_bbs = 0; 120 long n_loops = 0; 121 long n_stmts = 0; 122 long n_conditions = 0; 123 long n_p_bbs = 0; 124 long n_p_loops = 0; 125 long n_p_stmts = 0; 126 long n_p_conditions = 0; 127 128 basic_block bb; 129 130 FOR_ALL_BB_FN (bb, cfun) 131 { 132 gimple_stmt_iterator psi; 133 loop_p loop = bb->loop_father; 134 135 if (!bb_in_sese_p (bb, scop->scop_info->region)) 136 continue; 137 138 n_bbs++; 139 n_p_bbs += bb->count; 140 141 if (EDGE_COUNT (bb->succs) > 1) 142 { 143 n_conditions++; 144 n_p_conditions += bb->count; 145 } 146 147 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 148 { 149 n_stmts++; 150 n_p_stmts += bb->count; 151 } 152 153 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region)) 154 { 155 n_loops++; 156 n_p_loops += bb->count; 157 } 158 } 159 160 fprintf (file, "\nFunction Name: %s\n", current_function_name ()); 161 162 edge scop_begin = scop->scop_info->region.entry; 163 edge scop_end = scop->scop_info->region.exit; 164 165 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ", 166 scop_begin->src->index, scop_begin->dest->index); 167 fprintf (file, "exit_edge (bb_%d, bb_%d))", 168 scop_end->src->index, scop_end->dest->index); 169 170 fprintf (file, "\nSCoP statistics ("); 171 fprintf (file, "BBS:%ld, ", n_bbs); 172 fprintf (file, "LOOPS:%ld, ", n_loops); 173 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 174 fprintf (file, "STMTS:%ld)\n", n_stmts); 175 fprintf (file, "\nSCoP profiling statistics ("); 176 fprintf (file, "BBS:%ld, ", n_p_bbs); 177 fprintf (file, "LOOPS:%ld, ", n_p_loops); 178 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); 179 fprintf (file, "STMTS:%ld)\n", n_p_stmts); 180 } 181 182 /* Print statistics for SCOPS to FILE. */ 183 184 static void 185 print_graphite_statistics (FILE* file, vec<scop_p> scops) 186 { 187 int i; 188 189 scop_p scop; 190 191 FOR_EACH_VEC_ELT (scops, i, scop) 192 print_graphite_scop_statistics (file, scop); 193 194 /* Print the loop structure. */ 195 print_loops (file, 2); 196 print_loops (file, 3); 197 } 198 199 /* Initialize graphite: when there are no loops returns false. */ 200 201 static bool 202 graphite_initialize (isl_ctx *ctx) 203 { 204 int min_loops = PARAM_VALUE (PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION); 205 int max_bbs = PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION); 206 int nbbs = n_basic_blocks_for_fn (cfun); 207 int nloops = number_of_loops (cfun); 208 209 if (nloops <= min_loops 210 /* FIXME: This limit on the number of basic blocks of a function 211 should be removed when the SCOP detection is faster. */ 212 || (nbbs > max_bbs)) 213 { 214 if (dump_file && (dump_flags & TDF_DETAILS)) 215 { 216 if (nloops <= min_loops) 217 fprintf (dump_file, "\nFunction does not have enough loops: " 218 "PARAM_GRAPHITE_MIN_LOOPS_PER_FUNCTION = %d.\n", 219 min_loops); 220 221 else if (nbbs > max_bbs) 222 fprintf (dump_file, "\nFunction has too many basic blocks: " 223 "PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION = %d.\n", max_bbs); 224 225 fprintf (dump_file, "\nnumber of SCoPs: 0\n"); 226 print_global_statistics (dump_file); 227 } 228 229 isl_ctx_free (ctx); 230 return false; 231 } 232 233 scev_reset (); 234 recompute_all_dominators (); 235 initialize_original_copy_tables (); 236 237 if (dump_file && dump_flags) 238 { 239 dump_function_to_file (current_function_decl, dump_file, dump_flags); 240 print_loops (dump_file, 3); 241 } 242 243 return true; 244 } 245 246 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is 247 true. */ 248 249 static void 250 graphite_finalize (bool need_cfg_cleanup_p) 251 { 252 free_dominance_info (CDI_POST_DOMINATORS); 253 if (need_cfg_cleanup_p) 254 { 255 free_dominance_info (CDI_DOMINATORS); 256 scev_reset (); 257 cleanup_tree_cfg (); 258 profile_status_for_fn (cfun) = PROFILE_ABSENT; 259 release_recorded_exits (cfun); 260 tree_estimate_probability (false); 261 } 262 263 free_original_copy_tables (); 264 265 if (dump_file && dump_flags) 266 print_loops (dump_file, 3); 267 } 268 269 /* Deletes all scops in SCOPS. */ 270 271 static void 272 free_scops (vec<scop_p> scops) 273 { 274 int i; 275 scop_p scop; 276 277 FOR_EACH_VEC_ELT (scops, i, scop) 278 free_scop (scop); 279 280 scops.release (); 281 } 282 283 isl_ctx *the_isl_ctx; 284 285 /* Perform a set of linear transforms on the loops of the current 286 function. */ 287 288 void 289 graphite_transform_loops (void) 290 { 291 int i; 292 scop_p scop; 293 bool need_cfg_cleanup_p = false; 294 vec<scop_p> scops = vNULL; 295 isl_ctx *ctx; 296 297 /* If a function is parallel it was most probably already run through graphite 298 once. No need to run again. */ 299 if (parallelized_function_p (cfun->decl)) 300 return; 301 302 ctx = isl_ctx_alloc (); 303 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); 304 if (!graphite_initialize (ctx)) 305 return; 306 307 the_isl_ctx = ctx; 308 build_scops (&scops); 309 310 if (dump_file && (dump_flags & TDF_DETAILS)) 311 { 312 print_graphite_statistics (dump_file, scops); 313 print_global_statistics (dump_file); 314 } 315 316 FOR_EACH_VEC_ELT (scops, i, scop) 317 if (dbg_cnt (graphite_scop)) 318 { 319 scop->isl_context = ctx; 320 if (!build_poly_scop (scop)) 321 continue; 322 323 if (!apply_poly_transforms (scop)) 324 continue; 325 326 need_cfg_cleanup_p = true; 327 /* When code generation is not successful, do not continue 328 generating code for the next scops: the IR has to be cleaned up 329 and could be in an inconsistent state. */ 330 if (!graphite_regenerate_ast_isl (scop)) 331 break; 332 333 location_t loc = find_loop_location 334 (scop->scop_info->region.entry->dest->loop_father); 335 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, 336 "loop nest optimized\n"); 337 } 338 339 free_scops (scops); 340 graphite_finalize (need_cfg_cleanup_p); 341 the_isl_ctx = NULL; 342 isl_ctx_free (ctx); 343 } 344 345 #else /* If isl is not available: #ifndef HAVE_isl. */ 346 347 static void 348 graphite_transform_loops (void) 349 { 350 sorry ("Graphite loop optimizations cannot be used (isl is not available)."); 351 } 352 353 #endif 354 355 356 static unsigned int 357 graphite_transforms (struct function *fun) 358 { 359 if (number_of_loops (fun) <= 1) 360 return 0; 361 362 graphite_transform_loops (); 363 364 return 0; 365 } 366 367 static bool 368 gate_graphite_transforms (void) 369 { 370 /* Enable -fgraphite pass if any one of the graphite optimization flags 371 is turned on. */ 372 if (flag_graphite_identity 373 || flag_loop_parallelize_all 374 || flag_loop_nest_optimize) 375 flag_graphite = 1; 376 377 return flag_graphite != 0; 378 } 379 380 namespace { 381 382 const pass_data pass_data_graphite = 383 { 384 GIMPLE_PASS, /* type */ 385 "graphite0", /* name */ 386 OPTGROUP_LOOP, /* optinfo_flags */ 387 TV_GRAPHITE, /* tv_id */ 388 ( PROP_cfg | PROP_ssa ), /* properties_required */ 389 0, /* properties_provided */ 390 0, /* properties_destroyed */ 391 0, /* todo_flags_start */ 392 0, /* todo_flags_finish */ 393 }; 394 395 class pass_graphite : public gimple_opt_pass 396 { 397 public: 398 pass_graphite (gcc::context *ctxt) 399 : gimple_opt_pass (pass_data_graphite, ctxt) 400 {} 401 402 /* opt_pass methods: */ 403 virtual bool gate (function *) { return gate_graphite_transforms (); } 404 405 }; // class pass_graphite 406 407 } // anon namespace 408 409 gimple_opt_pass * 410 make_pass_graphite (gcc::context *ctxt) 411 { 412 return new pass_graphite (ctxt); 413 } 414 415 namespace { 416 417 const pass_data pass_data_graphite_transforms = 418 { 419 GIMPLE_PASS, /* type */ 420 "graphite", /* name */ 421 OPTGROUP_LOOP, /* optinfo_flags */ 422 TV_GRAPHITE_TRANSFORMS, /* tv_id */ 423 ( PROP_cfg | PROP_ssa ), /* properties_required */ 424 0, /* properties_provided */ 425 0, /* properties_destroyed */ 426 0, /* todo_flags_start */ 427 0, /* todo_flags_finish */ 428 }; 429 430 class pass_graphite_transforms : public gimple_opt_pass 431 { 432 public: 433 pass_graphite_transforms (gcc::context *ctxt) 434 : gimple_opt_pass (pass_data_graphite_transforms, ctxt) 435 {} 436 437 /* opt_pass methods: */ 438 virtual bool gate (function *) { return gate_graphite_transforms (); } 439 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); } 440 441 }; // class pass_graphite_transforms 442 443 } // anon namespace 444 445 gimple_opt_pass * 446 make_pass_graphite_transforms (gcc::context *ctxt) 447 { 448 return new pass_graphite_transforms (ctxt); 449 } 450 451 452