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

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [gcc/] [tree-ssa-math-opts.c] - Blame information for rev 20

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

Line No. Rev Author Line
1 12 jlechner
/* Global, SSA-based optimizations using mathematical identities.
2
   Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
18
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
19
02110-1301, USA.  */
20
 
21
/* Currently, the only mini-pass in this file tries to CSE reciprocal
22
   operations.  These are common in sequences such as this one:
23
 
24
        modulus = sqrt(x*x + y*y + z*z);
25
        x = x / modulus;
26
        y = y / modulus;
27
        z = z / modulus;
28
 
29
   that can be optimized to
30
 
31
        modulus = sqrt(x*x + y*y + z*z);
32
        rmodulus = 1.0 / modulus;
33
        x = x * rmodulus;
34
        y = y * rmodulus;
35
        z = z * rmodulus;
36
 
37
   We do this for loop invariant divisors, and with this pass whenever
38
   we notice that a division has the same divisor multiple times.
39
 
40
   Of course, like in PRE, we don't insert a division if a dominator
41
   already has one.  However, this cannot be done as an extension of
42
   PRE for several reasons.
43
 
44
   First of all, with some experiments it was found out that the
45
   transformation is not always useful if there are only two divisions
46
   hy the same divisor.  This is probably because modern processors
47
   can pipeline the divisions; on older, in-order processors it should
48
   still be effective to optimize two divisions by the same number.
49
   We make this a param, and it shall be called N in the remainder of
50
   this comment.
51
 
52
   Second, if trapping math is active, we have less freedom on where
53
   to insert divisions: we can only do so in basic blocks that already
54
   contain one.  (If divisions don't trap, instead, we can insert
55
   divisions elsewhere, which will be in blocks that are common dominators
56
   of those that have the division).
57
 
58
   We really don't want to compute the reciprocal unless a division will
59
   be found.  To do this, we won't insert the division in a basic block
60
   that has less than N divisions *post-dominating* it.
61
 
62
   The algorithm constructs a subset of the dominator tree, holding the
63
   blocks containing the divisions and the common dominators to them,
64
   and walk it twice.  The first walk is in post-order, and it annotates
65
   each block with the number of divisions that post-dominate it: this
66
   gives information on where divisions can be inserted profitably.
67
   The second walk is in pre-order, and it inserts divisions as explained
68
   above, and replaces divisions by multiplications.
69
 
70
   In the best case, the cost of the pass is O(n_statements).  In the
71
   worst-case, the cost is due to creating the dominator tree subset,
72
   with a cost of O(n_basic_blocks ^ 2); however this can only happen
73
   for n_statements / n_basic_blocks statements.  So, the amortized cost
74
   of creating the dominator tree subset is O(n_basic_blocks) and the
75
   worst-case cost of the pass is O(n_statements * n_basic_blocks).
76
 
77
   More practically, the cost will be small because there are few
78
   divisions, and they tend to be in the same basic block, so insert_bb
79
   is called very few times.
80
 
81
   If we did this using domwalk.c, an efficient implementation would have
82
   to work on all the variables in a single pass, because we could not
83
   work on just a subset of the dominator tree, as we do now, and the
84
   cost would also be something like O(n_statements * n_basic_blocks).
85
   The data structures would be more complex in order to work on all the
86
   variables in a single pass.  */
87
 
88
#include "config.h"
89
#include "system.h"
90
#include "coretypes.h"
91
#include "tm.h"
92
#include "flags.h"
93
#include "tree.h"
94
#include "tree-flow.h"
95
#include "real.h"
96
#include "timevar.h"
97
#include "tree-pass.h"
98
#include "alloc-pool.h"
99
#include "basic-block.h"
100
#include "target.h"
101
 
102
 
103
/* This structure represents one basic block that either computes a
104
   division, or is a common dominator for basic block that compute a
105
   division.  */
106
struct occurrence {
107
  /* The basic block represented by this structure.  */
108
  basic_block bb;
109
 
110
  /* If non-NULL, the SSA_NAME holding the definition for a reciprocal
111
     inserted in BB.  */
112
  tree recip_def;
113
 
114
  /* If non-NULL, the MODIFY_EXPR for a reciprocal computation that
115
     was inserted in BB.  */
116
  tree recip_def_stmt;
117
 
118
  /* Pointer to a list of "struct occurrence"s for blocks dominated
119
     by BB.  */
120
  struct occurrence *children;
121
 
122
  /* Pointer to the next "struct occurrence"s in the list of blocks
123
     sharing a common dominator.  */
124
  struct occurrence *next;
125
 
126
  /* The number of divisions that are in BB before compute_merit.  The
127
     number of divisions that are in BB or post-dominate it after
128
     compute_merit.  */
129
  int num_divisions;
130
 
131
  /* True if the basic block has a division, false if it is a common
132
     dominator for basic blocks that do.  If it is false and trapping
133
     math is active, BB is not a candidate for inserting a reciprocal.  */
134
  bool bb_has_division;
135
};
136
 
