1 /* Gimple Represented as Polyhedra. 2 Copyright (C) 2006-2018 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 #include "cfganal.h" 42 43 #ifdef HAVE_isl 44 #include "cfghooks.h" 45 #include "tree.h" 46 #include "gimple.h" 47 #include "ssa.h" 48 #include "fold-const.h" 49 #include "gimple-iterator.h" 50 #include "tree-cfg.h" 51 #include "tree-ssa-loop.h" 52 #include "tree-data-ref.h" 53 #include "tree-scalar-evolution.h" 54 #include "dbgcnt.h" 55 #include "tree-parloops.h" 56 #include "tree-cfgcleanup.h" 57 #include "tree-vectorizer.h" 58 #include "tree-ssa-loop-manip.h" 59 #include "tree-ssa.h" 60 #include "tree-into-ssa.h" 61 #include "graphite.h" 62 63 /* Print global statistics to FILE. */ 64 65 static void 66 print_global_statistics (FILE* file) 67 { 68 long n_bbs = 0; 69 long n_loops = 0; 70 long n_stmts = 0; 71 long n_conditions = 0; 72 profile_count n_p_bbs = profile_count::zero (); 73 profile_count n_p_loops = profile_count::zero (); 74 profile_count n_p_stmts = profile_count::zero (); 75 profile_count n_p_conditions = profile_count::zero (); 76 77 basic_block bb; 78 79 FOR_ALL_BB_FN (bb, cfun) 80 { 81 gimple_stmt_iterator psi; 82 83 n_bbs++; 84 if (bb->count.initialized_p ()) 85 n_p_bbs += bb->count; 86 87 /* Ignore artificial surrounding loop. */ 88 if (bb == bb->loop_father->header 89 && bb->index != 0) 90 { 91 n_loops++; 92 n_p_loops += bb->count; 93 } 94 95 if (EDGE_COUNT (bb->succs) > 1) 96 { 97 n_conditions++; 98 if (bb->count.initialized_p ()) 99 n_p_conditions += bb->count; 100 } 101 102 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 103 { 104 n_stmts++; 105 if (bb->count.initialized_p ()) 106 n_p_stmts += bb->count; 107 } 108 } 109 110 fprintf (file, "\nGlobal statistics ("); 111 fprintf (file, "BBS:%ld, ", n_bbs); 112 fprintf (file, "LOOPS:%ld, ", n_loops); 113 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 114 fprintf (file, "STMTS:%ld)\n", n_stmts); 115 fprintf (file, "Global profiling statistics ("); 116 fprintf (file, "BBS:"); 117 n_p_bbs.dump (file); 118 fprintf (file, ", LOOPS:"); 119 n_p_loops.dump (file); 120 fprintf (file, ", CONDITIONS:"); 121 n_p_conditions.dump (file); 122 fprintf (file, ", STMTS:"); 123 n_p_stmts.dump (file); 124 fprintf (file, ")\n\n"); 125 } 126 127 /* Print statistics for SCOP to FILE. */ 128 129 static void 130 print_graphite_scop_statistics (FILE* file, scop_p scop) 131 { 132 long n_bbs = 0; 133 long n_loops = 0; 134 long n_stmts = 0; 135 long n_conditions = 0; 136 profile_count n_p_bbs = profile_count::zero (); 137 profile_count n_p_loops = profile_count::zero (); 138 profile_count n_p_stmts = profile_count::zero (); 139 profile_count n_p_conditions = profile_count::zero (); 140 141 basic_block bb; 142 143 FOR_ALL_BB_FN (bb, cfun) 144 { 145 gimple_stmt_iterator psi; 146 loop_p loop = bb->loop_father; 147 148 if (!bb_in_sese_p (bb, scop->scop_info->region)) 149 continue; 150 151 n_bbs++; 152 if (bb->count.initialized_p ()) 153 n_p_bbs += bb->count; 154 155 if (EDGE_COUNT (bb->succs) > 1) 156 { 157 n_conditions++; 158 n_p_conditions += bb->count; 159 } 160 161 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 162 { 163 n_stmts++; 164 n_p_stmts += bb->count; 165 } 166 167 if (loop->header == bb && loop_in_sese_p (loop, scop->scop_info->region)) 168 { 169 n_loops++; 170 n_p_loops += bb->count; 171 } 172 } 173 174 fprintf (file, "\nFunction Name: %s\n", current_function_name ()); 175 176 edge scop_begin = scop->scop_info->region.entry; 177 edge scop_end = scop->scop_info->region.exit; 178 179 fprintf (file, "\nSCoP (entry_edge (bb_%d, bb_%d), ", 180 scop_begin->src->index, scop_begin->dest->index); 181 fprintf (file, "exit_edge (bb_%d, bb_%d))", 182 scop_end->src->index, scop_end->dest->index); 183 184 fprintf (file, "\nSCoP statistics ("); 185 fprintf (file, "BBS:%ld, ", n_bbs); 186 fprintf (file, "LOOPS:%ld, ", n_loops); 187 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 188 fprintf (file, "STMTS:%ld)\n", n_stmts); 189 fprintf (file, "SCoP profiling statistics ("); 190 fprintf (file, "BBS:"); 191 n_p_bbs.dump (file); 192 fprintf (file, ", LOOPS:"); 193 n_p_loops.dump (file); 194 fprintf (file, ", CONDITIONS:"); 195 n_p_conditions.dump (file); 196 fprintf (file, ", STMTS:"); 197 n_p_stmts.dump (file); 198 fprintf (file, ")\n\n"); 199 } 200 201 /* Print statistics for SCOPS to FILE. */ 202 203 static void 204 print_graphite_statistics (FILE* file, vec<scop_p> scops) 205 { 206 int i; 207 scop_p scop; 208 209 FOR_EACH_VEC_ELT (scops, i, scop) 210 print_graphite_scop_statistics (file, scop); 211 } 212 213 /* Deletes all scops in SCOPS. */ 214 215 static void 216 free_scops (vec<scop_p> scops) 217 { 218 int i; 219 scop_p scop; 220 221 FOR_EACH_VEC_ELT (scops, i, scop) 222 free_scop (scop); 223 224 scops.release (); 225 } 226 227 /* Transforms LOOP to the canonical loop closed SSA form. */ 228 229 static void 230 canonicalize_loop_closed_ssa (loop_p loop, edge e) 231 { 232 basic_block bb; 233 gphi_iterator psi; 234 235 bb = e->dest; 236 237 /* Make the loop-close PHI node BB contain only PHIs and have a 238 single predecessor. */ 239 if (single_pred_p (bb)) 240 { 241 e = split_block_after_labels (bb); 242 bb = e->src; 243 } 244 else 245 { 246 basic_block close = split_edge (e); 247 e = single_succ_edge (close); 248 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) 249 { 250 gphi *phi = psi.phi (); 251 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e); 252 tree arg = USE_FROM_PTR (use_p); 253 254 /* Only add close phi nodes for SSA_NAMEs defined in LOOP. */ 255 if (TREE_CODE (arg) != SSA_NAME 256 || SSA_NAME_IS_DEFAULT_DEF (arg) 257 || ! flow_bb_inside_loop_p (loop, 258 gimple_bb (SSA_NAME_DEF_STMT (arg)))) 259 continue; 260 261 tree res = copy_ssa_name (arg); 262 gphi *close_phi = create_phi_node (res, close); 263 add_phi_arg (close_phi, arg, gimple_phi_arg_edge (close_phi, 0), 264 UNKNOWN_LOCATION); 265 SET_USE (use_p, res); 266 } 267 bb = close; 268 } 269 270 /* Eliminate duplicates. This relies on processing loops from 271 innermost to outer. */ 272 for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi)) 273 { 274 gphi_iterator gsi = psi; 275 gphi *phi = psi.phi (); 276 277 /* At this point, PHI should be a close phi in normal form. */ 278 gcc_assert (gimple_phi_num_args (phi) == 1); 279 280 /* Iterate over the next phis and remove duplicates. */ 281 gsi_next (&gsi); 282 while (!gsi_end_p (gsi)) 283 if (gimple_phi_arg_def (phi, 0) == gimple_phi_arg_def (gsi.phi (), 0)) 284 { 285 replace_uses_by (gimple_phi_result (gsi.phi ()), 286 gimple_phi_result (phi)); 287 remove_phi_node (&gsi, true); 288 } 289 else 290 gsi_next (&gsi); 291 } 292 } 293 294 /* Converts the current loop closed SSA form to a canonical form 295 expected by the Graphite code generation. 296 297 The loop closed SSA form has the following invariant: a variable 298 defined in a loop that is used outside the loop appears only in the 299 phi nodes in the destination of the loop exit. These phi nodes are 300 called close phi nodes. 301 302 The canonical loop closed SSA form contains the extra invariants: 303 304 - when the loop contains only one exit, the close phi nodes contain 305 only one argument. That implies that the basic block that contains 306 the close phi nodes has only one predecessor, that is a basic block 307 in the loop. 308 309 - the basic block containing the close phi nodes does not contain 310 other statements. 311 312 - there exist only one phi node per definition in the loop. 313 314 In addition to that we also make sure that loop exit edges are 315 first in the successor edge vector. This is to make RPO order 316 as computed by pre_and_rev_post_order_compute be consistent with 317 what initial schedule generation expects. 318 */ 319 320 static void 321 canonicalize_loop_form (void) 322 { 323 loop_p loop; 324 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST) 325 { 326 edge e = single_exit (loop); 327 if (!e || (e->flags & (EDGE_COMPLEX|EDGE_FAKE))) 328 continue; 329 330 canonicalize_loop_closed_ssa (loop, e); 331 332 /* If the exit is not first in the edge vector make it so. */ 333 if (e != EDGE_SUCC (e->src, 0)) 334 { 335 unsigned ei; 336 for (ei = 0; EDGE_SUCC (e->src, ei) != e; ++ei) 337 ; 338 std::swap (EDGE_SUCC (e->src, ei), EDGE_SUCC (e->src, 0)); 339 } 340 } 341 342 /* We can end up releasing duplicate exit PHIs and also introduce 343 additional copies so the cached information isn't correct anymore. */ 344 scev_reset (); 345 346 checking_verify_loop_closed_ssa (true); 347 } 348 349 isl_ctx *the_isl_ctx; 350 351 /* Perform a set of linear transforms on the loops of the current 352 function. */ 353 354 void 355 graphite_transform_loops (void) 356 { 357 int i; 358 scop_p scop; 359 bool changed = false; 360 vec<scop_p> scops = vNULL; 361 isl_ctx *ctx; 362 363 /* If a function is parallel it was most probably already run through graphite 364 once. No need to run again. */ 365 if (parallelized_function_p (cfun->decl)) 366 return; 367 368 calculate_dominance_info (CDI_DOMINATORS); 369 370 /* We rely on post-dominators during merging of SESE regions so those 371 have to be meaningful. */ 372 connect_infinite_loops_to_exit (); 373 374 ctx = isl_ctx_alloc (); 375 isl_options_set_on_error (ctx, ISL_ON_ERROR_ABORT); 376 the_isl_ctx = ctx; 377 378 sort_sibling_loops (cfun); 379 canonicalize_loop_form (); 380 381 /* Print the loop structure. */ 382 if (dump_file && (dump_flags & TDF_DETAILS)) 383 { 384 print_loops (dump_file, 2); 385 print_loops (dump_file, 3); 386 } 387 388 calculate_dominance_info (CDI_POST_DOMINATORS); 389 build_scops (&scops); 390 free_dominance_info (CDI_POST_DOMINATORS); 391 392 /* Remove the fake exits before transform given they are not reflected 393 in loop structures we end up verifying. */ 394 remove_fake_exit_edges (); 395 396 if (dump_file && (dump_flags & TDF_DETAILS)) 397 { 398 print_graphite_statistics (dump_file, scops); 399 print_global_statistics (dump_file); 400 } 401 402 FOR_EACH_VEC_ELT (scops, i, scop) 403 if (dbg_cnt (graphite_scop)) 404 { 405 scop->isl_context = ctx; 406 if (!build_poly_scop (scop)) 407 continue; 408 409 if (!apply_poly_transforms (scop)) 410 continue; 411 412 changed = true; 413 if (graphite_regenerate_ast_isl (scop)) 414 { 415 location_t loc = find_loop_location 416 (scops[i]->scop_info->region.entry->dest->loop_father); 417 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc, 418 "loop nest optimized\n"); 419 } 420 } 421 422 if (changed) 423 { 424 mark_virtual_operands_for_renaming (cfun); 425 update_ssa (TODO_update_ssa); 426 checking_verify_ssa (true, true); 427 rewrite_into_loop_closed_ssa (NULL, 0); 428 scev_reset (); 429 checking_verify_loop_structure (); 430 } 431 432 if (dump_file && (dump_flags & TDF_DETAILS)) 433 { 434 loop_p loop; 435 int num_no_dependency = 0; 436 437 FOR_EACH_LOOP (loop, 0) 438 if (loop->can_be_parallel) 439 num_no_dependency++; 440 441 fprintf (dump_file, "%d loops carried no dependency.\n", 442 num_no_dependency); 443 } 444 445 free_scops (scops); 446 the_isl_ctx = NULL; 447 isl_ctx_free (ctx); 448 449 if (changed) 450 { 451 cleanup_tree_cfg (); 452 profile_status_for_fn (cfun) = PROFILE_ABSENT; 453 release_recorded_exits (cfun); 454 tree_estimate_probability (false); 455 } 456 } 457 458 #else /* If isl is not available: #ifndef HAVE_isl. */ 459 460 static void 461 graphite_transform_loops (void) 462 { 463 sorry ("Graphite loop optimizations cannot be used (isl is not available)."); 464 } 465 466 #endif 467 468 469 static unsigned int 470 graphite_transforms (struct function *fun) 471 { 472 if (number_of_loops (fun) <= 1) 473 return 0; 474 475 graphite_transform_loops (); 476 477 return 0; 478 } 479 480 static bool 481 gate_graphite_transforms (void) 482 { 483 /* Enable -fgraphite pass if any one of the graphite optimization flags 484 is turned on. */ 485 if (flag_graphite_identity 486 || flag_loop_parallelize_all 487 || flag_loop_nest_optimize) 488 flag_graphite = 1; 489 490 return flag_graphite != 0; 491 } 492 493 namespace { 494 495 const pass_data pass_data_graphite = 496 { 497 GIMPLE_PASS, /* type */ 498 "graphite0", /* name */ 499 OPTGROUP_LOOP, /* optinfo_flags */ 500 TV_GRAPHITE, /* tv_id */ 501 ( PROP_cfg | PROP_ssa ), /* properties_required */ 502 0, /* properties_provided */ 503 0, /* properties_destroyed */ 504 0, /* todo_flags_start */ 505 0, /* todo_flags_finish */ 506 }; 507 508 class pass_graphite : public gimple_opt_pass 509 { 510 public: 511 pass_graphite (gcc::context *ctxt) 512 : gimple_opt_pass (pass_data_graphite, ctxt) 513 {} 514 515 /* opt_pass methods: */ 516 virtual bool gate (function *) { return gate_graphite_transforms (); } 517 518 }; // class pass_graphite 519 520 } // anon namespace 521 522 gimple_opt_pass * 523 make_pass_graphite (gcc::context *ctxt) 524 { 525 return new pass_graphite (ctxt); 526 } 527 528 namespace { 529 530 const pass_data pass_data_graphite_transforms = 531 { 532 GIMPLE_PASS, /* type */ 533 "graphite", /* name */ 534 OPTGROUP_LOOP, /* optinfo_flags */ 535 TV_GRAPHITE_TRANSFORMS, /* tv_id */ 536 ( PROP_cfg | PROP_ssa ), /* properties_required */ 537 0, /* properties_provided */ 538 0, /* properties_destroyed */ 539 0, /* todo_flags_start */ 540 0, /* todo_flags_finish */ 541 }; 542 543 class pass_graphite_transforms : public gimple_opt_pass 544 { 545 public: 546 pass_graphite_transforms (gcc::context *ctxt) 547 : gimple_opt_pass (pass_data_graphite_transforms, ctxt) 548 {} 549 550 /* opt_pass methods: */ 551 virtual bool gate (function *) { return gate_graphite_transforms (); } 552 virtual unsigned int execute (function *fun) { return graphite_transforms (fun); } 553 554 }; // class pass_graphite_transforms 555 556 } // anon namespace 557 558 gimple_opt_pass * 559 make_pass_graphite_transforms (gcc::context *ctxt) 560 { 561 return new pass_graphite_transforms (ctxt); 562 } 563 564 565