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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-ssa-loop-ivcanon.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Induction variable canonicalization.
2
   Copyright (C) 2004, 2005, 2007, 2008, 2010
3
   Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it
8
under the terms of the GNU General Public License as published by the
9
Free Software Foundation; either version 3, or (at your option) any
10
later version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT
13
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
/* This pass detects the loops that iterate a constant number of times,
22
   adds a canonical induction variable (step -1, tested against 0)
23
   and replaces the exit test.  This enables the less powerful rtl
24
   level analysis to use this information.
25
 
26
   This might spoil the code in some cases (by increasing register pressure).
27
   Note that in the case the new variable is not needed, ivopts will get rid
28
   of it, so it might only be a problem when there are no other linear induction
29
   variables.  In that case the created optimization possibilities are likely
30
   to pay up.
31
 
32
   Additionally in case we detect that it is beneficial to unroll the
33
   loop completely, we do it right here to expose the optimization
34
   possibilities to the following passes.  */
35
 
36
#include "config.h"
37
#include "system.h"
38
#include "coretypes.h"
39
#include "tm.h"
40
#include "tree.h"
41
#include "tm_p.h"
42
#include "basic-block.h"
43
#include "tree-pretty-print.h"
44
#include "gimple-pretty-print.h"
45
#include "tree-flow.h"
46
#include "tree-dump.h"
47
#include "cfgloop.h"
48
#include "tree-pass.h"
49
#include "tree-chrec.h"
50
#include "tree-scalar-evolution.h"
51
#include "params.h"
52
#include "flags.h"
53
#include "tree-inline.h"
54
#include "target.h"
55
 
56
/* Specifies types of loops that may be unrolled.  */
57
 
58
enum unroll_level
59
{
60
  UL_SINGLE_ITER,       /* Only loops that exit immediately in the first
61
                           iteration.  */
62
  UL_NO_GROWTH,         /* Only loops whose unrolling will not cause increase
63
                           of code size.  */
64
  UL_ALL                /* All suitable loops.  */
65
};
66
 
67
/* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
68
   is the exit edge whose condition is replaced.  */
69
 
