gcc/graphite.c

   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