gcc/sese.c

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008-2016 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 "sese.h"
  44 #include "tree-ssa-propagate.h"
  45
  46 /* For a USE in BB, if BB is outside REGION, mark the USE in the
  47    LIVEOUTS set.  */
  48
  49 static void
  50 sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
  51                          tree use)
  52 {
  53   gcc_assert (!bb_in_sese_p (bb, region->region));
  54   if (TREE_CODE (use) != SSA_NAME)
  55     return;
  56
  57   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
  58
  59   if (!def_bb || !bb_in_sese_p (def_bb, region->region))
  60     return;
  61
  62   unsigned ver = SSA_NAME_VERSION (use);
  63   bitmap_set_bit (liveouts, ver);
  64 }
  65
  66 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
  67    used in BB that is outside of the REGION.  */
  68
  69 static void
  70 sese_build_liveouts_bb (sese_info_p region, bitmap liveouts, basic_block bb)
  71 {
  72   edge e;
  73   edge_iterator ei;
  74   ssa_op_iter iter;
  75   use_operand_p use_p;
  76
  77   FOR_EACH_EDGE (e, ei, bb->succs)
  78     for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
  79          gsi_next (&bsi))
  80       sese_build_liveouts_use (region, liveouts, bb,
  81                                PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e));
  82
  83   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
  84        gsi_next (&bsi))
  85     {
  86       gimple *stmt = gsi_stmt (bsi);
  87
  88       if (is_gimple_debug (stmt))
  89         continue;
  90
  91       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
  92         sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
  93     }
  94 }
  95
  96 /* For a USE in BB, return true if BB is outside REGION and it's not
  97    in the LIVEOUTS set.  */
  98
  99 static bool
 100 sese_bad_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
 101                        tree use)
 102 {
 103   gcc_assert (!bb_in_sese_p (bb, region->region));
 104
 105   if (TREE_CODE (use) != SSA_NAME)
 106     return false;
 107
 108   unsigned ver = SSA_NAME_VERSION (use);
 109
 110   /* If it's in liveouts, the variable will get a new PHI node, and
 111      the debug use will be properly adjusted.  */
 112   if (bitmap_bit_p (liveouts, ver))
 113     return false;
 114
 115   basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 116
 117   if (!def_bb || !bb_in_sese_p (def_bb, region->region))
 118     return false;
 119
 120   return true;
 121 }
 122
 123 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
 124    are not marked as liveouts.  */
 125
 126 static void
 127 sese_reset_debug_liveouts_bb (sese_info_p region, bitmap liveouts,
 128                               basic_block bb)
 129 {
 130   gimple_stmt_iterator bsi;
 131   ssa_op_iter iter;
 132   use_operand_p use_p;
 133
 134   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 135     {
 136       gimple *stmt = gsi_stmt (bsi);
 137
 138       if (!is_gimple_debug (stmt))
 139         continue;
 140
 141       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 142         if (sese_bad_liveouts_use (region, liveouts, bb,
 143                                    USE_FROM_PTR (use_p)))
 144           {
 145             gimple_debug_bind_reset_value (stmt);
 146             update_stmt (stmt);
 147             break;
 148           }
 149     }
 150 }
 151
 152 /* Build the LIVEOUTS of REGION: the set of variables defined inside
 153    and used outside the REGION.  */
 154
 155 static void
 156 sese_build_liveouts (sese_info_p region, bitmap liveouts)
 157 {
 158   basic_block bb;
 159
 160   /* FIXME: We could start iterating form the successor of sese.  */
 161   FOR_EACH_BB_FN (bb, cfun)
 162     if (!bb_in_sese_p (bb, region->region))
 163       sese_build_liveouts_bb (region, liveouts, bb);
 164
 165   /* FIXME: We could start iterating form the successor of sese.  */
 166   if (MAY_HAVE_DEBUG_STMTS)
 167     FOR_EACH_BB_FN (bb, cfun)
 168       if (!bb_in_sese_p (bb, region->region))
 169         sese_reset_debug_liveouts_bb (region, liveouts, bb);
 170 }
 171
 172 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 173
 174 sese_info_p
 175 new_sese_info (edge entry, edge exit)
 176 {
 177   sese_info_p region = XNEW (struct sese_info_t);
 178
 179   region->region.entry = entry;
 180   region->region.exit = exit;
 181   region->loop_nest.create (3);
 182   region->params.create (3);
 183   region->rename_map = new rename_map_t;
 184   region->copied_bb_map = new bb_map_t;
 185   region->bbs.create (3);
 186   region->incomplete_phis.create (3);
 187
 188   return region;
 189 }
 190
 191 /* Deletes REGION.  */
 192
 193 void
 194 free_sese_info (sese_info_p region)
 195 {
 196   region->params.release ();
 197   region->loop_nest.release ();
 198
 199   for (rename_map_t::iterator it = region->rename_map->begin ();
 200        it != region->rename_map->begin (); ++it)
 201     (*it).second.release ();
 202
 203   for (bb_map_t::iterator it = region->copied_bb_map->begin ();
 204        it != region->copied_bb_map->begin (); ++it)
 205     (*it).second.release ();
 206
 207   delete region->rename_map;
 208   delete region->copied_bb_map;
 209
 210   region->rename_map = NULL;
 211   region->copied_bb_map = NULL;
 212
 213   region->bbs.release ();
 214   region->incomplete_phis.release ();
 215
 216   XDELETE (region);
 217 }
 218
 219 /* Add exit phis for USE on EXIT.  */
 220
 221 static void
 222 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 223 {
 224   gphi *phi = create_phi_node (NULL_TREE, exit);
 225   create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
 226   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
 227   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
 228   update_stmt (phi);
 229 }
 230
 231 /* Insert in the block BB phi nodes for variables defined in REGION
 232    and used outside the REGION.  The code generation moves REGION in
 233    the else clause of an "if (1)" and generates code in the then
 234    clause that is at this point empty:
 235
 236    | if (1)
 237    |   empty;
 238    | else
 239    |   REGION;
 240 */
 241
 242 void
 243 sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
 244                                edge false_e, edge true_e)
 245 {
 246   unsigned i;
 247   bitmap_iterator bi;
 248   bitmap liveouts = BITMAP_ALLOC (NULL);
 249
 250   sese_build_liveouts (region, liveouts);
 251
 252   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
 253     if (!virtual_operand_p (ssa_name (i)))
 254       sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 255
 256   BITMAP_FREE (liveouts);
 257 }
 258
 259 /* Returns the outermost loop in SCOP that contains BB.  */
 260
 261 struct loop *
 262 outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
 263 {
 264   struct loop *nest;
 265
 266   nest = bb->loop_father;
 267   while (loop_outer (nest)
 268          && loop_in_sese_p (loop_outer (nest), region))
 269     nest = loop_outer (nest);
 270
 271   return nest;
 272 }
 273
 274 /* Same as outermost_loop_in_sese_1, returns the outermost loop
 275    containing BB in REGION, but makes sure that the returned loop
 276    belongs to the REGION, and so this returns the first loop in the
 277    REGION when the loop containing BB does not belong to REGION.  */
 278
 279 loop_p
 280 outermost_loop_in_sese (sese_l &region, basic_block bb)
 281 {
 282   loop_p nest = outermost_loop_in_sese_1 (region, bb);
 283
 284   if (loop_in_sese_p (nest, region))
 285     return nest;
 286
 287   /* When the basic block BB does not belong to a loop in the region,
 288      return the first loop in the region.  */
 289   nest = nest->inner;
 290   while (nest)
 291     if (loop_in_sese_p (nest, region))
 292       break;
 293     else
 294       nest = nest->next;
 295
 296   gcc_assert (nest);
 297   return nest;
 298 }
 299
 300 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 301
 302 edge
 303 get_true_edge_from_guard_bb (basic_block bb)
 304 {
 305   edge e;
 306   edge_iterator ei;
 307
 308   FOR_EACH_EDGE (e, ei, bb->succs)
 309     if (e->flags & EDGE_TRUE_VALUE)
 310       return e;
 311
 312   gcc_unreachable ();
 313   return NULL;
 314 }
 315
 316 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 317
 318 edge
 319 get_false_edge_from_guard_bb (basic_block bb)
 320 {
 321   edge e;
 322   edge_iterator ei;
 323
 324   FOR_EACH_EDGE (e, ei, bb->succs)
 325     if (!(e->flags & EDGE_TRUE_VALUE))
 326       return e;
 327
 328   gcc_unreachable ();
 329   return NULL;
 330 }
 331
 332 /* Sets the false region of an IF_REGION to REGION.  */
 333
 334 void
 335 if_region_set_false_region (ifsese if_region, sese_info_p region)
 336 {
 337   basic_block condition = if_region_get_condition_block (if_region);
 338   edge false_edge = get_false_edge_from_guard_bb (condition);
 339   basic_block dummy = false_edge->dest;
 340   edge entry_region = region->region.entry;
 341   edge exit_region = region->region.exit;
 342   basic_block before_region = entry_region->src;
 343   basic_block last_in_region = exit_region->src;
 344   hashval_t hash = htab_hash_pointer (exit_region);
 345   loop_exit **slot
 346     = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT);
 347
 348   entry_region->flags = false_edge->flags;
 349   false_edge->flags = exit_region->flags;
 350
 351   redirect_edge_pred (entry_region, condition);
 352   redirect_edge_pred (exit_region, before_region);
 353   redirect_edge_pred (false_edge, last_in_region);
 354   redirect_edge_succ (false_edge, single_succ (dummy));
 355   delete_basic_block (dummy);
 356
 357   exit_region->flags = EDGE_FALLTHRU;
 358   recompute_all_dominators ();
 359
 360   region->region.exit = false_edge;
 361
 362   free (if_region->false_region);
 363   if_region->false_region = region;
 364
 365   if (slot)
 366     {
 367       struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> ();
 368
 369       memcpy (loop_exit, *((struct loop_exit **) slot),
 370               sizeof (struct loop_exit));
 371       current_loops->exits->clear_slot (slot);
 372
 373       hashval_t hash = htab_hash_pointer (false_edge);
 374       slot = current_loops->exits->find_slot_with_hash (false_edge, hash,
 375                                                         INSERT);
 376       loop_exit->e = false_edge;
 377       *slot = loop_exit;
 378       false_edge->src->loop_father->exits->next = loop_exit;
 379     }
 380 }
 381
 382 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
 383
 384 static ifsese
 385 create_if_region_on_edge (edge entry, tree condition)
 386 {
 387   edge e;
 388   edge_iterator ei;
 389   sese_info_p sese_region = XNEW (struct sese_info_t);
 390   sese_info_p true_region = XNEW (struct sese_info_t);
 391   sese_info_p false_region = XNEW (struct sese_info_t);
 392   ifsese if_region = XNEW (struct ifsese_s);
 393   edge exit = create_empty_if_region_on_edge (entry, condition);
 394
 395   if_region->region = sese_region;
 396   if_region->region->region.entry = entry;
 397   if_region->region->region.exit = exit;
 398
 399   FOR_EACH_EDGE (e, ei, entry->dest->succs)
 400     {
 401       if (e->flags & EDGE_TRUE_VALUE)
 402         {
 403           true_region->region.entry = e;
 404           true_region->region.exit = single_succ_edge (e->dest);
 405           if_region->true_region = true_region;
 406         }
 407       else if (e->flags & EDGE_FALSE_VALUE)
 408         {
 409           false_region->region.entry = e;
 410           false_region->region.exit = single_succ_edge (e->dest);
 411           if_region->false_region = false_region;
 412         }
 413     }
 414
 415   return if_region;
 416 }
 417
 418 /* Moves REGION in a condition expression:
 419    | if (1)
 420    |   ;
 421    | else
 422    |   REGION;
 423 */
 424
 425 ifsese
 426 move_sese_in_condition (sese_info_p region)
 427 {
 428   basic_block pred_block = split_edge (region->region.entry);
 429   ifsese if_region;
 430
 431   region->region.entry = single_succ_edge (pred_block);
 432   if_region = create_if_region_on_edge (single_pred_edge (pred_block),
 433                                         integer_one_node);
 434   if_region_set_false_region (if_region, region);
 435
 436   return if_region;
 437 }
 438
 439 /* Replaces the condition of the IF_REGION with CONDITION:
 440    | if (CONDITION)
 441    |   true_region;
 442    | else
 443    |   false_region;
 444 */
 445
 446 void
 447 set_ifsese_condition (ifsese if_region, tree condition)
 448 {
 449   sese_info_p region = if_region->region;
 450   edge entry = region->region.entry;
 451   basic_block bb = entry->dest;
 452   gimple *last = last_stmt (bb);
 453   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 454   gcond *cond_stmt;
 455
 456   gcc_assert (gimple_code (last) == GIMPLE_COND);
 457
 458   gsi_remove (&gsi, true);
 459   gsi = gsi_last_bb (bb);
 460   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 461                                         false, GSI_NEW_STMT);
 462   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 463   gsi = gsi_last_bb (bb);
 464   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 465 }
 466
 467 /* Return true when T is defined outside REGION or when no definitions are
 468    variant in REGION.  When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
 469    when T depends on memory that may change in REGION.  */
 470
 471 bool
 472 invariant_in_sese_p_rec (tree t, const sese_l &region, bool *has_vdefs)
 473 {
 474   if (!defined_in_sese_p (t, region))
 475     return true;
 476
 477   gimple *stmt = SSA_NAME_DEF_STMT (t);
 478
 479   if (gimple_code (stmt) == GIMPLE_PHI
 480       || gimple_code (stmt) == GIMPLE_CALL)
 481     return false;
 482
 483   /* VDEF is variant when it is in the region.  */
 484   if (gimple_vdef (stmt))
 485     {
 486       if (has_vdefs)
 487         *has_vdefs = true;
 488       return false;
 489     }
 490
 491   /* A VUSE may or may not be variant following the VDEFs.  */
 492   if (tree vuse = gimple_vuse (stmt))
 493     return invariant_in_sese_p_rec (vuse, region, has_vdefs);
 494
 495   ssa_op_iter iter;
 496   use_operand_p use_p;
 497   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 498     {
 499       tree use = USE_FROM_PTR (use_p);
 500
 501       if (!defined_in_sese_p (use, region))
 502         continue;
 503
 504       if (!invariant_in_sese_p_rec (use, region, has_vdefs))
 505         return false;
 506     }
 507
 508   return true;
 509 }
 510
 511 /* Return true when DEF can be analyzed in REGION by the scalar
 512    evolution analyzer.  */
 513
 514 bool
 515 scev_analyzable_p (tree def, sese_l &region)
 516 {
 517   loop_p loop;
 518   tree scev;
 519   tree type = TREE_TYPE (def);
 520
 521   /* When Graphite generates code for a scev, the code generator
 522      expresses the scev in function of a single induction variable.
 523      This is unsafe for floating point computations, as it may replace
 524      a floating point sum reduction with a multiplication.  The
 525      following test returns false for non integer types to avoid such
 526      problems.  */
 527   if (!INTEGRAL_TYPE_P (type)
 528       && !POINTER_TYPE_P (type))
 529     return false;
 530
 531   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
 532   scev = scalar_evolution_in_region (region, loop, def);
 533
 534   return !chrec_contains_undetermined (scev)
 535     && (TREE_CODE (scev) != SSA_NAME
 536         || !defined_in_sese_p (scev, region))
 537     && (tree_does_not_contain_chrecs (scev)
 538         || evolution_function_is_affine_p (scev));
 539 }
 540
 541 /* Returns the scalar evolution of T in REGION.  Every variable that
 542    is not defined in the REGION is considered a parameter.  */
 543
 544 tree
 545 scalar_evolution_in_region (const sese_l &region, loop_p loop, tree t)
 546 {
 547   gimple *def;
 548   struct loop *def_loop;
 549   basic_block before = region.entry->src;
 550
 551   /* SCOP parameters.  */
 552   if (TREE_CODE (t) == SSA_NAME
 553       && !defined_in_sese_p (t, region))
 554     return t;
 555
 556   if (TREE_CODE (t) != SSA_NAME
 557       || loop_in_sese_p (loop, region))
 558     /* FIXME: we would need instantiate SCEV to work on a region, and be more
 559        flexible wrt. memory loads that may be invariant in the region.  */
 560     return instantiate_scev (before, loop,
 561                              analyze_scalar_evolution (loop, t));
 562
 563   def = SSA_NAME_DEF_STMT (t);
 564   def_loop = loop_containing_stmt (def);
 565
 566   if (loop_in_sese_p (def_loop, region))
 567     {
 568       t = analyze_scalar_evolution (def_loop, t);
 569       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 570       t = compute_overall_effect_of_inner_loop (def_loop, t);
 571       return t;
 572     }
 573
 574   bool has_vdefs = false;
 575   if (invariant_in_sese_p_rec (t, region, &has_vdefs))
 576     return t;
 577
 578   /* T variates in REGION.  */
 579   if (has_vdefs)
 580     return chrec_dont_know;
 581
 582   return instantiate_scev (before, loop, t);
 583 }