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 /* predcom pass isn't prepared to handle calls with data references. */
736 if (is_gimple_call (DR_STMT (dr
)))
738 dr
->aux
= (void *) (size_t) i
;
743 /* A component reserved for the "bad" data references. */
747 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
749 enum ref_step_type dummy
;
751 if (!suitable_reference_p (dr
, &dummy
))
753 ia
= (unsigned) (size_t) dr
->aux
;
754 merge_comps (comp_father
, comp_size
, n
, ia
);
758 FOR_EACH_VEC_ELT (depends
, i
, ddr
)
760 double_int dummy_off
;
762 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
767 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
768 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
772 bad
= component_of (comp_father
, n
);
774 /* If both A and B are reads, we may ignore unsuitable dependences. */
775 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
776 && (ia
== bad
|| ib
== bad
777 || !determine_offset (dra
, drb
, &dummy_off
)))
780 merge_comps (comp_father
, comp_size
, ia
, ib
);
783 comps
= XCNEWVEC (struct component
*, n
);
784 bad
= component_of (comp_father
, n
);
785 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
787 ia
= (unsigned) (size_t) dr
->aux
;
788 ca
= component_of (comp_father
, ia
);
795 comp
= XCNEW (struct component
);
796 comp
->refs
.create (comp_size
[ca
]);
800 dataref
= XCNEW (struct dref_d
);
802 dataref
->stmt
= DR_STMT (dr
);
803 dataref
->offset
= double_int_zero
;
804 dataref
->distance
= 0;
806 dataref
->always_accessed
807 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
808 gimple_bb (dataref
->stmt
));
809 dataref
->pos
= comp
->refs
.length ();
810 comp
->refs
.quick_push (dataref
);
813 for (i
= 0; i
< n
; i
++)
818 comp
->next
= comp_list
;
830 /* Returns true if the component COMP satisfies the conditions
831 described in 2) at the beginning of this file. LOOP is the current
835 suitable_component_p (struct loop
*loop
, struct component
*comp
)
839 basic_block ba
, bp
= loop
->header
;
840 bool ok
, has_write
= false;
842 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
844 ba
= gimple_bb (a
->stmt
);
846 if (!just_once_each_iteration_p (loop
, ba
))
849 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
852 if (DR_IS_WRITE (a
->ref
))
856 first
= comp
->refs
[0];
857 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
859 first
->offset
= double_int_zero
;
861 for (i
= 1; comp
->refs
.iterate (i
, &a
); i
++)
863 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
866 #ifdef ENABLE_CHECKING
868 enum ref_step_type a_step
;
869 ok
= suitable_reference_p (a
->ref
, &a_step
);
870 gcc_assert (ok
&& a_step
== comp
->comp_step
);
875 /* If there is a write inside the component, we must know whether the
876 step is nonzero or not -- we would not otherwise be able to recognize
877 whether the value accessed by reads comes from the OFFSET-th iteration
878 or the previous one. */
879 if (has_write
&& comp
->comp_step
== RS_ANY
)
885 /* Check the conditions on references inside each of components COMPS,
886 and remove the unsuitable components from the list. The new list
887 of components is returned. The conditions are described in 2) at
888 the beginning of this file. LOOP is the current loop. */
890 static struct component
*
891 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
893 struct component
**comp
, *act
;
895 for (comp
= &comps
; *comp
; )
898 if (suitable_component_p (loop
, act
))
906 FOR_EACH_VEC_ELT (act
->refs
, i
, ref
)
908 release_component (act
);
915 /* Compares two drefs A and B by their offset and position. Callback for
919 order_drefs (const void *a
, const void *b
)
921 const dref
*const da
= (const dref
*) a
;
922 const dref
*const db
= (const dref
*) b
;
923 int offcmp
= (*da
)->offset
.scmp ((*db
)->offset
);
928 return (*da
)->pos
- (*db
)->pos
;
931 /* Returns root of the CHAIN. */
934 get_chain_root (chain_p chain
)
936 return chain
->refs
[0];
939 /* Adds REF to the chain CHAIN. */
942 add_ref_to_chain (chain_p chain
, dref ref
)
944 dref root
= get_chain_root (chain
);
947 gcc_assert (root
->offset
.sle (ref
->offset
));
948 dist
= ref
->offset
- root
->offset
;
949 if (double_int::from_uhwi (MAX_DISTANCE
).ule (dist
))
954 gcc_assert (dist
.fits_uhwi ());
956 chain
->refs
.safe_push (ref
);
958 ref
->distance
= dist
.to_uhwi ();
960 if (ref
->distance
>= chain
->length
)
962 chain
->length
= ref
->distance
;
963 chain
->has_max_use_after
= false;
966 if (ref
->distance
== chain
->length
967 && ref
->pos
> root
->pos
)
968 chain
->has_max_use_after
= true;
970 chain
->all_always_accessed
&= ref
->always_accessed
;
973 /* Returns the chain for invariant component COMP. */
976 make_invariant_chain (struct component
*comp
)
978 chain_p chain
= XCNEW (struct chain
);
982 chain
->type
= CT_INVARIANT
;
984 chain
->all_always_accessed
= true;
986 FOR_EACH_VEC_ELT (comp
->refs
, i
, ref
)
988 chain
->refs
.safe_push (ref
);
989 chain
->all_always_accessed
&= ref
->always_accessed
;
995 /* Make a new chain rooted at REF. */
998 make_rooted_chain (dref ref
)
1000 chain_p chain
= XCNEW (struct chain
);
1002 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
1004 chain
->refs
.safe_push (ref
);
1005 chain
->all_always_accessed
= ref
->always_accessed
;
1012 /* Returns true if CHAIN is not trivial. */
1015 nontrivial_chain_p (chain_p chain
)
1017 return chain
!= NULL
&& chain
->refs
.length () > 1;
1020 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1024 name_for_ref (dref ref
)
1028 if (is_gimple_assign (ref
->stmt
))
1030 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1031 name
= gimple_assign_lhs (ref
->stmt
);
1033 name
= gimple_assign_rhs1 (ref
->stmt
);
1036 name
= PHI_RESULT (ref
->stmt
);
1038 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1041 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1042 iterations of the innermost enclosing loop). */
1045 valid_initializer_p (struct data_reference
*ref
,
1046 unsigned distance
, struct data_reference
*root
)
1048 aff_tree diff
, base
, step
;
1051 /* Both REF and ROOT must be accessing the same object. */
1052 if (!operand_equal_p (DR_BASE_ADDRESS (ref
), DR_BASE_ADDRESS (root
), 0))
1055 /* The initializer is defined outside of loop, hence its address must be
1056 invariant inside the loop. */
1057 gcc_assert (integer_zerop (DR_STEP (ref
)));
1059 /* If the address of the reference is invariant, initializer must access
1060 exactly the same location. */
1061 if (integer_zerop (DR_STEP (root
)))
1062 return (operand_equal_p (DR_OFFSET (ref
), DR_OFFSET (root
), 0)
1063 && operand_equal_p (DR_INIT (ref
), DR_INIT (root
), 0));
1065 /* Verify that this index of REF is equal to the root's index at
1066 -DISTANCE-th iteration. */
1067 aff_combination_dr_offset (root
, &diff
);
1068 aff_combination_dr_offset (ref
, &base
);
1069 aff_combination_scale (&base
, double_int_minus_one
);
1070 aff_combination_add (&diff
, &base
);
1072 tree_to_aff_combination_expand (DR_STEP (root
), TREE_TYPE (DR_STEP (root
)),
1073 &step
, &name_expansions
);
1074 if (!aff_combination_constant_multiple_p (&diff
, &step
, &off
))
1077 if (off
!= double_int::from_uhwi (distance
))
1083 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1084 initial value is correct (equal to initial value of REF shifted by one
1085 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1086 is the root of the current chain. */
1089 find_looparound_phi (struct loop
*loop
, dref ref
, dref root
)
1091 tree name
, init
, init_ref
;
1092 gimple phi
= NULL
, init_stmt
;
1093 edge latch
= loop_latch_edge (loop
);
1094 struct data_reference init_dr
;
1095 gimple_stmt_iterator psi
;
1097 if (is_gimple_assign (ref
->stmt
))
1099 if (DR_IS_READ (ref
->ref
))
1100 name
= gimple_assign_lhs (ref
->stmt
);
1102 name
= gimple_assign_rhs1 (ref
->stmt
);
1105 name
= PHI_RESULT (ref
->stmt
);
1109 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1111 phi
= gsi_stmt (psi
);
1112 if (PHI_ARG_DEF_FROM_EDGE (phi
, latch
) == name
)
1116 if (gsi_end_p (psi
))
1119 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1120 if (TREE_CODE (init
) != SSA_NAME
)
1122 init_stmt
= SSA_NAME_DEF_STMT (init
);
1123 if (gimple_code (init_stmt
) != GIMPLE_ASSIGN
)
1125 gcc_assert (gimple_assign_lhs (init_stmt
) == init
);
1127 init_ref
= gimple_assign_rhs1 (init_stmt
);
1128 if (!REFERENCE_CLASS_P (init_ref
)
1129 && !DECL_P (init_ref
))
1132 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1133 loop enclosing PHI). */
1134 memset (&init_dr
, 0, sizeof (struct data_reference
));
1135 DR_REF (&init_dr
) = init_ref
;
1136 DR_STMT (&init_dr
) = phi
;
1137 if (!dr_analyze_innermost (&init_dr
, loop
))
1140 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1146 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1149 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1151 dref nw
= XCNEW (struct dref_d
), aref
;
1155 nw
->distance
= ref
->distance
+ 1;
1156 nw
->always_accessed
= 1;
1158 FOR_EACH_VEC_ELT (chain
->refs
, i
, aref
)
1159 if (aref
->distance
>= nw
->distance
)
1161 chain
->refs
.safe_insert (i
, nw
);
1163 if (nw
->distance
> chain
->length
)
1165 chain
->length
= nw
->distance
;
1166 chain
->has_max_use_after
= false;
1170 /* For references in CHAIN that are copied around the LOOP (created previously
1171 by PRE, or by user), add the results of such copies to the chain. This
1172 enables us to remove the copies by unrolling, and may need less registers
1173 (also, it may allow us to combine chains together). */
1176 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1179 dref ref
, root
= get_chain_root (chain
);
1182 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
1184 phi
= find_looparound_phi (loop
, ref
, root
);
1188 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1189 insert_looparound_copy (chain
, ref
, phi
);
1193 /* Find roots of the values and determine distances in the component COMP.
1194 The references are redistributed into CHAINS. LOOP is the current
1198 determine_roots_comp (struct loop
*loop
,
1199 struct component
*comp
,
1200 vec
<chain_p
> *chains
)
1204 chain_p chain
= NULL
;
1205 double_int last_ofs
= double_int_zero
;
1207 /* Invariants are handled specially. */
1208 if (comp
->comp_step
== RS_INVARIANT
)
1210 chain
= make_invariant_chain (comp
);
1211 chains
->safe_push (chain
);
1215 comp
->refs
.qsort (order_drefs
);
1217 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
1219 if (!chain
|| DR_IS_WRITE (a
->ref
)
1220 || double_int::from_uhwi (MAX_DISTANCE
).ule (a
->offset
- last_ofs
))
1222 if (nontrivial_chain_p (chain
))
1224 add_looparound_copies (loop
, chain
);
1225 chains
->safe_push (chain
);
1228 release_chain (chain
);
1229 chain
= make_rooted_chain (a
);
1230 last_ofs
= a
->offset
;
1234 add_ref_to_chain (chain
, a
);
1237 if (nontrivial_chain_p (chain
))
1239 add_looparound_copies (loop
, chain
);
1240 chains
->safe_push (chain
);
1243 release_chain (chain
);
1246 /* Find roots of the values and determine distances in components COMPS, and
1247 separates the references to CHAINS. LOOP is the current loop. */
1250 determine_roots (struct loop
*loop
,
1251 struct component
*comps
, vec
<chain_p
> *chains
)
1253 struct component
*comp
;
1255 for (comp
= comps
; comp
; comp
= comp
->next
)
1256 determine_roots_comp (loop
, comp
, chains
);
1259 /* Replace the reference in statement STMT with temporary variable
1260 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1261 the reference in the statement. IN_LHS is true if the reference
1262 is in the lhs of STMT, false if it is in rhs. */
1265 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1269 gimple_stmt_iterator bsi
, psi
;
1271 if (gimple_code (stmt
) == GIMPLE_PHI
)
1273 gcc_assert (!in_lhs
&& !set
);
1275 val
= PHI_RESULT (stmt
);
1276 bsi
= gsi_after_labels (gimple_bb (stmt
));
1277 psi
= gsi_for_stmt (stmt
);
1278 remove_phi_node (&psi
, false);
1280 /* Turn the phi node into GIMPLE_ASSIGN. */
1281 new_stmt
= gimple_build_assign (val
, new_tree
);
1282 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1286 /* Since the reference is of gimple_reg type, it should only
1287 appear as lhs or rhs of modify statement. */
1288 gcc_assert (is_gimple_assign (stmt
));
1290 bsi
= gsi_for_stmt (stmt
);
1292 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1295 gcc_assert (!in_lhs
);
1296 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1297 stmt
= gsi_stmt (bsi
);
1304 /* We have statement
1308 If OLD is a memory reference, then VAL is gimple_val, and we transform
1314 Otherwise, we are replacing a combination chain,
1315 VAL is the expression that performs the combination, and OLD is an
1316 SSA name. In this case, we transform the assignment to
1323 val
= gimple_assign_lhs (stmt
);
1324 if (TREE_CODE (val
) != SSA_NAME
)
1326 val
= gimple_assign_rhs1 (stmt
);
1327 gcc_assert (gimple_assign_single_p (stmt
));
1328 if (TREE_CLOBBER_P (val
))
1329 val
= get_or_create_ssa_default_def (cfun
, SSA_NAME_VAR (new_tree
));
1331 gcc_assert (gimple_assign_copy_p (stmt
));
1343 val
= gimple_assign_lhs (stmt
);
1346 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1347 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1350 /* Returns a memory reference to DR in the ITER-th iteration of
1351 the loop it was analyzed in. Append init stmts to STMTS. */
1354 ref_at_iteration (data_reference_p dr
, int iter
, gimple_seq
*stmts
)
1356 tree off
= DR_OFFSET (dr
);
1357 tree coff
= DR_INIT (dr
);
1360 else if (TREE_CODE (DR_STEP (dr
)) == INTEGER_CST
)
1361 coff
= size_binop (PLUS_EXPR
, coff
,
1362 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1364 off
= size_binop (PLUS_EXPR
, off
,
1365 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1366 tree addr
= fold_build_pointer_plus (DR_BASE_ADDRESS (dr
), off
);
1367 addr
= force_gimple_operand_1 (addr
, stmts
, is_gimple_mem_ref_addr
,
1369 tree alias_ptr
= fold_convert (reference_alias_ptr_type (DR_REF (dr
)), coff
);
1370 /* While data-ref analysis punts on bit offsets it still handles
1371 bitfield accesses at byte boundaries. Cope with that. Note that
1372 we cannot simply re-apply the outer COMPONENT_REF because the
1373 byte-granular portion of it is already applied via DR_INIT and
1374 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1375 start at offset zero. */
1376 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
1377 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
1379 tree field
= TREE_OPERAND (DR_REF (dr
), 1);
1380 return build3 (BIT_FIELD_REF
, TREE_TYPE (DR_REF (dr
)),
1381 build2 (MEM_REF
, DECL_BIT_FIELD_TYPE (field
),
1383 DECL_SIZE (field
), bitsize_zero_node
);
1386 return fold_build2 (MEM_REF
, TREE_TYPE (DR_REF (dr
)), addr
, alias_ptr
);
1389 /* Get the initialization expression for the INDEX-th temporary variable
1393 get_init_expr (chain_p chain
, unsigned index
)
1395 if (chain
->type
== CT_COMBINATION
)
1397 tree e1
= get_init_expr (chain
->ch1
, index
);
1398 tree e2
= get_init_expr (chain
->ch2
, index
);
1400 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1403 return chain
->inits
[index
];
1406 /* Returns a new temporary variable used for the I-th variable carrying
1407 value of REF. The variable's uid is marked in TMP_VARS. */
1410 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1412 tree type
= TREE_TYPE (ref
);
1413 /* We never access the components of the temporary variable in predictive
1415 tree var
= create_tmp_reg (type
, get_lsm_tmp_name (ref
, i
));
1416 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1420 /* Creates the variables for CHAIN, as well as phi nodes for them and
1421 initialization on entry to LOOP. Uids of the newly created
1422 temporary variables are marked in TMP_VARS. */
1425 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1428 unsigned n
= chain
->length
;
1429 dref root
= get_chain_root (chain
);
1430 bool reuse_first
= !chain
->has_max_use_after
;
1431 tree ref
, init
, var
, next
;
1434 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1436 /* If N == 0, then all the references are within the single iteration. And
1437 since this is an nonempty chain, reuse_first cannot be true. */
1438 gcc_assert (n
> 0 || !reuse_first
);
1440 chain
->vars
.create (n
+ 1);
1442 if (chain
->type
== CT_COMBINATION
)
1443 ref
= gimple_assign_lhs (root
->stmt
);
1445 ref
= DR_REF (root
->ref
);
1447 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1449 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1450 chain
->vars
.quick_push (var
);
1453 chain
->vars
.quick_push (chain
->vars
[0]);
1455 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
1456 chain
->vars
[i
] = make_ssa_name (var
, NULL
);
1458 for (i
= 0; i
< n
; i
++)
1460 var
= chain
->vars
[i
];
1461 next
= chain
->vars
[i
+ 1];
1462 init
= get_init_expr (chain
, i
);
1464 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1466 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1468 phi
= create_phi_node (var
, loop
->header
);
1469 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1470 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1474 /* Create the variables and initialization statement for root of chain
1475 CHAIN. Uids of the newly created temporary variables are marked
1479 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1481 dref root
= get_chain_root (chain
);
1482 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1483 || chain
->type
== CT_COMBINATION
);
1485 initialize_root_vars (loop
, chain
, tmp_vars
);
1486 replace_ref_with (root
->stmt
,
1487 chain
->vars
[chain
->length
],
1491 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1492 initialization on entry to LOOP if necessary. The ssa name for the variable
1493 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1494 around the loop is created. Uid of the newly created temporary variable
1495 is marked in TMP_VARS. INITS is the list containing the (single)
1499 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1500 vec
<tree
> *vars
, vec
<tree
> inits
,
1504 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1507 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1509 /* Find the initializer for the variable, and check that it cannot
1513 vars
->create (written
? 2 : 1);
1514 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1515 vars
->quick_push (var
);
1517 vars
->quick_push ((*vars
)[0]);
1519 FOR_EACH_VEC_ELT (*vars
, i
, var
)
1520 (*vars
)[i
] = make_ssa_name (var
, NULL
);
1524 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1526 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1531 phi
= create_phi_node (var
, loop
->header
);
1532 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1533 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1537 gimple init_stmt
= gimple_build_assign (var
, init
);
1538 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1543 /* Execute load motion for references in chain CHAIN. Uids of the newly
1544 created temporary variables are marked in TMP_VARS. */
1547 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1549 auto_vec
<tree
> vars
;
1551 unsigned n_writes
= 0, ridx
, i
;
1554 gcc_assert (chain
->type
== CT_INVARIANT
);
1555 gcc_assert (!chain
->combined
);
1556 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1557 if (DR_IS_WRITE (a
->ref
))
1560 /* If there are no reads in the loop, there is nothing to do. */
1561 if (n_writes
== chain
->refs
.length ())
1564 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1565 &vars
, chain
->inits
, tmp_vars
);
1568 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1570 bool is_read
= DR_IS_READ (a
->ref
);
1572 if (DR_IS_WRITE (a
->ref
))
1578 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1585 replace_ref_with (a
->stmt
, vars
[ridx
],
1586 !is_read
, !is_read
);
1590 /* Returns the single statement in that NAME is used, excepting
1591 the looparound phi nodes contained in one of the chains. If there is no
1592 such statement, or more statements, NULL is returned. */
1595 single_nonlooparound_use (tree name
)
1598 imm_use_iterator it
;
1599 gimple stmt
, ret
= NULL
;
1601 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1603 stmt
= USE_STMT (use
);
1605 if (gimple_code (stmt
) == GIMPLE_PHI
)
1607 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1608 could not be processed anyway, so just fail for them. */
1609 if (bitmap_bit_p (looparound_phis
,
1610 SSA_NAME_VERSION (PHI_RESULT (stmt
))))
1615 else if (is_gimple_debug (stmt
))
1617 else if (ret
!= NULL
)
1626 /* Remove statement STMT, as well as the chain of assignments in that it is
1630 remove_stmt (gimple stmt
)
1634 gimple_stmt_iterator psi
;
1636 if (gimple_code (stmt
) == GIMPLE_PHI
)
1638 name
= PHI_RESULT (stmt
);
1639 next
= single_nonlooparound_use (name
);
1640 reset_debug_uses (stmt
);
1641 psi
= gsi_for_stmt (stmt
);
1642 remove_phi_node (&psi
, true);
1645 || !gimple_assign_ssa_name_copy_p (next
)
1646 || gimple_assign_rhs1 (next
) != name
)
1654 gimple_stmt_iterator bsi
;
1656 bsi
= gsi_for_stmt (stmt
);
1658 name
= gimple_assign_lhs (stmt
);
1659 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1661 next
= single_nonlooparound_use (name
);
1662 reset_debug_uses (stmt
);
1664 unlink_stmt_vdef (stmt
);
1665 gsi_remove (&bsi
, true);
1666 release_defs (stmt
);
1669 || !gimple_assign_ssa_name_copy_p (next
)
1670 || gimple_assign_rhs1 (next
) != name
)
1677 /* Perform the predictive commoning optimization for a chain CHAIN.
1678 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1681 execute_pred_commoning_chain (struct loop
*loop
, chain_p chain
,
1688 if (chain
->combined
)
1690 /* For combined chains, just remove the statements that are used to
1691 compute the values of the expression (except for the root one). */
1692 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1693 remove_stmt (a
->stmt
);
1697 /* For non-combined chains, set up the variables that hold its value,
1698 and replace the uses of the original references by these
1700 initialize_root (loop
, chain
, tmp_vars
);
1701 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1703 var
= chain
->vars
[chain
->length
- a
->distance
];
1704 replace_ref_with (a
->stmt
, var
, false, false);
1709 /* Determines the unroll factor necessary to remove as many temporary variable
1710 copies as possible. CHAINS is the list of chains that will be
1714 determine_unroll_factor (vec
<chain_p
> chains
)
1717 unsigned factor
= 1, af
, nfactor
, i
;
1718 unsigned max
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1720 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1722 if (chain
->type
== CT_INVARIANT
|| chain
->combined
)
1725 /* The best unroll factor for this chain is equal to the number of
1726 temporary variables that we create for it. */
1728 if (chain
->has_max_use_after
)
1731 nfactor
= factor
* af
/ gcd (factor
, af
);
1739 /* Perform the predictive commoning optimization for CHAINS.
1740 Uids of the newly created temporary variables are marked in TMP_VARS. */
1743 execute_pred_commoning (struct loop
*loop
, vec
<chain_p
> chains
,
1749 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1751 if (chain
->type
== CT_INVARIANT
)
1752 execute_load_motion (loop
, chain
, tmp_vars
);
1754 execute_pred_commoning_chain (loop
, chain
, tmp_vars
);
1757 update_ssa (TODO_update_ssa_only_virtuals
);
1760 /* For each reference in CHAINS, if its defining statement is
1761 phi node, record the ssa name that is defined by it. */
1764 replace_phis_by_defined_names (vec
<chain_p
> chains
)
1770 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1771 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1773 if (gimple_code (a
->stmt
) == GIMPLE_PHI
)
1775 a
->name_defined_by_phi
= PHI_RESULT (a
->stmt
);
1781 /* For each reference in CHAINS, if name_defined_by_phi is not
1782 NULL, use it to set the stmt field. */
1785 replace_names_by_phis (vec
<chain_p
> chains
)
1791 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1792 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1793 if (a
->stmt
== NULL
)
1795 a
->stmt
= SSA_NAME_DEF_STMT (a
->name_defined_by_phi
);
1796 gcc_assert (gimple_code (a
->stmt
) == GIMPLE_PHI
);
1797 a
->name_defined_by_phi
= NULL_TREE
;
1801 /* Wrapper over execute_pred_commoning, to pass it as a callback
1802 to tree_transform_and_unroll_loop. */
1806 vec
<chain_p
> chains
;
1811 execute_pred_commoning_cbck (struct loop
*loop
, void *data
)
1813 struct epcc_data
*const dta
= (struct epcc_data
*) data
;
1815 /* Restore phi nodes that were replaced by ssa names before
1816 tree_transform_and_unroll_loop (see detailed description in
1817 tree_predictive_commoning_loop). */
1818 replace_names_by_phis (dta
->chains
);
1819 execute_pred_commoning (loop
, dta
->chains
, dta
->tmp_vars
);
1822 /* Base NAME and all the names in the chain of phi nodes that use it
1823 on variable VAR. The phi nodes are recognized by being in the copies of
1824 the header of the LOOP. */
1827 base_names_in_chain_on (struct loop
*loop
, tree name
, tree var
)
1830 imm_use_iterator iter
;
1832 replace_ssa_name_symbol (name
, var
);
1837 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1839 if (gimple_code (stmt
) == GIMPLE_PHI
1840 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1843 BREAK_FROM_IMM_USE_STMT (iter
);
1849 name
= PHI_RESULT (phi
);
1850 replace_ssa_name_symbol (name
, var
);
1854 /* Given an unrolled LOOP after predictive commoning, remove the
1855 register copies arising from phi nodes by changing the base
1856 variables of SSA names. TMP_VARS is the set of the temporary variables
1857 for those we want to perform this. */
1860 eliminate_temp_copies (struct loop
*loop
, bitmap tmp_vars
)
1864 tree name
, use
, var
;
1865 gimple_stmt_iterator psi
;
1867 e
= loop_latch_edge (loop
);
1868 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1870 phi
= gsi_stmt (psi
);
1871 name
= PHI_RESULT (phi
);
1872 var
= SSA_NAME_VAR (name
);
1873 if (!var
|| !bitmap_bit_p (tmp_vars
, DECL_UID (var
)))
1875 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1876 gcc_assert (TREE_CODE (use
) == SSA_NAME
);
1878 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1879 stmt
= SSA_NAME_DEF_STMT (use
);
1880 while (gimple_code (stmt
) == GIMPLE_PHI
1881 /* In case we could not unroll the loop enough to eliminate
1882 all copies, we may reach the loop header before the defining
1883 statement (in that case, some register copies will be present
1884 in loop latch in the final code, corresponding to the newly
1885 created looparound phi nodes). */
1886 && gimple_bb (stmt
) != loop
->header
)
1888 gcc_assert (single_pred_p (gimple_bb (stmt
)));
1889 use
= PHI_ARG_DEF (stmt
, 0);
1890 stmt
= SSA_NAME_DEF_STMT (use
);
1893 base_names_in_chain_on (loop
, use
, var
);
1897 /* Returns true if CHAIN is suitable to be combined. */
1900 chain_can_be_combined_p (chain_p chain
)
1902 return (!chain
->combined
1903 && (chain
->type
== CT_LOAD
|| chain
->type
== CT_COMBINATION
));
1906 /* Returns the modify statement that uses NAME. Skips over assignment
1907 statements, NAME is replaced with the actual name used in the returned
1911 find_use_stmt (tree
*name
)
1916 /* Skip over assignments. */
1919 stmt
= single_nonlooparound_use (*name
);
1923 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1926 lhs
= gimple_assign_lhs (stmt
);
1927 if (TREE_CODE (lhs
) != SSA_NAME
)
1930 if (gimple_assign_copy_p (stmt
))
1932 rhs
= gimple_assign_rhs1 (stmt
);
1938 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1939 == GIMPLE_BINARY_RHS
)
1946 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1949 may_reassociate_p (tree type
, enum tree_code code
)
1951 if (FLOAT_TYPE_P (type
)
1952 && !flag_unsafe_math_optimizations
)
1955 return (commutative_tree_code (code
)
1956 && associative_tree_code (code
));
1959 /* If the operation used in STMT is associative and commutative, go through the
1960 tree of the same operations and returns its root. Distance to the root
1961 is stored in DISTANCE. */
1964 find_associative_operation_root (gimple stmt
, unsigned *distance
)
1968 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1969 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1972 if (!may_reassociate_p (type
, code
))
1977 lhs
= gimple_assign_lhs (stmt
);
1978 gcc_assert (TREE_CODE (lhs
) == SSA_NAME
);
1980 next
= find_use_stmt (&lhs
);
1982 || gimple_assign_rhs_code (next
) != code
)
1994 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
1995 is no such statement, returns NULL_TREE. In case the operation used on
1996 NAME1 and NAME2 is associative and commutative, returns the root of the
1997 tree formed by this operation instead of the statement that uses NAME1 or
2001 find_common_use_stmt (tree
*name1
, tree
*name2
)
2003 gimple stmt1
, stmt2
;
2005 stmt1
= find_use_stmt (name1
);
2009 stmt2
= find_use_stmt (name2
);
2016 stmt1
= find_associative_operation_root (stmt1
, NULL
);
2019 stmt2
= find_associative_operation_root (stmt2
, NULL
);
2023 return (stmt1
== stmt2
? stmt1
: NULL
);
2026 /* Checks whether R1 and R2 are combined together using CODE, with the result
2027 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2028 if it is true. If CODE is ERROR_MARK, set these values instead. */
2031 combinable_refs_p (dref r1
, dref r2
,
2032 enum tree_code
*code
, bool *swap
, tree
*rslt_type
)
2034 enum tree_code acode
;
2040 name1
= name_for_ref (r1
);
2041 name2
= name_for_ref (r2
);
2042 gcc_assert (name1
!= NULL_TREE
&& name2
!= NULL_TREE
);
2044 stmt
= find_common_use_stmt (&name1
, &name2
);
2047 /* A simple post-dominance check - make sure the combination
2048 is executed under the same condition as the references. */
2049 || (gimple_bb (stmt
) != gimple_bb (r1
->stmt
)
2050 && gimple_bb (stmt
) != gimple_bb (r2
->stmt
)))
2053 acode
= gimple_assign_rhs_code (stmt
);
2054 aswap
= (!commutative_tree_code (acode
)
2055 && gimple_assign_rhs1 (stmt
) != name1
);
2056 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2058 if (*code
== ERROR_MARK
)
2066 return (*code
== acode
2068 && *rslt_type
== atype
);
2071 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2072 an assignment of the remaining operand. */
2075 remove_name_from_operation (gimple stmt
, tree op
)
2078 gimple_stmt_iterator si
;
2080 gcc_assert (is_gimple_assign (stmt
));
2082 if (gimple_assign_rhs1 (stmt
) == op
)
2083 other_op
= gimple_assign_rhs2 (stmt
);
2085 other_op
= gimple_assign_rhs1 (stmt
);
2087 si
= gsi_for_stmt (stmt
);
2088 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2090 /* We should not have reallocated STMT. */
2091 gcc_assert (gsi_stmt (si
) == stmt
);
2096 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2097 are combined in a single statement, and returns this statement. */
2100 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2102 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2103 gimple new_stmt
, tmp_stmt
;
2104 tree new_name
, tmp_name
, var
, r1
, r2
;
2105 unsigned dist1
, dist2
;
2106 enum tree_code code
;
2107 tree type
= TREE_TYPE (name1
);
2108 gimple_stmt_iterator bsi
;
2110 stmt1
= find_use_stmt (&name1
);
2111 stmt2
= find_use_stmt (&name2
);
2112 root1
= find_associative_operation_root (stmt1
, &dist1
);
2113 root2
= find_associative_operation_root (stmt2
, &dist2
);
2114 code
= gimple_assign_rhs_code (stmt1
);
2116 gcc_assert (root1
&& root2
&& root1
== root2
2117 && code
== gimple_assign_rhs_code (stmt2
));
2119 /* Find the root of the nearest expression in that both NAME1 and NAME2
2126 while (dist1
> dist2
)
2128 s1
= find_use_stmt (&r1
);
2129 r1
= gimple_assign_lhs (s1
);
2132 while (dist2
> dist1
)
2134 s2
= find_use_stmt (&r2
);
2135 r2
= gimple_assign_lhs (s2
);
2141 s1
= find_use_stmt (&r1
);
2142 r1
= gimple_assign_lhs (s1
);
2143 s2
= find_use_stmt (&r2
);
2144 r2
= gimple_assign_lhs (s2
);
2147 /* Remove NAME1 and NAME2 from the statements in that they are used
2149 remove_name_from_operation (stmt1
, name1
);
2150 remove_name_from_operation (stmt2
, name2
);
2152 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2153 combine it with the rhs of S1. */
2154 var
= create_tmp_reg (type
, "predreastmp");
2155 new_name
= make_ssa_name (var
, NULL
);
2156 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2158 var
= create_tmp_reg (type
, "predreastmp");
2159 tmp_name
= make_ssa_name (var
, NULL
);
2161 /* Rhs of S1 may now be either a binary expression with operation
2162 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2163 so that name1 or name2 was removed from it). */
2164 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2166 gimple_assign_rhs1 (s1
),
2167 gimple_assign_rhs2 (s1
));
2169 bsi
= gsi_for_stmt (s1
);
2170 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2171 s1
= gsi_stmt (bsi
);
2174 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2175 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2180 /* Returns the statement that combines references R1 and R2. In case R1
2181 and R2 are not used in the same statement, but they are used with an
2182 associative and commutative operation in the same expression, reassociate
2183 the expression so that they are used in the same statement. */
2186 stmt_combining_refs (dref r1
, dref r2
)
2188 gimple stmt1
, stmt2
;
2189 tree name1
= name_for_ref (r1
);
2190 tree name2
= name_for_ref (r2
);
2192 stmt1
= find_use_stmt (&name1
);
2193 stmt2
= find_use_stmt (&name2
);
2197 return reassociate_to_the_same_stmt (name1
, name2
);
2200 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2201 description of the new chain is returned, otherwise we return NULL. */
2204 combine_chains (chain_p ch1
, chain_p ch2
)
2207 enum tree_code op
= ERROR_MARK
;
2212 tree rslt_type
= NULL_TREE
;
2216 if (ch1
->length
!= ch2
->length
)
2219 if (ch1
->refs
.length () != ch2
->refs
.length ())
2222 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2223 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2225 if (r1
->distance
!= r2
->distance
)
2228 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2239 new_chain
= XCNEW (struct chain
);
2240 new_chain
->type
= CT_COMBINATION
;
2242 new_chain
->ch1
= ch1
;
2243 new_chain
->ch2
= ch2
;
2244 new_chain
->rslt_type
= rslt_type
;
2245 new_chain
->length
= ch1
->length
;
2247 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2248 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2250 nw
= XCNEW (struct dref_d
);
2251 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2252 nw
->distance
= r1
->distance
;
2254 new_chain
->refs
.safe_push (nw
);
2257 new_chain
->has_max_use_after
= false;
2258 root_stmt
= get_chain_root (new_chain
)->stmt
;
2259 for (i
= 1; new_chain
->refs
.iterate (i
, &nw
); i
++)
2261 if (nw
->distance
== new_chain
->length
2262 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2264 new_chain
->has_max_use_after
= true;
2269 ch1
->combined
= true;
2270 ch2
->combined
= true;
2274 /* Try to combine the CHAINS. */
2277 try_combine_chains (vec
<chain_p
> *chains
)
2280 chain_p ch1
, ch2
, cch
;
2281 auto_vec
<chain_p
> worklist
;
2283 FOR_EACH_VEC_ELT (*chains
, i
, ch1
)
2284 if (chain_can_be_combined_p (ch1
))
2285 worklist
.safe_push (ch1
);
2287 while (!worklist
.is_empty ())
2289 ch1
= worklist
.pop ();
2290 if (!chain_can_be_combined_p (ch1
))
2293 FOR_EACH_VEC_ELT (*chains
, j
, ch2
)
2295 if (!chain_can_be_combined_p (ch2
))
2298 cch
= combine_chains (ch1
, ch2
);
2301 worklist
.safe_push (cch
);
2302 chains
->safe_push (cch
);
2309 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2310 impossible because one of these initializers may trap, true otherwise. */
2313 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2315 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2316 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2320 edge entry
= loop_preheader_edge (loop
);
2322 /* Find the initializers for the variables, and check that they cannot
2324 chain
->inits
.create (n
);
2325 for (i
= 0; i
< n
; i
++)
2326 chain
->inits
.quick_push (NULL_TREE
);
2328 /* If we have replaced some looparound phi nodes, use their initializers
2329 instead of creating our own. */
2330 FOR_EACH_VEC_ELT (chain
->refs
, i
, laref
)
2332 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2335 gcc_assert (laref
->distance
> 0);
2336 chain
->inits
[n
- laref
->distance
]
2337 = PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
);
2340 for (i
= 0; i
< n
; i
++)
2342 if (chain
->inits
[i
] != NULL_TREE
)
2345 init
= ref_at_iteration (dr
, (int) i
- n
, &stmts
);
2346 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2350 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2352 chain
->inits
[i
] = init
;
2358 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2359 be used because the initializers might trap. */
2362 prepare_initializers (struct loop
*loop
, vec
<chain_p
> chains
)
2367 for (i
= 0; i
< chains
.length (); )
2370 if (prepare_initializers_chain (loop
, chain
))
2374 release_chain (chain
);
2375 chains
.unordered_remove (i
);
2380 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2384 tree_predictive_commoning_loop (struct loop
*loop
)
2386 vec
<data_reference_p
> datarefs
;
2387 vec
<ddr_p
> dependences
;
2388 struct component
*components
;
2389 vec
<chain_p
> chains
= vNULL
;
2390 unsigned unroll_factor
;
2391 struct tree_niter_desc desc
;
2392 bool unroll
= false;
2396 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2397 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2399 /* Find the data references and split them into components according to their
2400 dependence relations. */
2401 stack_vec
<loop_p
, 3> loop_nest
;
2402 dependences
.create (10);
2403 datarefs
.create (10);
2404 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
2407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2408 fprintf (dump_file
, "Cannot analyze data dependencies\n");
2409 free_data_refs (datarefs
);
2410 free_dependence_relations (dependences
);
2414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2415 dump_data_dependence_relations (dump_file
, dependences
);
2417 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2418 loop_nest
.release ();
2419 free_dependence_relations (dependences
);
2422 free_data_refs (datarefs
);
2426 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2428 fprintf (dump_file
, "Initial state:\n\n");
2429 dump_components (dump_file
, components
);
2432 /* Find the suitable components and split them into chains. */
2433 components
= filter_suitable_components (loop
, components
);
2435 tmp_vars
= BITMAP_ALLOC (NULL
);
2436 looparound_phis
= BITMAP_ALLOC (NULL
);
2437 determine_roots (loop
, components
, &chains
);
2438 release_components (components
);
2440 if (!chains
.exists ())
2442 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2444 "Predictive commoning failed: no suitable chains\n");
2447 prepare_initializers (loop
, chains
);
2449 /* Try to combine the chains that are always worked with together. */
2450 try_combine_chains (&chains
);
2452 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2454 fprintf (dump_file
, "Before commoning:\n\n");
2455 dump_chains (dump_file
, chains
);
2458 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2459 that its number of iterations is divisible by the factor. */
2460 unroll_factor
= determine_unroll_factor (chains
);
2462 unroll
= (unroll_factor
> 1
2463 && can_unroll_loop_p (loop
, unroll_factor
, &desc
));
2464 exit
= single_dom_exit (loop
);
2466 /* Execute the predictive commoning transformations, and possibly unroll the
2470 struct epcc_data dta
;
2472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2473 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2475 dta
.chains
= chains
;
2476 dta
.tmp_vars
= tmp_vars
;
2478 update_ssa (TODO_update_ssa_only_virtuals
);
2480 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2481 execute_pred_commoning_cbck is called may cause phi nodes to be
2482 reallocated, which is a problem since CHAINS may point to these
2483 statements. To fix this, we store the ssa names defined by the
2484 phi nodes here instead of the phi nodes themselves, and restore
2485 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2486 replace_phis_by_defined_names (chains
);
2488 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2489 execute_pred_commoning_cbck
, &dta
);
2490 eliminate_temp_copies (loop
, tmp_vars
);
2494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2496 "Executing predictive commoning without unrolling.\n");
2497 execute_pred_commoning (loop
, chains
, tmp_vars
);
2501 release_chains (chains
);
2502 free_data_refs (datarefs
);
2503 BITMAP_FREE (tmp_vars
);
2504 BITMAP_FREE (looparound_phis
);
2506 free_affine_expand_cache (&name_expansions
);
2511 /* Runs predictive commoning. */
2514 tree_predictive_commoning (void)
2516 bool unrolled
= false;
2520 initialize_original_copy_tables ();
2521 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
2522 if (optimize_loop_for_speed_p (loop
))
2524 unrolled
|= tree_predictive_commoning_loop (loop
);
2530 ret
= TODO_cleanup_cfg
;
2532 free_original_copy_tables ();
2537 /* Predictive commoning Pass. */
2540 run_tree_predictive_commoning (void)
2545 return tree_predictive_commoning ();
2549 gate_tree_predictive_commoning (void)
2551 return flag_predictive_commoning
!= 0;
2556 const pass_data pass_data_predcom
=
2558 GIMPLE_PASS
, /* type */
2560 OPTGROUP_LOOP
, /* optinfo_flags */
2561 true, /* has_gate */
2562 true, /* has_execute */
2563 TV_PREDCOM
, /* tv_id */
2564 PROP_cfg
, /* properties_required */
2565 0, /* properties_provided */
2566 0, /* properties_destroyed */
2567 0, /* todo_flags_start */
2568 TODO_update_ssa_only_virtuals
, /* todo_flags_finish */
2571 class pass_predcom
: public gimple_opt_pass
2574 pass_predcom (gcc::context
*ctxt
)
2575 : gimple_opt_pass (pass_data_predcom
, ctxt
)
2578 /* opt_pass methods: */
2579 bool gate () { return gate_tree_predictive_commoning (); }
2580 unsigned int execute () { return run_tree_predictive_commoning (); }
2582 }; // class pass_predcom
2587 make_pass_predcom (gcc::context
*ctxt
)
2589 return new pass_predcom (ctxt
);