gcc/sese.c

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