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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 684 jeremybenn
/* Loop header copying on trees.
2
   Copyright (C) 2004, 2005, 2006, 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
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "tree.h"
26
#include "tm_p.h"
27
#include "basic-block.h"
28
#include "output.h"
29
#include "tree-flow.h"
30
#include "tree-dump.h"
31
#include "tree-pass.h"
32
#include "timevar.h"
33
#include "cfgloop.h"
34
#include "tree-inline.h"
35
#include "flags.h"
36
#include "tree-inline.h"
37
 
38
/* Duplicates headers of loops if they are small enough, so that the statements
39
   in the loop body are always executed when the loop is entered.  This
40
   increases effectiveness of code motion optimizations, and reduces the need
41
   for loop preconditioning.  */
42
 
43
/* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
44
   instructions should be duplicated, limit is decreased by the actual
45
   amount.  */
46
 
47
static bool
48
should_duplicate_loop_header_p (basic_block header, struct loop *loop,
49
                                int *limit)
50
{
51
  gimple_stmt_iterator bsi;
52
  gimple last;
53
 
54
  /* Do not copy one block more than once (we do not really want to do
55
     loop peeling here).  */
56
  if (header->aux)
57
    return false;
58
 
59
  /* Loop header copying usually increases size of the code.  This used not to
60
     be true, since quite often it is possible to verify that the condition is
61
     satisfied in the first iteration and therefore to eliminate it.  Jump
62
     threading handles these cases now.  */
63
  if (optimize_loop_for_size_p (loop))
64
    return false;
65
 
66
  gcc_assert (EDGE_COUNT (header->succs) > 0);
67
  if (single_succ_p (header))
68
    return false;
69
  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
70
      && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
71
    return false;
72
 
73
  /* If this is not the original loop header, we want it to have just
74
     one predecessor in order to match the && pattern.  */
75
  if (header != loop->header && !single_pred_p (header))
76
    return false;
77
 
78
  last = last_stmt (header);
79
  if (gimple_code (last) != GIMPLE_COND)
80
    return false;
81
 
82
  /* Approximately copy the conditions that used to be used in jump.c --
83
     at most 20 insns and no calls.  */
84
  for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
85
    {
86
      last = gsi_stmt (bsi);
87
 
88
      if (gimple_code (last) == GIMPLE_LABEL)
89
        continue;
90
 
91
      if (is_gimple_debug (last))
92
        continue;
93
 
94
      if (is_gimple_call (last))
95
        return false;
96
 
97
      *limit -= estimate_num_insns (last, &eni_size_weights);
98
      if (*limit < 0)
99
        return false;
100
    }
101
 
102
  return true;
103
}
104
 
105
/* Checks whether LOOP is a do-while style loop.  */
106
 
107
bool
108
do_while_loop_p (struct loop *loop)
109
{
110
  gimple stmt = last_stmt (loop->latch);
111
 
112
  /* If the latch of the loop is not empty, it is not a do-while loop.  */
113
  if (stmt
114
      && gimple_code (stmt) != GIMPLE_LABEL)
115
    return false;
116
 
117
  /* If the header contains just a condition, it is not a do-while loop.  */
118
  stmt = last_and_only_stmt (loop->header);
119
  if (stmt
120
      && gimple_code (stmt) == GIMPLE_COND)
121
    return false;
122
 
123
  return true;
124
}
125
 
126
/* For all loops, copy the condition at the end of the loop body in front
127
   of the loop.  This is beneficial since it increases efficiency of
128
   code motion optimizations.  It also saves one jump on entry to the loop.  */
129
 
