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-unswitch.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Loop unswitching.
2
   Copyright (C) 2004, 2005, 2007, 2008, 2010 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 "timevar.h"
34
#include "cfgloop.h"
35
#include "params.h"
36
#include "tree-pass.h"
37
#include "tree-inline.h"
38
 
39
/* This file implements the loop unswitching, i.e. transformation of loops like
40
 
41
   while (A)
42
     {
43
       if (inv)
44
         B;
45
 
46
       X;
47
 
48
       if (!inv)
49
         C;
50
     }
51
 
52
   where inv is the loop invariant, into
53
 
54
   if (inv)
55
     {
56
       while (A)
57
         {
58
           B;
59
           X;
60
         }
61
     }
62
   else
63
     {
64
       while (A)
65
         {
66
           X;
67
           C;
68
         }
69
     }
70
 
71
   Inv is considered invariant iff the values it compares are both invariant;
72
   tree-ssa-loop-im.c ensures that all the suitable conditions are in this
73
   shape.  */
74
 
75
static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
76
static bool tree_unswitch_single_loop (struct loop *, int);
77
static tree tree_may_unswitch_on (basic_block, struct loop *);
78
 
79
/* Main entry point.  Perform loop unswitching on all suitable loops.  */
80
 
81
unsigned int
82
tree_ssa_unswitch_loops (void)
83
{
84
  loop_iterator li;
85
  struct loop *loop;
86
  bool changed = false;
87
 
88
  /* Go through inner loops (only original ones).  */
89
  FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
90
    {
91
      changed |= tree_unswitch_single_loop (loop, 0);
92
    }
93
 
94
  if (changed)
95
    return TODO_cleanup_cfg;
96
  return 0;
97
}
98
 
99
/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
100
   basic blocks (for what it means see comments below).  */
101
 