70
static void
71
create_canonical_iv (struct loop *loop, edge exit, tree niter)
72
{
73
  edge in;
74
  tree type, var;
75
  gimple cond;
76
  gimple_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 = gsi_last_bb (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
  gimple_cond_set_code (cond, cmp);
108
  gimple_cond_set_lhs (cond, var);
109
  gimple_cond_set_rhs (cond, build_int_cst (type, 0));
110
  update_stmt (cond);
111
}
112
 
113
/* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.  */
114
 
115
unsigned
116
tree_num_loop_insns (struct loop *loop, eni_weights *weights)
117
{
118
  basic_block *body = get_loop_body (loop);
119
  gimple_stmt_iterator gsi;
120
  unsigned size = 0, i;
121
 
122
  for (i = 0; i < loop->num_nodes; i++)
123
    for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
124
      size += estimate_num_insns (gsi_stmt (gsi), weights);
125
  free (body);
126
 
127
  return size;
128
}
129
 
130
/* Describe size of loop as detected by tree_estimate_loop_size.  */
131
struct loop_size
132
{
133
  /* Number of instructions in the loop.  */
134
  int overall;
135
 
136
  /* Number of instructions that will be likely optimized out in
137
     peeled iterations of loop  (i.e. computation based on induction
138
     variable where induction variable starts at known constant.)  */
139
  int eliminated_by_peeling;
140
 
141
  /* Same statistics for last iteration of loop: it is smaller because
142
     instructions after exit are not executed.  */
143
  int last_iteration;
144
  int last_iteration_eliminated_by_peeling;
145
};
146
 
147
/* Return true if OP in STMT will be constant after peeling LOOP.  */
148
 
149
static bool
150
constant_after_peeling (tree op, gimple stmt, struct loop *loop)
151
{
152
  affine_iv iv;
153
 
154
  if (is_gimple_min_invariant (op))
155
    return true;
156
 
157
  /* We can still fold accesses to constant arrays when index is known.  */
158
  if (TREE_CODE (op) != SSA_NAME)
159
    {
160
      tree base = op;
161
 
162
      /* First make fast look if we see constant array inside.  */
163
      while (handled_component_p (base))
164
        base = TREE_OPERAND (base, 0);
165
      if ((DECL_P (base) == VAR_DECL
166
           && const_value_known_p (base))
167
          || CONSTANT_CLASS_P (base))
168
        {
169
          /* If so, see if we understand all the indices.  */
170
          base = op;
171
          while (handled_component_p (base))
172
            {
173
              if (TREE_CODE (base) == ARRAY_REF
174
                  && !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
175
                return false;
176
              base = TREE_OPERAND (base, 0);
177
            }
178
          return true;
179
        }
180
      return false;
181
    }
182
 
183
  /* Induction variables are constants.  */
184
  if (!simple_iv (loop, loop_containing_stmt (stmt), op, &iv, false))
185
    return false;
186
  if (!is_gimple_min_invariant (iv.base))
187
    return false;
188
  if (!is_gimple_min_invariant (iv.step))
189
    return false;
190
  return true;
191
}
192
 
193
/* Computes an estimated number of insns in LOOP, weighted by WEIGHTS.
194
   Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.  */
195
 
196
static void
197
tree_estimate_loop_size (struct loop *loop, edge exit, struct loop_size *size)
198
{
199
  basic_block *body = get_loop_body (loop);
200
  gimple_stmt_iterator gsi;
201
  unsigned int i;
202
  bool after_exit;
203
 
204
  size->overall = 0;
205
  size->eliminated_by_peeling = 0;
206
  size->last_iteration = 0;
207
  size->last_iteration_eliminated_by_peeling = 0;
208
 
209
  if (dump_file && (dump_flags & TDF_DETAILS))
210
    fprintf (dump_file, "Estimating sizes for loop %i\n", loop->num);
211
  for (i = 0; i < loop->num_nodes; i++)
212
    {
213
      if (exit && body[i] != exit->src
214
          && dominated_by_p (CDI_DOMINATORS, body[i], exit->src))
215
        after_exit = true;
216
      else
217
        after_exit = false;
218
      if (dump_file && (dump_flags & TDF_DETAILS))
219
        fprintf (dump_file, " BB: %i, after_exit: %i\n", body[i]->index, after_exit);
220
 
221
      for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
222
        {
223
          gimple stmt = gsi_stmt (gsi);
224
          int num = estimate_num_insns (stmt, &eni_size_weights);
225
          bool likely_eliminated = false;
226
 
227
          if (dump_file && (dump_flags & TDF_DETAILS))
228
            {
229
              fprintf (dump_file, "  size: %3i ", num);
230
              print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, 0);
231
            }
232
 
233
          /* Look for reasons why we might optimize this stmt away. */
234
 
235
          /* Exit conditional.  */
236
          if (body[i] == exit->src && stmt == last_stmt (exit->src))
237
            {
238
              if (dump_file && (dump_flags & TDF_DETAILS))
239
                fprintf (dump_file, "   Exit condition will be eliminated.\n");
240
              likely_eliminated = true;
241
            }
242
          /* Sets of IV variables  */
243
          else if (gimple_code (stmt) == GIMPLE_ASSIGN
244
              && constant_after_peeling (gimple_assign_lhs (stmt), stmt, loop))
245
            {
246
              if (dump_file && (dump_flags & TDF_DETAILS))
247
                fprintf (dump_file, "   Induction variable computation will"
248
                         " be folded away.\n");
249
              likely_eliminated = true;
250
            }
251
          /* Assignments of IV variables.  */
252
          else if (gimple_code (stmt) == GIMPLE_ASSIGN
253
                   && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
254
                   && constant_after_peeling (gimple_assign_rhs1 (stmt), stmt,loop)
255
                   && (gimple_assign_rhs_class (stmt) != GIMPLE_BINARY_RHS
256
                       || constant_after_peeling (gimple_assign_rhs2 (stmt),
257
                                                  stmt, loop)))
258
            {
259
              if (dump_file && (dump_flags & TDF_DETAILS))
260
                fprintf (dump_file, "   Constant expression will be folded away.\n");
261
              likely_eliminated = true;
262
            }
263
          /* Conditionals.  */
264
          else if (gimple_code (stmt) == GIMPLE_COND
265
                   && constant_after_peeling (gimple_cond_lhs (stmt), stmt, loop)
266
                   && constant_after_peeling (gimple_cond_rhs (stmt), stmt, loop))
267
            {
268
              if (dump_file && (dump_flags & TDF_DETAILS))
269
                fprintf (dump_file, "   Constant conditional.\n");
270
              likely_eliminated = true;
271
            }
272
 
273
          size->overall += num;
274
          if (likely_eliminated)
275
            size->eliminated_by_peeling += num;
276
          if (!after_exit)
277
            {
278
              size->last_iteration += num;
279
              if (likely_eliminated)
280
                size->last_iteration_eliminated_by_peeling += num;
281
            }
282
        }
283
    }
284
  if (dump_file && (dump_flags & TDF_DETAILS))
285
    fprintf (dump_file, "size: %i-%i, last_iteration: %i-%i\n", size->overall,
286
             size->eliminated_by_peeling, size->last_iteration,
287
             size->last_iteration_eliminated_by_peeling);
288
 
289
  free (body);
290
}
291
 
292
/* Estimate number of insns of completely unrolled loop.
293
   It is (NUNROLL + 1) * size of loop body with taking into account
294
   the fact that in last copy everything after exit conditional
295
   is dead and that some instructions will be eliminated after
296
   peeling.
297
 
298
   Loop body is likely going to simplify futher, this is difficult
299
   to guess, we just decrease the result by 1/3.  */
300
 
301
static unsigned HOST_WIDE_INT
302
estimated_unrolled_size (struct loop_size *size,
303
                         unsigned HOST_WIDE_INT nunroll)
304
{
305
  HOST_WIDE_INT unr_insns = ((nunroll)
306
                             * (HOST_WIDE_INT) (size->overall
307
                                                - size->eliminated_by_peeling));
308
  if (!nunroll)
309
    unr_insns = 0;
310
  unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
311
 
312
  unr_insns = unr_insns * 2 / 3;
313
  if (unr_insns <= 0)
314
    unr_insns = 1;
315
 
316
  return unr_insns;
317
}
318
 
319
/* Tries to unroll LOOP completely, i.e. NITER times.
320
   UL determines which loops we are allowed to unroll.
321
   EXIT is the exit of the loop that should be eliminated.  */
322
 
323
static bool
324
try_unroll_loop_completely (struct loop *loop,
325
                            edge exit, tree niter,
326
                            enum unroll_level ul)
327
{
328
  unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll, unr_insns;
329
  gimple cond;
330
  struct loop_size size;
331
 
332
  if (loop->inner)
333
    return false;
334
 
335
  if (!host_integerp (niter, 1))
336
    return false;
337
  n_unroll = tree_low_cst (niter, 1);
338
 
339
  max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
340
  if (n_unroll > max_unroll)
341
    return false;
342
 
343
  if (n_unroll)
344
    {
345
      if (ul == UL_SINGLE_ITER)
346
        return false;
347
 
348
      tree_estimate_loop_size (loop, exit, &size);
349
      ninsns = size.overall;
350
 
351
      unr_insns = estimated_unrolled_size (&size, n_unroll);
352
      if (dump_file && (dump_flags & TDF_DETAILS))
353
        {
354
          fprintf (dump_file, "  Loop size: %d\n", (int) ninsns);
355
          fprintf (dump_file, "  Estimated size after unrolling: %d\n",
356
                   (int) unr_insns);
357
        }
358
 
359
      if (unr_insns > ninsns
360
          && (unr_insns
361
              > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS)))
362
        {
363
          if (dump_file && (dump_flags & TDF_DETAILS))
364
            fprintf (dump_file, "Not unrolling loop %d "
365
                     "(--param max-completely-peeled-insns limit reached).\n",
366
                     loop->num);
367
          return false;
368
        }
369
 
370
      if (ul == UL_NO_GROWTH
371
          && unr_insns > ninsns)
372
        {
373
          if (dump_file && (dump_flags & TDF_DETAILS))
374
            fprintf (dump_file, "Not unrolling loop %d.\n", loop->num);
375
          return false;
376
        }
377
    }
378
 
379
  if (n_unroll)
380
    {
381
      sbitmap wont_exit;
382
      edge e;
383
      unsigned i;
384
      VEC (edge, heap) *to_remove = NULL;
385
 
386
      initialize_original_copy_tables ();
387
      wont_exit = sbitmap_alloc (n_unroll + 1);
388
      sbitmap_ones (wont_exit);
389
      RESET_BIT (wont_exit, 0);
390
 
391
      if (!gimple_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
392
                                                 n_unroll, wont_exit,
393
                                                 exit, &to_remove,
394
                                                 DLTHE_FLAG_UPDATE_FREQ
395
                                                 | DLTHE_FLAG_COMPLETTE_PEEL))
396
        {
397
          free_original_copy_tables ();
398
          free (wont_exit);
399
          return false;
400
        }
401
 
402
      FOR_EACH_VEC_ELT (edge, to_remove, i, e)
403
        {
404
          bool ok = remove_path (e);
405
          gcc_assert (ok);
406
        }
407
 
408
      VEC_free (edge, heap, to_remove);
409
      free (wont_exit);
410
      free_original_copy_tables ();
411
    }
