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