Branch data Line data Source code
1 : : /* Predictive commoning.
2 : : Copyright (C) 2005-2025 Free Software Foundation, Inc.
3 : :
4 : : This file is part of GCC.
5 : :
6 : : GCC is free software; you can redistribute it and/or modify it
7 : : under the terms of the GNU General Public License as published by the
8 : : Free Software Foundation; either version 3, or (at your option) any
9 : : later version.
10 : :
11 : : GCC is distributed in the hope that it will be useful, but WITHOUT
12 : : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : : for more details.
15 : :
16 : : You should have received a copy of the GNU General Public License
17 : : along with GCC; see the file COPYING3. If not see
18 : : <http://www.gnu.org/licenses/>. */
19 : :
20 : : /* This file implements the predictive commoning optimization. Predictive
21 : : commoning can be viewed as CSE around a loop, and with some improvements,
22 : : as generalized strength reduction-- i.e., reusing values computed in
23 : : earlier iterations of a loop in the later ones. So far, the pass only
24 : : handles the most useful case, that is, reusing values of memory references.
25 : : If you think this is all just a special case of PRE, you are sort of right;
26 : : however, concentrating on loops is simpler, and makes it possible to
27 : : incorporate data dependence analysis to detect the opportunities, perform
28 : : loop unrolling to avoid copies together with renaming immediately,
29 : : and if needed, we could also take register pressure into account.
30 : :
31 : : Let us demonstrate what is done on an example:
32 : :
33 : : for (i = 0; i < 100; i++)
34 : : {
35 : : a[i+2] = a[i] + a[i+1];
36 : : b[10] = b[10] + i;
37 : : c[i] = c[99 - i];
38 : : d[i] = d[i + 1];
39 : : }
40 : :
41 : : 1) We find data references in the loop, and split them to mutually
42 : : independent groups (i.e., we find components of a data dependence
43 : : graph). We ignore read-read dependences whose distance is not constant.
44 : : (TODO -- we could also ignore antidependences). In this example, we
45 : : find the following groups:
46 : :
47 : : a[i]{read}, a[i+1]{read}, a[i+2]{write}
48 : : b[10]{read}, b[10]{write}
49 : : c[99 - i]{read}, c[i]{write}
50 : : d[i + 1]{read}, d[i]{write}
51 : :
52 : : 2) Inside each of the group, we verify several conditions:
53 : : a) all the references must differ in indices only, and the indices
54 : : must all have the same step
55 : : b) the references must dominate loop latch (and thus, they must be
56 : : ordered by dominance relation).
57 : : c) the distance of the indices must be a small multiple of the step
58 : : We are then able to compute the difference of the references (# of
59 : : iterations before they point to the same place as the first of them).
60 : : Also, in case there are writes in the loop, we split the groups into
61 : : chains whose head is the write whose values are used by the reads in
62 : : the same chain. The chains are then processed independently,
63 : : making the further transformations simpler. Also, the shorter chains
64 : : need the same number of registers, but may require lower unrolling
65 : : factor in order to get rid of the copies on the loop latch.
66 : :
67 : : In our example, we get the following chains (the chain for c is invalid).
68 : :
69 : : a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
70 : : b[10]{read,+0}, b[10]{write,+0}
71 : : d[i + 1]{read,+0}, d[i]{write,+1}
72 : :
73 : : 3) For each read, we determine the read or write whose value it reuses,
74 : : together with the distance of this reuse. I.e. we take the last
75 : : reference before it with distance 0, or the last of the references
76 : : with the smallest positive distance to the read. Then, we remove
77 : : the references that are not used in any of these chains, discard the
78 : : empty groups, and propagate all the links so that they point to the
79 : : single root reference of the chain (adjusting their distance
80 : : appropriately). Some extra care needs to be taken for references with
81 : : step 0. In our example (the numbers indicate the distance of the
82 : : reuse),
83 : :
84 : : a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
85 : : b[10] --> (*) 1, b[10] (*)
86 : :
87 : : 4) The chains are combined together if possible. If the corresponding
88 : : elements of two chains are always combined together with the same
89 : : operator, we remember just the result of this combination, instead
90 : : of remembering the values separately. We may need to perform
91 : : reassociation to enable combining, for example
92 : :
93 : : e[i] + f[i+1] + e[i+1] + f[i]
94 : :
95 : : can be reassociated as
96 : :
97 : : (e[i] + f[i]) + (e[i+1] + f[i+1])
98 : :
99 : : and we can combine the chains for e and f into one chain.
100 : :
101 : : 5) For each root reference (end of the chain) R, let N be maximum distance
102 : : of a reference reusing its value. Variables R0 up to RN are created,
103 : : together with phi nodes that transfer values from R1 .. RN to
104 : : R0 .. R(N-1).
105 : : Initial values are loaded to R0..R(N-1) (in case not all references
106 : : must necessarily be accessed and they may trap, we may fail here;
107 : : TODO sometimes, the loads could be guarded by a check for the number
108 : : of iterations). Values loaded/stored in roots are also copied to
109 : : RN. Other reads are replaced with the appropriate variable Ri.
110 : : Everything is put to SSA form.
111 : :
112 : : As a small improvement, if R0 is dead after the root (i.e., all uses of
113 : : the value with the maximum distance dominate the root), we can avoid
114 : : creating RN and use R0 instead of it.
115 : :
116 : : In our example, we get (only the parts concerning a and b are shown):
117 : : for (i = 0; i < 100; i++)
118 : : {
119 : : f = phi (a[0], s);
120 : : s = phi (a[1], f);
121 : : x = phi (b[10], x);
122 : :
123 : : f = f + s;
124 : : a[i+2] = f;
125 : : x = x + i;
126 : : b[10] = x;
127 : : }
128 : :
129 : : 6) Factor F for unrolling is determined as the smallest common multiple of
130 : : (N + 1) for each root reference (N for references for that we avoided
131 : : creating RN). If F and the loop is small enough, loop is unrolled F
132 : : times. The stores to RN (R0) in the copies of the loop body are
133 : : periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
134 : : be coalesced and the copies can be eliminated.
135 : :
136 : : TODO -- copy propagation and other optimizations may change the live
137 : : ranges of the temporary registers and prevent them from being coalesced;
138 : : this may increase the register pressure.
139 : :
140 : : In our case, F = 2 and the (main loop of the) result is
141 : :
142 : : for (i = 0; i < ...; i += 2)
143 : : {
144 : : f = phi (a[0], f);
145 : : s = phi (a[1], s);
146 : : x = phi (b[10], x);
147 : :
148 : : f = f + s;
149 : : a[i+2] = f;
150 : : x = x + i;
151 : : b[10] = x;
152 : :
153 : : s = s + f;
154 : : a[i+3] = s;
155 : : x = x + i;
156 : : b[10] = x;
157 : : }
158 : :
159 : : Apart from predictive commoning on Load-Load and Store-Load chains, we
160 : : also support Store-Store chains -- stores killed by other store can be
161 : : eliminated. Given below example:
162 : :
163 : : for (i = 0; i < n; i++)
164 : : {
165 : : a[i] = 1;
166 : : a[i+2] = 2;
167 : : }
168 : :
169 : : It can be replaced with:
170 : :
171 : : t0 = a[0];
172 : : t1 = a[1];
173 : : for (i = 0; i < n; i++)
174 : : {
175 : : a[i] = 1;
176 : : t2 = 2;
177 : : t0 = t1;
178 : : t1 = t2;
179 : : }
180 : : a[n] = t0;
181 : : a[n+1] = t1;
182 : :
183 : : If the loop runs more than 1 iterations, it can be further simplified into:
184 : :
185 : : for (i = 0; i < n; i++)
186 : : {
187 : : a[i] = 1;
188 : : }
189 : : a[n] = 2;
190 : : a[n+1] = 2;
191 : :
192 : : The interesting part is this can be viewed either as general store motion
193 : : or general dead store elimination in either intra/inter-iterations way.
194 : :
195 : : With trivial effort, we also support load inside Store-Store chains if the
196 : : load is dominated by a store statement in the same iteration of loop. You
197 : : can see this as a restricted Store-Mixed-Load-Store chain.
198 : :
199 : : TODO: For now, we don't support store-store chains in multi-exit loops. We
200 : : force to not unroll in case of store-store chain even if other chains might
201 : : ask for unroll.
202 : :
203 : : Predictive commoning can be generalized for arbitrary computations (not
204 : : just memory loads), and also nontrivial transfer functions (e.g., replacing
205 : : i * i with ii_last + 2 * i + 1), to generalize strength reduction. */
206 : :
207 : : #include "config.h"
208 : : #include "system.h"
209 : : #include "coretypes.h"
210 : : #include "backend.h"
211 : : #include "rtl.h"
212 : : #include "tree.h"
213 : : #include "gimple.h"
214 : : #include "predict.h"
215 : : #include "tree-pass.h"
216 : : #include "ssa.h"
217 : : #include "gimple-pretty-print.h"
218 : : #include "alias.h"
219 : : #include "fold-const.h"
220 : : #include "cfgloop.h"
221 : : #include "tree-eh.h"
222 : : #include "gimplify.h"
223 : : #include "gimple-iterator.h"
224 : : #include "gimplify-me.h"
225 : : #include "tree-ssa-loop-ivopts.h"
226 : : #include "tree-ssa-loop-manip.h"
227 : : #include "tree-ssa-loop-niter.h"
228 : : #include "tree-ssa-loop.h"
229 : : #include "tree-into-ssa.h"
230 : : #include "tree-dfa.h"
231 : : #include "tree-ssa.h"
232 : : #include "tree-data-ref.h"
233 : : #include "tree-scalar-evolution.h"
234 : : #include "tree-affine.h"
235 : : #include "builtins.h"
236 : : #include "opts.h"
237 : : #include "tree-ssa-address.h"
238 : :
239 : : /* The maximum number of iterations between the considered memory
240 : : references. */
241 : :
242 : : #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
243 : :
244 : : /* Data references (or phi nodes that carry data reference values across
245 : : loop iterations). */
246 : :
247 : : typedef class dref_d
248 : : {
249 : : public:
250 : : /* The reference itself. */
251 : : struct data_reference *ref;
252 : :
253 : : /* The statement in that the reference appears. */
254 : : gimple *stmt;
255 : :
256 : : /* In case that STMT is a phi node, this field is set to the SSA name
257 : : defined by it in replace_phis_by_defined_names (in order to avoid
258 : : pointing to phi node that got reallocated in the meantime). */
259 : : tree name_defined_by_phi;
260 : :
261 : : /* Distance of the reference from the root of the chain (in number of
262 : : iterations of the loop). */
263 : : unsigned distance;
264 : :
265 : : /* Number of iterations offset from the first reference in the component. */
266 : : widest_int offset;
267 : :
268 : : /* Number of the reference in a component, in dominance ordering. */
269 : : unsigned pos;
270 : :
271 : : /* True if the memory reference is always accessed when the loop is
272 : : entered. */
273 : : unsigned always_accessed : 1;
274 : : } *dref;
275 : :
276 : :
277 : : /* Type of the chain of the references. */
278 : :
279 : : enum chain_type
280 : : {
281 : : /* The addresses of the references in the chain are constant. */
282 : : CT_INVARIANT,
283 : :
284 : : /* There are only loads in the chain. */
285 : : CT_LOAD,
286 : :
287 : : /* Root of the chain is store, the rest are loads. */
288 : : CT_STORE_LOAD,
289 : :
290 : : /* There are only stores in the chain. */
291 : : CT_STORE_STORE,
292 : :
293 : : /* A combination of two chains. */
294 : : CT_COMBINATION
295 : : };
296 : :
297 : : /* Chains of data references. */
298 : :
299 : : typedef struct chain
300 : : {
301 : 67429 : chain (chain_type t) : type (t), op (ERROR_MARK), rslt_type (NULL_TREE),
302 : 67429 : ch1 (NULL), ch2 (NULL), length (0), init_seq (NULL), fini_seq (NULL),
303 : 67429 : has_max_use_after (false), all_always_accessed (false), combined (false),
304 : 67429 : inv_store_elimination (false) {}
305 : :
306 : : /* Type of the chain. */
307 : : enum chain_type type;
308 : :
309 : : /* For combination chains, the operator and the two chains that are
310 : : combined, and the type of the result. */
311 : : enum tree_code op;
312 : : tree rslt_type;
313 : : struct chain *ch1, *ch2;
314 : :
315 : : /* The references in the chain. */
316 : : auto_vec<dref> refs;
317 : :
318 : : /* The maximum distance of the reference in the chain from the root. */
319 : : unsigned length;
320 : :
321 : : /* The variables used to copy the value throughout iterations. */
322 : : auto_vec<tree> vars;
323 : :
324 : : /* Initializers for the variables. */
325 : : auto_vec<tree> inits;
326 : :
327 : : /* Finalizers for the eliminated stores. */
328 : : auto_vec<tree> finis;
329 : :
330 : : /* gimple stmts intializing the initial variables of the chain. */
331 : : gimple_seq init_seq;
332 : :
333 : : /* gimple stmts finalizing the eliminated stores of the chain. */
334 : : gimple_seq fini_seq;
335 : :
336 : : /* True if there is a use of a variable with the maximal distance
337 : : that comes after the root in the loop. */
338 : : unsigned has_max_use_after : 1;
339 : :
340 : : /* True if all the memory references in the chain are always accessed. */
341 : : unsigned all_always_accessed : 1;
342 : :
343 : : /* True if this chain was combined together with some other chain. */
344 : : unsigned combined : 1;
345 : :
346 : : /* True if this is store elimination chain and eliminated stores store
347 : : loop invariant value into memory. */
348 : : unsigned inv_store_elimination : 1;
349 : : } *chain_p;
350 : :
351 : :
352 : : /* Describes the knowledge about the step of the memory references in
353 : : the component. */
354 : :
355 : : enum ref_step_type
356 : : {
357 : : /* The step is zero. */
358 : : RS_INVARIANT,
359 : :
360 : : /* The step is nonzero. */
361 : : RS_NONZERO,
362 : :
363 : : /* The step may or may not be nonzero. */
364 : : RS_ANY
365 : : };
366 : :
367 : : /* Components of the data dependence graph. */
368 : :
369 : 756630 : struct component
370 : : {
371 : 378315 : component (bool es) : comp_step (RS_ANY), eliminate_store_p (es),
372 : 378315 : next (NULL) {}
373 : :
374 : : /* The references in the component. */
375 : : auto_vec<dref> refs;
376 : :
377 : : /* What we know about the step of the references in the component. */
378 : : enum ref_step_type comp_step;
379 : :
380 : : /* True if all references in component are stores and we try to do
381 : : intra/inter loop iteration dead store elimination. */
382 : : bool eliminate_store_p;
383 : :
384 : : /* Next component in the list. */
385 : : struct component *next;
386 : : };
387 : :
388 : : /* A class to encapsulate the global states used for predictive
389 : : commoning work on top of one given LOOP. */
390 : :
391 : : class pcom_worker
392 : : {
393 : : public:
394 : 418112 : pcom_worker (loop_p l) : m_loop (l), m_cache (NULL) {}
395 : :
396 : 418112 : ~pcom_worker ()
397 : : {
398 : 418112 : free_data_refs (m_datarefs);
399 : 418112 : free_dependence_relations (m_dependences);
400 : 418112 : free_affine_expand_cache (&m_cache);
401 : 418112 : release_chains ();
402 : 418112 : }
403 : :
404 : : pcom_worker (const pcom_worker &) = delete;
405 : : pcom_worker &operator= (const pcom_worker &) = delete;
406 : :
407 : : /* Performs predictive commoning. */
408 : : unsigned tree_predictive_commoning_loop (bool allow_unroll_p);
409 : :
410 : : /* Perform the predictive commoning optimization for chains, make this
411 : : public for being called in callback execute_pred_commoning_cbck. */
412 : : void execute_pred_commoning (bitmap tmp_vars);
413 : :
414 : : private:
415 : : /* The pointer to the given loop. */
416 : : loop_p m_loop;
417 : :
418 : : /* All data references. */
419 : : auto_vec<data_reference_p, 10> m_datarefs;
420 : :
421 : : /* All data dependences. */
422 : : auto_vec<ddr_p, 10> m_dependences;
423 : :
424 : : /* All chains. */
425 : : auto_vec<chain_p> m_chains;
426 : :
427 : : /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
428 : : auto_bitmap m_looparound_phis;
429 : :
430 : : typedef hash_map<tree, name_expansion *> tree_expand_map_t;
431 : : /* Cache used by tree_to_aff_combination_expand. */
432 : : tree_expand_map_t *m_cache;
433 : :
434 : : /* Splits dependence graph to components. */
435 : : struct component *split_data_refs_to_components ();
436 : :
437 : : /* Check the conditions on references inside each of components COMPS,
438 : : and remove the unsuitable components from the list. */
439 : : struct component *filter_suitable_components (struct component *comps);
440 : :
441 : : /* Find roots of the values and determine distances in components COMPS,
442 : : and separates the references to chains. */
443 : : void determine_roots (struct component *comps);
444 : :
445 : : /* Prepare initializers for chains, and free chains that cannot
446 : : be used because the initializers might trap. */
447 : : void prepare_initializers ();
448 : :
449 : : /* Generates finalizer memory reference for chains. Returns true if
450 : : finalizer code generation for chains breaks loop closed ssa form. */
451 : : bool prepare_finalizers ();
452 : :
453 : : /* Try to combine the chains. */
454 : : void try_combine_chains ();
455 : :
456 : : /* Frees CHAINS. */
457 : : void release_chains ();
458 : :
459 : : /* Frees a chain CHAIN. */
460 : : void release_chain (chain_p chain);
461 : :
462 : : /* Prepare initializers for CHAIN. Returns false if this is impossible
463 : : because one of these initializers may trap, true otherwise. */
464 : : bool prepare_initializers_chain (chain_p chain);
465 : :
466 : : /* Generates finalizer memory references for CHAIN. Returns true
467 : : if finalizer code for CHAIN can be generated, otherwise false. */
468 : : bool prepare_finalizers_chain (chain_p chain);
469 : :
470 : : /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
471 : : void aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset);
472 : :
473 : : /* Determines number of iterations of the innermost enclosing loop before
474 : : B refers to exactly the same location as A and stores it to OFF. */
475 : : bool determine_offset (struct data_reference *a, struct data_reference *b,
476 : : poly_widest_int *off);
477 : :
478 : : /* Returns true if the component COMP satisfies the conditions
479 : : described in 2) at the beginning of this file. */
480 : : bool suitable_component_p (struct component *comp);
481 : :
482 : : /* Returns true if REF is a valid initializer for ROOT with given
483 : : DISTANCE (in iterations of the innermost enclosing loop). */
484 : : bool valid_initializer_p (struct data_reference *ref, unsigned distance,
485 : : struct data_reference *root);
486 : :
487 : : /* Finds looparound phi node of loop that copies the value of REF. */
488 : : gphi *find_looparound_phi (dref ref, dref root);
489 : :
490 : : /* Find roots of the values and determine distances in the component
491 : : COMP. The references are redistributed into chains. */
492 : : void determine_roots_comp (struct component *comp);
493 : :
494 : : /* For references in CHAIN that are copied around the loop, add the
495 : : results of such copies to the chain. */
496 : : void add_looparound_copies (chain_p chain);
497 : :
498 : : /* Returns the single statement in that NAME is used, excepting
499 : : the looparound phi nodes contained in one of the chains. */
500 : : gimple *single_nonlooparound_use (tree name);
501 : :
502 : : /* Remove statement STMT, as well as the chain of assignments in that
503 : : it is used. */
504 : : void remove_stmt (gimple *stmt);
505 : :
506 : : /* Perform the predictive commoning optimization for a chain CHAIN. */
507 : : void execute_pred_commoning_chain (chain_p chain, bitmap tmp_vars);
508 : :
509 : : /* Returns the modify statement that uses NAME. */
510 : : gimple *find_use_stmt (tree *name);
511 : :
512 : : /* If the operation used in STMT is associative and commutative, go
513 : : through the tree of the same operations and returns its root. */
514 : : gimple *find_associative_operation_root (gimple *stmt, unsigned *distance);
515 : :
516 : : /* Returns the common statement in that NAME1 and NAME2 have a use. */
517 : : gimple *find_common_use_stmt (tree *name1, tree *name2);
518 : :
519 : : /* Checks whether R1 and R2 are combined together using CODE, with the
520 : : result in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order
521 : : R2 CODE R1 if it is true. */
522 : : bool combinable_refs_p (dref r1, dref r2, enum tree_code *code, bool *swap,
523 : : tree *rslt_type);
524 : :
525 : : /* Reassociates the expression in that NAME1 and NAME2 are used so that
526 : : they are combined in a single statement, and returns this statement. */
527 : : gimple *reassociate_to_the_same_stmt (tree name1, tree name2);
528 : :
529 : : /* Returns the statement that combines references R1 and R2. */
530 : : gimple *stmt_combining_refs (dref r1, dref r2);
531 : :
532 : : /* Tries to combine chains CH1 and CH2 together. */
533 : : chain_p combine_chains (chain_p ch1, chain_p ch2);
534 : : };
535 : :
536 : : /* Dumps data reference REF to FILE. */
537 : :
538 : : extern void dump_dref (FILE *, dref);
539 : : void
540 : 312 : dump_dref (FILE *file, dref ref)
541 : : {
542 : 312 : if (ref->ref)
543 : : {
544 : 293 : fprintf (file, " ");
545 : 293 : print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
546 : 293 : fprintf (file, " (id %u%s)\n", ref->pos,
547 : 293 : DR_IS_READ (ref->ref) ? "" : ", write");
548 : :
549 : 293 : fprintf (file, " offset ");
550 : 293 : print_decs (ref->offset, file);
551 : 293 : fprintf (file, "\n");
552 : :
553 : 293 : fprintf (file, " distance %u\n", ref->distance);
554 : : }
555 : : else
556 : : {
557 : 19 : if (gimple_code (ref->stmt) == GIMPLE_PHI)
558 : 1 : fprintf (file, " looparound ref\n");
559 : : else
560 : 18 : fprintf (file, " combination ref\n");
561 : 19 : fprintf (file, " in statement ");
562 : 19 : print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
563 : 19 : fprintf (file, "\n");
564 : 19 : fprintf (file, " distance %u\n", ref->distance);
565 : : }
566 : :
567 : 312 : }
568 : :
569 : : /* Dumps CHAIN to FILE. */
570 : :
571 : : extern void dump_chain (FILE *, chain_p);
572 : : void
573 : 59 : dump_chain (FILE *file, chain_p chain)
574 : : {
575 : 59 : dref a;
576 : 59 : const char *chain_type;
577 : 59 : unsigned i;
578 : 59 : tree var;
579 : :
580 : 59 : switch (chain->type)
581 : : {
582 : : case CT_INVARIANT:
583 : : chain_type = "Load motion";
584 : : break;
585 : :
586 : 24 : case CT_LOAD:
587 : 24 : chain_type = "Loads-only";
588 : 24 : break;
589 : :
590 : 5 : case CT_STORE_LOAD:
591 : 5 : chain_type = "Store-loads";
592 : 5 : break;
593 : :
594 : 20 : case CT_STORE_STORE:
595 : 20 : chain_type = "Store-stores";
596 : 20 : break;
597 : :
598 : 9 : case CT_COMBINATION:
599 : 9 : chain_type = "Combination";
600 : 9 : break;
601 : :
602 : 0 : default:
603 : 0 : gcc_unreachable ();
604 : : }
605 : :
606 : 59 : fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
607 : 59 : chain->combined ? " (combined)" : "");
608 : 59 : if (chain->type != CT_INVARIANT)
609 : 58 : fprintf (file, " max distance %u%s\n", chain->length,
610 : 58 : chain->has_max_use_after ? "" : ", may reuse first");
611 : :
612 : 59 : if (chain->type == CT_COMBINATION)
613 : : {
614 : 18 : fprintf (file, " equal to %p %s %p in type ",
615 : 9 : (void *) chain->ch1, op_symbol_code (chain->op),
616 : 9 : (void *) chain->ch2);
617 : 9 : print_generic_expr (file, chain->rslt_type, TDF_SLIM);
618 : 9 : fprintf (file, "\n");
619 : : }
620 : :
621 : 59 : if (chain->vars.exists ())
622 : : {
623 : 0 : fprintf (file, " vars");
624 : 0 : FOR_EACH_VEC_ELT (chain->vars, i, var)
625 : : {
626 : 0 : fprintf (file, " ");
627 : 0 : print_generic_expr (file, var, TDF_SLIM);
628 : : }
629 : 0 : fprintf (file, "\n");
630 : : }
631 : :
632 : 59 : if (chain->inits.exists ())
633 : : {
634 : 41 : fprintf (file, " inits");
635 : 149 : FOR_EACH_VEC_ELT (chain->inits, i, var)
636 : : {
637 : 67 : fprintf (file, " ");
638 : 67 : print_generic_expr (file, var, TDF_SLIM);
639 : : }
640 : 41 : fprintf (file, "\n");
641 : : }
642 : :
643 : 59 : fprintf (file, " references:\n");
644 : 255 : FOR_EACH_VEC_ELT (chain->refs, i, a)
645 : 137 : dump_dref (file, a);
646 : :
647 : 59 : fprintf (file, "\n");
648 : 59 : }
649 : :
650 : : /* Dumps CHAINS to FILE. */
651 : :
652 : : void
653 : 35 : dump_chains (FILE *file, const vec<chain_p> &chains)
654 : : {
655 : 35 : chain_p chain;
656 : 35 : unsigned i;
657 : :
658 : 94 : FOR_EACH_VEC_ELT (chains, i, chain)
659 : 59 : dump_chain (file, chain);
660 : 35 : }
661 : :
662 : : /* Dumps COMP to FILE. */
663 : :
664 : : extern void dump_component (FILE *, struct component *);
665 : : void
666 : 104 : dump_component (FILE *file, struct component *comp)
667 : : {
668 : 104 : dref a;
669 : 104 : unsigned i;
670 : :
671 : 208 : fprintf (file, "Component%s:\n",
672 : 104 : comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
673 : 383 : FOR_EACH_VEC_ELT (comp->refs, i, a)
674 : 175 : dump_dref (file, a);
675 : 104 : fprintf (file, "\n");
676 : 104 : }
677 : :
678 : : /* Dumps COMPS to FILE. */
679 : :
680 : : extern void dump_components (FILE *, struct component *);
681 : : void
682 : 55 : dump_components (FILE *file, struct component *comps)
683 : : {
684 : 55 : struct component *comp;
685 : :
686 : 159 : for (comp = comps; comp; comp = comp->next)
687 : 104 : dump_component (file, comp);
688 : 55 : }
689 : :
690 : : /* Frees a chain CHAIN. */
691 : :
692 : : void
693 : 99597 : pcom_worker::release_chain (chain_p chain)
694 : : {
695 : 99597 : dref ref;
696 : 99597 : unsigned i;
697 : :
698 : 99597 : if (chain == NULL)
699 : 99597 : return;
700 : :
701 : 153330 : FOR_EACH_VEC_ELT (chain->refs, i, ref)
702 : 85901 : free (ref);
703 : :
704 : 67429 : if (chain->init_seq)
705 : 0 : gimple_seq_discard (chain->init_seq);
706 : :
707 : 67429 : if (chain->fini_seq)
708 : 0 : gimple_seq_discard (chain->fini_seq);
709 : :
710 : 67429 : delete chain;
711 : : }
712 : :
713 : : /* Frees CHAINS. */
714 : :
715 : : void
716 : 418112 : pcom_worker::release_chains ()
717 : : {
718 : 418112 : unsigned i;
719 : 418112 : chain_p chain;
720 : :
721 : 444419 : FOR_EACH_VEC_ELT (m_chains, i, chain)
722 : 26307 : release_chain (chain);
723 : 418112 : }
724 : :
725 : : /* Frees list of components COMPS. */
726 : :
727 : : static void
728 : 167965 : release_components (struct component *comps)
729 : : {
730 : 167965 : struct component *act, *next;
731 : :
732 : 517179 : for (act = comps; act; act = next)
733 : : {
734 : 349214 : next = act->next;
735 : 349214 : delete act;
736 : : }
737 : 167965 : }
738 : :
739 : : /* Finds a root of tree given by FATHERS containing A, and performs path
740 : : shortening. */
741 : :
742 : : static unsigned
743 : 6831646 : component_of (vec<unsigned> &fathers, unsigned a)
744 : : {
745 : 6831646 : unsigned root, n;
746 : :
747 : 10668859 : for (root = a; root != fathers[root]; root = fathers[root])
748 : 3837213 : continue;
749 : :
750 : 10668859 : for (; a != root; a = n)
751 : : {
752 : 3837213 : n = fathers[a];
753 : 3837213 : fathers[a] = root;
754 : : }
755 : :
756 : 6831646 : return root;
757 : 3837213 : }
758 : :
759 : : /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
760 : : components, A and B are components to merge. */
761 : :
762 : : static void
763 : 351101 : merge_comps (vec<unsigned> &fathers, vec<unsigned> &sizes,
764 : : unsigned a, unsigned b)
765 : : {
766 : 351101 : unsigned ca = component_of (fathers, a);
767 : 351101 : unsigned cb = component_of (fathers, b);
768 : :
769 : 351101 : if (ca == cb)
770 : : return;
771 : :
772 : 351101 : if (sizes[ca] < sizes[cb])
773 : : {
774 : 16400 : sizes[cb] += sizes[ca];
775 : 16400 : fathers[ca] = cb;
776 : : }
777 : : else
778 : : {
779 : 334701 : sizes[ca] += sizes[cb];
780 : 334701 : fathers[cb] = ca;
781 : : }
782 : : }
783 : :
784 : : /* Returns true if A is a reference that is suitable for predictive commoning
785 : : in the innermost loop that contains it. REF_STEP is set according to the
786 : : step of the reference A. */
787 : :
788 : : static bool
789 : 1126929 : suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
790 : : {
791 : 1126929 : tree ref = DR_REF (a), step = DR_STEP (a);
792 : :
793 : 1126929 : if (!step
794 : 998380 : || TREE_THIS_VOLATILE (ref)
795 : 983995 : || !is_gimple_reg_type (TREE_TYPE (ref))
796 : 2080481 : || tree_could_throw_p (ref))
797 : 212352 : return false;
798 : :
799 : 914577 : if (integer_zerop (step))
800 : 58215 : *ref_step = RS_INVARIANT;
801 : 856362 : else if (integer_nonzerop (step))
802 : 807093 : *ref_step = RS_NONZERO;
803 : : else
804 : 49269 : *ref_step = RS_ANY;
805 : :
806 : : return true;
807 : : }
808 : :
809 : : /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
810 : :
811 : : void
812 : 206214 : pcom_worker::aff_combination_dr_offset (struct data_reference *dr,
813 : : aff_tree *offset)
814 : : {
815 : 206214 : tree type = TREE_TYPE (DR_OFFSET (dr));
816 : 206214 : aff_tree delta;
817 : :
818 : 206214 : tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset, &m_cache);
819 : 206214 : aff_combination_const (&delta, type, wi::to_poly_widest (DR_INIT (dr)));
820 : 206214 : aff_combination_add (offset, &delta);
821 : 206214 : }
822 : :
823 : : /* Determines number of iterations of the innermost enclosing loop before B
824 : : refers to exactly the same location as A and stores it to OFF. If A and
825 : : B do not have the same step, they never meet, or anything else fails,
826 : : returns false, otherwise returns true. Both A and B are assumed to
827 : : satisfy suitable_reference_p. */
828 : :
829 : : bool
830 : 251084 : pcom_worker::determine_offset (struct data_reference *a,
831 : : struct data_reference *b, poly_widest_int *off)
832 : : {
833 : 753252 : aff_tree diff, baseb, step;
834 : 251084 : tree typea, typeb;
835 : :
836 : : /* Check that both the references access the location in the same type. */
837 : 251084 : typea = TREE_TYPE (DR_REF (a));
838 : 251084 : typeb = TREE_TYPE (DR_REF (b));
839 : 251084 : if (!useless_type_conversion_p (typeb, typea))
840 : : return false;
841 : :
842 : : /* Check whether the base address and the step of both references is the
843 : : same. */
844 : 227676 : if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
845 : 227676 : || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
846 : 114040 : return false;
847 : :
848 : 113636 : if (integer_zerop (DR_STEP (a)))
849 : : {
850 : : /* If the references have loop invariant address, check that they access
851 : : exactly the same location. */
852 : 10537 : *off = 0;
853 : 10537 : return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
854 : 10537 : && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
855 : : }
856 : :
857 : : /* Compare the offsets of the addresses, and check whether the difference
858 : : is a multiple of step. */
859 : 103099 : aff_combination_dr_offset (a, &diff);
860 : 103099 : aff_combination_dr_offset (b, &baseb);
861 : 103099 : aff_combination_scale (&baseb, -1);
862 : 103099 : aff_combination_add (&diff, &baseb);
863 : :
864 : 103099 : tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
865 : : &step, &m_cache);
866 : 103099 : return aff_combination_constant_multiple_p (&diff, &step, off);
867 : 251084 : }
868 : :
869 : : /* Returns the last basic block in LOOP for that we are sure that
870 : : it is executed whenever the loop is entered. */
871 : :
872 : : static basic_block
873 : 250634 : last_always_executed_block (class loop *loop)
874 : : {
875 : 250634 : unsigned i;
876 : 250634 : auto_vec<edge> exits = get_loop_exit_edges (loop);
877 : 250634 : edge ex;
878 : 250634 : basic_block last = loop->latch;
879 : :
880 : 646356 : FOR_EACH_VEC_ELT (exits, i, ex)
881 : 395722 : last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
882 : :
883 : 250634 : return last;
884 : 250634 : }
885 : :
886 : : /* Splits dependence graph on DATAREFS described by DEPENDENCES to
887 : : components. */
888 : :
889 : : struct component *
890 : 250634 : pcom_worker::split_data_refs_to_components ()
891 : : {
892 : 250634 : unsigned i, n = m_datarefs.length ();
893 : 250634 : unsigned ca, ia, ib, bad;
894 : 250634 : struct data_reference *dr, *dra, *drb;
895 : 250634 : struct data_dependence_relation *ddr;
896 : 250634 : struct component *comp_list = NULL, *comp;
897 : 250634 : dref dataref;
898 : : /* Don't do store elimination if loop has multiple exit edges. */
899 : 250634 : bool eliminate_store_p = single_exit (m_loop) != NULL;
900 : 250634 : basic_block last_always_executed = last_always_executed_block (m_loop);
901 : 250634 : auto_bitmap no_store_store_comps;
902 : 250634 : auto_vec<unsigned> comp_father (n + 1);
903 : 250634 : auto_vec<unsigned> comp_size (n + 1);
904 : 250634 : comp_father.quick_grow (n + 1);
905 : 250634 : comp_size.quick_grow (n + 1);
906 : :
907 : 1231219 : FOR_EACH_VEC_ELT (m_datarefs, i, dr)
908 : : {
909 : 730120 : if (!DR_REF (dr))
910 : : /* A fake reference for call or asm_expr that may clobber memory;
911 : : just fail. */
912 : : return NULL;
913 : : /* predcom pass isn't prepared to handle calls with data references. */
914 : 730120 : if (is_gimple_call (DR_STMT (dr)))
915 : : return NULL;
916 : 729951 : dr->aux = (void *) (size_t) i;
917 : 729951 : comp_father[i] = i;
918 : 729951 : comp_size[i] = 1;
919 : : }
920 : :
921 : : /* A component reserved for the "bad" data references. */
922 : 250465 : comp_father[n] = n;
923 : 250465 : comp_size[n] = 1;
924 : :
925 : 979881 : FOR_EACH_VEC_ELT (m_datarefs, i, dr)
926 : : {
927 : 729416 : enum ref_step_type dummy;
928 : :
929 : 729416 : if (!suitable_reference_p (dr, &dummy))
930 : : {
931 : 212352 : ia = (unsigned) (size_t) dr->aux;
932 : 212352 : merge_comps (comp_father, comp_size, n, ia);
933 : : }
934 : : }
935 : :
936 : 9108361 : FOR_EACH_VEC_ELT (m_dependences, i, ddr)
937 : : {
938 : : poly_widest_int dummy_off;
939 : :
940 : 4428948 : if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
941 : 2044111 : continue;
942 : :
943 : 2384837 : dra = DDR_A (ddr);
944 : 2384837 : drb = DDR_B (ddr);
945 : :
946 : : /* Don't do store elimination if there is any unknown dependence for
947 : : any store data reference. */
948 : 1463349 : if ((DR_IS_WRITE (dra) || DR_IS_WRITE (drb))
949 : 2727012 : && (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
950 : 315106 : || DDR_NUM_DIST_VECTS (ddr) == 0))
951 : : eliminate_store_p = false;
952 : :
953 : 2384837 : ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
954 : 2384837 : ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
955 : 2384837 : if (ia == ib)
956 : 2005943 : continue;
957 : :
958 : 378894 : bad = component_of (comp_father, n);
959 : :
960 : : /* If both A and B are reads, we may ignore unsuitable dependences. */
961 : 378894 : if (DR_IS_READ (dra) && DR_IS_READ (drb))
962 : : {
963 : 152315 : if (ia == bad || ib == bad
964 : 317450 : || !determine_offset (dra, drb, &dummy_off))
965 : 160653 : continue;
966 : : }
967 : : /* If A is read and B write or vice versa and there is unsuitable
968 : : dependence, instead of merging both components into a component
969 : : that will certainly not pass suitable_component_p, just put the
970 : : read into bad component, perhaps at least the write together with
971 : : all the other data refs in it's component will be optimizable. */
972 : 196286 : else if (DR_IS_READ (dra) && ib != bad)
973 : : {
974 : 124278 : if (ia == bad)
975 : : {
976 : 67448 : bitmap_set_bit (no_store_store_comps, ib);
977 : 67448 : continue;
978 : : }
979 : 56830 : else if (!determine_offset (dra, drb, &dummy_off))
980 : : {
981 : 27826 : bitmap_set_bit (no_store_store_comps, ib);
982 : 27826 : merge_comps (comp_father, comp_size, bad, ia);
983 : 27826 : continue;
984 : : }
985 : : }
986 : 72008 : else if (DR_IS_READ (drb) && ia != bad)
987 : : {
988 : 23642 : if (ib == bad)
989 : : {
990 : 15226 : bitmap_set_bit (no_store_store_comps, ia);
991 : 15226 : continue;
992 : : }
993 : 8416 : else if (!determine_offset (dra, drb, &dummy_off))
994 : : {
995 : 3902 : bitmap_set_bit (no_store_store_comps, ia);
996 : 3902 : merge_comps (comp_father, comp_size, bad, ib);
997 : 3902 : continue;
998 : : }
999 : : }
1000 : 36915 : else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb)
1001 : 31304 : && ia != bad && ib != bad
1002 : 57799 : && !determine_offset (dra, drb, &dummy_off))
1003 : : {
1004 : 3182 : merge_comps (comp_father, comp_size, bad, ia);
1005 : 3182 : merge_comps (comp_father, comp_size, bad, ib);
1006 : 3182 : continue;
1007 : : }
1008 : :
1009 : 100657 : merge_comps (comp_father, comp_size, ia, ib);
1010 : 4428948 : }
1011 : :
1012 : 250465 : if (eliminate_store_p)
1013 : : {
1014 : 114535 : tree niters = number_of_latch_executions (m_loop);
1015 : :
1016 : : /* Don't do store elimination if niters info is unknown because stores
1017 : : in the last iteration can't be eliminated and we need to recover it
1018 : : after loop. */
1019 : 114535 : eliminate_store_p = (niters != NULL_TREE && niters != chrec_dont_know);
1020 : : }
1021 : :
1022 : 250465 : auto_vec<struct component *> comps;
1023 : 250465 : comps.safe_grow_cleared (n, true);
1024 : 250465 : bad = component_of (comp_father, n);
1025 : 1230346 : FOR_EACH_VEC_ELT (m_datarefs, i, dr)
1026 : : {
1027 : 729416 : ia = (unsigned) (size_t) dr->aux;
1028 : 729416 : ca = component_of (comp_father, ia);
1029 : 729416 : if (ca == bad)
1030 : 295130 : continue;
1031 : :
1032 : 434286 : comp = comps[ca];
1033 : 434286 : if (!comp)
1034 : : {
1035 : 378315 : comp = new component (eliminate_store_p);
1036 : 378315 : comp->refs.reserve_exact (comp_size[ca]);
1037 : 378315 : comps[ca] = comp;
1038 : : }
1039 : :
1040 : 434286 : dataref = XCNEW (class dref_d);
1041 : 434286 : dataref->ref = dr;
1042 : 434286 : dataref->stmt = DR_STMT (dr);
1043 : 434286 : dataref->offset = 0;
1044 : 434286 : dataref->distance = 0;
1045 : :
1046 : 434286 : dataref->always_accessed
1047 : 434286 : = dominated_by_p (CDI_DOMINATORS, last_always_executed,
1048 : 434286 : gimple_bb (dataref->stmt));
1049 : 434286 : dataref->pos = comp->refs.length ();
1050 : 434286 : comp->refs.quick_push (dataref);
1051 : : }
1052 : :
1053 : 250465 : if (eliminate_store_p)
1054 : : {
1055 : 96497 : bitmap_iterator bi;
1056 : 97492 : EXECUTE_IF_SET_IN_BITMAP (no_store_store_comps, 0, ia, bi)
1057 : : {
1058 : 995 : ca = component_of (comp_father, ia);
1059 : 995 : if (ca != bad)
1060 : 889 : comps[ca]->eliminate_store_p = false;
1061 : : }
1062 : : }
1063 : :
1064 : 979881 : for (i = 0; i < n; i++)
1065 : : {
1066 : 729416 : comp = comps[i];
1067 : 729416 : if (comp)
1068 : : {
1069 : 378315 : comp->next = comp_list;
1070 : 378315 : comp_list = comp;
1071 : : }
1072 : : }
1073 : 250465 : return comp_list;
1074 : 501099 : }
1075 : :
1076 : : /* Returns true if the component COMP satisfies the conditions
1077 : : described in 2) at the beginning of this file. */
1078 : :
1079 : : bool
1080 : 378315 : pcom_worker::suitable_component_p (struct component *comp)
1081 : : {
1082 : 378315 : unsigned i;
1083 : 378315 : dref a, first;
1084 : 378315 : basic_block ba, bp = m_loop->header;
1085 : 378315 : bool ok, has_write = false;
1086 : :
1087 : 777485 : FOR_EACH_VEC_ELT (comp->refs, i, a)
1088 : : {
1089 : 421535 : ba = gimple_bb (a->stmt);
1090 : :
1091 : 421535 : if (!just_once_each_iteration_p (m_loop, ba))
1092 : : return false;
1093 : :
1094 : 399170 : gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
1095 : 399170 : bp = ba;
1096 : :
1097 : 399170 : if (DR_IS_WRITE (a->ref))
1098 : 138957 : has_write = true;
1099 : : }
1100 : :
1101 : 355950 : first = comp->refs[0];
1102 : 355950 : ok = suitable_reference_p (first->ref, &comp->comp_step);
1103 : 355950 : gcc_assert (ok);
1104 : 355950 : first->offset = 0;
1105 : :
1106 : 753406 : FOR_EACH_VEC_ELT (comp->refs, i, a)
1107 : : {
1108 : 397513 : if (has_write && comp->comp_step == RS_NONZERO)
1109 : : {
1110 : : /* Punt for non-invariant references where step isn't a multiple
1111 : : of reference size. If step is smaller than reference size,
1112 : : it overlaps the access in next iteration, if step is larger,
1113 : : but not multiple of the access size, there could be overlap
1114 : : in some later iteration. There might be more latent issues
1115 : : about this in predcom or data reference analysis. If the
1116 : : reference is a COMPONENT_REF, also check if step isn't a
1117 : : multiple of the containg aggregate size. See PR111683. */
1118 : 141032 : tree ref = DR_REF (a->ref);
1119 : 141032 : tree step = DR_STEP (a->ref);
1120 : 141032 : if (TREE_CODE (ref) == COMPONENT_REF
1121 : 141032 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
1122 : 55 : ref = TREE_OPERAND (ref, 0);
1123 : 141104 : do
1124 : : {
1125 : 141068 : tree sz = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1126 : 141068 : if (TREE_CODE (sz) != INTEGER_CST)
1127 : 57 : return false;
1128 : 282136 : if (wi::multiple_of_p (wi::to_offset (step),
1129 : 282136 : wi::to_offset (sz), SIGNED))
1130 : : break;
1131 : 93 : if (TREE_CODE (ref) != COMPONENT_REF)
1132 : : return false;
1133 : 36 : ref = TREE_OPERAND (ref, 0);
1134 : 36 : }
1135 : : while (1);
1136 : : }
1137 : 397456 : if (i == 0)
1138 : 355893 : continue;
1139 : : /* Polynomial offsets are no use, since we need to know the
1140 : : gap between iteration numbers at compile time. */
1141 : : poly_widest_int offset;
1142 : 41563 : if (!determine_offset (first->ref, a->ref, &offset)
1143 : 41563 : || !offset.is_constant (&a->offset))
1144 : 0 : return false;
1145 : :
1146 : 41563 : enum ref_step_type a_step;
1147 : 41563 : gcc_checking_assert (suitable_reference_p (a->ref, &a_step)
1148 : : && a_step == comp->comp_step);
1149 : 41563 : }
1150 : :
1151 : : /* If there is a write inside the component, we must know whether the
1152 : : step is nonzero or not -- we would not otherwise be able to recognize
1153 : : whether the value accessed by reads comes from the OFFSET-th iteration
1154 : : or the previous one. */
1155 : 355893 : if (has_write && comp->comp_step == RS_ANY)
1156 : : return false;
1157 : :
1158 : : return true;
1159 : : }
1160 : :
1161 : : /* Check the conditions on references inside each of components COMPS,
1162 : : and remove the unsuitable components from the list. The new list
1163 : : of components is returned. The conditions are described in 2) at
1164 : : the beginning of this file. */
1165 : :
1166 : : struct component *
1167 : 167965 : pcom_worker::filter_suitable_components (struct component *comps)
1168 : : {
1169 : 167965 : struct component **comp, *act;
1170 : :
1171 : 546280 : for (comp = &comps; *comp; )
1172 : : {
1173 : 378315 : act = *comp;
1174 : 378315 : if (suitable_component_p (act))
1175 : 349214 : comp = &act->next;
1176 : : else
1177 : : {
1178 : 29101 : dref ref;
1179 : 29101 : unsigned i;
1180 : :
1181 : 29101 : *comp = act->next;
1182 : 73788 : FOR_EACH_VEC_ELT (act->refs, i, ref)
1183 : 44687 : free (ref);
1184 : 29101 : delete act;
1185 : : }
1186 : : }
1187 : :
1188 : 167965 : return comps;
1189 : : }
1190 : :
1191 : : /* Compares two drefs A and B by their offset and position. Callback for
1192 : : qsort. */
1193 : :
1194 : : static int
1195 : 183561 : order_drefs (const void *a, const void *b)
1196 : : {
1197 : 183561 : const dref *const da = (const dref *) a;
1198 : 183561 : const dref *const db = (const dref *) b;
1199 : 183561 : int offcmp = wi::cmps ((*da)->offset, (*db)->offset);
1200 : :
1201 : 183561 : if (offcmp != 0)
1202 : : return offcmp;
1203 : :
1204 : 95360 : return (*da)->pos - (*db)->pos;
1205 : : }
1206 : :
1207 : : /* Compares two drefs A and B by their position. Callback for qsort. */
1208 : :
1209 : : static int
1210 : 48 : order_drefs_by_pos (const void *a, const void *b)
1211 : : {
1212 : 48 : const dref *const da = (const dref *) a;
1213 : 48 : const dref *const db = (const dref *) b;
1214 : :
1215 : 48 : return (*da)->pos - (*db)->pos;
1216 : : }
1217 : :
1218 : : /* Returns root of the CHAIN. */
1219 : :
1220 : : static inline dref
1221 : 94003 : get_chain_root (chain_p chain)
1222 : : {
1223 : 188006 : return chain->refs[0];
1224 : : }
1225 : :
1226 : : /* Given CHAIN, returns the last write ref at DISTANCE, or NULL if it doesn't
1227 : : exist. */
1228 : :
1229 : : static inline dref
1230 : 95 : get_chain_last_write_at (chain_p chain, unsigned distance)
1231 : : {
1232 : 327 : for (unsigned i = chain->refs.length (); i > 0; i--)
1233 : 220 : if (DR_IS_WRITE (chain->refs[i - 1]->ref)
1234 : 220 : && distance == chain->refs[i - 1]->distance)
1235 : : return chain->refs[i - 1];
1236 : :
1237 : : return NULL;
1238 : : }
1239 : :
1240 : : /* Given CHAIN, returns the last write ref with the same distance before load
1241 : : at index LOAD_IDX, or NULL if it doesn't exist. */
1242 : :
1243 : : static inline dref
1244 : 5 : get_chain_last_write_before_load (chain_p chain, unsigned load_idx)
1245 : : {
1246 : 5 : gcc_assert (load_idx < chain->refs.length ());
1247 : :
1248 : 5 : unsigned distance = chain->refs[load_idx]->distance;
1249 : :
1250 : 5 : for (unsigned i = load_idx; i > 0; i--)
1251 : 5 : if (DR_IS_WRITE (chain->refs[i - 1]->ref)
1252 : 5 : && distance == chain->refs[i - 1]->distance)
1253 : : return chain->refs[i - 1];
1254 : :
1255 : : return NULL;
1256 : : }
1257 : :
1258 : : /* Adds REF to the chain CHAIN. */
1259 : :
1260 : : static void
1261 : 16196 : add_ref_to_chain (chain_p chain, dref ref)
1262 : : {
1263 : 16196 : dref root = get_chain_root (chain);
1264 : :
1265 : 16196 : gcc_assert (wi::les_p (root->offset, ref->offset));
1266 : 16196 : widest_int dist = ref->offset - root->offset;
1267 : 16196 : gcc_assert (wi::fits_uhwi_p (dist));
1268 : :
1269 : 16196 : chain->refs.safe_push (ref);
1270 : :
1271 : 16196 : ref->distance = dist.to_uhwi ();
1272 : :
1273 : 16196 : if (ref->distance >= chain->length)
1274 : : {
1275 : 16196 : chain->length = ref->distance;
1276 : 16196 : chain->has_max_use_after = false;
1277 : : }
1278 : :
1279 : : /* Promote this chain to CT_STORE_STORE if it has multiple stores. */
1280 : 16196 : if (DR_IS_WRITE (ref->ref))
1281 : 67 : chain->type = CT_STORE_STORE;
1282 : :
1283 : : /* Don't set the flag for store-store chain since there is no use. */
1284 : 16196 : if (chain->type != CT_STORE_STORE
1285 : 16127 : && ref->distance == chain->length
1286 : 16127 : && ref->pos > root->pos)
1287 : 6159 : chain->has_max_use_after = true;
1288 : :
1289 : 16196 : chain->all_always_accessed &= ref->always_accessed;
1290 : 16196 : }
1291 : :
1292 : : /* Returns the chain for invariant component COMP. */
1293 : :
1294 : : static chain_p
1295 : 13274 : make_invariant_chain (struct component *comp)
1296 : : {
1297 : 13274 : chain_p chain = new struct chain (CT_INVARIANT);
1298 : 13274 : unsigned i;
1299 : 13274 : dref ref;
1300 : :
1301 : 13274 : chain->all_always_accessed = true;
1302 : :
1303 : 28779 : FOR_EACH_VEC_ELT (comp->refs, i, ref)
1304 : : {
1305 : 15505 : chain->refs.safe_push (ref);
1306 : 15505 : chain->all_always_accessed &= ref->always_accessed;
1307 : : }
1308 : :
1309 : 13274 : chain->inits = vNULL;
1310 : 13274 : chain->finis = vNULL;
1311 : :
1312 : 13274 : return chain;
1313 : : }
1314 : :
1315 : : /* Make a new chain of type TYPE rooted at REF. */
1316 : :
1317 : : static chain_p
1318 : 54126 : make_rooted_chain (dref ref, enum chain_type type)
1319 : : {
1320 : 54126 : chain_p chain = new struct chain (type);
1321 : :
1322 : 54126 : chain->refs.safe_push (ref);
1323 : 54126 : chain->all_always_accessed = ref->always_accessed;
1324 : 54126 : ref->distance = 0;
1325 : :
1326 : 54126 : chain->inits = vNULL;
1327 : 54126 : chain->finis = vNULL;
1328 : :
1329 : 54126 : return chain;
1330 : : }
1331 : :
1332 : : /* Returns true if CHAIN is not trivial. */
1333 : :
1334 : : static bool
1335 : 86294 : nontrivial_chain_p (chain_p chain)
1336 : : {
1337 : 54126 : return chain != NULL && chain->refs.length () > 1;
1338 : : }
1339 : :
1340 : : /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1341 : : is no such name. */
1342 : :
1343 : : static tree
1344 : 77346 : name_for_ref (dref ref)
1345 : : {
1346 : 77346 : tree name;
1347 : :
1348 : 77346 : if (is_gimple_assign (ref->stmt))
1349 : : {
1350 : 77346 : if (!ref->ref || DR_IS_READ (ref->ref))
1351 : 77346 : name = gimple_assign_lhs (ref->stmt);
1352 : : else
1353 : 0 : name = gimple_assign_rhs1 (ref->stmt);
1354 : : }
1355 : : else
1356 : 0 : name = PHI_RESULT (ref->stmt);
1357 : :
1358 : 77346 : return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1359 : : }
1360 : :
1361 : : /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1362 : : iterations of the innermost enclosing loop). */
1363 : :
1364 : : bool
1365 : 8 : pcom_worker::valid_initializer_p (struct data_reference *ref, unsigned distance,
1366 : : struct data_reference *root)
1367 : : {
1368 : 32 : aff_tree diff, base, step;
1369 : : poly_widest_int off;
1370 : :
1371 : : /* Both REF and ROOT must be accessing the same object. */
1372 : 8 : if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1373 : : return false;
1374 : :
1375 : : /* The initializer is defined outside of loop, hence its address must be
1376 : : invariant inside the loop. */
1377 : 8 : gcc_assert (integer_zerop (DR_STEP (ref)));
1378 : :
1379 : : /* If the address of the reference is invariant, initializer must access
1380 : : exactly the same location. */
1381 : 8 : if (integer_zerop (DR_STEP (root)))
1382 : 0 : return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1383 : 0 : && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1384 : :
1385 : : /* Verify that this index of REF is equal to the root's index at
1386 : : -DISTANCE-th iteration. */
1387 : 8 : aff_combination_dr_offset (root, &diff);
1388 : 8 : aff_combination_dr_offset (ref, &base);
1389 : 8 : aff_combination_scale (&base, -1);
1390 : 8 : aff_combination_add (&diff, &base);
1391 : :
1392 : 8 : tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
1393 : : &step, &m_cache);
1394 : 8 : if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1395 : : return false;
1396 : :
1397 : 8 : if (maybe_ne (off, distance))
1398 : : return false;
1399 : :
1400 : : return true;
1401 : 8 : }
1402 : :
1403 : : /* Finds looparound phi node of loop that copies the value of REF, and if its
1404 : : initial value is correct (equal to initial value of REF shifted by one
1405 : : iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1406 : : is the root of the current chain. */
1407 : :
1408 : : gphi *
1409 : 31937 : pcom_worker::find_looparound_phi (dref ref, dref root)
1410 : : {
1411 : 31937 : tree name, init, init_ref;
1412 : 31937 : gimple *init_stmt;
1413 : 31937 : edge latch = loop_latch_edge (m_loop);
1414 : 31937 : struct data_reference init_dr;
1415 : 31937 : gphi_iterator psi;
1416 : :
1417 : 31937 : if (is_gimple_assign (ref->stmt))
1418 : : {
1419 : 31936 : if (DR_IS_READ (ref->ref))
1420 : 29708 : name = gimple_assign_lhs (ref->stmt);
1421 : : else
1422 : 2228 : name = gimple_assign_rhs1 (ref->stmt);
1423 : : }
1424 : : else
1425 : 1 : name = PHI_RESULT (ref->stmt);
1426 : 31937 : if (!name)
1427 : : return NULL;
1428 : :
1429 : 31937 : tree entry_vuse = NULL_TREE;
1430 : 31937 : gphi *phi = NULL;
1431 : 289297 : for (psi = gsi_start_phis (m_loop->header); !gsi_end_p (psi); gsi_next (&psi))
1432 : : {
1433 : 257372 : gphi *p = psi.phi ();
1434 : 257372 : if (PHI_ARG_DEF_FROM_EDGE (p, latch) == name)
1435 : : phi = p;
1436 : 514720 : else if (virtual_operand_p (gimple_phi_result (p)))
1437 : 23579 : entry_vuse = PHI_ARG_DEF_FROM_EDGE (p, loop_preheader_edge (m_loop));
1438 : 257372 : if (phi && entry_vuse)
1439 : : break;
1440 : : }
1441 : 31937 : if (!phi || !entry_vuse)
1442 : : return NULL;
1443 : :
1444 : 12 : init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (m_loop));
1445 : 12 : if (TREE_CODE (init) != SSA_NAME)
1446 : : return NULL;
1447 : 10 : init_stmt = SSA_NAME_DEF_STMT (init);
1448 : 10 : if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1449 : : return NULL;
1450 : 8 : gcc_assert (gimple_assign_lhs (init_stmt) == init);
1451 : :
1452 : 8 : init_ref = gimple_assign_rhs1 (init_stmt);
1453 : 8 : if (!REFERENCE_CLASS_P (init_ref)
1454 : 8 : && !DECL_P (init_ref))
1455 : : return NULL;
1456 : :
1457 : : /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1458 : : loop enclosing PHI). */
1459 : 8 : memset (&init_dr, 0, sizeof (struct data_reference));
1460 : 8 : DR_REF (&init_dr) = init_ref;
1461 : 8 : DR_STMT (&init_dr) = phi;
1462 : 8 : if (!dr_analyze_innermost (&DR_INNERMOST (&init_dr), init_ref, m_loop,
1463 : : init_stmt))
1464 : : return NULL;
1465 : :
1466 : 8 : if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1467 : : return NULL;
1468 : :
1469 : : /* Make sure nothing clobbers the location we re-use the initial value
1470 : : from. */
1471 : 16 : if (entry_vuse != gimple_vuse (init_stmt))
1472 : : {
1473 : 7 : ao_ref ref;
1474 : 7 : ao_ref_init (&ref, init_ref);
1475 : 7 : unsigned limit = param_sccvn_max_alias_queries_per_access;
1476 : 7 : tree vdef = entry_vuse;
1477 : 7 : do
1478 : : {
1479 : 7 : gimple *def = SSA_NAME_DEF_STMT (vdef);
1480 : 7 : if (limit-- == 0 || gimple_code (def) == GIMPLE_PHI)
1481 : 7 : return NULL;
1482 : 7 : if (stmt_may_clobber_ref_p_1 (def, &ref))
1483 : : /* When the stmt is an assign to init_ref we could in theory
1484 : : use its RHS for the initial value of the looparound PHI
1485 : : we replace in prepare_initializers_chain, but we have
1486 : : no convenient place to store this info at the moment. */
1487 : : return NULL;
1488 : 0 : vdef = gimple_vuse (def);
1489 : : }
1490 : 0 : while (vdef != gimple_vuse (init_stmt));
1491 : : }
1492 : :
1493 : : return phi;
1494 : : }
1495 : :
1496 : : /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1497 : :
1498 : : static void
1499 : 1 : insert_looparound_copy (chain_p chain, dref ref, gphi *phi)
1500 : : {
1501 : 1 : dref nw = XCNEW (class dref_d), aref;
1502 : 1 : unsigned i;
1503 : :
1504 : 1 : nw->stmt = phi;
1505 : 1 : nw->distance = ref->distance + 1;
1506 : 1 : nw->always_accessed = 1;
1507 : :
1508 : 2 : FOR_EACH_VEC_ELT (chain->refs, i, aref)
1509 : 2 : if (aref->distance >= nw->distance)
1510 : : break;
1511 : 1 : chain->refs.safe_insert (i, nw);
1512 : :
1513 : 1 : if (nw->distance > chain->length)
1514 : : {
1515 : 0 : chain->length = nw->distance;
1516 : 0 : chain->has_max_use_after = false;
1517 : : }
1518 : 1 : }
1519 : :
1520 : : /* For references in CHAIN that are copied around the loop (created previously
1521 : : by PRE, or by user), add the results of such copies to the chain. This
1522 : : enables us to remove the copies by unrolling, and may need less registers
1523 : : (also, it may allow us to combine chains together). */
1524 : :
1525 : : void
1526 : 15866 : pcom_worker::add_looparound_copies (chain_p chain)
1527 : : {
1528 : 15866 : unsigned i;
1529 : 15866 : dref ref, root = get_chain_root (chain);
1530 : 15866 : gphi *phi;
1531 : :
1532 : 15866 : if (chain->type == CT_STORE_STORE)
1533 : 15866 : return;
1534 : :
1535 : 47749 : FOR_EACH_VEC_ELT (chain->refs, i, ref)
1536 : : {
1537 : 31937 : phi = find_looparound_phi (ref, root);
1538 : 31937 : if (!phi)
1539 : 31936 : continue;
1540 : :
1541 : 1 : bitmap_set_bit (m_looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1542 : 1 : insert_looparound_copy (chain, ref, phi);
1543 : : }
1544 : : }
1545 : :
1546 : : /* Find roots of the values and determine distances in the component COMP.
1547 : : The references are redistributed into chains. */
1548 : :
1549 : : void
1550 : 349214 : pcom_worker::determine_roots_comp (struct component *comp)
1551 : : {
1552 : 349214 : unsigned i;
1553 : 349214 : dref a;
1554 : 349214 : chain_p chain = NULL;
1555 : 349214 : widest_int last_ofs = 0;
1556 : 349214 : enum chain_type type;
1557 : :
1558 : : /* Invariants are handled specially. */
1559 : 349214 : if (comp->comp_step == RS_INVARIANT)
1560 : : {
1561 : 13274 : chain = make_invariant_chain (comp);
1562 : 13274 : m_chains.safe_push (chain);
1563 : 13274 : return;
1564 : : }
1565 : :
1566 : : /* Trivial component. */
1567 : 335940 : if (comp->refs.length () <= 1)
1568 : : {
1569 : 303772 : if (comp->refs.length () == 1)
1570 : : {
1571 : 303772 : free (comp->refs[0]);
1572 : 303772 : comp->refs.truncate (0);
1573 : : }
1574 : 303772 : return;
1575 : : }
1576 : :
1577 : 32168 : comp->refs.qsort (order_drefs);
1578 : :
1579 : : /* For Store-Store chain, we only support load if it is dominated by a
1580 : : store statement in the same iteration of loop. */
1581 : 32168 : if (comp->eliminate_store_p)
1582 : 16857 : for (a = NULL, i = 0; i < comp->refs.length (); i++)
1583 : : {
1584 : 16796 : if (DR_IS_WRITE (comp->refs[i]->ref))
1585 : : a = comp->refs[i];
1586 : 15136 : else if (a == NULL || a->offset != comp->refs[i]->offset)
1587 : : {
1588 : : /* If there is load that is not dominated by a store in the
1589 : : same iteration of loop, clear the flag so no Store-Store
1590 : : chain is generated for this component. */
1591 : 15123 : comp->eliminate_store_p = false;
1592 : 15123 : break;
1593 : : }
1594 : : }
1595 : :
1596 : : /* Determine roots and create chains for components. */
1597 : 102490 : FOR_EACH_VEC_ELT (comp->refs, i, a)
1598 : : {
1599 : 194770 : if (!chain
1600 : 38154 : || (chain->type == CT_LOAD && DR_IS_WRITE (a->ref))
1601 : 20751 : || (!comp->eliminate_store_p && DR_IS_WRITE (a->ref))
1602 : 178798 : || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
1603 : : {
1604 : 54126 : if (nontrivial_chain_p (chain))
1605 : : {
1606 : 943 : add_looparound_copies (chain);
1607 : 943 : m_chains.safe_push (chain);
1608 : : }
1609 : : else
1610 : 53183 : release_chain (chain);
1611 : :
1612 : : /* Determine type of the chain. If the root reference is a load,
1613 : : this can only be a CT_LOAD chain; other chains are intialized
1614 : : to CT_STORE_LOAD and might be promoted to CT_STORE_STORE when
1615 : : new reference is added. */
1616 : 54126 : type = DR_IS_READ (a->ref) ? CT_LOAD : CT_STORE_LOAD;
1617 : 54126 : chain = make_rooted_chain (a, type);
1618 : 54126 : last_ofs = a->offset;
1619 : 54126 : continue;
1620 : : }
1621 : :
1622 : 16196 : add_ref_to_chain (chain, a);
1623 : : }
1624 : :
1625 : 32168 : if (nontrivial_chain_p (chain))
1626 : : {
1627 : 14923 : add_looparound_copies (chain);
1628 : 14923 : m_chains.safe_push (chain);
1629 : : }
1630 : : else
1631 : 17245 : release_chain (chain);
1632 : 349214 : }
1633 : :
1634 : : /* Find roots of the values and determine distances in components COMPS, and
1635 : : separates the references to chains. */
1636 : :
1637 : : void
1638 : 167965 : pcom_worker::determine_roots (struct component *comps)
1639 : : {
1640 : 167965 : struct component *comp;
1641 : :
1642 : 517179 : for (comp = comps; comp; comp = comp->next)
1643 : 349214 : determine_roots_comp (comp);
1644 : 167965 : }
1645 : :
1646 : : /* Replace the reference in statement STMT with temporary variable
1647 : : NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1648 : : the reference in the statement. IN_LHS is true if the reference
1649 : : is in the lhs of STMT, false if it is in rhs. */
1650 : :
1651 : : static void
1652 : 34549 : replace_ref_with (gimple *stmt, tree new_tree, bool set, bool in_lhs)
1653 : : {
1654 : 34549 : tree val;
1655 : 34549 : gassign *new_stmt;
1656 : 34549 : gimple_stmt_iterator bsi, psi;
1657 : :
1658 : 34549 : if (gimple_code (stmt) == GIMPLE_PHI)
1659 : : {
1660 : 1 : gcc_assert (!in_lhs && !set);
1661 : :
1662 : 1 : val = PHI_RESULT (stmt);
1663 : 1 : bsi = gsi_after_labels (gimple_bb (stmt));
1664 : 1 : psi = gsi_for_stmt (stmt);
1665 : 1 : remove_phi_node (&psi, false);
1666 : :
1667 : : /* Turn the phi node into GIMPLE_ASSIGN. */
1668 : 1 : new_stmt = gimple_build_assign (val, new_tree);
1669 : 1 : gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1670 : 17604 : return;
1671 : : }
1672 : :
1673 : : /* Since the reference is of gimple_reg type, it should only
1674 : : appear as lhs or rhs of modify statement. */
1675 : 34548 : gcc_assert (is_gimple_assign (stmt));
1676 : :
1677 : 34548 : bsi = gsi_for_stmt (stmt);
1678 : :
1679 : : /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1680 : 34548 : if (!set)
1681 : : {
1682 : 17602 : gcc_assert (!in_lhs);
1683 : 17602 : gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1684 : 17602 : stmt = gsi_stmt (bsi);
1685 : 17602 : update_stmt (stmt);
1686 : 17602 : return;
1687 : : }
1688 : :
1689 : 16946 : if (in_lhs)
1690 : : {
1691 : : /* We have statement
1692 : :
1693 : : OLD = VAL
1694 : :
1695 : : If OLD is a memory reference, then VAL is gimple_val, and we transform
1696 : : this to
1697 : :
1698 : : OLD = VAL
1699 : : NEW = VAL
1700 : :
1701 : : Otherwise, we are replacing a combination chain,
1702 : : VAL is the expression that performs the combination, and OLD is an
1703 : : SSA name. In this case, we transform the assignment to
1704 : :
1705 : : OLD = VAL
1706 : : NEW = OLD
1707 : :
1708 : : */
1709 : :
1710 : 3719 : val = gimple_assign_lhs (stmt);
1711 : 3719 : if (TREE_CODE (val) != SSA_NAME)
1712 : : {
1713 : 3703 : val = gimple_assign_rhs1 (stmt);
1714 : 3703 : gcc_assert (gimple_assign_single_p (stmt));
1715 : 3703 : if (TREE_CLOBBER_P (val))
1716 : 0 : val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (new_tree));
1717 : : else
1718 : 3703 : gcc_assert (gimple_assign_copy_p (stmt));
1719 : : }
1720 : : }
1721 : : else
1722 : : {
1723 : : /* VAL = OLD
1724 : :
1725 : : is transformed to
1726 : :
1727 : : VAL = OLD
1728 : : NEW = VAL */
1729 : :
1730 : 13227 : val = gimple_assign_lhs (stmt);
1731 : : }
1732 : :
1733 : 16946 : new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1734 : 16946 : gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1735 : : }
1736 : :
1737 : : /* Returns a memory reference to DR in the (NITERS + ITER)-th iteration
1738 : : of the loop it was analyzed in. Append init stmts to STMTS. */
1739 : :
1740 : : static tree
1741 : 24581 : ref_at_iteration (data_reference_p dr, int iter,
1742 : : gimple_seq *stmts, tree niters = NULL_TREE)
1743 : : {
1744 : 24581 : tree off = DR_OFFSET (dr);
1745 : 24581 : tree coff = DR_INIT (dr);
1746 : 24581 : tree ref = DR_REF (dr);
1747 : 24581 : enum tree_code ref_code = ERROR_MARK;
1748 : 24581 : tree ref_type = NULL_TREE;
1749 : 24581 : tree ref_op1 = NULL_TREE;
1750 : 24581 : tree ref_op2 = NULL_TREE;
1751 : 24581 : tree new_offset;
1752 : :
1753 : 24581 : if (iter != 0)
1754 : : {
1755 : 24543 : new_offset = size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter));
1756 : 24543 : if (TREE_CODE (new_offset) == INTEGER_CST)
1757 : 24537 : coff = size_binop (PLUS_EXPR, coff, new_offset);
1758 : : else
1759 : 6 : off = size_binop (PLUS_EXPR, off, new_offset);
1760 : : }
1761 : :
1762 : 24581 : if (niters != NULL_TREE)
1763 : : {
1764 : 66 : niters = fold_convert (ssizetype, niters);
1765 : 66 : new_offset = size_binop (MULT_EXPR, DR_STEP (dr), niters);
1766 : 66 : if (TREE_CODE (niters) == INTEGER_CST)
1767 : 40 : coff = size_binop (PLUS_EXPR, coff, new_offset);
1768 : : else
1769 : 26 : off = size_binop (PLUS_EXPR, off, new_offset);
1770 : : }
1771 : :
1772 : : /* While data-ref analysis punts on bit offsets it still handles
1773 : : bitfield accesses at byte boundaries. Cope with that. Note that
1774 : : if the bitfield object also starts at a byte-boundary we can simply
1775 : : replicate the COMPONENT_REF, but we have to subtract the component's
1776 : : byte-offset from the MEM_REF address first.
1777 : : Otherwise we simply build a BIT_FIELD_REF knowing that the bits
1778 : : start at offset zero. */
1779 : 24581 : if (TREE_CODE (ref) == COMPONENT_REF
1780 : 24581 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
1781 : : {
1782 : 79 : unsigned HOST_WIDE_INT boff;
1783 : 79 : tree field = TREE_OPERAND (ref, 1);
1784 : 79 : tree offset = component_ref_field_offset (ref);
1785 : 79 : ref_type = TREE_TYPE (ref);
1786 : 79 : boff = tree_to_uhwi (DECL_FIELD_BIT_OFFSET (field));
1787 : : /* This can occur in Ada. See the comment in get_bit_range. */
1788 : 79 : if (boff % BITS_PER_UNIT != 0
1789 : 79 : || !tree_fits_uhwi_p (offset))
1790 : : {
1791 : 0 : ref_code = BIT_FIELD_REF;
1792 : 0 : ref_op1 = DECL_SIZE (field);
1793 : 0 : ref_op2 = bitsize_zero_node;
1794 : : }
1795 : : else
1796 : : {
1797 : 79 : boff >>= LOG2_BITS_PER_UNIT;
1798 : 79 : boff += tree_to_uhwi (offset);
1799 : 79 : coff = size_binop (MINUS_EXPR, coff, ssize_int (boff));
1800 : 79 : ref_code = COMPONENT_REF;
1801 : 79 : ref_op1 = field;
1802 : 79 : ref_op2 = TREE_OPERAND (ref, 2);
1803 : 79 : ref = TREE_OPERAND (ref, 0);
1804 : : }
1805 : : }
1806 : : /* We may not associate the constant offset across the pointer plus
1807 : : expression because that might form a pointer to before the object
1808 : : then. But for some cases we can retain that to allow tree_could_trap_p
1809 : : to return false - see gcc.dg/tree-ssa/predcom-1.c */
1810 : 24581 : tree addr, alias_ptr;
1811 : 24581 : if (integer_zerop (off)
1812 : 24581 : && TREE_CODE (DR_BASE_ADDRESS (dr)) != POINTER_PLUS_EXPR)
1813 : : {
1814 : 23435 : alias_ptr = fold_convert (reference_alias_ptr_type (ref), coff);
1815 : 23435 : addr = DR_BASE_ADDRESS (dr);
1816 : : }
1817 : : else
1818 : : {
1819 : 1146 : alias_ptr = build_zero_cst (reference_alias_ptr_type (ref));
1820 : 1146 : off = size_binop (PLUS_EXPR, off, coff);
1821 : 1146 : addr = fold_build_pointer_plus (DR_BASE_ADDRESS (dr), off);
1822 : : }
1823 : 24581 : addr = force_gimple_operand_1 (unshare_expr (addr), stmts,
1824 : : is_gimple_mem_ref_addr, NULL_TREE);
1825 : 24581 : tree type = build_aligned_type (TREE_TYPE (ref),
1826 : : get_object_alignment (ref));
1827 : 24581 : ref = build2 (MEM_REF, type, addr, alias_ptr);
1828 : 24581 : copy_ref_info (ref, DR_REF (dr));
1829 : 24581 : if (ref_type)
1830 : 79 : ref = build3 (ref_code, ref_type, ref, ref_op1, ref_op2);
1831 : 24581 : return ref;
1832 : : }
1833 : :
1834 : : /* Get the initialization expression for the INDEX-th temporary variable
1835 : : of CHAIN. */
1836 : :
1837 : : static tree
1838 : 10991 : get_init_expr (chain_p chain, unsigned index)
1839 : : {
1840 : 10991 : if (chain->type == CT_COMBINATION)
1841 : : {
1842 : 43 : tree e1 = get_init_expr (chain->ch1, index);
1843 : 43 : tree e2 = get_init_expr (chain->ch2, index);
1844 : :
1845 : 43 : return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1846 : : }
1847 : : else
1848 : 10948 : return chain->inits[index];
1849 : : }
1850 : :
1851 : : /* Returns a new temporary variable used for the I-th variable carrying
1852 : : value of REF. The variable's uid is marked in TMP_VARS. */
1853 : :
1854 : : static tree
1855 : 18540 : predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1856 : : {
1857 : 18540 : tree type = TREE_TYPE (ref);
1858 : : /* We never access the components of the temporary variable in predictive
1859 : : commoning. */
1860 : 18540 : tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1861 : 18540 : bitmap_set_bit (tmp_vars, DECL_UID (var));
1862 : 18540 : return var;
1863 : : }
1864 : :
1865 : : /* Creates the variables for CHAIN, as well as phi nodes for them and
1866 : : initialization on entry to LOOP. Uids of the newly created
1867 : : temporary variables are marked in TMP_VARS. */
1868 : :
1869 : : static void
1870 : 15460 : initialize_root_vars (class loop *loop, chain_p chain, bitmap tmp_vars)
1871 : : {
1872 : 15460 : unsigned i;
1873 : 15460 : unsigned n = chain->length;
1874 : 15460 : dref root = get_chain_root (chain);
1875 : 15460 : bool reuse_first = !chain->has_max_use_after;
1876 : 15460 : tree ref, init, var, next;
1877 : 15460 : gphi *phi;
1878 : 15460 : gimple_seq stmts;
1879 : 15460 : edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1880 : :
1881 : : /* If N == 0, then all the references are within the single iteration. And
1882 : : since this is an nonempty chain, reuse_first cannot be true. */
1883 : 15460 : gcc_assert (n > 0 || !reuse_first);
1884 : :
1885 : 15460 : chain->vars.create (n + 1);
1886 : :
1887 : 15460 : if (chain->type == CT_COMBINATION)
1888 : 16 : ref = gimple_assign_lhs (root->stmt);
1889 : : else
1890 : 15444 : ref = DR_REF (root->ref);
1891 : :
1892 : 45148 : for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1893 : : {
1894 : 16739 : var = predcom_tmp_var (ref, i, tmp_vars);
1895 : 16739 : chain->vars.quick_push (var);
1896 : : }
1897 : 15460 : if (reuse_first)
1898 : 9587 : chain->vars.quick_push (chain->vars[0]);
1899 : :
1900 : 41786 : FOR_EACH_VEC_ELT (chain->vars, i, var)
1901 : 26326 : chain->vars[i] = make_ssa_name (var);
1902 : :
1903 : 26326 : for (i = 0; i < n; i++)
1904 : : {
1905 : 10866 : var = chain->vars[i];
1906 : 10866 : next = chain->vars[i + 1];
1907 : 10866 : init = get_init_expr (chain, i);
1908 : :
1909 : 10866 : init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1910 : 10866 : if (stmts)
1911 : 10865 : gsi_insert_seq_on_edge_immediate (entry, stmts);
1912 : :
1913 : 10866 : phi = create_phi_node (var, loop->header);
1914 : 10866 : add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1915 : 10866 : add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1916 : : }
1917 : 15460 : }
1918 : :
1919 : : /* For inter-iteration store elimination CHAIN in LOOP, returns true if
1920 : : all stores to be eliminated store loop invariant values into memory.
1921 : : In this case, we can use these invariant values directly after LOOP. */
1922 : :
1923 : : static bool
1924 : 38 : is_inv_store_elimination_chain (class loop *loop, chain_p chain)
1925 : : {
1926 : 38 : if (chain->length == 0 || chain->type != CT_STORE_STORE)
1927 : : return false;
1928 : :
1929 : 38 : gcc_assert (!chain->has_max_use_after);
1930 : :
1931 : : /* If loop iterates for unknown times or fewer times than chain->length,
1932 : : we still need to setup root variable and propagate it with PHI node. */
1933 : 38 : tree niters = number_of_latch_executions (loop);
1934 : 38 : if (TREE_CODE (niters) != INTEGER_CST
1935 : 38 : || wi::leu_p (wi::to_wide (niters), chain->length))
1936 : 11 : return false;
1937 : :
1938 : : /* Check stores in chain for elimination if they only store loop invariant
1939 : : values. */
1940 : 54 : for (unsigned i = 0; i < chain->length; i++)
1941 : : {
1942 : 39 : dref a = get_chain_last_write_at (chain, i);
1943 : 39 : if (a == NULL)
1944 : 6 : continue;
1945 : :
1946 : 33 : gimple *def_stmt, *stmt = a->stmt;
1947 : 33 : if (!gimple_assign_single_p (stmt))
1948 : : return false;
1949 : :
1950 : 33 : tree val = gimple_assign_rhs1 (stmt);
1951 : 33 : if (TREE_CLOBBER_P (val))
1952 : : return false;
1953 : :
1954 : 33 : if (CONSTANT_CLASS_P (val))
1955 : 21 : continue;
1956 : :
1957 : 12 : if (TREE_CODE (val) != SSA_NAME)
1958 : : return false;
1959 : :
1960 : 12 : def_stmt = SSA_NAME_DEF_STMT (val);
1961 : 12 : if (gimple_nop_p (def_stmt))
1962 : 0 : continue;
1963 : :
1964 : 12 : if (flow_bb_inside_loop_p (loop, gimple_bb (def_stmt)))
1965 : : return false;
1966 : : }
1967 : : return true;
1968 : : }
1969 : :
1970 : : /* Creates root variables for store elimination CHAIN in which stores for
1971 : : elimination only store loop invariant values. In this case, we neither
1972 : : need to load root variables before loop nor propagate it with PHI nodes. */
1973 : :
1974 : : static void
1975 : 15 : initialize_root_vars_store_elim_1 (chain_p chain)
1976 : : {
1977 : 15 : tree var;
1978 : 15 : unsigned i, n = chain->length;
1979 : :
1980 : 15 : chain->vars.create (n);
1981 : 15 : chain->vars.safe_grow_cleared (n, true);
1982 : :
1983 : : /* Initialize root value for eliminated stores at each distance. */
1984 : 42 : for (i = 0; i < n; i++)
1985 : : {
1986 : 27 : dref a = get_chain_last_write_at (chain, i);
1987 : 27 : if (a == NULL)
1988 : 6 : continue;
1989 : :
1990 : 21 : var = gimple_assign_rhs1 (a->stmt);
1991 : 21 : chain->vars[a->distance] = var;
1992 : : }
1993 : :
1994 : : /* We don't propagate values with PHI nodes, so manually propagate value
1995 : : to bubble positions. */
1996 : 15 : var = chain->vars[0];
1997 : 27 : for (i = 1; i < n; i++)
1998 : : {
1999 : 12 : if (chain->vars[i] != NULL_TREE)
2000 : : {
2001 : 6 : var = chain->vars[i];
2002 : 6 : continue;
2003 : : }
2004 : 6 : chain->vars[i] = var;
2005 : : }
2006 : :
2007 : : /* Revert the vector. */
2008 : 22 : for (i = 0; i < n / 2; i++)
2009 : 7 : std::swap (chain->vars[i], chain->vars[n - i - 1]);
2010 : 15 : }
2011 : :
2012 : : /* Creates root variables for store elimination CHAIN in which stores for
2013 : : elimination store loop variant values. In this case, we may need to
2014 : : load root variables before LOOP and propagate it with PHI nodes. Uids
2015 : : of the newly created root variables are marked in TMP_VARS. */
2016 : :
2017 : : static void
2018 : 23 : initialize_root_vars_store_elim_2 (class loop *loop,
2019 : : chain_p chain, bitmap tmp_vars)
2020 : : {
2021 : 23 : unsigned i, n = chain->length;
2022 : 23 : tree ref, init, var, next, val, phi_result;
2023 : 23 : gimple *stmt;
2024 : 23 : gimple_seq stmts;
2025 : :
2026 : 23 : chain->vars.create (n);
2027 : :
2028 : 23 : ref = DR_REF (get_chain_root (chain)->ref);
2029 : 62 : for (i = 0; i < n; i++)
2030 : : {
2031 : 39 : var = predcom_tmp_var (ref, i, tmp_vars);
2032 : 39 : chain->vars.quick_push (var);
2033 : : }
2034 : :
2035 : 62 : FOR_EACH_VEC_ELT (chain->vars, i, var)
2036 : 39 : chain->vars[i] = make_ssa_name (var);
2037 : :
2038 : : /* Root values are either rhs operand of stores to be eliminated, or
2039 : : loaded from memory before loop. */
2040 : 23 : auto_vec<tree> vtemps;
2041 : 23 : vtemps.safe_grow_cleared (n, true);
2042 : 62 : for (i = 0; i < n; i++)
2043 : : {
2044 : 39 : init = get_init_expr (chain, i);
2045 : 39 : if (init == NULL_TREE)
2046 : : {
2047 : : /* Root value is rhs operand of the store to be eliminated if
2048 : : it isn't loaded from memory before loop. */
2049 : 29 : dref a = get_chain_last_write_at (chain, i);
2050 : 29 : val = gimple_assign_rhs1 (a->stmt);
2051 : 29 : if (TREE_CLOBBER_P (val))
2052 : : {
2053 : 0 : val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (var));
2054 : 0 : gimple_assign_set_rhs1 (a->stmt, val);
2055 : : }
2056 : :
2057 : 29 : vtemps[n - i - 1] = val;
2058 : : }
2059 : : else
2060 : : {
2061 : 10 : edge latch = loop_latch_edge (loop);
2062 : 10 : edge entry = loop_preheader_edge (loop);
2063 : :
2064 : : /* Root value is loaded from memory before loop, we also need
2065 : : to add PHI nodes to propagate the value across iterations. */
2066 : 10 : init = force_gimple_operand (init, &stmts, true, NULL_TREE);
2067 : 10 : if (stmts)
2068 : 10 : gsi_insert_seq_on_edge_immediate (entry, stmts);
2069 : :
2070 : 10 : next = chain->vars[n - i];
2071 : 10 : phi_result = copy_ssa_name (next);
2072 : 10 : gphi *phi = create_phi_node (phi_result, loop->header);
2073 : 10 : add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
2074 : 10 : add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
2075 : 10 : vtemps[n - i - 1] = phi_result;
2076 : : }
2077 : : }
2078 : :
2079 : : /* Find the insertion position. */
2080 : 23 : dref last = get_chain_root (chain);
2081 : 77 : for (i = 0; i < chain->refs.length (); i++)
2082 : : {
2083 : 54 : if (chain->refs[i]->pos > last->pos)
2084 : 6 : last = chain->refs[i];
2085 : : }
2086 : :
2087 : 23 : gimple_stmt_iterator gsi = gsi_for_stmt (last->stmt);
2088 : :
2089 : : /* Insert statements copying root value to root variable. */
2090 : 85 : for (i = 0; i < n; i++)
2091 : : {
2092 : 39 : var = chain->vars[i];
2093 : 39 : val = vtemps[i];
2094 : 39 : stmt = gimple_build_assign (var, val);
2095 : 39 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
2096 : : }
2097 : 23 : }
2098 : :
2099 : : /* Generates stores for CHAIN's eliminated stores in LOOP's last
2100 : : (CHAIN->length - 1) iterations. */
2101 : :
2102 : : static void
2103 : 38 : finalize_eliminated_stores (class loop *loop, chain_p chain)
2104 : : {
2105 : 38 : unsigned i, n = chain->length;
2106 : :
2107 : 104 : for (i = 0; i < n; i++)
2108 : : {
2109 : 66 : tree var = chain->vars[i];
2110 : 66 : tree fini = chain->finis[n - i - 1];
2111 : 66 : gimple *stmt = gimple_build_assign (fini, var);
2112 : :
2113 : 66 : gimple_seq_add_stmt_without_update (&chain->fini_seq, stmt);
2114 : : }
2115 : :
2116 : 38 : if (chain->fini_seq)
2117 : : {
2118 : 38 : gsi_insert_seq_on_edge_immediate (single_exit (loop), chain->fini_seq);
2119 : 38 : chain->fini_seq = NULL;
2120 : : }
2121 : 38 : }
2122 : :
2123 : : /* Initializes a variable for load motion for ROOT and prepares phi nodes and
2124 : : initialization on entry to LOOP if necessary. The ssa name for the variable
2125 : : is stored in VARS. If WRITTEN is true, also a phi node to copy its value
2126 : : around the loop is created. Uid of the newly created temporary variable
2127 : : is marked in TMP_VARS. INITS is the list containing the (single)
2128 : : initializer. */
2129 : :
2130 : : static void
2131 : 1762 : initialize_root_vars_lm (class loop *loop, dref root, bool written,
2132 : : vec<tree> *vars, const vec<tree> &inits,
2133 : : bitmap tmp_vars)
2134 : : {
2135 : 1762 : unsigned i;
2136 : 1762 : tree ref = DR_REF (root->ref), init, var, next;
2137 : 1762 : gimple_seq stmts;
2138 : 1762 : gphi *phi;
2139 : 1762 : edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
2140 : :
2141 : : /* Find the initializer for the variable, and check that it cannot
2142 : : trap. */
2143 : 1762 : init = inits[0];
2144 : :
2145 : 2118 : vars->create (written ? 2 : 1);
2146 : 1762 : var = predcom_tmp_var (ref, 0, tmp_vars);
2147 : 1762 : vars->quick_push (var);
2148 : 1762 : if (written)
2149 : 1406 : vars->quick_push ((*vars)[0]);
2150 : :
2151 : 4930 : FOR_EACH_VEC_ELT (*vars, i, var)
2152 : 3168 : (*vars)[i] = make_ssa_name (var);
2153 : :
2154 : 1762 : var = (*vars)[0];
2155 : :
2156 : 1762 : init = force_gimple_operand (init, &stmts, written, NULL_TREE);
2157 : 1762 : if (stmts)
2158 : 1406 : gsi_insert_seq_on_edge_immediate (entry, stmts);
2159 : :
2160 : 1762 : if (written)
2161 : : {
2162 : 1406 : next = (*vars)[1];
2163 : 1406 : phi = create_phi_node (var, loop->header);
2164 : 1406 : add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
2165 : 1406 : add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
2166 : : }
2167 : : else
2168 : : {
2169 : 356 : gassign *init_stmt = gimple_build_assign (var, init);
2170 : 356 : gsi_insert_on_edge_immediate (entry, init_stmt);
2171 : : }
2172 : 1762 : }
2173 : :
2174 : :
2175 : : /* Execute load motion for references in chain CHAIN. Uids of the newly
2176 : : created temporary variables are marked in TMP_VARS. */
2177 : :
2178 : : static void
2179 : 10735 : execute_load_motion (class loop *loop, chain_p chain, bitmap tmp_vars)
2180 : : {
2181 : 10735 : auto_vec<tree> vars;
2182 : 10735 : dref a;
2183 : 10735 : unsigned n_writes = 0, ridx, i;
2184 : 10735 : tree var;
2185 : :
2186 : 10735 : gcc_assert (chain->type == CT_INVARIANT);
2187 : 10735 : gcc_assert (!chain->combined);
2188 : 23227 : FOR_EACH_VEC_ELT (chain->refs, i, a)
2189 : 12492 : if (DR_IS_WRITE (a->ref))
2190 : 10652 : n_writes++;
2191 : :
2192 : : /* If there are no reads in the loop, there is nothing to do. */
2193 : 21470 : if (n_writes == chain->refs.length ())
2194 : 8973 : return;
2195 : :
2196 : 1762 : initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
2197 : : &vars, chain->inits, tmp_vars);
2198 : :
2199 : 1762 : ridx = 0;
2200 : 6850 : FOR_EACH_VEC_ELT (chain->refs, i, a)
2201 : : {
2202 : 3326 : bool is_read = DR_IS_READ (a->ref);
2203 : :
2204 : 3326 : if (DR_IS_WRITE (a->ref))
2205 : : {
2206 : 1486 : n_writes--;
2207 : 1486 : if (n_writes)
2208 : : {
2209 : 80 : var = vars[0];
2210 : 80 : var = make_ssa_name (SSA_NAME_VAR (var));
2211 : 80 : vars[0] = var;
2212 : : }
2213 : : else
2214 : : ridx = 1;
2215 : : }
2216 : :
2217 : 3326 : replace_ref_with (a->stmt, vars[ridx],
2218 : 3326 : !is_read, !is_read);
2219 : : }
2220 : 10735 : }
2221 : :
2222 : : /* Returns the single statement in that NAME is used, excepting
2223 : : the looparound phi nodes contained in one of the chains. If there is no
2224 : : such statement, or more statements, NULL is returned. */
2225 : :
2226 : : gimple *
2227 : 42374 : pcom_worker::single_nonlooparound_use (tree name)
2228 : : {
2229 : 42374 : use_operand_p use;
2230 : 42374 : imm_use_iterator it;
2231 : 42374 : gimple *stmt, *ret = NULL;
2232 : :
2233 : 85329 : FOR_EACH_IMM_USE_FAST (use, it, name)
2234 : : {
2235 : 43491 : stmt = USE_STMT (use);
2236 : :
2237 : 43491 : if (gimple_code (stmt) == GIMPLE_PHI)
2238 : : {
2239 : : /* Ignore uses in looparound phi nodes. Uses in other phi nodes
2240 : : could not be processed anyway, so just fail for them. */
2241 : 192 : if (bitmap_bit_p (m_looparound_phis,
2242 : 96 : SSA_NAME_VERSION (PHI_RESULT (stmt))))
2243 : 0 : continue;
2244 : :
2245 : : return NULL;
2246 : : }
2247 : 43395 : else if (is_gimple_debug (stmt))
2248 : 723 : continue;
2249 : 42672 : else if (ret != NULL)
2250 : : return NULL;
2251 : : else
2252 : : ret = stmt;
2253 : : }
2254 : :
2255 : : return ret;
2256 : : }
2257 : :
2258 : : /* Remove statement STMT, as well as the chain of assignments in that it is
2259 : : used. */
2260 : :
2261 : : void
2262 : 155 : pcom_worker::remove_stmt (gimple *stmt)
2263 : : {
2264 : 155 : tree name;
2265 : 155 : gimple *next;
2266 : 155 : gimple_stmt_iterator psi;
2267 : :
2268 : 155 : if (gimple_code (stmt) == GIMPLE_PHI)
2269 : : {
2270 : 0 : name = PHI_RESULT (stmt);
2271 : 0 : next = single_nonlooparound_use (name);
2272 : 0 : reset_debug_uses (stmt);
2273 : 0 : psi = gsi_for_stmt (stmt);
2274 : 0 : remove_phi_node (&psi, true);
2275 : :
2276 : 0 : if (!next
2277 : 0 : || !gimple_assign_ssa_name_copy_p (next)
2278 : 0 : || gimple_assign_rhs1 (next) != name)
2279 : 0 : return;
2280 : :
2281 : : stmt = next;
2282 : : }
2283 : :
2284 : 195 : while (1)
2285 : : {
2286 : 175 : gimple_stmt_iterator bsi;
2287 : :
2288 : 175 : bsi = gsi_for_stmt (stmt);
2289 : :
2290 : 175 : name = gimple_assign_lhs (stmt);
2291 : 175 : if (TREE_CODE (name) == SSA_NAME)
2292 : : {
2293 : 108 : next = single_nonlooparound_use (name);
2294 : 108 : reset_debug_uses (stmt);
2295 : : }
2296 : : else
2297 : : {
2298 : : /* This is a store to be eliminated. */
2299 : 134 : gcc_assert (gimple_vdef (stmt) != NULL);
2300 : : next = NULL;
2301 : : }
2302 : :
2303 : 175 : unlink_stmt_vdef (stmt);
2304 : 175 : gsi_remove (&bsi, true);
2305 : 175 : release_defs (stmt);
2306 : :
2307 : 175 : if (!next
2308 : 62 : || !gimple_assign_ssa_name_copy_p (next)
2309 : 195 : || gimple_assign_rhs1 (next) != name)
2310 : 155 : return;
2311 : :
2312 : 20 : stmt = next;
2313 : 20 : }
2314 : : }
2315 : :
2316 : : /* Perform the predictive commoning optimization for a chain CHAIN.
2317 : : Uids of the newly created temporary variables are marked in TMP_VARS.*/
2318 : :
2319 : : void
2320 : 15572 : pcom_worker::execute_pred_commoning_chain (chain_p chain,
2321 : : bitmap tmp_vars)
2322 : : {
2323 : 15572 : unsigned i;
2324 : 15572 : dref a;
2325 : 15572 : tree var;
2326 : 15572 : bool in_lhs;
2327 : :
2328 : 15572 : if (chain->combined)
2329 : : {
2330 : : /* For combined chains, just remove the statements that are used to
2331 : : compute the values of the expression (except for the root one).
2332 : : We delay this until after all chains are processed. */
2333 : : }
2334 : 15514 : else if (chain->type == CT_STORE_STORE)
2335 : : {
2336 : 54 : if (chain->length > 0)
2337 : : {
2338 : 38 : if (chain->inv_store_elimination)
2339 : : {
2340 : : /* If dead stores in this chain only store loop invariant
2341 : : values, we can simply record the invariant value and use
2342 : : it directly after loop. */
2343 : 15 : initialize_root_vars_store_elim_1 (chain);
2344 : : }
2345 : : else
2346 : : {
2347 : : /* If dead stores in this chain store loop variant values,
2348 : : we need to set up the variables by loading from memory
2349 : : before loop and propagating it with PHI nodes. */
2350 : 23 : initialize_root_vars_store_elim_2 (m_loop, chain, tmp_vars);
2351 : : }
2352 : :
2353 : : /* For inter-iteration store elimination chain, stores at each
2354 : : distance in loop's last (chain->length - 1) iterations can't
2355 : : be eliminated, because there is no following killing store.
2356 : : We need to generate these stores after loop. */
2357 : 38 : finalize_eliminated_stores (m_loop, chain);
2358 : : }
2359 : :
2360 : 54 : bool last_store_p = true;
2361 : 234 : for (i = chain->refs.length (); i > 0; i--)
2362 : : {
2363 : 126 : a = chain->refs[i - 1];
2364 : : /* Preserve the last store of the chain. Eliminate other stores
2365 : : which are killed by the last one. */
2366 : 126 : if (DR_IS_WRITE (a->ref))
2367 : : {
2368 : 121 : if (last_store_p)
2369 : : last_store_p = false;
2370 : : else
2371 : 67 : remove_stmt (a->stmt);
2372 : :
2373 : 121 : continue;
2374 : : }
2375 : :
2376 : : /* Any load in Store-Store chain must be dominated by a previous
2377 : : store, we replace the load reference with rhs of the store. */
2378 : 5 : dref b = get_chain_last_write_before_load (chain, i - 1);
2379 : 5 : gcc_assert (b != NULL);
2380 : 5 : var = gimple_assign_rhs1 (b->stmt);
2381 : 5 : replace_ref_with (a->stmt, var, false, false);
2382 : : }
2383 : : }
2384 : : else
2385 : : {
2386 : : /* For non-combined chains, set up the variables that hold its value. */
2387 : 15460 : initialize_root_vars (m_loop, chain, tmp_vars);
2388 : 15460 : a = get_chain_root (chain);
2389 : 15460 : in_lhs = (chain->type == CT_STORE_LOAD
2390 : 15460 : || chain->type == CT_COMBINATION);
2391 : 15460 : replace_ref_with (a->stmt, chain->vars[chain->length], true, in_lhs);
2392 : :
2393 : : /* Replace the uses of the original references by these variables. */
2394 : 46678 : for (i = 1; chain->refs.iterate (i, &a); i++)
2395 : : {
2396 : 15758 : var = chain->vars[chain->length - a->distance];
2397 : 15758 : replace_ref_with (a->stmt, var, false, false);
2398 : : }
2399 : : }
2400 : 15572 : }
2401 : :
2402 : : /* Determines the unroll factor necessary to remove as many temporary variable
2403 : : copies as possible. CHAINS is the list of chains that will be
2404 : : optimized. */
2405 : :
2406 : : static unsigned
2407 : 3073 : determine_unroll_factor (const vec<chain_p> &chains)
2408 : : {
2409 : 3073 : chain_p chain;
2410 : 3073 : unsigned factor = 1, af, nfactor, i;
2411 : 3073 : unsigned max = param_max_unroll_times;
2412 : :
2413 : 6990 : FOR_EACH_VEC_ELT (chains, i, chain)
2414 : : {
2415 : 3941 : if (chain->type == CT_INVARIANT)
2416 : 1712 : continue;
2417 : : /* For now we can't handle unrolling when eliminating stores. */
2418 : 2229 : else if (chain->type == CT_STORE_STORE)
2419 : : return 1;
2420 : :
2421 : 2205 : if (chain->combined)
2422 : : {
2423 : : /* For combined chains, we can't handle unrolling if we replace
2424 : : looparound PHIs. */
2425 : : dref a;
2426 : : unsigned j;
2427 : 146 : for (j = 1; chain->refs.iterate (j, &a); j++)
2428 : 88 : if (gimple_code (a->stmt) == GIMPLE_PHI)
2429 : 24 : return 1;
2430 : 58 : continue;
2431 : 58 : }
2432 : :
2433 : : /* The best unroll factor for this chain is equal to the number of
2434 : : temporary variables that we create for it. */
2435 : 2147 : af = chain->length;
2436 : 2147 : if (chain->has_max_use_after)
2437 : 1227 : af++;
2438 : :
2439 : 2147 : nfactor = factor * af / gcd (factor, af);
2440 : 2147 : if (nfactor <= max)
2441 : 3917 : factor = nfactor;
2442 : : }
2443 : :
2444 : : return factor;
2445 : : }
2446 : :
2447 : : /* Perform the predictive commoning optimization for chains.
2448 : : Uids of the newly created temporary variables are marked in TMP_VARS. */
2449 : :
2450 : : void
2451 : 15769 : pcom_worker::execute_pred_commoning (bitmap tmp_vars)
2452 : : {
2453 : 15769 : chain_p chain;
2454 : 15769 : unsigned i;
2455 : :
2456 : 42076 : FOR_EACH_VEC_ELT (m_chains, i, chain)
2457 : : {
2458 : 26307 : if (chain->type == CT_INVARIANT)
2459 : 10735 : execute_load_motion (m_loop, chain, tmp_vars);
2460 : : else
2461 : 15572 : execute_pred_commoning_chain (chain, tmp_vars);
2462 : : }
2463 : :
2464 : 42076 : FOR_EACH_VEC_ELT (m_chains, i, chain)
2465 : : {
2466 : 26307 : if (chain->type == CT_INVARIANT)
2467 : : ;
2468 : 15572 : else if (chain->combined)
2469 : : {
2470 : : /* For combined chains, just remove the statements that are used to
2471 : : compute the values of the expression (except for the root one). */
2472 : : dref a;
2473 : : unsigned j;
2474 : 26453 : for (j = 1; chain->refs.iterate (j, &a); j++)
2475 : 88 : remove_stmt (a->stmt);
2476 : : }
2477 : : }
2478 : 15769 : }
2479 : :
2480 : : /* For each reference in CHAINS, if its defining statement is
2481 : : phi node, record the ssa name that is defined by it. */
2482 : :
2483 : : static void
2484 : 624 : replace_phis_by_defined_names (vec<chain_p> &chains)
2485 : : {
2486 : 624 : chain_p chain;
2487 : 624 : dref a;
2488 : 624 : unsigned i, j;
2489 : :
2490 : 1964 : FOR_EACH_VEC_ELT (chains, i, chain)
2491 : 2739 : FOR_EACH_VEC_ELT (chain->refs, j, a)
2492 : : {
2493 : 1399 : if (gimple_code (a->stmt) == GIMPLE_PHI)
2494 : : {
2495 : 1 : a->name_defined_by_phi = PHI_RESULT (a->stmt);
2496 : 1 : a->stmt = NULL;
2497 : : }
2498 : : }
2499 : 624 : }
2500 : :
2501 : : /* For each reference in CHAINS, if name_defined_by_phi is not
2502 : : NULL, use it to set the stmt field. */
2503 : :
2504 : : static void
2505 : 624 : replace_names_by_phis (vec<chain_p> chains)
2506 : : {
2507 : 624 : chain_p chain;
2508 : 624 : dref a;
2509 : 624 : unsigned i, j;
2510 : :
2511 : 1964 : FOR_EACH_VEC_ELT (chains, i, chain)
2512 : 2739 : FOR_EACH_VEC_ELT (chain->refs, j, a)
2513 : 1399 : if (a->stmt == NULL)
2514 : : {
2515 : 1 : a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
2516 : 1 : gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
2517 : 1 : a->name_defined_by_phi = NULL_TREE;
2518 : : }
2519 : 624 : }
2520 : :
2521 : : /* Wrapper over execute_pred_commoning, to pass it as a callback
2522 : : to tree_transform_and_unroll_loop. */
2523 : :
2524 : : struct epcc_data
2525 : : {
2526 : : vec<chain_p> chains;
2527 : : bitmap tmp_vars;
2528 : : pcom_worker *worker;
2529 : : };
2530 : :
2531 : : static void
2532 : 624 : execute_pred_commoning_cbck (class loop *loop ATTRIBUTE_UNUSED, void *data)
2533 : : {
2534 : 624 : struct epcc_data *const dta = (struct epcc_data *) data;
2535 : 624 : pcom_worker *worker = dta->worker;
2536 : :
2537 : : /* Restore phi nodes that were replaced by ssa names before
2538 : : tree_transform_and_unroll_loop (see detailed description in
2539 : : tree_predictive_commoning_loop). */
2540 : 624 : replace_names_by_phis (dta->chains);
2541 : 624 : worker->execute_pred_commoning (dta->tmp_vars);
2542 : 624 : }
2543 : :
2544 : : /* Base NAME and all the names in the chain of phi nodes that use it
2545 : : on variable VAR. The phi nodes are recognized by being in the copies of
2546 : : the header of the LOOP. */
2547 : :
2548 : : static void
2549 : 669 : base_names_in_chain_on (class loop *loop, tree name, tree var)
2550 : : {
2551 : 669 : gimple *stmt, *phi;
2552 : 669 : imm_use_iterator iter;
2553 : :
2554 : 669 : replace_ssa_name_symbol (name, var);
2555 : :
2556 : 2135 : while (1)
2557 : : {
2558 : 1402 : phi = NULL;
2559 : 2078 : FOR_EACH_IMM_USE_STMT (stmt, iter, name)
2560 : : {
2561 : 1409 : if (gimple_code (stmt) == GIMPLE_PHI
2562 : 1409 : && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
2563 : : {
2564 : : phi = stmt;
2565 : : break;
2566 : : }
2567 : 1402 : }
2568 : 1402 : if (!phi)
2569 : 669 : return;
2570 : :
2571 : 733 : name = PHI_RESULT (phi);
2572 : 733 : replace_ssa_name_symbol (name, var);
2573 : 733 : }
2574 : : }
2575 : :
2576 : : /* Given an unrolled LOOP after predictive commoning, remove the
2577 : : register copies arising from phi nodes by changing the base
2578 : : variables of SSA names. TMP_VARS is the set of the temporary variables
2579 : : for those we want to perform this. */
2580 : :
2581 : : static void
2582 : 624 : eliminate_temp_copies (class loop *loop, bitmap tmp_vars)
2583 : : {
2584 : 624 : edge e;
2585 : 624 : gphi *phi;
2586 : 624 : gimple *stmt;
2587 : 624 : tree name, use, var;
2588 : 624 : gphi_iterator psi;
2589 : :
2590 : 624 : e = loop_latch_edge (loop);
2591 : 3215 : for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
2592 : : {
2593 : 2591 : phi = psi.phi ();
2594 : 2591 : name = PHI_RESULT (phi);
2595 : 2591 : var = SSA_NAME_VAR (name);
2596 : 1684 : if (!var || !bitmap_bit_p (tmp_vars, DECL_UID (var)))
2597 : 1922 : continue;
2598 : 669 : use = PHI_ARG_DEF_FROM_EDGE (phi, e);
2599 : 669 : gcc_assert (TREE_CODE (use) == SSA_NAME);
2600 : :
2601 : : /* Base all the ssa names in the ud and du chain of NAME on VAR. */
2602 : 669 : stmt = SSA_NAME_DEF_STMT (use);
2603 : 701 : while (gimple_code (stmt) == GIMPLE_PHI
2604 : : /* In case we could not unroll the loop enough to eliminate
2605 : : all copies, we may reach the loop header before the defining
2606 : : statement (in that case, some register copies will be present
2607 : : in loop latch in the final code, corresponding to the newly
2608 : : created looparound phi nodes). */
2609 : 701 : && gimple_bb (stmt) != loop->header)
2610 : : {
2611 : 32 : gcc_assert (single_pred_p (gimple_bb (stmt)));
2612 : 32 : use = PHI_ARG_DEF (stmt, 0);
2613 : 32 : stmt = SSA_NAME_DEF_STMT (use);
2614 : : }
2615 : :
2616 : 669 : base_names_in_chain_on (loop, use, var);
2617 : : }
2618 : 624 : }
2619 : :
2620 : : /* Returns true if CHAIN is suitable to be combined. */
2621 : :
2622 : : static bool
2623 : 92085 : chain_can_be_combined_p (chain_p chain)
2624 : : {
2625 : 92085 : return (!chain->combined
2626 : 91955 : && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
2627 : : }
2628 : :
2629 : : /* Returns the modify statement that uses NAME. Skips over assignment
2630 : : statements, NAME is replaced with the actual name used in the returned
2631 : : statement. */
2632 : :
2633 : : gimple *
2634 : 41413 : pcom_worker::find_use_stmt (tree *name)
2635 : : {
2636 : 42266 : gimple *stmt;
2637 : 42266 : tree rhs, lhs;
2638 : :
2639 : : /* Skip over assignments. */
2640 : 43119 : while (1)
2641 : : {
2642 : 42266 : stmt = single_nonlooparound_use (*name);
2643 : 42266 : if (!stmt)
2644 : : return NULL;
2645 : :
2646 : 41730 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
2647 : : return NULL;
2648 : :
2649 : 40404 : lhs = gimple_assign_lhs (stmt);
2650 : 40404 : if (TREE_CODE (lhs) != SSA_NAME)
2651 : : return NULL;
2652 : :
2653 : 40382 : if (gimple_assign_copy_p (stmt))
2654 : : {
2655 : 853 : rhs = gimple_assign_rhs1 (stmt);
2656 : 853 : if (rhs != *name)
2657 : : return NULL;
2658 : :
2659 : 853 : *name = lhs;
2660 : : }
2661 : 39529 : else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
2662 : : == GIMPLE_BINARY_RHS)
2663 : : return stmt;
2664 : : else
2665 : : return NULL;
2666 : : }
2667 : : }
2668 : :
2669 : : /* Returns true if we may perform reassociation for operation CODE in TYPE. */
2670 : :
2671 : : static bool
2672 : 839 : may_reassociate_p (tree type, enum tree_code code)
2673 : : {
2674 : 444 : if (FLOAT_TYPE_P (type)
2675 : 1073 : && !flag_unsafe_math_optimizations)
2676 : : return false;
2677 : :
2678 : 517 : return (commutative_tree_code (code)
2679 : 517 : && associative_tree_code (code));
2680 : : }
2681 : :
2682 : : /* If the operation used in STMT is associative and commutative, go through the
2683 : : tree of the same operations and returns its root. Distance to the root
2684 : : is stored in DISTANCE. */
2685 : :
2686 : : gimple *
2687 : 839 : pcom_worker::find_associative_operation_root (gimple *stmt, unsigned *distance)
2688 : : {
2689 : 839 : tree lhs;
2690 : 839 : gimple *next;
2691 : 839 : enum tree_code code = gimple_assign_rhs_code (stmt);
2692 : 839 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2693 : 839 : unsigned dist = 0;
2694 : :
2695 : 839 : if (!may_reassociate_p (type, code))
2696 : : return NULL;
2697 : :
2698 : 2551 : while (1)
2699 : : {
2700 : 1495 : lhs = gimple_assign_lhs (stmt);
2701 : 1495 : gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2702 : :
2703 : 1495 : next = find_use_stmt (&lhs);
2704 : 1495 : if (!next
2705 : 1495 : || gimple_assign_rhs_code (next) != code)
2706 : : break;
2707 : :
2708 : 1056 : stmt = next;
2709 : 1056 : dist++;
2710 : : }
2711 : :
2712 : 439 : if (distance)
2713 : 128 : *distance = dist;
2714 : : return stmt;
2715 : : }
2716 : :
2717 : : /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2718 : : is no such statement, returns NULL_TREE. In case the operation used on
2719 : : NAME1 and NAME2 is associative and commutative, returns the root of the
2720 : : tree formed by this operation instead of the statement that uses NAME1 or
2721 : : NAME2. */
2722 : :
2723 : : gimple *
2724 : 38600 : pcom_worker::find_common_use_stmt (tree *name1, tree *name2)
2725 : : {
2726 : 38600 : gimple *stmt1, *stmt2;
2727 : :
2728 : 38600 : stmt1 = find_use_stmt (name1);
2729 : 38600 : if (!stmt1)
2730 : : return NULL;
2731 : :
2732 : 682 : stmt2 = find_use_stmt (name2);
2733 : 682 : if (!stmt2)
2734 : : return NULL;
2735 : :
2736 : 586 : if (stmt1 == stmt2)
2737 : : return stmt1;
2738 : :
2739 : 555 : stmt1 = find_associative_operation_root (stmt1, NULL);
2740 : 555 : if (!stmt1)
2741 : : return NULL;
2742 : 156 : stmt2 = find_associative_operation_root (stmt2, NULL);
2743 : 156 : if (!stmt2)
2744 : : return NULL;
2745 : :
2746 : 155 : return (stmt1 == stmt2 ? stmt1 : NULL);
2747 : : }
2748 : :
2749 : : /* Checks whether R1 and R2 are combined together using CODE, with the result
2750 : : in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2751 : : if it is true. If CODE is ERROR_MARK, set these values instead. */
2752 : :
2753 : : bool
2754 : 38600 : pcom_worker::combinable_refs_p (dref r1, dref r2,
2755 : : enum tree_code *code, bool *swap, tree *rslt_type)
2756 : : {
2757 : 38600 : enum tree_code acode;
2758 : 38600 : bool aswap;
2759 : 38600 : tree atype;
2760 : 38600 : tree name1, name2;
2761 : 38600 : gimple *stmt;
2762 : :
2763 : 38600 : name1 = name_for_ref (r1);
2764 : 38600 : name2 = name_for_ref (r2);
2765 : 38600 : gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2766 : :
2767 : 38600 : stmt = find_common_use_stmt (&name1, &name2);
2768 : :
2769 : 38600 : if (!stmt
2770 : : /* A simple post-dominance check - make sure the combination
2771 : : is executed under the same condition as the references. */
2772 : 38600 : || (gimple_bb (stmt) != gimple_bb (r1->stmt)
2773 : 20 : && gimple_bb (stmt) != gimple_bb (r2->stmt)))
2774 : : return false;
2775 : :
2776 : 79 : acode = gimple_assign_rhs_code (stmt);
2777 : 79 : aswap = (!commutative_tree_code (acode)
2778 : 79 : && gimple_assign_rhs1 (stmt) != name1);
2779 : 79 : atype = TREE_TYPE (gimple_assign_lhs (stmt));
2780 : :
2781 : 79 : if (*code == ERROR_MARK)
2782 : : {
2783 : 35 : *code = acode;
2784 : 35 : *swap = aswap;
2785 : 35 : *rslt_type = atype;
2786 : 35 : return true;
2787 : : }
2788 : :
2789 : 44 : return (*code == acode
2790 : 44 : && *swap == aswap
2791 : 88 : && *rslt_type == atype);
2792 : : }
2793 : :
2794 : : /* Remove OP from the operation on rhs of STMT, and replace STMT with
2795 : : an assignment of the remaining operand. */
2796 : :
2797 : : static void
2798 : 128 : remove_name_from_operation (gimple *stmt, tree op)
2799 : : {
2800 : 128 : tree other_op;
2801 : 128 : gimple_stmt_iterator si;
2802 : :
2803 : 128 : gcc_assert (is_gimple_assign (stmt));
2804 : :
2805 : 128 : if (gimple_assign_rhs1 (stmt) == op)
2806 : 58 : other_op = gimple_assign_rhs2 (stmt);
2807 : : else
2808 : : other_op = gimple_assign_rhs1 (stmt);
2809 : :
2810 : 128 : si = gsi_for_stmt (stmt);
2811 : 128 : gimple_assign_set_rhs_from_tree (&si, other_op);
2812 : :
2813 : : /* We should not have reallocated STMT. */
2814 : 128 : gcc_assert (gsi_stmt (si) == stmt);
2815 : :
2816 : 128 : update_stmt (stmt);
2817 : 128 : }
2818 : :
2819 : : /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2820 : : are combined in a single statement, and returns this statement. */
2821 : :
2822 : : gimple *
2823 : 64 : pcom_worker::reassociate_to_the_same_stmt (tree name1, tree name2)
2824 : : {
2825 : 64 : gimple *stmt1, *stmt2, *root1, *root2, *s1, *s2;
2826 : 64 : gassign *new_stmt, *tmp_stmt;
2827 : 64 : tree new_name, tmp_name, var, r1, r2;
2828 : 64 : unsigned dist1, dist2;
2829 : 64 : enum tree_code code;
2830 : 64 : tree type = TREE_TYPE (name1);
2831 : 64 : gimple_stmt_iterator bsi;
2832 : :
2833 : 64 : stmt1 = find_use_stmt (&name1);
2834 : 64 : stmt2 = find_use_stmt (&name2);
2835 : 64 : root1 = find_associative_operation_root (stmt1, &dist1);
2836 : 64 : root2 = find_associative_operation_root (stmt2, &dist2);
2837 : 64 : code = gimple_assign_rhs_code (stmt1);
2838 : :
2839 : 64 : gcc_assert (root1 && root2 && root1 == root2
2840 : : && code == gimple_assign_rhs_code (stmt2));
2841 : :
2842 : : /* Find the root of the nearest expression in that both NAME1 and NAME2
2843 : : are used. */
2844 : 64 : r1 = name1;
2845 : 64 : s1 = stmt1;
2846 : 64 : r2 = name2;
2847 : 64 : s2 = stmt2;
2848 : :
2849 : 230 : while (dist1 > dist2)
2850 : : {
2851 : 166 : s1 = find_use_stmt (&r1);
2852 : 166 : r1 = gimple_assign_lhs (s1);
2853 : 166 : dist1--;
2854 : : }
2855 : 124 : while (dist2 > dist1)
2856 : : {
2857 : 60 : s2 = find_use_stmt (&r2);
2858 : 60 : r2 = gimple_assign_lhs (s2);
2859 : 60 : dist2--;
2860 : : }
2861 : :
2862 : 132 : while (s1 != s2)
2863 : : {
2864 : 68 : s1 = find_use_stmt (&r1);
2865 : 68 : r1 = gimple_assign_lhs (s1);
2866 : 68 : s2 = find_use_stmt (&r2);
2867 : 68 : r2 = gimple_assign_lhs (s2);
2868 : : }
2869 : :
2870 : : /* Remove NAME1 and NAME2 from the statements in that they are used
2871 : : currently. */
2872 : 64 : remove_name_from_operation (stmt1, name1);
2873 : 64 : remove_name_from_operation (stmt2, name2);
2874 : :
2875 : : /* Insert the new statement combining NAME1 and NAME2 before S1, and
2876 : : combine it with the rhs of S1. */
2877 : 64 : var = create_tmp_reg (type, "predreastmp");
2878 : 64 : new_name = make_ssa_name (var);
2879 : 64 : new_stmt = gimple_build_assign (new_name, code, name1, name2);
2880 : :
2881 : 64 : var = create_tmp_reg (type, "predreastmp");
2882 : 64 : tmp_name = make_ssa_name (var);
2883 : :
2884 : : /* Rhs of S1 may now be either a binary expression with operation
2885 : : CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2886 : : so that name1 or name2 was removed from it). */
2887 : 64 : tmp_stmt = gimple_build_assign (tmp_name, gimple_assign_rhs_code (s1),
2888 : : gimple_assign_rhs1 (s1),
2889 : : gimple_assign_rhs2 (s1));
2890 : :
2891 : 64 : bsi = gsi_for_stmt (s1);
2892 : 64 : gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2893 : 64 : s1 = gsi_stmt (bsi);
2894 : 64 : update_stmt (s1);
2895 : :
2896 : 64 : gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2897 : 64 : gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2898 : :
2899 : 64 : return new_stmt;
2900 : : }
2901 : :
2902 : : /* Returns the statement that combines references R1 and R2. In case R1
2903 : : and R2 are not used in the same statement, but they are used with an
2904 : : associative and commutative operation in the same expression, reassociate
2905 : : the expression so that they are used in the same statement. */
2906 : :
2907 : : gimple *
2908 : 73 : pcom_worker::stmt_combining_refs (dref r1, dref r2)
2909 : : {
2910 : 73 : gimple *stmt1, *stmt2;
2911 : 73 : tree name1 = name_for_ref (r1);
2912 : 73 : tree name2 = name_for_ref (r2);
2913 : :
2914 : 73 : stmt1 = find_use_stmt (&name1);
2915 : 73 : stmt2 = find_use_stmt (&name2);
2916 : 73 : if (stmt1 == stmt2)
2917 : : return stmt1;
2918 : :
2919 : 64 : return reassociate_to_the_same_stmt (name1, name2);
2920 : : }
2921 : :
2922 : : /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2923 : : description of the new chain is returned, otherwise we return NULL. */
2924 : :
2925 : : chain_p
2926 : 51971 : pcom_worker::combine_chains (chain_p ch1, chain_p ch2)
2927 : : {
2928 : 51971 : dref r1, r2, nw;
2929 : 51971 : enum tree_code op = ERROR_MARK;
2930 : 51971 : bool swap = false;
2931 : 51971 : chain_p new_chain;
2932 : 51971 : unsigned i;
2933 : 51971 : tree rslt_type = NULL_TREE;
2934 : :
2935 : 51971 : if (ch1 == ch2)
2936 : : return NULL;
2937 : 38728 : if (ch1->length != ch2->length)
2938 : : return NULL;
2939 : :
2940 : 116082 : if (ch1->refs.length () != ch2->refs.length ())
2941 : : return NULL;
2942 : :
2943 : 79 : for (i = 0; (ch1->refs.iterate (i, &r1)
2944 : 77229 : && ch2->refs.iterate (i, &r2)); i++)
2945 : : {
2946 : 38600 : if (r1->distance != r2->distance)
2947 : : return NULL;
2948 : :
2949 : 38600 : if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2950 : : return NULL;
2951 : : }
2952 : :
2953 : 29 : if (swap)
2954 : 1 : std::swap (ch1, ch2);
2955 : :
2956 : 29 : new_chain = new struct chain (CT_COMBINATION);
2957 : 29 : new_chain->op = op;
2958 : 29 : new_chain->ch1 = ch1;
2959 : 29 : new_chain->ch2 = ch2;
2960 : 29 : new_chain->rslt_type = rslt_type;
2961 : 29 : new_chain->length = ch1->length;
2962 : :
2963 : 102 : for (i = 0; (ch1->refs.iterate (i, &r1)
2964 : 175 : && ch2->refs.iterate (i, &r2)); i++)
2965 : : {
2966 : 73 : nw = XCNEW (class dref_d);
2967 : 73 : nw->stmt = stmt_combining_refs (r1, r2);
2968 : 73 : nw->distance = r1->distance;
2969 : :
2970 : 73 : new_chain->refs.safe_push (nw);
2971 : : }
2972 : :
2973 : 29 : ch1->combined = true;
2974 : 29 : ch2->combined = true;
2975 : 29 : return new_chain;
2976 : : }
2977 : :
2978 : : /* Recursively update position information of all offspring chains to ROOT
2979 : : chain's position information. */
2980 : :
2981 : : static void
2982 : 29 : update_pos_for_combined_chains (chain_p root)
2983 : : {
2984 : 29 : chain_p ch1 = root->ch1, ch2 = root->ch2;
2985 : 29 : dref ref, ref1, ref2;
2986 : 29 : for (unsigned j = 0; (root->refs.iterate (j, &ref)
2987 : 73 : && ch1->refs.iterate (j, &ref1)
2988 : 175 : && ch2->refs.iterate (j, &ref2)); ++j)
2989 : 73 : ref1->pos = ref2->pos = ref->pos;
2990 : :
2991 : 29 : if (ch1->type == CT_COMBINATION)
2992 : 13 : update_pos_for_combined_chains (ch1);
2993 : 29 : if (ch2->type == CT_COMBINATION)
2994 : : update_pos_for_combined_chains (ch2);
2995 : 29 : }
2996 : :
2997 : : /* Returns true if statement S1 dominates statement S2. */
2998 : :
2999 : : static bool
3000 : 12 : pcom_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
3001 : : {
3002 : 12 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3003 : :
3004 : 12 : if (!bb1 || s1 == s2)
3005 : : return true;
3006 : :
3007 : 12 : if (bb1 == bb2)
3008 : 12 : return gimple_uid (s1) < gimple_uid (s2);
3009 : :
3010 : 0 : return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
3011 : : }
3012 : :
3013 : : /* Try to combine the chains. */
3014 : :
3015 : : void
3016 : 15769 : pcom_worker::try_combine_chains ()
3017 : : {
3018 : 15769 : unsigned i, j;
3019 : 15769 : chain_p ch1, ch2, cch;
3020 : 15769 : auto_vec<chain_p> worklist;
3021 : 15769 : bool combined_p = false;
3022 : :
3023 : 42047 : FOR_EACH_VEC_ELT (m_chains, i, ch1)
3024 : 52556 : if (chain_can_be_combined_p (ch1))
3025 : 13272 : worklist.safe_push (ch1);
3026 : :
3027 : 58140 : while (!worklist.is_empty ())
3028 : : {
3029 : 13301 : ch1 = worklist.pop ();
3030 : 13301 : if (!chain_can_be_combined_p (ch1))
3031 : 29 : continue;
3032 : :
3033 : 94819 : FOR_EACH_VEC_ELT (m_chains, j, ch2)
3034 : : {
3035 : 52506 : if (!chain_can_be_combined_p (ch2))
3036 : 535 : continue;
3037 : :
3038 : 51971 : cch = combine_chains (ch1, ch2);
3039 : 51971 : if (cch)
3040 : : {
3041 : 29 : worklist.safe_push (cch);
3042 : 29 : m_chains.safe_push (cch);
3043 : 29 : combined_p = true;
3044 : 29 : break;
3045 : : }
3046 : : }
3047 : : }
3048 : 15769 : if (!combined_p)
3049 : 15758 : return;
3050 : :
3051 : : /* Setup UID for all statements in dominance order. */
3052 : 11 : basic_block *bbs = get_loop_body_in_dom_order (m_loop);
3053 : 11 : renumber_gimple_stmt_uids_in_blocks (bbs, m_loop->num_nodes);
3054 : 11 : free (bbs);
3055 : :
3056 : : /* Re-association in combined chains may generate statements different to
3057 : : order of references of the original chain. We need to keep references
3058 : : of combined chain in dominance order so that all uses will be inserted
3059 : : after definitions. Note:
3060 : : A) This is necessary for all combined chains.
3061 : : B) This is only necessary for ZERO distance references because other
3062 : : references inherit value from loop carried PHIs.
3063 : :
3064 : : We first update position information for all combined chains. */
3065 : 11 : dref ref;
3066 : 90 : for (i = 0; m_chains.iterate (i, &ch1); ++i)
3067 : : {
3068 : 79 : if (ch1->type != CT_COMBINATION || ch1->combined)
3069 : 63 : continue;
3070 : :
3071 : 55 : for (j = 0; ch1->refs.iterate (j, &ref); ++j)
3072 : 39 : ref->pos = gimple_uid (ref->stmt);
3073 : :
3074 : 16 : update_pos_for_combined_chains (ch1);
3075 : : }
3076 : : /* Then sort references according to newly updated position information. */
3077 : 101 : for (i = 0; m_chains.iterate (i, &ch1); ++i)
3078 : : {
3079 : 79 : if (ch1->type != CT_COMBINATION && !ch1->combined)
3080 : 5 : continue;
3081 : :
3082 : : /* Find the first reference with non-ZERO distance. */
3083 : 74 : if (ch1->length == 0)
3084 : 86 : j = ch1->refs.length();
3085 : : else
3086 : : {
3087 : 124 : for (j = 0; ch1->refs.iterate (j, &ref); ++j)
3088 : 124 : if (ref->distance != 0)
3089 : : break;
3090 : : }
3091 : :
3092 : : /* Sort all ZERO distance references by position. */
3093 : 74 : qsort (&ch1->refs[0], j, sizeof (ch1->refs[0]), order_drefs_by_pos);
3094 : :
3095 : 74 : if (ch1->combined)
3096 : 58 : continue;
3097 : :
3098 : : /* For ZERO length chain, has_max_use_after must be true since root
3099 : : combined stmt must dominates others. */
3100 : 16 : if (ch1->length == 0)
3101 : : {
3102 : 4 : ch1->has_max_use_after = true;
3103 : 4 : continue;
3104 : : }
3105 : : /* Check if there is use at max distance after root for combined chains
3106 : : and set flag accordingly. */
3107 : 12 : ch1->has_max_use_after = false;
3108 : 12 : gimple *root_stmt = get_chain_root (ch1)->stmt;
3109 : 107 : for (j = 1; ch1->refs.iterate (j, &ref); ++j)
3110 : : {
3111 : 19 : if (ref->distance == ch1->length
3112 : 19 : && !pcom_stmt_dominates_stmt_p (ref->stmt, root_stmt))
3113 : : {
3114 : 3 : ch1->has_max_use_after = true;
3115 : 3 : break;
3116 : : }
3117 : : }
3118 : : }
3119 : 15769 : }
3120 : :
3121 : : /* Prepare initializers for store elimination CHAIN in LOOP. Returns false
3122 : : if this is impossible because one of these initializers may trap, true
3123 : : otherwise. */
3124 : :
3125 : : static bool
3126 : 54 : prepare_initializers_chain_store_elim (class loop *loop, chain_p chain)
3127 : : {
3128 : 54 : unsigned i, n = chain->length;
3129 : :
3130 : : /* For now we can't eliminate stores if some of them are conditional
3131 : : executed. */
3132 : 54 : if (!chain->all_always_accessed)
3133 : : return false;
3134 : :
3135 : : /* Nothing to intialize for intra-iteration store elimination. */
3136 : 54 : if (n == 0 && chain->type == CT_STORE_STORE)
3137 : : return true;
3138 : :
3139 : : /* For store elimination chain, there is nothing to initialize if stores
3140 : : to be eliminated only store loop invariant values into memory. */
3141 : 38 : if (chain->type == CT_STORE_STORE
3142 : 38 : && is_inv_store_elimination_chain (loop, chain))
3143 : : {
3144 : 15 : chain->inv_store_elimination = true;
3145 : 15 : return true;
3146 : : }
3147 : :
3148 : 23 : chain->inits.create (n);
3149 : 23 : chain->inits.safe_grow_cleared (n, true);
3150 : :
3151 : : /* For store eliminatin chain like below:
3152 : :
3153 : : for (i = 0; i < len; i++)
3154 : : {
3155 : : a[i] = 1;
3156 : : // a[i + 1] = ...
3157 : : a[i + 2] = 3;
3158 : : }
3159 : :
3160 : : store to a[i + 1] is missed in loop body, it acts like bubbles. The
3161 : : content of a[i + 1] remain the same if the loop iterates fewer times
3162 : : than chain->length. We need to set up root variables for such stores
3163 : : by loading from memory before loop. Note we only need to load bubble
3164 : : elements because loop body is guaranteed to be executed at least once
3165 : : after loop's preheader edge. */
3166 : 23 : auto_vec<bool> bubbles;
3167 : 23 : bubbles.safe_grow_cleared (n + 1, true);
3168 : 100 : for (i = 0; i < chain->refs.length (); i++)
3169 : 54 : bubbles[chain->refs[i]->distance] = true;
3170 : :
3171 : 23 : struct data_reference *dr = get_chain_root (chain)->ref;
3172 : 62 : for (i = 0; i < n; i++)
3173 : : {
3174 : 39 : if (bubbles[i])
3175 : 29 : continue;
3176 : :
3177 : 10 : gimple_seq stmts = NULL;
3178 : :
3179 : 10 : tree init = ref_at_iteration (dr, (int) 0 - i, &stmts);
3180 : 10 : if (stmts)
3181 : 2 : gimple_seq_add_seq_without_update (&chain->init_seq, stmts);
3182 : :
3183 : 10 : chain->inits[i] = init;
3184 : : }
3185 : :
3186 : 23 : return true;
3187 : 23 : }
3188 : :
3189 : : /* Prepare initializers for CHAIN. Returns false if this is impossible
3190 : : because one of these initializers may trap, true otherwise. */
3191 : :
3192 : : bool
3193 : 29140 : pcom_worker::prepare_initializers_chain (chain_p chain)
3194 : : {
3195 : 29140 : unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
3196 : 29140 : struct data_reference *dr = get_chain_root (chain)->ref;
3197 : 29140 : tree init;
3198 : 29140 : dref laref;
3199 : 29140 : edge entry = loop_preheader_edge (m_loop);
3200 : :
3201 : 29140 : if (chain->type == CT_STORE_STORE)
3202 : 54 : return prepare_initializers_chain_store_elim (m_loop, chain);
3203 : :
3204 : : /* Find the initializers for the variables, and check that they cannot
3205 : : trap. */
3206 : 29086 : chain->inits.create (n);
3207 : 82678 : for (i = 0; i < n; i++)
3208 : 24506 : chain->inits.quick_push (NULL_TREE);
3209 : :
3210 : : /* If we have replaced some looparound phi nodes, use their initializers
3211 : : instead of creating our own. */
3212 : 76528 : FOR_EACH_VEC_ELT (chain->refs, i, laref)
3213 : : {
3214 : 47442 : if (gimple_code (laref->stmt) != GIMPLE_PHI)
3215 : 47441 : continue;
3216 : :
3217 : 1 : gcc_assert (laref->distance > 0);
3218 : 1 : chain->inits[n - laref->distance]
3219 : 2 : = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
3220 : : }
3221 : :
3222 : 50730 : for (i = 0; i < n; i++)
3223 : : {
3224 : 24506 : gimple_seq stmts = NULL;
3225 : :
3226 : 24506 : if (chain->inits[i] != NULL_TREE)
3227 : 1 : continue;
3228 : :
3229 : 24505 : init = ref_at_iteration (dr, (int) i - n, &stmts);
3230 : 24505 : if (!chain->all_always_accessed && tree_could_trap_p (init))
3231 : : {
3232 : 2862 : gimple_seq_discard (stmts);
3233 : 2862 : return false;
3234 : : }
3235 : :
3236 : 21643 : if (stmts)
3237 : 1140 : gimple_seq_add_seq_without_update (&chain->init_seq, stmts);
3238 : :
3239 : 21643 : chain->inits[i] = init;
3240 : : }
3241 : :
3242 : : return true;
3243 : : }
3244 : :
3245 : : /* Prepare initializers for chains, and free chains that cannot
3246 : : be used because the initializers might trap. */
3247 : :
3248 : : void
3249 : 15769 : pcom_worker::prepare_initializers ()
3250 : : {
3251 : 15769 : chain_p chain;
3252 : 15769 : unsigned i;
3253 : :
3254 : 44909 : for (i = 0; i < m_chains.length (); )
3255 : : {
3256 : 29140 : chain = m_chains[i];
3257 : 29140 : if (prepare_initializers_chain (chain))
3258 : 26278 : i++;
3259 : : else
3260 : : {
3261 : 2862 : release_chain (chain);
3262 : 2862 : m_chains.unordered_remove (i);
3263 : : }
3264 : : }
3265 : 15769 : }
3266 : :
3267 : : /* Generates finalizer memory references for CHAIN. Returns true
3268 : : if finalizer code for CHAIN can be generated, otherwise false. */
3269 : :
3270 : : bool
3271 : 38 : pcom_worker::prepare_finalizers_chain (chain_p chain)
3272 : : {
3273 : 38 : unsigned i, n = chain->length;
3274 : 38 : struct data_reference *dr = get_chain_root (chain)->ref;
3275 : 38 : tree fini, niters = number_of_latch_executions (m_loop);
3276 : :
3277 : : /* For now we can't eliminate stores if some of them are conditional
3278 : : executed. */
3279 : 38 : if (!chain->all_always_accessed)
3280 : : return false;
3281 : :
3282 : 38 : chain->finis.create (n);
3283 : 142 : for (i = 0; i < n; i++)
3284 : 66 : chain->finis.quick_push (NULL_TREE);
3285 : :
3286 : : /* We never use looparound phi node for store elimination chains. */
3287 : :
3288 : : /* Find the finalizers for the variables, and check that they cannot
3289 : : trap. */
3290 : 104 : for (i = 0; i < n; i++)
3291 : : {
3292 : 66 : gimple_seq stmts = NULL;
3293 : 66 : gcc_assert (chain->finis[i] == NULL_TREE);
3294 : :
3295 : 66 : if (TREE_CODE (niters) != INTEGER_CST && TREE_CODE (niters) != SSA_NAME)
3296 : : {
3297 : 11 : niters = unshare_expr (niters);
3298 : 11 : niters = force_gimple_operand (niters, &stmts, true, NULL);
3299 : 11 : if (stmts)
3300 : : {
3301 : 11 : gimple_seq_add_seq_without_update (&chain->fini_seq, stmts);
3302 : 11 : stmts = NULL;
3303 : : }
3304 : : }
3305 : 66 : fini = ref_at_iteration (dr, (int) 0 - i, &stmts, niters);
3306 : 66 : if (stmts)
3307 : 26 : gimple_seq_add_seq_without_update (&chain->fini_seq, stmts);
3308 : :
3309 : 66 : chain->finis[i] = fini;
3310 : : }
3311 : :
3312 : : return true;
3313 : : }
3314 : :
3315 : : /* Generates finalizer memory reference for chains. Returns true if
3316 : : finalizer code generation for chains breaks loop closed ssa form. */
3317 : :
3318 : : bool
3319 : 15769 : pcom_worker::prepare_finalizers ()
3320 : : {
3321 : 15769 : chain_p chain;
3322 : 15769 : unsigned i;
3323 : 15769 : bool loop_closed_ssa = false;
3324 : :
3325 : 42047 : for (i = 0; i < m_chains.length ();)
3326 : : {
3327 : 26278 : chain = m_chains[i];
3328 : :
3329 : : /* Finalizer is only necessary for inter-iteration store elimination
3330 : : chains. */
3331 : 26278 : if (chain->length == 0 || chain->type != CT_STORE_STORE)
3332 : : {
3333 : 26240 : i++;
3334 : 26240 : continue;
3335 : : }
3336 : :
3337 : 38 : if (prepare_finalizers_chain (chain))
3338 : : {
3339 : 38 : i++;
3340 : : /* Be conservative, assume loop closed ssa form is corrupted
3341 : : by store-store chain. Though it's not always the case if
3342 : : eliminated stores only store loop invariant values into
3343 : : memory. */
3344 : 38 : loop_closed_ssa = true;
3345 : : }
3346 : : else
3347 : : {
3348 : 0 : release_chain (chain);
3349 : 0 : m_chains.unordered_remove (i);
3350 : : }
3351 : : }
3352 : 15769 : return loop_closed_ssa;
3353 : : }
3354 : :
3355 : : /* Insert all initializing gimple stmts into LOOP's entry edge. */
3356 : :
3357 : : static void
3358 : 15769 : insert_init_seqs (class loop *loop, vec<chain_p> &chains)
3359 : : {
3360 : 15769 : unsigned i;
3361 : 15769 : edge entry = loop_preheader_edge (loop);
3362 : :
3363 : 57845 : for (i = 0; i < chains.length (); ++i)
3364 : 26307 : if (chains[i]->init_seq)
3365 : : {
3366 : 1107 : gsi_insert_seq_on_edge_immediate (entry, chains[i]->init_seq);
3367 : 1107 : chains[i]->init_seq = NULL;
3368 : : }
3369 : 15769 : }
3370 : :
3371 : : /* Performs predictive commoning for LOOP. Sets bit 1<<1 of return value
3372 : : if LOOP was unrolled; Sets bit 1<<2 of return value if loop closed ssa
3373 : : form was corrupted. Non-zero return value indicates some changes were
3374 : : applied to this loop. */
3375 : :
3376 : : unsigned
3377 : 418112 : pcom_worker::tree_predictive_commoning_loop (bool allow_unroll_p)
3378 : : {
3379 : 418112 : struct component *components;
3380 : 418112 : unsigned unroll_factor = 0;
3381 : 418112 : class tree_niter_desc desc;
3382 : 418112 : bool unroll = false, loop_closed_ssa = false;
3383 : :
3384 : 418112 : if (dump_file && (dump_flags & TDF_DETAILS))
3385 : 57 : fprintf (dump_file, "Processing loop %d\n", m_loop->num);
3386 : :
3387 : : /* Nothing for predicitive commoning if loop only iterates 1 time. */
3388 : 418112 : if (get_max_loop_iterations_int (m_loop) == 0)
3389 : : {
3390 : 21983 : if (dump_file && (dump_flags & TDF_DETAILS))
3391 : 1 : fprintf (dump_file, "Loop iterates only 1 time, nothing to do.\n");
3392 : :
3393 : 21983 : return 0;
3394 : : }
3395 : :
3396 : : /* Find the data references and split them into components according to their
3397 : : dependence relations. */
3398 : 396129 : auto_vec<loop_p, 3> loop_nest;
3399 : 396129 : if (!compute_data_dependences_for_loop (m_loop, true, &loop_nest, &m_datarefs,
3400 : : &m_dependences))
3401 : : {
3402 : 145495 : if (dump_file && (dump_flags & TDF_DETAILS))
3403 : 0 : fprintf (dump_file, "Cannot analyze data dependencies\n");
3404 : 145495 : return 0;
3405 : : }
3406 : :
3407 : 250634 : if (dump_file && (dump_flags & TDF_DETAILS))
3408 : 56 : dump_data_dependence_relations (dump_file, m_dependences);
3409 : :
3410 : 250634 : components = split_data_refs_to_components ();
3411 : :
3412 : 250634 : loop_nest.release ();
3413 : 250634 : if (!components)
3414 : : return 0;
3415 : :
3416 : 167965 : if (dump_file && (dump_flags & TDF_DETAILS))
3417 : : {
3418 : 55 : fprintf (dump_file, "Initial state:\n\n");
3419 : 55 : dump_components (dump_file, components);
3420 : : }
3421 : :
3422 : : /* Find the suitable components and split them into chains. */
3423 : 167965 : components = filter_suitable_components (components);
3424 : :
3425 : 167965 : auto_bitmap tmp_vars;
3426 : 167965 : determine_roots (components);
3427 : 167965 : release_components (components);
3428 : :
3429 : 167965 : if (!m_chains.exists ())
3430 : : {
3431 : 152196 : if (dump_file && (dump_flags & TDF_DETAILS))
3432 : 20 : fprintf (dump_file,
3433 : : "Predictive commoning failed: no suitable chains\n");
3434 : 152196 : return 0;
3435 : : }
3436 : :
3437 : 15769 : prepare_initializers ();
3438 : 15769 : loop_closed_ssa = prepare_finalizers ();
3439 : :
3440 : : /* Try to combine the chains that are always worked with together. */
3441 : 15769 : try_combine_chains ();
3442 : :
3443 : 15769 : insert_init_seqs (m_loop, m_chains);
3444 : :
3445 : 15769 : if (dump_file && (dump_flags & TDF_DETAILS))
3446 : : {
3447 : 35 : fprintf (dump_file, "Before commoning:\n\n");
3448 : 35 : dump_chains (dump_file, m_chains);
3449 : : }
3450 : :
3451 : 15769 : if (allow_unroll_p)
3452 : : /* Determine the unroll factor, and if the loop should be unrolled, ensure
3453 : : that its number of iterations is divisible by the factor. */
3454 : 3073 : unroll_factor = determine_unroll_factor (m_chains);
3455 : :
3456 : 3073 : if (unroll_factor > 1)
3457 : 637 : unroll = can_unroll_loop_p (m_loop, unroll_factor, &desc);
3458 : :
3459 : : /* Execute the predictive commoning transformations, and possibly unroll the
3460 : : loop. */
3461 : 637 : if (unroll)
3462 : : {
3463 : 624 : struct epcc_data dta;
3464 : :
3465 : 624 : if (dump_file && (dump_flags & TDF_DETAILS))
3466 : 9 : fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
3467 : :
3468 : 624 : dta.tmp_vars = tmp_vars;
3469 : 624 : dta.chains = m_chains.to_vec_legacy ();
3470 : 624 : dta.worker = this;
3471 : :
3472 : : /* Cfg manipulations performed in tree_transform_and_unroll_loop before
3473 : : execute_pred_commoning_cbck is called may cause phi nodes to be
3474 : : reallocated, which is a problem since CHAINS may point to these
3475 : : statements. To fix this, we store the ssa names defined by the
3476 : : phi nodes here instead of the phi nodes themselves, and restore
3477 : : the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
3478 : 624 : replace_phis_by_defined_names (m_chains);
3479 : :
3480 : 624 : tree_transform_and_unroll_loop (m_loop, unroll_factor, &desc,
3481 : : execute_pred_commoning_cbck, &dta);
3482 : 624 : eliminate_temp_copies (m_loop, tmp_vars);
3483 : : }
3484 : : else
3485 : : {
3486 : 15145 : if (dump_file && (dump_flags & TDF_DETAILS))
3487 : 26 : fprintf (dump_file,
3488 : : "Executing predictive commoning without unrolling.\n");
3489 : 15145 : execute_pred_commoning (tmp_vars);
3490 : : }
3491 : :
3492 : 46646 : return (unroll ? 2 : 1) | (loop_closed_ssa ? 4 : 1);
3493 : 564094 : }
3494 : :
3495 : : /* Runs predictive commoning. */
3496 : :
3497 : : unsigned
3498 : 204925 : tree_predictive_commoning (bool allow_unroll_p)
3499 : : {
3500 : 204925 : unsigned ret = 0, changed = 0;
3501 : :
3502 : 204925 : initialize_original_copy_tables ();
3503 : 1054080 : for (auto loop : loops_list (cfun, LI_ONLY_INNERMOST))
3504 : 439305 : if (optimize_loop_for_speed_p (loop))
3505 : : {
3506 : 418112 : pcom_worker w(loop);
3507 : 418112 : changed |= w.tree_predictive_commoning_loop (allow_unroll_p);
3508 : 418112 : }
3509 : 204925 : free_original_copy_tables ();
3510 : :
3511 : 204925 : if (changed > 0)
3512 : : {
3513 : 10667 : ret = TODO_update_ssa_only_virtuals;
3514 : :
3515 : : /* Some loop(s) got unrolled. */
3516 : 10667 : if (changed > 1)
3517 : : {
3518 : 579 : scev_reset ();
3519 : :
3520 : : /* Need to fix up loop closed SSA. */
3521 : 579 : if (changed >= 4)
3522 : 37 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3523 : :
3524 : : ret |= TODO_cleanup_cfg;
3525 : : }
3526 : : }
3527 : :
3528 : : if (ret != 0)
3529 : 10667 : cfun->pending_TODOs |= PENDING_TODO_force_next_scalar_cleanup;
3530 : :
3531 : 204925 : return ret;
3532 : : }
3533 : :
3534 : : /* Predictive commoning Pass. */
3535 : :
3536 : : static unsigned
3537 : 204925 : run_tree_predictive_commoning (struct function *fun, bool allow_unroll_p)
3538 : : {
3539 : 409850 : if (number_of_loops (fun) <= 1)
3540 : : return 0;
3541 : :
3542 : 204925 : return tree_predictive_commoning (allow_unroll_p);
3543 : : }
3544 : :
3545 : : namespace {
3546 : :
3547 : : const pass_data pass_data_predcom =
3548 : : {
3549 : : GIMPLE_PASS, /* type */
3550 : : "pcom", /* name */
3551 : : OPTGROUP_LOOP, /* optinfo_flags */
3552 : : TV_PREDCOM, /* tv_id */
3553 : : PROP_cfg, /* properties_required */
3554 : : 0, /* properties_provided */
3555 : : 0, /* properties_destroyed */
3556 : : 0, /* todo_flags_start */
3557 : : 0, /* todo_flags_finish */
3558 : : };
3559 : :
3560 : : class pass_predcom : public gimple_opt_pass
3561 : : {
3562 : : public:
3563 : 285081 : pass_predcom (gcc::context *ctxt)
3564 : 570162 : : gimple_opt_pass (pass_data_predcom, ctxt)
3565 : : {}
3566 : :
3567 : : /* opt_pass methods: */
3568 : : bool
3569 : 237971 : gate (function *) final override
3570 : : {
3571 : 237971 : if (flag_predictive_commoning != 0)
3572 : : return true;
3573 : : /* Loop vectorization enables predictive commoning implicitly
3574 : : only if predictive commoning isn't set explicitly, and it
3575 : : doesn't allow unrolling. */
3576 : 211525 : if (flag_tree_loop_vectorize
3577 : 178480 : && !OPTION_SET_P (flag_predictive_commoning))
3578 : 178480 : return true;
3579 : :
3580 : : return false;
3581 : : }
3582 : :
3583 : : unsigned int
3584 : 204925 : execute (function *fun) final override
3585 : : {
3586 : 204925 : bool allow_unroll_p = flag_predictive_commoning != 0;
3587 : 204925 : return run_tree_predictive_commoning (fun, allow_unroll_p);
3588 : : }
3589 : :
3590 : : }; // class pass_predcom
3591 : :
3592 : : } // anon namespace
3593 : :
3594 : : gimple_opt_pass *
3595 : 285081 : make_pass_predcom (gcc::context *ctxt)
3596 : : {
3597 : 285081 : return new pass_predcom (ctxt);
3598 : : }
|
