OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [sese.c] - Blame information for rev 714

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.