gcc/sese.c

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008-2018 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 hash_map <tree, tree>;
 160   region->bbs.create (3);
 161
 162   return region;
 163 }
 164
 165 /* Deletes REGION.  */
 166
 167 void
 168 free_sese_info (sese_info_p region)
 169 {
 170   region->params.release ();
 171   BITMAP_FREE (region->liveout);
 172   BITMAP_FREE (region->debug_liveout);
 173
 174   delete region->rename_map;
 175   region->rename_map = NULL;
 176   region->bbs.release ();
 177
 178   XDELETE (region);
 179 }
 180
 181 /* Add exit phis for USE on EXIT.  */
 182
 183 static void
 184 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 185 {
 186   gphi *phi = create_phi_node (NULL_TREE, exit);
 187   create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
 188   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
 189   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
 190   update_stmt (phi);
 191 }
 192
 193 /* Insert in the block BB phi nodes for variables defined in REGION
 194    and used outside the REGION.  The code generation moves REGION in
 195    the else clause of an "if (1)" and generates code in the then
 196    clause that is at this point empty:
 197
 198    | if (1)
 199    |   empty;
 200    | else
 201    |   REGION;
 202 */
 203
 204 void
 205 sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
 206                                edge false_e, edge true_e)
 207 {
 208   if (MAY_HAVE_DEBUG_BIND_STMTS)
 209     sese_reset_debug_liveouts (region);
 210
 211   unsigned i;
 212   bitmap_iterator bi;
 213   EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
 214     if (!virtual_operand_p (ssa_name (i)))
 215       sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 216 }
 217
 218 /* Returns the outermost loop in SCOP that contains BB.  */
 219
 220 struct loop *
 221 outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
 222 {
 223   struct loop *nest;
 224
 225   nest = bb->loop_father;
 226   while (loop_outer (nest)
 227          && loop_in_sese_p (loop_outer (nest), region))
 228     nest = loop_outer (nest);
 229
 230   return nest;
 231 }
 232
 233 /* Same as outermost_loop_in_sese_1, returns the outermost loop
 234    containing BB in REGION, but makes sure that the returned loop
 235    belongs to the REGION, and so this returns the first loop in the
 236    REGION when the loop containing BB does not belong to REGION.  */
 237
 238 loop_p
 239 outermost_loop_in_sese (sese_l &region, basic_block bb)
 240 {
 241   loop_p nest = outermost_loop_in_sese_1 (region, bb);
 242
 243   if (loop_in_sese_p (nest, region))
 244     return nest;
 245
 246   /* When the basic block BB does not belong to a loop in the region,
 247      return the first loop in the region.  */
 248   nest = nest->inner;
 249   while (nest)
 250     if (loop_in_sese_p (nest, region))
 251       break;
 252     else
 253       nest = nest->next;
 254
 255   gcc_assert (nest);
 256   return nest;
 257 }
 258
 259 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 260
 261 edge
 262 get_true_edge_from_guard_bb (basic_block bb)
 263 {
 264   edge e;
 265   edge_iterator ei;
 266
 267   FOR_EACH_EDGE (e, ei, bb->succs)
 268     if (e->flags & EDGE_TRUE_VALUE)
 269       return e;
 270
 271   gcc_unreachable ();
 272   return NULL;
 273 }
 274
 275 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 276
 277 edge
 278 get_false_edge_from_guard_bb (basic_block bb)
 279 {
 280   edge e;
 281   edge_iterator ei;
 282
 283   FOR_EACH_EDGE (e, ei, bb->succs)
 284     if (!(e->flags & EDGE_TRUE_VALUE))
 285       return e;
 286
 287   gcc_unreachable ();
 288   return NULL;
 289 }
 290
 291 /* Moves REGION in a condition expression:
 292    | if (1)
 293    |   ;
 294    | else
 295    |   REGION;
 296 */
 297
 298 ifsese
 299 move_sese_in_condition (sese_info_p region)
 300 {
 301   basic_block region_entry_dest = region->region.entry->dest;
 302   basic_block pred_block = split_edge (region->region.entry);
 303   basic_block merge_block = split_edge (region->region.exit);
 304
 305   edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
 306   edge false_edge = find_edge (pred_block, region_entry_dest);
 307   false_edge->flags &= ~EDGE_FALLTHRU;
 308   false_edge->flags |= EDGE_FALSE_VALUE;
 309   gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
 310   gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
 311                                    NULL_TREE, NULL_TREE);
 312   gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
 313   if (dom_info_available_p (CDI_DOMINATORS))
 314     set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
 315
 316   ifsese if_region = XNEW (ifsese_s);
 317   if_region->region = XCNEW (sese_info_t);
 318   if_region->true_region = XCNEW (sese_info_t);
 319   if_region->false_region = XCNEW (sese_info_t);
 320   if_region->region->region.entry = single_pred_edge (pred_block);
 321   if_region->region->region.exit = single_succ_edge (merge_block);
 322   if_region->false_region->region.entry = false_edge;
 323   if_region->false_region->region.exit = region->region.exit;
 324   if_region->true_region->region.entry = true_edge;
 325   if_region->true_region->region.exit
 326     = single_succ_edge (split_edge (true_edge));
 327
 328   region->region = if_region->false_region->region;
 329
 330   return if_region;
 331 }
 332
 333 /* Replaces the condition of the IF_REGION with CONDITION:
 334    | if (CONDITION)
 335    |   true_region;
 336    | else
 337    |   false_region;
 338 */
 339
 340 void
 341 set_ifsese_condition (ifsese if_region, tree condition)
 342 {
 343   sese_info_p region = if_region->region;
 344   edge entry = region->region.entry;
 345   basic_block bb = entry->dest;
 346   gimple *last = last_stmt (bb);
 347   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 348   gcond *cond_stmt;
 349
 350   gcc_assert (gimple_code (last) == GIMPLE_COND);
 351
 352   gsi_remove (&gsi, true);
 353   gsi = gsi_last_bb (bb);
 354   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 355                                         false, GSI_NEW_STMT);
 356   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 357   gsi = gsi_last_bb (bb);
 358   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 359 }
 360
 361 /* Return true when T is defined outside REGION or when no definitions are
 362    variant in REGION.  When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
 363    when T depends on memory that may change in REGION.  */
 364
 365 bool
 366 invariant_in_sese_p_rec (tree t, const sese_l &region, bool *has_vdefs)
 367 {
 368   if (!defined_in_sese_p (t, region))
 369     return true;
 370
 371   gimple *stmt = SSA_NAME_DEF_STMT (t);
 372
 373   if (gimple_code (stmt) == GIMPLE_PHI
 374       || gimple_code (stmt) == GIMPLE_CALL)
 375     return false;
 376
 377   /* VDEF is variant when it is in the region.  */
 378   if (gimple_vdef (stmt))
 379     {
 380       if (has_vdefs)
 381         *has_vdefs = true;
 382       return false;
 383     }
 384
 385   /* A VUSE may or may not be variant following the VDEFs.  */
 386   if (tree vuse = gimple_vuse (stmt))
 387     return invariant_in_sese_p_rec (vuse, region, has_vdefs);
 388
 389   ssa_op_iter iter;
 390   use_operand_p use_p;
 391   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 392     {
 393       tree use = USE_FROM_PTR (use_p);
 394
 395       if (!defined_in_sese_p (use, region))
 396         continue;
 397
 398       if (!invariant_in_sese_p_rec (use, region, has_vdefs))
 399         return false;
 400     }
 401
 402   return true;
 403 }
 404
 405 /* Return true when DEF can be analyzed in REGION by the scalar
 406    evolution analyzer.  */
 407
 408 bool
 409 scev_analyzable_p (tree def, sese_l &region)
 410 {
 411   loop_p loop;
 412   tree scev;
 413   tree type = TREE_TYPE (def);
 414
 415   /* When Graphite generates code for a scev, the code generator
 416      expresses the scev in function of a single induction variable.
 417      This is unsafe for floating point computations, as it may replace
 418      a floating point sum reduction with a multiplication.  The
 419      following test returns false for non integer types to avoid such
 420      problems.  */
 421   if (!INTEGRAL_TYPE_P (type)
 422       && !POINTER_TYPE_P (type))
 423     return false;
 424
 425   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
 426   scev = scalar_evolution_in_region (region, loop, def);
 427
 428   return (!chrec_contains_undetermined (scev)
 429           && (TREE_CODE (scev) != SSA_NAME
 430               || !defined_in_sese_p (scev, region))
 431           && scev_is_linear_expression (scev)
 432           && (! loop
 433               || ! loop_in_sese_p (loop, region)
 434               || ! chrec_contains_symbols_defined_in_loop (scev, loop->num)));
 435 }
 436
 437 /* Returns the scalar evolution of T in REGION.  Every variable that
 438    is not defined in the REGION is considered a parameter.  */
 439
 440 tree
 441 scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
 442 {
 443   /* SCOP parameters.  */
 444   if (TREE_CODE (t) == SSA_NAME
 445       && !defined_in_sese_p (t, region))
 446     return t;
 447
 448   if (!loop_in_sese_p (loop, region))
 449     loop = NULL;
 450
 451   return instantiate_scev (region.entry, loop,
 452                            analyze_scalar_evolution (loop, t));
 453 }
 454
 455 /* Return true if BB is empty, contains only DEBUG_INSNs.  */
 456
 457 bool
 458 sese_trivially_empty_bb_p (basic_block bb)
 459 {
 460   gimple_stmt_iterator gsi;
 461
 462   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 463     if (!is_gimple_debug (gsi_stmt (gsi))
 464         && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
 465       return false;
 466
 467   return true;
 468 }
 469
 470 /* Pretty print edge E to FILE.  */
 471
 472 void
 473 print_edge (FILE *file, const_edge e)
 474 {
 475   fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
 476 }
 477
 478 /* Pretty print sese S to FILE.  */
 479
 480 void
 481 print_sese (FILE *file, const sese_l &s)
 482 {
 483   fprintf (file, "(entry_"); print_edge (file, s.entry);
 484   fprintf (file, ", exit_"); print_edge (file, s.exit);
 485   fprintf (file, ")\n");
 486 }
 487
 488 /* Pretty print edge E to STDERR.  */
 489
 490 DEBUG_FUNCTION void
 491 debug_edge (const_edge e)
 492 {
 493   print_edge (stderr, e);
 494 }
 495
 496 /* Pretty print sese S to STDERR.  */
 497
 498 DEBUG_FUNCTION void
 499 debug_sese (const sese_l &s)
 500 {
 501   print_sese (stderr, s);
 502 }