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