Branch data Line data Source code
1 : : /* Predictive commoning.
2 : : Copyright (C) 2005-2024 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 : : #define INCLUDE_MEMORY
209 : : #include "system.h"
210 : : #include "coretypes.h"
211 : : #include "backend.h"
212 : : #include "rtl.h"
213 : : #include "tree.h"
214 : : #include "gimple.h"
215 : : #include "predict.h"
216 : : #include "tree-pass.h"
217 : : #include "ssa.h"
218 : : #include "gimple-pretty-print.h"
219 : : #include "alias.h"
220 : : #include "fold-const.h"
221 : : #include "cfgloop.h"
222 : : #include "tree-eh.h"
223 : : #include "gimplify.h"
224 : : #include "gimple-iterator.h"
225 : : #include "gimplify-me.h"
226 : : #include "tree-ssa-loop-ivopts.h"
227 : : #include "tree-ssa-loop-manip.h"
228 : : #include "tree-ssa-loop-niter.h"
229 : : #include "tree-ssa-loop.h"
230 : : #include "tree-into-ssa.h"
231 : : #include "tree-dfa.h"
232 : : #include "tree-ssa.h"
233 : : #include "tree-data-ref.h"
234 : : #include "tree-scalar-evolution.h"
235 : : #include "tree-affine.h"
236 : : #include "builtins.h"
237 : : #include "opts.h"
238 : :
239 : : /* The maximum number of iterations between the considered memory
240 : : references. */
241 : :
242 : : #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
243 : :
244 : : /* Data references (or phi nodes that carry data reference values across
245 : : loop iterations). */
246 : :
247 : : typedef class dref_d
248 : : {
249 : : public:
250 : : /* The reference itself. */
251 : : struct data_reference *ref;
252 : :
253 : : /* The statement in that the reference appears. */
254 : : gimple *stmt;
255 : :
256 : : /* In case that STMT is a phi node, this field is set to the SSA name
257 : : defined by it in replace_phis_by_defined_names (in order to avoid
258 : : pointing to phi node that got reallocated in the meantime). */
259 : : tree name_defined_by_phi;
260 : :
261 : : /* Distance of the reference from the root of the chain (in number of
262 : : iterations of the loop). */
263 : : unsigned distance;
264 : :
265 : : /* Number of iterations offset from the first reference in the component. */
266 : : widest_int offset;
267 : :
268 : : /* Number of the reference in a component, in dominance ordering. */
269 : : unsigned pos;
270 : :
271 : : /* True if the memory reference is always accessed when the loop is
272 : : entered. */
273 : : unsigned always_accessed : 1;
274 : : } *dref;
275 : :
276 : :
277 : : /* Type of the chain of the references. */
278 : :
279 : : enum chain_type
280 : : {
281 : : /* The addresses of the references in the chain are constant. */
282 : : CT_INVARIANT,
283 : :
284 : : /* There are only loads in the chain. */
285 : : CT_LOAD,
286 : :
287 : : /* Root of the chain is store, the rest are loads. */
288 : : CT_STORE_LOAD,
289 : :
290 : : /* There are only stores in the chain. */
291 : : CT_STORE_STORE,
292 : :
293 : : /* A combination of two chains. */
294 : : CT_COMBINATION
295 : : };
296 : :
297 : : /* Chains of data references. */
298 : :
299 : : typedef struct chain
300 : : {
301 : 60729 : chain (chain_type t) : type (t), op (ERROR_MARK), rslt_type (NULL_TREE),
302 : 60729 : ch1 (NULL), ch2 (NULL), length (0), init_seq (NULL), fini_seq (NULL),
303 : 60729 : has_max_use_after (false), all_always_accessed (false), combined (false),
304 : 60729 : inv_store_elimination (false) {}
305 : :
306 : : /* Type of the chain. */
307 : : enum chain_type type;
308 : :
309 : : /* For combination chains, the operator and the two chains that are
310 : : combined, and the type of the result. */
311 : : enum tree_code op;
312 : : tree rslt_type;
313 : : struct chain *ch1, *ch2;
314 : :
315 : : /* The references in the chain. */
316 : : auto_vec<dref> refs;
317 : :
318 : : /* The maximum distance of the reference in the chain from the root. */
319 : : unsigned length;
320 : :
321 : : /* The variables used to copy the value throughout iterations. */
322 : : auto_vec<tree> vars;
323 : :
324 : : /* Initializers for the variables. */
325 : : auto_vec<tree> inits;
326 : :
327 : : /* Finalizers for the eliminated stores. */
328 : : auto_vec<tree> finis;
329 : :
330 : : /* gimple stmts intializing the initial variables of the chain. */
331 : : gimple_seq init_seq;
332 : :
333 : : /* gimple stmts finalizing the eliminated stores of the chain. */
334 : : gimple_seq fini_seq;
335 : :
336 : : /* True if there is a use of a variable with the maximal distance
337 : : that comes after the root in the loop. */
338 : : unsigned has_max_use_after : 1;
339 : :
340 : : /* True if all the memory references in the chain are always accessed. */
341 : : unsigned all_always_accessed : 1;
342 : :
343 : : /* True if this chain was combined together with some other chain. */
344 : : unsigned combined : 1;
345 : :
346 : : /* True if this is store elimination chain and eliminated stores store
347 : : loop invariant value into memory. */
348 : : unsigned inv_store_elimination : 1;
349 : : } *chain_p;
350 : :
351 : :
352 : : /* Describes the knowledge about the step of the memory references in
353 : : the component. */
354 : :
355 : : enum ref_step_type
356 : : {
357 : : /* The step is zero. */
358 : : RS_INVARIANT,
359 : :
360 : : /* The step is nonzero. */
361 : : RS_NONZERO,
362 : :
363 : : /* The step may or may not be nonzero. */
364 : : RS_ANY
365 : : };
366 : :
367 : : /* Components of the data dependence graph. */
368 : :
369 : 658380 : struct component
370 : : {
371 : 329190 : component (bool es) : comp_step (RS_ANY), eliminate_store_p (es),
372 : 329190 : next (NULL) {}
373 : :
374 : : /* The references in the component. */
375 : : auto_vec<dref> refs;
376 : :
377 : : /* What we know about the step of the references in the component. */
378 : : enum ref_step_type comp_step;
379 : :
380 : : /* True if all references in component are stores and we try to do
381 : : intra/inter loop iteration dead store elimination. */
382 : : bool eliminate_store_p;
383 : :
384 : : /* Next component in the list. */
385 : : struct component *next;
386 : : };
387 : :
388 : : /* A class to encapsulate the global states used for predictive
389 : : commoning work on top of one given LOOP. */
390 : :
391 : : class pcom_worker
392 : : {
393 : : public:
394 : 362052 : pcom_worker (loop_p l) : m_loop (l), m_cache (NULL) {}
395 : :
396 : 362052 : ~pcom_worker ()
397 : : {
398 : 362052 : free_data_refs (m_datarefs);
399 : 362052 : free_dependence_relations (m_dependences);
400 : 362052 : free_affine_expand_cache (&m_cache);
401 : 362052 : release_chains ();
402 : 362052 : }
403 : :
404 : : pcom_worker (const pcom_worker &) = delete;
405 : : pcom_worker &operator= (const pcom_worker &) = delete;
406 : :
407 : : /* Performs predictive commoning. */
408 : : unsigned tree_predictive_commoning_loop (bool allow_unroll_p);
409 : :
410 : : /* Perform the predictive commoning optimization for chains, make this
411 : : public for being called in callback execute_pred_commoning_cbck. */
412 : : void execute_pred_commoning (bitmap tmp_vars);
413 : :
414 : : private:
415 : : /* The pointer to the given loop. */
416 : : loop_p m_loop;
417 : :
418 : : /* All data references. */
419 : : auto_vec<data_reference_p, 10> m_datarefs;
420 : :
421 : : /* All data dependences. */
422 : : auto_vec<ddr_p, 10> m_dependences;
423 : :
424 : : /* All chains. */
425 : : auto_vec<chain_p> m_chains;
426 : :
427 : : /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
428 : : auto_bitmap m_looparound_phis;
429 : :
430 : : typedef hash_map<tree, name_expansion *> tree_expand_map_t;
431 : : /* Cache used by tree_to_aff_combination_expand. */
432 : : tree_expand_map_t *m_cache;
433 : :
434 : : /* Splits dependence graph to components. */
435 : : struct component *split_data_refs_to_components ();
436 : :
437 : : /* Check the conditions on references inside each of components COMPS,
438 : : and remove the unsuitable components from the list. */
439 : : struct component *filter_suitable_components (struct component *comps);
440 : :
441 : : /* Find roots of the values and determine distances in components COMPS,
442 : : and separates the references to chains. */
443 : : void determine_roots (struct component *comps);
444 : :
445 : : /* Prepare initializers for chains, and free chains that cannot
446 : : be used because the initializers might trap. */
447 : : void prepare_initializers ();
448 : :
449 : : /* Generates finalizer memory reference for chains. Returns true if
450 : : finalizer code generation for chains breaks loop closed ssa form. */
451 : : bool prepare_finalizers ();
452 : :
453 : : /* Try to combine the chains. */
454 : : void try_combine_chains ();
455 : :
456 : : /* Frees CHAINS. */
457 : : void release_chains ();
458 : :
459 : : /* Frees a chain CHAIN. */
460 : : void release_chain (chain_p chain);
461 : :
462 : : /* Prepare initializers for CHAIN. Returns false if this is impossible
463 : : because one of these initializers may trap, true otherwise. */
464 : : bool prepare_initializers_chain (chain_p chain);
465 : :
466 : : /* Generates finalizer memory references for CHAIN. Returns true
467 : : if finalizer code for CHAIN can be generated, otherwise false. */
468 : : bool prepare_finalizers_chain (chain_p chain);
469 : :
470 : : /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
471 : : void aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset);
472 : :
473 : : /* Determines number of iterations of the innermost enclosing loop before
474 : : B refers to exactly the same location as A and stores it to OFF. */
475 : : bool determine_offset (struct data_reference *a, struct data_reference *b,
476 : : poly_widest_int *off);
477 : :
478 : : /* Returns true if the component COMP satisfies the conditions
479 : : described in 2) at the beginning of this file. */
480 : : bool suitable_component_p (struct component *comp);
481 : :
482 : : /* Returns true if REF is a valid initializer for ROOT with given
483 : : DISTANCE (in iterations of the innermost enclosing loop). */
484 : : bool valid_initializer_p (struct data_reference *ref, unsigned distance,
485 : : struct data_reference *root);
486 : :
487 : : /* Finds looparound phi node of loop that copies the value of REF. */
488 : : gphi *find_looparound_phi (dref ref, dref root);
489 : :
490 : : /* Find roots of the values and determine distances in the component
491 : : COMP. The references are redistributed into chains. */
492 : : void determine_roots_comp (struct component *comp);
493 : :
494 : : /* For references in CHAIN that are copied around the loop, add the
495 : : results of such copies to the chain. */
496 : : void add_looparound_copies (chain_p chain);
497 : :
498 : : /* Returns the single statement in that NAME is used, excepting
499 : : the looparound phi nodes contained in one of the chains. */
500 : : gimple *single_nonlooparound_use (tree name);
501 : :
502 : : /* Remove statement STMT, as well as the chain of assignments in that
503 : : it is used. */
504 : : void remove_stmt (gimple *stmt);
505 : :
506 : : /* Perform the predictive commoning optimization for a chain CHAIN. */
507 : : void execute_pred_commoning_chain (chain_p chain, bitmap tmp_vars);
508 : :
509 : : /* Returns the modify statement that uses NAME. */
510 : : gimple *find_use_stmt (tree *name);
511 : :
512 : : /* If the operation used in STMT is associative and commutative, go
513 : : through the tree of the same operations and returns its root. */
514 : : gimple *find_associative_operation_root (gimple *stmt, unsigned *distance);
515 : :
516 : : /* Returns the common statement in that NAME1 and NAME2 have a use. */
517 : : gimple *find_common_use_stmt (tree *name1, tree *name2);
518 : :
519 : : /* Checks whether R1 and R2 are combined together using CODE, with the
520 : : result in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order
521 : : R2 CODE R1 if it is true. */
522 : : bool combinable_refs_p (dref r1, dref r2, enum tree_code *code, bool *swap,
523 : : tree *rslt_type);
524 : :
525 : : /* Reassociates the expression in that NAME1 and NAME2 are used so that
526 : : they are combined in a single statement, and returns this statement. */
527 : : gimple *reassociate_to_the_same_stmt (tree name1, tree name2);
528 : :
529 : : /* Returns the statement that combines references R1 and R2. */
530 : : gimple *stmt_combining_refs (dref r1, dref r2);
531 : :
532 : : /* Tries to combine chains CH1 and CH2 together. */
533 : : chain_p combine_chains (chain_p ch1, chain_p ch2);
534 : : };
535 : :
536 : : /* Dumps data reference REF to FILE. */
537 : :
538 : : extern void dump_dref (FILE *, dref);
539 : : void
540 : 308 : dump_dref (FILE *file, dref ref)
541 : : {
542 : 308 : if (ref->ref)
543 : : {
544 : 289 : fprintf (file, " ");
545 : 289 : print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
546 : 289 : fprintf (file, " (id %u%s)\n", ref->pos,
547 : 289 : DR_IS_READ (ref->ref) ? "" : ", write");
548 : :
549 : 289 : fprintf (file, " offset ");
550 : 289 : print_decs (ref->offset, file);
551 : 289 : fprintf (file, "\n");
552 : :
553 : 289 : fprintf (file, " distance %u\n", ref->distance);
554 : : }
555 : : else
556 : : {
557 : 19 : if (gimple_code (ref->stmt) == GIMPLE_PHI)
558 : 1 : fprintf (file, " looparound ref\n");
559 : : else
560 : 18 : fprintf (file, " combination ref\n");
561 : 19 : fprintf (file, " in statement ");
562 : 19 : print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
563 : 19 : fprintf (file, "\n");
564 : 19 : fprintf (file, " distance %u\n", ref->distance);
565 : : }
566 : :
567 : 308 : }
568 : :
569 : : /* Dumps CHAIN to FILE. */
570 : :
571 : : extern void dump_chain (FILE *, chain_p);
572 : : void
573 : 58 : dump_chain (FILE *file, chain_p chain)
574 : : {
575 : 58 : dref a;
576 : 58 : const char *chain_type;
577 : 58 : unsigned i;
578 : 58 : tree var;
579 : :
580 : 58 : switch (chain->type)
581 : : {
582 : : case CT_INVARIANT:
583 : : chain_type = "Load motion";
584 : : break;
585 : :
586 : 24 : case CT_LOAD:
587 : 24 : chain_type = "Loads-only";
588 : 24 : break;
589 : :
590 : 5 : case CT_STORE_LOAD:
591 : 5 : chain_type = "Store-loads";
592 : 5 : break;
593 : :
594 : 19 : case CT_STORE_STORE:
595 : 19 : chain_type = "Store-stores";
596 : 19 : break;
597 : :
598 : 9 : case CT_COMBINATION:
599 : 9 : chain_type = "Combination";
600 : 9 : break;
601 : :
602 : 0 : default:
603 : 0 : gcc_unreachable ();
604 : : }
605 : :
606 : 58 : fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
607 : 58 : chain->combined ? " (combined)" : "");
608 : 58 : if (chain->type != CT_INVARIANT)
609 : 57 : fprintf (file, " max distance %u%s\n", chain->length,
610 : 57 : chain->has_max_use_after ? "" : ", may reuse first");
611 : :
612 : 58 : if (chain->type == CT_COMBINATION)
613 : : {
614 : 18 : fprintf (file, " equal to %p %s %p in type ",
615 : 9 : (void *) chain->ch1, op_symbol_code (chain->op),
616 : 9 : (void *) chain->ch2);
617 : 9 : print_generic_expr (file, chain->rslt_type, TDF_SLIM);
618 : 9 : fprintf (file, "\n");
619 : : }
620 : :
621 : 58 : if (chain->vars.exists ())
622 : : {
623 : 0 : fprintf (file, " vars");
624 : 0 : FOR_EACH_VEC_ELT (chain->vars, i, var)
625 : : {
626 : 0 : fprintf (file, " ");
627 : 0 : print_generic_expr (file, var, TDF_SLIM);
628 : : }
629 : 0 : fprintf (file, "\n");
630 : : }
631 : :
632 : 58 : if (chain->inits.exists ())
633 : : {
634 : 41 : fprintf (file, " inits");
635 : 149 : FOR_EACH_VEC_ELT (chain->inits, i, var)
636 : : {
637 : 67 : fprintf (file, " ");
638 : 67 : print_generic_expr (file, var, TDF_SLIM);
639 : : }
640 : 41 : fprintf (file, "\n");
641 : : }
642 : :
643 : 58 : fprintf (file, " references:\n");
644 : 251 : FOR_EACH_VEC_ELT (chain->refs, i, a)
645 : 135 : dump_dref (file, a);
646 : :
647 : 58 : fprintf (file, "\n");
648 : 58 : }
649 : :
650 : : /* Dumps CHAINS to FILE. */
651 : :
652 : : void
653 : 34 : dump_chains (FILE *file, const vec<chain_p> &chains)
654 : : {
655 : 34 : chain_p chain;
656 : 34 : unsigned i;
657 : :
658 : 92 : FOR_EACH_VEC_ELT (chains, i, chain)
659 : 58 : dump_chain (file, chain);
660 : 34 : }
661 : :
662 : : /* Dumps COMP to FILE. */
663 : :
664 : : extern void dump_component (FILE *, struct component *);
665 : : void
666 : 103 : dump_component (FILE *file, struct component *comp)
667 : : {
668 : 103 : dref a;
669 : 103 : unsigned i;
670 : :
671 : 206 : fprintf (file, "Component%s:\n",
672 : 103 : comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
673 : 379 : FOR_EACH_VEC_ELT (comp->refs, i, a)
674 : 173 : dump_dref (file, a);
675 : 103 : fprintf (file, "\n");
676 : 103 : }
677 : :
678 : : /* Dumps COMPS to FILE. */
679 : :
680 : : extern void dump_components (FILE *, struct component *);
681 : : void
682 : 54 : dump_components (FILE *file, struct component *comps)
683 : : {
684 : 54 : struct component *comp;
685 : :
686 : 157 : for (comp = comps; comp; comp = comp->next)
687 : 103 : dump_component (file, comp);
688 : 54 : }
689 : :
690 : : /* Frees a chain CHAIN. */
691 : :
692 : : void
693 : 90005 : pcom_worker::release_chain (chain_p chain)
694 : : {
695 : 90005 : dref ref;
696 : 90005 : unsigned i;
697 : :
698 : 90005 : if (chain == NULL)
699 : 90005 : return;
700 : :
701 : 139287 : FOR_EACH_VEC_ELT (chain->refs, i, ref)
702 : 78558 : free (ref);
703 : :
704 : 60729 : if (chain->init_seq)
705 : 0 : gimple_seq_discard (chain->init_seq);
706 : :
707 : 60729 : if (chain->fini_seq)
708 : 0 : gimple_seq_discard (chain->fini_seq);
709 : :
710 : 60729 : delete chain;
711 : : }
712 : :
713 : : /* Frees CHAINS. */
714 : :
715 : : void
716 : 362052 : pcom_worker::release_chains ()
717 : : {
718 : 362052 : unsigned i;
719 : 362052 : chain_p chain;
720 : :
721 : 387830 : FOR_EACH_VEC_ELT (m_chains, i, chain)
722 : 25778 : release_chain (chain);
723 : 362052 : }
724 : :
725 : : /* Frees list of components COMPS. */
726 : :
727 : : static void
728 : 140347 : release_components (struct component *comps)
729 : : {
730 : 140347 : struct component *act, *next;
731 : :
732 : 444250 : for (act = comps; act; act = next)
733 : : {
734 : 303903 : next = act->next;
735 : 303903 : delete act;
736 : : }
737 : 140347 : }
738 : :
739 : : /* Finds a root of tree given by FATHERS containing A, and performs path
740 : : shortening. */
741 : :
742 : : static unsigned
743 : 6171961 : component_of (vec<unsigned> &fathers, unsigned a)
744 : : {
745 : 6171961 : unsigned root, n;
746 : :
747 : 9298542 : for (root = a; root != fathers[root]; root = fathers[root])
748 : 3126581 : continue;
749 : :
750 : 9298542 : for (; a != root; a = n)
751 : : {
752 : 3126581 : n = fathers[a];
753 : 3126581 : fathers[a] = root;
754 : : }
755 : :
756 : 6171961 : return root;
757 : 3126581 : }
758 : :
759 : : /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
760 : : components, A and B are components to merge. */
761 : :
762 : : static void
763 : 282798 : merge_comps (vec<unsigned> &fathers, vec<unsigned> &sizes,
764 : : unsigned a, unsigned b)
765 : : {
766 : 282798 : unsigned ca = component_of (fathers, a);
767 : 282798 : unsigned cb = component_of (fathers, b);
768 : :
769 : 282798 : if (ca == cb)
770 : : return;
771 : :
772 : 282798 : if (sizes[ca] < sizes[cb])
773 : : {
774 : 16568 : sizes[cb] += sizes[ca];
775 : 16568 : fathers[ca] = cb;
776 : : }
777 : : else
778 : : {
779 : 266230 : sizes[ca] += sizes[cb];
780 : 266230 : fathers[cb] = ca;
781 : : }
782 : : }
783 : :
784 : : /* Returns true if A is a reference that is suitable for predictive commoning
785 : : in the innermost loop that contains it. REF_STEP is set according to the
786 : : step of the reference A. */
787 : :
788 : : static bool
789 : 959682 : suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
790 : : {
791 : 959682 : tree ref = DR_REF (a), step = DR_STEP (a);
792 : :
793 : 959682 : if (!step
794 : 863121 : || TREE_THIS_VOLATILE (ref)
795 : 849601 : || !is_gimple_reg_type (TREE_TYPE (ref))
796 : 1795151 : || tree_could_throw_p (ref))
797 : 160685 : return false;
798 : :
799 : 798997 : if (integer_zerop (step))
800 : 50788 : *ref_step = RS_INVARIANT;
801 : 748209 : else if (integer_nonzerop (step))
802 : 681855 : *ref_step = RS_NONZERO;
803 : : else
804 : 66354 : *ref_step = RS_ANY;
805 : :
806 : : return true;
807 : : }
808 : :
809 : : /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
810 : :
811 : : void
812 : 182228 : pcom_worker::aff_combination_dr_offset (struct data_reference *dr,
813 : : aff_tree *offset)
814 : : {
815 : 182228 : tree type = TREE_TYPE (DR_OFFSET (dr));
816 : 182228 : aff_tree delta;
817 : :
818 : 182228 : tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset, &m_cache);
819 : 182228 : aff_combination_const (&delta, type, wi::to_poly_widest (DR_INIT (dr)));
820 : 182228 : aff_combination_add (offset, &delta);
821 : 182228 : }
822 : :
823 : : /* Determines number of iterations of the innermost enclosing loop before B
824 : : refers to exactly the same location as A and stores it to OFF. If A and
825 : : B do not have the same step, they never meet, or anything else fails,
826 : : returns false, otherwise returns true. Both A and B are assumed to
827 : : satisfy suitable_reference_p. */
828 : :
829 : : bool
830 : 393292 : pcom_worker::determine_offset (struct data_reference *a,
831 : : struct data_reference *b, poly_widest_int *off)
832 : : {
833 : 1179876 : aff_tree diff, baseb, step;
834 : 393292 : tree typea, typeb;
835 : :
836 : : /* Check that both the references access the location in the same type. */
837 : 393292 : typea = TREE_TYPE (DR_REF (a));
838 : 393292 : typeb = TREE_TYPE (DR_REF (b));
839 : 393292 : if (!useless_type_conversion_p (typeb, typea))
840 : : return false;
841 : :
842 : : /* Check whether the base address and the step of both references is the
843 : : same. */
844 : 374845 : if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
845 : 374845 : || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
846 : 273865 : return false;
847 : :
848 : 100980 : if (integer_zerop (DR_STEP (a)))
849 : : {
850 : : /* If the references have loop invariant address, check that they access
851 : : exactly the same location. */
852 : 9886 : *off = 0;
853 : 9886 : return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
854 : 9886 : && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
855 : : }
856 : :
857 : : /* Compare the offsets of the addresses, and check whether the difference
858 : : is a multiple of step. */
859 : 91094 : aff_combination_dr_offset (a, &diff);
860 : 91094 : aff_combination_dr_offset (b, &baseb);
861 : 91094 : aff_combination_scale (&baseb, -1);
862 : 91094 : aff_combination_add (&diff, &baseb);
863 : :
864 : 91094 : tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
865 : : &step, &m_cache);
866 : 91094 : return aff_combination_constant_multiple_p (&diff, &step, off);
867 : 393292 : }
868 : :
869 : : /* Returns the last basic block in LOOP for that we are sure that
870 : : it is executed whenever the loop is entered. */
871 : :
872 : : static basic_block
873 : 207866 : last_always_executed_block (class loop *loop)
874 : : {
875 : 207866 : unsigned i;
876 : 207866 : auto_vec<edge> exits = get_loop_exit_edges (loop);
877 : 207866 : edge ex;
878 : 207866 : basic_block last = loop->latch;
879 : :
880 : 531977 : FOR_EACH_VEC_ELT (exits, i, ex)
881 : 324111 : last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
882 : :
883 : 207866 : return last;
884 : 207866 : }
885 : :
886 : : /* Splits dependence graph on DATAREFS described by DEPENDENCES to
887 : : components. */
888 : :
889 : : struct component *
890 : 207866 : pcom_worker::split_data_refs_to_components ()
891 : : {
892 : 207866 : unsigned i, n = m_datarefs.length ();
893 : 207866 : unsigned ca, ia, ib, bad;
894 : 207866 : struct data_reference *dr, *dra, *drb;
895 : 207866 : struct data_dependence_relation *ddr;
896 : 207866 : struct component *comp_list = NULL, *comp;
897 : 207866 : dref dataref;
898 : : /* Don't do store elimination if loop has multiple exit edges. */
899 : 207866 : bool eliminate_store_p = single_exit (m_loop) != NULL;
900 : 207866 : basic_block last_always_executed = last_always_executed_block (m_loop);
901 : 207866 : auto_bitmap no_store_store_comps;
902 : 207866 : auto_vec<unsigned> comp_father (n + 1);
903 : 207866 : auto_vec<unsigned> comp_size (n + 1);
904 : 207866 : comp_father.quick_grow (n + 1);
905 : 207866 : comp_size.quick_grow (n + 1);
906 : :
907 : 1028234 : FOR_EACH_VEC_ELT (m_datarefs, i, dr)
908 : : {
909 : 612658 : if (!DR_REF (dr))
910 : : /* A fake reference for call or asm_expr that may clobber memory;
911 : : just fail. */
912 : : return NULL;
913 : : /* predcom pass isn't prepared to handle calls with data references. */
914 : 612658 : if (is_gimple_call (DR_STMT (dr)))
915 : : return NULL;
916 : 612502 : dr->aux = (void *) (size_t) i;
917 : 612502 : comp_father[i] = i;
918 : 612502 : comp_size[i] = 1;
919 : : }
920 : :
921 : : /* A component reserved for the "bad" data references. */
922 : 207710 : comp_father[n] = n;
923 : 207710 : comp_size[n] = 1;
924 : :
925 : 819698 : FOR_EACH_VEC_ELT (m_datarefs, i, dr)
926 : : {
927 : 611988 : enum ref_step_type dummy;
928 : :
929 : 611988 : if (!suitable_reference_p (dr, &dummy))
930 : : {
931 : 160685 : ia = (unsigned) (size_t) dr->aux;
932 : 160685 : merge_comps (comp_father, comp_size, n, ia);
933 : : }
934 : : }
935 : :
936 : 8076126 : FOR_EACH_VEC_ELT (m_dependences, i, ddr)
937 : : {
938 : : poly_widest_int dummy_off;
939 : :
940 : 3934208 : if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
941 : 1812953 : continue;
942 : :
943 : 2121255 : dra = DDR_A (ddr);
944 : 2121255 : drb = DDR_B (ddr);
945 : :
946 : : /* Don't do store elimination if there is any unknown dependence for
947 : : any store data reference. */
948 : 1457850 : if ((DR_IS_WRITE (dra) || DR_IS_WRITE (drb))
949 : 2466271 : && (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
950 : 274706 : || DDR_NUM_DIST_VECTS (ddr) == 0))
951 : : eliminate_store_p = false;
952 : :
953 : 2121255 : ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
954 : 2121255 : ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
955 : 2121255 : if (ia == ib)
956 : 1577708 : continue;
957 : :
958 : 543547 : bad = component_of (comp_father, n);
959 : :
960 : : /* If both A and B are reads, we may ignore unsuitable dependences. */
961 : 543547 : if (DR_IS_READ (dra) && DR_IS_READ (drb))
962 : : {
963 : 306155 : if (ia == bad || ib == bad
964 : 622942 : || !determine_offset (dra, drb, &dummy_off))
965 : 311371 : continue;
966 : : }
967 : : /* If A is read and B write or vice versa and there is unsuitable
968 : : dependence, instead of merging both components into a component
969 : : that will certainly not pass suitable_component_p, just put the
970 : : read into bad component, perhaps at least the write together with
971 : : all the other data refs in it's component will be optimizable. */
972 : 211787 : else if (DR_IS_READ (dra) && ib != bad)
973 : : {
974 : 147435 : if (ia == bad)
975 : : {
976 : 97561 : bitmap_set_bit (no_store_store_comps, ib);
977 : 97561 : continue;
978 : : }
979 : 49874 : else if (!determine_offset (dra, drb, &dummy_off))
980 : : {
981 : 23504 : bitmap_set_bit (no_store_store_comps, ib);
982 : 23504 : merge_comps (comp_father, comp_size, bad, ia);
983 : 23504 : continue;
984 : : }
985 : : }
986 : 64352 : else if (DR_IS_READ (drb) && ia != bad)
987 : : {
988 : 21480 : if (ib == bad)
989 : : {
990 : 14625 : bitmap_set_bit (no_store_store_comps, ia);
991 : 14625 : continue;
992 : : }
993 : 6855 : else if (!determine_offset (dra, drb, &dummy_off))
994 : : {
995 : 3214 : bitmap_set_bit (no_store_store_comps, ia);
996 : 3214 : merge_comps (comp_father, comp_size, bad, ib);
997 : 3214 : continue;
998 : : }
999 : : }
1000 : 31278 : else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb)
1001 : 26137 : && ia != bad && ib != bad
1002 : 50232 : && !determine_offset (dra, drb, &dummy_off))
1003 : : {
1004 : 2123 : merge_comps (comp_father, comp_size, bad, ia);
1005 : 2123 : merge_comps (comp_father, comp_size, bad, ib);
1006 : 2123 : continue;
1007 : : }
1008 : :
1009 : 91149 : merge_comps (comp_father, comp_size, ia, ib);
1010 : 3934208 : }
1011 : :
1012 : 207710 : if (eliminate_store_p)
1013 : : {
1014 : 94656 : tree niters = number_of_latch_executions (m_loop);
1015 : :
1016 : : /* Don't do store elimination if niters info is unknown because stores
1017 : : in the last iteration can't be eliminated and we need to recover it
1018 : : after loop. */
1019 : 94656 : eliminate_store_p = (niters != NULL_TREE && niters != chrec_dont_know);
1020 : : }
1021 : :
1022 : 207710 : auto_vec<struct component *> comps;
1023 : 207710 : comps.safe_grow_cleared (n, true);
1024 : 207710 : bad = component_of (comp_father, n);
1025 : 1027408 : FOR_EACH_VEC_ELT (m_datarefs, i, dr)
1026 : : {
1027 : 611988 : ia = (unsigned) (size_t) dr->aux;
1028 : 611988 : ca = component_of (comp_father, ia);
1029 : 611988 : if (ca == bad)
1030 : 232613 : continue;
1031 : :
1032 : 379375 : comp = comps[ca];
1033 : 379375 : if (!comp)
1034 : : {
1035 : 329190 : comp = new component (eliminate_store_p);
1036 : 329190 : comp->refs.reserve_exact (comp_size[ca]);
1037 : 329190 : comps[ca] = comp;
1038 : : }
1039 : :
1040 : 379375 : dataref = XCNEW (class dref_d);
1041 : 379375 : dataref->ref = dr;
1042 : 379375 : dataref->stmt = DR_STMT (dr);
1043 : 379375 : dataref->offset = 0;
1044 : 379375 : dataref->distance = 0;
1045 : :
1046 : 379375 : dataref->always_accessed
1047 : 379375 : = dominated_by_p (CDI_DOMINATORS, last_always_executed,
1048 : 379375 : gimple_bb (dataref->stmt));
1049 : 379375 : dataref->pos = comp->refs.length ();
1050 : 379375 : comp->refs.quick_push (dataref);
1051 : : }
1052 : :
1053 : 207710 : if (eliminate_store_p)
1054 : : {
1055 : 80468 : bitmap_iterator bi;
1056 : 81078 : EXECUTE_IF_SET_IN_BITMAP (no_store_store_comps, 0, ia, bi)
1057 : : {
1058 : 610 : ca = component_of (comp_father, ia);
1059 : 610 : if (ca != bad)
1060 : 502 : comps[ca]->eliminate_store_p = false;
1061 : : }
1062 : : }
1063 : :
1064 : 819698 : for (i = 0; i < n; i++)
1065 : : {
1066 : 611988 : comp = comps[i];
1067 : 611988 : if (comp)
1068 : : {
1069 : 329190 : comp->next = comp_list;
1070 : 329190 : comp_list = comp;
1071 : : }
1072 : : }
1073 : 207710 : return comp_list;
1074 : 415576 : }
1075 : :
1076 : : /* Returns true if the component COMP satisfies the conditions
1077 : : described in 2) at the beginning of this file. */
1078 : :
1079 : : bool
1080 : 329190 : pcom_worker::suitable_component_p (struct component *comp)
1081 : : {
1082 : 329190 : unsigned i;
1083 : 329190 : dref a, first;
1084 : 329190 : basic_block ba, bp = m_loop->header;
1085 : 329190 : bool ok, has_write = false;
1086 : :
1087 : 678431 : FOR_EACH_VEC_ELT (comp->refs, i, a)
1088 : : {
1089 : 368758 : ba = gimple_bb (a->stmt);
1090 : :
1091 : 368758 : if (!just_once_each_iteration_p (m_loop, ba))
1092 : : return false;
1093 : :
1094 : 349241 : gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
1095 : 349241 : bp = ba;
1096 : :
1097 : 349241 : if (DR_IS_WRITE (a->ref))
1098 : 122511 : has_write = true;
1099 : : }
1100 : :
1101 : 309673 : first = comp->refs[0];
1102 : 309673 : ok = suitable_reference_p (first->ref, &comp->comp_step);
1103 : 309673 : gcc_assert (ok);
1104 : 309673 : first->offset = 0;
1105 : :
1106 : 657321 : FOR_EACH_VEC_ELT (comp->refs, i, a)
1107 : : {
1108 : 347694 : if (has_write && comp->comp_step == RS_NONZERO)
1109 : : {
1110 : : /* Punt for non-invariant references where step isn't a multiple
1111 : : of reference size. If step is smaller than reference size,
1112 : : it overlaps the access in next iteration, if step is larger,
1113 : : but not multiple of the access size, there could be overlap
1114 : : in some later iteration. There might be more latent issues
1115 : : about this in predcom or data reference analysis. If the
1116 : : reference is a COMPONENT_REF, also check if step isn't a
1117 : : multiple of the containg aggregate size. See PR111683. */
1118 : 123248 : tree ref = DR_REF (a->ref);
1119 : 123248 : tree step = DR_STEP (a->ref);
1120 : 123248 : if (TREE_CODE (ref) == COMPONENT_REF
1121 : 123248 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
1122 : 55 : ref = TREE_OPERAND (ref, 0);
1123 : 123320 : do
1124 : : {
1125 : 123284 : tree sz = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1126 : 123284 : if (TREE_CODE (sz) != INTEGER_CST)
1127 : 46 : return false;
1128 : 246568 : if (wi::multiple_of_p (wi::to_offset (step),
1129 : 246568 : wi::to_offset (sz), SIGNED))
1130 : : break;
1131 : 82 : if (TREE_CODE (ref) != COMPONENT_REF)
1132 : : return false;
1133 : 36 : ref = TREE_OPERAND (ref, 0);
1134 : 36 : }
1135 : : while (1);
1136 : : }
1137 : 347648 : if (i == 0)
1138 : 309627 : continue;
1139 : : /* Polynomial offsets are no use, since we need to know the
1140 : : gap between iteration numbers at compile time. */
1141 : : poly_widest_int offset;
1142 : 38021 : if (!determine_offset (first->ref, a->ref, &offset)
1143 : 38021 : || !offset.is_constant (&a->offset))
1144 : 0 : return false;
1145 : :
1146 : 38021 : enum ref_step_type a_step;
1147 : 38021 : gcc_checking_assert (suitable_reference_p (a->ref, &a_step)
1148 : : && a_step == comp->comp_step);
1149 : 38021 : }
1150 : :
1151 : : /* If there is a write inside the component, we must know whether the
1152 : : step is nonzero or not -- we would not otherwise be able to recognize
1153 : : whether the value accessed by reads comes from the OFFSET-th iteration
1154 : : or the previous one. */
1155 : 309627 : if (has_write && comp->comp_step == RS_ANY)
1156 : : return false;
1157 : :
1158 : : return true;
1159 : : }
1160 : :
1161 : : /* Check the conditions on references inside each of components COMPS,
1162 : : and remove the unsuitable components from the list. The new list
1163 : : of components is returned. The conditions are described in 2) at
1164 : : the beginning of this file. */
1165 : :
1166 : : struct component *
1167 : 140347 : pcom_worker::filter_suitable_components (struct component *comps)
1168 : : {
1169 : 140347 : struct component **comp, *act;
1170 : :
1171 : 469537 : for (comp = &comps; *comp; )
1172 : : {
1173 : 329190 : act = *comp;
1174 : 329190 : if (suitable_component_p (act))
1175 : 303903 : comp = &act->next;
1176 : : else
1177 : : {
1178 : 25287 : dref ref;
1179 : 25287 : unsigned i;
1180 : :
1181 : 25287 : *comp = act->next;
1182 : 64020 : FOR_EACH_VEC_ELT (act->refs, i, ref)
1183 : 38733 : free (ref);
1184 : 25287 : delete act;
1185 : : }
1186 : : }
1187 : :
1188 : 140347 : return comps;
1189 : : }
1190 : :
1191 : : /* Compares two drefs A and B by their offset and position. Callback for
1192 : : qsort. */
1193 : :
1194 : : static int
1195 : 168155 : order_drefs (const void *a, const void *b)
1196 : : {
1197 : 168155 : const dref *const da = (const dref *) a;
1198 : 168155 : const dref *const db = (const dref *) b;
1199 : 168155 : int offcmp = wi::cmps ((*da)->offset, (*db)->offset);
1200 : :
1201 : 168155 : if (offcmp != 0)
1202 : : return offcmp;
1203 : :
1204 : 95305 : return (*da)->pos - (*db)->pos;
1205 : : }
1206 : :
1207 : : /* Compares two drefs A and B by their position. Callback for qsort. */
1208 : :
1209 : : static int
1210 : 48 : order_drefs_by_pos (const void *a, const void *b)
1211 : : {
1212 : 48 : const dref *const da = (const dref *) a;
1213 : 48 : const dref *const db = (const dref *) b;
1214 : :
1215 : 48 : return (*da)->pos - (*db)->pos;
1216 : : }
1217 : :
1218 : : /* Returns root of the CHAIN. */
1219 : :
1220 : : static inline dref
1221 : 90688 : get_chain_root (chain_p chain)
1222 : : {
1223 : 181376 : return chain->refs[0];
1224 : : }
1225 : :
1226 : : /* Given CHAIN, returns the last write ref at DISTANCE, or NULL if it doesn't
1227 : : exist. */
1228 : :
1229 : : static inline dref
1230 : 85 : get_chain_last_write_at (chain_p chain, unsigned distance)
1231 : : {
1232 : 297 : for (unsigned i = chain->refs.length (); i > 0; i--)
1233 : 200 : if (DR_IS_WRITE (chain->refs[i - 1]->ref)
1234 : 200 : && distance == chain->refs[i - 1]->distance)
1235 : : return chain->refs[i - 1];
1236 : :
1237 : : return NULL;
1238 : : }
1239 : :
1240 : : /* Given CHAIN, returns the last write ref with the same distance before load
1241 : : at index LOAD_IDX, or NULL if it doesn't exist. */
1242 : :
1243 : : static inline dref
1244 : 5 : get_chain_last_write_before_load (chain_p chain, unsigned load_idx)
1245 : : {
1246 : 5 : gcc_assert (load_idx < chain->refs.length ());
1247 : :
1248 : 5 : unsigned distance = chain->refs[load_idx]->distance;
1249 : :
1250 : 5 : for (unsigned i = load_idx; i > 0; i--)
1251 : 5 : if (DR_IS_WRITE (chain->refs[i - 1]->ref)
1252 : 5 : && distance == chain->refs[i - 1]->distance)
1253 : : return chain->refs[i - 1];
1254 : :
1255 : : return NULL;
1256 : : }
1257 : :
1258 : : /* Adds REF to the chain CHAIN. */
1259 : :
1260 : : static void
1261 : 15735 : add_ref_to_chain (chain_p chain, dref ref)
1262 : : {
1263 : 15735 : dref root = get_chain_root (chain);
1264 : :
1265 : 15735 : gcc_assert (wi::les_p (root->offset, ref->offset));
1266 : 15735 : widest_int dist = ref->offset - root->offset;
1267 : 15735 : gcc_assert (wi::fits_uhwi_p (dist));
1268 : :
1269 : 15735 : chain->refs.safe_push (ref);
1270 : :
1271 : 15735 : ref->distance = dist.to_uhwi ();
1272 : :
1273 : 15735 : if (ref->distance >= chain->length)
1274 : : {
1275 : 15735 : chain->length = ref->distance;
1276 : 15735 : chain->has_max_use_after = false;
1277 : : }
1278 : :
1279 : : /* Promote this chain to CT_STORE_STORE if it has multiple stores. */
1280 : 15735 : if (DR_IS_WRITE (ref->ref))
1281 : 62 : chain->type = CT_STORE_STORE;
1282 : :
1283 : : /* Don't set the flag for store-store chain since there is no use. */
1284 : 15735 : if (chain->type != CT_STORE_STORE
1285 : 15671 : && ref->distance == chain->length
1286 : 15671 : && ref->pos > root->pos)
1287 : 7245 : chain->has_max_use_after = true;
1288 : :
1289 : 15735 : chain->all_always_accessed &= ref->always_accessed;
1290 : 15735 : }
1291 : :
1292 : : /* Returns the chain for invariant component COMP. */
1293 : :
1294 : : static chain_p
1295 : 12421 : make_invariant_chain (struct component *comp)
1296 : : {
1297 : 12421 : chain_p chain = new struct chain (CT_INVARIANT);
1298 : 12421 : unsigned i;
1299 : 12421 : dref ref;
1300 : :
1301 : 12421 : chain->all_always_accessed = true;
1302 : :
1303 : 26852 : FOR_EACH_VEC_ELT (comp->refs, i, ref)
1304 : : {
1305 : 14431 : chain->refs.safe_push (ref);
1306 : 14431 : chain->all_always_accessed &= ref->always_accessed;
1307 : : }
1308 : :
1309 : 12421 : chain->inits = vNULL;
1310 : 12421 : chain->finis = vNULL;
1311 : :
1312 : 12421 : return chain;
1313 : : }
1314 : :
1315 : : /* Make a new chain of type TYPE rooted at REF. */
1316 : :
1317 : : static chain_p
1318 : 48270 : make_rooted_chain (dref ref, enum chain_type type)
1319 : : {
1320 : 48270 : chain_p chain = new struct chain (type);
1321 : :
1322 : 48270 : chain->refs.safe_push (ref);
1323 : 48270 : chain->all_always_accessed = ref->always_accessed;
1324 : 48270 : ref->distance = 0;
1325 : :
1326 : 48270 : chain->inits = vNULL;
1327 : 48270 : chain->finis = vNULL;
1328 : :
1329 : 48270 : return chain;
1330 : : }
1331 : :
1332 : : /* Returns true if CHAIN is not trivial. */
1333 : :
1334 : : static bool
1335 : 77546 : nontrivial_chain_p (chain_p chain)
1336 : : {
1337 : 48270 : return chain != NULL && chain->refs.length () > 1;
1338 : : }
1339 : :
1340 : : /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1341 : : is no such name. */
1342 : :
1343 : : static tree
1344 : 116210 : name_for_ref (dref ref)
1345 : : {
1346 : 116210 : tree name;
1347 : :
1348 : 116210 : if (is_gimple_assign (ref->stmt))
1349 : : {
1350 : 116186 : if (!ref->ref || DR_IS_READ (ref->ref))
1351 : 116186 : name = gimple_assign_lhs (ref->stmt);
1352 : : else
1353 : 0 : name = gimple_assign_rhs1 (ref->stmt);
1354 : : }
1355 : : else
1356 : 24 : name = PHI_RESULT (ref->stmt);
1357 : :
1358 : 116210 : return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1359 : : }
1360 : :
1361 : : /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1362 : : iterations of the innermost enclosing loop). */
1363 : :
1364 : : bool
1365 : 20 : pcom_worker::valid_initializer_p (struct data_reference *ref, unsigned distance,
1366 : : struct data_reference *root)
1367 : : {
1368 : 80 : aff_tree diff, base, step;
1369 : : poly_widest_int off;
1370 : :
1371 : : /* Both REF and ROOT must be accessing the same object. */
1372 : 20 : if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1373 : : return false;
1374 : :
1375 : : /* The initializer is defined outside of loop, hence its address must be
1376 : : invariant inside the loop. */
1377 : 20 : gcc_assert (integer_zerop (DR_STEP (ref)));
1378 : :
1379 : : /* If the address of the reference is invariant, initializer must access
1380 : : exactly the same location. */
1381 : 20 : if (integer_zerop (DR_STEP (root)))
1382 : 0 : return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1383 : 0 : && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1384 : :
1385 : : /* Verify that this index of REF is equal to the root's index at
1386 : : -DISTANCE-th iteration. */
1387 : 20 : aff_combination_dr_offset (root, &diff);
1388 : 20 : aff_combination_dr_offset (ref, &base);
1389 : 20 : aff_combination_scale (&base, -1);
1390 : 20 : aff_combination_add (&diff, &base);
1391 : :
1392 : 20 : tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
1393 : : &step, &m_cache);
1394 : 20 : if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1395 : : return false;
1396 : :
1397 : 20 : if (maybe_ne (off, distance))
1398 : : return false;
1399 : :
1400 : : return true;
1401 : 20 : }
1402 : :
1403 : : /* Finds looparound phi node of loop that copies the value of REF, and if its
1404 : : initial value is correct (equal to initial value of REF shifted by one
1405 : : iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1406 : : is the root of the current chain. */
1407 : :
1408 : : gphi *
1409 : 31004 : pcom_worker::find_looparound_phi (dref ref, dref root)
1410 : : {
1411 : 31004 : tree name, init, init_ref;
1412 : 31004 : gimple *init_stmt;
1413 : 31004 : edge latch = loop_latch_edge (m_loop);
1414 : 31004 : struct data_reference init_dr;
1415 : 31004 : gphi_iterator psi;
1416 : :
1417 : 31004 : if (is_gimple_assign (ref->stmt))
1418 : : {
1419 : 30991 : if (DR_IS_READ (ref->ref))
1420 : 28796 : name = gimple_assign_lhs (ref->stmt);
1421 : : else
1422 : 2195 : name = gimple_assign_rhs1 (ref->stmt);
1423 : : }
1424 : : else
1425 : 13 : name = PHI_RESULT (ref->stmt);
1426 : 31004 : if (!name)
1427 : : return NULL;
1428 : :
1429 : 31004 : tree entry_vuse = NULL_TREE;
1430 : 31004 : gphi *phi = NULL;
1431 : 291046 : for (psi = gsi_start_phis (m_loop->header); !gsi_end_p (psi); gsi_next (&psi))
1432 : : {
1433 : 260066 : gphi *p = psi.phi ();
1434 : 260066 : if (PHI_ARG_DEF_FROM_EDGE (p, latch) == name)
1435 : : phi = p;
1436 : 520084 : else if (virtual_operand_p (gimple_phi_result (p)))
1437 : 21030 : entry_vuse = PHI_ARG_DEF_FROM_EDGE (p, loop_preheader_edge (m_loop));
1438 : 260066 : if (phi && entry_vuse)
1439 : : break;
1440 : : }
1441 : 31004 : if (!phi || !entry_vuse)
1442 : : return NULL;
1443 : :
1444 : 24 : init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (m_loop));
1445 : 24 : if (TREE_CODE (init) != SSA_NAME)
1446 : : return NULL;
1447 : 22 : init_stmt = SSA_NAME_DEF_STMT (init);
1448 : 22 : if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1449 : : return NULL;
1450 : 20 : gcc_assert (gimple_assign_lhs (init_stmt) == init);
1451 : :
1452 : 20 : init_ref = gimple_assign_rhs1 (init_stmt);
1453 : 20 : if (!REFERENCE_CLASS_P (init_ref)
1454 : 20 : && !DECL_P (init_ref))
1455 : : return NULL;
1456 : :
1457 : : /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1458 : : loop enclosing PHI). */
1459 : 20 : memset (&init_dr, 0, sizeof (struct data_reference));
1460 : 20 : DR_REF (&init_dr) = init_ref;
1461 : 20 : DR_STMT (&init_dr) = phi;
1462 : 20 : if (!dr_analyze_innermost (&DR_INNERMOST (&init_dr), init_ref, m_loop,
1463 : 20 : init_stmt))
1464 : : return NULL;
1465 : :
1466 : 20 : if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1467 : : return NULL;
1468 : :
1469 : : /* Make sure nothing clobbers the location we re-use the initial value
1470 : : from. */
1471 : 40 : if (entry_vuse != gimple_vuse (init_stmt))
1472 : : {
1473 : 7 : ao_ref ref;
1474 : 7 : ao_ref_init (&ref, init_ref);
1475 : 7 : unsigned limit = param_sccvn_max_alias_queries_per_access;
1476 : 7 : tree vdef = entry_vuse;
1477 : 7 : do
1478 : : {
1479 : 7 : gimple *def = SSA_NAME_DEF_STMT (vdef);
1480 : 7 : if (limit-- == 0 || gimple_code (def) == GIMPLE_PHI)
1481 : 7 : return NULL;
1482 : 7 : if (stmt_may_clobber_ref_p_1 (def, &ref))
1483 : : /* When the stmt is an assign to init_ref we could in theory
1484 : : use its RHS for the initial value of the looparound PHI
1485 : : we replace in prepare_initializers_chain, but we have
1486 : : no convenient place to store this info at the moment. */
1487 : : return NULL;
1488 : 0 : vdef = gimple_vuse (def);
1489 : : }
1490 : 0 : while (vdef != gimple_vuse (init_stmt));
1491 : : }
1492 : :
1493 : : return phi;
1494 : : }
1495 : :
1496 : : /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1497 : :
1498 : : static void
1499 : 13 : insert_looparound_copy (chain_p chain, dref ref, gphi *phi)
1500 : : {
1501 : 13 : dref nw = XCNEW (class dref_d), aref;
1502 : 13 : unsigned i;
1503 : :
1504 : 13 : nw->stmt = phi;
1505 : 13 : nw->distance = ref->distance + 1;
1506 : 13 : nw->always_accessed = 1;
1507 : :
1508 : 50 : FOR_EACH_VEC_ELT (chain->refs, i, aref)
1509 : 38 : if (aref->distance >= nw->distance)
1510 : : break;
1511 : 13 : chain->refs.safe_insert (i, nw);
1512 : :
1513 : 13 : if (nw->distance > chain->length)
1514 : : {
1515 : 12 : chain->length = nw->distance;
1516 : 12 : chain->has_max_use_after = false;
1517 : : }
1518 : 13 : }
1519 : :
1520 : : /* For references in CHAIN that are copied around the loop (created previously
1521 : : by PRE, or by user), add the results of such copies to the chain. This
1522 : : enables us to remove the copies by unrolling, and may need less registers
1523 : : (also, it may allow us to combine chains together). */
1524 : :
1525 : : void
1526 : 15372 : pcom_worker::add_looparound_copies (chain_p chain)
1527 : : {
1528 : 15372 : unsigned i;
1529 : 15372 : dref ref, root = get_chain_root (chain);
1530 : 15372 : gphi *phi;
1531 : :
1532 : 15372 : if (chain->type == CT_STORE_STORE)
1533 : 15372 : return;
1534 : :
1535 : 46327 : FOR_EACH_VEC_ELT (chain->refs, i, ref)
1536 : : {
1537 : 31004 : phi = find_looparound_phi (ref, root);
1538 : 31004 : if (!phi)
1539 : 30991 : continue;
1540 : :
1541 : 13 : bitmap_set_bit (m_looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1542 : 13 : insert_looparound_copy (chain, ref, phi);
1543 : : }
1544 : : }
1545 : :
1546 : : /* Find roots of the values and determine distances in the component COMP.
1547 : : The references are redistributed into chains. */
1548 : :
1549 : : void
1550 : 303903 : pcom_worker::determine_roots_comp (struct component *comp)
1551 : : {
1552 : 303903 : unsigned i;
1553 : 303903 : dref a;
1554 : 303903 : chain_p chain = NULL;
1555 : 303903 : widest_int last_ofs = 0;
1556 : 303903 : enum chain_type type;
1557 : :
1558 : : /* Invariants are handled specially. */
1559 : 303903 : if (comp->comp_step == RS_INVARIANT)
1560 : : {
1561 : 12421 : chain = make_invariant_chain (comp);
1562 : 12421 : m_chains.safe_push (chain);
1563 : 12421 : return;
1564 : : }
1565 : :
1566 : : /* Trivial component. */
1567 : 291482 : if (comp->refs.length () <= 1)
1568 : : {
1569 : 262206 : if (comp->refs.length () == 1)
1570 : : {
1571 : 262206 : free (comp->refs[0]);
1572 : 262206 : comp->refs.truncate (0);
1573 : : }
1574 : 262206 : return;
1575 : : }
1576 : :
1577 : 29276 : comp->refs.qsort (order_drefs);
1578 : :
1579 : : /* For Store-Store chain, we only support load if it is dominated by a
1580 : : store statement in the same iteration of loop. */
1581 : 29276 : if (comp->eliminate_store_p)
1582 : 33048 : for (a = NULL, i = 0; i < comp->refs.length (); i++)
1583 : : {
1584 : 16468 : if (DR_IS_WRITE (comp->refs[i]->ref))
1585 : : a = comp->refs[i];
1586 : 14905 : else if (a == NULL || a->offset != comp->refs[i]->offset)
1587 : : {
1588 : : /* If there is load that is not dominated by a store in the
1589 : : same iteration of loop, clear the flag so no Store-Store
1590 : : chain is generated for this component. */
1591 : 14892 : comp->eliminate_store_p = false;
1592 : 14892 : break;
1593 : : }
1594 : : }
1595 : :
1596 : : /* Determine roots and create chains for components. */
1597 : 93281 : FOR_EACH_VEC_ELT (comp->refs, i, a)
1598 : : {
1599 : 176280 : if (!chain
1600 : 34729 : || (chain->type == CT_LOAD && DR_IS_WRITE (a->ref))
1601 : 19760 : || (!comp->eliminate_store_p && DR_IS_WRITE (a->ref))
1602 : 162739 : || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
1603 : : {
1604 : 48270 : if (nontrivial_chain_p (chain))
1605 : : {
1606 : 905 : add_looparound_copies (chain);
1607 : 905 : m_chains.safe_push (chain);
1608 : : }
1609 : : else
1610 : 47365 : release_chain (chain);
1611 : :
1612 : : /* Determine type of the chain. If the root reference is a load,
1613 : : this can only be a CT_LOAD chain; other chains are intialized
1614 : : to CT_STORE_LOAD and might be promoted to CT_STORE_STORE when
1615 : : new reference is added. */
1616 : 48270 : type = DR_IS_READ (a->ref) ? CT_LOAD : CT_STORE_LOAD;
1617 : 48270 : chain = make_rooted_chain (a, type);
1618 : 48270 : last_ofs = a->offset;
1619 : 48270 : continue;
1620 : : }
1621 : :
1622 : 15735 : add_ref_to_chain (chain, a);
1623 : : }
1624 : :
1625 : 29276 : if (nontrivial_chain_p (chain))
1626 : : {
1627 : 14467 : add_looparound_copies (chain);
1628 : 14467 : m_chains.safe_push (chain);
1629 : : }
1630 : : else
1631 : 14809 : release_chain (chain);
1632 : 303903 : }
1633 : :
1634 : : /* Find roots of the values and determine distances in components COMPS, and
1635 : : separates the references to chains. */
1636 : :
1637 : : void
1638 : 140347 : pcom_worker::determine_roots (struct component *comps)
1639 : : {
1640 : 140347 : struct component *comp;
1641 : :
1642 : 444250 : for (comp = comps; comp; comp = comp->next)
1643 : 303903 : determine_roots_comp (comp);
1644 : 140347 : }
1645 : :
1646 : : /* Replace the reference in statement STMT with temporary variable
1647 : : NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1648 : : the reference in the statement. IN_LHS is true if the reference
1649 : : is in the lhs of STMT, false if it is in rhs. */
1650 : :
1651 : : static void
1652 : 33533 : replace_ref_with (gimple *stmt, tree new_tree, bool set, bool in_lhs)
1653 : : {
1654 : 33533 : tree val;
1655 : 33533 : gassign *new_stmt;
1656 : 33533 : gimple_stmt_iterator bsi, psi;
1657 : :
1658 : 33533 : if (gimple_code (stmt) == GIMPLE_PHI)
1659 : : {
1660 : 1 : gcc_assert (!in_lhs && !set);
1661 : :
1662 : 1 : val = PHI_RESULT (stmt);
1663 : 1 : bsi = gsi_after_labels (gimple_bb (stmt));
1664 : 1 : psi = gsi_for_stmt (stmt);
1665 : 1 : remove_phi_node (&psi, false);
1666 : :
1667 : : /* Turn the phi node into GIMPLE_ASSIGN. */
1668 : 1 : new_stmt = gimple_build_assign (val, new_tree);
1669 : 1 : gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1670 : 17094 : return;
1671 : : }
1672 : :
1673 : : /* Since the reference is of gimple_reg type, it should only
1674 : : appear as lhs or rhs of modify statement. */
1675 : 33532 : gcc_assert (is_gimple_assign (stmt));
1676 : :
1677 : 33532 : bsi = gsi_for_stmt (stmt);
1678 : :
1679 : : /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1680 : 33532 : if (!set)
1681 : : {
1682 : 17092 : gcc_assert (!in_lhs);
1683 : 17092 : gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1684 : 17092 : stmt = gsi_stmt (bsi);
1685 : 17092 : update_stmt (stmt);
1686 : 17092 : return;
1687 : : }
1688 : :
1689 : 16440 : if (in_lhs)
1690 : : {
1691 : : /* We have statement
1692 : :
1693 : : OLD = VAL
1694 : :
1695 : : If OLD is a memory reference, then VAL is gimple_val, and we transform
1696 : : this to
1697 : :
1698 : : OLD = VAL
1699 : : NEW = VAL
1700 : :
1701 : : Otherwise, we are replacing a combination chain,
1702 : : VAL is the expression that performs the combination, and OLD is an
1703 : : SSA name. In this case, we transform the assignment to
1704 : :
1705 : : OLD = VAL
1706 : : NEW = OLD
1707 : :
1708 : : */
1709 : :
1710 : 3659 : val = gimple_assign_lhs (stmt);
1711 : 3659 : if (TREE_CODE (val) != SSA_NAME)
1712 : : {
1713 : 3640 : val = gimple_assign_rhs1 (stmt);
1714 : 3640 : gcc_assert (gimple_assign_single_p (stmt));
1715 : 3640 : if (TREE_CLOBBER_P (val))
1716 : 0 : val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (new_tree));
1717 : : else
1718 : 3640 : gcc_assert (gimple_assign_copy_p (stmt));
1719 : : }
1720 : : }
1721 : : else
1722 : : {
1723 : : /* VAL = OLD
1724 : :
1725 : : is transformed to
1726 : :
1727 : : VAL = OLD
1728 : : NEW = VAL */
1729 : :
1730 : 12781 : val = gimple_assign_lhs (stmt);
1731 : : }
1732 : :
1733 : 16440 : new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1734 : 16440 : gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1735 : : }
1736 : :
1737 : : /* Returns a memory reference to DR in the (NITERS + ITER)-th iteration
1738 : : of the loop it was analyzed in. Append init stmts to STMTS. */
1739 : :
1740 : : static tree
1741 : 22113 : ref_at_iteration (data_reference_p dr, int iter,
1742 : : gimple_seq *stmts, tree niters = NULL_TREE)
1743 : : {
1744 : 22113 : tree off = DR_OFFSET (dr);
1745 : 22113 : tree coff = DR_INIT (dr);
1746 : 22113 : tree ref = DR_REF (dr);
1747 : 22113 : enum tree_code ref_code = ERROR_MARK;
1748 : 22113 : tree ref_type = NULL_TREE;
1749 : 22113 : tree ref_op1 = NULL_TREE;
1750 : 22113 : tree ref_op2 = NULL_TREE;
1751 : 22113 : tree new_offset;
1752 : :
1753 : 22113 : if (iter != 0)
1754 : : {
1755 : 22080 : new_offset = size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter));
1756 : 22080 : if (TREE_CODE (new_offset) == INTEGER_CST)
1757 : 22074 : coff = size_binop (PLUS_EXPR, coff, new_offset);
1758 : : else
1759 : 6 : off = size_binop (PLUS_EXPR, off, new_offset);
1760 : : }
1761 : :
1762 : 22113 : if (niters != NULL_TREE)
1763 : : {
1764 : 61 : niters = fold_convert (ssizetype, niters);
1765 : 61 : new_offset = size_binop (MULT_EXPR, DR_STEP (dr), niters);
1766 : 61 : if (TREE_CODE (niters) == INTEGER_CST)
1767 : 35 : coff = size_binop (PLUS_EXPR, coff, new_offset);
1768 : : else
1769 : 26 : off = size_binop (PLUS_EXPR, off, new_offset);
1770 : : }
1771 : :
1772 : : /* While data-ref analysis punts on bit offsets it still handles
1773 : : bitfield accesses at byte boundaries. Cope with that. Note that
1774 : : if the bitfield object also starts at a byte-boundary we can simply
1775 : : replicate the COMPONENT_REF, but we have to subtract the component's
1776 : : byte-offset from the MEM_REF address first.
1777 : : Otherwise we simply build a BIT_FIELD_REF knowing that the bits
1778 : : start at offset zero. */
1779 : 22113 : if (TREE_CODE (ref) == COMPONENT_REF
1780 : 22113 : && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
1781 : : {
1782 : 33 : unsigned HOST_WIDE_INT boff;
1783 : 33 : tree field = TREE_OPERAND (ref, 1);
1784 : 33 : tree offset = component_ref_field_offset (ref);
1785 : 33 : ref_type = TREE_TYPE (ref);
1786 : 33 : boff = tree_to_uhwi (DECL_FIELD_BIT_OFFSET (field));
1787 : : /* This can occur in Ada. See the comment in get_bit_range. */
1788 : 33 : if (boff % BITS_PER_UNIT != 0
1789 : 33 : || !tree_fits_uhwi_p (offset))
1790 : : {
1791 : 0 : ref_code = BIT_FIELD_REF;
1792 : 0 : ref_op1 = DECL_SIZE (field);
1793 : 0 : ref_op2 = bitsize_zero_node;
1794 : : }
1795 : : else
1796 : : {
1797 : 33 : boff >>= LOG2_BITS_PER_UNIT;
1798 : 33 : boff += tree_to_uhwi (offset);
1799 : 33 : coff = size_binop (MINUS_EXPR, coff, ssize_int (boff));
1800 : 33 : ref_code = COMPONENT_REF;
1801 : 33 : ref_op1 = field;
1802 : 33 : ref_op2 = TREE_OPERAND (ref, 2);
1803 : 33 : ref = TREE_OPERAND (ref, 0);
1804 : : }
1805 : : }
1806 : : /* We may not associate the constant offset across the pointer plus
1807 : : expression because that might form a pointer to before the object
1808 : : then. But for some cases we can retain that to allow tree_could_trap_p
1809 : : to return false - see gcc.dg/tree-ssa/predcom-1.c */
1810 : 22113 : tree addr, alias_ptr;
1811 : 22113 : if (integer_zerop (off))
1812 : : {
1813 : 21738 : alias_ptr = fold_convert (reference_alias_ptr_type (ref), coff);
1814 : 21738 : addr = DR_BASE_ADDRESS (dr);
1815 : : }
1816 : : else
1817 : : {
1818 : 375 : alias_ptr = build_zero_cst (reference_alias_ptr_type (ref));
1819 : 375 : off = size_binop (PLUS_EXPR, off, coff);
1820 : 375 : addr = fold_build_pointer_plus (DR_BASE_ADDRESS (dr), off);
1821 : : }
1822 : 22113 : addr = force_gimple_operand_1 (unshare_expr (addr), stmts,
1823 : : is_gimple_mem_ref_addr, NULL_TREE);
1824 : 22113 : tree type = build_aligned_type (TREE_TYPE (ref),
1825 : : get_object_alignment (ref));
1826 : 22113 : ref = build2 (MEM_REF, type, addr, alias_ptr);
1827 : 22113 : if (ref_type)
1828 : 33 : ref = build3 (ref_code, ref_type, ref, ref_op1, ref_op2);
1829 : 22113 : return ref;
1830 : : }
1831 : :
1832 : : /* Get the initialization expression for the INDEX-th temporary variable
1833 : : of CHAIN. */
1834 : :
1835 : : static tree
1836 : 9444 : get_init_expr (chain_p chain, unsigned index)
1837 : : {
1838 : 9444 : if (chain->type == CT_COMBINATION)
1839 : : {
1840 : 70 : tree e1 = get_init_expr (chain->ch1, index);
1841 : 70 : tree e2 = get_init_expr (chain->ch2, index);
1842 : :
1843 : 70 : return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1844 : : }
1845 : : else
1846 : 9374 : 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 : 17934 : predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1854 : : {
1855 : 17934 : tree type = TREE_TYPE (ref);
1856 : : /* We never access the components of the temporary variable in predictive
1857 : : commoning. */
1858 : 17934 : tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1859 : 17934 : bitmap_set_bit (tmp_vars, DECL_UID (var));
1860 : 17934 : 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 : 14986 : initialize_root_vars (class loop *loop, chain_p chain, bitmap tmp_vars)
1869 : : {
1870 : 14986 : unsigned i;
1871 : 14986 : unsigned n = chain->length;
1872 : 14986 : dref root = get_chain_root (chain);
1873 : 14986 : bool reuse_first = !chain->has_max_use_after;
1874 : 14986 : tree ref, init, var, next;
1875 : 14986 : gphi *phi;
1876 : 14986 : gimple_seq stmts;
1877 : 14986 : 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 : 14986 : gcc_assert (n > 0 || !reuse_first);
1882 : :
1883 : 14986 : chain->vars.create (n + 1);
1884 : :
1885 : 14986 : if (chain->type == CT_COMBINATION)
1886 : 19 : ref = gimple_assign_lhs (root->stmt);
1887 : : else
1888 : 14967 : ref = DR_REF (root->ref);
1889 : :
1890 : 46171 : for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1891 : : {
1892 : 16196 : var = predcom_tmp_var (ref, i, tmp_vars);
1893 : 16196 : chain->vars.quick_push (var);
1894 : : }
1895 : 14986 : if (reuse_first)
1896 : 8055 : chain->vars.quick_push (chain->vars[0]);
1897 : :
1898 : 39237 : FOR_EACH_VEC_ELT (chain->vars, i, var)
1899 : 24251 : chain->vars[i] = make_ssa_name (var);
1900 : :
1901 : 24251 : for (i = 0; i < n; i++)
1902 : : {
1903 : 9265 : var = chain->vars[i];
1904 : 9265 : next = chain->vars[i + 1];
1905 : 9265 : init = get_init_expr (chain, i);
1906 : :
1907 : 9265 : init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1908 : 9265 : if (stmts)
1909 : 9264 : gsi_insert_seq_on_edge_immediate (entry, stmts);
1910 : :
1911 : 9265 : phi = create_phi_node (var, loop->header);
1912 : 9265 : add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1913 : 9265 : add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1914 : : }
1915 : 14986 : }
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 : 33 : is_inv_store_elimination_chain (class loop *loop, chain_p chain)
1923 : : {
1924 : 33 : if (chain->length == 0 || chain->type != CT_STORE_STORE)
1925 : : return false;
1926 : :
1927 : 33 : 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 : 33 : tree niters = number_of_latch_executions (loop);
1932 : 33 : if (TREE_CODE (niters) != INTEGER_CST
1933 : 33 : || 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 : 44 : for (unsigned i = 0; i < chain->length; i++)
1939 : : {
1940 : 34 : dref a = get_chain_last_write_at (chain, i);
1941 : 34 : if (a == NULL)
1942 : 6 : continue;
1943 : :
1944 : 28 : gimple *def_stmt, *stmt = a->stmt;
1945 : 28 : if (!gimple_assign_single_p (stmt))
1946 : : return false;
1947 : :
1948 : 28 : tree val = gimple_assign_rhs1 (stmt);
1949 : 28 : if (TREE_CLOBBER_P (val))
1950 : : return false;
1951 : :
1952 : 28 : if (CONSTANT_CLASS_P (val))
1953 : 16 : 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 : 10 : initialize_root_vars_store_elim_1 (chain_p chain)
1974 : : {
1975 : 10 : tree var;
1976 : 10 : unsigned i, n = chain->length;
1977 : :
1978 : 10 : chain->vars.create (n);
1979 : 10 : chain->vars.safe_grow_cleared (n, true);
1980 : :
1981 : : /* Initialize root value for eliminated stores at each distance. */
1982 : 32 : for (i = 0; i < n; i++)
1983 : : {
1984 : 22 : dref a = get_chain_last_write_at (chain, i);
1985 : 22 : if (a == NULL)
1986 : 6 : continue;
1987 : :
1988 : 16 : var = gimple_assign_rhs1 (a->stmt);
1989 : 16 : 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 : 10 : var = chain->vars[0];
1995 : 22 : 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 : 17 : for (i = 0; i < n / 2; i++)
2007 : 7 : std::swap (chain->vars[i], chain->vars[n - i - 1]);
2008 : 10 : }
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 : 33 : finalize_eliminated_stores (class loop *loop, chain_p chain)
2102 : : {
2103 : 33 : unsigned i, n = chain->length;
2104 : :
2105 : 94 : for (i = 0; i < n; i++)
2106 : : {
2107 : 61 : tree var = chain->vars[i];
2108 : 61 : tree fini = chain->finis[n - i - 1];
2109 : 61 : gimple *stmt = gimple_build_assign (fini, var);
2110 : :
2111 : 61 : gimple_seq_add_stmt_without_update (&chain->fini_seq, stmt);
2112 : : }
2113 : :
2114 : 33 : if (chain->fini_seq)
2115 : : {
2116 : 33 : gsi_insert_seq_on_edge_immediate (single_exit (loop), chain->fini_seq);
2117 : 33 : chain->fini_seq = NULL;
2118 : : }
2119 : 33 : }
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 : 1699 : 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 : 1699 : unsigned i;
2134 : 1699 : tree ref = DR_REF (root->ref), init, var, next;
2135 : 1699 : gimple_seq stmts;
2136 : 1699 : gphi *phi;
2137 : 1699 : 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 : 1699 : init = inits[0];
2142 : :
2143 : 2024 : vars->create (written ? 2 : 1);
2144 : 1699 : var = predcom_tmp_var (ref, 0, tmp_vars);
2145 : 1699 : vars->quick_push (var);
2146 : 1699 : if (written)
2147 : 1374 : vars->quick_push ((*vars)[0]);
2148 : :
2149 : 4772 : FOR_EACH_VEC_ELT (*vars, i, var)
2150 : 3073 : (*vars)[i] = make_ssa_name (var);
2151 : :
2152 : 1699 : var = (*vars)[0];
2153 : :
2154 : 1699 : init = force_gimple_operand (init, &stmts, written, NULL_TREE);
2155 : 1699 : if (stmts)
2156 : 1374 : gsi_insert_seq_on_edge_immediate (entry, stmts);
2157 : :
2158 : 1699 : if (written)
2159 : : {
2160 : 1374 : next = (*vars)[1];
2161 : 1374 : phi = create_phi_node (var, loop->header);
2162 : 1374 : add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
2163 : 1374 : add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
2164 : : }
2165 : : else
2166 : : {
2167 : 325 : gassign *init_stmt = gimple_build_assign (var, init);
2168 : 325 : gsi_insert_on_edge_immediate (entry, init_stmt);
2169 : : }
2170 : 1699 : }
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 : 10667 : execute_load_motion (class loop *loop, chain_p chain, bitmap tmp_vars)
2178 : : {
2179 : 10667 : auto_vec<tree> vars;
2180 : 10667 : dref a;
2181 : 10667 : unsigned n_writes = 0, ridx, i;
2182 : 10667 : tree var;
2183 : :
2184 : 10667 : gcc_assert (chain->type == CT_INVARIANT);
2185 : 10667 : gcc_assert (!chain->combined);
2186 : 23071 : FOR_EACH_VEC_ELT (chain->refs, i, a)
2187 : 12404 : if (DR_IS_WRITE (a->ref))
2188 : 10627 : n_writes++;
2189 : :
2190 : : /* If there are no reads in the loop, there is nothing to do. */
2191 : 21334 : if (n_writes == chain->refs.length ())
2192 : 8968 : return;
2193 : :
2194 : 1699 : initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
2195 : : &vars, chain->inits, tmp_vars);
2196 : :
2197 : 1699 : ridx = 0;
2198 : 6629 : FOR_EACH_VEC_ELT (chain->refs, i, a)
2199 : : {
2200 : 3231 : bool is_read = DR_IS_READ (a->ref);
2201 : :
2202 : 3231 : if (DR_IS_WRITE (a->ref))
2203 : : {
2204 : 1454 : n_writes--;
2205 : 1454 : 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 : 3231 : replace_ref_with (a->stmt, vars[ridx],
2216 : 3231 : !is_read, !is_read);
2217 : : }
2218 : 10667 : }
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 : 63973 : pcom_worker::single_nonlooparound_use (tree name)
2226 : : {
2227 : 63973 : use_operand_p use;
2228 : 63973 : imm_use_iterator it;
2229 : 63973 : gimple *stmt, *ret = NULL;
2230 : :
2231 : 129025 : FOR_EACH_IMM_USE_FAST (use, it, name)
2232 : : {
2233 : 65608 : stmt = USE_STMT (use);
2234 : :
2235 : 65608 : 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 : 408 : if (bitmap_bit_p (m_looparound_phis,
2240 : 204 : SSA_NAME_VERSION (PHI_RESULT (stmt))))
2241 : 60 : continue;
2242 : :
2243 : : return NULL;
2244 : : }
2245 : 65404 : else if (is_gimple_debug (stmt))
2246 : 1227 : continue;
2247 : 64177 : 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 : 204 : pcom_worker::remove_stmt (gimple *stmt)
2261 : : {
2262 : 204 : tree name;
2263 : 204 : gimple *next;
2264 : 204 : gimple_stmt_iterator psi;
2265 : :
2266 : 204 : if (gimple_code (stmt) == GIMPLE_PHI)
2267 : : {
2268 : 12 : name = PHI_RESULT (stmt);
2269 : 12 : next = single_nonlooparound_use (name);
2270 : 12 : reset_debug_uses (stmt);
2271 : 12 : psi = gsi_for_stmt (stmt);
2272 : 12 : remove_phi_node (&psi, true);
2273 : :
2274 : 12 : if (!next
2275 : 11 : || !gimple_assign_ssa_name_copy_p (next)
2276 : 16 : || gimple_assign_rhs1 (next) != name)
2277 : 8 : return;
2278 : :
2279 : : stmt = next;
2280 : : }
2281 : :
2282 : 280 : while (1)
2283 : : {
2284 : 238 : gimple_stmt_iterator bsi;
2285 : :
2286 : 238 : bsi = gsi_for_stmt (stmt);
2287 : :
2288 : 238 : name = gimple_assign_lhs (stmt);
2289 : 238 : if (TREE_CODE (name) == SSA_NAME)
2290 : : {
2291 : 176 : next = single_nonlooparound_use (name);
2292 : 176 : reset_debug_uses (stmt);
2293 : : }
2294 : : else
2295 : : {
2296 : : /* This is a store to be eliminated. */
2297 : 124 : gcc_assert (gimple_vdef (stmt) != NULL);
2298 : : next = NULL;
2299 : : }
2300 : :
2301 : 238 : unlink_stmt_vdef (stmt);
2302 : 238 : gsi_remove (&bsi, true);
2303 : 238 : release_defs (stmt);
2304 : :
2305 : 238 : if (!next
2306 : 113 : || !gimple_assign_ssa_name_copy_p (next)
2307 : 280 : || gimple_assign_rhs1 (next) != name)
2308 : 196 : return;
2309 : :
2310 : 42 : stmt = next;
2311 : 42 : }
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 : 15111 : pcom_worker::execute_pred_commoning_chain (chain_p chain,
2319 : : bitmap tmp_vars)
2320 : : {
2321 : 15111 : unsigned i;
2322 : 15111 : dref a;
2323 : 15111 : tree var;
2324 : 15111 : bool in_lhs;
2325 : :
2326 : 15111 : 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 : 15035 : else if (chain->type == CT_STORE_STORE)
2333 : : {
2334 : 49 : if (chain->length > 0)
2335 : : {
2336 : 33 : 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 : 10 : 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 : 33 : finalize_eliminated_stores (m_loop, chain);
2356 : : }
2357 : :
2358 : 49 : bool last_store_p = true;
2359 : 214 : for (i = chain->refs.length (); i > 0; i--)
2360 : : {
2361 : 116 : 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 : 116 : if (DR_IS_WRITE (a->ref))
2365 : : {
2366 : 111 : if (last_store_p)
2367 : : last_store_p = false;
2368 : : else
2369 : 62 : remove_stmt (a->stmt);
2370 : :
2371 : 111 : 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 : 14986 : initialize_root_vars (m_loop, chain, tmp_vars);
2386 : 14986 : a = get_chain_root (chain);
2387 : 14986 : in_lhs = (chain->type == CT_STORE_LOAD
2388 : 14986 : || chain->type == CT_COMBINATION);
2389 : 14986 : 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 : 45283 : for (i = 1; chain->refs.iterate (i, &a); i++)
2393 : : {
2394 : 15311 : var = chain->vars[chain->length - a->distance];
2395 : 15311 : replace_ref_with (a->stmt, var, false, false);
2396 : : }
2397 : : }
2398 : 15111 : }
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 : 2971 : determine_unroll_factor (const vec<chain_p> &chains)
2406 : : {
2407 : 2971 : chain_p chain;
2408 : 2971 : unsigned factor = 1, af, nfactor, i;
2409 : 2971 : unsigned max = param_max_unroll_times;
2410 : :
2411 : 6921 : FOR_EACH_VEC_ELT (chains, i, chain)
2412 : : {
2413 : 3976 : if (chain->type == CT_INVARIANT)
2414 : 1703 : continue;
2415 : : /* For now we can't handle unrolling when eliminating stores. */
2416 : 2273 : else if (chain->type == CT_STORE_STORE)
2417 : : return 1;
2418 : :
2419 : 2250 : 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 : 155 : for (j = 1; chain->refs.iterate (j, &a); j++)
2426 : 97 : if (gimple_code (a->stmt) == GIMPLE_PHI)
2427 : 26 : 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 : 2189 : af = chain->length;
2434 : 2189 : if (chain->has_max_use_after)
2435 : 1317 : af++;
2436 : :
2437 : 2189 : nfactor = factor * af / gcd (factor, af);
2438 : 2189 : if (nfactor <= max)
2439 : 3950 : 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 : 14153 : pcom_worker::execute_pred_commoning (bitmap tmp_vars)
2450 : : {
2451 : 14153 : chain_p chain;
2452 : 14153 : unsigned i;
2453 : :
2454 : 39931 : FOR_EACH_VEC_ELT (m_chains, i, chain)
2455 : : {
2456 : 25778 : if (chain->type == CT_INVARIANT)
2457 : 10667 : execute_load_motion (m_loop, chain, tmp_vars);
2458 : : else
2459 : 15111 : execute_pred_commoning_chain (chain, tmp_vars);
2460 : : }
2461 : :
2462 : 39931 : FOR_EACH_VEC_ELT (m_chains, i, chain)
2463 : : {
2464 : 25778 : if (chain->type == CT_INVARIANT)
2465 : : ;
2466 : 15111 : 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 : 25996 : for (j = 1; chain->refs.iterate (j, &a); j++)
2473 : 142 : remove_stmt (a->stmt);
2474 : : }
2475 : : }
2476 : 14153 : }
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 : 591 : replace_phis_by_defined_names (vec<chain_p> &chains)
2483 : : {
2484 : 591 : chain_p chain;
2485 : 591 : dref a;
2486 : 591 : unsigned i, j;
2487 : :
2488 : 1869 : FOR_EACH_VEC_ELT (chains, i, chain)
2489 : 2618 : FOR_EACH_VEC_ELT (chain->refs, j, a)
2490 : : {
2491 : 1340 : 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 : 591 : }
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 : 591 : replace_names_by_phis (vec<chain_p> chains)
2504 : : {
2505 : 591 : chain_p chain;
2506 : 591 : dref a;
2507 : 591 : unsigned i, j;
2508 : :
2509 : 1869 : FOR_EACH_VEC_ELT (chains, i, chain)
2510 : 2618 : FOR_EACH_VEC_ELT (chain->refs, j, a)
2511 : 1340 : 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 : 591 : }
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 : 591 : execute_pred_commoning_cbck (class loop *loop ATTRIBUTE_UNUSED, void *data)
2531 : : {
2532 : 591 : struct epcc_data *const dta = (struct epcc_data *) data;
2533 : 591 : 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 : 591 : replace_names_by_phis (dta->chains);
2539 : 591 : worker->execute_pred_commoning (dta->tmp_vars);
2540 : 591 : }
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 : 641 : base_names_in_chain_on (class loop *loop, tree name, tree var)
2548 : : {
2549 : 641 : gimple *stmt, *phi;
2550 : 641 : imm_use_iterator iter;
2551 : :
2552 : 641 : replace_ssa_name_symbol (name, var);
2553 : :
2554 : 2063 : while (1)
2555 : : {
2556 : 1352 : phi = NULL;
2557 : 2000 : FOR_EACH_IMM_USE_STMT (stmt, iter, name)
2558 : : {
2559 : 1359 : if (gimple_code (stmt) == GIMPLE_PHI
2560 : 1359 : && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
2561 : : {
2562 : : phi = stmt;
2563 : : break;
2564 : : }
2565 : 1352 : }
2566 : 1352 : if (!phi)
2567 : 641 : return;
2568 : :
2569 : 711 : name = PHI_RESULT (phi);
2570 : 711 : replace_ssa_name_symbol (name, var);
2571 : 711 : }
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 : 591 : eliminate_temp_copies (class loop *loop, bitmap tmp_vars)
2581 : : {
2582 : 591 : edge e;
2583 : 591 : gphi *phi;
2584 : 591 : gimple *stmt;
2585 : 591 : tree name, use, var;
2586 : 591 : gphi_iterator psi;
2587 : :
2588 : 591 : e = loop_latch_edge (loop);
2589 : 3055 : for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
2590 : : {
2591 : 2464 : phi = psi.phi ();
2592 : 2464 : name = PHI_RESULT (phi);
2593 : 2464 : var = SSA_NAME_VAR (name);
2594 : 1590 : if (!var || !bitmap_bit_p (tmp_vars, DECL_UID (var)))
2595 : 1823 : continue;
2596 : 641 : use = PHI_ARG_DEF_FROM_EDGE (phi, e);
2597 : 641 : 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 : 641 : stmt = SSA_NAME_DEF_STMT (use);
2601 : 676 : 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 : 676 : && gimple_bb (stmt) != loop->header)
2608 : : {
2609 : 70 : gcc_assert (single_pred_p (gimple_bb (stmt)));
2610 : 35 : use = PHI_ARG_DEF (stmt, 0);
2611 : 35 : stmt = SSA_NAME_DEF_STMT (use);
2612 : : }
2613 : :
2614 : 641 : base_names_in_chain_on (loop, use, var);
2615 : : }
2616 : 591 : }
2617 : :
2618 : : /* Returns true if CHAIN is suitable to be combined. */
2619 : :
2620 : : static bool
2621 : 110201 : chain_can_be_combined_p (chain_p chain)
2622 : : {
2623 : 110201 : return (!chain->combined
2624 : 110035 : && (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 : 62142 : pcom_worker::find_use_stmt (tree *name)
2633 : : {
2634 : 63785 : gimple *stmt;
2635 : 63785 : tree rhs, lhs;
2636 : :
2637 : : /* Skip over assignments. */
2638 : 65428 : while (1)
2639 : : {
2640 : 63785 : stmt = single_nonlooparound_use (*name);
2641 : 63785 : if (!stmt)
2642 : : return NULL;
2643 : :
2644 : 63229 : if (gimple_code (stmt) != GIMPLE_ASSIGN)
2645 : : return NULL;
2646 : :
2647 : 62083 : lhs = gimple_assign_lhs (stmt);
2648 : 62083 : if (TREE_CODE (lhs) != SSA_NAME)
2649 : : return NULL;
2650 : :
2651 : 61969 : if (gimple_assign_copy_p (stmt))
2652 : : {
2653 : 1643 : rhs = gimple_assign_rhs1 (stmt);
2654 : 1643 : if (rhs != *name)
2655 : : return NULL;
2656 : :
2657 : 1643 : *name = lhs;
2658 : : }
2659 : 60326 : 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 : 1059 : may_reassociate_p (tree type, enum tree_code code)
2671 : : {
2672 : 658 : if (FLOAT_TYPE_P (type)
2673 : 1379 : && !flag_unsafe_math_optimizations)
2674 : : return false;
2675 : :
2676 : 741 : return (commutative_tree_code (code)
2677 : 741 : && 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 : 1059 : pcom_worker::find_associative_operation_root (gimple *stmt, unsigned *distance)
2686 : : {
2687 : 1059 : tree lhs;
2688 : 1059 : gimple *next;
2689 : 1059 : enum tree_code code = gimple_assign_rhs_code (stmt);
2690 : 1059 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2691 : 1059 : unsigned dist = 0;
2692 : :
2693 : 1059 : if (!may_reassociate_p (type, code))
2694 : : return NULL;
2695 : :
2696 : 4031 : while (1)
2697 : : {
2698 : 2353 : lhs = gimple_assign_lhs (stmt);
2699 : 2353 : gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2700 : :
2701 : 2353 : next = find_use_stmt (&lhs);
2702 : 2353 : if (!next
2703 : 2353 : || gimple_assign_rhs_code (next) != code)
2704 : : break;
2705 : :
2706 : 1678 : stmt = next;
2707 : 1678 : dist++;
2708 : : }
2709 : :
2710 : 675 : if (distance)
2711 : 196 : *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 : 57996 : pcom_worker::find_common_use_stmt (tree *name1, tree *name2)
2723 : : {
2724 : 57996 : gimple *stmt1, *stmt2;
2725 : :
2726 : 57996 : stmt1 = find_use_stmt (name1);
2727 : 57996 : if (!stmt1)
2728 : : return NULL;
2729 : :
2730 : 767 : stmt2 = find_use_stmt (name2);
2731 : 767 : if (!stmt2)
2732 : : return NULL;
2733 : :
2734 : 674 : if (stmt1 == stmt2)
2735 : : return stmt1;
2736 : :
2737 : 623 : stmt1 = find_associative_operation_root (stmt1, NULL);
2738 : 623 : if (!stmt1)
2739 : : return NULL;
2740 : 240 : stmt2 = find_associative_operation_root (stmt2, NULL);
2741 : 240 : if (!stmt2)
2742 : : return NULL;
2743 : :
2744 : 239 : 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 : 57996 : pcom_worker::combinable_refs_p (dref r1, dref r2,
2753 : : enum tree_code *code, bool *swap, tree *rslt_type)
2754 : : {
2755 : 57996 : enum tree_code acode;
2756 : 57996 : bool aswap;
2757 : 57996 : tree atype;
2758 : 57996 : tree name1, name2;
2759 : 57996 : gimple *stmt;
2760 : :
2761 : 57996 : name1 = name_for_ref (r1);
2762 : 57996 : name2 = name_for_ref (r2);
2763 : 57996 : gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2764 : :
2765 : 57996 : stmt = find_common_use_stmt (&name1, &name2);
2766 : :
2767 : 57996 : if (!stmt
2768 : : /* A simple post-dominance check - make sure the combination
2769 : : is executed under the same condition as the references. */
2770 : 57996 : || (gimple_bb (stmt) != gimple_bb (r1->stmt)
2771 : 20 : && gimple_bb (stmt) != gimple_bb (r2->stmt)))
2772 : : return false;
2773 : :
2774 : 135 : acode = gimple_assign_rhs_code (stmt);
2775 : 135 : aswap = (!commutative_tree_code (acode)
2776 : 135 : && gimple_assign_rhs1 (stmt) != name1);
2777 : 135 : atype = TREE_TYPE (gimple_assign_lhs (stmt));
2778 : :
2779 : 135 : if (*code == ERROR_MARK)
2780 : : {
2781 : 54 : *code = acode;
2782 : 54 : *swap = aswap;
2783 : 54 : *rslt_type = atype;
2784 : 54 : return true;
2785 : : }
2786 : :
2787 : 81 : return (*code == acode
2788 : 71 : && *swap == aswap
2789 : 152 : && *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 : 196 : remove_name_from_operation (gimple *stmt, tree op)
2797 : : {
2798 : 196 : tree other_op;
2799 : 196 : gimple_stmt_iterator si;
2800 : :
2801 : 196 : gcc_assert (is_gimple_assign (stmt));
2802 : :
2803 : 196 : if (gimple_assign_rhs1 (stmt) == op)
2804 : 82 : other_op = gimple_assign_rhs2 (stmt);
2805 : : else
2806 : : other_op = gimple_assign_rhs1 (stmt);
2807 : :
2808 : 196 : si = gsi_for_stmt (stmt);
2809 : 196 : gimple_assign_set_rhs_from_tree (&si, other_op);
2810 : :
2811 : : /* We should not have reallocated STMT. */
2812 : 196 : gcc_assert (gsi_stmt (si) == stmt);
2813 : :
2814 : 196 : update_stmt (stmt);
2815 : 196 : }
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 : 98 : pcom_worker::reassociate_to_the_same_stmt (tree name1, tree name2)
2822 : : {
2823 : 98 : gimple *stmt1, *stmt2, *root1, *root2, *s1, *s2;
2824 : 98 : gassign *new_stmt, *tmp_stmt;
2825 : 98 : tree new_name, tmp_name, var, r1, r2;
2826 : 98 : unsigned dist1, dist2;
2827 : 98 : enum tree_code code;
2828 : 98 : tree type = TREE_TYPE (name1);
2829 : 98 : gimple_stmt_iterator bsi;
2830 : :
2831 : 98 : stmt1 = find_use_stmt (&name1);
2832 : 98 : stmt2 = find_use_stmt (&name2);
2833 : 98 : root1 = find_associative_operation_root (stmt1, &dist1);
2834 : 98 : root2 = find_associative_operation_root (stmt2, &dist2);
2835 : 98 : code = gimple_assign_rhs_code (stmt1);
2836 : :
2837 : 98 : 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 : 98 : r1 = name1;
2843 : 98 : s1 = stmt1;
2844 : 98 : r2 = name2;
2845 : 98 : s2 = stmt2;
2846 : :
2847 : 388 : while (dist1 > dist2)
2848 : : {
2849 : 290 : s1 = find_use_stmt (&r1);
2850 : 290 : r1 = gimple_assign_lhs (s1);
2851 : 290 : dist1--;
2852 : : }
2853 : 216 : while (dist2 > dist1)
2854 : : {
2855 : 118 : s2 = find_use_stmt (&r2);
2856 : 118 : r2 = gimple_assign_lhs (s2);
2857 : 118 : dist2--;
2858 : : }
2859 : :
2860 : 200 : while (s1 != s2)
2861 : : {
2862 : 102 : s1 = find_use_stmt (&r1);
2863 : 102 : r1 = gimple_assign_lhs (s1);
2864 : 102 : s2 = find_use_stmt (&r2);
2865 : 102 : r2 = gimple_assign_lhs (s2);
2866 : : }
2867 : :
2868 : : /* Remove NAME1 and NAME2 from the statements in that they are used
2869 : : currently. */
2870 : 98 : remove_name_from_operation (stmt1, name1);
2871 : 98 : 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 : 98 : var = create_tmp_reg (type, "predreastmp");
2876 : 98 : new_name = make_ssa_name (var);
2877 : 98 : new_stmt = gimple_build_assign (new_name, code, name1, name2);
2878 : :
2879 : 98 : var = create_tmp_reg (type, "predreastmp");
2880 : 98 : 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 : 98 : tmp_stmt = gimple_build_assign (tmp_name, gimple_assign_rhs_code (s1),
2886 : : gimple_assign_rhs1 (s1),
2887 : : gimple_assign_rhs2 (s1));
2888 : :
2889 : 98 : bsi = gsi_for_stmt (s1);
2890 : 98 : gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2891 : 98 : s1 = gsi_stmt (bsi);
2892 : 98 : update_stmt (s1);
2893 : :
2894 : 98 : gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2895 : 98 : gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2896 : :
2897 : 98 : 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 : 109 : pcom_worker::stmt_combining_refs (dref r1, dref r2)
2907 : : {
2908 : 109 : gimple *stmt1, *stmt2;
2909 : 109 : tree name1 = name_for_ref (r1);
2910 : 109 : tree name2 = name_for_ref (r2);
2911 : :
2912 : 109 : stmt1 = find_use_stmt (&name1);
2913 : 109 : stmt2 = find_use_stmt (&name2);
2914 : 109 : if (stmt1 == stmt2)
2915 : : return stmt1;
2916 : :
2917 : 98 : 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 : 71009 : pcom_worker::combine_chains (chain_p ch1, chain_p ch2)
2925 : : {
2926 : 71009 : dref r1, r2, nw;
2927 : 71009 : enum tree_code op = ERROR_MARK;
2928 : 71009 : bool swap = false;
2929 : 71009 : chain_p new_chain;
2930 : 71009 : unsigned i;
2931 : 71009 : tree rslt_type = NULL_TREE;
2932 : :
2933 : 71009 : if (ch1 == ch2)
2934 : : return NULL;
2935 : 58209 : if (ch1->length != ch2->length)
2936 : : return NULL;
2937 : :
2938 : 174543 : if (ch1->refs.length () != ch2->refs.length ())
2939 : : return NULL;
2940 : :
2941 : 125 : for (i = 0; (ch1->refs.iterate (i, &r1)
2942 : 116030 : && ch2->refs.iterate (i, &r2)); i++)
2943 : : {
2944 : 57996 : if (r1->distance != r2->distance)
2945 : : return NULL;
2946 : :
2947 : 57996 : if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2948 : : return NULL;
2949 : : }
2950 : :
2951 : 38 : if (swap)
2952 : 1 : std::swap (ch1, ch2);
2953 : :
2954 : 38 : new_chain = new struct chain (CT_COMBINATION);
2955 : 38 : new_chain->op = op;
2956 : 38 : new_chain->ch1 = ch1;
2957 : 38 : new_chain->ch2 = ch2;
2958 : 38 : new_chain->rslt_type = rslt_type;
2959 : 38 : new_chain->length = ch1->length;
2960 : :
2961 : 147 : for (i = 0; (ch1->refs.iterate (i, &r1)
2962 : 256 : && ch2->refs.iterate (i, &r2)); i++)
2963 : : {
2964 : 109 : nw = XCNEW (class dref_d);
2965 : 109 : nw->stmt = stmt_combining_refs (r1, r2);
2966 : 109 : nw->distance = r1->distance;
2967 : :
2968 : 109 : new_chain->refs.safe_push (nw);
2969 : : }
2970 : :
2971 : 38 : ch1->combined = true;
2972 : 38 : ch2->combined = true;
2973 : 38 : 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 : 38 : update_pos_for_combined_chains (chain_p root)
2981 : : {
2982 : 38 : chain_p ch1 = root->ch1, ch2 = root->ch2;
2983 : 38 : dref ref, ref1, ref2;
2984 : 38 : for (unsigned j = 0; (root->refs.iterate (j, &ref)
2985 : 109 : && ch1->refs.iterate (j, &ref1)
2986 : 403 : && ch2->refs.iterate (j, &ref2)); ++j)
2987 : 109 : ref1->pos = ref2->pos = ref->pos;
2988 : :
2989 : 38 : if (ch1->type == CT_COMBINATION)
2990 : 19 : update_pos_for_combined_chains (ch1);
2991 : 38 : if (ch2->type == CT_COMBINATION)
2992 : : update_pos_for_combined_chains (ch2);
2993 : 38 : }
2994 : :
2995 : : /* Returns true if statement S1 dominates statement S2. */
2996 : :
2997 : : static bool
2998 : 15 : pcom_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
2999 : : {
3000 : 15 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
3001 : :
3002 : 15 : if (!bb1 || s1 == s2)
3003 : : return true;
3004 : :
3005 : 15 : if (bb1 == bb2)
3006 : 15 : 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 : 14153 : pcom_worker::try_combine_chains ()
3015 : : {
3016 : 14153 : unsigned i, j;
3017 : 14153 : chain_p ch1, ch2, cch;
3018 : 14153 : auto_vec<chain_p> worklist;
3019 : 14153 : bool combined_p = false;
3020 : :
3021 : 39893 : FOR_EACH_VEC_ELT (m_chains, i, ch1)
3022 : 51480 : if (chain_can_be_combined_p (ch1))
3023 : 12838 : worklist.safe_push (ch1);
3024 : :
3025 : 54058 : while (!worklist.is_empty ())
3026 : : {
3027 : 12876 : ch1 = worklist.pop ();
3028 : 12876 : if (!chain_can_be_combined_p (ch1))
3029 : 38 : continue;
3030 : :
3031 : 111414 : FOR_EACH_VEC_ELT (m_chains, j, ch2)
3032 : : {
3033 : 71585 : if (!chain_can_be_combined_p (ch2))
3034 : 576 : continue;
3035 : :
3036 : 71009 : cch = combine_chains (ch1, ch2);
3037 : 71009 : if (cch)
3038 : : {
3039 : 38 : worklist.safe_push (cch);
3040 : 38 : m_chains.safe_push (cch);
3041 : 38 : combined_p = true;
3042 : 38 : break;
3043 : : }
3044 : : }
3045 : : }
3046 : 14153 : if (!combined_p)
3047 : 14139 : return;
3048 : :
3049 : : /* Setup UID for all statements in dominance order. */
3050 : 14 : basic_block *bbs = get_loop_body_in_dom_order (m_loop);
3051 : 14 : renumber_gimple_stmt_uids_in_blocks (bbs, m_loop->num_nodes);
3052 : 14 : 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 : 14 : dref ref;
3064 : 114 : for (i = 0; m_chains.iterate (i, &ch1); ++i)
3065 : : {
3066 : 100 : if (ch1->type != CT_COMBINATION || ch1->combined)
3067 : 81 : continue;
3068 : :
3069 : 70 : for (j = 0; ch1->refs.iterate (j, &ref); ++j)
3070 : 51 : ref->pos = gimple_uid (ref->stmt);
3071 : :
3072 : 19 : update_pos_for_combined_chains (ch1);
3073 : : }
3074 : : /* Then sort references according to newly updated position information. */
3075 : 128 : for (i = 0; m_chains.iterate (i, &ch1); ++i)
3076 : : {
3077 : 100 : if (ch1->type != CT_COMBINATION && !ch1->combined)
3078 : 5 : continue;
3079 : :
3080 : : /* Find the first reference with non-ZERO distance. */
3081 : 95 : if (ch1->length == 0)
3082 : 107 : j = ch1->refs.length();
3083 : : else
3084 : : {
3085 : 166 : for (j = 0; ch1->refs.iterate (j, &ref); ++j)
3086 : 166 : if (ref->distance != 0)
3087 : : break;
3088 : : }
3089 : :
3090 : : /* Sort all ZERO distance references by position. */
3091 : 95 : qsort (&ch1->refs[0], j, sizeof (ch1->refs[0]), order_drefs_by_pos);
3092 : :
3093 : 95 : if (ch1->combined)
3094 : 76 : continue;
3095 : :
3096 : : /* For ZERO length chain, has_max_use_after must be true since root
3097 : : combined stmt must dominates others. */
3098 : 19 : 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 : 15 : ch1->has_max_use_after = false;
3106 : 15 : gimple *root_stmt = get_chain_root (ch1)->stmt;
3107 : 140 : for (j = 1; ch1->refs.iterate (j, &ref); ++j)
3108 : : {
3109 : 28 : if (ref->distance == ch1->length
3110 : 28 : && !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 : 14153 : }
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 : 49 : prepare_initializers_chain_store_elim (class loop *loop, chain_p chain)
3125 : : {
3126 : 49 : unsigned i, n = chain->length;
3127 : :
3128 : : /* For now we can't eliminate stores if some of them are conditional
3129 : : executed. */
3130 : 49 : if (!chain->all_always_accessed)
3131 : : return false;
3132 : :
3133 : : /* Nothing to intialize for intra-iteration store elimination. */
3134 : 49 : 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 : 33 : if (chain->type == CT_STORE_STORE
3140 : 33 : && is_inv_store_elimination_chain (loop, chain))
3141 : : {
3142 : 10 : chain->inv_store_elimination = true;
3143 : 10 : 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 : 177 : 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 : 27793 : pcom_worker::prepare_initializers_chain (chain_p chain)
3192 : : {
3193 : 27793 : unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
3194 : 27793 : struct data_reference *dr = get_chain_root (chain)->ref;
3195 : 27793 : tree init;
3196 : 27793 : dref laref;
3197 : 27793 : edge entry = loop_preheader_edge (m_loop);
3198 : :
3199 : 27793 : if (chain->type == CT_STORE_STORE)
3200 : 49 : 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 : 27744 : chain->inits.create (n);
3205 : 77543 : for (i = 0; i < n; i++)
3206 : 22055 : 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 : 73179 : FOR_EACH_VEC_ELT (chain->refs, i, laref)
3211 : : {
3212 : 45435 : if (gimple_code (laref->stmt) != GIMPLE_PHI)
3213 : 45422 : continue;
3214 : :
3215 : 13 : gcc_assert (laref->distance > 0);
3216 : 13 : chain->inits[n - laref->distance]
3217 : 26 : = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
3218 : : }
3219 : :
3220 : 47746 : for (i = 0; i < n; i++)
3221 : : {
3222 : 22055 : gimple_seq stmts = NULL;
3223 : :
3224 : 22055 : if (chain->inits[i] != NULL_TREE)
3225 : 13 : continue;
3226 : :
3227 : 22042 : init = ref_at_iteration (dr, (int) i - n, &stmts);
3228 : 22042 : if (!chain->all_always_accessed && tree_could_trap_p (init))
3229 : : {
3230 : 2053 : gimple_seq_discard (stmts);
3231 : 2053 : return false;
3232 : : }
3233 : :
3234 : 19989 : if (stmts)
3235 : 1106 : gimple_seq_add_seq_without_update (&chain->init_seq, stmts);
3236 : :
3237 : 19989 : 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 : 14153 : pcom_worker::prepare_initializers ()
3248 : : {
3249 : 14153 : chain_p chain;
3250 : 14153 : unsigned i;
3251 : :
3252 : 83892 : for (i = 0; i < m_chains.length (); )
3253 : : {
3254 : 27793 : chain = m_chains[i];
3255 : 27793 : if (prepare_initializers_chain (chain))
3256 : 25740 : i++;
3257 : : else
3258 : : {
3259 : 2053 : release_chain (chain);
3260 : 2053 : m_chains.unordered_remove (i);
3261 : : }
3262 : : }
3263 : 14153 : }
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 : 33 : pcom_worker::prepare_finalizers_chain (chain_p chain)
3270 : : {
3271 : 33 : unsigned i, n = chain->length;
3272 : 33 : struct data_reference *dr = get_chain_root (chain)->ref;
3273 : 33 : 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 : 33 : if (!chain->all_always_accessed)
3278 : : return false;
3279 : :
3280 : 33 : chain->finis.create (n);
3281 : 127 : for (i = 0; i < n; i++)
3282 : 61 : 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 : 94 : for (i = 0; i < n; i++)
3289 : : {
3290 : 61 : gimple_seq stmts = NULL;
3291 : 61 : gcc_assert (chain->finis[i] == NULL_TREE);
3292 : :
3293 : 61 : 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 : 61 : fini = ref_at_iteration (dr, (int) 0 - i, &stmts, niters);
3304 : 61 : if (stmts)
3305 : 26 : gimple_seq_add_seq_without_update (&chain->fini_seq, stmts);
3306 : :
3307 : 61 : 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 : 14153 : pcom_worker::prepare_finalizers ()
3318 : : {
3319 : 14153 : chain_p chain;
3320 : 14153 : unsigned i;
3321 : 14153 : bool loop_closed_ssa = false;
3322 : :
3323 : 79786 : for (i = 0; i < m_chains.length ();)
3324 : : {
3325 : 25740 : chain = m_chains[i];
3326 : :
3327 : : /* Finalizer is only necessary for inter-iteration store elimination
3328 : : chains. */
3329 : 25740 : if (chain->length == 0 || chain->type != CT_STORE_STORE)
3330 : : {
3331 : 25707 : i++;
3332 : 25707 : continue;
3333 : : }
3334 : :
3335 : 33 : if (prepare_finalizers_chain (chain))
3336 : : {
3337 : 33 : 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 : 33 : loop_closed_ssa = true;
3343 : : }
3344 : : else
3345 : : {
3346 : 0 : release_chain (chain);
3347 : 0 : m_chains.unordered_remove (i);
3348 : : }
3349 : : }
3350 : 14153 : return loop_closed_ssa;
3351 : : }
3352 : :
3353 : : /* Insert all initializing gimple stmts into LOOP's entry edge. */
3354 : :
3355 : : static void
3356 : 14153 : insert_init_seqs (class loop *loop, vec<chain_p> &chains)
3357 : : {
3358 : 14153 : unsigned i;
3359 : 14153 : edge entry = loop_preheader_edge (loop);
3360 : :
3361 : 94015 : for (i = 0; i < chains.length (); ++i)
3362 : 25778 : if (chains[i]->init_seq)
3363 : : {
3364 : 1070 : gsi_insert_seq_on_edge_immediate (entry, chains[i]->init_seq);
3365 : 1070 : chains[i]->init_seq = NULL;
3366 : : }
3367 : 14153 : }
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 : 362052 : pcom_worker::tree_predictive_commoning_loop (bool allow_unroll_p)
3376 : : {
3377 : 362052 : struct component *components;
3378 : 362052 : unsigned unroll_factor = 0;
3379 : 362052 : class tree_niter_desc desc;
3380 : 362052 : bool unroll = false, loop_closed_ssa = false;
3381 : :
3382 : 362052 : 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 : 362052 : if (get_max_loop_iterations_int (m_loop) == 0)
3387 : : {
3388 : 19876 : if (dump_file && (dump_flags & TDF_DETAILS))
3389 : 1 : fprintf (dump_file, "Loop iterates only 1 time, nothing to do.\n");
3390 : :
3391 : 19876 : return 0;
3392 : : }
3393 : :
3394 : : /* Find the data references and split them into components according to their
3395 : : dependence relations. */
3396 : 342176 : auto_vec<loop_p, 3> loop_nest;
3397 : 342176 : if (!compute_data_dependences_for_loop (m_loop, true, &loop_nest, &m_datarefs,
3398 : : &m_dependences))
3399 : : {
3400 : 134310 : if (dump_file && (dump_flags & TDF_DETAILS))
3401 : 0 : fprintf (dump_file, "Cannot analyze data dependencies\n");
3402 : 134310 : return 0;
3403 : : }
3404 : :
3405 : 207866 : if (dump_file && (dump_flags & TDF_DETAILS))
3406 : 55 : dump_data_dependence_relations (dump_file, m_dependences);
3407 : :
3408 : 207866 : components = split_data_refs_to_components ();
3409 : :
3410 : 207866 : loop_nest.release ();
3411 : 207866 : if (!components)
3412 : : return 0;
3413 : :
3414 : 140347 : 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 : 140347 : components = filter_suitable_components (components);
3422 : :
3423 : 140347 : auto_bitmap tmp_vars;
3424 : 140347 : determine_roots (components);
3425 : 140347 : release_components (components);
3426 : :
3427 : 140347 : if (!m_chains.exists ())
3428 : : {
3429 : 126194 : if (dump_file && (dump_flags & TDF_DETAILS))
3430 : 20 : fprintf (dump_file,
3431 : : "Predictive commoning failed: no suitable chains\n");
3432 : 126194 : return 0;
3433 : : }
3434 : :
3435 : 14153 : prepare_initializers ();
3436 : 14153 : loop_closed_ssa = prepare_finalizers ();
3437 : :
3438 : : /* Try to combine the chains that are always worked with together. */
3439 : 14153 : try_combine_chains ();
3440 : :
3441 : 14153 : insert_init_seqs (m_loop, m_chains);
3442 : :
3443 : 14153 : 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 : 14153 : 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 : 2971 : unroll_factor = determine_unroll_factor (m_chains);
3453 : :
3454 : 2971 : if (unroll_factor > 1)
3455 : 604 : unroll = can_unroll_loop_p (m_loop, unroll_factor, &desc);
3456 : :
3457 : : /* Execute the predictive commoning transformations, and possibly unroll the
3458 : : loop. */
3459 : 604 : if (unroll)
3460 : : {
3461 : 591 : struct epcc_data dta;
3462 : :
3463 : 591 : if (dump_file && (dump_flags & TDF_DETAILS))
3464 : 9 : fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
3465 : :
3466 : 591 : dta.tmp_vars = tmp_vars;
3467 : 591 : dta.chains = m_chains.to_vec_legacy ();
3468 : 591 : 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 : 591 : replace_phis_by_defined_names (m_chains);
3477 : :
3478 : 591 : tree_transform_and_unroll_loop (m_loop, unroll_factor, &desc,
3479 : : execute_pred_commoning_cbck, &dta);
3480 : 591 : eliminate_temp_copies (m_loop, tmp_vars);
3481 : : }
3482 : : else
3483 : : {
3484 : 13562 : if (dump_file && (dump_flags & TDF_DETAILS))
3485 : 25 : fprintf (dump_file,
3486 : : "Executing predictive commoning without unrolling.\n");
3487 : 13562 : execute_pred_commoning (tmp_vars);
3488 : : }
3489 : :
3490 : 41836 : return (unroll ? 2 : 1) | (loop_closed_ssa ? 4 : 1);
3491 : 482523 : }
3492 : :
3493 : : /* Runs predictive commoning. */
3494 : :
3495 : : unsigned
3496 : 190067 : tree_predictive_commoning (bool allow_unroll_p)
3497 : : {
3498 : 190067 : unsigned ret = 0, changed = 0;
3499 : :
3500 : 190067 : initialize_original_copy_tables ();
3501 : 952063 : for (auto loop : loops_list (cfun, LI_ONLY_INNERMOST))
3502 : 381862 : if (optimize_loop_for_speed_p (loop))
3503 : : {
3504 : 362052 : pcom_worker w(loop);
3505 : 362052 : changed |= w.tree_predictive_commoning_loop (allow_unroll_p);
3506 : 362052 : }
3507 : 190067 : free_original_copy_tables ();
3508 : :
3509 : 190067 : if (changed > 0)
3510 : : {
3511 : 9528 : ret = TODO_update_ssa_only_virtuals;
3512 : :
3513 : : /* Some loop(s) got unrolled. */
3514 : 9528 : if (changed > 1)
3515 : : {
3516 : 545 : scev_reset ();
3517 : :
3518 : : /* Need to fix up loop closed SSA. */
3519 : 545 : if (changed >= 4)
3520 : 32 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3521 : :
3522 : : ret |= TODO_cleanup_cfg;
3523 : : }
3524 : : }
3525 : :
3526 : : if (ret != 0)
3527 : 9528 : cfun->pending_TODOs |= PENDING_TODO_force_next_scalar_cleanup;
3528 : :
3529 : 190067 : return ret;
3530 : : }
3531 : :
3532 : : /* Predictive commoning Pass. */
3533 : :
3534 : : static unsigned
3535 : 190067 : run_tree_predictive_commoning (struct function *fun, bool allow_unroll_p)
3536 : : {
3537 : 380134 : if (number_of_loops (fun) <= 1)
3538 : : return 0;
3539 : :
3540 : 190067 : 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 : 273196 : pass_predcom (gcc::context *ctxt)
3562 : 546392 : : gimple_opt_pass (pass_data_predcom, ctxt)
3563 : : {}
3564 : :
3565 : : /* opt_pass methods: */
3566 : : bool
3567 : 221759 : gate (function *) final override
3568 : : {
3569 : 221759 : 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 : 197039 : if (flag_tree_loop_vectorize
3575 : 165348 : && !OPTION_SET_P (flag_predictive_commoning))
3576 : 165348 : return true;
3577 : :
3578 : : return false;
3579 : : }
3580 : :
3581 : : unsigned int
3582 : 190067 : execute (function *fun) final override
3583 : : {
3584 : 190067 : bool allow_unroll_p = flag_predictive_commoning != 0;
3585 : 190067 : 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 : 273196 : make_pass_predcom (gcc::context *ctxt)
3594 : : {
3595 : 273196 : return new pass_predcom (ctxt);
3596 : : }
|
