1 /* Single entry single exit control flow regions. 2 Copyright (C) 2008, 2009, 2010, 2011 3 Free Software Foundation, Inc. 4 Contributed by Jan Sjodin <jan.sjodin@amd.com> and 5 Sebastian Pop <sebastian.pop@amd.com>. 6 7 This file is part of GCC. 8 9 GCC is free software; you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation; either version 3, or (at your option) 12 any later version. 13 14 GCC is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with GCC; see the file COPYING3. If not see 21 <http://www.gnu.org/licenses/>. */ 22 23 #include "config.h" 24 #include "system.h" 25 #include "coretypes.h" 26 #include "tree-pretty-print.h" 27 #include "tree-flow.h" 28 #include "cfgloop.h" 29 #include "tree-chrec.h" 30 #include "tree-data-ref.h" 31 #include "tree-scalar-evolution.h" 32 #include "tree-pass.h" 33 #include "value-prof.h" 34 #include "sese.h" 35 36 /* Print to stderr the element ELT. */ 37 38 static void 39 debug_rename_elt (rename_map_elt elt) 40 { 41 fprintf (stderr, "("); 42 print_generic_expr (stderr, elt->old_name, 0); 43 fprintf (stderr, ", "); 44 print_generic_expr (stderr, elt->expr, 0); 45 fprintf (stderr, ")\n"); 46 } 47 48 /* Helper function for debug_rename_map. */ 49 50 static int 51 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) 52 { 53 struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot; 54 debug_rename_elt (entry); 55 return 1; 56 } 57 58 /* Print to stderr all the elements of RENAME_MAP. */ 59 60 DEBUG_FUNCTION void 61 debug_rename_map (htab_t rename_map) 62 { 63 htab_traverse (rename_map, debug_rename_map_1, NULL); 64 } 65 66 /* Computes a hash function for database element ELT. */ 67 68 hashval_t 69 rename_map_elt_info (const void *elt) 70 { 71 return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name); 72 } 73 74 /* Compares database elements E1 and E2. */ 75 76 int 77 eq_rename_map_elts (const void *e1, const void *e2) 78 { 79 const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1; 80 const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2; 81 82 return (elt1->old_name == elt2->old_name); 83 } 84 85 86 87 /* Print to stderr the element ELT. */ 88 89 static void 90 debug_ivtype_elt (ivtype_map_elt elt) 91 { 92 fprintf (stderr, "(%s, ", elt->cloog_iv); 93 print_generic_expr (stderr, elt->type, 0); 94 fprintf (stderr, ")\n"); 95 } 96 97 /* Helper function for debug_ivtype_map. */ 98 99 static int 100 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED) 101 { 102 struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot; 103 debug_ivtype_elt (entry); 104 return 1; 105 } 106 107 /* Print to stderr all the elements of MAP. */ 108 109 DEBUG_FUNCTION void 110 debug_ivtype_map (htab_t map) 111 { 112 htab_traverse (map, debug_ivtype_map_1, NULL); 113 } 114 115 /* Computes a hash function for database element ELT. */ 116 117 hashval_t 118 ivtype_map_elt_info (const void *elt) 119 { 120 return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv); 121 } 122 123 /* Compares database elements E1 and E2. */ 124 125 int 126 eq_ivtype_map_elts (const void *e1, const void *e2) 127 { 128 const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1; 129 const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2; 130 131 return (elt1->cloog_iv == elt2->cloog_iv); 132 } 133 134 135 136 /* Record LOOP as occuring in REGION. */ 137 138 static void 139 sese_record_loop (sese region, loop_p loop) 140 { 141 if (sese_contains_loop (region, loop)) 142 return; 143 144 bitmap_set_bit (SESE_LOOPS (region), loop->num); 145 VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop); 146 } 147 148 /* Build the loop nests contained in REGION. Returns true when the 149 operation was successful. */ 150 151 void 152 build_sese_loop_nests (sese region) 153 { 154 unsigned i; 155 basic_block bb; 156 struct loop *loop0, *loop1; 157 158 FOR_EACH_BB (bb) 159 if (bb_in_sese_p (bb, region)) 160 { 161 struct loop *loop = bb->loop_father; 162 163 /* Only add loops if they are completely contained in the SCoP. */ 164 if (loop->header == bb 165 && bb_in_sese_p (loop->latch, region)) 166 sese_record_loop (region, loop); 167 } 168 169 /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It 170 can be the case that an inner loop is inserted before an outer 171 loop. To avoid this, semi-sort once. */ 172 FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), i, loop0) 173 { 174 if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1) 175 break; 176 177 loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1); 178 if (loop0->num > loop1->num) 179 { 180 VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1); 181 VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0); 182 } 183 } 184 } 185 186 /* For a USE in BB, if BB is outside REGION, mark the USE in the 187 LIVEOUTS set. */ 188 189 static void 190 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb, 191 tree use) 192 { 193 unsigned ver; 194 basic_block def_bb; 195 196 if (TREE_CODE (use) != SSA_NAME) 197 return; 198 199 ver = SSA_NAME_VERSION (use); 200 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); 201 202 if (!def_bb 203 || !bb_in_sese_p (def_bb, region) 204 || bb_in_sese_p (bb, region)) 205 return; 206 207 bitmap_set_bit (liveouts, ver); 208 } 209 210 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are 211 used in BB that is outside of the REGION. */ 212 213 static void 214 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb) 215 { 216 gimple_stmt_iterator bsi; 217 edge e; 218 edge_iterator ei; 219 ssa_op_iter iter; 220 use_operand_p use_p; 221 222 FOR_EACH_EDGE (e, ei, bb->succs) 223 for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi)) 224 sese_build_liveouts_use (region, liveouts, bb, 225 PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e)); 226 227 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 228 { 229 gimple stmt = gsi_stmt (bsi); 230 231 if (is_gimple_debug (stmt)) 232 continue; 233 234 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 235 sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p)); 236 } 237 } 238 239 /* For a USE in BB, return true if BB is outside REGION and it's not 240 in the LIVEOUTS set. */ 241 242 static bool 243 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb, 244 tree use) 245 { 246 unsigned ver; 247 basic_block def_bb; 248 249 if (TREE_CODE (use) != SSA_NAME) 250 return false; 251 252 ver = SSA_NAME_VERSION (use); 253 254 /* If it's in liveouts, the variable will get a new PHI node, and 255 the debug use will be properly adjusted. */ 256 if (bitmap_bit_p (liveouts, ver)) 257 return false; 258 259 def_bb = gimple_bb (SSA_NAME_DEF_STMT (use)); 260 261 if (!def_bb 262 || !bb_in_sese_p (def_bb, region) 263 || bb_in_sese_p (bb, region)) 264 return false; 265 266 return true; 267 } 268 269 /* Reset debug stmts that reference SSA_NAMES defined in REGION that 270 are not marked as liveouts. */ 271 272 static void 273 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb) 274 { 275 gimple_stmt_iterator bsi; 276 ssa_op_iter iter; 277 use_operand_p use_p; 278 279 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 280 { 281 gimple stmt = gsi_stmt (bsi); 282 283 if (!is_gimple_debug (stmt)) 284 continue; 285 286 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) 287 if (sese_bad_liveouts_use (region, liveouts, bb, 288 USE_FROM_PTR (use_p))) 289 { 290 gimple_debug_bind_reset_value (stmt); 291 update_stmt (stmt); 292 break; 293 } 294 } 295 } 296 297 /* Build the LIVEOUTS of REGION: the set of variables defined inside 298 and used outside the REGION. */ 299 300 static void 301 sese_build_liveouts (sese region, bitmap liveouts) 302 { 303 basic_block bb; 304 305 FOR_EACH_BB (bb) 306 sese_build_liveouts_bb (region, liveouts, bb); 307 if (MAY_HAVE_DEBUG_INSNS) 308 FOR_EACH_BB (bb) 309 sese_reset_debug_liveouts_bb (region, liveouts, bb); 310 } 311 312 /* Builds a new SESE region from edges ENTRY and EXIT. */ 313 314 sese 315 new_sese (edge entry, edge exit) 316 { 317 sese region = XNEW (struct sese_s); 318 319 SESE_ENTRY (region) = entry; 320 SESE_EXIT (region) = exit; 321 SESE_LOOPS (region) = BITMAP_ALLOC (NULL); 322 SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3); 323 SESE_ADD_PARAMS (region) = true; 324 SESE_PARAMS (region) = VEC_alloc (tree, heap, 3); 325 326 return region; 327 } 328 329 /* Deletes REGION. */ 330 331 void 332 free_sese (sese region) 333 { 334 if (SESE_LOOPS (region)) 335 SESE_LOOPS (region) = BITMAP_ALLOC (NULL); 336 337 VEC_free (tree, heap, SESE_PARAMS (region)); 338 VEC_free (loop_p, heap, SESE_LOOP_NEST (region)); 339 340 XDELETE (region); 341 } 342 343 /* Add exit phis for USE on EXIT. */ 344 345 static void 346 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e) 347 { 348 gimple phi = create_phi_node (use, exit); 349 350 create_new_def_for (gimple_phi_result (phi), phi, 351 gimple_phi_result_ptr (phi)); 352 add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION); 353 add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION); 354 } 355 356 /* Insert in the block BB phi nodes for variables defined in REGION 357 and used outside the REGION. The code generation moves REGION in 358 the else clause of an "if (1)" and generates code in the then 359 clause that is at this point empty: 360 361 | if (1) 362 | empty; 363 | else 364 | REGION; 365 */ 366 367 void 368 sese_insert_phis_for_liveouts (sese region, basic_block bb, 369 edge false_e, edge true_e) 370 { 371 unsigned i; 372 bitmap_iterator bi; 373 bitmap liveouts = BITMAP_ALLOC (NULL); 374 375 update_ssa (TODO_update_ssa); 376 377 sese_build_liveouts (region, liveouts); 378 EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi) 379 sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e); 380 BITMAP_FREE (liveouts); 381 382 update_ssa (TODO_update_ssa); 383 } 384 385 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */ 386 387 edge 388 get_true_edge_from_guard_bb (basic_block bb) 389 { 390 edge e; 391 edge_iterator ei; 392 393 FOR_EACH_EDGE (e, ei, bb->succs) 394 if (e->flags & EDGE_TRUE_VALUE) 395 return e; 396 397 gcc_unreachable (); 398 return NULL; 399 } 400 401 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared. */ 402 403 edge 404 get_false_edge_from_guard_bb (basic_block bb) 405 { 406 edge e; 407 edge_iterator ei; 408 409 FOR_EACH_EDGE (e, ei, bb->succs) 410 if (!(e->flags & EDGE_TRUE_VALUE)) 411 return e; 412 413 gcc_unreachable (); 414 return NULL; 415 } 416 417 /* Returns the expression associated to OLD_NAME in RENAME_MAP. */ 418 419 static tree 420 get_rename (htab_t rename_map, tree old_name) 421 { 422 struct rename_map_elt_s tmp; 423 PTR *slot; 424 425 gcc_assert (TREE_CODE (old_name) == SSA_NAME); 426 tmp.old_name = old_name; 427 slot = htab_find_slot (rename_map, &tmp, NO_INSERT); 428 429 if (slot && *slot) 430 return ((rename_map_elt) *slot)->expr; 431 432 return NULL_TREE; 433 } 434 435 /* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */ 436 437 static void 438 set_rename (htab_t rename_map, tree old_name, tree expr) 439 { 440 struct rename_map_elt_s tmp; 441 PTR *slot; 442 443 if (old_name == expr) 444 return; 445 446 tmp.old_name = old_name; 447 slot = htab_find_slot (rename_map, &tmp, INSERT); 448 449 if (!slot) 450 return; 451 452 free (*slot); 453 454 *slot = new_rename_map_elt (old_name, expr); 455 } 456 457 /* Renames the scalar uses of the statement COPY, using the 458 substitution map RENAME_MAP, inserting the gimplification code at 459 GSI_TGT, for the translation REGION, with the original copied 460 statement in LOOP, and using the induction variable renaming map 461 IV_MAP. Returns true when something has been renamed. GLOOG_ERROR 462 is set when the code generation cannot continue. */ 463 464 static bool 465 rename_uses (gimple copy, htab_t rename_map, gimple_stmt_iterator *gsi_tgt, 466 sese region, loop_p loop, VEC (tree, heap) *iv_map, 467 bool *gloog_error) 468 { 469 use_operand_p use_p; 470 ssa_op_iter op_iter; 471 bool changed = false; 472 473 if (is_gimple_debug (copy)) 474 { 475 if (gimple_debug_bind_p (copy)) 476 gimple_debug_bind_reset_value (copy); 477 else if (gimple_debug_source_bind_p (copy)) 478 return false; 479 else 480 gcc_unreachable (); 481 482 return false; 483 } 484 485 FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_ALL_USES) 486 { 487 tree old_name = USE_FROM_PTR (use_p); 488 tree new_expr, scev; 489 gimple_seq stmts; 490 491 if (TREE_CODE (old_name) != SSA_NAME 492 || !is_gimple_reg (old_name) 493 || SSA_NAME_IS_DEFAULT_DEF (old_name)) 494 continue; 495 496 changed = true; 497 new_expr = get_rename (rename_map, old_name); 498 if (new_expr) 499 { 500 tree type_old_name = TREE_TYPE (old_name); 501 tree type_new_expr = TREE_TYPE (new_expr); 502 503 if (type_old_name != type_new_expr 504 || (TREE_CODE (new_expr) != SSA_NAME 505 && is_gimple_reg (old_name))) 506 { 507 tree var = create_tmp_var (type_old_name, "var"); 508 509 if (type_old_name != type_new_expr) 510 new_expr = fold_convert (type_old_name, new_expr); 511 512 new_expr = build2 (MODIFY_EXPR, type_old_name, var, new_expr); 513 new_expr = force_gimple_operand (new_expr, &stmts, true, NULL); 514 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); 515 } 516 517 replace_exp (use_p, new_expr); 518 continue; 519 } 520 521 scev = scalar_evolution_in_region (region, loop, old_name); 522 523 /* At this point we should know the exact scev for each 524 scalar SSA_NAME used in the scop: all the other scalar 525 SSA_NAMEs should have been translated out of SSA using 526 arrays with one element. */ 527 if (chrec_contains_undetermined (scev)) 528 { 529 *gloog_error = true; 530 new_expr = build_zero_cst (TREE_TYPE (old_name)); 531 } 532 else 533 new_expr = chrec_apply_map (scev, iv_map); 534 535 /* The apply should produce an expression tree containing 536 the uses of the new induction variables. We should be 537 able to use new_expr instead of the old_name in the newly 538 generated loop nest. */ 539 if (chrec_contains_undetermined (new_expr) 540 || tree_contains_chrecs (new_expr, NULL)) 541 { 542 *gloog_error = true; 543 new_expr = build_zero_cst (TREE_TYPE (old_name)); 544 } 545 else 546 /* Replace the old_name with the new_expr. */ 547 new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts, 548 true, NULL_TREE); 549 550 gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT); 551 replace_exp (use_p, new_expr); 552 553 if (TREE_CODE (new_expr) == INTEGER_CST 554 && is_gimple_assign (copy)) 555 { 556 tree rhs = gimple_assign_rhs1 (copy); 557 558 if (TREE_CODE (rhs) == ADDR_EXPR) 559 recompute_tree_invariant_for_addr_expr (rhs); 560 } 561 562 set_rename (rename_map, old_name, new_expr); 563 } 564 565 return changed; 566 } 567 568 /* Duplicates the statements of basic block BB into basic block NEW_BB 569 and compute the new induction variables according to the IV_MAP. 570 GLOOG_ERROR is set when the code generation cannot continue. */ 571 572 static void 573 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, 574 htab_t rename_map, 575 VEC (tree, heap) *iv_map, sese region, 576 bool *gloog_error) 577 { 578 gimple_stmt_iterator gsi, gsi_tgt; 579 loop_p loop = bb->loop_father; 580 581 gsi_tgt = gsi_start_bb (new_bb); 582 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 583 { 584 def_operand_p def_p; 585 ssa_op_iter op_iter; 586 gimple stmt = gsi_stmt (gsi); 587 gimple copy; 588 tree lhs; 589 590 /* Do not copy labels or conditions. */ 591 if (gimple_code (stmt) == GIMPLE_LABEL 592 || gimple_code (stmt) == GIMPLE_COND) 593 continue; 594 595 /* Do not copy induction variables. */ 596 if (is_gimple_assign (stmt) 597 && (lhs = gimple_assign_lhs (stmt)) 598 && TREE_CODE (lhs) == SSA_NAME 599 && is_gimple_reg (lhs) 600 && scev_analyzable_p (lhs, region)) 601 continue; 602 603 /* Create a new copy of STMT and duplicate STMT's virtual 604 operands. */ 605 copy = gimple_copy (stmt); 606 gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT); 607 mark_sym_for_renaming (gimple_vop (cfun)); 608 609 maybe_duplicate_eh_stmt (copy, stmt); 610 gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt); 611 612 /* Create new names for all the definitions created by COPY and 613 add replacement mappings for each new name. */ 614 FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS) 615 { 616 tree old_name = DEF_FROM_PTR (def_p); 617 tree new_name = create_new_def_for (old_name, copy, def_p); 618 set_rename (rename_map, old_name, new_name); 619 } 620 621 if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map, 622 gloog_error)) 623 { 624 gcc_assert (gsi_stmt (gsi_tgt) == copy); 625 fold_stmt_inplace (&gsi_tgt); 626 } 627 628 update_stmt (copy); 629 } 630 } 631 632 /* Copies BB and includes in the copied BB all the statements that can 633 be reached following the use-def chains from the memory accesses, 634 and returns the next edge following this new block. GLOOG_ERROR is 635 set when the code generation cannot continue. */ 636 637 edge 638 copy_bb_and_scalar_dependences (basic_block bb, sese region, 639 edge next_e, VEC (tree, heap) *iv_map, 640 bool *gloog_error) 641 { 642 basic_block new_bb = split_edge (next_e); 643 htab_t rename_map = htab_create (10, rename_map_elt_info, 644 eq_rename_map_elts, free); 645 646 next_e = single_succ_edge (new_bb); 647 graphite_copy_stmts_from_block (bb, new_bb, rename_map, iv_map, region, 648 gloog_error); 649 remove_phi_nodes (new_bb); 650 htab_delete (rename_map); 651 652 return next_e; 653 } 654 655 /* Returns the outermost loop in SCOP that contains BB. */ 656 657 struct loop * 658 outermost_loop_in_sese (sese region, basic_block bb) 659 { 660 struct loop *nest; 661 662 nest = bb->loop_father; 663 while (loop_outer (nest) 664 && loop_in_sese_p (loop_outer (nest), region)) 665 nest = loop_outer (nest); 666 667 return nest; 668 } 669 670 /* Sets the false region of an IF_REGION to REGION. */ 671 672 void 673 if_region_set_false_region (ifsese if_region, sese region) 674 { 675 basic_block condition = if_region_get_condition_block (if_region); 676 edge false_edge = get_false_edge_from_guard_bb (condition); 677 basic_block dummy = false_edge->dest; 678 edge entry_region = SESE_ENTRY (region); 679 edge exit_region = SESE_EXIT (region); 680 basic_block before_region = entry_region->src; 681 basic_block last_in_region = exit_region->src; 682 void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region, 683 htab_hash_pointer (exit_region), 684 NO_INSERT); 685 686 entry_region->flags = false_edge->flags; 687 false_edge->flags = exit_region->flags; 688 689 redirect_edge_pred (entry_region, condition); 690 redirect_edge_pred (exit_region, before_region); 691 redirect_edge_pred (false_edge, last_in_region); 692 redirect_edge_succ (false_edge, single_succ (dummy)); 693 delete_basic_block (dummy); 694 695 exit_region->flags = EDGE_FALLTHRU; 696 recompute_all_dominators (); 697 698 SESE_EXIT (region) = false_edge; 699 700 free (if_region->false_region); 701 if_region->false_region = region; 702 703 if (slot) 704 { 705 struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit (); 706 707 memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit)); 708 htab_clear_slot (current_loops->exits, slot); 709 710 slot = htab_find_slot_with_hash (current_loops->exits, false_edge, 711 htab_hash_pointer (false_edge), 712 INSERT); 713 loop_exit->e = false_edge; 714 *slot = loop_exit; 715 false_edge->src->loop_father->exits->next = loop_exit; 716 } 717 } 718 719 /* Creates an IFSESE with CONDITION on edge ENTRY. */ 720 721 static ifsese 722 create_if_region_on_edge (edge entry, tree condition) 723 { 724 edge e; 725 edge_iterator ei; 726 sese sese_region = XNEW (struct sese_s); 727 sese true_region = XNEW (struct sese_s); 728 sese false_region = XNEW (struct sese_s); 729 ifsese if_region = XNEW (struct ifsese_s); 730 edge exit = create_empty_if_region_on_edge (entry, condition); 731 732 if_region->region = sese_region; 733 if_region->region->entry = entry; 734 if_region->region->exit = exit; 735 736 FOR_EACH_EDGE (e, ei, entry->dest->succs) 737 { 738 if (e->flags & EDGE_TRUE_VALUE) 739 { 740 true_region->entry = e; 741 true_region->exit = single_succ_edge (e->dest); 742 if_region->true_region = true_region; 743 } 744 else if (e->flags & EDGE_FALSE_VALUE) 745 { 746 false_region->entry = e; 747 false_region->exit = single_succ_edge (e->dest); 748 if_region->false_region = false_region; 749 } 750 } 751 752 return if_region; 753 } 754 755 /* Moves REGION in a condition expression: 756 | if (1) 757 | ; 758 | else 759 | REGION; 760 */ 761 762 ifsese 763 move_sese_in_condition (sese region) 764 { 765 basic_block pred_block = split_edge (SESE_ENTRY (region)); 766 ifsese if_region; 767 768 SESE_ENTRY (region) = single_succ_edge (pred_block); 769 if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node); 770 if_region_set_false_region (if_region, region); 771 772 return if_region; 773 } 774 775 /* Replaces the condition of the IF_REGION with CONDITION: 776 | if (CONDITION) 777 | true_region; 778 | else 779 | false_region; 780 */ 781 782 void 783 set_ifsese_condition (ifsese if_region, tree condition) 784 { 785 sese region = if_region->region; 786 edge entry = region->entry; 787 basic_block bb = entry->dest; 788 gimple last = last_stmt (bb); 789 gimple_stmt_iterator gsi = gsi_last_bb (bb); 790 gimple cond_stmt; 791 792 gcc_assert (gimple_code (last) == GIMPLE_COND); 793 794 gsi_remove (&gsi, true); 795 gsi = gsi_last_bb (bb); 796 condition = force_gimple_operand_gsi (&gsi, condition, true, NULL, 797 false, GSI_NEW_STMT); 798 cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE); 799 gsi = gsi_last_bb (bb); 800 gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT); 801 } 802 803 /* Returns the scalar evolution of T in REGION. Every variable that 804 is not defined in the REGION is considered a parameter. */ 805 806 tree 807 scalar_evolution_in_region (sese region, loop_p loop, tree t) 808 { 809 gimple def; 810 struct loop *def_loop; 811 basic_block before = block_before_sese (region); 812 813 /* SCOP parameters. */ 814 if (TREE_CODE (t) == SSA_NAME 815 && !defined_in_sese_p (t, region)) 816 return t; 817 818 if (TREE_CODE (t) != SSA_NAME 819 || loop_in_sese_p (loop, region)) 820 return instantiate_scev (before, loop, 821 analyze_scalar_evolution (loop, t)); 822 823 def = SSA_NAME_DEF_STMT (t); 824 def_loop = loop_containing_stmt (def); 825 826 if (loop_in_sese_p (def_loop, region)) 827 { 828 t = analyze_scalar_evolution (def_loop, t); 829 def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1); 830 t = compute_overall_effect_of_inner_loop (def_loop, t); 831 return t; 832 } 833 else 834 return instantiate_scev (before, loop, t); 835 } 836