]> git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/tree-predcom.c
gimple.h: Remove all includes.
[thirdparty/gcc.git] / gcc / tree-predcom.c
1 /* Predictive commoning.
2 Copyright (C) 2005-2013 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 TODO -- stores killing other stores can be taken into account, e.g.,
160 for (i = 0; i < n; i++)
161 {
162 a[i] = 1;
163 a[i+2] = 2;
164 }
165
166 can be replaced with
167
168 t0 = a[0];
169 t1 = a[1];
170 for (i = 0; i < n; i++)
171 {
172 a[i] = 1;
173 t2 = 2;
174 t0 = t1;
175 t1 = t2;
176 }
177 a[n] = t0;
178 a[n+1] = t1;
179
180 The interesting part is that this would generalize store motion; still, since
181 sm is performed elsewhere, it does not seem that important.
182
183 Predictive commoning can be generalized for arbitrary computations (not
184 just memory loads), and also nontrivial transfer functions (e.g., replacing
185 i * i with ii_last + 2 * i + 1), to generalize strength reduction. */
186
187 #include "config.h"
188 #include "system.h"
189 #include "coretypes.h"
190 #include "tm.h"
191 #include "tree.h"
192 #include "tm_p.h"
193 #include "cfgloop.h"
194 #include "basic-block.h"
195 #include "tree-ssa-alias.h"
196 #include "internal-fn.h"
197 #include "tree-eh.h"
198 #include "gimple-expr.h"
199 #include "is-a.h"
200 #include "gimple.h"
201 #include "gimplify.h"
202 #include "gimple-iterator.h"
203 #include "gimplify-me.h"
204 #include "gimple-ssa.h"
205 #include "tree-phinodes.h"
206 #include "ssa-iterators.h"
207 #include "stringpool.h"
208 #include "tree-ssanames.h"
209 #include "tree-ssa-loop-ivopts.h"
210 #include "tree-ssa-loop-manip.h"
211 #include "tree-ssa-loop-niter.h"
212 #include "tree-ssa-loop.h"
213 #include "tree-into-ssa.h"
214 #include "expr.h"
215 #include "tree-dfa.h"
216 #include "tree-ssa.h"
217 #include "tree-data-ref.h"
218 #include "tree-scalar-evolution.h"
219 #include "tree-chrec.h"
220 #include "params.h"
221 #include "gimple-pretty-print.h"
222 #include "tree-pass.h"
223 #include "tree-affine.h"
224 #include "tree-inline.h"
225
226 /* The maximum number of iterations between the considered memory
227 references. */
228
229 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
230
231 /* Data references (or phi nodes that carry data reference values across
232 loop iterations). */
233
234 typedef struct dref_d
235 {
236 /* The reference itself. */
237 struct data_reference *ref;
238
239 /* The statement in that the reference appears. */
240 gimple stmt;
241
242 /* In case that STMT is a phi node, this field is set to the SSA name
243 defined by it in replace_phis_by_defined_names (in order to avoid
244 pointing to phi node that got reallocated in the meantime). */
245 tree name_defined_by_phi;
246
247 /* Distance of the reference from the root of the chain (in number of
248 iterations of the loop). */
249 unsigned distance;
250
251 /* Number of iterations offset from the first reference in the component. */
252 double_int offset;
253
254 /* Number of the reference in a component, in dominance ordering. */
255 unsigned pos;
256
257 /* True if the memory reference is always accessed when the loop is
258 entered. */
259 unsigned always_accessed : 1;
260 } *dref;
261
262
263 /* Type of the chain of the references. */
264
265 enum chain_type
266 {
267 /* The addresses of the references in the chain are constant. */
268 CT_INVARIANT,
269
270 /* There are only loads in the chain. */
271 CT_LOAD,
272
273 /* Root of the chain is store, the rest are loads. */
274 CT_STORE_LOAD,
275
276 /* A combination of two chains. */
277 CT_COMBINATION
278 };
279
280 /* Chains of data references. */
281
282 typedef struct chain
283 {
284 /* Type of the chain. */
285 enum chain_type type;
286
287 /* For combination chains, the operator and the two chains that are
288 combined, and the type of the result. */
289 enum tree_code op;
290 tree rslt_type;
291 struct chain *ch1, *ch2;
292
293 /* The references in the chain. */
294 vec<dref> refs;
295
296 /* The maximum distance of the reference in the chain from the root. */
297 unsigned length;
298
299 /* The variables used to copy the value throughout iterations. */
300 vec<tree> vars;
301
302 /* Initializers for the variables. */
303 vec<tree> inits;
304
305 /* True if there is a use of a variable with the maximal distance
306 that comes after the root in the loop. */
307 unsigned has_max_use_after : 1;
308
309 /* True if all the memory references in the chain are always accessed. */
310 unsigned all_always_accessed : 1;
311
312 /* True if this chain was combined together with some other chain. */
313 unsigned combined : 1;
314 } *chain_p;
315
316
317 /* Describes the knowledge about the step of the memory references in
318 the component. */
319
320 enum ref_step_type
321 {
322 /* The step is zero. */
323 RS_INVARIANT,
324
325 /* The step is nonzero. */
326 RS_NONZERO,
327
328 /* The step may or may not be nonzero. */
329 RS_ANY
330 };
331
332 /* Components of the data dependence graph. */
333
334 struct component
335 {
336 /* The references in the component. */
337 vec<dref> refs;
338
339 /* What we know about the step of the references in the component. */
340 enum ref_step_type comp_step;
341
342 /* Next component in the list. */
343 struct component *next;
344 };
345
346 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
347
348 static bitmap looparound_phis;
349
350 /* Cache used by tree_to_aff_combination_expand. */
351
352 static struct pointer_map_t *name_expansions;
353
354 /* Dumps data reference REF to FILE. */
355
356 extern void dump_dref (FILE *, dref);
357 void
358 dump_dref (FILE *file, dref ref)
359 {
360 if (ref->ref)
361 {
362 fprintf (file, " ");
363 print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
364 fprintf (file, " (id %u%s)\n", ref->pos,
365 DR_IS_READ (ref->ref) ? "" : ", write");
366
367 fprintf (file, " offset ");
368 dump_double_int (file, ref->offset, false);
369 fprintf (file, "\n");
370
371 fprintf (file, " distance %u\n", ref->distance);
372 }
373 else
374 {
375 if (gimple_code (ref->stmt) == GIMPLE_PHI)
376 fprintf (file, " looparound ref\n");
377 else
378 fprintf (file, " combination ref\n");
379 fprintf (file, " in statement ");
380 print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
381 fprintf (file, "\n");
382 fprintf (file, " distance %u\n", ref->distance);
383 }
384
385 }
386
387 /* Dumps CHAIN to FILE. */
388
389 extern void dump_chain (FILE *, chain_p);
390 void
391 dump_chain (FILE *file, chain_p chain)
392 {
393 dref a;
394 const char *chain_type;
395 unsigned i;
396 tree var;
397
398 switch (chain->type)
399 {
400 case CT_INVARIANT:
401 chain_type = "Load motion";
402 break;
403
404 case CT_LOAD:
405 chain_type = "Loads-only";
406 break;
407
408 case CT_STORE_LOAD:
409 chain_type = "Store-loads";
410 break;
411
412 case CT_COMBINATION:
413 chain_type = "Combination";
414 break;
415
416 default:
417 gcc_unreachable ();
418 }
419
420 fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
421 chain->combined ? " (combined)" : "");
422 if (chain->type != CT_INVARIANT)
423 fprintf (file, " max distance %u%s\n", chain->length,
424 chain->has_max_use_after ? "" : ", may reuse first");
425
426 if (chain->type == CT_COMBINATION)
427 {
428 fprintf (file, " equal to %p %s %p in type ",
429 (void *) chain->ch1, op_symbol_code (chain->op),
430 (void *) chain->ch2);
431 print_generic_expr (file, chain->rslt_type, TDF_SLIM);
432 fprintf (file, "\n");
433 }
434
435 if (chain->vars.exists ())
436 {
437 fprintf (file, " vars");
438 FOR_EACH_VEC_ELT (chain->vars, i, var)
439 {
440 fprintf (file, " ");
441 print_generic_expr (file, var, TDF_SLIM);
442 }
443 fprintf (file, "\n");
444 }
445
446 if (chain->inits.exists ())
447 {
448 fprintf (file, " inits");
449 FOR_EACH_VEC_ELT (chain->inits, i, var)
450 {
451 fprintf (file, " ");
452 print_generic_expr (file, var, TDF_SLIM);
453 }
454 fprintf (file, "\n");
455 }
456
457 fprintf (file, " references:\n");
458 FOR_EACH_VEC_ELT (chain->refs, i, a)
459 dump_dref (file, a);
460
461 fprintf (file, "\n");
462 }
463
464 /* Dumps CHAINS to FILE. */
465
466 extern void dump_chains (FILE *, vec<chain_p> );
467 void
468 dump_chains (FILE *file, vec<chain_p> chains)
469 {
470 chain_p chain;
471 unsigned i;
472
473 FOR_EACH_VEC_ELT (chains, i, chain)
474 dump_chain (file, chain);
475 }
476
477 /* Dumps COMP to FILE. */
478
479 extern void dump_component (FILE *, struct component *);
480 void
481 dump_component (FILE *file, struct component *comp)
482 {
483 dref a;
484 unsigned i;
485
486 fprintf (file, "Component%s:\n",
487 comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
488 FOR_EACH_VEC_ELT (comp->refs, i, a)
489 dump_dref (file, a);
490 fprintf (file, "\n");
491 }
492
493 /* Dumps COMPS to FILE. */
494
495 extern void dump_components (FILE *, struct component *);
496 void
497 dump_components (FILE *file, struct component *comps)
498 {
499 struct component *comp;
500
501 for (comp = comps; comp; comp = comp->next)
502 dump_component (file, comp);
503 }
504
505 /* Frees a chain CHAIN. */
506
507 static void
508 release_chain (chain_p chain)
509 {
510 dref ref;
511 unsigned i;
512
513 if (chain == NULL)
514 return;
515
516 FOR_EACH_VEC_ELT (chain->refs, i, ref)
517 free (ref);
518
519 chain->refs.release ();
520 chain->vars.release ();
521 chain->inits.release ();
522
523 free (chain);
524 }
525
526 /* Frees CHAINS. */
527
528 static void
529 release_chains (vec<chain_p> chains)
530 {
531 unsigned i;
532 chain_p chain;
533
534 FOR_EACH_VEC_ELT (chains, i, chain)
535 release_chain (chain);
536 chains.release ();
537 }
538
539 /* Frees a component COMP. */
540
541 static void
542 release_component (struct component *comp)
543 {
544 comp->refs.release ();
545 free (comp);
546 }
547
548 /* Frees list of components COMPS. */
549
550 static void
551 release_components (struct component *comps)
552 {
553 struct component *act, *next;
554
555 for (act = comps; act; act = next)
556 {
557 next = act->next;
558 release_component (act);
559 }
560 }
561
562 /* Finds a root of tree given by FATHERS containing A, and performs path
563 shortening. */
564
565 static unsigned
566 component_of (unsigned fathers[], unsigned a)
567 {
568 unsigned root, n;
569
570 for (root = a; root != fathers[root]; root = fathers[root])
571 continue;
572
573 for (; a != root; a = n)
574 {
575 n = fathers[a];
576 fathers[a] = root;
577 }
578
579 return root;
580 }
581
582 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
583 components, A and B are components to merge. */
584
585 static void
586 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)
587 {
588 unsigned ca = component_of (fathers, a);
589 unsigned cb = component_of (fathers, b);
590
591 if (ca == cb)
592 return;
593
594 if (sizes[ca] < sizes[cb])
595 {
596 sizes[cb] += sizes[ca];
597 fathers[ca] = cb;
598 }
599 else
600 {
601 sizes[ca] += sizes[cb];
602 fathers[cb] = ca;
603 }
604 }
605
606 /* Returns true if A is a reference that is suitable for predictive commoning
607 in the innermost loop that contains it. REF_STEP is set according to the
608 step of the reference A. */
609
610 static bool
611 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
612 {
613 tree ref = DR_REF (a), step = DR_STEP (a);
614
615 if (!step
616 || TREE_THIS_VOLATILE (ref)
617 || !is_gimple_reg_type (TREE_TYPE (ref))
618 || tree_could_throw_p (ref))
619 return false;
620
621 if (integer_zerop (step))
622 *ref_step = RS_INVARIANT;
623 else if (integer_nonzerop (step))
624 *ref_step = RS_NONZERO;
625 else
626 *ref_step = RS_ANY;
627
628 return true;
629 }
630
631 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
632
633 static void
634 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)
635 {
636 tree type = TREE_TYPE (DR_OFFSET (dr));
637 aff_tree delta;
638
639 tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset,
640 &name_expansions);
641 aff_combination_const (&delta, type, tree_to_double_int (DR_INIT (dr)));
642 aff_combination_add (offset, &delta);
643 }
644
645 /* Determines number of iterations of the innermost enclosing loop before B
646 refers to exactly the same location as A and stores it to OFF. If A and
647 B do not have the same step, they never meet, or anything else fails,
648 returns false, otherwise returns true. Both A and B are assumed to
649 satisfy suitable_reference_p. */
650
651 static bool
652 determine_offset (struct data_reference *a, struct data_reference *b,
653 double_int *off)
654 {
655 aff_tree diff, baseb, step;
656 tree typea, typeb;
657
658 /* Check that both the references access the location in the same type. */
659 typea = TREE_TYPE (DR_REF (a));
660 typeb = TREE_TYPE (DR_REF (b));
661 if (!useless_type_conversion_p (typeb, typea))
662 return false;
663
664 /* Check whether the base address and the step of both references is the
665 same. */
666 if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
667 || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
668 return false;
669
670 if (integer_zerop (DR_STEP (a)))
671 {
672 /* If the references have loop invariant address, check that they access
673 exactly the same location. */
674 *off = double_int_zero;
675 return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
676 && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
677 }
678
679 /* Compare the offsets of the addresses, and check whether the difference
680 is a multiple of step. */
681 aff_combination_dr_offset (a, &diff);
682 aff_combination_dr_offset (b, &baseb);
683 aff_combination_scale (&baseb, double_int_minus_one);
684 aff_combination_add (&diff, &baseb);
685
686 tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
687 &step, &name_expansions);
688 return aff_combination_constant_multiple_p (&diff, &step, off);
689 }
690
691 /* Returns the last basic block in LOOP for that we are sure that
692 it is executed whenever the loop is entered. */
693
694 static basic_block
695 last_always_executed_block (struct loop *loop)
696 {
697 unsigned i;
698 vec<edge> exits = get_loop_exit_edges (loop);
699 edge ex;
700 basic_block last = loop->latch;
701
702 FOR_EACH_VEC_ELT (exits, i, ex)
703 last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
704 exits.release ();
705
706 return last;
707 }
708
709 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
710
711 static struct component *
712 split_data_refs_to_components (struct loop *loop,
713 vec<data_reference_p> datarefs,
714 vec<ddr_p> depends)
715 {
716 unsigned i, n = datarefs.length ();
717 unsigned ca, ia, ib, bad;
718 unsigned *comp_father = XNEWVEC (unsigned, n + 1);
719 unsigned *comp_size = XNEWVEC (unsigned, n + 1);
720 struct component **comps;
721 struct data_reference *dr, *dra, *drb;
722 struct data_dependence_relation *ddr;
723 struct component *comp_list = NULL, *comp;
724 dref dataref;
725 basic_block last_always_executed = last_always_executed_block (loop);
726
727 FOR_EACH_VEC_ELT (datarefs, i, dr)
728 {
729 if (!DR_REF (dr))
730 {
731 /* A fake reference for call or asm_expr that may clobber memory;
732 just fail. */
733 goto end;
734 }
735 dr->aux = (void *) (size_t) i;
736 comp_father[i] = i;
737 comp_size[i] = 1;
738 }
739
740 /* A component reserved for the "bad" data references. */
741 comp_father[n] = n;
742 comp_size[n] = 1;
743
744 FOR_EACH_VEC_ELT (datarefs, i, dr)
745 {
746 enum ref_step_type dummy;
747
748 if (!suitable_reference_p (dr, &dummy))
749 {
750 ia = (unsigned) (size_t) dr->aux;
751 merge_comps (comp_father, comp_size, n, ia);
752 }
753 }
754
755 FOR_EACH_VEC_ELT (depends, i, ddr)
756 {
757 double_int dummy_off;
758
759 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
760 continue;
761
762 dra = DDR_A (ddr);
763 drb = DDR_B (ddr);
764 ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
765 ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
766 if (ia == ib)
767 continue;
768
769 bad = component_of (comp_father, n);
770
771 /* If both A and B are reads, we may ignore unsuitable dependences. */
772 if (DR_IS_READ (dra) && DR_IS_READ (drb)
773 && (ia == bad || ib == bad
774 || !determine_offset (dra, drb, &dummy_off)))
775 continue;
776
777 merge_comps (comp_father, comp_size, ia, ib);
778 }
779
780 comps = XCNEWVEC (struct component *, n);
781 bad = component_of (comp_father, n);
782 FOR_EACH_VEC_ELT (datarefs, i, dr)
783 {
784 ia = (unsigned) (size_t) dr->aux;
785 ca = component_of (comp_father, ia);
786 if (ca == bad)
787 continue;
788
789 comp = comps[ca];
790 if (!comp)
791 {
792 comp = XCNEW (struct component);
793 comp->refs.create (comp_size[ca]);
794 comps[ca] = comp;
795 }
796
797 dataref = XCNEW (struct dref_d);
798 dataref->ref = dr;
799 dataref->stmt = DR_STMT (dr);
800 dataref->offset = double_int_zero;
801 dataref->distance = 0;
802
803 dataref->always_accessed
804 = dominated_by_p (CDI_DOMINATORS, last_always_executed,
805 gimple_bb (dataref->stmt));
806 dataref->pos = comp->refs.length ();
807 comp->refs.quick_push (dataref);
808 }
809
810 for (i = 0; i < n; i++)
811 {
812 comp = comps[i];
813 if (comp)
814 {
815 comp->next = comp_list;
816 comp_list = comp;
817 }
818 }
819 free (comps);
820
821 end:
822 free (comp_father);
823 free (comp_size);
824 return comp_list;
825 }
826
827 /* Returns true if the component COMP satisfies the conditions
828 described in 2) at the beginning of this file. LOOP is the current
829 loop. */
830
831 static bool
832 suitable_component_p (struct loop *loop, struct component *comp)
833 {
834 unsigned i;
835 dref a, first;
836 basic_block ba, bp = loop->header;
837 bool ok, has_write = false;
838
839 FOR_EACH_VEC_ELT (comp->refs, i, a)
840 {
841 ba = gimple_bb (a->stmt);
842
843 if (!just_once_each_iteration_p (loop, ba))
844 return false;
845
846 gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
847 bp = ba;
848
849 if (DR_IS_WRITE (a->ref))
850 has_write = true;
851 }
852
853 first = comp->refs[0];
854 ok = suitable_reference_p (first->ref, &comp->comp_step);
855 gcc_assert (ok);
856 first->offset = double_int_zero;
857
858 for (i = 1; comp->refs.iterate (i, &a); i++)
859 {
860 if (!determine_offset (first->ref, a->ref, &a->offset))
861 return false;
862
863 #ifdef ENABLE_CHECKING
864 {
865 enum ref_step_type a_step;
866 ok = suitable_reference_p (a->ref, &a_step);
867 gcc_assert (ok && a_step == comp->comp_step);
868 }
869 #endif
870 }
871
872 /* If there is a write inside the component, we must know whether the
873 step is nonzero or not -- we would not otherwise be able to recognize
874 whether the value accessed by reads comes from the OFFSET-th iteration
875 or the previous one. */
876 if (has_write && comp->comp_step == RS_ANY)
877 return false;
878
879 return true;
880 }
881
882 /* Check the conditions on references inside each of components COMPS,
883 and remove the unsuitable components from the list. The new list
884 of components is returned. The conditions are described in 2) at
885 the beginning of this file. LOOP is the current loop. */
886
887 static struct component *
888 filter_suitable_components (struct loop *loop, struct component *comps)
889 {
890 struct component **comp, *act;
891
892 for (comp = &comps; *comp; )
893 {
894 act = *comp;
895 if (suitable_component_p (loop, act))
896 comp = &act->next;
897 else
898 {
899 dref ref;
900 unsigned i;
901
902 *comp = act->next;
903 FOR_EACH_VEC_ELT (act->refs, i, ref)
904 free (ref);
905 release_component (act);
906 }
907 }
908
909 return comps;
910 }
911
912 /* Compares two drefs A and B by their offset and position. Callback for
913 qsort. */
914
915 static int
916 order_drefs (const void *a, const void *b)
917 {
918 const dref *const da = (const dref *) a;
919 const dref *const db = (const dref *) b;
920 int offcmp = (*da)->offset.scmp ((*db)->offset);
921
922 if (offcmp != 0)
923 return offcmp;
924
925 return (*da)->pos - (*db)->pos;
926 }
927
928 /* Returns root of the CHAIN. */
929
930 static inline dref
931 get_chain_root (chain_p chain)
932 {
933 return chain->refs[0];
934 }
935
936 /* Adds REF to the chain CHAIN. */
937
938 static void
939 add_ref_to_chain (chain_p chain, dref ref)
940 {
941 dref root = get_chain_root (chain);
942 double_int dist;
943
944 gcc_assert (root->offset.sle (ref->offset));
945 dist = ref->offset - root->offset;
946 if (double_int::from_uhwi (MAX_DISTANCE).ule (dist))
947 {
948 free (ref);
949 return;
950 }
951 gcc_assert (dist.fits_uhwi ());
952
953 chain->refs.safe_push (ref);
954
955 ref->distance = dist.to_uhwi ();
956
957 if (ref->distance >= chain->length)
958 {
959 chain->length = ref->distance;
960 chain->has_max_use_after = false;
961 }
962
963 if (ref->distance == chain->length
964 && ref->pos > root->pos)
965 chain->has_max_use_after = true;
966
967 chain->all_always_accessed &= ref->always_accessed;
968 }
969
970 /* Returns the chain for invariant component COMP. */
971
972 static chain_p
973 make_invariant_chain (struct component *comp)
974 {
975 chain_p chain = XCNEW (struct chain);
976 unsigned i;
977 dref ref;
978
979 chain->type = CT_INVARIANT;
980
981 chain->all_always_accessed = true;
982
983 FOR_EACH_VEC_ELT (comp->refs, i, ref)
984 {
985 chain->refs.safe_push (ref);
986 chain->all_always_accessed &= ref->always_accessed;
987 }
988
989 return chain;
990 }
991
992 /* Make a new chain rooted at REF. */
993
994 static chain_p
995 make_rooted_chain (dref ref)
996 {
997 chain_p chain = XCNEW (struct chain);
998
999 chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
1000
1001 chain->refs.safe_push (ref);
1002 chain->all_always_accessed = ref->always_accessed;
1003
1004 ref->distance = 0;
1005
1006 return chain;
1007 }
1008
1009 /* Returns true if CHAIN is not trivial. */
1010
1011 static bool
1012 nontrivial_chain_p (chain_p chain)
1013 {
1014 return chain != NULL && chain->refs.length () > 1;
1015 }
1016
1017 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1018 is no such name. */
1019
1020 static tree
1021 name_for_ref (dref ref)
1022 {
1023 tree name;
1024
1025 if (is_gimple_assign (ref->stmt))
1026 {
1027 if (!ref->ref || DR_IS_READ (ref->ref))
1028 name = gimple_assign_lhs (ref->stmt);
1029 else
1030 name = gimple_assign_rhs1 (ref->stmt);
1031 }
1032 else
1033 name = PHI_RESULT (ref->stmt);
1034
1035 return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1036 }
1037
1038 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1039 iterations of the innermost enclosing loop). */
1040
1041 static bool
1042 valid_initializer_p (struct data_reference *ref,
1043 unsigned distance, struct data_reference *root)
1044 {
1045 aff_tree diff, base, step;
1046 double_int off;
1047
1048 /* Both REF and ROOT must be accessing the same object. */
1049 if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1050 return false;
1051
1052 /* The initializer is defined outside of loop, hence its address must be
1053 invariant inside the loop. */
1054 gcc_assert (integer_zerop (DR_STEP (ref)));
1055
1056 /* If the address of the reference is invariant, initializer must access
1057 exactly the same location. */
1058 if (integer_zerop (DR_STEP (root)))
1059 return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1060 && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1061
1062 /* Verify that this index of REF is equal to the root's index at
1063 -DISTANCE-th iteration. */
1064 aff_combination_dr_offset (root, &diff);
1065 aff_combination_dr_offset (ref, &base);
1066 aff_combination_scale (&base, double_int_minus_one);
1067 aff_combination_add (&diff, &base);
1068
1069 tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
1070 &step, &name_expansions);
1071 if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1072 return false;
1073
1074 if (off != double_int::from_uhwi (distance))
1075 return false;
1076
1077 return true;
1078 }
1079
1080 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1081 initial value is correct (equal to initial value of REF shifted by one
1082 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1083 is the root of the current chain. */
1084
1085 static gimple
1086 find_looparound_phi (struct loop *loop, dref ref, dref root)
1087 {
1088 tree name, init, init_ref;
1089 gimple phi = NULL, init_stmt;
1090 edge latch = loop_latch_edge (loop);
1091 struct data_reference init_dr;
1092 gimple_stmt_iterator psi;
1093
1094 if (is_gimple_assign (ref->stmt))
1095 {
1096 if (DR_IS_READ (ref->ref))
1097 name = gimple_assign_lhs (ref->stmt);
1098 else
1099 name = gimple_assign_rhs1 (ref->stmt);
1100 }
1101 else
1102 name = PHI_RESULT (ref->stmt);
1103 if (!name)
1104 return NULL;
1105
1106 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1107 {
1108 phi = gsi_stmt (psi);
1109 if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1110 break;
1111 }
1112
1113 if (gsi_end_p (psi))
1114 return NULL;
1115
1116 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1117 if (TREE_CODE (init) != SSA_NAME)
1118 return NULL;
1119 init_stmt = SSA_NAME_DEF_STMT (init);
1120 if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1121 return NULL;
1122 gcc_assert (gimple_assign_lhs (init_stmt) == init);
1123
1124 init_ref = gimple_assign_rhs1 (init_stmt);
1125 if (!REFERENCE_CLASS_P (init_ref)
1126 && !DECL_P (init_ref))
1127 return NULL;
1128
1129 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1130 loop enclosing PHI). */
1131 memset (&init_dr, 0, sizeof (struct data_reference));
1132 DR_REF (&init_dr) = init_ref;
1133 DR_STMT (&init_dr) = phi;
1134 if (!dr_analyze_innermost (&init_dr, loop))
1135 return NULL;
1136
1137 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1138 return NULL;
1139
1140 return phi;
1141 }
1142
1143 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1144
1145 static void
1146 insert_looparound_copy (chain_p chain, dref ref, gimple phi)
1147 {
1148 dref nw = XCNEW (struct dref_d), aref;
1149 unsigned i;
1150
1151 nw->stmt = phi;
1152 nw->distance = ref->distance + 1;
1153 nw->always_accessed = 1;
1154
1155 FOR_EACH_VEC_ELT (chain->refs, i, aref)
1156 if (aref->distance >= nw->distance)
1157 break;
1158 chain->refs.safe_insert (i, nw);
1159
1160 if (nw->distance > chain->length)
1161 {
1162 chain->length = nw->distance;
1163 chain->has_max_use_after = false;
1164 }
1165 }
1166
1167 /* For references in CHAIN that are copied around the LOOP (created previously
1168 by PRE, or by user), add the results of such copies to the chain. This
1169 enables us to remove the copies by unrolling, and may need less registers
1170 (also, it may allow us to combine chains together). */
1171
1172 static void
1173 add_looparound_copies (struct loop *loop, chain_p chain)
1174 {
1175 unsigned i;
1176 dref ref, root = get_chain_root (chain);
1177 gimple phi;
1178
1179 FOR_EACH_VEC_ELT (chain->refs, i, ref)
1180 {
1181 phi = find_looparound_phi (loop, ref, root);
1182 if (!phi)
1183 continue;
1184
1185 bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1186 insert_looparound_copy (chain, ref, phi);
1187 }
1188 }
1189
1190 /* Find roots of the values and determine distances in the component COMP.
1191 The references are redistributed into CHAINS. LOOP is the current
1192 loop. */
1193
1194 static void
1195 determine_roots_comp (struct loop *loop,
1196 struct component *comp,
1197 vec<chain_p> *chains)
1198 {
1199 unsigned i;
1200 dref a;
1201 chain_p chain = NULL;
1202 double_int last_ofs = double_int_zero;
1203
1204 /* Invariants are handled specially. */
1205 if (comp->comp_step == RS_INVARIANT)
1206 {
1207 chain = make_invariant_chain (comp);
1208 chains->safe_push (chain);
1209 return;
1210 }
1211
1212 comp->refs.qsort (order_drefs);
1213
1214 FOR_EACH_VEC_ELT (comp->refs, i, a)
1215 {
1216 if (!chain || DR_IS_WRITE (a->ref)
1217 || double_int::from_uhwi (MAX_DISTANCE).ule (a->offset - last_ofs))
1218 {
1219 if (nontrivial_chain_p (chain))
1220 {
1221 add_looparound_copies (loop, chain);
1222 chains->safe_push (chain);
1223 }
1224 else
1225 release_chain (chain);
1226 chain = make_rooted_chain (a);
1227 last_ofs = a->offset;
1228 continue;
1229 }
1230
1231 add_ref_to_chain (chain, a);
1232 }
1233
1234 if (nontrivial_chain_p (chain))
1235 {
1236 add_looparound_copies (loop, chain);
1237 chains->safe_push (chain);
1238 }
1239 else
1240 release_chain (chain);
1241 }
1242
1243 /* Find roots of the values and determine distances in components COMPS, and
1244 separates the references to CHAINS. LOOP is the current loop. */
1245
1246 static void
1247 determine_roots (struct loop *loop,
1248 struct component *comps, vec<chain_p> *chains)
1249 {
1250 struct component *comp;
1251
1252 for (comp = comps; comp; comp = comp->next)
1253 determine_roots_comp (loop, comp, chains);
1254 }
1255
1256 /* Replace the reference in statement STMT with temporary variable
1257 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1258 the reference in the statement. IN_LHS is true if the reference
1259 is in the lhs of STMT, false if it is in rhs. */
1260
1261 static void
1262 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs)
1263 {
1264 tree val;
1265 gimple new_stmt;
1266 gimple_stmt_iterator bsi, psi;
1267
1268 if (gimple_code (stmt) == GIMPLE_PHI)
1269 {
1270 gcc_assert (!in_lhs && !set);
1271
1272 val = PHI_RESULT (stmt);
1273 bsi = gsi_after_labels (gimple_bb (stmt));
1274 psi = gsi_for_stmt (stmt);
1275 remove_phi_node (&psi, false);
1276
1277 /* Turn the phi node into GIMPLE_ASSIGN. */
1278 new_stmt = gimple_build_assign (val, new_tree);
1279 gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1280 return;
1281 }
1282
1283 /* Since the reference is of gimple_reg type, it should only
1284 appear as lhs or rhs of modify statement. */
1285 gcc_assert (is_gimple_assign (stmt));
1286
1287 bsi = gsi_for_stmt (stmt);
1288
1289 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1290 if (!set)
1291 {
1292 gcc_assert (!in_lhs);
1293 gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1294 stmt = gsi_stmt (bsi);
1295 update_stmt (stmt);
1296 return;
1297 }
1298
1299 if (in_lhs)
1300 {
1301 /* We have statement
1302
1303 OLD = VAL
1304
1305 If OLD is a memory reference, then VAL is gimple_val, and we transform
1306 this to
1307
1308 OLD = VAL
1309 NEW = VAL
1310
1311 Otherwise, we are replacing a combination chain,
1312 VAL is the expression that performs the combination, and OLD is an
1313 SSA name. In this case, we transform the assignment to
1314
1315 OLD = VAL
1316 NEW = OLD
1317
1318 */
1319
1320 val = gimple_assign_lhs (stmt);
1321 if (TREE_CODE (val) != SSA_NAME)
1322 {
1323 val = gimple_assign_rhs1 (stmt);
1324 gcc_assert (gimple_assign_single_p (stmt));
1325 if (TREE_CLOBBER_P (val))
1326 val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (new_tree));
1327 else
1328 gcc_assert (gimple_assign_copy_p (stmt));
1329 }
1330 }
1331 else
1332 {
1333 /* VAL = OLD
1334
1335 is transformed to
1336
1337 VAL = OLD
1338 NEW = VAL */
1339
1340 val = gimple_assign_lhs (stmt);
1341 }
1342
1343 new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1344 gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1345 }
1346
1347 /* Returns a memory reference to DR in the ITER-th iteration of
1348 the loop it was analyzed in. Append init stmts to STMTS. */
1349
1350 static tree
1351 ref_at_iteration (data_reference_p dr, int iter, gimple_seq *stmts)
1352 {
1353 tree off = DR_OFFSET (dr);
1354 tree coff = DR_INIT (dr);
1355 if (iter == 0)
1356 ;
1357 else if (TREE_CODE (DR_STEP (dr)) == INTEGER_CST)
1358 coff = size_binop (PLUS_EXPR, coff,
1359 size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
1360 else
1361 off = size_binop (PLUS_EXPR, off,
1362 size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter)));
1363 tree addr = fold_build_pointer_plus (DR_BASE_ADDRESS (dr), off);
1364 addr = force_gimple_operand_1 (addr, stmts, is_gimple_mem_ref_addr,
1365 NULL_TREE);
1366 tree alias_ptr = fold_convert (reference_alias_ptr_type (DR_REF (dr)), coff);
1367 /* While data-ref analysis punts on bit offsets it still handles
1368 bitfield accesses at byte boundaries. Cope with that. Note that
1369 we cannot simply re-apply the outer COMPONENT_REF because the
1370 byte-granular portion of it is already applied via DR_INIT and
1371 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1372 start at offset zero. */
1373 if (TREE_CODE (DR_REF (dr)) == COMPONENT_REF
1374 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr), 1)))
1375 {
1376 tree field = TREE_OPERAND (DR_REF (dr), 1);
1377 return build3 (BIT_FIELD_REF, TREE_TYPE (DR_REF (dr)),
1378 build2 (MEM_REF, DECL_BIT_FIELD_TYPE (field),
1379 addr, alias_ptr),
1380 DECL_SIZE (field), bitsize_zero_node);
1381 }
1382 else
1383 return fold_build2 (MEM_REF, TREE_TYPE (DR_REF (dr)), addr, alias_ptr);
1384 }
1385
1386 /* Get the initialization expression for the INDEX-th temporary variable
1387 of CHAIN. */
1388
1389 static tree
1390 get_init_expr (chain_p chain, unsigned index)
1391 {
1392 if (chain->type == CT_COMBINATION)
1393 {
1394 tree e1 = get_init_expr (chain->ch1, index);
1395 tree e2 = get_init_expr (chain->ch2, index);
1396
1397 return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1398 }
1399 else
1400 return chain->inits[index];
1401 }
1402
1403 /* Returns a new temporary variable used for the I-th variable carrying
1404 value of REF. The variable's uid is marked in TMP_VARS. */
1405
1406 static tree
1407 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1408 {
1409 tree type = TREE_TYPE (ref);
1410 /* We never access the components of the temporary variable in predictive
1411 commoning. */
1412 tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1413 bitmap_set_bit (tmp_vars, DECL_UID (var));
1414 return var;
1415 }
1416
1417 /* Creates the variables for CHAIN, as well as phi nodes for them and
1418 initialization on entry to LOOP. Uids of the newly created
1419 temporary variables are marked in TMP_VARS. */
1420
1421 static void
1422 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1423 {
1424 unsigned i;
1425 unsigned n = chain->length;
1426 dref root = get_chain_root (chain);
1427 bool reuse_first = !chain->has_max_use_after;
1428 tree ref, init, var, next;
1429 gimple phi;
1430 gimple_seq stmts;
1431 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1432
1433 /* If N == 0, then all the references are within the single iteration. And
1434 since this is an nonempty chain, reuse_first cannot be true. */
1435 gcc_assert (n > 0 || !reuse_first);
1436
1437 chain->vars.create (n + 1);
1438
1439 if (chain->type == CT_COMBINATION)
1440 ref = gimple_assign_lhs (root->stmt);
1441 else
1442 ref = DR_REF (root->ref);
1443
1444 for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1445 {
1446 var = predcom_tmp_var (ref, i, tmp_vars);
1447 chain->vars.quick_push (var);
1448 }
1449 if (reuse_first)
1450 chain->vars.quick_push (chain->vars[0]);
1451
1452 FOR_EACH_VEC_ELT (chain->vars, i, var)
1453 chain->vars[i] = make_ssa_name (var, NULL);
1454
1455 for (i = 0; i < n; i++)
1456 {
1457 var = chain->vars[i];
1458 next = chain->vars[i + 1];
1459 init = get_init_expr (chain, i);
1460
1461 init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1462 if (stmts)
1463 gsi_insert_seq_on_edge_immediate (entry, stmts);
1464
1465 phi = create_phi_node (var, loop->header);
1466 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1467 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1468 }
1469 }
1470
1471 /* Create the variables and initialization statement for root of chain
1472 CHAIN. Uids of the newly created temporary variables are marked
1473 in TMP_VARS. */
1474
1475 static void
1476 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1477 {
1478 dref root = get_chain_root (chain);
1479 bool in_lhs = (chain->type == CT_STORE_LOAD
1480 || chain->type == CT_COMBINATION);
1481
1482 initialize_root_vars (loop, chain, tmp_vars);
1483 replace_ref_with (root->stmt,
1484 chain->vars[chain->length],
1485 true, in_lhs);
1486 }
1487
1488 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1489 initialization on entry to LOOP if necessary. The ssa name for the variable
1490 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1491 around the loop is created. Uid of the newly created temporary variable
1492 is marked in TMP_VARS. INITS is the list containing the (single)
1493 initializer. */
1494
1495 static void
1496 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1497 vec<tree> *vars, vec<tree> inits,
1498 bitmap tmp_vars)
1499 {
1500 unsigned i;
1501 tree ref = DR_REF (root->ref), init, var, next;
1502 gimple_seq stmts;
1503 gimple phi;
1504 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1505
1506 /* Find the initializer for the variable, and check that it cannot
1507 trap. */
1508 init = inits[0];
1509
1510 vars->create (written ? 2 : 1);
1511 var = predcom_tmp_var (ref, 0, tmp_vars);
1512 vars->quick_push (var);
1513 if (written)
1514 vars->quick_push ((*vars)[0]);
1515
1516 FOR_EACH_VEC_ELT (*vars, i, var)
1517 (*vars)[i] = make_ssa_name (var, NULL);
1518
1519 var = (*vars)[0];
1520
1521 init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1522 if (stmts)
1523 gsi_insert_seq_on_edge_immediate (entry, stmts);
1524
1525 if (written)
1526 {
1527 next = (*vars)[1];
1528 phi = create_phi_node (var, loop->header);
1529 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1530 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1531 }
1532 else
1533 {
1534 gimple init_stmt = gimple_build_assign (var, init);
1535 gsi_insert_on_edge_immediate (entry, init_stmt);
1536 }
1537 }
1538
1539
1540 /* Execute load motion for references in chain CHAIN. Uids of the newly
1541 created temporary variables are marked in TMP_VARS. */
1542
1543 static void
1544 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1545 {
1546 auto_vec<tree> vars;
1547 dref a;
1548 unsigned n_writes = 0, ridx, i;
1549 tree var;
1550
1551 gcc_assert (chain->type == CT_INVARIANT);
1552 gcc_assert (!chain->combined);
1553 FOR_EACH_VEC_ELT (chain->refs, i, a)
1554 if (DR_IS_WRITE (a->ref))
1555 n_writes++;
1556
1557 /* If there are no reads in the loop, there is nothing to do. */
1558 if (n_writes == chain->refs.length ())
1559 return;
1560
1561 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1562 &vars, chain->inits, tmp_vars);
1563
1564 ridx = 0;
1565 FOR_EACH_VEC_ELT (chain->refs, i, a)
1566 {
1567 bool is_read = DR_IS_READ (a->ref);
1568
1569 if (DR_IS_WRITE (a->ref))
1570 {
1571 n_writes--;
1572 if (n_writes)
1573 {
1574 var = vars[0];
1575 var = make_ssa_name (SSA_NAME_VAR (var), NULL);
1576 vars[0] = var;
1577 }
1578 else
1579 ridx = 1;
1580 }
1581
1582 replace_ref_with (a->stmt, vars[ridx],
1583 !is_read, !is_read);
1584 }
1585 }
1586
1587 /* Returns the single statement in that NAME is used, excepting
1588 the looparound phi nodes contained in one of the chains. If there is no
1589 such statement, or more statements, NULL is returned. */
1590
1591 static gimple
1592 single_nonlooparound_use (tree name)
1593 {
1594 use_operand_p use;
1595 imm_use_iterator it;
1596 gimple stmt, ret = NULL;
1597
1598 FOR_EACH_IMM_USE_FAST (use, it, name)
1599 {
1600 stmt = USE_STMT (use);
1601
1602 if (gimple_code (stmt) == GIMPLE_PHI)
1603 {
1604 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1605 could not be processed anyway, so just fail for them. */
1606 if (bitmap_bit_p (looparound_phis,
1607 SSA_NAME_VERSION (PHI_RESULT (stmt))))
1608 continue;
1609
1610 return NULL;
1611 }
1612 else if (is_gimple_debug (stmt))
1613 continue;
1614 else if (ret != NULL)
1615 return NULL;
1616 else
1617 ret = stmt;
1618 }
1619
1620 return ret;
1621 }
1622
1623 /* Remove statement STMT, as well as the chain of assignments in that it is
1624 used. */
1625
1626 static void
1627 remove_stmt (gimple stmt)
1628 {
1629 tree name;
1630 gimple next;
1631 gimple_stmt_iterator psi;
1632
1633 if (gimple_code (stmt) == GIMPLE_PHI)
1634 {
1635 name = PHI_RESULT (stmt);
1636 next = single_nonlooparound_use (name);
1637 reset_debug_uses (stmt);
1638 psi = gsi_for_stmt (stmt);
1639 remove_phi_node (&psi, true);
1640
1641 if (!next
1642 || !gimple_assign_ssa_name_copy_p (next)
1643 || gimple_assign_rhs1 (next) != name)
1644 return;
1645
1646 stmt = next;
1647 }
1648
1649 while (1)
1650 {
1651 gimple_stmt_iterator bsi;
1652
1653 bsi = gsi_for_stmt (stmt);
1654
1655 name = gimple_assign_lhs (stmt);
1656 gcc_assert (TREE_CODE (name) == SSA_NAME);
1657
1658 next = single_nonlooparound_use (name);
1659 reset_debug_uses (stmt);
1660
1661 unlink_stmt_vdef (stmt);
1662 gsi_remove (&bsi, true);
1663 release_defs (stmt);
1664
1665 if (!next
1666 || !gimple_assign_ssa_name_copy_p (next)
1667 || gimple_assign_rhs1 (next) != name)
1668 return;
1669
1670 stmt = next;
1671 }
1672 }
1673
1674 /* Perform the predictive commoning optimization for a chain CHAIN.
1675 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1676
1677 static void
1678 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1679 bitmap tmp_vars)
1680 {
1681 unsigned i;
1682 dref a;
1683 tree var;
1684
1685 if (chain->combined)
1686 {
1687 /* For combined chains, just remove the statements that are used to
1688 compute the values of the expression (except for the root one). */
1689 for (i = 1; chain->refs.iterate (i, &a); i++)
1690 remove_stmt (a->stmt);
1691 }
1692 else
1693 {
1694 /* For non-combined chains, set up the variables that hold its value,
1695 and replace the uses of the original references by these
1696 variables. */
1697 initialize_root (loop, chain, tmp_vars);
1698 for (i = 1; chain->refs.iterate (i, &a); i++)
1699 {
1700 var = chain->vars[chain->length - a->distance];
1701 replace_ref_with (a->stmt, var, false, false);
1702 }
1703 }
1704 }
1705
1706 /* Determines the unroll factor necessary to remove as many temporary variable
1707 copies as possible. CHAINS is the list of chains that will be
1708 optimized. */
1709
1710 static unsigned
1711 determine_unroll_factor (vec<chain_p> chains)
1712 {
1713 chain_p chain;
1714 unsigned factor = 1, af, nfactor, i;
1715 unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1716
1717 FOR_EACH_VEC_ELT (chains, i, chain)
1718 {
1719 if (chain->type == CT_INVARIANT || chain->combined)
1720 continue;
1721
1722 /* The best unroll factor for this chain is equal to the number of
1723 temporary variables that we create for it. */
1724 af = chain->length;
1725 if (chain->has_max_use_after)
1726 af++;
1727
1728 nfactor = factor * af / gcd (factor, af);
1729 if (nfactor <= max)
1730 factor = nfactor;
1731 }
1732
1733 return factor;
1734 }
1735
1736 /* Perform the predictive commoning optimization for CHAINS.
1737 Uids of the newly created temporary variables are marked in TMP_VARS. */
1738
1739 static void
1740 execute_pred_commoning (struct loop *loop, vec<chain_p> chains,
1741 bitmap tmp_vars)
1742 {
1743 chain_p chain;
1744 unsigned i;
1745
1746 FOR_EACH_VEC_ELT (chains, i, chain)
1747 {
1748 if (chain->type == CT_INVARIANT)
1749 execute_load_motion (loop, chain, tmp_vars);
1750 else
1751 execute_pred_commoning_chain (loop, chain, tmp_vars);
1752 }
1753
1754 update_ssa (TODO_update_ssa_only_virtuals);
1755 }
1756
1757 /* For each reference in CHAINS, if its defining statement is
1758 phi node, record the ssa name that is defined by it. */
1759
1760 static void
1761 replace_phis_by_defined_names (vec<chain_p> chains)
1762 {
1763 chain_p chain;
1764 dref a;
1765 unsigned i, j;
1766
1767 FOR_EACH_VEC_ELT (chains, i, chain)
1768 FOR_EACH_VEC_ELT (chain->refs, j, a)
1769 {
1770 if (gimple_code (a->stmt) == GIMPLE_PHI)
1771 {
1772 a->name_defined_by_phi = PHI_RESULT (a->stmt);
1773 a->stmt = NULL;
1774 }
1775 }
1776 }
1777
1778 /* For each reference in CHAINS, if name_defined_by_phi is not
1779 NULL, use it to set the stmt field. */
1780
1781 static void
1782 replace_names_by_phis (vec<chain_p> chains)
1783 {
1784 chain_p chain;
1785 dref a;
1786 unsigned i, j;
1787
1788 FOR_EACH_VEC_ELT (chains, i, chain)
1789 FOR_EACH_VEC_ELT (chain->refs, j, a)
1790 if (a->stmt == NULL)
1791 {
1792 a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1793 gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1794 a->name_defined_by_phi = NULL_TREE;
1795 }
1796 }
1797
1798 /* Wrapper over execute_pred_commoning, to pass it as a callback
1799 to tree_transform_and_unroll_loop. */
1800
1801 struct epcc_data
1802 {
1803 vec<chain_p> chains;
1804 bitmap tmp_vars;
1805 };
1806
1807 static void
1808 execute_pred_commoning_cbck (struct loop *loop, void *data)
1809 {
1810 struct epcc_data *const dta = (struct epcc_data *) data;
1811
1812 /* Restore phi nodes that were replaced by ssa names before
1813 tree_transform_and_unroll_loop (see detailed description in
1814 tree_predictive_commoning_loop). */
1815 replace_names_by_phis (dta->chains);
1816 execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1817 }
1818
1819 /* Base NAME and all the names in the chain of phi nodes that use it
1820 on variable VAR. The phi nodes are recognized by being in the copies of
1821 the header of the LOOP. */
1822
1823 static void
1824 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1825 {
1826 gimple stmt, phi;
1827 imm_use_iterator iter;
1828
1829 replace_ssa_name_symbol (name, var);
1830
1831 while (1)
1832 {
1833 phi = NULL;
1834 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1835 {
1836 if (gimple_code (stmt) == GIMPLE_PHI
1837 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1838 {
1839 phi = stmt;
1840 BREAK_FROM_IMM_USE_STMT (iter);
1841 }
1842 }
1843 if (!phi)
1844 return;
1845
1846 name = PHI_RESULT (phi);
1847 replace_ssa_name_symbol (name, var);
1848 }
1849 }
1850
1851 /* Given an unrolled LOOP after predictive commoning, remove the
1852 register copies arising from phi nodes by changing the base
1853 variables of SSA names. TMP_VARS is the set of the temporary variables
1854 for those we want to perform this. */
1855
1856 static void
1857 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1858 {
1859 edge e;
1860 gimple phi, stmt;
1861 tree name, use, var;
1862 gimple_stmt_iterator psi;
1863
1864 e = loop_latch_edge (loop);
1865 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1866 {
1867 phi = gsi_stmt (psi);
1868 name = PHI_RESULT (phi);
1869 var = SSA_NAME_VAR (name);
1870 if (!var || !bitmap_bit_p (tmp_vars, DECL_UID (var)))
1871 continue;
1872 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1873 gcc_assert (TREE_CODE (use) == SSA_NAME);
1874
1875 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1876 stmt = SSA_NAME_DEF_STMT (use);
1877 while (gimple_code (stmt) == GIMPLE_PHI
1878 /* In case we could not unroll the loop enough to eliminate
1879 all copies, we may reach the loop header before the defining
1880 statement (in that case, some register copies will be present
1881 in loop latch in the final code, corresponding to the newly
1882 created looparound phi nodes). */
1883 && gimple_bb (stmt) != loop->header)
1884 {
1885 gcc_assert (single_pred_p (gimple_bb (stmt)));
1886 use = PHI_ARG_DEF (stmt, 0);
1887 stmt = SSA_NAME_DEF_STMT (use);
1888 }
1889
1890 base_names_in_chain_on (loop, use, var);
1891 }
1892 }
1893
1894 /* Returns true if CHAIN is suitable to be combined. */
1895
1896 static bool
1897 chain_can_be_combined_p (chain_p chain)
1898 {
1899 return (!chain->combined
1900 && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
1901 }
1902
1903 /* Returns the modify statement that uses NAME. Skips over assignment
1904 statements, NAME is replaced with the actual name used in the returned
1905 statement. */
1906
1907 static gimple
1908 find_use_stmt (tree *name)
1909 {
1910 gimple stmt;
1911 tree rhs, lhs;
1912
1913 /* Skip over assignments. */
1914 while (1)
1915 {
1916 stmt = single_nonlooparound_use (*name);
1917 if (!stmt)
1918 return NULL;
1919
1920 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1921 return NULL;
1922
1923 lhs = gimple_assign_lhs (stmt);
1924 if (TREE_CODE (lhs) != SSA_NAME)
1925 return NULL;
1926
1927 if (gimple_assign_copy_p (stmt))
1928 {
1929 rhs = gimple_assign_rhs1 (stmt);
1930 if (rhs != *name)
1931 return NULL;
1932
1933 *name = lhs;
1934 }
1935 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1936 == GIMPLE_BINARY_RHS)
1937 return stmt;
1938 else
1939 return NULL;
1940 }
1941 }
1942
1943 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1944
1945 static bool
1946 may_reassociate_p (tree type, enum tree_code code)
1947 {
1948 if (FLOAT_TYPE_P (type)
1949 && !flag_unsafe_math_optimizations)
1950 return false;
1951
1952 return (commutative_tree_code (code)
1953 && associative_tree_code (code));
1954 }
1955
1956 /* If the operation used in STMT is associative and commutative, go through the
1957 tree of the same operations and returns its root. Distance to the root
1958 is stored in DISTANCE. */
1959
1960 static gimple
1961 find_associative_operation_root (gimple stmt, unsigned *distance)
1962 {
1963 tree lhs;
1964 gimple next;
1965 enum tree_code code = gimple_assign_rhs_code (stmt);
1966 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1967 unsigned dist = 0;
1968
1969 if (!may_reassociate_p (type, code))
1970 return NULL;
1971
1972 while (1)
1973 {
1974 lhs = gimple_assign_lhs (stmt);
1975 gcc_assert (TREE_CODE (lhs) == SSA_NAME);
1976
1977 next = find_use_stmt (&lhs);
1978 if (!next
1979 || gimple_assign_rhs_code (next) != code)
1980 break;
1981
1982 stmt = next;
1983 dist++;
1984 }
1985
1986 if (distance)
1987 *distance = dist;
1988 return stmt;
1989 }
1990
1991 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
1992 is no such statement, returns NULL_TREE. In case the operation used on
1993 NAME1 and NAME2 is associative and commutative, returns the root of the
1994 tree formed by this operation instead of the statement that uses NAME1 or
1995 NAME2. */
1996
1997 static gimple
1998 find_common_use_stmt (tree *name1, tree *name2)
1999 {
2000 gimple stmt1, stmt2;
2001
2002 stmt1 = find_use_stmt (name1);
2003 if (!stmt1)
2004 return NULL;
2005
2006 stmt2 = find_use_stmt (name2);
2007 if (!stmt2)
2008 return NULL;
2009
2010 if (stmt1 == stmt2)
2011 return stmt1;
2012
2013 stmt1 = find_associative_operation_root (stmt1, NULL);
2014 if (!stmt1)
2015 return NULL;
2016 stmt2 = find_associative_operation_root (stmt2, NULL);
2017 if (!stmt2)
2018 return NULL;
2019
2020 return (stmt1 == stmt2 ? stmt1 : NULL);
2021 }
2022
2023 /* Checks whether R1 and R2 are combined together using CODE, with the result
2024 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2025 if it is true. If CODE is ERROR_MARK, set these values instead. */
2026
2027 static bool
2028 combinable_refs_p (dref r1, dref r2,
2029 enum tree_code *code, bool *swap, tree *rslt_type)
2030 {
2031 enum tree_code acode;
2032 bool aswap;
2033 tree atype;
2034 tree name1, name2;
2035 gimple stmt;
2036
2037 name1 = name_for_ref (r1);
2038 name2 = name_for_ref (r2);
2039 gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2040
2041 stmt = find_common_use_stmt (&name1, &name2);
2042
2043 if (!stmt
2044 /* A simple post-dominance check - make sure the combination
2045 is executed under the same condition as the references. */
2046 || (gimple_bb (stmt) != gimple_bb (r1->stmt)
2047 && gimple_bb (stmt) != gimple_bb (r2->stmt)))
2048 return false;
2049
2050 acode = gimple_assign_rhs_code (stmt);
2051 aswap = (!commutative_tree_code (acode)
2052 && gimple_assign_rhs1 (stmt) != name1);
2053 atype = TREE_TYPE (gimple_assign_lhs (stmt));
2054
2055 if (*code == ERROR_MARK)
2056 {
2057 *code = acode;
2058 *swap = aswap;
2059 *rslt_type = atype;
2060 return true;
2061 }
2062
2063 return (*code == acode
2064 && *swap == aswap
2065 && *rslt_type == atype);
2066 }
2067
2068 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2069 an assignment of the remaining operand. */
2070
2071 static void
2072 remove_name_from_operation (gimple stmt, tree op)
2073 {
2074 tree other_op;
2075 gimple_stmt_iterator si;
2076
2077 gcc_assert (is_gimple_assign (stmt));
2078
2079 if (gimple_assign_rhs1 (stmt) == op)
2080 other_op = gimple_assign_rhs2 (stmt);
2081 else
2082 other_op = gimple_assign_rhs1 (stmt);
2083
2084 si = gsi_for_stmt (stmt);
2085 gimple_assign_set_rhs_from_tree (&si, other_op);
2086
2087 /* We should not have reallocated STMT. */
2088 gcc_assert (gsi_stmt (si) == stmt);
2089
2090 update_stmt (stmt);
2091 }
2092
2093 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2094 are combined in a single statement, and returns this statement. */
2095
2096 static gimple
2097 reassociate_to_the_same_stmt (tree name1, tree name2)
2098 {
2099 gimple stmt1, stmt2, root1, root2, s1, s2;
2100 gimple new_stmt, tmp_stmt;
2101 tree new_name, tmp_name, var, r1, r2;
2102 unsigned dist1, dist2;
2103 enum tree_code code;
2104 tree type = TREE_TYPE (name1);
2105 gimple_stmt_iterator bsi;
2106
2107 stmt1 = find_use_stmt (&name1);
2108 stmt2 = find_use_stmt (&name2);
2109 root1 = find_associative_operation_root (stmt1, &dist1);
2110 root2 = find_associative_operation_root (stmt2, &dist2);
2111 code = gimple_assign_rhs_code (stmt1);
2112
2113 gcc_assert (root1 && root2 && root1 == root2
2114 && code == gimple_assign_rhs_code (stmt2));
2115
2116 /* Find the root of the nearest expression in that both NAME1 and NAME2
2117 are used. */
2118 r1 = name1;
2119 s1 = stmt1;
2120 r2 = name2;
2121 s2 = stmt2;
2122
2123 while (dist1 > dist2)
2124 {
2125 s1 = find_use_stmt (&r1);
2126 r1 = gimple_assign_lhs (s1);
2127 dist1--;
2128 }
2129 while (dist2 > dist1)
2130 {
2131 s2 = find_use_stmt (&r2);
2132 r2 = gimple_assign_lhs (s2);
2133 dist2--;
2134 }
2135
2136 while (s1 != s2)
2137 {
2138 s1 = find_use_stmt (&r1);
2139 r1 = gimple_assign_lhs (s1);
2140 s2 = find_use_stmt (&r2);
2141 r2 = gimple_assign_lhs (s2);
2142 }
2143
2144 /* Remove NAME1 and NAME2 from the statements in that they are used
2145 currently. */
2146 remove_name_from_operation (stmt1, name1);
2147 remove_name_from_operation (stmt2, name2);
2148
2149 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2150 combine it with the rhs of S1. */
2151 var = create_tmp_reg (type, "predreastmp");
2152 new_name = make_ssa_name (var, NULL);
2153 new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2154
2155 var = create_tmp_reg (type, "predreastmp");
2156 tmp_name = make_ssa_name (var, NULL);
2157
2158 /* Rhs of S1 may now be either a binary expression with operation
2159 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2160 so that name1 or name2 was removed from it). */
2161 tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2162 tmp_name,
2163 gimple_assign_rhs1 (s1),
2164 gimple_assign_rhs2 (s1));
2165
2166 bsi = gsi_for_stmt (s1);
2167 gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2168 s1 = gsi_stmt (bsi);
2169 update_stmt (s1);
2170
2171 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2172 gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2173
2174 return new_stmt;
2175 }
2176
2177 /* Returns the statement that combines references R1 and R2. In case R1
2178 and R2 are not used in the same statement, but they are used with an
2179 associative and commutative operation in the same expression, reassociate
2180 the expression so that they are used in the same statement. */
2181
2182 static gimple
2183 stmt_combining_refs (dref r1, dref r2)
2184 {
2185 gimple stmt1, stmt2;
2186 tree name1 = name_for_ref (r1);
2187 tree name2 = name_for_ref (r2);
2188
2189 stmt1 = find_use_stmt (&name1);
2190 stmt2 = find_use_stmt (&name2);
2191 if (stmt1 == stmt2)
2192 return stmt1;
2193
2194 return reassociate_to_the_same_stmt (name1, name2);
2195 }
2196
2197 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2198 description of the new chain is returned, otherwise we return NULL. */
2199
2200 static chain_p
2201 combine_chains (chain_p ch1, chain_p ch2)
2202 {
2203 dref r1, r2, nw;
2204 enum tree_code op = ERROR_MARK;
2205 bool swap = false;
2206 chain_p new_chain;
2207 unsigned i;
2208 gimple root_stmt;
2209 tree rslt_type = NULL_TREE;
2210
2211 if (ch1 == ch2)
2212 return NULL;
2213 if (ch1->length != ch2->length)
2214 return NULL;
2215
2216 if (ch1->refs.length () != ch2->refs.length ())
2217 return NULL;
2218
2219 for (i = 0; (ch1->refs.iterate (i, &r1)
2220 && ch2->refs.iterate (i, &r2)); i++)
2221 {
2222 if (r1->distance != r2->distance)
2223 return NULL;
2224
2225 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2226 return NULL;
2227 }
2228
2229 if (swap)
2230 {
2231 chain_p tmp = ch1;
2232 ch1 = ch2;
2233 ch2 = tmp;
2234 }
2235
2236 new_chain = XCNEW (struct chain);
2237 new_chain->type = CT_COMBINATION;
2238 new_chain->op = op;
2239 new_chain->ch1 = ch1;
2240 new_chain->ch2 = ch2;
2241 new_chain->rslt_type = rslt_type;
2242 new_chain->length = ch1->length;
2243
2244 for (i = 0; (ch1->refs.iterate (i, &r1)
2245 && ch2->refs.iterate (i, &r2)); i++)
2246 {
2247 nw = XCNEW (struct dref_d);
2248 nw->stmt = stmt_combining_refs (r1, r2);
2249 nw->distance = r1->distance;
2250
2251 new_chain->refs.safe_push (nw);
2252 }
2253
2254 new_chain->has_max_use_after = false;
2255 root_stmt = get_chain_root (new_chain)->stmt;
2256 for (i = 1; new_chain->refs.iterate (i, &nw); i++)
2257 {
2258 if (nw->distance == new_chain->length
2259 && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2260 {
2261 new_chain->has_max_use_after = true;
2262 break;
2263 }
2264 }
2265
2266 ch1->combined = true;
2267 ch2->combined = true;
2268 return new_chain;
2269 }
2270
2271 /* Try to combine the CHAINS. */
2272
2273 static void
2274 try_combine_chains (vec<chain_p> *chains)
2275 {
2276 unsigned i, j;
2277 chain_p ch1, ch2, cch;
2278 auto_vec<chain_p> worklist;
2279
2280 FOR_EACH_VEC_ELT (*chains, i, ch1)
2281 if (chain_can_be_combined_p (ch1))
2282 worklist.safe_push (ch1);
2283
2284 while (!worklist.is_empty ())
2285 {
2286 ch1 = worklist.pop ();
2287 if (!chain_can_be_combined_p (ch1))
2288 continue;
2289
2290 FOR_EACH_VEC_ELT (*chains, j, ch2)
2291 {
2292 if (!chain_can_be_combined_p (ch2))
2293 continue;
2294
2295 cch = combine_chains (ch1, ch2);
2296 if (cch)
2297 {
2298 worklist.safe_push (cch);
2299 chains->safe_push (cch);
2300 break;
2301 }
2302 }
2303 }
2304 }
2305
2306 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2307 impossible because one of these initializers may trap, true otherwise. */
2308
2309 static bool
2310 prepare_initializers_chain (struct loop *loop, chain_p chain)
2311 {
2312 unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2313 struct data_reference *dr = get_chain_root (chain)->ref;
2314 tree init;
2315 gimple_seq stmts;
2316 dref laref;
2317 edge entry = loop_preheader_edge (loop);
2318
2319 /* Find the initializers for the variables, and check that they cannot
2320 trap. */
2321 chain->inits.create (n);
2322 for (i = 0; i < n; i++)
2323 chain->inits.quick_push (NULL_TREE);
2324
2325 /* If we have replaced some looparound phi nodes, use their initializers
2326 instead of creating our own. */
2327 FOR_EACH_VEC_ELT (chain->refs, i, laref)
2328 {
2329 if (gimple_code (laref->stmt) != GIMPLE_PHI)
2330 continue;
2331
2332 gcc_assert (laref->distance > 0);
2333 chain->inits[n - laref->distance]
2334 = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
2335 }
2336
2337 for (i = 0; i < n; i++)
2338 {
2339 if (chain->inits[i] != NULL_TREE)
2340 continue;
2341
2342 init = ref_at_iteration (dr, (int) i - n, &stmts);
2343 if (!chain->all_always_accessed && tree_could_trap_p (init))
2344 return false;
2345
2346 if (stmts)
2347 gsi_insert_seq_on_edge_immediate (entry, stmts);
2348
2349 chain->inits[i] = init;
2350 }
2351
2352 return true;
2353 }
2354
2355 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2356 be used because the initializers might trap. */
2357
2358 static void
2359 prepare_initializers (struct loop *loop, vec<chain_p> chains)
2360 {
2361 chain_p chain;
2362 unsigned i;
2363
2364 for (i = 0; i < chains.length (); )
2365 {
2366 chain = chains[i];
2367 if (prepare_initializers_chain (loop, chain))
2368 i++;
2369 else
2370 {
2371 release_chain (chain);
2372 chains.unordered_remove (i);
2373 }
2374 }
2375 }
2376
2377 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2378 unrolled. */
2379
2380 static bool
2381 tree_predictive_commoning_loop (struct loop *loop)
2382 {
2383 vec<data_reference_p> datarefs;
2384 vec<ddr_p> dependences;
2385 struct component *components;
2386 vec<chain_p> chains = vNULL;
2387 unsigned unroll_factor;
2388 struct tree_niter_desc desc;
2389 bool unroll = false;
2390 edge exit;
2391 bitmap tmp_vars;
2392
2393 if (dump_file && (dump_flags & TDF_DETAILS))
2394 fprintf (dump_file, "Processing loop %d\n", loop->num);
2395
2396 /* Find the data references and split them into components according to their
2397 dependence relations. */
2398 stack_vec<loop_p, 3> loop_nest;
2399 dependences.create (10);
2400 datarefs.create (10);
2401 if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
2402 &dependences))
2403 {
2404 if (dump_file && (dump_flags & TDF_DETAILS))
2405 fprintf (dump_file, "Cannot analyze data dependencies\n");
2406 free_data_refs (datarefs);
2407 free_dependence_relations (dependences);
2408 return false;
2409 }
2410
2411 if (dump_file && (dump_flags & TDF_DETAILS))
2412 dump_data_dependence_relations (dump_file, dependences);
2413
2414 components = split_data_refs_to_components (loop, datarefs, dependences);
2415 loop_nest.release ();
2416 free_dependence_relations (dependences);
2417 if (!components)
2418 {
2419 free_data_refs (datarefs);
2420 return false;
2421 }
2422
2423 if (dump_file && (dump_flags & TDF_DETAILS))
2424 {
2425 fprintf (dump_file, "Initial state:\n\n");
2426 dump_components (dump_file, components);
2427 }
2428
2429 /* Find the suitable components and split them into chains. */
2430 components = filter_suitable_components (loop, components);
2431
2432 tmp_vars = BITMAP_ALLOC (NULL);
2433 looparound_phis = BITMAP_ALLOC (NULL);
2434 determine_roots (loop, components, &chains);
2435 release_components (components);
2436
2437 if (!chains.exists ())
2438 {
2439 if (dump_file && (dump_flags & TDF_DETAILS))
2440 fprintf (dump_file,
2441 "Predictive commoning failed: no suitable chains\n");
2442 goto end;
2443 }
2444 prepare_initializers (loop, chains);
2445
2446 /* Try to combine the chains that are always worked with together. */
2447 try_combine_chains (&chains);
2448
2449 if (dump_file && (dump_flags & TDF_DETAILS))
2450 {
2451 fprintf (dump_file, "Before commoning:\n\n");
2452 dump_chains (dump_file, chains);
2453 }
2454
2455 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2456 that its number of iterations is divisible by the factor. */
2457 unroll_factor = determine_unroll_factor (chains);
2458 scev_reset ();
2459 unroll = (unroll_factor > 1
2460 && can_unroll_loop_p (loop, unroll_factor, &desc));
2461 exit = single_dom_exit (loop);
2462
2463 /* Execute the predictive commoning transformations, and possibly unroll the
2464 loop. */
2465 if (unroll)
2466 {
2467 struct epcc_data dta;
2468
2469 if (dump_file && (dump_flags & TDF_DETAILS))
2470 fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2471
2472 dta.chains = chains;
2473 dta.tmp_vars = tmp_vars;
2474
2475 update_ssa (TODO_update_ssa_only_virtuals);
2476
2477 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2478 execute_pred_commoning_cbck is called may cause phi nodes to be
2479 reallocated, which is a problem since CHAINS may point to these
2480 statements. To fix this, we store the ssa names defined by the
2481 phi nodes here instead of the phi nodes themselves, and restore
2482 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2483 replace_phis_by_defined_names (chains);
2484
2485 tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2486 execute_pred_commoning_cbck, &dta);
2487 eliminate_temp_copies (loop, tmp_vars);
2488 }
2489 else
2490 {
2491 if (dump_file && (dump_flags & TDF_DETAILS))
2492 fprintf (dump_file,
2493 "Executing predictive commoning without unrolling.\n");
2494 execute_pred_commoning (loop, chains, tmp_vars);
2495 }
2496
2497 end: ;
2498 release_chains (chains);
2499 free_data_refs (datarefs);
2500 BITMAP_FREE (tmp_vars);
2501 BITMAP_FREE (looparound_phis);
2502
2503 free_affine_expand_cache (&name_expansions);
2504
2505 return unroll;
2506 }
2507
2508 /* Runs predictive commoning. */
2509
2510 unsigned
2511 tree_predictive_commoning (void)
2512 {
2513 bool unrolled = false;
2514 struct loop *loop;
2515 unsigned ret = 0;
2516
2517 initialize_original_copy_tables ();
2518 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
2519 if (optimize_loop_for_speed_p (loop))
2520 {
2521 unrolled |= tree_predictive_commoning_loop (loop);
2522 }
2523
2524 if (unrolled)
2525 {
2526 scev_reset ();
2527 ret = TODO_cleanup_cfg;
2528 }
2529 free_original_copy_tables ();
2530
2531 return ret;
2532 }
2533
2534 /* Predictive commoning Pass. */
2535
2536 static unsigned
2537 run_tree_predictive_commoning (void)
2538 {
2539 if (!current_loops)
2540 return 0;
2541
2542 return tree_predictive_commoning ();
2543 }
2544
2545 static bool
2546 gate_tree_predictive_commoning (void)
2547 {
2548 return flag_predictive_commoning != 0;
2549 }
2550
2551 namespace {
2552
2553 const pass_data pass_data_predcom =
2554 {
2555 GIMPLE_PASS, /* type */
2556 "pcom", /* name */
2557 OPTGROUP_LOOP, /* optinfo_flags */
2558 true, /* has_gate */
2559 true, /* has_execute */
2560 TV_PREDCOM, /* tv_id */
2561 PROP_cfg, /* properties_required */
2562 0, /* properties_provided */
2563 0, /* properties_destroyed */
2564 0, /* todo_flags_start */
2565 TODO_update_ssa_only_virtuals, /* todo_flags_finish */
2566 };
2567
2568 class pass_predcom : public gimple_opt_pass
2569 {
2570 public:
2571 pass_predcom (gcc::context *ctxt)
2572 : gimple_opt_pass (pass_data_predcom, ctxt)
2573 {}
2574
2575 /* opt_pass methods: */
2576 bool gate () { return gate_tree_predictive_commoning (); }
2577 unsigned int execute () { return run_tree_predictive_commoning (); }
2578
2579 }; // class pass_predcom
2580
2581 } // anon namespace
2582
2583 gimple_opt_pass *
2584 make_pass_predcom (gcc::context *ctxt)
2585 {
2586 return new pass_predcom (ctxt);
2587 }
2588
2589