137
 
138
/* The instance of "struct occurrence" representing the highest
139
   interesting block in the dominator tree.  */
140
static struct occurrence *occ_head;
141
 
142
/* Allocation pool for getting instances of "struct occurrence".  */
143
static alloc_pool occ_pool;
144
 
145
 
146
 
147
/* Allocate and return a new struct occurrence for basic block BB, and
148
   whose children list is headed by CHILDREN.  */
149
static struct occurrence *
150
occ_new (basic_block bb, struct occurrence *children)
151
{
152
  struct occurrence *occ;
153
 
154
  occ = bb->aux = pool_alloc (occ_pool);
155
  memset (occ, 0, sizeof (struct occurrence));
156
 
157
  occ->bb = bb;
158
  occ->children = children;
159
  return occ;
160
}
161
 
162
 
163
/* Insert NEW_OCC into our subset of the dominator tree.  P_HEAD points to a
164
   list of "struct occurrence"s, one per basic block, having IDOM as
165
   their common dominator.
166
 
167
   We try to insert NEW_OCC as deep as possible in the tree, and we also
168
   insert any other block that is a common dominator for BB and one
169
   block already in the tree.  */
170
 
171
static void
172
insert_bb (struct occurrence *new_occ, basic_block idom,
173
           struct occurrence **p_head)
174
{
175
  struct occurrence *occ, **p_occ;
176
 
177
  for (p_occ = p_head; (occ = *p_occ) != NULL; )
178
    {
179
      basic_block bb = new_occ->bb, occ_bb = occ->bb;
180
      basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb);
181
      if (dom == bb)
182
        {
183
          /* BB dominates OCC_BB.  OCC becomes NEW_OCC's child: remove OCC
184
             from its list.  */
185
          *p_occ = occ->next;
186
          occ->next = new_occ->children;
187
          new_occ->children = occ;
188
 
189
          /* Try the next block (it may as well be dominated by BB).  */
190
        }
191
 
192
      else if (dom == occ_bb)
193
        {
194
          /* OCC_BB dominates BB.  Tail recurse to look deeper.  */
195
          insert_bb (new_occ, dom, &occ->children);
196
          return;
197
        }
198
 
199
      else if (dom != idom)
200
        {
201
          gcc_assert (!dom->aux);
202
 
203
          /* There is a dominator between IDOM and BB, add it and make
204
             two children out of NEW_OCC and OCC.  First, remove OCC from
205
             its list.  */
206
          *p_occ = occ->next;
207
          new_occ->next = occ;
208
          occ->next = NULL;
209
 
210
          /* None of the previous blocks has DOM as a dominator: if we tail
211
             recursed, we would reexamine them uselessly. Just switch BB with
212
             DOM, and go on looking for blocks dominated by DOM.  */
213
          new_occ = occ_new (dom, new_occ);
214
        }
215
 
216
      else
217
        {
218
          /* Nothing special, go on with the next element.  */
219
          p_occ = &occ->next;
220
        }
221
    }
222
 
223
  /* No place was found as a child of IDOM.  Make BB a sibling of IDOM.  */
224
  new_occ->next = *p_head;
225
  *p_head = new_occ;
226
}
227
 
228
/* Register that we found a division in BB.  */
229
 
230
static inline void
231
register_division_in (basic_block bb)
232
{
233
  struct occurrence *occ;
234
 
235
  occ = (struct occurrence *) bb->aux;
236
  if (!occ)
237
    {
238
      occ = occ_new (bb, NULL);
239
      insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head);
240
    }
241
 
242
  occ->bb_has_division = true;
243
  occ->num_divisions++;
244
}
245
 
246
 
247
/* Compute the number of divisions that postdominate each block in OCC and
248
   its children.  */
249
 
250
static void
251
compute_merit (struct occurrence *occ)
252
{
253
  struct occurrence *occ_child;
254
  basic_block dom = occ->bb;
255
 
256
  for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
257
    {
258
      basic_block bb;
259
      if (occ_child->children)
260
        compute_merit (occ_child);
261
 
262
      if (flag_exceptions)
263
        bb = single_noncomplex_succ (dom);
264
      else
265
        bb = dom;
266
 
267
      if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb))
268
        occ->num_divisions += occ_child->num_divisions;
269
    }
270
}
271
 
272
 
273
/* Return whether USE_STMT is a floating-point division by DEF.  */
274
static inline bool
275
is_division_by (tree use_stmt, tree def)
276
{
277
  return TREE_CODE (use_stmt) == MODIFY_EXPR
278
         && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
279
         && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def;
280
}
281
 
