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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-ssa-sink.c] - Blame information for rev 38

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

Line No. Rev Author Line
1 38 julius
/* Code sinking for trees
2
   Copyright (C) 2001, 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
3
   Contributed by Daniel Berlin <dan@dberlin.org>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 3, or (at your option)
10
any later version.
11
 
12
GCC is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public License 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 "ggc.h"
26
#include "tree.h"
27
#include "basic-block.h"
28
#include "diagnostic.h"
29
#include "tree-inline.h"
30
#include "tree-flow.h"
31
#include "tree-gimple.h"
32
#include "tree-dump.h"
33
#include "timevar.h"
34
#include "fibheap.h"
35
#include "hashtab.h"
36
#include "tree-iterator.h"
37
#include "real.h"
38
#include "alloc-pool.h"
39
#include "tree-pass.h"
40
#include "flags.h"
41
#include "bitmap.h"
42
#include "langhooks.h"
43
#include "cfgloop.h"
44
 
45
/* TODO:
46
   1. Sinking store only using scalar promotion (IE without moving the RHS):
47
 
48
   *q = p;
49
   p = p + 1;
50
   if (something)
51
     *q = <not p>;
52
   else
53
     y = *q;
54
 
55
 
56
   should become
57
   sinktemp = p;
58
   p = p + 1;
59
   if (something)
60
     *q = <not p>;
61
   else
62
   {
63
     *q = sinktemp;
64
     y = *q
65
   }
66
   Store copy propagation will take care of the store elimination above.
67
 
68
 
69
   2. Sinking using Partial Dead Code Elimination.  */
70
 
71
 
72
static struct
73
{
74
  /* The number of statements sunk down the flowgraph by code sinking.  */
75
  int sunk;
76
 
77
} sink_stats;
78
 
79
 
80
/* Given a PHI, and one of its arguments (DEF), find the edge for
81
   that argument and return it.  If the argument occurs twice in the PHI node,
82
   we return NULL.  */
83
 
84
static basic_block
85
find_bb_for_arg (tree phi, tree def)
86
{
87
  int i;
88
  bool foundone = false;
89
  basic_block result = NULL;
90
  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
91
    if (PHI_ARG_DEF (phi, i) == def)
92
      {
93
        if (foundone)
94
          return NULL;
95
        foundone = true;
96
        result = PHI_ARG_EDGE (phi, i)->src;
97
      }
98
  return result;
99
}
100
 
101
/* When the first immediate use is in a statement, then return true if all
102
   immediate uses in IMM are in the same statement.
103
   We could also do the case where  the first immediate use is in a phi node,
104
   and all the other uses are in phis in the same basic block, but this
105
   requires some expensive checking later (you have to make sure no def/vdef
106
   in the statement occurs for multiple edges in the various phi nodes it's
107
   used in, so that you only have one place you can sink it to.  */
108
 
109
static bool
110
all_immediate_uses_same_place (tree stmt)
111
{
112
  tree firstuse = NULL_TREE;
113
  ssa_op_iter op_iter;
114
  imm_use_iterator imm_iter;
115
  use_operand_p use_p;
116
  tree var;
117
 
118
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
119
    {
120
      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
121
        {
122
          if (firstuse == NULL_TREE)
123
            firstuse = USE_STMT (use_p);
124
          else
125
            if (firstuse != USE_STMT (use_p))
126
              return false;
127
        }
128
    }
129
 
130
  return true;
131
}
132
 
133
/* Some global stores don't necessarily have V_MAY_DEF's of global variables,
134
   but we still must avoid moving them around.  */
135
 
