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"
195 #include "gimplify.h"
196 #include "gimple-iterator.h"
197 #include "gimplify-me.h"
198 #include "gimple-ssa.h"
199 #include "tree-phinodes.h"
200 #include "ssa-iterators.h"
201 #include "stringpool.h"
202 #include "tree-ssanames.h"
203 #include "tree-ssa-loop-ivopts.h"
204 #include "tree-ssa-loop-manip.h"
205 #include "tree-ssa-loop-niter.h"
206 #include "tree-ssa-loop.h"
207 #include "tree-into-ssa.h"
209 #include "tree-dfa.h"
210 #include "tree-ssa.h"
212 #include "tree-data-ref.h"
213 #include "tree-scalar-evolution.h"
214 #include "tree-chrec.h"
216 #include "gimple-pretty-print.h"
217 #include "tree-pass.h"
218 #include "tree-affine.h"
219 #include "tree-inline.h"
221 /* The maximum number of iterations between the considered memory
224 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
226 /* Data references (or phi nodes that carry data reference values across
229 typedef struct dref_d
231 /* The reference itself. */
232 struct data_reference
*ref
;
234 /* The statement in that the reference appears. */
237 /* In case that STMT is a phi node, this field is set to the SSA name
238 defined by it in replace_phis_by_defined_names (in order to avoid
239 pointing to phi node that got reallocated in the meantime). */
240 tree name_defined_by_phi
;
242 /* Distance of the reference from the root of the chain (in number of
243 iterations of the loop). */
246 /* Number of iterations offset from the first reference in the component. */
249 /* Number of the reference in a component, in dominance ordering. */
252 /* True if the memory reference is always accessed when the loop is
254 unsigned always_accessed
: 1;
258 /* Type of the chain of the references. */
262 /* The addresses of the references in the chain are constant. */
265 /* There are only loads in the chain. */
268 /* Root of the chain is store, the rest are loads. */
271 /* A combination of two chains. */
275 /* Chains of data references. */
279 /* Type of the chain. */
280 enum chain_type type
;
282 /* For combination chains, the operator and the two chains that are
283 combined, and the type of the result. */
286 struct chain
*ch1
, *ch2
;
288 /* The references in the chain. */
291 /* The maximum distance of the reference in the chain from the root. */
294 /* The variables used to copy the value throughout iterations. */
297 /* Initializers for the variables. */
300 /* True if there is a use of a variable with the maximal distance
301 that comes after the root in the loop. */
302 unsigned has_max_use_after
: 1;
304 /* True if all the memory references in the chain are always accessed. */
305 unsigned all_always_accessed
: 1;
307 /* True if this chain was combined together with some other chain. */
308 unsigned combined
: 1;
312 /* Describes the knowledge about the step of the memory references in
317 /* The step is zero. */
320 /* The step is nonzero. */
323 /* The step may or may not be nonzero. */
327 /* Components of the data dependence graph. */
331 /* The references in the component. */
334 /* What we know about the step of the references in the component. */
335 enum ref_step_type comp_step
;
337 /* Next component in the list. */
338 struct component
*next
;
341 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
343 static bitmap looparound_phis
;
345 /* Cache used by tree_to_aff_combination_expand. */
347 static struct pointer_map_t
*name_expansions
;
349 /* Dumps data reference REF to FILE. */
351 extern void dump_dref (FILE *, dref
);
353 dump_dref (FILE *file
, dref ref
)
358 print_generic_expr (file
, DR_REF (ref
->ref
), TDF_SLIM
);
359 fprintf (file
, " (id %u%s)\n", ref
->pos
,
360 DR_IS_READ (ref
->ref
) ? "" : ", write");
362 fprintf (file
, " offset ");
363 dump_double_int (file
, ref
->offset
, false);
364 fprintf (file
, "\n");
366 fprintf (file
, " distance %u\n", ref
->distance
);
370 if (gimple_code (ref
->stmt
) == GIMPLE_PHI
)
371 fprintf (file
, " looparound ref\n");
373 fprintf (file
, " combination ref\n");
374 fprintf (file
, " in statement ");
375 print_gimple_stmt (file
, ref
->stmt
, 0, TDF_SLIM
);
376 fprintf (file
, "\n");
377 fprintf (file
, " distance %u\n", ref
->distance
);
382 /* Dumps CHAIN to FILE. */
384 extern void dump_chain (FILE *, chain_p
);
386 dump_chain (FILE *file
, chain_p chain
)
389 const char *chain_type
;
396 chain_type
= "Load motion";
400 chain_type
= "Loads-only";
404 chain_type
= "Store-loads";
408 chain_type
= "Combination";
415 fprintf (file
, "%s chain %p%s\n", chain_type
, (void *) chain
,
416 chain
->combined
? " (combined)" : "");
417 if (chain
->type
!= CT_INVARIANT
)
418 fprintf (file
, " max distance %u%s\n", chain
->length
,
419 chain
->has_max_use_after
? "" : ", may reuse first");
421 if (chain
->type
== CT_COMBINATION
)
423 fprintf (file
, " equal to %p %s %p in type ",
424 (void *) chain
->ch1
, op_symbol_code (chain
->op
),
425 (void *) chain
->ch2
);
426 print_generic_expr (file
, chain
->rslt_type
, TDF_SLIM
);
427 fprintf (file
, "\n");
430 if (chain
->vars
.exists ())
432 fprintf (file
, " vars");
433 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
436 print_generic_expr (file
, var
, TDF_SLIM
);
438 fprintf (file
, "\n");
441 if (chain
->inits
.exists ())
443 fprintf (file
, " inits");
444 FOR_EACH_VEC_ELT (chain
->inits
, i
, var
)
447 print_generic_expr (file
, var
, TDF_SLIM
);
449 fprintf (file
, "\n");
452 fprintf (file
, " references:\n");
453 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
456 fprintf (file
, "\n");
459 /* Dumps CHAINS to FILE. */
461 extern void dump_chains (FILE *, vec
<chain_p
> );
463 dump_chains (FILE *file
, vec
<chain_p
> chains
)
468 FOR_EACH_VEC_ELT (chains
, i
, chain
)
469 dump_chain (file
, chain
);
472 /* Dumps COMP to FILE. */
474 extern void dump_component (FILE *, struct component
*);
476 dump_component (FILE *file
, struct component
*comp
)
481 fprintf (file
, "Component%s:\n",
482 comp
->comp_step
== RS_INVARIANT
? " (invariant)" : "");
483 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
485 fprintf (file
, "\n");
488 /* Dumps COMPS to FILE. */
490 extern void dump_components (FILE *, struct component
*);
492 dump_components (FILE *file
, struct component
*comps
)
494 struct component
*comp
;
496 for (comp
= comps
; comp
; comp
= comp
->next
)
497 dump_component (file
, comp
);
500 /* Frees a chain CHAIN. */
503 release_chain (chain_p chain
)
511 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
514 chain
->refs
.release ();
515 chain
->vars
.release ();
516 chain
->inits
.release ();
524 release_chains (vec
<chain_p
> chains
)
529 FOR_EACH_VEC_ELT (chains
, i
, chain
)
530 release_chain (chain
);
534 /* Frees a component COMP. */
537 release_component (struct component
*comp
)
539 comp
->refs
.release ();
543 /* Frees list of components COMPS. */
546 release_components (struct component
*comps
)
548 struct component
*act
, *next
;
550 for (act
= comps
; act
; act
= next
)
553 release_component (act
);
557 /* Finds a root of tree given by FATHERS containing A, and performs path
561 component_of (unsigned fathers
[], unsigned a
)
565 for (root
= a
; root
!= fathers
[root
]; root
= fathers
[root
])
568 for (; a
!= root
; a
= n
)
577 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
578 components, A and B are components to merge. */
581 merge_comps (unsigned fathers
[], unsigned sizes
[], unsigned a
, unsigned b
)
583 unsigned ca
= component_of (fathers
, a
);
584 unsigned cb
= component_of (fathers
, b
);
589 if (sizes
[ca
] < sizes
[cb
])
591 sizes
[cb
] += sizes
[ca
];
596 sizes
[ca
] += sizes
[cb
];
601 /* Returns true if A is a reference that is suitable for predictive commoning
602 in the innermost loop that contains it. REF_STEP is set according to the
603 step of the reference A. */
606 suitable_reference_p (struct data_reference
*a
, enum ref_step_type
*ref_step
)
608 tree ref
= DR_REF (a
), step
= DR_STEP (a
);
611 || TREE_THIS_VOLATILE (ref
)
612 || !is_gimple_reg_type (TREE_TYPE (ref
))
613 || tree_could_throw_p (ref
))
616 if (integer_zerop (step
))
617 *ref_step
= RS_INVARIANT
;
618 else if (integer_nonzerop (step
))
619 *ref_step
= RS_NONZERO
;
626 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
629 aff_combination_dr_offset (struct data_reference
*dr
, aff_tree
*offset
)
631 tree type
= TREE_TYPE (DR_OFFSET (dr
));
634 tree_to_aff_combination_expand (DR_OFFSET (dr
), type
, offset
,
636 aff_combination_const (&delta
, type
, tree_to_double_int (DR_INIT (dr
)));
637 aff_combination_add (offset
, &delta
);
640 /* Determines number of iterations of the innermost enclosing loop before B
641 refers to exactly the same location as A and stores it to OFF. If A and
642 B do not have the same step, they never meet, or anything else fails,
643 returns false, otherwise returns true. Both A and B are assumed to
644 satisfy suitable_reference_p. */
647 determine_offset (struct data_reference
*a
, struct data_reference
*b
,
650 aff_tree diff
, baseb
, step
;
653 /* Check that both the references access the location in the same type. */
654 typea
= TREE_TYPE (DR_REF (a
));
655 typeb
= TREE_TYPE (DR_REF (b
));
656 if (!useless_type_conversion_p (typeb
, typea
))
659 /* Check whether the base address and the step of both references is the
661 if (!operand_equal_p (DR_STEP (a
), DR_STEP (b
), 0)
662 || !operand_equal_p (DR_BASE_ADDRESS (a
), DR_BASE_ADDRESS (b
), 0))
665 if (integer_zerop (DR_STEP (a
)))
667 /* If the references have loop invariant address, check that they access
668 exactly the same location. */
669 *off
= double_int_zero
;
670 return (operand_equal_p (DR_OFFSET (a
), DR_OFFSET (b
), 0)
671 && operand_equal_p (DR_INIT (a
), DR_INIT (b
), 0));
674 /* Compare the offsets of the addresses, and check whether the difference
675 is a multiple of step. */
676 aff_combination_dr_offset (a
, &diff
);
677 aff_combination_dr_offset (b
, &baseb
);
678 aff_combination_scale (&baseb
, double_int_minus_one
);
679 aff_combination_add (&diff
, &baseb
);
681 tree_to_aff_combination_expand (DR_STEP (a
), TREE_TYPE (DR_STEP (a
)),
682 &step
, &name_expansions
);
683 return aff_combination_constant_multiple_p (&diff
, &step
, off
);
686 /* Returns the last basic block in LOOP for that we are sure that
687 it is executed whenever the loop is entered. */
690 last_always_executed_block (struct loop
*loop
)
693 vec
<edge
> exits
= get_loop_exit_edges (loop
);
695 basic_block last
= loop
->latch
;
697 FOR_EACH_VEC_ELT (exits
, i
, ex
)
698 last
= nearest_common_dominator (CDI_DOMINATORS
, last
, ex
->src
);
704 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
706 static struct component
*
707 split_data_refs_to_components (struct loop
*loop
,
708 vec
<data_reference_p
> datarefs
,
711 unsigned i
, n
= datarefs
.length ();
712 unsigned ca
, ia
, ib
, bad
;
713 unsigned *comp_father
= XNEWVEC (unsigned, n
+ 1);
714 unsigned *comp_size
= XNEWVEC (unsigned, n
+ 1);
715 struct component
**comps
;
716 struct data_reference
*dr
, *dra
, *drb
;
717 struct data_dependence_relation
*ddr
;
718 struct component
*comp_list
= NULL
, *comp
;
720 basic_block last_always_executed
= last_always_executed_block (loop
);
722 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
726 /* A fake reference for call or asm_expr that may clobber memory;
730 dr
->aux
= (void *) (size_t) i
;
735 /* A component reserved for the "bad" data references. */
739 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
741 enum ref_step_type dummy
;
743 if (!suitable_reference_p (dr
, &dummy
))
745 ia
= (unsigned) (size_t) dr
->aux
;
746 merge_comps (comp_father
, comp_size
, n
, ia
);
750 FOR_EACH_VEC_ELT (depends
, i
, ddr
)
752 double_int dummy_off
;
754 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
759 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
760 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
764 bad
= component_of (comp_father
, n
);
766 /* If both A and B are reads, we may ignore unsuitable dependences. */
767 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
768 && (ia
== bad
|| ib
== bad
769 || !determine_offset (dra
, drb
, &dummy_off
)))
772 merge_comps (comp_father
, comp_size
, ia
, ib
);
775 comps
= XCNEWVEC (struct component
*, n
);
776 bad
= component_of (comp_father
, n
);
777 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
779 ia
= (unsigned) (size_t) dr
->aux
;
780 ca
= component_of (comp_father
, ia
);
787 comp
= XCNEW (struct component
);
788 comp
->refs
.create (comp_size
[ca
]);
792 dataref
= XCNEW (struct dref_d
);
794 dataref
->stmt
= DR_STMT (dr
);
795 dataref
->offset
= double_int_zero
;
796 dataref
->distance
= 0;
798 dataref
->always_accessed
799 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
800 gimple_bb (dataref
->stmt
));
801 dataref
->pos
= comp
->refs
.length ();
802 comp
->refs
.quick_push (dataref
);
805 for (i
= 0; i
< n
; i
++)
810 comp
->next
= comp_list
;
822 /* Returns true if the component COMP satisfies the conditions
823 described in 2) at the beginning of this file. LOOP is the current
827 suitable_component_p (struct loop
*loop
, struct component
*comp
)
831 basic_block ba
, bp
= loop
->header
;
832 bool ok
, has_write
= false;
834 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
836 ba
= gimple_bb (a
->stmt
);
838 if (!just_once_each_iteration_p (loop
, ba
))
841 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
844 if (DR_IS_WRITE (a
->ref
))
848 first
= comp
->refs
[0];
849 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
851 first
->offset
= double_int_zero
;
853 for (i
= 1; comp
->refs
.iterate (i
, &a
); i
++)
855 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
858 #ifdef ENABLE_CHECKING
860 enum ref_step_type a_step
;
861 ok
= suitable_reference_p (a
->ref
, &a_step
);
862 gcc_assert (ok
&& a_step
== comp
->comp_step
);
867 /* If there is a write inside the component, we must know whether the
868 step is nonzero or not -- we would not otherwise be able to recognize
869 whether the value accessed by reads comes from the OFFSET-th iteration
870 or the previous one. */
871 if (has_write
&& comp
->comp_step
== RS_ANY
)
877 /* Check the conditions on references inside each of components COMPS,
878 and remove the unsuitable components from the list. The new list
879 of components is returned. The conditions are described in 2) at
880 the beginning of this file. LOOP is the current loop. */
882 static struct component
*
883 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
885 struct component
**comp
, *act
;
887 for (comp
= &comps
; *comp
; )
890 if (suitable_component_p (loop
, act
))
898 FOR_EACH_VEC_ELT (act
->refs
, i
, ref
)
900 release_component (act
);
907 /* Compares two drefs A and B by their offset and position. Callback for
911 order_drefs (const void *a
, const void *b
)
913 const dref
*const da
= (const dref
*) a
;
914 const dref
*const db
= (const dref
*) b
;
915 int offcmp
= (*da
)->offset
.scmp ((*db
)->offset
);
920 return (*da
)->pos
- (*db
)->pos
;
923 /* Returns root of the CHAIN. */
926 get_chain_root (chain_p chain
)
928 return chain
->refs
[0];
931 /* Adds REF to the chain CHAIN. */
934 add_ref_to_chain (chain_p chain
, dref ref
)
936 dref root
= get_chain_root (chain
);
939 gcc_assert (root
->offset
.sle (ref
->offset
));
940 dist
= ref
->offset
- root
->offset
;
941 if (double_int::from_uhwi (MAX_DISTANCE
).ule (dist
))
946 gcc_assert (dist
.fits_uhwi ());
948 chain
->refs
.safe_push (ref
);
950 ref
->distance
= dist
.to_uhwi ();
952 if (ref
->distance
>= chain
->length
)
954 chain
->length
= ref
->distance
;
955 chain
->has_max_use_after
= false;
958 if (ref
->distance
== chain
->length
959 && ref
->pos
> root
->pos
)
960 chain
->has_max_use_after
= true;
962 chain
->all_always_accessed
&= ref
->always_accessed
;
965 /* Returns the chain for invariant component COMP. */
968 make_invariant_chain (struct component
*comp
)
970 chain_p chain
= XCNEW (struct chain
);
974 chain
->type
= CT_INVARIANT
;
976 chain
->all_always_accessed
= true;
978 FOR_EACH_VEC_ELT (comp
->refs
, i
, ref
)
980 chain
->refs
.safe_push (ref
);
981 chain
->all_always_accessed
&= ref
->always_accessed
;
987 /* Make a new chain rooted at REF. */
990 make_rooted_chain (dref ref
)
992 chain_p chain
= XCNEW (struct chain
);
994 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
996 chain
->refs
.safe_push (ref
);
997 chain
->all_always_accessed
= ref
->always_accessed
;
1004 /* Returns true if CHAIN is not trivial. */
1007 nontrivial_chain_p (chain_p chain
)
1009 return chain
!= NULL
&& chain
->refs
.length () > 1;
1012 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1016 name_for_ref (dref ref
)
1020 if (is_gimple_assign (ref
->stmt
))
1022 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1023 name
= gimple_assign_lhs (ref
->stmt
);
1025 name
= gimple_assign_rhs1 (ref
->stmt
);
1028 name
= PHI_RESULT (ref
->stmt
);
1030 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1033 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1034 iterations of the innermost enclosing loop). */
1037 valid_initializer_p (struct data_reference
*ref
,
1038 unsigned distance
, struct data_reference
*root
)
1040 aff_tree diff
, base
, step
;
1043 /* Both REF and ROOT must be accessing the same object. */
1044 if (!operand_equal_p (DR_BASE_ADDRESS (ref
), DR_BASE_ADDRESS (root
), 0))
1047 /* The initializer is defined outside of loop, hence its address must be
1048 invariant inside the loop. */
1049 gcc_assert (integer_zerop (DR_STEP (ref
)));
1051 /* If the address of the reference is invariant, initializer must access
1052 exactly the same location. */
1053 if (integer_zerop (DR_STEP (root
)))
1054 return (operand_equal_p (DR_OFFSET (ref
), DR_OFFSET (root
), 0)
1055 && operand_equal_p (DR_INIT (ref
), DR_INIT (root
), 0));
1057 /* Verify that this index of REF is equal to the root's index at
1058 -DISTANCE-th iteration. */
1059 aff_combination_dr_offset (root
, &diff
);
1060 aff_combination_dr_offset (ref
, &base
);
1061 aff_combination_scale (&base
, double_int_minus_one
);
1062 aff_combination_add (&diff
, &base
);
1064 tree_to_aff_combination_expand (DR_STEP (root
), TREE_TYPE (DR_STEP (root
)),
1065 &step
, &name_expansions
);
1066 if (!aff_combination_constant_multiple_p (&diff
, &step
, &off
))
1069 if (off
!= double_int::from_uhwi (distance
))
1075 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1076 initial value is correct (equal to initial value of REF shifted by one
1077 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1078 is the root of the current chain. */
1081 find_looparound_phi (struct loop
*loop
, dref ref
, dref root
)
1083 tree name
, init
, init_ref
;
1084 gimple phi
= NULL
, init_stmt
;
1085 edge latch
= loop_latch_edge (loop
);
1086 struct data_reference init_dr
;
1087 gimple_stmt_iterator psi
;
1089 if (is_gimple_assign (ref
->stmt
))
1091 if (DR_IS_READ (ref
->ref
))
1092 name
= gimple_assign_lhs (ref
->stmt
);
1094 name
= gimple_assign_rhs1 (ref
->stmt
);
1097 name
= PHI_RESULT (ref
->stmt
);
1101 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1103 phi
= gsi_stmt (psi
);
1104 if (PHI_ARG_DEF_FROM_EDGE (phi
, latch
) == name
)
1108 if (gsi_end_p (psi
))
1111 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1112 if (TREE_CODE (init
) != SSA_NAME
)
1114 init_stmt
= SSA_NAME_DEF_STMT (init
);
1115 if (gimple_code (init_stmt
) != GIMPLE_ASSIGN
)
1117 gcc_assert (gimple_assign_lhs (init_stmt
) == init
);
1119 init_ref
= gimple_assign_rhs1 (init_stmt
);
1120 if (!REFERENCE_CLASS_P (init_ref
)
1121 && !DECL_P (init_ref
))
1124 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1125 loop enclosing PHI). */
1126 memset (&init_dr
, 0, sizeof (struct data_reference
));
1127 DR_REF (&init_dr
) = init_ref
;
1128 DR_STMT (&init_dr
) = phi
;
1129 if (!dr_analyze_innermost (&init_dr
, loop
))
1132 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1138 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1141 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1143 dref nw
= XCNEW (struct dref_d
), aref
;
1147 nw
->distance
= ref
->distance
+ 1;
1148 nw
->always_accessed
= 1;
1150 FOR_EACH_VEC_ELT (chain
->refs
, i
, aref
)
1151 if (aref
->distance
>= nw
->distance
)
1153 chain
->refs
.safe_insert (i
, nw
);
1155 if (nw
->distance
> chain
->length
)
1157 chain
->length
= nw
->distance
;
1158 chain
->has_max_use_after
= false;
1162 /* For references in CHAIN that are copied around the LOOP (created previously
1163 by PRE, or by user), add the results of such copies to the chain. This
1164 enables us to remove the copies by unrolling, and may need less registers
1165 (also, it may allow us to combine chains together). */
1168 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1171 dref ref
, root
= get_chain_root (chain
);
1174 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
1176 phi
= find_looparound_phi (loop
, ref
, root
);
1180 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1181 insert_looparound_copy (chain
, ref
, phi
);
1185 /* Find roots of the values and determine distances in the component COMP.
1186 The references are redistributed into CHAINS. LOOP is the current
1190 determine_roots_comp (struct loop
*loop
,
1191 struct component
*comp
,
1192 vec
<chain_p
> *chains
)
1196 chain_p chain
= NULL
;
1197 double_int last_ofs
= double_int_zero
;
1199 /* Invariants are handled specially. */
1200 if (comp
->comp_step
== RS_INVARIANT
)
1202 chain
= make_invariant_chain (comp
);
1203 chains
->safe_push (chain
);
1207 comp
->refs
.qsort (order_drefs
);
1209 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
1211 if (!chain
|| DR_IS_WRITE (a
->ref
)
1212 || double_int::from_uhwi (MAX_DISTANCE
).ule (a
->offset
- last_ofs
))
1214 if (nontrivial_chain_p (chain
))
1216 add_looparound_copies (loop
, chain
);
1217 chains
->safe_push (chain
);
1220 release_chain (chain
);
1221 chain
= make_rooted_chain (a
);
1222 last_ofs
= a
->offset
;
1226 add_ref_to_chain (chain
, a
);
1229 if (nontrivial_chain_p (chain
))
1231 add_looparound_copies (loop
, chain
);
1232 chains
->safe_push (chain
);
1235 release_chain (chain
);
1238 /* Find roots of the values and determine distances in components COMPS, and
1239 separates the references to CHAINS. LOOP is the current loop. */
1242 determine_roots (struct loop
*loop
,
1243 struct component
*comps
, vec
<chain_p
> *chains
)
1245 struct component
*comp
;
1247 for (comp
= comps
; comp
; comp
= comp
->next
)
1248 determine_roots_comp (loop
, comp
, chains
);
1251 /* Replace the reference in statement STMT with temporary variable
1252 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1253 the reference in the statement. IN_LHS is true if the reference
1254 is in the lhs of STMT, false if it is in rhs. */
1257 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1261 gimple_stmt_iterator bsi
, psi
;
1263 if (gimple_code (stmt
) == GIMPLE_PHI
)
1265 gcc_assert (!in_lhs
&& !set
);
1267 val
= PHI_RESULT (stmt
);
1268 bsi
= gsi_after_labels (gimple_bb (stmt
));
1269 psi
= gsi_for_stmt (stmt
);
1270 remove_phi_node (&psi
, false);
1272 /* Turn the phi node into GIMPLE_ASSIGN. */
1273 new_stmt
= gimple_build_assign (val
, new_tree
);
1274 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1278 /* Since the reference is of gimple_reg type, it should only
1279 appear as lhs or rhs of modify statement. */
1280 gcc_assert (is_gimple_assign (stmt
));
1282 bsi
= gsi_for_stmt (stmt
);
1284 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1287 gcc_assert (!in_lhs
);
1288 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1289 stmt
= gsi_stmt (bsi
);
1296 /* We have statement
1300 If OLD is a memory reference, then VAL is gimple_val, and we transform
1306 Otherwise, we are replacing a combination chain,
1307 VAL is the expression that performs the combination, and OLD is an
1308 SSA name. In this case, we transform the assignment to
1315 val
= gimple_assign_lhs (stmt
);
1316 if (TREE_CODE (val
) != SSA_NAME
)
1318 val
= gimple_assign_rhs1 (stmt
);
1319 gcc_assert (gimple_assign_single_p (stmt
));
1320 if (TREE_CLOBBER_P (val
))
1321 val
= get_or_create_ssa_default_def (cfun
, SSA_NAME_VAR (new_tree
));
1323 gcc_assert (gimple_assign_copy_p (stmt
));
1335 val
= gimple_assign_lhs (stmt
);
1338 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1339 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1342 /* Returns a memory reference to DR in the ITER-th iteration of
1343 the loop it was analyzed in. Append init stmts to STMTS. */
1346 ref_at_iteration (data_reference_p dr
, int iter
, gimple_seq
*stmts
)
1348 tree off
= DR_OFFSET (dr
);
1349 tree coff
= DR_INIT (dr
);
1352 else if (TREE_CODE (DR_STEP (dr
)) == INTEGER_CST
)
1353 coff
= size_binop (PLUS_EXPR
, coff
,
1354 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1356 off
= size_binop (PLUS_EXPR
, off
,
1357 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1358 tree addr
= fold_build_pointer_plus (DR_BASE_ADDRESS (dr
), off
);
1359 addr
= force_gimple_operand_1 (addr
, stmts
, is_gimple_mem_ref_addr
,
1361 tree alias_ptr
= fold_convert (reference_alias_ptr_type (DR_REF (dr
)), coff
);
1362 /* While data-ref analysis punts on bit offsets it still handles
1363 bitfield accesses at byte boundaries. Cope with that. Note that
1364 we cannot simply re-apply the outer COMPONENT_REF because the
1365 byte-granular portion of it is already applied via DR_INIT and
1366 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1367 start at offset zero. */
1368 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
1369 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
1371 tree field
= TREE_OPERAND (DR_REF (dr
), 1);
1372 return build3 (BIT_FIELD_REF
, TREE_TYPE (DR_REF (dr
)),
1373 build2 (MEM_REF
, DECL_BIT_FIELD_TYPE (field
),
1375 DECL_SIZE (field
), bitsize_zero_node
);
1378 return fold_build2 (MEM_REF
, TREE_TYPE (DR_REF (dr
)), addr
, alias_ptr
);
1381 /* Get the initialization expression for the INDEX-th temporary variable
1385 get_init_expr (chain_p chain
, unsigned index
)
1387 if (chain
->type
== CT_COMBINATION
)
1389 tree e1
= get_init_expr (chain
->ch1
, index
);
1390 tree e2
= get_init_expr (chain
->ch2
, index
);
1392 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1395 return chain
->inits
[index
];
1398 /* Returns a new temporary variable used for the I-th variable carrying
1399 value of REF. The variable's uid is marked in TMP_VARS. */
1402 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1404 tree type
= TREE_TYPE (ref
);
1405 /* We never access the components of the temporary variable in predictive
1407 tree var
= create_tmp_reg (type
, get_lsm_tmp_name (ref
, i
));
1408 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1412 /* Creates the variables for CHAIN, as well as phi nodes for them and
1413 initialization on entry to LOOP. Uids of the newly created
1414 temporary variables are marked in TMP_VARS. */
1417 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1420 unsigned n
= chain
->length
;
1421 dref root
= get_chain_root (chain
);
1422 bool reuse_first
= !chain
->has_max_use_after
;
1423 tree ref
, init
, var
, next
;
1426 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1428 /* If N == 0, then all the references are within the single iteration. And
1429 since this is an nonempty chain, reuse_first cannot be true. */
1430 gcc_assert (n
> 0 || !reuse_first
);
1432 chain
->vars
.create (n
+ 1);
1434 if (chain
->type
== CT_COMBINATION
)
1435 ref
= gimple_assign_lhs (root
->stmt
);
1437 ref
= DR_REF (root
->ref
);
1439 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1441 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1442 chain
->vars
.quick_push (var
);
1445 chain
->vars
.quick_push (chain
->vars
[0]);
1447 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
1448 chain
->vars
[i
] = make_ssa_name (var
, NULL
);
1450 for (i
= 0; i
< n
; i
++)
1452 var
= chain
->vars
[i
];
1453 next
= chain
->vars
[i
+ 1];
1454 init
= get_init_expr (chain
, i
);
1456 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1458 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1460 phi
= create_phi_node (var
, loop
->header
);
1461 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1462 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1466 /* Create the variables and initialization statement for root of chain
1467 CHAIN. Uids of the newly created temporary variables are marked
1471 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1473 dref root
= get_chain_root (chain
);
1474 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1475 || chain
->type
== CT_COMBINATION
);
1477 initialize_root_vars (loop
, chain
, tmp_vars
);
1478 replace_ref_with (root
->stmt
,
1479 chain
->vars
[chain
->length
],
1483 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1484 initialization on entry to LOOP if necessary. The ssa name for the variable
1485 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1486 around the loop is created. Uid of the newly created temporary variable
1487 is marked in TMP_VARS. INITS is the list containing the (single)
1491 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1492 vec
<tree
> *vars
, vec
<tree
> inits
,
1496 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1499 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1501 /* Find the initializer for the variable, and check that it cannot
1505 vars
->create (written
? 2 : 1);
1506 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1507 vars
->quick_push (var
);
1509 vars
->quick_push ((*vars
)[0]);
1511 FOR_EACH_VEC_ELT (*vars
, i
, var
)
1512 (*vars
)[i
] = make_ssa_name (var
, NULL
);
1516 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1518 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1523 phi
= create_phi_node (var
, loop
->header
);
1524 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1525 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1529 gimple init_stmt
= gimple_build_assign (var
, init
);
1530 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1535 /* Execute load motion for references in chain CHAIN. Uids of the newly
1536 created temporary variables are marked in TMP_VARS. */
1539 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1541 auto_vec
<tree
> vars
;
1543 unsigned n_writes
= 0, ridx
, i
;
1546 gcc_assert (chain
->type
== CT_INVARIANT
);
1547 gcc_assert (!chain
->combined
);
1548 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1549 if (DR_IS_WRITE (a
->ref
))
1552 /* If there are no reads in the loop, there is nothing to do. */
1553 if (n_writes
== chain
->refs
.length ())
1556 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1557 &vars
, chain
->inits
, tmp_vars
);
1560 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1562 bool is_read
= DR_IS_READ (a
->ref
);
1564 if (DR_IS_WRITE (a
->ref
))
1570 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1577 replace_ref_with (a
->stmt
, vars
[ridx
],
1578 !is_read
, !is_read
);
1582 /* Returns the single statement in that NAME is used, excepting
1583 the looparound phi nodes contained in one of the chains. If there is no
1584 such statement, or more statements, NULL is returned. */
1587 single_nonlooparound_use (tree name
)
1590 imm_use_iterator it
;
1591 gimple stmt
, ret
= NULL
;
1593 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1595 stmt
= USE_STMT (use
);
1597 if (gimple_code (stmt
) == GIMPLE_PHI
)
1599 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1600 could not be processed anyway, so just fail for them. */
1601 if (bitmap_bit_p (looparound_phis
,
1602 SSA_NAME_VERSION (PHI_RESULT (stmt
))))
1607 else if (is_gimple_debug (stmt
))
1609 else if (ret
!= NULL
)
1618 /* Remove statement STMT, as well as the chain of assignments in that it is
1622 remove_stmt (gimple stmt
)
1626 gimple_stmt_iterator psi
;
1628 if (gimple_code (stmt
) == GIMPLE_PHI
)
1630 name
= PHI_RESULT (stmt
);
1631 next
= single_nonlooparound_use (name
);
1632 reset_debug_uses (stmt
);
1633 psi
= gsi_for_stmt (stmt
);
1634 remove_phi_node (&psi
, true);
1637 || !gimple_assign_ssa_name_copy_p (next
)
1638 || gimple_assign_rhs1 (next
) != name
)
1646 gimple_stmt_iterator bsi
;
1648 bsi
= gsi_for_stmt (stmt
);
1650 name
= gimple_assign_lhs (stmt
);
1651 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1653 next
= single_nonlooparound_use (name
);
1654 reset_debug_uses (stmt
);
1656 unlink_stmt_vdef (stmt
);
1657 gsi_remove (&bsi
, true);
1658 release_defs (stmt
);
1661 || !gimple_assign_ssa_name_copy_p (next
)
1662 || gimple_assign_rhs1 (next
) != name
)
1669 /* Perform the predictive commoning optimization for a chain CHAIN.
1670 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1673 execute_pred_commoning_chain (struct loop
*loop
, chain_p chain
,
1680 if (chain
->combined
)
1682 /* For combined chains, just remove the statements that are used to
1683 compute the values of the expression (except for the root one). */
1684 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1685 remove_stmt (a
->stmt
);
1689 /* For non-combined chains, set up the variables that hold its value,
1690 and replace the uses of the original references by these
1692 initialize_root (loop
, chain
, tmp_vars
);
1693 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1695 var
= chain
->vars
[chain
->length
- a
->distance
];
1696 replace_ref_with (a
->stmt
, var
, false, false);
1701 /* Determines the unroll factor necessary to remove as many temporary variable
1702 copies as possible. CHAINS is the list of chains that will be
1706 determine_unroll_factor (vec
<chain_p
> chains
)
1709 unsigned factor
= 1, af
, nfactor
, i
;
1710 unsigned max
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1712 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1714 if (chain
->type
== CT_INVARIANT
|| chain
->combined
)
1717 /* The best unroll factor for this chain is equal to the number of
1718 temporary variables that we create for it. */
1720 if (chain
->has_max_use_after
)
1723 nfactor
= factor
* af
/ gcd (factor
, af
);
1731 /* Perform the predictive commoning optimization for CHAINS.
1732 Uids of the newly created temporary variables are marked in TMP_VARS. */
1735 execute_pred_commoning (struct loop
*loop
, vec
<chain_p
> chains
,
1741 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1743 if (chain
->type
== CT_INVARIANT
)
1744 execute_load_motion (loop
, chain
, tmp_vars
);
1746 execute_pred_commoning_chain (loop
, chain
, tmp_vars
);
1749 update_ssa (TODO_update_ssa_only_virtuals
);
1752 /* For each reference in CHAINS, if its defining statement is
1753 phi node, record the ssa name that is defined by it. */
1756 replace_phis_by_defined_names (vec
<chain_p
> chains
)
1762 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1763 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1765 if (gimple_code (a
->stmt
) == GIMPLE_PHI
)
1767 a
->name_defined_by_phi
= PHI_RESULT (a
->stmt
);
1773 /* For each reference in CHAINS, if name_defined_by_phi is not
1774 NULL, use it to set the stmt field. */
1777 replace_names_by_phis (vec
<chain_p
> chains
)
1783 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1784 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1785 if (a
->stmt
== NULL
)
1787 a
->stmt
= SSA_NAME_DEF_STMT (a
->name_defined_by_phi
);
1788 gcc_assert (gimple_code (a
->stmt
) == GIMPLE_PHI
);
1789 a
->name_defined_by_phi
= NULL_TREE
;
1793 /* Wrapper over execute_pred_commoning, to pass it as a callback
1794 to tree_transform_and_unroll_loop. */
1798 vec
<chain_p
> chains
;
1803 execute_pred_commoning_cbck (struct loop
*loop
, void *data
)
1805 struct epcc_data
*const dta
= (struct epcc_data
*) data
;
1807 /* Restore phi nodes that were replaced by ssa names before
1808 tree_transform_and_unroll_loop (see detailed description in
1809 tree_predictive_commoning_loop). */
1810 replace_names_by_phis (dta
->chains
);
1811 execute_pred_commoning (loop
, dta
->chains
, dta
->tmp_vars
);
1814 /* Base NAME and all the names in the chain of phi nodes that use it
1815 on variable VAR. The phi nodes are recognized by being in the copies of
1816 the header of the LOOP. */
1819 base_names_in_chain_on (struct loop
*loop
, tree name
, tree var
)
1822 imm_use_iterator iter
;
1824 replace_ssa_name_symbol (name
, var
);
1829 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1831 if (gimple_code (stmt
) == GIMPLE_PHI
1832 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1835 BREAK_FROM_IMM_USE_STMT (iter
);
1841 name
= PHI_RESULT (phi
);
1842 replace_ssa_name_symbol (name
, var
);
1846 /* Given an unrolled LOOP after predictive commoning, remove the
1847 register copies arising from phi nodes by changing the base
1848 variables of SSA names. TMP_VARS is the set of the temporary variables
1849 for those we want to perform this. */
1852 eliminate_temp_copies (struct loop
*loop
, bitmap tmp_vars
)
1856 tree name
, use
, var
;
1857 gimple_stmt_iterator psi
;
1859 e
= loop_latch_edge (loop
);
1860 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1862 phi
= gsi_stmt (psi
);
1863 name
= PHI_RESULT (phi
);
1864 var
= SSA_NAME_VAR (name
);
1865 if (!var
|| !bitmap_bit_p (tmp_vars
, DECL_UID (var
)))
1867 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1868 gcc_assert (TREE_CODE (use
) == SSA_NAME
);
1870 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1871 stmt
= SSA_NAME_DEF_STMT (use
);
1872 while (gimple_code (stmt
) == GIMPLE_PHI
1873 /* In case we could not unroll the loop enough to eliminate
1874 all copies, we may reach the loop header before the defining
1875 statement (in that case, some register copies will be present
1876 in loop latch in the final code, corresponding to the newly
1877 created looparound phi nodes). */
1878 && gimple_bb (stmt
) != loop
->header
)
1880 gcc_assert (single_pred_p (gimple_bb (stmt
)));
1881 use
= PHI_ARG_DEF (stmt
, 0);
1882 stmt
= SSA_NAME_DEF_STMT (use
);
1885 base_names_in_chain_on (loop
, use
, var
);
1889 /* Returns true if CHAIN is suitable to be combined. */
1892 chain_can_be_combined_p (chain_p chain
)
1894 return (!chain
->combined
1895 && (chain
->type
== CT_LOAD
|| chain
->type
== CT_COMBINATION
));
1898 /* Returns the modify statement that uses NAME. Skips over assignment
1899 statements, NAME is replaced with the actual name used in the returned
1903 find_use_stmt (tree
*name
)
1908 /* Skip over assignments. */
1911 stmt
= single_nonlooparound_use (*name
);
1915 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1918 lhs
= gimple_assign_lhs (stmt
);
1919 if (TREE_CODE (lhs
) != SSA_NAME
)
1922 if (gimple_assign_copy_p (stmt
))
1924 rhs
= gimple_assign_rhs1 (stmt
);
1930 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1931 == GIMPLE_BINARY_RHS
)
1938 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1941 may_reassociate_p (tree type
, enum tree_code code
)
1943 if (FLOAT_TYPE_P (type
)
1944 && !flag_unsafe_math_optimizations
)
1947 return (commutative_tree_code (code
)
1948 && associative_tree_code (code
));
1951 /* If the operation used in STMT is associative and commutative, go through the
1952 tree of the same operations and returns its root. Distance to the root
1953 is stored in DISTANCE. */
1956 find_associative_operation_root (gimple stmt
, unsigned *distance
)
1960 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1961 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1964 if (!may_reassociate_p (type
, code
))
1969 lhs
= gimple_assign_lhs (stmt
);
1970 gcc_assert (TREE_CODE (lhs
) == SSA_NAME
);
1972 next
= find_use_stmt (&lhs
);
1974 || gimple_assign_rhs_code (next
) != code
)
1986 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
1987 is no such statement, returns NULL_TREE. In case the operation used on
1988 NAME1 and NAME2 is associative and commutative, returns the root of the
1989 tree formed by this operation instead of the statement that uses NAME1 or
1993 find_common_use_stmt (tree
*name1
, tree
*name2
)
1995 gimple stmt1
, stmt2
;
1997 stmt1
= find_use_stmt (name1
);
2001 stmt2
= find_use_stmt (name2
);
2008 stmt1
= find_associative_operation_root (stmt1
, NULL
);
2011 stmt2
= find_associative_operation_root (stmt2
, NULL
);
2015 return (stmt1
== stmt2
? stmt1
: NULL
);
2018 /* Checks whether R1 and R2 are combined together using CODE, with the result
2019 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2020 if it is true. If CODE is ERROR_MARK, set these values instead. */
2023 combinable_refs_p (dref r1
, dref r2
,
2024 enum tree_code
*code
, bool *swap
, tree
*rslt_type
)
2026 enum tree_code acode
;
2032 name1
= name_for_ref (r1
);
2033 name2
= name_for_ref (r2
);
2034 gcc_assert (name1
!= NULL_TREE
&& name2
!= NULL_TREE
);
2036 stmt
= find_common_use_stmt (&name1
, &name2
);
2039 /* A simple post-dominance check - make sure the combination
2040 is executed under the same condition as the references. */
2041 || (gimple_bb (stmt
) != gimple_bb (r1
->stmt
)
2042 && gimple_bb (stmt
) != gimple_bb (r2
->stmt
)))
2045 acode
= gimple_assign_rhs_code (stmt
);
2046 aswap
= (!commutative_tree_code (acode
)
2047 && gimple_assign_rhs1 (stmt
) != name1
);
2048 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2050 if (*code
== ERROR_MARK
)
2058 return (*code
== acode
2060 && *rslt_type
== atype
);
2063 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2064 an assignment of the remaining operand. */
2067 remove_name_from_operation (gimple stmt
, tree op
)
2070 gimple_stmt_iterator si
;
2072 gcc_assert (is_gimple_assign (stmt
));
2074 if (gimple_assign_rhs1 (stmt
) == op
)
2075 other_op
= gimple_assign_rhs2 (stmt
);
2077 other_op
= gimple_assign_rhs1 (stmt
);
2079 si
= gsi_for_stmt (stmt
);
2080 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2082 /* We should not have reallocated STMT. */
2083 gcc_assert (gsi_stmt (si
) == stmt
);
2088 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2089 are combined in a single statement, and returns this statement. */
2092 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2094 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2095 gimple new_stmt
, tmp_stmt
;
2096 tree new_name
, tmp_name
, var
, r1
, r2
;
2097 unsigned dist1
, dist2
;
2098 enum tree_code code
;
2099 tree type
= TREE_TYPE (name1
);
2100 gimple_stmt_iterator bsi
;
2102 stmt1
= find_use_stmt (&name1
);
2103 stmt2
= find_use_stmt (&name2
);
2104 root1
= find_associative_operation_root (stmt1
, &dist1
);
2105 root2
= find_associative_operation_root (stmt2
, &dist2
);
2106 code
= gimple_assign_rhs_code (stmt1
);
2108 gcc_assert (root1
&& root2
&& root1
== root2
2109 && code
== gimple_assign_rhs_code (stmt2
));
2111 /* Find the root of the nearest expression in that both NAME1 and NAME2
2118 while (dist1
> dist2
)
2120 s1
= find_use_stmt (&r1
);
2121 r1
= gimple_assign_lhs (s1
);
2124 while (dist2
> dist1
)
2126 s2
= find_use_stmt (&r2
);
2127 r2
= gimple_assign_lhs (s2
);
2133 s1
= find_use_stmt (&r1
);
2134 r1
= gimple_assign_lhs (s1
);
2135 s2
= find_use_stmt (&r2
);
2136 r2
= gimple_assign_lhs (s2
);
2139 /* Remove NAME1 and NAME2 from the statements in that they are used
2141 remove_name_from_operation (stmt1
, name1
);
2142 remove_name_from_operation (stmt2
, name2
);
2144 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2145 combine it with the rhs of S1. */
2146 var
= create_tmp_reg (type
, "predreastmp");
2147 new_name
= make_ssa_name (var
, NULL
);
2148 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2150 var
= create_tmp_reg (type
, "predreastmp");
2151 tmp_name
= make_ssa_name (var
, NULL
);
2153 /* Rhs of S1 may now be either a binary expression with operation
2154 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2155 so that name1 or name2 was removed from it). */
2156 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2158 gimple_assign_rhs1 (s1
),
2159 gimple_assign_rhs2 (s1
));
2161 bsi
= gsi_for_stmt (s1
);
2162 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2163 s1
= gsi_stmt (bsi
);
2166 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2167 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2172 /* Returns the statement that combines references R1 and R2. In case R1
2173 and R2 are not used in the same statement, but they are used with an
2174 associative and commutative operation in the same expression, reassociate
2175 the expression so that they are used in the same statement. */
2178 stmt_combining_refs (dref r1
, dref r2
)
2180 gimple stmt1
, stmt2
;
2181 tree name1
= name_for_ref (r1
);
2182 tree name2
= name_for_ref (r2
);
2184 stmt1
= find_use_stmt (&name1
);
2185 stmt2
= find_use_stmt (&name2
);
2189 return reassociate_to_the_same_stmt (name1
, name2
);
2192 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2193 description of the new chain is returned, otherwise we return NULL. */
2196 combine_chains (chain_p ch1
, chain_p ch2
)
2199 enum tree_code op
= ERROR_MARK
;
2204 tree rslt_type
= NULL_TREE
;
2208 if (ch1
->length
!= ch2
->length
)
2211 if (ch1
->refs
.length () != ch2
->refs
.length ())
2214 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2215 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2217 if (r1
->distance
!= r2
->distance
)
2220 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2231 new_chain
= XCNEW (struct chain
);
2232 new_chain
->type
= CT_COMBINATION
;
2234 new_chain
->ch1
= ch1
;
2235 new_chain
->ch2
= ch2
;
2236 new_chain
->rslt_type
= rslt_type
;
2237 new_chain
->length
= ch1
->length
;
2239 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2240 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2242 nw
= XCNEW (struct dref_d
);
2243 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2244 nw
->distance
= r1
->distance
;
2246 new_chain
->refs
.safe_push (nw
);
2249 new_chain
->has_max_use_after
= false;
2250 root_stmt
= get_chain_root (new_chain
)->stmt
;
2251 for (i
= 1; new_chain
->refs
.iterate (i
, &nw
); i
++)
2253 if (nw
->distance
== new_chain
->length
2254 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2256 new_chain
->has_max_use_after
= true;
2261 ch1
->combined
= true;
2262 ch2
->combined
= true;
2266 /* Try to combine the CHAINS. */
2269 try_combine_chains (vec
<chain_p
> *chains
)
2272 chain_p ch1
, ch2
, cch
;
2273 auto_vec
<chain_p
> worklist
;
2275 FOR_EACH_VEC_ELT (*chains
, i
, ch1
)
2276 if (chain_can_be_combined_p (ch1
))
2277 worklist
.safe_push (ch1
);
2279 while (!worklist
.is_empty ())
2281 ch1
= worklist
.pop ();
2282 if (!chain_can_be_combined_p (ch1
))
2285 FOR_EACH_VEC_ELT (*chains
, j
, ch2
)
2287 if (!chain_can_be_combined_p (ch2
))
2290 cch
= combine_chains (ch1
, ch2
);
2293 worklist
.safe_push (cch
);
2294 chains
->safe_push (cch
);
2301 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2302 impossible because one of these initializers may trap, true otherwise. */
2305 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2307 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2308 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2312 edge entry
= loop_preheader_edge (loop
);
2314 /* Find the initializers for the variables, and check that they cannot
2316 chain
->inits
.create (n
);
2317 for (i
= 0; i
< n
; i
++)
2318 chain
->inits
.quick_push (NULL_TREE
);
2320 /* If we have replaced some looparound phi nodes, use their initializers
2321 instead of creating our own. */
2322 FOR_EACH_VEC_ELT (chain
->refs
, i
, laref
)
2324 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2327 gcc_assert (laref
->distance
> 0);
2328 chain
->inits
[n
- laref
->distance
]
2329 = PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
);
2332 for (i
= 0; i
< n
; i
++)
2334 if (chain
->inits
[i
] != NULL_TREE
)
2337 init
= ref_at_iteration (dr
, (int) i
- n
, &stmts
);
2338 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2342 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2344 chain
->inits
[i
] = init
;
2350 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2351 be used because the initializers might trap. */
2354 prepare_initializers (struct loop
*loop
, vec
<chain_p
> chains
)
2359 for (i
= 0; i
< chains
.length (); )
2362 if (prepare_initializers_chain (loop
, chain
))
2366 release_chain (chain
);
2367 chains
.unordered_remove (i
);
2372 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2376 tree_predictive_commoning_loop (struct loop
*loop
)
2378 vec
<data_reference_p
> datarefs
;
2379 vec
<ddr_p
> dependences
;
2380 struct component
*components
;
2381 vec
<chain_p
> chains
= vNULL
;
2382 unsigned unroll_factor
;
2383 struct tree_niter_desc desc
;
2384 bool unroll
= false;
2388 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2389 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2391 /* Find the data references and split them into components according to their
2392 dependence relations. */
2393 stack_vec
<loop_p
, 3> loop_nest
;
2394 dependences
.create (10);
2395 datarefs
.create (10);
2396 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
2399 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2400 fprintf (dump_file
, "Cannot analyze data dependencies\n");
2401 free_data_refs (datarefs
);
2402 free_dependence_relations (dependences
);
2406 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2407 dump_data_dependence_relations (dump_file
, dependences
);
2409 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2410 loop_nest
.release ();
2411 free_dependence_relations (dependences
);
2414 free_data_refs (datarefs
);
2418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2420 fprintf (dump_file
, "Initial state:\n\n");
2421 dump_components (dump_file
, components
);
2424 /* Find the suitable components and split them into chains. */
2425 components
= filter_suitable_components (loop
, components
);
2427 tmp_vars
= BITMAP_ALLOC (NULL
);
2428 looparound_phis
= BITMAP_ALLOC (NULL
);
2429 determine_roots (loop
, components
, &chains
);
2430 release_components (components
);
2432 if (!chains
.exists ())
2434 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2436 "Predictive commoning failed: no suitable chains\n");
2439 prepare_initializers (loop
, chains
);
2441 /* Try to combine the chains that are always worked with together. */
2442 try_combine_chains (&chains
);
2444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2446 fprintf (dump_file
, "Before commoning:\n\n");
2447 dump_chains (dump_file
, chains
);
2450 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2451 that its number of iterations is divisible by the factor. */
2452 unroll_factor
= determine_unroll_factor (chains
);
2454 unroll
= (unroll_factor
> 1
2455 && can_unroll_loop_p (loop
, unroll_factor
, &desc
));
2456 exit
= single_dom_exit (loop
);
2458 /* Execute the predictive commoning transformations, and possibly unroll the
2462 struct epcc_data dta
;
2464 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2465 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2467 dta
.chains
= chains
;
2468 dta
.tmp_vars
= tmp_vars
;
2470 update_ssa (TODO_update_ssa_only_virtuals
);
2472 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2473 execute_pred_commoning_cbck is called may cause phi nodes to be
2474 reallocated, which is a problem since CHAINS may point to these
2475 statements. To fix this, we store the ssa names defined by the
2476 phi nodes here instead of the phi nodes themselves, and restore
2477 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2478 replace_phis_by_defined_names (chains
);
2480 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2481 execute_pred_commoning_cbck
, &dta
);
2482 eliminate_temp_copies (loop
, tmp_vars
);
2486 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2488 "Executing predictive commoning without unrolling.\n");
2489 execute_pred_commoning (loop
, chains
, tmp_vars
);
2493 release_chains (chains
);
2494 free_data_refs (datarefs
);
2495 BITMAP_FREE (tmp_vars
);
2496 BITMAP_FREE (looparound_phis
);
2498 free_affine_expand_cache (&name_expansions
);
2503 /* Runs predictive commoning. */
2506 tree_predictive_commoning (void)
2508 bool unrolled
= false;
2512 initialize_original_copy_tables ();
2513 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
2514 if (optimize_loop_for_speed_p (loop
))
2516 unrolled
|= tree_predictive_commoning_loop (loop
);
2522 ret
= TODO_cleanup_cfg
;
2524 free_original_copy_tables ();
2529 /* Predictive commoning Pass. */
2532 run_tree_predictive_commoning (void)
2537 return tree_predictive_commoning ();
2541 gate_tree_predictive_commoning (void)
2543 return flag_predictive_commoning
!= 0;
2548 const pass_data pass_data_predcom
=
2550 GIMPLE_PASS
, /* type */
2552 OPTGROUP_LOOP
, /* optinfo_flags */
2553 true, /* has_gate */
2554 true, /* has_execute */
2555 TV_PREDCOM
, /* tv_id */
2556 PROP_cfg
, /* properties_required */
2557 0, /* properties_provided */
2558 0, /* properties_destroyed */
2559 0, /* todo_flags_start */
2560 TODO_update_ssa_only_virtuals
, /* todo_flags_finish */
2563 class pass_predcom
: public gimple_opt_pass
2566 pass_predcom (gcc::context
*ctxt
)
2567 : gimple_opt_pass (pass_data_predcom
, ctxt
)
2570 /* opt_pass methods: */
2571 bool gate () { return gate_tree_predictive_commoning (); }
2572 unsigned int execute () { return run_tree_predictive_commoning (); }
2574 }; // class pass_predcom
2579 make_pass_predcom (gcc::context
*ctxt
)
2581 return new pass_predcom (ctxt
);