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   sese_build_liveouts (region, liveouts);
 305
 306   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
 307     if (!virtual_operand_p (ssa_name (i)))
 308       sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 309
 310   BITMAP_FREE (liveouts);
 311 }
 312
 313 /* Returns the outermost loop in SCOP that contains BB.  */
 314
 315 struct loop *
 316 outermost_loop_in_sese_1 (sese_l &region, basic_block bb)
 317 {
 318   struct loop *nest;
 319
 320   nest = bb->loop_father;
 321   while (loop_outer (nest)
 322          && loop_in_sese_p (loop_outer (nest), region))
 323     nest = loop_outer (nest);
 324
 325   return nest;
 326 }
 327
 328 /* Same as outermost_loop_in_sese_1, returns the outermost loop
 329    containing BB in REGION, but makes sure that the returned loop
 330    belongs to the REGION, and so this returns the first loop in the
 331    REGION when the loop containing BB does not belong to REGION.  */
 332
 333 loop_p
 334 outermost_loop_in_sese (sese_l &region, basic_block bb)
 335 {
 336   loop_p nest = outermost_loop_in_sese_1 (region, bb);
 337
 338   if (loop_in_sese_p (nest, region))
 339     return nest;
 340
 341   /* When the basic block BB does not belong to a loop in the region,
 342      return the first loop in the region.  */
 343   nest = nest->inner;
 344   while (nest)
 345     if (loop_in_sese_p (nest, region))
 346       break;
 347     else
 348       nest = nest->next;
 349
 350   gcc_assert (nest);
 351   return nest;
 352 }
 353
 354 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 355
 356 edge
 357 get_true_edge_from_guard_bb (basic_block bb)
 358 {
 359   edge e;
 360   edge_iterator ei;
 361
 362   FOR_EACH_EDGE (e, ei, bb->succs)
 363     if (e->flags & EDGE_TRUE_VALUE)
 364       return e;
 365
 366   gcc_unreachable ();
 367   return NULL;
 368 }
 369
 370 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 371
 372 edge
 373 get_false_edge_from_guard_bb (basic_block bb)
 374 {
 375   edge e;
 376   edge_iterator ei;
 377
 378   FOR_EACH_EDGE (e, ei, bb->succs)
 379     if (!(e->flags & EDGE_TRUE_VALUE))
 380       return e;
 381
 382   gcc_unreachable ();
 383   return NULL;
 384 }
 385
 386 /* Sets the false region of an IF_REGION to REGION.  */
 387
 388 void
 389 if_region_set_false_region (ifsese if_region, sese_info_p region)
 390 {
 391   basic_block condition = if_region_get_condition_block (if_region);
 392   edge false_edge = get_false_edge_from_guard_bb (condition);
 393   basic_block dummy = false_edge->dest;
 394   edge entry_region = region->region.entry;
 395   edge exit_region = region->region.exit;
 396   basic_block before_region = entry_region->src;
 397   basic_block last_in_region = exit_region->src;
 398   hashval_t hash = htab_hash_pointer (exit_region);
 399   loop_exit **slot
 400     = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT);
 401
 402   entry_region->flags = false_edge->flags;
 403   false_edge->flags = exit_region->flags;
 404
 405   redirect_edge_pred (entry_region, condition);
 406   redirect_edge_pred (exit_region, before_region);
 407   redirect_edge_pred (false_edge, last_in_region);
 408   redirect_edge_succ (false_edge, single_succ (dummy));
 409   delete_basic_block (dummy);
 410
 411   exit_region->flags = EDGE_FALLTHRU;
 412   recompute_all_dominators ();
 413
 414   region->region.exit = false_edge;
 415
 416   free (if_region->false_region);
 417   if_region->false_region = region;
 418
 419   if (slot)
 420     {
 421       struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> ();
 422
 423       memcpy (loop_exit, *((struct loop_exit **) slot),
 424               sizeof (struct loop_exit));
 425       current_loops->exits->clear_slot (slot);
 426
 427       hashval_t hash = htab_hash_pointer (false_edge);
 428       slot = current_loops->exits->find_slot_with_hash (false_edge, hash,
 429                                                         INSERT);
 430       loop_exit->e = false_edge;
 431       *slot = loop_exit;
 432       false_edge->src->loop_father->exits->next = loop_exit;
 433     }
 434 }
 435
 436 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
 437
 438 static ifsese
 439 create_if_region_on_edge (edge entry, tree condition)
 440 {
 441   edge e;
 442   edge_iterator ei;
 443   sese_info_p sese_region = XNEW (struct sese_info_t);
 444   sese_info_p true_region = XNEW (struct sese_info_t);
 445   sese_info_p false_region = XNEW (struct sese_info_t);
 446   ifsese if_region = XNEW (struct ifsese_s);
 447   edge exit = create_empty_if_region_on_edge (entry, condition);
 448
 449   if_region->region = sese_region;
 450   if_region->region->region.entry = entry;
 451   if_region->region->region.exit = exit;
 452
 453   FOR_EACH_EDGE (e, ei, entry->dest->succs)
 454     {
 455       if (e->flags & EDGE_TRUE_VALUE)
 456         {
 457           true_region->region.entry = e;
 458           true_region->region.exit = single_succ_edge (e->dest);
 459           if_region->true_region = true_region;
 460         }
 461       else if (e->flags & EDGE_FALSE_VALUE)
 462         {
 463           false_region->region.entry = e;
 464           false_region->region.exit = single_succ_edge (e->dest);
 465           if_region->false_region = false_region;
 466         }
 467     }
 468
 469   return if_region;
 470 }
 471
 472 /* Moves REGION in a condition expression:
 473    | if (1)
 474    |   ;
 475    | else
 476    |   REGION;
 477 */
 478
 479 ifsese
 480 move_sese_in_condition (sese_info_p region)
 481 {
 482   basic_block pred_block = split_edge (region->region.entry);
 483   ifsese if_region;
 484
 485   region->region.entry = single_succ_edge (pred_block);
 486   if_region = create_if_region_on_edge (single_pred_edge (pred_block),
 487                                         integer_one_node);
 488   if_region_set_false_region (if_region, region);
 489
 490   return if_region;
 491 }
 492
 493 /* Replaces the condition of the IF_REGION with CONDITION:
 494    | if (CONDITION)
 495    |   true_region;
 496    | else
 497    |   false_region;
 498 */
 499
 500 void
 501 set_ifsese_condition (ifsese if_region, tree condition)
 502 {
 503   sese_info_p region = if_region->region;
 504   edge entry = region->region.entry;
 505   basic_block bb = entry->dest;
 506   gimple *last = last_stmt (bb);
 507   gimple_stmt_iterator gsi = gsi_last_bb (bb);
 508   gcond *cond_stmt;
 509
 510   gcc_assert (gimple_code (last) == GIMPLE_COND);
 511
 512   gsi_remove (&gsi, true);
 513   gsi = gsi_last_bb (bb);
 514   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
 515                                         false, GSI_NEW_STMT);
 516   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
 517   gsi = gsi_last_bb (bb);
 518   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
 519 }
 520
 521 /* Return true when T is defined outside REGION or when no definitions are
 522    variant in REGION.  When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
 523    when T depends on memory that may change in REGION.  */
 524
 525 bool
 526 invariant_in_sese_p_rec (tree t, sese_l &region, bool *has_vdefs)
 527 {
 528   if (!defined_in_sese_p (t, region))
 529     return true;
 530
 531   gimple *stmt = SSA_NAME_DEF_STMT (t);
 532
 533   if (gimple_code (stmt) == GIMPLE_PHI
 534       || gimple_code (stmt) == GIMPLE_CALL)
 535     return false;
 536
 537   /* VDEF is variant when it is in the region.  */
 538   if (gimple_vdef (stmt))
 539     {
 540       if (has_vdefs)
 541         *has_vdefs = true;
 542       return false;
 543     }
 544
 545   /* A VUSE may or may not be variant following the VDEFs.  */
 546   if (tree vuse = gimple_vuse (stmt))
 547     return invariant_in_sese_p_rec (vuse, region, has_vdefs);
 548
 549   ssa_op_iter iter;
 550   use_operand_p use_p;
 551   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 552     {
 553       tree use = USE_FROM_PTR (use_p);
 554
 555       if (!defined_in_sese_p (use, region))
 556         continue;
 557
 558       if (!invariant_in_sese_p_rec (use, region, has_vdefs))
 559         return false;
 560     }
 561
 562   return true;
 563 }
 564
 565 /* Return true when DEF can be analyzed in REGION by the scalar
 566    evolution analyzer.  */
 567
 568 bool
 569 scev_analyzable_p (tree def, sese_l &region)
 570 {
 571   loop_p loop;
 572   tree scev;
 573   tree type = TREE_TYPE (def);
 574
 575   /* When Graphite generates code for a scev, the code generator
 576      expresses the scev in function of a single induction variable.
 577      This is unsafe for floating point computations, as it may replace
 578      a floating point sum reduction with a multiplication.  The
 579      following test returns false for non integer types to avoid such
 580      problems.  */
 581   if (!INTEGRAL_TYPE_P (type)
 582       && !POINTER_TYPE_P (type))
 583     return false;
 584
 585   loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
 586   scev = scalar_evolution_in_region (region, loop, def);
 587
 588   return !chrec_contains_undetermined (scev)
 589     && (TREE_CODE (scev) != SSA_NAME
 590         || !defined_in_sese_p (scev, region))
 591     && (tree_does_not_contain_chrecs (scev)
 592         || evolution_function_is_affine_p (scev));
 593 }
 594
 595 /* Returns the scalar evolution of T in REGION.  Every variable that
 596    is not defined in the REGION is considered a parameter.  */
 597
 598 tree
 599 scalar_evolution_in_region (sese_l &region, loop_p loop, tree t)
 600 {
 601   gimple *def;
 602   struct loop *def_loop;
 603   basic_block before = region.entry->src;
 604
 605   /* SCOP parameters.  */
 606   if (TREE_CODE (t) == SSA_NAME
 607       && !defined_in_sese_p (t, region))
 608     return t;
 609
 610   if (TREE_CODE (t) != SSA_NAME
 611       || loop_in_sese_p (loop, region))
 612     /* FIXME: we would need instantiate SCEV to work on a region, and be more
 613        flexible wrt. memory loads that may be invariant in the region.  */
 614     return instantiate_scev (before, loop,
 615                              analyze_scalar_evolution (loop, t));
 616
 617   def = SSA_NAME_DEF_STMT (t);
 618   def_loop = loop_containing_stmt (def);
 619
 620   if (loop_in_sese_p (def_loop, region))
 621     {
 622       t = analyze_scalar_evolution (def_loop, t);
 623       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
 624       t = compute_overall_effect_of_inner_loop (def_loop, t);
 625       return t;
 626     }
 627
 628   bool has_vdefs = false;
 629   if (invariant_in_sese_p_rec (t, region, &has_vdefs))
 630     return t;
 631
 632   /* T variates in REGION.  */
 633   if (has_vdefs)
 634     return chrec_dont_know;
 635
 636   return instantiate_scev (before, loop, t);
 637 }