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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-ssa-loop-manip.c] - Blame information for rev 38

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

Line No. Rev Author Line
1 38 julius
/* High-level loop manipulation functions.
2
   Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3
 
4
This file is part of GCC.
5
 
6
GCC is free software; you can redistribute it and/or modify it
7
under the terms of the GNU General Public License as published by the
8
Free Software Foundation; either version 3, or (at your option) any
9
later version.
10
 
11
GCC is distributed in the hope that it will be useful, but WITHOUT
12
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14
for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GCC; see the file COPYING3.  If not see
18
<http://www.gnu.org/licenses/>.  */
19
 
20
#include "config.h"
21
#include "system.h"
22
#include "coretypes.h"
23
#include "tm.h"
24
#include "tree.h"
25
#include "rtl.h"
26
#include "tm_p.h"
27
#include "hard-reg-set.h"
28
#include "basic-block.h"
29
#include "output.h"
30
#include "diagnostic.h"
31
#include "tree-flow.h"
32
#include "tree-dump.h"
33
#include "timevar.h"
34
#include "cfgloop.h"
35
#include "tree-pass.h"
36
#include "cfglayout.h"
37
#include "tree-scalar-evolution.h"
38
#include "params.h"
39
 
40
/* Creates an induction variable with value BASE + STEP * iteration in LOOP.
41
   It is expected that neither BASE nor STEP are shared with other expressions
42
   (unless the sharing rules allow this).  Use VAR as a base var_decl for it
43
   (if NULL, a new temporary will be created).  The increment will occur at
44
   INCR_POS (after it if AFTER is true, before it otherwise).  INCR_POS and
45
   AFTER can be computed using standard_iv_increment_position.  The ssa versions
46
   of the variable before and after increment will be stored in VAR_BEFORE and
47
   VAR_AFTER (unless they are NULL).  */
48
 
49
void
50
create_iv (tree base, tree step, tree var, struct loop *loop,
51
           block_stmt_iterator *incr_pos, bool after,
52
           tree *var_before, tree *var_after)
53
{
54
  tree stmt, initial, step1, stmts;
55
  tree vb, va;
56
  enum tree_code incr_op = PLUS_EXPR;
57
  edge pe = loop_preheader_edge (loop);
58
 
59
  if (!var)
60
    {
61
      var = create_tmp_var (TREE_TYPE (base), "ivtmp");
62
      add_referenced_var (var);
63
    }
64
 
65
  vb = make_ssa_name (var, NULL_TREE);
66
  if (var_before)
67
    *var_before = vb;
68
  va = make_ssa_name (var, NULL_TREE);
69
  if (var_after)
70
    *var_after = va;
71
 
72
  /* For easier readability of the created code, produce MINUS_EXPRs
73
     when suitable.  */
74
  if (TREE_CODE (step) == INTEGER_CST)
75
    {
76
      if (TYPE_UNSIGNED (TREE_TYPE (step)))
77
        {
78
          step1 = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
79
          if (tree_int_cst_lt (step1, step))
80
            {
81
              incr_op = MINUS_EXPR;
82
              step = step1;
83
            }
84
        }
85
      else
86
        {
87
          bool ovf;
88
 
89
          if (!tree_expr_nonnegative_warnv_p (step, &ovf)
90
              && may_negate_without_overflow_p (step))
91
            {
92
              incr_op = MINUS_EXPR;
93
              step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
94
            }
95
        }
96
    }
97
 
98
  /* Gimplify the step if necessary.  We put the computations in front of the
99
     loop (i.e. the step should be loop invariant).  */
100
  step = force_gimple_operand (step, &stmts, true, var);
101
  if (stmts)
102
    bsi_insert_on_edge_immediate_loop (pe, stmts);
103
 
104
  stmt = build2 (MODIFY_EXPR, void_type_node, va,
105
                 build2 (incr_op, TREE_TYPE (base),
106
                         vb, step));
107
  SSA_NAME_DEF_STMT (va) = stmt;
108
  if (after)
109
    bsi_insert_after (incr_pos, stmt, BSI_NEW_STMT);
110
  else
111
    bsi_insert_before (incr_pos, stmt, BSI_NEW_STMT);
112
 
113
  initial = force_gimple_operand (base, &stmts, true, var);
114
  if (stmts)
115
    bsi_insert_on_edge_immediate_loop (pe, stmts);
116
 
117
  stmt = create_phi_node (vb, loop->header);
118
  SSA_NAME_DEF_STMT (vb) = stmt;
119
  add_phi_arg (stmt, initial, loop_preheader_edge (loop));
120
  add_phi_arg (stmt, va, loop_latch_edge (loop));
121
}
122
 
