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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-ssa-ter.c] - Blame information for rev 723

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

Line No. Rev Author Line
1 684 jeremybenn
/* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
2
   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
3
   Free Software Foundation, Inc.
4
   Contributed by Andrew MacLeod  <amacleod@redhat.com>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify
9
it under the terms of the GNU General Public License as published by
10
the Free Software Foundation; either version 3, or (at your option)
11
any later version.
12
 
13
GCC is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
GNU General Public License for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
 
23
#include "config.h"
24
#include "system.h"
25
#include "coretypes.h"
26
#include "tm.h"
27
#include "tree.h"
28
#include "tree-pretty-print.h"
29
#include "gimple-pretty-print.h"
30
#include "bitmap.h"
31
#include "tree-flow.h"
32
#include "tree-dump.h"
33
#include "tree-ssa-live.h"
34
#include "flags.h"
35
 
36
 
37
/* Temporary Expression Replacement (TER)
38
 
39
   Replace SSA version variables during out-of-ssa with their defining
40
   expression if there is only one use of the variable.
41
 
42
   This pass is required in order for the RTL expansion pass to see larger
43
   chunks of code.  This allows it to make better choices on RTL pattern
44
   selection.  When expand is rewritten and merged with out-of-ssa, and
45
   understands SSA, this should be eliminated.
46
 
47
   A pass is made through the function, one block at a time.  No cross block
48
   information is tracked.
49
 
50
   Variables which only have one use, and whose defining stmt is considered
51
   a replaceable expression (see is_replaceable_p) are tracked to see whether
52
   they can be replaced at their use location.
53
 
54
   n_12 = C * 10
55
   a_2 = b_5 + 6
56
   v_9 = a_2 * n_12
57
 
58
   if there are the only use of n_12 and a_2, TER will substitute in their
59
   expressions in v_9, and end up with:
60
 
61
   v_9 = (b_5 + 6) * (C * 10)
62
 
63
   which will then have the ssa_name assigned to regular variables, and the
64
   resulting code which will be passed to the expander looks something like:
65
 
66
   v = (b + 6) * (C * 10)
67
 
68
 
69
   This requires ensuring that none of the variables used by the expression
70
   change between the def point and where it is used.  Furthermore, if any
71
   of the ssa_names used in this expression are themselves replaceable, we
72
   have to ensure none of that expressions' arguments change either.
73
   Although SSA_NAMES themselves don't change, this pass is performed after
74
   coalescing has coalesced different SSA_NAMES together, so there could be a
75
   definition of an SSA_NAME which is coalesced with a use that causes a
76
   problem, i.e.,
77
 
78
   PHI b_5 = <b_8(2), b_14(1)>
79
   <...>
80
   a_2 = b_5 + 6
81
   b_8 = c_4 + 4
82
   v_9 = a_2 * n_12
83
   <...>
84
 
85
   If b_5, b_8 and b_14 are all coalesced together...
86
   The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
87
   because b_8 is in fact killing the value of b_5 since they share a partition
88
   and will be assigned the same memory or register location.
89
 
90
   TER implements this but stepping through the instructions in a block and
91
   tracking potential expressions for replacement, and the partitions they are
92
   dependent on.  Expressions are represented by the SSA_NAME_VERSION of the
93
   DEF on the LHS of a GIMPLE_ASSIGN and the expression is the RHS.
94
 
95
   When a stmt is determined to be a possible replacement expression, the
96
   following steps are taken:
97
 
98
   EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the
99
   def and any uses in the expression.  non-NULL means the expression is being
100
   tracked.  The UID's themselves are used to prevent TER substitution into
101
   accumulating sequences, i.e.,
102
 
103
   x = x + y
104
   x = x + z
105
   x = x + w
106
   etc.
107
   this can result in very large expressions which don't accomplish anything
108
   see PR tree-optimization/17549.
109
 
110
   PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any
111
   partition which is used in the expression.  This is primarily used to remove
112
   an expression from the partition kill lists when a decision is made whether
113
   to replace it or not.  This is indexed by ssa version number as well, and
114
   indicates a partition number.  virtual operands are not tracked individually,
115
   but they are summarized by an artificial partition called VIRTUAL_PARTITION.
116
   This means a MAY or MUST def will kill *ALL* expressions that are dependent
117
   on a virtual operand.
118
   Note that the EXPR_DECL_UID and this bitmap represent very similar
119
   information, but the info in one is not easy to obtain from the other.
120
 
121
   KILL_LIST is yet another bitmap array, this time it is indexed by partition
122
   number, and represents a list of active expressions which will will no
123
   longer be valid if a definition into this partition takes place.
124
 
125
   PARTITION_IN_USE is simply a bitmap which is used to track which partitions
126
   currently have something in their kill list.  This is used at the end of
127
   a block to clear out the KILL_LIST bitmaps at the end of each block.
128
 
129
   NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store
130
   dependencies which will be reused by the current definition. All the uses
131
   on an expression are processed before anything else is done. If a use is
132
   determined to be a replaceable expression AND the current stmt is also going
133
   to be replaceable, all the dependencies of this replaceable use will be
134
   picked up by the current stmt's expression. Rather than recreate them, they
135
   are simply copied here and then copied into the new expression when it is
136
   processed.
137
 
138
   a_2 = b_5 + 6
139
   v_8 = a_2 + c_4
140
 
141
   a_2's expression 'b_5 + 6' is determined to be replaceable at the use
142
   location. It is dependent on the partition 'b_5' is in. This is cached into
143
   the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for
144
   replaceability, it is a candidate, and it is dependent on the partition
145
   b_5 is in *NOT* a_2, as well as c_4's partition.
146
 
147
   if v_8 is also replaceable:
148
 
149
   x_9 = v_8 * 5
150
 
151
   x_9 is dependent on partitions b_5, and c_4
152
 
153
   if a statement is found which has either of those partitions written to
154
   before x_9 is used, then x_9 itself is NOT replaceable.  */