412
 
413
  cond = last_stmt (exit->src);
414
  if (exit->flags & EDGE_TRUE_VALUE)
415
    gimple_cond_make_true (cond);
416
  else
417
    gimple_cond_make_false (cond);
418
  update_stmt (cond);
419
  update_ssa (TODO_update_ssa);
420
 
421
  if (dump_file && (dump_flags & TDF_DETAILS))
422
    fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
423
 
424
  return true;
425
}
426
 
427
/* Adds a canonical induction variable to LOOP if suitable.
428
   CREATE_IV is true if we may create a new iv.  UL determines
429
   which loops we are allowed to completely unroll.  If TRY_EVAL is true, we try
430
   to determine the number of iterations of a loop by direct evaluation.
431
   Returns true if cfg is changed.  */
432
 
433
static bool
434
canonicalize_loop_induction_variables (struct loop *loop,
435
                                       bool create_iv, enum unroll_level ul,
436
                                       bool try_eval)
437
{
438
  edge exit = NULL;
439
  tree niter;
440
 
441
  niter = number_of_latch_executions (loop);
442
  if (TREE_CODE (niter) == INTEGER_CST)
443
    {
444
      exit = single_exit (loop);
445
      if (!just_once_each_iteration_p (loop, exit->src))
446
        return false;
447
    }
448
  else
449
    {
450
      /* If the loop has more than one exit, try checking all of them
451
         for # of iterations determinable through scev.  */
452
      if (!single_exit (loop))
453
        niter = find_loop_niter (loop, &exit);
454
 
455
      /* Finally if everything else fails, try brute force evaluation.  */
456
      if (try_eval
457
          && (chrec_contains_undetermined (niter)
458
              || TREE_CODE (niter) != INTEGER_CST))
459
        niter = find_loop_niter_by_eval (loop, &exit);
460
 
461
      if (chrec_contains_undetermined (niter)
462
          || TREE_CODE (niter) != INTEGER_CST)
463
        return false;
464
    }
465
 
466
  if (dump_file && (dump_flags & TDF_DETAILS))
467
    {
468
      fprintf (dump_file, "Loop %d iterates ", loop->num);
469
      print_generic_expr (dump_file, niter, TDF_SLIM);
470
      fprintf (dump_file, " times.\n");
471
    }
472
 
473
  if (try_unroll_loop_completely (loop, exit, niter, ul))
474
    return true;
475
 
476
  if (create_iv)
477
    create_canonical_iv (loop, exit, niter);
478
 
479
  return false;
480
}
481
 