123
/* Add exit phis for the USE on EXIT.  */
124
 
125
static void
126
add_exit_phis_edge (basic_block exit, tree use)
127
{
128
  tree phi, def_stmt = SSA_NAME_DEF_STMT (use);
129
  basic_block def_bb = bb_for_stmt (def_stmt);
130
  struct loop *def_loop;
131
  edge e;
132
  edge_iterator ei;
133
 
134
  /* Check that some of the edges entering the EXIT block exits a loop in
135
     that USE is defined.  */
136
  FOR_EACH_EDGE (e, ei, exit->preds)
137
    {
138
      def_loop = find_common_loop (def_bb->loop_father, e->src->loop_father);
139
      if (!flow_bb_inside_loop_p (def_loop, e->dest))
140
        break;
141
    }
142
 
143
  if (!e)
144
    return;
145
 
146
  phi = create_phi_node (use, exit);
147
  create_new_def_for (PHI_RESULT (phi), phi, PHI_RESULT_PTR (phi));
148
  FOR_EACH_EDGE (e, ei, exit->preds)
149
    add_phi_arg (phi, use, e);
150
}
151
 
152
/* Add exit phis for VAR that is used in LIVEIN.
153
   Exits of the loops are stored in EXITS.  */
154
 
155
static void
156
add_exit_phis_var (tree var, bitmap livein, bitmap exits)
157
{
158
  bitmap def;
159
  unsigned index;
160
  basic_block def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (var));
161
  bitmap_iterator bi;
162
 
163
  if (is_gimple_reg (var))
164
    bitmap_clear_bit (livein, def_bb->index);
165
  else
166
    bitmap_set_bit (livein, def_bb->index);
167
 
168
  def = BITMAP_ALLOC (NULL);
169
  bitmap_set_bit (def, def_bb->index);
170
  compute_global_livein (livein, def);
171
  BITMAP_FREE (def);
172
 
173
  EXECUTE_IF_AND_IN_BITMAP (exits, livein, 0, index, bi)
174
    {
175
      add_exit_phis_edge (BASIC_BLOCK (index), var);
176
    }
177
}
178
 
179
/* Add exit phis for the names marked in NAMES_TO_RENAME.
180
   Exits of the loops are stored in EXITS.  Sets of blocks where the ssa
181
   names are used are stored in USE_BLOCKS.  */
182
 
183
static void
184
add_exit_phis (bitmap names_to_rename, bitmap *use_blocks, bitmap loop_exits)
185
{
186
  unsigned i;
187
  bitmap_iterator bi;
188
 
189
  EXECUTE_IF_SET_IN_BITMAP (names_to_rename, 0, i, bi)
190
    {
191
      add_exit_phis_var (ssa_name (i), use_blocks[i], loop_exits);
192
    }
193
}
194
 
195
/* Returns a bitmap of all loop exit edge targets.  */
196
 
197
static bitmap
198
get_loops_exits (void)
199
{
200
  bitmap exits = BITMAP_ALLOC (NULL);
201
  basic_block bb;
202
  edge e;
203
  edge_iterator ei;
204
 
205
  FOR_EACH_BB (bb)
206
    {
207
      FOR_EACH_EDGE (e, ei, bb->preds)
208
        if (e->src != ENTRY_BLOCK_PTR
209
            && !flow_bb_inside_loop_p (e->src->loop_father, bb))
210
          {
211
            bitmap_set_bit (exits, bb->index);
212
            break;
213
          }
214
    }
215
 
216
  return exits;
217
}
218
 
219
/* For USE in BB, if it is used outside of the loop it is defined in,
220
   mark it for rewrite.  Record basic block BB where it is used
221
   to USE_BLOCKS.  Record the ssa name index to NEED_PHIS bitmap.  */
222
 
223
static void
224
find_uses_to_rename_use (basic_block bb, tree use, bitmap *use_blocks,
225
                         bitmap need_phis)
226
{
227
  unsigned ver;
228
  basic_block def_bb;
229
  struct loop *def_loop;
230
 
231
  if (TREE_CODE (use) != SSA_NAME)
232
    return;
233
 
234
  /* We don't need to keep virtual operands in loop-closed form.  */
235
  if (!is_gimple_reg (use))
236
    return;
237
 
238
  ver = SSA_NAME_VERSION (use);
239
  def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (use));
240
  if (!def_bb)
241
    return;
242
  def_loop = def_bb->loop_father;
243
 
244
  /* If the definition is not inside loop, it is not interesting.  */
245
  if (!def_loop->outer)
246
    return;
247
 
