OSDN Git Service

2005-08-01 Richard Guenther <rguenther@suse.de>
[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 #include "config.h"
41 #include "system.h"
42 #include "coretypes.h"
43 #include "tm.h"
44 #include "flags.h"
45 #include "tree.h"
46 #include "tree-flow.h"
47 #include "real.h"
48 #include "timevar.h"
49 #include "tree-pass.h"
50
51 static bool
52 gate_cse_reciprocals (void)
53 {
54   return optimize && !optimize_size && flag_unsafe_math_optimizations;
55 }
56
57 /* Check if DEF's uses include more than one floating-point division,
58    and if so replace them by multiplications with the reciprocal.  If
59    PHI is true, insert the reciprocal calculation before BSI, otherwise
60    insert it after and move BSI to the new statement.
61
62    Does not check the type of DEF, nor that DEF is a GIMPLE register.
63    This is done in the caller for speed, because otherwise this routine
64    would be called for every definition and phi node.  */
65 static void
66 execute_cse_reciprocals_1 (block_stmt_iterator *bsi, tree def, bool phi)
67 {
68   use_operand_p use_p;
69   imm_use_iterator use_iter;
70   tree t, new_stmt, type;
71   int count = 0;
72   bool ok = !flag_trapping_math;
73
74   /* Find uses.  */
75   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
76     {
77       tree use_stmt = USE_STMT (use_p);
78       if (TREE_CODE (use_stmt) == MODIFY_EXPR
79           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
80           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
81         {
82           ++count;
83           /* Check if this use post-dominates the insertion point.  */
84           if (ok || dominated_by_p (CDI_POST_DOMINATORS, bsi->bb,
85                                     bb_for_stmt (use_stmt)))
86             ok = true;
87         }
88       if (count >= 2 && ok)
89         break;
90     }
91
92   if (count < 2 || !ok)
93     return;
94
95   /* Make a variable with the replacement and substitute it.  */
96   type = TREE_TYPE (def);
97   t = make_rename_temp (type, "reciptmp");
98   new_stmt = build2 (MODIFY_EXPR, void_type_node, t,
99                      fold_build2 (RDIV_EXPR, type, build_real (type, dconst1),
100                                   def));
101
102   if (phi)
103     bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
104   else
105     bsi_insert_after (bsi, new_stmt, BSI_NEW_STMT);
106
107   FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def)
108     {
109       tree use_stmt = USE_STMT (use_p);
110       if (use_stmt != new_stmt
111           && TREE_CODE (use_stmt) == MODIFY_EXPR
112           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
113           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
114         {
115           TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR);
116           SET_USE (use_p, t);
117         }
118     }
119 }
120
121 static void
122 execute_cse_reciprocals (void)
123 {
124   basic_block bb;
125   tree arg;
126
127   if (flag_trapping_math)
128     calculate_dominance_info (CDI_POST_DOMINATORS);
129
130   if (single_succ_p (ENTRY_BLOCK_PTR))
131     for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
132       if (default_def (arg))
133         {
134           block_stmt_iterator bsi;
135           bsi = bsi_start (single_succ (ENTRY_BLOCK_PTR));
136           execute_cse_reciprocals_1 (&bsi, default_def (arg), false);
137         }
138
139   FOR_EACH_BB (bb)
140     {
141       block_stmt_iterator bsi;
142       tree phi, def;
143       for (bsi = bsi_start (bb);
144            !bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR;
145            bsi_next (&bsi))
146         ;
147
148       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
149         {
150           def = PHI_RESULT (phi);
151           if (FLOAT_TYPE_P (TREE_TYPE (def))
152               && is_gimple_reg (def))
153             execute_cse_reciprocals_1 (&bsi, def, true);
154         }
155
156       for (; !bsi_end_p (bsi); bsi_next (&bsi))
157         {
158           tree stmt = bsi_stmt (bsi);
159           if (TREE_CODE (stmt) == MODIFY_EXPR
160               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
161               && FLOAT_TYPE_P (TREE_TYPE (def))
162               && TREE_CODE (def) == SSA_NAME)
163             execute_cse_reciprocals_1 (&bsi, def, false);
164         }
165     }
166
167   if (flag_trapping_math)
168     free_dominance_info (CDI_POST_DOMINATORS);
169 }
170
171 struct tree_opt_pass pass_cse_reciprocals =
172 {
173   "recip",                              /* name */
174   gate_cse_reciprocals,                 /* gate */
175   execute_cse_reciprocals,              /* execute */
176   NULL,                                 /* sub */
177   NULL,                                 /* next */
178   0,                                    /* static_pass_number */
179   0,                                    /* tv_id */
180   PROP_ssa,                             /* properties_required */
181   0,                                    /* properties_provided */
182   0,                                    /* properties_destroyed */
183   0,                                    /* todo_flags_start */
184   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
185     | TODO_verify_stmts,                /* todo_flags_finish */
186   0                                     /* letter */
187 };