Line data Source code
1 : /* Straight-line strength reduction.
2 : Copyright (C) 2012-2026 Free Software Foundation, Inc.
3 : Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : /* There are many algorithms for performing strength reduction on
22 : loops. This is not one of them. IVOPTS handles strength reduction
23 : of induction variables just fine. This pass is intended to pick
24 : up the crumbs it leaves behind, by considering opportunities for
25 : strength reduction along dominator paths.
26 :
27 : Strength reduction addresses explicit multiplies, and certain
28 : multiplies implicit in addressing expressions. It would also be
29 : possible to apply strength reduction to divisions and modulos,
30 : but such opportunities are relatively uncommon.
31 :
32 : Strength reduction is also currently restricted to integer operations.
33 : If desired, it could be extended to floating-point operations under
34 : control of something like -funsafe-math-optimizations. */
35 :
36 : #include "config.h"
37 : #include "system.h"
38 : #include "coretypes.h"
39 : #include "backend.h"
40 : #include "rtl.h"
41 : #include "tree.h"
42 : #include "gimple.h"
43 : #include "cfghooks.h"
44 : #include "tree-pass.h"
45 : #include "ssa.h"
46 : #include "expmed.h"
47 : #include "gimple-pretty-print.h"
48 : #include "fold-const.h"
49 : #include "gimple-iterator.h"
50 : #include "gimplify-me.h"
51 : #include "stor-layout.h"
52 : #include "cfgloop.h"
53 : #include "tree-cfg.h"
54 : #include "domwalk.h"
55 : #include "tree-ssa-address.h"
56 : #include "tree-affine.h"
57 : #include "tree-eh.h"
58 : #include "builtins.h"
59 : #include "tree-ssa-dce.h"
60 : #include "gimple-fold.h"
61 :
62 : /* Information about a strength reduction candidate. Each statement
63 : in the candidate table represents an expression of one of the
64 : following forms (the special case of CAND_REF will be described
65 : later):
66 :
67 : (CAND_MULT) S1: X = (B + i) * S
68 : (CAND_ADD) S1: X = B + (i * S)
69 :
70 : Here X and B are SSA names, i is an integer constant, and S is
71 : either an SSA name or a constant. We call B the "base," i the
72 : "index", and S the "stride."
73 :
74 : Any statement S0 that dominates S1 and is of the form:
75 :
76 : (CAND_MULT) S0: Y = (B + i') * S
77 : (CAND_ADD) S0: Y = B + (i' * S)
78 :
79 : is called a "basis" for S1. In both cases, S1 may be replaced by
80 :
81 : S1': X = Y + (i - i') * S,
82 :
83 : where (i - i') * S is folded to the extent possible.
84 :
85 : All gimple statements are visited in dominator order, and each
86 : statement that may contribute to one of the forms of S1 above is
87 : given at least one entry in the candidate table. Such statements
88 : include addition, pointer addition, subtraction, multiplication,
89 : negation, copies, and nontrivial type casts. If a statement may
90 : represent more than one expression of the forms of S1 above,
91 : multiple "interpretations" are stored in the table and chained
92 : together. Examples:
93 :
94 : * An add of two SSA names may treat either operand as the base.
95 : * A multiply of two SSA names, likewise.
96 : * A copy or cast may be thought of as either a CAND_MULT with
97 : i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
98 :
99 : Candidate records are allocated from an obstack. They are addressed
100 : both from a hash table keyed on S1, and from a vector of candidate
101 : pointers arranged in predominator order.
102 :
103 : Opportunity note
104 : ----------------
105 : Currently we don't recognize:
106 :
107 : S0: Y = (S * i') - B
108 : S1: X = (S * i) - B
109 :
110 : as a strength reduction opportunity, even though this S1 would
111 : also be replaceable by the S1' above. This can be added if it
112 : comes up in practice.
113 :
114 : Strength reduction in addressing
115 : --------------------------------
116 : There is another kind of candidate known as CAND_REF. A CAND_REF
117 : describes a statement containing a memory reference having
118 : complex addressing that might benefit from strength reduction.
119 : Specifically, we are interested in references for which
120 : get_inner_reference returns a base address, offset, and bitpos as
121 : follows:
122 :
123 : base: MEM_REF (T1, C1)
124 : offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
125 : bitpos: C4 * BITS_PER_UNIT
126 :
127 : Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
128 : arbitrary integer constants. Note that C2 may be zero, in which
129 : case the offset will be MULT_EXPR (T2, C3).
130 :
131 : When this pattern is recognized, the original memory reference
132 : can be replaced with:
133 :
134 : MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
135 : C1 + (C2 * C3) + C4)
136 :
137 : which distributes the multiply to allow constant folding. When
138 : two or more addressing expressions can be represented by MEM_REFs
139 : of this form, differing only in the constants C1, C2, and C4,
140 : making this substitution produces more efficient addressing during
141 : the RTL phases. When there are not at least two expressions with
142 : the same values of T1, T2, and C3, there is nothing to be gained
143 : by the replacement.
144 :
145 : Strength reduction of CAND_REFs uses the same infrastructure as
146 : that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
147 : field, MULT_EXPR (T2, C3) in the stride (S) field, and
148 : C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
149 : is thus another CAND_REF with the same B and S values. When at
150 : least two CAND_REFs are chained together using the basis relation,
151 : each of them is replaced as above, resulting in improved code
152 : generation for addressing.
153 :
154 : Conditional candidates
155 : ======================
156 :
157 : Conditional candidates are best illustrated with an example.
158 : Consider the code sequence:
159 :
160 : (1) x_0 = ...;
161 : (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
162 : if (...)
163 : (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
164 : (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
165 : (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
166 : (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
167 :
168 : Here strength reduction is complicated by the uncertain value of x_2.
169 : A legitimate transformation is:
170 :
171 : (1) x_0 = ...;
172 : (2) a_0 = x_0 * 5;
173 : if (...)
174 : {
175 : (3) [x_1 = x_0 + 1;]
176 : (3a) t_1 = a_0 + 5;
177 : }
178 : (4) [x_2 = PHI <x_0, x_1>;]
179 : (4a) t_2 = PHI <a_0, t_1>;
180 : (5) [x_3 = x_2 + 1;]
181 : (6r) a_1 = t_2 + 5;
182 :
183 : where the bracketed instructions may go dead.
184 :
185 : To recognize this opportunity, we have to observe that statement (6)
186 : has a "hidden basis" (2). The hidden basis is unlike a normal basis
187 : in that the statement and the hidden basis have different base SSA
188 : names (x_2 and x_0, respectively). The relationship is established
189 : when a statement's base name (x_2) is defined by a phi statement (4),
190 : each argument of which (x_0, x_1) has an identical "derived base name."
191 : If the argument is defined by a candidate (as x_1 is by (3)) that is a
192 : CAND_ADD having a stride of 1, the derived base name of the argument is
193 : the base name of the candidate (x_0). Otherwise, the argument itself
194 : is its derived base name (as is the case with argument x_0).
195 :
196 : The hidden basis for statement (6) is the nearest dominating candidate
197 : whose base name is the derived base name (x_0) of the feeding phi (4),
198 : and whose stride is identical to that of the statement. We can then
199 : create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
200 : allowing the final replacement of (6) by the strength-reduced (6r).
201 :
202 : To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
203 : A CAND_PHI is not a candidate for replacement, but is maintained in the
204 : candidate table to ease discovery of hidden bases. Any phi statement
205 : whose arguments share a common derived base name is entered into the
206 : table with the derived base name, an (arbitrary) index of zero, and a
207 : stride of 1. A statement with a hidden basis can then be detected by
208 : simply looking up its feeding phi definition in the candidate table,
209 : extracting the derived base name, and searching for a basis in the
210 : usual manner after substituting the derived base name.
211 :
212 : Note that the transformation is only valid when the original phi and
213 : the statements that define the phi's arguments are all at the same
214 : position in the loop hierarchy. */
215 :
216 :
217 : /* Index into the candidate vector, offset by 1. VECs are zero-based,
218 : while cand_idx's are one-based, with zero indicating null. */
219 : typedef unsigned cand_idx;
220 :
221 : /* The kind of candidate. */
222 : enum cand_kind
223 : {
224 : CAND_MULT,
225 : CAND_ADD,
226 : CAND_REF,
227 : CAND_PHI
228 : };
229 :
230 : class slsr_cand_d
231 : {
232 : public:
233 : /* The candidate statement S1. */
234 : gimple *cand_stmt;
235 :
236 : /* The base expression B: often an SSA name, but not always. */
237 : tree base_expr;
238 :
239 : /* The stride S. */
240 : tree stride;
241 :
242 : /* The index constant i. */
243 : offset_int index;
244 :
245 : /* The type of the candidate. This is normally the type of base_expr,
246 : but casts may have occurred when combining feeding instructions.
247 : A candidate can only be a basis for candidates of the same final type.
248 : (For CAND_REFs, this is the type to be used for operand 1 of the
249 : replacement MEM_REF.) */
250 : tree cand_type;
251 :
252 : /* The type to be used to interpret the stride field when the stride
253 : is not a constant. Normally the same as the type of the recorded
254 : stride, but when the stride has been cast we need to maintain that
255 : knowledge in order to make legal substitutions without losing
256 : precision. When the stride is a constant, this will be sizetype. */
257 : tree stride_type;
258 :
259 : /* The kind of candidate (CAND_MULT, etc.). */
260 : enum cand_kind kind;
261 :
262 : /* Index of this candidate in the candidate vector. */
263 : cand_idx cand_num;
264 :
265 : /* Index of the next candidate record for the same statement.
266 : A statement may be useful in more than one way (e.g., due to
267 : commutativity). So we can have multiple "interpretations"
268 : of a statement. */
269 : cand_idx next_interp;
270 :
271 : /* Index of the first candidate record in a chain for the same
272 : statement. */
273 : cand_idx first_interp;
274 :
275 : /* Index of the basis statement S0, if any, in the candidate vector. */
276 : cand_idx basis;
277 :
278 : /* First candidate for which this candidate is a basis, if one exists. */
279 : cand_idx dependent;
280 :
281 : /* Next candidate having the same basis as this one. */
282 : cand_idx sibling;
283 :
284 : /* If this is a conditional candidate, the CAND_PHI candidate
285 : that defines the base SSA name B. */
286 : cand_idx def_phi;
287 :
288 : /* Savings that can be expected from eliminating dead code if this
289 : candidate is replaced. */
290 : int dead_savings;
291 :
292 : /* For PHI candidates, use a visited flag to keep from processing the
293 : same PHI twice from multiple paths. */
294 : int visited;
295 :
296 : /* We sometimes have to cache a phi basis with a phi candidate to
297 : avoid processing it twice. Valid only if visited==1. */
298 : tree cached_basis;
299 : };
300 :
301 : typedef class slsr_cand_d slsr_cand, *slsr_cand_t;
302 : typedef const class slsr_cand_d *const_slsr_cand_t;
303 :
304 : /* Pointers to candidates are chained together as part of a mapping
305 : from base expressions to the candidates that use them. */
306 :
307 : struct cand_chain_d
308 : {
309 : /* Base expression for the chain of candidates: often, but not
310 : always, an SSA name. */
311 : tree base_expr;
312 :
313 : /* Pointer to a candidate. */
314 : slsr_cand_t cand;
315 :
316 : /* Chain pointer. */
317 : struct cand_chain_d *next;
318 :
319 : };
320 :
321 : typedef struct cand_chain_d cand_chain, *cand_chain_t;
322 : typedef const struct cand_chain_d *const_cand_chain_t;
323 :
324 : /* Information about a unique "increment" associated with candidates
325 : having an SSA name for a stride. An increment is the difference
326 : between the index of the candidate and the index of its basis,
327 : i.e., (i - i') as discussed in the module commentary.
328 :
329 : When we are not going to generate address arithmetic we treat
330 : increments that differ only in sign as the same, allowing sharing
331 : of the cost of initializers. The absolute value of the increment
332 : is stored in the incr_info. */
333 :
334 : class incr_info_d
335 : {
336 : public:
337 : /* The increment that relates a candidate to its basis. */
338 : offset_int incr;
339 :
340 : /* How many times the increment occurs in the candidate tree. */
341 : unsigned count;
342 :
343 : /* Cost of replacing candidates using this increment. Negative and
344 : zero costs indicate replacement should be performed. */
345 : int cost;
346 :
347 : /* If this increment is profitable but is not -1, 0, or 1, it requires
348 : an initializer T_0 = stride * incr to be found or introduced in the
349 : nearest common dominator of all candidates. This field holds T_0
350 : for subsequent use. */
351 : tree initializer;
352 :
353 : /* If the initializer was found to already exist, this is the block
354 : where it was found. */
355 : basic_block init_bb;
356 : };
357 :
358 : typedef class incr_info_d incr_info, *incr_info_t;
359 :
360 : /* Candidates are maintained in a vector. If candidate X dominates
361 : candidate Y, then X appears before Y in the vector; but the
362 : converse does not necessarily hold. */
363 : static vec<slsr_cand_t> cand_vec;
364 :
365 : enum cost_consts
366 : {
367 : COST_NEUTRAL = 0,
368 : COST_INFINITE = 1000
369 : };
370 :
371 : enum stride_status
372 : {
373 : UNKNOWN_STRIDE = 0,
374 : KNOWN_STRIDE = 1
375 : };
376 :
377 : enum phi_adjust_status
378 : {
379 : NOT_PHI_ADJUST = 0,
380 : PHI_ADJUST = 1
381 : };
382 :
383 : enum count_phis_status
384 : {
385 : DONT_COUNT_PHIS = 0,
386 : COUNT_PHIS = 1
387 : };
388 :
389 : /* Constrain how many PHI nodes we will visit for a conditional
390 : candidate (depth and breadth). */
391 : const int MAX_SPREAD = 16;
392 :
393 : /* Pointer map embodying a mapping from statements to candidates. */
394 : static hash_map<gimple *, slsr_cand_t> *stmt_cand_map;
395 :
396 : /* Obstack for candidates. */
397 : static struct obstack cand_obstack;
398 :
399 : /* Obstack for candidate chains. */
400 : static struct obstack chain_obstack;
401 :
402 : /* An array INCR_VEC of incr_infos is used during analysis of related
403 : candidates having an SSA name for a stride. INCR_VEC_LEN describes
404 : its current length. MAX_INCR_VEC_LEN is used to avoid costly
405 : pathological cases. */
406 : static incr_info_t incr_vec;
407 : static unsigned incr_vec_len;
408 : const int MAX_INCR_VEC_LEN = 16;
409 :
410 : /* For a chain of candidates with unknown stride, indicates whether or not
411 : we must generate pointer arithmetic when replacing statements. */
412 : static bool address_arithmetic_p;
413 :
414 : /* Forward function declarations. */
415 : static slsr_cand_t base_cand_from_table (tree);
416 : static tree introduce_cast_before_cand (slsr_cand_t, tree, tree);
417 : static bool legal_cast_p_1 (tree, tree);
418 :
419 : /* Produce a pointer to the IDX'th candidate in the candidate vector. */
420 :
421 : static slsr_cand_t
422 8074878 : lookup_cand (cand_idx idx)
423 : {
424 0 : return cand_vec[idx];
425 : }
426 :
427 : /* Helper for hashing a candidate chain header. */
428 :
429 : struct cand_chain_hasher : nofree_ptr_hash <cand_chain>
430 : {
431 : static inline hashval_t hash (const cand_chain *);
432 : static inline bool equal (const cand_chain *, const cand_chain *);
433 : };
434 :
435 : inline hashval_t
436 32076131 : cand_chain_hasher::hash (const cand_chain *p)
437 : {
438 32076131 : tree base_expr = p->base_expr;
439 32076131 : return iterative_hash_expr (base_expr, 0);
440 : }
441 :
442 : inline bool
443 25779963 : cand_chain_hasher::equal (const cand_chain *chain1, const cand_chain *chain2)
444 : {
445 25779963 : return operand_equal_p (chain1->base_expr, chain2->base_expr, 0);
446 : }
447 :
448 : /* Hash table embodying a mapping from base exprs to chains of candidates. */
449 : static hash_table<cand_chain_hasher> *base_cand_map;
450 :
451 : /* Pointer map used by tree_to_aff_combination_expand. */
452 : static hash_map<tree, name_expansion *> *name_expansions;
453 : /* Pointer map embodying a mapping from bases to alternative bases. */
454 : static hash_map<tree, tree> *alt_base_map;
455 :
456 : /* Given BASE, use the tree affine combiniation facilities to
457 : find the underlying tree expression for BASE, with any
458 : immediate offset excluded.
459 :
460 : N.B. we should eliminate this backtracking with better forward
461 : analysis in a future release. */
462 :
463 : static tree
464 60856 : get_alternative_base (tree base)
465 : {
466 60856 : tree *result = alt_base_map->get (base);
467 :
468 60856 : if (result == NULL)
469 : {
470 10229 : tree expr;
471 10229 : aff_tree aff;
472 :
473 10229 : tree_to_aff_combination_expand (base, TREE_TYPE (base),
474 : &aff, &name_expansions);
475 10229 : aff.offset = 0;
476 10229 : expr = aff_combination_to_tree (&aff);
477 :
478 20322 : bool existed = alt_base_map->put (base, base == expr ? NULL : expr);
479 10229 : gcc_assert (!existed);
480 :
481 10229 : return expr == base ? NULL : expr;
482 10229 : }
483 :
484 50627 : return *result;
485 : }
486 :
487 : /* Look in the candidate table for a CAND_PHI that defines BASE and
488 : return it if found; otherwise return NULL. */
489 :
490 : static cand_idx
491 2456850 : find_phi_def (tree base)
492 : {
493 2456850 : slsr_cand_t c;
494 :
495 2456850 : if (TREE_CODE (base) != SSA_NAME)
496 : return 0;
497 :
498 2456850 : c = base_cand_from_table (base);
499 :
500 173401 : if (!c || c->kind != CAND_PHI
501 2457743 : || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (c->cand_stmt)))
502 : return 0;
503 :
504 888 : return c->cand_num;
505 : }
506 :
507 : /* Determine whether all uses of NAME are directly or indirectly
508 : used by STMT. That is, we want to know whether if STMT goes
509 : dead, the definition of NAME also goes dead. */
510 : static bool
511 203705 : uses_consumed_by_stmt (tree name, gimple *stmt, unsigned recurse = 0)
512 : {
513 203705 : gimple *use_stmt;
514 203705 : imm_use_iterator iter;
515 203705 : bool retval = true;
516 :
517 594681 : FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
518 : {
519 294697 : if (use_stmt == stmt || is_gimple_debug (use_stmt))
520 184363 : continue;
521 :
522 110334 : if (!is_gimple_assign (use_stmt)
523 38750 : || !gimple_get_lhs (use_stmt)
524 38750 : || !is_gimple_reg (gimple_get_lhs (use_stmt))
525 32961 : || recurse >= 10
526 143255 : || !uses_consumed_by_stmt (gimple_get_lhs (use_stmt), stmt,
527 : recurse + 1))
528 : {
529 : retval = false;
530 : break;
531 : }
532 203705 : }
533 :
534 203705 : return retval;
535 : }
536 :
537 : /* Helper routine for find_basis_for_candidate. May be called twice:
538 : once for the candidate's base expr, and optionally again either for
539 : the candidate's phi definition or for a CAND_REF's alternative base
540 : expression. */
541 :
542 : static slsr_cand_t
543 7951100 : find_basis_for_base_expr (slsr_cand_t c, tree base_expr)
544 : {
545 7951100 : cand_chain mapping_key;
546 7951100 : cand_chain_t chain;
547 7951100 : slsr_cand_t basis = NULL;
548 :
549 : // Limit potential of N^2 behavior for long candidate chains.
550 7951100 : int iters = 0;
551 7951100 : int max_iters = param_max_slsr_candidate_scan;
552 :
553 7951100 : mapping_key.base_expr = base_expr;
554 7951100 : chain = base_cand_map->find (&mapping_key);
555 :
556 31836321 : for (; chain && iters < max_iters; chain = chain->next, ++iters)
557 : {
558 23885221 : slsr_cand_t one_basis = chain->cand;
559 :
560 42991157 : if (one_basis->kind != c->kind
561 14150242 : || one_basis->cand_stmt == c->cand_stmt
562 14149532 : || !operand_equal_p (one_basis->stride, c->stride, 0)
563 7915245 : || !types_compatible_p (one_basis->cand_type, c->cand_type)
564 6651018 : || !types_compatible_p (one_basis->stride_type, c->stride_type)
565 30536227 : || !dominated_by_p (CDI_DOMINATORS,
566 6651006 : gimple_bb (c->cand_stmt),
567 6651006 : gimple_bb (one_basis->cand_stmt)))
568 19105936 : continue;
569 :
570 4779285 : tree lhs = gimple_assign_lhs (one_basis->cand_stmt);
571 4779285 : if (lhs && TREE_CODE (lhs) == SSA_NAME
572 9538741 : && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
573 34 : continue;
574 :
575 4779251 : if (!basis || basis->cand_num < one_basis->cand_num)
576 23885221 : basis = one_basis;
577 : }
578 :
579 7951100 : return basis;
580 : }
581 :
582 : /* Use the base expr from candidate C to look for possible candidates
583 : that can serve as a basis for C. Each potential basis must also
584 : appear in a block that dominates the candidate statement and have
585 : the same stride and type. If more than one possible basis exists,
586 : the one with highest index in the vector is chosen; this will be
587 : the most immediately dominating basis. */
588 :
589 : static int
590 7950167 : find_basis_for_candidate (slsr_cand_t c)
591 : {
592 7950167 : slsr_cand_t basis = find_basis_for_base_expr (c, c->base_expr);
593 :
594 : /* If a candidate doesn't have a basis using its base expression,
595 : it may have a basis hidden by one or more intervening phis. */
596 7950167 : if (!basis && c->def_phi)
597 : {
598 769 : basic_block basis_bb, phi_bb;
599 769 : slsr_cand_t phi_cand = lookup_cand (c->def_phi);
600 769 : basis = find_basis_for_base_expr (c, phi_cand->base_expr);
601 :
602 769 : if (basis)
603 : {
604 : /* A hidden basis must dominate the phi-definition of the
605 : candidate's base name. */
606 71 : phi_bb = gimple_bb (phi_cand->cand_stmt);
607 71 : basis_bb = gimple_bb (basis->cand_stmt);
608 :
609 71 : if (phi_bb == basis_bb
610 71 : || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
611 : {
612 8 : basis = NULL;
613 8 : c->basis = 0;
614 : }
615 :
616 : /* If we found a hidden basis, estimate additional dead-code
617 : savings if the phi and its feeding statements can be removed. */
618 71 : tree feeding_var = gimple_phi_result (phi_cand->cand_stmt);
619 71 : if (basis && uses_consumed_by_stmt (feeding_var, c->cand_stmt))
620 26 : c->dead_savings += phi_cand->dead_savings;
621 : }
622 : }
623 :
624 7950167 : if (flag_expensive_optimizations && !basis && c->kind == CAND_REF)
625 : {
626 23304 : tree alt_base_expr = get_alternative_base (c->base_expr);
627 23304 : if (alt_base_expr)
628 164 : basis = find_basis_for_base_expr (c, alt_base_expr);
629 : }
630 :
631 6791842 : if (basis)
632 : {
633 1282959 : c->sibling = basis->dependent;
634 1282959 : basis->dependent = c->cand_num;
635 1282959 : return basis->cand_num;
636 : }
637 :
638 : return 0;
639 : }
640 :
641 : /* Record a mapping from BASE to C, indicating that C may potentially serve
642 : as a basis using that base expression. BASE may be the same as
643 : C->BASE_EXPR; alternatively BASE can be a different tree that share the
644 : underlining expression of C->BASE_EXPR. */
645 :
646 : static void
647 7962045 : record_potential_basis (slsr_cand_t c, tree base)
648 : {
649 7962045 : cand_chain_t node;
650 7962045 : cand_chain **slot;
651 :
652 7962045 : gcc_assert (base);
653 :
654 7962045 : node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain));
655 7962045 : node->base_expr = base;
656 7962045 : node->cand = c;
657 7962045 : node->next = NULL;
658 7962045 : slot = base_cand_map->find_slot (node, INSERT);
659 :
660 7962045 : if (*slot)
661 : {
662 3881488 : cand_chain_t head = (cand_chain_t) (*slot);
663 3881488 : node->next = head->next;
664 3881488 : head->next = node;
665 : }
666 : else
667 4080557 : *slot = node;
668 7962045 : }
669 :
670 : /* Allocate storage for a new candidate and initialize its fields.
671 : Attempt to find a basis for the candidate.
672 :
673 : For CAND_REF, an alternative base may also be recorded and used
674 : to find a basis. This helps cases where the expression hidden
675 : behind BASE (which is usually an SSA_NAME) has immediate offset,
676 : e.g.
677 :
678 : a2[i][j] = 1;
679 : a2[i + 20][j] = 2; */
680 :
681 : static slsr_cand_t
682 7961821 : alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base,
683 : const offset_int &index, tree stride, tree ctype,
684 : tree stype, unsigned savings)
685 : {
686 7961821 : slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack,
687 : sizeof (slsr_cand));
688 7961821 : c->cand_stmt = gs;
689 7961821 : c->base_expr = base;
690 7961821 : c->stride = stride;
691 7961821 : c->index = index;
692 7961821 : c->cand_type = ctype;
693 7961821 : c->stride_type = stype;
694 7961821 : c->kind = kind;
695 7961821 : c->cand_num = cand_vec.length ();
696 7961821 : c->next_interp = 0;
697 7961821 : c->first_interp = c->cand_num;
698 7961821 : c->dependent = 0;
699 7961821 : c->sibling = 0;
700 7961821 : c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;
701 7961821 : c->dead_savings = savings;
702 7961821 : c->visited = 0;
703 7961821 : c->cached_basis = NULL_TREE;
704 :
705 7961821 : cand_vec.safe_push (c);
706 :
707 7961821 : if (kind == CAND_PHI)
708 11654 : c->basis = 0;
709 : else
710 7950167 : c->basis = find_basis_for_candidate (c);
711 :
712 7961821 : record_potential_basis (c, base);
713 7961821 : if (flag_expensive_optimizations && kind == CAND_REF)
714 : {
715 37552 : tree alt_base = get_alternative_base (base);
716 37552 : if (alt_base)
717 224 : record_potential_basis (c, alt_base);
718 : }
719 :
720 7961821 : return c;
721 : }
722 :
723 : /* Determine the target cost of statement GS when compiling according
724 : to SPEED. */
725 :
726 : static int
727 1350724 : stmt_cost (gimple *gs, bool speed)
728 : {
729 1350724 : tree lhs, rhs1, rhs2;
730 1350724 : machine_mode lhs_mode;
731 :
732 1350724 : gcc_assert (is_gimple_assign (gs));
733 1350724 : lhs = gimple_assign_lhs (gs);
734 1350724 : rhs1 = gimple_assign_rhs1 (gs);
735 1350724 : lhs_mode = TYPE_MODE (TREE_TYPE (lhs));
736 :
737 1350724 : switch (gimple_assign_rhs_code (gs))
738 : {
739 388028 : case MULT_EXPR:
740 388028 : rhs2 = gimple_assign_rhs2 (gs);
741 :
742 388028 : if (tree_fits_shwi_p (rhs2))
743 318595 : return mult_by_coeff_cost (tree_to_shwi (rhs2), lhs_mode, speed);
744 :
745 69433 : gcc_assert (TREE_CODE (rhs1) != INTEGER_CST);
746 69433 : return mul_cost (speed, lhs_mode);
747 :
748 240991 : case PLUS_EXPR:
749 240991 : case POINTER_PLUS_EXPR:
750 240991 : case MINUS_EXPR:
751 240991 : return add_cost (speed, lhs_mode);
752 :
753 10657 : case NEGATE_EXPR:
754 10657 : return neg_cost (speed, lhs_mode);
755 :
756 676449 : CASE_CONVERT:
757 1352898 : return convert_cost (lhs_mode, TYPE_MODE (TREE_TYPE (rhs1)), speed);
758 :
759 : /* Note that we don't assign costs to copies that in most cases
760 : will go away. */
761 : case SSA_NAME:
762 : return 0;
763 :
764 0 : default:
765 0 : ;
766 : }
767 :
768 0 : gcc_unreachable ();
769 : }
770 :
771 : /* Look up the defining statement for BASE_IN and return a pointer
772 : to its candidate in the candidate table, if any; otherwise NULL.
773 : Only CAND_ADD and CAND_MULT candidates are returned. */
774 :
775 : static slsr_cand_t
776 15249721 : base_cand_from_table (tree base_in)
777 : {
778 15249721 : slsr_cand_t *result;
779 :
780 15249721 : gimple *def = SSA_NAME_DEF_STMT (base_in);
781 15249721 : if (!def)
782 : return (slsr_cand_t) NULL;
783 :
784 15249721 : result = stmt_cand_map->get (def);
785 :
786 15249721 : if (result && (*result)->kind != CAND_REF)
787 : return *result;
788 :
789 : return (slsr_cand_t) NULL;
790 : }
791 :
792 : /* Add an entry to the statement-to-candidate mapping. */
793 :
794 : static void
795 5764641 : add_cand_for_stmt (gimple *gs, slsr_cand_t c)
796 : {
797 5764641 : bool existed = stmt_cand_map->put (gs, c);
798 5764641 : gcc_assert (!existed);
799 5764641 : }
800 :
801 : /* Given PHI which contains a phi statement, determine whether it
802 : satisfies all the requirements of a phi candidate. If so, create
803 : a candidate. Note that a CAND_PHI never has a basis itself, but
804 : is used to help find a basis for subsequent candidates. */
805 :
806 : static void
807 4435189 : slsr_process_phi (gphi *phi, bool speed)
808 : {
809 4435189 : unsigned i;
810 4435189 : tree arg0_base = NULL_TREE, base_type;
811 4435189 : slsr_cand_t c;
812 4435189 : class loop *cand_loop = gimple_bb (phi)->loop_father;
813 4435189 : unsigned savings = 0;
814 :
815 : /* A CAND_PHI requires each of its arguments to have the same
816 : derived base name. (See the module header commentary for a
817 : definition of derived base names.) Furthermore, all feeding
818 : definitions must be in the same position in the loop hierarchy
819 : as PHI. */
820 :
821 4700690 : for (i = 0; i < gimple_phi_num_args (phi); i++)
822 : {
823 4689036 : slsr_cand_t arg_cand;
824 4689036 : tree arg = gimple_phi_arg_def (phi, i);
825 4689036 : tree derived_base_name = NULL_TREE;
826 4689036 : gimple *arg_stmt = NULL;
827 4689036 : basic_block arg_bb = NULL;
828 :
829 4689036 : if (TREE_CODE (arg) != SSA_NAME)
830 : return;
831 :
832 4267527 : arg_cand = base_cand_from_table (arg);
833 :
834 4267527 : if (arg_cand)
835 : {
836 317419 : while (arg_cand->kind != CAND_ADD && arg_cand->kind != CAND_PHI)
837 : {
838 30557 : if (!arg_cand->next_interp)
839 : return;
840 :
841 4019 : arg_cand = lookup_cand (arg_cand->next_interp);
842 : }
843 :
844 286862 : if (!integer_onep (arg_cand->stride))
845 : return;
846 :
847 170692 : derived_base_name = arg_cand->base_expr;
848 170692 : arg_stmt = arg_cand->cand_stmt;
849 170692 : arg_bb = gimple_bb (arg_stmt);
850 :
851 : /* Gather potential dead code savings if the phi statement
852 : can be removed later on. */
853 170692 : if (uses_consumed_by_stmt (arg, phi))
854 : {
855 93322 : if (gimple_code (arg_stmt) == GIMPLE_PHI)
856 2442 : savings += arg_cand->dead_savings;
857 : else
858 90880 : savings += stmt_cost (arg_stmt, speed);
859 : }
860 : }
861 3954127 : else if (SSA_NAME_IS_DEFAULT_DEF (arg))
862 : {
863 184496 : derived_base_name = arg;
864 184496 : arg_bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
865 : }
866 :
867 355188 : if (!arg_bb || arg_bb->loop_father != cand_loop)
868 3843755 : return;
869 :
870 281064 : if (i == 0)
871 : arg0_base = derived_base_name;
872 47538 : else if (!operand_equal_p (derived_base_name, arg0_base, 0))
873 : return;
874 : }
875 :
876 : /* Create the candidate. "alloc_cand_and_find_basis" is named
877 : misleadingly for this case, as no basis will be sought for a
878 : CAND_PHI. */
879 11654 : base_type = TREE_TYPE (arg0_base);
880 :
881 34962 : c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base,
882 11654 : 0, integer_one_node, base_type,
883 : sizetype, savings);
884 :
885 : /* Add the candidate to the statement-candidate mapping. */
886 11654 : add_cand_for_stmt (phi, c);
887 : }
888 :
889 : /* Given PBASE which is a pointer to tree, look up the defining
890 : statement for it and check whether the candidate is in the
891 : form of:
892 :
893 : X = B + (1 * S), S is integer constant
894 : X = B + (i * S), S is integer one
895 :
896 : If so, set PBASE to the candidate's base_expr and return double
897 : int (i * S).
898 : Otherwise, just return double int zero. */
899 :
900 : static offset_int
901 49675 : backtrace_base_for_ref (tree *pbase)
902 : {
903 49675 : tree base_in = *pbase;
904 49675 : slsr_cand_t base_cand;
905 :
906 49675 : STRIP_NOPS (base_in);
907 :
908 : /* Strip off widening conversion(s) to handle cases where
909 : e.g. 'B' is widened from an 'int' in order to calculate
910 : a 64-bit address. */
911 46908 : if (CONVERT_EXPR_P (base_in)
912 52442 : && legal_cast_p_1 (TREE_TYPE (base_in),
913 2767 : TREE_TYPE (TREE_OPERAND (base_in, 0))))
914 2115 : base_in = get_unwidened (base_in, NULL_TREE);
915 :
916 49675 : if (TREE_CODE (base_in) != SSA_NAME)
917 1803 : return 0;
918 :
919 47872 : base_cand = base_cand_from_table (base_in);
920 :
921 121397 : while (base_cand && base_cand->kind != CAND_PHI)
922 : {
923 50433 : if (base_cand->kind == CAND_ADD
924 49258 : && base_cand->index == 1
925 79690 : && TREE_CODE (base_cand->stride) == INTEGER_CST)
926 : {
927 : /* X = B + (1 * S), S is integer constant. */
928 5281 : *pbase = base_cand->base_expr;
929 5281 : return wi::to_offset (base_cand->stride);
930 : }
931 45152 : else if (base_cand->kind == CAND_ADD
932 43977 : && TREE_CODE (base_cand->stride) == INTEGER_CST
933 64651 : && integer_onep (base_cand->stride))
934 : {
935 : /* X = B + (i * S), S is integer one. */
936 19499 : *pbase = base_cand->base_expr;
937 19499 : return base_cand->index;
938 : }
939 :
940 25653 : base_cand = lookup_cand (base_cand->next_interp);
941 : }
942 :
943 23092 : return 0;
944 : }
945 :
946 : /* Look for the following pattern:
947 :
948 : *PBASE: MEM_REF (T1, C1)
949 :
950 : *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
951 : or
952 : MULT_EXPR (PLUS_EXPR (T2, C2), C3)
953 : or
954 : MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
955 :
956 : *PINDEX: C4 * BITS_PER_UNIT
957 :
958 : If not present, leave the input values unchanged and return FALSE.
959 : Otherwise, modify the input values as follows and return TRUE:
960 :
961 : *PBASE: T1
962 : *POFFSET: MULT_EXPR (T2, C3)
963 : *PINDEX: C1 + (C2 * C3) + C4
964 :
965 : When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
966 : will be further restructured to:
967 :
968 : *PBASE: T1
969 : *POFFSET: MULT_EXPR (T2', C3)
970 : *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
971 :
972 : static bool
973 5505545 : restructure_reference (tree *pbase, tree *poffset, offset_int *pindex,
974 : tree *ptype)
975 : {
976 5505545 : tree base = *pbase, offset = *poffset;
977 5505545 : offset_int index = *pindex;
978 5505545 : tree mult_op0, t1, t2, type;
979 5505545 : offset_int c1, c2, c3, c4, c5;
980 5505545 : offset_int mem_offset;
981 :
982 5505545 : if (!base
983 5505545 : || !offset
984 202460 : || TREE_CODE (base) != MEM_REF
985 79148 : || !mem_ref_offset (base).is_constant (&mem_offset)
986 79148 : || TREE_CODE (offset) != MULT_EXPR
987 50269 : || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
988 5555812 : || wi::umod_floor (index, BITS_PER_UNIT) != 0)
989 5455278 : return false;
990 :
991 50267 : t1 = TREE_OPERAND (base, 0);
992 50267 : c1 = offset_int::from (mem_offset, SIGNED);
993 50267 : type = TREE_TYPE (TREE_OPERAND (base, 1));
994 :
995 50267 : mult_op0 = TREE_OPERAND (offset, 0);
996 50267 : c3 = wi::to_offset (TREE_OPERAND (offset, 1));
997 :
998 50267 : if (TREE_CODE (mult_op0) == PLUS_EXPR)
999 :
1000 3716 : if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
1001 : {
1002 3124 : t2 = TREE_OPERAND (mult_op0, 0);
1003 3124 : c2 = wi::to_offset (TREE_OPERAND (mult_op0, 1));
1004 : }
1005 : else
1006 : return false;
1007 :
1008 46551 : else if (TREE_CODE (mult_op0) == MINUS_EXPR)
1009 :
1010 0 : if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
1011 : {
1012 0 : t2 = TREE_OPERAND (mult_op0, 0);
1013 0 : c2 = -wi::to_offset (TREE_OPERAND (mult_op0, 1));
1014 : }
1015 : else
1016 : return false;
1017 :
1018 : else
1019 : {
1020 46551 : t2 = mult_op0;
1021 46551 : c2 = 0;
1022 : }
1023 :
1024 49675 : c4 = index >> LOG2_BITS_PER_UNIT;
1025 49675 : c5 = backtrace_base_for_ref (&t2);
1026 :
1027 49675 : *pbase = t1;
1028 49675 : *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2),
1029 : wide_int_to_tree (sizetype, c3));
1030 49675 : *pindex = c1 + c2 * c3 + c4 + c5 * c3;
1031 49675 : *ptype = type;
1032 :
1033 49675 : return true;
1034 : }
1035 :
1036 : /* Given GS which contains a data reference, create a CAND_REF entry in
1037 : the candidate table and attempt to find a basis. */
1038 :
1039 : static void
1040 12241872 : slsr_process_ref (gimple *gs)
1041 : {
1042 12241872 : tree ref_expr, base, offset, type;
1043 12241872 : poly_int64 bitsize, bitpos;
1044 12241872 : machine_mode mode;
1045 12241872 : int unsignedp, reversep, volatilep;
1046 12241872 : slsr_cand_t c;
1047 :
1048 24483744 : if (gimple_vdef (gs))
1049 6883677 : ref_expr = gimple_assign_lhs (gs);
1050 : else
1051 5358195 : ref_expr = gimple_assign_rhs1 (gs);
1052 :
1053 12241872 : if (!handled_component_p (ref_expr)
1054 5605132 : || TREE_CODE (ref_expr) == BIT_FIELD_REF
1055 5577460 : || (TREE_CODE (ref_expr) == COMPONENT_REF
1056 4826440 : && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1))))
1057 12192197 : return;
1058 :
1059 5506184 : base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode,
1060 : &unsignedp, &reversep, &volatilep);
1061 5506184 : HOST_WIDE_INT cbitpos;
1062 5506184 : if (reversep || !bitpos.is_constant (&cbitpos))
1063 : return;
1064 5505545 : offset_int index = cbitpos;
1065 :
1066 5505545 : if (!restructure_reference (&base, &offset, &index, &type))
1067 : return;
1068 :
1069 49675 : c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset,
1070 : type, sizetype, 0);
1071 :
1072 : /* Add the candidate to the statement-candidate mapping. */
1073 49675 : add_cand_for_stmt (gs, c);
1074 : }
1075 :
1076 : /* Create a candidate entry for a statement GS, where GS multiplies
1077 : two SSA names BASE_IN and STRIDE_IN. Propagate any known information
1078 : about the two SSA names into the new candidate. Return the new
1079 : candidate. */
1080 :
1081 : static slsr_cand_t
1082 293778 : create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
1083 : {
1084 293778 : tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
1085 293778 : tree stype = NULL_TREE;
1086 293778 : offset_int index;
1087 293778 : unsigned savings = 0;
1088 293778 : slsr_cand_t c;
1089 293778 : slsr_cand_t base_cand = base_cand_from_table (base_in);
1090 :
1091 : /* Look at all interpretations of the base candidate, if necessary,
1092 : to find information to propagate into this candidate. */
1093 700267 : while (base_cand && !base && base_cand->kind != CAND_PHI)
1094 : {
1095 :
1096 112711 : if (base_cand->kind == CAND_MULT && integer_onep (base_cand->stride))
1097 : {
1098 : /* Y = (B + i') * 1
1099 : X = Y * Z
1100 : ================
1101 : X = (B + i') * Z */
1102 263 : base = base_cand->base_expr;
1103 263 : index = base_cand->index;
1104 263 : stride = stride_in;
1105 263 : ctype = base_cand->cand_type;
1106 263 : stype = TREE_TYPE (stride_in);
1107 263 : if (has_single_use (base_in))
1108 482 : savings = (base_cand->dead_savings
1109 241 : + stmt_cost (base_cand->cand_stmt, speed));
1110 : }
1111 112448 : else if (base_cand->kind == CAND_ADD
1112 96318 : && TREE_CODE (base_cand->stride) == INTEGER_CST)
1113 : {
1114 : /* Y = B + (i' * S), S constant
1115 : X = Y * Z
1116 : ============================
1117 : X = B + ((i' * S) * Z) */
1118 68243 : base = base_cand->base_expr;
1119 68243 : index = base_cand->index * wi::to_offset (base_cand->stride);
1120 68243 : stride = stride_in;
1121 68243 : ctype = base_cand->cand_type;
1122 68243 : stype = TREE_TYPE (stride_in);
1123 68243 : if (has_single_use (base_in))
1124 92454 : savings = (base_cand->dead_savings
1125 46227 : + stmt_cost (base_cand->cand_stmt, speed));
1126 : }
1127 :
1128 112711 : base_cand = lookup_cand (base_cand->next_interp);
1129 : }
1130 :
1131 293778 : if (!base)
1132 : {
1133 : /* No interpretations had anything useful to propagate, so
1134 : produce X = (Y + 0) * Z. */
1135 225272 : base = base_in;
1136 225272 : index = 0;
1137 225272 : stride = stride_in;
1138 225272 : ctype = TREE_TYPE (base_in);
1139 225272 : stype = TREE_TYPE (stride_in);
1140 : }
1141 :
1142 293778 : c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
1143 : ctype, stype, savings);
1144 293778 : return c;
1145 : }
1146 :
1147 : /* Create a candidate entry for a statement GS, where GS multiplies
1148 : SSA name BASE_IN by constant STRIDE_IN. Propagate any known
1149 : information about BASE_IN into the new candidate. Return the new
1150 : candidate. */
1151 :
1152 : static slsr_cand_t
1153 687165 : create_mul_imm_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
1154 : {
1155 687165 : tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
1156 687165 : offset_int index, temp;
1157 687165 : unsigned savings = 0;
1158 687165 : slsr_cand_t c;
1159 687165 : slsr_cand_t base_cand = base_cand_from_table (base_in);
1160 :
1161 : /* Look at all interpretations of the base candidate, if necessary,
1162 : to find information to propagate into this candidate. */
1163 1779258 : while (base_cand && !base && base_cand->kind != CAND_PHI)
1164 : {
1165 404928 : if (base_cand->kind == CAND_MULT
1166 35325 : && TREE_CODE (base_cand->stride) == INTEGER_CST)
1167 : {
1168 : /* Y = (B + i') * S, S constant
1169 : X = Y * c
1170 : ============================
1171 : X = (B + i') * (S * c) */
1172 14242 : temp = wi::to_offset (base_cand->stride) * wi::to_offset (stride_in);
1173 14242 : if (wi::fits_to_tree_p (temp, TREE_TYPE (stride_in)))
1174 : {
1175 13589 : base = base_cand->base_expr;
1176 13589 : index = base_cand->index;
1177 13589 : stride = wide_int_to_tree (TREE_TYPE (stride_in), temp);
1178 13589 : ctype = base_cand->cand_type;
1179 13589 : if (has_single_use (base_in))
1180 14114 : savings = (base_cand->dead_savings
1181 7057 : + stmt_cost (base_cand->cand_stmt, speed));
1182 : }
1183 : }
1184 390686 : else if (base_cand->kind == CAND_ADD && integer_onep (base_cand->stride))
1185 : {
1186 : /* Y = B + (i' * 1)
1187 : X = Y * c
1188 : ===========================
1189 : X = (B + i') * c */
1190 264451 : base = base_cand->base_expr;
1191 264451 : index = base_cand->index;
1192 264451 : stride = stride_in;
1193 264451 : ctype = base_cand->cand_type;
1194 264451 : if (has_single_use (base_in))
1195 426122 : savings = (base_cand->dead_savings
1196 213061 : + stmt_cost (base_cand->cand_stmt, speed));
1197 : }
1198 126235 : else if (base_cand->kind == CAND_ADD
1199 209116 : && base_cand->index == 1
1200 209116 : && TREE_CODE (base_cand->stride) == INTEGER_CST)
1201 : {
1202 : /* Y = B + (1 * S), S constant
1203 : X = Y * c
1204 : ===========================
1205 : X = (B + S) * c */
1206 0 : base = base_cand->base_expr;
1207 0 : index = wi::to_offset (base_cand->stride);
1208 0 : stride = stride_in;
1209 0 : ctype = base_cand->cand_type;
1210 0 : if (has_single_use (base_in))
1211 0 : savings = (base_cand->dead_savings
1212 0 : + stmt_cost (base_cand->cand_stmt, speed));
1213 : }
1214 :
1215 404928 : base_cand = lookup_cand (base_cand->next_interp);
1216 : }
1217 :
1218 687165 : if (!base)
1219 : {
1220 : /* No interpretations had anything useful to propagate, so
1221 : produce X = (Y + 0) * c. */
1222 409125 : base = base_in;
1223 409125 : index = 0;
1224 409125 : stride = stride_in;
1225 409125 : ctype = TREE_TYPE (base_in);
1226 : }
1227 :
1228 687165 : c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
1229 : ctype, sizetype, savings);
1230 687165 : return c;
1231 : }
1232 :
1233 : /* Given GS which is a multiply of scalar integers, make an appropriate
1234 : entry in the candidate table. If this is a multiply of two SSA names,
1235 : create two CAND_MULT interpretations and attempt to find a basis for
1236 : each of them. Otherwise, create a single CAND_MULT and attempt to
1237 : find a basis. */
1238 :
1239 : static void
1240 743248 : slsr_process_mul (gimple *gs, tree rhs1, tree rhs2, bool speed)
1241 : {
1242 743248 : slsr_cand_t c, c2;
1243 :
1244 : /* If this is a multiply of an SSA name with itself, it is highly
1245 : unlikely that we will get a strength reduction opportunity, so
1246 : don't record it as a candidate. This simplifies the logic for
1247 : finding a basis, so if this is removed that must be considered. */
1248 743248 : if (rhs1 == rhs2)
1249 : return;
1250 :
1251 735794 : if (TREE_CODE (rhs2) == SSA_NAME)
1252 : {
1253 : /* Record an interpretation of this statement in the candidate table
1254 : assuming RHS1 is the base expression and RHS2 is the stride. */
1255 146889 : c = create_mul_ssa_cand (gs, rhs1, rhs2, speed);
1256 :
1257 : /* Add the first interpretation to the statement-candidate mapping. */
1258 146889 : add_cand_for_stmt (gs, c);
1259 :
1260 : /* Record another interpretation of this statement assuming RHS1
1261 : is the stride and RHS2 is the base expression. */
1262 146889 : c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);
1263 146889 : c->next_interp = c2->cand_num;
1264 146889 : c2->first_interp = c->cand_num;
1265 : }
1266 588905 : else if (TREE_CODE (rhs2) == INTEGER_CST && !integer_zerop (rhs2))
1267 : {
1268 : /* Record an interpretation for the multiply-immediate. */
1269 588905 : c = create_mul_imm_cand (gs, rhs1, rhs2, speed);
1270 :
1271 : /* Add the interpretation to the statement-candidate mapping. */
1272 588905 : add_cand_for_stmt (gs, c);
1273 : }
1274 : }
1275 :
1276 : /* Create a candidate entry for a statement GS, where GS adds two
1277 : SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1278 : subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1279 : information about the two SSA names into the new candidate.
1280 : Return the new candidate. */
1281 :
1282 : static slsr_cand_t
1283 1929054 : create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in,
1284 : bool subtract_p, bool speed)
1285 : {
1286 1929054 : tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
1287 1929054 : tree stype = NULL_TREE;
1288 1929054 : offset_int index;
1289 1929054 : unsigned savings = 0;
1290 1929054 : slsr_cand_t c;
1291 1929054 : slsr_cand_t base_cand = base_cand_from_table (base_in);
1292 1929054 : slsr_cand_t addend_cand = base_cand_from_table (addend_in);
1293 :
1294 : /* The most useful transformation is a multiply-immediate feeding
1295 : an add or subtract. Look for that first. */
1296 5499326 : while (addend_cand && !base && addend_cand->kind != CAND_PHI)
1297 : {
1298 1641218 : if (addend_cand->kind == CAND_MULT
1299 1792761 : && addend_cand->index == 0
1300 2420349 : && TREE_CODE (addend_cand->stride) == INTEGER_CST)
1301 : {
1302 : /* Z = (B + 0) * S, S constant
1303 : X = Y +/- Z
1304 : ===========================
1305 : X = Y + ((+/-1 * S) * B) */
1306 627588 : base = base_in;
1307 627588 : index = wi::to_offset (addend_cand->stride);
1308 627588 : if (subtract_p)
1309 50252 : index = -index;
1310 627588 : stride = addend_cand->base_expr;
1311 627588 : ctype = TREE_TYPE (base_in);
1312 627588 : stype = addend_cand->cand_type;
1313 627588 : if (has_single_use (addend_in))
1314 1003472 : savings = (addend_cand->dead_savings
1315 501736 : + stmt_cost (addend_cand->cand_stmt, speed));
1316 : }
1317 :
1318 1641218 : addend_cand = lookup_cand (addend_cand->next_interp);
1319 : }
1320 :
1321 2694790 : while (base_cand && !base && base_cand->kind != CAND_PHI)
1322 : {
1323 765736 : if (base_cand->kind == CAND_ADD
1324 765736 : && (base_cand->index == 0
1325 429910 : || operand_equal_p (base_cand->stride,
1326 429910 : integer_zero_node, 0)))
1327 : {
1328 : /* Y = B + (i' * S), i' * S = 0
1329 : X = Y +/- Z
1330 : ============================
1331 : X = B + (+/-1 * Z) */
1332 113872 : base = base_cand->base_expr;
1333 215552 : index = subtract_p ? -1 : 1;
1334 113872 : stride = addend_in;
1335 113872 : ctype = base_cand->cand_type;
1336 227744 : stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype
1337 113872 : : TREE_TYPE (addend_in));
1338 113872 : if (has_single_use (base_in))
1339 166476 : savings = (base_cand->dead_savings
1340 83238 : + stmt_cost (base_cand->cand_stmt, speed));
1341 : }
1342 651864 : else if (subtract_p)
1343 : {
1344 67189 : slsr_cand_t subtrahend_cand = base_cand_from_table (addend_in);
1345 :
1346 160157 : while (subtrahend_cand && !base && subtrahend_cand->kind != CAND_PHI)
1347 : {
1348 25779 : if (subtrahend_cand->kind == CAND_MULT
1349 33433 : && subtrahend_cand->index == 0
1350 33433 : && TREE_CODE (subtrahend_cand->stride) == INTEGER_CST)
1351 : {
1352 : /* Z = (B + 0) * S, S constant
1353 : X = Y - Z
1354 : ===========================
1355 : Value: X = Y + ((-1 * S) * B) */
1356 0 : base = base_in;
1357 0 : index = wi::to_offset (subtrahend_cand->stride);
1358 0 : index = -index;
1359 0 : stride = subtrahend_cand->base_expr;
1360 0 : ctype = TREE_TYPE (base_in);
1361 0 : stype = subtrahend_cand->cand_type;
1362 0 : if (has_single_use (addend_in))
1363 0 : savings = (subtrahend_cand->dead_savings
1364 0 : + stmt_cost (subtrahend_cand->cand_stmt, speed));
1365 : }
1366 :
1367 25779 : subtrahend_cand = lookup_cand (subtrahend_cand->next_interp);
1368 : }
1369 : }
1370 :
1371 765736 : base_cand = lookup_cand (base_cand->next_interp);
1372 : }
1373 :
1374 1929054 : if (!base)
1375 : {
1376 : /* No interpretations had anything useful to propagate, so
1377 : produce X = Y + (1 * Z). */
1378 1187594 : base = base_in;
1379 2204684 : index = subtract_p ? -1 : 1;
1380 1187594 : stride = addend_in;
1381 1187594 : ctype = TREE_TYPE (base_in);
1382 2375188 : stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype
1383 1187594 : : TREE_TYPE (addend_in));
1384 : }
1385 :
1386 1929054 : c = alloc_cand_and_find_basis (CAND_ADD, gs, base, index, stride,
1387 : ctype, stype, savings);
1388 1929054 : return c;
1389 : }
1390 :
1391 : /* Create a candidate entry for a statement GS, where GS adds SSA
1392 : name BASE_IN to constant INDEX_IN. Propagate any known information
1393 : about BASE_IN into the new candidate. Return the new candidate. */
1394 :
1395 : static slsr_cand_t
1396 1942576 : create_add_imm_cand (gimple *gs, tree base_in, const offset_int &index_in,
1397 : bool speed)
1398 : {
1399 1942576 : enum cand_kind kind = CAND_ADD;
1400 1942576 : tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
1401 1942576 : tree stype = NULL_TREE;
1402 1942576 : offset_int index, multiple;
1403 1942576 : unsigned savings = 0;
1404 1942576 : slsr_cand_t c;
1405 1942576 : slsr_cand_t base_cand = base_cand_from_table (base_in);
1406 :
1407 4337639 : while (base_cand && !base && base_cand->kind != CAND_PHI)
1408 : {
1409 452487 : signop sign = TYPE_SIGN (TREE_TYPE (base_cand->stride));
1410 :
1411 452487 : if (TREE_CODE (base_cand->stride) == INTEGER_CST
1412 452487 : && wi::multiple_of_p (index_in, wi::to_offset (base_cand->stride),
1413 : sign, &multiple))
1414 : {
1415 : /* Y = (B + i') * S, S constant, c = kS for some integer k
1416 : X = Y + c
1417 : ============================
1418 : X = (B + (i'+ k)) * S
1419 : OR
1420 : Y = B + (i' * S), S constant, c = kS for some integer k
1421 : X = Y + c
1422 : ============================
1423 : X = (B + (i'+ k)) * S */
1424 267496 : kind = base_cand->kind;
1425 267496 : base = base_cand->base_expr;
1426 267496 : index = base_cand->index + multiple;
1427 267496 : stride = base_cand->stride;
1428 267496 : ctype = base_cand->cand_type;
1429 267496 : stype = base_cand->stride_type;
1430 267496 : if (has_single_use (base_in))
1431 323160 : savings = (base_cand->dead_savings
1432 161580 : + stmt_cost (base_cand->cand_stmt, speed));
1433 : }
1434 :
1435 452487 : base_cand = lookup_cand (base_cand->next_interp);
1436 : }
1437 :
1438 1942576 : if (!base)
1439 : {
1440 : /* No interpretations had anything useful to propagate, so
1441 : produce X = Y + (c * 1). */
1442 1675080 : kind = CAND_ADD;
1443 1675080 : base = base_in;
1444 1675080 : index = index_in;
1445 1675080 : stride = integer_one_node;
1446 1675080 : ctype = TREE_TYPE (base_in);
1447 1675080 : stype = sizetype;
1448 : }
1449 :
1450 1942576 : c = alloc_cand_and_find_basis (kind, gs, base, index, stride,
1451 : ctype, stype, savings);
1452 1942576 : return c;
1453 : }
1454 :
1455 : /* Given GS which is an add or subtract of scalar integers or pointers,
1456 : make at least one appropriate entry in the candidate table. */
1457 :
1458 : static void
1459 3240740 : slsr_process_add (gimple *gs, tree rhs1, tree rhs2, bool speed)
1460 : {
1461 3240740 : bool subtract_p = gimple_assign_rhs_code (gs) == MINUS_EXPR;
1462 3240740 : slsr_cand_t c = NULL, c2;
1463 :
1464 3240740 : if (TREE_CODE (rhs2) == SSA_NAME)
1465 : {
1466 : /* First record an interpretation assuming RHS1 is the base expression
1467 : and RHS2 is the stride. But it doesn't make sense for the
1468 : stride to be a pointer, so don't record a candidate in that case. */
1469 1298164 : if (!POINTER_TYPE_P (TREE_TYPE (rhs2)))
1470 : {
1471 1298164 : c = create_add_ssa_cand (gs, rhs1, rhs2, subtract_p, speed);
1472 :
1473 : /* Add the first interpretation to the statement-candidate
1474 : mapping. */
1475 1298164 : add_cand_for_stmt (gs, c);
1476 : }
1477 :
1478 : /* If the two RHS operands are identical, or this is a subtract,
1479 : we're done. */
1480 1298164 : if (operand_equal_p (rhs1, rhs2, 0) || subtract_p)
1481 : return;
1482 :
1483 : /* Otherwise, record another interpretation assuming RHS2 is the
1484 : base expression and RHS1 is the stride, again provided that the
1485 : stride is not a pointer. */
1486 1065216 : if (!POINTER_TYPE_P (TREE_TYPE (rhs1)))
1487 : {
1488 630890 : c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);
1489 630890 : if (c)
1490 : {
1491 630890 : c->next_interp = c2->cand_num;
1492 630890 : c2->first_interp = c->cand_num;
1493 : }
1494 : else
1495 0 : add_cand_for_stmt (gs, c2);
1496 : }
1497 : }
1498 1942576 : else if (TREE_CODE (rhs2) == INTEGER_CST)
1499 : {
1500 : /* Record an interpretation for the add-immediate. */
1501 1942576 : offset_int index = wi::to_offset (rhs2);
1502 1942576 : if (subtract_p)
1503 25686 : index = -index;
1504 :
1505 1942576 : c = create_add_imm_cand (gs, rhs1, index, speed);
1506 :
1507 : /* Add the interpretation to the statement-candidate mapping. */
1508 1942576 : add_cand_for_stmt (gs, c);
1509 : }
1510 : }
1511 :
1512 : /* Given GS which is a negate of a scalar integer, make an appropriate
1513 : entry in the candidate table. A negate is equivalent to a multiply
1514 : by -1. */
1515 :
1516 : static void
1517 98260 : slsr_process_neg (gimple *gs, tree rhs1, bool speed)
1518 : {
1519 : /* Record a CAND_MULT interpretation for the multiply by -1. */
1520 98260 : slsr_cand_t c = create_mul_imm_cand (gs, rhs1, integer_minus_one_node, speed);
1521 :
1522 : /* Add the interpretation to the statement-candidate mapping. */
1523 98260 : add_cand_for_stmt (gs, c);
1524 98260 : }
1525 :
1526 : /* Help function for legal_cast_p, operating on two trees. Checks
1527 : whether it's allowable to cast from RHS to LHS. See legal_cast_p
1528 : for more details. */
1529 :
1530 : static bool
1531 2828388 : legal_cast_p_1 (tree lhs_type, tree rhs_type)
1532 : {
1533 2828388 : unsigned lhs_size, rhs_size;
1534 2828388 : bool lhs_wraps, rhs_wraps;
1535 :
1536 2828388 : lhs_size = TYPE_PRECISION (lhs_type);
1537 2828388 : rhs_size = TYPE_PRECISION (rhs_type);
1538 2828388 : lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type);
1539 2828388 : rhs_wraps = ANY_INTEGRAL_TYPE_P (rhs_type) && TYPE_OVERFLOW_WRAPS (rhs_type);
1540 :
1541 2828388 : if (lhs_size < rhs_size
1542 2572225 : || (rhs_wraps && !lhs_wraps)
1543 1664797 : || (rhs_wraps && lhs_wraps && rhs_size != lhs_size))
1544 1346820 : return false;
1545 :
1546 : return true;
1547 : }
1548 :
1549 : /* Return TRUE if GS is a statement that defines an SSA name from
1550 : a conversion and is legal for us to combine with an add and multiply
1551 : in the candidate table. For example, suppose we have:
1552 :
1553 : A = B + i;
1554 : C = (type) A;
1555 : D = C * S;
1556 :
1557 : Without the type-cast, we would create a CAND_MULT for D with base B,
1558 : index i, and stride S. We want to record this candidate only if it
1559 : is equivalent to apply the type cast following the multiply:
1560 :
1561 : A = B + i;
1562 : E = A * S;
1563 : D = (type) E;
1564 :
1565 : We will record the type with the candidate for D. This allows us
1566 : to use a similar previous candidate as a basis. If we have earlier seen
1567 :
1568 : A' = B + i';
1569 : C' = (type) A';
1570 : D' = C' * S;
1571 :
1572 : we can replace D with
1573 :
1574 : D = D' + (i - i') * S;
1575 :
1576 : But if moving the type-cast would change semantics, we mustn't do this.
1577 :
1578 : This is legitimate for casts from a non-wrapping integral type to
1579 : any integral type of the same or larger size. It is not legitimate
1580 : to convert a wrapping type to a non-wrapping type, or to a wrapping
1581 : type of a different size. I.e., with a wrapping type, we must
1582 : assume that the addition B + i could wrap, in which case performing
1583 : the multiply before or after one of the "illegal" type casts will
1584 : have different semantics. */
1585 :
1586 : static bool
1587 2823585 : legal_cast_p (gimple *gs, tree rhs)
1588 : {
1589 2823585 : if (!is_gimple_assign (gs)
1590 2823585 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs)))
1591 : return false;
1592 :
1593 2823585 : return legal_cast_p_1 (TREE_TYPE (gimple_assign_lhs (gs)), TREE_TYPE (rhs));
1594 : }
1595 :
1596 : /* Given GS which is a cast to a scalar integer type, determine whether
1597 : the cast is legal for strength reduction. If so, make at least one
1598 : appropriate entry in the candidate table. */
1599 :
1600 : static void
1601 2823585 : slsr_process_cast (gimple *gs, tree rhs1, bool speed)
1602 : {
1603 2823585 : tree lhs, ctype;
1604 2823585 : slsr_cand_t base_cand, c = NULL, c2;
1605 2823585 : unsigned savings = 0;
1606 :
1607 2823585 : if (!legal_cast_p (gs, rhs1))
1608 : return;
1609 :
1610 1477471 : lhs = gimple_assign_lhs (gs);
1611 1477471 : base_cand = base_cand_from_table (rhs1);
1612 1477471 : ctype = TREE_TYPE (lhs);
1613 :
1614 1477471 : if (base_cand && base_cand->kind != CAND_PHI)
1615 : {
1616 : slsr_cand_t first_cand = NULL;
1617 :
1618 617508 : while (base_cand)
1619 : {
1620 : /* Propagate all data from the base candidate except the type,
1621 : which comes from the cast, and the base candidate's cast,
1622 : which is no longer applicable. */
1623 351947 : if (has_single_use (rhs1))
1624 398416 : savings = (base_cand->dead_savings
1625 199208 : + stmt_cost (base_cand->cand_stmt, speed));
1626 :
1627 703894 : c = alloc_cand_and_find_basis (base_cand->kind, gs,
1628 : base_cand->base_expr,
1629 351947 : base_cand->index, base_cand->stride,
1630 : ctype, base_cand->stride_type,
1631 : savings);
1632 351947 : if (!first_cand)
1633 265561 : first_cand = c;
1634 :
1635 351947 : if (first_cand != c)
1636 86386 : c->first_interp = first_cand->cand_num;
1637 :
1638 351947 : base_cand = lookup_cand (base_cand->next_interp);
1639 : }
1640 : }
1641 : else
1642 : {
1643 : /* If nothing is known about the RHS, create fresh CAND_ADD and
1644 : CAND_MULT interpretations:
1645 :
1646 : X = Y + (0 * 1)
1647 : X = (Y + 0) * 1
1648 :
1649 : The first of these is somewhat arbitrary, but the choice of
1650 : 1 for the stride simplifies the logic for propagating casts
1651 : into their uses. */
1652 1211910 : c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0,
1653 : integer_one_node, ctype, sizetype, 0);
1654 1211910 : c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
1655 : integer_one_node, ctype, sizetype, 0);
1656 1211910 : c->next_interp = c2->cand_num;
1657 1211910 : c2->first_interp = c->cand_num;
1658 : }
1659 :
1660 : /* Add the first (or only) interpretation to the statement-candidate
1661 : mapping. */
1662 1477471 : add_cand_for_stmt (gs, c);
1663 : }
1664 :
1665 : /* Given GS which is a copy of a scalar integer type, make at least one
1666 : appropriate entry in the candidate table.
1667 :
1668 : This interface is included for completeness, but is unnecessary
1669 : if this pass immediately follows a pass that performs copy
1670 : propagation, such as DOM. */
1671 :
1672 : static void
1673 151047 : slsr_process_copy (gimple *gs, tree rhs1, bool speed)
1674 : {
1675 151047 : slsr_cand_t base_cand, c = NULL, c2;
1676 151047 : unsigned savings = 0;
1677 :
1678 151047 : base_cand = base_cand_from_table (rhs1);
1679 :
1680 151047 : if (base_cand && base_cand->kind != CAND_PHI)
1681 : {
1682 : slsr_cand_t first_cand = NULL;
1683 :
1684 98317 : while (base_cand)
1685 : {
1686 : /* Propagate all data from the base candidate. */
1687 55564 : if (has_single_use (rhs1))
1688 94920 : savings = (base_cand->dead_savings
1689 47460 : + stmt_cost (base_cand->cand_stmt, speed));
1690 :
1691 111128 : c = alloc_cand_and_find_basis (base_cand->kind, gs,
1692 : base_cand->base_expr,
1693 55564 : base_cand->index, base_cand->stride,
1694 : base_cand->cand_type,
1695 : base_cand->stride_type, savings);
1696 55564 : if (!first_cand)
1697 42753 : first_cand = c;
1698 :
1699 55564 : if (first_cand != c)
1700 12811 : c->first_interp = first_cand->cand_num;
1701 :
1702 55564 : base_cand = lookup_cand (base_cand->next_interp);
1703 : }
1704 : }
1705 : else
1706 : {
1707 : /* If nothing is known about the RHS, create fresh CAND_ADD and
1708 : CAND_MULT interpretations:
1709 :
1710 : X = Y + (0 * 1)
1711 : X = (Y + 0) * 1
1712 :
1713 : The first of these is somewhat arbitrary, but the choice of
1714 : 1 for the stride simplifies the logic for propagating casts
1715 : into their uses. */
1716 108294 : c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0,
1717 108294 : integer_one_node, TREE_TYPE (rhs1),
1718 : sizetype, 0);
1719 108294 : c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
1720 108294 : integer_one_node, TREE_TYPE (rhs1),
1721 : sizetype, 0);
1722 108294 : c->next_interp = c2->cand_num;
1723 108294 : c2->first_interp = c->cand_num;
1724 : }
1725 :
1726 : /* Add the first (or only) interpretation to the statement-candidate
1727 : mapping. */
1728 151047 : add_cand_for_stmt (gs, c);
1729 151047 : }
1730 :
1731 2082932 : class find_candidates_dom_walker : public dom_walker
1732 : {
1733 : public:
1734 1041466 : find_candidates_dom_walker (cdi_direction direction)
1735 2082932 : : dom_walker (direction) {}
1736 : edge before_dom_children (basic_block) final override;
1737 : };
1738 :
1739 : /* Find strength-reduction candidates in block BB. */
1740 :
1741 : edge
1742 10986769 : find_candidates_dom_walker::before_dom_children (basic_block bb)
1743 : {
1744 10986769 : bool speed = optimize_bb_for_speed_p (bb);
1745 :
1746 15421958 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1747 4435189 : gsi_next (&gsi))
1748 4435189 : slsr_process_phi (gsi.phi (), speed);
1749 :
1750 106671436 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1751 84697898 : gsi_next (&gsi))
1752 : {
1753 84697898 : gimple *gs = gsi_stmt (gsi);
1754 :
1755 84697898 : if (stmt_could_throw_p (cfun, gs))
1756 3227568 : continue;
1757 :
1758 109106234 : if (gimple_vuse (gs) && gimple_assign_single_p (gs))
1759 12241872 : slsr_process_ref (gs);
1760 :
1761 69228458 : else if (is_gimple_assign (gs)
1762 69228458 : && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))
1763 3142128 : || POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))))
1764 : {
1765 9798753 : tree rhs1 = NULL_TREE, rhs2 = NULL_TREE;
1766 :
1767 9798753 : switch (gimple_assign_rhs_code (gs))
1768 : {
1769 2984024 : case MULT_EXPR:
1770 2984024 : case PLUS_EXPR:
1771 2984024 : rhs1 = gimple_assign_rhs1 (gs);
1772 2984024 : rhs2 = gimple_assign_rhs2 (gs);
1773 : /* Should never happen, but currently some buggy situations
1774 : in earlier phases put constants in rhs1. */
1775 2984024 : if (TREE_CODE (rhs1) != SSA_NAME)
1776 1 : continue;
1777 : break;
1778 :
1779 : /* Possible future opportunity: rhs1 of a ptr+ can be
1780 : an ADDR_EXPR. */
1781 1102130 : case POINTER_PLUS_EXPR:
1782 1102130 : case MINUS_EXPR:
1783 1102130 : rhs2 = gimple_assign_rhs2 (gs);
1784 4392553 : gcc_fallthrough ();
1785 :
1786 4392553 : CASE_CONVERT:
1787 4392553 : case SSA_NAME:
1788 4392553 : case NEGATE_EXPR:
1789 4392553 : rhs1 = gimple_assign_rhs1 (gs);
1790 4392553 : if (TREE_CODE (rhs1) != SSA_NAME)
1791 319696 : continue;
1792 : break;
1793 :
1794 9479056 : default:
1795 9479056 : ;
1796 : }
1797 :
1798 9479056 : switch (gimple_assign_rhs_code (gs))
1799 : {
1800 743248 : case MULT_EXPR:
1801 743248 : slsr_process_mul (gs, rhs1, rhs2, speed);
1802 743248 : break;
1803 :
1804 3240740 : case PLUS_EXPR:
1805 3240740 : case POINTER_PLUS_EXPR:
1806 3240740 : case MINUS_EXPR:
1807 3240740 : slsr_process_add (gs, rhs1, rhs2, speed);
1808 3240740 : break;
1809 :
1810 98260 : case NEGATE_EXPR:
1811 98260 : slsr_process_neg (gs, rhs1, speed);
1812 98260 : break;
1813 :
1814 2823585 : CASE_CONVERT:
1815 2823585 : slsr_process_cast (gs, rhs1, speed);
1816 2823585 : break;
1817 :
1818 151047 : case SSA_NAME:
1819 151047 : slsr_process_copy (gs, rhs1, speed);
1820 151047 : break;
1821 :
1822 : default:
1823 : ;
1824 : }
1825 : }
1826 : }
1827 10986769 : return NULL;
1828 : }
1829 :
1830 : /* Dump a candidate for debug. */
1831 :
1832 : static void
1833 33 : dump_candidate (slsr_cand_t c)
1834 : {
1835 33 : fprintf (dump_file, "%3d [%d] ", c->cand_num,
1836 33 : gimple_bb (c->cand_stmt)->index);
1837 33 : print_gimple_stmt (dump_file, c->cand_stmt, 0);
1838 33 : switch (c->kind)
1839 : {
1840 5 : case CAND_MULT:
1841 5 : fputs (" MULT : (", dump_file);
1842 5 : print_generic_expr (dump_file, c->base_expr);
1843 5 : fputs (" + ", dump_file);
1844 5 : print_decs (c->index, dump_file);
1845 5 : fputs (") * ", dump_file);
1846 5 : if (TREE_CODE (c->stride) != INTEGER_CST
1847 5 : && c->stride_type != TREE_TYPE (c->stride))
1848 : {
1849 0 : fputs ("(", dump_file);
1850 0 : print_generic_expr (dump_file, c->stride_type);
1851 0 : fputs (")", dump_file);
1852 : }
1853 5 : print_generic_expr (dump_file, c->stride);
1854 5 : fputs (" : ", dump_file);
1855 5 : break;
1856 17 : case CAND_ADD:
1857 17 : fputs (" ADD : ", dump_file);
1858 17 : print_generic_expr (dump_file, c->base_expr);
1859 17 : fputs (" + (", dump_file);
1860 17 : print_decs (c->index, dump_file);
1861 17 : fputs (" * ", dump_file);
1862 17 : if (TREE_CODE (c->stride) != INTEGER_CST
1863 17 : && c->stride_type != TREE_TYPE (c->stride))
1864 : {
1865 0 : fputs ("(", dump_file);
1866 0 : print_generic_expr (dump_file, c->stride_type);
1867 0 : fputs (")", dump_file);
1868 : }
1869 17 : print_generic_expr (dump_file, c->stride);
1870 17 : fputs (") : ", dump_file);
1871 17 : break;
1872 11 : case CAND_REF:
1873 11 : fputs (" REF : ", dump_file);
1874 11 : print_generic_expr (dump_file, c->base_expr);
1875 11 : fputs (" + (", dump_file);
1876 11 : print_generic_expr (dump_file, c->stride);
1877 11 : fputs (") + ", dump_file);
1878 11 : print_decs (c->index, dump_file);
1879 11 : fputs (" : ", dump_file);
1880 11 : break;
1881 0 : case CAND_PHI:
1882 0 : fputs (" PHI : ", dump_file);
1883 0 : print_generic_expr (dump_file, c->base_expr);
1884 0 : fputs (" + (unknown * ", dump_file);
1885 0 : print_generic_expr (dump_file, c->stride);
1886 0 : fputs (") : ", dump_file);
1887 0 : break;
1888 0 : default:
1889 0 : gcc_unreachable ();
1890 : }
1891 33 : print_generic_expr (dump_file, c->cand_type);
1892 33 : fprintf (dump_file, "\n basis: %d dependent: %d sibling: %d\n",
1893 : c->basis, c->dependent, c->sibling);
1894 33 : fprintf (dump_file,
1895 : " next-interp: %d first-interp: %d dead-savings: %d\n",
1896 : c->next_interp, c->first_interp, c->dead_savings);
1897 33 : if (c->def_phi)
1898 0 : fprintf (dump_file, " phi: %d\n", c->def_phi);
1899 33 : fputs ("\n", dump_file);
1900 33 : }
1901 :
1902 : /* Dump the candidate vector for debug. */
1903 :
1904 : static void
1905 3 : dump_cand_vec (void)
1906 : {
1907 3 : unsigned i;
1908 3 : slsr_cand_t c;
1909 :
1910 3 : fprintf (dump_file, "\nStrength reduction candidate vector:\n\n");
1911 :
1912 42 : FOR_EACH_VEC_ELT (cand_vec, i, c)
1913 36 : if (c != NULL)
1914 33 : dump_candidate (c);
1915 3 : }
1916 :
1917 : /* Callback used to dump the candidate chains hash table. */
1918 :
1919 : int
1920 14 : ssa_base_cand_dump_callback (cand_chain **slot, void *ignored ATTRIBUTE_UNUSED)
1921 : {
1922 14 : const_cand_chain_t chain = *slot;
1923 14 : cand_chain_t p;
1924 :
1925 14 : print_generic_expr (dump_file, chain->base_expr);
1926 14 : fprintf (dump_file, " -> %d", chain->cand->cand_num);
1927 :
1928 42 : for (p = chain->next; p; p = p->next)
1929 28 : fprintf (dump_file, " -> %d", p->cand->cand_num);
1930 :
1931 14 : fputs ("\n", dump_file);
1932 14 : return 1;
1933 : }
1934 :
1935 : /* Dump the candidate chains. */
1936 :
1937 : static void
1938 3 : dump_cand_chains (void)
1939 : {
1940 3 : fprintf (dump_file, "\nStrength reduction candidate chains:\n\n");
1941 3 : base_cand_map->traverse_noresize <void *, ssa_base_cand_dump_callback>
1942 17 : (NULL);
1943 3 : fputs ("\n", dump_file);
1944 3 : }
1945 :
1946 : /* Dump the increment vector for debug. */
1947 :
1948 : static void
1949 36348 : dump_incr_vec (void)
1950 : {
1951 36348 : if (dump_file && (dump_flags & TDF_DETAILS))
1952 : {
1953 0 : unsigned i;
1954 :
1955 0 : fprintf (dump_file, "\nIncrement vector:\n\n");
1956 :
1957 0 : for (i = 0; i < incr_vec_len; i++)
1958 : {
1959 0 : fprintf (dump_file, "%3d increment: ", i);
1960 0 : print_decs (incr_vec[i].incr, dump_file);
1961 0 : fprintf (dump_file, "\n count: %d", incr_vec[i].count);
1962 0 : fprintf (dump_file, "\n cost: %d", incr_vec[i].cost);
1963 0 : fputs ("\n initializer: ", dump_file);
1964 0 : print_generic_expr (dump_file, incr_vec[i].initializer);
1965 0 : fputs ("\n\n", dump_file);
1966 : }
1967 : }
1968 36348 : }
1969 :
1970 : /* Replace *EXPR in candidate C with an equivalent strength-reduced
1971 : data reference. */
1972 :
1973 : static void
1974 19221 : replace_ref (tree *expr, slsr_cand_t c)
1975 : {
1976 19221 : tree add_expr, mem_ref, acc_type = TREE_TYPE (*expr);
1977 19221 : unsigned HOST_WIDE_INT misalign;
1978 19221 : unsigned align;
1979 :
1980 : /* Ensure the memory reference carries the minimum alignment
1981 : requirement for the data type. See PR58041. */
1982 19221 : get_object_alignment_1 (*expr, &align, &misalign);
1983 19221 : if (misalign != 0)
1984 268 : align = least_bit_hwi (misalign);
1985 19221 : if (align < TYPE_ALIGN (acc_type))
1986 240 : acc_type = build_aligned_type (acc_type, align);
1987 :
1988 19221 : add_expr = fold_build2 (POINTER_PLUS_EXPR, c->cand_type,
1989 : c->base_expr, c->stride);
1990 19221 : mem_ref = fold_build2 (MEM_REF, acc_type, add_expr,
1991 : wide_int_to_tree (c->cand_type, c->index));
1992 :
1993 : /* Gimplify the base addressing expression for the new MEM_REF tree. */
1994 19221 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
1995 19221 : TREE_OPERAND (mem_ref, 0)
1996 19221 : = force_gimple_operand_gsi (&gsi, TREE_OPERAND (mem_ref, 0),
1997 : /*simple_p=*/true, NULL,
1998 : /*before=*/true, GSI_SAME_STMT);
1999 19221 : copy_ref_info (mem_ref, *expr);
2000 19221 : *expr = mem_ref;
2001 19221 : update_stmt (c->cand_stmt);
2002 19221 : }
2003 :
2004 : /* Return true if CAND_REF candidate C is a valid memory reference. */
2005 :
2006 : static bool
2007 8380 : valid_mem_ref_cand_p (slsr_cand_t c)
2008 : {
2009 8380 : if (TREE_CODE (TREE_OPERAND (c->stride, 1)) != INTEGER_CST)
2010 : return false;
2011 :
2012 8380 : struct mem_address addr
2013 16760 : = { NULL_TREE, c->base_expr, TREE_OPERAND (c->stride, 0),
2014 8380 : TREE_OPERAND (c->stride, 1), wide_int_to_tree (sizetype, c->index) };
2015 :
2016 8380 : return
2017 8380 : valid_mem_ref_p (TYPE_MODE (c->cand_type), TYPE_ADDR_SPACE (c->cand_type),
2018 : &addr);
2019 : }
2020 :
2021 : /* Replace CAND_REF candidate C, each sibling of candidate C, and each
2022 : dependent of candidate C with an equivalent strength-reduced data
2023 : reference. */
2024 :
2025 : static void
2026 8388 : replace_refs (slsr_cand_t c)
2027 : {
2028 : /* Replacing a chain of only 2 candidates which are valid memory references
2029 : is generally counter-productive because you cannot recoup the additional
2030 : calculation added in front of them. */
2031 23054 : if (c->basis == 0
2032 7906 : && c->dependent
2033 7906 : && !lookup_cand (c->dependent)->dependent
2034 4547 : && valid_mem_ref_cand_p (c)
2035 26887 : && valid_mem_ref_cand_p (lookup_cand (c->dependent)))
2036 : return;
2037 :
2038 19221 : if (dump_file && (dump_flags & TDF_DETAILS))
2039 : {
2040 9 : fputs ("Replacing reference: ", dump_file);
2041 9 : print_gimple_stmt (dump_file, c->cand_stmt, 0);
2042 : }
2043 :
2044 38442 : if (gimple_vdef (c->cand_stmt))
2045 : {
2046 6786 : tree *lhs = gimple_assign_lhs_ptr (c->cand_stmt);
2047 6786 : replace_ref (lhs, c);
2048 : }
2049 : else
2050 : {
2051 12435 : tree *rhs = gimple_assign_rhs1_ptr (c->cand_stmt);
2052 12435 : replace_ref (rhs, c);
2053 : }
2054 :
2055 19221 : if (dump_file && (dump_flags & TDF_DETAILS))
2056 : {
2057 9 : fputs ("With: ", dump_file);
2058 9 : print_gimple_stmt (dump_file, c->cand_stmt, 0);
2059 9 : fputs ("\n", dump_file);
2060 : }
2061 :
2062 19221 : if (c->sibling)
2063 482 : replace_refs (lookup_cand (c->sibling));
2064 :
2065 19221 : if (c->dependent)
2066 14666 : replace_refs (lookup_cand (c->dependent));
2067 : }
2068 :
2069 : /* Return TRUE if candidate C is dependent upon a PHI. */
2070 :
2071 : static bool
2072 2679513 : phi_dependent_cand_p (slsr_cand_t c)
2073 : {
2074 : /* A candidate is not necessarily dependent upon a PHI just because
2075 : it has a phi definition for its base name. It may have a basis
2076 : that relies upon the same phi definition, in which case the PHI
2077 : is irrelevant to this candidate. */
2078 2679513 : return (c->def_phi
2079 399 : && c->basis
2080 2679910 : && lookup_cand (c->basis)->def_phi != c->def_phi);
2081 : }
2082 :
2083 : /* Calculate the increment required for candidate C relative to
2084 : its basis. */
2085 :
2086 : static offset_int
2087 1394967 : cand_increment (slsr_cand_t c)
2088 : {
2089 1394967 : slsr_cand_t basis;
2090 :
2091 : /* If the candidate doesn't have a basis, just return its own
2092 : index. This is useful in record_increments to help us find
2093 : an existing initializer. Also, if the candidate's basis is
2094 : hidden by a phi, then its own index will be the increment
2095 : from the newly introduced phi basis. */
2096 1394967 : if (!c->basis || phi_dependent_cand_p (c))
2097 36391 : return c->index;
2098 :
2099 1358576 : basis = lookup_cand (c->basis);
2100 1358576 : gcc_assert (operand_equal_p (c->base_expr, basis->base_expr, 0));
2101 1358576 : return c->index - basis->index;
2102 : }
2103 :
2104 : /* Calculate the increment required for candidate C relative to
2105 : its basis. If we aren't going to generate pointer arithmetic
2106 : for this candidate, return the absolute value of that increment
2107 : instead. */
2108 :
2109 : static inline offset_int
2110 75866 : cand_abs_increment (slsr_cand_t c)
2111 : {
2112 75866 : offset_int increment = cand_increment (c);
2113 :
2114 75866 : if (!address_arithmetic_p && wi::neg_p (increment))
2115 2324 : increment = -increment;
2116 :
2117 75866 : return increment;
2118 : }
2119 :
2120 : /* Return TRUE iff candidate C has already been replaced under
2121 : another interpretation. */
2122 :
2123 : static inline bool
2124 1517999 : cand_already_replaced (slsr_cand_t c)
2125 : {
2126 673 : return (gimple_bb (c->cand_stmt) == 0);
2127 : }
2128 :
2129 : /* Common logic used by replace_unconditional_candidate and
2130 : replace_conditional_candidate. */
2131 :
2132 : static void
2133 1193850 : replace_mult_candidate (slsr_cand_t c, tree basis_name, offset_int bump,
2134 : auto_bitmap &sdce_worklist)
2135 : {
2136 1193850 : tree target_type = TREE_TYPE (gimple_assign_lhs (c->cand_stmt));
2137 1193850 : enum tree_code cand_code = gimple_assign_rhs_code (c->cand_stmt);
2138 :
2139 : /* It is not useful to replace casts, copies, negates, or adds of
2140 : an SSA name and a constant. */
2141 1193850 : if (cand_code == SSA_NAME
2142 : || CONVERT_EXPR_CODE_P (cand_code)
2143 : || cand_code == PLUS_EXPR
2144 : || cand_code == POINTER_PLUS_EXPR
2145 : || cand_code == MINUS_EXPR
2146 : || cand_code == NEGATE_EXPR)
2147 : return;
2148 :
2149 85067 : enum tree_code code = PLUS_EXPR;
2150 85067 : tree bump_tree;
2151 85067 : gimple *stmt_to_print = NULL;
2152 :
2153 85067 : if (wi::neg_p (bump))
2154 : {
2155 7043 : code = MINUS_EXPR;
2156 7043 : bump = -bump;
2157 : }
2158 :
2159 : /* It is possible that the resulting bump doesn't fit in target_type.
2160 : Abandon the replacement in this case. This does not affect
2161 : siblings or dependents of C. */
2162 85067 : if (bump != wi::ext (bump, TYPE_PRECISION (target_type),
2163 85067 : TYPE_SIGN (target_type)))
2164 : return;
2165 :
2166 84138 : bump_tree = wide_int_to_tree (target_type, bump);
2167 :
2168 : /* If the basis name and the candidate's LHS have incompatible types,
2169 : introduce a cast. */
2170 84138 : if (!useless_type_conversion_p (target_type, TREE_TYPE (basis_name)))
2171 4751 : basis_name = introduce_cast_before_cand (c, target_type, basis_name);
2172 :
2173 84138 : if (dump_file && (dump_flags & TDF_DETAILS))
2174 : {
2175 0 : fputs ("Replacing: ", dump_file);
2176 0 : print_gimple_stmt (dump_file, c->cand_stmt, 0);
2177 : }
2178 :
2179 84138 : if (bump == 0)
2180 : {
2181 62946 : tree lhs = gimple_assign_lhs (c->cand_stmt);
2182 62946 : gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
2183 62946 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
2184 62946 : slsr_cand_t cc = lookup_cand (c->first_interp);
2185 62946 : gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
2186 62946 : gsi_replace (&gsi, copy_stmt, false);
2187 188838 : while (cc)
2188 : {
2189 62946 : cc->cand_stmt = copy_stmt;
2190 62946 : cc = lookup_cand (cc->next_interp);
2191 : }
2192 62946 : if (dump_file && (dump_flags & TDF_DETAILS))
2193 : stmt_to_print = copy_stmt;
2194 : }
2195 : else
2196 : {
2197 21192 : tree rhs1, rhs2;
2198 21192 : if (cand_code != NEGATE_EXPR) {
2199 21192 : rhs1 = gimple_assign_rhs1 (c->cand_stmt);
2200 21192 : rhs2 = gimple_assign_rhs2 (c->cand_stmt);
2201 : /* Mark the 2 original rhs for maybe DCEing. */
2202 21192 : if (TREE_CODE (rhs1) == SSA_NAME)
2203 21192 : bitmap_set_bit (sdce_worklist, SSA_NAME_VERSION (rhs1));
2204 21192 : if (TREE_CODE (rhs2) == SSA_NAME)
2205 0 : bitmap_set_bit (sdce_worklist, SSA_NAME_VERSION (rhs2));
2206 : }
2207 21192 : if (cand_code != NEGATE_EXPR
2208 21192 : && ((operand_equal_p (rhs1, basis_name, 0)
2209 0 : && operand_equal_p (rhs2, bump_tree, 0))
2210 21192 : || (operand_equal_p (rhs1, bump_tree, 0)
2211 0 : && operand_equal_p (rhs2, basis_name, 0))))
2212 : {
2213 0 : if (dump_file && (dump_flags & TDF_DETAILS))
2214 : {
2215 0 : fputs ("(duplicate, not actually replacing)", dump_file);
2216 0 : stmt_to_print = c->cand_stmt;
2217 : }
2218 : }
2219 : else
2220 : {
2221 21192 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
2222 21192 : slsr_cand_t cc = lookup_cand (c->first_interp);
2223 21192 : tree lhs = gimple_assign_lhs (c->cand_stmt);
2224 21192 : basis_name = gimple_convert (&gsi, true, GSI_SAME_STMT,
2225 : UNKNOWN_LOCATION,
2226 21192 : TREE_TYPE (lhs), basis_name);
2227 21192 : bump_tree = gimple_convert (&gsi, true, GSI_SAME_STMT,
2228 : UNKNOWN_LOCATION,
2229 21192 : TREE_TYPE (lhs), bump_tree);
2230 21192 : gimple_assign_set_rhs_with_ops (&gsi, code, basis_name, bump_tree);
2231 21192 : update_stmt (gsi_stmt (gsi));
2232 63576 : while (cc)
2233 : {
2234 21192 : cc->cand_stmt = gsi_stmt (gsi);
2235 21192 : cc = lookup_cand (cc->next_interp);
2236 : }
2237 21192 : if (gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
2238 7797 : rewrite_to_defined_unconditional (&gsi);
2239 :
2240 21192 : if (dump_file && (dump_flags & TDF_DETAILS))
2241 0 : stmt_to_print = gsi_stmt (gsi);
2242 : }
2243 : }
2244 :
2245 84138 : if (dump_file && (dump_flags & TDF_DETAILS))
2246 : {
2247 0 : fputs ("With: ", dump_file);
2248 0 : print_gimple_stmt (dump_file, stmt_to_print, 0);
2249 0 : fputs ("\n", dump_file);
2250 : }
2251 : }
2252 :
2253 : /* Replace candidate C with an add or subtract. Note that we only
2254 : operate on CAND_MULTs with known strides, so we will never generate
2255 : a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
2256 : X = Y + ((i - i') * S), as described in the module commentary. The
2257 : folded value ((i - i') * S) is referred to here as the "bump." */
2258 :
2259 : static void
2260 1193841 : replace_unconditional_candidate (slsr_cand_t c, auto_bitmap &sdce_worklist)
2261 : {
2262 1193841 : slsr_cand_t basis;
2263 :
2264 1193841 : if (cand_already_replaced (c))
2265 0 : return;
2266 :
2267 1193841 : basis = lookup_cand (c->basis);
2268 1193841 : offset_int bump = cand_increment (c) * wi::to_offset (c->stride);
2269 :
2270 1193841 : replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump,
2271 : sdce_worklist);
2272 : }
2273 :
2274 : /* Return the index in the increment vector of the given INCREMENT,
2275 : or -1 if not found. The latter can occur if more than
2276 : MAX_INCR_VEC_LEN increments have been found. */
2277 :
2278 : static inline int
2279 70075 : incr_vec_index (const offset_int &increment)
2280 : {
2281 70075 : unsigned i;
2282 :
2283 126012 : for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++)
2284 : ;
2285 :
2286 70075 : if (i < incr_vec_len)
2287 : return i;
2288 : else
2289 0 : return -1;
2290 : }
2291 :
2292 : /* Create a new statement along edge E to add BASIS_NAME to the product
2293 : of INCREMENT and the stride of candidate C. Create and return a new
2294 : SSA name from *VAR to be used as the LHS of the new statement.
2295 : KNOWN_STRIDE is true iff C's stride is a constant. */
2296 :
2297 : static tree
2298 25 : create_add_on_incoming_edge (slsr_cand_t c, tree basis_name,
2299 : offset_int increment, edge e, location_t loc,
2300 : bool known_stride)
2301 : {
2302 25 : tree lhs, basis_type;
2303 25 : gassign *new_stmt, *cast_stmt = NULL;
2304 :
2305 : /* If the add candidate along this incoming edge has the same
2306 : index as C's hidden basis, the hidden basis represents this
2307 : edge correctly. */
2308 25 : if (increment == 0)
2309 : return basis_name;
2310 :
2311 21 : basis_type = TREE_TYPE (basis_name);
2312 21 : lhs = make_temp_ssa_name (basis_type, NULL, "slsr");
2313 :
2314 : /* Occasionally people convert integers to pointers without a
2315 : cast, leading us into trouble if we aren't careful. */
2316 21 : enum tree_code plus_code
2317 21 : = POINTER_TYPE_P (basis_type) ? POINTER_PLUS_EXPR : PLUS_EXPR;
2318 :
2319 21 : if (known_stride)
2320 : {
2321 13 : tree bump_tree;
2322 13 : enum tree_code code = plus_code;
2323 13 : offset_int bump = increment * wi::to_offset (c->stride);
2324 13 : if (wi::neg_p (bump) && !POINTER_TYPE_P (basis_type))
2325 : {
2326 5 : code = MINUS_EXPR;
2327 5 : bump = -bump;
2328 : }
2329 :
2330 13 : tree stride_type = POINTER_TYPE_P (basis_type) ? sizetype : basis_type;
2331 13 : bump_tree = wide_int_to_tree (stride_type, bump);
2332 13 : new_stmt = gimple_build_assign (lhs, code, basis_name, bump_tree);
2333 : }
2334 : else
2335 : {
2336 8 : int i;
2337 8 : bool negate_incr = !POINTER_TYPE_P (basis_type) && wi::neg_p (increment);
2338 8 : i = incr_vec_index (negate_incr ? -increment : increment);
2339 8 : gcc_assert (i >= 0);
2340 :
2341 8 : if (incr_vec[i].initializer)
2342 : {
2343 8 : tree init = incr_vec[i].initializer;
2344 8 : tree wanted_type = POINTER_TYPE_P (basis_type) ? c->stride_type : basis_type;
2345 :
2346 8 : if (!types_compatible_p (TREE_TYPE (c->stride), wanted_type))
2347 : {
2348 2 : tree cast_stride = make_temp_ssa_name (wanted_type, NULL,
2349 : "slsr");
2350 2 : cast_stmt = gimple_build_assign (cast_stride, NOP_EXPR,
2351 : init);
2352 2 : init = cast_stride;
2353 : }
2354 8 : enum tree_code code = negate_incr ? MINUS_EXPR : plus_code;
2355 8 : new_stmt = gimple_build_assign (lhs, code, basis_name, init);
2356 : }
2357 : else {
2358 0 : tree stride;
2359 0 : tree wanted_type = POINTER_TYPE_P (basis_type) ? c->stride_type : basis_type;
2360 :
2361 0 : if (!types_compatible_p (TREE_TYPE (c->stride), wanted_type))
2362 : {
2363 0 : tree cast_stride = make_temp_ssa_name (wanted_type, NULL,
2364 : "slsr");
2365 0 : cast_stmt = gimple_build_assign (cast_stride, NOP_EXPR,
2366 : c->stride);
2367 0 : stride = cast_stride;
2368 : }
2369 : else
2370 0 : stride = c->stride;
2371 :
2372 0 : if (increment == 1)
2373 0 : new_stmt = gimple_build_assign (lhs, plus_code, basis_name, stride);
2374 0 : else if (increment == -1)
2375 0 : new_stmt = gimple_build_assign (lhs, MINUS_EXPR, basis_name, stride);
2376 : else
2377 0 : gcc_unreachable ();
2378 : }
2379 : }
2380 :
2381 21 : if (cast_stmt)
2382 : {
2383 2 : gimple_set_location (cast_stmt, loc);
2384 2 : gsi_insert_on_edge (e, cast_stmt);
2385 : }
2386 :
2387 21 : gimple_set_location (new_stmt, loc);
2388 21 : if (gimple_needing_rewrite_undefined (new_stmt))
2389 : {
2390 3 : gimple_seq stmts;
2391 3 : stmts = rewrite_to_defined_unconditional (new_stmt);
2392 3 : gsi_insert_seq_on_edge (e, stmts);
2393 : }
2394 : else
2395 18 : gsi_insert_on_edge (e, new_stmt);
2396 :
2397 21 : if (dump_file && (dump_flags & TDF_DETAILS))
2398 : {
2399 0 : if (cast_stmt)
2400 : {
2401 0 : fprintf (dump_file, "Inserting cast on edge %d->%d: ",
2402 0 : e->src->index, e->dest->index);
2403 0 : print_gimple_stmt (dump_file, cast_stmt, 0);
2404 : }
2405 0 : fprintf (dump_file, "Inserting on edge %d->%d: ", e->src->index,
2406 0 : e->dest->index);
2407 0 : print_gimple_stmt (dump_file, new_stmt, 0);
2408 : }
2409 :
2410 : return lhs;
2411 : }
2412 :
2413 : /* Clear the visited field for a tree of PHI candidates. */
2414 :
2415 : static void
2416 80 : clear_visited (gphi *phi)
2417 : {
2418 80 : unsigned i;
2419 80 : slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
2420 :
2421 80 : if (phi_cand->visited)
2422 : {
2423 80 : phi_cand->visited = 0;
2424 :
2425 242 : for (i = 0; i < gimple_phi_num_args (phi); i++)
2426 : {
2427 162 : tree arg = gimple_phi_arg_def (phi, i);
2428 162 : gimple *arg_def = SSA_NAME_DEF_STMT (arg);
2429 162 : if (gimple_code (arg_def) == GIMPLE_PHI)
2430 2 : clear_visited (as_a <gphi *> (arg_def));
2431 : }
2432 : }
2433 80 : }
2434 :
2435 : /* Recursive helper function for create_phi_basis. */
2436 :
2437 : static tree
2438 18 : create_phi_basis_1 (slsr_cand_t c, gimple *from_phi, tree basis_name,
2439 : location_t loc, bool known_stride)
2440 : {
2441 18 : int i;
2442 18 : tree name, phi_arg;
2443 18 : gphi *phi;
2444 18 : slsr_cand_t basis = lookup_cand (c->basis);
2445 18 : int nargs = gimple_phi_num_args (from_phi);
2446 18 : basic_block phi_bb = gimple_bb (from_phi);
2447 18 : slsr_cand_t phi_cand = *stmt_cand_map->get (from_phi);
2448 18 : auto_vec<tree> phi_args (nargs);
2449 :
2450 18 : if (phi_cand->visited)
2451 0 : return phi_cand->cached_basis;
2452 18 : phi_cand->visited = 1;
2453 :
2454 : /* Process each argument of the existing phi that represents
2455 : conditionally-executed add candidates. */
2456 51 : for (i = 0; i < nargs; i++)
2457 : {
2458 33 : edge e = (*phi_bb->preds)[i];
2459 33 : tree arg = gimple_phi_arg_def (from_phi, i);
2460 33 : tree feeding_def;
2461 :
2462 : /* If the phi argument is the base name of the CAND_PHI, then
2463 : this incoming arc should use the hidden basis. */
2464 33 : if (operand_equal_p (arg, phi_cand->base_expr, 0))
2465 7 : if (basis->index == 0)
2466 7 : feeding_def = gimple_assign_lhs (basis->cand_stmt);
2467 : else
2468 : {
2469 0 : offset_int incr = -basis->index;
2470 0 : feeding_def = create_add_on_incoming_edge (c, basis_name, incr,
2471 : e, loc, known_stride);
2472 : }
2473 : else
2474 : {
2475 26 : gimple *arg_def = SSA_NAME_DEF_STMT (arg);
2476 :
2477 : /* If there is another phi along this incoming edge, we must
2478 : process it in the same fashion to ensure that all basis
2479 : adjustments are made along its incoming edges. */
2480 26 : if (gimple_code (arg_def) == GIMPLE_PHI)
2481 1 : feeding_def = create_phi_basis_1 (c, arg_def, basis_name,
2482 : loc, known_stride);
2483 : else
2484 : {
2485 25 : slsr_cand_t arg_cand = base_cand_from_table (arg);
2486 25 : offset_int diff = arg_cand->index - basis->index;
2487 25 : feeding_def = create_add_on_incoming_edge (c, basis_name, diff,
2488 : e, loc, known_stride);
2489 : }
2490 : }
2491 :
2492 : /* Because of recursion, we need to save the arguments in a vector
2493 : so we can create the PHI statement all at once. Otherwise the
2494 : storage for the half-created PHI can be reclaimed. */
2495 33 : phi_args.safe_push (feeding_def);
2496 : }
2497 :
2498 : /* Create the new phi basis. */
2499 18 : name = make_temp_ssa_name (TREE_TYPE (basis_name), NULL, "slsr");
2500 18 : phi = create_phi_node (name, phi_bb);
2501 18 : SSA_NAME_DEF_STMT (name) = phi;
2502 :
2503 51 : FOR_EACH_VEC_ELT (phi_args, i, phi_arg)
2504 : {
2505 33 : edge e = (*phi_bb->preds)[i];
2506 33 : add_phi_arg (phi, phi_arg, e, loc);
2507 : }
2508 :
2509 18 : update_stmt (phi);
2510 :
2511 18 : if (dump_file && (dump_flags & TDF_DETAILS))
2512 : {
2513 0 : fputs ("Introducing new phi basis: ", dump_file);
2514 0 : print_gimple_stmt (dump_file, phi, 0);
2515 : }
2516 :
2517 18 : phi_cand->cached_basis = name;
2518 18 : return name;
2519 18 : }
2520 :
2521 : /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2522 : is hidden by the phi node FROM_PHI, create a new phi node in the same
2523 : block as FROM_PHI. The new phi is suitable for use as a basis by C,
2524 : with its phi arguments representing conditional adjustments to the
2525 : hidden basis along conditional incoming paths. Those adjustments are
2526 : made by creating add statements (and sometimes recursively creating
2527 : phis) along those incoming paths. LOC is the location to attach to
2528 : the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2529 : constant. */
2530 :
2531 : static tree
2532 17 : create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name,
2533 : location_t loc, bool known_stride)
2534 : {
2535 17 : tree retval = create_phi_basis_1 (c, from_phi, basis_name, loc,
2536 : known_stride);
2537 17 : gcc_assert (retval);
2538 17 : clear_visited (as_a <gphi *> (from_phi));
2539 17 : return retval;
2540 : }
2541 :
2542 : /* Given a candidate C whose basis is hidden by at least one intervening
2543 : phi, introduce a matching number of new phis to represent its basis
2544 : adjusted by conditional increments along possible incoming paths. Then
2545 : replace C as though it were an unconditional candidate, using the new
2546 : basis. */
2547 :
2548 : static void
2549 9 : replace_conditional_candidate (slsr_cand_t c, auto_bitmap &sdce_worklist)
2550 :
2551 : {
2552 9 : tree basis_name, name;
2553 9 : slsr_cand_t basis;
2554 9 : location_t loc;
2555 :
2556 : /* Look up the LHS SSA name from C's basis. This will be the
2557 : RHS1 of the adds we will introduce to create new phi arguments. */
2558 9 : basis = lookup_cand (c->basis);
2559 9 : basis_name = gimple_assign_lhs (basis->cand_stmt);
2560 :
2561 : /* Create a new phi statement which will represent C's true basis
2562 : after the transformation is complete. */
2563 9 : loc = gimple_location (c->cand_stmt);
2564 9 : name = create_phi_basis (c, lookup_cand (c->def_phi)->cand_stmt,
2565 : basis_name, loc, KNOWN_STRIDE);
2566 :
2567 : /* Replace C with an add of the new basis phi and a constant. */
2568 9 : offset_int bump = c->index * wi::to_offset (c->stride);
2569 :
2570 9 : replace_mult_candidate (c, name, bump, sdce_worklist);
2571 9 : }
2572 :
2573 : /* Recursive helper function for phi_add_costs. SPREAD is a measure of
2574 : how many PHI nodes we have visited at this point in the tree walk. */
2575 :
2576 : static int
2577 23 : phi_add_costs_1 (gimple *phi, slsr_cand_t c, int one_add_cost, int *spread)
2578 : {
2579 23 : unsigned i;
2580 23 : int cost = 0;
2581 23 : slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
2582 :
2583 23 : if (phi_cand->visited)
2584 : return 0;
2585 :
2586 23 : phi_cand->visited = 1;
2587 23 : (*spread)++;
2588 :
2589 : /* If we work our way back to a phi that isn't dominated by the hidden
2590 : basis, this isn't a candidate for replacement. Indicate this by
2591 : returning an unreasonably high cost. It's not easy to detect
2592 : these situations when determining the basis, so we defer the
2593 : decision until now. */
2594 23 : basic_block phi_bb = gimple_bb (phi);
2595 23 : slsr_cand_t basis = lookup_cand (c->basis);
2596 23 : basic_block basis_bb = gimple_bb (basis->cand_stmt);
2597 :
2598 23 : if (phi_bb == basis_bb || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
2599 0 : return COST_INFINITE;
2600 :
2601 74 : for (i = 0; i < gimple_phi_num_args (phi); i++)
2602 : {
2603 51 : tree arg = gimple_phi_arg_def (phi, i);
2604 :
2605 51 : if (arg != phi_cand->base_expr)
2606 : {
2607 50 : gimple *arg_def = SSA_NAME_DEF_STMT (arg);
2608 :
2609 50 : if (gimple_code (arg_def) == GIMPLE_PHI)
2610 : {
2611 1 : cost += phi_add_costs_1 (arg_def, c, one_add_cost, spread);
2612 :
2613 1 : if (cost >= COST_INFINITE || *spread > MAX_SPREAD)
2614 : return COST_INFINITE;
2615 : }
2616 : else
2617 : {
2618 49 : slsr_cand_t arg_cand = base_cand_from_table (arg);
2619 :
2620 49 : if (arg_cand->index != c->index)
2621 46 : cost += one_add_cost;
2622 : }
2623 : }
2624 : }
2625 :
2626 : return cost;
2627 : }
2628 :
2629 : /* Compute the expected costs of inserting basis adjustments for
2630 : candidate C with phi-definition PHI. The cost of inserting
2631 : one adjustment is given by ONE_ADD_COST. If PHI has arguments
2632 : which are themselves phi results, recursively calculate costs
2633 : for those phis as well. */
2634 :
2635 : static int
2636 22 : phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost)
2637 : {
2638 22 : int spread = 0;
2639 22 : int retval = phi_add_costs_1 (phi, c, one_add_cost, &spread);
2640 22 : clear_visited (as_a <gphi *> (phi));
2641 22 : return retval;
2642 : }
2643 : /* For candidate C, each sibling of candidate C, and each dependent of
2644 : candidate C, determine whether the candidate is dependent upon a
2645 : phi that hides its basis. If not, replace the candidate unconditionally.
2646 : Otherwise, determine whether the cost of introducing compensation code
2647 : for the candidate is offset by the gains from strength reduction. If
2648 : so, replace the candidate and introduce the compensation code. */
2649 :
2650 : static void
2651 622796 : replace_uncond_cands_and_profitable_phis (slsr_cand_t c,
2652 : auto_bitmap &sdce_worklist)
2653 : {
2654 1193892 : if (phi_dependent_cand_p (c))
2655 : {
2656 : /* A multiply candidate with a stride of 1 is just an artifice
2657 : of a copy or cast; there is no value in replacing it. */
2658 51 : if (c->kind == CAND_MULT && wi::to_offset (c->stride) != 1)
2659 : {
2660 : /* A candidate dependent upon a phi will replace a multiply by
2661 : a constant with an add, and will insert at most one add for
2662 : each phi argument. Add these costs with the potential dead-code
2663 : savings to determine profitability. */
2664 22 : bool speed = optimize_bb_for_speed_p (gimple_bb (c->cand_stmt));
2665 22 : int mult_savings = stmt_cost (c->cand_stmt, speed);
2666 22 : gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
2667 22 : tree phi_result = gimple_phi_result (phi);
2668 88 : int one_add_cost = add_cost (speed,
2669 22 : TYPE_MODE (TREE_TYPE (phi_result)));
2670 22 : int add_costs = one_add_cost + phi_add_costs (phi, c, one_add_cost);
2671 22 : int cost = add_costs - mult_savings - c->dead_savings;
2672 :
2673 22 : if (dump_file && (dump_flags & TDF_DETAILS))
2674 : {
2675 0 : fprintf (dump_file, " Conditional candidate %d:\n", c->cand_num);
2676 0 : fprintf (dump_file, " add_costs = %d\n", add_costs);
2677 0 : fprintf (dump_file, " mult_savings = %d\n", mult_savings);
2678 0 : fprintf (dump_file, " dead_savings = %d\n", c->dead_savings);
2679 0 : fprintf (dump_file, " cost = %d\n", cost);
2680 0 : if (cost <= COST_NEUTRAL)
2681 0 : fputs (" Replacing...\n", dump_file);
2682 : else
2683 0 : fputs (" Not replaced.\n", dump_file);
2684 : }
2685 :
2686 22 : if (cost <= COST_NEUTRAL)
2687 9 : replace_conditional_candidate (c, sdce_worklist);
2688 : }
2689 : }
2690 : else
2691 1193841 : replace_unconditional_candidate (c, sdce_worklist);
2692 :
2693 1193892 : if (c->sibling)
2694 45585 : replace_uncond_cands_and_profitable_phis (lookup_cand (c->sibling),
2695 : sdce_worklist);
2696 :
2697 1193892 : if (c->dependent)
2698 571096 : replace_uncond_cands_and_profitable_phis (lookup_cand (c->dependent),
2699 : sdce_worklist);
2700 622796 : }
2701 :
2702 : /* Count the number of candidates in the tree rooted at C that have
2703 : not already been replaced under other interpretations. */
2704 :
2705 : static int
2706 39581 : count_candidates (slsr_cand_t c)
2707 : {
2708 106394 : unsigned count = cand_already_replaced (c) ? 0 : 1;
2709 :
2710 106394 : if (c->sibling)
2711 3233 : count += count_candidates (lookup_cand (c->sibling));
2712 :
2713 106394 : if (c->dependent)
2714 66813 : count += count_candidates (lookup_cand (c->dependent));
2715 :
2716 39581 : return count;
2717 : }
2718 :
2719 : /* Increase the count of INCREMENT by one in the increment vector.
2720 : INCREMENT is associated with candidate C. If INCREMENT is to be
2721 : conditionally executed as part of a conditional candidate replacement,
2722 : IS_PHI_ADJUST is true, otherwise false. If an initializer
2723 : T_0 = stride * I is provided by a candidate that dominates all
2724 : candidates with the same increment, also record T_0 for subsequent use. */
2725 :
2726 : static void
2727 106418 : record_increment (slsr_cand_t c, offset_int increment, bool is_phi_adjust)
2728 : {
2729 106418 : bool found = false;
2730 106418 : unsigned i;
2731 :
2732 : /* Treat increments that differ only in sign as identical so as to
2733 : share initializers, unless we are generating pointer arithmetic. */
2734 106418 : if (!address_arithmetic_p && wi::neg_p (increment))
2735 6100 : increment = -increment;
2736 :
2737 162348 : for (i = 0; i < incr_vec_len; i++)
2738 : {
2739 96454 : if (incr_vec[i].incr == increment)
2740 : {
2741 40524 : incr_vec[i].count++;
2742 40524 : found = true;
2743 :
2744 : /* If we previously recorded an initializer that doesn't
2745 : dominate this candidate, it's not going to be useful to
2746 : us after all. */
2747 40524 : if (incr_vec[i].initializer
2748 40524 : && !dominated_by_p (CDI_DOMINATORS,
2749 918 : gimple_bb (c->cand_stmt),
2750 918 : incr_vec[i].init_bb))
2751 : {
2752 0 : incr_vec[i].initializer = NULL_TREE;
2753 0 : incr_vec[i].init_bb = NULL;
2754 : }
2755 :
2756 : break;
2757 : }
2758 : }
2759 :
2760 65894 : if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1)
2761 : {
2762 : /* The first time we see an increment, create the entry for it.
2763 : If this is the root candidate which doesn't have a basis, set
2764 : the count to zero. We're only processing it so it can possibly
2765 : provide an initializer for other candidates. */
2766 65894 : incr_vec[incr_vec_len].incr = increment;
2767 65894 : incr_vec[incr_vec_len].count = c->basis || is_phi_adjust ? 1 : 0;
2768 65894 : incr_vec[incr_vec_len].cost = COST_INFINITE;
2769 :
2770 : /* Optimistically record the first occurrence of this increment
2771 : as providing an initializer (if it does); we will revise this
2772 : opinion later if it doesn't dominate all other occurrences.
2773 : Exception: increments of 0, 1 never need initializers;
2774 : and phi adjustments don't ever provide initializers. */
2775 65894 : if (c->kind == CAND_ADD
2776 55940 : && !is_phi_adjust
2777 55928 : && c->index == increment
2778 23815 : && (increment > 1 || increment < 0)
2779 71227 : && (gimple_assign_rhs_code (c->cand_stmt) == PLUS_EXPR
2780 3356 : || gimple_assign_rhs_code (c->cand_stmt) == POINTER_PLUS_EXPR))
2781 : {
2782 4007 : tree t0 = NULL_TREE;
2783 4007 : tree rhs1 = gimple_assign_rhs1 (c->cand_stmt);
2784 4007 : tree rhs2 = gimple_assign_rhs2 (c->cand_stmt);
2785 4007 : if (operand_equal_p (rhs1, c->base_expr, 0))
2786 : t0 = rhs2;
2787 707 : else if (operand_equal_p (rhs2, c->base_expr, 0))
2788 : t0 = rhs1;
2789 4001 : if (t0
2790 4001 : && SSA_NAME_DEF_STMT (t0)
2791 8002 : && gimple_bb (SSA_NAME_DEF_STMT (t0)))
2792 : {
2793 4001 : incr_vec[incr_vec_len].initializer = t0;
2794 4001 : incr_vec[incr_vec_len++].init_bb
2795 4001 : = gimple_bb (SSA_NAME_DEF_STMT (t0));
2796 : }
2797 : else
2798 : {
2799 6 : incr_vec[incr_vec_len].initializer = NULL_TREE;
2800 6 : incr_vec[incr_vec_len++].init_bb = NULL;
2801 : }
2802 : }
2803 : else
2804 : {
2805 61887 : incr_vec[incr_vec_len].initializer = NULL_TREE;
2806 61887 : incr_vec[incr_vec_len++].init_bb = NULL;
2807 : }
2808 : }
2809 106418 : }
2810 :
2811 : /* Recursive helper function for record_phi_increments. */
2812 :
2813 : static void
2814 12 : record_phi_increments_1 (slsr_cand_t basis, gimple *phi)
2815 : {
2816 12 : unsigned i;
2817 12 : slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
2818 :
2819 12 : if (phi_cand->visited)
2820 : return;
2821 12 : phi_cand->visited = 1;
2822 :
2823 36 : for (i = 0; i < gimple_phi_num_args (phi); i++)
2824 : {
2825 24 : tree arg = gimple_phi_arg_def (phi, i);
2826 24 : gimple *arg_def = SSA_NAME_DEF_STMT (arg);
2827 :
2828 24 : if (gimple_code (arg_def) == GIMPLE_PHI)
2829 0 : record_phi_increments_1 (basis, arg_def);
2830 : else
2831 : {
2832 24 : offset_int diff;
2833 :
2834 24 : if (operand_equal_p (arg, phi_cand->base_expr, 0))
2835 : {
2836 7 : diff = -basis->index;
2837 7 : record_increment (phi_cand, diff, PHI_ADJUST);
2838 : }
2839 : else
2840 : {
2841 17 : slsr_cand_t arg_cand = base_cand_from_table (arg);
2842 17 : diff = arg_cand->index - basis->index;
2843 17 : record_increment (arg_cand, diff, PHI_ADJUST);
2844 : }
2845 : }
2846 : }
2847 : }
2848 :
2849 : /* Given phi statement PHI that hides a candidate from its BASIS, find
2850 : the increments along each incoming arc (recursively handling additional
2851 : phis that may be present) and record them. These increments are the
2852 : difference in index between the index-adjusting statements and the
2853 : index of the basis. */
2854 :
2855 : static void
2856 12 : record_phi_increments (slsr_cand_t basis, gimple *phi)
2857 : {
2858 12 : record_phi_increments_1 (basis, phi);
2859 12 : clear_visited (as_a <gphi *> (phi));
2860 12 : }
2861 :
2862 : /* Determine how many times each unique increment occurs in the set
2863 : of candidates rooted at C's parent, recording the data in the
2864 : increment vector. For each unique increment I, if an initializer
2865 : T_0 = stride * I is provided by a candidate that dominates all
2866 : candidates with the same increment, also record T_0 for subsequent
2867 : use. */
2868 :
2869 : static void
2870 39581 : record_increments (slsr_cand_t c)
2871 : {
2872 106394 : if (!cand_already_replaced (c))
2873 : {
2874 106394 : if (!phi_dependent_cand_p (c))
2875 106382 : record_increment (c, cand_increment (c), NOT_PHI_ADJUST);
2876 : else
2877 : {
2878 : /* A candidate with a basis hidden by a phi will have one
2879 : increment for its relationship to the index represented by
2880 : the phi, and potentially additional increments along each
2881 : incoming edge. For the root of the dependency tree (which
2882 : has no basis), process just the initial index in case it has
2883 : an initializer that can be used by subsequent candidates. */
2884 12 : record_increment (c, c->index, NOT_PHI_ADJUST);
2885 :
2886 12 : if (c->basis)
2887 12 : record_phi_increments (lookup_cand (c->basis),
2888 12 : lookup_cand (c->def_phi)->cand_stmt);
2889 : }
2890 : }
2891 :
2892 106394 : if (c->sibling)
2893 3233 : record_increments (lookup_cand (c->sibling));
2894 :
2895 106394 : if (c->dependent)
2896 66813 : record_increments (lookup_cand (c->dependent));
2897 39581 : }
2898 :
2899 : /* Recursive helper function for phi_incr_cost. */
2900 :
2901 : static int
2902 15 : phi_incr_cost_1 (slsr_cand_t c, const offset_int &incr, gimple *phi,
2903 : int *savings)
2904 : {
2905 15 : unsigned i;
2906 15 : int cost = 0;
2907 15 : slsr_cand_t basis = lookup_cand (c->basis);
2908 15 : slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
2909 :
2910 15 : if (phi_cand->visited)
2911 : return 0;
2912 15 : phi_cand->visited = 1;
2913 :
2914 45 : for (i = 0; i < gimple_phi_num_args (phi); i++)
2915 : {
2916 30 : tree arg = gimple_phi_arg_def (phi, i);
2917 30 : gimple *arg_def = SSA_NAME_DEF_STMT (arg);
2918 :
2919 30 : if (gimple_code (arg_def) == GIMPLE_PHI)
2920 : {
2921 0 : int feeding_savings = 0;
2922 0 : tree feeding_var = gimple_phi_result (arg_def);
2923 0 : cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
2924 0 : if (uses_consumed_by_stmt (feeding_var, phi))
2925 0 : *savings += feeding_savings;
2926 : }
2927 : else
2928 : {
2929 30 : offset_int diff;
2930 30 : slsr_cand_t arg_cand;
2931 :
2932 : /* When the PHI argument is just a pass-through to the base
2933 : expression of the hidden basis, the difference is zero minus
2934 : the index of the basis. There is no potential savings by
2935 : eliminating a statement in this case. */
2936 30 : if (operand_equal_p (arg, phi_cand->base_expr, 0))
2937 : {
2938 7 : arg_cand = (slsr_cand_t)NULL;
2939 7 : diff = -basis->index;
2940 : }
2941 : else
2942 : {
2943 23 : arg_cand = base_cand_from_table (arg);
2944 23 : diff = arg_cand->index - basis->index;
2945 : }
2946 :
2947 30 : if (incr == diff)
2948 : {
2949 14 : tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
2950 14 : cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
2951 14 : if (arg_cand)
2952 : {
2953 14 : tree lhs = gimple_assign_lhs (arg_cand->cand_stmt);
2954 14 : if (uses_consumed_by_stmt (lhs, phi))
2955 14 : *savings += stmt_cost (arg_cand->cand_stmt, true);
2956 : }
2957 : }
2958 : }
2959 : }
2960 :
2961 : return cost;
2962 : }
2963 :
2964 : /* Add up and return the costs of introducing add statements that
2965 : require the increment INCR on behalf of candidate C and phi
2966 : statement PHI. Accumulate into *SAVINGS the potential savings
2967 : from removing existing statements that feed PHI and have no other
2968 : uses. */
2969 :
2970 : static int
2971 15 : phi_incr_cost (slsr_cand_t c, const offset_int &incr, gimple *phi,
2972 : int *savings)
2973 : {
2974 15 : int retval = phi_incr_cost_1 (c, incr, phi, savings);
2975 15 : clear_visited (as_a <gphi *> (phi));
2976 15 : return retval;
2977 : }
2978 :
2979 : /* Return the first candidate in the tree rooted at C that has not
2980 : already been replaced, favoring siblings over dependents. */
2981 :
2982 : static slsr_cand_t
2983 36348 : unreplaced_cand_in_tree (slsr_cand_t c)
2984 : {
2985 36348 : if (!cand_already_replaced (c))
2986 : return c;
2987 :
2988 0 : if (c->sibling)
2989 : {
2990 0 : slsr_cand_t sib = unreplaced_cand_in_tree (lookup_cand (c->sibling));
2991 0 : if (sib)
2992 : return sib;
2993 : }
2994 :
2995 0 : if (c->dependent)
2996 : {
2997 0 : slsr_cand_t dep = unreplaced_cand_in_tree (lookup_cand (c->dependent));
2998 0 : if (dep)
2999 : return dep;
3000 : }
3001 :
3002 : return NULL;
3003 : }
3004 :
3005 : /* Return TRUE if the candidates in the tree rooted at C should be
3006 : optimized for speed, else FALSE. We estimate this based on the block
3007 : containing the most dominant candidate in the tree that has not yet
3008 : been replaced. */
3009 :
3010 : static bool
3011 36348 : optimize_cands_for_speed_p (slsr_cand_t c)
3012 : {
3013 36348 : slsr_cand_t c2 = unreplaced_cand_in_tree (c);
3014 36348 : gcc_assert (c2);
3015 36348 : return optimize_bb_for_speed_p (gimple_bb (c2->cand_stmt));
3016 : }
3017 :
3018 : /* Add COST_IN to the lowest cost of any dependent path starting at
3019 : candidate C or any of its siblings, counting only candidates along
3020 : such paths with increment INCR. Assume that replacing a candidate
3021 : reduces cost by REPL_SAVINGS. Also account for savings from any
3022 : statements that would go dead. If COUNT_PHIS is true, include
3023 : costs of introducing feeding statements for conditional candidates. */
3024 :
3025 : static int
3026 4303 : lowest_cost_path (int cost_in, int repl_savings, slsr_cand_t c,
3027 : const offset_int &incr, bool count_phis)
3028 : {
3029 4303 : int local_cost, sib_cost, savings = 0;
3030 4303 : offset_int cand_incr = cand_abs_increment (c);
3031 :
3032 4303 : if (cand_already_replaced (c))
3033 : local_cost = cost_in;
3034 4303 : else if (incr == cand_incr)
3035 3009 : local_cost = cost_in - repl_savings - c->dead_savings;
3036 : else
3037 1294 : local_cost = cost_in - c->dead_savings;
3038 :
3039 4303 : if (count_phis
3040 292 : && phi_dependent_cand_p (c)
3041 4317 : && !cand_already_replaced (c))
3042 : {
3043 14 : gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
3044 14 : local_cost += phi_incr_cost (c, incr, phi, &savings);
3045 :
3046 14 : if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt))
3047 8 : local_cost -= savings;
3048 : }
3049 :
3050 4303 : if (c->dependent)
3051 1802 : local_cost = lowest_cost_path (local_cost, repl_savings,
3052 : lookup_cand (c->dependent), incr,
3053 : count_phis);
3054 :
3055 4303 : if (c->sibling)
3056 : {
3057 86 : sib_cost = lowest_cost_path (cost_in, repl_savings,
3058 : lookup_cand (c->sibling), incr,
3059 : count_phis);
3060 86 : local_cost = MIN (local_cost, sib_cost);
3061 : }
3062 :
3063 4303 : return local_cost;
3064 : }
3065 :
3066 : /* Compute the total savings that would accrue from all replacements
3067 : in the candidate tree rooted at C, counting only candidates with
3068 : increment INCR. Assume that replacing a candidate reduces cost
3069 : by REPL_SAVINGS. Also account for savings from statements that
3070 : would go dead. */
3071 :
3072 : static int
3073 185 : total_savings (int repl_savings, slsr_cand_t c, const offset_int &incr,
3074 : bool count_phis)
3075 : {
3076 185 : int savings = 0;
3077 185 : offset_int cand_incr = cand_abs_increment (c);
3078 :
3079 185 : if (incr == cand_incr && !cand_already_replaced (c))
3080 140 : savings += repl_savings + c->dead_savings;
3081 :
3082 185 : if (count_phis
3083 102 : && phi_dependent_cand_p (c)
3084 186 : && !cand_already_replaced (c))
3085 : {
3086 1 : int phi_savings = 0;
3087 1 : gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
3088 1 : savings -= phi_incr_cost (c, incr, phi, &phi_savings);
3089 :
3090 1 : if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt))
3091 1 : savings += phi_savings;
3092 : }
3093 :
3094 185 : if (c->dependent)
3095 106 : savings += total_savings (repl_savings, lookup_cand (c->dependent), incr,
3096 : count_phis);
3097 :
3098 185 : if (c->sibling)
3099 0 : savings += total_savings (repl_savings, lookup_cand (c->sibling), incr,
3100 : count_phis);
3101 :
3102 185 : return savings;
3103 : }
3104 :
3105 : /* Use target-specific costs to determine and record which increments
3106 : in the current candidate tree are profitable to replace, assuming
3107 : MODE and SPEED. FIRST_DEP is the first dependent of the root of
3108 : the candidate tree.
3109 :
3110 : One slight limitation here is that we don't account for the possible
3111 : introduction of casts in some cases. See replace_one_candidate for
3112 : the cases where these are introduced. This should probably be cleaned
3113 : up sometime. */
3114 :
3115 : static void
3116 36348 : analyze_increments (slsr_cand_t first_dep, machine_mode mode, bool speed)
3117 : {
3118 36348 : unsigned i;
3119 :
3120 102242 : for (i = 0; i < incr_vec_len; i++)
3121 : {
3122 65894 : HOST_WIDE_INT incr = incr_vec[i].incr.to_shwi ();
3123 :
3124 : /* If somehow this increment is bigger than a HWI, we won't
3125 : be optimizing candidates that use it. And if the increment
3126 : has a count of zero, nothing will be done with it. */
3127 65894 : if (!wi::fits_shwi_p (incr_vec[i].incr) || !incr_vec[i].count)
3128 29021 : incr_vec[i].cost = COST_INFINITE;
3129 :
3130 : /* Increments of 0, 1, and -1 are always profitable to replace,
3131 : because they always replace a multiply or add with an add or
3132 : copy, and may cause one or more existing instructions to go
3133 : dead. Exception: -1 can't be assumed to be profitable for
3134 : pointer addition. */
3135 36873 : else if (incr == 0
3136 36873 : || incr == 1
3137 2548 : || (incr == -1
3138 6 : && !POINTER_TYPE_P (first_dep->cand_type)))
3139 34325 : incr_vec[i].cost = COST_NEUTRAL;
3140 :
3141 : /* If we need to add an initializer, give up if a cast from the
3142 : candidate's type to its stride's type can lose precision.
3143 : Note that this already takes into account that the stride may
3144 : have been cast to a wider type, in which case this test won't
3145 : fire. Example:
3146 :
3147 : short int _1;
3148 : _2 = (int) _1;
3149 : _3 = _2 * 10;
3150 : _4 = x + _3; ADD: x + (10 * (int)_1) : int
3151 : _5 = _2 * 15;
3152 : _6 = x + _5; ADD: x + (15 * (int)_1) : int
3153 :
3154 : Although the stride was a short int initially, the stride
3155 : used in the analysis has been widened to an int, and such
3156 : widening will be done in the initializer as well. */
3157 2548 : else if (!incr_vec[i].initializer
3158 2036 : && TREE_CODE (first_dep->stride) != INTEGER_CST
3159 4584 : && !legal_cast_p_1 (first_dep->stride_type,
3160 2036 : TREE_TYPE (gimple_assign_lhs
3161 : (first_dep->cand_stmt))))
3162 54 : incr_vec[i].cost = COST_INFINITE;
3163 :
3164 : /* If we need to add an initializer, make sure we don't introduce
3165 : a multiply by a pointer type, which can happen in certain cast
3166 : scenarios. */
3167 2494 : else if (!incr_vec[i].initializer
3168 1982 : && TREE_CODE (first_dep->stride) != INTEGER_CST
3169 1982 : && POINTER_TYPE_P (first_dep->stride_type))
3170 0 : incr_vec[i].cost = COST_INFINITE;
3171 :
3172 : /* For any other increment, if this is a multiply candidate, we
3173 : must introduce a temporary T and initialize it with
3174 : T_0 = stride * increment. When optimizing for speed, walk the
3175 : candidate tree to calculate the best cost reduction along any
3176 : path; if it offsets the fixed cost of inserting the initializer,
3177 : replacing the increment is profitable. When optimizing for
3178 : size, instead calculate the total cost reduction from replacing
3179 : all candidates with this increment. */
3180 2494 : else if (first_dep->kind == CAND_MULT)
3181 : {
3182 113 : int cost = mult_by_coeff_cost (incr, mode, speed);
3183 113 : int repl_savings;
3184 :
3185 113 : if (tree_fits_shwi_p (first_dep->stride))
3186 : {
3187 0 : HOST_WIDE_INT hwi_stride = tree_to_shwi (first_dep->stride);
3188 0 : repl_savings = mult_by_coeff_cost (hwi_stride, mode, speed);
3189 : }
3190 : else
3191 113 : repl_savings = mul_cost (speed, mode);
3192 113 : repl_savings -= add_cost (speed, mode);
3193 :
3194 113 : if (speed)
3195 107 : cost = lowest_cost_path (cost, repl_savings, first_dep,
3196 107 : incr_vec[i].incr, COUNT_PHIS);
3197 : else
3198 6 : cost -= total_savings (repl_savings, first_dep, incr_vec[i].incr,
3199 : COUNT_PHIS);
3200 :
3201 113 : incr_vec[i].cost = cost;
3202 : }
3203 :
3204 : /* If this is an add candidate, the initializer may already
3205 : exist, so only calculate the cost of the initializer if it
3206 : doesn't. We are replacing one add with another here, so the
3207 : known replacement savings is zero. We will account for removal
3208 : of dead instructions in lowest_cost_path or total_savings. */
3209 : else
3210 : {
3211 2381 : int cost = 0;
3212 2381 : if (!incr_vec[i].initializer)
3213 1869 : cost = mult_by_coeff_cost (incr, mode, speed);
3214 :
3215 2381 : if (speed)
3216 2308 : cost = lowest_cost_path (cost, 0, first_dep, incr_vec[i].incr,
3217 : DONT_COUNT_PHIS);
3218 : else
3219 73 : cost -= total_savings (0, first_dep, incr_vec[i].incr,
3220 : DONT_COUNT_PHIS);
3221 :
3222 2381 : incr_vec[i].cost = cost;
3223 : }
3224 : }
3225 36348 : }
3226 :
3227 : /* Return the nearest common dominator of BB1 and BB2. If the blocks
3228 : are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
3229 : if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
3230 : return C2 in *WHERE; and if the NCD matches neither, return NULL in
3231 : *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
3232 :
3233 : static basic_block
3234 540 : ncd_for_two_cands (basic_block bb1, basic_block bb2,
3235 : slsr_cand_t c1, slsr_cand_t c2, slsr_cand_t *where)
3236 : {
3237 540 : basic_block ncd;
3238 :
3239 540 : if (!bb1)
3240 : {
3241 298 : *where = c2;
3242 298 : return bb2;
3243 : }
3244 :
3245 242 : if (!bb2)
3246 : {
3247 0 : *where = c1;
3248 0 : return bb1;
3249 : }
3250 :
3251 242 : ncd = nearest_common_dominator (CDI_DOMINATORS, bb1, bb2);
3252 :
3253 : /* If both candidates are in the same block, the earlier
3254 : candidate wins. */
3255 242 : if (bb1 == ncd && bb2 == ncd)
3256 : {
3257 213 : if (!c1 || (c2 && c2->cand_num < c1->cand_num))
3258 213 : *where = c2;
3259 : else
3260 0 : *where = c1;
3261 : }
3262 :
3263 : /* Otherwise, if one of them produced a candidate in the
3264 : dominator, that one wins. */
3265 29 : else if (bb1 == ncd)
3266 6 : *where = c1;
3267 :
3268 23 : else if (bb2 == ncd)
3269 12 : *where = c2;
3270 :
3271 : /* If neither matches the dominator, neither wins. */
3272 : else
3273 11 : *where = NULL;
3274 :
3275 : return ncd;
3276 : }
3277 :
3278 : /* Consider all candidates that feed PHI. Find the nearest common
3279 : dominator of those candidates requiring the given increment INCR.
3280 : Further find and return the nearest common dominator of this result
3281 : with block NCD. If the returned block contains one or more of the
3282 : candidates, return the earliest candidate in the block in *WHERE. */
3283 :
3284 : static basic_block
3285 8 : ncd_with_phi (slsr_cand_t c, const offset_int &incr, gphi *phi,
3286 : basic_block ncd, slsr_cand_t *where)
3287 : {
3288 8 : unsigned i;
3289 8 : slsr_cand_t basis = lookup_cand (c->basis);
3290 8 : slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
3291 :
3292 24 : for (i = 0; i < gimple_phi_num_args (phi); i++)
3293 : {
3294 16 : tree arg = gimple_phi_arg_def (phi, i);
3295 16 : gimple *arg_def = SSA_NAME_DEF_STMT (arg);
3296 :
3297 16 : if (gimple_code (arg_def) == GIMPLE_PHI)
3298 0 : ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, where);
3299 : else
3300 : {
3301 16 : offset_int diff;
3302 :
3303 16 : if (operand_equal_p (arg, phi_cand->base_expr, 0))
3304 6 : diff = -basis->index;
3305 : else
3306 : {
3307 10 : slsr_cand_t arg_cand = base_cand_from_table (arg);
3308 10 : diff = arg_cand->index - basis->index;
3309 : }
3310 :
3311 16 : basic_block pred = gimple_phi_arg_edge (phi, i)->src;
3312 :
3313 25 : if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
3314 8 : ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
3315 : }
3316 : }
3317 :
3318 8 : return ncd;
3319 : }
3320 :
3321 : /* Consider the candidate C together with any candidates that feed
3322 : C's phi dependence (if any). Find and return the nearest common
3323 : dominator of those candidates requiring the given increment INCR.
3324 : If the returned block contains one or more of the candidates,
3325 : return the earliest candidate in the block in *WHERE. */
3326 :
3327 : static basic_block
3328 1332 : ncd_of_cand_and_phis (slsr_cand_t c, const offset_int &incr, slsr_cand_t *where)
3329 : {
3330 1332 : basic_block ncd = NULL;
3331 :
3332 1332 : if (cand_abs_increment (c) == incr)
3333 : {
3334 527 : ncd = gimple_bb (c->cand_stmt);
3335 527 : *where = c;
3336 : }
3337 :
3338 1332 : if (phi_dependent_cand_p (c))
3339 8 : ncd = ncd_with_phi (c, incr,
3340 8 : as_a <gphi *> (lookup_cand (c->def_phi)->cand_stmt),
3341 : ncd, where);
3342 :
3343 1332 : return ncd;
3344 : }
3345 :
3346 : /* Consider all candidates in the tree rooted at C for which INCR
3347 : represents the required increment of C relative to its basis.
3348 : Find and return the basic block that most nearly dominates all
3349 : such candidates. If the returned block contains one or more of
3350 : the candidates, return the earliest candidate in the block in
3351 : *WHERE. */
3352 :
3353 : static basic_block
3354 1332 : nearest_common_dominator_for_cands (slsr_cand_t c, const offset_int &incr,
3355 : slsr_cand_t *where)
3356 : {
3357 1332 : basic_block sib_ncd = NULL, dep_ncd = NULL, this_ncd = NULL, ncd;
3358 1332 : slsr_cand_t sib_where = NULL, dep_where = NULL, this_where = NULL, new_where;
3359 :
3360 : /* First find the NCD of all siblings and dependents. */
3361 1332 : if (c->sibling)
3362 49 : sib_ncd = nearest_common_dominator_for_cands (lookup_cand (c->sibling),
3363 : incr, &sib_where);
3364 1332 : if (c->dependent)
3365 990 : dep_ncd = nearest_common_dominator_for_cands (lookup_cand (c->dependent),
3366 : incr, &dep_where);
3367 1332 : if (!sib_ncd && !dep_ncd)
3368 : {
3369 541 : new_where = NULL;
3370 541 : ncd = NULL;
3371 : }
3372 791 : else if (sib_ncd && !dep_ncd)
3373 : {
3374 45 : new_where = sib_where;
3375 45 : ncd = sib_ncd;
3376 : }
3377 746 : else if (dep_ncd && !sib_ncd)
3378 : {
3379 746 : new_where = dep_where;
3380 746 : ncd = dep_ncd;
3381 : }
3382 : else
3383 0 : ncd = ncd_for_two_cands (sib_ncd, dep_ncd, sib_where,
3384 : dep_where, &new_where);
3385 :
3386 : /* If the candidate's increment doesn't match the one we're interested
3387 : in (and nor do any increments for feeding defs of a phi-dependence),
3388 : then the result depends only on siblings and dependents. */
3389 1332 : this_ncd = ncd_of_cand_and_phis (c, incr, &this_where);
3390 :
3391 1332 : if (!this_ncd || cand_already_replaced (c))
3392 : {
3393 800 : *where = new_where;
3394 800 : return ncd;
3395 : }
3396 :
3397 : /* Otherwise, compare this candidate with the result from all siblings
3398 : and dependents. */
3399 532 : ncd = ncd_for_two_cands (ncd, this_ncd, new_where, this_where, where);
3400 :
3401 532 : return ncd;
3402 : }
3403 :
3404 : /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
3405 :
3406 : static inline bool
3407 135961 : profitable_increment_p (unsigned index)
3408 : {
3409 135961 : return (incr_vec[index].cost <= COST_NEUTRAL);
3410 : }
3411 :
3412 : /* For each profitable increment in the increment vector not equal to
3413 : 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
3414 : dominator of all statements in the candidate chain rooted at C
3415 : that require that increment, and insert an initializer
3416 : T_0 = stride * increment at that location. Record T_0 with the
3417 : increment record. */
3418 :
3419 : static void
3420 36348 : insert_initializers (slsr_cand_t c)
3421 : {
3422 36348 : unsigned i;
3423 :
3424 102242 : for (i = 0; i < incr_vec_len; i++)
3425 : {
3426 65894 : basic_block bb;
3427 65894 : slsr_cand_t where = NULL;
3428 65894 : gassign *init_stmt;
3429 65894 : gassign *cast_stmt = NULL;
3430 65894 : tree new_name, incr_tree, init_stride;
3431 65894 : offset_int incr = incr_vec[i].incr;
3432 :
3433 130983 : if (!profitable_increment_p (i)
3434 35130 : || incr == 1
3435 31622 : || (incr == -1
3436 2 : && (!POINTER_TYPE_P (lookup_cand (c->basis)->cand_type)))
3437 97516 : || incr == 0)
3438 65601 : continue;
3439 :
3440 : /* We may have already identified an existing initializer that
3441 : will suffice. */
3442 805 : if (incr_vec[i].initializer)
3443 : {
3444 512 : if (dump_file && (dump_flags & TDF_DETAILS))
3445 : {
3446 0 : fputs ("Using existing initializer: ", dump_file);
3447 0 : print_gimple_stmt (dump_file,
3448 0 : SSA_NAME_DEF_STMT (incr_vec[i].initializer),
3449 : 0, TDF_NONE);
3450 : }
3451 512 : continue;
3452 : }
3453 :
3454 : /* Find the block that most closely dominates all candidates
3455 : with this increment. If there is at least one candidate in
3456 : that block, the earliest one will be returned in WHERE. */
3457 293 : bb = nearest_common_dominator_for_cands (c, incr, &where);
3458 :
3459 : /* If the NCD is not dominated by the block containing the
3460 : definition of the stride, we can't legally insert a
3461 : single initializer. Mark the increment as unprofitable
3462 : so we don't make any replacements. FIXME: Multiple
3463 : initializers could be placed with more analysis. */
3464 293 : gimple *stride_def = SSA_NAME_DEF_STMT (c->stride);
3465 293 : basic_block stride_bb = gimple_bb (stride_def);
3466 :
3467 293 : if (stride_bb && !dominated_by_p (CDI_DOMINATORS, bb, stride_bb))
3468 : {
3469 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3470 0 : fprintf (dump_file,
3471 : "Initializer #%d cannot be legally placed\n", i);
3472 0 : incr_vec[i].cost = COST_INFINITE;
3473 0 : continue;
3474 : }
3475 :
3476 : /* If the nominal stride has a different type than the recorded
3477 : stride type, build a cast from the nominal stride to that type. */
3478 293 : if (!types_compatible_p (TREE_TYPE (c->stride), c->stride_type))
3479 : {
3480 152 : init_stride = make_temp_ssa_name (c->stride_type, NULL, "slsr");
3481 152 : cast_stmt = gimple_build_assign (init_stride, NOP_EXPR, c->stride);
3482 : }
3483 : else
3484 141 : init_stride = c->stride;
3485 :
3486 : /* Create a new SSA name to hold the initializer's value. */
3487 293 : new_name = make_temp_ssa_name (c->stride_type, NULL, "slsr");
3488 293 : incr_vec[i].initializer = new_name;
3489 :
3490 : /* Create the initializer and insert it in the latest possible
3491 : dominating position. */
3492 293 : incr_tree = wide_int_to_tree (c->stride_type, incr);
3493 293 : init_stmt = gimple_build_assign (new_name, MULT_EXPR,
3494 : init_stride, incr_tree);
3495 293 : if (where)
3496 : {
3497 279 : gimple_stmt_iterator gsi = gsi_for_stmt (where->cand_stmt);
3498 279 : location_t loc = gimple_location (where->cand_stmt);
3499 :
3500 279 : if (cast_stmt)
3501 : {
3502 152 : gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT);
3503 152 : gimple_set_location (cast_stmt, loc);
3504 : }
3505 :
3506 279 : gimple_set_location (init_stmt, loc);
3507 279 : if (gimple_needing_rewrite_undefined (init_stmt))
3508 : {
3509 119 : gimple_seq seq;
3510 119 : seq = rewrite_to_defined_unconditional (init_stmt);
3511 119 : gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
3512 : }
3513 : else
3514 160 : gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT);
3515 : }
3516 : else
3517 : {
3518 14 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
3519 14 : gimple *basis_stmt = lookup_cand (c->basis)->cand_stmt;
3520 14 : location_t loc = gimple_location (basis_stmt);
3521 :
3522 14 : gimple_set_location (init_stmt, gimple_location (basis_stmt));
3523 14 : if (!gsi_end_p (gsi) && stmt_ends_bb_p (gsi_stmt (gsi)))
3524 : {
3525 14 : if (cast_stmt)
3526 : {
3527 0 : gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT);
3528 0 : gimple_set_location (cast_stmt, loc);
3529 : }
3530 14 : if (gimple_needing_rewrite_undefined (init_stmt))
3531 : {
3532 9 : gimple_seq seq;
3533 9 : seq = rewrite_to_defined_unconditional (init_stmt);
3534 9 : gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
3535 : }
3536 : else
3537 5 : gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT);
3538 : }
3539 : else
3540 : {
3541 0 : if (cast_stmt)
3542 : {
3543 0 : gsi_insert_after (&gsi, cast_stmt, GSI_NEW_STMT);
3544 0 : gimple_set_location (cast_stmt, loc);
3545 : }
3546 0 : if (gimple_needing_rewrite_undefined (init_stmt))
3547 : {
3548 0 : gimple_seq seq;
3549 0 : seq = rewrite_to_defined_unconditional (init_stmt);
3550 0 : gsi_insert_seq_after (&gsi, seq, GSI_SAME_STMT);
3551 : }
3552 : else
3553 0 : gsi_insert_after (&gsi, init_stmt, GSI_SAME_STMT);
3554 : }
3555 : }
3556 :
3557 293 : if (dump_file && (dump_flags & TDF_DETAILS))
3558 : {
3559 0 : if (cast_stmt)
3560 : {
3561 0 : fputs ("Inserting stride cast: ", dump_file);
3562 0 : print_gimple_stmt (dump_file, cast_stmt, 0);
3563 : }
3564 0 : fputs ("Inserting initializer: ", dump_file);
3565 0 : print_gimple_stmt (dump_file, init_stmt, 0);
3566 : }
3567 : }
3568 36348 : }
3569 :
3570 : /* Recursive helper function for all_phi_incrs_profitable. */
3571 :
3572 : static bool
3573 12 : all_phi_incrs_profitable_1 (slsr_cand_t c, gphi *phi, int *spread)
3574 : {
3575 12 : unsigned i;
3576 12 : slsr_cand_t basis = lookup_cand (c->basis);
3577 12 : slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
3578 :
3579 12 : if (phi_cand->visited)
3580 : return true;
3581 :
3582 12 : phi_cand->visited = 1;
3583 12 : (*spread)++;
3584 :
3585 : /* If the basis doesn't dominate the PHI (including when the PHI is
3586 : in the same block as the basis), we won't be able to create a PHI
3587 : using the basis here. */
3588 12 : basic_block basis_bb = gimple_bb (basis->cand_stmt);
3589 12 : basic_block phi_bb = gimple_bb (phi);
3590 :
3591 12 : if (phi_bb == basis_bb
3592 12 : || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
3593 0 : return false;
3594 :
3595 29 : for (i = 0; i < gimple_phi_num_args (phi); i++)
3596 : {
3597 : /* If the PHI arg resides in a block not dominated by the basis,
3598 : we won't be able to create a PHI using the basis here. */
3599 21 : basic_block pred_bb = gimple_phi_arg_edge (phi, i)->src;
3600 :
3601 21 : if (!dominated_by_p (CDI_DOMINATORS, pred_bb, basis_bb))
3602 : return false;
3603 :
3604 21 : tree arg = gimple_phi_arg_def (phi, i);
3605 21 : gimple *arg_def = SSA_NAME_DEF_STMT (arg);
3606 :
3607 21 : if (gimple_code (arg_def) == GIMPLE_PHI)
3608 : {
3609 0 : if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), spread)
3610 0 : || *spread > MAX_SPREAD)
3611 : return false;
3612 : }
3613 : else
3614 : {
3615 21 : int j;
3616 21 : offset_int increment;
3617 :
3618 21 : if (operand_equal_p (arg, phi_cand->base_expr, 0))
3619 7 : increment = -basis->index;
3620 : else
3621 : {
3622 14 : slsr_cand_t arg_cand = base_cand_from_table (arg);
3623 14 : increment = arg_cand->index - basis->index;
3624 : }
3625 :
3626 21 : if (!address_arithmetic_p && wi::neg_p (increment))
3627 1 : increment = -increment;
3628 :
3629 21 : j = incr_vec_index (increment);
3630 :
3631 21 : if (dump_file && (dump_flags & TDF_DETAILS))
3632 : {
3633 0 : fprintf (dump_file, " Conditional candidate %d, phi: ",
3634 : c->cand_num);
3635 0 : print_gimple_stmt (dump_file, phi, 0);
3636 0 : fputs (" increment: ", dump_file);
3637 0 : print_decs (increment, dump_file);
3638 0 : if (j < 0)
3639 0 : fprintf (dump_file,
3640 : "\n Not replaced; incr_vec overflow.\n");
3641 : else {
3642 0 : fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost);
3643 0 : if (profitable_increment_p (j))
3644 0 : fputs (" Replacing...\n", dump_file);
3645 : else
3646 0 : fputs (" Not replaced.\n", dump_file);
3647 : }
3648 : }
3649 :
3650 21 : if (j < 0 || !profitable_increment_p (j))
3651 4 : return false;
3652 : }
3653 : }
3654 :
3655 : return true;
3656 : }
3657 :
3658 : /* Return TRUE iff all required increments for candidates feeding PHI
3659 : are profitable (and legal!) to replace on behalf of candidate C. */
3660 :
3661 : static bool
3662 12 : all_phi_incrs_profitable (slsr_cand_t c, gphi *phi)
3663 : {
3664 12 : int spread = 0;
3665 12 : bool retval = all_phi_incrs_profitable_1 (c, phi, &spread);
3666 12 : clear_visited (phi);
3667 12 : return retval;
3668 : }
3669 :
3670 : /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3671 : type TO_TYPE, and insert it in front of the statement represented
3672 : by candidate C. Use *NEW_VAR to create the new SSA name. Return
3673 : the new SSA name. */
3674 :
3675 : static tree
3676 5845 : introduce_cast_before_cand (slsr_cand_t c, tree to_type, tree from_expr)
3677 : {
3678 5845 : tree cast_lhs;
3679 5845 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3680 :
3681 11690 : cast_lhs = gimple_convert (&gsi, true, GSI_SAME_STMT,
3682 5845 : gimple_location (c->cand_stmt),
3683 : to_type, from_expr);
3684 :
3685 5845 : if (dump_file && (dump_flags & TDF_DETAILS))
3686 : {
3687 0 : fputs (" Inserting(cast): ", dump_file);
3688 0 : print_generic_expr (dump_file, cast_lhs);
3689 0 : fprintf (dump_file, "\n");
3690 : }
3691 :
3692 5845 : return cast_lhs;
3693 : }
3694 :
3695 : /* Replace the RHS of the statement represented by candidate C with
3696 : NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3697 : leave C unchanged or just interchange its operands. The original
3698 : operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3699 : If the replacement was made and we are doing a details dump,
3700 : return the revised statement, else NULL. */
3701 :
3702 : static gimple *
3703 7858 : replace_rhs_if_not_dup (enum tree_code new_code, tree new_rhs1, tree new_rhs2,
3704 : enum tree_code old_code, tree old_rhs1, tree old_rhs2,
3705 : slsr_cand_t c)
3706 : {
3707 7858 : if (new_code != old_code
3708 7858 : || ((!operand_equal_p (new_rhs1, old_rhs1, 0)
3709 0 : || !operand_equal_p (new_rhs2, old_rhs2, 0))
3710 3542 : && (!operand_equal_p (new_rhs1, old_rhs2, 0)
3711 0 : || !operand_equal_p (new_rhs2, old_rhs1, 0))))
3712 : {
3713 7858 : tree lhs = gimple_assign_lhs (c->cand_stmt);
3714 7858 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3715 7858 : tree rhs2_type = TREE_TYPE (lhs);
3716 7858 : if (POINTER_TYPE_P (rhs2_type))
3717 1217 : rhs2_type = sizetype;
3718 7858 : new_rhs1 = gimple_convert (&gsi, true, GSI_SAME_STMT,
3719 : UNKNOWN_LOCATION,
3720 7858 : TREE_TYPE (lhs), new_rhs1);
3721 7858 : new_rhs2 = gimple_convert (&gsi, true, GSI_SAME_STMT,
3722 : UNKNOWN_LOCATION,
3723 : rhs2_type, new_rhs2);
3724 7858 : slsr_cand_t cc = lookup_cand (c->first_interp);
3725 7858 : gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2);
3726 7858 : update_stmt (gsi_stmt (gsi));
3727 30184 : while (cc)
3728 : {
3729 14468 : cc->cand_stmt = gsi_stmt (gsi);
3730 14468 : cc = lookup_cand (cc->next_interp);
3731 : }
3732 :
3733 7858 : if (gimple_needing_rewrite_undefined (gsi_stmt (gsi)))
3734 6736 : rewrite_to_defined_unconditional (&gsi);
3735 7858 : if (dump_file && (dump_flags & TDF_DETAILS))
3736 0 : return gsi_stmt (gsi);
3737 : }
3738 :
3739 0 : else if (dump_file && (dump_flags & TDF_DETAILS))
3740 0 : fputs (" (duplicate, not actually replacing)\n", dump_file);
3741 :
3742 : return NULL;
3743 : }
3744 :
3745 : /* Strength-reduce the statement represented by candidate C by replacing
3746 : it with an equivalent addition or subtraction. I is the index into
3747 : the increment vector identifying C's increment. NEW_VAR is used to
3748 : create a new SSA name if a cast needs to be introduced. BASIS_NAME
3749 : is the rhs1 to use in creating the add/subtract. */
3750 :
3751 : static void
3752 18878 : replace_one_candidate (slsr_cand_t c, unsigned i, tree basis_name,
3753 : auto_bitmap &sdce_worklist)
3754 : {
3755 18878 : gimple *stmt_to_print = NULL;
3756 18878 : tree orig_rhs1, orig_rhs2;
3757 18878 : tree rhs2;
3758 18878 : enum tree_code orig_code, repl_code;
3759 18878 : offset_int cand_incr;
3760 :
3761 18878 : orig_code = gimple_assign_rhs_code (c->cand_stmt);
3762 18878 : orig_rhs1 = gimple_assign_rhs1 (c->cand_stmt);
3763 18878 : orig_rhs2 = gimple_assign_rhs2 (c->cand_stmt);
3764 18878 : cand_incr = cand_increment (c);
3765 :
3766 : /* If orig_rhs2 is NULL, we have already replaced this in situ with
3767 : a copy statement under another interpretation. */
3768 18878 : if (!orig_rhs2)
3769 0 : return;
3770 :
3771 : /* Mark the 2 original rhs for maybe DCEing. */
3772 18878 : if (TREE_CODE (orig_rhs1) == SSA_NAME)
3773 18878 : bitmap_set_bit (sdce_worklist, SSA_NAME_VERSION (orig_rhs1));
3774 18878 : if (TREE_CODE (orig_rhs2) == SSA_NAME)
3775 18878 : bitmap_set_bit (sdce_worklist, SSA_NAME_VERSION (orig_rhs2));
3776 :
3777 18878 : if (dump_file && (dump_flags & TDF_DETAILS))
3778 : {
3779 0 : fputs ("Replacing: ", dump_file);
3780 0 : print_gimple_stmt (dump_file, c->cand_stmt, 0);
3781 0 : stmt_to_print = c->cand_stmt;
3782 : }
3783 :
3784 18878 : if (address_arithmetic_p)
3785 : repl_code = POINTER_PLUS_EXPR;
3786 : else
3787 16335 : repl_code = PLUS_EXPR;
3788 :
3789 : /* If the increment has an initializer T_0, replace the candidate
3790 : statement with an add of the basis name and the initializer. */
3791 18878 : if (incr_vec[i].initializer)
3792 : {
3793 1422 : tree init_type = TREE_TYPE (incr_vec[i].initializer);
3794 1422 : tree orig_type = TREE_TYPE (orig_rhs2);
3795 :
3796 1422 : if (types_compatible_p (orig_type, init_type))
3797 1422 : rhs2 = incr_vec[i].initializer;
3798 : else
3799 0 : rhs2 = introduce_cast_before_cand (c, orig_type,
3800 0 : incr_vec[i].initializer);
3801 :
3802 1422 : if (incr_vec[i].incr != cand_incr)
3803 : {
3804 180 : gcc_assert (repl_code == PLUS_EXPR);
3805 : repl_code = MINUS_EXPR;
3806 : }
3807 :
3808 1422 : stmt_to_print = replace_rhs_if_not_dup (repl_code, basis_name, rhs2,
3809 : orig_code, orig_rhs1, orig_rhs2,
3810 : c);
3811 : }
3812 :
3813 : /* Otherwise, the increment is one of -1, 0, and 1. Replace
3814 : with a subtract of the stride from the basis name, a copy
3815 : from the basis name, or an add of the stride to the basis
3816 : name, respectively. It may be necessary to introduce a
3817 : cast (or reuse an existing cast). */
3818 17456 : else if (cand_incr == 1)
3819 : {
3820 6436 : tree stride_type = TREE_TYPE (c->stride);
3821 6436 : tree orig_type = TREE_TYPE (orig_rhs2);
3822 :
3823 6436 : if (types_compatible_p (orig_type, stride_type))
3824 5419 : rhs2 = c->stride;
3825 : else
3826 1017 : rhs2 = introduce_cast_before_cand (c, orig_type, c->stride);
3827 :
3828 6436 : stmt_to_print = replace_rhs_if_not_dup (repl_code, basis_name, rhs2,
3829 : orig_code, orig_rhs1, orig_rhs2,
3830 : c);
3831 : }
3832 :
3833 11020 : else if (cand_incr == -1)
3834 : {
3835 393 : tree stride_type = TREE_TYPE (c->stride);
3836 393 : tree orig_type = TREE_TYPE (orig_rhs2);
3837 393 : gcc_assert (repl_code != POINTER_PLUS_EXPR);
3838 :
3839 393 : if (types_compatible_p (orig_type, stride_type))
3840 316 : rhs2 = c->stride;
3841 : else
3842 77 : rhs2 = introduce_cast_before_cand (c, orig_type, c->stride);
3843 :
3844 393 : if (orig_code != MINUS_EXPR
3845 42 : || !operand_equal_p (basis_name, orig_rhs1, 0)
3846 393 : || !operand_equal_p (rhs2, orig_rhs2, 0))
3847 : {
3848 393 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3849 393 : tree lhs = gimple_assign_lhs (c->cand_stmt);
3850 393 : slsr_cand_t cc = lookup_cand (c->first_interp);
3851 393 : basis_name = gimple_convert (&gsi, true, GSI_SAME_STMT,
3852 : UNKNOWN_LOCATION,
3853 393 : TREE_TYPE (lhs), basis_name);
3854 393 : rhs2 = gimple_convert (&gsi, true, GSI_SAME_STMT,
3855 : UNKNOWN_LOCATION,
3856 393 : TREE_TYPE (lhs), rhs2);
3857 393 : gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2);
3858 393 : update_stmt (gsi_stmt (gsi));
3859 1530 : while (cc)
3860 : {
3861 744 : cc->cand_stmt = gsi_stmt (gsi);
3862 744 : cc = lookup_cand (cc->next_interp);
3863 : }
3864 :
3865 393 : if (dump_file && (dump_flags & TDF_DETAILS))
3866 0 : stmt_to_print = gsi_stmt (gsi);
3867 : }
3868 0 : else if (dump_file && (dump_flags & TDF_DETAILS))
3869 0 : fputs (" (duplicate, not actually replacing)\n", dump_file);
3870 : }
3871 :
3872 10627 : else if (cand_incr == 0)
3873 : {
3874 10627 : tree lhs = gimple_assign_lhs (c->cand_stmt);
3875 10627 : tree lhs_type = TREE_TYPE (lhs);
3876 10627 : tree basis_type = TREE_TYPE (basis_name);
3877 :
3878 10627 : if (types_compatible_p (lhs_type, basis_type))
3879 : {
3880 10567 : gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
3881 10567 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3882 10567 : slsr_cand_t cc = lookup_cand (c->first_interp);
3883 10567 : gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
3884 10567 : gsi_replace (&gsi, copy_stmt, false);
3885 39029 : while (cc)
3886 : {
3887 17895 : cc->cand_stmt = copy_stmt;
3888 17895 : cc = lookup_cand (cc->next_interp);
3889 : }
3890 :
3891 10567 : if (dump_file && (dump_flags & TDF_DETAILS))
3892 : stmt_to_print = copy_stmt;
3893 : }
3894 : else
3895 : {
3896 60 : gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3897 60 : gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name);
3898 60 : slsr_cand_t cc = lookup_cand (c->first_interp);
3899 60 : gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
3900 60 : gsi_replace (&gsi, cast_stmt, false);
3901 187 : while (cc)
3902 : {
3903 67 : cc->cand_stmt = cast_stmt;
3904 67 : cc = lookup_cand (cc->next_interp);
3905 : }
3906 :
3907 60 : if (dump_file && (dump_flags & TDF_DETAILS))
3908 : stmt_to_print = cast_stmt;
3909 : }
3910 : }
3911 : else
3912 0 : gcc_unreachable ();
3913 :
3914 18878 : if (dump_file && (dump_flags & TDF_DETAILS) && stmt_to_print)
3915 : {
3916 0 : fputs ("With: ", dump_file);
3917 0 : print_gimple_stmt (dump_file, stmt_to_print, 0);
3918 0 : fputs ("\n", dump_file);
3919 : }
3920 : }
3921 :
3922 : /* For each candidate in the tree rooted at C, replace it with
3923 : an increment if such has been shown to be profitable. */
3924 :
3925 : static void
3926 39581 : replace_profitable_candidates (slsr_cand_t c, auto_bitmap &sdce_worklist)
3927 : {
3928 70046 : if (!cand_already_replaced (c))
3929 : {
3930 70046 : offset_int increment = cand_abs_increment (c);
3931 70046 : enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt);
3932 70046 : int i;
3933 :
3934 70046 : i = incr_vec_index (increment);
3935 :
3936 : /* Only process profitable increments. Nothing useful can be done
3937 : to a cast or copy. */
3938 70046 : if (i >= 0
3939 70046 : && profitable_increment_p (i)
3940 68257 : && orig_code != SSA_NAME
3941 122505 : && !CONVERT_EXPR_CODE_P (orig_code))
3942 : {
3943 18882 : if (phi_dependent_cand_p (c))
3944 : {
3945 12 : gphi *phi = as_a <gphi *> (lookup_cand (c->def_phi)->cand_stmt);
3946 :
3947 12 : if (all_phi_incrs_profitable (c, phi))
3948 : {
3949 : /* Look up the LHS SSA name from C's basis. This will be
3950 : the RHS1 of the adds we will introduce to create new
3951 : phi arguments. */
3952 8 : slsr_cand_t basis = lookup_cand (c->basis);
3953 8 : tree basis_name = gimple_assign_lhs (basis->cand_stmt);
3954 :
3955 : /* Create a new phi statement that will represent C's true
3956 : basis after the transformation is complete. */
3957 8 : location_t loc = gimple_location (c->cand_stmt);
3958 8 : tree name = create_phi_basis (c, phi, basis_name,
3959 : loc, UNKNOWN_STRIDE);
3960 :
3961 : /* Replace C with an add of the new basis phi and the
3962 : increment. */
3963 8 : replace_one_candidate (c, i, name, sdce_worklist);
3964 : }
3965 : }
3966 : else
3967 : {
3968 18870 : slsr_cand_t basis = lookup_cand (c->basis);
3969 18870 : tree basis_name = gimple_assign_lhs (basis->cand_stmt);
3970 18870 : replace_one_candidate (c, i, basis_name, sdce_worklist);
3971 : }
3972 : }
3973 : }
3974 :
3975 70046 : if (c->sibling)
3976 3233 : replace_profitable_candidates (lookup_cand (c->sibling), sdce_worklist);
3977 :
3978 70046 : if (c->dependent)
3979 30465 : replace_profitable_candidates (lookup_cand (c->dependent), sdce_worklist);
3980 39581 : }
3981 :
3982 : /* Analyze costs of related candidates in the candidate vector,
3983 : and make beneficial replacements. */
3984 :
3985 : static void
3986 1041466 : analyze_candidates_and_replace (void)
3987 : {
3988 1041466 : unsigned i;
3989 1041466 : slsr_cand_t c;
3990 1041466 : auto_bitmap simple_dce_worklist;
3991 :
3992 : /* Each candidate that has a null basis and a non-null
3993 : dependent is the root of a tree of related statements.
3994 : Analyze each tree to determine a subset of those
3995 : statements that can be replaced with maximum benefit.
3996 :
3997 : Note the first NULL element is skipped. */
3998 9003287 : FOR_EACH_VEC_ELT_FROM (cand_vec, i, c, 1)
3999 : {
4000 7961821 : slsr_cand_t first_dep;
4001 :
4002 7961821 : if (c->basis != 0 || c->dependent == 0)
4003 7340356 : continue;
4004 :
4005 621465 : if (dump_file && (dump_flags & TDF_DETAILS))
4006 7 : fprintf (dump_file, "\nProcessing dependency tree rooted at %d.\n",
4007 : c->cand_num);
4008 :
4009 621465 : first_dep = lookup_cand (c->dependent);
4010 :
4011 : /* If this is a chain of CAND_REFs, unconditionally replace
4012 : each of them with a strength-reduced data reference. */
4013 621465 : if (c->kind == CAND_REF)
4014 7906 : replace_refs (c);
4015 :
4016 : /* If the common stride of all related candidates is a known
4017 : constant, each candidate without a phi-dependence can be
4018 : profitably replaced. Each replaces a multiply by a single
4019 : add, with the possibility that a feeding add also goes dead.
4020 : A candidate with a phi-dependence is replaced only if the
4021 : compensation code it requires is offset by the strength
4022 : reduction savings. */
4023 613559 : else if (TREE_CODE (c->stride) == INTEGER_CST)
4024 577211 : replace_uncond_cands_and_profitable_phis (first_dep,
4025 : simple_dce_worklist);
4026 :
4027 : /* When the stride is an SSA name, it may still be profitable
4028 : to replace some or all of the dependent candidates, depending
4029 : on whether the introduced increments can be reused, or are
4030 : less expensive to calculate than the replaced statements. */
4031 : else
4032 : {
4033 36348 : machine_mode mode;
4034 36348 : bool speed;
4035 :
4036 : /* Determine whether we'll be generating pointer arithmetic
4037 : when replacing candidates. */
4038 72696 : address_arithmetic_p = (c->kind == CAND_ADD
4039 36348 : && POINTER_TYPE_P (c->cand_type));
4040 :
4041 : /* If all candidates have already been replaced under other
4042 : interpretations, nothing remains to be done. */
4043 36348 : if (!count_candidates (c))
4044 0 : continue;
4045 :
4046 : /* Construct an array of increments for this candidate chain. */
4047 36348 : incr_vec = XNEWVEC (incr_info, MAX_INCR_VEC_LEN);
4048 36348 : incr_vec_len = 0;
4049 36348 : record_increments (c);
4050 :
4051 : /* Determine which increments are profitable to replace. */
4052 36348 : mode = TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c->cand_stmt)));
4053 36348 : speed = optimize_cands_for_speed_p (c);
4054 36348 : analyze_increments (first_dep, mode, speed);
4055 :
4056 : /* Insert initializers of the form T_0 = stride * increment
4057 : for use in profitable replacements. */
4058 36348 : insert_initializers (first_dep);
4059 36348 : dump_incr_vec ();
4060 :
4061 : /* Perform the replacements. */
4062 36348 : replace_profitable_candidates (first_dep, simple_dce_worklist);
4063 36348 : free (incr_vec);
4064 : }
4065 : }
4066 :
4067 : /* For conditional candidates, we may have uncommitted insertions
4068 : on edges to clean up. */
4069 1041466 : gsi_commit_edge_inserts ();
4070 :
4071 1041466 : simple_dce_from_worklist (simple_dce_worklist);
4072 1041466 : }
4073 :
4074 : namespace {
4075 :
4076 : const pass_data pass_data_strength_reduction =
4077 : {
4078 : GIMPLE_PASS, /* type */
4079 : "slsr", /* name */
4080 : OPTGROUP_NONE, /* optinfo_flags */
4081 : TV_GIMPLE_SLSR, /* tv_id */
4082 : ( PROP_cfg | PROP_ssa ), /* properties_required */
4083 : 0, /* properties_provided */
4084 : 0, /* properties_destroyed */
4085 : 0, /* todo_flags_start */
4086 : 0, /* todo_flags_finish */
4087 : };
4088 :
4089 : class pass_strength_reduction : public gimple_opt_pass
4090 : {
4091 : public:
4092 285722 : pass_strength_reduction (gcc::context *ctxt)
4093 571444 : : gimple_opt_pass (pass_data_strength_reduction, ctxt)
4094 : {}
4095 :
4096 : /* opt_pass methods: */
4097 1041484 : bool gate (function *) final override { return flag_tree_slsr; }
4098 : unsigned int execute (function *) final override;
4099 :
4100 : }; // class pass_strength_reduction
4101 :
4102 : unsigned
4103 1041466 : pass_strength_reduction::execute (function *fun)
4104 : {
4105 : /* Create the obstack where candidates will reside. */
4106 1041466 : gcc_obstack_init (&cand_obstack);
4107 :
4108 : /* Allocate the candidate vector and initialize the first NULL element. */
4109 1041466 : cand_vec.create (128);
4110 1041466 : cand_vec.safe_push (NULL);
4111 :
4112 : /* Allocate the mapping from statements to candidate indices. */
4113 1041466 : stmt_cand_map = new hash_map<gimple *, slsr_cand_t>;
4114 :
4115 : /* Create the obstack where candidate chains will reside. */
4116 1041466 : gcc_obstack_init (&chain_obstack);
4117 :
4118 : /* Allocate the mapping from base expressions to candidate chains. */
4119 1041466 : base_cand_map = new hash_table<cand_chain_hasher> (500);
4120 :
4121 : /* Allocate the mapping from bases to alternative bases. */
4122 1041466 : alt_base_map = new hash_map<tree, tree>;
4123 :
4124 : /* Initialize the loop optimizer. We need to detect flow across
4125 : back edges, and this gives us dominator information as well. */
4126 1041466 : loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4127 :
4128 : /* Walk the CFG in predominator order looking for strength reduction
4129 : candidates. */
4130 1041466 : find_candidates_dom_walker (CDI_DOMINATORS)
4131 1041466 : .walk (fun->cfg->x_entry_block_ptr);
4132 :
4133 1041466 : if (dump_file && (dump_flags & TDF_DETAILS))
4134 : {
4135 3 : dump_cand_vec ();
4136 3 : dump_cand_chains ();
4137 : }
4138 :
4139 2082932 : delete alt_base_map;
4140 1041466 : free_affine_expand_cache (&name_expansions);
4141 :
4142 : /* Analyze costs and make appropriate replacements. */
4143 1041466 : analyze_candidates_and_replace ();
4144 :
4145 1041466 : loop_optimizer_finalize ();
4146 1041466 : delete base_cand_map;
4147 1041466 : base_cand_map = NULL;
4148 1041466 : obstack_free (&chain_obstack, NULL);
4149 2082932 : delete stmt_cand_map;
4150 1041466 : cand_vec.release ();
4151 1041466 : obstack_free (&cand_obstack, NULL);
4152 :
4153 1041466 : return 0;
4154 : }
4155 :
4156 : } // anon namespace
4157 :
4158 : gimple_opt_pass *
4159 285722 : make_pass_strength_reduction (gcc::context *ctxt)
4160 : {
4161 285722 : return new pass_strength_reduction (ctxt);
4162 : }
|
