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

Subversion Repositories openrisc

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

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

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

powered by: WebSVN 2.1.0

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