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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 38 julius
/* Induction variable canonicalization.
2
   Copyright (C) 2004, 2005, 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
/* This pass detects the loops that iterate a constant number of times,
21
   adds a canonical induction variable (step -1, tested against 0)
22
   and replaces the exit test.  This enables the less powerful rtl
23
   level analysis to use this information.
24
 
25
   This might spoil the code in some cases (by increasing register pressure).
26
   Note that in the case the new variable is not needed, ivopts will get rid
27
   of it, so it might only be a problem when there are no other linear induction
28
   variables.  In that case the created optimization possibilities are likely
29
   to pay up.
30
 
31
   Additionally in case we detect that it is beneficial to unroll the
32
   loop completely, we do it right here to expose the optimization
33
   possibilities to the following passes.  */
34
 
35
#include "config.h"
36
#include "system.h"
37
#include "coretypes.h"
38
#include "tm.h"
39
#include "tree.h"
40
#include "rtl.h"
41
#include "tm_p.h"
42
#include "hard-reg-set.h"
43
#include "basic-block.h"
44
#include "output.h"
45
#include "diagnostic.h"
46
#include "tree-flow.h"
47
#include "tree-dump.h"
48
#include "cfgloop.h"
49
#include "tree-pass.h"
50
#include "ggc.h"
51
#include "tree-chrec.h"
52
#include "tree-scalar-evolution.h"
53
#include "params.h"
54
#include "flags.h"
55
#include "tree-inline.h"
56
 
57
/* Specifies types of loops that may be unrolled.  */
58
 
59
enum unroll_level
60
{
61
  UL_SINGLE_ITER,       /* Only loops that exit immediately in the first
62
                           iteration.  */
63
  UL_NO_GROWTH,         /* Only loops whose unrolling will not cause increase
64
                           of code size.  */
65
  UL_ALL                /* All suitable loops.  */
66
};
67
 
68
/* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
69
   is the exit edge whose condition is replaced.  */
70
 
71
static void
72
create_canonical_iv (struct loop *loop, edge exit, tree niter)
73
{
74
  edge in;
75
  tree cond, type, var;
76
  block_stmt_iterator incr_at;
77
  enum tree_code cmp;
78
 
79
  if (dump_file && (dump_flags & TDF_DETAILS))
80
    {
81
      fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
82
      print_generic_expr (dump_file, niter, TDF_SLIM);
83
      fprintf (dump_file, " iterations.\n");
84
    }
85
 
86
  cond = last_stmt (exit->src);
87
  in = EDGE_SUCC (exit->src, 0);
88
  if (in == exit)
89
    in = EDGE_SUCC (exit->src, 1);
90
 
91
  /* Note that we do not need to worry about overflows, since
92
     type of niter is always unsigned and all comparisons are
93
     just for equality/nonequality -- i.e. everything works
94
     with a modulo arithmetics.  */
95
 
96
  type = TREE_TYPE (niter);
97
  niter = fold_build2 (PLUS_EXPR, type,
98
                       niter,
99
                       build_int_cst (type, 1));
100
  incr_at = bsi_last (in->src);
101
  create_iv (niter,
102
             build_int_cst (type, -1),
103
             NULL_TREE, loop,
104
             &incr_at, false, NULL, &var);
105
 
106
  cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
107
  COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
108
                                  var,
109
                                  build_int_cst (type, 0));
110
  update_stmt (cond);
111
}
112
 
113
/* Computes an estimated number of insns in LOOP.  */
114
 
115
unsigned
116
tree_num_loop_insns (struct loop *loop)
117
{
118
  basic_block *body = get_loop_body (loop);
119
  block_stmt_iterator bsi;
120
  unsigned size = 1, i;
121
 
122
  for (i = 0; i < loop->num_nodes; i++)
123
    for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
124
      size += estimate_num_insns (bsi_stmt (bsi));
125
  free (body);
126
 
127
  return size;
128
}
129
 
130
/* Estimate number of insns of completely unrolled loop.  We assume
131
   that the size of the unrolled loop is decreased in the
132
   following way (the numbers of insns are based on what
133
   estimate_num_insns returns for appropriate statements):
134
 
135
   1) exit condition gets removed (2 insns)
136
   2) increment of the control variable gets removed (2 insns)
137
   3) All remaining statements are likely to get simplified
138
      due to constant propagation.  Hard to estimate; just
139
      as a heuristics we decrease the rest by 1/3.
140
 
141
   NINSNS is the number of insns in the loop before unrolling.
142
   NUNROLL is the number of times the loop is unrolled.  */
143
 
144
static unsigned HOST_WIDE_INT
145
estimated_unrolled_size (unsigned HOST_WIDE_INT ninsns,
146
                         unsigned HOST_WIDE_INT nunroll)