248
  if (!use_blocks[ver])
249
    use_blocks[ver] = BITMAP_ALLOC (NULL);
250
  bitmap_set_bit (use_blocks[ver], bb->index);
251
 
252
  bitmap_set_bit (need_phis, ver);
253
}
254
 
255
/* For uses in STMT, mark names that are used outside of the loop they are
256
   defined to rewrite.  Record the set of blocks in that the ssa
257
   names are defined to USE_BLOCKS and the ssa names themselves to
258
   NEED_PHIS.  */
259
 
260
static void
261
find_uses_to_rename_stmt (tree stmt, bitmap *use_blocks, bitmap need_phis)
262
{
263
  ssa_op_iter iter;
264
  tree var;
265
  basic_block bb = bb_for_stmt (stmt);
266
 
267
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
268
    find_uses_to_rename_use (bb, var, use_blocks, need_phis);
269
}
270
 
271
/* Marks names that are used in BB and outside of the loop they are
272
   defined in for rewrite.  Records the set of blocks in that the ssa
273
   names are defined to USE_BLOCKS.  Record the SSA names that will
274
   need exit PHIs in NEED_PHIS.  */
275
 
276
static void
277
find_uses_to_rename_bb (basic_block bb, bitmap *use_blocks, bitmap need_phis)
278
{
279
  block_stmt_iterator bsi;
280
  edge e;
281
  edge_iterator ei;
282
  tree phi;
283
 
284
  FOR_EACH_EDGE (e, ei, bb->succs)
285
    for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
286
      find_uses_to_rename_use (bb, PHI_ARG_DEF_FROM_EDGE (phi, e),
287
                               use_blocks, need_phis);
288
 
289
  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
290
    find_uses_to_rename_stmt (bsi_stmt (bsi), use_blocks, need_phis);
291
}
292
 
293
/* Marks names that are used outside of the loop they are defined in
294
   for rewrite.  Records the set of blocks in that the ssa
295
   names are defined to USE_BLOCKS.  If CHANGED_BBS is not NULL,
296
   scan only blocks in this set.  */
297
 
298
static void
299
find_uses_to_rename (bitmap changed_bbs, bitmap *use_blocks, bitmap need_phis)
300
{
301
  basic_block bb;
302
  unsigned index;
303
  bitmap_iterator bi;
304
 
305
  if (changed_bbs && !bitmap_empty_p (changed_bbs))
306
    {
307
      EXECUTE_IF_SET_IN_BITMAP (changed_bbs, 0, index, bi)
308
        {
309
          find_uses_to_rename_bb (BASIC_BLOCK (index), use_blocks, need_phis);
310
        }
311
    }
312
  else
313
    {
314
      FOR_EACH_BB (bb)
315
        {
316
          find_uses_to_rename_bb (bb, use_blocks, need_phis);
317
        }
318
    }
319
}
320
 
321
/* Rewrites the program into a loop closed ssa form -- i.e. inserts extra
322
   phi nodes to ensure that no variable is used outside the loop it is
323
   defined in.
324
 
325
   This strengthening of the basic ssa form has several advantages:
326
 
327
   1) Updating it during unrolling/peeling/versioning is trivial, since
328
      we do not need to care about the uses outside of the loop.
329
   2) The behavior of all uses of an induction variable is the same.
330
      Without this, you need to distinguish the case when the variable
331
      is used outside of the loop it is defined in, for example
332
 
333
      for (i = 0; i < 100; i++)
334
        {
335
          for (j = 0; j < 100; j++)
336
            {
337
              k = i + j;
338
              use1 (k);
339
            }
340
          use2 (k);
341
        }
342
 
343
      Looking from the outer loop with the normal SSA form, the first use of k
344
      is not well-behaved, while the second one is an induction variable with
345
      base 99 and step 1.
346
 
347
      If CHANGED_BBS is not NULL, we look for uses outside loops only in
348
      the basic blocks in this set.
349
 
350
      UPDATE_FLAG is used in the call to update_ssa.  See
351
      TODO_update_ssa* for documentation.  */
352
 
