gcc/sese.c

   1 /* Single entry single exit control flow regions.
   2    Copyright (C) 2008, 2009, 2010
   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 "tm.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "rtl.h"
  30 #include "basic-block.h"
  31 #include "diagnostic.h"
  32 #include "tree-pretty-print.h"
  33 #include "tree-flow.h"
  34 #include "toplev.h"
  35 #include "tree-dump.h"
  36 #include "timevar.h"
  37 #include "cfgloop.h"
  38 #include "tree-chrec.h"
  39 #include "tree-data-ref.h"
  40 #include "tree-scalar-evolution.h"
  41 #include "tree-pass.h"
  42 #include "domwalk.h"
  43 #include "value-prof.h"
  44 #include "pointer-set.h"
  45 #include "gimple.h"
  46 #include "sese.h"
  47
  48 /* Print to stderr the element ELT.  */
  49
  50 static void
  51 debug_rename_elt (rename_map_elt elt)
  52 {
  53   fprintf (stderr, "(");
  54   print_generic_expr (stderr, elt->old_name, 0);
  55   fprintf (stderr, ", ");
  56   print_generic_expr (stderr, elt->expr, 0);
  57   fprintf (stderr, ")\n");
  58 }
  59
  60 /* Helper function for debug_rename_map.  */
  61
  62 static int
  63 debug_rename_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
  64 {
  65   struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
  66   debug_rename_elt (entry);
  67   return 1;
  68 }
  69
  70 /* Print to stderr all the elements of MAP.  */
  71
  72 DEBUG_FUNCTION void
  73 debug_rename_map (htab_t map)
  74 {
  75   htab_traverse (map, debug_rename_map_1, NULL);
  76 }
  77
  78 /* Computes a hash function for database element ELT.  */
  79
  80 hashval_t
  81 rename_map_elt_info (const void *elt)
  82 {
  83   return SSA_NAME_VERSION (((const struct rename_map_elt_s *) elt)->old_name);
  84 }
  85
  86 /* Compares database elements E1 and E2.  */
  87
  88 int
  89 eq_rename_map_elts (const void *e1, const void *e2)
  90 {
  91   const struct rename_map_elt_s *elt1 = (const struct rename_map_elt_s *) e1;
  92   const struct rename_map_elt_s *elt2 = (const struct rename_map_elt_s *) e2;
  93
  94   return (elt1->old_name == elt2->old_name);
  95 }
  96
  97 \f
  98
  99 /* Print to stderr the element ELT.  */
 100
 101 static void
 102 debug_ivtype_elt (ivtype_map_elt elt)
 103 {
 104   fprintf (stderr, "(%s, ", elt->cloog_iv);
 105   print_generic_expr (stderr, elt->type, 0);
 106   fprintf (stderr, ")\n");
 107 }
 108
 109 /* Helper function for debug_ivtype_map.  */
 110
 111 static int
 112 debug_ivtype_map_1 (void **slot, void *s ATTRIBUTE_UNUSED)
 113 {
 114   struct ivtype_map_elt_s *entry = (struct ivtype_map_elt_s *) *slot;
 115   debug_ivtype_elt (entry);
 116   return 1;
 117 }
 118
 119 /* Print to stderr all the elements of MAP.  */
 120
 121 DEBUG_FUNCTION void
 122 debug_ivtype_map (htab_t map)
 123 {
 124   htab_traverse (map, debug_ivtype_map_1, NULL);
 125 }
 126
 127 /* Computes a hash function for database element ELT.  */
 128
 129 hashval_t
 130 ivtype_map_elt_info (const void *elt)
 131 {
 132   return htab_hash_pointer (((const struct ivtype_map_elt_s *) elt)->cloog_iv);
 133 }
 134
 135 /* Compares database elements E1 and E2.  */
 136
 137 int
 138 eq_ivtype_map_elts (const void *e1, const void *e2)
 139 {
 140   const struct ivtype_map_elt_s *elt1 = (const struct ivtype_map_elt_s *) e1;
 141   const struct ivtype_map_elt_s *elt2 = (const struct ivtype_map_elt_s *) e2;
 142
 143   return (elt1->cloog_iv == elt2->cloog_iv);
 144 }
 145
 146 \f
 147
 148 /* Record LOOP as occuring in REGION.  */
 149
 150 static void
 151 sese_record_loop (sese region, loop_p loop)
 152 {
 153   if (sese_contains_loop (region, loop))
 154     return;
 155
 156   bitmap_set_bit (SESE_LOOPS (region), loop->num);
 157   VEC_safe_push (loop_p, heap, SESE_LOOP_NEST (region), loop);
 158 }
 159
 160 /* Build the loop nests contained in REGION.  Returns true when the
 161    operation was successful.  */
 162
 163 void
 164 build_sese_loop_nests (sese region)
 165 {
 166   unsigned i;
 167   basic_block bb;
 168   struct loop *loop0, *loop1;
 169
 170   FOR_EACH_BB (bb)
 171     if (bb_in_sese_p (bb, region))
 172       {
 173         struct loop *loop = bb->loop_father;
 174
 175         /* Only add loops if they are completely contained in the SCoP.  */
 176         if (loop->header == bb
 177             && bb_in_sese_p (loop->latch, region))
 178           sese_record_loop (region, loop);
 179       }
 180
 181   /* Make sure that the loops in the SESE_LOOP_NEST are ordered.  It
 182      can be the case that an inner loop is inserted before an outer
 183      loop.  To avoid this, semi-sort once.  */
 184   for (i = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), i, loop0); i++)
 185     {
 186       if (VEC_length (loop_p, SESE_LOOP_NEST (region)) == i + 1)
 187         break;
 188
 189       loop1 = VEC_index (loop_p, SESE_LOOP_NEST (region), i + 1);
 190       if (loop0->num > loop1->num)
 191         {
 192           VEC_replace (loop_p, SESE_LOOP_NEST (region), i, loop1);
 193           VEC_replace (loop_p, SESE_LOOP_NEST (region), i + 1, loop0);
 194         }
 195     }
 196 }
 197
 198 /* For a USE in BB, if BB is outside REGION, mark the USE in the
 199    LIVEOUTS set.  */
 200
 201 static void
 202 sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
 203                          tree use)
 204 {
 205   unsigned ver;
 206   basic_block def_bb;
 207
 208   if (TREE_CODE (use) != SSA_NAME)
 209     return;
 210
 211   ver = SSA_NAME_VERSION (use);
 212   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 213
 214   if (!def_bb
 215       || !bb_in_sese_p (def_bb, region)
 216       || bb_in_sese_p (bb, region))
 217     return;
 218
 219   bitmap_set_bit (liveouts, ver);
 220 }
 221
 222 /* Marks for rewrite all the SSA_NAMES defined in REGION and that are
 223    used in BB that is outside of the REGION.  */
 224
 225 static void
 226 sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
 227 {
 228   gimple_stmt_iterator bsi;
 229   edge e;
 230   edge_iterator ei;
 231   ssa_op_iter iter;
 232   use_operand_p use_p;
 233
 234   FOR_EACH_EDGE (e, ei, bb->succs)
 235     for (bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi); gsi_next (&bsi))
 236       sese_build_liveouts_use (region, liveouts, bb,
 237                                PHI_ARG_DEF_FROM_EDGE (gsi_stmt (bsi), e));
 238
 239   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 240     {
 241       gimple stmt = gsi_stmt (bsi);
 242
 243       if (is_gimple_debug (stmt))
 244         continue;
 245
 246       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 247         sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
 248     }
 249 }
 250
 251 /* For a USE in BB, return true if BB is outside REGION and it's not
 252    in the LIVEOUTS set.  */
 253
 254 static bool
 255 sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
 256                        tree use)
 257 {
 258   unsigned ver;
 259   basic_block def_bb;
 260
 261   if (TREE_CODE (use) != SSA_NAME)
 262     return false;
 263
 264   ver = SSA_NAME_VERSION (use);
 265
 266   /* If it's in liveouts, the variable will get a new PHI node, and
 267      the debug use will be properly adjusted.  */
 268   if (bitmap_bit_p (liveouts, ver))
 269     return false;
 270
 271   def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
 272
 273   if (!def_bb
 274       || !bb_in_sese_p (def_bb, region)
 275       || bb_in_sese_p (bb, region))
 276     return false;
 277
 278   return true;
 279 }
 280
 281 /* Reset debug stmts that reference SSA_NAMES defined in REGION that
 282    are not marked as liveouts.  */
 283
 284 static void
 285 sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
 286 {
 287   gimple_stmt_iterator bsi;
 288   ssa_op_iter iter;
 289   use_operand_p use_p;
 290
 291   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
 292     {
 293       gimple stmt = gsi_stmt (bsi);
 294
 295       if (!is_gimple_debug (stmt))
 296         continue;
 297
 298       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 299         if (sese_bad_liveouts_use (region, liveouts, bb,
 300                                    USE_FROM_PTR (use_p)))
 301           {
 302             gimple_debug_bind_reset_value (stmt);
 303             update_stmt (stmt);
 304             break;
 305           }
 306     }
 307 }
 308
 309 /* Build the LIVEOUTS of REGION: the set of variables defined inside
 310    and used outside the REGION.  */
 311
 312 static void
 313 sese_build_liveouts (sese region, bitmap liveouts)
 314 {
 315   basic_block bb;
 316
 317   FOR_EACH_BB (bb)
 318     sese_build_liveouts_bb (region, liveouts, bb);
 319   if (MAY_HAVE_DEBUG_INSNS)
 320     FOR_EACH_BB (bb)
 321       sese_reset_debug_liveouts_bb (region, liveouts, bb);
 322 }
 323
 324 /* Builds a new SESE region from edges ENTRY and EXIT.  */
 325
 326 sese
 327 new_sese (edge entry, edge exit)
 328 {
 329   sese region = XNEW (struct sese_s);
 330
 331   SESE_ENTRY (region) = entry;
 332   SESE_EXIT (region) = exit;
 333   SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
 334   SESE_LOOP_NEST (region) = VEC_alloc (loop_p, heap, 3);
 335   SESE_ADD_PARAMS (region) = true;
 336   SESE_PARAMS (region) = VEC_alloc (tree, heap, 3);
 337
 338   return region;
 339 }
 340
 341 /* Deletes REGION.  */
 342
 343 void
 344 free_sese (sese region)
 345 {
 346   if (SESE_LOOPS (region))
 347     SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
 348
 349   VEC_free (tree, heap, SESE_PARAMS (region));
 350   VEC_free (loop_p, heap, SESE_LOOP_NEST (region));
 351
 352   XDELETE (region);
 353 }
 354
 355 /* Add exit phis for USE on EXIT.  */
 356
 357 static void
 358 sese_add_exit_phis_edge (basic_block exit, tree use, edge false_e, edge true_e)
 359 {
 360   gimple phi = create_phi_node (use, exit);
 361
 362   create_new_def_for (gimple_phi_result (phi), phi,
 363                       gimple_phi_result_ptr (phi));
 364   add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
 365   add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
 366 }
 367
 368 /* Insert in the block BB phi nodes for variables defined in REGION
 369    and used outside the REGION.  The code generation moves REGION in
 370    the else clause of an "if (1)" and generates code in the then
 371    clause that is at this point empty:
 372
 373    | if (1)
 374    |   empty;
 375    | else
 376    |   REGION;
 377 */
 378
 379 void
 380 sese_insert_phis_for_liveouts (sese region, basic_block bb,
 381                                edge false_e, edge true_e)
 382 {
 383   unsigned i;
 384   bitmap_iterator bi;
 385   bitmap liveouts = BITMAP_ALLOC (NULL);
 386
 387   update_ssa (TODO_update_ssa);
 388
 389   sese_build_liveouts (region, liveouts);
 390   EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
 391     sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
 392   BITMAP_FREE (liveouts);
 393
 394   update_ssa (TODO_update_ssa);
 395 }
 396
 397 /* Returns the expression associated to OLD_NAME in MAP.  */
 398
 399 static tree
 400 get_rename (htab_t map, tree old_name)
 401 {
 402   struct rename_map_elt_s tmp;
 403   PTR *slot;
 404
 405   gcc_assert (TREE_CODE (old_name) == SSA_NAME);
 406   tmp.old_name = old_name;
 407   slot = htab_find_slot (map, &tmp, NO_INSERT);
 408
 409   if (slot && *slot)
 410     return ((rename_map_elt) *slot)->expr;
 411
 412   return old_name;
 413 }
 414
 415 /* Register in MAP the rename tuple (OLD_NAME, EXPR).  */
 416
 417 void
 418 set_rename (htab_t map, tree old_name, tree expr)
 419 {
 420   struct rename_map_elt_s tmp;
 421   PTR *slot;
 422
 423   if (old_name == expr)
 424     return;
 425
 426   tmp.old_name = old_name;
 427   slot = htab_find_slot (map, &tmp, INSERT);
 428
 429   if (!slot)
 430     return;
 431
 432   if (*slot)
 433     free (*slot);
 434
 435   *slot = new_rename_map_elt (old_name, expr);
 436 }
 437
 438 /* Rename the SSA_NAMEs used in STMT and that appear in MAP.  */
 439
 440 static void
 441 rename_variables_in_stmt (gimple stmt, htab_t map, gimple_stmt_iterator *insert_gsi)
 442 {
 443   ssa_op_iter iter;
 444   use_operand_p use_p;
 445
 446   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 447     {
 448       tree use = USE_FROM_PTR (use_p);
 449       tree expr, type_use, type_expr;
 450       gimple_seq stmts;
 451
 452       if (TREE_CODE (use) != SSA_NAME)
 453         continue;
 454
 455       expr = get_rename (map, use);
 456       if (use == expr)
 457         continue;
 458
 459       type_use = TREE_TYPE (use);
 460       type_expr = TREE_TYPE (expr);
 461
 462       if (type_use != type_expr
 463           || (TREE_CODE (expr) != SSA_NAME
 464               && is_gimple_reg (use)))
 465         {
 466           tree var;
 467
 468           if (is_gimple_debug (stmt))
 469             {
 470               if (gimple_debug_bind_p (stmt))
 471                 gimple_debug_bind_reset_value (stmt);
 472               else
 473                 gcc_unreachable ();
 474
 475               break;
 476             }
 477
 478           var = create_tmp_var (type_use, "var");
 479
 480           if (type_use != type_expr)
 481             expr = fold_convert (type_use, expr);
 482
 483           expr = build2 (MODIFY_EXPR, type_use, var, expr);
 484           expr = force_gimple_operand (expr, &stmts, true, NULL);
 485           gsi_insert_seq_before (insert_gsi, stmts, GSI_SAME_STMT);
 486         }
 487
 488       replace_exp (use_p, expr);
 489     }
 490
 491   update_stmt (stmt);
 492 }
 493
 494 /* Returns true if NAME is a parameter of SESE.  */
 495
 496 static bool
 497 is_parameter (sese region, tree name)
 498 {
 499   int i;
 500   tree p;
 501
 502   for (i = 0; VEC_iterate (tree, SESE_PARAMS (region), i, p); i++)
 503     if (p == name)
 504       return true;
 505
 506   return false;
 507 }
 508
 509 /* Returns true if NAME is an induction variable.  */
 510
 511 static bool
 512 is_iv (tree name)
 513 {
 514   return gimple_code (SSA_NAME_DEF_STMT (name)) == GIMPLE_PHI;
 515 }
 516
 517 static void expand_scalar_variables_stmt (gimple, basic_block, sese,
 518                                           htab_t, gimple_stmt_iterator *);
 519 static tree
 520 expand_scalar_variables_expr (tree, tree, enum tree_code, tree, basic_block,
 521                               sese, htab_t, gimple_stmt_iterator *);
 522
 523 static tree
 524 expand_scalar_variables_call (gimple stmt, basic_block bb, sese region,
 525                               htab_t map, gimple_stmt_iterator *gsi)
 526 {
 527   int i, nargs = gimple_call_num_args (stmt);
 528   VEC (tree, gc) *args = VEC_alloc (tree, gc, nargs);
 529   tree fn_type = TREE_TYPE (gimple_call_fn (stmt));
 530   tree fn = gimple_call_fndecl (stmt);
 531   tree call_expr, var, lhs;
 532   gimple call;
 533
 534   for (i = 0; i < nargs; i++)
 535     {
 536       tree arg = gimple_call_arg (stmt, i);
 537       tree t = TREE_TYPE (arg);
 538
 539       var = create_tmp_var (t, "var");
 540       arg = expand_scalar_variables_expr (t, arg, TREE_CODE (arg), NULL,
 541                                           bb, region, map, gsi);
 542       arg = build2 (MODIFY_EXPR, t, var, arg);
 543       arg = force_gimple_operand_gsi (gsi, arg, true, NULL,
 544                                       true, GSI_SAME_STMT);
 545       VEC_quick_push (tree, args, arg);
 546     }
 547
 548   lhs = gimple_call_lhs (stmt);
 549   var = create_tmp_var (TREE_TYPE (lhs), "var");
 550   call_expr = build_call_vec (fn_type, fn, args);
 551   call = gimple_build_call_from_tree (call_expr);
 552   var = make_ssa_name (var, call);
 553   gimple_call_set_lhs (call, var);
 554   gsi_insert_before (gsi, call, GSI_SAME_STMT);
 555
 556   return var;
 557 }
 558
 559 /* Copies at GSI all the scalar computations on which the ssa_name OP0
 560    depends on in the SESE: these are all the scalar variables used in
 561    the definition of OP0, that are defined outside BB and still in the
 562    SESE, i.e. not a parameter of the SESE.  The expression that is
 563    returned contains only induction variables from the generated code:
 564    MAP contains the induction variables renaming mapping, and is used
 565    to translate the names of induction variables.  */
 566
 567 static tree
 568 expand_scalar_variables_ssa_name (tree type, tree op0, basic_block bb,
 569                                   sese region, htab_t map,
 570                                   gimple_stmt_iterator *gsi)
 571 {
 572   gimple def_stmt;
 573   tree new_op;
 574
 575   if (is_parameter (region, op0)
 576       || is_iv (op0))
 577     return fold_convert (type, get_rename (map, op0));
 578
 579   def_stmt = SSA_NAME_DEF_STMT (op0);
 580
 581   /* Check whether we already have a rename for OP0.  */
 582   new_op = get_rename (map, op0);
 583
 584   if (new_op != op0
 585       && gimple_bb (SSA_NAME_DEF_STMT (new_op)) == bb)
 586     return fold_convert (type, new_op);
 587
 588   if (gimple_bb (def_stmt) == bb)
 589     {
 590       /* If the defining statement is in the basic block already
 591          we do not need to create a new expression for it, we
 592          only need to ensure its operands are expanded.  */
 593       expand_scalar_variables_stmt (def_stmt, bb, region, map, gsi);
 594       return fold_convert (type, new_op);
 595     }
 596   else
 597     {
 598       if (!gimple_bb (def_stmt)
 599           || !bb_in_sese_p (gimple_bb (def_stmt), region))
 600         return fold_convert (type, new_op);
 601
 602       switch (gimple_code (def_stmt))
 603         {
 604         case GIMPLE_ASSIGN:
 605           {
 606             tree var0 = gimple_assign_rhs1 (def_stmt);
 607             enum tree_code subcode = gimple_assign_rhs_code (def_stmt);
 608             tree var1 = gimple_assign_rhs2 (def_stmt);
 609             tree type = gimple_expr_type (def_stmt);
 610
 611             return expand_scalar_variables_expr (type, var0, subcode, var1, bb,
 612                                                  region, map, gsi);
 613           }
 614
 615         case GIMPLE_CALL:
 616           return expand_scalar_variables_call (def_stmt, bb, region, map, gsi);
 617
 618         default:
 619           gcc_unreachable ();
 620           return new_op;
 621         }
 622     }
 623 }
 624
 625 /* Copies at GSI all the scalar computations on which the expression
 626    OP0 CODE OP1 depends on in the SESE: these are all the scalar
 627    variables used in OP0 and OP1, defined outside BB and still defined
 628    in the SESE, i.e. not a parameter of the SESE.  The expression that
 629    is returned contains only induction variables from the generated
 630    code: MAP contains the induction variables renaming mapping, and is
 631    used to translate the names of induction variables.  */
 632
 633 static tree
 634 expand_scalar_variables_expr (tree type, tree op0, enum tree_code code,
 635                               tree op1, basic_block bb, sese region,
 636                               htab_t map, gimple_stmt_iterator *gsi)
 637 {
 638   if (TREE_CODE_CLASS (code) == tcc_constant
 639       || TREE_CODE_CLASS (code) == tcc_declaration)
 640     return op0;
 641
 642   /* For data references we have to duplicate also its memory
 643      indexing.  */
 644   if (TREE_CODE_CLASS (code) == tcc_reference)
 645     {
 646       switch (code)
 647         {
 648         case REALPART_EXPR:
 649         case IMAGPART_EXPR:
 650           {
 651             tree op = TREE_OPERAND (op0, 0);
 652             tree res = expand_scalar_variables_expr
 653               (type, op, TREE_CODE (op), NULL, bb, region, map, gsi);
 654             return build1 (code, type, res);
 655           }
 656
 657         case INDIRECT_REF:
 658           {
 659             tree old_name = TREE_OPERAND (op0, 0);
 660             tree expr = expand_scalar_variables_ssa_name
 661               (type, old_name, bb, region, map, gsi);
 662
 663             if (TREE_CODE (expr) != SSA_NAME
 664                 && is_gimple_reg (old_name))
 665               {
 666                 tree type = TREE_TYPE (old_name);
 667                 tree var = create_tmp_var (type, "var");
 668
 669                 expr = build2 (MODIFY_EXPR, type, var, expr);
 670                 expr = force_gimple_operand_gsi (gsi, expr, true, NULL,
 671                                                  true, GSI_SAME_STMT);
 672               }
 673
 674             return fold_build1 (code, type, expr);
 675           }
 676
 677         case ARRAY_REF:
 678           {
 679             tree op00 = TREE_OPERAND (op0, 0);
 680             tree op01 = TREE_OPERAND (op0, 1);
 681             tree op02 = TREE_OPERAND (op0, 2);
 682             tree op03 = TREE_OPERAND (op0, 3);
 683             tree base = expand_scalar_variables_expr
 684               (TREE_TYPE (op00), op00, TREE_CODE (op00), NULL, bb, region,
 685                map, gsi);
 686             tree subscript = expand_scalar_variables_expr
 687               (TREE_TYPE (op01), op01, TREE_CODE (op01), NULL, bb, region,
 688                map, gsi);
 689
 690             return build4 (ARRAY_REF, type, base, subscript, op02, op03);
 691           }
 692
 693         case COMPONENT_REF:
 694           return op0;
 695
 696         default:
 697           /* The above cases should catch everything.  */
 698           gcc_unreachable ();
 699         }
 700     }
 701
 702   if (TREE_CODE_CLASS (code) == tcc_unary)
 703     {
 704       tree op0_type = TREE_TYPE (op0);
 705       enum tree_code op0_code = TREE_CODE (op0);
 706       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
 707                                                     NULL, bb, region, map, gsi);
 708
 709       return fold_build1 (code, type, op0_expr);
 710     }
 711
 712   if (TREE_CODE_CLASS (code) == tcc_binary
 713       || TREE_CODE_CLASS (code) == tcc_comparison)
 714     {
 715       tree op0_type = TREE_TYPE (op0);
 716       enum tree_code op0_code = TREE_CODE (op0);
 717       tree op0_expr = expand_scalar_variables_expr (op0_type, op0, op0_code,
 718                                                     NULL, bb, region, map, gsi);
 719       tree op1_type = TREE_TYPE (op1);
 720       enum tree_code op1_code = TREE_CODE (op1);
 721       tree op1_expr = expand_scalar_variables_expr (op1_type, op1, op1_code,
 722                                                     NULL, bb, region, map, gsi);
 723
 724       return fold_build2 (code, type, op0_expr, op1_expr);
 725     }
 726
 727   if (code == SSA_NAME)
 728     return expand_scalar_variables_ssa_name (type, op0, bb, region, map, gsi);
 729
 730   if (code == ADDR_EXPR)
 731     {
 732       tree op00 = TREE_OPERAND (op0, 0);
 733
 734       if (handled_component_p (op00)
 735           && TREE_CODE (op00) == ARRAY_REF)
 736         {
 737           tree e = expand_scalar_variables_expr (TREE_TYPE (op00), op00,
 738                                                  TREE_CODE (op00),
 739                                                  NULL, bb, region, map, gsi);
 740           return fold_build1 (code, TREE_TYPE (op0), e);
 741         }
 742
 743       return op0;
 744     }
 745
 746   gcc_unreachable ();
 747   return NULL;
 748 }
 749
 750 /* Copies at the beginning of BB all the scalar computations on which
 751    STMT depends on in the SESE: these are all the scalar variables used
 752    in STMT, defined outside BB and still defined in the SESE, i.e. not a
 753    parameter of the SESE.  The expression that is returned contains
 754    only induction variables from the generated code: MAP contains the
 755    induction variables renaming mapping, and is used to translate the
 756    names of induction variables.  */
 757
 758 static void
 759 expand_scalar_variables_stmt (gimple stmt, basic_block bb, sese region,
 760                               htab_t map, gimple_stmt_iterator *gsi)
 761 {
 762   ssa_op_iter iter;
 763   use_operand_p use_p;
 764
 765   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
 766     {
 767       tree use = USE_FROM_PTR (use_p);
 768       tree type = TREE_TYPE (use);
 769       enum tree_code code = TREE_CODE (use);
 770       tree use_expr;
 771
 772       if (!is_gimple_reg (use))
 773         continue;
 774
 775       /* Don't expand USE if we already have a rename for it.  */
 776       use_expr = get_rename (map, use);
 777       if (use_expr != use)
 778         continue;
 779
 780       use_expr = expand_scalar_variables_expr (type, use, code, NULL, bb,
 781                                                region, map, gsi);
 782       use_expr = fold_convert (type, use_expr);
 783
 784       if (use_expr == use)
 785         continue;
 786
 787       if (is_gimple_debug (stmt))
 788         {
 789           if (gimple_debug_bind_p (stmt))
 790             gimple_debug_bind_reset_value (stmt);
 791           else
 792             gcc_unreachable ();
 793
 794           break;
 795         }
 796
 797       if (TREE_CODE (use_expr) != SSA_NAME)
 798         {
 799           tree var = create_tmp_var (type, "var");
 800
 801           use_expr = build2 (MODIFY_EXPR, type, var, use_expr);
 802           use_expr = force_gimple_operand_gsi (gsi, use_expr, true, NULL,
 803                                                true, GSI_SAME_STMT);
 804         }
 805
 806       replace_exp (use_p, use_expr);
 807     }
 808
 809   update_stmt (stmt);
 810 }
 811
 812 /* Copies at the beginning of BB all the scalar computations on which
 813    BB depends on in the SESE: these are all the scalar variables used
 814    in BB, defined outside BB and still defined in the SESE, i.e. not a
 815    parameter of the SESE.  The expression that is returned contains
 816    only induction variables from the generated code: MAP contains the
 817    induction variables renaming mapping, and is used to translate the
 818    names of induction variables.  */
 819
 820 static void
 821 expand_scalar_variables (basic_block bb, sese region, htab_t map)
 822 {
 823   gimple_stmt_iterator gsi;
 824
 825   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
 826     {
 827       gimple stmt = gsi_stmt (gsi);
 828       expand_scalar_variables_stmt (stmt, bb, region, map, &gsi);
 829       gsi_next (&gsi);
 830     }
 831 }
 832
 833 /* Rename all the SSA_NAMEs from block BB according to the MAP.  */
 834
 835 static void
 836 rename_variables (basic_block bb, htab_t map)
 837 {
 838   gimple_stmt_iterator gsi;
 839   gimple_stmt_iterator insert_gsi = gsi_start_bb (bb);
 840
 841   for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 842     rename_variables_in_stmt (gsi_stmt (gsi), map, &insert_gsi);
 843 }
 844
 845 /* Remove condition from BB.  */
 846
 847 static void
 848 remove_condition (basic_block bb)
 849 {
 850   gimple last = last_stmt (bb);
 851
 852   if (last && gimple_code (last) == GIMPLE_COND)
 853     {
 854       gimple_stmt_iterator gsi = gsi_last_bb (bb);
 855       gsi_remove (&gsi, true);
 856     }
 857 }
 858
 859 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set.  */
 860
 861 edge
 862 get_true_edge_from_guard_bb (basic_block bb)
 863 {
 864   edge e;
 865   edge_iterator ei;
 866
 867   FOR_EACH_EDGE (e, ei, bb->succs)
 868     if (e->flags & EDGE_TRUE_VALUE)
 869       return e;
 870
 871   gcc_unreachable ();
 872   return NULL;
 873 }
 874
 875 /* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag cleared.  */
 876
 877 edge
 878 get_false_edge_from_guard_bb (basic_block bb)
 879 {
 880   edge e;
 881   edge_iterator ei;
 882
 883   FOR_EACH_EDGE (e, ei, bb->succs)
 884     if (!(e->flags & EDGE_TRUE_VALUE))
 885       return e;
 886
 887   gcc_unreachable ();
 888   return NULL;
 889 }
 890
 891 /* Returns true when NAME is defined in LOOP.  */
 892
 893 static bool
 894 name_defined_in_loop_p (tree name, loop_p loop)
 895 {
 896   return !SSA_NAME_IS_DEFAULT_DEF (name)
 897     && gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father == loop;
 898 }
 899
 900 /* Returns true when EXPR contains SSA_NAMEs defined in LOOP.  */
 901
 902 static bool
 903 expr_defined_in_loop_p (tree expr, loop_p loop)
 904 {
 905   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
 906     {
 907     case 3:
 908       return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop)
 909         || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop)
 910         || expr_defined_in_loop_p (TREE_OPERAND (expr, 2), loop);
 911
 912     case 2:
 913       return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop)
 914         || expr_defined_in_loop_p (TREE_OPERAND (expr, 1), loop);
 915
 916     case 1:
 917       return expr_defined_in_loop_p (TREE_OPERAND (expr, 0), loop);
 918
 919     case 0:
 920       return TREE_CODE (expr) == SSA_NAME
 921         && name_defined_in_loop_p (expr, loop);
 922
 923     default:
 924       return false;
 925     }
 926 }
 927
 928 /* Returns the gimple statement that uses NAME outside the loop it is
 929    defined in, returns NULL if there is no such loop close phi node.
 930    An invariant of the loop closed SSA form is that the only use of a
 931    variable, outside the loop it is defined in, is in the loop close
 932    phi node that just follows the loop.  */
 933
 934 static gimple
 935 alive_after_loop (tree name)
 936 {
 937   use_operand_p use_p;
 938   imm_use_iterator imm_iter;
 939   loop_p loop = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_father;
 940
 941   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
 942     {
 943       gimple stmt = USE_STMT (use_p);
 944
 945       if (gimple_code (stmt) == GIMPLE_PHI
 946           && gimple_bb (stmt)->loop_father != loop)
 947         return stmt;
 948     }
 949
 950   return NULL;
 951 }
 952
 953 /* Return true if a close phi has not yet been inserted for the use of
 954    variable NAME on the single exit of LOOP.  */
 955
 956 static bool
 957 close_phi_not_yet_inserted_p (loop_p loop, tree name)
 958 {
 959   gimple_stmt_iterator psi;
 960   basic_block bb = single_exit (loop)->dest;
 961
 962   for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
 963     if (gimple_phi_arg_def (gsi_stmt (psi), 0) == name)
 964       return false;
 965
 966   return true;
 967 }
 968
 969 /* A structure for passing parameters to add_loop_exit_phis.  */
 970
 971 typedef struct alep {
 972   loop_p loop;
 973   VEC (rename_map_elt, heap) *new_renames;
 974 } *alep_p;
 975
 976 /* Helper function for htab_traverse in insert_loop_close_phis.  */
 977
 978 static int
 979 add_loop_exit_phis (void **slot, void *data)
 980 {
 981   struct rename_map_elt_s *entry;
 982   alep_p a;
 983   loop_p loop;
 984   tree expr, new_name, old_name;
 985   bool def_in_loop_p, used_outside_p, need_close_phi_p;
 986   gimple old_close_phi;
 987
 988   if (!slot || !*slot || !data)
 989     return 1;
 990
 991   entry = (struct rename_map_elt_s *) *slot;
 992   a = (alep_p) data;
 993   loop = a->loop;
 994   new_name = expr = entry->expr;
 995   old_name = entry->old_name;
 996
 997   def_in_loop_p = expr_defined_in_loop_p (expr, loop);
 998   if (!def_in_loop_p)
 999     return 1;
1000
1001   /* Remove the old rename from the map when the expression is defined
1002      in the loop that we're closing.  */
1003   free (*slot);
1004   *slot = NULL;
1005
1006   if (TREE_CODE (expr) != SSA_NAME)
1007     return 1;
1008
1009   old_close_phi = alive_after_loop (old_name);
1010   used_outside_p = (old_close_phi != NULL);
1011   need_close_phi_p = (used_outside_p
1012                       && close_phi_not_yet_inserted_p (loop, new_name));
1013
1014   /* Insert a loop close phi node.  */
1015   if (need_close_phi_p)
1016     {
1017       basic_block bb = single_exit (loop)->dest;
1018       gimple phi = create_phi_node (new_name, bb);
1019       tree new_res = create_new_def_for (gimple_phi_result (phi), phi,
1020                                          gimple_phi_result_ptr (phi));
1021
1022       add_phi_arg (phi, new_name, single_pred_edge (bb), UNKNOWN_LOCATION);
1023       VEC_safe_push (rename_map_elt, heap, a->new_renames,
1024                      new_rename_map_elt (gimple_phi_result (old_close_phi),
1025                                          new_res));
1026     }
1027
1028   return 1;
1029 }
1030
1031 /* Traverses MAP and removes from it all the tuples (OLD, NEW) where
1032    NEW is defined in LOOP.  Inserts on the exit of LOOP the close phi
1033    node "RES = phi (NEW)" corresponding to "OLD_RES = phi (OLD)" in
1034    the original code.  Inserts in MAP the tuple (OLD_RES, RES).  */
1035
1036 void
1037 insert_loop_close_phis (htab_t map, loop_p loop)
1038 {
1039   int i;
1040   struct alep a;
1041   rename_map_elt elt;
1042
1043   a.loop = loop;
1044   a.new_renames = VEC_alloc (rename_map_elt, heap, 3);
1045   update_ssa (TODO_update_ssa);
1046   htab_traverse (map, add_loop_exit_phis, &a);
1047   update_ssa (TODO_update_ssa);
1048
1049   for (i = 0; VEC_iterate (rename_map_elt, a.new_renames, i, elt); i++)
1050     {
1051       set_rename (map, elt->old_name, elt->expr);
1052       free (elt);
1053     }
1054
1055   VEC_free (rename_map_elt, heap, a.new_renames);
1056 }
1057
1058 /* Helper structure for htab_traverse in insert_guard_phis.  */
1059
1060 struct igp {
1061   basic_block bb;
1062   edge true_edge, false_edge;
1063   htab_t before_guard;
1064 };
1065
1066 /* Return the default name that is before the guard.  */
1067
1068 static tree
1069 default_before_guard (htab_t before_guard, tree old_name)
1070 {
1071   tree res = get_rename (before_guard, old_name);
1072
1073   if (res == old_name)
1074     {
1075       if (is_gimple_reg (res))
1076         return fold_convert (TREE_TYPE (res), integer_zero_node);
1077       return gimple_default_def (cfun, SSA_NAME_VAR (res));
1078     }
1079
1080   return res;
1081 }
1082
1083 /* Prepares EXPR to be a good phi argument when the phi result is
1084    RES.  Insert needed statements on edge E.  */
1085
1086 static tree
1087 convert_for_phi_arg (tree expr, tree res, edge e)
1088 {
1089   tree type = TREE_TYPE (res);
1090
1091   if (TREE_TYPE (expr) != type)
1092     expr = fold_convert (type, expr);
1093
1094   if (TREE_CODE (expr) != SSA_NAME
1095       && !is_gimple_min_invariant (expr))
1096     {
1097       tree var = create_tmp_var (type, "var");
1098       gimple_seq stmts;
1099
1100       expr = build2 (MODIFY_EXPR, type, var, expr);
1101       expr = force_gimple_operand (expr, &stmts, true, NULL);
1102       gsi_insert_seq_on_edge_immediate (e, stmts);
1103     }
1104
1105   return expr;
1106 }
1107
1108 /* Helper function for htab_traverse in insert_guard_phis.  */
1109
1110 static int
1111 add_guard_exit_phis (void **slot, void *s)
1112 {
1113   struct rename_map_elt_s *entry = (struct rename_map_elt_s *) *slot;
1114   struct igp *i = (struct igp *) s;
1115   basic_block bb = i->bb;
1116   edge true_edge = i->true_edge;
1117   edge false_edge = i->false_edge;
1118   tree res = entry->old_name;
1119   tree name1 = entry->expr;
1120   tree name2 = default_before_guard (i->before_guard, res);
1121   gimple phi;
1122
1123   /* Nothing to be merged if the name before the guard is the same as
1124      the one after.  */
1125   if (name1 == name2)
1126     return 1;
1127
1128   name1 = convert_for_phi_arg (name1, res, true_edge);
1129   name2 = convert_for_phi_arg (name2, res, false_edge);
1130
1131   phi = create_phi_node (res, bb);
1132   res = create_new_def_for (gimple_phi_result (phi), phi,
1133                             gimple_phi_result_ptr (phi));
1134
1135   add_phi_arg (phi, name1, true_edge, UNKNOWN_LOCATION);
1136   add_phi_arg (phi, name2, false_edge, UNKNOWN_LOCATION);
1137
1138   entry->expr = res;
1139   *slot = entry;
1140   return 1;
1141 }
1142
1143 /* Iterate over RENAME_MAP and get tuples of the form (OLD, NAME1).
1144    If there is a correspondent tuple (OLD, NAME2) in BEFORE_GUARD,
1145    with NAME1 different than NAME2, then insert in BB the phi node:
1146
1147    | RES = phi (NAME1 (on TRUE_EDGE), NAME2 (on FALSE_EDGE))"
1148
1149    if there is no tuple for OLD in BEFORE_GUARD, insert
1150
1151    | RES = phi (NAME1 (on TRUE_EDGE),
1152    |            DEFAULT_DEFINITION of NAME1 (on FALSE_EDGE))".
1153
1154    Finally register in RENAME_MAP the tuple (OLD, RES).  */
1155
1156 void
1157 insert_guard_phis (basic_block bb, edge true_edge, edge false_edge,
1158                    htab_t before_guard, htab_t rename_map)
1159 {
1160   struct igp i;
1161   i.bb = bb;
1162   i.true_edge = true_edge;
1163   i.false_edge = false_edge;
1164   i.before_guard = before_guard;
1165
1166   update_ssa (TODO_update_ssa);
1167   htab_traverse (rename_map, add_guard_exit_phis, &i);
1168   update_ssa (TODO_update_ssa);
1169 }
1170
1171 /* Create a duplicate of the basic block BB.  NOTE: This does not
1172    preserve SSA form.  */
1173
1174 static void
1175 graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb, htab_t map)
1176 {
1177   gimple_stmt_iterator gsi, gsi_tgt;
1178
1179   gsi_tgt = gsi_start_bb (new_bb);
1180   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1181     {
1182       def_operand_p def_p;
1183       ssa_op_iter op_iter;
1184       gimple stmt = gsi_stmt (gsi);
1185       gimple copy;
1186
1187       if (gimple_code (stmt) == GIMPLE_LABEL)
1188         continue;
1189
1190       /* Create a new copy of STMT and duplicate STMT's virtual
1191          operands.  */
1192       copy = gimple_copy (stmt);
1193       gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
1194       mark_sym_for_renaming (gimple_vop (cfun));
1195
1196       maybe_duplicate_eh_stmt (copy, stmt);
1197       gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
1198
1199       /* Create new names for all the definitions created by COPY and
1200          add replacement mappings for each new name.  */
1201       FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
1202         {
1203           tree old_name = DEF_FROM_PTR (def_p);
1204           tree new_name = create_new_def_for (old_name, copy, def_p);
1205           set_rename (map, old_name, new_name);
1206         }
1207     }
1208 }
1209
1210 /* Copies BB and includes in the copied BB all the statements that can
1211    be reached following the use-def chains from the memory accesses,
1212    and returns the next edge following this new block.  */
1213
1214 edge
1215 copy_bb_and_scalar_dependences (basic_block bb, sese region,
1216                                 edge next_e, htab_t map)
1217 {
1218   basic_block new_bb = split_edge (next_e);
1219
1220   next_e = single_succ_edge (new_bb);
1221   graphite_copy_stmts_from_block (bb, new_bb, map);
1222   remove_condition (new_bb);
1223   remove_phi_nodes (new_bb);
1224   expand_scalar_variables (new_bb, region, map);
1225   rename_variables (new_bb, map);
1226
1227   return next_e;
1228 }
1229
1230 /* Returns the outermost loop in SCOP that contains BB.  */
1231
1232 struct loop *
1233 outermost_loop_in_sese (sese region, basic_block bb)
1234 {
1235   struct loop *nest;
1236
1237   nest = bb->loop_father;
1238   while (loop_outer (nest)
1239          && loop_in_sese_p (loop_outer (nest), region))
1240     nest = loop_outer (nest);
1241
1242   return nest;
1243 }
1244
1245 /* Sets the false region of an IF_REGION to REGION.  */
1246
1247 void
1248 if_region_set_false_region (ifsese if_region, sese region)
1249 {
1250   basic_block condition = if_region_get_condition_block (if_region);
1251   edge false_edge = get_false_edge_from_guard_bb (condition);
1252   basic_block dummy = false_edge->dest;
1253   edge entry_region = SESE_ENTRY (region);
1254   edge exit_region = SESE_EXIT (region);
1255   basic_block before_region = entry_region->src;
1256   basic_block last_in_region = exit_region->src;
1257   void **slot = htab_find_slot_with_hash (current_loops->exits, exit_region,
1258                                           htab_hash_pointer (exit_region),
1259                                           NO_INSERT);
1260
1261   entry_region->flags = false_edge->flags;
1262   false_edge->flags = exit_region->flags;
1263
1264   redirect_edge_pred (entry_region, condition);
1265   redirect_edge_pred (exit_region, before_region);
1266   redirect_edge_pred (false_edge, last_in_region);
1267   redirect_edge_succ (false_edge, single_succ (dummy));
1268   delete_basic_block (dummy);
1269
1270   exit_region->flags = EDGE_FALLTHRU;
1271   recompute_all_dominators ();
1272
1273   SESE_EXIT (region) = false_edge;
1274
1275   if (if_region->false_region)
1276     free (if_region->false_region);
1277   if_region->false_region = region;
1278
1279   if (slot)
1280     {
1281       struct loop_exit *loop_exit = ggc_alloc_cleared_loop_exit ();
1282
1283       memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
1284       htab_clear_slot (current_loops->exits, slot);
1285
1286       slot = htab_find_slot_with_hash (current_loops->exits, false_edge,
1287                                        htab_hash_pointer (false_edge),
1288                                        INSERT);
1289       loop_exit->e = false_edge;
1290       *slot = loop_exit;
1291       false_edge->src->loop_father->exits->next = loop_exit;
1292     }
1293 }
1294
1295 /* Creates an IFSESE with CONDITION on edge ENTRY.  */
1296
1297 static ifsese
1298 create_if_region_on_edge (edge entry, tree condition)
1299 {
1300   edge e;
1301   edge_iterator ei;
1302   sese sese_region = XNEW (struct sese_s);
1303   sese true_region = XNEW (struct sese_s);
1304   sese false_region = XNEW (struct sese_s);
1305   ifsese if_region = XNEW (struct ifsese_s);
1306   edge exit = create_empty_if_region_on_edge (entry, condition);
1307
1308   if_region->region = sese_region;
1309   if_region->region->entry = entry;
1310   if_region->region->exit = exit;
1311
1312   FOR_EACH_EDGE (e, ei, entry->dest->succs)
1313     {
1314       if (e->flags & EDGE_TRUE_VALUE)
1315         {
1316           true_region->entry = e;
1317           true_region->exit = single_succ_edge (e->dest);
1318           if_region->true_region = true_region;
1319         }
1320       else if (e->flags & EDGE_FALSE_VALUE)
1321         {
1322           false_region->entry = e;
1323           false_region->exit = single_succ_edge (e->dest);
1324           if_region->false_region = false_region;
1325         }
1326     }
1327
1328   return if_region;
1329 }
1330
1331 /* Moves REGION in a condition expression:
1332    | if (1)
1333    |   ;
1334    | else
1335    |   REGION;
1336 */
1337
1338 ifsese
1339 move_sese_in_condition (sese region)
1340 {
1341   basic_block pred_block = split_edge (SESE_ENTRY (region));
1342   ifsese if_region;
1343
1344   SESE_ENTRY (region) = single_succ_edge (pred_block);
1345   if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
1346   if_region_set_false_region (if_region, region);
1347
1348   return if_region;
1349 }
1350
1351 /* Replaces the condition of the IF_REGION with CONDITION:
1352    | if (CONDITION)
1353    |   true_region;
1354    | else
1355    |   false_region;
1356 */
1357
1358 void
1359 set_ifsese_condition (ifsese if_region, tree condition)
1360 {
1361   sese region = if_region->region;
1362   edge entry = region->entry;
1363   basic_block bb = entry->dest;
1364   gimple last = last_stmt (bb);
1365   gimple_stmt_iterator gsi = gsi_last_bb (bb);
1366   gimple cond_stmt;
1367
1368   gcc_assert (gimple_code (last) == GIMPLE_COND);
1369
1370   gsi_remove (&gsi, true);
1371   gsi = gsi_last_bb (bb);
1372   condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
1373                                         false, GSI_NEW_STMT);
1374   cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
1375   gsi = gsi_last_bb (bb);
1376   gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
1377 }
1378
1379 /* Returns the scalar evolution of T in REGION.  Every variable that
1380    is not defined in the REGION is considered a parameter.  */
1381
1382 tree
1383 scalar_evolution_in_region (sese region, loop_p loop, tree t)
1384 {
1385   gimple def;
1386   struct loop *def_loop;
1387   basic_block before = block_before_sese (region);
1388
1389   if (TREE_CODE (t) != SSA_NAME
1390       || loop_in_sese_p (loop, region))
1391     return instantiate_scev (before, loop,
1392                              analyze_scalar_evolution (loop, t));
1393
1394   if (!defined_in_sese_p (t, region))
1395     return t;
1396
1397   def = SSA_NAME_DEF_STMT (t);
1398   def_loop = loop_containing_stmt (def);
1399
1400   if (loop_in_sese_p (def_loop, region))
1401     {
1402       t = analyze_scalar_evolution (def_loop, t);
1403       def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
1404       t = compute_overall_effect_of_inner_loop (def_loop, t);
1405       return t;
1406     }
1407   else
1408     return instantiate_scev (before, loop, t);
1409 }