1 /* Gimple Represented as Polyhedra. 2 Copyright (C) 2006-2015 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 One important document to read is CLooG's internal manual: 31 http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD 32 that describes the data structure of loops used in this file, and 33 the functions that are used for transforming the code. */ 34 35 #include "config.h" 36 37 #ifdef HAVE_isl 38 #include <isl/constraint.h> 39 #include <isl/set.h> 40 #include <isl/map.h> 41 #include <isl/options.h> 42 #include <isl/union_map.h> 43 #endif 44 45 #include "system.h" 46 #include "coretypes.h" 47 #include "diagnostic-core.h" 48 #include "hash-set.h" 49 #include "machmode.h" 50 #include "vec.h" 51 #include "double-int.h" 52 #include "input.h" 53 #include "alias.h" 54 #include "symtab.h" 55 #include "options.h" 56 #include "wide-int.h" 57 #include "inchash.h" 58 #include "tree.h" 59 #include "fold-const.h" 60 #include "predict.h" 61 #include "tm.h" 62 #include "hard-reg-set.h" 63 #include "input.h" 64 #include "function.h" 65 #include "dominance.h" 66 #include "cfg.h" 67 #include "basic-block.h" 68 #include "tree-ssa-alias.h" 69 #include "internal-fn.h" 70 #include "gimple-expr.h" 71 #include "is-a.h" 72 #include "gimple.h" 73 #include "gimple-iterator.h" 74 #include "tree-cfg.h" 75 #include "tree-ssa-loop.h" 76 #include "tree-dump.h" 77 #include "cfgloop.h" 78 #include "tree-chrec.h" 79 #include "tree-data-ref.h" 80 #include "tree-scalar-evolution.h" 81 #include "sese.h" 82 #include "dbgcnt.h" 83 #include "tree-parloops.h" 84 #include "tree-pass.h" 85 #include "tree-cfgcleanup.h" 86 87 #ifdef HAVE_isl 88 89 #include "graphite-poly.h" 90 #include "graphite-scop-detection.h" 91 #include "graphite-isl-ast-to-gimple.h" 92 #include "graphite-sese-to-poly.h" 93 94 /* Print global statistics to FILE. */ 95 96 static void 97 print_global_statistics (FILE* file) 98 { 99 long n_bbs = 0; 100 long n_loops = 0; 101 long n_stmts = 0; 102 long n_conditions = 0; 103 long n_p_bbs = 0; 104 long n_p_loops = 0; 105 long n_p_stmts = 0; 106 long n_p_conditions = 0; 107 108 basic_block bb; 109 110 FOR_ALL_BB_FN (bb, cfun) 111 { 112 gimple_stmt_iterator psi; 113 114 n_bbs++; 115 n_p_bbs += bb->count; 116 117 /* Ignore artificial surrounding loop. */ 118 if (bb == bb->loop_father->header 119 && bb->index != 0) 120 { 121 n_loops++; 122 n_p_loops += bb->count; 123 } 124 125 if (EDGE_COUNT (bb->succs) > 1) 126 { 127 n_conditions++; 128 n_p_conditions += bb->count; 129 } 130 131 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 132 { 133 n_stmts++; 134 n_p_stmts += bb->count; 135 } 136 } 137 138 fprintf (file, "\nGlobal statistics ("); 139 fprintf (file, "BBS:%ld, ", n_bbs); 140 fprintf (file, "LOOPS:%ld, ", n_loops); 141 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 142 fprintf (file, "STMTS:%ld)\n", n_stmts); 143 fprintf (file, "\nGlobal profiling statistics ("); 144 fprintf (file, "BBS:%ld, ", n_p_bbs); 145 fprintf (file, "LOOPS:%ld, ", n_p_loops); 146 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); 147 fprintf (file, "STMTS:%ld)\n", n_p_stmts); 148 } 149 150 /* Print statistics for SCOP to FILE. */ 151 152 static void 153 print_graphite_scop_statistics (FILE* file, scop_p scop) 154 { 155 long n_bbs = 0; 156 long n_loops = 0; 157 long n_stmts = 0; 158 long n_conditions = 0; 159 long n_p_bbs = 0; 160 long n_p_loops = 0; 161 long n_p_stmts = 0; 162 long n_p_conditions = 0; 163 164 basic_block bb; 165 166 FOR_ALL_BB_FN (bb, cfun) 167 { 168 gimple_stmt_iterator psi; 169 loop_p loop = bb->loop_father; 170 171 if (!bb_in_sese_p (bb, SCOP_REGION (scop))) 172 continue; 173 174 n_bbs++; 175 n_p_bbs += bb->count; 176 177 if (EDGE_COUNT (bb->succs) > 1) 178 { 179 n_conditions++; 180 n_p_conditions += bb->count; 181 } 182 183 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 184 { 185 n_stmts++; 186 n_p_stmts += bb->count; 187 } 188 189 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) 190 { 191 n_loops++; 192 n_p_loops += bb->count; 193 } 194 } 195 196 fprintf (file, "\nSCoP statistics ("); 197 fprintf (file, "BBS:%ld, ", n_bbs); 198 fprintf (file, "LOOPS:%ld, ", n_loops); 199 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 200 fprintf (file, "STMTS:%ld)\n", n_stmts); 201 fprintf (file, "\nSCoP profiling statistics ("); 202 fprintf (file, "BBS:%ld, ", n_p_bbs); 203 fprintf (file, "LOOPS:%ld, ", n_p_loops); 204 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); 205 fprintf (file, "STMTS:%ld)\n", n_p_stmts); 206 } 207 208 /* Print statistics for SCOPS to FILE. */ 209 210 static void 211 print_graphite_statistics (FILE* file, vec<scop_p> scops) 212 { 213 int i; 214 215 scop_p scop; 216 217 FOR_EACH_VEC_ELT (scops, i, scop) 218 print_graphite_scop_statistics (file, scop); 219 } 220 221 /* Initialize graphite: when there are no loops returns false. */ 222 223 static bool 224 graphite_initialize (isl_ctx *ctx) 225 { 226 if (number_of_loops (cfun) <= 1 227 /* FIXME: This limit on the number of basic blocks of a function 228 should be removed when the SCOP detection is faster. */ 229 || (n_basic_blocks_for_fn (cfun) > 230 PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))) 231 { 232 if (dump_file && (dump_flags & TDF_DETAILS)) 233 print_global_statistics (dump_file); 234 235 isl_ctx_free (ctx); 236 return false; 237 } 238 239 scev_reset (); 240 recompute_all_dominators (); 241 initialize_original_copy_tables (); 242 243 if (dump_file && dump_flags) 244 dump_function_to_file (current_function_decl, dump_file, dump_flags); 245 246 return true; 247 } 248 249 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is 250 true. */ 251 252 static void 253 graphite_finalize (bool need_cfg_cleanup_p) 254 { 255 if (need_cfg_cleanup_p) 256 { 257 scev_reset (); 258 cleanup_tree_cfg (); 259 profile_status_for_fn (cfun) = PROFILE_ABSENT; 260 release_recorded_exits (); 261 tree_estimate_probability (); 262 } 263 264 free_original_copy_tables (); 265 266 if (dump_file && dump_flags) 267 print_loops (dump_file, 3); 268 } 269 270 isl_ctx *the_isl_ctx; 271 272 /* Perform a set of linear transforms on the loops of the current 273 function. */ 274 275 void 276 graphite_transform_loops (void) 277 { 278 int i; 279 scop_p scop; 280 bool need_cfg_cleanup_p = false; 281 vec<scop_p> scops = vNULL; 282 isl_ctx *ctx; 283 284 /* If a function is parallel it was most probably already run through graphite 285 once. No need to run again. */ 286 if (parallelized_function_p (cfun->decl)) 287 return; 288 289 ctx = isl_ctx_alloc (); 290 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); 291 if (!graphite_initialize (ctx)) 292 return; 293 294 the_isl_ctx = ctx; 295 build_scops (&scops); 296 297 if (dump_file && (dump_flags & TDF_DETAILS)) 298 { 299 print_graphite_statistics (dump_file, scops); 300 print_global_statistics (dump_file); 301 } 302 303 FOR_EACH_VEC_ELT (scops, i, scop) 304 if (dbg_cnt (graphite_scop)) 305 { 306 scop->ctx = ctx; 307 build_poly_scop (scop); 308 309 if (POLY_SCOP_P (scop) 310 && apply_poly_transforms (scop) 311 && graphite_regenerate_ast_isl (scop)) 312 need_cfg_cleanup_p = true; 313 314 } 315 316 free_scops (scops); 317 graphite_finalize (need_cfg_cleanup_p); 318 the_isl_ctx = NULL; 319 isl_ctx_free (ctx); 320 } 321 322 #else /* If ISL is not available: #ifndef HAVE_isl. */ 323 324 static void 325 graphite_transform_loops (void) 326 { 327 sorry ("Graphite loop optimizations cannot be used (ISL is not available)."); 328 } 329 330 #endif 331 332 333 static unsigned int 334 graphite_transforms (struct function *fun) 335 { 336 if (number_of_loops (fun) <= 1) 337 return 0; 338 339 graphite_transform_loops (); 340 341 return 0; 342 } 343 344 static bool 345 gate_graphite_transforms (void) 346 { 347 /* Enable -fgraphite pass if any one of the graphite optimization flags 348 is turned on. */ 349 if (flag_loop_block 350 || flag_loop_interchange 351 || flag_loop_strip_mine 352 || flag_graphite_identity 353 || flag_loop_parallelize_all 354 || flag_loop_optimize_isl 355 || flag_loop_unroll_jam) 356 flag_graphite = 1; 357 358 return flag_graphite != 0; 359 } 360 361 namespace { 362 363 const pass_data pass_data_graphite = 364 { 365 GIMPLE_PASS, /* type */ 366 "graphite0", /* name */ 367 OPTGROUP_LOOP, /* optinfo_flags */ 368 TV_GRAPHITE, /* tv_id */ 369 ( PROP_cfg | PROP_ssa ), /* properties_required */ 370 0, /* properties_provided */ 371 0, /* properties_destroyed */ 372 0, /* todo_flags_start */ 373 0, /* todo_flags_finish */ 374 }; 375 376 class pass_graphite : public gimple_opt_pass 377 { 378 public: 379 pass_graphite (gcc::context *ctxt) 380 : gimple_opt_pass (pass_data_graphite, ctxt) 381 {} 382 383 /* opt_pass methods: */ 384 virtual bool gate (function *) { return gate_graphite_transforms (); } 385 386 }; // class pass_graphite 387 388 } // anon namespace 389 390 gimple_opt_pass * 391 make_pass_graphite (gcc::context *ctxt) 392 { 393 return new pass_graphite (ctxt); 394 } 395 396 namespace { 397 398 const pass_data pass_data_graphite_transforms = 399 { 400 GIMPLE_PASS, /* type */ 401 "graphite", /* name */ 402 OPTGROUP_LOOP, /* optinfo_flags */ 403 TV_GRAPHITE_TRANSFORMS, /* tv_id */ 404 ( PROP_cfg | PROP_ssa ), /* properties_required */ 405 0, /* properties_provided */ 406 0, /* properties_destroyed */ 407 0, /* todo_flags_start */ 408 0, /* todo_flags_finish */ 409 }; 410 411 class pass_graphite_transforms : public gimple_opt_pass 412 { 413 public: 414 pass_graphite_transforms (gcc::context *ctxt) 415 : gimple_opt_pass (pass_data_graphite_transforms, ctxt) 416 {} 417 418 /* opt_pass methods: */ 419 virtual bool gate (function *) { return gate_graphite_transforms (); } 420 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); } 421 422 }; // class pass_graphite_transforms 423 424 } // anon namespace 425 426 gimple_opt_pass * 427 make_pass_graphite_transforms (gcc::context *ctxt) 428 { 429 return new pass_graphite_transforms (ctxt); 430 } 431 432 433