136
bool
137
is_hidden_global_store (tree stmt)
138
{
139
  /* Check virtual definitions.  If we get here, the only virtual
140
     definitions we should see are those generated by assignment
141
     statements.  */
142
  if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
143
    {
144
      tree lhs;
145
 
146
      gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR);
147
 
148
      /* Note that we must not check the individual virtual operands
149
         here.  In particular, if this is an aliased store, we could
150
         end up with something like the following (SSA notation
151
         redacted for brevity):
152
 
153
                foo (int *p, int i)
154
                {
155
                  int x;
156
                  p_1 = (i_2 > 3) ? &x : p;
157
 
158
                  # x_4 = V_MAY_DEF <x_3>
159
                  *p_1 = 5;
160
 
161
                  return 2;
162
                }
163
 
164
         Notice that the store to '*p_1' should be preserved, if we
165
         were to check the virtual definitions in that store, we would
166
         not mark it needed.  This is because 'x' is not a global
167
         variable.
168
 
169
         Therefore, we check the base address of the LHS.  If the
170
         address is a pointer, we check if its name tag or symbol tag is
171
         a global variable.  Otherwise, we check if the base variable
172
         is a global.  */
173
      lhs = TREE_OPERAND (stmt, 0);
174
      if (REFERENCE_CLASS_P (lhs))
175
        lhs = get_base_address (lhs);
176
 
177
      if (lhs == NULL_TREE)
178
        {
179
          /* If LHS is NULL, it means that we couldn't get the base
180
             address of the reference.  In which case, we should not
181
             move this store.  */
182
          return true;
183
        }
184
      else if (DECL_P (lhs))
185
        {
186
          /* If the store is to a global symbol, we need to keep it.  */
187
          if (is_global_var (lhs))
188
            return true;
189
 
190
        }
191
      else if (INDIRECT_REF_P (lhs))
192
        {
193
          tree ptr = TREE_OPERAND (lhs, 0);
194
          struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
195
          tree nmt = (pi) ? pi->name_mem_tag : NULL_TREE;
196
          tree smt = var_ann (SSA_NAME_VAR (ptr))->symbol_mem_tag;
197
 
198
          /* If either the name tag or the symbol tag for PTR is a
199
             global variable, then the store is necessary.  */
200
          if ((nmt && is_global_var (nmt))
201
              || (smt && is_global_var (smt)))
202
            {
203
              return true;
204
            }
205
        }
206
      else
207
        gcc_unreachable ();
208
    }
209
  return false;
210
}
211
 
212
/* Find the nearest common dominator of all of the immediate uses in IMM.  */
213
 
214
static basic_block
215
nearest_common_dominator_of_uses (tree stmt)
216
{
217
  bitmap blocks = BITMAP_ALLOC (NULL);
218
  basic_block commondom;
219
  unsigned int j;
220
  bitmap_iterator bi;
221
  ssa_op_iter op_iter;
222
  imm_use_iterator imm_iter;
223
  use_operand_p use_p;
224
  tree var;
225
 
226
  bitmap_clear (blocks);
227
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS)
228
    {
229
      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var)
230
        {
231
          tree usestmt = USE_STMT (use_p);
232
          basic_block useblock;
233
 
234
          if (TREE_CODE (usestmt) == PHI_NODE)
235
            {
236
              int idx = PHI_ARG_INDEX_FROM_USE (use_p);
237
 
238
              useblock = PHI_ARG_EDGE (usestmt, idx)->src;
239
            }
240
          else
241
            {
242
              useblock = bb_for_stmt (usestmt);
243
            }
244
 
245
          /* Short circuit. Nothing dominates the entry block.  */
246
          if (useblock == ENTRY_BLOCK_PTR)
247
            {
248
              BITMAP_FREE (blocks);
249
              return NULL;
250
            }
251
          bitmap_set_bit (blocks, useblock->index);
252
        }
253
    }
254
  commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks));
255
  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi)
256
    commondom = nearest_common_dominator (CDI_DOMINATORS, commondom,
257
                                          BASIC_BLOCK (j));
258
  BITMAP_FREE (blocks);
259
  return commondom;
260
}
261
 
262
/* Given a statement (STMT) and the basic block it is currently in (FROMBB),
263
   determine the location to sink the statement to, if any.
264
   Return the basic block to sink it to, or NULL if we should not sink
265
   it.  */
266
 
267
static tree
268
statement_sink_location (tree stmt, basic_block frombb)
269
{
270
  tree use, def;
271
  use_operand_p one_use = NULL_USE_OPERAND_P;
272
  basic_block sinkbb;
273
  use_operand_p use_p;
274
  def_operand_p def_p;
275
  ssa_op_iter iter;
276
  stmt_ann_t ann;
277
  tree rhs;
278
  imm_use_iterator imm_iter;
279
 
280
  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
281
    {
282
      FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def)
283
        {
284
          break;
285
        }
286
      if (one_use != NULL_USE_OPERAND_P)
287
        break;
288
    }
289
 
290
  /* Return if there are no immediate uses of this stmt.  */
291
  if (one_use == NULL_USE_OPERAND_P)
292
    return NULL;
293
 
294
  if (TREE_CODE (stmt) != MODIFY_EXPR)
295
    return NULL;
296
  rhs = TREE_OPERAND (stmt, 1);
297
 
