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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [sese.c] - Blame information for rev 859

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

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

powered by: WebSVN 2.1.0

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