annotate gcc/gimple-ssa-strength-reduction.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
16
kono
parents:
diff changeset
1 /* Straight-line strength reduction.
kono
parents:
diff changeset
2 Copyright (C) 2012-2017 Free Software Foundation, Inc.
kono
parents:
diff changeset
3 Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
kono
parents:
diff changeset
4
kono
parents:
diff changeset
5 This file is part of GCC.
kono
parents:
diff changeset
6
kono
parents:
diff changeset
7 GCC is free software; you can redistribute it and/or modify it under
kono
parents:
diff changeset
8 the terms of the GNU General Public License as published by the Free
kono
parents:
diff changeset
9 Software Foundation; either version 3, or (at your option) any later
kono
parents:
diff changeset
10 version.
kono
parents:
diff changeset
11
kono
parents:
diff changeset
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
kono
parents:
diff changeset
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
kono
parents:
diff changeset
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
kono
parents:
diff changeset
15 for more details.
kono
parents:
diff changeset
16
kono
parents:
diff changeset
17 You should have received a copy of the GNU General Public License
kono
parents:
diff changeset
18 along with GCC; see the file COPYING3. If not see
kono
parents:
diff changeset
19 <http://www.gnu.org/licenses/>. */
kono
parents:
diff changeset
20
kono
parents:
diff changeset
21 /* There are many algorithms for performing strength reduction on
kono
parents:
diff changeset
22 loops. This is not one of them. IVOPTS handles strength reduction
kono
parents:
diff changeset
23 of induction variables just fine. This pass is intended to pick
kono
parents:
diff changeset
24 up the crumbs it leaves behind, by considering opportunities for
kono
parents:
diff changeset
25 strength reduction along dominator paths.
kono
parents:
diff changeset
26
kono
parents:
diff changeset
27 Strength reduction addresses explicit multiplies, and certain
kono
parents:
diff changeset
28 multiplies implicit in addressing expressions. It would also be
kono
parents:
diff changeset
29 possible to apply strength reduction to divisions and modulos,
kono
parents:
diff changeset
30 but such opportunities are relatively uncommon.
kono
parents:
diff changeset
31
kono
parents:
diff changeset
32 Strength reduction is also currently restricted to integer operations.
kono
parents:
diff changeset
33 If desired, it could be extended to floating-point operations under
kono
parents:
diff changeset
34 control of something like -funsafe-math-optimizations. */
kono
parents:
diff changeset
35
kono
parents:
diff changeset
36 #include "config.h"
kono
parents:
diff changeset
37 #include "system.h"
kono
parents:
diff changeset
38 #include "coretypes.h"
kono
parents:
diff changeset
39 #include "backend.h"
kono
parents:
diff changeset
40 #include "rtl.h"
kono
parents:
diff changeset
41 #include "tree.h"
kono
parents:
diff changeset
42 #include "gimple.h"
kono
parents:
diff changeset
43 #include "cfghooks.h"
kono
parents:
diff changeset
44 #include "tree-pass.h"
kono
parents:
diff changeset
45 #include "ssa.h"
kono
parents:
diff changeset
46 #include "expmed.h"
kono
parents:
diff changeset
47 #include "gimple-pretty-print.h"
kono
parents:
diff changeset
48 #include "fold-const.h"
kono
parents:
diff changeset
49 #include "gimple-iterator.h"
kono
parents:
diff changeset
50 #include "gimplify-me.h"
kono
parents:
diff changeset
51 #include "stor-layout.h"
kono
parents:
diff changeset
52 #include "cfgloop.h"
kono
parents:
diff changeset
53 #include "tree-cfg.h"
kono
parents:
diff changeset
54 #include "domwalk.h"
kono
parents:
diff changeset
55 #include "params.h"
kono
parents:
diff changeset
56 #include "tree-ssa-address.h"
kono
parents:
diff changeset
57 #include "tree-affine.h"
kono
parents:
diff changeset
58 #include "builtins.h"
kono
parents:
diff changeset
59
kono
parents:
diff changeset
60 /* Information about a strength reduction candidate. Each statement
kono
parents:
diff changeset
61 in the candidate table represents an expression of one of the
kono
parents:
diff changeset
62 following forms (the special case of CAND_REF will be described
kono
parents:
diff changeset
63 later):
kono
parents:
diff changeset
64
kono
parents:
diff changeset
65 (CAND_MULT) S1: X = (B + i) * S
kono
parents:
diff changeset
66 (CAND_ADD) S1: X = B + (i * S)
kono
parents:
diff changeset
67
kono
parents:
diff changeset
68 Here X and B are SSA names, i is an integer constant, and S is
kono
parents:
diff changeset
69 either an SSA name or a constant. We call B the "base," i the
kono
parents:
diff changeset
70 "index", and S the "stride."
kono
parents:
diff changeset
71
kono
parents:
diff changeset
72 Any statement S0 that dominates S1 and is of the form:
kono
parents:
diff changeset
73
kono
parents:
diff changeset
74 (CAND_MULT) S0: Y = (B + i') * S
kono
parents:
diff changeset
75 (CAND_ADD) S0: Y = B + (i' * S)
kono
parents:
diff changeset
76
kono
parents:
diff changeset
77 is called a "basis" for S1. In both cases, S1 may be replaced by
kono
parents:
diff changeset
78
kono
parents:
diff changeset
79 S1': X = Y + (i - i') * S,
kono
parents:
diff changeset
80
kono
parents:
diff changeset
81 where (i - i') * S is folded to the extent possible.
kono
parents:
diff changeset
82
kono
parents:
diff changeset
83 All gimple statements are visited in dominator order, and each
kono
parents:
diff changeset
84 statement that may contribute to one of the forms of S1 above is
kono
parents:
diff changeset
85 given at least one entry in the candidate table. Such statements
kono
parents:
diff changeset
86 include addition, pointer addition, subtraction, multiplication,
kono
parents:
diff changeset
87 negation, copies, and nontrivial type casts. If a statement may
kono
parents:
diff changeset
88 represent more than one expression of the forms of S1 above,
kono
parents:
diff changeset
89 multiple "interpretations" are stored in the table and chained
kono
parents:
diff changeset
90 together. Examples:
kono
parents:
diff changeset
91
kono
parents:
diff changeset
92 * An add of two SSA names may treat either operand as the base.
kono
parents:
diff changeset
93 * A multiply of two SSA names, likewise.
kono
parents:
diff changeset
94 * A copy or cast may be thought of as either a CAND_MULT with
kono
parents:
diff changeset
95 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
kono
parents:
diff changeset
96
kono
parents:
diff changeset
97 Candidate records are allocated from an obstack. They are addressed
kono
parents:
diff changeset
98 both from a hash table keyed on S1, and from a vector of candidate
kono
parents:
diff changeset
99 pointers arranged in predominator order.
kono
parents:
diff changeset
100
kono
parents:
diff changeset
101 Opportunity note
kono
parents:
diff changeset
102 ----------------
kono
parents:
diff changeset
103 Currently we don't recognize:
kono
parents:
diff changeset
104
kono
parents:
diff changeset
105 S0: Y = (S * i') - B
kono
parents:
diff changeset
106 S1: X = (S * i) - B
kono
parents:
diff changeset
107
kono
parents:
diff changeset
108 as a strength reduction opportunity, even though this S1 would
kono
parents:
diff changeset
109 also be replaceable by the S1' above. This can be added if it
kono
parents:
diff changeset
110 comes up in practice.
kono
parents:
diff changeset
111
kono
parents:
diff changeset
112 Strength reduction in addressing
kono
parents:
diff changeset
113 --------------------------------
kono
parents:
diff changeset
114 There is another kind of candidate known as CAND_REF. A CAND_REF
kono
parents:
diff changeset
115 describes a statement containing a memory reference having
kono
parents:
diff changeset
116 complex addressing that might benefit from strength reduction.
kono
parents:
diff changeset
117 Specifically, we are interested in references for which
kono
parents:
diff changeset
118 get_inner_reference returns a base address, offset, and bitpos as
kono
parents:
diff changeset
119 follows:
kono
parents:
diff changeset
120
kono
parents:
diff changeset
121 base: MEM_REF (T1, C1)
kono
parents:
diff changeset
122 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
kono
parents:
diff changeset
123 bitpos: C4 * BITS_PER_UNIT
kono
parents:
diff changeset
124
kono
parents:
diff changeset
125 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
kono
parents:
diff changeset
126 arbitrary integer constants. Note that C2 may be zero, in which
kono
parents:
diff changeset
127 case the offset will be MULT_EXPR (T2, C3).
kono
parents:
diff changeset
128
kono
parents:
diff changeset
129 When this pattern is recognized, the original memory reference
kono
parents:
diff changeset
130 can be replaced with:
kono
parents:
diff changeset
131
kono
parents:
diff changeset
132 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
kono
parents:
diff changeset
133 C1 + (C2 * C3) + C4)
kono
parents:
diff changeset
134
kono
parents:
diff changeset
135 which distributes the multiply to allow constant folding. When
kono
parents:
diff changeset
136 two or more addressing expressions can be represented by MEM_REFs
kono
parents:
diff changeset
137 of this form, differing only in the constants C1, C2, and C4,
kono
parents:
diff changeset
138 making this substitution produces more efficient addressing during
kono
parents:
diff changeset
139 the RTL phases. When there are not at least two expressions with
kono
parents:
diff changeset
140 the same values of T1, T2, and C3, there is nothing to be gained
kono
parents:
diff changeset
141 by the replacement.
kono
parents:
diff changeset
142
kono
parents:
diff changeset
143 Strength reduction of CAND_REFs uses the same infrastructure as
kono
parents:
diff changeset
144 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
kono
parents:
diff changeset
145 field, MULT_EXPR (T2, C3) in the stride (S) field, and
kono
parents:
diff changeset
146 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
kono
parents:
diff changeset
147 is thus another CAND_REF with the same B and S values. When at
kono
parents:
diff changeset
148 least two CAND_REFs are chained together using the basis relation,
kono
parents:
diff changeset
149 each of them is replaced as above, resulting in improved code
kono
parents:
diff changeset
150 generation for addressing.
kono
parents:
diff changeset
151
kono
parents:
diff changeset
152 Conditional candidates
kono
parents:
diff changeset
153 ======================
kono
parents:
diff changeset
154
kono
parents:
diff changeset
155 Conditional candidates are best illustrated with an example.
kono
parents:
diff changeset
156 Consider the code sequence:
kono
parents:
diff changeset
157
kono
parents:
diff changeset
158 (1) x_0 = ...;
kono
parents:
diff changeset
159 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
kono
parents:
diff changeset
160 if (...)
kono
parents:
diff changeset
161 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
kono
parents:
diff changeset
162 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
kono
parents:
diff changeset
163 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
kono
parents:
diff changeset
164 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
kono
parents:
diff changeset
165
kono
parents:
diff changeset
166 Here strength reduction is complicated by the uncertain value of x_2.
kono
parents:
diff changeset
167 A legitimate transformation is:
kono
parents:
diff changeset
168
kono
parents:
diff changeset
169 (1) x_0 = ...;
kono
parents:
diff changeset
170 (2) a_0 = x_0 * 5;
kono
parents:
diff changeset
171 if (...)
kono
parents:
diff changeset
172 {
kono
parents:
diff changeset
173 (3) [x_1 = x_0 + 1;]
kono
parents:
diff changeset
174 (3a) t_1 = a_0 + 5;
kono
parents:
diff changeset
175 }
kono
parents:
diff changeset
176 (4) [x_2 = PHI <x_0, x_1>;]
kono
parents:
diff changeset
177 (4a) t_2 = PHI <a_0, t_1>;
kono
parents:
diff changeset
178 (5) [x_3 = x_2 + 1;]
kono
parents:
diff changeset
179 (6r) a_1 = t_2 + 5;
kono
parents:
diff changeset
180
kono
parents:
diff changeset
181 where the bracketed instructions may go dead.
kono
parents:
diff changeset
182
kono
parents:
diff changeset
183 To recognize this opportunity, we have to observe that statement (6)
kono
parents:
diff changeset
184 has a "hidden basis" (2). The hidden basis is unlike a normal basis
kono
parents:
diff changeset
185 in that the statement and the hidden basis have different base SSA
kono
parents:
diff changeset
186 names (x_2 and x_0, respectively). The relationship is established
kono
parents:
diff changeset
187 when a statement's base name (x_2) is defined by a phi statement (4),
kono
parents:
diff changeset
188 each argument of which (x_0, x_1) has an identical "derived base name."
kono
parents:
diff changeset
189 If the argument is defined by a candidate (as x_1 is by (3)) that is a
kono
parents:
diff changeset
190 CAND_ADD having a stride of 1, the derived base name of the argument is
kono
parents:
diff changeset
191 the base name of the candidate (x_0). Otherwise, the argument itself
kono
parents:
diff changeset
192 is its derived base name (as is the case with argument x_0).
kono
parents:
diff changeset
193
kono
parents:
diff changeset
194 The hidden basis for statement (6) is the nearest dominating candidate
kono
parents:
diff changeset
195 whose base name is the derived base name (x_0) of the feeding phi (4),
kono
parents:
diff changeset
196 and whose stride is identical to that of the statement. We can then
kono
parents:
diff changeset
197 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
kono
parents:
diff changeset
198 allowing the final replacement of (6) by the strength-reduced (6r).
kono
parents:
diff changeset
199
kono
parents:
diff changeset
200 To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
kono
parents:
diff changeset
201 A CAND_PHI is not a candidate for replacement, but is maintained in the
kono
parents:
diff changeset
202 candidate table to ease discovery of hidden bases. Any phi statement
kono
parents:
diff changeset
203 whose arguments share a common derived base name is entered into the
kono
parents:
diff changeset
204 table with the derived base name, an (arbitrary) index of zero, and a
kono
parents:
diff changeset
205 stride of 1. A statement with a hidden basis can then be detected by
kono
parents:
diff changeset
206 simply looking up its feeding phi definition in the candidate table,
kono
parents:
diff changeset
207 extracting the derived base name, and searching for a basis in the
kono
parents:
diff changeset
208 usual manner after substituting the derived base name.
kono
parents:
diff changeset
209
kono
parents:
diff changeset
210 Note that the transformation is only valid when the original phi and
kono
parents:
diff changeset
211 the statements that define the phi's arguments are all at the same
kono
parents:
diff changeset
212 position in the loop hierarchy. */
kono
parents:
diff changeset
213
kono
parents:
diff changeset
214
kono
parents:
diff changeset
215 /* Index into the candidate vector, offset by 1. VECs are zero-based,
kono
parents:
diff changeset
216 while cand_idx's are one-based, with zero indicating null. */
kono
parents:
diff changeset
217 typedef unsigned cand_idx;
kono
parents:
diff changeset
218
kono
parents:
diff changeset
219 /* The kind of candidate. */
kono
parents:
diff changeset
220 enum cand_kind
kono
parents:
diff changeset
221 {
kono
parents:
diff changeset
222 CAND_MULT,
kono
parents:
diff changeset
223 CAND_ADD,
kono
parents:
diff changeset
224 CAND_REF,
kono
parents:
diff changeset
225 CAND_PHI
kono
parents:
diff changeset
226 };
kono
parents:
diff changeset
227
kono
parents:
diff changeset
228 struct slsr_cand_d
kono
parents:
diff changeset
229 {
kono
parents:
diff changeset
230 /* The candidate statement S1. */
kono
parents:
diff changeset
231 gimple *cand_stmt;
kono
parents:
diff changeset
232
kono
parents:
diff changeset
233 /* The base expression B: often an SSA name, but not always. */
kono
parents:
diff changeset
234 tree base_expr;
kono
parents:
diff changeset
235
kono
parents:
diff changeset
236 /* The stride S. */
kono
parents:
diff changeset
237 tree stride;
kono
parents:
diff changeset
238
kono
parents:
diff changeset
239 /* The index constant i. */
kono
parents:
diff changeset
240 widest_int index;
kono
parents:
diff changeset
241
kono
parents:
diff changeset
242 /* The type of the candidate. This is normally the type of base_expr,
kono
parents:
diff changeset
243 but casts may have occurred when combining feeding instructions.
kono
parents:
diff changeset
244 A candidate can only be a basis for candidates of the same final type.
kono
parents:
diff changeset
245 (For CAND_REFs, this is the type to be used for operand 1 of the
kono
parents:
diff changeset
246 replacement MEM_REF.) */
kono
parents:
diff changeset
247 tree cand_type;
kono
parents:
diff changeset
248
kono
parents:
diff changeset
249 /* The type to be used to interpret the stride field when the stride
kono
parents:
diff changeset
250 is not a constant. Normally the same as the type of the recorded
kono
parents:
diff changeset
251 stride, but when the stride has been cast we need to maintain that
kono
parents:
diff changeset
252 knowledge in order to make legal substitutions without losing
kono
parents:
diff changeset
253 precision. When the stride is a constant, this will be sizetype. */
kono
parents:
diff changeset
254 tree stride_type;
kono
parents:
diff changeset
255
kono
parents:
diff changeset
256 /* The kind of candidate (CAND_MULT, etc.). */
kono
parents:
diff changeset
257 enum cand_kind kind;
kono
parents:
diff changeset
258
kono
parents:
diff changeset
259 /* Index of this candidate in the candidate vector. */
kono
parents:
diff changeset
260 cand_idx cand_num;
kono
parents:
diff changeset
261
kono
parents:
diff changeset
262 /* Index of the next candidate record for the same statement.
kono
parents:
diff changeset
263 A statement may be useful in more than one way (e.g., due to
kono
parents:
diff changeset
264 commutativity). So we can have multiple "interpretations"
kono
parents:
diff changeset
265 of a statement. */
kono
parents:
diff changeset
266 cand_idx next_interp;
kono
parents:
diff changeset
267
kono
parents:
diff changeset
268 /* Index of the basis statement S0, if any, in the candidate vector. */
kono
parents:
diff changeset
269 cand_idx basis;
kono
parents:
diff changeset
270
kono
parents:
diff changeset
271 /* First candidate for which this candidate is a basis, if one exists. */
kono
parents:
diff changeset
272 cand_idx dependent;
kono
parents:
diff changeset
273
kono
parents:
diff changeset
274 /* Next candidate having the same basis as this one. */
kono
parents:
diff changeset
275 cand_idx sibling;
kono
parents:
diff changeset
276
kono
parents:
diff changeset
277 /* If this is a conditional candidate, the CAND_PHI candidate
kono
parents:
diff changeset
278 that defines the base SSA name B. */
kono
parents:
diff changeset
279 cand_idx def_phi;
kono
parents:
diff changeset
280
kono
parents:
diff changeset
281 /* Savings that can be expected from eliminating dead code if this
kono
parents:
diff changeset
282 candidate is replaced. */
kono
parents:
diff changeset
283 int dead_savings;
kono
parents:
diff changeset
284
kono
parents:
diff changeset
285 /* For PHI candidates, use a visited flag to keep from processing the
kono
parents:
diff changeset
286 same PHI twice from multiple paths. */
kono
parents:
diff changeset
287 int visited;
kono
parents:
diff changeset
288
kono
parents:
diff changeset
289 /* We sometimes have to cache a phi basis with a phi candidate to
kono
parents:
diff changeset
290 avoid processing it twice. Valid only if visited==1. */
kono
parents:
diff changeset
291 tree cached_basis;
kono
parents:
diff changeset
292 };
kono
parents:
diff changeset
293
kono
parents:
diff changeset
294 typedef struct slsr_cand_d slsr_cand, *slsr_cand_t;
kono
parents:
diff changeset
295 typedef const struct slsr_cand_d *const_slsr_cand_t;
kono
parents:
diff changeset
296
kono
parents:
diff changeset
297 /* Pointers to candidates are chained together as part of a mapping
kono
parents:
diff changeset
298 from base expressions to the candidates that use them. */
kono
parents:
diff changeset
299
kono
parents:
diff changeset
300 struct cand_chain_d
kono
parents:
diff changeset
301 {
kono
parents:
diff changeset
302 /* Base expression for the chain of candidates: often, but not
kono
parents:
diff changeset
303 always, an SSA name. */
kono
parents:
diff changeset
304 tree base_expr;
kono
parents:
diff changeset
305
kono
parents:
diff changeset
306 /* Pointer to a candidate. */
kono
parents:
diff changeset
307 slsr_cand_t cand;
kono
parents:
diff changeset
308
kono
parents:
diff changeset
309 /* Chain pointer. */
kono
parents:
diff changeset
310 struct cand_chain_d *next;
kono
parents:
diff changeset
311
kono
parents:
diff changeset
312 };
kono
parents:
diff changeset
313
kono
parents:
diff changeset
314 typedef struct cand_chain_d cand_chain, *cand_chain_t;
kono
parents:
diff changeset
315 typedef const struct cand_chain_d *const_cand_chain_t;
kono
parents:
diff changeset
316
kono
parents:
diff changeset
317 /* Information about a unique "increment" associated with candidates
kono
parents:
diff changeset
318 having an SSA name for a stride. An increment is the difference
kono
parents:
diff changeset
319 between the index of the candidate and the index of its basis,
kono
parents:
diff changeset
320 i.e., (i - i') as discussed in the module commentary.
kono
parents:
diff changeset
321
kono
parents:
diff changeset
322 When we are not going to generate address arithmetic we treat
kono
parents:
diff changeset
323 increments that differ only in sign as the same, allowing sharing
kono
parents:
diff changeset
324 of the cost of initializers. The absolute value of the increment
kono
parents:
diff changeset
325 is stored in the incr_info. */
kono
parents:
diff changeset
326
kono
parents:
diff changeset
327 struct incr_info_d
kono
parents:
diff changeset
328 {
kono
parents:
diff changeset
329 /* The increment that relates a candidate to its basis. */
kono
parents:
diff changeset
330 widest_int incr;
kono
parents:
diff changeset
331
kono
parents:
diff changeset
332 /* How many times the increment occurs in the candidate tree. */
kono
parents:
diff changeset
333 unsigned count;
kono
parents:
diff changeset
334
kono
parents:
diff changeset
335 /* Cost of replacing candidates using this increment. Negative and
kono
parents:
diff changeset
336 zero costs indicate replacement should be performed. */
kono
parents:
diff changeset
337 int cost;
kono
parents:
diff changeset
338
kono
parents:
diff changeset
339 /* If this increment is profitable but is not -1, 0, or 1, it requires
kono
parents:
diff changeset
340 an initializer T_0 = stride * incr to be found or introduced in the
kono
parents:
diff changeset
341 nearest common dominator of all candidates. This field holds T_0
kono
parents:
diff changeset
342 for subsequent use. */
kono
parents:
diff changeset
343 tree initializer;
kono
parents:
diff changeset
344
kono
parents:
diff changeset
345 /* If the initializer was found to already exist, this is the block
kono
parents:
diff changeset
346 where it was found. */
kono
parents:
diff changeset
347 basic_block init_bb;
kono
parents:
diff changeset
348 };
kono
parents:
diff changeset
349
kono
parents:
diff changeset
350 typedef struct incr_info_d incr_info, *incr_info_t;
kono
parents:
diff changeset
351
kono
parents:
diff changeset
352 /* Candidates are maintained in a vector. If candidate X dominates
kono
parents:
diff changeset
353 candidate Y, then X appears before Y in the vector; but the
kono
parents:
diff changeset
354 converse does not necessarily hold. */
kono
parents:
diff changeset
355 static vec<slsr_cand_t> cand_vec;
kono
parents:
diff changeset
356
kono
parents:
diff changeset
357 enum cost_consts
kono
parents:
diff changeset
358 {
kono
parents:
diff changeset
359 COST_NEUTRAL = 0,
kono
parents:
diff changeset
360 COST_INFINITE = 1000
kono
parents:
diff changeset
361 };
kono
parents:
diff changeset
362
kono
parents:
diff changeset
363 enum stride_status
kono
parents:
diff changeset
364 {
kono
parents:
diff changeset
365 UNKNOWN_STRIDE = 0,
kono
parents:
diff changeset
366 KNOWN_STRIDE = 1
kono
parents:
diff changeset
367 };
kono
parents:
diff changeset
368
kono
parents:
diff changeset
369 enum phi_adjust_status
kono
parents:
diff changeset
370 {
kono
parents:
diff changeset
371 NOT_PHI_ADJUST = 0,
kono
parents:
diff changeset
372 PHI_ADJUST = 1
kono
parents:
diff changeset
373 };
kono
parents:
diff changeset
374
kono
parents:
diff changeset
375 enum count_phis_status
kono
parents:
diff changeset
376 {
kono
parents:
diff changeset
377 DONT_COUNT_PHIS = 0,
kono
parents:
diff changeset
378 COUNT_PHIS = 1
kono
parents:
diff changeset
379 };
kono
parents:
diff changeset
380
kono
parents:
diff changeset
381 /* Constrain how many PHI nodes we will visit for a conditional
kono
parents:
diff changeset
382 candidate (depth and breadth). */
kono
parents:
diff changeset
383 const int MAX_SPREAD = 16;
kono
parents:
diff changeset
384
kono
parents:
diff changeset
385 /* Pointer map embodying a mapping from statements to candidates. */
kono
parents:
diff changeset
386 static hash_map<gimple *, slsr_cand_t> *stmt_cand_map;
kono
parents:
diff changeset
387
kono
parents:
diff changeset
388 /* Obstack for candidates. */
kono
parents:
diff changeset
389 static struct obstack cand_obstack;
kono
parents:
diff changeset
390
kono
parents:
diff changeset
391 /* Obstack for candidate chains. */
kono
parents:
diff changeset
392 static struct obstack chain_obstack;
kono
parents:
diff changeset
393
kono
parents:
diff changeset
394 /* An array INCR_VEC of incr_infos is used during analysis of related
kono
parents:
diff changeset
395 candidates having an SSA name for a stride. INCR_VEC_LEN describes
kono
parents:
diff changeset
396 its current length. MAX_INCR_VEC_LEN is used to avoid costly
kono
parents:
diff changeset
397 pathological cases. */
kono
parents:
diff changeset
398 static incr_info_t incr_vec;
kono
parents:
diff changeset
399 static unsigned incr_vec_len;
kono
parents:
diff changeset
400 const int MAX_INCR_VEC_LEN = 16;
kono
parents:
diff changeset
401
kono
parents:
diff changeset
402 /* For a chain of candidates with unknown stride, indicates whether or not
kono
parents:
diff changeset
403 we must generate pointer arithmetic when replacing statements. */
kono
parents:
diff changeset
404 static bool address_arithmetic_p;
kono
parents:
diff changeset
405
kono
parents:
diff changeset
406 /* Forward function declarations. */
kono
parents:
diff changeset
407 static slsr_cand_t base_cand_from_table (tree);
kono
parents:
diff changeset
408 static tree introduce_cast_before_cand (slsr_cand_t, tree, tree);
kono
parents:
diff changeset
409 static bool legal_cast_p_1 (tree, tree);
kono
parents:
diff changeset
410
kono
parents:
diff changeset
411 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
kono
parents:
diff changeset
412
kono
parents:
diff changeset
413 static slsr_cand_t
kono
parents:
diff changeset
414 lookup_cand (cand_idx idx)
kono
parents:
diff changeset
415 {
kono
parents:
diff changeset
416 return cand_vec[idx - 1];
kono
parents:
diff changeset
417 }
kono
parents:
diff changeset
418
kono
parents:
diff changeset
419 /* Helper for hashing a candidate chain header. */
kono
parents:
diff changeset
420
kono
parents:
diff changeset
421 struct cand_chain_hasher : nofree_ptr_hash <cand_chain>
kono
parents:
diff changeset
422 {
kono
parents:
diff changeset
423 static inline hashval_t hash (const cand_chain *);
kono
parents:
diff changeset
424 static inline bool equal (const cand_chain *, const cand_chain *);
kono
parents:
diff changeset
425 };
kono
parents:
diff changeset
426
kono
parents:
diff changeset
427 inline hashval_t
kono
parents:
diff changeset
428 cand_chain_hasher::hash (const cand_chain *p)
kono
parents:
diff changeset
429 {
kono
parents:
diff changeset
430 tree base_expr = p->base_expr;
kono
parents:
diff changeset
431 return iterative_hash_expr (base_expr, 0);
kono
parents:
diff changeset
432 }
kono
parents:
diff changeset
433
kono
parents:
diff changeset
434 inline bool
kono
parents:
diff changeset
435 cand_chain_hasher::equal (const cand_chain *chain1, const cand_chain *chain2)
kono
parents:
diff changeset
436 {
kono
parents:
diff changeset
437 return operand_equal_p (chain1->base_expr, chain2->base_expr, 0);
kono
parents:
diff changeset
438 }
kono
parents:
diff changeset
439
kono
parents:
diff changeset
440 /* Hash table embodying a mapping from base exprs to chains of candidates. */
kono
parents:
diff changeset
441 static hash_table<cand_chain_hasher> *base_cand_map;
kono
parents:
diff changeset
442
kono
parents:
diff changeset
443 /* Pointer map used by tree_to_aff_combination_expand. */
kono
parents:
diff changeset
444 static hash_map<tree, name_expansion *> *name_expansions;
kono
parents:
diff changeset
445 /* Pointer map embodying a mapping from bases to alternative bases. */
kono
parents:
diff changeset
446 static hash_map<tree, tree> *alt_base_map;
kono
parents:
diff changeset
447
kono
parents:
diff changeset
448 /* Given BASE, use the tree affine combiniation facilities to
kono
parents:
diff changeset
449 find the underlying tree expression for BASE, with any
kono
parents:
diff changeset
450 immediate offset excluded.
kono
parents:
diff changeset
451
kono
parents:
diff changeset
452 N.B. we should eliminate this backtracking with better forward
kono
parents:
diff changeset
453 analysis in a future release. */
kono
parents:
diff changeset
454
kono
parents:
diff changeset
455 static tree
kono
parents:
diff changeset
456 get_alternative_base (tree base)
kono
parents:
diff changeset
457 {
kono
parents:
diff changeset
458 tree *result = alt_base_map->get (base);
kono
parents:
diff changeset
459
kono
parents:
diff changeset
460 if (result == NULL)
kono
parents:
diff changeset
461 {
kono
parents:
diff changeset
462 tree expr;
kono
parents:
diff changeset
463 aff_tree aff;
kono
parents:
diff changeset
464
kono
parents:
diff changeset
465 tree_to_aff_combination_expand (base, TREE_TYPE (base),
kono
parents:
diff changeset
466 &aff, &name_expansions);
kono
parents:
diff changeset
467 aff.offset = 0;
kono
parents:
diff changeset
468 expr = aff_combination_to_tree (&aff);
kono
parents:
diff changeset
469
kono
parents:
diff changeset
470 gcc_assert (!alt_base_map->put (base, base == expr ? NULL : expr));
kono
parents:
diff changeset
471
kono
parents:
diff changeset
472 return expr == base ? NULL : expr;
kono
parents:
diff changeset
473 }
kono
parents:
diff changeset
474
kono
parents:
diff changeset
475 return *result;
kono
parents:
diff changeset
476 }
kono
parents:
diff changeset
477
kono
parents:
diff changeset
478 /* Look in the candidate table for a CAND_PHI that defines BASE and
kono
parents:
diff changeset
479 return it if found; otherwise return NULL. */
kono
parents:
diff changeset
480
kono
parents:
diff changeset
481 static cand_idx
kono
parents:
diff changeset
482 find_phi_def (tree base)
kono
parents:
diff changeset
483 {
kono
parents:
diff changeset
484 slsr_cand_t c;
kono
parents:
diff changeset
485
kono
parents:
diff changeset
486 if (TREE_CODE (base) != SSA_NAME)
kono
parents:
diff changeset
487 return 0;
kono
parents:
diff changeset
488
kono
parents:
diff changeset
489 c = base_cand_from_table (base);
kono
parents:
diff changeset
490
kono
parents:
diff changeset
491 if (!c || c->kind != CAND_PHI
kono
parents:
diff changeset
492 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (c->cand_stmt)))
kono
parents:
diff changeset
493 return 0;
kono
parents:
diff changeset
494
kono
parents:
diff changeset
495 return c->cand_num;
kono
parents:
diff changeset
496 }
kono
parents:
diff changeset
497
kono
parents:
diff changeset
498 /* Determine whether all uses of NAME are directly or indirectly
kono
parents:
diff changeset
499 used by STMT. That is, we want to know whether if STMT goes
kono
parents:
diff changeset
500 dead, the definition of NAME also goes dead. */
kono
parents:
diff changeset
501 static bool
kono
parents:
diff changeset
502 uses_consumed_by_stmt (tree name, gimple *stmt, unsigned recurse = 0)
kono
parents:
diff changeset
503 {
kono
parents:
diff changeset
504 gimple *use_stmt;
kono
parents:
diff changeset
505 imm_use_iterator iter;
kono
parents:
diff changeset
506 bool retval = true;
kono
parents:
diff changeset
507
kono
parents:
diff changeset
508 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
kono
parents:
diff changeset
509 {
kono
parents:
diff changeset
510 if (use_stmt == stmt || is_gimple_debug (use_stmt))
kono
parents:
diff changeset
511 continue;
kono
parents:
diff changeset
512
kono
parents:
diff changeset
513 if (!is_gimple_assign (use_stmt)
kono
parents:
diff changeset
514 || !gimple_get_lhs (use_stmt)
kono
parents:
diff changeset
515 || !is_gimple_reg (gimple_get_lhs (use_stmt))
kono
parents:
diff changeset
516 || recurse >= 10
kono
parents:
diff changeset
517 || !uses_consumed_by_stmt (gimple_get_lhs (use_stmt), stmt,
kono
parents:
diff changeset
518 recurse + 1))
kono
parents:
diff changeset
519 {
kono
parents:
diff changeset
520 retval = false;
kono
parents:
diff changeset
521 BREAK_FROM_IMM_USE_STMT (iter);
kono
parents:
diff changeset
522 }
kono
parents:
diff changeset
523 }
kono
parents:
diff changeset
524
kono
parents:
diff changeset
525 return retval;
kono
parents:
diff changeset
526 }
kono
parents:
diff changeset
527
kono
parents:
diff changeset
528 /* Helper routine for find_basis_for_candidate. May be called twice:
kono
parents:
diff changeset
529 once for the candidate's base expr, and optionally again either for
kono
parents:
diff changeset
530 the candidate's phi definition or for a CAND_REF's alternative base
kono
parents:
diff changeset
531 expression. */
kono
parents:
diff changeset
532
kono
parents:
diff changeset
533 static slsr_cand_t
kono
parents:
diff changeset
534 find_basis_for_base_expr (slsr_cand_t c, tree base_expr)
kono
parents:
diff changeset
535 {
kono
parents:
diff changeset
536 cand_chain mapping_key;
kono
parents:
diff changeset
537 cand_chain_t chain;
kono
parents:
diff changeset
538 slsr_cand_t basis = NULL;
kono
parents:
diff changeset
539
kono
parents:
diff changeset
540 // Limit potential of N^2 behavior for long candidate chains.
kono
parents:
diff changeset
541 int iters = 0;
kono
parents:
diff changeset
542 int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN);
kono
parents:
diff changeset
543
kono
parents:
diff changeset
544 mapping_key.base_expr = base_expr;
kono
parents:
diff changeset
545 chain = base_cand_map->find (&mapping_key);
kono
parents:
diff changeset
546
kono
parents:
diff changeset
547 for (; chain && iters < max_iters; chain = chain->next, ++iters)
kono
parents:
diff changeset
548 {
kono
parents:
diff changeset
549 slsr_cand_t one_basis = chain->cand;
kono
parents:
diff changeset
550
kono
parents:
diff changeset
551 if (one_basis->kind != c->kind
kono
parents:
diff changeset
552 || one_basis->cand_stmt == c->cand_stmt
kono
parents:
diff changeset
553 || !operand_equal_p (one_basis->stride, c->stride, 0)
kono
parents:
diff changeset
554 || !types_compatible_p (one_basis->cand_type, c->cand_type)
kono
parents:
diff changeset
555 || !types_compatible_p (one_basis->stride_type, c->stride_type)
kono
parents:
diff changeset
556 || !dominated_by_p (CDI_DOMINATORS,
kono
parents:
diff changeset
557 gimple_bb (c->cand_stmt),
kono
parents:
diff changeset
558 gimple_bb (one_basis->cand_stmt)))
kono
parents:
diff changeset
559 continue;
kono
parents:
diff changeset
560
kono
parents:
diff changeset
561 tree lhs = gimple_assign_lhs (one_basis->cand_stmt);
kono
parents:
diff changeset
562 if (lhs && TREE_CODE (lhs) == SSA_NAME
kono
parents:
diff changeset
563 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
kono
parents:
diff changeset
564 continue;
kono
parents:
diff changeset
565
kono
parents:
diff changeset
566 if (!basis || basis->cand_num < one_basis->cand_num)
kono
parents:
diff changeset
567 basis = one_basis;
kono
parents:
diff changeset
568 }
kono
parents:
diff changeset
569
kono
parents:
diff changeset
570 return basis;
kono
parents:
diff changeset
571 }
kono
parents:
diff changeset
572
kono
parents:
diff changeset
573 /* Use the base expr from candidate C to look for possible candidates
kono
parents:
diff changeset
574 that can serve as a basis for C. Each potential basis must also
kono
parents:
diff changeset
575 appear in a block that dominates the candidate statement and have
kono
parents:
diff changeset
576 the same stride and type. If more than one possible basis exists,
kono
parents:
diff changeset
577 the one with highest index in the vector is chosen; this will be
kono
parents:
diff changeset
578 the most immediately dominating basis. */
kono
parents:
diff changeset
579
kono
parents:
diff changeset
580 static int
kono
parents:
diff changeset
581 find_basis_for_candidate (slsr_cand_t c)
kono
parents:
diff changeset
582 {
kono
parents:
diff changeset
583 slsr_cand_t basis = find_basis_for_base_expr (c, c->base_expr);
kono
parents:
diff changeset
584
kono
parents:
diff changeset
585 /* If a candidate doesn't have a basis using its base expression,
kono
parents:
diff changeset
586 it may have a basis hidden by one or more intervening phis. */
kono
parents:
diff changeset
587 if (!basis && c->def_phi)
kono
parents:
diff changeset
588 {
kono
parents:
diff changeset
589 basic_block basis_bb, phi_bb;
kono
parents:
diff changeset
590 slsr_cand_t phi_cand = lookup_cand (c->def_phi);
kono
parents:
diff changeset
591 basis = find_basis_for_base_expr (c, phi_cand->base_expr);
kono
parents:
diff changeset
592
kono
parents:
diff changeset
593 if (basis)
kono
parents:
diff changeset
594 {
kono
parents:
diff changeset
595 /* A hidden basis must dominate the phi-definition of the
kono
parents:
diff changeset
596 candidate's base name. */
kono
parents:
diff changeset
597 phi_bb = gimple_bb (phi_cand->cand_stmt);
kono
parents:
diff changeset
598 basis_bb = gimple_bb (basis->cand_stmt);
kono
parents:
diff changeset
599
kono
parents:
diff changeset
600 if (phi_bb == basis_bb
kono
parents:
diff changeset
601 || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
kono
parents:
diff changeset
602 {
kono
parents:
diff changeset
603 basis = NULL;
kono
parents:
diff changeset
604 c->basis = 0;
kono
parents:
diff changeset
605 }
kono
parents:
diff changeset
606
kono
parents:
diff changeset
607 /* If we found a hidden basis, estimate additional dead-code
kono
parents:
diff changeset
608 savings if the phi and its feeding statements can be removed. */
kono
parents:
diff changeset
609 tree feeding_var = gimple_phi_result (phi_cand->cand_stmt);
kono
parents:
diff changeset
610 if (basis && uses_consumed_by_stmt (feeding_var, c->cand_stmt))
kono
parents:
diff changeset
611 c->dead_savings += phi_cand->dead_savings;
kono
parents:
diff changeset
612 }
kono
parents:
diff changeset
613 }
kono
parents:
diff changeset
614
kono
parents:
diff changeset
615 if (flag_expensive_optimizations && !basis && c->kind == CAND_REF)
kono
parents:
diff changeset
616 {
kono
parents:
diff changeset
617 tree alt_base_expr = get_alternative_base (c->base_expr);
kono
parents:
diff changeset
618 if (alt_base_expr)
kono
parents:
diff changeset
619 basis = find_basis_for_base_expr (c, alt_base_expr);
kono
parents:
diff changeset
620 }
kono
parents:
diff changeset
621
kono
parents:
diff changeset
622 if (basis)
kono
parents:
diff changeset
623 {
kono
parents:
diff changeset
624 c->sibling = basis->dependent;
kono
parents:
diff changeset
625 basis->dependent = c->cand_num;
kono
parents:
diff changeset
626 return basis->cand_num;
kono
parents:
diff changeset
627 }
kono
parents:
diff changeset
628
kono
parents:
diff changeset
629 return 0;
kono
parents:
diff changeset
630 }
kono
parents:
diff changeset
631
kono
parents:
diff changeset
632 /* Record a mapping from BASE to C, indicating that C may potentially serve
kono
parents:
diff changeset
633 as a basis using that base expression. BASE may be the same as
kono
parents:
diff changeset
634 C->BASE_EXPR; alternatively BASE can be a different tree that share the
kono
parents:
diff changeset
635 underlining expression of C->BASE_EXPR. */
kono
parents:
diff changeset
636
kono
parents:
diff changeset
637 static void
kono
parents:
diff changeset
638 record_potential_basis (slsr_cand_t c, tree base)
kono
parents:
diff changeset
639 {
kono
parents:
diff changeset
640 cand_chain_t node;
kono
parents:
diff changeset
641 cand_chain **slot;
kono
parents:
diff changeset
642
kono
parents:
diff changeset
643 gcc_assert (base);
kono
parents:
diff changeset
644
kono
parents:
diff changeset
645 node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain));
kono
parents:
diff changeset
646 node->base_expr = base;
kono
parents:
diff changeset
647 node->cand = c;
kono
parents:
diff changeset
648 node->next = NULL;
kono
parents:
diff changeset
649 slot = base_cand_map->find_slot (node, INSERT);
kono
parents:
diff changeset
650
kono
parents:
diff changeset
651 if (*slot)
kono
parents:
diff changeset
652 {
kono
parents:
diff changeset
653 cand_chain_t head = (cand_chain_t) (*slot);
kono
parents:
diff changeset
654 node->next = head->next;
kono
parents:
diff changeset
655 head->next = node;
kono
parents:
diff changeset
656 }
kono
parents:
diff changeset
657 else
kono
parents:
diff changeset
658 *slot = node;
kono
parents:
diff changeset
659 }
kono
parents:
diff changeset
660
kono
parents:
diff changeset
661 /* Allocate storage for a new candidate and initialize its fields.
kono
parents:
diff changeset
662 Attempt to find a basis for the candidate.
kono
parents:
diff changeset
663
kono
parents:
diff changeset
664 For CAND_REF, an alternative base may also be recorded and used
kono
parents:
diff changeset
665 to find a basis. This helps cases where the expression hidden
kono
parents:
diff changeset
666 behind BASE (which is usually an SSA_NAME) has immediate offset,
kono
parents:
diff changeset
667 e.g.
kono
parents:
diff changeset
668
kono
parents:
diff changeset
669 a2[i][j] = 1;
kono
parents:
diff changeset
670 a2[i + 20][j] = 2; */
kono
parents:
diff changeset
671
kono
parents:
diff changeset
672 static slsr_cand_t
kono
parents:
diff changeset
673 alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base,
kono
parents:
diff changeset
674 const widest_int &index, tree stride, tree ctype,
kono
parents:
diff changeset
675 tree stype, unsigned savings)
kono
parents:
diff changeset
676 {
kono
parents:
diff changeset
677 slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack,
kono
parents:
diff changeset
678 sizeof (slsr_cand));
kono
parents:
diff changeset
679 c->cand_stmt = gs;
kono
parents:
diff changeset
680 c->base_expr = base;
kono
parents:
diff changeset
681 c->stride = stride;
kono
parents:
diff changeset
682 c->index = index;
kono
parents:
diff changeset
683 c->cand_type = ctype;
kono
parents:
diff changeset
684 c->stride_type = stype;
kono
parents:
diff changeset
685 c->kind = kind;
kono
parents:
diff changeset
686 c->cand_num = cand_vec.length () + 1;
kono
parents:
diff changeset
687 c->next_interp = 0;
kono
parents:
diff changeset
688 c->dependent = 0;
kono
parents:
diff changeset
689 c->sibling = 0;
kono
parents:
diff changeset
690 c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;
kono
parents:
diff changeset
691 c->dead_savings = savings;
kono
parents:
diff changeset
692 c->visited = 0;
kono
parents:
diff changeset
693 c->cached_basis = NULL_TREE;
kono
parents:
diff changeset
694
kono
parents:
diff changeset
695 cand_vec.safe_push (c);
kono
parents:
diff changeset
696
kono
parents:
diff changeset
697 if (kind == CAND_PHI)
kono
parents:
diff changeset
698 c->basis = 0;
kono
parents:
diff changeset
699 else
kono
parents:
diff changeset
700 c->basis = find_basis_for_candidate (c);
kono
parents:
diff changeset
701
kono
parents:
diff changeset
702 record_potential_basis (c, base);
kono
parents:
diff changeset
703 if (flag_expensive_optimizations && kind == CAND_REF)
kono
parents:
diff changeset
704 {
kono
parents:
diff changeset
705 tree alt_base = get_alternative_base (base);
kono
parents:
diff changeset
706 if (alt_base)
kono
parents:
diff changeset
707 record_potential_basis (c, alt_base);
kono
parents:
diff changeset
708 }
kono
parents:
diff changeset
709
kono
parents:
diff changeset
710 return c;
kono
parents:
diff changeset
711 }
kono
parents:
diff changeset
712
kono
parents:
diff changeset
713 /* Determine the target cost of statement GS when compiling according
kono
parents:
diff changeset
714 to SPEED. */
kono
parents:
diff changeset
715
kono
parents:
diff changeset
716 static int
kono
parents:
diff changeset
717 stmt_cost (gimple *gs, bool speed)
kono
parents:
diff changeset
718 {
kono
parents:
diff changeset
719 tree lhs, rhs1, rhs2;
kono
parents:
diff changeset
720 machine_mode lhs_mode;
kono
parents:
diff changeset
721
kono
parents:
diff changeset
722 gcc_assert (is_gimple_assign (gs));
kono
parents:
diff changeset
723 lhs = gimple_assign_lhs (gs);
kono
parents:
diff changeset
724 rhs1 = gimple_assign_rhs1 (gs);
kono
parents:
diff changeset
725 lhs_mode = TYPE_MODE (TREE_TYPE (lhs));
kono
parents:
diff changeset
726
kono
parents:
diff changeset
727 switch (gimple_assign_rhs_code (gs))
kono
parents:
diff changeset
728 {
kono
parents:
diff changeset
729 case MULT_EXPR:
kono
parents:
diff changeset
730 rhs2 = gimple_assign_rhs2 (gs);
kono
parents:
diff changeset
731
kono
parents:
diff changeset
732 if (tree_fits_shwi_p (rhs2))
kono
parents:
diff changeset
733 return mult_by_coeff_cost (tree_to_shwi (rhs2), lhs_mode, speed);
kono
parents:
diff changeset
734
kono
parents:
diff changeset
735 gcc_assert (TREE_CODE (rhs1) != INTEGER_CST);
kono
parents:
diff changeset
736 return mul_cost (speed, lhs_mode);
kono
parents:
diff changeset
737
kono
parents:
diff changeset
738 case PLUS_EXPR:
kono
parents:
diff changeset
739 case POINTER_PLUS_EXPR:
kono
parents:
diff changeset
740 case MINUS_EXPR:
kono
parents:
diff changeset
741 return add_cost (speed, lhs_mode);
kono
parents:
diff changeset
742
kono
parents:
diff changeset
743 case NEGATE_EXPR:
kono
parents:
diff changeset
744 return neg_cost (speed, lhs_mode);
kono
parents:
diff changeset
745
kono
parents:
diff changeset
746 CASE_CONVERT:
kono
parents:
diff changeset
747 return convert_cost (lhs_mode, TYPE_MODE (TREE_TYPE (rhs1)), speed);
kono
parents:
diff changeset
748
kono
parents:
diff changeset
749 /* Note that we don't assign costs to copies that in most cases
kono
parents:
diff changeset
750 will go away. */
kono
parents:
diff changeset
751 case SSA_NAME:
kono
parents:
diff changeset
752 return 0;
kono
parents:
diff changeset
753
kono
parents:
diff changeset
754 default:
kono
parents:
diff changeset
755 ;
kono
parents:
diff changeset
756 }
kono
parents:
diff changeset
757
kono
parents:
diff changeset
758 gcc_unreachable ();
kono
parents:
diff changeset
759 return 0;
kono
parents:
diff changeset
760 }
kono
parents:
diff changeset
761
kono
parents:
diff changeset
762 /* Look up the defining statement for BASE_IN and return a pointer
kono
parents:
diff changeset
763 to its candidate in the candidate table, if any; otherwise NULL.
kono
parents:
diff changeset
764 Only CAND_ADD and CAND_MULT candidates are returned. */
kono
parents:
diff changeset
765
kono
parents:
diff changeset
766 static slsr_cand_t
kono
parents:
diff changeset
767 base_cand_from_table (tree base_in)
kono
parents:
diff changeset
768 {
kono
parents:
diff changeset
769 slsr_cand_t *result;
kono
parents:
diff changeset
770
kono
parents:
diff changeset
771 gimple *def = SSA_NAME_DEF_STMT (base_in);
kono
parents:
diff changeset
772 if (!def)
kono
parents:
diff changeset
773 return (slsr_cand_t) NULL;
kono
parents:
diff changeset
774
kono
parents:
diff changeset
775 result = stmt_cand_map->get (def);
kono
parents:
diff changeset
776
kono
parents:
diff changeset
777 if (result && (*result)->kind != CAND_REF)
kono
parents:
diff changeset
778 return *result;
kono
parents:
diff changeset
779
kono
parents:
diff changeset
780 return (slsr_cand_t) NULL;
kono
parents:
diff changeset
781 }
kono
parents:
diff changeset
782
kono
parents:
diff changeset
783 /* Add an entry to the statement-to-candidate mapping. */
kono
parents:
diff changeset
784
kono
parents:
diff changeset
785 static void
kono
parents:
diff changeset
786 add_cand_for_stmt (gimple *gs, slsr_cand_t c)
kono
parents:
diff changeset
787 {
kono
parents:
diff changeset
788 gcc_assert (!stmt_cand_map->put (gs, c));
kono
parents:
diff changeset
789 }
kono
parents:
diff changeset
790
kono
parents:
diff changeset
791 /* Given PHI which contains a phi statement, determine whether it
kono
parents:
diff changeset
792 satisfies all the requirements of a phi candidate. If so, create
kono
parents:
diff changeset
793 a candidate. Note that a CAND_PHI never has a basis itself, but
kono
parents:
diff changeset
794 is used to help find a basis for subsequent candidates. */
kono
parents:
diff changeset
795
kono
parents:
diff changeset
796 static void
kono
parents:
diff changeset
797 slsr_process_phi (gphi *phi, bool speed)
kono
parents:
diff changeset
798 {
kono
parents:
diff changeset
799 unsigned i;
kono
parents:
diff changeset
800 tree arg0_base = NULL_TREE, base_type;
kono
parents:
diff changeset
801 slsr_cand_t c;
kono
parents:
diff changeset
802 struct loop *cand_loop = gimple_bb (phi)->loop_father;
kono
parents:
diff changeset
803 unsigned savings = 0;
kono
parents:
diff changeset
804
kono
parents:
diff changeset
805 /* A CAND_PHI requires each of its arguments to have the same
kono
parents:
diff changeset
806 derived base name. (See the module header commentary for a
kono
parents:
diff changeset
807 definition of derived base names.) Furthermore, all feeding
kono
parents:
diff changeset
808 definitions must be in the same position in the loop hierarchy
kono
parents:
diff changeset
809 as PHI. */
kono
parents:
diff changeset
810
kono
parents:
diff changeset
811 for (i = 0; i < gimple_phi_num_args (phi); i++)
kono
parents:
diff changeset
812 {
kono
parents:
diff changeset
813 slsr_cand_t arg_cand;
kono
parents:
diff changeset
814 tree arg = gimple_phi_arg_def (phi, i);
kono
parents:
diff changeset
815 tree derived_base_name = NULL_TREE;
kono
parents:
diff changeset
816 gimple *arg_stmt = NULL;
kono
parents:
diff changeset
817 basic_block arg_bb = NULL;
kono
parents:
diff changeset
818
kono
parents:
diff changeset
819 if (TREE_CODE (arg) != SSA_NAME)
kono
parents:
diff changeset
820 return;
kono
parents:
diff changeset
821
kono
parents:
diff changeset
822 arg_cand = base_cand_from_table (arg);
kono
parents:
diff changeset
823
kono
parents:
diff changeset
824 if (arg_cand)
kono
parents:
diff changeset
825 {
kono
parents:
diff changeset
826 while (arg_cand->kind != CAND_ADD && arg_cand->kind != CAND_PHI)
kono
parents:
diff changeset
827 {
kono
parents:
diff changeset
828 if (!arg_cand->next_interp)
kono
parents:
diff changeset
829 return;
kono
parents:
diff changeset
830
kono
parents:
diff changeset
831 arg_cand = lookup_cand (arg_cand->next_interp);
kono
parents:
diff changeset
832 }
kono
parents:
diff changeset
833
kono
parents:
diff changeset
834 if (!integer_onep (arg_cand->stride))
kono
parents:
diff changeset
835 return;
kono
parents:
diff changeset
836
kono
parents:
diff changeset
837 derived_base_name = arg_cand->base_expr;
kono
parents:
diff changeset
838 arg_stmt = arg_cand->cand_stmt;
kono
parents:
diff changeset
839 arg_bb = gimple_bb (arg_stmt);
kono
parents:
diff changeset
840
kono
parents:
diff changeset
841 /* Gather potential dead code savings if the phi statement
kono
parents:
diff changeset
842 can be removed later on. */
kono
parents:
diff changeset
843 if (uses_consumed_by_stmt (arg, phi))
kono
parents:
diff changeset
844 {
kono
parents:
diff changeset
845 if (gimple_code (arg_stmt) == GIMPLE_PHI)
kono
parents:
diff changeset
846 savings += arg_cand->dead_savings;
kono
parents:
diff changeset
847 else
kono
parents:
diff changeset
848 savings += stmt_cost (arg_stmt, speed);
kono
parents:
diff changeset
849 }
kono
parents:
diff changeset
850 }
kono
parents:
diff changeset
851 else if (SSA_NAME_IS_DEFAULT_DEF (arg))
kono
parents:
diff changeset
852 {
kono
parents:
diff changeset
853 derived_base_name = arg;
kono
parents:
diff changeset
854 arg_bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
kono
parents:
diff changeset
855 }
kono
parents:
diff changeset
856
kono
parents:
diff changeset
857 if (!arg_bb || arg_bb->loop_father != cand_loop)
kono
parents:
diff changeset
858 return;
kono
parents:
diff changeset
859
kono
parents:
diff changeset
860 if (i == 0)
kono
parents:
diff changeset
861 arg0_base = derived_base_name;
kono
parents:
diff changeset
862 else if (!operand_equal_p (derived_base_name, arg0_base, 0))
kono
parents:
diff changeset
863 return;
kono
parents:
diff changeset
864 }
kono
parents:
diff changeset
865
kono
parents:
diff changeset
866 /* Create the candidate. "alloc_cand_and_find_basis" is named
kono
parents:
diff changeset
867 misleadingly for this case, as no basis will be sought for a
kono
parents:
diff changeset
868 CAND_PHI. */
kono
parents:
diff changeset
869 base_type = TREE_TYPE (arg0_base);
kono
parents:
diff changeset
870
kono
parents:
diff changeset
871 c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base,
kono
parents:
diff changeset
872 0, integer_one_node, base_type,
kono
parents:
diff changeset
873 sizetype, savings);
kono
parents:
diff changeset
874
kono
parents:
diff changeset
875 /* Add the candidate to the statement-candidate mapping. */
kono
parents:
diff changeset
876 add_cand_for_stmt (phi, c);
kono
parents:
diff changeset
877 }
kono
parents:
diff changeset
878
kono
parents:
diff changeset
879 /* Given PBASE which is a pointer to tree, look up the defining
kono
parents:
diff changeset
880 statement for it and check whether the candidate is in the
kono
parents:
diff changeset
881 form of:
kono
parents:
diff changeset
882
kono
parents:
diff changeset
883 X = B + (1 * S), S is integer constant
kono
parents:
diff changeset
884 X = B + (i * S), S is integer one
kono
parents:
diff changeset
885
kono
parents:
diff changeset
886 If so, set PBASE to the candidate's base_expr and return double
kono
parents:
diff changeset
887 int (i * S).
kono
parents:
diff changeset
888 Otherwise, just return double int zero. */
kono
parents:
diff changeset
889
kono
parents:
diff changeset
890 static widest_int
kono
parents:
diff changeset
891 backtrace_base_for_ref (tree *pbase)
kono
parents:
diff changeset
892 {
kono
parents:
diff changeset
893 tree base_in = *pbase;
kono
parents:
diff changeset
894 slsr_cand_t base_cand;
kono
parents:
diff changeset
895
kono
parents:
diff changeset
896 STRIP_NOPS (base_in);
kono
parents:
diff changeset
897
kono
parents:
diff changeset
898 /* Strip off widening conversion(s) to handle cases where
kono
parents:
diff changeset
899 e.g. 'B' is widened from an 'int' in order to calculate
kono
parents:
diff changeset
900 a 64-bit address. */
kono
parents:
diff changeset
901 if (CONVERT_EXPR_P (base_in)
kono
parents:
diff changeset
902 && legal_cast_p_1 (TREE_TYPE (base_in),
kono
parents:
diff changeset
903 TREE_TYPE (TREE_OPERAND (base_in, 0))))
kono
parents:
diff changeset
904 base_in = get_unwidened (base_in, NULL_TREE);
kono
parents:
diff changeset
905
kono
parents:
diff changeset
906 if (TREE_CODE (base_in) != SSA_NAME)
kono
parents:
diff changeset
907 return 0;
kono
parents:
diff changeset
908
kono
parents:
diff changeset
909 base_cand = base_cand_from_table (base_in);
kono
parents:
diff changeset
910
kono
parents:
diff changeset
911 while (base_cand && base_cand->kind != CAND_PHI)
kono
parents:
diff changeset
912 {
kono
parents:
diff changeset
913 if (base_cand->kind == CAND_ADD
kono
parents:
diff changeset
914 && base_cand->index == 1
kono
parents:
diff changeset
915 && TREE_CODE (base_cand->stride) == INTEGER_CST)
kono
parents:
diff changeset
916 {
kono
parents:
diff changeset
917 /* X = B + (1 * S), S is integer constant. */
kono
parents:
diff changeset
918 *pbase = base_cand->base_expr;
kono
parents:
diff changeset
919 return wi::to_widest (base_cand->stride);
kono
parents:
diff changeset
920 }
kono
parents:
diff changeset
921 else if (base_cand->kind == CAND_ADD
kono
parents:
diff changeset
922 && TREE_CODE (base_cand->stride) == INTEGER_CST
kono
parents:
diff changeset
923 && integer_onep (base_cand->stride))
kono
parents:
diff changeset
924 {
kono
parents:
diff changeset
925 /* X = B + (i * S), S is integer one. */
kono
parents:
diff changeset
926 *pbase = base_cand->base_expr;
kono
parents:
diff changeset
927 return base_cand->index;
kono
parents:
diff changeset
928 }
kono
parents:
diff changeset
929
kono
parents:
diff changeset
930 if (base_cand->next_interp)
kono
parents:
diff changeset
931 base_cand = lookup_cand (base_cand->next_interp);
kono
parents:
diff changeset
932 else
kono
parents:
diff changeset
933 base_cand = NULL;
kono
parents:
diff changeset
934 }
kono
parents:
diff changeset
935
kono
parents:
diff changeset
936 return 0;
kono
parents:
diff changeset
937 }
kono
parents:
diff changeset
938
kono
parents:
diff changeset
939 /* Look for the following pattern:
kono
parents:
diff changeset
940
kono
parents:
diff changeset
941 *PBASE: MEM_REF (T1, C1)
kono
parents:
diff changeset
942
kono
parents:
diff changeset
943 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
kono
parents:
diff changeset
944 or
kono
parents:
diff changeset
945 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
kono
parents:
diff changeset
946 or
kono
parents:
diff changeset
947 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
kono
parents:
diff changeset
948
kono
parents:
diff changeset
949 *PINDEX: C4 * BITS_PER_UNIT
kono
parents:
diff changeset
950
kono
parents:
diff changeset
951 If not present, leave the input values unchanged and return FALSE.
kono
parents:
diff changeset
952 Otherwise, modify the input values as follows and return TRUE:
kono
parents:
diff changeset
953
kono
parents:
diff changeset
954 *PBASE: T1
kono
parents:
diff changeset
955 *POFFSET: MULT_EXPR (T2, C3)
kono
parents:
diff changeset
956 *PINDEX: C1 + (C2 * C3) + C4
kono
parents:
diff changeset
957
kono
parents:
diff changeset
958 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
kono
parents:
diff changeset
959 will be further restructured to:
kono
parents:
diff changeset
960
kono
parents:
diff changeset
961 *PBASE: T1
kono
parents:
diff changeset
962 *POFFSET: MULT_EXPR (T2', C3)
kono
parents:
diff changeset
963 *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
kono
parents:
diff changeset
964
kono
parents:
diff changeset
965 static bool
kono
parents:
diff changeset
966 restructure_reference (tree *pbase, tree *poffset, widest_int *pindex,
kono
parents:
diff changeset
967 tree *ptype)
kono
parents:
diff changeset
968 {
kono
parents:
diff changeset
969 tree base = *pbase, offset = *poffset;
kono
parents:
diff changeset
970 widest_int index = *pindex;
kono
parents:
diff changeset
971 tree mult_op0, t1, t2, type;
kono
parents:
diff changeset
972 widest_int c1, c2, c3, c4, c5;
kono
parents:
diff changeset
973
kono
parents:
diff changeset
974 if (!base
kono
parents:
diff changeset
975 || !offset
kono
parents:
diff changeset
976 || TREE_CODE (base) != MEM_REF
kono
parents:
diff changeset
977 || TREE_CODE (offset) != MULT_EXPR
kono
parents:
diff changeset
978 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
kono
parents:
diff changeset
979 || wi::umod_floor (index, BITS_PER_UNIT) != 0)
kono
parents:
diff changeset
980 return false;
kono
parents:
diff changeset
981
kono
parents:
diff changeset
982 t1 = TREE_OPERAND (base, 0);
kono
parents:
diff changeset
983 c1 = widest_int::from (mem_ref_offset (base), SIGNED);
kono
parents:
diff changeset
984 type = TREE_TYPE (TREE_OPERAND (base, 1));
kono
parents:
diff changeset
985
kono
parents:
diff changeset
986 mult_op0 = TREE_OPERAND (offset, 0);
kono
parents:
diff changeset
987 c3 = wi::to_widest (TREE_OPERAND (offset, 1));
kono
parents:
diff changeset
988
kono
parents:
diff changeset
989 if (TREE_CODE (mult_op0) == PLUS_EXPR)
kono
parents:
diff changeset
990
kono
parents:
diff changeset
991 if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
kono
parents:
diff changeset
992 {
kono
parents:
diff changeset
993 t2 = TREE_OPERAND (mult_op0, 0);
kono
parents:
diff changeset
994 c2 = wi::to_widest (TREE_OPERAND (mult_op0, 1));
kono
parents:
diff changeset
995 }
kono
parents:
diff changeset
996 else
kono
parents:
diff changeset
997 return false;
kono
parents:
diff changeset
998
kono
parents:
diff changeset
999 else if (TREE_CODE (mult_op0) == MINUS_EXPR)
kono
parents:
diff changeset
1000
kono
parents:
diff changeset
1001 if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
kono
parents:
diff changeset
1002 {
kono
parents:
diff changeset
1003 t2 = TREE_OPERAND (mult_op0, 0);
kono
parents:
diff changeset
1004 c2 = -wi::to_widest (TREE_OPERAND (mult_op0, 1));
kono
parents:
diff changeset
1005 }
kono
parents:
diff changeset
1006 else
kono
parents:
diff changeset
1007 return false;
kono
parents:
diff changeset
1008
kono
parents:
diff changeset
1009 else
kono
parents:
diff changeset
1010 {
kono
parents:
diff changeset
1011 t2 = mult_op0;
kono
parents:
diff changeset
1012 c2 = 0;
kono
parents:
diff changeset
1013 }
kono
parents:
diff changeset
1014
kono
parents:
diff changeset
1015 c4 = index >> LOG2_BITS_PER_UNIT;
kono
parents:
diff changeset
1016 c5 = backtrace_base_for_ref (&t2);
kono
parents:
diff changeset
1017
kono
parents:
diff changeset
1018 *pbase = t1;
kono
parents:
diff changeset
1019 *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2),
kono
parents:
diff changeset
1020 wide_int_to_tree (sizetype, c3));
kono
parents:
diff changeset
1021 *pindex = c1 + c2 * c3 + c4 + c5 * c3;
kono
parents:
diff changeset
1022 *ptype = type;
kono
parents:
diff changeset
1023
kono
parents:
diff changeset
1024 return true;
kono
parents:
diff changeset
1025 }
kono
parents:
diff changeset
1026
kono
parents:
diff changeset
1027 /* Given GS which contains a data reference, create a CAND_REF entry in
kono
parents:
diff changeset
1028 the candidate table and attempt to find a basis. */
kono
parents:
diff changeset
1029
kono
parents:
diff changeset
1030 static void
kono
parents:
diff changeset
1031 slsr_process_ref (gimple *gs)
kono
parents:
diff changeset
1032 {
kono
parents:
diff changeset
1033 tree ref_expr, base, offset, type;
kono
parents:
diff changeset
1034 HOST_WIDE_INT bitsize, bitpos;
kono
parents:
diff changeset
1035 machine_mode mode;
kono
parents:
diff changeset
1036 int unsignedp, reversep, volatilep;
kono
parents:
diff changeset
1037 slsr_cand_t c;
kono
parents:
diff changeset
1038
kono
parents:
diff changeset
1039 if (gimple_vdef (gs))
kono
parents:
diff changeset
1040 ref_expr = gimple_assign_lhs (gs);
kono
parents:
diff changeset
1041 else
kono
parents:
diff changeset
1042 ref_expr = gimple_assign_rhs1 (gs);
kono
parents:
diff changeset
1043
kono
parents:
diff changeset
1044 if (!handled_component_p (ref_expr)
kono
parents:
diff changeset
1045 || TREE_CODE (ref_expr) == BIT_FIELD_REF
kono
parents:
diff changeset
1046 || (TREE_CODE (ref_expr) == COMPONENT_REF
kono
parents:
diff changeset
1047 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1))))
kono
parents:
diff changeset
1048 return;
kono
parents:
diff changeset
1049
kono
parents:
diff changeset
1050 base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode,
kono
parents:
diff changeset
1051 &unsignedp, &reversep, &volatilep);
kono
parents:
diff changeset
1052 if (reversep)
kono
parents:
diff changeset
1053 return;
kono
parents:
diff changeset
1054 widest_int index = bitpos;
kono
parents:
diff changeset
1055
kono
parents:
diff changeset
1056 if (!restructure_reference (&base, &offset, &index, &type))
kono
parents:
diff changeset
1057 return;
kono
parents:
diff changeset
1058
kono
parents:
diff changeset
1059 c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset,
kono
parents:
diff changeset
1060 type, sizetype, 0);
kono
parents:
diff changeset
1061
kono
parents:
diff changeset
1062 /* Add the candidate to the statement-candidate mapping. */
kono
parents:
diff changeset
1063 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1064 }
kono
parents:
diff changeset
1065
kono
parents:
diff changeset
1066 /* Create a candidate entry for a statement GS, where GS multiplies
kono
parents:
diff changeset
1067 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
kono
parents:
diff changeset
1068 about the two SSA names into the new candidate. Return the new
kono
parents:
diff changeset
1069 candidate. */
kono
parents:
diff changeset
1070
kono
parents:
diff changeset
1071 static slsr_cand_t
kono
parents:
diff changeset
1072 create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
kono
parents:
diff changeset
1073 {
kono
parents:
diff changeset
1074 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
kono
parents:
diff changeset
1075 tree stype = NULL_TREE;
kono
parents:
diff changeset
1076 widest_int index;
kono
parents:
diff changeset
1077 unsigned savings = 0;
kono
parents:
diff changeset
1078 slsr_cand_t c;
kono
parents:
diff changeset
1079 slsr_cand_t base_cand = base_cand_from_table (base_in);
kono
parents:
diff changeset
1080
kono
parents:
diff changeset
1081 /* Look at all interpretations of the base candidate, if necessary,
kono
parents:
diff changeset
1082 to find information to propagate into this candidate. */
kono
parents:
diff changeset
1083 while (base_cand && !base && base_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1084 {
kono
parents:
diff changeset
1085
kono
parents:
diff changeset
1086 if (base_cand->kind == CAND_MULT && integer_onep (base_cand->stride))
kono
parents:
diff changeset
1087 {
kono
parents:
diff changeset
1088 /* Y = (B + i') * 1
kono
parents:
diff changeset
1089 X = Y * Z
kono
parents:
diff changeset
1090 ================
kono
parents:
diff changeset
1091 X = (B + i') * Z */
kono
parents:
diff changeset
1092 base = base_cand->base_expr;
kono
parents:
diff changeset
1093 index = base_cand->index;
kono
parents:
diff changeset
1094 stride = stride_in;
kono
parents:
diff changeset
1095 ctype = base_cand->cand_type;
kono
parents:
diff changeset
1096 stype = TREE_TYPE (stride_in);
kono
parents:
diff changeset
1097 if (has_single_use (base_in))
kono
parents:
diff changeset
1098 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1099 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1100 }
kono
parents:
diff changeset
1101 else if (base_cand->kind == CAND_ADD
kono
parents:
diff changeset
1102 && TREE_CODE (base_cand->stride) == INTEGER_CST)
kono
parents:
diff changeset
1103 {
kono
parents:
diff changeset
1104 /* Y = B + (i' * S), S constant
kono
parents:
diff changeset
1105 X = Y * Z
kono
parents:
diff changeset
1106 ============================
kono
parents:
diff changeset
1107 X = B + ((i' * S) * Z) */
kono
parents:
diff changeset
1108 base = base_cand->base_expr;
kono
parents:
diff changeset
1109 index = base_cand->index * wi::to_widest (base_cand->stride);
kono
parents:
diff changeset
1110 stride = stride_in;
kono
parents:
diff changeset
1111 ctype = base_cand->cand_type;
kono
parents:
diff changeset
1112 stype = TREE_TYPE (stride_in);
kono
parents:
diff changeset
1113 if (has_single_use (base_in))
kono
parents:
diff changeset
1114 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1115 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1116 }
kono
parents:
diff changeset
1117
kono
parents:
diff changeset
1118 if (base_cand->next_interp)
kono
parents:
diff changeset
1119 base_cand = lookup_cand (base_cand->next_interp);
kono
parents:
diff changeset
1120 else
kono
parents:
diff changeset
1121 base_cand = NULL;
kono
parents:
diff changeset
1122 }
kono
parents:
diff changeset
1123
kono
parents:
diff changeset
1124 if (!base)
kono
parents:
diff changeset
1125 {
kono
parents:
diff changeset
1126 /* No interpretations had anything useful to propagate, so
kono
parents:
diff changeset
1127 produce X = (Y + 0) * Z. */
kono
parents:
diff changeset
1128 base = base_in;
kono
parents:
diff changeset
1129 index = 0;
kono
parents:
diff changeset
1130 stride = stride_in;
kono
parents:
diff changeset
1131 ctype = TREE_TYPE (base_in);
kono
parents:
diff changeset
1132 stype = TREE_TYPE (stride_in);
kono
parents:
diff changeset
1133 }
kono
parents:
diff changeset
1134
kono
parents:
diff changeset
1135 c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
kono
parents:
diff changeset
1136 ctype, stype, savings);
kono
parents:
diff changeset
1137 return c;
kono
parents:
diff changeset
1138 }
kono
parents:
diff changeset
1139
kono
parents:
diff changeset
1140 /* Create a candidate entry for a statement GS, where GS multiplies
kono
parents:
diff changeset
1141 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
kono
parents:
diff changeset
1142 information about BASE_IN into the new candidate. Return the new
kono
parents:
diff changeset
1143 candidate. */
kono
parents:
diff changeset
1144
kono
parents:
diff changeset
1145 static slsr_cand_t
kono
parents:
diff changeset
1146 create_mul_imm_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
kono
parents:
diff changeset
1147 {
kono
parents:
diff changeset
1148 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
kono
parents:
diff changeset
1149 widest_int index, temp;
kono
parents:
diff changeset
1150 unsigned savings = 0;
kono
parents:
diff changeset
1151 slsr_cand_t c;
kono
parents:
diff changeset
1152 slsr_cand_t base_cand = base_cand_from_table (base_in);
kono
parents:
diff changeset
1153
kono
parents:
diff changeset
1154 /* Look at all interpretations of the base candidate, if necessary,
kono
parents:
diff changeset
1155 to find information to propagate into this candidate. */
kono
parents:
diff changeset
1156 while (base_cand && !base && base_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1157 {
kono
parents:
diff changeset
1158 if (base_cand->kind == CAND_MULT
kono
parents:
diff changeset
1159 && TREE_CODE (base_cand->stride) == INTEGER_CST)
kono
parents:
diff changeset
1160 {
kono
parents:
diff changeset
1161 /* Y = (B + i') * S, S constant
kono
parents:
diff changeset
1162 X = Y * c
kono
parents:
diff changeset
1163 ============================
kono
parents:
diff changeset
1164 X = (B + i') * (S * c) */
kono
parents:
diff changeset
1165 temp = wi::to_widest (base_cand->stride) * wi::to_widest (stride_in);
kono
parents:
diff changeset
1166 if (wi::fits_to_tree_p (temp, TREE_TYPE (stride_in)))
kono
parents:
diff changeset
1167 {
kono
parents:
diff changeset
1168 base = base_cand->base_expr;
kono
parents:
diff changeset
1169 index = base_cand->index;
kono
parents:
diff changeset
1170 stride = wide_int_to_tree (TREE_TYPE (stride_in), temp);
kono
parents:
diff changeset
1171 ctype = base_cand->cand_type;
kono
parents:
diff changeset
1172 if (has_single_use (base_in))
kono
parents:
diff changeset
1173 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1174 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1175 }
kono
parents:
diff changeset
1176 }
kono
parents:
diff changeset
1177 else if (base_cand->kind == CAND_ADD && integer_onep (base_cand->stride))
kono
parents:
diff changeset
1178 {
kono
parents:
diff changeset
1179 /* Y = B + (i' * 1)
kono
parents:
diff changeset
1180 X = Y * c
kono
parents:
diff changeset
1181 ===========================
kono
parents:
diff changeset
1182 X = (B + i') * c */
kono
parents:
diff changeset
1183 base = base_cand->base_expr;
kono
parents:
diff changeset
1184 index = base_cand->index;
kono
parents:
diff changeset
1185 stride = stride_in;
kono
parents:
diff changeset
1186 ctype = base_cand->cand_type;
kono
parents:
diff changeset
1187 if (has_single_use (base_in))
kono
parents:
diff changeset
1188 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1189 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1190 }
kono
parents:
diff changeset
1191 else if (base_cand->kind == CAND_ADD
kono
parents:
diff changeset
1192 && base_cand->index == 1
kono
parents:
diff changeset
1193 && TREE_CODE (base_cand->stride) == INTEGER_CST)
kono
parents:
diff changeset
1194 {
kono
parents:
diff changeset
1195 /* Y = B + (1 * S), S constant
kono
parents:
diff changeset
1196 X = Y * c
kono
parents:
diff changeset
1197 ===========================
kono
parents:
diff changeset
1198 X = (B + S) * c */
kono
parents:
diff changeset
1199 base = base_cand->base_expr;
kono
parents:
diff changeset
1200 index = wi::to_widest (base_cand->stride);
kono
parents:
diff changeset
1201 stride = stride_in;
kono
parents:
diff changeset
1202 ctype = base_cand->cand_type;
kono
parents:
diff changeset
1203 if (has_single_use (base_in))
kono
parents:
diff changeset
1204 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1205 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1206 }
kono
parents:
diff changeset
1207
kono
parents:
diff changeset
1208 if (base_cand->next_interp)
kono
parents:
diff changeset
1209 base_cand = lookup_cand (base_cand->next_interp);
kono
parents:
diff changeset
1210 else
kono
parents:
diff changeset
1211 base_cand = NULL;
kono
parents:
diff changeset
1212 }
kono
parents:
diff changeset
1213
kono
parents:
diff changeset
1214 if (!base)
kono
parents:
diff changeset
1215 {
kono
parents:
diff changeset
1216 /* No interpretations had anything useful to propagate, so
kono
parents:
diff changeset
1217 produce X = (Y + 0) * c. */
kono
parents:
diff changeset
1218 base = base_in;
kono
parents:
diff changeset
1219 index = 0;
kono
parents:
diff changeset
1220 stride = stride_in;
kono
parents:
diff changeset
1221 ctype = TREE_TYPE (base_in);
kono
parents:
diff changeset
1222 }
kono
parents:
diff changeset
1223
kono
parents:
diff changeset
1224 c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
kono
parents:
diff changeset
1225 ctype, sizetype, savings);
kono
parents:
diff changeset
1226 return c;
kono
parents:
diff changeset
1227 }
kono
parents:
diff changeset
1228
kono
parents:
diff changeset
1229 /* Given GS which is a multiply of scalar integers, make an appropriate
kono
parents:
diff changeset
1230 entry in the candidate table. If this is a multiply of two SSA names,
kono
parents:
diff changeset
1231 create two CAND_MULT interpretations and attempt to find a basis for
kono
parents:
diff changeset
1232 each of them. Otherwise, create a single CAND_MULT and attempt to
kono
parents:
diff changeset
1233 find a basis. */
kono
parents:
diff changeset
1234
kono
parents:
diff changeset
1235 static void
kono
parents:
diff changeset
1236 slsr_process_mul (gimple *gs, tree rhs1, tree rhs2, bool speed)
kono
parents:
diff changeset
1237 {
kono
parents:
diff changeset
1238 slsr_cand_t c, c2;
kono
parents:
diff changeset
1239
kono
parents:
diff changeset
1240 /* If this is a multiply of an SSA name with itself, it is highly
kono
parents:
diff changeset
1241 unlikely that we will get a strength reduction opportunity, so
kono
parents:
diff changeset
1242 don't record it as a candidate. This simplifies the logic for
kono
parents:
diff changeset
1243 finding a basis, so if this is removed that must be considered. */
kono
parents:
diff changeset
1244 if (rhs1 == rhs2)
kono
parents:
diff changeset
1245 return;
kono
parents:
diff changeset
1246
kono
parents:
diff changeset
1247 if (TREE_CODE (rhs2) == SSA_NAME)
kono
parents:
diff changeset
1248 {
kono
parents:
diff changeset
1249 /* Record an interpretation of this statement in the candidate table
kono
parents:
diff changeset
1250 assuming RHS1 is the base expression and RHS2 is the stride. */
kono
parents:
diff changeset
1251 c = create_mul_ssa_cand (gs, rhs1, rhs2, speed);
kono
parents:
diff changeset
1252
kono
parents:
diff changeset
1253 /* Add the first interpretation to the statement-candidate mapping. */
kono
parents:
diff changeset
1254 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1255
kono
parents:
diff changeset
1256 /* Record another interpretation of this statement assuming RHS1
kono
parents:
diff changeset
1257 is the stride and RHS2 is the base expression. */
kono
parents:
diff changeset
1258 c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);
kono
parents:
diff changeset
1259 c->next_interp = c2->cand_num;
kono
parents:
diff changeset
1260 }
kono
parents:
diff changeset
1261 else
kono
parents:
diff changeset
1262 {
kono
parents:
diff changeset
1263 /* Record an interpretation for the multiply-immediate. */
kono
parents:
diff changeset
1264 c = create_mul_imm_cand (gs, rhs1, rhs2, speed);
kono
parents:
diff changeset
1265
kono
parents:
diff changeset
1266 /* Add the interpretation to the statement-candidate mapping. */
kono
parents:
diff changeset
1267 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1268 }
kono
parents:
diff changeset
1269 }
kono
parents:
diff changeset
1270
kono
parents:
diff changeset
1271 /* Create a candidate entry for a statement GS, where GS adds two
kono
parents:
diff changeset
1272 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
kono
parents:
diff changeset
1273 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
kono
parents:
diff changeset
1274 information about the two SSA names into the new candidate.
kono
parents:
diff changeset
1275 Return the new candidate. */
kono
parents:
diff changeset
1276
kono
parents:
diff changeset
1277 static slsr_cand_t
kono
parents:
diff changeset
1278 create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in,
kono
parents:
diff changeset
1279 bool subtract_p, bool speed)
kono
parents:
diff changeset
1280 {
kono
parents:
diff changeset
1281 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
kono
parents:
diff changeset
1282 tree stype = NULL_TREE;
kono
parents:
diff changeset
1283 widest_int index;
kono
parents:
diff changeset
1284 unsigned savings = 0;
kono
parents:
diff changeset
1285 slsr_cand_t c;
kono
parents:
diff changeset
1286 slsr_cand_t base_cand = base_cand_from_table (base_in);
kono
parents:
diff changeset
1287 slsr_cand_t addend_cand = base_cand_from_table (addend_in);
kono
parents:
diff changeset
1288
kono
parents:
diff changeset
1289 /* The most useful transformation is a multiply-immediate feeding
kono
parents:
diff changeset
1290 an add or subtract. Look for that first. */
kono
parents:
diff changeset
1291 while (addend_cand && !base && addend_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1292 {
kono
parents:
diff changeset
1293 if (addend_cand->kind == CAND_MULT
kono
parents:
diff changeset
1294 && addend_cand->index == 0
kono
parents:
diff changeset
1295 && TREE_CODE (addend_cand->stride) == INTEGER_CST)
kono
parents:
diff changeset
1296 {
kono
parents:
diff changeset
1297 /* Z = (B + 0) * S, S constant
kono
parents:
diff changeset
1298 X = Y +/- Z
kono
parents:
diff changeset
1299 ===========================
kono
parents:
diff changeset
1300 X = Y + ((+/-1 * S) * B) */
kono
parents:
diff changeset
1301 base = base_in;
kono
parents:
diff changeset
1302 index = wi::to_widest (addend_cand->stride);
kono
parents:
diff changeset
1303 if (subtract_p)
kono
parents:
diff changeset
1304 index = -index;
kono
parents:
diff changeset
1305 stride = addend_cand->base_expr;
kono
parents:
diff changeset
1306 ctype = TREE_TYPE (base_in);
kono
parents:
diff changeset
1307 stype = addend_cand->cand_type;
kono
parents:
diff changeset
1308 if (has_single_use (addend_in))
kono
parents:
diff changeset
1309 savings = (addend_cand->dead_savings
kono
parents:
diff changeset
1310 + stmt_cost (addend_cand->cand_stmt, speed));
kono
parents:
diff changeset
1311 }
kono
parents:
diff changeset
1312
kono
parents:
diff changeset
1313 if (addend_cand->next_interp)
kono
parents:
diff changeset
1314 addend_cand = lookup_cand (addend_cand->next_interp);
kono
parents:
diff changeset
1315 else
kono
parents:
diff changeset
1316 addend_cand = NULL;
kono
parents:
diff changeset
1317 }
kono
parents:
diff changeset
1318
kono
parents:
diff changeset
1319 while (base_cand && !base && base_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1320 {
kono
parents:
diff changeset
1321 if (base_cand->kind == CAND_ADD
kono
parents:
diff changeset
1322 && (base_cand->index == 0
kono
parents:
diff changeset
1323 || operand_equal_p (base_cand->stride,
kono
parents:
diff changeset
1324 integer_zero_node, 0)))
kono
parents:
diff changeset
1325 {
kono
parents:
diff changeset
1326 /* Y = B + (i' * S), i' * S = 0
kono
parents:
diff changeset
1327 X = Y +/- Z
kono
parents:
diff changeset
1328 ============================
kono
parents:
diff changeset
1329 X = B + (+/-1 * Z) */
kono
parents:
diff changeset
1330 base = base_cand->base_expr;
kono
parents:
diff changeset
1331 index = subtract_p ? -1 : 1;
kono
parents:
diff changeset
1332 stride = addend_in;
kono
parents:
diff changeset
1333 ctype = base_cand->cand_type;
kono
parents:
diff changeset
1334 stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype
kono
parents:
diff changeset
1335 : TREE_TYPE (addend_in));
kono
parents:
diff changeset
1336 if (has_single_use (base_in))
kono
parents:
diff changeset
1337 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1338 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1339 }
kono
parents:
diff changeset
1340 else if (subtract_p)
kono
parents:
diff changeset
1341 {
kono
parents:
diff changeset
1342 slsr_cand_t subtrahend_cand = base_cand_from_table (addend_in);
kono
parents:
diff changeset
1343
kono
parents:
diff changeset
1344 while (subtrahend_cand && !base && subtrahend_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1345 {
kono
parents:
diff changeset
1346 if (subtrahend_cand->kind == CAND_MULT
kono
parents:
diff changeset
1347 && subtrahend_cand->index == 0
kono
parents:
diff changeset
1348 && TREE_CODE (subtrahend_cand->stride) == INTEGER_CST)
kono
parents:
diff changeset
1349 {
kono
parents:
diff changeset
1350 /* Z = (B + 0) * S, S constant
kono
parents:
diff changeset
1351 X = Y - Z
kono
parents:
diff changeset
1352 ===========================
kono
parents:
diff changeset
1353 Value: X = Y + ((-1 * S) * B) */
kono
parents:
diff changeset
1354 base = base_in;
kono
parents:
diff changeset
1355 index = wi::to_widest (subtrahend_cand->stride);
kono
parents:
diff changeset
1356 index = -index;
kono
parents:
diff changeset
1357 stride = subtrahend_cand->base_expr;
kono
parents:
diff changeset
1358 ctype = TREE_TYPE (base_in);
kono
parents:
diff changeset
1359 stype = subtrahend_cand->cand_type;
kono
parents:
diff changeset
1360 if (has_single_use (addend_in))
kono
parents:
diff changeset
1361 savings = (subtrahend_cand->dead_savings
kono
parents:
diff changeset
1362 + stmt_cost (subtrahend_cand->cand_stmt, speed));
kono
parents:
diff changeset
1363 }
kono
parents:
diff changeset
1364
kono
parents:
diff changeset
1365 if (subtrahend_cand->next_interp)
kono
parents:
diff changeset
1366 subtrahend_cand = lookup_cand (subtrahend_cand->next_interp);
kono
parents:
diff changeset
1367 else
kono
parents:
diff changeset
1368 subtrahend_cand = NULL;
kono
parents:
diff changeset
1369 }
kono
parents:
diff changeset
1370 }
kono
parents:
diff changeset
1371
kono
parents:
diff changeset
1372 if (base_cand->next_interp)
kono
parents:
diff changeset
1373 base_cand = lookup_cand (base_cand->next_interp);
kono
parents:
diff changeset
1374 else
kono
parents:
diff changeset
1375 base_cand = NULL;
kono
parents:
diff changeset
1376 }
kono
parents:
diff changeset
1377
kono
parents:
diff changeset
1378 if (!base)
kono
parents:
diff changeset
1379 {
kono
parents:
diff changeset
1380 /* No interpretations had anything useful to propagate, so
kono
parents:
diff changeset
1381 produce X = Y + (1 * Z). */
kono
parents:
diff changeset
1382 base = base_in;
kono
parents:
diff changeset
1383 index = subtract_p ? -1 : 1;
kono
parents:
diff changeset
1384 stride = addend_in;
kono
parents:
diff changeset
1385 ctype = TREE_TYPE (base_in);
kono
parents:
diff changeset
1386 stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype
kono
parents:
diff changeset
1387 : TREE_TYPE (addend_in));
kono
parents:
diff changeset
1388 }
kono
parents:
diff changeset
1389
kono
parents:
diff changeset
1390 c = alloc_cand_and_find_basis (CAND_ADD, gs, base, index, stride,
kono
parents:
diff changeset
1391 ctype, stype, savings);
kono
parents:
diff changeset
1392 return c;
kono
parents:
diff changeset
1393 }
kono
parents:
diff changeset
1394
kono
parents:
diff changeset
1395 /* Create a candidate entry for a statement GS, where GS adds SSA
kono
parents:
diff changeset
1396 name BASE_IN to constant INDEX_IN. Propagate any known information
kono
parents:
diff changeset
1397 about BASE_IN into the new candidate. Return the new candidate. */
kono
parents:
diff changeset
1398
kono
parents:
diff changeset
1399 static slsr_cand_t
kono
parents:
diff changeset
1400 create_add_imm_cand (gimple *gs, tree base_in, const widest_int &index_in,
kono
parents:
diff changeset
1401 bool speed)
kono
parents:
diff changeset
1402 {
kono
parents:
diff changeset
1403 enum cand_kind kind = CAND_ADD;
kono
parents:
diff changeset
1404 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
kono
parents:
diff changeset
1405 tree stype = NULL_TREE;
kono
parents:
diff changeset
1406 widest_int index, multiple;
kono
parents:
diff changeset
1407 unsigned savings = 0;
kono
parents:
diff changeset
1408 slsr_cand_t c;
kono
parents:
diff changeset
1409 slsr_cand_t base_cand = base_cand_from_table (base_in);
kono
parents:
diff changeset
1410
kono
parents:
diff changeset
1411 while (base_cand && !base && base_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1412 {
kono
parents:
diff changeset
1413 signop sign = TYPE_SIGN (TREE_TYPE (base_cand->stride));
kono
parents:
diff changeset
1414
kono
parents:
diff changeset
1415 if (TREE_CODE (base_cand->stride) == INTEGER_CST
kono
parents:
diff changeset
1416 && wi::multiple_of_p (index_in, wi::to_widest (base_cand->stride),
kono
parents:
diff changeset
1417 sign, &multiple))
kono
parents:
diff changeset
1418 {
kono
parents:
diff changeset
1419 /* Y = (B + i') * S, S constant, c = kS for some integer k
kono
parents:
diff changeset
1420 X = Y + c
kono
parents:
diff changeset
1421 ============================
kono
parents:
diff changeset
1422 X = (B + (i'+ k)) * S
kono
parents:
diff changeset
1423 OR
kono
parents:
diff changeset
1424 Y = B + (i' * S), S constant, c = kS for some integer k
kono
parents:
diff changeset
1425 X = Y + c
kono
parents:
diff changeset
1426 ============================
kono
parents:
diff changeset
1427 X = (B + (i'+ k)) * S */
kono
parents:
diff changeset
1428 kind = base_cand->kind;
kono
parents:
diff changeset
1429 base = base_cand->base_expr;
kono
parents:
diff changeset
1430 index = base_cand->index + multiple;
kono
parents:
diff changeset
1431 stride = base_cand->stride;
kono
parents:
diff changeset
1432 ctype = base_cand->cand_type;
kono
parents:
diff changeset
1433 stype = base_cand->stride_type;
kono
parents:
diff changeset
1434 if (has_single_use (base_in))
kono
parents:
diff changeset
1435 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1436 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1437 }
kono
parents:
diff changeset
1438
kono
parents:
diff changeset
1439 if (base_cand->next_interp)
kono
parents:
diff changeset
1440 base_cand = lookup_cand (base_cand->next_interp);
kono
parents:
diff changeset
1441 else
kono
parents:
diff changeset
1442 base_cand = NULL;
kono
parents:
diff changeset
1443 }
kono
parents:
diff changeset
1444
kono
parents:
diff changeset
1445 if (!base)
kono
parents:
diff changeset
1446 {
kono
parents:
diff changeset
1447 /* No interpretations had anything useful to propagate, so
kono
parents:
diff changeset
1448 produce X = Y + (c * 1). */
kono
parents:
diff changeset
1449 kind = CAND_ADD;
kono
parents:
diff changeset
1450 base = base_in;
kono
parents:
diff changeset
1451 index = index_in;
kono
parents:
diff changeset
1452 stride = integer_one_node;
kono
parents:
diff changeset
1453 ctype = TREE_TYPE (base_in);
kono
parents:
diff changeset
1454 stype = sizetype;
kono
parents:
diff changeset
1455 }
kono
parents:
diff changeset
1456
kono
parents:
diff changeset
1457 c = alloc_cand_and_find_basis (kind, gs, base, index, stride,
kono
parents:
diff changeset
1458 ctype, stype, savings);
kono
parents:
diff changeset
1459 return c;
kono
parents:
diff changeset
1460 }
kono
parents:
diff changeset
1461
kono
parents:
diff changeset
1462 /* Given GS which is an add or subtract of scalar integers or pointers,
kono
parents:
diff changeset
1463 make at least one appropriate entry in the candidate table. */
kono
parents:
diff changeset
1464
kono
parents:
diff changeset
1465 static void
kono
parents:
diff changeset
1466 slsr_process_add (gimple *gs, tree rhs1, tree rhs2, bool speed)
kono
parents:
diff changeset
1467 {
kono
parents:
diff changeset
1468 bool subtract_p = gimple_assign_rhs_code (gs) == MINUS_EXPR;
kono
parents:
diff changeset
1469 slsr_cand_t c = NULL, c2;
kono
parents:
diff changeset
1470
kono
parents:
diff changeset
1471 if (TREE_CODE (rhs2) == SSA_NAME)
kono
parents:
diff changeset
1472 {
kono
parents:
diff changeset
1473 /* First record an interpretation assuming RHS1 is the base expression
kono
parents:
diff changeset
1474 and RHS2 is the stride. But it doesn't make sense for the
kono
parents:
diff changeset
1475 stride to be a pointer, so don't record a candidate in that case. */
kono
parents:
diff changeset
1476 if (!POINTER_TYPE_P (TREE_TYPE (rhs2)))
kono
parents:
diff changeset
1477 {
kono
parents:
diff changeset
1478 c = create_add_ssa_cand (gs, rhs1, rhs2, subtract_p, speed);
kono
parents:
diff changeset
1479
kono
parents:
diff changeset
1480 /* Add the first interpretation to the statement-candidate
kono
parents:
diff changeset
1481 mapping. */
kono
parents:
diff changeset
1482 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1483 }
kono
parents:
diff changeset
1484
kono
parents:
diff changeset
1485 /* If the two RHS operands are identical, or this is a subtract,
kono
parents:
diff changeset
1486 we're done. */
kono
parents:
diff changeset
1487 if (operand_equal_p (rhs1, rhs2, 0) || subtract_p)
kono
parents:
diff changeset
1488 return;
kono
parents:
diff changeset
1489
kono
parents:
diff changeset
1490 /* Otherwise, record another interpretation assuming RHS2 is the
kono
parents:
diff changeset
1491 base expression and RHS1 is the stride, again provided that the
kono
parents:
diff changeset
1492 stride is not a pointer. */
kono
parents:
diff changeset
1493 if (!POINTER_TYPE_P (TREE_TYPE (rhs1)))
kono
parents:
diff changeset
1494 {
kono
parents:
diff changeset
1495 c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);
kono
parents:
diff changeset
1496 if (c)
kono
parents:
diff changeset
1497 c->next_interp = c2->cand_num;
kono
parents:
diff changeset
1498 else
kono
parents:
diff changeset
1499 add_cand_for_stmt (gs, c2);
kono
parents:
diff changeset
1500 }
kono
parents:
diff changeset
1501 }
kono
parents:
diff changeset
1502 else
kono
parents:
diff changeset
1503 {
kono
parents:
diff changeset
1504 /* Record an interpretation for the add-immediate. */
kono
parents:
diff changeset
1505 widest_int index = wi::to_widest (rhs2);
kono
parents:
diff changeset
1506 if (subtract_p)
kono
parents:
diff changeset
1507 index = -index;
kono
parents:
diff changeset
1508
kono
parents:
diff changeset
1509 c = create_add_imm_cand (gs, rhs1, index, speed);
kono
parents:
diff changeset
1510
kono
parents:
diff changeset
1511 /* Add the interpretation to the statement-candidate mapping. */
kono
parents:
diff changeset
1512 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1513 }
kono
parents:
diff changeset
1514 }
kono
parents:
diff changeset
1515
kono
parents:
diff changeset
1516 /* Given GS which is a negate of a scalar integer, make an appropriate
kono
parents:
diff changeset
1517 entry in the candidate table. A negate is equivalent to a multiply
kono
parents:
diff changeset
1518 by -1. */
kono
parents:
diff changeset
1519
kono
parents:
diff changeset
1520 static void
kono
parents:
diff changeset
1521 slsr_process_neg (gimple *gs, tree rhs1, bool speed)
kono
parents:
diff changeset
1522 {
kono
parents:
diff changeset
1523 /* Record a CAND_MULT interpretation for the multiply by -1. */
kono
parents:
diff changeset
1524 slsr_cand_t c = create_mul_imm_cand (gs, rhs1, integer_minus_one_node, speed);
kono
parents:
diff changeset
1525
kono
parents:
diff changeset
1526 /* Add the interpretation to the statement-candidate mapping. */
kono
parents:
diff changeset
1527 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1528 }
kono
parents:
diff changeset
1529
kono
parents:
diff changeset
1530 /* Help function for legal_cast_p, operating on two trees. Checks
kono
parents:
diff changeset
1531 whether it's allowable to cast from RHS to LHS. See legal_cast_p
kono
parents:
diff changeset
1532 for more details. */
kono
parents:
diff changeset
1533
kono
parents:
diff changeset
1534 static bool
kono
parents:
diff changeset
1535 legal_cast_p_1 (tree lhs_type, tree rhs_type)
kono
parents:
diff changeset
1536 {
kono
parents:
diff changeset
1537 unsigned lhs_size, rhs_size;
kono
parents:
diff changeset
1538 bool lhs_wraps, rhs_wraps;
kono
parents:
diff changeset
1539
kono
parents:
diff changeset
1540 lhs_size = TYPE_PRECISION (lhs_type);
kono
parents:
diff changeset
1541 rhs_size = TYPE_PRECISION (rhs_type);
kono
parents:
diff changeset
1542 lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type);
kono
parents:
diff changeset
1543 rhs_wraps = ANY_INTEGRAL_TYPE_P (rhs_type) && TYPE_OVERFLOW_WRAPS (rhs_type);
kono
parents:
diff changeset
1544
kono
parents:
diff changeset
1545 if (lhs_size < rhs_size
kono
parents:
diff changeset
1546 || (rhs_wraps && !lhs_wraps)
kono
parents:
diff changeset
1547 || (rhs_wraps && lhs_wraps && rhs_size != lhs_size))
kono
parents:
diff changeset
1548 return false;
kono
parents:
diff changeset
1549
kono
parents:
diff changeset
1550 return true;
kono
parents:
diff changeset
1551 }
kono
parents:
diff changeset
1552
kono
parents:
diff changeset
1553 /* Return TRUE if GS is a statement that defines an SSA name from
kono
parents:
diff changeset
1554 a conversion and is legal for us to combine with an add and multiply
kono
parents:
diff changeset
1555 in the candidate table. For example, suppose we have:
kono
parents:
diff changeset
1556
kono
parents:
diff changeset
1557 A = B + i;
kono
parents:
diff changeset
1558 C = (type) A;
kono
parents:
diff changeset
1559 D = C * S;
kono
parents:
diff changeset
1560
kono
parents:
diff changeset
1561 Without the type-cast, we would create a CAND_MULT for D with base B,
kono
parents:
diff changeset
1562 index i, and stride S. We want to record this candidate only if it
kono
parents:
diff changeset
1563 is equivalent to apply the type cast following the multiply:
kono
parents:
diff changeset
1564
kono
parents:
diff changeset
1565 A = B + i;
kono
parents:
diff changeset
1566 E = A * S;
kono
parents:
diff changeset
1567 D = (type) E;
kono
parents:
diff changeset
1568
kono
parents:
diff changeset
1569 We will record the type with the candidate for D. This allows us
kono
parents:
diff changeset
1570 to use a similar previous candidate as a basis. If we have earlier seen
kono
parents:
diff changeset
1571
kono
parents:
diff changeset
1572 A' = B + i';
kono
parents:
diff changeset
1573 C' = (type) A';
kono
parents:
diff changeset
1574 D' = C' * S;
kono
parents:
diff changeset
1575
kono
parents:
diff changeset
1576 we can replace D with
kono
parents:
diff changeset
1577
kono
parents:
diff changeset
1578 D = D' + (i - i') * S;
kono
parents:
diff changeset
1579
kono
parents:
diff changeset
1580 But if moving the type-cast would change semantics, we mustn't do this.
kono
parents:
diff changeset
1581
kono
parents:
diff changeset
1582 This is legitimate for casts from a non-wrapping integral type to
kono
parents:
diff changeset
1583 any integral type of the same or larger size. It is not legitimate
kono
parents:
diff changeset
1584 to convert a wrapping type to a non-wrapping type, or to a wrapping
kono
parents:
diff changeset
1585 type of a different size. I.e., with a wrapping type, we must
kono
parents:
diff changeset
1586 assume that the addition B + i could wrap, in which case performing
kono
parents:
diff changeset
1587 the multiply before or after one of the "illegal" type casts will
kono
parents:
diff changeset
1588 have different semantics. */
kono
parents:
diff changeset
1589
kono
parents:
diff changeset
1590 static bool
kono
parents:
diff changeset
1591 legal_cast_p (gimple *gs, tree rhs)
kono
parents:
diff changeset
1592 {
kono
parents:
diff changeset
1593 if (!is_gimple_assign (gs)
kono
parents:
diff changeset
1594 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs)))
kono
parents:
diff changeset
1595 return false;
kono
parents:
diff changeset
1596
kono
parents:
diff changeset
1597 return legal_cast_p_1 (TREE_TYPE (gimple_assign_lhs (gs)), TREE_TYPE (rhs));
kono
parents:
diff changeset
1598 }
kono
parents:
diff changeset
1599
kono
parents:
diff changeset
1600 /* Given GS which is a cast to a scalar integer type, determine whether
kono
parents:
diff changeset
1601 the cast is legal for strength reduction. If so, make at least one
kono
parents:
diff changeset
1602 appropriate entry in the candidate table. */
kono
parents:
diff changeset
1603
kono
parents:
diff changeset
1604 static void
kono
parents:
diff changeset
1605 slsr_process_cast (gimple *gs, tree rhs1, bool speed)
kono
parents:
diff changeset
1606 {
kono
parents:
diff changeset
1607 tree lhs, ctype;
kono
parents:
diff changeset
1608 slsr_cand_t base_cand, c = NULL, c2;
kono
parents:
diff changeset
1609 unsigned savings = 0;
kono
parents:
diff changeset
1610
kono
parents:
diff changeset
1611 if (!legal_cast_p (gs, rhs1))
kono
parents:
diff changeset
1612 return;
kono
parents:
diff changeset
1613
kono
parents:
diff changeset
1614 lhs = gimple_assign_lhs (gs);
kono
parents:
diff changeset
1615 base_cand = base_cand_from_table (rhs1);
kono
parents:
diff changeset
1616 ctype = TREE_TYPE (lhs);
kono
parents:
diff changeset
1617
kono
parents:
diff changeset
1618 if (base_cand && base_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1619 {
kono
parents:
diff changeset
1620 while (base_cand)
kono
parents:
diff changeset
1621 {
kono
parents:
diff changeset
1622 /* Propagate all data from the base candidate except the type,
kono
parents:
diff changeset
1623 which comes from the cast, and the base candidate's cast,
kono
parents:
diff changeset
1624 which is no longer applicable. */
kono
parents:
diff changeset
1625 if (has_single_use (rhs1))
kono
parents:
diff changeset
1626 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1627 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1628
kono
parents:
diff changeset
1629 c = alloc_cand_and_find_basis (base_cand->kind, gs,
kono
parents:
diff changeset
1630 base_cand->base_expr,
kono
parents:
diff changeset
1631 base_cand->index, base_cand->stride,
kono
parents:
diff changeset
1632 ctype, base_cand->stride_type,
kono
parents:
diff changeset
1633 savings);
kono
parents:
diff changeset
1634 if (base_cand->next_interp)
kono
parents:
diff changeset
1635 base_cand = lookup_cand (base_cand->next_interp);
kono
parents:
diff changeset
1636 else
kono
parents:
diff changeset
1637 base_cand = NULL;
kono
parents:
diff changeset
1638 }
kono
parents:
diff changeset
1639 }
kono
parents:
diff changeset
1640 else
kono
parents:
diff changeset
1641 {
kono
parents:
diff changeset
1642 /* If nothing is known about the RHS, create fresh CAND_ADD and
kono
parents:
diff changeset
1643 CAND_MULT interpretations:
kono
parents:
diff changeset
1644
kono
parents:
diff changeset
1645 X = Y + (0 * 1)
kono
parents:
diff changeset
1646 X = (Y + 0) * 1
kono
parents:
diff changeset
1647
kono
parents:
diff changeset
1648 The first of these is somewhat arbitrary, but the choice of
kono
parents:
diff changeset
1649 1 for the stride simplifies the logic for propagating casts
kono
parents:
diff changeset
1650 into their uses. */
kono
parents:
diff changeset
1651 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0,
kono
parents:
diff changeset
1652 integer_one_node, ctype, sizetype, 0);
kono
parents:
diff changeset
1653 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
kono
parents:
diff changeset
1654 integer_one_node, ctype, sizetype, 0);
kono
parents:
diff changeset
1655 c->next_interp = c2->cand_num;
kono
parents:
diff changeset
1656 }
kono
parents:
diff changeset
1657
kono
parents:
diff changeset
1658 /* Add the first (or only) interpretation to the statement-candidate
kono
parents:
diff changeset
1659 mapping. */
kono
parents:
diff changeset
1660 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1661 }
kono
parents:
diff changeset
1662
kono
parents:
diff changeset
1663 /* Given GS which is a copy of a scalar integer type, make at least one
kono
parents:
diff changeset
1664 appropriate entry in the candidate table.
kono
parents:
diff changeset
1665
kono
parents:
diff changeset
1666 This interface is included for completeness, but is unnecessary
kono
parents:
diff changeset
1667 if this pass immediately follows a pass that performs copy
kono
parents:
diff changeset
1668 propagation, such as DOM. */
kono
parents:
diff changeset
1669
kono
parents:
diff changeset
1670 static void
kono
parents:
diff changeset
1671 slsr_process_copy (gimple *gs, tree rhs1, bool speed)
kono
parents:
diff changeset
1672 {
kono
parents:
diff changeset
1673 slsr_cand_t base_cand, c = NULL, c2;
kono
parents:
diff changeset
1674 unsigned savings = 0;
kono
parents:
diff changeset
1675
kono
parents:
diff changeset
1676 base_cand = base_cand_from_table (rhs1);
kono
parents:
diff changeset
1677
kono
parents:
diff changeset
1678 if (base_cand && base_cand->kind != CAND_PHI)
kono
parents:
diff changeset
1679 {
kono
parents:
diff changeset
1680 while (base_cand)
kono
parents:
diff changeset
1681 {
kono
parents:
diff changeset
1682 /* Propagate all data from the base candidate. */
kono
parents:
diff changeset
1683 if (has_single_use (rhs1))
kono
parents:
diff changeset
1684 savings = (base_cand->dead_savings
kono
parents:
diff changeset
1685 + stmt_cost (base_cand->cand_stmt, speed));
kono
parents:
diff changeset
1686
kono
parents:
diff changeset
1687 c = alloc_cand_and_find_basis (base_cand->kind, gs,
kono
parents:
diff changeset
1688 base_cand->base_expr,
kono
parents:
diff changeset
1689 base_cand->index, base_cand->stride,
kono
parents:
diff changeset
1690 base_cand->cand_type,
kono
parents:
diff changeset
1691 base_cand->stride_type, savings);
kono
parents:
diff changeset
1692 if (base_cand->next_interp)
kono
parents:
diff changeset
1693 base_cand = lookup_cand (base_cand->next_interp);
kono
parents:
diff changeset
1694 else
kono
parents:
diff changeset
1695 base_cand = NULL;
kono
parents:
diff changeset
1696 }
kono
parents:
diff changeset
1697 }
kono
parents:
diff changeset
1698 else
kono
parents:
diff changeset
1699 {
kono
parents:
diff changeset
1700 /* If nothing is known about the RHS, create fresh CAND_ADD and
kono
parents:
diff changeset
1701 CAND_MULT interpretations:
kono
parents:
diff changeset
1702
kono
parents:
diff changeset
1703 X = Y + (0 * 1)
kono
parents:
diff changeset
1704 X = (Y + 0) * 1
kono
parents:
diff changeset
1705
kono
parents:
diff changeset
1706 The first of these is somewhat arbitrary, but the choice of
kono
parents:
diff changeset
1707 1 for the stride simplifies the logic for propagating casts
kono
parents:
diff changeset
1708 into their uses. */
kono
parents:
diff changeset
1709 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0,
kono
parents:
diff changeset
1710 integer_one_node, TREE_TYPE (rhs1),
kono
parents:
diff changeset
1711 sizetype, 0);
kono
parents:
diff changeset
1712 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
kono
parents:
diff changeset
1713 integer_one_node, TREE_TYPE (rhs1),
kono
parents:
diff changeset
1714 sizetype, 0);
kono
parents:
diff changeset
1715 c->next_interp = c2->cand_num;
kono
parents:
diff changeset
1716 }
kono
parents:
diff changeset
1717
kono
parents:
diff changeset
1718 /* Add the first (or only) interpretation to the statement-candidate
kono
parents:
diff changeset
1719 mapping. */
kono
parents:
diff changeset
1720 add_cand_for_stmt (gs, c);
kono
parents:
diff changeset
1721 }
kono
parents:
diff changeset
1722
kono
parents:
diff changeset
1723 class find_candidates_dom_walker : public dom_walker
kono
parents:
diff changeset
1724 {
kono
parents:
diff changeset
1725 public:
kono
parents:
diff changeset
1726 find_candidates_dom_walker (cdi_direction direction)
kono
parents:
diff changeset
1727 : dom_walker (direction) {}
kono
parents:
diff changeset
1728 virtual edge before_dom_children (basic_block);
kono
parents:
diff changeset
1729 };
kono
parents:
diff changeset
1730
kono
parents:
diff changeset
1731 /* Find strength-reduction candidates in block BB. */
kono
parents:
diff changeset
1732
kono
parents:
diff changeset
1733 edge
kono
parents:
diff changeset
1734 find_candidates_dom_walker::before_dom_children (basic_block bb)
kono
parents:
diff changeset
1735 {
kono
parents:
diff changeset
1736 bool speed = optimize_bb_for_speed_p (bb);
kono
parents:
diff changeset
1737
kono
parents:
diff changeset
1738 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
kono
parents:
diff changeset
1739 gsi_next (&gsi))
kono
parents:
diff changeset
1740 slsr_process_phi (gsi.phi (), speed);
kono
parents:
diff changeset
1741
kono
parents:
diff changeset
1742 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
kono
parents:
diff changeset
1743 gsi_next (&gsi))
kono
parents:
diff changeset
1744 {
kono
parents:
diff changeset
1745 gimple *gs = gsi_stmt (gsi);
kono
parents:
diff changeset
1746
kono
parents:
diff changeset
1747 if (gimple_vuse (gs) && gimple_assign_single_p (gs))
kono
parents:
diff changeset
1748 slsr_process_ref (gs);
kono
parents:
diff changeset
1749
kono
parents:
diff changeset
1750 else if (is_gimple_assign (gs)
kono
parents:
diff changeset
1751 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))
kono
parents:
diff changeset
1752 || POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))))
kono
parents:
diff changeset
1753 {
kono
parents:
diff changeset
1754 tree rhs1 = NULL_TREE, rhs2 = NULL_TREE;
kono
parents:
diff changeset
1755
kono
parents:
diff changeset
1756 switch (gimple_assign_rhs_code (gs))
kono
parents:
diff changeset
1757 {
kono
parents:
diff changeset
1758 case MULT_EXPR:
kono
parents:
diff changeset
1759 case PLUS_EXPR:
kono
parents:
diff changeset
1760 rhs1 = gimple_assign_rhs1 (gs);
kono
parents:
diff changeset
1761 rhs2 = gimple_assign_rhs2 (gs);
kono
parents:
diff changeset
1762 /* Should never happen, but currently some buggy situations
kono
parents:
diff changeset
1763 in earlier phases put constants in rhs1. */
kono
parents:
diff changeset
1764 if (TREE_CODE (rhs1) != SSA_NAME)
kono
parents:
diff changeset
1765 continue;
kono
parents:
diff changeset
1766 break;
kono
parents:
diff changeset
1767
kono
parents:
diff changeset
1768 /* Possible future opportunity: rhs1 of a ptr+ can be
kono
parents:
diff changeset
1769 an ADDR_EXPR. */
kono
parents:
diff changeset
1770 case POINTER_PLUS_EXPR:
kono
parents:
diff changeset
1771 case MINUS_EXPR:
kono
parents:
diff changeset
1772 rhs2 = gimple_assign_rhs2 (gs);
kono
parents:
diff changeset
1773 gcc_fallthrough ();
kono
parents:
diff changeset
1774
kono
parents:
diff changeset
1775 CASE_CONVERT:
kono
parents:
diff changeset
1776 case SSA_NAME:
kono
parents:
diff changeset
1777 case NEGATE_EXPR:
kono
parents:
diff changeset
1778 rhs1 = gimple_assign_rhs1 (gs);
kono
parents:
diff changeset
1779 if (TREE_CODE (rhs1) != SSA_NAME)
kono
parents:
diff changeset
1780 continue;
kono
parents:
diff changeset
1781 break;
kono
parents:
diff changeset
1782
kono
parents:
diff changeset
1783 default:
kono
parents:
diff changeset
1784 ;
kono
parents:
diff changeset
1785 }
kono
parents:
diff changeset
1786
kono
parents:
diff changeset
1787 switch (gimple_assign_rhs_code (gs))
kono
parents:
diff changeset
1788 {
kono
parents:
diff changeset
1789 case MULT_EXPR:
kono
parents:
diff changeset
1790 slsr_process_mul (gs, rhs1, rhs2, speed);
kono
parents:
diff changeset
1791 break;
kono
parents:
diff changeset
1792
kono
parents:
diff changeset
1793 case PLUS_EXPR:
kono
parents:
diff changeset
1794 case POINTER_PLUS_EXPR:
kono
parents:
diff changeset
1795 case MINUS_EXPR:
kono
parents:
diff changeset
1796 slsr_process_add (gs, rhs1, rhs2, speed);
kono
parents:
diff changeset
1797 break;
kono
parents:
diff changeset
1798
kono
parents:
diff changeset
1799 case NEGATE_EXPR:
kono
parents:
diff changeset
1800 slsr_process_neg (gs, rhs1, speed);
kono
parents:
diff changeset
1801 break;
kono
parents:
diff changeset
1802
kono
parents:
diff changeset
1803 CASE_CONVERT:
kono
parents:
diff changeset
1804 slsr_process_cast (gs, rhs1, speed);
kono
parents:
diff changeset
1805 break;
kono
parents:
diff changeset
1806
kono
parents:
diff changeset
1807 case SSA_NAME:
kono
parents:
diff changeset
1808 slsr_process_copy (gs, rhs1, speed);
kono
parents:
diff changeset
1809 break;
kono
parents:
diff changeset
1810
kono
parents:
diff changeset
1811 default:
kono
parents:
diff changeset
1812 ;
kono
parents:
diff changeset
1813 }
kono
parents:
diff changeset
1814 }
kono
parents:
diff changeset
1815 }
kono
parents:
diff changeset
1816 return NULL;
kono
parents:
diff changeset
1817 }
kono
parents:
diff changeset
1818
kono
parents:
diff changeset
1819 /* Dump a candidate for debug. */
kono
parents:
diff changeset
1820
kono
parents:
diff changeset
1821 static void
kono
parents:
diff changeset
1822 dump_candidate (slsr_cand_t c)
kono
parents:
diff changeset
1823 {
kono
parents:
diff changeset
1824 fprintf (dump_file, "%3d [%d] ", c->cand_num,
kono
parents:
diff changeset
1825 gimple_bb (c->cand_stmt)->index);
kono
parents:
diff changeset
1826 print_gimple_stmt (dump_file, c->cand_stmt, 0);
kono
parents:
diff changeset
1827 switch (c->kind)
kono
parents:
diff changeset
1828 {
kono
parents:
diff changeset
1829 case CAND_MULT:
kono
parents:
diff changeset
1830 fputs (" MULT : (", dump_file);
kono
parents:
diff changeset
1831 print_generic_expr (dump_file, c->base_expr);
kono
parents:
diff changeset
1832 fputs (" + ", dump_file);
kono
parents:
diff changeset
1833 print_decs (c->index, dump_file);
kono
parents:
diff changeset
1834 fputs (") * ", dump_file);
kono
parents:
diff changeset
1835 if (TREE_CO