298
  /* There are a few classes of things we can't or don't move, some because we
299
     don't have code to handle it, some because it's not profitable and some
300
     because it's not legal.
301
 
302
     We can't sink things that may be global stores, at least not without
303
     calculating a lot more information, because we may cause it to no longer
304
     be seen by an external routine that needs it depending on where it gets
305
     moved to.
306
 
307
     We don't want to sink loads from memory.
308
 
309
     We can't sink statements that end basic blocks without splitting the
310
     incoming edge for the sink location to place it there.
311
 
312
     We can't sink statements that have volatile operands.
313
 
314
     We don't want to sink dead code, so anything with 0 immediate uses is not
315
     sunk.
316
 
317
  */
318
  ann = stmt_ann (stmt);
319
  if (stmt_ends_bb_p (stmt)
320
      || TREE_SIDE_EFFECTS (rhs)
321
      || TREE_CODE (rhs) == EXC_PTR_EXPR
322
      || TREE_CODE (rhs) == FILTER_EXPR
323
      || is_hidden_global_store (stmt)
324
      || ann->has_volatile_ops
325
      || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
326
    return NULL;
327
 
328
  FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
329
    {
330
      tree def = DEF_FROM_PTR (def_p);
331
      if (is_global_var (SSA_NAME_VAR (def))
332
          || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def))
333
        return NULL;
334
    }
335
 
336
  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
337
    {
338
      tree use = USE_FROM_PTR (use_p);
339
      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use))
340
        return NULL;
341
    }
342
 
343
  /* If all the immediate uses are not in the same place, find the nearest
344
     common dominator of all the immediate uses.  For PHI nodes, we have to
345
     find the nearest common dominator of all of the predecessor blocks, since
346
     that is where insertion would have to take place.  */
347
  if (!all_immediate_uses_same_place (stmt))
348
    {
349
      basic_block commondom = nearest_common_dominator_of_uses (stmt);
350
 
351
      if (commondom == frombb)
352
        return NULL;
353
 
354
      /* Our common dominator has to be dominated by frombb in order to be a
355
         trivially safe place to put this statement, since it has multiple
356
         uses.  */
357
      if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
358
        return NULL;
359
 
360
      /* It doesn't make sense to move to a dominator that post-dominates
361
         frombb, because it means we've just moved it into a path that always
362
         executes if frombb executes, instead of reducing the number of
363
         executions .  */
364
      if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom))
365
        {
366
          if (dump_file && (dump_flags & TDF_DETAILS))
367
            fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n");
368
          return NULL;
369
        }
370
 
371
      if (commondom == frombb || commondom->loop_depth > frombb->loop_depth)
372
        return NULL;
373
      if (dump_file && (dump_flags & TDF_DETAILS))
374
        {
375
          fprintf (dump_file, "Common dominator of all uses is %d\n",
376
                   commondom->index);
377
        }
378
      return first_stmt (commondom);
379
    }
380
 
381
  use = USE_STMT (one_use);
382
  if (TREE_CODE (use) != PHI_NODE)
383
    {
384
      sinkbb = bb_for_stmt (use);
385
      if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
386
          || sinkbb->loop_father != frombb->loop_father)
387
        return NULL;
388
      return use;
389
    }
390
 
391
  /* Note that at this point, all uses must be in the same statement, so it
392
     doesn't matter which def op we choose, pick the first one.  */
393
  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
394
    break;
395
 
396
 
397
  sinkbb = find_bb_for_arg (use, def);
398
  if (!sinkbb)
399
    return NULL;
400
 
401
  /* This will happen when you have
402
     a_3 = PHI <a_13, a_26>
403
 
404
     a_26 = V_MAY_DEF <a_3>
405
 
406
     If the use is a phi, and is in the same bb as the def,
407
     we can't sink it.  */
408
 
409
  if (bb_for_stmt (use) == frombb)
410
    return NULL;
411
  if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth
412
      || sinkbb->loop_father != frombb->loop_father)
413
    return NULL;
414
 
415
  return first_stmt (sinkbb);
416
}
417
 
418
/* Perform code sinking on BB */
419
 