155
 
156
 
157
/* Temporary Expression Replacement (TER) table information.  */
158
 
159
typedef struct temp_expr_table_d
160
{
161
  var_map map;
162
  bitmap *partition_dependencies;       /* Partitions expr is dependent on.  */
163
  bitmap replaceable_expressions;       /* Replacement expression table.  */
164
  bitmap *expr_decl_uids;               /* Base uids of exprs.  */
165
  bitmap *kill_list;                    /* Expr's killed by a partition.  */
166
  int virtual_partition;                /* Pseudo partition for virtual ops.  */
167
  bitmap partition_in_use;              /* Partitions with kill entries.  */
168
  bitmap new_replaceable_dependencies;  /* Holding place for pending dep's.  */
169
  int *num_in_part;                     /* # of ssa_names in a partition.  */
170
  int *call_cnt;                        /* Call count at definition.  */
171
} *temp_expr_table_p;
172
 
173
/* Used to indicate a dependency on VDEFs.  */
174
#define VIRTUAL_PARTITION(table)        (table->virtual_partition)
175
 
176
#ifdef ENABLE_CHECKING
177
extern void debug_ter (FILE *, temp_expr_table_p);
178
#endif
179
 
180
 
181
/* Create a new TER table for MAP.  */
182
 
183
static temp_expr_table_p
184
new_temp_expr_table (var_map map)
185
{
186
  temp_expr_table_p t;
187
  unsigned x;
188
 
189
  t = XNEW (struct temp_expr_table_d);
190
  t->map = map;
191
 
192
  t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
193
  t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
194
  t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
195
 
196
  t->partition_in_use = BITMAP_ALLOC (NULL);
197
 
198
  t->virtual_partition = num_var_partitions (map);
199
  t->new_replaceable_dependencies = BITMAP_ALLOC (NULL);
200
 
201
  t->replaceable_expressions = NULL;
202
  t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
203
  for (x = 1; x < num_ssa_names; x++)
204
    {
205
      int p;
206
      tree name = ssa_name (x);
207
      if (!name)
208
        continue;
209
      p = var_to_partition (map, name);
210
      if (p != NO_PARTITION)
211
        t->num_in_part[p]++;
212
    }
213
  t->call_cnt = XCNEWVEC (int, num_ssa_names + 1);
214
 
215
  return t;
216
}
217
 
218
 