353
void
354
rewrite_into_loop_closed_ssa (bitmap changed_bbs, unsigned update_flag)
355
{
356
  bitmap loop_exits = get_loops_exits ();
357
  bitmap *use_blocks;
358
  unsigned i, old_num_ssa_names;
359
  bitmap names_to_rename = BITMAP_ALLOC (NULL);
360
 
361
  /* If the pass has caused the SSA form to be out-of-date, update it
362
     now.  */
363
  update_ssa (update_flag);
364
 
365
  old_num_ssa_names = num_ssa_names;
366
  use_blocks = XCNEWVEC (bitmap, old_num_ssa_names);
367
 
368
  /* Find the uses outside loops.  */
369
  find_uses_to_rename (changed_bbs, use_blocks, names_to_rename);
370
 
371
  /* Add the PHI nodes on exits of the loops for the names we need to
372
     rewrite.  */
373
  add_exit_phis (names_to_rename, use_blocks, loop_exits);
374
 
375
  for (i = 0; i < old_num_ssa_names; i++)
376
    BITMAP_FREE (use_blocks[i]);
377
  free (use_blocks);
378
  BITMAP_FREE (loop_exits);
379
  BITMAP_FREE (names_to_rename);
380
 
381
  /* Fix up all the names found to be used outside their original
382
     loops.  */
383
  update_ssa (TODO_update_ssa);
384
}
385
 
386
/* Check invariants of the loop closed ssa form for the USE in BB.  */
387
 
388
static void
389
check_loop_closed_ssa_use (basic_block bb, tree use)
390
{
391
  tree def;
392
  basic_block def_bb;
393
 
394
  if (TREE_CODE (use) != SSA_NAME || !is_gimple_reg (use))
395
    return;
396
 
397
  def = SSA_NAME_DEF_STMT (use);
398
  def_bb = bb_for_stmt (def);
399
  gcc_assert (!def_bb
400
              || flow_bb_inside_loop_p (def_bb->loop_father, bb));
401
}
402
 
403
/* Checks invariants of loop closed ssa form in statement STMT in BB.  */
404
 
405
static void
406
check_loop_closed_ssa_stmt (basic_block bb, tree stmt)
407
{
408
  ssa_op_iter iter;
409
  tree var;
410
 
411
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
412
    check_loop_closed_ssa_use (bb, var);
413
}
414
 
415
/* Checks that invariants of the loop closed ssa form are preserved.  */
416
 
417
void
418
verify_loop_closed_ssa (void)
419
{
420
  basic_block bb;
421
  block_stmt_iterator bsi;
422
  tree phi;
423
  unsigned i;
424
 
425
  if (current_loops == NULL)
426
    return;
427
 
428
  verify_ssa (false);
429
 
430
  FOR_EACH_BB (bb)
431
    {
432
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
433
        for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
434
          check_loop_closed_ssa_use (PHI_ARG_EDGE (phi, i)->src,
435
                                     PHI_ARG_DEF (phi, i));
436
 
437
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
438
        check_loop_closed_ssa_stmt (bb, bsi_stmt (bsi));
439
    }
440
}
441
 
442
/* Split loop exit edge EXIT.  The things are a bit complicated by a need to
443
   preserve the loop closed ssa form.  */
444
 
445
void
446
split_loop_exit_edge (edge exit)
447
{
448
  basic_block dest = exit->dest;
449
  basic_block bb = loop_split_edge_with (exit, NULL);
450
  tree phi, new_phi, new_name, name;
451
  use_operand_p op_p;
452
 
453
  for (phi = phi_nodes (dest); phi; phi = PHI_CHAIN (phi))
454
    {
455
      op_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, single_succ_edge (bb));
456
 
457
      name = USE_FROM_PTR (op_p);
458
 
459
      /* If the argument of the phi node is a constant, we do not need
460
         to keep it inside loop.  */
461
      if (TREE_CODE (name) != SSA_NAME)
462
        continue;
463
 
464
      /* Otherwise create an auxiliary phi node that will copy the value
465
         of the ssa name out of the loop.  */
466
      new_name = duplicate_ssa_name (name, NULL);
467
      new_phi = create_phi_node (new_name, bb);
468
      SSA_NAME_DEF_STMT (new_name) = new_phi;
469
      add_phi_arg (new_phi, name, exit);
470
      SET_USE (op_p, new_name);
471
    }
472
}
473
 
474
/* Insert statement STMT to the edge E and update the loop structures.
475
   Returns the newly created block (if any).  */
476
 
477
basic_block
478
bsi_insert_on_edge_immediate_loop (edge e, tree stmt)
479
{
480
  basic_block src, dest, new_bb;
481
  struct loop *loop_c;
482
 
483
  src = e->src;
484
  dest = e->dest;
485
 
486
  loop_c = find_common_loop (src->loop_father, dest->loop_father);
487
 
488
  new_bb = bsi_insert_on_edge_immediate (e, stmt);
489
 
490
  if (!new_bb)
491
    return NULL;
492
 
493
  add_bb_to_loop (new_bb, loop_c);
494
  if (dest->loop_father->latch == src)
495
    dest->loop_father->latch = new_bb;
496
 
497
  return new_bb;
498
}
499
 