130
static unsigned int
131
copy_loop_headers (void)
132
{
133
  loop_iterator li;
134
  struct loop *loop;
135
  basic_block header;
136
  edge exit, entry;
137
  basic_block *bbs, *copied_bbs;
138
  unsigned n_bbs;
139
  unsigned bbs_size;
140
 
141
  loop_optimizer_init (LOOPS_HAVE_PREHEADERS
142
                       | LOOPS_HAVE_SIMPLE_LATCHES);
143
  if (number_of_loops () <= 1)
144
    {
145
      loop_optimizer_finalize ();
146
      return 0;
147
    }
148
 
149
#ifdef ENABLE_CHECKING
150
  verify_loop_structure ();
151
#endif
152
 
153
  bbs = XNEWVEC (basic_block, n_basic_blocks);
154
  copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
155
  bbs_size = n_basic_blocks;
156
 
157
  FOR_EACH_LOOP (li, loop, 0)
158
    {
159
      /* Copy at most 20 insns.  */
160
      int limit = 20;
161
 
162
      header = loop->header;
163
 
164
      /* If the loop is already a do-while style one (either because it was
165
         written as such, or because jump threading transformed it into one),
166
         we might be in fact peeling the first iteration of the loop.  This
167
         in general is not a good idea.  */
168
      if (do_while_loop_p (loop))
169
        continue;
170
 
171
      /* Iterate the header copying up to limit; this takes care of the cases
172
         like while (a && b) {...}, where we want to have both of the conditions
173
         copied.  TODO -- handle while (a || b) - like cases, by not requiring
174
         the header to have just a single successor and copying up to
175
         postdominator.  */
176
 
177
      exit = NULL;
178
      n_bbs = 0;
179
      while (should_duplicate_loop_header_p (header, loop, &limit))
180
        {
181
          /* Find a successor of header that is inside a loop; i.e. the new
182
             header after the condition is copied.  */
183
          if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
184
            exit = EDGE_SUCC (header, 0);
185
          else
186
            exit = EDGE_SUCC (header, 1);
187
          bbs[n_bbs++] = header;
188
          gcc_assert (bbs_size > n_bbs);
189
          header = exit->dest;
190
        }
191
 
192
      if (!exit)
193
        continue;
194
 
195
      if (dump_file && (dump_flags & TDF_DETAILS))
196
        fprintf (dump_file,
197
                 "Duplicating header of the loop %d up to edge %d->%d.\n",
198
                 loop->num, exit->src->index, exit->dest->index);
199
 
200
      /* Ensure that the header will have just the latch as a predecessor
201
         inside the loop.  */
202
      if (!single_pred_p (exit->dest))
203
        exit = single_pred_edge (split_edge (exit));
204
 
205
      entry = loop_preheader_edge (loop);
206
 
207
      if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
208
        {
209
          fprintf (dump_file, "Duplication failed.\n");
210
          continue;
211
        }
212
 
213
      /* If the loop has the form "for (i = j; i < j + 10; i++)" then
214
         this copying can introduce a case where we rely on undefined
215
         signed overflow to eliminate the preheader condition, because
216
         we assume that "j < j + 10" is true.  We don't want to warn
217
         about that case for -Wstrict-overflow, because in general we
218
         don't warn about overflow involving loops.  Prevent the
219
         warning by setting the no_warning flag in the condition.  */
220
      if (warn_strict_overflow > 0)
221
        {
222
          unsigned int i;
223
 
224
          for (i = 0; i < n_bbs; ++i)
225
            {
226
              gimple_stmt_iterator bsi;
227
 
228
              for (bsi = gsi_start_bb (copied_bbs[i]);
229
                   !gsi_end_p (bsi);
230
                   gsi_next (&bsi))
231
                {
232
                  gimple stmt = gsi_stmt (bsi);
233
                  if (gimple_code (stmt) == GIMPLE_COND)
234
                    gimple_set_no_warning (stmt, true);
235
                  else if (is_gimple_assign (stmt))
236
                    {
237
                      enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
238
                      if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
239
                        gimple_set_no_warning (stmt, true);
240
                    }
241
                }
242
            }
243
        }
244
 
245
      /* Ensure that the latch and the preheader is simple (we know that they
246
         are not now, since there was the loop exit condition.  */
247
      split_edge (loop_preheader_edge (loop));
248
      split_edge (loop_latch_edge (loop));
249
    }
250
 
251
  free (bbs);
252
  free (copied_bbs);
253
 
254
  loop_optimizer_finalize ();
255
  return 0;
256
}
257
 
258
static bool
259
gate_ch (void)
260
{
261
  return flag_tree_ch != 0;
262
}
263
 
264
struct gimple_opt_pass pass_ch =
265
{
266
 {
267
  GIMPLE_PASS,
268
  "ch",                                 /* name */
269
  gate_ch,                              /* gate */
270
  copy_loop_headers,                    /* execute */
271
  NULL,                                 /* sub */
272
  NULL,                                 /* next */
273
  0,                                     /* static_pass_number */
274
  TV_TREE_CH,                           /* tv_id */
275
  PROP_cfg | PROP_ssa,                  /* properties_required */
276
  0,                                     /* properties_provided */
277
  0,                                     /* properties_destroyed */
278
  0,                                     /* todo_flags_start */
279
  TODO_cleanup_cfg
280
    | TODO_verify_ssa
281
    | TODO_verify_flow                  /* todo_flags_finish */
282
 }
283
};

powered by: WebSVN 2.1.0

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