219
/* Free TER table T.  If there are valid replacements, return the expression
220
   vector.  */
221
 
222
static bitmap
223
free_temp_expr_table (temp_expr_table_p t)
224
{
225
  bitmap ret = NULL;
226
 
227
#ifdef ENABLE_CHECKING
228
  unsigned x;
229
  for (x = 0; x <= num_var_partitions (t->map); x++)
230
    gcc_assert (!t->kill_list[x]);
231
  for (x = 0; x < num_ssa_names; x++)
232
    {
233
      gcc_assert (t->expr_decl_uids[x] == NULL);
234
      gcc_assert (t->partition_dependencies[x] == NULL);
235
    }
236
#endif
237
 
238
  BITMAP_FREE (t->partition_in_use);
239
  BITMAP_FREE (t->new_replaceable_dependencies);
240
 
241
  free (t->expr_decl_uids);
242
  free (t->kill_list);
243
  free (t->partition_dependencies);
244
  free (t->num_in_part);
245
  free (t->call_cnt);
246
 
247
  if (t->replaceable_expressions)
248
    ret = t->replaceable_expressions;
249
 
250
  free (t);
251
  return ret;
252
}
253
 
254
 
255
/* Return TRUE if VERSION is to be replaced by an expression in TAB.  */
256
 
257
static inline bool
258
version_to_be_replaced_p (temp_expr_table_p tab, int version)
259
{
260
  if (!tab->replaceable_expressions)
261
    return false;
262
  return bitmap_bit_p (tab->replaceable_expressions, version);
263
}
264
 
265
 
266
/* Add partition P to the list if partitions VERSION is dependent on.  TAB is
267
   the expression table */
268
 
269
static inline void
270
make_dependent_on_partition (temp_expr_table_p tab, int version, int p)
271
{
272
  if (!tab->partition_dependencies[version])
273
    tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
274
 
275
  bitmap_set_bit (tab->partition_dependencies[version], p);
276
}
277
 
278
 
279
/* Add VER to the kill list for P.  TAB is the expression table */
280
 
281
static inline void
282
add_to_partition_kill_list (temp_expr_table_p tab, int p, int ver)
283
{
284
  if (!tab->kill_list[p])
285
    {
286
      tab->kill_list[p] = BITMAP_ALLOC (NULL);
287
      bitmap_set_bit (tab->partition_in_use, p);
288
    }
289
  bitmap_set_bit (tab->kill_list[p], ver);
290
}
291
 
292
 
293
/* Remove VER from the partition kill list for P.  TAB is the expression
294
   table.  */
295
 
296
static inline void
297
remove_from_partition_kill_list (temp_expr_table_p tab, int p, int version)
298
{
299
  gcc_checking_assert (tab->kill_list[p]);
300
  bitmap_clear_bit (tab->kill_list[p], version);
301
  if (bitmap_empty_p (tab->kill_list[p]))
302
    {
303
      bitmap_clear_bit (tab->partition_in_use, p);
304
      BITMAP_FREE (tab->kill_list[p]);
305
    }
306
}
307
 
308
 
309
/* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
310
   replaceable by an expression, add a dependence each of the elements of the
311
   expression.  These are contained in the new_replaceable list.  TAB is the
312
   expression table.  */
313
 
314
static void
315
add_dependence (temp_expr_table_p tab, int version, tree var)
316
{
317
  int i;
318
  bitmap_iterator bi;
319
  unsigned x;
320
 
321
  i = SSA_NAME_VERSION (var);
322
  if (version_to_be_replaced_p (tab, i))
323
    {
324
      if (!bitmap_empty_p (tab->new_replaceable_dependencies))
325
        {
326
          /* Version will now be killed by a write to any partition the
327
             substituted expression would have been killed by.  */
328
          EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
329
            add_to_partition_kill_list (tab, x, version);
330
 
331
          /* Rather than set partition_dependencies and in_use lists bit by
332
             bit, simply OR in the new_replaceable_dependencies bits.  */
333
          if (!tab->partition_dependencies[version])
334
            tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
335
          bitmap_ior_into (tab->partition_dependencies[version],
336
                           tab->new_replaceable_dependencies);
337
          bitmap_ior_into (tab->partition_in_use,
338
                           tab->new_replaceable_dependencies);
339
          /* It is only necessary to add these once.  */
340
          bitmap_clear (tab->new_replaceable_dependencies);
341
        }
342
    }
343
  else
344
    {
345
      i = var_to_partition (tab->map, var);
346
      gcc_checking_assert (i != NO_PARTITION);
347
      gcc_checking_assert (tab->num_in_part[i] != 0);
348
      /* Only dependencies on ssa_names which are coalesced with something need
349
         to be tracked.  Partitions with containing only a single SSA_NAME
350
         *cannot* have their value changed.  */
351
      if (tab->num_in_part[i] > 1)
352
        {
353
          add_to_partition_kill_list (tab, i, version);
354
          make_dependent_on_partition (tab, version, i);
355
        }
356
    }
357
}
358
 
