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
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
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];
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 "tree-pretty-print.h"
202 #include "gimple-pretty-print.h"
203 #include "tree-pass.h"
204 #include "tree-affine.h"
205 #include "tree-inline.h"
207 /* The maximum number of iterations between the considered memory
210 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
212 /* Data references (or phi nodes that carry data reference values across
215 typedef struct dref_d
217 /* The reference itself. */
218 struct data_reference *ref;
220 /* The statement in that the reference appears. */
223 /* In case that STMT is a phi node, this field is set to the SSA name
224 defined by it in replace_phis_by_defined_names (in order to avoid
225 pointing to phi node that got reallocated in the meantime). */
226 tree name_defined_by_phi;
228 /* Distance of the reference from the root of the chain (in number of
229 iterations of the loop). */
232 /* Number of iterations offset from the first reference in the component. */
235 /* Number of the reference in a component, in dominance ordering. */
238 /* True if the memory reference is always accessed when the loop is
240 unsigned always_accessed : 1;
244 DEF_VEC_ALLOC_P (dref, heap);
246 /* Type of the chain of the references. */
250 /* The addresses of the references in the chain are constant. */
253 /* There are only loads in the chain. */
256 /* Root of the chain is store, the rest are loads. */
259 /* A combination of two chains. */
263 /* Chains of data references. */
267 /* Type of the chain. */
268 enum chain_type type;
270 /* For combination chains, the operator and the two chains that are
271 combined, and the type of the result. */
274 struct chain *ch1, *ch2;
276 /* The references in the chain. */
277 VEC(dref,heap) *refs;
279 /* The maximum distance of the reference in the chain from the root. */
282 /* The variables used to copy the value throughout iterations. */
283 VEC(tree,heap) *vars;
285 /* Initializers for the variables. */
286 VEC(tree,heap) *inits;
288 /* True if there is a use of a variable with the maximal distance
289 that comes after the root in the loop. */
290 unsigned has_max_use_after : 1;
292 /* True if all the memory references in the chain are always accessed. */
293 unsigned all_always_accessed : 1;
295 /* True if this chain was combined together with some other chain. */
296 unsigned combined : 1;
300 DEF_VEC_ALLOC_P (chain_p, heap);
302 /* Describes the knowledge about the step of the memory references in
307 /* The step is zero. */
310 /* The step is nonzero. */
313 /* The step may or may not be nonzero. */
317 /* Components of the data dependence graph. */
321 /* The references in the component. */
322 VEC(dref,heap) *refs;
324 /* What we know about the step of the references in the component. */
325 enum ref_step_type comp_step;
327 /* Next component in the list. */
328 struct component *next;
331 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
333 static bitmap looparound_phis;
335 /* Cache used by tree_to_aff_combination_expand. */
337 static struct pointer_map_t *name_expansions;
339 /* Dumps data reference REF to FILE. */
341 extern void dump_dref (FILE *, dref);
343 dump_dref (FILE *file, dref ref)
348 print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
349 fprintf (file, " (id %u%s)\n", ref->pos,
350 DR_IS_READ (ref->ref) ? "" : ", write");
352 fprintf (file, " offset ");
353 dump_double_int (file, ref->offset, false);
354 fprintf (file, "\n");
356 fprintf (file, " distance %u\n", ref->distance);
360 if (gimple_code (ref->stmt) == GIMPLE_PHI)
361 fprintf (file, " looparound ref\n");
363 fprintf (file, " combination ref\n");
364 fprintf (file, " in statement ");
365 print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
366 fprintf (file, "\n");
367 fprintf (file, " distance %u\n", ref->distance);
372 /* Dumps CHAIN to FILE. */
374 extern void dump_chain (FILE *, chain_p);
376 dump_chain (FILE *file, chain_p chain)
379 const char *chain_type;
386 chain_type = "Load motion";
390 chain_type = "Loads-only";
394 chain_type = "Store-loads";
398 chain_type = "Combination";
405 fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
406 chain->combined ? " (combined)" : "");
407 if (chain->type != CT_INVARIANT)
408 fprintf (file, " max distance %u%s\n", chain->length,
409 chain->has_max_use_after ? "" : ", may reuse first");
411 if (chain->type == CT_COMBINATION)
413 fprintf (file, " equal to %p %s %p in type ",
414 (void *) chain->ch1, op_symbol_code (chain->op),
415 (void *) chain->ch2);
416 print_generic_expr (file, chain->rslt_type, TDF_SLIM);
417 fprintf (file, "\n");
422 fprintf (file, " vars");
423 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
426 print_generic_expr (file, var, TDF_SLIM);
428 fprintf (file, "\n");
433 fprintf (file, " inits");
434 for (i = 0; VEC_iterate (tree, chain->inits, i, var); i++)
437 print_generic_expr (file, var, TDF_SLIM);
439 fprintf (file, "\n");
442 fprintf (file, " references:\n");
443 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
446 fprintf (file, "\n");
449 /* Dumps CHAINS to FILE. */
451 extern void dump_chains (FILE *, VEC (chain_p, heap) *);
453 dump_chains (FILE *file, VEC (chain_p, heap) *chains)
458 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
459 dump_chain (file, chain);
462 /* Dumps COMP to FILE. */
464 extern void dump_component (FILE *, struct component *);
466 dump_component (FILE *file, struct component *comp)
471 fprintf (file, "Component%s:\n",
472 comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
473 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
475 fprintf (file, "\n");
478 /* Dumps COMPS to FILE. */
480 extern void dump_components (FILE *, struct component *);
482 dump_components (FILE *file, struct component *comps)
484 struct component *comp;
486 for (comp = comps; comp; comp = comp->next)
487 dump_component (file, comp);
490 /* Frees a chain CHAIN. */
493 release_chain (chain_p chain)
501 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)
504 VEC_free (dref, heap, chain->refs);
505 VEC_free (tree, heap, chain->vars);
506 VEC_free (tree, heap, chain->inits);
514 release_chains (VEC (chain_p, heap) *chains)
519 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
520 release_chain (chain);
521 VEC_free (chain_p, heap, chains);
524 /* Frees a component COMP. */
527 release_component (struct component *comp)
529 VEC_free (dref, heap, comp->refs);
533 /* Frees list of components COMPS. */
536 release_components (struct component *comps)
538 struct component *act, *next;
540 for (act = comps; act; act = next)
543 release_component (act);
547 /* Finds a root of tree given by FATHERS containing A, and performs path
551 component_of (unsigned fathers[], unsigned a)
555 for (root = a; root != fathers[root]; root = fathers[root])
558 for (; a != root; a = n)
567 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
568 components, A and B are components to merge. */
571 merge_comps (unsigned fathers[], unsigned sizes[], unsigned a, unsigned b)
573 unsigned ca = component_of (fathers, a);
574 unsigned cb = component_of (fathers, b);
579 if (sizes[ca] < sizes[cb])
581 sizes[cb] += sizes[ca];
586 sizes[ca] += sizes[cb];
591 /* Returns true if A is a reference that is suitable for predictive commoning
592 in the innermost loop that contains it. REF_STEP is set according to the
593 step of the reference A. */
596 suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
598 tree ref = DR_REF (a), step = DR_STEP (a);
601 || !is_gimple_reg_type (TREE_TYPE (ref))
602 || tree_could_throw_p (ref))
605 if (integer_zerop (step))
606 *ref_step = RS_INVARIANT;
607 else if (integer_nonzerop (step))
608 *ref_step = RS_NONZERO;
615 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
618 aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset)
622 tree_to_aff_combination_expand (DR_OFFSET (dr), sizetype, offset,
624 aff_combination_const (&delta, sizetype, tree_to_double_int (DR_INIT (dr)));
625 aff_combination_add (offset, &delta);
628 /* Determines number of iterations of the innermost enclosing loop before B
629 refers to exactly the same location as A and stores it to OFF. If A and
630 B do not have the same step, they never meet, or anything else fails,
631 returns false, otherwise returns true. Both A and B are assumed to
632 satisfy suitable_reference_p. */
635 determine_offset (struct data_reference *a, struct data_reference *b,
638 aff_tree diff, baseb, step;
641 /* Check that both the references access the location in the same type. */
642 typea = TREE_TYPE (DR_REF (a));
643 typeb = TREE_TYPE (DR_REF (b));
644 if (!useless_type_conversion_p (typeb, typea))
647 /* Check whether the base address and the step of both references is the
649 if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
650 || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
653 if (integer_zerop (DR_STEP (a)))
655 /* If the references have loop invariant address, check that they access
656 exactly the same location. */
657 *off = double_int_zero;
658 return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
659 && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
662 /* Compare the offsets of the addresses, and check whether the difference
663 is a multiple of step. */
664 aff_combination_dr_offset (a, &diff);
665 aff_combination_dr_offset (b, &baseb);
666 aff_combination_scale (&baseb, double_int_minus_one);
667 aff_combination_add (&diff, &baseb);
669 tree_to_aff_combination_expand (DR_STEP (a), sizetype,
670 &step, &name_expansions);
671 return aff_combination_constant_multiple_p (&diff, &step, off);
674 /* Returns the last basic block in LOOP for that we are sure that
675 it is executed whenever the loop is entered. */
678 last_always_executed_block (struct loop *loop)
681 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
683 basic_block last = loop->latch;
685 for (i = 0; VEC_iterate (edge, exits, i, ex); i++)
686 last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
687 VEC_free (edge, heap, exits);
692 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
694 static struct component *
695 split_data_refs_to_components (struct loop *loop,
696 VEC (data_reference_p, heap) *datarefs,
697 VEC (ddr_p, heap) *depends)
699 unsigned i, n = VEC_length (data_reference_p, datarefs);
700 unsigned ca, ia, ib, bad;
701 unsigned *comp_father = XNEWVEC (unsigned, n + 1);
702 unsigned *comp_size = XNEWVEC (unsigned, n + 1);
703 struct component **comps;
704 struct data_reference *dr, *dra, *drb;
705 struct data_dependence_relation *ddr;
706 struct component *comp_list = NULL, *comp;
708 basic_block last_always_executed = last_always_executed_block (loop);
710 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
714 /* A fake reference for call or asm_expr that may clobber memory;
718 dr->aux = (void *) (size_t) i;
723 /* A component reserved for the "bad" data references. */
727 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
729 enum ref_step_type dummy;
731 if (!suitable_reference_p (dr, &dummy))
733 ia = (unsigned) (size_t) dr->aux;
734 merge_comps (comp_father, comp_size, n, ia);
738 for (i = 0; VEC_iterate (ddr_p, depends, i, ddr); i++)
740 double_int dummy_off;
742 if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
747 ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
748 ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
752 bad = component_of (comp_father, n);
754 /* If both A and B are reads, we may ignore unsuitable dependences. */
755 if (DR_IS_READ (dra) && DR_IS_READ (drb)
756 && (ia == bad || ib == bad
757 || !determine_offset (dra, drb, &dummy_off)))
760 merge_comps (comp_father, comp_size, ia, ib);
763 comps = XCNEWVEC (struct component *, n);
764 bad = component_of (comp_father, n);
765 for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
767 ia = (unsigned) (size_t) dr->aux;
768 ca = component_of (comp_father, ia);
775 comp = XCNEW (struct component);
776 comp->refs = VEC_alloc (dref, heap, comp_size[ca]);
780 dataref = XCNEW (struct dref_d);
782 dataref->stmt = DR_STMT (dr);
783 dataref->offset = double_int_zero;
784 dataref->distance = 0;
786 dataref->always_accessed
787 = dominated_by_p (CDI_DOMINATORS, last_always_executed,
788 gimple_bb (dataref->stmt));
789 dataref->pos = VEC_length (dref, comp->refs);
790 VEC_quick_push (dref, comp->refs, dataref);
793 for (i = 0; i < n; i++)
798 comp->next = comp_list;
810 /* Returns true if the component COMP satisfies the conditions
811 described in 2) at the beginning of this file. LOOP is the current
815 suitable_component_p (struct loop *loop, struct component *comp)
819 basic_block ba, bp = loop->header;
820 bool ok, has_write = false;
822 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
824 ba = gimple_bb (a->stmt);
826 if (!just_once_each_iteration_p (loop, ba))
829 gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
832 if (!DR_IS_READ (a->ref))
836 first = VEC_index (dref, comp->refs, 0);
837 ok = suitable_reference_p (first->ref, &comp->comp_step);
839 first->offset = double_int_zero;
841 for (i = 1; VEC_iterate (dref, comp->refs, i, a); i++)
843 if (!determine_offset (first->ref, a->ref, &a->offset))
846 #ifdef ENABLE_CHECKING
848 enum ref_step_type a_step;
849 ok = suitable_reference_p (a->ref, &a_step);
850 gcc_assert (ok && a_step == comp->comp_step);
855 /* If there is a write inside the component, we must know whether the
856 step is nonzero or not -- we would not otherwise be able to recognize
857 whether the value accessed by reads comes from the OFFSET-th iteration
858 or the previous one. */
859 if (has_write && comp->comp_step == RS_ANY)
865 /* Check the conditions on references inside each of components COMPS,
866 and remove the unsuitable components from the list. The new list
867 of components is returned. The conditions are described in 2) at
868 the beginning of this file. LOOP is the current loop. */
870 static struct component *
871 filter_suitable_components (struct loop *loop, struct component *comps)
873 struct component **comp, *act;
875 for (comp = &comps; *comp; )
878 if (suitable_component_p (loop, act))
886 for (i = 0; VEC_iterate (dref, act->refs, i, ref); i++)
888 release_component (act);
895 /* Compares two drefs A and B by their offset and position. Callback for
899 order_drefs (const void *a, const void *b)
901 const dref *const da = (const dref *) a;
902 const dref *const db = (const dref *) b;
903 int offcmp = double_int_scmp ((*da)->offset, (*db)->offset);
908 return (*da)->pos - (*db)->pos;
911 /* Returns root of the CHAIN. */
914 get_chain_root (chain_p chain)
916 return VEC_index (dref, chain->refs, 0);
919 /* Adds REF to the chain CHAIN. */
922 add_ref_to_chain (chain_p chain, dref ref)
924 dref root = get_chain_root (chain);
927 gcc_assert (double_int_scmp (root->offset, ref->offset) <= 0);
928 dist = double_int_add (ref->offset, double_int_neg (root->offset));
929 if (double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE), dist) <= 0)
934 gcc_assert (double_int_fits_in_uhwi_p (dist));
936 VEC_safe_push (dref, heap, chain->refs, ref);
938 ref->distance = double_int_to_uhwi (dist);
940 if (ref->distance >= chain->length)
942 chain->length = ref->distance;
943 chain->has_max_use_after = false;
946 if (ref->distance == chain->length
947 && ref->pos > root->pos)
948 chain->has_max_use_after = true;
950 chain->all_always_accessed &= ref->always_accessed;
953 /* Returns the chain for invariant component COMP. */
956 make_invariant_chain (struct component *comp)
958 chain_p chain = XCNEW (struct chain);
962 chain->type = CT_INVARIANT;
964 chain->all_always_accessed = true;
966 for (i = 0; VEC_iterate (dref, comp->refs, i, ref); i++)
968 VEC_safe_push (dref, heap, chain->refs, ref);
969 chain->all_always_accessed &= ref->always_accessed;
975 /* Make a new chain rooted at REF. */
978 make_rooted_chain (dref ref)
980 chain_p chain = XCNEW (struct chain);
982 chain->type = DR_IS_READ (ref->ref) ? CT_LOAD : CT_STORE_LOAD;
984 VEC_safe_push (dref, heap, chain->refs, ref);
985 chain->all_always_accessed = ref->always_accessed;
992 /* Returns true if CHAIN is not trivial. */
995 nontrivial_chain_p (chain_p chain)
997 return chain != NULL && VEC_length (dref, chain->refs) > 1;
1000 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1004 name_for_ref (dref ref)
1008 if (is_gimple_assign (ref->stmt))
1010 if (!ref->ref || DR_IS_READ (ref->ref))
1011 name = gimple_assign_lhs (ref->stmt);
1013 name = gimple_assign_rhs1 (ref->stmt);
1016 name = PHI_RESULT (ref->stmt);
1018 return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
1021 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1022 iterations of the innermost enclosing loop). */
1025 valid_initializer_p (struct data_reference *ref,
1026 unsigned distance, struct data_reference *root)
1028 aff_tree diff, base, step;
1031 /* Both REF and ROOT must be accessing the same object. */
1032 if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
1035 /* The initializer is defined outside of loop, hence its address must be
1036 invariant inside the loop. */
1037 gcc_assert (integer_zerop (DR_STEP (ref)));
1039 /* If the address of the reference is invariant, initializer must access
1040 exactly the same location. */
1041 if (integer_zerop (DR_STEP (root)))
1042 return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
1043 && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
1045 /* Verify that this index of REF is equal to the root's index at
1046 -DISTANCE-th iteration. */
1047 aff_combination_dr_offset (root, &diff);
1048 aff_combination_dr_offset (ref, &base);
1049 aff_combination_scale (&base, double_int_minus_one);
1050 aff_combination_add (&diff, &base);
1052 tree_to_aff_combination_expand (DR_STEP (root), sizetype, &step,
1054 if (!aff_combination_constant_multiple_p (&diff, &step, &off))
1057 if (!double_int_equal_p (off, uhwi_to_double_int (distance)))
1063 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1064 initial value is correct (equal to initial value of REF shifted by one
1065 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1066 is the root of the current chain. */
1069 find_looparound_phi (struct loop *loop, dref ref, dref root)
1071 tree name, init, init_ref;
1072 gimple phi = NULL, init_stmt;
1073 edge latch = loop_latch_edge (loop);
1074 struct data_reference init_dr;
1075 gimple_stmt_iterator psi;
1077 if (is_gimple_assign (ref->stmt))
1079 if (DR_IS_READ (ref->ref))
1080 name = gimple_assign_lhs (ref->stmt);
1082 name = gimple_assign_rhs1 (ref->stmt);
1085 name = PHI_RESULT (ref->stmt);
1089 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1091 phi = gsi_stmt (psi);
1092 if (PHI_ARG_DEF_FROM_EDGE (phi, latch) == name)
1096 if (gsi_end_p (psi))
1099 init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1100 if (TREE_CODE (init) != SSA_NAME)
1102 init_stmt = SSA_NAME_DEF_STMT (init);
1103 if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
1105 gcc_assert (gimple_assign_lhs (init_stmt) == init);
1107 init_ref = gimple_assign_rhs1 (init_stmt);
1108 if (!REFERENCE_CLASS_P (init_ref)
1109 && !DECL_P (init_ref))
1112 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1113 loop enclosing PHI). */
1114 memset (&init_dr, 0, sizeof (struct data_reference));
1115 DR_REF (&init_dr) = init_ref;
1116 DR_STMT (&init_dr) = phi;
1117 if (!dr_analyze_innermost (&init_dr))
1120 if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
1126 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1129 insert_looparound_copy (chain_p chain, dref ref, gimple phi)
1131 dref nw = XCNEW (struct dref_d), aref;
1135 nw->distance = ref->distance + 1;
1136 nw->always_accessed = 1;
1138 for (i = 0; VEC_iterate (dref, chain->refs, i, aref); i++)
1139 if (aref->distance >= nw->distance)
1141 VEC_safe_insert (dref, heap, chain->refs, i, nw);
1143 if (nw->distance > chain->length)
1145 chain->length = nw->distance;
1146 chain->has_max_use_after = false;
1150 /* For references in CHAIN that are copied around the LOOP (created previously
1151 by PRE, or by user), add the results of such copies to the chain. This
1152 enables us to remove the copies by unrolling, and may need less registers
1153 (also, it may allow us to combine chains together). */
1156 add_looparound_copies (struct loop *loop, chain_p chain)
1159 dref ref, root = get_chain_root (chain);
1162 for (i = 0; VEC_iterate (dref, chain->refs, i, ref); i++)
1164 phi = find_looparound_phi (loop, ref, root);
1168 bitmap_set_bit (looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
1169 insert_looparound_copy (chain, ref, phi);
1173 /* Find roots of the values and determine distances in the component COMP.
1174 The references are redistributed into CHAINS. LOOP is the current
1178 determine_roots_comp (struct loop *loop,
1179 struct component *comp,
1180 VEC (chain_p, heap) **chains)
1184 chain_p chain = NULL;
1185 double_int last_ofs = double_int_zero;
1187 /* Invariants are handled specially. */
1188 if (comp->comp_step == RS_INVARIANT)
1190 chain = make_invariant_chain (comp);
1191 VEC_safe_push (chain_p, heap, *chains, chain);
1195 qsort (VEC_address (dref, comp->refs), VEC_length (dref, comp->refs),
1196 sizeof (dref), order_drefs);
1198 for (i = 0; VEC_iterate (dref, comp->refs, i, a); i++)
1200 if (!chain || !DR_IS_READ (a->ref)
1201 || double_int_ucmp (uhwi_to_double_int (MAX_DISTANCE),
1202 double_int_add (a->offset,
1203 double_int_neg (last_ofs))) <= 0)
1205 if (nontrivial_chain_p (chain))
1207 add_looparound_copies (loop, chain);
1208 VEC_safe_push (chain_p, heap, *chains, chain);
1211 release_chain (chain);
1212 chain = make_rooted_chain (a);
1213 last_ofs = a->offset;
1217 add_ref_to_chain (chain, a);
1220 if (nontrivial_chain_p (chain))
1222 add_looparound_copies (loop, chain);
1223 VEC_safe_push (chain_p, heap, *chains, chain);
1226 release_chain (chain);
1229 /* Find roots of the values and determine distances in components COMPS, and
1230 separates the references to CHAINS. LOOP is the current loop. */
1233 determine_roots (struct loop *loop,
1234 struct component *comps, VEC (chain_p, heap) **chains)
1236 struct component *comp;
1238 for (comp = comps; comp; comp = comp->next)
1239 determine_roots_comp (loop, comp, chains);
1242 /* Replace the reference in statement STMT with temporary variable
1243 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1244 the reference in the statement. IN_LHS is true if the reference
1245 is in the lhs of STMT, false if it is in rhs. */
1248 replace_ref_with (gimple stmt, tree new_tree, bool set, bool in_lhs)
1252 gimple_stmt_iterator bsi, psi;
1254 if (gimple_code (stmt) == GIMPLE_PHI)
1256 gcc_assert (!in_lhs && !set);
1258 val = PHI_RESULT (stmt);
1259 bsi = gsi_after_labels (gimple_bb (stmt));
1260 psi = gsi_for_stmt (stmt);
1261 remove_phi_node (&psi, false);
1263 /* Turn the phi node into GIMPLE_ASSIGN. */
1264 new_stmt = gimple_build_assign (val, new_tree);
1265 gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
1269 /* Since the reference is of gimple_reg type, it should only
1270 appear as lhs or rhs of modify statement. */
1271 gcc_assert (is_gimple_assign (stmt));
1273 bsi = gsi_for_stmt (stmt);
1275 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1278 gcc_assert (!in_lhs);
1279 gimple_assign_set_rhs_from_tree (&bsi, new_tree);
1280 stmt = gsi_stmt (bsi);
1287 /* We have statement
1291 If OLD is a memory reference, then VAL is gimple_val, and we transform
1297 Otherwise, we are replacing a combination chain,
1298 VAL is the expression that performs the combination, and OLD is an
1299 SSA name. In this case, we transform the assignment to
1306 val = gimple_assign_lhs (stmt);
1307 if (TREE_CODE (val) != SSA_NAME)
1309 gcc_assert (gimple_assign_copy_p (stmt));
1310 val = gimple_assign_rhs1 (stmt);
1322 val = gimple_assign_lhs (stmt);
1325 new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
1326 gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
1329 /* Returns the reference to the address of REF in the ITER-th iteration of
1330 LOOP, or NULL if we fail to determine it (ITER may be negative). We
1331 try to preserve the original shape of the reference (not rewrite it
1332 as an indirect ref to the address), to make tree_could_trap_p in
1333 prepare_initializers_chain return false more often. */
1336 ref_at_iteration (struct loop *loop, tree ref, int iter)
1338 tree idx, *idx_p, type, val, op0 = NULL_TREE, ret;
1342 if (handled_component_p (ref))
1344 op0 = ref_at_iteration (loop, TREE_OPERAND (ref, 0), iter);
1348 else if (!INDIRECT_REF_P (ref)
1349 && TREE_CODE (ref) != MEM_REF)
1350 return unshare_expr (ref);
1352 if (INDIRECT_REF_P (ref)
1353 || TREE_CODE (ref) == MEM_REF)
1355 /* Take care for MEM_REF and MISALIGNED_INDIRECT_REF at
1357 ret = unshare_expr (ref);
1358 idx = TREE_OPERAND (ref, 0);
1359 idx_p = &TREE_OPERAND (ret, 0);
1361 else if (TREE_CODE (ref) == COMPONENT_REF)
1363 /* Check that the offset is loop invariant. */
1364 if (TREE_OPERAND (ref, 2)
1365 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1368 return build3 (COMPONENT_REF, TREE_TYPE (ref), op0,
1369 unshare_expr (TREE_OPERAND (ref, 1)),
1370 unshare_expr (TREE_OPERAND (ref, 2)));
1372 else if (TREE_CODE (ref) == ARRAY_REF)
1374 /* Check that the lower bound and the step are loop invariant. */
1375 if (TREE_OPERAND (ref, 2)
1376 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 2)))
1378 if (TREE_OPERAND (ref, 3)
1379 && !expr_invariant_in_loop_p (loop, TREE_OPERAND (ref, 3)))
1382 ret = build4 (ARRAY_REF, TREE_TYPE (ref), op0, NULL_TREE,
1383 unshare_expr (TREE_OPERAND (ref, 2)),
1384 unshare_expr (TREE_OPERAND (ref, 3)));
1385 idx = TREE_OPERAND (ref, 1);
1386 idx_p = &TREE_OPERAND (ret, 1);
1391 ok = simple_iv (loop, loop, idx, &iv, true);
1394 iv.base = expand_simple_operations (iv.base);
1395 if (integer_zerop (iv.step))
1396 *idx_p = unshare_expr (iv.base);
1399 type = TREE_TYPE (iv.base);
1400 if (POINTER_TYPE_P (type))
1402 val = fold_build2 (MULT_EXPR, sizetype, iv.step,
1404 val = fold_build2 (POINTER_PLUS_EXPR, type, iv.base, val);
1408 val = fold_build2 (MULT_EXPR, type, iv.step,
1409 build_int_cst_type (type, iter));
1410 val = fold_build2 (PLUS_EXPR, type, iv.base, val);
1412 *idx_p = unshare_expr (val);
1418 /* Get the initialization expression for the INDEX-th temporary variable
1422 get_init_expr (chain_p chain, unsigned index)
1424 if (chain->type == CT_COMBINATION)
1426 tree e1 = get_init_expr (chain->ch1, index);
1427 tree e2 = get_init_expr (chain->ch2, index);
1429 return fold_build2 (chain->op, chain->rslt_type, e1, e2);
1432 return VEC_index (tree, chain->inits, index);
1435 /* Marks all virtual operands of statement STMT for renaming. */
1438 mark_virtual_ops_for_renaming (gimple stmt)
1442 if (gimple_code (stmt) == GIMPLE_PHI)
1444 var = PHI_RESULT (stmt);
1445 if (is_gimple_reg (var))
1448 if (TREE_CODE (var) == SSA_NAME)
1449 var = SSA_NAME_VAR (var);
1450 mark_sym_for_renaming (var);
1455 if (gimple_vuse (stmt))
1456 mark_sym_for_renaming (gimple_vop (cfun));
1459 /* Returns a new temporary variable used for the I-th variable carrying
1460 value of REF. The variable's uid is marked in TMP_VARS. */
1463 predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
1465 tree type = TREE_TYPE (ref);
1466 /* We never access the components of the temporary variable in predictive
1468 tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
1470 add_referenced_var (var);
1471 bitmap_set_bit (tmp_vars, DECL_UID (var));
1475 /* Creates the variables for CHAIN, as well as phi nodes for them and
1476 initialization on entry to LOOP. Uids of the newly created
1477 temporary variables are marked in TMP_VARS. */
1480 initialize_root_vars (struct loop *loop, chain_p chain, bitmap tmp_vars)
1483 unsigned n = chain->length;
1484 dref root = get_chain_root (chain);
1485 bool reuse_first = !chain->has_max_use_after;
1486 tree ref, init, var, next;
1489 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1491 /* If N == 0, then all the references are within the single iteration. And
1492 since this is an nonempty chain, reuse_first cannot be true. */
1493 gcc_assert (n > 0 || !reuse_first);
1495 chain->vars = VEC_alloc (tree, heap, n + 1);
1497 if (chain->type == CT_COMBINATION)
1498 ref = gimple_assign_lhs (root->stmt);
1500 ref = DR_REF (root->ref);
1502 for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
1504 var = predcom_tmp_var (ref, i, tmp_vars);
1505 VEC_quick_push (tree, chain->vars, var);
1508 VEC_quick_push (tree, chain->vars, VEC_index (tree, chain->vars, 0));
1510 for (i = 0; VEC_iterate (tree, chain->vars, i, var); i++)
1511 VEC_replace (tree, chain->vars, i, make_ssa_name (var, NULL));
1513 for (i = 0; i < n; i++)
1515 var = VEC_index (tree, chain->vars, i);
1516 next = VEC_index (tree, chain->vars, i + 1);
1517 init = get_init_expr (chain, i);
1519 init = force_gimple_operand (init, &stmts, true, NULL_TREE);
1521 gsi_insert_seq_on_edge_immediate (entry, stmts);
1523 phi = create_phi_node (var, loop->header);
1524 SSA_NAME_DEF_STMT (var) = phi;
1525 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1526 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1530 /* Create the variables and initialization statement for root of chain
1531 CHAIN. Uids of the newly created temporary variables are marked
1535 initialize_root (struct loop *loop, chain_p chain, bitmap tmp_vars)
1537 dref root = get_chain_root (chain);
1538 bool in_lhs = (chain->type == CT_STORE_LOAD
1539 || chain->type == CT_COMBINATION);
1541 initialize_root_vars (loop, chain, tmp_vars);
1542 replace_ref_with (root->stmt,
1543 VEC_index (tree, chain->vars, chain->length),
1547 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1548 initialization on entry to LOOP if necessary. The ssa name for the variable
1549 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1550 around the loop is created. Uid of the newly created temporary variable
1551 is marked in TMP_VARS. INITS is the list containing the (single)
1555 initialize_root_vars_lm (struct loop *loop, dref root, bool written,
1556 VEC(tree, heap) **vars, VEC(tree, heap) *inits,
1560 tree ref = DR_REF (root->ref), init, var, next;
1563 edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
1565 /* Find the initializer for the variable, and check that it cannot
1567 init = VEC_index (tree, inits, 0);
1569 *vars = VEC_alloc (tree, heap, written ? 2 : 1);
1570 var = predcom_tmp_var (ref, 0, tmp_vars);
1571 VEC_quick_push (tree, *vars, var);
1573 VEC_quick_push (tree, *vars, VEC_index (tree, *vars, 0));
1575 for (i = 0; VEC_iterate (tree, *vars, i, var); i++)
1576 VEC_replace (tree, *vars, i, make_ssa_name (var, NULL));
1578 var = VEC_index (tree, *vars, 0);
1580 init = force_gimple_operand (init, &stmts, written, NULL_TREE);
1582 gsi_insert_seq_on_edge_immediate (entry, stmts);
1586 next = VEC_index (tree, *vars, 1);
1587 phi = create_phi_node (var, loop->header);
1588 SSA_NAME_DEF_STMT (var) = phi;
1589 add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
1590 add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
1594 gimple init_stmt = gimple_build_assign (var, init);
1595 mark_virtual_ops_for_renaming (init_stmt);
1596 gsi_insert_on_edge_immediate (entry, init_stmt);
1601 /* Execute load motion for references in chain CHAIN. Uids of the newly
1602 created temporary variables are marked in TMP_VARS. */
1605 execute_load_motion (struct loop *loop, chain_p chain, bitmap tmp_vars)
1607 VEC (tree, heap) *vars;
1609 unsigned n_writes = 0, ridx, i;
1612 gcc_assert (chain->type == CT_INVARIANT);
1613 gcc_assert (!chain->combined);
1614 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1615 if (!DR_IS_READ (a->ref))
1618 /* If there are no reads in the loop, there is nothing to do. */
1619 if (n_writes == VEC_length (dref, chain->refs))
1622 initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
1623 &vars, chain->inits, tmp_vars);
1626 for (i = 0; VEC_iterate (dref, chain->refs, i, a); i++)
1628 bool is_read = DR_IS_READ (a->ref);
1629 mark_virtual_ops_for_renaming (a->stmt);
1631 if (!DR_IS_READ (a->ref))
1636 var = VEC_index (tree, vars, 0);
1637 var = make_ssa_name (SSA_NAME_VAR (var), NULL);
1638 VEC_replace (tree, vars, 0, var);
1644 replace_ref_with (a->stmt, VEC_index (tree, vars, ridx),
1645 !is_read, !is_read);
1648 VEC_free (tree, heap, vars);
1651 /* Returns the single statement in that NAME is used, excepting
1652 the looparound phi nodes contained in one of the chains. If there is no
1653 such statement, or more statements, NULL is returned. */
1656 single_nonlooparound_use (tree name)
1659 imm_use_iterator it;
1660 gimple stmt, ret = NULL;
1662 FOR_EACH_IMM_USE_FAST (use, it, name)
1664 stmt = USE_STMT (use);
1666 if (gimple_code (stmt) == GIMPLE_PHI)
1668 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1669 could not be processed anyway, so just fail for them. */
1670 if (bitmap_bit_p (looparound_phis,
1671 SSA_NAME_VERSION (PHI_RESULT (stmt))))
1676 else if (ret != NULL)
1685 /* Remove statement STMT, as well as the chain of assignments in that it is
1689 remove_stmt (gimple stmt)
1693 gimple_stmt_iterator psi;
1695 if (gimple_code (stmt) == GIMPLE_PHI)
1697 name = PHI_RESULT (stmt);
1698 next = single_nonlooparound_use (name);
1699 psi = gsi_for_stmt (stmt);
1700 remove_phi_node (&psi, true);
1703 || !gimple_assign_ssa_name_copy_p (next)
1704 || gimple_assign_rhs1 (next) != name)
1712 gimple_stmt_iterator bsi;
1714 bsi = gsi_for_stmt (stmt);
1716 name = gimple_assign_lhs (stmt);
1717 gcc_assert (TREE_CODE (name) == SSA_NAME);
1719 next = single_nonlooparound_use (name);
1721 mark_virtual_ops_for_renaming (stmt);
1722 gsi_remove (&bsi, true);
1723 release_defs (stmt);
1726 || !gimple_assign_ssa_name_copy_p (next)
1727 || gimple_assign_rhs1 (next) != name)
1734 /* Perform the predictive commoning optimization for a chain CHAIN.
1735 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1738 execute_pred_commoning_chain (struct loop *loop, chain_p chain,
1745 if (chain->combined)
1747 /* For combined chains, just remove the statements that are used to
1748 compute the values of the expression (except for the root one). */
1749 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1750 remove_stmt (a->stmt);
1754 /* For non-combined chains, set up the variables that hold its value,
1755 and replace the uses of the original references by these
1757 root = get_chain_root (chain);
1758 mark_virtual_ops_for_renaming (root->stmt);
1760 initialize_root (loop, chain, tmp_vars);
1761 for (i = 1; VEC_iterate (dref, chain->refs, i, a); i++)
1763 mark_virtual_ops_for_renaming (a->stmt);
1764 var = VEC_index (tree, chain->vars, chain->length - a->distance);
1765 replace_ref_with (a->stmt, var, false, false);
1770 /* Determines the unroll factor necessary to remove as many temporary variable
1771 copies as possible. CHAINS is the list of chains that will be
1775 determine_unroll_factor (VEC (chain_p, heap) *chains)
1778 unsigned factor = 1, af, nfactor, i;
1779 unsigned max = PARAM_VALUE (PARAM_MAX_UNROLL_TIMES);
1781 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1783 if (chain->type == CT_INVARIANT || chain->combined)
1786 /* The best unroll factor for this chain is equal to the number of
1787 temporary variables that we create for it. */
1789 if (chain->has_max_use_after)
1792 nfactor = factor * af / gcd (factor, af);
1800 /* Perform the predictive commoning optimization for CHAINS.
1801 Uids of the newly created temporary variables are marked in TMP_VARS. */
1804 execute_pred_commoning (struct loop *loop, VEC (chain_p, heap) *chains,
1810 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1812 if (chain->type == CT_INVARIANT)
1813 execute_load_motion (loop, chain, tmp_vars);
1815 execute_pred_commoning_chain (loop, chain, tmp_vars);
1818 update_ssa (TODO_update_ssa_only_virtuals);
1821 /* For each reference in CHAINS, if its defining statement is
1822 phi node, record the ssa name that is defined by it. */
1825 replace_phis_by_defined_names (VEC (chain_p, heap) *chains)
1831 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1832 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1834 if (gimple_code (a->stmt) == GIMPLE_PHI)
1836 a->name_defined_by_phi = PHI_RESULT (a->stmt);
1842 /* For each reference in CHAINS, if name_defined_by_phi is not
1843 NULL, use it to set the stmt field. */
1846 replace_names_by_phis (VEC (chain_p, heap) *chains)
1852 for (i = 0; VEC_iterate (chain_p, chains, i, chain); i++)
1853 for (j = 0; VEC_iterate (dref, chain->refs, j, a); j++)
1854 if (a->stmt == NULL)
1856 a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
1857 gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
1858 a->name_defined_by_phi = NULL_TREE;
1862 /* Wrapper over execute_pred_commoning, to pass it as a callback
1863 to tree_transform_and_unroll_loop. */
1867 VEC (chain_p, heap) *chains;
1872 execute_pred_commoning_cbck (struct loop *loop, void *data)
1874 struct epcc_data *const dta = (struct epcc_data *) data;
1876 /* Restore phi nodes that were replaced by ssa names before
1877 tree_transform_and_unroll_loop (see detailed description in
1878 tree_predictive_commoning_loop). */
1879 replace_names_by_phis (dta->chains);
1880 execute_pred_commoning (loop, dta->chains, dta->tmp_vars);
1883 /* Base NAME and all the names in the chain of phi nodes that use it
1884 on variable VAR. The phi nodes are recognized by being in the copies of
1885 the header of the LOOP. */
1888 base_names_in_chain_on (struct loop *loop, tree name, tree var)
1891 imm_use_iterator iter;
1893 SSA_NAME_VAR (name) = var;
1898 FOR_EACH_IMM_USE_STMT (stmt, iter, name)
1900 if (gimple_code (stmt) == GIMPLE_PHI
1901 && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
1904 BREAK_FROM_IMM_USE_STMT (iter);
1910 name = PHI_RESULT (phi);
1911 SSA_NAME_VAR (name) = var;
1915 /* Given an unrolled LOOP after predictive commoning, remove the
1916 register copies arising from phi nodes by changing the base
1917 variables of SSA names. TMP_VARS is the set of the temporary variables
1918 for those we want to perform this. */
1921 eliminate_temp_copies (struct loop *loop, bitmap tmp_vars)
1925 tree name, use, var;
1926 gimple_stmt_iterator psi;
1928 e = loop_latch_edge (loop);
1929 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
1931 phi = gsi_stmt (psi);
1932 name = PHI_RESULT (phi);
1933 var = SSA_NAME_VAR (name);
1934 if (!bitmap_bit_p (tmp_vars, DECL_UID (var)))
1936 use = PHI_ARG_DEF_FROM_EDGE (phi, e);
1937 gcc_assert (TREE_CODE (use) == SSA_NAME);
1939 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1940 stmt = SSA_NAME_DEF_STMT (use);
1941 while (gimple_code (stmt) == GIMPLE_PHI
1942 /* In case we could not unroll the loop enough to eliminate
1943 all copies, we may reach the loop header before the defining
1944 statement (in that case, some register copies will be present
1945 in loop latch in the final code, corresponding to the newly
1946 created looparound phi nodes). */
1947 && gimple_bb (stmt) != loop->header)
1949 gcc_assert (single_pred_p (gimple_bb (stmt)));
1950 use = PHI_ARG_DEF (stmt, 0);
1951 stmt = SSA_NAME_DEF_STMT (use);
1954 base_names_in_chain_on (loop, use, var);
1958 /* Returns true if CHAIN is suitable to be combined. */
1961 chain_can_be_combined_p (chain_p chain)
1963 return (!chain->combined
1964 && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
1967 /* Returns the modify statement that uses NAME. Skips over assignment
1968 statements, NAME is replaced with the actual name used in the returned
1972 find_use_stmt (tree *name)
1977 /* Skip over assignments. */
1980 stmt = single_nonlooparound_use (*name);
1984 if (gimple_code (stmt) != GIMPLE_ASSIGN)
1987 lhs = gimple_assign_lhs (stmt);
1988 if (TREE_CODE (lhs) != SSA_NAME)
1991 if (gimple_assign_copy_p (stmt))
1993 rhs = gimple_assign_rhs1 (stmt);
1999 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
2000 == GIMPLE_BINARY_RHS)
2007 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
2010 may_reassociate_p (tree type, enum tree_code code)
2012 if (FLOAT_TYPE_P (type)
2013 && !flag_unsafe_math_optimizations)
2016 return (commutative_tree_code (code)
2017 && associative_tree_code (code));
2020 /* If the operation used in STMT is associative and commutative, go through the
2021 tree of the same operations and returns its root. Distance to the root
2022 is stored in DISTANCE. */
2025 find_associative_operation_root (gimple stmt, unsigned *distance)
2029 enum tree_code code = gimple_assign_rhs_code (stmt);
2030 tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2033 if (!may_reassociate_p (type, code))
2038 lhs = gimple_assign_lhs (stmt);
2039 gcc_assert (TREE_CODE (lhs) == SSA_NAME);
2041 next = find_use_stmt (&lhs);
2043 || gimple_assign_rhs_code (next) != code)
2055 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
2056 is no such statement, returns NULL_TREE. In case the operation used on
2057 NAME1 and NAME2 is associative and commutative, returns the root of the
2058 tree formed by this operation instead of the statement that uses NAME1 or
2062 find_common_use_stmt (tree *name1, tree *name2)
2064 gimple stmt1, stmt2;
2066 stmt1 = find_use_stmt (name1);
2070 stmt2 = find_use_stmt (name2);
2077 stmt1 = find_associative_operation_root (stmt1, NULL);
2080 stmt2 = find_associative_operation_root (stmt2, NULL);
2084 return (stmt1 == stmt2 ? stmt1 : NULL);
2087 /* Checks whether R1 and R2 are combined together using CODE, with the result
2088 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2089 if it is true. If CODE is ERROR_MARK, set these values instead. */
2092 combinable_refs_p (dref r1, dref r2,
2093 enum tree_code *code, bool *swap, tree *rslt_type)
2095 enum tree_code acode;
2101 name1 = name_for_ref (r1);
2102 name2 = name_for_ref (r2);
2103 gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
2105 stmt = find_common_use_stmt (&name1, &name2);
2110 acode = gimple_assign_rhs_code (stmt);
2111 aswap = (!commutative_tree_code (acode)
2112 && gimple_assign_rhs1 (stmt) != name1);
2113 atype = TREE_TYPE (gimple_assign_lhs (stmt));
2115 if (*code == ERROR_MARK)
2123 return (*code == acode
2125 && *rslt_type == atype);
2128 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2129 an assignment of the remaining operand. */
2132 remove_name_from_operation (gimple stmt, tree op)
2135 gimple_stmt_iterator si;
2137 gcc_assert (is_gimple_assign (stmt));
2139 if (gimple_assign_rhs1 (stmt) == op)
2140 other_op = gimple_assign_rhs2 (stmt);
2142 other_op = gimple_assign_rhs1 (stmt);
2144 si = gsi_for_stmt (stmt);
2145 gimple_assign_set_rhs_from_tree (&si, other_op);
2147 /* We should not have reallocated STMT. */
2148 gcc_assert (gsi_stmt (si) == stmt);
2153 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2154 are combined in a single statement, and returns this statement. */
2157 reassociate_to_the_same_stmt (tree name1, tree name2)
2159 gimple stmt1, stmt2, root1, root2, s1, s2;
2160 gimple new_stmt, tmp_stmt;
2161 tree new_name, tmp_name, var, r1, r2;
2162 unsigned dist1, dist2;
2163 enum tree_code code;
2164 tree type = TREE_TYPE (name1);
2165 gimple_stmt_iterator bsi;
2167 stmt1 = find_use_stmt (&name1);
2168 stmt2 = find_use_stmt (&name2);
2169 root1 = find_associative_operation_root (stmt1, &dist1);
2170 root2 = find_associative_operation_root (stmt2, &dist2);
2171 code = gimple_assign_rhs_code (stmt1);
2173 gcc_assert (root1 && root2 && root1 == root2
2174 && code == gimple_assign_rhs_code (stmt2));
2176 /* Find the root of the nearest expression in that both NAME1 and NAME2
2183 while (dist1 > dist2)
2185 s1 = find_use_stmt (&r1);
2186 r1 = gimple_assign_lhs (s1);
2189 while (dist2 > dist1)
2191 s2 = find_use_stmt (&r2);
2192 r2 = gimple_assign_lhs (s2);
2198 s1 = find_use_stmt (&r1);
2199 r1 = gimple_assign_lhs (s1);
2200 s2 = find_use_stmt (&r2);
2201 r2 = gimple_assign_lhs (s2);
2204 /* Remove NAME1 and NAME2 from the statements in that they are used
2206 remove_name_from_operation (stmt1, name1);
2207 remove_name_from_operation (stmt2, name2);
2209 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2210 combine it with the rhs of S1. */
2211 var = create_tmp_reg (type, "predreastmp");
2212 add_referenced_var (var);
2213 new_name = make_ssa_name (var, NULL);
2214 new_stmt = gimple_build_assign_with_ops (code, new_name, name1, name2);
2216 var = create_tmp_reg (type, "predreastmp");
2217 add_referenced_var (var);
2218 tmp_name = make_ssa_name (var, NULL);
2220 /* Rhs of S1 may now be either a binary expression with operation
2221 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2222 so that name1 or name2 was removed from it). */
2223 tmp_stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (s1),
2225 gimple_assign_rhs1 (s1),
2226 gimple_assign_rhs2 (s1));
2228 bsi = gsi_for_stmt (s1);
2229 gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
2230 s1 = gsi_stmt (bsi);
2233 gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
2234 gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
2239 /* Returns the statement that combines references R1 and R2. In case R1
2240 and R2 are not used in the same statement, but they are used with an
2241 associative and commutative operation in the same expression, reassociate
2242 the expression so that they are used in the same statement. */
2245 stmt_combining_refs (dref r1, dref r2)
2247 gimple stmt1, stmt2;
2248 tree name1 = name_for_ref (r1);
2249 tree name2 = name_for_ref (r2);
2251 stmt1 = find_use_stmt (&name1);
2252 stmt2 = find_use_stmt (&name2);
2256 return reassociate_to_the_same_stmt (name1, name2);
2259 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2260 description of the new chain is returned, otherwise we return NULL. */
2263 combine_chains (chain_p ch1, chain_p ch2)
2266 enum tree_code op = ERROR_MARK;
2271 tree rslt_type = NULL_TREE;
2275 if (ch1->length != ch2->length)
2278 if (VEC_length (dref, ch1->refs) != VEC_length (dref, ch2->refs))
2281 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2282 && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2284 if (r1->distance != r2->distance)
2287 if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
2298 new_chain = XCNEW (struct chain);
2299 new_chain->type = CT_COMBINATION;
2301 new_chain->ch1 = ch1;
2302 new_chain->ch2 = ch2;
2303 new_chain->rslt_type = rslt_type;
2304 new_chain->length = ch1->length;
2306 for (i = 0; (VEC_iterate (dref, ch1->refs, i, r1)
2307 && VEC_iterate (dref, ch2->refs, i, r2)); i++)
2309 nw = XCNEW (struct dref_d);
2310 nw->stmt = stmt_combining_refs (r1, r2);
2311 nw->distance = r1->distance;
2313 VEC_safe_push (dref, heap, new_chain->refs, nw);
2316 new_chain->has_max_use_after = false;
2317 root_stmt = get_chain_root (new_chain)->stmt;
2318 for (i = 1; VEC_iterate (dref, new_chain->refs, i, nw); i++)
2320 if (nw->distance == new_chain->length
2321 && !stmt_dominates_stmt_p (nw->stmt, root_stmt))
2323 new_chain->has_max_use_after = true;
2328 ch1->combined = true;
2329 ch2->combined = true;
2333 /* Try to combine the CHAINS. */
2336 try_combine_chains (VEC (chain_p, heap) **chains)
2339 chain_p ch1, ch2, cch;
2340 VEC (chain_p, heap) *worklist = NULL;
2342 for (i = 0; VEC_iterate (chain_p, *chains, i, ch1); i++)
2343 if (chain_can_be_combined_p (ch1))
2344 VEC_safe_push (chain_p, heap, worklist, ch1);
2346 while (!VEC_empty (chain_p, worklist))
2348 ch1 = VEC_pop (chain_p, worklist);
2349 if (!chain_can_be_combined_p (ch1))
2352 for (j = 0; VEC_iterate (chain_p, *chains, j, ch2); j++)
2354 if (!chain_can_be_combined_p (ch2))
2357 cch = combine_chains (ch1, ch2);
2360 VEC_safe_push (chain_p, heap, worklist, cch);
2361 VEC_safe_push (chain_p, heap, *chains, cch);
2368 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2369 impossible because one of these initializers may trap, true otherwise. */
2372 prepare_initializers_chain (struct loop *loop, chain_p chain)
2374 unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
2375 struct data_reference *dr = get_chain_root (chain)->ref;
2379 edge entry = loop_preheader_edge (loop);
2381 /* Find the initializers for the variables, and check that they cannot
2383 chain->inits = VEC_alloc (tree, heap, n);
2384 for (i = 0; i < n; i++)
2385 VEC_quick_push (tree, chain->inits, NULL_TREE);
2387 /* If we have replaced some looparound phi nodes, use their initializers
2388 instead of creating our own. */
2389 for (i = 0; VEC_iterate (dref, chain->refs, i, laref); i++)
2391 if (gimple_code (laref->stmt) != GIMPLE_PHI)
2394 gcc_assert (laref->distance > 0);
2395 VEC_replace (tree, chain->inits, n - laref->distance,
2396 PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry));
2399 for (i = 0; i < n; i++)
2401 if (VEC_index (tree, chain->inits, i) != NULL_TREE)
2404 init = ref_at_iteration (loop, DR_REF (dr), (int) i - n);
2408 if (!chain->all_always_accessed && tree_could_trap_p (init))
2411 init = force_gimple_operand (init, &stmts, false, NULL_TREE);
2413 gsi_insert_seq_on_edge_immediate (entry, stmts);
2415 VEC_replace (tree, chain->inits, i, init);
2421 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2422 be used because the initializers might trap. */
2425 prepare_initializers (struct loop *loop, VEC (chain_p, heap) *chains)
2430 for (i = 0; i < VEC_length (chain_p, chains); )
2432 chain = VEC_index (chain_p, chains, i);
2433 if (prepare_initializers_chain (loop, chain))
2437 release_chain (chain);
2438 VEC_unordered_remove (chain_p, chains, i);
2443 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2447 tree_predictive_commoning_loop (struct loop *loop)
2449 VEC (data_reference_p, heap) *datarefs;
2450 VEC (ddr_p, heap) *dependences;
2451 struct component *components;
2452 VEC (chain_p, heap) *chains = NULL;
2453 unsigned unroll_factor;
2454 struct tree_niter_desc desc;
2455 bool unroll = false;
2459 if (dump_file && (dump_flags & TDF_DETAILS))
2460 fprintf (dump_file, "Processing loop %d\n", loop->num);
2462 /* Find the data references and split them into components according to their
2463 dependence relations. */
2464 datarefs = VEC_alloc (data_reference_p, heap, 10);
2465 dependences = VEC_alloc (ddr_p, heap, 10);
2466 compute_data_dependences_for_loop (loop, true, &datarefs, &dependences);
2467 if (dump_file && (dump_flags & TDF_DETAILS))
2468 dump_data_dependence_relations (dump_file, dependences);
2470 components = split_data_refs_to_components (loop, datarefs, dependences);
2471 free_dependence_relations (dependences);
2474 free_data_refs (datarefs);
2478 if (dump_file && (dump_flags & TDF_DETAILS))
2480 fprintf (dump_file, "Initial state:\n\n");
2481 dump_components (dump_file, components);
2484 /* Find the suitable components and split them into chains. */
2485 components = filter_suitable_components (loop, components);
2487 tmp_vars = BITMAP_ALLOC (NULL);
2488 looparound_phis = BITMAP_ALLOC (NULL);
2489 determine_roots (loop, components, &chains);
2490 release_components (components);
2494 if (dump_file && (dump_flags & TDF_DETAILS))
2496 "Predictive commoning failed: no suitable chains\n");
2499 prepare_initializers (loop, chains);
2501 /* Try to combine the chains that are always worked with together. */
2502 try_combine_chains (&chains);
2504 if (dump_file && (dump_flags & TDF_DETAILS))
2506 fprintf (dump_file, "Before commoning:\n\n");
2507 dump_chains (dump_file, chains);
2510 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2511 that its number of iterations is divisible by the factor. */
2512 unroll_factor = determine_unroll_factor (chains);
2514 unroll = (unroll_factor > 1
2515 && can_unroll_loop_p (loop, unroll_factor, &desc));
2516 exit = single_dom_exit (loop);
2518 /* Execute the predictive commoning transformations, and possibly unroll the
2522 struct epcc_data dta;
2524 if (dump_file && (dump_flags & TDF_DETAILS))
2525 fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
2527 dta.chains = chains;
2528 dta.tmp_vars = tmp_vars;
2530 update_ssa (TODO_update_ssa_only_virtuals);
2532 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2533 execute_pred_commoning_cbck is called may cause phi nodes to be
2534 reallocated, which is a problem since CHAINS may point to these
2535 statements. To fix this, we store the ssa names defined by the
2536 phi nodes here instead of the phi nodes themselves, and restore
2537 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2538 replace_phis_by_defined_names (chains);
2540 tree_transform_and_unroll_loop (loop, unroll_factor, exit, &desc,
2541 execute_pred_commoning_cbck, &dta);
2542 eliminate_temp_copies (loop, tmp_vars);
2546 if (dump_file && (dump_flags & TDF_DETAILS))
2548 "Executing predictive commoning without unrolling.\n");
2549 execute_pred_commoning (loop, chains, tmp_vars);
2553 release_chains (chains);
2554 free_data_refs (datarefs);
2555 BITMAP_FREE (tmp_vars);
2556 BITMAP_FREE (looparound_phis);
2558 free_affine_expand_cache (&name_expansions);
2563 /* Runs predictive commoning. */
2566 tree_predictive_commoning (void)
2568 bool unrolled = false;
2573 initialize_original_copy_tables ();
2574 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
2575 if (optimize_loop_for_speed_p (loop))
2577 unrolled |= tree_predictive_commoning_loop (loop);
2583 ret = TODO_cleanup_cfg;
2585 free_original_copy_tables ();