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