359
 
360
/* Return TRUE if expression STMT is suitable for replacement.
361
   TER is true if is_replaceable_p is called from within TER, false
362
   when used from within stmt_is_replaceable_p, i.e. EXPAND_INITIALIZER
363
   expansion.  The differences are that with !TER some tests are skipped
364
   to make it more aggressive (doesn't require the same bb, or for -O0
365
   same locus and same BLOCK), on the other side never considers memory
366
   loads as replaceable, because those don't ever lead into constant
367
   expressions.  */
368
 
369
static inline bool
370
is_replaceable_p (gimple stmt, bool ter)
371
{
372
  use_operand_p use_p;
373
  tree def;
374
  gimple use_stmt;
375
  location_t locus1, locus2;
376
  tree block1, block2;
377
 
378
  /* Only consider modify stmts.  */
379
  if (!is_gimple_assign (stmt))
380
    return false;
381
 
382
  /* If the statement may throw an exception, it cannot be replaced.  */
383
  if (stmt_could_throw_p (stmt))
384
    return false;
385
 
386
  /* Punt if there is more than 1 def.  */
387
  def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
388
  if (!def)
389
    return false;
390
 
391
  /* Only consider definitions which have a single use.  */
392
  if (!single_imm_use (def, &use_p, &use_stmt))
393
    return false;
394
 
395
  /* If the use isn't in this block, it wont be replaced either.  */
396
  if (ter && gimple_bb (use_stmt) != gimple_bb (stmt))
397
    return false;
398
 
399
  locus1 = gimple_location (stmt);
400
  block1 = gimple_block (stmt);
401
 
402
  if (gimple_code (use_stmt) == GIMPLE_PHI)
403
    {
404
      locus2 = 0;
405
      block2 = NULL_TREE;
406
    }
407
  else
408
    {
409
      locus2 = gimple_location (use_stmt);
410
      block2 = gimple_block (use_stmt);
411
    }
412
 
413
  if (!optimize
414
      && ter
415
      && ((locus1 && locus1 != locus2) || (block1 && block1 != block2)))
416
    return false;
417
 
418
  /* Used in this block, but at the TOP of the block, not the end.  */
419
  if (gimple_code (use_stmt) == GIMPLE_PHI)
420
    return false;
421
 
422
  /* There must be no VDEFs.  */
423
  if (gimple_vdef (stmt))
424
    return false;
425
 
426
  /* Without alias info we can't move around loads.  */
427
  if ((!optimize || !ter)
428
      && gimple_assign_single_p (stmt)
429
      && !is_gimple_val (gimple_assign_rhs1 (stmt)))
430
    return false;
431
 
432
  /* Float expressions must go through memory if float-store is on.  */
433
  if (flag_float_store
434
      && FLOAT_TYPE_P (gimple_expr_type (stmt)))
435
    return false;
436
 
437
  /* An assignment with a register variable on the RHS is not
438
     replaceable.  */
439
  if (gimple_assign_rhs_code (stmt) == VAR_DECL
440
      && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
441
    return false;
442
 
443
  /* No function calls can be replaced.  */
444
  if (is_gimple_call (stmt))
445
    return false;
446
 
447
  /* Leave any stmt with volatile operands alone as well.  */
448
  if (gimple_has_volatile_ops (stmt))
449
    return false;
450
 
451
  return true;
452
}
453
 
454
 
455
/* Variant of is_replaceable_p test for use in EXPAND_INITIALIZER
456
   expansion.  */
457
 
458
bool
459
stmt_is_replaceable_p (gimple stmt)
460
{
461
  return is_replaceable_p (stmt, false);
462
}
463
 
464
 
465
/* This function will remove the expression for VERSION from replacement
466
   consideration in table TAB.  If FREE_EXPR is true, then remove the
467
   expression from consideration as well by freeing the decl uid bitmap.  */
468
 
469
static void
470
finished_with_expr (temp_expr_table_p tab, int version, bool free_expr)
471
{
472
  unsigned i;
473
  bitmap_iterator bi;
474
 
475
  /* Remove this expression from its dependent lists.  The partition dependence
476
     list is retained and transfered later to whomever uses this version.  */
477
  if (tab->partition_dependencies[version])
478
    {
479
      EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
480
        remove_from_partition_kill_list (tab, i, version);
481
      BITMAP_FREE (tab->partition_dependencies[version]);
482
    }
483
  if (free_expr)
484
    BITMAP_FREE (tab->expr_decl_uids[version]);
485
}
486
 
487
 
488
/* Create an expression entry for a replaceable expression.  */
489
 
490
static void
491
process_replaceable (temp_expr_table_p tab, gimple stmt, int call_cnt)
492
{
493
  tree var, def, basevar;
494
  int version;
495
  ssa_op_iter iter;
496
  bitmap def_vars, use_vars;
497
 
498
  gcc_checking_assert (is_replaceable_p (stmt, true));
499
 
500
  def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
501
  version = SSA_NAME_VERSION (def);
502
  basevar = SSA_NAME_VAR (def);
503
  def_vars = BITMAP_ALLOC (NULL);
504
 
505
  bitmap_set_bit (def_vars, DECL_UID (basevar));
506
 
507
  /* Add this expression to the dependency list for each use partition.  */
508
  FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
509
    {
510
      int var_version = SSA_NAME_VERSION (var);
511
 
512
      use_vars = tab->expr_decl_uids[var_version];
513
      add_dependence (tab, version, var);
514
      if (use_vars)
515
        {
516
          bitmap_ior_into (def_vars, use_vars);
517
          BITMAP_FREE (tab->expr_decl_uids[var_version]);
518
        }
519
      else
520
        bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
521
    }
522
  tab->expr_decl_uids[version] = def_vars;
523
 
524
  /* If there are VUSES, add a dependence on virtual defs.  */
525
  if (gimple_vuse (stmt))
526
    {
527
      make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
528
      add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
529
    }
530
 
531
  tab->call_cnt[version] = call_cnt;
532
}
533
 
534
 
535
/* This function removes any expression in TAB which is dependent on PARTITION
536
   from consideration, making it not replaceable.  */
537
 
538
static inline void
539
kill_expr (temp_expr_table_p tab, int partition)
540
{
541
  unsigned version;
542
 
543
  /* Mark every active expr dependent on this var as not replaceable.
544
     finished_with_expr can modify the bitmap, so we can't execute over it.  */
545
  while (tab->kill_list[partition])
546
    {
547
      version = bitmap_first_set_bit (tab->kill_list[partition]);
548
      finished_with_expr (tab, version, true);
549
    }
550
 
551
  gcc_checking_assert (!tab->kill_list[partition]);
552
}
553
 
554
 
555
/* This function kills all expressions in TAB which are dependent on virtual
556
   partitions.  */
557
 
558
static inline void
559
kill_virtual_exprs (temp_expr_table_p tab)
560
{
561
  kill_expr (tab, VIRTUAL_PARTITION (tab));
562
}
563
 
564
 
565
/* Mark the expression associated with VAR as replaceable, and enter
566
   the defining stmt into the partition_dependencies table TAB.  If
567
   MORE_REPLACING is true, accumulate the pending partition dependencies.  */
568
 
569
static void
570
mark_replaceable (temp_expr_table_p tab, tree var, bool more_replacing)
571
{
572
  int version = SSA_NAME_VERSION (var);
573
 
574
  /* Move the dependence list to the pending listpending.  */
575
  if (more_replacing && tab->partition_dependencies[version])
576
    bitmap_ior_into (tab->new_replaceable_dependencies,
577
                     tab->partition_dependencies[version]);
578
 
579
  finished_with_expr (tab, version, !more_replacing);
580
 
581
  /* Set the replaceable expression.  */
582
  if (!tab->replaceable_expressions)
583
    tab->replaceable_expressions = BITMAP_ALLOC (NULL);
584
  bitmap_set_bit (tab->replaceable_expressions, version);
585
}
586
 
587
 
588
/* This function processes basic block BB, and looks for variables which can
589
   be replaced by their expressions.  Results are stored in the table TAB.  */
590
 
591
static void
592
find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
593
{
594
  gimple_stmt_iterator bsi;
595
  gimple stmt;
596
  tree def, use, fndecl;
597
  int partition;
598
  var_map map = tab->map;
599
  ssa_op_iter iter;
600
  bool stmt_replaceable;
601
  int cur_call_cnt = 0;
602
 
603
  for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
604
    {
605
      stmt = gsi_stmt (bsi);
606
 
607
      if (is_gimple_debug (stmt))
608
        continue;
609
 
610
      stmt_replaceable = is_replaceable_p (stmt, true);
611
 
612
      /* Determine if this stmt finishes an existing expression.  */
613
      FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
614
        {
615
          unsigned ver = SSA_NAME_VERSION (use);
616
 
617
          /* If this use is a potential replacement variable, process it.  */
618
          if (tab->expr_decl_uids[ver])
619
            {
620
              bool same_root_var = false;
621
              ssa_op_iter iter2;
622
              bitmap vars = tab->expr_decl_uids[ver];
623
 
624
              /* See if the root variables are the same.  If they are, we
625
                 do not want to do the replacement to avoid problems with
626
                 code size, see PR tree-optimization/17549.  */
627
              if (!bitmap_empty_p (vars))
628
                FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
629
                  {
630
                    if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
631
                      {
632
                        same_root_var = true;
633
                        break;
634
                      }
635
                  }
636
 
637
              /* If the stmt does a memory store and the replacement
638
                 is a load aliasing it avoid creating overlapping
639
                 assignments which we cannot expand correctly.  */
640
              if (gimple_vdef (stmt)
641
                  && gimple_assign_single_p (stmt))
642
                {
643
                  gimple def_stmt = SSA_NAME_DEF_STMT (use);
644
                  while (is_gimple_assign (def_stmt)
645
                         && gimple_assign_rhs_code (def_stmt) == SSA_NAME)
646
                    def_stmt
647
                      = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
648
                  if (gimple_vuse (def_stmt)
649
                      && gimple_assign_single_p (def_stmt)
650
                      && refs_may_alias_p (gimple_assign_lhs (stmt),
651
                                           gimple_assign_rhs1 (def_stmt)))
652
                    same_root_var = true;
653
                }
654
 
655
              /* Mark expression as replaceable unless stmt is volatile, or the
656
                 def variable has the same root variable as something in the
657
                 substitution list, or the def and use span a call such that
658
                 we'll expand lifetimes across a call.  */
659
              if (gimple_has_volatile_ops (stmt) || same_root_var
660
                  || (tab->call_cnt[ver] != cur_call_cnt
661
                      && SINGLE_SSA_USE_OPERAND (SSA_NAME_DEF_STMT (use), SSA_OP_USE)
662
                         == NULL_USE_OPERAND_P))
663
                finished_with_expr (tab, ver, true);
664
              else
665
                mark_replaceable (tab, use, stmt_replaceable);
666
            }
667
        }
668
 
669
      /* Next, see if this stmt kills off an active expression.  */
670
      FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
671
        {
672
          partition = var_to_partition (map, def);
673
          if (partition != NO_PARTITION && tab->kill_list[partition])
674
            kill_expr (tab, partition);
675
        }
676
 
677
      /* Increment counter if this is a non BUILT_IN call. We allow
678
         replacement over BUILT_IN calls since many will expand to inline
679
         insns instead of a true call.  */
680
      if (is_gimple_call (stmt)
681
          && !((fndecl = gimple_call_fndecl (stmt))
682
               && DECL_BUILT_IN (fndecl)))
683
        cur_call_cnt++;
684
 
685
      /* Now see if we are creating a new expression or not.  */
686
      if (stmt_replaceable)
687
        process_replaceable (tab, stmt, cur_call_cnt);
688
 
689
      /* Free any unused dependency lists.  */
690
      bitmap_clear (tab->new_replaceable_dependencies);
691
 
692
      /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
693
         including the current stmt.  */
694
      if (gimple_vdef (stmt))
695
        kill_virtual_exprs (tab);
696
    }
697
}
698
 
699
 
700
/* This function is the driver routine for replacement of temporary expressions
701
   in the SSA->normal phase, operating on MAP.  If there are replaceable
702
   expressions, a table is returned which maps SSA versions to the
703
   expressions they should be replaced with.  A NULL_TREE indicates no
704
   replacement should take place.  If there are no replacements at all,
705
   NULL is returned by the function, otherwise an expression vector indexed
706
   by SSA_NAME version numbers.  */
707
 
708
extern bitmap
709
find_replaceable_exprs (var_map map)
710
{
711
  basic_block bb;
712
  temp_expr_table_p table;
713
  bitmap ret;
714
 
715
  table = new_temp_expr_table (map);
716
  FOR_EACH_BB (bb)
717
    {
718
      find_replaceable_in_bb (table, bb);
719
      gcc_checking_assert (bitmap_empty_p (table->partition_in_use));
720
    }
721
 
722
  ret = free_temp_expr_table (table);
723
  return ret;
724
}
725
 
726
/* Dump TER expression table EXPR to file F.  */
727
 
728
void
729
dump_replaceable_exprs (FILE *f, bitmap expr)
730
{
731
  tree var;
732
  unsigned x;
733
 
734
  fprintf (f, "\nReplacing Expressions\n");
735
  for (x = 0; x < num_ssa_names; x++)
736
    if (bitmap_bit_p (expr, x))
737
      {
738
        var = ssa_name (x);
739
        print_generic_expr (f, var, TDF_SLIM);
740
        fprintf (f, " replace with --> ");
741
        print_gimple_stmt (f, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
742
        fprintf (f, "\n");
743
      }
744
  fprintf (f, "\n");
745
}
746
 
747
 
748
#ifdef ENABLE_CHECKING
749
/* Dump the status of the various tables in the expression table.  This is used
750
   exclusively to debug TER.  F is the place to send debug info and T is the
751
   table being debugged.  */
752
 
753
DEBUG_FUNCTION void
754
debug_ter (FILE *f, temp_expr_table_p t)
755
{
756
  unsigned x, y;
757
  bitmap_iterator bi;
758
 
759
  fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n",
760
           VIRTUAL_PARTITION (t));
761
  if (t->replaceable_expressions)
762
    dump_replaceable_exprs (f, t->replaceable_expressions);
763
  fprintf (f, "Currently tracking the following expressions:\n");
764
 
765
  for (x = 1; x < num_ssa_names; x++)
766
    if (t->expr_decl_uids[x])
767
      {
768
        print_generic_expr (f, ssa_name (x), TDF_SLIM);
769
        fprintf (f, " dep-parts : ");
770
        if (t->partition_dependencies[x]
771
            && !bitmap_empty_p (t->partition_dependencies[x]))
772
          {
773
            EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
774
              fprintf (f, "P%d ",y);
775
          }
776
        fprintf (f, "   basedecls: ");
777
        EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
778
          fprintf (f, "%d ",y);
779
        fprintf (f, "   call_cnt : %d",t->call_cnt[x]);
780
        fprintf (f, "\n");
781
      }
782
 
783
  bitmap_print (f, t->partition_in_use, "Partitions in use ",
784
                "\npartition KILL lists:\n");
785
 
786
  for (x = 0; x <= num_var_partitions (t->map); x++)
787
    if (t->kill_list[x])
788
      {
789
        fprintf (f, "Partition %d : ", x);
790
        EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
791
          fprintf (f, "_%d ",y);
792
      }
793
 
794
  fprintf (f, "\n----------\n");
795
}
796
#endif

powered by: WebSVN 2.1.0

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