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

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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