gcc/sese.c

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008-2017 Free Software Foundation, Inc.
   3    Contributed by Jan Sjodin <jan.sjodin@amd.com> and
   4    Sebastian Pop <sebastian.pop@amd.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "backend.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "cfghooks.h"
  29 #include "tree-pass.h"
  30 #include "ssa.h"
  31 #include "tree-pretty-print.h"
  32 #include "fold-const.h"
  33 #include "gimplify.h"
  34 #include "gimple-iterator.h"
  35 #include "gimple-pretty-print.h"
  36 #include "gimplify-me.h"
  37 #include "tree-cfg.h"
  38 #include "tree-ssa-loop.h"
  39 #include "tree-into-ssa.h"
  40 #include "cfgloop.h"
  41 #include "tree-data-ref.h"
  42 #include "tree-scalar-evolution.h"
  43 #include "tree-ssa-propagate.h"
  44 #include "cfganal.h"
  45 #include "sese.h"
  46
  47 /* For a USE in BB, if BB is outside REGION, mark the USE in the
  48    LIVEOUTS set.  */
  49
  50 static void
  51 sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
  52                          tree use)
  53 {
  54   gcc_assert (!bb_in_sese_p (bb, region->region));
  55   if (TREE_CODE (use) != SSA_NAME)
  56     return;
  57
  58   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
  59
  60   if (!def_bb || !bb_in_sese_p (def_bb, region->region))
  61     return;
  62
  63   unsigned ver = SSA_NAME_VERSION (use);
  64   bitmap_set_bit (liveouts, ver);
  65 }
  66
  67 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
  68    used in BB that is outside of the REGION.  */
  69
  70 static void
  71 sese_build_liveouts_bb (sese_info_p region, basic_block bb)
  72 {
  73   ssa_op_iter iter;
  74   use_operand_p use_p;
  75
  76   for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
  77        gsi_next (&bsi))
  78     FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
  79       sese_build_liveouts_use (region, region->liveout,
  80                                bb, USE_FROM_PTR (use_p));
  81
  82   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
  83        gsi_next (&bsi))
  84     {
  85       gimple *stmt = gsi_stmt (bsi);
  86
  87       bitmap liveouts = region->liveout;
  88       if (is_gimple_debug (stmt))
  89         liveouts = region->debug_liveout;
  90
  91       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
  92         sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
  93     }
  94 }
  95
  96 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
  97    are not marked as liveouts.  */
  98
  99 static void
 100 sese_reset_debug_liveouts (sese_info_p region)
 101 {
 102   bitmap_iterator bi;
 103   unsigned i;
 104   EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout,
 105                                   0, i, bi)
 106     {
 107       tree name = ssa_name (i);
 108       auto_vec<gimple *, 4> stmts;
 109       gimple *use_stmt;
 110       imm_use_iterator use_iter;
 111       FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
 112         {
 113           if (! is_gimple_debug (use_stmt)
 114               || bb_in_sese_p (gimple_bb (use_stmt), region->region))
 115             continue;
 116           stmts.safe_push (use_stmt);
 117         }
 118       while (!stmts.is_empty ())
 119         {
 120           gimple *stmt = stmts.pop ();
 121           gimple_debug_bind_reset_value (stmt);
 122           update_stmt (stmt);
 123         }
 124     }
 125 }
 126
 127 /* Build the LIVEOUTS of REGION: the set of variables defined inside
 128    and used outside the REGION.  */
 129
 130 void
 131 sese_build_liveouts (sese_info_p region)
 132 {
 133   basic_block bb;
 134
 135   gcc_assert (region->liveout == NULL
 136               && region->debug_liveout == NULL);
 137
 138   region->liveout = BITMAP_ALLOC (NULL);
 139   region->debug_liveout = BITMAP_ALLOC (NULL);
 140
 141   /* FIXME: We could start iterating form the successor of sese.  */
 142   FOR_EACH_BB_FN (bb, cfun)
 143     if (!bb_in_sese_p (bb, region->region))
 144       sese_build_liveouts_bb (region, bb);
 145 }
 146
 147 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 148
 149 sese_info_p
 150 new_sese_info (edge entry, edge exit)
 151 {
 152   sese_info_p region = XNEW (struct sese_info_t);
 153
 154   region->region.entry = entry;
 155   region->region.exit = exit;
 156   region->liveout = NULL;
 157   region->debug_liveout = NULL;
 158   region->params.create (3);
 159   region->rename_map = new rename_map_t;
 160   region->parameter_rename_map = new parameter_rename_map_t;
 161   region->copied_bb_map = new bb_map_t;
 162   region->bbs.create (3);
 163   region->incomplete_phis.create (3);
 164
 165
 166   return region;
 167 }
 168
 169 /* Deletes REGION.  */
 170
 171 void
 172 free_sese_info (sese_info_p region)
 173 {
 174   region->params.release ();
 175   BITMAP_FREE (region->liveout);
 176   BITMAP_FREE (region->debug_liveout);
 177
 178   for (rename_map_t::iterator it = region->rename_map->begin ();
 179        it != region->rename_map->end (); ++it)
 180     (*it).second.release ();
 181
 182   for (bb_map_t::iterator it = region->copied_bb_map->begin ();
 183        it != region->copied_bb_map->end (); ++it)
 184     (*it).second.release ();
 185
 186   delete region->rename_map;
 187   delete region->parameter_rename_map;
 188   delete region->copied_bb_map;
 189
 190   region->rename_map = NULL;
 191   region->parameter_rename_map = NULL;
 192   region->copied_bb_map = NULL;
 193
 194   region->bbs.release ();
 195   region->incomplete_phis.release ();
 196
 197   XDELETE (region);
 198 }
 199
 200 /* Add exit phis for USE on EXIT.  */
 201
 202 static void
 203 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 204 {
 205   gphi *phi = create_phi_node (NULL_TREE, exit);
 206   create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
 207   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
 208   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
 209   update_stmt (phi);
 210 }
 211
 212 /* Insert in the block BB phi nodes for variables defined in REGION
 213    and used outside the REGION.  The code generation moves REGION in
 214    the else clause of an "if (1)" and generates code in the then
 215    clause that is at this point empty:
 216
 217    | if (1)
 218    |   empty;
 219    | else
 220    |   REGION;
 221 */
 222
 223 void
 224 sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
 225                                edge false_e, edge true_e)
 226 {
 227   if (MAY_HAVE_DEBUG_STMTS)
 228     sese_reset_debug_liveouts (region);
 229
 230   unsigned i;
 231   bitmap_iterator bi;
 232   EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
 233     if (!virtual_operand_p (ssa_name (i)))
 234       sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 235 }
 236
 237 /* Returns the outermost loop in SCOP that contains BB.  */
 238
 239 struct loop *
 240 outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
 241 {
 242   struct loop *nest;
 243
 244   nest = bb->loop_father;
 245   while (loop_outer (nest)
 246          && loop_in_sese_p (loop_outer (nest), region))
 247     nest = loop_outer (nest);
 248
 249   return nest;
 250 }
 251
 252 /* Same as outermost_loop_in_sese_1, returns the outermost loop
 253    containing BB in REGION, but makes sure that the returned loop
 254    belongs to the REGION, and so this returns the first loop in the
 255    REGION when the loop containing BB does not belong to REGION.  */
 256
 257 loop_p
 258 outermost_loop_in_sese (sese_l &region, basic_block bb)
 259 {
 260   loop_p nest = outermost_loop_in_sese_1 (region, bb);
 261
 262   if (loop_in_sese_p (nest, region))
 263     return nest;
 264
 265   /* When the basic block BB does not belong to a loop in the region,
 266      return the first loop in the region.  */
 267   nest = nest->inner;
 268   while (nest)
 269     if (loop_in_sese_p (nest, region))
 270       break;
 271     else
 272       nest = nest->next;
 273
 274   gcc_assert (nest);
 275   return nest;
 276 }
 277
 278 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 279
 280 edge
 281 get_true_edge_from_guard_bb (basic_block bb)
 282 {
 283   edge e;
 284   edge_iterator ei;
 285
 286   FOR_EACH_EDGE (e, ei, bb->succs)
 287     if (e->flags & EDGE_TRUE_VALUE)
 288       return e;
 289
 290   gcc_unreachable ();
 291   return NULL;
 292 }
 293
 294 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 295
 296 edge
 297 get_false_edge_from_guard_bb (basic_block bb)
 298 {
 299   edge e;
 300   edge_iterator ei;
 301
 302   FOR_EACH_EDGE (e, ei, bb->succs)
 303     if (!(e->flags & EDGE_TRUE_VALUE))
 304       return e;
 305
 306   gcc_unreachable ();
 307   return NULL;
 308 }
 309
 310 /* Moves REGION in a condition expression:
 311    | if (1)
 312    |   ;
 313    | else
 314    |   REGION;
 315 */
 316
 317 ifsese
 318 move_sese_in_condition (sese_info_p region)
 319 {
 320   basic_block region_entry_dest = region->region.entry->dest;
 321   basic_block pred_block = split_edge (region->region.entry);
 322   basic_block merge_block = split_edge (region->region.exit);
 323
 324   edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
 325   edge false_edge = find_edge (pred_block, region_entry_dest);
 326   false_edge->flags &= ~EDGE_FALLTHRU;
 327   false_edge->flags |= EDGE_FALSE_VALUE;
 328   gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
 329   gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
 330                                    NULL_TREE, NULL_TREE);
 331   gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
 332   if (dom_info_available_p (CDI_DOMINATORS))
 333     set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
 334
 335   ifsese if_region = XNEW (ifsese_s);
 336   if_region->region = XCNEW (sese_info_t);
 337   if_region->true_region = XCNEW (sese_info_t);
 338   if_region->false_region = XCNEW (sese_info_t);
 339   if_region->region->region.entry = single_pred_edge (pred_block);
 340   if_region->region->region.exit = single_succ_edge (merge_block);
 341   if_region->false_region->region.entry = false_edge;
 342   if_region->false_region->region.exit = region->region.exit;
 343   if_region->true_region->region.entry = true_edge;
 344   if_region->true_region->region.exit
 345     = single_succ_edge (split_edge (true_edge));
 346
 347   region->region = if_region->false_region->region;
 348
 349   return if_region;
 350 }
 351
 352 /* Replaces the condition of the IF_REGION with CONDITION:
 353    | if (CONDITION)
 354    |   true_region;
 355    | else
 356    |   false_region;
 357 */
 358
 359 void
 360 set_ifsese_condition (ifsese if_region, tree condition)
 361 {
 362   sese_info_p region = if_region->region;
 363   edge entry = region->region.entry;
 364   basic_block bb = entry->dest;
 365   gimple *last = last_stmt (bb);
 366   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 367   gcond *cond_stmt;
 368
 369   gcc_assert (gimple_code (last) == GIMPLE_COND);
 370
 371   gsi_remove (&gsi, true);
 372   gsi = gsi_last_bb (bb);
 373   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 374                                         false, GSI_NEW_STMT);
 375   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 376   gsi = gsi_last_bb (bb);
 377   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 378 }
 379
 380 /* Return true when T is defined outside REGION or when no definitions are
 381    variant in REGION.  When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
 382    when T depends on memory that may change in REGION.  */
 383
 384 bool
 385 invariant_in_sese_p_rec (tree t, const sese_l &region, bool *has_vdefs)
 386 {
 387   if (!defined_in_sese_p (t, region))
 388     return true;
 389
 390   gimple *stmt = SSA_NAME_DEF_STMT (t);
 391
 392   if (gimple_code (stmt) == GIMPLE_PHI
 393       || gimple_code (stmt) == GIMPLE_CALL)
 394     return false;
 395
 396   /* VDEF is variant when it is in the region.  */
 397   if (gimple_vdef (stmt))
 398     {
 399       if (has_vdefs)
 400         *has_vdefs = true;
 401       return false;
 402     }
 403
 404   /* A VUSE may or may not be variant following the VDEFs.  */
 405   if (tree vuse = gimple_vuse (stmt))
 406     return invariant_in_sese_p_rec (vuse, region, has_vdefs);
 407
 408   ssa_op_iter iter;
 409   use_operand_p use_p;
 410   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 411     {
 412       tree use = USE_FROM_PTR (use_p);
 413
 414       if (!defined_in_sese_p (use, region))
 415         continue;
 416
 417       if (!invariant_in_sese_p_rec (use, region, has_vdefs))
 418         return false;
 419     }
 420
 421   return true;
 422 }
 423
 424 /* Return true when DEF can be analyzed in REGION by the scalar
 425    evolution analyzer.  */
 426
 427 bool
 428 scev_analyzable_p (tree def, sese_l &region)
 429 {
 430   loop_p loop;
 431   tree scev;
 432   tree type = TREE_TYPE (def);
 433
 434   /* When Graphite generates code for a scev, the code generator
 435      expresses the scev in function of a single induction variable.
 436      This is unsafe for floating point computations, as it may replace
 437      a floating point sum reduction with a multiplication.  The
 438      following test returns false for non integer types to avoid such
 439      problems.  */
 440   if (!INTEGRAL_TYPE_P (type)
 441       && !POINTER_TYPE_P (type))
 442     return false;
 443
 444   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
 445   scev = scalar_evolution_in_region (region, loop, def);
 446
 447   return (!chrec_contains_undetermined (scev)
 448           && (TREE_CODE (scev) != SSA_NAME
 449               || !defined_in_sese_p (scev, region))
 450           && scev_is_linear_expression (scev)
 451           && (! loop
 452               || ! loop_in_sese_p (loop, region)
 453               || ! chrec_contains_symbols_defined_in_loop (scev, loop->num)));
 454 }
 455
 456 /* Returns the scalar evolution of T in REGION.  Every variable that
 457    is not defined in the REGION is considered a parameter.  */
 458
 459 tree
 460 scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
 461 {
 462   gimple *def;
 463   struct loop *def_loop;
 464
 465   /* SCOP parameters.  */
 466   if (TREE_CODE (t) == SSA_NAME
 467       && !defined_in_sese_p (t, region))
 468     return t;
 469
 470   if (TREE_CODE (t) != SSA_NAME
 471       || loop_in_sese_p (loop, region))
 472     /* FIXME: we would need instantiate SCEV to work on a region, and be more
 473        flexible wrt. memory loads that may be invariant in the region.  */
 474     return instantiate_scev (region.entry, loop,
 475                              analyze_scalar_evolution (loop, t));
 476
 477   def = SSA_NAME_DEF_STMT (t);
 478   def_loop = loop_containing_stmt (def);
 479
 480   if (loop_in_sese_p (def_loop, region))
 481     {
 482       t = analyze_scalar_evolution (def_loop, t);
 483       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 484       t = compute_overall_effect_of_inner_loop (def_loop, t);
 485       return t;
 486     }
 487
 488   bool has_vdefs = false;
 489   if (invariant_in_sese_p_rec (t, region, &has_vdefs))
 490     return t;
 491
 492   /* T variates in REGION.  */
 493   if (has_vdefs)
 494     return chrec_dont_know;
 495
 496   return instantiate_scev (region.entry, loop, t);
 497 }
 498
 499 /* Return true if BB is empty, contains only DEBUG_INSNs.  */
 500
 501 bool
 502 sese_trivially_empty_bb_p (basic_block bb)
 503 {
 504   gimple_stmt_iterator gsi;
 505
 506   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 507     if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG
 508         && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
 509       return false;
 510
 511   return true;
 512 }
 513
 514 /* Pretty print edge E to FILE.  */
 515
 516 void
 517 print_edge (FILE *file, const_edge e)
 518 {
 519   fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
 520 }
 521
 522 /* Pretty print sese S to FILE.  */
 523
 524 void
 525 print_sese (FILE *file, const sese_l &s)
 526 {
 527   fprintf (file, "(entry_"); print_edge (file, s.entry);
 528   fprintf (file, ", exit_"); print_edge (file, s.exit);
 529   fprintf (file, ")\n");
 530 }
 531
 532 /* Pretty print edge E to STDERR.  */
 533
 534 DEBUG_FUNCTION void
 535 debug_edge (const_edge e)
 536 {
 537   print_edge (stderr, e);
 538 }
 539
 540 /* Pretty print sese S to STDERR.  */
 541
 542 DEBUG_FUNCTION void
 543 debug_sese (const sese_l &s)
 544 {
 545   print_sese (stderr, s);
 546 }