Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / sese.c
1 /* Single entry single exit control flow regions.
2    Copyright (C) 2008-2015 Free Software Foundation, Inc.
3    Contributed by Jan Sjodin <jan.sjodin@amd.com> and
4    Sebastian Pop <sebastian.pop@amd.com>.
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
12
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "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
76 bool
77 debug_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 \f
88
89 /* Hashtable helpers.  */
90
91 struct 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
98 inline hashval_t
99 rename_map_hasher::hash (tree old_name)
100 {
101   return SSA_NAME_VERSION (old_name);
102 }
103
104 typedef hash_map<tree, tree, rename_map_hasher> rename_map_type;
105 \f
106
107 /* Print to stderr all the elements of RENAME_MAP.  */
108
109 DEBUG_FUNCTION void
110 debug_rename_map (rename_map_type *rename_map)
111 {
112   rename_map->traverse <void *, debug_rename_map_1> (NULL);
113 }
114 \f
115
116 /* Record LOOP as occurring in REGION.  */
117
118 static void
119 sese_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
131 void
132 build_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
169 static void
170 sese_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
193 static void
194 sese_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
223 static bool
224 sese_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
253 static void
254 sese_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
281 static void
282 sese_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
295 sese
296 new_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
312 void
313 free_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
326 static void
327 sese_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
346 void
347 sese_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
366 edge
367 get_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
382 edge
383 get_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
398 static tree
399 get_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
411 static void
412 set_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
427 static bool
428 rename_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
533 static void
534 graphite_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
597 edge
598 copy_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
615 struct loop *
616 outermost_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
630 void
631 if_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
679 static ifsese
680 create_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
720 ifsese
721 move_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
740 void
741 set_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
764 tree
765 scalar_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 }