482
/* The main entry point of the pass.  Adds canonical induction variables
483
   to the suitable loops.  */
484
 
485
unsigned int
486
canonicalize_induction_variables (void)
487
{
488
  loop_iterator li;
489
  struct loop *loop;
490
  bool changed = false;
491
 
492
  FOR_EACH_LOOP (li, loop, 0)
493
    {
494
      changed |= canonicalize_loop_induction_variables (loop,
495
                                                        true, UL_SINGLE_ITER,
496
                                                        true);
497
    }
498
 
499
  /* Clean up the information about numbers of iterations, since brute force
500
     evaluation could reveal new information.  */
501
  scev_reset ();
502
 
503
  if (changed)
504
    return TODO_cleanup_cfg;
505
  return 0;
506
}
507
 
508
/* Unroll LOOPS completely if they iterate just few times.  Unless
509
   MAY_INCREASE_SIZE is true, perform the unrolling only if the
510
   size of the code does not increase.  */
511
 
512
unsigned int
513
tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
514
{
515
  loop_iterator li;
516
  struct loop *loop;
517
  bool changed;
518
  enum unroll_level ul;
519
  int iteration = 0;
520
 
521
  do
522
    {
523
      changed = false;
524
 
525
      FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
526
        {
527
          if (may_increase_size && optimize_loop_for_speed_p (loop)
528
              /* Unroll outermost loops only if asked to do so or they do
529
                 not cause code growth.  */
530
              && (unroll_outer
531
                  || loop_outer (loop_outer (loop))))
532
            ul = UL_ALL;
533
          else
534
            ul = UL_NO_GROWTH;
535
          changed |= canonicalize_loop_induction_variables
536
                       (loop, false, ul, !flag_tree_loop_ivcanon);
537
        }
538
 
539
      if (changed)
540
        {
541
          /* This will take care of removing completely unrolled loops
542
             from the loop structures so we can continue unrolling now
543
             innermost loops.  */
544
          if (cleanup_tree_cfg ())
545
            update_ssa (TODO_update_ssa_only_virtuals);
546
 
547
          /* Clean up the information about numbers of iterations, since
548
             complete unrolling might have invalidated it.  */
549
          scev_reset ();
550
        }
551
    }
552
  while (changed
553
         && ++iteration <= PARAM_VALUE (PARAM_MAX_UNROLL_ITERATIONS));
554
 
555
  return 0;
556
}

powered by: WebSVN 2.1.0

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