147
{
148
  HOST_WIDE_INT unr_insns = 2 * ((HOST_WIDE_INT) ninsns - 4) / 3;
149
  if (unr_insns <= 0)
150
    unr_insns = 1;
151
  unr_insns *= (nunroll + 1);
152
 
153
  return unr_insns;
154
}
155
 
156
/* Tries to unroll LOOP completely, i.e. NITER times.  LOOPS is the
157
   loop tree.  UL determines which loops we are allowed to unroll.
158
   EXIT is the exit of the loop that should be eliminated.  */
159
 
160
static bool
161
try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
162
                            struct loop *loop,
163
                            edge exit, tree niter,
164
                            enum unroll_level ul)
165
{
166
  unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
167
  tree old_cond, cond, dont_exit, do_exit;
168
 
169
  if (loop->inner)
170
    return false;
171
 
172
  if (!host_integerp (niter, 1))
173
    return false;
174
  n_unroll = tree_low_cst (niter, 1);
175
 
176
  max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
177
  if (n_unroll > max_unroll)
178
    return false;
179
 
180
  if (n_unroll)
181
    {
182
      if (ul == UL_SINGLE_ITER)
183
        return false;
184
 
185
      ninsns = tree_num_loop_insns (loop);
186
 
187
      if (n_unroll * ninsns
188
          > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
189
        return false;
190
 
191
      if (ul == UL_NO_GROWTH)
192
        {
193
          unr_insns = estimated_unrolled_size (ninsns, n_unroll);
194
 
195
          if (dump_file && (dump_flags & TDF_DETAILS))
196
            {
197
              fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
198
              fprintf (dump_file, "  Estimated size after unrolling: %d\n",
199
                       (int) unr_insns);
200
            }
201
 
202
          if (unr_insns > ninsns)
203
            {
204
              if (dump_file && (dump_flags & TDF_DETAILS))
205
                fprintf (dump_file, "Not unrolling loop %d:\n", loop->num);
206
              return false;
207
            }
208
        }
209
    }
210
 
211
  if (exit->flags & EDGE_TRUE_VALUE)
212
    {
213
      dont_exit = boolean_false_node;
214
      do_exit = boolean_true_node;
215
    }
216
  else
217
    {
218
      dont_exit = boolean_true_node;
219
      do_exit = boolean_false_node;
220
    }
221
  cond = last_stmt (exit->src);
222
 
223
  if (n_unroll)
224
    {
225
      sbitmap wont_exit;
226
      edge *edges_to_remove = XNEWVEC (edge, n_unroll);
227
      unsigned int n_to_remove = 0;
228
 
229
      old_cond = COND_EXPR_COND (cond);
230
      COND_EXPR_COND (cond) = dont_exit;
231
      update_stmt (cond);
232
      initialize_original_copy_tables ();
233
 
234
      wont_exit = sbitmap_alloc (n_unroll + 1);
235
      sbitmap_ones (wont_exit);
236
      RESET_BIT (wont_exit, 0);
237
 
238
      if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
239
                                               loops, n_unroll, wont_exit,
240
                                               exit, edges_to_remove,
241
                                               &n_to_remove,
242
                                               DLTHE_FLAG_UPDATE_FREQ
243
                                               | DLTHE_FLAG_COMPLETTE_PEEL))
244
        {
245
          COND_EXPR_COND (cond) = old_cond;
246
          update_stmt (cond);
247
          free_original_copy_tables ();
248
          free (wont_exit);
249
          free (edges_to_remove);
250
          return false;
251
        }
252
      free (wont_exit);
253
      free (edges_to_remove);
254
      free_original_copy_tables ();
255
    }
256
 
257
  COND_EXPR_COND (cond) = do_exit;
258
  update_stmt (cond);
259
 
260
  update_ssa (TODO_update_ssa);
261
 
262
  if (dump_file && (dump_flags & TDF_DETAILS))
263
    fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
264
 
265
  return true;
266
}
267
 
268
/* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
269
   tree.  CREATE_IV is true if we may create a new iv.  UL determines
270
   which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
271
   to determine the number of iterations of a loop by direct evaluation.
272
   Returns true if cfg is changed.  */
273
 
274
static bool
275
canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
276
                                       bool create_iv, enum unroll_level ul,
277
                                       bool try_eval)
278
{
279
  edge exit = NULL;
280
  tree niter;
281
 
282
  niter = number_of_iterations_in_loop (loop);
283
  if (TREE_CODE (niter) == INTEGER_CST)
284
    {
285
      exit = loop->single_exit;
286
      if (!just_once_each_iteration_p (loop, exit->src))
287
        return false;
288
 
289
      /* The result of number_of_iterations_in_loop is by one higher than
290
         we expect (i.e. it returns number of executions of the exit
291
         condition, not of the loop latch edge).  */
292
      niter = fold_build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
293
                           build_int_cst (TREE_TYPE (niter), 1));
294
    }