500
/* Returns the basic block in that statements should be emitted for induction
501
   variables incremented at the end of the LOOP.  */
502
 
503
basic_block
504
ip_end_pos (struct loop *loop)
505
{
506
  return loop->latch;
507
}
508
 
509
/* Returns the basic block in that statements should be emitted for induction
510
   variables incremented just before exit condition of a LOOP.  */
511
 
512
basic_block
513
ip_normal_pos (struct loop *loop)
514
{
515
  tree last;
516
  basic_block bb;
517
  edge exit;
518
 
519
  if (!single_pred_p (loop->latch))
520
    return NULL;
521
 
522
  bb = single_pred (loop->latch);
523
  last = last_stmt (bb);
524
  if (TREE_CODE (last) != COND_EXPR)
525
    return NULL;
526
 
527
  exit = EDGE_SUCC (bb, 0);
528
  if (exit->dest == loop->latch)
529
    exit = EDGE_SUCC (bb, 1);
530
 
531
  if (flow_bb_inside_loop_p (loop, exit->dest))
532
    return NULL;
533
 
534
  return bb;
535
}
536
 
537
/* Stores the standard position for induction variable increment in LOOP
538
   (just before the exit condition if it is available and latch block is empty,
539
   end of the latch block otherwise) to BSI.  INSERT_AFTER is set to true if
540
   the increment should be inserted after *BSI.  */
541
 
542
void
543
standard_iv_increment_position (struct loop *loop, block_stmt_iterator *bsi,
544
                                bool *insert_after)
545
{
546
  basic_block bb = ip_normal_pos (loop), latch = ip_end_pos (loop);
547
  tree last = last_stmt (latch);
548
 
549
  if (!bb
550
      || (last && TREE_CODE (last) != LABEL_EXPR))
551
    {
552
      *bsi = bsi_last (latch);
553
      *insert_after = true;
554
    }
555
  else
556
    {
557
      *bsi = bsi_last (bb);
558
      *insert_after = false;
559
    }
560
}
561
 
562
/* Copies phi node arguments for duplicated blocks.  The index of the first
563
   duplicated block is FIRST_NEW_BLOCK.  */
564
 
565
static void
566
copy_phi_node_args (unsigned first_new_block)
567
{
568
  unsigned i;
569
 
570
  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
571
    BASIC_BLOCK (i)->flags |= BB_DUPLICATED;
572
 
573
  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
574
    add_phi_args_after_copy_bb (BASIC_BLOCK (i));
575
 
576
  for (i = first_new_block; i < (unsigned) last_basic_block; i++)
577
    BASIC_BLOCK (i)->flags &= ~BB_DUPLICATED;
578
}
579
 
580
 
581
/* The same as cfgloopmanip.c:duplicate_loop_to_header_edge, but also
582
   updates the PHI nodes at start of the copied region.  In order to
583
   achieve this, only loops whose exits all lead to the same location
584
   are handled.
585
 
586
   Notice that we do not completely update the SSA web after
587
   duplication.  The caller is responsible for calling update_ssa
588
   after the loop has been duplicated.  */
589
 
590
bool
591
tree_duplicate_loop_to_header_edge (struct loop *loop, edge e,
592
                                    struct loops *loops,
593
                                    unsigned int ndupl, sbitmap wont_exit,
594
                                    edge orig, edge *to_remove,
595
                                    unsigned int *n_to_remove, int flags)
596
{
597
  unsigned first_new_block;
598
 
599
  if (!(loops->state & LOOPS_HAVE_SIMPLE_LATCHES))
600
    return false;
601
  if (!(loops->state & LOOPS_HAVE_PREHEADERS))
602
    return false;
603
 
604
#ifdef ENABLE_CHECKING
605
  verify_loop_closed_ssa ();
606
#endif
607
 
608
  first_new_block = last_basic_block;
609
  if (!duplicate_loop_to_header_edge (loop, e, loops, ndupl, wont_exit,
610
                                      orig, to_remove, n_to_remove, flags))
611
    return false;
612
 
613
  /* Readd the removed phi args for e.  */
614
  flush_pending_stmts (e);
615
 
616
  /* Copy the phi node arguments.  */
617
  copy_phi_node_args (first_new_block);
618
 
619
  scev_reset ();
620
 
621
  return true;
622
}
623
 
624
/* Build if (COND) goto THEN_LABEL; else goto ELSE_LABEL;  */
625
 
626
static tree
627
build_if_stmt (tree cond, tree then_label, tree else_label)
628
{
629
  return build3 (COND_EXPR, void_type_node,
630
                 cond,
631
                 build1 (GOTO_EXPR, void_type_node, then_label),
632
                 build1 (GOTO_EXPR, void_type_node, else_label));
633
}
634
 
