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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Loop header copying on trees.
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 "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
  block_stmt_iterator bsi;
54
  tree 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
  gcc_assert (EDGE_COUNT (header->succs) > 0);
62
  if (single_succ_p (header))
63
    return false;
64
  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
65
      && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
66
    return false;
67
 
68
  /* If this is not the original loop header, we want it to have just
69
     one predecessor in order to match the && pattern.  */
70
  if (header != loop->header && !single_pred_p (header))
71
    return false;
72
 
73
  last = last_stmt (header);
74
  if (TREE_CODE (last) != COND_EXPR)
75
    return false;
76
 
77
  /* Approximately copy the conditions that used to be used in jump.c --
78
     at most 20 insns and no calls.  */
79
  for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
80
    {
81
      last = bsi_stmt (bsi);
82
 
83
      if (TREE_CODE (last) == LABEL_EXPR)
84
        continue;
85
 
86
      if (get_call_expr_in (last))
87
        return false;
88
 
89
      *limit -= estimate_num_insns (last);
90
      if (*limit < 0)
91
        return false;
92
    }
93
 
94
  return true;
95
}
96
 
97
/* Checks whether LOOP is a do-while style loop.  */
98
 
99
static bool
100
do_while_loop_p (struct loop *loop)
101
{
102
  tree stmt = last_stmt (loop->latch);
103
 
104
  /* If the latch of the loop is not empty, it is not a do-while loop.  */
105
  if (stmt
106
      && TREE_CODE (stmt) != LABEL_EXPR)
107
    return false;
108
 
109
  /* If the header contains just a condition, it is not a do-while loop.  */
110
  stmt = last_and_only_stmt (loop->header);
111
  if (stmt
112
      && TREE_CODE (stmt) == COND_EXPR)
113
    return false;
114
 
115
  return true;
116
}
117
 
118
/* For all loops, copy the condition at the end of the loop body in front
119
   of the loop.  This is beneficial since it increases efficiency of
120
   code motion optimizations.  It also saves one jump on entry to the loop.  */
121
 
122
static unsigned int
123
copy_loop_headers (void)
124
{
125
  struct loops *loops;
126
  unsigned i;
127
  struct loop *loop;
128
  basic_block header;
129
  edge exit, entry;
130
  basic_block *bbs, *copied_bbs;
131
  unsigned n_bbs;
132
  unsigned bbs_size;
133
 
134
  loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS
135
                               | LOOPS_HAVE_SIMPLE_LATCHES);
136
  if (!loops)
137
    return 0;
138
 
139
#ifdef ENABLE_CHECKING
140
  verify_loop_structure (loops);
141
#endif
142
 
143
  bbs = XNEWVEC (basic_block, n_basic_blocks);
144
  copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
145
  bbs_size = n_basic_blocks;
146
 
147
  for (i = 1; i < loops->num; i++)
148
    {
149
      /* Copy at most 20 insns.  */
150
      int limit = 20;
151
 
152
      loop = loops->parray[i];
153
      if (!loop)
154
        continue;
155
      header = loop->header;
156
 
157
      /* If the loop is already a do-while style one (either because it was
158
         written as such, or because jump threading transformed it into one),
159
         we might be in fact peeling the first iteration of the loop.  This
160
         in general is not a good idea.  */
161
      if (do_while_loop_p (loop))
162
        continue;
163
 
164
      /* Iterate the header copying up to limit; this takes care of the cases
165
         like while (a && b) {...}, where we want to have both of the conditions
166
         copied.  TODO -- handle while (a || b) - like cases, by not requiring
167
         the header to have just a single successor and copying up to
168
         postdominator.  */
169
 
170
      exit = NULL;
171
      n_bbs = 0;
172
      while (should_duplicate_loop_header_p (header, loop, &limit))
173
        {
174
          /* Find a successor of header that is inside a loop; i.e. the new
175
             header after the condition is copied.  */
176
          if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
177
            exit = EDGE_SUCC (header, 0);
178
          else
179
            exit = EDGE_SUCC (header, 1);
180
          bbs[n_bbs++] = header;
181
          gcc_assert (bbs_size > n_bbs);
182
          header = exit->dest;
183
        }
184
 
185
      if (!exit)
186
        continue;
187
 
188
      if (dump_file && (dump_flags & TDF_DETAILS))
189
        fprintf (dump_file,
190
                 "Duplicating header of the loop %d up to edge %d->%d.\n",
191
                 loop->num, exit->src->index, exit->dest->index);
192
 
193
      /* Ensure that the header will have just the latch as a predecessor
194
         inside the loop.  */
195
      if (!single_pred_p (exit->dest))
196
        exit = single_pred_edge (loop_split_edge_with (exit, NULL));
197
 
198
      entry = loop_preheader_edge (loop);
199
 
200
      if (!tree_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
201
        {
202
          fprintf (dump_file, "Duplication failed.\n");
203
          continue;
204
        }
205
 
206
      /* If the loop has the form "for (i = j; i < j + 10; i++)" then
207
         this copying can introduce a case where we rely on undefined
208
         signed overflow to eliminate the preheader condition, because
209
         we assume that "j < j + 10" is true.  We don't want to warn
210
         about that case for -Wstrict-overflow, because in general we
211
         don't warn about overflow involving loops.  Prevent the
212
         warning by setting TREE_NO_WARNING.  */
213
      if (warn_strict_overflow > 0)
214
        {
215
          unsigned int i;
216
 
217
          for (i = 0; i < n_bbs; ++i)
218
            {
219
              tree last;
220
 
221
              last = last_stmt (copied_bbs[i]);
222
              if (TREE_CODE (last) == COND_EXPR)
223
                TREE_NO_WARNING (last) = 1;
224
            }
225
        }
226
 
227
      /* Ensure that the latch and the preheader is simple (we know that they
228
         are not now, since there was the loop exit condition.  */
229
      loop_split_edge_with (loop_preheader_edge (loop), NULL);
230
      loop_split_edge_with (loop_latch_edge (loop), NULL);
231
    }
232
 
233
  free (bbs);
234
  free (copied_bbs);
235
 
236
  loop_optimizer_finalize (loops);
237
  return 0;
238
}
239
 
240
static bool
241
gate_ch (void)
242
{
243
  return flag_tree_ch != 0;
244
}
245
 
246
struct tree_opt_pass pass_ch =
247
{
248
  "ch",                                 /* name */
249
  gate_ch,                              /* gate */
250
  copy_loop_headers,                    /* execute */
251
  NULL,                                 /* sub */
252
  NULL,                                 /* next */
253
  0,                                     /* static_pass_number */
254
  TV_TREE_CH,                           /* tv_id */
255
  PROP_cfg | PROP_ssa,                  /* properties_required */
256
  0,                                     /* properties_provided */
257
  0,                                     /* properties_destroyed */
258
  0,                                     /* todo_flags_start */
259
  TODO_cleanup_cfg | TODO_dump_func
260
  | TODO_verify_ssa,                    /* todo_flags_finish */
261
 
262
};

powered by: WebSVN 2.1.0

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