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 "tree-ssanames.h"
202 #include "tree-ssa-loop-ivopts.h"
203 #include "tree-ssa-loop-manip.h"
204 #include "tree-ssa-loop-niter.h"
205 #include "tree-ssa-loop.h"
206 #include "tree-into-ssa.h"
207 #include "tree-dfa.h"
208 #include "tree-ssa.h"
210 #include "tree-data-ref.h"
211 #include "tree-scalar-evolution.h"
212 #include "tree-chrec.h"
214 #include "gimple-pretty-print.h"
215 #include "tree-pass.h"
216 #include "tree-affine.h"
217 #include "tree-inline.h"
219 /* The maximum number of iterations between the considered memory
222 #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
224 /* Data references (or phi nodes that carry data reference values across
227 typedef struct dref_d
229 /* The reference itself. */
230 struct data_reference
*ref
;
232 /* The statement in that the reference appears. */
235 /* In case that STMT is a phi node, this field is set to the SSA name
236 defined by it in replace_phis_by_defined_names (in order to avoid
237 pointing to phi node that got reallocated in the meantime). */
238 tree name_defined_by_phi
;
240 /* Distance of the reference from the root of the chain (in number of
241 iterations of the loop). */
244 /* Number of iterations offset from the first reference in the component. */
247 /* Number of the reference in a component, in dominance ordering. */
250 /* True if the memory reference is always accessed when the loop is
252 unsigned always_accessed
: 1;
256 /* Type of the chain of the references. */
260 /* The addresses of the references in the chain are constant. */
263 /* There are only loads in the chain. */
266 /* Root of the chain is store, the rest are loads. */
269 /* A combination of two chains. */
273 /* Chains of data references. */
277 /* Type of the chain. */
278 enum chain_type type
;
280 /* For combination chains, the operator and the two chains that are
281 combined, and the type of the result. */
284 struct chain
*ch1
, *ch2
;
286 /* The references in the chain. */
289 /* The maximum distance of the reference in the chain from the root. */
292 /* The variables used to copy the value throughout iterations. */
295 /* Initializers for the variables. */
298 /* True if there is a use of a variable with the maximal distance
299 that comes after the root in the loop. */
300 unsigned has_max_use_after
: 1;
302 /* True if all the memory references in the chain are always accessed. */
303 unsigned all_always_accessed
: 1;
305 /* True if this chain was combined together with some other chain. */
306 unsigned combined
: 1;
310 /* Describes the knowledge about the step of the memory references in
315 /* The step is zero. */
318 /* The step is nonzero. */
321 /* The step may or may not be nonzero. */
325 /* Components of the data dependence graph. */
329 /* The references in the component. */
332 /* What we know about the step of the references in the component. */
333 enum ref_step_type comp_step
;
335 /* Next component in the list. */
336 struct component
*next
;
339 /* Bitmap of ssa names defined by looparound phi nodes covered by chains. */
341 static bitmap looparound_phis
;
343 /* Cache used by tree_to_aff_combination_expand. */
345 static struct pointer_map_t
*name_expansions
;
347 /* Dumps data reference REF to FILE. */
349 extern void dump_dref (FILE *, dref
);
351 dump_dref (FILE *file
, dref ref
)
356 print_generic_expr (file
, DR_REF (ref
->ref
), TDF_SLIM
);
357 fprintf (file
, " (id %u%s)\n", ref
->pos
,
358 DR_IS_READ (ref
->ref
) ? "" : ", write");
360 fprintf (file
, " offset ");
361 dump_double_int (file
, ref
->offset
, false);
362 fprintf (file
, "\n");
364 fprintf (file
, " distance %u\n", ref
->distance
);
368 if (gimple_code (ref
->stmt
) == GIMPLE_PHI
)
369 fprintf (file
, " looparound ref\n");
371 fprintf (file
, " combination ref\n");
372 fprintf (file
, " in statement ");
373 print_gimple_stmt (file
, ref
->stmt
, 0, TDF_SLIM
);
374 fprintf (file
, "\n");
375 fprintf (file
, " distance %u\n", ref
->distance
);
380 /* Dumps CHAIN to FILE. */
382 extern void dump_chain (FILE *, chain_p
);
384 dump_chain (FILE *file
, chain_p chain
)
387 const char *chain_type
;
394 chain_type
= "Load motion";
398 chain_type
= "Loads-only";
402 chain_type
= "Store-loads";
406 chain_type
= "Combination";
413 fprintf (file
, "%s chain %p%s\n", chain_type
, (void *) chain
,
414 chain
->combined
? " (combined)" : "");
415 if (chain
->type
!= CT_INVARIANT
)
416 fprintf (file
, " max distance %u%s\n", chain
->length
,
417 chain
->has_max_use_after
? "" : ", may reuse first");
419 if (chain
->type
== CT_COMBINATION
)
421 fprintf (file
, " equal to %p %s %p in type ",
422 (void *) chain
->ch1
, op_symbol_code (chain
->op
),
423 (void *) chain
->ch2
);
424 print_generic_expr (file
, chain
->rslt_type
, TDF_SLIM
);
425 fprintf (file
, "\n");
428 if (chain
->vars
.exists ())
430 fprintf (file
, " vars");
431 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
434 print_generic_expr (file
, var
, TDF_SLIM
);
436 fprintf (file
, "\n");
439 if (chain
->inits
.exists ())
441 fprintf (file
, " inits");
442 FOR_EACH_VEC_ELT (chain
->inits
, i
, var
)
445 print_generic_expr (file
, var
, TDF_SLIM
);
447 fprintf (file
, "\n");
450 fprintf (file
, " references:\n");
451 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
454 fprintf (file
, "\n");
457 /* Dumps CHAINS to FILE. */
459 extern void dump_chains (FILE *, vec
<chain_p
> );
461 dump_chains (FILE *file
, vec
<chain_p
> chains
)
466 FOR_EACH_VEC_ELT (chains
, i
, chain
)
467 dump_chain (file
, chain
);
470 /* Dumps COMP to FILE. */
472 extern void dump_component (FILE *, struct component
*);
474 dump_component (FILE *file
, struct component
*comp
)
479 fprintf (file
, "Component%s:\n",
480 comp
->comp_step
== RS_INVARIANT
? " (invariant)" : "");
481 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
483 fprintf (file
, "\n");
486 /* Dumps COMPS to FILE. */
488 extern void dump_components (FILE *, struct component
*);
490 dump_components (FILE *file
, struct component
*comps
)
492 struct component
*comp
;
494 for (comp
= comps
; comp
; comp
= comp
->next
)
495 dump_component (file
, comp
);
498 /* Frees a chain CHAIN. */
501 release_chain (chain_p chain
)
509 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
512 chain
->refs
.release ();
513 chain
->vars
.release ();
514 chain
->inits
.release ();
522 release_chains (vec
<chain_p
> chains
)
527 FOR_EACH_VEC_ELT (chains
, i
, chain
)
528 release_chain (chain
);
532 /* Frees a component COMP. */
535 release_component (struct component
*comp
)
537 comp
->refs
.release ();
541 /* Frees list of components COMPS. */
544 release_components (struct component
*comps
)
546 struct component
*act
, *next
;
548 for (act
= comps
; act
; act
= next
)
551 release_component (act
);
555 /* Finds a root of tree given by FATHERS containing A, and performs path
559 component_of (unsigned fathers
[], unsigned a
)
563 for (root
= a
; root
!= fathers
[root
]; root
= fathers
[root
])
566 for (; a
!= root
; a
= n
)
575 /* Join operation for DFU. FATHERS gives the tree, SIZES are sizes of the
576 components, A and B are components to merge. */
579 merge_comps (unsigned fathers
[], unsigned sizes
[], unsigned a
, unsigned b
)
581 unsigned ca
= component_of (fathers
, a
);
582 unsigned cb
= component_of (fathers
, b
);
587 if (sizes
[ca
] < sizes
[cb
])
589 sizes
[cb
] += sizes
[ca
];
594 sizes
[ca
] += sizes
[cb
];
599 /* Returns true if A is a reference that is suitable for predictive commoning
600 in the innermost loop that contains it. REF_STEP is set according to the
601 step of the reference A. */
604 suitable_reference_p (struct data_reference
*a
, enum ref_step_type
*ref_step
)
606 tree ref
= DR_REF (a
), step
= DR_STEP (a
);
609 || TREE_THIS_VOLATILE (ref
)
610 || !is_gimple_reg_type (TREE_TYPE (ref
))
611 || tree_could_throw_p (ref
))
614 if (integer_zerop (step
))
615 *ref_step
= RS_INVARIANT
;
616 else if (integer_nonzerop (step
))
617 *ref_step
= RS_NONZERO
;
624 /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET. */
627 aff_combination_dr_offset (struct data_reference
*dr
, aff_tree
*offset
)
629 tree type
= TREE_TYPE (DR_OFFSET (dr
));
632 tree_to_aff_combination_expand (DR_OFFSET (dr
), type
, offset
,
634 aff_combination_const (&delta
, type
, tree_to_double_int (DR_INIT (dr
)));
635 aff_combination_add (offset
, &delta
);
638 /* Determines number of iterations of the innermost enclosing loop before B
639 refers to exactly the same location as A and stores it to OFF. If A and
640 B do not have the same step, they never meet, or anything else fails,
641 returns false, otherwise returns true. Both A and B are assumed to
642 satisfy suitable_reference_p. */
645 determine_offset (struct data_reference
*a
, struct data_reference
*b
,
648 aff_tree diff
, baseb
, step
;
651 /* Check that both the references access the location in the same type. */
652 typea
= TREE_TYPE (DR_REF (a
));
653 typeb
= TREE_TYPE (DR_REF (b
));
654 if (!useless_type_conversion_p (typeb
, typea
))
657 /* Check whether the base address and the step of both references is the
659 if (!operand_equal_p (DR_STEP (a
), DR_STEP (b
), 0)
660 || !operand_equal_p (DR_BASE_ADDRESS (a
), DR_BASE_ADDRESS (b
), 0))
663 if (integer_zerop (DR_STEP (a
)))
665 /* If the references have loop invariant address, check that they access
666 exactly the same location. */
667 *off
= double_int_zero
;
668 return (operand_equal_p (DR_OFFSET (a
), DR_OFFSET (b
), 0)
669 && operand_equal_p (DR_INIT (a
), DR_INIT (b
), 0));
672 /* Compare the offsets of the addresses, and check whether the difference
673 is a multiple of step. */
674 aff_combination_dr_offset (a
, &diff
);
675 aff_combination_dr_offset (b
, &baseb
);
676 aff_combination_scale (&baseb
, double_int_minus_one
);
677 aff_combination_add (&diff
, &baseb
);
679 tree_to_aff_combination_expand (DR_STEP (a
), TREE_TYPE (DR_STEP (a
)),
680 &step
, &name_expansions
);
681 return aff_combination_constant_multiple_p (&diff
, &step
, off
);
684 /* Returns the last basic block in LOOP for that we are sure that
685 it is executed whenever the loop is entered. */
688 last_always_executed_block (struct loop
*loop
)
691 vec
<edge
> exits
= get_loop_exit_edges (loop
);
693 basic_block last
= loop
->latch
;
695 FOR_EACH_VEC_ELT (exits
, i
, ex
)
696 last
= nearest_common_dominator (CDI_DOMINATORS
, last
, ex
->src
);
702 /* Splits dependence graph on DATAREFS described by DEPENDS to components. */
704 static struct component
*
705 split_data_refs_to_components (struct loop
*loop
,
706 vec
<data_reference_p
> datarefs
,
709 unsigned i
, n
= datarefs
.length ();
710 unsigned ca
, ia
, ib
, bad
;
711 unsigned *comp_father
= XNEWVEC (unsigned, n
+ 1);
712 unsigned *comp_size
= XNEWVEC (unsigned, n
+ 1);
713 struct component
**comps
;
714 struct data_reference
*dr
, *dra
, *drb
;
715 struct data_dependence_relation
*ddr
;
716 struct component
*comp_list
= NULL
, *comp
;
718 basic_block last_always_executed
= last_always_executed_block (loop
);
720 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
724 /* A fake reference for call or asm_expr that may clobber memory;
728 dr
->aux
= (void *) (size_t) i
;
733 /* A component reserved for the "bad" data references. */
737 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
739 enum ref_step_type dummy
;
741 if (!suitable_reference_p (dr
, &dummy
))
743 ia
= (unsigned) (size_t) dr
->aux
;
744 merge_comps (comp_father
, comp_size
, n
, ia
);
748 FOR_EACH_VEC_ELT (depends
, i
, ddr
)
750 double_int dummy_off
;
752 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
757 ia
= component_of (comp_father
, (unsigned) (size_t) dra
->aux
);
758 ib
= component_of (comp_father
, (unsigned) (size_t) drb
->aux
);
762 bad
= component_of (comp_father
, n
);
764 /* If both A and B are reads, we may ignore unsuitable dependences. */
765 if (DR_IS_READ (dra
) && DR_IS_READ (drb
)
766 && (ia
== bad
|| ib
== bad
767 || !determine_offset (dra
, drb
, &dummy_off
)))
770 merge_comps (comp_father
, comp_size
, ia
, ib
);
773 comps
= XCNEWVEC (struct component
*, n
);
774 bad
= component_of (comp_father
, n
);
775 FOR_EACH_VEC_ELT (datarefs
, i
, dr
)
777 ia
= (unsigned) (size_t) dr
->aux
;
778 ca
= component_of (comp_father
, ia
);
785 comp
= XCNEW (struct component
);
786 comp
->refs
.create (comp_size
[ca
]);
790 dataref
= XCNEW (struct dref_d
);
792 dataref
->stmt
= DR_STMT (dr
);
793 dataref
->offset
= double_int_zero
;
794 dataref
->distance
= 0;
796 dataref
->always_accessed
797 = dominated_by_p (CDI_DOMINATORS
, last_always_executed
,
798 gimple_bb (dataref
->stmt
));
799 dataref
->pos
= comp
->refs
.length ();
800 comp
->refs
.quick_push (dataref
);
803 for (i
= 0; i
< n
; i
++)
808 comp
->next
= comp_list
;
820 /* Returns true if the component COMP satisfies the conditions
821 described in 2) at the beginning of this file. LOOP is the current
825 suitable_component_p (struct loop
*loop
, struct component
*comp
)
829 basic_block ba
, bp
= loop
->header
;
830 bool ok
, has_write
= false;
832 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
834 ba
= gimple_bb (a
->stmt
);
836 if (!just_once_each_iteration_p (loop
, ba
))
839 gcc_assert (dominated_by_p (CDI_DOMINATORS
, ba
, bp
));
842 if (DR_IS_WRITE (a
->ref
))
846 first
= comp
->refs
[0];
847 ok
= suitable_reference_p (first
->ref
, &comp
->comp_step
);
849 first
->offset
= double_int_zero
;
851 for (i
= 1; comp
->refs
.iterate (i
, &a
); i
++)
853 if (!determine_offset (first
->ref
, a
->ref
, &a
->offset
))
856 #ifdef ENABLE_CHECKING
858 enum ref_step_type a_step
;
859 ok
= suitable_reference_p (a
->ref
, &a_step
);
860 gcc_assert (ok
&& a_step
== comp
->comp_step
);
865 /* If there is a write inside the component, we must know whether the
866 step is nonzero or not -- we would not otherwise be able to recognize
867 whether the value accessed by reads comes from the OFFSET-th iteration
868 or the previous one. */
869 if (has_write
&& comp
->comp_step
== RS_ANY
)
875 /* Check the conditions on references inside each of components COMPS,
876 and remove the unsuitable components from the list. The new list
877 of components is returned. The conditions are described in 2) at
878 the beginning of this file. LOOP is the current loop. */
880 static struct component
*
881 filter_suitable_components (struct loop
*loop
, struct component
*comps
)
883 struct component
**comp
, *act
;
885 for (comp
= &comps
; *comp
; )
888 if (suitable_component_p (loop
, act
))
896 FOR_EACH_VEC_ELT (act
->refs
, i
, ref
)
898 release_component (act
);
905 /* Compares two drefs A and B by their offset and position. Callback for
909 order_drefs (const void *a
, const void *b
)
911 const dref
*const da
= (const dref
*) a
;
912 const dref
*const db
= (const dref
*) b
;
913 int offcmp
= (*da
)->offset
.scmp ((*db
)->offset
);
918 return (*da
)->pos
- (*db
)->pos
;
921 /* Returns root of the CHAIN. */
924 get_chain_root (chain_p chain
)
926 return chain
->refs
[0];
929 /* Adds REF to the chain CHAIN. */
932 add_ref_to_chain (chain_p chain
, dref ref
)
934 dref root
= get_chain_root (chain
);
937 gcc_assert (root
->offset
.sle (ref
->offset
));
938 dist
= ref
->offset
- root
->offset
;
939 if (double_int::from_uhwi (MAX_DISTANCE
).ule (dist
))
944 gcc_assert (dist
.fits_uhwi ());
946 chain
->refs
.safe_push (ref
);
948 ref
->distance
= dist
.to_uhwi ();
950 if (ref
->distance
>= chain
->length
)
952 chain
->length
= ref
->distance
;
953 chain
->has_max_use_after
= false;
956 if (ref
->distance
== chain
->length
957 && ref
->pos
> root
->pos
)
958 chain
->has_max_use_after
= true;
960 chain
->all_always_accessed
&= ref
->always_accessed
;
963 /* Returns the chain for invariant component COMP. */
966 make_invariant_chain (struct component
*comp
)
968 chain_p chain
= XCNEW (struct chain
);
972 chain
->type
= CT_INVARIANT
;
974 chain
->all_always_accessed
= true;
976 FOR_EACH_VEC_ELT (comp
->refs
, i
, ref
)
978 chain
->refs
.safe_push (ref
);
979 chain
->all_always_accessed
&= ref
->always_accessed
;
985 /* Make a new chain rooted at REF. */
988 make_rooted_chain (dref ref
)
990 chain_p chain
= XCNEW (struct chain
);
992 chain
->type
= DR_IS_READ (ref
->ref
) ? CT_LOAD
: CT_STORE_LOAD
;
994 chain
->refs
.safe_push (ref
);
995 chain
->all_always_accessed
= ref
->always_accessed
;
1002 /* Returns true if CHAIN is not trivial. */
1005 nontrivial_chain_p (chain_p chain
)
1007 return chain
!= NULL
&& chain
->refs
.length () > 1;
1010 /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
1014 name_for_ref (dref ref
)
1018 if (is_gimple_assign (ref
->stmt
))
1020 if (!ref
->ref
|| DR_IS_READ (ref
->ref
))
1021 name
= gimple_assign_lhs (ref
->stmt
);
1023 name
= gimple_assign_rhs1 (ref
->stmt
);
1026 name
= PHI_RESULT (ref
->stmt
);
1028 return (TREE_CODE (name
) == SSA_NAME
? name
: NULL_TREE
);
1031 /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
1032 iterations of the innermost enclosing loop). */
1035 valid_initializer_p (struct data_reference
*ref
,
1036 unsigned distance
, struct data_reference
*root
)
1038 aff_tree diff
, base
, step
;
1041 /* Both REF and ROOT must be accessing the same object. */
1042 if (!operand_equal_p (DR_BASE_ADDRESS (ref
), DR_BASE_ADDRESS (root
), 0))
1045 /* The initializer is defined outside of loop, hence its address must be
1046 invariant inside the loop. */
1047 gcc_assert (integer_zerop (DR_STEP (ref
)));
1049 /* If the address of the reference is invariant, initializer must access
1050 exactly the same location. */
1051 if (integer_zerop (DR_STEP (root
)))
1052 return (operand_equal_p (DR_OFFSET (ref
), DR_OFFSET (root
), 0)
1053 && operand_equal_p (DR_INIT (ref
), DR_INIT (root
), 0));
1055 /* Verify that this index of REF is equal to the root's index at
1056 -DISTANCE-th iteration. */
1057 aff_combination_dr_offset (root
, &diff
);
1058 aff_combination_dr_offset (ref
, &base
);
1059 aff_combination_scale (&base
, double_int_minus_one
);
1060 aff_combination_add (&diff
, &base
);
1062 tree_to_aff_combination_expand (DR_STEP (root
), TREE_TYPE (DR_STEP (root
)),
1063 &step
, &name_expansions
);
1064 if (!aff_combination_constant_multiple_p (&diff
, &step
, &off
))
1067 if (off
!= double_int::from_uhwi (distance
))
1073 /* Finds looparound phi node of LOOP that copies the value of REF, and if its
1074 initial value is correct (equal to initial value of REF shifted by one
1075 iteration), returns the phi node. Otherwise, NULL_TREE is returned. ROOT
1076 is the root of the current chain. */
1079 find_looparound_phi (struct loop
*loop
, dref ref
, dref root
)
1081 tree name
, init
, init_ref
;
1082 gimple phi
= NULL
, init_stmt
;
1083 edge latch
= loop_latch_edge (loop
);
1084 struct data_reference init_dr
;
1085 gimple_stmt_iterator psi
;
1087 if (is_gimple_assign (ref
->stmt
))
1089 if (DR_IS_READ (ref
->ref
))
1090 name
= gimple_assign_lhs (ref
->stmt
);
1092 name
= gimple_assign_rhs1 (ref
->stmt
);
1095 name
= PHI_RESULT (ref
->stmt
);
1099 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
1101 phi
= gsi_stmt (psi
);
1102 if (PHI_ARG_DEF_FROM_EDGE (phi
, latch
) == name
)
1106 if (gsi_end_p (psi
))
1109 init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1110 if (TREE_CODE (init
) != SSA_NAME
)
1112 init_stmt
= SSA_NAME_DEF_STMT (init
);
1113 if (gimple_code (init_stmt
) != GIMPLE_ASSIGN
)
1115 gcc_assert (gimple_assign_lhs (init_stmt
) == init
);
1117 init_ref
= gimple_assign_rhs1 (init_stmt
);
1118 if (!REFERENCE_CLASS_P (init_ref
)
1119 && !DECL_P (init_ref
))
1122 /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
1123 loop enclosing PHI). */
1124 memset (&init_dr
, 0, sizeof (struct data_reference
));
1125 DR_REF (&init_dr
) = init_ref
;
1126 DR_STMT (&init_dr
) = phi
;
1127 if (!dr_analyze_innermost (&init_dr
, loop
))
1130 if (!valid_initializer_p (&init_dr
, ref
->distance
+ 1, root
->ref
))
1136 /* Adds a reference for the looparound copy of REF in PHI to CHAIN. */
1139 insert_looparound_copy (chain_p chain
, dref ref
, gimple phi
)
1141 dref nw
= XCNEW (struct dref_d
), aref
;
1145 nw
->distance
= ref
->distance
+ 1;
1146 nw
->always_accessed
= 1;
1148 FOR_EACH_VEC_ELT (chain
->refs
, i
, aref
)
1149 if (aref
->distance
>= nw
->distance
)
1151 chain
->refs
.safe_insert (i
, nw
);
1153 if (nw
->distance
> chain
->length
)
1155 chain
->length
= nw
->distance
;
1156 chain
->has_max_use_after
= false;
1160 /* For references in CHAIN that are copied around the LOOP (created previously
1161 by PRE, or by user), add the results of such copies to the chain. This
1162 enables us to remove the copies by unrolling, and may need less registers
1163 (also, it may allow us to combine chains together). */
1166 add_looparound_copies (struct loop
*loop
, chain_p chain
)
1169 dref ref
, root
= get_chain_root (chain
);
1172 FOR_EACH_VEC_ELT (chain
->refs
, i
, ref
)
1174 phi
= find_looparound_phi (loop
, ref
, root
);
1178 bitmap_set_bit (looparound_phis
, SSA_NAME_VERSION (PHI_RESULT (phi
)));
1179 insert_looparound_copy (chain
, ref
, phi
);
1183 /* Find roots of the values and determine distances in the component COMP.
1184 The references are redistributed into CHAINS. LOOP is the current
1188 determine_roots_comp (struct loop
*loop
,
1189 struct component
*comp
,
1190 vec
<chain_p
> *chains
)
1194 chain_p chain
= NULL
;
1195 double_int last_ofs
= double_int_zero
;
1197 /* Invariants are handled specially. */
1198 if (comp
->comp_step
== RS_INVARIANT
)
1200 chain
= make_invariant_chain (comp
);
1201 chains
->safe_push (chain
);
1205 comp
->refs
.qsort (order_drefs
);
1207 FOR_EACH_VEC_ELT (comp
->refs
, i
, a
)
1209 if (!chain
|| DR_IS_WRITE (a
->ref
)
1210 || double_int::from_uhwi (MAX_DISTANCE
).ule (a
->offset
- last_ofs
))
1212 if (nontrivial_chain_p (chain
))
1214 add_looparound_copies (loop
, chain
);
1215 chains
->safe_push (chain
);
1218 release_chain (chain
);
1219 chain
= make_rooted_chain (a
);
1220 last_ofs
= a
->offset
;
1224 add_ref_to_chain (chain
, a
);
1227 if (nontrivial_chain_p (chain
))
1229 add_looparound_copies (loop
, chain
);
1230 chains
->safe_push (chain
);
1233 release_chain (chain
);
1236 /* Find roots of the values and determine distances in components COMPS, and
1237 separates the references to CHAINS. LOOP is the current loop. */
1240 determine_roots (struct loop
*loop
,
1241 struct component
*comps
, vec
<chain_p
> *chains
)
1243 struct component
*comp
;
1245 for (comp
= comps
; comp
; comp
= comp
->next
)
1246 determine_roots_comp (loop
, comp
, chains
);
1249 /* Replace the reference in statement STMT with temporary variable
1250 NEW_TREE. If SET is true, NEW_TREE is instead initialized to the value of
1251 the reference in the statement. IN_LHS is true if the reference
1252 is in the lhs of STMT, false if it is in rhs. */
1255 replace_ref_with (gimple stmt
, tree new_tree
, bool set
, bool in_lhs
)
1259 gimple_stmt_iterator bsi
, psi
;
1261 if (gimple_code (stmt
) == GIMPLE_PHI
)
1263 gcc_assert (!in_lhs
&& !set
);
1265 val
= PHI_RESULT (stmt
);
1266 bsi
= gsi_after_labels (gimple_bb (stmt
));
1267 psi
= gsi_for_stmt (stmt
);
1268 remove_phi_node (&psi
, false);
1270 /* Turn the phi node into GIMPLE_ASSIGN. */
1271 new_stmt
= gimple_build_assign (val
, new_tree
);
1272 gsi_insert_before (&bsi
, new_stmt
, GSI_NEW_STMT
);
1276 /* Since the reference is of gimple_reg type, it should only
1277 appear as lhs or rhs of modify statement. */
1278 gcc_assert (is_gimple_assign (stmt
));
1280 bsi
= gsi_for_stmt (stmt
);
1282 /* If we do not need to initialize NEW_TREE, just replace the use of OLD. */
1285 gcc_assert (!in_lhs
);
1286 gimple_assign_set_rhs_from_tree (&bsi
, new_tree
);
1287 stmt
= gsi_stmt (bsi
);
1294 /* We have statement
1298 If OLD is a memory reference, then VAL is gimple_val, and we transform
1304 Otherwise, we are replacing a combination chain,
1305 VAL is the expression that performs the combination, and OLD is an
1306 SSA name. In this case, we transform the assignment to
1313 val
= gimple_assign_lhs (stmt
);
1314 if (TREE_CODE (val
) != SSA_NAME
)
1316 val
= gimple_assign_rhs1 (stmt
);
1317 gcc_assert (gimple_assign_single_p (stmt
));
1318 if (TREE_CLOBBER_P (val
))
1319 val
= get_or_create_ssa_default_def (cfun
, SSA_NAME_VAR (new_tree
));
1321 gcc_assert (gimple_assign_copy_p (stmt
));
1333 val
= gimple_assign_lhs (stmt
);
1336 new_stmt
= gimple_build_assign (new_tree
, unshare_expr (val
));
1337 gsi_insert_after (&bsi
, new_stmt
, GSI_NEW_STMT
);
1340 /* Returns a memory reference to DR in the ITER-th iteration of
1341 the loop it was analyzed in. Append init stmts to STMTS. */
1344 ref_at_iteration (data_reference_p dr
, int iter
, gimple_seq
*stmts
)
1346 tree off
= DR_OFFSET (dr
);
1347 tree coff
= DR_INIT (dr
);
1350 else if (TREE_CODE (DR_STEP (dr
)) == INTEGER_CST
)
1351 coff
= size_binop (PLUS_EXPR
, coff
,
1352 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1354 off
= size_binop (PLUS_EXPR
, off
,
1355 size_binop (MULT_EXPR
, DR_STEP (dr
), ssize_int (iter
)));
1356 tree addr
= fold_build_pointer_plus (DR_BASE_ADDRESS (dr
), off
);
1357 addr
= force_gimple_operand_1 (addr
, stmts
, is_gimple_mem_ref_addr
,
1359 tree alias_ptr
= fold_convert (reference_alias_ptr_type (DR_REF (dr
)), coff
);
1360 /* While data-ref analysis punts on bit offsets it still handles
1361 bitfield accesses at byte boundaries. Cope with that. Note that
1362 we cannot simply re-apply the outer COMPONENT_REF because the
1363 byte-granular portion of it is already applied via DR_INIT and
1364 DR_OFFSET, so simply build a BIT_FIELD_REF knowing that the bits
1365 start at offset zero. */
1366 if (TREE_CODE (DR_REF (dr
)) == COMPONENT_REF
1367 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (dr
), 1)))
1369 tree field
= TREE_OPERAND (DR_REF (dr
), 1);
1370 return build3 (BIT_FIELD_REF
, TREE_TYPE (DR_REF (dr
)),
1371 build2 (MEM_REF
, DECL_BIT_FIELD_TYPE (field
),
1373 DECL_SIZE (field
), bitsize_zero_node
);
1376 return fold_build2 (MEM_REF
, TREE_TYPE (DR_REF (dr
)), addr
, alias_ptr
);
1379 /* Get the initialization expression for the INDEX-th temporary variable
1383 get_init_expr (chain_p chain
, unsigned index
)
1385 if (chain
->type
== CT_COMBINATION
)
1387 tree e1
= get_init_expr (chain
->ch1
, index
);
1388 tree e2
= get_init_expr (chain
->ch2
, index
);
1390 return fold_build2 (chain
->op
, chain
->rslt_type
, e1
, e2
);
1393 return chain
->inits
[index
];
1396 /* Returns a new temporary variable used for the I-th variable carrying
1397 value of REF. The variable's uid is marked in TMP_VARS. */
1400 predcom_tmp_var (tree ref
, unsigned i
, bitmap tmp_vars
)
1402 tree type
= TREE_TYPE (ref
);
1403 /* We never access the components of the temporary variable in predictive
1405 tree var
= create_tmp_reg (type
, get_lsm_tmp_name (ref
, i
));
1406 bitmap_set_bit (tmp_vars
, DECL_UID (var
));
1410 /* Creates the variables for CHAIN, as well as phi nodes for them and
1411 initialization on entry to LOOP. Uids of the newly created
1412 temporary variables are marked in TMP_VARS. */
1415 initialize_root_vars (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1418 unsigned n
= chain
->length
;
1419 dref root
= get_chain_root (chain
);
1420 bool reuse_first
= !chain
->has_max_use_after
;
1421 tree ref
, init
, var
, next
;
1424 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1426 /* If N == 0, then all the references are within the single iteration. And
1427 since this is an nonempty chain, reuse_first cannot be true. */
1428 gcc_assert (n
> 0 || !reuse_first
);
1430 chain
->vars
.create (n
+ 1);
1432 if (chain
->type
== CT_COMBINATION
)
1433 ref
= gimple_assign_lhs (root
->stmt
);
1435 ref
= DR_REF (root
->ref
);
1437 for (i
= 0; i
< n
+ (reuse_first
? 0 : 1); i
++)
1439 var
= predcom_tmp_var (ref
, i
, tmp_vars
);
1440 chain
->vars
.quick_push (var
);
1443 chain
->vars
.quick_push (chain
->vars
[0]);
1445 FOR_EACH_VEC_ELT (chain
->vars
, i
, var
)
1446 chain
->vars
[i
] = make_ssa_name (var
, NULL
);
1448 for (i
= 0; i
< n
; i
++)
1450 var
= chain
->vars
[i
];
1451 next
= chain
->vars
[i
+ 1];
1452 init
= get_init_expr (chain
, i
);
1454 init
= force_gimple_operand (init
, &stmts
, true, NULL_TREE
);
1456 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1458 phi
= create_phi_node (var
, loop
->header
);
1459 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1460 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1464 /* Create the variables and initialization statement for root of chain
1465 CHAIN. Uids of the newly created temporary variables are marked
1469 initialize_root (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1471 dref root
= get_chain_root (chain
);
1472 bool in_lhs
= (chain
->type
== CT_STORE_LOAD
1473 || chain
->type
== CT_COMBINATION
);
1475 initialize_root_vars (loop
, chain
, tmp_vars
);
1476 replace_ref_with (root
->stmt
,
1477 chain
->vars
[chain
->length
],
1481 /* Initializes a variable for load motion for ROOT and prepares phi nodes and
1482 initialization on entry to LOOP if necessary. The ssa name for the variable
1483 is stored in VARS. If WRITTEN is true, also a phi node to copy its value
1484 around the loop is created. Uid of the newly created temporary variable
1485 is marked in TMP_VARS. INITS is the list containing the (single)
1489 initialize_root_vars_lm (struct loop
*loop
, dref root
, bool written
,
1490 vec
<tree
> *vars
, vec
<tree
> inits
,
1494 tree ref
= DR_REF (root
->ref
), init
, var
, next
;
1497 edge entry
= loop_preheader_edge (loop
), latch
= loop_latch_edge (loop
);
1499 /* Find the initializer for the variable, and check that it cannot
1503 vars
->create (written
? 2 : 1);
1504 var
= predcom_tmp_var (ref
, 0, tmp_vars
);
1505 vars
->quick_push (var
);
1507 vars
->quick_push ((*vars
)[0]);
1509 FOR_EACH_VEC_ELT (*vars
, i
, var
)
1510 (*vars
)[i
] = make_ssa_name (var
, NULL
);
1514 init
= force_gimple_operand (init
, &stmts
, written
, NULL_TREE
);
1516 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
1521 phi
= create_phi_node (var
, loop
->header
);
1522 add_phi_arg (phi
, init
, entry
, UNKNOWN_LOCATION
);
1523 add_phi_arg (phi
, next
, latch
, UNKNOWN_LOCATION
);
1527 gimple init_stmt
= gimple_build_assign (var
, init
);
1528 gsi_insert_on_edge_immediate (entry
, init_stmt
);
1533 /* Execute load motion for references in chain CHAIN. Uids of the newly
1534 created temporary variables are marked in TMP_VARS. */
1537 execute_load_motion (struct loop
*loop
, chain_p chain
, bitmap tmp_vars
)
1541 unsigned n_writes
= 0, ridx
, i
;
1544 gcc_assert (chain
->type
== CT_INVARIANT
);
1545 gcc_assert (!chain
->combined
);
1546 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1547 if (DR_IS_WRITE (a
->ref
))
1550 /* If there are no reads in the loop, there is nothing to do. */
1551 if (n_writes
== chain
->refs
.length ())
1554 initialize_root_vars_lm (loop
, get_chain_root (chain
), n_writes
> 0,
1555 &vars
, chain
->inits
, tmp_vars
);
1558 FOR_EACH_VEC_ELT (chain
->refs
, i
, a
)
1560 bool is_read
= DR_IS_READ (a
->ref
);
1562 if (DR_IS_WRITE (a
->ref
))
1568 var
= make_ssa_name (SSA_NAME_VAR (var
), NULL
);
1575 replace_ref_with (a
->stmt
, vars
[ridx
],
1576 !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
);
2041 acode
= gimple_assign_rhs_code (stmt
);
2042 aswap
= (!commutative_tree_code (acode
)
2043 && gimple_assign_rhs1 (stmt
) != name1
);
2044 atype
= TREE_TYPE (gimple_assign_lhs (stmt
));
2046 if (*code
== ERROR_MARK
)
2054 return (*code
== acode
2056 && *rslt_type
== atype
);
2059 /* Remove OP from the operation on rhs of STMT, and replace STMT with
2060 an assignment of the remaining operand. */
2063 remove_name_from_operation (gimple stmt
, tree op
)
2066 gimple_stmt_iterator si
;
2068 gcc_assert (is_gimple_assign (stmt
));
2070 if (gimple_assign_rhs1 (stmt
) == op
)
2071 other_op
= gimple_assign_rhs2 (stmt
);
2073 other_op
= gimple_assign_rhs1 (stmt
);
2075 si
= gsi_for_stmt (stmt
);
2076 gimple_assign_set_rhs_from_tree (&si
, other_op
);
2078 /* We should not have reallocated STMT. */
2079 gcc_assert (gsi_stmt (si
) == stmt
);
2084 /* Reassociates the expression in that NAME1 and NAME2 are used so that they
2085 are combined in a single statement, and returns this statement. */
2088 reassociate_to_the_same_stmt (tree name1
, tree name2
)
2090 gimple stmt1
, stmt2
, root1
, root2
, s1
, s2
;
2091 gimple new_stmt
, tmp_stmt
;
2092 tree new_name
, tmp_name
, var
, r1
, r2
;
2093 unsigned dist1
, dist2
;
2094 enum tree_code code
;
2095 tree type
= TREE_TYPE (name1
);
2096 gimple_stmt_iterator bsi
;
2098 stmt1
= find_use_stmt (&name1
);
2099 stmt2
= find_use_stmt (&name2
);
2100 root1
= find_associative_operation_root (stmt1
, &dist1
);
2101 root2
= find_associative_operation_root (stmt2
, &dist2
);
2102 code
= gimple_assign_rhs_code (stmt1
);
2104 gcc_assert (root1
&& root2
&& root1
== root2
2105 && code
== gimple_assign_rhs_code (stmt2
));
2107 /* Find the root of the nearest expression in that both NAME1 and NAME2
2114 while (dist1
> dist2
)
2116 s1
= find_use_stmt (&r1
);
2117 r1
= gimple_assign_lhs (s1
);
2120 while (dist2
> dist1
)
2122 s2
= find_use_stmt (&r2
);
2123 r2
= gimple_assign_lhs (s2
);
2129 s1
= find_use_stmt (&r1
);
2130 r1
= gimple_assign_lhs (s1
);
2131 s2
= find_use_stmt (&r2
);
2132 r2
= gimple_assign_lhs (s2
);
2135 /* Remove NAME1 and NAME2 from the statements in that they are used
2137 remove_name_from_operation (stmt1
, name1
);
2138 remove_name_from_operation (stmt2
, name2
);
2140 /* Insert the new statement combining NAME1 and NAME2 before S1, and
2141 combine it with the rhs of S1. */
2142 var
= create_tmp_reg (type
, "predreastmp");
2143 new_name
= make_ssa_name (var
, NULL
);
2144 new_stmt
= gimple_build_assign_with_ops (code
, new_name
, name1
, name2
);
2146 var
= create_tmp_reg (type
, "predreastmp");
2147 tmp_name
= make_ssa_name (var
, NULL
);
2149 /* Rhs of S1 may now be either a binary expression with operation
2150 CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
2151 so that name1 or name2 was removed from it). */
2152 tmp_stmt
= gimple_build_assign_with_ops (gimple_assign_rhs_code (s1
),
2154 gimple_assign_rhs1 (s1
),
2155 gimple_assign_rhs2 (s1
));
2157 bsi
= gsi_for_stmt (s1
);
2158 gimple_assign_set_rhs_with_ops (&bsi
, code
, new_name
, tmp_name
);
2159 s1
= gsi_stmt (bsi
);
2162 gsi_insert_before (&bsi
, new_stmt
, GSI_SAME_STMT
);
2163 gsi_insert_before (&bsi
, tmp_stmt
, GSI_SAME_STMT
);
2168 /* Returns the statement that combines references R1 and R2. In case R1
2169 and R2 are not used in the same statement, but they are used with an
2170 associative and commutative operation in the same expression, reassociate
2171 the expression so that they are used in the same statement. */
2174 stmt_combining_refs (dref r1
, dref r2
)
2176 gimple stmt1
, stmt2
;
2177 tree name1
= name_for_ref (r1
);
2178 tree name2
= name_for_ref (r2
);
2180 stmt1
= find_use_stmt (&name1
);
2181 stmt2
= find_use_stmt (&name2
);
2185 return reassociate_to_the_same_stmt (name1
, name2
);
2188 /* Tries to combine chains CH1 and CH2 together. If this succeeds, the
2189 description of the new chain is returned, otherwise we return NULL. */
2192 combine_chains (chain_p ch1
, chain_p ch2
)
2195 enum tree_code op
= ERROR_MARK
;
2200 tree rslt_type
= NULL_TREE
;
2204 if (ch1
->length
!= ch2
->length
)
2207 if (ch1
->refs
.length () != ch2
->refs
.length ())
2210 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2211 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2213 if (r1
->distance
!= r2
->distance
)
2216 if (!combinable_refs_p (r1
, r2
, &op
, &swap
, &rslt_type
))
2227 new_chain
= XCNEW (struct chain
);
2228 new_chain
->type
= CT_COMBINATION
;
2230 new_chain
->ch1
= ch1
;
2231 new_chain
->ch2
= ch2
;
2232 new_chain
->rslt_type
= rslt_type
;
2233 new_chain
->length
= ch1
->length
;
2235 for (i
= 0; (ch1
->refs
.iterate (i
, &r1
)
2236 && ch2
->refs
.iterate (i
, &r2
)); i
++)
2238 nw
= XCNEW (struct dref_d
);
2239 nw
->stmt
= stmt_combining_refs (r1
, r2
);
2240 nw
->distance
= r1
->distance
;
2242 new_chain
->refs
.safe_push (nw
);
2245 new_chain
->has_max_use_after
= false;
2246 root_stmt
= get_chain_root (new_chain
)->stmt
;
2247 for (i
= 1; new_chain
->refs
.iterate (i
, &nw
); i
++)
2249 if (nw
->distance
== new_chain
->length
2250 && !stmt_dominates_stmt_p (nw
->stmt
, root_stmt
))
2252 new_chain
->has_max_use_after
= true;
2257 ch1
->combined
= true;
2258 ch2
->combined
= true;
2262 /* Try to combine the CHAINS. */
2265 try_combine_chains (vec
<chain_p
> *chains
)
2268 chain_p ch1
, ch2
, cch
;
2269 vec
<chain_p
> worklist
= vNULL
;
2271 FOR_EACH_VEC_ELT (*chains
, i
, ch1
)
2272 if (chain_can_be_combined_p (ch1
))
2273 worklist
.safe_push (ch1
);
2275 while (!worklist
.is_empty ())
2277 ch1
= worklist
.pop ();
2278 if (!chain_can_be_combined_p (ch1
))
2281 FOR_EACH_VEC_ELT (*chains
, j
, ch2
)
2283 if (!chain_can_be_combined_p (ch2
))
2286 cch
= combine_chains (ch1
, ch2
);
2289 worklist
.safe_push (cch
);
2290 chains
->safe_push (cch
);
2296 worklist
.release ();
2299 /* Prepare initializers for CHAIN in LOOP. Returns false if this is
2300 impossible because one of these initializers may trap, true otherwise. */
2303 prepare_initializers_chain (struct loop
*loop
, chain_p chain
)
2305 unsigned i
, n
= (chain
->type
== CT_INVARIANT
) ? 1 : chain
->length
;
2306 struct data_reference
*dr
= get_chain_root (chain
)->ref
;
2310 edge entry
= loop_preheader_edge (loop
);
2312 /* Find the initializers for the variables, and check that they cannot
2314 chain
->inits
.create (n
);
2315 for (i
= 0; i
< n
; i
++)
2316 chain
->inits
.quick_push (NULL_TREE
);
2318 /* If we have replaced some looparound phi nodes, use their initializers
2319 instead of creating our own. */
2320 FOR_EACH_VEC_ELT (chain
->refs
, i
, laref
)
2322 if (gimple_code (laref
->stmt
) != GIMPLE_PHI
)
2325 gcc_assert (laref
->distance
> 0);
2326 chain
->inits
[n
- laref
->distance
]
2327 = PHI_ARG_DEF_FROM_EDGE (laref
->stmt
, entry
);
2330 for (i
= 0; i
< n
; i
++)
2332 if (chain
->inits
[i
] != NULL_TREE
)
2335 init
= ref_at_iteration (dr
, (int) i
- n
, &stmts
);
2336 if (!chain
->all_always_accessed
&& tree_could_trap_p (init
))
2340 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
2342 chain
->inits
[i
] = init
;
2348 /* Prepare initializers for CHAINS in LOOP, and free chains that cannot
2349 be used because the initializers might trap. */
2352 prepare_initializers (struct loop
*loop
, vec
<chain_p
> chains
)
2357 for (i
= 0; i
< chains
.length (); )
2360 if (prepare_initializers_chain (loop
, chain
))
2364 release_chain (chain
);
2365 chains
.unordered_remove (i
);
2370 /* Performs predictive commoning for LOOP. Returns true if LOOP was
2374 tree_predictive_commoning_loop (struct loop
*loop
)
2376 vec
<data_reference_p
> datarefs
;
2377 vec
<ddr_p
> dependences
;
2378 struct component
*components
;
2379 vec
<chain_p
> chains
= vNULL
;
2380 unsigned unroll_factor
;
2381 struct tree_niter_desc desc
;
2382 bool unroll
= false;
2386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2387 fprintf (dump_file
, "Processing loop %d\n", loop
->num
);
2389 /* Find the data references and split them into components according to their
2390 dependence relations. */
2391 stack_vec
<loop_p
, 3> loop_nest
;
2392 dependences
.create (10);
2393 datarefs
.create (10);
2394 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
2397 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2398 fprintf (dump_file
, "Cannot analyze data dependencies\n");
2399 free_data_refs (datarefs
);
2400 free_dependence_relations (dependences
);
2404 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2405 dump_data_dependence_relations (dump_file
, dependences
);
2407 components
= split_data_refs_to_components (loop
, datarefs
, dependences
);
2408 loop_nest
.release ();
2409 free_dependence_relations (dependences
);
2412 free_data_refs (datarefs
);
2416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2418 fprintf (dump_file
, "Initial state:\n\n");
2419 dump_components (dump_file
, components
);
2422 /* Find the suitable components and split them into chains. */
2423 components
= filter_suitable_components (loop
, components
);
2425 tmp_vars
= BITMAP_ALLOC (NULL
);
2426 looparound_phis
= BITMAP_ALLOC (NULL
);
2427 determine_roots (loop
, components
, &chains
);
2428 release_components (components
);
2430 if (!chains
.exists ())
2432 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2434 "Predictive commoning failed: no suitable chains\n");
2437 prepare_initializers (loop
, chains
);
2439 /* Try to combine the chains that are always worked with together. */
2440 try_combine_chains (&chains
);
2442 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2444 fprintf (dump_file
, "Before commoning:\n\n");
2445 dump_chains (dump_file
, chains
);
2448 /* Determine the unroll factor, and if the loop should be unrolled, ensure
2449 that its number of iterations is divisible by the factor. */
2450 unroll_factor
= determine_unroll_factor (chains
);
2452 unroll
= (unroll_factor
> 1
2453 && can_unroll_loop_p (loop
, unroll_factor
, &desc
));
2454 exit
= single_dom_exit (loop
);
2456 /* Execute the predictive commoning transformations, and possibly unroll the
2460 struct epcc_data dta
;
2462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2463 fprintf (dump_file
, "Unrolling %u times.\n", unroll_factor
);
2465 dta
.chains
= chains
;
2466 dta
.tmp_vars
= tmp_vars
;
2468 update_ssa (TODO_update_ssa_only_virtuals
);
2470 /* Cfg manipulations performed in tree_transform_and_unroll_loop before
2471 execute_pred_commoning_cbck is called may cause phi nodes to be
2472 reallocated, which is a problem since CHAINS may point to these
2473 statements. To fix this, we store the ssa names defined by the
2474 phi nodes here instead of the phi nodes themselves, and restore
2475 the phi nodes in execute_pred_commoning_cbck. A bit hacky. */
2476 replace_phis_by_defined_names (chains
);
2478 tree_transform_and_unroll_loop (loop
, unroll_factor
, exit
, &desc
,
2479 execute_pred_commoning_cbck
, &dta
);
2480 eliminate_temp_copies (loop
, tmp_vars
);
2484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2486 "Executing predictive commoning without unrolling.\n");
2487 execute_pred_commoning (loop
, chains
, tmp_vars
);
2491 release_chains (chains
);
2492 free_data_refs (datarefs
);
2493 BITMAP_FREE (tmp_vars
);
2494 BITMAP_FREE (looparound_phis
);
2496 free_affine_expand_cache (&name_expansions
);
2501 /* Runs predictive commoning. */
2504 tree_predictive_commoning (void)
2506 bool unrolled
= false;
2511 initialize_original_copy_tables ();
2512 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
2513 if (optimize_loop_for_speed_p (loop
))
2515 unrolled
|= tree_predictive_commoning_loop (loop
);
2521 ret
= TODO_cleanup_cfg
;
2523 free_original_copy_tables ();
2528 /* Predictive commoning Pass. */
2531 run_tree_predictive_commoning (void)
2536 return tree_predictive_commoning ();
2540 gate_tree_predictive_commoning (void)
2542 return flag_predictive_commoning
!= 0;
2547 const pass_data pass_data_predcom
=
2549 GIMPLE_PASS
, /* type */
2551 OPTGROUP_LOOP
, /* optinfo_flags */
2552 true, /* has_gate */
2553 true, /* has_execute */
2554 TV_PREDCOM
, /* tv_id */
2555 PROP_cfg
, /* properties_required */
2556 0, /* properties_provided */
2557 0, /* properties_destroyed */
2558 0, /* todo_flags_start */
2559 TODO_update_ssa_only_virtuals
, /* todo_flags_finish */
2562 class pass_predcom
: public gimple_opt_pass
2565 pass_predcom (gcc::context
*ctxt
)
2566 : gimple_opt_pass (pass_data_predcom
, ctxt
)
2569 /* opt_pass methods: */
2570 bool gate () { return gate_tree_predictive_commoning (); }
2571 unsigned int execute () { return run_tree_predictive_commoning (); }
2573 }; // class pass_predcom
2578 make_pass_predcom (gcc::context
*ctxt
)
2580 return new pass_predcom (ctxt
);