635
/* Returns true if we can unroll LOOP FACTOR times.  Number
636
   of iterations of the loop is returned in NITER.  */
637
 
638
bool
639
can_unroll_loop_p (struct loop *loop, unsigned factor,
640
                   struct tree_niter_desc *niter)
641
{
642
  edge exit;
643
 
644
  /* Check whether unrolling is possible.  We only want to unroll loops
645
     for that we are able to determine number of iterations.  We also
646
     want to split the extra iterations of the loop from its end,
647
     therefore we require that the loop has precisely one
648
     exit.  */
649
 
650
  exit = single_dom_exit (loop);
651
  if (!exit)
652
    return false;
653
 
654
  if (!number_of_iterations_exit (loop, exit, niter, false)
655
      || niter->cmp == ERROR_MARK
656
      /* Scalar evolutions analysis might have copy propagated
657
         the abnormal ssa names into these expressions, hence
658
         emiting the computations based on them during loop
659
         unrolling might create overlapping life ranges for
660
         them, and failures in out-of-ssa.  */
661
      || contains_abnormal_ssa_name_p (niter->may_be_zero)
662
      || contains_abnormal_ssa_name_p (niter->control.base)
663
      || contains_abnormal_ssa_name_p (niter->control.step)
664
      || contains_abnormal_ssa_name_p (niter->bound))
665
    return false;
666
 
667
  /* And of course, we must be able to duplicate the loop.  */
668
  if (!can_duplicate_loop_p (loop))
669
    return false;
670
 
671
  /* The final loop should be small enough.  */
672
  if (tree_num_loop_insns (loop) * factor
673
      > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
674
    return false;
675
 
676
  return true;
677
}
678
 
679
/* Determines the conditions that control execution of LOOP unrolled FACTOR
680
   times.  DESC is number of iterations of LOOP.  ENTER_COND is set to
681
   condition that must be true if the main loop can be entered.
682
   EXIT_BASE, EXIT_STEP, EXIT_CMP and EXIT_BOUND are set to values describing
683
   how the exit from the unrolled loop should be controlled.  */
684
 
685
static void
686
determine_exit_conditions (struct loop *loop, struct tree_niter_desc *desc,
687
                           unsigned factor, tree *enter_cond,
688
                           tree *exit_base, tree *exit_step,
689
                           enum tree_code *exit_cmp, tree *exit_bound)
690
{
691
  tree stmts;
692
  tree base = desc->control.base;
693
  tree step = desc->control.step;
694
  tree bound = desc->bound;
695
  tree type = TREE_TYPE (base);
696
  tree bigstep, delta;
697
  tree min = lower_bound_in_type (type, type);
698
  tree max = upper_bound_in_type (type, type);
699
  enum tree_code cmp = desc->cmp;
700
  tree cond = boolean_true_node, assum;
701
 
702
  *enter_cond = boolean_false_node;
703
  *exit_base = NULL_TREE;
704
  *exit_step = NULL_TREE;
705
  *exit_cmp = ERROR_MARK;
706
  *exit_bound = NULL_TREE;
707
  gcc_assert (cmp != ERROR_MARK);
708
 
709
  /* We only need to be correct when we answer question
710
     "Do at least FACTOR more iterations remain?" in the unrolled loop.
711
     Thus, transforming BASE + STEP * i <> BOUND to
712
     BASE + STEP * i < BOUND is ok.  */
713
  if (cmp == NE_EXPR)
714
    {
715
      if (tree_int_cst_sign_bit (step))
716
        cmp = GT_EXPR;
717
      else
718
        cmp = LT_EXPR;
719
    }
720
  else if (cmp == LT_EXPR)
721
    {
722
      gcc_assert (!tree_int_cst_sign_bit (step));
723
    }
724
  else if (cmp == GT_EXPR)
725
    {
726
      gcc_assert (tree_int_cst_sign_bit (step));
727
    }
728
  else
729
    gcc_unreachable ();
730
 
731
  /* The main body of the loop may be entered iff:
732
 
733
     1) desc->may_be_zero is false.
734
     2) it is possible to check that there are at least FACTOR iterations
735
        of the loop, i.e., BOUND - step * FACTOR does not overflow.
736
     3) # of iterations is at least FACTOR  */
737
 
738
  if (!zero_p (desc->may_be_zero))
739
    cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
740
                        invert_truthvalue (desc->may_be_zero),
741
                        cond);
742
 
743
  bigstep = fold_build2 (MULT_EXPR, type, step,
744
                         build_int_cst_type (type, factor));
745
  delta = fold_build2 (MINUS_EXPR, type, bigstep, step);
746
  if (cmp == LT_EXPR)
747
    assum = fold_build2 (GE_EXPR, boolean_type_node,
748
                         bound,
749
                         fold_build2 (PLUS_EXPR, type, min, delta));
750
  else
751
    assum = fold_build2 (LE_EXPR, boolean_type_node,
752
                         bound,
753
                         fold_build2 (PLUS_EXPR, type, max, delta));
754
  cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
755
 
756
  bound = fold_build2 (MINUS_EXPR, type, bound, delta);
757
  assum = fold_build2 (cmp, boolean_type_node, base, bound);
758
  cond = fold_build2 (TRUTH_AND_EXPR, boolean_type_node, assum, cond);
759
 
760
  cond = force_gimple_operand (unshare_expr (cond), &stmts, false, NULL_TREE);
761
  if (stmts)
762
    bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
763
  /* cond now may be a gimple comparison, which would be OK, but also any
764
     other gimple rhs (say a && b).  In this case we need to force it to
765
     operand.  */
766
  if (!is_gimple_condexpr (cond))
767
    {
768
      cond = force_gimple_operand (cond, &stmts, true, NULL_TREE);
769
      if (stmts)
770
        bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
771
    }
772
  *enter_cond = cond;
773
 
774
  base = force_gimple_operand (unshare_expr (base), &stmts, true, NULL_TREE);
775
  if (stmts)
776
    bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
777
  bound = force_gimple_operand (unshare_expr (bound), &stmts, true, NULL_TREE);
778
  if (stmts)
779
    bsi_insert_on_edge_immediate_loop (loop_preheader_edge (loop), stmts);
780
 
781
  *exit_base = base;
782
  *exit_step = bigstep;
783
  *exit_cmp = cmp;
784
  *exit_bound = bound;
785
}
786
 
