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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [tree-ssa-loop-ch.c] - Blame information for rev 280

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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