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 "gimple-ssa.h"
196 #include "tree-phinodes.h"
197 #include "ssa-iterators.h"
198 #include "tree-ssanames.h"
199 #include "tree-ssa-loop-ivopts.h"
200 #include "tree-ssa-loop-manip.h"
201 #include "tree-ssa-loop-niter.h"
202 #include "tree-ssa-loop.h"
203 #include "tree-into-ssa.h"
204 #include "tree-dfa.h"
205 #include "tree-ssa.h"
207 #include "tree-data-ref.h"
208 #include "tree-scalar-evolution.h"
209 #include "tree-chrec.h"
211 #include "gimple-pretty-print.h"
212 #include "tree-pass.h"
213 #include "tree-affine.h"
214 #include "tree-inline.h"
216 /* The maximum number of iterations between the considered memory
219 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
221 /* Data references (or phi nodes that carry data reference values across
224 typedef struct dref_d
226 /* The reference itself. */
227 struct data_reference
*ref
;
229 /* The statement in that the reference appears. */
232 /* In case that STMT is a phi node, this field is set to the SSA name
233 defined by it in replace_phis_by_defined_names (in order to avoid
234 pointing to phi node that got reallocated in the meantime). */
235 tree name_defined_by_phi
;
237 /* Distance of the reference from the root of the chain (in number of
238 iterations of the loop). */
241 /* Number of iterations offset from the first reference in the component. */
244 /* Number of the reference in a component, in dominance ordering. */
247 /* True if the memory reference is always accessed when the loop is
249 unsigned always_accessed
: 1;
253 /* Type of the chain of the references. */
257 /* The addresses of the references in the chain are constant. */
260 /* There are only loads in the chain. */
263 /* Root of the chain is store, the rest are loads. */
266 /* A combination of two chains. */
270 /* Chains of data references. */
274 /* Type of the chain. */
275 enum chain_type type
;
277 /* For combination chains, the operator and the two chains that are
278 combined, and the type of the result. */
281 struct chain
*ch1
, *ch2
;
283 /* The references in the chain. */
286 /* The maximum distance of the reference in the chain from the root. */
289 /* The variables used to copy the value throughout iterations. */
292 /* Initializers for the variables. */
295 /* True if there is a use of a variable with the maximal distance
296 that comes after the root in the loop. */
297 unsigned has_max_use_after
: 1;
299 /* True if all the memory references in the chain are always accessed. */
300 unsigned all_always_accessed
: 1;
302 /* True if this chain was combined together with some other chain. */
303 unsigned combined
: 1;
307 /* Describes the knowledge about the step of the memory references in
312 /* The step is zero. */
315 /* The step is nonzero. */
318 /* The step may or may not be nonzero. */
322 /* Components of the data dependence graph. */
326 /* The references in the component. */
329 /* What we know about the step of the references in the component. */
330 enum ref_step_type comp_step
;
332 /* Next component in the list. */
333 struct component
*next
;
336 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
338 static bitmap looparound_phis
;
340 /* Cache used by tree_to_aff_combination_expand. */
342 static struct pointer_map_t
*name_expansions
;
344 /* Dumps data reference REF to FILE. */
346 extern void dump_dref (FILE *, dref
);
348 dump_dref (FILE *file
, dref ref
)
353 print_generic_expr (file
, DR_REF (ref
->ref
), TDF_SLIM
);
354 fprintf (file
, " (id %u%s)\n", ref
->pos
,
355 DR_IS_READ (ref
->ref
) ? "" : ", write");
357 fprintf (file
, " offset ");
358 dump_double_int (file
, ref
->offset
, false);
359 fprintf (file
, "\n");
361 fprintf (file
, " distance %u\n", ref
->distance
);
365 if (gimple_code (ref
->stmt
) == GIMPLE_PHI
)
366 fprintf (file
, " looparound ref\n");
368 fprintf (file
, " combination ref\n");
369 fprintf (file
, " in statement ");
370 print_gimple_stmt (file
, ref
->stmt
, 0, TDF_SLIM
);
371 fprintf (file
, "\n");
372 fprintf (file
, " distance %u\n", ref
->distance
);
377 /* Dumps CHAIN to FILE. */
379 extern void dump_chain (FILE *, chain_p
);
381 dump_chain (FILE *file
, chain_p chain
)
384 const char *chain_type
;
391 chain_type
= "Load motion";
395 chain_type
= "Loads-only";
399 chain_type
= "Store-loads";
403 chain_type
= "Combination";
410 fprintf (file
, "%s chain %p%s\n", chain_type
, (void *) chain
,
411 chain
->combined
? " (combined)" : "");
412 if (chain
->type
!= CT_INVARIANT
)
413 fprintf (file
, " max distance %u%s\n", chain
->length
,
414 chain
->has_max_use_after
? "" : ", may reuse first");
416 if (chain
->type
== CT_COMBINATION
)
418 fprintf (file
, " equal to %p %s %p in type ",
419 (void *) chain
->ch1
, op_symbol_code (chain
->op
),
420 (void *) chain
->ch2
);
421 print_generic_expr (file
, chain
->rslt_type
, TDF_SLIM
);
422 fprintf (file
, "\n");
425 if (chain
->vars
.exists ())
427 fprintf (file
, " vars");
428 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
431 print_generic_expr (file
, var
, TDF_SLIM
);
433 fprintf (file
, "\n");
436 if (chain
->inits
.exists ())
438 fprintf (file
, " inits");
439 FOR_EACH_VEC_ELT (chain
->inits
, i
, var
)
442 print_generic_expr (file
, var
, TDF_SLIM
);
444 fprintf (file
, "\n");
447 fprintf (file
, " references:\n");
448 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
451 fprintf (file
, "\n");
454 /* Dumps CHAINS to FILE. */
456 extern void dump_chains (FILE *, vec
<chain_p
> );
458 dump_chains (FILE *file
, vec
<chain_p
> chains
)
463 FOR_EACH_VEC_ELT (chains
, i
, chain
)
464 dump_chain (file
, chain
);
467 /* Dumps COMP to FILE. */
469 extern void dump_component (FILE *, struct component
*);
471 dump_component (FILE *file
, struct component
*comp
)
476 fprintf (file
, "Component%s:\n",
477 comp
->comp_step
== RS_INVARIANT
? " (invariant)" : "");
478 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
480 fprintf (file
, "\n");
483 /* Dumps COMPS to FILE. */
485 extern void dump_components (FILE *, struct component
*);
487 dump_components (FILE *file
, struct component
*comps
)
489 struct component
*comp
;
491 for (comp
= comps
; comp
; comp
= comp
->next
)
492 dump_component (file
, comp
);
495 /* Frees a chain CHAIN. */
498 release_chain (chain_p chain
)
506 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
509 chain
->refs
.release ();
510 chain
->vars
.release ();
511 chain
->inits
.release ();
519 release_chains (vec
<chain_p
> chains
)
524 FOR_EACH_VEC_ELT (chains
, i
, chain
)
525 release_chain (chain
);
529 /* Frees a component COMP. */
532 release_component (struct component
*comp
)
534 comp
->refs
.release ();
538 /* Frees list of components COMPS. */
541 release_components (struct component
*comps
)
543 struct component
*act
, *next
;
545 for (act
= comps
; act
; act
= next
)
548 release_component (act
);
552 /* Finds a root of tree given by FATHERS containing A, and performs path
556 component_of (unsigned fathers
[], unsigned a
)
560 for (root
= a
; root
!= fathers
[root
]; root
= fathers
[root
])
563 for (; a
!= root
; a
= n
)
572 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
573 components, A and B are components to merge. */
576 merge_comps (unsigned fathers
[], unsigned sizes
[], unsigned a
, unsigned b
)
578 unsigned ca
= component_of (fathers
, a
);
579 unsigned cb
= component_of (fathers
, b
);
584 if (sizes
[ca
] < sizes
[cb
])
586 sizes
[cb
] += sizes
[ca
];
591 sizes
[ca
] += sizes
[cb
];
596 /* Returns true if A is a reference that is suitable for predictive commoning
597 in the innermost loop that contains it. REF_STEP is set according to the
598 step of the reference A. */
601 suitable_reference_p (struct data_reference
*a
, enum ref_step_type
*ref_step
)
603 tree ref
= DR_REF (a
), step
= DR_STEP (a
);
606 || TREE_THIS_VOLATILE (ref
)
607 || !is_gimple_reg_type (TREE_TYPE (ref
))
608 || tree_could_throw_p (ref
))
611 if (integer_zerop (step
))
612 *ref_step
= RS_INVARIANT
;
613 else if (integer_nonzerop (step
))
614 *ref_step
= RS_NONZERO
;
621 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
624 aff_combination_dr_offset (struct data_reference
*dr
, aff_tree
*offset
)
626 tree type
= TREE_TYPE (DR_OFFSET (dr
));
629 tree_to_aff_combination_expand (DR_OFFSET (dr
), type
, offset
,
631 aff_combination_const (&delta
, type
, tree_to_double_int (DR_INIT (dr
)));
632 aff_combination_add (offset
, &delta
);
635 /* Determines number of iterations of the innermost enclosing loop before B
636 refers to exactly the same location as A and stores it to OFF. If A and
637 B do not have the same step, they never meet, or anything else fails,
638 returns false, otherwise returns true. Both A and B are assumed to
639 satisfy suitable_reference_p. */
642 determine_offset (struct data_reference
*a
, struct data_reference
*b
,
645 aff_tree diff
, baseb
, step
;
648 /* Check that both the references access the location in the same type. */
649 typea
= TREE_TYPE (DR_REF (a
));
650 typeb
= TREE_TYPE (DR_REF (b
));
651 if (!useless_type_conversion_p (typeb
, typea
))
654 /* Check whether the base address and the step of both references is the
656 if (!operand_equal_p (DR_STEP (a
), DR_STEP (b
), 0)
657 || !operand_equal_p (DR_BASE_ADDRESS (a
), DR_BASE_ADDRESS (b
), 0))
660 if (integer_zerop (DR_STEP (a
)))
662 /* If the references have loop invariant address, check that they access
663 exactly the same location. */
664 *off
= double_int_zero
;
665 return (operand_equal_p (DR_OFFSET (a
), DR_OFFSET (b
), 0)
666 && operand_equal_p (DR_INIT (a
), DR_INIT (b
), 0));
669 /* Compare the offsets of the addresses, and check whether the difference
670 is a multiple of step. */
671 aff_combination_dr_offset (a
, &diff
);
672 aff_combination_dr_offset (b
, &baseb
);
673 aff_combination_scale (&baseb
, double_int_minus_one
);
674 aff_combination_add (&diff
, &baseb
);
676 tree_to_aff_combination_expand (DR_STEP (a
), TREE_TYPE (DR_STEP (a
)),
677 &step
, &name_expansions
);
678 return aff_combination_constant_multiple_p (&diff
, &step
, off
);
681 /* Returns the last basic block in LOOP for that we are sure that
682 it is executed whenever the loop is entered. */
685 last_always_executed_block (struct loop
*loop
)
688 vec
<edge
> exits
= get_loop_exit_edges (loop
);
690 basic_block last
= loop
->latch
;
692 FOR_EACH_VEC_ELT (exits
, i
, ex
)
693 last
= nearest_common_dominator (CDI_DOMINATORS
, last
, ex
->src
);
699 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
701 static struct component
*
702 split_data_refs_to_components (struct loop
*loop
,
703 vec
<data_reference_p
> datarefs
,
706 unsigned i
, n
= datarefs
.length ();
707 unsigned ca
, ia
, ib
, bad
;
708 unsigned *comp_father
= XNEWVEC (unsigned, n
+ 1);
709 unsigned *comp_size
= XNEWVEC (unsigned, n
+ 1);
710 struct component
**comps
;
711 struct data_reference
*dr
, *dra
, *drb
;
712 struct data_dependence_relation
*ddr
;
713 struct component
*comp_list
= NULL
, *comp
;
715 basic_block last_always_executed
= last_always_executed_block (loop
);
717 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
721 /* A fake reference for call or asm_expr that may clobber memory;
725 dr
->aux
= (void *) (size_t) i
;
730 /* A component reserved for the "bad" data references. */
734 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
736 enum ref_step_type dummy
;
738 if (!suitable_reference_p (dr
, &dummy
))
740 ia
= (unsigned) (size_t) dr
->aux
;
741 merge_comps (comp_father
, comp_size
, n
, ia
);
745 FOR_EACH_VEC_ELT (depends
, i
, ddr
)
747 double_int dummy_off
;
749 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
754 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
755 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
759 bad
= component_of (comp_father
, n
);
761 /* If both A and B are reads, we may ignore unsuitable dependences. */
762 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
763 && (ia
== bad
|| ib
== bad
764 || !determine_offset (dra
, drb
, &dummy_off
)))
767 merge_comps (comp_father
, comp_size
, ia
, ib
);
770 comps
= XCNEWVEC (struct component
*, n
);
771 bad
= component_of (comp_father
, n
);
772 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
774 ia
= (unsigned) (size_t) dr
->aux
;
775 ca
= component_of (comp_father
, ia
);
782 comp
= XCNEW (struct component
);
783 comp
->refs
.create (comp_size
[ca
]);
787 dataref
= XCNEW (struct dref_d
);
789 dataref
->stmt
= DR_STMT (dr
);
790 dataref
->offset
= double_int_zero
;
791 dataref
->distance
= 0;
793 dataref
->always_accessed
794 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
795 gimple_bb (dataref
->stmt
));
796 dataref
->pos
= comp
->refs
.length ();
797 comp
->refs
.quick_push (dataref
);
800 for (i
= 0; i
< n
; i
++)
805 comp
->next
= comp_list
;
817 /* Returns true if the component COMP satisfies the conditions
818 described in 2) at the beginning of this file. LOOP is the current
822 suitable_component_p (struct loop
*loop
, struct component
*comp
)
826 basic_block ba
, bp
= loop
->header
;
827 bool ok
, has_write
= false;
829 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
831 ba
= gimple_bb (a
->stmt
);
833 if (!just_once_each_iteration_p (loop
, ba
))
836 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
839 if (DR_IS_WRITE (a
->ref
))
843 first
= comp
->refs
[0];
844 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
846 first
->offset
= double_int_zero
;
848 for (i
= 1; comp
->refs
.iterate (i
, &a
); i
++)
850 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
853 #ifdef ENABLE_CHECKING
855 enum ref_step_type a_step
;
856 ok
= suitable_reference_p (a
->ref
, &a_step
);
857 gcc_assert (ok
&& a_step
== comp
->comp_step
);
862 /* If there is a write inside the component, we must know whether the
863 step is nonzero or not -- we would not otherwise be able to recognize
864 whether the value accessed by reads comes from the OFFSET-th iteration
865 or the previous one. */
866 if (has_write
&& comp
->comp_step
== RS_ANY
)
872 /* Check the conditions on references inside each of components COMPS,
873 and remove the unsuitable components from the list. The new list
874 of components is returned. The conditions are described in 2) at
875 the beginning of this file. LOOP is the current loop. */
877 static struct component
*
878 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
880 struct component
**comp
, *act
;
882 for (comp
= &comps
; *comp
; )
885 if (suitable_component_p (loop
, act
))
893 FOR_EACH_VEC_ELT (act
->refs
, i
, ref
)
895 release_component (act
);
902 /* Compares two drefs A and B by their offset and position. Callback for
906 order_drefs (const void *a
, const void *b
)
908 const dref
*const da
= (const dref
*) a
;
909 const dref
*const db
= (const dref
*) b
;
910 int offcmp
= (*da
)->offset
.scmp ((*db
)->offset
);
915 return (*da
)->pos
- (*db
)->pos
;
918 /* Returns root of the CHAIN. */
921 get_chain_root (chain_p chain
)
923 return chain
->refs
[0];
926 /* Adds REF to the chain CHAIN. */
929 add_ref_to_chain (chain_p chain
, dref ref
)
931 dref root
= get_chain_root (chain
);
934 gcc_assert (root
->offset
.sle (ref
->offset
));
935 dist
= ref
->offset
- root
->offset
;
936 if (double_int::from_uhwi (MAX_DISTANCE
).ule (dist
))
941 gcc_assert (dist
.fits_uhwi ());
943 chain
->refs
.safe_push (ref
);
945 ref
->distance
= dist
.to_uhwi ();
947 if (ref
->distance
>= chain
->length
)
949 chain
->length
= ref
->distance
;
950 chain
->has_max_use_after
= false;
953 if (ref
->distance
== chain
->length
954 && ref
->pos
> root
->pos
)
955 chain
->has_max_use_after
= true;
957 chain
->all_always_accessed
&= ref
->always_accessed
;
960 /* Returns the chain for invariant component COMP. */
963 make_invariant_chain (struct component
*comp
)
965 chain_p chain
= XCNEW (struct chain
);
969 chain
->type
= CT_INVARIANT
;
971 chain
->all_always_accessed
= true;
973 FOR_EACH_VEC_ELT (comp
->refs
, i
, ref
)
975 chain
->refs
.safe_push (ref
);
976 chain
->all_always_accessed
&= ref
->always_accessed
;
982 /* Make a new chain rooted at REF. */
985 make_rooted_chain (dref ref
)
987 chain_p chain
= XCNEW (struct chain
);
989 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
991 chain
->refs
.safe_push (ref
);
992 chain
->all_always_accessed
= ref
->always_accessed
;
999 /* Returns true if CHAIN is not trivial. */
1002 nontrivial_chain_p (chain_p chain
)
1004 return chain
!= NULL
&& chain
->refs
.length () > 1;
1007 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1011 name_for_ref (dref ref
)
1015 if (is_gimple_assign (ref
->stmt
))
1017 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1018 name
= gimple_assign_lhs (ref
->stmt
);
1020 name
= gimple_assign_rhs1 (ref
->stmt
);
1023 name
= PHI_RESULT (ref
->stmt
);
1025 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1028 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1029 iterations of the innermost enclosing loop). */
1032 valid_initializer_p (struct data_reference
*ref
,
1033 unsigned distance
, struct data_reference
*root
)
1035 aff_tree diff
, base
, step
;
1038 /* Both REF and ROOT must be accessing the same object. */
1039 if (!operand_equal_p (DR_BASE_ADDRESS (ref
), DR_BASE_ADDRESS (root
), 0))
1042 /* The initializer is defined outside of loop, hence its address must be
1043 invariant inside the loop. */
1044 gcc_assert (integer_zerop (DR_STEP (ref
)));
1046 /* If the address of the reference is invariant, initializer must access
1047 exactly the same location. */
1048 if (integer_zerop (DR_STEP (root
)))
1049 return (operand_equal_p (DR_OFFSET (ref
), DR_OFFSET (root
), 0)
1050 && operand_equal_p (DR_INIT (ref
), DR_INIT (root
), 0));
1052 /* Verify that this index of REF is equal to the root's index at
1053 -DISTANCE-th iteration. */
1054 aff_combination_dr_offset (root
, &diff
);
1055 aff_combination_dr_offset (ref
, &base
);
1056 aff_combination_scale (&base
, double_int_minus_one
);
1057 aff_combination_add (&diff
, &base
);
1059 tree_to_aff_combination_expand (DR_STEP (root
), TREE_TYPE (DR_STEP (root
)),
1060 &step
, &name_expansions
);
1061 if (!aff_combination_constant_multiple_p (&diff
, &step
, &off
))
1064 if (off
!= double_int::from_uhwi (distance
))
1070 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1071 initial value is correct (equal to initial value of REF shifted by one
1072 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1073 is the root of the current chain. */
1076 find_looparound_phi (struct loop
*loop
, dref ref
, dref root
)
1078 tree name
, init
, init_ref
;
1079 gimple phi
= NULL
, init_stmt
;
1080 edge latch
= loop_latch_edge (loop
);
1081 struct data_reference init_dr
;
1082 gimple_stmt_iterator psi
;
1084 if (is_gimple_assign (ref
->stmt
))
1086 if (DR_IS_READ (ref
->ref
))
1087 name
= gimple_assign_lhs (ref
->stmt
);
1089 name
= gimple_assign_rhs1 (ref
->stmt
);
1092 name
= PHI_RESULT (ref
->stmt
);
1096 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1098 phi
= gsi_stmt (psi
);
1099 if (PHI_ARG_DEF_FROM_EDGE (phi
, latch
) == name
)
1103 if (gsi_end_p (psi
))
1106 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1107 if (TREE_CODE (init
) != SSA_NAME
)
1109 init_stmt
= SSA_NAME_DEF_STMT (init
);
1110 if (gimple_code (init_stmt
) != GIMPLE_ASSIGN
)
1112 gcc_assert (gimple_assign_lhs (init_stmt
) == init
);
1114 init_ref
= gimple_assign_rhs1 (init_stmt
);
1115 if (!REFERENCE_CLASS_P (init_ref
)
1116 && !DECL_P (init_ref
))
1119 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1120 loop enclosing PHI). */
1121 memset (&init_dr
, 0, sizeof (struct data_reference
));
1122 DR_REF (&init_dr
) = init_ref
;
1123 DR_STMT (&init_dr
) = phi
;
1124 if (!dr_analyze_innermost (&init_dr
, loop
))
1127 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1133 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1136 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1138 dref nw
= XCNEW (struct dref_d
), aref
;
1142 nw
->distance
= ref
->distance
+ 1;
1143 nw
->always_accessed
= 1;
1145 FOR_EACH_VEC_ELT (chain
->refs
, i
, aref
)
1146 if (aref
->distance
>= nw
->distance
)
1148 chain
->refs
.safe_insert (i
, nw
);
1150 if (nw
->distance
> chain
->length
)
1152 chain
->length
= nw
->distance
;
1153 chain
->has_max_use_after
= false;
1157 /* For references in CHAIN that are copied around the LOOP (created previously
1158 by PRE, or by user), add the results of such copies to the chain. This
1159 enables us to remove the copies by unrolling, and may need less registers
1160 (also, it may allow us to combine chains together). */
1163 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1166 dref ref
, root
= get_chain_root (chain
);
1169 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
1171 phi
= find_looparound_phi (loop
, ref
, root
);
1175 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1176 insert_looparound_copy (chain
, ref
, phi
);
1180 /* Find roots of the values and determine distances in the component COMP.
1181 The references are redistributed into CHAINS. LOOP is the current
1185 determine_roots_comp (struct loop
*loop
,
1186 struct component
*comp
,
1187 vec
<chain_p
> *chains
)
1191 chain_p chain
= NULL
;
1192 double_int last_ofs
= double_int_zero
;
1194 /* Invariants are handled specially. */
1195 if (comp
->comp_step
== RS_INVARIANT
)
1197 chain
= make_invariant_chain (comp
);
1198 chains
->safe_push (chain
);
1202 comp
->refs
.qsort (order_drefs
);
1204 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
1206 if (!chain
|| DR_IS_WRITE (a
->ref
)
1207 || double_int::from_uhwi (MAX_DISTANCE
).ule (a
->offset
- last_ofs
))
1209 if (nontrivial_chain_p (chain
))
1211 add_looparound_copies (loop
, chain
);
1212 chains
->safe_push (chain
);
1215 release_chain (chain
);
1216 chain
= make_rooted_chain (a
);
1217 last_ofs
= a
->offset
;
1221 add_ref_to_chain (chain
, a
);
1224 if (nontrivial_chain_p (chain
))
1226 add_looparound_copies (loop
, chain
);
1227 chains
->safe_push (chain
);
1230 release_chain (chain
);
1233 /* Find roots of the values and determine distances in components COMPS, and
1234 separates the references to CHAINS. LOOP is the current loop. */
1237 determine_roots (struct loop
*loop
,
1238 struct component
*comps
, vec
<chain_p
> *chains
)
1240 struct component
*comp
;
1242 for (comp
= comps
; comp
; comp
= comp
->next
)
1243 determine_roots_comp (loop
, comp
, chains
);
1246 /* Replace the reference in statement STMT with temporary variable
1247 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1248 the reference in the statement. IN_LHS is true if the reference
1249 is in the lhs of STMT, false if it is in rhs. */
1252 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1256 gimple_stmt_iterator bsi
, psi
;
1258 if (gimple_code (stmt
) == GIMPLE_PHI
)
1260 gcc_assert (!in_lhs
&& !set
);
1262 val
= PHI_RESULT (stmt
);
1263 bsi
= gsi_after_labels (gimple_bb (stmt
));
1264 psi
= gsi_for_stmt (stmt
);
1265 remove_phi_node (&psi
, false);
1267 /* Turn the phi node into GIMPLE_ASSIGN. */
1268 new_stmt
= gimple_build_assign (val
, new_tree
);
1269 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1273 /* Since the reference is of gimple_reg type, it should only
1274 appear as lhs or rhs of modify statement. */
1275 gcc_assert (is_gimple_assign (stmt
));
1277 bsi
= gsi_for_stmt (stmt
);
1279 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1282 gcc_assert (!in_lhs
);
1283 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1284 stmt
= gsi_stmt (bsi
);
1291 /* We have statement
1295 If OLD is a memory reference, then VAL is gimple_val, and we transform
1301 Otherwise, we are replacing a combination chain,
1302 VAL is the expression that performs the combination, and OLD is an
1303 SSA name. In this case, we transform the assignment to
1310 val
= gimple_assign_lhs (stmt
);
1311 if (TREE_CODE (val
) != SSA_NAME
)
1313 val
= gimple_assign_rhs1 (stmt
);
1314 gcc_assert (gimple_assign_single_p (stmt
));
1315 if (TREE_CLOBBER_P (val
))
1316 val
= get_or_create_ssa_default_def (cfun
, SSA_NAME_VAR (new_tree
));
1318 gcc_assert (gimple_assign_copy_p (stmt
));
1330 val
= gimple_assign_lhs (stmt
);
1333 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1334 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1337 /* Returns a memory reference to DR in the ITER-th iteration of
1338 the loop it was analyzed in. Append init stmts to STMTS. */
1341 ref_at_iteration (data_reference_p dr
, int iter
, gimple_seq
*stmts
)
1343 tree off
= DR_OFFSET (dr
);
1344 tree coff
= DR_INIT (dr
);
1347 else if (TREE_CODE (DR_STEP (dr
)) == INTEGER_CST
)
1348 coff
= size_binop (PLUS_EXPR
, coff
,
1349 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1351 off
= size_binop (PLUS_EXPR
, off
,
1352 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1353 tree addr
= fold_build_pointer_plus (DR_BASE_ADDRESS (dr
), off
);
1354 addr
= force_gimple_operand_1 (addr
, stmts
, is_gimple_mem_ref_addr
,
1356 tree alias_ptr
= fold_convert (reference_alias_ptr_type (DR_REF (dr
)), coff
);
1357 /* While data-ref analysis punts on bit offsets it still handles
1358 bitfield accesses at byte boundaries. Cope with that. Note that
1359 we cannot simply re-apply the outer COMPONENT_REF because the
1360 byte-granular portion of it is already applied via DR_INIT and
1361 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1362 start at offset zero. */
1363 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
1364 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
1366 tree field
= TREE_OPERAND (DR_REF (dr
), 1);
1367 return build3 (BIT_FIELD_REF
, TREE_TYPE (DR_REF (dr
)),
1368 build2 (MEM_REF
, DECL_BIT_FIELD_TYPE (field
),
1370 DECL_SIZE (field
), bitsize_zero_node
);
1373 return fold_build2 (MEM_REF
, TREE_TYPE (DR_REF (dr
)), addr
, alias_ptr
);
1376 /* Get the initialization expression for the INDEX-th temporary variable
1380 get_init_expr (chain_p chain
, unsigned index
)
1382 if (chain
->type
== CT_COMBINATION
)
1384 tree e1
= get_init_expr (chain
->ch1
, index
);
1385 tree e2
= get_init_expr (chain
->ch2
, index
);
1387 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1390 return chain
->inits
[index
];
1393 /* Returns a new temporary variable used for the I-th variable carrying
1394 value of REF. The variable's uid is marked in TMP_VARS. */
1397 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1399 tree type
= TREE_TYPE (ref
);
1400 /* We never access the components of the temporary variable in predictive
1402 tree var
= create_tmp_reg (type
, get_lsm_tmp_name (ref
, i
));
1403 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1407 /* Creates the variables for CHAIN, as well as phi nodes for them and
1408 initialization on entry to LOOP. Uids of the newly created
1409 temporary variables are marked in TMP_VARS. */
1412 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1415 unsigned n
= chain
->length
;
1416 dref root
= get_chain_root (chain
);
1417 bool reuse_first
= !chain
->has_max_use_after
;
1418 tree ref
, init
, var
, next
;
1421 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1423 /* If N == 0, then all the references are within the single iteration. And
1424 since this is an nonempty chain, reuse_first cannot be true. */
1425 gcc_assert (n
> 0 || !reuse_first
);
1427 chain
->vars
.create (n
+ 1);
1429 if (chain
->type
== CT_COMBINATION
)
1430 ref
= gimple_assign_lhs (root
->stmt
);
1432 ref
= DR_REF (root
->ref
);
1434 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1436 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1437 chain
->vars
.quick_push (var
);
1440 chain
->vars
.quick_push (chain
->vars
[0]);
1442 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
1443 chain
->vars
[i
] = make_ssa_name (var
, NULL
);
1445 for (i
= 0; i
< n
; i
++)
1447 var
= chain
->vars
[i
];
1448 next
= chain
->vars
[i
+ 1];
1449 init
= get_init_expr (chain
, i
);
1451 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1453 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1455 phi
= create_phi_node (var
, loop
->header
);
1456 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1457 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1461 /* Create the variables and initialization statement for root of chain
1462 CHAIN. Uids of the newly created temporary variables are marked
1466 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1468 dref root
= get_chain_root (chain
);
1469 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1470 || chain
->type
== CT_COMBINATION
);
1472 initialize_root_vars (loop
, chain
, tmp_vars
);
1473 replace_ref_with (root
->stmt
,
1474 chain
->vars
[chain
->length
],
1478 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1479 initialization on entry to LOOP if necessary. The ssa name for the variable
1480 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1481 around the loop is created. Uid of the newly created temporary variable
1482 is marked in TMP_VARS. INITS is the list containing the (single)
1486 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1487 vec
<tree
> *vars
, vec
<tree
> inits
,
1491 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1494 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1496 /* Find the initializer for the variable, and check that it cannot
1500 vars
->create (written
? 2 : 1);
1501 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1502 vars
->quick_push (var
);
1504 vars
->quick_push ((*vars
)[0]);
1506 FOR_EACH_VEC_ELT (*vars
, i
, var
)
1507 (*vars
)[i
] = make_ssa_name (var
, NULL
);
1511 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1513 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1518 phi
= create_phi_node (var
, loop
->header
);
1519 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1520 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1524 gimple init_stmt
= gimple_build_assign (var
, init
);
1525 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1530 /* Execute load motion for references in chain CHAIN. Uids of the newly
1531 created temporary variables are marked in TMP_VARS. */
1534 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1538 unsigned n_writes
= 0, ridx
, i
;
1541 gcc_assert (chain
->type
== CT_INVARIANT
);
1542 gcc_assert (!chain
->combined
);
1543 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1544 if (DR_IS_WRITE (a
->ref
))
1547 /* If there are no reads in the loop, there is nothing to do. */
1548 if (n_writes
== chain
->refs
.length ())
1551 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1552 &vars
, chain
->inits
, tmp_vars
);
1555 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1557 bool is_read
= DR_IS_READ (a
->ref
);
1559 if (DR_IS_WRITE (a
->ref
))
1565 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1572 replace_ref_with (a
->stmt
, vars
[ridx
],
1573 !is_read
, !is_read
);
1579 /* Returns the single statement in that NAME is used, excepting
1580 the looparound phi nodes contained in one of the chains. If there is no
1581 such statement, or more statements, NULL is returned. */
1584 single_nonlooparound_use (tree name
)
1587 imm_use_iterator it
;
1588 gimple stmt
, ret
= NULL
;
1590 FOR_EACH_IMM_USE_FAST (use
, it
, name
)
1592 stmt
= USE_STMT (use
);
1594 if (gimple_code (stmt
) == GIMPLE_PHI
)
1596 /* Ignore uses in looparound phi nodes. Uses in other phi nodes
1597 could not be processed anyway, so just fail for them. */
1598 if (bitmap_bit_p (looparound_phis
,
1599 SSA_NAME_VERSION (PHI_RESULT (stmt
))))
1604 else if (is_gimple_debug (stmt
))
1606 else if (ret
!= NULL
)
1615 /* Remove statement STMT, as well as the chain of assignments in that it is
1619 remove_stmt (gimple stmt
)
1623 gimple_stmt_iterator psi
;
1625 if (gimple_code (stmt
) == GIMPLE_PHI
)
1627 name
= PHI_RESULT (stmt
);
1628 next
= single_nonlooparound_use (name
);
1629 reset_debug_uses (stmt
);
1630 psi
= gsi_for_stmt (stmt
);
1631 remove_phi_node (&psi
, true);
1634 || !gimple_assign_ssa_name_copy_p (next
)
1635 || gimple_assign_rhs1 (next
) != name
)
1643 gimple_stmt_iterator bsi
;
1645 bsi
= gsi_for_stmt (stmt
);
1647 name
= gimple_assign_lhs (stmt
);
1648 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
1650 next
= single_nonlooparound_use (name
);
1651 reset_debug_uses (stmt
);
1653 unlink_stmt_vdef (stmt
);
1654 gsi_remove (&bsi
, true);
1655 release_defs (stmt
);
1658 || !gimple_assign_ssa_name_copy_p (next
)
1659 || gimple_assign_rhs1 (next
) != name
)
1666 /* Perform the predictive commoning optimization for a chain CHAIN.
1667 Uids of the newly created temporary variables are marked in TMP_VARS.*/
1670 execute_pred_commoning_chain (struct loop
*loop
, chain_p chain
,
1677 if (chain
->combined
)
1679 /* For combined chains, just remove the statements that are used to
1680 compute the values of the expression (except for the root one). */
1681 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1682 remove_stmt (a
->stmt
);
1686 /* For non-combined chains, set up the variables that hold its value,
1687 and replace the uses of the original references by these
1689 initialize_root (loop
, chain
, tmp_vars
);
1690 for (i
= 1; chain
->refs
.iterate (i
, &a
); i
++)
1692 var
= chain
->vars
[chain
->length
- a
->distance
];
1693 replace_ref_with (a
->stmt
, var
, false, false);
1698 /* Determines the unroll factor necessary to remove as many temporary variable
1699 copies as possible. CHAINS is the list of chains that will be
1703 determine_unroll_factor (vec
<chain_p
> chains
)
1706 unsigned factor
= 1, af
, nfactor
, i
;
1707 unsigned max
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1709 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1711 if (chain
->type
== CT_INVARIANT
|| chain
->combined
)
1714 /* The best unroll factor for this chain is equal to the number of
1715 temporary variables that we create for it. */
1717 if (chain
->has_max_use_after
)
1720 nfactor
= factor
* af
/ gcd (factor
, af
);
1728 /* Perform the predictive commoning optimization for CHAINS.
1729 Uids of the newly created temporary variables are marked in TMP_VARS. */
1732 execute_pred_commoning (struct loop
*loop
, vec
<chain_p
> chains
,
1738 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1740 if (chain
->type
== CT_INVARIANT
)
1741 execute_load_motion (loop
, chain
, tmp_vars
);
1743 execute_pred_commoning_chain (loop
, chain
, tmp_vars
);
1746 update_ssa (TODO_update_ssa_only_virtuals
);
1749 /* For each reference in CHAINS, if its defining statement is
1750 phi node, record the ssa name that is defined by it. */
1753 replace_phis_by_defined_names (vec
<chain_p
> chains
)
1759 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1760 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1762 if (gimple_code (a
->stmt
) == GIMPLE_PHI
)
1764 a
->name_defined_by_phi
= PHI_RESULT (a
->stmt
);
1770 /* For each reference in CHAINS, if name_defined_by_phi is not
1771 NULL, use it to set the stmt field. */
1774 replace_names_by_phis (vec
<chain_p
> chains
)
1780 FOR_EACH_VEC_ELT (chains
, i
, chain
)
1781 FOR_EACH_VEC_ELT (chain
->refs
, j
, a
)
1782 if (a
->stmt
== NULL
)
1784 a
->stmt
= SSA_NAME_DEF_STMT (a
->name_defined_by_phi
);
1785 gcc_assert (gimple_code (a
->stmt
) == GIMPLE_PHI
);
1786 a
->name_defined_by_phi
= NULL_TREE
;
1790 /* Wrapper over execute_pred_commoning, to pass it as a callback
1791 to tree_transform_and_unroll_loop. */
1795 vec
<chain_p
> chains
;
1800 execute_pred_commoning_cbck (struct loop
*loop
, void *data
)
1802 struct epcc_data
*const dta
= (struct epcc_data
*) data
;
1804 /* Restore phi nodes that were replaced by ssa names before
1805 tree_transform_and_unroll_loop (see detailed description in
1806 tree_predictive_commoning_loop). */
1807 replace_names_by_phis (dta
->chains
);
1808 execute_pred_commoning (loop
, dta
->chains
, dta
->tmp_vars
);
1811 /* Base NAME and all the names in the chain of phi nodes that use it
1812 on variable VAR. The phi nodes are recognized by being in the copies of
1813 the header of the LOOP. */
1816 base_names_in_chain_on (struct loop
*loop
, tree name
, tree var
)
1819 imm_use_iterator iter
;
1821 replace_ssa_name_symbol (name
, var
);
1826 FOR_EACH_IMM_USE_STMT (stmt
, iter
, name
)
1828 if (gimple_code (stmt
) == GIMPLE_PHI
1829 && flow_bb_inside_loop_p (loop
, gimple_bb (stmt
)))
1832 BREAK_FROM_IMM_USE_STMT (iter
);
1838 name
= PHI_RESULT (phi
);
1839 replace_ssa_name_symbol (name
, var
);
1843 /* Given an unrolled LOOP after predictive commoning, remove the
1844 register copies arising from phi nodes by changing the base
1845 variables of SSA names. TMP_VARS is the set of the temporary variables
1846 for those we want to perform this. */
1849 eliminate_temp_copies (struct loop
*loop
, bitmap tmp_vars
)
1853 tree name
, use
, var
;
1854 gimple_stmt_iterator psi
;
1856 e
= loop_latch_edge (loop
);
1857 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1859 phi
= gsi_stmt (psi
);
1860 name
= PHI_RESULT (phi
);
1861 var
= SSA_NAME_VAR (name
);
1862 if (!var
|| !bitmap_bit_p (tmp_vars
, DECL_UID (var
)))
1864 use
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
1865 gcc_assert (TREE_CODE (use
) == SSA_NAME
);
1867 /* Base all the ssa names in the ud and du chain of NAME on VAR. */
1868 stmt
= SSA_NAME_DEF_STMT (use
);
1869 while (gimple_code (stmt
) == GIMPLE_PHI
1870 /* In case we could not unroll the loop enough to eliminate
1871 all copies, we may reach the loop header before the defining
1872 statement (in that case, some register copies will be present
1873 in loop latch in the final code, corresponding to the newly
1874 created looparound phi nodes). */
1875 && gimple_bb (stmt
) != loop
->header
)
1877 gcc_assert (single_pred_p (gimple_bb (stmt
)));
1878 use
= PHI_ARG_DEF (stmt
, 0);
1879 stmt
= SSA_NAME_DEF_STMT (use
);
1882 base_names_in_chain_on (loop
, use
, var
);
1886 /* Returns true if CHAIN is suitable to be combined. */
1889 chain_can_be_combined_p (chain_p chain
)
1891 return (!chain
->combined
1892 && (chain
->type
== CT_LOAD
|| chain
->type
== CT_COMBINATION
));
1895 /* Returns the modify statement that uses NAME. Skips over assignment
1896 statements, NAME is replaced with the actual name used in the returned
1900 find_use_stmt (tree
*name
)
1905 /* Skip over assignments. */
1908 stmt
= single_nonlooparound_use (*name
);
1912 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
1915 lhs
= gimple_assign_lhs (stmt
);
1916 if (TREE_CODE (lhs
) != SSA_NAME
)
1919 if (gimple_assign_copy_p (stmt
))
1921 rhs
= gimple_assign_rhs1 (stmt
);
1927 else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt
))
1928 == GIMPLE_BINARY_RHS
)
1935 /* Returns true if we may perform reassociation for operation CODE in TYPE. */
1938 may_reassociate_p (tree type
, enum tree_code code
)
1940 if (FLOAT_TYPE_P (type
)
1941 && !flag_unsafe_math_optimizations
)
1944 return (commutative_tree_code (code
)
1945 && associative_tree_code (code
));
1948 /* If the operation used in STMT is associative and commutative, go through the
1949 tree of the same operations and returns its root. Distance to the root
1950 is stored in DISTANCE. */
1953 find_associative_operation_root (gimple stmt
, unsigned *distance
)
1957 enum tree_code code
= gimple_assign_rhs_code (stmt
);
1958 tree type
= TREE_TYPE (gimple_assign_lhs (stmt
));
1961 if (!may_reassociate_p (type
, code
))
1966 lhs
= gimple_assign_lhs (stmt
);
1967 gcc_assert (TREE_CODE (lhs
) == SSA_NAME
);
1969 next
= find_use_stmt (&lhs
);
1971 || gimple_assign_rhs_code (next
) != code
)
1983 /* Returns the common statement in that NAME1 and NAME2 have a use. If there
1984 is no such statement, returns NULL_TREE. In case the operation used on
1985 NAME1 and NAME2 is associative and commutative, returns the root of the
1986 tree formed by this operation instead of the statement that uses NAME1 or
1990 find_common_use_stmt (tree
*name1
, tree
*name2
)
1992 gimple stmt1
, stmt2
;
1994 stmt1
= find_use_stmt (name1
);
1998 stmt2
= find_use_stmt (name2
);
2005 stmt1
= find_associative_operation_root (stmt1
, NULL
);
2008 stmt2
= find_associative_operation_root (stmt2
, NULL
);
2012 return (stmt1
== stmt2
? stmt1
: NULL
);
2015 /* Checks whether R1 and R2 are combined together using CODE, with the result
2016 in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
2017 if it is true. If CODE is ERROR_MARK, set these values instead. */
2020 combinable_refs_p (dref r1
, dref r2
,
2021 enum tree_code
*code
, bool *swap
, tree
*rslt_type
)
2023 enum tree_code acode
;
2029 name1
= name_for_ref (r1
);
2030 name2
= name_for_ref (r2
);
2031 gcc_assert (name1
!= NULL_TREE
&& name2
!= NULL_TREE
);
2033 stmt
= find_common_use_stmt (&name1
, &name2
);
2038 acode
= gimple_assign_rhs_code (stmt
);
2039 aswap
= (!commutative_tree_code (acode
)
2040 && gimple_assign_rhs1 (stmt
) != name1
);
2041 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2043 if (*code
== ERROR_MARK
)
2051 return (*code
== acode
2053 && *rslt_type
== atype
);
2056 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2057 an assignment of the remaining operand. */
2060 remove_name_from_operation (gimple stmt
, tree op
)
2063 gimple_stmt_iterator si
;
2065 gcc_assert (is_gimple_assign (stmt
));
2067 if (gimple_assign_rhs1 (stmt
) == op
)
2068 other_op
= gimple_assign_rhs2 (stmt
);
2070 other_op
= gimple_assign_rhs1 (stmt
);
2072 si
= gsi_for_stmt (stmt
);
2073 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2075 /* We should not have reallocated STMT. */
2076 gcc_assert (gsi_stmt (si
) == stmt
);
2081 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2082 are combined in a single statement, and returns this statement. */
2085 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2087 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2088 gimple new_stmt
, tmp_stmt
;
2089 tree new_name
, tmp_name
, var
, r1
, r2
;
2090 unsigned dist1
, dist2
;
2091 enum tree_code code
;
2092 tree type
= TREE_TYPE (name1
);
2093 gimple_stmt_iterator bsi
;
2095 stmt1
= find_use_stmt (&name1
);
2096 stmt2
= find_use_stmt (&name2
);
2097 root1
= find_associative_operation_root (stmt1
, &dist1
);
2098 root2
= find_associative_operation_root (stmt2
, &dist2
);
2099 code
= gimple_assign_rhs_code (stmt1
);
2101 gcc_assert (root1
&& root2
&& root1
== root2
2102 && code
== gimple_assign_rhs_code (stmt2
));
2104 /* Find the root of the nearest expression in that both NAME1 and NAME2
2111 while (dist1
> dist2
)
2113 s1
= find_use_stmt (&r1
);
2114 r1
= gimple_assign_lhs (s1
);
2117 while (dist2
> dist1
)
2119 s2
= find_use_stmt (&r2
);
2120 r2
= gimple_assign_lhs (s2
);
2126 s1
= find_use_stmt (&r1
);
2127 r1
= gimple_assign_lhs (s1
);
2128 s2
= find_use_stmt (&r2
);
2129 r2
= gimple_assign_lhs (s2
);
2132 /* Remove NAME1 and NAME2 from the statements in that they are used
2134 remove_name_from_operation (stmt1
, name1
);
2135 remove_name_from_operation (stmt2
, name2
);
2137 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2138 combine it with the rhs of S1. */
2139 var
= create_tmp_reg (type
, "predreastmp");
2140 new_name
= make_ssa_name (var
, NULL
);
2141 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2143 var
= create_tmp_reg (type
, "predreastmp");
2144 tmp_name
= make_ssa_name (var
, NULL
);
2146 /* Rhs of S1 may now be either a binary expression with operation
2147 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2148 so that name1 or name2 was removed from it). */
2149 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2151 gimple_assign_rhs1 (s1
),
2152 gimple_assign_rhs2 (s1
));
2154 bsi
= gsi_for_stmt (s1
);
2155 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2156 s1
= gsi_stmt (bsi
);
2159 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2160 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2165 /* Returns the statement that combines references R1 and R2. In case R1
2166 and R2 are not used in the same statement, but they are used with an
2167 associative and commutative operation in the same expression, reassociate
2168 the expression so that they are used in the same statement. */
2171 stmt_combining_refs (dref r1
, dref r2
)
2173 gimple stmt1
, stmt2
;
2174 tree name1
= name_for_ref (r1
);
2175 tree name2
= name_for_ref (r2
);
2177 stmt1
= find_use_stmt (&name1
);
2178 stmt2
= find_use_stmt (&name2
);
2182 return reassociate_to_the_same_stmt (name1
, name2
);
2185 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2186 description of the new chain is returned, otherwise we return NULL. */
2189 combine_chains (chain_p ch1
, chain_p ch2
)
2192 enum tree_code op
= ERROR_MARK
;
2197 tree rslt_type
= NULL_TREE
;
2201 if (ch1
->length
!= ch2
->length
)
2204 if (ch1
->refs
.length () != ch2
->refs
.length ())
2207 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2208 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2210 if (r1
->distance
!= r2
->distance
)
2213 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2224 new_chain
= XCNEW (struct chain
);
2225 new_chain
->type
= CT_COMBINATION
;
2227 new_chain
->ch1
= ch1
;
2228 new_chain
->ch2
= ch2
;
2229 new_chain
->rslt_type
= rslt_type
;
2230 new_chain
->length
= ch1
->length
;
2232 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2233 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2235 nw
= XCNEW (struct dref_d
);
2236 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2237 nw
->distance
= r1
->distance
;
2239 new_chain
->refs
.safe_push (nw
);
2242 new_chain
->has_max_use_after
= false;
2243 root_stmt
= get_chain_root (new_chain
)->stmt
;
2244 for (i
= 1; new_chain
->refs
.iterate (i
, &nw
); i
++)
2246 if (nw
->distance
== new_chain
->length
2247 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2249 new_chain
->has_max_use_after
= true;
2254 ch1
->combined
= true;
2255 ch2
->combined
= true;
2259 /* Try to combine the CHAINS. */
2262 try_combine_chains (vec
<chain_p
> *chains
)
2265 chain_p ch1
, ch2
, cch
;
2266 vec
<chain_p
> worklist
= vNULL
;
2268 FOR_EACH_VEC_ELT (*chains
, i
, ch1
)
2269 if (chain_can_be_combined_p (ch1
))
2270 worklist
.safe_push (ch1
);
2272 while (!worklist
.is_empty ())
2274 ch1
= worklist
.pop ();
2275 if (!chain_can_be_combined_p (ch1
))
2278 FOR_EACH_VEC_ELT (*chains
, j
, ch2
)
2280 if (!chain_can_be_combined_p (ch2
))
2283 cch
= combine_chains (ch1
, ch2
);
2286 worklist
.safe_push (cch
);
2287 chains
->safe_push (cch
);
2293 worklist
.release ();
2296 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2297 impossible because one of these initializers may trap, true otherwise. */
2300 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2302 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2303 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2307 edge entry
= loop_preheader_edge (loop
);
2309 /* Find the initializers for the variables, and check that they cannot
2311 chain
->inits
.create (n
);
2312 for (i
= 0; i
< n
; i
++)
2313 chain
->inits
.quick_push (NULL_TREE
);
2315 /* If we have replaced some looparound phi nodes, use their initializers
2316 instead of creating our own. */
2317 FOR_EACH_VEC_ELT (chain
->refs
, i
, laref
)
2319 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2322 gcc_assert (laref
->distance
> 0);
2323 chain
->inits
[n
- laref
->distance
]
2324 = PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
);
2327 for (i
= 0; i
< n
; i
++)
2329 if (chain
->inits
[i
] != NULL_TREE
)
2332 init
= ref_at_iteration (dr
, (int) i
- n
, &stmts
);
2333 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2337 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2339 chain
->inits
[i
] = init
;
2345 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2346 be used because the initializers might trap. */
2349 prepare_initializers (struct loop
*loop
, vec
<chain_p
> chains
)
2354 for (i
= 0; i
< chains
.length (); )
2357 if (prepare_initializers_chain (loop
, chain
))
2361 release_chain (chain
);
2362 chains
.unordered_remove (i
);
2367 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2371 tree_predictive_commoning_loop (struct loop
*loop
)
2373 vec
<data_reference_p
> datarefs
;
2374 vec
<ddr_p
> dependences
;
2375 struct component
*components
;
2376 vec
<chain_p
> chains
= vNULL
;
2377 unsigned unroll_factor
;
2378 struct tree_niter_desc desc
;
2379 bool unroll
= false;
2383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2384 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2386 /* Find the data references and split them into components according to their
2387 dependence relations. */
2388 stack_vec
<loop_p
, 3> loop_nest
;
2389 dependences
.create (10);
2390 datarefs
.create (10);
2391 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
2394 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2395 fprintf (dump_file
, "Cannot analyze data dependencies\n");
2396 free_data_refs (datarefs
);
2397 free_dependence_relations (dependences
);
2401 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2402 dump_data_dependence_relations (dump_file
, dependences
);
2404 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2405 loop_nest
.release ();
2406 free_dependence_relations (dependences
);
2409 free_data_refs (datarefs
);
2413 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2415 fprintf (dump_file
, "Initial state:\n\n");
2416 dump_components (dump_file
, components
);
2419 /* Find the suitable components and split them into chains. */
2420 components
= filter_suitable_components (loop
, components
);
2422 tmp_vars
= BITMAP_ALLOC (NULL
);
2423 looparound_phis
= BITMAP_ALLOC (NULL
);
2424 determine_roots (loop
, components
, &chains
);
2425 release_components (components
);
2427 if (!chains
.exists ())
2429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2431 "Predictive commoning failed: no suitable chains\n");
2434 prepare_initializers (loop
, chains
);
2436 /* Try to combine the chains that are always worked with together. */
2437 try_combine_chains (&chains
);
2439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2441 fprintf (dump_file
, "Before commoning:\n\n");
2442 dump_chains (dump_file
, chains
);
2445 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2446 that its number of iterations is divisible by the factor. */
2447 unroll_factor
= determine_unroll_factor (chains
);
2449 unroll
= (unroll_factor
> 1
2450 && can_unroll_loop_p (loop
, unroll_factor
, &desc
));
2451 exit
= single_dom_exit (loop
);
2453 /* Execute the predictive commoning transformations, and possibly unroll the
2457 struct epcc_data dta
;
2459 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2460 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2462 dta
.chains
= chains
;
2463 dta
.tmp_vars
= tmp_vars
;
2465 update_ssa (TODO_update_ssa_only_virtuals
);
2467 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2468 execute_pred_commoning_cbck is called may cause phi nodes to be
2469 reallocated, which is a problem since CHAINS may point to these
2470 statements. To fix this, we store the ssa names defined by the
2471 phi nodes here instead of the phi nodes themselves, and restore
2472 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2473 replace_phis_by_defined_names (chains
);
2475 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2476 execute_pred_commoning_cbck
, &dta
);
2477 eliminate_temp_copies (loop
, tmp_vars
);
2481 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2483 "Executing predictive commoning without unrolling.\n");
2484 execute_pred_commoning (loop
, chains
, tmp_vars
);
2488 release_chains (chains
);
2489 free_data_refs (datarefs
);
2490 BITMAP_FREE (tmp_vars
);
2491 BITMAP_FREE (looparound_phis
);
2493 free_affine_expand_cache (&name_expansions
);
2498 /* Runs predictive commoning. */
2501 tree_predictive_commoning (void)
2503 bool unrolled
= false;
2508 initialize_original_copy_tables ();
2509 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
2510 if (optimize_loop_for_speed_p (loop
))
2512 unrolled
|= tree_predictive_commoning_loop (loop
);
2518 ret
= TODO_cleanup_cfg
;
2520 free_original_copy_tables ();
2525 /* Predictive commoning Pass. */
2528 run_tree_predictive_commoning (void)
2533 return tree_predictive_commoning ();
2537 gate_tree_predictive_commoning (void)
2539 return flag_predictive_commoning
!= 0;
2544 const pass_data pass_data_predcom
=
2546 GIMPLE_PASS
, /* type */
2548 OPTGROUP_LOOP
, /* optinfo_flags */
2549 true, /* has_gate */
2550 true, /* has_execute */
2551 TV_PREDCOM
, /* tv_id */
2552 PROP_cfg
, /* properties_required */
2553 0, /* properties_provided */
2554 0, /* properties_destroyed */
2555 0, /* todo_flags_start */
2556 TODO_update_ssa_only_virtuals
, /* todo_flags_finish */
2559 class pass_predcom
: public gimple_opt_pass
2562 pass_predcom (gcc::context
*ctxt
)
2563 : gimple_opt_pass (pass_data_predcom
, ctxt
)
2566 /* opt_pass methods: */
2567 bool gate () { return gate_tree_predictive_commoning (); }
2568 unsigned int execute () { return run_tree_predictive_commoning (); }
2570 }; // class pass_predcom
2575 make_pass_predcom (gcc::context
*ctxt
)
2577 return new pass_predcom (ctxt
);