282
/* Return the LHS of a RDIV_EXPR that computes a reciprocal in type TYPE.  */
283
static tree
284
get_constant_one (tree type)
285
{
286
  tree scalar, cst;
287
  int i;
288
 
289
  gcc_assert (FLOAT_TYPE_P (type));
290
  switch (TREE_CODE (type))
291
    {
292
    case REAL_TYPE:
293
      return build_real (type, dconst1);
294
 
295
    case VECTOR_TYPE:
296
      scalar = build_real (TREE_TYPE (type), dconst1);
297
 
298
      /* Create 'vect_cst_ = {cst,cst,...,cst}'  */
299
      cst = NULL_TREE;
300
      for (i = TYPE_VECTOR_SUBPARTS (type); --i >= 0; )
301
        cst = tree_cons (NULL_TREE, scalar, cst);
302
 
303
      return build_vector (type, cst);
304
 
305
    default:
306
      /* Complex operations have been split already.  */
307
      gcc_unreachable ();
308
    }
309
}
310
 
311
/* Walk the subset of the dominator tree rooted at OCC, setting the
312
   RECIP_DEF field to a definition of 1.0 / DEF that can be used in
313
   the given basic block.  The field may be left NULL, of course,
314
   if it is not possible or profitable to do the optimization.
315
 
316
   DEF_BSI is an iterator pointing at the statement defining DEF.
317
   If RECIP_DEF is set, a dominator already has a computation that can
318
   be used.  */
319
 
320
static void
321
insert_reciprocals (block_stmt_iterator *def_bsi, struct occurrence *occ,
322
                    tree def, tree recip_def, int threshold)
323
{
324
  tree type, new_stmt;
325
  block_stmt_iterator bsi;
326
  struct occurrence *occ_child;
327
 
328
  if (!recip_def
329
      && (occ->bb_has_division || !flag_trapping_math)
330
      && occ->num_divisions >= threshold)
331
    {
332
      /* Make a variable with the replacement and substitute it.  */
333
      type = TREE_TYPE (def);
334
      recip_def = make_rename_temp (type, "reciptmp");
335
      new_stmt = build2 (MODIFY_EXPR, void_type_node, recip_def,
336
                         fold_build2 (RDIV_EXPR, type, get_constant_one (type),
337
                                      def));
338
 
339
 
340
      if (occ->bb_has_division)
341
        {
342
          /* Case 1: insert before an existing division.  */
343
          bsi = bsi_after_labels (occ->bb);
344
          while (!bsi_end_p (bsi) && !is_division_by (bsi_stmt (bsi), def))
345
            bsi_next (&bsi);
346
 
347
          bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT);
348
        }
349
      else if (def_bsi && occ->bb == def_bsi->bb)
350
        {
351
          /* Case 2: insert right after the definition.  Note that this will
352
             never happen if the definition statement can throw, because in
353
             that case the sole successor of the statement's basic block will
354
             dominate all the uses as well.  */
355
          bsi_insert_after (def_bsi, new_stmt, BSI_NEW_STMT);
356
        }
357
      else
358
        {
359
          /* Case 3: insert in a basic block not containing defs/uses.  */
360
          bsi = bsi_after_labels (occ->bb);
361
          bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT);
362
        }
363
 
364
      occ->recip_def_stmt = new_stmt;
365
    }
366
 
367
  occ->recip_def = recip_def;
368
  for (occ_child = occ->children; occ_child; occ_child = occ_child->next)
369
    insert_reciprocals (def_bsi, occ_child, def, recip_def, threshold);
370
}
371
 
372
 
373
/* Replace the division at USE_P with a multiplication by the reciprocal, if
374
   possible.  */
375
 
376
static inline void
377
replace_reciprocal (use_operand_p use_p)
378
{
379
  tree use_stmt = USE_STMT (use_p);
380
  basic_block bb = bb_for_stmt (use_stmt);
381
  struct occurrence *occ = (struct occurrence *) bb->aux;
382
 
383
  if (occ->recip_def && use_stmt != occ->recip_def_stmt)
384
    {
385
      TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR);
386
      SET_USE (use_p, occ->recip_def);
387
      fold_stmt_inplace (use_stmt);
388
      update_stmt (use_stmt);
389
    }
390
}
391
 
392
 
393
/* Free OCC and return one more "struct occurrence" to be freed.  */
394
 