787
/* Unroll LOOP FACTOR times.  LOOPS is the loops tree.  DESC describes
788
   number of iterations of LOOP.  EXIT is the exit of the loop to that
789
   DESC corresponds.
790
 
791
   If N is number of iterations of the loop and MAY_BE_ZERO is the condition
792
   under that loop exits in the first iteration even if N != 0,
793
 
794
   while (1)
795
     {
796
       x = phi (init, next);
797
 
798
       pre;
799
       if (st)
800
         break;
801
       post;
802
     }
803
 
804
   becomes (with possibly the exit conditions formulated a bit differently,
805
   avoiding the need to create a new iv):
806
 
807
   if (MAY_BE_ZERO || N < FACTOR)
808
     goto rest;
809
 
810
   do
811
     {
812
       x = phi (init, next);
813
 
814
       pre;
815
       post;
816
       pre;
817
       post;
818
       ...
819
       pre;
820
       post;
821
       N -= FACTOR;
822
 
823
     } while (N >= FACTOR);
824
 
825
   rest:
826
     init' = phi (init, x);
827
 
828
   while (1)
829
     {
830
       x = phi (init', next);
831
 
832
       pre;
833
       if (st)
834
         break;
835
       post;
836
     } */
837
 
838
void
839
tree_unroll_loop (struct loops *loops, struct loop *loop, unsigned factor,
840
                  edge exit, struct tree_niter_desc *desc)
