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