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