395
static struct occurrence *
396
free_bb (struct occurrence *occ)
397
{
398
  struct occurrence *child, *next;
399
 
400
  /* First get the two pointers hanging off OCC.  */
401
  next = occ->next;
402
  child = occ->children;
403
  occ->bb->aux = NULL;
404
  pool_free (occ_pool, occ);
405
 
406
  /* Now ensure that we don't recurse unless it is necessary.  */
407
  if (!child)
408
    return next;
409
  else
410
    {
411
      while (next)
412
        next = free_bb (next);
413
 
414
      return child;
415
    }
416
}
417
 
418
 
419
/* Look for floating-point divisions among DEF's uses, and try to
420
   replace them by multiplications with the reciprocal.  Add
421
   as many statements computing the reciprocal as needed.
422
 
423
   DEF must be a GIMPLE register of a floating-point type.  */
424
 
425
static void
426
execute_cse_reciprocals_1 (block_stmt_iterator *def_bsi, tree def)
427
{
428
  use_operand_p use_p;
429
  imm_use_iterator use_iter;
430
  struct occurrence *occ;
431
  int count = 0, threshold;
432
 
433
  gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def));
434
 
435
  FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
436
    {
437
      tree use_stmt = USE_STMT (use_p);
438
      if (is_division_by (use_stmt, def))
439
        {
440
          register_division_in (bb_for_stmt (use_stmt));
441
          count++;
442
        }
443
    }
444
 
445
  /* Do the expensive part only if we can hope to optimize something.  */
446
  threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def)));
447
  if (count >= threshold)
448
    {
449
      for (occ = occ_head; occ; occ = occ->next)
450
        {
451
          compute_merit (occ);
452
          insert_reciprocals (def_bsi, occ, def, NULL, threshold);
453
        }
454
 
455
      FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def)
456
        {
457
          tree use_stmt = USE_STMT (use_p);
458
          if (is_division_by (use_stmt, def))
459
            replace_reciprocal (use_p);
460
        }
461
    }
462
 
463
  for (occ = occ_head; occ; )
464
    occ = free_bb (occ);
465
 
466
  occ_head = NULL;
467
}
468
 
469
 
470
static bool
471
gate_cse_reciprocals (void)
472
{
473
  return optimize && !optimize_size && flag_unsafe_math_optimizations;
474
}
475
 
476
 
477
/* Go through all the floating-point SSA_NAMEs, and call
478
   execute_cse_reciprocals_1 on each of them.  */
479
static void
480
execute_cse_reciprocals (void)
481
{
482
  basic_block bb;
483
  tree arg;
484
 
485
  occ_pool = create_alloc_pool ("dominators for recip",
486
                                sizeof (struct occurrence),
487
                                n_basic_blocks / 3 + 1);
488
 
489
  calculate_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
490
 
491
#ifdef ENABLE_CHECKING
492
  FOR_EACH_BB (bb)
493
    gcc_assert (!bb->aux);
494
#endif
495
 
496
  for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
497
    if (default_def (arg)
498
        && FLOAT_TYPE_P (TREE_TYPE (arg))
499
        && is_gimple_reg (arg))
500
      execute_cse_reciprocals_1 (NULL, default_def (arg));
501
 
502
  FOR_EACH_BB (bb)
503
    {
504
      block_stmt_iterator bsi;
505
      tree phi, def;
506
 
507
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
508
        {
509
          def = PHI_RESULT (phi);
510
          if (FLOAT_TYPE_P (TREE_TYPE (def))
511
              && is_gimple_reg (def))
512
            execute_cse_reciprocals_1 (NULL, def);
513
        }
514
 
515
      for (bsi = bsi_after_labels (bb); !bsi_end_p (bsi); bsi_next (&bsi))
516
        {
517
          tree stmt = bsi_stmt (bsi);
518
          if (TREE_CODE (stmt) == MODIFY_EXPR
519
              && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
520
              && FLOAT_TYPE_P (TREE_TYPE (def))
521
              && TREE_CODE (def) == SSA_NAME)
522
            execute_cse_reciprocals_1 (&bsi, def);
523
        }
524
    }
525
 
526
  free_dominance_info (CDI_DOMINATORS | CDI_POST_DOMINATORS);
527
  free_alloc_pool (occ_pool);
528
}
529
 
530
struct tree_opt_pass pass_cse_reciprocals =
531
{
532
  "recip",                              /* name */
533
  gate_cse_reciprocals,                 /* gate */
534
  execute_cse_reciprocals,              /* execute */
535
  NULL,                                 /* sub */
536
  NULL,                                 /* next */
537
  0,                                     /* static_pass_number */
538
  0,                                     /* tv_id */
539
  PROP_ssa,                             /* properties_required */
540
  0,                                     /* properties_provided */
541
  0,                                     /* properties_destroyed */
542
  0,                                     /* todo_flags_start */
543
  TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
544
    | TODO_verify_stmts,                /* todo_flags_finish */
545
 
546
};

powered by: WebSVN 2.1.0

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