1 /* Predictive commoning.
2 Copyright (C) 2005-2013 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 3, 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 COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file implements the predictive commoning optimization. Predictive
21 commoning can be viewed as CSE around a loop, and with some improvements,
22 as generalized strength reduction-- i.e., reusing values computed in
23 earlier iterations of a loop in the later ones. So far, the pass only
24 handles the most useful case, that is, reusing values of memory references.
25 If you think this is all just a special case of PRE, you are sort of right;
26 however, concentrating on loops is simpler, and makes it possible to
27 incorporate data dependence analysis to detect the opportunities, perform
28 loop unrolling to avoid copies together with renaming immediately,
29 and if needed, we could also take register pressure into account.
31 Let us demonstrate what is done on an example:
33 for (i = 0; i < 100; i++)
35 a[i+2] = a[i] + a[i+1];
41 1) We find data references in the loop, and split them to mutually
42 independent groups (i.e., we find components of a data dependence
43 graph). We ignore read-read dependences whose distance is not constant.
44 (TODO -- we could also ignore antidependences). In this example, we
45 find the following groups:
47 a[i]{read}, a[i+1]{read}, a[i+2]{write}
48 b[10]{read}, b[10]{write}
49 c[99 - i]{read}, c[i]{write}
50 d[i + 1]{read}, d[i]{write}
52 2) Inside each of the group, we verify several conditions:
53 a) all the references must differ in indices only, and the indices
54 must all have the same step
55 b) the references must dominate loop latch (and thus, they must be
56 ordered by dominance relation).
57 c) the distance of the indices must be a small multiple of the step
58 We are then able to compute the difference of the references (# of
59 iterations before they point to the same place as the first of them).
60 Also, in case there are writes in the loop, we split the groups into
61 chains whose head is the write whose values are used by the reads in
62 the same chain. The chains are then processed independently,
63 making the further transformations simpler. Also, the shorter chains
64 need the same number of registers, but may require lower unrolling
65 factor in order to get rid of the copies on the loop latch.
67 In our example, we get the following chains (the chain for c is invalid).
69 a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
70 b[10]{read,+0}, b[10]{write,+0}
71 d[i + 1]{read,+0}, d[i]{write,+1}
73 3) For each read, we determine the read or write whose value it reuses,
74 together with the distance of this reuse. I.e. we take the last
75 reference before it with distance 0, or the last of the references
76 with the smallest positive distance to the read. Then, we remove
77 the references that are not used in any of these chains, discard the
78 empty groups, and propagate all the links so that they point to the
79 single root reference of the chain (adjusting their distance
80 appropriately). Some extra care needs to be taken for references with
81 step 0. In our example (the numbers indicate the distance of the
84 a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
85 b[10] --> (*) 1, b[10] (*)
87 4) The chains are combined together if possible. If the corresponding
88 elements of two chains are always combined together with the same
89 operator, we remember just the result of this combination, instead
90 of remembering the values separately. We may need to perform
91 reassociation to enable combining, for example
93 e[i] + f[i+1] + e[i+1] + f[i]
95 can be reassociated as
97 (e[i] + f[i]) + (e[i+1] + f[i+1])
99 and we can combine the chains for e and f into one chain.
101 5) For each root reference (end of the chain) R, let N be maximum distance
102 of a reference reusing its value. Variables R0 up to RN are created,
103 together with phi nodes that transfer values from R1 .. RN to
105 Initial values are loaded to R0..R(N-1) (in case not all references
106 must necessarily be accessed and they may trap, we may fail here;
107 TODO sometimes, the loads could be guarded by a check for the number
108 of iterations). Values loaded/stored in roots are also copied to
109 RN. Other reads are replaced with the appropriate variable Ri.
110 Everything is put to SSA form.
112 As a small improvement, if R0 is dead after the root (i.e., all uses of
113 the value with the maximum distance dominate the root), we can avoid
114 creating RN and use R0 instead of it.
116 In our example, we get (only the parts concerning a and b are shown):
117 for (i = 0; i < 100; i++)
129 6) Factor F for unrolling is determined as the smallest common multiple of
130 (N + 1) for each root reference (N for references for that we avoided
131 creating RN). If F and the loop is small enough, loop is unrolled F
132 times. The stores to RN (R0) in the copies of the loop body are
133 periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
134 be coalesced and the copies can be eliminated.
136 TODO -- copy propagation and other optimizations may change the live
137 ranges of the temporary registers and prevent them from being coalesced;
138 this may increase the register pressure.
140 In our case, F = 2 and the (main loop of the) result is
142 for (i = 0; i < ...; i += 2)
159 TODO -- stores killing other stores can be taken into account, e.g.,
160 for (i = 0; i < n; i++)
170 for (i = 0; i < n; i++)
180 The interesting part is that this would generalize store motion; still, since
181 sm is performed elsewhere, it does not seem that important.
183 Predictive commoning can be generalized for arbitrary computations (not
184 just memory loads), and also nontrivial transfer functions (e.g., replacing
185 i * i with ii_last + 2 * i + 1), to generalize strength reduction. */
189 #include "coretypes.h"
194 #include "basic-block.h"
195 #include "tree-ssa-alias.h"
196 #include "internal-fn.h"
198 #include "gimple-expr.h"
201 #include "gimplify.h"
202 #include "gimple-iterator.h"
203 #include "gimplify-me.h"
204 #include "gimple-ssa.h"
205 #include "tree-phinodes.h"
206 #include "ssa-iterators.h"
207 #include "stringpool.h"
208 #include "tree-ssanames.h"
209 #include "tree-ssa-loop-ivopts.h"
210 #include "tree-ssa-loop-manip.h"
211 #include "tree-ssa-loop-niter.h"
212 #include "tree-ssa-loop.h"
213 #include "tree-into-ssa.h"
215 #include "tree-dfa.h"
216 #include "tree-ssa.h"
217 #include "tree-data-ref.h"
218 #include "tree-scalar-evolution.h"
219 #include "tree-chrec.h"
221 #include "gimple-pretty-print.h"
222 #include "tree-pass.h"
223 #include "tree-affine.h"
224 #include "tree-inline.h"
226 /* The maximum number of iterations between the considered memory
229 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
231 /* Data references (or phi nodes that carry data reference values across
234 typedef struct dref_d
236 /* The reference itself. */
237 struct data_reference
*ref
;
239 /* The statement in that the reference appears. */
242 /* In case that STMT is a phi node, this field is set to the SSA name
243 defined by it in replace_phis_by_defined_names (in order to avoid
244 pointing to phi node that got reallocated in the meantime). */
245 tree name_defined_by_phi
;
247 /* Distance of the reference from the root of the chain (in number of
248 iterations of the loop). */
251 /* Number of iterations offset from the first reference in the component. */
254 /* Number of the reference in a component, in dominance ordering. */
257 /* True if the memory reference is always accessed when the loop is
259 unsigned always_accessed
: 1;
263 /* Type of the chain of the references. */
267 /* The addresses of the references in the chain are constant. */
270 /* There are only loads in the chain. */
273 /* Root of the chain is store, the rest are loads. */
276 /* A combination of two chains. */
280 /* Chains of data references. */
284 /* Type of the chain. */
285 enum chain_type type
;
287 /* For combination chains, the operator and the two chains that are
288 combined, and the type of the result. */
291 struct chain
*ch1
, *ch2
;
293 /* The references in the chain. */
296 /* The maximum distance of the reference in the chain from the root. */
299 /* The variables used to copy the value throughout iterations. */
302 /* Initializers for the variables. */
305 /* True if there is a use of a variable with the maximal distance
306 that comes after the root in the loop. */
307 unsigned has_max_use_after
: 1;
309 /* True if all the memory references in the chain are always accessed. */
310 unsigned all_always_accessed
: 1;
312 /* True if this chain was combined together with some other chain. */
313 unsigned combined
: 1;
317 /* Describes the knowledge about the step of the memory references in
322 /* The step is zero. */
325 /* The step is nonzero. */
328 /* The step may or may not be nonzero. */
332 /* Components of the data dependence graph. */
336 /* The references in the component. */
339 /* What we know about the step of the references in the component. */
340 enum ref_step_type comp_step
;
342 /* Next component in the list. */
343 struct component
*next
;
346 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
348 static bitmap looparound_phis
;
350 /* Cache used by tree_to_aff_combination_expand. */
352 static struct pointer_map_t
*name_expansions
;
354 /* Dumps data reference REF to FILE. */
356 extern void dump_dref (FILE *, dref
);
358 dump_dref (FILE *file
, dref ref
)
363 print_generic_expr (file
, DR_REF (ref
->ref
), TDF_SLIM
);
364 fprintf (file
, " (id %u%s)\n", ref
->pos
,
365 DR_IS_READ (ref
->ref
) ? "" : ", write");
367 fprintf (file
, " offset ");
368 dump_double_int (file
, ref
->offset
, false);
369 fprintf (file
, "\n");
371 fprintf (file
, " distance %u\n", ref
->distance
);
375 if (gimple_code (ref
->stmt
) == GIMPLE_PHI
)
376 fprintf (file
, " looparound ref\n");
378 fprintf (file
, " combination ref\n");
379 fprintf (file
, " in statement ");
380 print_gimple_stmt (file
, ref
->stmt
, 0, TDF_SLIM
);
381 fprintf (file
, "\n");
382 fprintf (file
, " distance %u\n", ref
->distance
);
387 /* Dumps CHAIN to FILE. */
389 extern void dump_chain (FILE *, chain_p
);
391 dump_chain (FILE *file
, chain_p chain
)
394 const char *chain_type
;
401 chain_type
= "Load motion";
405 chain_type
= "Loads-only";
409 chain_type
= "Store-loads";
413 chain_type
= "Combination";
420 fprintf (file
, "%s chain %p%s\n", chain_type
, (void *) chain
,
421 chain
->combined
? " (combined)" : "");
422 if (chain
->type
!= CT_INVARIANT
)
423 fprintf (file
, " max distance %u%s\n", chain
->length
,
424 chain
->has_max_use_after
? "" : ", may reuse first");
426 if (chain
->type
== CT_COMBINATION
)
428 fprintf (file
, " equal to %p %s %p in type ",
429 (void *) chain
->ch1
, op_symbol_code (chain
->op
),
430 (void *) chain
->ch2
);
431 print_generic_expr (file
, chain
->rslt_type
, TDF_SLIM
);
432 fprintf (file
, "\n");
435 if (chain
->vars
.exists ())
437 fprintf (file
, " vars");
438 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
441 print_generic_expr (file
, var
, TDF_SLIM
);
443 fprintf (file
, "\n");
446 if (chain
->inits
.exists ())
448 fprintf (file
, " inits");
449 FOR_EACH_VEC_ELT (chain
->inits
, i
, var
)
452 print_generic_expr (file
, var
, TDF_SLIM
);
454 fprintf (file
, "\n");
457 fprintf (file
, " references:\n");
458 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
461 fprintf (file
, "\n");
464 /* Dumps CHAINS to FILE. */
466 extern void dump_chains (FILE *, vec
<chain_p
> );
468 dump_chains (FILE *file
, vec
<chain_p
> chains
)
473 FOR_EACH_VEC_ELT (chains
, i
, chain
)
474 dump_chain (file
, chain
);
477 /* Dumps COMP to FILE. */
479 extern void dump_component (FILE *, struct component
*);
481 dump_component (FILE *file
, struct component
*comp
)
486 fprintf (file
, "Component%s:\n",
487 comp
->comp_step
== RS_INVARIANT
? " (invariant)" : "");
488 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
490 fprintf (file
, "\n");
493 /* Dumps COMPS to FILE. */
495 extern void dump_components (FILE *, struct component
*);
497 dump_components (FILE *file
, struct component
*comps
)
499 struct component
*comp
;
501 for (comp
= comps
; comp
; comp
= comp
->next
)
502 dump_component (file
, comp
);
505 /* Frees a chain CHAIN. */
508 release_chain (chain_p chain
)
516 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
519 chain
->refs
.release ();
520 chain
->vars
.release ();
521 chain
->inits
.release ();
529 release_chains (vec
<chain_p
> chains
)
534 FOR_EACH_VEC_ELT (chains
, i
, chain
)
535 release_chain (chain
);
539 /* Frees a component COMP. */
542 release_component (struct component
*comp
)
544 comp
->refs
.release ();
548 /* Frees list of components COMPS. */
551 release_components (struct component
*comps
)
553 struct component
*act
, *next
;
555 for (act
= comps
; act
; act
= next
)
558 release_component (act
);
562 /* Finds a root of tree given by FATHERS containing A, and performs path
566 component_of (unsigned fathers
[], unsigned a
)
570 for (root
= a
; root
!= fathers
[root
]; root
= fathers
[root
])
573 for (; a
!= root
; a
= n
)
582 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
583 components, A and B are components to merge. */
586 merge_comps (unsigned fathers
[], unsigned sizes
[], unsigned a
, unsigned b
)
588 unsigned ca
= component_of (fathers
, a
);
589 unsigned cb
= component_of (fathers
, b
);
594 if (sizes
[ca
] < sizes
[cb
])
596 sizes
[cb
] += sizes
[ca
];
601 sizes
[ca
] += sizes
[cb
];
606 /* Returns true if A is a reference that is suitable for predictive commoning
607 in the innermost loop that contains it. REF_STEP is set according to the
608 step of the reference A. */
611 suitable_reference_p (struct data_reference
*a
, enum ref_step_type
*ref_step
)
613 tree ref
= DR_REF (a
), step
= DR_STEP (a
);
616 || TREE_THIS_VOLATILE (ref
)
617 || !is_gimple_reg_type (TREE_TYPE (ref
))
618 || tree_could_throw_p (ref
))
621 if (integer_zerop (step
))
622 *ref_step
= RS_INVARIANT
;
623 else if (integer_nonzerop (step
))
624 *ref_step
= RS_NONZERO
;
631 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
634 aff_combination_dr_offset (struct data_reference
*dr
, aff_tree
*offset
)
636 tree type
= TREE_TYPE (DR_OFFSET (dr
));
639 tree_to_aff_combination_expand (DR_OFFSET (dr
), type
, offset
,
641 aff_combination_const (&delta
, type
, tree_to_double_int (DR_INIT (dr
)));
642 aff_combination_add (offset
, &delta
);
645 /* Determines number of iterations of the innermost enclosing loop before B
646 refers to exactly the same location as A and stores it to OFF. If A and
647 B do not have the same step, they never meet, or anything else fails,
648 returns false, otherwise returns true. Both A and B are assumed to
649 satisfy suitable_reference_p. */
652 determine_offset (struct data_reference
*a
, struct data_reference
*b
,
655 aff_tree diff
, baseb
, step
;
658 /* Check that both the references access the location in the same type. */
659 typea
= TREE_TYPE (DR_REF (a
));
660 typeb
= TREE_TYPE (DR_REF (b
));
661 if (!useless_type_conversion_p (typeb
, typea
))
664 /* Check whether the base address and the step of both references is the
666 if (!operand_equal_p (DR_STEP (a
), DR_STEP (b
), 0)
667 || !operand_equal_p (DR_BASE_ADDRESS (a
), DR_BASE_ADDRESS (b
), 0))
670 if (integer_zerop (DR_STEP (a
)))
672 /* If the references have loop invariant address, check that they access
673 exactly the same location. */
674 *off
= double_int_zero
;
675 return (operand_equal_p (DR_OFFSET (a
), DR_OFFSET (b
), 0)
676 && operand_equal_p (DR_INIT (a
), DR_INIT (b
), 0));
679 /* Compare the offsets of the addresses, and check whether the difference
680 is a multiple of step. */
681 aff_combination_dr_offset (a
, &diff
);
682 aff_combination_dr_offset (b
, &baseb
);
683 aff_combination_scale (&baseb
, double_int_minus_one
);
684 aff_combination_add (&diff
, &baseb
);
686 tree_to_aff_combination_expand (DR_STEP (a
), TREE_TYPE (DR_STEP (a
)),
687 &step
, &name_expansions
);
688 return aff_combination_constant_multiple_p (&diff
, &step
, off
);
691 /* Returns the last basic block in LOOP for that we are sure that
692 it is executed whenever the loop is entered. */
695 last_always_executed_block (struct loop
*loop
)
698 vec
<edge
> exits
= get_loop_exit_edges (loop
);
700 basic_block last
= loop
->latch
;
702 FOR_EACH_VEC_ELT (exits
, i
, ex
)
703 last
= nearest_common_dominator (CDI_DOMINATORS
, last
, ex
->src
);
709 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
711 static struct component
*
712 split_data_refs_to_components (struct loop
*loop
,
713 vec
<data_reference_p
> datarefs
,
716 unsigned i
, n
= datarefs
.length ();
717 unsigned ca
, ia
, ib
, bad
;
718 unsigned *comp_father
= XNEWVEC (unsigned, n
+ 1);
719 unsigned *comp_size
= XNEWVEC (unsigned, n
+ 1);
720 struct component
**comps
;
721 struct data_reference
*dr
, *dra
, *drb
;
722 struct data_dependence_relation
*ddr
;
723 struct component
*comp_list
= NULL
, *comp
;
725 basic_block last_always_executed
= last_always_executed_block (loop
);
727 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
731 /* A fake reference for call or asm_expr that may clobber memory;
735 dr
->aux
= (void *) (size_t) i
;
740 /* A component reserved for the "bad" data references. */
744 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
746 enum ref_step_type dummy
;
748 if (!suitable_reference_p (dr
, &dummy
))
750 ia
= (unsigned) (size_t) dr
->aux
;
751 merge_comps (comp_father
, comp_size
, n
, ia
);
755 FOR_EACH_VEC_ELT (depends
, i
, ddr
)
757 double_int dummy_off
;
759 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
764 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
765 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
769 bad
= component_of (comp_father
, n
);
771 /* If both A and B are reads, we may ignore unsuitable dependences. */
772 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
773 && (ia
== bad
|| ib
== bad
774 || !determine_offset (dra
, drb
, &dummy_off
)))
777 merge_comps (comp_father
, comp_size
, ia
, ib
);
780 comps
= XCNEWVEC (struct component
*, n
);
781 bad
= component_of (comp_father
, n
);
782 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
784 ia
= (unsigned) (size_t) dr
->aux
;
785 ca
= component_of (comp_father
, ia
);
792 comp
= XCNEW (struct component
);
793 comp
->refs
.create (comp_size
[ca
]);
797 dataref
= XCNEW (struct dref_d
);
799 dataref
->stmt
= DR_STMT (dr
);
800 dataref
->offset
= double_int_zero
;
801 dataref
->distance
= 0;
803 dataref
->always_accessed
804 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
805 gimple_bb (dataref
->stmt
));
806 dataref
->pos
= comp
->refs
.length ();
807 comp
->refs
.quick_push (dataref
);
810 for (i
= 0; i
< n
; i
++)
815 comp
->next
= comp_list
;
827 /* Returns true if the component COMP satisfies the conditions
828 described in 2) at the beginning of this file. LOOP is the current
832 suitable_component_p (struct loop
*loop
, struct component
*comp
)
836 basic_block ba
, bp
= loop
->header
;
837 bool ok
, has_write
= false;
839 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
841 ba
= gimple_bb (a
->stmt
);
843 if (!just_once_each_iteration_p (loop
, ba
))
846 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
849 if (DR_IS_WRITE (a
->ref
))
853 first
= comp
->refs
[0];
854 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
856 first
->offset
= double_int_zero
;
858 for (i
= 1; comp
->refs
.iterate (i
, &a
); i
++)
860 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
863 #ifdef ENABLE_CHECKING
865 enum ref_step_type a_step
;
866 ok
= suitable_reference_p (a
->ref
, &a_step
);
867 gcc_assert (ok
&& a_step
== comp
->comp_step
);
872 /* If there is a write inside the component, we must know whether the
873 step is nonzero or not -- we would not otherwise be able to recognize
874 whether the value accessed by reads comes from the OFFSET-th iteration
875 or the previous one. */
876 if (has_write
&& comp
->comp_step
== RS_ANY
)
882 /* Check the conditions on references inside each of components COMPS,
883 and remove the unsuitable components from the list. The new list
884 of components is returned. The conditions are described in 2) at
885 the beginning of this file. LOOP is the current loop. */
887 static struct component
*
888 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
890 struct component
**comp
, *act
;
892 for (comp
= &comps
; *comp
; )
895 if (suitable_component_p (loop
, act
))
903 FOR_EACH_VEC_ELT (act
->refs
, i
, ref
)
905 release_component (act
);
912 /* Compares two drefs A and B by their offset and position. Callback for
916 order_drefs (const void *a
, const void *b
)
918 const dref
*const da
= (const dref
*) a
;
919 const dref
*const db
= (const dref
*) b
;
920 int offcmp
= (*da
)->offset
.scmp ((*db
)->offset
);
925 return (*da
)->pos
- (*db
)->pos
;
928 /* Returns root of the CHAIN. */
931 get_chain_root (chain_p chain
)
933 return chain
->refs
[0];
936 /* Adds REF to the chain CHAIN. */
939 add_ref_to_chain (chain_p chain
, dref ref
)
941 dref root
= get_chain_root (chain
);
944 gcc_assert (root
->offset
.sle (ref
->offset
));
945 dist
= ref
->offset
- root
->offset
;
946 if (double_int::from_uhwi (MAX_DISTANCE
).ule (dist
))
951 gcc_assert (dist
.fits_uhwi ());
953 chain
->refs
.safe_push (ref
);
955 ref
->distance
= dist
.to_uhwi ();
957 if (ref
->distance
>= chain
->length
)
959 chain
->length
= ref
->distance
;
960 chain
->has_max_use_after
= false;
963 if (ref
->distance
== chain
->length
964 && ref
->pos
> root
->pos
)
965 chain
->has_max_use_after
= true;
967 chain
->all_always_accessed
&= ref
->always_accessed
;
970 /* Returns the chain for invariant component COMP. */
973 make_invariant_chain (struct component
*comp
)
975 chain_p chain
= XCNEW (struct chain
);
979 chain
->type
= CT_INVARIANT
;
981 chain
->all_always_accessed
= true;
983 FOR_EACH_VEC_ELT (comp
->refs
, i
, ref
)
985 chain
->refs
.safe_push (ref
);
986 chain
->all_always_accessed
&= ref
->always_accessed
;
992 /* Make a new chain rooted at REF. */
995 make_rooted_chain (dref ref
)
997 chain_p chain
= XCNEW (struct chain
);
999 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
1001 chain
->refs
.safe_push (ref
);
1002 chain
->all_always_accessed
= ref
->always_accessed
;
1009 /* Returns true if CHAIN is not trivial. */
1012 nontrivial_chain_p (chain_p chain
)
1014 return chain
!= NULL
&& chain
->refs
.length () > 1;
1017 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1021 name_for_ref (dref ref
)
1025 if (is_gimple_assign (ref
->stmt
))
1027 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1028 name
= gimple_assign_lhs (ref
->stmt
);
1030 name
= gimple_assign_rhs1 (ref
->stmt
);
1033 name
= PHI_RESULT (ref
->stmt
);
1035 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1038 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1039 iterations of the innermost enclosing loop). */
1042 valid_initializer_p (struct data_reference
*ref
,
1043 unsigned distance
, struct data_reference
*root
)
1045 aff_tree diff
, base
, step
;
1048 /* Both REF and ROOT must be accessing the same object. */
1049 if (!operand_equal_p (DR_BASE_ADDRESS (ref
), DR_BASE_ADDRESS (root
), 0))
1052 /* The initializer is defined outside of loop, hence its address must be
1053 invariant inside the loop. */
1054 gcc_assert (integer_zerop (DR_STEP (ref
)));
1056 /* If the address of the reference is invariant, initializer must access
1057 exactly the same location. */
1058 if (integer_zerop (DR_STEP (root
)))
1059 return (operand_equal_p (DR_OFFSET (ref
), DR_OFFSET (root
), 0)
1060 && operand_equal_p (DR_INIT (ref
), DR_INIT (root
), 0));
1062 /* Verify that this index of REF is equal to the root's index at
1063 -DISTANCE-th iteration. */
1064 aff_combination_dr_offset (root
, &diff
);
1065 aff_combination_dr_offset (ref
, &base
);
1066 aff_combination_scale (&base
, double_int_minus_one
);
1067 aff_combination_add (&diff
, &base
);
1069 tree_to_aff_combination_expand (DR_STEP (root
), TREE_TYPE (DR_STEP (root
)),
1070 &step
, &name_expansions
);
1071 if (!aff_combination_constant_multiple_p (&diff
, &step
, &off
))
1074 if (off
!= double_int::from_uhwi (distance
))
1080 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1081 initial value is correct (equal to initial value of REF shifted by one
1082 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1083 is the root of the current chain. */
1086 find_looparound_phi (struct loop
*loop
, dref ref
, dref root
)
1088 tree name
, init
, init_ref
;
1089 gimple phi
= NULL
, init_stmt
;
1090 edge latch
= loop_latch_edge (loop
);
1091 struct data_reference init_dr
;
1092 gimple_stmt_iterator psi
;
1094 if (is_gimple_assign (ref
->stmt
))
1096 if (DR_IS_READ (ref
->ref
))
1097 name
= gimple_assign_lhs (ref
->stmt
);
1099 name
= gimple_assign_rhs1 (ref
->stmt
);
1102 name
= PHI_RESULT (ref
->stmt
);
1106 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1108 phi
= gsi_stmt (psi
);
1109 if (PHI_ARG_DEF_FROM_EDGE (phi
, latch
) == name
)
1113 if (gsi_end_p (psi
))
1116 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1117 if (TREE_CODE (init
) != SSA_NAME
)
1119 init_stmt
= SSA_NAME_DEF_STMT (init
);
1120 if (gimple_code (init_stmt
) != GIMPLE_ASSIGN
)
1122 gcc_assert (gimple_assign_lhs (init_stmt
) == init
);
1124 init_ref
= gimple_assign_rhs1 (init_stmt
);
1125 if (!REFERENCE_CLASS_P (init_ref
)
1126 && !DECL_P (init_ref
))
1129 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1130 loop enclosing PHI). */
1131 memset (&init_dr
, 0, sizeof (struct data_reference
));
1132 DR_REF (&init_dr
) = init_ref
;
1133 DR_STMT (&init_dr
) = phi
;
1134 if (!dr_analyze_innermost (&init_dr
, loop
))
1137 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1143 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1146 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1148 dref nw
= XCNEW (struct dref_d
), aref
;
1152 nw
->distance
= ref
->distance
+ 1;
1153 nw
->always_accessed
= 1;
1155 FOR_EACH_VEC_ELT (chain
->refs
, i
, aref
)
1156 if (aref
->distance
>= nw
->distance
)
1158 chain
->refs
.safe_insert (i
, nw
);
1160 if (nw
->distance
> chain
->length
)
1162 chain
->length
= nw
->distance
;
1163 chain
->has_max_use_after
= false;
1167 /* For references in CHAIN that are copied around the LOOP (created previously
1168 by PRE, or by user), add the results of such copies to the chain. This
1169 enables us to remove the copies by unrolling, and may need less registers
1170 (also, it may allow us to combine chains together). */
1173 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1176 dref ref
, root
= get_chain_root (chain
);
1179 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
1181 phi
= find_looparound_phi (loop
, ref
, root
);
1185 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1186 insert_looparound_copy (chain
, ref
, phi
);
1190 /* Find roots of the values and determine distances in the component COMP.
1191 The references are redistributed into CHAINS. LOOP is the current
1195 determine_roots_comp (struct loop
*loop
,
1196 struct component
*comp
,
1197 vec
<chain_p
> *chains
)
1201 chain_p chain
= NULL
;
1202 double_int last_ofs
= double_int_zero
;
1204 /* Invariants are handled specially. */
1205 if (comp
->comp_step
== RS_INVARIANT
)
1207 chain
= make_invariant_chain (comp
);
1208 chains
->safe_push (chain
);
1212 comp
->refs
.qsort (order_drefs
);
1214 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
1216 if (!chain
|| DR_IS_WRITE (a
->ref
)
1217 || double_int::from_uhwi (MAX_DISTANCE
).ule (a
->offset
- last_ofs
))
1219 if (nontrivial_chain_p (chain
))
1221 add_looparound_copies (loop
, chain
);
1222 chains
->safe_push (chain
);
1225 release_chain (chain
);
1226 chain
= make_rooted_chain (a
);
1227 last_ofs
= a
->offset
;
1231 add_ref_to_chain (chain
, a
);
1234 if (nontrivial_chain_p (chain
))
1236 add_looparound_copies (loop
, chain
);
1237 chains
->safe_push (chain
);
1240 release_chain (chain
);
1243 /* Find roots of the values and determine distances in components COMPS, and
1244 separates the references to CHAINS. LOOP is the current loop. */
1247 determine_roots (struct loop
*loop
,
1248 struct component
*comps
, vec
<chain_p
> *chains
)
1250 struct component
*comp
;
1252 for (comp
= comps
; comp
; comp
= comp
->next
)
1253 determine_roots_comp (loop
, comp
, chains
);
1256 /* Replace the reference in statement STMT with temporary variable
1257 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1258 the reference in the statement. IN_LHS is true if the reference
1259 is in the lhs of STMT, false if it is in rhs. */
1262 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1266 gimple_stmt_iterator bsi
, psi
;
1268 if (gimple_code (stmt
) == GIMPLE_PHI
)
1270 gcc_assert (!in_lhs
&& !set
);
1272 val
= PHI_RESULT (stmt
);
1273 bsi
= gsi_after_labels (gimple_bb (stmt
));
1274 psi
= gsi_for_stmt (stmt
);
1275 remove_phi_node (&psi
, false);
1277 /* Turn the phi node into GIMPLE_ASSIGN. */
1278 new_stmt
= gimple_build_assign (val
, new_tree
);
1279 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1283 /* Since the reference is of gimple_reg type, it should only
1284 appear as lhs or rhs of modify statement. */
1285 gcc_assert (is_gimple_assign (stmt
));
1287 bsi
= gsi_for_stmt (stmt
);
1289 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1292 gcc_assert (!in_lhs
);
1293 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1294 stmt
= gsi_stmt (bsi
);
1301 /* We have statement
1305 If OLD is a memory reference, then VAL is gimple_val, and we transform
1311 Otherwise, we are replacing a combination chain,
1312 VAL is the expression that performs the combination, and OLD is an
1313 SSA name. In this case, we transform the assignment to
1320 val
= gimple_assign_lhs (stmt
);
1321 if (TREE_CODE (val
) != SSA_NAME
)
1323 val
= gimple_assign_rhs1 (stmt
);
1324 gcc_assert (gimple_assign_single_p (stmt
));
1325 if (TREE_CLOBBER_P (val
))
1326 val
= get_or_create_ssa_default_def (cfun
, SSA_NAME_VAR (new_tree
));
1328 gcc_assert (gimple_assign_copy_p (stmt
));
1340 val
= gimple_assign_lhs (stmt
);
1343 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1344 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1347 /* Returns a memory reference to DR in the ITER-th iteration of
1348 the loop it was analyzed in. Append init stmts to STMTS. */
1351 ref_at_iteration (data_reference_p dr
, int iter
, gimple_seq
*stmts
)
1353 tree off
= DR_OFFSET (dr
);
1354 tree coff
= DR_INIT (dr
);
1357 else if (TREE_CODE (DR_STEP (dr
)) == INTEGER_CST
)
1358 coff
= size_binop (PLUS_EXPR
, coff
,
1359 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1361 off
= size_binop (PLUS_EXPR
, off
,
1362 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1363 tree addr
= fold_build_pointer_plus (DR_BASE_ADDRESS (dr
), off
);
1364 addr
= force_gimple_operand_1 (addr
, stmts
, is_gimple_mem_ref_addr
,
1366 tree alias_ptr
= fold_convert (reference_alias_ptr_type (DR_REF (dr
)), coff
);
1367 /* While data-ref analysis punts on bit offsets it still handles
1368 bitfield accesses at byte boundaries. Cope with that. Note that
1369 we cannot simply re-apply the outer COMPONENT_REF because the
1370 byte-granular portion of it is already applied via DR_INIT and
1371 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1372 start at offset zero. */
1373 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
1374 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
1376 tree field
= TREE_OPERAND (DR_REF (dr
), 1);
1377 return build3 (BIT_FIELD_REF
, TREE_TYPE (DR_REF (dr
)),
1378 build2 (MEM_REF
, DECL_BIT_FIELD_TYPE (field
),
1380 DECL_SIZE (field
), bitsize_zero_node
);
1383 return fold_build2 (MEM_REF
, TREE_TYPE (DR_REF (dr
)), addr
, alias_ptr
);
1386 /* Get the initialization expression for the INDEX-th temporary variable
1390 get_init_expr (chain_p chain
, unsigned index
)
1392 if (chain
->type
== CT_COMBINATION
)
1394 tree e1
= get_init_expr (chain
->ch1
, index
);
1395 tree e2
= get_init_expr (chain
->ch2
, index
);
1397 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1400 return chain
->inits
[index
];
1403 /* Returns a new temporary variable used for the I-th variable carrying
1404 value of REF. The variable's uid is marked in TMP_VARS. */
1407 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1409 tree type
= TREE_TYPE (ref
);
1410 /* We never access the components of the temporary variable in predictive
1412 tree var
= create_tmp_reg (type
, get_lsm_tmp_name (ref
, i
));
1413 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1417 /* Creates the variables for CHAIN, as well as phi nodes for them and
1418 initialization on entry to LOOP. Uids of the newly created
1419 temporary variables are marked in TMP_VARS. */
1422 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1425 unsigned n
= chain
->length
;
1426 dref root
= get_chain_root (chain
);
1427 bool reuse_first
= !chain
->has_max_use_after
;
1428 tree ref
, init
, var
, next
;
1431 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1433 /* If N == 0, then all the references are within the single iteration. And
1434 since this is an nonempty chain, reuse_first cannot be true. */
1435 gcc_assert (n
> 0 || !reuse_first
);
1437 chain
->vars
.create (n
+ 1);
1439 if (chain
->type
== CT_COMBINATION
)
1440 ref
= gimple_assign_lhs (root
->stmt
);
1442 ref
= DR_REF (root
->ref
);
1444 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1446 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1447 chain
->vars
.quick_push (var
);
1450 chain
->vars
.quick_push (chain
->vars
[0]);
1452 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
1453 chain
->vars
[i
] = make_ssa_name (var
, NULL
);
1455 for (i
= 0; i
< n
; i
++)
1457 var
= chain
->vars
[i
];
1458 next
= chain
->vars
[i
+ 1];
1459 init
= get_init_expr (chain
, i
);
1461 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1463 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1465 phi
= create_phi_node (var
, loop
->header
);
1466 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1467 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1471 /* Create the variables and initialization statement for root of chain
1472 CHAIN. Uids of the newly created temporary variables are marked
1476 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1478 dref root
= get_chain_root (chain
);
1479 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1480 || chain
->type
== CT_COMBINATION
);
1482 initialize_root_vars (loop
, chain
, tmp_vars
);
1483 replace_ref_with (root
->stmt
,
1484 chain
->vars
[chain
->length
],
1488 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1489 initialization on entry to LOOP if necessary. The ssa name for the variable
1490 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1491 around the loop is created. Uid of the newly created temporary variable
1492 is marked in TMP_VARS. INITS is the list containing the (single)
1496 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1497 vec
<tree
> *vars
, vec
<tree
> inits
,
1501 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1504 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1506 /* Find the initializer for the variable, and check that it cannot
1510 vars
->create (written
? 2 : 1);
1511 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1512 vars
->quick_push (var
);
1514 vars
->quick_push ((*vars
)[0]);
1516 FOR_EACH_VEC_ELT (*vars
, i
, var
)
1517 (*vars
)[i
] = make_ssa_name (var
, NULL
);
1521 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1523 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1528 phi
= create_phi_node (var
, loop
->header
);
1529 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1530 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1534 gimple init_stmt
= gimple_build_assign (var
, init
);
1535 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1540 /* Execute load motion for references in chain CHAIN. Uids of the newly
1541 created temporary variables are marked in TMP_VARS. */
1544 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1546 auto_vec
<tree
> vars
;
1548 unsigned n_writes
= 0, ridx
, i
;
1551 gcc_assert (chain
->type
== CT_INVARIANT
);
1552 gcc_assert (!chain
->combined
);
1553 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1554 if (DR_IS_WRITE (a
->ref
))
1557 /* If there are no reads in the loop, there is nothing to do. */
1558 if (n_writes
== chain
->refs
.length ())
1561 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1562 &vars
, chain
->inits
, tmp_vars
);
1565 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1567 bool is_read
= DR_IS_READ (a
->ref
);
1569 if (DR_IS_WRITE (a
->ref
))
1575 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1582 replace_ref_with (a
->stmt
, vars
[ridx
],
1583 !is_read
, !is_read
);
1587 /* Returns the single statement in that NAME is used, excepting
1588 the looparound phi nodes contained in one of the chains. If there is no
1589 such statement, or more statements, NULL is returned. */
1592 single_nonlooparound_use (tree name
)
1595 imm_use_iterator it
;
1596 gimple stmt
, ret
= NULL
;
1598 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1600 stmt
= USE_STMT (use
);
1602 if (gimple_code (stmt
) == GIMPLE_PHI
)
1604 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1605 could not be processed anyway, so just fail for them. */
1606 if (bitmap_bit_p (looparound_phis
,
1607 SSA_NAME_VERSION (PHI_RESULT (stmt
))))
1612 else if (is_gimple_debug (stmt
))
1614 else if (ret
!= NULL
)
1623 /* Remove statement STMT, as well as the chain of assignments in that it is
1627 remove_stmt (gimple stmt
)
1631 gimple_stmt_iterator psi
;
1633 if (gimple_code (stmt
) == GIMPLE_PHI
)
1635 name
= PHI_RESULT (stmt
);
1636 next
= single_nonlooparound_use (name
);
1637 reset_debug_uses (stmt
);
1638 psi
= gsi_for_stmt (stmt
);
1639 remove_phi_node (&psi
, true);
1642 || !gimple_assign_ssa_name_copy_p (next
)
1643 || gimple_assign_rhs1 (next
) != name
)
1651 gimple_stmt_iterator bsi
;
1653 bsi
= gsi_for_stmt (stmt
);
1655 name
= gimple_assign_lhs (stmt
);
1656 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1658 next
= single_nonlooparound_use (name
);
1659 reset_debug_uses (stmt
);
1661 unlink_stmt_vdef (stmt
);
1662 gsi_remove (&bsi
, true);
1663 release_defs (stmt
);
1666 || !gimple_assign_ssa_name_copy_p (next
)
1667 || gimple_assign_rhs1 (next
) != name
)
1674 /* Perform the predictive commoning optimization for a chain CHAIN.
1675 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1678 execute_pred_commoning_chain (struct loop
*loop
, chain_p chain
,
1685 if (chain
->combined
)
1687 /* For combined chains, just remove the statements that are used to
1688 compute the values of the expression (except for the root one). */
1689 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1690 remove_stmt (a
->stmt
);
1694 /* For non-combined chains, set up the variables that hold its value,
1695 and replace the uses of the original references by these
1697 initialize_root (loop
, chain
, tmp_vars
);
1698 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1700 var
= chain
->vars
[chain
->length
- a
->distance
];
1701 replace_ref_with (a
->stmt
, var
, false, false);
1706 /* Determines the unroll factor necessary to remove as many temporary variable
1707 copies as possible. CHAINS is the list of chains that will be
1711 determine_unroll_factor (vec
<chain_p
> chains
)
1714 unsigned factor
= 1, af
, nfactor
, i
;
1715 unsigned max
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1717 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1719 if (chain
->type
== CT_INVARIANT
|| chain
->combined
)
1722 /* The best unroll factor for this chain is equal to the number of
1723 temporary variables that we create for it. */
1725 if (chain
->has_max_use_after
)
1728 nfactor
= factor
* af
/ gcd (factor
, af
);
1736 /* Perform the predictive commoning optimization for CHAINS.
1737 Uids of the newly created temporary variables are marked in TMP_VARS. */
1740 execute_pred_commoning (struct loop
*loop
, vec
<chain_p
> chains
,
1746 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1748 if (chain
->type
== CT_INVARIANT
)
1749 execute_load_motion (loop
, chain
, tmp_vars
);
1751 execute_pred_commoning_chain (loop
, chain
, tmp_vars
);
1754 update_ssa (TODO_update_ssa_only_virtuals
);
1757 /* For each reference in CHAINS, if its defining statement is
1758 phi node, record the ssa name that is defined by it. */
1761 replace_phis_by_defined_names (vec
<chain_p
> chains
)
1767 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1768 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1770 if (gimple_code (a
->stmt
) == GIMPLE_PHI
)
1772 a
->name_defined_by_phi
= PHI_RESULT (a
->stmt
);
1778 /* For each reference in CHAINS, if name_defined_by_phi is not
1779 NULL, use it to set the stmt field. */
1782 replace_names_by_phis (vec
<chain_p
> chains
)
1788 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1789 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1790 if (a
->stmt
== NULL
)
1792 a
->stmt
= SSA_NAME_DEF_STMT (a
->name_defined_by_phi
);
1793 gcc_assert (gimple_code (a
->stmt
) == GIMPLE_PHI
);
1794 a
->name_defined_by_phi
= NULL_TREE
;
1798 /* Wrapper over execute_pred_commoning, to pass it as a callback
1799 to tree_transform_and_unroll_loop. */
1803 vec
<chain_p
> chains
;
1808 execute_pred_commoning_cbck (struct loop
*loop
, void *data
)
1810 struct epcc_data
*const dta
= (struct epcc_data
*) data
;
1812 /* Restore phi nodes that were replaced by ssa names before
1813 tree_transform_and_unroll_loop (see detailed description in
1814 tree_predictive_commoning_loop). */
1815 replace_names_by_phis (dta
->chains
);
1816 execute_pred_commoning (loop
, dta
->chains
, dta
->tmp_vars
);
1819 /* Base NAME and all the names in the chain of phi nodes that use it
1820 on variable VAR. The phi nodes are recognized by being in the copies of
1821 the header of the LOOP. */
1824 base_names_in_chain_on (struct loop
*loop
, tree name
, tree var
)
1827 imm_use_iterator iter
;
1829 replace_ssa_name_symbol (name
, var
);
1834 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1836 if (gimple_code (stmt
) == GIMPLE_PHI
1837 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1840 BREAK_FROM_IMM_USE_STMT (iter
);
1846 name
= PHI_RESULT (phi
);
1847 replace_ssa_name_symbol (name
, var
);
1851 /* Given an unrolled LOOP after predictive commoning, remove the
1852 register copies arising from phi nodes by changing the base
1853 variables of SSA names. TMP_VARS is the set of the temporary variables
1854 for those we want to perform this. */
1857 eliminate_temp_copies (struct loop
*loop
, bitmap tmp_vars
)
1861 tree name
, use
, var
;
1862 gimple_stmt_iterator psi
;
1864 e
= loop_latch_edge (loop
);
1865 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1867 phi
= gsi_stmt (psi
);
1868 name
= PHI_RESULT (phi
);
1869 var
= SSA_NAME_VAR (name
);
1870 if (!var
|| !bitmap_bit_p (tmp_vars
, DECL_UID (var
)))
1872 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1873 gcc_assert (TREE_CODE (use
) == SSA_NAME
);
1875 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1876 stmt
= SSA_NAME_DEF_STMT (use
);
1877 while (gimple_code (stmt
) == GIMPLE_PHI
1878 /* In case we could not unroll the loop enough to eliminate
1879 all copies, we may reach the loop header before the defining
1880 statement (in that case, some register copies will be present
1881 in loop latch in the final code, corresponding to the newly
1882 created looparound phi nodes). */
1883 && gimple_bb (stmt
) != loop
->header
)
1885 gcc_assert (single_pred_p (gimple_bb (stmt
)));
1886 use
= PHI_ARG_DEF (stmt
, 0);
1887 stmt
= SSA_NAME_DEF_STMT (use
);
1890 base_names_in_chain_on (loop
, use
, var
);
1894 /* Returns true if CHAIN is suitable to be combined. */
1897 chain_can_be_combined_p (chain_p chain
)
1899 return (!chain
->combined
1900 && (chain
->type
== CT_LOAD
|| chain
->type
== CT_COMBINATION
));
1903 /* Returns the modify statement that uses NAME. Skips over assignment
1904 statements, NAME is replaced with the actual name used in the returned
1908 find_use_stmt (tree
*name
)
1913 /* Skip over assignments. */
1916 stmt
= single_nonlooparound_use (*name
);
1920 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1923 lhs
= gimple_assign_lhs (stmt
);
1924 if (TREE_CODE (lhs
) != SSA_NAME
)
1927 if (gimple_assign_copy_p (stmt
))
1929 rhs
= gimple_assign_rhs1 (stmt
);
1935 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1936 == GIMPLE_BINARY_RHS
)
1943 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1946 may_reassociate_p (tree type
, enum tree_code code
)
1948 if (FLOAT_TYPE_P (type
)
1949 && !flag_unsafe_math_optimizations
)
1952 return (commutative_tree_code (code
)
1953 && associative_tree_code (code
));
1956 /* If the operation used in STMT is associative and commutative, go through the
1957 tree of the same operations and returns its root. Distance to the root
1958 is stored in DISTANCE. */
1961 find_associative_operation_root (gimple stmt
, unsigned *distance
)
1965 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1966 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1969 if (!may_reassociate_p (type
, code
))
1974 lhs
= gimple_assign_lhs (stmt
);
1975 gcc_assert (TREE_CODE (lhs
) == SSA_NAME
);
1977 next
= find_use_stmt (&lhs
);
1979 || gimple_assign_rhs_code (next
) != code
)
1991 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
1992 is no such statement, returns NULL_TREE. In case the operation used on
1993 NAME1 and NAME2 is associative and commutative, returns the root of the
1994 tree formed by this operation instead of the statement that uses NAME1 or
1998 find_common_use_stmt (tree
*name1
, tree
*name2
)
2000 gimple stmt1
, stmt2
;
2002 stmt1
= find_use_stmt (name1
);
2006 stmt2
= find_use_stmt (name2
);
2013 stmt1
= find_associative_operation_root (stmt1
, NULL
);
2016 stmt2
= find_associative_operation_root (stmt2
, NULL
);
2020 return (stmt1
== stmt2
? stmt1
: NULL
);
2023 /* Checks whether R1 and R2 are combined together using CODE, with the result
2024 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2025 if it is true. If CODE is ERROR_MARK, set these values instead. */
2028 combinable_refs_p (dref r1
, dref r2
,
2029 enum tree_code
*code
, bool *swap
, tree
*rslt_type
)
2031 enum tree_code acode
;
2037 name1
= name_for_ref (r1
);
2038 name2
= name_for_ref (r2
);
2039 gcc_assert (name1
!= NULL_TREE
&& name2
!= NULL_TREE
);
2041 stmt
= find_common_use_stmt (&name1
, &name2
);
2044 /* A simple post-dominance check - make sure the combination
2045 is executed under the same condition as the references. */
2046 || (gimple_bb (stmt
) != gimple_bb (r1
->stmt
)
2047 && gimple_bb (stmt
) != gimple_bb (r2
->stmt
)))
2050 acode
= gimple_assign_rhs_code (stmt
);
2051 aswap
= (!commutative_tree_code (acode
)
2052 && gimple_assign_rhs1 (stmt
) != name1
);
2053 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2055 if (*code
== ERROR_MARK
)
2063 return (*code
== acode
2065 && *rslt_type
== atype
);
2068 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2069 an assignment of the remaining operand. */
2072 remove_name_from_operation (gimple stmt
, tree op
)
2075 gimple_stmt_iterator si
;
2077 gcc_assert (is_gimple_assign (stmt
));
2079 if (gimple_assign_rhs1 (stmt
) == op
)
2080 other_op
= gimple_assign_rhs2 (stmt
);
2082 other_op
= gimple_assign_rhs1 (stmt
);
2084 si
= gsi_for_stmt (stmt
);
2085 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2087 /* We should not have reallocated STMT. */
2088 gcc_assert (gsi_stmt (si
) == stmt
);
2093 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2094 are combined in a single statement, and returns this statement. */
2097 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2099 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2100 gimple new_stmt
, tmp_stmt
;
2101 tree new_name
, tmp_name
, var
, r1
, r2
;
2102 unsigned dist1
, dist2
;
2103 enum tree_code code
;
2104 tree type
= TREE_TYPE (name1
);
2105 gimple_stmt_iterator bsi
;
2107 stmt1
= find_use_stmt (&name1
);
2108 stmt2
= find_use_stmt (&name2
);
2109 root1
= find_associative_operation_root (stmt1
, &dist1
);
2110 root2
= find_associative_operation_root (stmt2
, &dist2
);
2111 code
= gimple_assign_rhs_code (stmt1
);
2113 gcc_assert (root1
&& root2
&& root1
== root2
2114 && code
== gimple_assign_rhs_code (stmt2
));
2116 /* Find the root of the nearest expression in that both NAME1 and NAME2
2123 while (dist1
> dist2
)
2125 s1
= find_use_stmt (&r1
);
2126 r1
= gimple_assign_lhs (s1
);
2129 while (dist2
> dist1
)
2131 s2
= find_use_stmt (&r2
);
2132 r2
= gimple_assign_lhs (s2
);
2138 s1
= find_use_stmt (&r1
);
2139 r1
= gimple_assign_lhs (s1
);
2140 s2
= find_use_stmt (&r2
);
2141 r2
= gimple_assign_lhs (s2
);
2144 /* Remove NAME1 and NAME2 from the statements in that they are used
2146 remove_name_from_operation (stmt1
, name1
);
2147 remove_name_from_operation (stmt2
, name2
);
2149 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2150 combine it with the rhs of S1. */
2151 var
= create_tmp_reg (type
, "predreastmp");
2152 new_name
= make_ssa_name (var
, NULL
);
2153 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2155 var
= create_tmp_reg (type
, "predreastmp");
2156 tmp_name
= make_ssa_name (var
, NULL
);
2158 /* Rhs of S1 may now be either a binary expression with operation
2159 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2160 so that name1 or name2 was removed from it). */
2161 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2163 gimple_assign_rhs1 (s1
),
2164 gimple_assign_rhs2 (s1
));
2166 bsi
= gsi_for_stmt (s1
);
2167 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2168 s1
= gsi_stmt (bsi
);
2171 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2172 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2177 /* Returns the statement that combines references R1 and R2. In case R1
2178 and R2 are not used in the same statement, but they are used with an
2179 associative and commutative operation in the same expression, reassociate
2180 the expression so that they are used in the same statement. */
2183 stmt_combining_refs (dref r1
, dref r2
)
2185 gimple stmt1
, stmt2
;
2186 tree name1
= name_for_ref (r1
);
2187 tree name2
= name_for_ref (r2
);
2189 stmt1
= find_use_stmt (&name1
);
2190 stmt2
= find_use_stmt (&name2
);
2194 return reassociate_to_the_same_stmt (name1
, name2
);
2197 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2198 description of the new chain is returned, otherwise we return NULL. */
2201 combine_chains (chain_p ch1
, chain_p ch2
)
2204 enum tree_code op
= ERROR_MARK
;
2209 tree rslt_type
= NULL_TREE
;
2213 if (ch1
->length
!= ch2
->length
)
2216 if (ch1
->refs
.length () != ch2
->refs
.length ())
2219 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2220 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2222 if (r1
->distance
!= r2
->distance
)
2225 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2236 new_chain
= XCNEW (struct chain
);
2237 new_chain
->type
= CT_COMBINATION
;
2239 new_chain
->ch1
= ch1
;
2240 new_chain
->ch2
= ch2
;
2241 new_chain
->rslt_type
= rslt_type
;
2242 new_chain
->length
= ch1
->length
;
2244 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2245 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2247 nw
= XCNEW (struct dref_d
);
2248 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2249 nw
->distance
= r1
->distance
;
2251 new_chain
->refs
.safe_push (nw
);
2254 new_chain
->has_max_use_after
= false;
2255 root_stmt
= get_chain_root (new_chain
)->stmt
;
2256 for (i
= 1; new_chain
->refs
.iterate (i
, &nw
); i
++)
2258 if (nw
->distance
== new_chain
->length
2259 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2261 new_chain
->has_max_use_after
= true;
2266 ch1
->combined
= true;
2267 ch2
->combined
= true;
2271 /* Try to combine the CHAINS. */
2274 try_combine_chains (vec
<chain_p
> *chains
)
2277 chain_p ch1
, ch2
, cch
;
2278 auto_vec
<chain_p
> worklist
;
2280 FOR_EACH_VEC_ELT (*chains
, i
, ch1
)
2281 if (chain_can_be_combined_p (ch1
))
2282 worklist
.safe_push (ch1
);
2284 while (!worklist
.is_empty ())
2286 ch1
= worklist
.pop ();
2287 if (!chain_can_be_combined_p (ch1
))
2290 FOR_EACH_VEC_ELT (*chains
, j
, ch2
)
2292 if (!chain_can_be_combined_p (ch2
))
2295 cch
= combine_chains (ch1
, ch2
);
2298 worklist
.safe_push (cch
);
2299 chains
->safe_push (cch
);
2306 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2307 impossible because one of these initializers may trap, true otherwise. */
2310 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2312 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2313 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2317 edge entry
= loop_preheader_edge (loop
);
2319 /* Find the initializers for the variables, and check that they cannot
2321 chain
->inits
.create (n
);
2322 for (i
= 0; i
< n
; i
++)
2323 chain
->inits
.quick_push (NULL_TREE
);
2325 /* If we have replaced some looparound phi nodes, use their initializers
2326 instead of creating our own. */
2327 FOR_EACH_VEC_ELT (chain
->refs
, i
, laref
)
2329 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2332 gcc_assert (laref
->distance
> 0);
2333 chain
->inits
[n
- laref
->distance
]
2334 = PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
);
2337 for (i
= 0; i
< n
; i
++)
2339 if (chain
->inits
[i
] != NULL_TREE
)
2342 init
= ref_at_iteration (dr
, (int) i
- n
, &stmts
);
2343 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2347 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2349 chain
->inits
[i
] = init
;
2355 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2356 be used because the initializers might trap. */
2359 prepare_initializers (struct loop
*loop
, vec
<chain_p
> chains
)
2364 for (i
= 0; i
< chains
.length (); )
2367 if (prepare_initializers_chain (loop
, chain
))
2371 release_chain (chain
);
2372 chains
.unordered_remove (i
);
2377 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2381 tree_predictive_commoning_loop (struct loop
*loop
)
2383 vec
<data_reference_p
> datarefs
;
2384 vec
<ddr_p
> dependences
;
2385 struct component
*components
;
2386 vec
<chain_p
> chains
= vNULL
;
2387 unsigned unroll_factor
;
2388 struct tree_niter_desc desc
;
2389 bool unroll
= false;
2393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2394 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2396 /* Find the data references and split them into components according to their
2397 dependence relations. */
2398 stack_vec
<loop_p
, 3> loop_nest
;
2399 dependences
.create (10);
2400 datarefs
.create (10);
2401 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
2404 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2405 fprintf (dump_file
, "Cannot analyze data dependencies\n");
2406 free_data_refs (datarefs
);
2407 free_dependence_relations (dependences
);
2411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2412 dump_data_dependence_relations (dump_file
, dependences
);
2414 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2415 loop_nest
.release ();
2416 free_dependence_relations (dependences
);
2419 free_data_refs (datarefs
);
2423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2425 fprintf (dump_file
, "Initial state:\n\n");
2426 dump_components (dump_file
, components
);
2429 /* Find the suitable components and split them into chains. */
2430 components
= filter_suitable_components (loop
, components
);
2432 tmp_vars
= BITMAP_ALLOC (NULL
);
2433 looparound_phis
= BITMAP_ALLOC (NULL
);
2434 determine_roots (loop
, components
, &chains
);
2435 release_components (components
);
2437 if (!chains
.exists ())
2439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2441 "Predictive commoning failed: no suitable chains\n");
2444 prepare_initializers (loop
, chains
);
2446 /* Try to combine the chains that are always worked with together. */
2447 try_combine_chains (&chains
);
2449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2451 fprintf (dump_file
, "Before commoning:\n\n");
2452 dump_chains (dump_file
, chains
);
2455 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2456 that its number of iterations is divisible by the factor. */
2457 unroll_factor
= determine_unroll_factor (chains
);
2459 unroll
= (unroll_factor
> 1
2460 && can_unroll_loop_p (loop
, unroll_factor
, &desc
));
2461 exit
= single_dom_exit (loop
);
2463 /* Execute the predictive commoning transformations, and possibly unroll the
2467 struct epcc_data dta
;
2469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2470 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2472 dta
.chains
= chains
;
2473 dta
.tmp_vars
= tmp_vars
;
2475 update_ssa (TODO_update_ssa_only_virtuals
);
2477 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2478 execute_pred_commoning_cbck is called may cause phi nodes to be
2479 reallocated, which is a problem since CHAINS may point to these
2480 statements. To fix this, we store the ssa names defined by the
2481 phi nodes here instead of the phi nodes themselves, and restore
2482 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2483 replace_phis_by_defined_names (chains
);
2485 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2486 execute_pred_commoning_cbck
, &dta
);
2487 eliminate_temp_copies (loop
, tmp_vars
);
2491 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2493 "Executing predictive commoning without unrolling.\n");
2494 execute_pred_commoning (loop
, chains
, tmp_vars
);
2498 release_chains (chains
);
2499 free_data_refs (datarefs
);
2500 BITMAP_FREE (tmp_vars
);
2501 BITMAP_FREE (looparound_phis
);
2503 free_affine_expand_cache (&name_expansions
);
2508 /* Runs predictive commoning. */
2511 tree_predictive_commoning (void)
2513 bool unrolled
= false;
2517 initialize_original_copy_tables ();
2518 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
2519 if (optimize_loop_for_speed_p (loop
))
2521 unrolled
|= tree_predictive_commoning_loop (loop
);
2527 ret
= TODO_cleanup_cfg
;
2529 free_original_copy_tables ();
2534 /* Predictive commoning Pass. */
2537 run_tree_predictive_commoning (void)
2542 return tree_predictive_commoning ();
2546 gate_tree_predictive_commoning (void)
2548 return flag_predictive_commoning
!= 0;
2553 const pass_data pass_data_predcom
=
2555 GIMPLE_PASS
, /* type */
2557 OPTGROUP_LOOP
, /* optinfo_flags */
2558 true, /* has_gate */
2559 true, /* has_execute */
2560 TV_PREDCOM
, /* tv_id */
2561 PROP_cfg
, /* properties_required */
2562 0, /* properties_provided */
2563 0, /* properties_destroyed */
2564 0, /* todo_flags_start */
2565 TODO_update_ssa_only_virtuals
, /* todo_flags_finish */
2568 class pass_predcom
: public gimple_opt_pass
2571 pass_predcom (gcc::context
*ctxt
)
2572 : gimple_opt_pass (pass_data_predcom
, ctxt
)
2575 /* opt_pass methods: */
2576 bool gate () { return gate_tree_predictive_commoning (); }
2577 unsigned int execute () { return run_tree_predictive_commoning (); }
2579 }; // class pass_predcom
2584 make_pass_predcom (gcc::context
*ctxt
)
2586 return new pass_predcom (ctxt
);