841
{
842
  tree dont_exit, exit_if, ctr_before, ctr_after;
843
  tree enter_main_cond, exit_base, exit_step, exit_bound;
844
  enum tree_code exit_cmp;
845
  tree phi_old_loop, phi_new_loop, phi_rest, init, next, new_init, var;
846
  struct loop *new_loop;
847
  basic_block rest, exit_bb;
848
  edge old_entry, new_entry, old_latch, precond_edge, new_exit;
849
  edge nonexit, new_nonexit;
850
  block_stmt_iterator bsi;
851
  use_operand_p op;
852
  bool ok;
853
  unsigned est_niter;
854
  unsigned irr = loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP;
855
  sbitmap wont_exit;
856
 
857
  est_niter = expected_loop_iterations (loop);
858
  determine_exit_conditions (loop, desc, factor,
859
                             &enter_main_cond, &exit_base, &exit_step,
860
                             &exit_cmp, &exit_bound);
861
 
862
  new_loop = loop_version (loops, loop, enter_main_cond, NULL, true);
863
  gcc_assert (new_loop != NULL);
864
  update_ssa (TODO_update_ssa);
865
 
866
  /* Unroll the loop and remove the old exits.  */
867
  dont_exit = ((exit->flags & EDGE_TRUE_VALUE)
868
               ? boolean_false_node
869
               : boolean_true_node);
870
  if (exit == EDGE_SUCC (exit->src, 0))
871
    nonexit = EDGE_SUCC (exit->src, 1);
872
  else
873
    nonexit = EDGE_SUCC (exit->src, 0);
874
  nonexit->probability = REG_BR_PROB_BASE;
875
  exit->probability = 0;
876
  nonexit->count += exit->count;
877
  exit->count = 0;
878
  exit_if = last_stmt (exit->src);
879
  COND_EXPR_COND (exit_if) = dont_exit;
880
  update_stmt (exit_if);
881
 
882
  wont_exit = sbitmap_alloc (factor);
883
  sbitmap_ones (wont_exit);
884
  ok = tree_duplicate_loop_to_header_edge
885
          (loop, loop_latch_edge (loop), loops, factor - 1,
886
           wont_exit, NULL, NULL, NULL, DLTHE_FLAG_UPDATE_FREQ);
887
  free (wont_exit);
888
  gcc_assert (ok);
889
  update_ssa (TODO_update_ssa);
890
 
891
  /* Prepare the cfg and update the phi nodes.  */
892
  rest = loop_preheader_edge (new_loop)->src;
893
  precond_edge = single_pred_edge (rest);
894
  loop_split_edge_with (loop_latch_edge (loop), NULL);
895
  exit_bb = single_pred (loop->latch);
896
 
897
  new_exit = make_edge (exit_bb, rest, EDGE_FALSE_VALUE | irr);
898
  new_exit->count = loop_preheader_edge (loop)->count;
899
  est_niter = est_niter / factor + 1;
900
  new_exit->probability = REG_BR_PROB_BASE / est_niter;
901
 
902
  new_nonexit = single_pred_edge (loop->latch);
903
  new_nonexit->flags = EDGE_TRUE_VALUE;
904
  new_nonexit->probability = REG_BR_PROB_BASE - new_exit->probability;
905
 
906
  old_entry = loop_preheader_edge (loop);
907
  new_entry = loop_preheader_edge (new_loop);
908
  old_latch = loop_latch_edge (loop);
909
  for (phi_old_loop = phi_nodes (loop->header),
910
       phi_new_loop = phi_nodes (new_loop->header);
911
       phi_old_loop;
912
       phi_old_loop = PHI_CHAIN (phi_old_loop),
913
       phi_new_loop = PHI_CHAIN (phi_new_loop))
914
    {
915
      init = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_entry);
916
      op = PHI_ARG_DEF_PTR_FROM_EDGE (phi_new_loop, new_entry);
917
      gcc_assert (operand_equal_for_phi_arg_p (init, USE_FROM_PTR (op)));
918
      next = PHI_ARG_DEF_FROM_EDGE (phi_old_loop, old_latch);
919
 
920
      /* Prefer using original variable as a base for the new ssa name.
921
         This is necessary for virtual ops, and useful in order to avoid
922
         losing debug info for real ops.  */
923
      if (TREE_CODE (next) == SSA_NAME)
924
        var = SSA_NAME_VAR (next);
925
      else if (TREE_CODE (init) == SSA_NAME)
926
        var = SSA_NAME_VAR (init);
927
      else
928
        {
929
          var = create_tmp_var (TREE_TYPE (init), "unrinittmp");
930
          add_referenced_var (var);
931
        }
932
 
933
      new_init = make_ssa_name (var, NULL_TREE);
934
      phi_rest = create_phi_node (new_init, rest);
935
      SSA_NAME_DEF_STMT (new_init) = phi_rest;
936
 
937
      add_phi_arg (phi_rest, init, precond_edge);
938
      add_phi_arg (phi_rest, next, new_exit);
939
      SET_USE (op, new_init);
940
    }
941
 
942
  /* Finally create the new counter for number of iterations and add the new
943
     exit instruction.  */
944
  bsi = bsi_last (exit_bb);
945
  create_iv (exit_base, exit_step, NULL_TREE, loop,
946
             &bsi, true, &ctr_before, &ctr_after);
947
  exit_if = build_if_stmt (build2 (exit_cmp, boolean_type_node, ctr_after,
948
                                   exit_bound),
949
                           tree_block_label (loop->latch),
950
                           tree_block_label (rest));
951
  bsi_insert_after (&bsi, exit_if, BSI_NEW_STMT);
952
 
953
  verify_flow_info ();
954
  verify_dominators (CDI_DOMINATORS);
955
  verify_loop_structure (loops);
956
  verify_loop_closed_ssa ();
957
}

powered by: WebSVN 2.1.0

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