295
  else
296
    {
297
      /* If the loop has more than one exit, try checking all of them
298
         for # of iterations determinable through scev.  */
299
      if (!loop->single_exit)
300
        niter = find_loop_niter (loop, &exit);
301
 
302
      /* Finally if everything else fails, try brute force evaluation.  */
303
      if (try_eval
304
          && (chrec_contains_undetermined (niter)
305
              || TREE_CODE (niter) != INTEGER_CST))
306
        niter = find_loop_niter_by_eval (loop, &exit);
307
 
308
      if (chrec_contains_undetermined (niter)
309
          || TREE_CODE (niter) != INTEGER_CST)
310
        return false;
311
    }
312
 
313
  if (dump_file && (dump_flags & TDF_DETAILS))
314
    {
315
      fprintf (dump_file, "Loop %d iterates ", loop->num);
316
      print_generic_expr (dump_file, niter, TDF_SLIM);
317
      fprintf (dump_file, " times.\n");
318
    }
319
 
320
  if (try_unroll_loop_completely (loops, loop, exit, niter, ul))
321
    return true;
322
 
323
  if (create_iv)
324
    create_canonical_iv (loop, exit, niter);
325
 
326
  return false;
327
}
328
 
329
/* The main entry point of the pass.  Adds canonical induction variables
330
   to the suitable LOOPS.  */
331
 
332
unsigned int
333
canonicalize_induction_variables (struct loops *loops)
334
{
335
  unsigned i;
336
  struct loop *loop;
337
  bool changed = false;
338
 
339
  for (i = 1; i < loops->num; i++)
340
    {
341
      loop = loops->parray[i];
342
 
343
      if (loop)
344
        changed |= canonicalize_loop_induction_variables (loops, loop,
345
                                                          true, UL_SINGLE_ITER,
346
                                                          true);
347
    }
348
 
349
  /* Clean up the information about numbers of iterations, since brute force
350
     evaluation could reveal new information.  */
351
  scev_reset ();
352
 
353
  if (changed)
354
    return TODO_cleanup_cfg;
355
  return 0;
356
}
357
 
358
/* Unroll LOOPS completely if they iterate just few times.  Unless
359
   MAY_INCREASE_SIZE is true, perform the unrolling only if the
360
   size of the code does not increase.  */
361
 
362
unsigned int
363
tree_unroll_loops_completely (struct loops *loops, bool may_increase_size)
364
{
365
  unsigned i;
366
  struct loop *loop;
367
  bool changed = false;
368
  enum unroll_level ul;
369
 
370
  for (i = 1; i < loops->num; i++)
371
    {
372
      loop = loops->parray[i];
373
 
374
      if (!loop)
375
        continue;
376
 
377
      if (may_increase_size && maybe_hot_bb_p (loop->header))
378
        ul = UL_ALL;
379
      else
380
        ul = UL_NO_GROWTH;
381
      changed |= canonicalize_loop_induction_variables (loops, loop,
382
                                                        false, ul,
383
                                                        !flag_tree_loop_ivcanon);
384
    }
385
 
386
  /* Clean up the information about numbers of iterations, since complete
387
     unrolling might have invalidated it.  */
388
  scev_reset ();
389
 
390
  if (changed)
391
    return TODO_cleanup_cfg;
392
  return 0;
393
}
394
 
395
/* Checks whether LOOP is empty.  */
396
 
397
static bool
398
empty_loop_p (struct loop *loop)
399
{
400
  edge exit;
401
  struct tree_niter_desc niter;
402
  tree phi, def;
403
  basic_block *body;
404
  block_stmt_iterator bsi;
405
  unsigned i;
406
  tree stmt;
407
 
408
  /* If the loop has multiple exits, it is too hard for us to handle.
409
     Similarly, if the exit is not dominating, we cannot determine
410
     whether the loop is not infinite.  */
411
  exit = single_dom_exit (loop);
412
  if (!exit)
413
    return false;
414
 
415
  /* The loop must be finite.  */
416
  if (!number_of_iterations_exit (loop, exit, &niter, false))
417
    return false;
418
 
419
  /* Values of all loop exit phi nodes must be invariants.  */
420
  for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
421
    {
422
      if (!is_gimple_reg (PHI_RESULT (phi)))
423
        continue;
424
 
425
      def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
426
 
427
      if (!expr_invariant_in_loop_p (loop, def))
428
        return false;
429
    }
430
 
431
  /* And there should be no memory modifying or from other reasons
432
     unremovable statements.  */
433
  body = get_loop_body (loop);
434
  for (i = 0; i < loop->num_nodes; i++)
435
    {
436
      /* Irreducible region might be infinite.  */
437
      if (body[i]->flags & BB_IRREDUCIBLE_LOOP)
438
        {
439
          free (body);
440
          return false;
441
        }
442
 
443
      for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
444
        {
445
          stmt = bsi_stmt (bsi);
446
          if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)
447
              || stmt_ann (stmt)->has_volatile_ops)
448
            {
449
              free (body);
450
              return false;
451
            }
452
 
453
          /* Also, asm statements and calls may have side effects and we
454
             cannot change the number of times they are executed.  */
455
          switch (TREE_CODE (stmt))
456
            {
457
            case RETURN_EXPR:
458
            case MODIFY_EXPR:
459
              stmt = get_call_expr_in (stmt);
460
              if (!stmt)
461
                break;
462
 
463
            case CALL_EXPR:
464
              if (TREE_SIDE_EFFECTS (stmt))
465
                {
466
                  free (body);
467
                  return false;
468
                }
469
              break;
470
 
471
            case ASM_EXPR:
472
              /* We cannot remove volatile assembler.  */
473
              if (ASM_VOLATILE_P (stmt))
474
                {
475
                  free (body);
476
                  return false;
477
                }
478
              break;
479
 
480
            default:
481
              break;
482
            }
483
        }
