1 /* Predictive commoning.
2 Copyright (C) 2005 Free Software Foundation, Inc.
4 This file is part of GCC.
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 2, or (at your option) any
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
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];
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
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
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++)
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)
160 TODO -- stores killing other stores can be taken into account, e.g.,
161 for (i = 0; i < n; i++)
171 for (i = 0; i < n; i++)
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. */
190 #include "coretypes.h"
195 #include "tree-flow.h"
197 #include "tree-data-ref.h"
198 #include "tree-scalar-evolution.h"
199 #include "tree-chrec.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
209 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
211 /* Data references. */
215 /* The reference itself. */
216 struct data_reference *ref;
218 /* The statement in that the reference appears. */
221 /* Distance of the reference from the root of the chain (in number of
222 iterations of the loop). */
225 /* Number of iterations offset from the first reference in the component. */
228 /* Number of the reference in a component, in dominance ordering. */
231 /* True if the memory reference is always accessed when the loop is
233 unsigned always_accessed : 1;
237 DEF_VEC_ALLOC_P (dref, heap);
239 /* Type of the chain of the references. */
243 /* The addresses of the references in the chain are constant. */
246 /* There are only loads in the chain. */
249 /* Root of the chain is store, the rest are loads. */
252 /* A combination of two chains. */
256 /* Chains of data references. */
260 /* Type of the chain. */
261 enum chain_type type;
263 /* For combination chains, the operator and the two chains that are
264 combined, and the type of the result. */
265 enum tree_code operator;
267 struct chain *ch1, *ch2;
269 /* The references in the chain. */
270 VEC(dref,heap) *refs;
272 /* The maximum distance of the reference in the chain from the root. */
275 /* The variables used to copy the value throughout iterations. */
276 VEC(tree,heap) *vars;
278 /* Initializers for the variables. */
279 VEC(tree,heap) *inits;
281 /* True if there is a use of a variable with the maximal distance
282 that comes after the root in the loop. */
283 unsigned has_max_use_after : 1;
285 /* True if all the memory references in the chain are always accessed. */
286 unsigned all_always_accessed : 1;
288 /* True if this chain was combined together with some other chain. */
289 unsigned combined : 1;
293 DEF_VEC_ALLOC_P (chain_p, heap);
295 /* Describes the knowledge about the step of the memory references in
300 /* The step is zero. */
303 /* The step is nonzero. */
306 /* The step may or may not be nonzero. */
310 /* Components of the data dependence graph. */
314 /* The references in the component. */
315 VEC(dref,heap) *refs;
317 /* What we know about the step of the references in the component. */
318 enum ref_step_type comp_step;
320 /* Next component in the list. */
321 struct component *next;
324 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
326 static bitmap looparound_phis;
328 /* Cache used by tree_to_aff_combination_expand. */
330 static struct pointer_map_t *name_expansions;
332 /* Dumps data reference REF to FILE. */
334 extern void dump_dref (FILE *, dref);
336 dump_dref (FILE *file, dref ref)
341 print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
342 fprintf (file, " (id %u%s)\n", ref->pos,
343 DR_IS_READ (ref->ref) ? "" : ", write");
345 fprintf (file, " offset ");
346 dump_double_int (file, ref->offset, false);
347 fprintf (file, "\n");
349 fprintf (file, " distance %u\n", ref->distance);
353 if (TREE_CODE (ref->stmt) == PHI_NODE)
354 fprintf (file, " looparound ref\n");
356 fprintf (file, " combination ref\n");
357 fprintf (file, " in statement ");
358 print_generic_expr (file, ref->stmt, TDF_SLIM);
359 fprintf (file, "\n");
360 fprintf (file, " distance %u\n", ref->distance);
365 /* Dumps CHAIN to FILE. */
367 extern void dump_chain (FILE *, chain_p);
369 dump_chain (FILE *file, chain_p chain)
372 const char *chain_type;
379 chain_type = "Load motion";
383 chain_type = "Loads-only";
387 chain_type = "Store-loads";
391 chain_type = "Combination";
398 fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
399 chain->combined ? " (combined)" : "");
400 if (chain->type != CT_INVARIANT)
401 fprintf (file, " max distance %u%s\n", chain->length,
402 chain->has_max_use_after ? "" : ", may reuse first");
404 if (chain->type == CT_COMBINATION)
406 fprintf (file, " equal to %p %s %p in type ",
407 (void *) chain->ch1, op_symbol_code (chain->operator),
408 (void *) chain->ch2);
409 print_generic_expr (file, chain->rslt_type, TDF_SLIM);
410 fprintf (file, "\n");
415 fprintf (file, " vars");
416 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
419 print_generic_expr (file, var, TDF_SLIM);
421 fprintf (file, "\n");
426 fprintf (file, " inits");
427 for (i = 0; VEC_iterate (tree, chain->inits, i, var); i++)
430 print_generic_expr (file, var, TDF_SLIM);
432 fprintf (file, "\n");
435 fprintf (file, " references:\n");
436 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
439 fprintf (file, "\n");
442 /* Dumps CHAINS to FILE. */
444 extern void dump_chains (FILE *, VEC (chain_p, heap) *);
446 dump_chains (FILE *file, VEC (chain_p, heap) *chains)
451 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
452 dump_chain (file, chain);
455 /* Dumps COMP to FILE. */
457 extern void dump_component (FILE *, struct component *);
459 dump_component (FILE *file, struct component *comp)
464 fprintf (file, "Component%s:\n",
465 comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
466 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
468 fprintf (file, "\n");
471 /* Dumps COMPS to FILE. */
473 extern void dump_components (FILE *, struct component *);
475 dump_components (FILE *file, struct component *comps)
477 struct component *comp;
479 for (comp = comps; comp; comp = comp->next)
480 dump_component (file, comp);
483 /* Frees a chain CHAIN. */
486 release_chain (chain_p chain)
494 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)
497 VEC_free (dref, heap, chain->refs);
498 VEC_free (tree, heap, chain->vars);
499 VEC_free (tree, heap, chain->inits);
507 release_chains (VEC (chain_p, heap) *chains)
512 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
513 release_chain (chain);
514 VEC_free (chain_p, heap, chains);
517 /* Frees a component COMP. */
520 release_component (struct component *comp)
522 VEC_free (dref, heap, comp->refs);
526 /* Frees list of components COMPS. */
529 release_components (struct component *comps)
531 struct component *act, *next;
533 for (act = comps; act; act = next)
536 release_component (act);
540 /* Finds a root of tree given by FATHERS containing A, and performs path
544 component_of (unsigned fathers[], unsigned a)
548 for (root = a; root != fathers[root]; root = fathers[root])
551 for (; a != root; a = n)
560 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
561 components, A and B are components to merge. */
564 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)
566 unsigned ca = component_of (fathers, a);
567 unsigned cb = component_of (fathers, b);
572 if (sizes[ca] < sizes[cb])
574 sizes[cb] += sizes[ca];
579 sizes[ca] += sizes[cb];
584 /* Returns true if A is a reference that is suitable for predictive commoning
585 in the innermost loop that contains it. REF_STEP is set according to the
586 step of the reference A. */
589 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
591 tree ref = DR_REF (a), step = DR_STEP (a);
594 || !is_gimple_reg_type (TREE_TYPE (ref)))
597 if (integer_zerop (step))
598 *ref_step = RS_INVARIANT;
599 else if (integer_nonzerop (step))
600 *ref_step = RS_NONZERO;
607 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
610 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)
614 tree_to_aff_combination_expand (DR_OFFSET (dr), sizetype, offset,
616 aff_combination_const (&delta, sizetype, tree_to_double_int (DR_INIT (dr)));
617 aff_combination_add (offset, &delta);
620 /* Determines number of iterations of the innermost enclosing loop before B
621 refers to exactly the same location as A and stores it to OFF. If A and
622 B do not have the same step, they never meet, or anything else fails,
623 returns false, otherwise returns true. Both A and B are assumed to
624 satisfy suitable_reference_p. */
627 determine_offset (struct data_reference *a, struct data_reference *b,
630 aff_tree diff, baseb, step;
633 /* Check that both the references access the location in the same type. */
634 typea = TREE_TYPE (DR_REF (a));
635 typeb = TREE_TYPE (DR_REF (b));
636 if (!tree_ssa_useless_type_conversion_1 (typeb, typea))
639 /* Check whether the base address and the step of both references is the
641 if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
642 || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
645 if (integer_zerop (DR_STEP (a)))
647 /* If the references have loop invariant address, check that they access
648 exactly the same location. */
649 *off = double_int_zero;
650 return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
651 && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
654 /* Compare the offsets of the addresses, and check whether the difference
655 is a multiple of step. */
656 aff_combination_dr_offset (a, &diff);
657 aff_combination_dr_offset (b, &baseb);
658 aff_combination_scale (&baseb, double_int_minus_one);
659 aff_combination_add (&diff, &baseb);
661 tree_to_aff_combination_expand (DR_STEP (a), sizetype,
662 &step, &name_expansions);
663 return aff_combination_constant_multiple_p (&diff, &step, off);
666 /* Returns the last basic block in LOOP for that we are sure that
667 it is executed whenever the loop is entered. */
670 last_always_executed_block (struct loop *loop)
673 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
675 basic_block last = loop->latch;
677 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
678 last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
679 VEC_free (edge, heap, exits);
684 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
686 static struct component *
687 split_data_refs_to_components (struct loop *loop,
688 VEC (data_reference_p, heap) *datarefs,
689 VEC (ddr_p, heap) *depends)
691 unsigned i, n = VEC_length (data_reference_p, datarefs);
692 unsigned ca, ia, ib, bad;
693 unsigned *comp_father = XNEWVEC (unsigned, n + 1);
694 unsigned *comp_size = XNEWVEC (unsigned, n + 1);
695 struct component **comps;
696 struct data_reference *dr, *dra, *drb;
697 struct data_dependence_relation *ddr;
698 struct component *comp_list = NULL, *comp;
700 basic_block last_always_executed = last_always_executed_block (loop);
702 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
706 /* A fake reference for call or asm_expr that may clobber memory;
710 dr->aux = (void *) (size_t) i;
715 /* A component reserved for the "bad" data references. */
719 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
721 enum ref_step_type dummy;
723 if (!suitable_reference_p (dr, &dummy))
725 ia = (unsigned) (size_t) dr->aux;
726 merge_comps (comp_father, comp_size, n, ia);
730 for (i = 0; VEC_iterate (ddr_p, depends, i, ddr); i++)
732 double_int dummy_off;
734 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
739 ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
740 ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
744 bad = component_of (comp_father, n);
746 /* If both A and B are reads, we may ignore unsuitable dependences. */
747 if (DR_IS_READ (dra) && DR_IS_READ (drb)
748 && (ia == bad || ib == bad
749 || !determine_offset (dra, drb, &dummy_off)))
752 merge_comps (comp_father, comp_size, ia, ib);
755 comps = XCNEWVEC (struct component *, n);
756 bad = component_of (comp_father, n);
757 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
759 ia = (unsigned) (size_t) dr->aux;
760 ca = component_of (comp_father, ia);
767 comp = XCNEW (struct component);
768 comp->refs = VEC_alloc (dref, heap, comp_size[ca]);
772 dataref = XCNEW (struct dref);
774 dataref->stmt = DR_STMT (dr);
775 dataref->offset = double_int_zero;
776 dataref->distance = 0;
778 dataref->always_accessed
779 = dominated_by_p (CDI_DOMINATORS, last_always_executed,
780 bb_for_stmt (dataref->stmt));
781 dataref->pos = VEC_length (dref, comp->refs);
782 VEC_quick_push (dref, comp->refs, dataref);
785 for (i = 0; i < n; i++)
790 comp->next = comp_list;
802 /* Returns true if the component COMP satisfies the conditions
803 described in 2) at the beginning of this file. LOOP is the current
807 suitable_component_p (struct loop *loop, struct component *comp)
811 basic_block ba, bp = loop->header;
812 bool ok, has_write = false;
814 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
816 ba = bb_for_stmt (a->stmt);
818 if (!just_once_each_iteration_p (loop, ba))
821 gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
824 if (!DR_IS_READ (a->ref))
828 first = VEC_index (dref, comp->refs, 0);
829 ok = suitable_reference_p (first->ref, &comp->comp_step);
831 first->offset = double_int_zero;
833 for (i = 1; VEC_iterate (dref, comp->refs, i, a); i++)
835 if (!determine_offset (first->ref, a->ref, &a->offset))
838 #ifdef ENABLE_CHECKING
840 enum ref_step_type a_step;
841 ok = suitable_reference_p (a->ref, &a_step);
842 gcc_assert (ok && a_step == comp->comp_step);
847 /* If there is a write inside the component, we must know whether the
848 step is nonzero or not -- we would not otherwise be able to recognize
849 whether the value accessed by reads comes from the OFFSET-th iteration
850 or the previous one. */
851 if (has_write && comp->comp_step == RS_ANY)
857 /* Check the conditions on references inside each of components COMPS,
858 and remove the unsuitable components from the list. The new list
859 of components is returned. The conditions are described in 2) at
860 the beginning of this file. LOOP is the current loop. */
862 static struct component *
863 filter_suitable_components (struct loop *loop, struct component *comps)
865 struct component **comp, *act;
867 for (comp = &comps; *comp; )
870 if (suitable_component_p (loop, act))
875 release_component (act);
882 /* Compares two drefs A and B by their offset and position. Callback for
886 order_drefs (const void *a, const void *b)
890 int offcmp = double_int_scmp ((*da)->offset, (*db)->offset);
895 return (*da)->pos - (*db)->pos;
898 /* Returns root of the CHAIN. */
901 get_chain_root (chain_p chain)
903 return VEC_index (dref, chain->refs, 0);
906 /* Adds REF to the chain CHAIN. */
909 add_ref_to_chain (chain_p chain, dref ref)
911 dref root = get_chain_root (chain);
914 gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0);
915 dist = double_int_add (ref->offset, double_int_neg (root->offset));
916 if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0)
918 gcc_assert (double_int_fits_in_uhwi_p (dist));
920 VEC_safe_push (dref, heap, chain->refs, ref);
922 ref->distance = double_int_to_uhwi (dist);
924 if (ref->distance >= chain->length)
926 chain->length = ref->distance;
927 chain->has_max_use_after = false;
930 if (ref->distance == chain->length
931 && ref->pos > root->pos)
932 chain->has_max_use_after = true;
934 chain->all_always_accessed &= ref->always_accessed;
937 /* Returns the chain for invariant component COMP. */
940 make_invariant_chain (struct component *comp)
942 chain_p chain = XCNEW (struct chain);
946 chain->type = CT_INVARIANT;
948 chain->all_always_accessed = true;
950 for (i = 0; VEC_iterate (dref, comp->refs, i, ref); i++)
952 VEC_safe_push (dref, heap, chain->refs, ref);
953 chain->all_always_accessed &= ref->always_accessed;
959 /* Make a new chain rooted at REF. */
962 make_rooted_chain (dref ref)
964 chain_p chain = XCNEW (struct chain);
966 chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
968 VEC_safe_push (dref, heap, chain->refs, ref);
969 chain->all_always_accessed = ref->always_accessed;
976 /* Returns true if CHAIN is not trivial. */
979 nontrivial_chain_p (chain_p chain)
981 return chain != NULL && VEC_length (dref, chain->refs) > 1;
984 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
988 name_for_ref (dref ref)
992 if (TREE_CODE (ref->stmt) == GIMPLE_MODIFY_STMT)
994 if (!ref->ref || DR_IS_READ (ref->ref))
995 name = GIMPLE_STMT_OPERAND (ref->stmt, 0);
997 name = GIMPLE_STMT_OPERAND (ref->stmt, 1);
1000 name = PHI_RESULT (ref->stmt);
1002 return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1005 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1006 iterations of the innermost enclosing loop). */
1009 valid_initializer_p (struct data_reference *ref,
1010 unsigned distance, struct data_reference *root)
1012 aff_tree diff, base, step;
1015 if (!DR_BASE_ADDRESS (ref))
1018 /* Both REF and ROOT must be accessing the same object. */
1019 if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1022 /* The initializer is defined outside of loop, hence its address must be
1023 invariant inside the loop. */
1024 gcc_assert (integer_zerop (DR_STEP (ref)));
1026 /* If the address of the reference is invariant, initializer must access
1027 exactly the same location. */
1028 if (integer_zerop (DR_STEP (root)))
1029 return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1030 && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1032 /* Verify that this index of REF is equal to the root's index at
1033 -DISTANCE-th iteration. */
1034 aff_combination_dr_offset (root, &diff);
1035 aff_combination_dr_offset (ref, &base);
1036 aff_combination_scale (&base, double_int_minus_one);
1037 aff_combination_add (&diff, &base);
1039 tree_to_aff_combination_expand (DR_STEP (root), sizetype, &step,
1041 if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1044 if (!double_int_equal_p (off, uhwi_to_double_int (distance)))
1050 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1051 initial value is correct (equal to initial value of REF shifted by one
1052 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1053 is the root of the current chain. */
1056 find_looparound_phi (struct loop *loop, dref ref, dref root)
1058 tree name, phi, init, init_stmt, init_ref;
1059 edge latch = loop_latch_edge (loop);
1060 struct data_reference init_dr;
1062 if (TREE_CODE (ref->stmt) == GIMPLE_MODIFY_STMT)
1064 if (DR_IS_READ (ref->ref))
1065 name = GIMPLE_STMT_OPERAND (ref->stmt, 0);
1067 name = GIMPLE_STMT_OPERAND (ref->stmt, 1);
1070 name = PHI_RESULT (ref->stmt);
1074 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1075 if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1081 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1082 if (TREE_CODE (init) != SSA_NAME)
1084 init_stmt = SSA_NAME_DEF_STMT (init);
1085 if (TREE_CODE (init_stmt) != GIMPLE_MODIFY_STMT)
1087 gcc_assert (GIMPLE_STMT_OPERAND (init_stmt, 0) == init);
1089 init_ref = GIMPLE_STMT_OPERAND (init_stmt, 1);
1090 if (!REFERENCE_CLASS_P (init_ref)
1091 && !DECL_P (init_ref))
1094 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1095 loop enclosing PHI). */
1096 memset (&init_dr, 0, sizeof (struct data_reference));
1097 DR_REF (&init_dr) = init_ref;
1098 DR_STMT (&init_dr) = phi;
1099 dr_analyze_innermost (&init_dr);
1101 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1107 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1110 insert_looparound_copy (chain_p chain, dref ref, tree phi)
1112 dref nw = XCNEW (struct dref), aref;
1116 nw->distance = ref->distance + 1;
1117 nw->always_accessed = 1;
1119 for (i = 0; VEC_iterate (dref, chain->refs, i, aref); i++)
1120 if (aref->distance >= nw->distance)
1122 VEC_safe_insert (dref, heap, chain->refs, i, nw);
1124 if (nw->distance > chain->length)
1126 chain->length = nw->distance;
1127 chain->has_max_use_after = false;
1131 /* For references in CHAIN that are copied around the LOOP (created previously
1132 by PRE, or by user), add the results of such copies to the chain. This
1133 enables us to remove the copies by unrolling, and may need less registers
1134 (also, it may allow us to combine chains together). */
1137 add_looparound_copies (struct loop *loop, chain_p chain)
1140 dref ref, root = get_chain_root (chain);
1143 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)
1145 phi = find_looparound_phi (loop, ref, root);
1149 bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1150 insert_looparound_copy (chain, ref, phi);
1154 /* Find roots of the values and determine distances in the component COMP.
1155 The references are redistributed into CHAINS. LOOP is the current
1159 determine_roots_comp (struct loop *loop,
1160 struct component *comp,
1161 VEC (chain_p, heap) **chains)
1165 chain_p chain = NULL;
1167 /* Invariants are handled specially. */
1168 if (comp->comp_step == RS_INVARIANT)
1170 chain = make_invariant_chain (comp);
1171 VEC_safe_push (chain_p, heap, *chains, chain);
1175 qsort (VEC_address (dref, comp->refs), VEC_length (dref, comp->refs),
1176 sizeof (dref), order_drefs);
1178 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
1180 if (!chain || !DR_IS_READ (a->ref))
1182 if (nontrivial_chain_p (chain))
1183 VEC_safe_push (chain_p, heap, *chains, chain);
1185 release_chain (chain);
1186 chain = make_rooted_chain (a);
1190 add_ref_to_chain (chain, a);
1193 if (nontrivial_chain_p (chain))
1195 add_looparound_copies (loop, chain);
1196 VEC_safe_push (chain_p, heap, *chains, chain);
1199 release_chain (chain);
1202 /* Find roots of the values and determine distances in components COMPS, and
1203 separates the references to CHAINS. LOOP is the current loop. */
1206 determine_roots (struct loop *loop,
1207 struct component *comps, VEC (chain_p, heap) **chains)
1209 struct component *comp;
1211 for (comp = comps; comp; comp = comp->next)
1212 determine_roots_comp (loop, comp, chains);
1215 /* Replace the reference in statement STMT with temporary variable
1216 NEW. If SET is true, NEW is instead initialized to the value of
1217 the reference in the statement. IN_LHS is true if the reference
1218 is in the lhs of STMT, false if it is in rhs. */
1221 replace_ref_with (tree stmt, tree new, bool set, bool in_lhs)
1224 block_stmt_iterator bsi;
1226 if (TREE_CODE (stmt) == PHI_NODE)
1228 gcc_assert (!in_lhs && !set);
1230 val = PHI_RESULT (stmt);
1231 bsi = bsi_after_labels (bb_for_stmt (stmt));
1232 remove_phi_node (stmt, NULL_TREE, false);
1234 /* Turn the phi node into GIMPLE_MODIFY_STMT. */
1235 new_stmt = build_gimple_modify_stmt (val, new);
1236 SSA_NAME_DEF_STMT (val) = new_stmt;
1237 bsi_insert_before (&bsi, new_stmt, BSI_NEW_STMT);
1241 /* Since the reference is of gimple_reg type, it should only
1242 appear as lhs or rhs of modify statement. */
1243 gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
1245 /* If we do not need to initialize NEW, just replace the use of OLD. */
1248 gcc_assert (!in_lhs);
1249 GIMPLE_STMT_OPERAND (stmt, 1) = new;
1254 bsi = bsi_for_stmt (stmt);
1257 val = GIMPLE_STMT_OPERAND (stmt, 1);
1266 (since the reference is of gimple_reg type, VAL is either gimple
1267 invariant or ssa name). */
1271 val = GIMPLE_STMT_OPERAND (stmt, 0);
1281 new_stmt = build_gimple_modify_stmt (new, unshare_expr (val));
1282 bsi_insert_after (&bsi, new_stmt, BSI_NEW_STMT);
1283 SSA_NAME_DEF_STMT (new) = new_stmt;
1286 /* Returns the reference to the address of REF in the ITER-th iteration of
1287 LOOP, or NULL if we fail to determine it (ITER may be negative). We
1288 try to preserve the original shape of the reference (not rewrite it
1289 as an indirect ref to the address), to make tree_could_trap_p in
1290 prepare_initializers_chain return false more often. */
1293 ref_at_iteration (struct loop *loop, tree ref, int iter)
1295 tree idx, *idx_p, type, val, op0 = NULL_TREE, ret;
1299 if (handled_component_p (ref))
1301 op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter);
1305 else if (!INDIRECT_REF_P (ref))
1306 return unshare_expr (ref);
1308 if (TREE_CODE (ref) == INDIRECT_REF)
1310 ret = build1 (INDIRECT_REF, TREE_TYPE (ref), NULL_TREE);
1311 idx = TREE_OPERAND (ref, 0);
1312 idx_p = &TREE_OPERAND (ret, 0);
1314 else if (TREE_CODE (ref) == COMPONENT_REF)
1316 /* Check that the offset is loop invariant. */
1317 if (TREE_OPERAND (ref, 2)
1318 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1321 return build3 (COMPONENT_REF, TREE_TYPE (ref), op0,
1322 unshare_expr (TREE_OPERAND (ref, 1)),
1323 unshare_expr (TREE_OPERAND (ref, 2)));
1325 else if (TREE_CODE (ref) == ARRAY_REF)
1327 /* Check that the lower bound and the step are loop invariant. */
1328 if (TREE_OPERAND (ref, 2)
1329 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1331 if (TREE_OPERAND (ref, 3)
1332 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3)))
1335 ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE,
1336 unshare_expr (TREE_OPERAND (ref, 2)),
1337 unshare_expr (TREE_OPERAND (ref, 3)));
1338 idx = TREE_OPERAND (ref, 1);
1339 idx_p = &TREE_OPERAND (ret, 1);
1344 ok = simple_iv (loop, first_stmt (loop->header), idx, &iv, true);
1347 iv.base = expand_simple_operations (iv.base);
1348 if (integer_zerop (iv.step))
1349 *idx_p = unshare_expr (iv.base);
1352 type = TREE_TYPE (iv.base);
1353 val = fold_build2 (MULT_EXPR, type, iv.step,
1354 build_int_cst_type (type, iter));
1355 val = fold_build2 (PLUS_EXPR, type, iv.base, val);
1356 *idx_p = unshare_expr (val);
1362 /* Get the initialization expression for the INDEX-th temporary variable
1366 get_init_expr (chain_p chain, unsigned index)
1368 if (chain->type == CT_COMBINATION)
1370 tree e1 = get_init_expr (chain->ch1, index);
1371 tree e2 = get_init_expr (chain->ch2, index);
1373 return fold_build2 (chain->operator, chain->rslt_type, e1, e2);
1376 return VEC_index (tree, chain->inits, index);
1379 /* Marks all virtual operands of statement STMT for renaming. */
1382 mark_virtual_ops_for_renaming (tree stmt)
1387 if (TREE_CODE (stmt) == PHI_NODE)
1392 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_ALL_VIRTUALS)
1394 if (TREE_CODE (var) == SSA_NAME)
1395 var = SSA_NAME_VAR (var);
1396 mark_sym_for_renaming (var);
1400 /* Calls mark_virtual_ops_for_renaming for all members of LIST. */
1403 mark_virtual_ops_for_renaming_list (tree list)
1405 tree_stmt_iterator tsi;
1407 for (tsi = tsi_start (list); !tsi_end_p (tsi); tsi_next (&tsi))
1408 mark_virtual_ops_for_renaming (tsi_stmt (tsi));
1411 /* Returns a new temporary variable used for the I-th variable carrying
1412 value of REF. The variable's uid is marked in TMP_VARS. */
1415 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1417 tree type = TREE_TYPE (ref);
1418 tree var = create_tmp_var (type, get_lsm_tmp_name (ref, i));
1420 /* We never access the components of the temporary variable in predictive
1422 if (TREE_CODE (type) == COMPLEX_TYPE
1423 || TREE_CODE (type) == VECTOR_TYPE)
1424 DECL_GIMPLE_REG_P (var) = 1;
1426 add_referenced_var (var);
1427 bitmap_set_bit (tmp_vars, DECL_UID (var));
1431 /* Creates the variables for CHAIN, as well as phi nodes for them and
1432 initialization on entry to LOOP. Uids of the newly created
1433 temporary variables are marked in TMP_VARS. */
1436 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1439 unsigned n = chain->length;
1440 dref root = get_chain_root (chain);
1441 bool reuse_first = !chain->has_max_use_after;
1442 tree ref, init, var, next, stmts;
1444 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1446 /* If N == 0, then all the references are within the single iteration. And
1447 since this is an nonempty chain, reuse_first cannot be true. */
1448 gcc_assert (n > 0 || !reuse_first);
1450 chain->vars = VEC_alloc (tree, heap, n + 1);
1452 if (chain->type == CT_COMBINATION)
1453 ref = GIMPLE_STMT_OPERAND (root->stmt, 0);
1455 ref = DR_REF (root->ref);
1457 for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1459 var = predcom_tmp_var (ref, i, tmp_vars);
1460 VEC_quick_push (tree, chain->vars, var);
1463 VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0));
1465 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
1466 VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL_TREE));
1468 for (i = 0; i < n; i++)
1470 var = VEC_index (tree, chain->vars, i);
1471 next = VEC_index (tree, chain->vars, i + 1);
1472 init = get_init_expr (chain, i);
1474 init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1477 mark_virtual_ops_for_renaming_list (stmts);
1478 bsi_insert_on_edge_immediate (entry, stmts);
1481 phi = create_phi_node (var, loop->header);
1482 SSA_NAME_DEF_STMT (var) = phi;
1483 add_phi_arg (phi, init, entry);
1484 add_phi_arg (phi, next, latch);
1488 /* Create the variables and initialization statement for root of chain
1489 CHAIN. Uids of the newly created temporary variables are marked
1493 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1495 dref root = get_chain_root (chain);
1496 bool in_lhs = (chain->type == CT_STORE_LOAD
1497 || chain->type == CT_COMBINATION);
1499 initialize_root_vars (loop, chain, tmp_vars);
1500 replace_ref_with (root->stmt,
1501 VEC_index (tree, chain->vars, chain->length),
1505 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1506 initialization on entry to LOOP if necessary. The ssa name for the variable
1507 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1508 around the loop is created. Uid of the newly created temporary variable
1509 is marked in TMP_VARS. INITS is the list containing the (single)
1513 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1514 VEC(tree, heap) **vars, VEC(tree, heap) *inits,
1518 tree ref = DR_REF (root->ref), init, var, next, stmts;
1520 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1522 /* Find the initializer for the variable, and check that it cannot
1524 init = VEC_index (tree, inits, 0);
1526 *vars = VEC_alloc (tree, heap, written ? 2 : 1);
1527 var = predcom_tmp_var (ref, 0, tmp_vars);
1528 VEC_quick_push (tree, *vars, var);
1530 VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0));
1532 for (i = 0; VEC_iterate (tree, *vars, i, var); i++)
1533 VEC_replace (tree, *vars, i, make_ssa_name (var, NULL_TREE));
1535 var = VEC_index (tree, *vars, 0);
1537 init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1540 mark_virtual_ops_for_renaming_list (stmts);
1541 bsi_insert_on_edge_immediate (entry, stmts);
1546 next = VEC_index (tree, *vars, 1);
1547 phi = create_phi_node (var, loop->header);
1548 SSA_NAME_DEF_STMT (var) = phi;
1549 add_phi_arg (phi, init, entry);
1550 add_phi_arg (phi, next, latch);
1554 init = build_gimple_modify_stmt (var, init);
1555 SSA_NAME_DEF_STMT (var) = init;
1556 mark_virtual_ops_for_renaming (init);
1557 bsi_insert_on_edge_immediate (entry, init);
1562 /* Execute load motion for references in chain CHAIN. Uids of the newly
1563 created temporary variables are marked in TMP_VARS. */
1566 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1568 VEC (tree, heap) *vars;
1570 unsigned n_writes = 0, ridx, i;
1573 gcc_assert (chain->type == CT_INVARIANT);
1574 gcc_assert (!chain->combined);
1575 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1576 if (!DR_IS_READ (a->ref))
1579 /* If there are no reads in the loop, there is nothing to do. */
1580 if (n_writes == VEC_length (dref, chain->refs))
1583 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1584 &vars, chain->inits, tmp_vars);
1587 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1589 bool is_read = DR_IS_READ (a->ref);
1590 mark_virtual_ops_for_renaming (a->stmt);
1592 if (!DR_IS_READ (a->ref))
1597 var = VEC_index (tree, vars, 0);
1598 var = make_ssa_name (SSA_NAME_VAR (var), NULL_TREE);
1599 VEC_replace (tree, vars, 0, var);
1605 replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
1606 !is_read, !is_read);
1609 VEC_free (tree, heap, vars);
1612 /* Returns the single statement in that NAME is used, excepting
1613 the looparound phi nodes contained in one of the chains. If there is no
1614 such statement, or more statements, NULL_TREE is returned. */
1617 single_nonlooparound_use (tree name)
1620 imm_use_iterator it;
1621 tree stmt, ret = NULL_TREE;
1623 FOR_EACH_IMM_USE_FAST (use, it, name)
1625 stmt = USE_STMT (use);
1627 if (TREE_CODE (stmt) == PHI_NODE)
1629 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1630 could not be processed anyway, so just fail for them. */
1631 if (bitmap_bit_p (looparound_phis,
1632 SSA_NAME_VERSION (PHI_RESULT (stmt))))
1637 else if (ret != NULL_TREE)
1646 /* Remove statement STMT, as well as the chain of assignments in that it is
1650 remove_stmt (tree stmt)
1654 if (TREE_CODE (stmt) == PHI_NODE)
1656 name = PHI_RESULT (stmt);
1657 next = single_nonlooparound_use (name);
1658 remove_phi_node (stmt, NULL_TREE, true);
1661 || TREE_CODE (next) != GIMPLE_MODIFY_STMT
1662 || GIMPLE_STMT_OPERAND (next, 1) != name)
1670 block_stmt_iterator bsi;
1672 bsi = bsi_for_stmt (stmt);
1674 name = GIMPLE_STMT_OPERAND (stmt, 0);
1675 gcc_assert (TREE_CODE (name) == SSA_NAME);
1677 next = single_nonlooparound_use (name);
1679 mark_virtual_ops_for_renaming (stmt);
1680 bsi_remove (&bsi, true);
1683 || TREE_CODE (next) != GIMPLE_MODIFY_STMT
1684 || GIMPLE_STMT_OPERAND (next, 1) != name)
1691 /* Perform the predictive commoning optimization for a chain CHAIN.
1692 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1695 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1702 if (chain->combined)
1704 /* For combined chains, just remove the statements that are used to
1705 compute the values of the expression (except for the root one). */
1706 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1707 remove_stmt (a->stmt);
1711 /* For non-combined chains, set up the variables that hold its value,
1712 and replace the uses of the original references by these
1714 root = get_chain_root (chain);
1715 mark_virtual_ops_for_renaming (root->stmt);
1717 initialize_root (loop, chain, tmp_vars);
1718 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1720 mark_virtual_ops_for_renaming (a->stmt);
1721 var = VEC_index (tree, chain->vars, chain->length - a->distance);
1722 replace_ref_with (a->stmt, var, false, false);
1727 /* Determines the unroll factor necessary to remove as many temporary variable
1728 copies as possible. CHAINS is the list of chains that will be
1732 determine_unroll_factor (VEC (chain_p, heap) *chains)
1735 unsigned factor = 1, af, nfactor, i;
1736 unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1738 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1740 if (chain->type == CT_INVARIANT || chain->combined)
1743 /* The best unroll factor for this chain is equal to the number of
1744 temporary variables that we create for it. */
1746 if (chain->has_max_use_after)
1749 nfactor = factor * af / gcd (factor, af);
1757 /* Perform the predictive commoning optimization for CHAINS.
1758 Uids of the newly created temporary variables are marked in TMP_VARS. */
1761 execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains,
1767 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1769 if (chain->type == CT_INVARIANT)
1770 execute_load_motion (loop, chain, tmp_vars);
1772 execute_pred_commoning_chain (loop, chain, tmp_vars);
1775 update_ssa (TODO_update_ssa_only_virtuals);
1778 /* For each reference in CHAINS, if its defining statement is
1779 ssa name, set it to phi node that defines it. */
1782 replace_phis_by_defined_names (VEC (chain_p, heap) *chains)
1788 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1789 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1791 gcc_assert (TREE_CODE (a->stmt) != SSA_NAME);
1792 if (TREE_CODE (a->stmt) == PHI_NODE)
1793 a->stmt = PHI_RESULT (a->stmt);
1797 /* For each reference in CHAINS, if its defining statement is
1798 phi node, set it to the ssa name that is defined by it. */
1801 replace_names_by_phis (VEC (chain_p, heap) *chains)
1807 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1808 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1809 if (TREE_CODE (a->stmt) == SSA_NAME)
1811 a->stmt = SSA_NAME_DEF_STMT (a->stmt);
1812 gcc_assert (TREE_CODE (a->stmt) == PHI_NODE);
1816 /* Wrapper over execute_pred_commoning, to pass it as a callback
1817 to tree_transform_and_unroll_loop. */
1821 VEC (chain_p, heap) *chains;
1826 execute_pred_commoning_cbck (struct loop *loop, void *data)
1828 struct epcc_data *dta = data;
1830 /* Restore phi nodes that were replaced by ssa names before
1831 tree_transform_and_unroll_loop (see detailed description in
1832 tree_predictive_commoning_loop). */
1833 replace_names_by_phis (dta->chains);
1834 execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1837 /* Returns true if we can and should unroll LOOP FACTOR times. Number
1838 of iterations of the loop is returned in NITER. */
1841 should_unroll_loop_p (struct loop *loop, unsigned factor,
1842 struct tree_niter_desc *niter)
1849 /* Check whether unrolling is possible. We only want to unroll loops
1850 for that we are able to determine number of iterations. We also
1851 want to split the extra iterations of the loop from its end,
1852 therefore we require that the loop has precisely one
1855 exit = single_dom_exit (loop);
1859 if (!number_of_iterations_exit (loop, exit, niter, false))
1862 /* And of course, we must be able to duplicate the loop. */
1863 if (!can_duplicate_loop_p (loop))
1866 /* The final loop should be small enough. */
1867 if (tree_num_loop_insns (loop, &eni_size_weights) * factor
1868 > (unsigned) PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS))
1874 /* Base NAME and all the names in the chain of phi nodes that use it
1875 on variable VAR. The phi nodes are recognized by being in the copies of
1876 the header of the LOOP. */
1879 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1882 imm_use_iterator iter;
1885 SSA_NAME_VAR (name) = var;
1890 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1892 if (TREE_CODE (stmt) == PHI_NODE
1893 && flow_bb_inside_loop_p (loop, bb_for_stmt (stmt)))
1896 BREAK_FROM_IMM_USE_STMT (iter);
1902 if (bb_for_stmt (phi) == loop->header)
1903 e = loop_latch_edge (loop);
1905 e = single_pred_edge (bb_for_stmt (stmt));
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. */
1918 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1921 tree phi, name, use, var, stmt;
1923 e = loop_latch_edge (loop);
1924 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
1926 name = PHI_RESULT (phi);
1927 var = SSA_NAME_VAR (name);
1928 if (!bitmap_bit_p (tmp_vars, DECL_UID (var)))
1930 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1931 gcc_assert (TREE_CODE (use) == SSA_NAME);
1933 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1934 stmt = SSA_NAME_DEF_STMT (use);
1935 while (TREE_CODE (stmt) == PHI_NODE
1936 /* In case we could not unroll the loop enough to eliminate
1937 all copies, we may reach the loop header before the defining
1938 statement (in that case, some register copies will be present
1939 in loop latch in the final code, corresponding to the newly
1940 created looparound phi nodes). */
1941 && bb_for_stmt (stmt) != loop->header)
1943 gcc_assert (single_pred_p (bb_for_stmt (stmt)));
1944 use = PHI_ARG_DEF (stmt, 0);
1945 stmt = SSA_NAME_DEF_STMT (use);
1948 base_names_in_chain_on (loop, use, var);
1952 /* Returns true if CHAIN is suitable to be combined. */
1955 chain_can_be_combined_p (chain_p chain)
1957 return (!chain->combined
1958 && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
1961 /* Returns the modify statement that uses NAME. Skips over assignment
1962 statements, NAME is replaced with the actual name used in the returned
1966 find_use_stmt (tree *name)
1968 tree stmt, rhs, lhs;
1970 /* Skip over assignments. */
1973 stmt = single_nonlooparound_use (*name);
1977 if (TREE_CODE (stmt) != GIMPLE_MODIFY_STMT)
1980 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
1981 if (TREE_CODE (lhs) != SSA_NAME)
1984 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
1992 || REFERENCE_CLASS_P (rhs)
1993 || TREE_CODE_LENGTH (TREE_CODE (rhs)) != 2)
1999 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
2002 may_reassociate_p (tree type, enum tree_code code)
2004 if (FLOAT_TYPE_P (type)
2005 && !flag_unsafe_math_optimizations)
2008 return (commutative_tree_code (code)
2009 && associative_tree_code (code));
2012 /* If the operation used in STMT is associative and commutative, go through the
2013 tree of the same operations and returns its root. Distance to the root
2014 is stored in DISTANCE. */
2017 find_associative_operation_root (tree stmt, unsigned *distance)
2019 tree rhs = GIMPLE_STMT_OPERAND (stmt, 1), lhs, next;
2020 enum tree_code code = TREE_CODE (rhs);
2023 if (!may_reassociate_p (TREE_TYPE (rhs), code))
2028 lhs = GIMPLE_STMT_OPERAND (stmt, 0);
2029 gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2031 next = find_use_stmt (&lhs);
2035 rhs = GIMPLE_STMT_OPERAND (next, 1);
2036 if (TREE_CODE (rhs) != code)
2048 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2049 is no such statement, returns NULL_TREE. In case the operation used on
2050 NAME1 and NAME2 is associative and commutative, returns the root of the
2051 tree formed by this operation instead of the statement that uses NAME1 or
2055 find_common_use_stmt (tree *name1, tree *name2)
2059 stmt1 = find_use_stmt (name1);
2063 stmt2 = find_use_stmt (name2);
2070 stmt1 = find_associative_operation_root (stmt1, NULL);
2073 stmt2 = find_associative_operation_root (stmt2, NULL);
2077 return (stmt1 == stmt2 ? stmt1 : NULL_TREE);
2080 /* Checks whether R1 and R2 are combined together using CODE, with the result
2081 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2082 if it is true. If CODE is ERROR_MARK, set these values instead. */
2085 combinable_refs_p (dref r1, dref r2,
2086 enum tree_code *code, bool *swap, tree *rslt_type)
2088 enum tree_code acode;
2091 tree name1, name2, stmt, rhs;
2093 name1 = name_for_ref (r1);
2094 name2 = name_for_ref (r2);
2095 gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2097 stmt = find_common_use_stmt (&name1, &name2);
2102 rhs = GIMPLE_STMT_OPERAND (stmt, 1);
2103 acode = TREE_CODE (rhs);
2104 aswap = (!commutative_tree_code (acode)
2105 && TREE_OPERAND (rhs, 0) != name1);
2106 atype = TREE_TYPE (rhs);
2108 if (*code == ERROR_MARK)
2116 return (*code == acode
2118 && *rslt_type == atype);
2121 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2122 an assignment of the remaining operand. */
2125 remove_name_from_operation (tree stmt, tree op)
2129 gcc_assert (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT);
2131 rhs = &GIMPLE_STMT_OPERAND (stmt, 1);
2132 if (TREE_OPERAND (*rhs, 0) == op)
2133 *rhs = TREE_OPERAND (*rhs, 1);
2134 else if (TREE_OPERAND (*rhs, 1) == op)
2135 *rhs = TREE_OPERAND (*rhs, 0);
2141 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2142 are combined in a single statement, and returns this statement. */
2145 reassociate_to_the_same_stmt (tree name1, tree name2)
2147 tree stmt1, stmt2, root1, root2, r1, r2, s1, s2;
2148 tree new_stmt, tmp_stmt, new_name, tmp_name, var;
2149 unsigned dist1, dist2;
2150 enum tree_code code;
2151 tree type = TREE_TYPE (name1);
2152 block_stmt_iterator bsi;
2154 stmt1 = find_use_stmt (&name1);
2155 stmt2 = find_use_stmt (&name2);
2156 root1 = find_associative_operation_root (stmt1, &dist1);
2157 root2 = find_associative_operation_root (stmt2, &dist2);
2158 code = TREE_CODE (GIMPLE_STMT_OPERAND (stmt1, 1));
2160 gcc_assert (root1 && root2 && root1 == root2
2161 && code == TREE_CODE (GIMPLE_STMT_OPERAND (stmt2, 1)));
2163 /* Find the root of the nearest expression in that both NAME1 and NAME2
2170 while (dist1 > dist2)
2172 s1 = find_use_stmt (&r1);
2173 r1 = GIMPLE_STMT_OPERAND (s1, 0);
2176 while (dist2 > dist1)
2178 s2 = find_use_stmt (&r2);
2179 r2 = GIMPLE_STMT_OPERAND (s2, 0);
2185 s1 = find_use_stmt (&r1);
2186 r1 = GIMPLE_STMT_OPERAND (s1, 0);
2187 s2 = find_use_stmt (&r2);
2188 r2 = GIMPLE_STMT_OPERAND (s2, 0);
2191 /* Remove NAME1 and NAME2 from the statements in that they are used
2193 remove_name_from_operation (stmt1, name1);
2194 remove_name_from_operation (stmt2, name2);
2196 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2197 combine it with the rhs of S1. */
2198 var = create_tmp_var (type, "predreastmp");
2199 add_referenced_var (var);
2200 new_name = make_ssa_name (var, NULL_TREE);
2201 new_stmt = build_gimple_modify_stmt (new_name,
2202 fold_build2 (code, type, name1, name2));
2203 SSA_NAME_DEF_STMT (new_name) = new_stmt;
2205 var = create_tmp_var (type, "predreastmp");
2206 add_referenced_var (var);
2207 tmp_name = make_ssa_name (var, NULL_TREE);
2208 tmp_stmt = build_gimple_modify_stmt (tmp_name,
2209 GIMPLE_STMT_OPERAND (s1, 1));
2210 SSA_NAME_DEF_STMT (tmp_name) = tmp_stmt;
2212 GIMPLE_STMT_OPERAND (s1, 1) = fold_build2 (code, type, new_name, tmp_name);
2215 bsi = bsi_for_stmt (s1);
2216 bsi_insert_before (&bsi, new_stmt, BSI_SAME_STMT);
2217 bsi_insert_before (&bsi, tmp_stmt, BSI_SAME_STMT);
2222 /* Returns the statement that combines references R1 and R2. In case R1
2223 and R2 are not used in the same statement, but they are used with an
2224 associative and commutative operation in the same expression, reassociate
2225 the expression so that they are used in the same statement. */
2228 stmt_combining_refs (dref r1, dref r2)
2231 tree name1 = name_for_ref (r1);
2232 tree name2 = name_for_ref (r2);
2234 stmt1 = find_use_stmt (&name1);
2235 stmt2 = find_use_stmt (&name2);
2239 return reassociate_to_the_same_stmt (name1, name2);
2242 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2243 description of the new chain is returned, otherwise we return NULL. */
2246 combine_chains (chain_p ch1, chain_p ch2)
2249 enum tree_code op = ERROR_MARK;
2254 tree rslt_type = NULL_TREE;
2258 if (ch1->length != ch2->length)
2261 if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
2264 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2265 && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2267 if (r1->distance != r2->distance)
2270 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2281 new_chain = XCNEW (struct chain);
2282 new_chain->type = CT_COMBINATION;
2283 new_chain->operator = op;
2284 new_chain->ch1 = ch1;
2285 new_chain->ch2 = ch2;
2286 new_chain->rslt_type = rslt_type;
2287 new_chain->length = ch1->length;
2289 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2290 && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2292 nw = XCNEW (struct dref);
2293 nw->stmt = stmt_combining_refs (r1, r2);
2294 nw->distance = r1->distance;
2296 VEC_safe_push (dref, heap, new_chain->refs, nw);
2299 new_chain->has_max_use_after = false;
2300 root_stmt = get_chain_root (new_chain)->stmt;
2301 for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
2303 if (nw->distance == new_chain->length
2304 && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2306 new_chain->has_max_use_after = true;
2311 ch1->combined = true;
2312 ch2->combined = true;
2316 /* Try to combine the CHAINS. */
2319 try_combine_chains (VEC (chain_p, heap) **chains)
2322 chain_p ch1, ch2, cch;
2323 VEC (chain_p, heap) *worklist = NULL;
2325 for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++)
2326 if (chain_can_be_combined_p (ch1))
2327 VEC_safe_push (chain_p, heap, worklist, ch1);
2329 while (!VEC_empty (chain_p, worklist))
2331 ch1 = VEC_pop (chain_p, worklist);
2332 if (!chain_can_be_combined_p (ch1))
2335 for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++)
2337 if (!chain_can_be_combined_p (ch2))
2340 cch = combine_chains (ch1, ch2);
2343 VEC_safe_push (chain_p, heap, worklist, cch);
2344 VEC_safe_push (chain_p, heap, *chains, cch);
2351 /* Sets alias information based on data reference DR for REF,
2355 set_alias_info (tree ref, struct data_reference *dr)
2358 tree tag = DR_SYMBOL_TAG (dr);
2360 gcc_assert (tag != NULL_TREE);
2362 ref = get_base_address (ref);
2363 if (!ref || !INDIRECT_REF_P (ref))
2366 var = SSA_NAME_VAR (TREE_OPERAND (ref, 0));
2367 if (var_ann (var)->symbol_mem_tag)
2371 new_type_alias (var, tag, ref);
2373 var_ann (var)->symbol_mem_tag = tag;
2375 var_ann (var)->subvars = DR_SUBVARS (dr);
2378 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2379 impossible because one of these initializers may trap, true otherwise. */
2382 prepare_initializers_chain (struct loop *loop, chain_p chain)
2384 unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2385 struct data_reference *dr = get_chain_root (chain)->ref;
2388 edge entry = loop_preheader_edge (loop);
2390 /* Find the initializers for the variables, and check that they cannot
2392 chain->inits = VEC_alloc (tree, heap, n);
2393 for (i = 0; i < n; i++)
2394 VEC_quick_push (tree, chain->inits, NULL_TREE);
2396 /* If we have replaced some looparound phi nodes, use their initializers
2397 instead of creating our own. */
2398 for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++)
2400 if (TREE_CODE (laref->stmt) != PHI_NODE)
2403 gcc_assert (laref->distance > 0);
2404 VEC_replace (tree, chain->inits, n - laref->distance,
2405 PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
2408 for (i = 0; i < n; i++)
2410 if (VEC_index (tree, chain->inits, i) != NULL_TREE)
2413 init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
2417 if (!chain->all_always_accessed && tree_could_trap_p (init))
2420 init = force_gimple_operand (init, &stmts, false, NULL_TREE);
2423 mark_virtual_ops_for_renaming_list (stmts);
2424 bsi_insert_on_edge_immediate (entry, stmts);
2426 set_alias_info (init, dr);
2428 VEC_replace (tree, chain->inits, i, init);
2434 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2435 be used because the initializers might trap. */
2438 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
2443 for (i = 0; i < VEC_length (chain_p, chains); )
2445 chain = VEC_index (chain_p, chains, i);
2446 if (prepare_initializers_chain (loop, chain))
2450 release_chain (chain);
2451 VEC_unordered_remove (chain_p, chains, i);
2456 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2460 tree_predictive_commoning_loop (struct loop *loop)
2462 VEC (data_reference_p, heap) *datarefs;
2463 VEC (ddr_p, heap) *dependences;
2464 struct component *components;
2465 VEC (chain_p, heap) *chains = NULL;
2466 unsigned unroll_factor;
2467 struct tree_niter_desc desc;
2468 bool unroll = false;
2472 if (dump_file && (dump_flags & TDF_DETAILS))
2473 fprintf (dump_file, "Processing loop %d\n", loop->num);
2475 /* Find the data references and split them into components according to their
2476 dependence relations. */
2477 datarefs = VEC_alloc (data_reference_p, heap, 10);
2478 dependences = VEC_alloc (ddr_p, heap, 10);
2479 compute_data_dependences_for_loop (loop, true, &datarefs, &dependences);
2480 if (dump_file && (dump_flags & TDF_DETAILS))
2481 dump_data_dependence_relations (dump_file, dependences);
2483 components = split_data_refs_to_components (loop, datarefs, dependences);
2484 free_dependence_relations (dependences);
2487 free_data_refs (datarefs);
2491 if (dump_file && (dump_flags & TDF_DETAILS))
2493 fprintf (dump_file, "Initial state:\n\n");
2494 dump_components (dump_file, components);
2497 /* Find the suitable components and split them into chains. */
2498 components = filter_suitable_components (loop, components);
2500 tmp_vars = BITMAP_ALLOC (NULL);
2501 looparound_phis = BITMAP_ALLOC (NULL);
2502 determine_roots (loop, components, &chains);
2503 release_components (components);
2507 if (dump_file && (dump_flags & TDF_DETAILS))
2509 "Predictive commoning failed: no suitable chains\n");
2512 prepare_initializers (loop, chains);
2514 /* Try to combine the chains that are always worked with together. */
2515 try_combine_chains (&chains);
2517 if (dump_file && (dump_flags & TDF_DETAILS))
2519 fprintf (dump_file, "Before commoning:\n\n");
2520 dump_chains (dump_file, chains);
2523 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2524 that its number of iterations is divisible by the factor. */
2525 unroll_factor = determine_unroll_factor (chains);
2527 unroll = should_unroll_loop_p (loop, unroll_factor, &desc);
2528 exit = single_dom_exit (loop);
2530 /* Execute the predictive commoning transformations, and possibly unroll the
2534 struct epcc_data dta;
2536 if (dump_file && (dump_flags & TDF_DETAILS))
2537 fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2539 dta.chains = chains;
2540 dta.tmp_vars = tmp_vars;
2542 update_ssa (TODO_update_ssa_only_virtuals);
2544 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2545 execute_pred_commoning_cbck is called may cause phi nodes to be
2546 reallocated, which is a problem since CHAINS may point to these
2547 statements. To fix this, we store the ssa names defined by the
2548 phi nodes here instead of the phi nodes themselves, and restore
2549 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2550 replace_phis_by_defined_names (chains);
2552 tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2553 execute_pred_commoning_cbck, &dta);
2554 eliminate_temp_copies (loop, tmp_vars);
2558 if (dump_file && (dump_flags & TDF_DETAILS))
2560 "Executing predictive commoning without unrolling.\n");
2561 execute_pred_commoning (loop, chains, tmp_vars);
2565 release_chains (chains);
2566 free_data_refs (datarefs);
2567 BITMAP_FREE (tmp_vars);
2568 BITMAP_FREE (looparound_phis);
2570 free_affine_expand_cache (&name_expansions);
2575 /* Runs predictive commoning. */
2578 tree_predictive_commoning (void)
2580 bool unrolled = false;
2584 initialize_original_copy_tables ();
2585 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
2587 unrolled |= tree_predictive_commoning_loop (loop);
2593 cleanup_tree_cfg_loop ();
2595 free_original_copy_tables ();