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