484
      }
485
  free (body);
486
 
487
  return true;
488
}
489
 
490
/* Remove LOOP by making it exit in the first iteration.  */
491
 
492
static void
493
remove_empty_loop (struct loop *loop)
494
{
495
  edge exit = single_dom_exit (loop), non_exit;
496
  tree cond_stmt = last_stmt (exit->src);
497
  tree do_exit;
498
  basic_block *body;
499
  unsigned n_before, freq_in, freq_h;
500
  gcov_type exit_count = exit->count;
501
 
502
  non_exit = EDGE_SUCC (exit->src, 0);
503
  if (non_exit == exit)
504
    non_exit = EDGE_SUCC (exit->src, 1);
505
 
506
  if (exit->flags & EDGE_TRUE_VALUE)
507
    do_exit = boolean_true_node;
508
  else
509
    do_exit = boolean_false_node;
510
 
511
  COND_EXPR_COND (cond_stmt) = do_exit;
512
  update_stmt (cond_stmt);
513
 
514
  /* Let us set the probabilities of the edges coming from the exit block.  */
515
  exit->probability = REG_BR_PROB_BASE;
516
  non_exit->probability = 0;
517
  non_exit->count = 0;
518
 
519
  /* Update frequencies and counts.  Everything before
520
     the exit needs to be scaled FREQ_IN/FREQ_H times,
521
     where FREQ_IN is the frequency of the entry edge
522
     and FREQ_H is the frequency of the loop header.
523
     Everything after the exit has zero frequency.  */
524
  freq_h = loop->header->frequency;
525
  freq_in = EDGE_FREQUENCY (loop_preheader_edge (loop));
526
  if (freq_h != 0)
527
    {
528
      body = get_loop_body_in_dom_order (loop);
529
      for (n_before = 1; n_before <= loop->num_nodes; n_before++)
530
        if (body[n_before - 1] == exit->src)
531
          break;
532
      scale_bbs_frequencies_int (body, n_before, freq_in, freq_h);
533
      scale_bbs_frequencies_int (body + n_before, loop->num_nodes - n_before,
534
                                 0, 1);
535
      free (body);
536
    }
537
 
538
  /* Number of executions of exit is not changed, thus we need to restore
539
     the original value.  */
540
  exit->count = exit_count;
541
}
542
 
543
/* Removes LOOP if it is empty.  Returns true if LOOP is removed.  CHANGED
544
   is set to true if LOOP or any of its subloops is removed.  */
545
 
546
static bool
547
try_remove_empty_loop (struct loop *loop, bool *changed)
548
{
549
  bool nonempty_subloop = false;
550
  struct loop *sub;
551
 
552
  /* First, all subloops must be removed.  */
553
  for (sub = loop->inner; sub; sub = sub->next)
554
    nonempty_subloop |= !try_remove_empty_loop (sub, changed);
555
 
556
  if (nonempty_subloop || !empty_loop_p (loop))
557
    return false;
558
 
559
  remove_empty_loop (loop);
560
  *changed = true;
561
  return true;
562
}
563
 
564
/* Remove the empty LOOPS.  */
565
 
566
unsigned int
567
remove_empty_loops (struct loops *loops)
568
{
569
  bool changed = false;
570
  struct loop *loop;
571
 
572
  for (loop = loops->tree_root->inner; loop; loop = loop->next)
573
    try_remove_empty_loop (loop, &changed);
574
 
575
  if (changed)
576
    {
577
      scev_reset ();
578
      return TODO_cleanup_cfg;
579
    }
580
  return 0;
581
}

powered by: WebSVN 2.1.0

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