PR tree-optimization/43833
[official-gcc/alias-decl.git] / gcc / tree-predcom.c
blob41873cefb8c0d425a3fa83253f8c1b36dd9910a1
1 /* Predictive commoning.
2 Copyright (C) 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
10 later version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This file implements the predictive commoning optimization. Predictive
22 commoning can be viewed as CSE around a loop, and with some improvements,
23 as generalized strength reduction-- i.e., reusing values computed in
24 earlier iterations of a loop in the later ones. So far, the pass only
25 handles the most useful case, that is, reusing values of memory references.
26 If you think this is all just a special case of PRE, you are sort of right;
27 however, concentrating on loops is simpler, and makes it possible to
28 incorporate data dependence analysis to detect the opportunities, perform
29 loop unrolling to avoid copies together with renaming immediately,
30 and if needed, we could also take register pressure into account.
32 Let us demonstrate what is done on an example:
34 for (i = 0; i < 100; i++)
36 a[i+2] = a[i] + a[i+1];
37 b[10] = b[10] + i;
38 c[i] = c[99 - i];
39 d[i] = d[i + 1];
42 1) We find data references in the loop, and split them to mutually
43 independent groups (i.e., we find components of a data dependence
44 graph). We ignore read-read dependences whose distance is not constant.
45 (TODO -- we could also ignore antidependences). In this example, we
46 find the following groups:
48 a[i]{read}, a[i+1]{read}, a[i+2]{write}
49 b[10]{read}, b[10]{write}
50 c[99 - i]{read}, c[i]{write}
51 d[i + 1]{read}, d[i]{write}
53 2) Inside each of the group, we verify several conditions:
54 a) all the references must differ in indices only, and the indices
55 must all have the same step
56 b) the references must dominate loop latch (and thus, they must be
57 ordered by dominance relation).
58 c) the distance of the indices must be a small multiple of the step
59 We are then able to compute the difference of the references (# of
60 iterations before they point to the same place as the first of them).
61 Also, in case there are writes in the loop, we split the groups into
62 chains whose head is the write whose values are used by the reads in
63 the same chain. The chains are then processed independently,
64 making the further transformations simpler. Also, the shorter chains
65 need the same number of registers, but may require lower unrolling
66 factor in order to get rid of the copies on the loop latch.
68 In our example, we get the following chains (the chain for c is invalid).
70 a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
71 b[10]{read,+0}, b[10]{write,+0}
72 d[i + 1]{read,+0}, d[i]{write,+1}
74 3) For each read, we determine the read or write whose value it reuses,
75 together with the distance of this reuse. I.e. we take the last
76 reference before it with distance 0, or the last of the references
77 with the smallest positive distance to the read. Then, we remove
78 the references that are not used in any of these chains, discard the
79 empty groups, and propagate all the links so that they point to the
80 single root reference of the chain (adjusting their distance
81 appropriately). Some extra care needs to be taken for references with
82 step 0. In our example (the numbers indicate the distance of the
83 reuse),
85 a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
86 b[10] --> (*) 1, b[10] (*)
88 4) The chains are combined together if possible. If the corresponding
89 elements of two chains are always combined together with the same
90 operator, we remember just the result of this combination, instead
91 of remembering the values separately. We may need to perform
92 reassociation to enable combining, for example
94 e[i] + f[i+1] + e[i+1] + f[i]
96 can be reassociated as
98 (e[i] + f[i]) + (e[i+1] + f[i+1])
100 and we can combine the chains for e and f into one chain.
102 5) For each root reference (end of the chain) R, let N be maximum distance
103 of a reference reusing its value. Variables R0 upto RN are created,
104 together with phi nodes that transfer values from R1 .. RN to
105 R0 .. R(N-1).
106 Initial values are loaded to R0..R(N-1) (in case not all references
107 must necessarily be accessed and they may trap, we may fail here;
108 TODO sometimes, the loads could be guarded by a check for the number
109 of iterations). Values loaded/stored in roots are also copied to
110 RN. Other reads are replaced with the appropriate variable Ri.
111 Everything is put to SSA form.
113 As a small improvement, if R0 is dead after the root (i.e., all uses of
114 the value with the maximum distance dominate the root), we can avoid
115 creating RN and use R0 instead of it.
117 In our example, we get (only the parts concerning a and b are shown):
118 for (i = 0; i < 100; i++)
120 f = phi (a[0], s);
121 s = phi (a[1], f);
122 x = phi (b[10], x);
124 f = f + s;
125 a[i+2] = f;
126 x = x + i;
127 b[10] = x;
130 6) Factor F for unrolling is determined as the smallest common multiple of
131 (N + 1) for each root reference (N for references for that we avoided
132 creating RN). If F and the loop is small enough, loop is unrolled F
133 times. The stores to RN (R0) in the copies of the loop body are
134 periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
135 be coalesced and the copies can be eliminated.
137 TODO -- copy propagation and other optimizations may change the live
138 ranges of the temporary registers and prevent them from being coalesced;
139 this may increase the register pressure.
141 In our case, F = 2 and the (main loop of the) result is
143 for (i = 0; i < ...; i += 2)
145 f = phi (a[0], f);
146 s = phi (a[1], s);
147 x = phi (b[10], x);
149 f = f + s;
150 a[i+2] = f;
151 x = x + i;
152 b[10] = x;
154 s = s + f;
155 a[i+3] = s;
156 x = x + i;
157 b[10] = x;
160 TODO -- stores killing other stores can be taken into account, e.g.,
161 for (i = 0; i < n; i++)
163 a[i] = 1;
164 a[i+2] = 2;
167 can be replaced with
169 t0 = a[0];
170 t1 = a[1];
171 for (i = 0; i < n; i++)
173 a[i] = 1;
174 t2 = 2;
175 t0 = t1;
176 t1 = t2;
178 a[n] = t0;
179 a[n+1] = t1;
181 The interesting part is that this would generalize store motion; still, since
182 sm is performed elsewhere, it does not seem that important.
184 Predictive commoning can be generalized for arbitrary computations (not
185 just memory loads), and also nontrivial transfer functions (e.g., replacing
186 i * i with ii_last + 2 * i + 1), to generalize strength reduction. */
188 #include "config.h"
189 #include "system.h"
190 #include "coretypes.h"
191 #include "tm.h"
192 #include "tree.h"
193 #include "tm_p.h"
194 #include "cfgloop.h"
195 #include "tree-flow.h"
196 #include "ggc.h"
197 #include "tree-data-ref.h"
198 #include "tree-scalar-evolution.h"
199 #include "tree-chrec.h"
200 #include "params.h"
201 #include "diagnostic.h"
202 #include "tree-pass.h"
203 #include "tree-affine.h"
204 #include "tree-inline.h"
206 /* The maximum number of iterations between the considered memory
207 references. */
209 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
211 /* Data references (or phi nodes that carry data reference values across
212 loop iterations). */
214 typedef struct dref_d
216 /* The reference itself. */
217 struct data_reference *ref;
219 /* The statement in that the reference appears. */
220 gimple stmt;
222 /* In case that STMT is a phi node, this field is set to the SSA name
223 defined by it in replace_phis_by_defined_names (in order to avoid
224 pointing to phi node that got reallocated in the meantime). */
225 tree name_defined_by_phi;
227 /* Distance of the reference from the root of the chain (in number of
228 iterations of the loop). */
229 unsigned distance;
231 /* Number of iterations offset from the first reference in the component. */
232 double_int offset;
234 /* Number of the reference in a component, in dominance ordering. */
235 unsigned pos;
237 /* True if the memory reference is always accessed when the loop is
238 entered. */
239 unsigned always_accessed : 1;
240 } *dref;
242 DEF_VEC_P (dref);
243 DEF_VEC_ALLOC_P (dref, heap);
245 /* Type of the chain of the references. */
247 enum chain_type
249 /* The addresses of the references in the chain are constant. */
250 CT_INVARIANT,
252 /* There are only loads in the chain. */
253 CT_LOAD,
255 /* Root of the chain is store, the rest are loads. */
256 CT_STORE_LOAD,
258 /* A combination of two chains. */
259 CT_COMBINATION
262 /* Chains of data references. */
264 typedef struct chain
266 /* Type of the chain. */
267 enum chain_type type;
269 /* For combination chains, the operator and the two chains that are
270 combined, and the type of the result. */
271 enum tree_code op;
272 tree rslt_type;
273 struct chain *ch1, *ch2;
275 /* The references in the chain. */
276 VEC(dref,heap) *refs;
278 /* The maximum distance of the reference in the chain from the root. */
279 unsigned length;
281 /* The variables used to copy the value throughout iterations. */
282 VEC(tree,heap) *vars;
284 /* Initializers for the variables. */
285 VEC(tree,heap) *inits;
287 /* True if there is a use of a variable with the maximal distance
288 that comes after the root in the loop. */
289 unsigned has_max_use_after : 1;
291 /* True if all the memory references in the chain are always accessed. */
292 unsigned all_always_accessed : 1;
294 /* True if this chain was combined together with some other chain. */
295 unsigned combined : 1;
296 } *chain_p;
298 DEF_VEC_P (chain_p);
299 DEF_VEC_ALLOC_P (chain_p, heap);
301 /* Describes the knowledge about the step of the memory references in
302 the component. */
304 enum ref_step_type
306 /* The step is zero. */
307 RS_INVARIANT,
309 /* The step is nonzero. */
310 RS_NONZERO,
312 /* The step may or may not be nonzero. */
313 RS_ANY
316 /* Components of the data dependence graph. */
318 struct component
320 /* The references in the component. */
321 VEC(dref,heap) *refs;
323 /* What we know about the step of the references in the component. */
324 enum ref_step_type comp_step;
326 /* Next component in the list. */
327 struct component *next;
330 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
332 static bitmap looparound_phis;
334 /* Cache used by tree_to_aff_combination_expand. */
336 static struct pointer_map_t *name_expansions;
338 /* Dumps data reference REF to FILE. */
340 extern void dump_dref (FILE *, dref);
341 void
342 dump_dref (FILE *file, dref ref)
344 if (ref->ref)
346 fprintf (file, " ");
347 print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
348 fprintf (file, " (id %u%s)\n", ref->pos,
349 DR_IS_READ (ref->ref) ? "" : ", write");
351 fprintf (file, " offset ");
352 dump_double_int (file, ref->offset, false);
353 fprintf (file, "\n");
355 fprintf (file, " distance %u\n", ref->distance);
357 else
359 if (gimple_code (ref->stmt) == GIMPLE_PHI)
360 fprintf (file, " looparound ref\n");
361 else
362 fprintf (file, " combination ref\n");
363 fprintf (file, " in statement ");
364 print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
365 fprintf (file, "\n");
366 fprintf (file, " distance %u\n", ref->distance);
371 /* Dumps CHAIN to FILE. */
373 extern void dump_chain (FILE *, chain_p);
374 void
375 dump_chain (FILE *file, chain_p chain)
377 dref a;
378 const char *chain_type;
379 unsigned i;
380 tree var;
382 switch (chain->type)
384 case CT_INVARIANT:
385 chain_type = "Load motion";
386 break;
388 case CT_LOAD:
389 chain_type = "Loads-only";
390 break;
392 case CT_STORE_LOAD:
393 chain_type = "Store-loads";
394 break;
396 case CT_COMBINATION:
397 chain_type = "Combination";
398 break;
400 default:
401 gcc_unreachable ();
404 fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
405 chain->combined ? " (combined)" : "");
406 if (chain->type != CT_INVARIANT)
407 fprintf (file, " max distance %u%s\n", chain->length,
408 chain->has_max_use_after ? "" : ", may reuse first");
410 if (chain->type == CT_COMBINATION)
412 fprintf (file, " equal to %p %s %p in type ",
413 (void *) chain->ch1, op_symbol_code (chain->op),
414 (void *) chain->ch2);
415 print_generic_expr (file, chain->rslt_type, TDF_SLIM);
416 fprintf (file, "\n");
419 if (chain->vars)
421 fprintf (file, " vars");
422 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
424 fprintf (file, " ");
425 print_generic_expr (file, var, TDF_SLIM);
427 fprintf (file, "\n");
430 if (chain->inits)
432 fprintf (file, " inits");
433 for (i = 0; VEC_iterate (tree, chain->inits, i, var); i++)
435 fprintf (file, " ");
436 print_generic_expr (file, var, TDF_SLIM);
438 fprintf (file, "\n");
441 fprintf (file, " references:\n");
442 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
443 dump_dref (file, a);
445 fprintf (file, "\n");
448 /* Dumps CHAINS to FILE. */
450 extern void dump_chains (FILE *, VEC (chain_p, heap) *);
451 void
452 dump_chains (FILE *file, VEC (chain_p, heap) *chains)
454 chain_p chain;
455 unsigned i;
457 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
458 dump_chain (file, chain);
461 /* Dumps COMP to FILE. */
463 extern void dump_component (FILE *, struct component *);
464 void
465 dump_component (FILE *file, struct component *comp)
467 dref a;
468 unsigned i;
470 fprintf (file, "Component%s:\n",
471 comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
472 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
473 dump_dref (file, a);
474 fprintf (file, "\n");
477 /* Dumps COMPS to FILE. */
479 extern void dump_components (FILE *, struct component *);
480 void
481 dump_components (FILE *file, struct component *comps)
483 struct component *comp;
485 for (comp = comps; comp; comp = comp->next)
486 dump_component (file, comp);
489 /* Frees a chain CHAIN. */
491 static void
492 release_chain (chain_p chain)
494 dref ref;
495 unsigned i;
497 if (chain == NULL)
498 return;
500 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)
501 free (ref);
503 VEC_free (dref, heap, chain->refs);
504 VEC_free (tree, heap, chain->vars);
505 VEC_free (tree, heap, chain->inits);
507 free (chain);
510 /* Frees CHAINS. */
512 static void
513 release_chains (VEC (chain_p, heap) *chains)
515 unsigned i;
516 chain_p chain;
518 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
519 release_chain (chain);
520 VEC_free (chain_p, heap, chains);
523 /* Frees a component COMP. */
525 static void
526 release_component (struct component *comp)
528 VEC_free (dref, heap, comp->refs);
529 free (comp);
532 /* Frees list of components COMPS. */
534 static void
535 release_components (struct component *comps)
537 struct component *act, *next;
539 for (act = comps; act; act = next)
541 next = act->next;
542 release_component (act);
546 /* Finds a root of tree given by FATHERS containing A, and performs path
547 shortening. */
549 static unsigned
550 component_of (unsigned fathers[], unsigned a)
552 unsigned root, n;
554 for (root = a; root != fathers[root]; root = fathers[root])
555 continue;
557 for (; a != root; a = n)
559 n = fathers[a];
560 fathers[a] = root;
563 return root;
566 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
567 components, A and B are components to merge. */
569 static void
570 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)
572 unsigned ca = component_of (fathers, a);
573 unsigned cb = component_of (fathers, b);
575 if (ca == cb)
576 return;
578 if (sizes[ca] < sizes[cb])
580 sizes[cb] += sizes[ca];
581 fathers[ca] = cb;
583 else
585 sizes[ca] += sizes[cb];
586 fathers[cb] = ca;
590 /* Returns true if A is a reference that is suitable for predictive commoning
591 in the innermost loop that contains it. REF_STEP is set according to the
592 step of the reference A. */
594 static bool
595 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
597 tree ref = DR_REF (a), step = DR_STEP (a);
599 if (!step
600 || !is_gimple_reg_type (TREE_TYPE (ref))
601 || tree_could_throw_p (ref))
602 return false;
604 if (integer_zerop (step))
605 *ref_step = RS_INVARIANT;
606 else if (integer_nonzerop (step))
607 *ref_step = RS_NONZERO;
608 else
609 *ref_step = RS_ANY;
611 return true;
614 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
616 static void
617 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)
619 aff_tree delta;
621 tree_to_aff_combination_expand (DR_OFFSET (dr), sizetype, offset,
622 &name_expansions);
623 aff_combination_const (&delta, sizetype, tree_to_double_int (DR_INIT (dr)));
624 aff_combination_add (offset, &delta);
627 /* Determines number of iterations of the innermost enclosing loop before B
628 refers to exactly the same location as A and stores it to OFF. If A and
629 B do not have the same step, they never meet, or anything else fails,
630 returns false, otherwise returns true. Both A and B are assumed to
631 satisfy suitable_reference_p. */
633 static bool
634 determine_offset (struct data_reference *a, struct data_reference *b,
635 double_int *off)
637 aff_tree diff, baseb, step;
638 tree typea, typeb;
640 /* Check that both the references access the location in the same type. */
641 typea = TREE_TYPE (DR_REF (a));
642 typeb = TREE_TYPE (DR_REF (b));
643 if (!useless_type_conversion_p (typeb, typea))
644 return false;
646 /* Check whether the base address and the step of both references is the
647 same. */
648 if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
649 || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
650 return false;
652 if (integer_zerop (DR_STEP (a)))
654 /* If the references have loop invariant address, check that they access
655 exactly the same location. */
656 *off = double_int_zero;
657 return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
658 && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
661 /* Compare the offsets of the addresses, and check whether the difference
662 is a multiple of step. */
663 aff_combination_dr_offset (a, &diff);
664 aff_combination_dr_offset (b, &baseb);
665 aff_combination_scale (&baseb, double_int_minus_one);
666 aff_combination_add (&diff, &baseb);
668 tree_to_aff_combination_expand (DR_STEP (a), sizetype,
669 &step, &name_expansions);
670 return aff_combination_constant_multiple_p (&diff, &step, off);
673 /* Returns the last basic block in LOOP for that we are sure that
674 it is executed whenever the loop is entered. */
676 static basic_block
677 last_always_executed_block (struct loop *loop)
679 unsigned i;
680 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
681 edge ex;
682 basic_block last = loop->latch;
684 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
685 last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
686 VEC_free (edge, heap, exits);
688 return last;
691 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
693 static struct component *
694 split_data_refs_to_components (struct loop *loop,
695 VEC (data_reference_p, heap) *datarefs,
696 VEC (ddr_p, heap) *depends)
698 unsigned i, n = VEC_length (data_reference_p, datarefs);
699 unsigned ca, ia, ib, bad;
700 unsigned *comp_father = XNEWVEC (unsigned, n + 1);
701 unsigned *comp_size = XNEWVEC (unsigned, n + 1);
702 struct component **comps;
703 struct data_reference *dr, *dra, *drb;
704 struct data_dependence_relation *ddr;
705 struct component *comp_list = NULL, *comp;
706 dref dataref;
707 basic_block last_always_executed = last_always_executed_block (loop);
709 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
711 if (!DR_REF (dr))
713 /* A fake reference for call or asm_expr that may clobber memory;
714 just fail. */
715 goto end;
717 dr->aux = (void *) (size_t) i;
718 comp_father[i] = i;
719 comp_size[i] = 1;
722 /* A component reserved for the "bad" data references. */
723 comp_father[n] = n;
724 comp_size[n] = 1;
726 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
728 enum ref_step_type dummy;
730 if (!suitable_reference_p (dr, &dummy))
732 ia = (unsigned) (size_t) dr->aux;
733 merge_comps (comp_father, comp_size, n, ia);
737 for (i = 0; VEC_iterate (ddr_p, depends, i, ddr); i++)
739 double_int dummy_off;
741 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
742 continue;
744 dra = DDR_A (ddr);
745 drb = DDR_B (ddr);
746 ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
747 ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
748 if (ia == ib)
749 continue;
751 bad = component_of (comp_father, n);
753 /* If both A and B are reads, we may ignore unsuitable dependences. */
754 if (DR_IS_READ (dra) && DR_IS_READ (drb)
755 && (ia == bad || ib == bad
756 || !determine_offset (dra, drb, &dummy_off)))
757 continue;
759 merge_comps (comp_father, comp_size, ia, ib);
762 comps = XCNEWVEC (struct component *, n);
763 bad = component_of (comp_father, n);
764 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
766 ia = (unsigned) (size_t) dr->aux;
767 ca = component_of (comp_father, ia);
768 if (ca == bad)
769 continue;
771 comp = comps[ca];
772 if (!comp)
774 comp = XCNEW (struct component);
775 comp->refs = VEC_alloc (dref, heap, comp_size[ca]);
776 comps[ca] = comp;
779 dataref = XCNEW (struct dref_d);
780 dataref->ref = dr;
781 dataref->stmt = DR_STMT (dr);
782 dataref->offset = double_int_zero;
783 dataref->distance = 0;
785 dataref->always_accessed
786 = dominated_by_p (CDI_DOMINATORS, last_always_executed,
787 gimple_bb (dataref->stmt));
788 dataref->pos = VEC_length (dref, comp->refs);
789 VEC_quick_push (dref, comp->refs, dataref);
792 for (i = 0; i < n; i++)
794 comp = comps[i];
795 if (comp)
797 comp->next = comp_list;
798 comp_list = comp;
801 free (comps);
803 end:
804 free (comp_father);
805 free (comp_size);
806 return comp_list;
809 /* Returns true if the component COMP satisfies the conditions
810 described in 2) at the beginning of this file. LOOP is the current
811 loop. */
813 static bool
814 suitable_component_p (struct loop *loop, struct component *comp)
816 unsigned i;
817 dref a, first;
818 basic_block ba, bp = loop->header;
819 bool ok, has_write = false;
821 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
823 ba = gimple_bb (a->stmt);
825 if (!just_once_each_iteration_p (loop, ba))
826 return false;
828 gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
829 bp = ba;
831 if (!DR_IS_READ (a->ref))
832 has_write = true;
835 first = VEC_index (dref, comp->refs, 0);
836 ok = suitable_reference_p (first->ref, &comp->comp_step);
837 gcc_assert (ok);
838 first->offset = double_int_zero;
840 for (i = 1; VEC_iterate (dref, comp->refs, i, a); i++)
842 if (!determine_offset (first->ref, a->ref, &a->offset))
843 return false;
845 #ifdef ENABLE_CHECKING
847 enum ref_step_type a_step;
848 ok = suitable_reference_p (a->ref, &a_step);
849 gcc_assert (ok && a_step == comp->comp_step);
851 #endif
854 /* If there is a write inside the component, we must know whether the
855 step is nonzero or not -- we would not otherwise be able to recognize
856 whether the value accessed by reads comes from the OFFSET-th iteration
857 or the previous one. */
858 if (has_write && comp->comp_step == RS_ANY)
859 return false;
861 return true;
864 /* Check the conditions on references inside each of components COMPS,
865 and remove the unsuitable components from the list. The new list
866 of components is returned. The conditions are described in 2) at
867 the beginning of this file. LOOP is the current loop. */
869 static struct component *
870 filter_suitable_components (struct loop *loop, struct component *comps)
872 struct component **comp, *act;
874 for (comp = &comps; *comp; )
876 act = *comp;
877 if (suitable_component_p (loop, act))
878 comp = &act->next;
879 else
881 dref ref;
882 unsigned i;
884 *comp = act->next;
885 for (i = 0; VEC_iterate (dref, act->refs, i, ref); i++)
886 free (ref);
887 release_component (act);
891 return comps;
894 /* Compares two drefs A and B by their offset and position. Callback for
895 qsort. */
897 static int
898 order_drefs (const void *a, const void *b)
900 const dref *const da = (const dref *) a;
901 const dref *const db = (const dref *) b;
902 int offcmp = double_int_scmp ((*da)->offset, (*db)->offset);
904 if (offcmp != 0)
905 return offcmp;
907 return (*da)->pos - (*db)->pos;
910 /* Returns root of the CHAIN. */
912 static inline dref
913 get_chain_root (chain_p chain)
915 return VEC_index (dref, chain->refs, 0);
918 /* Adds REF to the chain CHAIN. */
920 static void
921 add_ref_to_chain (chain_p chain, dref ref)
923 dref root = get_chain_root (chain);
924 double_int dist;
926 gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0);
927 dist = double_int_add (ref->offset, double_int_neg (root->offset));
928 if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0)
930 free (ref);
931 return;
933 gcc_assert (double_int_fits_in_uhwi_p (dist));
935 VEC_safe_push (dref, heap, chain->refs, ref);
937 ref->distance = double_int_to_uhwi (dist);
939 if (ref->distance >= chain->length)
941 chain->length = ref->distance;
942 chain->has_max_use_after = false;
945 if (ref->distance == chain->length
946 && ref->pos > root->pos)
947 chain->has_max_use_after = true;
949 chain->all_always_accessed &= ref->always_accessed;
952 /* Returns the chain for invariant component COMP. */
954 static chain_p
955 make_invariant_chain (struct component *comp)
957 chain_p chain = XCNEW (struct chain);
958 unsigned i;
959 dref ref;
961 chain->type = CT_INVARIANT;
963 chain->all_always_accessed = true;
965 for (i = 0; VEC_iterate (dref, comp->refs, i, ref); i++)
967 VEC_safe_push (dref, heap, chain->refs, ref);
968 chain->all_always_accessed &= ref->always_accessed;
971 return chain;
974 /* Make a new chain rooted at REF. */
976 static chain_p
977 make_rooted_chain (dref ref)
979 chain_p chain = XCNEW (struct chain);
981 chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
983 VEC_safe_push (dref, heap, chain->refs, ref);
984 chain->all_always_accessed = ref->always_accessed;
986 ref->distance = 0;
988 return chain;
991 /* Returns true if CHAIN is not trivial. */
993 static bool
994 nontrivial_chain_p (chain_p chain)
996 return chain != NULL && VEC_length (dref, chain->refs) > 1;
999 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1000 is no such name. */
1002 static tree
1003 name_for_ref (dref ref)
1005 tree name;
1007 if (is_gimple_assign (ref->stmt))
1009 if (!ref->ref || DR_IS_READ (ref->ref))
1010 name = gimple_assign_lhs (ref->stmt);
1011 else
1012 name = gimple_assign_rhs1 (ref->stmt);
1014 else
1015 name = PHI_RESULT (ref->stmt);
1017 return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1020 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1021 iterations of the innermost enclosing loop). */
1023 static bool
1024 valid_initializer_p (struct data_reference *ref,
1025 unsigned distance, struct data_reference *root)
1027 aff_tree diff, base, step;
1028 double_int off;
1030 /* Both REF and ROOT must be accessing the same object. */
1031 if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1032 return false;
1034 /* The initializer is defined outside of loop, hence its address must be
1035 invariant inside the loop. */
1036 gcc_assert (integer_zerop (DR_STEP (ref)));
1038 /* If the address of the reference is invariant, initializer must access
1039 exactly the same location. */
1040 if (integer_zerop (DR_STEP (root)))
1041 return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1042 && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1044 /* Verify that this index of REF is equal to the root's index at
1045 -DISTANCE-th iteration. */
1046 aff_combination_dr_offset (root, &diff);
1047 aff_combination_dr_offset (ref, &base);
1048 aff_combination_scale (&base, double_int_minus_one);
1049 aff_combination_add (&diff, &base);
1051 tree_to_aff_combination_expand (DR_STEP (root), sizetype, &step,
1052 &name_expansions);
1053 if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1054 return false;
1056 if (!double_int_equal_p (off, uhwi_to_double_int (distance)))
1057 return false;
1059 return true;
1062 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1063 initial value is correct (equal to initial value of REF shifted by one
1064 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1065 is the root of the current chain. */
1067 static gimple
1068 find_looparound_phi (struct loop *loop, dref ref, dref root)
1070 tree name, init, init_ref;
1071 gimple phi = NULL, init_stmt;
1072 edge latch = loop_latch_edge (loop);
1073 struct data_reference init_dr;
1074 gimple_stmt_iterator psi;
1076 if (is_gimple_assign (ref->stmt))
1078 if (DR_IS_READ (ref->ref))
1079 name = gimple_assign_lhs (ref->stmt);
1080 else
1081 name = gimple_assign_rhs1 (ref->stmt);
1083 else
1084 name = PHI_RESULT (ref->stmt);
1085 if (!name)
1086 return NULL;
1088 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1090 phi = gsi_stmt (psi);
1091 if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1092 break;
1095 if (gsi_end_p (psi))
1096 return NULL;
1098 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1099 if (TREE_CODE (init) != SSA_NAME)
1100 return NULL;
1101 init_stmt = SSA_NAME_DEF_STMT (init);
1102 if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1103 return NULL;
1104 gcc_assert (gimple_assign_lhs (init_stmt) == init);
1106 init_ref = gimple_assign_rhs1 (init_stmt);
1107 if (!REFERENCE_CLASS_P (init_ref)
1108 && !DECL_P (init_ref))
1109 return NULL;
1111 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1112 loop enclosing PHI). */
1113 memset (&init_dr, 0, sizeof (struct data_reference));
1114 DR_REF (&init_dr) = init_ref;
1115 DR_STMT (&init_dr) = phi;
1116 if (!dr_analyze_innermost (&init_dr))
1117 return NULL;
1119 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1120 return NULL;
1122 return phi;
1125 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1127 static void
1128 insert_looparound_copy (chain_p chain, dref ref, gimple phi)
1130 dref nw = XCNEW (struct dref_d), aref;
1131 unsigned i;
1133 nw->stmt = phi;
1134 nw->distance = ref->distance + 1;
1135 nw->always_accessed = 1;
1137 for (i = 0; VEC_iterate (dref, chain->refs, i, aref); i++)
1138 if (aref->distance >= nw->distance)
1139 break;
1140 VEC_safe_insert (dref, heap, chain->refs, i, nw);
1142 if (nw->distance > chain->length)
1144 chain->length = nw->distance;
1145 chain->has_max_use_after = false;
1149 /* For references in CHAIN that are copied around the LOOP (created previously
1150 by PRE, or by user), add the results of such copies to the chain. This
1151 enables us to remove the copies by unrolling, and may need less registers
1152 (also, it may allow us to combine chains together). */
1154 static void
1155 add_looparound_copies (struct loop *loop, chain_p chain)
1157 unsigned i;
1158 dref ref, root = get_chain_root (chain);
1159 gimple phi;
1161 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)
1163 phi = find_looparound_phi (loop, ref, root);
1164 if (!phi)
1165 continue;
1167 bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1168 insert_looparound_copy (chain, ref, phi);
1172 /* Find roots of the values and determine distances in the component COMP.
1173 The references are redistributed into CHAINS. LOOP is the current
1174 loop. */
1176 static void
1177 determine_roots_comp (struct loop *loop,
1178 struct component *comp,
1179 VEC (chain_p, heap) **chains)
1181 unsigned i;
1182 dref a;
1183 chain_p chain = NULL;
1184 double_int last_ofs = double_int_zero;
1186 /* Invariants are handled specially. */
1187 if (comp->comp_step == RS_INVARIANT)
1189 chain = make_invariant_chain (comp);
1190 VEC_safe_push (chain_p, heap, *chains, chain);
1191 return;
1194 qsort (VEC_address (dref, comp->refs), VEC_length (dref, comp->refs),
1195 sizeof (dref), order_drefs);
1197 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
1199 if (!chain || !DR_IS_READ (a->ref)
1200 || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE),
1201 double_int_add (a->offset,
1202 double_int_neg (last_ofs))) <= 0)
1204 if (nontrivial_chain_p (chain))
1206 add_looparound_copies (loop, chain);
1207 VEC_safe_push (chain_p, heap, *chains, chain);
1209 else
1210 release_chain (chain);
1211 chain = make_rooted_chain (a);
1212 last_ofs = a->offset;
1213 continue;
1216 add_ref_to_chain (chain, a);
1219 if (nontrivial_chain_p (chain))
1221 add_looparound_copies (loop, chain);
1222 VEC_safe_push (chain_p, heap, *chains, chain);
1224 else
1225 release_chain (chain);
1228 /* Find roots of the values and determine distances in components COMPS, and
1229 separates the references to CHAINS. LOOP is the current loop. */
1231 static void
1232 determine_roots (struct loop *loop,
1233 struct component *comps, VEC (chain_p, heap) **chains)
1235 struct component *comp;
1237 for (comp = comps; comp; comp = comp->next)
1238 determine_roots_comp (loop, comp, chains);
1241 /* Replace the reference in statement STMT with temporary variable
1242 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1243 the reference in the statement. IN_LHS is true if the reference
1244 is in the lhs of STMT, false if it is in rhs. */
1246 static void
1247 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs)
1249 tree val;
1250 gimple new_stmt;
1251 gimple_stmt_iterator bsi, psi;
1253 if (gimple_code (stmt) == GIMPLE_PHI)
1255 gcc_assert (!in_lhs && !set);
1257 val = PHI_RESULT (stmt);
1258 bsi = gsi_after_labels (gimple_bb (stmt));
1259 psi = gsi_for_stmt (stmt);
1260 remove_phi_node (&psi, false);
1262 /* Turn the phi node into GIMPLE_ASSIGN. */
1263 new_stmt = gimple_build_assign (val, new_tree);
1264 gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1265 return;
1268 /* Since the reference is of gimple_reg type, it should only
1269 appear as lhs or rhs of modify statement. */
1270 gcc_assert (is_gimple_assign (stmt));
1272 bsi = gsi_for_stmt (stmt);
1274 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1275 if (!set)
1277 gcc_assert (!in_lhs);
1278 gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1279 stmt = gsi_stmt (bsi);
1280 update_stmt (stmt);
1281 return;
1284 if (in_lhs)
1286 /* We have statement
1288 OLD = VAL
1290 If OLD is a memory reference, then VAL is gimple_val, and we transform
1291 this to
1293 OLD = VAL
1294 NEW = VAL
1296 Otherwise, we are replacing a combination chain,
1297 VAL is the expression that performs the combination, and OLD is an
1298 SSA name. In this case, we transform the assignment to
1300 OLD = VAL
1301 NEW = OLD
1305 val = gimple_assign_lhs (stmt);
1306 if (TREE_CODE (val) != SSA_NAME)
1308 gcc_assert (gimple_assign_copy_p (stmt));
1309 val = gimple_assign_rhs1 (stmt);
1312 else
1314 /* VAL = OLD
1316 is transformed to
1318 VAL = OLD
1319 NEW = VAL */
1321 val = gimple_assign_lhs (stmt);
1324 new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1325 gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1328 /* Returns the reference to the address of REF in the ITER-th iteration of
1329 LOOP, or NULL if we fail to determine it (ITER may be negative). We
1330 try to preserve the original shape of the reference (not rewrite it
1331 as an indirect ref to the address), to make tree_could_trap_p in
1332 prepare_initializers_chain return false more often. */
1334 static tree
1335 ref_at_iteration (struct loop *loop, tree ref, int iter)
1337 tree idx, *idx_p, type, val, op0 = NULL_TREE, ret;
1338 affine_iv iv;
1339 bool ok;
1341 if (handled_component_p (ref))
1343 op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter);
1344 if (!op0)
1345 return NULL_TREE;
1347 else if (!INDIRECT_REF_P (ref))
1348 return unshare_expr (ref);
1350 if (INDIRECT_REF_P (ref))
1352 /* Take care for INDIRECT_REF and MISALIGNED_INDIRECT_REF at
1353 the same time. */
1354 ret = copy_node (ref);
1355 idx = TREE_OPERAND (ref, 0);
1356 idx_p = &TREE_OPERAND (ret, 0);
1358 else if (TREE_CODE (ref) == COMPONENT_REF)
1360 /* Check that the offset is loop invariant. */
1361 if (TREE_OPERAND (ref, 2)
1362 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1363 return NULL_TREE;
1365 return build3 (COMPONENT_REF, TREE_TYPE (ref), op0,
1366 unshare_expr (TREE_OPERAND (ref, 1)),
1367 unshare_expr (TREE_OPERAND (ref, 2)));
1369 else if (TREE_CODE (ref) == ARRAY_REF)
1371 /* Check that the lower bound and the step are loop invariant. */
1372 if (TREE_OPERAND (ref, 2)
1373 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1374 return NULL_TREE;
1375 if (TREE_OPERAND (ref, 3)
1376 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3)))
1377 return NULL_TREE;
1379 ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE,
1380 unshare_expr (TREE_OPERAND (ref, 2)),
1381 unshare_expr (TREE_OPERAND (ref, 3)));
1382 idx = TREE_OPERAND (ref, 1);
1383 idx_p = &TREE_OPERAND (ret, 1);
1385 else
1386 return NULL_TREE;
1388 ok = simple_iv (loop, loop, idx, &iv, true);
1389 if (!ok)
1390 return NULL_TREE;
1391 iv.base = expand_simple_operations (iv.base);
1392 if (integer_zerop (iv.step))
1393 *idx_p = unshare_expr (iv.base);
1394 else
1396 type = TREE_TYPE (iv.base);
1397 if (POINTER_TYPE_P (type))
1399 val = fold_build2 (MULT_EXPR, sizetype, iv.step,
1400 size_int (iter));
1401 val = fold_build2 (POINTER_PLUS_EXPR, type, iv.base, val);
1403 else
1405 val = fold_build2 (MULT_EXPR, type, iv.step,
1406 build_int_cst_type (type, iter));
1407 val = fold_build2 (PLUS_EXPR, type, iv.base, val);
1409 *idx_p = unshare_expr (val);
1412 return ret;
1415 /* Get the initialization expression for the INDEX-th temporary variable
1416 of CHAIN. */
1418 static tree
1419 get_init_expr (chain_p chain, unsigned index)
1421 if (chain->type == CT_COMBINATION)
1423 tree e1 = get_init_expr (chain->ch1, index);
1424 tree e2 = get_init_expr (chain->ch2, index);
1426 return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1428 else
1429 return VEC_index (tree, chain->inits, index);
1432 /* Marks all virtual operands of statement STMT for renaming. */
1434 void
1435 mark_virtual_ops_for_renaming (gimple stmt)
1437 tree var;
1439 if (gimple_code (stmt) == GIMPLE_PHI)
1441 var = PHI_RESULT (stmt);
1442 if (is_gimple_reg (var))
1443 return;
1445 if (TREE_CODE (var) == SSA_NAME)
1446 var = SSA_NAME_VAR (var);
1447 mark_sym_for_renaming (var);
1448 return;
1451 update_stmt (stmt);
1452 if (gimple_vuse (stmt))
1453 mark_sym_for_renaming (gimple_vop (cfun));
1456 /* Returns a new temporary variable used for the I-th variable carrying
1457 value of REF. The variable's uid is marked in TMP_VARS. */
1459 static tree
1460 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1462 tree type = TREE_TYPE (ref);
1463 /* We never access the components of the temporary variable in predictive
1464 commoning. */
1465 tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1467 add_referenced_var (var);
1468 bitmap_set_bit (tmp_vars, DECL_UID (var));
1469 return var;
1472 /* Creates the variables for CHAIN, as well as phi nodes for them and
1473 initialization on entry to LOOP. Uids of the newly created
1474 temporary variables are marked in TMP_VARS. */
1476 static void
1477 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1479 unsigned i;
1480 unsigned n = chain->length;
1481 dref root = get_chain_root (chain);
1482 bool reuse_first = !chain->has_max_use_after;
1483 tree ref, init, var, next;
1484 gimple phi;
1485 gimple_seq stmts;
1486 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1488 /* If N == 0, then all the references are within the single iteration. And
1489 since this is an nonempty chain, reuse_first cannot be true. */
1490 gcc_assert (n > 0 || !reuse_first);
1492 chain->vars = VEC_alloc (tree, heap, n + 1);
1494 if (chain->type == CT_COMBINATION)
1495 ref = gimple_assign_lhs (root->stmt);
1496 else
1497 ref = DR_REF (root->ref);
1499 for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1501 var = predcom_tmp_var (ref, i, tmp_vars);
1502 VEC_quick_push (tree, chain->vars, var);
1504 if (reuse_first)
1505 VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0));
1507 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
1508 VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL));
1510 for (i = 0; i < n; i++)
1512 var = VEC_index (tree, chain->vars, i);
1513 next = VEC_index (tree, chain->vars, i + 1);
1514 init = get_init_expr (chain, i);
1516 init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1517 if (stmts)
1518 gsi_insert_seq_on_edge_immediate (entry, stmts);
1520 phi = create_phi_node (var, loop->header);
1521 SSA_NAME_DEF_STMT (var) = phi;
1522 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1523 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1527 /* Create the variables and initialization statement for root of chain
1528 CHAIN. Uids of the newly created temporary variables are marked
1529 in TMP_VARS. */
1531 static void
1532 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1534 dref root = get_chain_root (chain);
1535 bool in_lhs = (chain->type == CT_STORE_LOAD
1536 || chain->type == CT_COMBINATION);
1538 initialize_root_vars (loop, chain, tmp_vars);
1539 replace_ref_with (root->stmt,
1540 VEC_index (tree, chain->vars, chain->length),
1541 true, in_lhs);
1544 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1545 initialization on entry to LOOP if necessary. The ssa name for the variable
1546 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1547 around the loop is created. Uid of the newly created temporary variable
1548 is marked in TMP_VARS. INITS is the list containing the (single)
1549 initializer. */
1551 static void
1552 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1553 VEC(tree, heap) **vars, VEC(tree, heap) *inits,
1554 bitmap tmp_vars)
1556 unsigned i;
1557 tree ref = DR_REF (root->ref), init, var, next;
1558 gimple_seq stmts;
1559 gimple phi;
1560 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1562 /* Find the initializer for the variable, and check that it cannot
1563 trap. */
1564 init = VEC_index (tree, inits, 0);
1566 *vars = VEC_alloc (tree, heap, written ? 2 : 1);
1567 var = predcom_tmp_var (ref, 0, tmp_vars);
1568 VEC_quick_push (tree, *vars, var);
1569 if (written)
1570 VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0));
1572 for (i = 0; VEC_iterate (tree, *vars, i, var); i++)
1573 VEC_replace (tree, *vars, i, make_ssa_name (var, NULL));
1575 var = VEC_index (tree, *vars, 0);
1577 init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1578 if (stmts)
1579 gsi_insert_seq_on_edge_immediate (entry, stmts);
1581 if (written)
1583 next = VEC_index (tree, *vars, 1);
1584 phi = create_phi_node (var, loop->header);
1585 SSA_NAME_DEF_STMT (var) = phi;
1586 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1587 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1589 else
1591 gimple init_stmt = gimple_build_assign (var, init);
1592 mark_virtual_ops_for_renaming (init_stmt);
1593 gsi_insert_on_edge_immediate (entry, init_stmt);
1598 /* Execute load motion for references in chain CHAIN. Uids of the newly
1599 created temporary variables are marked in TMP_VARS. */
1601 static void
1602 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1604 VEC (tree, heap) *vars;
1605 dref a;
1606 unsigned n_writes = 0, ridx, i;
1607 tree var;
1609 gcc_assert (chain->type == CT_INVARIANT);
1610 gcc_assert (!chain->combined);
1611 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1612 if (!DR_IS_READ (a->ref))
1613 n_writes++;
1615 /* If there are no reads in the loop, there is nothing to do. */
1616 if (n_writes == VEC_length (dref, chain->refs))
1617 return;
1619 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1620 &vars, chain->inits, tmp_vars);
1622 ridx = 0;
1623 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1625 bool is_read = DR_IS_READ (a->ref);
1626 mark_virtual_ops_for_renaming (a->stmt);
1628 if (!DR_IS_READ (a->ref))
1630 n_writes--;
1631 if (n_writes)
1633 var = VEC_index (tree, vars, 0);
1634 var = make_ssa_name (SSA_NAME_VAR (var), NULL);
1635 VEC_replace (tree, vars, 0, var);
1637 else
1638 ridx = 1;
1641 replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
1642 !is_read, !is_read);
1645 VEC_free (tree, heap, vars);
1648 /* Returns the single statement in that NAME is used, excepting
1649 the looparound phi nodes contained in one of the chains. If there is no
1650 such statement, or more statements, NULL is returned. */
1652 static gimple
1653 single_nonlooparound_use (tree name)
1655 use_operand_p use;
1656 imm_use_iterator it;
1657 gimple stmt, ret = NULL;
1659 FOR_EACH_IMM_USE_FAST (use, it, name)
1661 stmt = USE_STMT (use);
1663 if (gimple_code (stmt) == GIMPLE_PHI)
1665 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1666 could not be processed anyway, so just fail for them. */
1667 if (bitmap_bit_p (looparound_phis,
1668 SSA_NAME_VERSION (PHI_RESULT (stmt))))
1669 continue;
1671 return NULL;
1673 else if (ret != NULL)
1674 return NULL;
1675 else
1676 ret = stmt;
1679 return ret;
1682 /* Remove statement STMT, as well as the chain of assignments in that it is
1683 used. */
1685 static void
1686 remove_stmt (gimple stmt)
1688 tree name;
1689 gimple next;
1690 gimple_stmt_iterator psi;
1692 if (gimple_code (stmt) == GIMPLE_PHI)
1694 name = PHI_RESULT (stmt);
1695 next = single_nonlooparound_use (name);
1696 psi = gsi_for_stmt (stmt);
1697 remove_phi_node (&psi, true);
1699 if (!next
1700 || !gimple_assign_ssa_name_copy_p (next)
1701 || gimple_assign_rhs1 (next) != name)
1702 return;
1704 stmt = next;
1707 while (1)
1709 gimple_stmt_iterator bsi;
1711 bsi = gsi_for_stmt (stmt);
1713 name = gimple_assign_lhs (stmt);
1714 gcc_assert (TREE_CODE (name) == SSA_NAME);
1716 next = single_nonlooparound_use (name);
1718 mark_virtual_ops_for_renaming (stmt);
1719 gsi_remove (&bsi, true);
1720 release_defs (stmt);
1722 if (!next
1723 || !gimple_assign_ssa_name_copy_p (next)
1724 || gimple_assign_rhs1 (next) != name)
1725 return;
1727 stmt = next;
1731 /* Perform the predictive commoning optimization for a chain CHAIN.
1732 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1734 static void
1735 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1736 bitmap tmp_vars)
1738 unsigned i;
1739 dref a, root;
1740 tree var;
1742 if (chain->combined)
1744 /* For combined chains, just remove the statements that are used to
1745 compute the values of the expression (except for the root one). */
1746 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1747 remove_stmt (a->stmt);
1749 else
1751 /* For non-combined chains, set up the variables that hold its value,
1752 and replace the uses of the original references by these
1753 variables. */
1754 root = get_chain_root (chain);
1755 mark_virtual_ops_for_renaming (root->stmt);
1757 initialize_root (loop, chain, tmp_vars);
1758 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1760 mark_virtual_ops_for_renaming (a->stmt);
1761 var = VEC_index (tree, chain->vars, chain->length - a->distance);
1762 replace_ref_with (a->stmt, var, false, false);
1767 /* Determines the unroll factor necessary to remove as many temporary variable
1768 copies as possible. CHAINS is the list of chains that will be
1769 optimized. */
1771 static unsigned
1772 determine_unroll_factor (VEC (chain_p, heap) *chains)
1774 chain_p chain;
1775 unsigned factor = 1, af, nfactor, i;
1776 unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1778 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1780 if (chain->type == CT_INVARIANT || chain->combined)
1781 continue;
1783 /* The best unroll factor for this chain is equal to the number of
1784 temporary variables that we create for it. */
1785 af = chain->length;
1786 if (chain->has_max_use_after)
1787 af++;
1789 nfactor = factor * af / gcd (factor, af);
1790 if (nfactor <= max)
1791 factor = nfactor;
1794 return factor;
1797 /* Perform the predictive commoning optimization for CHAINS.
1798 Uids of the newly created temporary variables are marked in TMP_VARS. */
1800 static void
1801 execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains,
1802 bitmap tmp_vars)
1804 chain_p chain;
1805 unsigned i;
1807 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1809 if (chain->type == CT_INVARIANT)
1810 execute_load_motion (loop, chain, tmp_vars);
1811 else
1812 execute_pred_commoning_chain (loop, chain, tmp_vars);
1815 update_ssa (TODO_update_ssa_only_virtuals);
1818 /* For each reference in CHAINS, if its defining statement is
1819 phi node, record the ssa name that is defined by it. */
1821 static void
1822 replace_phis_by_defined_names (VEC (chain_p, heap) *chains)
1824 chain_p chain;
1825 dref a;
1826 unsigned i, j;
1828 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1829 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1831 if (gimple_code (a->stmt) == GIMPLE_PHI)
1833 a->name_defined_by_phi = PHI_RESULT (a->stmt);
1834 a->stmt = NULL;
1839 /* For each reference in CHAINS, if name_defined_by_phi is not
1840 NULL, use it to set the stmt field. */
1842 static void
1843 replace_names_by_phis (VEC (chain_p, heap) *chains)
1845 chain_p chain;
1846 dref a;
1847 unsigned i, j;
1849 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1850 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1851 if (a->stmt == NULL)
1853 a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1854 gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1855 a->name_defined_by_phi = NULL_TREE;
1859 /* Wrapper over execute_pred_commoning, to pass it as a callback
1860 to tree_transform_and_unroll_loop. */
1862 struct epcc_data
1864 VEC (chain_p, heap) *chains;
1865 bitmap tmp_vars;
1868 static void
1869 execute_pred_commoning_cbck (struct loop *loop, void *data)
1871 struct epcc_data *const dta = (struct epcc_data *) data;
1873 /* Restore phi nodes that were replaced by ssa names before
1874 tree_transform_and_unroll_loop (see detailed description in
1875 tree_predictive_commoning_loop). */
1876 replace_names_by_phis (dta->chains);
1877 execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1880 /* Base NAME and all the names in the chain of phi nodes that use it
1881 on variable VAR. The phi nodes are recognized by being in the copies of
1882 the header of the LOOP. */
1884 static void
1885 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1887 gimple stmt, phi;
1888 imm_use_iterator iter;
1890 SSA_NAME_VAR (name) = var;
1892 while (1)
1894 phi = NULL;
1895 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1897 if (gimple_code (stmt) == GIMPLE_PHI
1898 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1900 phi = stmt;
1901 BREAK_FROM_IMM_USE_STMT (iter);
1904 if (!phi)
1905 return;
1907 name = PHI_RESULT (phi);
1908 SSA_NAME_VAR (name) = var;
1912 /* Given an unrolled LOOP after predictive commoning, remove the
1913 register copies arising from phi nodes by changing the base
1914 variables of SSA names. TMP_VARS is the set of the temporary variables
1915 for those we want to perform this. */
1917 static void
1918 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1920 edge e;
1921 gimple phi, stmt;
1922 tree name, use, var;
1923 gimple_stmt_iterator psi;
1925 e = loop_latch_edge (loop);
1926 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1928 phi = gsi_stmt (psi);
1929 name = PHI_RESULT (phi);
1930 var = SSA_NAME_VAR (name);
1931 if (!bitmap_bit_p (tmp_vars, DECL_UID (var)))
1932 continue;
1933 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1934 gcc_assert (TREE_CODE (use) == SSA_NAME);
1936 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1937 stmt = SSA_NAME_DEF_STMT (use);
1938 while (gimple_code (stmt) == GIMPLE_PHI
1939 /* In case we could not unroll the loop enough to eliminate
1940 all copies, we may reach the loop header before the defining
1941 statement (in that case, some register copies will be present
1942 in loop latch in the final code, corresponding to the newly
1943 created looparound phi nodes). */
1944 && gimple_bb (stmt) != loop->header)
1946 gcc_assert (single_pred_p (gimple_bb (stmt)));
1947 use = PHI_ARG_DEF (stmt, 0);
1948 stmt = SSA_NAME_DEF_STMT (use);
1951 base_names_in_chain_on (loop, use, var);
1955 /* Returns true if CHAIN is suitable to be combined. */
1957 static bool
1958 chain_can_be_combined_p (chain_p chain)
1960 return (!chain->combined
1961 && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
1964 /* Returns the modify statement that uses NAME. Skips over assignment
1965 statements, NAME is replaced with the actual name used in the returned
1966 statement. */
1968 static gimple
1969 find_use_stmt (tree *name)
1971 gimple stmt;
1972 tree rhs, lhs;
1974 /* Skip over assignments. */
1975 while (1)
1977 stmt = single_nonlooparound_use (*name);
1978 if (!stmt)
1979 return NULL;
1981 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1982 return NULL;
1984 lhs = gimple_assign_lhs (stmt);
1985 if (TREE_CODE (lhs) != SSA_NAME)
1986 return NULL;
1988 if (gimple_assign_copy_p (stmt))
1990 rhs = gimple_assign_rhs1 (stmt);
1991 if (rhs != *name)
1992 return NULL;
1994 *name = lhs;
1996 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
1997 == GIMPLE_BINARY_RHS)
1998 return stmt;
1999 else
2000 return NULL;
2004 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
2006 static bool
2007 may_reassociate_p (tree type, enum tree_code code)
2009 if (FLOAT_TYPE_P (type)
2010 && !flag_unsafe_math_optimizations)
2011 return false;
2013 return (commutative_tree_code (code)
2014 && associative_tree_code (code));
2017 /* If the operation used in STMT is associative and commutative, go through the
2018 tree of the same operations and returns its root. Distance to the root
2019 is stored in DISTANCE. */
2021 static gimple
2022 find_associative_operation_root (gimple stmt, unsigned *distance)
2024 tree lhs;
2025 gimple next;
2026 enum tree_code code = gimple_assign_rhs_code (stmt);
2027 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2028 unsigned dist = 0;
2030 if (!may_reassociate_p (type, code))
2031 return NULL;
2033 while (1)
2035 lhs = gimple_assign_lhs (stmt);
2036 gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2038 next = find_use_stmt (&lhs);
2039 if (!next
2040 || gimple_assign_rhs_code (next) != code)
2041 break;
2043 stmt = next;
2044 dist++;
2047 if (distance)
2048 *distance = dist;
2049 return stmt;
2052 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2053 is no such statement, returns NULL_TREE. In case the operation used on
2054 NAME1 and NAME2 is associative and commutative, returns the root of the
2055 tree formed by this operation instead of the statement that uses NAME1 or
2056 NAME2. */
2058 static gimple
2059 find_common_use_stmt (tree *name1, tree *name2)
2061 gimple stmt1, stmt2;
2063 stmt1 = find_use_stmt (name1);
2064 if (!stmt1)
2065 return NULL;
2067 stmt2 = find_use_stmt (name2);
2068 if (!stmt2)
2069 return NULL;
2071 if (stmt1 == stmt2)
2072 return stmt1;
2074 stmt1 = find_associative_operation_root (stmt1, NULL);
2075 if (!stmt1)
2076 return NULL;
2077 stmt2 = find_associative_operation_root (stmt2, NULL);
2078 if (!stmt2)
2079 return NULL;
2081 return (stmt1 == stmt2 ? stmt1 : NULL);
2084 /* Checks whether R1 and R2 are combined together using CODE, with the result
2085 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2086 if it is true. If CODE is ERROR_MARK, set these values instead. */
2088 static bool
2089 combinable_refs_p (dref r1, dref r2,
2090 enum tree_code *code, bool *swap, tree *rslt_type)
2092 enum tree_code acode;
2093 bool aswap;
2094 tree atype;
2095 tree name1, name2;
2096 gimple stmt;
2098 name1 = name_for_ref (r1);
2099 name2 = name_for_ref (r2);
2100 gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2102 stmt = find_common_use_stmt (&name1, &name2);
2104 if (!stmt)
2105 return false;
2107 acode = gimple_assign_rhs_code (stmt);
2108 aswap = (!commutative_tree_code (acode)
2109 && gimple_assign_rhs1 (stmt) != name1);
2110 atype = TREE_TYPE (gimple_assign_lhs (stmt));
2112 if (*code == ERROR_MARK)
2114 *code = acode;
2115 *swap = aswap;
2116 *rslt_type = atype;
2117 return true;
2120 return (*code == acode
2121 && *swap == aswap
2122 && *rslt_type == atype);
2125 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2126 an assignment of the remaining operand. */
2128 static void
2129 remove_name_from_operation (gimple stmt, tree op)
2131 tree other_op;
2132 gimple_stmt_iterator si;
2134 gcc_assert (is_gimple_assign (stmt));
2136 if (gimple_assign_rhs1 (stmt) == op)
2137 other_op = gimple_assign_rhs2 (stmt);
2138 else
2139 other_op = gimple_assign_rhs1 (stmt);
2141 si = gsi_for_stmt (stmt);
2142 gimple_assign_set_rhs_from_tree (&si, other_op);
2144 /* We should not have reallocated STMT. */
2145 gcc_assert (gsi_stmt (si) == stmt);
2147 update_stmt (stmt);
2150 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2151 are combined in a single statement, and returns this statement. */
2153 static gimple
2154 reassociate_to_the_same_stmt (tree name1, tree name2)
2156 gimple stmt1, stmt2, root1, root2, s1, s2;
2157 gimple new_stmt, tmp_stmt;
2158 tree new_name, tmp_name, var, r1, r2;
2159 unsigned dist1, dist2;
2160 enum tree_code code;
2161 tree type = TREE_TYPE (name1);
2162 gimple_stmt_iterator bsi;
2164 stmt1 = find_use_stmt (&name1);
2165 stmt2 = find_use_stmt (&name2);
2166 root1 = find_associative_operation_root (stmt1, &dist1);
2167 root2 = find_associative_operation_root (stmt2, &dist2);
2168 code = gimple_assign_rhs_code (stmt1);
2170 gcc_assert (root1 && root2 && root1 == root2
2171 && code == gimple_assign_rhs_code (stmt2));
2173 /* Find the root of the nearest expression in that both NAME1 and NAME2
2174 are used. */
2175 r1 = name1;
2176 s1 = stmt1;
2177 r2 = name2;
2178 s2 = stmt2;
2180 while (dist1 > dist2)
2182 s1 = find_use_stmt (&r1);
2183 r1 = gimple_assign_lhs (s1);
2184 dist1--;
2186 while (dist2 > dist1)
2188 s2 = find_use_stmt (&r2);
2189 r2 = gimple_assign_lhs (s2);
2190 dist2--;
2193 while (s1 != s2)
2195 s1 = find_use_stmt (&r1);
2196 r1 = gimple_assign_lhs (s1);
2197 s2 = find_use_stmt (&r2);
2198 r2 = gimple_assign_lhs (s2);
2201 /* Remove NAME1 and NAME2 from the statements in that they are used
2202 currently. */
2203 remove_name_from_operation (stmt1, name1);
2204 remove_name_from_operation (stmt2, name2);
2206 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2207 combine it with the rhs of S1. */
2208 var = create_tmp_reg (type, "predreastmp");
2209 add_referenced_var (var);
2210 new_name = make_ssa_name (var, NULL);
2211 new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2213 var = create_tmp_reg (type, "predreastmp");
2214 add_referenced_var (var);
2215 tmp_name = make_ssa_name (var, NULL);
2217 /* Rhs of S1 may now be either a binary expression with operation
2218 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2219 so that name1 or name2 was removed from it). */
2220 tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2221 tmp_name,
2222 gimple_assign_rhs1 (s1),
2223 gimple_assign_rhs2 (s1));
2225 bsi = gsi_for_stmt (s1);
2226 gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2227 s1 = gsi_stmt (bsi);
2228 update_stmt (s1);
2230 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2231 gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2233 return new_stmt;
2236 /* Returns the statement that combines references R1 and R2. In case R1
2237 and R2 are not used in the same statement, but they are used with an
2238 associative and commutative operation in the same expression, reassociate
2239 the expression so that they are used in the same statement. */
2241 static gimple
2242 stmt_combining_refs (dref r1, dref r2)
2244 gimple stmt1, stmt2;
2245 tree name1 = name_for_ref (r1);
2246 tree name2 = name_for_ref (r2);
2248 stmt1 = find_use_stmt (&name1);
2249 stmt2 = find_use_stmt (&name2);
2250 if (stmt1 == stmt2)
2251 return stmt1;
2253 return reassociate_to_the_same_stmt (name1, name2);
2256 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2257 description of the new chain is returned, otherwise we return NULL. */
2259 static chain_p
2260 combine_chains (chain_p ch1, chain_p ch2)
2262 dref r1, r2, nw;
2263 enum tree_code op = ERROR_MARK;
2264 bool swap = false;
2265 chain_p new_chain;
2266 unsigned i;
2267 gimple root_stmt;
2268 tree rslt_type = NULL_TREE;
2270 if (ch1 == ch2)
2271 return NULL;
2272 if (ch1->length != ch2->length)
2273 return NULL;
2275 if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
2276 return NULL;
2278 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2279 && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2281 if (r1->distance != r2->distance)
2282 return NULL;
2284 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2285 return NULL;
2288 if (swap)
2290 chain_p tmp = ch1;
2291 ch1 = ch2;
2292 ch2 = tmp;
2295 new_chain = XCNEW (struct chain);
2296 new_chain->type = CT_COMBINATION;
2297 new_chain->op = op;
2298 new_chain->ch1 = ch1;
2299 new_chain->ch2 = ch2;
2300 new_chain->rslt_type = rslt_type;
2301 new_chain->length = ch1->length;
2303 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2304 && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2306 nw = XCNEW (struct dref_d);
2307 nw->stmt = stmt_combining_refs (r1, r2);
2308 nw->distance = r1->distance;
2310 VEC_safe_push (dref, heap, new_chain->refs, nw);
2313 new_chain->has_max_use_after = false;
2314 root_stmt = get_chain_root (new_chain)->stmt;
2315 for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
2317 if (nw->distance == new_chain->length
2318 && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2320 new_chain->has_max_use_after = true;
2321 break;
2325 ch1->combined = true;
2326 ch2->combined = true;
2327 return new_chain;
2330 /* Try to combine the CHAINS. */
2332 static void
2333 try_combine_chains (VEC (chain_p, heap) **chains)
2335 unsigned i, j;
2336 chain_p ch1, ch2, cch;
2337 VEC (chain_p, heap) *worklist = NULL;
2339 for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++)
2340 if (chain_can_be_combined_p (ch1))
2341 VEC_safe_push (chain_p, heap, worklist, ch1);
2343 while (!VEC_empty (chain_p, worklist))
2345 ch1 = VEC_pop (chain_p, worklist);
2346 if (!chain_can_be_combined_p (ch1))
2347 continue;
2349 for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++)
2351 if (!chain_can_be_combined_p (ch2))
2352 continue;
2354 cch = combine_chains (ch1, ch2);
2355 if (cch)
2357 VEC_safe_push (chain_p, heap, worklist, cch);
2358 VEC_safe_push (chain_p, heap, *chains, cch);
2359 break;
2365 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2366 impossible because one of these initializers may trap, true otherwise. */
2368 static bool
2369 prepare_initializers_chain (struct loop *loop, chain_p chain)
2371 unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2372 struct data_reference *dr = get_chain_root (chain)->ref;
2373 tree init;
2374 gimple_seq stmts;
2375 dref laref;
2376 edge entry = loop_preheader_edge (loop);
2378 /* Find the initializers for the variables, and check that they cannot
2379 trap. */
2380 chain->inits = VEC_alloc (tree, heap, n);
2381 for (i = 0; i < n; i++)
2382 VEC_quick_push (tree, chain->inits, NULL_TREE);
2384 /* If we have replaced some looparound phi nodes, use their initializers
2385 instead of creating our own. */
2386 for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++)
2388 if (gimple_code (laref->stmt) != GIMPLE_PHI)
2389 continue;
2391 gcc_assert (laref->distance > 0);
2392 VEC_replace (tree, chain->inits, n - laref->distance,
2393 PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
2396 for (i = 0; i < n; i++)
2398 if (VEC_index (tree, chain->inits, i) != NULL_TREE)
2399 continue;
2401 init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
2402 if (!init)
2403 return false;
2405 if (!chain->all_always_accessed && tree_could_trap_p (init))
2406 return false;
2408 init = force_gimple_operand (init, &stmts, false, NULL_TREE);
2409 if (stmts)
2410 gsi_insert_seq_on_edge_immediate (entry, stmts);
2412 VEC_replace (tree, chain->inits, i, init);
2415 return true;
2418 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2419 be used because the initializers might trap. */
2421 static void
2422 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
2424 chain_p chain;
2425 unsigned i;
2427 for (i = 0; i < VEC_length (chain_p, chains); )
2429 chain = VEC_index (chain_p, chains, i);
2430 if (prepare_initializers_chain (loop, chain))
2431 i++;
2432 else
2434 release_chain (chain);
2435 VEC_unordered_remove (chain_p, chains, i);
2440 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2441 unrolled. */
2443 static bool
2444 tree_predictive_commoning_loop (struct loop *loop)
2446 VEC (data_reference_p, heap) *datarefs;
2447 VEC (ddr_p, heap) *dependences;
2448 struct component *components;
2449 VEC (chain_p, heap) *chains = NULL;
2450 unsigned unroll_factor;
2451 struct tree_niter_desc desc;
2452 bool unroll = false;
2453 edge exit;
2454 bitmap tmp_vars;
2456 if (dump_file && (dump_flags & TDF_DETAILS))
2457 fprintf (dump_file, "Processing loop %d\n", loop->num);
2459 /* Find the data references and split them into components according to their
2460 dependence relations. */
2461 datarefs = VEC_alloc (data_reference_p, heap, 10);
2462 dependences = VEC_alloc (ddr_p, heap, 10);
2463 compute_data_dependences_for_loop (loop, true, &datarefs, &dependences);
2464 if (dump_file && (dump_flags & TDF_DETAILS))
2465 dump_data_dependence_relations (dump_file, dependences);
2467 components = split_data_refs_to_components (loop, datarefs, dependences);
2468 free_dependence_relations (dependences);
2469 if (!components)
2471 free_data_refs (datarefs);
2472 return false;
2475 if (dump_file && (dump_flags & TDF_DETAILS))
2477 fprintf (dump_file, "Initial state:\n\n");
2478 dump_components (dump_file, components);
2481 /* Find the suitable components and split them into chains. */
2482 components = filter_suitable_components (loop, components);
2484 tmp_vars = BITMAP_ALLOC (NULL);
2485 looparound_phis = BITMAP_ALLOC (NULL);
2486 determine_roots (loop, components, &chains);
2487 release_components (components);
2489 if (!chains)
2491 if (dump_file && (dump_flags & TDF_DETAILS))
2492 fprintf (dump_file,
2493 "Predictive commoning failed: no suitable chains\n");
2494 goto end;
2496 prepare_initializers (loop, chains);
2498 /* Try to combine the chains that are always worked with together. */
2499 try_combine_chains (&chains);
2501 if (dump_file && (dump_flags & TDF_DETAILS))
2503 fprintf (dump_file, "Before commoning:\n\n");
2504 dump_chains (dump_file, chains);
2507 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2508 that its number of iterations is divisible by the factor. */
2509 unroll_factor = determine_unroll_factor (chains);
2510 scev_reset ();
2511 unroll = (unroll_factor > 1
2512 && can_unroll_loop_p (loop, unroll_factor, &desc));
2513 exit = single_dom_exit (loop);
2515 /* Execute the predictive commoning transformations, and possibly unroll the
2516 loop. */
2517 if (unroll)
2519 struct epcc_data dta;
2521 if (dump_file && (dump_flags & TDF_DETAILS))
2522 fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2524 dta.chains = chains;
2525 dta.tmp_vars = tmp_vars;
2527 update_ssa (TODO_update_ssa_only_virtuals);
2529 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2530 execute_pred_commoning_cbck is called may cause phi nodes to be
2531 reallocated, which is a problem since CHAINS may point to these
2532 statements. To fix this, we store the ssa names defined by the
2533 phi nodes here instead of the phi nodes themselves, and restore
2534 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2535 replace_phis_by_defined_names (chains);
2537 tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2538 execute_pred_commoning_cbck, &dta);
2539 eliminate_temp_copies (loop, tmp_vars);
2541 else
2543 if (dump_file && (dump_flags & TDF_DETAILS))
2544 fprintf (dump_file,
2545 "Executing predictive commoning without unrolling.\n");
2546 execute_pred_commoning (loop, chains, tmp_vars);
2549 end: ;
2550 release_chains (chains);
2551 free_data_refs (datarefs);
2552 BITMAP_FREE (tmp_vars);
2553 BITMAP_FREE (looparound_phis);
2555 free_affine_expand_cache (&name_expansions);
2557 return unroll;
2560 /* Runs predictive commoning. */
2562 unsigned
2563 tree_predictive_commoning (void)
2565 bool unrolled = false;
2566 struct loop *loop;
2567 loop_iterator li;
2568 unsigned ret = 0;
2570 initialize_original_copy_tables ();
2571 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
2572 if (optimize_loop_for_speed_p (loop))
2574 unrolled |= tree_predictive_commoning_loop (loop);
2577 if (unrolled)
2579 scev_reset ();
2580 ret = TODO_cleanup_cfg;
2582 free_original_copy_tables ();
2584 return ret;