420
static void
421
sink_code_in_bb (basic_block bb)
422
{
423
  basic_block son;
424
  block_stmt_iterator bsi;
425
  edge_iterator ei;
426
  edge e;
427
 
428
  /* If this block doesn't dominate anything, there can't be any place to sink
429
     the statements to.  */
430
  if (first_dom_son (CDI_DOMINATORS, bb) == NULL)
431
    goto earlyout;
432
 
433
  /* We can't move things across abnormal edges, so don't try.  */
434
  FOR_EACH_EDGE (e, ei, bb->succs)
435
    if (e->flags & EDGE_ABNORMAL)
436
      goto earlyout;
437
 
438
  for (bsi = bsi_last (bb); !bsi_end_p (bsi);)
439
    {
440
      tree stmt = bsi_stmt (bsi);
441
      block_stmt_iterator tobsi;
442
      tree sinkstmt;
443
 
444
      sinkstmt = statement_sink_location (stmt, bb);
445
      if (!sinkstmt)
446
        {
447
          if (!bsi_end_p (bsi))
448
            bsi_prev (&bsi);
449
          continue;
450
        }
451
      if (dump_file)
452
        {
453
          fprintf (dump_file, "Sinking ");
454
          print_generic_expr (dump_file, stmt, TDF_VOPS);
455
          fprintf (dump_file, " from bb %d to bb %d\n",
456
                   bb->index, bb_for_stmt (sinkstmt)->index);
457
        }
458
      tobsi = bsi_for_stmt (sinkstmt);
459
      /* Find the first non-label.  */
460
      while (!bsi_end_p (tobsi)
461
             && TREE_CODE (bsi_stmt (tobsi)) == LABEL_EXPR)
462
        bsi_next (&tobsi);
463
 
464
      /* If this is the end of the basic block, we need to insert at the end
465
         of the basic block.  */
466
      if (bsi_end_p (tobsi))
467
        bsi_move_to_bb_end (&bsi, bb_for_stmt (sinkstmt));
468
      else
469
        bsi_move_before (&bsi, &tobsi);
470
 
471
      sink_stats.sunk++;
472
      if (!bsi_end_p (bsi))
473
        bsi_prev (&bsi);
474
 
475
    }
476
 earlyout:
477
  for (son = first_dom_son (CDI_POST_DOMINATORS, bb);
478
       son;
479
       son = next_dom_son (CDI_POST_DOMINATORS, son))
480
    {
481
      sink_code_in_bb (son);
482
    }
483
}
484
 
485
/* Perform code sinking.
486
   This moves code down the flowgraph when we know it would be
487
   profitable to do so, or it wouldn't increase the number of
488
   executions of the statement.
489
 
490
   IE given
491
 
492
   a_1 = b + c;
493
   if (<something>)
494
   {
495
   }
496
   else
497
   {
498
     foo (&b, &c);
499
     a_5 = b + c;
500
   }
501
   a_6 = PHI (a_5, a_1);
502
   USE a_6.
503
 
504
   we'll transform this into:
505
 
506
   if (<something>)
507
   {
508
      a_1 = b + c;
509
   }
510
   else
511
   {
512
      foo (&b, &c);
513
      a_5 = b + c;
514
   }
515
   a_6 = PHI (a_5, a_1);
516
   USE a_6.
517
 
518
   Note that this reduces the number of computations of a = b + c to 1
519
   when we take the else edge, instead of 2.
520
*/
521
static void
522
execute_sink_code (void)
523
{
524
  struct loops *loops = loop_optimizer_init (LOOPS_NORMAL);
525
 
526
  connect_infinite_loops_to_exit ();
527
  memset (&sink_stats, 0, sizeof (sink_stats));
528
  calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
529
  sink_code_in_bb (EXIT_BLOCK_PTR);
530
  if (dump_file && (dump_flags & TDF_STATS))
531
    fprintf (dump_file, "Sunk statements:%d\n", sink_stats.sunk);
532
  free_dominance_info (CDI_POST_DOMINATORS);
533
  remove_fake_exit_edges ();
534
  loop_optimizer_finalize (loops);
535
}
536
 
537
/* Gate and execute functions for PRE.  */
538
 
539
static unsigned int
540
do_sink (void)
541
{
542
  execute_sink_code ();
543
  return 0;
544
}
545
 
546
static bool
547
gate_sink (void)
548
{
549
  return flag_tree_sink != 0;
550
}
551
 
552
struct tree_opt_pass pass_sink_code =
553
{
554
  "sink",                               /* name */
555
  gate_sink,                            /* gate */
556
  do_sink,                              /* execute */
557
  NULL,                                 /* sub */
558
  NULL,                                 /* next */
559
  0,                                     /* static_pass_number */
560
  TV_TREE_SINK,                         /* tv_id */
561
  PROP_no_crit_edges | PROP_cfg
562
    | PROP_ssa | PROP_alias,            /* properties_required */
563
  0,                                     /* properties_provided */
564
  0,                                     /* properties_destroyed */
565
  0,                                     /* todo_flags_start */
566
  TODO_update_ssa
567
    | TODO_dump_func
568
    | TODO_ggc_collect
569
    | TODO_verify_ssa,                  /* todo_flags_finish */
570
 
571
};

powered by: WebSVN 2.1.0

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