102
static tree
103
tree_may_unswitch_on (basic_block bb, struct loop *loop)
104
{
105
  gimple stmt, def;
106
  tree cond, use;
107
  basic_block def_bb;
108
  ssa_op_iter iter;
109
 
110
  /* BB must end in a simple conditional jump.  */
111
  stmt = last_stmt (bb);
112
  if (!stmt || gimple_code (stmt) != GIMPLE_COND)
113
    return NULL_TREE;
114
 
115
  /* To keep the things simple, we do not directly remove the conditions,
116
     but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
117
     loop where we would unswitch again on such a condition.  */
118
  if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
119
    return NULL_TREE;
120
 
121
  /* Condition must be invariant.  */
122
  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
123
    {
124
      def = SSA_NAME_DEF_STMT (use);
125
      def_bb = gimple_bb (def);
126
      if (def_bb
127
          && flow_bb_inside_loop_p (loop, def_bb))
128
        return NULL_TREE;
129
    }
130
 
131
  cond = build2 (gimple_cond_code (stmt), boolean_type_node,
132
                 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
133
 
134
  return cond;
135
}
136
 
137
/* Simplifies COND using checks in front of the entry of the LOOP.  Just very
138
   simplish (sufficient to prevent us from duplicating loop in unswitching
139
   unnecessarily).  */
140
 
141
static tree
142
simplify_using_entry_checks (struct loop *loop, tree cond)
143
{
144
  edge e = loop_preheader_edge (loop);
145
  gimple stmt;
146
 
147
  while (1)
148
    {
149
      stmt = last_stmt (e->src);
150
      if (stmt
151
          && gimple_code (stmt) == GIMPLE_COND
152
          && gimple_cond_code (stmt) == TREE_CODE (cond)
153
          && operand_equal_p (gimple_cond_lhs (stmt),
154
                              TREE_OPERAND (cond, 0), 0)
155
          && operand_equal_p (gimple_cond_rhs (stmt),
156
                              TREE_OPERAND (cond, 1), 0))
157
        return (e->flags & EDGE_TRUE_VALUE
158
                ? boolean_true_node
159
                : boolean_false_node);
160
 
161
      if (!single_pred_p (e->src))
162
        return cond;
163
 
164
      e = single_pred_edge (e->src);
165
      if (e->src == ENTRY_BLOCK_PTR)
166
        return cond;
167
    }
168
}
169
 
170
/* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
171
   it to grow too much, it is too easy to create example on that the code would
172
   grow exponentially.  */
173
 
174
static bool
175
tree_unswitch_single_loop (struct loop *loop, int num)
176
{
177
  basic_block *bbs;
178
  struct loop *nloop;
179
  unsigned i, found;
180
  tree cond = NULL_TREE;
181
  gimple stmt;
182
  bool changed = false;
183
 
184
  /* Only unswitch innermost loops.  */
185
  if (loop->inner)
186
    {
187
      if (dump_file && (dump_flags & TDF_DETAILS))
188
        fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
189
      return false;
190
    }
191
 
192
  /* Do not unswitch in cold regions.  */
193
  if (optimize_loop_for_size_p (loop))
194
    {
195
      if (dump_file && (dump_flags & TDF_DETAILS))
196
        fprintf (dump_file, ";; Not unswitching cold loops\n");
197
      return false;
198
    }
199
 
200
  /* The loop should not be too large, to limit code growth.  */
201
  if (tree_num_loop_insns (loop, &eni_size_weights)
202
      > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
203
    {
204
      if (dump_file && (dump_flags & TDF_DETAILS))
205
        fprintf (dump_file, ";; Not unswitching, loop too big\n");
206
      return false;
207
    }
208
 
209
  i = 0;
210
  bbs = get_loop_body (loop);
211
  found = loop->num_nodes;
212
 
213
  while (1)
214
    {
215
      /* Find a bb to unswitch on.  */
216
      for (; i < loop->num_nodes; i++)
217
        if ((cond = tree_may_unswitch_on (bbs[i], loop)))
218
          break;
219
 
220
      if (i == loop->num_nodes)
221
        {
222
          if (dump_file
223
              && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
224
              && (dump_flags & TDF_DETAILS))
225
            fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
226
 
227
          if (found == loop->num_nodes)
228
            {
229
              free (bbs);
230
              return changed;
231
            }
232
          break;
233
        }
234
 
235
      cond = simplify_using_entry_checks (loop, cond);
236
      stmt = last_stmt (bbs[i]);
237
      if (integer_nonzerop (cond))
238
        {
239
          /* Remove false path.  */
240
          gimple_cond_set_condition_from_tree (stmt, boolean_true_node);
241
          changed = true;
242
        }
243
      else if (integer_zerop (cond))
244
        {
245
          /* Remove true path.  */
246
          gimple_cond_set_condition_from_tree (stmt, boolean_false_node);
247
          changed = true;
248
        }
249
      /* Do not unswitch too much.  */
250
      else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
251
        {
252
          i++;
253
          continue;
254
        }
255
      /* In nested tree_unswitch_single_loop first optimize all conditions
256
         using entry checks, then discover still reachable blocks in the
257
         loop and find the condition only among those still reachable bbs.  */
258
      else if (num != 0)
259
        {
260
          if (found == loop->num_nodes)
261
            found = i;
262
          i++;
263
          continue;
264
        }
265
      else
266
        {
267
          found = i;
268
          break;
269
        }
270
 
271
      update_stmt (stmt);
272
      i++;
273
    }
274
 
275
  if (num != 0)
276
    {
277
      basic_block *tos, *worklist;
278
 
279
      /* When called recursively, first do a quick discovery
280
         of reachable bbs after the above changes and only
281
         consider conditions in still reachable bbs.  */
282
      tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
283
 
284
      for (i = 0; i < loop->num_nodes; i++)
285
        bbs[i]->flags &= ~BB_REACHABLE;
286
 
287
      /* Start with marking header.  */
288
      *tos++ = bbs[0];
289
      bbs[0]->flags |= BB_REACHABLE;
290
 
291
      /* Iterate: find everything reachable from what we've already seen
292
         within the same innermost loop.  Don't look through false edges
293
         if condition is always true or true edges if condition is
294
         always false.  */
295
      while (tos != worklist)
296
        {
297
          basic_block b = *--tos;
298
          edge e;
299
          edge_iterator ei;
300
          int flags = 0;
301
 
302
          if (EDGE_COUNT (b->succs) == 2)
303
            {
304
              gimple stmt = last_stmt (b);
305
              if (stmt
306
                  && gimple_code (stmt) == GIMPLE_COND)
307
                {
308
                  if (gimple_cond_true_p (stmt))
309
                    flags = EDGE_FALSE_VALUE;
310
                  else if (gimple_cond_false_p (stmt))
311
                    flags = EDGE_TRUE_VALUE;
312
                }
313
            }
314
 
315
          FOR_EACH_EDGE (e, ei, b->succs)
316
            {
317
              basic_block dest = e->dest;
318
 
319
              if (dest->loop_father == loop
320
                  && !(dest->flags & BB_REACHABLE)
321
                  && !(e->flags & flags))
322
                {
323
                  *tos++ = dest;
324
                  dest->flags |= BB_REACHABLE;
325
                }
326
            }
327
        }
328
 
329
      free (worklist);
330
 
331
      /* Find a bb to unswitch on.  */
332
      for (; found < loop->num_nodes; found++)
333
        if ((bbs[found]->flags & BB_REACHABLE)
334
            && (cond = tree_may_unswitch_on (bbs[found], loop)))
335
          break;
336
 
337
      if (found == loop->num_nodes)
338
        {
339
          free (bbs);
340
          return changed;
341
        }
342
    }
343
 
344
  if (dump_file && (dump_flags & TDF_DETAILS))
345
    fprintf (dump_file, ";; Unswitching loop\n");
346
 
347
  initialize_original_copy_tables ();
348
  /* Unswitch the loop on this condition.  */
349
  nloop = tree_unswitch_loop (loop, bbs[found], cond);
350
  if (!nloop)
351
    {
352
      free_original_copy_tables ();
353
      free (bbs);
354
      return changed;
355
    }
356
 
357
  /* Update the SSA form after unswitching.  */
358
  update_ssa (TODO_update_ssa);
359
  free_original_copy_tables ();
360
 
361
  /* Invoke itself on modified loops.  */
362
  tree_unswitch_single_loop (nloop, num + 1);
363
  tree_unswitch_single_loop (loop, num + 1);
364
  free (bbs);
365
  return true;
366
}
367
 
368
/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
369
   unswitching of innermost loops.  COND is the condition determining which
370
   loop is entered -- the new loop is entered if COND is true.  Returns NULL
371
   if impossible, new loop otherwise.  */
372
 
373
static struct loop *
374
tree_unswitch_loop (struct loop *loop,
375
                    basic_block unswitch_on, tree cond)
376
{
377
  unsigned prob_true;
378
  edge edge_true, edge_false;
379
 
380
  /* Some sanity checking.  */
381
  gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
382
  gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
383
  gcc_assert (loop->inner == NULL);
384
 
385
  extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
386
  prob_true = edge_true->probability;
387
  return loop_version (loop, unshare_expr (cond),
388
                       NULL, prob_true, prob_true,
389
                       REG_BR_PROB_BASE - prob_true, false);
390
}

powered by: WebSVN 2.1.0

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