OSDN Git Service

2006-04-18 Paolo Bonzini <bonzini@gnu.org>
[pf3gnuchains/gcc-fork.git] / gcc / tree-ssa-math-opts.c
1 /* 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 unsigned int
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   return 0;
529 }
530
531 struct tree_opt_pass pass_cse_reciprocals =
532 {
533   "recip",                              /* name */
534   gate_cse_reciprocals,                 /* gate */
535   execute_cse_reciprocals,              /* execute */
536   NULL,                                 /* sub */
537   NULL,                                 /* next */
538   0,                                    /* static_pass_number */
539   0,                                    /* tv_id */
540   PROP_ssa,                             /* properties_required */
541   0,                                    /* properties_provided */
542   0,                                    /* properties_destroyed */
543   0,                                    /* todo_flags_start */
544   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
545     | TODO_verify_stmts,                /* todo_flags_finish */
546   0                                     /* letter */
547 };